基于模糊Fisher 准则的半模糊聚类算法

第 30 卷第 9 期 电 子 与 信 息 学 报 Vol.30No.9 2008 年 9 月 Journal of Electronics & Information Technology Sept..2008 基于模糊 Fisher准则的半模糊聚类算法 曹苏群①② 王士同① 陈晓峰① 谢振平① 邓赵红① ①(江南大学信息学院 无锡 214122) ②(淮阴工学院机械系 淮安 223001) 摘 要：该文针对线性可分数据提出一种鲁棒的基于模糊 Fisher 准则的半模糊聚类算法 FFC-SFCA。FFC-SFCA 通过模糊化散布矩阵，将模糊理论引入Fisher判别方法，通过对模糊Fisher准则函数迭代优化实现聚类。FFC-SFCA 的优势在于具有很好的鲁棒性且可以获得可分性好的聚类结果，同时，可以求得最优鉴别矢量和分类阈值。实验证 实了 FFC-SFCA 的有效性以及对两个常规聚类算法的优越性。 关键词：Fisher 准则；半模糊聚类；最优鉴别矢量 中图分类号：TP181 文献标识码：A 文章编号：1009-5896(2008)09-2162-04 Fuzzy Fisher Criterion Based Semi-Fuzzy Clustering Algorithm Cao Su-qun①② Wang Shi-tong① Chen Xiao-feng① Xie Zhen-ping① Deng Zhao-Hong① ①(School of Information, Jiangnan University, Wuxi 214122, China) ②(Department of Mechanical Engineering, Huaiyin Institute of Technology, Huaian 223001, China) Abstract: The robust Fuzzy Fisher Criterion based Semi-Fuzzy Clustering Algorithm (FFC-SFCA) for linearly separable data is presented in this paper. FFC-SFCA incorporates Fisher discrimination method with fuzzy theory using fuzzy scatter matrix. By iteratively optimizing the fuzzy Fisher criterion function, the final clustering results are obtained. FFC-SFCA exhibits its robustness and capability to obtain well separable clustering results. In addition, optimal discriminant vector and threshold of classifier can also be figured out. The experimental results for artificial and real datasets demonstrate its validity and distinctive superiority over the two conventional clustering algorithms. Key words: Fisher criterion; Semi-fuzzy clustering; Optimal discriminant vector 1 引言 有监督情况下，常常通过 Fisher 线性判别(FLD) [1]进行 投影方向上投影点类内和类间散布矩阵的优化运算，使得投 影点类间尽量分开同时类内尽量密集。2002 年，Clausi 提出 了 KIF(K-means Iterative Fisher)方法[2]，将 Fisher 准则巧 妙地应用于无监督聚类，在纹理分割等实验中取得了可分性 好的聚类结果。该算法通过 K-means 初始化与迭代 Fisher 线性判别方法组合实现，本质上属于硬划分，虽然执行效率 较高，但抗噪性能较差。本文将模糊理论引入 Fisher 判别方 法，给出模糊 Fisher 准则函数定义，进而提出了一种半模糊 聚类的新算法 FFC-SFCA(Fuzzy Fisher Criterion based Semi-Fuzzy Clustering Algorithm)，与 KIF 算法相比， FFC-SFCA 具有 3 个优点：(1)明确给定了目标函数定义， 具有严格的 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 理论基础；(2)属于半模糊聚类算法，综合了 2007-02-05 收到，2007-09-28 改回 2004 年教育部优秀人才支持计划(NCET-04-0496)，模式识别国家重 点实验室开放课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，南京大学软件新技术国家重点实验室开放课题， 教育部重点科学研究项目(105087)和国防应用基础研究基金项目 (A1420061266)资助课题 传统硬聚类收敛速度快和模糊聚类的对初始化不敏感和抗 噪性能强的优点；(3)该方法在对数据集实现聚类的同时，不 仅可以求得最优鉴别矢量，用于特征提取和降维，而且可以 求得分界线进而构造出分类器。 2 模糊 Fisher准则 参照 Kuo-lung Wu 等在文献[3]中模糊散布矩阵定义， 将模糊理论引入 Fisher 判别方法。 设一集合包含N 个d 维样本 1 2 N, , ,x x x" ，模式类别有 c 个，在该样本空间，定义各类样本均值向量记为 im ，模 糊类内散布矩阵记为 fwS ， T 1 1 ( )( ) c N m fw ij j i j i i j u = = = − −∑∑S x m x m (1) 模糊类间散布矩阵记为 fbS ， T 1 1 ( )( ) c N m fb ij i i i j u = = = − −∑∑S m x m x (2) 设 T=y xω ，在该投影空间，定义各类样本均值向量记 为 j im ，有 j Ti i=m mω (3) 第 9 期 曹苏群等：基于模糊 Fisher 准则的半模糊聚类算法 2163 定义模糊类内散布矩阵记为 i fwS ， i 1 1 c N m fw ij i j u = = =∑∑S j j T T( )( )i ij j fw⋅ − − =y m y m Sω ω 。模糊类间散布矩阵记为 fbS� ， i j j T T 1 1 ( )( ) c N m fb i iij fb i j u = = = − − =∑∑S m y m y Sω ω。 定义模糊 Fisher 准则(Fuzzy Fisher Criterion)函数： i i T FFC T fb fb fw fw J = = SS S S ω ω ω ω (4) 对于线性可分数据集，将 FFCJ 作为聚类目标函数，当 FFCJ 取得极大值时，表明样本点在ω方向上投影类间距离最 大且类内距离最小。使用 Lagrange 乘子法求解 FFCJ 取得极 大值时，ω， im 和 iju 的取值。 定义 Lagrange 函数为 T T 1 1 1 N c fb fw j ij j i L uλ λ = = ⎛ ⎞⎟⎜ ⎟= − + −⎜ ⎟⎜ ⎟⎜⎝ ⎠∑ ∑S Sω ω ω ω (5) 式中λ和 ( 1,2, , )j j nλ = " 为 Lagrange 乘子。 将L 分别对ω， im 及 iju 求偏导数，并令偏导数为零， 即 / 0L∂ ∂ =ω (6) / 0iL∂ ∂ =m (7) / 0ijL u∂ ∂ = (8) 对于式(6)，由于 fbS 和 fwS 均为对称半正定矩阵，当 fwS 非奇异时，可求解得： 1 fw fb λ− =S S ω ω (9) 解式(9)为求一般矩阵 1fw fb−S S 的本征值问题，λ即为该矩阵的 特征值，而ω为对应的特征向量。 对于式(7)，可以解得 1 1 ( / ) (1 1/ ) N m ij j j i N m ij j u u λ λ = = − = − ∑ ∑ x x m (10) 对于式(8)，可以解得 1 1 T T T T ( ( )( ) ( )( ) ) ij m j j i j i i i u m λ λ − = ⎛ ⎞⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟− − − − − ⎟⎜⎝ ⎠x m x m m x m xω ω ω ω (11) 又 1 1, =1,2, , c kj k u j N = =∑ " ，所以有 { } 1 T T T 1 1/( 1)T 1 [ ( ( )( ) ( ) ( ) )] c kj k c j j k j k k k m k u mλ λ = = − = = − − − − ⋅ − ∑ ∑ x m x m m x m x ω ω ω ω (12) 式(11)和式(12)两式相除，得 ( ) ( ) T T T T 1 T T T1 1 1 T 1 ( )( ) (1/ ) ( )( ) ( )( ) (1/ ) ( )( ) (13) ij j i j i i i c m j k j k k m k k u λ λ− − = − − = − − − − − ⎡⎢⋅ − − −⎢⎣ ⎤⎥⋅ − − ⎥⎦ ∑ x m x m m x m x x m x m m x m x ω ω ω ω ω ω ω ω 在模糊聚类中，通常限定 [0,1]iju ∈ ，因此，对上式给出 如下限定条件，若 T T T T( )( ) (1/ ) ( )( )j i j i i iλ− − ≤ − −x m x m m x m xω ω ω ω (14) 则 1iju = 且对所有 i' i≠ ，有 ' 0i ju = 。也就是说，当该条 件满足时，样本点 jx 将完全隶属于第 i 类，即在此范围内采 用硬划分。此条件的几何意义为：将样本点、聚类中心以及 所有样本中心向ω方向投影，若样本投影点与聚类中心投影 点欧氏距离小于或等于聚类中心投影点与所有样本中心投 影点间欧氏距离的1/ λ ，则对该点采用硬划分。可以使用 图 1，对此做出直观解释。 图 1 FFC-SFCA 硬划分区示意图 图 1 中“ ”□ 为第 1 类样本点，“ ”○ 为第 2 类样本点，样 本点中带“.”标记的为满足式(14)而采用硬划分的点，将这些 点按虚线方向向最优鉴别矢量方向线投影，根据图示，硬划 分区域为垂直最优鉴别矢量方向且对称分布于聚类中心的 两带状区域。 3 FFC-SFCA算法 根据求解结果，FFC-SFCA 算法描述如下： 步骤 1 使用 -meansk 算法初始化隶属矩阵 U 以及聚 类中心 im ； 步骤 2 使用式(1)、式(2)式分别计算 ,fw fbS S ，根据式 (9)求得矩阵 1fw fb− ⋅S S 的最大特征值 λ ，并取 ω 为矩阵 1 fw fb − ⋅S S 属于λ的模为 1 的特征向量； 步骤 3 使用式(4)计算模糊 Fisher 准则函数 FFCJ ，若 它相对上次准则函数数值的改变量小于某个阈值或者迭代 次数超过设定次数，则算法停止； 步骤 4 使用式(13)，式(10)分别计算新的隶属矩阵 U 以及聚类中心 im ，返回步骤 2。 2164 电 子 与 信 息 学 报 第 30 卷 4 实验结果及其分析 4.1 实验 1 人工数据集 首先，由两个相邻的椭圆中随机生成若干数据点构成两 类二维人工数据集，如图 2 所示。使用 FCM，KIF，FFC- SFCA 3 种算法对该人工数据集进行聚类实验，各算法聚类 效果请见图 3-图 5。 图 2 两类二维人工数据集 图 3 FCM 聚类效果 图 4 KIF 聚类效果 图 5 FFC-SFCA 聚类效果 (加点样本点为硬划分点) 从图中可以看出，KIF 与 FFC-SFCA 聚类结果相近， 均好于 FCM。FFC-SFCA 可计算出最优鉴别矢量以及分界 阈值，为降维和设计线性分类器提供了很好的依据，图 5 中 实线即为最优鉴别矢量方向线，点划线即为分界线。 为进一步比较 KIF 和 FFC-SFCA，通过数据加噪实验， 测试 KIF 和 FFC-SFCA 算法的抗噪性能。在图 2 中人工数 据集加入一定数量[0,1]间的随机噪声点，分别使用 KIF 和 FFC-SFCA 对其进行聚类，并用著名的约当指数(Rand Index) [4]评价其聚类结果。定义 1 2,P P 分别为对原数据集 D 和加噪数据集聚类划分结果，通过公式 1 2Rand( , )P P = ( 1)/2 a b n n + × − 来计算这两种划分的一致性。其中a 表示 D 中 任意两个样本 ,i jd d 在 1 2,P P 中同属于一类的个数；b 表示 ,i jd d 都不属于同一类的个数；n 表示数据集 D 的样本个数。 Rand Index 的范围为[0,1]，只有在 1 2,P P 完全一致的情况下， Rand Index 值为 1。Rand Index 统计的值越小，两种划分 差距越大，也说明该聚类算法受噪声点影响大。为了保证比 较的准确性和公平性， 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 两种算法分别进行 100 次实验后 得到的 Rand Index 的均值，绘制图 6 曲线。 图 6 两种算法针对噪声点的 Rand Index 变化曲线 从图 6 中可以看出，KIF 算法聚类结果受噪声点影响很 大，随着噪声点数目的增加，Rand Index 越来越小。FFC- SFCA 算法受噪声点影响则较小，而且在噪声点占样本总数 20％以内时，Rand Index 稳定 90％以上。因此，属模糊聚 类的 FFC-SFCA 算法与 KIF 硬聚类算法相比，有显著的抗 噪性能。 4.2 实验 2 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 数据集 Iris 用 UCI[5]中的 Iris 数据集来检验该聚类方法的有效 性[6]。Iris 数据集包含 3 类共 150 条样本记录，每条记录有 4 个属性。分别用 FCM，KIF 和 FFC-SFCA 进行聚类，将聚 类结果与原数据集样本标记对比，统计各算法错分样本数， 进而计算其准确率，结果如表 1 所示。 表 1 3种算法对 Iris数据集聚类准确率比较 算法 错分样本数 分类准确率(%) FCM 16 89.3 KIF 5 96.7 FFC-SFCA 2 98.7 从表 1 可以看出，对 Iris 数据集进行聚类分析，FFC- SFCA 在分类准确率上均优于 FCM 和 KIF 算法。 5 结束语 本文提出了一种半模糊聚类算法 FFC-SFCA，该方法通 过模糊化散布矩阵，将模糊理论引入 Fisher 判别方法，并定 义模糊 Fisher 准则函数，通过对该函数进行迭代优化运算进 而实现聚类。实验表明，该方法对线性可分数据集，具有良 好的聚类效果且抗噪性能显著，并且在实现聚类的同时，可 以求得最优鉴别矢量用于特征提取和降维，也可以求得分界 线进而构造分类器。由于 FFC-SFCA 需要求解矩阵特征值 和特征向量并且样本点隶属度等需通过迭代公式进行计算， 因而在高维大数据量情况下，需要进一步研究算法效率提高 的途径。 参 考 文 献 [1] 边肇祺, 张学工. 模式识别. 第二版. 北京: 清华大学出版社, 2000: 87-90 [2] Clausi D A. K-means iterative Fisher(KIF) unsupervised 第 9 期 曹苏群等：基于模糊 Fisher 准则的半模糊聚类算法 2165 clustering algorithm applied to image texture segmentation. Pattern Recognition, 2002, 35(9): 1959-1972. [3] Wu Kuo-Lung, Yu Jian, and Yang Miin-Shen. A novel fuzzy clustering algorithm based on a fuzzy scatter matrix with optimality tests. Pattern Recognition Letters, 2005, 26(4): 639-652. [4] Rand W. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 1971, 66(336): 846-850. [5] Blake C L and Merz C J. UCI repository of machine learning databases, Irvine. CA: University of California, Department of Information and Computer Science, http://www.ics.uci. edu/~mlearn/MLRepository.html, 1998, 7. [6] 修宇, 王士同, 吴锡生等. 方向相似性聚类方法 DSCM. 计算 机研究与发展, 2006, 43(8): 1425-1431. Xiu Yu, Wang Shi-tong, and Wu Xi-sheng, et al.. The directional similarity-based clustering method DSCM. Journal of Computer Research and Development, 2006, 43(8): 1425-1431. 曹苏群： 男，1976 年生，讲师，博士生，从事模式识别、机器学 习等研究. 王士同： 男，1964 年生，教授，博士生导师，从事人工智能、机 器学习等研究. 陈晓峰： 男，1977 年生，博士生，从事人工智能、模式识别的研 究.