决策树实战1

决策树简介

决策的构造

1.决策树的流程

（1）收集数据
（2）准备数据
比如下面的数据：

因为决策树只能处理数值型的数据，所以要准备特定的数据格式。
使用上面的数据表格中有两个特征和一个分类结果。可以像下面这样准备数据或者说构建特征向量。

    [1,1,'Y']
    [1,1,'Y']
    [1,0,'N']
    [0,1,'N']
    [0,1,'N']

其中第一，二列特征为’no surfacing’和’flippers’。
实现代码：

    dataset = [
    [1,1,'Y']
    [1,1,'Y']
    [1,0,'N']
    [0,1,'N']
    [0,1,'N']]
    labels = ['no surfacing','flippers']

（3）分析数据
（4）训练算法
（5）测试算法
（6）使用算法

2.决策树的构造

这里只介绍ID3算法构造决策树。
（1）评估每个特征，选择划分数据类别决定性的特征
（2）根据特征划分数据子集
（3）若子集中的数据不是同一个类型，根据另外一个特征继续划分子集，直到每一个特征下的所有子集的数据类型相同。

3.信息增益(information gain)和熵(entropy)

信息增益在这里理解为数据集划分前后信息发生的变化。
ID3算法是以最大信息增益为划分依据的算法。
熵指的是信息的期望值，定义为
l(xi)=−log2p(xi),p(xi)$l(x_i)=-lo{g}_{2}p(x_i),p(x_i)$为选择类别i$i$的概率
所有类别包含的信息期望值：
H=−∑ni=1p(xi)logxp(xi)$H=-\sum _{i=1}^{n}p(x_i)lo{g}_{x}p(x_i)$,其中n表示分类的数目。在上面的数据中类别只有2类，是鱼和不是鱼。

计算给定数据集的香浓熵
手算：
这里只有两个类别，是鱼和不是鱼，按照频率估算概率，得到P(Y)=2/5$P(Y)=2/5$,P(N)=3/5$P(N)=3/5$,这也称为经验概率。所以
H=−P(Y)log2P(Y)−P(N)log2P(N)=−25log225−35log235=0.97095$H=-P(Y)lo{g}_{2}P(Y)-P(N)lo{g}_{2}P(N)=-\frac{2}{5}lo{g}_2\frac{2}{5}-\frac{3}{5}lo{g}_2\frac{3}{5}=0.97095$

代码：

    from math import log

    def calShannonEntropy(dataset):
        num = len(dataset)
        label_liat = {}
        for x in dataset:
            label = x[-1]  # the last column is label
            if label not in label_liat.keys():
                label_liat[label]=0
            label_liat[label] += 1
        shannonEnt = 0.0
        for key in label_liat:
            prob = float(label_liat[key]/num)
            shannonEnt -= prob * log(prob,2)

        return shannonEnt

代码计算结果与手算的相同：0.9709505944546686

4. 划分数据集

我们根据最大信息增益最大的特征去划分数据集，提取出来多个子集，子集个数等于该特征的取值个数，比如上面的特征“是否有脚蹼”的取值就有两个“是”和“否”，根据是否有脚蹼，可以划分为两个子集。。
首先需要计算给定某个特征做划分时信息增益，然后根据信息增益去选择特征。

信息增益的计算：
在这个例子中，对于特征2，其中有脚蹼个数4个，没有脚蹼个数为1个。估算概率：

P(有脚蹼)=4/5,P(没有脚蹼)=1/5$$P(有脚蹼)=4/5,P(没有脚蹼)=1/5$$

有脚蹼子集的熵

H1=−P(Y)log2P(Y)−P(x)log2P(x)=−12∗log212−12∗log212=1$$H1=-P(Y)lo{g}_{2}P(Y)-P(x)lo{g}_{2}P(x)=-\frac{1}{2}\ast lo{g}_2\frac{1}{2}-\frac{1}{2}\ast lo{g}_2\frac{1}{2}=1$$

没有脚蹼子集的熵

H2=−P(Y)log2P(Y)−P(x)log2P(x)=0$$H2=-P(Y)lo{g}_{2}P(Y)-P(x)lo{g}_{2}P(x)=0$$

信息增益：
H(全集的熵)-[P(有脚蹼)H(有脚蹼子集的熵)+P(没有脚蹼)H(没有脚蹼子集的熵H)]=

0.97095−[45×1+15×0]=0.97095−45=0.17095$$0.97095-[\frac{4}{5}\times 1+\frac{1}{5}\times 0]=0.97095-\frac{4}{5}=0.17095$$

代码实现：

    def keyFeatureSelect(dataset):
        """
        通过信息增益判断哪个特征是关键特征并返回这个特征
        :param dataset: 输入数据集
        :return: 特征
        """
        num_feature = len(dataset[0])-1
        base_entropy = calShannonEntropy(dataset)
        bestInfogain = 0
        bestfeature = -1
        for i in range(num_feature):
            featlist = [example[i] for example in dataset]
            feat_value = set(featlist)
            feat_entropy = 0
            for value in feat_value:
                subset = splitDate(dataset,i,value)
                prob = len(subset)/float(len(dataset))
                feat_entropy += prob * calShannonEntropy(subset)
            infoGain = base_entropy - feat_entropy
            print("第%d个特征的信息增益%0.3f" %(i,infoGain))
            if (infoGain > bestInfogain):
                bestInfogain = infoGain
                bestfeature = i

        print("第%d个特征最关键" % i)
        return  bestfeature

5. 构建决策树

基于原始的数据集，选出了最好的特征开始划分多个子集；第一次划分之后，数据被传到树分支的下一个节点，在这个节点上再次划分数据。采用递归原则处理数据集。

递归调用很关键的是要给定递归出口，这里的条件是：历遍所有的划分数据集的属性或者每个分支下的所有实例都具有相同的分类。
进一步解释终止条件：
在划分上树的时候是消耗特征的，所以特征总能被历遍；
然而当历遍了所有的特征之后，类标签可能不是唯一的，这是需要使用投票的方式决定叶子的类别。

投票方式决定类别的代码：

    impor operator
    def voteClass(classlist):
        """
        通过投票的方式决定类别
        :param classlist: 输入类别的集合
        :return: 大多数类别的标签
        """
        classcount = {}
        for x in classlist:
            if x not in classcount.keys():classcount[x]=0
            classcount += 1
        sortclass = sorted(classcount.iteritems(),key = operator.itemgetter(1),reverse=True)

        return sortclass[0][0]

创建树的代码：

def createTree(dataset,labels):
        """
        递归构建树
        :param dataset: dataset
        :param labels: labels of feature
        :return:树
        """
        labelsCopy = labels[:]   # 原代码没有这个，结果第一次运行之后第一个特征被删除了，所以做了修改
        classList = [example[-1] for example in dataset]
        if classList.count(classList[0]) == len(classList): #判断所有类标签是否相同
            return classList[0]
        if len(dataset[0]) == 1: # 是否历遍了所有特征（是否剩下一个特征）
            return voteClass(classList)
        bestFeat = keyFeatureSelect(dataset)
        bestFeatLabel = labelsCopy[bestFeat]
        tree = {bestFeatLabel:{}} # 使用字典实现树
        del labelsCopy[bestFeat]
        featValues = [example[bestFeat] for example in dataset]
        uniqueValue = set(featValues)
        for value in uniqueValue:
            subLabels = labelsCopy[:] #复制类标签到新的列表中，保证每次递归调用不改变原始列表
            tree[bestFeatLabel][value] = createTree(splitDate(dataset,bestFeat,value),subLabels)
        return tree

6. 从准备数据到创建树的完整代码

from math import log

    def calShannonEntropy(dataset):
        """
        计算香浓熵
        :param dataset: 输入数据集
        :return: 熵
        """
        num = len(dataset)
        label_liat = {}
        for x in dataset:
            label = x[-1]  # the last column is label
            if label not in label_liat.keys():
                label_liat[label]=0
            label_liat[label] += 1
        shannonEnt = 0.0
        for key in label_liat:
            prob = float(label_liat[key]/num)
            shannonEnt -= prob * log(prob,2)

        print("数据集的香浓熵为%f" % shannonEnt)
        return shannonEnt


    def splitDate(dataset, axis, value):
        """
        根据某个特征划分数据集，
        :param dataset: 输入数据集
        :param axis: 数据集的每一列表示一个特征，axis取不同的值表示取不同的特征
        :param value: 根据这个特征划分的类别标记，在二叉树中常为2个，是或者否
        :return: 返回去掉了某个特征并且值是value的数据
        """
        newdataset = []
        for x in dataset:
            if x[axis] == value:
                reduceFeat = x[:axis]
                reduceFeat.extend(x[axis+1:])
                newdataset.append(reduceFeat)
        return newdataset

    def keyFeatureSelect(dataset):
        """
        通过信息增益判断哪个特征是关键特征并返回这个特征
        :param dataset: 输入数据集
        :return: 特征
        """
        num_feature = len(dataset[0])-1
        base_entropy = calShannonEntropy(dataset)
        bestInfogain = 0
        bestfeature = -1
        for i in range(num_feature):
            featlist = [example[i] for example in dataset]
            feat_value = set(featlist)
            feat_entropy = 0
            for value in feat_value:
                subset = splitDate(dataset,i,value)
                prob = len(subset)/float(len(dataset))
                feat_entropy += prob * calShannonEntropy(subset)
            infoGain = base_entropy - feat_entropy
            print("第%d个特征的信息增益%0.3f" %(i,infoGain))
            if (infoGain > bestInfogain):
                bestInfogain = infoGain
                bestfeature = i

        print("第%d个特征最关键" % i)
        return  bestfeature


    def voteClass(classlist):
        """
        通过投票的方式决定类别
        :param classlist: 输入类别的集合
        :return: 大多数类别的标签
        """
        import operator

        classcount = {}
        for x in classlist:
            if x not in classcount.keys():classcount[x]=0
            classcount += 1
        sortclass = sorted(classcount.iteritems(),key = operator.itemgetter(1),reverse=True)

        return sortclass[0][0]


    def createTree(dataset,labels):
        """
        递归构建树
        :param dataset: dataset
        :param labels: labels of feature
        :return:树
        """
        labelsCopy = labels[:]          # 原代码没有这个，结果第一次运行之后第一个特征被删除了，所以做了修改
        classList = [example[-1] for example in dataset]
        if classList.count(classList[0]) == len(classList): #判断所有类标签是否相同
            return classList[0]
        if len(dataset[0]) == 1: # 是否历遍了所有特征（是否剩下一个特征）
            return voteClass(classList)
        bestFeat = keyFeatureSelect(dataset)
        bestFeatLabel = labelsCopy[bestFeat]
        tree = {bestFeatLabel:{}} # 使用字典实现树
        del labelsCopy[bestFeat]
        featValues = [example[bestFeat] for example in dataset]
        uniqueValue = set(featValues)
        for value in uniqueValue:
            subLabels = labelsCopy[:] #复制类标签到新的列表中，保证每次递归调用不改变原始列表
            tree[bestFeatLabel][value] = createTree(splitDate(dataset,bestFeat,value),subLabels)
        return tree


    def decTreeClassify(inputTree, featLables, testVec):
        """
        使用决策树模型进行分类
        :param inputTree:
        :param featLables:
        :param testVec:
        :return:
        """
        firstStr = list(inputTree.keys())[0]    # 根节点
        secondDict = inputTree[firstStr]        # 节点下的值
        featIndex = featLables.index(firstStr)  # 获得第一个特征的label对应数据的位置
        for key in secondDict.keys():           # secondDict.keys()表示一个特征的取值
            if testVec[featIndex] == key:       # 比较测试向量中的值和树的节点值
                if type(secondDict[key]).__name__ == 'dict':
                    classLabel = decTreeClassify(secondDict[key], featLables, testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel


    def storeTree(inputTree, filename):
        """
        store the trained Tree.
        :param inputTree: the the trained Tree
        :param filename: save tree as file name
        :return: None
        """
        import pickle
        fw = open(filename,'wb')
        pickle.dump(inputTree,fw)
        fw.close()
        print("tree save as", filename)


    def grabTree(filename):
        """
        read stored tree from disk
        :param filename: the goal file
        :return: Tree
        """
        print("load tree from disk...")
        import pickle
        fr = open(filename,"rb")
        return pickle.load(fr)



    if __name__== '__main__':
        dataset = [
                    [1, 1,'Y'],
                    [1, 1,'Y'],
                    [1, 0,'N'],
                    [0, 1,'N'],
                    [0, 1,'N']]
        labels = ['no surfacing', 'flippers']

        shannonEnt = calShannonEntropy(dataset)
        keyfeature = keyFeatureSelect(dataset)
        tree = createTree(dataset,labels)
        print(tree)

7. 决策树的使用

训练好决策树之后如何使用模型来做分类？
输入：训练好的树模型；数据集的标签；待分类数据
分类过程：比较待分类数据与决策树上的数值，递归执行该过程知道进入叶子节点，最后将测试数据定义为叶子节点所属的类型。
输出：类别

实现代码：

    def decTreeClassify(inputTree, featLables, testVec):
        """
        使用决策树模型进行分类
        :param inputTree:
        :param featLables:
        :param testVec:
        :return:
        """
        firstStr = list(inputTree.keys())[0]    # 根节点
        secondDict = inputTree[firstStr]        # 节点下的值
        featIndex = featLables.index(firstStr)  # 获得第一个特征的label对应数据的位置
        for key in secondDict.keys():           # secondDict.keys()表示一个特征的取值
            if testVec[featIndex] == key:       # 比较测试向量中的值和树的节点值
                if type(secondDict[key]).__name__ == 'dict':
                    classLabel = decTreeClassify(secondDict[key], featLables, testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel

8. 存储决策树

使用Python模块pickle序列化对象，保存在磁盘中。

    def storeTree(inputTree, filename):
        """
        store the trained Tree.
        :param inputTree: the the trained Tree
        :param filename: save tree as file name
        :return: None
        """
        import pickle
        fw = open(filename,'wb')
        pickle.dump(inputTree,fw)
        fw.close()
        print("tree save as", filename)


    def grabTree(filename):
        """
        read stored tree from disk
        :param filename: the goal file
        :return: Tree
        """
        print("load tree from disk...")
        import pickle
        fr = open(filename,"rb")
        return pickle.load(fr)

可能会遇到下面的问题：
（1）执行 fw = open(filename,’wb’) 报错
TypeError: write() argument must be str, not bytes
Python3.x版本会报这个错，写入要以二进制写入，使用’wb’而不是原代码的’w’

（2）执行fr = open(filename,”rb”) 报错
UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0x80 in position 205: illegal multibyte sequence
解决办法1：
FILE_OBJECT= open(‘order.log’,’r’, encoding=’UTF-8’)
解决办法2：
FILE_OBJECT= open(‘order.log’,’rb’)

---

参考：《机器学习实战》