7. fejezet - Asszociációs elemzés: Magas szintű fogalmak

Tartalom

Kategorikus attribútumok kezelése
Folytonos attribútumok kezelése
Diszkretizálás-alapú módszerek
Statisztikán alapuló módszerek
Nem diszkretizálási módszerek
Fogalomhierarchiák kezelése
Szekvenciális mintázatok
A probléma megfogalmazása
Szekvenciális mintázatok feltárása
Időbeli megszorítások
Különböző számítási sémák
Részgráf mintázatok
Gráfok és részgráfok
Gyakori részgráfok bányászata
Apriori-szerű módszer
Jelöltgenerálás
A jelöltek nyesése
A támogatottság kiszámítása
Ritka mintázatok
Negatív mintázatok
Negatívan korrelált mintázatok
A ritka mintázatok, a negatív mintázatok és a negatívan korrelált mintázatok összehasonlítása
Az érdekes ritka mintázatok bányászatának módszerei
Negatív mintázatok bányászatán alapuló módszerek
Várható támogatottságon alapuló módszerek
Irodalmi megjegyzések
Feladatok

Az asszociációs szabályok bányászatának az előző fejezetben leírt megfogalmazásánál feltételeztük, hogy a bemenő adatok bináris attribútumokból állnak, melyeket elemeknek nevezünk. Azt is feltételeztük továbbá, hogy egy elem jelenléte fontosabb, mint a hiánya. Ennek eredményeképpen az elemeket aszimmetrikus bináris attribútumokként kezeljük, és csak a gyakori mintázatokkal foglalkozunk.

Ebben a fejezetben kiterjesztjük a megfogalmazást szimmetrikus bináris, kategorikus és folytonos attribútumokkal rendelkező adatállományokra. A megfogalmazást kiterjesztjük továbbá az olyan bonyolultabb konstrukciókra is, mint a sorozatok és a gráfok. Bár ezzel nem változtatunk az asszociációs elemzési algoritmusok általános felépítésén, de az algoritmusok bizonyos részleteit módosítanunk kell, hogy kezelni tudják a hagyományostól eltérő konstrukciókat.

Kategorikus attribútumok kezelése

Számos alkalmazásban használunk szimmetrikus bináris és nominális attribútumokat. A 7.1. táblázatban látható internetes kérdőíves adatok olyan szimmetrikus bináris attribútumokat tartalmaznak, mint például a Nem, Otthoni számítógép, Online csevegés, Online vásárlás, és Biztonsági aggályok; ezen felül pedig olyan nominális attribútumokat is, mint az Iskolázottsági szint és Állam . Asszociációs elemzéssel olyan érdekes információkat tárhatunk fel az Internet felhasználóiról, mint például:

{Online vásárlás = igen}{Biztonsági aggályok = igen}.

Ez a szabály arra utal, hogy a legtöbb olyan internet-felhasználó, aki online boltokban vásárol, foglalkozik személyes adatainak biztonságával.

7.1. táblázat - Internetes kérdőíves adatok kategorikus attribútumokkal

Nem

Iskolázottsági

Állam

Otthoni

Online

Online

Biztonsági

szint

számítógép

csevegés

vásárlás

aggályok

egyetem

Illinois

igen

igen

igen

igen

férfi

főiskola

California

nem

nem

nem

nem

férfi

egyetem

Michigan

igen

igen

igen

igen

főiskola

Virginia

nem

nem

igen

igen

egyetem

California

igen

nem

nem

igen

férfi

főiskola

Minnesota

igen

igen

igen

igen

férfi

érettségi

Alaska

igen

igen

nem

nem

férfi

érettségi

Oregon

igen

nem

nem

nem

egyetem

Texas

nem

igen

nem

nem


Az ilyen mintázatok kinyeréséhez először ``elemekké'' alakítjuk a kategorikus és a szimmetrikus bináris attribútumokat, hogy használni tudjuk a meglévő asszociációs szabály bányászati algoritmusokat. Ezt a transzformációt végrehajthatjuk úgy, hogy minden egyes attribútum-érték párhoz létrehozunk egy új elemet. Az Iskolázottsági szint nominális attribútumot például az Iskolázottság=főiskola , Iskolázottság=egyetem és Iskolázottság=érettségi bináris elemekkel helyettesíthetjük. A szimmetrikus bináris attribútumok, mint például a Nem , hasonlóképpen alakíthatóak át olyan bináris elempárokká, mint a Férfi és . A 7.2. táblázatban látható az internetes kérdőíves adatok binarizálásának eredménye.

7.2. táblázat - Internetes kérdőíves adatok a kategorikus és szimmetrikus bináris attribútumok binarizálása után

Férfi

Iskolázottság

Iskolázottság

Biztonsági

Biztonsági

= egyetem

= főiskola

aggályok

aggályok

= igen

= nem

0

1

1

0

1

0

1

0

0

1

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

1

0

1

0

1

0

0

1

1

0

1

0

0

1

0

1

1

0

0

0

0

1

0

1

1

0

0

1


A következő szempontokat kell mérlegelnünk, amikor binarizált adatokon hajtunk végre asszociációs elemzést:

  1. Előfordulhat, hogy egyes attribútumértékek nem elég gyakoriak ahhoz, hogy egy gyakori mintázat részét képezzék. Ez a probléma látványosabban jelentkezik nominális attribútumoknál, amelyeknek sok lehetséges értéke lehet, mint például az államok nevei. A támogatottsági küszöbérték csökkentése nem segít ezen, mivel exponenciálisan növeli a talált gyakori mintázatok számát (amelyek nagy része hamis lehet), és így költségesebbé teszi a számítást. Szerencsésebb megoldás, ha a hasonló attribútumértékeket néhány kategóriába soroljuk be, például az államok neveit a földrajzi régiójuk nevére cseréljük, mint például Közép-Nyugat, Északnyugati part, Délnyugat, Keleti part . Másik megoldásként a kevésbé gyakori attribútumértékeket összevonhatjuk egy Egyéb kategóriába, mint ahogy a 7.1. ábrán is látható.

7.1. ábra - Tortadiagram egyesített Egyéb kategóriával

Tortadiagram egyesített Egyéb kategóriával

  1. Egyes attribútumértékek előfordulási gyakorisága jelentősen nagyobb lehet, mint a többi értéké. Tegyük fel például, hogy a felmérésben résztvevők 85%-a rendelkezik otthoni számítógéppel. Ha minden, az adatállományban gyakran előforduló attribútumértékhez létrehozunk egy bináris elemet, könnyen előfordulhat, hogy a következő példához hasonló felesleges mintázatokat generálunk:

{Otthoni számítógép = igen, Online vásárlás = igen}

    {Biztonsági aggályok = igen}.

Ez a szabály azért felesleges, mert a szakasz elején megadott, általánosabb szabály már magában foglalja. Mivel a magas előfordulási gyakoriságú elemek általában egy attribútum jellemző értékéhez tartoznak, nagyon ritkán hordoznak olyan új információt, amely segíthet a mintázat megértésében. Ezért hasznos lehet az ilyen elemek eltávolítása, mielőtt szabványos aszociációs elemzési algoritmusokat alkalmaznánk. Egy másik lehetőség nagy számú támogatottsági értékkel rendelkező adatállományok kezelésére a 6.8. alfejezetben leírt módszerek alkalmazása.

  1. Bár minden tranzakció mérete az eredeti adatállomány attribútumainak számával egyezik meg, a számítási idő mégis megnőhet, főleg akkor, ha az újonnan létrehozott elemek közül sok válik gyakorivá. Ezt azzal magyarázhatjuk, hogy több időt vesz igénybe azon elemhalmaz jelöltek kezelése, amelyeket ezek az elemek generálnak (lásd ex4:traffic. feladatot ex4:traffic. oldalon). Egy mód a számítási időt csökkentésére, hogy elkerüljük az olyan elemhalmaz jelöltek generálását, amelyek ugyanazon attribútumhoz tartozó elemek közül egynél többet tartalmaznak. Nem kell generálnunk például az olyan elemhalmaz jelölteket, mint az {Állam = X, Állam = Y,…} , mert az elemhalmaz támogatottsága nulla.