要点
- 对象：静态数据；
- 过程：以某种方式分组；
- 结果：同一集合中的元素相异度尽可能小，不同集合中的元素相异度尽可能大；
- 特点：集合特点在划分之前不给定，无监督学习。
在许多时候分类条件不满足，尤其是处理海量数据时，如果通过预处理使数据满足分类算法的要求，代价巨大，应考虑聚类算法
聚类分析讨论的对象是大量的样品，要求能合理地对所有样品进行分类，没有任何模式可供参考或依循，即是在没有先验知识的情况下进行的。
如何对事物进行定量分类呢？我们知道，同类事物具有很强的相似性，即同类事物之间的“距离”应很小，因此我们用距离统计量作为分类依据。
距离
样本间距离
最常用的是闵可夫斯基距离。
当特征变量（指标）观测值具有不同的数量级和不同的测量单位时，直接使用上式计算距离常使数值较小的指标失去作用，为提高分类效果，常需对数据进行 预处理 ，常采用的预处理方式有两种：
- 标准化
$x_{ik}=\dfrac{x_{ik}-\bar x_k}{S_k}$
$\bar x_k=1/n \sum\limits_{i=1}^n x_{ik}$ $S_k=[1/n\sum\limits_{i=1}^n(x_{ik}-\bar x_k)^2]^0.5$ - 正规化
$x’_ {ik}=\dfrac{x_{ik}-\min\limits_i (x_{ik})}{\max\limits_i (x_{ik})-\min\limits_i(x_ik)}$
类与类之间的距离
- SingleLinkage
- 又叫做 nearest-neighbor ,最短距离法，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离，也就是说，最近两个样本之间的距离越小，这两个类之间的相似度就越大。容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster 。
$D_{pq}=\min\limits_{i\in p,j\in q} d_{ij}$ - CompleteLinkage
- 这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大，两个 cluster 即使已经很接近了，但是只要有不配合的点存在，就顽固到底，老死不相合并，也是不太好的办法。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点。
- Average-linkage
- 类平均距离法, 这种方法就是把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。
$D^2_ {pq}=\dfrac{1}{n_p n_q}\sum\limits_ {j \in p}\sum\limits_ {j \in q} d^2_ {ij}$ - average-linkage
- 的一个变种就是取两两距离的中值，与取均值相比更加能够解除个别偏离样本对结果的干扰。
- 重心距离法
- $D_{pq}=d(\bar X_p,\bar X_q)$
受异常值影响较小，但不单调，可能导致树状聚类图上的图形逆转。 - Ward最小方差法
- $D(C_i,C_j)=\sum\limits_{x\in C_{ij}}(x-r_{ij})^2 - \sum\limits_{x\in C_i}(x-r_i)^2-\sum\limits_{x\in C_j}(x-r_j)^2$
很少受到异常值影响，但要求样本间距离是欧氏距离。
常用聚类方法
- 系统聚类Hierachical Clustering Methods
- K-means
- 高斯混合模型Gaussian Mixture Models
- 模糊C均值聚类Fuzzy C-Means Clustering
- DBSCAN
聚类结果的评价
- 画图直观评价
- 轮廓系数(Silhouette Coefficient)
- ARI(Adjusted Rand index)
轮廓系数
- 簇内不相识度
- 样本i到同簇其它样本的平均距离$a_i$
- 簇不相识度
- 一个簇内所有点的 簇内不相似度
- 簇间不相似度
- 样本i到簇$C_j$的平均距离为$b_{ij}$,簇间不相似度为$b_j=\min (b_{i1},b_{i2},…,b_{iK})$
- 样本i的轮廓系数
- 定义i的簇内不相似度为$a_i$,
簇间不相似度为$b_i$,
那么轮廓系数为$s_i=\dfrac{b_i-a_i}{\max (a_i,b_i)}$
$s_i$接近1表示样本i聚类合理，接近-1表示聚类不合理，接近0表示样本在两个簇的边界上。 - 聚类的轮廓系数
- 所有点的轮廓系数的平均。
ARI
有“标准答案”时，可以用ARI评价聚类结果
A，B 是两种划分
ARI(A,B)=0,表示A，B划分是独立的
ARI(A,B)=1， 表示A，B 划分是完全相同的。
