Irodalmi megjegyzések

Az asszociációs szabályok bányászatát először Agrawal és társai vezették be [4629, 4655], melynek célja a bevásárlókosarakhoz köthető tranzakciók közti érdekes kapcsolatok felfedezése volt. Az eredeti elképzelés óta kiterjedt kutatásokat végeztek az asszociációs elemzés i feladathoz tartozó fogalmi, implementációs és alkalmazási kérdések megválaszolása érdekében. Az ezen a területen végzett különböző tudományos tevékenységekről a 6.31. ábrán láthatunk összefoglalót.

Fogalmi kérdések

A fogalmi kérdésekkel foglalkozó kutatások elsősorban a következő témákkal foglalkoznak: (1) keretrendszer kidolgozása az asszociációs elemzés elméleti alapjainak a leírására, (2) szabályok kiterjesztése újfajta mintázatok kezelésére, (3) szabályok kiterjesztése olyan attribútumtípusokra, melyek túlmutatnak az aszimmetrikus bináris adatokon.

Agrawal és társai úttörő munkáját követve, óriási mennyiségű kutatói munkát fordítottak az asszociációs elemzés elméletének a kidolgozására. Gunopoulos és társai [4756] megmutatták, hogy kapcsolat van a maximális gyakori elemhalmazok keresése és a hipergráfok transzverzálisa között. Az asszociációs elemzés i feladat bonyolultságának a felső határa is meg lett állapítva. Zaki és társai [4932, 4930] valamint Pasquier és társai [4848] a formális fogalomelemzést alkalmazták a gyakori elemhalmazok előállításának a vizsgálatára. Zaki és társai munkássága ezt követően a zárt gyakori elemhalmazok fogalmának a bevezetéséhez vezetett [4932]. Friedman és társai az asszociációs elemzés problematikáját a többdimenziós térben történő ``dudor-vadászat'' (bump hunting) esetében vizsgálták [4749]. Egészen pontosan, a gyakori elemhalmazok előállítására úgy tekintettek, mint többdimenziós térben történő nagy valószínűségi sűrűségű területek keresésére.

Az évek során új típusú mintázatokat definiáltak, mint például profil asszociációs szabály ok [4652], ciklikus asszociációs szabályok [4843], fuzzy asszociációs szabályok [4804], kivételes szabályok [4897], negatív asszociációs szabályok [4871, 4702], súlyozott asszociációs szabályok [4863, 4706], függőségi szabályok [4885], jellegzetes szabályok [5080], intertranzakciós asszociációs szabályok [4907, 4743], illetve részleges osztályozási szabályok [4833, 4658]. De vannak további mintázat-típusok is: zárt elemhalmazok [4932, 4848], maximális elemhalmazok [4686], hiperklikk mintázatok [4925], támogatottsági borítékok [4895], feljövő mintázatok [4729], és kontraszthalmazok [4685]. Az asszociációs elemzés t szintén sikeresen alkalmazták szekvenciális [4656, 4893], térbeli [4780], és gráf-alapú [4782, 4806, 4926, 4847, 4929] adatokra. A kereszttámogatott mintázatok fogalmát először Hui és társai [4925] vezették be. A szerzők egy hatékony algoritmust (Hyperclique Miner) is javasoltak a kereszttámogatott mintázatok automatikus kizárására.

Alapos kutatások történtek arra vonatkozóan, hogy az asszociációs szabály eredeti definícióját a nominális [4892], sorrendi [4820], intervallum [4828] és hányados [4892, 4750, 4757, 4935, 4913] típusú attribútumokra is kiterjesszék. Az egyik legfontosabb kérdés, hogy ezen attribútumok esetében hogyan definiáljuk a támogatottsági mértéket. Steinbach és társai [4896] javasoltak egy módszertant, mellyel a támogatottság eredeti fogalmát ki lehet terjeszteni általánosabb mintázatokra és attribútumtípusokra.

6.31. ábra - Az asszociációs elemzéshez kapcsolódó különböző kutatási tevékenységek összefoglalója

Az asszociációs elemzéshez kapcsolódó különböző kutatási tevékenységek összefoglalója

Implementációs kérdések

Ezen a téren a kutatási tevékenységek a következő problémák köré csoportosulnak: (1) adatbányászati képessség integrálása létező adatbázis technológiába, (2) hatékony és skálázható adatbányászati algoritmusok fejlesztése, (3) felhasználó által megadott vagy területspecifikus megszorítások kezelése, és (4) kinyert mintázatok utófeldolgozása.

Számos előnye van az asszociációs elemzés létező adatbázis technológiába való integrálásának. Először is, ki lehet használni az adatbázisrendszer indexelő és lekérdezéskezelő képességeit. Másodsorban, támaszkodhatunk az adatbáziskezelő rendszer támogatására a skálázhatóságot, az ellenőrzési pontokat, illetve a párhuzamosítást illetően [4868]. A Houtsma és társai [4779] által fejlesztett SETM algoritmus az egyik legelső olyan algoritmus volt, mely támogatta az asszociációs szabályok felfedezését SQL lekérdezések segítségével. Azóta számos módszert fejlesztettek ki, melyek asszociációs szabályok bányászatát teszik lehetővé adatbázisrendszerekben. Például a DMQL [4762] és M-SQL [4781] lekérdezőnyelvek az eredeti SQL nyelvet bővítik ki új operátorokkal, lehetővé téve így az asszociációs szabályok bányászatát. A szabálybányász (Mine Rule) operátor [4824] egy sokoldalú SQL operátor, mellyel mind klaszterezett attribútumokat, mind pedig elemhierarchiákat kezelni lehet. Tsur és társai [4906] egy ``generál-és-tesztel'' módszert dolgoztak ki az asszociációs szabályok bányászatára, melynek neve lekérdezés rajok (query flocks). Chen és társai [4711] egy elosztott OLAP-alapú infrastruktúrát dolgoztak ki a többszintű asszociációs szabályok bányászatára.

Dunkel és Soparkar [4735] megvizsgálta az Apriori algoritmus idő- és tárbonyolultságát. Az FP-bővítés algoritmus Han és társai [4764] nevéhez fűződik. További, gyakori elemhalmazokat bányászó algoritmusok: Park és társai [4845] DHP (dynamic hashing and pruning, dinamikus hasítás és nyesés) algoritmusa, illetve Savasere és társai [4870] Partition algoritmusa. Toivonen [4905] egy mintavétel-alapú gyakori elemhalmazokat előállító algoritmust javasolt. Ez az algoritmus csak egyszer olvassa végig az adatokat, de a szükségesnél több jelöltet állít elő. A DIC (dynamic itemset counting, dinamikus elemhalmaz-számláló) algoritmus [4703] másfélszer olvassa végig az adatokat és kevesebb jelöltet állít elő, mint a mintavétel-alapú algoritmus. További említésre méltó algoritmusok: fa-projekció algoritmus [4154] és H-Mine [4850]. A gyakori elemhalmazokat előállító algoritmusokról áttekintő cikkek is találhatók [4654, 4775]. Számos adathalmaz és algoritmus található a FIMI (Frequent Itemset Mining Implementations, gyakori elemhalmazokat bányászó implementációk) tárházban (http://fimi.cs.helsinki.fi). Több szerző is dolgozott asszociációs mintázatokat bányászó párhuzamos algoritmusokon [4651, 4758, 4835, 4883, 4933]. Ezen algoritmusokról a [4931] cikkben olvashatunk áttekintést. Hidber [4773] valamint Cheng és társai [4714] asszociációs szabályokat bányászó algoritmusok online és növekményes verzióit dolgozták ki.

Srikant és társai [4894] az asszociációs szabályok bányászatának a problémáját logikai megszorítások tükrében vizsgálták, úgymint

( süteménytej)(féleség(sütemény)¬származék(búzakenyér)).

Egy ilyen megszorítás esetén az algoritmus olyan szabályokat keres, melyek (1) mind süteményt, mind pedig tejet is tartalmaznak, vagy (2) süteményféleségeket tartalmaznak de nem búzakenyér származékok. Singh és társai [4887] valamint Ng és társai [4839] is kidolgoztak alternatív módszereket az asszociációs szabályok megszorítás-alapú bányászatára. A megszorításokat a különböző elemhalmazok támogatottságára is alkalmazni lehet. Ezt a problémát Wang és társai [4912], Liu és társai [4816] valamint Seno és társai [4880] vizsgálták.

Az asszociációs elemzés egyik potenciális problémája az, hogy a jelenlegi algoritmusokkal nagyon nagy számú mintázatot lehet előállítani. A probléma leküzdésére olyan módszereket fejlesztettek ki, melyekkel a mintázatokat rangsorolni, összegezni, és szűrni lehet. Toivonen és társai [4904] a redundáns szabályokat strukturális szabály burkolókkal (structural rule covers) zárták ki, majd a megmaradó szabályokat klaszterezéssel csoportosították. Liu és társai [4817] a statisztikai khi-négyzet próba segítségével távolították el a félrevezető mintázatokat, majd a megmaradó mintázatokat a mintázatok egy részhalmazával, az úgynevezett irányított elrendezésű szabályokkal (direction setting rules) foglalták össze. Számos szerző vizsgálta az objektív mértékek használatát a mintázatok szűréséhez, például Brin és társai [4702], Bayardo és Agrawal [4687], Aggarwal és Yu [4653], illetve DuMouchel és Pregibon [4733]. Ezen mértékek jellemzőit többen is vizsgálták: Piatetsky-Shapiro [4853], Kamber és Singhal [4793], Hilderman és Hamilton [4774], illetve Tan és társai [4900]. Az osztályzatok és nemek közti kapcsolatot tartalmazó példa esetén (mellyel a sorok és oszlopok skálázásra érzéketlen jellemzőjének a fontosságát emeltük ki) erősen támaszkodtunk Mosteller egyik fejtegetésére [4834]. Továbbá a tea-kávé példához (mellyel a megbízhatósági mérték korlátait szemléltettük) Brin és társai [4702] egyik példája adta az ihletet. A megbízhatóság korlátai miatt Brin és társai [4702] inkább az érdekességi tényezőt javasolták, mint érdekességi mértéket. A teljes-bizonyosság mértéket Omiecinski [4842] javasolta. A kereszttámogatott jellemzőt Xiong és társai [4925] vezették be, s ők mutatták meg azt is, hogy a teljes-bizonyosság mértékkel ki lehet zárni a kereszttámogatott mintázatokat. A legfőbb gond, amiért a támogatottság mellett nehezen lehet használni az alternatív objektív mértékeket az, hogy ezek a mértékek nem rendelkeznek a monotonitás tulajdonsággal; emiatt nehezen lehet őket beépíteni az adatbányászati algoritmusokba. Xiong és társai [4923] egy hatékony módszert javasoltak a korrelációk bányászatához: a ϕ -együtthatóhoz egy felső határ függvény t vezetettek be. Bár a jellemző nem monoton, a jellemző felső korlátja megadható egy kifejezéssel, így ezt ki lehet használni erősen korreláló elempárok hatékony bányászatához.

Fabris és Freitas [4740] az érdekes összefüggések felfedezésére a Simpson paradoxon előfordulásainak a kimutatását javasolták [4886]. Megiddo és Srikant [4822] a kinyert mintázatok érvényesítésére egy olyan megközelítést mutattak be, mely hipotézis-tesztelő módszereket alkalmaz. Egy többszöri próbavételen alapuló módszert is kidolgoztak a sokszoros összehasonlítás miatt előálló félrevezető mintázatok elkerülése érdekében. Bolton és társai [4694] a Benjamini-Hochberg [4688] és Bonferroni korrekciós módszereket alkalmazták a bevásárlókosár adatokban felfedezett mintázatok p -értékeinek a beigazításához. Webb [4917] valamint Zhang és társai [4934] alternatív módszereket javasoltak a sokszoros összehasonlítás problémájának kezelésére.

Számos szerző vizsgálta a szubjektív mértékek alkalmazását az asszociációs elemzés ben. Silberschatz and Tuzhilin [4884] két elvet mutatott be, melyekkel eldönthető, hogy egy adott szabály érdekes-e szubjektív szempontból. A váratlan feltételes szabályok fogalmát Liu és társai [4814] vezették be. Cooley és társai [4718] a gyenge bizonyosságú (soft belief) halmazok és a Dempster-Shafer elmélet egyesítésének ötletét vizsgálták, majd ezt a módszert arra használták fel, hogy webes adatokban ellentmondásos, valamint újszerű asszociációs mintázatokat azonosítsanak. A szubjektíve érdekes mintázatok azonosítására további módszerek is léteznek, például a Bayes-féle háló [4785], vagy a szomszédság-alapú információ [4730].

A különféle vizualizációs módszerek szintén segíthetik a felhasználót abban, hogy gyorsan átlássák a felfedezett mintázatok alapvető struktúráját. Számos kereskedelmi forgalomban kapható adatbányászati eszköz a teljes szabályhalmazt (mely szabályok megfelelnek a támogatottsági és megbízhatósági kritériumoknak) kétdimenziós diagramként ábrázolja, ahol a tengelyek a szabályok feltételi és következményi oldalának felelnek meg. Hofmann és társai [4776] mozaik diagramok és emeletes (Double Decker) diagramok használatát javasolták az asszociációs szabályok megjelenítésére. Ezzel a megközelítéssel nem csak egy bizonyos szabályt lehet megjeleníteni, hanem a szabály feltételi és következményi oldalán szereplő elemhalmazok közti teljes kontingenciatáblázatot is. Ez a módszer azonban azt feltételezi, hogy a szabály következményi oldalán csupán egyetlen attribútum szerepel.

Alkalmazási kérdések

Az asszociációs elemzés t számos alkalmazási területen felhasználták, mint például webes bányászat [4898, 4852], dokumentumelemzés [4777], telekommunikációs riasztások elemzése [4797], hálózati betörések észlelése [4810, 4684, 4724], illetve bioinformatika [4869, 4922]. Az asszociációs és korrelációs mintázatok elemzésének a felhasználását a földtudományokban a [4901, 4855, 4854] cikkekben vizsgálták.

Az asszociációs mintázatokat egyéb tanulási problémák esetében is felhasználták, például osztályozás [4815, 4813], regresszió [4844] és klaszterezés [4927, 4760, 4924]. Az osztályozást és az asszociációs szabályok bányászatát Freitas hasonlította össze helyzetjelentésében [4746]. Számos szerző vizsgálta az asszociációs mintázatok felhasználását a klaszterezésben: Han és társai [4760], Kosters és társai [4800], Yang és társai [4927], illetve Xiong és társai [4924].