张 坤等:无重复投影数据库扫描的序列模式挖掘算法
129
投影数据库相同,所以D成了ABC和AC的公共子结点,压缩了前缀树的大小1但前缀树仍可能很庞大,如果每生成一个新的结点,都在已生成的前缀树中检查是否存在相同的投影数据库,代价依然很高1利用投影数据库相等的一些必要条件可以提高搜索的效率1 定理21如果两个前缀序列拥有相同的投影数据库,那么这两个投影数据库的大小必然相同,前缀序列的最后一项也必然相同1
证明1略1
类似的必要条件还有很多,可根据实际情况选择,选择的一般依据为①计算代价较小;1据结构,,具体由STL提供的m实现1
综上分析,可得到SPMDS算法1
算法21MiningSP(s,D,minsup,F)1
输入:序列数据库D;支持度阈值minsup1输出:序列模式集F1①s=NULL;
②CallSPMDS(s,Ds,minsup);③遍历前缀树s得到序列模式集F1算法31SPMDS(s,Ds,minsup)1输入:树结点s、投影数据库Ds和最小支持度阈值minsup1
输出:前缀树1
①扫描一遍Ds得到所有的频繁项w;②将w作为s的子结点;
③if|Ds|<minsup或者不存在w④ return
⑤for每一个wdo⑥ 从Ds得到Dw;⑦ 按照必要条件搜索,并通过计算单向杂凑
函数值判断是否存在重复的投影数据库
p;
的性能,以下的所有分析仅考虑投影数据库不空的序列模式和闭合序列模式,定理3给出了一个估计1
引理21不同投影数据库的数量不大于序列模式的数量,不小于闭合序列模式的数量1
证明1显然每一个序列模式最多需要一个投影数据库与之对应,因此不同投影数据库的数量不大于序列模式的数量,又任意两个不同的闭合序列模,或者支持度不同,不满足定理21
2,3给出了另一种估计1
31不同投影数据库的数量不大于闭合序列模式的长度之和1
证明1假定生成一棵闭合序列模式的前缀树,很容易看出,生成一个结点最多需要一个投影数据库与之对应,从而结论成立1
综合以上引理,可得如下定理1
定理31不同投影数据库的数量小于序列模式数量和闭合序列模式长度之和的极小值,大于闭合序列模式的数量1
分析算法2和算法3可知,这两个算法的时间复杂度均为O(k×n),k为扫描投影数据库的次数,n为平均每次扫描投影数据库的元素个数,n值的大小由数据库的规模决定,k为O(2m),m为长度等于1的频繁项个数,在大数据集上挖掘,k值的大小决定了算法的性能1以较小的代价判断是否存在重复投影数据库可以显著减小k值,从而提高算法性能1以下详细分析了两个算法性能上的差别1
单向杂凑函数的计算代价和树的搜索代价为t,用PrefixSpan构造前缀树时需要Pn个投影数据库,其中有Sn个不相同,则PrefixSpan最多需要额外计算和搜索Pn个投影数据库,其代价为t×Pn1又假定每发现一个重复的投影数据库节省的代价为r(rµt),则总的节省代价为r×(Pn-Sn)1因此,假定本文的算法SPMDS相对于PrefixSpan节省的代价为C,由上分析可知:
C>r×(Pn-Sn)-t×Pn=
Pn×[r(1-SnΠPn)-t]1
(1)
⑧ ifp存在do⑨ 将p的所有子结点插入到w的子结点中⑩ return λ elseωλ SPMDS(w,Dw,minsup)1
根据序列模式和闭合序列模式的数量,定理3
能够给出SnΠPn的估计值,从式

(1)可知,SnΠPn越小t越小,SPMDS的效果越好1从而在长序列模式和密数据集挖掘上,SPMDS有较佳的效果,t可以通过选用不同的单向杂凑函数和采用不同的必要
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的序列...重复第二步,直到没有新的序列模式或新的候选序 列...
热门文档