Gyakori elemhalmazok előállítása

Az összes lehetséges elemhalmaz felsorolásához egy hálóstruktúrát alkalmazhatunk. A 6.1. ábra egy elemhalmazhálót szemléltet I={a,b,c,d,e} esetén. Általánosságban elmondható, hogy egy k elemet tartalmazó adathalmazból potenciálisan 2 k 1 gyakori elemhalmazt lehet előállítani, melyben nincs benne az üres halmaz. Mivel számos gyakorlati alkalmazás esetén k értéke nagyon nagy lehet, ezért az elemhalmazok felfedezéséhez szükséges keresési tér exponenciálisan nagy.

6.1. ábra - Egy elemhalmazháló.

Egy elemhalmazháló.

Ha a nyers erő módszerét alkalmaznánk a gyakori elemhalmazok keresésére, akkor az elemhalmazhálóban valamennyi elemhalmazjelölt támogatottság át meg kellene állapítani. Ehhez a jelölteket össze kell vetni minden egyes tranzakció val, ezt a műveletet a 6.2. ábra mutatja. Ha a jelölt szerepel egy tranzakció ban, akkor a támogatottság i szintjét megnöveljük. Például a {kenyér,tej} támogatottság át háromszor kell megnövelni, mivel ez az elemhalmaz az 1-es, 4-es, illetve 5-ös tranzakció kban szerepel. Ez a megközelítés azonban nagyon költséges lehet, ugyanis O(NMw) összehasonlítás kell hozzá, ahol N a tranzakció k száma, M= 2 k 1 az elemhalmazjelölt ek száma, w pedig a maximális tranzakció szélesség.

6.2. ábra - Elemhalmazjelöltek támogatottságának a kiszámítása

Elemhalmazjelöltek támogatottságának a kiszámítása

A gyakori elemhalmaz ok előállítása esetén a számítás bonyolultságát többféleképpen is csökkenteni lehet.

  1. Elemhalmazjelölt ek számának ( M ) csökkentése: Az apriori-elv, melyet a következő szakaszban írunk le, hatékony módja annak, hogy bizonyos elemhalmazjelölt eket a támogatottságuk kiszámítása nélkül is ki lehessen zárni.

  2. Összehasonlítások számának csökkentése: Ahelyett, hogy minden elemhalmazjelöltet összevetnénk az összes tranzakció val, az összehasonlítások számát fejlettebb adatstruktúrák alkalmazásával is csökkenthetjük, mely adatstruktúrák vagy az elemhalmazjelölt eket tárolják le, vagy az adathalmazt tömörítik össze. Ezeket a stratégiákat 6.2.3. és 6.6. szakaszokban tekintjük át.

Az apriori-elv

Ez a szakasz azt mutatja be, hogy a támogatottság i mérték hogyan segít lecsökkenteni az elemhalmazjelöltek számát a gyakori elemhalmazok előállítása során. A támogatottságot a következő elv miatt tudjuk felhasználni az elemhalmazjelölt ek nyesése során:

6.1. Tétel

(apriori-elv) Ha egy elemhalmaz gyakori, akkor ezen elemhalmaz összes részhalmaza is gyakori.

Az apriori-elv mögötti ötlet szemléltetéséhez vegyük a 6.3. ábrán látható elemhalmazhálót, s tegyük fel, hogy {c,d,e} gyakori. Világos, hogy ha egy tranzakció tartalmazza a {c,d,e} elemhalmazt, akkor ennek a részhalmazait ( {c,d} , {c,e} , {d,e} , {c} , {d} , {e} ) is tartalmazza. Következésképpen, ha {c,d,e} gyakori, akkor {c,d,e} összes részhalmazának is gyakorinak kell lennie (ezeket az ábrán szürkével jelöltük).

6.3. ábra - Az apriori-elv szemléltetése. Ha {c, d, e} gyakori, akkor ezen elemhalmaz összes részhalmaza is gyakori.

Az apriori-elv szemléltetése. Ha {c, d, e} gyakori, akkor ezen elemhalmaz összes részhalmaza is gyakori.

6.4. ábra - A támogatottság alapú nyesés szemléltetése. Ha {a,b} nem gyakori, akkor {a,b} egyetlen szuperhalmaza sem gyakori.

A támogatottság alapú nyesés szemléltetése. Ha {a,b} nem gyakori, akkor {a,b} egyetlen szuperhalmaza sem gyakori.

Ezzel szemben, ha egy elemhalmaz ( például {a,b} ) nem gyakori, akkor az elemhalmaz egyetlen szuperhalmaza sem lehet gyakori. Ahogy az a 6.4. ábrán látható, ha az {a,b} elemhalmazról kiderül, hogy nem gyakori, akkor az {a,b} szuperhalmazait tartalmazó teljes részgráf figyelmen kívül hagyható. Az exponenciális keresési térnek a támogatottsági mérték alapján történő ``nyírási'' stratégiáját támogatottságalapú nyesésnek hívjuk. Ez a fajta nyesési stratégia a támogatottsági mérték egy kulcsfontosságú jellemzője miatt lehetséges, mely szerint egy elemhalmaz támogatottság a soha nem lépi túl a részhalmazainak támogatottság át. A támogatottsági mérték ezen jellemzője antimonoton tulajdonságként is ismert.

6.2. Definíció

(Monotonitás tulajdonság) Legyen I elemek egy halmaza, J= 2 I pedig I hatványhalmaza. Az f mérték monoton (vagy felfelé zárt), ha

X,YJ:  (XY)f(X)f(Y).

Ez a definíció azt jelenti, hogy ha X részhalmaza Y -nak, akkor f(X) nem lehet nagyobb, mint f(Y) . Ezzel szemben f antimonoton (vagy lefelé zárt), ha

X,YJ:  (XY)f(Y)f(X),

vagyis ha X részhalmaza Y -nak, akkor f(Y) nem lehet nagyobb, mint f(X) .

Ha egy mérték rendelkezik az antimonoton tulajdonsággal, akkor közvetlenül beépíthető az adatbányászati algoritmus okba az elemhalmazjelöltek exponenciális keresési terének hatékony nyesése érdekében. Ezt a következő szakaszban fogjuk bemutatni.

Gyakori elemhalmazok előállítása az Apriori algoritmussal

Az asszociációs szabály okat bányászó Apriori algoritmus az első olyan algoritmus, amely a támogatottság alapú nyesési módszert használta fel az elemhalmazjelöltek exponenciális számának a csökkentésére. A 6.5. ábra vázlatosan ábrázolja a gyakori elemhalmazok Apriori algoritmussal történő előállítását a 6.1. táblázatban lévő tranzakció kra alkalmazva. Tegyük fel, hogy a támogatottsági küszöbérték 60% , vagyis a minimális támogatottsági szint 3.

6.5. ábra - Gyakori elemhalmazok előállítása az Apriori algoritmussal

Gyakori elemhalmazok előállítása az Apriori algoritmussal

Kezdetben minden elemet 1-elemhalmazjelöltnek tekintünk. A támogatottság i értékek kiszámítása után a { kóla } és { tojás } elemhalmazjelölteket kizárjuk, mivel háromnál kevesebb tranzakció ban szerepelnek. A következő interációban a 2-elemhalmazjelöltek előállításához csupán a gyakori 1- elemhalmaz okat használjuk fel, ugyanis az apriori-elv biztosítja, hogy a nem gyakori 1- elemhalmaz ok egyetlen szuperhalmaza sem gyakori. Mivel csak négy gyakori 1-elemhalmazunk van, az algoritmus által előállított 2-elemhalmazjelöltek száma ( 4 2 )=6 . A támogatottság i értékek kiszámítása után kiderül, hogy ezen hat jelölt közül kettő, a {sör,kenyér} és a {sör,tej} nem gyakoriak. A maradék négy jelölt gyakori, így felhasználjuk őket a 3-elemhalmazjelöltek előállításához. A támogatottság alapú nyesés nélkül a példában szereplő hat elemből ( 6 3 )=20 darab 3-elemhalmazjelöltet lehetne előállítani. Az apriori-elvet követve azonban csak azokat a 3-elemhalmazjelölteket kell megtartani, amelyeknek az összes részhalmaza gyakori. Ezzel a jellemzővel egyedül a {kenyér,pelenka,tej} jelölt rendelkezik.

Az apriori nyesési stratégia hatékonyságát az előállított elemhalmazjelöltek összeszámlálásával tudjuk megmutatni. Ha a nyers erő módszerével állítjuk elő az összes (legfeljebb 3 elemű) elemhalmazt mint jelölteket, akkor ez

( 6 1 )+( 6 2 )+( 6 3 )=6+15+20=41

számú jelöltet produkál. Az apriori-elvvel ez a szám lecsökkenthető

( 6 1 )+( 4 2 )+1=6+6+1=13

számú jelöltre, mely még ezen egyszerű példa esetén is egy 68%-os csökkenést jelent az elemhalmazjelöltek számában.

Az Apriori algoritmus gyakori elemhalmazokat előállító részének a pszeudokódját a 6.1. algoritmus szemlélteti. Jelölje C k a k -elemhalmazjelöltek halmazát, F k pedig a gyakori k -elemhalmazok halmazát:

6.1. algoritmus Az Apriori algoritmus gyakori elemhalmazokat előállító része

1: k = 1

2: Fk = { i | i ∈ I ∧ σ({i}) ≥ N × minsup } {az összes gyakori 1-elemhalmaz megkeresése}

3: repeat

4: k = k + 1

5: Ck = Apriori-Gen(Fk−1) {elemhalmazjeloltek előállítása}

6: for minden t ∈ T tranzakcióra do

7: Ct = részhalmaz(Ck, t) {a t-hez tartozó összes jelölt azonosítása}

8: for minden c ∈ Ct elemhalmazjelöltre do

9: σ(c) = σ(c) + 1 {támogatottsági szint növelése}

10: end for

11: end for

12: Fk = { c | c ∈ Ck ∧σ(c) ≥ N ×minsup } {gyakori k-elemhalmazok kinyerése}

13: until Fk = ∅

14: Eredmeny = Fk

  • Az algoritmus először végigmegy az adathalmazon és megállapítja az elemek támogatottság át. Ezen lépés végére ismert lesz az összes gyakori 1-elemhalmaz (lásd F 1 , 1. és 2. lépés).

  • Az algoritmus ezután új k -elemhalmazjelölteket állít elő iteratív módon az előző iterációban talált gyakori ( k1 )-elemhalmazokból (5. lépés). A jelöltek előállításáért az Apriori-Gen nevű függvény a felelős, ezt a 6.2.3. szakaszban mutatjuk be.

  • A jelöltek támogatottság i értékének megállapításához az algoritmusnak ismét végig kell mennie az adathalmazon (6--10. lépések). A részhalmaz függvény mindazon C k -beli elemhalmazjelölteket adja vissza, melyek szerepelnek az egyes t tranzakció kban. Ezen függvény implementációját a 6.2.4. szakaszban mutatjuk be.

  • A támogatottság i értékek kiszámítása után az algoritmus kizárja az összes olyan elemhalmazjelöltet, amelyeknek a támogatottság a kisebb, mint a minsup érték (12. lépés).

  • Az algoritmus akkor áll le, amikor már nem tud több gyakori elemhalmazt előállítani, azaz F k = (13. lépés).

Az Apriori algoritmus gyakori elemhalmazokat előállító részének két fontos jellemzője van. Először is, az Apriori szintenkénti algoritmus, ugyanis az elemhalmazhálót szintenként járja be, vagyis a gyakori 1-elemhalmazoktól folyamatosan halad a leghosszabb gyakori elemhalmazokig. Másodsorban az Apriori generál-és-tesztel stratégiát használ a gyakori elemhalmazok megtalálásához. Az új elemhalmazjelölteket minden egyes iterációban az előző lépésben talált gyakori elemhalmazokból állítja elő. Az algoritmus ezután kiszámolja a jelöltek támogatottságát és ezt összeveti a minsup küszöbértékkel. Az algoritmusnak összesen k max +1 iterációra van szüksége, ahol k max a legnagyobb gyakori elemhalmaz méretét jelöli.

Jelöltek előállítása és nyesése

A 6.1. algoritmus 5. lépésében látott Apriori-Gen függvény a következő két lépésben állítja elő az elemhalmazjelölteket:

  1. Jelöltek generálása: Ez a művelet új k -elemhalmazjelölteket állít elő az előző iteráció során talált gyakori ( k1 )-elemhalmazok alapján.

  2. Jelöltek nyesése: Ez a művelet néhány k -elemhamazjelöltet zár ki a támogatottság alapú nyesési stratégiát felhasználva.

A jelöltek nyesésének szemléltetéséhez vegyünk egy X={ i 1 , i 2 ,, i k } k -elemhalmazjelöltet. Az algoritmusnak el kell döntenie, hogy X összes X{ i j } , j=1,2,,k , valódi részhalmaza gyakori-e. Ha akár csak egy nem gyakori, X azonnal kizárható. Ezzel a módszerrel hatékonyan le lehet csökkenteni azon elemhalmazjelöltek számát, melyeknek ki kell számítani a támogatottsági szintjét. Ennek a műveletnek O(k) a bonyolultsága minden k - elemhalmazjelölt re. Azonban, ahogy azt látni fogjuk a későbbiekben, egy adott elemhalmazjelölt esetén nem kell az összes k részhalmazt megvizsgálni. Ha a jelölt előállításához a k részhalmazból m darab lett felhasználva, akkor a nyesési lépés során csupán a maradék km részhalmazt kell leellenőrizni.

Az elemhalmazjelölteket elméletileg többféle módon is elő lehet állítani. Következzék itt egy lista arról, hogy egy hatékony jelöltgeneráló módszernek milyen követelményeknek kell megfelelnie:

  1. Lehetőleg ne állítson elő túl sok felesleges jelöltet. Egy elemhalmazjelölt felesleges, ha legalább egy részhalmaza nem gyakori. A támogatottság antimonoton jellemzője alapján egy ilyen jelölt garantáltan nem gyakori.

  2. A jelölthalmaznak teljesnek kell lennie, vagyis a jelöltek előállítása során egyetlen gyakori elemhalmaz sem maradhat ki. A teljesség biztosításához az elemhalmazjelöltek halmazának magába kell foglalnia a gyakori elemhalmaz ok halmazát, azaz F k C k minden k -ra.

  3. Lehetőség szerint ne állítsa elő ugyanazt a jelöltet egynél többször. Például az {a,b,c,d} elemhalmazjelöltet többféleképpen is elő lehet állítani: az {a,b,c} és {d} egyesítésével, a {b,d} és {a,c} összevonásával, a {c} és {a,b,d} összevonásával, stb. A jelöltek ismételt előállítása felesleges számításokat jelent, így ezt a hatékonyabb műveletvégzés miatt inkább kerüljük.

A következőkben néhány módszert mutatunk be röviden a jelöltek előállítására, beleértve azt is, amelyet az Apriori-Gen függvény használ.

A nyers erő módszere

A nyers erő módszere valamennyi k -elemhalmazt lehetséges jelöltként kezel, majd a felesleges jelölteket a jelöltek nyesésével távolítja el (lásd a 6.6. ábrát). Az előállított elemhalmazjelöltek száma a k szinten ( d k ) , ahol d az elemek teljes számát jelöli. Bár a jelöltek előállítása meglehetősen egyszerű, a jelöltek nyesése nagyon költséges a megvizsgálandó elemhalmazok óriási száma miatt. Tegyük fel, hogy az egyes jelöltek esetén a szükséges számítások mennyisége O(k) . A módszer teljes bonyolultsága ekkor O( k=1 d k× d k )=O(d 2 d1 ) .

6.6. ábra - 3-elemhalmazjelöltek előállítása a nyers erő módszerével

3-elemhalmazjelöltek előállítása a nyers erő módszerével

F k1 × F 1 módszer

A jelöltek előállítására egy másik módszer, ha minden gyakori (k1) -elemhalmazt gyakori elemekkel bővítünk ki. A 6.7. ábra azt szemlélteti, hogyan lehet egy gyakori 2-elemhalmazt ( például {sör,pelenka} ) úgy kibővíteni egy gyakori elemmel ( például kenyér), hogy ezáltal egy 3- elemhalmazjelölt et kapjunk ( {sör,pelenka,kenyér} ). Ez a módszer O(| F k1 |×| F 1 |) k - elemhalmazjelölt et eredményez, ahol | F j | a gyakori j -elemhalmazok számát jelöli. Ennek a lépésnek a teljes bonyolultsága O( k k| F k1 || F 1 |) .

6.7. ábra - k-elemhalmazjelöltek előállítása és nyesése gyakori (k − 1)-elemhalmazok és gyakori elemek párosításával. Megjegyezzük, hogy néhány jelölt felesleges a nem gyakori részhalmazok miatt.

k-elemhalmazjelöltek előállítása és nyesése gyakori (k − 1)-elemhalmazok és gyakori elemek párosításával. Megjegyezzük, hogy néhány jelölt felesleges a nem gyakori részhalmazok miatt.

Az eljárás teljes, mivel minden gyakori k -elemhalmaz egy gyakori (k1) -elemhalmazból és egy gyakori 1-elemhalmazból áll össze. Következésképpen az összes gyakori k -elemhalmaz része a módszer által előállított k - elemhalmazjelölt ek halmazának. Ez a módszer azonban nem akadályozza meg egy jelölt egynél többszöri előállítását. Például a {kenyér,pelenka,tej} előállítható {kenyér,pelenka} és {tej} , vagy a {kenyér,tej} és {pelenka} , vagy a {pelenka,tej} és {kenyér} elemhalmazok egyesítésével. Egy lehetséges mód a jelöltek többszöri előállításának a megakadályozására, ha a gyakori elemhalmazokban az elemeket lexikografikus sorrendben tartjuk. Ekkor minden egyes X ( k1 )-elemhalmazt csak olyan elemekkel bővítünk ki, melyek lexikografikusan nagyobbak az X -ben szereplő elemeknél. Például a {kenyér,pelenka} bővíthető a {tej} elemhalmazzal, ugyanis a tej lexikografikusan nagyobb, mint a kenyér vagy a pelenka. Azonban a {pelenka,tej} nem bővíthető a {kenyér} , a {kenyér,tej} pedig nem bővíthető a {pelenka} elemhalmazzal, mivel sérül a lexikografikus rendezésre vonatkozó feltétel.

Bár ez az eljárás lényeges előrelépés a nyers erő módszerével szemben, még mindig nagyon sok felesleges jelölttel kell számolni. A {sör,pelenka} és {tej} elemhalmazokból előállított jelölt például felesleges, mivel az egyik részhalmaza ( {sör,tej} ) nem gyakori. A felesleges jelöltek számának csökkentésére számos heurisztika létezik. Megjegyezzük például, hogy minden k - elemhalmazjelölt esetén, mely túljut a nyesési lépésen, teljesülnie kell a következő feltételnek: a jelölt minden egyes eleme legalább k1 darab gyakori ( k1 )-elemhalmazban szerepel. Ellenkező esetben ugyanis a jelölt garantáltan nem gyakori. Például a {sör,pelenka,tej} csak akkor érdekes 3-elemhalmazjelölt, ha minden egyes eleme -- beleértve a sört is -- legalább két gyakori 2- elemhalmaz ban szerepel. Mivel csak egy gyakori 2-elemhalmazban szerepel a sör, ezért az összes sört tartalmazó jelölt nem gyakori.

F k1 × F k1 módszer

Az Apriori-Gen függvény ben szereplő módszer a jelölteket gyakori ( k1 )-elemhalmazpárok egyesítésével állítja elő. Az egyesítést csak akkor kell végrehajtani, ha az elemhalmazpárok első k2 elemei azonosak. Legyen A={ a 1 , a 2 ,, a k1 } és B={ b 1 , b 2 ,, b k1 } egy gyakori ( k1 )-elemhalmazpár. A -t és B -t csak a következő feltétel teljesülése esetén egyesítjük:

a i = b i ,i=1,2,,k2, ésa k1 b k1 .

6.8. ábra - k-elemhalmazjelöltek előállítása és nyesése gyakori (k − 1)-elemhalmazpárok egyesítésével

k-elemhalmazjelöltek előállítása és nyesése gyakori (k − 1)-elemhalmazpárok egyesítésével

A 6.8. ábrán a {kenyér,pelenka} és {kenyér,tej} gyakori elemhalmaz ok lettek egyesítve, melynek eredménye a {kenyér,pelenka,tej} 3- elemhalmazjelölt . Az algoritmusnak nem kell egyesíteni a {sör,pelenka} és {pelenka,tej} elemhalmazokat, mivel ezek első elemei különböznek. Ha a {sör,pelenka,tej} egy hasznos jelölt lenne, akkor ezt a jelöltet inkább a {sör,pelenka} és {sör,tej} elemhalmazok egyesítése eredményezné. Ez a példa két dolgot is szemléltet: egyrészt a jelölteket előállító módszer teljességét, másrészt pedig a lexikografikus rendezés előnyét, ez ugyanis megakadályozza egy jelölt többszöri előállítását. Mivel a jelölteket a gyakori ( k1 )-elemhalmazpárok egyesítésével állítjuk elő, ezért egy kiegészítő lépésre még szükség van a jelöltek nyeséséhez, ugyanis meg kell győződni arról is, hogy a jelöltek maradék k2 részhalmazai is gyakoriak-e.

A támogatottsági szint kiszámítása

A támogatottsági szint kiszámítása során megállapítjuk minden elemhalmazjelölt előfordulási gyakoriságát. Ez a művelet csak azon jelöltekre vonatkozik, melyek túljutottak az Apriori-Gen függvény nyesési lépésén. A támogatottsági szint kiszámítása a 6.1. algoritmusban a 6--11. sorokban található. Az egyik megközelítés az lehet, hogy minden tranzakció t összehasonlítunk az összes elemhalmazjelölt tel (lásd a 6.2. ábrát), és ha egy jelölt szerepel a tranzakció ban, akkor megnöveljük a jelölt támogatottság i szintjét. Ez a módszer azonban nagyon számításigényes, különösen akkor, ha a tranzakció k és az elemhalmazjelölt ek nagy számban vannak jelen.

Egy másik megközelítés során minden egyes tranzakció esetén felsoroljuk a tranzakció ban szereplő összes elemhalmazt, majd megnöveljük az ezeknek megfelelő elemhalmazjelöltek támogatottsági szintjét. Vegyünk például egy t tranzakció t, amely öt elemet tartalmaz: {1,2,3,5,6} . Ebben a tranzakció ban összesen ( 5 3 )=10 darab 3- elemhalmazjelölt szerepel. Ezen elemhalmaz ok közül elképzelhető, hogy néhány megfelel az éppen vizsgált 3- elemhalmazjelölt ek valamelyikének. Ebben az esetben megnöveljük ezen elemhalmazjelöltek támogatottsági szintjét. A t azon részhalmazait, melyek egyetlen jelöltnek sem felelnek meg, egyszerűen figyelmen kívül hagyjuk.

A 6.9. ábra a t -ben szereplő 3-elemhalmazok egy szisztematikus felsorolását szemlélteti. Ha feltesszük, hogy az elemhalmazokban szereplő elemek lexikografikusan növekvő sorrendben helyezkednek el, akkor egy elemhalmazt úgy is elő lehet állítani, hogy megadjuk a legkisebb elemét, majd az ezt követő nagyobb elemeket. Például adott t={1,2,3,5,6} esetén a t -ben található 3-elemhalmazoknak 1-gyel, 2-vel, vagy 3-mal kell kezdődniük. Olyan 3- elemhalmaz t nem lehet előállítani, amely 5-tel vagy 6-tal kezdődik, mivel t -ben csupán két olyan elem van, melyek nagyobbak vagy egyenlők 5-tel. A t -ben található 3-elemhalmazok első elemét háromféleképpen lehet megadni, ezt a 6.9. ábrán látható prefix struktúra első szintje szemlélteti. Például az 1 2  3  5  6 egy olyan 3-elemhalmazt jelöl, mely 1-gyel kezdődik, s ezt további két elem követi a {2,3,5,6} halmazból.

6.9. ábra - A t tranzakció három elemet tartalmazó részhalmazainak felsorolása

A t tranzakció három elemet tartalmazó részhalmazainak felsorolása

Az első elem rögzítése után a prefix struktúra 2. szintje azt mutatja, hogy hányféleképpen lehet kiválasztani a második elemet. Például az 1 2 3  5  6 azon elemhalmaz okat jelöli, melyek (1  2) -vel kezdődnek és vagy 3-mal, vagy 5-tel, vagy 6-tal folytatódnak. Végül a prefix struktúra 3. szintjén láthatjuk a t -ben található összes 3-elemhalmazt. Például {1  2} -vel három darab 3-elemhalmaz kezdődik ( {1,2,3} , {1,2,5} , {1,2,6} ), {2  3} -mal pedig kettő ( {2,3,5} , {2,3,6} ).

A 6.9. ábrán látható prefix struktúra azt szemlélteti, hogy hogyan lehet egy tranzakció elemhalmazait szisztematikusan felsorolni. Ehhez meg kell adni az elemhalmazok elemeit egyenként, a bal szélső elemtől kezdve a jobb szélsőig. Hátra van még annak a megállapítása, hogy a felsorolt 3-elemhalmazok megegyeznek-e valamely létező elemhalmazjelölttel. Egyezés esetén a megfelelő jelölt támogatottság i értékét megnöveljük. A következő szakaszban azt mutatjuk be, hogy ezt az összeillesztési műveletet hogyan lehet hatékonyan megoldani hasítófa (hash tree) alkalmazásával.

Támogatottság i szint kiszámítása hasítófa használatával

Az Apriori algoritmusban az elemhalmazjelölteket különböző kosarakba soroljuk, majd egy hasítófában tároljuk le őket. A támogatottság i szint kiszámításakor a tranzakció kban található elemhalmazokat is a nekik megfelelő kosarakba soroljuk be. Így ahelyett, hogy egy tranzakció minden egyes elemhalmaz át összehasonlítanánk az összes elemhalmazjelölttel, elegendő csak egyetlen kosár elemhalmazjelöltjeivel összevetni az elemhalmazokat (lásd a 6.10. ábrát).

6.10. ábra - Elemhalmazok támogatottságának a kiszámítása hasítóstruktúra segítségével

Elemhalmazok támogatottságának a kiszámítása hasítóstruktúra segítségével

A 6.11. ábra egy hasítófa-struktúrára mutat példát. A fa belső csomópontjai a h(p)=p  mod  3 hasító függvény t használják, mely azt határozza meg, hogy az adott csomópontban mely ágat kell követni a következő lépésben. Az 1-es, 4-es és 7-es elemek például ugyanabba az ágba (a bal szélső ágba) kerülnek, mivel 3-mal osztva ugyanazt a maradékot adják. Az elemhalmazjelöltek a hasítófa levélcsúcsaiban helyezkednek el. A 6.11. ábrán látható hasítófában 15 darab 3-elemhalmazjelölt látható, melyek 9 levélcsúcsra lettek szétosztva.

6.11. ábra - Tranzakció szétosztása egy hasítófa gyökércsúcsánal

Tranzakció szétosztása egy hasítófa gyökércsúcsánal

6.12. ábra - Részhalmaz művelet egy jelölteket tartalmazó hasítófa gyökerének bal szelső részfáján

Részhalmaz művelet egy jelölteket tartalmazó hasítófa gyökerének bal szelső részfáján

Vegyük a t={1,2,3,5,6} tranzakció t. Az elemhalmazjelöltek támogatottság i szintjének a módosításához a hasítófát úgy kell bejárni, hogy legalább egyszer érintsük mindazon levélcsúcsokat, melyek a t tranzakció hoz tartozó 3-elemhalmazjelölteket tartalmazzák. Emlékezzünk, hogy a t -ben található 3-elemhalmazoknak 1-gyel, 2-vel, vagy 3-mal kell kezdődniük (lásd a 6.9. ábra prefixstruktúráját az 1. szinten). Emiatt a hasítófa gyökércsúcsában a tranzakció 1-es, 2-es és 3-as elemeire külön-külön alkalmazzuk a hasító függvény t. A hasítás során az 1-es elem a gyökércsúcs bal gyermekéhez, a 2-es elem középre, míg a 3-as elem a jobboldali gyermekhez kerül. A fa következő szintjén a tranzakció t a második elemnél hasítjuk (lásd a 6.9. ábra második szintjét). Például miután az 1-es elemet hasítottuk a gyökércsúcsnál, ezt követően a 2-es, 3-as, illetve 5-ös elemeket hasítjuk. A 2-es és 5-ös elemek a középső gyermekhez, míg a 3-as elem a hasítás során a jobboldali gyermekhez kerül (lásd 6.12. ábrát). Ez a művelet addig folytatódik, míg el nem érjük a hasítófa levélcsúcsait. Ekkor a levélcsúcsban tárolt elemhalmazjelölteket összehasonlítjuk a tranzakció val. Ha egy jelölt a tranzakció részhalmaza, akkor a támogatottsági szintjét megnöveljük. Ebben a példában a 9 levélcsúcsból 5-öt kell végigjárni, s a 15 elemhalmazból 9-et kell összehasonlítani a tranzakció val.

Számítási bonyolultság

Az Apriori algoritmus számítási bonyolultságát a következő tényezők befolyásolhatják.

Támogatottság i küszöbérték

A támogatottság i küszöbérték csökkentése során gyakran megnő a gyakori elemhalmazok száma. Az algoritmus számítási bonyolultságára ez kedvezőtlenül hat, mivel több elemhalmazjelöltet kell kezelni (lásd a 6.13. ábrát). Alacsonyabb támogatottság i küszöbérték esetén a gyakori elemhalmazok maximális mérete is növekedést mutat. Amint ez az érték nő, az algoritmusnak több alkalommal kell végigolvasnia az adathalmazt.

6.13. ábra - A támogatottsági küszöbérték hatása az elemhamazjelöltek és gyakori elemhalmazok számának alakulására

A támogatottsági küszöbérték hatása az elemhamazjelöltek és gyakori elemhalmazok számának alakulására

Elemek száma (dimenzió)

Az elemszám növekedésével több tárterületre van szükség az elemek támogatottság i szintjének a tárolásához. Ha az adatok méretével együtt a gyakori elemek száma is nő, akkor a számítási és I/O költségek is megnőnek, mivel az algoritmusnak több elemhalmazjelöltet kell előállítania.

Tranzakció k száma

Mivel az Apriori algoritmusnak egy adathalmazt többször is végig kell olvasnia, ezért a több tranzakció hosszabb futási időt eredményez.

6.14. ábra - Effect of average transaction width on the number of candidate and frequent itemsets.

Effect of average transaction width on the number of candidate and frequent itemsets.

Tranzakció k átlagos szélessége

Sűrű adathalmazokban a tranzakció k átlagos szélessége nagyon nagy lehet. Ez kétféleképpen befolyásolja az Apriori algoritmus bonyolultságát. Egyrészt a tranzakció k átlagos szélességének a növekedése megnöveli a gyakori elemhalmazok maximális méretét. Ennek eredményeképpen a jelöltek generálása és a jelöltek támogatottság i szintjének a megállapítása során több elemhalmazjelöltet kell megvizsgálni (lásd a 6.14. ábrát). Másodsorban, ha nő a tranzakció k szélessége, akkor a tranzakció k több elemhalmazt tartalmaznak. A támogatottság i szint kiszámításakor ez megnöveli a hasítófákban történő bejárások számát.

A következőkben az Apriori algoritmus időbonyolultságának részletes elemzése következik.

Gyakori 1-elemhalmazok előállítása

Minden tranzakció esetében meg kell növelni a tranzakció ban szereplő elemek támogatottsági szintjét. Feltéve, hogy a tranzakció k átlagos szélessége w , ehhez a művelethez O(Nw) idő szükséges, ahol N a tranzakció k számát jelöli.

Jelöltek előállítása

A k -elemhalmazjelöltek előállításához gyakori ( k1 )-elemhalmazpárokat vonunk össze, és teszteljük, hogy rendelkeznek-e legalább k2 közös elemmel. Egy-egy összevonási művelet legfeljebb k2 egyenlőségi összehasonlítást igényel. A legjobb esetben minden összevonási művelet egy értékes k -elemhalmazjelöltet eredményez. A legrosszabb esetben az algoritmus nak az előző iterációban talált összes gyakori ( k1 )-elemhalmazpárt össze kell vonnia. Emiatt a gyakori elemhalmazok összevonásának teljes költségére fennáll, hogy:

k=2 w (k2)| C k |  összevonásköltsége   k=2 w (k2)| F k1 | 2 .

A jelöltek előállítása során az elemhalmazjelöltek tárolására egy hasítófát is létrehozunk. Mivel a fa maximális mélysége k , ezért a hasítófa elemhalmazjelölt ekkel való feltöltési költsége O( k=2 w k| C k |) . A jelöltek nyesése során minden k -elemhalmazjelölt esetén le kell ellenőrizni, hogy a k2 elemű részhalmazaik gyakoriak-e. Mivel egy jelölt keresési költsége a hasítófában O(k) , a jelöltek nyeséséhez O( k=2 w k(k2)| C k |) idő szükséges.

Támogatottság i szint kiszámítása

Minden |t| hosszúságú tranzakció ból ( |t| k ) darab k méretű elemhalmaz állítható elő. Ez megegyezik a tranzakció nkénti hasítófa-bejárások tényleges számával. A támogatottsági szint kiszámítási költsége O(N k ( w k ) α k ) , ahol w a maximális tranzakció szélességet, α k pedig azt a költséget jelöli, mely a k -elemhalmazjelöltek támogatottsági szintjének növeléséhez kell a hasítófában.