Abstract:

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.

Key words: data mining, K-means algorithm, initial cluster center, weighted Euclidean distance, weight product

摘要：

K-means聚类算法简单高效，应用广泛。针对传统K-means算法初始聚类中心点的选择随机性导致算法易陷入局部最优以及K值需要人工确定的问题，为了得到最合适的初始聚类中心，提出一种基于距离和样本权重改进的K-means算法。该聚类算法采用维度加权的欧氏距离来度量样本点之间的远近，计算出所有样本的密度和权重后，令密度最大的点作为第一个初始聚类中心，并剔除该簇内所有样本，然后依次根据上一个聚类中心和数据集中剩下样本点的权重并通过引入的参数[τi]找出下一个初始聚类中心，不断重复此过程直至数据集为空，最后自动得到[k]个初始聚类中心。在UCI数据集上进行测试，对比经典K-means算法、WK-means算法、ZK-means算法和DCK-means算法，基于距离和权重改进的K-means算法的聚类效果更好。

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