决策树算法分析与应用

一：定义

决策树是一种迭代算法，先从第一个根节点选择变量进行拆分，直到所有变量都已经用尽，或者在某节点只能对等拆分（拆分后的两类包含的数据量相等）时，停止迭代。在每一个节点，都选择最大化信息增益的变量进行拆分。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每一个分支代表一个测试的输出，每个叶子节点代表一种类别。
比如下面这张图中内部节点是下雨、距离远；分支是从下雨节点出来的是、否，从距离远出来的是、否；叶子节点是地铁、步行。

二：决策树功能

决策树是一种预测模型，它代表的是对象属性与对象值之间的一种映射关系。比如：我们要预测一个大学生今天会干嘛（假设他平常的生活由聚会、学习、去酒吧、看电视等构成），我们可以这样分析：首先看他今天有没有聚会，有聚会的话他就去参加聚会，否则再看他有没有作业要交；如果没有作业要交的话，他就会选择去酒吧，如果作业很紧急的话，他就会选择学习，如果不是特别紧急的话，他就会选择在家；如果他选择懒惰在家的话，他就会选择看电视，否则的话他就会选择学习。这就是一个决策树的分析和产生过程，下面让我们来把这个决策树画出来。

三：决策树的优缺点

通过上面的分析以及决策树的构建，我们发现决策树非常容易理解和实现，具有很好的解释性。但是一个决策树往往会过拟合。为了解决这个问题，可以采用’事后剪枝法’。也就是说，为了防止决策树过于复杂，在构建好完整的树之后，在树的某个节点将树剪短。剪短的决策树往往具有更好的外推扩展能力。另外，如果要使用决策树来预测连续性变量，我们则需要将连续性变量离散化，具体采用何种方式离散化则需要根据数据集来定。最后一点是当类别增多的时候，错误可能就会增加的比较快。

四：特征选择

特征选择就是我们选择用哪个特征来划分空间，它对模型的好坏往往有着直接的影响。通常一个数据集中会包含许多的冗余信息，我们需要在其中寻找到那些对我们划分空间影响非常大的特征。那么如何判断应该选择哪个特征呢？
通常是这样的，如果选择某个特征对数据集进行划分之后，划分得到的子集的分类效果比选择其他任何一个特征的分类效果都好，那么就应该选择这个特征了。

五：熵

在信息论中，熵用来表示一个特征变量所包含的信息量，其定义如下：
$H(X)=-P(X=1)log_2(P(X=1))-P(X=0)log_2(P(X=0))$H(X)=−P(X=1)log2​(P(X=1))−P(X=0)log2​(P(X=0))
H(X)代表变量X的熵值，当P(X=0)=1或P(X=1)=1时，X的熵H(X)=0，当P(X=0)=P(X=1)=0.5时，X的熵最大。如下图所示：

六：信息增益

信息增益的定义如下，对于变量X，在给定一个变量值a的情况下，X熵值的减少量：
$IG(X,a)=H(X)-H(X|a)$IG(X,a)=H(X)−H(X∣a)
H(X|a)代表X给定属性的条件熵。假设a0是属性a的实际值，那么H(X|a=a0)表示在该属性值给定条件下X的条件熵。
$H(X|a=a0)=-p(X=1|a=a_0)log_2(p(X=1|a=a_0))-p(X=0|a=a_0)log_2(p(X=0|a=a_0))$H(X∣a=a0)=−p(X=1∣a=a0​)log2​(p(X=1∣a=a0​))−p(X=0∣a=a0​)log2​(p(X=0∣a=a0​))
假设a有n个属性值，那么H(X|a)的计算公式为：
$H(X|a)=\sum_{i=1}^n p(a=a_i)H(X|a=a_i)$H(X∣a)=i=1∑n​p(a=ai​)H(X∣a=ai​)
通俗的说，X给定属性a的条件熵指的是在知道属性a的取值之后，X熵值的减少量。因为熵代表了不确定性，也就是说，在知道a之后，我们对变量X有了新的认识，对它的不确定性减少了。从属性a的角度来说，就是它为我们进一步了解X所带来的额外信息量。

有了熵和信息增益的概念之后，我们就知道可以顺利的搭建决策树了：在摆放变量时，总是先摆放信息增益量最大的变量，因为它能够为我们了解X带来最大的信息量。

七：代码实现

import math
import operator

class DecisionTree:

    def __init__(self,trainData):
        self.trainData = trainData


    # 计算香农熵
    def calc_Shannon_Entropy(self,DataSet):
        '''
        :param DataSet: 数据集
        :return: 当前数据集的香农熵
        '''
        # 标签集合，统计每个标签出现的次数
        label_count = {}
        for row in DataSet:
            feature = row[-1]
            if feature in label_count.keys():
                label_count[feature] += 1
            else:
                label_count[feature] = 1

        # 计算当前数据集的香农熵
        Shannon_Entropy = 0.0
        for key in label_count:
            p = float(label_count[key])/len(DataSet)
            Shannon_Entropy -= p * math.log(p,2)

        return Shannon_Entropy

    # 划分数据集
    def split_DataSet(self,DataSet,axis,value):
        '''
        :param DataSet: 数据集
        :param axis: 划分的列号
        :param value: 划分的特征值
        :return: 划分后的子集
        '''
        split_dataset = []
        for row in DataSet:
            if row[axis] == value:
                reduce_data = row[:axis]
                reduce_data.extend(row[axis+1:])
                split_dataset.append(reduce_data)

        return split_dataset


    # 选择最优的划分方案
    def choose_best_feature_to_split(self,DataSet):
        '''
        :param DataSet: 数据集
        :return: 和原数据集熵差最大的划分对应的特征列号
        '''
        # 特征个数
        feature_number = len(DataSet[0]) - 1
        # 原数据集的香农熵
        base_Entropy = self.calc_Shannon_Entropy(DataSet)

        # 暂存最大熵增量
        best_Shannon = 0
        # 最好的特征划分对应的列号
        best_feature_column = -1

        # 按列遍历数据集
        for i in range(feature_number):
            # 获取该列所有特征
            fea_List = [row[i] for row in DataSet]
            # 将其转化为集合
            fea_Set = set(fea_List)

            new_Entropy = 0.0
            # 计算该特征划分下所有划分子集的香农熵之和
            for value in fea_Set:
                sub_dataSet = self.split_DataSet(DataSet,i,value)
                p = len(sub_dataSet)/float(len(DataSet))
                new_Entropy += p * self.calc_Shannon_Entropy(sub_dataSet)

            # information_Gain 信息增益 = 当前数据集的熵 - 已知某个特征之后的条件熵

            information_Gain = base_Entropy - new_Entropy
            if information_Gain > best_Shannon:
                best_Shannon = information_Gain
                best_feature_column = i

        return best_feature_column


    #采用多数表决的方式求出标签中出现次数最多的类标签
    def max_count_label(self,classify_list):
        '''
        :param classify_list: 分类标签集
        :return: 出现次数最多的标签
        '''
        class_count = {}

        for vote in classify_list:
            if vote in class_count.keys():
                class_count[vote] += 1
            else:
                class_count[vote] = 1
        # 根据字典的值将字典排序（降序）
        sorted_class_count = sorted(class_count.items(),key=operator.itemgetter(1),reverse=True)

        return sorted_class_count[0][0]

    # 创建决策树
    def CreateTree(self,DataSet,labels):
        '''
        :param DataSet: 数据集
        :param labels: 划分标签集（特征集）
        :return: 决策树
        '''
        classify_list = [row[-1] for row in DataSet]

        # 如果数据集内所有分类一致
        if classify_list.count(classify_list[0]) == len(classify_list):
            return classify_list[0]
        # 如果所有特征都划分完毕
        elif len(DataSet[0]) == 1:
            return self.max_count_label(classify_list)
        else:
            best_feature = self.choose_best_feature_to_split(DataSet)           # 选择最佳划分特征
            best_feature_label = labels[best_feature]                           # 最佳划分对应的划分标签
            my_tree = {best_feature_label:{}}                                   # 构建字典空树
            del(labels[best_feature])                                           # 从划分标签中删除划分的标签
            feature_value = [row[best_feature] for row in DataSet]              # 获取最佳划分对应特征的所有特征值
            feature_value_set = set(feature_value)                              # 特征唯一化

            for value in feature_value_set:                         # 逐行遍历特征值集合
                # 保存所有划分标签信息并将其划分后的数据集传入，进行下一次递归
                sub_labels = labels[:]
                my_tree[best_feature_label][value] = self.CreateTree(self.split_DataSet(DataSet,best_feature,value),sub_labels)

        return my_tree



def main():
    trainData = [
        [0, 0, 0, 0,'no'],
        [0, 0, 0, 1,'no'],
        [0, 1, 0, 1,'yes'],
        [0, 1, 1, 0,'yes'],
        [0, 0, 0, 0,'no'],
        [1, 0, 0, 0,'no'],
        [1, 0, 0, 1,'no'],
        [1, 1, 1, 1,'yes'],
        [1, 0, 1, 2,'yes'],
        [1, 0, 1, 2,'yes'],
        [2, 0, 1, 2,'yes'],
        [2, 0, 1, 1,'yes'],
        [2, 1, 0, 1,'yes'],
        [2, 1, 0, 2,'yes'],
        [2, 0, 0, 0,'no'],
    ]
    labels = ['年龄', '有工作','有自己的房子','信贷情况']
    DCT = DecisionTree(trainData)
    print(DCT.CreateTree(trainData,labels))

if __name__ == '__main__':
    main()

下面我们把这个表构建为决策树
这个表格反映了银行通过对一个人的评判，然后决定是否 给予其贷款

序号	年龄	有工作	有自己的房子	信贷情况	类别
0	青年	否	否	一般	否
1	青年	否	否	好	否
2	青年	是	否	好	是
3	青年	是	是	一般	是
4	青年	否	否	一般	否
5	中年	否	否	一般	否
6	中年	否	否	好	否
7	中年	是	是	好	是
8	中年	否	是	非常好	是
9	中年	否	是	非常好	是
10	老年	否	是	非常好	是
11	老年	否	是	好	是
12	老年	是	否	好	是
13	老年	是	否	非常好	是
14	老年	否	否	一般	否

• 年龄列：0代表青年；1代表中年；2代表老年
• 有工作列：0代表否；1代表是
• 有自己的房子列：0代表否；1代表是
• 信贷情况列：0代表一般；1代表好；2代表非常好

运行结果

{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

我们将字典形式的树画成决策树来看看：