引用本文

陶新民, 王若彤, 常瑞, 李晨曦, 刘艳超. 基于低密度分割密度敏感距离的谱聚类算法. 自动化学报, 2020, 46(7): 1479-1495. doi: 10.16383/j.aas.c180084

TAO Xin-Min, WANG Ruo-Tong, CHANG Rui, LI Chen-Xi, LIU Yan-Chao. Low Density Separation Density Sensitive Distance-based Spectral Clustering Algorithm. ACTA AUTOMATICA SINICA, 2020, 46(7): 1479-1495. doi: 10.16383/j.aas.c180084

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

关键词

谱聚类，低密度分割，欧氏距离，密度敏感，鲁棒性 

摘要

本文提出一种基于低密度分割密度敏感距离的谱聚类算法, 该算法首先使用低密度分割密度敏感距离计算相似度矩阵, 该距离测度通过指数函数和伸缩因子实现放大不同流形体数据间的距离和缩短同一流形体数据间距离的目的, 从而有效反映数据分布的全局一致性和局部一致性特征.另外, 算法通过增加相对密度敏感项来考虑数据的局部分布特征, 从而有效避免孤立噪声和"桥"噪声的影响.文中最后给出了基于SC (Scattering criteria)指标的k近邻图k值选取办法和基于谱熵贡献率的特征向量选取方法.实验部分, 讨论了参数选择对算法性能的影响并给出取值建议, 通过与其他流行谱聚类算法聚类结果的对比分析, 表明本文提出的基于低密度分割密度敏感距离的谱聚类算法聚类性能明显优于其他算法.

文章导读

谱聚类(Spectral clustering)算法是一种基于谱图划分理论的子空间聚类算法[1], 与传统聚类算法相比, 因其对聚类样本空间的形状和维度没有特殊要求, 且具有收敛于全局最优解的优点, 现已被广泛应用在图像分割[2-4]、并行计算[5]、数据分类[6]等方面.其中, NJW (Ng-Jordan-Weiss)算法[7]是谱聚类算法中最核心、最常用的方法.它通过数据的规范化拉普拉斯矩阵的特征向量作为样本集进行聚类, 相似度矩阵的确定是影响该算法性能的重要因素, 而相似度矩阵又取决于距离测度的选择[8].在被广泛应用的谱聚类算法中, 多采用欧氏距离和曼哈顿距离作为相似性的度量[9-10].除此以外, 余弦距离、皮尔森相似距离也常常被应用在谱聚类中[11].然而这些距离测度方法都没有考虑数据的分布特征, 如数据呈现非线性或局域流形特征时, 这些方法所表现的聚类性能并不理想[12].

考虑到数据的分布特征影响, 文献[13]利用连接距离来测量样本点间的相似程度.所谓连接距离, 是指从数据集全局出发, 通过寻找连接任意两点间所有路径中最大间隔距离中的最小值作为两个样本间的距离测度.通过该距离测度能消除只考虑样本点间距离的大小而不考虑数据全局分布特征的弊端, 从而反映数据集的空间分布一致性.但是, 该距离测度无法防止"桥"噪声数据的影响, 当"桥"噪声产生时, 原本的流形体会在该距离测度下合并, 导致无法实现正确聚类[14-16].为消除样本局部分布特征对聚类性能的影响, 文献[17]提出了一种密度敏感的谱聚类算法, 该算法使用基于密度敏感的相似度矩阵计算方法, 通过密度项放大正常样本点与孤立噪声点的距离, 同时缩小正常样本点间距离的方式消除孤立噪声的影响; 然而, 该距离测度没有考虑数据的非线性和流形分布特征对算法性能的影响.文献[18]提出了一种典型的密度峰值聚类算法, 该算法通过考虑数据间的密度关系进行聚类, 满足了数据间的全部一致性.然而该距离测度没能充分考虑数据的局部一致性特征且易受"桥"噪声数据的影响.据此, Yu等[19]提出利用基于密度的最短几何距离谱聚类算法, 虽然算法使用基于密度的最短几何距离测度可以反映数据集分布特征的影响, 但是这种距离测度只考虑了数据集的局部空间一致性, 没能考虑全局空间一致性.且算法的性能受k值的影响很大, 极端情况下当k取值较大时, 该距离测度等价于欧氏距离, 导致聚类效果并不理想[20-21].

为解决上述问题, 本文在综合考虑全局空间一致性和局部空间一致性的基础上, 提出一种基于低密度分割密度敏感距离的谱聚类算法.考虑到位于同一流形体上两点间会有许多较短的边连接, 而位于不同流形体上的两点需要较长边相连, 算法使用低密度分割密度敏感距离通过指数函数和伸缩因子实现放大位于不同流形上的数据点间距离, 缩短位于同一流形上的数据点间距离的目的, 从而有效反映了数据分布的全局一致性和局部一致性特征.为进一步防止孤立噪声以及"桥"噪声的影响, 该距离测度还充分考虑了数据的局部分布特征, 通过增加相对密度敏感项实现缩小正常样本点间距离、增大正常样本点与噪声样本点间距离的目的.此外, 由于k最近邻参数的确定以及特征向量的选择对谱聚类算法聚类性能的影响很大, 文中给出了基于SC (Scattering criteria)指标的k近邻图k值选取方法和基于谱熵贡献率的特征向量选取方法.通过实验对比可知, 本文所提出的基于低密度分割密度敏感距离的谱聚类算法在人工数据集和UCI数据集上均得到了较好的聚类结果, 表明了该方法的合理性与有效性.

图 1  全局一致性距离示意图

图 2  局部空间一致性距离示意图

图 3  Ring数据集相似度矩阵

本文提出一种基于低密度分割密度敏感距离的谱聚类算法, 通过实验分析得到如下结论:

1) 为解决数据分布特征对现有谱聚类算法聚类性能的影响, 本文引入低密度分割密度敏感距离进行数据间相似性测量, 并通过理论推导和实验证明本文算法所采用的距离测度能同时满足数据间的全局一致性和局部一致性特征要求, 使获得的相似度矩阵更符合实际数据的分布情况, 同时通过增加相对密度敏感项来考虑样本局部分布特征的影响, 大大提高了算法聚类性能.

2) 由于最近邻个数的确定以及特征向量的选择对谱聚类算法的聚类性能影响很大, 本文进一步给出了基于SC指标的k近邻图k值选取方法和基于谱熵贡献率的特征向量选取方法.实验部分通过对仿真和UCI数据集在不同参数设置下聚类性能的对比分析, 结果验证了上述两种方法的正确性和有效性.

3) 实验最后对不同谱聚类算法的鲁棒性进行了比较, 结果表明本文LDSDSD-SC算法在所有比较的5种算法中鲁棒性能最好, 这说明本文算法采用的低密度分割密度敏感距离不仅能同时满足聚类的全局一致性和局部一致性的特征, 且能有效防止孤立噪声和“桥''噪声对聚类性能的影响, 使得算法的鲁棒性显著提高.需要说明的是, 如何选取特征向量的个数以及在聚类个数未知的情况下如何确定聚类个数都将是本课题下一阶段研究的重点.

作者简介

王若彤

东北林业大学工程技术学院硕士研究生.主要研究方向为物联网技术, 人工智能, 模式识别.E-mail: celia_wangrt@163.com

常瑞

东北林业大学工程技术学院硕士研究生.主要研究方向为物联网技术, 人工智能, 模式识别.E-mail: m15765549429@163.com

李晨曦

东北林业大学工程技术学院硕士研究生.主要研究方向为物联网技术, 人工智能, 模式识别.E-mail: chenxili0613@163.com

刘艳超

东北林业大学工程技术学院硕士研究生.主要研究方向为物联网技术, 智慧物流, 数字通信技术.E-mail: 15776802213@163.com

陶新民

东北林业大学工程技术学院教授.主要研究方向为智能信号处理, 物联网技术, 故障诊断, 软计算方法, 模式识别, 网络安全.本文通信作者.E-mail: taoxinmin@nefu.edu.cn