.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（ｈ）ＬＲ 图 ４ 各个聚类集成方法在不同数据规模下的运行时间 对比 Ｆｉｇ．４ Ｅｘｅｃｕｔｉｏｎ ｔｉｍｅ ｏｆ ｄｉｆｆｅｒｅｎｔ ｍｅｔｈｏｄｓ ｗｉｔｈ ｖａｒｙｉｎｇ ｄａｔａ ｓｉｚｅｓ ３ 结束语 为解决聚类集成研究中的聚类成员可靠度估计 与加权问题，本文提出了一个基于二部图结构与决策 加权机制的聚类集成方法。 我们将每个聚类成员视 作一个包含若干连接决策的集合，并为每个聚类成员 的决策集合分配一个单位的可信度。 该可信度由聚 类成员内的各个决策共同分享。 进一步地，我们提出 基于可信度分享的决策加权机制，并将之整合至一个 统一的二部图模型中。 因其二部图结构，该图模型可 利用 Ｔｃｕｔ 算法进行快速分割，从而得到最终聚类集 成结果。 本文在 ８ 个实际数据集中进行了实验，将所 提出方法与聚类成员以及 ６ 个现有方法进行了对比 分析。 实验结果验证了本文方法在聚类质量及运算 效率上的显著优势。 参考文献： ［１］ＳＴＲＥＨＬ Ａ， ＧＨＯＳＨ Ｊ． Ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅｓ⁃ａ ｋｎｏｗｌｅｄｇｅ ｒｅｕｓｅ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｃｏｍｂｉｎｉｎｇ ｍｕｌｔｉｐｌｅ ｐａｒｔｉｔｉｏｎｓ［ Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｓｅａｒｃｈ， ２００３， ３（３）： ５８３⁃６１７． ［２］ＣＲＩＳＴＯＦＯＲ Ｄ， ＳＩＭＯＶＩＣＩ Ｄ． Ｆｉｎｄｉｎｇ ｍｅｄｉａｎ ｐａｒｔｉｔｉｏｎｓ ｕ⁃ ｓｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ⁃ｔｈｅｏｒｅｔｉｃａｌ⁃ｂａｓｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｕｎｉｖｅｒｓａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００２， ８ （ ２）： １５３⁃ １７２． ［３］ＦＥＲＮ Ｘ Ｚ， ＢＲＯＤＬＥＹ Ｃ Ｅ． Ｓｏｌｖｉｎｇ ｃｌｕｓｔｅｒ ｅｎｓｅｍｂｌｅ ｐｒｏｂ⁃ ｌｅｍｓ ｂｙ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ， ２００４． ［４］ＦＲＥＤ Ａ Ｌ Ｎ， ＪＡＩＮ Ａ Ｋ． Ｃｏｍｂｉｎｉｎｇ ｍｕｌｔｉｐｌｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕ⁃ ｓｉｎｇ ｅｖｉｄｅｎｃｅ ａｃｃｕｍｕｌａｔｉｏｎ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００５， ２７（６）： ８３５⁃８５０． ［５］ＷＡＮＧ Ｘｉ， ＹＡＮＧ Ｃｈｕｎｙｕ， ＺＨＯＵ Ｊｉｅ． Ｃｌｕｓｔｅｒｉｎｇ ａｇｇｒｅｇａ⁃ ｔｉｏｎ ｂｙ ｐｒｏｂａｂｉｌｉｔｙ ａｃｃｕｍｕｌａｔｉｏｎ ［ Ｊ ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２００９， ４２（５）： ６６８⁃６７５． ［６］ＳＩＮＧＨ Ｖ， ＭＵＫＨＥＲＪＥＥ Ｌ， ＰＥＮＧ Ｊｉｍｉｎｇ， ｅｔ ａｌ． Ｅｎｓｅｍｂｌｅ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｓｅｍｉｄｅｆｉｎｉｔｅ ｐｒｏｇｒａｍｍｉｎｇ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ［Ｊ］． Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ， ２０１０， ７９（１ ／ ２）： １７７⁃２００． ［７］ ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｅｘｐｌｏｉ⁃ ｔｉｎｇ ｔｈｅ ｗｉｓｄｏｍ ｏｆ ｃｒｏｗｄ： ａ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ａｐｐｒｏａｃｈ ｔｏ ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎ⁃ ａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｃｉｅｎｃｅ ａｎｄ Ｂｉｇ Ｄａｔａ Ｅｎｇｉｎｅｅｒ⁃ ｉｎｇ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１３： １１２⁃１１９． ［８］ ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｃｏｍｂｉ⁃ ｎｉｎｇ ｍｕｌｔｉｐｌｅ ｃｌｕｓｔｅｒｉｎｇｓ ｖｉａ ｃｒｏｗｄ ａｇｒｅｅｍｅｎｔ ｅｓｔｉｍａｔｉｏｎ ａｎｄ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｒｉｔｙ ｌｉｎｋ ａｎａｌｙｓｉｓ ［ Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１５， １７０： ２４０⁃２５０． ［９］ ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｅｎｓｅｍ⁃ ｂｌｅ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｆａｃｔｏｒ ｇｒａｐｈ ［ Ｊ ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１６， ５０： １３１⁃１４２． ［１０］ＨＵＡＮＧ Ｄｏｎｇ， ＬＡＩ Ｊｉａｎｈｕａｎｇ， ＷＡＮＧ Ｃｈａｎｇｄｏｎｇ． Ｒｏｂｕｓｔ ｅｎｓｅｍｂｌｅ ｃｌｕｓｔｅｒｉｎｇ ｕｓｉｎｇ ｐｒｏｂａｂｉｌｉｔｙ ｔｒａｊｅｃｔｏｒｉｅｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１６， ２８ （５）： １３１２⁃１３２６． ［１１］ＬＩ Ｔａｏ， ＤＩＮＧ Ｃ． Ｗｅｉｇｈｔｅｄ ｃｏｎｓｅｎｓｕｓ ｃｌｕｓｔｅｒｉｎｇ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００８ ＳＩＡＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ ｍｉｎｉｎｇ． Ａｕｃｋｌａｎｄ， Ｎｅｗ Ｚｅａｌａｎｄ， ２００８： ７９８⁃８０９． ［ １２ ］ ＫＡＲＹＰＩＳ Ｇ， ＫＵＭＡＲ Ｖ． Ｍｕｌｔｉｌｅｖｅｌ ｋ⁃ｗａｙ ｐａｒｔｉｔｉｏｎｉｎｇ ｓｃｈｅｍｅ ｆｏｒ ｉｒｒｅｇｕｌａｒ ｇｒａｐｈｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｐａｒａｌｌｅｌ ａｎｄ ｄｉｓ⁃ ｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔｉｎｇ， １９９８， ４８（１）： ９６⁃１２９． ［１３］ＮＧ Ａ Ｙ， ＪＯＲＤＡＮ Ｍ Ｉ， ＷＥＩＳＳ Ｙ． Ｏｎ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ： Ａｎａｌｙｓｉｓ ａｎｄ ａｎ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒ⁃ ｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， ２００１． ［１４］ＴＯＰＣＨＹ Ａ， ＪＡＩＮ Ａ Ｋ， ＰＵＮＣＨ Ｗ． Ｃｌｕｓｔｅｒｉｎｇ ｅｎｓｅｍｂｌｅｓ： ｍｏｄｅｌｓ ｏｆ ｃｏｎｓｅｎｓｕｓ ａｎｄ ｗｅａｋ ｐａｒｔｉｔｉｏｎｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００５， ２７ （１２）： １８６６⁃１８８１． ［１５］ＶＥＧＡ⁃ＰＯＮＳ Ｓ， ＣＯＲＲＥＡ⁃ＭＯＲＲＩＳ Ｊ， ＲＵＩＺ⁃ＳＨＵＬＣＬＯＰ⁃ ＥＲ Ｊ． Ｗｅｉｇｈｔｅｄ ｐａｒｔｉｔｉｏｎ ｃｏｎｓｅｎｓｕｓ ｖｉａ ｋｅｒｎｅｌｓ［ Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１０， ４３（８）： ２７１２⁃２７２４． ［ １６ ］ ＶＥＧＡ⁃ＰＯＮＳ Ｓ， ＲＵＩＺ⁃ＳＨＵＬＣＬＯＰＥＲ Ｊ， ＧＵＥＲＲＡ⁃ ＧＡＮＤóＮ Ａ． Ｗｅｉｇｈｔｅｄ ａｓｓｏｃｉａｔｉｏｎ ｂａｓｅｄ ｍｅｔｈｏｄｓ ｆｏｒ ｔｈｅ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｐａｒｔｉｔｉｏｎｓ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇ⁃ ｎｉｔｉｏｎ ｌｅｔｔｅｒｓ， ２０１１， ３２（１６）： ２１６３⁃２１７０． ［１７］徐森， 周天， 于化龙， 等． 一种基于矩阵低秩近似的聚类 集成算法［Ｊ］． 电子学报， ２０１３， ４１（６）： １２１９⁃１２２４． ＸＵ Ｓｅｎ， ＺＨＯＵ Ｔｉａｎ， ＹＵ Ｈｕａｌｏｎｇ， ｅｔ ａｌ． Ｍａｔｒｉｘ ｌｏｗ ｒａｎｋ ·４２４· 智 能 系 统 学 报 第 １１ 卷