一、应用背景
当在生活上决定“今天出门要不要带伞”，当在工作上需要分析“这个用户会不会流失”等诸如此类的问题，实际上我们就是在做决策。一般决策我们会这样思考“如果条件是这样这样, 那么我就选择A; 如果条件是那样那样, 那么我就选择B”。这样的思考过程，就与决策树算法的过程相类似。
二、决策树概述
决策树是一种分而治之，不断分类细化的决策过程。一个困难的预测问题, 通过树的分支节点, 被划分成两个或多个子集。并将依规则分割子集的过程不断递归下去。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则时, 该分支节点会停止细分，此为自上而下的停止阈值法，而有些决策树也使用自下而上的剪枝法来实现细分的终止。
三、基础概念
（1）不纯度函数
决策树最重要的概念就是不纯度函数。 当对节点进行分割的时候，实际上就是找到一个合适的特征，以及特征的一个合适的取值作为阈值来进行分割。
那么怎么确定那个是合适的特征？特征的那个取值又是合适的呢? 主要的依据就是不纯度的变化。首先我们给出不纯度函数的定义. 不纯度函数不是一个具体的函数，它是满足一系列约束的函数的总称。不纯度函数(I)的定义为：
如上公式可以看出不纯度函数的定义域是长度为k的向量，向量每个数的取值为0~1，且加和为1。第i个数是特征矩阵中属于类别i的特征向量个数在整个样本个数(n_sample)的占比。 每一项其实就是属于类目c_i的概率，记为p_i。且必须满足如下约束：
- 当所有样本都属于同一类时I取最小值
- 当样本中每个类目下样本个数相同时I取最大值
- I对于定义域中每个取值p_1,...,p_k是对称的. 即I(p_1, p_2,...,p_k) = I(p_2,p_1,..,p_k)等
- I必须是绝度凸函数(strickly concave)即设p和p'(注意这里是一个长度为k的向量)为定义域下两个可能的取值
（2）不纯度变化
每个父节点的两个子节点的划分，要进行定量评价，于是引入了不纯度变化的概念。设X1,X2...Xs是特征空间X的一个划分， 不纯度变化定义为：
这个公式很好理解，令s=2, 那么 X_1,X_2是对于原空间的一个划分。一个好的划分应该让不纯度变低, 以便让类目归属更加清晰。 公式后面一个累加和实际上就是这两个划分的不纯度的期望。原不纯度减去划分后的不纯度的期望就是减少的不纯度的差值。这个差值越大说明划分让子节点的纯度更高。
分类决策树节点划分的依据是找到一个特征的一个取值, 根据这个划分是的不纯度缩减量最大。
（3）不纯度函数1：信息熵
首先介绍一下信息熵的概念， 我们把样本抽取过程当做一次随机试验A, 那么A有k个可能的输出A_1,A_2,...,A_k . 对应于k个分类。 那么A的信息熵定义为：
信息熵满足不纯度函数的定义，所以：
从上述不纯度函数的定义得到相应的不纯度变化函数：
当不纯度函数为信息熵时不纯度变化又叫做信息增益。
（4）不纯度函数2：基尼指数
基于基尼指数的不纯度函数：
不纯度变化函数：
不管是信息熵还是基尼指数，都是不纯度函数的一种形式。实际上我们也可以自行设计不纯度函数。
如果把信息熵和基尼指数图形画出来，发现他们的差别其实不大。
四、SPSS构建信用卡违约决策树
通过决策树构建违约情况的分类模型，用于预测用户是否违约。
（1）示例数据
原始数据分别记录了每个用户的年龄、学历、工作、收入、债务、违约情况等特征。
（2）构建SPSS模型流
拖入不同类型的节点，构建SPSS模型流
银行信贷.sav节点：输入数据
类型、选择节点：整理数据、过滤异常数据
分区节点：根据分区字段，对每个类分别建模。
违约情况节点：使用C5.0算法构建决策树
（3）运行结果
五、决策树的局限性
决策树的主要问题是容易形成过拟合. 如果我们通过各种剪枝和条件限制, 虽然可以避免过拟合, 但是会牺牲特征的有效性。
例如样本有1w个测试记录，属性的数量是1k个，为了保证模型的有效性, 规定每个叶子节点包含的最少样本数为100。在构造决策树的过程中我们可以断言节点个数不会超过100个, 这样很多属性不仅没有多次分裂, 甚至有些特征根本无法参与决策。