决策树算法
1. 简单概括
利用熵将整个数据集进行分割
使得分割后数据集的熵最小
不断对子数据集进行递归
直至无法进一步分割或者子数据集里数据的标签都一致时递归结束
分割的过程会形成一棵决策树
利用决策树将输入的数据归类到某一分割后的数据集中
子数据集所带有的标签就是决策的结果
2. 熵的定义和实现
熵定义为信息的期望值
信息的计算公式为
$$
l(x_i) = -log_2p(x_i) \quad 其中 \ p(x_i) \ 是选择某一分类的概率
$$
信息的期望值为
<br/>H=−∑i=1np(xi)log2p(xi)<br/><br />
H = -\sum_{i=1}^n p(x_i)log_2p(x_i)<br />
<br/>H=−i=1∑np(xi)log2p(xi)<br/>
核心代码
def calcShannon(dataSet):
dataSetSize = len(dataSet)
result = {}
# 利用字典统计每一种标签的数据数量
for data in dataSet:
label = data[-1]
result[label] = result.get(label, 0) + 1
shannon = 0
# 对于每一种分类计算其概率并统计信息熵
for key in result:
prob = result[key]/dataSetSize
shannon -= prob * math.log(prob, 2)
return shannon
3. 分割数据集
# 分割数据集,将维度axis且值为value的数据单独提取出来
def splitDataSet(dataSet, axis, value):
result = []
for data in dataSet:
if data[axis] == value:
# 使用axis分割后将axis这一列从数据中去掉
tmp = data[:axis]
# 这里通过entend拼接数组跳过了axis这一列
tmp.extend(data[axis+1:])
result.append(tmp)
return result
4. 选择最好的分割维度
def chooseBestSplitAxis(dataSet):
numOfAxis = len(dataSet[0]) - 1
baseEntropy = calcShannon(dataSet)
bestInfoGain = 0.0
bestAxis = -1
# 对所有维度都循环试验
for axis in range(numOfAxis):
allValue = [x[axis] for x in dataSet]
# 维度下所有可能的不重复值
valueSet = set(allValue)
newEntropy = 0.0
for value in valueSet:
# 按不重复的值分割成子数据集
subDataSet = splitDataSet(dataSet, axis, value)
prob = float(len(subDataSet)) / float(len(dataSet))
# 新的熵为部分熵按比例求和
newEntropy += prob * calcShannon(subDataSet)
# 作差为正说明新熵比旧熵小,混乱程度减小
# newInfoGain = baseEntropy - newEntropy
# if newInfoGain > bestInfoGain:
# bestAxis = axis
# bestInfoGain = newInfoGain
if newEntropy < baseEntropy:
# 上面源码有点绕 简单理解就是熵变小了就选择
bestAxis = axis
return bestAxis
5. 生成决策树
def createTree(dataSet, labels):
labelList = [data[-1] for data in dataSet]
# 递归出口一:子数据集的标签已经统一只有一种,不需要再进一步分割
if labelList.count(labelList[0]) == len(labelList):
return labelList[0]
# 递归出口二:子数据集已经没有了可分割的维度只剩下了标签
if len(dataSet[0]) == 1:
# 统计子数据集中出现次数最多的标签即为决策结果
return voteMaxLabel(labelList)
# 选择熵最小的分割维度
bestAxis = chooseBestSplitAxis(dataSet)
bestLabel = labels[bestAxis]
# 建立决策树字典
myTree = {bestLabel: {}}
# 删除已用于分割的维度对应的标签
del(labels[bestAxis])
allValue = [x[bestAxis] for x in dataSet]
valueSet = set(allValue)
for value in valueSet:
# 复制一遍标签
subLabel = labels[:]
# 采用最好的分割方法分割数据集后递归生成子树
myTree[bestLabel][value] = createTree(splitDataSet(dataSet, bestAxis, value), subLabel)
return myTree
6. 利用决策树进行决策
决策树生成范例
{'flippers': {0: 'no', 1: {'no surfacing': {0: 'no', 1: 'yes'}}}}
其中每一次决策需要用到决策树的两层
以这里的决策树为例
第一层‘flippers’为进行决策的标签
第二层的0和1为在该标签下进行决策的不同选择
核心代码
def classifyByTree(tree, labels, data):
# 得到进行决策的标签
firstLabel = list(tree.keys())[0]
# 用该标签进行决策的子树
secondDict = tree[firstLabel]
# 得到用于决策的标签所属的维度,用于后面取出数据在该维度的值
firstLabelIndex = labels.index(firstLabel)
classLabel = 'Error'
# 对于该标签下进行决策的不同的值
for value in secondDict.keys():
# 如果数据在该决策标签维度下的值等于子树的决策值
if data[firstLabelIndex] == value:
# 如果子树下还有子树(即还是一个字典类型的数据)则继续进行决策
if type(secondDict[value]).__name__ == 'dict':
classLabel = classifyByTree(secondDict[value], labels, data)
else:
# 否则子树下的值就是决策的结果
classLabel = secondDict[value]
return classLabel