ID3算法（含实例）
（1）ID3算法简介
（2）ID3算法节点分裂规则
（3）ID3算法实例
（4）剪枝
------------------------------------------------------------------------------------------------------------------------- 一、简介1、信息熵Entropy
其中为第i个类别的概率，S是样例集合
信息熵越大，样本越混乱；信息熵越小，样本越纯净。
2、期望信息
设特征A具有v个不同的类别，其样本个数分别记为
E(A)特征A的期望信息，为特征A的第j个类别的数量占特征A所有类别的概率，为特征A下第j个类别中占样例集合S不同类别的概率
3、信息增益
为特征A的信息增益
信息熵越小，信息增益越大，样本越纯净
选择信息增益最大的特征作为分裂标准
二、实例1、样本（特征必须离散变量，支持多特征、多分类）
1024个样本，4个特征，2个分类
计数年龄收入学生信誉是否购买64青高否良否64青高否优否128中高否良买60老中否良买64老低是良买64老低是优否64中低是优买128青中否良否64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买64老中否优否2、计算信息熵
3、计算特征A的信息熵
假设以年龄为例：
分为青年：384/0.375（样本/概率）、中年：256/0.25（样本/概率）、老年：384/0.375（样本/概率）
以年龄为特征的熵为：
H(S|A)=0.375∗H(S|A1)+0.25∗H(S|A2)+0.375∗H(S|A3)" role="presentation">H(S|A)=0.375∗H(S|A1)+0.25∗H(S|A2)+0.375∗H(S|A3)
青年：128/256（买/不买），概率为1/3和2/3（买/不买）
![H(S|A_{1})=-[frac{1}{3}*log(frac{1}{3})+frac{2}{3}*log(frac{2}{3})]=0.9149](http://img.mcbbbk.com/upload/news/2024/0920/photos/middle/20240920215403_5vbh_lp1cv1mk.jpg)
中年：256/0（买/不买），概率为1和0（买/不买）
老年：256/128（买/不买），概率为2/3和1/3（买/不买）
![H(S|A_{3})=-[frac{2}{3}*log(frac{2}{3})+frac{1}{3}*log(frac{1}{3})]=0.9149](http://img.mcbbbk.com/upload/news/2024/0920/photos/middle/20240920215403_5vbh_5u23ovt4.jpg)
故得到以年龄为特征的熵（平均信息期望/条件熵）为
(H(S|A) =0.375*H(S|A_{1})+0.25*H(S|A_{2})+0.375*H(S|A_{3})=0.6862)
年龄特征的信息增益为：
同理可得
收入：
学生：
信誉：
可以看出，‘年龄’的信息增益最大，因此选择‘年龄’作为节点来划分。
按此方法，直至叶节点为’纯‘的结束。
三、剪枝树的剪枝包括预剪枝和后剪枝，通过提前停止树的构造进行剪枝的方法称为预剪枝，后剪枝是首先构造完整的决策树，然后把置信度不够节点子树替代为叶子节点的过程。
预剪枝判断停止树的生长可以归纳为以下几种：
1、树的高度限制：设定树的高度最大值，当达到限定值时，停止树的生长；
2、训练样本限制：对一个拥有较少训练样本的节点进行分裂时容易出现过拟合现象，因此设定样本量阀值，当样本量少于阀值时停止生长；
3、系统性能增益：当属性的信息增益小于某个指定的阀值时停止增长。
相对而言预剪枝比较简单，在实际的运用中运用最广的还是后剪枝。
后剪枝算法主要有以下几类：
1、降低错误剪枝REP(Reduced Error Pruning)；
2、悲观错误剪枝PER(Pessimistic Error Pruning)；
3、基于错误剪枝EBP(Error-Based Pruning)；
4、代价-复杂度剪枝CCP(Cost-Complexity Pruning)；
5、最小错误剪枝MEP(Minimun Error Pruning)
以上算法的理论介绍详见：
http://wenku.baidu.com/view/415c3cc19ec3d5bbfd0a7464.html?re=view
四、总结1、ID3算法的流程
（1）自上而下贪婪搜索
（2）遍历所有的属性，按照信息增益最大的属性进行分裂
（3）根据分裂属性划分样本
（4）重复上述流程，直至满足条件结束
2、ID3算法的特点
（1）上述过程可以看出，ID3算法倾向于选择属性值较多的属性，有些时候不能提供有价值的信息
（2）贪婪性以及奥姆剃刀原理（尽量用较少的东西做更多的事）
（3）不适用于连续变量
（4）只能用于分类
注：以上内容属个人理解，学艺不精，请各位大神多多指教
相关知识
Python3 实例
你还能说出哪些生物影响和适应环境的实例
沙盘分析实例解析
城市的犬主与宠物设计：如何满足宠物的需求
城市的犬主与宠物设计：如何满足宠物的需求1.背景介绍 城市的犬主与宠物设计：如何满足宠物的需求 随着城市的发展和人口的增
动物语音识别用什么算法
统计学习理论及应用
阿里这套算法，让1亿只猫惊呆了
实例—具有心理关怀和情绪关怀的宠物产品设计
钮扣宠物定位器新算法(4.0)发布啦
网址: ID3算法（含实例） https://m.mcbbbk.com/newsview195953.html
| 上一篇: 决策树生成的决策规则转化成正则表 |
下一篇: 宠物新消费决策者商务论坛——PI |
