英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
从多角度分析现有聚类算法
摘要：聚类是数据挖掘领域中研究的重要问题之一，它用来将数据集分成簇从而使得簇内部的数据尽量相似而簇外部的数据尽量不相似。不同的聚类方法使用不同的相似测度和技术，对几种重要的聚类方法从以下三个方面进行分析：1、聚类尺度，2、集群的表示，3、算法框架。在此基础上，分析了一些综合或概括了其他方法的算法。由于分析从三个角度进行，所提出的方法能够涵盖并区分现有的绝大多数算法。所做的工作是自调节聚类算法以及聚类基准测试研究的基础。
关键词：数据挖掘、聚类、算法
聚类是一种重要的数据挖掘技术，用于数据分割和图片信息，聚类技术被广泛应用于财务数据分类，空间数据采集，卫星图像分析和医疗数据自动检测等等，聚类的问题是将数据集分成簇从而使簇内部的数据尽可能相似而簇外的数据尽可能不相似，它可以被形式化为如下几点：
定义1：给出一个数据集V{v1,v2,hellip;,vn}，virsquo;s (i=1,2,hellip;,n)是里面的数据点，将V分成{C1,C2,hellip;,Ck}（CiV (i =1,2,hellip;,k), cup;i=1k Ci = V,）并且基于数据点之间相似性的过程就称为聚类，Cirsquo;s (i =1,2,hellip;,k) 就叫簇。
这个定义并没有给出数据点相似性的定义，实际上，不同的聚类方法有不同的定义标准。
聚类通常也被称为无监督学习的过程，因为并没有关于数据集的先验知识，因此聚类分析通常作为其他知识发现操作的预处理，聚类结果的质量对整个知识发现过程来说十分重要。对于数据挖掘操作来说，高性能和可扩展性是除准确性以外的必要元素。因此，一个好的聚类算法应该满足以下要求：独立于先验知识，只需要容易建立的参数，准确，迅速，有好的扩展性。
在构建聚类算法方面已经做了大量的研究工作。都使用了新技术来提高处理特定特征数据集的能力。然而，如上所述，不同的算法使用了不同的标准。由于没有聚类方法的基准，所以很难通过一个普通的衡量标准来比较这些算法。 但是，还是需要进行详细比较。这是因为：（1）分析优缺点，可以对现有算法进行改进。（2）用户应该能够为某个数据集选择正确的算法，从而可以获得最佳的结果和性能。（3）详细比较是构建聚类基准的基础。
在本文中，我们从不同的方面分析了几种现有的流行算法。与其他一些调查工作[1〜3]不同的是，我们从不同的观点广泛地比较这些算法，而另一些尝试将某些方法推广到某个框架，如参考文献[1,2]，这些只能 覆盖有限的算法，或者仅仅引入聚类算法作为教程[3]，所以算法之间没有比较。由于不同的算法使用不同的标准和技术，这些调查只能涵盖一些算法。此外，一些算法不能被区分，因为它们使用相同的技术，使得它们在某个框架中属于相同的类别。
本文的其余部分结构如下：第1至第3单元从三个不同的角度分析聚类算法，即聚类标准，算法框架和聚类表示。第4单元介绍了一些方法，这些方法综合或概括了其他方法的算法。第5单元介绍了集群自动检测的研究重点。最后，第6单元是结语。
应该注意的是，从各个角度来看，尽管我们尝试对尽可能多的算法进行分类，但还是算法被遗漏。一些算法可能属于同一类别。然而，从所有这些观点观察这些算法时，我们就可以区分不同的算法。这是我们工作的动力。
1 标准
聚类分析的基础是相似性的定义。通常，相似度的定义包含两部分：（1）数据点之间的相似度；（2）数据点集之间的相似性。 并不是所有的聚类方法都需要它们。一些算法只使用一个。
聚类标准可以分为三类：基于距离，基于密度和基于链接。基于距离和基于密度的聚类通常应用于欧几里德空间中的数据，而基于链接的聚类可以应用于任意度量空间中的数据。
1.1 基于距离的聚类
基于距离的聚类的基本思想是，集群是彼此接近的数据点。在欧几里德空间中，两个数据点之间的距离很容易定义。广泛使用的距离定义包括欧几里德距离和曼哈顿距离。
然而，两组数据点之间的相似性定义有几种选择，如下所示：
Similarityrep (Ci ,Cj ) =distance(repi , rep j ) (1)
或
（2）
或
Similaritymax (Ci ,Cj )=max{distance(vi ,v j ) | vi Ci ,v j Cj} （3）
或
Similaritymin (Ci ,Cj )=min{distance(vi , v j ) | vi Ci , v j Cj} （4）
在（1）中，repi 和rep j分别代表Ci 和Cj，一个数据集的代表往往是它的均值，例如K均值[4]。单一代表性方法通常采用定义（1）。很明显，（2），（3）和（4）的复杂度都是O（| Ci | * | Cj |），对于大数据集而言效率低下。虽然它们是更全面的定义，但它们通常不直接应用于子集群或集群的相似性定义。唯一的例外是BIRCH [5]，其中采用CF矢量和CF树来加速计算。采取一些权衡方法，如2.1节中将讨论的，其中还给出了单一代表性方法的详细分析。
基于距离的聚类的优点是距离易于计算和理解。并且基于距离的聚类算法通常需要K的参数，这是用户想要的最终聚类的数量，或是区分两个聚类的最小距离。然而，它们的缺点也是明显地对噪音敏感。虽然有些技术在其中部分引入，但也会导致其他严重问题。CURE [6]采用代表性缩减技术来减少噪声的影响。然而，由我们的实验结果图1所示，它引起了无法识别中空形状的簇的问题。这种缺点抵消了多代表的优点即算法可以识别任意形状的集群。BIRCH是第一个考虑了噪声的聚类算法，引入了一个新的参数T，这个参数基本上是一个与密度相关的参数。此外，除非CF-tree的页面存储能力已知（Page_size / entry_size / T是该页面中的密度近似值），否则用户很难理解此参数。 此外，它可能会导致小簇和长形簇的丢失。由于缺乏空间，所以省略详细的讨论。
图1 由CURE识别的空心簇
1.2 基于密度的聚类方法
除了基于距离的聚类方法之外，基于密度的聚类代表群集是密集区域。因此，数据点的相似性定义是基于它们是否属于连通的密集区域。属于连通密集区域的数据点属于同一簇。 基于密度的不同计算，基于密度的聚类可以进一步分类为最近邻（本文其余部分称为NN）方法和基于细胞的方法。它们之间的区别在于前者根据数据集定义密度，后者根据数据空间定义密度。无论基于密度的聚类算法属于哪一种，它始终需要一个最小密度阈值参数，这是定义密集区域的关键。
1.2.1 神经网络方法
神经网络方法只处理在半径为ε的超球体中有超过k个邻居的点作为簇中的数据点。由于每个点的邻居点应该被计算，所以总是使用支持区域查询的索引结构，如R *树或X树。由于维度的特性[7]，这些方法对维度没有很好的可扩展性。此外，神经网络方法会导致数据频繁的I / O套都非常大。然而，对于大多数多维数据集，这些方法是有效的。总而言之，这种方法的缺点就是它们所基于的索引结构的缺点。
传统的神经网络方法，如DBSCAN及其后代[8〜10]，需要密度阈值参数和半径ε。最近，OPTICS [11]的基本思想与DBSCAN相同，着重于自动识别集群结构。由于OPTICS中的新技术不属于本小节的主题，因此我们将在第5节中进行讨论。
1.2.2 基于单元的方法
基于单元的方法计算基于单位的密度信息。STING [12]，WaveCluster [13]，DBCLASD [14]，CLIQUE [15]和OptiGrid [16]都属于这一类。基于细胞的方法具有的缺点是细胞只是密集区域的近似。一些方法介绍了解决这个问题的技术，将在2.3节中介绍。
当数据集包含粒度小于计算密度的单位粒度的群集或子群集时，基于密度的聚类方法都会遇到问题。众所周知的例子是哑铃形簇，如我们的实验结果图2所示。然而，对于基于密度的聚类方法，如果参数设置正确，就很容易去除噪声。也就是说，它对噪音是鲁棒的。
图2 基于密度算法（DBSCAN）识别的哑铃形簇
1.3 基于连锁的聚类方法
除了基于距离或基于密度的聚类之外，基于连锁的聚类可以应用于任意度量空间。此外，由于在高维空间中，距离信息和密度信息不足以用于聚类，因此经常采用基于连锁的聚类。属于这种方法的算法包括ROCK [17]，CHAMELEON [18]，ARHP [19,20]，STIRR [21]，CACTUS [22]等。
基于连锁的方法基于图或超图模型。他们通常将数据集映射到图形/超图中，然后根据边缘/超边缘信息对数据点进行聚类，从而将高度连通的数据点分配给同一个集群。图形模型与超图模型之间的差异在于前者反映了一对节点之间的相似度，而后者通常反映出同步信息。ROCK和CHAMELEON使用图形模型，而ARHP，PDDP，STIRR和CACTUS使用超图模型。虽然CACTUS的开发人员并没有说明它是基于超图模型的算法，但它的确属于这种算法。
基于连锁的聚类结果的质量取决于联动或超边缘的定义。由于不可能处理完整的图形，图形/超图模型总是消除重量较低的边/超边，因此图/超图是稀疏的。但是，为了提高效率，可能会降低精度。
该类别中的算法使用不同的框架。ROCK和CHAMELEON是分层聚类方法，ARHP是分裂方法，STIRR使用动态系统模型。此外，由于共生问题与关联规则挖掘问题相似，ARHP和CACTUS都借用了Apriori算法[23]找到集群。采用Apriori式算法的另一种算法是CLIQUE。然而，单调引理用于基于在子空间中发现的群集找到高维集群。CLIQUE不是基于联动的聚类方法，它是与本小节讨论的其他算法的区别。算法框架的详细讨论将在第3单元中给出。由于CHAMELEON使用链路和距离信息，所以将在4.1节中单独讨论。
2 聚类表示
聚类的目的是对数据集群进行识别分类，这些是类似数据的总结。 每个算法应该以某种形式表示簇和子簇。尽管使用集群标识标注每个数据点是一个简单的想法，但大多数方法都不采用这种方法。这可能是因为：（1）摘要。不仅应该易于理解，还应该成对（数据-点，簇-ID）；（2）在聚类过程中标记所有数据点在时间和空间上昂贵的；（3）一些方法采用精确的紧凑型集群代表，这使得标签的耗时过程不必要。我们将集群表示技术分为四种，如下所述：
2.1 代表点
大多数基于距离的聚类方法都使用一些点来表示聚类。这些点被称为代表点。代表可以是数据点，或数据库中不存在的其他点，例如某些数据点集合的平均。属于该类别的数据表示技术可以进一步分为三类：
2.1.1 单代表
最简单的方法是使用一个点作为每个集群的代表。 每个数据点被分配给与其代表最接近的集群中。代表点可以是集群的平均值，如k-means [4]方法，或数据库中的数据点，它是最接近中心的点，像k-medoids方法一样。其他算法包括BIRCH [5]，CLARA [24]和CLARANS [25]。 参考文献[25]详细介绍了k-means和k-medoids方法对聚类结果的不同影响。 既然与本文的动机无关，我们不在这里进行介绍。
单一代表性方法的缺点是显而易见的：（1）只能识别球面簇; 和（2）拥有小簇的大簇将被分割，而大簇中的一些数据点将被分配给小簇。这两种现象如图3所示（本图的右侧部分是参考文献[6]，图1（b））。因此，当处理具有很大差异的任意形状的簇或簇的数据集时，这种方法将失败。
图3 通过单一代表性方法识别的非球形簇和不同尺度的簇
2.1.2 所有数据点
使用集群中的所有数据点来表示它是另一种简单的方法。然而，它十分耗时，因为：（1）数据集总是很大，使得标签信息不能适应于存储器，这导致频繁的磁盘访问，以及（2）在计算集群内部和外部之间的信息时，它将访问所有数据点。此外，标签信息很难理解。 因此，没有流行的算法采用这种方法。
2.1.3 多代表
在CURE中引入了多代表方法，它是单点和全点方法之间的权衡。第一个代表是数据点，它与集群的平均值最远。接下来，每次选择与最近的现有代表点的距离
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[138122]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
