[人工智能]初识决策树

决策树的生成主要分以下两步，这两步通常通过学习已经知道分类结果的样本来实现。

1. 节点的分裂：一般当一个节点所代表的属性无法给出判断时，则选择将这一节点分成2个

子节点（如不是二叉树的情况会分成n个子节点）

2. 阈值的确定：选择适当的阈值使得分类错误率最小 （Training Error）。

比较常用的决策树有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。

ID3: 由增熵（Entropy）原理来决定那个做父节点，那个节点需要分裂。对于一组数据，熵越小说明分类结果越好。熵定义如下：

Entropy＝- sum [p(x_i) * log2(P(x_i) ]

其中p(x_i) 为x_i出现的概率。假如是2分类问题，当A类和B类各占50%的时候，

Entropy = - （0.5*log_2( 0.5)+0.5*log_2( 0.5))= 1

当只有A类，或只有B类的时候，

Entropy= - （1*log_2( 1）+0）=0

枚举每个属性，计算熵减

熵减为父节点的熵减去所有子节点的熵

import numpy as np
import pandas as pd
import operator
from math import log

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

def chooseMaxNum(dataset):
    cnt={}
    for i in dataset:
        if i not in cnt.keys():
            cnt[i]=0
        cnt[i]+=1
    tmp=sorted(cnt.items(),key=operator.itemgetter(1),reverse=1)
    return tmp[0][0]

def calEntropy(dataset):
    pass

def splitdata(dataset,bestFeat,value):
    tmp=[]
    for row in dataset:
        if(row[bestFeat]==value):
            atmp=row[:bestFeat]
            atmp.extend(row[bestFeat+1:])
            tmp.append(atmp)
    return tmp

def cal(dataset):
    n=len(dataset)
    cnt={}
    for row in dataset:
        if row[-1] not in cnt.keys():
            cnt[row[-1]]=0
        cnt[row[-1]]+=1
    entropy=0.0
    for row in cnt:
        p=float(cnt[row])/n
        entropy-=log(p,2)*p
    return entropy


def chooseBestFeat(dataset):
    m=len(dataset[0])-1
    n=float(len(dataset))
    baseEntropy=cal(dataset)
    bestInfoGain,bestFeat=0.0,-1
    for i in range(m):
        featset=set([row[i] for row in dataset])
        ans=0.0
        for j in featset:
            splitset=splitdata(dataset,i,j)
            ans+=cal(splitset)*len(splitset)/n
        ans=baseEntropy-ans
        if ans>bestInfoGain:
            bestInfoGain=ans
            bestFeat=i
    return bestFeat


def createTree(dataset,labels):
    result=[row[-1] for row in dataset]
    if result.count(result[0])==len(result):
        return result[0]
    if len(dataset[0])==1:
        return chooseMaxNum(dataset)
    bestFeat=chooseBestFeat(dataset)
    bestFeatLabels=labels[bestFeat]
    myTree={bestFeatLabels:{}}
    del(labels[bestFeat])
    featSet=[x[bestFeat] for x in dataset]
    featSet=set(featSet)
    for i in featSet:
        sublabel=labels[:]
        myTree[bestFeatLabels][i]=createTree(splitdata(dataset,bestFeat,i),sublabel)
    return myTree


def classify(myTree,labels,testdata):
    nowfeat=list(myTree.keys())[0]
    secondTree=myTree[nowfeat]
    featIndex=labels.index(nowfeat)
    featvalue=testdata[featIndex]
    ans=secondTree[featvalue]
    if isinstance(ans,dict):
        classLabel=classify(ans,labels,testdata)
    else:
        classLabel=ans
    return classLabel


def fishTest():
    dataset,labels=createDataSet()
    import copy
    myTree=createTree(dataset,copy.deepcopy(labels))
    print(myTree)
    print(classify(myTree,labels,[1,1]))


if __name__ == '__main__':
    fishTest()

结果：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
yes

C4.5：通过对ID3的学习，可以知道ID3存在一个问题，那就是越细小的分割分类错误率越小，所以ID3会越分越细。为了避免分割太细，c4.5对ID3进行了改进，C4.5中，优化项要除以分割太细的代价，这个比值叫做信息增益率，显然分割太细分母增加，信息增益率会降低。除此之外，其他的原理和ID3相同。

CART：分类回归树，CART是一个二叉树

CART只能将一个父节点分为2个子节点。CART用GINI指数来决定如何分裂：

GINI指数：总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）。

CART还是一个回归树，回归解析用来决定分布是否终止。理想地说每一个叶节点里都只有一个类别时分类应该停止，但是很多数据并不容易完全划分，或者完全划分需要很多次分裂，必然造成很长的运行时间，所以CART可以对每个叶节点里的数据分析其均值方差，当方差小于一定值可以终止分裂，以换取计算成本的降低。

CART和ID3一样，存在偏向细小分割，即过度学习（过度拟合的问题），为了解决这一问题，对特别长的树进行剪枝处理，直接剪掉。

以上的决策树训练的时候，一般会采取Cross-Validation法