Hierarhično razvrščanje v skupine s pomočjo argumentiranega strojnega učenja

ZAKOTNIK, JURE (author), Guid, Matej (mentor)

Področje odkrivanja skupin (angl.clustering) v podatkih je dandanes dobro raziskano, vendar se še vedno iščejo novi pristopi za izboljšanje kakovosti odkrivanja skupin. Eden izmed takih pristopov je možnost interakcije domenskih strokovnjakov z odkrivanjem skupin tako, da eksperti podajajo domensko znanje v obliki pozitivnih (angl. must-link) in negativnih (angl. cannot-link) omejitev na pare učnih primerov, ki se strokovnjaku zdijo primerni. Tak način podajanja omejitev omogoča izboljšanje odkritih skupin in njihovo večjo skladnost z ekspertnim znanjem. V praksi je podajanje pozitivnih in negativnih omejitev na posamezne pare učnih primerov tipično dolgotrajen in zahteven proces tudi za domenske strokovnjake. V diplomski nalogi se soočimo s problemom zajemanja relevantnega domenskega znanja iz strokovnjaka in v ta namen razvijemo metodo hierarhične-ga razvrščanja v skupine s pomočjo argumentiranega strojnega učenja (angl. Argument-based hierarchical clustering, ABHC). Imenovana metoda temelji na hierarhičnem razvrščanju v skupine in paradigmi argumentiranega strojnega učenja, ki se ukvarja z zajemanjem strokovnjakovega znanja. Metoda avtomatsko izbere učne primere, ki jih smatra kot problematične, in jih predstavi domenskemu strokovnjaku. Ekspertu v dani domeni torej prikaže primere, za katere meni, da ne sodijo v skupino, v katero so bili razvrščeni. Ekspert na problematične primere vnaša domensko znanje v obliki argumentov, metoda pa s pomočjo protiprimerov izpostavlja morebitne pomanjkljivosti ali nekonsistentnosti strokovnjakovih argumentov. Strokovnjak lahko tako dopolni pomanjkljivosti podanih argumentov in s tem dobi bolj kakovostno postavljene omejitve. Le-te pa so ključ za izboljšanje rezultata razvrščanja primerov v skupine. Hkrati so pridobljene omejitve in posledično tudi odkrite skupine skladne s strokovnjakovim znanjem. Razvili smo aplikacijo, ki omogoča interakcijo strokovnjaka s hierarhičnim razvrščanjem v skupine s pomočjo prej omenjene metode. Učinkovitost algoritma smo empirično ovrednotili na treh eksperimentalnih domenah s pomočjo domenskega eksperta in rezultate razvrščanja primerjali s klasičnim algoritmom hierarhičnega razvrščanja v skupine z omejitvami ter dobili spodbudne rezultate. Novo metodo hierarhičnega razvrščanja v skupine smo primerjali tudi s sorodnim algoritmom AB k-means, ki prav tako temelji na odkrivanju skupin s pomočjo argumentiranega strojnega učenja, a se pri tem opira na metodo voditeljev. V izbranih eksperimentalnih domenah smo pokazali, da ABHC občutno izboljša rezultate odkrivanja skupin.

• Language: Slovenian
• Keywords: strojno učenje, nenadzorovano učenje, delno nenadzorovano strojno učenje, hierarhično razvrščanje, argumentirano strojno učenje, odkrivanje skupin z omejitvami
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-124755
• COBISS.SI-ID: 51621123
• Publication date in RUL: 15.02.2021

Secondary language

• Language: English
• Title: Hierarchical clustering with argument-based machine learning

Abstract

Data clustering and data clustering methods are well researched topics nowadays, but there is always room for improvement. One way to improve data clustering methods is to implement them with knowledge from any domain expert. One way to extract knowledge from a given expert is in the form of positive must-link and negative cannot-link pairwise constraints. This type of constraints improves the quality of the detected groups. In real-world applications, extracting knowledge in the form of positive and negative constraints is a challenging and time-consuming task for any expert. In this thesis we address the problem of extracting relevant domain knowledge from any expert and develop a method called Argument-based Hierarchi- cal Clustering (ABHC), which is based on hierarchical clustering and built on the argument-based machine learning paradigm (ABML). The method automatically selects cases that are considered problematic and presents them to the expert. In other words, these problematic cases are cases that are likely to have been clustered into the wrong cluster. The expert then articulates its domain knowledge in the form of arguments and constraints as to why the problematic case should or should not be in the cluster it was clustered into. While the method uses counter examples to expose any shortcomings or inconsistencies in the expert's arguments. The counter examples allow the expert to improve his arguments and as a result we get more e_cient constraints and these are the key to improve the clustering results and not only that, the constraints obtained in this way are more consistent with the knowledge of the expert. We have also developed an interactive application using the aforementioned method to test the e_ectiveness of our approach. The method was tested on three experimental domains using domain expert knowledge. We compared the results with two other algorithms. One is a hierarchical clustering with constraints called Constrained Agglomerative (CA) and the other called Argument-based k-means (AB k-means), which is also based on argumentbased machine learning but uses the k-means algorithm as a clustering method. The results look promising.

• Keywords: machine learning, unsupervised machine learning, semi-unsupervised machine learning, hierarchical clustering, argument-based machine learning, constrained clustering