7.6 聚类分析
7.6.1 距离与相似性的度量
7.6.2 聚类效果的评价指标
7.6.2.1 内部评价指标
- 轮廓系数
\[ s(i)=\frac{b(i)-a(i)}{\max\{a(i), b(i)\}} \]
\(a(i)\)表示样本i到同簇其他点的平均距离，度量簇内紧密度；\(b(i)\)表示样本i到最近邻簇所有点的平均距离，度量簇间分离度。
平均轮廓系数越大，表明聚类效果越好。
- DBI
\[ DBI = \frac{1}{k}\sum_{i=1}^k \max_{j \neq i }(\frac{\sigma_i + \sigma_j}{d(c_i, c_j)}) \]
其中\(\sigma_i\)表示簇i内样本到质心的平均距离，\(d(c_i, d_j)\)表示簇i与j质心间距离。
DBI越小越好。
- CH指数
\[ CH = \frac{SSB/(k-1)}{SSW/(n-k)} \]
其中\(SSB\)表示簇间平方和，\(SSW\)表示簇内平方和。
CH值越大越好。
7.6.3 系统聚类
7.6.3.1 类与类之间的距离
- 最短距离法：\(D_{KL} = \min\limits_{i\in G_K, j \in G_L} \{d_{ij}\}\)
适用于长条形的或不规则现状的类，对球形类的效果不是很好
- 最长距离法：\(D_{KL} = \max\limits_{i\in G_K, j \in G_L} \{d_{ij}\}\)
倾向于产生直径相等的类，易受异常值的影响
- 类平均法：\(D_{KL}=\frac{\sum_{i\in G_K, j \in G_L}d_{ij}}{n_Kn_L}\)
两类中所有距离的平均数，倾向于先合并方差小的类，而且偏向于产生方差相同的类
- 中间距离法：\(D_{MJ}^2=\frac{1}{2}D_{KJ}^2+\frac{1}{2}D_{LJ}^2-\frac{1}{4}D_{KL}^2\)
平行四边形的对角线的中线距离，
- 重心法：\(D_{KL}^2 = ||\bar X_K - \bar X_L||^2 = (\bar X_K-\bar X_L)'(\bar X_K-\bar X_L)\)
注意这里是平方距离，是重心差的内积。和其他系统聚类方法相比在处理异常值方面更稳健
- Ward法：\(D_{KL}^2 = ||\bar X_K - \bar X_L||^2/(\frac{1}{n_K}+\frac{1}{n_L})\)
在重心法的基础上多除了各自数量的倒数和。该法倾向于先合并样品少的类，且对异常值非常敏感
下面是不同形状数据及各种距离的系统聚类方法效果。
能完全分开的球状数据
各种距离的系统聚类方法均适用。
不能完全分开的球状数据
Ward法、类平均法、重心法的聚类形状差不多，Ward法比较适合样本大小相等的球状数据的聚类。
最短距离法最差。
样本大小不等的球状数据
重心法的聚类效果最好，类平均法偏向产生方差相等的类。
并排拉长的数据
最短距离法效果最好。
Ward法、类平均法、重心法都不行。数据进行预处理后可以得到较好的聚类结果。
非球状数据
最短距离法聚类效果最好。
Ward法、类平均法、重心法都不行，即使对数据进行预处理后仍不起作用。
系统距离的特点：
无需事先指定类的数目。
需要确定相异度（距离/相似性系数）和联接度量准则。
运算量较大，适用于小规模数据。
一旦完成合并或分裂，则无法撤销或修正。
7.6.4 Kmeans
算法步骤：
输入观测样本数据和聚类数目K。
随机将所有观测样本分配到K个类中，作为样本初始类。
分别计算K个类的中心\(\bar x^{(i)}, \, i=1,...,K\)。
计算每个观测样本到其所属类的中心的平方距离\(SSE=\sum_{i=1}^K\sum_{j\in G_i} ||x_j-\bar x^{(i)}||^2\)。
重新将每个观测样本分配到距离其最近的类中心所在的类中，使得SSE减少。
重复第3-5步，直至SSE不在减少，得到最终的聚类结果。
kmeans聚类的特点：
核心思想是使同类内所有样本点的总体差异性尽可能小。
适用于中大规模样本数据。
需要事先指定聚类的数目K。
不同的初始类可能会导致不同结果。
适用于发现球状类。
可能会陷入局部解。
对异常值非常敏感。
7.6.5 其他聚类方法
7.6.5.1 DBSCAN
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)基于数据点在空间分布上的密度来发现任意形状的簇。簇被定义为密度相连的点的最大集合。密度低于某个阈值的区域被视为噪声。
并非所有观测点都属于簇，允许噪声的存在
DBSCAN需要定义两个参数：半径eps与区域内最少点数minPts。对于任意一个点，在其半径内若存在多于区域内最少点数个点，那么就将该店标记为核心点，找到所有的核心点，并将所有密度可达的核心点归于一个簇中。非核心点若与核心点相邻则也属于该簇，反之则为离群点。
在R中，可用dbscan包的dbscan()实现，并通过kNNdistplot()来辅助判断半径大小。
当给定
minPts时（一般minPts>=维度数+1），kNNdistplot()的横轴表示按到k近邻的距离从小到大排序的点，纵轴表示距离，找到曲线的拐点对应的距离就是较为合适的半径