在上一篇文章中我们介绍了knn算法，knn算法是很简单的机器学习算法，但是它也有一些缺点，比如计算量太大，无法给出数据内在的含义；因此，今天来说一说knn的优化版——决策树。
决策树其实不需要有什么机器学习的基础，它将信息很直观的在图中显示了出来，下面就是一棵决策树
决策树由判断模块和终止模块组成，树叶就是终止模块，除树叶外的节点，就是判断模块，在判断模块中就是分类的标签，如何确定是否属于该分类，就看判断模块的的树枝上的信息，如果属于该分类，那么树枝直接连接这着树叶节点，也就是终止模块，如果不属于，那么就要进入另一个判断模块，进一步判断属于哪个分类。
因此，我们可以发现决策树的判断模块其实是重要的，采用什么判断依据来决定分类归属，决定着最终分类的准确性。那么如何确定判断依据呢？这里要引入一个信息增益（熵）的概念：信息增益是特征选择的一个重要指标，它定义为一个特征能够为分类系统带来多少信息，带来的信息越多，说明该特征越重要，相应的信息增益也就越大。信息增益等于信息熵-条件熵
信息熵：信息量度量的是一个具体事件发生了所带来的信息，而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望
1
| H=-{p(x1)*log2(p(x1))+p(x2)*log2(p(x2))+...+p(xn)*log2(p(xn))} ;p(xi)是选择第i个分类的概率
|
条件熵：定义为X给定条件下，Y的条件概率分布的熵对X的数学期望
如果说信息增益的值越大，那么采用这个时候的分类依据就是当前最优的选择；所以在每一个判断模块，我们都要计算当前的信息增益，选择出一个当前最优的分类依据作为判断依据。
信息熵的代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def calcShanonEnt(dataSet):
"""
计算熵（也就是计算集合的纯度）
:param dataSet:
:return:
"""
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt
|
依据信息增益的结果对数据集进行分类代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| def splitDataSet(dataSet, axis, value):
"""
数据切分方案
:param dataSet:
:param axis:
:param value:
:return:
"""
returnData = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
returnData.append(reducedFeatVec)
return returnData
def chooseBestFeatureToSplit(dataSet):
"""
选择最合适的数据分割方案，根据数据集的特征项进行选择分类决策
:param dataSet:
:return:
"""
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShanonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueValue = set(featList)
newEntropy = 0.0
for value in uniqueValue:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(subDataSet))
newEntropy += prob * calcShanonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
|
现在我们得到一个决策树决策的重要依据——信息增益，现在，还需要明白决策树的终止模块的条件，第一个条件是我们已经遍历完了所有的划分数据集的属性；第二个条件是分支下的所有实例具有相同的分类，只要满足两个条件中的一个，那么就到了终止模块。
知道了决策树判断模块的判断依据以及终止模块的终止条件，我们就可以很快实现决策树了。
决策树代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| def majorityCnt(classList):
"""
投票表决决定叶子的分类
:param classList:
:return:
"""
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
def createTree(dataSet, labels):
"""
递归的创建决策树
:param dataSet:
:param labels:
:return:
"""
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList):
return classList[0]
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel: {}}
del (labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
|