Feladatok
Vissza 6. fejezet - Asszociációs elemzés: Alapvető fogalmak és algoritmusok Előre

Feladatok

1. A következő kérdések mindegyikéhez adjunk példát egy asszociációs szabályra a bevásárlókosarak területéről. A szabályok feleljenek meg az adott feltételeknek. Azt is vizsgáljuk meg, hogy ezek a szabályok szubjektíve érdekesek-e.

  1. Magas támogatottságú és magas megbízhatóságú szabály.

  2. Viszonylag magas támogatottságú, de alacsony megbízhatóságú szabály.

  3. Alacsony támogatottságú és alacsony megbízhatóságú szabály.

  4. Alacsony támogatottságú és magas megbízhatóságú szabály.

2. Tekintsük a 6.22. táblázatban látható adathalmazt.

6.22. táblázat - Bevásárlókosár tranzakciók

vevőazonosító

tranzakcióazonosító

vásárolt cikkek

1

0001

{a,d,e}

1

0024

{a,b,c,e}

2

0012

{a,b,d,e}

2

0031

{a,c,d,e}

3

0015

{b,c,e}

3

0022

{b,d,e}

4

0029

{c,d}

4

0040

{a,b,c}

5

0033

{a,d,e}

5

0038

{a,b,e}


  1. Számítsuk ki az {e} , {b,d} és {b,d,e} elemhalmazok támogatottság át. A tranzakcióazonosítók bevásárlókosaraknak felelnek meg.

  2. Az (a) pont eredményeit felhasználva számítsuk ki a {b,d}→{e} és {e}→{b,d} asszociációs szabályok megbízhatóság át. A megbízhatóság szimmetrikus mérték?

  3. Ismételjük meg az (a) pont számításait úgy, hogy most a vevőazonosítókat tekintjük bevásárlókosaraknak. Az árucikkeket bináris változókként kezeljük (melynek értéke 1, ha az árucikk legalább egy -- a vevő által vásárolt -- tranzakcióban szerepel; különben 0).

  4. A (c) pont eredményeit felhasználva számítsuk ki a {b,d}→{e} és {e}→{b,d} asszociációs szabályok megbízhatóság át.

  5. (e) Tekintsük a tranzakcióazonosítókat bevásárlókosaraknak. Ekkor legyen az r asszociációs szabály támogatottsága s 1 , megbízhatósága pedig c 1 . Ha a vevőazonosítókat vesszük bevásárlókosaraknak, akkor legyen az r szabály támogatottság a s 2 , megbízhatósága pedig c 2 . Vizsgáljuk meg, hogy van-e valamilyen kapcsolat s 1 és s 2 , illetve c 1 és c 2 között.

3.

  1. Mi a ∅→A és A→∅ szabály ok megbízhatóság a?

  2. Legyen a {p}→{q} , {p}→{q,r} és {p,r}→{q} szabály ok megbízhatóság a c 1 , c 2 és c 3 . Ha feltesszük, hogy c 1 , c 2 és c 3 értékei eltérőek, akkor c 1 , c 2 és c 3 között milyen lehetséges összefüggések állhatnak fenn? Melyik szabálynak van a legkisebb megbízhatóság a?

  1. Tegyük fel, hogy a (b) pontban leírt három szabály támogatottság a azonos, és ismételjük meg így az előző pont számításait. Melyik szabálynak van a legnagyobb megbízhatóság a?

  1. Tranzitivitás: tegyük fel, hogy az A→B és B→C szabályok megbízhatóság a nagyobb, mint egy minconf küszöbérték. Elképzelhető-e, hogy az A→C megbízhatóság a kisebb mint a minconf érték?

4. Döntsük el, hogy az alábbi mértékek közül melyik monoton, antimonoton, vagy nem monoton (azaz se nem monoton, se nem antimonoton).

Példa: A támogatottság ( s= σ(X) |T| ) antimonoton, mivel s(X)≥s(Y) minden X⊂Y esetén.

  1. Egy karakterisztikus szabály a következőképpen néz ki: {p}→{ q 1 , q 2 ,…, q n } , vagyis a szabály feltételi oldalán csupán egyetlen elem szerepel. Egy k méretű elemhalmazból k darab karakterisztikus szabályt lehet előállítani. Jelölje ζ az adott elemhalmazból előállított összes karakterisztikus szabály legkisebb megbízhatóság át:

    ζ({ p 1 , p 2 ,…, p k })=min[c({ p 1 }→{ p 2 , p 3 ,…, p k }),

    …,c({ p k }→{ p 1 , p 3 …, p k−1 })]

A ζ monoton, antimonoton, vagy nem monoton?

  1. Egy diszkrimináns szabály a következőképpen néz ki: { p 1 , p 2 ,…, p n }→{q} , vagyis a szabály következményi oldalán csupán egyetlen elem szerepel. Egy k méretű elemhalmazból k darab diszkrimináns szabályt lehet előállítani. Jelölje η az adott elemhalmaz ból előállított összes diszkrimináns szabály legkisebb megbízhatóság át:

    η({ p 1 , p 2 ,…, p k })=min[c({ p 2 , p 3 ,…, p k }→{ p 1 }),

    …,c({ p 1 , p 2 ,… p k−1 }→{ p k })]

Az η monoton, antimonoton, vagy nem monoton?

  1. Ismételjük meg az (a) és (b) pontok számításait úgy, hogy a min függvény t max függvény re cseréljük.

5. Bizonyítsuk be a (6.23) egyenletet. (Útmutatás: először számoljuk össze, hogy a szabály bal oldalát alkotó elemhalmazt hányféleképpen lehet létrehozni. Ezután a bal oldalról vett minden k méretű elemhalmaz esetén számoljuk össze, hogy a szabály jobb oldalát alkotó d−k elemet hányféleképpen lehet kiválasztani.)

6. Tekintsük a 6.23. táblázatban látható bevásárlókosár tranzakciókat.

6.23. táblázat - Bevásárlókosár tranzakciók

tranzakció azonosító

vásárolt cikkek

1

{ tej, sör, pelenka }

2

{ kenyér, vaj, tej }

3

{ tej, pelenka, sütemény }

4

{ kenyér, vaj, sütemény }

5

{ sör, sütemény, pelenka }

6

{ tej, pelenka, kenyér, vaj }

7

{ kenyér, vaj, pelenka }

8

{ sör, pelenka }

9

{ tej, pelenka, kenyér, vaj }

10

{ sör, sütemény }


  1. Ebből az adathalmazból összesen hány asszociációs szabályt lehet kinyerni (beleértve a nulla támogatottsági értékkel rendelkező szabályokat is)?

  2. A kinyerhető gyakori elemhalmazok közül mi a legnagyobb elemhalmaz mérete ( minsup≥0 mellett)?

  3. Fejezzük ki képlettel, hogy az adathalmazból legfeljebb hány darab 3-elemhalmazt lehet kinyerni.

  4. Adjunk példát egy olyan elemhalmazra, mely legalább 2 elemet tartalmaz és támogatottsága a legnagyobb.

  5. Keressünk egy olyan elemhalmazpárt ( a és b ), melyre teljesül, hogy az {a}→{b} és {b}→{a} szabályok megbízhatóság a azonos.

7. Vegyük a következő gyakori 3-elemhalmazokat:

{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5},{3,4,5}.

Tegyük fel, hogy az adathalmazban csupán öt elem szerepel.

  1. Soroljuk fel az összes 4- elemhalmazjelölt et, melyeket az F k−1 × F 1 egyesítési stratégia állítana elő.

  2. Soroljuk fel az összes 4- elemhalmazjelölt et, melyeket az Apriori jelöltgeneráló módszere állítana elő.

  3. Soroljuk fel azon 4- elemhalmazjelölt eket, melyek túljutnak az Apriori algoritmus jelölteket nyeső lépésén.

8. Az Apriori algoritmus egy ``generál és tesztel’’ stratégiát alkalmaz a gyakori elemhalmazok előállítására. A k+1 méretű elemhalmazjelölt eket k méretű gyakori elemhalmaz párok egyesítésével hozza létre (ezt jelölteket előállító lépésnek is hívjuk). Egy jelölt kizárásra kerül, ha a jelölteket nyeső lépés során kiderül, hogy az adott jelöltnek valamelyik részhalmaza nem gyakori. Tegyük fel, hogy az Apriori algoritmust a 6.24. táblázatban látható adathalmazra alkalmazzuk minsup=30% küszöbérték mellett, vagyis a 3-nál kevesebb tranzakcióban szereplő elemhalmazokat nem gyakori elemhalmazoknak tekintjük.

6.24. táblázat - Példa bevásárlókosár tranzakciókra

tranzakció azonosító

vásárolt cikkek

1

{a,b,d,e}

2

{b,c,d}

3

{a,b,d,e}

4

{a,c,d,e}

5

{b,c,d,e}

6

{b,d,e}

7

{c,d}

8

{a,b,c}

9

{a,d,e}

10

{b,d}


  1. Rajzoljuk meg a 6.24. táblázatban látható adathalmaznak megfelelő elemhalmazhálót. A háló csúcspontjait a következő betűvel (vagy betűkkel) jelöljük meg:

  1. Mi a gyakori elemhalmazok százalékos aránya (összevetve a hálóban található összes elemhalmaz számával)?

  2. Mi az Apriori algoritmus nyesési aránya ezen az adathalmazon? (A nyesési arány azon elemhalmaz ok százalékos arányát jelöli, melyek nem tekinthetők jelölteknek a következő két ok egyike miatt: (1) a jelölteket előállító lépés kihagyta őket, vagy (2) a jelölteket nyeső lépés eltávolította őket.)

  3. Mi a hibás riasztások aránya (vagyis azon elemhalmazjelölt ek százalékos aránya, melyekről csak a támogatottság kiszámítása után derül ki, hogy nem gyakoriak)?

9. Az Apriori algoritmus egy hasítófa adatstruktúrát alkalmaz az elemhalmazjelölt ek támogatottság ának a hatékony kiszámításához. Tekintsük a 6.32. ábrán látható, 3- elemhalmazjelölt eket tartalmazó hasítófát.

6.32. ábra - Példa egy hasítófa struktúrára

Példa egy hasítófa struktúrára

  1. Vegyük az {1,3,4,5,8} elemeket tartalmazó tranzakciót. A hasítófa mely levélcsúcsait fogjuk bejárni a tranzakcióból előállítható jelöltek keresése során?

  2. Felhasználva az (a) pontban bejárt levélcsúcsokat, állapítsuk meg, hogy mely elemhalmazjelölt ek szerepelnek az {1,3,4,5,8} tranzakcióban.

10. Vegyük a következő 3- elemhalmazjelölt eket:

{1,2,3},{1,2,6},{1,3,4},{2,3,4},{2,4,5},{3,4,6},{4,5,6}

  1. Építsünk egy hasítófát a fenti 3- elemhalmazjelölt eknek. Tegyük fel, hogy a fa a következő hasító függvény t alkalmazza: a páratlan számmal jelölt elemeket a hasítás során az aktuális csomóponttól balra osztjuk be, míg a páros számmal jelölt elemek jobbra kerülnek. Egy k - elemhalmazjelölt beszúrása a fába úgy történik, hogy a jelölt elemeire külön-külön alkalmazzuk a hasító függvény t, és a függvény értékének megfelelően a fa megfelelő ágait követjük. Amint elértünk egy levélcsúcsot, a jelöltet a következő feltételek alapján szúrjuk be:

1 feltétel: Ha a levélcsúcs mélysége k (a gyökér mélységét 0-nak tekintjük), akkor a jelöltet beszúrjuk, függetlenül attól, hogy már hány elem szerepel az adott csúcsban.

2 feltétel: Ha a levélcsúcs mélysége kisebb mint k , akkor a jelöltet csak akkor szúrjuk be, ha a csúcsban tárolt elemhalmaz ok száma kevesebb mint a maxsize érték. Tegyük fel, hogy ebben a példában maxsize=2 .

3 feltétel: Ha a levélcsúcs mélysége kisebb mint k , és a csúcsban tárolt elemhalmaz ok száma egyenlő a maxsize értékkel, akkor a levélcsúcsot egy belső csúccsá alakítjuk át, majd a korábbi levélcsúcs alá új gyermek levélcsúcsokat hozunk létre. A régi levélcsúcsban korábban tárolt elemhalmazjelölt eket a hasítóértékeik alapján az új gyermekcsúcsokban osztjuk szét. Az új jelöltet szintén a hasítóértéke alapján helyezzük el a megfelelő levélcsúcsban.

  1. A jelölteket tartalmazó hasítófában hány darab levélcsúcs található? Hány darab belső csúcs van a fában?

  2. Vegyünk egy tranzakció t a következő elemekkel: {1,2,3,5,6} . Az (a) pontban létrehozott hasítófát felhasználva mely levélcsúcsok lesznek összehasonlítva a tranzakció val? Mely 3- elemhalmazjelölt ek szerepelnek a tranzakció ban?

11. Tekintsük a 6.24. táblázat tranzakció it, illetve az adathalmazhoz tartozó elemhalmazhálót (lásd a 6.33. ábrát). Jelöljük meg a hálóstruktúra csúcsait a következő betűvel (vagy betűkkel):

6.33. ábra - Egy elemhalmazháló

Egy elemhalmazháló

A támogatottsági küszöbérték legyen 30%.

12. Az eredeti, asszociációs szabályokat bányászó módszer szerint az érdektelen szabályokat a támogatottság i és megbízhatóság i értékek alapján szűrjük ki.

  1. A 6.25. táblázat tranzakció it felhasználva rajzoljuk meg az alábbi szabályok kontingenciatáblázatait.

6.25. táblázat - Példa bevásárlókosár tranzakciókra

tranzakció azonosító

vásárolt cikkek

1

{a,b,d,e}

2

{b,c,d}

3

{a,b,d,e}

4

{a,c,d,e}

5

{b,c,d,e}

6

{b,d,e}

7

{c,d}

8

{a,b,c}

9

{a,d,e}

10

{b,d}


A szabály ok: {b}→{c} , {a}→{d} , {b}→{d} , {e}→{c} , {c}→{a} .

  1. Az (a) pont kontingenciatáblázatait felhasználva számítsuk ki a szabályok alábbi mértékeit, majd a mértékek alapján rendezzük a szabályokat csökkenő sorrendbe.

    1. Támogatottság .

    2. Megbízhatóság .

    3. Érdekesség( X→Y ) = P(X,Y) P(X) P(Y) .

    4. IS( X→Y ) = P(X,Y) P(X)P(Y) .

    5. Klosgen( X→Y ) = P(X,Y) ×(P(Y|X)−P(Y)) , ahol P(Y|X)= P(X,Y) P(X) .

    6. Esélyhányados( X→Y ) = P(X,Y)P( X Ż , Y Ż ) P(X, Y Ż )P( X Ż ,Y) .

13. A 12. feladatban megállapított sorrendet véve, számítsuk ki a megbízhatóság és a további öt mérték közti korrelációt. Melyik mérték korrelál leginkább a megbízhatóság gal? Melyik mérték korrelál legkevésbé a megbízhatóság gal?

14. Válaszoljunk a következő kérdésekre a 6.34. ábrán látható adathalmazok alapján. Megjegyezzük, hogy valamennyi adathalmazban 1000 elem és 10 000 tranzakció szerepel. A sötét cellák az elemek meglétét, míg a fehér cellák az elemek hiányát jelölik. Az Apriori algoritmust fogjuk felhasználni a gyakori elemhalmaz ok kinyeréséhez minsup=10% küszöbérték mellett (vagyis az elemhalmaz oknak legalább 1000 tranzakció ban kell szerepelniük).

  1. Melyik adathalmaz (vagy adathalmazok) fogja adni a legtöbb gyakori elemhalmazt?

  2. Melyik adathalmaz (vagy adathalmazok) fogja adni a legkevesebb gyakori elemhalmazt?

  1. Melyik adathalmaz (vagy adathalmazok) fogja adni a leghosszabb gyakori elemhalmazt?

  1. Melyik adathalmaz (vagy adathalmazok) fogja adni a legmagasabb támogatottság i értékkel rendelkező gyakori elemhalmazokat?

  1. Melyik adathalmaz (vagy adathalmazok) fog olyan gyakori elemhalmazokat adni, mely elemhalmazokban az elemek támogatottság a jelentős eltérést mutat (vagyis az elemek támogatottság a meglehetősen vegyes, kezdve a 20%-nál kisebb támogatottság tól a 70% feletti támogatottság ig)?

6.34. ábra - Ábrák a 14. feladathoz

Ábrák a 14. feladathoz

15.

  1. Bizonyítsuk be, hogy a ϕ -együttható értéke akkor és csakis akkor 1, ha f 11 = f 1+ = f +1 .

  2. Mutassuk meg, hogy ha A és B független, akkor P(A,B)×P(A, B Ż )=P(A, B Ż )×P( A Ż ,B) .

  1. Mutassuk meg, hogy Yule Q és Y együtthatói

Q=[ f 11 f 00 − f 10 f 01 f 11 f 00 + f 10 f 01 ]

Y=[ f 11 f 00 − f 10 f 01 f 11 f 00 + f 10 f 01 ]

az esélyhányados normalizált verziói.

  1. Írjunk A 6.11. és 6.12. táblázatban szereplő mértékek értékeire egy egyszerűsített képletet, feltételezve hogy a változók statisztikailag függetlenek.

16. Vegyük az A→B asszociációs szabály M= P(B|A)−P(B) 1−P(B) érdekességi mértékét.

  1. A mérték milyen intervallumból vehet fel értéket? A mérték mikor éri el a maximális és minimális értékét?

  2. Hogyan változik M , ha P(A,B) értéke nő, közben pedig P(A) és P(B) nem változik?

  1. Hogyan változik M , ha P(A) értéke nő, közben pedig P(A,B) és P(B) nem változik?

  1. Hogyan változik M , ha P(B) értéke nő, közben pedig P(A,B) és P(A) nem változik?

  1. Szimmetrikus-e a mérték a változók permutációja esetén?

  1. Mi lesz a mérték értéke, ha A és B statisztikailag függetlenek?

  1. Null-invariáns-e a mérték?

  1. Invariáns marad-e a mérték a sorok és oszlopok skálázása esetén?

  1. Hogyan viselkedik a mérték az inverzió műveletre?

17. Vegyünk egy bevásárlókosár adathalmazt, melyben 100 tranzakció és 20 elem található. Legyen az a elem támogatottság a 25%, a b elem támogatottság a 90%, az {a,b} elemhalmaz támogatottság a pedig 20%. A támogatottság i és megbízhatóság i küszöbértékek 10%, illetve 60%.

  1. Számítsuk ki az {a}→{b} asszociációs szabály megbízhatóság át. A kapott megbízhatóság i értékek alapján érdekesnek mondható-e a szabály ?

  2. Számítsuk ki az {a,b} asszociációs mintázat érdekességi mértékét. Az érdekességi mérték alapján írjuk le az a és b elemek közti kapcsolat jellegét.

  1. Az (a) és (b) pontok eredményeiből milyen következtetést tudunk levonni?

  1. Bizonyítsuk be, hogy ha az {a}→{b} szabály megbízhatóság a kisebb, mint a {b} támogatottság a, akkor:

  1. c({ a Ż }→{b})≥c({a}→{b}) ,

  2. c({ a Ż }→{b})≥s({b}) ,

ahol a c(⋅) a szabály megbízhatóság át, az s(⋅) pedig az elemhalmaz támogatottság át jelöli.

18. A 6.26. táblázat az A és B bináris változók 2×2×2 -es kontingenciatáblázatát mutatja a C kontrollváltozó különböző értékei mellett.

6.26. táblázat - Egy kontingenciatáblázat

 

A

A

 

1

0

C = 0

B

1

0

15

0

15

30

C = 1

B

1

5

0

0

0

15


  1. Számítsuk ki az A és B ϕ -együtthatóját, ha (i) C=0 , (ii) C=1 , illetve (iii) C=0 vagy C=1 .

Megjegyezzük, hogy ϕ({A,B})= P(A,B)−P(A)P(B) P(A)P(B)(1−P(A))(1−P(B)) .

  1. A fenti eredményekből milyen következetést tudunk levonni?

19. Vegyük a 6.27. táblázat kontingenciatáblázatait.

6.27. táblázat - Kontingenciatáblázatok a 19. feladathoz

B

B Ż

 

B

B Ż

A

9

1

A

89

1

A Ż

1

89

A Ż

1

9

        

(a) I. táblázat

   

(b) II. táblázat

   

  1. Az I. táblázat esetén számítsuk ki az {A,B} asszociációs mintázat támogatottság át, érdekességi mértékét, illetve ϕ -együtthatóját. Számítsuk ki az A→B és B→A szabály ok megbízhatóság át is.

  2. A II. táblázat esetén számítsuk ki az {A,B} asszociációs mintázat támogatottság át, érdekességi mértékét, illetve ϕ korrelációs együtthatóját. Számítsuk ki az A→B és B→A szabály ok megbízhatóság át is.

  3. Milyen következetést tudunk levonni az (a) és (b) pontok eredményeiből?

20. Vegyük a 6.19. és 6.20. táblázatokat. A táblázatok nagyfelbontású televíziókat és edzőgépeket vásárló vevők közti összefüggéseket tartalmaznak.

  1. Számítsuk ki mindkét táblázat esélyhányadosait.

  2. Számítsuk ki mindkét táblázat ϕ -együtthatóját.

  3. Számítsuk ki mindkét táblázat érdekességi tényezőjét.

Hogyan változnak a fenti mértékek esetében az asszociációk irányai, ha az adatokat nem rétegezve, hanem összevonva kezeljük?

Vissza Fel Előre
Irodalmi megjegyzések Főoldal 7. fejezet - Asszociációs elemzés: Magas szintű fogalmak