基于香农熵的决策树算法

　

香农熵

基于香农熵的决策树算法

---

《机器学习实战》一书中有介绍构造决策树的算法。

所谓决策树就是已知一些项特征的信息和项最终分类，求通过特征判断项最终分类的递归决策树。例如书中的例子是判断一个动物是不是鱼类，下面为一个数据集。

def createdataset():
    dataSet = [\
        [1, 1, 'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

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

---

算法大致流程是:

1.获得数据集

2.找到一个好的特征划分数据集为两部分

3.递归这一过程直到数据集内全部为同种类

4.打印由上述划分确定的树状结构

---

那么如何划分数据集，也就是如何确定最佳划分状态?当然是信息量大的划分。信息量可以用香农熵刻画。

U(s)=−Σ(pi∗logpi2)，其中P(s=si)=pi，且{si}为s的一个划分

具体严格的数学推导我觉得可以用性质刻画定义(数学上很多函数都是先给出性质再解函数方程获得唯一定义，于是干脆用性质代替定义)。

显然U(s)有性质信息量等于各部分信息量之和:U(s)=ΣU(si)

并定义初值条件U(B(1，12))=1(bit)

那么，只需要求出U(s_i)即可，下面假设f(P(si))=U(si)，只需要求出f(x)(0<x<1)表达式即可

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

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

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

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

---

决策树代码略

相关阅读

信息论知识：互信息、交叉熵、KL散度

信息论的基本想法是一个不太可能的事件居然发生了，要比一个非常可能的事件发生，能提供更多的信息。消息说：‘‘今天早上太阳升起’’

【解决办法】torch交叉熵使用时遇到 Dimension out of

简述 其实这个问题我很久以前用pytorch写程序的时候就遇到过这个问题，当时纠结了很久之后最后解决了。当时本来就想来写个东西来记

决策树（信息熵—GINI）计算习题

文章目录1 有以下二分类问题训练样本GINI计算2 有以下二分类问题数据集。信息增益计算1 有以下二分类问题训练样本 顾客ID 性

香农三大定理

香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。香

机器学习基础（五十八）—— 香农熵、相对熵（KL散度）与交叉

1. 香农熵（Shannon entropy） 信息熵（又叫香农熵）反映了一个系统的无序化（有序化）程度，一个系统越有序，信息熵就越低，反之就越高。 如果一