决策树是一个if-then规则的集合，不断选取某一既定特征的既定取值作为分类条件，将数据集划分成一个个子集，直到最终形成叶节点。所以算法的关键步骤在于对分类特征的选择。决策树常用的学习算法有三种：ID3，C4.5和CART。其中ID3和C4.5形成的树每一层可能有大于两个的节点，每层的节点数对应于其根节点可取值的个数，通过计算信息增益或信息增益比选取最优的分类特征。而CART树是二叉树，即每次将数据集分成两个子集，CART也可以用于回归。CART在用于回归时，通过计算平方差选择最优分类值；而用于分类时，通过计算基尼指数来进行特征选择。
ID3在学习过程中，选择信息增益最大的特征来进行分类。其中信息增益为经验熵与条件经验熵的差值。
熵 H(D)：表示随机变量D发生的不确定性，所以与D发生的概率有关，概率越小或越大，熵都会很小，因为D会有大概率发生或不发生，其不确定性低。
条件熵 H(D|A)：在A发生的条件下，D发生的不确定性。
所以信息增益g(D,A)表示得知A的发生，对D发生的不确定性的减少程度，所以g(D,A)越大，表示选择特征的可靠性越高。具体计算公式如下：
其中，|D|为数据集的样本个数，数据集D有K个类Ck, |Ck|为第k个类的样本个数，选取特征A将数据集D分为i个子集，|Di|为第i个子集的样本个数。
ID3递归的建立决策树，从跟节点开始，对每个特征计算信息增益，选信息增益最大的特征作为节点分类特征，根据该特征可取的值建立子节点，再对子节点用同样的方法划分。所以随着决策树一层一层的生成，数据集的列数会一列一列减少。当满足停机条件时，建立叶节点。停机条件有：a. 子集中所以数据属于同一类；b. 所以特征均已被用于分类；c. 信息增益小于某个既定阈值。
python代码如下：
def createTree(dataSet, labels): classList = [item[-1] for item in dataSet] if (classList.count(classList[0]) == len(classList)): return classList[0] if (len(dataSet[0]) == 1): return majorityClass(classList) #该函数返回classlist中占比最大的类 bestFeat = maxInforGain(dataSet) #该函数计算最大增益 bestLabel = labels[bestFeat] tree = {bestLabel:{}} del(labels[bestFeat]) bestValues = set([value[bestFeat] for value in dataSet]) for value in bestValues: tree[bestLabel][value] = createTree(splitDataSet\ (dataSet, bestFeat, value), labels ) return tree 但当决策树生成了很多的叶节点时，表明模型复杂度很高。对于训练数据集来说，这样使得近似误差很小，但对于测试实例，过于复杂的模型会导致过拟合，使估计误差增大。所以需要从树的底端向上进行剪枝，剪掉一些不必要的叶节点或子树，而将其父节点作为叶节点。通过极小化损失函数实现，损失函数Ca(T)表示为：其中|T|为叶节点的个数，Nt为第t个叶节点中数据的个数，a>=0为参数。C(T)表示模型对训练数据的预测误差，|T|表示模型复杂度。a用于控制两者的权重，a越大，|T|越小（因为要极小化损失函数，a很大时，只有减小|T|来实现），模型复杂度降低；反之a很小，复杂度的权重降低。对每一个子树计算它加入决策树之前和之后的损失函数，若它的加入使树的损失函数变大，则需要剪掉子树，将它的父节点设为叶节点：
依次检查当前节点的子节点是否为叶节点
如果不是，调用函数本身继续寻找叶节点
如果是，计算有和没有这棵子树的损失函数
如果有它的损失函数更小，返回这棵子树
如果没它的损失函数更小，返回父节点作为叶节点
C4.5算法C4.5为ID3算法相似，只是C4.5选择用信息增益比来选择分类特征。信息增益比为信息增益与特征的熵的比值：
CARTCART即分类回归树，使用二元切分来处理分类或者回归问题。同样该算法的核心在于如何选择切分特征来将数据集一分为二。对于回归问题，使用平方误差最小准则：
即对所有特征K，以及每个特征可以取得的所有值S，都计算其左边集合和右边集合的平方误差之和，取其中的最小值为切分点。平方误差为当前数据集的y值与y的平均值之差的平方和，也可以表示为平均方差乘以数据集中样本数目。选好最优切分值后，将数据集分为两个子集，再继续对子集进行切分，直到满足停机条件，构建叶节点。叶节点的值为叶节点中包含的所有数据的y值的平均值。
python代码如下：
#计算最优切分点，当满足停机条件时，返回的切分特征为None def bestSplit(dataSet, leafType=regLeaf, errType=regErr, ops = (1,4)): errDec = ops[0]; minN = ops[1] if len(set(dataSet[:,-1].T.tolist()[0])) == 1: return None, leafType(dataSet) k = dataSet.shape[1] - 1 bestFea = 0; minErr = inf; bestVal = 0 for i in range(k): for value in set(dataSet[:,i].T.tolist()[0]): lMat, rMat = split(dataSet, i, value) if(shape(lMat)[0] < minN or shape(rMat)[0] < minN): continue err = errType(lMat) + errType(rMat) if (err < minErr): minErr = err bestVal = value bestFea = i if(errType(dataSet) - minErr < errDec): return None, leafType(dataSet) lMat, rMat = split(dataSet, bestFea, bestVal) if(shape(lMat)[0] < minN or shape(rMat)[0] < minN): return None, leafType(dataSet) return bestFea, bestVal def CARTree (dataSet, leafType=regLeaf, errType=regErr, ops = (1,4)): feat, val = bestSplit(dataSet,leafType,errType,ops) if feat == None: return val rtree = {} rtree['spInd'] = feat rtree['spVal'] = val lSet, rSet = split(dataSet, feat, val) rtree['left'] = CARTree(lSet, leafType, errType, ops) rtree['right'] = CARTree(rSet, leafType, errType, ops) return rtree 而对于分类问题，树的构建流程与回归树一致，只是用基尼指数最小化准则来选择特征。 数据集共有K个类，Ck为属于第k类的样本。基尼指数的定义类似于熵，表示样本集合的不确定性。Gini(D,A)表示经A=a的划分后集合D的不确定度。 为了避免过拟合，同样需要对CART树进行剪枝，可以采用交叉验证法。使损失函数中的a由小按一定规律增大，对应于每一个a，都有一个使损失函数最小的树Tt。最后通过交叉验证找出平方误差或基尼指数最小的树，即为最优决策树。