第4章聚类分.ppt

第4章 聚类分析;4.1 概述; 从机器学习的角度看，聚类是一种无监督的机器学习方法，即事先对数据集的分布没有任何的了解，它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。 聚类分析中“簇”的特征： 聚类所说的簇不是事先给定的，而是根据数据的相似性和距离来划分 聚的数目和结构都没有事先假定 ;注意：聚类也可以是不明确的;聚类分析正在蓬勃发展，广泛应用于一些探索性领域,如统计学与模式分析，金融分析，市场营销，决策支持，信息检索，WEB挖掘，网络安全，图象处理，地质勘探、城市规划，土地使用、空间数据分析，生物学，天文学，心理学，考古学等。;4.1.1 聚类分析研究的主要内容 ;4.1.2 数据挖掘对聚类算法的要求 聚类是一个富有挑战性的研究领域，数据挖掘对聚类的典型要求如下： (1)可伸缩性(Scalability) (2)处理不同类型属性的能力 (3)发现任意形状的聚类 (4)用于决定输入参数的领域知识最小化 (5)对于输入记录顺序不敏感 (6)高维性 (7)处理噪音和异常数据的能力 (8)基于约束的聚类 (9)可解释性;4.1.3 典型聚类方法简介 ;基于划分的聚类;基于层次的聚类;4.2 基于划分的聚类算法;4.2.1 基本k-means聚类算法 ;k-means聚类算法示例-1;k-means聚类算法示例-2;;; (a) 大小不同的簇 (b) 形状不同的簇 图4.3 基于质心的划分方法不能识别的数据 ;4.2.2 二分k-means算法 ;4.2.3 k-means聚类算法的拓展 -1;定义4-1 给定簇C， ，a 在C中关于Di 的频度定义为C在 Di上的投影中包含a 的次数： 定义4-2 给定簇C，C的摘要信息CSI(Cluster Summary Information)定义为： ，其中 为C的大小, 由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即： ;定义4-3 给定D的簇C、 和 ,对象 与 ， x0。 (1)对象p，q在属性i上的差异程度(或距离) 定义为： 对于分类属性或二值属性， ; 对于连续数值属性或顺序属性， ； (2)两个对象p，q间的差异程度(或距离) 定义为： ; ;(3)对象p与簇C间的距离 定义为p与簇C的摘要之间的距 离： 。 这里 为p与C在属性 上的距离，对于分类属性 其值定义为p与C中每个对象在属性 上的距离的算术平均值，即 ；对于数值属性 其值定义为 。 (4) 簇C1与C2间的距离 定义为两个簇的摘要间的距离： 。 ;这里 为 与 在属性 上的距离，对于分类属性 其值定义为 中每个对象与 中每个对象的差异的平均值：