分享
分销 收藏 举报 申诉 / 38

类型数据挖掘概念与技术原书第2版第7章聚类分析析.ppt

  • 上传人:pc****0
  • 文档编号:13920940
  • 上传时间:2026-05-07
  • 格式:PPT
  • 页数:38
  • 大小:1.22MB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    数据 挖掘 概念 技术 原书第 聚类分析
    资源描述:
    ,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,聚类分析,聚类(簇):数据对象的集合,在同一个聚类(簇)中的对象彼此相似,不同簇中的对象则相异,聚类分析,将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程,聚类是一种无指导的学习:没有预定义的类编号,聚类分析的数据挖掘功能,作为一个独立的工具来获得数据分布的情况,作为其他算法(如:特征和分类)的预处理步骤,什么是聚类分析?,模式识别,空间数据分析,在,GIS,系统中,对相似区域进行聚类,产生主题地图,检测空间聚类,并给出它们在空间数据挖掘中的解释,图像处理,商务应用中,帮市场分析人员发现不同的顾客群,万维网,对,WEB,上的文档进行分类,对,WEB,日志的数据进行聚类,以发现相同的用户访问模式,聚类分析的典型应用,一个好的聚类分析方法会产生高质量的聚类,高类内相似度,低类间相似度,作为统计学的一个分支,聚类分析的研究主要是基于距离的聚类;一个高质量的聚类分析结果,将取决于所使用的聚类方法,聚类方法的所使用的相似性度量和方法的实施,方法发现隐藏模式的能力,什么是好的聚类分析?,可扩展性,(Scalability),大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率,处理不同数据类型的能力,数字型;二元类型,分类型,/,标称型,序数型,比例标度型等等,发现任意形状的能力,基于距离的聚类算法往往发现的是球形的聚类,其实现实的聚类是任意形状的,用于决定输入参数的领域知识最小化,对于高维数据,参数很难决定,聚类的质量也很难控制,处理噪声数据的能力,对空缺值、离群点、数据噪声不敏感,数据挖掘对聚类分析的要求,(1),对于输入数据的顺序不敏感,同一个数据集合,以不同的次序提交给同一个算法,应该产生相似的结果,高维性,高维的数据往往比较稀松,而且高度倾斜,基于约束的聚类,找到既满足约束条件,又具有良好聚类特性的数据分组,可解释性和可用性,聚类要和特定的语义解释和应用相联系,数据挖掘对聚类分析的要求,(2),许多基于内存的聚类算法采用以下两种数据结构,数据矩阵:用,p,个变量来表示,n,个对象,也叫二模矩阵,行与列代表不同实体,相异度矩阵:存储,n,个对象两两之间的临近度,也叫单模矩阵,行和列代表相同的实体,聚类分析中的数据类型,许多聚类算法都是以相异度矩阵为基础,如果数据是用数据矩阵形式表示,则往往要将其先转化为相异度矩阵。,相异度,d(i,j),的具体计算会因所使用的数据类型不同而不同,常用的数据类型包括:,区间标度变量,二元变量,标称型、序数型和比例标度型变量,混合类型的变量,相异度计算,区间标度度量是一个粗略线性标度的连续度量,比如重量、高度等,选用的度量单位将直接影响聚类分析的结果,因此需要实现度量值的标准化,将原来的值转化为无单位的值,给定一个变量,f,的度量值,可使用以下方法进行标准化:,计算平均的绝对偏差,其中,计算标准化的度量值,(z-score),使用平均的绝对偏差往往比使用标准差更具有健壮性,区间标度变量,对象间的相似度和相异度,(1),对象间的相似度和相异度是基于两个对象间的距离来计算的,Euclidean,距离,i=(x,i1,x,i2,x,ip,),和,j=(x,j1,x,j2,x,jp,),是两个,p,维数据对象,Manhattan,距离,对象间的相似度和相异度,(2),Manhattan,距离和,Euclidean,距离的性质,d(i,j),0,d(i,i),=0,d(i,j),=,d(j,i),d(i,j),d(i,k),+,d(k,j),Minkowski,距离,上式中,,q,为正整数,如果,q=1,则表示,Manhattan,距离,如果,q=2,则表示,Euclidean,距离,一个二元变量只有两种状态:,0,或,1,;,e.g.smoker,来表示是否吸烟,一个对象可以包含多个二元变量。,二元变量的可能性表:,如何计算两个二元变量之间的相似度?,二元变量,(1),Object,i,Object,j,对称的,VS.,不对称的 二元变量,对称的二元变量指变量的两个状态具有同等价值,相同权重;,e.g.,性别,基于对称的二元变量的相似度称为恒定的相似度,可以使用简单匹配系数评估它们的相异度:,不对称的二元变量中,变量的两个状态的重要性是不同的;,e.g.HIV,阳性,VS HIV,阴性,基于不对称的二元变量的相似度称为非恒定的相似度,可以使用,Jaccard,系数评估它们的相异度,二元变量,(2),二元变量的相异度,示例,P228,例,8.1,二元变量之间的相异度(病人记录表),Name,是对象标识,gender,是对称的二元变量,其余属性都是非对称的二元变量,如过,Y,和,P,(,positive,阳性)为,1,,,N,为,0,,则:,标称变量,标称变量是二元变量的推广,它可以具有多于两个的状态值。比如:红、绿、蓝、黄。对于标称型变量,值之间的排列顺序是不重要的。,计算标称变量所描述的对象(一个对象可以包含多个标称变量),i,和,j,之间的相异度,方法一:简单匹配方法,m:,匹配的数目,即对象,i,和,j,取值相同的变量的数目,(,也可加上权重,),方法二:对,M,个标称状态中的每个状态创建一个新的二元变量,并用非对称的二元变量来编码标称变量,红绿蓝黄取值,0100,绿,0010,蓝,。,序数型变量,一个序数型变量可以是离散的或者是连续的,序数型变量的值之间是有顺序关系的,比如:讲师、副教授、正教授。,假设,f,是描述,n,个对象的一组序数型变量之一,,f,的相异度计算如下:,1.,设第,i,个对象的,f,值为,x,if,,则用它在值中的序,r,if,代替,2.,将每个变量的值域映射到,0,1,的空间,3.,采用区间标度变量的相异度计算方法计算,f,的相异度,一个比例标度型变量,x,if,是在非线性的标度中所取的正的度量值,例如指数标度,近似的遵循以下公式:,Ae,Bt,or,Ae,-Bt,计算比例标度型变量描述的对象之间的相异度,采用与区间标度变量同样的方法,标度可能被扭曲,效果往往不好,对比例标度型变量进行对数变化之后进行与区间标度变量的相似处理,y,if,=,log(x,if,),将,x,if,看作连续的序数型数据,将其秩作为区间标度的值来对待,比例标度变量,在真实的数据库中,数据对象不是被一种类型的度量所描述,而是被多种类型(即混合类型)的度量所描述,包括:,区间标度度量、对称二元变量,不对称二元变量,标称变量,序数型变量合比例标度变量,计算混合型变量描述的对象之间的相异度,将变量按类型分组,对每种类型的变量进行单独的聚类分析,在每种聚类分析导出相似结果的情况下可行,所有变量一起处理,进行一次聚类分析,可以将不同类型的变量组合在单个相异度矩阵中,把所有有意义的变量转换到共同的值域区间,0,1,之内,混合类型的变量,聚类分析算法种类繁多,具体的算法选择取决于数据类型,聚类的应用和目的,常用的聚类算法包括:,划分方法,层次的方法,基于密度的方法,基于网格的方法,基于模型的方法,实际应用中的聚类算法,往往是上述聚类方法中多种方法的整合,主要的聚类方法,给定一个,n,个对象或元组的数据库,一个划分方法构建数据的,k,个划分,每个划分表示一个簇,并且,k=n,。,每个组至少包含一个对象,每个对象属于且仅属于一个组,划分准则:同一个聚类中的对象尽可能的接近或相关,不同聚类中的对象尽可能的原理或不同,簇的表示,k-,平均算法,由簇的平均值来代表整个簇,k,中心点算法,由处于簇的中心区域的某个值代表整个簇,划分方法,对给定数据对象集合进行层次分解,自底向上方法(凝聚):开始将每个对象作为单独的一个组,然后相继的合并相近的对象或组,直到所有的组合并为一个,或者达到一个终止条件。,自顶向下方法(分裂):开始将所有的对象置于一个簇中,在迭代的每一步,一个簇被分裂为多个更小的簇,直到最终每个对象在一个单独的簇中,或达到一个终止条件,缺点:合并或分裂的步骤不能被撤销,层次的方法,基于距离的聚类方法的缺点:只能发现球状的簇,难以发现任意形状的簇。,基于密度的据类:只要临近区域的密度(对象或数据点的数目)超过某个临界值,就继续聚类。,优点:可以过滤掉“噪声”和“离群点”,发现任意形状的簇。,基于密度的方法,把对象空间量化为有限数目的单元,形成一个网格结构。所有的聚类都在这个网格结构上进行。,优点:处理数度快(因为处理时间独立于数据对象数目,只与量化空间中每一维的单元数目有关),基于网格的方法,为每个簇假定一个模型,寻找数据对给定模型的最佳拟合。,一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类,这种方法同时也用于自动的决定数据集中聚类的数目,通过统计学的方法,考虑噪声和离群点,从而产生健壮的聚类方法,基于模型的方法,给定,n,个对象的数据集,以及要生成的簇的数目,k,,划分算法将对象组织为,k,个划分(,k n,)每个划分代表一个簇,通常通过计算对象间距离进行划分,典型的划分方法,k,均值,k,中心点,以上两种方法的变种,划分的方法,簇的相似度是关于簇中对象的均值度量,可以看作簇的质心(,centroid,),k,均值算法流程,随机选择,k,个对象,每个对象代表一个簇的初始均值或中心,对剩余的每个对象,根据它与簇均值的距离,将他指派到最相似的簇,计算每个簇的新均值,回到步骤,2,,循环,直到准则函数收敛,常用准则函数:平方误差准则,基于质心的技术:,k,均值方法,(,p,是空间中的点,,m,i,是簇,C,i,的均值,),P263,图,7-2,k,均值方法,-,示例,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2,随机选择,2,个对象,作为簇的中心,将每个对象指派到最相似的簇,更新每个簇的均值,更新每个簇的均值,重新分派,重新分派,可扩展性较好,算法复杂度为,O(nkt),,其中,n,为对象总数,,k,是簇的个数,,t,是迭代次数。,经常终止于局部最优解,缺点,只有当簇均值有定义的情况下,,k,均值方法才能使用。(某些分类属性的均值可能没有定义),用户必须首先给定簇数目,不适合发现非凸形状的簇,或者大小差别很大的簇,对噪声和离群点数据敏感,k,均值算法的评论,k,均值方法有些变种,他们的区别在于,不同的初始,k,个均值的选择,不同的相异度计算,不同的计算簇均值的策略,聚类分类数据的方法:,k,众数(,mode,)方法,用众数来替代簇的均值,采用新的相异性度量处理分类对象,采用基于频率的方法更新簇的众数,可以集成,k,均值和,k,众数方法,对具有数值和分类值的数据进行聚类,k,均值方法的变种,k,均值方法对于离群点敏感,一个具有很大极端值的对象可能显著的扭曲数据的分布,平方误差函数将进一步严重恶化这种影响,k,中心点方法:采用簇的中心点,即最靠近中心的对象来代表簇,降低算法对离群点的敏感度,基于代表对象的技术:,k,中心点方法,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,k,中心点方法仍然基于最小化所有对象与其对应的参照点之间的相异度之和原则,使用的是绝对误差标准,(p,是空间中的点,代表簇,Cj,中一个给定对象;,oj,是簇,Cj,中的代表对象,),通常该算法重复迭代,直到每个代表对象都成为它的簇的实际中心点,首先随意选择初始代表对象,只要能够提高结果聚类质量,迭代过程就使用非代表对象替换代表对象,聚类结果的质量用代价函数评估,该函数度量对象与其簇的代表对象之间的平均差异度,k,中心点方法步骤,为了确定非代表对象,O,random,是否能够替代当前代表对象,O,j,,对于每一个非代表对象,p,,考虑四种情况,k,中心点方法,-,代表对象替换,(1),+,O,i,+,O,j,p,+,O,random,1.,重新分配给,O,i,+,O,i,+,O,j,p,+,O,random,2.,重新分配给,O,random,+,O,i,+,O,j,p,+,O,random,3.,不发生变化,+,O,i,+,O,j,p,+,O,random,4.,重新分配给,O,random,重新分配将对代价函数产生影响,如果当前的代表对象被非代表对象所取代,代价函数就是计算绝对误差值的差,变换的总代价是所有非代表对象所产生的代价之和,总代价为负,实际的绝对误差,E,将减少,,O,j,可以被,O,random,所取代,总代价为正,则本次迭代没有变化,k,中心点方法,-,代表对象替换,(2),当存在噪声和离群点时,,k,中心点方法比,k,均值方法更加鲁棒,中心点较少的受离群点影响,k,中心点方法的执行代价比,k,均值方法要高,k,均值方法:,O(nkt),k,中心点方法:,O(k(n-k),2,),n,与,k,较大时,,k,中心点方法的执行代价很高,两种方法都要用户指定簇的数目,k,k,均值方法与,k,中心点方法比较,什么是离群点?,一个数据集与其他数据有着显著区别的数据对象的集合,例如:运动员:,Michael Jordon,舒马赫,布勃卡,离群点产生原因,度量或执行错误(年龄:,-999,),数据变异的结果,离群点挖掘,给定一个,n,个数据对象的集合,以及预期的离群点数目,k,,发现与剩余的数据有着显著差异的头,k,个数据对象,应用,欺诈检测、医疗中的异常分析等,离群点分析,统计的方法对于给定的数据集合假定了一个分布或概率模型(例如正态分布),使用依赖于以下参数的不一致性检验(,discordancy tests,),数据分布,分布参数(,e.g.,均值或方差),预期的离群点数,缺点,绝大多数检验是针对单个属性的,而数据挖掘要求在多维空间中发现离群点,大部分情况下,数据分布可能是未知的,基于统计的离群点检测,为了解决统计学方法带来的一些限制,引入了基于距离的离群点检测,在不知道数据分布的情况下对数据进行多维分析,基于距离的离群点:即,DB(p,d),,如果数据集合,S,中的对象至少有,p,部分与对象,o,的距离大于,d,,则对象,o,就是,DB(p,d),。,挖掘基于距离的离群点的高效算法:,基于索引的算法,嵌套循环算法,基于单元的算法,基于距离的离群点检测,通过检查一组对象的主要特征来确立离群点,跟主要特征的描述相“偏离”的对象被认为是离群点,两种基于偏离的离群点探测技术,序列异常技术,模仿人类从一系列推测类似的对象中识别异常对象的方式,OLAP,数据立方体技术,在大规模的多维数据中采用数据立方体来确定异常区域。如果一个立方体的单元值显著的不同于根据统计模型得到的期望值,则改单元值被认为是一个异常,并用可视化技术表示。,基于偏离的离群点检测,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:数据挖掘概念与技术原书第2版第7章聚类分析析.ppt
    链接地址:https://www.zixin.com.cn/doc/13920940.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork