高 波,何振峰

(福州大学 数学与计算机科学学院,福州 350108)

聚类是一种无监督学习方法,它根据样本间相似度把样本划分到若干簇[1].K-Means 算法是聚类算法的一种典型代表,它因其简单而又有效的特性备受欢迎,并且在十大经典数据挖掘算法中排名第二[2].该算法根据用户指定的K值,基于某种距离度量方式,把样本划分为K个不同的簇,使得簇内样本相似性高,簇间样本相似性低[1].高维数据空间中数据分布稀疏且存在着大量无关属性,数据的重要结构信息会隐藏在海量的噪声数据中,因此使用K-Means 算法在高维数据上进行聚类很难发现数据的内在结构,使得聚类效果差[3,4].然而在现实的聚类分析应用场景中,数据维度通常很高,比如图片视频或文本数据,其维度一般为千万级,甚至更高.针对这一问题,Mautz 等人于2017年提出了SubKMeans 算法[5],该算法能够将数据映射到子空间中进行聚类,降低维度影响,提升K-Means 类算法聚类性能.

SubKMeans 算法将数据空间划分为一个包含有大部分重要信息的子空间和一个基本不包含重要信息的子空间,通过映射矩阵能够把数据投影到包含有大部分重要信息的子空间中进行聚类,从一定程度上减轻“维度灾难”对K-Means 类算法的影响.但是SubKMeans算法只是对经典K-Means 类算法的一种扩展,它依然会受到K-Means 类算法固有缺陷的限制[6].SubKMeans算法是无监督聚类算法,需要用户事先指定K值,而在现实中部分数据集的种类数是未知的,这给使用者带来巨大的困扰,因……