决策树分类

引入

市面上有一款智能音箱是“天猫精灵”，它有一个功能是猜人物，具体操作是，用户在心里想一个人物（可以是明星、名著人物、虚拟人物等），然后天猫精灵会给出一系列问题，用户需要根据心中的人物的特点对天猫精灵的问题进行“是”或者“否”或者“不清楚”的回答，人们发现，在若干论回答后，天猫精灵总是能猜到用户想到的人物，比如猪八戒、陈冠希等。这个过程其实就是一个决策的过程，对于每一个问题进行是或否或者不清楚的回答，进行下一步的决策，逐渐缩小问题解的可行域，最终确定一个最可能的答案。我们经常使用决策树处理分类问题，近来的调查表明决策树也是最经常使用的数据挖掘算法。它之所以如此流行，一个很重要的原因就是不需要了解机器学习的知识，就能搞明白决策树是如何工作的。

如果你以前没有接触过决策树，完全不用担心，它的概念非常简单。即使不知道它也可以通过简单的图形了解其工作原理，图3-1所示的流程图就是一个决策树，长方形代表判断模块（ decision block），椭圆形代表终止模块（ terminating block），表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作分支（ branch），它可以到达另一个判断模块或者终止模块。

模型

我们可以想象决策树的整个过程，是目标逐渐确定的过程，也就是系统的熵越来越小的过程，越来越有序的过程。这一点也被著名克劳德·香农想到了，因此他提出使用信息熵来表示当前数据划分的置信程度，从而选择一个最好的划分，然后继续进行划分，直到构建完整的决策树。

如果看不明白什么是信息增益（ information gain）和熵（ entropy），请不要着急——它们自诞生的那一天起，就注定会令世人十分费解。克劳德·香农写完信息论之后，约翰·冯·诺依曼建议使用“熵”这个术语，因为大家都不知道它是什么意思。

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号$x_i$的信息定义为

其中$p(x_i)$是选择该分类的概率。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

克劳德·香农被公认为是二十世纪最聪明的人之一，威廉·庞德斯通在其2005年出版的 《财富公式》一书中是这样描写克劳德·香农的： “贝尔实验室和MIT有很多人将香农和爱因斯坦相提并论，而其他人则认为这种对比是不 公平的——对香农是不公平的。”

代码及其分析

数据集准备

这部分和其他分类算法相似：

通过离开水是否能存活（分量0）以及是否具有脚蹼（分量1）来判断一个输入是不是一个鱼类（分量2 ）

1
2
3
4
5
6
7
8
9
10
def create_dataset():
    train = [
        [1, 1, 'Yes'],
        [1, 1, 'yes'],
        [1, 0, 'No'],
        [0, 1, 'No'],
        [0, 1, 'No']
    ]
    labels = ["No surfacing", "Flippers"]
    return train, labels

计算某个数据集的香农熵

  • 计算每个类型出现的概率
    • 通过 dict() 类型来计数
    • 使用频率近似代替概率
  • 带入公式求解
1
2
3
4
5
6
7
8
9
10
11
def calc_shannon(dataset):
    n = len(dataset)
    cnt = {}
    for v in dataset:
        label = v[-1]
        cnt[label] = cnt.get(label, 0) + 1
    shannon = 0.0
    for label in cnt:
        prob = float(cnt[label]) / n
        shannon -= prob * log(prob, 2)
    return shannon

划分数据集

  • 把数据集 dataset 按照在 axis 分量的取值是否是 value 进行划分
  • 为了避免污染数据集，因此新创建了局部变量
  • 对于每一条记录，如果取值是 value 则在此处分开，并拼接这个属性之后的属性
  • 追加到答案中，最终返回
1
2
3
4
5
6
7
8
def split_dataset(dataset, axis, value):
    sub_dataset = []
    for record in dataset:
        if record[axis] == value:
            prev = record[:axis]
            prev.extend(record[axis + 1:])
            sub_dataset.append(prev)
    return sub_dataset

选择最优划分

  • 这一步中对每一个属性进行划分，选择其中可以让熵增最大的那一个属性的下标并返回
  • 由于数据集的特点，因此除了最后一项是标签之外其他都是属性
  • 如果熵增变大，则更新答案，最后返回结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def get_best_feat(dataset):
    n = len(dataset[0]) - 1
    base = calc_shannon(dataset)
    mx_gain, idx = 0.0, -1
    for i in range(n):
        feat_set = set([v[i] for v in dataset])
        nxt_shannon = 0.0
        for value in feat_set:
            subset = split_dataset(dataset, i, value)
            prob = len(subset) / len(dataset)
            nxt_shannon += prob * calc_shannon(subset)
        dealt = base - nxt_shannon
        if dealt > mx_gain:
            mx_gain = dealt
            idx = i
    return idx

建树和预测

在准备工作都做好之后就可以开始递归建树以及预测了，因为每一次都挑选了最优的划分，不断地划分到叶子结点（也就是最后的标签）就可以获得决策树

这里采用的数据结构是字典，每一个字典的 key 是结点， value是一个新的字典，代表这条分支的子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def majority_count(feat):
    counter = {}
    for f in feat:
        counter[f] = counter.get(f, 0) + 1
    sorted_counter = sorted(counter.items(), key=lambda x: x[1], reverse=True)
    return sorted_counter[0][0]


def create_tree(dataset, labels):
    feats = [d[-1] for d in dataset]
    if feats.count(feats[0]) == len(feats):
        return feats[0]
    if len(dataset[0]) == 1:
        return majority_count(feats)
    feat = get_best_feat(dataset)
    label = labels[feat]
    res = {label: {}}
    del(labels[feat])
    subset = set([d[feat] for d in dataset])
    for v in subset:
        sub_labels = labels[:]
        res[label][v] = create_tree(split_dataset(dataset, feat, v), sub_labels)
    return res

进行预测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def classify(tree, labels, vec):
    res = ""
    root = list(tree.keys())[0]
    fi, idx = tree[root], labels.index(root)
    for decision in fi.keys():
        if decision == vec[idx]:
            if type(fi[decision]).__name__ == 'dict':
                res = classify(fi[decision], labels, vec)
            else:
                res = fi[decision]
    return res


def main():
    dataset, labels = create_dataset()
    tree = create_tree(dataset, labels.copy())
    print(classify(tree, labels, [1, 0]))


if __name__ == '__main__':
    main()