Fogalomhierarchiák kezelése
Vissza 7. fejezet - Asszociációs elemzés: Magas szintű fogalmak Előre

Fogalomhierarchiák kezelése

A fogalomhierarchia egy adott területen definiált különböző egyedek vagy fogalmak egy többszintű elrendezése. A bevásárlókosarak vizsgálatához használt hierarchia például árucikkek egy taxonómiájának formáját ölti, melyben leírjuk egy élelmiszerboltban árusított elemek ``részhalmaz'' (is-a) típusú kapcsolatait -- például a tej egy élelmiszer, a DVD pedig egy szórakoztató elektronikai eszköz (lásd a 7.2. ábrát). A fogalomhierarchiákat gyakran szakterületi tudás, vagy bizonyos szervezetek által meghatározott standard osztályozási sémák alapján építik fel (például a Kongresszusi Könyvtár osztályozási sémáját használják a könyvtári anyagok téma szerint történő osztályozására).

7.2. ábra - Példa elemek egy taxonómiájára

Példa elemek egy taxonómiájára

Egy fogalomhierarchiát reprezentálhatunk irányított körmentes gráffal, ahogy az a 7.2. ábrán is látható. Ha a gráf egy p csúcsából él vezet egy másik, c csúcsba, a p csúcsot c szülőcsúcsának, c -t pedig p gyerekcsúcsának hívjuk. Például a sovány tej szülője a tej, mert a tej csúcsból irányított él vezet a sovány tej csúcsba. X ̂ -et az X ősének nevezzük ( X -et pedig X ̂ leszármazottjának), ha az irányított körmentes gráfban az X ̂ csúcsból út vezet az X csúcsba. A 7.2. ábrán látható diagramon az élelmiszer a sovány tej egy őse, az AC adapter pedig a műszaki cikkek egy leszármazottja.

A következők a legfőbb előnyei annak, ha fogalomhierarchiákat alkalmazunk az asszociációs elemzésben:

  1. Előfordulhat, hogy a hierarchia alacsonyabb szintjein lévő elemeknek nincs elég támogatottságuk ahhoz, hogy megjelenjenek a gyakori elemhalmazokban. Például, bár az AC adapterek és dokkolók eladási mutatói alacsonyak lehetnek, magas értékű lehet a laptop tartozékok eladása, mely a fogalomhierarchiában a szülőcsúcsuk. Fogalomhierarchia használata nélkül előfordulhat, hogy kihagyunk olyan érdekes mintázatokat, melyek laptop tartozékokat tartalmaznak.

  2. A fogalomhierarchia alsóbb szintjein feltárt szabályok általában túl specifikusak, és gyakran nem olyan érdekesek, mint a magasabb szintű szabályok. Az olyan alaptermékek például, mint a tej és a kenyér, hajlamosak sok olyan alacsony szintű szabályt generálni, mint például sovány tej → teljes kiőrlésű kenyér, 2%-os tej → teljes kiőrlésű kenyér, vagy sovány tej → fehér kenyér. Ha fogalomhierarchiát használunk, ezeket egyetlen szabályban összegezhetjük: tej → kenyér. Ha azonban csak a hierarchiák legfelső szintjén elhelyezkedő elemeket vesszük figyelembe, az sem feltétlenül megfelelő, mivel az ilyen szabályoknak gyakran nincs semmilyen gyakorlati haszna. Bár lehet például, hogy a műszaki cikkek→élelmiszer szabály kielégíti a támogatottsági és megbízhatósági küszöbértékeket, de nem nyújt plusz információt, mivel nem tudjuk, hogy pontosan melyek a műszaki cikkek és élelmiszerek azon kombinációi, amelyeket a vásárlók gyakran vásárolnak meg. Ha csak a tej és az elemek azok az árucikkek, amelyeket gyakran adnak el együtt, akkor az {élelmiszer, műszaki cikkek} mintázat valószínűleg túláltalánosítja a helyzetet.

A következőképpen egészíthetjük ki a standard asszociációs elemzést úgy, hogy tartalmazzon fogalomhierarchiákat. Először minden t tranzakciót kicserélünk a t' kiterjesztett tranzakciójára, amely tartalmazza t összes elemét és azok felmenőit. Például a { DVD, teljes kiőrlésű kenyér } tranzakciót a { DVD, teljes kiőrlésű kenyér, szórakoztató elektronika, műszaki cikkek, kenyér, élelmiszer } tranzakcióvá terjeszthetjük ki, ahol a szórakoztató elektronika és a műszaki cikkek a DVD ősei, míg a kenyér és az élelmiszer a teljes kiőrlésű kenyér ősei. Ezzel a megközelítéssel olyan meglévő algoritmusokat is alkalmazhatunk az adatbázisra, mint például az Apriori, hogy a hierarchiák különböző szintjein átnyúló szabályokat tárjunk fel. Ennek a megközelítésnek azonban több nyilvánvaló korlátja van:

  1. A magasabb szintű elemeknek általában nagyobb a támogatottsági értékük, mint a fogalomhierarchia alacsonyabb szintjein találhatóaknak. Ennek eredményeképpen, ha a támogatottsági küszöbértéket túl magasra állítjuk, akkor csak a magas szintű elemeket tartalmazó mintázatokat nyerjük ki. Másrészt viszont, ha a küszöbértéket túl alacsonyra állítjuk, akkor az algoritmus túl sok mintázatot generál (melyek nagy része valószínűleg hamis), és számítási hatékonysága lecsökken.

  2. Egy fogalomhierarchia bevezetése általában az asszociációs elemzési algoritmusok számítási idejének növekedését vonja maga után, mert nő az árucikkek száma és a tranzakciók szélessége is. Az ilyen algoritmusokkal generált mintázat jelöltek és gyakori mintázatok száma is exponenciális arányban nő a tranzakciók szélességével.

  3. Egy fogalomhierarchia bevezetése felesleges szabályok előállításához vezethet. Egy X→Y szabály felesleges, ha létezik egy általánosabb X ̂ → Y ̂ szabály, melyben X ̂ az X egy őse, Y ̂ pedig az Y egy őse, és a két szabály megbízhatósága nagyon hasonló. Tegyük fel például, hogy nagyon hasonló a {kenyér}→{tej} , {fehér kenyér}→{2%-os tej} , {teljes kiőrlésű kenyér}→{2%-os tej} , {fehér kenyér}→{sovány tej} , és {fehér kenyér}→{sovány tej} szabályok megbízhatósága. Ekkor a hierarchia alacsonyabb szintjeihez tartozó árucikkeket tartalmazó szabályokat feleslegesnek tekintjük, mert összefoglalhatóak egy, az őseiket tartalmazó szabállyal. Egy olyan elemhalmaz is felesleges, mint például {sovány tej, tej, élelmiszer} , mert az élelmiszer és a tej a sovány tej ősei. Szerencsére az ilyen elemhalmazok a hierarchia ismeretének birtokában könnyen eltávolíthatóak a gyakori elemhalmazok generálása során.

Vissza Fel Előre
Folytonos attribútumok kezelése Főoldal Szekvenciális mintázatok