第11章 数据挖掘聚类分析.ppt

数据挖掘 聚类分析 引言 “物以类聚，人以群分”。对事物进行分类，是人们认识事物的出发点，也是人们认识世界的一种重要方法。因此，分类学已成为人们认识世界的一门基础科学。 在生物、经济、社会、人口等领域的研究中，存在着大量量化分类研究。例如：在生物学中，为了研究生物的演变，生物学家需要根据各种生物不同的特征对生物进行分类。 在经济研究中，为了研究不同地区城镇居民生活中的收入和消费情况，往往需要划分不同的类型去研究。 在地质学中，为了研究矿物勘探，需要根据各种矿石的化学和物理性质和所含化学成分把它们归于不同的矿石类。 在人口学研究中，需要构造人口生育分类模式、人口死亡分类状况，以此来研究人口的生育和死亡规律。 但历史上这些分类方法多半是人们主要依靠经验作定性分类，致使许多分类带有主观性和任意性，不能很好地揭示客观事物内在的本质差别与联系；特别是对于多因素、多指标的分类问题，定性分类的准确性不好把握。 为了克服定性分类存在的不足，人们把数学方法引入分类中，形成了数值分类学。 后来随着多元统计分析的发展，从数值分类学中逐渐分离出了聚类分析方法。 随着计算机技术的不断发展，利用数学方法研究分类不仅非常必要而且完全可能，因此近年来，聚类分析的理论和应用得到了迅速的发展。 聚类分析就是分析如何对样品（或变量-在多元统计中，它就是一个向量）进行量化分类的问题。通常聚类分析分为Q型聚类和R型聚类。Q型聚类是对样品进行分类处理，R型聚类是对变量进行分类处理。 什么是聚类 聚类（clustering）就是将数据分组成多个簇（cluster），使得同一个簇的对象之间具有较高的相似度，不同簇的对象相异 早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗、动物和植物 聚类无所不在 聚类无所不在 聚类无所不在 聚类的应用领域 有贡献的领域 什么情况下应该聚类 聚类分析原理 聚类与分类 相似性及其度量 从复杂数据中提取相对简单分组结构的主要工作是找到一个“紧密度”或相似性度量 “当我们看到它的时候，我们即可领会” 基于特征来测量相似性 产生特征 提炼特征 规范化特征 减少特征 测量相似性 在选择相似性度量时掺杂着大量的主观因素：变量的本质（离散的、连续的、二值的）或测量刻度（标称的、顺序的、间隔的、比值的）及主题知识 当所有项被聚类后，通常用距离表明邻近度 变量通常基于相关系数或关联度量而聚合 距离度量的常见计算方法 令O1和O2表示客观世界中的两个对象，O1和O2之间的距离（相异性）是一个实数，用distance(O1,O2)或d(O1，O2) 明考夫斯基距离 （4）幂距离 （5）差异百分率 二元属性对象的相似性 当项不能用有意义的p维测量表示时，项对之间的比较通常根据某些特征的存在和缺失完成，相似的项具有更多的共同项 引入二元变量来描述是否具有某种特征，若具有该特征变量值为1，否则变量值为0 个体对的变量得分计算得分矩阵 1 1的个数为a 1 0的个数为b 0 1的个数为c 0 0的个数为d 相似性系数 简单匹配系数SMC Jaccard系数 Rao系数 实例分析 聚类的基本类型 层次聚类 自底向上（凝聚） 假定所有项属于一个单独簇，然后寻找最佳配对并合并成一个新的簇 自顶向下（分裂） 开始将所有数据看作一个簇，考虑所有可能的方法，将簇一分为二选择最佳划分，并递归第在这两个上继续划分 凝聚层次聚类 依靠共同的距离度量，聚类过程从寻找距离最近的簇开始，并把这两个簇合并为一个簇。 在开始时，让每个对象自成一簇，每个簇都以选定的距离度量定义 合并后，如何确定新簇之间的距离？？？ 单连接（single linkage） 完全连接（complete linkage） 单连接（最近邻） 两个簇的距离由不同簇的两个最近的对象间的距离决定 簇的距离是属于不同簇的两个样本间的最近距离 d(c1,c2)=min{d(o,O)} 完全连接（最远邻） 两个簇的距离隶属于不同簇的距离最远的两个对象的距离所决定（最远邻的距离） 组平均 两个簇的距离就是隶属不同簇的所有对象的距离的平均 加权平均 组质心 加权组质心 沃德法 单连接 完全连接 层次聚类的优缺点 优点 可以通过观察树状图来确定正确的簇数目 层次的本质很好地反映了人类对某些领域的直觉 树状图的一个潜在应用时可以用来检测离群点 缺点 有时会表现出无意义的或者不合逻辑的模式 无需事先指定簇的数目 层次本质很好地反映了人类对某些领域认识的直觉 可伸缩性不好：时间复杂性至少为O(n2),n是所有对象的数量 和任何启发式搜素算法一样，局部最优是一个问题 对结果的解释具有主观性 算法的步骤 决定k的取值 初始化k个簇中心 通过把对象分配给最近的簇中心来确定N