Pelin, Helena (2016) Spektralno klasteriranje. Diploma thesis, Faculty of Science > Department of Mathematics.

PDF
Language: Croatian Download (3MB)  Preview 
Abstract
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 NPhard 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.
Item Type:  Thesis (Diploma thesis) 

Supervisor:  Drmač, Zlatko 
Date:  2016 
Number of Pages:  54 
Subjects:  NATURAL SCIENCES > Mathematics 
Divisions:  Faculty of Science > Department of Mathematics 
Depositing User:  Iva Prah 
Date Deposited:  04 Nov 2016 13:37 
Last Modified:  04 Nov 2016 13:37 
URI:  http://digre.pmf.unizg.hr/id/eprint/5263 
Actions (login required)
View Item 