【统计学习方法死磕系列Ⅱ】聚类算法

一、引言：无监督学习的基石

聚类（Clustering）是无监督学习中最核心的任务之一。与分类不同，聚类面对的数据没有标签——我们不知道每个样本属于哪个类别，甚至不知道一共有几个类别。聚类的目标是：将数据集中的样本自动划分为若干个组（簇，cluster），使得组内样本尽可能相似，组间样本尽可能不同。

聚类算法广泛应用于客户分群、图像分割、异常检测、文档聚类、基因表达分析等领域。本文将系统介绍六种经典聚类算法：k-means 及其改进、k-medoids、DBSCAN、层次聚类、谱聚类和高斯混合模型，并讨论聚类评估指标。

二、k-means 聚类

2.1 算法原理

k-means（k 均值）是最经典、最广泛使用的聚类算法，由 MacQueen 于 1967 年提出。它基于原型聚类的思想：每个簇由一个中心点（centroid）来代表。

数学模型：

给定数据集 $X = {x_1, x_2, \dots, x_N}$，k-means 的目标是将数据分为 $k$ 个簇 $C = {C_1, C_2, \dots, C_k}$，最小化簇内平方误差（Within-Cluster Sum of Squares, WCSS）：

$$ J = \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2 $$

其中 $\mu_j = \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i$ 是簇 $C_j$ 的均值（中心点）。

2.2 算法流程（Lloyd 算法）

Algorithm: k-means (Lloyd's algorithm)
--------------------------------------
Input:  X = {x1, ..., xN}, k (number of clusters), max_iters
Output: cluster assignments and centroids

1. Initialize k centroids μ1, ..., μk randomly (e.g., pick k random points)

2. Repeat until convergence or max_iters:
   // Assignment step:
   For each point xi:
       Assign xi to cluster j where j = argmin_j ||xi - μj||^2
   
   // Update step:
   For each cluster j:
       μj = (1/|Cj|) * Σ_{xi ∈ Cj} xi
   
3. Return cluster assignments and centroids

2.3 Python 实现

import numpy as np

class KMeans:
    def __init__(self, n_clusters=3, max_iters=300, tol=1e-4):
        self.k = n_clusters
        self.max_iters = max_iters
        self.tol = tol
        self.centroids = None
    
    def fit(self, X):
        n_samples, n_features = X.shape
        
        # Initialize centroids randomly
        idx = np.random.choice(n_samples, self.k, replace=False)
        self.centroids = X[idx]
        
        for _ in range(self.max_iters):
            # Assignment step
            distances = self._euclidean_distances(X, self.centroids)
            labels = np.argmin(distances, axis=1)
            
            # Update step
            new_centroids = np.zeros_like(self.centroids)
            for j in range(self.k):
                cluster_points = X[labels == j]
                if len(cluster_points) > 0:
                    new_centroids[j] = cluster_points.mean(axis=0)
                else:
                    # Handle empty cluster: reinitialize
                    new_centroids[j] = X[np.random.randint(n_samples)]
            
            # Check convergence
            shift = np.sum((new_centroids - self.centroids) ** 2)
            if shift < self.tol:
                break
            
            self.centroids = new_centroids
        
        self.labels_ = labels
        return self
    
    def _euclidean_distances(self, X, centroids):
        """Compute pairwise squared Euclidean distances"""
        # ||x - μ||^2 = ||x||^2 + ||μ||^2 - 2·x·μ^T
        X_norm = np.sum(X ** 2, axis=1, keepdims=True)
        C_norm = np.sum(centroids ** 2, axis=1)
        cross = np.dot(X, centroids.T)
        return X_norm + C_norm - 2 * cross
    
    def predict(self, X):
        distances = self._euclidean_distances(X, self.centroids)
        return np.argmin(distances, axis=1)

2.4 vq 风格的 k 均值

在实际工程中，通常不使用上面的纯 Python 实现，而是使用高度优化的工业级实现。例如 scipy.cluster.vq.kmeans2 或 sklearn.cluster.KMeans：

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=3, init='k-means++', n_init=10, max_iter=300)
kmeans.fit(X)
print(f"Inertia (WCSS): {kmeans.inertia_:.2f}")
print(f"Centroids:\n{kmeans.cluster_centers_}")

2.5 k-means++ 初始化

标准的 k-means 随机初始化容易导致收敛到较差的局部最优。k-means++ 是一种智能初始化策略（Arthur & Vassilvitskii, 2007）：

Algorithm: k-means++ initialization
--------------------------------------
1. Choose first centroid μ1 uniformly at random from X

2. For each remaining centroid μj (j = 2, ..., k):
   a. For each point xi, compute D(xi) = min_{p<j} ||xi - μp||^2
      (distance to the nearest already-chosen centroid)
   b. Choose new centroid μj from X with probability proportional to D(xi)^2

3. Proceed with standard k-means

直观理解：k-means++ 倾向于选择距离已有中心较远的点作为新中心，使初始中心更加分散，从而更可能收敛到好的解。

概率选择：

$$ P(x_i \text{ 被选为下一个中心}) = \frac{D(x_i)^2}{\sum_{j} D(x_j)^2} $$

2.6 k 值选择：肘部法则与 Silhouette

肘部法则（Elbow Method）：

画出 WCSS 随 k 的变化曲线，当曲线出现明显的”肘部”（拐点）时，该点对应的 k 就是合适的簇数。

wcss = []
for k in range(1, 11):
    kmeans = KMeans(n_clusters=k, init='k-means++')
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)

# Plot: k vs WCSS, look for the "elbow"

轮廓系数（Silhouette Score）：

轮廓系数不需要真实标签，它衡量簇内紧致性和簇间分离性的平衡：

对于样本 $i$：

$a(i)$：样本 $i$ 到同簇其他样本的平均距离（簇内相似度）
$b(i)$：样本 $i$ 到最近其他簇中所有样本的平均距离（簇间不相似度）

$$ s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} $$

$s(i) \in [-1, 1]$，接近 1 表示聚类优良，接近 0 表示样本在边界，接近 -1 表示可能分错了簇。

整体聚类质量为所有样本 $s(i)$ 的平均值。

三、k-medoids：k-means 的抗噪版本

3.1 动机

k-means 使用均值作为簇中心，对离群点非常敏感。一个极端点可以把中心拉得很远，扭曲整个簇。k-medoids（k 中心点）使用实际的数据点作为簇中心（medoid），对噪声和离群点更加鲁棒。

3.2 PAM 算法（Partitioning Around Medoids）

k-medoids 最经典的实现是 PAM 算法：

Algorithm: PAM (Partitioning Around Medoids)
----------------------------------------------
1. Initialize: select k data points as initial medoids

2. Repeat:
   For each pair (h, i) where h is a medoid and i is a non-medoid:
       Compute total cost reduction if swapping h with i
   If there exists a swap that reduces cost:
       Perform the best swap
   Else:
       Converged, return medoids

代价计算：使用绝对误差（L1 距离），总代价为 $\sum_j \sum_{x \in C_j} |x - m_j|_1$。

3.3 CLARA 和 CLARANS

PAM 算法在大型数据集上计算量过大（每次评估交换需 $O(k(N-k)^2)$）。

CLARA（Clustering LARge Applications）：随机采样多个子集，在每个子集上运行 PAM，选最佳结果
CLARANS（Clustering Large Applications based on RANdomized Search）：随机搜索交换组合，避免遍历所有可能性

3.4 k-means vs k-medoids 对比

方面	k-means	k-medoids
簇中心	均值（可能不在数据中）	实际数据点
距离度量	必须用欧氏距离	任意距离度量
对离群点	非常敏感	鲁棒
计算复杂度	$O(Nk \cdot \text{iters})$	$O(k(N-k)^2)$
可解释性	一般	好（中心是实际样本）

四、DBSCAN：基于密度的聚类

4.1 动机

k-means 有两个根本性局限：

只能发现球形簇，无法处理任意形状的簇
必须预先指定 k

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）基于样本密度的连通性来定义簇，能处理任意形状，并自动识别噪声点。

4.2 核心概念

DBSCAN 基于两个关键参数：

$\varepsilon$（eps）：邻域半径
MinPts：核心点所需的最小邻域点数

定义了三种样本点：

类型	定义	含义
核心点（core point）	$\|N_{\varepsilon}(x)\| \geq \text{MinPts}$	在簇的密集区域内部
边界点（border point）	非核心点，但在某核心点的 $\varepsilon$ 邻域内	在簇的边缘
噪声点（noise point）	既非核心点也非边界点	不属于任何簇

其中 $N_{\varepsilon}(x) = {x’ \in X : d(x, x’) \leq \varepsilon}$。

密度可达（density-reachable）：点 $p$ 从点 $q$ 密度可达，如果存在核心点序列 $p_1, \dots, p_m$ 使得 $p_1 = q, p_m = p$，且 $p_{i+1}$ 在 $p_i$ 的 $\varepsilon$ 邻域内。

密度相连（density-connected）：点 $p$ 和 $q$ 都与某点 $o$ 密度可达，则 $p$ 和 $q$ 密度相连。一个簇就是所有密度相连的点的最大集合。

4.3 算法流程

Algorithm: DBSCAN
----------------------------------------------
Input:  X, eps, min_samples
Output: cluster labels (-1 for noise)

1. Mark all points as unvisited
2. cluster_id = 0

3. For each point p in X:
   If p is visited: continue
   
   Mark p as visited
   neighbors = points within eps distance of p
   
   If |neighbors| < min_samples:
       Mark p as NOISE (-1)
   Else:
       cluster_id += 1
       ExpandCluster(p, neighbors, cluster_id)

function ExpandCluster(p, neighbors, cluster_id):
   Assign p to cluster_id
   
   For each q in neighbors:
       If q is not visited:
           Mark q as visited
           q_neighbors = points within eps distance of q
           If |q_neighbors| >= min_samples:
               neighbors = neighbors ∪ q_neighbors
       If q is not assigned to any cluster:
           Assign q to cluster_id

4.4 Python 实现

from sklearn.neighbors import NearestNeighbors
import numpy as np

class DBSCAN:
    def __init__(self, eps=0.5, min_samples=5):
        self.eps = eps
        self.min_samples = min_samples
    
    def fit(self, X):
        n_samples = len(X)
        self.labels_ = np.full(n_samples, -1, dtype=int)  # -1 = unvisited/noise
        
        # Use k-d tree for fast neighbor search
        nn = NearestNeighbors(radius=self.eps)
        nn.fit(X)
        
        cluster_id = 0
        for i in range(n_samples):
            if self.labels_[i] != -1:
                continue
            
            # Find neighbors within eps
            neighbors = nn.radius_neighbors([X[i]], return_distance=False)[0]
            
            if len(neighbors) < self.min_samples:
                self.labels_[i] = -1  # noise
            else:
                cluster_id += 1
                self._expand_cluster(X, nn, i, neighbors, cluster_id)
        
        self.n_clusters_ = cluster_id
        return self
    
    def _expand_cluster(self, X, nn, point_idx, neighbors, cluster_id):
        self.labels_[point_idx] = cluster_id
        
        i = 0
        while i < len(neighbors):
            q = neighbors[i]
            
            if self.labels_[q] == -1:  # not yet visited
                self.labels_[q] = cluster_id
                q_neighbors = nn.radius_neighbors([X[q]], return_distance=False)[0]
                
                if len(q_neighbors) >= self.min_samples:
                    # Add new neighbors
                    neighbors = np.concatenate([neighbors, q_neighbors])
            
            i += 1

4.5 参数选择

$\varepsilon$ 的选择——k-距离图法：

from sklearn.neighbors import NearestNeighbors

# Compute distances to k-th nearest neighbor
k = min_samples - 1
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X)
distances, _ = nn.kneighbors(X)
# Sort distances by k-th neighbor
k_dist = np.sort(distances[:, -1])

# Plot k-dist graph; ε should be at the "elbow"

$\varepsilon$ 应选在 k-距离图的”膝盖”处——该点之前距离平缓，之后急剧上升。

MinPts 的选择经验法则：

$\text{MinPts} \geq d + 1$（$d$ 为特征维数）
通常 $\text{MinPts} = 2 \cdot d$
大数据集和有噪声的场景下适当增大

五、层次聚类（Hierarchical Clustering）

5.1 凝聚式与分裂式

层次聚类构建一个树状的簇层次结构（dendrogram），无需预先指定簇数。

类型	起点	方向	复杂度
凝聚式（agglomerative）	每个样本一个簇	自底向上合并	更常用
分裂式（divisive）	所有样本一个簇	自顶向下分裂	较少用

5.2 簇间距离度量（Linkage）

凝聚式层次聚类的关键是定义两个簇之间的距离。常见的 linkage 准则：

单链接（Single Linkage）：

$$ d(C_i, C_j) = \min_{x \in C_i, y \in C_j} \|x - y\| $$

两簇中最近点对的距离。容易产生”链状效应”（chaining effect）。

全链接（Complete Linkage）：

$$ d(C_i, C_j) = \max_{x \in C_i, y \in C_j} \|x - y\| $$

两簇中最远点对的距离。倾向于产生紧凑的球形簇。

平均链接（Average Linkage）：

$$ d(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i} \sum_{y \in C_j} \|x - y\| $$

Ward 链接：

合并后使簇内平方误差增加最小的两个簇合并：

$$ \Delta(C_i, C_j) = \frac{|C_i||C_j|}{|C_i| + |C_j|} \|\mu_i - \mu_j\|^2 $$

Ward 方法是实践中效果最好也是最常用的 linkage。

5.3 算法流程

Algorithm: Agglomerative Hierarchical Clustering
----------------------------------------------
1. Initialize: each point is its own cluster

2. Compute pairwise distance matrix between all clusters

3. Repeat N - 1 times:
   a. Find the two closest clusters Ci and Cj
   b. Merge Ci and Cj into a new cluster
   c. Update distance matrix (compute distances to new cluster)

4. Return dendrogram; cut at desired height to get k clusters

5.4 树状图（Dendrogram）与剪枝

Dendrogram 是层次聚类的可视化工具。横轴是样本，纵轴是合并距离。

选择簇数的方法：在 dendrogram 中寻找合并距离跳跃最大的位置（即在合并两个差异很大的簇之前剪枝）。

from scipy.cluster.hierarchy import dendrogram, linkage, fcluster

# Ward linkage
Z = linkage(X, method='ward')

# Cut dendrogram at k clusters
labels = fcluster(Z, t=k, criterion='maxclust')

# Plot dendrogram
dendrogram(Z)

六、谱聚类（Spectral Clustering）

6.1 动机

k-means 在非凸形状的簇上表现很差（如两个嵌套的环）。谱聚类将聚类问题转化为图割问题，能够处理任意形状的簇。

6.2 算法原理

谱聚类基于图的拉普拉斯矩阵的谱分解。

算法流程：

Algorithm: Spectral Clustering
----------------------------------------------
1. Construct similarity graph:
   - ε-neighborhood graph: connect points within distance ε
   - k-NN graph: connect each point to its k nearest neighbors
   - Fully connected graph with RBF kernel

2. Compute graph Laplacian L = D - W
   where W is the affinity matrix, D_ii = Σ_j W_ij

3. Compute first k eigenvectors of L (corresponding to smallest eigenvalues)

4. Use the eigenvectors as feature vectors, apply k-means

6.3 数学基础

相似度矩阵：通常使用高斯核

$$ W_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) $$

非归一化拉普拉斯：$L = D - W$

归一化拉普拉斯（两种常见形式）：

对称归一化：$L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$
随机游走归一化：$L_{\text{rw}} = D^{-1} L = I - D^{-1} W$

6.4 为什么谱聚类有效？

考虑理想情况（数据完美分为 k 个连通分量），拉普拉斯矩阵 $L$ 有 k 个零特征值，每个特征值对应的特征向量是指示向量（该分量内的点为 1，其余为 0）。

在实际中（数据不完全断开），前 k 个特征向量近似于指示向量，它们将数据嵌入到一个低维空间，在该空间中簇是线性可分的。因此最后一步用 k-means 就能轻松分割。

6.5 Python 实现

from sklearn.cluster import SpectralClustering
from sklearn.neighbors import kneighbors_graph

# Option 1: Direct sklearn
sc = SpectralClustering(n_clusters=3, affinity='rbf', gamma=0.1)
labels = sc.fit_predict(X)

# Option 2: Manual implementation for learning
from scipy.sparse.linalg import eigsh
from sklearn.cluster import KMeans

def spectral_clustering(X, k, sigma=1.0):
    n = len(X)
    # Adjacency matrix (RBF kernel)
    W = np.exp(-np.sum((X[:, np.newaxis] - X[np.newaxis, :]) ** 2, axis=2) 
               / (2 * sigma ** 2))
    # Degree matrix
    D = np.diag(np.sum(W, axis=1))
    # Normalized Laplacian
    D_inv_sqrt = np.linalg.inv(np.sqrt(D) + 1e-10 * np.eye(n))
    L = np.eye(n) - D_inv_sqrt @ W @ D_inv_sqrt
    # Eigen-decomposition
    eigvals, eigvecs = eigsh(L, k=k, which='SM')
    # k-means on eigenvectors
    kmeans = KMeans(n_clusters=k)
    labels = kmeans.fit_predict(eigvecs[:, :k])
    return labels

七、高斯混合模型（GMM）聚类

7.1 软聚类与硬聚类

k-means 对每个样本给出硬分配（hard assignment）：每个样本恰好属于一个簇。GMM 给出软分配（soft assignment）：每个样本以一定的概率属于每个簇。

GMM 聚类是 EM 算法在聚类任务上的直接应用（详见《EM算法》一文）。

7.2 GMM 与 k-means 的关系

方面	k-means	GMM
簇形状	仅球形	椭圆形（任意协方差）
分配方式	硬分配	软分配（概率）
模型	非概率	概率模型
协方差类型	$\sigma^2 I$（球形）	full, tied, diag, spherical
收敛	局部最优	局部最优
参数个数	$k \cdot d$	$k \cdot (d + d(d+1)/2 + 1)$

7.3 协方差约束类型

GMM 中每个组分可以有不同类型的协方差矩阵：

类型	描述	参数数	适用场景
`full`	各组分独立的完全协方差	$k \cdot d(d+1)/2$	任何形状
`tied`	所有组分共享同一个协方差	$d(d+1)/2$	同形状不同位置
`diag`	各组分独立的对角协方差	$k \cdot d$	轴对齐椭圆
`spherical`	各组分独立的球形协方差	$k$	各组分球形

spherical 等同于软 k-means。

八、聚类评估指标

8.1 内部指标（无需真实标签）

轮廓系数（Silhouette Score）：

$$ s = \frac{1}{N} \sum_{i=1}^{N} \frac{b(i) - a(i)}{\max(a(i), b(i))} $$

Davies-Bouldin Index（DBI）：

衡量簇间分离度和簇内紧致度的比值，越小越好：

$$ DB = \frac{1}{k} \sum_{i=1}^{k} \max_{j \neq i} \frac{\sigma_i + \sigma_j}{d(\mu_i, \mu_j)} $$

其中 $\sigma_i$ 是簇 $i$ 内样本到中心的平均距离。

Calinski-Harabasz Index（CHI）：

方差比准则，越大越好：

$$ CH = \frac{\text{tr}(B_k) / (k-1)}{\text{tr}(W_k) / (N-k)} $$

其中 $B_k$ 是簇间散布矩阵，$W_k$ 是簇内散布矩阵。

8.2 外部指标（需要真实标签）

调整兰德指数（Adjusted Rand Index, ARI）：

$$ ARI = \frac{\text{RI} - \mathbb{E}[\text{RI}]}{\max(\text{RI}) - \mathbb{E}[\text{RI}]} $$

ARI $\in [-1, 1]$，1 表示完美匹配，0 表示随机水平。

归一化互信息（Normalized Mutual Information, NMI）：

$$ NMI(Y, C) = \frac{2 \cdot I(Y; C)}{H(Y) + H(C)} $$

NMI $\in [0, 1]$。

九、算法选择指南

场景	推荐算法	原因
簇是球形的	k-means (k-means++)	快速，实现简单
有离群点	k-medoids, DBSCAN	鲁棒性强
任意形状	DBSCAN, 谱聚类	基于密度/图
需要层次结构	层次聚类（Ward linkage）	产生 dendrogram
大样本，小维度	k-means	速度最快
高维数据	谱聚类（先降维）	k-means 在高维效果差
簇大小差异大	DBSCAN, GMM	k-means 偏向等大簇
需要软分配	GMM	概率输出
不确定 k	DBSCAN, 层次聚类	无需预设 k

十、面试高频问题

Q1：k-means 的收敛性如何？它一定会收敛到全局最优吗？

k-means 的 Lloyd 算法保证经过有限步迭代后收敛（因为每次迭代 WCSS 要么减小要么不动，而可能的聚类分配是有限的）。但收敛到的是局部最优，而非全局最优。

k-means 的 WCSS 目标函数是 NP-hard 的。理论上找到全局最优解需要枚举所有可能的聚类分配，这是指数复杂度的。实践中通过 k-means++ 初始化和多次随机运行（设置 n_init=10）来增加找到好解的概率。

Q2：DBSCAN 的 $\varepsilon$ 和 MinPts 如何选择？

MinPts：通常取 $2 \cdot d$（d 为特征维数），或至少 $d + 1$。对于大数据集可以适当增大。

$\varepsilon$：使用 k-距离图（k = MinPts - 1）——计算每个点到其第 k 近邻的距离，将这些距离排序后绘图，在”膝盖”处取 $\varepsilon$。如果 $\varepsilon$ 太小会导致大量数据被标为噪声（欠聚类），太大则导致不同簇被合并（过聚类）。

Q3：k-means 和 GMM 的关系？什么时候用 GMM？

两者在极限意义下同构：当 GMM 各组分协方差趋于 $\sigma^2 I$ 且 $\sigma^2 \to 0$ 时，E 步的软分配退化为硬分配，M 步等价于 k-means 的均值更新。这种情况下两者等价。

使用 GMM 的场景：

需要样本属于各簇的概率（而不仅是硬标签）
簇的形状不是球形（GMM 可以学习椭圆形的簇）
需要生成式模型作密度估计（如异常检测时判断”样本是否来自任一簇”）
需要统计推断（如检验某参数是否显著）

Q4：谱聚类为什么能处理非凸形状的簇？

谱聚类通过拉普拉斯矩阵的特征向量将原始数据嵌入到一个新的空间中（谱嵌入），在这个新空间中，原始空间中非凸的簇变得”球状”和线性可分。最后一步在这个低维嵌入空间做 k-means，从而间接实现了对原始空间中任意形状簇的分割。

数学上看，拉普拉斯矩阵的前 k 个特征向量提供了图的最小能量划分，对应最优的归一化图割（Normalized Cut）。

Q5：如何处理大规模数据的聚类问题？

Mini-batch k-means：每次只用小批量样本更新中心，适合百万级样本
BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）：增量构建 CF 树（Clustering Feature Tree），适合流式数据和超大规模数据
CLARANS：k-medoids 的高效近似
先采样再聚类：随机采样 + 标准算法
分布式聚类：Spark MLlib 提供了分布式 k-means 实现
降维：先 PCA/UMAP 降到低维，再聚类

十一、总结

聚类是无监督学习的核心任务，本文系统介绍了六大经典算法族：基于原型的 k-means 和 k-medoids、基于密度的 DBSCAN、基于层次的层次聚类、基于图的谱聚类，以及基于概率的 GMM。每种方法都有其适用场景和局限性。

理解这些算法的关键不仅在于掌握它们的数学细节，更在于建立对”哪种数据用哪种聚法”的直觉——球形用 k-means，有噪声用 DBSCAN，需要层次用层次聚类，非凸用谱聚类，需要软分配用 GMM。在实践中，建议同时尝试多种方法，使用 Silhouette Score 和 DBI 等内部指标进行模型选择。

参考文献：

MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium.
Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. SODA ‘07.
Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. KDD ‘96.
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. NIPS.
Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53-65.