SLIQ：高速、可伸缩的基于决策树分类算法

SLIQ算法是一种决策树分类器，它采用预排序技术，解决了当训练集数据量巨大、无法全部放入内存时，如何高速准确生成决策树的问题，并能同时处理离散和连续属性。

例5.6：表5-6为样本集，每个样本具有两个非类别属性（age， salary）和一个类别属性（class），该类别属性具有两个值（G， B）。

表5-6　SLIQ算法示例5.6样本集

1） Gini指标（Gini index）

ID3和C4.5算法构造的决策树过程中，使用信息量作为评价节点分割质量的参数，SLIQ算法使用Gini指标代替信息量。

定义5.13（数据集S的Gini指标，Gini index）：若数据样本集S含有来自m个类的样本，Pj是S中第j类数据的相对频率，则数据集S的Gini指标定义为：

容易看出，Gini指标越小，信息增益量越大，节点分割质量越好。

当将S分裂为两个子集S1和S2时，基尼指数计算方法如式5-9所示：

其中，n为数据样本集S中的总样本数，n1为S1中所含的样本数，n2为S2中所含的样本数。

从Gini指数的计算可以看出，其优点是只需知道每种分割的类分布数。下面给一个例子说明Gini指标的计算方法：

例5.7：对图5-1a中的训练样本按年龄升序排序结果见表5-7，计算Ginisplit（27.5）、Ginisplit（ 18.5）和Ginisplit（ 37.5） 。

表5-7　排序结果

同理：

Ginisplit（18.5） = 0.4 　　　 Giniplit（37.5） = 0.417

2）属性的分割方法

SLIQ算法构造决策树时，先对每个节点计算最佳分割策略，然后执行分割。

（1）对于数值型连续属性分裂形式为A＜=v：先对数值型属性排序，假设排序后的结果为v1， v2，…， ，因为分割只会发生在两个节点之间，所以分割点有n—1种可能性，通常取中点（vi+vi+1）/2作为分割值，然后从小到大依次取不同的分割点，取信息增益指标最大（Gini最小）的一个作为分割点。

这个方法中，需要对每个节点进行排序，所以操作的代价极大，于是降低排序成本成为一个重要的问题，为解决这个问题，SLIQ算法对数值型属性采用预排序策略，即在树生长阶段的开始对每个数值型属性排序一次，而不需要在决策树的每个节点都进行排序，关于预排序的数据结构和方法下面会有更详细的介绍。

（2）对于离散型属性：设V（A）为A的所有可能的值，分裂测试将要取遍V的所有子集V′。寻找当分裂成V′和V—V′两部分时的Gini指标，取到Gini最小的时候，就是最佳分裂方法。这是一个对集合V的所有子集进行遍历的过程，代价将是很大的。算法采用贪心算法对此进行优化：从空子集V′开始，再向V′中加入能得到最佳分裂的V中的元素，重复执行这个过程，直到分裂值没有变化停止。需要注意的是，当该离散属性所有可能值的个数不超过一定阈值（一般取10）时，可以直接计算，不需要贪心算法。

3）数据结构

SLIQ在树的构建阶段使用预排序（pre-sorting）技术以减少计算数值型连续属性的代价。实现预排序需要的主要数据结构包括：属性表（attribute list）、类表（class list）以及树节点。

定义5.14（属性表）：对训练数据的每个属性生成一个单独的表（list），称为属性表。属性表有两个字段：属性值和指向类表的索引。

例如：

定义5.15（类表）：类表有两个字段：类标号及决策树叶节点的指针。类表中的第i个值对应训练数据中的第i个样本。决策树中的每一个叶节点代表训练数据中的一个划分。该划分依赖于从节点到根的路径。类表在任何时间都可以找到样本所属的划分。

例如：

仅有一张类表，必需常驻内存。属性表在必要时可写回磁盘。

4）数据初始化

算法的输入是训练样本集。训练集输入之后，分成一个一个的属性表。

所有类标识存入类表，类表中的leaf字段指向该记录对应的决策树的叶子，初始状态下，所有记录指向树根。

对属性表进行内部排序，交换属性值vi，同时交换i，生成有序的属性表序列，这是SLIQ算法中对属性进行的唯一一次排序。

排序完成后，属性表中的i是属性值指向类表的指针，如图5-8所示。

图5-8　预排序示例初始时根结点为N1

5）计算最佳分裂

最佳分裂指标计算阶段将通过一次对所有属性表的遍历，找出所有叶节点的最佳分裂方案。算法如图5-9所示。

计算最佳分裂阶段有一个重要的结构：类直方图（class histogram）。它位于决策树的每个顶点内，存放每个节点当前的类信息——左、右子树的每个类各拥有多少节点。图5-10中，L值表示满足测试的样本分布，R表示不满足测试的样本分布。

（1）当前属性A是数值型时，每次作遍历时，类直方图亦随之改变，随时记录以当前属性A的当前值v为阈值的节点分裂方式对叶节点L的分裂状况。由类直方图即可算出某个分裂方案的Gini index。完成对A的遍历后，Gini index最低的（信息增益最高的）A的值就是用属性A分裂的最佳阈值。新方案存入决策树节点。

（2）当前属性A是离散型时，在遍历过程中，记录每个属性值对应的类的个数。遍历完成后，得到信息增益最高的A的子集，即为所求的用A的分裂方案。新方案存入决策树节点。

图5-9　计算最佳分裂的算法

对整个属性表的每个属性进行一次完全的遍历之后，对每个节点而言，已经得到它的最佳分裂方案，包括用哪个属性进行分类以及分类的阈值是什么，并且存放在决策树的节点内。

图5-10是一个计算最佳分裂方案的例子。

图5-10　计算分裂指标的例子

假设之前已经使用分割点age ≤ 35处理了属性“age”，当前待分裂属性为“salary”。右边为类直方图的变化过程。salary属性表从上往下扫描，这时，叶子队列里面的节点有N2、 N3。属性表中的第一个值属于节点N2，因此第一个分裂计算是对N2节点的分裂（salary≤1 041），分裂之后，相应的样本（salary 1041，类指针为9）满足左边分支，其余的属于右分支，于是N2的类直方图被更新。接下来，计算对N3节点的分裂（salary ≤7 182），分裂之后，相应的样本（salary 7182，类指针为1）属于左分支，N3的类直方图被更新。

6）更新类表(www.xing528.com)

当最佳分裂参数已经存放在节点中之后，算法（图5-11）的下一步是为每个叶节点创建子节点、更新类表（执行节点分裂）。

图5-11　执行分裂某个叶节点的算法

如图5-12表示在salary属性上分割N2和N3后被更新的类表。遍历salary属性表，对应salary的值为7182的类表（指针为1）位置被更新。首先，类表位置为1的叶指针用于找到样本应该属于的节点（现在为节点N3），然后，在节点N3被选择的分裂用于发现样本应该所属的新的子节点（节点N6），为反映这个变化，在类表中位置1的N3被更新为N6。最后，节点N3分裂成N6、 N7， N3转为内部节点。

7）终止条件

在树的构造过程中，重复执行最佳分裂计算和类表更新两个步骤，直到每个叶节点成为纯节点（即包含仅属于一个类的样本）且不需要更多分裂结束。

8）剪枝

SLIQ的剪枝算法MDL属于后剪枝方法，它的目标是生成一棵描述长度最小的决策树。

由于训练数据中的“噪声”影响而造成的错误的分支将导致利用模型时的分类错误。剪枝就是去除那些导致错误的分支，在可能的子树中挑选错误率最小的子树。

决策树中应用最小描述长度准则的MDL［5］修剪算法对树进行剪枝，该方法根据编码所需的二进位位数，而不是根据期望错误率，并且不需要独立的样本集。

对同样的数据可以采用不同的模型，最小描述长度MDL给出了一种选择模型的依据。MDL基本思想是找出一个模型，使得模型的算法复杂度与该模型相适应的训练数据的描述长度的和最小，即对数据编码的最好模型是使依据模型描述数据代价的总和最小及描述模型的代价最小。MDL倾向于选择最简单的模型。

图5-12　更新类表

如果模型M对数据D编码的一个模型，那么编码的总代价cost（M， D）定义为：

cost（M， D） = cost（D | M）+cost（M）

其中，cost（D | M）代价表示给定模型M后对数据编码的比特数；cost（M）表示描述模型本身所需的编码代价。在决策树方法中，模型是指剪枝初始决策树时得到的一系列子树。

MDL修剪算法目标是寻求一种合理且较小的树，使得训练样本的大多数数据符合这棵树，把样本中不符合的数据作为例外编码，使得下面两项最小：编码决策树（不一定是完全正确的）所需的比特；编码样本空间中与决策树不符的实例所需要的比特。即生成一棵描述长度最小的决策树。

MDL修剪算法分为两部分：编码模式判断对数据编码及对模型编码的代价。

（1）数据编码。如果由决策树产生的分类与样本原来的类标号不一致，则此样本的分类是错误的。由决策树对训练集编码的代价定义为所有分类错误个数之和。分类错误的计算是在树构建阶段完成的，因此数据编码代价并不高。

（2）模型编码。对模型编码的代价包括描述树本身的代价与描述用于树中每一个内部节点测试的代价。

①树编码。给定一个决策树，对树的编码的比特数依赖于树结构。有以下三种方案：

a.code1：一个节点或者没有子节点，或者有两个子节点。共有两种可能性，只需使用一位比特对每一个节点编码。

b.code2：每一个节点没有子节点、一个左子节点、一个右子节点或两个子节点四种情况，需两位比特对四种情况编码。

c.code3：只需编码内部节点，此时节点可能有一个左子节点、一个右子节点或两个子节点。需log2 3位比特。

②分支编码。对分支的编码依赖于对分支测试的属性类型：

a.连续属性：若形如A ≤ v的分支，v是一个实数，对这个测试的编码的代价只是对v编码的最大值，比如是P。虽然P的值可以在决策树中对每一个这种测试进行判断，但一般的仍给出由经验值决定的值l。

b.离散属性：对形如A∈S，S是A的所有可能子集，需计算的代价分为两部分，一部分是用于树中这种测试的数量，即每个属性Ai其数量为n Ai；另一部分按lnnAi计算的代价。

Ltest记为在内部节点上的任意测试的编码代价。

MDL修剪算法对决策树的每一个节点的代码长度进行计算以判断是否将节点转变为叶节点、修剪左子节点、修剪右子节点或保持节点不动。

对于上述任何选择，一个节点t的代码长度C（t）的计算方法如下：

C′（ti）代表对使用父节点统计数编码子节点的代价，其他数值自设定。在部分剪枝情况下，修剪t1或t2时，落入已剪枝树枝的样本用父节点的统计数编码。

剪枝策略共有三种：

（1）完全剪枝（full）：只考虑式5-10和式5-11的情况，对一个节点t如果Cleaf（t）计算代价比Cboth（t）小，则将这两个子节点修剪，并将该节点变为叶节点，树的编码代价就只用一个比特（code1 ）。

（2）部分剪枝（partial）：考虑四种情况，比较四种计算代价的大小，选择代价最小的作为修剪的方法。树的编码代价需要两个比特（code2 ）。

（3）混合剪枝（hybrid）：修剪树包含两个阶段，第一步先用完全剪枝策略得到一个比较小的树，然后再考虑式5-11、式5-12、式5-13后三种计算方式来修剪树。

经过对三种策略算法比较实验证明，部分剪枝策略将生成更小的决策树，但分类准确率相对较低；混合剪枝策略具有与完全剪枝相同的准确率，同时生成的决策树平均较小，因此一般认为混合剪枝是较好的策略。

9） SLIQ算法总流程

图5-13　SLIQ算法总流程

算法的控制结构是一个队列，该队列存放当前的所有叶节点，是为了控制广度优先搜索的结束。当队列空时，说明所有的叶节点都已被处理过，这时建树算法结束。第10步是利用MDL算法进行裁剪。

需要说明的是，这里给的终止条件是当叶子节点为纯节点时，在实际应用中，可以考虑前面提到的三种终止条件，如没有继续可用的属性（这需要在SLIQ算法中进行调整，如ID3中，曾使用的属性去除，此时可用多数投票方法决定类，但是这样可能会带来较大的错误率，需要权衡）。

10）其他问题

当某叶子是纯节点时，它将停止分裂。以后，这些节点将不参与运算。所以，这时可以将属性表中叶节点包含的记录全部删去。这样可以压缩属性表规模，降低换入换出磁盘时的I/O负荷。

11） SLIQ算法的优点

（1）运算速度快，对属性值只作一次排序。

（2）利用整个训练集的所有数据，不做取样处理，不丧失精确度。

（3）轻松处理磁盘常驻的大型训练集，适合处理数据仓库的海量历史数据。

（4）更快的，更小的目标树。

（5）低代价的MDL剪枝算法。