数据挖掘常用算法概述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,关联分析,关联规则挖掘的提出,关联规则挖掘的典型案例：购物篮问题,在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将所购买的商品放入到自己的购物篮中。,通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯,哪些物品经常被顾客购买？,同一次购买中，哪些商品经常会被一起购买？,一般用户的购买过程中是否存在一定的购买时间序列？,具体应用：利润最大化,商品货架设计：更加适合客户的购物路径,货存安排 ：实现超市的零库存管理,用户分类 ：提供个性化的服务,其他典型应用,相关文献的收集,购物篮,=,文档（,Document,）,项 目,=,单词（,Word,）,相关网站的收集,购物篮,=,词句,（,Sentences,）,项 目,=,链接文档,（,Document,）,什么是关联规则挖掘,?,关联规则挖掘,简单的说，关联规则挖掘发现大量数据中项集之间有趣的关联,在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。,应用,购物篮分析、交叉销售、产品目录设计、,loss-leader analysis,、聚集、分类等。,关联规则挖掘形式化定义,给定,:,交易数据库,每笔交易是：一个项目列表,(,消费者一次购买活动中购买的商品,),查找,:,所有描述一个项目集合与其他项目集合相关性的规则,应用,*,护理用品,(,商店应该怎样提高护理用品的销售？,),家用电器,*(,其他商品的库存有什么影响,?),在产品直销中使用附加邮寄,其它相关概念,包含,k,个项目的集合，称为,k-,项集,项集的出现频率是包含项集的事务个数，称为项集的频率、支持计数或者计数,关联规则的基本形式：前提条件,结论,支持度,置信度,buys(x,“diapers”),buys(x,“beers”)0.5%,60%,major(x,“CS”)takes(x,“DB”),grade(x,“A”)1%,75%,关联规则兴趣度的度量值：支持度,推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描述采用支持度、置信度概念。,支持度（,Support,）：规则,X,Y,在交易数据库,D,中的支持度是交易集中包含,X,和,Y,的交易数与所有交易数之比，记为,support(X,Y),，即,support(X,Y)=|T:X,Y,T,，,T,D|/|D|,，它是概率,P,（,X,Y,），具体,表示为,：,S,=,总交易数,同时包含项目集,X,和,Y,的交易数,购买商品,Y,的交易,同时购买商品,X,和,Y,的交易,购买商品,X,的交易,关联规则兴趣度的度量值：置信度,置信度（,Confidence,），规则,X,Y,在交易集中的置信度是指包含,X,和,Y,的交易数与包含,X,的交易数之比，记为,confidence(X,Y),，即,confidence(X,Y)=|T:X,Y,T,，,T,D|/|T:X,T,，,T,D|,，它是概率,P,（,X|Y,），具体,表示为,：,最小支持度和最小置信度,用户（分析员）不关心可信程度太低的规则，因而用户需要输入两个参数：最小支持度和最小置信度。,C,=,购买商品,X,的交易数,同时购买商品,X,和,Y,的交易数,购买商品,Y,的交易,同时购买商品,X,和,Y,的交易,购买商品,X,的交易,支持度和置信度举例,零售商场销售分析：,数据项为商品，记录集合为交易记录集合,规则为：“购买商品,X,的顾客，同时购买商品,Y”,，即,X,Y,；,设最小支持度为,0.3,；最小置信度也为,0.3,。,分析结果：,频繁项集及其基本特征,频繁项集的定义,如果项集满足最小支持度，则称之为频繁项集（高频项集）,频繁项集的基本特征,任何频繁项集的子集均为频繁项集。例如：,ABC,是频繁项集，则,AB,、,AC,、,BC,均为频繁项集,在数据库表分区的情况下，一个项集是频繁的，则至少在一个分区内是频繁的,关联规则挖掘的种类,布尔,vs.,数值型关联,(,基于 处理数据的类型,),性别“女”,职业“秘书”,1%,75%,布尔型关联规则,性别“女”,收入,=2000,1%,75%,数值型关联规则,单维,vs.,多维 关联,age(x,“30.39”)income(x,“42.48K”),buys(x,“PC”)1%,75%,buys(x,“Book”)buys(x,“Pen”),buys(x,“Ink”)1%,75%,单层,vs.,多层 分析,那个品种牌子的啤酒与那个牌子的尿布有关系,?,各种扩展,相关性、因果分析,关联并不一定意味着相关或因果,最大模式和闭合相集,添加约束,如,哪些“小东西”的销售促发了“大家伙”的买卖？,关联规则挖掘的基本过程,找出所有的频繁项集,F,，,其中对于任何的,Z,F,，,在交易集合,D,中至少,s%,的事务包含,Z,根据置信度和频繁项集,F,产生关联规则。具体方法如下：,conf(X Y)=supp(X)/supp(X Y),如果,conf(X Y)c,成立，则产生,X Y,的规则,因为,:,supp(X Y)=supp(X Y)s,且,conf(X Y)c,因此关联规则的挖掘可以转换为频繁项集的挖掘和频繁项集之间的关联。,关联规则挖掘：一个例子,对于,A,C,：,support=support(A,、,C)=50%,confidence=support(A,、,C)/support(A)=66.6%,最小值尺度,50%,最小可信度,50%,关联规则挖掘的优缺点,优点,它可以产生清晰有用的结果,它支持间接数据挖掘,可以处理变长的数据,它的计算的消耗量是可以预见的,缺点,当问题变大时，计算量增长得厉害,难以决定正确的数据,容易忽略稀有的数据,查找频繁项集,Apriori,算法,查找具有最小支持度的频繁项集是关联规则挖掘最为重要的步骤,Apriori,算法是目前最有影响力的一个算法，在,1994,年，由,R.Agrawal,S.Srikant,提出,该算法基于频繁项集的特征：如果项集,l=i,1,i,2,i,n,是频繁的，当且仅当项集的所有子集均为频繁项集,.,也就是说，如果,supp(l)s,，当且仅当,supp(l)s,l l,因此，我们可以采用层次顺序的方法来实现频繁项集的挖掘。首先，挖掘一阶频繁项集,L,1,。在此基础上，形成二阶候选项集，挖掘二阶频繁项集。依此类推。,Apriori,算法,连接,:,用,L,k-1,自连接得到,C,k,剪枝,:,一个,k-,项集，如果它的一个,k-1,项集（它的子集）不是频繁的，那他本身也不可能是频繁的。,伪代码,:,C,k,:,长度为,k,的候选项集,L,k,:,长度为,k,的频繁项集,L,1,=frequent items;,for(k=1;L,k,!=,;k+)do,begin,C,k+1,=,从,L,k,生成候选项集,;,对于数据库中的任一交易,t do,如果,t,中包含,C,k+1,中所包含的项集，则计数加,1,L,k+1,=C,k+1,中超过最小支持度的频繁项集,end,return,k Lk,;,Apriori,算法,例子,数据库,D,扫描,D,C,1,L,1,L,2,C,2,C,2,扫描,D,C,3,L,3,扫描,D,Apriori,够快了吗,?,性能瓶颈,Apriori,算法的核心,:,用频繁的,(k 1)-,项集生成候选的频繁,k-,项集,用数据库扫描和模式匹配计算候选集的支持度,Apriori,的瓶颈,:,候选集生成,巨大的候选集,:,10,4,个频繁,1-,项集要生成,10,7,个候选,2-,项集，并且累计和检查它们的频繁性,要找长度为,100,的频繁模式，如,a1,a2,a100,你必须先产生,2,100,10,30,个候选集,重复扫描数据库：,如果最长的模式是,n,的话，则需要,(n+1),次数据库扫描,关联规则结果显示,(Table Form),关联规则可视化,Using Rule Graph,扩展知识：多层关联规则,项通常具有层次,底层的项通常支持度也低,某些特定层的规则可能更有意义,交易数据库可以按照维或层编码,可以进行共享的多维挖掘,食品,面包,牛奶,脱脂奶,光明,统一,酸奶,白,黄,扩展知识：多维关联规则,单维关联规则（维内关联规则）,关联规则中仅包含单个谓词（维）,通常针对的是事务数据库,buys(X,“milk”),buys(X,“bread”),多维关联规则：规则内包含,2,个以上维,/,谓词,维间关联规则,(,不重复谓词,),age(X,”19-25”),occupation(X,“student”),buys(X,“coke”),混合维关联规则,(,存在重复,谓词,),age(X,”19-25”),buys(X,“popcorn”),buys(X,“coke”),分类与预测,本章内容,分类与预测的基本概念,决策树分类,实例：移动通信客户流失分析系统,神经网络,其他分类方法,预测（回归）,建立模型过程,历史数据,模型,建模,记录集合,预测,数学公式,规则集合,分类,为一个事件或对象进行归类,预测分类标签（离散值）,基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类,分类模型：分类器（分类函数、分类规则等）,预测,:,对连续或者有序的值进行建模和预测（回归方法）,典型应用,客户,/,用户分类,信用评分,目标营销,医疗诊断,分类和预测,分类的相关概念,训练集（,Training Set,）：由一组数据库记录或者元组构成，每个记录由有关字段值组成特征向量，这些字段称为属性。,用于分类的属性称为标签属性。标签属性也就是训练集的类别标记。,标签属性的类型必须是离散的，而且标签属性的可能值的数目越少越好。,分类的两个步骤,模型创建,:,对一个已经事先确定的类别创建模型,每个元组属于一个事先确定的类别，使用分类标签属性予以确定,用于创建模型的数据集叫,:,训练集。单个元组称为训练样本,模型可以用分类规则，决策树，或者数学方程的形式来表达。,模型使用,:,用创建的模型预测未来或者类别未知的记录,估计模型的准确率,使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较,准确率：,测试集和训练集是独立的。,分类过程：模型创建（学习过程）,训练集,分类算法,IF rank=professor,OR years 6,THEN tenured=yes,模型,分类过程,:,使用模型,模型,测试集,未知数据,(Jeff,Professor,4),Tenured?,本章内容,分类与预测的基本概念,决策树分类,实例：移动通信客户流失分析系统,神经网络,其他分类方法,预测,（回归）,使用决策树进行分类,决策树,一个树型的结构,内部节点上选用一个属性进行分裂 （决策节点）,每个分叉都是分裂的一个部分,叶子节点表示一个分布,节点的子节点个数跟算法相关,age?,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,决策树分类的特点,优点,容易生成可以理解的规则,计算量相对来说不大,可以处理离散和连续字段,可以清晰显示哪些字段比较重要,缺点,对连续性的字段难以预测,类别太多的时候，错误的可能性会加大,一般情况下，标签属性的个数有限,决策树的生成与使用,决策树生成算法分成两个步骤,树的生成,开始，数据都在根节点,递归的进行数据分割,树的修剪,去掉一些可能是噪音或者异常的数据,决策树使用,:,对未知数据进行分割,按照决策树上采用的分割属性逐层往下，直到一个叶子节点,训练集,ID3,算法,决策树结果：“,buys_computer”,age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,决策树算法,基本算法（贪心算法）,自上而下分而治之的方法,开始时，所有的数据都在根节点,属性都是种类字段,(,如果是连续的，将其离散化,),所有记录用所选属性递归的进行分割,属性的选择是基于一个启发式规则或者一个统计的度量,(,如,information gain),停止分割的条件,一个节点上的数据都是属于同一个类别,没有属性可以再用于对数据进行分割,几种经典算法介绍,CART,min(P(c1),P(c2),2P(c1)P(c2),P(c1)logP(c1)+P(c2)logP(c2)C4.5(ID3),C4.5(ID3),对种类字段处理时，缺省是对每个值作为一个分割,Gain,和,Gain Ratio,CHAID,在,Overfitting,前停止树的生成,必须都是分类属性,选择分割。,X2,检验,从树中生成分类规则,用,IF-THEN,这种形式来表现规则,每个叶子节点都创建一条规则,每个分割都成为一个规则中的一个条件,叶子节点中的类别就是,Then,的内容,规则对于人来说更容易理解,例子,IF age=“=30”AND student=“no”THEN buys_computer=“no”,IF age=“40”AND credit_rating=“excellent”THEN buys_computer=“yes”,IF age=“=30”AND credit_rating=“fair”THEN buys_computer=“no”,本章内容,分类与预测的基本概念,决策树分类,实例：移动通信客户流失分析系统,神经网络,其他分类方法,预测（回归）,应用背景与问题定义,背景,在移动通信领域，客户流失成为通信运营企业关注的焦点,通信业务产生的海量、珍贵数据为数据挖掘的研究提供了坚实的基础,把数据挖掘理论应用于移动通信领域的客户流失分析，进而为通信企业的实际业务提供指导是一项具有挑战性的工作,定义,客户流失分析，就是利用数据挖掘等分析方法，对已流失客户过去一段时间的通话、缴费等信息进行分析，提炼出流失客户的行为特征，利用这些特征预测在网客户的流失倾向,按真实比例抽取，可能掩盖流失用户的特征,解决方法：“样本放大”,数据预处理,抽样,分割,抽样,原始数据,（流失概率,3.2%,）,抽样,采样后,（流失概率,25%,）,合并,10,000,310,000,300,000,50%,20:1,5,000,15,000,20,000,流失,非流失,数据预处理,时间相关属性,属性序列,S,1,用户标识,性别,年龄,入网品牌,1,月份通话时长,2,月份通话时长,6,月份通话时长,1,月份话费,6,月份话费,是否流失,属性序列,S,n,“,静态”属性,流失标志,解决方法：,生成汇总属性（求和、取均值等）,生成,“,趋势属性,”,，如由属性序列,S,1,生成属性,“,通话时长趋势,”,问题：,决策树算法缺乏处理时间相关属性的能力，致使效率下降,数据预处理,生成趋势属性,把每个月通话时长,Y,视为月份,X,（取值从,1,到,6,）的线性函数，即,Y=+X,，系数,作为属性,“,通话时长趋势,”,的取值，从而把求趋势属性的问题转化为简单的线形回归问题，,数据预处理,生成趋势属性（续）,实际应用中，发现各个月份的数值对趋势属性的影响不同，可以对各个月份指定不同的权重,w,作为新生成的趋势属性，可以进一步转换成离散值，如，显著上升、小幅上升、持平、小幅下降、显著下降,例如：,1,到,6,月份权重分别取,1,、,1,、,1,、,2,、,3,、,4,决策树示例,通话次数,=20,品牌,话费金额,神州行,全球通,流失,=25,流失,非,流失,非,流失,用户,ID,通话次数,品牌,话费金额,流失标志,139*884,23,全球通,23,品牌,非,流失,神州行,全球通,第一步：建立决策树,第二步：预测,流失,20,80 0.2,通话次数,=20,品牌,消费金额,神州行,10,30 0.25,10,50 0.167,全球通,2,23 0.08,8,7 0.53,=25,4,36 0.1,品牌,6,14 0.3,神州行,全球通,1,8 0.11,5,6 0.45,C,x,y k%,x,:,流失用户数,y,:,未流失用户数,k:,流失概率,k=x/(x+y),A,决策树算法,数据结构,主要内容,分类与预测的基本概念,决策树分类,实例：移动通信客户流失分析系统,神经网络,其他分类方法,预测,（回归）,神经网络技术,生物神经系统的计算模拟,(,实际上是一个很好的学习系统的例子,),海量并行计算技术使得性能大大提高,最早的神经网络算法为,1959,由,Rosenblatt,提出,基本结构,神经元结构,k,-,f,加权和,输入,向量,X,输出,y,激活函数,权重,向量,w,w,0,w,1,w,n,x,0,x,1,x,n,多层感知系统,Output nodes,Input nodes,Hidden nodes,Output vector,Input vector:,x,i,w,ij,计算实例,一个训练样本,X=1,0,1,输出为,1,X1=1,x2=0,x3=1,w14=0.2,w15=-0.3,w24=0.4,w25=0.1,w34=-.5,w35=0.2,w46=-0.3,w56=-0.2,偏置值,:,节点,4:-0.4,节点,5:0.2,节点,6:0.1,学习率设为,0.9,节点,4:,输入值,:w14*x1+w24*x2+w34*x3+,节点,4,的偏置,=1*0.2+0.4*0-0.5*1-0.4=-0.7,输出值,:,可得,0.332,同理,:,节点,5,输入值,0.1,输出值,0.525,节点,6:,输入值,:w46*o4+w56*o5+,节点,6,的偏置,=-0.3*0.332-0.2*0.525+0.1=-0.105,输出值,:0.474,计算实例,误差计算,节点,6:,0.474*(1-0.474)*(1-0.474)=0.1311,节点,5:,0.525*(1-0.525)*0.1311*(-0.2)=-0.0065,同理节点,4,误差为,:-0.0087,更新权值和偏置值,W46:,-0.3+(0.9)(0.1311)(0.332)=-0.261,其他,Wij,同理,节点,6,的偏置,:,0.1+(0.9)*(0.1311)=0.218,其他偏置同理,终止条件,对所有样本作一次扫描称为一个周期,终止条件,:,对前一周期所有,Wij,的修改值都小于某个指定的阈值,;,或超过预先指定的周期数,.,防止训练过度,前馈神经网络,前馈网络的表达能力,布尔函数。任何布尔函数可以被具有两层单元的网络准确表示，尽管对于最坏的情况，所需隐藏单元的数量随着网络输入数量的增加指数级增长。,连续函数。任何有界的连续函数可以由一个两层的网络以任意小的误差逼近。这个理论适用于隐藏层使用,sigmoid,单元、输出层使用（非阈值的）线性单元的网络。所需的隐藏单元数量依赖于要逼近的函数。,任意函数。任意函数可以被一个有三层单元的网络以任意精度逼近。与前面相同，输出层使用线性单元，两个隐藏层使用,sigmoid,单元，每一层所需的单元数量一般不确定。,神经网络特点,优点,有很强的非线性拟合能力，可映射任意复杂的非线性关系。,学习规则简单，便于计算机实现。,具有很强的鲁棒性、记忆能力以及强大的自学习能力。,缺点,最严重的问题是没能力来解释自己的推理过程和推理依据。,不能向用户提出必要的询问，而且当数据不充分的时候，神经网络就无法进行工作。,把一切问题的特征都变为数字，把一切推理都变为数值计算，其结果势必是丢失信息。,理论和学习算法还有待于进一步完善和提高。,应用,适合神经网络学习的问题,实例是用很多“属性,-,值”对表示的。,目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量。,训练数据可能包含错误。,可容忍长时间的训练。,可能需要快速求出目标函数值。,人类能否理解学到的目标函数是不重要的。,实验,使用,Clementine,进行神经网络分类挖掘,（工具使用参见补充教材）,主要内容,分类与预测的基本概念,决策树分类,实例：移动通信客户流失分析系统,神经网络,其他分类方法,预测,（回归）,其它分类方法,贝叶斯（,Bayesian,）分类,k-,临近分类,基于案例的推理,遗传算法,粗糙集理论,模糊集方法,分类的准确性：评估错误率,数据分区,:,训练,-,测试数据,将一个数据集合分成两个独立的数据集。例如：训练数据,(2/3),测试数据,(1/3),通常应用于大量数据样本的数据集,交叉验证,将一个数据集合分成若干个子样本集,用,k-1,个子样本作为训练数据，,1,个子样本作为测试数据,每一个数据集合具有合适的宽度,分类的准确性：混淆矩阵,混淆矩阵（,confusion matrix,）用来作为分类规则特征的表示，它包括了每一类的样本个数，包括正确的和错误的分类。,主对角线给出了每一类正确分类的样本的个数，非对角线上的元素则表示未被正确分类的样本个数,实际的类,预,测,的,类,A,类,B,类,C,类,总计,A,类,45,2,3,50,B,类,10,38,2,50,C,类,4,6,40,50,总计,59,46,45,150,3,个类的混淆矩阵,分类的准确性：收益图,查全率分析图：,X,轴：按离网倾向评分从大到小排序后的客户占目标客户人数的百分比；,Y,轴：前,x%,的客户中被准确预测为离网的客户占目标客户中离网总人数的百分比，即查全率。,Lift,分析图：,X,轴：按离网倾向评分从大到小排序后的客户占目标客户人数的百分比；,Y,轴：命中率的提升倍数。,聚类分析,聚类分析,什么是聚类分析,?,划分方法（,Partitioning Methods,）,分层方法,基于密度的方法,异常分析,什么是聚类分析,?,簇（,Cluster,）,:,一个数据对象的集合,在同一个簇中，对象之间具有尽可能大的相似性；,不同簇的对象之间具有尽可能大的相异性。,聚类分析,把一个给定的数据对象集合分成不同的簇，即“物以类聚”；,聚类是一种无监督分类法,:,没有预先指定的类别标识；,典型的应用,作为一个独立的分析工具，用于了解数据的分布；,作为其它算法的一个数据预处理步骤；,应用聚类分析的例子,市场销售,:,帮助市场人员发现客户数据库中不同群体，然后利用这些知识来开展一个目标明确的市场计划；,土地使用,:,在一个陆地观察数据库中标识那些土地使用相似的地区；,保险,:,对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；,城市规划,:,根据类型、价格、地理位置等来划分不同类型的住宅；,地震研究,:,根据地质断层的特点把已观察到的地震中心分成不同的类；,如何评价一个好的聚类方法,?,一个好的聚类方法要能产生高质量的聚类结果,簇，这些簇具备以下两个特征：,簇内极大相似性,簇间极小相似性,聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；,聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；,聚类分析中的数据类型,如何度量对象间的距离？,欧几里德距离,曼哈顿距离,明考斯基距离,聚类分析,什么是聚类分析,?,划分方法（,Partitioning Methods,）,分层方法,基于密度的方法,异常分析,划分方法,:,基本概念,划分方法,:,将一个包含,n,个数据对象的数据库组织成,k,个划分（,k=n,），其中每个划分代表一个簇（,Cluster,）。,给定一个,k,，要构造出,k,个簇，并满足采用的划分准则：,全局最优,:,尽可能的列举所有的划分；,启发式方法,:,k-,均值和,k-,中心点算法,k-,均值,(MacQueen67):,由簇的中心来代表簇；,k-,中心点或,PAM(Partition around medoids,)(Kaufman&Rousseeuw87):,每个簇由簇中的某个数据对象来代表。,K-,均值算法,给定,k,，算法的处理流程如下,:,1.,随机的把所有对象分配到,k,个非空的簇中；,2.,计算每个簇的平均值，并用该平均值代表相应的簇；,3.,将每个对象根据其与各个簇中心的距离，重新分配到与它最近的簇中；,4.,回到第二步，直到不再有新的分配发生。,K-,均值算法图示,K-,均值算法例子,Given:2,4,10,12,3,20,30,11,25,k=2,随机指派均值,:m,1,=3,m,2,=4,K,1,=2,3,K,2,=4,10,12,20,30,11,25,m,1,=2.5,m,2,=16,K,1,=2,3,4,K,2,=10,12,20,30,11,25,m,1,=3,m,2,=18,K,1,=2,3,4,10,K,2,=12,20,30,11,25,m,1,=4.75,m,2,=19.6,K,1,=2,3,4,10,11,12,K,2,=20,30,25,m,1,=7,m,2,=25,K-,均值算法,优点,相对高效的,:,算法复杂度,O,(,tkn,),其中,n,是数据对象的个数,k,是簇的个数,t,是迭代的次数，通常,k,t,n,.,算法通常终止于局部最优解；,缺点,只有当平均值有意义的情况下才能使用，对于标称字段不适用；,必须事先给定要生成的簇的个数；,对“噪声”和异常数据敏感；,不能发现非凸面形状的数据。,聚类分析,什么是聚类分析,?,划分方法（,Partitioning Methods,）,分层方法,基于密度的方法,基于网格的方法,异常分析,层次方法,采用距离作为衡量聚类的标准。该方法不需要指定聚类的个数，但用户可以指定希望得到的簇的数目作为一个结束条件。,Step 0,Step 1,Step 2,Step 3,Step 4,b,d,c,e,a,a b,d e,c d e,a b c d e,Step 4,Step 3,Step 2,Step 1,Step 0,聚集,(AGNES),分裂,(DIANA),层次聚类方法讨论,层次方法的主要缺点：,没有良好的伸缩性,:,时间复杂度至少是,O,(,n,2,),一旦一个合并或分裂被执行，就不能修复；,综合层次聚类和其它的聚类技术：,BIRCH(1996),:,使用,CF-tree,动态调整子聚类的质量。,CURE(1998,):,从聚类中选择分布“好”的数据点，并以指定的比例向聚类中心收缩。,CHAMELEON(1999),:,利用动态建模技术进行层次聚类。,聚类分析,什么是聚类分析,?,划分方法（,Partitioning Methods,）,分层方法,基于密度的方法,异常分析,定义,两个参数：,：邻域的最大半径,MinPts,：数据对象,-,邻域内最少的数据个数,给定对象集合,D,邻域,N,(p),:,对象,p,的半径为,内的区域，即,q,D|dist(p,q,)B,的“提升”,提升：一种兴趣度的度量,correlation,lift,P(A),和,P(B),同时考虑,P(A,B)=P(B)*P(A),A,和,B,是独立时间,取值小于,1,，,A and B,负相关,取值大于,1,，,A and B,正相关,（,2/8,）,/,（,4/8*2/8,）,=2,2/8=0.25,