Spektralno klasteriranje

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

[img]
Preview
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 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.

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 View Item