基于核协方差矩阵的无监督数据聚类

程 宁 戴远泉

(湖北轻工职业技术学院计算机学院 湖北 武汉 430070)

0 引 言

当来自同一类的数据向量彼此线性相关时,可以利用数据向量之间的相似性或距离度量进行聚类[1]。这样的模型已经在遥感信息、人类行为分类等领域得到了广泛的应用[2-3]。聚类效果的好坏对于分类以及识别精度等都会产生较大的影响,因此如何尽可能地提升聚类效果是大数据时代研究的热点[4]。

针对来自不同来源的信号或来自不同类别的不相关数据向量,已经有文献很好地探讨了使用线性相关来解决聚类问题。文献[5]提出了一种适用于线性数据模型的基于典型相关分析(Canonical Correlation Analysis,CCA)的聚类框架,将工作扩展到基于卷积神经网络的数据模型中。文献[6]讨论了一种半监督方法,在多视图环境中利用类间和类内的相关性实现聚类。文献[7]提出了一种基于旋转和投影的对称正交非负矩阵分解(Nonnegative Matrix Factorization,NMF)交替方法。

但是上述方法均是针对考虑数据中的线性相关性,针对数据中的非线性问题未提出解决方法。在过去几年中,许多不同的方法已经被提出来处理非线性传感器-源关系。深度NMF方法将矩阵分解为两个以上的因子,从而得到更适合聚类的低维模型[8]。核化或基于图的方法通过将数据映射到更高维空间或通过使用图正则化器惩罚代价函数来处理非线性数据模型[9]。在基于核CCA的聚类算法中,数据协方差矩阵被RBF核协方差矩阵代替[10]。文献[11]探讨了一种利用非线性数据关系进行聚类的基于图的方法,其中标准NMF代价函数由一个图正则化器补充。虽然上述方法考虑到了数据相关性中的非线性,但是方法十分依赖有监督训练来寻找合适的核或图,并且需要先验知识选择与数据相关的多个可调参数。

针对上述问题,提出一种基于核协方差矩阵的无监督数据聚类方法,通过数据集实验验证本文方法能够有效解决无监督聚类问题。

1 相关方法

1.1 问题描述

考虑从总共Q个类中获得的一组P个信号或数据向量。假定来自特定类的信号受相同的源信号影响。给定Q个源或类的总数,第i个信号向量为xi(n),存在

(1)

在不同的应用场景下,未知函数fj(·)可以是线性的或非线性的。在线性情况下,假设源信号sj(n)∀j∈{1,2,…,Q}是互不相关的,信号间的互相关可以作为相似性度量用于识别是否来自同一个源的或者属于同一类的信号。因此线性情况下的协方差矩阵可以表示为:

(2)

1.2 诱导稀疏

稀疏正则化矩阵分解可以表示为:

(3)

s.t.M≥0,N≥0

1.3 核化框架与核选择

(4)

核化矩阵分解的目标可以表述为:

(5)

基于矩阵分解的聚类方法的主要优点在于它们是无监督的,并且不需要任何训练数据。然而式(5)中所述的矩阵分解框架需要一个合适的核协方差矩阵,其性能在很大程度上取决于一个核的适当选择或多个核的线性组合。在文献中,核选择/学习任务主要是在有监督的环境下完成的,因此总体方案并非真正的无监督。

为了巩固块对角协方差矩阵的重要性,考虑Salinas数据集中来自4个不同类的高光谱图像像素的例子。每个高光谱像素是一个224维向量,其中每个维度代表特定频段的能量。像素是根据类标签排序的,因此来自同一类的像素一起出现。考虑在不同方差值上为这些像素计算的高斯核协方差矩阵族。在图1(a)-图1(c)中,有方差值分别为103.5、10-1.5和1010的核协方差矩阵。可以看出,对于高斯方差参数的高值和低值,高光谱像素之间的关系完全丧失,因为低方差表示所有像素都是独立的,而对于高方差则表示所有像素似乎都是相关的。但是,当方差设置得当时,如图1(a)所示,可以观察到块对角线行为,其中每个块代表来自同一类的像素之间的高度相关性以及属于不同类的像素之间的不相关性。

(a) σ2=103.5

(b) σ2=1010

(c) σ2=10-1.5图1 在核协方差结构中选择不同的核方差σ2的影响

命题1在由式(1)和式(2)描述的线性设置中,可以假定相关矩阵是块对角的。表示来自同一类的信号之间的高相关性的每个块对角可以被视为秩-1块,并且在具有Q类的数据集中,存在Q个这样的秩-1对角块。

(6)

因此,在具有Q个可能类的数据中,有效的核学习的目标是寻找具有基础映射φ(·)的核,该映射可以线性化高维空间中的相关性,使得对角线上有Q个秩-1的块,从而得到秩为Q的核协方差矩阵。

1.4 基于特征向量的核选择

对于实际应用,数据总是会受到某些噪声的破坏,而且数据向量的长度是有限的,因此只能评估实际协方差的估计值。因此,评估的协方差矩阵的秩几乎总是大于Q。为了在实际应用中施加秩Q约束,可以对Q个最大特征值的大小施加约束。但是最大化Q个特征值之和是不够的,因为图1(b)中考虑的形式的矩阵在所有项中的大小都是恒定的,并且会导致可行矩阵的强特征值小于Q。因此,重要的是不仅要最大化Q个特征值之和,而且要确保矩阵具有Q个强特征值。为此,提出可最大化第Q个最大特征值,以确保矩阵的秩至少为Q。

(7)

式中:函数Λi(.):RP×P→R表示输入自变量矩阵的第i个最大特征值。对于给定矩阵K,其定义为:

(8)

s.t.VVT=IQ

式中:IQ是Q×Q的单位矩阵;矩阵V的列是K的特征向量;V是一个P×Q的矩阵。

因此,第Q特征值最大的核协方差矩阵最适合于基于矩阵分解的聚类。鉴于核矩阵对于每个核参数的缩放比例可能不同,因此在找到特征值之前适当地对其进行归一化至关重要。由于本文方法着重于提高第Q个特征值的大小,因此适当的归一化策略是按所有特征值的总和缩放每个矩阵。因此,在归一化后,最大化第Q个特征值等效于最大化第Q个特征值相对于所有特征值之和的百分比份额。

式(8)中的特征值最大化问题也可以替代地用不同的形式表示为特征值和的差,即:

(9)

式(9)给出的凸函数公式的一个差为优化提供了一定的优势。然后,可以将基于第Q个特征值最大化的核学习目标表示为:

(10)

因此,总体聚类问题的目标可以这样表述:

(11)

如果存在B个字典核的线性组合,使得整个核协方差矩阵具有秩Q,则式(11)在其最小值处达到期望的解。

2 本文算法

2.1 非凸性

2.2 凸函数的差分算法

(12)

式中:∂H(Xk)是H(X)在Xk处的次梯度,上标k代表DCA的第k次迭代。

(13)

松弛目标函数可以表示为:

(14)

(15)

索引k是最外面的循环迭代索引,它计算所有三个参数M、N和α的更新。每个迭代k包含两个更新循环:(1) 在保持N=Nk-1恒定的同时更新M、α;(2) 更新N,保持M、α恒定。内循环根据索引p进行。在迭代p期间,评估基于式(13)的仿射优化器。然后,使用简单的基于次梯度下降或基于内部点的方法来解决具有主化近似的松弛问题。次梯度下降的迭代次数可以进一步由索引q表示。对于投影的次梯度下降情况,有关于M和α的次梯度为:

(16)

(17)

因此,在第p+1次迭代中迭代地重新评估式(13)中的仿射优化。总体算法在算法1中进行概述。

算法1基于核协方差矩阵的无监督数据聚类算法

1.初始化M和αj;

3.while

4.while|Mk,p-Mk,p-1|>thresh1do

5.N=Nk-1,p*;

7.使用式(16)更新M和αj直到收敛。

8.endwhile

9.while|Nk,p-Nk,p-1|>thresh1do

10.M=Mk-1,p*;

12.使用式(16)更新N直到收敛;

13.endwhile

14.endwhile

3 实验与结果分析

3.1 综合示例

作为核化框架的一部分,这里使用从两个最常用的核家族,高斯径向基函数(RBF)核和多项式核派生的不同的核矩阵。实际上,该字典可以由超出RBF和多项式的不同核族构建而成。高斯核和多项式核的表达式如下:

(18)

为了进一步解释本文算法,考虑了一个Q=4类的综合示例。来自4类的每一类都有15个向量,因此核矩阵的大小为60×60。为了提高可视化效果,在评估核协方差之前,应将来自同一类的向量视为有序/分组在一起。从图2(a)中可以看出,总共考虑了B=6个人工生成的核。从图2(a)的左上角开始,顺时针旋转,第一个核的值全部为零。下一个对类1和3的元素具有较高的协方差。下一个仅对类2具有较高的协方差。接下来的两个核表示不合适的信息,因为对角矩阵表示所有数据向量都是独立的,而常值核表示所有数据向量都来自同一类。图2(a)中的最后一个核表示来自类4的高度相关的向量。对于此设置,希望核学习对核矩阵2、3和6具有非零的αj值(从图2(a)中的左上角开始顺时针编号)。

(a) 6个输入核

请注意,用于聚类的基于稀疏性的矩阵分解框架依赖于不同类之间的不相关性。映射的特征空间中的转换数据必须满足此属性,而原始数据空间中的类并不一定是不相关的。确定非线性映射φ(·),以便在映射的特征空间中,来自不同类的变换后的数据元素可以不相关。因此,所提出的基于特征值最大化的框架可以用于识别映射,即具有块对角结构的适当的核满足映射特征空间中的不相关假设。

3.2 对比设置

在本节中,将使用多个数据集显示数值结果,以证明本文算法的有效性。在3种不同的设置下验证整个核学习和聚类框架的性能:(1) 高光谱图像数据集;(2) 基于智能手机的人类活动检测和文档分类数据集。

将本文方案的性能与5种不同的无监督算法进行比较:(1) 标准非负矩阵分解(NMF)[6];(2)
图非负矩阵分解(GNMF)[7];(3) Deep NMF(DNMF)[11];(4) 核典型相关分析(CCA)[10];(5) K-Means[9]。还展示了在10%和25%训练数据下的核支持向量机的结果,该核支持向量机方法为SVM与K-means结合的聚类算法(SK-Means)[15],从而对类似仿真环境下监督方法的性能进行对比。

对于GNMF和Deep NMF,对200多个不同的参数集进行了重复模拟,以确定适合每个数据集的参数。在GNMF情况下,进行了这200次参数选择重复以识别2个实体:(1) 权重图拉普拉斯相关项的alpha因子,其值在0.001～200之间变化;(2) 最佳关联图。对于每个参数组合,将结果平均10次重复。在Deep NMF情况下,本文在分析中使用了多达4个层,大小各异。对于不同的组合,分解层的数量在2至4之间变化,每层的大小在4至200范围内变化。每种组合在10次重复中再次取平均值。此处展示的结果是每个单独数据集的参数的最佳组合。

对于本文方法,确定了高光谱图像数据集的λ和μ值。首先,选择μ的值。为了使矩阵分解达到理想的结果,必须选择块对角核。因此,为了表示基于特征值的核学习任务的优先级,参数μ被赋予一个较大的值。这里尝试了100、25、10和1的值。从这10个中选出了一个。接下来,选择稀疏性参数λ。根据文献[3]选择了该参数的值。这些值以0.1的乘法步骤从1减少,即1、0.1、0.01和0.001等。由于会产生非零支持的稀疏矩阵因子,因此发现0.001的值就足够了,因此只需要4次迭代。所有数据集都使用相同的参数值,说明了所选参数和算法对不同数据集的鲁棒性,以及类数Q和数据向量数P的变化。

对于GNMF和Deep NMF的仿真,使用了相应论文作者提供的代码。对于核SVM,使用了MATLAB中具有自动缩放功能的内置实现,其中,使用训练数据自动选择了核参数。对于K-Means,也使用了MATLAB的内置实现,提出基于SVM的K-means聚类算法,该机制主要是首先对数据集节点进行初次聚类,找到聚类中心和簇群,然后对每个簇群内运用支持向量机算法使簇群内的不同类节点间距离最大化以减少分簇的风险,再对两两分类后的簇群重新划分簇并判断聚类中心是否改变,最后通过不停迭代直至达到最优的效果。聚类精度作为比较方法性能的度量。

3.3 活动检测

第一个数据集是基于米兰比可卡大学智能手机的人类活动识别(UniMiB)数据集。该数据集包含来自安装在30个不同用户上的智能手机的加速度计读数,这些用户执行一系列活动,包括步行、跑步和爬楼梯。信号被预分割为各个时期,每个时期的长度为51个样本,并以该时期的峰值为中心。沿着加速度计的每个XYZ轴考虑信号,因此,连接的信号长153个样本。目的是根据信号/向量所代表的活动类别对其进行聚类。

从步行、跑步和爬楼梯这3个活动来考虑各个时期。结果在所有30个用户上取平均值,并在图3中以箱形图的形式显示,方框中的标记是指中值准确度,而方框的边缘标记了所有实验中准确度的25%和75%。可以看出,所提出的框架的性能优于6个方案。对于Deep NMF情况,具有2个分别有50和4个特征的隐藏层的配置,对于GNMF情况,α=1.2,产生了最佳准确度。结果表明,相对于其他几种无监督算法,在数据集向量弱相关或者不相关条件下,本文方法能够保证较高的聚类精度,并且无须依赖先验知识调整参数。相对于有监督算法,本文方法无须依赖有监督训练就能够实现较高的聚类精度。

图3 UniMiB数据集的准确率比较的箱形图

3.4 高光谱图像

高光谱图像数据集代表了本文方法在遥感环境中的应用。此处考虑的图像已由位于加利福尼亚州萨利纳斯山谷的AVIRIS传感系统捕获,并具有224个维度,分别代表不同频段的能量。图像主要由农田组成,其中图像的不同部分存在不同的农作物/材料。每个像素观察到16种不同类型的材料/作物之一。目的是独立考虑每个像素,并根据它们观察到的材料将基于224维向量的像素聚类为不同的类。基本假设是:观察相同类的像素将具有相似的光谱反射率值。对于仿真,在每次迭代过程中,考虑一组Q=4种不同的随机选择材料,并选择15个随机像素表示这4类。在总共100个随机材料和像素选择上重复了该实验。

总体聚类精度可以在图4中看到。图4显示了100次实验的准确率的箱形图,在图4(b)中,在P=500像素的更大数据设置中,还展示了不同方法的准确度。从这些数字可以推断出,GNMF和本文方法在性能上彼此相似,并且都比经过10%训练的Deep NMF、CCA、K-Means和SK-Means聚类方法更好。在GNMF情况下,使用α=1的值。由于高光谱图像数据量较大,因此几乎所有方法的聚类精度都较高,随着像素的增大,数据量也随之增大,可以发现无论数据量的大小,本文方法的聚类精度均能保持较高的水平,而传统的SK-means聚类方法在训练数据大小不同时,聚类精度差距较大,说明有监督方法对于数据样本大小依赖性较强,而无监督算法对数据的依赖程度明显较低。相对于其他几种无监督算法,本文方法能够保证较高的聚类精度,验证了本文算法不仅不需要先验知识调整参数,而且在聚类精度能够得到保证。

(a) P=100

(b) P=500图4 Salinas高光谱图像数据集的准确率箱形图

3.5 文档聚类

第三个数据集是la2数据集,该数据集是使用《洛杉矶时报》的文章编译而成的,并已在TREC中使用。数据集包含6个类的3 075个文件,所考虑的文件至少有100个单词,因此考虑的文件总数减少到2 030。在此评估中,考虑了一组来自4个不同类的100个文件,从每个类中随机选择25个。与其他案例研究类似,这里的目标是将属于同一类的文档进行聚类。一个文档由一个向量表示,其中它的维数表示某个特定单词的出现频率。

在图5中给出了文档数据集聚类精度的箱形图。收敛时,α值对于对应于σ2=107、σ2=106和σ2=105的RBF核和度为2的多项式核的核矩阵具有显著的权重。对于Deep NMF情况,分别具有2个有200和4个特征的隐藏层的配置,对于GNMF情况,α=0.05,产生了最高的准确度。

图5 文件聚类数据集的准确率箱形图

由于该数据量较少,聚类结果表明在数据量较少的情况下,SK-Means聚类方法聚类性能明显下降,其他几种无监督算法的聚类精度相比之下也不够理想,而本文方法依旧能够保持相对较高的聚类精度。总体而言,由于核学习组件可确保来自不同类的元素之间具有弱相关性,而类内数据则具有强相关性,而l1-l2惩罚矩阵分解框架可实现无监督的准确聚类,因此该新型框架具有更好的聚类性能。说明即使在数据匮乏的情况下,新框架也可以实现更好的聚类性能,即提出的框架在不依赖于数据训练以及参数先验调整的条件下,能够在无监督条件下实现良好的聚类性能。

3.6 计算成本分析

进一步分析各个数据集上相应方法的计算时间,如表1所示,本文方法虽然较其他以先验知识为基础的无监督算法的计算时间要长,但是其计算时间整体上与有监督算法相差不大,主要因为有监督方法需要大量的时间进行训练,这进一步证明了本文方法在计算时间上具有实用性。

表1 算法计算时间对比 单位:s

4 结 语

为解决数据向量聚类模型过于依赖先验知识以及有监督训练问题,提出一种基于核协方差矩阵的无监督数据聚类方法。通过高光谱图像、人类活动、文档分类三个数据集的验证表明:

(1) 本文算法针对不同的数据集均能表现出较好的聚类性能,验证了算法对于数据集具有较强的泛化性能。针对非线性数据类之间相关性较弱等问题,本文方法能够实现较好的聚类效果。

(2) 本文方法的聚类性能不仅较优于有监督以及其他几种无监督算法的聚类性能,而且能够解决监督训练依赖性以及无监督参数选择难的问题。在数据量稀疏或者先验知识不足条件下,依旧能够实现良好的聚类效果。

(3) 本文方法计算成本相较于其他方法并无增加,进一步说明本文方法具有较好的实用性能。