分类算法大数据

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Lecture 5,分类,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,分类,n,维属性空间,X,：,x,1,x,2, ,x,n,，类标识集合,Y,：,y,1,y,2, ,y,m,。,给定一组实例,（,i,= 1, 2,），,表示,n,维向量,x,i,的类标识是,y,i,，其中,x,i,X,。 这组实例实际上隐含了某一个函数,f,：,X,Y,，使得对于所有的,i,，,有,f,(,x,i,) =,y,i,。,分类问题：找到一个函数,h,(,x,),，使得对于,x,X,，,Pr(,x,)|,f,(,x,),h,(,x,),尽可能的小。,分类：一个,2,步的过程,分类过程（,1,）模型构造,:,对已经分类的数据集进行描述。,分类模型可以表示为分类规则,决策树,或数学公式等。,分类过程（,1,）模型评价,:,对构造出的分类模型进行评价（准确度）。,分类过程（,2,）模型使用,：如果精度可以接受,可以用该模型对未知类型的对象分类。,分类过程,(1):,模型构造,训练数据,分类算法,IF rank = professor,OR years 6,THEN tenured = yes,分类器,(,模型,),分类过程,(1):,模型评价,I,划分法,:,训练集与测试集,把样本划分成,2,个独立的数据集合,如,训练集,(2/3),测试集,(1/3),。,适用于大规模的数据样本。,分类过程,(1):,模型评价,II,交叉验证,(Cross-validation),把数据集合划分成,k,个子样本；,使用,k -,1,个子样本作为训练集，另一个作为测试样本,k,-,折交叉验证。,适用于中等规模的数据。,留一测试,(Leave One Out,，,k,=,n,),适用于小规模数据。,分类过程,(2):,用模型预测,分类器,测试数据,未分类对象,(Jeff, Professor, 4),Tenured?,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,决策树简介,根结点,脖子短,大象,长颈鹿,松鼠,老鼠,会吱吱叫,不会吱吱叫,个子大,在水里,鼻子长,脖子长,个子小,鼻子短,在陆地上,犀牛,河马,内部节点：决策属性,叶子节点：目标属性,属性值,决策树简介,合取,：从根节点到叶节点的每一条路经都对应着一条,分类规则,，规则间各个部分（各个层的条件）的关系是合取关系。,析取,：整个决策树就对应着一组析取的规则,(Disjunctive Rule),。,简单,：决策树学习算法的最大优点是简单，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。,决策树学习要解决的主要问题,数据标注,：这些数据的所有属性应该是完全标注的。,特征选择,：数据的哪些属性可以被用来分类。,分支准则,：即在众多分支准则中，每一步选择哪一准则使最终的树更令人满意。,分类停止条件,：树增长满足什么条件时停止。,决策树归纳算法,ID3,：描述,ID3(Examples, Attributes),Examples,即训练样例集，,Attributes,是决策属性列表。算法返回一棵能正确分类给定,Examples,的决策树。,1.,创建树的根节点,Root,。,2.,如果,Examples,都为同一类，则节点标记为该类，并返回单节点树,Root,。,3.,如果,Attributes,为空，则节点标记为,Examples,中最普遍的类,(,多数投票,),，并返回单结点树,Root,。,决策树归纳算法：描述（续）,4.,否则开始：,4.1 A,Attributes,中分类,Examples,能力最好的属性,.,4.2 Root,的决策属性,A.,4.3,对于,A,的每个可能值,v,i,4.3.1,在,Root,下加一个新的分枝对应测试,A=v,i,.,4.3.2,令,Examples,vi,为,Examples,中满足,A,属性值为,v,i,的子集,.,4.3.3,如果,Examples,vi,为空,4.3.3.1,在这个新分支下加一个叶子节点,并标记为,Examples,中最普遍的类，并返回,.,4.3.3.2,否则在这个新分支下加一个子树,ID3(Examples,vi, Attributes - A),属性选择度量,:,信息增益,(ID3/C4.5),启发式策略,：选择具有最高信息增益的属性。,期望信息,：设样本集合,s,含有,s,i,个类为,C,i,的元组,i,= 1, m,，则对一个给定的样本分类所需的期望信息是：,熵,（,Entropy,）,：具有值,a,1,a,2,a,v,的属性,A,的熵,E(A),为属性,A,导致的,s,的划分的期望信息的加权平均和。：,信息增益,：在,A,上分枝将获得的信息增益是,决策树构造：一个例子,决策树构造：一个例子,计算分类所需的期望信息：,决策树构造：一个例子,属性,age,的熵的计算：,决策树构造：一个例子,属性,age,的信息增益,：,同样，对其它属性有,：,递归调用：,5,个：,3,个买，,2,个不买,决策树构造：一个例子,ID3(5,个, BC, I, S, C),ID3(4,个, BC, I, S, C),ID3(5,个, BC, I, S, C),age?,40,30.40,5,个：,2,个买，,3,个不买,4,个：都买,算法停止,所以我们有决策树：,5,个：,3,个买，,2,个不买,age?,40,30.40,5,个：,2,个买，,3,个不买,yes,决策树构造：一个例子,ID3(5,个, BC, I, S, C),ID3(5,个, BC, I, S, C),下一步递归调用,ID3,：针对年龄,30,的样本集测试剩余的属性,计算对,30,的样本集进行分类所需的信息：其中,2,个买（类,Yes,或,1,），,3,个不买（类,No,或,2,），所以有：,决策树构造：一个例子,计算属性,student,的熵,E(student),：,学生（属性值,1,）有,2,个，都买，即属于类,Yes,或,1,，非学生（属性值,2,）有,3,个，属于类,No,或,2,。,决策树构造：一个例子,因此，,Gain,(student)=I(s,1,s,2,)-E(stu)=0.971,同样，计算其它几个属性的增益：,Gain(income)=,略,Gain(credit_rating)=,略,属性,Student,的增益最大。,决策树构造：一个例子,递归调用,：,决策树构造：一个例子,ID3(3,个, BC, I, C),ID3(2,个, BC, I, C),算法停止,算法停止,age?,student?,no,yes,40,yes,30.40,ID3(5,个, BC, I, S, C),2,个：都买,3,个：都不买,5,个：,3,个买，,2,个不买,所以我们有决策树,：,决策树构造：一个例子,ID3(5,个, BC, I, S, C),age?,student?,no,yes,40,no,yes,yes,30.40,5,个：,3,个买，,2,个不买,下一步递归调用,ID3,：针对年龄,40,的样本集测试剩余的属性,计算对,40,的样本集进行分类所需的信息：其中,3,个买（类,Yes,或,1,），,2,个不买（类,No,或,2,）,决策树构造：一个例子,计算属性,Credit_Rating,的熵,E(CR),：,fair,（属性值,1,）有,3,个，都买，即属于类,Yes,或,1,，,excellent,（属性值,2,）有,2,个，属于类,No,或,2,。,决策树构造：一个例子,Gain(CR)=I(s,1,s,2,)-E(CR)=0.971,同样，计算其它几个属性的增益,Gain(income)=,略,Gain(Stu)=,略,属性,Credit_Rating,的增益最大,决策树构造：一个例子,递归调用,：,决策树构造：一个例子,ID3(2,个, BC, I, S),ID3(3,个, BC, I, S),算法停止,算法停止,age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,yes,yes,30.40,3,个：都买,2,个：都不买,所以我们有决策树,：,age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,决策树构造：一个例子,所有样本已经被分类，算法停止，我们得到最终的决策树如下：,age?,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,决策树构造：一个例子,决策树裁剪,“Everything should be made as simple as possible, but not simpler.”,Albert Einstein,避免过度拟合,Class B,Class B,Class A,Class A,no,yes,no,no,no,no,yes,yes,yes,Class B,Class A,Class B,no,yes,yes,裁剪前,裁剪后,Class B,Class A,Class A,no,yes,no,no,yes,yes,Class B,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,朴素贝页斯分类器,X,是一个类标识未知的数据样本。,对分类问题,确定,P,(,C,i,|,X,):,给定观测数据样本,X,，确定,X,属于类,C,i,的概率。,P,(,C,i,):,类,C,i,的先验概率,(prior probability) (,即在我们观测任何数据之前的初始概率,它反映了背景知识,),P,(,X,):,样本数据被观测的概率。,P,(,X,|,C,i,):,在属于类,C,i,的前提下，观测到样本,X,的概率。,贝叶斯定理,给定训练集,X,X,属于类,C,i,的后验概率,(posteriori probability),P,(,C,|,X,),遵守如下贝叶斯定理,MAP (Maximum a posteriori,，极大后验,),假设,实际应用的困难,:,需要许多概率的初始知识,需要较多的计算时间。,简化：朴素贝叶斯分类器,一个简化假设,:,属性之间是条件独立的,:,一旦知道了概率,P,(,X,|,C,i,),把,X,赋予使得,P,(,X,|,C,i,)*,P,(,C,i,),具有极大值的类,C,i,。,一个例子,类,:,C1:buys_computer=,yes,C2:buys_computer=,no,数据样本,X =(age=30,Income=medium,Student=yes,Credit_rating=,Fair),一个例子,对每一个类，计算,P(X|C,i,),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|Ci) :,P(X|buys_computer=“yes”)= 0.222,0.444,0.667,0.0.667 =0.044,P(X|buys_computer=“no”)= 0.6,0.4,0.2,0.4 =0.019,P(X|Ci),P(Ci ) :,P(X | yes),P(yes) = 0.028,P(X | no),P(no) = 0.007,所以：,X,属于类 “,buys_computer=yes”,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,最近邻分类（,k,-NN,）,“,故近朱者赤，近墨者黑；声和则响清，形正则影直。,”,孟子,滕文公章句下,给定一个未知样本，,k,最近邻分类法搜索模式空间，找出最接近未知样本的,k,个训练样本。这,k,个训练样本是未知样本的,k,个“近邻”。“近邻性”有多种定义方式，如欧几里得距离。,未知样本被分配到,k,个最近邻者中最公共的类。,k,1,时，未知样本被指定到模式空间中与之最近邻的训练样本的类。,示例,给定训练集合：,k,=3,对象,1,2, 3,的类是,C,1,。 对象,4, 5, 6,的类是,C,2,。确定对象,7,：,(15,17),的类标识。,示例,计算对象,7,与所有训练样本的距离：,7,的,3,个最近邻对象是,3, 5, 6,其中,3,的类是,C,1,，,5,和,6,的类是,C,2,，因此,7,的类标识是,C,2,。,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,基于规则的分类器,IF,Condition,THEN,Prediction_Class,IF,age,=,“,=30,”,AND,student,=,“,no,”,THEN,buys_computer,=,“,no,”,IF,age,=,“,=30,”,AND,student,=,“,yes,”,THEN,buys_computer,=,“,yes,”,前件，后件，覆盖,利用分治法学习规则,Separate_and_Conquer(,D,),设,D,c,为,D,中类,c,的示例集合,;,For each class c,While(,D,c,),R,Learn_One_Rule(,D,D,c,);,D,c,D,c, ,D,c,中被,R,覆盖的实例,;,Rule_Set,Rule_Set,R,;,End while,End for,Return,Rule_Set,;,学习一个规则,Learn_One_Rule(,D,D,c,),R,;,D,c,D,D,c,while(,R,还覆盖反例,I,D,c,),根据某种规则质量度量标准选择一个属性,A,max,;,从,D,c,中,移除被,A,max,区分的反类；,R,R,A,max,;,End while,Return,R,;,一个示例,选择属性,AT,使得：与,AT,取值不同的其它类的示例数目最多。,以“,1”,为正类学习覆盖“,1”,类的规则。,一个示例,一个示例,所有反例已被覆盖，,我们得到一条规则如下：,(C=1), (,D=1),(Class = 1),一个示例,利用规则,(C=1), (,D=1),(Class = 1),删除所有正类。,该规则已覆盖所有正类。,以“,0”,为正类继续学习覆盖“,0”,类的规则。,基于规则的分类若干问题,学习到的规则能够覆盖整个示例空间吗？缺省规则,如何学到最优规则？,NP,hard,问题,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,k,最近邻的弱点,距离的度量,参数敏感,不相关属性,CRN- ,Wang Jiabing, Zhang Pei, Wen Guihua, and Wei Jia. Classifying categorical data by rule-based neighbors. In,Proc. of the IEEE International Conference on Data Mining,(,ICDM 2011,). Vancouver, Canada, December 1114, pp. 12481253, 2011,.,CRN,基本思想,学习一个特征子集的集合,S,：对于每一对属于不同类的实例，存在一个特征子集,V,使得这两个实例在,V,上的取值不完全相同。,根据,S,来重新定义“邻居”,。,用“邻居”进行分类。,CRN,基本思想,问题：存在指数增长的特征子集。,启发式方法：,属性应该具有很好的分类能力,特征子集应该越小越好,区分不相关属性,符号约定,D,:,训练集,.,D,c,:,D,中类标识为,c,的子集,.,I,A,:,实例,I,在属性,A,上的取值,.,V,:,特征子集（,feature set,）,S,:,V,的集合,.,设,I,D,c,.,我们说属性,A,区分,实例,I,和,I,，如果,I,A,I,A,;,给定一个特征子集,V,我们说,V,区分,D,D,c,和,I,，,如果任给,I,D,D,c,，存在,A,V,，使得,I,A,I,A,.,设,I,D,c,及,D,c,D,D,c,，,C,(,A,D,c,),为,D,c,中,I,A,I,A,的实例数目。,给定训练集,D,一个特征子集,V,一个标记实例,I,D,c,一个未标记实例,I,我们说,I,是,I,关于,V,类为,c,的邻居当且仅当任给,A,V,I,A,=,I,A,.,一些定义,属性的度量,E,(,A,D,),：,A,在训练集,D,中的熵，分类能力。,C,(,A,D,c,),：子集越小越好。,SI,(,A,D,),：,A,在,D,中的划分信息，用来克服,E,(,A,D,),和,C,(,A,D,c,),的偏好二者倾向于选择具有多个值的属性。,训练算法,对于每个属性，计算熵,E,及划分信息,S,，令,ES,=,E,*,S,;,对于每个类,c,Temp,D,c,，,I,D,c,D,D,c,;,While(|,Temp,|),任意挑选,Temp,中的一个实例,I,；,V,Learning,_,One,_,Feature,_,Set,(,I,ES,D,c,);,如果,V,不属于,S,，则将其加入,S,;,从,Temp,中删去,I,的所有关于,V,的邻居,;,返回,S,;,学习一个特征子集,Attribute,_,Set, ,所有属性,;,计算,Attribute,_,Set,中每一个属性关于,D,c,的质量度量,;,While (|,D,c,|,&,|,Attribute,_,Set,|),V,V,A,min,|,A,min,在,Attribute,_,Set,中质量度量值最小,；,Attribute,_,Set,Attribute,_,Set,A,min,;,从,D,c,中删去被,A,min,区分开的实例,，即,I,Amin,I,Amin,的实例,I,;,重新计算,Attribute,_,Set,中每一个属性关于,D,c,的质量度量,;,返回,V,;,分类阶段,给定一个待分类实例,I,，特征子集集合,S,，训练集,D,，,CRN,将根据,I,在每个特征子集,V,上邻居的类分布纯度、邻居个数及,V,的大小来共同决定,I,的类别。,邻居的混杂度,N,c,(,V,):,一个待分类实例,I,在,V,上类为,c,的邻居数目，,SUM,为,N,c,(,V,),之和（即对,c,求和），即,I,在,V,上的所有邻居之和。,定义,I,在,V,上邻居的,混杂度,如下（越小越纯）：,候选类标识,定义,I,在,V,上的候选类标识,CL,(,V,),如下,：,类标识的优先级,定义类标识优先级如下，其中,IP,min,为,I,在所有特征子集上的最小混杂度：,分类规则,定义,Priority,max,为最大的优先级,若,IP,min,为不为,+,返回具有最大优先级的候选类标识,CL,(,V,)(,若有多个，则返回在训练集中数目最小的类标识）；,否则,返回训练集中占多数的类标识；,精度：UCI数据,精度：人造数据,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,集成学习（,Ensemble Learning,）,基本思想：训练子集集成,训练集,1,训练集,2,训练集,3,.,集成,.,分类器,C1,分类方法,(CM),CM,分类器,C2,CM,分类器,C3,分类器,C*,集成学习（,Ensemble Learning,）,基本思想：属性子集集成,属性集,1,属性集,2,属性集,3,.,集成,.,分类器,C1,分类方法,(CM),CM,分类器,C2,CM,分类器,C3,分类器,C*,分类（有监督学习）,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规则的分类器,CRN,：基于特征子集的近邻分类器,集成学习,样本复杂性,样本复杂性,时间复杂性和空间复杂性,：一个学习算法需要多大的计算量和存储空间。,样本复杂性,：学习器要成功地学习到目标概念（以较高的概率），需要多少训练样例？,样本复杂性的一个定理,给定参数,0,1,，使任何一致学习器以概率大于等于,、错误率小于等于,学习到假设空间,H,中的目标概念所需的样本数,m,满足如下不等式：,例子：布尔概念,布尔文字的合取：若假设空间,H,定义为,n,个布尔文字的合取，则假设空间,H,的大小,|,H,|,为,3,n,。将器代入上式解得：,若定义为,10,个文字的合取，那么可有,95%,的概率它将学习到一个错误率小于,0.1,的假设，而且所需的样例数量为,140,。,多项式样本复杂性！,例子：无偏学习,考虑一无偏概念类,H,，它包含所有与样本空间,X,有关的可教授的概念。,H,对应于,X,的幂集，即包含,X,的所有子集的集合，共包含,2,|,X,|,个概念。若,X,中的示例定义为,n,个布尔特征值，将有,|,X,|,2,n,个不同示例，因此有以下个不同的概念：,将其代入到前述不等式得：,指数样本复杂性,不可学习！,