第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)
第3期 黄栋，等：基于决策加权的聚类集成算法 419· 于非负矩阵分解的加权聚类集成方法，但该方法的 2-D串编码的一致性度量，并利用0-1半正定规划 非负矩阵分解过程运算负担非常大，基本无法应用 来最大化此一致性度量，以得到中心聚类。 于大数据集；文献[8]提出了一种基于归一化群体 尽管国内外研究者已经提出了许多聚类集成算 认可度指标的加权聚类集成方法，但较高的计算复 法「]，但这些算法大都将各个聚类成员同等对待， 杂度也是限制其更广泛应用的一个重要障碍。在当 缺乏对聚类成员进行可靠度估计及加权的能力，容 前聚类集成研究中，如何高效地对聚类成员的可靠 易受低质量聚类成员（甚至病态聚类成员）的负面 度进行评估并加权集成，仍是一个非常具有挑战性 影响。针对此问题，近年来有研究者提出了一些解 的问题。 决方法[8，。文献[11]提出了一种基于非负矩阵 针对此问题，本文提出了一种基于二部图构造 分解的加权聚类集成方法，在该方法的优化过程中， 和决策加权机制的聚类集成算法。我们将每个聚类 可对各聚类成员的可靠度进行估计并加权：但是，该 成员视作一个包含若干连接决策的集合。每个聚类 方法的非负矩阵分解过程的耗时非常大，使其无法 成员的决策集合享有一个单位的可信度，该可信度 应用于较大数据集。文献[8]利用归一化群体认可 由集合内的各个决策共同分享。进一步，我们根据 度指标对各个聚类成员的可靠度进行估计，并进而 每个聚类成员的每个决策分享得到的可信度进行加 提出了两个加权聚类集成算法；但是归一化群体认 权，并将之整合至一个二部图模型，进而利用快速二 可度指标的计算复杂度较高，使其难以适用于大规 部图分割算法将该图划分为若干块以得到最终聚类 模数据的聚类集成问题。在当前聚类集成研究中， 结果。我们将本文方法及多个对比方法在8个实际 如何有效地、高效地估计聚类成员可靠度并据此加 数据集上进行实验分析，实验结果表明，本文方法相 权集成，进而提高聚类集成性能，仍是一个亟待解决 较于其他对比方法在聚类集成效果及运算效率上均 的挑战性问题。 表现出显著优势。 2基于决策加权的聚类集成算法 1相关研究 2.1问题建模 现有的聚类集成方法，主要可以分为3类：1) 给定一个数据集X={x1,x2,…,xN},其中x:表 基于点对相似性的方法[]：2)基于图分割的方 示X中的第i个数据点，N表示X中数据点的个数。 法1.)；3)基于中心聚类的方法[2,6。 令Ⅱ表示一个包含M个聚类成员的集合，记作 基于点对相似性的方法[4，)根据数据点与数据 Ⅱ={π，π2，…，m“} 点之间在多个聚类成员中属于相同簇的频率来得到 式中π"表示聚类集合Ⅱ中的第m个聚类成员。每 一个共联矩阵，并以该共联矩阵作为相似性矩阵，进 一个聚类成员是对数据集X的一个聚类结果，各个 而采用层次聚类方法得到最终聚类结果。文献[4] 聚类成员可以由不同聚类算法得到，或者由一个聚 最早提出共联矩阵的概念，并提出了线索集聚聚类 类算法在不同初始化和参数设置下运行得到。每个 (evidence accumulation clustering,EAC)方法。文献 聚类成员包含若干个簇，记作 [5]对EAC方法进行扩展，将簇的大小加入考虑， Tm={C,Cg,…,Cm} 提出了概率集聚算法。 式中：C表示聚类成员πm中的第i个簇，n表示π” 基于图分割的方法1，)首先根据聚类集成信息 中簇的个数。每个簇是一个包含若干数据点的集 构造一个图结构，再利用图分割算法将图划分为若 合。根据聚类的性质可知，一个聚类成员内所有簇 干块，进而得到最终的聚类集成结果。文献[1]将 的并集，就是整个数据集，即：U,C=X;同一个聚 聚类集成中的每一个簇视作一条超边，构造得到一 类内的任意两个簇之间的交集为空集，即：Vi≠， 个超图结构，进而可使用METS算法[2或Ncut算 C∩C=。将全体聚类成员的簇的集合表示为 法[]将其分割为若干块，以得到最终聚类结果。 C={C1,C2,…,CN} 基于中心聚类的方法[2，将聚类集成问题建模 式中：C,表示集合C中的第i个簇，N,表示集合C中 为一个最优化问题，其优化目标是寻找一个与所有 制 聚类成员的相似性最大化的聚类结果。中心聚类问 n"。 簇的总数。由其定义可知N= 题是一个NP难问题，因而在全局聚类空间寻找 聚类集成的目标是将聚类集合Ⅱ中各聚类成员 最优解对于较大的数据集是几乎不可行的。针对此 的信息融合得到一个更优、更鲁棒的聚类结果。根据 问题，文献[2]将聚类表示为染色体，并提出利用遗 输入信息的不同，聚类集成问题主要有2种不同的建 传算法求得一个近似解。文献[6]提出一种基于 模方式：第1种建模方式同时以聚类集合Π和数据集
于非负矩阵分解的加权聚类集成方法，但该方法的 非负矩阵分解过程运算负担非常大，基本无法应用 于大数据集；文献［８］提出了一种基于归一化群体 认可度指标的加权聚类集成方法，但较高的计算复 杂度也是限制其更广泛应用的一个重要障碍。 在当 前聚类集成研究中，如何高效地对聚类成员的可靠 度进行评估并加权集成，仍是一个非常具有挑战性 的问题。 针对此问题，本文提出了一种基于二部图构造 和决策加权机制的聚类集成算法。 我们将每个聚类 成员视作一个包含若干连接决策的集合。 每个聚类 成员的决策集合享有一个单位的可信度，该可信度 由集合内的各个决策共同分享。 进一步，我们根据 每个聚类成员的每个决策分享得到的可信度进行加 权，并将之整合至一个二部图模型，进而利用快速二 部图分割算法将该图划分为若干块以得到最终聚类 结果。 我们将本文方法及多个对比方法在 ８ 个实际 数据集上进行实验分析，实验结果表明，本文方法相 较于其他对比方法在聚类集成效果及运算效率上均 表现出显著优势。 １ 相关研究 现有的聚类集成方法，主要可以分为 ３ 类：１） 基于点对相似性的方法［４⁃５］ ；２） 基于图分割的方 法［１，３］ ；３）基于中心聚类的方法［２，６］ 。 基于点对相似性的方法［４，５］ 根据数据点与数据 点之间在多个聚类成员中属于相同簇的频率来得到 一个共联矩阵，并以该共联矩阵作为相似性矩阵，进 而采用层次聚类方法得到最终聚类结果。 文献［４］ 最早提出共联矩阵的概念，并提出了线索集聚聚类 （ｅｖｉｄｅｎｃｅ ａｃｃｕｍｕｌａｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ，ＥＡＣ）方法。 文献 ［５］对 ＥＡＣ 方法进行扩展，将簇的大小加入考虑， 提出了概率集聚算法。 基于图分割的方法［１，３］ 首先根据聚类集成信息 构造一个图结构，再利用图分割算法将图划分为若 干块，进而得到最终的聚类集成结果。 文献［１］ 将 聚类集成中的每一个簇视作一条超边，构造得到一 个超图结构，进而可使用 ＭＥＴＩＳ 算法［１２］ 或 Ｎｃｕｔ 算 法［１３］将其分割为若干块，以得到最终聚类结果。 基于中心聚类的方法［２，６］ 将聚类集成问题建模 为一个最优化问题，其优化目标是寻找一个与所有 聚类成员的相似性最大化的聚类结果。 中心聚类问 题是一个 ＮＰ 难问题［１４］ ，因而在全局聚类空间寻找 最优解对于较大的数据集是几乎不可行的。 针对此 问题，文献［２］将聚类表示为染色体，并提出利用遗 传算法求得一个近似解。 文献［６］ 提出一种基于 ２⁃Ｄ串编码的一致性度量，并利用 ０－１ 半正定规划 来最大化此一致性度量，以得到中心聚类。 尽管国内外研究者已经提出了许多聚类集成算 法［１⁃６］ ，但这些算法大都将各个聚类成员同等对待， 缺乏对聚类成员进行可靠度估计及加权的能力，容 易受低质量聚类成员（甚至病态聚类成员） 的负面 影响。 针对此问题，近年来有研究者提出了一些解 决方法［８，１１］ 。 文献［１１］ 提出了一种基于非负矩阵 分解的加权聚类集成方法，在该方法的优化过程中， 可对各聚类成员的可靠度进行估计并加权；但是，该 方法的非负矩阵分解过程的耗时非常大，使其无法 应用于较大数据集。 文献［８］利用归一化群体认可 度指标对各个聚类成员的可靠度进行估计，并进而 提出了两个加权聚类集成算法；但是归一化群体认 可度指标的计算复杂度较高，使其难以适用于大规 模数据的聚类集成问题。 在当前聚类集成研究中， 如何有效地、高效地估计聚类成员可靠度并据此加 权集成，进而提高聚类集成性能，仍是一个亟待解决 的挑战性问题。 ２ 基于决策加权的聚类集成算法 ２．１ 问题建模 给定一个数据集 Ｘ ＝ ｘ１ ，ｘ２ ，…，ｘＮ { } ，其中ｘｉ 表 示 Ｘ 中的第 ｉ 个数据点，Ｎ 表示 Ｘ 中数据点的个数。 令 Π 表示一个包含 Ｍ 个聚类成员的集合，记作 Π ＝ π １ ，π ２ ，…，π Ｍ { } 式中 π ｍ 表示聚类集合 Π 中的第 ｍ 个聚类成员。 每 一个聚类成员是对数据集 Ｘ 的一个聚类结果，各个 聚类成员可以由不同聚类算法得到，或者由一个聚 类算法在不同初始化和参数设置下运行得到。 每个 聚类成员包含若干个簇，记作 π ｍ ＝ Ｃ ｍ １ ，Ｃ ｍ ２ ，…，Ｃ ｍ { ｎｍ} 式中： Ｃ ｍ ｉ 表示聚类成员π ｍ 中的第 ｉ 个簇，ｎ ｍ 表示π ｍ 中簇的个数。 每个簇是一个包含若干数据点的集 合。 根据聚类的性质可知，一个聚类成员内所有簇 的并集，就是整个数据集，即：∪ｎｍ ｉ ＝ １ Ｃ ｍ ｉ ＝ Ｘ；同一个聚 类内的任意两个簇之间的交集为空集，即：∀ｉ ≠ ｊ， Ｃ ｍ ｉ ∩ Ｃ ｍ ｊ ＝。 将全体聚类成员的簇的集合表示为 Ｃ ＝ Ｃ１ ，Ｃ２ ，…，ＣＮｃ { } 式中： Ｃｉ 表示集合 Ｃ 中的第 ｉ 个簇，Ｎｃ 表示集合 Ｃ 中 簇的总数。 由其定义可知Ｎｃ ＝ ∑ Ｍ ｍ ＝ １ ｎ ｍ 。 聚类集成的目标是将聚类集合 Π 中各聚类成员 的信息融合得到一个更优、更鲁棒的聚类结果。 根据 输入信息的不同，聚类集成问题主要有 ２ 种不同的建 模方式：第１ 种建模方式同时以聚类集合 Π 和数据集 第 ３ 期 黄栋，等：基于决策加权的聚类集成算法 ·４１９·
·420· 智能系统学报 第11卷 X作为输入信息[s):第2种建模方式则只以聚类集 论的直观理解在于，若一个聚类成员作出的连接决 合Ⅱ为输入信息，而不需要访问数据集X中的数据 策数量越小（即越稀有），则其正确率往往越高（即 特征o。两种建模方式的区别就在于除聚类成员 越宝贵)：若其连接决策数量越大，则其决策出错的 的信息之外是否可访问原始数据特征。在聚类集成 比例往往越高。当一个聚类成员将全体数据点都归 研究中，第2种建模方式对原始数据的依赖度更低， 入同一个簇时，其连接决策数达到最大值，此时该聚 亦被更广泛采用o]:本文的聚类集成研究按照第2 类成员的连接决策失去意义。 种建模方式进行，即以聚类集合Ⅱ为输入，不要求访 0.8 问原始数据特征，依此得到最终聚类结果π‘。 2.2决策加权 0.7 在聚类集成问题中，每一个聚类成员可以视作 是一个包含若干个连接决策的集合。如果数据点x: 0.6 和x在聚类成员πm中被划分在同一个簇，那么我 0.5 们称m对xi和x作出了一个连接决策，由此可得 一个簇C∈π"所作出的连接决策的数量为 0.4 (1-1C|)1Cg 米 #Decisions(Cπ)= 2 0.3 0 0.5 1.015 20*10 式中C表示簇C中数据点的个数。进而，可得聚 #Decisions 类成员π"所作出的连接决策的数量，即为π中所有 图1对于MNST数据集，各聚类成员的连接决策数与 簇的连接决策数之和： 正确决策率之间的关系 Fig.1 The relation between #Decisions and RatioCD #Decisions(πm)= ∑#Decisions(C) (1) for the MNIST dataset k= 每个聚类成员包含一定数量的连接决策：聚类 一个聚类成员的正确决策率，是其对于数据点两 成员的可靠度估计与加权问题，可视作是对聚类成 两之间处于同一个簇的判断的正确比例，可视作该聚 员连接决策的可靠度估计与加权问题。我们在实例 类成员的可靠度。由于聚类决策数与可靠度的负相 研究中发现，聚类成员的可靠度与其连接决策总数 关关系，为减小低可靠度决策的不良影响以提高聚类 存在显著的负相关关系。 集成鲁棒性，一个可行策略是采取权值与聚类决策数 具体地，我们以MNIST数据集[1)为例。该数 负相关的加权集成方案。在本文中，我们对每个聚类 据集包含5000个数据点。我们使用k均值聚类算 成员分配一个单位的可信度，该可信度由聚类成员内 法为该数据集生成100个聚类成员，每次生成均采 的全体决策共同分享。那么，聚类成员π"中每个连 用随机聚类个数及随机初始化。如果两个数据点x: 接决策分享到的可信度是l/#Decisions(πm)个单位。 和x:在聚类成员πm中被划分在同一个簇，并且这 根据各个聚类成员中连接决策的平均可信度对其加 两个数据点在MNIST数据集的真实类别中也属于 权，则聚类成员πm的权值计算公式为 同一个类，那么称聚类成员πm对数据点x:和x作 1 出了一个正确决策，并将π"作出的正确决策的数 花（πm)= #Decisions(m) 量记作#CorrectDecisions(πm)。我们将聚类成员m" 1 作出的所有连接决策中正确决策所占的比例，称为 #Decisions( 正确决策率，记作RatioCD(πm),计算公式为 进而可得： RatioCD(#CorrectDecisions() 1 (2) 10(πm)= #Decisions(π") 图1显示了MNIST数据集的1O0个聚类成员 Deciston(r)∑Decision( 的连接决策数与正确决策率之间的关系。对每一个 (3) 聚类成员，根据式(1)计算其连接决策数，根据式 由定义可知，全体聚类成员的权值之和为1，即 (2)计算其正确决策率，从而在图1中描出对应的 (r）=1 坐标点。由图1可以看到，聚类成员的连接决策数 m=1 与其正确决策率存在显著的负相关关系。此实验结 2.3二部图构造与聚类集成 在聚类成员可靠度分析与权值分配的基础上
Ｘ 作为输入信息［１５⁃１７］ ；第 ２ 种建模方式则只以聚类集 合 Π 为输入信息，而不需要访问数据集 Ｘ 中的数据 特征［１⁃１０］ 。 两种建模方式的区别就在于除聚类成员 的信息之外是否可访问原始数据特征。 在聚类集成 研究中，第 ２ 种建模方式对原始数据的依赖度更低， 亦被更广泛采用［１⁃１０］ ；本文的聚类集成研究按照第 ２ 种建模方式进行，即以聚类集合 Π 为输入，不要求访 问原始数据特征，依此得到最终聚类结果π ∗ 。 ２．２ 决策加权 在聚类集成问题中，每一个聚类成员可以视作 是一个包含若干个连接决策的集合。 如果数据点 ｘｉ 和 ｘｊ在聚类成员 π ｍ 中被划分在同一个簇，那么我 们称 πｍ 对 ｘｉ 和 ｘｊ 作出了一个连接决策，由此可得 一个簇 Ｃ ｍ ｋ ∈π ｍ 所作出的连接决策的数量为 ＃Ｄｅｃｉｓｉｏｎｓ（Ｃ ｍ ｋ ） ＝ （１ － Ｃ ｍ ｋ ） Ｃ ｍ ｋ ２ 式中 Ｃ ｍ ｋ 表示簇Ｃ ｍ ｋ 中数据点的个数。 进而，可得聚 类成员π ｍ所作出的连接决策的数量，即为π ｍ中所有 簇的连接决策数之和： ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ） ＝ ∑ ｎｍ ｋ ＝ １ ＃Ｄｅｃｉｓｉｏｎｓ（Ｃ ｍ ｋ ） （１） 每个聚类成员包含一定数量的连接决策；聚类 成员的可靠度估计与加权问题，可视作是对聚类成 员连接决策的可靠度估计与加权问题。 我们在实例 研究中发现，聚类成员的可靠度与其连接决策总数 存在显著的负相关关系。 具体地，我们以 ＭＮＩＳＴ 数据集［１８］ 为例。 该数 据集包含 ５ ０００ 个数据点。 我们使用 ｋ 均值聚类算 法为该数据集生成 １００ 个聚类成员，每次生成均采 用随机聚类个数及随机初始化。 如果两个数据点 ｘｉ 和 ｘｊ 在聚类成员 π ｍ 中被划分在同一个簇，并且这 两个数据点在 ＭＮＩＳＴ 数据集的真实类别中也属于 同一个类，那么称聚类成员 π ｍ 对数据点 ｘｉ 和 ｘｊ 作 出了一个正确决策，并将 π ｍ 作出的正确决策的数 量记作＃ＣｏｒｒｅｃｔＤｅｃｉｓｉｏｎｓ（π ｍ ）。 我们将聚类成员 π ｍ 作出的所有连接决策中正确决策所占的比例，称为 正确决策率，记作 ＲａｔｉｏＣＤ（π ｍ ），计算公式为 ＲａｔｉｏＣＤ π ｍ ( ) ＝ ＃ＣｏｒｒｅｃｔＤｅｃｉｓｉｏｎｓ（π ｍ ） ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ） （２） 图 １ 显示了 ＭＮＩＳＴ 数据集的 １００ 个聚类成员 的连接决策数与正确决策率之间的关系。 对每一个 聚类成员，根据式（１） 计算其连接决策数，根据式 （２）计算其正确决策率，从而在图 １ 中描出对应的 坐标点。 由图 １ 可以看到，聚类成员的连接决策数 与其正确决策率存在显著的负相关关系。 此实验结 论的直观理解在于，若一个聚类成员作出的连接决 策数量越小（即越稀有），则其正确率往往越高（即 越宝贵）；若其连接决策数量越大，则其决策出错的 比例往往越高。 当一个聚类成员将全体数据点都归 入同一个簇时，其连接决策数达到最大值，此时该聚 类成员的连接决策失去意义。 图 １ 对于 ＭＮＩＳＴ 数据集，各聚类成员的连接决策数与 正确决策率之间的关系 Ｆｉｇ．１ Ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ＃ Ｄｅｃｉｓｉｏｎｓ ａｎｄ ＲａｔｉｏＣＤ ｆｏｒ ｔｈｅ ＭＮＩＳＴ ｄａｔａｓｅｔ 一个聚类成员的正确决策率，是其对于数据点两 两之间处于同一个簇的判断的正确比例，可视作该聚 类成员的可靠度。 由于聚类决策数与可靠度的负相 关关系，为减小低可靠度决策的不良影响以提高聚类 集成鲁棒性，一个可行策略是采取权值与聚类决策数 负相关的加权集成方案。 在本文中，我们对每个聚类 成员分配一个单位的可信度，该可信度由聚类成员内 的全体决策共同分享。 那么，聚类成员π ｍ中每个连 接决策分享到的可信度是 １／ ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ）个单位。 根据各个聚类成员中连接决策的平均可信度对其加 权，则聚类成员 π ｍ 的权值计算公式为 ｗ π ｍ ( ) ＝ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ） ∑ Ｍ ｋ ＝ １ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｋ ） 进而可得： ｗ π ｍ ( ) ＝ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ）∑ Ｍ ｋ ＝ １ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｋ ） （３） 由定义可知，全体聚类成员的权值之和为 １，即 ∑ Ｍ ｍ ＝ １ ｗ π ｍ ( ) ＝ １ ２．３ 二部图构造与聚类集成 在聚类成员可靠度分析与权值分配的基础上， ·４２０· 智 能 系 统 学 报 第 １１ 卷
第3期 黄栋，等：基于决策加权的聚类集成算法 ·421· 我们将进一步将聚类集成问题构造为一个二部图模 是Glass、Ecoli、Image Segmentation(IS)、MNIST 型。在所构造的二部图模型中，聚类集合中各个聚 ISOLET、Pen Digits(PD)、USPS以及Letter Recog- 类成员的簇与数据点同时作为节点。簇节点与簇节 nition(LR)。其中，除MNIST数据集来自于文献 点之间不存在连接边：数据点节点与数据点节点之 [18]之外，其他7个数据集均来自于UCI机器学习 间亦不存在连接边。两个节点之间存在连接边，当 数据仓库(UCI machine learning repository)【o。所 且仅当其中一个节点是数据点节点，另一个节点是 用的测试数据集的具体情况如表1所示。 簇节点，并且该数据点位于该簇之内。边的权值由 表1实验数据集 该簇所在的聚类成员的权值决定（见式(3）)。由 Table 1 Description of datasets 此，可得到一个二部图结构，其左部为数据点节点的 数据集 数据点数 维度 类别数 集合，右部为簇节点的集合。我们将该二部图结构 Glass 214 9 7 表示为 Ecoli 336 7 8 G=(U,V,E) 9 2310 19 7 式中：U=X表示左部节点集（数据点集合），V=C表 示右部节点集（簇集合），E表示边的集合。给定两 MNIST 5000 784 10 个节点u,和v,两者之间的边的权值定义为 ISOLET 7797 617 26 (w(T()), :∈X,y∈C,4:∈ PD 10992 16 10 e= 0. 否则 USPS 11000 256 10 式中：π(e)表示簇U所在的聚类成员，即如果巴∈ LR 20000 16 26 π，则T(u)=π。 3.2实验设置与评价指标 接下来，利用图G的二部图结构，我们采用 在本文实验中，我们首先需要生成一个包含若 Tcut算法[1将图G快速地分割为若千块，进而将每 干聚类成员的聚类集合，以对比分析本文方法以及 一块中数据点集合作为最终聚类的一个簇，由此可 其他聚类集成方法的聚类效果。具体地，我们在每 以得到最终聚类结果。 一次运行中使用k均值聚类算法生成M个聚类成 2.4时间复杂度 员，每一个聚类成员的生成均采用随机初始化，并在 第2.3节所构造的二部图G包含有N+N。个节 区间[2，√厅]中随机选取初始聚类个数k。对于 点，其中N是数据点个数，Nc是簇个数。如果使用 每一个方法在每一个数据集上的实验，我们均运行 经典的Ncut算法[9)对图G进行分割，其时间复杂 10次（每次使用随机生成的聚类集合，如前所述）， 度是O(k(N+N)32),其中k是图分割的块数。与 然后得到各个方法的平均性能得分，以实现客观公 之相比，本文采用的Tcut算法[9)可利用图G的二 平的对比与分析。 部图结构，进行快速图分割，其时间复杂度是 我们将聚类成员个数M称为聚类集成规模：将 O(kWN+kN2):考虑式(3)中权值计算的复杂度是 数据集的数据点数N称为数据规模。在后续实验 O(N),故本文总体算法的时间复杂度即是 中，我们首先固定聚类集成规模M=10,接下来分别 O(kW+kN)。由于在实际聚类问题中数据点个 进行本文方法与聚类成员以及与其他聚类集成方法 数N通常远大于簇个数N。,因此使用Tcut算法相当 的对比实验，并进一步测试在不同聚类集成规模M 于可使时间复杂度由O(kN2)降低至O(kN)。当 下各个聚类集成方法的聚类表现。最后，将对比测 面对大数据集时，本文算法在运算效率上的优势尤 试各个聚类集成方法的运算效率。在本文实验中， 其显著；在本文后续的对比实验中，本文聚类集成算 采用标准互信息量(normalized mutual information, 法相比于现有算法的效率优势也得到了验证。 NMI)山作为评价指标。NMI可根据两个聚类之间 3 实验结果与分析 的互信息量来度量其相似性，是聚类研究中被广泛 应用的一个评价指标。一个聚类结果（与真实聚类 在本节中，我们将在多个实际数据集中进行实 比较)的NMI值越大，则表示其聚类质量越好。 验，与若干现有聚类集成算法进行对比分析，以验证 3.3与聚类成员的对比实验 本文方法的有效性及运算效率。 聚类集成的目标是融合多个聚类成员的信息以 3.1数据集 期得到一个更优聚类。在本节中，我们将本文方法 本文的实验一共使用了8个实际数据集，分别 的聚类集成结果，与聚类成员进行对比实验。在每
我们将进一步将聚类集成问题构造为一个二部图模 型。 在所构造的二部图模型中，聚类集合中各个聚 类成员的簇与数据点同时作为节点。 簇节点与簇节 点之间不存在连接边；数据点节点与数据点节点之 间亦不存在连接边。 两个节点之间存在连接边，当 且仅当其中一个节点是数据点节点，另一个节点是 簇节点，并且该数据点位于该簇之内。 边的权值由 该簇所在的聚类成员的权值决定（见式（３））。 由 此，可得到一个二部图结构，其左部为数据点节点的 集合，右部为簇节点的集合。 我们将该二部图结构 表示为 Ｇ ＝ （Ｕ，Ｖ，Ｅ） 式中：Ｕ＝Ｘ 表示左部节点集（数据点集合），Ｖ ＝ Ｃ 表 示右部节点集（簇集合），Ｅ 表示边的集合。 给定两 个节点ｕｉ和ｖｊ，两者之间的边的权值定义为 ｅｉｊ ＝ ｗ π ｖｊ ( ( ) ) ， ｕｉ ∈ Ｘ，ｖｊ ∈ Ｃ，ｕｉ ∈ ｖｊ {０， 否则 式中：π ｖｊ ( ) 表示簇ｖｊ 所在的聚类成员，即如果ｖｊ ∈ π ｍ ，则 π ｖｊ ( ) ＝π ｍ 。 接下来，利用图 Ｇ 的二部图结构， 我们采用 Ｔｃｕｔ 算法［１９］将图 Ｇ 快速地分割为若干块，进而将每 一块中数据点集合作为最终聚类的一个簇，由此可 以得到最终聚类结果。 ２．４ 时间复杂度 第 ２．３ 节所构造的二部图 Ｇ 包含有 Ｎ＋Ｎｃ 个节 点，其中 Ｎ 是数据点个数，Ｎｃ 是簇个数。 如果使用 经典的 Ｎｃｕｔ 算法［１９］ 对图 Ｇ 进行分割，其时间复杂 度是Ｏ ｋ Ｎ＋Ｎｃ ( ) ３／ ２ ( ) ，其中 ｋ 是图分割的块数。 与 之相比，本文采用的 Ｔｃｕｔ 算法［１９］ 可利用图 Ｇ 的二 部图 结 构， 进 行 快 速 图 分 割， 其 时 间 复 杂 度 是 Ｏ ｋＮ＋ｋ Ｎｃ ３／ ２ ( ) ；考虑式（３）中权值计算的复杂度是 Ｏ (Ｎ) ， 故 本 文 总 体 算 法 的 时 间 复 杂 度 即 是 Ｏ ｋＮ＋ｋ Ｎｃ ３／ ２ ( ) 。 由于在实际聚类问题中数据点个 数 Ｎ 通常远大于簇个数Ｎｃ，因此使用 Ｔｃｕｔ 算法相当 于可使时间复杂度由 Ｏ ｋ Ｎ ３／ ２ ( ) 降低至 Ｏ(ｋＮ) 。 当 面对大数据集时，本文算法在运算效率上的优势尤 其显著；在本文后续的对比实验中，本文聚类集成算 法相比于现有算法的效率优势也得到了验证。 ３ 实验结果与分析 在本节中，我们将在多个实际数据集中进行实 验，与若干现有聚类集成算法进行对比分析，以验证 本文方法的有效性及运算效率。 ３．１ 数据集 本文的实验一共使用了 ８ 个实际数据集，分别 是 Ｇｌａｓｓ、 Ｅｃｏｌｉ、 Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ （ ＩＳ）、 ＭＮＩＳＴ、 ＩＳＯＬＥＴ、 Ｐｅｎ Ｄｉｇｉｔｓ（ＰＤ）、 ＵＳＰＳ 以及 Ｌｅｔｔｅｒ Ｒｅｃｏｇ⁃ ｎｉｔｉｏｎ（ ＬＲ）。 其中，除 ＭＮＩＳＴ 数据集来自于文献 ［１８］之外，其他 ７ 个数据集均来自于 ＵＣＩ 机器学习 数据仓库（ＵＣＩ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ） ［２０］ 。 所 用的测试数据集的具体情况如表 １ 所示。 表 １ 实验数据集 Ｔａｂｌｅ １ Ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｄａｔａｓｅｔｓ 数据集 数据点数 维度 类别数 Ｇｌａｓｓ ２１４ ９ ７ Ｅｃｏｌｉ ３３６ ７ ８ ＩＳ ２ ３１０ １９ ７ ＭＮＩＳＴ ５ ０００ ７８４ １０ ＩＳＯＬＥＴ ７ ７９７ ６１７ ２６ ＰＤ １０ ９９２ １６ １０ ＵＳＰＳ １１ ０００ ２５６ １０ ＬＲ ２０ ０００ １６ ２６ ３．２ 实验设置与评价指标 在本文实验中，我们首先需要生成一个包含若 干聚类成员的聚类集合，以对比分析本文方法以及 其他聚类集成方法的聚类效果。 具体地，我们在每 一次运行中使用 ｋ 均值聚类算法生成 Ｍ 个聚类成 员，每一个聚类成员的生成均采用随机初始化，并在 区间 [２， Ｎ ] 中随机选取初始聚类个数 ｋ。 对于 每一个方法在每一个数据集上的实验，我们均运行 １０ 次（每次使用随机生成的聚类集合，如前所述）， 然后得到各个方法的平均性能得分，以实现客观公 平的对比与分析。 我们将聚类成员个数 Ｍ 称为聚类集成规模；将 数据集的数据点数 Ｎ 称为数据规模。 在后续实验 中，我们首先固定聚类集成规模 Ｍ ＝ １０，接下来分别 进行本文方法与聚类成员以及与其他聚类集成方法 的对比实验，并进一步测试在不同聚类集成规模 Ｍ 下各个聚类集成方法的聚类表现。 最后，将对比测 试各个聚类集成方法的运算效率。 在本文实验中， 采用标准互信息量（ ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ， ＮＭＩ） ［１］作为评价指标。 ＮＭＩ 可根据两个聚类之间 的互信息量来度量其相似性，是聚类研究中被广泛 应用的一个评价指标。 一个聚类结果（与真实聚类 比较）的 ＮＭＩ 值越大，则表示其聚类质量越好。 ３．３ 与聚类成员的对比实验 聚类集成的目标是融合多个聚类成员的信息以 期得到一个更优聚类。 在本节中，我们将本文方法 的聚类集成结果，与聚类成员进行对比实验。 在每 第 ３ 期 黄栋，等：基于决策加权的聚类集成算法 ·４２１·
.422 智能系统学报 第11卷 个数据集上均测试10次：每次测试均随机生成一个 USPS等数据集，本文方法相较聚类成员优势更 包含M个聚类成员的聚类集合，然后在此聚类集合 显著。 上运行本文算法以得到一个集成聚类结果。由此， 3.4聚类集成方法的对比实验 得到本文方法在10次运行测试中的平均表现以及 本节将所提出方法与6个现有的聚类集成方法 聚类成员的平均表现（以NMI度量）。如图2所示。 进行对比实验。这6个对比方法分别是evidence accumulation clustering (EAC)hybrid bipartite 0.9 本文方法 graph formulation (HBGF)SimRank similarity 0.8 口聚类成员 based method (SRS)weighted connected triple 0.7 based method(WCT)[2],weighted evidence accumula- 0.6 tion clustering(WEAC)sgraph partitioning with multi-granularity link analysis(GP-MGLA)[8] 0.5 在每一个数据集中，每个聚类集成方法均运行 0.4 10次，每次运行根据第3.2节所述随机生成聚类成 0.3 员，进而得到每个算法在每个数据集的平均NMI得 0.2 分及其标准差。在表2中，在每一个数据集中，最高 Glass Ecoli IS MNISTISOLETPD USPS LR NM得分以粗体显示。如表2所示，本文方法在8 个数据集上均取得了优于其他聚类集成方法的聚类 图2本文方法与聚类成员的性能对比 Fig.2 Comparison between our method and the base 效果，特别是在Glass、MNIST和USPS数据集上，本 clusterings 文方法取得的平均NMI得分比其他方法高出10% 本文方法可取得比聚类成员更好的聚类结果： 左右。表2的对比实验结果验证了本文方法在聚类 尤其是在Glass、Ecoli、IS、MNIST、PD、 集成效果上的优势。 表2本文方法与其他聚类集成方法的对比实验 Table 2 The average performances of different methods 测试方法 Glass Ecoli IS MNIST ISOLET PD USPS LR 本文方法 0.463 0.682 0.641 0.653 0.756 0.787 0.632 0.454 EACt4] 0.418 0.640 0.618 0.592 0.746 0.747 0.580 0.435 HBGF ( 0.397 0.635 0.624 0.609 0.747 0.757 0.588 0.441 SRS [21] 0.423 0.632 0.623 0.594 0.747 0.755 0.593 0.436 WCT [z) 0.434 0.678 0.623 0.627 0.752 0.764 0.598 0.439 WEAC [s] 0.409 0.637 0.616 0.607 0.746 0.752 0.581 0.439 GP-MGLA[8) 0.399 0.640 0.634 0.624 0.747 0.758 0.602 0.441 3.5在不同聚类集成规模下的对比实验 间对比实验。所有实验均在MATLAB2014h下运行， 接下来，我们进行本文方法与其他对比方法在不所使用的工作站配置具体如下：Windows Server2008 同聚类集成规模（即聚类成员个数）下的对比实验。R264位操作系统：英特尔八核心2.4GHz中央处理 当聚类集成规模由M=10增长到50时，各个聚类集器：96GB内存。为求客观对比各个算法运行的CPU 成方法在10次运行中的平均NM得分如图3所示。时间，所有实验均在单线程模式下运行。 在Ecoli数据集中，WCT方法取得了与本文方法基本 为测试各个聚类集成算法在不同数据规模（即 相当的性能表现。除了Ecoi数据集之外，在其他7数据点个数)下的运行时间，本节实验在LR数据集 个数据集中，本文方法在不同聚类集成规模下的聚类的不同大小的子集上进行。LR数据集一共包含有2 表现均显著优于其他方法。图3的实验结果验证了万个数据点：我们在实验中所测试的子集大小从0逐 本文方法在不同聚类集成规模下表现出比其他聚类步增长至20000。例如，当测试数据规模设定为W'∈ 集成方法更好的鲁棒性。 [0,20000]时，我们就随机从整个LR数据集中选取 3.6运行时间 N'个数据点进行实验，并记录各个测试方法在此数据 在本节中，我们进行各个聚类集成方法的运行时规模上的运行时间。如图4所示，当数据规模较小
个数据集上均测试 １０ 次；每次测试均随机生成一个 包含 Ｍ 个聚类成员的聚类集合，然后在此聚类集合 上运行本文算法以得到一个集成聚类结果。 由此， 得到本文方法在 １０ 次运行测试中的平均表现以及 聚类成员的平均表现（以 ＮＭＩ 度量）。 如图 ２ 所示。 图 ２ 本文方法与聚类成员的性能对比 Ｆｉｇ．２ Ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ ｏｕｒ ｍｅｔｈｏｄ ａｎｄ ｔｈｅ ｂａｓｅ ｃｌｕｓｔｅｒｉｎｇｓ 本文方法可取得比聚类成员更好的聚类结果； 尤其是在 Ｇｌａｓｓ、Ｅｃｏｌｉ、 ＩＳ、ＭＮＩＳＴ、ＰＤ、 ＵＳＰＳ 等数据集，本文方法相较聚类成员优势更 显著。 ３．４ 聚类集成方法的对比实验 本节将所提出方法与 ６ 个现有的聚类集成方法 进行对比实验。 这 ６ 个对比方法分别是 ｅｖｉｄｅｎｃｅ ａｃｃｕｍｕｌａｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ （ ＥＡＣ ） ［４］ 、 ｈｙｂｒｉｄ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｆｏｒｍｕｌａｔｉｏｎ （ ＨＢＧＦ ） ［３］ 、 ＳｉｍＲａｎｋ ｓｉｍｉｌａｒｉｔｙ ｂａｓｅｄ ｍｅｔｈｏｄ （ ＳＲＳ ） ［２１］ 、 ｗｅｉｇｈｔｅｄ ｃｏｎｎｅｃｔｅｄ ｔｒｉｐｌｅ ｂａｓｅｄ ｍｅｔｈｏｄ（ＷＣＴ） ［２２］ 、ｗｅｉｇｈｔｅｄ ｅｖｉｄｅｎｃｅ ａｃｃｕｍｕｌａ⁃ ｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ（ＷＥＡＣ） ［８］以及 ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇ ｗｉｔｈ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｌｉｎｋ ａｎａｌｙｓｉｓ（ＧＰ⁃ＭＧＬＡ） ［８］ 。 在每一个数据集中，每个聚类集成方法均运行 １０ 次，每次运行根据第 ３．２ 节所述随机生成聚类成 员，进而得到每个算法在每个数据集的平均 ＮＭＩ 得 分及其标准差。 在表 ２ 中，在每一个数据集中，最高 ＮＭＩ 得分以粗体显示。 如表 ２ 所示，本文方法在 ８ 个数据集上均取得了优于其他聚类集成方法的聚类 效果，特别是在 Ｇｌａｓｓ、ＭＮＩＳＴ 和 ＵＳＰＳ 数据集上，本 文方法取得的平均 ＮＭＩ 得分比其他方法高出 １０％ 左右。 表 ２ 的对比实验结果验证了本文方法在聚类 集成效果上的优势。 表 ２ 本文方法与其他聚类集成方法的对比实验 Ｔａｂｌｅ ２ Ｔｈｅ ａｖｅｒａｇｅ ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｍｅｔｈｏｄｓ 测试方法 Ｇｌａｓｓ Ｅｃｏｌｉ ＩＳ ＭＮＩＳＴ ＩＳＯＬＥＴ ＰＤ ＵＳＰＳ ＬＲ 本文方法 ０．４６３ ０．６８２ ０．６４１ ０．６５３ ０．７５６ ０．７８７ ０．６３２ ０．４５４ ＥＡＣ ［４］ ０．４１８ ０．６４０ ０．６１８ ０．５９２ ０．７４６ ０．７４７ ０．５８０ ０．４３５ ＨＢＧＦ ［３］ ０．３９７ ０．６３５ ０．６２４ ０．６０９ ０．７４７ ０．７５７ ０．５８８ ０．４４１ ＳＲＳ ［２１］ ０．４２３ ０．６３２ ０．６２３ ０．５９４ ０．７４７ ０．７５５ ０．５９３ ０．４３６ ＷＣＴ ［２２］ ０．４３４ ０．６７８ ０．６２３ ０．６２７ ０．７５２ ０．７６４ ０．５９８ ０．４３９ ＷＥＡＣ ［８］ ０．４０９ ０．６３７ ０．６１６ ０．６０７ ０．７４６ ０．７５２ ０．５８１ ０．４３９ ＧＰ－ＭＧＬＡ ［８］ ０．３９９ ０．６４０ ０．６３４ ０．６２４ ０．７４７ ０．７５８ ０．６０２ ０．４４１ ３．５ 在不同聚类集成规模下的对比实验 接下来，我们进行本文方法与其他对比方法在不 同聚类集成规模（即聚类成员个数）下的对比实验。 当聚类集成规模由 Ｍ ＝ １０ 增长到 ５０ 时，各个聚类集 成方法在 １０ 次运行中的平均 ＮＭＩ 得分如图 ３ 所示。 在 Ｅｃｏｌｉ 数据集中，ＷＣＴ 方法取得了与本文方法基本 相当的性能表现。 除了 Ｅｃｏｌｉ 数据集之外，在其他 ７ 个数据集中，本文方法在不同聚类集成规模下的聚类 表现均显著优于其他方法。 图 ３ 的实验结果验证了 本文方法在不同聚类集成规模下表现出比其他聚类 集成方法更好的鲁棒性。 ３．６ 运行时间 在本节中，我们进行各个聚类集成方法的运行时 间对比实验。 所有实验均在 ＭＡＴＬＡＢ ２０１４ｂ 下运行， 所使用的工作站配置具体如下：Ｗｉｎｄｏｗｓ Ｓｅｒｖｅｒ ２００８ Ｒ２ ６４ 位操作系统；英特尔八核心 ２．４ ＧＨｚ 中央处理 器；９６ ＧＢ 内存。 为求客观对比各个算法运行的 ＣＰＵ 时间，所有实验均在单线程模式下运行。 为测试各个聚类集成算法在不同数据规模（即 数据点个数）下的运行时间，本节实验在 ＬＲ 数据集 的不同大小的子集上进行。 ＬＲ 数据集一共包含有 ２ 万个数据点；我们在实验中所测试的子集大小从 ０ 逐 步增长至 ２０ ０００。 例如，当测试数据规模设定为Ｎ′∈ [０，２０ ０００] 时，我们就随机从整个 ＬＲ 数据集中选取 Ｎ′个数据点进行实验，并记录各个测试方法在此数据 规模上的运行时间。 如图 ４ 所示，当数据规模较小 ·４２２· 智 能 系 统 学 报 第 １１ 卷
第3期 黄栋，等：基于决策加权的聚类集成算法 .423. 时，HBGF、EAC、WEAC以及本文方法均有较高运算 效率。而当数据规模继续增长时，本文方法相对于其 。一本文方法米一EAC日一HBGF e—SRS -4-WCT-★-WEAC 他方法的效率优势开始变大。对于整个LR数据集 -·A-GP-MGLA 20000个数据点的规模，本文方法仅需要6.19s:除本 0.77 文方法之外，其他对比方法之中最快的3个方法 (HBGF、EAC和WEAC)则分别需要12.18、34.48和 是076 33.87s的运算时间。图4验证了本文方法的优势。 0.75 ◆一本文方法米一EAC一日一HBGF 040 10 2030405060 SRS-WCT.-WEAC 聚类集成规模 0.50r --A-GP-MGLA (e)ISOLET ●一本文方法米一EAC -e-HBGF 0.45 -.-WCT -·★-WEAC-a-GP-MGLA 0.80r 0.40 0.78 0.35 0 10203040 5060 0.76 聚类集成规模 (a)Glass ●一本文方法米一EAC日一HBGF 0740 10 203040 5060 e一SRS-g-WCT-★-WEAC 聚类集成规模 --A-GP-MGLA 0.70r (f)PD 差065 美d ●一本文方法米一EACB一HBGF 一米 --4.-WCT -★-WEAC-A-GP-MGLA 0.40 0.65 0 10203040 5060 聚类集成规模 (b)Ecoli ●一本文方法米一EACB一HBGF 0.60 年 o-SRS-g-WCT-★-WEAC --A-GP-MGLA 0.66r ●●● 0.64 .A 0.55 0 10203040 50 60 差062 聚类集成规模 0.60 (g)USPS 0.58 0102030405060 聚类集成规模 一●一本文方法米一EAC B一HBGF (c)IS ----WCT -★-WEAC-a-GP-MGLA ●一本文方法米一EAC一B一HBGF 0.50r SRS -4-WCT-★-WEAC 0.70r --A.-GP-MGLA 0.45 0.44 0.65 米一 0.43 0 203040 5060 0.60 聚类集成规模 (h)LR 0.55 0 10 203040 5060 图3各个方法的聚类集成性能 聚类集成规模 Fig.3 The performances of different clustering ensem- (d)MNIST ble methods with varying ensemble sizes
时，ＨＢＧＦ、ＥＡＣ、ＷＥＡＣ 以及本文方法均有较高运算 效率。 而当数据规模继续增长时，本文方法相对于其 他方法的效率优势开始变大。 对于整个 ＬＲ 数据集 ２０ ０００ 个数据点的规模，本文方法仅需要６．１９ ｓ；除本 文方法之外，其他对比方法之中最快的 ３ 个方法 （ＨＢＧＦ、ＥＡＣ 和 ＷＥＡＣ）则分别需要 １２．１８、３４．４８ 和 ３３．８７ ｓ 的运算时间。 图 ４ 验证了本文方法的优势。 （ａ）Ｇｌａｓｓ （ｂ）Ｅｃｏｌｉ （ｃ）ＩＳ （ｄ）ＭＮＩＳＴ （ｅ）ＩＳＯＬＥＴ （ｆ）ＰＤ （ｇ）ＵＳＰＳ （ｈ）ＬＲ 图 ３ 各个方法的聚类集成性能 Ｆｉｇ．３ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍ⁃ ｂｌｅ ｍｅｔｈｏｄｓ ｗｉｔｈ ｖａｒｙｉｎｇ ｅｎｓｅｍｂｌｅ ｓｉｚｅｓ 第 ３ 期 黄栋，等：基于决策加权的聚类集成算法 ·４２３·
.424. 智能系统学报 第11卷 100 sing evidence accumulation.IEEE transactions on pattern 一米一本文方法 analysis and machine intelligence,2005,27(6):835-850. -eEAC 80 X一HBGF -SRS 0 [5]WANG Xi,YANG Chunyu,ZHOU Jie.Clustering aggrega- 米 -·米-WCT tion by probability accumulation[J].Pattern recognition, -米-WEAC 60 -·e-GP-MGLA 2009,42(5):668-675 [6]SINGH V,MUKHERJEE L,PENG Jiming,et al.Ensemble % -8.0. 米 clustering using semidefinite programming with applications [J].Machine learning,2010.79(1/2):177-200. [7]HUANG Dong,LAI Jianhuang,WANG Changdong.Exploi- 杀举 米 ×109 ting the wisdom of crowd:a multi-granularity approach to 0.5 1.0 1.5 2.0 clustering ensemble[C]//Proceedings of the 4th Internation- 数据规模 al Conference on Intelligence Science and Big Data Engineer- (h)LR ing.Beijing,China,2013:112-119. 图4各个聚类集成方法在不同数据规模下的运行时间 [8]HUANG Dong,LAI Jianhuang,WANG Changdong.Combi- 对比 ning multiple clusterings via crowd agreement estimation and Fig.4 Execution time of different methods with varying multi-granularity link analysis[J].Neurocomputing,2015, data sizes 170:240-250. 3 结束语 [9]HUANG Dong,LAI Jianhuang,WANG Changdong.Ensem- 为解决聚类集成研究中的聚类成员可靠度估计 ble clustering using factor graph[J].Pattern recognition, 2016,50:131-142 与加权问题，本文提出了一个基于二部图结构与决策 [10]HUANG Dong,LAI Jianhuang,WANG Changdong.Robust 加权机制的聚类集成方法。我们将每个聚类成员视 ensemble clustering using probability trajectories[J].IEEE 作一个包含若干连接决策的集合，并为每个聚类成员 transactions on knowledge and data engineering,2016,28 的决策集合分配一个单位的可信度。该可信度由聚 (5):1312-1326. 类成员内的各个决策共同分享。进一步地，我们提出 [11]LI Tao,DING C.Weighted consensus clustering[C]//Pro- 基于可信度分享的决策加权机制，并将之整合至一个 ceedings of the 2008 SIAM International Conference on Data 统一的二部图模型中。因其二部图结构，该图模型可 mining.Auckland,New Zealand,2008:798-809. 利用Tcut算法进行快速分割，从而得到最终聚类集[l2]KARYPIS G,KUMAR V.Multilevel k-way partitioning 成结果。本文在8个实际数据集中进行了实验，将所 scheme for irregular graphs[J].Journal of parallel and dis- 提出方法与聚类成员以及6个现有方法进行了对比 tributed computing,1998,48(1):96-129. 分析。实验结果验证了本文方法在聚类质量及运算 [13]NG A Y,JORDAN M I,WEISS Y.On spectral clustering: Analysis and an algorithm[C]//Advances in Neural Infor- 效率上的显著优势。 mation Processing Systems.Vancouver,Canada,2001. 参考文献： [14]TOPCHY A,JAIN A K,PUNCH W.Clustering ensembles: models of consensus and weak partitions[J.IEEE transac- [1]STREHL A,GHOSH J.Cluster ensembles-a knowledge reuse tions on pattern analysis and machine intelligence,2005,27 framework for combining multiple partitions[J].The journal (12):1866-1881. of machine learning research,2003,3(3):583-617. [15]VEGA-PONS S,CORREA-MORRIS J,RUIZ-SHULCLOP- 2]CRISTOFOR D,SIMOVICI D.Finding median partitions u- ER J.Weighted partition consensus via kernels[]].Pattern sing information-theoretical-based genetic algorithms [J]. rec0 gnition,2010,43(8):2712-2724. Journal of universal computer science,2002,8(2):153-[16 VEGA-PONS S,RUIZ-SHULCLOPER J,GUERRA- 172 GANDON A.Weighted association based methods for the [3]FERN X Z,BRODLEY C E.Solving cluster ensemble prob- combination of heterogeneous partitions[J].Pattern recog- lems by bipartite graph partitioning[C]//Proceedings of the nition letters,.2011,32(16):2163-2170, 2 Ist International Conference on Machine Learning.New[I7]徐森，周天，于化龙，等.一种基于矩阵低秩近似的聚类 York,NY,USA,2004. 集成算法[J].电子学报，2013,41(6)：1219-1224. [4]FRED A L N,JAIN A K.Combining multiple clusterings u- XU Sen,ZHOU Tian,YU Hualong,et al.Matrix low rank
（ｈ）ＬＲ 图 ４ 各个聚类集成方法在不同数据规模下的运行时间 对比 Ｆｉｇ．４ Ｅｘｅｃｕｔｉｏｎ ｔｉｍｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ｍｅｔｈｏｄｓ ｗｉｔｈ ｖａｒｙｉｎｇ ｄａｔａ ｓｉｚｅｓ ３ 结束语 为解决聚类集成研究中的聚类成员可靠度估计 与加权问题，本文提出了一个基于二部图结构与决策 加权机制的聚类集成方法。 我们将每个聚类成员视 作一个包含若干连接决策的集合，并为每个聚类成员 的决策集合分配一个单位的可信度。 该可信度由聚 类成员内的各个决策共同分享。 进一步地，我们提出 基于可信度分享的决策加权机制，并将之整合至一个 统一的二部图模型中。 因其二部图结构，该图模型可 利用 Ｔｃｕｔ 算法进行快速分割，从而得到最终聚类集 成结果。 本文在 ８ 个实际数据集中进行了实验，将所 提出方法与聚类成员以及 ６ 个现有方法进行了对比 分析。 实验结果验证了本文方法在聚类质量及运算 效率上的显著优势。 参考文献： ［１］ＳＴＲＥＨＬ Ａ， ＧＨＯＳＨ Ｊ． Ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅｓ⁃ａ ｋｎｏｗｌｅｄｇｅ ｒｅｕｓｅ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｃｏｍｂｉｎｉｎｇ ｍｕｌｔｉｐｌｅ ｐａｒｔｉｔｉｏｎｓ［ Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｓｅａｒｃｈ， ２００３， ３（３）： ５８３⁃６１７． ［２］ＣＲＩＳＴＯＦＯＲ Ｄ， ＳＩＭＯＶＩＣＩ Ｄ． Ｆｉｎｄｉｎｇ ｍｅｄｉａｎ ｐａｒｔｉｔｉｏｎｓ ｕ⁃ ｓｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ⁃ｔｈｅｏｒｅｔｉｃａｌ⁃ｂａｓｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｕｎｉｖｅｒｓａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００２， ８ （ ２）： １５３⁃ １７２． ［３］ＦＥＲＮ Ｘ Ｚ， ＢＲＯＤＬＥＹ Ｃ Ｅ． Ｓｏｌｖｉｎｇ ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅ ｐｒｏｂ⁃ ｌｅｍｓ ｂｙ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ， ２００４． ［４］ＦＲＥＤ Ａ Ｌ Ｎ， ＪＡＩＮ Ａ Ｋ． Ｃｏｍｂｉｎｉｎｇ ｍｕｌｔｉｐｌｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕ⁃ ｓｉｎｇ ｅｖｉｄｅｎｃｅ ａｃｃｕｍｕｌａｔｉｏｎ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００５， ２７（６）： ８３５⁃８５０． ［５］ＷＡＮＧ Ｘｉ， ＹＡＮＧ Ｃｈｕｎｙｕ， ＺＨＯＵ Ｊｉｅ． Ｃｌｕｓｔｅｒｉｎｇ ａｇｇｒｅｇａ⁃ ｔｉｏｎ ｂｙ ｐｒｏｂａｂｉｌｉｔｙ ａｃｃｕｍｕｌａｔｉｏｎ ［ Ｊ ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２００９， ４２（５）： ６６８⁃６７５． ［６］ＳＩＮＧＨ Ｖ， ＭＵＫＨＥＲＪＥＥ Ｌ， ＰＥＮＧ Ｊｉｍｉｎｇ， ｅｔ ａｌ． Ｅｎｓｅｍｂｌｅ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｓｅｍｉｄｅｆｉｎｉｔｅ ｐｒｏｇｒａｍｍｉｎｇ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ［Ｊ］． Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ， ２０１０， ７９（１ ／ ２）： １７７⁃２００． ［７］ ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｅｘｐｌｏｉ⁃ ｔｉｎｇ ｔｈｅ ｗｉｓｄｏｍ ｏｆ ｃｒｏｗｄ： ａ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ａｐｐｒｏａｃｈ ｔｏ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎ⁃ ａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｃｉｅｎｃｅ ａｎｄ Ｂｉｇ Ｄａｔａ Ｅｎｇｉｎｅｅｒ⁃ ｉｎｇ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１３： １１２⁃１１９． ［８］ ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｃｏｍｂｉ⁃ ｎｉｎｇ ｍｕｌｔｉｐｌｅ ｃｌｕｓｔｅｒｉｎｇｓ ｖｉａ ｃｒｏｗｄ ａｇｒｅｅｍｅｎｔ ｅｓｔｉｍａｔｉｏｎ ａｎｄ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｌｉｎｋ ａｎａｌｙｓｉｓ ［ Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１５， １７０： ２４０⁃２５０． ［９］ ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｅｎｓｅｍ⁃ ｂｌｅ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｆａｃｔｏｒ ｇｒａｐｈ ［ Ｊ ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１６， ５０： １３１⁃１４２． ［１０］ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｒｏｂｕｓｔ ｅｎｓｅｍｂｌｅ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｐｒｏｂａｂｉｌｉｔｙ ｔｒａｊｅｃｔｏｒｉｅｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１６， ２８ （５）： １３１２⁃１３２６． ［１１］ＬＩ Ｔａｏ， ＤＩＮＧ Ｃ． Ｗｅｉｇｈｔｅｄ ｃｏｎｓｅｎｓｕｓ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００８ ＳＩＡＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ ｍｉｎｉｎｇ． Ａｕｃｋｌａｎｄ， Ｎｅｗ Ｚｅａｌａｎｄ， ２００８： ７９８⁃８０９． ［ １２ ］ ＫＡＲＹＰＩＳ Ｇ， ＫＵＭＡＲ Ｖ． Ｍｕｌｔｉｌｅｖｅｌ ｋ⁃ｗａｙ ｐａｒｔｉｔｉｏｎｉｎｇ ｓｃｈｅｍｅ ｆｏｒ ｉｒｒｅｇｕｌａｒ ｇｒａｐｈｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｐａｒａｌｌｅｌ ａｎｄ ｄｉｓ⁃ ｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔｉｎｇ， １９９８， ４８（１）： ９６⁃１２９． ［１３］ＮＧ Ａ Ｙ， ＪＯＲＤＡＮ Ｍ Ｉ， ＷＥＩＳＳ Ｙ． Ｏｎ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ： Ａｎａｌｙｓｉｓ ａｎｄ ａｎ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒ⁃ ｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， ２００１． ［１４］ＴＯＰＣＨＹ Ａ， ＪＡＩＮ Ａ Ｋ， ＰＵＮＣＨ Ｗ． Ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅｓ： ｍｏｄｅｌｓ ｏｆ ｃｏｎｓｅｎｓｕｓ ａｎｄ ｗｅａｋ ｐａｒｔｉｔｉｏｎｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００５， ２７ （１２）： １８６６⁃１８８１． ［１５］ＶＥＧＡ⁃ＰＯＮＳ Ｓ， ＣＯＲＲＥＡ⁃ＭＯＲＲＩＳ Ｊ， ＲＵＩＺ⁃ＳＨＵＬＣＬＯＰ⁃ ＥＲ Ｊ． Ｗｅｉｇｈｔｅｄ ｐａｒｔｉｔｉｏｎ ｃｏｎｓｅｎｓｕｓ ｖｉａ ｋｅｒｎｅｌｓ［ Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１０， ４３（８）： ２７１２⁃２７２４． ［ １６ ］ ＶＥＧＡ⁃ＰＯＮＳ Ｓ， ＲＵＩＺ⁃ＳＨＵＬＣＬＯＰＥＲ Ｊ， ＧＵＥＲＲＡ⁃ ＧＡＮＤóＮ Ａ． Ｗｅｉｇｈｔｅｄ ａｓｓｏｃｉａｔｉｏｎ ｂａｓｅｄ ｍｅｔｈｏｄｓ ｆｏｒ ｔｈｅ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｐａｒｔｉｔｉｏｎｓ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇ⁃ ｎｉｔｉｏｎ ｌｅｔｔｅｒｓ， ２０１１， ３２（１６）： ２１６３⁃２１７０． ［１７］徐森， 周天， 于化龙， 等． 一种基于矩阵低秩近似的聚类 集成算法［Ｊ］． 电子学报， ２０１３， ４１（６）： １２１９⁃１２２４． ＸＵ Ｓｅｎ， ＺＨＯＵ Ｔｉａｎ， ＹＵ Ｈｕａｌｏｎｇ， ｅｔ ａｌ． Ｍａｔｒｉｘ ｌｏｗ ｒａｎｋ ·４２４· 智 能 系 统 学 报 第 １１ 卷
第3期 黄栋，等：基于决策加权的聚类集成算法 .425. approximation--based cluster ensemble algorithm[J].Acta作者简介： electronica sinica,2013,41(6):1219-1224. 黄栋，男，1987年生，讲师，主要研究 [18]LECUN Y,BOTTOU L,BENGIO Y,et al.Gradient-based 方向为数据挖掘与模式识别，发表学术 learning applied to document recognition[J].Proceedings of 论文10余篇。 the IEEE,1998,86(11):2278-2324. [19]LI Zhenguo,WU Xiaoming,CHANG S F.Segmentation u- sing superpixels:a bipartite graph partitioning approach [C]//Proceedings of the 2012 IEEE Conference on Com- 王昌栋，男，1984年生，讲师，主要研 puter Vision and Pattem Recognition.Providence,RI, 究方向为非线性聚类、社交网络、大数据 USA,2012:789-796. 分析，发表学术论文40余篇。 [20]BACHE K,LICHMAN M.UCI machine learning repository EB/OL].(2013-04-04).http://archive.ics.uci.edu/ml. [21]IAM-ON N,BOONGOEN T,GARRETT S.Refining pair- wise similarity matrix for cluster ensemble problem with 赖剑煌，男，1964年生，教授，博士生 cluster relations[C]//Proceedings of the 11th International 导师，博士，广东省图象图形学会理事 Conference on Discovery Science.Budapest,Hungary, 长，中国图象图形学会常务理事，主要研 2008:222-233. 究方向为生物特征识别、数字图像处理、 [22]IAM-ON N,BOONGOEN T,GARRETT S,et al.A link- 模式识别和机器学习。主持国家自然科 based approach to the cluster ensemble problem[J].IEEE 学基金与广东联合重点项目、科技部科 transactions on pattern analysis and machine intelligence, 技支撑课题各1项，主持国家自然科学基金项目4项。发表 2011.33(12):2396-2409. 学术论文近200篇。 全国知识图谱与语义计算大会 China Conference on Knowledge Graph and Semantic Computing (CCKS2016) 全国知识图谱与语义计算大会(CCKS:China Conference on Knowledge Graph and Semantic Computing)由中国中文信息学会语 言与知识计算专家委员会负责组织和承办。CCKS2O16源于国内两个主要的相关会议：中文知识图谱研讨会Conference on Chi- nese Knowledge Graph(KG)和中国语义互联网与Web科学大会Chinese Semantic Web and WebScience Conference(CSWS)。首届 中文知识图谱研讨会于2013年在苏州举行，随后分别在武汉、宜昌成功举办第二次和第三次研讨会。CSWS首次会议于2006年 在北京举办，随后的近十年里，逐渐成为国内语义技术领域的主要会议。新的知识图谱与语义计算大会将致力于成为国内知识 图谱、语义技术、链接数据等领域的核心会议，并聚集了知识表示、自然语言处理、机器学习、数据库、图计算等相关领域的重要学 者和研究人员。 今年会议的主题是“语义、知识与链接大数据”。今年会议的主题是“语义、知识与链接大数据”。会议将包括学术讲习班 工业界论坛、评测与竞赛、特邀报告、学术论文、海报及演示等主要环节。其中，学术讲习班邀请国内外知名研究者讲授实学术界 最新进展和实战经验，工业界论坛邀请产业界的主要研发人员分享经验，促进产学研合作。 大会同时欢迎英文和中文论文。英文论文将被Spig©r出版的论文集收录，中文论文将被推荐到东南大学学报、中文信息 学报等期刊发表。部分优秀论文将被推荐到the Semantic Web Journal,Elsevier Journal of Big Data Research,Journalof Web Seman- tics等国际期刊发表。所有论文要求是未发表内容，并通过会议论文网站提交：https://easychair.org/conferences/?conf= ccks2016.相关主题如下（但不限于）： 1)知识表示 5)知识共享与基于知识的系统 2)知识图谱构建与信息抽取 6)知识推理 3)语义集成 7)链接数据 4)知识存储 会议网站：htp:/ccks2016.cipsc..org.cn/或http:/ccks2016.cm
ａｐｐｒｏｘｉｍａｔｉｏｎ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ａｃｔａ ｅｌｅｃｔｒｏｎｉｃａ ｓｉｎｉｃａ， ２０１３， ４１（６）： １２１９⁃１２２４． ［１８］ＬＥＣＵＮ Ｙ， ＢＯＴＴＯＵ Ｌ， ＢＥＮＧＩＯ Ｙ， ｅｔ ａｌ． Ｇｒａｄｉｅｎｔ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ ａｐｐｌｉｅｄ ｔｏ ｄｏｃｕｍｅｎｔ ｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ， １９９８， ８６（１１）： ２２７８⁃２３２４． ［１９］ＬＩ Ｚｈｅｎｇｕｏ， ＷＵ Ｘｉａｏｍｉｎｇ， ＣＨＡＮＧ Ｓ Ｆ． Ｓｅｇｍｅｎｔａｔｉｏｎ ｕ⁃ ｓｉｎｇ ｓｕｐｅｒｐｉｘｅｌｓ： ａ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇ ａｐｐｒｏａｃｈ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１２ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ⁃ ｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｐｒｏｖｉｄｅｎｃｅ， ＲＩ， ＵＳＡ， ２０１２： ７８９⁃７９６． ［２０］ＢＡＣＨＥ Ｋ， ＬＩＣＨＭＡＮ Ｍ． ＵＣＩ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ ［ＥＢ／ ＯＬ］． （２０１３⁃０４⁃０４）． ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ ／ ｍｌ． ［２１］ ＩＡＭ⁃ＯＮ Ｎ， ＢＯＯＮＧＯＥＮ Ｔ， ＧＡＲＲＥＴＴ Ｓ． Ｒｅｆｉｎｉｎｇ ｐａｉｒ⁃ ｗｉｓｅ ｓｉｍｉｌａｒｉｔｙ ｍａｔｒｉｘ ｆｏｒ ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅ ｐｒｏｂｌｅｍ ｗｉｔｈ ｃｌｕｓｔｅｒ ｒｅｌａｔｉｏｎｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １１ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｉｓｃｏｖｅｒｙ Ｓｃｉｅｎｃｅ． Ｂｕｄａｐｅｓｔ， Ｈｕｎｇａｒｙ， ２００８： ２２２⁃２３３． ［２２］ＩＡＭ⁃ＯＮ Ｎ， ＢＯＯＮＧＯＥＮ Ｔ， ＧＡＲＲＥＴＴ Ｓ， ｅｔ ａｌ． Ａ ｌｉｎｋ⁃ ｂａｓｅｄ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅ ｐｒｏｂｌｅｍ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１１， ３３（１２）： ２３９６⁃２４０９． 作者简介： 黄栋，男，１９８７ 年生，讲师，主要研究 方向为数据挖掘与模式识别，发表学术 论文 １０ 余篇。 王昌栋，男，１９８４ 年生，讲师，主要研 究方向为非线性聚类、社交网络、大数据 分析，发表学术论文 ４０ 余篇。 赖剑煌，男，１９６４ 年生，教授，博士生 导师，博士，广东省图象图形学会理事 长，中国图象图形学会常务理事，主要研 究方向为生物特征识别、数字图像处理、 模式识别和机器学习。 主持国家自然科 学基金与广东联合重点项目、科技部科 技支撑课题各 １ 项，主持国家自然科学基金项目 ４ 项。 发表 学术论文近２００ 篇。 全国知识图谱与语义计算大会 Ｃｈｉｎａ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｇｒａｐｈ ａｎｄ Ｓｅｍａｎｔｉｃ Ｃｏｍｐｕｔｉｎｇ （ＣＣＫＳ２０１６） 全国知识图谱与语义计算大会（ＣＣＫＳ： Ｃｈｉｎａ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｇｒａｐｈ ａｎｄ Ｓｅｍａｎｔｉｃ Ｃｏｍｐｕｔｉｎｇ）由中国中文信息学会语 言与知识计算专家委员会负责组织和承办。 ＣＣＫＳ２０１６ 源于国内两个主要的相关会议：中文知识图谱研讨会 Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｈｉ⁃ ｎｅｓｅ Ｋｎｏｗｌｅｄｇｅ Ｇｒａｐｈ （ＫＧ）和中国语义互联网与 Ｗｅｂ 科学大会 Ｃｈｉｎｅｓｅ Ｓｅｍａｎｔｉｃ Ｗｅｂ ａｎｄ ＷｅｂＳｃｉｅｎｃｅ Ｃｏｎｆｅｒｅｎｃｅ （ＣＳＷＳ）。 首届 中文知识图谱研讨会于 ２０１３ 年在苏州举行，随后分别在武汉、宜昌成功举办第二次和第三次研讨会。 ＣＳＷＳ 首次会议于 ２００６ 年 在北京举办，随后的近十年里，逐渐成为国内语义技术领域的主要会议。 新的知识图谱与语义计算大会将致力于成为国内知识 图谱、语义技术、链接数据等领域的核心会议，并聚集了知识表示、自然语言处理、机器学习、数据库、图计算等相关领域的重要学 者和研究人员。 今年会议的主题是“语义、知识与链接大数据”。 今年会议的主题是“语义、知识与链接大数据”。 会议将包括学术讲习班、 工业界论坛、评测与竞赛、特邀报告、学术论文、海报及演示等主要环节。 其中，学术讲习班邀请国内外知名研究者讲授实学术界 最新进展和实战经验，工业界论坛邀请产业界的主要研发人员分享经验，促进产学研合作。 大会同时欢迎英文和中文论文。 英文论文将被 Ｓｐｒｉｎｇｅｒ 出版的论文集收录，中文论文将被推荐到东南大学学报、中文信息 学报等期刊发表。 部分优秀论文将被推荐到 ｔｈｅ Ｓｅｍａｎｔｉｃ Ｗｅｂ Ｊｏｕｒｎａｌ， Ｅｌｓｅｖｉｅｒ Ｊｏｕｒｎａｌ ｏｆ Ｂｉｇ Ｄａｔａ Ｒｅｓｅａｒｃｈ， Ｊｏｕｒｎａｌｏｆ Ｗｅｂ Ｓｅｍａｎ⁃ ｔｉｃｓ 等国际期刊发表。 所有论文要求是未发表内容，并通过会议论文网站提交：ｈｔｔｐｓ：／ ／ ｅａｓｙｃｈａｉｒ． ｏｒｇ ／ ｃｏｎｆｅｒｅｎｃｅｓ／ ？ ｃｏｎｆ ＝ ｃｃｋｓ２０１６ ．相关主题如下（但不限于）： １）知识表示 ２）知识图谱构建与信息抽取 ３）语义集成 ４）知识存储 ５）知识共享与基于知识的系统 ６）知识推理 ７）链接数据 会议网站：ｈｔｔｐ：／ ／ ｃｃｋｓ２０１６．ｃｉｐｓｃ．ｏｒｇ．ｃｎ ／ 或 ｈｔｔｐ：／ ／ ｃｃｋｓ２０１６．ｃｎ 第 ３ 期 黄栋，等：基于决策加权的聚类集成算法 ·４２５·