| 在基于兴趣的序列概念格的基础上，可以快速地发现最大的序列模式以及用户需求的频繁序列。算法思想如下：
(1) 利用算法SCLI生成基于兴趣度的序列概念格IMSL。
(2) 把格IMSL节点中各序列的位置信息保存到位置信息表中。格IMSL 中的各序列就是1-兴趣序列。
(3) 扫描位置信息表，对位置信息表中的各序列利用∞运算与∝运算进行2-序列的扩展，同时判断候选序列S在SDB中的支持兴趣度值SIM|(S)| = SIM(S)*Support(S)是否大于Min-Sim，若大于则把生成的2-序列中各序列的位置信息更新到位置信息表中。
(4) 扫描2-序列中的位置信息表，对位置信息表中的各序列利用∞运算与∝运算进行3-序列的扩展，并把生成的3-序列中各序列的位置信息更新到位置信息表中。同理生成k-序列，直到没有生成新的序列扩展或项扩展为止。
(5) 按照定义6扫描位置信息表，生成最大兴趣序列模式。
算法IMLSP(Interest Measure LatticeSequence Pattern)实现了挖掘满足用户需求的最大序列模式，具体算法描述如下：
| 算法 Procedure IMLSP (IMSL (K), IMV,) 输入：序列模糊格IMSL (K)，兴趣序列阈值Min-Sim 输出：满足用户需求的兴趣序列模式集MaxIMseq |
| 1: |
Begin |
| 2: |
Maxseq:=Φ |
| 3: |
For each node  of IMSL(K) do |
| 4: |
Mark:= Eventi |
| 5: |
Tab(S). Si:= Eventi |
| 6: |
Tab(S). Eposi := (Cid , Eid) i |
| 7: |
Tab(S). SIMi := SIMi |( Event)| |
| 8: |
For two Event of Tab(S) do |
| 9: |
IF Cidi= Cidj and Eidi<Eidj and Tab(S). SIMj ≥Min-Sim then |
| 10: |
S∝ and Tab(S). Eposi := (Eidi, Eidj) |
| 11: |
Mark:= Tab(S). Sj |
| 12: |
Endif |
| 13: |
IF Cidi= Cidj and Eidi=Eidj and Tab(S). SIMj ≥Min-Sim then |
| 14: |
S∞and Tab(S). Eposi := (Eidi, Eidj) |
| 15: |
Mark:= Tab(S). Sj |
| 16: |
Endif |
| 17: |
Endfor |
| 18: |
Update Tab(S) |
| 19: |
Call IMLSP (IMSL (K), IMV,) |
| 20: |
For each Event of Mark do |
| 21: |
IF Eventi is not subsequences of Eventj then |
| 22: |
MaxIMseq:= Eventi |
| 23: |
Endif |
| 24: |
Endfor |
| 25: |
End |
针对表1中的序列数据库中构建的基于兴趣度的序列概念格模型进行最大序列模式的挖掘，其中，Min-Sim =0.6。
表1 交易数据库
| Cid |
Sequence |
| 10 |
<(abc)(ac)d(cf)> |
| 20 |
<(ab)(df)> |
| 30 |
<(eg)(af)b> |
| 40 |
<(ab)(cd)(bg)h> |
(1) 按照算法SCLI生成相应的序列概念格的Hasse图如图1。
图1 序列概念格的Hasse图
(2) 把图1节点中各序列的位置信息保存到位置信息表中如下表2
表2 图1中1-序列的位置信息
| 1-序列 |
位置信息 |
Sim |
| <(a)> |
(10,1)(10,2) (20,1) (30,2)(40,1) |
1.0 |
| <(b)> |
(10,1)(20,1)(30,3)(40,1)(40,3) |
2.0 |
| <(c)> |
(10,1)(10,2)(10,4)(40,2) |
2.0 |
| <(d)> |
(10,3)(20,2)(40,2) |
1.8 |
| <(f)> |
(10,4)(20,2)(30,2) |
0.9 |
| <(g)> |
(30,1)(40,3) |
1.6 |
| <(h)> |
(40,4) |
1.1 |
| <(ab)> |
(10,1) (20,1)(40,1) |
0.9 |
| <(ac)> |
(10,1) (10,2) |
0.7 |
| <(bg)> |
(40,3) |
1.2 |
| <(eg)> |
(30,1) |
0.8 |
(3) 对表2中的每个1-序列利用∞运算与∝运算进行2-序列的扩展，同时判断候选序列S在SDB中的支持兴趣度值SIM|(S)| = SIM(S)*Support(S)是否大于Min-Sim，本例中Min-Sim=0.6，若大于则把生成的2-序列中各序列的位置信息更新到位置信息表中表3。
表3 2-序列的位置信息
| 2-序列 |
位置信息 |
Sim |
|
| <(a)(b)> |
(30,3)(40,3) |
0.6 |
|
| <(a)(c)> |
(10,2)(10,4)(40,2) |
1.05 |
| <(a)(d)> |
(10,3)(20,2)(40,2) |
1.2 |
<(a)(f)> |
(10,4)(20,2) |
0.5 |
| <(b)(c)> |
(10,2)(10,4)(40,2) |
1.35 |
| <(b)(d)> |
(10,3)(20,2)(40,2) |
1.5 |
| <(b)(f)> |
(10,4)(20,2) |
0.7 |
| <(ab)(c)> |
(10,2)(10,4)(40,2) |
1.1 |
| <(ab)(f)> |
(10,4)(20,2) |
0.6 |
(4) 由2-序列没有生成3-序列，故，最长的序列模式长度为2。
(5) 最后生成的最大兴趣序列模式：{<(h)>、<(a)(b)>、<(a)(c)>、<(a)(d)>、<(b)(d)>、<(bg)>、<(eg)>、<(ab)(c)>、<(ab)(f)>}，其序列模式的兴趣度值分别为{1.1、0.6、1.05、1.2、1.5、1.2、0.75、1.1、0.6}。
4.结果分析将本文研究的基于序列概念格的挖掘算法与传统的挖掘算法相比较，我们可以得出以下结论：
(1) 由于序列概念格的渐进式构造算法的优点在于可以实现概念格的维护和更新，因此，带兴趣度的序列概念格的挖掘完全适应于增量式挖掘序列模式，当有新数据加入，即数据库规模增大时，不需要重新扫描整个新数据库，只需要在原始序列概念格上进行更新操作，得到新的序列概念格，然后按挖掘过程获取新的序列模式，实现对序列模式发现的增量挖掘。
(2) 另外一个问题是由于概念格的节点数量在最坏的情况下是呈指数增长的，因此内存的消耗量有时会达到难以承受的程度，因此可以考虑利用外部存储器和分解格或者采取并行的方法来构格。
5.结语基于兴趣度的序列概念格的最大序列模式挖掘完全适应于增量式挖掘序列模式。论文检测。序列概念格构造是建立在序列数据库形式背景的基础上，序列形式背景的复杂性很大程度上制约后续处理的性能，因此如何将序列数据库转化成序列形式背景，并满足用户支持度和置信度的情况下，使序列形式背景进一步优化是一个重要的预处理研究方向。所以，下一步的研究则需要考虑并行处理以提高挖掘的效率。
参考文献
[1] AGRAWAL R，IMIELINSKI T，SWAMI A．Mining association rulesbetweensets of items in large databases[C]／／Proceedings of the ACM SIGMOD Conference on Management of Data．Washington，DC：ACM Press，1993：207—216．
[2] Agrawal R ,Srikant R. Mining Sequential Patterns [A] . Proc 1995 Int Conf Data Engineering( ICDE’95) [C] .Taipei : IEEE Computer Society ,1995. 3～141
[3] Agrawal R ,Srikant R. Mining Sequential Patterns : Generalizationgs and PerformanceImprovments[A] . Proc 5th Int Conf Extending Database Technology ( EDBT) [C] .Avignon : Lecture Notes in Computer Science , 1996. 3～17.
[4] M. Zaki. SPADE:An Efficient Algorithm for Mining Frequent Sequences. Machine Learning, 2001，41（1 / 2）:31 - 60 .
[5] Han J，Pei J，Mortazavi—Asl B，et a1．Prefixspan：Mining Sequential PatternsEficiently by Prefix—Projected Pattern Growth[C]／／AlexG，Per—Ake L．Proceedings of theInternational Conference on Data Engineering．Heidelberg：TEEE Press，2001：115—116．
[6] 王虎，丁世飞：序列模式挖掘研究与发展[J] ,计算机科学 2009Vo1．36 No．12
[7] 聂成林，王浩， 胡学钢 ：基于概念格的序列模式挖掘[J],计算机工程 2003 Vol.29 No.20
[8] 李云，徐涛，田素方，李拓.带兴趣度的序列概念格模型及其构造[J]，计算机应用，vol.28，No.3，2008：726-728。
2/2 首页 上一页 1 2 |
