决策树的思想比较简单，不复杂，决策树，就是通过一个属性将数据进行划分，而这个属性的选择也就是决策树的关键，用什么样的属性分开的值尽可能属于同一个类别。
属性选择的方法很多，书中主要介绍了：通过信息增益、增益比率、以及基尼指数.
具体伪代码书中给出：
本文采用了ID3算法划分数据集。该算法采用了一个叫信息增益的概念，关于信息论的部分，曾经写过一文http://www.cnblogs.com/fengbing/archive/2011/12/15/2288801.html中有部分阐述。
我的理解就是，信息是什么，怎么度量，也就是信息经过压缩之后还能代表本身的最小值，这个可以根据霍夫曼编码看出。
具体说明：
考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息中重复出现的概率为
Pn，则该符号的熵也即表示该符号所需的位数位为：
En = - log2( Pn )
整条信息的熵也即表示整条信息所需的位数为：E =
∑En
举个例子，对下面这条只出现了 a b c 三个字符的字符串：
aabbaccbaa
字符串长度为 10，字符 a b c 分别出现了 5 3
2 次，则 a b c 在信息中出现的概率分别为 0.5 0.3 0.2，他们的熵分别为：
Ea = -log2(0.5) = 1
Eb =
-log2(0.3) = 1.737
Ec = -log2(0.2) = 2.322
整条信息的熵也即表达整个字符串需要的位数为：
E =
Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
回想一下如果用计算机中常用的 ASCII 编码，表示上面的字符串我们需要整整 80
位，这样我们就用较少的位数表示较频繁出现的符号。
而这个值不能再小了，再小就不能表示这个信息量了。而这个最小的信息量也就是这个信息的度量。
下面就来上代码
1: # -*- coding: utf-8 -*
2: from math import log
3:
4: def calcShannonEnt(dataSet):
5: numEntries = len(dataSet)#得到数据集总数
6: labelCounts = {}
7: for featVec in dataSet:
8: currentLabel = featVec[-1]#-1表示最后一列
9: #这边处理可能不好理解，初始不在字典中先设为0，再加1，以后再字典中就直接加1
10: #我们可能处理是if no in dictionary，设为1，else +1
11: if currentLabel not in labelCounts.keys():
12: labelCounts[currentLabel] = 0
13: labelCounts[currentLabel] +=1
14: shannonEnt = 0.0
15: for key in labelCounts:
16: prob = float(labelCounts[key])/numEntries
17: shannonEnt -= prob*log(prob,2)
18: return shannonEnt
19:
20: def createDataSet():
21: dataSet = [[1, 1, ‘yes‘],
22: [1, 1, ‘yes‘],
23: [1, 0, ‘no‘],
24: [0, 1, ‘no‘],
25: [0, 1, ‘no‘]]
26: labels = [‘no surfacing‘,‘flippers‘]
27: return dataSet, labels
运行
1: >>> import tree
2: >>> myDat,labels = tree.createDataSet()
3: >>> myDat
4: [[1, 1, ‘yes‘], [1, 1, ‘yes‘], [1, 0, ‘no‘], [0, 1, ‘no‘], [0, 1, ‘no‘]]
5: >>> tree.calcShannonEnt(myDat)
6: 0.9709505944546686
这边求得的熵并不高，也就是说信息量不大，下面根据作者一样，我们增加分类，我们会发现熵变大，即信息量变大。
1: >>> myDat[0][-1]=‘maybe‘
2: >>> myDat
3: [[1, 1, ‘maybe‘], [1, 1, ‘yes‘], [1, 0, ‘no‘], [0, 1, ‘no‘], [0, 1, ‘no‘]]
4: >>> tree.calcShannonEnt(myDat)
5: 1.3709505944546687
通过信息增益的概念来构造决策树的方法有ID3，C4.5，C5.0还有通过基尼指数的CART算法。
书中没有介绍通过基尼指数的实现，目前也不实现，等书看完了后续对没有实现的算法再进行实现。
我们知道了信息熵，下面我们就开始划分数据集。
1: #axis第几个特征，value特征的值，以这个特征分类
2: def splitDataSet(dataSet,axis,value):
3: retDataSet = []
4: for featVec in dataSet:
5: if featVec[axis] == value:
6: reduceFeatVec = featVec[:axis]#featVec[:axis],axis=0时返回[]
7: reduceFeatVec.extend(featVec[axis+1:])
8: retDataSet.append(reduceFeatVec)
9: return retDataSet
得到的结果
1: >>> import tree
2: >>> myDat,labels = tree.createDataSet()
3: >>> tree.splitDataSet(myDat,0,1)
4: [[1, ‘yes‘], [1, ‘yes‘], [0, ‘no‘]]
我们这边是以第一个特征值进行分类，下面我们要对所有的特征值进行分类，计算每个分类下的信息熵。
这样信息增益就是分裂前后的两个信息量的差
1: def chooseBestFeatureToSplit(dataSet):
2: numFeatures = len(dataSet[0]) - 1 #最后一个是类别，特征数是每一行数目减去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]#example[i]代表第i列的特征值，在for循环获取这一列的所有值
7: uniqueVals = set(featList) #set是一个无序不重复集跟其他语言一样，这样得到i这一列不同的特征值
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
这个例子的第一步就是（3/5）*（-(2/3)*log(2/3)-(1/3)*log(1/3))+(2/5)*(-1*log1)
没有分类的时候直接计算-(2/5)*log(2/5)-(3/5)*log(3/5)
原始信息熵减去分裂之后的信息熵，就是信息增益，信息增益大的就选择这个特征进行分类。
我们打印出信息增益看出
1: num 0 infoGain 0.419973
2: num 1 infoGain 0.170951
所有以0也就是第一列的特征进行划分。
目前我们给出了第一次特征的划分，下面还要进行第二次的划分，甚至更多，决策树是一种树的形式，我们考虑采用的方式是递归处理。
递归处理要有一个结束条件。
1、遍历了所有的属性，或者每个分支下所有的实例都具有相同的分类。
2、可能会遇到最后没有属性可以划分这个样本子集的时候，我们采用投票原则，多的就为这个样本子集的类别标识，强制为叶子节点
具体代码：
1: def majorityCnt(classList):
2: classCount={}
3: for vote in classList:
4: if vote not in classCount.keys():
5: classCount[vote] = 0
6: classCount[vote] += 1
7: #这个sorted跟sort的区别前面提到，这个是重新建了一个数组，sort是在原有的基础上
8: sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
9: return sortedClassCount[0][0]
10:
11: def createTree(dataSet,labels):
12: classList = [example[-1] for example in dataSet]#得到分类这边是yes no
13: if classList.count(classList[0]) == len(classList): #这边说明都是同一个属性了，不好再分了
14: return classList[0]
15: if len(dataSet[0]) == 1:
16: return majorityCnt(classList)
17: bestFeat = chooseBestFeatureToSplit(dataSet)
18: bestFeatLabel = labels[bestFeat]
19: myTree = {bestFeatLabel:{}}
20: del(labels[bestFeat])
21: featValues = [example[bestFeat] for example in dataSet]
22: uniqueVals = set(featValues)
23: for value in uniqueVals:#分类 递归
24: subLabels = labels[:] #:表示全部
25: myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
26: return myTree
结果：
1: >>> import tree
2: >>> myDat,labels = tree.createDataSet()
3: >>> myTree = tree.createTree(myDat,labels)
4: >>> myTree
5: {‘no surfacing‘: {0: ‘no‘, 1: {‘flippers‘: {0: ‘no‘, 1: ‘yes‘}}}}
这边是采用字典的形式表示这个树形结构的，这个json字符串也有点像，不过决策树的优势在于它的图形表示，下面就通过之前用过的Matplotlib画图。
最终得到如下图：
具体画图这边就不叙述了，没有细看。主要通过得到叶子数，得到数的深度。
下面还是一样，给出一个真实的例子，然后对模型进行正确性评估。
也就是知道这个决策树，我们给出一个特征属性，来判断这个的类别是什么
1:
2: def classify(inputTree,featLabels,testVec):
3: firstStr = inputTree.keys()[0]
4: secondDict = inputTree[firstStr]
5: featIndex = featLabels.index(firstStr)
6: key = testVec[featIndex]
7: valueOfFeat = secondDict[key]
8: if isinstance(valueOfFeat, dict): #判断valueOfFeat是不是字典类型，也就是判断是不是还有子集，有在进行递归判断
9: classLabel = classify(valueOfFeat, featLabels, testVec)
10: else: classLabel = valueOfFeat
11: return classLabel
测试：
1: >>> import tree
2: >>> import treePlotter
3: >>> myTree = treePlotter.retrieveTree(0)
4: >>> myData,labels = tree.createDataSet()
5: >>> tree.classify(myTree,labels,[1,0])
6: ‘no‘
测试模型
另外我们创建好决策树之后就将其保存，这样要使用直接调用就好。
数据持久保存使用pickle模块，进行基本的数据序列和反序列化
1: #pickle模块实现了基本的数据序列和反序列化
2: def storeTree(inputTree,filename):
3: import pickle
4: fw = open(filename,‘w‘)
5: pickle.dump(inputTree,fw)
6: fw.close()
7:
8: def grabTree(filename):
9: import pickle
10: fr = open(filename)
11: return pickle.load(fr)
使用
1: >>> myTree = {‘no surfacing‘: {0: ‘no‘, 1: {‘flippers‘: {0: ‘no‘, 1: ‘yes‘}}}}
2: >>> myTree
3: {‘no surfacing‘: {0: ‘no‘, 1: {‘flippers‘: {0: ‘no‘, 1: ‘yes‘}}}}
4: >>> tree.storeTree(myTree,‘classifierStorage.txt‘)
5: >>> tree.grabTree(‘classifierStorage.txt‘)
6: {‘no surfacing‘: {0: ‘no‘, 1: {‘flippers‘: {0: ‘no‘, 1: ‘yes‘}}}}
7: >>>
最后作者给出了隐形眼镜的测试，我这边也把其代码列出
1: >>> fr = open(‘lenses.txt‘)
2: >>> lenses = [inst.strip().split(‘\t‘) for inst in fr.readlines()]
3: >>> lensesLabels = [‘age‘,‘prescript‘,‘astigmatic‘,‘tearRate‘]
4: >>> lensesTree = tree.createTree(lenses,lensesLabels)
5: >>> lensesTree
6: {‘tearRate‘: {‘reduced‘: ‘no lenses‘, ‘normal‘: {‘astigmatic‘: {‘yes‘: {‘prescript‘: {‘hyper‘: {‘age‘: {‘pre‘: ‘no lenses‘, ‘presbyopic‘: ‘no lenses‘, ‘young‘: ‘hard‘}}, ‘myope‘: ‘hard‘}}, ‘no‘: {‘age‘: {‘pre‘: ‘soft‘, ‘presbyopic‘: {‘prescript‘: {‘hyper‘: ‘soft‘, ‘myope‘: ‘no lenses‘}}, ‘young‘: ‘soft‘}}}}}}
7: >>> import treePlotter
8: >>> treePlotter.createPlot(lensesTree)
最后给出图如下：
这样基本的ID3算法就结束了，不过决策树远不止这么多。
决策树是一个很好的思想，因为其直观，效果也好，普通用户使用甚至可以得出几十年专家的水准。但是它也有很多问题，就关这个特征属性的选择问题，就有很多研究。
我们现在使用了信息增益，之后有C4.5算法采用信息增益比，在这本书的第九章有CART算法采用基尼指数，另外还有距离度量、基于统计的等等。
另外由于在真实世界中没有没有完善的数据，这数据有噪声，而我们刚刚的算法没有考虑这些问题。
还有属性之间是有关联的，这样划分出来的结果也会有问题，最终导致划分过细，而且最后的结果不易于理解。
于是有一些方案来解决这些问题。这个在这本书的第九章会给出一定的解决方案，这个ID3算法就到这边。