基于Hash函数取样的线性时间聚类方法LCHS

摘要：

作为数据挖掘中的经典算法,k-中心点算法存在效率低、对大数据集适应性差等严重不足.该文针对这一不足,提出并实现Hash分层模型LCHS(Linear Clustering Based Hash Sampling),主要贡献包括:(1)将m维超立方体按等概率空间进行分桶,使得每层(即Hash桶)的数据个数相近,以较小的计算代价获得分层抽样的效果;(2) 新算法保证了样本具有对总体数据的充分的统计代表性;(3)从理论上证明了新算法复杂度为O(N);(4)对比实验表明新算法在数据集的个数接近10000时,效率比传统算法提高2个数量级,数据集的个数接近8000时,聚类质量比CLARA算法提高55%.

关键词：k-中心点、聚类分析、线性时间、Hash函数、取样

所属期刊栏目：26

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金60473071;国家重点基础研究发展计划973计划2002CB111504;高等学校博士学科点专项科研项目桂科自0339039

在线出版日期：2005-09-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1364-1368