第三周决策树和Boostingppt课件

1、1分类: 根本概念分类: 根本概念决策树基于规那么分类贝叶斯分类方法提高分类准确率的技术小结2什么是分类？分类，分类器银行贷款员需求分析数据，以便搞清楚哪些贷款恳求者是“平安的；医学研讨人员分析癌症数据，以便选择治疗方案数据分析义务都是分类，都需求构造一个分类器来预测类标号数值预测，预测器销售经理希望预测一位给定的顾客在双11的一次购物期间将花多少钱数据分析义务就是数值预测，所构造的模型预测器预测一个延续值函数或有序值，而不是类标号3分类预测类标号 (离散的或标称的)基于训练集和类标号构建分类器，并对新的数据进展分类数值预测所构造的模型预测一个延续值函数，而不是类标号典型运用信誉卡/贷款同意:

2、医疗诊断: 肿瘤是良性的还是恶性的欺诈检测: 一次买卖能否是欺诈的网页分类: 属于哪一类预测问题: 分类与数值预测4分类一个两阶段过程两阶段：学习阶段构建分类模型和分类阶段运用模型预测给定数据的类标号分类模型构建(学习阶段): 描画预先定义的类假设每个元组都属于一个预先定义的类，由类标号属性确定，类标号属性是离散值的和无序的用于模型构建的元组集合称为训练集模型用分类规那么，决策树，或数学公式表示模型运用(分类阶段): 用于分类未知对象评价模型的准确性检验样本的知标签与模型的分类结果比较准确率是被模型正确分类的检验样本所占的百分比检验集是独立于训练集的 (否那么过分拟合) 假设准确性是可接受的，

3、那么运用模型来分类新的数据5监视和无监视学习监视学习 (分类)监视:提供了每个训练元组的类标号即分类器的学习在被告知每个训练元组属于哪个类的“监视下进展的新的数据基于训练集被分类无监视学习 (聚类)每个训练元组的类标号是未知的要学习的类的个数或集合也能够事先不知道6阶段 (1): 模型构建训练数据分类算法IF rank = professorOR years 6THEN tenured = yes 分类器(模型)学习：用分类算法分析训练数据7阶段 (2): 运用模型预测分类器检验数据新数据(Jeff, Professor, 4)Tenured?分类：检验数据用于评价分类规那么的准确率8分类:

4、根本概念分类: 根本概念决策树基于规那么分类贝叶斯分类方法提高分类准确率的技术小结9决策树从有类标号的训练元组中学习决策树树构造每个内部结点非树叶结点表示在一个属性上的测试每个分枝代表该测试的一个输出每个树叶结点存放一个类标号树的最顶层结点是根结点如何运用决策树分类？给定一个类标号未知的元组X，在决策树上测试该元组的属性值。跟踪一条由根到叶结点的途径，该叶结点就存放着该元组的类预测。10决策树归纳: 一个例子age?overcaststudent?credit rating?40noyesyesyes31.40nofairexcellentyesno训练数据集: Buys_computer决策

5、树:11决策树归纳算法根底算法 (贪婪算法)决策树以自顶向下递归的分治方式构造从训练元组集和它们相关联的类标号开场构造决策树一切属性是具有类别的 (假设是延续数值型的，那么它们需求事先离散化)基于选择的属性对元组进展递归划分测试属性基于统计学度量来选择 (例如, 信息增益)停顿划分的条件给定结点的一切元组都属于同一个类没有剩余属性可以用来进一步划分元组给定的分枝没有元组算法根本战略三个参数：D为数据分区，开场时，它是训练元组和它们相应类标号的完选集。参数attribute_list是描画元组属性的列表。参数Attribute_selection_method用来选择可以按类“最好地区分给定元组

6、的属性，该过程运用一种属性选择度量信息增益或基尼指数。树从单个结点N开场，N代表D中的训练元组假设D中的元组都为同一类，那么结点N变成树叶，并用该类标志它否那么，算法调用Attribute_selection_method确定分裂准那么。分裂准那么指定分裂属性，并且也指出分裂点或分裂子集对分裂准那么的每个输出，由结点N生长一个分枝。根据分裂属性A的类型，有三种能够的情况A是离散值的: 结点N的测试输出直接对应于A的知值A是延续值的: 结点N的测试有两个能够的输出，分别对应于条件Asplit_point, 其中split_point是分裂点A是离散值并且必需产生二叉树: 在结点N的测试形如“A

7、SA？，其中SA是A的分裂子集算法: Generate_decision_tree。由数据分区D中的训练元组产生决策树。输入:数据分区D, 训练元组和他们对应类标号的集合attribute_list, 候选属性的集合。Attribute_selection_method, 一个确定“最好地划分数据元组为个体类的分裂准那么的过程。这个准那么由分裂属性(splitting_attribute)和分裂点或划分子集组成。输出: 一棵决策树。方法:(1) 创建一个结点N；(2) if D中的元组都在同一类C中 then(3) 前往N作为叶结点, 以类C标志;(4) if attribute_list为空

8、 then(5) 前往N作为叶结点, 标志为D中的多数类; /多数表决(6) 运用Attribute_selection_method (D, attribute_list), 找出“最好的splitting_criterion;(7) 用splitting_criterion标志结点N;(8) if splitting_attribute是离散值的，并且允许多路划分 then /不限于二叉树(9) 从attribute_list中删除分裂属性 ；(10) for splitting_criterion的每个输出 j / 划分元组并对每个分区产生子树(11) 设Dj是D中 满足输出 j 的数据

9、元组的集合； /一个分区(12) if Dj为空 then(13) 加一个树叶到结点N, 标志为D中的多数类 ；(14) else 加一个由Generate_decision_tree (Dj, attribute_list)前往的结点到N； endfor(15) 前往N；14属性选择度量: 信息增益 (ID3/C4.5)符号定义 ：设数据分区D为标志类元组的训练集。假定类标号属性具有m个不同值，定义m个不同类。设Ci,D是D中Ci类元组的集合。选择具有最高信息增益的属性A作为结点N的分裂属性对D中的元组分类所需求的期望信息由下式给出:基于按A划分对D的元组分类所需求的期望信息:按属性A划分的

10、信息增益Pi用|Ci,D|/|D| 估计15属性选择: 信息增益Class P: buys_computer = “yesClass N: buys_computer = “no 意思为14个样本中有5个 “age split-point的元组集合.17属性选择: 增益率 (C4.5)信息增益度量倾向于选择具有大量值的属性C4.5 (ID3的后继) 采用增益率来抑制这个问题 (规范化信息增益)GainRatio(A) = Gain(A)/SplitInfo(A)Ex.gain_ratio(income) = 0.029/1.557 = 0.019具有最大增益率的属性作为分裂属性18基尼指数 (

11、CART)假设一个数据集D包含n个类，那么D的基尼指数定义为 其中 pj 是D中元组属于类 j 的概率, 并用|Ci,D|/|D|估计假设数据集D基于属性 A 被划分成两个子集D1 和 D2, 那么基尼指数定义为不纯度降低:对于离散值属性, 选择该属性产生最小基尼指数的子集作为它的分裂子集；对于延续值属性，选择产生最小基尼指数的点作为分裂点；产生最小基尼指数或最大不纯度降低的属性选为分裂属性19基尼指数的计算例如数据集D 有 9 个buys_computer = “yes的元组和 5 个 “no的元组假设按income属性子集low, medium将数据集划分为D1(10个元组)和D2(4个元

12、组) Ginilow,high 是 0.458; Ginimedium,high 是 0.450. 因此在income的子集 low,medium上划分, 由于 它的基尼指数 最小20过分拟合与树剪枝过分拟合: 树创建时，由于数据中的噪声和离群点，会过分拟合训练数据有很多分枝，一些是由于噪声和离群点导致的异常预测准确率下降两种方法来防止过分拟合先剪枝: 假设划分一个结点后的元组低于预定义阈值，那么提早停顿树的构建选取一个适当的阈值是困难的后剪枝: 由 “完全生长的树剪去子树用回溯方式去除树的一些点Use a set of data different from the training dat

13、a to decide which is the “best pruned tree21分类: 根本概念分类: 根本概念决策树基于规那么分类贝叶斯分类方法提高分类准确率的技术小结22运用IF-THEN 规那么分类以 IF-THEN 规那么的方式表示学习得到的模型R: IF age = youth AND student = yes THEN buys_computer = yes“IF 部分称为规那么前件或前提, “THEN 部分称为规那么的结论在规那么前件，条件由一个或多个用逻辑衔接词AND衔接的属性测试组成；规那么的结论包含一个类预测对于给定的元组，假设规那么前件中的条件都成立，那么规那么

14、覆盖了该元组规那么的评价: 覆盖率和准确率ncovers 表示规那么R覆盖的元组数ncorrect 表示规那么R正确分类的元组数coverage(R) = ncovers /|D| /* D: 训练数据集*/accuracy(R) = ncorrect / ncovers23运用IF-THEN 规那么分类如何运用基于规那么的分类来预测给定元组X的类标号？假设规那么被X满足，那么称该规那么被触发。例如，X=(age=youth, income=medium, student=yes, credit_rating=fair)X满足规那么R，触发该规那么。假设R是独一满足的规那么，那么该规那么激活，

15、前往X的类预测留意，触发并不总意味激活，由于能够有多个规那么被满足假设多个规那么被触发，那么需求处理冲突规模序: 把最高优先权赋予具有“最苛刻要求的被触发的规那么 (即, 具有最多属性测试的)规那么序: 预先确定规那么的优先次序。基于类的序: 按类的普遍性降序排序基于规那么的序 (决策表): 根据规那么质量的度量，规那么被组织成一个优先权列表。最先出如今决策表中的被触发的规那么具有最高优先权，因此激活它的类预测。24age?student?credit rating?40noyesyesyes31.40nofairexcellentyesno例子: 从 buys_computer 决策树提取规

16、那么R1: IF age = young AND student = no THEN buys_computer = noR2: IF age = young AND student = yes THEN buys_computer = yesR3: IF age = mid-age THEN buys_computer = yesR4: IF age = old AND credit_rating = excellent THEN buys_computer = noR5: IF age = old AND credit_rating = fair THEN buys_computer =

17、yes由决策树提取规那么与决策树相比，IF-THEN规那么能够更容易了解，尤其是当决策树非常大时对每条从根到树叶结点的途径创建一个规那么给定途径上的每个分裂准那么的逻辑AND构成规那么的前件(“IF部分); 存放类预测的树叶结点构成规那么的后件(“THEN部分)规那么是互斥的和穷举的25规那么归纳:顺序覆盖算法顺序覆盖算法: 直接从训练集中提取规那么典型的顺序覆盖算法: FOIL, AQ, CN2, RIPPER规那么被顺序地学习, 给定类的每个规那么覆盖该类的许多元组并且希望不覆盖其他类的元组步骤: 一次学习一个规那么每学习一个规那么, 就删除该规那么覆盖的元组在剩下的元组上反复该过程，直到

18、满足终止条件, 例如, 不再有训练元组，或前往规那么的质量低于用户指定的阈值与决策树对比: 决策树归纳是同时学习一组规那么26根本顺序覆盖算法算法：顺序覆盖。学习一组IF-THEN分类规那么。输入： D，类标志元组的数据集合。 Att-vals, 一切属性与它们能够值的集合。输出：IF-THEN规那么的集合。方法：Rule_set=; /学习的规那么集初始为空for每个类c do repeat Rule=Learn_One_Rule (D, Att-vals, c); 从D中删除被Rule覆盖的元组； until 终止条件满足； Rule_set=Rule_set+Rule /将新规那么添加到

19、规那么集endfor前往Rule_set;27如何Learn-One-Rule?从最普通的规那么开场: condition = empty(条件为空)经过采用一种贪婪的深度优先战略添加新的属性选择最能提高规那么质量的属性规那么质量度量: 同时思索覆盖率和准确率Foil-gain (in FOIL & RIPPER): 用下式估计扩展条件而获得的信息偏向于具有高准确率并且覆盖许多正元组的规那么28分类: 根本概念分类: 根本概念决策树基于规那么分类贝叶斯分类方法提高分类准确率的技术小结29贝叶斯定理: 根底贝叶斯定理:X 表示数据元组: 类标号未知H为某种假设，如数据元组X属于某个特定类 C 分

20、类是确定P(H|X) (即后验概率): 在条件X下，H的后验概率，例如，X是一位35岁的顾客，其收入为4万美圆。令H为某种假设，如顾客将购买计算机，那么P(H|X) 反映当我们知道顾客的年龄和收入时，顾客X将购买计算机的概率 。P(H) (先验概率): H的先验概率如, 恣意给定顾客将购买计算机的概率P(X): X的先验概率，如顾客集合中的年龄为35岁并且收入为4万美圆的概率P(X|H): 在条件H下，X的后验概率例如, 知顾客X将购买计算机，该顾客是35岁并且收入为4万美圆的概率30分类就是导出最大后验概率设D是训练元组和它们相关联的类标号的集合。每个元组用一个n维属性向量 X = (x1,

21、 x2, , xn)表示假定有m 个类C1, C2, , Cm.分类法将预测X属于具有最高后验概率的类, 即, 最大的P(Ci|X)。 假设P(Ci|X) 在一切k个类的P(Ck|X) 中最大，那么预测 X 属于类Ci每个类的后验概率可根据以下贝叶斯定理计算得到由于P(X)对一切类为常数，所以只需求最大化31朴素贝叶斯分类简单假定: 属性有条件地相互独立 (即属性之间不存在依赖关系):假设 Ak 是分类属性, 那么P(xk|Ci)是D中属性Ak的值为xk的Ci类的元组数除以D中Ci类的元组数 |Ci, D|假设 Ak 是延续值属性, P(xk|Ci) 通常基于均值 和规范差 的高斯分布计算假定

22、延续值属性服从均值为 、规范差为 的高斯分布，由下式定义32朴素贝叶斯分类Class:C1:buys_computer = yesC2:buys_computer = no待分类数据: X = (age =30, Income = medium,Student = yes,Credit_rating = Fair)33朴素贝叶斯分类: 例子P(Ci): P(buys_computer = “yes) = 9/14 = 0.643 P(buys_computer = “no) = 5/14= 0.357为每个类计算 P(X|Ci) P(age = “=30 | buys_computer = “

23、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_ratin

24、g = “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 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.

25、4 = 0.019P(X|Ci)*P(Ci) : P(X|buys_computer = “yes) * P(buys_computer = “yes) = 0.028 P(X|buys_computer = “no) * P(buys_computer = “no) = 0.007因此, X 属于类(“buys_computer = yes)34防止零概率问题朴素贝叶斯分类预测需求每个条件概率是非零的，否那么，预测概率将会为零例如，假设一个具有1000个元组的数据集, income=low (0), income= medium (990), 和 income = high (10)运用拉普

26、拉斯校准 (或拉普拉斯估计法)每个组元组数加1Prob(income = low) = 1/1003Prob(income = medium) = 991/1003Prob(income = high) = 11/1003“校准的概率估计与对应的“未校准的估计很接近35朴素贝叶斯分类: 评价优点易于实施大部分情况下可以获得好的结果缺陷假设: 类条件独立，因此损失准确性实践中, 属性之间经常存在依赖性属性之间存在依赖的情况不能经过朴素贝叶斯分类建模怎样处置这些依赖性? 贝叶斯信心网络36分类: 根本概念分类: 根本概念决策树基于规那么分类贝叶斯分类方法提高分类准确率的技术小结组合方法: 提高分类准确率组合方法把k个学习得到的模型, M1, M2, , Mk, 组合在一同，旨在创建 一个改良的复合分类模型M*流行的组合方法装袋: 在一组分类器上平均预测提升: 基于一组分类器的加权表决37给定一个待分类元组X，它搜集由基分类器前往的类标号预测，并输出占多数的类。装袋: 自助聚集类似: 基于多个医生多数表决的诊断训练每次迭代i，d个元组的训练集Di采用有放回抽样从原始数据集D抽取从每个训练集Di学习一个分类器模型Mi分类: 对一个未知元组X分类每个分类器Mi 前往它的类预测装袋分类器M* 统计得票，并将得票最高的类赋予X预测: 经过取给定元组的每个预测的