1. 由决策树的根节点到叶节点的每一条路径构建一条if-then规则
2. 路径上的内部节点的特征对应着if的判断条件，而叶节点的类对应着规则的then结论

1. 可读性和可解释性强，可通过可视化的方式直观展现 - "分而治之”（divide-and-conquer）策略
2. 对数据预处理的要求较低，不需要预先做数据规范化。这是因为决策树不是非常关注样本特征维度中的数值大小，而是更关注其代表了类别，根据所属的范畴进行二分类，这也是判别式模型的好处
3. 内存开销小，不像DNN深度学习算法需要在内存中保存大量的中间梯度变量，decision tree的内存开销是logN级别的
4. 既可以处理数值数据(连续性)，也可以处理分类数据(离散型)
5. 能够处理多分类问题(输出的Y是一个2维数组)
6. 性能优良，分类速度快，单纯由逻辑判断组成

1. 决策树很容易陷入训练样本数据的细节中，过分地细分会导致训练出一个很"复杂且深"的树出来。这是因为 太过复杂的树很容易对训练数据中的噪音过于敏感
2. 决策树本身存在"不稳定性"，训练样本集中的一些微小的变化，可能就会导致决策树建立出一个不同的分类模型，这也是决策树对训练数据样本太过敏感的表现，这个问题可以用决策森林的投票法得到缓解
3. 当数据中某些维度上的分布特别密集(这可能是采样观察量不够的原因)，决策树可能会形成偏树，这种偏树无法拟合出真实的数据规律，对之后的分类效果也会下降

1. 一是设计特征时尽量引入domain knowledge(专家领域知识)：对于业务领域专家来说，他能通过将人工判断的经验通过抽象转化成一系列的特征维度，人工的经验越丰富，所提取的特征的代表性往往就越强，决策树非常依赖于代表性强的特征
2. 二是对提取出来的特征做选择、变换和再学习，这一点是机器学习算法不管的部分
3. 现在的机器学习还做不到完全的point to point黑盒预测，前期的特征提取和特征预处理在很多场景下还依赖于专家的参与

http://scikit-learn.org/stable/modules/tree.html#tree

1. 内部节点(internal node)：表示一个特征维度或一个属性
2. 叶节点：表示一个类

https://technet.microsoft.com/zh-cn/library/cc645758(v=sql.105).aspx
http://www.jianshu.com/p/3997745880d4

1. 开始，构建根节点，将所有训练数据都放在根节点
2. 选择一个最优特征，选择的标准是信息增益(比)最大或基尼指数最小，即选择能让分类后的样本纯度最大的特征维度。按照这一特征将训练数据集分隔成子集，使得各子集有一个在当前条件下最好的分类
3. 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点中去；
4. 如果还有子集不能被"基本正确"分类(纯度还不高)，那么就对这些子集继续选择新的最优特征(局部最优)，继续对其进行分割，构建相应的节点
5. 如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止
6. 最后每个子集都被分到叶节点上，即都有了明确的类，这就生成了一棵决策树

从贝叶斯后验概率的角度来看，决策树学习是由训练数据集估计后验条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个(当然最大似然后验概率只有一个)。我们选择的条件概率模型应该不仅对训练数据有很好的拟合而且对未知数据有很好的预测

http://scikit-learn.org/stable/modules/tree.html
http://www.cnblogs.com/yonghao/p/5061873.html
http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
http://blog.csdn.net/nieson2012/article/details/51314873
http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

信息增益大的特征具有更强的分类能力，同时获得更好的经验风险

样本数：15
样本类别 K = 2：是；否
特征维度(属性)：
1）年龄：青年；中年；老年
2）有工作：是；否
3）有自己的房子：是；否
4）信贷情况：一般；好；非常好

http://zh.numberempire.com/graphingcalculator.php?functions=log%281-x%29%2C1%2F%28x-1%29

1. 若当天结点中的D所有实例都属于同一类Ck，则T为单节点树(这是建树停止的强条件)，并将类Ck作为该节点的类标记。返回T
2. 若当前可选取的特征A为空(即无特征可选)，则T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记(有可能纯度未达到100%)，返回T
3. 否则，从当前D中计算所有特征的信息增益，选择信息增益最大的特征Ag，如果Ag对应的信息增益小于收敛阈值(类似于损失函数减少量阈值，用于提前终止，快速收敛)，则设置T为单节点树，并将当前D中实例数量最大的类Ck作为该结点类标记，返回T
4. 否则，对Ag的每一可能取值ai，依照Ag = ai将D分割成若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子节点沟通树T，返回T
5. 对第i个子结点，已Di为训练集，以A-{Ag}为特征集(在剩下来的特征中继续寻找最优)，递归地调用1~4步。得到子树Ti，返回Ti

1. 由于特征A3(有自己的房子)的信息增益最大，所以选择特征A3作为根节点的特征。它将训练数据集D划分为两个子集D1(A3取值为"是")和D2(A3取值为"否")
2. 由于D1只有同一类label的样本(即纯度已经100%)，即"有自己房子"的样本的label都是能够予以放款。所以D1成为一个叶节点，结点的类标记为"是"
3. 对D2则需要从特征A1(年龄)、A2(有工作)和A4(信贷情况)中选择新的特征，计算各个特征的信息增益
g（D2，A1） = H（D2） - H（D2 | A1） = -3/9 * log3/9 - 6/9 * log6/9 - H（D2 | A1） = 0.918 - H（D2 | A1）= 0.918 -【4/9* H(D21) + 2/9 * H(D22) + 3/9 * H(D23)】
= 0.918 - 【4/9 * ( -3/4 * log3/4 - 1/4 * log1/4) + 2/9 * 0 + 3/9 * (-2/3 * log2/3 - 1/3 * log1/3) 】= 0.918 - 0.667 = 0.251
g（D2，A2） = H（D2） - H（D2 | A2） = 0.918
g（D2，A4） = H（D2） - H（D2 | A4） = 0.474
# 可以看到，在条件概率对应的特征Ag下，如果依据该特征进行分类后，不管label是哪一类，只要纯度最高，则对应的信息增益就是最高的，信息增益关注的是分类后的纯度

4. 选择信息增益最大的A2(有工作)作为结点的特征
5. 由于A2有两个可能的取值：
1）一个对应"是"(有工作)的子结点，包含3个样本，它们属于同一类，所以这就是一个叶节点，标记为"是"；
2）另一个是对应"否"(无工作)的子节点，包含6个样本，它们也属于同一类，所以这也是一个叶节点，类标记为"否"

6. 由于到了这一步后，所以子节点的纯度都已经到100%，因此建树过程结束

1. 左分支是取值为"是"的分支
2. 右分支有取值为"否"的分支

1. 分类树对特征空间的划分是针对离散的特征(例如年龄、收入、工作等)进行的，而回归树的特征数量往往是一个连续区间(例如【0，10.5】)，回归树是将特征空间"采样化"成m个数量的区域Rm，只要落在这个区域内的特征，不管其值如何，都统一归一化为同一个特征值
2. 分类树的输入样本在一个特征中的特征值是离散有限的，但是回归树的输入样本在一个特征中的特征值是连续无限的，所以回归树这里最重要的"采样思想"，在每个特征单元Rm上有一个固定的输出值Cm，本质上就是用线性分类器在对连续变量进行离散的拟合

# -*- coding: utf-8 -*-

# Import the necessary modules and libraries
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

import pydotplus
from sklearn import tree

# Create a random dataset
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

# Fit regression model
regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
print X
print y
regr_1.fit(X, y)
regr_2.fit(X, y)

# Predict
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)

# generate a PDF file
\'\'\'
dot_data = tree.export_graphviz(regr_1, out_file=None)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf("dt_2.pdf")

dot_data = tree.export_graphviz(regr_2, out_file=None)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf("dt_5.pdf")
\'\'\'


# Plot the results
plt.figure()
plt.scatter(X, y, c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
#plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

1. 该样本总共有80个，特征为X坐标，特征值为Y坐标，这样很利于我们画图可视化和理解
2. 回归树遍历所有特征，尝试将每个特征作为切分变量，并计算在该切分点下，两边区间Rm的最小平方误差Cm(Cm是一定可以算出来的)
3. 在第一轮选择中，回归树最终选择了3.1328这个点，这时候
　1）左区间的最优输出值(即采样值)(其实就是均值)是0.5712
　2）右区间的最优输出值是-0.6675
4. 由于我们指定了树深度为2，所以回归树继续递归地在第一轮分出的子区间中寻找最优切分点
1）这一次在左区间找到了0.5139
2）在右区间找到了3.8502
5. 根据新的切分点将左右子区间再次切分成子区间，这样就有4个区间了：R1【0: 0.5139】；R2【0.5139: 3.1328】；R3【3.1328: 3.8502】；R4【3.8502: 5】，这4个区间的输出值就是这4个区间的样本均值：
Cm1 = 0.0524；Cm2 = 0.7138；Cm1 = -0.4519；Cm1 = -0.8686；

1. 设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。遍历所有特征，计算每个特征分类后的条件基尼指数
2. 在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其切分点(均值)作为最优特征和最优切分点。将训练集分配到这两个子节点中
3. 对两个子节点递归地调用1、2过程，直至满足条件。(结点中的样本个数小于阈值、或样本集的基尼指数小于阈值)、或者没有更多特征
4. 生成CART决策树

A1：年龄
1：青年
2：中年
3. 老年

A2：有工作
1. 有工作
2. 无工作

A3：有自己的房子
1. 有房子
2. 无房子

A4：信贷情况
1. 非常好
2. 好
3. 一般

https://cethik.vip/2016/09/21/machineCAST/

1 originally launched in 1978 , this popular film was re-introduced in 1998 to a whole new generation of moviegoers .  based on the mighty successful musical from broadway , grease was followed in 1980 with the less stellar grease 2 ( 6 . 5/10 ) ,  starring a young michelle pheiffer in one of her first feature film roles .  plot : high-school musical set in the 1950\'s showcasing the relationship between the cool danny zuko of the t-birds ( travolta ) and the innocent and pure sandy olsen ( newton-john ) from australia .  the film follows the couple and their vivacious friends during their last year at rydell high through song , dance and humour .  critique : fun-loving , energetic and innocent look back at times much simpler .  this movie effectively juggles a thin romantic story line and the overall experience of the 1950\'s , with a superb soundtrack and some great dance numbers .  admittedly , i am somewhat biased in this opinion , since this film blasts me into my past as a rebellious youth ( grease was one of schmoe\'s first big-screen experiences , and every other scene sends me reeling into the times of my elaborate grease bubble-gum card collection ) , and the lesser responsibilities that i possessed at that time .  but apart from the nostalgic vibe , i was still extremely impressed by this film , as it continued to amuse me , despite my previous dozen or so viewings .  this film took john travolta from a dim-witted " sweathog " on tv\'s welcome back kotter , and transformed him into a movie-star of spectacular proportions ( saturday night fever ( 7 . 5/10 ) in 1979 confirmed that sudden popularity ) .  unfortunately for the rest of the cast , his popularity was not terribly contagious , despite their effective showings in this classic movie .  on the down side , some of the absolute innocence in this film might bore or turn people off ( like when sandy sings about " drinking lemonade " and " staying out until 10 " with danny in " summer nights " ) , and the plot isn\'t exactly the most elaborate story-line ever created , but despite these small reservations , this movie carries enough great music and high energy to keep anyone amused through its rapid 110 minute running time ( and believe me . . . i  am not a fan of the musicals ! ! ) .  make sure to look for a young lorenzo lamas in the static role of the brainless football player , as well as the national bandstand dance contest as one of the film\'s absolute highlights .  and don\'t forget to buy the popular soundtrack afterwards , so that you could listen to its peppy tunes whenever you\'re feeling a little blue .  little known facts : henry winkler , of tv\'s happy days\' fonzie fame , turned down the part of danny zuko because he did not want to be typecast for the rest of his career .  both travolta and conaway were smitten by newton-john during the filming of this picture .  conaway eventually bowed out of the woo-fest , and married newton-john\'s sister a year later ( divorced after five years ) .  

0 confucius once said , " governing a nation is like cooking a small fish -- don\'t overdo it . "  his maxim might be easily applied to writing a comedy script , for quantity over quality is one of the worst mistakes an amateur scribe can make .  granted , mike judge , writer-director of the workplace satire office space isn\'t exactly an amateur ( his most infamous work , the mtv series " beavis and butt-head " was pure gold for its network ) .  but unfailingly , judge manages to make some rather inexcusable mistakes in office space by spreading an iffy plot over too much ground .  the iffiness in judge\'s plot -- a group of coworkers plan the downfall of their despicable boss -- is not in its appeal .  in fact , based on the popularity of scott adams\' cartoon " dilbert , " which will soon have its own television series , a satirical view of the american workplace is a hot item in hollywood .  unfortunately the concept lends itself to skit-length sequences which would be more at home on the set of " saturday night live " rather than a full-length feature .  the most convincing evidence of this are the trailers for office space , which feature almost all of the movie\'s top content ; this leaves the actual picture appearing very deflated .  other evidence of office space\'s failure to work are its lack of good jokes .  the comedy is marginally funny at best , but not enough to get a packed house of theater-goers to laugh out loud .  the material in the movie is on-key for an older demographic than judge is used to targeting , and this could partially explain his work here .  however , the movie is loaded with too many misfires -- including the token plot -- to allow for any excuse .  the plot centers around three or four cubicled engineers , headed up by peter gibbons ( ron livingston ) , at a company named initech .  after the movie elaborately establishes the miserable working conditions at initech , the movie introduces us to two consultants ( john c . mcginley and paul willson ) which are in charge of " downsizing " the company\'s payroll .  when peter and his gang learns of this , as well as the reason behind it -- so their smooth talking boss bill lumbergh ( gary cole ) \'s stock will go up -- they set about creating a plan to see his downfall .  the circumstances that follow were obviously intended to be hilarious but they come out as anything but .  a sympathetic cast and a muddled jennifer aniston-as-love-interest subplot are all that keep this one together , but it\'s definitely missable in lieu of something more intelligent .  

bad?
-N-> class 1    (333 for class 0, 533 for class 1)
-Y-> class 0    (358 for class 0, 176 for class 1)

1. 被分到True类(class = 1)的866个样本中
　　1) 533的label class = 1
　　2) 333的label class = 0：看起来还有很多样本虽然在这个维度分类点有相同的区间范围，但是一定还在其他维度有不同的表现，似乎还应该继续分下去

2. 被分到False类(class = 0)的534个样本中
　　1) 358的label class = 0
　　2) 176的label class = 1

# Accuracy of training set
print np.mean(dt.predict(X_tr) == Y_tr)
0.636428571429

# Accuracy of dev set
print np.mean(dt.predict(X_de) == Y_de)
0.605

# Accuracy of test set
print np.mean(dt.predict(X_te) == Y_te)
0.595

bad?
-N-> worst?
|    -N-> class 1    (281 for class 0, 514 for class 1)
|    -Y-> class 0    (52 for class 0, 19 for class 1)
-Y-> stupid?
|    -N-> class 0    (281 for class 0, 168 for class 1)
|    -Y-> class 0    (77 for class 0, 8 for class 1)
0.66
0.62
0.615

bad?
-N-> worst?
|    -N-> many?
|    |    -N-> class 1    (204 for class 0, 274 for class 1)
|    |    -Y-> class 1    (77 for class 0, 240 for class 1)
|    -Y-> present?
|    |    -N-> class 0    (52 for class 0, 13 for class 1)
|    |    -Y-> class 1    (0 for class 0, 6 for class 1)
-Y-> stupid?
|    -N-> wonderfully?
|    |    -N-> class 0    (280 for class 0, 153 for class 1)
|    |    -Y-> class 1    (1 for class 0, 15 for class 1)
|    -Y-> bob?
|    |    -N-> class 0    (76 for class 0, 4 for class 1)
|    |    -Y-> class 1    (1 for class 0, 4 for class 1)
0.676428571429
0.645
0.625

bad?
-N-> worst?
|    -N-> many?
|    |    -N-> dull?
|    |    |    -N-> class 1    (184 for class 0, 271 for class 1)
|    |    |    -Y-> class 0    (20 for class 0, 3 for class 1)
|    |    -Y-> ludicrous?
|    |    |    -N-> class 1    (70 for class 0, 240 for class 1)
|    |    |    -Y-> class 0    (7 for class 0, 0 for class 1)
|    -Y-> present?
|    |    -N-> brilliant?
|    |    |    -N-> class 0    (52 for class 0, 9 for class 1)
|    |    |    -Y-> class 1    (0 for class 0, 4 for class 1)
|    |    -Y-> class 1    (0 for class 0, 6 for class 1)
-Y-> stupid?
|    -N-> wonderfully?
|    |    -N-> life?
|    |    |    -N-> class 0    (205 for class 0, 79 for class 1)
|    |    |    -Y-> class 0    (75 for class 0, 74 for class 1)
|    |    -Y-> area?
|    |    |    -N-> class 1    (0 for class 0, 15 for class 1)
|    |    |    -Y-> class 0    (1 for class 0, 0 for class 1)
|    -Y-> bob?
|    |    -N-> buddy?
|    |    |    -N-> class 0    (76 for class 0, 2 for class 1)
|    |    |    -Y-> class 1    (0 for class 0, 2 for class 1)
|    |    -Y-> falls?
|    |    |    -N-> class 1    (0 for class 0, 4 for class 1)
|    |    |    -Y-> class 0    (1 for class 0, 0 for class 1)
0.699285714286
0.645
0.635

bad?
-N-> worst?
|    -N-> many?
|    |    -N-> dull?
|    |    |    -N-> both?
|    |    |    |    -N-> class 1    (149 for class 0, 164 for class 1)
|    |    |    |    -Y-> class 1    (35 for class 0, 107 for class 1)
|    |    |    -Y-> terrific?
|    |    |    |    -N-> class 0    (20 for class 0, 1 for class 1)
|    |    |    |    -Y-> class 1    (0 for class 0, 2 for class 1)
|    |    -Y-> ludicrous?
|    |    |    -N-> awful?
|    |    |    |    -N-> class 1    (61 for class 0, 236 for class 1)
|    |    |    |    -Y-> class 0    (9 for class 0, 4 for class 1)
|    |    |    -Y-> class 0    (7 for class 0, 0 for class 1)
|    -Y-> present?
|    |    -N-> brilliant?
|    |    |    -N-> approach?
|    |    |    |    -N-> class 0    (52 for class 0, 6 for class 1)
|    |    |    |    -Y-> class 1    (0 for class 0, 3 for class 1)
|    |    |    -Y-> class 1    (0 for class 0, 4 for class 1)
|    |    -Y-> class 1    (0 for class 0, 6 for class 1)
-Y-> stupid?
|    -N-> wonderfully?
|    |    -N-> life?
|    |    |    -N-> plausible?
|    |    |    |    -N-> class 0    (205 for class 0, 73 for class 1)
|    |    |    |    -Y-> class 1    (0 for class 0, 6 for class 1)
|    |    |    -Y-> else?
|    |    |    |    -N-> class 1    (54 for class 0, 70 for class 1)
|    |    |    |    -Y-> class 0    (21 for class 0, 4 for class 1)
|    |    -Y-> political?
|    |    |    -N-> class 1    (0 for class 0, 15 for class 1)
|    |    |    -Y-> class 0    (1 for class 0, 0 for class 1)
|    -Y-> bob?
|    |    -N-> meeting?
|    |    |    -N-> treats?
|    |    |    |    -N-> class 0    (75 for class 0, 0 for class 1)
|    |    |    |    -Y-> class 1    (1 for class 0, 2 for class 1)
|    |    |    -Y-> class 1    (0 for class 0, 2 for class 1)
|    |    -Y-> give?
|    |    |    -N-> class 1    (0 for class 0, 4 for class 1)
|    |    |    -Y-> class 0    (1 for class 0, 0 for class 1)
0.722857142857
0.62
0.6425

1. C（T）只由训练数据决定，它反映了模型对训练数据的预测误差，即模型与训练数据的拟合程度
2. | T | 表示模型复杂度(等比于叶节点个数)
3. 参数 a>=0 控制两者之间的平衡
　　1）较大的a的情况下：| T | 就被迫要尽量小，但是C（T）相对地就会增加，这动态地促使模型选择较简单的模型(浅树)
　　2）较小的a的情况下：| T | 就被迫要尽量大，C（T）就会相对地减小，促使选择较复杂的模型(深树)

1. 子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高
2. 相反子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好

https://github.com/hal3/ciml
https://github.com/hal3/ciml/tree/master/labs/lab1-DTs-and-overfitting
http://ciml.info/dl/v0_99/ciml-v0_99-ch01.pdf 
http://scikit-learn.org/stable/auto_examples/tree/plot_tree_regression.html