Párhuzamos Adatsűrűség alapú kieső érték keresés MapReduce alapokon
Párhuzamos adatsűrűség alapú kieső érték keresés MapReduce alapokon
Az elmúlt évtizedekben a tárolt adat mennyisége folyamatosan nőtt, sok esetben akkora méretű adathalmazok keletkeztek, amik már csak nagy nehézségekkel vagy egyáltalán nem kezelhetőek hagyományos relációs adatbázisokban. A hatalmas méretű adatok kezelésére jöttek létre a különféle BigData technológiák. Ezek közül jelenleg a legnépszerűbbek a különféle Hadoop alapú megoldások. A Hadoop egy open source Apache projekt, tekinthető egy BigData management és elemző szoftver családnak, illetve sokan hívják a BigData elemzés operációs rendszerének. Egy Hadoop klaszter több ezer gépig is remekül skálázódik, Petabyte méretű adatok elemzésére is alkalmas. Fontos azonban kiemelni, hogy a Hadoop-os adatelemzés speciális lépéseket igényel, az általa használt MapReduce alapú programozási modell használatával automatikusan párhuzamosítható programok futtatását teszi lehetővé. Az automatizáltságnak azonban ára van, ez bizonyos megkötésekkel jár, és nem is minden megoldás valósítható meg rajta. Ez természetesen azt jelenti, hogy az adatelemzési és adatbányászati algoritmusokat újra implementálni kell a MapReduce paradigma szerint. Számos elemző algoritmus illetve módszer már elérhető open source könyvtárakban, azonban még mindig sokkal kevesebb algoritmust tartalmaznak ezek mint például a hagyományos adatbányász és statisztikai szoftverekben és könyvtárakban. Napjaink egyik fontos adatbányászati feladata az outlier keresés. Ennek segítségével lehet többek között bankkártyás csalásokat, webes támadásokat, meghibásodásokat vagy sokféle anomáliát általában. Számos kieső értékeket észlelő algoritmus van, ezek több családba sorolhatók, attól függően, hogy miben nyilvánul meg az adatok egymástól és az adathalmaztól való különbözősége. Kutatásomban ezek közül a közelség alapú megközelítést választom, ahol a kiugróságot a többi adattól való távolsággal lehet mérni. A távolságok megfelelő pontoktól való mérésének elvégzéséhez érdemes egy olyan elosztott adatszerkezetet létrehozni, ahol az egyes pontokhoz térben közel található pontok hatékony megtalálását támogatja. Ez Hadoop klaszter esetén azt jelenti, hogy az egymáshoz közel elhelyezkedő pontok, amik esetében a távolságokat ki kell számolnunk, mindenképpen egy gépen legyenek. Ennek a megoldásához kutatási munkám során egyfajta hierarchikus térbeli rácsot, azaz egy fát, tervezek létrehozni mintavételezés alkalmazásával. A hierarchikus rács levél elemei annyiban lesznek megnövelve (egymást átfedve), hogy ne kelljen a más gépen lévő adatokhoz nyúlni a megfelelően közellévő pontok megtalálásához. Így a közelségen alapú algoritmusokon belül a pont körüli térben az adatsűrűséget számoló outlier keresés megoldható nagy hálózati forgalom nélkül, mivel minden szükséges adat lokálisan rendelkezésre áll. A kritikus lépés a mintavételezés, aminek ha nem megfelelő az eredménye, akkor a rács nem lesz egyenletes, és az algoritmus sem kellően hatékony. Megfelelő minta nagyság esetén ennek a valószínűsége elhanyagolhatóan kicsi lehet, illetve szükség esetén meg lehet ismételni a rács elkészítését. Miután létrehoztunk egy kellően jó minőségű rácsot, a sűrűség alapú kieső érték keresés az algoritmus szekvenciális verziójával is végrehajtható, annyit kell figyelembe venni, hogy a rács megnövelt peremén lévő pontok csak a keresés helyességéhez kellenek az egyes gépeken. A kutatás eredménye felhasználható nagy adathalmazokon hatékony kieső érték kereséshez, például online csalások és egeszségügyi adatok esetén.
szerző
-
Lux Zoltán András
Villamosmérnöki szak, alapképzés
alapképzés (BA/BSc)
konzulens
-
Dr. Ekler Péter
Docens, Automatizálási és Alkalmazott Informatikai Tanszék
