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

《高维数据对象聚类算法效果分析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、高维数据对象聚类算法效果分析１引言　　聚类分析是数据挖掘领域中的一项重要的研究课题，高维数据对象的聚类又是聚类分析的重要研究课题，也是涉及到聚类算法是否能够有效地应用于各个领域，例如多属性（高维）流数据的聚类分析。高维数据的特点表现为：①高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零；②高维空间中数据比低维空间中数据分布稀疏，其中数据间距离几乎相等是普遍现象。目前，对高维数据的聚类主要有3种方法：属性转换、子空间聚类、协同聚类、属性转换是通过创建新属性，将一些旧属性合并在一起来降低数据集的维度的方法。目前，主成分分析方法（ＰＣＡ）、

2、自组织特征映射（ＳＯＭ）、多维缩放（ＭＤＳ）、小波分析等是普遍应用的降维方法。虽然采用降维技术使得数据的维度大大降低，但数据的可理解性和可解释性变得较差，一些对聚类有用的信息也可能会随之丢失，很难准确地表达和理解结果。在处理高维数据时，采用属性转换的方法得到的聚类效果并不是很理想，有一定的局限性，不能满足当前高维聚类算法发展的需要。　　子空间聚类算法对特征选择的任务进行了拓展，它是在同一个数据集的不同子空间上进行聚类。子空间聚类和特征选择一样使用搜索策略和评测标准来筛选出需要聚类的簇，因为不同的子空间上存在不同的簇，因此我们要对评测标准设置一些条件。　

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

4、法能建立矩阵元素的横向联系，并用此来重新分布列对行的影响，并反过来进行。　　本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上，通过实验研究了聚类算法的聚类精度随数据对象维度的变化特征。同时，提出了利用复相关系数倒数阈值实现降维的方法。　　２数据对象离散度与维度的关系　　２．１实验数据　　实验中所用的数据集均来自ＵＣＩ数据库，数据集包括Ｉｒｉｓ，Ｗｉｎｅ，ＷｉｓｃｏｎｓｉｎＤｉａｇｎｏｓｔｉｃＢｒｅａｓｔＣａｎｃｅｒ，ＳＰＥＣＴＨｅａｒｔ和ＬｉｂｒａｓＭｏｖｅｍｅｎｔ。数据集的详细描述见表１。　　２．２相关定义　　为了确定数据对象随维

5、度变化规律，我们定义了数据对象间的最大距离和平均距离来定量确定数据对象间的离散度。　　最大距离：假设数据集D有n个数据对象，每个数据对象有ｄ个属性（维），即Ｘｉ＝｛ｘｋ，ｋ＝１，…，ｄ｝，ｉ＝１，…，n。数据对象间的最大距离被定义为：　　２．３实验结果　　为了研究维数对聚类精度的影响，有必要研究对象间的距离随维数增高的变化趋势。根据上面定义的公式（１）和公式（２），数据对象间的最大距离和平均距离随维数的增加而增大。我们使用ＵＣＩ数据库中的ＬｉｂｒａｓＭｏｖｅｍｅｎｔ数据集，先对数据集进行最小―最大标准化处理，然后计算此数据集中数据对象间随维数增高的最大

6、距离和平均距离。实验结果分别显示在图１和图２中。　　如图１和图２所示，随着维数的增加，数据对象间的最大距离和平均距离逐渐增大。表明数据对象在高维数据空间变得比较稀疏，很可能导致数据空间中客观簇的消失，使得基于距离的聚类算法往往不能够取得良好的聚类效果。因此，为了获得有效的聚类结果，基于距离、密度和密度可达的聚类算法有必要进行改进或降维。　　３维数对算法聚类精度的影响　　３．１直接聚类　　我们给出了确定聚类效果的准确度公式。假设数据集Ｄ中有ｋ个类，即Ｃｉ（ｉ＝１，…，ｋ），Oｉｐ（ｐ＝１，…，ｍｐ）是类Ci中的数据对象。数据集Ｄ经过聚类后，出现了ｋ个类Ｃ

7、ｉ′（ｉ＝１，…，ｋ），Ｏｉｐ′（ｐ＝１，…，ｍｐ′）是Ci′类中的数据对象，准确度被定义为：　　｜Ｃｋ∩Ｃｉ′｜是同时属于类Ｃｉ和Ｃｉ′的数据对象Ｏｉｐ（ｐ＝１，…，ｍｐ）和Oip′（ｐ＝１，…，ｍｐ′）的个数；

8、D

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

10、，传统的聚类算法，如Ｋ－ｍｅａｎｓ和层次聚类算法，这种基于距离的聚类算法是有效的，但是当维数大