一个近似的线性时间聚类算法

An Approximated Linear Clustering Method

聚类分析是数据挖掘的一个重要研究方向,而PAM算法是聚类算法中一个重要的方法.本文针对PAM算法不适应大数据集的缺点,给出一个近似的线性时间聚类算法(ALCM),并且从理论上证明了该算法复杂度为关于数据集个数的线性时间复杂度.通过比较实验表明:1)随着数据个数的增大,PAM所花费的时间将激剧增大,而ALCM花费时间与数据集个数呈近似线性增长的关系,即ALCM是适应大数据集的.2)PAM算法和ALCM算法随数据个数增大,二者的代价函数并无明显差异.

Cluster is an important research direction and the PAM algorithm is one ot the most important method. But the PAM can work well with large data set. To solve the problem, this paper shows an Approximated Linear Clustering Method （ALCM）, and proves that the complexity of the new algorithm is O（n）, where n is the number of data set. The comparing experiment shows that the performance of ALCM method is higher than the PAM with large data set, and it is not obviously different between two methods about the value of Cost function.