|
转自 KPMG大数据挖掘 决策树算法是数据挖掘中一种非常常用的算法，它不仅可以直接对个体进行分类，还可以预测出每个观测属于某一类别的可能性，因变量可以是二分变量，也可以有多种取值，因此该方法兼备了判别分析、二元logistic模型和多元logistic模型的功能。 由于这些特点，决策树算法还常被用作基分类器来进行集成学习，比如随机森林算法就是基于CART构建起来的。决策树也可根据节点分裂规则不同而进行细分，比如CART、ID3和C4.5等。 首先，对应用比较广泛的CART算法中的代价复杂度剪枝进行理论探讨 1. 为什么要剪枝？ CART（classification and regression trees）实际上包括了两部分的内容，第一部分涉及因变量是离散变量的分类模型，也就是所谓的分类树；第二部分涉及了因变量是连续变量的回归模型，即回归树。但第二部分内容在实际数据挖掘项目中应用的比较少，因此这里我们只介绍分类树的剪枝算法。 决策树建模属于有监督算法，因变量属于离散变量，而自变量可以是连续变量或离散变量。一般来讲，只要决策树充分地生长，就可以将训练样本中的所有个体进行完美的分类，即每个终节点里面个体的因变量取值都是一样的。但是我们都知道，现实世界中的数据总会存在不同程度的噪音，比如数据的错误、偶然以及冗余信息等，如果让模型完美拟合训练数据，实际应用时我们会受到噪音的误导。因为这些噪音并不是真实的规律，将模型应用于验证数据时，模型的精度会出现大幅度的下降，即所谓的过拟合现象（overfitting）。 过拟合是很多机器学习算法中都必须考虑的问题，举一个例子，读中学的时候迫于考试压力，有的同学采取题海战术，甚至把题目背下来，但是一到考试，他就考得很差，因为考试时出现的题目与平时相比肯定经过了一些变化，他非常复杂地记住了每道题的做法，但却没有提炼出通用的、规律性的东西。相反，背英语作文框架的同学往往会取得较高的分数，因为这些框架是通用的，是规律性的东西。我们训练决策树模型也是一个道理，不需要让模型“记住”太细节的东西，更希望它能“记住”那些规律性的东西。 解决这种问题的一个思路，就是先让决策树自由地生长，使之对训练样本有非常完美的拟合，然后再利用规则剪掉部分枝叶，达到精简决策树的目的；代价复杂度剪枝就是这种思路。下面我们来介绍这种算法的基本原理。 2. 成本复杂测量度的定义 我们不妨用Tmax来代表一颗充分生长的决策树，而T代表它的子树（subtree），用表示该子树中叶子节点个数，即为树T的复杂度。α≥0表示复杂参数，R(T)是T的误判成本。Rα(T)表示在复杂参数为α时T的成本复杂测量度： 从公式可以看出，Rα(T)实际是误判成本与复杂参数的线性组合。当决策树自由生长的时候，误判成本R(T)可以降的很低，但是因为树“枝繁叶茂”，此时会比较大，片面追求误判成本最小化必然产生过大的决策树。复杂参数α可以视为每多一个叶子节点而带来的复杂成本，Rα(T)实际上是在原来误判成本的基础上增加了惩罚因子 对于每一个α，我们都可以找到使得Ra(T)达到最小的子树T(α)。当α很小的时候，每一个叶子结点带来的复杂成本也较小，这样为了追求Rα(T)最小化，子树T(α)往往会比较“茂盛”，但是随着α的增大，惩罚因子 3. 子树序列的生成 1）子树T1的生成 子树序列生成的起点是T1。由于理论上可以证明，对于任意非叶子节点t与其子树tL和tR之间存在关系：R(t)≥R(tL)+R(tR)。即：t节点的误判成本不会小于两个子树的误判成本之和。如果R(t)=R(tL)+R(tR)，不分裂t节点，决策树会更加简洁，因此可以剪掉子树tL和tR。将Tmax所有满足该条件的枝干都剪掉，就得到子树T1。需要注意的是，子树T1的生成是根据误判成本来的，与成本复杂测量度无关。 2）其他子树的生成 剪枝实际上是在非叶子节点t和以t为根结点的子树之间进行选择。对于t本身而言，其成本复杂测量度： 而以t为根结点的子树的成本复杂测量度： 如果Rα(T)与Rα(Tt)相等，基于简洁性的原因，t的枝干应该被剪掉，显然此时： 理论上来讲， 至此，我们就得到了子树序列T1>T2>…>{t1}，这种方法从T1开始剪枝，初始时往往会剪掉叶子节点较多的枝干，但是随着树越来越小，被剪掉枝干的叶子节点会越来越少。不过，究竟取哪一个子树作为最终的模型，还需要利用验证数据集来进行选择。 实际项目中，我们主要运用独立样本法或交叉验证的方法来进行选择，下面我们讨论如何根据验证数据找出最终的决策树，也就是确定最适合训练数据集合的复杂度α。 为了找出最佳子树，首先确定选择标准，并引入一些规则定义。 1. 规则定义 1）预测概率Q(i|j)：表示某个观测的因变量为j，模型将其判别为i的概率。如果模型能够完美识别，那么Q(j|j)=1；Q(i|j)=0(当i≠j时)。 2）类别的误判成本R(j)：用c(i|j)表示将属于j的个体判别为i的误判成本，很明显，c(i|i=0)。类别的误判成本为： 它表示类别为j的观测的平均误判成本。这个指标我们在上一期中也有所涉及，只是当时为了叙述的连贯性而没有明确加以定义。 3）模型的误判成本：用p(j)表示类别j的先验概率，整个模型的误判成本为： 下面我们会利用这里定义的规则，基于两种不同的思路来进行最佳子树的选择。 2. 独立样本验证法 不妨假设我们的训练集为L，将L拆分为两个独立样本L1和L2，其中L2的样本量为N2，根据上一期介绍的思路，利用L1得到子树序列{Tk}。然后利用每一个子树去预测L2中的类别，由于L2中的因变量是已知的，Tk的误判成本Rts(Tk)是可以计算出来的。以Nj2表示L2中j类别的观测个数；对于{Tk}中的任意子树，Nij2表示Tk将类别为j的观测判别为i类别的个数，据此可以得到预测概率：
根据上文的介绍，可知类别的误判成本：
对于给定的先验概率p(j)，得到子树的误判成本：
对于子树序列{Tk}中的每一个子树，都可以计算出Rts(T)，挑出使得Rts(T)最小的子树作为最佳子树Tk0：
3. 交叉验证法 如果训练集L足够大，独立样本验证法是不错的选择。但是很多情况下，L规模有限，这时就可以考虑使用交叉验证法。在v重交叉验证中，原始训练集L被随机分为v个子集Lp，p=1,2,…,v，每个子集中的观测个数相同。那么第p个训练样本为： 对于每一个固定的α，用T(α)和表示对应于Tmax和
这里Nij表示在测试时，属于j类别的观测被预测为i类别的个数。需要指出的是，由于每个在L中的观测在v个测试集Lp出现且只出现一次，因此在v个测试样本中j类别的观测个数之和刚好等于L中j类别观测个数。接下来的步骤类似于独立样本验证法，计算出预测概率:
然后得到类别的误判成本：
对于给定的先验概率p(j)，得到误判成本：
需要注意，这里表示的是T(α)的误判成本。从上一期我们知道，子树序列{Tk}对应了各自的复杂参数{αk}，先利用{αk}生成一个新的序列{α'k}:
子树Tk的误判成本：
挑出使得
在实际操作中，v常取5或者10，分别称之为5重交叉验证或者10重交叉验证，显然v越大，计算需要的时间也就越长。 4. 结语 从思路上来讲，这两种方法都是通过训练模型和剪枝采用不一样的数据的方法来避免过拟合的，区别在于对原有样本的利用方法，交叉迭代法更加充分地利用了原有数据信息。当样本量不是很大的时候，我们建议采用交叉迭代的方法，既能够充分利用原有信息，训练模型的时间成本也不至于太高。当样本足够大时，可以考虑直接利用独立样本验证。从应用来看，目前sas软件和R语言的rpart包都可以利用CART算法建立决策树模型，深层次地理解算法可以正确地设置相应的参数，避免模型的误用和滥用，取得最佳的建模效果。 久其智通数据(9zdata)定位于“媒体与营销大数据服务提供商”，致力于为媒体和互联网营销企业提供优质、全方位的定制化和SaaS化的技术平台服务方案。 久其智通数据落于北京中关村软件园区，是上市公司久其软件(sz.002279)控股子公司,目前已在大数据业务模块化基础应用平台、画像工厂、用户行为实时分析与个性化推荐、品牌营销效果监测、流量变现和媒体出海等方面，积累了丰富的产品经验。 |
|
|
