哈尔滨医科大学《数据挖掘》第8章 聚类分析：基本概念和算法.pptVIP

(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002 (C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002 聚类分析：基本概念和算法 目录 概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点） 什么是聚类分析? 聚类分析将数据划分成有意义或有用的组（簇）。 聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。 其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。 聚类的复杂性 不同的聚类类型 划分聚类（Partitional Clustering） 层次聚类（Hierarchical Clustering） 互斥聚类（exclusive clustering） 非互斥（重叠）聚类（non-exclusive） 模糊聚类（fuzzy clustering） 完全聚类（complete clustering） 部分聚类（partial clustering） 划分聚类（Partitional Clustering） 划分成不重叠的子集，使得每个数据对象恰在一个子集。 层次聚类（Hierarchical Clustering） 嵌套簇的集族，组织成一棵树。 聚类的类型：层次的与划分的 聚类的类型：互斥的、重叠的、模糊的 互斥的（Exclusive） 每个对象都指派到单个簇. 重叠的（overlapping）或非互斥的（non-exclusive） 聚类用来反映一个对象.同时属于多个组（类）这一事实。 例如：在大学里，一个人可能既是学生，又是雇员 模糊聚类（Fuzzy clustering ） 每个对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇。换言之，簇被视为模糊集。 聚类的类型：部分、完全 部分的（Partial） 部分聚类中数据集某些对象可能不属于明确定义的组。如：一些对象可能是离群点、噪声。 完全的（complete） 完全聚类将每个对象指派到一个簇。 不同的簇类型 明显分离的 基于原型的 基于图的 基于密度的 概念簇 簇类型: 明显分离的（Well-Separated） 每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。 簇类型:基于原型的 每个对象到定义该簇的原型（质心、中心）的距离比到其他簇的原型的距离更近。 簇类型:基于图的 如果数据用图表示，其中节点是对象，而边代表对象之间的联系。 簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通的对象组。 簇类型: 基于密度的（Density-Based） 簇是对象的稠密区域，被低密度的区域环绕。 簇类型: 概念簇（Conceptual Clusters） 可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。 . 目录 概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点） 基本K均值算法（重点） 1.选择k个点作为初始的质心 2.repeat 3.将每个点指派到最近的质心，形成k个簇 4. 重新计算每个簇的质心 5.until 质心不发生变化 算法演示 算法分解演示 选择初始的质心 随机选择 从层次聚类中提取K个簇，并用这些簇的质心作为初始质心 随机选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点 二分K均值 选择了较差的初始质心的结果演示 选择了较差的初始质心的结果分解演示 二分k均值 二分k均值算法是基本k均值算法的直接扩充。它将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇。 算法演示 二分k均值算法 初始化簇表，使之包含由所有的点组成的簇。 Repeat 从簇表中取出一个簇。 for i=1 to 实验次数 do 使用基本k均值，二分选定的簇。 end for 从二分实验中选择具有最小总sse的两个簇。 将这两个簇添加到簇表中。 Until 簇表中包含k个簇。 优点与缺点 优点： 算法简单 适用于球形簇 二分k均值等变种算法运行良好，不受初始化问题的影响。 缺点： 不能处理非球形簇、不同尺寸和不同密度的簇 对离群点、噪声敏感 K均值应用 目录 概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点） 层次聚类算法（重点） 计算邻近度矩阵 Repeat 合并最近的两个簇 更新邻近性矩阵，以反映新的簇与 原来的簇之间的邻近行 Until 仅剩下一个簇 层次聚类 各种相似度和相异度