Spektralno klasteriranje

master's thesis

• Author: Helena Pelin
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Vjeran Hari (član povjerenstva)
• Committee member: Luka Grubišić (član povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Ukratko, metoda spektralnog klasteriranja zahtijeva da naše podatke koje je potrebno grupirati prikažemo u formi neusmjerenog grafa u kojem težine bridova definiramo kao mjere sličnosti između podataka. Kako bismo particionirali graf, potrebne su nam funkcije particioniranja poput reza, razmjernog reza ili normaliziranog reza. Kao najbolja funkcija pokazuje se normalizirani rez jer jedini posjeduje svojstvo dualnosti, odnosno istovremene minimizacije sličnosti između klastera te maksimizacije sličnosti unutar klastera što je upravo i cilj metode. Kako su optimizacije normaliziranog reza NP-teški problemi, metoda se iz diskretnog prostora prebacuje na neprekidnu domenu gdje nam na raspolaganju stoje sva dobra svojstva Laplacijana grafa, njegovih svojstvenih vrijednosti i vektora te teoremi iz varijacijske karakterizacije spektra simetrične matrice susjedstva. Pokazuje se da je za particioniranje grafa na K dijelova potrebno pronaći svojstvene vektore K najvećih svojstvenih vrijednosti normaliziranog Laplacijana grafa čime dobivamo neprekidno rješenje particioniranja. Da bismo dobili diskretno rješenje koje najbolje aproksimira pravo, spektralnom rotacijom naizmjenično nalazimo ortogonalnu matricu i diskretna rješenja čija će ortonormalna transformacija konvergirati ka pravom rješenju.

Abstract (english)

In this work we focused on the spectral clustering method which has become one of the most popular modern clustering algorithms. For the purpose of clustering the given objects (people, pixels, points...), we represented the data in a form of a weighted undirected graph where the nodes are the points in a feature space and the edges represent similarities between the points. In order to partition the graph, one needs partitioning functions like Cut, Ratio Cut or Normalized cut. The last one appears to perform the best because of the duality property. This means that the function simultaneously minimizes the disassociation between the groups and maximizes the association within the groups which is exactly what the clustering method is aiming to do. The optimization of the Normalized cut function is shown to be a NP-hard problem so in order to find a solution, we have to move our problem from the discrete domain to the continuous one. Based on the variational characterization of the spectrum of the associated Laplacian, an approximate solution is constructed using the eigenspace of its dominant eigenvalues. It is shown that to partition the graph into K groups, one has to find the eigenvectors of the K largest eigenvalues of the normalized Laplacian. By doing so, we obtain the relaxed solution to the problem. In order to get the discrete one, we iteratively find a sequence of orthogonal matrices and a discrete approximate solutions that tend to approximate well the true discrete solution.

• Keywords: spektralno klasteriranje; neusmjereni graf; normalizirani rez; NP-teški problem; Laplacijani graf; particioniranje grafa
• Keywords (english): spectral clustering method; undirected graph; Normalized cut; NP-hard problem; Laplacian graph; partition ot the graph
• Language: croatian
• URN:NBN: urn:nbn:hr:217:536542
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-29 11:40:34