ID3算法

信息熵：
熵是度量样本集合纯度最常用的一种指标，代表一个系统中蕴含着多少信息量，信息量越大表面一个系统不确定性就越大，就存在跟多的可能性，即信息熵越大
假定当前样本集合D中第k类样本所占的比例为$P_k$(k=1,2,……,|y|)，则D的信息熵为：
$Ent=-{\sum }_{k=1}^{|y|}{p}_{k}lo{g}_2{p}_k$
其中，|y|表示样本类被种数，$p_k$表示第k类样本所占比例，且$0\le p_k\le 1,{\sum }_{k=1}^n{p}_k=1$
信息熵满足以下不等式：
$0\le Ent(D)\le lo{g}_2|y|$ y表示样本D中的个数
若令|y|=n，$p_k=x_k$，那么信息熵$Ent(D)$就可以看作一个n元的实值函数，即
$Ent(D)=f(x_1,\dots \dots ,x_n)=-{\sum }_{k=1}^n{x}_{k}lo{g}_2{x}_k$，其中：$0\le x_q\le 1,{\sum }_{k=1}^n{x}_k=1$
引入拉格朗日乘子法$\lambda$
$L(x_1,\dots \dots x_n,\lambda )=-{\sum }_{k=1}^n{x}_{k}lo{g}_2{x}_k+\lambda ({\sum }_{k=1}^n{x}_k-1)$
对L分别关于$x,\lambda$求一阶偏导，并令偏导等于0：
$\frac{\partial (x_1,\dots \dots ,x_n,\lambda )}{\partial x_1}=\frac{\partial }{\partial x_1}[-{\sum }_{k=1}^n{x}_{k}lo{g}_2{x}_k+\lambda ({\sum }_{k=1}^n{x}_k-1)]=0$

$=-lo{g}_2{x}_1-x_1\cdot \frac{1}{x_{1}ln2}+\lambda =0$
$=-lo{g}_2{x}_1-\frac{1}{ln2}+\lambda =0$
$\Rightarrow \lambda =lo{g}_2{x}_1+\frac{1}{ln2}$
同理可推：
$\lambda =lo{g}_2{x}_1+\frac{1}{ln2}=lo{g}_2{x}_2+\frac{1}{ln2}=\dots \dots =lo{g}_2{x}_n+\frac{1}{ln2}$
对于任意的x，满足约束条件：
${\sum }_{k=1}^n{x}_k=1$
因此：
$x_1=x_2=x_3\dots \dots =x_n=\frac{1}{n}$
最大值点还是最小值点需要做个简单的检验：
当$x_1=x_2=x_3\dots \dots =x_n=\frac{1}{n}$时：
$f(\frac{1}{n},\dots \dots \frac{1}{n})=-{\sum }_{k=1}^n\frac{1}{n}lo{g}_2\frac{1}{n}=-n\cdot lo{g}_2\frac{1}{n}=lo{g}_{2}n$
将$x_1=1,x_2=x_3=\dots \dots =x_n=0时$：
$f(1,0,\dots \dots ,0)=-1\cdot lo{g}_{2}1-0\cdot lo{g}_{2}0\dots \dots -0\cdot lo{g}_{2}0=0$
显然$lo{g}_{2}n\ge 0$，所以$x_1=x_2\dots \dots =x_n=\frac{1}{n}$为最大值点，最大值为$lo{g}_{2}n$
下面考虑求$f(x_1,\dots \dots ,x_n)$的最小值，仅考虑$0\le x_k\le 1,f(x_1,\dots \dots ，x_n)$可以看作是n个互不相关一元函数的加和，即：
$f(x_1,\dots \dots ，x_n)={\sum }_{k=1}^{n}g(x_k)$
$g(x_k)=-x_{k}lo{g}_2{x}_k,0\le x_k\le 1$
求$g(x_i)$的最小值，但因为其表达式相同。所以只求出一个就可。
求$g(x_1)$的最小值，首先对$g(x_1)$关于$x_1$求一阶、二阶导数：
$g(x_1{)}^{\prime }=\frac{d(-x_{1}lo{g}_2{x}_1)}{d{x}_1}=-lo{g}_2{x}_1-x_1\cdot \frac{1}{x_{1}ln2}=-lo{g}_2{x}_1-ln2$
$g(x_1{)}^{\prime \prime }=\frac{d(-lo{g}_2{x}_1-\frac{1}{ln2})}{d{x}_1}=-\frac{1}{x_{1}ln2}$
在定义域$0\le x_k\le 1$上，始终有$g^{\prime \prime }(x_1)=-\frac{1}{x_{1}ln2}<0$，即$g(x_i)$为开口向下的凹函数，最小值在边界$x_1=0$或$x_1=1$处取得：
$g(0)=-0lo{g}_{2}0=0$
$g(1)=-1lo{g}_{2}1=0$
$g(x_1)$的最小值即为0，同理可得$g(x_2)\dots \dots g(x_n)$的最小值也0，那么$f(x_1,\dots \dots ,x_n)$的最小值此时为0
如果令某个$x_k=1$，那么根据约束条件${\sum }_{k=1}^n=1$可知：
$x_1=x_2=\dots \dots =x_{k+1}=\dots \dots =x_n=0$
带入$f(x_1,\dots \dots ,x_n)$得：
$f(0,0\dots \dots 0,1,0\dots \dots 0)=0$
所以$x_k=1,x_1=x_2=\dots \dots =x_{k-1}=x_{k+1}=\dots \dots =x_n=0$，一定是$f(x_1,\dots \dots ,x_n)$在满足约束条件下的最小值点，其最小值和为0。
所以说：$0\le Ent(D)\le lo{g}_{2}n$

信息增益

假定离散属性$\alpha$有$V$个可能的取值${\alpha }^1,{\alpha }^2\dots \dots {\alpha }^V$，如果使用特征a来对数据集$D$进行划分，则会产生$V$个分支结点，其中第$v$个结点包含了数据集$D$中所有在特征$\alpha$上取值为${\alpha }^V$的样本总数，记住$D^v$。再考虑到不同的分支结点所包含的样本数量不同，给分支结点赋予不同的权重，这样对样本数越多的分支点的影响就会越大，因此，就能够计算出特征对样本集$D$进行划分所获得的“信息增益”：
$Gain(D,\alpha )=Ent(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$

讯享网
该数据集包含十七个样本、有五个属性。类别为好瓜（8/17）、坏瓜（9/17）
$Ent(D)=-\frac{8}{17}\ast lo{g}_2\frac{8}{17}-\frac{9}{17}\ast lo{g}_2\frac{9}{17}=0.9975$
下面计算每个信息的信息增益
属性$a_1$:色泽
$Gain(D,a_1)=Ent(D)-{\sum }_{v=1}^{3}Ent(D^v)$
$=Ent(D)-(\frac{D^1}{D}\times Ent(D^1)+\frac{D^2}{D}\times Ent(D^2)+\frac{D^3}{D}\times Ent(D^3))$
对数据集进行色泽划分：D1青绿（包含6个样本）、D2乌黑（6个样本）、D3浅白（5个样本）

$=0.9975-(\frac{6}{17}(-\frac{3}{6}lo{g}_2\frac{3}{6}-\frac{3}{6}lo{g}_2\frac{3}{6})+\frac{6}{17}(-\frac{4}{6}lo{g}_2\frac{4}{6}-\frac{2}{6}lo{g}_2\frac{2}{6}+\frac{5}{17}(-\frac{1}{5}lo{g}_2\frac{1}{5}-\frac{4}{5}lo{g}_2\frac{4}{5}))$
$=0.1091$
同理可求属性$a_2$:根蒂
$Gain(D,a_2)=0.1427$
属性$a_3$:敲声
$Gain(D,a_3)=0.1408$
属性$a_4$:纹理
$Gain(D,a_4)=0.3808$
属性$a_5$:脐部
$Gain(D,a_5)=0.2892$
比较所得纹理属性的信息增益最大
然后对每一个分支节点做进一步划分，以下图中分支节点（“纹理=清晰”）为例，该结点包含的样本集合中有编号{1、2、3、4、5、6、8、10、15}的九个样例，可用属性集合为{色泽、根蒂、敲声、脐部、触感}，基于样本集合（“纹理=清晰”）

样本集合(“纹理=清晰”)的信息熵为：
$Ent(D_2)=-\frac{7}{9}lo{g}_2\frac{7}{9}-\frac{2}{9}lo{g}_2\frac{2}{9}=0.7642$
我们接下来选择色泽属性${\alpha }_1$
$Gain(D_2,{\alpha }_1)=Ent(D_2)-{\sum }_{v=1}^3\frac{|D_2^v|}{D_2}Ent(D_2^v)$
$=Ent(D_2)-(\frac{D_2^1}{D_2}\times Ent(D_2^1)+\frac{D_2^2}{D_2}\times Ent(D_2^3)\frac{D_2^3}{D_2}\times Ent(D_2^3))$
$=0.0431$
根蒂属性，${\alpha }_2$:
$Gain(D_2,{\alpha }_2)=0.4581$
敲声属性${\alpha }_3$:
$Gain(D_2,{\alpha }_3)=0.3308$
脐部属性${\alpha }_4$:
$Gain(D_2,{\alpha }_4)=0.4581$
触感属性${\alpha }_5$:
$Gain(D_2,{\alpha }_5)=0.4581$

随机选择最大的其中之一作为划分属性，这里选择“根蒂”作为划分属性。

继续对上图中的每个分支结点递归进行划分，以上图中的结点{ “根蒂=蜷缩”}为例，设该样本集为{1，2，3，4，5}，共五个样本，但这五个样本的label均为好瓜。因此均为正样本。得到的分支节点图为：

接下来对上图中结点（“根蒂=稍蜷”）进行划分，该点的样本集为{6，8，15}，共3个样本。可用特征集为色泽、敲声、肚脐、触感进行计算信息增益、得到下表

色泽触感作为最大，这里我们选择色泽。

青绿为好瓜，递归返回对乌黑进行划分。色泽等于浅白此点为空，类别按照父节点中类别最高的样本所以色泽为浅白的类别为好瓜。
最终决策树如下图所示

ID3算法的不足：

1. ID3没有考虑连续性
2. ID3采用信息熵大的特征优先建立决策树的节点，取值比较多的特征比取值少的特征信息增益大。
3. 未对缺失值做考虑
4. 没有考虑过拟合的情况