Techniky dolovania dát

Ľubomír Horňák

 

Slovenská technická univerzita, Fakulta informatiky a informačných technológií
Ústav informatiky a softvérového inžinierstva
Ilkovičova 3, 842 16 Bratislava, Slovenská republika
lubomir -dot- hornak -at- gmail -dot- com

 

Spracované podľa: Witten, Ian a Frank, Eibe: Data Mining

Abstrakt. Množstco spracovávaných a ukladaných informácií spolu s rastom ich hodnoty nás núti efektívne využívať výpočtové prostriedky. Bez využitia špeciálnych metód by sme v dátach ľahko stratili orientáciu. Na efektívne využitie dát nám slúžia techniky dolovania v dátach.

Abstract Amount of processed and stored information with growth of their value forces us to effective use of computing infrastructure. Without special methods we should easily lost orientation in data. For effective use of data serves techniques of Data Mining.

 

Obsah

 

1 Úvod

Dnešné diskové a pamäťové kapacity umožňujú uložiť oveľa väčšie množstvá údajov než v minulosti. Priamo úmerne s množstvom uložených údajov klesá ich prehľadnosť a tiež množstvo informácií, ktoré v nich môžme vyhľadať. Ide hlavne o vyhľadanie relevantných informácií, ktoré sa stáva pri enormne veľkom množstve dát takmer nemožným. Veľké množstvá dát sa dajú nájsť najmä v databázach spoločností, ktoré poskytujú svoje služby veľkému počtu zákazníkov, ako sú rôzne objednávkové služby - predaj leteniek, dovoleniek či cestovných lístkov – ďalej poisťovne, banky, nebankové subjekty poskytujúce úvery či telekomunikačné spoločnosti. Ďaľším veľkým zberateľom veľkého množstva informácií je štátna správa a zdravotníctvo, kde sa uchovávajú daňové priznania, dáta o zaplatených alebo vyplatených sociálnych dávkach, dáta o poskytnutých finančných dotáciách, chorobopisy, údaje o vydaných liekoch a pod. V neposledno rade sa obrovské množstvo dát nachádza na každom serveri v jeho logoch.

Klasický prístup k dátam je, že po ich uložení do databázového prostredia sa k nim pristupuje pomocou dopytov. Pri veľkom množstve dát je však možné, že zadaný dotaz nám nevráti relevantné výsledky. Klasické metódy dokážu odpovedať na otázky typu „Koľko ľudí si v mesiaci marec objednalo hypotekárny úver?“, ale nedokážu dopovedať na zložitejšie otázky, napríklad „Bude osoba XY schopná splatiť hypotekárny úver?“.

Na odpovedanie na tieto otázky je potrebné urobiť operácie nad dátami s použitím určitých algoritmov. Ide o algoritmy na dolovanie dát. Po ich aplikovaní bude možné odpovedať aj na otázky o schopnosti klientov splatiť úver a tak znížiť riziko straty pri poskytovaní služieb. Metódy dolovania dát teda vyhľadávajú vzory v dátach a vzťahy medzi nimi. Takto nám pomáhajú zisťovať relevantné informácie z veľkých databáz, ako i objavovať skryté informácie ukryté v dátach, ktoré niesu viditeľné na prvý pohľad.

Dolovanie dát je komplexný proces, ktorý zahŕňa fázy od prípravy dát až po ich interpretáciu. V práci budú popísané jednotlivé fázy, hlavný dôraz bude kladený na fázu klasifikácie, v ktorej sa používajú algoritmy objavujúce vzory a vzťahy v dátach.

 

2 Fázy dolovania dát

Dolovanie dát pozostáva z piatich fáz:

  • výber dát,
  • predspracovanie dát,
  • transformácia dát,
  • klasifikácia dát a
  • interpretácia dát.
  • Na začiatku procesu dolovania dát si musíme vybrať dáta z ktorých chceme získať znalosti. Z celkového množstva databázových tabuliek ktoré máme k dispozícii vyberieme tie, ktoré nám môžu poskytnúť požadované výsledky. Táto fáza závisí od dát, musíme veľmi dobre vedieť aké dáta sú obsiahnuté v jednotlivých tabuľkách a ktoré z nich sú vhodné na požadované výsledky, aby sme ich vhodne zvolili. Pri nevhodnom zvolení dát nedosiahneme žiadne výsledky, v horšom prípade dostame zlé výsledky, ktré nesprávne ovplyvnia naše rozhodovanie.

    Dáta, ktoré sme vybrali a ktoré ideme analyzovať však môžu byť nekonzistentné, nekompletné, zašumené alebo mnohorozmerné. Nekonzistentnosť vzniká, keď máme dáta z rôznych zdrojov ktoré zaznamenávali o udalosti rôzne atribúty. Nekompletnosť vzniká ak v čase zaznamenávania neboli dané informácie k dispozícii, nebol čas ich zaznamenať alebo sa považovali za nepodstatné. Zašumenosť dát znamená, že obsahujú chyby, najčastejšie vzniknuté ručným vkladaním dát do databáz. A nakoniec je tu problém dimenzionality. Dáta môžu obsahovať príliš veľké množstvo atribútov, ktoré nielenže spomaľujú výpočet, ale môžu aj prispieť k zlým výsledkom.

    Na odstránenie, alebo minimalizovanie spomenutých problémov slúži fáza predprípravy dát. V tejto fáze integrujeme dáta z rôznych zdrojov, čistíme ich a vysporadúvame sa s chýbajúcimi dátami. Integrovaním dát eliminujeme chyby, ktoré vznikli spojením dát z rôznych zdrojov, napríklad zlúčením databáz po fúzii dvoch spoločností, alebo chyby vzniknuté rôznymi štýlmi ukladania záznamov, rôznymi primárnimi kľúčmi či rôznimi konvenciami zápisu. V procese integrovania dát zjednocujeme zápis záznamov (napríklad odstránime používanie 2 a II v tom isom atribúte), identifikujeme rovnaké entity (napríklad pomocou ich identifikátorov, alebo metadát) a odstraňujeme redundantné dáta, teda dáta, ktoré sa dajú vypočítať z iných atribútov a tým pádom sú nadbytočné.

    Ďaľším krokom v predpríprave dát je nahradenie chýbajúcich dát. Hlavným problémom pri nahrádzaní chýbajúcich dát je, že nevieme rozlíšiť, či sa pri zbieraní daný atribút nepodario získať, alebo či jeho získanie nebolo irelevantné. Napríklad máme kolekciu dát, kde zbierame nasledovné údaje o osobách: meno, vek, pohlavie a či je daná osoba tehotná. Pri zápise dát sa môže stať, že pri veľkej skupine osôb bude atribút o tehotnosti nevyplnený, lebo bol nerelevantný (pri mužoch) alebo neaplikovateľný (napríklad päťročné dievča). S chýbajúcimi hodnotami sa môžme vysporiadať viacerými spôsobmi. Môžme daný záznam ignorovať, ale pri veľkom množstve takýchto záznamov nám vznikne problém. Ak je málo chýbajúcich záznamov, môžme ich vyplniť manuálne. Ďalej je možné použiť konštantnú hodnotu (napríklad „neznáme“), aritmetický priemer hodnôt alebo použiť aritmetický priemer hodnôt patriacich do tej istej triedy. Na použitie poslednej možnosti musíme mať dáta klasifikované, teda musíme poznať ich priradenie do tried.

    V dátach, ktoré máme k dispozícii sa veľmi často nachádzajú chyby. Dáta, ktoré používame na dolovanie často neboli zbierané na tento účel, je v nich plno chýb vziknutých pri zbere dát – napríklad chyby merania, duplikácia dát či úmyselné chyby. Úmyselné chyby vznikajú napríklad pri zadávaní osobných údajov, keď zadávateľ úmyselne zadá nesprávne hodnoty. Duplikované dáta musia byť odstránené, pretože môžu negatívne ovplyvniť výsledky dolovania. Chyby merania vieme zistiť pomocou štatistických metód, kde ľahko zbadáme „outliery“, teda hodnoty výrazne odchýlené od ostatných, alebo zhlukovaním.

    Problému dimenzionality sa zbavíme vhodným výberom atribútov. Pri ich vhodnom výbere nielenže zvýšime presnosť a rýchlosť algoritmu, ale dostaneme sa aj k kompaktnejšej a zroyumiteľnejšej reprezentácii. Atribúty môžme vybrať použitím iného algoritmu na dolovanie v dátach (rozhodovací strom), náhodným výberom inštancií alebo štatistickým výberom. Takisto odstraňujeme korelované atribúty. Pri náhodnom výbere inštancií máme k dispozícii dva prístupy - „near hit“ a „near miss“. Ak je pri prístupe near hit rôzna hodnota atribútu, tak je atribút nerelevantný. A naopak, pri prístupe near miss rôzna hodnota atribútu znamená, že atribút je relevantný. Štatistický výber môže byť buď dopredný, alebo ho môžeme vykonať spätnou elimináciou. Pri doprednom výbere pridávame najlepšie atribúty, pri spätnej eliminácii zase odoberáme najhoršie atribúty.Pomáhajú nám pri tom štatistické testy, ako sú t-test alebo Wilcoxon rank sum test.

    Po ukončení fázy predspracovania môžme použiť predspracované dáta na transformáciu. V rámci transformácie dáta vyhladzujeme (odstraňujeme zašuemneé dáta, napríklad zhlukovaním, regresiou), diskretizujeme numerické atribúty, agregujeme (napríklad denné dáta do týždenných), vzorkujeme, normalizujeme (napríklad do intervalu <-1, 1>), transformujeme text na atribútové vektory, zovšeobecňujeme (nízkoúrovňové dáta sa nahrádzajú vyššieúrovňovými konceptami, napríklad ulica –> mesto –> štát). Nie vždy používame všetky spomenuté operácie, volíme ich v závislosti na dátach.

    Po fáze transformácie nasledujú fázy klasifikácie a interpretácie dát. V fáze klasifikácie aplikujeme algoritmy, ktoré nám v fáze interpretácie dát dájú odpovede na otázky kôli ktorým sme aplikovali dolovanie v dátach. Fáza klasifikácie bude bližšie popísaná v nasledujúcej kapitole.

     

    3 Klasifikácia dát

    Pri klasifikácii dát sa na predpripravené dáta aplikuje niektorý z algoritmov, ktoré budú popísané v tejto kapitole. Algoritmus volíme podľa dát, ich množstva, úloh ktoré potrebujeme vyriešiť a pod. V klasifikácii sa dáta zatrieďujú do preddefinovaných skupín (tried). Prebieha tu „učenie s učiteľom“, kde sa algoritmus učí charakteristiku tried na základe dát pre ktoré pozná príslušnosť k skupinám, teda na základe trénovacej množiny. Klasifikáciu môžme definovať nasledovne [3]: Pre danú množinu dát D={d1, ..., dn} a množinu tried C={C1, ..., Cm}, klasifikačný probém je definovať zobrazenie f:D -> C, kde pre každé di je definovaná práve jedna trieda. Trieda Cj obsahuje práve tie prvky, ktoré sa pomocou funkcie f zobrazia do tejto triedy, t.j. Cj= {di | f(di) = Cj, pre všetky di patriace do D}.

    3.1 Rozhodovacie tabuľky

    Najjednoduchším spôsobom, ako zobrazovať výsledok klasifikácie, resp. strojového učenia sa je urobiť ho takým istým ako je vstup – rozhodovacou tabuľkou. Napríklad nasledujúca tabuľka zobrazuje údaje o počasí. Na zistenie, či pôjdeme alebo nepôjdeme hrať sa iba pozrieme do tabuľky na príslušné podmienky. Vytvoriť rozhodovaciu tabuľku nieje najjednoduchšia úloha. Je potrebné zvoliť niektoré z atribútov, ktoré máme k dispozícii. Napríklad, ak teplota (temperature) je pre rozhodovanie irelevantná, vyradíme ju z rozhodovacej tabuľky. Takto získame menšiu tabuľku, ktorá bude bez chýbajúceho atribútu lepšie vystihovať naše potreby pri rozhodovaní. Problémom samozrejme je vhodne určiť atribúty, ktoré nebudú ovplyvňovať výsledok a možno ich bez problému z tabuľky vyradiť.

    Príklad rozhodovacej tabuľky

    Obr. 1 - Príklad rozhodovacej tabuľky[1]

    3.2 Rozhodovacie stromy

    Rozhodovacie stromy sú najpopulárnejšou formou reprezentácie klasifikáčných algoritmov najmä pre svoju ľahko pochopiteľnú reprezentáciu získaných znalostí. Rozhodovací strom je strom s nasledujúcimi vlastnosťami:

  • Medziľahlý uzol reprezentuje vybraný atribút, resp.skupinu atribútov,
  • Listový uzol reprezentuje niektorú z tried a
  • Hrana reprezentuje test na atribút (skupinu atribútov) z nadradeného uzla
  • Z testov, ktoré sa vzťahujú na daný medziľahlý uzol, a teda na z neho vychádzajúce hrany, môže byť úspešný vždy práve jeden. Rozhodovací strom sa konštruuje na základe objektov trénovacej množiny. Nové objekty, u ktorých nepoznáme zaradenie do triedy, potom prechádzajú týmto stromom od koreňového uzla cez jednotlivé hrany podľa výsledkov jendnotlivých testov. Nakoniec skončia v jedom z listových uzlov, ktorý zaradí objekt do príslušnej triedy.

    Existuje viacero algoritmov na konštrukciu stromov, najznámejšie sú C4.5 a jeho predchodca ID3. Ich popis je nad rámec tejto práce. Záujemca ho môže nájsť v použitej literatúre. Jednotlivé algoritmy pre konštrukciu rozhodovacích stromov sa líšia stratégiou rozdeľovania aktuálnej množiny objektov, spôsobom orezávania stromov a mnohými ďalšími vlastnosťami. Orezávanie stromov má za cieľ dosiahnuť stručnejšiu reprezentáciu výsledného stromu pri zachovaní primeranej presnosti klasifikácie. Dôvodom je jav označovaný ako preučenie,kedy skonštruovaný rozhodovací strom príliš podrobne kopíruje charakteristiky príkladov z trénovacej množiny, čo ale môže znížiť jeho presnosť pre nové príklady. Okrem toho sú menšie stromy prehľadnejšie a poskytujú tak ľahšie pochopiteľné znalosti.

    Príklad rozhodovacieho stromu

    Obr. 2 - Príklad rozhodovacieho stromu[3]

    3.3 Zhlukovanie

    V prípade, ak niesu vopred dané triedy pre objekty, systém sa musí sám naučiť zistiť, aké triedy obsahuje. Jeden zo spôsobov, ako to urobiť je Zhlukovanie (Clustrovanie). Jednoduchý príklad zhlukovania databázy môžme vidieť na nasledujúcom obrázku. Prvým krokom je objaviť zhluky navzájom súvisiacich objektov a následne je potrebné objaviť popis, ktorý opisuje každý z týchto zhlukov, napríklad D1, D2, D3.

    Rozdeľovanie databázy do zhlukov

    Obr. 3 - Rozdeľovanie databázy do zhlukov[2]

    Zhlukovania a segmentácia v princípe rozdeľujú databázu na menšie časti, objekty v každej časti sú si podobné na základe nejakých kritérií alebo metriky. Zhlukovanie na základe podobnosti je prístup, ktorý sa objavuje v mnohých disciplínach. Ak je možné merať podobnosť, máme k dispozícii množstvo techník na vytváranie zhlukov. Príslušnosť do zhlukov môže byť založená na miere podobnosti medzi objektami. Z týejto miery sa vytvoria pravidlá, na základe ktorých sa definuje príslušnosť do zhlukov. Iným prístupom je vybudovať sadu funkcií ktoré merajú nejakú vlastnosť zhluku ako funkciu určitých parametrov zo zhluku. Druhému prístupu sa darí dosahovať to čo nazýame „optimálne rozdelenie“, t.j. Objekty sú čo najideálnejšie priradené do zhlukov. Väčšina dataminigových aplikácií používa prvý spomenutý prístup na rozdelenie klientov a zákazníkov do skupín. Druhý prístup je používaný na analýzu dát, napríklad keď priraďujeme poisťovacie tarify zákazníci môžu byť rozdelený do zhlukov na základe množstva parametrov a dosiahneme „optimálne rozdelenie“.

    3.4 Neurónové siete

    Neurónové siete predstavujú prístup k výpočtom ktorý zahrňuje vývoj matematických štruktúr s schopnosťou učiť sa. Neurónové siete majú značnú schopnosť odvodiť výsledky z komplikovaných slebo nepresných dát a môžu byť použité na nájdenie vzorov a odhalenie trendov ktoré sú príliš komplexné na to, aby ich mohol nájsť človek, alebo iná výpočtová technika. Naučená neurónová sieť môže byť považovaná za „experta“ v kategórií informácií ktoré dostala na analýzu. Takýto „expert“ môže byť potom použitý na poskytnutie prehľadu v nových oblastiach záujmu a tiež môže poskytnúť odpovede na otázky „čo ak“.

    Neurónové siete majú široké využitie pri riešení problémov reálneho sveta a boli už úspešne implementované v mnohých odvetviach priemyslu. Keďže neurónové siete sú najlepšie na identifikovanie vzorov a trendov v dátach, sú veľmi vhodné na predpovedanie, napríklad odhady úspešnosti predaja, direct marketingu, validáciu dát, manažment rizík a pod.

    Neurónová sieť sa skladá z neurónov, ktoré sú usporiadané do vstupnej vrstvy, skrytých vrstiev a výstupnej vrstvy. Každý uzol (neurón) vstupnej vrstvy predstavuje jednu vstupnú premennú. Každý zo vstupných uzlov je napojený na každý uzol v skrytej vrstve. Uzly v skrytej vrstve môžu byť napojené buď na uzly v nasledujúcej skrytej vrstve, alebo na uzly vo výstupnej vrstve. Výstupná vrstva sa skladá z jedného alebo viacerých uzlov predstavujúcich výstupné premenné.

    Neurón

    Obr. 4 - Neurón[3]

    Každý z uzlov za vstupnou vrstvou má sadu vstupov. Tieto vstupy sú násobené váhou spojenia Wxy, ďalej sú sčítané dokopy a následne je na ich výslednú hodnotu aplikovaná aktivačná funkcia. Výsledná hodnota je výstupnou hodnotou daného uzla a je poslaná na vstup na uzly v ďalšej vrstve. Váha spojenia Wxy je parameter, ktorého hodnota je na začiatku neznáma je stanovený trénovaním. Vlastnosti a možnosti neurónovej siete sú určené jej topológiou, teda počtom jej uzlov, skrytých vrstiev a tým ako sú prepojené.

    Schéma neurónovej siete

    Obr. 5 - Schéma neurónovej siete[3]

     

    4 Záver

    Ako vidno, techniky dolovania dát nachádzajú stále širšie a širšie uplatnenie pri riešení denných úloh v priemysle. S rastom zbieraných, uložených a tým aj historických dát bude stále dôležitejšie, aby sme z nich dokázali efektívne a v reálnom čase dolovať údaje, ktoré potrebujeme. Na to je potrebný rozvoj strojového učenia sa, aby počítač nielen vykonával úlohy,ale aj „vedel“, čo vykonáva a dokázal sa učiť. Jednou z metód ktoré nám pomôzžu, a vlastne dnes už aj pomáhajú je dolovania v dátach - data mining. Tento článok načrtol základné princípy dolovania v dátach, kôli jeho rozsahu a určeniu doň nebolo možné zahrnúť všetky podrobnosti. V prípade záujmu si čitateľ môže viac naštudovať v dolespomenutej literatúre, prípadne zadať do googlu „data mining“ a nájsť špecifické informácie, ktoré potrebuje v rastúcom množstve odkazov na túto prudko sa rozvíjajúcu informatickú disciplínu.

     

    Použitá literatúra

    [1]Witten, Ian a Frank, Eibe: Data Mining. 2 vyd. San Francisco: Morgan Kaufman Publishers, 2005. ISBN 0-12-088407-0

    [2]Dilly, Ruth. Data Mining - Student Notes, 1995. http://www.pcc.qub.ac.uk/tec/courses/datamining/stu_notes/dm_book_1.html (01.11.2007)

    [3]Kosková, Gabriela. Získavanie znalostí - Prednášky, 2007. http://www2.fiit.stuba.sk/ZZ/prednasky.html (01.11.2007)

     


    Znalostné systémy
    Zimný semester 2007/2008