基于从共现矩阵提取关联的类别型数据聚类

关云鹏,刘玉龙

(华北计算技术研究所系统八部，北京 100083)

0 引 言

近几十年来，随着现代科学技术的进步，人们获取数据的能力大大提升，不仅仅是数据量层面的大大提高，而且数据类型也是多种多样。由于信息的大幅增长和对数据内在信息的分析需求，数据挖掘技术应运而生。数据挖掘实现从数据中提取隐藏的但有用的信息。聚类分析是数据挖掘和机器学习中一种常见的研究工具，它可以在不使用先验知识的情况下将数据集划分为多个聚类，将数据集分组成簇，使得同一类别中的对象相互之间尽可能相似，不同类别之间，尽可能不同[1]。聚类的过程可以定义为[2]：“给定N个对象的表示，根据相似度的度量，找到K个组，使同一组对象之间的相似度高，而不同对象之间的相似度低。”聚类分析技术已经被用到众多领域中，比如：市场研究、医学科学、计算机科学等。

类别型数据聚类是针对类别型的数据进行聚类分析，类别型数据相比于数值型数据的最大区别是，特征值之间没有天然的距离，且类别型数据的特征值是离散的，比如颜色的特征值是红色、橙色、黄色等[3]。常见的类别型数据聚类是通过使用相似度量来完成的，例如最常见的类别型数据聚类方法k-modes[4-5]提出的简单匹配不相似度(Hamming距离)，但是汉明距离往往会导致聚类具有弱的内部相似性(intra-similarity)[6]，往往获得较低的准确度。基于相异度量的研究，不仅受到数据集本身特点的影响较大,而且噪音信息还会影响最终结果。基于表示学习的类别型数据聚类，虽然可以考虑数据内部耦合关系，但实现流程复杂，而且表示结果对最终聚类结果影响大，由于不同表示学习方法捕获不同数据集的能力不同，结果容易受到数据集自身特点的影响。

因此，本文提出一种基于从共现矩阵提取关联的类别型数据聚类方法。在真实的16个具有多种数据特征(包括多维度、多值对象)的类别型数据集上，与8种不同的类别型聚类方法的聚类效果进行对比。本方法是一种创新性的尝试，方便有效，在实验中取得优秀的成绩，这为未来各个领域展开类别型数据聚类任务扩展了一个新思路。

1 相关工作

类别型数据聚类已经被应用到众多领域中，研究角度也是各有不同，本章从4个角度介绍类别型数据聚类相关研究，基于相异度量的类别型数据聚类、基于相似度量的类别型数据聚类、基于类别型数据表示的聚类方法研究和聚类集成算法。

关于相异度量，有一种匹配方法，即将2个相同分类属性的值的相异度量记作0，不同的记作1。这种方法被广泛应用在类别型聚类方法中，如k-modes方法和其改进方法k-prototype[7]。Huang等人[5]研究的fuzzy k-modes方法，是为了优化划分不确定边界对象。文献[8]提出由属性在类内出现的频率计算2个属性之间的距离。在此度量基础上，Cao等人[9]又结合前边提到的0-1匹配，提出了一种将整个数据属性值的分布引入到相异度量的研究算法。

CACTUS[10]类别型数据聚类指出了每2个属性值的相似度由它们与一组属性值的共现程度来决定。除此之外，Ahmad等人[11]在2个属性值共现概率基础上进行了改进，提出了一种新的混合属性聚类方法。该方法对不同的属性赋予不同权重，在一定程度上改进了同一属性下2个属性值的相异度量，但是也忽略了自身的异同。

类别型数据聚类还可以在类别型数据表示基础上再进行聚类，得到最终聚类结果。表示学习是为了学习数据内部的耦合关系，得到的表示结果更有利于类别型数据聚类的进行。文献[12]提到在类别型数据中表示更多的耦合关系可以提高最终聚类结果。但是，有研究提到，捕获更多但是重复性的耦合关系并不能保证结果的提升[13]。对称不确定性(SU)准则使得在具有多个耦合的几种分类数据表示方法中具有更好的表示性能[13-14]。文献[15]中的方法使用主成分分析来减少耦合之间的冗余提升性能。还有深度表示学习的方法也用于类别型数据聚类的研究，有利用神经网络结构的autoencoder[16]，也有利用对抗学习的BiGAN[17]和VAE[18]。

此外，聚类集成也可以应用到类别型数据聚类领域，由于类别型数据的数据特点的特殊性，在每个属性下的属性值都是离散的。类别型数据在每个属性中的数据可以看作是在该属性子空间下的聚类集合结果，最后将各个集合进行集成得到最终聚类结果。最近，有的研究提出了一个度量来反应集合之间的一致性和不一致性[19]，使用加权聚类上的耦合集成选择策略提高性能。另外还有通过构建共现矩阵和coherent-link矩阵组合为三维向量[20]的方法去提高性能。

2 基于从共现矩阵提取关联的类别型数据聚类方法

2.1 方法概览

本文方法的概览示意图如图1所示，输入为类别型数据，输出为最终的聚类结果。如图1所示，输入数据定义为[A1,…,AM]，表示类别型数据的各个属性列，然后根据不同属性子空间中的共现频率信息构建共现矩阵CM。共现矩阵中的每个元素都在0～1之间，且这些数据元素是离散的。矩阵的大小是N×N，N为类别型数据集的对象个数。在共现矩阵基础上，通过将那些小于不同阈值的矩阵元素设置为0，来生成重构矩阵。图中的C(i,j)

图1 方法概览示意图

2.2 共现矩阵的构建

本方法的基础是构建共现矩阵，共现矩阵刻画了在不同属性列下数据共同出现的频率，它可以看作是用于聚类的相似度矩阵。本文主要研究如何根据这个矩阵检测聚类结构。类别型数据X拥有M个属性列，即[A1,A2,…,AM]。每个属性列都由几种分类离散值组成，表示为Ai={Ci1,Ci2,…,CiKi}，Cij是Ai的第j个离散型分类值，Ki是Ai中分类值数。设A={C1,C2,…,CK}是最终的聚类结果，其中K是A中的最终聚簇数目，Ci是A的一个聚簇结果。共现矩阵(CM)的定义如下[21]：

(1)

其中，Cmb是Am中的第b个分类离散值，P(i,j,Cmb)表示为：

(2)

图2 共现矩阵生成图

算法1 计算共现矩阵

输入：类别型数据X=[A1,A2,…,AM]。

输出：共现矩阵CM。

Step1计算数据集行数N，列数M；

Step2初始化共现矩阵；CM←zeros(N,N)；

Step3第一层循环fori=1:M；

Step4初始化标识矩阵s←zeros(N,max(Ai)+1)；

Step5第二层循环forj=1:N；

Step6计算标识矩阵s，判断Ai(j)是否等于k-1，其中k∈[1:max(Ai)+1]。如果等于，则s(j,k)←1，结束第二层循环；

Step7计算连接矩阵ConnectM=s×sΤ；

Step8CM←CM+ConnectM，结束第一层循环；

Step9CM←CM/M。

2.3 共现矩阵切除噪音

类别型数据的聚类结果是在共现矩阵基础上切除噪音信息，再利用归一化切割得到的，所以共现矩阵在一定程度上可以反映出聚簇的结构，然而直接观察是很难分辨的，这里利用了VAT[22]算法对原始矩阵进行重新排序，得到全新的排列有序的共现矩阵OrderCM，相比而言，OrderCM矩阵更容易看到聚簇的结构信息。共现矩阵和OrderCM矩阵灰度图像对比如图3所示。图3采用的数据是2.2节中构建共现矩阵使用的数据，左侧为原始的共现矩阵，右侧为重新排序的OrderCM矩阵。其中VAT算法流程如算法2所示，该方法处理原始数据的共现矩阵CM，重新排列，越相似的数据会被排列的更紧密。但是OrderCM矩阵和共现矩阵同样都能反映出聚簇的结构，只是OrderCM矩阵观察聚簇的结构信息更直观。

图3 共现矩阵和OrderCM灰度对比图

算法2 VAT算法

输入：N×N的共现矩阵CM。

输出：重新排列的OrderCM=[ocmij]。

Step1构建不相似矩阵DM=[dmij]←(1-CM)；

Step2J←{1,2,…,N};I←∅;P←(0,0,…,0)；

Step3[i,j]←argmaxp,q∈J{dmpq}；

Step4P(1)←i;I←{i};J←J-{i}；

Step5第一层循环forl=2:N；

Step6[i,j]←argminp∈I,q∈J{dmpq}；

Step7P(l)←j;I←I∪{j};J←J-{j}，结束循环；

Step8遍历赋值[ocmij]←[dmP(i)P(j)] ，1≤i,j≤N。

为了直观地展示剔除共现矩阵里的噪音信息会影响聚类结果，在重新排序后的OrderCM矩阵上，尝试切除一些低频信息，即影响聚类结果的信息。处理过程如图4所示。图4采用的数据集为path-based[23]数据集。图4(a)表示OrderCM矩阵切除噪音数据前的灰度图像，图4(c)表示OrderCM矩阵切除噪音数据后的灰度图像，图4(b)、图4(d)为对应得到聚类结果图。图4(a)中虚线标注的矩形区域为切除的4个低频噪音区域，很直观地看出，切除这些噪音数据后，聚类结果得到优化。下面结合定理1从理论层面，分析一下切除这些噪音信息会得到较好的聚类结果。其中切除噪音后的共现矩阵会被归一化切割处理，实现聚类划分的目的，详细介绍见2.4节。

图4 OrderCM矩阵切除噪音数据聚类对比图

定理1 假设类别型数据X是由2个聚簇组成的，分别记为P和W。现在利用VAT算法对其共现矩阵重新排列，将P和W划分为很多聚簇子集，记作{P1,P2,…,Pm}和{W1,W2,…,Wn}。假设Pi(i∈[1,m])和Wj(j∈[1,n])之间没有任何关联，Pi(i∈[1,m])和Pj(j∈[1,m])以及Wi(i∈[1,n])和Wj(j∈[1,n])之间存在着相似关联，则归一化切割(Ncut)可以得到最好的聚类。

定理1证明：在本文研究问题中，归一化切割Ncut[24]的目标函数为：

(3)

其中要求f(P,W)尽可能小，目标函数越小，聚类效果越好。

根据定理1假设，可知∀i∈[1,m],j∈[1,n]，使CM(Pi,Wj)=0则CM(P,W)=0；∃i∈[1,m],j∈[1,m]，使CM(Pi,Pj)>0则CM(P,P)>0；∃i∈[1,n],j∈[1,n]，使CM(Wi,Wj)>0则CM(W,W)>0。由归一化切割的目标函数，即公式(3)，计算得f(P,W)=0。

反之，∃i∈[1,m],j∈[1,n]，使得Wj⊂P和Pi⊂W，即∃i∈[1,m],j∈[1,n]，使得CM(Pi,Wj)>0，则CM(P,W)>0。同时保证条件CM(P,P)>0和CM(W,W)>0，由公式(3)计算得f(P,W)>0。综上所述，通过假言推理可得，假设成立时，归一化切割的目标函数最小，故可以得到最好的聚类，证毕。

上述定理可以表明，切除部分相似关联可以得到好的聚类结果，经过实验测试发现，切除的相似关联是共现矩阵中共现频率值较小的元素，从图4中也可以发现这一点。由于去除噪音信息是有助于聚类效果提升的，2.5节中的算法3实现了对共现矩阵切除低频噪音信息，再进行归一化切割得到聚类结果。

2.4 归一化切割

归一化切割(Ncut)[24]最早是解决图像分割问题的方法，文献[24]将图像分割问题转化为最小割问题，并完善了普通最小割算法的缺陷。Ncut的目标函数表示为公式(4)。A和B都是点集合，V是图像像素的全部点集，其中A∩B=∅，cut(A,B)表示分割A和B的割集权值和，assoc(A,V)表示A与全部点相连的权值和。

(4)

本文可以将去除噪音信息的共现矩阵CMα输入到归一化切割算法中，即将CMα视为一个图像的像素关联矩阵。矩阵CMα中的每个元素表示2个对象的共现概率，相应可以看作一个像素点到另一个像素点的相似程度。按照像素点之间的相似程度来确定区域划分，将相邻像素点之间的相似程度视为边，则相似程度越高，边代表的权重值越大。由于不同聚簇的相似度小，所以聚簇边缘连接边的权值也较小，从而找到区域边界，实现了聚簇的划分。因此，本文考虑将归一化切割目标函数设置为公式(3)。在下一节的CDCBCM算法中，将归一化切割融入到整体算法流程中。

2.5 CDCBCM算法

基于从共现矩阵提取关联的类别型数据聚类的步骤如算法3，整体梳理了从输入类别型数据X和标签label，到输出最终聚类结果bestC的流程。其中设置切除阈值p，表示不超过多少的共现频率值会被切除，本文将从0开始，切除步长设置为0.01，一直增长到阈值p结束。label的输入是为了对齐结果BestMap和计算F1-score值，K表示聚簇的种类数。

算法3 CDCBCM算法

输入：X=[A1,A2,…,AM]和原始标签label。

输出：bestC=[C1,C2,…,CK]。

Step1计算共现矩阵CM=GenCM(X)；

Step2T←[0,0.01,0.02,…,p];C←∅；

Step3第一层循环fort∈T；

Step4更新CMα←CM；

Step5遍历CMα(i,j)(i,j∈[1,N])，如果CMα(i,j)≤t，则CMα(i,j)←0；

Step6C←Ncut(CMα,K)；

Step7结果对齐C←BestMap(label,C)；

Step8F1←F1score(label,C)；

Step9比较并更新最好的F1和最好的聚类bestC；

Step10结束循环。

3 实验测试与分析

3.1 实验设计

本次实验环境使用Windows10系统，AMD Ryzen 7 5800H，编码使用Matlab2016a软件环境以及Python3.8版本。

本文采用了16种不同领域的真实公开数据集进行实验测试，其中包含医疗领域的Hepatitis、Spect、Audiology、Primarytumor和Dermatology；基因科学领域的DNAPromoter、DNANominal和Splice；分层决策数据Krvskp；自然领域的Zoo、Soybeanlarge、Flare和Mushroom；商业领域的Crx；灾难预测相关领域的Titanic；合成数据ThreeOf9。数据集的具体参数如表1所示。

表1 数据集详细参数情况表

本次实验对比方法有，传统的基于汉明距离的k-modes算法、将数据分布引入相异度量的Rough[9]、基于共现程度的Ahmad[11]、基于类别型数据表示的CDE[15]、COS[14]、DILCA[13]，以及深度学习方法BiGAN[17]和VAE[18]。最后还与一种聚类集成算法LTA[20]进行比较。

本次实验采用F-score[25-26]来评估CDCBCM算法的性能，设置F-score中参数β=1，得到F1-score如公式(5)，分值越高表示聚类的效果越好。除此之外，为了进一步比较上述对比方法和本方法的性能，通过Friedman test和Bonferroni-Dunn test[27]这2种方法计算平均排名并对比性能。

(5)

3.2 方法对比与分析

在实验中，由于数据集众多，为了确保能得到更好的聚类结果，对不同数据集CDCBCM算法设置不同的切除阈值，最终结果取多次切除后归一化切割聚类的最好成绩，除此之外，对比方法中基于表示的方法需要在表示学习后，将数据输入到相应聚类方法中，如CDE、BiGAN和VAE的表示结果被输入k-means中，COS、DILCA的表示结果被输入到k-modes中。类别型聚类实验结果的F1-score百分比对比如表2所示。

表2 F1-score百分比方法对比表 单位：%

表2中每行加粗标注的数值表示在此数据集下，对应的算法得分最高，算法性能最好。可以看出在实验的16个真实公开数据集中，本文提出的CDCBCM算法在7个数据集中得到分值最高，如DNANominal和Mushroom。在DNANominal数据集上，本方法得到71.26%，相比其他最好方法DILCA，提升了12.08个百分点；在Mushroom数据集上，本法得到88.05%，相比其他最好方法COS，提升了5.14个百分点。在没有得分最高的数据集中，本方法也可以和其他方法取得接近的结果。

表3 对比方法平均排名表

为了更直观地了解算法的性能，根据表2的结果计算了各个方法的平均排名，得到表3对比方法平均排名表，平均排名是根据算法在不同数据集上的排名进行算数平均得到的。可以看到CDCBCM算法比其他的最好算法CDE的排名(3.38)还高1.13个排名，相比表现差的VAE算法提高了5.56个排名。

图5 Bonferroni-Dunn检验各方法对比图

3.3 超参数测试

在实验过程中，本方法需要设置一个超参数，即切除阈值p，设置不同的值表示在共现矩阵中要切除不同范围的频率数据，相应也会得到不同程度的聚类结果。虽然设置较高的阈值，在切除过程中也能找到最合适的切除阈值和得到对应的聚类结果，但是设置过高阈值会引起计算资源的浪费。相反，设置过低的阈值也不可以，过低的阈值可能导致无法完全切除噪音数据，不能得到最优的聚类结果。为更清楚表现切除不同频率数据信息带来的变化，以数据集DNAPromoter为例，切除共现矩阵中的频率值从0～0.5，步长为0.01，F1-score百分比变化如图6所示，可以发现切除不同频率的数据信息，会得到不同程度的聚类效果，其中在切除频率达到0.32和0.33时，得到最好的结果。但是切除频率过高也会导致结果变差，所以设置合适的切割阈值既可以保证能够得到最好的结果也可以避免不必要的计算。

图6 数据切除的F1-score变化趋势图

因此，设置一组阈值参数对比实验，以DNAPromoter、Flare、Titanic、ThreeOf9数据集为例，并且切除阈值p分别设置为如下数值[0.05,0.1,0.15,0.2,0.25,0.3,0.35,0.4,0.45,0.5]，记录最好的F1-score百分比，如图7所示。从图中可以看出在不同数据集下，达到最好结果的阈值设置各有不同，有的在p=0.05下就达到最好结果，有的则需要p=0.45。

图7 不同阈值下的F1-score变化趋势图

3.4 其他优势

前面提到，部分聚类集成算法也可以解决类别型数据聚类问题，如文献[20]。可以将类别型数据的不同属性列下的数据看作是不同的聚类结果，输入到聚类集成算法得到最终的聚类结果。本文中的CDCBCM算法和文献[20]中提出的方法LTA相比，CDCBCM算法能直接利用数据的原始信息并得到好的聚类结果，而LTA算法更依赖于原始基准聚类算法的质量。实验结果如图8所示，在这些数据集上，可以看到，LTA算法直接针对原始类别型数据表现结果较差，整体性能弱于CDCBCM算法，本算法可以更好地从原始数据捕获关联信息，进而得到较好的聚类结果。

图8 方法性能对比图

4 结束语

本文在共现矩阵的基础上，提出了一种从共现矩阵提取关联信息的类别型数据聚类方法。首先通过原始信息构建共现矩阵，在其基础上切除噪音数据信息，本文也证明了切除数据信息能带来聚类结果上的提升，并可视化展示聚类优化结果。对切除数据信息后的共现矩阵进行归一化切割即可得到最终的聚类结果。

在真实的16个不同领域的公开数据集中，本方法与8个方法进行比较，结果表明本方法与大多数方法相比有较大优势，并取得最好的平均排名。本文还展示了切除阈值p对实验结果的影响。与LTA算法相比，本方法能更好地从原始数据捕获有用的关联信息。总的来说，本文为类别型数据聚类提供了一种新的解决思路，并且切除数据信息时设置的阈值p的选择问题仍可以继续进行研究。