电子政务服务网站建设,温州门户网站,建立网站项目计划书模板,实时新闻在哪里能查到1. 熵
物理学上#xff0c;熵 Entropy 是“混乱”程度的量度。 系统越有序#xff0c;熵值越低#xff1b;系统越混乱或者分散#xff0c;熵值越⾼。
1948年⾹农提出了信息熵#xff08;Entropy#xff09;的概念。 从信息的完整性上进⾏的描述#xff1a;当系统的有序…1. 熵
物理学上熵 Entropy 是“混乱”程度的量度。 系统越有序熵值越低系统越混乱或者分散熵值越⾼。
1948年⾹农提出了信息熵Entropy的概念。 从信息的完整性上进⾏的描述当系统的有序状态⼀致时数据越集中的地⽅熵值越⼩数据
越分散的地⽅熵值越⼤。 从信息的有序性上进⾏的描述当数据量⼀致时系统越有序熵值越低系统越混乱或者分
散熵值越⾼。
信息熵 (information entropy)是度量样本集合纯度最常⽤的⼀种指标。 假定当前样本集合 D 中第
k 类样本所占的⽐例为 pk (k 1, 2,. . . , |y|) D为样本的所有数量Ck 为第k类样本
的数量。 则 D 的信息熵定义为log是以2为底lg是以10为底
其中Ent(D) 的值越⼩则 D 的纯度越⾼。
例子假设我们没有看世界杯的⽐赛但是想知道哪⽀球队会是冠军 我们只能猜测某⽀球队是
或不是冠军然后观众⽤对或不对来回答 我们想要猜测次数尽可能少⽤什么⽅法
答案 ⼆分法。
假如有 16 ⽀球队分别编号先问是否在 1-8 之间如果是就继续问是否在 1-4 之间 以此类
推直到最后判断出冠军球队是哪⽀。 如果球队数量是 16我们需要问 4 次来得到最后的答案。
那么世界冠军这条消息的信息熵就是 4。
那么信息熵等于4是如何进⾏计算的呢
Ent(D) -p1 * logp1 p2 * logp2 ... p16 * logp16其中 p1, ..., p16 分别是这 16 ⽀球队
夺冠的概率。 当每⽀球队夺冠概率相等都是 1/16 的时侯Ent(D) -16 * 1/16 * log1/16 4
每个事件概率相同时熵最⼤这件事越不确定。
2. 信息增益
信息增益以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性熵越⼤样本
的不确定性就越⼤。 因此可以使⽤划分前后集合熵的差值来衡量使⽤当前特征对于样本集合D划分
效果的好坏。
信息增益 entroy(前) - entroy(后)
信息增益表示得知特征X的信息⽽使得类Y的信息熵减少的程度。
假定离散属性a有 V 个可能的取值
若使⽤ a 来对样本集 D 进⾏划分则会产⽣ V 个分⽀结点其中第v个分⽀结点包含了 D 中所有
在属性 a上取值为 av 的样本记为 D。我们可根据前⾯给出的信息熵公式计算出 D 的信息熵再
考虑到不同的分⽀结点所包含的样本数不同给分⽀结点赋予权重
即样本数越多的分⽀结点的影响越⼤于是可计算出⽤属性 a 对样本集 D 进⾏划分所获得的信息
增益 (information gain)。
其中特征a对训练数据集 D 的信息增益 Gain(D,a)定义为集合 D 的信息熵 Ent(D) 与给定特征 a
条件下 D 的信息条件熵 Ent(D∣a) 之差即公式为 公式的详细解释 信息熵的计算 条件熵的计算 其中Dv 表示 a 属性中第 v 个分⽀节点包含的样本数
Ckv 表示 a 属性中第 v 个分⽀节点包含的样本数中第 k 个类别下包含的样本数
⼀般⽽⾔信息增益越⼤则意味着使⽤属性 a 来进⾏划分所获得的纯度提升越⼤。因此我们
可⽤信息增益来进⾏决策树的划分属性选择著名的 ID3 决策树学习算法 [Quinlan 1986] 就是
以信息增益为准则来选择划分属性。 其中ID3 名字中的 ID 是 Iterative Dichotomiser (迭代⼆分
器)的简称。
比如第⼀列为论坛号码第⼆列为性别第三列为活跃度最后⼀列⽤户是否流失。 我们要解
决⼀个问题性别和活跃度两个特征哪个对⽤户流失影响更⼤ 通过计算信息增益可以解决这个问题统计上右表信息。其中Positive为正样本已流失
Negative为负样本未流失下⾯的数值为不同划分下对应的⼈数。 可得到三个熵
①计算类别信息熵整体熵 ②性别属性的信息熵 ③性别的信息增益 ④活跃度的信息熵 ⑤活跃度的信息增益 活跃度的信息增益⽐性别的信息增益⼤也就是说活跃度对⽤户流失的影响⽐性别⼤。在做特
征选择或者数据分析的时候应该重点考察活跃度这个指标。
3. 信息增益率
在上⾯的介绍中我们有意忽略了编号这⼀列。若把编号也作为⼀个候选划分属性则根据信
息增益公式可计算出它的信息增益为 0.9182远⼤于其他候选划分属性。 计算每个属性的信息熵
过程中发现该属性的值为0也就是其信息增益为0.9182。但是很明显这么分类最后出现的结
果不具有泛化效果⽆法对新样本进⾏有效预测。
实际上信息增益准则对可取值数⽬较多的属性有所偏好为减少这种偏好可能带来的不利影响
著名的 C4.5 决策树算法不直接使⽤信息增益⽽是使⽤增益率 (gain ratio) 来选择最优划分属
性。 增益率增益率是⽤前⾯的信息增益 Gain(D, a) 和属性 a 对应的固有值(intrinsic value) 的
⽐值来共同定义的。 属性 a 的可能取值数⽬越多(即 V 越⼤)则 IV(a) 的值通常会越⼤。
⽤分裂信息度量来考虑某种属性进⾏分裂时分⽀的数量信息和尺⼨信息把这些信息称为属性的内
在信息 instrisic information。信息增益率⽤信息增益/内在信息会导致属性的重要性随着内在
信息的增⼤⽽减⼩也就是说如果这个属性本身不确定性就很⼤那我就越不倾向于选取它
这样算是对单纯⽤信息增益有所补偿。
上面的例子中计算属性分裂信息度量 计算信息增益率 活跃度的信息增益率更⾼⼀些所以在构建决策树的时候优先选择通过这种⽅式在选取节点的
过程中我们可以降低取值较多的属性的选取偏好。
例子2第⼀列为天⽓第⼆列为温度第三列为湿度第四列为⻛速最后⼀列该活动是否进
⾏。根据下⾯表格数据判断在对应天⽓下活动是否会进⾏ 该数据集有四个属性属性集合A{ 天⽓温度湿度⻛速} 类别标签有两个类别集合L{进
⾏取消}。
①计算类别信息熵。类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概
念熵越⼤不确定性就越⼤把事情搞清楚所需要的信息量就越多。 ②计算每个属性的信息熵。每个属性的信息熵相当于⼀种条件熵。表示的是在某种属性的条件下
各种类别出现的不确定性之和。属性的信息熵越⼤表示这个属性中拥有的样本类别越不“纯”。 ③计算信息增益。信息增益 熵 - 条件熵在这⾥就是类别信息熵 - 属性信息熵它表示的是信息
不确定性减少的程度。如果⼀个属性的信息增益越⼤就表示⽤这个属性进⾏样本划分可以更好的
减少划分后样本的不确定性当然选择该属性就可以更快更好地完成分类⽬标。 信息增益就是
ID3算法的特征选择指标。 假设把上⾯表格1的数据前⾯添加⼀列为编号取值(1--14)。若把编号也作为⼀个候选划分属
性则根据前⾯步骤计算每个属性的信息熵过程中该属性的值为0也就是其信息增益为
0.940。但是很明显这么分类最后出现的结果不具有泛化效果。此时根据信息增益就⽆法选择出
有效分类特征。所以C4.5选择使⽤信息增益率对ID3进⾏改进。
④计算属性分裂信息度量。⽤分裂信息度量来考虑某种属性进⾏分裂时分⽀的数量信息和尺⼨信
息把这些信息称为属性的内在信息 instrisic information。信息增益率⽤信息增益/内在信息
会导致属性的重要性随着内在信息的增⼤⽽减⼩也就是说如果这个属性本身不确定性就很⼤
那就越不倾向于选取它这样算是对单纯⽤信息增益有所补偿。 ⑤计算信息增益率。 天⽓的信息增益率最⾼选择天⽓为分裂属性。发现分裂了之后天⽓是“阴”的条件下类别是”纯
“的所以把它定义为叶⼦节点选择不“纯”的结点继续分裂。
C4.5的算法流程
while(当前节点不纯)1.计算当前节点的类别熵(以类别取值计算)2.计算当前阶段的属性熵(按照属性取值吓得类别取值计算)3.计算信息增益4.计算各个属性的分裂信息度量5.计算各个属性的信息增益率
end while
当前阶段设置为叶⼦节点
C4.5的优点
①⽤信息增益率来选择属性克服了⽤信息增益来选择属性时偏向选择值多的属性的不⾜。
②采⽤了⼀种后剪枝⽅法避免树的⾼度⽆节制的增⻓避免过度拟合数据
③对于缺失值的处理 在某些情况下可供使⽤的数据可能缺少某些属性的值。假如〈xc(x)〉是
样本集S中的⼀个训练实例但是其属性A 的值A(x)未知。 处理缺少属性值的⼀种策略是赋给它结
点n所对应的训练实例中该属性的最常⻅值 另外⼀种更复杂的策略是为A的每个可能值赋予⼀个
概率C4.5就是使⽤这种⽅法处理缺少的属性值。
4. 基尼值和基尼指数
CART 决策树 [Breiman et al., 1984] 使⽤基尼指数Gini index来选择划分属性。CART 是
Classification and Regression Tree的简称这是⼀种著名的决策树学习算法分类和回归任务都
可⽤基尼值GiniD从数据集D中随机抽取两个样本其类别标记不⼀致的概率。GiniD值
越⼩数据集D的纯度越⾼。 数据集 D 的纯度可⽤基尼值来度量 D为样本的所有数量Ck 为第 k 类样本的数量。
基尼指数Gini_indexD⼀般选择使划分后基尼系数最⼩的属性作为最优化分属性。 1. 对数据集⾮序列标号属性{是否有房婚姻状况年收⼊}分别计算它们的Gini指数取Gini指数
最⼩的属性作为决策树的根节点属性。
2. 根节点的Gini值为 3. 当根据是否有房来进⾏划分时Gini指数计算过程为 4. 若按婚姻状况属性来划分属性婚姻状况有三个可能的取值{marriedsingledivorced}分别
计算划分后的Gini系数增益。 {married} | {single,divorced} {single} | {married,divorced} {divorced} |
{single,married} 对⽐计算结果根据婚姻状况属性来划分根节点时取Gini指数最⼩的分组作为划分结果即:
{married} | {single,divorced} 。
5. 同理可得年收⼊Gini 对于年收⼊属性为数值型属性⾸先需要对数据按升序排序然后从⼩
到⼤依次⽤相邻值的中间值作为分隔将样本划分为两组。例如当⾯对年收⼊为60和70这两个值
时我们算得其中间值为65。以中间值65作为分割点求出Gini指数。 根据计算知道三个属性划分根节点的指数最⼩的有两个年收⼊属性和婚姻状况他们的指数都
为0.3。此时选取⾸先出现的属性{married}作为第⼀次划分。
6. 接下来采⽤同样的⽅法分别计算剩下属性其中根节点的Gini系数为此时是否拖⽋贷款的
各有3个records。 7. 对于是否有房属性可得 8. 对于年收⼊属性则有 经过如上流程构建的决策树如下图 CART的算法流程
while(当前节点不纯)1.遍历每个变量的每⼀种分割⽅式找到最好的分割点2.分割成两个节点N1和N2
end while
每个节点⾜够“纯”为⽌
