Cluster Analysis: K-means, Hierarchical & DBSCAN

1. What is Cluster Analysis?

ExamSlide 4：Finding groups of objects such that the objects in a group will be similar (or related) to one another and different from (or unrelated to) the objects in other groups.

• Intra-cluster distances are minimized
• Inter-cluster distances are maximized

Applications (slide 5)：

• Understanding：Group related documents for browsing、group genes and proteins that have similar functionality、group stocks with similar price fluctuations。
• Summarization：Reduce the size of large data sets（例：Clustering precipitation in Australia）。

Notion of a Cluster can be Ambiguous (slide 6)：同一組點可以睇成 Two Clusters、Four Clusters 或 Six Clusters——"How many clusters?" 冇唯一答案，視乎 granularity 同應用。

2. Types of Clusterings

Slide 7：A clustering is a set of clusters。重要區分：

2.1 Other Distinctions Between Sets of Clusters (Slide 10)

3. Types of Clusters

3.1 Characteristics of the Input Data Are Important (Slide 16)

• Type of proximity or density measure：central to clustering，視乎 data 同 application。
• 影響 proximity / density 嘅 data characteristics：Dimensionality、Sparseness（curse of dimensionality）、Attribute type、Special relationships in the data（例如 autocorrelation）、Distribution of the data。
• Noise and Outliers：often interfere with the operation of the clustering algorithm。

Slide 17：本 chapter 主要講 K-means clustering 同 Hierarchical clustering（另附 DBSCAN optional）。

4. K-means Clustering

Slide 19：

• Partitional clustering approach
• Number of clusters, K, must be specified
• Each cluster is associated with a centroid (center point)
• Each point is assigned to the cluster with the closest centroid
• The basic algorithm is very simple：

1: Select K points as the initial centroids.
2: repeat
3:     Form K clusters by assigning all points to the closest centroid.
4:     Recompute the centroid of each cluster.
5: until The centroids don't change

4.1 K-means Details (Slide 22)

• Initial centroids are often chosen randomly → clusters produced vary from one run to another。
• Centroid is (typically) the mean of the points in the cluster。
• 'Closeness' is measured by Euclidean distance, cosine similarity, correlation, etc.
• K-means will converge for common similarity measures mentioned above。
• Most of the convergence happens in the first few iterations；stopping condition 常改為 'Until relatively few points change clusters'。
• ExamComplexity is $O(n \times K \times I \times d)$：n = number of points，K = number of clusters，I = number of iterations，d = number of attributes。

4.2 Worked example：1-D K-means（自擬）

import numpy as np
from sklearn.cluster import KMeans
X = np.array([2, 3, 4, 10, 11, 12, 20, 25, 30]).reshape(-1, 1)
km = KMeans(n_clusters=2, init=np.array([[2], [12]]), n_init=1).fit(X)
km.labels_, km.cluster_centers_, km.inertia_      # inertia_ = SSE = 150

4.3 Evaluating K-means Clusters: SSE (Slide 23)

Most common measure is Sum of Squared Error (SSE)：每個 point 嘅 error = 佢同最近 cluster（centroid）嘅距離；將 errors 平方再加總：

$x$ 係 cluster $C_i$ 入面嘅 data point，$m_i$ 係 cluster $C_i$ 嘅 representative point。可以證明令 SSE 最細嘅 $m_i$ 就係 cluster 嘅 center (mean)。

• Given two sets of clusters, we prefer the one with the smallest error。
• ExamOne easy way to reduce SSE is to increase K（$K = n$ 時 $SSE = 0$！所以唔可以單靠 SSE 揀 K）。
• A good clustering with smaller K can have a lower SSE than a poor clustering with higher K。

Slide 24 "Two different K-means Clusterings"：同一組 original points，可以得到 Optimal Clustering 或 Sub-optimal Clustering——取決於 initial centroids。

4.4 Importance of Choosing Initial Centroids (Slides 25–31)

Slides 25–26 圖示：好嘅 initial centroids 幾個 iterations 就搵到 optimal；差嘅 initial centroids 會卡喺 sub-optimal（local minimum）。

ExamSlide 27：如果有 K 個 'real' clusters，揀到每個 cluster 各一個 initial centroid 嘅機會好細，K 越大越細。如果每個 cluster 大小都係 n：

例如 $K = 10$：$P = 10!/10^{10} = 3{,}628{,}800 / 10{,}000{,}000{,}000 =$ 0.00036。（$K = 3$：3!/27 = 0.222；$K = 5$：120/3125 = 0.0384。）

有時 initial centroids 會自己 readjust 去「正確」位置，有時唔會。Five pairs of clusters 例子（10 clusters，slides 28–31）：

• Slides 28–29：Starting with two initial centroids in one cluster of each pair of clusters → 每對 clusters 有兩個 centroids，結果可以正確分開。
• Slides 30–31：Starting with some pairs of clusters having three initial centroids, while others have only one → 有一個 centroid 嘅嗰對 clusters 會被合併成一個，有三個 centroids 嘅會將一個 cluster 錯誤切開。

4.5 Solutions to Initial Centroids Problem (Slide 32)

• Multiple runs：有幫助，但 probability is not on your side（K 大時要好多次）；揀 SSE 最細嗰次。
• Sample and use hierarchical clustering to determine initial centroids。
• Generate a larger number of clusters and then perform a hierarchical clustering（merging the clusters）。
• Select more than k initial centroids and then select among these initial centroids（e.g., select most widely separated）。
• Use some strategy to select the k initial centroids：K-means++ is a robust way of doing this selection。

4.6 K-means++ (Slide 33)

比 random initialization 慢，但 very consistently produces better results in terms of SSE；保證 approximation ratio $O(\log k)$ in expectation。

4.7 Limitations of K-means (Slides 34–40)

Overcoming K-means Limitations (slides 38–40)：One solution is to find a large number of clusters such that each of them represents a part of a natural cluster. But these small clusters need to be put together in a post-processing step.

4.8 Pre-processing and Post-processing (Slide 41)

5. Hierarchical Clustering

Slide 43：Produces a set of nested clusters organized as a hierarchical tree；can be visualized as a dendrogram——a tree like diagram that records the sequences of merges or splits（y 軸係 merge 時嘅距離）。

Strengths (slide 44)：

• Do not have to assume any particular number of clusters：any desired number of clusters can be obtained by 'cutting' the dendrogram at the proper level。
• They may correspond to meaningful taxonomies：例如 biological sciences 嘅 animal kingdom（slide notes：Vertebrates → Mammals（Primates、Rodents、Carnivores）、Birds、Reptiles、Fish；Invertebrates → Arthropods、Mollusks、Annelids）。

5.1 Agglomerative vs Divisive (Slide 45)

Traditional hierarchical algorithms use a similarity or distance matrix，merge or split one cluster at a time。

5.2 Agglomerative Clustering Algorithm (Slides 46–50)

1. Compute the proximity matrix
2. Let each data point be a cluster
3. Repeat
4.     Merge the two closest clusters
5.     Update the proximity matrix
6. Until only a single cluster remains

Slides 47–50：Starting situation（每點一個 cluster + proximity matrix）→ intermediate situation（clusters C1…C5）→ 要 merge 最近嘅 C2 同 C5 → merge 後問題："How do we update the proximity matrix?"（C2 ∪ C5 嗰行 / 列要重新計）。

5.3 How to Define Inter-Cluster Distance (Slides 51–55)

5.4 Worked example：MIN / MAX / Group Average（自擬）

五點 a–e 嘅 distance matrix：

MIN dendrogram（高度 = merge 距離）
 5 ┤       ┌─────┴─────┐
 4 ┤       │        ┌──┴──┐
 3 ┤       │        │   ┌─┴─┐
 2 ┤    ┌──┴──┐     │   │   │
   └────a─────b─────c───d───e──

from scipy.cluster.hierarchy import linkage, dendrogram
from scipy.spatial.distance import squareform
D = [[0,2,6,10,9],[2,0,5,9,8],[6,5,0,4,5],[10,9,4,0,3],[9,8,5,3,0]]
for m in ["single", "complete", "average"]:      # MIN, MAX, Group Average
    print(m, linkage(squareform(D), method=m))
dendrogram(linkage(squareform(D), "single"), labels=list("abcde"))

5.5 MIN (Single Link): Strength & Limitations (Slides 56–59)

• Strength：Can handle non-elliptical shapes（slide 58：six clusters，可以沿住鏈狀 / 彎曲形狀連埋一齊）。
• Limitation：Sensitive to noise（slide 59：noise points 可以喺兩個 clusters 之間「搭橋」，令佢哋被 chain 埋一齊——chaining effect）。

5.6 MAX (Complete Linkage): Strength & Limitations (Slides 60–63)

• Strength：Less susceptible to noise（slide 62）。
• Limitations：Tends to break large clusters；Biased towards globular clusters（slide 63）。

5.7 Group Average (Slides 64–66)

• Proximity of two clusters is the average of pairwise proximity between points in the two clusters。
• Need to use average connectivity for scalability since total proximity favors large clusters（所以要除以 $|C_i| \times |C_j|$）。
• Compromise between Single and Complete Link。
• Strengths：Less susceptible to noise and outliers。Limitations：Biased towards globular clusters。

5.8 Time and Space Requirements (Slide 67)

• $O(N^2)$ space since it uses the proximity matrix（N = number of points）。
• $O(N^3)$ time in many cases：there are N steps and at each step the size $N^2$ proximity matrix must be updated and searched。
• Complexity can be reduced to $O(N^2 \log(N))$ time with some cleverness。

對比 K-means 嘅 $O(n\cdot K\cdot I\cdot d)$，hierarchical clustering 對大 data sets 慢好多。

5.9 Problems and Limitations (Slide 68)

• Once a decision is made to combine two clusters, it cannot be undone（greedy）。
• No global objective function is directly minimized（唔似 K-means minimize SSE）。
• Different schemes have problems with one or more of：sensitivity to noise and outliers；difficulty handling clusters of different sizes and non-globular shapes；breaking large clusters。

6. Cluster Validity

Slide 70：Supervised classification 有 accuracy、precision、recall 等 measures。Cluster analysis 嘅對應問題係：點樣評估 clusters 嘅 "goodness"？但 "clusters are in the eye of the beholder"! 咁點解仲要評估？

• To avoid finding patterns in noise（K-means 喺 random data 上都會「搵到」K 個 clusters！）
• To compare clustering algorithms
• To compare two sets of clusters
• To compare two clusters

6.1 Different Aspects of Cluster Validation (Slide 71)

1. Determining the clustering tendency of a set of data, i.e., distinguishing whether non-random structure actually exists in the data。
2. Comparing the results of a cluster analysis to externally known results, e.g., to externally given class labels（external index）。
3. Evaluating how well the results of a cluster analysis fit the data without reference to external information（use only the data → internal index）。
4. Comparing the results of two different sets of cluster analyses to determine which is better。
5. Determining the 'correct' number of clusters。

For 2, 3, and 4, we can further distinguish whether we want to evaluate the entire clustering or just individual clusters。

6.2 Measures of Cluster Validity Via Correlation (Slides 72–73)

兩個 matrices：

• Proximity Matrix
• Ideal Similarity Matrix：每個 data point 一行一列；entry = 1 if the pair belongs to the same cluster，0 if different clusters。

計兩個 matrices 嘅 correlation。因為 matrices 係 symmetric，只需要計 $n(n-1)/2$ 個 entries。High correlation 表示同一 cluster 嘅點互相接近。Not a good measure for some density or contiguity-based clusters.

6.3 Using Similarity Matrix for Cluster Validation (Slides 74–76)

Order the similarity matrix with respect to cluster labels and inspect visually. 好嘅 clustering 會見到對角線上有清晰嘅高相似度方塊。Clusters in random data are not so crisp（slides 75–76：DBSCAN、K-means、Complete Link 喺 random data 上嘅方塊都模糊）。

6.4 Internal Measures: SSE (Slides 77–78)

Internal Index：used to measure the goodness of a clustering structure without respect to external information，例如 SSE。

• SSE is good for comparing two clusterings or two clusters（average SSE）。
• Can also be used to estimate the number of clusters：畫 SSE vs K 曲線，搵 "knee / elbow"（SSE 急跌之後變平嘅位置）。
• Clusters in more complicated figures aren't well separated（slide 78：SSE curve for a more complicated data set，elbow 未必明顯）。

sse = [KMeans(n_clusters=k, n_init=10, random_state=0).fit(X).inertia_ for k in range(1, 11)]
plt.plot(range(1, 11), sse, "o-"); plt.xlabel("K"); plt.ylabel("SSE")   # 搵 elbow

6.5 Framework for Cluster Validity (Slides 79–81)

• Need a framework to interpret any measure：例如 evaluation measure = 10，係 good、fair 定 poor？
• Statistics provide a framework：The more "atypical" a clustering result is, the more likely it represents valid structure in the data。
• 將 index 值同 random data / random clusterings 嘅 index 值比較；if the value of the index is unlikely, then the cluster results are valid。（較複雜、較難理解。）
• 比較兩組 cluster analyses 時 framework 較唔需要，但仍有「兩個 index 值嘅差是否 significant」嘅問題。

Statistical Framework for SSE (slide 80)：例子：compare SSE of 0.005 against three clusters in random data。Histogram 顯示 500 組 random data（每組 100 點，x、y 分佈於 0.2–0.8）分成 3 clusters 嘅 SSE——random data 嘅 SSE 遠大於 0.005，所以 $SSE = 0.005$ 嘅 clustering 好 "atypical" → 代表真實結構。

Statistical Framework for Correlation (slide 81)：同樣將 ideal similarity / proximity matrix 嘅 correlation 同 random data 比較。

6.6 Internal Measures: Cohesion and Separation (Slides 82–84)

• Cluster Cohesion：measures how closely related are objects in a cluster（例：SSE）。
• Cluster Separation：measure how distinct or well-separated a cluster is from other clusters（例：squared error between clusters）。

Proximity graph based approach (slide 84)：Cluster cohesion is the sum of the weight of all links within a cluster；cluster separation is the sum of the weights between nodes in the cluster and nodes outside the cluster。

6.7 Internal Measures: Silhouette Coefficient (Slide 85)

Silhouette coefficient combines ideas of both cohesion and separation，可以用於 individual points、clusters 同 clusterings。

from sklearn.metrics import silhouette_score, silhouette_samples
silhouette_samples(D, labels=[0,0,1,1,1], metric="precomputed")   # 每點 s
silhouette_score(X, km.labels_)                                     # 整體平均

7. Density Based Clustering: DBSCAN (Optional)

Slide 86：Clusters are regions of high density that are separated from one another by regions of low density。

Slides 88–89 例子圖：MinPts = 7 示意；Eps = 10, MinPts = 4 時 original points 被標記為 core、border、noise。

7.1 DBSCAN Algorithm (Slide 90)

Form clusters using core points, and assign border points to one of its neighboring clusters：

1. Label all points as core, border, or noise points。
2. Eliminate noise points。
3. Put an edge between all core points within a distance Eps of each other。
4. Make each group of connected core points into a separate cluster。
5. Assign each border point to one of the clusters of its associated core points。

7.2 When DBSCAN Works / Does NOT Work Well (Slides 91–92)

7.3 Determining Eps and MinPts (Slide 93)

• Idea：for points in a cluster, their k-th nearest neighbors are at close distance；noise points have the k-th nearest neighbor at farther distance。
• So, plot sorted distance of every point to its k-th nearest neighbor（k-distance plot）；曲線急升嘅 "knee" 位置就係 Eps 嘅好選擇，k 就做 MinPts。

from sklearn.neighbors import NearestNeighbors
from sklearn.cluster import DBSCAN
k = 4
dist, _ = NearestNeighbors(n_neighbors=k).fit(X).kneighbors(X)
plt.plot(np.sort(dist[:, -1]))                  # k-distance plot，搵 knee → Eps
labels = DBSCAN(eps=1.5, min_samples=3).fit_predict(np.array([1,2,3,4,8,9,20]).reshape(-1,1))
# labels: [0 0 0 0 -1 -1 -1]   (-1 = noise)

自我測驗 Self-test

一頁總結 Cheat sheet