分类算法大数据

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,分类算法大数据,分类有监视学习,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规那么的分类器,CRN：基于特征子集的近邻分类器,集成学习,样本复杂性,分类,n维属性空间X：x1, x2, , xn ，类标识集合Y：y1, y2, , ym。,给定一组实例i = 1, 2, ，表示n维向量xi的类标识是yi，其中xi X 。 这组实例实际上隐含了某一个函数f：XY，使得对于所有的i，有f(xi) =yi。,分类问题：找到一个函数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的每个可能值vi,4.3.1 在Root下加一个新的分枝对应测试A=vi.,4.3.2 令Examplesvi为Examples中满足A属性值为vi的子集.,4.3.3 如果Examplesvi为空,4.3.3.1 在这个新分支下加一个叶子节点, 并标记为 Examples 中最普遍的类，并返回.,4.3.3.2 否那么在这个新分支下加一个子树 ID3(Examplesvi, Attributes - A),属性选择度量,:,信息增益,(ID3/C4.5),启发式策略：选择具有最高信息增益的属性。,期望信息：设样本集合s含有si 个类为Ci 的元组, i = 1, , m，那么对一个给定的样本分类所需的期望信息是：,熵Entropy：具有值 a1,a2,av的属性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,同样，计算其它几个属性的增益：,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,同样，计算其它几个属性的增益,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|Ci),X=(age=30 ,income =medium, student=yes,credit_rating=fair),P(X|Ci) : P(X|buys_computer=“yes)= 0.222 0.444 0.667 ,P(X|buys_computer=“no)= 0.6 0.4 0.2 ,P(X|Ci) P(Ci ) : P(X | yes) ,P(X | no) ,所以：X 属于类 “buys_computer=yes,分类有监视学习,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规那么的分类器,CRN：基于特征子集的近邻分类器,集成学习,样本复杂性,最近邻分类k-NN,“故近朱者赤，近墨者黑；声和那么响清，形正那么影直。,?孟子?滕文公章句下?,给定一个未知样本， k最近邻分类法搜索模式空间，找出最接近未知样本的k个训练样本。这k个训练样本是未知样本的k个“近邻。“近邻性有多种定义方式，如欧几里得距离。,未知样本被分配到k个最近邻者中最公共的类。k1时，未知样本被指定到模式空间中与之最近邻的训练样本的类。,例如,给定训练集合：,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),设Dc为D中类c的例如集合;,For each class c,While(Dc ),R Learn_One_Rule(D, Dc);,Dc Dc Dc中被R覆盖的实例;,Rule_Set Rule_Set R;,End while,End for,Return Rule_Set;,学习一个规那么,Learn_One_Rule(D, Dc),R ;,Dc D Dc,while(R还覆盖反例I Dc),根据某种规那么质量度量标准选择一个属性Amax;,从Dc 中 移除被Amax 区分的反类；,R R Amax;,End while,Return R;,一个例如,选择属性AT使得：与AT取值不同的其它类的例如数目最多。,以“1为正类学习覆盖“1类的规那么。,一个例如,一个例如,所有反例已被覆盖，,我们得到一条规那么如下：,(C=1) (D=1)(Class = 1),一个例如,利用规那么(C=1) (D=1)(Class = 1)删除所有正类。,该规那么已覆盖所有正类。,以“0为正类继续学习覆盖“0类的规那么。,基于规那么的分类假设干问题,学习到的规那么能够覆盖整个例如空间吗？缺省规那么,如何学到最优规那么？NPhard问题,分类有监视学习,什么是分类,决策树算法,朴素贝页斯分类器,最近邻分类器,基于规那么的分类器,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 2021). Vancouver, Canada, December 1114, pp. 12481253, 2021.,CRN根本思想,学习一个特征子集的集合S：对于每一对属于不同类的实例，存在一个特征子集V使得这两个实例在V上的取值不完全一样。,根据S来重新定义“邻居。,用“邻居进展分类。,CRN根本思想,问题：存在指数增长的特征子集。,启发式方法：,属性应该具有很好的分类能力,特征子集应该越小越好,区分不相关属性,符号约定,D: 训练集.,Dc: D中类标识为c的子集.,IA: 实例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, Dc)：子集越小越好。,SI(A, D) ：A在D中的划分信息，用来抑制E(A, D)和C(A, Dc)的偏好二者倾向于选择具有多个值的属性。,训练算法,对于每个属性，计算熵E及划分信息S，令ES=E*S;,对于每个类 c,Temp Dc ，I Dc D Dc;,While(|Temp |),任意挑选Temp中的一个实例I；,V Learning_One_Feature_Set (I, ES, Dc);,如果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,的类别。,邻居的混杂度,Nc(V): 一个待分类实例I在V上类为c的邻居数目，SUM为Nc(V)之和即对c求和，即I在V上的所有邻居之和。,定义I在V上邻居的混杂度如下越小越纯：,候选类标识,定义,I,在,V,上的候选类标识,CL,(,V,),如下,：,类标识的优先级,定义类标识优先级如下，其中,IP,min,为,I,在所有特征子集上的最小混杂度：,分类规那么,定义Prioritymax为最大的优先级,假设IPmin为不为+,返回具有最大优先级的候选类标识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|为3n。将器代入上式解得：,假设定义为10个文字的合取，那么可有95%的概率它将学习到一个错误率小于的假设，而且所需的样例数量为140。,多项式样本复杂性！,例子：无偏学习,考虑一无偏概念类H，它包含所有与样本空间X有关的可教授的概念。 H对应于X的幂集，即包含X的所有子集的集合，共包含2 |X|个概念。假设X中的例如定义为n个布尔特征值，将有|X|2n个不同例如，因此有以下个不同的概念：,将其代入到前述不等式得：,指数样本复杂性,不可学习！,谢谢,