引用本文

张瑞霖, 郑海阳, 苗振国, 王鸿鹏. 基于空间向量分解的边界剥离密度聚类. 自动化学报, 2023, 49(6): 1195−1213 doi: 10.16383/j.aas.c220208

Zhang Rui-Lin, Zheng Hai-Yang, Miao Zhen-Guo, Wang Hong-Peng. Density clustering based on the border-peeling using space vector decomposition. Acta Automatica Sinica, 2023, 49(6): 1195−1213 doi: 10.16383/j.aas.c220208

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c220208

关键词

聚类，空间向量分解，边界剥离，投影子空间，高维，密度 

摘要

作为聚类的重要组成部分, 边界点在引导聚类收敛和提升模式识别能力方面起着重要作用, 以BP (Border-peeling clustering)为最新代表的边界剥离聚类借助潜在边界信息来确保簇核心区域的空间隔离, 提高了簇骨架代表性并解决了边界隶属问题. 然而, 现有边界剥离聚类仍存在判别特征不完备、判别模式单一、嵌套迭代等约束. 为此, 提出了基于空间向量分解的边界剥离密度聚类(Density clustering based on the border-peeling using space vector decomposition, CBPVD), 以投影子空间和原始数据空间为基准, 从分布稀疏性(紧密性)和方向偏斜性(对称性)两个视角强化边界的细粒度特征, 进而通过主动边界剥离反向建立簇骨架并指导边界隶属. 与同类算法相比, 40个数据集(人工、UCI、视频图像)上的实验结果以及4个视角的理论分析表明了CBPVD在高维聚类和边界模式识别方面具有良好的综合表现.

文章导读

聚类分析旨在将目标数据划分到若干互不相交的集合中, 以实现高组内相似性和低组间相似性[1], 广泛用于图像分割、推荐系统、海量数据标注等人工智能场景[2].

作为最受欢迎的聚类范式之一, 密度聚类的首要任务是搜索一批高代表性对象并建立簇的核心区域, 进而指导其余对象归属. 核心对象包含了丰富的结构信息, 通过给定的可达条件, 形成的核心区域(目标簇骨架)可有效表征簇的实际结构. 因此, 大多数密度聚类方法将核心对象的特征提取作为聚类主线. 例如, 以DPC (Clustering by fast search and find of density peaks)[3]代表的密度峰值聚类[4-7]通过峰值最大化判别核心对象; H-DBSCAN[8]等派生于DBSCAN[9]的传统方法利用全局密度描述核心对象. 总的来说, 在识别核心对象后, 许多方法[10-11]以此为基准构建簇的骨架, 却忽视了边界对象的重要性, 仅将其视为核心对象在数据空间上的相对补.

事实上, 较之特征单一的核心点, 边界点较为复杂多变, 主要位于目标簇的边缘、簇与簇之间以及远离簇的区域[12]. 在簇骨架建立时, 边界点往往会弱化簇的独立性、误合并近邻簇. 此外边界点往往具有两个或多个群体的属性特征, 在实际场景中包含了高价值的模式信息[13], 如临床中携带病毒或致病基因但未发病的人群、人脸识别中动作复杂、归属模糊的图像. 基于此, 一些研究者将密度聚类中边界被动过滤转为主动剥离, 进一步确保簇骨架之间的空间隔离. 尽管已针对性地提出一些面向边界剥离的密度聚类, 如基于统计量的Spinver[14]、CA-CSM[15]、C-USB[16]; 基于D-S证据理论的3W-DPET[17]; 基于切平面一致性的DCUBI[18], 以及最新发表的BP (Border-peeling clustering)算法[13], 但现有方法的边界剥离模式仍面临着判别特征不完备、判别条件单一、倾向低维凸数据等局限.

受子空间聚类[19]的启发, 提出了一种基于空间向量分解的边界剥离密度聚类(Density clustering based on the border-peeling using space vector decomposition, CBPVD), 将数据点与其近邻形成的空间关系由原始高维空间射影到低维子空间中, 利用边界(核心对象)在投影子空间上的分布方向偏斜性(对称性)以及在原始空间上的分布稀疏性(稠密性)强化特征表示, 实现边界有效剥离, 进而通过传递闭包和密度优先级策略共同指导对象划分. 本文工作如下:

1)引入空间向量分解理论, 从矢量视角分析并量化高维数据的局部分布;

2)从原始数据空间和投影子空间两个维度强化边界特征表示, 提出了一种非迭代、细粒度的边界剥离方法; 利用传递闭包和密度优先级策略, 建立了一种两阶段对象关联策略;

3)提出了基于空间向量分解的边界剥离密度聚类, 广泛的实验和深入分析验证了算法在高维聚类和边界模式信息识别方面的有效性.

图 1  计算边界置信的图示

本文通过融合边界点(核心点)在投影子空间上的维度偏斜性(对称性)和原始数据空间上的空间稀疏性(紧密性)主动剥离聚类边界, 提出了基于空间向量分解的边界剥离密度聚类CBPVD, 不仅解决了现有边界剥离聚类中边界判别标准单一、嵌套迭代、倾向于分布均匀、球形簇的局限, 同时提升了算法在复杂分布、高维数据下的表现. 算法的有效性可归为如下因素, 首先, 边界点的判断不再单一依靠密度大小, 而是以原始数据空间和投影子空间为基准从分布大小和分布方向两个视角强化边界的细粒度特征表示; 其次, 提出的两阶段对象关联策略避免了现有算法中边界之间的冗余级联, 减少了对象划分错误的闭包传递; 此外, CBPVD无需迭代优化, 其超参数少于BP算法且易于确定; 最后, 从理论分析和多维实验上对比了CBPVD与EC、DPC、BP、K-means、GB-DPC、SNN-DPC的聚类表现, 累计40个数据集(合成、UCI、图像)的实验结果和4个维度的深入分析(鲁棒性、统计排名、性能、边界模式识别)表明CBPVD在高维聚类和边界模式信息提取方面的有效性. 如何将边界剥离聚类思想嵌入深度神经网络以实现参数推荐和扩大应用场景是下一步工作.

作者简介

张瑞霖

哈尔滨工业大学(深圳)计算机科学与技术学院博士研究生. 主要研究方向为深度学习, 计算机视觉和数据挖掘. E-mail: zzurlz@163.com

郑海阳

哈尔滨工业大学(深圳)计算机科学与技术学院硕士研究生. 主要研究方向为深度学习. E-mail: 21S151085@stu.hit.edu.cn

苗振国

哈尔滨工业大学(深圳)计算机科学与技术学院硕士研究生. 主要研究方向为深度学习. E-mail: 20S051017@stu.hit.edu.cn

王鸿鹏

哈尔滨工业大学(深圳)计算机科学与技术学院教授. 主要研究方向为计算机视觉, 智能机器人和人工智能. 本文通信作者. E-mail: wanghp@hit.edu.cn