决策树

Roy

2017-10-17

决策树是机器学习中一种简单明了的分类算法，用程序语言描述就是if...elif...else...，关键问题则是如何选择合适的特征对数据集进行切割，常见算法有： ID3、C4.5、CART等。

今天主要记录一下ID3这个算法，想使用这个算法首先要了解信息增益，想了解信息增益则要先明白什么是"熵”。熵描述了一个系统的混乱复杂程度，有一个理论叫做"熵增加”，含义就是一个没有外力干涉的系统混乱程度总是增加的，比如一个房间如果没人打扫的话只会越来越混乱，而不会自己变得整洁。

计算熵的公式如下：

$$H=-\sum_{i=i}^{n}P(x_i)log_2P(x_i)$$

其中$P(x_i)$ 表示P发生的概率。

举个栗子，比如我们有下面这些数据：

饮料	肉类	水果	闹肚子
牛奶	牛肉	香蕉	否
可乐	鸭肉	苹果	否
可乐	鸡肉	香蕉	是
牛奶	猪肉	苹果	否
咖啡	鱼肉	香蕉	是

上面记录了食物和是否闹肚子之间的关系，那么闹肚子的概率2/5不闹肚子的概率是3/5，所以整个样本的熵就是：

$$-{2 \over 5}log_2{2 \over 5} - {3 \over 5}log_2{3 \over 5}\approx0.971$$

当水果吃香蕉的时候，闹肚子的概率为2/3不闹肚子的概率是1/3，所以当吃香蕉时候条件熵为： $$-{2 \over 3}log_2{2 \over 3} - {1 \over 3}log_2{1 \over 3}\approx0.918$$

同理，吃苹果时候从来不闹肚子，所以条件熵为0。

那么在特征"水果"上的信息增益就是：

0.971 - ((3/5)*0.918+(2/5)*0) = 0.42

注意计算信息增益时候需要将 条件熵乘以这个情形发生的概率 。

同理可以求得特征"饮料"的信息增益：0.571和特征"肉类"的信息增益：0.971。

选择信息增益最大的特征来分割数据，所以选肉类。

计算熵的代码如下:

from math import log

def create_dataset():
    """构造数据集"""
    return [
        ['milk','beef','banana','N'],
        ['coca','fish','apple','N'],
        ['coca','beef','banana','Y'],
        ['milk','pork','apple','N'],
        ['coffee','fish','banana','Y'],
    ],['drink','meat','fruit']


def split_dataset(dataset,col,val):
    """切分col列值为val的数据集"""
    res_dataset = []
    for each in dataset:
        if each[col] == val:
            temp = each[:]
            temp.remove(val)
            res_dataset.append(temp)
    return res_dataset


def calc_shannon_ent(dataset):
    """计算熵"""
    count = len(dataset)
    labels = {}
    for each in dataset:
        label = each[-1]
        if label not in labels.keys():
            labels[label] = 0
        labels[label] += 1
    ent = 0
    for one in labels.keys():
        prod = labels[one] / count
        temp = prod * log(prod, 2)
        ent += temp
    return -ent


dataset,labels = create_dataset()
print(calc_shannon_ent(dataset))
sub_data = split_dataset(dataset,2,'banana')
print(sub_data)
print(calc_shannon_ent(sub_data))

输出如下：

0.9709505944546686
[['milk', 'beef', 'N'], ['coca', 'chicken', 'Y'], ['coffee', 'fish', 'Y']]
0.9182958340544896

接下来就是计算信息增益：

def choose_feature2split(dataset):
    """返回信息增益最高的特征是第几列"""
    best_infogain = 0
    best_feature_col = -1
    all_count = len(dataset)
    base_ent = calc_shannon_ent(dataset) # 整个样本的熵

    feature_num = len(dataset[0]) - 1 # 这里有2个前提:数据集中列数相同，且最后一列为标签

    for i in range(feature_num):
        feat_list = set([each[i] for each in dataset]) # 得到某特征有多少不同的值

        ent_temp = 0
        for feat in feat_list:
            sub_dataset = split_dataset(dataset,i,feat)
            prob = len(sub_dataset) / all_count # 计算这种条件发生的概率

            ent_temp += prob * calc_shannon_ent(sub_dataset)
        tmp_infogain = base_ent - ent_temp
        print("col:%s,gain:%s" % (i,tmp_infogain))
        if tmp_infogain > best_infogain:
            best_infogain = tmp_infogain
            best_feature_col = i
    return best_feature_col

输出如下：

col:0,gain:0.5709505944546686
col:1,gain:0.9709505944546686
col:2,gain:0.4199730940219749

ID3算法优点就是理解起来比较容易，缺点则是容易造成 过拟合 问题，另外在某些极端情况下，比如某个特征每一行值都独一无二(比如例子中的肉类)，这个算法倾向于优先根据此特征划分，效率极差。而且这个算法没法处理连续型数据，比较适合 类别较少的离散数据。

也因为如此，所以C4.5算法中使用 信息增益率 替换了信息增益判断，具体细节以后再写。接下来构造树：

def create_tree(dataset,labels):
    cls_list = [each[-1] for each in dataset] # 前提是最后一列为标签

    if len(set(cls_list)) == 1:
        # 当标签只剩一种时候返回

        return cls_list[0]
    best_feat_col = choose_feature2split(dataset)
    best_feat_label = labels[best_feat_col]
    tree = {best_feat_label:{}}
    for val in set([each[best_feat_col] for each in dataset]):
        sub_labels = labels[:]
        del(sub_labels[best_feat_col])
        tree[best_feat_label][val] = create_tree(split_dataset(dataset,best_feat_col,val),sub_labels)
    return tree

输出如下：

dataset,labels = create_dataset()
tree = create_tree(dataset,labels)

{'meat': {'beef': 'N', 'chicken': 'Y', 'duck': 'N', 'fish': 'Y', 'pork': 'N'}}

可以看出，根据上面示例构造出的决策树仅仅根据meat来决定。

将原始数据集修改一下：

def create_dataset():
    return [
        ['milk', 'beef', 'banana', 'N'],
        ['coca', 'fish', 'apple', 'N'],
        ['coca', 'beef', 'banana', 'Y'],
        ['milk', 'pork', 'apple', 'Y'],
        ['coffee', 'fish', 'banana', 'Y'],
    ],['drink','meat','fruit']

可以得到下面这中决策树：

{'drink': {'coca': {'meat': {'beef': 'Y', 'fish': 'N'}},
           'coffee': 'Y',
           'milk': {'meat': {'beef': 'N', 'pork': 'Y'}}}}

接下来进行分类：

def classify(tree, labels, test_vec):
    root_label = list(tree.keys())[0]  # py3中keys是一个生成器

    sub_tree = tree[root_label]
    feat_col = labels.index(root_label)  # 找到特征是第几列

    for key in sub_tree.keys():
        if test_vec[feat_col] == key:
            if isinstance(sub_tree[key], dict):
                cls_label = classify(sub_tree[key], labels, test_vec)  # 判断节点

            else:
                cls_label = sub_tree[key]  # 叶子节点

    return cls_label

print(classify(tree,labels,['milk','beef','apple']))
N

输出了N，但如果我们把beef改成fish这种不在决策树中的情况，则会报错。这点也说明了这个算法的过拟合缺点。