您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 自组织映射 >

基于自组织特征映射的聚类集成算法

发布时间:2019-06-15 22:39 来源:未知 编辑:admin

  基于自组织特征映射的聚类集成算法_工学_高等教育_教育专区。计算机工程与设计ComputerEngineering ?智能技术? andDesign 2010,31(22)4885 基于自组织特征映射的聚类集成算法 谭维, 杨燕 (西南交通大学信息科学与

  计算机工程与设计ComputerEngineering ?智能技术? andDesign 2010,31(22)4885 基于自组织特征映射的聚类集成算法 谭维, 杨燕 (西南交通大学信息科学与技术学院,四川成都610031) 摘要:为改善单一聚类算法的聚类性能,提出一种基于自组织特征映射(SOM)的聚类集成算法.该算法利用多个具有差异 性的聚类成员,将原始数据集转换成一个新的特征空间矩阵;然后计算各个聚类成员的聚类综合质量,并将其作为新特征 空间矩阵的属性权重,最后利用SOM神经网络进行集成,产生最终的共识聚类结果。实验结果表明,与集成前的基聚类算法 和其它聚类集成算法相比,该算法能够有效地提高聚类质量。 关键词:聚类集成;自组织特征映射;特征空间矩阵;聚类综合质量;属性权重 中图法分类号:TP391 文献标识码:A 文章编号:1000-7024(2010)22-4885-04 on Clustering ensemble based self-organizing feature map TAN Wei.YANG Yah (School Abstract:To zing feature ofInformation Science and Technology,Southwest Jiaotong University,Chengdu 610031,China) improve the clustering performance ofa single clustering algorithm,a clustering ensemble algorithm based on self-organi- a map is proposed.Firstly,the ordinary dataset is transformeA into the overall duster quality is computed for each clustering new feature space matrix using different clustering as so- lutions.Then solution the weight of the attribute of the new feature sp∞e matrix.FinaUy,the COD_跎138US clustering result is generated by SOM neural network.The experimental results show that the proposed algorithm ring Call effectively improve the clustering performance comparing with other clustering ensemble algorithms and the basis cluste- algorithm before combination. Key words:clustering ensemble;self-organizing feature map;feature space matrix;overall cluster quality;weight ofthe attribute 0引言 聚类分析是数据挖掘领域的一个重要研究方向,它按照 某种给定的相似性度量方式将数据对象切割成类或簇,能够 发现数据对象自然分布模式。尽管目前提出了许多聚类算法 及其改进算法,但在现实中还没有一个算法能够识别出任意 形状的数据结构分布。如果聚类算法不适合某些特殊分布的 数据集,这会导致劣质甚至是错误的聚类结果。 聚类集成川是近年来提出的一个新的概念。它综合多种 不同聚类算法或不同初始参数的同一聚类算法产生的划分, 可获得比单一聚类算法更好的聚类结果。共识函数的设计是 聚类集成最关键的问题,已成为国内外研究热点。Fred等捌提 出了一种基于共联矩阵的集成方法,该方法首先将各个聚类 算法的结果表示成共联矩阵,最后采用层次聚类法生成最后 的聚类结果。Ghosh等Ⅲ引进图分割思想,提出了CSPA,HGPA, MCLA这3种基于超图的算法。Yang等“1提出了一种基于自 适应谐振理论的聚类集成算法。它将多个改进的蚁群算法产 生的聚类成员作为ART神经网络的输入,经过ART网络模型 学习后,得到最终的聚类结果。 收稿日期:2009-12.23:修订日期:2010-05.26。 自组织特征映SOM是常用于聚类分析的一种神经网络 模型。它自动对输入模式进行聚类,可以将高维数据投影在 一维或二维网络上,并尽可能保持原始输入模式的拓扑结构。 SOM的非监督式自主学习、自稳定性、拓扑结构保持性及可 视化等特征01受到了越来越多的关注和应用。 本文提出一种基于自组织特征映射的聚类集成算法 (CESOM)。该算法首先根据差异性聚类成员把原始数据集转 换到一个新特征空间矩阵,然后引入聚类综合质量对新特征 空问矩阵属性进行加权,最后用SOM算法作为共识函数进行 聚类。文中首先介绍SOM算法基本原理和聚类综合质量,然 后详细介绍基于SOM的聚类集成算法,最后给出实验结果和 分析。 l SOM的基本原理 自组织特征映射是Kohonen教授提出的一种竞争型神经 网络模型M。该网络模拟了人脑神经元细胞层响应外部刺激 信号的功能,且不同神经元细胞对刺激信号的响应程度也不 一样。SOM网络与一般性竞争网络采用“赢者通吃”机制稍有 不同的是,当自组织映射竞争之后,除竞争获胜神经元学习 作者简介:谭维(1985-),男,湖北荆州人,硕士研究生,研究方向为计算智能和数据挖掘: CCF会员,研究方向为计算智能、群体智能和数据挖掘。E-maih tanweill03@126.com 杨燕(1964--),女,安徽合肥人,博士,教授 万方数据 4886 2010,3 1(22) 计算机工程与设计Computer Engineering and Design 外,其邻域神经元也能够学习。 SOM是由输入层和竞争层构成的双层网络,其网络拓扑 结构如图l所示。输入层由Ⅳ个神经元构成,用于接受外部输 入模式,即J) ̄r维数据向量。竞争层(输出层)通常排列成一个l 维或2维的平面阵列,由M个神经元构成,用于将输入层的节 点映射到竞争层节点上。输入层的所有节点和竞争层所有节 Ocq(f1)=I-(S?Crop+(1一历?Set,) (3) Cmp表示聚类密集性,Sep表示聚类分离性。声为平衡系 数,且OSO<l,用来权衡聚类密集性和聚类分离性的比重。一 般取声=0.5,表示二者被赋予相同的权重。 对于给定的数据集彳=仅。X2,…,妇},定义其簇内方差为 点用权值w“f=l,2,…,Ⅳ..,=l,2,…,脚进行连接,且连接权值 在网络训练过程中动态更新。 式中:Ⅳ_数据集.擀本个数,鼬,对—-x.和i距离,卜数 据集X的均值,即 一=厮 i=专∑蜀 (5) 簇内方差Dev(X)越小,表示数据集整体结构更加密集,样 本同一性越高。 若聚类结果将数据集划分成C={c。,c2,…,Cc),则定义聚 类密集性为 Cmp=吉砉渊 图l (6) 自组织特征映射网络拓扑结构 式中:C—一聚类个数,Dev(cJ>一类a的方差。根据聚类结果 应保证类内相似性最大的原则,为了使簇内数据尽町能更加 紧凑,聚类密集性应越小越好。 定义聚类分离性为 SOM算法步骤如下: (1)确定SOM网络拓扑结构,输入层和竞争层神经元个数。 (2)设置t=0,随机初始化权值向量以O)(,=l,2,…,肋,M 为竞争层神经元个数。 (3)随机为网络提供一个输入向量《f)=0m妇,…,‰)7,七= l,2,…,厶其中工为待输入的数据集向量总数。 “)计算当前输入向量与竞争层神经元的距离,并选择距 离最小的神经元为获胜神经元g(f) qO)=argmin 0“f)一’l“f)0 (1) 式中:卜高斯常量,为方便计算通常设20"=l,矗与托是类。 和类cj的聚类中心。根据聚类结果应保证类间相似性最小的 原则,为了使簇间数据尽可能更加分开,聚类分离性应越小越 好。 Cmp和Sep的定义可知,聚类综合质量Ocq值越大,表 明聚类效果越好。 Sep=南砉,善c,e冲[_掣] ∽ (5)调整获胜神经元及其邻域范围内神经元的权值向量为 3基于SOM的聚类集成 3.1特征空间变换 给定样本总数为Ⅳ数据集X=缸。X2,…,新},每个数据样本 知=k。勘,…,妇),且x,6Rd,d为样本的维数,则数据集的原始 特征空间可表示为Nxd的数据矩阵,如表l所示。 表l DimI 州)=搿椰㈤叫m j删eN,((t,)) 近区域,二者都是随时间t增加而下降的递减函数。 否则返回步骤(3)。 (7)更新学习率和邻域半径。 (2) 椭是学习率参数,且峋(班l,M(f)是获胜神经元g的邻 (6)判断输入向量是否全部提供给网络,若是转入下一步, 数据集原始特征空间矩阵 Dim2 J¨ Dim, 工l, Ⅸm4 J“ (8)若总迭代次数达到乃算法结束,否则返回步骤(3)。 工’ 工i1 2聚类综合质量 为判断聚类结果质量的好坏,需要一个客观的评价指标来 评价聚类结果的合理性。聚类性能评价方法通常分为3种叫: 外部评价法、内部评价法、相对评价法。外部评价法将聚类结 果得到类标签和已知类标签进行比较,此评价法的前提是数 据集样本的类标签己知。内部评价法在样本类标签未知的情 况下,基于数据集自身的固有特征判断聚类结果优劣。相对 评价法事先设置相关参数和定义评价标准,找出最优参数和 标准评价聚类结果。 聚类综合质量Ocq(overall cluster quality)是将聚类密集性 庇 工, 勘I X¨ 妇 工扭 勋 轴 轴 jv h .跏 舶 工腮 鼬 实验中,我们选取经典的划分聚类算法K.Means算法作 为基聚类算法,产生多个聚类成员。K.Means算法具有执行效 率高,速度快等优点,虽然算法初始中心点的选取具有随机 性,每次聚类结果都不一样,但这恰好满足了聚类成员之间的 差异性要求。 对数据集随机执行Ⅳ次K-Means算法,并产生不同的Ⅳ个 和聚类分离性”’结合的一种聚类相对评价方法。Ocq指标 定义为 聚类成员n=‰,石2,…,砌},其中篇一{而(jrf),疵∞),…,枷.)}表 示第i个样本对应的所有聚类成员划分结果,如)是第i个样本 万方数据 谭维,杨燕:基于自组织特征映射的聚类集成算法 在聚类成员乃中的类标签。构造一个矩阵F,将日个聚类成员 看作原始数据集朋拘属性,使x,Egt”,如表2所示。 表2数据集新特征空间矩阵 石o /',r2 2010,3 I(22)4887 (9) o“f)一wXt)o=1∑wp(勘一w扩I 【-?I J 重新定义的加权距离考虑了数据集内在结构信息,而不 只对仅含有对象类标签的聚类成员进行处理,聚类信息更 珊 ,rH“I) m 为完备。 SOM聚类集成算法模型如图2所示,其步骤如下: Xt 而0.) Ⅱj‰) 尬“2) 廊沁) 而0。) 而 X’ g.∞) 霸“,) 霸∞) 而b,) ,帆:) 万Ⅳ“,) 妇 m(却) E缸矗 扔“0 Ⅱ融南 数据集经过日次聚类划分和特征空间变换之后,产生了 一个NxI-I特征空间矩阵F。新的数据矩阵F的维数为何,即聚类 成员的总个数。矩阵F的各个元素不再是数据样本在原始特 征空间下属性值,而用数据样本在其所在的聚类成员中的类 标签来代替。在当前研究中,许多聚类集成算法基于NxN共 联矩阵进行共识聚类,当数据样本总数Ⅳ很大时,势必会造成 大量的内存开销。一般情况下,聚类成员个数水<Ⅳ,故采用 Nxt-媾征空间矩阵描述数据的新特征,在节约内存空间上具 有一定优势。 3.2聚类成员加权 目前多数聚类集成算法直接根据聚类成员的划分结果进 行集成,不考虑数据固有特征。此外,由于聚类成员之间的差 异性,不同聚类成员质量有好有坏,而现有的集成算法将各个 聚类成员同等对待,忽略了它们对最终集成结果影响力的大 小。对于聚类质量较好的聚类成员,应加强其对目标聚类的 贡献程度:对于聚类质量较差的聚类成员,应削弱其对目标聚 类的贡献程度。 由聚类综合质量Ocq评价原理可知,Ocq指标从聚类密 集性和分离性两个方面评价聚类结果,并给出一个定量的值 描述聚类质量好坏。因此,我们考虑用Oeq指标对聚类成 员加权。 图2 自组织特征映射聚类集成算法模型 (1)用K-Means算法随机初始化c个聚类中心,重复执行日 次K-Means算法产生Ⅳ个差异性聚类成员1-I=协,尬,…,/t't.t}: (2)对原始数据集进行特征空间变化,生成一个Nxt-t特征 空间矩阵F,将Ⅳ个聚类成员作为特征空间矩阵,的属性: (3)用Ocq指标评价聚类成员的聚类质量,计算聚类成员 的权重向量w岫,并将w岫赋予给特征窄间矩阵尸的各个属性: “)将特征空间矩阵F为SOM网络的输入,经过有限次迭 代后输出聚类集成结果。 4实验结果和分析 实验选用人工数据集,UCI数据集,Web数据集作为测试 数据。3D3K和8D5K数据集是基于高斯函数分布模型随机产 生的人工数据,中间4组是来自于UCI数据集的真实数据, Web数据集是来自标准分类测试文档集Reuters.21578。所有 测试数据集的相关描述如表3所示。 假定单个聚类成员确=l,2,…,劢的Ocq评价结果为 Valueo“00,定义该聚类成员的权重为 垆:毕逝划壹垆:1,wT,>ol ∑Valueo”Orh)u” h=l (8) 数据集 3D3K 8D5K Iris 表3实验测试数据集描述 类犁 人工 人工 UCI UCI UCI UCI ’ 样本个数 300 1000 150 178 10l 214 l000 分类数 3 5 3 3 7 6 8 属性 3 8 4 13 16 9 1214 聚类成员构成的权重向量为w岫=(舻,舻,…,wP)’。通 过Ocq指标加权后,“优秀”聚类成员被赋予较高的权重,“恶 劣”聚类成员被赋予较低的权重。由于日个聚类成员被表示为 新特征空间矩阵的属性,因此,各个聚类成员的权重等价于新 特征空间矩阵的属性权重。 3.3 Wine Zoo Glass SOM聚类集成 原始数据集经过特征空间变化之后,聚类集成问题变成 Web WEB 一个对特征空间矩阵F再聚类的问题。采用SOM算法进行聚 类集成时,直接将特征空间矩阵,作为SOM网络的输入。需 要注意的是,由于考虑了聚类成员的权重,新特征空间的属性 重要性不再相等。在SOM算法迭代过程中,当计算输入向量 与竞争层神经元的加权距离寻求获胜神经元时,将w岫作为新 特征空间的属性权重向量。若用欧式距离定义输入向量与竞 争层神经元的距离,则公式(1)中的距离度量可表示为 设置聚类成员个数日为20,运行Ⅳ次K.Means算法,每次 随机选取数据集的C个聚类中心,c取值如表4所示。SOM算 法对特征空间矩阵进行聚类时,初始学习率为0.9,总迭代次 数为200次,初始邻域半径为整个竞争层网络宽度。实验中 将本文算法和文献【3】中3种基于超图的聚类集成算法CSPA、 HGPA、MCLA、产生聚类成员的K.Means算法以及不进行Oeq 加权直接用SOM算法进行集成的结果进行比较。由于数据 万方数据 4888 2010,31(22) 计算机工程与设计Computer Engineering and Design 表4各种算法的F measlIre值比较 数据集 3D3K 8D5K Iris C K.Mcalls 0.9575 0.8912 O.8436 0.6989 0.7210 0.5278 0.6386 CSPA l 1 0.8678 0.6839 HG队 0.5698 O.2493 0.6479 0.5958 0.6346 0.4410 O.1515 MCLA l l 0.8869 0.7148 0.7656 0.4893 0.6468 加权前CESOM l l 0.8875 O.7148 0.7067 0.5033 0.652l CESOM l l 0.8884 0.7148 0.7051 O.5046 O.6667 3 5 3 3 7 6 8 Wine Zoo Glass 0.62“ 0.4588 0.6007 Web 集真实的类标签信息已知,实验采用外部评价法F measure“田 【2】Fred A L N,Jain A瓦Combining denee multiple elusterings using evi- 011 对6种情况的聚类结果进行评价,表4给出了运行50次后各 种算法在每个数据集上的平均F e瑚saem_。值 accumulation[J].IEEE Transactions Pattern Analysis and Machine Intelligence,2005,27(6):835.850. for detection ofover- 从表4中可看出,除Zoo和Glass数据集外,SOM聚类集 成算法都有效改善了集成前K.Means算法的聚类质量。对于 Glass数据集,所有集成算法都不能得到满意的集成结果,但 SOM聚类集成算法F measure值更接近于K-Means算法。此 外,经过Oeq加权SOM聚类集成算法F_measure值总体上略 高于加权前的结果。在与CSPA、HGPA、MCLA算法的比较中, SOM聚类集成算法总体上优于这3种算法,而MCLA算法在 Zoo数据上表现最好。 【3】Deodhar M,Ghosh J.Consensus clustering Iapping clusters iII microarray of the dm[c].HongKong:Proceedings On Sixth IEEE International Conference Data Mining- Workshops,2006:104-108. 【4】Yang Y,Kamel M,Jin EART-based clustering aggregation[C].At- lanta:lEEE Press,Proceedings of 1EEE on International Conference Granular Compming,2006:482-485. D.Surveyofclustering 【5】Xu R,Wuusch ctions 011 algorithms0].IEEE Transa- 5结束语 本文提出了一种基于自组织特征映射的聚类集成算法 CESOM。该算法将不同的聚类结果表示成一个新特征窄间矩 阵,然后利用聚类综合质量Oeq对新特征窄间矩阵的属性进 行加权,最后将其作为SOM神经网络的输入模式,得到最终 的集成划分。该算法将聚类集成问题简化为一个对聚类结果 二次聚类的问题,具有良好的可理解性和扩展性。实验表明, CESOM算法能够较好地改善聚类质量,且得到了与CSPA, HGPA,MCLA算法同等或更优的聚类效果。 【9】9 【7】 Neural Networks,2005。12(3):645-672. 【6】Kohonen T.Self-organizing neural projections[J】.Neural Net- works,2006,19(6):723-733. 杨燕,靳蕃,Kamel M.聚类有效性评价综述【J】.计算机应用研充 2008,25(6):1630.1632. 【8】Halkidi M,Gunopulos mework based on D,vazirgiannis M,et a1.A and clustering fra- subjective on objective validity criteria[J]. ACM Transactions Knowledge Discovery from Data,2008,1 (4):l一25. He J,Tan A,Tan of generating a 参考文献: 【l】Topchy a,Jain A K,Puneh and weak C.Modified ART 2A growing network capable fi】【ed number of nodes[J].IEEE Transactions On W.Clustering ensembles:Models of oil Neural Networks,2004,15(3):728-737. gonscllSUS partition[J].IEEE Transactions Pattern 【10】杨燕,张昭涛,基于阙值和蚁群算法结合的聚类方法【J】,西南交 通大学学报,2006,41(6):71 9.722. Analysis and Machine Intelligence,2005,27(12):1866-1881. (上接第4884页) 【4】Dussanlt J Pdvlareotte P,Roch the global optimization of a S.et alA smoothing heuristic for [7】 Sakawa M,Nishizaki I,Umura Y.Interactive fuzzy programming class of bilinear bilevel programs formulti?-levellinearprogrammingproblemswithfuzzyparame?? 【EB/OL].http://www.iro.umontreal.ca/-marcotte/ARTIPS/ Smoothing.pdf,2003. 【5】 刘宝碇,赵瑞清,王纲.不确定规划及其应用【M】.北京:清华大学 出版社。2003. ters[J].Fuzzy Sets 【8】 Katagiri ning tree and Systems,2005,109:3-19. H’Sakawa M,Ishii H.Fuzzy random bottle neck span- problems[J】.European Journal of Operational Re- search,2004,152:88-95. satiscing method for 【6】Katagiri H.Sakawa M.A丑interactive fuzzy fuzzy random linear multi objective 0-1 through the 【9】 Osman M sAbd El—Wahed W F,Mcrvat M ket a1.A solution methodology of bi—level linear programming problems programming based on genetic expectation optimization model【C】.Mathematical algorithm[J].Journal 352.359. of Mathematics and Statistics,2009,5“): andComputerModelling,2004:411-421. 万方数据 基于自组织特征映射的聚类集成算法 作者: 作者单位: 刊名: 英文刊名: 年,卷(期): 谭维, 杨燕, TAN Wei, YANG Yan 西南交通大学,信息科学与技术学院,四川,成都,610031 计算机工程与设计 COMPUTER ENGINEERING AND DESIGN 2010,31(22) 参考文献(10条) 1.He J;Tan A;Tan C Modified ART 2A growing network capable of generating a fixed number of nodes[外 文期刊] 2004(03) 2.Halkidi M;Gunopulos D;Vazirgiannis M A clustering framework based on subjective and objective validity criteria[外文期刊] 2008(04) 3.杨燕;靳蓍;Kamel M 聚类有效性评价综述[期刊论文]-计算机应用研究 2008(06) 4.Kohonen T Self-organizing neural projections[外文期刊] 2006(06) 5.Xu R;Wunsch D Survey of clustering aigorithms 2005(03) 6.Yang Y;Kamel M;Jin F ART-based clustering aggregation 2006 7.杨燕;张昭涛 基于阈值和蚁群算法结合的聚类方法[期刊论文]-西南交通大学学报 2006(06) 8.Deodhar M;Ghosh J Consensus clustering for detection of overlapping clusters in microarray data 2006 9.Fred A L N;Jain A K Combining multiple clusterings using evidence accumulation[外文期刊hy A;Jain A K;Punch W Clustering ensembles:Models of consensus and weak partition[外文期刊] 2005(12) 本文链接:

http://donatewale.com/zizuzhiyingshe/29.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有