第7章数据挖掘

1、2021-7-12021-7-1数据挖掘数据挖掘1 第六章第六章 聚聚 类类 分分 析析 l什么是聚类分析？什么是聚类分析？ l主要聚类方法的分类主要聚类方法的分类 l划分方法划分方法 l层次方法层次方法 l基于密度的方法基于密度的方法 l基于网格的方法基于网格的方法 l聚类的评估聚类的评估 l基于模型的聚类方法基于模型的聚类方法 l小结小结 2021-7-12021-7-1数据挖掘数据挖掘2 聚类的普遍应用聚类的普遍应用 2021-7-12021-7-1数据挖掘数据挖掘3 聚类的应用举例聚类的应用举例 2021-7-12021-7-1数据挖掘数据挖掘4 什么是好的聚类？什么是好的聚类？ 20

2、21-7-12021-7-1数据挖掘数据挖掘5 数据挖掘对聚类的要求数据挖掘对聚类的要求 l可伸缩性可伸缩性 l处理不同类型属性的能力处理不同类型属性的能力 l发现任意形状的聚类发现任意形状的聚类 l对于决定输入参数的领域知识需求最小对于决定输入参数的领域知识需求最小 l处理带噪声数据的能力处理带噪声数据的能力 l增量聚类和对输入记录的次序不敏感增量聚类和对输入记录的次序不敏感 l高维性高维性 l基于约束的聚类基于约束的聚类 l可解释性和可用性可解释性和可用性 聚类方法的比较准则聚类方法的比较准则 l划分准则划分准则 l簇的分离性簇的分离性 l相似性度量相似性度量 l聚类空间聚类空间 2021

3、-7-12021-7-1数据挖掘数据挖掘6 2021-7-12021-7-1数据挖掘数据挖掘7 主要聚类方法的分类主要聚类方法的分类 2021-7-12021-7-1数据挖掘数据挖掘8 划分算法：基本概念划分算法：基本概念 2021-7-12021-7-1数据挖掘数据挖掘9 K-平均聚类算法平均聚类算法 2 1 i k i ip C Epm 平方误差准则函平方误差准则函 数数 2021-7-12021-7-1数据挖掘数据挖掘10 2021-7-12021-7-1数据挖掘数据挖掘11 K-平均方法的特点平均方法的特点 局局 2021-7-12021-7-1数据挖掘数据挖掘12 K-平均方法的变种

4、平均方法的变种 lK-K-平均法在以下策略上的不同，有一些变种平均法在以下策略上的不同，有一些变种 lK K个平均值的选择个平均值的选择 l相异度的计算相异度的计算 l计算聚类平均值的策略计算聚类平均值的策略 l处理分类数据：处理分类数据：K-K-模方法模方法 l用模来代替聚类的平均值用模来代替聚类的平均值 l使用新的相异性度量来处理分类对象使用新的相异性度量来处理分类对象 l采用相关的定理来修改聚类的模采用相关的定理来修改聚类的模 l分类数据和数值数据的混合分类数据和数值数据的混合: :K-K-原型方法原型方法 2021-7-12021-7-1数据挖掘数据挖掘13 K-中心点聚类方法中心点聚

5、类方法 1 E j k j jp C po 绝对误差标准绝对误差标准 2021-7-12021-7-1数据挖掘数据挖掘14 K-中心点聚类方法中心点聚类方法 2021-7-12021-7-1数据挖掘数据挖掘15 PAM（围绕中心点的划分）（围绕中心点的划分） 2021-7-12021-7-1数据挖掘数据挖掘16 CLARA(Clustering large application) 2021-7-12021-7-1数据挖掘数据挖掘17 层次方法层次方法 2021-7-12021-7-1数据挖掘数据挖掘18 AGNES (Agglomerative Nesting) 2021-7-12021-7

6、-1数据挖掘数据挖掘19 DIANA( Divisive Analysis) l与与AGNESAGNES算法相反算法相反 l最终每一个结点形成只包含它本身的簇最终每一个结点形成只包含它本身的簇 2021-7-12021-7-1数据挖掘数据挖掘20 更多关于层次聚类方法更多关于层次聚类方法 2021-7-12021-7-1数据挖掘数据挖掘21 BIRCH 2021-7-12021-7-1数据挖掘数据挖掘22 聚类特征向量聚类特征向量 2021-7-12021-7-1数据挖掘数据挖掘23 2021-7-12021-7-1数据挖掘数据挖掘24 CHAMELEON 2021-7-12021-7-1数据

7、挖掘数据挖掘25 CHAMELEON的总体框架的总体框架 2021-7-12021-7-1数据挖掘数据挖掘26 基于密度的聚类方法基于密度的聚类方法 2021-7-12021-7-1数据挖掘数据挖掘27 基于密度的聚类：背景基于密度的聚类：背景 2021-7-12021-7-1数据挖掘数据挖掘28 2021-7-12021-7-1数据挖掘数据挖掘29 DBSCAN:一个基于高度连接区域一个基于高度连接区域 的密度聚类算法的密度聚类算法 2021-7-12021-7-1数据挖掘数据挖掘30 DBSCAN:算法算法 l任意选择一个点任意选择一个点P P l找出从对象找出从对象P P关于关于EpsE

8、ps和和MinPtsMinPts密度可达的密度可达的 所有点所有点 l如果是一个中心点，则一个聚类就形成了如果是一个中心点，则一个聚类就形成了 l如果如果P P是一个边界点，没有从是一个边界点，没有从P P密度可达的密度可达的 对象，则访问数据库中其他的点对象，则访问数据库中其他的点 l继续该过程，直到所有的点被处理继续该过程，直到所有的点被处理 2021-7-12021-7-1数据挖掘数据挖掘31 基于网格的聚类方法基于网格的聚类方法 2021-7-12021-7-1数据挖掘数据挖掘32 STING:统计信息网格方法统计信息网格方法 2021-7-12021-7-1数据挖掘数据挖掘33 20

9、21-7-12021-7-1数据挖掘数据挖掘34 聚类的评估聚类的评估 l估计聚类趋势：仅当数据中存在非随机结构，聚估计聚类趋势：仅当数据中存在非随机结构，聚 类分析是有意义类分析是有意义 l确定数据集中的簇数：确定数据集中的簇数： l测定聚类的质量测定聚类的质量 2021-7-12021-7-1数据挖掘数据挖掘35 估计聚类趋势估计聚类趋势 l霍普金斯统计量：霍普金斯统计量： l均匀地从均匀地从D D的空间中抽取的空间中抽取n n个点个点p p1 1,p,p2 2,p,pn n。对于。对于 每个点找出在每个点找出在D D中的最近邻集合中的最近邻集合x xi i l均匀地从均匀地从D D的空间

10、中抽取的空间中抽取n n个点个点q q1 1,q,q2 2,q,qn n。对于。对于 每个点找出在每个点找出在D D中的最近邻集合中的最近邻集合y yi i l计算霍普金斯统计量计算霍普金斯统计量H H l如果如果D D为均匀分布，则为均匀分布，则H H大约为大约为0.50.5 2021-7-12021-7-1数据挖掘数据挖掘36 1 11 n i i nn ii ii y H xy 确定簇数确定簇数 l经验方法：对于经验方法：对于n n个数据点集合，设置簇数个数据点集合，设置簇数 大约为大约为 l肘方法：给定肘方法：给定k0k0，使用一种类似，使用一种类似k-k-均值的均值的 算法对数据集聚

11、类，并计算簇内方差和算法对数据集聚类，并计算簇内方差和 var(k)var(k)，绘制，绘制varvar关于关于k k的曲线，曲线的第一的曲线，曲线的第一 个拐点为正确的簇数个拐点为正确的簇数 l交叉验证：交叉验证： 2021-7-12021-7-1数据挖掘数据挖掘37 2 n 测定聚类质量测定聚类质量 l外在方法：有监督的方法：外在方法：有监督的方法： l簇的同质性：聚类中的簇越纯，聚类越好簇的同质性：聚类中的簇越纯，聚类越好 l簇的完全性：属于相同类别的对象分配到相同的簇簇的完全性：属于相同类别的对象分配到相同的簇 l碎布袋：把一个异种对象放入一个纯的簇中应该比碎布袋：把一个异种对象放入一

12、个纯的簇中应该比 放入碎布袋中受更大的惩罚放入碎布袋中受更大的惩罚 l小簇保持性：把小类别划分成小片比将大类别划分小簇保持性：把小类别划分成小片比将大类别划分 成小片更有害成小片更有害 2021-7-12021-7-1数据挖掘数据挖掘38 l精度：同一簇中的有多少个其他对象与该精度：同一簇中的有多少个其他对象与该 对象同属一个类别对象同属一个类别 l召回率：反映有多少同一类别的对象被分召回率：反映有多少同一类别的对象被分 配在相同的簇中配在相同的簇中 2021-7-12021-7-1数据挖掘数据挖掘39 内在方法内在方法 l轮廓系数：轮廓系数： 2021-7-12021-7-1数据挖掘数据挖掘

13、40 ( )( ) ( ) max ( ), ( ) b oa o s o a o b o O与与O所属簇的其他对所属簇的其他对 象之间的平均距离象之间的平均距离 O到不属于到不属于O的所有簇的所有簇 的最小平均距离的最小平均距离 基于概率模型的聚类算法基于概率模型的聚类算法 l期望最大化方法（期望最大化方法（EMEM） 2021-7-12021-7-1数据挖掘数据挖掘41 期望最大化方法期望最大化方法 l期望步：根据当前的模糊聚类或概率期望步：根据当前的模糊聚类或概率 簇的参数，把对象指派到簇中簇的参数，把对象指派到簇中 l最大化步：发现新的聚类或参数，最最大化步：发现新的聚类或参数，最 小

14、化模糊聚类的小化模糊聚类的SSESSE或基于概率模型的或基于概率模型的 聚类的期望似然聚类的期望似然 2021-7-12021-7-1数据挖掘数据挖掘42 2021-7-12021-7-1数据挖掘数据挖掘43 其他基于模型的方法其他基于模型的方法 l神经网络方法：神经网络方法： l将每个簇描述为一个标本，标本作为聚类的原将每个簇描述为一个标本，标本作为聚类的原 型型 l根据某些距离度量，新的对象可以被分配到标根据某些距离度量，新的对象可以被分配到标 本于其最相似的簇本于其最相似的簇 l竞争学习竞争学习 l采用若干单元的层次结构（神经元）采用若干单元的层次结构（神经元） l以一种以一种“ “胜者

15、全取胜者全取” ”的方式对系统当前处理的对的方式对系统当前处理的对 象进行竞争象进行竞争 2021-7-12021-7-1数据挖掘数据挖掘44 什么是离群点发现什么是离群点发现 l什么是离群点？什么是离群点？ l和其他数据相当不同的对象集和其他数据相当不同的对象集 l问题问题 l找出找出n n个离群点个离群点 l应用应用 l信用卡的欺诈检测信用卡的欺诈检测 l电信的欺诈检测电信的欺诈检测 l顾客分类顾客分类 l医疗分析医疗分析 l全局离群点：显著偏离数据集中的其余对全局离群点：显著偏离数据集中的其余对 象，又称点异常象，又称点异常 l情境离群点：关于对象的特定情境，它显情境离群点：关于对象的特定情境，它显 著地偏离其他对象，又称条件离群点著地偏离其他对象，又称条件离群点 l集体离群点：多个对象作为一个整体显著集体离群点：多个对象作为一个整体显著 地偏离整个数据集地偏离整个数据集 2021-7-12021-7-1数据挖掘数据挖掘45 离群点检测的方法离群点检测的方法 l统计学方法：假定正常的数据对象由一个统计学方法：假定正常的数据对象由一个 统计模型产生，不遵守该模型的数据是离统计模型产生，不遵守该模型的数据是离 群点群点 l基于邻近性方法：