启发式k-means聚类算法的改进研究

摘要

启发式k-means聚类算法通过在k-means第一次迭代后查看附近的集群来预测每个数据点可能会被划分到的集群子集，有效地加快了算法的运行速度。但由于启发式算法存在随机选择初始聚类中心以及无法有效识别数据集中离群点的缺陷，导致聚类结果的误差平方和较大并且轮廓系数偏小。针对这一问题，提出了CHk-means算法，该算法引入仔细播种方法，克服了启发式k-means算法随机选择初始聚类中心带来的局部最优解问题；该算法引入局部异常因子LOF算法对离群点进行检测，降低了离群点数据对聚类结果的影响。在多个数据集上对3种算法进行对比试验，结果表明CHk-means算法可有效降低聚类结果的误差平方和，增强聚类的轮廓系数，使聚类质量得到明显改善。

关键词

聚类算法 / k-means / 启发式算法 / 仔细播种 / 局部异常因子 / 离群点

基金资助

国家自然科学基金项目(61771087)