Python机器学习从原理到实践(1)：决策树分类算法

一、决策树原理

决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。 决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树是一种知识表示形式，它是对所有样本数据的高度概括决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。

决策树算法ID3的基本思想：

首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。

J.R.Quinlan的工作主要是引进了信息论中的信息增益，他将其称为信息增益（information gain），作为属性判别能力的度量，设计了构造决策树的递归算法。

举例子比较容易理解：

对于气候分类问题，属性为:

天气(A1) 取值为： 晴，多云，雨

气温(A2) 取值为： 冷 ，适中，热

湿度(A3) 取值为： 高 ，正常

风 (A4) 取值为： 有风， 无风

每个样例属于不同的类别，此例仅有两个类别，分别为P，N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。

由ID3算法得出一棵正确分类训练集中每个样例的决策树，见下图。

决策树叶子为类别名，即P 或者N。其它结点由样例的属性组成，每个属性的不同取值对应一分枝。

若要对一样例分类，从树根开始进行测试，按属性的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，样例被判为属于该叶结点所标记的类别。

现用图来判一个具体例子，

某天早晨气候描述为:

天气：多云

气温：冷

湿度：正常

风： 无风

它属于哪类气候呢?-------------从图中可判别该样例的类别为P类。

ID3就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。

ID3算法：

⒈ 对当前例子集合，计算各属性的信息增益；

⒉ 选择信息增益最大的属性Ak；

⒊ 把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；

⒋ 对既含正例又含反例的子集，递归调用建树算法；

⒌ 若子集仅含正例或反例，对应分枝标上P或N，返回调用处。

一般只要涉及到树的情况，经常会要用到递归。

对于气候分类问题进行具体计算有：

⒈ 信息熵的计算:

其中S是样例的集合， P(ui)是类别i出现概率：

|S|表示例子集S的总数，|ui|表示类别ui的例子数。对9个正例和5个反例有： P（u1）=9/14 P（u2）=5/14 H（S）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit ⒉ 信息增益的计算:

其中A是属性，Value(A)是属性A取值的集合，v是A的某一属性值，Sv是S中A的值为v的样例集合，| Sv |为Sv中所含样例数。 以属性A1为例，根据信息增益的计算公式，属性A1的信息增益为

S=[9+,5-] //原样例集中共有14个样例，9个正例，5个反例 S晴=[2+,3-]//属性A1取值晴的样例共5个，2正，3反 S多云=[4+,0-] //属性A1取值多云的样例共4个，4正，0反 S雨=[3+,2-] //属性A1取值晴的样例共5个，3正，2反 故

3.结果为

属性A1的信息增益最大，所以被选为根结点。

4.建决策树的根和叶子

ID3算法将选择信息增益最大的属性天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:

其中S2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。

5.递归建树

分别对S1和S3子集递归调用ID3算法，在每个子集中对各属性求信息增益.

（1）对S1，湿度属性信息增益最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。

（2）对S3，风属性信息增益最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。

二、PYTHON实现决策树算法分类

本代码为machine learning in action 第三章例子，亲测无误。

1、计算给定数据shangnon数据的函数：

[python] view plaincopy

1. def calcShannonEnt(dataSet):
2. #calculate the shannon value
3. numEntries = len(dataSet)
4. labelCounts = {}
5. for featVec in dataSet: #create the dictionary for all of the data
6. currentLabel = featVec[-1]
7. if currentLabel not in labelCounts.keys():
8. labelCounts[currentLabel] = 0
9. labelCounts[currentLabel] += 1
10. shannonEnt = 0.0
11. for key in labelCounts:
12. prob = float(labelCounts[key])/numEntries
13. shannonEnt -= prob*log(prob,2) #get the log value
14. return shannonEnt

2. 创建数据的函数

[python] view plaincopy

1. def createDataSet():
2. dataSet = [[1,1,'yes'],
3. [1,1, 'yes'],
4. [1,0,'no'],
5. [0,1,'no'],
6. [0,1,'no']]
7. labels = ['no surfacing','flippers']
8. return dataSet, labels

3.划分数据集，按照给定的特征划分数据集

[python] view plaincopy

1. def splitDataSet(dataSet, axis, value):
2. retDataSet = []
3. for featVec in dataSet:
4. if featVec[axis] == value: #abstract the fature
5. reducedFeatVec = featVec[:axis]
6. reducedFeatVec.extend(featVec[axis+1:])
7. retDataSet.append(reducedFeatVec)
8. return retDataSet

4.选择最好的数据集划分方式

[python] view plaincopy

1. def chooseBestFeatureToSplit(dataSet):
2. numFeatures = len(dataSet[0])-1
3. baseEntropy = calcShannonEnt(dataSet)
4. bestInfoGain = 0.0; bestFeature = -1
5. for i in range(numFeatures):
6. featList = [example[i] for example in dataSet]
7. uniqueVals = set(featList)
8. newEntropy = 0.0
9. for value in uniqueVals:
10. subDataSet = splitDataSet(dataSet, i , value)
11. prob = len(subDataSet)/float(len(dataSet))
12. newEntropy +=prob * calcShannonEnt(subDataSet)
13. infoGain = baseEntropy - newEntropy
14. if(infoGain > bestInfoGain):
15. bestInfoGain = infoGain
16. bestFeature = i
17. return bestFeature

5.递归创建树

用于找出出现次数最多的分类名称的函数

[python] view plaincopy

1. def majorityCnt(classList):
2. classCount = {}
3. for vote in classList:
4. if vote not in classCount.keys(): classCount[vote] = 0
5. classCount[vote] += 1
6. sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
7. return sortedClassCount[0][0]

用于创建树的函数代码

[python] view plaincopy

1. def createTree(dataSet, labels):
2. classList = [example[-1] for example in dataSet]
3. # the type is the same, so stop classify
4. if classList.count(classList[0]) == len(classList):
5. return classList[0]
6. # traversal all the features and choose the most frequent feature
7. if (len(dataSet[0]) == 1):
8. return majorityCnt(classList)
9. bestFeat = chooseBestFeatureToSplit(dataSet)
10. bestFeatLabel = labels[bestFeat]
11. myTree = {bestFeatLabel:{}}
12. del(labels[bestFeat])
13. #get the list which attain the whole properties
14. featValues = [example[bestFeat] for example in dataSet]
15. uniqueVals = set(featValues)
16. for value in uniqueVals:
17. subLabels = labels[:]
18. myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
19. return myTree

然后是在python 名利提示符号输入如下命令：

[python] view plaincopy

1. myDat, labels = trees.createDataSet()
2. myTree = trees.createTree(myDat,labels)
3. print myTree

结果是：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

6.实用决策树进行分类的函数

[python] view plaincop

1. def classify(inputTree, featLabels, testVec):
2. firstStr = inputTree.keys()[0]
3. secondDict = inputTree[firstStr]
4. featIndex = featLabels.index(firstStr)
5. for key in secondDict.keys():
6. if testVec[featIndex] == key:
7. if type(secondDict[key]).__name__ == 'dict':
8. classLabel = classify(secondDict[key], featLabels, testVec)
9. else: classLabel = secondDict[key]
10. return classLabel

在Python命令提示符，输入：

[python] view plaincopy

1. trees.classify(myTree,labels,[1,0])

得到结果：

'no'

Congratulation. Oh yeah. You did it.!!!

以下为补充学习笔记

1、决策树算法

决策树用树形结构对样本的属性进行分类，是最直观的分类算法，而且也可以用于回归。不过对于一些特殊的逻辑分类会有困难。典型的如异或（XOR）逻辑，决策树并不擅长解决此类问题。

决策树的构建不是唯一的，遗憾的是最优决策树的构建属于NP问题。因此如何构建一棵好的决策树是研究的重点。

J. Ross Quinlan在1975提出将信息熵的概念引入决策树的构建，这就是鼎鼎大名的ID3算法。后续的C4.5, C5.0, CART等都是该方法的改进。

请看下面这个例子。

假设要构建这么一个自动选好苹果的决策树，简单起见，我只让他学习下面这4个样本：

[plain] view plaincopy

1. 样本 红 大 好苹果
2. 0 1 1 1
3. 1 1 0 1
4. 2 0 1 0
5. 3 0 0 0

样本中有2个属性，A0表示是否红苹果。A1表示是否大苹果。

那么这个样本在分类前的信息熵就是S = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

信息熵为1表示当前处于最混乱，最无序的状态。

本例仅2个属性。那么很自然一共就只可能有2棵决策树，如下图所示：

显然左边先使用A0（红色）做划分依据的决策树要优于右边用A1（大小）做划分依据的决策树。

当然这是直觉的认知。定量的考察，则需要计算每种划分情况的信息熵增益。

先选A0作划分，各子节点信息熵计算如下：

0，1叶子节点有2个正例，0个负例。信息熵为：e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。

2，3叶子节点有0个正例，2个负例。信息熵为：e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

因此选择A0划分后的信息熵为每个子节点的信息熵所占比重的加权和：E = e1*2/4 + e2*2/4 = 0。

选择A0做划分的信息熵增益G（S, A0）=S - E = 1 - 0 = 1.

事实上，决策树叶子节点表示已经都属于相同类别，因此信息熵一定为0。

同样的，如果先选A1作划分，各子节点信息熵计算如下：

0，2子节点有1个正例，1个负例。信息熵为：e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

1，3子节点有1个正例，1个负例。信息熵为：e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1。

因此选择A1划分后的信息熵为每个子节点的信息熵所占比重的加权和：E = e1*2/4 + e2*2/4 = 1。也就是说分了跟没分一样！

选择A1做划分的信息熵增益G（S, A1）=S - E = 1 - 1 = 0.

因此，每次划分之前，我们只需要计算出信息熵增益最大的那种划分即可。

2、数据集

为方便讲解与理解，我们使用如下一个极其简单的测试数据集：

[plain] view plaincopy

1. 1.5 50 thin
2. 1.5 60 fat
3. 1.6 40 thin
4. 1.6 60 fat
5. 1.7 60 thin
6. 1.7 80 fat
7. 1.8 60 thin
8. 1.8 90 fat
9. 1.9 70 thin
10. 1.9 80 fat

这个数据一共有10个样本，每个样本有2个属性，分别为身高和体重，第三列为类别标签，表示“胖”或“瘦”。该数据保存在1.txt中。

我们的任务就是训练一个决策树分类器，输入身高和体重，分类器能给出这个人是胖子还是瘦子。

（数据是作者主观臆断，具有一定逻辑性，但请无视其合理性）

决策树对于“是非”的二值逻辑的分枝相当自然。而在本数据集中，身高与体重是连续值怎么办呢？

虽然麻烦一点，不过这也不是问题，只需要找到将这些连续值划分为不同区间的中间点，就转换成了二值逻辑问题。

本例决策树的任务是找到身高、体重中的一些临界值，按照大于或者小于这些临界值的逻辑将其样本两两分类，自顶向下构建决策树。

使用python的机器学习库，实现起来相当简单和优雅。

3、Python实现

Python代码实现如下：

[python] view plaincopy

1. # -*- coding: utf-8 -*-
2. import numpy as np
3. import scipy as sp
4. from sklearn import tree
5. from sklearn.metrics import precision_recall_curve
6. from sklearn.metrics import classification_report
7. from sklearn.cross_validation import train_test_split
10. ''''' 数据读入 '''
11. data = []
12. labels = []
13. with open("data\\1.txt") as ifile:
14. for line in ifile:
15. tokens = line.strip().split(' ')
16. data.append([float(tk) for tk in tokens[:-1]])
17. labels.append(tokens[-1])
18. x = np.array(data)
19. labels = np.array(labels)
20. y = np.zeros(labels.shape)
23. ''''' 标签转换为0/1 '''
24. y[labels=='fat']=1
26. ''''' 拆分训练数据与测试数据 '''
27. x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2)
29. ''''' 使用信息熵作为划分标准，对决策树进行训练 '''
30. clf = tree.DecisionTreeClassifier(criterion='entropy')
31. print(clf)
32. clf.fit(x_train, y_train)
34. ''''' 把决策树结构写入文件 '''
35. with open("tree.dot", 'w') as f:
36. f = tree.export_graphviz(clf, out_file=f)
38. ''''' 系数反映每个特征的影响力。越大表示该特征在分类中起到的作用越大 '''
39. print(clf.feature_importances_)
41. '''''测试结果的打印'''
42. answer = clf.predict(x_train)
43. print(x_train)
44. print(answer)
45. print(y_train)
46. print(np.mean( answer == y_train))
48. '''''准确率与召回率'''
49. precision, recall, thresholds = precision_recall_curve(y_train, clf.predict(x_train))
50. answer = clf.predict_proba(x)[:,1]
51. print(classification_report(y, answer, target_names = ['thin', 'fat']))

输出结果类似如下所示：

[ 0.2488562 0.7511438] array([[ 1.6, 60. ], [ 1.7, 60. ], [ 1.9, 80. ], [ 1.5, 50. ], [ 1.6, 40. ], [ 1.7, 80. ], [ 1.8, 90. ], [ 1.5, 60. ]]) array([ 1., 0., 1., 0., 0., 1., 1., 1.]) array([ 1., 0., 1., 0., 0., 1., 1., 1.]) 1.0

precision recall f1-score support thin 0.83 1.00 0.91 5 fat 1.00 0.80 0.89 5

avg / total 1.00 1.00 1.00 8

array([ 0., 1., 0., 1., 0., 1., 0., 1., 0., 0.]) array([ 0., 1., 0., 1., 0., 1., 0., 1., 0., 1.])

可以看到，对训练过的数据做测试，准确率是100%。但是最后将所有数据进行测试，会出现1个测试样本分类错误。

说明本例的决策树对训练集的规则吸收的很好，但是预测性稍微差点。

这里有3点需要说明，这在以后的机器学习中都会用到。

1、拆分训练数据与测试数据。

这样做是为了方便做交叉检验。交叉检验是为了充分测试分类器的稳定性。

代码中的0.2表示随机取20%的数据作为测试用。其余80%用于训练决策树。

也就是说10个样本中随机取8个训练。本文数据集小，这里的目的是可以看到由于取的训练数据随机，每次构建的决策树都不一样。

2、特征的不同影响因子。

样本的不同特征对分类的影响权重差异会很大。分类结束后看看每个样本对分类的影响度也是很重要的。

在本例中，身高的权重为0.25，体重为0.75，可以看到重量的重要性远远高于身高。对于胖瘦的判定而言，这也是相当符合逻辑的。

3、准确率与召回率。

这2个值是评判分类准确率的一个重要标准。比如代码的最后将所有10个样本输入分类器进行测试的结果：

测试结果：array([ 0., 1., 0., 1., 0., 1., 0., 1., 0., 0.]) 真实结果：array([ 0., 1., 0., 1., 0., 1., 0., 1., 0., 1.])

分为thin的准确率为0.83。是因为分类器分出了6个thin，其中正确的有5个，因此分为thin的准确率为5/6=0.83。

分为thin的召回率为1.00。是因为数据集中共有5个thin，而分类器把他们都分对了（虽然把一个fat分成了thin！），召回率5/5=1。

分为fat的准确率为1.00。不再赘述。

分为fat的召回率为0.80。是因为数据集中共有5个fat，而分类器只分出了4个（把一个fat分成了thin！），召回率4/5=0.80。

很多时候，尤其是数据分类难度较大的情况，准确率与召回率往往是矛盾的。你可能需要根据你的需要找到最佳的一个平衡点。

比如本例中，你的目标是尽可能保证找出来的胖子是真胖子（准确率），还是保证尽可能找到更多的胖子（召回率）。

代码还把决策树的结构写入了tree.dot中。打开该文件，很容易画出决策树，还可以看到决策树的更多分类信息。

本文的tree.dot如下所示：

[plain] view plaincopy

1. digraph Tree {
2. 0 [label="X[1] <= 55.0000\nentropy = 0.954434002925\nsamples = 8", shape="box"] ;
3. 1 [label="entropy = 0.0000\nsamples = 2\nvalue = [ 2. 0.]", shape="box"] ;
4. 0 -> 1 ;
5. 2 [label="X[1] <= 70.0000\nentropy = 0.650022421648\nsamples = 6", shape="box"] ;
6. 0 -> 2 ;
7. 3 [label="X[0] <= 1.6500\nentropy = 0.918295834054\nsamples = 3", shape="box"] ;
8. 2 -> 3 ;
9. 4 [label="entropy = 0.0000\nsamples = 2\nvalue = [ 0. 2.]", shape="box"] ;
10. 3 -> 4 ;
11. 5 [label="entropy = 0.0000\nsamples = 1\nvalue = [ 1. 0.]", shape="box"] ;
12. 3 -> 5 ;
13. 6 [label="entropy = 0.0000\nsamples = 3\nvalue = [ 0. 3.]", shape="box"] ;
14. 2 -> 6 ;
15. }

根据这个信息，决策树应该长的如下这个样子：