作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (8): 58-63,71. doi: 10.19678/j.issn.1000-3428.0054555

• 人工智能与模式识别 • 上一篇    下一篇

一种可重叠子空间K-Means聚类算法

刘宇航1, 马慧芳1,2, 刘海姣1, 余丽1   

  1. 1. 西北师范大学 计算机科学与工程学院, 兰州 730070;
    2. 桂林电子科技大学 广西可信软件重点实验室, 广西 桂林 541004
  • 收稿日期:2019-04-10 修回日期:2019-07-01 发布日期:2019-07-17
  • 作者简介:刘宇航(1996-),男,硕士研究生,主研方向为智能计算;马慧芳(通信作者),教授、博士;刘海姣,硕士研究生;余丽,讲师、博士。
  • 基金资助:
    国家自然科学基金(61762078,61363058);广西可信软件重点实验室研究课题(kx202003);广西多源信息挖掘与安全重点实验室开放基金(MIMS18-08);西北师范大学2019年度青年教师科研能力提升计划重大项目(NWNU-LKQN2019-2)。

An Overlapping Subspace K-Means Clustering Algorithm

LIU Yuhang1, MA Huifang1,2, LIU Haijiao1, YU Li1   

  1. 1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China;
    2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
  • Received:2019-04-10 Revised:2019-07-01 Published:2019-07-17

摘要: 现有聚类算法面向高维稀疏数据时多数未考虑类簇可重叠和离群点的存在,导致聚类效果不理想。为此,提出一种可重叠子空间K-Means聚类算法。设计类簇子空间计算策略,在聚类过程中动态更新每个类簇的属性子空间,并定义合理的约束函数指导聚类过程,从而实现类簇的可重叠性与离群点的控制。在此基础上定义合理的目标函数对传统K-Means算法进行修正,利用熵权约束分别计算每个类簇中各维度的权重,使用权重值标识不同类簇中维度的相对重要性,并加入控制重叠程度和离群值数量的参数。在人工数据集和真实数据集上的实验结果表明,该算法在NMI、F1指标上均优于EWKM、NEO-K-Means、OKM等子空间聚类算法,具有更好的聚类结果。

关键词: 目标函数, 子空间聚类, 离群点, 熵权约束, K-Means聚类算法

Abstract: Most of existing clustering algorithms for high-dimensional sparse data do not consider overlapping class clusters and outliers,resulting in unsatisfactory clustering results.Therefore,this paper proposes an overlapping subspace K-Means clustering algorithm.The computing strategy for class cluster subspace is given.The attribute subspace of each class cluster is dynamically updated in the clustering process,and a reasonable constraint function is defined to guide the clustering process,so as to realize the overlap of clusters and the control of outliers.On this basis,a reasonable objective function is defined to modify the traditional K-Means algorithm,and the weight of each dimension in each class cluster is calculated by using the entropy weight constraint.The value of weight is used to identify the relative importance of the dimensions in different class clusters.And some parameters are added to control the degree of overlap and the number of outliers.Experimental results on artificial data set and real data set show that the proposed algorithm outperforms EWKM,NEO-K-Means,OKM and other subspace clustering algorithms in terms of NMI and F1 indicators with better clustering results.

Key words: objective function, subspace clustering, outlier, entropy weight constraint, K-Means clustering algorithm

中图分类号: