机器学习算法(三):决策树

时间:2021-03-04 21:04:47

决策树的学习器,不太适合用数学公式表示。

它构造了一个树形结构来建立模型,每个测试样本能在树上找到属于自己的叶节点,把自己归为该叶节点所标记的类别。

那么如何构造决策树?

关键是选择哪个属性作为树的分支节点,这里用到了信息论的概念

通过计算信息增益,信息增益越大,意味着使用这个属性进行划分所获得的“纯度“”提升越大,这里的纯度指样本越来越属于同一类别。

首先计算信息熵,样本集合D的信息熵如下,其中n为特征数目,$p_{i}$为第i类样本的比例。

$Ent(D) = \sum\limits_{i=1}^{n}p_{i}log_{2}p_{i}$

假设属性a 有V个可能的取值,$D^{v}$为假设以a作为分支节点,a取值为V的样本集合,那么用属性a对样本集合进行划分的信息增益为:

$Gain(D, a) = Ent(D) - \sum\limits_{v=1}^{V} \frac{|D^{v}|}{|D|} Ent(D^{v})$

选取信息增益最大的属性作为当前的划分属性,这样就做出了决策树的一个分支节点。

迭代计算直到得到决策树的叶节点,比如最后所有样本属于一个类别。这就是最基本的ID3算法。

 

深入研究决策树算法还可以考虑下面一些问题,留待以后补充。

1) 通过剪枝来对付过拟合

2) 连续值的处理

3) 缺失值的处理

4)对每个分支节点采取多变量决策