华中科技大学谭毅华-数据挖掘4-分类讲课稿.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Data Mining Yihua Tan IPRAI-HUST,*,p,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Data Mining Yihua Tan IPRAI-HUST,*,p,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,Data Mining Yihua Tan IPRAI-HUST,*,p,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,Data Mining Yihua Tan IPRAI-HUST,*,p,*,数据挖掘：分类,谭 毅 华,Yihua.tan,华中科技大学图像识别与人工智能研究所,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,分类,VS.,预测,分类,:,预测类标号,基于训练集和值（类标号）构造数据分类模型,，并对新的数据进行分类,预测,:,对连续函数建模,i.e.,预测未知或丢失的数据,典型应用,信用证明,客户市场,医学诊断,目标识别,分类：两步骤,模型构造,:,描述预定类别的样本,每个样本属于预定义的类，由类标号属性确定,模型构造的元组称为,训练集,模型表达为分类规则、决策树或数学公式,模型使用,:,用于对未来或未知的对象分类,模型的,估计精度,测试样本的已知标号和模型的分类结果进行对比,准确率为测试样本由模型正确分类的百分比,测试集独立于训练集,否则会产生过拟合现象,若准确率可接受,以该模型对未知类标号的数据元组,分类,分类过程,1:,模型构造,训练数据,分类算法,IF rank=professor,OR years 6,THEN tenured=yes,分类器,(,模型,),分类过程,2:,应用模型,分类器,测试数据,未知数据,(Jeff,Professor,4),Tenured?,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,数据预处理和准备,数据清理,消除或减少数据噪声，处理缺失值。,相关分析,去除不相关或冗余属性,数据变换,规范化或归一化数据,分类和预测方法的评价,精度,分类器精度,:,正确地预测,数据,类标号的能力,预测器精度,:,猜测,数据,的预测属性值,速度,构造模型的时间,(,训练时间,),应用模型的时间,(,分类,/,预测时间,),鲁棒性,:,对存在噪声或缺失值的数据，分类器或预测器正确分类的能力,可伸缩性,:,大容量数据库，分类器或预测器的效率,可解释性,模型提供的理解和领悟能力,其它度量,e.g.,规则的好坏,决策树大小 或分类规则的紧致度,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,决策树归纳分类,算法种类多,Hunts Algorithm(one of the earliest),CART,ID3,C4.5,SLIQ,SPRINT,训练样本：购买计算机的统计表,决策树的构造,age?,31.40,student?,credit rating?,40,fair,excellent,yes,no,no,yes,yes,yes,no,基本决策树算法,基本算法,(,贪婪算法,),自顶向下的分治算法构造树,开始,所有的训练样本和树根相连,属性为分类属性,(,若是连续值，则离散化,),根据选定的属性递归地划分样本,?,如何选择,基于启发式或统计度量选取测试属性,(e.g.,信息增益,),停止划分的准则,所有样本均和属于同一类的节点连接,无剩下的属性用于继续划分样本,叶节点分类应用,多数表决法,无剩余的样本,划分示例,令,Dt,为到达节点,t,，与之相连的所有样本集,一般过程,:,若,Dt,包含的样本属于同一类,yt,则,t,标记为叶节点，其标号为,yt,若,Dt,为空,则,t,是标号为,yd,的叶节点,若,Dt,包含的样本超过一类,以属性测试将样本进一步划分,.,递归地应用此过程划分样本数据。,D,t,?,划分示例,Dont,Cheat,Refund,Dont,Cheat,Dont,Cheat,Yes,No,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,Taxable,Income,Dont,Cheat,=80K,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,类标号,决策树方法的关键问题,贪婪策略下的问题,如何划分数据,怎样指定属性的测试条件,区分为几类,?,怎样确定,”,最佳,”,划分,?,何时停止划分,?,D,t,属性的测试条件,和属性的类型有关,CarType?,Family,Sports,Luxury,A?,A1,A2,A3,A?,ATh,ATh,Income?,Low,Medium,High,Income?,2000,2000,AS?,yes,no,CarType,Family,Sports,yes,no,测试条件,例子,离,散,值,连,续,值,离,散,值,决策树方法的关键问题,贪婪策略下的问题,如何划分数据,怎样指定属性的测试条件,区分为几类,?,怎样确定,”,最佳,”,划分,?,何时停止划分,?,D,t,怎样确定最佳划分,非同质性,不纯度高,同质性,不纯度低,划分前,:,类,0,有,10,个样本,类,1,有,10,样本,类同质分布优先,需度量属性节点的,impurity,哪个测试条件最优？,属性选择度量,属性选择度量划分规则,划分属性：度量得分高的属性,流行的属性选择度量,信息增益,(ID3,，,C4.5),选取时，偏向于多值属性,增益率,(C4.5),偏向不平衡划分,Gini,指标,(IBM IntelligentMiner),偏向于多值属性,类的数量很大时，计算较困难,信息增益,(Information Gain),基于信息论“熵”，选取具有最大信息增益的属性划分,在属性节点,A,处，样本集,D,所具有的熵,(,p(j|D),为类,j,在节点,t,处的概率,).,度量节点的均质性,当所有的类均匀分布时，最大为,(log n,c,),，具有 最多信息,当只有所有样本属于一类时，最小为,(0.0),，具有最少信息,在属性,A,处，将样本分为,v,类的信息量,通过在属性,A,，形成,v,个分支后，信息增益为,增益最大的选为划分属性,信息增益例子,类,P:buys_computer=“yes”,类,N:buys_computer=“no”,指,14,个样本中有,5,个“,age=30”,两个属于类,p,，,2,个属于类,N ,因此,Similarly,决策树首层,age?,40,30.40,增益率,(Gain Ratio),C4.5(ID3,的后继算法,),应用增益率克服信息增益的偏斜性,(,信息增益的规范化,),Ex.,GainRatio(income)=0.029/0.926=0.031,具有最大增益率的属性选为划分属性,Gini,指数,Gini,指数,:,节点属性,A,划分样本的不纯度，设样本集为,D,(NOTE:,p(j|D),类,j,在样本,D,中的概率,).,当所有样本均匀分布在不同类时，最大为,(1-1/nc),表示最小兴趣信息,当所有的样本属于一类时，最小 为,(0.0),，表示最大兴趣信息,基于,Gini,指数的划分,用于,CART,算法,在节点,A,，将训练集,D,划分为,k,个子集,(,子节点,D,i,),，则以划分的不纯度加权和度量其优劣,n,i,=,子树 的训练样本个数,i,n,=,节点,p,处训练样本个数,.,Gini,例子,P(C1)=0/6=0 P(C2)=6/6=1,Gini=1 P(C1),2,P(C2),2,=1 0 1=0,P(C1)=1/6 P(C2)=5/6,Gini=1 (1/6),2,(5/6),2,=0.278,P(C1)=2/6 P(C2)=4/6,Gini=1 (2/6),2,(4/6),2,=0.444,二值属性的,Gini,指数,划分为两个子集,带权划分的效果,:Gini,指数越小越好,寻求更大和更纯的划分,B?,Yes,No,Node N1,Node N2,Gini(D1)=1 (5/7),2,(2/7),2,=0.174,Gini(D2)=1 (1/5),2,(4/5),2,=0.32,Gini(Children)=7/12*0.174+5/12*0.32=0.204,决策树方法的关键问题,贪婪策略下的问题,如何划分数据,怎样指定属性的测试条件,区分为几类,?,怎样确定,”,最佳,”,划分,?,何时停止划分,所有样本属于同一类，则中止,所有的样本具有相同的属性,其它的提前中止法,ID3,算法,ID3(Examples,Class_no,Attributes),创建树的根节点,如果样本属同一类,C,返回该根结点，创建单节点树，并以,C,作为类标号,如果,Attributes,为空，那么返回根节点，其类标号为样本集中的多数类,否则开始,A,Attributes,中分类样本能力最好的属性（最大信息增益）,以,A,作为节点分类属性,对于,A,的每个可能值,vi,在节点下加一个新的分支对应测试,A=vi,令样本,vi,为样本集中中满足,A,属性值为,vi,的子集,如果,Examplevi,为空,在这个新分支下加一个叶子节点，节点的标号为样本中的多数类,否则在新分支下加一个子树,ID3,（,Examplesvi,Class_no,Attributes-A,）,结束,返回,root,决策树方法分类实践时存在的问题,确定决策树增长的深度,处理连续值的属性,处理属性值不完整的训练数据,处理不同代价的属性,提高计算效率,过拟合现象,噪声引起分类面扭曲,数据缺失，使得决策树使用其它分类任务的预测值进行分类,分支太多，由噪声或野值点产生异常,分类未见数据时精度低,剪枝方法处理过拟合,前剪枝,(Early Stopping Rule),在生成完全树之前中止,典型的中止条件,:,所有的样本属于同一类,所有的属性值相同,更严格的条件,:,样本数少于用户指定的数量,样本的类分布独立于已知特征,(e.g.,using,2,test),如果继续划分当前节点并不会改善不纯度,(e.g.,Gini or information gain).,剪枝方法处理过拟合,后剪枝,在生成完全树之后处理,以自底向上的方式修剪节点,如果修建后改善了泛化误差，则以叶节点代替子树,叶节点的类标号以子树中大多数样本的标号代替,可以使用,MDL,实现后剪枝,错误率的估计,重置换错误率,:,训练错误率,(,e(t),泛化错误率,:,测试错误率,(,e(t),泛化错误率估计方法,:,乐观方法,:e(t)=e(t),悲观方法,:,对每个叶节点,:e(t)=(e(t)+0.5),总错误率,:e(T)=,e(T)+N 0.5(N:,节点个数,),对树有,30,叶节点，训练集有,10,个错误,(,共,1000,个样本,):,训练错误率,=10/1000=1%,泛化错误率,=(10+300.5)/1000=2.5%,减少错误率的剪枝,:,使用验证数据集估计泛化错误,后剪枝方法实例,Class=Yes,20,Class=No,10,Error=10/30,训练错误率,(,划分前,)=10/30,悲观错误率,(,划分前,),=(10+0.5)/30=10.5/30,训练错误率,(,划分后,)=9/30,悲观错误率,(,划分后,),=(9+4,0.5)/30=11/30,剪枝,!,Class=Yes,8,Class=No,4,Class=Yes,3,Class=No,4,Class=Yes,4,Class=No,1,Class=Yes,5,Class=No,1,最短描述长度剪枝算法,L(Model,Data)=L(Data|Model)+L(Model),L,为用于编码的比特数,.,搜索具有最短长度比特树的模型,.,L(Data|Model),对错分率编码,.,L(Model),对节点编码,(,分支数,),和划分条件编码,ID3,的扩展,C4.5,简单的深度优先构造树,合并具有连续值的属性,可处理缺失属性值的样本,未知值用常用值代替,使用不同的剪枝技术以避免树的不平衡,基于误分率的树叶节点代替子树,使用增益比选取属性,产生规则,(if-then),K,次迭代交叉验证,可从以下网址下载,:,www.cse.unsw.edu.au/quinlan/c4.5r8.tar.gz,分类树的增强,可使用连续值属性,通过将连续值分为若干离散区间集，动态地定义新的离散属性,处理缺失属性值,赋以最常用的值,给每个值赋以概率,属性构造,基于已有的属性，构造新的属性实现稀疏表达,减少重复（多次测试）和复制（同样的子树）,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,Bayesian Classifier,统计分类器,:,实现,概率预测,i.e.,预测类成员的概率,理论基础,:,Bayes,定理,性能,:,简单的贝页斯分类器,nave Bayesian classifier,和决策树及神经网络性能相当,可增量的,:,在假设正确的前提下，每个训练样本可增加或减少其概率,先验知识和数据混合使用,标准,:,尽管贝页斯方法计算上难以处理，但可提供标准的模型最优选择,贝页斯定理,给定训练样本,X,假设,H,的后验概率,P(H|,X,),服从贝页斯定理,形式上可写为,posteriori=likelihood x prior/evidence,若,P(C,i,|,X,),的概率高于所有的其它,k,类,P(C,k,|X),，则预测,X,属于,C,i,类,实际困难,:,需要知道许多概率的先验知识,这是很大的计算代价,朴素贝页斯分类的预备知识,令,D,为训练元组集及其类标号,每个元组可表示为,n,维向量,X,=(x,1,x,2,x,n,),假定 共有,m,类,C,1,C,2,C,m,.,分类过程是后验概率的求解过程,i.e.,令,P(C,i,|,X,),最大,从贝页斯定理,由于,P(X),为常数,故计算,需令其最大化,贝页斯分类器的推导,简单假设,:,属性条件独立,(i.e.,属性间无依赖关系,):,大大降低了计算量,:,只计算类内的分布,若,A,k,为分类属性,P(x,k,|C,i,),是,D,中属性,A,k,的值为,x,k,类属,C,i,类的元组数除以,D,中,C,i,类的元组数,|C,i,D,|,若,A,k,为连续值,P(x,k,|C,i,),通常假定服从均值为,和标准差为,的高斯分布,而,分类实例：训练样本,Class:,C1:buys_computer=yes,C2:buys_computer=no,Data sample,X=(age=30,Income=medium,Student=yes,Credit_rating=Fair),朴素贝页斯分类过程,计算先验概率,P(C,i,):,P(buys_computer=“yes”)=9/14=0.643,P(buys_computer=“no”)=5/14=0.357,计算条件概率,Compute P(X|C,i,)for each class,P(age=“=30”|buys_computer=“yes”)=2/9=0.222,P(age=“=30”|buys_computer=“no”)=3/5=0.6,P(income=“medium”|buys_computer=“yes”)=4/9=0.444,P(income=“medium”|buys_computer=“no”)=2/5=0.4,P(student=“yes”|buys_computer=“yes)=6/9=0.667,P(student=“yes”|buys_computer=“no”)=1/5=0.2,P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667,P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4,计算后验概率,X=(age=30,income=medium,student=yes,credit_rating=fair),P(X|C,i,):,P(X|buys_computer=“yes”)=0.222 x 0.444 x 0.667 x 0.667=0.044,P(X|buys_computer=“no”)=0.6 x 0.4 x 0.2 x 0.4=0.019,P(X|C,i,)*P(C,i,):,P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028,P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007,Therefore,X belongs to class(“buys_computer=yes”),零概率问题,朴素贝页斯预测需要每个条件概率非零，否则整个预测概率为零,假设数据有,1000,个数据集,income=low(0),income=medium(990),and income=high(10),Laplacian,校准,(or Laplacian,估计器,),每个计数都加上,1,Prob(income=low)=1/1003,Prob(income=medium)=991/1003,Prob(income=high)=11/1003,“,校准”概率估计非常接近,“,未校准”概率估计,朴素贝页斯分类器的评价,优点,容易实现,大多数情况下结果令人满意,缺点,满足假设,:,类条件独立，对实际分布的描述不准确,实际上，不同的属性间是相关联的,E.g.,医院,:,病人,:,档案,:,年龄,家族史,etc.,症状,:,发烧,咳嗽等,.,疾病,:,肺癌,糖尿病,etc.,这些属性间的关联无法由朴素贝页斯分类器建模,如何处理这种相关性,?,Bayesian Belief Networks,Bayesian Belief Networks,贝页斯证据网络允许 属性变量的子集条件独立,因果关系的图模型,表达变量间的依赖性,给出了联合概率的完全表示,Y,Z,P,X,节点,:,随机变量,连接箭头,:,依赖性,X,和,Y,为,Z,的父节点,而,Y,为,P,的父节点,Z,和,P,间无依赖性,是一个无环图,简单的贝页斯证据网络实例,Family,History,LungCancer,PositiveXRay,Smoker,Emphysema,Dyspnea,LC,LC,(FH,S),(FH,S),(FH,S),(FH,S),0.8,0.2,0.5,0.5,0.7,0.3,0.1,0.9,Bayesian Belief Networks,变量,LungCancer,的条件概率表,(,CPT,),CPT,表示每个父节点不同组合的条件概率,数据元组,X,由属性,Y1,Yn,描述,的联合概率表示为,BPN,的训练,几种情况,:,给定网络结构和所有的观测变量,:,学习,CPTs,网络结构已知,存在一些隐变量,:,梯度下降法,和神经网络的学习类似,网络结构未知,所有观测变量已知,:,通过模型空间搜索构造网络拓扑,结构未知,所有都是隐变量,:,没有办法学习？！,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,基于规则的分类,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,基于规则的分类器,使用一系列“,ifthen”,对数据集分类,规则,:(,Condition,),y,此处,Condition,为多个属性值,y,为类标号,LHS(IF,部分,),:,规则前件或前提,RHS(then,部分,),:,规则结论,分类规则例子,:,(,血的类型,=,温血,),(,下蛋,=Yes),鸟,(,税收收入,Bird,规则,R3,覆盖,grizzly bear=Mammal,规则的评价,n,covers,=,规则,R,覆盖的样本数,n,correct,=,规则,R,正确分类的样本数,D:,数据样本集,规则覆盖率,:,Coverage(R)=n,covers,/|D|,规则准确率,:,Accuracy(R)=n,correct,/n,covers,(Status=Single)No,Coverage=40%,Accuracy=50%,规则的冲突,触发：规则被满足,激活：该规则为唯一满足的,R1:(Give Birth=no),(Can Fly=yes)Birds,R2:(Give Birth=no),(Live in Water=yes)Fishes,R3:(Give Birth=yes),(Blood Type=warm)Mammals,R4:(Give Birth=no),(Can Fly=no)Reptiles,R5:(Live in Water,=sometimes)Amphibians,A lemur triggers rule R3,so it is classified as a mammal,A turtle triggers both R4 and R5,A dogfish shark triggers none of the rules,冲突解决,规模序,(size ording):,要求最严格的规则赋予最高优先级,(i.e.,最多属性测试,),基于类的序,:,按照类的频繁性或错分代价的降序排列,基于规则的序,(,决策表,):,根据规则的质量度量或专家意见，规则组织为长的优先级列表,从决策树提取规则,规则易于理解,从根到树的叶节点的每条路径创建一个规则,沿每个划分准则的逻辑,AND,形成规则的前提，存放类预测的叶节点形成规则后件,规则间是互斥或穷举的,Example:,从,buys_computer,决策树提取的规则,IF,age,=young AND,student,=,no,THEN,buys_computer,=,no,IF,age,=young AND,student,=,yes,THEN,buys_computer,=,yes,IF,age,=mid-age THEN,buys_computer,=,yes,IF,age,=old AND,credit_rating,=,excellent,THEN,buys_computer,=,yes,IF,age,=young AND,credit_rating,=,fair,THEN,buys_computer,=,no,age?,student?,credit rating?,40,no,yes,yes,yes,31.40,no,fair,excellent,yes,no,规则归纳：序贯覆盖算法,Sequential covering:,直接从数据抽取规则,典型的序贯覆盖算法,:FOIL,AQ,CN2,RIPPER,序贯地学习规则,对每个给定的类,C,i,希望覆盖该类的许多元组，但不包括其它类的元组,(,或很少,),步骤,:,一次学习一个规则,每次学习规则时,删除规则覆盖到的元组,对剩余的元组重复此过程，直到满足中止条件,.,如无训练样本或规则质量低于用户指定的门限,决策树归纳,:,同时学习一组规则,顺序覆盖算法,while,(,还有足够的元组,),产生一条规则,删除满足规则的元组,规则,3,覆盖的样本,规则覆盖的样本,2,规则,1,覆盖的样本,Positive examples,Learn One Rule,算法,从空规则开始,:,条件,=,空,深度优先贪婪算法增加新的变量,选择提高规则质量最多的变量,规则质量度量,:,覆盖率和准确率,Foil,信息增益,(in FOIL&RIPPER):,扩展前提来估计,info_gain,适合于有较高准确率，并且覆盖很多正元组的规则,基于独立测试集的规则剪枝,Pos/neg,为规则,R,覆盖的正,/,负元组数,若规则,R,剪枝后的,FOIL_Prune,更高,则对,R,剪枝,产生规则,Positive examples,Negative examples,A3,=1,A3,=1&,A1,=2,A3,=1&,A1,=2,&A8,=5,产生规则,while,(true),搜索最优预测,p,若,FOIL_Gain(,p,)threshold,则 将,p,加入当前规则,否则,break,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,基于规则的分类,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,Back Propagation,一种神经网络学习算法：对多层前馈神经网络的学习,人工神经网络,心理学家和神经学家开创，用于测试神经元的计算模拟,神经网络：一组连接的输入,/,输出单元，每个连接和一个权系数关联,学习阶段：调整权系数，使其正确预测输入元组的类标号,又称为连接者学习,Neuro(Perceptron),由多个互连的节点和权系数连接,输出节点为输入节点的加权和,根据输入的门限，定义相应的函数f,最后，n维输入矢量X映射为变量y,Perceptron Model,or,多层前馈神经网络,将类预测作为输入的非线性组合,给定足够多的隐藏单元和训练样本，多层神经网络可逼近任意函数,若权系数不返回到前一层，则称前馈神经网络,定义神经网络拓扑,设计网络拓扑,:,输入层单元数,隐藏层单元数,(,若多于,1,层,),每个隐藏层的单元数,输出层的单元数,将训练元组中每个属性的观测值进行归一化，如：使其落入,0.01.0,每个域值一个输入单元,初始化为,0,输出,若分类时有两类以上,每类一个输出单元,若神经网络经训练后发现准确度不高,以不同的神经网络拓扑或不同的初始权系数集训练,后向传播算法学习,迭代地处理训练元组数据集，比较器网络预测值和已知的目标值,(,类标号或连续预测值,),对每个训练元组,权系数对网络预测值和实际目标值之间的,MSE,最小,后向进行修正,:,从输出层,经每个隐藏层,最后到首层,步骤,初始化权系数,(,赋以很小的随机数,),，每个单元一个偏差度,前向传播输入,(,应用激励函数,),后向传播误差,(,通过更新权系数和偏差度,),中止条件,(,当误差很小时,etc.),后向传播和可解释性,后向传播的效率,:,给定,|D|,个元组和,w,个权系数，每个周期,(,对训练集的一次迭代,),需要化的时间为,O(|D|*,w,),在最坏的情况下，周期数为可能是输入数,n,的指数,从网络抽取规则,:,网络剪枝,删除对训练后的网络影响最小的加权连接以简化网络结构,对连接、单元或活跃值聚类,对输入值和活跃值进行学习，导出描述输入和隐藏单元层的关系,灵敏度分析,:,评估给定的输入变量对网络输出的影响。,.,这种形式的分析得到的知识可用“,IF x,减少,5%THEN Y,增加,8%”,的规则表达,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,基于规则的分类,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,一个简单的例子,哪个分类更优,?B1 or B2?,怎样定义更优,?,SVM,的简介,适用于线性和非线性可分数据的新分类方法,通过非线性映射，将原始训练数据变换到更高维空间,在新的维度下,搜索线性可分的超平面,(i.e.,“,决策边界”,),通过合适的高维映射,来自两类的数据总可被超平面分开,SVM,以支持向量搜索超平面,(“,基本”训练元组,),和边缘,(,由支持向量定义,),SVM,的基本思想,支持向量,小边缘,大边缘,边缘和支持向量,SVM-,线性可分情况,m,令,D,为数据集,(,X,1,y,1,),(,X,|D|,y,|D|,),此处,X,i,为 和类标号,y,i,相关联的训练元组,存在无数条线,(,超平面,),分开两类，但我们期望找出最佳的分类,(,对未见数据具有最小的分类误差,),SVM,搜索最大的边缘,i.e.,maximum marginal hyperplane,(MMH),SVM-,线性可分,SVM-,线性可分,目标是最大化,:,等价于最小化,:,满足以下约束,:,约束的二次优化问题,数值方法求解,(e.g.,二次规划,),训练后的决策边界,SVM-,问题线性不可分,问题是线性不可分，怎么办？,引入松弛变量,最小化,:,约束条件下,:,SVM-,决策面分线性,将原始输入数据变换到高维的空间,例,6-10,在新的空间搜索线性可分平面,SVM-,核函数映射,利用核函数,K(,X,i,X,j,),对原始数据映射，如,K(,X,i,X,j,)=,(,X,i,),(,X,j,),典型的核函数,SVM,可用于多类分类,(2,两类,),和回归分析,(,使用附加的用户参数,),SVM,相关链接,SVM Website,www.kernel-machines.org/,实现的代码,LIBSVM:SVM,的高效实现,多类分类,两类分类等,SVM-light:,简单但性能劣于,LIBSVM,只支持两类分类，,c,语言,SVM-torch:,用,C,语言实现,.,Lazy VS.Eager Learning,Lazy vs.eager learning,Lazy learning(e.g.,基于实例的学习,):,简单地存储样本,(,或小的预处理,),，一直等到给定测试元组,Eager learning(,前面提到的方法,):,给定训练集,在检验元组到来之前，构造泛化的分类模型,Lazy:,训练时间少，但在预测时需花费更多时间,准确率,Lazy learning:,更有效地利用假设空间，因为使用很多的局部函数隐式地逼近全局函数,Eager:,必须归结于单个假设，覆盖整个实例空间,K-,最近邻法,基本思想：类比学习,走路像鸭子，叫声像鸭子，则该动物是鸭子,训练集,测试集,计算距离,选择,k,个最近的记录,K-,最近邻法算法,所有的实例对应,n-,维空间,根据欧式距离定义邻近性,dist(,X,1,X,2,),目标函数可为离散或实值函数,对离散值,k,-NN,返回未知元组,x,q,k,个最近邻训练集中的最普遍的值,Voronoi,图,:,对训练样本的典型集，,1-NN,的决策面,Voronoi Diagram,关于,k-NN,算法,k-NN,是对给定的未知元组，预测其实值,返回,k,最近邻的均值,权距离最近邻算法,根据,k,近邻对未知元组,x,q,的距离贡献，计算预测值,距离近，则权系数大，,w=1/d,2,k,近邻平均后，对噪声鲁棒,维数灾难,:,相邻的距离可能由不相关的属性主导,通过轴拉伸删除最不相关的属性,K-NN,例,Class,Marital Status,Single,Married,Divorced,Yes,2,0,1,No,2,4,1,名词属性的距离,:,d(Single,Married),=|2/4 0/4|+|2/4 4/4|=1,d(Single,Divorced),=|2/4 1/2|+|2/4 1/2|=0,d(Married,Divorced),=|0/4 1/2|+|4/4 1/2|=1,d(Refund=Yes,Refund=No),=|0/3 3/7|+|3/3 4/7|=6/7,Class,Refund,Yes,No,Yes,0,3,No,3,4,K-NN,例续,元组,X,和,Y,的距离,:,其中,:,若,X,大多数情况下预测准确，,w,X,1,若,X,预测不可靠，则,w,X,1,Case-based reasoning,储存案例,使用训练数据预测未见数据的类 标号,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,基于规则的分类,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,Case-based reasoning,CBR:,使用问题解数据库解决新问题,储存,符号描述,(,元组,or,案例,),而不是欧式空间中的点,应用,:,客户,-,服务,(,产品故障诊断,),法律裁决,方法,案例表达为符号描述,(e.g.,函数图,),搜索相似空间,多个搜索到的案例可综合,案例搜索,基于知识的推理和问题求解的紧耦合,挑战,寻找最优相似度,基于句法相似度的索引，当搜索失效时，回溯或自适应地附加案例,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,基于规则的分类,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,Genetic algorithm,遗传算法,:,模拟生物进化,创建由初始规则组成的初始种群,每个规则由一个二进位串表示,E.g.,if A,1,and NOT A,2,then C,2,可编码为,100,若属性有,k,个值,(k 2),则可用,k,比特对该属性编码,基于“适者生存”的原则,形成由当前种群中最适合的规则及其后代组成新的种群,规则的适应度由其对训练样本的分类精度表示,后代通过交叉和变异产生,该过程继续，直到种群进化到每个规则均满足预先指定的适应度,速度较慢，但易于并行,Rough Set Approach,用于“近似的”或“粗糙的”定义等价类,给定类,C,的粗糙集由两个集合逼近,:a lower approximation(,一定属于,C),和,an upper approximation(,不可能认为不属于,C),寻找属性的最小子集,(,特征简化）是,NP,难题，但识别矩阵,(,discernibility matrix,),存放每对数据元组的属性值之间的差别，降低计算强度,模糊集方法,模糊逻辑使用,0.0,和,1.0,间的真值表示成员的隶属度,(,如,模糊隶属度图,),属性值转换为模糊值,e.g.,通过计算模糊值，将收入映射到离散类别,low,medium,high,给定新的样本,可给出多个模糊值,每个可适用的规则为类成员贡献一票,典型地,对每个预测类的真值求和，并组合这些和,内 容,分类和预测的基本概念,关于分类和预测的问题,分类的方法,决策树分类器,Bayesian,分类器,基于规则的分类,后向传播分类器,SVM,分类器,惰性学习法分类,其它分类方法,预测的方法,分类和预测方法的评估,什么是预测,(,数值,),预测和分类类似,构建模型,针对给定的输入，使用模型预测连续或顺序值,预测和分类的不同点,分类指预测分类标号,预测模型使用连续函数,预测的主要方法,:regression,对一个或多个独立变量（或预测变量）和一个因变量,(,或响应变量）之间的关系建模,回归分析,线性回归和多元线性回归,非线性回归,其它的回归方法,:,广义线性模型,Poisson,回归,对数线性模型,回归树,Linear Regression,线性回归,:,