第7章数据挖掘

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

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

3、2022-4-142022-4-14数据挖掘数据挖掘7主要聚类方法的分类主要聚类方法的分类2022-4-142022-4-14数据挖掘数据挖掘8划分算法：基本概念划分算法：基本概念2022-4-142022-4-14数据挖掘数据挖掘9K-平均聚类算法平均聚类算法21ikiip CEpm平方误差准则函平方误差准则函数数2022-4-142022-4-14数据挖掘数据挖掘102022-4-142022-4-14数据挖掘数据挖掘11K-平均方法的特点平均方法的特点局局2022-4-142022-4-14数据挖掘数据挖掘12K-平均方法的变种平均方法的变种lK-K-平均法在以下策略上的不同，有一些变种

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

5、-4-14数据挖掘数据挖掘14K-中心点聚类方法中心点聚类方法2022-4-142022-4-14数据挖掘数据挖掘15PAM（围绕中心点的划分）（围绕中心点的划分）2022-4-142022-4-14数据挖掘数据挖掘16CLARA(Clustering large application)2022-4-142022-4-14数据挖掘数据挖掘17层次方法层次方法2022-4-142022-4-14数据挖掘数据挖掘18AGNES (Agglomerative Nesting)2022-4-142022-4-14数据挖掘数据挖掘19DIANA( Divisive Analysis)l与与AGNESA

6、GNES算法相反算法相反l最终每一个结点形成只包含它本身的簇最终每一个结点形成只包含它本身的簇2022-4-142022-4-14数据挖掘数据挖掘20更多关于层次聚类方法更多关于层次聚类方法2022-4-142022-4-14数据挖掘数据挖掘21BIRCH2022-4-142022-4-14数据挖掘数据挖掘22聚类特征向量聚类特征向量2022-4-142022-4-14数据挖掘数据挖掘232022-4-142022-4-14数据挖掘数据挖掘24CHAMELEON2022-4-142022-4-14数据挖掘数据挖掘25CHAMELEON的总体框架的总体框架2022-4-142022-4-14数据

7、挖掘数据挖掘26基于密度的聚类方法基于密度的聚类方法2022-4-142022-4-14数据挖掘数据挖掘27基于密度的聚类：背景基于密度的聚类：背景2022-4-142022-4-14数据挖掘数据挖掘282022-4-142022-4-14数据挖掘数据挖掘29DBSCAN:一个基于高度连接区域一个基于高度连接区域的密度聚类算法的密度聚类算法2022-4-142022-4-14数据挖掘数据挖掘30DBSCAN:算法算法l任意选择一个点任意选择一个点P Pl找出从对象找出从对象P P关于关于EpsEps和和MinPtsMinPts密度可达的密度可达的所有点所有点l如果是一个中心点，则一个聚类就形成

8、了如果是一个中心点，则一个聚类就形成了l如果如果P P是一个边界点，没有从是一个边界点，没有从P P密度可达的密度可达的对象，则访问数据库中其他的点对象，则访问数据库中其他的点l继续该过程，直到所有的点被处理继续该过程，直到所有的点被处理2022-4-142022-4-14数据挖掘数据挖掘31基于网格的聚类方法基于网格的聚类方法2022-4-142022-4-14数据挖掘数据挖掘32STING:统计信息网格方法统计信息网格方法2022-4-142022-4-14数据挖掘数据挖掘332022-4-142022-4-14数据挖掘数据挖掘34聚类的评估聚类的评估l估计聚类趋势：仅当数据中存在非随机结

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

10、集合中的最近邻集合y yi il计算霍普金斯统计量计算霍普金斯统计量H Hl如果如果D D为均匀分布，则为均匀分布，则H H大约为大约为0.50.52022-4-142022-4-14数据挖掘数据挖掘36111niinniiiiyHxy确定簇数确定簇数l经验方法：对于经验方法：对于n n个数据点集合，设置簇数个数据点集合，设置簇数大约为大约为l肘方法：给定肘方法：给定k0k0，使用一种类似，使用一种类似k-k-均值的均值的算法对数据集聚类，并计算簇内方差和算法对数据集聚类，并计算簇内方差和var(k)var(k)，绘制，绘制varvar关于关于k k的曲线，曲线的第一的曲线，曲线的第一个拐点为

11、正确的簇数个拐点为正确的簇数l交叉验证：交叉验证：2022-4-142022-4-14数据挖掘数据挖掘372n测定聚类质量测定聚类质量l外在方法：有监督的方法：外在方法：有监督的方法：l簇的同质性：聚类中的簇越纯，聚类越好簇的同质性：聚类中的簇越纯，聚类越好l簇的完全性：属于相同类别的对象分配到相同的簇簇的完全性：属于相同类别的对象分配到相同的簇l碎布袋：把一个异种对象放入一个纯的簇中应该比碎布袋：把一个异种对象放入一个纯的簇中应该比放入碎布袋中受更大的惩罚放入碎布袋中受更大的惩罚l小簇保持性：把小类别划分成小片比将大类别划分小簇保持性：把小类别划分成小片比将大类别划分成小片更有害成小片更有害

12、2022-4-142022-4-14数据挖掘数据挖掘38l精度：同一簇中的有多少个其他对象与该精度：同一簇中的有多少个其他对象与该对象同属一个类别对象同属一个类别l召回率：反映有多少同一类别的对象被分召回率：反映有多少同一类别的对象被分配在相同的簇中配在相同的簇中2022-4-142022-4-14数据挖掘数据挖掘39内在方法内在方法l轮廓系数：轮廓系数：2022-4-142022-4-14数据挖掘数据挖掘40( )( )( )max ( ), ( )b oa os oa o b oO与与O所属簇的其他对所属簇的其他对象之间的平均距离象之间的平均距离O到不属于到不属于O的所有簇的所有簇的最小平

13、均距离的最小平均距离基于概率模型的聚类算法基于概率模型的聚类算法l期望最大化方法（期望最大化方法（EMEM）2022-4-142022-4-14数据挖掘数据挖掘41期望最大化方法期望最大化方法l期望步：根据当前的模糊聚类或概率期望步：根据当前的模糊聚类或概率簇的参数，把对象指派到簇中簇的参数，把对象指派到簇中l最大化步：发现新的聚类或参数，最最大化步：发现新的聚类或参数，最小化模糊聚类的小化模糊聚类的SSESSE或基于概率模型的或基于概率模型的聚类的期望似然聚类的期望似然2022-4-142022-4-14数据挖掘数据挖掘422022-4-142022-4-14数据挖掘数据挖掘43其他基于模型

14、的方法其他基于模型的方法l神经网络方法：神经网络方法：l将每个簇描述为一个标本，标本作为聚类的原将每个簇描述为一个标本，标本作为聚类的原型型l根据某些距离度量，新的对象可以被分配到标根据某些距离度量，新的对象可以被分配到标本于其最相似的簇本于其最相似的簇l竞争学习竞争学习l采用若干单元的层次结构（神经元）采用若干单元的层次结构（神经元）l以一种以一种“ “胜者全取胜者全取” ”的方式对系统当前处理的对的方式对系统当前处理的对象进行竞争象进行竞争2022-4-142022-4-14数据挖掘数据挖掘44什么是离群点发现什么是离群点发现l什么是离群点？什么是离群点？l和其他数据相当不同的对象集和其他

15、数据相当不同的对象集l问题问题l找出找出n n个离群点个离群点l应用应用l信用卡的欺诈检测信用卡的欺诈检测l电信的欺诈检测电信的欺诈检测l顾客分类顾客分类l医疗分析医疗分析l全局离群点：显著偏离数据集中的其余对全局离群点：显著偏离数据集中的其余对象，又称点异常象，又称点异常l情境离群点：关于对象的特定情境，它显情境离群点：关于对象的特定情境，它显著地偏离其他对象，又称条件离群点著地偏离其他对象，又称条件离群点l集体离群点：多个对象作为一个整体显著集体离群点：多个对象作为一个整体显著地偏离整个数据集地偏离整个数据集2022-4-142022-4-14数据挖掘数据挖掘45离群点检测的方法离群点检测的方法l统计学方法：假定正常的数据对象由一个统计学方法：假定正常的数据对象由一个统计模型产生，不遵守该模型的数据是离统计模型产生，不遵守该模型的数据是离群点群点l基于邻近性方法：若某