第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.2016030 网络出版地址：http:/www.cmki.net/kcms/detail/23.1538.TP.20160513.0921.020.html 基于决策加权的聚类集成算法 黄栋，王昌栋23，赖剑煌2,3，梁云1，边山，陈羽 (1.华南农业大学数学与信息学院，广东广州510640：2.中山大学数据科学与计算机学院，广东广州510006：3.广 东省信息安全技术重点实验室，广东广州510006)》 摘要：聚类集成的目标是融合多个聚类成员的信息以得到一个更优、更鲁棒的聚类结果。针对聚类成员可靠度估 计与加权问题，提出了一个基于二部图模型与决策加权机制的聚类集成方法。在该方法中，每个聚类成员被视作一 个包含若干连接决策的集合。每个聚类成员的决策集合享有一个单位的可信度，该可信度由集合内的各个决策共 同分享。基于可信度分享的思想，进一步对各个聚类成员内的决策进行加权，并将此决策加权机制整合至一个统一 的二部图模型：然后利用快速二部图分割算法将该图划分为若干子集，以得到最终聚类结果。实验结果表明，该方 法相较于其他对比方法在聚类效果及运算效率上均表现出显著优势。 关键词：聚类：聚类集成：决策加权：二部图模型：图分割：基聚类：可信度分享：加权集成 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)03-0418-08 中文引用格式：黄栋，王昌栋，赖剑煌，等.基于决策加权的聚类集成算法[J].智能系统学报，2016,11(3)：418-424. 英文引用格式：HUANG Dong,WANG Changdong,LAI Jianhuang,etal.Clustering ensemble by decision weighting[J].CAAI Transactions on Intelligent Systems,2016,11(3):418-424. Clustering ensemble by decision weighting HUANG Dong',WANG Changdong23,LAI Jianhuang2.3,LIANG Yun',BIAN Shan',CHEN Yu' (1.College of Mathematics and Informatics,South China Agricultural University,Guangzhou 510640,China;2.School of Data and Computer Science,Sun Yat-sen University,Guangzhou 510006,China;3.Guangdong Key Laboratory of Information Security Technol- ogy,Guangzhou 510006,China) Abstract:The clustering ensemble technique aims to combine multiple base clusterings to achieve better and more robust clustering results.To evaluate the reliability of the base clusterings and weight them accordingly,in this pa- per,we propose a new clustering ensemble approach based on a bipartite graph formulation and decision weighting strategy.Each base clustering is treated as a bag of decisions,and is assigned one unit of credit.This credit is shared (divided)by all the decisions in one clustering.Using the credit sharing concept,we propose weighting the decisions in the base clusterings with regard to the credit they have.Then,the clustering ensemble problem is for- mulated into a bipartite graph model that incorporates the decision weights,and the final clustering is obtained by rapidly partitioning the bipartite graph.Experimental results have demonstrated the superiority of the proposed algo- rithm in terms of both effectiveness and efficiency. Keywords:clustering;clustering ensemble;decision weighting;bipartite graph formulation;graph partitioning; base clustering;credit sharing;weighted clustering ensemble 聚类集成(clustering ensemble)的目标是融合多 ber)或者基聚类(base clustering);聚类成员可以由 个聚类结果以得到一个更优的最终聚类结果[]。 不同聚类算法生成，或者由一个聚类方法在不同参 每一个输入聚类称为一个聚类成员(ensemble mem- 数设定下生成。聚类成员的质量（或可靠度）是影 响聚类集成性能的关键因素之一。然而，在无监督 收稿日期：2016-03-18.网络出版日期：2016-05-13. 设定下，现有方法大多无法自动评估聚类成员可靠 基金项目：国家自然科学基金项目(61573387,61502543)：广东省自 然科学基金博士启动项目(2016A030310457,2015A030310 度并据此对其加权，从而容易受到低质量聚类成员 450,2014A030310180):广东省科技计划项目(2015A0202 (甚至病态聚类成员)的负面影响。近年来，部分研 09124,2015B010108001):广州市科技计划项目(20150801 究者开始对此进行研究并提出了一些加权聚类集成 0032):中央高校基本科研业务费专项项目(161lgzd15). 通信作者：王昌栋.E-mail:changdongwang(@hotmail.com. 的方法[8，]，但是这些方法往往在集成效果和运算 效率上仍有局限性。例如，文献[11]提出了一种基第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２１．０２０．ｈｔｍｌ 基于决策加权的聚类集成算法 黄栋１ ，王昌栋２，３ ，赖剑煌２，３ ，梁云１ ，边山１ ，陈羽１ （１．华南农业大学 数学与信息学院，广东 广州 ５１０６４０； ２．中山大学 数据科学与计算机学院，广东 广州 ５１０００６； ３．广 东省信息安全技术重点实验室， 广东 广州 ５１０００６） 摘 要：聚类集成的目标是融合多个聚类成员的信息以得到一个更优、更鲁棒的聚类结果。 针对聚类成员可靠度估 计与加权问题，提出了一个基于二部图模型与决策加权机制的聚类集成方法。 在该方法中，每个聚类成员被视作一 个包含若干连接决策的集合。 每个聚类成员的决策集合享有一个单位的可信度，该可信度由集合内的各个决策共 同分享。 基于可信度分享的思想，进一步对各个聚类成员内的决策进行加权，并将此决策加权机制整合至一个统一 的二部图模型；然后利用快速二部图分割算法将该图划分为若干子集，以得到最终聚类结果。 实验结果表明，该方 法相较于其他对比方法在聚类效果及运算效率上均表现出显著优势。 关键词：聚类；聚类集成；决策加权；二部图模型；图分割；基聚类；可信度分享；加权集成 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０４１８⁃０８ 中文引用格式：黄栋，王昌栋，赖剑煌，等．基于决策加权的聚类集成算法［Ｊ］． 智能系统学报， ２０１６， １１（３）： ４１８⁃４２４． 英文引用格式：ＨＵＡＮＧ Ｄｏｎｇ，ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ，ＬＡＩ Ｊｉａｎｈｕａｎｇ， ｅｔ ａｌ． Ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ ｂｙ ｄｅｃｉｓｉｏｎ ｗｅｉｇｈｔｉｎｇ ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ４１８⁃４２４． Ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ ｂｙ ｄｅｃｉｓｉｏｎ ｗｅｉｇｈｔｉｎｇ ＨＵＡＮＧ Ｄｏｎｇ １ ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ ２，３ ， ＬＡＩ Ｊｉａｎｈｕａｎｇ ２，３ ， ＬＩＡＮＧ Ｙｕｎ １ ， ＢＩＡＮ Ｓｈａｎ １ ， ＣＨＥＮ Ｙｕ １ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｃｓ， Ｓｏｕｔｈ Ｃｈｉｎａ Ａｇｒｉｃｕｌｔｕｒａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｇｕａｎｇｚｈｏｕ ５１０６４０， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｄａｔａ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｓｕｎ Ｙａｔ⁃ｓｅｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ； ３． Ｇｕａｎｇｄｏｎｇ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ Ｔｅｃｈｎｏｌ⁃ ｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ ｔｅｃｈｎｉｑｕｅ ａｉｍｓ ｔｏ ｃｏｍｂｉｎｅ ｍｕｌｔｉｐｌｅ ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇｓ ｔｏ ａｃｈｉｅｖｅ ｂｅｔｔｅｒ ａｎｄ ｍｏｒｅ ｒｏｂｕｓｔ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ．Ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｒｅｌｉａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇｓ ａｎｄ ｗｅｉｇｈｔ ｔｈｅｍ ａｃｃｏｒｄｉｎｇｌｙ， ｉｎ ｔｈｉｓ ｐａ⁃ ｐｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａ ｎｅｗ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ａ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｆｏｒｍｕｌａｔｉｏｎ ａｎｄ ｄｅｃｉｓｉｏｎ ｗｅｉｇｈｔｉｎｇ ｓｔｒａｔｅｇｙ． Ｅａｃｈ ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇ ｉｓ ｔｒｅａｔｅｄ ａｓ ａ ｂａｇ ｏｆ ｄｅｃｉｓｉｏｎｓ， ａｎｄ ｉｓ ａｓｓｉｇｎｅｄ ｏｎｅ ｕｎｉｔ ｏｆ ｃｒｅｄｉｔ． Ｔｈｉｓ ｃｒｅｄｉｔ ｉｓ ｓｈａｒｅｄ （ｄｉｖｉｄｅｄ） ｂｙ ａｌｌ ｔｈｅ ｄｅｃｉｓｉｏｎｓ ｉｎ ｏｎｅ ｃｌｕｓｔｅｒｉｎｇ． Ｕｓｉｎｇ ｔｈｅ ｃｒｅｄｉｔ ｓｈａｒｉｎｇ ｃｏｎｃｅｐｔ， ｗｅ ｐｒｏｐｏｓｅ ｗｅｉｇｈｔｉｎｇ ｔｈｅ ｄｅｃｉｓｉｏｎｓ ｉｎ ｔｈｅ ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇｓ ｗｉｔｈ ｒｅｇａｒｄ ｔｏ ｔｈｅ ｃｒｅｄｉｔ ｔｈｅｙ ｈａｖｅ． Ｔｈｅｎ， ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ ｐｒｏｂｌｅｍ ｉｓ ｆｏｒ⁃ ｍｕｌａｔｅｄ ｉｎｔｏ ａ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｍｏｄｅｌ ｔｈａｔ ｉｎｃｏｒｐｏｒａｔｅｓ ｔｈｅ ｄｅｃｉｓｉｏｎ ｗｅｉｇｈｔｓ， ａｎｄ ｔｈｅ ｆｉｎａｌ ｃｌｕｓｔｅｒｉｎｇ ｉｓ ｏｂｔａｉｎｅｄ ｂｙ ｒａｐｉｄｌｙ ｐａｒｔｉｔｉｏｎｉｎｇ ｔｈｅ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｈａｖｅ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈｅ ｓｕｐｅｒｉｏｒｉｔｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏ⁃ ｒｉｔｈｍ ｉｎ ｔｅｒｍｓ ｏｆ ｂｏｔｈ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ． Ｋｅｙｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ； ｄｅｃｉｓｉｏｎ ｗｅｉｇｈｔｉｎｇ； ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｆｏｒｍｕｌａｔｉｏｎ； ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇ； ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇ； ｃｒｅｄｉｔ ｓｈａｒｉｎｇ； ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ 收稿日期：２０１６⁃０３⁃１８． 网络出版日期：２０１６⁃０５⁃１３ 基金项目：国家自然科学基金项目（６１５７３３８７， ６１５０ 聚类集成（ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ）的目标是 通信作者：王昌栋． Ｅ⁃ｍａｉｌ：ｃｈａｎｇｄｏｎｇｗａｎｇ＠ ｈｏｔｍａｉｌ．ｃｏｍ． 融合多 个聚类结果以得到一个更优的最终聚类结果［１⁃１０］ 。 每一个输入聚类称为一个聚类成员（ｅｎｓｅｍｂｌｅ ｍｅｍ⁃ ｂｅｒ）或者基聚类（ ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇ）；聚类成员可以由 不同聚类算法生成，或者由一个聚类方法在不同参 数设定下生成。 聚类成员的质量（或可靠度） 是影 响聚类集成性能的关键因素之一。 然而，在无监督 设定下，现有方法大多无法自动评估聚类成员可靠 度并据此对其加权，从而容易受到低质量聚类成员 （甚至病态聚类成员）的负面影响。 近年来，部分研 究者开始对此进行研究并提出了一些加权聚类集成 的方法［８，１１］ ，但是这些方法往往在集成效果和运算 效率上仍有局限性。 例如，文献［１１］提出了一种基 ． ２５４３）；广东省自 然科学基金博士启动项目(2016A030310457,2015A030310 450,2014A030310180)；广东省科技计划项目(2015A0202 09124,2015B010108001)；广州市科技计划项目(20150801 0032)；中央高校基本科研业务费专项项目(16lgzd15)