SLIQ算法

基本内容SLIQ:一种快速可扩展的分类算法SPRINT:数据挖掘中一种可扩展的并行分类器SLIQ:一种快速可扩展的分类算法分类算法存在一个问题——不能进行扩展数据量在急剧增长，训练样本达到数百万是非常普遍的，由于内存及CPU时间的限制，原有的许多算法已经无法处理这些数据。因此，必须寻找新的方法来解决大数据集的分类问题。扩展性问题可扩展：对应于分类算法评估尺度中的伸缩性。伸缩性：指对磁盘驻留数据的处理能力，即对大数据量有效构造模型的能力。SLIQ算法提出的意义：为了解决一般算法无法解决的可伸缩性问题。一般决策树分类方法决策树的构造分为两个阶段：1.树的构建对每个属性分支计算最优分支选择。使用最优的分支生成划分。2.树的修剪修剪策略有基于代价复杂度的修剪，悲观修剪，和最小描述长度MDL修剪。一般决策分类方法决策树的构造分为两个阶段：1.树的构建对每个属性分支计算最优分支选择。使用最优的分支生成划分。2.树的修剪修剪策略有基于代价复杂度的修剪，悲观修剪，和最小描述长度MDL修剪。最优分支的选择问题最优分支的选择依据于分支指标，分支指标用来给属性的可选分支确定“优良程度”。分支指标：熵（ID3和C4.5）最小Gini指标（CART，SLIQ和SPRINT）。SLIQ使用Gini指标作为分支指标定义：对数据集包含n个类的数据集S，Gini(S)定义为：，Pj是S中第j类数据的频率。如果集合S分成两部分S1andS2。那么这个分割的Gini就是：提供最小Ginisplit就被选择作为分割的标准。21()1njjGiniSP1212()()()splitnnSGiniGiniGiniSSnn式中，n1，n2分别是S1，S2的记录数。连续属性的分支选择操作：采用的二叉分支的方法。第一步，与C4.5的处理方法类似，即根据将要分支的属性取值对训练样本进行排序。设属性取值排序后的结果为v1，v2……，vn，vi和vi+1之间一般取中间点(vi+vi+1)/2作为分支点，这样需确定n-1个可能的分支。因为每次计算都需要排序，所以这项操作的代价极大。解决：SLIQ在树的构建阶段是用预排序技术以减少计算连续属性的代价。Av离散属性的分支选择测试：设S（A）为离散属性A的所有值的集合，则分支测试就是具有的形式，其中为S产生的子集。有n个取值的属性所产生的子集数量为个。因此对最优子集的搜索的代价将是十分昂贵的。解决：若属性A所有可能值的集合S的笛卡尔乘积小于一个阈值MAXSETSIZE，则直接计算S的所有子集。否则使用贪心算法。ASS2n贪心算法：即先将一个集合C置为空集，另一个集合D包含所有的值，然后反复地从D中选取一个值移至C中，直到没有合适的值可以选取。选择移动的值应满足条件：移动后导致Gini值减小并且与移动其它值相比其Gini值是最小的。树的修剪修剪阶段要选出拥有最小已估计错误比率的子树。估计错误比率的方法：使用原始训练样本集，如交叉验证等。对于大数据集不可用，因构建一个决策树代价很大。使用独立的数据集，如何确定测试数据集的大小，及导致精度降低。解决：SLIQ使用基于最小描述长度（MDL）方法来修剪决策树。SLIQ使用如下技术提高可扩展性1.用预排序技术来减少计算连续属性的代价。2.利用贪心算法来确定离散属性的分支。3.使用MDL算法修剪树。SLIQ中预排序所需的数据结构SLIQ使用若干驻留磁盘的属性表和单个驻留内存的类表。属性表：有两个字段，①属性值，②指向类表的索引。类表：也有两个字段，①类的标号，②决策树叶节点的指针。天气索引晴0多云1…………类型叶点适合N1不适合N1…………预排序过程首先，对训练数据扫描一次后，为每一个非类别属性建立一个属性表，每一个属性值都对应着相应的类表索引。类表的所有叶指针字段都指向决策树的根节点。连续属性的属性表独立地进行排序。预排序举例agesalaryclass3065G2315B4075G5540B55100G4560Gageindex232301403456555554salaryindex1524046066517531005classleafGN1BN1GN1BN1GN1GN1预排序后123456驻留磁盘的属性表驻留内存的类表训练数据集预排序后计算最佳分割最佳分割包括两个内容：属性的最佳分割点，最佳的分割属性。为了计算节点中属性的分支指标Gini，在每个叶节点对应的数据划分中需使用类的频率分布。分布通过附加在每一个叶节点上的类矩形表累计。类矩形表类矩形表(histogram)：位于决策树的每个节点内，存放每个节点当前的类分布信息——左、右子树的每个类各拥有多少条记录。对于连续属性，矩形表由形如类，频率的若干对组成。对于离散属性，矩形表有形如属性值，类，频率的若干三元组组成。计算连续属性最佳分割当前属性是连续属性时，每次做遍历时，类矩形表亦随之改变，随时表征以当前属性A的当前值v做分割点时对叶子的分裂状况。并由类矩形表计算出某个分裂方案的Gini值。完成对属性A的遍历后，Gini值最低的A的值就是用属性A分裂的最佳值。新方案可以存入决策树节点。计算离散属性最佳分割当前属性是离散属性时，遍历过程中，记录下每个属性值对应的类的分布信息。遍历完成后，利用贪心算法得到Gini最小的离散属性A的子集。即为所求的用A的分裂方案。新方案可以存入决策树节点。分支计算举例如图，假设在属性age上使用分支对数据已初始化。当前待分裂属性Salary，右边为类矩形图的变化过程。属性表从上往下扫描。12345635agesalaryrid1524046066517531005classleafGN2BN2GN3BN3GN3GN3N1N2N3001100131001001310011003初始矩形表更新类矩形表及计算N2第一个分支节点(salary≤15)更新类矩形表及计算N3第一个分支节点(salary≤40)BGBGBGBGBGBGLRLRLRLRLRLR35age选择分支属性生成子节点并更新类表最佳分割求解出后，信息已存放在节点中，算法的下一步便是创建子节点、更新类表。这一步的主要任务是对应该分裂的类表进行更改。类表的更新算法Updatelables()for在分支中使用的每一个属性Ado遍历A的属性表for属性表中的每一个值vdo找到类表中的对应位置（比如说e）通过在从e指向的节点上进行分支测试找到v所属的新类c将e的类标号更新到c更新在e中引用的节点到与类c对应的子节点endend类表更新举例agerid232301403456555554salaryrid1524046066517531005classleafGN2BN4GN3BN3GN3GN3N1N2N3N4N5N6N7123456N6Age≤35Salary≤50Salary≤40属性表类表属性表SLIQ采用MDL修剪MDL(MinimumDescriptionLength)思想：遵循最简单的解就是最期望的。编码的总代价为：Cost(M,D)=cost(D/M)+cost(M)其中,cost(D/M)：给定模型M后对数据编码的比特数。cost(M)：对模型M编码的代价。MDL目标：就是修剪决策树以使Cost(M,D)最小。算法流程算法的控制结构是一个队列。这个队列存放当前的所有叶子节点，这是为了控制搜索的结束。当队列为空时，说明所有的叶子节点都已经被处理完毕，这时建树算法可以结束。算法流程举例设训练样本数据集如右图：agesalaryclass3065G2315B4075G5540B55100G4560GSLIQ的执行过程创建根节点N1创建并排序属性表，创建类表：属性表属性表类表123456年龄表工资表类表ageindex232301403456555554salaryindex1524046066517531005N1classleafGN1BN1GN1BN1GN1GN1预排序SLIQ的执行过程创建空队列queue，并将N1入队fr队列queue的队头元素出队，及N1出队计算出刚出队的元素N1所对应节点Ginisplit①计算属性age的Ginisplitage对应节点N1的取值有：23、30、40、45、55、55分别计算N1splitsplitsplitsplitsplit2330304040454555ini23iniiniiniini2222GGGGG、、、、、splitini55GAge中Gini值的计算对于即的计算方法如下：首先构造节点N1的类矩形表，如图（a）；其次根据age的属性确定类矩形表中元素的值，结果如图（b）；最后根据图（b）计算即：同理可以求出、、splitini35Gsplit3040ini2GBGLR（a）BGLR1113（b）splitini35Gsplit21111411335ini35110.42622226444412Gsplit4555ini0.422Gsplitini230.44Gsplit2330ini0.62Gsplit4045ini0.62Gsplitini550.44Gsalary中Gini值的计算②计算属性salary的GinisplitSalary属性中取值有：15、40、60、65、75、100同样以计算出值分别为0.44、0.27、0.22、0.33、0.4、0.44。由上可知，属性salary的最小，那么N1引出两个子节点N2和N3，将N2和N3入队，并将salary属性表的第一和第二个记录（salary=50）的Index值在类表中对应的leaf值改为N2，类表中其余的改为N3，如下图表示。frsplitsplitsplitsplit154040606065ini15iniiniini222GGGG、、、、splitsplit657575100iniini22GG、split4060ini2GN2N3类表更新agerid232301403456555554classleafGN3BN2GN3BN2GN3GN3N1N2N3salary≤50属性表类表123456年龄表类表队列queue的队头元素N2出队计算刚出队元素N2所对应的节点的Ginisplit。此时只需考虑age属性，由属性表可知age对应的节点N2取值有：23、55，再由类表可知对于这两条记录都属于B类，所以不需要计算gini值，节点N2不再分解。队列queue的队头元素N3出队计算N3所对应的节点的Ginisplit。此时只需考虑age属性，由属性表可知age对应的节点N3取值有：30、40、45、55，由类属性表可知其都属于G类，故也无需计算gini值，N3也不再分解，作为叶节点。队列queue为空，整个过程结束。对应的决策树如图。N1N2N3salary≤50SLIQ算法总结SLIQ采用二分查找树结构，对每个节点先计算最佳分裂方案，然后再执行分裂。SLIQ使用新的数据结构以利于树的构造：若干驻留磁盘的属性表和单个驻留内存的类表。SLIQ算法的优缺点优点：1、可处理磁盘常驻的大型数据集。2、使用预排序技术，提高了运算速度。3、可处理离散属性和连续属性。缺点：由于类表需要常驻内存，因此限制了SLIQ算法可处理的数据记录规模。