数据挖掘中一种高效的聚类通用框架研究

Research on an Efficient Clustering General Framework in Data Mining

随着传感器和互联网技术高速发展,数据集的规模激增,但系统的存储和处理能力仍然滞后。针对目前的数据聚类算法所需的测量值数目较多、时间开销大的不足,为了高效地解决大型数据集中的数据聚类问题,提出了一种主动式分层聚类通用框架,通过在小型数据集上重复运行离线聚类算法,既保证了算法性能,又降低了测量值计算复杂度和运行时间复杂度。然后,基于谱聚类算法讨论了本文框架,理论分析结果表明,利用O(n lg2n)个相似性数据可以恢复规模为Ω(lgn)的所有聚类,对包含n个对象的数据集,其运行时间为O(n lg3n)。最后,通过全面的仿真实验,证明了所提框架的其他优异性能。

Advances in sensing technologies and the growth of the internet have resuhed in an explosion in the size of datasets, while the storage and processing power continue to lag behind. Aiming at the disadvantages of required the larger number of measurements and spent the more running time at the current data clustering algorithms, in order to efficiently solve problems related to the large datasets, a general framework is proposed for active hierarchical clustering that repeatedly runs an off-the-shelf clustering algorithm on small subsets of the data and comes with guarantees on performance, measurement complexity and runtime complexity. This framework is instantiated with the spectral clustering algorithm and concrete results is provided on its performance. Theoretical analysis results show that, this algorithm recovers all clusters of size Ω（lgn） using O（n lg2n） similarities and runs in O（ n lg3n） time for a dataset of n objects. This framework is practically alluring.