信息论基础

熵

如果X是一个离散型随机变量,其概率分布为:
p(x)=P(X=x),x∈X.X的熵H(X)为:

$H[x]=-\sum_xp(x)lnp(x)$

约定0log0=0

联合熵

如果X,Y是一对离散型随机变量X,Y～p(x,y),
X,Y的联合熵H(X,Y)为：

$H(X,Y)=-\sum_{x∈X}\sum_{y∈Y}p(x,y)logp(x,y)$

条件熵

定义事件X与Y

$H(X|Y)=\sum_{i,j}p(x_i,y_j)log\frac{p_{y_i}}{p(x_i,y_j)}$

其中$p(x_i,y_j)$为X=$x_i$且Y=$y_j$.
推导过程:

$H(Y|X)=\sum_{x∈X}p(x)H(Y|X=x)=-\sum_{x∈X}\sum_{y∈Y}p(x,y)logp(y|x)$

相对熵(KL散度)

考虑某个未知的分布p(x),假定我们已经使用一个近似的分布q(x)对他进行建模.如果我们使用q(x)来建立一个编码体系,用来把x的值传给接收者,那么,由于我们使用了q(x),而不是真实分布p(x),因此在具体化x的值(假定我们选择了一个高效的编码系统)时,我们需要一些附加的信息,我们需要的平均的附加信息量为

$KL(p||q)=-\int p(x)lnq(x)dx-(-\int p(x)lnp(x)dx)=-\int p(x)ln\frac{q(x)}{p(x)}dx$

KL散度不能说为距离,是因为其不满足对称性和三角法则.

互信息

互信息实际上是更广泛的相对熵的特殊情形
如果变量不是独立的,我们可以考虑考察,联合概率分布与边缘分布乘积之间的KL散度,来判断它们是否”接近”于相互独立.此时,

$I[x,y]=KL(p(x,y)||p(x)p(y))=-\int\int p(x,y)ln\frac{p(x)p(y)}{p(x,y)}dxdy$ $I[x,y]=H[x]-H[x|y]=H[y]-H[y|x]$

互信息,条件熵与联合熵的区别与联系

交叉熵

如果一个随机变量 X ~ p(x),q(x)为用于近似 p(x)的概率分布,那么,随机变量 X 和模型 q 之间的交叉熵定义为:

$H(X,q)=H(X)+D(p||q)=-\sum_xp(x)logq(x)$

交叉熵的概念用以衡量估计模型与真实分布之间的差异

困惑度

在nlp中有出现
在设计语言模型时,我们通常用困惑度来代替交叉熵衡量语言模型的好坏。给定语言L的样本
$l_1^n=l_1….l_n$,L的困惑度$PP_q$定义为:

$PP_q=2^{H(L,q)}$

2的交叉熵次方

加权熵

$H_w(X)=-\sum_{i=1}^qw_ip_ilogp_i$

瑞丽熵(Renyi entropy)

设有一离散变量的概率分布$(p_1,p_2,…,p_n)$,Renyi信息熵定义为:

$H=\frac{1}{1-q}ln\sum_{i=1}^Np_i^q$ $R(q)=\frac{log(\sum_{i=1}^n p_i^q)}{1-qq}$

其中,q为一个可取任意实数的一个参数.
当q=0时,R(q)=log(n),即计算出了元素的个数的对数
当q=1时,分子分母趋近于0,可用洛必达求其极限为:

$lim_{q\rightarrow 1}R(q)=-\sum_{i=1}^np_ilog(p_i)$

即当q=1时,Renyi熵变成了香浓熵

信息增益

训练数据集D,|D|为样本容量,即样本的个数,设K个类$C_k$来表示,$|C_k|$为$C_i$的样本个数,|$C_k$|之和为|D|,k=1,2,…,根据特征A将集合D划分为n个子集$D_1,D_2,…,D_n$,$|D_i|$为$D_i$的样本个数,$|D_i|$之和为|D|,i=1,2,…,记$D_i$中属于$C_k$的集合为$D_{ik}$,即交集,$|D_{ik}|$为$D_{ik}$的样本个数,算法如下:

$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$

选定A的条件熵

$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$

信息增益

$g(D,A)=H(D)-H(D|A)$

基尼不纯度

假设某分类问题有K个类别,样本点属于第k类的概率为$p_k$,其概率分布的基尼系数为

$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$

在属性A发生的情况下,决策事件B发生的基尼指数:

$Gini(B,A)=\sum_{i=1}^n\frac{|B_i|}{|B|}Gini(B_i)$

基尼指数(Gini Index)是CART算法的衡量依据。决策树的生成就是递归地构建二叉树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

决策树算法

优点:

决策树算法中学习简单的决策树规则建立决策树模型的过程非常容易理解
决策树模型可以可视化,非常直观
应用范围广,可用于分类和回归,而且非常容易做多类别的分类
能够处理数值型和连续的样本特征
缺点:
容易过拟合
学习一棵最优的决策树被认为是NP-complete问题.实际中的决策树是基于启发式的贪心算法建立的,这种算法不能保证建立全局最优的决策树. Random Forest引入随机能够缓解这个问题
ID3
引入的上面提到的信息增益 $g(D,A)=H(D)-H(D|A)$ 基本思想是,熵表示的是一种混乱程度,熵越大,越混乱,而一旦我们确定下一个特征以后,我们希望这种分类的混乱度应该更低(或者说是更能确定这种该样本的类别),所以确定一个特征是一个熵减的过程,如何确定最好的特征,就需要确定的特征能使熵降低越多越好(即越稳定),所以我们会选择信息增益大的特征为当前结点划分依据.

C4.5

上面提到的ID3存在着一个缺点,它一般会优先选择有较多属性值的Feature,因为属性值多的feature,会有相对相对较大的信息增益(分得越细确定性越高,被认为是越稳定的).为了避免这个问题,C4.5引入了信息增益比来作为选择分支的准则.信息增益比率通过引入一个被称作分裂信息的项来惩罚取值较多的Feature.

另外最重要的是C4.5还弥补了ID3中不能处理特征属性值连续的问题,但是对连续属性值需要扫描排序,会使C4.5性能下降

$SplitInformation(D,A)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log\frac{|D_i|}{|D|}$

这就是那个分裂信息项,主要就是表示该特征的分裂的程度

$GainRatio(D,A)=\frac{g(D,A)}{SplitInformation(D,A)}$

CART分类树

CART又叫分类回归树.
主要的评估依据就是前面提到的GINI指数
ID3根据属性值分割数据,之后该特征不会再起作用,这种快速分割的方式会影响算法的准确率.CART是一棵二叉树(只会二分),采用二元切分,每次把数据切成两份,分别进入左子树、右子树.而且每个非叶子节点都有两个孩子,所以CART的叶子结点数比非叶子结点树多1(是不是有点像哈夫曼树？！)相比ID3和C4.5,CART应用要多一些,既可以用于分类也可用于回归.CART分类时,使用Gini指数来选择最好的数据分割的特征,gini描述的纯度,与信息熵的含义相似.CART中每一次迭代都会降低Gini系数.

回归树原理

之前的线性回归都提到过,回归问题一般都是用均方误差作为损失函数,当然回归树也不例外.

$L=\frac{1}{n}\sum_{i=1}^n(y_i-\hat{y_i})^2$

问题是我们将一个样本送入树模型中,最终它只会从一个叶子结点出来,那么它的输出的值只有一个,从那个叶结点输出的值都一样,我们该如何确定这个值?一般想到的都是落在该区域的样本均值,作为该区域的输出值.
先将上面的$y$表示成下述形式($\hat{y}$是ground truth)

$y=\sum_{m=1}^Mc_mI(x∈R_m)$

加入使用特征j的取值s来将输入空间划分为两个区域,分别为:

$R_1(j,s)=\{x|x^{(j)}≤s\}和R_2(j,s)=\{x|x^{(j)}＞ s\}$

考虑最小化损失函数,即:

$min_{j,s}[\sum_{x_i∈R_1(j,s)}(y_i-c_1)^2+\sum_{x_i∈R_2(j,s)}(y_i-c_2)^2]$

其中$c_1,c_2$分别为$R_1$,$R_2$区间内的输出平均值.

为使平方误差最小,我们需要依次对每个特征的每个取值进行遍历,计算出当前每一个可能的切分点的误差,然后选择切分误差最小的切分点将输入空间切分为两个部分,然后递归上述步骤,直到切分结束.此方法切分的树称为最小二乘回归树.

总结：此方法的复杂度较高，尤其在每次寻找切分点时，需要遍历当前所有特征的所有可能取值，假如总共有F个特征，每个特征有N个取值，生成的决策树有S个内部节点，则该算法的时间复杂度为：O(FNS)。

CART实践中的特点:

决策树防止过拟合手段

决策树是很容易过拟合,如何防止过拟合呢？这里采用剪枝操作,分为预剪枝和后剪枝.

预剪枝

预剪枝其实就是在树生成的过程进行剪枝。
核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。

后剪枝

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。

解释一下上面的第8步计算,书上的意思是,对完整树$T_0$中的任意内部结点t,以t为单结点树(结点为叶,没有分支)的损失函数

$C_α(t)=C(t)+α$

以t为根节点的子树$T_t$的损失函数是

$C_α(T_t)=C(T_t)+α|T_t|$

当α=0或充分小时,有不等式:

$C_{α}(T_t)＜C_{α}(t)$

当α增大到某一值时, $C_α(T_t)=C_α(t)$
当α再继续增大时,不等式反向,所以只要

$α=\frac{C(t)-C(T_t)}{|T_t|-1}$ ,$T_t$与t有相同的损失函数值,而t的结点更少,因此,因此t比$T_t$更可取,对$T_t$进行剪枝。

这里剪枝的目的不是为了最小化损失函数，剪枝的目的是为了达到一个更好的泛化能力。而对于决策树来说，叶结点的数量越多，反应了决策树对训练数据的细节反应的越多，继而弱化了泛化能力。α值衡量了损失函数中叶结点数量的权重,α值越大,在最小化损失函数时,需要更多的考虑叶结点数量的影响.α可以看作是一个系数,不同的α对应不同的损失函数,而对于所有的这些损失函数来说,在训练机上进行决策树生成时候的步骤都一样,差别知识在判断某些结点是否进行展开的区别.
这个有点类似于对一个函数的泰勒级数展开，而 α 值控制着展开的次数项，越小的值展开的次数项越多（往回收缩的高次项越少）。因为决策树的结点个数是有限的，对应到α的值来说也是有限的。上述求α过程就是得到具体收缩每一个分支对应的值。

一些其他的防止过拟合的方法

集成方法,如随机森林
控制满足分裂条件的不纯度的阈值
控制叶子节点个数
控制继续下一次划分时叶子结点的最小样本数

sklearn

分类树

sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

criterion：string类型，可选参数（默认=”gini”）。度量划分属性质量：”gini”指基尼不纯度（Gini impurity）；”entropy”指信息增益。
splitter：string类型，可选参数（默认=”best”）。每个结点选择划分属性的策略：“best”选择最好的划分；”random”选择最好的随机划分。
max_features：int或float或string类型或None，可选参数（默认=None）。选择划分时所用的特征数目：
若是int类型，则使用max_features个特征；
若是float类型，则使用int(max_features*特征总数)个特征；
若是”auto“或”sqrt“，则使用sqrt(特征总数)个特征；
若是“log2”，则使用log2(特征总数)个特征；
若是None，则使用全部特征。
max_depth：int类型或None，可选参数（默认=None）。树的最大深度。
min_samples_split： int或float类型，可选参数（默认=2）。划分一个内部结点所需的最小样本数：若是int类型，则最少使用min_samples_split个样本；若是float类型，则最少使用ceil(min_samples_split*特征总数)个样本。
min_samples_leaf：int或float类型，可选参数（默认=1）。叶子结点所需的最小样本数：若是int类型，则最少为min_samples_leaf个样本；若是float类型，则最少为ceil(min_samples_leaf*特征总数)个样本。
min_weight_fraction_leaf：float类型，可选参数（默认=0）。限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。
max_leaf_nodes：int类型或None，可选参数（默认=None）。叶子结点数目最大值。
class_weight：dict或list或”balanced”或None，可选参数（默认=None）。类别权重：
dict：{类别标签：权重}指定类别权重；
list：多输出问题，应给定一个包含多个dict的list参数；
“balanced”：自动调整类别权重根据类别样本个数所占比例：样本总数/（类别的样本数）；
random_state：int类型或RandomState实例或None，可选参数（默认=None）。

若是int，random_state是随机数生成器的种子；
若是RandomState实例，random_state是随机数生成器；
若是None，则随机数生成器是使用np.random的RandomState实例。
min_impurity_split：float类型，可选参数（默认=1e-7）。树增长的早停阈值：如果某结点的不纯度小于这个阈值，则该结点为叶子结点。

presort：bool类型，可选参数（默认=False）。是否在拟合过程中预排序数据to加速寻找最好的划分：对于样本量大的决策树，设为True可能会减慢训练过程；当使用样本量少或者受限深度的决策树，设置为true会加速训练。

回归树

>>> sklearn.tree.DecisionTreeRegressor(criterion=’mse’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, presort=False)

criterion：string类型，可选参数（默认=”gini“）。度量划分属性质量：”mse”指均方误差，”mae“指平均绝对误差。
其余参数同DecisionTreeClassifier，但是没有class_weight这个参数。属性和方法也和DecisionTreeClassifier一致，没有class_这个属性。

决策树绘制

from sklearn.externals.six import StringIO
from sklearn import tree
import pydotplus

clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, Y)

dot_data = StringIO()
tree.export_graphviz(clf,out_file = dot_data,
					 feature_names = feature_name,
					 class_names = target_name, filled = True,
					 rounded = True, special_characters = True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("Tree.pdf")
print('Visible tree plot saved as pdf.')

参考文献

https://blog.csdn.net/sun_wangdong/article/details/83057155
https://blog.csdn.net/am290333566/article/details/81187562
《数据挖掘导论》之分类基本概念、决策树与模型评估