第4章聚类分析.ppt

第4章聚类分析 概述 基于划分的聚类算法 层次聚类算法 基于密度的聚类算法 基于图的聚类算法 一趟聚类算法 基于原型的聚类算法 聚类算法评价 概述简单地描述, 聚类(Clustering) 是将数据集划分为若干相似对象组成的多个组(group) 或簇(cluster) 的过程,使得同一组中对象间的相似度最大化,不同组中对象间的相似度最小化。或者说一个簇(cluster) 就是由彼此相似的一组对象所构成的集合,不同簇中的对象通常不相似或相似度很低。类间相似度最小化(距离最大化) 类内相似度最大化(距离最小化) 从机器学习的角度看,聚类是一种无监督的机器学习方法, 即事先对数据集的分布没有任何的了解,它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。聚类方法的目的是寻找数据中:潜在的自然分组结构和感兴趣的关系。聚类分析中“簇”的特征: ?聚类所说的簇不是事先给定的,而是根据数据的相似性和距离来划分?聚的数目和结构都没有事先假定注意:聚类也可以是不明确的有多少聚类? 有多少聚类? 四个类 2个类六个类聚类分析正在蓬勃发展,广泛应用于一些探索性领域,如统计学与模式分析,金融分析,市场营销,决策支持,信息检索, WEB 挖掘,网络安全,图象处理,地质勘探、城市规划,土地使用、空间数据分析,生物学,天文学,心理学,考古学等。 聚类分析研究的主要内容?(1) 模式表示(包括特征提取和/或选择); ?(2) 适合于数据领域的模式相似性定义; ?(3) 聚类或划分算法; ?(4) 数据摘要; ?(5) 输出结果的评估。特征选择/ 提取模式相似性计算划分模式表示模式聚类结果反馈回路 数据挖掘对聚类算法的要求聚类是一个富有挑战性的研究领域,数据挖掘对聚类的典型要求如下: (1) 可伸缩性(Scalability) (2) 处理不同类型属性的能力(3) 发现任意形状的聚类(4) 用于决定输入参数的领域知识最小化(5) 对于输入记录顺序不敏感(6) 高维性(7) 处理噪音和异常数据的能力(8) 基于约束的聚类(9) 可解释性 典型聚类方法简介?划分方法(partitioning methods) 基于质心(K-means) 、中心的划分方法?层次的方法(hierarchical methods) BIRCH 、 ROCK 、 CURE ?基于密度的方法 DBSCAN 、 OPTICS ?基于图的方法 Chameleon 、 SNN ?基于网格的方法(grid-based methods ) STING 、 WaveCluster 、 CLIQUE ?基于模型的方法(model-based methods) EM 、 COBWEB 、神经网络?其他聚类方法谱聚类算法(spectral clustering) 、蚁群聚类算法等基于划分的聚类原始数据点基于划分的聚类结果基于层次的聚类 p4 p1p3 p2 p4 p1 p3 p2 p4 p1p2p3 p4 p1p2p3 传统的层次聚类非传统的基于层次的聚类非传统的树图传统的基于层次的树图