Częste wydobywanie poddrzewa

W informatyce częsta eksploracja poddrzew to problem znalezienia w danej bazie danych wszystkich wzorców, których wsparcie (metryka związana z liczbą jej wystąpień w innych poddrzewach) przekracza zadany próg . Jest to bardziej ogólna postać problemu poddrzewa maksymalnej zgodności.

Definicja

Częste eksplorowanie poddrzew to problem polegający na próbie znalezienia wszystkich wzorców, których „wsparcie” przekracza określony przez użytkownika poziom, gdzie „wsparcie” jest obliczane jako liczba drzew w bazie danych, które mają co najmniej jedno poddrzewo izomorficzne do dany wzór.

Definicja formalna

Problem częstego eksploracji poddrzew został formalnie zdefiniowany jako:

Biorąc pod uwagę próg minfreq , klasa drzew , przechodnia relacja poddrzewa między drzewami $P$$\ Displaystyle P \ preceq T}$ między drzewami $Displaystyle P, T \ w {\ mathcal {C}}}$ , skończony zbiór drzew $}} \ subseteq {\ mathcal {C}}}$ , częstym problemem eksploracji poddrzewa jest problem znalezienia wszystkie drzewa $\$$mathcal {C}}}$ takie, że żadne dwa drzewa w nie izomorficzne i

${\ Displaystyle \ forall P \ in {\ mathcal {P}}: \ quad \ operatorname {freq} (P, {\ mathcal {D}}) = \ suma \ nolimits _ {T \ in {\ mathcal {D} }} d (P, T) \ geq \ operatorname {minfreq} ,}$

gdzie d

${\ Displaystyle \ forall T \ w {\ mathcal {C}}: \ quad d (P ', T) \ geq d (P, T).}$

funkcją antymonotoniczną taką, że jeśli ${\ Displaystyle P'\ preceq P}$ , to

TreeMiner

W 2002 roku Mohammed J. Zaki przedstawił TreeMiner, wydajny algorytm do rozwiązywania częstego problemu eksploracji poddrzewa, który wykorzystywał „listę zakresów” do reprezentowania węzłów drzewa i który był przeciwieństwem PatternMatcher, algorytmu opartego na dopasowywaniu wzorców.

Definicje

Indukowane poddrzewa

Poddrzewo ${\ Displaystyle S = (V_ {s}, E_ {s})}$ jest indukowanym poddrzewem ${\ Displaystyle T = ( V, E)}$ wtedy i tylko wtedy, gdy ${\ Displaystyle V_ {s} \ subseteq V}$ i ${\ Displaystyle E_ {s} \ subseteq E}$ . Innymi słowy, dowolne dwa węzły w S, które są bezpośrednio połączone krawędzią, są również bezpośrednio połączone w T. Dla dowolnego węzła A i B w S, jeśli węzeł A jest rodzicem węzła B w S, to węzeł A musi być również rodzic węzła B w T.

Osadzone poddrzewa

Poddrzewo $Displaystyle$$_ V, E)}$ poddrzewem wtedy i tylko wtedy, gdy ${\ Displaystyle V_ {s} \ subseteq V}$ a dwa węzły końcowe dowolnej krawędzi w S znajdują się na tej samej ścieżce od korzenia do węzła liścia w T. Innymi słowy, dla dowolnego węzła A i B w S, jeśli węzeł A jest rodzicem węzła B w S, to węzeł A musi być przodkiem węzła B w T. Wszelkie indukowane poddrzewa są również osadzonymi poddrzewami, a zatem koncepcja osadzonych poddrzew jest uogólnieniem indukowanych poddrzew. Jako takie osadzone poddrzewa charakteryzują ukryte wzorce w drzewie, których brakuje w tradycyjnym eksploracji indukowanych poddrzew. Poddrzewo o rozmiarze k jest często nazywane k-poddrzewem.

Wsparcie

Wsparcie dla poddrzewa to liczba drzew w bazie danych zawierającej to poddrzewo. Poddrzewo jest częste, jeśli jego wsparcie jest nie mniejsze niż próg określony przez użytkownika (często oznaczany jako minsup). Celem TreeMiner jest znalezienie wszystkich osadzonych drzew podrzędnych, które mają przynajmniej minimalne wsparcie.

Ciągowa reprezentacja drzew

Istnieje kilka różnych sposobów kodowania struktury drzewa. TreeMiner wykorzystuje łańcuchowe reprezentacje drzew do wydajnej manipulacji drzewami i liczenia podpór. Początkowo łańcuch jest ustawiony na ${\ displaystyle \ varnothing}$ . Zaczynając od korzenia drzewa, etykiety węzłów są dodawane do łańcucha w kolejności wyszukiwania od początku do końca. -1 jest dodawane do łańcucha za każdym razem, gdy proces wyszukiwania cofa się od dziecka do rodzica. Na przykład proste drzewo binarne z korzeniem oznaczonym jako A, lewy element potomny oznaczony jako B i prawy element potomny oznaczony jako C może być reprezentowany przez łańcuch AB -1 C -1.

Klasa równoważności prefiksu

Mówi się, że dwa k-poddrzewa należą do tej samej klasy równoważności przedrostków, jeśli ich reprezentacja łańcuchowa jest identyczna aż do (k-1)-tego węzła. Innymi słowy, wszystkie elementy w klasie równoważności przedrostków różnią się tylko ostatnim węzłem. Na przykład dwa drzewa z reprezentacją łańcuchową AB -1 C -1 i AB -1 D -1 należą do klasy równoważności prefiksu AB z elementami (C, 0) i (D, 0). Element klasy prefiksu jest określony przez etykietę węzła połączoną z pierwszym indeksem głębokości węzła, do którego jest dołączony, od 0. W tym przykładzie oba elementy prefiksu klasy AB są dołączone do korzenia, który ma indeks równy 0.

Zakres

$l$ przez parę liczb, gdzie i r to minimalny i maksymalny indeks węzła w poddrzewie zakorzenionym , l jest indeksem A, a r jest indeksem najbardziej wysuniętego na prawo liścia wśród potomków A. Jako taki indeks dowolnego potomka A musi leżeć w zakresie A, co będzie bardzo użyteczną właściwością przy liczeniu obsługa poddrzew.

Algorytm

Pokolenie kandydatów

Częste wzorce poddrzew są zgodne z właściwością antymonotoniczną. Innymi słowy, wsparcie k-poddrzewa jest mniejsze lub równe wsparciu jego (k-1)-poddrzew. Tylko super wzorce znanych częstych wzorców mogą być częste. Wykorzystując tę ​​właściwość, kandydaci na k-poddrzewa mogą być generowani na podstawie częstych (k-1)-poddrzew poprzez rozszerzenie klasy prefiksu. Niech C będzie klasą równoważności przedrostka z dwoma elementami (x,i) i (y,j). Niech C' będzie klasą reprezentującą rozszerzenie elementu (x,i). Elementy C' są dodawane przez wykonanie łączenia na dwóch (k-1)-poddrzewach w C. Łączenie operacja na (x,i) i (y,j) jest zdefiniowana następująco.

• Jeśli ${\ Displaystyle i> j}$ , to dodaj (y, j) do C '.
• Jeśli ${\ displaystyle i = j}$ , to dodaj (y, j) i (y, ni) do C 'gdzie ni pierwszy indeks głębokości x w C
• Jeśli ${\ displaystyle i <j}$ , do C 'nie można dodać żadnego możliwego elementu

Ta operacja jest powtarzana dla dowolnych dwóch uporządkowanych, ale niekoniecznie odrębnych elementów w C, aby skonstruować rozszerzone klasy przedrostków k-poddrzew.

Reprezentacja listy zakresów

TreeMiner przeprowadza generowanie kandydatów w pierwszej kolejności, używając reprezentacji poddrzew na liście zakresu, aby ułatwić szybsze liczenie wsparcia. K-poddrzewo S może być reprezentowane przez tryplet (t,m,s), gdzie t jest identyfikatorem drzewa, z którego pochodzi poddrzewo, m jest etykietą dopasowania prefiksu, a s zasięgiem ostatniego węzła w S W zależności od tego, jak S występuje w różnych drzewach w bazie danych, S może mieć różną reprezentację listy zasięgu. TreeMiner definiuje łączenie z listą zakresów , które wykonuje rozszerzenie klasy na reprezentacji poddrzew w liście zakresów. Dwa elementy (x,i) i (y,j) można połączyć, jeśli istnieją dwa poddrzewa ${\ Displaystyle (t_ {x}, m_ {x}, s_ {x})}$ i ${\ Displaystyle (t_ {y}, m_ {y} ,s_{y})}$ , które spełniają jeden z poniższych warunków.

• Test w zakresie: ${\ Displaystyle t_ {x} = t_ {y}, m_ {x} = m_ {y}, s_ {y} \ podzbiór s_ {x}}$ , co odpowiada przypadkowi, gdy ${\ displaystyle i = j}$ .
• test poza zakresem: ${\ Displaystyle t_ {x} = t_ {y}, m_ {x} = m_ {y}, s_ {y}> s_ {x}}$ , które odpowiadają przypadkowi, gdy ${\ displaystyle i> j}$ .

Dzięki śledzeniu odrębnych identyfikatorów drzew używanych w testach listy zakresu można skutecznie obliczyć obsługę poddrzew.

Aplikacje

Dziedziny, w których częsta eksploracja poddrzewa jest użyteczna, zwykle obejmują złożone relacje między jednostkami danych: na przykład analiza dokumentów XML często wymaga częstej eksploracji poddrzewa. Inną dziedziną, w której jest to przydatne, jest problem eksploracji korzystania z sieci: ponieważ działania podejmowane przez użytkowników podczas odwiedzania witryny internetowej można rejestrować i kategoryzować na wiele różnych sposobów, złożone bazy danych drzew muszą być analizowane z częstą eksploracją poddrzew. Inne dziedziny, w których częste eksplorowanie poddrzew jest przydatne, obejmują biologię obliczeniową , analizę struktury RNA, rozpoznawanie wzorców, bioinformatykę i analizę KEGG Baza danych GLYCAN.

Wyzwania

Sprawdzenie, czy wzorzec (lub transakcja) obsługuje dany podgraf, jest problemem NP-zupełnym , ponieważ jest to NP-zupełny przypadek problemu izomorfizmu podgrafu . Ponadto, z powodu eksplozji kombinatorycznej , według Lei i in., „wydobywanie wszystkich częstych wzorców poddrzew staje się niewykonalne w przypadku dużej i gęstej bazy danych drzew”.