宋仁旺，苏小杰，石 慧

(太原科技大学电子信息工程学院，太原 030024)

随着信息行业的爆炸式发展，数据已成为行各业重要的生产因素，同时也对海量数据的挖掘提出新的挑战。信息爆炸产生的海量数据对从大量数据中挖掘有用信息提出挑战[1-4]。数据的聚类是数据挖掘实施过程中的核心技术[5-6]。MacQueen[7]为解决数据挖掘问题提出了一个局部搜索的算法——K-means聚类算法。该算法原理简单、运算高效、时间和空间复杂度较低，至今依然是工业和社会科学中最流行的算法[8]。但该K-means聚类效果对最初K个初始中心点的选取和离群值都非常敏感，当用于海量数据聚类时，由于其迭代次数过多且迭代过程涉及多次文件系统的读写操作非常费时[9-11]，所以有必要对K-means聚类算法初始聚类中心点的选取进行改进以减少聚类过程中的迭代次数，从而降低聚类所需的时间并提高聚类效果。

针对上述问题，学者从不同角度对K-means算法进行了改进。Arthur等[12]在K-means算法的基础上对中心点的选择进行改进，即基于每个数据点到已有中心点的距离采用线性概率选出下一个聚类中心点，简单地说就是数据点离现有的中心点距离越远就越有可能被选为类簇中心点，该方法能有效解决初始聚类中心点敏感的问题，但是由于类簇中心点的选择具有有序性，这使得算法无法并行扩展，极大地限制了算法在大规模数据集上的应用。K-medoids算法是在K-means聚类方法基础演变而来，该算法的特点是选取的每个中心点都是样本点，因此该方法能够解决K-means算法对噪声和离群值敏感问题，但是该算法时间复杂度高，不适合应用于大批量数据集[13]。……