Ritka mintázatok

Az eddigiekben leírt asszociációs elemzési szabályrendszer alapját az a feltevés képezi, hogy egy elem jelenléte egy tranzakcióban fontosabb, mint a hiánya. Ennek következményeképpen az adatbázisban ritkán fellelhető mintázatokat gyakran nem tekintjük érdekesnek és a támogatottsági mérték segítségével eltávolítjuk. Az ilyen mintázatokat nevezzük ritka mintázatoknak.

7.7. Definíció

(Ritka mintázat) A ritka mintázat egy olyan elemhalmaz vagy szabály, melynek a minsup küszöbértéknél kisebb a támogatottsága.

Bár a ritka mintázatok túlnyomó többsége nem érdekes, néhányuk az elemzők hasznára válhat, főleg azok, amelyek az adatokban fellelhető negatív korrelációkhoz kapcsolódnak. Például a DVD-k és videomagnók együttes vásárlásainak száma alacsony, mert az olyan vásárló, aki megvesz egy DVD-t, valószínűleg nem fog videomagnót venni, és fordítva. Az ilyen negatív korrelációs mintázatok segíthetnek a versenyző termékek, azaz egymással helyettesíthető termékek azonosításában. Ilyen versenyző termékek például a tea és a kávé, a vaj és a margarin, a normál és a cukormentes üdítők, vagy az asztali számítógépek és a laptopok.

Egyes ritka mintázatok megléte érdekes ritka események vagy rendkívüli állapotok előfordulására utalhat az adatállományban. Ha például a {Tűz = igen} gyakori, de a {Tűz = igen, Riasztó = bekapcsolva} ritka, akkor ez utóbbi egy érdekes ritka mintázat, mert jelezheti a riasztórendszerek meghibásodását. Az ilyen szokatlan helyzetek észleléséhez meg kell határoznunk a mintázat várható támogatottságát, így ha a mintázatnak jelentősen alacsonyabb a támogatottsága, mint amire számítottunk, kijelenthetjük, hogy egy érdekes ritka mintázattal van dolgunk.

A ritka mintázatok bányászata komoly kihívást jelent, mivel az ilyen mintázatok hatalmas mennyiségben nyerhetőek ki az adatállományokból. Konkrétabban, a ritka mintázatok bányászatának kulcsproblémái a következők: (1) hogyan azonosítsuk az érdekes ritka mintázatokat, és (2) hogyan tárjuk fel őket hatékonyan nagy adatállományokban. Hogy más szemszögből is lássuk az érdekes ritka mintázatok különböző típusait, két kapcsolódó fogalmat -- a negatív mintázatokat és a negatívan korrelált mintázatokat -- mutatunk be a 7.6.1. illetve a 7.6.2. szakaszokban, majd ezen mintázatok kapcsolatait a 7.6.3. szakaszban tisztázzuk. Végül két, ritka mintázatok bányászatához kifejlesztett módszertant mutatunk be a 7.6.5. és 7.6.6. szakaszokban.

Negatív mintázatok

Legyen I={ i 1 , i 2 ,, i d } egy elemhalmaz. Egy i k Ż negatív elem az i k elem hiányát jelöli az adott tranzakcióban. Például a kávé Ż egy negatív elem, melynek értéke 1, ha a tranzakció nem tartalmazza a kávét.

7.8. Definíció

(Negatív elemhalmaz) Az X negatív elemhalmaz egy olyan elemhalmaz, amely rendelkezik a következő tulajdonságokkal: (1) X=A B Ż , ahol A egy pozitív elemekből álló halmaz, B Ż pedig egy negatív elemekből álló halmaz, | B Ż |1 , és (2) s(X)minsup .

7.9. Definíció

(Negatív asszociációs szabály) A negatív asszociációs szabály egy olyan asszociációs szabály, amely rendelkezik a következő tulajdonságokkal: (1) a szabályt egy negatív elemhalmazból nyerjük, (2) a szabály támogatottsága nagyobb vagy egyenlő, mint minsup , és (3) a szabály megbízhatósága nagyobb vagy egyenlő, mint minconf .

A fejezet további részében a negatív elemhalmazokat és negatív asszociációs szabályokat együttesen negatív mintázatoknak nevezzük. Negatív asszociációs szabály például a tea kávé Ż , ami arra utalhat, hogy akik teáznak, azok általában nem isznak kávét.

Negatívan korrelált mintázatok

A 382. oldalon található 6.7.1. szakaszban tárgyaltuk, hogy hogyan használhatunk korrelációanalízist két kategorikus változó kapcsolatának elemzésére. A pozitívan korrelált elemhalmazok feltárásához hasznosnak bizonyultak az olyan mértékek, mint például az érdekességi tényező ((6.5) egyenlet) és a ϕ -együttható ((6.8) egyenlet). Ebben a szakaszban kiterjesztjük ezek tárgyalását negatívan korrelált mintázatokra.

Jelöljön X={ x 1 , x 2 ,, x k } egy k -elemhalmazt, P(X) pedig jelölje annak valószínűségét, hogy egy tranzakció tartalmazza X -et. Asszociációs elemzés során a valószínűséget gyakran az elemhalmaz támogatottságával, s(X) -szel becsüljük.

7.10. Definíció

(Negatívan korrelált elemhalmaz) Egy X elemhalmaz negatívan korrelált, ha

s(X) j=1 k s( x j )=s( x 1 )×s( x 2 )××s( x k ), (7.3)

ahol s( x j ) az x j elem támogatottsága.

A fenti kifejezés jobb oldala, j=1 k s( x j ) egy becslést ad annak valószínűségére, hogy X minden eleme statisztikailag független. A 7.10. definíció azt állítja, hogy egy elemhalmaz negatívan korrelált, ha a várható támogatottságnál kisebb a támogatottsága, melyet a statisztikai függetlenség feltételezése mellett számítunk ki. Minél kisebb s(X) , annál erősebb negatív korreláció van jelen a mintázatban.

7.11. Definíció

(Negatívan korrelált asszociációs szabály) Egy XY asszociációs szabály negatívan korrelált, ha

s(X Y)s(X)s(Y), (7.4)

ahol X és Y diszjunkt elemhalmazok, azaz X Y= .

Az előző definíció csak részben adja meg az X elemei és Y elemei közötti negatív korreláció feltételét. A negatív korreláció teljes feltételét a következőképpen határozhatjuk meg:

s(X Y) i s( x i ) j s( y j ), (7.5)

ahol x i X és y j Y . Mivel X (és Y ) elemei gyakran pozitívan korreláltak, az asszociációs szabályok negatív korrelációjának leírására célszerűbb a parciális feltételt használni, mint a teljes feltételt. Például, bár a

{szemüveg, lencsetisztító}{kontaktlencse, sóoldat}

szabály a (7.4) egyenlőtlenség alapján negatívan korrelált, a szemüveg és a lencsetisztító, illetve a kontaktlencse és a sóoldat pozitívan korreláltak. Ha inkább a (7.5) egyenlőtlenséget alkalmazzuk, elmulaszthatjuk az ilyen szabályokat, mert nem biztos, hogy teljesítik a negatív korreláció teljes feltételét.

A negatív korreláció feltételét kifejezhetjük a pozitív és negatív elemhalmazok támogatottságával is. Jelölje X Ż és Y Ż az X -hez illetve az Y -hoz tartozó negatív elemhalmazokat. Mivel

s(X Y)s(X)s(Y)

=s(X Y)[s(X Y)+s(X Y Ż )][s(X Y)+s( X Ż Y)]

=s(X Y)[1s(X Y)s(X Y Ż )s( X Ż Y)]s(X Y Ż )s( X Ż Y)

=s(X Y)s( X Ż Y Ż )s(X Y Ż )s( X Ż Y),

a negatív korreláció feltételét a következőképpen írhatjuk fel:

s(X Y)s( X Ż Y Ż )s(X Y Ż )s( X Ż Y). (7.6)

A fejezet további részében a negatív elemhalmazokat és a negatív asszociációs szabályokat együttesen negatívan korrelált mintázatoknak nevezzük.

A ritka mintázatok, a negatív mintázatok és a negatívan korrelált mintázatok összehasonlítása

A ritka mintázatok, a negatív mintázatok és a negatívan korrelált mintázatok fogalmai közeli rokonságban állnak egymással. Bár a ritka mintázatok és a negatívan korrelált mintázatok csak olyan elemhalmazokra vagy szabályokra utalnak, amelyek elemei pozitívak, míg a negatív mintázatok olyan elemhalmazokra vagy szabályokra, amelyek elemei között pozitívak és negatívak is találhatóak, mégis felfedezhetőek bizonyos hasonlóságok ezen fogalmak között, mint ahogy azt a 7.22. ábra is mutatja.

7.22. ábra - A ritka mintázatok, a negatív mintázatok és a negatívan korrelált mintázatok összehasonlítása

A ritka mintázatok, a negatív mintázatok és a negatívan korrelált mintázatok összehasonlítása

Először fontos megjegyezni, hogy sok ritka mintázathoz létezik hozzá tartozó negatív mintázat. Hogy megértsük, miért van így, tekintsük a 7.9. táblázatot. Ha az X Y ritka, akkor valószínűleg tartozik hozzá egy negatív mintázat, hacsak minsup nem túl nagy. Ha például feltételezzük, hogy minsup0.25 , akkor, ha X Y ritka, az X Y Ż , X Ż Y vagy X Ż Y Ż elemhalmazok közül legalább egy támogatottságának nagyobbnak kell lennie, mint minsup , mivel a kontingenciatáblázatban a támogatottságok összege 1.

7.9. táblázat - Kétdimenziós kontingenciatáblázat az XY asszociációs szabályhoz

Y

Y Ż

X

s(X Y)

s(X Y Ż )

s(X)

X Ż

s( X Ż Y)

s( X Ż Y Ż )

s( X Ż )

s(Y)

s( Y Ż )

1


Másodjára azt is vegyük észre, hogy sok negatívan korrelált mintázathoz is tartozik negatív mintázat. Tekintsük a 7.9. kontingenciatáblázatot és a negatív korreláció a (7.6) egyenlőtlenségben meghatározott feltételét. Ha X és Y között erős a negatív korreláció, akkor

s(X Y Ż )×s( X Ż Y)?s(X Y)×s( X Ż Y Ż ).

Így vagy X Y Ż , vagy X Ż Y , vagy mindkettő támogatottsága viszonylag nagy, ha X és Y negatívan korreláltak. Ezek az elemhalmazok negatív mintázatok.

Végül, mivel minél kisebb X Y támogatottsága, annál erősebb a mintázat negatív korrelációja, általában érdekesebbek azok a negatívan korrelált mintázatok, amelyek ritkák, mint azok a negatívan korrelált mintázatok, amelyek gyakoriak. A ritka negatívan korrelált mintázatokat a 7.22. ábrán a két mintázat típus területeinek metszete reprezentálja.

Az érdekes ritka mintázatok bányászatának módszerei

Elméletileg a ritka elemhalmazokat az összes olyan elemhalmaz jelenti, melyeket a standard gyakori elemhalmazokat generáló algoritmusok, mint például az Apriori vagy az FP-bővítés, nem nyernek ki. Ezek azok az elemhalmazok, amelyek a 7.23. ábrán jelölt gyakori elemhalmaz határvonal alatt helyezkednek el.

7.23. ábra - Gyakori és ritka elemhalmazok

Gyakori és ritka elemhalmazok

A ritka mintázatok száma exponenciálisan nagy lehet, főleg ritka, magas dimenziós adatok esetén, ezért a ritka mintázatok bányászatához kifejlesztett módszerek főleg arra koncentrálnak, hogy csak azokat a ritka mintázatokat adják vissza, amelyek érdekesek. Ilyen mintázatok például a 7.6.2. szakaszban tárgyalt negatívan korrelált mintázatok. Ezeket a mintázatokat úgy kapjuk, hogy kiselejtezzük az összes olyan ritka elemhalmazt, amelyek nem felelnek meg a negatív korreláció (7.3) egyenlőtlenséggel megadott feltételének. Ez a megközelítés igen számításigényes lehet, mert ahhoz, hogy meghatározhassuk, hogy negatívan korreláltak-e, ki kell számítanunk az összes ritka elemhalmaz támogatottságát. A gyakori elemhalmazokhoz használt támogatottsági mértékkel szemben a negatívan korrelált elemhalmazokhoz használt korreláció-alapú mértékek nem rendelkeznek antimonoton tulajdonsággal, amelyet kihasználhatnánk az exponenciális keresési tér nyesésére. Bár igazán hatékony megoldás még nem született, számos innovatív módszert fejlesztettek ki, melyekről említést teszünk a fejezet végén található irodalmi megjegyzésekben.

A fejezet hátralevő részében az érdekes ritka mintázatok bányászati módszereinek két típusával foglalkozunk. A 7.6.5. szakaszban a negatív mintázatok bányászatának módszereivel, a 7.6.6. szakaszban pedig az érdekes ritka mintázatok feltárásának olyan módszereivel foglalkozunk, amelyek a várható támogatottságon alapulnak.

Negatív mintázatok bányászatán alapuló módszerek

A ritka mintázatok bányászatához kifejlesztett módszerek első osztálya minden elemet szimmetrikus bináris változóként kezel. A 7.1. szakaszban leírt módszert alkalmazva binarizálhatjuk a tranzakciós adatokat úgy, hogy kiegészítjük őket negatív elemekkel. A 7.24. ábrán láthatunk egy példát olyan adatok tranzakciókká alakítására, amelyek pozitív és negatív elemeket is tartalmaznak. Ha olyan meglévő gyakori elemhalmaz bányászati algoritmusokat alkalmazunk a kiegészített tranzakciókon, mint például az Apriori, kinyerhetjük az összes negatív elemhalmazt.

7.24. ábra - Adatállományok kiegészítése negatív elemekkel

Adatállományok kiegészítése negatív elemekkel

Csak akkor tudunk ilyen megközelítést alkalmazni, ha néhány változót szimmetrikus binárisként kezelünk (azaz olyan negatív mintázatokat keresünk, amelyekben csak néhány elem negáltja szerepel). Ha minden elemet szimmetrikus binárisként kell kezelnünk, a következő okokból kezelhetetlen kiszámításílag a feladat :

  1. Ha minden elemet kiegészítünk a hozzá tartozó negatív elemmel, az elemszám megduplázódik. Ahelyett, hogy 2 d méretű elemhalmaz rácsot tárnánk fel, ahol d az eredeti adatállomány elemeinek száma, a rács mérete számottevően megnő, mint ahogy az a 21. feladatban is látható az 501. oldalon.

  2. A negatív elemek beillesztésével a támogatottságon alapuló nyesés elveszti hatékonyságát. Bármely x változó esetén vagy x -nek, vagy x Ż -nek nagyobb vagy egyenlő a támogatottsága, mint 50% , így még ha 50% is a támogatottsági küszöb, az elemek fele gyakori marad. Alacsonyabb küszöbértékek esetén sokkal több elem, és valószínűleg sokkal több elemhalmaz is gyakori lesz. A támogatottság-alapú nyesési stratégia, amelyet az Apriori-ban alkalmazunk, csak akkor hatásos, ha a legtöbb elemhalmaz támogatottsága alacsony; más esetben a gyakori elemhalmazok száma exponenciálisan nő.

  3. A negatív elemek beillesztésével minden tranzakció szélessége megnő. Tegyük fel, hogy az eredeti adatállományban d elem található. Az olyan ritka adatállományok esetén, mint például a bevásárlókosár tranzakciók, a tranzakciók szélessége általában jóval kisebb d -nél. Ennek következtében általában viszonylag kicsi a gyakori elemhalmazok maximális mérete, melynek felső korlátja a tranzakciók w max maximális szélessége. Amikor negatív elemeket is felveszünk, a tranzakciók mérete d -re növekszik, mert egy elem vagy jelen van a tranzakcióban, vagy hiányzik belőle, de egyszerre mindkettő nem lehetséges. Mivel így a tranzakciók maximális szélessége w max -ról d -re nő, ennek hatására a gyakori elemhalmazok száma exponenciális növekedésnek indul. Ennek következtében sok meglévő algoritmus összeomlik, amikor a kiegészített adatállományra próbáljuk alkalmazni.

Az előzőekben kifejtett nyers erőn alapuló megközelítés nagy számításigényű, mert arra kényszerít, hogy nagy mennyiségű pozitív és negatív mintázat támogatottságát határozzuk meg. Az adatállomány negatív elemekkel történő kiegészítése helyett egy másik megközelítés lehet a negatív elemhalmazok támogatottságának meghatározása a hozzájuk tartozó pozitív elemek támogatottsága alapján. Például {p, q Ż , r Ż } támogatottságát a következőképpen számíthatjuk ki:

s({p, q Ż , r Ż })=s({p})s({p,q})s({p,r})+s({p,q,r}).

Általánosabban fogalmazva, bármely X Y Ż elemhalmaz támogatottságát megkaphatjuk a következő formában:

s(X Y Ż )=s(X)+ i=1 n ZY,|Z|=i { (1) i ×s(X Z)}. (7.7)

Ahhoz, hogy alkalmazni tudjuk a (7.7) egyenletet, meg kell határoznunk s(X Z) -t minden lehetséges Z -re, ahol Z az Y egy részhalmaza. Ha X és Z egy tetszőleges kombinációjának támogatottsága meghaladja minsup értékét, akkor az meghatározható az Apriori algoritmussal. Minden más kombinációra explicit módon kell meghatároznunk a támogatottságot, például a teljes tranzakcióhalmaz vizsgálatával. Egy másik lehetséges megközelítés minden X Z ritka elemhalmaz támogatottságának elvetése vagy a minsup küszöbértékkel történő közelítése.

Számos optimalizációs stratégia létezik az adatbányászati algoritmusok teljesítményének további növelésére. Először is, korlátozhatjuk a szimmetrikus binárisnak tekinthető attribútumok számát. Konkrétabban, egy y Ż negatív elemet csak akkor tartunk érdekesnek, ha y egy gyakori elem. Ez a stratégia azon alapszik, hogy a ritka elemek általában nagyobb mennyiségű ritka mintázatot generálnak, amelyek nagy része érdektelen. Ha olyan változókra korlátozzuk a (7.7) egyenletben megadott Y Ż halmazt, amelyek pozitív elemei gyakoriak, az adatbányászati algoritmusnak lényegesen kevesebb negatív elemhalmaz jelöltet kell elemeznie. Egy másik stratégia a negatív mintázatok típusának korlátozása. Az algoritmus elemezheti például csak az olyan X Y Ż negatív mintázatokat, amelyeknek legalább egy pozitív eleme van (azaz |X|1 ). Ez a stratégia azon alapszik, hogy az adatállomány nagyon kevés olyan pozitív elemet tartalmaz, amelyek támogatottsága nagyobb, mint 50% , ezért az X Ż Y Ż alakú negatív mintázatok nagy része gyakorivá válik, ezáltal a bányászati algoritmus teljesítményét rontva.

Várható támogatottságon alapuló módszerek

A módszerek egy másik típusa csak akkor tekint érdekesnek egy ritka mintázatot, ha valós támogatottsága jelentősen alacsonyabb, mint a várható támogatottsága. A negatívan korrelált mintázatok várható támogatottságát a statisztikai függetlenség feltételezése alapján számítjuk ki. Ebben a szakaszban két alternatív megközelítést mutatunk be a mintázatok várható támogatottságának meghatározására, melyek (1) fogalomhierarchiát, illetve (2) egy indirekt asszociációnak nevezett szomszédságon alapuló módszer használnak.

Fogalomhierarchián alapuló várható támogatottság

Az objektív mértékek önmagukban nem biztos, hogy elégnek bizonyulnak az érdektelen ritka mintázatok kiszűrésére. Tegyük fel például, hogy a kenyér és a laptop gyakori elemek. Bár a {kenyér, laptop} elemhalmaz ritka, és talán negatívan korrelált is, de nem érdekes, mert a támogatottságának hiánya a terület szakértői számára nyilvánvalónak tűnik. Ezért az ilyen ritka mintázatok generálásának elkerüléséhez egy szubjektív megközelítés szükséges a várható támogatottság meghatározásához.

Az előző példában a kenyér és a laptop két teljesen különböző termékkategóriába tartoznak, így nem meglepő, ha azt találjuk, hogy támogatottságuk alacsony. Ez a példa azt is szemlélteti, hogy milyen előnye van annak, ha szakterületi tudást alkalmazunk a nem érdekes mintázatok nyeséséhez. Vásárlói kosár adatokhoz megkaphatjuk ezt a szakterületi tudást egy olyan fogalomhierarchiából, mint amely például a 7.25. ábrán látható. Ennek a megközelítésnek az az alapfeltevése, hogy az ugyanabba a termékcsaládba tartozó elemek várhatóan hasonló típusú kapcsolatba kerülnek más elemekkel. Például, mivel a sonka és a szalonna ugyanabba a termékcsaládba tartoznak, azt várjuk, hogy a sonka és a chips kapcsolata némileg hasonló lesz a szalonna és a chips kapcsolatához. Ha ezen párok bármelyikének kisebb a valós támogatottsága, mint a várható támogatottsága, akkor a ritka mintázat érdekes.

7.52. ábra - Példa fogalomhierarchiára

Példa fogalomhierarchiára

7.26. ábra - Érdekes negatív mintázatok bányászata fogalomhierarchia felhasználásával

Érdekes negatív mintázatok bányászata fogalomhierarchia felhasználásával

A várható támogatottság kiszámítási módjának bemutatásához tekintsük a 7.26. ábrát. Tegyük fel, hogy a {C,G} elemhalmaz gyakori. Jelölje s() egy mintázat valódi támogatottságát, ε() pedig a várható támogatottságát. C és G bármely gyermekének vagy testvérének várható támogatottsága kiszámítható az alábbi formulákkal:

ε(s(E,J))=s(C,G)× s(E) s(C) × s(J) s(G) (7.8)

ε(s(C,J))=s(C,G)× s(J) s(G) (7.9)

ε(s(C,H))=s(C,G)× s(H) s(G) (7.10)

7.27. ábra - Két elem közötti indirekt asszociáció

Két elem közötti indirekt asszociáció

Az indirekt asszociáció egy magas szintű ábrázolását láthatjuk a 7.27. ábrán. Az a és b elemek a cukormentes üdítőitalt és a normál üdítőitalt reprezentálják, míg a közvetítőhalmaznak (mediator set) nevezett Y olyan termékeket tartalmaz, mint például a chips és a keksz. Következőekben az indirekt asszociáció egy formális definícióját adjuk meg.

7.12. Definíció

(Indirekt asszociáció) Egy (a,b) elempár elemei között indirekt asszociáció áll fenn az Y közvetítőhalmazon keresztül, ha teljesülnek a következő feltételek:

  1. s({a,b}) t s (elempár támogatottsági feltétel).

  2. Létezik Y , amelyre:

    1. s({a} Y) t f és s({b} Y) t f (közvetítő támogatottsági feltétel),

    2. d({a},Y) t d ,d({b},Y) t d , ahol d(X,Z) az X és Z közötti asszociáció egy objektív mértéke (közvetítő függőségi feltétel).

Fontos megjegyezni, hogy a közvetítő támogatottsági és függőségi feltételeket annak biztosítására alkalmazzuk, hogy Y elemei a -nak és b -nek is közeli szomszédságában helyezkedjenek el. A használható függőségi mértékek közé tartoznak az érdekességi, koszinusz, IS, Jaccard és más mértékek is, amelyekről a 382. oldalon található a 6.7.1. szakaszban ejtettünk szót.

Az indirekt asszociáció sok helyen alkalmazható. Piaci területen a és b lehetnek olyan versenyző termékek, mint például az asztali számítógépek és laptopok. A szövegbányászatban szinonimák, antonimák, vagy más kontextusokban alkalmazott szavak azonosítására használhatjuk az indirekt asszociációt. Ha például adott egy dokumentumgyűjtemény, az adat szó indirekt asszociációban állhat az arany szóval a bányászat közvetítésével. Ebből a mintázatból arra következtethetünk, hogy a bányászat szó két különböző kontextusban használható: az adatbányászat és az aranybányászat területén.

Indirekt asszociációkat a következőképpen generálhatunk. Először generáljuk a gyakori elemhalmazok halmazát egy standard algoritmussal, mint például az Apriori vagy az FP-bővítés. Ezután a gyakori k -elemhalmazokat páronként egyesítjük, így (a,b,Y) indirekt asszociáció jelölteket kapunk, ahol a és b egy elempárt alkotnak, Y pedig azok közös közvetítője. Ha például {p,q,r} és {p,q,s} gyakori 3-elemhalmazok, akkor az (r,s,{p,q}) indirekt asszociáció jelöltet kapjuk a két gyakori elemhalmaz egyesítésével. Miután generáltuk a jelölteket, ellenőriznünk kell, hogy eleget tesznek-e a 7.12. definícióban megadott elempár támogatottsági és közvetítő függőségi feltételeknek. A közvetítő támogatottsági feltételt azonban nem kell vizsgálnunk, mert az indirekt asszociáció jelölteket gyakori elemhalmazok páronkénti egyesítésével kapjuk. Az eljárás algoritmusát a 7.2. algoritmusban foglaljuk össze.

7.2. algoritmus. Indirekt asszociációkat bányászó algoritmus

1: Generáljuk F k -t, a gyakori elemhalmazok halmazát

2: for k=2 to k max do

3: C k ={(a,b,Y)|{a} Y F k ,{b} Y F k ,ab}

4: for minden (a,b,Y) C k jelöltre do

5: if s({a,b}) t s d({a},Y) t d d({b},Y) t d then

6: I k = I k {(a,b,Y)}

7: end if

8: end for

9: end for

10: Eredmény = I k