Szabálygenerálás

Ebben a szakaszban azt mutatjuk be, hogy egy adott gyakori elemhalmazból hogyan tudunk hatékonyan asszociációs szabály okat kinyerni. Minden Y gyakori k -elemhalmazból összesen 2 k 2 asszociációs szabály t lehet előállítani. Ebben nincs benne az üres feltételi illetve üres következményi oldallal rendelkező két szabály ( Y és Y ). Egy asszociációs szabály az Y elemhalmaz két nem üres részhalmazra ( X és YX ) való szétválasztásával nyerhető ki, ahol az XYX megfelel a megbízhatósági küszöbértéknek. Megjegyezzük, hogy az így előállított szabályok kötelező módon eleget tesznek a támogatottsági küszöbértéknek, hiszen egy gyakori elemhalmazból lettek előállítva.

6.2. Példa.

Legyen X={1,2,3} egy gyakori elemhalmaz. Ebből hat asszociációs szabályjelöltet lehet előállítani: {1,2}{3} , {1,3}{2} , {2,3}{1} , {1}{2,3} , {2}{1,3} és {3}{1,2} . Mivel minden egyes jelölt támogatottsága azonos X támogatottságával, ezért a szabályok eleget tesznek a támogatottsági küszöbértéknek.

Egy asszociációs szabály megbízhatóságának a kiszámításához nem kell újraolvasni a tranzakció s adatbázist. Vegyük például az {1,2}{3} szabály t, mely az X={1,2,3} gyakori elemhalmazból lett előállítva. Ezen szabály megbízhatósága σ({1,2,3})/σ({1,2}) . Mivel {1,2,3} gyakori, a támogatottság antimonoton jellemzője biztosítja, hogy az {1,2} -nek is gyakorinak kell lennie. Mivel a gyakori elemhalmazok előállítása során mindkét elemhalmaz támogatottság a meg lett állapítva, ezért szükségtelen ismét végigolvasni a teljes adathalmazt.

Megbízhatóságon alapuló nyesés

A támogatottsági mértékkel ellentétben a megbízhatóság semmiféle monoton jellemzővel nem rendelkezik. Például az XY megbízhatósága lehet nagyobb, kisebb, vagy azonos egy másik X ̃ Y ̃ szabály megbízhatóságával, ahol X ̃ X és Y ̃ Y (lásd 3. gyakorlatot ex3:conf_prop. oldalon). Mindazonáltal, ha összehasonlítjuk az egyazon Y gyakori elemhalmazból előállított szabály okat, a támogatottsági mértékre a következő tétel fog érvényesülni.

6.2. Tétel

Ha egy XYX szabály nem felel meg a megbízhatósági küszöbértéknek, akkor egyetlen X'YX' szabály, ahol X' részhalmaza X -nek, sem fog annak megfelelni.

A tétel bizonyításához vegyük az X'YX' és XYX szabályokat, ahol X'X . A szabályok megbízhatósága σ(Y)/σ(X') illetve σ(Y)/σ(X) . Mivel X' részhalmaza X -nek, ezért σ(X')σ(X) . Ebből következik, hogy az első szabály megbízhatósága nem lehet nagyobb mint a másodiké.

Szabálygenerálás az Apriori algoritmussal

Az Apriori algoritmus az asszociációs szabályokat szintenként állítja elő, ahol a szinteket a következményi oldalon található elemek száma határozza meg. Először azokat a magas megbízhatóságú szabály okat állítjuk elő, melyek következményi oldalán egyetlen elem van, majd ezekből a szabály okból új szabályjelölteket generálunk. Például ha {acd}{b} és {abd}{c} magas megbízhatóságú szabály ok, akkor a két szabály következményi oldalának összevonásával az {ad}{bc} szabályjelöltet kapjuk. A 6.15. ábrán egy hálóstruktúra látható, mely az {a,b,c,d} gyakori elemhalmazból előállított asszociációs szabály okat szemlélteti. Ha a háló valamelyik csúcsa alacsony megbízhatóságú, akkor a 6.2. tétel alapján a csúcsból kiinduló teljes részgráf azonnal eltávolítható. Tegyük fel, hogy a {bcd}{a} szabály megbízhatósága alacsony. Ekkor figyelmen kívül hagyható az összes olyan szabály, amely az a elemet a következményi oldalon tartalmazza ( {cd}{ab} , {bd}{ac} , {bc}{ad} , illetve {d}{abc} ).

A szabályokat előállító pszeudokódot a 6.2., illetve a 6.3. algoritmus szemlélteti. Vegyük észre a hasonlóságot az Apriori-Szabály-Gen eljárás (6.3. algoritmus) és a gyakori elemhalmazokat előállító eljárás között (6.1. algoritmus). Az egyetlen különbség csupán az, hogy a szabálygenerálás során nem kell újra és újra végigolvasni az adatbázist a szabályjelöltek megbízhatóságának kiszámításához. Ehelyett a gyakori elemhalmazok előállítása során kiszámolt támogatottsági értékeket fogjuk felhasználni a szabály ok megbízhatóságának a megállapításához.

6.15. ábra - Asszociációs szabályok nyesése a megbízhatósági mérték alapján.

Asszociációs szabályok nyesése a megbízhatósági mérték alapján.

6.2. algoritmus Szabálygenerálás az Apriori algoritmussal

1: for minden fk gyakori k-elemhalmazra, ahol k ≥ 2 do

2: H1 = {i | i ∈ fk} {a szabály egyelemű következményi oldalai}

3: call Apriori-Szabály-Gen(fk,H1)

4: end for

AprioriSzabályGen( f k , H m ) eljárás

call Apriori-Szabály-Gen( f k , H m+1 )

6.3. algoritmus AprioriSzabályGen( f k , H m ) eljárás

1: k=| f k | { a gyakori elemhalmaz mérete}

2: m=| H m | {a szabály következményi oldalának a mérete}

3: if km+1 then

4: H m+1 = Apriori-Gen( H m )

5: for minden h m+1 H m+1 esetén do

6: conf=σ( f k )/σ( f k h m+1 )

7: for confminconf then

8: ( f k h m+1 ) h m+1 szabály előállítása

9: else

10: H m+1 H m+1 h m+1 h m+1 { h m+1 törlése H m+1 -ből }

11: end if

12: end for

13: call Apriori-Szabály-Gen( f k , H m+1 )

14: end if

Példa: kongresszusi szavazási jegyzék

Ez a szakasz az asszociációs elemzés alkalmazási eredményeit szemlélteti, ahol az elemzés tárgya az Amerikai Képviselőház tagjainak a szavazási jegyzéke. Az adatok az 1984-es kongresszusi szavazási jegyzékek adatbázisából származnak, mely megtalálható az UCI[5] gépi tanulás adattárában. A tranzakció k tartalmazzák az adott képviselő politikai hovatartozását, illetve hogy hogyan szavazott 16 kulcskérdésben. Az adathalmazban 435 tranzakció és 34 attribútum szerepel. Az attribútumok listája a 6.3. táblázatban látható.

6.3. táblázat - Az 1984-es amerikai kongresszusi szavazási jegyzék bináris attribútumainak listája. Forrás: UCI gépi tanulás adattára

1. republikánus

18. segély Nicaraguának = nem

2. demokrata

19. MX-rakéta = igen

3. mozgássérült gyerekek = igen

20. MX-rakéta = nem

4. mozgássérült gyerekek = nem

21. bevándorlás = igen

5. vízgazdálkodási költségek megosztása = igen

22. bevándorlás = nem

6. vízgazdálkodási költségek megosztása = nem

23. mesterséges üzemanyagokat előállító cégek támogatásának mérséklése = igen

7. költségvetési határozat = igen

24. mesterséges üzemanyagokat előállító cégek támogatásának mérséklése = nem

8. költségvetési határozat = nem

25. oktatási kiadások = igen

9. orvosi bérek befagyasztása = igen

26. oktatási kiadások = nem

10. orvosi bérek befagyasztása = nem

27. perlési jog = igen

11. segély El Salvadornak = igen

28. perlési jog = nem

12. segély El Salvadornak = nem

29. bűnözés = igen

13. iskolai vallásos csoportok = igen

30. bűnözés = nem

14. iskolai vallásos csoportok = nem

31. adómentes export = igen

15. műholdelhárító kísérletek leállítása = igen

32. adómentes export = nem

16. műholdelhárító kísérletek leállítása = nem

33. exporttörvény = igen

17. segély Nicaraguának = igen

34. exporttörvény = nem


6.4. táblázat - Az 1984-es amerikai kongresszusi szavazási jegyzékből kinyert asszociációs szabály ok

asszociációs szabály

megbízha-tóság

{költségvetési határozat=nem,MXrakéta=nem,segély El Salvadornak=igen} {republikánus}

91,0%

{költségvetési határozat=igen,MXrakéta=igen,segély El Salvadornak=nem} {demokrata}

97,5%

{bűnözés=igen,perlési jog=igen,orvosi bérek befagyasztása=igen} {republikánus}

93,5%

{bűnözés=nem,perlési jog=nem,orvosi bérek befagyasztása=nem} {demokrata}

100%


Az Apriori algoritmust ezután minsup=30% és minconf=90% értékekkel alkalmaztuk az adathalmazon. A 6.4. táblázatban az algoritmus által kinyert magas megbízhatóságú szabályok közül láthatunk néhányat. Az első két szabály arra enged következtetni, hogy republikánus azon képviselők többsége, akik igennel szavaztak El Salvador megsegítésére és nemmel a költségvetési határozatra illetve az MX-rakétákra; míg akik ellenezték a segélyt El Salvador számára és támogatták a költségvetési határozatot és az MX-rakétákat, azok demokraták. Ezek a magas megbízhatóságú szabály ok felfedik azokat a kulcskérdéseket, melyek megosztották a két politikai párt tagjait. A minconf csökkentésével olyan szabály okat is találhatunk, melyek olyan kérdéseket tartalmaznak, melyek egyetértésre találtak a pártok között. Például minconf=40% esetén a szabály ok azt mutatják, hogy a vállalati leépítések kérdésében majdnem ugyanannyi szavazat érkezett a két pártból -- a nemmel szavazók 52,3%-a republikánus, míg a nemmel szavazók maradék 47,7%-a demokrata.



[5] Irvine-i Kaliforniai Egyetem (UCI -- University of California at Irvine)