聚类算法

聚类分析

聚类分析的基本思想是在样品之间定义距离，在变量之间定义相似系数，距离或相似系数代表样品或变量之间的相似程度。按相似程度的大小，将样品（或变量）逐一归类，关系密切的类聚到一个小的分类单位，然后逐步扩大，使得关系疏远的聚合到一个大的分类单位，知道所有样品（或变量）都聚集完毕，形成一个表示亲疏关系的谱系图，依次按照某些要求对样品（或变量）进行分类。

1 分类统计量——距离与相似系数

样品之间的相似性度量——距离

用样品之间的距离来衡量各样品之间的相似程度。

广义的距离有:欧式距离、绝对距离、Minkowski距离、Chebyshev距离、方差加权距离和马氏距离。本仿真中用欧氏距离。

2 谱系聚类算法（层次聚类法）

谱系聚类法的思想：先将样品合成小类，再逐步扩大为大类。

2.1 合并距离

Gp，Gq分别表示两个类，设它们分别含有np，nq各样品。若类Gp中有样品x1，x2,，……xnp，则其均值为

1xpnpxi1nri，称为类Gp的重心。类Gp和Gq之间的距离记为Dpq。

(1) 最短距离：类与类之间的距离为两类最近样品间的距离。

(2) 最长距离：类与类之间的距离为两类最远样品间的距离。

(3) 类平均距离：类与类之间的距离为两个类中所包含的节点距离的平均值。

Dpq1npnqiGpjGqdij

Dpqd(xp,xq)(4) 中心距离：类与类之间的距离为两个类中心之间的距离。

(5) Ward距离：每次的合并保证同一类内的离差平方和最小。

Dpqnpnqnpnq(xpxq)T(xpxq)

2.2 步骤：

(6)

（0）n个样品开始时作为n个类，计算两两之间的距离，构成一个对称距离矩阵D。

(7)

选择D（0）中的非对角上的最小元素，将该对角元素对应的两个类合成一个类。

同时在D（0）中消去对应的行和咧，并加入新类与剩下的其未合并的类间的距离组成的一行和一列，得到一个新的距离矩阵，它是n-1阶方阵。

(8) 重复第二步，直到达到合适的类数为止。

3 模糊C均值聚类算法

3.1 思路

给定数据集Xx1,x2,…xn，其中每个样本包含s个属性。FCM算法就是将数据集X划分到c（2cn）个类中，vv1,v2,…vc为c个聚类中心。FCM的目标函数如下：

m2J(U,c1,...,cc)Jiuijdiji1i1jccn…………（1）

其中：uij表示第j个样本属于第i类的隶属度，聚类中心与第j个数据点间的欧几里德距离。

uij[0,1],uij1i1c。dij=||ci-xj||为第i个

FCM算法就是求在满足

uij[0,1],uij1i1c的条件下，目标函数最小。类中心和隶属度函

数可以通过以下函数计算求出。

uvij1nj1nmijxjumij…………………………………… (2)

和

uij1dijk1dkjc2/(m1)………………………………… (3)

3.2 算法流程

1. 输入聚类数目c，模糊因子m和迭代中止条件；

2. 初始化聚类中心V0；

3. 用公式计算U；

4. 用公式计算V1；

5. 如果|V1-V0|，则迭代中止，转步骤6；否则，令V0=V1，转向步骤3；

6. 输出结果（V，U）。

3.3 该算法的不足

1. 聚类个数c需要预先给定。

2. 算法对初始值的选取依赖性极大以及算法常陷入局部极小解。

3.4 改进算法：

1. 初始聚类中心的选取；