第6章聚类分析.ppt
《第6章聚类分析.ppt》由会员分享,可在线阅读,更多相关《第6章聚类分析.ppt(168页珍藏版)》请在三一文库上搜索。
1、1,第6章 聚类分析,什么是聚类(Clustering)分析? 聚类分析中的数据类型 主要聚类方法分类 划分方法(Partitioning Methods) 层次方法(Hierarchical Methods) 基于密度的方法(Density-Based Methods) 基于网格的方法(Grid-Based Methods) 基于模型的聚类方法(Model-Based Clustering Methods) 孤立点分析(Outlier Analysis) 小结,2,什么是聚类分析?,聚类: 数据对象的集合/簇 (cluster) 同一簇中的对象彼此相似 不同簇中的对象彼此相异 聚类分析 将数
2、据对象分组成为多个类或簇 聚类是无指导的分类: 没有预先定义的类 典型应用 作为洞察数据内部分布的独一无二的工具 作为其它算法的预处理步骤,3,聚类的一般应用,模式识别 空间数据分析 聚类产生GIS(地理信息系统)的专题地图thematic maps 在空间数据挖掘中检测空间聚类并解释它们 图象处理 经济科学 (特别是市场研究) WWW 文本分类 Web日志数据聚类,发现类似访问模式群,4,聚类应用的例子,市场营销: 帮助市场营销者发现他们的基本顾客的不同组群,然后利用这一知识制定有针对性的营销计划 国土利用 在地球观测数据库中识别类似的国土使用区域 保险 对汽车保险持有者的分组 城市规划 根
3、据房子的类型,价值,和地理位置对一个城市中房屋的分组 地震研究 应当将观测到的地震震中沿大陆板块断裂进行聚类,5,什么是好的聚类方法?,一个好的聚类方法应当产生高质量的聚类 类内相似性高 类间相似性低 聚类结果的质量依赖于方法所使用的相似性度量和它的实现. 聚类方法的质量也用它发现某些或全部隐藏的模式的能力来度量,6,数据挖掘对聚类的要求,可伸缩性 有的算法当数据对象少于200时处理很好, 但对大量数据对象偏差较大 大型数据库包含数百万个对象 处理不同属性类型的能力 许多算法专门用于数值类型的数据 实际应用涉及不同的数据类型,i.e. 混合了数值和分类数据 发现任意形状的聚类 基于距离的聚类趋
4、向于发现具有相近尺度和密度的球状簇 一个簇可能是任意形状的,7,数据挖掘对聚类的要求(续),用于决定输入参数的领域知识最小化 许多聚类算法要求用户输入一定的参数, 如希望产生的簇的数目.聚类结果对于输入参数十分敏感 参数难以确定, 增加了用户的负担, 使聚类质量难以控制 处理噪声数据和孤立点的能力 一些聚类算法对于噪音数据敏感, 可能导致低质量的聚类结果 现实世界中的数据库大都包含了孤立点, 空缺, 或者错误的数据 对于输入记录的顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的, 以不同的次序输入会导致不同的聚类,8,数据挖掘对聚类的要求(续),高维性(high dimensionality
5、) 许多聚类算法擅长处理低维的数据, 可能只涉及两到三维 数据库或者数据仓库可能包含若干维或者属性, 数据可能非常稀疏, 而且高度偏斜 整合用户指定的约束 现实世界的应用可能需要在各种约束条件下进行聚类 要找到既满足特定的约束, 又具有良好聚类特性的数据分组是一项具有挑战性的任务 可解释性和可用性 用户希望聚类结果是可解释的, 可理解的, 和可用的 聚类可能需要和特定的语义解释和应用相联系,9,第6章. 聚类分析,什么是聚类(Clustering)分析? 聚类分析中的数据类型 主要聚类方法分类 划分方法(Partitioning Methods) 层次方法(Hierarchical Metho
6、ds) 基于密度的方法(Density-Based Methods) 基于网格的方法(Grid-Based Methods) 基于模型的聚类方法(Model-Based Clustering Methods) 孤立点分析(Outlier Analysis) 小结,10,数据结构,数据矩阵 (two modes) 相异度矩阵 (Dissimilarity matrix) (one mode),11,评估聚类的质量,有一个单独的“质量”函数, 它度量聚类的“好坏”. 很难定义“足够类似”或“足够好” 对此问题是相当主观的. 相异度/相似度矩阵 相似性用距离函数表示, 通常记作 d(i, j) 对于
7、区间标度变量, 二元变量, 标称变量, 序数和比例标度变量, 距离函数的定义通常是很不相同的. 根据应用和数据语义, 不同的变量应赋予不同的权.,12,聚类分析的数据类型,区间标度变量(Interval-scaled variables) 二元变量(Binary variables) 标称(名词性), 序数, 和比例标度变量(Nominal, ordinal, and ratio variables) 混合类型变量(Variables of mixed types),13,区间标度变量,区间标度变量:一种粗略线形标度的连续度量 为了避免度量单位的影响,数据标准化 (1)计算平均绝对偏差: 其中
8、 (2)计算标准化的度量值 (z-score) 使用平均绝对偏差比使用标准差更具有鲁棒性,14,对象之间的相似性/相异性,通常, 使用距离来度量两个数据对象之间的相似性/相异性 常用的距离包括:闵可夫斯基(Minkowski) 距离: 其中 i = (xi1, xi2, , xip)和 j = (xj1, xj2, , xjp) 是两个 p-维数据对象(q 正整数) 如果q = 1, d是曼哈坦 (Manhattan)距离,15,对象之间的相似性/相异性,如果 q = 2, d是欧几里德(Euclidean)距离 : 距离的性质 非负性: d(i,j) 0 自身到自身的距离为0: d(i,i)
9、 = 0 对称性: d(i,j) = d(j,i) 三角不等式: d(i,j) d(i,k) + d(k,j) 也可以使用加权的距离, 如加权的欧几里德距离,16,二元变量,二元变量(binary variable )只有两个状态0或1. 0表示该变量为空, 1表示该变量存在 例如, 描述病人的变量smoker, 1表示病人抽烟, 而0表示病人不抽烟 计算二元变量的相似度 假定所有二元变量具有相同的权重, 则得到一个两行两列的可能性表(contingency table),对象 i,对象 j,17,二元变量,对称的: 二元变量的两个状态具有同等价值,并具有相同的权重 例: 性别是对称的二元变量
10、 恒定的相似度: 基于对称的二元变量的相似度, 当一些或全部二元变量编码改变时, 计算结果不会发生变化 对称的二元变量的相异度计算-简单匹配系数 不对称的: 二元变量的两个状态的输出不是同样重要 例: 疾病检查结果的肯定和否定.,18,二元变量(续),根据惯例, 比较重要的输出结果是出现几率较小的 例: HIV阳性是比较重要的结果,出现几率较小, 而HIV阴性(正常情况)出现几率较大 通常, 比较重要的输出结果编码为1, 另一种结果编码为0 两个都取1的情况(正匹配)比两个都取0的情况(负匹配)更有意义. -非恒定的相似度 对于非对称的相似度, 负匹配数目t被忽略. 采用Jaccard系数,1
11、9,二元变量之间的相异度,例 gender 是对称的 其余都不是对称的 Y和P的值设置为1, 而 N的值设置为 0,20,标称变量-分类变量,名义变量,标称变量(Nominal variable)是二元变量的拓广, 它可以取多于两种状态值, 如, red, yellow, blue, green 方法1: 简单匹配 m:状态取值匹配的变量数目, p: 变量总数 方法 2:(可以用非对称的二元变量对标称变量编码)使用大量二元变量, 对M个标称状态的每一个, 创建一个新的二元变量. 对于一个有特定状态值的对象, 对应状态值的二元变量值置1, 其余二元变量的值置0,21,序数型变量,序数型变量(or
12、dinal variable)可以是离散的, 也可以是连续的 离散的序数型变量类似于标称变量, 但序数型变量的M个状态是以有意义的序列排序 连续的序数型变量看起来像一个未知刻度的连续数据的集合. 值的相对顺序是必要的, 而其实际的大小则不重要 将区间标度变量的值域划分为有限个区间, 从而将其值离散化, 也可以得到序数型变量 序数型变量的值可以映射为秩(rank). 例如, 假设变量f有Mf个状态, 这些有序的状态定义了一个排列1,Mf,22,序数型变量(续),相异度计算可以用类似于区间标度变量的方法处理 设第i 个对象f 的值为 xif , 用对应的值rif 替代xif, 其中 rif 1,M
13、f 将每个变量的值域映射到0, 1区间, 以便每个变量都具有相同的权重: 用下式替换rif 使用区间标度变量计算距离的方法计算相异度, z if作为第i 个对象f 的值,23,比例标度变量,比例标度变量(Ratio-scaled variable)非线性的刻度上取正的度量值,例如指数标度,近似地遵循如下的公式 AeBt 或Ae-Bt 相异度计算: 采用与处理区间标度变量同样的方法 不是好的选择! (为什么?标度可能被扭曲) 进行对数变换 yif = log(xif) 将xif看作连续的序数型数据, 将其秩作为区间标度值 方法的选取取决于应用, 但后两种方法比较有效,24,混合类型变量,数据库可
14、能包含所有六种类型 对称的二元变量, 不对称的二元变量, 标称的, 序数的, 区间的, 比例标度的 如何计算混合类型变量描述的对象的相异度? 方法1: 将变量按类型分组, 对每种类型的变量单独进行聚类分析 如果这些分析得到兼容的结果, 这种方法是可行的 在实际的应用中, 这种方法行不通 方法2:将所有的变量一起处理, 只进行一次聚类分析. 将不同类型的变量组合在单个相异度矩阵中, 把所有变量转换到共同的值域区间0.0, 1.0上,25,混合类型变量(续),假设数据集包含p个不同类型的变量,对象i 和j 之间的相异度d(i,j)定义为 其中, 如果xif或xjf 缺失(即对象i 或对象j 没有变
15、量f 的度量值)或者xif =xjf=0, 且变量f 是不对称的二元变量, 则指示项 ; 否则, 指示项 变量f 对i 和j 之间相异度的计算方式与其具体类型有关 如果f 是二元或标称变量: 如果 xif = xjf , dij(f) = 0; 否则 dij(f) = 1,26,混合类型变量(续),如果f 是区间标度变量, 使用规格化的距离 如果f 是序数型或比例标度型变量 计算秩rif 和 将 zif 作为区间标度变量对待,27,向量对象,向量x和y 余弦度量 Tanimoto系数,28,第8章. 聚类分析,什么是聚类(Clustering)分析? 聚类分析中的数据类型 主要聚类方法分类 划
16、分方法(Partitioning Methods) 层次方法(Hierarchical Methods) 基于密度的方法(Density-Based Methods) 基于网格的方法(Grid-Based Methods) 基于模型的聚类方法(Model-Based Clustering Methods) 孤立点分析(Outlier Analysis) 小结,29,主要聚类方法的分类,划分方法(Partitioning method): 构造n个对象数据库D的划分, 将其划分成k个聚类满足如下的要求: 每个组至少包含一个对象 每个对象必须属于且只属于一个组 在某些模糊划分技术中, 第二个要求可
17、以放宽 基本方法: 首先创建一个初始划分. 然后采用一种迭代的重定位技术, 尝试通过在划分间移动对象来改进划分 好的划分的一般准则: 在同一个类中的对象之间尽可能“接近”或相关, 而不同类中的对象之间尽可能“远离”或不同,30,主要聚类方法的分类(续),全局最优: 穷举所有可能的划分 启发式方法: k-平均值(k- means)和 k-中心点(k- medoids) 算法 k-平均值(MacQueen67): 每个簇用该簇中对象的平均值来表示 k-中心点或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每个簇用接近聚类中心的一个
18、对象来表示 这些启发式算法适合发现中小规模数据库中的球状聚类 对于大规模数据库和处理任意形状的聚类,这些算法需要进一步扩展,31,主要聚类方法的分类(续),层次方法(Hierarchy method): 对给定数据对象集合进行层次的分解 两种层次方法 凝聚方法, 也称为自底向上的方法: 开始将每个对象作为单独的一个组; 然后继续地合并相近的对象或组, 直到所有的组合并为一个(层次的最上层), 或者达到一个终止条件 分裂方法, 也称为自顶向下的方法: 开始将所有的对象置于一个簇; 在迭代的每一步, 一个簇被分裂为更小的簇, 直到最终每个对象在单独的一个簇中, 或者达到一个终止条件,32,主要聚类
19、方法的分类(续),层次方法的缺点: 一个步骤一旦完成便不能被撤消. 该规定可以避免考虑选择不同的组合, 减少计算代价 问题: 不能更正错误的决定 改进层次聚类结果的措施 在每层划分中, 仔细分析对象间的“联接”, 例如CURE和Chameleon中的做法 综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法,然后用迭代的重定位来改进结果。例如在BIRCH中的方法,33,主要聚类方法的分类(续),基于密度的方法(Density-based method): 基于密度函数 基本思想: 只要临近区域的密度(对象或数据点的数目)超过某个阀值, 就继续聚类. 也就是说, 对给定类中的每个数据点, 在
20、一个给定范围的区域中必须至少包含一定数目的点 该方法可以用来过滤“噪音”数据,发现任意形状的簇 DBSCAN是一个有代表性的基于密度的方法, 它根据一个密度阀值来控制簇的增长 OPTICS是另一个基于密度的方法, 它为自动的, 交互的聚类分析计算一个聚类顺序,34,主要聚类方法的分类(续),基于网格的方法(Grid-based method): 把对象空间量化为有限数目的单元, 形成了一个网格结构. 所有的聚类操作都在这个网格结构(即量化的空间)上进行 这种方法的主要优点是它的处理速度很快, 其处理时间独立于数据对象的数目, 只与量化空间中每一维的单元数目有关 STING是基于网格方法的一个典
21、型例子 CLIQUE和WaveCluster这两种算法既是基于网格的, 又是基于密度的,35,主要聚类方法的分类(续),基于模型的方法(Model-based Method): 基于模型的方法为每个簇假定了一个模型, 寻找数据对给定模型的最佳拟合,36,第6章. 聚类分析,什么是聚类(Clustering)分析? 聚类分析中的数据类型 主要聚类方法分类 划分方法(Partitioning Methods) 层次方法(Hierarchical Methods) 基于密度的方法(Density-Based Methods) 基于网格的方法(Grid-Based Methods) 基于模型的聚类方法
22、(Model-Based Clustering Methods) 孤立点分析(Outlier Analysis) 小结,37,划分方法,划分方法: 构造n个对象数据库D的划分, 将其划分成k个聚类 给定 k, 找k 个clusters 对于选定的划分标准它是最优的 全局最优(Global optimal): 枚举所有的划分 启发式方法(Heuristic methods): k-平均(k-means)和k-中心点(k-medoids)算法 k-平均(MacQueen67): 每个簇用簇的重心( 簇的平均值) 表示 k-中心点或PAM (Partition around medoids) (Ka
23、ufman & Rousseeuw87): 每个簇用接近聚类中心的一个对象来表示,38,k-平均聚类算法,算法: k-平均 (1) 任意选择k个对象作为初始的簇中心; (2) repeat (3) 根据簇中对象的平均值, 将每个对象(重新)赋给最类似的簇; (4) 更新簇的平均值, 即重新计算每个簇中对象的平均值; (5) until 不再发生变化 通常, 采用平方误差准则作为收敛函数, 其定义如下 其中, mi是簇Ci的平均值 该准则试图使生成的结果簇尽可能紧凑, 独立,39,k-平均聚类算法(续),例,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,1
24、0,K=2 任意选择 K个对象作为初始聚类中心,将每个对象赋给最类似的中心,更新簇的平均值,重新赋值,更新簇的平均值,重新赋值,40,k-平均聚类算法(续),优点: 相对有效性: O(tkn), 其中 n 是对象数目, k 是簇数目, t 是迭代次数; 通常, k, t n. 比较: PAM: O(k(n-k)2 ), CLARA: O(ks2 + k(n-k) 当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好 Comment: 常常终止于局部最优. 全局最优 可以使用诸如确定性的退火(deterministic annealing)和遗传算法(genetic algorithms)等技
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 聚类分析
链接地址:https://www.31doc.com/p-3130281.html