模糊ISODATA分类方法详解

以上介绍的方法，都是基于模糊等价关系的聚类方法，这种聚类方法的优点是聚类灵活，可以根据不同的阈值来聚类，但在聚类前必须作模糊相似矩阵；在聚类过程中，没有充分利用人们已有的分类经验；分类后不知道每一类别的聚类中心的信息，为此人们希望能有一种可以充分利用人们已有的分类经验，且能知道聚类中心信息的软划分。模糊等价关系聚类法，最后是按λ截关系组成的经典矩阵来划分的，这是一种硬划分。我们希望知道各类样本隶属于某类的隶属度，这样就知道有多大的把握将这些样本划分在某类中。以下介绍的模糊ISODATA（Interactive Self-Organizing Data）法就具有这样的优点。

1.问题的数学模型

1）已知条件

设已知n个待分类的样本，我们可以将它们视为论域X中的元素：

每个样本（元素）Xk有m个特征：

n个样本（元素）的特征组成一个特征矩阵

式中：xkj为第k个样本的第j个特征。

2）求解

（1）设分成s类，求各类的聚类中心，即求

①s个聚类中心

②各聚类中心的特征

③各聚类中心组成的特征矩阵

式中：vij为第i聚类中心的第j特征。

（2）设分成s类，求各样本（n个）隶属于各类（s类）的隶属度。

①s类隶属度

②各样本属于第i类的隶属度

(www.xing528.com)

③n个样本隶属于s类的隶属度矩阵

2.解法

用迭代法来求解此问题。

设某聚类中心是Vi，待分类的样本是Xk，此样本越接近聚类中心Vi，则此样本隶属于第i类的隶属度越大；若Vi是其他各类的聚类中心，此样本越远离Vj，则此样本越不应被分在其他各类中。式（7.6.53）说明了Xk与第i类的相对隶属关系（相对距离关系）：

式中：r是正整数，r=1，2，…，n，通常取r=2。

易知，d（Xk，Vi）越小，Xk越应划分在第i类，也就是说，样本Xk，隶属于第i类的隶属度应越大。综合对各个Vj的关系，于是便有

式中：Xk=（xk1，xk2，…，xkm），Vi=｛vi1，vi2，…，vim｝，Vj=｛vj1，vj2，…，vjm｝。i=j=1，2，…，s；r=1，2，…，n，通常r=2。

若已知第k样本的第j特征xkj，又知第k样本隶属于第i类的隶属度uik，那么下列乘积

就表示了第k个样本特征值xkj在第i类的聚类中心相应的特征值中所占的比例，综合各类样本，就可以求得第i类聚类中心的第j个特征值为

式中：r=1，2，…，n，通常r=2；i=1，2，…，s；j=1，2，…，m。

式（7.6.54）与式（7.6.56）是一组迭代公式，vij是第i个聚类中心的第j特征，uik是第k个样本隶属于第i类的隶属度是距离。给定ε（任意小数），当uik多次迭代后与前一次uik的差值小于ε时，就认为迭代可以终止，此时的uik与vij就是求得的结果。全部迭代过程如图7.6.16所示。

图7.6.16　模糊ISODATA法的流程图

在解具体问题时，初始划分矩阵要按照经验来给定。uik的取值越接近各样本在不同类别中的隶属度，迭代收敛越快，分类也越精确，聚类中心值也越接近实际情况。事实表明：若中各元素取相同的值，则迭代一定不收敛，所以初始划分矩阵不能任意选取，否则会出现振荡和发散的情况。此外，模糊划分矩阵Us×n（包括初始、中间及最终的矩阵）还必须满足以下条件：

（1）uik∈［0，1］（归一性）；

（2）=1，∀k（划分性）；

（3）＞0，∀i（非空性）。

关于如何选取初始值的问题，至今尚未见有人作过系统的研究，作者曾在1984年的中美双边模糊数学学术讨论会上就此问题与模糊ISODATA法的创始人J.C.Bezdek博士做过讨论，他也认为这是一个未解决的理论难题。作者此后在1987年的《模糊系统与数学》创刊号上发表过一文，特别对模糊等价关系法及模糊ISODATA法在理论上存在的问题作了综述。当时作者在文中指出：“研究模糊ISODATA法迭代收敛问题的目的，就是要为迭代寻求收敛的准则，收敛与初始值及范数（距离）的关系如何？怎样用数学形式来描述收敛的指标？收敛性如何受到类别C及指数r的影响？改善收敛性、提高收敛速度应采取什么措施？这些都是为达到目的所必须搞清楚的理论问题。”所幸，经过多年的研究，我国学者已就这些问题获得不少进展。1998年，何清在《模糊系统与数学》第12卷第2期上对十多年来我国及国际上模糊聚类分析的理论及应用研究的进展做了总结，指出：“朱剑英教授所提出的寻求失真最小的最优模糊等价矩阵问题在理论上已得到系统、圆满的解决”。但“朱剑英教授关于ISODATA方法提出的几个问题尚未获得系统圆满的回答。”