机器学习算法---决策树

1、决策树的分类

在建立一棵决策树的过程中，一个很重要的问题就是：怎么样将树干分叉？
由此问题，便引申出了三种基本的决策树：

1. ID3：利用数据集的信息增益来划分，在介绍信息增益之前先来了解一下熵的概念。
   对于一个数据集，其熵定义如下：
   
   H=−∑i=1np(xi)log2p(xi)
   
   其中 p(xi) 为 xi 为某一类别的概率。
   根据香农信息理论，信息熵表示了信息的不确定度，当数据集呈均匀分布时，熵最大。
   那么，在分类之前数据集的信息熵是可以计算得到的，它和划分后的数据集的信息熵的差值即为信息增益。这里有一个划分好坏的判断标准，对于一个特定的数据集，它的信息熵是一定的，若根据某一规则将数据集划分后，数据集的信息熵越小，说明数据集的不确定度越小，即数据间的差异越小，此时信息增益越大。从而得出，信息增益越大，划分方式越好。
2. C4.5: 利用数据集的信息增益比来划分数据集，从ID3进化而来，避免了分类决策时偏向于取值较多的特征的问题。
3. CART树：采用基尼系数作为分类标准。基尼系数具有以下特点：（1）基尼系数是一种不等性度量；（2）值介于0-1之间，0表示完全相同，1表示完全不同，基尼系数越大，数据集越混乱。

2、决策树的剪枝

当根据训练数据集生成一棵决策树后，由于训练数据集的局限性，往往会发生“过拟合”的情形。也就是将数据的类别分的过于细致，使得结果不准确并且树过于臃肿。此时需要进行“剪枝”。
剪枝的方法一般有：预剪枝和后剪枝两种。对于剪枝方法的详细介绍可参考这篇文章剪枝。

3、python实现决策树分类

from math import log
import operator

'''******************************python实现决策树******************************'''
'''加载数据集'''
def loadData():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
return dataSet, labels
'''计算数据集的熵，熵越小，分类效果越好'''
def calShang(data):
    num=len(data)
#特征的字典，键值为字典，值为特征个数
    classCount={}
for feat in data:
        featVec=feat[-1]
#若字典中不存在此键值，则创建
if featVec not in classCount.keys():
            classCount[featVec]=0
        classCount[featVec]+=1
    Shang=0.0
for key in classCount:
        prob=classCount[key]/float(num)
        Shang-=prob*log(prob,2)
return Shang
'''分割数据集，根据特征值value分割'''
def splitData(data,axis,value):
    retData=[]
for dataList in data:
if dataList[axis]==value:
            newData=dataList[:axis]
            newData.extend(dataList[axis+1:])
            retData.append(newData)
return retData
'''根据数据集的熵值大小，寻找最优的数据集划分方式'''
def findOptSplit(data):
#特征变量的个数
    numFeat=len(data[0])-1
#先将原始数据集的熵值作为最小的熵值
    bestShang=calShang(data)
for i in range(numFeat):
        Shang=0.0
        featList=[feat[i] for feat in data]
        featSet=set(featList)
for value in featSet:
            splData=splitData(data,i,value)
            prob=len(splData)/float(len(data))
            Shang+=prob*calShang(splData)
if Shang<bestShang:
            bestShang=Shang
            bestFeat=i
return bestFeat
'''获取出现次数最多的类别名称'''
def majorityCnt(classList):
    classCount={}
for vote in classList:
if vote not in classCount.keys():
            classCount=0
        classCount[vote]+=1
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount
'''创建树'''
def createTree(dataSet,labels):
    classList=[example[-1] for example in dataSet]
#如果类别相同，则返回当前类别
if classList.count(classList[0])==len(classList):
return classList[0]
#如果只存在一个数据，则返回当前最多的类别
if len(dataSet[0])==1:
return majorityCnt(classList)
#寻找最好的数据集划分方式
    bestFeat=findOptSplit(dataSet)
    bestFeatLbel=labels[bestFeat]
    myTree={bestFeatLbel:{}}
#删除当前特征
del(labels[bestFeat])
    featValues=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featValues)
for value in uniqueVals:
        subLabels=labels[:]
        myTree[bestFeatLbel][value]=createTree(splitData(dataSet,bestFeat,value),subLabels)
return myTree

4、sklearn实现决策树分类

'''******************************sklearn实现决策树******************************'''
#分类问题
def sklearn_TreeClassi():
import numpy as np
from sklearn.datasets import load_iris
from sklearn import tree
import os
    os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin/'
#加载数据集
    iris=load_iris()
    x=iris.data[:,[0,2]]
    y=iris.target
#训练决策树
    clf=tree.DecisionTreeClassifier(max_depth=4)
    clf.fit(x,y)
#导出为Graphviz格式
from sklearn.externals.six import StringIO
import pydotplus
with open("iris.dot",'w') as f:
        f=tree.export_graphviz(clf,out_file=f)
'''可视化方法1---在命令行执行'''
#dot -Tpdf iris.dot -o iris.pdf
'''可视化方法2'''
    dot_data=StringIO()
    tree.export_graphviz(clf,out_file=dot_data)
    graph=pydotplus.graph_from_dot_data(dot_data.getvalue())
#导出到PDF
# graph.write_pdf("iris.pdf")
    x_min,x_max=x[:,0].min()-1,x[:,0].max()+1
    y_min,y_max=x[:,1].min()-1,x[:,1].max()+1
    xx,yy=np.meshgrid(np.arange(x_min,x_max,0.1),
                      np.arange(y_min,y_max,0.1))
    z=clf.predict(np.c_[xx.ravel(),yy.ravel()])
    z=z.reshape(xx.shape)

import matplotlib.pyplot as plt
    plt.contourf(xx,yy,z,alpha=0.4)
    plt.scatter(x[:,0],x[:,1],c=y,alpha=0.8)
    plt.show()

5、sklearn实现决策树回归

#回归问题
def sklearn_TreeRegressor():
    import numpy as np
    from sklearn.tree import DecisionTreeRegressor
    import matplotlib.pyplot as plt

    rng=np.random.RandomState(1)
x=np.sort(5*rng.rand(80,1),axis=0)
y=np.sin(x).ravel()
y[::5]+=3*(0.5-rng.rand(16))

    regr_1=DecisionTreeRegressor(max_depth=2)
    regr_2=DecisionTreeRegressor(max_depth=5)
    regr_1.fit(x,y)
    regr_2.fit(x,y)

    x_test=np.arange(0.0,5,0.01)[:,np.newaxis]
    y_1=regr_1.predict(x_test)
    y_2=regr_2.predict(x_test)

    plt.figure()
    plt.scatter(x,y,s=20,edgecolors="black",
                c="darkorange",label="data")
    plt.plot(x_test,y_1,color="cornflowerblue",
             label="max_depth=2",linewidth=2)
    plt.plot(x_test,y_2,color="yellowgreen",label="max_depth=5",linewidth=2)
    plt.xlabel("data")
    plt.ylabel("target")
    plt.title("Decision Tree Regression")
    plt.legend()
    plt.show()