基于香农熵的决策树算法

基于香农熵的决策树算法

《机器学习实战》一书中有介绍构造决策树的算法。 所谓决策树就是已知一些项特征的信息和项最终分类，求通过特征判断项最终分类的递归决策树。例如书中的例子是判断一个动物是不是鱼类，下面为一个数据集。

书里举的另一个例子是隐形眼镜的问题。书里提供了绘图引擎用于绘制决策树。

算法大致流程是: 1.获得数据集 2.找到一个好的特征划分数据集为两部分 3.递归这一过程直到数据集内全部为同种类 4.打印由上述划分确定的树状结构

那么如何划分数据集，也就是如何确定最佳划分状态?当然是信息量大的划分。信息量可以用香农熵刻画。 U(s)=−Σ(pi∗logpi2)，其中P(s=si)=pi，且{si}为s的一个划分$U (s)= -/Sigma(p_i*log_2^{p_i})，其中P(s=s_i)=p_i，且/{s_i/}为s的一个划分$

具体严格的数学推导我觉得可以用性质刻画定义(数学上很多函数都是先给出性质再解函数方程获得唯一定义，于是干脆用性质代替定义)。 显然U(s)有性质信息量等于各部分信息量之和:U(s)=ΣU(si)$U(s)=/Sigma{U(s_i)}$ 并定义初值条件U(B(1，12))=1(bit)$U(B(1，{1 /over 2})) = 1(bit)$ 那么，只需要求出U(s_i)即可，下面假设f(P(si))=U(si)$f(P(s_i))=U(s_i)$，只需要求出f(x)(0<x<1)表达式即可$f(x)(0<x<1)表达式即可$

先考虑一个简单的问题，p=12k$p={1/over 2^k}$时，2k$2^k$个状态信息量之和为U=2kf(p)=k(bit)$U=2^kf(p)=k(bit)$，因为由定义1bit信息可以解决一个二分问题。那么f(p)=k2k=−p∗logp2$f(p)={k/over{2^k}}=-p*log_2^p$，当然这仅仅解决了1p=2k${1/over p} =2^k$情形。

然后利用相同手法可以得到性质(函数方程)f(x)x+f(f)y=f(x+y)x+y${f(x)/over x}+{f(f)/over y}={f(x+y)/over x+y}$且有初值条件f(12)=12和连续条件$f({1/over 2})={1/over 2}和连续条件$

这就是一个中规中规中矩的函数方程了，依次解决1p${1/over p}$是整数，有理数情况，最后用连续条件(Cauchy法)推广到实数即可。

可以得到信息量的表示方法，也就是香农熵，注意与热力学熵推导过程一模一样，除了常数不同。

决策树代码略