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

Ebben a szakaszban az asszociációs elemzés ben használt alapvető terminológiát tekintjük át, illetve megadjuk a feladat formális leírását.

Bináris reprezentáció

A bevásárlókosár adatokat a 6.2. táblázatban látható bináris formátumban tudjuk reprezentálni, ahol egy sor egy tranzakció nak, egy oszlop pedig egy árucikknek felel meg. Egy árucikket bináris változónak lehet tekinteni, melynek értéke egy, ha az árucikk szerepel egy tranzakció ban, különben nulla. Mivel egy tranzakció ban egy cikk jelenléte gyakran fontosabb, mint a cikk hiánya, ezért a cikkek aszimmetrikus bináris változók. A valódi bevásárlókosár adatok esetén ez a reprezentáció talán túlságosan is leegyszerűsített nézetet ad, mivel néhány fontos szempontot -- mint például a vásárolt áruk mennyiségét vagy árát -- nem vesz figyelembe. Az ilyen jellegű nem-bináris adatok kezelésére szolgáló módszereket 7. fejezetben mutatjuk be.

Elemhalmaz és támogatottsági szint

Legyen I={ i 1 , i 2 , … , i d } a bevásárlókosár adatokban szereplő árucikkek halmaza, T={ t 1 , t 2 ,…, t N } pedig a tranzakció k halmaza. Minden egyes t i tranzakció az I egy részhalmazát tartalmazza. Az asszociációs elemzés ben nulla vagy több cikk együttesét elemhalmaznak (itemset) nevezzük. Ha egy elemhalmaz k elemet tartalmaz, akkor azt k - elemhalmaz nak hívjuk. Például a {sör,pelenka,tej} egy 3- elemhalmaz . Az üres halmaz egy olyan elemhalmaz , amely egyetlen elemet sem tartalmaz.

A tranzakció szélességét a tranzakció ban szereplő elemek száma határozza meg. Azt mondjuk, hogy a t j tranzakció tartalmazza az X elemhalmaz t, ha X részhalmaza a t j tranzakció nak. A 6.2. táblázat második tranzakció ja például tartalmazza a {kenyér,pelenka} elemhalmaz t, a {kenyér,tej} elemhalmaz t viszont nem tartalmazza. Egy elemhalmaz fontos jellemzője a támogatottság i szint, amely azt mutatja meg, hogy egy adott elemhalmaz összesen hány tranzakció ban szerepel. Egy X elemhalmaz támogatottság i szintje (jelölése σ(X) ) matematikailag a következőképpen írható le:

σ(X)=|{ t i |X⊆ t i ,   t i ∈T}|,

ahol |⋅| egy halmaz elemeinek számát jelöli. A 6.2. táblázatban szereplő adathalmaz ban a {sör,pelenka,tej} támogatottság i szintje kettő, mivel csak két tranzakció tartalmazza mindhárom elemet.

Asszociációs szabály

Egy asszociációs szabály egy X→Y alakú implikációs kifejezés, ahol X és Y diszjunkt elemhalmazok, vagyis X ∩ ​ Y=∅ . Egy asszociációs szabály erejét a szabály támogatottság ával (support) illetve megbízhatóság ával (confidence) tudjuk mérni. A támogatottság azt határozza meg, hogy egy szabály milyen gyakran alkalmazható egy adott adathalmaz ra. A megbízhatóság azt mutatja meg, hogy az X -et tartalmazó tranzakció ban az Y elemei milyen gyakorisággal jelennek meg. Ezen mértékek formális definíciói:

Támogatottság:    s(X→Y)= σ(X ∪ ​ Y) N , (6.1)

Megbízhatóság:    c(X→Y)= σ(X ∪ ​ Y) σ(X) . (6.2)

6.1. Példa.

Vegyük a {tej,pelenka}→{sör} szabály t. Mivel a {tej,pelenka,sör} támogatottság i szintje 2 és a tranzakció k száma összesen 5, ezért a szabály támogatottság a 2/5=0,4 . A szabály megbízhatóság át úgy kapjuk meg, hogy elosztjuk a {tej,pelenka,sör} támogatottság át a {tej,pelenka} támogatottság ával. Mivel 3 olyan tranzakció van, melyek tartalmaznak tejet és pelenkát, ezért a szabály megbízhatóság a 2/3=0,67 .

Mire jó a támogatottság és a megbízhatóság ?

A támogatottság egy fontos mérték, hiszen elképzelhető, hogy egy alacsony támogatottság ú szabály csupán véletlenül fordul elő. Egy alacsony támogatottság ú szabály nagy valószínűséggel nem is érdekes üzleti szempontból, mivel nem előnyös olyan árukat reklámozni, amelyeket a vásárlók csak ritkán vesznek meg együtt (kivéve azt az esetet, amelyet a 6.2.1. szakaszban mutatunk be). A támogatottság ot ezen okok miatt gyakran az érdektelen szabály ok kizárására használják. Amint azt a 6.2.1. szakaszban látni fogjuk, a támogatottság rendelkezik egy olyan előnyös jellemzővel is, amely felhasználható az asszociációs szabály ok hatékony felderítésére.

A megbízhatóság ezzel szemben a szabály által jelölt következtetés hitelességét méri le. Egy adott X→Y szabály esetén minél magasabb a megbízhatóság , annál valószínűbb, hogy az X -et tartalmazó tranzakció kban az Y is jelen van. A megbízhatóság egyben becslést is ad az Y feltételes valószínűségére adott X esetén.

Az asszociációs elemzés eredményeit azonban óvatosan kell értelmezni. Egy asszociációs szabály által jelölt következtetés nem feltétlenül jelent okozati viszonyt. Inkább azt mondhatjuk, hogy a szabály feltételi és következményi oldalán szereplő elemek gyakran fordulnak elő együtt. Az okozati összefüggéshez viszont ismerni kell az adatokban lévő ok és okozati attribútum okat, és általában olyan kapcsolatokról van szó, melyek idővel változnak (például az ózoncsökkenés a globális felmelegedéshez vezet).

Az asszociációs szabály ok bányászatának problémája

Az asszociációs szabály ok bányászatának problémáját formálisan a következő képpen írhatjuk le:

6.1. Definíció

(Asszociációs szabály ok feltárása) Ha adott a tranzakció k egy T halmaza, akkor találjuk meg az összes olyan szabály t, melyre igaz, hogy a támogatottság ≥ minsup és a megbízhatóság ≥ minconf . A minsup és minconf változók a megfelelő támogatottság i és megbízhatóság i küszöbértékeket jelölik.

Ha az asszociációs szabály ok bányászatához a nyers erő módszerét alkalmaznánk, akkor az összes lehetséges szabály támogatottság át, illetve megbízhatóságát meg kellene állapítani. Ez a megközelítés azonban megengedhetetlenül költséges, mivel egy adathalmazból exponenciálisan sok szabályt lehet kinyerni. Egészen pontosan egy d elemet tartalmazó adathalmazból összesen

R= 3 d − 2 d+1 +1 (6.3)

darab szabályt lehet előállítani. Eme egyenlet bizonyítását meghagyjuk az Olvasó számára (lásd 5. gyakorlatot 417. oldalon). Ezzel a módszerrel még a 6.1. táblázatban látható kisméretű adathalmaz esetén is 3 6 − 2 7 +1=602 szabály támogatottság át és megbízhatóságát kellene kiszámítani. Ezen szabály ok több mint 80%-át el kellene vetni a minsup=20% és minconf=50% küszöbértékek esetén, vagyis a számítások túlnyomó többsége feleslegesnek bizonyulna. A szükségtelen számítási műveletek elkerülése végett hasznos lenne már a számítások elején úgy megszűrni a szabály okat, hogy ne kelljen kiszámolni a támogatottság ukat és megbízhatóságukat.

Az asszociációs szabály okat bányászó algoritmusok teljesítményének a növelése felé az első lépés a támogatottság i illetve a megbízhatósági követelmények szétválasztása. A (6.2) egyenletből látható, hogy egy X→Y szabály támogatottság a csupán a szabálynak megfelelő X ∪ ​ Y elemhalmaz támogatottság ától függ. Például a következő szabályok támogatottság a azonos, mivel egyazon elemhalmazból, {sör,pelenka,tej} , származnak az elemeik:

Ha az elemhalmaz nem gyakori, akkor mind a hat szabályjelöltet azonnal ki lehet zárni anélkül, hogy ki kellene számítani a megbízhatóságukat.

Így aztán számos asszociációs szabály t bányászó algoritmus azt a bevett stratégiát alkalmazza, hogy a problémát két nagyobb részfeladatra bontja:

A gyakori elemhalmazok kiszámítási költsége általában magasabb, mint a szabályok generálása esetén. A 6.2. szakaszban a gyakori elemhalmazok, míg a 6.3. szakaszban az asszociációs szabály ok előállítására mutatunk be néhány hatékony módszert.