Objavovanie znalostí a jeho potenciál
pre reálne aplikácie
František Babič, Ján Paralič
Katedra kybernetiky a umelej inteligencie, Fakulta elektrotechniky a informatiky,
Technická univerzita v Košiciach, Letná 9, 042 00 Košice, Slovensko
[email protected], [email protected]
Abstrakt: Objavovanie alebo dolovanie znalostí reprezentuje proces získavania nových,
potenciálne užitočných znalostí z rôznych typov historických dát. Tento prístup postupne
nachádza čoraz väčšie uplatnenie v rôznych profesionálnych alebo akademických
oblastiach, v rámci ktorých sú zhromažďované veľké objemy dát. Tieto datasety v sebe
častokrát ukrývajú dôležité informácie, ktoré môžu priniesť organizácii konkurenčnú
výhodu, vyšší zisk, stabilizovanie zákazníckej základne alebo nárast počtu zákazníkov,
šetrenie v oblasti opravy alebo výroby produktov, atď. V tomto článku prezentujeme
riešenie vybraných reálnych aplikácií pomocou tohto prístupu ako názornú ukážku
širokého aplikačného potenciálu metód dolovania znalostí. Prvé dva príklady sú výsledky
našich študentov získané pri práci na zadaniach úloh zo súťaží Data Mining Cup,
konkrétne predikciu predajnosti knižných titulov a predikciu úspešnosti internetových
aukcií. Tretí príklad prezentuje výsledok spolupráce s firmou MicroStep MIS v rámci
projektu APVV (Data Mining Meteo), zameraného okrem iného na predikciu výskytu hmly
na vybraných letiskách. Všetky tri príklady svojimi výsledkami dokumentujú vhodnosť
a potenciál použitých prístupov, čo je dobrou motiváciou a inšpiráciou do budúcnosti.
Abstract: Knowledge discovery represents data mining process which should produce
new and potentially usefull knowledge from various types of historical data. This
approach has been gradually adopted in different professional or academic domains that
posees large datasets. The datasets contain important information that can be used for
achievement of competitive advantage, higher profit, stabilization or increase of
customers’ group, savings in repair or production processes, etc. In this paper we present
the data mining process on 3 real cases. First two cases present results of our students
working within our course on data from Data Mining Cup, in particular forecast of
purchase quantities for selected book titles and prediction of success of internet auctions.
The last one presents some of our results achieved within a research project with
MicroStep MIS company focussed also on fog forecasting at the selected airports. The
obtained results in these three cases show suitability and potential of applied methods
that provide good motivation and inspiration for future work.
Klíčová slova: objavovanie znalostí, meterologické dáta, predajnosť, internetové aukcie
Keywords: Knowledge discovery, meteorological data, salability, internet auctions
1. Objavovanie znalostí v databázach
Objavovanie znalostí v databázach (v angličtine Knowledge Discovery in Databases KDD) alebo Data mining - DM) predstavuje zaujímavú oblasť so širokým aplikačným
potenciálom v rôznych doménach. Metódy objavovania znalostí je možné použiť na
riešenie úloh v oblastiach ako (obr.1):
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
125
František Babič, Ján Paralič
Marketing - analýza dát o zákazníkoch; identifikácia určitých skupín zákazníkov,
čo pomáha pri odhadoch budúceho správania zákazníka, pri plánovaní
reklamných kampaní, výpredajov, atď.
Individuálna reklama a elektronický obchod – identifikácia profilu jednotlivých
používateľov na základe ním zadaných informácií a/alebo analýz jeho
nákupného správania; na základe tohoto profilu je možné ponúkať
personalizovanú reklamu.
Odhaľovanie podvodov – na základe dlhodobého sledovania správania
zákazníka sa vytvorí profil stabilného správania a významné zmeny generujú
alarm s potenciálne negatívnou hodnotou. Tento prístup je možné použiť
napríklad pre telekomunikačné alebo bankové dáta.
Takisto predikcia vývoja kurzov akcií alebo mien, predikcia spotreby elektrickej
energie alebo vody, analýza príčin rôznych typov porúch, predikcia predajnosti
na základe dát popisujúcich trh a jeho produkty, analýza klientov bánk s cieľom
efektívneho ponúkania úverov, klasifikácia chorôb pacientov na základe
identifikovaných príznakov, a mnohé ďalšie.
Obr.1 Najčastejšie oblasti využívania KDD podľa prieskumu Rexer Analytics
(Analytics data mining survey 2009-2010)
Objavovanie znalostí v databázach (OZ) predstavuje proces semi-automatickej extrakcie
znalostí z databáz [Paralič03]. Cieľom tohto procesu je objaviť skutočne cenné znalosti,
ktoré môžu priniesť reálny prínos alebo zisk. Z tohoto dôvodu je nevyhnutná asistencia
človeka (preto semi-automatický), ktorý rozhoduje o výbere vhodných operácií, metód
a ich parametrov, ale najmä vyhodnocuje získané vzory a vyberá z nich nové znalosti. To
znamená, že používateľ musí mať primerané znalosti z danej domény, aby dokázal celý
proces realizovať efektívne a s dobrými výsledkami.
V komerčnej sfére sa častejšie používa v tejto súvislosti pojem podniková inteligencia, (BI
z anglického Business Intelligence), ktorým sa všeobecne označujú softvérové nástroje
na zber a analýzu dát. Podniková inteligencia umožňuje ľuďom na všetkých úrovniach
organizácie prístup k dátam, interakciu s dátami a analýzu dát s cieľom riadiť podnikanie,
zlepšiť výkonnosť, objaviť nové príležitosti a fungovať efektívne [Howson08].
126
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
Objavovanie znalostí a jeho potenciál pre reálne aplikácie
Proces objavovania znalostí je iteratívny, interaktívny a multidisciplinárny. V praxi to
znamená, že ak používateľ aplikácie v niektorom kroku zistí, že napr. iná reprezentácia
dát alebo iné nastavenie parametrov metódy by mohlo zmeniť resp. vylepšiť nájdené
znalosti resp. vzory, jednoducho sa vráti k relevantnému kroku, urobí zmenu a postupuje
dopredu cez všetky nasledujúce kroky v danom poradí.
1.1 CRISP-DM
CRISP-DM [Shearer00] reprezentuje všeobecnú metodológiu pre proces objavovania
znalostí, ktorá umožňuje jeho rýchlejšie a efektívnejšie vykonávanie, najmä s menšími
nákladmi. Proces objavovania znalostí podľa CRISP-DM pozostáva zo šiestich fáz, medzi
ktorými existujú úzke vzťahy a obojstranné prechody (pozri obr.2). Verzia CRISP-DM 1.0
bola vydaná v roku 1999, v súčasnosti sa očakáva vydanie verzie 2.0. Táto metodológia
predstavuje ucelený postup ako implementovať riešenie dolovania znalostí pomocou
vhodných softvérových prostriedkov. Samozrejme v prípade potreby môže byť
adaptované na konkrétne podmienky a požiadavky zákazníka.
1.1.1 Pochopenie cieľa
Prvou fázou je pochopenie cieľa, ktoré zahŕňa základné kroky ako stanovenie
obchodných cieľov, ktoré môžu byť objektívne merateľné (kritériá obchodného úspechu,
na základe ktorých môžeme vyhodnotiť úspešnosť a prínos nášho riešenia) alebo
subjektívne vnímateľné. Výstupom sú akékoľvek informácie, ktoré je možné ďalej použiť
v procese OZ. Druhým krokom je zhodnotenie existujúcich podmienok, ktoré obsahuje
ich detailný popis; zoznam všetkých dostupných zdrojov akéhokoľvek druhu; zoznam
možných ohraničení a obmedzení pre projekt; možné riziká; terminológiu, obchodnú aj
z oblasti OZ; analýzu nákladov a prínosov projektu. Zoznam vstupov do projektu musí
zahŕňať časové, finančné, hmotné prostriedky; potenciálne použiteľný softvér, ľudské
zdroje (obchodní experti, dátoví špecialisti, technici a špecialisti na OZ), dátové zdroje
(nemenné extrakty, prístup k dátovým skladom), atď.
Obr.2: Životný cyklus procesu objavovania znalostí podľa CRISP-DM
Zhromaždené informácie sa použijú na definovanie cieľov dolovania prostredníctvom
transformácie obchodných cieľov. To znamená určenie cieľov dolovania v dátach
a kritériá úspechu v terminológií OZ, napr. miera presnosti modelu. Táto fáza končí
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
127
František Babič, Ján Paralič
vytvorením plánu projektu (špecifikácie), ktorý povedie riešenie k cieľovému stavu, čiže
splneniu obchodných cieľov. V tomto pláne musia byť presne definované kroky, ktoré
budú uskutočnené, ich časová postupnosť a náročnosť, vstupy a výstupy, závislosti. Plán
je dynamický, čo znamená, že po každej fáze je kontrolovaný a aktualizovaný.
1.1.2 Pochopenie dát
Úlohou druhej fázy je oboznámiť sa s príslušnými dátami (ich zdrojmi), ktoré máme pre
riešenie úlohy k dispozícií. Začíname počiatočným zberom dát, ktorý pokračuje popisom
dát, verifikáciou ich kvality a postupným prieskumom dát. Tieto kroky sú zamerané na
určenie kľúčových atribútov a závislostí medzi nimi (korelačné koeficienty alebo
kontingenčná tabuľka), určenie distribúcie rôznych hodnôt atribútov pomocou
histogramov, výpočet základných štatistických ukazovateľov jako priemer, modus,
medián, šikmosť, špicatosť, atď.
1.1.3 Príprava dát (Predspracovanie)
Fáza predspracovania predstavuje časovo najnáročnejšiu časť (60-70%) celého procesu
OZ, ktorej cieľom je príprava dát vzhľadom na metódy a algoritmy, ktoré budú v ďalšom
kroku na tieto dáta aplikované. Všetky vykonané operácie nad dátami je nutné
dokumentovať pre účely dodatočných zmien a modifikácii na základe priebežných
výsledkov. V tejto fáze sú využívané operácie ako integrácia dát z rôznych vstupných
zdrojov; výber dát na základe stanovených cieľov, požadovanej kvality a technologických
obmedzení; čistenie dát zamerané na chýbajúce, výrazne odchýlené alebo prázdne
hodnoty; vytváranie nových atribútov derivovaním, spájaním alebo elimináciou
pôvodných; odstránenie redundatných alebo zlé naformátovaných dát.
1.1.4 Modelovanie
Modelovanie pokrýva aplikáciu vhodných metód objavovania znalostí (napr.
rozhodovacie stromy, lineárna regresia, zhlukovanie, asociačné pravidlá, neurónové
siete) na predspracované dáta. Tento postup zahŕňa štyri základné kroky: výber techniky
modelovania; návrh metriky, ktorá bude použitá na vyhodnotenie vytvorených modelov,
napr. počet chybne klasifikovaných príkladov; rozdelenie vstupných dát na trénovaciu
a testovaciu množinu; generovanie modelov na základe nastavených parametrov;
ohodnotenie vytvorených modelov na základe stanovenej metriky. Ak sme nedosiahli
požadovanú kvalitu a výsledok, dochádza k prenastaveniu parametrov a novej iterácii, po
prípade návrat k predspracovaniu dát.
1.1.5 Vyhodnotenie
Vo fáze vyhodnotenia dochádza k evaluácii dosiahnutých výsledkov (modelov) ale
transformáciou na pôvodné obchodné ciele. To znamená, že vytvorený model sa aplikuje
do praxe, a sleduje sa jeho kvalita, úspešnosť alebo prínosy. Pokiaľ je tento model
označený ako vhodný, dochádza ku kompletnej revízii celej úlohy a postupu jej riešenia.
Predmetom skúmania sú jednotlivé operácie, ich príčiny, nastavenia a dôsledky.
Výsledkom je finálne vyhodnotenie s definitívou, či projekt dolovania splnil pôvodne
stanovené ciele, či je nutné vykonať ďalšie iterácie alebo ide o tzv. finálne rozhodnutie.
1.1.6 Nasadenie
Základom nasadenia výsledkov do praxe je plán, ktorý určuje stratégiu monitorovania
a údržby. Okrem toho je vytvorená záverečná správa, ktorá obsahuje súhrn alebo
128
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
Objavovanie znalostí a jeho potenciál pre reálne aplikácie
prezentáciu finálnych výsledkov a posúdenie celého projektu. Ak bol definovaný
všeobecný postup na tvorbu daného modelu, musí byť zdokumentovaný pre ďalšie
použitie. Dôkladný plán údržby je nutný, ak sa výsledky stávajú súčasťou každodennej
aktivity firmy, a je tu predpoklad zlého použitia v praxi. Záverečným dokumentom celého
procesu je revízna správa, ktorá slúži pre vnútornú potrebu firmy implementujúcej
získané modely. Pracovníci, ktorí sa podieľali na celom procese, popíšu svoje skúsenosti
a použité techniky, upozornia na problematické miesta.
2. Príklady využitia OZ v praxi
V tejto kapitole uvedieme tri príklady možného využitia metód OZ pre riešenie reálnej
aplikácie. Prvé dva prezentujú výsledky našich študentov získané pri práci na zadaniach
1
úloh zo súťaží Data Mining Cup , konkrétne predikciu predajnosti knižných titulov a
predikciu úspešnosti internetových aukcií. Cieľom tejto súťaže je podporiť mladých
výskumníkov a študentov v oblasti objavovania znalostí prostredníctvom práce na
reálnych dátach z rôznych domén. Každoročným favoritom sú tímy študentov
z nemeckých univerzít ako Karlsruhe alebo Dortmund, ktoré majú v tejto oblasti dlhú
a úspešnú históriu. Každoročné zadania súťaže predstavujú reálne problémy, pre
riešenie ktorých sú k dispozícii historické dáta zhromaždené v spolupráci s príslušnou
firmou.
2
Tretí príklad prezentuje výsledok spolupráce s firmou MicroStep MIS v rámci projektu
APVV (Data Mining Meteo alebo Predpovedné a detekčné metódy význačných a
nebezpečných javov založené na dolovaní meteorologických dát), zameraného okrem
iného na predikciu výskytu hmly na vybraných letiskách [Bednár11].
2.1 Predikcia predajnosti knižných titulov
Knižný trh v Nemecku je jedným z najväčších trhov v súčasnosti, ročne sa v Nemecku
vydá cez 96 000 titulov. Pre predajcov je výzva kúpiť správny titul na sklad a ponúkať ho
vo vhodnom množstve a čase, aby maximalizovali svoj zisk. V spolupráci s najväčším
nemeckým predajcom kníh sa podarilo zozbierať a uložiť veľké množstvo historických dát
popisujúcich predajnosť vybraných knižných titulov v jednotlivých lokalitách. Úlohou je na
základe týchto dát predpovedať predajnosť ôsmych nových titulov. Tento obchodný cieľ
je možné pretransformovať do oblasti OZ ako predikcia hodnoty spojitého (numerického)
atribútu. To znamená, že máme k dispozícií predajné štatistiky rôznych knižných titulov
v rôznych monitorovaných lokalitách a na ich základe máme predpovedať predajnosť
ôsmich nových titulov. Táto predpoveď bude možná na základe identifikácie skrytých
vzťahov v dátach, napr. medzi podobnými žánrami, autorskými kolektívmi, a pod.
K dispozícii boli dáta uložené vo formáte txt. Trénovacia množina obsahovala 2418
záznamov reprezentujúce jednotlivé lokality (kníhkupectvá). K dispozícií boli záznamy
predajnosti o 1856 knižných tituloch. Každý knižný titul bol definovaný čiselnou
kombináciou, ktorá popisovala jeho zameranie, žáner alebo vonkajšie charakteristiky ako
typ väzby, atď. Na základe týchto identifikátorov bolo možné vytvoriť hierarchiu
konceptov pre účely generalizácie. Táto hierarchia popisuje v podstate kategorizáciu
knižných titulov od konkrétnej knižky až po všeobecnú kategóriu typu beletria. Pohyb
1
2
http://www.data-mining-cup.de/en/
http://www.microstep-mis.com/index.php?lang=sk
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
129
František Babič, Ján Paralič
v hierarchii smerom nahor alebo nadol nám umožní pracovať s rôznymi úrovňami
všeobecnosti na základe očakávaných výsledkov.
Výber a čistenie dát neboli nutné, keďže do fázy modelovania boli posunuté všetky
pôvodné záznamy, ktoré navyše neobsahovali žiadne prázdne hodnoty, čiže pôvodný
dataset bol kompletný. Nulové hodnoty boli zachované, pretože nesú dôležitú informáciu
o knižničných tituloch s nulovou predajnosťou. V ďalšom kroku sme postupne redukovali
počet stĺpcov (atribútov) na základe navrhnutej hierarchie konceptov s cieľom vytvoriť
charakteristické vzory pre podobné skupiny kníh. Táto generalizácia priniesla zníženie
počtu knižných titulov na 95 s ukončovaciou podmienkou priemernej hodnoty predajnosti
v novom atribúte v intervale <0,2000>.
Obr.3: Príklad časti implementácie algoritmu lineárnej regresie v prostredí SPSS
Clementine
Ako vhodnú metódu sme vybrali algoritmus lineárnej regresie, prostredníctvom ktorého
bol vytvorený predikčný model. Keďže máme 8 cieľových atribútov, rozhodli sme sa
vytvoriť 8 samostatných modelov v dvoch bežne používaných softvérových prostrediach
3
4
v oblasti dolovania znalostí: IBM SPSS (obr.3) a SAS Miner (obr.4).
Obr.4: Príklad časti implementácie algoritmu lineárnej regresie v prostredí SAS Miner
Kvalita dosiahnutých výsledkov bola verifikovaná na základe chybovej funkcie, ktorá bola
daná sumou (absolútnou hodnotou) rozdielov medzi predpovedanou a skutočnou
hodnotou vo všetkých lokalitách. Cieľom bolo samozrejme dosiahnúť čo najmenšiu
hodnotu tejto chybovej funkcie. V príslušnom roku súťaže víťaz dosiahol celkovú chybu
17 260, náš výsledok v SPSS predstavoval hodnotu 30 295 a v SAS 31 626, čo by
zodpovedalo umiestneniu okolo 30. miesta. Celkové predajnosti jednotlivých knižných
titulov sú v státisícoch, takže chyby niekoľko tisíc kusov sú relatívne presnými
3
4
http://www.spss.com/
http://www.sas.com/technologies/analytics/datamining/miner/
130
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
Objavovanie znalostí a jeho potenciál pre reálne aplikácie
predpoveďami. Každopádne existuje priestor na dosiahnutie lepších výsledkov, najmä čo
sa týka aplikácie iných vhodných predikčných algoritmov, alebo zmenami v hierarchii
konceptov, ktorá by lepšie odrážala štruktúru knižného trhu.
Tento príklad riešenia poukazuje na možnosť nasadenia vytvorených modelov do praxe,
čo by predajcom prinieslo znalosti o predpokladanej predajnosti každej novej knihy, ktorá
je k dispozícií na trhu. Tieto modely by bolo samozrejme nutné kontinuálne vyvíjať a
upravovať vzhľadom na meniacu sa situáciu na trhu, aby kopírovali aktuálne podmienky.
Napr. vo forme vytvorenia dátového skladu, ktorý by bol neustále aktualizovaný, aby
odrážal aktuálnu situáciu na trhu. Takýto dátový sklad by mohol plniť základné
reportovacie funkcie, ako napr. v prípade potreby rýchle a efektívne vytvorený prehľad
predajnosti za určitý kvartál, atď. Nadstavbou by boli práve vhodné metódy OZ ako
predikcia predajnosti, klasifikácia alebo zhlukovanie knižných titulov do rôznych a pod.
2.2 Predikcia úspešnosti internetovej aukcie
5
6
Aukčné systémy jako Ebay či Amazon predstavujú čoraz častejší prostriedok nákupu
rôznych typov produktov. Svoje služby poskytujú súkromným aj právnickým osobám, a
ich spoločnou črtou je dosiahnuť čo najvyššiu predajnú cenu. Na dosiahnutie tohto cieľa
existuje niekoľko postupov ako napr. dlhšie/kratšie trvanie aukcie, rôzne štartovacie ceny,
prerušenie aukcií počas víkendov či pracovných dní, a mnohé iné varianty, ktoré majú
zaručiť úspech. Jednou z možností je vytvoriť klasifikačný model na základe
zhromaždených historických dát (o týchto prípadoch vieme povedať, či boli úspešné
alebo nie), ktorý bude kategorizovať nové prípady aukcií do dvoch cieľových tried: zisk
vyšší ako priemer, alebo zisk nižší ako priemer.
V tomto prípade boli k dispozícií historické dáta popisujúce internetové aukcie predajcu
elektroniky prostredníctvom portálu Ebay.com. Trénovaciu vzorku tvorilo 8 000 online
aukcií z kategórie "Audio&Hi-Fi:MP3-Player:Apple iPod", kde každá aukcia bola popísaná
atribútmi ako začiatok, koniec, titulok, štartovacia cena, okamžitá cena, atď. Tieto atribúty
vytvárali textový popis aukcie poskytujúci dostatok informácií, ale takisto vyžadoval
nutnosť dôsledného predspracovania. Výsledná dátová množina umožnila vytvoriť
klasifikačný model, ktorý s určitou presnosťou bude vediet prideliť správnu cieľovú triedu
novým aukciám v testovacej množine.
Na popis dát boli použité nástroje v prostredí IBM SPSS ako Data audit, Quality alebo
Statistics. Zamerali sme sa na úplnosť dát, čiže prázdne, nezadané alebo prípadne
chybne zadané hodnoty atribútov. Preskúmanie prinieslo pozitívne prekvapenie, keďže
všetky atribúty okrem „gms“ (nebol nakoniec zahrnutý do analýzy) vykazovali 100%
kompletnosť a 8 000 správne zadaných údajov. Cieľový atribút „gms_greater_avg“
obsahoval zhruba rovnomerne zastúpené hodnoty 1 a 0 (47,51% , resp. 52,49 %).
V rámci predspracovania sme použili viacero prístupov na dosiahnutie kvalitnej vzorky
dát. Na úvod sme odfiltrovali všetky atribúty, ktoré mali nízku informačnú hodnotu pre
cieľovú kategóriu. Takisto sme diskretizovali numerický atribút „štartovacia cena“ na 10
rovnako veľkých intervalov s cieľom jeho generalizácie. Na základe podrobnej analýzy
popisu a štruktúry pôvodných atribútov sme sa rozhodli vytvoriť nové atribúty, ktoré by
lepšie charakterizovali dátovú množinu a vyhovovali metódam objavovania znalostí.
V podstate išlo o extrakciu kľúčových slov z textového popisu každej aukcie v atribúte
5
6
http://www.ebay.com/
http://www.amazon.com/
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
131
František Babič, Ján Paralič
„listing_title“. Vytvorili sme nový atribút kapacita_GB, ktorý sme naplnili veľkosťou pamäti
jednotlivých iPodov v GB. Tento atribút nám umožnil generovať klasifikačný model pre
každú konkrétnu kapacitu modelu. To znamená, že v prípade klasifikácie novej aukcie je
prvým rozdielovým atribútom práve táto kapacita, ktorá rozdelí množinu aukcií na
príslušné časti.
Pre názornosť uvádzame len vybrané príklady nových atribútov (vo väčšine prípadov ide
o binárne atribúty):
Neu_neuwertig: hodnota 1, ak „listing_title“ obsahuje slová ako NEU (nový)
alebo NEUWERTIG (nový tovar). Ak tieto slová neobsahuje, tak nadobúda
hodnotu 0. Je jednou z hlavných súčastí popisu tovaru. Nehovorí o tom či bol
tovar používaný, ale popisuje stav tovaru. Podľa toho sa zákazník rozhoduje, či
je cena adekvátna tovaru. Ak je cena za nový tovar rovnaká ako za mierne
poškodený resp. s poškodeným balením atď., je väčšia pravdepodobnosť kúpy
nového tovaru.
OVP: 1, ak listing_title obsahuje slovo OVP alebo ORIGINALVERPACKUNG
alebo ORIGINALVERPACKT, čo znamená originálne balenie. Ak toto slovo
neobsahuje, tak nadobúda hodnotu 0. Originálne balenie znamená vo veľkej
väčšine prípadov kompletný tovar s príslušenstvom, bez toho aby bol tovar
používaný resp. vybalený.
DEFEKT: 1, ak listing_title obsahuje slovo DEFEKT (poškodený) alebo slovo
GEBRAUCHT (použitý). Ak neobsahuje ani jedno z týchto slov, tak nadobúda
hodnotu 0. Aj keď tieto slová nie sú synonymá, spojili sme ich, lebo samostatne
by tvorili veľmi malé kategórie. Existuje všeobecný predpoklad, že použité alebo
poškodené zariadenia by sa mali pohybovať v nižších cenových reláciách.
Samozrejme cena záleží aj od vážnosti poškodenia resp. opotrebenia pri
používaní. Poškodený tovar teda prináša nižšie tržby.
GARANTIE: 1, ak listing_title obsahuje slovo GARANTIE (záruka), inak
nadobúda hodnotu 0. Platnosť záruky je veľkou výhodou v prípade
predávajúceho, pretože vie potvrdiť vek tovaru. Podobne aj kupujúci má
tendenciu kúpiť tovar v záruke, pre prípad skrytej chyby alebo možnosť vrátiť
tovar v prípade poškodenia.
Pre vytvorenie klasifikátora sme v prostredí IBM SPSS (viď. obr.5) vybrali algoritmus
C4.5 [Quinlan93], ktorý slúži na generovanie rozhodovacích stromov. Tento algoritmus
sme doplnili o 10-násobnú krížovú validáciu a metódu boosting [Shapire03] na zlepšenie
presnosti klasifikátora. Kvalitu vytvorených klasifikačných modelov sme hodnotili podľa
počtu správne zatriedených príkladov z testovacej množiny. Priemerná úspešnosť
vytvoreného modelu sa pohybovala okolo 74%. Táto hodnota však nie je smerodajná, na
vyhodnotenie úspešnosti modelov bola použitá cenová matica, ktorá bola súčasťou
zadania úlohy. Táto matica pozitívne oceňuje správne klasifikované príklady, na druhej
strane negatívne penalizuje tie nesprávne zadelené. Cieľom je samozrejme dosiahnúť
maximálny počet bodov. Víťaz v danom roku dosiahol 5 020 bodov, náš výsledok
predstavuje hodnoty okolo 3800 bodov.
132
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
Objavovanie znalostí a jeho potenciál pre reálne aplikácie
Obr.5: Časť implementovaného riešenia v prostredí IBM SPSS
Porovnanie použitých prístupov v oboch prípadoch (víťaz, resp. náš prístup) ukazuje
odlišnosti najmä z pohľadu použitých výpočtových prostriedkov a času samotného
generovania modelov. Napr. v oboch prípadoch boli extrahované príznaky/atribúty
popisujúce jednotlivé predmety aukcie z položky „listing_title“. Tento prístup predstavoval
základný stavebný kameň úspešnosti, keďže len jednoduchá klasifikácia na základe
dodaných pôvodných atribútov priniesla nízke výsledné bodové hodnotenie. Víťaz
extrahoval viac ako 4 tisíc kľúčových slov, z ktorých vytvoril binárne atribúty. Ako vhodná
metóda klasifikácie boli v oboch prípadoch použité rozhodovacie stromy, kde víťazný
model obsahoval okolo 1000 rozhodovacích stromov (náš model 4 – na základe atribútu
kapacita), avšak ich samotné generovanie trvalo skoro celý deň. Tento víťazný prístup
sme sa rozhodli vyskúšať aj my, kde už rozšírenie nášho modelu na osem rozhodovacích
stromov, prinieslo zlepšenie výsledného hodnotenia o 200 bodov. Tento progres
predstavuje motiváciu v ďalšej práci s cieľom priblížiť sa dosiahnutým výsledkom víťaza,
ale s ohľadom na dostupné výpočtové kapacity (nami dosiahnutý výsledok bol
vygenerovaný v reálnom čase).
2.3 Predikcia výskytu dôležitého meterologického javu
V súčasnosti, najmä v súvislosti s vplyvom význačných a nebezpečných javov na
spoločnosť (doprava, poľnohospodárstvo, turistický ruch, civilná ochrana), vzniká
zvýšený záujem o krátkodobé výstrahy s presnejšou lokalizáciou ako všeobecné
predpovede počasia. Takýmto význačným meteorologickým javom je aj hmla, ktorá má
značný vplyv na ľudské aktivity (spomeňme leteckú, lodnú či cestnú dopravu). Preto sme
si v našom prípade stanovili úlohu predpovedať výskyt hmly v lokálnom meradle
pomocou vybraných klasifikačných algoritmov (binárna klasifikácia: 0 - nebude hmla
alebo 1 - bude hmla). Vstupné dáta predstavovali meteorologické merania z prostredia
letísk v Spojených Arabských Emirátoch, ktoré dodala firma MicroStep MIS zaoberajúca
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
133
František Babič, Ján Paralič
7
sa dlhodobo touto problematikou. Tieto historické dáta obsahovali METAR správy
reprezentujúce pravidelné správy o počasí v štandardnom formáte. Získaná dátová
množina bola analyzovaná s cieľom pochopiť jednotlivé atribúty, ich hodnoty a verifikovať
kvalitu dát. Už v tejto fáze bol identifikovaný nepomer medzi pozitívnymi a negatívnymi
príkladmi hmly (pozitívny – bola hmla, negatívny – nebola hmla). Dodaná vzorka
obsahovala len 0,36% pozitívnych príkladov, čo inšpirovalo viacero následných operácií
vo fáze predspracovania alebo modelovania. Takisto boli identifikované kľúčové atribúty
(aktuálne počasie na letisku, viditeľné mraky v prvej úrovni, celkové pokrytie mrakmi,
dohľadnosť, relatívna vlhkosť, atď.), aj pomocou expertov v meteorológii.
Vo fáze predspracovania bolo najprv nutné vyriešiť manipuláciu s velkým množstvom dát,
ktorá prinášala problémy v štandardných nástrojoch (napr. MS Excel) z pohľadu
výkonnosti. Preto bola navrhnutá a implementovaná vlastná aplikácia [Albert11], ktorá
ponúka rôzne typy operácii predspracovania, ako integrácia a čistenie dát, dopĺňanie
chýbajúcich hodnôt rôznymi spôsobmi, vytváranie časových okien o zvolenej veľkosti,
riešenie duplicitných záznamov, rôzne filtre, atď. Výsledkom týchto operácií bola
pripravená dátová množina pre fázu modelovania. Je dôležité poznamenať, že sme sa do
tejto fázy niekoľkokrát vrátili, práve na základe dosiahnutých výsledkov vo fáze
modelovania. Testovali sme rôzne prístupy k predspracovaniu, menili sme nastavenia
jednotlivých operácií; hľadali dodatočné zdroje dát, ktoré by nám umožnili lepšie popísať
dané meterologické javy. Takisto sme predspracované dáta transformovali do časových
sérií (okien).
Obr.6: Výsledná matica rozdelenia príkladov do cieľových tried
Fáza modelovania zahŕňala vytvorenie konkrétnych klasifikačných modelov pre predikciu
hmly. Na tieto účely boli použité dva prístupy: neurónové siete a rozhodovacie stromy.
Rozhodovacie stromy (algoritmus C4.5) pre ich schopnosť pracovať s nekompletnými
a zašumenými doménami; a jednoduchú interpretovateľnosť výsledného modelu.
7
http://sk.wikipedia.org/wiki/METAR
134
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
Objavovanie znalostí a jeho potenciál pre reálne aplikácie
Neurónové nástroje, na druhej strane, predstavujú robustný klasifikačný nástroj, ale
neumožňujú interpretovať výsledný model. Tieto dve metódy boli aplikované na
vytvorené časové okná o veľkosti 5 meraní (prvé časové okno obsahovala merania č.
1,2,3,4,5 – druhé časové okno obsahovalo merania č.2,3,4,5,6, atď.). Experimenty boli
realizované opäť v prostredí IBM SPSS (pozri obr.6). V rámci týchto experimentov sme
riešili nevyváženosť klasifikačnej triedy, vhodný pomer rozdelenia dát na trénovaciu
a testovaciu množinu, stratifikovaný výber dát do týchto množín, atď. Takisto sme
zanedbali dáta, ktoré reprezentovali kontinuálny výskyt hmly, lebo v takom prípade je
predpoveď hmly v podstate jednoduchá záležitosť.
Evaluácia dosiahnutých výsledkov bola založená na nasledovnej metrike:
Návratnosť = správne klasifikované pozitívne príklady (1-1 podľa matice) / (správne
klasifikované pozitívne príklady (1-1 podľa matice) + nesprávne klasifikované
negatívne príklady (0-1 podľa matice))
Falošný poplach = nesprávne klasifikované pozitívne príklady (1-0 podľa matice) /
všetky pozitívne príklady (1-0 + 1-1)
Úspešnosť modelu = návratnosť – falošný poplach
Naše experimenty dosiahli potešujúce a prijateľné výsledky (úspešnosť modelu 0,33 (+/0,19 odchýlka) pre rozhodovacie stromy a 0,26 (+/-0,12 odchýlka) pre neurónové siete),
ktoré sú porovnateľné s inými existujúcimi prístupmi v tejto oblasti. Zároveň je nutné
pokračovať vo vylepšovaní modelov, najmä vo fáze predspracovania s cieľom získať
vyvážený pomer pozitívnych a negatívnych príkladov hmly (napr. vytvorením
reprezentatívnych negatívnych vzorov v rovnakom počte ako máme pozitívne príklady –
napr. pomocou zhlukovacej analýzy).
3. Záver
Cieľom nášho článku bolo ukázať potenciál využitia metód objavovania znalostí v
rôznych reálnych aplikáciách prostredníctvom vhodných výpočtových prostriedkov. Tri
prezentované príklady predstavujú ukážky implementácie projektov dolovania znalostí
pomocou metodológie CRISP-DM, ktorá reprezentuje všeobecne prijímaný štandard pre
danú oblasť. Dosiahnuté výsledky dokumentujú vhodne zvolené prístupy, ale zároveň
poskytujú priestor pre ďalšie zlepšenie. Takisto výber nástroja IBM SPSS sa ukázal ako
dobrá alternatíva, aj vzhľadom na výsledky prieskumu Rexer, kde sa už niekoľko rokov
objavuje na popredných miestach v kategóriách využívania alebo obľúbenosti.
8
Naša výskumná skupina sa tejto oblasti venuje už niekoľko rokov, napr. v rámci
projektov sme riešili úlohy ako predikcia spotreby pitnej vody, analýza dát popisujúcich
akcie používateľov v kolaboratívnom systéme, predikcia hmly a nízkej oblačnosti na
základe historických meterologických dát, a ďalšie. Na tieto účely sme vybudovali
laboratórium, ktoré poskytuje základné hardvérové vybavenie (pracovné stanice,
serverové riešenia, sieťová infraštruktúra spojená s optickou kostrou SANET) opatrené
viacerými zaujímavými softvérovými prostriedkami, nielen pre oblasť dolovania znalostí,
napr. IBM SPSS, SAS Enterprise Guide alebo Miner, Statistica Base, atď.
Prostredníctvom vybudovanej technologickej infraštruktúry chceme nadviazať na
doterajšie skúsenosti, a naďalej sa podieľať na výskume a vývoji v tejto oblasti,
samozrejme aj v spolupráci s praxou. V štádiu riešenia pripravujeme analýzy
8
http://web.tuke.sk/fei-cit/index.html
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
135
František Babič, Ján Paralič
transakčných dát reprezentujúce nákupy zákazníkov (bežný tovar alebo drogéria)
s cieľom odhaliť zaujímavé závislosti, napr. vo forme asociačných pravidiel.
V dnešnej dobe sa takisto do popredia dostáva pojem Business Intelligence (BI), ktorá
ponúka zaujímavé možnosti pre firmy, najmä čo sa týka priblíženia dátových operácií
používateľom v priateľskej a jednoduchej forme. V tejto oblasti plánujeme experimentálne
otestovať vybrané open source riešenia ako Pentaho alebo SpangoBI prostredníctvom
implementácie dátového skladu obsahujúceho finančné informácie o firmách.
Poďakovanie
Tento príspevok vznikol za podpory grantovej agentúry APVV SR v rámci projektu
VMSP-P-0048-09 (50%) a realizáciou projektu Rozvoj Centra informačných
a komunikačných technológií pre znalostné systémy (kód ITMS projektu: 26220120030)
na základe podpory operačného programu Výskum a vývoj financovaného z Európskeho
fondu regionálneho rozvoja (50%).
4. Referencie
[Alber11]
ALBERT, F.: Diplomová práca. Katedra kybernetiky a umelej inteligencie,
FEI Technická univerzita v Košiciach, 2011.
[Bednár11]
BEDNÁR P., BABIČ F., ALBERT F., PARALIČ J., BARTÓK J.: Design and
implementation of local data mining model for short-term fog prediction at the airport.
In: 9th IEEE International Symposium on Applied Machine Intelligence and
Informatics: Proceedings, Smolenice 2011, s.349-353, Budapešť: Obuda University,
ISBN 978-1-4244-7428-8.
[Howson08] HOWSON, C.: Successful Business Intelligence. McGraw-Hill, New York,
2008, ISBN 978-0071498517.
[Paralič03]
PARALIČ, J.: Objavovanie znalostí v databázach. Elfa, Košice 2003,
ISBN 80-89066-60-7.
[Shapire03] SCHAPIRE, R. E.: The boosting approach to machine learning: an
overview. Nonlinear estimation and classification (Berkeley, CA, 2001), s.149–171,
Lecture Notes in Statist., 171, Springer, New York, 2003.
[Shearer00] SHEARER, C.: The CRISP-DM model: the new blueprint for data mining.
Journal of Data Warehousing 5, s.13–22 (2000).
[Quinlan93] QUINLAN, J. R.: C4.5: Programs for Machine Learning. Morgan Kaufmann
Publishers, 1993.
136
SYSTÉMOVÁ INTEGRACE 2 - PŘÍLOHA/2011
Download

Compaq Computer, s