机器学习

决策树

信息论

信息

• 信息即信源：表示一段信息，如文本、语音等等。
• 信源的不确定性：信源发出的消息不确定性越大，收信者获取的信息量就越大。如果信源发送的消息是确切的，则对收信者来说没有任何价值（没有信息量）。衡量不确定性的方法就是考察信源的概率空间。X包含的状态越多，状态的概率越小，则不确定性越大，所含有的信息量越大。

信息量

• 如何衡量信息的大小，如何衡量信息所包含的信息量？
  
  自信息量H(X)：一个事件(消息)本身所包含的信息量，由事件的不确定性决定的。

• 如何用数学模型表示的信息量？

1. 单调性：
   信息量与信息出现的概率成反比，即信息出现的概率越大，则的信息量越小。
2. 可加性：信息与是独立随机变量可加(暂且简单认为独立，不独立有条件熵)
3. 非负性

寻找一个函数同时满足以上三点，即：
随机事件发生概率为，则信息量函数定义为：

可加性证明：，,相互独立

信息熵

定义：信息量在分布下的数学期望：

热力学第二定律

薛定谔.《生命是什么》 （第六章 有序，无序和熵）
基本思想：一个正常的人若要维持高序的状态，则必须要吸收负熵来维持高序稳定的状态，否则我们的熵会趋于增大而变的无序。所以人需要吃食物，食物是高序稳定的，经过吸收变得无序产生负熵来维持我们高序稳定状态。

信息熵可以描述数据的混合程度。
熵越大，混合度越高，数据纯度越低。熵[0， 1]

信息熵的计算

数据集：
X X X | O O O X X X O O

• ：最初整个系统（数据集）的固定熵，即经验熵（李航，统计学习方法）
  
• 根据某个特征将数据集划分为(X X X)和(O O O X X X O O)：
  

即数据集划分后两个子数据集的信息熵。由这样划分数据集之后，整个系统（数据集）的信息熵有何变化呢？由此引入了信息增益(Information Gain)。

信息增益

信息增益是：原始数据集的熵 减去 按特征划分若干个子数据集的加权熵
信息增益所表达的是：由于熵的减小，而增加信息的获得是多少。
已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益（Information Gain）”。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。在信息增益中，衡量标准是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。对一个特征而言，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量。

信息增益越大越好，还是越小越好？
信息增益是：原始数据集的熵减去按特征划分若干个子数据集的加权熵。我们的目的是使每一个子集的熵最小（最小代表每个子集都是一类数据，高度有序的状态，高纯度），即加权熵尽量小，则IG越大。
根据IG准则的特征选择方法是什么？
对训练数据集（或子集），计算其每一个特征的信息增益，选择信息增益最大的特征。

更新中...

参考链接：

1. 李航，统计学习方法
2. 信息论的熵
3. https://github.com/wzyonggege/statistical-learning-method
4. MathJax basic tutorial and quick reference