决策树
- 故事一则 某母亲为女儿找相亲对象： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 一颗决策树应运而生：
- 决策树是一个分类模型，是运用已有资料训练模型，然后运用到未知类别的事物身上，从而确定该事物的类别。
- 就像上面故事中未曾谋面的男主人公，虽然见或不见，他就在那里，不悲不喜，但他到底属于的哪一类，就需要用上图所示的决策树来决定。
- 决策树的精神是要将目标属性的混乱程度降到最低。。。该怎么降，这就涉及到了提及N次的信息论中的 信息增益 小朋友。
- 具体思想，是先求得整体的信息熵，然后求得每一个属性在对整体进行划分后的信息熵， 两者相减（H(u)-H(u|v)），最大者对应的属性就是划分能力最好的属性。 因为 若结果最大，则说明H(u|v)在所有后验熵中最小，也就是对应的系统最有序，也就是划分程度最高，不选它，选谁，是不是。。。。。
- 决策示例：
- 最终的类别是Play或是No，影响决定的因素有：天气、气温、湿度、风。
- 怎样进行决策呢：
- 类别：P N 对应域 u1 、u2
- 属性： 天气A1 :晴、多云、雨； 气温A2:冷、适中、热； 湿度A3:高、正常：风A4:有、无。
- 先验概率：P(u1)=9/14 —|— P(u2)=5/14
- 先验熵：H（u）=-9/14*log(9/14)-5/14*log(5/14)=0.94
- 对天气A1，晴v1、多云v2、雨v3
- p(v1)=5/14、p(v2)=4/14、p(v3)=5/14
- p(u1|v1)=2/5、p(u2|v1)=3/5
- H(u|v1)=-2/5*log(2/5)-3/5*log(3/5)=0.97、同理H(u|v2)=0、H(u|v3)=0.97
- 条件熵：对A1 H(u|V)=p(vi)*H(u|vi)=0.69
- 信息增益：I(A1)=H(u)=H(u|V)=0.25、同理I(A2)=0.03、I(A3)=0.15、I(A4)=0.05
- 其中A1的信息增益最大，所以选取A1为根节点的分裂属性，将其三个取值作为三个分支
- 上述过程为ID3算法的具体决策过程片段，ID4.5是对ID3算法的改进，最主要的改进是用 信息增益率 来代替 信息增益。来克服ID3中总是偏向值比较多的属性。
- 信息增益率：
- 其中Gain(S,A)与ID3算法中的信息增益相同，而分裂信息 SplitInfo(S,A)代表了按照属性A分裂样本集S的广度和均匀性
- 具体解释：
- 其中，S1到Sc是c个不同值的属性A分割S而形成的c个样本子集。如按照属性A把S集（含30个用例）分成了10个用例和20个用例两个集合则SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3)
- ID4.5的有点，可以处理连续的属性值，只需输入一个参数（0.25置信度）用于剪枝处理
- 剪枝：
- 其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。
- 通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计，从而决定是否真的剪枝
- 粗浅研究，进一步探讨和算法实现容日后再续（ＣＳＤＮ同步更新）
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2015-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
