实现机器学习的分步指南 II - 决策树

Ryukkkk

4.00/5 (4投票s)

2019年5月5日

CPOL

3分钟阅读

8186

易于实现的机器学习

引言

决策的原理并不复杂。从根节点开始，将存储在节点中的特征值与测试对象的相应特征值进行比较。然后，根据比较结果递归地转向左子树或右子树。最后，叶节点的标签是测试对象的预测。

例如，下面有一棵决策树，其中特征集为{hungry, money}，标签集为{go to restaurant, go to buy a hamburger, go to sleep}。

在决策过程中，首先如果我饿了，转向右子树，这意味着我会去睡觉。否则转向左子树。然后，检查我的钱包里有多少钱。如果我有超过25美元，我会去餐厅。否则，我只能去买一个汉堡包。

决策树模型

决策树模型由特征选择、决策树生成和分类组成。

特征选择

特征选择的目的是选择具有训练数据分类能力的特征，以使学习过程更有效。特征选择包括两个部分，即特征选择和特征值选择。所选元组（特征，特征值）用作决策树中的节点。

特征选择通常基于**信息增益**或**信息增益率**。信息增益定义为集合D的经验熵， $H(D)$ ，与选择特征A下的条件熵， $H\left( D|A \right)$ 之间的差异，其计算公式为

$g\left( D,A \right)=H\left( D \right)-H\left( D|A \right)$

具体而言，当数据集D被特征A分为两个子集时，信息增益表示为

$g\left( D|A \right)=H\left( D \right)-\alpha H\left( D_{1} \right)-\left( 1-\alpha\right) H\left( D_{2} \right)$

其中 $\alpha$ 是第一个子集的比率，即

$\alpha=\frac{\left|D_{1}\right|}{\left|D\right|}$

信息增益的计算代码如下所示

 left_set, right_set = self.divideData(data, i, value)
 # calculate information gain
 ratio = float(len(left_set)/sample_num)
 if ratio == 0.0:
     info_gain = init_entropy - (1 - ratio) * self.getEntropy(right_set[:, -1])
 elif ratio == 1.0:
     info_gain = init_entropy - ratio*self.getEntropy(left_set[:, -1])
 else:
     info_gain = init_entropy - ratio * 
     self.getEntropy(left_set[:, -1]) - (1 - ratio) * self.getEntropy(right_set[:, -1])

到目前为止，我们已经学习了如何计算信息增益。但是，如何计算经验熵？经验熵是训练集标签的熵，由下式给出

$H\left( D\right)=-\sum_{k=1}^{K}\frac{\left| C_{k}\right|}{\left| D\right|}log_{2}\frac{\left| C_{k}\right|}{\left|D\right|}$

上面的等式看起来有点复杂，但很容易实现。让我们看一下它的代码

    def getEntropy(self, labels):
        labels_num = len(labels)
        label_count = self.uniqueCount(labels)

        entropy = 0.0
        for j in label_count:
            prop = label_count[j]/labels_num
            entropy = entropy + (-prop*math.log(prop, 2))

        return entropy

决策树的生成

有很多算法可以生成决策树，例如**ID3**，**C4.5**。在本文中，我们以ID3算法为例生成决策树。

首先，让我们弄清楚特征选择后的拆分过程。众所周知，特征选择是为了使数据可分类。因此，拆分过程是根据所选特征划分训练数据index及其选定的值value。具体来说，拆分过程是**如果样本中的index特征值大于value，则将样本添加到右子树并删除样本中的index特征；否则，如果样本中的index 特征值小于value，则将样本添加到左子树并删除样本中的index特征。 **拆分过程的代码是

    def divideData(self, data, index, value):
        left_set = []
        right_set = []
        # select feature in index with value
        for temp in data:
            if temp[index] >= value:
                # delete this feature
                new_feature = np.delete(temp, index)
                right_set.append(new_feature)
            else:
                new_feature = np.delete(temp, index)
                left_set.append(new_feature)
        return np.array(left_set), np.array(right_set)

在生成决策树之前，我们定义一个数据结构来保存决策树中的节点

class DecisionNode:
    def __init__(self, index=-1, value=None, results=None, right_tree=None, left_tree=None):
        self.index = index                    # the index of feature
        self.value = value                    # the value of the feature with index
        self.results = results                # current decision result
        self.right_tree = right_tree
        self.left_tree = left_tree

然后，我们可以递归地生成决策树。**如果数据集中没有特征，则停止。如果信息增益小于给定的阈值，则停止。否则，根据最佳选择的特征及其值拆分数据集**如下所示

     def createDecisionTree(self, data):
        # if there is no feature in data, stop division
        if len(data) == 0:
            self.tree_node = DecisionNode()
            return self.tree_node

        best_gain = 0.0
        best_criteria = None
        best_set = None

        feature_num = len(data[0]) - 1
        sample_num = len(data[:, -1])
        init_entropy = self.getEntropy(data[:, -1])

        # get the best division
        for i in range(feature_num):
            uniques = np.unique(data[:, i])
            for value in uniques:
                left_set, right_set = self.divideData(data, i, value)
                # calculate information gain
                ratio = float(len(left_set)/sample_num)
                if ratio == 0.0:
                    info_gain = init_entropy - (1 - ratio) * self.getEntropy(right_set[:, -1])
                elif ratio == 1.0:
                    info_gain = init_entropy - ratio*self.getEntropy(left_set[:, -1])
                else:
                    info_gain = init_entropy - ratio * self.getEntropy
                      (left_set[:, -1]) - (1 - ratio) * self.getEntropy(right_set[:, -1])
                if info_gain > best_gain:
                    best_gain = info_gain
                    best_criteria = (i, value)
                    best_set = (left_set, right_set)

        # create the decision tree
        if best_gain < self.t:
            self.tree_node = DecisionNode(results=self.uniqueCount(data[:, -1]))
            return self.tree_node
        else:
            ltree = self.createDecisionTree(best_set[0])
            rtree = self.createDecisionTree(best_set[1])
            self.tree_node = DecisionNode(index=best_criteria[0], 
                             value=best_criteria[1], left_tree=ltree, right_tree=rtree)
            return self.tree_node

分类

分类的原理类似于二叉排序树，即**将存储在节点中的特征值与测试对象的相应特征值进行比较。然后，递归地转向左子树或右子树**如下所示

    def classify(self, sample, tree):
        if tree.results != None:
            return tree.results
        else:
            value = sample[tree.index]
            branch = None
            if value >= tree.value:
                branch = tree.right_tree
            else:
                branch = tree.left_tree
            return self.classify(sample, branch)

结论与分析

在生成决策树之后，存在通过动态编程进行剪枝的过程，以获得最佳决策树。此外，分类和回归树（CART）是一种决策树，不仅可以应用于分类，还可以应用于回归。最后，让我们将我们的决策树与Sklearn中的树进行比较，检测性能如下所示

从图中我们可以了解到，决策树不如sklearn的树好，这可能是因为我们没有应用剪枝过程。

本文相关的代码和数据集可以在 MachineLearning 中找到。