Crossroad Blog

KDD Cup 2009 prišiel s typickou úlohou kladenou na dnešných analytikov – tvorby viacerých modelov, nad množstvom neznámych dát, v  krátkom čase. Tento článok predstavuje samotnú súťaž a postup riešenia založený na postupnej redukcii objemu dát s ohľadom na výpočtovú náročnosť metód využitú v jednotlivých krokoch.

1 Úvod

KDD Cup je medzinárodná súťaž v data – miningu a objavovaní znalostí každoročne organizovaná organizáciou ACM Special Interest Group on Knowledge Discovery and Data Mining [http://www.sigkdd.org/kddcup/].

Veľkým benefitom súťaže pre riešiteľov je možnosť otestovať si skúsenosti na netriviálnych úlohach z reálneho sveta. Tieto úlohy, podľa organizátorov, zároveň reflektujú výzvy súčasnosti stojace pred riešiteľmi v mnohých oblastiach a podporujú výskum nových metód a riešení.

13. ročník súťaže podporila spoločnosť Orange. Pripravila praktickú úlohú postavenú nad vlastnými dátami. V pravidlách stanovila požiadavky, ktoré aj sama žiada od vlastných analytikov pri riešení podobných úloh. A poskytla finančnú odmenu pre víťazov súťaže.

Špecifikom súťaže bol krátky čas na riešenie, veľmi široká množina dát, viacero úloh. Aj keď harvér pre riešenie pravidlá súťaže nijako nelimitovali, nie každý riešiteľ má k dispozícií dostatočný hardvér pre spracovanie daného množstva dát a svoje riešenie musí prispôsobiť vlastným možnostiam.

2 Zadanie úlohy

Úlohou bol odhad príznakov (churn, appetency, up-sell) pre klientov Orange [1].

Churn – náchylnosť klienta k zrušeniu, resp. nepredĺženiu zmluvného vzťahu alebo ďalšieho využívania služieb spoločnosti.

Appetency – v kontexte súťaže znamená náchylnosť k zakúpeniu novej služby alebo produktu.

Up-sell – náchylnosť k zakúpeniu služby s vyššou hodnotou alebo prídavku k existujúcej službe.

Dátová množina obsahovala:

• 15 000 atribútov o klientoch v jednej tabuľke, z toho 14 740 numerických, a 260 kategoriálnych, žiadne konštantné hodnoty
• 50 000 pozorovaní so známym výstupom z množiny {0,1} pre všetky 3 súťažné úlohy – trénovacia množina
• 50 000 pozorovaní bez známeho výstupu – validačná množina

Kvalita riešenia sa hodnotila presnosťou predikcie na validačnej množine. Hodnotiacim kriériom bola priemerná hodnota AUC pre všetky 3 riešené úlohy.

AUC znamená plochy krivkou ROC (Reciever Operating Characteristics) – závislosť kumulatívneho percenta pozítívnych pozorovaní ku kumulatívnemu percentu negatívnych pozorovaní vzhľadom na hodnotu skóre.

Počas súťaže bolo možné získať hodnotu AUC na 10% validačnej množiny – to umožnilo overenie vlastného riešenia a zamedzilo pokusom preučiť model. Po uzavretí súťaže organizátori zverejnili výsledky na celej validačnej množine.

3 Riešenie

Pre riešenie bola zvolená overená CRISP DM [www.crisp-dm.org] metodológia pozostávajúca z krokov pochopenia úlohy, pochopenia dát, prípravy dát, modelovania, vyhodnocovania modelu a nasadenia riešenia, pričom kľúčovými pre riešenie boli kroky prípravy dát a modelovania. Ako modelovacia technika bola zvolená logistická regresia. Ako hardvér pre riešenie bol použítý bežný notebook CPU Intel Pentium Mobile 1.6GHz, 1.5 GB RAM, 40 GB HDD a SAS9 Base.

3.1 Voľba systému na spracovanie dát

Prvým problémom bolo načítanie vstupného súboru – 3,3 GB dát v CSV formáte. Relačnédatabázy (Oracle, MS SQL, …) dokážu vytvárať tabuľky s maximálne 1000 stĺpcami, preto na reprezentáciu dát neboli vhodné. Jednotlivý riešitelia používali Matlab, prípadne písali vlastný kód na spracovanie dát v jazykoch C, či Java. Ako vhodný na spracovanie takto širokých dát sa ukázal systém SAS9 Base. Dokáže vytvoriť tabuľky s teoreticky neobmedzeným počtom stĺpcov, navyše obsahuje funkcie pre ďalšie kroky prípravy dát a tvorby modelu [2].

3.2 Redukcia objemu dát

Pokiaľ je obrovské množstvo dát problémom, viacero prístupov:

• Redukcia počtu pozorovaní (riadky)
  • Použitie náhodnej vzorky dát – výsledky získané na dostatočnej veľkej vzorke dát budú podobné ako na celých dátach
  • Stratifikované vzorkovanie – s dodržaním distribúcie cieľovej premennej alebo so zahrnutím všetkých pozitívnych prípadov
• Redukcia počtu atribútov (stĺpce)
  • Na základe heuristických pravidiel pre „správny tvar prediktoru”
  • Na základe štatistík hodnotiacich významnosť
• Divide & Conquer (rozdeľuj a panuj)
  • Rozdeliť dataset na časti, analyzovať ich zvlášť a spojiť výsledky
  • Výsledok bude podobne dobrý, spravidla získaný v kratšom čase

Pri riešení na uvedenom hardvéri dokázala logistická regresia spracovať 50 000 pozorovaní na vstupe v rozumnom čase a nebolo potrebné použiť vzorkovanie dát.

15 000 atribútov na vstupe logistickej regresie je na bežný hadrvér priveľa. Preto sa aplikoval trojúrovňový proces redukcie počtu stĺpcov ako je zobrazený na obrázku 2.

Obrázok 2. Proces redukcie počtu atribútov pri tvorbe viacerých modelov

Prvá úroveň spočívala v diskretizácii numerických atribútov do N skupín s rovnakou početnosťou záznamov. Je to plne automatizovateľný proces, v SAS realizovaný procedúrou‚proc rank‘. Po diskretizácií sa chýbajúce hodnoty nahradia hodnotou „NA”. Následne sa odfiltrujú atribúty, ktoré obsahovali viac ako 95% hodnôt v jednej kategórii, tým pádom sú nevhodné pre logistickú regresiu. Tento krok vyradil 82% skúmaných atribútov a zabezpečil vhodný tvar dát pre ostatné kroky modelovania.

Druhá úroveň filtruje atribúty na základe významnosti ich vplyvu na cieľovú premennú. Vhodné štatistiky sú napríklad chi-kvadrát alebo v oblasti kreditného rizika preferovaná informačná hodnota, vypočítavaná na základe váhy vplyvu (Weight of Evidence, WoE) jednotlivých kategórií atribútov [3].

Efektívny výpočet týchto štatistík pre množstvo atribútov je možné efektívne realizovať generovanými SQL dopytmi v relačnej databáze. Filtrovanie sa následne realizuje stanovením hraničnej hodnoty pre významnosť atribútu.

Tretia úroveň je realizovaná automatickými metódou stepwise, ktorú poskytuje logistická regresia v systéme SAS. Princípom postupného pridávania (odoberania) najvplyvnejších (najmenej vplyvných) atribútov sa vyberú optimálne kombinácie prediktorov pre finálne modely. Výsledný počet prediktorov závisí od nastavení parametrov procedúry, v bežných úlohach je výstupom niekoľko desiatok atribútov-

Po tejto fáze sa už existuje zoznam najlepších kandidátov na finálne prediktory. Po odhade parametrov logistickej regresie môžu byť modely hotové. Pre vyladenie kvality predikcie je vhodné vrátiť sa na začiatok – detailne preskúmať základné tvary kandidátov, skúsiť nové transformácie a vytvoriť nový model ľubovoľnou metódou – na malej množine atribútov budú tieto kroky už časovo oveľa menej náročné.

4 Záver

Uvedený postup riešenia znamenal na výsledkovej listine 37. miesto z 453 zúčastnených tímov. Víťazom súťaže sa stal 12-členný IBM Research, ktorý využil cluster 9 dvojprocesorových staníc, otestoval kombinácie viacerých metód a napríklad aj generovanie nových atribútov [4]. Bol lepší o 4,90% AUC (84.93% vs. 80.02%).

Podstatou popísanej metódy ako celku je výrazné zníženie komplexnosti úlohy pre klasifikátor, pri malej redukcii informančnej hodnoty ukrytej v  dátach.

Hlavným prínosom prístupu je vysoká miera automatizácie, ktorá funguje pri spracovaní veľkého objemu dát, minimalizuje chyby spôsobené ľudkým faktorom a prináša kvalitné výsledky. Navyše v krátkom čase, s použitím bežného hardvéru a softvéru. To už sú vlastnosti spĺňajúce predpoklady pre širšie rozšírenie metód prediktívneho modelovania nad množstvom dát aj v slovenských podmienkach.

Použitá literatúra

1. http://www.kddcup-orange.com/ – portál súťaže

2. Olivia Parr Rud, Data Mining Cookbook, Juhn Wiley & Sons 2001, ISBN 0–471–38564–6

3. Raymond Anderson, The Credit Scoring Toolkit, Oxford, 2007, ISBN 978–0–19–922640–5

4. http://clopinet.com/isabelle/Projects/KDDcup09/ – workshop po súťaži, TOP riešitelia