概念理解

熵:

条件熵:

$H(y|A)$H(y∣A) : A 是特征，y是目标或者分类，“条件”可以理解为 A对y的限制，假如：feature A有m个featureValue, $H(y|A)$H(y∣A) 就是在取feature A有m个featureValue的值下，y的不确定和。$H(y|A)$H(y∣A)理解为y被A限制后的不确定性，A对y分类的影响

信息增益，互信息:

$g(y,A) = H(y) - H(y|A)$g(y,A)=H(y)−H(y∣A)
可以看成条件熵的相反，这个可以看成A对y分类的影响，简单理解就是y在引入A之后的不确定度。

假如以$g(y,A)$g(y,A)作为y分类的标准，那么y就选择$g(y,A)$g(y,A)的feature A, 那么这种策略就倾向于选择featureValue个数m越多的feature A，直观一点就是分类越多，y的确定性就会增加。

信息增益比

假如一直选择featureValue个数m越多的feature ，决策树就会成为一个又胖又矮的树，不管在哪里矮胖肯定不受欢迎，我们喜欢高瘦的，但是又不能太高，我们需要一个具有美感的$x$x叉树。
在此引入了对m的惩罚，信息增益比:
$g_R(y,A) = g(y,A) / IV(A)$gR​(y,A)=g(y,A)/IV(A)
$IV(A)$IV(A)为y关于A的熵，类似于交叉熵，和m有关。

基尼指数

可以看出基尼指数是和熵定义类似的，基尼指数越小，y的不确定度越小。

ID3算法

算法描述