一类带最小约束的模糊聚类问题

尚松蒲 赵中建

摘要: 考虑到模糊聚类中引入传递性可能使问题失真, 提出了一类带最小约束的模糊聚类问题. 给出了解决这类问题的两类方法: 直接聚类法与基于无约束聚类的方法. 并将这些方法与一般模糊聚类的方法进行了比较.

关键词: 模糊聚类;约束聚类;失真;算法

1 引言

模糊聚类分析是根据模糊相似矩阵对各个对象进行分类[1]. 模糊聚类分析是模糊数学中应用最多、最活跃的一个分支,在科学研究、工程技术、经济管理方面都有着广泛的应用. 模糊聚类分析的常用方法包括传递闭包法、直接聚类法以及作为直接聚类法图形化的最大树法. 这些方法都是等价的,结果也完全一样,在聚类时都假设了传递性.由模糊相似矩阵求传递闭包得到模糊等价矩阵,这种对传递性的引入使两个相似度很小的元素可以通过其它的元素而归为一类,而这在有些实际问题中是不可接受的[2,3]. 因此我们提出了一类带最小约束的模糊聚类问题,它比一般的模糊聚类问题多了一个约束条件: 相似度小于某个阈值的两个元素不能在同一类中。

在接下来的第二部分我们给出问题的数学描述,第三部分给出直接聚类的解法,第四部分给出基于无约束的解法,最后第五部分做出总结,并比较以上的方法与无约束模糊聚类方法的联系与区别。

2 问题描述

假定有要对集合{x1,x2,…,xn}里的n个元素(对象)进行聚类, 给定的条件包括:

(1)模糊相似矩阵R, 矩阵中的元素rij表示元素i与元素j的相似系数, R满足自反性(rii=1)与对称性(rij=rji);

2.1约束阈值?姿0:带最小约束条件的模糊聚类问题即是在聚类阈值?姿水平上,限制同一类的元素间的相似系数大于等于约束阈值?姿0的模糊聚类问题. 下面给出这个问题的一些解法.

2.2直接聚类法:直接聚类法最开始将n个对象各自作为一类,然后在满足约束条件的情形下,逐步将某些类合并,直到不能合并为止.算法如下:

(1)初始有n类: {x1},{x2},…,{xn},令

,

(2)若S=?覫,算法终止;否则转(3).

(3)取S中最大元素,令,若i0所在类中的元素与j0所在类中的元素的相似系数的最小值大于等于?姿0,则将i0所在类与j0所在类合并为一类,转(2);否则直接转(2).该算法与无约束模糊聚类中的直接聚类法类似,只是考虑到约束条件而更加复杂。算法的结果是满足约束条件的聚类.

3 基于无约束的聚类

按照不考虑约束条件给出在?姿水平上的模糊聚类,然后在每一类中进行必要的再分类以满足约束条件。

方法一: 我们以n个对象为顶点构造一个图,顶点i与顶点j连边当且仅当对象i与对象j满足rij姿0,我们称这个图为约束图。显然,对象i与对象j不能归为一类当且仅当顶点i与顶点j之间有连边。将这些点k分类, 等价于将约束图构造为一个k-部图. 确定最小的k是NP-困难的[4]。我们可以先构造约束图的点覆盖, 假设C={i1,i2,…,im}是约束图的点覆盖,D是约束图中不包含C中的点的非零度的点的集合,以点覆盖C中的点与D为基础,构造m+1类,将其余点按照相似系数的大小,分别归入这m+1类。得到一个满足约束条件的分类。

(1)将某类中所有相似系数小于?姿0的集合记为T.

(2)若T=?覫,算法终止;否则转(3).

(3)取T中的最小元素,则将i0与j0分属于不同的两类,其余元素按照相似系数大小归为其中某一类,对这两个类,分别转(1)。

方法一是应用图论中有限覆盖理论来构造满足约束条件的分类,方法二采用逐步分解法得到满足约束条件的分类。

4 总结

以上提出了一类带最小约束的模糊聚类问题, 这个问题对解决无约束模糊聚类中因传递性而产生的失真问题是一个有益的尝试. 并给出了两类解法:直接聚类法法与基于无约束聚类的聚类,后者分为点覆盖法与逐步聚类法. 与无约束的模糊聚类问题相比, 这个问题更复杂, 解法的难度也更大, 聚类的结果也更具有不确定性. 对上述问题可以提出更具体的聚类目标而得到更数学化的模型。

参考文献

[1] 谢季坚, 刘承平. 模糊数学方法及其应用[M]. 武汉: 华中科技大学出版社,2000.

[2] 鲍正益. 模糊聚类算法及其有效性研究 [D]. 厦门: 厦门大学, 2006.

[3] 于剑,程乾生.模糊聚类方法中的最佳聚类数的搜索范围[J].中国科学(E辑),2002,32(2): 274-280.

[4] W.T.Tutte. Graph theory [M]. 北京: 机械工业出版社, 2004.

作者简介:尚松蒲(1974 -),男,河南叶县人,讲师,博士,主要从事组合优化问题研究。