数据挖掘导论__第5章_分类_其他技术

数据挖掘导论,Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等译人民邮电出版社,第5章分类:其他技术,基于规则的分类最近邻分类贝叶斯分类神经网络支持向量机组合方法不平衡类问题多类问题,5.1基于规则的分类器,基于规则的分类器,使用一组“ifthen”规则进行分类规则:(Condition)y其中Condition是属性测试的合取y是类标号左部:规则的前件或前提右部:规则的结论分类规则的例子:(BloodType=Warm)(LayEggs=Yes)Birds(TaxableIncome鸟类规则r3覆盖“灰熊”=哺乳类,2020/5/28,6,数据挖掘：概念与技术,规则的质量,用覆盖率和准确率度量规则的覆盖率（coverage）:满足规则前件的记录所占的比例规则的准确率（accuracy）:在满足规则前件的记录中，满足规则后件的记录所占的比例规则:(Status=Single)NoCoverage=40%,Accuracy=50%,Tid,Refund,Marital,Status,Taxable,Income,Class,1,Yes,Single,125K,No,2,No,Married,100K,No,3,No,Single,8,No,Single,85K,Yes,9,No,Married,75K,No,10,No,Singl,e,90K,Yes,10,2020/5/28,7,数据挖掘：概念与技术,如何用规则分类,一组规则r1：（胎生=否）（飞行动物=是）鸟类r2：（胎生=否）（水生动物=是）鱼类r3：（胎生=是）（体温=恒温）哺乳类r4：（胎生=否）（飞行动物=否）爬行类r5：（水生动物=半）两栖类待分类记录狐猴触发规则r3,它分到哺乳类海龟触发规则r4和r5-冲突狗鲨未触发任何规则,2020/5/28,8,数据挖掘：概念与技术,规则的分类器的特征,互斥规则集每个记录最多被一个规则覆盖如果规则都是相互独立的，分类器包含互斥规则如果规则集不是互斥的一个记录可能被多个规则触发如何处理?有序规则集基于规则的序vs基于类的序无序规则集使用投票策略,2020/5/28,9,数据挖掘：概念与技术,规则的分类器的特征(续),穷举规则集每个记录至少被一个规则覆盖如果规则集涵盖了属性值的所有可能组合，则规则集具有穷举覆盖如果规则集不是穷举的一个记录可能不被任何规则触发如何处理?使用缺省类,2020/5/28,10,数据挖掘：概念与技术,有序规则集,根据规则优先权将规则排序定秩（rank）有序规则集又成决策表（decisionlist）对记录进行分类时由被触发的，具有最高秩的规则确定记录的类标号如果没有规则被触发，则指派到缺省类,2020/5/28,11,数据挖掘：概念与技术,规则定序方案,基于规则的序根据规则的质量排序基于类的序属于同一类的规则放在一起基于类信息（如类的分布、重要性）对每类规则排序,2020/5/28,12,数据挖掘：概念与技术,如何建立基于规则的分类器,直接方法:直接由数据提取规则例如:RIPPER,CN2,Holtes1R间接方法:由其他分类模型提取规则(例如，从决策树、神经网络等).例如:C4.5rules,2020/5/28,13,数据挖掘：概念与技术,直接方法:顺序覆盖,基本思想依次对每个类建立一个或多个规则对第i类建立规则第i类记录为正例，其余为负例建立一个第i类的规则r，尽可能地覆盖正例，而不覆盖负例删除r覆盖的所有记录，在剩余数据集上学习下一个规则，直到所有第i类记录都被删除,2020/5/28,14,数据挖掘：概念与技术,直接方法:顺序覆盖,顺序覆盖（sequentialcovering）算法1：令E是训练记录，A是属性值对的集合(Aj,vj)2：令Yo是类的有序集y1,y2,.,yk3：令R=是初始规则列表4：for每个类yYoykdo5：while终止条件不满足do6：rLearn-One-Rule(E,A,y)7：从E中删除被r覆盖的训练记录8：追加r到规则列表尾部：RRr9：endwhile10：endfor11：把默认规则yk插入到规则列表R尾部,2020/5/28,15,数据挖掘：概念与技术,顺序覆盖:例,(a)Originaldata,(b)Step1,(c)Step2,(c)Step3,2020/5/28,16,数据挖掘：概念与技术,删除实例,为什么要删除实例?否则,下一个规则将与前面的规则相同为什么删除正实例?确保下一个规则不同为什么删除负实例?防止低估规则的准确率比较图中的规则R2和R3,2020/5/28,17,数据挖掘：概念与技术,Learn-One-Rule,规则增长实例删除规则评估停止准则规则剪枝,2020/5/28,18,数据挖掘：概念与技术,规则增长,两种策略一般到特殊从初始规则r:y开始反复加入合取项，得到更特殊的规则，直到不能再加入特殊到一般随机地选择一个正例作为初始规则反复删除合取项，得到更一般的规则，直到不能再删除问题加入/删除合取项有多种选择，如何选择？何时停止加入/删除合取项？需要评估标准,2020/5/28,19,数据挖掘：概念与技术,规则增长:例,一般到特殊,特殊到一般,2020/5/28,20,数据挖掘：概念与技术,规则评估,常用的度量准确率似然比LaplaceM-estimateFOIL信息增益,2020/5/28,21,数据挖掘：概念与技术,规则评估(续),准确率Accuracyn:被规则覆盖的实例数nc:被规则正确分类的实例数问题：准确率高的规则可能覆盖率太低似然比（越高越好）k是类的个数fi是被规则覆盖的类i的样本的观测频度ei是规则作随机猜测的期望频度,2020/5/28,22,数据挖掘：概念与技术,规则评估:例,例:60个正例和100个反例规则r1：覆盖50个正例和5个反例（acc=90.9%）规则r2：覆盖2个正例和0个反例（acc=100%）使用准确率,r2好使用似然比r1:正类的期望频度为e+=5560/160=20.625负类的期望频度为e=55100/160=34.375r2:正类的期望频度为e+=260/160=0.75负类的期望频度为e=2100/160=1.25R(r1)=250log2(50/20.625)+5log2(5/34.375)=99.9R(r2)=22log2(2/0.75)+0log2(0/1.25)=5.66r1比r2好,2020/5/28,23,数据挖掘：概念与技术,规则评估(续),考虑规则覆盖率的评估度量n是规则覆盖的样例数，f+是规则覆盖的正例数，k是类的总数，p+是正类的先验概率当规则的覆盖率很高时，两个度量都渐近地趋向于规则的准确率f+/n继续前例r1的Laplace度量为51/57=89.47%，很接近它的准确率r2的Laplace度量（75%）比它的准确率小很多,2020/5/28,24,数据挖掘：概念与技术,规则评估(续),考虑规则的支持度计数的评估度量规则的支持度计数对应于它所覆盖的正例数FOIL信息增益（FirstOrderInductiveLeanerinformationgain）设规则r:A+覆盖p0个正例和n0个反例;规则r:AB+覆盖p1个正例和n1个反例.扩展后规则的FOIL信息增益定义为该度量与p1和p1/(p1+n1)成正比，所以它更倾向于选择那些高支持度计数和高准确率的规则继续前例r1和r2的FOIL信息增益分别为43.12和2，因此规则r1比r2好,2020/5/28,25,数据挖掘：概念与技术,停止条件与规则剪枝,停止条件计算增益如果增益不显著,则丢弃新规则规则剪枝类似于决策树后剪枝降低错误剪枝:删除规则中的合取项比较剪枝前后的错误率如果降低了错误率,则剪掉该合取项,2020/5/28,26,数据挖掘：概念与技术,直接方法:RIPPER,对于2类问题,选定一个类为正类，另一个为负类从正类学习规则负类时缺省类多类问题按类的大小（属于特定类的实例所占的比例）对诸类排序从最小的类开始学习规则，其余类都看做负类对次小类学习规则，如此下去,2020/5/28,27,数据挖掘：概念与技术,直接方法:RIPPER(续),规则增长:由空规则开始只要能够提高FOIL信息增益就增加一个合取项当规则不再覆盖负实例时就停止剪枝剪枝度量:v=(pn)/(p+n)p:验证集中被规则覆盖的正实例数n:验证集中被规则覆盖的负实例数剪枝方法:如果剪掉合取项可以提高v就剪,2020/5/28,28,数据挖掘：概念与技术,直接方法:RIPPER(续),建立规则集:使用顺序覆盖算找出覆盖当前正实例的最佳规则删除被规则覆盖的所有正实例和负实例当一个规则加入规则集时，计算新的描述长度当新的描述长度比已经得到的描述长度多d位时，就停止增加新规则,2020/5/28,29,数据挖掘：概念与技术,直接方法:RIPPER(续),优化规则集:对规则集R中的每个规则r考虑2个替换的规则:替换规则(r*):重新增长新规则编辑的规则(r):把一个新的合取项增加到规则r比较替换前后的规则集选择最小化MDL的规则集对剩下的正实例，重复规则产生和优化,2020/5/28,30,数据挖掘：概念与技术,规则提取的间接方法,决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则路径中的测试条件构成规则前件的合取项，叶结点的类标号赋给规则后件,2020/5/28,31,数据挖掘：概念与技术,间接方法:C4.5rules(续),从未剪枝的决策树提取规则规则产生对每个规则r:Ay,考虑替换规则r:Ay其中A由删除A的一个合取项得到比较r与所有r的悲观误差如果r的悲观误差小，则剪枝重复该过程，直到不能改进,2020/5/28,32,数据挖掘：概念与技术,间接方法:C4.5rules,规则定序不是对规则定序，而是对规则的子集定序(classordering)每个规则子集是一组具有相同规则后件(class)的规则计算每个子集的描述长度描述长度=L(error)+gL(model)g是参数，考虑规则集中冗余属性(缺省值g=0.5),2020/5/28,33,数据挖掘：概念与技术,2020/5/28,数据挖掘：概念与技术,34,C4.5vsC4.5rulesvsRIPPER,基于规则的分类器的特征,表达能力与决策树一样高容易解释容易产生能够快速对新实例分类性能可与决策树相媲美,2020/5/28,35,数据挖掘：概念与技术,5.2最近邻分类器,急切学习vs惰性学习,急切学习（EagerLearner）两步过程:(1)归纳(2)演绎惰性学习（lazylearner）把训练数据建模过程推迟到需要对样本分类时例子Rote-learner（死记硬背）记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类最近邻（Nearestneighbor）使用“最近”的k个点(最近邻)进行分类,2020/5/28,37,数据挖掘：概念与技术,最近邻分类器,基本思想:Ifitwalkslikeaduck,quackslikeaduck,thenitsprobablyaduck,2020/5/28,38,数据挖掘：概念与技术,最近邻分类器,要求存放训练记录计算记录间距离的度量k值,最近邻数对未知记录分类:计算域各训练记录的距离找出k个最近邻使用最近邻的类标号决定未知记录的类标号(例如,多数表决),2020/5/28,39,数据挖掘：概念与技术,2020/5/28,数据挖掘：概念与技术,40,最近邻定义,记录x的k-最近邻是与x之间距离最小的k个训练数据点,2020/5/28,数据挖掘：概念与技术,41,1nearest-neighbor,VoronoiDiagram,k-最近邻分类算法,k-最近邻分类算法1：令k是最近邻数目，D是训练样例的集合2：for每个测试样例z=(x,y)do3：计算z和每个样例(x,y)D之间的距离d(x,x)4：选择离z最近的k个训练样例的集合DzD5：6：endfor距离加权表决,2020/5/28,42,数据挖掘：概念与技术,k-最近邻,k值的选择:如果k太小,则对噪声点敏感如果k太大,邻域可能包含很多其他类的点定标问题（规范化）属性可能需要规范化，防止距离度量被具有很大值域的属性所左右,2020/5/28,43,数据挖掘：概念与技术,k-NN的特点,k-NN的特点是一种基于实例的学习需要一个邻近性度量来确定实例间的相似性或距离不需要建立模型，但分类一个测试样例开销很大需要计算域所有训练实例之间的距离基于局部信息进行预测，对噪声非常敏感最近邻分类器可以生成任意形状的决策边界决策树和基于规则的分类器通常是直线决策边界需要适当的邻近性度量和数据预处理防止邻近性度量被某个属性左右,2020/5/28,44,数据挖掘：概念与技术,5.3贝叶斯分类器,贝叶斯定理,每个记录用一个d维特征向量X=(x1,x2,xd)表示假定有k个类y1,y2,yk.给定X,X属于yj类的后验概率P(yj|X)满足贝叶斯(Bayes)定理MAP(maximumposteriorihypothesis,最大后验假设)将X指派到具有最大后验概率P(yj|X)的类yj，即将X指派到P(X|yj)P(yj)最大的类yj,2020/5/28,46,数据挖掘：概念与技术,朴素贝叶斯分类,朴素贝叶斯分类(NaveBayesClassifier)工作原理给定一个未知的数据样本X,分类法将预测X属于具有最高后验概率的类.即,未知的样本分配给类yj,当且仅当根据贝叶斯定理,我们有由于P(X)对于所有类为常数,只需要最大化P(X|yj)P(yj)即可.,2020/5/28,47,数据挖掘：概念与技术,朴素贝叶斯分类(续),估计P(yj)类yj的先验概率可以用下式估计P(yj)=nj/n其中,nj是类yj中的训练样本数,而n是训练样本总数估计P(X|yj)为便于估计P(X|yj),假定类条件独立-给定样本的类标号,假定属性值条件地相互独立.于是,P(X|Y=yj)可以用下式估计其中,P(xi|yj)可以由训练样本估值,2020/5/28,48,数据挖掘：概念与技术,朴素贝叶斯分类(续),估计P(xi|yj)设第i个属性Ai是分类属性,则P(xi|yj)=nij/nj其中nij是在属性Ai上具有值xi的yj类的训练样本数,而nj是yj类的训练样本数设第i个属性Ai是连续值属性把Ai离散化假定Ai服从高斯分布其中,ij,ij分别为给定yj类的训练样本在属性Ai上的均值和标准差,2020/5/28,49,数据挖掘：概念与技术,朴素贝叶斯分类,朴素贝叶斯分类器所需要的信息计算每个类的先验概率P(yj)P(yj)=nj/n其中,nj是yi类的训练样本数,而n是训练样本总数对于离散属性Ai，设的不同值为ai1,ai2,ail，对于每个类yj，计算后验概率P(aik|yj),1klP(aik|yj)=nikj/nj其中nikj是在属性Ai上具有值aik的yj类的训练样本数,而nj是yj类的训练样本数对于连续属性Ai和每个类yj，计算yj类样本的均值ij,标准差ij,2020/5/28,50,数据挖掘：概念与技术,贝叶斯分类器:例,例:,P(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻状况=单身|No)=2/7P(婚姻状况=离婚|No)=1/7P(婚姻状况=已婚|No)=4/7P(婚姻状况=单身|Yes)=2/3P(婚姻状况=离婚|Yes)=1/3P(婚姻状况=已婚|Yes)=0年收入：类=No：样本均值=110样本方差=2975类=Yes：样本均值=90样本方差=25,2020/5/28,51,数据挖掘：概念与技术,贝叶斯分类器:例(续),X=（有房=否，婚姻状况=已婚，年收入=$120K）计算P(X|No)和P(X|Yes)P(X|No)=P(有房=否|No)P(婚姻状况=已婚|No)P(年收入=$120K|No)=4/74/70.0072=0.0024P(X|Yes)=P(有房=否|Yes)P(婚姻状况=已婚|Yes)P(年收入=$120K|Yes)=101.2109=0计算P(X|No)P(No)和P(X|Yes)P(Yes)P(X|No)P(No)=0.00240.7=0.00168P(X|Yes)P(Yes)=00.3=0因为P(X|No)P(No)P(X|Yes)P(Yes),所以X分类为No,2020/5/28,52,数据挖掘：概念与技术,贝叶斯分类器,问题如果诸条件概率P(Xi=xi|Y=yj)中的一个为0，则它们的乘积（计算P(X|Y=yj)的表达式）为0很可能每个P(X|Y=yj)都为0解决方法使用Laplace估计:原估计:P(Xi=xi|Y=yj)=nij/nj,2020/5/28,53,数据挖掘：概念与技术,贝叶斯分类器的特点,对孤立的噪声点的鲁棒性个别点对概率估计的影响很小容易处理缺失值在估计概率时忽略缺失值的训练实例对不相关属性的鲁棒性各类在不相关属性上具有类似分布类条件独立假设可能不成立使用其他技术，如贝叶斯信念网络（BayesianBeliefNetworks，BBN）,2020/5/28,54,数据挖掘：概念与技术,贝叶斯信念网络,贝叶斯信念网络(Bayesianbeliefnetwork)允许在变量的子集间定义类条件独立性因果关系图模型表示变量之间的依赖给出联合概率分布的说明图示节点:随机变量边:依赖X,Y是Z的父节点/前驱,并且Y是P的父节点/前驱Z和P之间没有依赖关系图中没有环,2020/5/28,55,数据挖掘：概念与技术,贝叶斯信念网络:例,变量LungCance(LC)值的条件概率表(CPT),给出其双亲结点FamilyHistory和Smoke的每个可能值的组合的条件概率,2020/5/28,56,数据挖掘：概念与技术,贝叶斯信念网络:例(续),给出了LungCancer的CPT.对于其双亲值的每个可能组合,表中给出了LungCancer的每个值的条件概率.例如,由左上角和右下角,我们分别看到P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.9对应于属性或变量Z1,Zn的任意元组(z1,zn)的联合概率由下式计算其中,P(zi|parents(zi)的值对应于Zi的CPT中的表目,2020/5/28,57,数据挖掘：概念与技术,训练贝叶斯信念网络,若干情况给定网络结构和所有可观测变量只需要学习CPT网络结构已知,而某些变量是隐藏的使用梯度下降法或类似于神经网络的方法训练信念网络网络结构未知,所有的变量可以观测搜索模型空间,构造网络拓扑结构网络结构未知,所有变量是隐藏的没有已知的好算法D.Heckerman,Bayesiannetworksfordatamining,2020/5/28,58,数据挖掘：概念与技术,训练贝叶斯信念网络,梯度下降法设S是s个训练样本X1,X2,.,Xs的集合,wijk是具有双亲Ui=uik的变量Y=yij的CPT项wijk可以看作权,类似于神经网络中隐藏单元的权.权的集合记作w这些权被初始化为随机概率值.梯度下降策略采用贪心爬山法.在每次迭代中,修改这些权,并最终收敛到一个局部最优解基于w的每个可能设置都等可能的假定,该方法搜索能最好地对数据建模wijk值.目标是最大化,2020/5/28,59,数据挖掘：概念与技术,训练贝叶斯信念网络:梯度下降法,给定网络结构和wijk的初值,该算法按以下步骤处理计算梯度：对每个i,j,k，计算沿梯度方向前进一小步:用下式更新权值l是表示步长的学习率,设置为一个小常数重新规格化权值：由于权值wijk是概率值,它们必须在0.0和1.0之间,并且对于所有的i,k，必须有,2020/5/28,60,数据挖掘：概念与技术,BBN的特点,BBN提供了一种用图形模型来捕获特定领域的先验知识的方法。网络还可以用来对变量间的因果依赖关系进行编码构造网络可能既费时又费力。然而，一旦网络结构确定下来，添加新变量就十分容易贝叶斯网络很适合处理不完整的数据。对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理因为数据和先验知识以概率的方式结合起来了，所以该方法对模型的过分拟合问题是非常鲁棒的,2020/5/28,61,数据挖掘：概念与技术,使用BBN进行推理举例,E:锻炼,D:饮食,HD:心脏病,Hb:胸口痛,BP:血压,CP:胸痛,2020/5/28,62,数据挖掘：概念与技术,情况一：没有先验信息,通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个人是否可能患心脏病设Yes,No表示锻炼的两个值，健康,不健康表示饮食的两个值，由全概率公式P(HD=Yes)=0.250.70.25+0.450.70.75+0.550.30.25+0.750.30.75=0.49因为P(HD=No)=1P(HD=Yes)=0.51，所以，此人不得心脏病的机率略微大一点,2020/5/28,63,数据挖掘：概念与技术,情况二：高血压,如果一个人有高血压，可以通过比较后验概率P(HD=Yes|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病先用全概率公式，计算P(BP=高)P(BP=高)=0.850.49+0.20.51=0.5185其中Yes,No用贝叶斯公式计算此人患心脏病的后验概率,2020/5/28,64,数据挖掘：概念与技术,情况三,情况三：高血压、饮食健康、经常锻炼身体患心脏病的后验概率,2020/5/28,65,数据挖掘：概念与技术,5.4人工神经网络,神经网络,神经网络最早是由心理学家和神经学家提出的,旨在寻求开发和测试神经的计算模拟神经网络是一组连接的输入/输出单元,其中每个连接都与一个权相关联在学习阶段,通过调整神经网络的权,使得能够预测输入样本的正确类标记神经网络的优点对噪音数据的高承受能力对未知样本的分类能力神经网络缺点需要很长的训练时间,因而对于有足够长训练时间的应用更合适很难解释蕴涵在学习权之中的符号含义它需要大量的参数,这些通常主要靠经验确定,如网络拓扑或“结构”,2020/5/28,67,数据挖掘：概念与技术,多层前馈神经网络,后向传播是一种神经网络学习算法后向传播算法在多层前馈(multilayerfeed-forward)神经网络上学习例:一个多层前馈神经网络训练样本X=x1,x2,.,xi馈入输入层.每层之间存在加权连接;其中,wij表示由某层的单元j到前一层的单元i的权,2020/5/28,68,数据挖掘：概念与技术,多层前馈神经网络(续),输入同时提供给称作输入层的单元层隐藏层的数量是任意的,实践中通常只用一层输出层发布给定样本的网络预测隐藏层和输出层的单元,有时称作neurodes(源于符号生物学),或输出单元包含n个隐藏层的网络称作n+1层神经网络网络是前馈的,如果其权都不回送到输入单元,或前一层的输出单元网络是全连接的,如果每个单元都向下一层的每个单元提供输入给定足够多的隐藏单元,线性阈值函数的多层前馈神经网络可以逼近任何函数,2020/5/28,69,数据挖掘：概念与技术,多层前馈神经网络(续),定义网络拓扑用户必须说明输入层的单元数,隐藏层数,每一隐藏层的单元数和输出层的单元数对于“最好的”隐藏层单元数没有明确的规则网络设计是一个实验过程,并可能影响结果训练网络的准确性.权的初值也可能影响结果的准确性一旦网络经过训练,并且其准确率不能被接受,则通常用不同的网络拓扑或使用不同的初始权值,重复训练过程对训练样本中每个属性的值进行规格化将有助于加快学习过程通常,对输入值规格化,使得它们落入0.0和1.0之间离散值属性可以重新编码,使得每个域值一个输入单元例如,如果属性A的定义域为(a0,a1,a2),则可以分配三个输入单元I0,I1,I2表示A,2020/5/28,70,数据挖掘：概念与技术,后向传播,基本思想迭代地处理一组训练样本,将每个样本的网络预测与实际知道的类标号比较,进行学习.对于每个训练样本,修改权值,使得网络预测和实际类之间的均方误差最小尽管不能保证,一般地,权将最终收敛,学习过程停止步骤解释初始化权:网络的权被初始化为很小的随机数(例如,由-1.0到1.0,或由-0.5到0.5),每个单元有一个偏置,也类似地初始化为小随机数每个样本X按以下步骤处理向前传播输入后向传播误差重复以上两步,直至终止条件满足,2020/5/28,71,数据挖掘：概念与技术,后向传播(续),向前传播输入计算隐藏层和输出层每个单元的净输入和输出对于输入层的单元j,它的输出等于它的输入;Oj=Ij.给定隐藏层或输出层的单元j,到单元j的净输入Ij是其中,wij是由上一层的单元i到单元j的连接的权;Oi是上一层的单元i的输出;而j是单元j的偏差(用来改变单元的活性)给定单元j的净输入Ij,则单元j的输出Oj用下式(logistic函数)计算该函数又称挤压函数,因为它将一个较大的输入值域映射到较小的区间0到1,2020/5/28,72,数据挖掘：概念与技术,一个神经元(Neuron),一个隐藏或输出单元j：j的输入是来自前一层的输出.这些与对应的权相乘,以形成加权和,加权和加到与单元j相联的偏差上,一个非线性的活化函数用于净输入,2020/5/28,73,数据挖掘：概念与技术,神经网络的激活函数,线性函数,S型函数,双曲正切函数,符号函数,2020/5/28,74,数据挖掘：概念与技术,后向传播(续),后向传播误差通过更新权和反映网络预测误差的偏置,向后传播误差对于输出层单元j,误差Errj用下式计算其中,Oj是单元j的实际输出,而Tj是j基于给定训练样本的已知类标号的真正输出,Oj(1-Oj)是logistic函数的导数隐藏层单元j的误差是其中,wkj是由下一较高层中单元k到单元j的连接权,而Errk是单元k的误差,2020/5/28,75,数据挖掘：概念与技术,后向传播(续),后向传播误差(续)更新权和偏置,以反映传播的误差权由下式更新其中,wij是权wij的改变;变量l是学习率,通常取0和1之间的值.学习率帮助避免陷入判定空间的局部最小学习率调整规则:将学习率设置为1/t.其中t是已对训练样本集迭代的次数偏置由下式更新其中,j是偏置j的改变,2020/5/28,76,数据挖掘：概念与技术,后向传播(续),实例更新VS.周期更新实例更新(caseupdate):每处理一个样本就更新权值和偏置周期更新(epochupdate):处理完训练集中的所有样本之后再更新权值和偏置终止条件前一周期所有的wij都小于某个指定的阈值,或前一周期未正确分类的样本百分比小于某个阈值,或超过预先指定的周期数实践中,权值收敛可能需要数十万个周期,2020/5/28,77,数据挖掘：概念与技术,后向传播算法,输入D:由训练元组和它们的相关联的目标值组成的数据集l:学习率Network:多层前馈网络输出:训练后的神经网络方法:(1)初始化network的权和偏置(2)while(终止条件不满足)(3)for(D中每个训练元组X)(4)/向前传播输入(5)for每个输入层单元j(6)Oj=Ij；/输入单元的输出是它的实际输入值(7)for(隐藏或输出层每个单元j)(8)/相对于前一层i,计算单元j的净输入(9)/计算单元j的输出,2020/5/28,78,数据挖掘：概念与技术,后向传播算法(续),(10)/后向传播误差(11)for输出层每个单元j(12)Errj=Oj(1Oj)(TjOj)；/计算误差(13)for(由最后一个到第一个隐藏层,对于隐藏层每个单元j)(14)/计算下一个较高层k的误差(15)fornetwor中每个权wij(16)wij=(l)ErrjOi；/权值增量(17)wij=wij+wij；/权值更新(18)fornetwor中每个偏差j(19)j=(l)Errj；/偏置增量(20)j=j+j；/偏置更新(21),2020/5/28,79,数据挖掘：概念与技术,后向传播:例,一个多层前馈神经网络第一个训练样本X=1,0,1（其类标号为1）,2020/5/28,80,数据挖掘：概念与技术,后向传播:例(续),初始输入、权值和偏差值净输入和输出的计算计算每个结点的误差,2020/5/28,81,数据挖掘：概念与技术,后向传播:例(续),计算权和偏置的更新,2020/5/28,82,数据挖掘：概念与技术,神经网络的特点,至少含有一个隐藏层的多层神经网络是一种普适近似（universalapproximator），即可以用来近似任何目标函数ANN可以处理冗余特征权值在训练过程中自动学习，冗余特征的权值非常小神经网络对训练数据中的噪声非常敏感使用确认集来确定模型的泛化误差每次迭代把权值减少一个因子使用的梯度下降方法经常会收敛到局部最小值权值更新公式中加上一个动量项训练ANN是一个很耗时的过程，但分类非常快,2020/5/28,83,数据挖掘：概念与技术,5.5支持向量机,支持向量机,支持向量机(SupportVectorMachines,SVM)源于Vapnik和Chervonenkis的统计学习理论的早期工作第一篇论文是Boser,Guyon和VapnikBGV92的文章优点对复杂的非线性边界的建模能力与其它模型相比,它们不太容易过分拟合支持向量机还提供了学习模型的紧凑表示广泛的使用范围SVM可以用来预测和分类它们已经用在许多领域,包括手写数字识别、对象识别、演说人识别,以及基准时间序列预测检验,2020/5/28,85,数据挖掘：概念与技术,支持向量机,两个线性可分的类找到这样一个超平面，使得所有的方块位于这个超平面的一侧，而所有的圆圈位于它的另一侧可能存在无穷多个那样的超平面,2020/5/28,86,数据挖掘：概念与技术,决策边界的边缘,找这样的超平面，它最大化边缘B1比B2好,2020/5/28,87,数据挖掘：概念与技术,SVM的决策边界和边缘,一个线性分类器的决策边界可以写成如下形式：wx+b=0其中，w和b是模型的参数,2020/5/28,88,数据挖掘：概念与技术,边缘,方块的类标号为+1，圆圈的类标号为1z的类标号y调整决策边界的参数w和b，两个平行的超平面bi1和bi2可以表示如下bi1：wx+b=1bi2：wx+b=1可以证明,边缘d,2020/5/28,89,数据挖掘：概念与技术,边缘推导,w的方向垂直于决策边界如果xa和xb是任意两个位于决策边界上的点，则wxa+b=0,wxb+b=0于是w(xbxa)=0.由于xbxa是决策超平面中任意向量,于是w的方向必然垂直于决策边界令x1是bi1上的数据点，x2是bi2上的数据点.代入bi1和bi2相减得到w.(x1x2)=2由令u=w,v=x1x2,得到|w|x1x2|cos(w,x1x2)=2,2020/5/28,90,数据挖掘：概念与技术,边缘推导(续),但|x1x2|cos(w,x1x2)=d于是|w|d=2，即,2020/5/28,91,数据挖掘：概念与技术,SVM,SVM的训练阶段从训练数据中估计决策边界的参数w和b最大化边缘d，并满足wxi+b1如果yi=1wxi+b1如果yi=1即yi(wxi+b)1最大化d等价于最小化这是一个凸二次优化问题，可以通过标准的拉格朗日乘子（Lagrangemultiplier）方法求解,2020/5/28,92,数据挖掘：概念与技术,SVM(续),拉格朗日算子其中，参数i称为拉格朗日乘子对Lp关于w和b求偏导，并令它们等于零因为拉格朗日乘子i是未知的，因此仍然不能得到w和b的解,(5-38),(5-39),(5-40),2020/5/28,93,数据挖掘：概念与技术,SVM(续),使用Karuch-Kuhn-Tucher（KKT）条件：i0iyi(wxi+b)1=0（5.42）除非训练实例满足方程yi(wxi+b)=1,否则拉格朗日乘子i必须为零i0的训练实例位于超平面bi1或bi2上，称为支持向量（5.39）和（5.40）代入到公式（5.38）中这是Lp的对偶问题(最大化问题).可以使用数值计算技术,如二次规划来求解,(5-43),2020/5/28,94,数据挖掘：概念与技术,SVM(续),解出i后,用(5.39)求w,再用(5.42)求b决策边界为z可以按以下的公式来分类如果f(z)=1，则检验实例z被分为到正类，否则分到负类,2020/5/28,95,数据挖掘：概念与技术,SVM:例,例:二维数据集包含8个训练实例使用二次规划方法,求解优化问题LD,得到i.w1=iyixi1=65.526110.3858+65.5261(1)0.4871=6.64w2=iyixi2=65.526110.4687+65.5261(1)0.611=9.32b(1)=1wx1=1(6.64)(0.3858)(9.32)(0.4687)=7.9300b(2)=1wx2=1(6.64)(0.4871)(9.32)(0.611)=7.9289b=(b(1)+b(2)/2=7.93,i,2020/5/28,96,数据挖掘：概念与技术,SVM:不可分情况,如果不是线性可分的，怎么办？软边缘（softmargin）允许一定训练误差引入松驰变量i其中C和k是用户指定的参数，对误分训练实例加罚取k=1，C根据模型在确认集上的性能选择,2020/5/28,97,数据挖掘：概念与技术,SVM:不可分情况(续),拉格朗日算子其中，前面两项是需要最小化的目标函数，第三项表示与松弛变量相关的不等式约束，而最后一项是要求i的值非负的结果KKT条件i0,i0,i0iyi(wxi+b)1+i=0ii=0,2020/5/28,98,数据挖掘：概念与技术,SVM:不可分情况(续),令L关于w,b和i的一阶导数为零,2020/5/28,99,数据挖掘：概念与技术,SVM:不可分情况(续),对偶拉格朗日问题其形式与可分情况相同,但是0iC,2020/5/28,100,数据挖掘：概念与技术,非线性SVM,使用非线性变换例:,2020/5/28,101,数据挖掘：概念与技术,非线性SVM(续),非线性SVM的优化问题约束条件:yi(w(xi)+b)1,i=1,2,.,N对偶拉格朗日问题参数w和b,2020/5/28,102,数据挖掘：概念与技术,非线性SVM(续),实例z分类点积(xi)(xj)计算问题能否在原空间直接计算?例:,2020/5/28,103,数据挖掘：概念与技术,核技术,Mercer定理:核函数K可以表示为K(u,v)=(u)(v),当且仅当对于任意满足g(x)2dx为有限值的函数g(x)，则K(x,y)g(x)g(y)dxdy0满足定理5.1的核函数称为正定（positivedefinite）核函数常用核函数,2020/5/28,104,数据挖掘：概念与技术,SVM的特点,SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值SVM通过最大化决策边界的边缘来控制模型的能力需要提供其他参数，如使用的核函数类型、为了引入松弛变量所需的代价函数C等分类属性处理每个分类属性值引入一个哑变量,转化为二元变量可以推广到多类问题,2020/5/28,105,数据挖掘：概念与技术,多类问题,SVM是对二类问题设计的还有一些方法也是针对二类问题的如何处理多类问题?训练令Y=y1,y2,.,yK是类标号的集合1-r方法:分解成K个二类问题每一个类yiY创建一个二类问题,其中所有属于yi的样本都被看作正类,而其他样本作为负类1-1方法:构建K(K1)/2个二类分类器每一个分类器用来区分一对类(yi,yj)为类(yi,yj)构建二类分类器时,不属于yi或yj的样本被忽略掉,2020/5/28,106,数据挖掘：概念与技术,多类问题(续),分类投票表决票的计算1-r方法如果一个样本被分为正类,则正类得一票如果一个样本被分为负类,则除正类之外的所有类都得到一票1-1方法如果Cj把样本分到yi类,则yi类得一票冲突处理分到多数类/少数类,2020/5/28,107,数据挖掘：概念与技术,多类问题:例,例:Y=y1,y2,y3,y41-r方法建立4个分类器设这4个分类器分别把检验实例x分类为+,使用简单的多数表决,y1得到最高的票4，而其他类仅仅得到3票,因此检验实例被分类为y11-1方法建立6个分类器假设它们对x如下表y1和y4都得到2票,而y2和y3仅仅得到1票,2020/5/28,108,数据挖掘：概念与技术,5.6组合方法,一般思想,聚集多个分类器的预测来提高分类准确率称为组合（ensemble）或分类器组合（classifiercombination）方法,2020/5/28,110,数据挖掘：概念与技术,Whydo