Számos asszociációelemző algoritmus teljesítményét befolyásolja a bemeneti adatok összetétele. Az Apriori algoritmus számítási bonyolultsága például olyan jellemzőktől függ, mint az adatokban lévő elemek száma és a tranzakció k átlagos szélessége. Ebben a szakaszban egy másik fontos jellemzőt vizsgálunk meg, melynek jelentős hatása van az asszociációelemző algoritmusok teljesítményére, illetve a kinyert mintázatok minőségére. Egészen pontosan azon adathalmazokra koncentrálunk, melyekben a támogatottság eloszlása aszimmetrikus. Ezekben az adathalmazokban az elemek többségének aránylag alacsony vagy közepes a gyakorisága, néhány elem gyakorisága viszont nagyon magas.

A 6.29. ábrán egy ilyen eloszlással rendelkező valós adathalmazra láthatunk példát. Az adathalmaz, melyet a PUMS (Public Use Microdata Sample) népszámlálási adatbázisból vettünk, 49046 rekordot és 2113 aszimmetrikus bináris változót tartalmaz. Az alfejezet hátralévő részében az aszimmetrikus bináris változókat elemekként, a rekordokat pedig tranzakció kként fogjuk kezelni. Bár az elemek több mint 80%-ának a támogatottsága kevesebb, mint 1%, egy részüknek a támogatottsága nagyobb, mint 90%. A támogatottság szerinti aszimmetrikus eloszlás gyakori elemhalmazokra kifejtett hatását úgy szemléltetjük, hogy az elemeket támogatottsági szintjük alapján három csoportba soroljuk: G 1 , G 2 , és G 3 . Az egyes csoportokba tartozó elemek számát a 6.21. táblázat mutatja.

Ezen adathalmaz bányászatához a megfelelő támogatottsági küszöbérték kiválasztása nem egy egyszerű feladat. Ha a küszöbérték túl magas ( például 20%), akkor nagyon sok érdekes mintázatot elszalaszthatunk az alacsony támogatottságú mintázatok közül ( G 1 csoport). A bevásárlókosarak elemzése esetén az ilyen alacsony támogatottságú mintázatok olyan drága termékek is lehetnek ( például ékszerek), melyeket csak ritkán vesznek a vásárlók, ugyanakkor ezek a mintázatok érdekesek lehetnek a viszonteladók számára. Ezzel szemben, ha a küszöbértékeket túl alacsonyra állítjuk, akkor az asszociációs mintázatokat a következő okok miatt nehezen tudjuk megtalálni. Először is, a jelenlegi asszociációelemző algoritmusok számítási- és memóriaigényei jelentősen megnőnek alacsony támogatottsági küszöbérték esetén. Másodszor, alacsony küszöbérték mellett a kinyert mintázatok száma is jelentősen megnő. Harmadszor, számos hamis mintázatot is kinyerhetünk, melyekben egy magas gyakoriságú elem ( például tej) összefüggésben áll egy alacsony gyakoriságú elemmel ( például kaviár). Az ilyen mintázatokat kereszttámogatott (cross-support) mintázatoknak hívjuk. Ezek a mintázatok valószínűleg félrevezetőek, ugyanis korrelációjuk általában gyenge. Például 0,05% támogatottsági küszöbérték esetén 18 847 olyan gyakori mintázat van, ahol az elemek G 1 -ből vagy G 3 -ból származnak. Ezeknek 93%-a kereszttámogatott mintázat, vagyis olyan mintázat mely G 1 -ből és G 3 -ból is tartalmaz elemeket. A kereszttámogatott mintázatok maximális korrelációja 0,029. Ez az érték sokkal kevesebb, mint az azonos csoportból származó elemeket tartalmazó mintázatok maximális korrelációja (ami az 1,0 értéket is eléri). Hasonló állítást lehetne tenni az előző szakaszokban bemutatott további érdekességi mértékekről is. Ez a példa azt mutatta meg, hogy nagyszámú gyengén korreláló kereszttámogatott mintázatot kaphatunk, ha a támogatottsági küszöbérték megfelelően alacsony. Mielőtt bemutatnák egy módszertant ezen mintázatok kizárására, formálisan is definiáljuk a kereszttámogatott mintázatok fogalmát.

6.9. Definíció

(Kereszttámogatott mintázat) Egy kereszttámogatott mintázat olyan X = { i 1 , i 2 ,…, i k } elemhalmaz, melynek

r(X)= min[s( i 1 ),s( i 2 ),…,s( i k )] max[s( i 1 ),s( i 2 ),…,s( i k )] (6.13)

támogatottsági aránya kisebb, mint a felhasználó által megadott h c küszöbérték.

6.4. Példa.

Tegyük fel, hogy a tej támogatottsága 70%, a cukoré 10%, a kaviáré pedig 0,04%. Ha h c =0,01 , akkor a {tej,cukor,kaviár} gyakori elemhalmaz kereszttámogatott mintázat, hiszen támogatottsági aránya

r= min[0,7;0,1;0,0004] max[0,7;0,1;0,0004] = 0,0004 0,7 =0,00058≤0,01.

A meglevő mértékek (mint például a támogatottság és a megbízhatóság) nem feltétlenül elegendők a kereszttámogatott mintázatok kizárására, amint azt a 6.30. ábrán szereplő adathalmazon látni fogjuk. Ha h c =0,3 , akkor a {p,q} , {p,r} és {p,q,r} elemhalmazok kereszttámogatott mintázatok, ugyanis a támogatottsági arányuk (0,2) kevesebb, mint a h c küszöbérték. Bár a kereszttámogatott mintázatok kizárására alkalmazhatnánk egy magas támogatottsági küszöbértéket is ( például 20%), de ez azzal a hátránnyal járna, hogy olyan érdekes mintázatokat is kizárnánk, mint például az erősen korreláló {q,r} elemhalmaz (melynek a támogatottsága 16,7%).

A megbízhatóságon alapuló nyesés sem segít, mivel a kereszttámogatott mintázatokból kinyert szabály ok megbízhatósága nagyon magas lehet. Például a {q}→{p} megbízhatósága 80%, miközben a {p,q} egy kereszttámogatott mintázat. Az a tény, hogy a kereszttámogatott mintázatokból magas megbízhatóságú szabály okat lehet kinyerni, végső soron nem meglepő, hiszen a mintázat egyik eleme ( p ) nagy gyakorisággal szerepel az adathalmazban. Ebből következik, hogy p sok olyan tranzakcióban is előfordul, amelyben q szerepel. Ugyanakkor a {q}→{r} szabály is magas megbízhatóságú annak ellenére, hogy a {q,r} nem kereszttámogatott mintázat. Ez a példa jól mutatja, hogy a megbízhatósági mérték használatával nem egyszerű megkülönböztetni a kereszttámogatott és a nem kereszttámogatott mintázatokból előállított szabályokat.

Visszatérve az előző példára, vegyük észre, hogy a {p}→{q} szabály megbízhatósága nagyon alacsony. Ez azért van, mert a p -t tartalmazó tranzakció k többsége nem tartalmazza a q -t. Ezzel szemben a {q,r} mintázatból előállított {r}→{q} szabály megbízhatósága nagyon magas. Ez a megfigyelés azt sugallja, hogy a kereszttámogatott mintázatokat úgy is felfedezhetjük, ha az adott elemhalmazból kinyerhető szabály ok közül a legalacsonyabb megbízhatóságút vizsgáljuk meg. Ezen állítás bizonyítását a következőképpen érthetjük meg.

c({ i 1 i 2 }→{ i 3 , i 4 ,…, i k })≤c({ i 1 i 2 i 3 }→{ i 4 , i 5 ,…, i k }).

Ezen tulajdonság szerint a megbízhatóság nem nő, ha egy asszociációs szabály ban az elemeket a szabály bal oldaláról a szabály jobb oldalára helyezzük át. Ebből a jellemzőből az következik, hogy egy gyakori elemhalmaz ból előállítható szabály ok közül a legkisebb megbízhatóságúnak csupán egy eleme van a szabály bal oldalán. R 1 -gyel jelöljük azon szabály ok halmazát, melyeknek a bal oldalán csak egy elem szerepel.

{ i j }→{ i 1 , i 2 ,…, i j−1 , i j+1 ,…, i k }

szabály nak van a legkisebb megbízhatósága R 1 -ben, ha s( i j )=max[s( i 1 ),s( i 2 ),…,s( i k )] . Ez egyenesen a megbízhatóság definíciójából következik, mely nem más, mint a szabály támogatottsága és a szabály feltételi oldalának a támogatottság a közti arány.

s({ i 1 , i 2 ,…, i k }) max[s( i 1 ),s( i 2 ),…,s( i k )] .

Ezt a kifejezést úgy is nevezzük mint teljes-bizonyosság (h-confidence vagy all-confidence) mérték. A támogatottság antimonoton jellemzője miatt a teljes-bizonyosság mérték számlálóját korlátozza a gyakori elemhalmaz ban szereplő elemek legkisebb támogatottsága. Másképpen fogalmazva, egy X={ i 1 , i 2 ,…, i k } elemhalmaz teljes-bizonyossága nem lehet nagyobb a következő kifejezés értékénél:

teljes−bizonyosság(X)≤ min[s( i 1 ),s( i 2 ),…,s( i k )] max[s( i 1 ),s( i 2 ),…,s( i k )] .

Megjegyezzük, hogy a teljes-bizonyosság felső korlátja és a (6.13) egyenlet támogatottsági aránya ( r ) egymással ekvivalens. Mivel egy kereszttámogatott mintázat támogatottsági aránya mindig kisebb, mint h c , ezért a mintázat teljes-bizonyossága is biztosan kisebb, mint h c .

Vagyis a kereszttámogatott mintázatok kizárhatók, ha a mintázatok teljes-bizonyosság értékei túllépik a h c értéket. Végül megjegyezzük, hogy a teljes-bizonyosság használatának előnyei túlmutatnak a kereszttámogatott mintázatok kizárásán. Ez a mérték szintén antimonoton, azaz

teljes−bizonyosság({ i 1 , i 2 ,…, i k })≥teljes−bizonyosság({ i 1 , i 2 ,…, i k+1 }),

így közvetlenül is beépíthető az adatbányászati algoritmusokba. Ezen túlmenően a teljes-bizonyosság azt is biztosítja, hogy egy elemhalmazban található elemek erősen korreláljanak egymással. Tegyük fel például, hogy egy X elemhalmaz teljes-bizonyossága 80%. Ha X egy eleme szerepel egy tranzakcióban, akkor legalább 80% az esélye annak, hogy X többi eleme is szerepel ugyanabban a tranzakcióban. Az ilyen erősen kapcsolódó mintázatokat hiperklikk mintázatoknak nevezzük.