Lágy számítások XML adatkezelésben és deduplikációban

.
Eddig még sose tettem ilyet ezen a blogon, remélem nem túlságosan "necces" meg "gáz", hogy most ilyenre van hangulatom.

Ajánlom ezt a blogposztot...
* a Sztaki ifj. Benczúr András és Lukács András vezette adatbányász csapatának, akiknek eddig sosem tudtam eléggé megköszönni, hogy megengedték személyes részvételemet műhelymunka keretében való egyes témábavágó, - ennek a posztnak az alapját is képező cikkhez hasonlatos típusú - cikkek ismertetésén. Sőt, amikor kérdést tettem fel, akkor sem tették ki a szűrömet.
* Sidló Csabának, akinek a DeDup témában való cikkismertetéseit/előadásait mindig is külön rákészülve, és ami fő, élvezettel hallgathattam az elmúlt évek során.
* Fekete Zsoltnak, aki élményszámbamenően hatékony kérdéseket és felvetéseket tud megejteni a cikkek széles skáláján/spektrumán.
* Gáspár-Papanek Csabának (blog), irányomba való jóindulatáért, segítőkészségéért.
* Kovács Gyulának és Arató Bencének, akiknek a legutóbbi sikeres DeDup-projektemet köszönhetem, aminek során, síma notebookon, 100% vegytiszta Oracle-környezetben, teljes céges deduplikálást 70 másodperces, teljes magánszemélyes deduplikálást 20 perces futásidőre tudtam optimalizálni, érdekes akviziciós ügyfélkonszolidáció keretében.

Nem akármilyen könyv jelent meg és került ragadozó kezeim közé, a fenti tárgybeli (angol) címmel Soft Computing in XML Data Management, a Springer kiadónál, idén 2010-ben, 363 oldalon, 130 euróért (uszkve 40.000 forint).

Az összesen 12 cikk, egyenletesen három nagy témába sorolódik:
1. Fuzzy típusú határozatlanság XML-ek vonatkozásában
2. Rugalmasság az XML típusú adatmenedzsmentben
3. Néhány fejlesztés és alkalmazás a témában

Mielőtt belevágnánk egy kis bevezető a címhez.

A soft computing magyarul lágy számítások a mesterséges intelligencia és ezen keresztül az adatbányászat kulcsfontosságú területe, eredendően olyan típusú nehéz (matematikai) problémákra - amelyek explicit meg nyers erő módszerekkel nehezen kezelhetők - vázolt egyfajta alternatív megoldási lehetőséget. Klasszikusan a (1) Fuzzy, (2) Neurális háló, (3) Evolúciós/Genetikus algoritmusok illetve ezek tetszőleges kombinációi tartoztak bele, mára a wikipedia szerint például még a Bayes háló is beletartozik, számomra némileg meglepő módon. A blogposzt címében lévő könyv alapvetően egyébként a fuzzy vonulatot tárgyalja /azért van benne Bayes háló is :o)/. A lágy számításos témáról az 1922-es születésű, műegyetemi professzor emeritus, Retter Gyula írt szenzációs, friss, két - ráadásul  magyar nyelvű - könyvet.
(1) Fuzzy, neurális genetikus, kaotikus rendszerek : bevezetés a "lágy számítás" módszereibe
(2) Kombinált fuzzy, neurális, genetikus rendszerek

Az XML, mint a neve is mutatja egy Markup Language-féleség, nagyszerű tulajdonságai - teljesség igénye nélkül:
* text-formátum
* félig-strukturáltság
* különbségképzési lehetőség
* szintaktikai meg valamilyen fokú szemantikai konzisztencia biztosítása
Nem véletlen hogy mára széles körben nagyon jól használható formátumnak bizonyult.Többek közt adatok tárolására is. De nemcsak szimplán relációs világban megszokott rekordok tárolására jó. Kottázó programok(!) szabványos kimenete is például. Ad absurdum multimédiás és/vagy bináris adatokat is tudhat hordozni.Az Oracle rdbms-ben külön keletkezett XMLtype típusú mezőféleség speciális funkcionalitással, stb.

A könyv első mondhatni bevezető és felcsigázó része:
(1) cikk például a fuzzy adatokat tartalmazó XML adatforrások fuzzy reprezentációjához használható XMLschema lehetőségeit vesézi. Ez önmagában cikk nélkül is egy érdekes gondolat, akkor is ha eddigi életemből a fuzzy-vonulat eléggé kimaradt.
(2) cikk a fuzzyval megspékelt(beágyazott) relációs adatbázisról szól, fuzzy DTD-vel való leképzéssel
(3) cikkben a fuzzy halmazok és hasonlósági relációk szintén egy érdekes téma.
(4) De mindezeket übereli a könyv ezen részének zárófejezete: adatintegráció XML-ek segítségével. Egy ponton túl, ahonnan a relációs ábrázolás már nehézkes, amikor már nem csak az adatok hanem a befoglaló struktúráik is lehetnek képlékenyek, kézenfekvően merülnek fel a XML nyújtotta félig-strukturáltság előnyei, speciális szabályrendszerrel megspékelve. (Érdekesség: integrációs algoritmus alapjának az XQuery-t választották a cikk szerzői!!!!)

A könyv második részében olyan témák kerülnek elő, hogy
(1) ha már az adatok és strukturáik kevéssé fixek (horribile dictu heterogén környezetből származóan), akkor a rajtuk való keresés és join is más megközelítést igényel, ha eredményre akarunk jutni.
(2) cikk azt feszegeti, hogy az XQuery-ből hogyan lesz fuzzy XQuery.
(3) Egy további lehetőség az XML nyújtotta rugalmassági előnyök kiaknázására, amikor relációs adatokat XML-leképezve (ez ugye eléggé könnyedén megtehető, pláne, hogy szigorúbb struktúrából könnyebb áttérni egy megengedőbb struktúrába) egy bővített funkcionalitású lekérdezési interface-t lehet adni az a leképzett adatokra.
(4) Végül a könyv ezen részét lezáró, az első rész szintén utolsó cikkével nagyban harmonizáló deduplikációs cikkfinomság, de erről külön szeretnék beszélni, hiszen őmiatta születik ez a blogposzt.

A könyv harmadik részére megjön az igény, hogy a már meglévő újszerű tárolású és tálalású adataink köré most már kész alkalmazást is kellene építeni.
(1) Itt lehet említeni például  a Fuzzy Process Modellek részére XML-alapú adatcserét.
(2) Sőt lehet XML-alapú keretrendszert építeni inkomplett és inkozisztens adatok menedzselésére (a cikkben konkréten egy klinikai rendszerként).
(3) Sőt nagyot álmodva komplett Fuzzy Adatbázis Architektúra is konstruálható (Alliance), fuzzy-logika technikákkal, XML-bázison.
(4) A könyvet lezáró utolsó cikkben már az indexelés vonatkozásai is hangsúlyt kapnak, a szemantikai feltárással egyetemben.

És akkor nézzük a második rész negyedik amúgy 32(!) oldalas cikkét:

An Overview of XML Duplicate Detection Algorithms.

A magyarul DeDuplikálás vagy röviden DeDup életem meghatározó feladata, élménye. Több ilyen projektben dolgoztam, még többet láttam. Egyszer talán lesz mód, hogy megírjam ebbéli élményeimet, tapasztalataimat.Már többször nekikezdtem egyébként, hogy valamit megírjak belőle ezen a blogon, de akárhonnan közelítettem, mindig túl sok volt az anyag, mindig túlnőttem a képzeletben magam elé állított kereteket, így eddig minden ilyen irányú próbálkozásom kudarcba fulladt.

Pár dolgot viszont mindenképpen érdemes magyarázólag és előljáróban említeni a továbbiakhoz.

(1) Ha az egyik informatikai rendszerben egy urat Szalamander Gáborként, egy másikban Szalamander G.ként tárolják, miközben az anyja neve, személyigazolványszáma stb megegyezik, akkor triviálisan egy és ugyanazon húsvér ember adatai vannak különféleképpen tárolva. Persze nemcsak rövidítés, hanem elírástól elkezdve a legkülönfélébb hibákig sokféle eltérés lehet a rögzített adatokban.Kézenfekvően merül fel a feladat, hogy az egy emberhez tartozó különféle adatrekordokat kapcsoljuk valahogy össze a rekordokban lévő természetes, ám nem feltétlen kitöltött adatok illetve nem feltétlen egzakt egyezés alapján (mivel az amúgy egyébként preciz rögzítésű valamint 100%-os kitöltöttségük miatt jól használható informatikai egész azonosítók eltérnek, így azok nem használhatók a feladatban).Az előbbiek (természetes adatok) alapján a deduplikálásnak komoly nyelvspecifikus vonzatai is vannak, ami magyar nyelvterület esetén - mint sok mindenben így itt is - tudhatnak komoly kihívásokba ütközni (egy példa; Ausztráliában összehasonlíthatatlanul egyszerűbb a lakcímek kezelése)

(2) Ha van egy nagy táblánk, amiben minden húsvér ember minden rekordja szerepel, akkor adatbányász terminológiával élve kezdetben csoportosítást kell végezni a rekordokra, újabb rekordok megjelenésekor meg osztályozást.

(3) A számítógépes/algoritmikus DeDup elméletileg bizonyíthatóan sosem lehet 100%-ban tökéletes. Elsőfajú hibaként tévesen is kerülhet be egy rekord a rekordcsoportba, másodfajú hiba szerint maradhat is ki rekord egy rekordcsoportból.Az ilyen problémák kiküszöbölésére humán erőforrást (brrr) szoktak alkalmazni.

(4) Két adatrekordról eldönteni adatösszevetéssel, hogy akkor most ők egy ember két rekordja szintén nagyon nehéz feladat (gépileg is és kézzel is), alapvetően szabályrendszert szoktak megadni rá. Mivel az elsőfajú hiba a sokkal inkább üldözendő, ezért az ilyen közelítő szabályrendszer alapvetően "szigorú" és kevésbé megengedő szokott lenni (egy csaló ember rekordját egy VIP ember rekordjával nem "praktikus" összevonni). Az összevont/csoportosított rekordokból meghatározni egy "legjobb rekordot" megint nagyon nehéz feladat, amit megint csak közelítőleg lehet megoldani.

(5) A nyers erő (brute force) algoritmus szerint minden rekordot mindenkivel összehasonlítva négyzetes lesz az algoritmus műveletigénye. Mivel többszázezres deduplikálandó ügyfélállományok még Magyarországon sem ritkák, ezért ez az út a lehetetlenség útja, az óriási és elvégezhetetlen számítási igény miatt.

(6) Belátható, hogy a mindent mindennel összehasonlítás túlnyomórészt felesleges is. Tehát az igazi feladat minden szükséges hasonlítást elvégezni a a hasonlítások számának minimalizálásával.


És akkor most már nézzük a DEDUPLIKÁCIÓS CIKKet néhány részletében.

A célkitűzése egyfelöl egy új reprezentáció megadása a deduplikálásra, a hatásosság(=effectiveness) szofisztikáltság értelemben és a hatékonyság(=efficiency) azaz mondjuk most így műveletigény csökkentés jegyében. Majd összehasonlítóan megvizsgál három létező rendszert (DogmatiX, XMLDup, SXNM), amelyek különféle módokon egyensúlyoznak a hatékonyság és eredményesség között. Az első és harmadik struktúra-vezérelt metódus, a közbülső pedig Bayes-hálós.

A cikk nagyságrendi adata szerint 2002 óta évi 600 milliárd dollárt költenek adatminőségi problémákra csak az USÁ-ban. Azaz összevethetőség szempontjából megjegyezhető: a teljes magyar adósság többszörösen belefér ekkora éves(!) összegbe.

Az adatintegráció három lépése:
(1) Séma-megfeleltetés/illesztés és - leképezés (schema matching, schema mapping).
Idetartozik, hogy ha az egyik forrásban név mellett csak az anyja neve van, a másikban meg csak a telefonszám, akkor a közös sémában mindkettő plusz attribútum fog szerepelni
Idetartozik, hogy például ugyf_tel attribútumban (és nem egy másikban) van a szükséges telefonszám adat.
Idetartoznak olyan finomságok is, ha az egyik adatforrásban külön vannak a család- és keresztnevek egy másikban egyben Magyar nyelvterületen olyan típusú "örömökkel", mint például Hunné Zoltán Erika.
(2) A duplikátum-detektálás ezen a fenti közös sémára hozott adatokon.
(3) Az adatfúzió, amikor a szükséges sorok összevonódnak (közös azonosítót kapnak).

Az angol szakirodalomban 1959-től kezdve időrendi sorrendben a következő terminológiák sorolódnak fel a deduplikálásra. :o)
* record linkage
* entity identification
* deduplication
* duplicate detection
* object matching
* entity resolution
* fuzzy duplicate identification
* object consolidation
* reference reconciliation
* object identification

Mivel XML-ben vannak az adatok, rögtön merül fel a kérdés mit nyerünk és veszítünk a relációs módihoz képest.
Előny: sokkal flexibilisebben, korlátok nélkül tárolódhatnak benne az adatok, illetve a hierarchikus (fa)struktúra révén kellemesebb műveletigényű deduplikáló algoritmus lehetősége csillan meg.
Hátrány: jóval nehezebb maga a deduplikálás, az alábbi két probléma mentén
(A) candidate-description ambiguity (én most így mondom, adatszintű többértelműség)
(B) structural diversity (strukturális különbözőség)

Szakirodalom alapján az alábbiak hozhatók fel XML-centrikusan szemlélve a hagyományos deduplikálás történelmi előzményeként. A komponensek kvázi tetszőleges kombinációja megtalálható a cikkben, olykor irodalmi jegyzékes hivatkozással is. :o)
ADAT: (1) relációs tábla (2) Fa például XML-adat (3) Gráf például XML kulcsreferenciák.
ALGORITMUS: (1) Iteratív (2) klaszterező split and merge alapon (3) gépi tanuló algoritmus, ahol a modell is, a hasonlóságmérték (=similarity) is tanulás tárgya
ALGORITMUS FÓKUSZ: (1) Hatásosság, minőség (2) Hatékonyság (3) Skálázhatóság

XML-alapú deduplikálás történelmi előzményei:
* Úgynevezett közelítő (approximate) XML-join, saját - tree edit - távolság-fogalommal.
* Vektorokra leképzés, cosinus távolsággal
* Súlyozott hasonlósági mértékek lineáris kombinációja deduplikációs mezők fontossága alapján
* Ezután robbanásszerűen szaporodtak az olyan XML-alapú deduplikálások, amik egyre jobban támaszkodtak az XML-sajtosságaira (struktúra, szemantika)

Nézzük akkor a beveztőben említett és a cikk fókuszában lévő három algoritmust/rendszert:

Itt egy ábra két node-dal, IMDB filmadatbázisból:

I. DogmatiX Framework

(A) candidate definition, azaz a duplikátum-jelöltek (alap)definiciója, azaz megmondani, hogy az XML-ben mely csomópontok képezik a hasonlítgatások tárgyát. Régi relációs terminológiában annak megmondása, hogy mely mezők alapján hasonlítunk két ügyfél-rekordot (például anyja neve alapján igen, átlagegyenlege alapján nem)

(B) duplication definition, azaz mikor kell összevonni két egyedet (és mikor nem). Természetesen minden fentebb definiált jelöltre megadva. Ez ebben a DogmatiX-ben praktikusan egy Xquery-kifejezés lesz. A query egy (text,xpath) párosba fog leképződni, aminek a hivatalos neve, Object Description (=OD). Példa: U-> ("John S.", /mv/dr/text()) illetve U*-> ("J.Smith", /mv/dr/text()). A dolog első ránézésre ijesztőnek néz ki, de könnyedén algoritmizálható r-távolságban lévő (1) ősökkel, (2) leszármazottakkal illetve (3) k db legközelebbi leszármazottra vett szélességi kereséssel.

(C) duplication detection, azaz hogyan kell duplikátumot találni. Első lépés a szükséges hasonlítások csökkentése egy filter függvénnyel, amely arányt számol a jól ismert IDF-fel (=Inverse Document Frequency) méghozzá egy adott - fentebb definiált - OD és az összes OD vonatkozásában. Pontosabban softIDF-et (attól soft, hogy vannak csak lényegében hasonló elemek, amiket azonosnak vesz). Ezután az - amúgy egy küszöbértéktől függő - filter után minden pár hasonlítódik egymással. Az U és U* hasonlósága (normalizált edit distance), a következőképpen néz ki (a konkrét fenti példánkban)

Sim(U,U*)=softIDF(Pros and Cons)/(softIDF(Pros and Cons)+softIDF(John S.)+softIDF(J.Smith))

Struktúra-vezérelt XML-távolság

Egy javítás lehetséges az előzőhöz képest, mégpedig egy speciális távolságfogalommal, az úgynevezett átfedések koncepció alapján  (=overlay). A fenti ábrán U és U* minden node-ja megfeleltetés révén átfedésbe hozható egymással, az U* egyszem AC2-jét leszámítva (annak nincs párja U-ban).

Egy átfedés akkor komplett, ha nem része másik átfedésnek.
Az átfedés költsége a mappelt node-os string-hasonlítások Levenshtein-távolságainak (~edit distance) összege.
Egy átfedés akkor optimális, ha komplett és nincs más átfedés, alacsonyabb átfedési költséggel.

A mélyben egy rekurzív algoritmus dolgozik gyökérből lefelé haladóan. A node-párosítás pedig az operációkutatásból ismert hozzárendelési problémánál ismeretes úgynevezett magyar módszer alapján történik.

Az állítás az, hogy a téves összevonások jobban elkerülhetők így (bőven elhihető), de meglepő módon kvázi ugyanolyan sőt akár még inkább könnyedén számolható az egész DogmatiX-es cucc az előző távolságfogalommal. Ezt mondjuk én most így hirtelen nem látom át, a cikk meg nem részletezi miért is.


II. SXNM—Sorted Neighborhood for XML Duplicate Detection

Ez a bottom-up metódus úgy próbálja csökkenteni a szükségtelen összehasonlítgatásokat, hogy miután minden hasonlítandó tényezőre kiszámol egy generált kulcsot - például: U{"Pros and Cons", 1983}->PRO83, U*{"Pros and Cons", 1984}->PRO84 - a kapott kulcsokat egyszer még a kezdetek kezdetén lerendezi és minden elemen egyszer végigmenve, minden elemnek csak a közvetlen - fixen rögzített - környezetétbe hasonlítgat bele.(Mj: A módszer magyar nyelvterületen ebben a formában bukásra van ítélve, ugyanis a kedves hölgyek férjhez mehetnek és felvehetik férjük nevét -> Salm Gizella, Matula Gizella). Persze a rendezés utáni műveletigény látványosan csökken a nyers erős módszer négyzetes műveletigényéhez képes O(nlog(n)).

A DogmatiX-hez hasonlóan az OD-k megkonstruálhatók, annyi a nóvum, hogy az OD-hez még relevancia is kapcsolódik pluszba. A hasonlóság elemzés is ugyanúgy mehet Levenshtein-távolságok aggregálásával (súlyozott összeg). Bár a cikk szerzői bedobják az egyébként szintén ismert és használatos Jaccard-távolságot is.


III. Bayes Networks for XML Duplicate Detection (XMLDup)

A cikk abból a tételből indul ki, hogy két node deduplikálandó, ha értékeik azonosak, és a gyerekeik is deduplikálandók - mily meglepő az előzmények után :o) A fenti körmentes irányított gráfos ábra mutat egy példát, hogy hogyan is néz ki ez a korábbi példára vetítve.A bottom-up módszer kellemetessége abban nyílvánul meg, hogy a teljes node-halmaz helyett az egymástól független fontos node-okat veszi csak górcső alá.

Ezek után a klasszikus Bayes háló számolását alkalmazva, node-ok közti "valszínűségpropagálás" a hagyományos módon számolódik, ahogy a fenti ábrán is látszik, mv11 gyökér-node esetén. Ha a kapott érték 0-hoz közeli, akkor teljes a különbözőség, ha 1-hez, akkor meg egyezés áll fenn. Karakterfűzér-hasonlításra e cikk szerzői is a (normalizált) Levenshtein-távolságot használták.


FUTÁSI TAPASZTALATOK:

Adatbázisok:

Hát az látható, hogy túl nagy fába nem vágódik a fejsze.;) Az adatbázisok nagyjából fele-fele arányban tartamaznak duplikátumokat és "szingliket".

IMDB: véletlenszerű válogatás a közismert filmes adatbázisból, attribútumok: title, director, author, year, movie key, rating, genre, keywords, cast member, runtime, country, language, certification

Restaurant. Fodor’s and Zagat’s restaurant guides adatbázisa, attribútumok: name,
address, city, type, phone, code, geographic coordinates

Cora: könyvtári információs adatbázis, attribútumok.: author, title, venue name, volume, date

FreeDB: Ez az audiólemezek népszerű szöveges adatbázisa, kevesebb duplikátummal, attribútumok:  artist, disc title, category, genre, year, CD extra information, track titles

IMDB+FilmDienst:. Véletlenszerű 500 film kiszedése a két adatbázisból. Integrálás után az attribútumok: year, title, aka-title, info, genre, actor


Rendszerek összehasonlítása

A szokásos precision és recall százalékos mértékek alapján

Precision: korrektül eltalált duplikátumok aránya a tesztelendő rendszer által duplikátumnak minősítettekhez képest..

Recall: korrektül eltalált duplikátumok aránya a valós duplikátumokhoz képest.


Futási idők

Nem meglepő módon tarolt az SXNM, ami a deduplikálás minősége helyett inkább a performanciára összepontosított.


DeDuplikálás minősége

A függőleges tengelyre kerül a precision, a vízszintesre meg a recall.Mivel az a jó, ha minden duplikátum megvan és tökéletes duplikátum azonosítás mellett, ezért a cél, a teljes "négyszög" elérése. Az a rossz, ha valaki minél kevésbé tudja a [1,1] négyszöget kifeszíteni. A leggyorsabb SXNM látnivalóan gyengélkedik a deduplikálási minőség terén.


Végső következtetések

(1) Az eredményes deduplikálást nagyban befolyásolja az adatbázisokban lévő hibák típusa. Erre én is tettem személyes megjegyzést/kiegészítést az SXNM elméleti taglalása kapcsán.

(2) DogmatiX nagyon jó deduplikálási minőséget adott, (többiekhez képest) nem annyira rossz futási idők mellett.

(3) A cikk szerzői szerint alapvető hátrány a cikkbeli módszereknél, a különféle paraméterek, súlyok, küszöbértékek, hasonlóságok nem túl egzakt mivolta. (Mj.: szerintem nyugodtan mondhatjuk, hogy ez általános téma egészét érintő probléma és nem specifikus és konkrét módszerek problémája)

(4) Jó lenne elmozdulni a minél egzaktabb és automatikusabb feldolgozás irányába.

+1 blogposztírói morfondírozás

Érdekesek ezek a tudományos kísérleti cuccok. Próbálnak demó méretű adatbázisokon ötleteket kipróbálni több-kevesebb sikerrel. Miközben itthon is, évek óta, nap mint nap, többszázeres ügyfélállományokon kell elviselhető teljes deduplikálást produkálni.

Amit én alapvetően hiányolok az a párhuzamosítás gondolatának teljes mellőzése. Holott skálázhatóság mellett kevésbé lenne releváns a felesleges párosítási igények radikális redukálása - de jó szópáros... :o)))

Mindazonáltal a DogmatiX IDF-es ötlete elött le a kalappal. Az mindentől függetlenül zseniális gondolat egy józan paraszti ész szerint is reális XML-es gondolatkör apropóján.