6.3. Definíció

(Maximális gyakori elemhalmaz) Egy maximális gyakori elemhalmaz egy olyan gyakori elemhalmaz, melynek egyetlen közvetlen szuperhalmaza sem gyakori.

Ennek a fogalomnak a szemléltetéséhez vegyük a 6.16. ábrán látható elemhalmaz hálót. A hálóban az elemhalmazok két csoportra vannak osztva, úgy mint gyakori és nem gyakori elemhalmazok. Az ábrán szintén látható egy szaggatott vonal, mely a gyakori elemhalmazok határát jelzi. A határ feletti elemhalmazok gyakoriak, míg a határ alatti (szürkével jelölt) csúcsok nem gyakoriak. A határközeli csúcsok közül az {a,d} , {a,c,e} és {b,c,d,e} elemhalmazokat maximális gyakorinak tekintjük, mivel a közvetlen szuperhalmazaik nem gyakoriak. Például az {a,d} maximális gyakori, mivel az összes közvetlen szuperhalmaza ( {a,b,d} , {a,c,d} és {a,d,e} ) nem gyakori. Ezzel szemben az {a,c} nem maximális, mivel az egyik közvetlen szuperhalmaza ( {a,c,e} ) gyakori.

A maximális gyakori elemhalmazok egy tömör reprezentációját biztosítják a gyakori elemhalmazoknak. Másképp megfogalmazva, ezek az elemhalmaz ok adják azt a legkisebb halmazt, melyből az összes gyakori elemhalmazt le lehet vezetni. A 6.16. ábrán például a gyakori elemhalmazok két csoportba oszthatók:

Az első csoportba tartozó gyakori elemhalmazok vagy az {a,c,e} vagy az {a,d} részhalmazai. A második csoport tagjai a {b, c, d, e} részhalmazai. Vagyis az {a,c,e} , {a,d} és {b,c,d,e} maximális gyakori elemhalmazok egy tömör reprezentációját adják a 6.16. ábrán látható gyakori elemhalmazoknak.

A maximális gyakori elemhalmazok különösen a nagyon hosszú gyakori elemhalmazokat tartalmazó adathalmazok esetén biztosítanak értékes reprezentációt. Az ilyen adathalmazokban ugyanis exponenciálisan sok gyakori elemhalmaz van. Mindazonáltal ennek a megközelítésnek csak akkor van gyakorlati haszna, ha létezik olyan hatékony algoritmus, mely közvetlenül megtalálja a maximális gyakori elemhalmazokat anélkül, hogy fel kellene sorolnia ezen elemhalmaz ok összes részhalmazát. 6.5. szakaszban röviden bemutatunk egy ilyen módszert.

Bár a maximális gyakori elemhalmazok egy tömör reprezentációt biztosítanak, nem tartalmaznak információt a részhalmazaik támogatottságával kapcsolatban. Az {a,c,e} , {a,d} és {b,c,d,e} elemhalmazok támogatottság a például semmiféle utalást nem ad a részhalmazaik támogatottságával kapcsolatban. Ezért aztán a nem maximális gyakori elemhalmazok támogatottságának a megállapításához ismét végig kell olvasni az adathalmazt. Bizonyos esetekben előnyös lehet a gyakori elemhalmaz oknak egy olyan minimális reprezentációja, amely megőrzi a támogatottsági információkat. A következő szakaszban egy ilyen reprezentációt mutatunk be.

A zárt elemhalmazok az elemhalmazok egy minimális reprezentációját adják a támogatottsági információk elvesztése nélkül. A zárt elemhalmazok formális definíciója a következőképpen hangzik:

6.4. Definíció

(Zárt elemhalmaz) Az X elemhalmaz zárt, ha X egyetlen közvetlen szuperhalmaza sem rendelkezik az X támogatottsági szintjével.

Másképp fogalmazva X nem zárt, ha legalább egy közvetlen szuperhalmazának a támogatottsága egyezik X támogatottságával. A zárt elemhalmazokra a 6.17. ábrán mutatunk példákat. Az elemhalmazok támogatottságának a jobb szemléltetéséhez a háló minden egyes csúcsához (elemhalmazához) hozzárendeltük a megfelelő tranzakció azonosítókat. Például a {b,c} csúcshoz rendelt tranzakció azonosítók: 1, 2 és 3, vagyis {b,c} támogatottsági szintje három. Az ábrán látható tranzakció kban vegyük észre, hogy ha egy tranzakció ban szerepel a b , akkor a c is szerepel benne. Ebből következik, hogy {b} támogatottsága azonos {b,c} támogatottságával és így {b} nem tekinthető zárt elemhalmaznak. Hasonlóképpen, mivel c előfordul mindazon tranzakció kban, melyekben szerepel a is és d is, az {a,d} elemhalmaz sem zárt. Másrészt viszont {b,c} zárt elemhalmaz, ugyanis a támogatottsági szintje eltér az összes szuperhalmaza támogatottságától.

6.5. Definíció

(Zárt gyakori elemhalmaz) Egy elemhalmaz akkor gyakori zárt elemhalmaz, ha zárt és a támogatottsága nagyobb vagy egyenlő, mint a minsup érték.

Az előző példánál maradva tegyük fel, hogy a támogatottsági küszöbérték 40%. Ekkor { b,c } zárt gyakori elemhalmaz mivel a támogatottsága 60%. A többi zárt gyakori elemhalmazt szürke színű csúcsokkal jelöltük.

Léteznek algoritmusok, melyek egy adott adathalmazból közvetlenül a zárt gyakori elemhalmazokat nyerik ki. Az érdeklődő Olvasó további információt találhat ezekről az algoritmusokról a fejezet végi irodalmi megjegyzésekben. A zárt gyakori elemhalmazokat fel lehet használni a nem zárt gyakori elemhalmazok támogatottságának a megállapításához. Vegyük például az {a,d} gyakori elemhalmazt a 6.17. ábrán. Mivel ez az elemhalmaz nem zárt, ezért a támogatottsági szintjének azonosnak kell lennie az egyik közvetlen szuperhalmaza támogatottságával. A feladat tehát annak eldöntése, hogy a szuperhalmazok közül ( {a,b,d} , {a,c,d} vagy {a,d,e} ) melyiknek ugyanakkora a támogatottsága mint {a,d} -nek. Az apriori-elv kimondja, hogy ha egy tranzakció tartalmazza az {a,d} egy szuperhalmazát, akkor az {a,d} -t is tartalmaznia kell. Azonban ha egy tranzakció tartalmazza {a,d} -t, akkor nem kell tartalmaznia {a,d} szuperhalmazait. Ezért {a,d} támogatottságának azonosnak kell lennie a legnagyobb támogatottsági értékkel rendelkező szuperhalmazának a támogatottságával. Mivel {a,c,d} támogatottsága nagyobb, mint az {a,b,d} vagy {a,d,e} támogatottsága, ezért az {a,d} támogatottságának azonosnak kell lennie az {a,c,d} támogatottságával. Ezt a módszertant felhasználva létre lehet hozni egy algoritmust a nem zárt gyakori elemhalmazok támogatottságának a kiszámítására. Ennek az algoritmusnak a pszeudokódját a 6.4. algoritmus szemlélteti. Az algoritmus általánosító módon, vagyis a legnagyobbtól a legkisebb gyakori elemhalmazok felé halad. Ez azért van, mert egy nem zárt gyakori elemhalmaz támogatottságának a kiszámításához ismerni kell az adott elemhalmaz összes szuperhalmazának a támogatottságát.

Támogatottság i szint kiszámítása zárt gyakori elemhalmazok használatával

A zárt gyakori elemhalmazok használatának előnyét a 6.5. táblázatban látható adatbázissal szemléltetjük. Az adatbázis tíz tranzakció t és 15 elemet tartalmaz. Az elemek három csoportba sorolhatók: (1) A csoport, elemek a 1 -től a 5 -ig; (2) B csoport, elemek b 1 -től b 5 -ig; illetve (3) C csoport, elemek c 1 -től c 5 -ig. Megjegyezzük, hogy az elemek a csoportokon belül tökéletesen társulnak egymással és nem szerepelnek együtt más csoportokban szereplő elemekkel. Ha a támogatottsági küszöbérték 20%, akkor a gyakori elemhalmazok száma összesen 3×( 2 5 −1)=93 . Az adatbázisban azonban csak három zárt gyakori elemhalmaz szerepel: { a 1 , a 2 , a 3 , a 4 , a 5 } , { b 1 , b 2 , b 3 , b 4 , b 5 } és { c 1 , c 2 , c 3 , c 4 , c 5 } . Sok esetben elegendő ha az elemzőnek csak a zárt gyakori elemhalmazokat adjuk át az összes gyakori elemhalmaz helyett.

A zárt gyakori elemhalmazok néhány redundáns asszociációs szabály eltávolítására is alkalmasak. Egy X→Y asszociációs szabály redundáns, ha létezik egy olyan másik X'→Y' szabály , ahol X részhalmaza X' -nek és Y részhalmaza Y' -nek, továbbá a két szabály támogatottsága és megbízhatósága azonos. A 6.17. ábrán látható példában {b} nem zárt gyakori elemhalmaz, míg {b,c} zárt. Következésképpen a {b}→{d,e} asszociációs szabály redundáns, ugyanis a támogatottsága és megbízhatósága azonos a {b,c}→{d,e} szabály paramétereivel. Ha a szabály ok generálásához zárt gyakori elemhalmazokat használunk, akkor az ilyesfajta redundáns szabály ok nem fordulnak elő.

Végül megjegyezzük, hogy a maximális gyakori elemhalmazok egyben zártak is, hiszen egyetlen maximális gyakori elemhalmaz támogatottsága sem lehet azonos valamelyik közvetlen szuperhalmazáéval. A gyakori, maximálisan gyakori és zárt gyakori elemhalmazok közötti összefüggéseket a 6.18. ábra mutatja.