机器学习实战笔记 – 决策树(Decision Tree)

Intro

决策树的核心算法有多种实现,如在机器学习技法介绍的C&RT,以及未涉及的C4.5,以及本书中介绍的ID3。

对于ID3,我们首先定义某个符号或者分类\(x_i\)的信息如下:

$$l(x_i) = -\log_{2}{p(x_i)}$$

其中,\(p(x_i)\)为某符号或者分类在训练集\(D_{train}\)中在所有的符号或者分类中出现的频率,接着我们定义信息熵\(H\):

$$H = – \sum^{n}_{i=1} p(x_i) \log_{2}{p(x_i)}$$

可以看出,信息熵\(H\)其实是求所有符号或分类的期望。

在本节中,决策树的构建算法将选择一个特征及其取值对训练集进行分割,使用该特征及其取值分割训练集可以使得分割后的\(n\)子训练集集信息熵相对于原信息熵增益最大,然后再递归地对子训练集使用该算法,直到训练集特征归一,即无法继续分割。

决策树算法具有如下特点:

优点:计算复杂度低、图形化表示后具有树形结构易于理解、对数据缺失不敏感。

缺点:如果没有Regularization,会出现Overfitting。

适用数据类型:数值型、标称型。

Algorithm

  1. 数据预处理,本算法只支持标称型数据,需要将所有的数值型数据转化为标称型;
  2. 构建决策树根节点,计算原始信息熵,初次选择最佳分割特征,存储最佳分割特征索引;
  3. 根据最佳分割特征及其取值分割训练集,得到的子训练集将原最佳特征列移除;
  4. 对于每一个得到的子训练集重复步骤2到步骤4,直到没有特征可以分割;
  5. 返回决策树;

Code

由于函数与变量名严格按照Objective-C风格命名,表意清晰,故将注释略去。

def create_decision_tree(data_set, tags):

    labels = [vector[-1] for vector in data_set]

    if labels.count(labels[0]) == len(labels):
        return labels[0]

    if len(data_set[0]) == 1:
        return classify(labels)

    best_split_feature_index = get_index_of_best_split_feature(data_set)

    best_split_feature_tag = tags[best_split_feature_index]

    decision_tree = {best_split_feature_tag: {}}

    del(tags[best_split_feature_index])

    best_split_features = [vector[best_split_feature_index] for vector in data_set]

    best_split_features_set = set(best_split_features)

    for best_split_feature in best_split_features_set:

        sub_tags = tags[:]

        sub_data_set = split_data_set(data_set, best_split_feature_index, best_split_feature)

        sub_decision_tree = create_decision_tree(sub_data_set, sub_tags)

        decision_tree[best_split_feature_tag][best_split_feature] = sub_decision_tree

    return decision_tree

Summary

以上是对决策树算法在机器学习实战中的总结,在下一节我们将介绍朴素贝叶斯。