决策树的主要任务就是探寻数据中所蕴含的知识信息。所以决策树可以使用不熟悉的数据集，并从中提取出一系列规则，而这些规则的提炼过程就是机器学习的过程。
在构造决策树时必须要面对的问题是：当前我们究竟该选哪个特征来进行数据的分类。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。
完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果分支下的数据属于同一类型，则当前的数据集无需进一步划分；如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的方法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。上面介绍的就是ID3算法，我们在每次划分数据集的时候都只选取一个特征属性。
划分数据的根本原则就是：将无序的数据变的更加有序。划分前后信息发生的变化我们称之为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
那么如何计算那个虚无缥缈的信息增益呢？针对这个问题香农同学提出了一个：熵的概念。在高中物理也提到过熵，它标识物体的无序程度。而我们这里使用的熵则代表了信息的无序程度。熵定义为信息的期望值，符号的信息定义为：
------- 1
其中是选择该分类的概率。
为了计算熵，我们需要计算所有分类可能包含的信息期望值，可以通过如下的公式得到：
------- 2
其中n是分类的数目。
下面给出计算信息熵的Python代码：
def calcShannonEnt(dataSet):
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:#通过前面的公式2计算信息熵
prob = float(labelCounts[key])/numEntries#分类出现概率
shannonEnt -= prob * log(prob,2) #log base 2
return shannonEnt
其中，返回的熵越大，说明数据的无序程度越高。
在具体进行数据集划分的时候，我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的选择。
在划分具体数据集时，可以使用如下的代码实现：
#三个参数为：待划分的数据集，划分数据集的特征索引，需要返回的特征值
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:#符合划分要求
reducedFeatVec = featVec[:axis]#提取该属性之前的内容
reducedFeatVec.extend(featVec[axis+1:])#提取该属性之后的内容，并合并为一个列表
retDataSet.append(reducedFeatVec)#将划分好的数据添加到返回集合中
return retDataSet
接下来我们将利用香农熵和前面的splitDataSet函数帮我们找到最好的特征划分方式。具体代码如下：
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #计算特征的数量
baseEntropy = calcShannonEnt(dataSet)#计算最初的熵值
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures):#遍历数据中的特征
featList = [example[i] for example in dataSet]
uniqueVals = set(featList) #获得特征的取值集合
newEntropy = 0.0
for value in uniqueVals:
#提取有该特征值的数据集
subDataSet = splitDataSet(dataSet, i, value)
#计算该数据集的出现概率
prob = len(subDataSet)/float(len(dataSet))
#计算信息熵
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy #计算信息增益
if (infoGain > bestInfoGain): #确定最佳的划分特征
bestInfoGain = infoGain
bestFeature = i
return bestFeature #返回最佳划分特征的索引
到目前为止我们已经可以通过计算信息增益来确定划分特征了，接下来就可以根据这一原则来实现决策树的构建。构建时的思路如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件时：程序遍历玩所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，通常，此时会采用多数表决的方法决定该叶子节点的分类。
实现多数表决的代码如下：
def majorityCnt(classList):
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):
#提取数据集中的分类情况
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
以上就是递归实现决策树创建的代码。在对“树”这个数据结构进行编程的时候，我们常常会看到递归实现，因为“树”本身就是以递归的方式进行定义的，所以在构建的时候使用递归的方式，思路也会更清晰。
到这里我们已经完成了决策树的具体构建，下面就是对它进行使用的部分了，实现的代码如下：
#输入参数依次为：构建好的决策树，特征列表，测试向量
def classify(inputTree,featLabels,testVec):
#取得第一个键值
firstStr = inputTree.keys()[0]
#取得根键值所对应的字典结构
secondDict = inputTree[firstStr]
#得到对应键值在属性列表中的索引
featIndex = featLabels.index(firstStr)
#取得测试向量中对应索引的值
key = testVec[featIndex]
#根据前面的值再次取到对应的取值结构
valueOfFeat = secondDict[key]
#如果该结构是字典，则需进一步分析
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
#若不是字典，则直接返回对应的值
else: classLabel = valueOfFeat
return classLabel
例如我们可以如下来构造和使用决策树算法：
myDat, labels = createDataSet()
wlabels = labels[:] #copy，因为createTree会改变传入参数的值
myTree = createTree(myDat, wlabels)
firstStr = myTree.keys()[0]
print classify(myTree, labels, [1,0]) print classify(myTree, labels, [1,1])
执行效果如下：
其中createDataSet函数的定义如下：
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing','flippers']
return dataSet, labels