拓展差异度的高维数据聚类算法

武 森，何慧霞，范岩岩

北京科技大学 经济管理学院，北京 100083

1 引言

高维数据聚类是文本挖掘、客户管理以及图文声像等应用领域的常见研究课题[1-3]。大部分传统聚类算法为低维数据而设计，但是当数据量和数据维数呈指数增长时，传统算法的局限就日益显现[4]。高维数据具有稀疏性、维度灾难等特性，并且噪声变量降低了在所有维中识别类的可能性[5]。如何在高维数据下进行有效的聚类，成为一项有意义且具有挑战性的课题。

CABOSFV[6]是一种针对高维数据的稀疏特征进行聚类的算法，只需对数据进行一次扫描就能生成最终聚类结果，计算效率大幅提升。CABOSFV算法因其高效性帮助解决了一系列高维数据聚类问题，黄月等[7]采用CABOSFV 的思想构建了基于“文献-关键词”矩阵的知识结构识别方法；Wang 等[8]基于CABOSFV 对肺癌患者的症候进行聚类，归纳出肺癌的三种中医证候分类；刘希宋等[9]将CABOSFV用于客户知识管理的应用场景中，验证了CABOSFV 相对于传统聚类算法的优越性。然而CABOSFV 由于参数指定复杂性和顺序敏感性造成了聚类结果不稳定。文献[10]采用层次聚类的思想，绕过了参数指定的要求并避免了数据对象的输入顺序对聚类结果的影响，但其改变了CABOSFV 的效率优势，增加了算法的计算复杂度，随着数据数量和维数的增加，算法的时间效率明显降低。

如何在保证并进一步提高算法效率的同时获得更高的聚类质量成为本文研究的出发点。基于此，针对CABOSFV算法数据对象分配受类大小影响这一问题，提出拓展差异度的CABOSFV_D 聚类算法。引入调整指数p，拓展稀疏差异度度量方式，降低类中对象个数对对象分配的影响，使聚类过程更加准确合理。在此基础上结合位集（BitSet）运算速度快的优点，提出用位集的方式实现CABOSFV_D 算法，提高算法的运行效率。基于六个UCI标准数据集进行聚类实验，分析讨论调整指数的分布范围，并给出确定差异度上限的方法。

2 相关工作

2.1 高维数据聚类

目前对高维数据的聚类主要包括：基于降维的聚类[11-12]、子空间聚类[13-14]、基于超图的聚类[15]以及基于稀疏特征聚类[16]。基于降维的聚类，通过特征选择[17-18]或特征变换[19]对高维数据进行降维处理再完成聚类。这类算法应用广泛，但其不足在于：降维后数据空间改变，可能损失部分重要聚类信息。由于高维数据在全维空间进行聚类比较困难，一些学者利用子空间思想在相同数据集的不同子空间中发现类。子空间聚类可以从多角度、多属性综合考虑来进行聚类，但其缺陷是子空间的划分和选取标准难以界定。基于超图聚类算法的主要思想是把高维数据处理问题转换为图划分问题，可以根据用户需要灵活调整聚类效果和质量，但相关参数的选取将直接影响着聚类质量的好坏。还有一类针对高维数据的稀疏特征进行聚类的算法，代表算法是CABOSFV算法[6]，将在下一部分进行介绍。

2.2 CABOSFV算法

CABOSFV算法是针对二态变量高维稀疏数据的高效聚类算法。该算法定义了集合的稀疏差异度（SFD），反映二态变量高维稀疏数据集合中对象的相似性。CABOSFV算法还定义了稀疏特征向量（SFV）及其可加性定理，能够实现只对数据进行一次扫描就完成聚类。因此，CABOSFV算法可以节省大量数据扫描和比较的时间，计算效率得到很大的提高[20]。CABOSFV 算法具有高效性，但受参数指定和输入顺序的影响造成聚类质量不稳定。现有的相关改进算法[10]对聚类过程进行调整和优化，以避免上述缺陷，但是增加了算法的复杂性，聚类效率受到较大影响。如何在保证算法效率的同时提高聚类质量是本文要解决的一个问题。

稀疏差异度是CABOSFV的一个核心概念，其计算公式为SFD(X)=e/(|X| ×a)，其中 |X|指集合X中的对象个数，e为该子集中所有对象取值不全相同的属性个数，a为取值全为1的属性个数。阈值b是算法的一个参数，代表一个类内对象的差异度上限。稀疏差异度SFD 和阈值b共同决定当前对象是否被分配到集合X中。根据CABOSFV算法步骤，当前对象需要从已存在的k个类中寻找与其合并后稀疏差异度最小的类，然后根据差异度上限b判断是否加入该类。然而随着现存集合中的数据对象逐渐变多，即 |X|变大，|X|这一项对SFD的影响起到主导作用，使得即使不是十分相似的对象构成集合的SFD 也很小，小于等于提前指定好的b，从而把本不太相似的对象分到同一类。即CABOSFV算法更倾向于将对象分配到数据对象较多的类中。针对上述问题，提出一种拓展差异度的CABOSFV_D聚类算法。

3 CABOSFV_D聚类算法

针对CABOSFV算法稀疏差异度的不足，本文提出拓展的差异度度量方式，同时用位集实现算法，使聚类效果和计算效率都得到提升。

3.1 拓展的差异度度量方式

在CABOSFV算法中，集合的稀疏差异度SFD是计算相似度的基础，由于集合内的差异度决定了是否将当前对象加入到某一集合（类），因此其在算法流程中起到至关重要的作用。通过分析传统CABOSFV 中稀疏差异度计算公式的局限性，发现问题主要在于算法的执行过程中稀疏差异度公式中数据对象 |X|变化幅度过大，调节趋势过度，而e a这一项的变化趋势缓慢。因此，提出一种拓展的集合稀疏差异度定义方式。

定义1（拓展集合差异度）设具有n个对象的二态数据集合{x1,x2,…,xn} ，X为其中的一个对象子集，其中的对象个数记为 |X|，在该子集中所有对象稀疏特征取值皆为1的属性个数为a，稀疏特征取值不全相同的属性个数为e，p为大于等于1 的常整数，则集合X的拓展差异度表示为：

拓展的稀疏差异度通过给定指数p，调整稀疏差异度公式中分母的变化幅度，使不相似的对象不会误分到同一类，增强算法的合理性。传统CABOSFV的稀疏差异度是该拓展定义p=1 时的一种特殊情况。

假设{x1,x2,…,x10} 是由属性{a1,a2,…,a5} 描述的数据对象，每个数据对象的各属性取值以及外部类标签如表1 所示。给定差异度上限b=0.5，分别使用原始差异度计算公式(p=1) 和拓展的差异度计算公式(p≥1)进行聚类。使用原稀疏差异度聚类的对象分配过程为：（1）将每个数据对象视作一个集合；（2）计算，将集合和合并到一个新类中，即={x1,x2}；（3）计算SFD(⋃)=5/(3×0)=∞＞b，将视作一个新的类，即；（4）计 算，且，因此将集合（5）对于集合，进行类似于（4）的操作，可得{x1,x2,x4,x5,x6} ；（6）对于集合，计算SFD(⋃)=b，因此将加入类中，={x1,x2,x4,x5,x6,x7,}。此时发现使用原始差异度聚类，前六个对象分配结果和实际情况相符，然而随着类内对象个数的增加，对象x7被误分到了标签为1的类中，实际上x7和标签为1 的对象（如x6）并不相似。与原差异度公式中p仅能取1 不同，使用拓展的差异度度量方式进行聚类时，指数p可取大于等于1 的常整数，此处以p=2 为例，前6个数据对象的分配结果和使用原始差异度聚类的结果是一致的。对于对象x7，计算SFD(X7(0)⋃X1(1))=，因此将视作一个新的类，即={x7} ，和实际情况相符。通过进一步分析发现p取3、4等值时也能得到正确的聚类结果。因此说明和原差异度p仅能取1的计算方式相比，拓展的集合差异度具有调整分母的变化幅度的能力，从而能够更加准确地进行对象的分配。

表1 十个数据对象取值描述

3.2 位集及位集差异度

位集是一种特殊的数据结构[21]，由二进制位构成，保存l、0信息。CABOSFV_D算法适用于二态变量高维稀疏数据，结合二态变量仅有1和0两种取值的特殊性，以及位集保存l和0信息这种特殊的数据结构。本文提出用位集的方式实现CABOSFV_D聚类算法，把对象用位集表示，继而所有的稀疏差异度的计算也通过位集运算完成，从而保证整个算法用位集实现。另外，由于位集的大小按需增长，数据维度的增加对位集的构建与运算没有影响，分类属性采用独热编码[22]的方式转化为二态属性没有信息的损失，因此基于拓展差异度的CABOSFV_D算法同样适用于分类属性聚类问题。

3.2.1 二态数据对象的位集表示

为了有效地运用位集运算进行二态数据对象聚类，需要将描述每个对象的所有二态数据全部存入位集中。假设具有n个对象的二态数据对象集合X={x1,x2,…,xn}，描述对象的m个属性集合为A={a1,a2,…,am} ，属性aq(q∈{1,2,…,m} )均有两种取值，即1 或0。对于每一个对象xi,i∈{1,2,…,n} ，将其所有属性值按位存储到位集中，记为B(xi)，称为对象xi的位集表示。其中，第1 位存储属性a1取值的信息；第2 位存储属性a2取值的信息，以此类推。存储一个对象的位集所需的位数为m。按照这种方式将描述每个对象的所有二态属性数据以二进制形式全部存储到位集中，不同的对象对应不同的位集，且不损失任何属性信息，继而可以有效地运用位集运算进行二态变量高维稀疏聚类。

3.2.2 位集差异度及性质

为将拓展的稀疏差异度计算公式SFD(X)=e/用位集的方式表示，先给出位集差异度的定义。

定义2（位集差异度）设二态数据集合表示X={x1,x2,…,xn} ，B(xi)和B(xj)分别为对象xi和xj的位集表示，则这两个对象之间的位集差异度d(xi,xj)定义为：

其中，B(xi)ORB(xj)和B(xi)AND(xj)分别表示对应的位进行逻辑或（OR）和逻辑与（AND）运算，结果仍然是位集；| |表示取值为1的位数。根据该位集差异度定义，两对象间取值不同的位数越多，且取值皆为1 的位数越少，则两个对象越具有较大的差异性。根据逻辑与（AND）和逻辑或（OR）运算满足幂等率和交换率，位集差异度满足性质：（1）d(xi,xi)=0 ；（2）d(xi,xj)=d(xj,xi)。

定义3（位集差异度推广）X={x1,x2,…,xn} 为二态数据集合，设B(xi)为对象xi,i∈{1,2,…,n} 的位集表示，且记BOR(x1,x2,…,xn)和BAND(x1,x2,…,xn)分别为：

其中BOR(x1,x2,…,xn)和BAND(x1,x2,…,xn)仍然是位集，将两个对象之间的位集差异度定义推广到集合X={x1,x2,…,xn} 内各对象之间位集差异度的定义为：

根据位集差异度推广的定义，n个对象取值不同的位数越多，及取值皆为1 的位数越少，代表这n个对象间的差异越大。其中两个对象之间的位集差异度是位集差异度推广的定义在集合中只包含两个对象时的一种特殊情况。下面给出计算任意两个非空子集合并后的差异度公式。

设二态数据集合表示X={x1,x2,…,xn} ，Y和Z为X的任意两个非空子集，则Y和Z合并后的差异度表示为：

式（6）表明，当X的任意两个非空子集Y和Z合并时，可以根据关于Y的位集BOR(Y)和BAND(Y)及关于Z的位集BOR(Z)和BAND(Z)直接计算得到关于合并后集合的位集BOR(Y⋃Z)和BAND(Y⋃Z)及位集差异度d(Y⋃Z)。特别地，当Y=Z时，d(Y⋃Z)=d(Y)=d(Z)。

3.3 CABOSFV_D算法步骤

基于拓展差异度的CABOSFV_D算法步骤如下：

输入：对象xi的位集表示B(xi),i=1,2,…,n；阈值b；指数p。

输出：类X1,X2,…,Xc。

步骤1计算BOR(x1,x2)和BAND(x1,x2)，根据定义2中的公式（2）得到x1和x2的位集差异度，若合并后的位集差异度不大于阈值b，则类为X1={x1,x2} ，类的个数c=1；否则，将两个对象分别作为一个初始类，即X1={x1} ，X2={x2} ，类的个数c=2。

步骤2对于B(x3)，分别计算BOR(Xk⋃{x3} )和BAND(Xk⋃{x3} )，k∈{1,2,…,c} ，根据公式（6）得到集合Xk⋃{x3} 内各对象间的位集差异度d(Xk⋃{x3} )，寻找使得该位集差异度最小的k0，对应的类为Xk0。若求得的最小的位集差异度不大于阈值b，则类Xk0=Xk0⋃{x3} ，此时类的个数c不变；否则，新建一个类Xc+1={x3} ，类的个数更新为c=c+1。

步骤3对于B(xi),i∈{4,5,…,n} ，重复进行类似于步骤2的操作。

步骤4输出类X1,X2,…,Xc。

从上述算法步骤可知，CABOSFV_D的算法流程和原CABOSFV 是一致的，因此时间复杂度没有变化，两者的区别在于CABOSFV 算法在执行过程中计算差异度时需要对数据对象的所有属性维分别进行计算，而CABOSFV_D使用位集只需进行一次运算，数据维度对位集的构建并没有影响，因此CABOSFV_D能够提升算法的运算效率。

CABOSFV_D 聚类算法综合考虑了算法的聚类准确性和时间性能，一方面对稀疏差异度计算公式进行拓展，调整公式中分母的变化幅度，能够提高聚类过程对象分配的准确性，另一方面利用位集定义集合差异度并快速实现算法，进一步提高了算法的时间效率。综合CABOSFV_D的聚类效果和运算效率，其更能有效地解决大规模高维数据聚类问题。

4 实验结果

4.1 数据集选取与处理

实验中选取了UCI 机器学习库中的六个真实数据集Zoo（ZO）、Soybean-smal（lSS）、Congressional Voting Records（VO）、Lymphography（LYM）、Audiology_Standardized（AS）和Dermatology（DER）进行算法验证。其中VO数据集部分缺失，去除有缺失属性的对象，最终用于实验的VO数据集的对象个数是232个。此外CABOSFV_D算法是针对二态变量高维稀疏数据提出的，因此对于非二值的分类属性，采用独热编码[22]的方式处理成二态数据。实验数据描述如表2所示。

表2 数据集描述

4.2 评价指标

由于在实验中使用的数据集已经有了类别标签，因此选择外部质量评价准则进行评价，直接将聚类标签与实际标签进行比较。本实验选择标准互信息（Normalized Mutual information，NMI）和兰德指数（Rand Index，RI）两个常用聚类评价指标对聚类结果进行评价。

（1）标准互信息

其中，X为实际类别信息，Y为聚类结果信息，MI是互信息，H是信息熵，NMI越大，表明聚类效果与真实情况越吻合。

（2）兰德指数

其中，X和Y分别是实际类别信息和聚类结果信息，n1表示在X与Y中均属于同一类的数据对个数，n2表示在X与Y中均不属于同一类的数据对个数。n为数据集中对象个数，表示集合中能够形成的数据对的总个数。兰德指数越大，聚类效果越接近真实结果。

4.3 实验及结果分析

4.3.1 实验设计

实验环境为Windows 10 操作系统，CPU处理器为Intel Core i5 8250U，内存8 GB，编程工具为Matlab R2015a。

为检验CABOSFV_D 算法的聚类性能，选取传统CABOSFV 算法进行对比实验。实验中CABOSFV_D和CABOSFV需要预先设置差异度阈值，给定阈值范围b={0.125,0.25,0.375,…,2.875,3} ；CABOSFV_D 需要预先设置差异度调整指数p，给定范围p={1,2,…,10} 。对数据进行随机排序，分别使用传统CABOSFV 算法和CABOSFV_D 算法对数据聚类，记为一组实验。分别在六个数据集上进行100 组重复实验以消除算法随机性，每组实验取参数b和p最佳情况下的聚类结果，然后将这100 组最优聚类结果的平均值作为最终聚类结果。

4.3.2 结果分析

利用Matlab 实现两种算法在UCI 数据集上的聚类实验，获得了算法在六个数据集上聚类结果的RI 和NMI评价指标，如表3和表4所示。图1和图2是聚类结果的评价指标对比图，从中可以看出，当算法以拓展的稀疏差异度公式进行聚类时，六个数据集的聚类结果的NMI和RI指标值都得到了提高，其中AS数据集上聚类评价指标值的提升最为明显。外部评价指标NMI和RI代表着聚类结果和真实结果的吻合程度，NMI和RI的值越大说明聚类越准确，因此可以证明CABOSFV_D算法的聚类准确性要高于CABOSFV算法。鉴于CABOSFV_D的位集实现方式只对算法的运算效率产生影响，因此聚类准确性的提高主要是由于拓展的稀疏差异度调整了公式中分母的变化幅度。

表3 两种算法聚类结果的NMI指标

表4 两种算法聚类结果的RI指标

图1 聚类结果的NMI指标对比图

图2 聚类结果的RI指标对比图

在实验中还记录了各个算法运行所需时间，采用平均运行时间（Average Time，AT）来衡量算法的时间效率。平均运行时间计算方式如公式（9）所示：

其中，ti表示算法第i次运行所需时间，n表示算法运行的次数。

表5显示了原始CABOSFV算法和CABOSFV_D算法在六个数据集上的平均运行时间。其中CABOSFV_D算法使用位集的实现方法进行聚类，在六个数据集上的平均运行时间相比原始算法分别减少了80.06%、87.89%、70.02%、90.08%、87.85%、93.70%。

表5 两种算法运行时间比较

综合以上实验结果，CABOSFV_D算法的聚类结果要优于传统CABOSFV算法，且时间成本远远低于原始的聚类实现方式。因此可以证明CABOSFV_D 和传统CABOSFV相比具有更好的聚类性能，在保证且进一步提高算法效率的同时获得了更高的聚类质量。

4.3.3 差异度调整指数 p 分析

CABOSFV_D 算法引入指数p拓展了集合的稀疏差异度，指数p影响着稀疏差异度分母的调整幅度，进而影响算法聚类质量，因此选取合适的p对算法至关重要。不同数据集100 组随机实验的最优指数p的分布呈现出了不同的规律。图3 显示了在六个数据集上最优指数p的分布，其中ZO、SS、LYM、DER 四个数据集的分布较为类似，它们的最优p值为2的次数在总实验次数中占比最高。LYM 的最优p值集中分布在[1，4]，在100 次实验中占比100%。DER 的最优p值集中分布在[2，3]，在总实验次数中占比99%。ZO最优p值集中分布在[1，4]，在100次实验中占比97%。SS数据集上最优p值的分布相对分散，主要集中在[1，4]，在实验中占比74%。AS 数据集在p=4 时取得最优值的次数最多，其最优p值分布也相对分散，主要集中于[2，4]，在实验中占比57%。对于VO数据集，p=1时取得最佳结果的次数最多，最优p值集中在[1，2]，在总实验次数中占比97%。

图3 六个数据集上的最优p 值分布

由上述分析可知，同一数据集的最优p值分布相对集中，对于不同数据集，最优p值的分布略有差异，但多集中于[1，4]的范围内，在实际应用中可在此范围中选择合适的p值。

4.3.4 阈值b 确定方法

阈值b是集合差异度上限，在本实验中为了检验所提算法的性能采用带有外部类标签信息的标准数据集，通过比较不同参数下聚类结果的外部评价指标选取合适的b值。然而实际聚类应用中的数据通常没有类标签，此时可利用内部评价指标来确定b。CVTAB[23]是一种二值数据内部评价指标，CVTAB取值越大，表明类间差异度越大，聚类效果越好。利用CVTAB 确定阈值b的具体步骤如下：

输入：数据集data,b可选取值{b1,b2,…,bz} ，其中bi∈[0.125,3],i∈{1,2,…,z}，调整指数p。

输出：最佳b值。

（1）将 (b1,p,data)输入CABOSFV_D 中，得到数据集data的一个划分π1。

（2）计算划分π1的内部有效性评价指标CVTAB1。

（3）对于bi,i∈{2,3,…,z} ，重复步骤（1）、（2）的操作，得到对应的CVTABi。

（4）寻 找z0使 得CVTABz0=max(CVTABi), i∈{1,2,…,z}。

（5）输出最佳b值：bz0。

5 结束语

针对CABOSFV 算法在聚类过程中数据对象更易被分配到较大的类中这一问题提出CABOSFV_D 算法。该算法对稀疏差异度度量方式进行了拓展，引入差异度调整指数p，从而缓和稀疏差异度公式中对象个数的影响，使对象分配更加准确合理。在此基础上，结合位集具有运算速度快这一优势，将二态数据对象和稀疏差异度都用位集存储和表示，提高算法处理大规模数据时的运算效率。在六个UCI 标准数据集上进行实验，结果表明CABOSFV_D获得了比CABOSFV更好的聚类结果，且时间效率明显提高，更能适用于数据规模较大的实际应用场景。最后基于实验结果讨论了选取调整指数p的参考范围，并给出了确定差异度上限b的方法。