决策树

决策树其实跟人做决策过程的道理是比较相似的.

比如小明在想今天要不要出去玩这件事情，首先会看看今天是不是工作日，如果是工作日，好了还是安心去搬砖吧! 如果不是工作日那再看看当前新冠肺炎疫情情况，如果没好，那还是窝在家里比较安全，如果疫情好了那小明再去看看今天天气怎么样，如果刮风下雨温度太低什么的那也窝在家里吧，如果不下雨, ok 那小明就开开心心的出去浪了, 这个就是整个决策树的流程了.

如图：

这里有个关键问题是，小明要决策的条件很多(是不是刮风、是不是下雨、温度怎么样), 怎么判断先用哪个条件做决策再用哪个条件呢？换句话说这些条件的先后顺序怎么定?

image

在决策树中定义这些分裂条件优先级比较有名的算法有：信息增益(ID3)、信息增益率(ID4.5)、基尼系数(CART)，下面分别介绍一下

信息增益(ID3)

ID3算法使用的是信息增益作为划分标准

• 总样本的信息熵：

• 某个属性的信息熵：

• 那么信息增益就是：

• 举个例子🌰，这里有一份小明历史上是否出去玩的数据：

总共14条数据，其中出去玩(Yes)的次数9, 那出去玩的概率是 P(Y) = 9/14

不出去玩(No)的次数5，那不出去玩的概率是 P(N) = 5/14

• 那么该样本的信息熵 info(D)就是：

样本中共有4个属性(条件): Outlook, Temperature, Humidity, Wind

Outlook属性的信息熵：

Sunny: 总数：5, Yes：2, No：3

• 它的信息熵就是：

Overcast: 总数：4, Yes：4, No：0

• 它的信息熵就是：

Rain: 总数：5, Yes：3, No：2

• 它的信息熵就是：

• Outlook属性总的信息熵就是：

  

• 最终算出Outlook属性信息增益是：

使用同样方法我们可以计算出其它属性的信息增益是：

所以Outlook的信息增益最高，所有我们切分决策树第一层的时候就选择使用使用天气属性(Outlook)，下一层依然采用相同方法来寻找信息增益最大的属性

信息增益率(ID4.5)

ID3算法存在一个问题，就是偏向于多值属性(过拟合)， 例如，如果存在唯一标识属性ID，则ID3会选择它作为分 裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处

ID3的后继改进算法C4.5使用信息增益率(gain ratio)，试图克服这个偏倚

• 信息增益：

  

• 引入的分裂信息熵：

  

• 那么信息增益率就是：

  

  需要注意的是，信息增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益高于平均值水平的属性，再从中选择增益率最高的属性

基尼系数(CART)

CART算法在分类树使用基尼指数增益, 回归树使用最小化均方差

• 基尼指数：

  

• 分裂后的基尼指数：

  

• 基尼指数增益：

  

我们在候选属性集合A中，选择那个使划分后基尼指数最小的属性作为最优划分属性，即 a = argmin Gini(A)(D, a)

决策树剪枝

为了防止决策树的过拟合， 在决策树的构造中通常会做剪枝操作，剪枝分为预剪枝和后剪枝：

• 预剪枝：

在构造过程中，当某个节点满足剪枝条件, 则直接停止 此分支的构造

• 后剪枝：

先构造完完整的决策树, 在通过某些条件遍历树进行剪枝

附代码

# -*- encoding: utf8 -*-
from math import log
​
​
class DecisionTree:
    """
    ID3算法实现的决策树
    """
​
    def __init__(self):
​
        self.__feature_labels = dict()
        self.__tree = dict()
​
    def cul_entropy(self, data_set):
        """
        计算信息熵
        :param data_set:
        :return: float ent
        """
        total_len = len(data_set)
        label_counts = {}
​
        for item in data_set:
            label_counts[item[-1]] = label_counts.get(item[-1], 0) + 1
​
        ent = 0
        for key in label_counts:
            label_prob = float(label_counts[key]) / total_len
            ent -= label_prob * log(label_prob, 2)
​
        return ent
​
    def cul_information_gain_label(self, before_ent, data_set, axis):
        """
        计算信息增益
        :param before_ent:
        :param data_set:
        :param axis:
        :return: float information gain
        """
        total_len = len(data_set)
        feature_values = [item[axis] for item in data_set]
        unique_feature_values = set(feature_values)
​
        label_ent = 0
        for feature_value in unique_feature_values:
            label_data_set = self.split_data_lable(data_set, axis, feature_value)
            label_ent += float(len(label_data_set)) / total_len * self.cul_entropy(label_data_set)
​
        return before_ent - label_ent
​
    def get_best_feature(self, data_set):
        """
        获得信息增益最大的一个特征
        :param data_set:
        :return: feature axis
        """
        features_len = len(data_set[0][:-1])
        before_ent = self.cul_entropy(data_set)
​
        label_gain = {}
        for axis in range(features_len):
            label_gain[axis] = self.cul_information_gain_label(before_ent, data_set, axis)
​
        return max(label_gain.iterkeys(), key=lambda k: label_gain[k])
​
    def split_data_lable(self, data_set, axis, feature_value):
        label_data_set = []
        for item in data_set:
            if item[axis] == feature_value:
                item_vec = item[:axis]
                item_vec.extend(item[axis + 1:])
                label_data_set.append(item_vec)
​
        return label_data_set
​
    def create_tree_id3(self, data_set, labels):
        class_list = [item[-1] for item in data_set]
        # 预剪枝 - 所有数据属于同一类型停止分枝
        if class_list.count(class_list[0]) == len(class_list):
            return class_list[0]
​
        best_feature = self.get_best_feature(data_set)
        best_feature_label = labels[best_feature]
        del(labels[best_feature])
        my_tree = {best_feature_label: {}}
​
        feature_values = [item[best_feature] for item in data_set]
        unique_feature_values = set(feature_values)
        for feature_value in unique_feature_values:
            sub_labels = labels[:]
            my_tree[best_feature_label][feature_value] = self.create_tree_id3(self.split_data_lable(data_set, best_feature, feature_value), sub_labels)
​
        return my_tree
​
    def fit(self, data_set, labels):
        for axis in range(len(labels)):
            self.__feature_labels[labels[axis]] = axis
​
        self.__tree = self.create_tree_id3(data_set, labels)
        print "tree:", self.__tree
​
    def predict_tree(self, tree, product):
        for key in tree:
            feature_value = product[self.__feature_labels[key]]
            if isinstance(tree[key][feature_value], dict):
                return self.predict_tree(tree[key][feature_value], product)
            else:
                return tree[key][feature_value]
​
    def predict(self, products):
        return [self.predict_tree(self.__tree, product) for product in products]
​
​
def load_data():
    labels = ['Outlook', 'Temperature', 'Humidity', 'Wind', 'Play']
    data_set = [
        ['Sunny', 'Hot', 'High', 'Weak', 'No'],
        ['Sunny', 'Hot', 'High', 'Strong', 'No'],
        ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],
        ['Rain', 'Mild', 'High', 'Weak', 'Yes'],
        ['Rain', 'Cool', 'Normal', 'Weak', 'Yes'],
        ['Rain', 'Cool', 'Normal', 'Strong', 'No'],
        ['Overcast', 'Cool', 'Normal', 'Strong', 'Yes'],
        ['Sunny', 'Mild', 'High', 'Weak', 'No'],
        ['Sunny', 'Cool', 'Normal', 'Weak', 'Yes'],
        ['Rain', 'Mild', 'Normal', 'Weak', 'Yes'],
        ['Sunny', 'Mild', 'Normal', 'Strong', 'Yes'],
        ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],
        ['Overcast', 'Hot', 'Normal', 'Weak', 'Yes'],
        ['Rain', 'Mild', 'High', 'Strong', 'No']
    ]
​
    return data_set, labels
​
​
if __name__ == '__main__':
    data_set, labels = load_data()
    dt = DecisionTree()
    dt.fit(data_set, labels)
​
    products = [
                ['Rain', 'Mild', 'High', 'Strong'],
                ['Overcast', 'Hot', 'High', 'Strong'],
                ]
​
    probs = dt.predict(products)
    print "probs:", probs

参考

• [1] 周志华.<<机器学习>>

• [2] 李航.<<统计学习方法>>

  
  关注公众号