预备知识：
信息熵：信息量的期望，反映随机变量的不确定性
H(X)=-∑x->Xp(x)log(p(x))
通俗的理解信息熵
设类别C={c1,c2,...ck) 记分类标记ck的样本数为|ck|,样本为D,样本总数|D|
H(D)=-∑|ck|/|D|log(|ck|/|D|) 其中k为类别标记数
条件熵定义：
H(X|Y)=∑p(x)H(X|Y=y)
通俗理解条件熵
设类别C={c1,c2,...ck) 记分类标记为ck的样本数为|ck|,样本为D,样本总数|D| A为特征集合 Di为按特征取值将D划分为若干个非空子集的第i个集合 |Dik|表示第i个集合分类标记为ck的样本数
H(D|A)=∑i=1 to n|ci|/|D|H(Di) 其中n为特征的取值数量
=∑i=1 to n|ci|/|D|∑k=1..K|Dik|/|Di|log(|Dik|/|Di|)
信息增益：
G(X,Y)=H(X)-H(X|Y)
信息增益比：
Gr(X,Y)=G(X,Y)/H(X)
ID3算法
该算法通过信息增益对特征进行选择
输入：训练集D,特征集A
输出:决策树T
(1) 若D中的样本属于同一类ck,则将ck作为该节点的类标记，返回T
(2) 若A=空集,则将D中所含样本数最多的类别作为该节点的类标记，放回T
(3)否则 计算所有特征对D的信息增益，选择信息增益最大的特征Am作为当前节点
(4)按Am的取值将D划分为若干个非空的子集Di,以Di为训练集，A-Am为特征集合，递归建立决策树
C4.5算法
ID3算法对取值较多的特征有偏好性，C4.5对这一问题进行了修正
C4.5通过信息增益比对特征进行选择
输入：训练集D,特征集A
输出:决策树T
(1) 若D中的样本属于同一类ck,则将ck作为该节点的类标记，返回T
(2) 若A=空集,则将D中所含样本数最多的类别作为该节点的类标记，放回T
(3)否则 计算所有特征对D的信息增益比，选择信息增益比最大的特征Am作为当前节点
(4)按Am的取值将D划分为若干个非空的子集Di,以Di为训练集，A-Am为特征集合，递归建立决策树