聚类算法综述

学术型硕士课程论文（或读书报告）课程名称：科技论文写作题目：数据挖掘中聚类算法的综述题目类型（课程论文或读书报告）：课程论文学院：计算机科学与工程学院专业名称：计算机科学与技术姓名：王银学号：2015200619任课教师：潘地林授课时间：2015年9月6日～2015年11月7日提交时间：2015年12月10日数据挖掘中聚类算法的综述王银（安徽理工大学计算机科学与工程学院，安徽）摘要：聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。本综述按照聚类算法的分类，对每一类中具有代表性的算法进行介绍，分析和评价。最后从发现聚类形状、所适用的数据库和输入数据顺序的敏感性等方面进行了算法推荐，以便对聚类算法作进一步的研究。关键词：数据挖掘；聚类分析；聚类算法ReviewofClusteringAlgorithminDataMiningAbstract:ClusteringisanimportanttechnologyinDataMiningtodiscoverydatadistributionandimplicitmodel.theclassificationofclusteringalgorithmswasproposedinthispaper.Eachclasshasarepresentativealgorithmisintroduced,analysisandevaluation.Intheend,itissuggestedthatthealgorithmcanbeusedtofurtherstudytheclusteringalgorithm,whichisbasedontheshapeofthediscovery,thedatabaseandtheorderofinputdata.Keywords:DataMining;Clusteringanalysis;ClusteringAlgorithm1引言随着信息技术和计算机技术的迅猛发展，人们面临着越来越多的文本、图像、视频以及音频数据，为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识，数据挖掘（DataMining，DM）技术应运而生。所谓数据挖掘，就是从大量无序的数据中发现隐含的、有效的、有价值的、可理解的模式，进而发现有用的知识，并得出时间的趋向和关联，为用户提供问题求解层次的决策支持能力。与此同时，聚类作为数据挖掘的主要方法之一，也越来越引起人们的关注。聚类就是利用计算机技术来实现这目的的一种技术。其输入是一组未分类的记录，且事先不知道如何分类，也可能不知道要分成几类，通过分析数据，合理划分记录集合，确定每个记录所属的类别，把相似性大的对象聚集为一个簇。聚类的标准是使簇内相似度尽可能大、簇间相似度尽可能小。典型的聚类过程主要包括数据准备、特征选择和特征提取、接近度计算、聚类(或分组)、对聚类结果进行有效性评估等[7]步骤。聚类过程：(1)数据准备：包括特征标准化和降维。(2)特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。(3)特征提取：通过对所选择的特征进行转换形成新的突出特征。(4)聚类(或分组)：首先选择合适特征类型的某种距离函数或构造新的距离函数进行接近程度的度量，然后执行聚类或分组。(5)聚类结果评估：是指对聚类结果进行评估。评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。2聚类算法的分类聚类属于无监督学习，它是一种常见的数据分析工具，其目的是把大量数据点的集合分成若干类，使得每个类中的数据之间最大程度地相似，而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中，聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。本文将聚类算法分为划分聚类算法、层次聚类算法、基于密度的聚类算法、基于网格的聚类算法以及基于模型的聚类算法。2.1划分聚类算法给定一个包含n个样本的数据对象的数据集，构建数据的k个划分(k≤n)，每个划分表示一个聚类。要满足每个类至少包含一个对象、每个对象属于且仅属于一个类这两个条件。创建一个划分的数目为k的初始划分，然后采用一种迭代的重定位技术，通过反复迭代来改进划分，直到满足一个最优的划分。一个好的划分的一般准则是：在同一类中的对象之间尽可能“相似”，不同类中的对象之间尽可能“相异”[4]。其代表算法有K-means、K-medoids[5]、大型数据库划分方法(CLARANS)等。很多算法都是由这三个算法改进而来的，为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。2.2层次的聚类算法层次法对给定的数据对象集合像树一样进行层次似的分解,形成一棵聚类树。按层次分解的形成方式自底向上还是自顶向下，层次法可分为凝聚和分裂两大类。凝聚的方法，也称为自底向上的方法，首先将每个对象作为单独的一个聚类，然后根据性质和规则相继地合并相近的类。直到所有的对象都合并为一个聚类中(层次的最上层)，或者满足一定的终止条件为止。而分裂的方法，也称为自顶向下的方法，正好与凝聚法相反，首先将所有的对象都看做是一个聚类，然后在每一步中，上层类被分裂为下层更小的类，直到每个类只包含一个单独的对象，或者也满足一个终止条件为止。分裂算法将生成与凝聚方法完全相同的类集，只是生成过程的次序完全相反。层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。代表算法有BIRCH,CURE等算法。2.3基于密度的聚类算法绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪音”数据，发现任意形状的簇。DBSCAN是一个有代表性的基于密度的方法，它根据一个密度阈值来控制簇的增长。OPTICS是另一个基于密度的方法，它为自动的，交互的聚类分析计算一个聚类顺序。2.4基于网格的聚类算法基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都基于这个网格结构(即量化空间)上进行。这种算法的优点就是处理速度很快，并且其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此类算法也不适合维数较多的情况，因为维数的增加，网格单元会随之呈指数增加。常见的基于网格的代表算法有STING、CLIQUE、WAVE-CLUSTER等[8]。2.5基于模型的聚类算法基于模型的聚类方法就是设法优化给定的数据和某些数学模型之间的适应性，找出数据对给定模型的最佳拟合。该算法通过构建反映数据点空间分布的密度函数来实现聚类。它也基于标准的统计数字自动决定聚类的数目。通过统计数字来分析噪声数据或孤立点，从而产生优化的聚类方法。基于模型的方法主要有两类：统计学方法和网络神经方法[8]。其中，统计学方法有COBWEB算法，网络神经方法有SOM算法。3典型的聚类算法分析3.1K-means算法k-means算法以k为参数，把n个对象分为k个簇，以使类内具有较高的相似度，而类间的相似度最低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。首先，随机地选择k个对象，每个对象初始地代表了一个簇中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇,然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。但是k-means方法只有在簇的平均值被定义的情况下才能使用。K-means方法不适合于发现非凸面形状的簇，或者大小差别很大的簇。而且，它对于“噪音”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。3.2BIRCH算法BIRCH是—个一次扫描就可以进行较好的聚类，它利用层次方法的平衡迭代进行聚类。其核心是用一个聚类特征三元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征。它通过构造满足分支因子和簇直径（阈值）限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法具有对象数目的线性易伸缩性，及良好的聚类质量。如果簇不是球形，则该算法不能很好地工作。3.3DBSCAN算法DBSCAN是基于密度的聚类算法，可以将足够高密度的区域分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的类。该算法利用类的密度连通性可以快速发现任意形状的类。基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大量内存支持，I／O消耗也非常大。聚类过程的大部分时间用在区域查询操作上。DBSCAN算法的优点是能够发现空间数据库中任意形状的密度连通集；在给定合适的参数条件下，能很好地处理噪声点；对用户领域知识要求较少。缺点是对数据的输入顺序不太敏感；适用于大型数据库，但DBSCAN算法要求事先指定领域和阈值，具体使用的参数依赖于应用的目的。3.4STING算法STING是一种网格的多分辨率聚类技术。它将空间区域划分为矩形单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从底层单元计算得到。STING是独立于查询的，有利于并行处理和增量更新。但由于STING采用了一个多分辨率的方法来进行聚类分析，聚类的质量取决于网格结构的最低层粒度。如果数据粒度比较细，处理的代价明显增加。并且STING在构建一个父单元时没有考虑子单元和其相邻单元之间的关系。因此，尽管该技术处理速度快，但可能降低簇的质量和精确性。3.5COBWEB算法COBWEB算法以一个分类树的形式创建层次聚类，它的输入对象用“分类属性”-“值”来描述。其工作流程是：在给定一个新的对象后，COBWEB沿一条适当的路径向下，修改计数，以寻找可以分类该对象的最好节点。该判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点的一个好的选择。COBWEB算法的优点是可以自动修正划分中类的数目；不需要用户提供输入参数。其缺点是COBWEB算法是基于这样一个假设：在每个属性上的概率分布是彼此独立的，但这个假设并不总是成立。因此，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。COBWEB不适用于聚类大型数据库的数据。4总结与展望通过以上的分析得知，没有一种算法是十全十美的。在选择算法时，要根据具体情况而定，也可以结合多个算法使用。例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率，来选择聚类算法。一般情况下有以下结论[6]：(1)目标数据库如果比较大，建议使用综合性的聚类算法，如：BIRCH、CURE、DBSCAN和STING等。以提高算法效率。(2)如果聚类的形状是球形或者凸形，BIRCH和CLARANS比较适合。(3)一般而言，聚类算法对数据输入的顺序都比较敏感。如果希望不敏感，可以选用基于网格的STING算法。(4)将不同类型的聚类算法相互结合(例如BIRCH算法和CURE算法)，综合各自的优点。以满足不同的聚类要求，是今后聚类算法的一个重要发展方向。聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析，还可以作为一个独立的工具来获得数据分布的情况。聚类算法的研究具有广泛的应用前景，其今后的发展也面临着越来越多的挑战。首先是聚类算法的选择，建议使用者根据实际情况(例如发现聚类的形状、数据输人顾序是否敏感、适用数据库的大小或者算法效率)来选择合适的聚类算法。其次，对于