模糊聚类分析

模糊聚类分析

聚类分析就是将一个没有类别标记的样本集按照某种准则划分成若干个子集（类），使相似的样本尽可能归为一类，而不相似的样本尽可能划分到不同的类中。由于在对样本集进行聚类的过程中，没有任何关于类别的先验知识，所以聚类分析属于无监督分类的范畴。

传统的聚类分析是一种硬划分，它将每个待识别的对象严格地划分到某个类中，类别划分的界限是分明的，具有“非此即彼”的性质。而现实世界中，一组对象根据其亲疏程度和相似性是否形成一个类群，或一个对象是否属于一个类别，其界限往往是不分明的，具有“亦此亦彼”的性质。对于这种带有不确定性的聚类问题，模糊聚类分析提供了有力的分析工具。

模糊聚类分析能够建立样本对于类别的不确定性描述，表达样本类属的中介性，已经成为聚类分析研究的主流。粗略来讲，模糊聚类分析方法可分为两类：基于模糊等价关系的聚类方法和基于目标函数的聚类方法。有时，这两类方法也结合起来使用。

一、数据预处理

在模糊聚类分析中，我们称待分类的对象为样本。要对样本进行合理的分类，首先应考虑样本的各种特性指标（观测数据）。设有n个被分类对象，即样本集为

X = {x1, x2, …, xn}

每一个xi有m个特性指标，即xi可表示为特性指标向量

xi = {xi1, xi2, …, xim}

其中xij表示第i个样本的第j个特性指标。于是，n个样本的特性指标矩阵为

⎛x11

⎜⎜x21⎜M⎜⎜x⎝n1x12Lx1m⎞

⎟

x22Lx2m⎟

MLM⎟

⎟

xn2Lxnm⎟⎠

通常，我们也将样本集记为特性指标矩阵的形式，即X = (xij)n×m。

如果m个特性指标的量纲和数量级都不相同，在运算过程中就可能会因为突出某些数量级特别大的特性指标对分类的作用，而降低甚至排除某些数量级很小的特性指标的作用，致使对各特性指标的分类缺乏一个统一的尺度。所以，为了消除特性指标单位的差别和数量级不同的影响，当特性指标的量纲和数量级不相同时，通常事先对各种指标值实施数据标准化（规格化），从而使得各个指标值都统一于某种共同的数值特性范围。我们称之为数据预处理。

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

设给定的样本集为X = (xij)n×m，标准化之后的样本集为X = (x′ij)n×m，则

′=xij

式中

xij−j

σj

，i = 1, 2, …, n，j = 1, 2, …, m

1n

j=∑xij，σj=

ni=1

(2) 极大极小标准化

1n

(xij−j)，j = 1, 2, …, m ∑n−1i=1

设给定的样本集为X = (xij)n×m，标准化之后的样本集为X = (x′ij)n×m，则

′=xij

式中

xij−xjminxjmax−xjmin

，i = 1, 2, …, n，j = 1, 2, …, m

xjmin=min{xij}，xjmax=max{xij}，j = 1, 2, …, m

1≤i≤n

1≤i≤n

显然，实施数据标准化之后，每个指标值均在区间 [0, 1] 中。

二、基于模糊等价关系的聚类方法 （一）模糊等价矩阵聚类方法

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

模糊等价矩阵聚类法

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

设待分类的样本集为X = {x1, x2, …, xn} 或X = (xij)n×m，并已经标准化。如果能够计算出衡量样本xi与xj之间相似程度的相似性统计量rij，使得

，i, j = 1, 2, …, n 0 ≤ rij ≤ 1，

其中，rij = 0表示样本xi与xj之间毫不相似，rij = 1表示样本xi与xj之间完全相似或者等同，rii表示样本xi自己与自己的相似程度，恒取为1，即rii = 1，i = 1, 2, …, n，那么，描述样本之间的模糊相似关系、建立在样本集X上的模糊相似矩阵为

⎛r11r12⎜

⎜r21r22R=⎜

MM⎜

⎜rr⎝n1n2Lr1n⎞

⎟Lr2n⎟

⎟LM⎟Lrnn⎟⎠

常用的计算样本的相似性统计量的方法有如下几种： (1) 相关系数法

rij=

∑|x

k=1

m

ik

−i|⋅|xjk−j|

∑(x

k=1

m

ik

−i)2⋅

∑(x

k=1

m

ik

−j)2

其中

1m1m

i=∑xik，j=∑xjk

mk=1mk=1

(2) 夹角余弦法

rij=

∑x

k=1

m

ik

⋅xjk

∑

k=1

m

x2ik⋅x2jk

(3) 数量积法

⎧1,⎪rij=⎨1

⎪⎩M

其中M为一适当选取的正数，满足

i=j

∑x

k=1

m

ik

⋅xjk,i≠j

⎧m⎫M≥max⎨∑xik⋅xjk⎬

i, j

⎩k=1⎭

(4) 最大最小法

rij=

∑min(x

k=1mk=1

m

ik

,xjk)

∑max(x

m

ik

,xjk)

(5) 算术平均最小法

rij=

∑min(x

k=1

m

ik

,xjk)

1

(xik+xjk)∑2k=1

(6) 几何平均最小法

rij=

∑min(x

k=1m

m

ik

,xjk)

∑

k=1

xik⋅xjk

(7) 指数相似系数法

rij=

其中Sk是第k个特征的标准差：

1∑emk=1

m

2

4(xik−xjk)−⋅23Sk

1m

S=(∑xik−k)2

nk=1

2k

(8) 绝对值指数法

−

rij=e

(9) 绝对值减数法

∑|xik−xjk|

k=1

m

i=j⎧1,

⎪m

rij=⎨

1−c∑|xik−xjk|,i≠j⎪k=1⎩

其中，c是一个适当选取的数，使得0 ≤ rij ≤ 1。

(10) 绝对值倒数法

i=j⎧1,⎪M⎪,i≠j rij=⎨m

⎪∑|xik−xjk|⎪⎩k=1

其中M为适当选取的正数，使得0 ≤ rij ≤ 1。

2．改造模糊相似矩阵为模糊等价矩阵

根据计算相似性统计量得到的模糊矩阵R，一般只满足自反性和对称性，即R是相似矩阵。为了进行模糊聚类，需将R改造成模糊等价矩阵。为此采用平方法求出R的传递闭包t(R)，t(R) 便是所求的模糊等价矩阵。

3．聚类

根据得到的模糊等价矩阵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⎝

5355434235

2⎞⎟5⎟3⎟ ⎟1⎟1⎟⎠

由于数据不存在量纲和数量级的差异，故不需进行数据标准化，直接进入构造模糊相似矩阵步骤。按照绝对值减数法建立模糊相似关系，取c = 0.1，得模糊相似矩阵

⎛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.4

0.80.310.50.50.80.410.50.5

0.50.40.510.60.50.40.510.6

0.110.10.20.40.80.110.50.30.50.20.510.6

0.3⎞⎟0.4⎟0.3⎟ ⎟0.6⎟1⎟⎠0.410.40.40.4

0.80.410.50.5

0.50.40.510.6

0.5⎞⎟0.4⎟0.5⎟，

⎟0.6⎟1⎟⎠

用平方法求传递闭包，以便将模糊相似矩阵改造成模糊等价矩阵，我们有：

0.5⎞⎛1

⎟⎜0.4⎟⎜0.40.5⎟，R4=⎜0.8⎟⎜0.6⎟⎜0.5

⎜0.51⎟⎠⎝0.5⎞

⎟0.4⎟

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，并已经标准化。如果能够计算出衡量样本xi与xj之间相似程度的相似性统计量rij，使得

，i, j = 1, 2, …, n 0 ≤ rij ≤ 1，

其中，rij = 0表示样本xi与xj之间毫不相似，rij = 1表示样本xi与xj之间完全相似或者等同，rii表示样本xi自己与自己的相似程度，恒取为1，即rii = 1，i = 1, 2, …, n，那么，描述样本之间的模糊相似关系、建立在样本集X上的模糊相似矩阵为

⎛r11r12

⎜

r⎜r

R=⎜2122

MM⎜

⎜rr⎝n1n2Lr1n⎞

⎟Lr2n⎟

LM⎟

⎟Lrnn⎟⎠

建立模糊相似矩阵的方法与模糊等价矩阵聚类法完全相同。 2．构造完全赋权图

构造一个完全赋权图K|X| ，K|X| 中顶点集为X = {x1, x2, …, xn}，每条边xixj的权值为xi与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.38

⎞⎟⎟⎟1

⎟

0.381⎟0.380.451⎟⎟0.530.550.591⎟⎠

1616⎞⎛1

⎜⎟T=⎜56423⎟

⎜0.640.600.550.530.53⎟⎝⎠

其中，矩阵T中的第一、第二行表示构成最大支撑树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，ni为第

iiiiiii

}， 的特性指标向量为xk，k = 1, …, ni，i个类的样本数，第i个类的样本为 {x1i, x2, K, xnixk=(xk1, xk2, K, xkm)

则第i个类的聚类中心向量为

1

vi=(v, v, K, v)，v=

ni

i1

i2

im

ij

∑x

k=1

ni

ikj

，j = 1, …, m

样本集的中心向量为

1n

=(1, 2, K, m)，j=∑xj，j = 1, …, m

nk=1

设Cλ 为对应 λ 值的聚类数，构造F统计量

1Cλ

ni||vi−||2∑C−1i=1

Fλ=λ Cλni

1

||xij−vi||2∑∑n−Cλi=1j=1

式中分子表示类间距离，分母表示类内距离，Fλ 越大说明分类越合理，对应F统计量最大的阈值 λ* 为最佳阈值。

三、模糊C均值聚类方法

模糊C均值（FCM，Fuzzy C Means）聚类算法是一个通用的数据聚类算法，其中每个样本点属于一个类的程度，以一个隶属度来指定。在基于目标函数的模糊聚类方法中，FCM算法的理论最为完善，应用

最为广泛。

（一）模糊C均值（FCM）聚类算法

并且在每个模糊群组中寻FCM将一个含有n个向量的样本集X = {x1, x2, …, xn} 划分成c个模糊群组，

找一个聚类中心，使得一个基于距离测度的目标函数最小化。它兼顾了类之间的交迭，允许对象对所有的类有部分归属。每一个样本点都以0和1之间的一个隶属程度属于任何群组，聚类的结果是用下面的c×n矩阵

U=(μik)c×n

⎛μ11

⎜⎜μ=⎜21

M⎜⎜μ⎝c1

μ12Lμ1n⎞

⎟

μ22Lμ2n⎟

M

μc2

⎟LM⎟

Lμcn⎟⎠

表示的一个模糊c划分：

Mfc = {U∈Rc×n | μik∈[0, 1]；

∑i=1μik=1，∀k；n >∑k=1μik>0，∀i}

cn

矩阵U的第i行给出了描述样本集X中第i个类的模糊子集 μi的隶属函数，i = 1, …, c；U的第k列表示样本点xk在X的c个模糊子集中的隶属度值；μik = μi(xk) 表示xk隶属于X的第i个类（模糊子集）的隶属度值。

设Jm：Mfc×Rc×p→R+，

Jm(U, V) =

∑∑μ

i=1k=1

cn

mik2dik (2.4.1)

这里，U∈Mfc是X的模糊c划分；V = {v1, …, vc}，vi∈Rp是第i个模糊群组 μi的聚类中心，i = 1, …, c；dik是样本点xk与第i类的中心向量vi之间的距离测度，

2

dik= ||xk−vi||A=(xk−vi)TA(xk−vi)，A是p阶对称正定矩阵 (2.4.2)

2

m∈[1, ∞] 是控制最后划分的模糊性的加权指数，增大m将增加函数的模糊性。显然， Jm(U, V) 是一个平方误差聚类准则，算法的目的是寻找合适的U和V，使得Jm(U, V) 达到最小值，因此，聚类问题即转化为求解如下的非线性优化问题

cn

⎧m2

=JUVmin(,)μ∑∑⎪mikdik

(2.4.3) i=1k=1⎨

⎪s.t.U∈M

fc⎩

由于U中各列都是独立的，因此

⎧cnm2⎫n⎧cm2⎫

min{Jm(U,V)}=min⎨∑∑μikdik⎬=∑min⎨∑μikdik⎬ (2.4.4)

⎩i=1k=1⎭k=1⎩i=1⎭

考虑到约束条件

∑

ci=1

μik=1，使用Lagrange乘数法，令

⎛c⎞

F=∑μd+λ⎜∑μik−1⎟ (2.4.5)

i=1⎝i=1⎠

m2

ikikc

则最优化的一阶必要条件为

c

∂F

=∑μik−1=0 (2.4.6a) ∂λi=1

且

∂F∂μ=mμm−12

jtdjt−λ=0 jt

由 (2.4.6b) 得

1

⎡λm−1

μ⎤jt=⎢⎢ ⎣md2⎥

jt⎥⎦

将上式代入 (2.4.6a) 得

11∑c

μc

1

⎛λ⎞m−1

⎡1m−1

m−⎧1

1

⎪c⎫lt==1

∑⎜

ll=1

⎝m⎟⎠⎢⎤⎣d2⎥=⎛⎜λ⎞lt⎦

⎝m⎟⎠

⎨∑⎡⎢1⎤m−1⎪2⎥⎬=1 ⎪⎩l=1⎣dlt⎦⎪⎭

因而

1⎛⎜λ⎞

m−1

⎝m⎟⎠

=

11

∑c

⎡1⎤m−1

l=1⎢⎣d2⎥lt⎦

将上式代入 (2.4.7) 得

μ1jt=

2

∑c

⎡m−1

⎢djt⎤⎢⎣d⎥l=1lt⎦⎥

考虑到dik可能为0，应分两种情况加以讨论。对于 ∀k，定义集合

I = {i | 1 ≤ i ≤ c, d~

kik = 0}，Ik= {1, …, c} − Ik，

则使得Jm(U, V) 达到最小的 μik值为：

(2.4.6b) (2.4.7)

1⎧=μ,Ik=∅2⎪ik

c⎡⎪dik⎤m−1

(2.4.8) ⎢⎥⎨∑j=1⎢⎪⎣djk⎥⎦

~⎪μ=0, ∀i∈IIk≠∅k, ∑i∈Iμik=1,k⎩ik

用类似的方法可以获得Jm(U, V) 达到最小的vi值。令

∂

Jm(U,V)=0 ∂vi

得到

m

∑μikk=1n

∂

[(xk−vi)TA(xk−vi)]=0 ∂vi

于是

∑μ

k=1

n

mik

[−2A(xk−vi)]=0

即

mμ∑ik(xk−vi)=0 k=1n

由此得

vi=

1

∑μ

k=1

n

mk=1

ik

∑μ

n

mikk

x (2.4.9)

若样本集X、聚类数c和权重m的值已知，就能由式 (2.4.8) 和 (2.4.9) 确定最佳模糊分类矩阵和聚类中心。算法的迭代步骤如下：

FCM聚类算法

1° 初始化：给定聚类数c，0 ≤ c ≤ n，设定迭代停止阈值 ε，初始化中心向量矩阵V (0)，设置迭代计数器l = 0；

(l)

2° 更新划分矩阵U (l)：对于 ∀i，k，如果 ∃dik > 0，则有

2

⎧c⎫(l)⎤m−1⎡d⎪⎪=⎨∑⎢ik⎥⎬ (2.4.10a) (l)

⎢djk⎦⎥⎪⎪j=1⎣⎩⎭

−1

(l)

μik

(l)

如果 ∃i，r使得dir = 0，则有

(l)(l)

= 1，且对j ≠ r，μij = 0 (2.4.10b) μir

(l)

3° 更新聚类中心向量矩阵V (l +1)：对于 ∀i，k，如果 ∃dik > 0，则有

vi(l+1)=

∑(μ)

k=1

n

(l+1)m

ik

⋅xk

∑(μ

k=1

n

(l+1)mik

)

(2.4.11)

4° 判断与终止：如果 || V (l) − V (l +1) ||

FCM是一个实现模糊聚类的典型算法，它以最小化类内距的方式来更新隶属度。一旦样本点的隶属度确定下来，按照最大隶属原则，样本点将被指派给具有最高隶属度的类别。 （二）聚类有效性分析

与其它基于目标函数的模糊聚类方法一样，FCM要求在实施算法之前，必须事先指定分类数目。如果我们指定的聚类数不正确，即使使用很好的聚类算法也不会得到最优的聚类结果。例如，图1 给出一个数据集，我们从视觉上很容易得知这个数据集分三类。然而，当我们使用FCM聚类算法对其进行聚类，并把类别数设为4时，我们会得到如图2所示的结果。FCM算法可能得到了类别数为4时的最好的聚类效果，然而这个结果对于这个数据集来说却不是最优的，因为它没有反应出数据集的真实结构。

图1 由三类数据组成的数据集 图2 数据集被FCM聚成4类的结果

然而，在实际应用中通常事先并不知道或难以确切知道样本集的聚类数。因此，根据给定样本集中数据的内在结构来自动判断样本集最应该具有的聚类数（称之为最佳聚类数），是一个非常有意义的课题。这种自动寻求样本集的最佳聚类数问题，我们称之为聚类有效性分析，可以借助有效性函数来实现。聚类的有效性函数，均以聚类算法的相关参数为自变量，目的是评价在选定的参数值下，算法所得的分类结果是否或以多大程度有效地反映了数据本身固有的分类结构。经过深入研究，人们基本取得一致的认识：反映聚类有效性的主要特征是类内的紧致性和类间的分离性，因而人们设计的聚类有效性函数，都始于这一基本出发点。

已经提出的聚类有效性函数有许多，并且人们还在逐步改进。比较有代表性的有如下几个。 (1) 划分系数

如果将给定样本集分成c类，对应的模糊划分矩阵为U = (μij)c×n，则相应的划分系数为

1cn21

Fc=∑∑μij=tr(UUT)

ni=1j=1n

Fc的最大值对应于最佳的聚类数c*。

，反映的是在模糊划分矩事实上，若令UU T = (sij)c×c，则sij是U的第i行与第j行的内积（即相关性）阵为U的模糊聚类中，第i类与第j类两类相互覆盖的程度。

考虑两种特殊的情况：

情形1：分类是清晰的。此时，模糊划分矩阵U为如下形式（以c = 3，n = 7为例）：

⎡1100000⎤

⎥

U=⎢0010100⎢⎥

⎢⎣0001011⎥⎦

相应的UU T为：

⎡200⎤

⎥

UUT=⎢020⎢⎥

⎢⎣003⎥⎦

划分系数为Fc = 1。这说明任意两类之间都不相互覆盖。

情形2：分类是最模糊的。此时，分类矩阵R为如下形式：

L⎡⎤

⎥

MLMU=⎢⎢⎥⎢⎣L⎥⎦c×n

相应的UU T为：

⎡cL⎢

UUT=⎢ML

⎢nL⎣c⎤⎥M⎥ n⎥c⎦c×c

c划分系数为Fc = 1/c。这说明任意两类之间都最大程度地相互覆盖。

可以证明：1/c ≤ Fc ≤ 1。 (2) 平均模糊熵

如果将给定样本集分成c类，对应的模糊划分矩阵为U = (μij)c×n，则相应的平均模糊熵为

1cn

Hc=−∑∑μijln(μij)

ni=1j=1

Hc的最小值对应于最佳的聚类数c*。

平均模糊熵是借用熵函数的形式来度量对应于某一个模糊划分的模糊性。显然，如果分类是清晰的，则模糊划分矩阵退化为一个硬划分矩阵：μij ∈{0, 1}，此时Hc = 0。

上面提到的划分系数和平均模糊熵这两个有效性函数，只用隶属度来衡量聚类的有效性，而没有考虑到数据集的结构，通常它们有如下几个缺陷：

• 随着聚类数的变化而具有单调性 • 对模糊聚类算法中的加权指数（m）敏感 • 和样本集的数据结构缺少直接联系

而下面有效性函数，则同时兼顾了模糊划分的隶属度和样本集的数据结构。

(3) 变差−−分离度

如果将给定样本集分成c类，对应的模糊划分矩阵为U = (μij)c×n，聚类中心矩阵为V = (v1, v2, …, vc)T，vi为第i类的聚类中心向量，则相应的变差−−分离度为

VarN(U,V)VW=

SepN(c,U)

Vw的最小值对应于最佳的聚类数c*，其中

VarN(U,V)=

Var(U,V)

，Varmax=maxVar(U,V)，

c∈{2,3,L,cmax}VarmaxSep(c,U)

，Sepmax=maxSep(c,U)

c∈{2,3,L,cmax}Sepmax

SepN(c,U)=

我们称Var(U, V) 为变差度，其定义如下：

⎡cnμijd2(xj,vi)⎤⎛c+1⎞2

Var(U,V)=⎢∑∑⎟ ×⎜

n(i)c−1⎠⎢⎥⎣i=1j=1⎦⎝

这里，n(i) 是第i类的样本数，d(x, y) 是一个度量，定义为：

d(x, y) = [1 − exp(−β || x − y||2) ]1/2

式中

β=

n

∑||x

j=1

n

j

−||2

1c

，=∑xj

nj=1

变差度所反映的是样本集整体的平均类内分散程度，分类的效果越好，类内的数据越紧密，变差度就越小。

称Sep(c, U) 为分离度，其定义如下：

Sep(c,U)=1−max{ S(Fi,Fj)}

i≠j

式中

S(Fi,Fj)=max{ min(μik,μjk)}

xk∈X

分离度通过模糊集之间的不相似性来描述各个类之间的隔离程度，分类效果越好，分离度越大。

注：最佳聚类数c* 的求取，通常是对c = 2, 3, …, cmax逐次实施模糊聚类算法，然后根据相应的模糊划分矩阵U和聚类中心矩阵V计算有效性函数值，最后比较得出最佳的聚类数c*。在实际应用中，需要处理的数据集其样本数可能非常大，但真实的分类数并不很大。因而通常取cmax = n1/2，或者根据实际情况将cmax限定的更小，以减少算法运行的费用。

例题 设给定的数据集如表1所示，样本点分布的散点图如图1所示。

图1 数据的散点图

分别使用划分系数、平均模糊熵和变差−−分离度对给定数据进行15次有效性检验，得到的检验结果如表2－4。从有效性函数的平均检验值可以看出，给定数据集的最佳聚类数为2，即从数据的分布结构来看，分成两类是最合理的。

如果将数据集分成两类，根据FCM聚类算法，得到的聚类结果如表5。

表5 分成两类的聚类结果

样本序号 所属类标号 样本序号 所属类标号 样本序号 所属类标号

表1：给定的数据集

样本序号

指标1

指标2

表2 划分系数

运行次数

c = 2

c = 3

c = 4

c = 5

平均值：

表3 平均熵

运行次数

c = 2

c = 3

c = 4

c = 5

平均值：

表4 变差−−分离度

运行次数

c = 2

c = 3

c = 4

c = 5

平均值：