Učenje odločitvenih pravil z evolucijsko optimizacijo

PIČULIN, MATEJ (author), Robnik Šikonja, Marko (mentor)

Učenje pravil je eno od uspešnih napovednih in opisnih metod strojnega učenja. Pravila dosegajo solidno klasifikacijsko točnost in so razložljiva, kar je pomembno za končne uporabnike, ki napovedim z razlago bolj zaupajo. Izziv pri iskanju odločitvenih pravil je dobiti kratke in razumljive sezname pravil z visoko klasifikacijsko točnostjo. To je vodilo do razvoja mnogih različnih oblik klasifikacijskih pravil, kot so trda pravila, mehka pravila, verjetnostna pravila itd. Razvili smo dve metodi za iskanje odločitvenih pravil z uporabo optimizacije s kolonijo mravelj, ki je uspešna metoda za diskretno optimizacijo. V prvem delu disertacije predstavimo novo metodo imenovano nAnt-Miner, ki, za razliko od večine drugih metod, osnovanih na koloniji mravelj, obravnava tudi številske atribute. To vodi do večjega preiskovalnega prostora in vpliva na čas izvajanja ter porabo pomnilnika. Pokazali smo, da je metoda nAnt-Miner primerljiva z ostalimi metodami na osnovi kolonije mravelj, vendar je slabša od metode FURIA za iskanje mehkih pravil. Prednost metode nAnt-Miner je v tem, da lahko zazna močne odvisnosti med atributi. V drugem delu disertacije predstavimo metodo ProAnt-Miner, ki išče verjetnostna pravila. Predstavimo novo interpretacijo feromonov za delovanje te metode. Metoda ProAnt-Miner je v primerjavi z metodo nAnt-Miner hitrejša, dosega višjo klasifikacijsko točnost in porabi manj pomnilnika, predvsem zaradi uporabe drugačnega preiskovalnega grafa. Pokazali smo, da se metoda ProAnt-Miner, glede na klasifikacijsko točnost, statistično ne razlikuje od vodilnih metod, kot sta FURIA in RIPPER. Metoda ProAnt-Miner ima novo obliko pravil, ki lahko da nov pogled na podatke. Metodi smo ovrednotili na realnih in umetnih podatkovnih množicah.

• Language: Slovenian
• Keywords: kolonija mravelj, evolucijsko računanje, strojno učenje, učenje pravil, verjetnosta pravila, mehka pravila
• Work type: Doctoral dissertation
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2018
• PID: 20.500.12556/RUL-105183
• Publication date in RUL: 07.11.2018

PIČULIN, MATEJ, 2018, Učenje odločitvenih pravil z evolucijsko optimizacijo [online]. Doctoral dissertation. [Accessed 12 April 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=105183

Secondary language

• Language: English

Abstract

One of successful predictive and descriptive approaches in machine learning is decision rule learning. Decision rules achieve reasonable classification accuracy and are interpretable, which is important to end users, who trust predictions more if they are supported with explanations. The challenge in mining decision rules is to find a short and comprehensible rule list with high classification accuracy. This led to many different types of classification rules like crisp rules, soft rules, probabilistic rules, etc. We developed two new methods for mining classification rules based on ant colony optimization, which is a successful discrete optimization method. In the first part of the dissertation, we present a new method called nAnt-Miner, which can, contrary to most other ant colony based approaches, handle numeric attributes. This leads to an increased search space and affects the running time and use of memory. We showed that the nAnt-Miner method is comparable to other ant colony optimization based rule learning methods, but is worse than fuzzy rules based method FURIA. The advantage of the nAnt-Miner method is that it can detect strong dependencies between attributes. In the second part of the dissertation we present the ProAnt-Miner method, which mines probabilistic rules. We introduce a novel interpretation of pheromone values for this approach. ProAnt-Miner is faster, achieves better prediction accuracy than nAnt-Miner, and uses less memory due to a different search graph. We showed that the ProAnt-Miner classification accuracy does not statistically differ from the state-of-the-art methods like FURIA and RIPPER. The ProAnt-Miner method has new rule form, which can give the user new insights. We evaluated both methods on real and artificial datasets.

• Keywords: ant colony optimization, evolutionary computation, machine learning, rule learning, probabilistic rules, soft rules