开篇
决策树（Decision Tree）是最流行的机器学习算法之一。决策树可以解决分类（classification）和回归分析（Regression）的问题。sklearn中可以仅仅使用几行代码就可以完成决策树的建立。但是，这对于真正想从事机器学习的朋友们是不够的。这一讲，我们就着重来详解一下决策树。
决策树的优势
我们知道机器学习中有很多的模型算法，为什么决策树可以长盛不衰？它到底有什么优势？这是我们学习决策树的基础。
决策树
一起先来看一个决策树的实例。决策树的逻辑更加接近于人类判断的逻辑。比较好理解。逻辑树模型的判断逻辑非常清晰，且可视化，如上图。在判断泰坦尼克号上幸存人员的时候，通过决策树应该怎么做呢？
首先，我们判断性别是否是男性：是（Yes）或者否（No）；
如果是男性，判断年龄是否大于9.5；
如果是女性，则此人是存活（Survived）。。。
决策树每一个判断都是一个问题，而答案的不同则会长出不同的树枝。我们可以看出决策树整个的逻辑非常的清晰和简单。
什么是决策树？
数据挖掘和机器学习中的决策树训练，使用决策树作为预测模型来预测样本的类标。这种决策树也称作分类树或回归树。在这些树的结构里， 叶子节点给出类标而内部节点代表某个属性。
在决策分析中，一棵决策树可以明确地表达决策的过程。在数据挖掘中，一棵决策树表达的是数据而不是决策。本页的决策树是数据挖掘中的决策树。 -----维基百科
数据
假设我们拿到的数据如上，第一步是分析数据的特征变量（Feature）有哪些？上图中，特征变量就有 天气（outlook）、温度（temp.）、湿度（humidity）、有风（windy）和是否出游（play）。
从决策树中，所有的判断都是从决策树的根部节点开始，慢慢的一步一步的生出中间的过渡节点，最后长出叶子（leaf node）并形成判断并且可以用来预测。
那问题来了，每个节点都对应一个特征变量，那我们该怎么选择最重要的特征变量作为根节点呢？
创建决策树
现在有很多办法筛选特征变量，但是最常用的两种方法是：CART（Classification and Regression Trees） 和 ID3 （Iterative Dichotomiser 3）。CART方法是以Gini 指数为基准，而ID3是以熵变函数作为基准。
具体的公式可以直接参看维基百科：
CART方法
ID3方法
公式是需要例子去消化并记忆的。下面，我们一起来通过这两种方法筛选出最重要的特征变量吧。
使用ID3方法：
在ID3方法中，我们需要计算每个特征变量的熵。下面就是公式。
熵
分别计算每一个特征变量的熵，我们拿有风与否（windy）举例：
首先，我们要算一下play（yes或者no）的总熵：
在14行数据中，有9行数据play显示为yes，另外5行play显示为no
那么，
E(yes) = -(9/14) * ln(9/14) = 0.41
E(no) = -(5/14) * ln(5/14) = 0.53
H(S) = E(yes) + E(no) = 0.41 + 0.53 = 0.94
当windy是false的时候，有6行数据显示play为yes，还有2行数据显示play为no。
当windy是true的时候，有3行数据显示play为yes，还有3行数据显示play为no。
E(windy = false) = -6/8 * log(6/8) - 2/8 * log(2/8) = 0.811
E(windy = true) = -3/6 * log(3/6) - 3/6 * log(3/6) = 1
总共有14行数据，那么，当选择windy的时候，熵的平均值使用加权平均数即可得：
I(windy）= 8/14 * 0.811 + 6/14 * 1 = 0.892
我们得到了H(S)和信息值 I(windy），那么选择windy带来的信息增益是多少呢？
Gain(windy) = H(S) - I(windy) = 0.94 - 0.892 = 0.048
我们需要计算所有特征变量的 信息增益，从中选取信息增益最大的 特征变量，则是根节点。当我们之后选择过渡节点的时候，同样重复上述过程即可。
最后的决策树如下图所示：
决策树
CART方法
同样的，我们拿windy作为示范：
当windy是false的时候，有6行数据显示play为yes，还有2行数据显示play为no。
p（windy-false,play-yes）= 6/8
p（windy-false,play-no）= 2/8
Gini(windy-false) = 1 - p（windy-false,play-yes）^2 - p（windy-false,play-no）^2
= 1 - (6/8)^2 - (2/8)^2 = 3/5
当windy是true的时候，有3行数据显示play为yes，还有3行数据显示play为no。
p（windy-true,play-yes）= 3/6
p（windy-true,play-no）= 3/6
Gini(windy-true) = 1 - p（windy-true,play-yes）^2 - p（windy-true,play-no）^2
= 1 - (3/6)^2 - (3/6)^2 = 1/2
那么，当选择windy时，平均Gini值为：
Gini(windy）= 8/14 * 3/5 + 6/14 * 1/2 = 0.557
Gini值与之前算的信息增益有所不同，Gini值越小，证明模型越好。
python 机器学习包Sklearn中如何实现决策树
sklearn
sklearn中引入tree模块，通过tree.DecisionTreeClassifier() 就可以创建一个决策树。
clf = clf.fit(X_train, Y_train) 通过fit函数就可以实现决策树模型的训练了。
然而在决策树中，可以定义很多参数。如上图所示。我们一个一个的过一遍这些参数。
- criterion: string类型，可选（默认为"gini"）：衡量分类的质量。支持的标准有"gini"代表的是Gini impurity(不纯度)与"entropy"代表的是information gain（信息增益）。
- splitter: string类型，可选（默认为"best"）：在节点中选择分类的策略。支持的策略有"best"，选择最好的分类，"random"选择最好的随机分类。
- max_features: int,float,string or None 可选（默认为None）在进行分类时需要考虑的特征数。1.如果是int，在每次分类是都要考虑max_features个特征。2.如果是float,那么max_fea
- max_depth: int or None,可选（默认为"None"）表示树的最大深度。如果是"None",则节点会一直扩展直到所有的叶子都是纯的或者所有的叶子节点都包含少于min_samples_split个样本点。忽视max_leaf_nodes是不是为None。
- min_samples_split: int,float,可选（默认为2）：区分一个内部节点需要的最少的样本数。
- min_samples_leaf: int,float,可选（默认为1）：一个叶节点所需要的最小样本数：
- min_weight_fraction_leaf: float,可选（默认为0）： 一个叶节点的输入样本所需要的最小的加权分数。
- max_leaf_nodes: int,None 可选（默认为None）：在最优方法中使用max_leaf_nodes构建一个树。最好的节点是在杂质相对减少。如果是None则对叶节点的数目没有限制。如果不是None则不考虑max_depth.
- class_weight: dict,list of dicts,"Banlanced" or None,可选（默认为None）： 表示在表{class_label:weight}中的类的关联权值。如果没有指定，所有类的权值都为1。对于多输出问题，一列字典的顺序可以与一列y的次序相同。 "balanced"模型使用y的值去自动适应权值，并且是以输入数据中类的频率的反比例。
- random_state: int,RandomState instance or None： 如果是int,random_state 是随机数字发生器的种子；如果是RandomState，random_state是随机数字发生器，如果是None，随机数字发生器是np.random使用的RandomState instance.
- persort: bool,可选（默认为False）：是否预分类数据以加速训练时最好分类的查找。在有大数据集的决策树中，如果设为true可能会减慢训练的过程。当使用一个小数据集或者一个深度受限的决策树中，可以减速训练的过程。
总结
现在，python中关于机器学习的包有很多，这大大方便了我们的使用。但同时也助长了我们的惰性。不求原理，只求输入几行代码出结果就行。
逃学博士会慢慢地将机器学习的常用算法原理过一遍。谢谢大家耐心的看完。
