基于距离和权重改进的K-means算法  

Improved K-means Algorithm Based on Distance andWeight

作　　者：王子龙 李进[2] 宋亚飞[2] WANG Zilong;LI Jin;SONG Yafei(Graduate College,Air Force Engineering University,Xi’an 710051,China;School of Air and Missile Defense,Air Force Engineering University,Xi’an 710051,China)

机构地区：[1]空军工程大学研究生院,西安710051 [2]空军工程大学防空反导学院,西安710051

出　　处：《计算机工程与应用》2020年第23期87-94,共8页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61703426,No.61503407,No.61876189);中国博士后科学基金(No.2018M633680);陕西省高校科协青年人才托举计划(No.20190108)。

摘　　要：K-means聚类算法简单高效,应用广泛。针对传统K-means算法初始聚类中心点的选择随机性导致算法易陷入局部最优以及K值需要人工确定的问题,为了得到最合适的初始聚类中心,提出一种基于距离和样本权重改进的K-means算法。该聚类算法采用维度加权的欧氏距离来度量样本点之间的远近,计算出所有样本的密度和权重后,令密度最大的点作为第一个初始聚类中心,并剔除该簇内所有样本,然后依次根据上一个聚类中心和数据集中剩下样本点的权重并通过引入的参数τi找出下一个初始聚类中心,不断重复此过程直至数据集为空,最后自动得到k个初始聚类中心。在UCI数据集上进行测试,对比经典K-means算法、WK-means算法、ZK-means算法和DCKmeans算法,基于距离和权重改进的K-means算法的聚类效果更好。K-means clustering algorithm is simple,efficient and widely used.The randomness of the selection of the initial clustering center of the traditional K-means algorithm leads to the problem that the algorithm is easy to fall into the local optimal and the K value needs to be determined manually.In order to obtain the most appropriate initial clustering center,an improved K-means algorithm based on distance and sample weight is proposed.This clustering algorithm uses dimensionally-weighted Euclidean distance to measure the distance between sample points,after calculating the density and weight of all samples,the point with the highest density is used as the first initial cluster center,and all samples within the cluster are eliminated,then,according to the last cluster center and the weights of the remaining sample points in the data set,the next initial cluster center is found through the introduced parameterτi,this process is repeated until the data set is empty,finally k initial cluster centers are automatically obtained.The experiments are carried out on the UCI data set.Compared with the classical K-means algorithm,WK-means algorithm,ZK-means algorithm and DCK-means algorithm,the improved K-means algorithm based on distance and weight has better clustering effect.

关 键 词：数据挖掘 K-MEANS算法 初始聚类中心 加权欧式距离 权重 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]