机器学习笔记5：决策树

决策树简介

机器学习中，决策树（Decision Tree）是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。本文主要讲解ID3算法构造决策树。

学习决策树首先需要了解信息论中的熵（也称为香农熵，信息熵，Entropy）和信息增益（Information Gain）的概念。

熵的定义是信息的期望值，想要计算熵，首先我们需要知道怎么计算信息。如果待分类的事务可能划分在多个事务中，则符号$x_i$的信息定义为。

$$
\large
l(x_i) = -\log_2^{p(x_i)}
$$

由此有熵的计算公式。

$$
\large
E = -\sum_{i=1}^n p(x_i)log_2^{p(x_i)}
$$

信息增益的定义将一个数据集合的熵，减去原数据集减去某个指定特征属性的各个值之后的子数据集的熵的期望。数学公式如下。

$$
\large
IG(fea) = ent(ds) - \sum_{i=0}^{len(fea)}[p(v_i) \times ent(sub(ds,fea,v_i))]
$$

其中，
$IG(fea)$表示数据集中特征为$fea$的信息增益。
$ent(ds)$表示求数据集$ds$的熵。
$len(fea)$表示数据集中特征为$fea$的值的集合去重后的长度。
$v_i$表示特征$fea$的第$i$个取值。
$p(v_i)$表示$fea$取值为$v_i$概率。
$sub(ds,fea,v)$表示求数据集$ds$中的数据的键为$fea$且值为$v_i$时的子集，注意该子集不包括fea特征。

从信息增益的定义我们可以知道，当数据集中的某一个特征属性的信息增益越大，表明该特征含有的信息量越大。

下面是创建决策树的一般流程。

if 数据集中不存在多个特征：
    return 数据集
else:
    计算最佳划分数据集的最佳特征
    按计算出的特征划分数据集
    创建分支点
    for 每个划分的数据子集:
        递归调用本函数，参数为数据子集

构建决策树的过程的一个关键步骤就是划分数据，ID3算法采用信息增益划分数据（其他采用IG划分数据的算法还有C4.5，C5.0算法），其他算法还有采用基尼不纯度（Gini Impurity，用于分类回归树CART算法）等。

构建好决策树之后，就是用其来对新数据进行分类。分类过程比较简单，本文的Python实现小节中的源码的classify(dt, labels, vec)函数用于对新数据进行分类，代码较少，读者可自行阅读。

此外，构造决策树是很耗时的任务，然而用决策树进行分类却很快，因此，一般可以将决策树存储起来，以提升实际算法工作时的效率（Python中提供有pickle模块，用于存储结构化数据）。

示例

上图显示了一个完整的构件好了的决策树。

Python实现

# -*- coding: utf-8 -*-
"""
Decision Tree
by Charles Ouyang
2016.06.21
"""
import math
def create_data_set():
    """
    create training data set and labels
    :return: data set, labels
    """
    return [[1, 1, 0], [1, 1, 0], [1, 0, 0], [0, 0, 1], [0, 0, 1], [2, 2, 2], [2, 1, 1]], [0, 1]
def calc_entropy(data_set):
    """
    calculate entropy for the data set
    :param data_set:
    :return: entropy
    """
    # calculate probability for each category
    total_count = len(data_set)
    entry_dict = {}
    for vec in data_set:
        if vec[-1] not in entry_dict:
            entry_dict.setdefault(vec[-1], 1)
        else:
            entry_dict[vec[-1]] += 1
    # calculate the entropy
    entropy = .0
    for entry in entry_dict:
        probability = float(entry_dict[entry]) / total_count
        entropy -= probability * math.log(probability, 2)
    return entropy
def split_data_set(data_set, entry, value):
    """
    get child data set while value of specific entry of origin data set is specific
    :param data_set:
    :param entry:
    :param value:
    :return: split data set
    """
    data_result = []
    for vec in data_set:
        if vec[entry] == value:
            data_result.append(vec[:entry] + vec[entry + 1:])
    return data_result
def calc_information_gain(data_set, entry):
    """
    calculate information gain for data set and specific entry
    :param data_set:
    :param entry:
    :return: information gain
    """
    total_count = len(data_set)
    base_entropy = calc_entropy(data_set)
    value_dict = {}
    for vec in data_set:
        if vec[entry] not in value_dict:
            value_dict.setdefault(vec[entry], 1)
        else:
            value_dict[vec[entry]] += 1
    # calculate entropy for entry
    new_entropy = .0
    for value in value_dict:
        probability = float(value_dict[value]) / total_count
        new_entropy += probability * calc_entropy(split_data_set(data_set, entry, value))
    # return information gain
    return base_entropy - new_entropy
def calc_best_feature(data_set):
    """
    calculate the best feature of which information gain is the highest
    :param data_set:
    :return:
    """
    best_feature = 0
    best_ig = calc_information_gain(data_set, best_feature)
    for i in range(1, len(data_set[0]) - 1):
        cur_ig = calc_information_gain(data_set, i)
        if best_ig < cur_ig:
            best_ig = cur_ig
            best_feature = i
    return best_feature
def create_branch(data_set, labels):
    """
    create a decision tree branch
    :param data_set:
    :param labels:
    :return: a decision tree branch
    """
    categories = []
    for vec in data_set:
        categories.append(vec[-1])
    # if there is no feature in data set then return the most common category
    if len(data_set[0]) == 1:
        return max(set(categories), key=categories.count)
    # if there is only one category in data set then return it
    if len(categories) == categories.count(categories[0]):
        return categories[0]
    # calculate the best feature
    best_feature = calc_best_feature(data_set)
    branch = {labels[best_feature]: {}}
    # labels for next level, label of best feature removed
    labels_next_level = labels[:best_feature] + labels[best_feature + 1:]
    # storing handled values
    values = []
    # create children branches
    for vec in data_set:
        # if value not handled
        if vec[best_feature] not in values:
            values.append(vec[best_feature])
            # add branches to the tree
            branch[labels[best_feature]][vec[best_feature]] = create_branch(
                split_data_set(data_set, best_feature, vec[best_feature]), labels_next_level)
    # return the branch
    return branch
def classify(dt, labels, vec):
    """
    classify vector with decision tree
    :param dt: decision tree
    :param labels: feature labels
    :param vec: vector
    :return: category
    """
    key = dt.keys()[0]
    sub_tree = dt[key]
    key_index = labels.index(key)
    if type(sub_tree[vec[key_index]]).__name__ != 'dict':
        return sub_tree[vec[key_index]]
    else:
        return classify(sub_tree[vec[key_index]], labels, vec)
if __name__ == '__main__':
    # test code
    _data_set, _labels = create_data_set()
    _dt = create_branch(_data_set, _labels)
    _category = classify(_dt, _labels, [0, 0])
    print(_category)

决策树算法的优劣

优点：计算复杂度不高，输出结果易于理解，对中间缺失值不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
使用数据范围：数值型和标称型。

决策树简介

示例

Python实现

决策树算法的优劣

参考