mining sequential patterns by prefix projections ( 续 ).ppt

PrefixSpan﹕Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth 學生 : 907737 張資昊 907747 蔡明成 指導老師 : 劉俞志 名詞解釋 items： 在顧客交易資料庫中的一種產品，稱之為一個item。 itemset： 由一個以上的items所組成的一個非空集合，其中表示為一個item。 sequence and element： 由一個以上的itemset所組成一個有順序性的序列。其中表示為一個itemset，也就是element。 length：一個sequence中所存在的item數量。 l - sequence：長度為l 的sequence。 名詞解釋(續) subsequence and super sequence：定義sequence α = 〈aa…a〉, sequence β = 〈bb…b〉，如果存在整數1?jj…j?m，使得a?b,a?b,…,a?b，則我們稱α為β的subsequence，而β為α的super sequence或稱為β contain α。本文中標示為α β。 sequence database：由一群〈sid, s〉紀錄所構成的集合，其中sid為sequence_id，且s為一sequence。 名詞解釋(續) (frequent) sequential pattern：若sequence database存在一個sequence α使得support(α) ? ξ(a positive integer as the support threshold)，則我們稱之為(frequent) sequential patterns。 l - pattern：長度為l的sequential pattern。 support：一個sequence α在sequence database S中的support，就是此database中containing α的tuple數量。本文中標示為support(α) 目的 Sequential pattern mining在資料挖礦中是一個重要的問題，之前的做法大多數都是以Apriori演算法為基礎，但此方法在資料庫龐大或sequential pattern大量與長度較長時，其效能將出現問題。在本篇文章中，作者提出一個新的方法叫做PrefixSpan - (Prefix-projected Sequential Pattern)，它不僅可以大大地減少candidate subsequence的產生，更可以大量地降低projected database所需的空間，使得程序變得有效率。此外，在大量序列的資料庫中挖掘sequential pattern，其效能勝於Apriori-based GSP演算法和FreeSpan，改善了以往效能不佳的問題。 三種演算法比較 GSP GSP是一個典型的Apriori-like mothod，它採用了multiple-pass與candidate-generation-and-test 的方式在sequential pattern mining上。 主要步驟如下﹕ 先掃描出所有length-1的frequent sequence，將它存於seed set之中(在此seed set之中即為sequential pattern)，接著做 Step1(generate)﹕利用seed set內的sequence，組合成length加1的candidate sequences。 Step2(test)﹕測試各個candidate sequence support是否大於min_support，若大於，則存此candidate sequence於seed set之中。 不斷重複上述兩個Step，直到沒有candidate大於min_support，則此seed set內的資料即為sequential pattern。過程如下﹕ GSP(續) GSP(續)Example 先掃描找出length-1的frequent sequence﹕abcdef放入seed set中(seed set = a,b,c,d,e)，接著產生length-2的candidate﹕aaab…afbabb…bf…fa…ff(ab)(ac)..(af)(bc)(bd)…(bf)…(ef)，接著測試各個candidate是否大於min_support，若大於則加如seed set中，接著找length-3的candidate…依此類推，最後seed set中即為sequential patter。 GSP