决策树

决策树分类，从根节点开始，对实例的某一个特征进行测试，根据测试结果分配到其自己点，这时每个子节点对应一个特征值。如此重复递归，直到到达叶子节点。

决策树学习算法包括特征选择，决策树生成和剪枝。

特征选择 决定用哪个特征划分特征空间

熵 表示产量的不确定性的度量。

H(X)=-£pi*log(pi)

熵值越大不确定性越大

信息增益

表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

集合D的经验熵H(D)与特征A在条件D下的经验熵H(D|A)之差，即

g(D,A)=H(D)-H(D|A)

常用的算法有ID3,C4.5,CART

ID3,C4.5的区别

C4.5使用信息增益比选择特征，ID3使用信息增益选择特征。