Számítástudományi és Információelméleti Tanszék

 

Témakiírás

Diszkrét matematikai módszerek az adatbányászatban

A 90-es években a tárolókapacitások méretének igen erőteljes növekedése, valamint az árak nagymértékű csökkenése miatt az elektronikus eszközök és adatbázisok a hétköznapi életben is mind inkább elterjedtek. Az egyszerű és olcsó tárolási lehetőségek a nyers, feldolgozatlan adatok tömeges méretű felhalmozását eredményezték, ezek azonban közvetlen visszakeresésen és ellenőrzésen kívül egyéb haszonnal nem jártak. Sok helyen a ritkán látogatott adatokból “adat temetők” (data tombs) alakultak ki, amelyek tárolása költséget jelentett, de hasznot nem hozott.

Egyre több területen merült fel az igény, hogy az adathalmazokból a hagyományosnál árnyaltabb szerkezetű információt nyerjenek ki. A hagyományos adatbázis-kezelő rendszerek komplexebb feladatokat egyátalán nem tudnak megoldani, vagy az eredmény kiszámítása elfogadhatatlanul hosszú időbe telt. A szükség egy új tudományterületet keltett életre, az adatbányászatot, amelynek célja "hasznos, látens információ kinyerése adatbázisokból".

A digitális gazdaság nagy ígérete, hogy az ügyfeleket jellemző fogyasztói magatartásokról információk gazdag tárháza áll rendelkezésre, amely alapjául szolgál a korábbi lehetőségekhez képest jóval alaposabb, pontosabb és hatékonyabb tervezésnek, ill. fejlesztésnek. Például a weben megjelenő cégek és szervezetek számára az ügyfélismeret lehetőségét az üzemeltetés során keletkező forgalmi naplóállományok elemzése adja meg. Ennek során weboldalakra vonatkozó látogatottsági statisztikák nyerhetők, a gyakori bejárási útvonalak feltérképezésével, nyomkövetési technikák alkalmazásával azonos érdeklődési körrel, fogyasztói magatartással jellemezhető felhasználói profilok ismerhetők fel.

A nagy adatmennyiségek feldolgozásához az adatbányászat ad módszert. Tárgyköréhez klasszikus értelemben az adatbázis legfeljebb egy-kétszeri elolvasásából információt nyerő kifinomult algoritmusok tartoznak. Az algoritmusok legújabb generációja ugyanakkor véletlen mintavételezéses, ill. algebrai meggondolásokkal képes az adatbázis méretét is redukálni.

Az Internet-felhasználók zöméről feltételezhető, hogy viselkedése napi, heti és akár éves szinten is ismétlődő mintázatokból áll. Ezek ismerete egyrészt elősegíti a számukra megfelelő tartalom naprakész biztosítását, másrészt a viselkedéses mintázatuk ismerete alapján jellemezhetünk, kategorizálhatunk is felhasználói csoportokat, pontosítva ezzel adataik elemzését.

Előfordulhatnak olyan weboldal kombinációk, ahol a bizonyos weboldal csoportok iránt érdeklődő böngészők jelentős része bizonyos további oldalakat is megnéz. Ezt a jelenséget az előbbi oldalakból az utóbbiakhoz vezető asszociációs szabálynak nevezzük. Ezeknek a szabályoknak az ismerete alapján például felhívhatjuk a felhasználó figyelmét, hogy érdeklődési köréhez tartozó további oldalakat találhat, vagy éppen rávehetjük reklámok megtekintésére, mielőtt további kedvenc oldalaihoz eljuthat. Hasonló asszociációs szabályok ismerhetők fel nagyobb áruházláncok termékcsoportjai között, abban az értelemben, hogy ha X vásárló egy Y terméket megvesz, akkor nagy valószínűséggel egy Z terméket is meg fog vásárolni. “Klasszikus” példa a {pelenka}Þ sör szabály.

Az időben ismétlődő periódusok, szekvenciák felismerésére szakosodott az epizódkutatás. Hosszú eseménysorozatokban lehetnek gyakran előforduló elemek, vagy elemhalmazok. Definiálhatunk soros, párhuzamos, illetve kaszkád epizódokat. Epizódkutatás során ezen epizódok minél hatékonyabb megtalálása a cél. A módszer alkalmazásai közé tartozhat például robotok vagy kifinomultabb automatikus letöltések által mesterségesen generált forgalom kiszűrése és így hitelesebb forgalomauditálás; vagy a szolgáltató érdekével ellentétes olyan magatartásformák, mint az adatbázisok célzott letöltése vagy online lekérdezhetőségükkel való egyéb visszaélés felderítése is.

A felhasználói mintázat hasonló részeinek, különféle értelemben vett klasztereinek, így például az azonos érdeklődésű, hasonló oldalakat látogató felhasználóknak fellelése az adatbányászat legnehezebb és legkisebb pontosságú módszerekkel rendelkező területe. Ugyanakkor egy üzleti döntéshez vagy stratégia kialakításhoz valószínűleg csak a csoportjellemzők biztosíthatnak kellő megalapozottságot, az egyedi jellegzetességek nem.

A csoportosítás, klaszterezés legtöbb felmerülő kérdése megfogalmazható úgy, hogy az egyes esetekhez tartozó nagyszámú változó egy magas dimenziós tér pontjait adja. Például a tér dimenziói az egyes weboldalak lehetnek, a felhasználókhoz pedig a látogatási gyakoriságokból álló vektor a tér egy-egy pontját rendeli. Ebben a térben egy klaszter a közeli pontok, azaz a hasonló oldalakat látogató felhasználók csoportja. A klaszterek meghatározásának megkönnyítésére használható algebrai módszer a spektrálfelbontás, amelynek segítségével viszonylag kevés adatvesztéssel jelentősen csökkenthető a dimenziószám és így a feladatméret. Egy másik módszer az adatok csoportosítására a logikai analízis, ahol (az esetlegesen geometriai térben levő) adatokat binarizálják, és utána olyan Boole-formulákat keresnek, melyek megfelelő minőségben osztják fel az adathalmazt.

A világháló összefüggései gyakran jellemezhetők gráffal: például egy hiperhivatkozás a hivatkozó hiperszövegtől a hivatkozott felé, egy elektronikus levél a küldőtől a feladó felé mutató gráfélnek tekinthető. Egy gráf klaszterekre bontására a statisztika a Laplace-mátrix módszert alkalmazza, amely a gráfot az Euklideszi térbe ágyazza be megfelelő módon. A gráfelmélet hagyományosabb módszerei közé tartozik a különféle erősséggel összefüggő komponensek megkeresése. Az újabb típusú módszerek, mint a webgráf modellezésén alapuló következtetések, az egyes gráfcsúcsokra mutató élek mint ajánlások erejét mérő rangsorolások pedig kifejezetten az Internettel együtt, annak vizsgálatára születtek.

A nagy adatmennyiségek feldolgozásához az adatbányászat ad módszert. Tárgyköréhez klasszikus értelemben az adatbázis legfeljebb egy-kétszeri elolvasásából információt nyerő kifinomult algoritmusok tartoznak. Az algoritmusok legújabb generációja ugyanakkor véletlen mintavételezéses, ill. algebrai meggondolásokkal képes az adatbázis méretét is redukálni.

Kutatások célja a problémakör matematikai alapjainak vizsgálata. Ez a következő fő irányokat jelenti:

Tehát tervezett kutatásaink elsősorban alapkutatás jellegűek, ugyanakkor a téma közvetlen gyakorlati alkalmazásokkal bír. Az adatbányászat matematikai megalapozásának szükségességét jelzi, hogy a SIAM második adatbányászati szimpóziumán (Washington, D.C., 2002 április 10-13) külön workshop volt szentelve az adatbányászat és a diszkrét matematika kapcsolatának. Azonban, az ilyen irányú kutatások még nagyon újak, kezdeti stádiumban vannak.

 

Szükséges nyelvtudás: angol

Dr. Sali Attila
egyetemi adjunktus
31-61
sali@renyi.hu