张 坤等:无重复投影数据库扫描的序列模式挖掘算法
127
Table1 AnExampleofSequenceDatabase
虽然PrefixSpan已经取得了较好的性能,但不能很好地解决密数据集或长模式的挖掘问题,根本原因在于序列模式挖掘过程中存在大量的重复投影数据库1本文提出了一种名为SPMDS的算法,首先将投影数据库是否相等的判定问题转化为伪投影是否相等的判定问题,接着对伪投影做单向杂凑函数,将伪投影是否相等的判定问题简化为伪投影Hash值是否相等的判定问题,最后按照投影数据库相等的必要条件,对前缀树做索引,简化搜索代价,从而解决了重复数据库扫描问题1实验和分析表明算法的性能优于PrefixSpan1
表1 序列数据库的一个例子
SequenceID
1234
Sequence
EABCDEBABCDAEBCDBDF
为讨论简单项的序列模式挖掘算法,首先给出
两个定义,献[5]1
、:
(m<n),1,,a,1,b2,…,bm〉s2是s1的子序列,且s1≠s2,若存在序列s3=
(m<l=n),满足:①c1=b1,c2=〈c1,c2,…,cl〉
b2,…,cm=bm;②除了s1外,没有任何s1的子序列包含s3,并令s4=s3-s2,则称s4为s2相对于s1的投影1序列数据库中所有关于序列s2的投影组成的集合称为s2的投影数据库1
例21假设序列数据库为表1所示,AB相对于EBABCD的投影为CD,AB的投影数据库如表2所示:
Table2 TheProjectDatabase

ofAB
1 相关定义
,,en,记为〈e1,e2,…,en〉,项集1本文只讨论每个事件都是简单项的情况1序列的长度是序列中事件的个数1给定序列s1=〈a1,
(n=m),如果存在a2,…,an〉,s2=〈b1,b2,…,bm〉
1=i1<i2<…<in=m,使得a1=bi1,a2=bi2,…,
an=bin,则称s1是s2的子序列,或称s2包含s11
序列数据库(SDB)是序列的集合,记为SDB={s1,
s2,…,sm}1序列s的绝对支持度α是序列数据库中
表2 AB的投影数据库
SequenceID
123
Sequence
CDCDCD
包含s的序列的个数,相对支持度为αΠ|SDB|
(|SDB|表示序列数据库中序列的个数)1除实验部
分外,本文只采用绝对支持度1给定一个阈值ζ,序列模式挖掘是从SDB中找出所有支持度大于ζ的序列s1如果s的支持度大于阈值ζ,则称s为频繁序列模式,简称序列模式1
根据Apriori性质可知,如果s是s′的子序列,那么s的支持度不小于s′1s为闭合序列模式,当且仅当s是一个序列模式且不存在s的超序列s′,使得s′和s有相同的支持度1关于闭合序列模式挖掘的最新研究见CloSpan[11]和BIDE[12]1
例11表1给出的序列数据库由4个序列组成1假定支持度的阈值为2,那么这个序列数据库中的序列模式为AB,AC,AD,BC,BD,CD,EA,EB,
EC,ED,ABC,ABD,ACD,BCD,EAB,EAC,EAD,EBC,EBD,ECD,ABCD,EABC,EABD,EACD,EBCD,EABCD,而闭合序列模式为ABCD,BD,EABCD,EBCD1可以看出闭合序列模
定义21前缀树1序列数据库的前缀树是指满
足以下条件的树:
①除根结点外每条路径都对应一个序列;
②按照字母序排列,左兄弟结点小于右兄弟结点;
③子结点都由父结点对应序列的投影数据库中支持度大于阈值的项组成1
根据表1,投影数据库的前缀树如图1所示:
Fig11 Theprefixtreefortable11
式要远少于序列模式,实际情况也是如此1
图1 表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的序列...重复第二步,直到没有新的序列模式或新的候选序 列...
热门文档