Python 决策树算法实现 - 使用信息增益构建决策树
import numpy as np
import matplotlib.pyplot as plt
from pylab import *
# 特征字典，亦做全局变量
featureDic = {
'色泽': ['浅白', '青绿', '乌黑'],
'根蒂': ['硬挺', '蜷缩', '稍蜷'],
'敲声': ['沉闷', '浊响', '清脆'],
'纹理': ['清晰', '模糊', '稍糊'],
'脐部': ['凹陷', '平坦', '稍凹'],
'触感': ['硬滑', '软粘']
}
def getDataSet():
dataSet = [
['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.697, 0.460, 1],
['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', 0.774, 0.376, 1],
['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.634, 0.264, 1],
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', 0.608, 0.318, 1],
['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.556, 0.215, 1],
['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', 0.403, 0.237, 1],
['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', 0.481, 0.149, 1],
['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', 0.437, 0.211, 1],
['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', 0.666, 0.091, 0],
['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', 0.243, 0.267, 0],
['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', 0.245, 0.057, 0],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', 0.343, 0.099, 0],
['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', 0.639, 0.161, 0],
['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', 0.657, 0.198, 0],
['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', 0.360, 0.370, 0],
['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', 0.593, 0.042, 0],
['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', 0.719, 0.103, 0]
]
features = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖量']
# 每种特征的属性个数
numList = [] # [3, 3, 3, 3, 3, 2]
for i in range(len(features) - 2):
numList.append(len(featureDic[features[i]]))
# 编码，把文字替换成数字。用1、2、3表示同种特征的不同类型
newDataSet = []
for dataVec in dataSet: # 第一每一个数据
dataNum = dataVec[-3:] # 保存数据中的数值部分
newData = []
for i in range(len(dataVec) - 3): # 值为字符的每一列
for j in range(numList[i]): # 对应列的特征的每一类
if dataVec[i] == featureDic[features[i]][j]:
newData.append(j+1)
newData.extend(dataNum) # 编码好的部分和原来的数值部分合并
newDataSet.append(newData)
return np.array(newDataSet), features
def calEntropy(dataArr, classArr):
n = dataArr.size
data0 = dataArr[classArr == 0]
data1 = dataArr[classArr == 1]
p0 = data0.size / float(n)
p1 = data1.size / float(n)
# 约定：p=0, p*log_2(p) = 0
if p0 == 0:
ent = -(p1 * np.log(p1))
elif p1 == 0:
ent = -(p0 * np.log(p0))
else:
ent = -(p0 * np.log2(p0) + p1 * np.log2(p1))
return ent
def splitDataSet(dataSet, ax, value):
'''
按照给点的属性ax和其中一种取值value来划分数据。
当属性类型为标称数据时，返回一个属性值都为value的数据集。
当属性类型为数值型数据事，以与value的大小关系为基准返回两个数据集。
input:
dataSet: 输入数据集，形状为(m,n)表示m个数据，前n-1列个属性，最后一列为类型。
ax：属性类型
value: 标称型时为1、2、3等。数值型为形如0.123的数。
return：
1.标称型dataSet返回第ax个属性中值为value组成的集合
2.数值型dataSet返回两个集合。其一中数据都小于等于value，另一都大于。
'''
# 2个连续属性密度、含糖量+类型为后3列，其余为标称型
if ax < dataSet.shape[1] - 3:
dataS = np.delete(dataSet[dataSet[:, ax] == value], ax, axis=1)
return dataS
else:
dataL = dataSet[dataSet[:, ax] <= value]
dataR = dataSet[dataSet[:, ax] > value]
return dataL, dataR
def calInfoGain(dataSet, labelList, ax, value=-1):
'''
计算给定数据dataSet在属性ax上的香农熵增益。
input：
dataSet：输入数据集，形状为(m,n)表示m个数据，前n-1列个属性，最后一列为类型。
labelList：属性列表，如['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖量']
ax: 选择用来计算信息增益的属性。0表示第一个属性，1表示第二个属性等。
前六个特征是标称型，后两个特征是数值型。
value: 用来划分数据的值。当标称型时默认为-1, 即不使用这个参数。
return：
gain:信息增益
'''
baseEnt = calEntropy(dataSet[:, :-1], dataSet[:, -1]) # 计算D的原始信息熵
newEnt = 0.0 # 划分完数据后的香农熵
if ax < dataSet.shape[1] - 3: # 计算标称型的香农熵
num = len(featureDic[labelList[ax]]) # 每一个特征的类别数
for j in range(num):
subDataSet = splitDataSet(dataSet, ax, j+1)
prob = len(subDataSet) / float(len(dataSet))
if prob != 0:
newEnt += prob * calEntropy(subDataSet[:, :-1], subDataSet[:, -1])
else:
# 数据集划分为两份
dataL, dataR = splitDataSet(dataSet, ax, value)
# 计算两数据集的信息熵
entL = calEntropy(dataL[:, :-1], dataL[:, -1])
entR = calEntropy(dataR[:, :-1], dataR[:, -1])
# 计算划分完总数据集的信息熵
newEnt = (dataL.size * entL + dataR.size * entR) / float(dataSet.size)
# 计算信息增益
gain = baseEnt - newEnt
return gain
def chooseBestSplit(dataSet, labelList):
maxGain = 0.0
bestFeature = -1
bestThresh = -1
m, n = dataSet.shape
# 对每一个特征
for i in range(n - 1):
if i < (n - 3): # 标称型
gain = calInfoGain(dataSet, labelList, i)
if gain > maxGain:
bestFeature = i
maxGain = gain
else: # 数值型
featVals = dataSet[:, i] # 得到第i个特征的所有值
sortedFeat = np.sort(featVals) # 按照从小到大的顺序排列第i个特征的所有值
T = []
# 计算划分点
for j in range(m - 1):
t = (sortedFeat[j] + sortedFeat[j + 1]) / 2.0
T.append(t)
# 对每一个划分值,计算增益熵
for t in T:
gain = calInfoGain(dataSet, featureDic, i, t)
if gain > maxGain:
bestFeature = i
bestThresh = t
maxGain = gain
return bestFeature, bestThresh, maxGain
def majorityCnt(classList):
'''
投票，0多返回'坏瓜',否则返回'好瓜'。
'''
cnt0 = len(classList[classList == 0])
cnt1 = len(classList[classList == 1])
if cnt0 > cnt1:
return '坏瓜'
else:
return '好瓜'
def createTree(dataSet, labels):
classList = dataSet[:, -1]
# 如果剩余的类别全相同,则返回
if len(classList[classList == classList[0]]) == len(classList):
if classList[0] == 0:
return '坏瓜'
else:
return '好瓜'
# 如果只剩下类标签，投票返回
if len(dataSet[0]) == 1:
return majorityCnt(classList)
# 得到增益最大划分的属性、值
bestFeat, bestVal, entGain = chooseBestSplit(dataSet, labels)
bestFeatLabel = labels[bestFeat]
if bestVal != -1: # 如果是数值型
txt = bestFeatLabel + '<=' + str(bestVal) + '?'
else: # 如果是标称型
txt = bestFeatLabel + '=' + '?'
myTree = {txt: {}}
if bestVal != -1: # 数值型的话就是左右两个子树。
subDataL, subDataR = splitDataSet(dataSet, bestFeat, bestVal)
myTree[txt]['是'] = createTree(subDataL, labels)
myTree[txt]['否'] = createTree(subDataR, labels)
else:
i = 0
# 生成子树的时候要将已遍历的属性删去。数值型不要删除。
del (labels[bestFeat])
uniqueVals = featureDic[bestFeatLabel] # 最好的特征的类别列表
for value in uniqueVals: # 标称型的属性值有几种，就要几个子树。
# Python中列表作为参数类型时，是按照引用传递的，要保证同一节点的子节点能有相同的参数。
subLabels = labels[:] # subLabels = 注意要用[:]，不然还是引用
i += 1
subDataSet = splitDataSet(dataSet, bestFeat, i)
myTree[txt][value] = createTree(subDataSet, subLabels)
return myTree
# 定义文本框和箭头格式
decisionNode = dict(boxstyle='sawtooth', fc='0.8')
leafNode = dict(boxstyle='round4', fc='0.8')
arrow_args = dict(arrowstyle='<-')
mpl.rcParams['font.sans-serif'] = ['SimHei'] # 没有这句话汉字都是口口
# mpl.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的问题
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, fontsize=20)
def plotNode(nodeTxt, centerPt, parentPt, nodeType): # 绘制带箭头的注解
createPlot.ax1.annotate(nodeTxt,
xy=parentPt,
xycoords='axes fraction',
xytext=centerPt,
textcoords='axes fraction',
va='center',
ha='center',
bbox=nodeType,
arrowprops=arrow_args,
fontsize=20)
def getNumLeafs(myTree): # 获取叶节点的数目
numLeafs = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
def getTreeDepth(myTree): # 获取树的层数
maxDepth = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
thisDepth = 1 + getTreeDepth(secondDict[key])
else:
thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth
def plotTree(myTree, parentPt, nodeTxt):
numLeafs = getNumLeafs(myTree)
getTreeDepth(myTree)
firstStr = list(myTree.keys())[0]
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW,
plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt)
plotNode(firstStr, cntrPt, parentPt, decisionNode)
secondDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
plotTree(secondDict[key], cntrPt, str(key))
else:
plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff),
cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
def createPlot(inTree):
fig = plt.figure(1, figsize=(600, 30), facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW
plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show()
def main():
dataSet, labelList = getDataSet()
myTree = createTree(dataSet, labelList)
createPlot(myTree)
if __name__ == '__main__':
main()
代码功能介绍
这段代码可以分成以下几个板块来介绍其功能作用：
-
导入必要的库和模块：
- 导入numpy库并重命名为np，它提供了高性能的数值计算功能。
- 导入matplotlib.pyplot模块并重命名为plt，用于绘制图表。
- 导入pylab模块，它是matplotlib的一个模块，提供了更高级的绘图功能。
-
定义特征字典featureDic：
- 定义了一个全局变量featureDic，用于存储特征和对应的可能取值。
-
定义获取数据集的函数getDataSet：
- 定义了一个数据集dataSet，包含了一些特征和对应的标签。
- 定义了一个特征列表features，包含了所有特征的名称。
- 定义了一个编码函数，将数据集中的特征值替换为对应的数字编码。
- 返回编码后的数据集和特征列表。
-
定义计算熵的函数calEntropy：
- 根据给定的数据和类别计算熵的值。
- 使用np.log和np.log2函数计算对数。
- 根据熵的定义计算并返回熵的值。
-
定义划分数据集的函数splitDataSet：
- 根据给定的属性和值划分数据集。
- 当属性类型为标称数据时，返回属性值都为给定值的数据集。
- 当属性类型为数值型数据时，以给定的值作为阈值划分数据集为两部分。
-
定义计算信息增益的函数calInfoGain：
- 根据给定的数据集、特征列表、属性索引和阈值（当属性为数值型时）计算信息增益。
- 根据属性类型的不同，分别计算标称型和数值型属性的信息增益。
- 使用calEntropy函数计算熵和划分后的数据集的熵。
- 根据信息增益的定义计算并返回信息增益的值。
-
定义选择最佳划分属性的函数chooseBestSplit：
- 遍历所有属性，选择具有最大信息增益的属性作为最佳划分属性。
- 对于标称型属性，计算信息增益。
- 对于数值型属性，计算每个划分点的信息增益，并选择具有最大信息增益的划分点作为最佳划分点。
- 返回最佳划分属性、最佳划分点和最大信息增益。
-
定义投票函数majorityCnt：
- 根据类别列表进行投票，返回类别较多的结果。
-
定义创建决策树的函数createTree：
- 判断是否已经划分完所有属性或所有数据属于同一类别，如果是则返回类别标签。
- 判断是否只剩下类标签，如果是则进行投票，返回投票结果。
- 根据信息增益选择最佳划分属性和划分点。
- 根据最佳划分属性和划分点递归创建子树，返回决策树。
-
定义创建绘图所需的文本框和箭头格式的函数和绘制树的函数：
- 定义绘制文本框的函数plotNode。
- 定义绘制箭头和文本的函数plotMidText。
- 定义计算叶节点数目的函数getNumLeafs。
- 定义计算树的层数的函数getTreeDepth。
- 定义绘制树的函数plotTree。
- 定义绘制整个图表的函数createPlot。
-
定义主函数main：
- 调用getDataSet函数获取数据集和特征列表。
- 调用createTree函数创建决策树。
- 调用createPlot函数绘制决策树图表。
-
运行主函数main。
以上是代码按照功能作用的分段介绍。
原文地址: https://www.cveoy.top/t/topic/bdVL 著作权归作者所有。请勿转载和采集!