如何选择电商网站建设,龙江建站技术,十大免费软件下载,大连专业模板网站制作1. 决策树ID3算法的信息论基础
机器学习算法其实很古老#xff0c;作为一个码农经常会不停的敲if, else if, else,其实就已经在用到决策树的思想了。只是你有没有想过#xff0c;有这么多条件#xff0c;用哪个条件特征先做if#xff0c;哪个条件特征后做if比较优呢#…1. 决策树ID3算法的信息论基础
机器学习算法其实很古老作为一个码农经常会不停的敲if, else if, else,其实就已经在用到决策树的思想了。只是你有没有想过有这么多条件用哪个条件特征先做if哪个条件特征后做if比较优呢怎么准确的定量选择这个标准就是决策树机器学习算法的关键了。1970年代一个叫昆兰的大牛找到了用信息论中的熵来度量决策树的决策选择过程方法一出它的简洁和高效就引起了轰动昆兰把这个算法叫做ID3。下面我们就看看ID3算法是怎么选择特征的。
首先我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性越不确定的事物它的熵就越大。具体的随机变量X的熵的表达式如下
H(X)−∑i1npilogpiH(X) -\sum\limits_{i1}^{n}p_i logp_iH(X)−i1∑npilogpi
其中n代表X的n种不同的离散取值。而pip_ipi代表了X取值为i的概率log为以2或者e为底的对数。举个例子比如X有2个可能的取值而这两个取值各为1/2时X的熵最大此时X具有最大的不确定性。值为H(X)−(12log1212log12)log2H(X) -(\frac{1}{2}log\frac{1}{2} \frac{1}{2}log\frac{1}{2}) log2H(X)−(21log2121log21)log2。如果一个值概率大于1/2另一个值概率小于1/2则不确定性减少对应的熵也会减少。比如一个概率1/3一个概率2/3则对应熵为H(X)−(13log1323log23)log3−23log2log2)H(X) -(\frac{1}{3}log\frac{1}{3} \frac{2}{3}log\frac{2}{3}) log3 - \frac{2}{3}log2 log2)H(X)−(31log3132log32)log3−32log2log2)
熟悉了一个变量X的熵很容易推广到多个个变量的联合熵这里给出两个变量X和Y的联合熵表达式
H(X,Y)−∑i1np(xi,yi)logp(xi,yi)H(X,Y) -\sum\limits_{i1}^{n}p(x_i,y_i)logp(x_i,y_i)H(X,Y)−i1∑np(xi,yi)logp(xi,yi)
有了联合熵又可以得到条件熵的表达式H(X|Y)条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下
H(X∣Y)−∑i1np(xi,yi)logp(xi∣yi)∑j1np(yj)H(X∣yj)H(X|Y) -\sum\limits_{i1}^{n}p(x_i,y_i)logp(x_i|y_i) \sum\limits_{j1}^{n}p(y_j)H(X|y_j)H(X∣Y)−i1∑np(xi,yi)logp(xi∣yi)j1∑np(yj)H(X∣yj)
好吧绕了一大圈终于可以重新回到ID3算法了。我们刚才提到H(X)度量了X的不确定性条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性那么H(X)-H(X|Y)呢从上面的描述大家可以看出它度量了X在知道Y以后不确定性减少程度这个度量我们在信息论中称为互信息记为I(X,Y)。在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大则越适合用来分类。
上面一堆概念大家估计比较晕用下面这个图很容易明白他们的关系。左边的椭圆代表H(X),右边的椭圆代表H(Y),中间重合的部分就是我们的互信息或者信息增益I(X,Y), 左边的椭圆去掉重合部分就是H(X|Y),右边的椭圆去掉重合部分就是H(Y|X)。两个椭圆的并就是H(X,Y)。 2. 决策树ID3算法的思路
上面提到ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树用计算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D输出为0或者1。其中有9个输出为0 6个输出为1。 样本中有个特征A取值为A1A2和A3。在取值为A1的样本的输出中有3个输出为1 2个输出为0取值为A2的样本输出中,2个输出为1,3个输出为0 在取值为A3的样本中4个输出为11个输出为0.
样本D的熵为H(D)−(915log2915615log2615)0.971H(D) -(\frac{9}{15}log_2\frac{9}{15} \frac{6}{15}log_2\frac{6}{15}) 0.971H(D)−(159log2159156log2156)0.971
样本D在特征下的条件熵为 H(D∣A)515H(D1)515H(D2)515H(D3)H(D|A) \frac{5}{15}H(D1) \frac{5}{15}H(D2) \frac{5}{15}H(D3)H(D∣A)155H(D1)155H(D2)155H(D3)
−515(35log23525log225)−515(25log22535log235)−515(45log24515log215)0.888 -\frac{5}{15}(\frac{3}{5}log_2\frac{3}{5} \frac{2}{5}log_2\frac{2}{5}) - \frac{5}{15}(\frac{2}{5}log_2\frac{2}{5} \frac{3}{5}log_2\frac{3}{5}) -\frac{5}{15}(\frac{4}{5}log_2\frac{4}{5} \frac{1}{5}log_2\frac{1}{5}) 0.888−155(53log25352log252)−155(52log25253log253)−155(54log25451log251)0.888
对应的信息增益为I(D,A)H(D)−H(D∣A)0.083I(D,A) H(D) - H(D|A) 0.083I(D,A)H(D)−H(D∣A)0.083
下面我们看看具体算法过程大概是怎么样的。
输入的是m个样本样本输出集合为D每个样本有n个离散特征特征集合即为A输出为决策树T。
算法的过程为
1)初始化信息增益的阈值ϵ
2判断样本是否为同一类输出Di如果是则返回单节点树T。标记类别为Di
3) 判断特征是否为空如果是则返回单节点树T标记类别为样本中输出类别D实例数最多的类别。
4计算A中的各个特征一共n个对输出D的信息增益选择信息增益最大的特征Ag
5) 如果Ag的信息增益小于阈值ϵ则返回单节点树T标记类别为样本中输出类别D实例数最多的类别。
6否则按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
7对于所有的子节点令DDi,AA−{Ag}递归调用2-6步得到子树Ti并返回。
3. 决策树ID3算法的不足
ID3算法虽然提出了新思路但是还是有很多值得改进的地方。
a)ID3没有考虑连续特征比如长度密度都是连续值无法在ID3运用。这大大限制了ID3的用途。
b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现在相同条件下取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值各为1/2另一个变量为3个值各为1/3其实他们都是完全不确定的变量但是取3个值的比取2个值的信息增益大。如果校正这个问题呢
c) ID3算法对于缺失值的情况没有做考虑
d) 没有考虑过拟合的问题
