机器学习实战——决策树的计算过程

K-近邻算法的缺点

在前几篇文章中，我们介绍了K-近邻算法。K-近邻算法的最大缺点是无法给出数据的内在含义。

决策树

而今天要学习的决策树算法的一大优势就在于其数据形式非常容易理解。决策树是处理分类问题中最经常使用的数据挖掘算法。

决策树解决问题的一般流程如下：

(1) 收集数据：可以使用任何方法。

(2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。

(3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。

(4) 训练算法：构造树的数据结构。

(5) 测试算法：使用经验树计算错误率。

(6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义

决策树算法需要一步一步的构造数据集的子集合。在这个过程中，需要计算划分子集合过程中的信息增益，从而每次划分时，都是的信息增益最大。

在划分数据集之前之后信息发生的变化称为信息增益

为了计算划分集合的信息增益，我们先来学习一下，如何计算一个结合的熵。

计算数据集的熵

一个数据集的概率可以阐述为：集合中某个分类的概率为p(x_i)，且集合中共有n个分类，则集合的熵为：

H = - ∑ⁿ ₁ p(x_i)log₂（p(x_i)）

p(x_i) = 集合中该分类的数量 / 集合实例总数量

如此，我们便能够计算集合的熵。

划分数据集

按照什么样的策略来划分数据集合呢？我们按照指定某个特征值符合某一规则，或者某个特征值等于某个值时，我们将其按照这样的规则来划分。

比如有数据[1, 2, 3, 男], [1， 3， 4，男], [2, 2, 4, 女]，其中前三列为特征值，最后一列为分类。比如，我们可以按照第一列特征等于1来划分，如此便得到两个集合：[[1, 2, 3, 男], [1， 3， 4，男]], 以及集合 [[2, 2, 4, 女]]。

如何判断此时划分数据集是否正确呢，或者是否能够使得信息增益最大呢？这就需要逐个的按照每个特征都来划分一次，每次都计算出划分后的每个子集的熵x以及子集在父集合中的概率p，子集个数为n，父集合的熵为H，则使用第i个特征划分集合的信息增益为：

G_i = H - ∑（1-> n） p * x

如此，计算出使得G_i最小的i值，即为当次划分集合最好的特征，即第i列特征。

注意事项

数据集的最后一列为类别标签，每一行都有相同多的数据长度。