基于流形距离核的自适应迁移谱聚类算法

齐晓轩 都 丽 洪振麒

1(沈阳大学应用技术学院 辽宁 沈阳 110044)2(沈阳大学信息工程学院 辽宁 沈阳 110044)

0 引 言

聚类[1-2]作为数据挖掘领域中重要的方法，主要是将同类对象划分为同一簇，不同类对象划分到不同簇的过程。聚类方法有很多种，如C-means、FCM、MECA[3-5]等算法，但这些算法在高斯分布数据集上聚类效果良好，在非高斯分布数据集上聚类效果却不太理想，容易受样本形状影响。谱聚类算法(SC)[6-10]作为一种图论演化而来的算法，不受样本空间形状的制约，且收敛于全局最优解，在一定程度上解决了这个问题。

SC算法首先根据给定的样本集计算任意两点的相似度矩阵W，然后计算特征矩阵，最后使用特征矩阵进行聚类，所以相似度矩阵W的选取直接影响特征矩阵的构造，进而影响聚类效果。Kong等[10]通过建立新的相似图来构造相似度矩阵;ZelnikManor等[13]利用数据点的邻域分布，自动调节尺度参数，增加其泛化能力。Wang等[3]针对相似度矩阵构造存在尺度敏感问题，利用密度差来调整样本点之间的相似度。范子静等[14]利用模糊划分改进谱聚类中硬化分，调整相似性度量函数。以上方法皆是以欧氏距离作为相似性度量方法，无法反映空间分布结构特征。张建朋等[15]通过使用流形距离代替欧氏距离构造相似性矩阵来改进AP算法,较好地解决了数据分布的全局结构问题；Tao等[16]使用流形距离计算相似度矩阵，但没有考虑数据点全部的邻域信息，对于复杂分布点效果依然不理想。

在实际环境中，领域中可用数据的匮乏或者数据受到污染，样本特征信息稀疏，传统的聚类算法很难达到良好效果。针对此种情况，迁移学习可以有效利用在某个不同但相关领域上学习到的知识或模式(源域)指导当前领域(目标域)中数据量匮乏的聚类任务，辅助提高聚类效果。在聚类中加入迁移学习已帮助学者们解决了很多问题[16-19]：Dai等[20]通过同时聚类目标和辅助数据提出一种基于协同聚类的自学习聚类(STC);Jiang等[21]通过联合聚类方法提出迁移谱聚类方法(TSC);魏彩娜等[22]提出基于F-范数正则项的迁移谱聚类方法(TSC-IDFR);Qian等[23]提出使用中心与隶属度信息迁移的TI-KT-CM和TII-KT-CM方法。

为提高谱聚类的领域适应能力，降低样本数量、数据空间分布对谱聚类的性能影响，本文提出一种基于流形距离核的自适应迁移谱聚类算法。具体包括两个方面的改进：① 考虑数据分布的全局一致性，使用流形距离作为相似性计算方法，且面对簇边缘分布不均匀或不同簇边缘分布密度相近，局部密度情况复杂会导致错分的问题，对核函数进行自适应调整，提高谱聚类对复杂数据集的处理能力；② 考虑领域数据匮乏问题，引入迁移学习方法，使用源域的知识辅助目标域进行谱聚类。经实验验证，本文算法与原始谱聚类算法相比有明显提升。

1 相关概念

1.1 SC算法

SC算法(见图1)主要思想是把样本点连接起来构造无向权重图，根据距离远近赋予权重高低，根据子图内权重和高、子图间权重和低的最优划分原则对图进行最优划分，从而完成聚类。

图1 SC算法原理示意图

SC算法的最优化模型为：

maxtr(UTLU)U∈RN×k

(1)

s.t.UTU=I

算法实现过程：

输入：n个样本点X=x1,x2,…,xn，聚类个数k

输出：聚类簇c1,c2,…,ck

步骤1构造无向权重图G(V,E),计算相似度矩阵W：

(2)

步骤2计算度矩阵D:

(3)

步骤3计算拉普拉斯矩阵L:

L=D-W

(4)

标准化L：

(5)

步骤4计算L的前k个最小特征值的特征向量组成矩阵且对其进行标准化，得到特征矩阵U={u1,u2,…,uk},U∈Rn×k。

步骤5采用C-means或FCM等对U进行聚类，得到聚类结果{c1,c2,…,ck}。

1.2 流形距离

欧氏距离是最快捷简单的距离度量方法。但使用欧氏距离计算的聚类算法往往会忽略数据的空间分布特征，无法满足聚类的全局一致性。为了解决这个问题，有学者提出流形距离，具体形式如下：

局部流形距离即流形上的点到点的线段长度，在同一流形结构中，数据集任意两点xi、xj之间的流形距离为：

Ld(xi,xj)=ρdist(xi,xj)-1

(6)

式中：dist(xi,xj)为xi和xj两点之间的欧氏距离。

全局流形距离：构造数据点间的加权无向图G(V,E)，V为图的顶点,E为图边集合。令p={p1,p2,…,pk}∈Vl表示图上一条连接点p1与pk的路径，其中边(pm,pm+1)∈E，1≤m

设P=(p1,p2,…,pk)是xi和xj之间的一条最短路径,则全局流形距离为连接两点之间的最短路径的所有局部距离之和：

(7)

式中：pi,j是xi和xj之间的最短路径。

(8)

该方法可增大不同流形上数据点的距离，缩小不同流形上数据点的距离。

2 算法设计

2.1 基于流形距离核的自适应谱聚类算法(ASC-MDK)

SC算法用高斯核函数构建相似度矩阵，但是欧氏距离在计算距离时受结构影响较大，当数据集为复杂的流形结构时，会损失很多结构特征，使用流形距离代替欧氏距离能在一定程度上解决这个问题。

本文以流形距离计算任意两点的距离，且对核函数进行调整，使其面对更复杂的分布时，保留更多样本特征信息，提高聚类准确率。欧氏距离计算的核函数为：

(9)

本文用流形距离作为距离度量方法，流形距离核函数为：

(10)

该核函数虽能考虑数据的整体结构分布，但参数σ均是通过反复测试得到，时间复杂度高，若取固定值，则影响核函数的泛化性，制约聚类效果。为了取得合适参数，ZelnikManor等[13]提出使用数据点的邻域信息计算一种自动选择尺度参数σ的方法，为每一个样本点选择一个σi，定义的核函数为：

(11)

式中:σi为点xi到第k个近邻的欧氏距离，但该k近邻方法易受噪声点影响。本文尺度参数取点xi的加权距离，可在一定程度上提高核函数的自适应能力，降低噪声点的干扰，具体表示为：

(12)

(13)

式中:参数σi取点xi的第k个近邻点xk的加权距离。由此可以得到融入加权参数和流形距离的核函数，具体表示为：

(14)

使用流形距离计算的相似度矩阵考虑了全局一致性，加权参数可减小参数对特征矩阵的影响。但当簇间密度差异较大、簇边缘分布不均匀或不同簇边缘分布密度相近时，局部密度情况复杂会导致错分，仍会影响聚类效果。以图2和图3为例，利用式(14)计算图2中点的相似度，a、b位于较稠密的簇中,c、d处于较稀疏的簇中，且它们都处于簇的边缘，正确聚类有一定难度，已知dist(a,b)=dist(b,c)=dist(c,d)，可知当σb<σd、σbσc<σdσc，得K(b,c)

图2 样密度分布不均匀示意图

图3为双月形分布，已知dist(e,f)=dist(f,g)，当σe=σg时，σeσf=σgσf，表明e、f和g、f的相似度相同，但e、f应聚为一类，所以g影响了f的聚类，可能使f聚为错误的一类。所以应该赋予e、f更高的相似性。

图3 双月形分布示意图

为解决上述问题，提高聚类准确率，本文使用共享近邻方法(SNN)[24]来调整相似度矩阵，SNN定义为求两个点共享的近邻点的个数。xi和xj表示样本集{x1,x2,…,xn}的任意两点，两点的相似度为共享最近邻点的个数，即：

(15)

(16)

当共享近邻数为0时，SNN(xi,xj)+1=1，即对相似性不作调整。因为a、b处于稠密的簇中，可知a、b的共享近邻的个数多于b、c的共享近邻个数，所以SNN(a,b)+1>SNN(b,c)+1，可以对相似性进行调整，使a、b的相似性更大，使聚为一类的概率更高。e、f处于同一流形中，g处于另一流形中，可知e、f共享近邻多于g、f，所以SNN(e,f)+1>SNN(f,g)+1，可以对相似性进行调整，使e、f的相似性更大，更可能聚为一类。

综上，基于SC算法提出了一种改进的计算相似度函数的方法：“加权局部密度自适应的流形距离核”，表示为：

(17)

该核函数得到的距离空间是离散值，区间为[0，+∞]，相似度空间区间为[0，+∞]。通过式(17)，可知该函数满足以下基本性质：

1) 非负性：Kij≥0；

2) 自反性：Kij=0；

3) 对称性：Kij=Kji；

4) 一致性：当S(xa,xb)

2.2 ATSC-MDK算法

ASC-MDK在样本充分时，可通过考虑数据聚类的全局分布，局部复杂分布情况，进行自适应调节。但当数据匮乏时，该方法依然不会得到理想效果，由此引入迁移学习解决这个问题。基于F-范数的正则项迁移谱聚类方法(TSC-IDFR)[21]在SC算法上，引入迁移学习机制形成了基于高级知识迁移的谱聚类算法，即把源域提取出的高级知识进行迁移，指导目标域数据集的聚类。

TSC-IDFR通过减小目标域数据和源域数据上的知识之间的不相似程度，得优化函数为：

(18)

式中:U(C)和U(O)分别表示目标域数据和源域数据的特征矩阵；KU(C)和KU(O)分别表示U(C)和U(O)对应的相似度矩阵。经过变换，得到优化目标函数：

(19)

式(19)通过最小化目标函数，即最大化tr(U(C)U(C)TU(O)U(O)T),作为迁移正则项加入谱聚类原始优化函数中，那么TSC-IDFR的最优化模型为：

(20)

s.t.U(C)TU(C)=I

经变换得：

(21)

s.t.U(C)TU(C)=I

式中：λ为调整目标域关于源域知识的迁移程度，其参考取值范围为(0.1,1.0)。

在该迁移谱聚类方法基础上，融入ASC-MDK算法，提出基于流形距离核的自适应迁移谱聚类算法(ATSC-MDK)，其最优化模型为：

(22)

2.3 算法流程

输入：源域数据集data(O)，目标域数据集data(C),聚类个数c,伸缩因子ρ，最近邻点数k

输出：目标域数据点的划分c1，c2,…,ck

步骤1使用第K近邻机制为输入的目标域数据集data(C)从源域数据集data(O)中挑选可参照样本集(采用网格搜索方法)。

(1) 通过迪杰特斯拉算法[25]进行数据集任意相邻两点最短路径选择，并通过式(8)计算最短路径和。

(2) 根据式(12)、式(13)计算参数σi和σj。

(3) 根据共享近邻算法计算SNN(xi,xj)+1；最后计算式(17)得到Kij。

(4) 计算数据集的拉普拉斯矩阵L，其中：

对角元素为：Kii=0,1≤i,j

构造拉普拉斯矩阵：L=D-K。

算法流程图如图4所示。

图4 ATSC-MDK算法流程图

3 实 验

3.1 算法分析

3.1.1 相似度对比分析

相似度矩阵对于谱聚类算法进行特征提取而言是至关重要的一步，会直接影响聚类结果。如图5所示，以双月型数据集(如图3所示)为例，(a)为以本文提出的距离核计算的相似度矩阵，(b)为传统谱聚类的高斯核计算的相似度矩阵。以高斯核计算的距离矩阵类别分布不明显，无明显规律可循，说明以欧氏距离计算的相似度矩阵很大程度上忽略复杂数据集的分布结构，而本文距离核计算的点阵颜色分布及深浅较明显，呈块对角模式，可看到明显分类。这表明，本文方法能更好地反映数据集的内在结构和整体分布，采用的流形距离测度较空间分布形状不敏感，更能考虑流形分布对聚类的影响。且通过考虑边缘密度情况，降低边缘密度影响造成错分情况。最后采用加权自适应核参数，避免了参数敏感，且降低了噪声点的干扰。

(a) 距离核 (b) 高斯核图5 两种方法相似度矩阵计算对比

3.1.2 复杂度分析

本文算法主要执行任务是计算ATSC-MDK算法的迭代过程。ATSC-MDK运行一次需要分别进行源域和目标域的ASC-MDK算法。选取来自源域的样本数据时间复杂度是O(m×n2)，利用Dijkstra算法搜索最短路径的空间复杂度为O(n2)，构建KNN网络并赋权的计算径向基参数时间复杂度为O(n2)，SNN共享近邻时间复杂度O(n2)，调整系数λ时间复杂度O(n)，本文整体迭代次数为T,因此算法的时间复杂度为O(m×n2+3n2+n)。本文所提算法处理数据量较大时，可利用GPU对算法进行加速，增加算法的实用性。

3.2 算法对比

为验证ATSC-MDK算法的有效性，将使用三组人工模拟数据集和三组公共数据集进行实验对比。本文除了与SC算法比较，还将与ASC-MDK、FCM、TI-KT-CM、TII-KT-CM、TSC-IDFR算法进行对比。

实验采用归一化互信息(NMI)和兰德指数(RI)[26]两大常用方法作为评价标准。

(23)

式中：P(i,j)为同时聚类到U类和类标签为V的概率，P(i)为聚类到U类的概率，P′(j)为聚类到V类的概率。NMI取值范围为[0,1],越趋近于1，聚类效果越好。

(24)

实验环境：所用PC为Xeon处理器，2.8 GHz，16 GB RAM, 算法编程使用MATLAB2016a。

3.2.1 模拟数据集及实验

迁移学习的场景要求领域相关且不相同，为此本文在以下场景进行实验：

(1) 高斯分布迁移数据集M1-M2:如图6所示的低维人工模拟数据集。(a)为采用高斯概率分布函数随机生成4类共800个数据样本的源域数据集；(b)-(h)为采用高斯概率分布函数随机生成4类320个数据样本的目标域数据集。

图6 高斯分布迁移数据集M1-M2

(2) 双月型迁移数据集L1-L2：如图7所示，(a)不含噪声，共121个数据点且分为上下两类；(b)-(h)为受噪声干扰，共120个数据点且上下分类界限有重叠，边缘分布较复杂。

图7 双月型迁移数据集L1-L2

(3) Threecircles迁移数据集C1-C2：如图8所示，(a)为三个同心圆围起来的源域数据集；(b)-(h)为非同心圆，且有交叉的目标域数据集。

图8 Threecircles迁移数据集C1-C2

由图6-图8和表1可得：SC算法在人工数据集上表现效果较差，ATSK-MDK算法在两大评价指标上均高于其余对比算法，可以得到较好的聚类效果。

表1 人工模拟数据集的各类算法聚类效果对比

M1-M2：凸形数据集中，ATSC-MDK,TSK-IDFR是在SC算法基础上进行知识迁移,TI-KT-CM和TII-KT-CM是在FCM算法上进行知识迁移，经过表1数据聚类结果对比，均在原始算法上有所提升，说明在场景迁移中，来自源域的历史信息可以进行有效的迁移，提高目标域聚类效果。

L1-L2：L1为绝对流形数据集，L2目标域数据集为数据分布较分散，数据相互重叠的流形数据集，边缘数据分布较复杂，容易造成错误聚类，且为典型的非凸型数据集。在考虑数据流形分布的情况下，可充分体现流形距离优势。基于FCM下进行知识迁移的TI-KT-CM和TII-KT-CM很明显对于非凸形数据集聚类效果不佳，但效果依旧有所提升，进一步说明迁移学习的有效性。而SC算法可以适应任意形状的数据且不易陷入局部最优，所以对于非凸形数据集有明显优势。在此基础上，考虑到这种特殊的流形分布，ASC-MDK明显优于欧氏距离的SC，加入流形距离的ATSC-MDK算法明显优于欧氏距离的TSC-IDFR算法。且根据实验结果，在此种分布下，考虑数据的分布结构比加入迁移学习方法提升效果更为突出。

C1-C2：FCM是通过寻找聚类中心的方法进行聚类，在此种多流形分布下，聚类中心非常难找，没考虑分布结构的情况下，聚类错误率非常高，正确率不超过30%，所以隶属度进行迁移的TI-KT-CM,TII-KT-CM算法，提升效果微乎其微。此种形状的数据集，SC算法的优势非常明显，ASC-MDK算法可以更进一步考虑分布的全局一致性，面对复杂边缘分布，且可自适应调节，效果有所提升。ATSC-MDK针对以上问题，面对分布结构，边缘密度等复杂情况，聚类效果较好。

3.2.2 真实数据集实验结果分析

为了进一步验证算法的有效性，在三个公共数据集上验证，该数据集为迁移学习、聚类效果常用的验证数据集，具有一定的基准性。

(1) 数据集1：来自UCI的人类活动时间序列数据集。从中选取来自志愿者的6类自然活动：走路，上楼梯，下楼梯，坐下，站立，躺下。本文源域选取494条女性数据记录，目标域选取312条男性数据记录，并进行降维处理。

(2) 数据集2：来自ESF数据库的垃圾邮件数据集。本文源域使用公共消息资源的4 000条数据记录，目标域使用用户的1 800条数据。

(3) 数据集3：来自Brodatz纹理数据库。图9为源域纹理图像，图10为目标域纹理图像(有噪声)。通过滤波方法对纹理特征进行提取，且对维度进行处理，构成了最终TIS纹理数据。

图9 源域

图10 目标域

真实迁移场景数据与真实数据集的各类算法聚类效果对比如表2、表3所示。

表2 真实迁移场景数据

表3 真实数据集的各类算法聚类效果对比

由表2和3可得：ATSC-MDK算法在NMI和RI指标中均高于其余算法，虽然在人类活动序列数据集中，提高不太明显，但是在垃圾邮件数据集中提高比较明显，所以总体聚类效果有所提升。在考虑到数据的空间分布时，ASC-MDK在经典谱聚类的基础上对核函数机型改进，对比SC效果有明显的提升，说明考虑空间分布可以较好地提高聚类效果。TSC-IDFR中融合ASC-MDK所建立的ATSC-MDK算法，克服数据数量影响聚类性能的问题，对比SC聚类效果有很大提升。

真实目标域数据集与源域数据集分布相似但不相同，在分布时有一定的差异性，所以ATSC-MDK、TSC-IDFR、TI-KT-CM、TII-KT-CM均可获得来自源域的有用信息，提高目标域的聚类有效性。ATSC-MDK不仅选取有用数据集，考虑源域和目标域的空间分布特征，因此选取最有效的指导目标域的数据集，在一定程度上有效避免了负迁移。

4 结 语

为提高SC算法的领域适应能力，降低数据空间分布、样本数量等对其性能的影响，本文提出一种基于流形距离核的自适应迁移谱聚类算法(ATSC-MDK)。考虑数据分布的全局一致性，使用流形距离作为相似性计算方法，充分考虑全部局部邻域信息，对核函数进行自适应调整，提高谱聚类对复杂数据集的处理能力；考虑领域数据匮乏问题，引入迁移学习，使用源域的知识辅助目标域进行谱聚类。实验结果表明，本文算法性能与原始谱聚类算法相比有明显提升。