Metode indukcije pravila
Metoda stabla odlučivanja je bazirana na pristupu podijeli-pa-vladaj ("divide-and-conquer") klasifikacijskim problemima. Te metode rade na principu dijeljenja prostora primjera na osnovu vrijednosti jednog atributa, koji najbolje primjere prema klasama, a potom, rekurzivno, procesirajući podskupove primjera prema podjeli.
Alternativni pristup je da se uzme svaka klasa odvojeno, te pokuša 'pokriti' sve primjere u toj klasi, istovremeno isključujući sve primjere koji nisu u toj klasi. To je tzv. pristup 'pokrivajući' ("covering") pristup, jer se u svakom novom koraku nastoji odrediti pravilo koje 'pokriva' odredjeni dio primjera.
Metode indukcije pravila su algoritmi koji rade na principu pokrivanja prostora prmjera i to dodavanjem testova pravilu koje se generira, uvijek nastojeći stvoriti pravilo maksimalne točnosti. Dok metode stabla odlučivanja odabiru atribut koji najbolje maksimizira separaciju izmedju klasa (koristeći kriterij informacijskog dobitka), metode indukcije pravila nastoje pronaći u svakom novom koraku par atribut-vrijednost koji maksimizira vjerojatnost željene klase.
Slika 1 prikazuje jednu od osnovnih metoda induciranja pravila (ustvari to je Prism metoda, opisana u knjizi I.H. Witten & E. Frank "Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations"
Slika 1: Jednostavni algoritam indukcije pravila.
Ova metoda generira samo 'ispravna' pravila, ako gledamo njenu točnost na primjerima iz skupa za učenje. Bilo koje pravilo s točnošću manjom od 100% je netočno, jer klasificira primjere u ciljnu klasu koji zapravo ne spadaju u tu klasu. Jednostavni algoritam na Slici 1, nastavlja dodavati uvjete pravilu sve dok ono nije potpuno točno. Algoritam iterira po svim klasama ciljnog atributa, generirajući pravila za svaku klasu posebno. Algoritam uvijek počinje s praznom lijevom stranom - pravilom, koje ustvari pokriva sve primjere skupa E (!), te u svakom koraku, dodavanjem novog uvjeta (par atribut-vrijednost) ograničava pokrivanje pravila, sve dok ono ne pokriva samo primjere ciljne klase.
U svakom koraku algoritam odabire najbolji par atribut-vrijednost u smislu točnosti. Ukoliko postoji više parova atribut-vrijednost koji su iste točnosti, odabire se onaj koji pokriva najveći broj primjera.
WWW tekstovi o metodama indukcije pravila
A tutorial on rule induction
by P.Flach
http://macflach.cs.bris.ac.uk/~flach/presentations/IDAHTML/sld001.htm
Rule induction: Ross Quinlan's ID3 algorithm
(part of the Data Mining tutorial)
by P.Ross
http://www.dcs.napier.ac.uk/~peter/vldb/dm/dm.html
© 2001 LIS - Institut Rudjer Bošković
Posljednja izmjena: September 08 2015 09:28:57.