一、决策树剪枝
1.目的
剪枝（pruning）是决策树学习算法解决过拟合问题的主要手段。
在决策树学习中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，这时有可能因训练样本学得“太好”了，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。
剪枝策略分为预剪枝（prepruning）和后剪枝(post-pruning)。
2.剪枝前
使用上一次作业中的数据集（稍作调整）：判断特征是否属于我室友sjh。
划分训练集和验证集：
回顾一下剪枝操作前的决策树的样子：
以及数据集当前的信息熵：
3.预剪枝
①概念
预剪枝（pre-pruning）：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
②过程
先计算出所有特征的信息增益值：
调用函数计算信息增益
def chooseBestFeatureToSplit(dataSet, labels):
"""
选择最好的数据集划分特征，根据信息增益值来计算
:param dataSet:
:return:
"""
# 得到数据的特征值总数
numFeatures = len(dataSet[0]) - 1
# 计算出基础信息熵
baseEntropy = calcShannonEnt(dataSet)
# 基础信息增益为0.0
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=dataSet, axis=i, value=value)
# 计算出权重
prob = len(subDataSet) / float(len(dataSet))
# 计算出当前特征值的熵
newEntropy += prob * calcShannonEnt(subDataSet)
# 计算出“信息增益”
infoGain = baseEntropy - newEntropy
#print('当前特征值为：' + labels[i] + '，对应的信息增益值为：' + str(infoGain)+"i等于"+str(i))
#如果当前的信息增益比原来的大
if infoGain > bestInfoGain:
# 最好的信息增益
bestInfoGain = infoGain
# 新的最好的用来划分的特征值
bestFeature = i
#print('信息增益最大的特征为：' + labels[bestFeature])
return bestFeature
打印结果返回信息增益值最大的三个特征：发色、籍贯和发型
先选择发型来对数据集进行划分，这会产生三个分支，如下图所示：
但因为是预剪枝，所以要判断是否应该进行这个划分，判断的标准就是看划分前后的泛化性能是否有提升，也就是如果划分后泛化性能有提升，则划分；否则，不划分。
下面来看看是否要用发型进行划分，划分前：所有样本都在根节点，把该结点标记为叶节点，其类别标记为训练集中样本数量最多的类别，然后用验证集对其性能评估，可以看出样本{13,14}被正确分类，其他被错误分类，因此精度为50%。
划分后： 划分后的的决策树如下，很明显，验证集上只有14被分类错误，其余三个样例都分类正确。此时精度是3/4 = 75% > 50%。所以，我们可以用发型进行划分。
接下来，决策树算法对结点 ②进行划分，再次使用信息增益挑选出值最大的那个特征，信息增益值最大的特征是“发色”，则使用发色划分后决策树为：
计算方法和上面类似所以略过
依旧用验证集进行计算，划分后精度为：3/4=75%=75%，因此可以划分结点 ②。
下一步划分最优的属性为“籍贯”，划分后验证集精度为100%>75%，因此这个划分也可以提升验证集精度，允许划分。
所以基于预剪枝策略生成的最终的决策树为：
4.后剪枝
①概念
后剪枝(post-pruning)是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
②过程
先整理一下剪枝前的决策树：
代入验证集的数据，易知该决策树的验证集精度为3/4=75%。后剪枝首先考察上图中的结点⑤，若将其领衔的分支剪除，则相当于把②替换为叶结点。
替换后的叶结点未包含训练样本，选择将其类别标记为"是"：
此时决策树的验证集精度仍为3/4=75%。于是，后剪枝策略决定不进行剪枝。
然后考察结点②，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为{1,6,8,10} 的训练样例，叶结点标记为"是"。
此时决策树的验证集精度仍为3/4=75%。于是，后剪枝策略决定不进行剪枝。
最后考察结点①，若将其领衔的子树替换为叶结点，则此时决策树的验证集精度为初始值75%。于是，后剪枝策略决定不进行剪枝。
最终，基于后剪枝策略所生成的决策树如下图所示，其验证集精度为75%（由于验证集选的不好，导致后剪枝没有变化，以后有时间重新划验证集再试一下）
5.总结
后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
二、knn与决策树对比
KNN算法，对于数值型的数据适配度比较高，且预处理较少，一般单一类数据归一化即可，选择求距离的公式也可以依托实际进行。KNN有算法的一个优点为对异常值不敏感，但是在预处理的时候，如果能将极端数据去掉后再进行归一化，分类效果会更好。
决策树算法对于数据预处理要求高一点，需要预分类，分类过程如果面向问题本身会更加好，用于制作实际算法投入运用的话，由用户来进行一个标度效果对于特定用户本身会更好。但是数据过多的时候，决策树剪枝方面要多进行考虑，但是势必带来准确度降低。