sliq：一种快速可扩展的分类算法

《sliq：一种快速可扩展的分类算法》由会员分享，可在线阅读，更多相关《sliq：一种快速可扩展的分类算法（53页珍藏版）》请在金锄头文库上搜索。

1、SLIQ：一种快速可扩展的分类算法,讲课人：杨震,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6

2、.具体实例。 2.2.离散属性的分支选择。 3.总结,1. SLIQ算法的扩展性,分类算法存在一个问题不能进行扩展 数据量在急剧增长，训练样本达到数百万是非常普遍的，由于内存及CPU时间的限制，原有的许多算法已经无法处理这些数据。 因此，必须寻找新的方法来解决大数据集的分类问题。,SLIQ使用如下技术提高可扩展性,用预排序技术来减少计算连续属性的代价。 利用贪心算法来确定离散属性的分支。 使用MDL算法修剪树。,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2

3、.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,最优分支的选择问题,最优分支的选择依据于分支指标，分支指标用来给属性的可选分支确定“优良程度”。 分支指标： 熵（ID3和C4.5） 最小Gini指标（CART，SLIQ和SPRINT）。,SLIQ使用Gini指标作为分支指标,定义：对数据集包含n个类的数据集S，Gini(S)定义为： Gini（S）=1-Pj2，Pj是S中第j类数据的频率。 如果一个划分将数据集D分成两个子集D1和D2。则分割后的Ginisplit是： Ginisplit=|D1|/|D|Gini(D1)+|

4、D2|/|D|Gini(D2) 提供最小Ginisplit 就被选择作为分割的标准。,可以证明，Gini越小，信息增益越大。,离散属性,Education属性最优分裂值确定,Gini(L)=1-(3/3)2=0 Gini(H)=1-(3/4)2-(1/4)2=0.38,Gini_Split(Education)=3/7*0+4/7*0.38=0.22,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.

5、6.具体实例。 2.2.离散属性的分支选择。 3.总结,连续属性的分支选择,操作： 设v是实数，采用 Av 的二叉分支的方法。第一步，与C4.5的处理方法类似，即根据将要分支的属性取值对训练样本进行排序。设属性取值排序后的结果为v1，v2，vn ，vi 和vi+1之间一般取中间点(vi +vi+1)/2作为分支点，这样需确定n-1个可能的分支。 因为每次计算都需要排序，所以这项操作的代价极大。 解决： SLIQ在树的构建阶段是用预排序技术以减少计算连续属性的代价。,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割

6、。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,SLIQ中预排序所需的数据结构,SLIQ使用若干驻留磁盘的属性表和单个驻留内存的类表。 属性表：有两个字段， 属性值， 指向类表的索引。 类表：也有两个字段， 类的标号， 决策树叶节点的指针。,预排序过程,首先，对训练数据扫描一次后，为每一个非类别属性建立一个属性表，每一个属性值都对应着相应的类表索引。 类表的所有叶指针字段都指向决策树的根节点。 连续属性的属性表独立地进行排序。,预排序举例,预排序 后,1 2 3 4 5

7、6,驻留磁盘的属性表,训练数据集,预排序后,1 2 3 4 5 6,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,计算最佳分割,最佳分割包括两个内容： 1.属性的最佳分割点， 2.最佳的分割属性。 为了计算节点中属性的分支指标Gini，在每个叶节点对应的数据划分中需使用类的频率分布。 分布通过附加在每一个叶节点上的类矩形表累计。,类矩形表,类

8、矩形表(histogram)： 位于决策树的每个节点内，存放每个节点当前的类分布信息左、右子树的每个类各拥有多少条记录。 对于连续属性，矩形表由形如的若干对组成。 对于离散属性，矩形表有形如的若干三元组组成。,如图，假设在属性age上使用分支 age35 对数据已初始化。当前待分裂属性Salary，右边为类矩形图的变化过程。属性表从上往下扫描。 1 2 3 4 5 6,N1,N2,N3,初始矩形表,B G,B G,L R,L R,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节

9、点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,选择分支属性生成子节点并更新类表,最佳分割求解出后，信息已存放在节点中，即该节点的类矩形表得到了更新，算法的下一步便是针对每一个叶节点生成子节点，同时更新类表。,类表的更新算法,Updatelables( ) for 在分支中使用的每一个属性A do 遍历A的属性表 for 属性表中的每一个值v do 找到类表中的对应位置（比如说e） 通过在从e指向的节点上进行分支测试找 到v所属的新类c 将e的类标号更新到c 更新在e中引用的节点到与类c对应的子 节点 en

10、d end,类表更新举例,N1,N2,N3,N4,N5,N6,N7,1 2 3 4 5 6,N6,Age35,Salary50,Salary40,属性表,类表,属性表,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,决策树何时结束构建,算法的控制结构是一个队列。这个队列存放当前的所有叶子节点，这是为了控制广度优先搜索的结束。当队列为空时，说明所

11、有的叶子节点都已经被处理完毕，这时建树算法可以结束。,f r,f r,结束,1.SLIQ算法的扩展性。 2.最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,SLIQ采用MDL修剪,最小描述长度( MDL) 原理: 其基本原理是对于一组给定的实例数据 D ， 如果要对其进行保存 ，为了节省存储空间， 一般采用某种模型对其进行编码压缩，然后再保存压缩后的数据。同时， 为了以后正确

12、恢复这些实例数据，将所用的模型也保存起来。所以需要保存的数据长度( 比特数) 等于这些实例数据进行编码压缩后的长度加上保存模型所需的数据长度，将该数据长度称为总描述长度。最小描述长度( MDL) 原理就是要求选择总描述长度最小的模型。,MDL( Minimum Description Length)思想： 遵循最简单的解就是最期望的。 编码的总代价为： Cost(M,D)=cost(D/M)+cost(M) 其中, cost(D/M)：给定模型M后对数据编码的比特数。 cost(M)：对模型M编码的代价。 MDL目标：就是修剪决策树以使Cost(M,D)最小。,1.SLIQ算法的扩展性。 2.

13、最优分之的选择问题。 2.1.连续属性的分支选择。 2.1.1.预排序。 2.1.2.计算最佳分割。 2.1.3.选择分支属性生成子节点并更新类表。 2.1.4.决策树结束构建。 2.1.5.MDL修剪。 2.1.6.具体实例。 2.2.离散属性的分支选择。 3.总结,具体实例,设训练样本数据集如表1所示。 表1 训练数据,（1）创建根节点N1，结果如下图所示。,N1,（2）创建并排序属性表，创建类表，结果如图所示。,1 2 3 4 5 6,属性表,属性表,类表,预排序,Age List,Class List,Salary List,（3）创建空队列quene,并将N1入队，如图所示。,f r

14、,(4) 队列quene的队头元素出队，即N1出队。,（5）计算刚出队元素N1所对应节点的ginisplit： 计算Age的ginisplit。将Age的属性表调入内存，由该属性表及类表可知，属性Age对应节点N1的取值有：23、30、40、45、55。分别计算ginisplit（ ）、ginisplit（ ）、ginisplit（ ）、ginisplit（ ）。其值分别为：0.6、0.42、0.6、0.42。,对于ginisplit（ ），即ginisplit（35）的计算，其方法是这样的：首先构造节点N1的类矩形表，如下图1所示，其中,L的值表示样本的分布满足测试条件，R的值表示样本的分布

15、不满足测试条件；其次，根据Age的属性值确定类矩形表的值，结果如图2所示,B G,L R,（2）,B G,L R,（1）,根据图2计算ginisplit（35），即ginisplit（35）=,计算属性Salary的ginisplit。将Salary的属性表调入内存（此时可以将Age的属性表调出内存），由该属性表可知，属性Salary的取值有：15,40,60,65,75,100。分别计算ginisplit（ ）、ginisplit（ ）、ginisplit（ ）、ginisplit（ ）、ginisplit（ ）。其值分别为： 0.27、0、0.22、0.33、0.4。,由上可知，属性Sal

16、ary的ginisplit（ ）的值最小，那么可以由N1引出两个孩子节点N2和N3，将N2和N3入队，并将Salary属性表中第一和第二个记录（其Salary值均不大于50）的rid值改为N2，类表中的其余leaf值改为N3。,f r,1 2 3 4 5 6,属性表,类表,Class List,Salary List,N2,N3,N3,N2,N3,N3,N3,Salary50,N1,N2,（6）队列quene的队头元素出队，即N2出队。,（7）计算刚出队元素N2所对应节点的ginisplit。此时只需考虑属性Age，将Age的属性表调入内存，由该属性表及类表可知，属性Age对应节点N2的取值有：23、55。由类表可知，对于此的两条记录均属于B类，不需计算ginisplit。节点N2不再分解，为叶子节点。,（8）队列quene的队头元素出队，即N3出队。,（9）计