数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第7章
54页1、1,第七章 聚类分析,2,第七章 目录,7.1 概述 7.2 K均值算法 7.3 BIRCH算法 7.4 DBSCAN算法 7.5 STING算法 7.6 EM算法 7.7 本章小结,3,7.1 概述,7.1.1 聚类概念 7.1.2 相似性测度 7.1.3 聚类过程 7.1.4 聚类算法分类,4,7.1.1聚类概念(1),聚类是将物理或抽象对象的集合分成相似的对象类的过程。使得同一个簇中的对象之间具有较高的相似性,而不同簇中的对象具有较高的相异性。 聚类可形式描述为: =o1, o2, , on表示一个对象集合, oi表示第i个对象,i=1, 2,n; Cx表示第x个簇,Cx,x=1,2,k; Similarity(oi, oj)表示对象oi与对象oj之间的相似度;,5,1) 2)对于 , 有 3),7.1.1聚类概念(2),若各簇Cx是刚性聚类结果,则各Cx需满足如下条件:,6,7.1.2 相似性测度,1)距离相似性度量。距离越近越相似。 2)密度相似性度量。密度越相近,相似性越高。 3)连通性相似性度量。 4)概念相似性度量。共性(比如共享最近邻)越多越相似。,7,7.1.3 聚
2、类过程,典型聚类过程:,聚类分析的三要素是相似性测度、聚类准则和聚类算法。,8,7.1.4 聚类方法分类(1),1)划分式聚类算法(partitioning method):预先指定聚类数目或聚类中心,通过反复迭代运算,逐步优化准则函数的值,当准则函数收敛时,得到最终聚类结果。 例:k均值算法、k中心点算法及它们的变种。 2)层次聚类算法(hierarchical method):将数据对象组织成一棵聚类树,使用数据的联接规则,透过一种架构方式,反复将数据进行分裂或聚合,以形成一个层次序列的聚类问题解。 例:BIRCH、ROCK和Chameleon 等。,9,3)基于密度的聚类算法(density-based method):通过数据密度来发现簇,将簇看作是数据空间中被低密度区域(代表噪声)分割开的稠密对象区域。 例:DBSCAN、OPTICS、DENCLUE。 4)基于网格的聚类算法(gridbased method):使用一种多分辨率的网格数据结构,将对象空间量化为有限数目的单元,形成网格结构,所有的聚类操作都在网格上进行,从而获得较快的处理速度。 例:STING、WaveClus
3、ter。,7.1.4 聚类方法分类(2),10,5)基于模型的聚类算法(model-based method):基于“数据根据潜在的混合概率分布生成”假设,为每个簇假定一个模型,并寻找数据对给定模型的最佳拟合。这类算法通过构建反映数据点空间分布的密度函数来定位簇,能考虑“噪声”数据和离群点的影响,鲁棒性较好。 例:EM 、COBWEB 、SOM。,7.1.4 聚类方法分类(3),11,7.2 K均值算法,7.2.1 误差平方和准则 7.2.2 K均值算法,12,7.2.1误差平方和准则,若Nx是第Cx个簇中的对象数目,mx是这些对象的均值,即 误差平方和准则J 就是所有簇的簇中各个对象与均值间的误差平方和之和,即: J 度量了用k个聚类中心m1,m2,mk代表k个簇C1,C2,Ck时所产生的总的误差平方和。对于不同的聚类,J的值不同,使J 值极小的聚类是误差平方和准则下的最优结果。,13,7.2.2 K均值算法(1),核心思想是:首先选定k个初始聚类中心,根据最小距离原则将每个数据对象分配到某一簇中,然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况,直至收敛(J 值不再变化
4、)。 当存在噪声和离群数据时,k中心点算法比k均值算法效果好,但是k中心点聚类算法的执行代价比k均值算法高。 k均值算法描述如下: 算法:k均值聚类算法(D,k) 输入:数据对象集合D,簇数目k 输出:k个簇的集合,14,步骤: (1) 从D中随机选取k个不同的数据对象作为k个簇C1,C2,Ck的中心m1,m2,mk (2) repeat (2.1)for D中每个数据对象o (2.1.1) 寻找i, (2.1.2)将o分配给簇Ci (2.2)for 每个簇计算 计算,7.2.2 K均值算法(2),15,/计算新的聚类中心, 为当前簇 中的对象数目 3)计算平方误差 3. Until J 不再发生变化,7.2.2 K均值算法(3),16,7.3 BIRCH算法,7.3.1 聚类特征 7.3.2 CF树 7.3.3 CF树的构造 7.3.4 BIRCH算法,17,7.3.1 聚类特征(Clustering Feature,CF),聚类特征是一个三元组,概括了对象簇的信息。如果某个簇包含N个d维的数据点oi,则CF=(N,LS,SS),其中N是簇中点的数目,LS是N个点的线性和(即 ),S
《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第7章》由会员E****分享,可在线阅读,更多相关《数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第7章》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页