Častá těžba podstromu - Frequent subtree mining - Wikipedia

v počítačová věda, častá těžba podstromu je problém najít všechny vzory v dané databázi, jejíž podpora (metrika související s jejím počtem výskytů v jiných podstromech) je nad danou prahovou hodnotou.^[1] Jedná se o obecnější formu problému podstromu maximální dohody.^[2]

Definice

Častou těžbou podstromu je problém pokusu najít všechny vzory, jejichž „podpora“ přesahuje určitou uživatelem zadanou úroveň, kde se „podpora“ počítá jako počet stromů v databázi, které mají alespoň jeden podstrom izomorfní k danému vzoru.^[3]

Formální definice

Problém časté těžby podstromu byl formálně definován jako:^[1]

Vzhledem k limitu minfreq, třída stromů ${ displaystyle { mathcal {C}}}$, tranzitivní vztah podstromu ${ displaystyle P preceq T}$ mezi stromy ${ displaystyle P, T v { mathcal {C}}}$, konečná sada stromů ${ displaystyle { mathcal {D}} subseteq { mathcal {C}}}$, častým problémem těžby podstromu je problém najít všechny stromy ${ displaystyle { mathcal {P}} podmnožina { mathcal {C}}}$ tak, aby v ní nebyly žádné dva stromy ${ displaystyle { mathcal {P}}}$ jsou izomorfní a

${ displaystyle forall P in { mathcal {P}}: quad mathrm {freq} (P, { mathcal {D}}) = sum nolimits _ {T in { mathcal {D} }} d (P, T) geq mathrm {minfreq},}$

kde d je anti-monotónní funkce taková, že pokud ${ displaystyle P ' preceq P}$ pak

${ displaystyle forall T in { mathcal {C}}: quad d (P ', T) geq d (P, T).}$

TreeMiner

V roce 2002 představil Mohammed J. Zaki TreeMiner, efektivní algoritmus pro řešení častého problému těžby podstromu, který používal "seznam oborů" k reprezentaci uzlů stromu a který byl porovnán s PatternMatcher, algoritmem založeným na porovnávání vzorů.^[4]

Definice

Vyvolané sub-stromy

Podstrom ${ displaystyle S = (V_ {s}, E_ {s})}$ je indukovaný sub-strom ${ displaystyle T = (V, E)}$ kdyby a jen kdyby ${ displaystyle V_ {s} subseteq V}$ a ${ displaystyle E_ {s} subseteq E}$. Jinými slovy, jakékoli dva uzly v S, které jsou přímo spojeny hranou, jsou také přímo spojeny v T. Pro jakýkoli uzel A a B v S, pokud je uzel A mateřským uzlem B v S, pak uzel A musí být také rodič uzlu B v T.

Zapuštěné dílčí stromy

Podstrom ${ displaystyle S = (V_ {s}, E_ {s})}$ je vložený podstrom z ${ displaystyle T = (V, E)}$ kdyby a jen kdyby ${ displaystyle V_ {s} subseteq V}$ a dva uzly koncového bodu libovolné hrany v S jsou na stejné cestě od kořene k listovému uzlu v T. Jinými slovy, pro jakýkoli uzel A a B v S, pokud je uzel A mateřským uzlem B v S, pak uzel A musí být předkem uzlu B v T. Jakékoli indukované dílčí stromy jsou také vloženými dílčími stromy, a proto je koncept vložených dílčích stromů zobecněním indukovaných dílčích stromů. Jako takový vložené sub-stromy charakterizují skryté vzory ve stromu, které chybí v tradiční indukované těžbě sub-stromu. Sub-strom o velikosti k se často nazývá k-sub-strom.

Podpěra, podpora

Podpora sub-stromu je počet stromů v databázi, která obsahuje sub-strom. Podstrom je častý, pokud jeho podpora není menší než uživatelem zadaná prahová hodnota (často označovaná jako minsup). Cílem TreeMineru je najít všechny vložené dílčí stromy, které mají podporu alespoň s minimální podporou.

Řetězcové znázornění stromů

Existuje několik různých způsobů kódování stromové struktury. TreeMiner používá řetězcové reprezentace stromů pro efektivní manipulaci se stromy a podporu počítání. Zpočátku je řetězec nastaven na ${ displaystyle varnothing}$. Počínaje kořenem stromu jsou štítky uzlů přidány k řetězci v pořadí hledání do hloubky. -1 se do řetězce přidá, kdykoli se proces hledání vrátí zpět od dítěte k jeho nadřazenému. Například jednoduchý binární strom s kořenem označeným A, levé podřízené označení B a pravé podřízené označení C může být reprezentováno řetězcem A B -1 C -1.

Třída ekvivalence předpon

Dva k-sub-stromy jsou považovány za stejné ekvivalenční třídy prefixů, pokud je jejich řetězcové vyjádření identické až do (k-1) -tého uzlu. Jinými slovy, všechny prvky ve třídě ekvivalence předpon se liší pouze podle posledního uzlu. Například dva stromy s řetězcovou reprezentací A B -1 C -1 a A B -1 D -1 jsou ve třídě ekvivalence předpony A B s prvky (C, 0) a (D, 0). Prvek třídy předpony je určen štítkem uzlu spárovaným s prvním indexem hloubky prvního uzlu, ke kterému je připojen. V tomto příkladu jsou oba prvky třídy předpony A B připojeny ke kořenu, který má index 0.

Rozsah

Rozsah uzlu A je dán dvojicí čísel ${ displaystyle [l, r]}$ kde l a r jsou minimální a maximální index uzlu v pod stromě zakořeněném v A. Jinými slovy, l je index A a r je index listu nejvíce vpravo mezi potomky A. Jako takový index jakéhokoli potomka A musí ležet v rozsahu A, což bude velmi užitečná vlastnost při počítání podpory pod stromů.

Algoritmus

Generace kandidátů

Protimonopolní vlastnost se řídí častými vzory podřízených stromů. Jinými slovy, podpora k-dílčího stromu je menší nebo stejná jako podpora jeho (k-1) dílčích stromů. Pouze super vzory známých častých vzorů mohou být časté. Využitím této vlastnosti lze kandidáty k-dílčích stromů generovat na základě častých (k-1) sub-stromů prostřednictvím rozšíření třídy předpony. Nechť C je třída ekvivalence předpony se dvěma prvky (x, i) a (y, j). Nechť C 'je třída představující rozšíření prvku (x, i). Prvky C 'jsou přidány provedením připojit se operace na dvou (k-1) sub-stromech v C. The připojit se operace na (x, i) a (y, j) je definována jako následující.

• Li ${ displaystyle i> j}$, pak přidejte (y, j) do C '.
• Li ${ displaystyle i = j}$, pak přidejte (y, j) a (y, ni) k C ', kde ni je index hloubky první x v C
• Li ${ displaystyle i$, do C 'nelze přidat žádný možný prvek

Tato operace se opakuje pro libovolné dva uspořádané, ale ne nutně odlišné prvky v C, aby se vytvořily třídy rozšířených předpon k-dílčích stromů.

Reprezentace seznamu oborů

TreeMiner provádí generování hloubky prvního kandidáta pomocí reprezentace dílčích stromů v seznamu oborů, aby usnadnil rychlejší počítání podpory. K-sub-strom S může být reprezentace tripletem (t, m, s), kde t je id stromu, ze kterého sub-strom pochází, m je štítek shody prefixu a s rozsah posledního uzlu v S V závislosti na tom, jak se S vyskytuje v různých stromech v databázi, může mít S různé reprezentace seznamu oborů. TreeMiner definuje připojit seznam oborů který provádí rozšíření třídy na reprezentaci dílčích stromů v seznamu oborů. Dva prvky (x, i) a (y, j) lze spojit, pokud existují dva dílčí stromy ${ displaystyle (t_ {x}, m_ {x}, s_ {x})}$a ${ displaystyle (t_ {y}, m_ {y}, s_ {y})}$ které splňují některou z následujících podmínek.

• Interní test: ${ displaystyle t_ {x} = t_ {y}, m_ {x} = m_ {y}, s_ {y} podmnožina s_ {x}}$, což odpovídá případu, kdy ${ displaystyle i = j}$.
• Test mimo rozsah: ${ displaystyle t_ {x} = t_ {y}, m_ {x} = m_ {y}, s_ {y}> s_ {x}}$, které odpovídají případu, kdy ${ displaystyle i> j}$.

Sledováním odlišných ID stromů použitých v testech seznamu oborů lze efektivně vypočítat podporu dílčích stromů.

Aplikace

Domény, ve kterých je užitečná častá těžba podstromu, mají tendenci zahrnovat složité vztahy mezi datovými entitami: například analýza dokumentů XML často vyžaduje častou těžbu podstromu.^[1] Další doménou, kde je to užitečné, je problém s těžbou využití webu: protože akce prováděné uživateli při návštěvě webu lze zaznamenávat a kategorizovat mnoha různými způsoby, je třeba analyzovat složité databáze stromů s častým těžením podstromu.^[4] Mezi další domény, ve kterých je užitečná častá těžba podstromu, patří výpočetní biologie,^[5][6] Analýza struktury RNA,^[6] rozpoznávání vzorů,^[7] bioinformatika,^[8] a analýza KEGG Databáze GLYCAN.^[9]

Výzvy

Kontrola, zda vzor (nebo transakce) podporuje daný podgraf, je NP-kompletní problém, protože se jedná o NP úplnou instanci problém izomorfismu podgrafu.^[7] Dále kvůli kombinatorická exploze, podle Lei et al., „těžba všech častých vzorů podstromu se stává nemožnou pro velkou a hustou databázi stromů“.^[10]

Reference