第四章序列模式分析4

数据挖掘第四章：序列模式分析本章内容4.1序列模式的基本概念4.2GSP算法4.3PrefixSpan算法基本要求：掌握序列模式的基本概念，掌握GSP、PrefixSpan两种典型序列模式挖掘算法4.1序列模式的基本概念序列模式(sequentialpattern)的概念最早是由Agrawal和Srikant提出的，序列模式分析旨在寻找事件间在顺序上的相关性。例子：凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒。两年前购买了Ford牌轿车的顾客，很可能在今年采取贴旧换新的购车行动。购买了自行车的客户中，70%的客户会在两个月后购买打气筒。典型应用•客户购买行为模式预测•Web访问模式预测•疾病诊断•自然灾害预测•DNA序列分析4.1序列模式的基本概念序列模式(sequentialpattern)的概念最早是由Agrawal和Srikant提出的，序列模式分析旨在寻找事件间在顺序上的相关性。例子：凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒。两年前购买了Ford牌轿车的顾客，很可能在今年采取贴旧换新的购车行动。购买了自行车的客户中，70%的客户会在两个月后购买打气筒。典型应用E-learning中的应用三角形的定义三角形内角和定理内角和的定义外角和的定义三角形外角和定理学习依赖关系4.1序列模式的基本概念typhoonflood,landslidetyphoonflood,landslideAseriesofdailynewspaperarticlestyphoon(flood,landslide)事件中的例子4.1序列模式的基本概念TransactionTimeCustomerItemsBoughtJune20,199410:13amJ.BrownJuice,CokeJune20,199411:02amF.ZappaBrandyJune20,199411:47amJ.BrownBeerJune20,19942:32pmB.MooreBeerJune21,19949:22amJ.BrownWine,Water,CiderJune21,19943:19pmJ.MitchellBeer,Gin,CiderJune21,19945:27pmB.AdamsBeer(Diapers?)June21,19946:17pmB.MooreWine,CiderJune22,199410:34amB.AdamsBrandyJune22,19945:03pmB.MooreBrandy交易数据数据库交易数据数据库（按顾客与时间排序）CustomerTransactionTimeItemsBoughtB.AdamsJune21,19945:27pmBeerB.AdamsJune22,199410:34amBrandyJ.BrownJune20,199410:13amJuice,CokeJ.BrownJune20,199411:47amBeerJ.BrownJune21,19949:22amWine,Water,CiderJ.MitchellJune21,19943:19pmBeer,Gin,CiderB.MooreJune20,19942:32pmBeerB.MooreJune21,19946:17pmWine,CiderB.MooreJune22,19945:03pmBrandyF.ZappaJune20,199411:02amBrandy4.1序列模式的基本概念序列数据库CustomerCustomerSequenceB.Adams(Beer)(Brandy)J.Brown(Juice,Coke)(Beer)(Wine,Water,Cider)J.Mitchell(Beer,Gin,Cider)B.Moore(Beer)(Wine,Cider)(Brandy)F.Zappa(Brandy)序列模式SequentialPatternswithSupport40%CustomersSupportingit(Beer)(Brandy)B.Adams,B.Moore(Beer)(Wine,Cider)J.Brown,B.Moore4.1序列模式的基本概念4.1序列模式的基本概念序列模式：给定一个由不同序列组成的集合，其中每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式就是频繁子序列，即该子序列在序列集中的出现频率不低于最小支持度阈值。4.1序列模式的基本概念SequenceDatabaseSequenceElement(Transaction)Event(Item)CustomerPurchasehistoryofagivencustomerAsetofitemsboughtbyacustomerattimetBooks,diaryproducts,CDs,etcEventdataHistoryofeventsgeneratedbyagivensensorEventstriggeredbyasensorattimetTypesofalarmsgeneratedbysensorsGenomesequencesDNAsequenceofaparticularspeciesAnelementoftheDNAsequenceBasesA,T,G,CSequenceE1E2E1E3E2E3E4E2Element(Transaction)Event(Item)4.1序列模式的基本概念形式化表示：项目集(Itemset)是各种项目组成的集合。序列(Sequence)是不同项目集的有序排列，序列s可以表示为s=s1s2…sl，sj(1=j=l)为项目集，也称为序列s的元素。序列的元素(Element)可表示为(x1，x2，…，xm)，xk(1=k=m)为不同的项目，如果一个序列只有一个项目，则括号可以省略。同一元素中的项目间排列没有顺序，为了表达的唯一性，同一个元素内部的项目按字典序排列。一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列。4.1序列模式的基本概念4.1序列模式的基本概念形式化表示：设=a1a2…an，=b1b2…bm，如果存在整数1=j1j2…jn=m，使得a1bj1，a2bj2，…，anbjn，则称序列为序列的子序列（为的超序列），又称序列包含序列，记为。DatasequenceSubsequenceContain?{2,4}{3,5,6}{8}{2}{3,5}Yes{1,2}{3,4}{1}{2}{2,4}{2,4}{2,5}{2}{4}4.1序列模式的基本概念给定一个n-序列，其中包含了多少个k-子序列?{ab}{cde}{f}{ghi}n=9k=4:Y__YY___Y{a}{de}{i}12649kn4.1序列模式的基本概念形式化表示：序列在序列数据库S中的支持度为序列数据库S中包含序列的序列个数，记为Support()。给定支持度阈值，如果序列在序列数据库中的支持度不低于，则称序列为序列模式。长度为l的序列模式记为l-模式。4.1序列模式的基本概念序列模式挖掘：给定一个序列集，找出其中的所有频繁子序列序列数据库序列:(ef)(ab)(df)cb一个元素是一个项集，元素中的项目是无序的，可按字母序排列。设支持度阈值min_sup=2,(ab)c是序列模式SIDsequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40eg(af)cbc4.1序列模式的基本概念ItemItemsetTransaction以Customer_Id及TransactionTime排序4.1序列模式的基本概念Sequence(30)(90)issupportedbycustomer1and430(4070)issupportedbycustomer2and44.1序列模式的基本概念序列模式的局限性：时间限制–相邻事件之间最大与/或最小的时间间隔–例如:购买‘Foundation’,然后购买‘FoundationandEmpire’与‘Ringworld’应在三个月之内.分类体系4.1序列模式的基本概念Example:AcustomerwhoboughtFoundation,thenPerfectSpy,wouldsupportthefollowingpatterns:•Foundation,thenPerfectSpy•Asimov,thenPerfectSpy•ScienceFiction,thenLeCarre4.1序列模式的基本概念序列模式挖掘问题描述输入–对于序列数据库D:•I={i1,i2,…,in}是所有项目的集合•每个序列都是按时间排列的一组交易•每个交易包含以下字段:sequence-id,transaction-id,transaction-timeandasetofitems.问题–找到满足最小支持度的所有序列模式4.1序列模式的基本概念主要算法类Apriori算法•GSP(GeneralizedSequentialPatterns)：Srikant&Agrawal[EDBT’96]•SPADE：Zaki[MachineLeanining’00]基于模式增长（Pattern-Growth-based）的算法•PrefixSpan&FreeSpan：Hanetal.KDD’00;Pei,etal.[ICDE’01]本章内容4.1序列模式的基本概念4.2GSP算法4.3PrefixSpan算法4.2GSP算法Apriori性质如果序列S是非频繁的,则S的所有超序列都是非频繁的hb是非频繁的，则hab与(ah)b都是非频繁的SIDsequence10(bd)cb(ac)20(bf)(ce)b(fg)30(ah)(bf)abf40(be)(ce)d50a(bd)bcb(ade)设支持度阈值min_sup=24.2GSP算法GSP算法描述扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集。根据长度为i的种子集Li，通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。重复第二步，直到没有新的序列模式或新的候选序列模式产生为止L1C2L2C3L3C4L4……4.2GSP算法候选序列模式步骤连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。L1C2L2C3L3C4L4……4.2GSP算法GSP算法实现生成候选序列模式：生成尽可能少候选模式，同时保证结果完整性计算候选序列模式的支持度：找出序列中元素出现的位置实现分类体系4.2GSP算法生成候选序列模式目标:给定所有的(k-1)-序列,生成所有的候选k-序列模式算法:•连接阶段:Lk-1相互连接。S1能够连接S2，当(S1–firstitem)与(S2–lastitem)相同•剪切阶段:删除包含“不满足最小支持度要求的(k-1)子序列”的候选序列模式。4.2GSP算法例子：从长度为3的序列模式产生长度为4的获选序列模式。SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruni