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.

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 X→Y 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)[1−s(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 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.

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 minsup≤0.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.

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.

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.

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.

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.

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 :

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 ∑ Z⊂Y,|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.

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.

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)

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:

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.