第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) ,使算法具有更好的 收敛性和鲁棒性
·44 智能系统学报 第3卷 2)中心向量w迭代公式为 1方向相似性聚类算法(DSCM) 方向相似性聚类算法](directional similarity xfue wi= (4) based clustering algorithm,DSCM)定义一个新的 I∑xue,I 方向相似度量函数S(x,w)来度量方向数据向量 x和聚类中心向量w,的相似性：S(X,w)=e, 对于式(2)的极值，可以通过利用拉格朗日优化 理论推导出模糊方向相似性聚类算法(FDSC)关于 i=1,2,c代表类别下标，j=1,2,…n代表样本 隶属度的迭代公式(3)和中心向量w的迭代公 下标，k为尺度参数.S(x,w)值越大说明数据向量 式4)求解.与传统的FCM聚类算法有所不同，按 x与中心向量w,的相似度越高.DSCM算法定义 照FDSC算法定义，数据向量xy与中心向量w,的 聚类目标函数为 相似度越高其隶属度应越大，故式3)中·1/(m- 王sw=,P (1) 1)>0,即权重指数m<1,同时为了保证算法有较好 DSCM算法通过拉格朗日优化理论构造拉格 的收敛性，权重指数0<m<1.FDSC聚类思想可以 朗日优化目标函数，推导出中心向量w的迭代公 理解成通过中心向量和隶属度的迭代公式求解最优 式，对所有样本经过有限次迭代过程自组织的找到 聚类中心w,使得目标代价函数Jsc最大，即样本 所有不动点，进一步采用凝聚层次聚类算法(ag 间相似度总和最大 glomerative hierarchical clustering,AHC)分析不动 2.2基于竞争学习理论的隶属度目标函数的构造 点的层次数，并通过层次聚类图进一步确定最佳聚 竞争学习的学习规则分为WTA(winner-take- 类数以及类与类之间的关系 all)与WTM(winner-take-more)2种，分别称为 DSCM算法可以避免初始化敏感的问题，能够 “硬”竞争学习(hard competitive learning)与“软”竞 对方向性数据进行自组织，并利用AHC算法侦测 争学习(soft competitive learning)s),WTA规则 出最优的聚类数.但对于高维大量数据特别是文本 存在一个重要问题：对于不同初始值的节点，学习 数据，由于样本数很大，对所有样本无法通过 过程中可能存在死节点(dead nodes)或利用不充分 DSCM算法中的有限次迭代过程，自组织的找到所 (under-utilization)的现象.为此，研究人员提出了 有不动点.因此DSCM算法的应用受到了很大的局 WTM规则，通过引入模糊隶属度等方法，削弱了学 限性。 习对节点初始值的依赖，但同时也造成数据的获胜 节点不确定，使得部分节点可能偏离其实际的类数 2鲁棒的模糊方向相似性聚类算法 据.文献[6]提出了惩罚对手的竞争学习(RPCL), 2.1 模糊方向相似性聚类算法(FDSC) 对于数据集中的每个样本，不仅其获胜节点以一定 在方向相似性聚类算法的基础上，引入模糊隶 的学习速率向该数据集“靠近”，而且其竞争对手以 属度关系，建立如下模糊化的目标函数： 更小的学习速率（惩罚速率）被“推离”该数据集，从 JDc=∑∑Ge 而减小了对学习过程的干扰 (2 基于惩罚对手的竞争学习(RPCL)的思想，在 目标函数满足条件： 24=10< 模糊方向相似性聚类算法DSC的基础之上，文中 <n, 进一步提出鲁棒性的模糊方向相似性聚类算法 ∈0,1]，式中：m为权重指数，i=1,2,c代表 RFDSC.对于一个单独的样本点x,通过引入隶属 类别下标，j=1,2,,n代表样本下标，k为尺度 参数 度约束函数：f(n,b,)= 定理1在∑=1,0< <n,∈ 构造新的目标函数： 0,11,ww=1条件下，使FDSC算法的目标函数 ,王，Ge)取极值时： (5) 1)隶属度迭代公式为 下文将对式(5)中参数a(1≤≤的选择做说明. =(e)v”/∑e)vm.”. 3) 权重指数m∈0，)，目标函数满足∑4=1,0< 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1 方向相似性聚类算法(DSCM) 方向相似性聚类算法[3 ] ( directional similarity2 based clustering algorit hm ,DSCM) 定义一个新的 方向相似度量函数 S ( xj , wi) 来度量方向数据向量 xj 和聚类中心向量 wi 的相似性 : S ( xj , wi) = e kx T j wi , i = 1 ,2 , …, c 代表类别下标 , j = 1 ,2 , …, n 代表样本 下标 , k 为尺度参数. S ( xj , wi) 值越大说明数据向量 xj 与中心向量 wi 的相似度越高. DSCM 算法定义 聚类目标函数为 J S = ∑ c i = 1 ∑ n j = 1 S ( xj ,wi) = ∑ c i = 1 ∑ n j =1 e kx T j wi . (1) DSCM 算法通过拉格朗日优化理论构造拉格 朗日优化目标函数 ,推导出中心向量 wi 的迭代公 式 ,对所有样本经过有限次迭代过程自组织的找到 所有不动点 , 进一步采用凝聚层次聚类算法 ( ag2 glomerative hierarchical clustering ,A HC) 分析不动 点的层次数 ,并通过层次聚类图进一步确定最佳聚 类数以及类与类之间的关系. DSCM 算法可以避免初始化敏感的问题 ,能够 对方向性数据进行自组织 ,并利用 A HC 算法侦测 出最优的聚类数. 但对于高维大量数据特别是文本 数据 , 由 于 样 本 数 很 大 , 对 所 有 样 本 无 法 通 过 DSCM 算法中的有限次迭代过程 ,自组织的找到所 有不动点. 因此 DSCM 算法的应用受到了很大的局 限性. 2 鲁棒的模糊方向相似性聚类算法 211 模糊方向相似性聚类算法(FDSC) 在方向相似性聚类算法的基础上 ,引入模糊隶 属度关系 ,建立如下模糊化的目标函数 : J FDSC = ∑ c i = 1 ∑ n j = 1 u m ij e kx T j wi . (2) 目标函数满足条件 : ∑ c i =1 uij = 1 ,0 0 ,即权重指数 m < 1 ,同时为了保证算法有较好 的收敛性 ,权重指数 0 < m < 1. FDSC 聚类思想可以 理解成通过中心向量和隶属度的迭代公式求解最优 聚类中心 wi ,使得目标代价函数 J FDBC最大 ,即样本 间相似度总和最大. 212 基于竞争学习理论的隶属度目标函数的构造 竞争学习的学习规则分为 WTA (winner2take2 all) 与 WTM ( winner2take2more) 2 种 ,分别称为 “硬”竞争学习(hard competitive learning) 与“软”竞 争学习 (soft competitive learning) [425 ] . WTA 规则 存在一个重要问题 :对于不同初始值的节点 , 学习 过程中可能存在死节点 (dead nodes) 或利用不充分 (under2utilization) 的现象. 为此 ,研究人员提出了 WTM 规则 ,通过引入模糊隶属度等方法 ,削弱了学 习对节点初始值的依赖 ,但同时也造成数据的获胜 节点不确定 ,使得部分节点可能偏离其实际的类数 据. 文献[ 6 ]提出了惩罚对手的竞争学习 (RPCL) , 对于数据集中的每个样本 ,不仅其获胜节点以一定 的学习速率向该数据集“靠近”,而且其竞争对手以 更小的学习速率(惩罚速率) 被“推离”该数据集 ,从 而减小了对学习过程的干扰. 基于惩罚对手的竞争学习 ( RPCL) 的思想 ,在 模糊方向相似性聚类算法 FDSC 的基础之上 ,文中 进一步提出鲁棒性的模糊方向相似性聚类算法 RFDSC. 对于一个单独的样本点 xj ,通过引入隶属 度约束函数 : f ( u1 , u2 , …, uc ) = ∑ c i =1 ui ( u m- 1 i - 1) , 构造新的目标函数 : J RFDSC = ∑ c i = 1 ∑ n j = 1 u m ij (e kx T j wi ) - ∑ n j = 1 aj ∑ c i =1 uij ( u m- 1 ij - 1) . (5) 下文将对式(5) 中参数 aj (1 ≤j ≤n) 的选择做说明. 权重指数 m ∈(0 ,1) ,目标函数满足 ∑ c i = 1 uij = 1 ,0 < ·44 · 智 能 系 统 学 报 第 3 卷
第1期 朱林，等：鲁棒的模糊方向相似性聚类算法 ·45· 时： 20), ,u)取得最大值m-1;当u(i=1,2, 代入式6)从而得到： 中一个4为1，其他h(i≠为0时，f(h,, 地=(es,.mine.+Vvav/ 取最小值0，即0≤f(h,也，，)≤cm-1. 7) 通过加入隶属度约束函数，使得当函数J RFDSC hmin 极大，即f(M,也，)极小时，出现某个趋向 2)中心向量w迭代公式： 于1，其他的“(iW趋向于0的情况.图1显示加 ∑xue 入约束函数后，也的明晰含义被显著提升.改进算 (8) 法兼顾了硬聚类和模糊聚类的优点，因此对数据集 Ⅱ∑xuge,I 将有更好的鲁棒性」 下面对定理3中出现的权重指数m、尺度参数 -U(x) 1.0 -U(x) k和模糊程度常数刀的选择做详细说明. 0.8 --U(x) 对于权重指数m,上文已经指出由于与传统的 0.6 FCM聚类算法的不同，按照FDSC和RFDSC算法 04 定义，数据向量x与中心向量w,的相似度越高其 03 隶属度应越大，故权重指数m1)或减小(k<1)方向数据 1.0 0.8 向量x和聚类中心向量w,的相似性程度.实验结 --(x ---U(x) 果表明，当权重指数k取值在1~5时，具有较好的 0.4 收敛性和聚类效果，故文中尺度参数k取3。 02 模糊程度常数？的选择同样与数据集有关，影 -2 0 24681012 响模糊划分的模糊程度，值越大模糊程度越高：值越 小模糊程度越低，越趋进于硬聚类.当趋于无穷时， (b)RFDSC算法的隶属度函数 样本点对每一类的隶属度均为1/c.通过对模糊程 图1不同的求属度函数曲线 度常数的控制，使得样本点对距离最近的类中心施 Fig.1 Different kinds of membership curves 加最大的吸引力，这个力越大，类中心收敛速度也越 2.3 RFDSC算法 快，样本点也可以对相似性较小的类中心有微弱的 对于RFDSC算法，首先给出如下定理 吸引力，避免聚类过程出现死节点，保证了算法具有 很好的鲁棒性).由于RFDSC算法采用了竞争学 定理3在∑山=1,0<∑山<m,西<n, 习规则，通过加入隶属度约束函数显著提升隶属度 山∈0,1]，ww,=1以及权重指数m∈0，)条 明晰含义，兼顾了硬聚类和模糊聚类的优点，因 件下，使RFDSC算法的目标函数JRD= 此在高维大量数据情况下，RFDSC算法比FDSC算 王，Ge·,w1G)取极值 法的鲁棒性和收敛速度都有了很大提高.由于 RFDSC算法对赢者的吸引力的增强作用随I减小 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
∑ n j = 1 uij 0) , 代入式(6) 从而得到 : uij = (e kx T j wi - min e kx T j w 3 +η) - 1/ ( m- 1) / ∑ c i =1 (e kx T j wi - min e kx T j w 3 +η) - 1/ ( m- 1) . (7) 2) 中心向量 wi 迭代公式 : wi = ∑ n j = 1 x T j u m ij e kx T j wi ‖∑ n j = 1 x T j u m ij e kx T j wi ‖ . (8) 下面对定理 3 中出现的权重指数 m、尺度参数 k 和模糊程度常数η的选择做详细说明. 对于权重指数 m ,上文已经指出由于与传统的 FCM 聚类算法的不同 ,按照 FDSC 和 RFDSC 算法 定义 ,数据向量 xj 与中心向量 wi 的相似度越高其 隶属度应越大 ,故权重指数 m 1) 或减小( k < 1) 方向数据 向量 xj 和聚类中心向量 wi 的相似性程度. 实验结 果表明 ,当权重指数 k 取值在 1～5 时 ,具有较好的 收敛性和聚类效果 ,故文中尺度参数 k 取 3. 模糊程度常数η的选择同样与数据集有关 ,影 响模糊划分的模糊程度 ,值越大模糊程度越高;值越 小模糊程度越低 ,越趋进于硬聚类. 当趋于无穷时 , 样本点对每一类的隶属度均为 1/ c. 通过对模糊程 度常数的控制 ,使得样本点对距离最近的类中心施 加最大的吸引力 ,这个力越大 ,类中心收敛速度也越 快;样本点也可以对相似性较小的类中心有微弱的 吸引力 ,避免聚类过程出现死节点 ,保证了算法具有 很好的鲁棒性[7 ] . 由于 RFDSC 算法采用了竞争学 习规则 ,通过加入隶属度约束函数显著提升隶属度 uij明晰含义 ,兼顾了硬聚类和模糊聚类的优点 ,因 此在高维大量数据情况下 ,RFDSC 算法比 FDSC 算 法的鲁棒性和收敛速度都有了很大提高. 由于 RFDSC 算法对赢者的吸引力的增强作用随η减小 第 1 期 朱 林 ,等 :鲁棒的模糊方向相似性聚类算法 ·45 ·
·46 智能系统学报 第3卷 而增大，对赢者对手的抑制作用随增大而减小，所 随机变量，互信息NMI公式定义为NMI(X,Y)= 以需要选取一个合适的1值.实验结果表明，？的取 IX:Y ，I(X:Y)为变量X,Y的互信息 值取所有方向数据向量x到聚类中心向量w:的最 JH(x)·H(Y) 大相似性的0.01~0.2左右较为合适，故文中模糊 量，H9,H(Y)为变量X和Y的熵.平均准确率 程度常数取0.15. atb 基于定理3，得到具有更好鲁棒性的模糊方向 AA的公式定义为：AA(X,)=nx.)/2其中 相似性聚类算法RFDSC.下面给出RFDSC算法的 a表示任意2个样本在X、Y中同属于一类的个数， 完整描述： b表示任意2个样本都不属于同一类的个数，n表示 1)初始化聚类数目c(2≤c≤N),阈值e(1=1 数据集的样本个数.互信息NMI和平均准确率AA 为迭代次数、权重指数m、尺度参数k、模糊程度常 的范围均为0,1]，值越高表示聚类结果越准确，值 数刀和最大迭代次数T,并随机产生并归一化中心 越小2种划分差距越大，在X、Y完全一致的情况 向量w: 下，NMI和AA值为1. 2)根据式7)计算样本的隶属度值1： 3.2实验数据集说明 3)根据式8)计算归一化中心向量W: 实验采用20 Newsgroups!11的数据集及部分 4如果‖1-‖T则停止，算 来自CLUTO文本聚类工具箱的10种数据集.数 法结束，否则1=1+1，跳转2)： 据集含有的样本数从204个到19949不等，数据维 5)当算法收敛，得到各类的中心向量w和样本 数最小的为5832维，最大的为43586维，实际聚类数 集模糊隶属度 最小的为3个，最大的为20个，从以上特征看出这 些数据集很好的反映了不同文本数据集所具有的特 3 实验结果及分析 征.其中NG20数据平均地选自来自20个不同新闻 在本节中首先介绍聚类性能的评价标准，然后 组，经过的Bow toolkit!s]对20 Newsgroups文本 分别对文本数据集进行说明，最后通过使用SPK 进行了预处理后含有19949个向量文本数据. means)、soft-movMF2、FDSC和RFDSC4种相 NG17-19是NG20数据的一个子集，以往的聚类算 似性聚类算法对文本数据集进行测试，以检测各种 法对该数据集的聚类结果表明，因为类与类之间有 聚类算法的性能.由于DSCM算法在处理高维大量 重叠导致对该数据集的聚类难度较高.其他数据均 数据时，算法速度太慢，对文本数据集的有所有样本 来自CLUTO工具箱4，，这些数据集均已经过预处 无法通过有限次迭代过程，自组织的找到所有不动 理为向量文本数据.数据集的详细说明见表1， 点，因此没有对DSCM算法进行比较 表1文本数据集的简要说明 3.1算法性能评价准则 Table 1 Summary of text datasets 对于聚类结果有效性的度量，可以分为面向分 Data Source Kbalance 类的和面向相似性的2种度量方式.第1种度量方 NG20 20-Newsgroups 1994943586200.991 式，如互信息(normalized mutual information, 3 overlapping/ NM)、纯度和F度量，这些度量评估聚类结果包含 NG1719 299815810 30.998 subgroups from N(20 单个类的对象的程度.第2种度量方式，如平均准确 ohscal OHSUMED-233445 1116211465100.437 AA(averaged accuracy or rand index)Jaccard klb WebACE 234021839 6 0043 度量，这些方法度量在多大程度上，同一个类的2个 hitech San Jose Mercury(TREC) 230110080 60.192 对象在同一簇中，或相反⑧1.而衡量传统信息检索系 la12 LA Times(TREC) 627931472 60282 统的性能参数：召回率(Recall)和精度(Precision)也 trll TREC 414 6429 9 0046 是衡量分类算法性能的常用指标，然而聚类的过程 tr23 TREC 2045832 60.066 中并不存在自动分类类别与手工分类类别确定的一 tr41 TREC 878 7454100.037 一对应关系，因而无法像分类一样直接以精度和召 tr45 TREC 6908261100.088 回率作为评价标准.为此在文中采用互信息 注：a代表文本数（样本数），代表词项维数)k代 NMI和平均准确率AA2)分别作为算法的面 表文本实际类别数，balance是数据的平衡系数即包含最少 向分类和面向相似性的2种评价标准.假设X代表 文本数的类与包含最多文本数的类中的文本数之比，这个值 己知的文本类标随机变量，y代表聚类结果的类标 反映了数据集内类与类之间的平衡性 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
而增大 ,对赢者对手的抑制作用随η增大而减小 ,所 以需要选取一个合适的η值. 实验结果表明 ,η的取 值取所有方向数据向量 x 到聚类中心向量 wi 的最 大相似性的 0101～012 左右较为合适 ,故文中模糊 程度常数η取 0115. 基于定理 3 ,得到具有更好鲁棒性的模糊方向 相似性聚类算法 RFDSC. 下面给出 RFDSC 算法的 完整描述 : 1) 初始化聚类数目 c (2 ≤c ≤N) ,阈值ε( l = 1 为迭代次数) 、权重指数 m、尺度参数 k、模糊程度常 数η和最大迭代次数 T ,并随机产生并归一化中心 向量 w 1 i ; 2) 根据式(7) 计算样本的隶属度值 u l + 1 ij ; 3) 根据式(8) 计算归一化中心向量 w l + 1 i ; 4) 如果 ‖u l + 1 ij - u ( l) ij ‖ T 则停止 ,算 法结束 ,否则 l = l + 1 ,跳转 2) ; 5) 当算法收敛 ,得到各类的中心向量 wi 和样本 集模糊隶属度 uij . 3 实验结果及分析 在本节中首先介绍聚类性能的评价标准 ,然后 分别对文本数据集进行说明 ,最后通过使用 SP K2 means [ 1 ] 、soft2movMF [ 2 ] 、FDSC 和 RFDSC 4 种相 似性聚类算法对文本数据集进行测试 ,以检测各种 聚类算法的性能. 由于 DSCM 算法在处理高维大量 数据时 ,算法速度太慢 ,对文本数据集的有所有样本 无法通过有限次迭代过程 ,自组织的找到所有不动 点 ,因此没有对 DSCM 算法进行比较. 311 算法性能评价准则 对于聚类结果有效性的度量 ,可以分为面向分 类的和面向相似性的 2 种度量方式. 第 1 种度量方 式 , 如 互 信 息 ( normalized mut ual information , NMI) 、纯度和 F 度量 ,这些度量评估聚类结果包含 单个类的对象的程度. 第 2 种度量方式 ,如平均准确 率 AA ( averaged accuracy or rand index) 、J accard 度量 ,这些方法度量在多大程度上 ,同一个类的 2 个 对象在同一簇中 ,或相反[8 ] . 而衡量传统信息检索系 统的性能参数 :召回率(Recall) 和精度(Precision) 也 是衡量分类算法性能的常用指标. 然而聚类的过程 中并不存在自动分类类别与手工分类类别确定的一 一对应关系 ,因而无法像分类一样直接以精度和召 回率作为评价标准[9 ] . 为此在文中采用互信息 NMI [10 ]和平均准确率 AA [11212 ] 分别作为算法的面 向分类和面向相似性的 2 种评价标准. 假设 X 代表 已知的文本类标随机变量 , Y 代表聚类结果的类标 随机变量 ,互信息 NMI 公式定义为 NMI( X , Y) = I ( X ; Y) H ( X) ·H ( Y) , I ( X ; Y) 为变量 X , Y 的互信息 量 , H ( X) , H ( Y) 为变量 X 和 Y 的熵. 平均准确率 AA 的公式定义为 :AA ( X , Y) = a + b n ×( n - 1) / 2 ,其中 a 表示任意 2 个样本在 X 、Y 中同属于一类的个数 , b表示任意 2 个样本都不属于同一类的个数 , n 表示 数据集的样本个数. 互信息 NMI 和平均准确率 AA 的范围均为[0 ,1 ] ,值越高表示聚类结果越准确 ,值 越小 2 种划分差距越大 ,在 X 、Y 完全一致的情况 下 ,NMI 和 AA 值为 1. 312 实验数据集说明 实验采用 202Newsgroup s [13 ] 的数据集及部分 来自 CL U TO [ 14 ]文本聚类工具箱的 10 种数据集. 数 据集含有的样本数从 204 个到19 949不等 ,数据维 数最小的为5 832维 ,最大的为43 586维 ,实际聚类数 最小的为 3 个 ,最大的为 20 个 ,从以上特征看出这 些数据集很好的反映了不同文本数据集所具有的特 征. 其中 N G20 数据平均地选自来自 20 个不同新闻 组 ,经过的 Bow toolkit [ 15 ] 对 202Newsgroup s 文本 进行了预 处理后含 有 19 949 个 向 量 文 本 数 据. N G17219 是 N G20 数据的一个子集 ,以往的聚类算 法对该数据集的聚类结果表明 ,因为类与类之间有 重叠导致对该数据集的聚类难度较高. 其他数据均 来自 CL U TO 工具箱[14 ] ,这些数据集均已经过预处 理为向量文本数据. 数据集的详细说明见表 1. 表 1 文本数据集的简要说明 Table 1 Summary of text datasets Data Source nd nw K balance N G20 202Newsgroup s 19 949 43 586 20 01991 N G17219 3 overlapping/ subgroups from NG20 2 998 15 810 3 01998 ohscal O HSUMED2233445 11 162 11 465 10 01437 klb WebACE 2 340 21 839 6 01043 hitech San Jose Mercury( TREC) 2 301 10 080 6 01192 la12 LA Times( TREC) 6 279 31 472 6 01282 tr11 TREC 414 6 429 9 01046 tr23 TREC 204 5 832 6 01066 tr41 TREC 878 7 454 10 01037 tr45 TREC 690 8 261 10 01088 注 : nd 代表文本数 (样本数) , nw 代表词项 (维数) , k 代 表文本实际类别数 , balance 是数据的平衡系数即包含最少 文本数的类与包含最多文本数的类中的文本数之比 ,这个值 反映了数据集内类与类之间的平衡性. ·46 · 智 能 系 统 学 报 第 3 卷
第1期 朱林，等：鲁棒的模糊方向相似性聚类算法 ·47 在使用方向性聚类算法分析各数据集前，以上 表5模糊程度常数I变化时DSC算法针 数据都经过L2归一化处理 对tr5数据集的实验结果 3.3实验结果及分析 Table 5 The results of RFDSC on tr45 datasets with 为了测试算法性能，对以上数据集分别采用 the change of n SPKmeans、soft-novMF、FDSC和RFDSC4种相 0.05 0.1 0.15 02 似性聚类算法的结果进行比较.为保证实验的公平 性，所有算法均采用随机初始化的策略选取初始聚 互信息 0657n0606610050673n050640h04 类中心，并对每种算法进行20次聚类实验后取平均 值作为最终实验结果」 平均准确率0894 0.895 0.899 0.884 首先，对FDSC算法和RFDSC算法采用不同 大小的尺度参数k、模糊程度常数？和权重指数m 来测试其对聚类结果的影响. 表6表7分别给出了RFDSC算法采用不同大 表2、表3分别给出了FDSC算法采用不同大 小的权重指数m针对NG17-19和tr45数据集进行 小的尺度参数k针对NG1719和tr45数据集进行 聚类实验后得到的互信息NMI的均值和标准差及 聚类实验后得到的互信息NMI的均值和标准差及 平均准确率AA的均值.实验中模糊程度常数7取 平均准确率AA的均值.实验中权重指数m取0.9. 0.15,尺度参数k取3 表2尺度参数k变化时DSC算法针对 表6权重指数m变化时RDSC算法针对 NG下19数据集的实验结果 NG719数据集的实验结果 Table 2 The results of FDSC on NGI7-19 datasets Table 6 The results of RFDSC on NGl7-19 with the change of k datasets with the change of m k 1 2 4 085 0.9 0.95 互信息 0326005041000504310040394h05 互信息 03970.0604180.05 0375010 平均准确率0.596 0.677 0.682 0642 平均准确率 0.675 0674 0.640 表3尺度参数k变化时FDSC算法针对 r45数据集的实验结果 表7权重指数m变化时RDSC算法 ble 3 The results of FDSC on tr45 datasets with the change of k 针对tr45数据集的实验结果 2 3 4 Table 7 The results of RFDSC on tr45 datasets with 互信息0564h030630h030649h030594h04 the change of m 平均准确率08620876 0893 0845 085 0.9 0.95 表4表5分别给出了RFDSC算法采用不同大 互信息 06490.040.6740.030649004 小的模糊程度常数n针对NG1下19和tr45数据集 进行聚类实验后得到的互信息NMI的均值和标准 平均准确率 0.885 0.902 0.887 差及平均准确率AA的均值.实验中权重指数m取 0.9,尺度参数k取3 从上述实验结果可以看出，当尺度参数k取3、 模糊程度常数取0.15、权重指数m取0.9时，FD 表4模糊程度常数n变化时RDSC算法针对 NG下19数据集的实验结果 SC算法和RFDSC算法取得比较好的聚类结果 Ta ble 4 The results of RFDSC on NGI7-19 datasets with 下面给出SPKmeans、soft-movMF、FDSC和 the change of n RFDSC4种相似性聚类算法对上述10种文本数据 集的聚类结果。 2 0.05 0.1 0.15 02 表8、表9给出了4种算法进行聚类实验后得 互信息0.3780.080397h080.418005Q399h09 到的互信息NMI的均值和标准差， 平均准确率 0.645 0.647 0.674 0673 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
在使用方向性聚类算法分析各数据集前 ,以上 数据都经过 L2 归一化处理. 313 实验结果及分析 为了测试算法性能 ,对以上数据集分别采用 SP Kmeans、soft2movMF、FDSC 和 RFDSC 4 种相 似性聚类算法的结果进行比较. 为保证实验的公平 性 ,所有算法均采用随机初始化的策略选取初始聚 类中心 ,并对每种算法进行 20 次聚类实验后取平均 值作为最终实验结果. 首先 ,对 FDSC 算法和 RFDSC 算法采用不同 大小的尺度参数 k、模糊程度常数η和权重指数 m 来测试其对聚类结果的影响. 表 2、表 3 分别给出了 FDSC 算法采用不同大 小的尺度参数 k 针对 N G17219 和 tr45 数据集进行 聚类实验后得到的互信息 NMI 的均值和标准差及 平均准确率 AA 的均值. 实验中权重指数 m 取 019. 表 2 尺度参数 k变化时 FDSC算法针对 NG17219 数据集的实验结果 Table 2 The results of FDSC on NG17219 datasets with the change of k k 1 2 3 4 互信息 01326 ±0105 01410 ±0105 01431 ±0104 01394 ±0105 平均准确率 01596 01677 01682 01642 表 3 尺度参数 k 变化时 FDSC算法针对 tr45 数据集的实验结果 Table 3 The results of FDSC on tr45 datasets with the change of k k 1 2 3 4 互信息 01564 ±0103 01630 ±0103 01649 ±0103 01594 ±0104 平均准确率 01862 01876 01893 01845 表 4 表 5 分别给出了 RFDSC 算法采用不同大 小的模糊程度常数η针对 N G17219 和 tr45 数据集 进行聚类实验后得到的互信息 NMI 的均值和标准 差及平均准确率 AA 的均值. 实验中权重指数 m 取 019 ,尺度参数 k 取 3. 表 4 模糊程度常数η变化时 RFDSC算法针对 NG17219 数据集的实验结果 Table 4 The results of RFDSC on NG17219 datasets with the change of η η 0105 011 0115 012 互信息 01378 ±0108 01397 ±0108 01418 ±0105 01399 ±0109 平均准确率 01645 01647 01674 01673 表 5 模糊程度常数η变化时 RFDSC算法针 对 tr45 数据集的实验结果 Table 5 The results of RFDSC on tr45 datasets with the change of η η 0105 011 0115 012 互信息 01657 ±0105 01661 ±0105 01673 ±0105 01640 ±0104 平均准确率 01894 01895 01899 01884 表 6 表 7 分别给出了 RFDSC 算法采用不同大 小的权重指数 m 针对 N G17219 和 tr45 数据集进行 聚类实验后得到的互信息 NMI 的均值和标准差及 平均准确率 AA 的均值. 实验中模糊程度常数η取 0115 ,尺度参数 k 取 3. 表 6 权重指数 m变化时 RFDSC算法针对 NG17219 数据集的实验结果 Table 6 The results of RFDSC on NG17219 datasets with the change of m m 0185 019 0195 互信息 01397 ±0106 01418 ±0105 01375 ±0110 平均准确率 01675 01674 01640 表 7 权重指数 m变化时 RFDSC算法 针对 tr45 数据集的实验结果 Table 7 The results of RFDSC on tr45 datasets with the change of m m 0185 019 0195 互信息 01649 ±0104 01674 ±0103 01649 ±0104 平均准确率 01885 01902 01887 从上述实验结果可以看出 ,当尺度参数 k 取 3、 模糊程度常数η取 0115、权重指数 m 取 019 时 ,FD2 SC 算法和 RFDSC 算法取得比较好的聚类结果. 下面给出 SP Kmeans、soft2movMF、FDSC 和 RFDSC 4 种相似性聚类算法对上述 10 种文本数据 集的聚类结果. 表 8、表 9 给出了 4 种算法进行聚类实验后得 到的互信息 NMI 的均值和标准差. 第 1 期 朱 林 ,等 :鲁棒的模糊方向相似性聚类算法 ·47 ·
·48 智能系统学报 第3卷 表8针对N20、NG719、ohscal、kIb、hitech 数情况下要小于其他算法，说明FDSC和RFDSC 数据集的互信息值 算法的稳定性较好，能够更好地避免局部极值点.当 Table 8 NMI results on NC20,NGI7-19, 然，在部分数据集的试验中，RFDSC算法与其他算 ohscal,klb,hitech datasets 法相比，还不是最优的，在下一步的工作中，将对 N20 NG1719 ohscal klb hitech RFDSC算法中权重指数m、尺度参数k和模糊程度 SPKmeans0548h030303h090437h020579h050282h02 常数的选择问题做更深入的研究，以提高算法的 sofi-movMF057002030h100442h020607h04022h2 性能 DSC04430020431h080433n0106020B02801 4结束语 RFDSC0564020418h050447n010624h0G028h01 文中在方向相似性聚类算法DSCM基础之上， 首先提出模糊方向相似性聚类算法FDSC,继而从 表9针对a12r11、tr23tr41tr45数据集的互信息值 竞争学习角度，通过引入隶属度约束函数，并根据拉 Ta ble 9 NMI results on la12,trl1,tr23,tr41,tr45 datasets 格朗日优化理论推导出鲁棒的模糊方向相似性聚类 la12 trl1 tr23 tr41 tr45 算法RFDSC,最后将RFDSC算法很好的应用于文 SPKmeans0523h0B0535h050269h050585h50657h07 本方向性数据聚类中，从而解决了DSCM对高维大 sof+-movMF0535004060mh04036600406270040660h04 量数据的扩展问题 FDSC0471020641h02038620645h0B0636h03 附 录 RFDSC05220030646h0203490020654h0B0674n03 定理1证明 证明使FDSC算法的目标函数即式(2)中的 表10、表11给出了4种算法进行聚类实验后 得到的平均准确率AA的均值 JDc达到最大，即求在) %=1,0<2%<m 表10针对N20Ya79-ohscal klbhitech数据集的平均准确率 ∈0,11以及ww,=1条件下的极值，为此引入 Tihe 10 AA resuts on NG20,NG719,ohscal,klb,hitech datasets Lagrange乘子入，b.并定义Lagrange目标函数 Lw.入，b NG20NG1719 ohscal klb hitech SPKmeans 0.935 0.663 0.863 0.730 0.726 Lw,a》=,,9ey soft-movMF 0.938 0.672 0865 0.747 0.752 w-1+h(ww.-1. 9 FDSC 0889 0.677 0.865 0746 0.732 对Lw,入，关于求偏导，令其值为零得 RFDSC 0.924 0.6740.867 0.7790.757 =[ 10) m(e) 表11针对a12、trl1、r23、tr41、tr45数据集的平均准确率 将式10代入，卫4=1，消去←/m得 Table 11 AA results on lal2,trl1,tr23,tr41,tr45 datasets (11) lal2 trll tr23 tr41 tr45 对Lw,入，b关于w求偏导数，并令其值为零 SPKmeans 0.830 0.840 0.680 0.8530.886 可得 soft-movMF 0.835 0.856 0.718 0.860 0.893 2w 0. (12) FDSC 0805 0.859 0.732 0.861 0.877 则有 w=∑kxue"/(-2). 13) RFDSC 0821 0.864 0.702 0.865 0.902 由于ww,=1,由公式13)可以进一步推出： 从上述实验结果可以看出，RFDSC算法的聚类 ∑xue" 效果在大多数情况下要好于其他算法，同时也发现 证毕 了FDSC和RFDSC算法的互信息的标准差在大多 ∑xwge, 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
表 8 针对 NG20、NG17219、ohscal、k1b、hitech 数据集的互信息值 Table 8 NMI results on NG20 , NG17219 , ohscal , k1b, hitech datasets N G20 N G17219 ohscal k1b hitech SPKmeans 01548 ±0103 01303 ±0109 01437 ±0102 01579 ±0105 01282 ±0102 soft2movMF 01570 ±0102 01390 ±0110 01442 ±0102 01607 ±0104 01292 ±0102 FDSC 01443 ±0102 01431 ±0108 01433 ±0101 01602 ±0103 01288 ±0101 RFDSC 01564 ±0102 01418 ±0105 01447 ±0101 01624 ±0103 01298 ±0101 表 9 针对 la12、tr11、tr23、tr41、tr45 数据集的互信息值 Table 9 NMI results on la12 ,tr11 ,tr23 ,tr41 ,tr45 datasets la12 tr11 tr23 tr41 tr45 SPKmeans 01523 ±0103 01535 ±0105 01269 ±0105 01585 ±0105 01657 ±0107 soft2movMF 01535 ±0104 01602 ±0104 01366 ±0104 01627 ±0104 01660 ±0104 FDSC 01471 ±0102 01641 ±0102 01386 ±0102 01645 ±0103 01636 ±0103 RFDSC 01522 ±0103 01646 ±0102 01349 ±0102 01654 ±0103 01674 ±0103 表 10、表 11 给出了 4 种算法进行聚类实验后 得到的平均准确率 AA 的均值. 表10 针对 NG20、NG17219、ohscal、k1b、hitech数据集的平均准确率 Table 10 AAresults on NG20, NG17219,ohscal , k1b, hitech datasets N G20 N G17219 ohscal k1b hitech SPKmeans 01935 01663 01863 01730 01726 soft2movMF 01938 01672 01865 01747 01752 FDSC 01889 01677 01865 01746 01732 RFDSC 01924 01674 01867 01779 01757 表 11 针对 la12、tr11、tr23、tr41、tr45 数据集的平均准确率 Table 11 AA results on la12 ,tr11 ,tr23 ,tr41 ,tr45 datasets la12 tr11 tr23 tr41 tr45 SPKmeans 01830 01840 01680 01853 01886 soft2movMF 01835 01856 01718 01860 01893 FDSC 01805 01859 01732 01861 01877 RFDSC 01821 01864 01702 01865 01902 从上述实验结果可以看出 ,RFDSC 算法的聚类 效果在大多数情况下要好于其他算法 ,同时也发现 了 FDSC 和 RFDSC 算法的互信息的标准差在大多 数情况下要小于其他算法 ,说明 FDSC 和 RFDSC 算法的稳定性较好 ,能够更好地避免局部极值点. 当 然 ,在部分数据集的试验中 ,RFDSC 算法与其他算 法相比 ,还不是最优的 ,在下一步的工作中 ,将对 RFDSC 算法中权重指数 m、尺度参数 k 和模糊程度 常数η的选择问题做更深入的研究 ,以提高算法的 性能. 4 结束语 文中在方向相似性聚类算法 DSCM 基础之上 , 首先提出模糊方向相似性聚类算法 FDSC ,继而从 竞争学习角度 ,通过引入隶属度约束函数 ,并根据拉 格朗日优化理论推导出鲁棒的模糊方向相似性聚类 算法 RFDSC ,最后将 RFDSC 算法很好的应用于文 本方向性数据聚类中 ,从而解决了 DSCM 对高维大 量数据的扩展问题. 附 录 定理 1 证明 证明 使 FDSC 算法的目标函数即式 (2) 中的 J FDSC 达到最大 ,即求在 ∑ c i = 1 uij = 1 ,0 < ∑ n j = 1 uij < n , uij ∈[0 ,1 ] 以及 w T i wi = 1 条件下的极值 ,为此引入 Lagrange 乘子 λ, b. 并定义 Lagrange 目标 函数 L (w,λ, b) : L (w,λ, a , b) = ∑ c i =1 ∑ n j =1 u m ij (e kx T j wi ) + ∑ n j = 1 λj ( ∑ c i = 1 uij - 1) + ∑ c i = 1 bi (w T i wi - 1) . (9) 对 L (w,λ, b) 关于 uij求偏导 ,令其值为零得 uij = [ - λj m (e kx T j wi ) ] 1/ ( m- 1) . (10) 将式(10) 代入 ∑ c i = 1 uij = 1 ,消去( - λj) / m 得 uij = (e kx T j wi ) - 1/ ( m- 1) / ∑ c i = 1 (e kx T j wi ) - 1/ ( m- 1) . (11) 对 L (w,λ, b) 关于 wi 求偏导数 ,并令其值为零 可得 9L 9wi = ∑ n j =1 kx T j u m ij e kx T j wi + 2biwi = 0. (12) 则有 wi = ∑ n j = 1 kx T j u m ij e kx T j wi / ( - 2bi) . (13) 由于 w T i wi = 1 ,由公式(13) 可以进一步推出 : wi = ∑ n j = 1 x T j u m ij e kx T j wi ‖∑ n j = 1 x T j u m ij e kx T j wi ‖ . 证毕. ·48 · 智 能 系 统 学 报 第 3 卷
第1期 朱林，等：鲁棒的模糊方向相似性聚类算法 ·49· 定理2证明 证明：1)因为0≤h≤1,00), 又因为f(M,也，在0,1下上是连续的， 代入式10)从而得到 故f(n,,一定有最值，而最值一定在驻点 u=(es"min e 或边界点处取得 e.mine以.+nvey. (17) 下面分别求f(h,,)在驻点或边界点 对Lw,人，a,b关于w求偏导数，并令其值为零得 处的函数值 y当n=e==1时，fn,e,)= 0=,25e+26m=0. (18) cm-1. 则有： 2)对于0,1的边界点(h,也，，e),设h, w=】 ae/126. (19) 地，h中有p1≤p≤个w为0，q0≤g)个 由于ww=1,由式(19)可以进一步推出： h为1. xue ①若p+q=c,则∑4w1-)=0. W= 证毕 ②若p+q<c,将w=0,1代入f(M,, ue )中，不失一般性，不防假设前p+g个u,为0或1， 则f(n,,…)转化为c·p·q维的形如 参考文献： (1·)的函数.由反证法很容易证明 [1]DHILLON I S,MODHA D S.Concept decompositions -p1 for large sparse text data using clustering [J].Machine ∑w(w1-1)<cm.1 Learning,2001,42(1):143175. - [2]BANERJEE A,DHILLON I S,GHOST J,et al.Gem 综上所述，f(h,b,k)在m==g= erative model based clustering of directional data [C]// 七时取最大值。.1 证毕 Conference on Knowledge Discovery in Data.Washing- ton,DC,2003. 定理3证明 [3]LI H X,WANG S T,XIU Y.Applying robust direc- 证明使RFDSC算法的目标函数即式(5)中 tional similarity based clustering approach RDSC to clas- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
定理 2 证明 证明 : 1) 因为 0 ≤ ui ≤1 ,0 0) , 代入式(10) 从而得到 uij = (e kx T j wi - min e kx T j w 3 +η) - 1/ ( m- 1) / ∑ c i =1 (e kx T j wi - min e kx T j w 3 +η) - 1/ ( m- 1) . (17) 对 L (w,λ, a , b) 关于 wi 求偏导数 ,并令其值为零得 9L 9wi = ∑ n j =1 kx T j u m ij e kx T j wi + 2biwi = 0. (18) 则有 : wi = ∑ n j = 1 kx T j u m ij e kx T j wi / ( - 2bi) . (19) 由于 w T i wi = 1 ,由式(19) 可以进一步推出 : wi = ∑ n j = 1 x T j u m ij e kx T j wi ‖∑ n j = 1 x T j u m ij e kx T j wi ‖ . 证毕. 参考文献 : [1 ]D HILLON I S , MODHA D S. Concept decompositions for large sparse text data using clustering [J ]. Machine Learning , 2001 , 42 (1) :1432175. [2 ]BAN ERJ EE A , DHILLON I S , GHOST J , et al. Gen2 erative model based clustering of directional data [ C]/ / Conference on Knowledge Discovery in Data. Washing2 ton , DC , 2003. [3 ]L I H X , WAN G S T , XIU Y. Applying robust direc2 tional similarity based clustering approach RDSC to clas2 第 1 期 朱 林 ,等 :鲁棒的模糊方向相似性聚类算法 ·49 ·
·50· 智能系统学报 第3卷 sification of gene expression data [J].J Bioinformatics [12]RAND W.Objective criteria for the evaluation of clus- and Computational Biology,2006,4(3):745-768. tering methods[J ]Journal of the American Statistical [4]ZHANG YJ,LIU Z Q.Self-splitting competitive learn- Association,1971,66(336):846850. ing:a new orrline clustering paradigm [J].IEEE Trans [13 ]Available on http :/kdd.ics.uci.edu.databases/ on Neural Network,2002,13(2):369-380. 20newsgroups/20newsgroups.html. [5]WU S H,LIEW W C,YAN H,et al.Cluster analysis [14 ]Available on ftp:/www.cs.umn.edu/~karypis/CLU- of gene expression data based on self-splitting and mer- TO/flies/datasets.tar.gz. ging competitive learning [J].IEEE Trans on Informa- [15]Mow:A toolkit for statistical language modeling,text tion Technology in Biomedicine,2004,8(1):5-15. retrieval,classification and clustering Available on ht- [6]XU L,KRZYA KA,OJA E.Rival penalized competitive tp //www.cs.cmu.edu/mccallum/bow. learning for clustering analysis,RBF net and curve de- 作者简介： tection [J ]IEEE Trans on Neural Network,1993,4 朱林，男，1983年生，硕士研究生，主要 (4):636649. 研究方向为图像处理模式识别. [7]魏立梅，谢维信，对手抑制式模糊C均值算法U].电子 学报，2000,28(7)：6366. WEI Limei,XIE Weixin.Rival checked fuzzy C-means algorithm [J].Acta Electronica Sinica,2000,28(7): 63-66. [8]TAN P N.MICHAEL S,KUMAR V.Introduction to 王士同，男，1964年生，教授，博士生导 data mining [M].Boston:Addison Wesley,2005. 师，中国计算机学会高级会员，主要研究方向 [9]姜宁，宫秀军，史忠植.高维特征空间中文本聚类研究 为人工智能、模式识别、数据挖掘、神经网络 U].计算机工程与应用，2002,38(10)：6367 及生物信息学 JIANG Ning,GONG Xiujun,SHI Zhongzhi.Text clus- tering in highrdimension feature space[J].Computer En gineering and Applications,2002,38(10):63-67. [10]AL EXANDER S,JO YDEEP G.Cluster ensembles-a 修字，男，1976年生，硕士研究生，主要 knowledge reuse framework for combining partitions 研究方向为模式识别、数据挖掘 [J].Journal of Machine Learning Research,2002,3 (3):583-617. [11]MA KOTO I,TA KENOBU T.Hierarchical Bayesian clustering for automatic text classification[R].Depart- ment of Computer Science,Tokyo Institute of Technolo- gy,1995. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
sification of gene expression data [J ]. J Bioinformatics and Computational Biology , 2006 , 4 (3) :7452768. [4 ]ZHAN G Y J , L IU Z Q. Self2splitting competitive learn2 ing : a new on2line clustering paradigm [J ]. IEEE Trans on Neural Network , 2002 , 13 (2) :3692380. [5 ]WU S H , L IEW W C , YAN H , et al. Cluster analysis of gene expression data based on self2splitting and mer2 ging competitive learning [J ]. IEEE Trans on Informa2 tion Technology in Biomedicine , 2004 , 8 (1) :5215. [6 ]XU L , KRZYA K A , OJ A E. Rival penalized competitive learning for clustering analysis , RBF net and curve de2 tection [J ]. IEEE Trans on Neural Network , 1993 , 4 (4) :6362649. [7 ]魏立梅 , 谢维信. 对手抑制式模糊 C 均值算法[J ]. 电子 学报 , 2000 ,28 (7) :63266. WEI Limei , XIE Weixin. Rival checked fuzzy C2means algorithm [J ]. Acta Electronica Sinica , 2000 , 28 ( 7) : 63266. [8 ] TAN P N. MICHAEL S , KUMAR V. Introduction to data mining [ M]. Boston : Addison Wesley ,2005. [9 ]姜 宁 , 宫秀军 ,史忠植. 高维特征空间中文本聚类研究 [J ]. 计算机工程与应用 , 2002 , 38 (10) :63267. J IAN G Ning , GON G Xiujun , SHI Zhongzhi. Text clus2 tering in high2dimension feature space[J ]. Computer En2 gineering and Applications , 2002 , 38 (10) : 63267. [10 ] AL EXANDER S , JO YDEEP G. Cluster ensembles2a knowledge reuse framework for combining partitions [J ]. Journal of Machine Learning Research , 2002 , 3 (3) :5832617. [11 ] MA KO TO I , TA KENOBU T. Hierarchical Bayesian clustering for automatic text classification[ R]. Depart2 ment of Computer Science ,Tokyo Institute of Technolo2 gy , 1995. [12 ]RAND W. Objective criteria for the evaluation of clus2 tering methods[J ]. Journal of the American Statistical Association , 1971 , 66 (336) :8462850. [13 ]Available on http :/ / kdd. ics. uci. edu. / databases/ 20newsgroups/ 20newsgroup s. html. [14 ]Available on ftp :/ / www. cs. umn. edu/ ～karypis/ CLU2 TO/ flies/ datasets. tar. gz. [15 ]Mow : A toolkit for statistical language modeling , text retrieval , classification and clustering Available on ht2 tp :/ / www. cs. cmu. edu/ mccallum/ bow. 作者简介 : 朱 林 ,男 ,1983 年生 ,硕士研究生 ,主要 研究方向为图像处理、模式识别. 王士同 ,男 ,1964 年生 ,教授 ,博士生导 师 ,中国计算机学会高级会员 ,主要研究方向 为人工智能、模式识别、数据挖掘、神经网络 及生物信息学. 修 宇 ,男 ,1976 年生 ,硕士研究生 ,主要 研究方向为模式识别、数据挖掘. ·50 · 智 能 系 统 学 报 第 3 卷