数据挖掘之决策树算法ID3算法的相关原理

ID3决策树:针对属性选择问题，是决策树算法中最为典型和最具影响力的决策树算法。
ID3决策树算法使用信息增益度作为选择测试属性。


其中p(ai) 表示ai 发生的概率。
假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个
发生，则其平均的信息量可如下度量：

对数底数可以为任何数，不同的取值对应了熵的不同单位。

通常取2，并规定当p(ai)=0时   =0

Entropy（S，A）=∑（|Sv|/|S|）* Entropy（Sv）公式2 

以去不去打羽毛球为例子
A:属性：outlook
S:训练样本集合
∑：属性A 的所有可能的取值:sunny ,overcast, rainy
Sv是属性A有v值的S子集:包含sunny的子集
|Sv|  Sv中元素的个数   
|S|  S中元素的个数

信息增益Gain的值：（决策属性的熵）—（条件属性的熵）
Entropy（Sv）——> 获得该条件属性的熵
假设有一个属性包含两种值V1/V2
P1 = V1/(V1+V2)
P2 = V2/(V1+V2)
I(p1,p2) = p1*log2(1/p1)+p2*log2(1/p2) = - (p1*log2(p1)+p2*log2(p2) )
Entropy （Sv）= ∑ I(p1,p2)*[(p1+p2)/(Alltotal)]----->求出来是平均期望

注：决策属性求熵的时候,因为决策属性是全局的所有的数据都会有的信息，所以说决策属性求熵的话不必求期望，直接求出来的熵就等于期望了。

信息增益Gain的值：（决策属性的熵）—（条件属性的熵）

要求所有属性的信息增益的值然后对这些值进行比较，取最大的信息增益值对应的信息的属性作为分支节点，往下的话继续进行如上的操作。
百度百科：
ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。以下是一些信息论的基本概念：
定义1：若存在n个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为-Log2(1/n)
定义2：若有n个消息，其给定概率分布为P=(p1,p2…pn)，则由该分布传递的信息量称为P的熵
定义3：若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck，则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)
定义4：若我们先根据非类别属性X的值将T分成集合T1,T2…Tn，则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到，即Info(Ti)的加权平均值为：
Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))
定义5：
信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为：
Gain(X, T)=Info(T)-Info(X, T)
ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本.

注：
ID3算法是一种经典的决策树学习算法，由Quinlan于1979年
提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节
点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值
变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节
点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于
同一类。
 变量如表1所示，自变量为年龄、职业、性别；因变量为结果（吃大排档的频率）。
                            表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 =count(A1j)/count(Aj)=0、
p3j =count(A3j)/count(Aj)=0；
 (p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )→0；
    具体说来:
LIM(p2j→1) p2j*log2(p2j) →LIM(p2j→1) 1*0→0
LIM(p1j→0) p1j*log2(p1j) →LIM(p1j→0) log2(p1j) /(1/ p1j) →LIM(p1j→0) p1j* log2(e) →0
LIM(p3j→0) p1j*log2(p3j) →LIM(p3j→0) log2(p3j) /(1/ p3j) →LIM(p3j→0) p3j* log2(e) →0
(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )→0+0+0=0
    可见，如果每个年龄段都对结果有确定影响，那么各年龄段的不加权的期望信息(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )就很小，从而E(A)就很小甚至趋近0了；
4、自变量的期望信息计算
4.1、E（A）计算
    从表4看，有两个年龄段对结果产生了不同影响，计算如下：
E(30-40)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))
       =3/16*(-(2/3* log2(2/3) +1/3*log2(1/3) ))
       =0.172
E(20-30)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))
       =5/16*(-(1/5* log2(1/5)+3/5* log2(3/5) +1/5*log2(1/5) ))
       =0.428
    最终算得：
E(A)= E(30-40)+ E(20-30)=0.172+0.428=0.6
  
                        表4    年龄信息表
年龄A	结果
60-70	从不
60-70	从不
60-70	从不
40-50	从不
40-50	从不
30-40	经常
30-40	偶尔
30-40	偶尔
20以下	偶尔
20以下	偶尔
20以下	偶尔
20-30	偶尔
20-30	偶尔
20-30	从不
20-30	经常
20-30	偶尔
5、信息增益的计算
年龄变量的信息增益计算为：
Gain(A)=E(结果)-E(A)= 1.406-0.6=0.806
同理可以计算Gain(B)、Gain(C)；
注：信息增益大说明较好的降低了划分前的无序程度，因此决策树的第一次划分就看哪个变量的信息增益大就按哪个划分；
6、划分过程
如果是像上例那样变量选项比较少的决策树来讲，假设年龄变量的信息增益最大，那么第一部划分就是：
40-70岁      从不去光顾
20岁以下     偶尔
20-30岁      数据再按照职业和性别计算信息增益找出规则
30-40岁      数据再按照职业和性别计算信息增益找出规则
实际划分是按分割阈值的标准：
A、数值型变量——对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。
B、分类型变量——列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。
注两个问题：根节点一定要产生两个子集吗，要是产生三个子集、四个子集呢，产生多少子集有什么标准呢？我猜测是不是多个子集之间的结果两两差异显著就可以继续进行拆分，如果新的子集不能和原来任一子集的结果都有显著差异就停止划分呢？如何构建这个阈值的统计量呢？
7、划分停止的标准
    满足以下一个即停止生长。
（1） 节点达到完全纯性；
（2） 数树的深度达到用户指定的深度；
（3） 节点中样本的个数少于用户指定的个数；
（4） 异质性指标下降的最大幅度小于用户指定的幅度。
剪枝：完整的决策树对训练样本特征的描述可能“过于精确”（受噪声数据的影响），缺少了一般代表性而无法较好的用对新数据做分类预测，出现 ”过度拟合“。
——移去对树的精度影响不大的划分。使用 成本复杂度方法，即同时度量错分风险和树的复杂程度，使二者越小越好。
剪枝方式：
A、 预修剪（prepruning）：停止生长策略
B、后修剪（postpruning）：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。