作者：王佳鑫审校：陈之炎
本文约4800字，建议阅读15分钟本文带你了解决策树是如何工作的。决策树的基础概念
决策树(Decision Tree)是一种非参数的有监督学习方法，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。决策树算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各种集成算法，在各个行业和领域都有广泛的应用。我们来简单了解一下决策树是如何工作的。
决策树算法的本质是一种图结构，只需要问一系列问题就可以对数据进行分类了。如图1所示决策树算法算出了下面的这棵决策树：
图1 决策树算法示例
可以看出，在这个决策过程中，我们一直在对记录的特征进行提问。最初的问题所在的地方叫做根节点，在得到结论前的每一个问题都是中间节点，而得到的每一个结论都叫做叶子节点。
决策树算法的核心是要解决两个问题：
（1）如何从数据表中找出最佳节点和最佳分枝？（即怎么构造决策树）
（2）如何让决策树停止生长，防止过拟合？（即如何剪枝）
几乎所有决策树有关的模型调整方法，都围绕这两个问题展开。
1.构造原理——如何构造一棵决策树？
为了要将表格转化为一棵树，决策树需要找出最佳节点和最佳的分枝方法，对分类树来说，衡量这个“最佳”的指标叫做“不纯度”。通常来说，不纯度越低，决策树对训练集的拟合越好。现在使用的决策树算法在分枝方法上的核心大多是围绕在对某个不纯度相关指标的最优化上。
不纯度基于节点来计算，树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的，也就是说，在同一棵决策树上，叶子节点的不纯度一定是最低的。
构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在以下几种节点：
这里，先介绍信息熵的概念。
在构造决策树的时候，会基于纯度来构建。而经典的“不纯度”的指标有三种，分别是信息增益（ID3算法）、信息增益率（C4.5算法）以及基尼指数（Cart算法）。这里我们只介绍常用的信息增益算法。
1)信息增益（ID3算法）
信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。所以信息增益的公式可以表示为：
其中是父亲节点，是子节点，中的作为节点的属性选择。
ID3的算法规则相对简单，可解释性强。同样也存在缺陷，比如我们会发现ID3算法倾向于选择取值比较多的属性。这种缺陷不是每次都会发生，只是存在一定的概率。在大部分情况下，ID3 都能生成不错的决策树分类。针对可能发生的缺陷，后人提出了新的算法进行改进。
例题：请对以下数据建立决策树进行分析，判断一个案例“下雨、热、湿度、正常、弱风“，是否可以打网球？
表1 建立决策树分析数据表
该数据集包含7个训练样本，其中正例占4/7，其中反例占3/7，计算得到根结点的信息熵为
(1)属性“Outlook”，其对应的3个数据子集分别为
D1(Outlook=Sunny), D2(Outlook=Rain), D3(Outlook=Overcast)
子集D1有2个样例，其中正例占0，反例占1，D2、D3同理，
子集D2有3个样例，其中正例占2/3，反例占1/3，
子集D3有2个样例，其中正例占1，反例占0。
3个结点的信息熵为：
则属性“Outlook”的信息增益为
(2)属性“Temperature”，其对应的3个数据子集分别为
D1(Temperature=Hot), D2(Temperature=Mild), D3(Temperature=Cool)
子集D1有3个样例，其中正例占1/3，反例占2/3，D2、D3同理，
子集D2有1个样例，其中正例占1，反例占0，
子集D3有3个样例，其中正例占2/3，反例占1/3。
3个结点的信息熵为：
则属性“Temperature”的信息增益为
(3)属性“Humidity”，其对应的2个数据子集分别为：
D1(Humidity=High), D2(Humidity=Normal)
子集D1有4个样例，其中正例占1/2，反例占1/2，D2、D3同理，
子集D2有3个样例，其中正例占2/3，反例占1/3。
2个结点的信息熵为：
则属性“Humidity”的信息增益为
(4)属性“Wind”，其对应的2个数据子集分别为
D1(Wind=Strong), D2(Wind=Weak)
子集D1有3个样例，其中正例占1/3，反例占2/3，D2、D3同理，
子集D2有4个样例，其中正例占3/4，反例占1/4。
2个结点的信息熵为：
则属性“Wind”的信息增益为
显然，属性Outlook的信息增益最大，其被选为划分属性。
2)信息熵的属性
由于Sunny全纯，Overcast全纯，但Rain有Yes也有No。
该数据集包含3个训练样本，其中正例占，其中反例占，计算得到根结点的信息熵为
(1)属性“Temperature”，其对应的3个数据子集分别为
D1(Temperature=Hot), D2(Temperature=Mild), D3(Temperature=Cool)
子集D1有0个样例，其中正例占0，反例占0，D2、D3同理，
子集D2有1个样例，其中正例占1，反例占0，
子集D3有2个样例，其中正例占1/2，反例占1/2。
3个结点的信息熵为：
则属性“Temperature”的信息增益为
(2)属性“Humidity”，其对应的2个数据子集分别为：
D1(Humidity=High), D2(Humidity=Normal)
子集D1有1个样例，其中正例占1，反例占0，D2、D3同理，
子集D2有2个样例，其中正例占1/2，反例占1/2。
2个结点的信息熵为：
则属性“Humidity”的信息增益为
(3)属性“Wind”，其对应的2个数据子集分别为：
D1(Wind=Strong), D2(Wind=Weak)
子集D1有1个样例，其中正例占0，反例占1，D2、D3同理，
子集D2有2个样例，其中正例占1，反例占0。
2个结点的信息熵为：
则属性“Wind”的信息增益为
显然，属性wind的信息增益最大，其被选为下层划分属性。
但由于strong纯为No，weak纯为Yes
因此分支结束。
最终得到的决策树如图2所示：
图2 决策树
因此，一个案例“下雨、热、湿度、正常、弱风“，可以打网球。
2.剪枝原理——如何剪枝？
剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
剪枝的两种方法：
1)预剪枝
在决策树构造时就进行剪枝。方法是，在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。
2)后剪枝
在生成决策树之后再进行剪枝。通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。方法是：用这个节点子树的叶子节点来替代该节点，类标记为这个节点子树中最频繁的那个类。
3.决策树的优点
（1）易于理解和解释，因为树木可以画出来被看见。
（2）需要很少的数据准备。其他很多算法通常都需要数据规范化，需要创建虚拟变量并删除空值等。
（3）使用树的成本(比如说，在预测数据的时候)是用于训练树的数据点的数量的对数，相比于其他算法，这是一个很低的成本。
（4）能够同时处理数字和分类数据，既可以做回归又可以做分类。其他技术通常专门用于分析仅具有一种变量类型的数据集。
（5）能够处理多输出问题，即含有多个标签的问题，注意与一个标签中含有多种标签分类的问题区别开。
（6）是一个白盒模型，结果很容易能够被解释。如果在模型中可以观察到给定的情况，则可以通过布尔逻辑轻松解释条件。相反，在黑盒模型中(例如，在人工神经网络中)，结果可能更难以解释。
（7）可以使用统计测试验证模型，这让我们可以考虑模型的可靠性。
（8）即使其假设在某种程度上违反了生成数据的真实模型，也能够表现良好。
4.决策树的缺点
（1）决策树学习者可能创建过于复杂的树，这些树不能很好地推广数据。这称为过度拟合。修剪，设置叶节点所需的最小样本数或设置树的最大深度等机制是避免此问题所必需的，而这些参数的整合和调整对初学者来说会比较晦涩。
（2）决策树可能不稳定，数据中微小的变化可能导致生成完全不同的树，这个问题需要通过集成算法来解决。
（3）决策树的学习是基于贪婪算法，它靠优化局部最优(每个节点的最优)来试图达到整体的最优，但这种做法不能保证返回全局最优决策树。这个问题也可以由集成算法来解决，在随机森林中，特征和样本会在分枝过程中被随机采样。
（4）有些概念很难学习，因为决策树不容易表达它们，例如XOR，奇偶校验或多路复用器问题。
（5）如果标签中的某些类占主导地位，决策树学习者会创建偏向主导类的树。因此，建议在拟合决策树之前平衡数据集。
5.决策树在金融领域的应用
比特币匿名性的特征为非法活动的发展提供了有利的工具。洗钱、勒索、恐怖融资等非法交易隐匿于正常交易之中，难以发觉。现今未有研究对恐怖融资相关交易进行预测。关于反洗钱的预备知识梳理，我们比特币恐怖融资的交易行为特点有了初步的了解，恐怖融资的招募地址多为临时中转地址，转移资金方面收到一笔资金就转移一笔，在融资来源与流向实体上，大部分实体为未知匿名实体，且存在一些发生过滥用行为的交易所和服务商实体，说明非法活动之间是存在关联的，恐怖组织会易于采用已知的滥用实体进行资金的转移，交易模式多表现为资金的分散与汇聚，符合洗钱的理念。由第二章相关研究分析可知，现并未有研究涉及比特币恐怖融资交易预测，恐怖组织创建并利用比特币地址进行融资活动，行为特征将会从地址的交易数据中表现出来，对恐怖融资地址预测在理论和现实监管上都有重要意义。本章节参照以往非法交易识别文献分析以及当前融资交易行为的分析，选取了交易强度特征、交易频度特征这两个基础交易特征，并进一步添加关联地址特征，获取关联地址的实体标签数据用于恐怖融资地址预测。
我们从Kaggle上选取了区块链情报公司Elliptic公开发布的比特币交易网络数据集。其中在这些交易数据中，节点表示比特币交易中的实体，边表示比特币交易实体间的交易关系和方式，该交易网络数据集一共分为三个数据表，如下表2所示各个表的数据说明。
表2 三张数据表的说明
基于已经处理好的交易多维特征数据，我们构建了有监督学习的比特币交易实体分类模型。我们筛选掉了原始数据集中标签为“unknown”的交易实体数据，对剩余的交易实体节点进行建模和训练。交易实体的166个特征分为两部分，其中前94个交易基础特征是从“feat0”到“feat93”来命名，而名称为“neigh_feat0”到“neigh_feat71”是72个从交易关联实体地址信息提取的特征。
利用前94个交易基础特征构建第一个实体分类模型，同时为了验证关联节点对于其交易实体类别是否存在影响，我们把所有166个关联实体交易特征构建第二个实体分类模型。在构建模型进行训练之前，需要对数据进行处理和清洗：
（1）划分训练集和测试集
首先利用sklearn包的train_test_split()函数得到比例为7:3的训练集和测试集。
（2）样本不平衡的处理
由探索性分析结果可知，Elliptic提供的案例集中不同“class”的数据集存在较明显的样本不平衡的问题。如果这样的数据应用在class标签数量不平衡问题的模型上，那么自然而然地，模型的聚焦点会更多地放在标签数量较多的合法交易实体上，这样的结果是我们意料之外和不想得到的。
对样本不平衡问题进行处理，通过查找相关文献，我们可以通过增加稀有样本数量的方法来平衡数据集。经试验表明，我们对已经切分好的训练集数据进行过采样得到合法非法比例为1:1的总共5万多条交易数据。
由上述分析可知，将过采样之后得到的训练集用于Logistic Regressoin、MLP、Random Forest和XGBoost的建模，从而得到第一个实体分类模型stata_94构建前的数据信息如表3所示，。同理，我们进行第二个实体分类模型stata_166构建前的数据信息，如表4所示。
表3 第一个实体分类模型stata_94建立的各组数据及其维度信息
表4 第二个实体分类模型stata_166建立的各组数据及其维度信息
（3）特征筛选和标准化处理
本次特征选择采取方差过滤的方法进行特征筛选。方差过滤是一个通过特征本身的方差来过滤特征的方法。例如，如果一个特征本身的方差非常小，那就意味着这个特征在样本中基本上没有差异。也许特征中的大部分值是相同的，甚至整个特征的值是相同的，那么这个特征对样本的判别没有影响。因此，我们需要对方差为0的特征予以删除。
结论
通过实验可以发现，所有特征的方差值都大于0，为了覆盖更多的特征维度和信息，我们选择保留所有的特征。之后，需要对筛选出来的训练集特征进行标准化处理，从而让模型的效果被影响最小。
编辑：王菁
数据派研究部介绍
数据派研究部成立于2017年初，以兴趣为核心划分多个组别，各组既遵循研究部整体的知识分享和实践项目规划，又各具特色：
算法模型组：积极组队参加kaggle等比赛，原创手把手教系列文章；
调研分析组：通过专访等方式调研大数据的应用，探索数据产品之美；
系统平台组：追踪大数据&人工智能系统平台技术前沿，对话专家；
自然语言处理组：重于实践，积极参加比赛及策划各类文本分析项目；
制造业大数据组：秉工业强国之梦，产学研政结合，挖掘数据价值；
数据可视化组：将信息与艺术融合，探索数据之美，学用可视化讲故事；
网络爬虫组：爬取网络信息，配合其他各组开发创意项目。
点击文末“阅读原文”，报名数据派研究部志愿者，总有一组适合你~
转载须知
如需转载，请在开篇显著位置注明作者和出处（转自：数据派THUID：DatapiTHU），并在文章结尾放置数据派醒目二维码。有原创标识文章，请发送【文章名称-待授权公众号名称及ID】至联系邮箱，申请白名单授权并按要求编辑。
未经许可的转载以及改编者，我们将依法追究其法律责任。
点击“阅读原文”加入组织~