XML流挖掘实现文档 INDX OF.docxVIP

XML流挖掘实现文档 1.相关背景 1.1有序树与无序树的相关概念 有序树存在节点间的一个唯一的排序规则，而无根树是预先定义结点间的一个排序规则，每个结点的所有子结点都从左到右按这个排序规则排列 2.有序子树挖掘算法描述 2.1 初始化局部子树池和全局子树池两个数据结构 APT和GPT结构类似，都是树状的结构，每个节点代表一棵子树。它们的根都为虚根。 2.2接收XML数据流 接收的XML数据流，形成一棵棵的XML树，例： 2.3按照深度优先的方式遍历范式化的树，在APT中利用尾节点扩展的方式进行子树枚举 第一棵子树按照深度优先遍历的结果是A1 , B2, C2, D3，、 第二棵子树的深度优先遍历结果是A1,B2,D3,C2 按照这样的顺序进行局部子树池尾节点扩展，尾节点扩展的方法如下： 1.当前读入的节点被看成尾节点 2.在原来的树中找到尾节点的父节点 3.在局部子树池中找到包含该父节点的局部子树池节点 4.把尾节点添加在这些局部子树池节点之后，形成新的局部子树池节 例子中的两棵树生成的局部子树池树结果如下： 2.4把局部子树池中的子树插入全局子树池中，清空局部子树池，准备处理下一颗树 读完一棵树，把形成的局部子树池分别归并到全局子树池中，全局子树池中包含了节点的COUNT属性，如果在全局子树池中找到相应子树则Frequent++，否则插入新的全局子树池节点，这个节点的delta为最大可能的误差，frequent = 1。 两颗子树插入完成后的全局子树池如下所示。 插入完成后清空局部子树池。 2.5当插入一个batch的树后，利用Lossy Counting进行剪枝并输出结果 假设BatchSize为2，support为2那么在插入两棵树后，进行Lossy Counting的剪枝 ，f+delta = bcurrent（当前Batch的ID）的子树会被剪去，而frequent大于等于2的子树会被输出。 于是上述结果中输出的子树为以下7棵 3.无序子树挖掘算法描述 3.1 初始化全局树和等价类树两个数据结构：这两个结构体是算法的核心。全局树和等价类树都是树状的结构。全局树存有节点、边、标签、TID等信息，等价类树则存着前缀等价类以及频繁项信息。 3.2 读入输入流： 假设传入的batchsize 定为4，support为0.5 。那么，一个BACTH中有4棵XML树。 3.3把读到的XML树插入全???树中：根据每棵接收到的XML树，我们把它们插入全局树的数据结构中,根据点和边的异同来判断是否新插入节点，全局树除了存储了节点，边，根，标签之外，每个节点还存储了一个先序遍历的数字、transaction ID list（TIDList）、oTID和active值（标志是否是当前BACTH）。 3.4调整TIDLIST：对每一条路径和全局树中的active路径进行比较,(active路径即是当前batch中包含的路径)如果有一条路径是非active但是它又被一条active路径所包含(test inclusion)，那么它也被标成active，并且加入包含它路径的TID。于是全局树变成（路径167被168包含，所以7加上8中的TID），于是RST(167).TIDList = {3,4} , RST(167).oTIDs = {3}, RST(167).gTIDs = 4 3.5 用等价类树生成所有候选带根子树：首先构造C0， C0为DTS的根节点,没一层次的等价类都由上一层的等价类推导而来，ck推导ck+1主要通过两个方法，第一是最右active叶节点扩展，第二是等价类内join，之后在已有的等价类树中查找，如果已存在那么更新count，不存在的话新建，所有等价类内的RST的节点都有指针指向全局树中相应的节点。等价类扩展的示例和完整的结果如下图 可见不经剪枝的等价类树会非常的庞大，所以在每一层生成等价类后需要进行剪枝，而且在执行过程中，仅仅需要对标志为active的带根子树进行操作，每个等价类都是按照TREE ENCODING的顺序排列。首先是做最右active叶子节点扩展，然后把当前RST和排序排在当前RST之后的active RST进行求交操作，交操作之后生成的新的RST的TIDLIST是之前两个子RST的 TIDLIST的交集，最后返回新生成的等价类。 3.6 剪枝：对生成的等价类我们要进行剪枝操作，从上一步生成的等价类中，我们依次选取RST，RST的TIDLIST有以下相关属性（ n1到nm是RST的叶子节点）： (1) RST.TIDList = n1.T IDList ∩ . . .∩ nm.T IDList; (2) RST.oT IDs = n1.oT IDs ∩ . . .∩ nm.oT IDs; (3