A New Consensus Method for Cluster Ensembles to Improve Clustering Accuracy and Stability

摘要

数据分组是理解学习中的一个基本和重要的模式，相似的模型被聚集到同一个分组中，不同的模型在不同的分组中。本论文提出了一种基于统计共识的聚类融合算法来提高聚类的准确性和稳定性，算法可以应用于隐私问题数据或大规模不能聚集到一个位置的分布式数据挖掘中。融合方法已广泛应用于监督式学习，并且事实证明，融合方法比单一的预测＼学习模式相比，能将预测误差减少到相当高的程度。近些年，人们正在研究非监督的学习（聚类融合），期望获得可喜成果。本文所提出的基于统计共识的聚类融合方法通过四个步骤获得最后的共识聚类结果。
　　 第一步是利用K-means算法在不同的初始参数下运行多次产生聚类成员。初始参数对K-means算法的影响是比较大的，采用不同的初始参数在同一数据集上得到多种聚类结果。第二步是在产生聚类成员中选择一个最佳聚类。这部分通过基于K-means算法定义的目标函数来实现，这个目标函数可以减小误差并使得类之间的紧凑度和分离度更好。由于缺少标记，误差是能判断聚类分析质量的很好的数学方法。第三步是融合方法，论文采用选择性聚类融合方法，选取一致性聚类并丢弃不一致的聚类。在融合中，利用信息理论（互信息）作为选择一致性聚类的标准，第四步是一致性函数。最后的聚类结果是利用一致性聚类成员使用统计共识函数得到的。
　　 论文所研究聚类融合算法改善了聚类结果的精确性以及稳定性。由于聚类融合在数据挖掘和机器学习中有很大影响力，将多种聚类模型融合到一种聚类方法中，通常效果会比单一聚类算法好。大多数数据挖掘和知识发现技术是针对建模，而不是在结果的精确度上。但是对于复杂商业智能系统，确实需要更多关注聚类精确度，而不是聚类建模。任何商务智能系统都需要一个高质量聚类作为其核心，在大多数情况下它涉及到大量数据，并且数据有时可能在分布式环境下。问题在于，现有的经典聚类算法并不稳定，它们的不稳定导致在不准确的聚类结果，同时因为经典聚类算法假设数据是在单一的位置上，所以这些算法并不适合数据不能合并到单一位置的分布式数据环境。
　　 本文提出的新聚类融合算法除了提高稳定性和聚类结果精确度外，它还可以用于分布式数据的聚类。分布式数据挖掘是数据挖掘的有趣的方面之一，尤其是当数据集因存储（通常数据挖掘涉及到大量的数据）或隐私性等原因，不能合并到一个位置。单一的经典聚类算法是不能处理这些情况的。我们的方法使用许多模式和聚类中心表示聚类，这使得我们的算法独特于现有的使用类标签标识每个模式或数据点的聚类融合方法。用聚类中心和大量模式表示的聚类，直接解决了标签对应问题，而不用像现有的大多数算法引用额外的技术。这种方法也节省了时间与空间，共识函数只需要聚类中心和数据点数量这些信息，它远远小于数据集中的实际数据点数量，这使得我们的算法适用于处理并行或分布式环境中的大量数据。实验结果表明，本文提出的聚类融合算法与k-means经典聚类算反比较，算法的精度性和稳定性更好。
　　 论文章节安排如下：第一章介绍了数据挖掘和知识发现涉及的技术理念以及其应用。第二章着重于聚类和聚类融合，并对现有融合算法及技术进行了综述，第三章是提出的新聚类融合算法。第四章是实验与评估，第五章是结论。最后是感谢，参考文献和附录。

目录

文摘

英文文摘

Dedication

CHAPER 1 INTRODUCTION

1.1 Background

1.2 Literature Review

1.2.1 Data Mining and Knowledge Discovery in Databases

1.2.2 Clustering and Business Intelligent Applications

1.2.3 Business Intelligent Systems

1.3 Why This Research

1.4 Research Contribution

CHAPTER 2 CLUSTER ENSEMBLES REVIEW

2.1 Ensembles

2.2 Cluster Ensembles

2.2.1 Cluster Ensemble Background

2.2.2 Methods for Generating Clustering Ensembles

2.2.3 Consensus by Voting Techniques

2.2.4 Graph Theory Consensus Techniques

2.2.5 Mixture Model Consensus Technique

2.2.6 Rand Index Technique

CHAPTER 3 THE PROPOSED ENSEMBLE METHOD

3.1 The Ensemble Technique Abstraction

3.2 Generating Data Partitions

3.2.1 The K-means Clustering Algorithms

3.2.2 Missing Values

3.3 Reference Partition Selection

3.4 Filtering of Inconsistency Partitions

3.5 The Consensus Function

3.6 Summary for the Consensus Process

3.6.1 Pictorial Representations

3.6.2 Consensus Algorithm

CHAPTER 4 EXPERIMENTS AND EVALUATIONS

4.1 Experiments

4.2 Evaluations

CHAPTER 5 CONCLUSION AND REMARK

REFERENCES

APPENDICES

Appendix A: 2-Dimension Graphical Representation of Clusters

Appendix B: Useful Mat Lab Functions

ACKNOWLEDGEMETS