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).

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,Y∈J:  (X⊆Y)→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,Y∈J:  (X⊆Y)→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.

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.

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:

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.

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:

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 k−m 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:

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 d−1 ) .

F k−1 × F 1 módszer

A jelöltek előállítására egy másik módszer, ha minden gyakori (k−1) -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 k−1 |×| 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 k−1 || F 1 |) .

Az eljárás teljes, mivel minden gyakori k -elemhalmaz egy gyakori (k−1) -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 ( k−1 )-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 k−1 darab gyakori ( k−1 )-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 k−1 × F k−1 módszer

Az Apriori-Gen függvény ben szereplő módszer a jelölteket gyakori ( k−1 )-elemhalmazpárok egyesítésével állítja elő. Az egyesítést csak akkor kell végrehajtani, ha az elemhalmazpárok első k−2 elemei azonosak. Legyen A={ a 1 , a 2 ,…, a k−1 } és B={ b 1 , b 2 ,…, b k−1 } egy gyakori ( k−1 )-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,…,k−2, ésa k−1 ≠ b k−1 .

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 ( k−1 )-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 k−2 részhalmazai is gyakoriak-e.

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.

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).

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.

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.

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.

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.

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 ( k−1 )-elemhalmazpárokat vonunk össze, és teszteljük, hogy rendelkeznek-e legalább k−2 közös elemmel. Egy-egy összevonási művelet legfeljebb k−2 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 ( k−1 )-elemhalmazpárt össze kell vonnia. Emiatt a gyakori elemhalmazok összevonásának teljes költségére fennáll, hogy:

∑ k=2 w (k−2)| C k |≤  összevonásköltsége  ≤ ∑ k=2 w (k−2)| F k−1 | 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 k−2 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(k−2)| 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.