大数据分析之分类算法.pdf

⼤数据分析之分类算法 数据分析之决策树ID3算法 什么是分类算法？ 分类算法跟之前的聚类都是让不同对象个体划分到不同的组中的。但是分类不同之处在于类别在运算之前就已经是确定的。 分类是根据训练数据集合，结合某种分类算法，⽐如这篇讲的ID3算法来⽣成最终的分类规则，这样当提供⼀个对象的时候我们可以根据它 们的特征将其划分到某个分组中。 决策树ID3算法是分类中的经典算法，决策树的每⼀层节点依照某⼀确定程度⽐较⾼的属性向下分⼦节点，每个⼦节点在根据其他确定程度 相对较⾼的属性进⾏划分，直到 ⽣成⼀个能完美分类训练样例的决策树或者满⾜某个分类终⽌条件为⽌。 术语定义： ⾃信息量：设信源X发出a的概率p(a),在收到符号a之前，收信者对a的不确定性定义为a的⾃信息量I(a)=-logp(a)。 信息熵：⾃信息量只能反映符号的不确定性，⽽信息熵⽤来度量整个信源整体的不确定性，定义为：H(X)= 求和(p(ai) I(ai)) 条件熵：设信源为X，收信者收到信息Y，⽤条件熵H(X"Y)来描述收信者收到Y后X的不确定性的估计。 平均互信息量：⽤平均互信息量来表⽰信息Y所能提供的关于X的信息量的⼤⼩。 互信息量I(X"Y)=H(X)-H(X"Y) 下边的ID3算法就是⽤到了每⼀个属性对分类的信息增益⼤⼩来决定属性所在的层次，信息增益越⼤，则越 应该先作为分类依据。 ID3算法步骤 a.对当前例⼦集合，计算属性的信息增益； b.选择信息增益最⼤的属性Ai(关于信息增益后⾯会有详细叙述) c.把在Ai处取值相同的例⼦归于同于⼦集，Ai取⼏个值就得⼏个⼦集 d.对依次对每种取值情况下的⼦集,递归调⽤建树算法，即返回a， e.若⼦集只含有单个属性，则分⽀为叶⼦节点，判断其属性值并标上相应的符号，然后返回调⽤处，或者树达到规定的深度，或者⼦集所有 元素都属于⼀个分类都结束。 举例分析 世界杯期间我和同学⼀起去吃了⼏回⼤排档，对那种边凑热闹边看球的氛围感觉很不错，但虽然每个夏天我都会凑⼏回这种热闹，但肯定并 不是所有⼈都喜欢凑这种热闹的，⽽应⽤决策树算法则能有效发现哪些⼈愿意去，哪些⼈偶尔会去，哪些⼈从不愿意去； 变量如表1所⽰，⾃变量为年龄、职业、性别；因变量为结果（吃⼤排档的频率）。 年龄A 职业B 性别C 结果 20-30 学⽣ 男 偶尔 30-40 ⼯⼈ 男 经常 40-50 教师 ⼥ 从不 20-30 ⼯⼈ ⼥ 偶尔 60-70 教师 男 从不 40-50 ⼯⼈ ⼥ 从不 30-40 教师 男 偶尔 20-30 学⽣ ⼥ 从不 20以下 学⽣ 男 偶尔 20以下 ⼯⼈ ⼥ 偶尔 20-30 ⼯⼈ 男 经常 20以下 学⽣ 男 偶尔 20-30 教师 男 偶尔 60-70 教师 ⼥ 从不 30-40 ⼯⼈ ⼥ 偶尔 60-70 ⼯⼈ 男 从不 计算过程： 1、⾸先计算结果选项出现的频率： 表2 结果频率表 从不p1 经常p2 偶尔p3 0.375 0.125 0.5 2、计算因变量的期望信息： E(结果)=-(p1*log2(p1)+p2*log2(p2)+p3*log2(p3) ) =-(0.375*log2(0.375)+0.125*log2(0.125)+0.5*log2(0.5) ) =1.406 注：这⾥Pi对应上⾯的频率 3、计算⾃变量的期望信息(以年龄A为例)： E(A)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )) 3.1公式说明： Count(Aj):年龄A第j个选项个数； j是下⾯表3五个选项任⼀ 表3 年龄记录数量表 选项 20-30 20以下 30-40 40-50 60-70 数量 5 3 3 2 3 Count(A):年龄总记录数 p1j =count(A1j)/count(Aj) :年龄A第j个选项在结果中选择了"从不"的个数占年龄A第j个选项个数的⽐例； p2j =count(A2j)/count(Aj) :年龄A第j个选项在结果中选择了"偶尔"的个数占年龄A第j个选项个数的⽐例； p3j =count(A3j)/count(Aj) :年龄A第j个选项在结果中选择了"经常"的个数占年龄A第j个选项个数的⽐例； 3.2公式分析 在决策树中⾃变量是否显著影响因变量的判定标准由⾃变量选项的不同能否导致因变量结果的不同决定，举例来说如果⽼年⼈都从不去⼤排 档，中年⼈都经常去，⽽少年都偶尔去，那么年龄因素肯定是决定是否吃⼤排档的主要因素； 按照假设，即不同年龄段会对结果产⽣确定的影响，以表3年龄在20以下的3个⼈为例，假设他们都在结果中选择了"偶尔"选项，此时: p2j =count(A2j)/count(Aj)=1， p1j =co