在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)
网友评论