1 Odkrywanie wzorców sekwencjiPrefix Span Odkrywanie wzorców sekwencji z ograniczeniami Uogólnione wzorce sekwencji
2 Odkrywanie wzorców sekwencjiDana jest baza danych sekwencji - znajdź zbiór sekwencji częstych (wzorców sekwencji) A sekwencja : < (ef) (ab) (df) c b > A baza danych elementy posortowane alfabetycznie SID sequence 10
3 Własność Apriori Jeżeli sekwencja S nie jest częsta, to żadna „nad-sekwencja” S również nie jest częsta
4 Podstawowy algorytm – (1)Baza danych jest wielokrotnie przeglądana. W pierwszej iteracji odkrywane są zbiory częste o minimalnym wsparciu, tzw. częste 1-sekwencje Każda kolejna iteracja wykorzystuje do generacji sekwencji kandydujących sekwencje częste odkryte w poprzedniej iteracji Wsparcie sekwencji kandydujących jest obliczane podczas odczytu bazy danych Warunek stopu - nie ma więcej kandydatów lub żaden z kandydatów nie jest częsty
5 Podstawowy algorytm – (2)
6 Wady algorytmów Apriori–LikeOgromny zbiór wygenerowanych kandydatów 1,000 1-elementowych sekwencji daje elementowych kandydatów! Wiele dostępów do bazy danych Trudności w znajdowaniu długich wzorców Bardzo duża liczba małych kandydatów 100-elementowy wzorzec potrzebuje kandydatów!
7 PrefixSpan - (1) Algorytm PrefixSpan składa się z trzech kroków:Znajdowanie wzorców sekwencji o rozmiarze 1 Dzielenie przestrzeni poszukiwań na partycje Analiza podzbiorów sekwencji przechowywanych w partycjach
8 PrefixSpan - (2) znajdowanie wzorców sekwencji o długości 1Jednokrotny odczyt bazy danych sekwencji DS w celu znalezienia wszystkich sekwencji częstych jednoelementowych (tj. o rozmiarze 1) o długości 1. Sekwencje częste o długości 1, które zawierają więcej elementów, np. sekwencja ( (a b) ), są znajdowane w kolejnych krokach algorytmu. Do opisu sekwencji częstych będziemy stosować następującą notację: (sekwencja) : licznik wsparcia. Przykładowo, (a) : 4, oznacza sekwencję (a), której licznik wsparcia wynosi 4. W tym kroku transformujemy również bazę danych sekwencji DS do postaci bazy danych sekwencji DS z której usunięto wszystkie elementy, które nie są częste. Elementami częstymi są tylko i wyłącznie jednoelementowe sekwencje częste o długości 1.
9 PrefixSpan - (3) dzielenie przestrzeni poszukiwań na partycjePrzestrzeń wszystkich wzorców sekwencji można podzielić na n partycji, zwanych projekcyjnymi bazami danych, gdzie n odpowiada liczbie jednoelementowych sekwencji częstych o długości 1 znalezionych w kroku poprzednim. Dowolny wzorzec sekwencji musi rozpoczynać się od jednej ze znalezionych 1-sekwencji częstych (jednoelementowych)
10 PrefixSpan (4) analiza podzbiorów sekwencji przechowywanych w partycjachDla każdej jednoelementowej sekwencji częstej o długości 1 tworzymy projekcyjną bazę danych jej postfiksów Każda projekcyjna baza danych jest następnie rekurencyjnie eksplorowana w celu wygenerowania wzorców sekwencji. Eksploracja polega na znajdowaniu wieloelementowych sekwencji częstych o długości 1 lub sekwencji częstych o długości 2, utworzeniu kolejnych projekcyjnych baz danych dla znalezionych sekwencji częstych, eksploracji tych baz danych, itd.
11 PrefixSpan (5) Krok 1: znajdź 1-elementowe wzorce 1-sekwencji, ,
12 PrefixSpan (6) Rozważmy tylko projekcje a-projekcyjna baza danych PrefixSpan (6) Rozważmy tylko projekcje -projekcje : <(abc)(ac)d(cf)>, <(_d)c(bc)(ae)>, <(_b)(df)cb>, <(_f)cbc> Znajdź wszystkie 2-elementowe sekwencje z prefiksem :
13 PrefixSpan (7)
14 Kompletność algorytmu PrefixSpanSDB SID sequence 10
15 Efektywność algorytmu PrefixSpanBrak generacji zbiorów kandydujących Coraz mniejsze rozmiary projekcji Główny koszt alg. PrefixSpan - konstrukcja kolejnych projekcji Jednym ze sposobów redukcji liczby i rozmiarów projekcyjnych baz danych, generowanych przez algorytm PrefixSpan, jest zastosowanie dwupoziomowego schematu projekcji (ang. bi-level projection)
16 Dwupoziomowy schemat projekcjiPrześledźmy sposób odkrywania sekwencji częstych wykorzystywany w algorytmie PrefixSpan. Pierwszy krok polega na odczycie bazy danych DS w celu znalezienia wszystkich jednoelementowych sekwencji częstych o długości 1: , ,
17 Dwupoziomowy schemat projekcjiMacierz S zawiera informacje o wsparciu wszystkich sekwencji o długości i rozmiarze 2 oraz długości 1 i rozmiarze 2, skonstruowanych w oparciu o jednoelementowe sekwencje częste o długości 1. Elementy macierzy S leżące na przekątnej reprezentują wartości liczników wsparcia sekwencji o długości i rozmiarze 2. Przykładowo, S[a, a]=2 wskazuje, że sekwencja (a a) posiada wsparcie 2. Podobnie, licznik wsparcia sekwencji (b b) wynosi 1. Pozostałe elementy macierzy S reprezentują trzy liczniki wsparcia.
18 Dwupoziomowy schemat projekcjiElement M[a, b] = (x_1, x_2, x_3) reprezentuje wartości licznika wsparcia, odpowiednio, 2-sekwencji ( a b ), 2-sekwencji ( b a) oraz 1-sekwencji ( (a b) ). Przykładowo, element S[a b] = (4, 2, 2) wskazuje, że licznik wsparcia sekwencji (a b) wynosi 4, licznik wsparcia sekwencji (b a) wynosi 2, i licznik wsparcia sekwencji ( (a b) ) wynosi 2. Zauważmy, że elementy macierzy leżące po obu stronach przekątnej zawierają identyczną informację: S[a, b] = S[b, a]. Stąd, do opisu wsparcia sekwencji wystarczy macierz trójkątna.
19 S-matrix S-matrix Wszystkie 2-elem. wzorce zawierają się w S-matrixSDB SID sequence 10
20
21 Zysk z „Bi-level Projection”Więcej wzorców jest znajdowanych w każdym kroku Mniej projekcji Np. dla 53 wzorców. 53 zwykłych projekcji 22 „bi-level projection”
22 Główne cechy alg. PrefixSpanPrefixSpan należy do algorytmów „pattern-growth” Wyszukiwanie jest bardziej skupione i tym samym bardziej efektywne Użycie elementów z algorytmu Apriori - „bi-level projection”
23 Uogólnione sformułowanie problemuWzorzec sekwencji a przyczynowość Dotychczasowe sformułowanie problemu nie uwzględnia ograniczeń czasowych na wzorce sekwencji Sekwencją S nazywać będziemy uporządkowaną listę wyrazów (T1, T2, ..., Tn), gdzie Ti jest zbiorem elementów. Z każdym wyrazem sekwencji Ti sekwencji S jest związany znacznik czasowy ts(Ti), określający czas wystąpienia zdarzenia Ti Wyrazy Ti w sekwencji S są uporządkowane według rosnących wartości ich znaczników czasowych
24 Uogólnione sformułowanie problemuSekwencja: ( (T1): ts(T1)) , (T2): ts(T2) , ..., (Tn): ts(Tn) ) Nowe pojęcia – ograniczenia czasowe: Okno zdarzeń (w-size) – przedział czasu, w ramach którego zbiór transakcji w bazie danych D jest interpretowany jako „pojedyncza” transakcji Minimalny odstęp (min-gap) – minimalny odstęp czasowy pomiędzy kolejnymi wyrazami wzorca sekwencji Maksymalny odstęp (maz-gap) – maksymalny odstęp czasowy pomiędzy kolejnymi wyrazami wzorca sekwencji Wartości ograniczeń definiowane przez użytkownika
25 Uogólnione sformułowanie problemuSekwencja S1 (a1, a2, ..., an) zawiera się w innej sekwencji S2 (b1, b2, ..., bm), jeżeli istnieją takie liczby naturalne i1 u1 < i2 u2 < ... < in un , takie że: Str 73 monografii !!! Sekwencja S DS wspiera sekwencję Q, jeżeli Q zawiera się w sekwencji S ( w myśl powyższej definicji) Wsparciem sekwencji S w bazie danych DS., sup(S, DS), nazywać będziemy iloraz liczby sekwencji w DS, które wspierają S, do liczby wszystkich sekwencji w DS
26 Sformułowanie problemuCelem procesu odkrywania wzorców sekwencji z ograniczeniami czasowymi jest znalezienie wszystkich sekwencji, których wsparcie w bazie danych sekwencji DS jest większe lub równe pewne minimalnej wartości progowej minsup Sekwencje, które spełniają powyższy warunek minimalnego wsparcia nazywamy sekwencjami częstymi lub wzorcami sekwencji Sekwencje częste, które są maksymalne, nazywać będziemy maksymalnymi wzorcami sekwencji
27 Problem – (1) Brak ograniczenia max_gap: dowolna sekwencja X, zawierająca sekwencję S, zawiera również wszystkie podsekwencje sekwencji S W przypadku ograniczenia max-gap powyższe stwierdzenie nie jest prawdziwe! Przykład: załóżmy max-gap = 3 dana sekwencja X = ((1 2): 1, (3 4): 3, (5 6): 5, (7 8): 7) X zawiera sekwencję S = ((1 2): 1, (3 4): 3, (5 6): 5), ale X nie zawiera sekwencji Y = ((1 2): 1, (5 6): 5), która jest podsekwencją sekwencji S
28 Problem – (2) Konsekwencje: brak własności monotoniczności miary wsparcia w przypadku ograniczenia max-gap Brak monotoniczności uniemożliwia generowanie sekwencji kandydujących w oparciu o ideę algorytmu Apriori – ograniczenie przestrzeni możliwych rozwiązań (inaczej mówiąc, ograniczenie przestrzeni generacji potencjalnie częstych sekwencji kandydujących) Rozwiązanie: podsekwencje spójne
29 Problem – (3) Podsekwencja spójna: Sekwencję Y nazywamy podsekwencją spójną sekwencji X, wtedy i tylko wtedy, gdy jest spełniony jeden z następujących warunków: Sekwencja Y powstała z sekwencji X poprzez usuniecie pojedynczego elementu z pierwszego lub ostatniego wyrazu sekwencji X Sekwencja Y powstała z sekwencji X poprzez usuniecie pojedynczego elementy z dowolnego wyrazu sekwencji X, pod warunkiem, ze wyraz ten zawierał więcej niż 1 element Sekwencja Y jest podsekwencją spójną sekwencji Z, która jest podsekwencją spójną sekwencji X
30 Problem – (4) Dowolna sekwencja X, zawierająca sekwencję S, zawiera również wszystkie podsekwencje spójne sekwencji S Konsekwencje: jeżeli sekwencja S jest sekwencją częstą, to wszystkie jej podsekwencje spójne muszą być częste Do znajdowania wzorców sekwencji z ograniczeniami można wykorzystać algorytm GSP (algorytm typu Apriori-like –zmodyfikowana wersja lgorytmu podstawowego)
31 Uogólnione wzorce sekwencji (1)Użytkownicy są często zainteresowani znajdowaniem wzorców sekwencji z pewnymi dodatkowymi ograniczeniami: Ograniczenia elementów „Znajdź wszystkie produkty, które klienci kupują najczęściej zanim kupią DVD” Ograniczenia czasowe „ Znajdź wszystkie produkty, które klienci kupują w ciągu miesiąca od dnia zakupu telewizora”
32 Uogólnione wzorce sekwencji (2)Wzorce sekwencyjne uwzględniające taksonomie elementów i określające zależności kolejnościowe pomiędzy nazwanymi grupami zdarzeń – uogólnione wzorce sekwencji Wzorce sekwencyjne określające zależności kolejnościowe pomiędzy zdarzeniami opisanymi zarówno atrybutami kategorycznymi jak i atrybutami ciągłymi – wielowymiarowe (ilościowe) wzorce sekwencji