模糊聚类分析

模糊聚类分析----96845308-7160-11ec-a68e-7cb59b590d7d聚类分析就是将一个没有类别标记的样本集按照某种准则划分成若干个子集（类），使相似的样本尽可能归为一类，而不相似的样本尽可能划分到不同的类中。

由于在对样本集进行聚类的过程中，没有任何关于类别的先验知识，所以聚类分析属于无监督分类的范畴。

传统的聚类分析是一种硬划分，它严格地将每个待识别对象划分为一个类。

阶级划分的界限是明确的，具有非此即彼的性质。

在现实世界中，无论是一组对象根据其亲和力和相似性形成一个组，还是一个对象是否属于一个类别，其边界往往是不明确的，并且具有“这个和那个”的性质。

对于这种具有不确定性的聚类问题，模糊聚类分析提供了一种强有力的分析工具。

模糊聚类分析能够建立样本对于类别的不确定性描述，表达样本类属的中介性，已经成为聚类分析研究的主流。

粗略来讲，模糊聚类分析方法可分为两类：基于模糊等价关系的聚类方法和基于目标函数的聚类方法。

有时，这两类方法也结合起来使用。

一、数据预处理在模糊聚类分析中，我们称待分类的对象为样本。

要对样本进行合理的分类，首先应考虑样本的各种特性指标（观测数据）。

设有n个被分类对象，即样本集为x={x1，x2，…，xn}每一个xi有m个特性指标，即xi可表示为特性指标向量xi={xi1，xi2，…，xim}其中xij表示第i个样本的第j个特性指标。

于是，n个样本的特性指标矩阵为⎜⎜x21⎜M⎜⎜十、⎜n1x12lx1m⎜x22lx2m⎜xn2lxnm⎜⎜通常，我们也将样本集记为特性指标矩阵的形式，即x=(xij)n×m。

如果M个特征指标的维度和数量级不同，在运行过程中可能会突出一些大数量级特征指标的作用，而一些小数量级特征指标的作用可能会减少甚至被排除，导致每个特征指标的分类缺乏统一的尺度。

因此，为了消除不同特征指标单位和数量级的影响，当特征指标的维度和数量级不同时，通常会提前对各种指标值进行数据标准化（归一化），使每个指标值统一在一个共同的数值特征范围内。

我们称之为数据预处理。

常用的数据标准化方法有两种：均值方差标准化和极大极小标准化。

(1)均值方差标准化假设给定的样本集为x=（Xij）n×m。

标准化样本集为x=（x′ij）n×m。

然后，i=1,2,…,n，j=1,2,…,mj=∑xij，σj=(2)极大极小标准化（十九）−j），j=1,2，…，m∑N−1i=1设给定的样本集为x=(xij)n×m，标准化之后的样本集为x=(x′ij)n×m，则xij−xjminxjmax−xjmin，i=1,2,…,n，j=1,2,…,mxjmin=min{xij}，xjmax=max{xij}，j=1,2，…，m显然，实施数据标准化之后，每个指标值均在区间[0,1]中。

二、基于模糊等价关系的聚类方法（Ⅰ）模糊等价矩阵聚类方法模糊等价矩阵聚类方法是典型的基于模糊等价关系的聚类方法之一。

其主要思想就是从计算各个样本之间的相似性统计量出发，建立样本集x上的模糊相似矩阵（关系）；通过改造模糊相似矩阵为模糊等价矩阵，达到对样本集x进行模糊聚类的目的。

模糊等价矩阵聚类法1°选择适当的相似性统计量；2°构造样本集上的模糊相似矩阵；3°将模糊相似矩阵改造为模糊等价矩阵；4°聚类；画出聚类的谱系图。

1．建立模糊相似矩阵将样本集分类为x={x1，X2，…，xn}或x=（Xij）n×m，并已标准化。

如果可以计算相似性统计RiJ来测量样本席XI和XJ之间的相似性，那么，i,j=1,2,…,n0≤rij≤1，其中，RiJ＝0表示样本席席和XJ根本不相似，RiJ＝1表示样本席Xi和XJ完全相似或相等，RII表示样本Xi和它们自身之间的相似程度，它总是被取为1，即，RII＝1，I ＝1,2，…N.然后，基于样本集X，建立描述样本之间模糊相似关系的模糊相似矩阵⎜r11r12⎜⎜r21r22r=⎜⎜rr⎜n1n2lr1n⎜⎜lm⎜lrnn⎜⎜常用的计算样本的相似性统计量的方法有如下几种：(1)相关系数法−我|⋅|xjk−j|i=∑xik，j=∑xjkmk=1mk=1(2)夹角余弦法x2ik⋅x2jk(3)数量积法⎜1.⎜里杰=⎜1.其中m为一适当选取的正数，满足⋅xjk，我≠J⎜m⎜m≥max⎜∑xik⋅xjk⎜（4）最大最小法k=1mk=1（5）算术平均最小值法(xik+xjk)∑2k=1（6）几何平均最小值法xik⋅xjk（7）指数相似系数法其中sk是第k个特征的标准差：1.∑emk=14(xik−xjk)−⋅23sks=(∑希克−k）二,(8)绝对值指数法（9）绝对值减法∑|xik−xjk|1.−C∑|希克−xjk |，i≠J⎜k=1⎜其中，c是一个适当选取的数，使得0≤rij≤1。

（10）绝对倒数法i=j⎜1,⎜m⎜,i≠jrij=⎜m⎜∑|希克−xjk|⎜⎜k=1其中m为适当选取的正数，使得0≤rij≤1。

2.将模糊相似矩阵转化为模糊等价矩阵根据计算相似性统计量得到的模糊矩阵r，一般只满足自反性和对称性，即r是相似矩阵。

为了进行模糊聚类，需将r改造成模糊等价矩阵。

为此采用平方法求出r的传递闭包t(r)，t(r)便是所求的模糊等价矩阵。

根据得到的模糊等价矩阵t（R），我们可以使用不同层次的割矩阵来得到该层次的聚类结果。

所有不同层次的聚类结果构成了聚类谱系。

例环境单元分类每个环境单元包括四个要素：空气、水、土壤和作物。

环境单元的污染状况通过四种元素中污染物含量的超标来描述。

有五个环境单位，其污染数据如下：i=(5,5,3,2)，ii=(2,3,4,5)，iii=(5,5,2,3)，iv=(1,5,3,1)，v=(2,4,5,1)让u={I，II，III，IV，V}，并尝试对u进行分类。

解样本集的特性指标矩阵为⎜5.⎜⎜2.⎜5.⎜⎜1.⎜2.⎜53554342352.⎜⎜5.⎜3.⎜⎜1.⎜1.⎜⎜由于数据不存在量纲和数量级的差异，故不需进行数据标准化，直接进入构造模糊相似矩阵步骤。

按照绝对值减数法建立模糊相似关系，取c=0.1，得模糊相似矩阵⎜⎜0.1r=⎜0.8⎜⎜0.5⎜0.3⎜⎜1.⎜⎜0.3r2=⎜0.8⎜⎜0.5⎜0.5⎜⎜1⎜⎜0.4r8=⎜0.8⎜⎜0.5⎜0.5⎜0.310.30.40.40.410.40.40.40.80.310.50.50.80.410.50.50.50.40.510.60.50.40.510.60.110.10.20.40.80.110.50.30.50.20.510.60.3⎜⎜0.4⎜0.3⎜⎜0.6⎜1⎜⎜0.410.40.40.40.80.410.50.50.50.40.510.60.5⎜⎜0.4⎜0.5⎜，⎜0.6⎜1⎜⎜用平方法求传递闭包，将模糊相似矩阵转化为模糊等价矩阵。

我们有：⎜⎜0.4⎜⎜0.40.5⎜，r4=⎜0.8⎜⎜0.6⎜⎜0.5⎜0.51⎜⎜⎜0.5⎜0.5⎜=r4⎜0.6⎜1⎜⎜因此，传递闭包t（R）=R4是模糊等价矩阵。

根据得到的模糊等价矩阵t（R），通过使用不同级别的切割矩阵，得到每个级别的聚类结果，如下所示：当0.0≤λ≤0.4时，u分为一类：{i,ii,iii,iv,v}；当0.4最后，所有不同级别的聚类结果形成如下聚类谱系：不同水平下聚类结果的谱系图（二）模糊最大生成树聚类方法模糊最大支撑树聚类方法是另一个典型的基于模糊等价关系的聚类方法。

它首先构造一个完全赋权图k|x|，k|x|中的顶点为待分类的样本点，边权为相应的两个样本之间的相似性统计量值；然后通过寻找完全赋权图k|x|的最大支撑树，来进行聚类。

模糊最大生成树聚类法1°选择合适的相似性统计；2.在样本集上构造模糊相似矩阵；3°根据模糊相似关系矩阵构造完全赋权图；4°寻找完全赋权图的最大支撑树；5°由最大支撑树进行聚类分析。

1．建立模糊相似矩阵将样本集分类为x={x1，X2，…，xn}或x=（Xij）n×m，并已标准化。

如果可以计算相似性统计RiJ来测量样本席XI和XJ之间的相似性，那么，i,j=1,2,…,n0≤rij≤1，其中，RiJ＝0表示样本席席和XJ根本不相似，RiJ＝1表示样本席Xi和XJ完全相似或相等，RII表示样本Xi和它们自身之间的相似程度，它总是被取为1，即，RII＝1，I＝1,2，…N.然后，基于样本集X，建立描述样本之间模糊相似关系的模糊相似矩阵⎜r11r12r=⎜2122⎜rr⎜n1n2lr1n⎜⎜lrnn⎜⎜建立模糊相似矩阵的方法与模糊等价矩阵聚类法完全相同。

2．构造完全赋权图构造一个完全加权的图k x，其中顶点集是x= {x1，x2，…，xn}，每个边xxJ的权重是席和XJ之间的相关性。

系数（模糊相似关系矩阵中的元素）rij。

3.找到k | x的最大支撑树|用kruskal算法或者prim算法，求完全赋权图k|x|的最大支撑树（生成树）t。

kruskal算法和prim算法可参见相关的图论著作。

4．聚类选择合适的阈值λ，切断小于最大支持树tλ的权重。

连接的顶点（采样点）属于同一类。

例如，设x={1，…，6}，已知的模糊相似矩阵为：⎜1⎜⎜0.53⎜0.38r=⎜⎜0.45⎜0.64⎜⎜0.60⎜利用图论中的prim算法，可求得矩阵10.380.450.530.380.381⎜0.380.451⎜⎜0.530.550.591⎜⎜1616⎜⎜1.⎜⎜t=⎜56423⎜⎜0.640.600.550.530.53⎜⎜⎜其中，矩阵t中的第一、第二行表示构成最大支撑树t的边的端点标号，第三行表示对应的边权值，如图。

根据最大生成树T，可以得到不同层次的聚类结果如下：当0.00≤λ≤0.53时，x分为一类：{1,2,3,4,5,6}；当0.53最后，所有不同级别的聚类结果形成如下聚类谱系：不同水平下聚类结果的谱系图（三）最佳阈值的确定基于模糊等价关系的模糊聚类算法，如上述的模糊等价矩阵法和模糊最大支撑树法，本质上是一种动态的聚类方法，最终给出的只是在不同水平下的聚类结果。

如何选择阈值λ，使得在λ水平下样本集的聚类结果更为合理，我们称之为最佳阈值的确定问题。

最佳阈值通常根据问题的背景和经验知识来确定，也可以运用f统计量来选择理论最佳阈值。

如果样本集X={x1，X2，…，xn}的第k个样本的特征索引向量是XK={XK1，xk2，…，XKM}，k=1，。

，N、倪是第二个iiiiiii}，的特征指数向量为XK，k=1，。

，Ni，I类样品的数量，I类样品为{x1i，X2，K，xnixk=（XK1，xk2，K，XKM）则第i个类的聚类中心向量为vi=（v，v，k，v），v=，j=1,…,m样本集的中心向量为=(1,2,k,m)，j=∑xj，j=1,…,m设置λ值对应的Cλ并构造F统计量ni||vi−||2∑c−1i=1fλ=λcλni||xij−vi||2∑∑n−cλi=1j=1在公式中，分子表示类之间的距离，分母表示类内的距离，Fλ越大，分类越合理，与最大F统计量对应的阈值λ*是最佳阈值。