什么是决策树呢？
决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。
文绉绉的文字总是既拗口又难懂，其实只需要一张图就可以看清决策树的本质。
说白了，就是每次选取一个特征值，直到到达叶子节点完成决策过程。
这里面涉及到一个问题，也是决策树的一个必须解决的问题：特征位置如何选择？比如为什么年龄的判断在长相的前面？
这种选择依据是什么？这些问题将在下面解答。
老规矩，Talk is cheap, show me your code.
#-*-coding:utf-8-*- from math import log def calcShannonEnt(datsSet): #长度 numEntries = len(dataSet) #字典统计 labelCounts = {} #遍历特征 for featVec in dataSet: #最后一维特征(分类) currentLabel = featVec[-1] #如果不在字典中，则添加进字典 #可以写成labelCounts[labelCount] = labelCounts.get(currentLabel,0) + 1 if currentLabel not in labelCounts.key(): 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
这段代码很简单，可能对于最后几句话理解起来有些困难。那我们一起来分析一下。
什么是信息增益和熵呢？学过信息论的同学肯定知道，那么对于没有学过的同学呢？不要着急，我们一起来看看。
首先 信息增益和熵是一回事，就是一个事情两个名字而已。那么什么是熵呢？
熵就是信息的期望值，在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。ok，那么什么是信息呢？是如何用数学语言描述呢？信息的定义就是：
-ln(p)
很简单是不，那么我们应该怎么理解呢？首先p代表某个分类出现的概率。比如，均匀色子出现6的概率为1/6，硬币正面朝上的概率为1/2。
“信息熵”是一个非常神奇的概念，它能够反映知道一个事件的结果后平均会给你带来多大的信息量。如果某个结果的发生概率为 p ，当你知道它确实发生了，你得到的信息量就被定义为 – log(p) 。 p 越小，你得到的信息量就越大。如果一颗骰子的六个面分别是 1 、 1 、 1 、 2 、 2 、 3 ，那么你知道了投掷的结果是 1 时可能并不会那么吃惊，它给你带来的信息量是 – log(1/2) ，约为 0.693 。知道投掷结果是 2 ，给你带来的信息量则是 – log(1/3) ≈ 1.0986 。知道投掷结果是 3 ，给你带来的信息量则有 – log(1/6) ≈ 1.79 。但是，你只有 1/2 的机会得到 0.693 的信息量，只有 1/3 的机会得到 1.0986 的信息量，只有 1/6 的机会得到 1.79 的信息量，因而平均情况下你会得到 0.693/2 + 1.0986/3 + 1.79/6 ≈ 1.0114 的信息量。这个 1.0114 就是那颗骰子的信息熵。
现在，假如某颗骰子有 100 个面，其中 99 个面都是 1 ，只有一个面上写的 2 。知道骰子的抛掷结果是 2 会给你带来一个巨大无比的信息量，它等于 – log(1/100) ，约为 4.605 ；但你只有百分之一的概率获取到这么大的信息量，其他情况下你只能得到 – log(99/100) ≈ 0.01005 的信息量。平均情况下，你只能获得 0.056 的信息量，这就是这颗骰子的信息熵。再考虑一个最极端的情况：如果一颗骰子的六个面都是 1 ，投掷它不会给你带来任何信息，它的信息熵为 – log(1) = 0 。什么时候信息熵会更大呢？换句话说，发生了怎样的事件之后，你最想问一下它的结果如何？直觉上看，当然就是那些结果最不确定的事件。没错，信息熵直观地反映了一个事件的结果有多么的随机。
为什么每个字母所承载的信息量跟它出现的概率有关？
信息的作用就体现在使得某事件发生的概率从之前的某个概率变为1。所以信息量是与概率有关的。基于此，香农提出了他的第一条假设：信息量是关于事件发生概率的函数。
为什么要取对数函数，而不是其他函数？
我们需要注意到任意事件的概率有一个很重要的属性，概率取值必须介于[0,1]区间。再来看对数函数，它有一个很好的性质，值域可以很好的放大定义域处于[0,1]上的值，将[0,1]上的值映射到[0,∞]，一个相当好的逆normalization过程。而我们知道要想知道整个系统的混杂程度，得研究每一个个体出现的概率分布，并由个体的概率分布来分析整个系统的行为。然而，概率值分布的区间太小，也就是说值与值之间的变化太小，特征不够明显。我们想要通过用每个个体的概率分布值来计算和比较不同系统之间混杂程度，最后得出的结果区分度必然不高，有些可能甚至需要精确到小数点后几十位才能比较，最后甚至可能会导致溢出而无法比较。所以为了让特征明确话，我们需要对原本的概率函数进行一些处理，让数值特之间的变化差距大一些，而对数函数则很好的可以帮助扩大区分度。这也是需要对概率取对数函数的原因。
为什么需要取负？
其实很容易看出，如果某一个体发生的概率越小，说明它越有倾向杂质和噪声的可能，越容易导致系统混乱无序。因此，小概率个体实则对系统杂乱性和不确定性贡献越大，所以我们在处理个体概率时，不仅需要将其映射到更大的区间上以增大辨识度，还需要找个区间递减函数来映射之。综合以上，我们需要用递减的对数函数来处理个体概率。
信息增益大家明白了吧，那么这里为什么要引入信息增益呢？当然是为了回答上面的特征位置的问题。
大家已经明白了，熵是随机变量不确定性的度量。熵越大，随机变量的不确定性越大（证明见P60《统计学习方法》李航著）。当我们得知特征X的信息后，必然会使得类Y的信息不确定性减小，那么这个减小量，就用信息增益表示。所以我们优先使用信息增益大的特征（为了尽快消除不确定性，达到决策目的）。为了便于理解程序，这里给出几个必要的数学公式
随机变量X的熵定义为：$H(X) = -sum_{i=1}^{n} P_i logP_i $
条件熵$H(Y|X)$表示在已知随机变量X的条件下随机变量Y的不确定性，即条件熵。
数学表达式为 $H(Y|X) = sum_{i=1}^{n} P_i H(Y|X=x_i)$
信息增益$g(D,A) = H(D) - H(D|A)$
至此，信息增益就介绍完了，那么为什么可以确保信息增益一定为正数呢？
其实证明很简单啦，$H(Y|X)=sum_{i=1}^{n} P_i H(Y|X=x_i)$ VS $H(Y) = sum_{i=1}^{n} H(Y|X=x_i)$ 孰大孰小一目了然吧？
分类算法除了需要测量信息熵，还要划分数据集，度量花费数据集的熵，一边判断当前是否正确地划分了数据集。
#划分数据集:待划分的数据集、划分数据集的特征、特征的返回值 #注意：python函数传递的是列表的引用，所以修改列表将影响列表整个生存周期 def splitDataSet(dataSet, axis, value): #返回数据集 retDataSet = [] #遍历dataSet，去掉value for featVec in dataSet: #如果axis对应value if featVec[axis] == value: #获取axis之前的元素 reduceFeatVec = featVec[:axis] #extend和append有什么区别呢？想想看 reducedFeaVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
这里可以这样理解这段代码：当我们按照某个特征划分数据集的时候，就需要将将所有符合要求的元素抽取出来。
下面的程序选择最大的信息增益：
#选取特征，划分数据集，计算得出最好的划分数据集的特征 def chooseBestFeatureToSplit(dataSet): #特征的数目（除去其本身） numFeatures = len(dataSet[0])-1 #计算经验熵 bestEntropy = calcShannonEnt(dataSet) # bestInfoGain = 0.0; bestFeature = -1 #遍历每一个feature， for i in range(numFeatures): #提取出这个特征 featList = [example[i] for example in dataSet] #python集合，目的是去除重复，获得这个特征所有的取值范围 uniqueVals = set(featList) newEntropy = 0.0 #遍历这个特征的取值范围 for value in uniqueVals: #某一个特征取值，找出子数据集 subDataSet = splitDataSet(dataSet, i, value) # 计算经验条件熵 prob = len(subDataSet)/float(len(dataSet)) #概率 * 这个特征为value时候的熵 newEntropy += prob * calcShannonEnt(subDataSet) #信息增益 infoGain = baseEntropy - newEntropy #选取信息增益最大的特征 if (infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature
建立决策树：
#建立决策树 def createTree(dataSet, labels): #获取dataSet分类 classList = [example[-1] for example in dataSet] #如果是同一个值的话 if classList.count(classList[0]) == len(classList): #返回唯一的分类 return classList[0] #已经到达叶子节点了 if len(dataSet[0]) == 1: #如果还不能划分的话，返回classList中最多的元素 return majorityCnt(classList) #返回最大信息增益的特征 bestFeat = chooseBestFeatureToSplit(dataSet) #特征到标签 bestFeatLabel = labels[bestFeat] #构建一个数，先生成根 myTree = {bestFeatLabel:{}} #去掉labels 中 下标是bestFeat的元素 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
下面将讲解