数据挖掘之聚类算法综述.pdf

《数据挖掘之聚类算法综述.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据挖掘中聚类算法综述摘要：聚类分析是数据挖掘中重要的研究内容之一，对聚类准则进行了总结，对五类传统的聚类算法的研究现状和进展进行了较为全面的总结，就一些新的聚类算法进行了梳理，根据样本归属关系、样本数据预处理、样本的相似性度量、样本的更新策略、样本的高维性和与其他学科的融合等六个方面对聚类中近20多个新算法，如粒度聚类、不确定聚类、量子聚类、核聚类、谱聚类、聚类集成、概念聚类、球壳聚类、仿射聚类、数据流聚类等，分别进行了详细的概括。关键字：数据挖掘聚类算法聚类准则一引言聚类分析将数据划分成有意义或有用的组（簇）。如果目标是划分成有意义的组，

2、则簇应当捕获数据的自然结构。然而，在某种意义下，聚类分析只有解决其他问题（如数据汇总）的起点。无论是旨在理解还是实用，聚类分析都在广泛的领域扮演着重要的角色。这些领域包括：心理学和其他社会科学、生物学、统计学、模式识别、信息检索、机器学习和数据挖掘。传统的聚类算法通常有基于划分的聚类、基于层次的聚类、基于网格的聚类、基于密度的聚类和基于模型的聚类。其中每种类型中，又会分出几种不同思想的聚类算法。本文就针对数据挖掘中传统的聚类算法进行了归纳和分类，总结了各种算法的思想并分析其性能特点。二聚类算法分类图1聚类算法分类图三传统聚类算法3.1基于划分

3、的聚类基于划分的聚类给定一个包含n个数据对象的数据库，以及要生成的类的数目k，一个划分方法将数据对象组织成k个划分(k≤n)，其中每个划分代表一个类。也就是说，它将数据划分为k个组，同时满足如下的要求：①每个组至少包含一个对象；②每个对象必须属于且只属于一个组(在某些模糊划分技术中此要求可以放宽)。划分方法的基本思想是：给定要构建的划分的数目k，首先创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。划分方法中最著名和最常用的是k-means、k-modes和它们的变种。3.1.1K-means算法K均值算法比

4、较简单，首先，选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。每个点指派到最近的质心，而指派到一个质心的点集为一个簇。然后，根据指派到簇的点，更新每个粗的质心。重复指派和更新步骤，直到簇不发生变化，或等价地，直到质心不发生变化。K-means算法基本步骤如下：输入：D：数据集K：质心个数输出：较优的质心集合1：选择K个点作为初始质心。2：repeat3：将每个点指派到最近的质心，形成K个簇。4：重新计算每个簇的质心。5：until质心不发生变化。K-means的空间需求是适度的，因为只需要存放数据点和质心。具体地说，所需要的存储

5、量为O((m+K)n)，其中m是点数，n是属性数。K均值的时间需求也是适度的—基本上与数据点个数线性相关。具体地说，所需要的时间为O(I*K*m*n)，其中I是收敛所需要的迭代次数。3.1.2K-modes算法k-modes算法是在数据挖掘中对分类属性型数据的采用的聚类算法。k-modes算法是对k-means算法的扩展。k-means算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理数值型数据，而不能处理分类属性型数据。例如表示人的属性有：姓名、性别、年龄、家庭住址等属性。而k-modes算法就能够处理分类属性型数据。k-modes算法采

6、用差异度来代替k-means算法中的距离。k-modes算法中差异度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。这个和就是某个样本到某个聚类中心的差异度。该样本属于差异度最小的聚类中心。3.1.2.1知识点1、Dissimilaritymeasure,where2、簇的modes：新形成的簇的modes就是，每个出现最频繁的属性值的集合。3.1.2.2算法大致步骤1：初始化K个modes2：分配所有的点到差异度最小的modes中去3：重新计算每个簇的modes4：重复2-

7、3步骤，直到modes不发生变化，或者变化很小。K-Modes聚类算法的时间复杂度为O(knmt)，其中n表示数据集U中包含的对象数，m为属性个数,，k为聚类个数,，t为最大迭代次数，空间复杂度为O(n+k)3.1.2.3算法优缺点优点：能够处理分类数据。缺点：仅能得到局部最优解。此算法适用于非度量数据。3.1.3PAM算法PAM（PartitioningAroundMedoids）是最早推出的K中心点算法之一。它试图确定n个对象的k个划分。在随机选择k个初始代表对象之后，该算法反复地试图选择簇的更好的代表对象。分析所有可能的对象对，每对中的

8、一个对象看作是代表对象，而另一个不是。对于每个这样的组合，计算结果聚类的质量。对象oj被那个可以使误差值减少最多的对象所取代。在一次迭代中产生的每个簇中最好的对象集