一种融合三支决策理论的改进K-means算法  

Improved K-means Algorithm Combining Three-way Decision Theory

作　　者：夏月月 张以文[1] XIA Yue-yue;ZHANG Yi-wen(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

机构地区：[1]安徽大学计算机科学与技术学院,合肥230601

出　　处：《小型微型计算机系统》2020年第4期724-731,共8页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61872002)资助;安徽省自然科学基金项目(1808085MF197)资助。

摘　　要：传统的K-means算法及其改进算法在对数据集进行聚类划分时通常精确地确定样本点与聚簇的隶属关系,没有充分考虑隶属关系模糊的边界点.本文提出一种结合三支决策理论的改进算法TK-means.首先,将数据空间分为核心区域和边缘区域分别处理,解决K-means算法对所有样本点统一处理造成的聚类结果不准确的问题;其次,结合网格聚类算法中划分网格的思想快速确定核心点和边缘点;最后,设计了新的初始聚类中心确定方法,可有效解决K-means算法初始聚类中心随机选择使得聚类结果不稳定的问题.通过模拟数据集和UCI数据集的大量实验证明,TK-means算法比现有经典的K-means及其改进算法拥有更好的性能.When the traditional K-means algorithm and its improved algorithms cluster the data sets,they usually determine the membership relationship between the sample points and the clusters precisely,and do not fully consider the boundary points of the fuzzy membership relationship.In this paper,we propose an improved algorithm TK-means combining three decision theory.Firstly,the data space is divided into core area and edge area respectively,aiming to solve the problem of inaccurate clustering results,which is caused by the K-means algorithm for the uniform processing of all sample points.Secondly,by combining the idea of meshing in the grid clustering algorithm,the core point and the edge point are quickly determined;Finally,a newinitial clustering center determination method is designed,which can effectively solve the problem that the initial clustering center of K-means algorithm is randomly selected to make the clustering result unstable.A large number of experiments with simulation data sets and UCI data sets prove that the TKmeans algorithm has better performance than the existing classic K-means and its improved algorithms.

关 键 词：三支决策 K-MEANS 划分聚类算法 

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