Az FP-bővítés algoritmus
Vissza 6. fejezet - Asszociációs elemzés: Alapvető fogalmak és algoritmusok Előre

Az FP-bővítés algoritmus

Ebben a szakaszban egy alternatív algoritmust mutatunk be melynek neve FP-bővítés (FP-growth).[6] Ez az algoritmus teljesen másképp közelíti meg a gyakori elemhalmazok bányászatát. Az FP-bővítés nem követi az Apriori ``generál és tesztel'' paradigmáját. Ehelyett az adathalmazt egy kompakt struktúrába sűríti (ennek neve FP-fa, azaz gyakori mintázatok fája), majd a gyakori elemhalmazokat közvetlenül ebből a struktúrából nyeri ki. A következőkben ezt a módszert mutatjuk be részletesen.

FP-fa reprezentáció

Egy FP-fa nem más, mint a bemeneti adatok tömörített reprezentációja. Létrehozásakor beolvassuk az adathalmazt tranzakciónként, majd az egyes tranzakció kat az FP-fában ráillesztjük egy-egy útvonalra. Mivel a különböző tranzakció kban számos azonos elem is lehet, így a tranzakció k útvonalai átfedhetik egymást. Minél jobban fedik egymást az útvonalak, az FP-fa struktúrával annál jobb tömörítést tudunk elérni. Ha az FP-fa mérete elég kicsi ahhoz, hogy beférjen a központi memóriába, akkor a gyakori elemhalmazokat közvetlenül ebből a memóriában tárolt struktúrából tudjuk kinyerni, és nem kell újra és újra végigolvasni az adatokat egy másodlagos tárolón.

6.24. ábra - Egy FP-fa felépítése.

Egy FP-fa felépítése.

A 6.24. ábrán látható adathalmaz tíz tranzakció t és öt elemet tartalmaz. Az ábrán szintén feltüntettük az első három tranzakció beolvasásával kapott FP-fa struktúrákat. A fa minden egyes csúcsához hozzá van rendelve egy attribútumcímke és egy számláló; ez utóbbi az adott útvonalra illesztett tranzakció k számát jelöli. Kezdetben az FP-fában csupán a gyökércsúcs szerepel, ezt a null szimbólummal jelöljük. Az FP-fa folyamatos bővítése a következőképpen történik:

  1. Egyszer végigolvassuk az adathalmazt az elemek támogatottsági szintjének megállapítása miatt. A nem gyakori elemeket elvetjük, a gyakori elemeket pedig előfordulási gyakoriságuk szerinti csökkenő sorrendbe rendezzük. A 6.24. ábrán látható adathalmaz esetén az a a leggyakoribb elem, ezt követi a b , a c , a d majd az e .

  2. Az algoritmus még egyszer végigolvassa az adathalmazt az FP-fa felépítéséhez. Az első tranzakció ( {a,b} ) beolvasása után létrehozzuk az a -val és b -vel jelölt csúcsokat. A tranzakció t így a null→a→b útvonal reprezentálja. Az útvonal csúcsaiban a számlálók értéke 1.

  3. A második tranzakció ({ b , c , d }) beolvasása után a b , c és d elemeknek új csúcsokat hozunk létre. A csúcsok összekötésével megkapjuk a null→b→c→d útvonalat, mely a második tranzakció t reprezentálja. Az útvonal csúcsaiban a számlálók értéke szintén egy. Bár az első két tranzakció ban van egy közös elem ( b ), a tranzakció k útvonalai mégis diszjunktak, ugyanis a két tranzakció nak nincs közös előtagja.

  4. A harmadik tranzakció ( {a,c,d,e} ) és az első tranzakció előtagja tartalmaz egy közös elemet ( a ). Következésképpen a harmadik tranzakció útvonala ( null→a→c→d → e ) átfedi az első tranzakció útvonalát ( null→a→b ). Az egymást fedő útvonalak miatt az a csúcs számlálóját kettőre növeljük, míg az újonnan létrehozott csúcsok ( c , d és e ) számlálóinak értéke egy.

  5. Ez a művelet addig folytatódik, míg az összes tranzakció t rá nem illesztjük az FP-fa megfelelő útvonalára. Az összes tranzakció beolvasásával kapott végleges FP-fa a 6.24. ábra alján látható.

Egy FP-fa mérete általában kisebb, mint a tömörítetlen adatbázis mérete. Ez azzal magyarázható, hogy a bevásárlókosarak adataiban számos tranzakció ban szerepelnek azonos árucikkek. A legjobb esetben az összes tranzakció ban ugyanazok az elemek szerepelnek. Ekkor az FP-fa csupán egyetlen ágat tartalmaz. A legrosszabb esetben a tranzakció kban szereplő elemek egyedi halmazokat alkotnak. Mivel ekkor a tranzakció k között nincs egyetlen közös elem sem, az FP-fa mérete gyakorlatilag azonos lesz az eredeti adathalmaz méretével. Az igazság az, hogy az FP-fa fizikailag nagyobb helyet fog elfoglalni a csúcsok közti mutatók és az elemekhez rendelt számlálók külön tárigénye miatt.

6.25. ábra - A 6.24. ábrán látható adathalmaz FP-fa reprezentációja az elemek eltérő rendezése mellett

A 6.24. ábrán látható adathalmaz FP-fa reprezentációja az elemek eltérő rendezése mellett

Egy FP-fa mérete attól is függ, hogy hogyan rendezzük az elemeket. Ha az előző példában megfordítjuk a rendezést, vagyis az elemeket támogatottság szerinti növekvő sorrendbe tesszük, akkor a 6.25. ábrán látható FP-fát kapjuk. A fa sűrűbbnek tűnik, mivel a gyökércsúcsnál az ágak száma 2-ről 5-re, a magas támogatottságú elemeket tartalmazó csúcsok ( például a és b ) száma pedig 3-ról 12-re emelkedett. Mindazonáltal a támogatottság szerinti csökkenő sorrend használata nem vezet mindig a legkisebb fához. Növeljük meg például fig4:fptree. ábrán látható adathalmazt 100 db {e} -t, 80 db {d} -t, 60 db {c} -t és 40 db {b} -t tartalmazó tranzakció val. Most az e elem a leggyakoribb; ezt követi a d , c , b és a . Az új tranzakció kkal kiterjesztett adathalmaz esetén a támogatottság szerinti csökkenő sorrend alkalmazása a 6.25. ábrán látható FP-fához hasonló eredményt adna. A támogatottság szerinti növekvő sorrend alkalmazása viszont egy kisebb, a 6.24. (iv) ábrához hasonló FP-fát eredményezne.

Az FP-fákban szerepel még egy mutatólista is, ahol a mutatók az azonos elemeket tartalmazó csúcsokat kötik össze. Ezek a mutatók (a 6.24. és a 6.25. ábrákon szaggatott vonallal jelöltük őket) az egyes elemek gyors elérését könnyítik meg a fában. A következő szakaszban azt mutatjuk be, hogy hogyan lehet felhasználni az FP-fát a mutatóival együtt a gyakori elemhalmazok előállításához.

Gyakori elemhalmazok előállítása az FP-bővítés algoritmussal

Az FP-bővítés algoritmus a gyakori elemhalmazokat egy FP-fából állítja elő, ahol a fát alulról felfelé irányuló módon tárja fel. Vegyük például a 6.24. ábrán látható fát. Az algoritmus először az e -re végződő gyakori elemhalmazokat keresi meg, majd a d -re, c -re, b -re és végül az a -ra végződőeket. Az egy bizonyos elemre végződő gyakori elemhalmazok alulról felfelé irányuló stratégiával való megkeresése ekvivalens a 6.5. szakaszban leírt utótag-alapú megközelítéssel. Mivel az összes tranzakció illeszkedik az FP-fa egy útvonalára, ezért az egy bizonyos elemre végződő ( például e ) gyakori elemhalmazokat úgy is ki tudjuk nyerni, ha csak az e -re végződő útvonalakat vizsgáljuk meg. Az e csúcshoz társított mutatók használatával ezekhez az útvonalakhoz nagyon gyorsan hozzá lehet férni. Az így feltérképezett útvonalak a 6.26. (a) ábrán láthatók. Egy kicsit később fogjuk részletezni, hogy ezen útvonalakból hogyan lehet kinyerni a gyakori elemhalmazokat.

6.26. ábra - A gyakori elemhalmaz ok előállításának problémája több részproblémára felosztva. Az egyes részproblémák az e , d , c , b és a végződésű gyakori elemhalmaz okat keresik meg.

A gyakori elemhalmaz ok előállításának problémája több részproblémára felosztva. Az egyes részproblémák az e, d, c, b és a végződésű gyakori elemhalmaz okat keresik meg.

Miután megtaláltuk az e -re végződő gyakori elemhalmazokat, az algoritmus nekilát a d -re végződő gyakori elemhalmazok keresésének. Ehhez a d csúcshoz rendelt útvonalakat kell feldolgozni (lásd a 6.26. (b) ábrát). Ez a művelet a c , b majd végül az a csúcshoz rendelt útvonalak feldolgozásával folytatódik. Az ezen elemekhez tartozó útvonalak a 6.26. (c), (d) és (e) ábrákon láthatók. Az útvonalhoz tartozó gyakori elemhalmazokat a 6.6. táblázatban foglaltuk össze.

6.6. táblázat - A gyakori elemhalmaz ok listája. Az elemhalmaz ok az utótagjaik alapján vannak rendezve .

utótag

gyakori elemhalmaz ok

e

{ e } , { d,e } , { a,d,e } , { c,e } , { a,e }

d

{ d } , { c,d } , { b,c,d } , { a,c,d } , { b,d } , { a,b,d } , { a,d }

c

{ c } , { b,c } , { a,b,c } , { a,c }

b

{ b } , { a,b }

a

{ a }


Az FP-bővítés algoritmus az egy bizonyos utótagra végződő gyakori elemhalmaz okat az úgynevezett ``oszd meg és uralkodj'' stratégiával keresi meg, melynek során egy problémát kisebb részproblémákra oszt fel. Tegyük fel például , hogy az e -re végződő gyakori elemhalmazokat szeretnénk megkeresni. Ehhez először is azt kell leellenőrizni, hogy maga az {e} elemhalmaz gyakori-e. Ha gyakori, akkor nézzük a következő részproblémákat: találjuk meg a de , majd a ce , be és ae utótaggal rendelkező gyakori elemhalmazokat. Ezen részproblémákat aztán további kisebb részproblémákra osztjuk fel. Az egyes részproblémák megoldásainak az egyesítésével meg tudjuk találni az összes e utótagú gyakori elemhalmazt. Az ``oszd meg és uralkodj'' módszer az FP-bővítés algoritmus fő stratégiája.

A részproblémák megoldásának konkrét szemléltetésére nézzük meg, hogy hogyan tudjuk megkeresni az e -re végződő gyakori elemhalmazokat.

  1. Az első lépés során összegyűjtjük az összes e -t tartalmazó útvonalat. Ezeket a kezdeti útvonalakat prefix útvonalaknak nevezzük (lásd a 6.27. (a) ábrát).

6.27. ábra - Az e -re végződő gyakori elemhalmaz ok megtalálása az FP-bővítés algoritmus sal

Az e-re végződő gyakori elemhalmaz ok megtalálása az FP-bővítés algoritmus sal

  1. A 6.27. (a) ábrán látható prefix útvonalakból megállapítjuk az e támogatottsági értékét. Ehhez az e -vel jelölt csúcsok számlálóinak az értékét kell összeadni. Ha például a minimális támogatottsági szint 2, akkor {e} gyakori elemhalmaz, hiszen a támogatottsági szintje 3.

  2. Mivel {e} gyakori, az algoritmusnak további részproblémákat kell megoldania: meg kell keresni a de , ce , be és ae végződésű gyakori elemhalmazokat. Ezen részproblémák megoldása előtt azonban a prefix útvonalakat egy feltételes FP-fába kell átalakítani. Ez felépítésében ugyan hasonlít egy FP-fára, viszont arra szolgál, hogy megtaláljunk egy bizonyos utótaggal rendelkező gyakori mintázatokat. Egy feltételes FP-fát a következőképpen hozunk létre:

  1. Először is frissíteni kell a prefix útvonalakon a támogatottsági értékeket, ugyanis néhány érték olyan tranzakció kat is tartalmaz, melyekben nem szerepel az e . Például a 6.27. (a) ábrán a jobb szélső null→b:2→c:2→e:1 útvonal a {b,c} tranzakció t is tartalmazza, de ebben nem szerepel az e elem. A prefix útvonalon tehát a számlálókat 1-re kell állítani, mely innentől a {b,c,e} -t tartalmazó tranzakció k valódi számát fogja mutatni.

  2. (b) A prefix útvonalakat megrövidítjük az e csúcsok eltávolításával. Ezeket a csúcsokat nyugodtan el lehet távolítani, hiszen a prefix útvonalakon úgy állítottuk be a számlálók értékét, hogy azok csupán az e -t tartalmazó tranzakció kat fejezzék ki. A de , ce , be és ae végződésű gyakori elemhalmazokat kereső részproblémáknak már nincs szükségük az e csúcsokra.

  3. (c) A prefix útvonalakon történő támogatottsági értékek frissítése során néhány elemről kiderülhet, hogy már nem gyakoriak. Például a b csúcs csak egyszer fordul elő és a támogatottsági értéke 1. Ez azt jelenti, hogy csupán egyetlen tranzakció tartalmazza egyszerre a b és e elemeket. A b elemet innentől nyugodtan figyelmen kívül hagyhatjuk, ugyanis biztosak lehetünk benne, hogy minden be végződésű elemhalmaz nem gyakori.

Az e feltételes FP-fája a 6.27. (b) ábrán látható. A fa különbözik az eredeti prefix útvonalaktól, ugyanis a számlálókat frissítettük, a b és e csúcsokat pedig eltávolítottuk.

  1. Az FP-bővítés algoritmus az e feltételes FP-fáját használja fel a de , ce és ae végződésű gyakori elemhalmazokat kereső részproblémák megoldásához. A de végződésű gyakori elemhalmazok megtalálásához össze kell gyűjteni az e feltételes FP-fájából a d prefix útvonalait (lásd a 6.27. (c) ábrát). A d -hez tartozó előfordulási gyakoriságok hozzáadásával megkapjuk a {d,e} támogatottsági szintjét. Mivel ez egyenlő kettővel, ezért {d,e} gyakori elemhalmaz. Ezután az algoritmus felépíti a 3-as pontban leírt módon a de feltételes FP-fáját. A számlálók frissítése és a nem gyakori c elem eltávolítása után a 6.27. (d) ábrán látható feltételes FP-fát kapjuk. Mivel a feltételes FP-fa csupán egy elemet tartalmaz ( a ), melynek a támogatottsági szintje azonos a minsup értékkel, ezért az algoritmus előállítja az {a,d,e} gyakori elemhalmazt és továbblép a következő részproblémára, mely nem más, mint a ce végződésű gyakori elemhalmazok előállítása. A c prefix útvonalainak feldolgozása után csupán a {c,e} bizonyul gyakorinak. Az algoritmus továbblép a következő részproblémára, ahol már csak egyetlen gyakori elemhalmaz maradt, az {a,e} .

Ezzel a példával az FP-bővítés algoritmusban használt ``oszd meg és uralkodj'' stratégiát szemléltettük. A rekurzív lépésekben egy feltételes FP-fát építünk, melynek során frissítjük a prefix útvonalakon a számlálókat, illetve eltávolítjuk a nem gyakori elemeket. Mivel a részproblémák diszjunktak, az FP-bővítés nem fogja ismételten előállítani ugyanazt az elemhalmaz t. Miközben az algoritmus közös utótaggal rendelkező elemhalmazokat állít elő, a csúcsokhoz rendelt számlálók lehetővé teszik a támogatottsági szintek megállapítását.

Az FP-bővítés egy érdekes algoritmus, mely azt mutatja meg, hogy egy tranzakció s adathalmaz kompakt reprezentációjából hogyan lehet gyakori elemhalmaz okat hatékonyan előállítani. Ráadásul bizonyos tranzakció s adathalmazok esetén az FP-bővítés nagyságrendekkel jobb teljesítményt nyújt, mint a klasszikus Apriori. Az FP-bővítés futási ideje az adathalmaz tömörítési tényezőjétől függ. Ha az előállított feltételes FP-fák túlságosan szerteágazók (a legrosszabb esetben egy teljes prefix fa), akkor az algoritmus teljesítménye számottevően visszaesik, mivel jelentősen megnő a részproblémák száma, és így nagyon sok részeredményt kell összevonni.


[6] A fordító megjegyzése: Az FP a frequent pattern, azaz a gyakori mintázat, gyakori elemhalmaz rövidítése.

Vissza Fel Előre
Alternatív módszerek gyakori elemhalmazok előállítására Főoldal Az asszociációs mintázatok kiértékelése