序列模式图构造算法分析与实现

2005.12JOURNALOFSHENYANGINSTITUTEOFCHEMICALTECHNOLOGY

Vol.19󰀁No.4

Dec.2005

文章编号:󰀁1004-4639(2005)04-0292-04

序列模式图构造算法分析与实现

石东阳,󰀁吕󰀁静,󰀁陈未如

(沈阳化工学院,辽宁沈阳110142)

摘󰀁要:󰀁分析了序列模式图构造算法的效率,采用实际开发工具具体予以实现,并对实验结果进行分析.序列模式图构造算法的实现对基于序列模式图进行进一步的挖掘有重要意义.关键词:󰀁数据挖掘;󰀁序列模式;󰀁序列模式图中图分类号:󰀁TP301󰀁󰀁󰀁文献标识码:󰀁A

󰀁󰀁序列模式挖掘(SequentialPatternMining)是RakeshAgrawal等人首先提出的一种重要的数据挖掘方法[1],有着广泛的应用,如顾客购物习惯,Web访问模式,科学实验过程分析,自然灾害预测,疾病治疗,药物检验以及DNA分析等.

对序列模式挖掘,已经提出了很多挖掘算法.AprioriAll,AprioriSome,DynamicSome,GSP

[3]

[2]

地表示出各序列之间的关系,基于此可以对挖掘结果做进一步的研究.

1󰀁SPG构造算法及算法分析

由于SPG是MSS的图形化表示,因此构造SPG主要分2步:构造MSS;构造SPG.算法的伪码描述如下:

算法Construct

SPG

输入:序列模式集P输出:序列模式图SPG

(1)/*初始化*/

LetPbethesetofsequentialpatterns,whichistheresultofsequentialpatternmining.

LetMSSbeanemptyset.Letmbethelen󰀁gthofthelongestmaximalsequentialpatternofP.

ConstructanemptydirectedgraphG.(2)/*构造最大序列模式集MSS*/k=m

RepeatwhilePisnotempty

󰀁LetPk={p|p󰀂P,andlength(p)=k}.󰀁Foreachp󰀂Pk

󰀁󰀁󰀁Ifpisnotasubpatternofanyele󰀁mentofMSS󰀁thenMSS=MSS {p}

󰀁Endfor󰀁k=k-1󰀁P=P-Pk

以及SPADE

[5]

[4]

等一系列算法都是基于

Apriori算法提出来的;此后,基于数据投影

[6]

(dataprojection)的算法因其高效率而广为流行,如FreeSpan

和PrefixSpan

[7]

;SPADE是一种是基于内存索引

基于格的算法,而MEMISP

[8]

的方法;SPIRIT[9]使用正则表达式综合了挖掘中的各种约束(constraints)条件.

综上所述,目前,序列模式挖掘领域的绝大部分工作围绕着提高算法的性能进行,在挖掘结果的表达、整理及进一步分析等方面尚缺乏进一步深入的研究.而数据挖掘的目的是要给用户一个易理解的结果以辅助决策,现在这些序列模式是以零散的方式直接呈现给用户的.是否有一种统一的方法表示这些挖掘结果?挖掘出的序列模式之间是否具有内在的联系?基于这些挖掘结果能否进一步发现一些新的模式?基于这种思想,我们提出了序列模式图(SPG,SequentialPatternGraph)的概念[1].序列模式图可以清楚

收稿日期:󰀁2004-11-05

基金项目:󰀁辽宁省教育厅科学研究计划资助项目(20040287)

作者简介:󰀁石东阳(1978-),男,河南平顶山人,在读硕士研究生,主要从事基于序列模式挖掘的序列模式图算法分析与实现的研究.

第4期󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁石东阳,等:序列模式图构造算法分析与实现293

EndRepeat

(3)/*构造序列模式图SPG*/k=m

RepeatwhileMSSisnotempty

󰀁LetSk={s|s󰀂MSS,andlength(s)=k}.󰀁Foreachs󰀂Sk

󰀁󰀁IfGisemptythen

󰀁󰀁󰀁󰀁Constructthedirectedgraphfors,andthatwillbegraphG.

󰀁󰀁else

󰀁󰀁󰀁󰀁LetpreS,postSandelemSbeemptysets.

󰀁󰀁󰀁󰀁FindthesameprefixofsandG,denotedbypreS.

󰀁󰀁󰀁󰀁󰀁/*序列s的前几个元素与图G中某一路径上前几个结点具有相同的值*/

󰀁󰀁󰀁󰀁FindthesamepostfixofsandG,denotedbypostS.

󰀁󰀁󰀁󰀁󰀁/*序列s的后几个元素与图G中某一路径上后几个结点具有相同的值*/

󰀁󰀁󰀁󰀁elemS=s-preS-postS

󰀁󰀁󰀁󰀁ConstructthedirectedgraphG!forelemS.

󰀁󰀁󰀁󰀁IfpreSisnotemptythen

󰀁󰀁󰀁󰀁󰀁󰀁AddadirectededgefromthelastvertexofpreSinGtotheheadvertexofG!.

󰀁󰀁󰀁󰀁IfpostSisnotemptythen

󰀁󰀁󰀁󰀁󰀁󰀁AddadirectededgefromthelastvertexofG!totheheadvertexofpostSinG.

󰀁󰀁󰀁󰀁󰀁󰀁NowGisnewdirectedgraph,whichincludesanewpatterns.

󰀁󰀁󰀁󰀁Endif󰀁󰀁Endfor.󰀁󰀁k=k-1

󰀁󰀁MSS=MSS-Sk󰀁EndRepeat

对于序列模式图构造算法,影响其效率的主要是2部分,即第2步的MSS构造和第3步的SPG图构造.假设序列模式个数为n,最大序列模式个数为m,序列模式的最大长度为k.第2步要进行n次循环,每次循环的主要工作是子模式的判断.子模式的判断时间与两模式的长度之和成正比,而每次判断的次数分别是0,1,2,∀,m-1,所以本步骤的算法复杂度为O(kmn),如果将k看成是常数,则算法复杂度为O(mn).第3步要进行m次循环,每次循环的主要工作是preS和postS的计算.与第2步类似,其算法复杂度为O(km2)或O(m2).所以该算法的时间复杂度为O(k(mn+m2)),若k为常数,则为O(mn+m2).

2󰀁算法实现

根据算法的伪码描述,算法实现的数据流图如图1所示.

图1󰀁构造SPG的数据流图

各功能解释如下:

格式转换:这个过程是将用各种格式(如文本文件)表示的序列模式的挖掘结果集转换成本系统采用的表示方法,存入数据库中.数据库中保存序列模式的二维表的结构如表1所示.

表1󰀁SP表(序列表)

属性名NumberSeqNoValue

数据类型

intsmallintvarchar

大小4250

主码###

描述序列模式的序号序列模式中元素(项集)的顺序号

项的值

󰀁󰀁构造MSS:这个过程从序列模式集仔找到最大序列集并保存到数据库中.数据库中保存最大序列模式集的二维表的结构如表2所示.

表2󰀁MSS表(最大序列表)

属性名NumberSeqNoValue

数据类型

intsmallintvarchar

大小4250

主码###

描述序列模式在MSS中的序号序裂模式中元素(项集)的顺序号

项的值

󰀁󰀁构造SPG:这个过程构造序列模式图,并将构造的序列模式图的边和结点分别存入2个二维表中.其结构分别如表3、表4所示.

表3󰀁VerTab(结点表)

属性名VIDNumberSeqNo

数据类型

intintsmallint

大小442

主码#

描述结点编号序列模式在

MSS中的序号序列模式中元素(项集)的顺序号294

表4󰀁EdgTab(边表)

属性名AIDVInVOut

数据类型

intintint

大小444

主码#

沈󰀁阳󰀁化󰀁工󰀁学󰀁院󰀁学󰀁报󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁2005年

的数据库连接方式.

描述有向边的编号

3.2󰀁数据源

实验的数据源是由PrefixSpan算法生成的.PrefixSpan是一种高效的数据挖掘算法,它可以挖掘出所有的序列模式,同时也大大降低了候选序列的生成.在数据集上调用PrefixSpan算法将生成一个∃frequent.dat%文件,文件中的每一行代表一个序列.例如:(23)(3145):0.004087.其中(23),(3145)分别代表2个元素,0.004087为该序列的支持度.

实验在CPU为P&2.0G,RAM为512M的计算机上完成.实验结果如表5所示.在Pre󰀁fixSpan算法中使用的数据集是C10T8S8I8.

[7]

边的输入结点编号边的输入结点编号

3󰀁实验结果及分析

3.1󰀁编程工具

󰀁󰀁考虑到C++语言在处理数据逻辑方面比较方便,采用C++语言编写,并使用VC6.0编译器.后台数据库采用SQLServer2000,它是一个高效率的数据库管理系统.前台应用程序与数据库的连接采用ODBC方式,它是一种简单稳定

表5󰀁实验结果

支持度/%6.05.55.04.54.03.53.02.52.01.5

3804214815576668811268213542109718

3754144705366388311187200339839400

序列模式数

MSS的数目得到MSS的时间/

ms31314779941724381265512528156

37240745048453060067559551328

12204088157317662146234388663

SPG结点的数目

SPG边的数目

得到SPG的时间/

ms1617621412505781797721940437

3.3󰀁实验分析

序列模式和最大序列集与最小支持度的关系如图2所示.

图3显示了SPG的边和结点的数目与最小支持度的关系,随着最小支持度的增加,边和结点的数目都减小,但边数随着支持度的增加迅速减少,而结点数则变化不大,这说明随着支持度的增加序列之间的联系减少的很快.

图3󰀁SPG的边和结点数

图2󰀁序列/最大序列数

最小支持度

最小支持度

󰀁󰀁由图2可以看出,随着最小支持度的增加,序列模式和最大序列集的数目都减小,即满足最小支持度的序列减少.

󰀁󰀁图4和图5分别显示了产生MSS(最大序列集)和产生SPG(序列模式图)的运行时间和与序列数的关系,它们的时间复杂度都是O(N2),这与前面分析的算法效率是一致的.

第4期󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁石东阳,等:序列模式图构造算法分析与实现295

[2]󰀁RamakrishnanSrikant,RakeshAgrawal.MiningSe󰀁

quentialPatterns:GeneralizationsandPerformance

Improvements[J/OL].http://www.informatik.uni󰀁trier.de/~ley/db/conf/edbt/SrikantA96.html,March1996.

[3]󰀁MohammedJaveedZaki.SPADE:AnEfficientAl󰀁

gorithmforMiningFrequentSequences[J].Machine

图4󰀁运行时间

序列数

Learning,2001,42(1/2):31-60.

[4]󰀁RakeshAgrawal,RamakrishnanSrikant.FastAlgo󰀁

rithmsforMiningAssociationRules[J/OL].http://www.informatik.uni󰀁trier.de/~ley/db/conf/vldb/vldb94󰀁487.html,Setember1994.

[5]󰀁HanJiawei,PeiJian,BehzadMortazavi󰀁Asl,etal.

Freespan:FrequentPattern󰀁projectedSequentialPat󰀁

ternMining[J/OL].http://portal.acm.org/cita󰀁

图5󰀁运行时间

最大序列数

tion.cfm?id=347090.347167,March2000.[6]󰀁PeiJian,HanJianwei,BehzadMortazavi󰀁Asl,etal.

PrefixSpan:MiningSequentialPatternsEfficiently

byPrefix󰀁projectedPatternGrowth[J/OL].http://citeseer.ist.psu.edu/pei01prefixspan.html,Septem󰀁ber2001.

[7]󰀁LinMingyen,LeeSuh󰀁Yin.FastDiscoveryofSe󰀁

quentialPatternsbyMemoryIndexing[J].InProc.of2002DaWaK,2002,150-160.

[8]󰀁MinosGarofalakis,RajeevRastogi,KyuseokShim.

SPRIT:SequentialPatternMiningwithRegularEx󰀁pressionConstraints[J/OL].http://www.infor󰀁matik.uni󰀁trier.de/ley/db/conf/vldb/Garofalak󰀁isRS99.html,September1999.

[9]󰀁吕静,王晓峰,AdjeiOsei,etal.序列模式图及其构

造算法[J],计算机学报,2004,(6):783-786.

~

4󰀁结束语

本文介绍了序列模式图的概念与性质,它是由离散状态的序列集到统一图结构的桥梁,可以将序列模式结果集统一到序列模式图中来,它不仅是序列模式挖掘结果集的最小化表示,还是序列相互关系的初步体现.进一步实现了序列模式图的构造算法,并进行了实验,实验结果与我们的分析完全一致.

参考文献:

[1]󰀁RakeshAgrawal,RamakrishnanSrikant.MiningSe󰀁

quentialPatterns[J/OL].http://www.informatik.

uni󰀁trier.de/~ley/db/conf/icde/AgrawalS95.html,March1995.

AnalysisandImplementationofSequentialPatternGraph

ConstructionAlgorithm

SHIDong󰀁yang,󰀁L󰀁Jing,󰀁CHENWei󰀁ru

(ShenyangInstituteofChemicalTechnology,Shenyang110142,China)

Abstract:󰀁BasedontheefficiencyanalysisofSPGconstructionalgorithm,Construct󰀁SPGwasimple󰀁mentedbyusingC++.Finally,theexperimentalresultwasgiven.TheimplementationofSPGCon󰀁structionalgorithmisveryimportantforthefutureworkbasedonSequentialPatternsGraph.Keywords:󰀁datamining;󰀁sequentialpatterns;󰀁sequentialpatternsgraph