基于局部密度离群点检测k-means算法*

刘 凤， 戴家佳， 胡 阳

(贵州大学 数学与统计学院，贵阳 550025)

0 引 言

聚类是无监督学习中一个重要的方法，它在一定意义上检测数据集中相似的对象，并形成群集的过程，这在大数据时代是很有必要的。聚类的最主要目的是使得群集与群集之间的距离最大化，群集内的对象距离最小化。同一个簇中的对象与该簇中其他的对象是非常相似的，不同群集之间中对象彼此差异是比较大的。MacQueen[1]提出k-means算法，该算法是一种最著名的划分聚类算法，其算法原理在聚类算法中是比较简单的，并且易于聚类。在实际生活中聚类分析也得到比较广泛的应用[2-4]。虽其原理简单，但是该算法也存在一些缺点，最主要有以下几个方面：对球状形数据集聚类结果较好，其他的数据集聚类结果相对较差；在聚类的时候容易局部收敛；k是随机的，需要在聚类的时候人为给定；聚类算法中初始聚类中心的选取问题；若数据集中有离群点、数据类型不一致等对聚类结果影响比较大。考虑这些不足之处，有大量学者对其不足进行改进，Arthur和Vassilvitskii[5]对其初始聚类中心随机性做改进，首先在数据集中随机选择一个数据点作为第一个初始聚类中心；其次在数据集中选择与第一个聚类中心相对最远的点作为第二个类簇中心，依据这种原理，直到选出k个群集质心。然而聚类中心的选择会影响聚类数目的准确性，Alibuhtto和Mahat[6]提出了一种基于距离的k-means算法，来确定聚类中的聚类数目。Masud等[7]提出了聚类数目与聚类中心的自动选择方法，Zhou等[8]提出了基于遗传算法的初始聚类中心的自动选择。……