数据挖掘2015最新精品课程完整课件(第7讲)---挖掘复杂类型频繁模式

挖掘复杂类型频繁模式主要内容序列模式挖掘频繁子图挖掘序列模式挖掘3序列挖掘或称序列模式挖掘，是指从序列数据库中发现蕴涵的序列模式。时间序列分析和序列模式挖掘有许多相似之处，在应用范畴、技术方法等方面也有很大的重合度。但是，序列挖掘一般是指相对时间或者其他顺序出现的序列的高频率子序列的发现，典型的应用还是限于离散型的序列。序列模式挖掘最早是由Agrawal等人提出的，它的最初动机是针对带有交易时间属性的交易数据库中发现频繁项目序列以发现某一时间段内客户的购买活动规律。近年来序列模式挖掘已经成为数据挖掘的一个重要方面，其应用范围也不局限于交易数据库，在DNA分析等尖端科学研究领域、Web访问等新型应用数据源等众多方面得到针对性研究。概述频繁序列(frequentsequentialpattern)源自频繁项集序列模式挖掘的应用购物序列医疗处方股市通话序列Web点击序列程序执行序列DNA序列和基因结构序列模式挖掘给定一个序列的集合，挖掘全部的频繁子序列模式Asequencedatabase每个元素包含了项目的集合，元素内的项目没有顺序。a(bc)dc是a(abc)(ac)d(cf)的子序列给定最小支持度阈值min_sup=2,(ab)c是频繁序列模式如果t中每个有序元素都是s中一个有序元素的子集，则称序列t是另一个序列s的子序列。SIDsequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40eg(af)cbcAsequence:(ef)(ab)(df)cb子序列（包含）一个序列a1a2…an是另一序列的子集b1b2…bm(m≥n)当且仅当存在整数i1i2…in使得a1bi1,a2bi1,…,anbin2020年2月24日星期一DataMining:ConceptsandTechniques6DatasequenceSubsequenceContain?{2,4}{3,5,6}{8}{2}{3,5}Yes{1,2}{3,4}{1}{2}No{2,4}{2,4}{2,5}{2}{4}Yes序列模式的Apriori性质如给定最小支持度阈值min_sup=2,hb是非频繁的,则hab和(ah)b也不是频繁的a(bd)bcb(ade)50(be)(ce)d40(ah)(bf)abf30(bf)(ce)b(fg)20(bd)cb(ac)10SequenceSeq.ID若序列S不频繁，则S的超序列(super-sequences)也不再频繁。2020年2月24日星期一8序列挖掘—数据源的形式表6-1带交易时间的交易数据源示例客户号（Cust_id）交易时间（Tran_time）物品（Item）11June25’99June30’993090222June10’99June15’99June20’9910，203040，60，703June25’9930，50，70444June25’99June30’99July25’993040，70905June12’9990表6-2顾客序列表示例客户号（Cust_id）顾客序列（CustomerSequence）1（30）（90）2（10，20）（30）（40，60，70）3（30，50，70）4（30）（40，70）（(90)5（90）带交易时间的交易数据库的典型形式是包含客户号（Customer-id）、交易时间（Transaction-Time）以及在交易中购买的项（Item）等的交易记录表。表6-1给出了一个这样数据表的示例。这样的数据源需要进行形式化的整理，其中一个理想的预处理方法就是转换成顾客序列，即将一个顾客的交易按交易时间排序成项目序列。例如表6-2给出了表6-1对应的所有顾客序列表。2020年2月24日星期一9序列挖掘—数据源的形式(续)表6-2顾客序列表示例操作系统及其系统进程调用是评价系统安全性的一个重要方面。通过对正常调用序列的学习可以预测随后发生的系统调用序列、发现异常的调用。因此序列挖掘是从系统调用等操作系统审计数据中发现有用模式的一个理想的技术。表6-3给出了一个系统调用数据表示意，它是利用数据挖掘技术进行操作系统安全性审计的常用数据源。表6-3系统进程调用数据示例进程号（Pro_id）调用时间（Call_time）调用号（Call_id）74474410699106974410699-104：01：10：3004：01：10：3104：01：10：3204：01：10：3404：01：10：3504：01：10：3804：01：10：3904：01：10：4023144245816216表6-4系统调用序列数据表示例进程号（Pro_id）调用序列（Call_sequence）74410699（23，14，81）（14，24，16）（4，5，62）GSP—GeneralizedSequentialPatternMining算法流程数据库中每个项目都作为1-候选序列for每一层(即k-序列模式)do扫描数据库，计算每个候选序列的支持度连接k-频繁序列生成(k+1)-候选序列。直到没有任何频繁序列或候选序列产生为止发现长度为1的序列模式所有单项目序列都是初始候选序列a,b,c,d,e,f,g,h扫描一遍数据库，计算支持度a(bd)bcb(ade)50(be)(ce)d40(ah)(bf)abf30(bf)(ce)b(fg)20(bd)cb(ac)10SequenceSeq.IDmin_sup=2CandSupa3b5c4d3e3f2g1h1GSP算法挖掘流程abcdefghaaab…afbabb…ff(ab)…(ef)abbaabababaabab…abba(bd)bc…(bd)cba1stscan:8cand.6length-1seq.pat.2ndscan:51cand.19length-2seq.pat.10cand.notinDBatall3rdscan:46cand.19length-3seq.pat.20cand.notinDBatall4thscan:8cand.6length-4seq.pat.5thscan:1cand.1length-5seq.pat.Cand.cannotpasssup.thresholdCand.notinDBatalla(bd)bcb(ade)50(be)(ce)d40(ah)(bf)abf30(bf)(ce)b(fg)20(bd)cb(ac)10SequenceSeq.IDmin_sup=2GSP算法其中，产生候选序列模式主要分两步：连接阶段：如果去掉序列模式S1的第一个项目与去掉序列模式S2的最后一个项目所得到的序列相同，则可以将S1于S2进行连接，即将S2的最后一个项目添加到S1中。剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。候选序列模式的支持度计算按照如下方法进行：对于给定的候选序列模式集合C，扫描序列数据库DT，对于其中的每一条序列d，找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数。14GSP算法举例下表演示了从长度为3的序列模式产生长度为4的候选序列模式的过程。在连接阶段，序列（1，2），3可以与2，（3，4）连接，因为（*，2），3与2，（3，*）是相同的，两序列连接后为（1，2），（3，4）；（1，2），3与2，3，5连接，得到（1，2），3，5。剩下的序列是不能和任何长度为3的序列连接的，比如（1，2），4不能与任何长度为3的序列连接，这是因为其他序列没有（2），（4，*）或者（2），（4）（*）的形式。GSP算法举例在修剪阶段（1，2），3，5将被剪掉，这是因为1，3，5并不在L3中，而（1，2），（3，4）的长度为3的子序列都在L3因而被保留下来。SequentialpatternsWithLength3Candidate4-SequencesAfterJoinAfterPruning（1，2），3（1，2），41，（3，4）（1，3），52，（3，4）2，3，5（1，2），（3，4）（1，2），3，5（1，2），（3，4）候选-验证方式存在的问题产生大量的候选序列模式.特别是2-候选序列需要多次扫描数据库每次扫描数据库，候选序列的长度加1挖掘长序列模式的效率低下短序列模式的数量与序列模式的长度间呈指数关系前缀与后缀投影a,aa,a(ab),a(abc)是序列a(abc)(ac)d(cf)的前缀给定序列a(abc)(ac)d(cf)PrefixSuffix(Prefix-BasedProjection)a(abc)(ac)d(cf)aa(_bc)(ac)d(cf)ab(_c)(ac)d(cf)基于前缀投影的序列模式挖掘prefixspan算法韩家炜在2004年提出的序列模式算法Step1:发现1-频繁序列a,b,c,d,e,fStep2:整个搜索空间可以划分为如下6个子集:以a为前缀的序列;以b为前缀的序列;…以f为前缀的序列SIDsequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40eg(af)cbcMin_sup=2挖掘以a为前缀的序列模式只需要考虑a的投影数据库a-投影数据库:(abc)(ac)d(cf)(_d)c(bc)(ae)(_b)(df)cb(_f)cbca-投影数据库中局部频繁项目a:2,b:4,_b:2,c:4,d:2,f:2以a为前缀的2-频繁序列模式aa:2,ab:4,(ab):2,ac:4,ad:2,af:2SIDsequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40eg(af)cbc挖掘以a为前缀的序列模式挖掘如下6个子集aa-投影数据库;ab-投影数据库;(ab)-投影数据库;ac-投影数据库;ad-投影数据库;af-投影数据库。挖掘以aa为前缀的序列模式以aa为前缀的子序列:(_bc)(ac)d(cf)和(_e).在aa-投影数据库中没有任何频繁项集,故没有频繁序列模式.挖掘以ab为前缀的序列模式ab-投影数据库:(_c)(ac)d(cf)(_c)(ae)c.局部频繁项目a:2,_c:2,c:2以ab为前缀的3-序列模式aba:2,a(bc):2,abc:2aba-投影数据库:(_c)d(cf),(_e).a(bc)-投影数据库(ac)d(cf),(ae),4-序列模式a(bc)a:2.abc-投影数据库:d(cf).PrefixSpan算法SIDsequence10a(abc)(ac)d(cf)20(ad)c(bc)(ae)30(ef)(ab)(df)cb40eg(af)cbcSDBLength-1sequentialpatternsa,b,c,d,e,fa-projecteddatabase(abc)(ac)d(cf)