Üzleti intelligencia skálázható architektúrákon Doktori értekezés tézisek Sidló Csaba István ˝ Lukács András Ph.D. Témavezeto:
Eötvös Loránd Tudományegyetem Informatikai Kar Információs Rendszerek Tanszék Informatika Doktori Iskola Demetrovics János D.Sc. Információs Rendszerek Doktori Program Benczúr András D.Sc. Budapest, 2011.
1.
Bevezetés
Az üzleti intelligencia (BI, „Business Intelligence”) módszerei és eszközei, mint az várható volt, az elmúlt évtizedben elfogadottá váltak és széles körben el is terjedtek. Ma a BI egyre nagyobb szerepet kap nemcsak vezet˝oi döntések meghozatalában, hanem mind több vállalat napi m˝uködésében is. Mindeközben, ami viszont kevésbé volt el˝ore látható, az IT-világ nagyot fordult, és nagy változásokon megy keresztül napjainkban is. A webes tartalmak, a mobil alkalmazások, a közösségi hálózatok és az on-line adatmennyiségek robbanásával együtt új technológiák, paradigmák, eszközök, valamint új felhasználói igények jelennek meg. A dolgozat célja üzleti intelligencia megoldások fejlesztése, javítása az új igényeknek megfelel˝oen. Az értekezés három BI témakörre koncentrálva mutat be új eredményeket. Ezen eredmények kiterjesztik az üzleti intelligencia módszerek alkalmazhatóságának határait. A témakörök, a konkrét problémák felvetései és arra adott válaszok egymásból következnek, id˝orendben haladva logikus folytatásai egymásnak. Az eredmények mindegyikét valós üzleti igény, a létez˝o eszközökkel nem, vagy csak nehezen megoldható probléma motiválta. Emiatt miközben a kidolgozott konkrét algoritmusok, formalizmusok és módszerek tudományos értelemben is el˝orelépést jelentenek, konkrét gyakorlati alkalmazások igazolják vissza azok használhatóságát és hatékonyságát. Az els˝o BI témakör a régóta kutatott és klasszikus adatbányászatnak mondható gyakori termékhalmaz keresés. Kiinduló feltevésünk szerint a relációs adatbázisok megfelel˝o alapot nyújthatnak adatbányászati algoritmusok számára. Ezt igazolandó olyan, relációs adatbáziskezel˝o rendszerekhez szorosan illeszked˝o új adatbányászati algoritmusokat ismertetünk, melyek hatékony megoldást jelentenek gyakori termékhalmazok keresésére SQL alapokon. A relációs adatbáziskezel˝o rendszerek és adatbányászati módszerek vizsgálata során beazonosíthatóvá váltak a relációs adatbázis architektúrák BI szempontból gyenge pontjai. Az eredmények második csoportját ebb˝ol ered˝oen az a kérdés motiválta, hogyan lehetne ezen architektúrákat költséghatékony módon, adatbányászati és BI igényeknek megfelel˝oen b˝ovíteni. Az értekezés második témaköre tehát az architektúrák világa; ennek kapcsán bemutatásra kerül egy, a gyakorlatban is kipróbált hatékony prototípus architektúra. A döntéstámogatási módszerek vizsgálata és konkrét megoldások kidolgozása során az adatmin˝oség javító módszerekre különösen nagy hangsúlyt fektettünk. Olyannyira, hogy az adatmin˝oség kérdése motiválta a harmadik témakör választását. Számomra is világossá vált, hogy jól skálázódó, hatékony adatbányászati algoritmusok sem alkalmazhatók megfelel˝oen a gyakorlatban, ha a rendelkezésre álló adatok min˝osége nem megfelel˝o. Igaz azonban sajnos az is, hogy az elterjedt adattisztító eszközök és módszerek képességei meglehet˝osen korlátozottak. Az értekezés harmadik témaköre az 1
azonosságfeloldás, mint az adatmin˝oség javítási feladatok olyan csoportja, ahol a korábban ismert eljárások látványosan nem elégítik ki az üzleti intelligencia igényeket. A dolgozat eredményei olyan jól használható módszerek, melyek hatékonyan oldják meg az azonosságfeloldás feladatát relációs adatbázisok, hatékony indexelés, majd új generációs osztott architektúrák felhasználásával. A kutatás munka els˝odleges célkit˝uzései az adatbányászati (tágabb értelemben pedig BI) módszerek és az adatbázisok integrációjának javítása, új, a gyakorlatban is jól használható, ezen adattároló architektúrákkal hatékonyan együttm˝uköd˝o, jól skálázódó algoritmusok el˝oállítása voltak. A kutatás módszerei megfelelnek az adott területen bevett gyakorlatnak. A témák kifejtése során a kapcsolódó irodalmat részletesen feldolgoztuk és áttekintettük. Ahol lehetséges, vizsgáljuk a problémák algoritmikus bonyolultságát és bonyolultsági korlátait. A legfontosabb próbák mégis – a feladatok jellegéb˝ol adódóan – a gyakorlati problémák megoldásai voltak. Nagy hangsúlyt fektettünk nemcsak a kísérletek megfelel˝o min˝oség˝u kivitelezésére, de prototípus rendszerek és valós alkalmazások kifejlesztésére is. Az eredményeket nemzetközi konferenciákon és workshop-okon mutattuk be a terület kutatói közösségének. A füzet végén található „Publikációk” rész felsorolja ezen, a téziseknél is hivatkozott közleményeket. Az általam eddig megismert küls˝o hivatkozások felsorolása szintén a befejez˝o részben található.
2.
Új eredmények
Az értekezésben öt tézis köré rendezve kerülnek bemutatásra új eredmények. Ebb˝ol egy gyakori termékhalmaz kereséssel foglalkozik, egy architektúra javaslatot ismertet üzleti intelligencia alkalmazásokhoz, három pedig azonosságfeloldási algoritmusokat és módszereket tárgyal. Gyakori elemhalmaz bányászat A gyakori termékhalmazok, vagy általánosabb elnevezéssel élve gyakori elemhalmazok keresése (FIM, azaz „Frequent Itemset Mining”) az adatbányászat klasszikus feladata, ami számos más feladat megoldását is lehet˝ové teszi, mint asszociációs szabályok vagy gyakori sorozatok keresése. A terület kiterjedt irodalommal, sok algoritmussal és implementációval rendelkezik (lásd [Han 06] vagy [Freq]). A FIM probléma lényege gyakori minták keresése olyan nagy adathalmazokban, melyek tranzakciókba (kosarakba) rendezett elemeket (termékeket) tartalmaznak, mint egy bolt vásárlói kosarainak klasszikus példájánál. A feladat azon gyakori elem (termék) halmazok megtalálása, melyek támogatottsága, tehát hogy hány tranzakcióban (kosárban) szerepelnek, nagyobb egy el˝ore megadott küszöbértéknél.
2
Érdekl˝odésünk tárgya a relációs adatbáziskezel˝ok és a FIM algoritmusok viszonya, annak vizsgálata, hogy mennyire lehetnek hatékonyak a relációs adatbáziskezel˝o rendszerekkel szorosan integrált FIM algoritmusok. Az irodalom több jelöltállítás alapú algoritmus relációs környezetbe ültetett változatát tárgyalja, de az algoritmusok másik nagy és hatékony osztálya, a mintanövel˝o algoritmusok alulreprezentáltak (lásd [Han 00, Shan 04]). 1. Tézis. Hatékony SQL-alapú gyakori termékhalmaz keres˝o algoritmus [FIM 1] Kidolgoztunk és ismertettünk egy relációs adatbázis környezetre és SQL m˝uveletekre épül˝o mintanövel˝o FIM algoritmust, ami hatékonyan használja ki az adatbáziskezel˝o rendszer nyújtotta szolgáltatásokat, valamint illeszkedik annak adatmodelljéhez és más megkötéseihez. A gyakorlati alkalmazhatóságot kísérletek és egy prototípus alkalmazási példa demonstrálják, szemléltetve az el˝orelépést a korábbi algoritmusokhoz képest. Az eredményeket Lukács Andrással közösen publikáltuk [FIM 1], akinek hozzájárulása az FIM problémával kapcsolatos irodalmi és általános bevezet˝o részek kidolgozása. Üzleti intelligencia architektúrák Üzleti intelligencia alkalmazások megvalósításához, kiszolgálásához többféle architektúraváltozat közül választhatunk. Gyakori a relációs adatbáziskezel˝ok használata platformként, relációs adattárházak építésére vagy ad-hoc elemz˝o alkalmazásokra is. Bár valószín˝uleg sokszor a feltör˝oben lév˝o osztott architektúrák (mint a Hadoop vagy más osztott NoSQL, azaz nem relációs megoldások) jelenthetnek hatékony alternatívát, egyértelm˝uen látszódnak mind a NoSQL, mind pedig a relációs megoldások korlátai. Az értekezés azt a kérdést vizsgálja, hogyan b˝ovíthet˝ok ki a relációs adatbáziskezel˝ok adatbányászati, és általában véve üzleti intelligencia platformmá. Az adatbányászati feladatok megoldására léteznek hatékony megoldások, de ezek függetlenek az adatokat legtöbbször tartalmazó adatbáziskezel˝o rendszerekt˝ol. Beazonosítva a relációs technológia határait és az adatbányászati feladatok igényeit megtervezhet˝o egy olyan architektúra, ami hatékonyan ötvözi az elérhet˝o adattároló eszközök el˝onyeit. 2. Tézis. Kétfázisú üzleti intelligencia architektúra [Arch 1, Arch 2] Kidolgoztunk és ismertettünk egy olyan architektúra típust, ami képes költséghatékonyan és tudásfeltárási feladatok megoldásához célszer˝u módon integrálni relációs adattárházakat és oszloporientált, hosszú távú tárolást és adatbányászatot támogató rendszereket.
3
Az eredmények Benczúr A. Andrással, Csalogány Károllyal, Lukács Andrással, Rácz Balázzsal, Uher Mátéval és Végh Lászlóval közösek. Az én hozzájárulásom mindkét cikkben [Arch 1, Arch 2] az általános architektúra kidolgozása, az integráció problémáinak felvázolása és megoldása konkrét prototípus alkalmazás kivitelezéséig, valamint a prototípus webanalitikai adattárház megtervezése, felépítése és m˝uködtetése voltak. A bemutatott architektúra alkalmazhatóságát prototípus rendszer demonstrálja, ahol egy kereskedelmi adatbáziskezel˝o és egy saját adatbányászati keretrendszer integrációja segítségével oldunk meg webanalitikai feladatokat. Az eredményeket a magyar [origo] portál weblogjára felépített webanalitikai kétfázisú adattárház éles alkalmazásában validáltuk. Korábbi hasonló webanalitikai projektek a nagy adatmennyiség (akkoriban 7-9 millió oldaltalálat, 35 GB körüli nyers webszerver logfile naponta) miatt ezen hagyományos adattárház megközelítés˝u projektek sorra elbuktak a viszonylag nagy ráfordítások ellenére. A kétfázisú architektúránkkal sikerült ugyanezen feladatra költséghatékony módon egy olyan elemz˝o rendszert építenünk, ami éveken át m˝uködött minimális ráfordításokkal. Azonosságfeloldás Az azonosságfeloldás (ER, „Entity Resolution”) rejtett, való világbeli entitásokhoz köthet˝o megfigyelések csoportosítása az entitások köré. Ugyanezen témát többféle elnevezéssel sokféle megfogalmazásban tárgyalják, úgymint például duplikátum-keresés, deduplikálás, rekord összekapcsolás ([Talb 10] ad közérthet˝o összefoglalót a témakörr˝ol). Munkánk során nyilvánvalóvá vált, hogy egy hatékony, jól skálázódó azonosságfeloldó algoritmusra sok üzleti intelligenciai, de számos operatív alkalmazásnak is szüksége van. Az azonosságok felismeréséb˝ol profitálhatnak CRM és marketing rendszerek, törzsadat rendszerek, de akár a webes keres˝ok és más webes szolgáltatások is. Azonosságfeloldás nélkül olyan alapvet˝o kérdéseket sem lehet megbízhatóan megválaszolni, mint például hány ügyfelünk is van, vagy hogy kerestünk-e már egy adott ügyfelet célzott reklámmal. A f˝o nehézséget legtöbbször az adathalmazok mérete jelenti: nem állnak rendelkezésre olyan algoritmusok, amelyek képesek lennének megbirkózni a gyakorlatban el˝oforduló adatmennyiségekkel. Az irodalom korábbi algoritmusai jellemz˝oen memória alapon és kis adathalmazt feltételezve készültek. A dolgozat áttekinti az azonosságfeloldás és kapcsolódó témák irodalmát, beazonosítja az alkalmazások igényeit, majd több IT környezetre és feladat-változatra is hatékony megoldó algoritmust ismertet. Bemutatásra kerül többféle, részben új modell, motivációs példák és alkalmazások. A következ˝o tézisek [ER 1, ER 2, ER 3] publikálás ideje szerint következnek egymás után. A bemutatott módszerek egyre hatékonyabbak is, de a tézisek eredményei egymásra mer˝olegesnek tekinthet˝ok. Akárcsak a gyakori elemhalmaz bányászó algoritmusoknál, itt is jogos a kérdés, hogy mennyire 4
használhatók fel a relációs adatbáziskezel˝o rendszerek képességei az adott feladat megoldásához. Ezen megoldások el˝onyös tulajdonsága lehet, hogy általánosan elterjedt, legtöbbször az adatot magát is tartalmazó rendszerre épülnek, melyek már bizonyítottak nagy adathalmazok tárolása, feldolgozása és elemzése során. 3. Tézis. Hatékony relációs adatbáziskezel˝o alapú ER algoritmusok [ER 1] Elkészítettem és bemutattam olyan, relációs adatbázisra tervezett modelleket majd ezekre épül˝o algoritmusokat, melyek jól skálázódnak az adatmennyiséggel. Ezen algoritmusok a gyakorlatban jól alkalmazhatóak és a korábban ismert hasonló algoritmusoknál hatékonyabbak. Az eredményeket egyedüli szerz˝oként ADBIS konferencián ismertettem, majd a konferencia válogatott cikkeivel LNCS folyóirat számban jelent meg [ER 1]. A megoldás hatékonyságát kísérletek valamint esettanulmány szemlélteti. A gyakorlatban való alkalmazhatóságot az AEGON Magyarország biztosító ügyfél adattárház környezetében való éles használat támasztja alá. Ezen alkalmazásban 10 millió körüli ügyfélrekordra végezzük el az azonosságfeloldást egy hagyományos, közepes teljesítmény˝u adatbázis szerveren, ami a korábban publikált eredmények alapján elérhetetlennek t˝unt. Az ER megoldás szorosan integrált egy, a biztosító által a napi m˝uködésben is használt ügyfél adattárházzal, és jelenleg is m˝uködik. Az adatbáziskezel˝o rendszerek egy központi, jól kidolgozott szolgáltatása, amit többek között a relációs algoritmusok is használnak, a hatékony indexelés. Korábban is születtek ugyan algoritmusok, amik az illeszked˝o rekordok keresésekor index-szer˝u konstrukciókat használtak, de ezen módszerek felhasználhatóságának vizsgálata, és indexeket megfelel˝oen használó algoritmusok kifejlesztése korábban nem történt meg. 4. Tézis. ER algoritmusok hatékony indexeléssel [ER 2] Kidolgozásra és bemutatásra kerültek olyan, memóriakorláttól független, küls˝o tárat is használó algoritmusok, melyek hatékonyan építenek és használnak entitás-indexeket az azonosságfeloldás feladatának megoldásához. Az eredményeket egyedüli szerz˝oként ADBIS konferencián ismertettem, és a konferencia kiadványában jelent meg [ER 2]. Azt, hogy megéri indexeket építeni és karbantartani a keresési id˝ok rövidülése miatt, mérések és esettanulmány igazolja. Az algoritmusokat a 3. Tézis biztosítói adattárházának környezetében és feladatára vizsgáltuk. Az ER algoritmusok skálázhatóságának javítására az indexelés, a feladat hatékony keresésekre való visszavezetése mellett a párhuzamosítás bevett módszere kínálkozik, ami a következ˝o tézis alapja. A párhuzamosításra, a feladat szétosztására azonban több lehet˝oségünk is kínálkozik, melyek közül talán az újonnan kifejl˝odött, s˝ot fejl˝od˝oben lév˝o keretrendszerek és paradigmák a legérdekesebbek. 5
5. Tézis. Osztott ER algoritmusok [ER 3] Megmutattuk, hogy az ER feladat hatékonyan megoldható osztott számítási környezetekben, konkrétan • osztott kulcs-érték tárolókkal, • Map-Reduce keretrendszerekkel, • kötegelt szinkronizált párhuzamos feldolgozással (BSP, „Bulk Synchronous Parallel”). A párhuzamos algoritmusaink leghatékonyabbja az általunk jelenleg ismert legjobban skálázódó ER megoldás. Az eredmények közösek Garzó Andrással, Molnár Andrással és Benczúr A. Andrással. Az én hozzájárulásom a feladat megfogalmazása, a három párhuzamosítási lehet˝oség felvetése, részvétel ezek kidolgozásában, a kulcs-érték tárolókon alapuló algoritmusok részletes kidolgozása és implementálása, a biztosítói adathalmaz el˝oállítása és a kísérletek koordinálása voltak. Az alkalmazhatóságot a 3. Tézis biztosítói adattárházának környezetében és feladatára vizsgáltuk, és kísérletekkel igazoltuk. Szintén vizsgáltuk az algoritmusok kommunikációs bonyolultságának alsó korlátait, illetve a leírt modellel lefedhet˝o feladatok körét. Az azonosságfeloldó algoritmusaink kiértékeléséhez némileg eltér˝o környezeteket használtunk, emiatt pedig lehetetlen a precíz összehasonlítás. Ennek ellenére érdemes áttekinteni az 1. ábrát a felhasználhatóság hozzávet˝oleges értékeléséhez, ahol biztosító ügyféladatain alkalmazott azonosságfeloldás futásidejét ábrázoljuk a rekordok számának függvényében (a bal a jobb oldal nagyított változata). A grafikonon • Java-F-Swoosh: a legjobb korábban publikált általános azonosságfeloldó algoritmus (F-Swoosh [Benj 09]) egy Java implementációja, • DB-GER: a legjobb relációs azonosságfeloldó algoritmusunk relációs adatbázis alapokon, • index-ER-BDB: a legjobb hatékonyan indexel˝o, nem párhuzamos algoritmusunk, és • MapReduce: a legjobb elosztott algoritmusunk, 15 darab szerveren futtatva. Korábbi eredmények 10 vagy 100 ezres nagyságrend˝u rekordszámot feltételeznek; erre példa egy, az osztott környezet miatt hasonló új alkalmazás 114 ezer rekordja [Kirs 10], ami hasonlóság alapú egyezést alkalmaz. A mi kísérleteinkhez legközelebb 10 millió rekorddal jutottak [Weis 08]. Ehhez képest is jelent˝os javulást jelent azonban a mi kísérletünkben szerepl˝o 600 millió rekord.
6
1. ábra. Azonosságfeloldó algoritmusaink skálázhatósága ügyféladatokon
7
Hivatkozások [Benj 09] O. Benjelloun, H. Garcia-Molina, D. Menestrina, Q. Su, S. E. Whang, and J. Widom. „Swoosh: a generic approach to entity resolution”. VLDB J., Vol. 18, No. 1, pp. 255–276, 2009. [Freq]
„Frequent Itemset Mining Implementations Repository”. helsinki.fi/. [last accessed: 2 August 2011].
http://fimi.cs.
[Han 00] J. Han, J. Pei, and Y. Yin. „Mining frequent patterns without candidate generation”. In: Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp. 1–12, ACM Press, 2000. [Han 06] J. Han and M. Kamber. Data mining: concepts and techniques. The Morgan Kaufmann series in data management systems, Elsevier, 2006. [Kirs 10] T. Kirsten, L. Kolb, M. Hartung, A. Gross, H. Köpcke, and E. Rahm. „Data Partitioning for Parallel Entity Matching”. Computing Research Repository, 2010. [Shan 04] X. Shang, K.-U. Sattler, and I. Geist. „SQL Based Frequent Pattern Mining with FPGrowth.”. In: INAP/WLP, pp. 32–46, 2004. [Talb 10] J. R. Talburt. Entity Resolution and Information Quality. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st Ed., 2010. [Weis 08] M. Weis, F. Naumann, U. Jehle, J. Lufter, and H. Schuster. „Industry-scale duplicate detection”. Proc. of the VLDB Endow., Vol. 1, No. 2, pp. 1253–1264, 2008.
8
Publikációk [FIM 1]
Csaba István Sidló and András Lukács. „Shaping SQL-Based Frequent Pattern Mining Algorithms”. Knowledge Discovery in Inductive Databases: 4th International Workshop, KDID 2005, Revised Selected and Invited Papers, pages 188–201, 2005. [Arch 1] Andras A. Benczúr, Károly Csalogány, András Lukács, Balázs Rácz, Csaba Sidló, Máté Uher and Laszló Végh. „An Architecture for Mining Massive Web Logs with Experiments”. In Proceedings of the HUBUSKA Open Workshop on Generic Issues of Knowledge Technologies, 2005. [Arch 2] Balázs Rácz, Csaba István Sidló, András Lukács and András A. Benczúr. „Two-Phase Data Warehouse Optimized for Data Mining”. Lecture Notes in Computer Science, volume 4365, 2007. [ER 1] Csaba István Sidló. „Generic Entity Resolution in Relational Databases”. In Proceedings of the 2007 International Conference on Advances in Databases and Information Systems (ADBIS 2007), Lecture Notes in Computer Science, volue 5739, pages 59–73, 2007. [ER 2] Csaba István Sidló. „Entity Resolution with Heavy Indexing”. In Proceedings of the 2011 International Conference on Advances in Databases and Information Systems (ADBIS 2011), CEUR Workshop Proceedings, 2011. [ER 3] Csaba István Sidló, András Garzó, András Molnár and András A. Benczúr. „Infrastructures and Bounds for Distributed Entity Resolution”. In Proceedings of the 9th International Workshop on Quality in Databases In conjunction with VLDB 2011 (QDB 2011), 2011.
Egyéb kapcsolódó publikációk [Alg 1] [WA 1]
Iványi Antal (alkotó szerkeszt˝o). „Informatikai algoritmusok”, 16. fejezet, Elek István, Sidló Csaba: Térinformatika, 188–201. oldal, ELTE Eötvös Kiadó, 2005. Fajszi Bulcsú, Cser László és Fehér Tamás (alkotó szerkeszt˝ok). „Üzleti haszon az adatok mélyén”, 11. fejezet, Sidló Csaba: „Webanalitika és látogatottságelemzés”, 243–266. oldal, Alinea Kiadó, 2010.
9
Publikációk küls˝o hivatkozásai [R 1]
Talburt, John R., „Entity Resolution and Information Quality”, Morgan Kaufmann Publishers Inc., 1st edition, 2010. [R 2] Zhengrui Jiang. „A Decision-Theoretic Framework for Numerical Attribute Value Reconciliation”, IEEE Transactions on Knowledge and Data Engineering, volume 99, IEEE Computer Society, 2011. [R 3] Grabowski Sz. and Deorowicz, S., „Efficient preprocessing for web log compression”. International Scientific Journal of Computing, pages 35–42, 2006 [R 4] Eszter P. Windhager and Libertad Tansini and Istvan Biro and Devdatt Dubhashi, „Iterative Algorithms for Collaborative Filtering with Mixture Models”. In Proceedings of the International Workshop on Intelligent Information Access,2006. [R 5] E. Khorram and S. M. Mirzababaei. „Finding an Optimized Discriminate Function for Internet Application Recognition”. In Proceedings of the Second World Enformatika Conference, WEC’05. pages 160–163, 2005. [R 6] M. Rahmati and S. M. Mirzababaei. „Data Mining on the Router Logs for Statistical Application Classification”. In Proceedings of the Second World Enformatika Conference, WEC’05, 2005.
10
