聚类

2.1 聚类的概念

“物以类聚，人以群分”，聚类是一种非监督学习，不同于分类的监督学习，聚类不会给出一个“正确答案”，而是通过识别模式样本之间的“相似性”，比如“距离”，“相似性”在阈值内则可以聚为一类。

---

2.2 相似性测度和聚类准则

2.2.1 相似性测度

1.欧式(Euclid)距离

image

即我们通常说的“直线距离”在多维向量中的拓展。

---

2.马氏(Maharanobis)距离

image

X：模式向量；M：均值向量；C：该类模式总体的协方差矩阵。

image image

当C = I 时，马氏距离退化为欧式距离。在欧式距离的基础上进行归一化，剔除了方差的影响。

---

3.明氏(Minkowaki)距离

image

也称为m-范数，当m=2时为欧式距离，m=1时称为“街坊距离”。

image

---

4.汉明(Hamming)距离

当模式向量各分量的取值为1或(-1)的二值模式时，用汉明模式衡量相似性。

image

若两个模式向量每个分量的取值都相等，则汉明距离为n；若两个模式向量的每个分量的取值都不相等，则汉明距离为0。

---

5.角度相似性函数

image

即两个模式向量之间夹角的余弦。（可联想高中数学中求余弦的方法）

当特征（模式向量的分量）的取值为0或1的二值模式时，这个度量具有特别的含义。

X^T_iX_j的值表示X_i和X_j中共有的特征数目。
而||X_i||·||X_j||表示X_i中具有特征的数目和X_j中具有特征数目的几何平均值。

---

6.Tanimoto测度

Tanimoto测度
只适用于0、1二值模式。

---

2.2.2 聚类准则

1.阈值准则

即简单的大于阈值T或小于阈值T则判定为真的准则。

---

2.函数准则

聚类准则函数：在聚类分析中，表示聚类过程中，所产生的中间分类结果质量的一种度量函数。
聚类准则函数是样本集{X}和模式类别{S_j, j=1,2,…,c}的函数，c为类别数。
一种常用的指标是误差平方之和：

误差平方和
J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。
聚类的目的就是使J的值达到极小。

---

2.3 基于距离阈值的聚类算法

2.3.1 近邻聚类法

算法描述：
（1）任取样本X_i作为第一个聚类中心的初始值，如令Z₁= X₁
（2）计算样本X2到Z1的欧氏距离D₂₁。
若D₂₁>T，定义一新的聚类中心Z₂= X₂；
否则X₂∈以Z₁为中心的聚类。
（3）假设已有聚类中心Z1、Z2，计算D₃₁=||X₃ - Z₁||和D₃₂=||X₃ - Z₂||
若D₃₁>T且D₃₂>T，则建立第三个聚类中心Z₃= X₃；
否则X3∈离Z₁和Z₂中最近者（最近邻的聚类中心）。

算法特点：
聚类中心的选取和模式样本的划分同时进行。
局限性：依赖第一个聚类中心的位置选择//某个模式样本离两个聚类中心的距离都在域值内，它属于哪个聚类取决于哪个聚类中心是聚类中心初始值；
待分类模式样本的排列次序;
距离阈值T的大小//太大只有一类，太小每个模式样本一类;
模式样本分布的几何性质等。
优点：简单、快速。

---

2.3.2 最大最小距离算法

也称小中取大距离算法。首先根据阈值寻找聚类中心，然后根据最近邻规则把模式样本划分至对应聚类中心中。

算法描述：
（1）任取一个模式样本作为第一类聚类中心Z₁。
（2）选择离Z₁距离最远的模式样本作为第二类聚类中心Z₂。
（3）逐个计算每个模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。
   因为共有N个模式样本，所以此时得到N个最小距离。
（4）在所有最小距离中取出一个最大距离，如果该最大值达到||Z₁ - Z₂||的一定分数比值（本算法的阈值）以上，则将此模式样本定义为新的聚类中心Z_i，并返回第（3）步。否则，聚类中心的寻找结束，进入第（5）步。
（5）寻找聚类中心结束后，将模式样本{X_i, i=1,2,…,N}按最近距离划分至对应聚类中心中。

算法特点：
按照小中取大原则先选出所有聚类中心，然后再将剩余模式样本划分至对应聚类中心中。

---

2.4 层次聚类法

也称系统聚类法或分级聚类法，是实际工作中采用最多的方法之一。

算法描述：
（1）建立N个聚类中心（即每个模式样本都是聚类中心）G₁(0),G₂(0),…,G_N(0)。并计算各类之间的距离，得到一个N×N维的距离矩阵D(0)。这里括号内的数表示聚类运算的轮数，0则表示初始化状态。
（2）找出距离矩阵D(0)中最小的元素，若此元素小于给出的阈值T，则将其对应的两类合并为一类，并建立新的分类：G₁(1),G₂(2),…,G_N(N-1)，且计算距离矩阵D(1)。
（3）重复（2）直到D(n)的最小元素大于T，这意味着所有的类间距离都大于T，这时所得的分类即为聚类结果。也可以不设阈值T，直到将所有样本聚为一类为止，输出聚类的分类树。

算法特点：
每个样本先自成一类，然后按距离逐步合并，减少类别数，直到达到分类要求。

距离计算准则：
（1）最短距离法。计算两类样本之间的最小距离。

最短距离法公式
最短距离法图示
（2）最长距离法
类似于最短距离法取最长距离。
（3）中间距离法
介于最长和最短之间。取法同最短距离法。
当K类由I类和J类合并而成，则H类和K类之间的距离为：
中间距离法的递推公式
（4）重心法
以上定义的类间距离未考虑每一类中所包含的样本数目，重心法在这一方面有所改进。若I类中有n_I个样本，J类中有n_J个样本，则：
重心法递推公式
（5）类平均距离法
类平均距离法公式

---

2.5 动态聚类法

先选择若干个聚类中心，再按照事先定义好的聚类准则进行聚类。过程中聚类中心不断地被修改，直到分类合理为止。“动态”指的是积累过程中聚类中心不断被修改的变化状态。

动态聚类法

2.5.1 K-均值算法

K-均值算法也称C-均值算法，是根据函数准则进行分类的聚类算法，目的是使聚类准则函数最小化。
这里使用的聚类准则函数是聚类集中每一个样本点到该聚类中心的距离平方和，对于第 j 个聚类集，准则函数定义为：

准则函数
S_j表示第j个聚类集，其聚类中心是Z_j，N_j表示S_j中的样本个数。
对所有K个J_j进行求和得：
求和结果
我们的目的是使J极小，对其求导得：
求导
这表明S_j类的聚类中心应选择该类样本的均值。

算法描述：
（1）任选K个聚类中心Z₁(1)，Z₂(1)，…，Z_K(1)，括号内的数表示迭代次序。
（2）按最短距离原则将其余样本分配到任一聚类中心中。
（3）计算各个聚类中心的新值（即该类样本均值）Z_j(k+1)，这里要计算K个聚类中心的样本均值，故称K-均值算法。
（4）如果新计算出的样本中心与上一轮的样本中心不一致，则回到步骤（2），直到Z_j(k+1)=Z_j(k)为止。除了第1轮的样本中心是存在的样本点外，之后计算出的样本中心可能都不存在于样本集中。