一个基於长度二序列矩阵之有效率的序列型样挖掘演算法

1、一個基於長度二序列矩陣之有效一個基於長度二序列矩陣之有效率的序列型樣挖掘演算法率的序列型樣挖掘演算法An Efficient Sequential Pattern Mining Algorithm Based on a 2-Sequence Matrix Presented by Chia-Ying HsiehAdvisor: Prof. Don-Lin YangE-Mail: .tw2Outline nIntroductionnBackground nRelated WorknMotivationnPurpose nESPEnExperiment nConclu

2、sions and Future Work3Introduction nData mining techniques have been developed many years.nRecently, sequential pattern mining becomes an important issue in finding sequential information from huge databases. It is interesting and has broad applications in business, bioinformatics, web mining, compu

3、ter intrusion detection and so on. nWe would like to develop an more efficient sequential pattern mining algorithm based on a 2-sequence matrix.4BackgroundnData miningnAssociation rulenThe association rule mining task is the job of finding which attributes “go-together” nFSE(2006)nSequential pattern

4、n Sequential patterns mining consider the sequences of events occurrences and an item can appear many times in a sequence. nAprioriAll(1994), GSP (1996), PrefixSpan (2001)5Related Work (1/5)nFSE (Fast Support Enumeration)nUse to mining association rules without the need of predetermining the minimum

5、 support in the candidate generationnOnly scan the transaction database oncenNeed more memory space6Related Work (2/5)nMain categories in sequential pattern mining algorithms nCandidate generate-and-test approachn AprioriAll, GSPn Divide-and-conquer approachnPrefixSpan 7Related Work (3/5)nGSPnCandid

6、ate generate-and-test approach nMultiple passes over the database nGenerate huge number of candidates when a sequence database is largenDifficult to handle long sequential transactions of databases. 8Related Work (4/5)nPrefixSpannDivide-and-conquer approach nProjected-database may be larger than the

7、 original database nMultiple scans of the projected-database 9Related Work (5/5)ApproachAlgorithmNo. of DB scansIncremental itemsCandidate Generate-and-TestGSPn*No Divide-and-conquer approach PrefixSpan1No Support EnumerationFSE1NoESPE(Efficient Sequential Pattern Enumerate)1Yes 10MotivationnScan da

8、tabasenMultiple database scannGenerate candidatenGenerate all possible candidate sequencesnPre-determine the minimal supportn Hard to determine suitable thresholdsnReduce memory spacenIncremental mining11PurposenNo multiple database scannESPE only scans the database once nNo need to generate all can

9、didates n ESPE can effective execute and reduce the waste of memory spacenCan deal with long sequences nNo need to predetermine the minimal support nESPE finds all interesting patterns nFind rules based on users demand effectively nUsers can choose information they really wantnIncremental process of

10、 new items and transactions12Problem Statement nSequence nAn ordered list of itemsets nl-sequence nThe length of sequence l is the number of items. For example, ABC is a 3-sequence nMinimum supportnPartition nWe partition a sequence into two sections X and Y nX is the candidate 2-sequence (PX)nY is

11、the remaining sequence of PX (PY ).x.x x: x.x.x x Y and xX is,That sequence remaining is Y sequence-2 candidate is X: denote we,.xxxx sequence aFor :1 43214321n321nnxxasYXDefinition13ESPE algorithm (1/4)14Enumerate 2-sequence (1/3)nPurposenAvoid generating too many candidates to run out of memory n

12、Can deal with long sequences nThis method is like FSEs enumeration method nOnly generate 2-sequences and use Definition 1 to record sequences.x.x x: x.x.x x Y and xX is,That sequence remaining is Y sequence-2 candidate is X: denote we,.xxxx sequence aFor :1 43214321n321nnxxasYXDefinition15Enumerate

13、2-sequence (2/3)31213 =31:213312 311 313 3121 3123 3113 3121331213 =32:13321 323321331213 =31:331213 =3331213 =12:13121 123121331213 =11:311331213 =1331213 =21:321331213 =23nOur method only enumerates 8 sequencesn Traditional method enumerates 23 sequences16Enumerate 2-sequence (3/3)17Storage effect

14、iveness (1/3)nPurposenTo store and retrieve the results efficiently nUse Definition2 to compute the indexnThe 2-sequentces are 124443 2) 1(:3) 1(:2:1 thensequence,-2 a is xy If2yxindexyxcaseyxxindexyxcaseyxindexyxcaseDefinition2) 12(1:32indexyxcase1644:1indexyxcase153) 14(4:2indexyxcase18Storage eff

15、ectiveness (2/3)15The Matrix requires to recalculate the index19Storage effectiveness (3/3)nInterlaced Matrix20Encode the sequences (1/2)nPurpose n Reduce the memory space and search timenUse Interlaced Matrix (Definition 2) method to encode PY2) 1(:3) 1(:2:1 thensequence,-2 a is xy If2 yxindexyxcas

16、eyxxindexyxcaseyxindexyxcaseDefinition21Encode the sequences (2/2)Length1234567EncodeIndexitem add”-”IndexBydefinition2Length2+Length1Length2+Length2Length2+Length2+Length1Length2+Length2+Length2Length2+Length2+Length2+Length1Example : a sequences PY is 12113 2,1,-3 12= 1+(2-1) 2=211= 1*1=13= -322Us

17、er on-demandnPurposenBe able to retrieve the result quickly based on the users demandnUsers can input min_sup, length, or specified-item23A Simple Example (1/3)SIDSequence13 1 2 1 321 2 3 233 1 2 341 2 1 3 1SIDSequenceAll of the 2-sequences13 1 2 1 33 1:2 1 33 2:1 33 31 2:1 31 1:31 32 1:32 3SIDIndex

18、13 1:2 1 3:73 2:1 3:83 3:91 2:1 3:21 1:3:11 3:52 1:3:32 3:6CodeSupport PY1(11)1Length=1-3:12(12)1Length=1-1:1 -3:1Length=25:13(21)1Length=1-3:14(22)Length=15(13)1Length=16(23)Length=17(31)1Length=1-1:1 -2:1 -3:1Length=22:1 6:1 (5):1Length=32,-3:18(32)1Length=1-1:1 -3:1Length=25:19(33)1Length=124A Si

19、mple Example (2/3)SIDIndex21 2:3 2:21 3:2:52 3:2:62 2:43 2:833 1:2 3:73 2:3:83 3:91 2:3:21 3:52 3:641 2:1 3 1:21 1:3 1:11 3:1:52 1:3 1:32 3:1:63 1:7SIDSequence13 1 2 1 321 2 3 233 1 2 341 2 1 3 1SIDsequenceAll of the 2-sequences21 2 3 21 2:3 21 3:22 3:22 23 233 1 2 33 1:2 33 2:33 31 2:31 32 341 2 1

20、3 11 2:1 3 11 1:3 11 3:12 1:3 12 3:13 125A Simple Example (3/3)CodeSupport PY1(11)2Length=1-1:1 -3:1Length=27:12(12)4Length=1-1:2 -2:1 -3:4Length=21:1 5:2 7:1 8:1Length=35,-1:13(21)2Length=1-1:1 -3:1Length=27:14(22)1Length=15(13)4Length=1-1:1 -2:16(23)4Length=1-1:1 -2:17(31)3Length=1-1:1 -2:2 -3:2Le

21、ngth=22:1 6:2 (5):1Length=32,-3:18(32)3Length=1-1:1 -3:2Length=25:19(33)2Length=1If min_sup=3code=2,5,6,7,8If min_length=4PYs length=2If specify sequence is 21=code=326Experiment (1/3)nScalability test for various min_sup thresholds 27Experiment (2/3)nScalability test for various transactions per cu

22、stomer 28Experiment (3/3)nScalability test for various min_sup thresholds Compare with FSE29Conclusions (1/2)nWe purpose a new method, ESPE, to mine sequential patterns without predetermining the minimal support.nESPE enumerates all 2-sequences by scanning the database only once, uses simple mathematical equations to compute all indexes of 2-sequences and encodes remaining se