计算机工程

作者：魏文浩, 唐泽坤, 刘刚

单位：兰州大学 信息科学与工程学院, 兰州 730000

关键词：二分K-means算法,聚类中心,初始中心点,权重,数据挖掘

基金：中央高校基本科研业务费专项资金重点项目"基于大数据的城市公共安全风险预警研究"（17LZUJBWZD012）；教育部哲学社会科学研究重大课题攻关项目"大数据驱动的城市公共安全风险研究"（16JZD023）。

K-means算法初始中心点选择的随机性以及对噪声点的敏感性，使得聚类结果易陷入局部最优解，为获得最佳初始聚类中心，提出一种基于距离和密度的并行二分K-means算法。计算数据集的平均样本距离，根据数据点之间的距离计算数据的权重，选择最大权重数据点作为第一个中心点，小于平均样本距离的数据点不参加下一次聚类，将剩余数据点的权重与中心点距离相乘，选择值最大的数据点作为下一个中心点，得到两个中心点后按照距离对数据进行分配，将每个中心点代表的类分为两类后在每类上继续重复上述步骤。通过模仿细胞分裂的方法对数据进行切分，构建一棵满二叉树，当叶子结点数超过类别数k时停止聚类，合并叶子结点得到k个初始聚类中心执行K-means算法。在UCI公开数据集上进行测试，结果表明，对比传统K-means算法、Canopy-Kmeans算法、二分K-means算法、WK-means算法、MWK-means算法和DCK-means算法，该算法效率更高，具有较好的聚类效果。

来源：2020年第9期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第9期