高维数据对象聚类算法效果分析

郝媛 高学东 孟海东

［摘要］ 虽然经典聚类算法能够有效地处理维度较低的数据对象，但随着维度的增加，算法的性能和效率就会明显下降。本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上，对聚类算法的聚类精度随数据对象维度增加的变化特征进行了实验研究。同时，利用复相关系数的倒数对属性进行加权，提出了利用复相关系数倒数阈值实现降维的方法，并取得了良好的实验结果。

［关键词］ 高维数据；聚类效果；复相关系数；降维

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 08. 035

［中图分类号］F270.7；TP301［文献标识码］A［文章编号］1673 - 0194（2012）08- 0051- 03

１引言

聚类分析是数据挖掘领域中的一项重要的研究课题，高维数据对象的聚类又是聚类分析的重要研究课题，也是涉及到聚类算法是否能够有效地应用于各个领域，例如多属性（高维）流数据的聚类分析。高维数据的特点表现为：①高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零；②高维空间中数据比低维空间中数据分布稀疏，其中数据间距离几乎相等是普遍现象。目前，对高维数据的聚类主要有3种方法：属性转换、子空间聚类、协同聚类、属性转换是通过创建新属性，将一些旧属性合并在一起来降低数据集的维度的方法。目前，主成分分析方法（ＰＣＡ）、自组织特征映射（ＳＯＭ）、多维缩放（ＭＤＳ）、小波分析等是普遍应用的降维方法。虽然采用降维技术使得数据的维度大大降低，但数据的可理解性和可解释性变得较差，一些对聚类有用的信息也可能会随之丢失，很难准确地表达和理解结果。在处理高维数据时，采用属性转换的方法得到的聚类效果并不是很理想，有一定的局限性，不能满足当前高维聚类算法发展的需要。

子空间聚类算法对特征选择的任务进行了拓展，它是在同一个数据集的不同子空间上进行聚类。子空间聚类和特征选择一样使用搜索策略和评测标准来筛选出需要聚类的簇，因为不同的子空间上存在不同的簇，因此我们要对评测标准设置一些条件。

协同聚类在数据点聚类和属性聚类之间达到了一种平衡。因为它从对象—属性两个角度同时进行聚类操作。假设Ｘ是由数据对象和数据属性构成的矩阵，一般被叫做关系矩阵、可能性矩阵、影响矩阵、频率矩阵等。一般被应用于反映基因响应的强度、一个Ｗeb页面的点击率，或一个仓库里各项商品的销售数量等。Ｇｏｖａｅｒｔ于１９９５提出了可能性矩阵表中行列块的同时聚类算法。Ｄｈｉｌｌｏｎ于２００１年提出了一种协同代数聚类算法，它与文本挖掘相关，是基于二部图和它们的最小切割的。Ｏｙａｎａｇｉ等人于２００１年提出了一种简单的Ｐｉｎｇ－Ｐｏｎｇ算法，它能在稀疏二元矩阵中发现相应区域，该算法能建立矩阵元素的横向联系，并用此来重新分布列对行的影响，并反过来进行。

本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上，通过实验研究了聚类算法的聚类精度随数据对象维度的变化特征。同时，提出了利用复相关系数倒数阈值实现降维的方法。

２数据对象离散度与维度的关系

２．１ 实验数据

实验中所用的数据集均来自ＵＣＩ数据库，数据集包括Ｉｒｉｓ，Ｗｉｎｅ，Ｗｉｓｃｏｎｓｉｎ Ｄｉａｇｎｏｓｔｉｃ Ｂｒｅａｓｔ Ｃａｎｃｅｒ，ＳＰＥＣＴ Ｈｅａｒｔ和Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ。数据集的详细描述见表１。

２．２ 相关定义

为了确定数据对象随维度变化规律，我们定义了数据对象间的最大距离和平均距离来定量确定数据对象间的离散度。

最大距离：假设数据集D有n个数据对象，每个数据对象有ｄ个属性（维），即Ｘｉ＝｛ｘｋ，ｋ＝１，…，ｄ｝，ｉ＝１，…，n。数据对象间的最大距离被定义为：

２．３ 实验结果

为了研究维数对聚类精度的影响，有必要研究对象间的距离随维数增高的变化趋势。根据上面定义的公式（１）和公式（２），数据对象间的最大距离和平均距离随维数的增加而增大。我们使用ＵＣＩ数据库中的Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ数据集，先对数据集进行最小—最大标准化处理，然后计算此数据集中数据对象间随维数增高的最大距离和平均距离。实验结果分别显示在图１和图２中。

如图１和图２所示，随着维数的增加，数据对象间的最大距离和平均距离逐渐增大。表明数据对象在高维数据空间变得比较稀疏，很可能导致数据空间中客观簇的消失，使得基于距离的聚类算法往往不能够取得良好的聚类效果。因此，为了获得有效的聚类结果，基于距离、密度和密度可达的聚类算法有必要进行改进或降维。

３维数对算法聚类精度的影响

３．１ 直接聚类

我们给出了确定聚类效果的准确度公式。假设数据集Ｄ中有ｋ个类，即Ｃｉ（ｉ＝１，…，ｋ），Oｉｐ（ｐ＝１，…，ｍｐ）是类Ci中的数据对象。数据集Ｄ经过聚类后，出现了ｋ个类Ｃｉ′（ｉ＝１，…，ｋ），Ｏｉｐ′（ｐ＝１，…，ｍｐ′）是Ci′类中的数据对象，准确度被定义为：

｜Ｃｋ∩Ｃｉ′｜是同时属于类Ｃｉ和Ｃｉ′的数据对象Ｏｉｐ（ｐ＝１，…，ｍｐ）和Oip′（ｐ＝１，…，ｍｐ′）的个数；|D|是数据集D中的数据对象的个数。

为了研究维数对算法聚类精度的影响，我们分别用Ｋ－ｍｅａｎｓ和层次聚类算法对以上５个不同维数的数据集进行聚类分析，聚类结果如图３所示。当数据集的维数小于３０的时候，两种聚类算法的性能较好，当数据集的维数大于３０的时候，聚类算法的精度随维数的增高而降低。实验结果在一定程度上表明，当数据集的维数小于３０的时候，传统的聚类算法，如Ｋ－ｍｅａｎｓ和层次聚类算法，这种基于距离的聚类算法是有效的，但是当维数大于３０的时候它们的聚类结果很不理想。

３．２ ＰＣＡ降维聚类

Ｗｉｎｅ数据集有１３维，经过主成分分析（ＰＣＡ）降维后，原有的１３维变成了３维，为了比较ＰＣＡ降维前和降维后的效果，我们用Ｋ－ｍｅａｎｓ和层次聚类算法对原有的数据集和经过降维后的数据集进行聚类，结果如图４所示。

对数据集降维后，Ｋ－ｍｅａｎｓ和层次聚类算法的聚类精度有所提高，但是效果不是很明显。此结果也说明了 Ｋ－ｍｅａｎｓ和层次聚类对３０维以内的数据集的聚类精度比较高。

Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ数据集有９０维，经过ＰＣＡ降维后变成了１０维，降维前和降维后的聚类结果如图５所示。

降维前和降维后Ｋ－ｍｅａｎｓ和层次聚类算法的聚类精度都很低，结果表明：①以上两种聚类算法不能有效地处理高维数据；②ＰＣＡ降维对聚类算法不总是有效的；③此数据集包含１５个类，对于高维、多类的数据集，聚类算法不能很好地辨别存在的类（簇）。

４基于复相关系数倒数降维

４．１ 复相关系数倒数加权

复相关系数的倒数赋权法是在方差倒数赋权法的基础上提出来的。假设数据对象的某一属性为Xk，则它的复相关系数记为ρk。ρk越大，表明Xk与其余的属性越相关，越能被非Xk代替，也就是说Xk属性对聚类的作用越小；反之，ρk越小，Xk与其余的属性越不相关，Xk属性对聚类的作用越大。所以可以用|ρi|-1计算数据对象属性权重系数wk。

４．２ 降维实验

我们也可以采用复相关系数的倒数赋权法作为一种特征选择方法，对数据集中数据对象的每个属性加权后，得到了每个属性的权值，然后根据权值的大小，我们设定一个阈值参数σ，选择权值大于σ的属性，从而实现了对数据集的降维，然后对降维后数据集进行聚类。为了说明此方法的有效性，采用ｋ－ｍｅａｎｓ算法、层次聚类算法、ＣＡＤＤ （基于密度和密度可达聚类算法）算法对ＷＤＢＣ数据集和ＳＰＥＣＴ Ｈｅａｒｔ数据集进行聚类，来对比降维前和降维后的结果。

ＷＤＢＣ数据集有３０个属性，取权值σ≥0.036时，该数据集降为３维；取权值大于０．０３４时，该数据集降为６维；取权值大于０．０３３时，该数据集降为１５维。降为３维、６维、１５维的数据集和原数据集的聚类精度如图６所示，实验结果表明该数据集降为６维时聚类效果最好。

ＳＰＥＣＴ Ｈｅａｒｔ数据集有４４个属性，取权值大于０．０２４时，该数据集降为５维；取权值大于０．０２３时，该数据集降为１８维；取权值大于０．０２２时，该数据集降为２８维。降为５维、１８维、２８维的数据集和原数据集的聚类精度如图７所示，实验结果表明该数据集降为１８维时聚类效果最好。

Ｌｉｂｒａｓ Ｍｏｖｅｍｅｎｔ数据集有９０个属性，取权值大于０．０１１ １１３时，该数据集降为１０维；取权值大于０．０１１ １１１时，该数据集降为３４维；取权值大于０．０１１ １１０时，该数据集降为４７维。降为１０维、３４维、４７维的数据集和原数据集的聚类精度如图８所示。实验结果表明聚类算法对该数据集的聚类效果较差，原因是此数据集包含１５个类，类比较多，聚类算法不能很好地识别，但是该数据集降为４７维时聚类效果有所提高，仍能体现出本文降维方法的有效性，ＣＡＤＤ算法的聚类效果相对好一些，从而体现了ＣＡＤＤ算法的优越性。

由以上实验结果表明：①采用复相关系数的倒数赋权法作为一种属性选择方法是有效的，并且计算量较小，适合处理高维数据；②降维要降到合适的维度，如果维数太少，则会丢失对聚类重要的属性信息，如果维数太多，则会产生“噪声”，影响聚类结果；③一般的聚类算法不能很好地处理高维且类比较多的数据集，因此有待于进一步研究能处理高维且类比较多的数据集的聚类算法。

５结论

对于传统的基于距离的聚类算法，当数据对象的维数小于或等于３０时，聚类分析往往能够取得良好的聚类效果；维数高于３０时，聚类效果不佳。甚至使用ＰＣＡ降维后，聚类算法对高维数据的聚类效果的改进也不是很明显。用复相关系数的倒数赋权法为差异度加权，并且把复相关系数的倒数赋权法用作一种属性选择方法，通过设定属性加权系数的阈值参数对数据对象进行降维也能取得较好的聚类结果。

主要参考文献

［１］冯永，吴开贵，熊忠阳，等．一种有效的并行高维聚类算法［Ｊ］．计算机科学，２００５，３２（３）：２１６－２１８．

［２］王永卿．高维海量数据聚类算法研究［Ｄ］．南宁：广西大学，２００７．

［３］［加］Ｊｉａｗｅｉ Ｈａｎ，［加］ Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ． 数据挖掘概念与技术［Ｍ］．北京：机械工业出版社，２００１．

［４］Ｇ Ｇｏｖａｅｒｔ．Ｓｉｍｕｌｔａｎｅｏｕｓ Ｃｌｕｓｔｅｒｉｎｇ ｏｆ Ｒｏｗｓ ａｎｄ Ｃｏｌｕｍｎｓ［Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｃｙｂｅｒｙｒｅｔｉｃｓ，１９９５，２４（4）：４３７－４５８．

［５］Inderjit S Dhillon． Ｃｏ－ｃｌｕｓｔｅｒｉｎｇ Ｄｏｃｕｍｅｎｔｓ ａｎｄ Ｗｏｒｄｓ Ｕｓｉｎｇ Ｂｉｐａｒｔｉｔｅ Ｓｐｅｃｔｒａｌ Ｇｒａｐｈ Ｐａｒｔｉｔｉｏｎｉｎｇ［Ｃ］//Ｐｒｏｃｅｅｄｉｎｇｓ ａｎｄ ｔｈｅ ７ｔｈ ＡＣＭ ＳＩＧＫＤＤ， Ｎｅｗ Ｙｏｒｋ，ＮＹ，２００１．

［６］Shigeru Oyanagi,Kazuto Kubota,Ahihiko Nakase． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Mａｔｒｉｘ Cｌｕｓｔｅｒｉｎｇ ｔｏ Ｗｅｂ Lｏｇ Aｎａｌｙｓｉｓ ａｎｄ Aｃｃｅｓｓ Pｒｅｄｉｃｔｉｏｎ［Ｃ］//７ｔｈ ＡＣＭ ＳＩＧＫＤＤ， Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ，2001.

［7］宋宇辰，张玉英，孟海东．一种基于加权欧氏距离聚类方法的研究［Ｊ］．计算机工程与应用，２００７，４３（４）：１７９－１８０．

［8］孟海东，宋飞燕，宋宇辰．面向复杂簇的聚类算法研究与实现［Ｊ］．计算机应用与软件，２００８，２５（１０）：３２－３４．