第3卷第1期 智能系统学报 Vol.3 Ne 1 2008年2月 CAAI Transactions on Intelligent Systems Fcb.2008 鲁棒的模糊方向相似性聚类算法 朱林，王士同，修宇 (江南大学信息工程学院，江苏无锡214122) 摘要：鉴于文本数据具有方向性数据的特征，可利用方向数据的知识完成对文本数据聚类，提出了模糊方向相似 性聚类算法DSC继而从竞争学习角度，通过引入隶属度约束函数，并根据拉格朗日优化理论推导出鲁棒的模糊方 向相似性聚类算法RFDSC.实验结果表明RFDSC算法能够快速有效地对文本数据集进行聚类」 关键词：聚类算法，方向相似性，鲁棒性：竞争学习 中图分类号：TP391.41文献标识码：A文章编号：16734785(2008)01-004308 A robust clustering algorithm with fuzzy directional similarity ZHU Lin,WANG Shi-tong,XIU Yu (School of Information Engineering Jiangnan University,Wuxi 214122,China) Abstract:One of the important characteristics of text clustering in datasets is that each cluster center in the dataset has a direction that is different from that of all other cluster centers.This directional information should be incorporated in clustering analysis.In this paper,a new robust fuzzy directional similarity clus tering algorithm(RFDSC)is proposed by introducing membership constraints.The new objective function was constructed.Finally,the robustness and convergence of the proposed algorithm were analyzed from the viewpoint of competitive learning.Experimental tests of text clustering in datasets using RFDSC dem- onstrate its effectiveness. Key words:clustering algorithm;directional similarity;robustness;competitive learning 聚类分析是无监督模式识别中的一种重要方方向数据的知识完成对这类数据的有效聚类.文献 法，己广泛应用于数据挖掘、图像处理、计算机视觉、 [12]分别提出了2种不同的针对方向性数据的聚 生物信息和文本分析.聚类算法就是将一组分布未 类算法SPKmeans!)和movMFI2),但2种算法由于 知的数据进行分类，其目的是寻找隐藏在数据中的 对初始化较敏感，聚类性能有待提高.文献[3]提出 结构，并按照某种相似程度的度量，尽可能地使具有 了方向相似性聚类算法，其根据方向分布理论提出 相同性质的数据归于同一类.针对不同的应用和不 了数据的相似性度量，通过集成方向相似性聚类方 同的理论已提出多种各具特色的聚类算法，如划分 法和凝聚层次聚类方法解决了聚类中初始化敏感等 方法(K-means、Clarans、Frem)、层次方法(Chame- 问题.但由于该算法将每个样本点均作为不动点，通 leon、Brich)、基于网格方法(WaveCluster、Stng、 过迭代求其最优解，在处理高维大量数据如文本数 Clique)、基于密度方法(Dbscan、Optics)等 据时，算法速度太慢，不能得到很好的应用 近年来大量研究表明，高维数据诸如文本数据 文中所做工作的意义在于首先提出模糊方向相 及基因表达数据具有方向性数据的特征，可以利用 似性聚类算法(fuzzy directional similarity cluste- ring,FDSC),在此基础之上，从竞争学习角度，通过 收稿日期：2007-0514. 对目标函数中引入隶属度约束函数，推导出鲁棒的 基金项目：因家“863”"资助项目(2006AA10Z313):国家自然科学基金 资助项目(60773206：60704047)：国防应用基础研究基金 模糊方向相似性聚类算法(robust fuzzy directional 资助项目(A1420461266);教育部科学研究重点基金资助 similarity clustering,RFDSC),使算法具有更好的 项目(105087). 通讯作者：王士同，Email:wxwangst@yahoo.com.cn 收敛性和鲁棒性 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3 卷第 1 期 智 能 系 统 学 报 Vol. 3 №. 1 2008 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2008 鲁棒的模糊方向相似性聚类算法 朱 林 ,王士同 ,修 宇 (江南大学 信息工程学院 ,江苏 无锡 214122) 摘 要 :鉴于文本数据具有方向性数据的特征 ,可利用方向数据的知识完成对文本数据聚类 ,提出了模糊方向相似 性聚类算法 FDSC ,继而从竞争学习角度 ,通过引入隶属度约束函数 ,并根据拉格朗日优化理论推导出鲁棒的模糊方 向相似性聚类算法 RFDSC. 实验结果表明 RFDSC 算法能够快速有效地对文本数据集进行聚类. 关键词 :聚类算法 ;方向相似性 ;鲁棒性 ;竞争学习 中图分类号 : TP391141 文献标识码 :A 文章编号 :167324785 (2008) 0120043208 A robust clustering algorithm with fuzzy directional similarity ZHU Lin , WAN G Shi2tong , XIU Yu (School of Information Engineering ,Jiangnan University , Wuxi 214122 , China) Abstract :One of the important characteristics of text clustering in datasets is t hat each cluster center in t he dataset has a direction t hat is different from that of all ot her cluster centers. This directional information should be incorporated in clustering analysis. In t his paper , a new robust f uzzy directional similarity clus2 tering algorit hm (RFDSC) is proposed by introducing membership constraints. The new objective f unction was constructed. Finally , t he robust ness and convergence of t he proposed algorit hm were analyzed from t he viewpoint of competitive learning. Experimental tests of text clustering in datasets using RFDSC dem2 onstrate its effectiveness. Keywords :clustering algorit hm ; directional similarity ; robust ness ; competitive learning 收稿日期 :2007205214. 基金项目 :国家“863”资助项目(2006AA10Z313) ;国家自然科学基金 资助项目(60773206 ;60704047) ;国防应用基础研究基金 资助项目(A1420461266) ;教育部科学研究重点基金资助 项目(105087) . 通讯作者 :王士同. E2mail :wxwangst @yahoo. com. cn. 聚类分析是无监督模式识别中的一种重要方 法 ,已广泛应用于数据挖掘、图像处理、计算机视觉、 生物信息和文本分析. 聚类算法就是将一组分布未 知的数据进行分类 ,其目的是寻找隐藏在数据中的 结构 ,并按照某种相似程度的度量 ,尽可能地使具有 相同性质的数据归于同一类. 针对不同的应用和不 同的理论已提出多种各具特色的聚类算法 ,如划分 方法( K2means、Clarans、Frem) 、层次方法 (Chame2 leon、Brich) 、基于网格方法 ( WaveCluster、Stng、 Clique) 、基于密度方法(Dbscan、Optics) 等. 近年来大量研究表明 ,高维数据诸如文本数据 及基因表达数据具有方向性数据的特征 ,可以利用 方向数据的知识完成对这类数据的有效聚类. 文献 [122 ]分别提出了 2 种不同的针对方向性数据的聚 类算法 SP Kmeans [1 ]和 movMF [2 ] ,但 2 种算法由于 对初始化较敏感 ,聚类性能有待提高. 文献[ 3 ]提出 了方向相似性聚类算法 ,其根据方向分布理论提出 了数据的相似性度量 ,通过集成方向相似性聚类方 法和凝聚层次聚类方法解决了聚类中初始化敏感等 问题. 但由于该算法将每个样本点均作为不动点 ,通 过迭代求其最优解 ,在处理高维大量数据如文本数 据时 ,算法速度太慢 ,不能得到很好的应用. 文中所做工作的意义在于首先提出模糊方向相 似性聚类算法 (f uzzy directional similarity cluste2 ring ,FDSC) ,在此基础之上 ,从竞争学习角度 ,通过 对目标函数中引入隶属度约束函数 ,推导出鲁棒的 模糊方向相似性聚类算法 (robust f uzzy directional similarity clustering ,RFDSC) ,使算法具有更好的 收敛性和鲁棒性