HI,欢迎来到学术之家,学术咨询:400-888-7501 订阅咨询:400-888-7502 股权代码 102064

基于索引树的带通配符序列模式挖掘算法

作者:王乐; 王水; 刘胜蓝; 王辉兵数据挖掘序列模式通配符模式匹配索引树

摘要:随着有序时间序列数据的出现,序列模式挖掘成为数据挖掘领域的一个分支.其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题,同时随着数据规模越来越大,算法的挖掘效率尤为重要.现有算法多采用树型结构来实现数据的压缩表示,树的结构和模式匹配方法对挖掘效率有决定性的影响.该文首先设计一个新的树结构索引树I-Tree(Index-Tree)来维护原始序列数据以及序列模式和模式索引信息;然后在索引树的基础上,提出一个新的带通配符的序列模式挖掘算法ITM(Index-Tree based sequential pattern Mining).算法ITM主要用4个策略提高算法的挖掘效率:(1)将原始序列中相同项压缩到一个节点上,该节点只记录项在原始序列中的索引;(2)采用迭代的方式,长度k+1的序列模式是用长度k(k>0)的候选序列模式产生;(3)采用前缀树的结构,逐层将k+1的候选序列模式压缩到索引树上,叶子节点上记录序列模式最后一项的索引;(4)整个挖掘过程,只用一棵索引树.算法ITM通过采用以上索引树压缩原始序列数据以及存储候选序列模式,有效地缩小搜索空间,从而算法效率得到显著提升.另一种提高挖掘效率的思路,是在挖掘过程中允许有小部分的模式丢失,来换取挖掘效率的大幅度提升,即所谓的近似模式挖掘.该文也给出了一个近似序列模式挖掘算法AITM(Approximate Index-Tree based sequential pattern Mining),该近似算法通过估计超序列模式的支持数,将非候选节点提前删掉,减少索引树上的节点个数,从而提高算法的时空效率;但是也因为估计的支持数可能会小于实际值,从而丢失了部分频繁的序列模式.该文实验中,提出的两个算法分别与算法MGCS、MAPB和MAPD进行了对比实验,采用3个典型数据序列进行测试,并设计了3组实验:(1)不同的最小支持度对算法的效率影响;(2)算法的扩展性;(3)通配符长度对算法效率�

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

计算机学报

《计算机学报》(月刊)创刊于1978年,由中国计算机学会与中国科学院计算技术研究所主办、科学出版社出版,以中文编辑形式与读者见面,同时以英文摘要形式向国际各大检索系统提供基本内容介绍。 一直在计算机领域保持着领先水平,刊登的文章被国际多种著名检索刊物所收录.包括《中国学术期刊文摘》,美国《EI》,英国《SA》,美国《数学评论》,日本《科技文献速报》,俄罗斯《文摘杂志》等。 《计算机学报》刊登的内容覆盖计算机领域的各个学科,以论文、技术报告、短文、研究简报、综论等形式报道以下方面的科研成果:计算机科学理论、计算...

杂志详情

相关期刊
×

说明:关注微信公众号,免费领取下载码。

 

发送任意关键词,比如“下载”,即可下载该篇文章。

PDF文件建议使用adobe或Office打开

作品认领

本站文章皆为用户上传,可能会出现作者遗漏,为促进学术资源开放获取,作者完成个人作品认领,即可获得平台文献免费下载权限。

详询在线客服 ×

被举报文档标题:基于索引树的带通配符序列模式挖掘算法

被举报文档地址:


我确定以上信息无误

举报类型:

非法(文档涉及政治、宗教、色情或其他违反国家法律法规的内容)

侵权

其他

举报理由:
   (必填)