文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 无重复投影数据库扫描的序列模式挖掘算法
侵权投诉

无重复投影数据库扫描的序列模式挖掘算法

128

计算机研究与发展 2007,44(1)

2 无重复投影数据库扫描的算法

算法11简单项的PrefixSpan算法1

PrefixSpan(s,Ds,minsup,F)1

输入:序列数据库SDB和最小支持度阈值minsup,Ds为序列s的投影数据库1

输出:所有的序列模式F1①将s插入F,

②扫描一遍Ds找到所有支持度大于minsup的项w,

③if|Ds|<minsup或者不存在w④  return⑤for⑥ ⑦ +w,Ds+w,minsup,F)1算法的挖掘过程是采用深度优先策略的前缀树生成过程,算法的性能与扫描投影数据库的次数相关1由此不难得到以下引理1

引理11深度大于1的前缀树的结点数等于序列模式的个数,生成前缀树需要扫描投影数据库的最小次数为前缀树的内部结点数,最大次数为整个树的结点数1

证明1算法的运行过程实际上是每个结点的处理过程,每次递归都在第2步扫描一遍数据库,因此引理1成立1

如果要生成长序列模式如〈e1,e2,…,e20〉,至少会有219-1个内部结点,根据以上引理,至少需要扫描219-1次数据库,造成算法的性能急剧下降1在实际的扫描过程中会出现很多重复的投影数据库,例如,从表1所示的序列数据库中不难看出,EB和AB具有相同的投影数据库1

CloSpan[11]在挖掘闭合序列模式中给出了一个判定投影数据库相等的简明定理,虽然取得了较好的性能,然而这个定理不仅需要判断两个前缀序列是否包含,而且只能挖掘闭合序列模式,挖掘时仍可能会扫描重复的投影数据库1为此本文给出另一个定理1

定理11每个序列的投影数据库都能够用一系列指向原始数据库的指针表示,这一系列的指针称为伪投影;两个投影数据库相等,当且仅当这一系列的指针相等1

证明1因为投影数据库只是原始数据库的一个子集,如果重新在内存中生成投影数据库则需要消

耗大量的内存,伪投影就避免了反复生成投影数据库1例如AB的投影数据库可以通过指向原始数据库(表1)中第1个序列的第4个元素、第2个序列的第5个元素、第3个序列的第4个元素的3个指针表示1如果两个序列的投影数据库所对应的一系列指针完全相同,意味着这两个序列有完全相同的投影数据库1

在文献[526]中,使用伪投影是为了避免投影数据库大量的生成,,,首先,其次指针的比较次数,1因此,本文选用单向杂凑函数降低检查代价1

推论11如果单向杂凑函数的冲突率可以忽略,那么两个投影数据库相等当且仅当两个投影数据库伪投影的Hash值相等1

证明1如果冲突率忽略,伪投影是否相等的判定问题等价于伪投影Hash值是否相等的判定问题,由定理1,伪投影是否相等的判定问题又等价于投影数据库是否相等的判定问题,因此,投影数据库是否相等的判定问题等价于伪投影Hash值是否相等的判定问题,推论1成立1

目前有很多著名的单向杂凑函数,这些杂凑函数的冲突概率一般都可以忽略,例如MD5[13],UHASH[14],SHA21[15]等1利用推论1,在每生成一个投影数据库的过程中,需要计算一遍这个投影数据库的Hash值,将这个值保存在前缀树中,在前缀树的深度优先生成过程中,如果发现某个结点p对应的Hash值等于当前结点w的Hash值,意味着投影数据库相同,从而不必继续扫描重复的投影数据库,

无重复投影数据库扫描的序列模式挖掘算法

只需要将p在投影数据库中的子结点同时作为w的子结点即可1

经过改进后,算法的执行过程实际上变成改进的前缀树生成过程1在改进的前缀树中,某些结点可能存在共享1例如在图2中,由于ABC和AC的

Fig12 Twolayerindexandimprovedprefixtree1

图2 两级索引结构和改进的前缀树

上一页第3页

你可能喜欢

热门文档

相关文档

  • 序列模式挖掘算法

    第4章 序列模式挖掘算法 2010-9-6 1 主要内容...并将Li+1作为新的种子集 重复第二步,直到没有新...如果α为空,则为S,否则为α的投影数据库 扫描S...

  • 数据挖掘序列模式算法

    数据挖掘序列模式算法_IT/计算机_专业资料。数据...并将Li+1作为新的种子集 重复第二步,直到没有新...不断产生序列数据库的多个 更小的投影数据库,然后...

  • 序列模式挖掘算法

    序列模式挖掘算法简介报告人: 报告人:邓爱林 2001-...并将 i+1作为新的种子集 重复第二步, 重复第二...否则为α的投影数据库 扫描S 找到满足下述要求的...

  • 序列模式挖掘算法

    序列模式挖掘算法简介报告人: 报告人:邓爱林 2001-...并将 i+1作为新的种子集 重复第二步, 重复第二...否则为α的投影数据库 扫描S 找到满足下述要求的...

  • 多维序列模式挖掘

    无重复投影数据库扫描的序列模式挖掘算法[J].计算机研究与发展, 2007,44(1):126—132 [9] Lin Ming — yen , Lee S Y . Fast discovery of sequential ...

  • 【论文】一种基于序列末项位置信息的序列模式挖掘算法

    一种基于序列末项位置信息的序列模式挖掘算法_专业资料。针对PrefixSpan算法中反复扫描投影数据库寻找局部频繁项并重复构造挖掘大量重复投影数据库的不足,提出一种...

  • 序列模式挖掘算法简介

    然后在各个投影数据库上进行序 列模式挖掘 2001-8-15 10 一、序列模式简介 ...GSP算法描述: ? 扫描序列数据库,得到长度为1的序列模式L1,作 为初始的种子集...

  • 基于投影数据库的序列模式挖掘增量式更新算法

    基于投影数据库的序列模式挖掘增量式更新算法_自然科学_专业资料。基于投影数据... 无重复投影数据库扫描的... 暂无评价 7页 2.00 序列模式挖掘算法的分析...

  • 序列模式挖掘算法

    更小的投影数据库,然后在各个投影数据库上进行序 ...GSP算法描述: ? 扫描序列数据库,得到长度为1的序列...重复第二步,直到没有新的序列模式或新的候选序 列...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email