Download
PDF 1.35 MB
master's thesis
35   20
Spectral Methods for Data Clustering
Josipa Nemčić (2017)
Josip Juraj Strossmayer University of Osijek
Department of Mathematics
Chair of Applied Mathematics
Computer Science Research Group
Cite this document

Nemčić, J. (2017). Spektralne metode grupiranja podataka (Master's thesis). Retrieved from https://urn.nsk.hr/urn:nbn:hr:126:937992

Nemčić, Josipa. "Spektralne metode grupiranja podataka." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. https://urn.nsk.hr/urn:nbn:hr:126:937992

Nemčić, Josipa. "Spektralne metode grupiranja podataka." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. https://urn.nsk.hr/urn:nbn:hr:126:937992

Nemčić, J. (2017). 'Spektralne metode grupiranja podataka', Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, accessed 21 November 2019, https://urn.nsk.hr/urn:nbn:hr:126:937992

Nemčić J. Spektralne metode grupiranja podataka [Master's thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics; 2017 [cited 2019 November 21] Available at: https://urn.nsk.hr/urn:nbn:hr:126:937992

J. Nemčić, "Spektralne metode grupiranja podataka", Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, Osijek, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:126:937992

Metadata
TitleSpektralne metode grupiranja podataka
Title (english)Spectral Methods for Data Clustering
AuthorJosipa Nemčić
MentorSnježana Majstorović (mentor)
Committee memberDarija Marković (predsjednik povjerenstva)
Committee memberSlobodan Jelić (član povjerenstva)
Committee memberSnježana Majstorović (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
(Chair of Applied Mathematics)
(Computer Science Research Group)
Osijek
Defense date and country2017-04-21, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Applied Mathematics and Mathematical Modeling
Abstract
Grupiranje ili klasteriranje je postupak organiziranja podataka u disjunktne grupe (klastere) takve da su podatci unutar jedne grupe međusobno slični te različiti od podataka u drugim grupama. Sličnost mjerimo preko neke funkcije sličnosti pa podatke i odnose među njima prikazujemo pomoću grafa sličnosti. Imamo više vrsta takvih grafova, a razlikuju se po načinu na koji oblikuju lokalno susjedstvo. Svakom od tih grafova možemo pridružiti Laplaceovu matricu koja predstavlja ključni matematički objekt u spektralnim metodama. Spektralno grupiranje koristi svojstvene vektore Laplaceovih matrica za promjenu reprezentacije originalnih podataka i po tome je dobilo ime. Na promijenjenim podatcima se zatim primijeni k-means algoritam koji nam daje konačne grupe. Na prvi pogled, spektralne metode se mogu činiti kao proširenje k-means algoritma, ali to zapravo nije točno. Ključni korak kod spektralnih metoda je promjena reprezentacije podataka na vrlo pametan na- čin, tako da nakon toga čak i jednostavan algoritam kao k-means može trivijalno otkriti grupe. Spektralno grupiranje se u praksi pokazalo vrlo dobro, čak i na skupovima koji nisu dani normalnom distribucijom i nisu konveksni, međutim rezultati ovise o dosta parametra i zapravo nemamo nikakvu teorijsku garanciju na kvalitetu rješenja. S obzirom da nam ove metode omogućuju da vrlo komplicirane probleme riješimo na vrlo jednostavan način i to preko standardnih operacija linearne algebre, to je mana preko koje možemo prijeći.
Abstract (english)
Clustering is a process of organizing data into distinct groups (clusters) such that data points in one group are similar to each other and dissimilar to the data points in the other groups. We measure similarity through some similarity function and represent data by similarity graphs. There are several types of such graphs and they differ by the way they model local adjacency. We use those graphs to obtain Laplace matrix, which is the crucial mathematical object for spectral clustering methods. Spectral clustering use the eigenvectors of Laplace matrix in order to change the representation of the original data, and that’s the reason for naming. On the changed data, we just run k-means algorithm and we end up with final clusters. On the first look, we could take spectral methods as k-means improvement, but it’s not really true. The main step in spectral methods is very smart change of representation, so that afterwards, even a simple algorithm like k-means can trivially detect groups. Spectral clustering shows very well results in application, even on a data sets which are not normally distributed and those that are nonconvex. However, the results depend on many parameters and we don’t have any kind of theoretical support to guarantee it’s quality. Considering this methods allow us to solve really complicated problems in a really simple way, by standard operations of linear algebra, it’s the disadvantage that we can live with.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:126:937992
Study programmeTitle: Mathematics; specializations in: Financial and Statistical Mathematics, Mathematics and Computer Science, Industrial and Applied Mathematics
Course: Financial and Statistical Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
Created on2017-11-10 08:06:25