决策树算法是机器学习中监督学习算法中的一种，其主要意义是根据已有数据对算法进行不断训练，从而得到决策树，在新数据输入时对结果进行预测判定的一种算法。监督学习就是指需要提供大量的已有数据，包括输入和输出，其目的就是得出一种规则来对任意的输入对应一个输出。
如上图，右侧就是决策树算法得到的一个结果，对于输入的数据会进行不断的判断，最简单的就是二叉树的实现，对于每一个问题只有两个分支进行判断。得到结果后再进入下一层条件分支进行判断，依次递归，最终得到预测的结果。其中每个分支处（分支节点）的判断条件称为属性或者标签，最后的节点（叶节点）为判断结果。在分类过程中当出现所有数据结果处于同一类时则停止继续分支，得到叶节点。
在寻找分类特征时主要依据的就是概率统计方面的一些原理，主要的算法有ID3、C4.5、CRAT等。拿ID3来说，主要依据的是信息熵的理论。熵表示的是一种确定程度，熵值越小表示确定度越大，反之表示越混乱。同理，在通信中使用了信息熵的概念，熵值越小表示信息量越小，即确定性越大；反之表示不确定性越大。因此，分类特质的选择就是在所有特质中选择信息熵值最小的进行分类，之后删除该特征后剩下的特征中选择信息熵最小的，以此递归，直到分类完成。ID3使用信息增益值进行特征选择，C4.5使用信息增益率，这两种算法本质原理都是选取特征信息熵最小，其中C4.5的算法是在信息增益的基础上除以一个系数，算是算法的一个优化。另外CRAT算法特征选取依据是计算基尼系数，也是一种统计的方法。但最终都是在所有特征中计算某个统计值进行比较，选择一个最大或者最小的值进行分类，之后在剩余特征中递归进行。
以下是python实现的一个简单示例，帮助理解：
from math import log import operator '''计算给定数据集的熵''' 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 #labelCount中存放每种结果对应的数量值 shannonEnt = 0.0 '''信息量的计算公式为-log2(p(x))，其中p(x)为某信息的概率，所有特征信息量相加得到的便是信息熵''' for key in labelCounts: prob = float(labelCounts[key])/numEntries shannonEnt -= prob * log(prob,2) return shannonEnt '''创建数据集，dataSet中子列表最后一个元素表示的是结果''' def createDataSet(): dataSet = [ [1,1,'yes'], [1,1,'yes'], [1,0,'no'], [0,1,'no'], [0,1,'no'] ] labels = ['without water','flippers'] #标签对应dataSet子列表的前两列 return dataSet,labels '''划分数据集，表示在某个特征划分基础上去掉该特征后续的数据，在特征选择递归时使用''' 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 '''选择出信息增益大的特征''' 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 createTree(dataSet,labels): classList = [example[-1] for example in dataSet] if classList.count(classList[0]) == len(classList):#类别完全相同则停止划分 return classList[0] bestFeat = chooseBestFeatureToSplit(dataSet) #得到的是下标 bestFeatLabel = labels[bestFeat] #取值：no water 或者 flippers myTree = {bestFeatLabel:{}} del(labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) '''对特征值进行循环，返回的结果为两种，如果划分之后正好是同一类则停止划分，返回classList[0]，得到叶节点;如果不是同一类，则返回myTree作为该特征的下一层分支节点，一次递归''' for value in uniqueVals: subLables = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLables) return myTree if __name__ == '__main__': dataSet, label = createDataSet() print(createTree(dataSet,label)) ------------output------------ {'without water': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}可以实际运行，得到的决策树相当于下图：
