基于惰性学习的查询接口发现算法

《基于惰性学习的查询接口发现算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2.3.4基于GINI指示的决策树分类算法研究23.4.1CART算法分析分类与回归树(CART)是在1984年由Breinman[16]提出的，与C4.5算法一样，它也是首先生成一棵复杂的树，然后依据交叉验证和测试集验证对树剪枝，最后得到通用树。CART是ID3的一种改进，但不同点在于，CART算法采用的是二分递归分割方法，在每个子类需要产生子节点处产生且只产生两个节点，这样就使得产生的决策树中除叶节点外每个节点都有两个子节点，因此该算法产生的决策树是二叉树。CART算法每次划分数据集的依据是Gini系数(GiniInd

2、ex),Gini系数越小划分的准确性越好。如果训练样本集S含有n个不同的类，则Gini(S)的定义为：Gini(S)=1.0-^p2(2-15)其中Pi是i类在S中出现的概率，如果S被分成&和S2两类，那么这次划分的Gini系数是：⑻=gGiniCSJ+l^Gini(S2)(2-16)1^11^1其中，

3、S

4、、

5、sd、

6、S2

7、分别为S、S:、&中的样本个数。CART算法求得在所划分属性上所有划分的Gini系数，哪种划分Gini系数最小就作为在该属性的最优划分，然后与所有候选属性的最优划分相比较，Gini系数最小的划分的属性

8、就作为最终测试属性。CART算法在有下列条件之一出现时停止建树：•节点的样本数只有1个；•剩余样本属于同一个类；•决策树高度超过了用户设定的阈值；之前的决策树算法只给叶节点分配类别，中间节点没有类别属性，CART算法认为每个中间节点可能成为叶节点，所以对每个节点(包括非叶节点和叶节点)都分配了类别。而方法可以是当前节点出现最多的类，也可以是其它更复杂的方式。CART算法对缺失数据还是非常健壮的。假如某个记录没有某个非类别属性值，决策树生成是将不使用这条记录来确定最优划分，而是用其它可用信息来确定最优分裂。当用CART算法对

9、新数据进行分类时，可用使用替代属性处理缺失值。替代属性就是模拟决策树中实际分裂值以及非类别属性，在首选非类别属性数据缺失时能用替代属性替代。CART算法是一种非参数识别技术，它的基础是统计理论,其统计解析能力很强大。但是和一般的统计分析方法所存的劣势一样，CART身上也有缺点，比如稳定性较差，在样本数据集相同的情况下，用CART算法生成的决策树模式可能有很大差别，特别是在样本数量比较小时更加明显。23.4.1SLIQ算法分析SLIQ算法是1996年由IBMAlmaden[17]研究中心提出的一种分类算法，这种算法不仅具备高

10、速可伸缩特性，还能够同时处理离散属性和数值属性。SLIQ和其它的决策树算法相比，它不仅能对内存中的数据分类，还能对驻留在外存上的数据分类，因此是可扩展的。与此同时，SLIQ算法定义了新的数据结构，使用了预排序技术，并对决策树生成加以改进，能够产生紧凑而精确结构的决策树。SLIQ算法在建立树之前就预排序所有样本的各个数值属性，首先分割训练样本，对样本上附加的类别标号建立类表，类表的每个表项包含两字段：类标号以及标识决策树的叶节点的索引。样本每一属性建立一个对应的属性表，每个属性表表项包括两个字段：属性值以及标识类表的表项的索

11、引。第i个训练样本对应于第i个类表表项。在SLIQ算法中单次只需对一个属性表操作，暂时用不到的属性表可写回外存，需要时再调回来，因此只要内存能够存储存储表和单个属性表就可以处理存储在外存上的大量数据集。构建一棵树主要有两个步骤：第一是扫描各个属性表，求出当前各个叶节点最优分支方案；第二是使用上步得出的最优方案生成样本集的划分，同时修改类表指针。Gini系数是SLIQ算法的分支指标。与基本决策树算法相比，SLIQ算法的先进性在于实现了决策树分类的扩展性，即能够支持驻留在外存上的大量数据的迅速分类，这其中运用的多个重要策略很大

12、程度使决策树算法时间复杂度得到降低，这跟它需具备处理海量数据的能力要求是相关联的。SLIQ算法运用的提高程序分类效率的方法主要有数据属性预排序和树宽度优先增长的策略以及贪心法求解分类属性最优分裂子集。SLIQ算法能够处理大量的训练样本集，伸缩性较好。SLIQ算法执行时要修改类表，故类表必须常驻内存，而且当训练样本集増大时类表也会随之增大，从这点上说，SLIQ算法还是难以摆脱内存容量限制。为了摆脱主存的容量限制，在SLIQ基础上JohnShafer等人提出了SPLRINT算法，它从根本上解决了这个问题，SPRINT能够处理其

13、它算法都处理不了的超大规模训练集，并且容易实现并行化，能有效生成决策树。第三章基于惰性学习的查询接口发现算法查询接口的发现中非常重要的一步是如何从找到的众多表单中辨别出DeepWeb查询接口，本章主要内容是在前人研究的基础上，使用了惰性学习的K最近邻算法来提高査询接口判别的准确性。3.1惰性学习法概念惰