机器学习算法（四）决策树

一、信息熵

首先给出信息熵的定义如下 H(x)=−∑x∈χp(x)lnp(x)
1、无约束条件时，均匀分布熵最大
2、若给定分布的期望和方差，则正态分布的熵最大

二、决策树是什么

决策树就是下图所示的东西

三、决策树

1、几个名词：

1、训练数据集：D
2、数据的标签有K种，即有K个类，记为 Ck
3、数据有多个特征，其中有某一个特征叫A，这个A特征有n个取值，记所有A特征取值为i的数据的集合为 Di
4、在子集 Di 中属于第k个类的样本集合记为 Dik
定义如下两个量：
H(D)=∑k=1K∣∣Ck∣∣|D|log∣∣Ck∣∣|D|
H(D|A)=−∑i=1n|Di||D|∑k=1K∣∣Dik∣∣∣∣Di∣∣log∣∣Dik∣∣∣∣Di∣∣

2、评估指标

根据以上定义的量，定义如下几个评估指标：
1、信息增益： g(D,A)=H(D)−H(D|A)
2、信息增益率： gr(D,A)=g(D,A)/H(A)
3、基尼系数： Gini(p)=1−∑Kk=1(∣∣Ck∣∣|D|)2

3、决策树算法

常用决策树算法包括ID3算法、C4.5算法，CART决策树，它们最重要的不同在于评估指标不同，其中，ID3采用信息增益作为评估指标，C4.5采用信息增益率作为评估指标，CART决策树采用基尼系数作为评估指标。

我们以ID3为例，它首先扫描所有特征，找出信息增益最大的特征作为其根节点，在对其各个子节点递归地进行这个过程，直至达到某个收敛条件。

4、决策树的目标函数

决策树的目标函数，或者说决策树的损失函数为：
C(T)=∑t∈leafNt×H(t)
其中， Nt 代表某一叶结点中包含的样本数； H(t) 代表该叶结点中的熵

对该目标函数进行正则化后的目标函数为： Cα(T)=C(T)+α×|leafs| ,即加上叶节点个数的信息。