机器学习——决策树的三种学习方法
目录
我们知道决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一颗熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶子结点中的实例都属于同一类。
建立决策树的关键，即在当前状态下选择哪一个属性作为分类依据。根据不同的目标函数，建立决策树主要有以下三种算法。
- ID3(Iterative Dichotomiser)
- C4.5
- CART(Classification And Regression Tree)
ID3
ID3算法的核心思想就是以信息增益来度量特征的选择，选择分裂后信息增益最大的特征进行分裂。信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
要理解信息增益我们先从信息熵的定义开始。信息熵是香农借鉴热力学的概念提出的对信息进行描述的概念，指信息中排除了冗余后的平均信息量。不确定函数f应满足两个条件：（1）f是事情发生概率P的减函数；（2）两个独立符号所产生的不确定性等于各自不确定性之和。所以有，信息源的平均不确定性应当为单个符号不确定性
的统计平均值（E），可称为信息熵，即
H(Y|X)=H(X,Y)-H(X)被称为条件熵，表示X发生的前提下Y的熵，当熵和条件熵中的概率????数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别成为经验熵和经验条件熵。定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)的特征A给定条件下D的经验条件熵H(D|A)之差，即g(D,A)=H(D)-H(D|A),显然，这即为训练数据集D和特征A的互信息。
推导条件熵的定义式
信息增益的计算方法
设训练数据集为D，|D|表示样本个数；
设有K个类,
为属于类
的样本个数，有：
；
设特征A有n个不同的取值{}，根据特征A的取值将D划分为n个子集
为
的样本个数，有：
；
记子集中属于类
的样本的集合为
,
为
的样本个数。
计算数据集D的经验熵:
计算经验条件熵H(D|A):
计算特征A的信息增益：
遍历所有特征，选择信息增益最大的特征作为当前的分类特征。
优点：决策树ID3算法易于理解,能处理数据型的也能处理常规型的数据,还可以在相对较短的时间内能够对大型的数据集做出可行且较好的结果。
缺点：决策树ID3算法比较偏向于选择属性值多的类别。
C4.5
ID3偏向于选择属性值多的特征类别，这样会导致每个属性的样本数较少，此时噪声对模型的影响会更为显著，容易产生过拟合。为解决这一问题，引入信息增益率来作为度量进行特征选择，信息增益率公式为：
公式中将信息增益除以所对应特征的信息熵来表示信息增益率，若特征属性值较多则H(A)较大，信息增益率比信息增益小，能够很好的抑制模型选择属性值多的特征。
CART
CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。公式如下：
Variance方差也是衡量集合中样本不纯度的一种指标，因为只是针对连续值，因此只能用于处理回归决策树。假设集合D中每个样本的值为，那么集合D的Variance方差则定义为：
一个特征的信息增益（率）/gini指数越大，表明属性对样本的熵减少能力更强，这个属性使得数据由不确定性变成确定性的能力越强。