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

Tartalom

A probléma leírása
Gyakori elemhalmazok előállítása
Az apriori-elv
Gyakori elemhalmazok előállítása az Apriori algoritmussal
Jelöltek előállítása és nyesése
A támogatottsági szint kiszámítása
Számítási bonyolultság
Szabálygenerálás
Megbízhatóságon alapuló nyesés
Szabálygenerálás az Apriori algoritmussal
Példa: kongresszusi szavazási jegyzék
Gyakori elemhalmazok tömör reprezentációja
Maximális gyakori elemhalmaz
Zárt gyakori elemhalmazok
Alternatív módszerek gyakori elemhalmazok előállítására
Az FP-bővítés algoritmus
FP-fa reprezentáció
Gyakori elemhalmazok előállítása az FP-bővítés algoritmussal
Az asszociációs mintázatok kiértékelése
Objektív érdekességi mértékek
A bináris változópárokon túlmutató mértékek
Simpson paradoxona
A támogatottság aszimmetrikus eloszlásának hatása
Irodalmi megjegyzések
Feladatok

Sok üzleti vállalkozás nagy mennyiségű adatot halmoz fel a mindennapi működése során. Az élelmiszerboltok pénztárainál például minden egyes nap óriási mennyiségű vásárlói adat gyűlik össze. A 6.1. táblázatban lévő példa ilyen adatokat tartalmaz, ezeket általában vásárlói kosár tranzakcióknak nevezzük. A táblázat minden egyes sora egy-egy tranzakció nak felel meg. Minden sorhoz tartozik egy egyedi azonosító ( TID ), illetve az adott vásárló által megvett árucikkek halmaza. A kiskereskedők számára érdekes lehet ezen adatok vizsgálata, ha többet akarnak megtudni a vevőik vásárlói szokásairól. Az ilyen értékes információnak számos üzleti felhasználása lehet, például reklámok készítése, leltárvezetés, vagy a vásárlói kapcsolattartás menedzselésének segítése.

6.1. táblázat - Egy példa vásárlói kosár tranzakciókra

TID

Árucikkek

1

{ kenyér, tej }

2

{ kenyér, pelenka, sör, tojás }

3

{ tej, pelenka, sör, kóla }

4

{ kenyér, tej, pelenka, sör }

5

{ kenyér, tej, pelenka, kóla }


Ez a fejezet az asszociációs elemzés nevű módszertant mutatja be, ame`llyel nagy adathalmazokban lévő rejtett összefüggéseket tudunk felfedezni. A feltárt kapcsolatokat asszociációs szabályokként vagy gyakori elemek halmazaiként tudjuk reprezentálni. A 6.1. táblázatban található adathalmazból például a következő szabályt tudjuk kinyerni:

{pelenka}{sör}.

Ez a szabály egy erős összefüggést sugall a pelenka- és a söreladás között, ugyanis számos vevő a pelenkával együtt sört is vesz. Az ilyen típusú szabály ok a kiskereskedők számára új lehetőségeket biztosíthatnak különböző cikkek árukapcsolására.

A bevásárlókosarak adatai mellett az asszociációs elemzés más területekre is alkalmazható, mint például bioinformatika, orvosi diagnosztizálás, web-bányászat, illetve tudományos adatok vizsgálata. A földtudományi adatok elemzése során például az asszociációs mintázatok érdekes összefüggéseket fedhetnek fel az óceáni, a szárazföldi és a légköri folyamatok között. Ezen információk segítségével a tudósok jobban megérthetik a Föld természeti erői közti kölcsönhatásokat. Bár az itt bemutatott módszerek általában többféle adathalmaz esetén is alkalmazhatók, a példa kedvéért mi főleg a bevásárlókosarak adataira fogunk koncentrálni.

A bevásárlókosarak adatain alkalmazott asszociációs elemzés esetén két kulcsfontosságú szempontot kell figyelembe venni. Először is egy nagyméretű tranzakció s adathalmazban a mintázatok megtalálása jelentős számítási költséggel járhat. Másodsorban a felfedezett mintázatok egy része potenciálisan félrevezető, ugyanis elképzelhető, hogy csak véletlenül fordulnak elő. A fejezet hátralévő része ezen két szempont köré épül fel. A fejezet első részét az asszociációs elemzés alapfogalmainak és néhány hatékony mintázatkereső algoritmus bemutatásának szenteljük. A fejezet második része a felfedezett mintázatok értékelésével foglalkozik, melynek célja a hibás eredmények előállításának a megelőzése.

A probléma leírása

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.

6.2. táblázat - A bevásárlókosár adatok bináris ( 0/1 ) reprezentációja

TID

kenyér

tej

pelenka

sör

tojás

kóla

1

1

1

0

0

0

0

2

1

0

1

1

1

0

3

0

1

1

1

0

1

4

1

1

1

1

0

0

5

1

1

1

0

0

1


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 XY 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(XY)= σ(X Y) N , (6.1)

Megbízhatóság:    c(XY)= σ(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 XY 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 XY 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:

{sör,pelenka}{tej} ,

{sör,tej}{pelenka} ,

{pelenka,tej}{sör} ,

{sör}{pelenka,tej} ,

{tej}{sör,pelenka} ,

{pelenka}{sör,tej} .

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:

  1. Gyakori elemhalmazok generálása, ahol a cél megtalálni az összes olyan elemhalmazt amelyek megfelelnek a minsup küszöbértéknek.

  2. Szabálygenerálás, melynek célja az összes magas megbízhatóságú szabály kinyerése az előző pontban megtalált gyakori elemhalmazokból.

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.