type
Post
Created date
Jun 16, 2022 01:21 PM
category
Data Science
tags
Machine Learning
Machine Learning
status
Published
Language
From
summary
slug
password
Author
Priority
Featured
Featured
Cover
Origin
Type
URL
Youtube
Youtube
icon
Definition
- Partition Clustering (Non-Hierarchical)
- Divide the data objects into unique subsets, of which a number of sets (i.e., ) are pre-defined.
- are sequential either building up from separate clusters or breaking down from the one cluster.
- In some cases, the exact number of clusters may be known (like marketing customers group), then we can use Partition Clustering.
- A good clustering is one for which the within-cluster variation is as small as possible.
Knowing what Partition Clustering is, let's explore one of its kind — KNN.
- Each cluster is associated with a centroid
- Each point is assigned to the cluster with the CLOSEST centroid.
Theory
Assumption
- The data is in feature space, which means data in feature space can be measured by distance metrics such as Manhattan, Euclidean etc.
- Each data point can only belong to one cluster.
- Each training data point consists of a set of vectors and class labels associated with each vector.
- Wishes to have ‘K’ as an odd number in case of 2 class classification.
Mechanism - Here are the steps of KNN :
- Select k points (at random) as the initial centroids
- Repeat :
2.1. Form k clusters by assigning all points to the CLOSEST centroid
2.2. Re-compute the centroid of each cluster
- Until the centroids don’t change.
Why and Why not KNN :
Advantage :
- Simple to implement
- Since the KNN algorithm requires no training before making predictions, new data can be added seamlessly which will not impact the algorithm's accuracy.
Disadvantage :
It depends on initial values. The problem of which is that it has different :
- Sizes
- Density
- Non-globular shapes
- Contain outliers
Example
Bredwin
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fd1c0d14b-3bb5-41f6-b1ca-08baa27cc8bd%2Fk-means_clustering.jpeg%3Ftable%3Dblock%26id%3D17c80709-cc61-463d-bb0c-0bec0676df3f%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3Dd5VNZN4dOhePBCJj1roSUxoaBhvqXTAS66vfIiLBdfA?table=block&id=17c80709-cc61-463d-bb0c-0bec0676df3f&cache=v2)
Brendi
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F2715c45e-6056-4b52-b174-40b4a5a6a1af%2Fk-means-drawbacks.jpeg%3Ftable%3Dblock%26id%3D2e60bc69-bc5e-4913-a415-cdf6db83c29e%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D8oLPAm9_9okIRxumfgXcI72pSdXyGxpcp9rxKidU3EM?table=block&id=2e60bc69-bc5e-4913-a415-cdf6db83c29e&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F8e2da2bd-6e6c-4426-bc64-41e3f68731b9%2Fk-means.jpeg%3Ftable%3Dblock%26id%3D3f232a1c-3a6c-4600-a221-ca2173e0a2b1%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DG5fHZTrT5WW1eEl-CRR82CoZwgINp9SAS6zyLKmNOG0?table=block&id=3f232a1c-3a6c-4600-a221-ca2173e0a2b1&cache=v2)
R code
set.seed(2021) # set seed for reproducibility (kmeans have initialise at different random starts) flea_km <- stats::kmeans(flea_std[,2:7], centers = 3) ## flea_std is a numeric df.
Elbow plot
# factoextra::fviz_nbclust helper function; used; visualise & determine the optimal k factoextra::fviz_nbclust(x = tourr::flea %>% select(-species), FUNcluster = kmeans, method = "wss", # within cluster ss k.max = 10) # max no. of clusters to consider
Measure
R interpretation
Comparing HCluster
assumed you have run this
# --- (II) (III) compute distance matrix + pass as input into `stats::hclust` flea_hc_w <- stats::dist(flea_std[,2:7]) %>% stats::hclust(method = "ward.D2")
map cluster labels to obs. from both methods ```{r} flea_std <- flea_std %>% mutate(cl_w = stats::cutree(flea_hc_w, k = 3), # extract cluster solution from hclust; k = 3 cl_km = flea_km$cluster) # extract cluster solutions from k-means; k = 3 ``` compute confusion table; compare both results •note: labels doesn't matter ```{r} flea_std %>% count(cl_w, cl_km) %>% # compute agreemeent # pivot into wide form; create confusion table pivot_wider(names_from = cl_w, values_from = n, values_fill = 0) %>% rename("cl_km/cl_wards" = cl_km) ```
b. Map the cluster labels from the two results, and calculate the agreement.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F6dff536d-f5d5-4e92-bc69-410c07f937bb%2FUntitled.png%3Ftable%3Dblock%26id%3D76a9f1e3-83f9-49cb-a1db-f7f15f536e44%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DCZQqI-GN2QcTVkKjq9_u0FbdhW-8bRBQeCt0rnX_RgU?table=block&id=76a9f1e3-83f9-49cb-a1db-f7f15f536e44&cache=v2)
## matrix table(actual = flea_std$species, fitted = flea_km$cluster)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fa0befef1-f8a4-442c-a26e-8cb16c5bea40%2FUntitled.png%3Ftable%3Dblock%26id%3D449fe094-4a0f-4a5c-97ab-e3aeda36815f%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DVG8m_ewyWY2Zm1zggOBTuAIsUlRZcpTZXeHRnfcJjE8?table=block&id=449fe094-4a0f-4a5c-97ab-e3aeda36815f&cache=v2)
KNN and SSE
- Split ‘loose’ clusters, i.e., clusters with relatively HIGH SSE.
- If you have 100 data points, and you have 1 cluster, then your SSE is highest.
- Merge clusters that are ‘close’ and that have relatively LOW SSE.
- If you have 100 data points, and you have 100 clusters, then your SSE is 0.
FAQ
What are the advantages and disadvantages of hierarchical & non-hierarchical clustering
Hierarchical: are sequential either building up from separate clusters or breaking down from the one cluster.
Non-hierarchical: The number of clusters is chosen a priori.
Advantages of Hierarchical clustering
- All possible solutions (with respect to the number of clusters) is provided in a single analysis
- It is structured and can be explored using the dendrogram.
- Don’t need to assume any particular number of clusters. Any desired number of clusters can be obtained by ‘cutting’ the dendrogram at the proper level
Advantages of K-Means Clustering
- Can explore cluster allocations that will never be visited by the path of hierarchical solutions.
- With a large number of variables, if K is small, K-Means may be computationally faster than hierarchical clustering.
- K-Means might yield tighter clusters than hierarchical clustering
- An instance can change cluster (move to another cluster) when the centroids are recomputed.
Disadvantages of Hierarchical clustering
- It is not possible to undo the previous step: once the instances have been assigned to a cluster, they can no longer be moved around.
- Time complexity: not suitable for large datasets
- Very sensitive to outliers
Disadvantages of Hierarchical clustering
- Need to assume any particular number of clusters (K-Value), which is hard to predict.
- Initial seeds (centers of each cluster) have a strong influence on the final results
- Sensitive to scale.
How does each point find its closest centroid?
- To find its centroid, you need to calculate the "distance" between each point and all the centroids,
- then you will know which is the closest one.
Is there any Pre-processing for KNN?
Yes, you need to :
• Normalise the data
• Eliminate outliers
Is there any Post-processing for KNN?
• Eliminate small clusters that may represent outliers 埋吾到堆ge 走開
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Faea1c8bb-882a-4c99-848c-089e643eb07c%2FUntitled.png%3Ftable%3Dblock%26id%3D93c3947e-ecf8-4aee-b75d-32077628e0bf%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3Dgq9vPigu4i7PGKJ1q56X_jq751H3OZ9xLUBSXnMdc_w?table=block&id=93c3947e-ecf8-4aee-b75d-32077628e0bf&cache=v2)
SSE係埋堆的measure, 如果太高就分開佢地
-Split ‘loose’ clusters, i.e., clusters with relatively high SSE.
-Merge clusters that are ‘close’ and that have relatively low SSE
Will the initial centroids influence final clusters? if so, how do you cope with that?
Why is KNN tending to produce a good clustering?
Because the within-cluster variation tends to be small.
Math
![By partitioning K clusters, we want to minimise the total within-cluster variation as SMALL as possible.](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F4d7b0475-d838-4a20-9926-939a63743c89%2FUntitled.png%3Ftable%3Dblock%26id%3D47f9583a-d0e4-4801-85a1-b812659ba0ea%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DLOngBxLkzpkLtGA3YtvM5iigNCs1HvL4mlA6eOsXSsc?table=block&id=47f9583a-d0e4-4801-85a1-b812659ba0ea&cache=v2)
This link is good.
Reference
Extra Resource
Slides [Slides]
- Author:Jason Siu
- URL:https://jason-siu.com/article/3caabe32-cf84-4c41-991a-e977b87edd37
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts