决策树 Decision Tree
C5.0
先简述下C5.0，C5.0是一个商业软件，对于公众是不可得到的。它是在C4.5算法做了一些改进。比之C45，减少了内存，使用更少的规则集，并且准确率更高。
CART：
Classification and Regression Trees与C4.5算法是非常相似的，也只是如何选取节点的区别，但是CART支持预测连续的值（回归）。CART只构建二叉树，而C4.5则能构建多叉树。
Gini：
每个属性的划分按照能减少的杂质的量来进行排序，而杂质的减少量定义为划分前的杂质减去划分后的每个节点的杂质量划分所占比率之和。而杂质度量方法常用Gini指标，假设一个样本共有C类，那么一个节点A的Gini不纯度可定义为：
其中Pi表示属于i类的概率，当Gini(A)=0时，所有样本属于同类，所有类在节点中以等概率出现时，Gini(A)最大化，此时C(C-1)/2。
范例：
举个栗子，依旧使用如下数据：
假设现在来看Student属性，那么按照它划分后的Gini指数计算如下：
Gini(row1) = 1-(6/9)^2-(3/9)^2 = 4/9 Gini(row2) = 1-(1/5)^2-(4/5)^2 = 8/25 Gini = 9/14 * 4/9 + 5/14 *8/25 = 14/35
之后便是算出所有属性的Gini值，Gini值越小，说明按照这样划分后杂乱度就越小。
Python实现方法：
使用sklearn库中的DecisionTreeClassifier()方法。这个方法是基于CART的，但是可以使用Information Gain的方法来分，也就是使用C4.5的方法来进行划分，但是依旧是二叉树而不能生成多叉树。 使用pydotplus库，和第三方开源画图工具graphviz进行画图，graphviz可以在http://www.graphviz.org/中下载，并需要在Path中配置相应的环境变量，默认路径是：C:\Program Files (x86)\Graphviz2.38\bin。如果配置完环境变量还是提示找不到graphviz，可以在pydotplus源码中默认Path默认路径：C:\Users\用户名\AppData\Local\Programs\Python\Python35-32\Lib\site-packages\pydotplus，下面的graphviz.py文件，并修改def find_graphviz():方法下的if 'PROGRAMFILES' in os.environ:变成if False:，并将else条件修改为path = r"C:\Program Files (x86)\Graphviz2.38\bin"。 以上方法实测有效，基于Python3.5，如果是Python，应该使用pydot库，理论上也适用。
下面代码所需的car.data，可以去 https://archive.ics.uci.edu/ml/datasets/Car+Evaluation下载。 如果无法使用pydotplus，我们可以只输出文字形式：
import numpy as np
from sklearn import tree
from sklearn.feature_extraction import DictVectorizer
from sklearn.externals.six import StringIO
import pydotplus
data = []
labels = []
with open("car.data") as ifile:
for line in ifile:
rowDict = {}#data需要是字典形式，因为之后需要使用DictVectorizer()修改字符串数据类型，以便符合DecisionTreeClassifier()
tokens = line.strip().split(',')
rowDict['buying']=tokens[0]#分割数据，将label与data分开
rowDict['maint']=tokens[1]
rowDict['doors']=tokens[2]
rowDict['persons']=tokens[3]
rowDict['lug_boot']=tokens[4]
rowDict['safety']=tokens[5]
data.append(rowDict)
labels.append(tokens[-1])
x = np.array(data)
labels = np.array(labels)
y = np.zeros(labels.shape)#初始label全为0
#print(x[1199])#调试用
#print(labels[1199])
y[labels =='vgood']=1#当label等于这三种属性的话，设置为1。
y[labels =='good']=1
y[labels =='acc']=1
print(y[1199])
vec = DictVectorizer()#转换字符串数据类型
dx = vec.fit_transform(x).toarray()
#print(dx[:5])#调试用
#print(vec.get_feature_names())
clf = tree.DecisionTreeClassifier(criterion = 'entropy',max_depth=7,min_samples_split=20,min_samples_leaf=10) #CART算法，使用entropy作为标准
clf = clf.fit(dx,y)#导入数据
print(clf)
with open("tree.dot",'w') as f:
f=tree.export_graphviz(clf,feature_names=vec.get_feature_names(),out_file = f)#输出结果至文件
使用pydotplus+graphviz进行决策树的图像展示：
dot_data = StringIO()
tree.export_graphviz(clf,feature_names=vec.get_feature_names(),out_file=dot_data)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("tree.pdf")
剪枝：
如果是使用sklearn库的决策树生成的话，剪枝方法有限，仅仅只能改变其中参数来进行剪枝。 DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=7,
max_features=None, max_leaf_nodes=None,
min_impurity_split=1e-07, min_samples_leaf=10,
min_samples_split=20, min_weight_fraction_leaf=0.0,
presort=False, random_state=None, splitter='best')
criterion: ”gini” or “entropy”(default=”gini”)是计算属性的gini(基尼不纯度)还是entropy(信息增益)，来选择最合适的节点。
splitter: ”best” or “random”(default=”best”)随机选择属性还是选择不纯度最大的属性，建议用默认。
max_features: 选择最适属性时划分的特征不能超过此值。
当为整数时，即最大特征数；当为小数时，训练集特征数*小数；
if “auto”, then max_features=sqrt(n_features).
If “sqrt”, thenmax_features=sqrt(n_features).
If “log2”, thenmax_features=log2(n_features).
If None, then max_features=n_features.
max_depth: (default=None)设置树的最大深度，默认为None，这样建树时，会使每一个叶节点只有一个类别，或是达到min_samples_split。
min_samples_split:根据属性划分节点时，每个划分最少的样本数。
min_samples_leaf:叶子节点最少的样本数。
max_leaf_nodes: (default=None)叶子树的最大样本数。
min_weight_fraction_leaf: (default=0) 叶子节点所需要的最小权值
进阶：
另外还有以下几种进阶的剪枝方式：
Reduced-Error Pruning(REP,错误率降低剪枝):
决定是否修剪这个结点有如下步骤组成：
1：删除以此结点为根的子树
2：使其成为叶子结点
3：赋予该结点关联的训练数据的最常见分类
4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点
从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到会降低验证集合精度为止。
Pessimistic Error Pruning(PEP，悲观剪枝）：
先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项式分布，并计算它的标准差。对于给定的置信区间，采用下界估计作为规则性能的度量。这样做的结果，是对于大的数据集合，该剪枝策略能够非常接近观察精度，随着数据集合的减小，离观察精度越来越远。该剪枝方法尽管不是统计有效的，但是在实践中有效。
Cost-Complexity Pruning(CCP、代价复杂度)： 暂时不会╮(╯▽╰)╭