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

数据挖掘中聚类算法综述 摘要：聚类分析是数据挖掘中重要的研究内容之一，对聚类准则进行了总结，对五类传统的聚类算法的研究现状和 进展进行了较为全面的总结，就一些新的聚类算法进行了梳理，根据样本归属关系、样本数据预处理、样本的相似 性度量、样本的更新策略、样本的高维性和与其他学科的融合等六个方面对聚类中近20 多个新算法，如粒度聚类、 不确定聚类、量子聚类、核聚类、谱聚类、聚类集成、概念聚类、球壳聚类、仿射聚类、数据流聚类等，分别进行 了详细的概括。 关键字：数据挖掘 聚类算法 聚类准则 一 引言 聚类分析将数据划分成有意义或有用的组（簇）。如果目标是划分成有意义的组，则簇应当捕获数据的自然结 构。然而，在某种意义下，聚类分析只有解决其他问题（如数据汇总）的起点。无论是旨在理解还是实用，聚类分 析都在广泛的领域扮演着重要的角色。这些领域包括：心理学和其他社会科学、生物学、统计学、模式识别、信息 检索、机器学习和数据挖掘。 传统的聚类算法通常有基于划分的聚类、基于层次的聚类、基于网格的聚类、基于密度的聚类和基于模型的聚 类。其中每种类型中，又会分出几种不同思想的聚类算法。本文就针对数据挖掘中传统的聚类算法进行了归纳和分 类，总结了各种算法的思想并分析其性能特点。 二 聚类算法分类 图1 聚类算法分类图 三 传统聚类算法 3.1 基于划分的聚类 基于划分的聚类给定一个包含n个数据对象的数据库，以及要生成的类的数目k，一个划分方法将数据对象组织 成k个划分(k≤n)，其中每个划分代表一个类。也就是说，它将数据划分为k个组，同时满足如下的要求：①每个组 至少包含一个对象；②每个对象必须属于且只属于一个组(在某些模糊划分技术中此要求可以放宽) 。划分方法的基 本思想是：给定要构建的划分的数目k，首先创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象 在划分间移动来改进划分。划分方法中最著名和最常用的是k-means、k-modes和它们的变种。 3.1.1 K-means 算法 K 均值算法比较简单，首先，选择K 个初始质心，其中K 是用户指定的参数，即所期望的簇的个数。每个点指 派到最近的质心，而指派到一个质心的点集为一个簇。然后，根据指派到簇的点，更新每个粗的质心。重复指派和 更新步骤，直到簇不发生变化，或等价地，直到质心不发生变化。 K-means 算法基本步骤如下： 输入：D：数据集 K：质心个数 输出：较优的质心集合 1：选择K 个点作为初始质心。 2 ：repeat 3 ： 将每个点指派到最近的质心，形成K 个簇。 4 ： 重新计算每个簇的质心。 5 ：until 质心不发生变化。 K-means 的空间需求是适度的，因为只需要存放数据点和质心。具体地说，所需要的存储量为O((m+K)n)，其中 m 是点数，n 是属性数。K 均值的时间需求也是适度的—基本上与数据点个数线性相关。具体地说，所需要的时间 为O(I*K*m*n)，其中I 是收敛所需要的迭代次数。 3.1.2 K-modes 算法 k-modes 算法是在数据挖掘中对分类属性型数据的采用的聚类算法。k-modes 算法是对k-means 算法的扩展。 k-means 算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理数值型数据，而不能处理分类属性型数据。例 如表示人的属性有：姓名、性别、年龄、家庭住址等属性。而k-modes 算法就能够处理分类属性型数据。k-modes 算法采用差异度来代替k-means 算法中的距离。k-modes 算法中差异度越小，则表示距离越小。一个样本和一个聚 类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。这个和就是某个样本到某 个聚类中心的差异度。该样本属于差异度最小的聚类中心。 知识点 1、Dissimilarity measure ,where 2、簇的modes： 新形成的簇的modes 就是，每个出现最频繁的属性值的集合。 算法大致步骤 1：初始化K 个modes 2：分配所有的点到差异度最小的modes 中去 3 ：重新计算每个簇的modes 4 ：重复2-3 步骤，直到modes 不发生变化，或者变化很小。 K-Modes 聚类算法的时间复杂