DMS Tutorial - ILLM Applications and results

Primjene ILLM sistema

ILLM (Inductive Learning by Logic Minimization) je skup programa namijenjen rješavanju klasifikacijskih problema. 'Online' sistem za indukciju pravila dostupan preko DMS stranica, baziran je na algoritmima ILLM sistema. Da bi ilustrirali karakteristike ILLM sistema, ovdje navodimo nekoliko realnih, kompleksnih problema iz različitih područja (od istraživanja do marketinga), na kojima je ILLM sistem uspješno primijenjen.

KDD (Knowledge Discovery in Databases) Cup 1999

Opis

Problem ovog natjecanja u konstruiranju klasifikacijskog modela, u sklopu velike svjetske konferencija KDD 1999 (Knowledge Discovery in Databases 1999), bio je vezan uz problematiku otkrivanja legitimnih odnosno nelegitmnih upada na lokalnu računalnu mrežu. Skup primjera za učenje i testiranje rješenja napravili su Prof. Sal Stolfo s Columbia University i Prof. Wenke Lee s North Carolina State University. (Isti podaci dostupni su sada u arhivi datoteka UC Irvine KDD archive.) Klasifikacijski problem sastojao se u otkrivanju 5 različitih klasa upada na sistem, uz posebnu 'matricu grešaka' sa posebnim težinskim faktorima za svaki tip greške ("cost sensitive confusion matrix"). Sam volumen originalnih podataka je vrlo velik (~4 GByte-a => ~ 5 miliona primjera u skupu primjera za učenje).

Detaljni opis problema i rezultata se može naći na ovom mjestu.

ILLM rješenje

ILLM je korišten generiranjem skupova pravila na slučajno odabarnim uzorcima od po nekoliko tisuća primjera iz originalnog skupa podataka. Generirani modeli testirani su na posebnom validacijskom skupu primjera (10vih podataka za učenje), a modeli s najvišom točnosti, izdvojeni su u poseban skup za testiranje. Klasifikacija testnih primjera napravljena je 'glasanjem' modela, uz korištenje 'matrice grešaka' s težinskim faktorima.

Rezultat

24 učesnika su na kraju dali rezultate na ocjenu. Rješenje postignuto ILLM sistemom bilo je na 17 mjestu. Ovaj problem dodatno nas je stimulirao na traženju novih rješenja u kombiniranjumodela, te kasnije na promjene u optimizacijskom kriteriju algoritma pretraživanja ILLM sistema.

CoIL (Computational Intelligence and Learning) Challenge 2000

Description

CoIL Challenge 2000 bilo je natjecanje organizirano od strane Computational Intelligence and Learning Cluster, tzv. mreže izvrsnosti koja je sponzorirana od strane EU. Održano je u proljeće 2000. Ukupno je natjecanje završilo 43 učesnika (mahom istraživačke grupe, ali i komercijalne kompanije), iako je početni broj učesnika bio daleko veći (147 registriranih).

Problem natjecanja bio je vezan uz tzv. 'direktni' marketing u području osiguranja. Iz perspektive modeliranja podataka problem je imao dva cilja: prediktivni - napraviti model s najvišim 'lift'-om koji 'prepoznaje' potencijalne kupce police osiguranja, i deskriptivni - napraviti opis potencijalnih kupaca koji će najbolje odgovarati stručnjacima iz područja marketinga. Detaljni opis problema dan je na stranicama "CoIL Challenge"-a.

Rješenje

ILLM sistem omogućava generiranje modela koji istovremeno daju rezultate i u prediktivnom i u deskriptivnom smislu, pa su oba problema rješavana istovremeno, t.j. najbolji model s obzirom na predikciju iskorišten je i za opis klijenata u okviru deskriptivnog zadatka. U eksperimentalnoj fazi korištena je metoda 'peterostruke unakrsne validacije' ("5-fold cross validation), na skupu za učenje, da bi se optimirali parametri modela (kompleksnost pravila). Konačni rezultat bio je skup pravila s najvišom vrijednosti 'lift'-a. Taj skup pravila poslužio je istovremeno za identifikaciju i opis 5-6 različitih segmenata kupaca u okviru deskriptivnog dijela zadatka. Detaljni opis svih rezultata učesnika dan je u posebnom izvještaju koji su pripremili organizatori (P. van der Putten and M. van Someren).

Rezultat

Prediktivni zadatak: 9-ti od 43(147)
Deskriptivni zadatak: 2-gi od 43(147)

NIPS (Unlabeled Data Competition) 2000

Opis

Ovo natjecanje organizirano je od strane interdisciplinarne grupe (GNCG - Guelph Natural Computation Group) sa Sveučilišta u Guelph-u. Natjecanje je bilo vezano uz poseban, novi pristup strojnom učenju, kod kojeg se nastoji koristiti i podatke koji nisu klasificirani (validacijski i testni primjeri), u procesu generiranja (učenja modela). Puni naziv natjecanja bio je "Unlabeled Data Supervised Learning Competition". Problemi (11 ukupno) koji su rješavani bili su klasifikacijskog i prediktivnog (regresijskog) tipa.

Detaljni opis natjecanja nalazi se na ovom mjestu.

Rješenje

Različita rješenja su primijenjena za različite probleme. Specifičnost je pristupa diktirana korištenjem validacijskog skupa primjera u cilju poboljšanja rezultata učenja. Generalni je pristup ILLM sistemom bio korištenje iterativne procedure kojom su odredjeni primjeri iz validacijskog skupa (takodjer neklasificirani!), postepeno ubacivani u skup za učenje na osnovurezultata dobivenih korištenjem metode eliminacije šuma ILLM sistema.

Rezultat

ILLM sistem je primijenjen na 3 od 11 problema. Ukupan rezultat bilo je sedmo mjesto.

(p1 - 1. mjesto;p5 - 6. i 7. mjesto;p7 - 14. mjesto).

CINC (Computers in Cardiology) 2001

Opis

Ovo natjecanje zahtjevalo je generiranje potpuno automatizirane metode za predikciju (otkrivanje) početka kritičnog poremećaja u radu srca - atrijalne fibrilacije ("paroxysmal atrial fibrillation/flutter" - PAF), na osnovu EKG signala prije samog početka poremećaja. Atrijalna fibrilacija je povezana uz velik rizik pojave srčanog udara i najčešći je oblik srčane aritmije (samo u Sjedinjenim državama oko 2.2 milijun ljudi). Trenutno ne postoji metoda pouzdanog otkrivanja početka poremećaja. Prediktivni algoritam u tom smislu bio bi od ogromnog značaja u prevenciji, terapiji i poboljšanju kvalitete života srčanih bolesnika. Natjecanje je bilo organizirano od strane PhysioNet i NIH/NCRR koji su stavili na raspolaganje dobro pripremljenu bazu EKG signala, te software nužan za kvalitetnu obradu signala.

Detalji i pravila natjecanja, podaci i software mogu se naći na stranicama PhysioNet-a . Dva su odvojena zadatka postavljena pred natjecatelje. Prvi zadatak povezan je s otkrivanjem modela za otkrivanje pacijenata koji pate od atrijalne fibrilacije. Drugi zadatak bio je definiranje modela za otkrivanje samog starta poremećaja ("PAF episode"), kod pacijenata koji pate od atrijalne fibrilacije.

Rješenje

Budući da su podaci (EKG signal) dani u specijalnom formatu, organizatori su ponudili specijalni software, koji omogućava čitanje signala, te osnovnu manipulaciju i analizu. Ovaj je software korišten za proces generiranja potencijalnih atributa za skup primjera za generiranje modela. Proces otkrivanja značajnih atributa bio je i ključan dio ovog problema. U našem slučaju kvaliteta atributa je provjeravana generiranjem modela na skupu za učenje, te provjerom na umjetno stvorenom validacijskom podskupu primjera za učenje. Skup tako otkrivenih atributa, korišten je za stvaranje modela (pravila) za oba zadatka. Konačno programsko rješenje predstavlja kombinaciju software-a za obradu podataka radi generiranja vrijednosti atributa, algoritam za testiranje i sam model (pravila), koja može poslužiti za automatsko otkrivanje početka poremećaja.

Rezultat

Sedmo mjesto (Zadatak br. 2: otkrivanje početka poremećaja ("onset of PAF").

PTC (Predictive Toxicology Challenge) 2001

Opis

Prevencija pojave raka uzrokovanog raznim kemijskim spojevima u okolišu je zdravstveni problem od najvećeg značaja. Gotovo sva područja ljudske aktivnosti u industrijaliziranom svijetu suočena su s rizicima vezanim uz korištenje odredjenih kemijskih spojeva. Procjene govore o cca 100,000 različitih kemikalija, koje su u upotrebi u elikim količinama u našem okruženju. Samo je mali dio tih spojeva testiran na karcinogenezu. US National Toxicology Program (NTP) intenzivno radi na poboljšanju tog stanja provodjenjem testova na miševima i štakorima, te time izdvajajući spojeve koji su potencijalno karcinogeni i za ljude. Budući da je to testiranje vrlo skup (i spor) način odredjivanja rizičnosti spojeva, potreba za jeftinijim i bržim načinom trebala bi se riješiti stvaranjem modela karcinogeneze na osnovu strukture i drugih kemijskih svojstava spojeva. Takvi modeli trebali bi imati slijedeće karakteristike:

da budu sposobni za pouzdanu predikciju toksičnosti kemikalija;
da omoguće jeftinu identifikaciju rizičnih spojeva;
da smanje potrebu za korištenjem laboratorijskih životinja u ispitivanjima.

Predictive Toxicology Challenge 2001 je osmišljen s ciljem da se postojeći programi za strojno učenje iskoriste u tu svrhu: cilj je da se dobiju modeli koji predvidjaju rezultate bioloških testova na karcinogenezu spojeva, korištenjem informacija o kemijskoj strukturi. Kompletan opis problema dan je na ovim stranicama.

Rješenje

Korištena su dva skupa deskriptora (atributa u terminologiji analize podataka), za generiranje modela ILLM sistemom:

skup napravljen na Institutu Rudjer Bošković (Dr. B. Lučić - DRAGON set);
skup napravljen u tvrtki Pfizer (George Cowan);

Nekoliko modela generirano je korištenjem podskupova deskriptora radi optimiranje prediktivne točnosti i robustnosti modela. Za svaki od zadataka (4 sveukupno, posebno za miševe i štakore, te za svaki spol), napravljena su po tri modela, koristeći različite kriterije za senzitivnost modela. Odabir tri različito senzitivna modela bio je diktiran metodom ocjenjivanja modela - ROC krivulje.

Rezultat

U fazi izrade i ocjene modela učestvovalo je samo desetak istraživačkih grupa (vjerojatno zbog relativno zahtjevnog dijela pripreme podataka (transformacija, formatiranje). Rezultati dobiveni ILLM sistemom u prosjeku su u gornjoj polovici svih rezultata, prema točnosti predikcije.