虽然学习的慢了点,但是一直在学习,距离上次的 KNN 过去已经有一段时间了,这段时间学习了决策树。

什么是决策树

决策树隶属于有监督学习的一种。简单的来说就是根据属性分类,采用树状结构建立模型。每个非叶子节点都是一个 if-else 条件判断条件。叶子节点为数据类型。

最典型的例子就是

图中可以看到,通过一步一步缩小范围最终把结果锁定在某一个或者某一些类别中。这就是决策树的原理。

决策树的建立

建立决策树最重要的一个概念就是信息增益。信息增益就是在每一个节点进行分类的的时候起关键指导作用的条件判断部分。说的直白一点就是,信息分类的依据。

信息增益依赖信息熵。

信息熵又叫香农熵。熵表示信息分布的均匀性(信息的不确定性),信息分布的越均匀信息熵就越大,信息的不确定定就越大。

信息增益 = 熵(分类前)- 熵(分类后)

信息增益可以衡量一个特征对于分类影响的大小。增益越大,则表明此特增对于分类的影响越大。

熵的计算公式:

选择A作为分类节点分类后熵的计算公式:

解释一下上边两个公式:

到这里基本上决策树中重要的理论部分就介绍完了。

准备工作

接下来准备样本。

dataSet = [
    [1, 3, 0, 1, 'no'],
    [1, 3, 0, 2, 'no'],
    [2, 3, 0, 1, 'yes'],
    [3, 2, 0, 1, 'yes'],
    [3, 1, 1, 1, 'yes'],
    [3, 1, 1, 2, 'no'],
    [2, 1, 1, 2, 'yes'],
    [1, 2, 0, 1, 'no'],
    [1, 1, 1, 1, 'yes'],
    [3, 2, 1, 1, 'yes'],
    [1, 2, 1, 2, 'yes'],
    [2, 2, 0, 2, 'yes'],
    [2, 3, 0, 1, 'yes'],
    [3, 2, 0, 2, 'no']
]
labels = ['age','salary','isStudent','credit']

解释一下,在 dataSet 中一共有 14 条样本,每个样本中前 4 个值为样本的属性,最后一个值为样本的类型标签,标签表示当前这个人是否购买电脑。labels 中有四个值,分别对应样本中前 4 个值的描述(年龄、工资、是否是学生,信用度)。

代码

创建决策树

首先先从创建树开始

def create_tree(self, dataset, classes, feat_names):
''' 根据当前数据集递归创建决策树
:param dataset: 数据集
:param feat_names: 数据集中数据相应的特征名称
:param classes: 数据集中数据相应的类型
:param tree: 以字典形式返回决策树
'''
# 如果数据集中只有一种类型停止树分裂
if len(set(classes)) == 1:
return classes[0]

# 如果遍历完所有特征,返回比例最多的类型
if len(feat_names) == 0:
return self.get_majority(classes)

# 分裂创建新的子树
tree = {}
best_feat_idx = self.choose_best_split_feature(dataset, classes)
feature = feat_names[best_feat_idx]
tree[feature] = {}

# 创建用于递归创建子树的子数据集
sub_feat_names = feat_names[:]
sub_feat_names.pop(best_feat_idx)

splited_dict = self.split_dataset(dataset, classes, best_feat_idx)
for feat_val, (sub_dataset, sub_classes) in splited_dict.items():
tree[feature][feat_val] = self.create_tree(sub_dataset,sub_classes, sub_feat_names)
self.tree = tree
self.feat_names = feat_names
return tree

从方法中可以看出,这里是通过递归来创建决策树的。

接下来一行一行的来剖析。

首先,判断数据集中是否只有一种类型,如果只有一种类型则返回唯一的类型,代表分裂出了最终结果,结束分裂。
然后,再判断是否所有特征都遍历完成。如果所有特征都遍历完成,则代表分类已经结束,同样需要结束分裂。这里我们需要对结果中的分类进行统计,返回占比最高的类型。在统计分类占比的时候,定义了一个方法 get_majority(classes)

def get_majority(classes):
''' 返回类型中占据大多数的类型
'''
cls_num = defaultdict(lambda: 0)
for cls in classes:
cls_num[cls] += 1
return max(cls_num, key=cls_num.get)

然后创建一棵空的树 tree={}

接下来一行

best_feat_idx = self.choose_best_split_feature(dataset, classes)

选择一个最优的分裂点。具体代码如下:

def choose_best_split_feature(self, dataset, classes):
    ''' 根据信息增益确定最好的划分数据的特征
    :param dataset: 待划分的数据集
    :param classes: 数据集对应的类型
    :return: 划分数据的增益最大的属性索引
    '''
    base_entropy = self.get_shanno_entropy(classes)

    feat_num = len(dataset[0])
    entropy_gains = []
    for i in range(feat_num):
        splited_dict = self.split_dataset(dataset, classes, i)
        new_entropy = sum([
            len(sub_classes) / len(classes) * self.get_shanno_entropy(sub_classes)
            for _, (_, sub_classes) in splited_dict.items()
        ])
        entropy_gains.append(base_entropy - new_entropy)
    return entropy_gains.index(max(entropy_gains))

最优分裂点的选择方法是:遍历所有分裂点的信息增益,选择信息增益最大的分裂点即为最优分裂点。这里涉及到了另外的几个操作。

熵的计算

base_entropy = self.get_shanno_entropy(classes)

    def get_shanno_entropy(self, values):
        ''' 根据给定列表中的值计算其Shanno Entropy
        '''
        values = [a for a in values]
        uniq_vals = set(values)
        val_nums = {key: values.count(key) for key in uniq_vals}
        probs = [v / len(values) for k, v in val_nums.items()]
        entropy = sum([-prob * log2(prob) for prob in probs])
        return entropy

上边计算熵的代码对应了熵的计算公式。这里就不细说了。

切分数据集

split_dataset(dataset, classes, i)

def split_dataset(dataset, classes, feat_idx):
    ''' 根据某个特征以及特征值划分数据集
    :param dataset: 待划分的数据集, 有数据向量组成的列表.
    :param classes: 数据集对应的类型, 与数据集有相同的长度
    :param feat_idx: 特征在特征向量中的索引
    :param splited_dict: 保存分割后数据的字典 特征值: [子数据集, 子类型列表]
    '''
    splited_dict = {}
    for data_vect, cls in zip(dataset, classes):
        feat_val = data_vect[feat_idx]
        sub_dataset, sub_classes = splited_dict.setdefault(feat_val, [[], []])
        sub_dataset.append(data_vect[: feat_idx] + data_vect[feat_idx+1: ])
        sub_classes.append(cls)
    return splited_dict

在这个方法中,最重要的就是分裂这一步,在这一步中主要是删除向量中的分裂属性,把其他属性重新组成向量。

继续回到创建决策树的方法中。
接下来的一行,遍历分裂后的数据字典,递归创建树。出现两种情况是会停止递归。

以上就是决策树的创建过程。

利用构建的决策树对数据进行分类

def classify(self, data_vect, feat_names=None, tree=None):
    ''' 根据构建的决策树对数据进行分类
    '''
    if tree is None:
        tree = self.tree

    if feat_names is None:
        feat_names = self.feat_names

    # Recursive base case.
    if type(tree) is not dict:
        return tree

    feature = list(tree.keys())[0]
    value = data_vect[feat_names.index(feature)]
    f_tree = tree[feature]
    sub_tree = f_tree[value]

    return self.classify(data_vect, feat_names, sub_tree)

从代码中可以看出来,分类的过程也是通过递归来实现的。

拓展

相对来说构建树的过程是比较消耗时间的,所以我们可以将生成的决策树保存成二进制文件,这样下次就可以加载已经构建好的树来进行使用。所以这里写一下保存树和加载树的代码。保存对象数据这里使用 python 的 pickle 包。

所以在写代码之前需要先引入类库。

import pickle
def dump_tree(self, filename, tree=None):
    ''' 存储决策树
    '''
    if tree is None:
        tree = self.tree

    with open(filename, 'wb') as f:
        pickle.dump(tree, f)
def load_tree(self, filename):
    ''' 加载树结构
    '''
    with open(filename, 'rb') as f:
        tree = pickle.load(f)
        self.tree = tree
    return tree

测试代码

使用我们之前构造的测试数据进行测试。

#!/usr/bin/env python  
# encoding: utf-8  

"""
@version: v1.0 
@author: zhangyw
@site: http://blog.zhangyingwei.com
@software: PyCharm 
@file: decision_tree_app.py 
@time: 2017/11/22 15:01 
"""
import os
from ml.classify.decision_tree.decision_tree import DecisionTree

dataSet = [
    [1, 3, 0, 1, 'no'],
    [1, 3, 0, 2, 'no'],
    [2, 3, 0, 1, 'yes'],
    [3, 2, 0, 1, 'yes'],
    [3, 1, 1, 1, 'yes'],
    [3, 1, 1, 2, 'no'],
    [2, 1, 1, 2, 'yes'],
    [1, 2, 0, 1, 'no'],
    [1, 1, 1, 1, 'yes'],
    [3, 2, 1, 1, 'yes'],
    [1, 2, 1, 2, 'yes'],
    [2, 2, 0, 2, 'yes'],
    [2, 3, 0, 1, 'yes'],
    [3, 2, 0, 2, 'no']
]
labels = ['age','salary','isStudent','credit']

model = DecisionTree()
data_set = [item[0:4] for item in dataSet]
feat_names = labels
classes = [item[4] for item in dataSet]
model.create_tree(data_set,classes,feat_names)
tree_file_name = "decision_tree.pkl"
if os.path.exists(tree_file_name):
    model.load_tree(tree_file_name)
else:
    model.create_tree(data_set,classes,feat_names)
    model.dump_tree(tree_file_name)
test_vect = data_set[8]
res = model.classify(test_vect,feat_names)
print(res)

以上就是整个决策树的过程了,感觉不是很完善,但是目前也就这么多了。后续如果有什么补充的话再说吧!!!