快速聚类算法在个性化服务中的应用

Fast Cluster Algorithm Applied in Individuation Information Service

许多实际应用已经证明,k-means算法能够有效地得到好的聚类结果。但是,k-means直接算法的时间复杂度和模式复杂度对数据量的大小非常敏感,无法满足一些高性能的应用场合,如个性化服务中对用户数据进行的群组分析。对此,笔者提出了一种新颖的基于k-d树的聚类算法。这种算法采用空间数据结构—k-d树组织所有的样本数据,可以高效地搜索到离某个给定的聚类中心最近的全部模式。实验结果表明,该方案可以显著提高k-means直接算法的运算速度,在距离运算量和总的运算时间上,可把性能提高1～2个数量级。

The k-means method has been shown to be effective in producing good clustering results with many practical applications.However,the time required in a direct algorithm of k-means method is sensitive to the number of patterns.To this problem,this paper presents a new algorithm to perform k-means clustering:k-d tree based cluster al-gorithm.This experimental results demonstrate that the scheme can improve the computational speed of the direct k-means algorithm by an order to two orders of magnitude in the total number of distance calculations and the overall time of computation.