ch8 聚类数据挖掘技术.ppt
《ch8 聚类数据挖掘技术.ppt》由会员分享,可在线阅读,更多相关《ch8 聚类数据挖掘技术.ppt(66页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第八章第八章 聚类数据挖掘技术聚类数据挖掘技术,一、聚类一、聚类:l按照数据之间的按照数据之间的相似性相似性,对数据集进行分组或分类,对数据集进行分组或分类(簇(簇,cluster)的过程,试图使类内差距最小化,的过程,试图使类内差距最小化,类间差距最大化。类间差距最大化。l利用聚类结果,可以提取数据集中隐藏的信息,对利用聚类结果,可以提取数据集中隐藏的信息,对未来数据进行未来数据进行预测和分类预测和分类。应用于数据挖掘、模式。应用于数据挖掘、模式识别、图像处理、经济学识别、图像处理、经济学“物以类聚,人以群分物以类聚,人以群分”l聚类分析源于许多研究领域,包括数据挖掘、聚类分析源于许多研究领
2、域,包括数据挖掘、统计学、机器学习、模式识别等。作为一个数统计学、机器学习、模式识别等。作为一个数据挖掘中的一个功能,聚类分析能作为一个独据挖掘中的一个功能,聚类分析能作为一个独立的工具来获得数据分布的情况,并且概括出立的工具来获得数据分布的情况,并且概括出每个簇的特点,或者集中注意力对特定的某些每个簇的特点,或者集中注意力对特定的某些簇做进一步的分析。簇做进一步的分析。l数据挖掘技术的一个突出的特点是处理巨大数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集,这对聚类分析技术提出了的、复杂的数据集,这对聚类分析技术提出了特殊的挑战,要求算法具有可伸缩性、处理不特殊的挑战,要求算法具有可伸
3、缩性、处理不同类型属性的能力、发现任意形状的类、处理同类型属性的能力、发现任意形状的类、处理高维数据的能力等。根据潜在的各项应用,数高维数据的能力等。根据潜在的各项应用,数据挖掘对聚类分析方法提出了不同要求。据挖掘对聚类分析方法提出了不同要求。二、聚类在数据挖掘中的典型应用:二、聚类在数据挖掘中的典型应用:n聚类分析可以作为其它算法的预处理步骤聚类分析可以作为其它算法的预处理步骤:利用聚类进:利用聚类进行数据预处理,可以获得数据的基本概况,在此基础上行数据预处理,可以获得数据的基本概况,在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也进行特征抽取或分类就可以提高精确度和挖掘效率。也可
4、将聚类结果用于进一步关联分析,以获得进一步的有可将聚类结果用于进一步关联分析,以获得进一步的有用信息。用信息。n可以作为一个独立的工具来获得数据的分布情况可以作为一个独立的工具来获得数据的分布情况:聚类:聚类分析是获得数据分布情况的有效方法。通过观察聚类得分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点,可以集中对特定的某些簇作进一步到的每个簇的特点,可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩估评、分析。这在诸如市场细分、目标顾客定位、业绩估评、生物种群划分等方面具有广阔的应用前景。生物种群划分等方面具有广阔的应用前景。n聚类分析可以完成孤立点挖掘
5、聚类分析可以完成孤立点挖掘:许多数据挖掘算法试图:许多数据挖掘算法试图使孤立点影响最小化,或者排除它们。然而孤立点本身使孤立点影响最小化,或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中,孤立点可能预示可能是非常有用的。如在欺诈探测中,孤立点可能预示着欺诈行为的存在。着欺诈行为的存在。广泛的应用领域广泛的应用领域l商务:商务:帮助市场分析人员从客户信息库中发现不同的帮助市场分析人员从客户信息库中发现不同的客户群客户群,用购买模式来刻画不同的客户群的特征用购买模式来刻画不同的客户群的特征l土地使用:土地使用:在地球观测数据库中识别土地使用情况相在地球观测数据库中识别土地使用情况相似的
6、地区似的地区l保险业:保险业:汽车保险单持有者的分组汽车保险单持有者的分组l城市规划:城市规划:根据根据房子的类型,价值和地理分布对房子房子的类型,价值和地理分布对房子分组分组l生物学:生物学:推导植物和动物的分类,对基因进行分类推导植物和动物的分类,对基因进行分类n聚类分析的目标就是形成的数据簇,并且满足聚类分析的目标就是形成的数据簇,并且满足下面两个条件:下面两个条件:n一个簇内的数据尽量相似(一个簇内的数据尽量相似(high high intra-classintra-class similaritysimilarity););n不同簇的数据尽量不相似(不同簇的数据尽量不相似(low l
7、ow inter-classinter-class similaritysimilarity)。)。n衡量一个聚类分析算法质量,依靠:衡量一个聚类分析算法质量,依靠:n相似度测量机制是否合适。相似度测量机制是否合适。n是否能发现数据背后潜在的、手工难以发现的类知识。是否能发现数据背后潜在的、手工难以发现的类知识。三、聚类分析的目标三、聚类分析的目标:四、聚类分析方法的分类四、聚类分析方法的分类:n按照聚类的标准,聚类方法可分为如下两种:按照聚类的标准,聚类方法可分为如下两种:n统计聚类方法:这种聚类方法主要基于对象之间的几统计聚类方法:这种聚类方法主要基于对象之间的几何距离的。何距离的。n概念
8、聚类方法:概念聚类方法基于对象具有的概念进概念聚类方法:概念聚类方法基于对象具有的概念进行聚类。行聚类。n按照聚类算法所处理的数据类型,聚类方法可分为三种:按照聚类算法所处理的数据类型,聚类方法可分为三种:n数值型数据聚类方法:所分析的数据的属性只限于数数值型数据聚类方法:所分析的数据的属性只限于数值数据。值数据。n离散型数据聚类方法:所分析的数据的属性只限于离离散型数据聚类方法:所分析的数据的属性只限于离散型数据。散型数据。n混合型数据聚类方法:能同时处理数值和离散数据。混合型数据聚类方法:能同时处理数值和离散数据。n按照聚类的尺度,聚类方法可被分为以下三种:按照聚类的尺度,聚类方法可被分为
9、以下三种:n基于距离的聚类算法:用各式各样的距离来衡量数据基于距离的聚类算法:用各式各样的距离来衡量数据对象之间的相似度,如对象之间的相似度,如k k-means-means、k k-medoids-medoids、BIRCHBIRCH、CURECURE等算法。等算法。n基于密度的聚类算法:相对于基于距离的聚类算法,基于密度的聚类算法:相对于基于距离的聚类算法,基于密度的聚类方法主要是依据合适的密度函数等。基于密度的聚类方法主要是依据合适的密度函数等。n基于互连性基于互连性(Linkage-Based)(Linkage-Based)的聚类算法:通常基于的聚类算法:通常基于图或超图模型。高度连通
10、的数据聚为一类。图或超图模型。高度连通的数据聚为一类。n按照聚类聚类分析算法的主要思路,可以被归纳为如下按照聚类聚类分析算法的主要思路,可以被归纳为如下几种。几种。n划分法(划分法(Partitioning MethodsPartitioning Methods):):基于一定标准构基于一定标准构建数据的划分。属于该类的聚类方法有:建数据的划分。属于该类的聚类方法有:k-meansk-means、k-k-modesmodes、k-prototypesk-prototypes、k-medoidsk-medoids、PAMPAM、CLARACLARA、CLARANSCLARANS等。等。n层次法(
11、层次法(Hierarchical MethodsHierarchical Methods):):对给定数据对象对给定数据对象集合进行层次的分解。集合进行层次的分解。n密度法(密度法(density-based Methodsdensity-based Methods):):基于数据对象基于数据对象的相连密度评价。的相连密度评价。n网格法(网格法(Grid-based MethodsGrid-based Methods):):将数据空间划分成将数据空间划分成为有限个单元(为有限个单元(CellCell)的网格结构,基于网格结构进的网格结构,基于网格结构进行聚类。行聚类。n模型法(模型法(Mode
12、l-Based MethodsModel-Based Methods):):给每一个簇假定给每一个簇假定一个模型,然后去寻找能够很好的满足这个模型的数一个模型,然后去寻找能够很好的满足这个模型的数据集。据集。五、五、数据相似性的度量数据相似性的度量-距离距离l距离越大,相似性越小。距离越大,相似性越小。l点间距离点间距离与与类间距离类间距离 类间距离基于点间距离计算类间距离基于点间距离计算l距离函数应同时满足距离函数应同时满足 1.d(i,j)0 2.d(i,i)=0 3.d(i,j)=d(j,i)4.d(i,j)d(i,k)+d(k,j)常用点间距离常用点间距离常用点间距离常用点间距离相异度
13、相异度相异度相异度l欧式距离欧式距离l城区距离城区距离l切比雪夫距离切比雪夫距离l明科夫斯基距离明科夫斯基距离数据矢量数据矢量x=(x1,x2,xn),y=(y1,y2,yn).常用类间距离常用类间距离常用类间距离常用类间距离l最短距离法最短距离法l最长距离法最长距离法l类平均法类平均法l重心法重心法两个聚类两个聚类p和和q.六、聚类方法六、聚类方法l划分方法划分方法:构造数据的最优划分:构造数据的最优划分l层次方法层次方法:对数据进行层次分解或合并:对数据进行层次分解或合并l基于密度的方法基于密度的方法:(:(1)基于密度连通性,如)基于密度连通性,如DBSCAN,OPTICS;(;(2)基
14、于密度分布函数,基于密度分布函数,如如DENCLUEl基于网格的方法基于网格的方法:采用多分辨率网格数据结构,:采用多分辨率网格数据结构,如如STING,BANG,CLIQUE,MAFIAl基于模型的方法基于模型的方法:SOM神经网络神经网络(1)(1)划分方法划分方法n给定一个有n个对象的数据集,划分聚类技术将构造数据k个划分,每一个划分就代表一个簇,k n。也就是说,它将数据划分为k个簇,而且这k个划分满足下列条件:n每一个簇至少包含一个对象。n每一个对象属于且仅属于一个簇。n对于给定的k,算法首先给出一个初始的划分方法,以后通过反复迭代的方法改变划分,使得每一次改进之后的划分方案都较前一
15、次更好。l启发式方法启发式方法:k-平均算法和平均算法和k-中心点算法中心点算法k-均值算法均值算法:每个簇用该簇中对象的平均值每个簇用该簇中对象的平均值来表示。来表示。k-中心点算法中心点算法:每个簇用接近聚类中心的一每个簇用接近聚类中心的一个对象来表示个对象来表示nk k-means-means算法,也被称为算法,也被称为k k-平均或平均或k k-均值,是一种均值,是一种得到最广泛使用的聚类算法。相似度的计算根据一得到最广泛使用的聚类算法。相似度的计算根据一个簇中对象的平均值来进行。个簇中对象的平均值来进行。首先将所有对象随机分配到首先将所有对象随机分配到k个非空的簇中。个非空的簇中。计
16、算每个簇的平均值,并用该平均值代表相应的簇。计算每个簇的平均值,并用该平均值代表相应的簇。根据每个对象与各个簇中心的距离,分配给最近的簇。根据每个对象与各个簇中心的距离,分配给最近的簇。然后转第二步,重新计算每个簇的平均值。这个过程然后转第二步,重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。不断重复直到满足某个准则函数才停止。K-K-均值算法均值算法K-均值聚类示例均值聚类示例From“Data Mining:Concepts and Techniques”,J.Han and M.Kamber算法算法 k-means算法算法输入:簇的数目输入:簇的数目k和包含和包含n个
17、对象的数据库。个对象的数据库。输出:输出:k个簇,使平方误差准则最小。个簇,使平方误差准则最小。(1)assign initial value for means;/*任意选择任意选择k个对象作为初始的簇中心个对象作为初始的簇中心*/(2)REPEAT(3)FOR j=1 to n DO assign each xj to the closest clusters;(4)FOR i=1 to k DO /*更新簇平均值更新簇平均值*/(5)Compute /*计算准则函数计算准则函数E*/(6)UNTIL E不再明显地发生变化。不再明显地发生变化。n算法首先随机地选择算法首先随机地选择k k个
18、对象,每个对象初始地代表了个对象,每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离,将它赋给最近的簇。然后重新计算每个簇簇中心的距离,将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。的平均值。这个过程不断重复,直到准则函数收敛。n准则函数试图使生成的结果簇尽可能地紧凑和独立。准则函数试图使生成的结果簇尽可能地紧凑和独立。样本数据样本数据序号序号 属性属性 1 属性属性 21 1 12 2 13 1 24 2 25 4 36 5 37 4 48 5 4迭代次数迭代次数 平均值平均
19、值平均值平均值 产生的新簇产生的新簇 新平均值新平均值 新平均值新平均值 (簇(簇1)(簇(簇2)(簇(簇1)(簇(簇2)1 (1,1)(1,2)1,2,3,4,5,6,7,8 (1.5,1)(3.5,3)2 (1.5,1)(3.5,3)1,2,3,4,5,6,7,8 (1.5,1.5)(4.5,3.5)3 (1.5,1.5)(4.5,3.5)1,2,3,4,5,6,7,8 (1.5,1.5)(4.5,3.5)根据所给的数据通过对其实施根据所给的数据通过对其实施k-means(设设n=8,k=2),其主其主要执行执行步骤:要执行执行步骤:第一次迭代:假定随机选择的两个对象,如序号第一次迭代:假
20、定随机选择的两个对象,如序号1和序号和序号3当当作初始点,分别找到离两点最近的对象,并产生两个簇作初始点,分别找到离两点最近的对象,并产生两个簇1,2和和3,4,5,6,7,8。对于产生的簇分别计算平均值,得到平均值点。对于产生的簇分别计算平均值,得到平均值点。对于对于1,2,平均值点为(,平均值点为(1.5,1)(这里的平均值是)(这里的平均值是简单的相加除简单的相加除2););对于对于3,4,5,6,7,8,平均值点为(,平均值点为(3.5,3)。)。第二次迭代:通过平均值调整对象的所在的簇,重新聚类,第二次迭代:通过平均值调整对象的所在的簇,重新聚类,即将所有点按离平均值点(即将所有点按
21、离平均值点(1.5,1)、()、(3.5,3)最近的原)最近的原则重新分配。得到两个新的簇:则重新分配。得到两个新的簇:1,2,3,4和和5,6,7,8。重新计算簇平均值点,得到新的平均值点为(。重新计算簇平均值点,得到新的平均值点为(1.5,1.5)和(和(4.5,3.5)。)。第三次迭代:将所有点按离平均值点(第三次迭代:将所有点按离平均值点(1.5,1.5)和()和(4.5,3.5)最近的原则重新分配,调整对象,簇仍然为)最近的原则重新分配,调整对象,簇仍然为1,2,3,4和和5,6,7,8,发现没有出现重新分配,而且准则函数,发现没有出现重新分配,而且准则函数收敛,程序结束。收敛,程序
22、结束。实例实例k k-means-means算法的性能分析算法的性能分析n主要优点:主要优点:n是解决聚类问题的一种经典算法,简单、快速。是解决聚类问题的一种经典算法,简单、快速。n对处理大数据集,该算法是相对可伸缩和高效率的。对处理大数据集,该算法是相对可伸缩和高效率的。n当结果簇是密集的,它的效果较好。当结果簇是密集的,它的效果较好。n主要缺点主要缺点n在簇的平均值被定义的情况下才能使用,可能不适用于在簇的平均值被定义的情况下才能使用,可能不适用于某些应用。某些应用。n必须事先给出必须事先给出k k(要生成的簇的数目),而且对初值敏要生成的簇的数目),而且对初值敏感,对于不同的初始值,可能
23、会导致不同结果。感,对于不同的初始值,可能会导致不同结果。n不适合于发现非凸面形状的簇或者大小差别很大的簇。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且,它对于而且,它对于“躁声躁声”和孤立点数据是敏感的。和孤立点数据是敏感的。k k-means-means算法的几种改进方法算法的几种改进方法nk k-mode-mode 算法:实现对离散数据的快速聚类,保留算法:实现对离散数据的快速聚类,保留了了k k-means-means算法的效率同时将算法的效率同时将k k-means-means的应用范围扩的应用范围扩大到离散数据。大到离散数据。nk k-prototype-prototype
24、算法:可以对离散与数值属性两种混算法:可以对离散与数值属性两种混合的数据进行聚类,在合的数据进行聚类,在k k-prototype-prototype中定义了一个中定义了一个对数值与离散属性都计算的相异性度量标准。对数值与离散属性都计算的相异性度量标准。nk k-中心点算法中心点算法k k-means-means算法对于孤立点是敏感的。算法对于孤立点是敏感的。为了解决这个问题,不采用簇中的平均值作为参照为了解决这个问题,不采用簇中的平均值作为参照点,可以选用簇中位置最中心的对象,即中心点作点,可以选用簇中位置最中心的对象,即中心点作为参照点。这样划分方法仍然是基于最小化所有对为参照点。这样划分
25、方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。象与其参照点之间的相异度之和的原则来执行的。k-k-中心点算法(中心点算法(k-medoidsk-medoids)l也称也称PAM算法(算法(Partitioning Around Medoids)基于有代表性的数据(基于有代表性的数据(中心点中心点),而不是均值代),而不是均值代表每个簇。表每个簇。l思路思路 1.1.为每个簇随机选择一个代表对象为每个簇随机选择一个代表对象(中心点中心点);2.2.剩余的对象根据其与代表对象的距离分配给剩余的对象根据其与代表对象的距离分配给与其最近的一个簇;与其最近的一个簇;3.3.反复地
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ch8 聚类数据挖掘技术 数据 挖掘 技术
限制150内