文章目录
1.基本概念2.决策树的构建2.1特征选取2.2 决策树的修剪与存储2.3 小结
1.基本概念
与上一章的k-NN类似，决策树也是一种常见的机器学习算法，不过它是通过构建树形结构来进行决策。基本思想则是根据样本特征的取值将整个数据集划分为不同的子集（可以理解为：根据某些判定条件，判定一些数据是不同类型的，从而分割开来），同一个子集内的数据多少会有些共同点。
举个简单的例子：利用两个问题判断一个人是不是农批
# 创建一个数据集，通过一个人“是否经常玩游戏”以及“玩的是不是王者荣耀”来判断一个人是不是农批
def createDataSet():
labels = ['always', 'honorOfKing']
# 1 表肯定，0 表否定
dataSet = [
[1, 1, 'y'],
[1, 0, 'n'],
[0, 1, 'n'],
[0, 0, 'n'],
]
# 创建一部字典，y对应的索引是农批，n对应不是农批
my_dic = {
'y': 'nongPi',
'n': 'Non-nongPi',
}
return dataSet, labels, my_dic
def testExample(isAlways, isHonorOfKing):
curData, thelabels, my_dic = createDataSet()
for i in range(len(curData)):
if isAlways == curData[i][0] and isHonorOfKing == curData[i][1]:
return curData[i][2]
if __name__ == '__main__':
datas, labels, dic = createDataSet()
my_data = testExample(1, 1)
result = dic.get(my_data)
print('you are ' + result)
实验结果是符合预期的，因为测试样本满足“玩游戏”这个先决条件，继而满足“玩的是王者荣耀”这个条件，所以能判断样本是农批，但代码没有体现出条件的先后关系。如果能够实现“判定一个人不常玩游戏”后直接判定为“不是农批”，逻辑会更严密些，后面学习到的“决策权重”可以解决这个问题。
2.决策树的构建
2.1特征选取
需要选取数个有力的特征才能够保证算法分类的准确性，以“一个人向银行贷款“为例，假设我是银行管理员，有人来办理贷款，我肯定要先判断这个人的资产如何，信用如何，才能决定要不要贷款给他，要贷的话要给他多少钱。我可以选取以下特征：年龄（判断一个人的生命周期），是否就业（判断个人收入），是否有房（判断一个人万一还不上钱，有没有不动产可以偿债），有没有失信记录（看这个人是不是老赖），由上述特征判定是否提供贷款。
上述几个特征都是比较有用的，但是他们仍有优先级的区别，比如一个人如果有严重的“失信记录”，那么即使他其他的特征分值都很高，最后的结果可能也不会很理想。为了区分特征之间优先级（权重）的不同，需要引入“香农熵”这个概念，熵
H
H
H指的是信息的期望值，如式1所示
H
=
−
∑
i
=
1
n
p
(
x
i
)
l
o
g
2
p
(
x
i
)
(1)
H = -\sum_{i=1}^np(x_i)log_{2}p(x_i)\tag1
H=−i=1∑np(xi)log2p(xi)(1) 其中，
x
i
x_i
xi是某一事件，
p
(
x
i
)
p(x_i)
p(xi)是选择此特征的概率，n是特征的数目。
def calcShannonEnt(data_set):
from math import log
num_entries = len(data_set) # 数据集长度（几个样本）
label_counts = {} # 保存每个标签出现次数的字典
for feat in datas: # 循环读取每个样本对应的标签，字典里没有的话就添加一个，有的话则个数加一
cur_label = feat[-1]
if cur_label not in label_counts.keys():
label_counts[cur_label] = 0
label_counts[cur_label] += 1
shannon_ent = 0.0 # 按公式计算香农熵
for key in label_counts:
prob = float(label_counts[key])/num_entries # 计算选择这个标签的概率
shannon_ent -= prob*log(prob,2)
return shannon_ent
此处calcShannonEnt()函数测试的是之前“判断是否为农批”的熵（只有两个特征），通过统计每个标签出现的概率，计算数据集的香农熵。在划分数据集时，需要尝试不同的特征作为划分依据，并计算每个特征划分后的熵。
为了体现出调换不同特征对熵改变的贡献，我需要使用特征较多的样本集，比如“是否提供贷款”这个例子
## 创建一个新的样本集
def createDataSet():
## 年龄：0代表青年，1代表中年，2代表老年；
## 有工作：0代表否，1代表是；
## 有自己的房子：0代表否，1代表是；
## 信贷情况：0代表一般，1代表好，2代表非常好；
## 类别(是否给贷款)：no代表否，yes代表是；
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 # 返回数据集和分类属性
这里引入信息增益g(D,A)这一概念，信息增益与特征对最终的分类结果影响呈正比，即：某一特征的信息增益越大，则这个特征对决策结果影响越大，计算方法参考式2
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
(2)
g(D,A) = H(D)-H(D|A)\tag2
g(D,A)=H(D)−H(D∣A)(2) 其中，g(D,A)为特征A对数据集D训练的增益，H(D)为数据集的经验熵，H(D|A)为特征A下数据集的熵。现在根据式1计算下经验熵H(D)
H
(
D
)
=
−
9
15
l
o
g
2
9
15
−
6
15
l
o
g
2
6
15
=
0.971
H(D) = -\frac{9}{15}log_{2}\frac{9}{15}-\frac{6}{15}log_{2}\frac{6}{15} = 0.971
H(D)=−159log2159−156log2156=0.971 现在，我想了解下有无工作这一特征对借贷的影响大不大，统计结果如下：
有工作没工作人数510允许放贷人数54
现在计算下特征为“有无工作”的熵
H
(
D
∣
A
0
)
H(D|A_0)
H(D∣A0)，计算公式如式3
H
(
D
∣
A
0
)
=
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
(3)
H(D|A_0) = \sum^n_{i = 1}\frac{|D_i|}{|D|}H(D_i)\tag3
H(D∣A0)=i=1∑n∣D∣∣Di∣H(Di)(3) 此时可以计算出这一特征的增益
g
(
D
,
A
0
)
=
H
(
D
)
−
[
5
15
H
(
D
1
)
+
10
15
H
(
D
2
)
]
=
0.971
−
[
5
15
×
0
+
10
15
(
−
4
10
l
o
g
2
4
10
−
6
10
l
o
g
2
6
10
)
]
=
0.324
g(D,A_0) = H(D)-[\frac{5}{15}H(D_1)+\frac{10}{15}H(D_2)] \\= 0.971-[\frac{5}{15}×0+\frac{10}{15}(-\frac{4}{10}log_2\frac{4}{10}-\frac{6}{10}log_2\frac{6}{10})]\\=0.324
g(D,A0)=H(D)−[155H(D1)+1510H(D2)]=0.971−[155×0+1510(−104log2104−106log2106)]=0.324 我们要想生成一棵最合理的决策树，就需要求出所有特征的信息增益，依次得到当前最优的特征
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
逐个计算各个特征的信息增益，挑选出增益最高的特征，返回其索引以及增益
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, bestInfoGain # 返回信息增益最大的特征的索引值
得出结论：最佳特征索引为2（有无房子）
2.2 决策树的修剪与存储
决策树的生成较为费时，为了避免每次为样本做依次决策都需要重新对数据集进行训练，我们可以将第一次训练的结果保存起来
生成一棵决策树，需要根据节点对应的信息增益选择特征，递归构建。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。 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,temp = 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: # 遍历特征，创建决策树。
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels)
return myTree
把结果保存到某文件当中 def storeTree(inputTree, filename):
with open(filename, 'w',encoding='utf8') as file:
file.write(str(inputTree))
需要用的时候读取这个文件 def grabTree(filename):
with open(filename, 'r',encoding="utf-8") as file:
data = file.read()
return data
最后用一组数据[0,1]（表示：无房子，有工作）测试一下刚刚分类的结果 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
2.3 小结
在处理大批量的数据前，决策树算法需要先计算出“熵”，以判断数据集中哪些特征对结果的影响力度大，比如在前面“银行放贷”这个例子中，我们得出信息增益最强的特征是“有没有房子”，有的话直接放贷，若没有，则去匹配与之相关度最高的特征：“有没有工作”。在判断样本标签的过程中，用这种办法可以在避免过度匹配数据集的情况下，保证预测的准确度。
在存储决策树的过程中，《机器学习实战》中，使用pickle模块来存储字典，不知道是编码问题还是什么，写入txt文本的内容都是乱码，我选用了其他编码、解码方式，或者将字典内容转换为json数据流再输入，都无法解决这个问题，最后只能用基本的读写文件方式写入树的内容。
参考文章
发表评论