分类算法大数据.pptVIP

计算属性Credit_Rating的熵E(CR)：fair（属性值1）有3个，都买，即属于类Yes或1，excellent（属性值2）有2个，属于类No或2。 决策树构造：一个例子 Gain(CR)=I(s1,s2)-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 =30 40 no yes yes 30..40 3个：都买 2个：都不买 所以我们有决策树： age? overcast student? credit rating? no yes fair excellent =30 40 no no yes yes yes 30..40 决策树构造：一个例子 所有样本已经被分类，算法停止，我们得到最终的决策树如下： age? student? credit rating? no yes fair excellent =30 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(Ci|X): 给定观测数据样本X，确定X属于类Ci的概率。 P(Ci): 类Ci的先验概率(prior probability) (即在我们观测任何数据之前的初始概率, 它反映了背景知识) P(X): 样本数据被观测的概率。 P(X|Ci): 在属于类Ci的前提下，观测到样本X的概率。 贝叶斯定理 给定训练集X, X属于类Ci的后验概率(posteriori probability), P(C|X) 遵守如下贝叶斯定理 MAP (Maximum a posteriori，极大后验) 假设 实际应用的困难: 需要许多概率的初始知识, 需要较多的计算时间。 简化：朴素贝叶斯分类器 一个简化假设: 属性之间是条件独立的: 一旦知道了概率P(X|Ci), 把X赋予使得 P(X|Ci)*P(Ci)具有极大值的类Ci。 一个例子 类: C1:buys_computer= ‘yes’ C2:buys_computer= ‘no’ 数据样本 X =(age=30, Income=medium, Student=yes Credit_rating= Fair) 一个例子 对每一个类，计算P(X|Ci) 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_ratin