决策树算法

参考链接：

https://blog.csdn.net/asialee_bird/article/details/81118245

https://blog.csdn.net/github_39261590/article/details/76546281

---

决策树算法：ID3、C4.5、CART
ID3：选择信息熵增益最大的feature作为node，实现对数据的归纳分类。
C4.5：是ID3的一个改进，比ID3准确率高且快，可以处理连续值和有缺失值的feature。
CART：使用基尼指数的划分准则，通过在每个步骤最大限度降低不纯洁度，CART能够处理孤立点以及能够对空缺值进行处理。

三种决策树总结：
ID3：取值多的属性，更容易使数据更纯，其信息增益更大。
C4.5：采用信息增益率替代信息增益。
CART：以基尼系数替代熵，最小化不纯度，而不是最大化信息增益。

---

1.ID3算法：
核心思想：信息增益(information gain)---表示两个信息熵的差值
以信息增益作为分裂属性选取的依据，信息增益表示某个属性能够为分类系统带来多少“信息”，
信息越多，则通过该属性对数据集的分类更为准确.

第一步：
首先计算未分类前的熵，总共有8位同学，男生3位，女生5位。
熵（总）=-3/8log2(3/8)-5/8log2(5/8)=0.9544

第二步：
分别计算同学A和同学B分类后信息熵
同学A首先按头发分类，分类后的结果为：长头发中有1男3女。短头发中有2男2女。
熵（同学A长发）=-1/4log2(1/4)-3/4log2(3/4)=0.8113
熵（同学A短发）=-2/4log2(2/4)-2/4log2(2/4)=1
熵（同学A）=4/8*0.8113+4/8*1=0.9057
信息增益（同学A）=熵（总）-熵（同学A）=0.9544-0.9057=0.0487

第三步：
同学B按声音特征来分，分类后的结果为：声音粗中有3男3女。声音细中有0男2女。
熵（同学B声音粗）=-3/6log2(3/6)-3/6log2(3/6)=1
熵（同学B声音粗）=-2/2log2(2/2)=0
熵（同学B）=6/81+2/8*0=0.75
信息增益（同学B）=熵（总）-熵（同学A）=0.9544-0.75=0.2087

结论：按同学B的方法，先按声音特征分类，信息增益更大，区分样本的能力更强，更具有代表性。
存在的缺点：
1.ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。
信息增益的缺点是倾向于选择取值较多是属性，在有些情况下这类属性可能不会提供太多有价值的信息。
2.ID3算法只能对描述属性为离散型属性的数据集构造决策树。

---

2.C4.5算法：引入信息增益率的概念
它克服了ID3算法无法处理属性缺失和连续属性的问题，并且引入了优化决策树的剪枝方法，使算法更高效，适用性更强。

信息增益率本质： 是在信息增益的基础之上乘上一个惩罚参数，特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

缺点：信息增益率偏向取值较少的特征。（跟ID3正好相反）

使用情况：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

---

3.CART算法用基尼指数：
代替了信息熵，用二叉树作为模型结构，所以不是直接通过属性值进行数据划分，该算法要在所有属性中找出最佳的二元划分。
CART算法通过递归操作不断地对决策属性进行划分，同时利用验证数据对树模型进行优化。

---

代码实现：ID3算法_v1

from math import log
import operator

def calcShannonEnt(dataSet):  # 计算数据的熵(entropy)
    numEntries=len(dataSet)  # 数据条数
    labelCounts={}
    for featVec in dataSet:
        currentLabel=featVec[-1] # 每行数据的最后一个字（类别）
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1  # 统计有多少个类以及每个类的数量
    shannonEnt=0
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
        shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
    return shannonEnt

def createDataSet1():    # 创造示例数据
    dataSet = [['长', '粗', '男'],
               ['短', '粗', '男'],
               ['短', '粗', '男'],
               ['长', '细', '女'],
               ['短', '细', '女'],
               ['短', '粗', '女'],
               ['长', '粗', '女'],
               ['长', '粗', '女']]
    labels = ['头发','声音']  #两个特征
    return dataSet,labels

def splitDataSet(dataSet,axis,value): # 按某个特征分类后的数据
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec =featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):  # 选择最优的分类特征
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)  # 原始的熵
    bestInfoGain = 0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet,i,value)
            prob =len(subDataSet)/float(len(dataSet))
            newEntropy +=prob*calcShannonEnt(subDataSet)  # 按特征分类后的熵
        infoGain = baseEntropy - newEntropy  # 原始熵与按特征分类后的熵的差值
        if (infoGain>bestInfoGain):   # 若按某特征划分后，熵值减少的最大，则次特征为最优分类特征
            bestInfoGain=infoGain
            bestFeature = i
    return bestFeature

def majorityCnt(classList):    #按分类后类别数量排序，比如：最后分类为2男1女，则判定为男；
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=0
        classCount[vote]+=1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels):
    classList=[example[-1] for example in dataSet]  # 类别：男或女
    print(classList)
    if classList.count(classList[0])==len(classList):
        return classList[0]
    if len(dataSet[0])==1:
        return majorityCnt(classList)

    bestFeat=chooseBestFeatureToSplit(dataSet) #选择最优特征
    bestFeatLabel=labels[bestFeat]
    myTree={bestFeatLabel:{}} #分类结果以字典形式保存
    del(labels[bestFeat])

    featValues=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featValues)
    for value in uniqueVals:
        subLabels=labels[:]
        myTree[bestFeatLabel][value]=createTree(splitDataSet\
                            (dataSet,bestFeat,value),subLabels)
    return myTree


if __name__=='__main__':
    dataSet, labels=createDataSet1()  # 创造示列数据
    result=createTree(dataSet, labels)
    print(result)  # 输出决策树模型结果

---

代码实现：ID3算法_v2

# -*- coding: UTF-8 -*-
from math import log
import operator
 
 
 
"""
放贷对象判断：
年龄：0代表青年，1代表中年，2代表老年；
有工作：0代表否，1代表是；
有自己的房子：0代表否，1代表是；
信贷情况：0代表一般，1代表好，2代表非常好；
类别(是否给贷款)：no代表否，yes代表是。
"""
def createDataSet():
    dataSet = [[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 = ['年龄', '有工作', '有自己的房子', '信贷情况']        #分类属性
    return dataSet, labels                           #返回数据集和分类属性

"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
    dataSet：数据集
Returns:
    shannonEnt：经验熵(香农熵)
"""
def calcShannonEnt(dataSet):
    numEntires = len(dataSet)                        #返回数据集的行数
    labelCounts = {}                                 #保存每个标签(Label)出现次数的字典
    for featVec in dataSet:                          #对每组特征向量进行统计
        currentLabel = featVec[-1]                   #提取标签(Label)信息
        if currentLabel not in labelCounts.keys():   #如果标签(Label)没有放入统计次数的字典,添加进去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1               #Label计数
        
    shannonEnt = 0.0                                 #经验熵(香农熵)
    for key in labelCounts:                          #计算香农熵
        prob = float(labelCounts[key]) / numEntires  #选择该标签(Label)的概率
        shannonEnt -= prob * log(prob, 2)            #利用公式计算
    return shannonEnt                                #返回经验熵(香农熵)
 
 
"""
函数说明:按照给定特征划分数据集
Parameters:
    dataSet - 待划分的数据集
    axis - 划分数据集的特征
    value - 需要返回的特征的值
"""
def splitDataSet(dataSet, axis, value):
    retDataSet = []                                     #创建返回的数据集列表
    for featVec in dataSet:                             #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]             #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet                                   #返回划分后的数据集
 
 
"""
函数说明:选择最优特征
Parameters:
    dataSet - 数据集
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值
"""
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1                     #特征数量
    baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
    bestInfoGain = 0.0                                    #信息增益
    bestFeature = -1                                      #最优特征的索引值
    for i in range(numFeatures):                          #遍历所有特征
        #获取dataSet的第i个所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)                         #创建set集合{},元素不可重复
        newEntropy = 0.0                                   #经验条件熵
        for value in uniqueVals:                           #计算信息增益
            subDataSet = splitDataSet(dataSet, i, value)           #subDataSet划分后的子集
            prob = len(subDataSet) / float(len(dataSet))           #计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet)        #根据公式计算经验条件熵
        infoGain = baseEntropy - newEntropy                        #信息增益
        print("第%d个特征的增益为%.3f" % (i, infoGain))             #打印每个特征的信息增益
        if (infoGain > bestInfoGain):                              #计算信息增益
            bestInfoGain = infoGain                                #更新信息增益，找到最大的信息增益
            bestFeature = i                                        #记录信息增益最大的特征的索引值
    return bestFeature                                             #返回信息增益最大的特征的索引值
 
 
"""
函数说明:统计classList中出现此处最多的元素(类标签)
Parameters:
    classList - 类标签列表
Returns:
    sortedClassCount[0][0] - 出现此处最多的元素(类标签)
"""
def majorityCnt(classList):
    classCount = {}
    for vote in classList:                                        #统计classList中每个元素出现的次数
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)        #根据字典的值降序排序
    return sortedClassCount[0][0]                                #返回classList中出现次数最多的元素
 
 
"""
函数说明:递归构建决策树
Parameters:
    dataSet - 训练数据集
    labels - 分类属性标签
    featLabels - 存储选择的最优特征标签
Returns:
    myTree - 决策树
"""
def createTree(dataSet, labels, featLabels):
    classList = [example[-1] for example in dataSet]               #取分类标签(是否放贷:yes or no)
    if classList.count(classList[0]) == len(classList):            #如果类别完全相同则停止继续划分
        return classList[0]
    if len(dataSet[0]) == 1:                                       #遍历完所有特征时返回出现次数最多的类标签
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)                   #选择最优特征
    bestFeatLabel = labels[bestFeat]                               #最优特征的标签
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树
    del(labels[bestFeat])                                          #删除已经使用特征标签
    featValues = [example[bestFeat] for example in dataSet]        #得到训练集中所有最优特征的属性值
    uniqueVals = set(featValues)                                   #去掉重复的属性值
    for value in uniqueVals:
        subLabels=labels[:]
        #递归调用函数createTree(),遍历特征，创建决策树。
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels)
    return myTree
 
 
"""
函数说明:使用决策树执行分类
Parameters:
    inputTree - 已经生成的决策树
    featLabels - 存储选择的最优特征标签
    testVec - 测试数据列表，顺序对应最优特征标签
Returns:
    classLabel - 分类结果
"""
def classify(inputTree, featLabels, testVec):
    firstStr = next(iter(inputTree))             #获取决策树结点
    secondDict = inputTree[firstStr]             #下一个字典
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel
 
 
if __name__ == '__main__':
    dataSet, labels = createDataSet()
    featLabels = []
    myTree = createTree(dataSet, labels, featLabels)
    print(myTree)
    testVec = [0, 1]     # 测试数据
    result = classify(myTree, featLabels, testVec)
    if result == 'yes':
        print('放贷')
    if result == 'no':
        print('不放贷')

---

代码实现：ID3算法（sklearn调用）

from sklearn import tree
from numpy import *
import numpy as np

def loadDataSet(fileName):
    dataMat = []
    labelMat = []
    with open(fileName) as fr:
        for line in fr.readlines():
            lineArr = line.strip().split('    ')
            dataline = list(map(float, lineArr))
            
            dataMat.append([float(dataline[0]), float(dataline[1]), float(dataline[2])])
            labelMat.append(int(dataline[3]))
    return dataMat, labelMat


def createDataSet():
    dataSet = [[0, 0, 0, 0],         #数据集
               [0, 0, 0, 1],
               [0, 1, 0, 1],
               [0, 1, 1, 0],
               [0, 0, 0, 0],
               [1, 0, 0, 0]]
    labels = [0, 0, 1, 1, 0, 0]        #分类属性
    return dataSet, labels                           #返回数据集和分类属性


#加载训练集
dataSet1, labels1 = loadDataSet('img/txt/left.txt')   #1.加载一个txt数据集
dataSet1=np.array(dataSet1, dtype='float32')
print(dataSet1.shape)

dataSet2, labels2 = createDataSet()
# print(dataSet, labels)

#1）sklearn实现分类（二分类、多分类均可以）
clf=tree.DecisionTreeClassifier(criterion='entropy',splitter='best')   #entropy:信息增益，gini:基尼指数
clf=clf.fit(dataSet1, labels1)

test=[[1,0,0]]
print(clf.predict(test))   #预测属于哪个类
print(clf.predict_proba(test))   #预测属于每个类的概率
print(clf.feature_importances_)   #特征权重
 
# 把树写入文件
# with open("tree.dot", 'w') as f:  
#     f = tree.export_graphviz(clf, out_file=f)  

# #2)sklearn实现树回归
# #注意：回归的时候y的值应该是浮点数，而不是整数值
# clf=tree.DecisionTreeRegressor()
# clf=clf.fit(dataSet2, labels2)

# test=[[0,0,0,0]]
# print(clf.predict(test))



# criterion:
# 在决策树分类时，可选择“gini”，表示采用基尼系数，即CART算法；选择“entropy”，表示采用信息增益。
# 在决策树回归时，可选择“mse”，表示采用均方差；选择“mae”，表示采用与均值之差的绝对值的和。

# splitter，表示特征划分点选择策略，可选"best"或者"random"，默认设置是“best”
# best在特征的所有划分点中找出最优的划分点。
# random是随机的在部分划分点中找局部最优的划分点。
# 默认的"best"适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐"random" 。

# max_depth，表示决策树的最大深度，默认设置为None。（即剪枝，超过n层则剪掉）

# min_samples_split，表示结点再划分所需最小样本数，可选，默认设置为2
# 可以选择int或者float，如果某结点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。

# min_samples_leaf，表示叶结点所需的最少样本数，可选，默认值为1
# 如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 

# max_leaf_nodes，表示最大叶结点数，可选，默认为None。
# 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。
# 如果加了限制，算法会建立在最大叶子节点数内最优的决策树。

# min_impurity_decrease，表示结点减少的最小不纯度，也是一种阀值，可选，默认为0.0。
# 可选float。如果加权的不纯度减少量(基尼系数，信息增益，均方差，绝对差)超过阀值，则该结点将会被继续分割 。

# min_impurity_split，表示结点划分的最小不纯度，也是一种阀值，默认为None。
# 可选float。如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。