基于距离和密度的PBK-means算法
来源：计算机工程杂志2020年第9期北京时间：
作者：魏文浩, 唐泽坤, 刘刚
单位：兰州大学 信息科学与工程学院, 兰州 730000
摘要：K-means算法初始中心点选择的随机性以及对噪声点的敏感性，使得聚类结果易陷入局部最优解，为获得最佳初始聚类中心，提出一种基于距离和密度的并行二分K-means算法。计算数据集的平均样本距离，根据数据点之间的距离计算数据的权重，选择最大权重数据点作为第一个中心点，小于平均样本距离的数据点不参加下一次聚类，将剩余数据点的权重与中心点距离相乘，选择值最大的数据点作为下一个中心点，得到两个中心点后按照距离对数据进行分配，将每个中心点代表的类分为两类后在每类上继续重复上述步骤。通过模仿细胞分裂的方法对数据进行切分，构建一棵满二叉树，当叶子结点数超过类别数k时停止聚类，合并叶子结点得到k个初始聚类中心执行K-means算法。在UCI公开数据集上进行测试，结果表明，对比传统K-means算法、Canopy-Kmeans算法、二分K-means算法、WK-means算法、MWK-means算法和DCK-means算法，该算法效率更高，具有较好的聚类效果。
关键词：二分K-means算法,聚类中心,初始中心点,权重,数据挖掘
基金资助：中央高校基本科研业务费专项资金重点项目基于大数据的城市公共安全风险预警研究（17LZUJBWZD012）；教育部哲学社会科学研究重大课题攻关项目大数据驱动的城市公共安全风险研究（16JZD023）。
