数据挖掘十大算法（一）：决策树算法 python和sklearn实现

大家好，欢迎来到IT知识分享网。

学完到第三章——决策树，python代码实现的仅是ID3算法，sklearn为优化过的C4.5，这里做一个详细的总结包括（原理、代码、可视化、scikit-learn实现），皆为亲自实践后的感悟。以下进入正文。

早前简单了解了决策树的原理，然后为了尽快使用便没有深究直接使用sklearn实现，虽然sklearn使用起来极其极其的方便，但是我还是想理解到其中的代码实现机制以及一些数学知识，所以在《机器学习实战》的第三章我结合它的思路用自己的代码实现了（香农熵、信息增益、创建决策树字典、可视化决策树）。思路和代码都不是很难，较容易理解。这样实践后最大的收获不仅是代码的编写能力，还有什么样的数据以及如何调整数据集才能更好的适用于决策树。（个人代码主要数据格式为DataFrame）

这里补充几个知识点：

    1：数据集种类(目标变量)越多越复杂熵越大，所以原始数据的熵最大

    2：熵公式：   n代表X的n种不同的离散取值，pi代表X取值为i的概率，log以2或e为底的对数

    3：信息增益(简单处理)：原始数据熵-目前特征的熵

决策树原理：（这里只是重点描述，决策树还是涉及很多知识的，详细请参考更多博文）

    1：求得每个特征的熵，与目前原始数据熵比较从而得到该特征的信息增益。

    2：从中选出信息增益最大的那个最优特征，将它取出来当作当前节点。

    3：排除当前节点，递归继续重复1、2步骤。

    4：两个条件结束3的递归。1：当前节点下目标变量唯一。 2：所有特征都循环完了。

上面的4点是创建决策树中最关键的点，也是其基本原理，围绕这四个点我们可以创建出简单的决策树，下面为代码段。

代码实现：

下面是创建的测试数据集，当然复杂的数据集都能实现，只要满足该DataFrame格式

from math import log
import pandas as pd
import numpy as np
#数据集种类越多越复杂熵越大

#创建数据集 （返回DataFrame）
def createdata():
    data = pd.DataFrame({'water':[1,1,1,0,0],'feet':[1,1,0,1,1],'survive':['yes','yes','no','no','no']})
    return data

#计算香农熵  （DataFrame）
def calculateshang(data):
    names = data[data.columns[-1]]      #依据公式求某列特征的熵 目标变量作为概率依据
    n = len(names)
    labels = {}
    for i,j in names.value_counts().items():
        labels[i] = j
    shang = 0
    for i in labels:            #利用循环求熵
        pi = labels[i]/n
        shang -= pi * log(pi,2)
    return shang

#划分数据集  （DataFrame,特征列名,该列某个特征值）
def splitdataSet(data,feature,feature_value):
    recvdata = []
    n = len(data)
    for i in range(n):          #如果该行的这个特征值==循环到的这个特征值，去掉该特征加入返回列表
        if(data.iloc[[i],:][feature].values[0] == feature_value):
            temp = data.iloc[[i],:]  #问题一：DataFrame如何取一行为Series，就可以直接drop了
            k = temp.index.values[0]
            temp_t = temp.ix[k]         #问题二：DataFrame为什么这里使用iloc或loc不行，明明我是按照位置取值的而非行号
            tem = temp_t.drop(feature)
            recvdata.append(tem)
    recvDF = pd.DataFrame(recvdata)     #将满足条件的所有行定义为DataFrame
    return recvDF

#得出最好的特征名，用来划分数据集 （DataFrame）
def choosebestfeaturetosplit(data):
    nameFeatures = data.columns
    baseEntropy = calculateshang(data)  #基础最大原始香农熵
    bestinfoGain = 0.0                  #初始化最好信息增益
    bestFeature = -1                    #初始化最好的特征名
    for Feature in nameFeatures[:-1]:   #循环所有特征
        uniquevalue = set(data[Feature])#该特征的所有唯一值
        newEntropy = 0.0            #中间熵
        for value in uniquevalue:
            subdata = splitdataSet(data,Feature,value)
            pi = len(subdata) / len(data)
            newEntropy += pi * calculateshang(subdata)
        infoGain = baseEntropy - newEntropy     #中间信息增益
        if(infoGain > bestinfoGain):
            bestinfoGain = infoGain
            bestFeature = Feature   #循环比较所有特征，返回信息增益最大的特征列名
    return bestFeature

#若创建数结束后目标变量仍不唯一，则以最多的一类为准  (Series)
def major_k(classlist):
    classcount = classlist.value_counts()
    result = classcount.sort_values(ascending=False).index[0]
    return result

#建立决策树  （DataFrame）（返回dict）： {'water': {0: 'no', 1: {'food': {0: 'no', 1: 'yes'}}}}
def createtree(data):
    labels = data.columns
    classlist = data[labels[-1]]
    if(len(classlist.values) == classlist.value_counts()[0]):   #结束条件1：该分支目标变量唯一
        return classlist.values[0]
    if(len(labels) == 1):                          #结束条件2：所有特征名都循环完了
        return major_k(classlist)   #这里并不能直接返回目标变量名，可能不唯一，所以调用major_k
    bestFeature = choosebestfeaturetosplit(data)
    myTree = {bestFeature:{}}   #这里很巧妙，以此来创建嵌套字典
    unique = set(data[bestFeature])
    for value in unique:
        myTree[bestFeature][value] = createtree(splitdataSet(data,bestFeature,value))   #递归创建树
    return myTree

#分类器预测  （嵌套字典 列表特征名 列表测试数据）
def classfiy(myTree,labels,test):
    firstStr = list(myTree.keys())[0]       #需要获取首个特征的列号，以便从测试数据中取值比较
    secondDict = myTree[firstStr]           #获得第二个字典
    featIndex = labels.index(firstStr)      #获取测试集对应特征数值
    for key in secondDict.keys():
        if(test[featIndex] == key):
            if(type(secondDict[key]).__name__ == 'dict'):       #判断该值是否还是字典，如果是，则继续递归
                classlabel = classfiy(secondDict[key],labels,test)
            else:
                classlabel = secondDict[key]
    return classlabel

#画决策树pdf图   （DataFrame）
def showtree_pdf(data):
    from sklearn import tree    #导入sklearn的决策树模型（包括分类和回归两种）
    import pydotplus    #画句子的依存结构树

    a = data.iloc[:,:-1]    #特征矩阵
    b = data.iloc[:,-1]     #目标变量
    clf = tree.DecisionTreeClassifier() #分类决策树
    clf.fit(a,b)
    dot_data = tree.export_graphviz(clf, out_file=None) #利用export_graphviz将树导出为Graphviz格式
    graph = pydotplus.graph_from_dot_data(dot_data)
    graph.write_pdf("iris1.pdf")  #保存树图iris.pdf到本地

if __name__=="__main__":
    data = createdata() #创建数据集

    myTree = createtree(data)   #创建嵌套字典树
    print(myTree)

    result = classfiy(myTree,list(data.columns),[1,0])  #预测测试数据
    print(result)

    showtree_pdf(data)    #使用sklearn和pydotplus来画决策树，windows需要提前安装graphviz工具

下面结果第一行是嵌套字典格式的决策树，第二行为预测值(没问题)

下面是我使用sklearn构建的模型再用pydotplus库和graphviz绘制的pdf图，graphviz需要到这里下载msi来安装，然后添加系统路径。

讲讲这个决策树图的含义（很多人的博客抄袭别人就是画个图，我感觉他都不知道这个图什么意思。。。由于没找到参考，以下个人理解总结）：

    1：X[0]表示第一个节点特征(这里为water)的值，<=0.5(特征值)可以分为两类，目标变量不唯一的3个数据再判断X[1]第二个节点特征feet

    2：gini系数越小，不纯度越低，特征越好(叶子节点很纯gini=0)

    3：samples表示当前节点的样本数

    4：目标变量有多少个离散变量种类，value列表长度就多长（例如：no、yes为两个：[3个no,2个yes]）

——————————————————————————————————————————–

好了以上便是有关决策树简单实现的所有内容，从头编写一次代码，理解底层原理，接触原始数据后基本算是决策树入门了，那么为了提高编码和工作效率我们可以使用sklearn来极为方便的实现。

sklearn决策树算法类库内部实现是使用了调优过的CART树算法，既可以做分类(DecisionTreeClassifier)，又可以做回归(DecisionTreeRegressor)，两者参数几乎一致，部分意义有差别。

C4.5为优化过的ID3算法，改进：

    1：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性不足；

    2：在树构造过程中进行剪枝；

    3：能够完成对连续属性的离散化处理；

    4：能够对不完整数据进行处理。

这里我还会提到一个很方便、很爽的方法Categorical。

    如果使用我上面编写的代码那么则可以处理数据特征为非数值型的特征值，但是如果要在sklearn中使用决策树模型那么则需要将没有大小的离散型值转换为数值如：[red,blue,yellow]->[0,1,2]，这里我们使用Categorical可以轻松实现。下面是转换、画图完整代码。

原始数据：

代码：

import pandas as pd
import numpy as np
#数据集种类越多越复杂熵越大

#画决策树pdf图   （DataFrame）
def showtree_pdf(data):
    from sklearn import tree    #导入sklearn的决策树模型（包括分类和回归两种）
    import pydotplus    #画句子的依存结构树

    a = data.iloc[:,:-1]    #特征矩阵
    b = data.iloc[:,-1]     #目标变量
    clf = tree.DecisionTreeClassifier() #分类决策树
    clf.fit(a,b)    #训练
    dot_data = tree.export_graphviz(clf, out_file=None) #利用export_graphviz将树导出为Graphviz格式
    graph = pydotplus.graph_from_dot_data(dot_data)
    graph.write_pdf("iris4.pdf")  #保存树图iris.pdf到本地

def change(data):
    names = data.columns[:-1]
    for i in names:
        col = pd.Categorical(data[i])
        data[i] = col.codes
    print(data)

if __name__=="__main__":
    data = pd.read_table('lenses.txt',header=None,sep='\t') #读取文件
    change(data)        #转换非大小离散型为数值型
    showtree_pdf(data)  #画pdf图

看看转换后的数据：

再看看决策图pdf：

相当的简单方便，如果需要预测直接使用predict方法就行，当然模型里面有很多的参数可能需要调整，这也就是为什么我们需要深入了解底层的原理，这样能帮助我们理解如何去调参。参数博客参考

以上为全部内容，有问题还请还请指教。