摘要：要找到有情人，通常是一个漫长的过程。在scikit-learn中，如何模拟人类的决策过程？决策树的目的是构建一颗最优的二叉分割树，因此从根节点往下，每一个结点的条件选择，都是为了让树结构最简洁。
姻缘天注定，一段婚姻一段缘，是报恩报怨，还是讨债还债，在一开始，谁都不知道。但可以确定一点，今生定会在一起，无论是长相厮守，还是短暂快乐。
佛曰：和有情人，做快乐事，别问是劫还是缘。
要找到有情人，通常是一个漫长的过程，也许会经历很多场相亲活动。时间久了，对相亲也有更多的认识，并且积累和记录一些数据，如下表：
| 序号 | 身高 | 房子 | 车子 | 长相 | 工作 | 约否 |
|---|---|---|---|---|---|---|
| 1 | 1.80 | 有 | 无 | 6.5 | fact | 约 |
| 2 | 1.62 | 有 | 无 | 5.5 | IT | 约 |
| 3 | 1.71 | 无 | 有 | 8.5 | bank | 约 |
| 4 | 1.58 | 有 | 有 | 6.3 | bank | 约 |
| 5 | 1.68 | 无 | 有 | 5.1 | IT | 不约 |
| 6 | 1.63 | 有 | 无 | 5.3 | bank | 不约 |
| 7 | 1.78 | 无 | 无 | 4.5 | IT | 不约 |
| 8 | 1.64 | 无 | 无 | 7.8 | fact | 不约 |
| 9 | 1.65 | 无 | 有 | 6.6 | bank | 约吗？ |
前面8条数据为过往的相亲记录，最后字段为是否愿意继续约会的记录。如前4条数据，会愿意继续约会，后面四条，直接pass。将这八条记录作为训练集，第9条是一条新数据，作为预测，决断是否要继续约会呢？
对数据进行一些处理，将其中的离散变量（类别变量）进行替换，保存成csv格式如下表。1表示有，0表示无，目标值的-1表示没有意义，待预测。对于属性“工作”列，使用字典：{'IT': 0, 'bank': 1, 'fact':2}进行映射。
height,house,car,handsome,job,is_date
1.80,1,0,6.5,2,1
1.62,1,0,5.5,0,1
1.71,0,1,8.5,1,1
1.58,1,1,6.3,1,1
1.68,0,1,5.1,0,0
1.63,1,0,5.3,1,0
1.78,0,0,4.5,0,0
1.64,0,0,7.8,2,0
1.65,0,1,6.6,0,-1
01 scikit-learn模拟
程序员喜欢用代码说话，喜欢用代码模拟，那么在scikit-learn中，如何模拟人类的决策过程呢？
# sklearn_dt.py
import pandas as pd
from sklearn.tree import DecisionTreeClassifier,export_graphviz
df = pd.read_csv('sklearn_data.csv')
train,test = df.query("is_date != -1"), df.query("is_date == -1")
y_train, X_train = train['is_date'],train.drop(['is_date'], axis=1)
X_test = test.drop(['is_date'], axis=1)
model = DecisionTreeClassifier(criterion='gini')
model.fit(X_train, y_train)
print model.predict(X_test)
上面代码，使用pandas加载数据集，然后选择出训练集与测试集，倒数第三行构建了一个决策树模型，全部使用默认参数，最后对测试数据进行预测。
需要注意一个参数，criterion='gini'，这是决策树构建的核心算法，参数“gini”指示了程序使用基尼不纯度来进行构建决策树。对于分类问题，scikit-learn还支持使用参数值为"entropy"，表示使用熵的信息增益来构建决策树。对于回归问题，scikit-learn使用mse(均方误差)来构建。
多次运行上面的程序，程序会在某些时刻输出0，某些时间输出1。
02 信息增益，基尼不纯度
上面虽然只是用一行代码便构建了一个决策树，但实际上这一行代码后面，做了很多事情，也就是决策树构建的过程。
由前面的图片可以看出，决策树是一颗二叉树，左右两个分支，中间一个条件判断，条件满足走左分支，条件不满足，走右分支。一层层往下，因此可以用递归过程来构建。唯一的问题，在当前的结点，应该选择哪个条件来进行分割。
决策树的目的是构建一颗最优的二叉分割树，因此从根节点往下，每一个结点的条件选择，都是为了让树结构最简洁。换一句简单的说，就是尽量的找出能使当前数据集尽量分开的条件。
专业术语来说，是使得数据集的不纯度越来小，即纯度越来越大，使得数据尽可能的分开；不纯度也可以理解成数据集的混乱程度（熵），数据越混乱，不纯度越高，熵越大，也即不确定性越大。比如数据集里面，约会和不约会的概率都是0.5，那么表示不确定性很多，即不纯度很大，纯度很小。
我们的目的，就是找到一个条件进行分割，使得这种不确定性减小，如长相小于等于5.4的数据，一定不约，其不纯度为0，表示完全纯净了，都是不约，没有不确定性。
决策树常用的算法有ID3，C4.5，C5.0，CART，其中前面三种，都是用的熵的信息增益(率)来表示。最后一个CART（Classification And Regression Tree)，即分类回归树，Scikit-learn实现的便是这种算法，从名字知道，既能用于分类，也用于回归问题，其中分类问题可以使用基尼(Gini)不纯度和熵的信息增益，回归问题使用了方差降低(Variance Reduction，同mse的均方误差)的算法。
维基上面有各种算法的数学公式，对分类问题，都是基于各个类别的概率的简单计算。在构建树的时候，算法会尝试在当前数据集的所有特征上进行切分，找到概率计算出来的最优切分，并将当前条件做为切分点。
以上面的数据为例，使用gini不纯度进行分割，最开始数据集的不纯度为0.5（根结点的impurity=0.5)，在尝试了所有将数据切分一分为二（比如，切分按是否有房切分，长相大于7划分，长相小于5划分）的条件后，发现handsome<=5.4的划分，是最优的划分。
因此，决策树的构建过程，主要为两个步骤，一是数据二叉划分，不同的实现方法，有不同的数据划分，对离散变量，通常是按集合的方法，将数据集划分成两类，比如{'bank', 'IT', 'fact'}这个集合，通常会划分成{'bank'}, {'IT','fact'}；{'IT'},{'bank','fact'}；{'bank','IT'},{'fact'}这三个。而对于连续型数据，{3.8, 4.5, 7.8}这样的集体，则会按两个数的平均值进行划分。
数据分割完后，使用一种度量方法，来计算当前结点应该选择哪一个条件进行最优切分，选中的条件，即为当前的决策。
03 决策之树，决策过程
从上面的算法中，可以简单理解为，决策树就是找到当前最优的条件进行将数据一分为二，最优的条件即为当前的决策。
使用图表，来分析具体的决策过程，在scikit-learn程序中，添加如下代码：
export_graphviz(model.tree_,
out_file='tree.dot',
feature_names=df.columns,
max_depth=None,
# 下面几个参数，需要使用最新的scikit-learn 0.17版本才能用
class_names=["is_date:no", "is_date:yes"],
rounded=True,
filled=True,
)
对生成的决策树图片的说明：
- 第一行为决策条件（非叶子结点），比如根节点handsome<=5.4，条件为真走左边，为假走右边。
- impurity表示当前数据集的基尼不纯度
- samples表示当前数据集的样本数
- value表示当前数据集各个类别（按类别顺序从小到大排序，第0类，第1类……）的数量，如果value中的值相等，当前节点没有着色，为白色。
- class表示当前数据集中的多数类别，如果value中各个值相等，则应该是按顺序取值。
运行上面的代码，会输出一个tree.dot的文件，再使用如下的命令，可以生成一个图片(开篇图片左边部分)：
$ sudo apt-get install graphviz # 需要安装程序
$ dot -Tpng tree.dot -o tree.png
分析图片的数据，总结出决策规则如下：
- 长相小于等于5.4的，一定不约；
- 不满足前面条件，但：有房子的，一定约；
-
不满足前面条件，但：有车，约，没有车的，不约；
知识星球.jpeg
对待测数据，使用上面的规则：
- 长相大于5.4，不满足规则1，继续下一条；
- 没有房子，不满足规则2，继续下一条规则；
- 有车，符合第3条规则，约。
04 spark模拟
上面的决策过程，换成简单的程序思维来表达，就是if-else的条件判断，使用spark的实现的决策树，可以打印出来if-else的条件决策过程：
# spark_dt.py
from pprint import pprint
from pyspark import SparkContext
from pyspark.mllib.tree import DecisionTree
from pyspark.mllib.regression import LabeledPoint
sc = SparkContext()
data = sc.textFile('spark_data.csv').map(lambda x: x.split(',')).map(lambda x: (float(x[0]), int(x[1]), int(x[2]), float(x[3]), int(x[4]), int(x[5])))
train = data.filter(lambda x: x[5]!=-1).map(lambda v: LabeledPoint(v[-1], v[:-1]))
test = data.filter(lambda x: x[5]==-1)#.map(lambda v: LabeledPoint(v[-1], v[:-1]))
model = DecisionTree.trainClassifier(train,
numClasses=2,
categoricalFeaturesInfo={1:2, 2:2, 4:3},
impurity='gini',
maxDepth=5,
)
print 'The predict is:', model.predict(test).collect()
print 'The Decision tree is:', model.toDebugString()
通过上面的model.toDebugString()，打印出决策的过程，见开篇图片右边部分。
05 结尾
上面演示了两种不同的决策树实现，scikit-learn和spark，在演示数据上，输出可能会不同，因为各自的实现是有差别的。主要在于对离散变量（工作属性）的处理和数据的分割上面。
决策树还会涉及剪枝的问题，完全生成的决策树会伴随着数据的噪声导致过拟合，实际应用通常使用随机森林来防止过拟合。关于随机森林，请持续关注。
