高维混合型数据聚类算法研究

郭小康

（西安建筑科技大学管理学院，陕西 西安 710050）

0 引言

研究者们已经提出了许多优秀的聚类算法，并在实际中得到了很好的应用。然而，现有的聚类算法大多是针对低维数据设计的，而且，这些算法都是针对不同的特殊数据类型设计的，很难找到一种通用的算法应用于各种数据类型的聚类分析中，尤其是对高维数据，由于其数据分布的特殊性，使得现有的聚类算法无法满足处理高维数据的需求。为了对高维数据进行聚类，提出了一种新的高维数据聚类算法（AWSCH：an weighted subspace algorithm for the clustering of high-dimensional dataset）[1-2]，算法采用基于变异信息熵和方差的概念对高维数据进行类的特征子空间的搜索，在尽可能保留数据有效信息的情况下有效地降低了数据的维度，从而显著地提高了聚类效率，同时，由于采用了新的相似度度量方式，从而在混合型数据空间上也可以进行特征子空间的搜索，算法的通用性也得到了提高。

1 数据聚类

数据在预处理之后，留下的数据相对来说都是特征较为明显的数据，在此基础之上，我们采用凝聚算法的思想进行初始数据簇的合并操作，直到簇的个数等于原始数据种类的个数。在聚类的过程中，采用子空间聚类的方式进行，而子空间的搜索使用维纯度的方差进行。

1.1 子空间的寻找

在子空间聚类思想里，子空间维度能较好地体现数据类的特征，它们的特征通常比较明显，而非特征子空间的维度特征相对来说就没有那么明显。在子空间的搜索过程中，子空间的凝聚度越大越好，而噪声空间凝聚度越小越好，怎样在两者之间找到一个平衡点成为子空间搜索的关键。

通常特征子空间搜索时大多是采用一个阈值，进而在数据空间每个维度上得出一个标准，比如信息熵，当熵值小于阈值时，就把该维放进特征子空间，否则相反。但是阈值的选取受人为因素影响较大，尤其是针对不同的数据集，所采用的阈值大多不一样，所以找到一个自适应的方式进行特征子空间的搜索显得十分必要。

为解决这个问题，我们利用维纯度的方差进行特征子空间的搜索，在经过数据的预处理之后，数据已经变成一个个的数据簇，对于每一个簇的每一个维度可以进行维纯度的计算，维纯度就代表了该维度上的凝聚程度。在进行特征子空间的搜索时，把噪声子空间维纯度的方差定义为Variance(S)，特征子空间的维方差定义为Variance(F)，这样就可以按自适应函数f(e)计算出该簇的特征子空间[3]。

其中，对于子空间M来说：

其中|M|为子空间M的维数，avgM为子空间 M 上维纯度的平均值，Sl(i)为子空间 M中第 i维上的维纯度。

所求出的子空间应使f(e)取得最小值。该函数既考虑了子空间的数据的紧凑度，又考虑了噪声空间的凌乱程度，在特征子空间和噪声子空间之间找到了一个平衡点，使得特征子空间的搜索更加合理化。

方差是度量数据离散程度的最重要、最常用的指标之一，它是测算数值型数据离散程度的最重要的方法之一，把它用于簇的特征子空间的搜索显得很自然。由函数f(e)求出的特征子空间能代表该簇的属性特征[4]。

1.2 类的prototype提取

类 prototype的提取其实就是类的特征的提取，对于一个数据集来说，它所包含的k个类就具有k个prototype，如果能把原始数据分成到k个凝聚度较好的簇，则这k个簇就可以被看作是该数据集k的具体的类，类的特征就是该数据集的k个prototype。

在类prototype提取的过程中，两个簇的相似度是在两个簇的特征子空间的并集上进行的，这样能充分的考虑到两个簇的特征信息以及合并之后数据紧凑度。在得到两个簇的特征子空间的基础上，通过公式即可得到两个簇的相似度[5]。

这样，通过计算所有簇对之间的相似度就能得到由簇对的相似度组成的相似度矩阵，在每次进行簇的合并时，从相似度矩阵中找到具有最大相似度的两个簇进行合并，直到簇的个数等于原始数据集中类的个数，至此，非噪声据的聚类工作结束。

每个簇的特征子空间所包含的簇通常情况下是不同的。在子空间并集上进行相似度的计算，既能保留每一个簇的特征子空间信息，又能同时满足保留两个簇的相关特征信息的基本要求，同时又去掉了共同的噪声空间维度的干扰，能较好地体现子空间聚类的思想[6]。

2 算法描述

算法由三部分组成，第一部分是数据的预处理，这里利用了一种新的相似度的度量方式进行数据之间的相似度的计算，把原始数据集初始化成一个个小的数据簇，然后进行异常数据的隔离，经过隔离之后留下来的簇第二部分输入；第二部分是数据集类的 prototype 的提取，在此过程中采用子空间的方式进行簇之间的相似度的计算，直到剩下的簇的个数等于数据集中类的个数；第三部分是被隔离的异常数据的回归，也就是把第一步隔离出来的异常数据回归到第二部分形成的初始类中[7-8]。

算法的输入有数据D，数据初始化阈值init_rate，异常数据隔离阈值min_size，输出是聚类结果Result，AWSCH算法具体表述如下[9-10]：

Step0: 初始化阈值和类的个数k；

Step1: 对数据集D进行预处理；

Step2: 依据min_size隔离异常数据；

Step3: 按公式（1）提取子空间，计算相似度，进行初始簇的合并，提取类prototype提取；

Step4: 按公式（1）提取子空间，计算相似度，对被隔离的异常数据进行回归分类处理；

Step5：输出聚类结果Result。

3 实验对比

3.1 混合型数据

在实验过程中，选取 UCI机器学习网站上Heart Disease(Heart)、 Acute Inflammations(Acute)、Credit Approval(Credit)和 Zoo四个典型的混合型数据集进行实验验证，并对聚类结果进行分析。

3.2 数据描述

Zoo含有 101个数据，总维数为17。数据集包含数值型维数 2维，分类型15维。其中，第一维为类标识。数据集共分为7类，各个类包含的数据个数分别为 41、20、5、13、4、8、10（表1）。

表1 数据集基本信息

Credit含有 690个数据，总维数为15。数据集包含数值型维数7维，分类型数据维数8维。其中，最后一维为类标识，取值只有两个。数据集共分为2类，各个类包含的数据个数分别为303、383。表2给出了各算法在Credit数据集上的正确率。

表2 各算法在数据集上的正确率

Heart含有303个的数据，总维数为14。数值型维数为6，分类型维数为8。其中，最后一维为类标识，数据集共分为5类，各个类包含的数据个数分别为164、55、36、35、13。

Acute含有120个数据，总维数为8。数值型维数为3，分类型数据维数为5。数据集可以在最后两维针对不同的情况进行不同的类标识。以最后一维为依据时，类的大小分别为50、70；以另一维为依据时，类的大小分别为59、61。

四个数据集的详细信息如下：

在对混合型数据进行聚类时，可以进行相似度的计算，采用公式（1）进行特征子空间的搜索，在聚类过程中的p和q的取值依据数据集的不同情况进行设定[11]。

3.3 实验结果对比

从表2中可以看出，本文算法能取得表中结果的参数并不是唯一的，在许多其他参数下也能得到相同或接近的结果，图1即为 init_rate 取不同值时，AWSCH 算法在数据集 Credit上的聚类准确率。

图1 init_rate 取不同值时在Credit 上的正确率

由图1可以看出，当 init_rate大于0.8 时，AWSCH在Credit上的正确率都是一样的，也就是说AWSCH算法在其他参数下同样具有较好的聚类准确率， 显示了AWSCH算法的有效性。AWSCH在其他参数不同取值及其他数据集上也有类似的效果，不再逐一列举。

为了更直观地显示各个算法的聚类结果，特对各算法的聚类结果用直方图显示，如图2所示。

图2 各算法在数据集上的正确率

从图2可以直观地看出，AWSCH算法的聚类明显优于其他算法，体现了算法的有效性。算法的性能来源于它prototype提取的合理性、相似度度量的适宜性以及隔离数据到prototype分配的创新性。

4 结论

本文提出了一种子空间聚类算法AWSCH。利用维纯度去度量每一维数据的有序程度，避免了混合型数据聚类中标准不统一的问题；利用维纯度的方差去搜索子空间，找到了一个自适应的约束方程，充分地考虑了特征子空间和噪声空间的影响，使子空间的搜索更加合理；在子空间权重分配时，没有明显的去分配每一维的权重，而采用维纯度无形当中就给子空间中每一个维度赋予适当的权值；提出了一种能应用于混合型数据相似度的计算方法，从而提出一种类prototype的提取方法，用于高维数据聚类。在相似度计算方面，首先搜索能较好地代表数据特征的子空间，然后在子空间上进行相似度的计算，从而提高聚类的精确度。在数据集类prototype的提取方面，先把较为相似的数据聚在一块，在对噪声数据隔离之后再进行prototype的提取，这样就能避免噪声数据对prototype的影响， 而且能避免把较为相似的数据聚到不同的类中，从而提高聚类精度。prototype 提取结束之后，在被隔离数据分配到类prototype过程中，并不是把数据直接分配到相关prototype所在的类，而是在所有数据prototype匹配结束之后，统一进行数据的分配，这样减少了噪声数据对类prototype的影响，避免了噪声数据对类的真实prototype的影响，并且降低了prototype更新所带来的计算复杂度。