计算机研究与发展
Journal

ofComputerResearchandDevelopmentISSN100021239ΠCN1121777ΠTP
44(1):126~132,2007
无重复投影数据库扫描的序列模式挖掘算法
张 坤 朱扬勇
(复旦大学计算机与信息技术系 上海 200433)(042021150@fudan1edu1cn)
SequencePatternMiningWithoutDuplicateProjectDatabaseScan
ZhangKunandZhuYangyong
(DepartmentofComputingandInformationTechnology,Fudan,200433)
Abstract SequencepatternofWebclickstreams,thepredic2tionofdisastersandofproteinsequences1PrefixSpan,whichisbasedonfrequent,oneofthefastestalgorithmstowardsthistarget1However,PrefixSpanamountofduplicatedprojectdatabasesinminingdensedatasetsandlongse2quencepatterns1Inordertoovercomethisdrawback,arandomalgorithmnamedSPMDSisproposed1ThealgorithmavoidsscanningduplicatedprojectdatabasesbycheckingevidencescomputedbyexercisingonewayhashfunctionsuchasMD5topseudoprojectionsofprojectdatabases,andalsoimprovesitsperfor2mancebysimplifyingthesearchintheprojecttreeusingsomenecessaryconditions1BothexperimentsandanalysesshowthatSPMDSisbetterthanPrefixSpan1
Keywords sequencepatternmining;projectdatabase;prefixtree;onewayHashfunction
摘 要 序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广
泛应用1基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一1然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降1算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能1实验和分析都表明SPMDS性能优于PrefixSpan1
关键词 序列模式挖掘;投影数据库;前缀树;单向杂凑函数中图法分类号 TP311
Agrawal和Srikant不仅是序列模式挖掘概念的奠基人,而且还在文献[1]中提出了AprioriAll,AprioriSome,DynamicSome等序列模式挖掘算法;随后他们又提出了GSP算法[2],该算法通过改进连接方式等技术提高了算法的性能1Zaki将序列数据表示成一种垂直的形式,提出了性能更好的SPADE[3]算法1这些算法的共同点在于都需要产生大量的候选集,在候选集的生成和剪枝过程中消耗大量的时间1频繁模式增长算法FreeSpan[4],PrefixSpan[526]打破这种性能上的瓶颈,这类算法采用分而治之的思想,先
收稿日期:2005-11-12;修回日期:2006-07-27 基金项目:国家自然科学基金项目(60573093)
将序列数据库划分成小的投影数据库,然后在投影
数据库中递归地挖掘序列模式,取得了较好的效果1
此外还有一些针对数据结构的优化算法:MEMIPS[7]基于内存索引,仅对PrefixSpan做了微小的改动;WAP2Tree[8]是一种类FP2Tree[9]的结构,它试图共享不同序列中的共有数据,然而需要产生大量的中间树,实验表明共享的数据并不多;SPAM[10]用位图来描述序列数据,提出了i2extend和s2extend的概念并进行剪枝优化,但不能很好地解决位图的稀疏性问题1
第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的序列...重复第二步,直到没有新的序列模式或新的候选序 列...
热门文档