监督学习之树模型（4）-- CART算法

在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼不纯度来代替信息增益比，基尼不纯度越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

基尼不纯度
给出概率分布的基尼不纯度定义：

1、执行步骤

step 1：计算基尼不纯度、分裂后的基尼不纯度来选择最好的数据集划分特征
step 2：选取分裂后基尼不纯度最小的特征作为根节点划分数据集，创建分支节点
step 3：对每个分支进行判定类别是否相同。相同则停止划分，不同则按照上述方法继续进行划分。

2、代码实现

基于CART算法构建决策树

# coding:utf-8
'''
CART决策树算法
'''
import numpy as np
import math

#========================================================
#  生成训练集
#========================================================

def createDataSet():
    dataSet = [['青年', '否', '否', '一般', '拒绝'],
               ['青年', '否', '否', '好', '拒绝'],
               ['青年', '是', '否', '好', '同意'],
               ['青年', '是', '是', '一般', '同意'],
               ['青年', '否', '否', '一般', '拒绝'],
               ['中年', '否', '否', '一般', '拒绝'],
               ['中年', '否', '否', '好', '拒绝'],
               ['中年', '是', '是', '好', '同意'],
               ['中年', '否', '是', '非常好', '同意'],
               ['中年', '否', '是', '非常好', '同意'],
               ['老年', '否', '是', '非常好', '同意'],
               ['老年', '否', '是', '好', '同意'],
               ['老年', '是', '否', '好', '同意'],
               ['老年', '是', '否', '非常好', '同意'],
               ['老年', '否', '否', '一般', '拒绝'],
              ]
    featureName = ['年龄', '有工作', '有房子', '信贷情况']
    return dataSet, featureName

#========================================================
#  计算基尼不纯度
#========================================================

def get_Gini(dataSet):
    '''
    计算给定数据集的基尼不纯度
    '''
    # 为分类创建字典
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts.setdefault(currentLabel, 0)
        labelCounts[currentLabel] += 1

    # 计算基尼不纯度
    Gini = 0.0
    temp = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / len(dataSet) 
        temp += prob ** 2
    Gini = 1 - temp
    return Gini

#========================================================
#  数据集分割和分裂后基尼不纯度
#========================================================

def splitDataSet(dataSet, axis, value):
    '''
    按照给定的特征列及特征值划分数据集
    INPUT --> 数据集, 特征列序号, 特征值
    OUTPUT --> 符合该特征的所有实例并且自动移除掉这维特征
    '''

    # 循环遍历dataSet中的每一行数据，返回不含划分特征的子集
    output = []
    for featVec in dataSet:
        if featVec[axis] == value:
            smallFeatVec = featVec[:axis]
            smallFeatVec.extend(featVec[axis+1:])
            output.append(smallFeatVec)
    return output

def get_CondGini(dataSet, axis, uniqueVals):
    '''
    计算给定数据集划分的基尼不纯度
    INPUT --> 数据集, 目标特征列序号, 目标特征列的值域
    OUTPUT --> 该划分的基尼不纯度
    '''
    CondGini = 0.0
    splitInfo = 0.0
    for value in uniqueVals:
        subDataSet = splitDataSet(dataSet, axis, value)
        prob = len(subDataSet) / float(len(dataSet))
        CondGini += prob * get_Gini(subDataSet)
    return CondGini

#========================================================
#  找出分裂后基尼不纯度最小的划分特征
#========================================================

def chooseBestFeat(dataSet):
    '''
    选择最好的划分特征
    INPUT --> 数据集
    OUTPUT --> 最好的划分特征
    '''
    numFeatures = len(dataSet[0]) -1 # 最后一列是分类
    baseGini = get_Gini(dataSet) # 返回整个数据集的基尼不纯度
    bestInfoGain = 10000.0
    bestFeature = -1
    for i in range(numFeatures): # 遍历所有特征
        # 找到需要分类的特征子集
        featValues = [line[i] for line in dataSet]
        uniqueVals = set(featValues)
        CondGini = get_CondGini(dataSet, i, uniqueVals)
        if(CondGini < baseGini):
            baseGini = CondGini
            bestFeature = i
    return bestFeature

#========================================================
#  构造决策树
#========================================================

def majorityCnt(classList):
    '''
    投票表决代码
    '''
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount.setdefault(vote, 0)
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=lambda i:i[1], reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet, featureName):
    '''
    创建决策树
    INPUT --> 数据集, 特征标签
    '''
    classList = [line[-1] for line in dataSet] # 分类目标列

    if classList.count(classList[0]) == len(classList): # 统计属于类型classList[0]的个数
        return classList[0] # 当类别完全相同则停止继续划分
    if len(dataSet[0]) ==1: # 当只有一个特征的时候，遍历所有实例返回出现次数最多的类别
        return majorityCnt(classList) # 返回类别标签
    
    bestFeat = chooseBestFeat(dataSet)
    bestFeatLabel = featureName[bestFeat]  # 该特征的label
    myTree ={bestFeatLabel:{}}  # map结构,key为featureLabel
    del (featureName[bestFeat])
    # 找到需要分类的特征子集
    featValues = [line[bestFeat] for line in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = featureName[:] # 子集合
        # 构建数据的子集合，并进行递归
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

#========================================================
#  主程序
#========================================================

if __name__ == '__main__':
    dataSet, featureName = createDataSet()
    r = chooseBestFeat(dataSet)
    # print(r)
    myTree = createTree(dataSet, featureName)
    print(myTree)