序列模式-2.pptVIP

AprioriSome It generates candidates for a pass using only the large sequences found in the previous pass. Divided into 2 phase: forward vs. backward Advantage: Reduce counting time wasted in counting non-maximal ones. Next function AprioriSome (cont.) //Forward Phase L1 = {Large 1-sequences}; // Result of the litemset phase C1 = L1; // so that we have a nice loop condition Last =1; // we last counted Clast for (k=2; Ck-1≠φ and Llast≠φ;k++) do begin if (Lk-1 known) then Ck=New candidates generated from Lk-1; Else Ck =New candidates generated from Ck-1; if (k==next(last)) then begin Foreach customer-sequence c in the database do Increment the count of all candidates in Ck that are contained in c Lk=Candidates in Ck with minimum support. Last=k; end end AprioriSome (cont.) //Backward Phase for (k--; k=1; k-- ) do if (Lk was not determined in the forward phase) then begin Delete all sequences in Ck contained in some Li, ik; foreach customer-sequence c in DT do Increment the count of all candidates in Ck that are contained in c. Lk=Candidates in Ck with minimum support. end else begin // Lk already known Delete all sequences in Lk contained in some Li, ik; end end Answer=UkLk; Ck Lk C1 L1 f(k)=2k Example - AprioriSome C2 L3 L2 C3 C5 C4 L4 So far, we covered Read-based Write-based Point-based Association Mining Apriori[AgSr94] VIPER[SHSB00] FPGrowth [HaPe00] Sub-Graph Mining AGM[PKDD’00] FSG[ICDM’01] Mofa[ICDM’02] gSpan[ICDM’02] Sequential Pattern Discovery GSP[AgSr96] PrefixSpan [PHPC01] Iceberg Cube Apriori[AgSr94] BUC[BeRa99], H-cubing [HPDW01] PrefixSpan: Example of Write-based Method SID sequence 10 a(abc)(ac)d(cf) 20 (ad)c(bc)(ae) 30 (ef)(ab)(df)cb 40 eg(af)cbc SDB Length-1 sequential patterns a, b, c, d, e, f a-projected database (abc)(ac)d(cf) (_d)c(bc)(ae) (_b)(df)cb (_f)cbc Length-2 sequential patterns aa, ab, (ab), ac, ad, af Having prefix a Having prefix aa aa-proj.