[理学]第4章聚类分析

《[理学]第4章聚类分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章聚类分析4.1概述4.2基于划分的聚类算法4.3层次聚类算法4.4基于密度的聚类算法4.5基于图的聚类算法4.6一趟聚类算法4.7基于原型的聚类算法4.8聚类算法评价4.1概述简单地描述，聚类(Clustering)是将数据集划分为若干相似对象组成的多个组(group)或簇(cluster)的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。或者说一个簇(cluster)就是由彼此相似的一组对象所构成的集合，不同簇中的对象通常不相似或相似度很低。类间相似度最小化(距离最大化)类内相似度

2、最大化(距离最小化)从机器学习的角度看，聚类是一种无监督的机器学习方法，即事先对数据集的分布没有任何的了解，它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。聚类分析中“簇”的特征：聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划分聚的数目和结构都没有事先假定注意：聚类也可以是不明确的有多少聚类？四个类2个类六个类聚类分析正在蓬勃发展，广泛应用于一些探索性领域,如统计学与模式分析，金融分析，市场营销，决策支持，信息检索，WEB

3、挖掘，网络安全，图象处理，地质勘探、城市规划，土地使用、空间数据分析，生物学，天文学，心理学，考古学等。4.1.1聚类分析研究的主要内容(1)模式表示(包括特征提取和/或选择)；(2)适合于数据领域的模式相似性定义；(3)聚类或划分算法；(4)数据摘要；(5)输出结果的评估。4.1.2数据挖掘对聚类算法的要求聚类是一个富有挑战性的研究领域，数据挖掘对聚类的典型要求如下：(1)可伸缩性(Scalability)(2)处理不同类型属性的能力(3)发现任意形状的聚类(4)用于决定输入参数的领域知识最小化(5)对于输入

4、记录顺序不敏感(6)高维性(7)处理噪音和异常数据的能力(8)基于约束的聚类(9)可解释性4.1.3典型聚类方法简介划分方法(partitioningmethods)基于质心(K-means)、中心的划分方法层次的方法(hierarchicalmethods)BIRCH、ROCK、CURE基于密度的方法DBSCAN、OPTICS基于图的方法Chameleon、SNN基于网格的方法(grid-basedmethods)STING、WaveCluster、CLIQUE基于模型的方法(model-basedmetho

5、ds)EM、COBWEB、神经网络其他聚类方法谱聚类算法(spectralclustering)、蚁群聚类算法等基于划分的聚类原始数据点基于划分的聚类结果基于层次的聚类传统的层次聚类非传统的基于层次的聚类非传统的树图传统的基于层次的树图4.2基于划分的聚类算法给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k<=n。也就是说，它将数据划分为k个组，同时满足如下的要求：(1)每个组至少包含一个对象；(2)每个对象必须属于且只属于一个组。划分式聚类算法需要预先指定簇数目或簇

6、中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。这类方法分为基于质心的(Centroid-based)划分方法和基于中心的(Medoid-based)划分方法。4.2.1基本k-means聚类算法k-means聚类算法：(1)从数据集D中任意选择k个对象作为初始簇中心；(2)repeat(3)for数据集D中每个对象Pdo(4)计算对象P到k个簇中心的距离(5)将对象P指派到与其最近(距离最短)的簇；(6)endfor(7)计算每个簇中对象的均值，做为新的簇的中心；(8)

7、untilk个簇的簇中心不再发生变化K-means算法采用来表示一个簇k-means聚类算法示例-1例4.1对表4-1中二维数据，使用k-means算法将其划分为2个簇，假设初始簇中心选为P7(4，5)，P10(5，5)。表4-1k-means聚类过程示例数据集1解：图4-2显示了对于给定的数据集k-means聚类算法的执行过程。(1)根据题目，假设划分的两个簇分别为C1和C2，中心分别为(4，5)和(5，5)，下面计算10个样本到这2个簇中心的距离，并将10个样本指派到与其最近的簇：(2)第一

8、轮迭代结果如下：属于簇C1的样本有：{P7，P1，P2，P4，P5，P8}属于簇C2的样本有：{P10，P3，P6，P9}重新计算新的簇的中心，有：C1的中心为(3.5，5.167)，C2的中心为(6.75，4.25)P1P2P3P4P5P6P7P8P9P10x3374384475y4637855145k-means聚类算法示例-2(3)继续计算10个样本到新的簇的中心的距离，重新分配