| Title | Spektralne metode grupiranja podataka |
| Author | Josipa Nemčić |
| Mentor(s) | Snježana Majstorović (thesis advisor)
|
| 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. |
| Keywords | spectral clustering similarity graph Laplace matrix k-means image segmentation |
| Parallel title (English) | Spectral Methods for Data Clustering |
| Committee Members | Darija Marković (committee chairperson)
Slobodan Jelić (committee member)
Snježana Majstorović (committee member)
|
| Granter | Josip Juraj Strossmayer University of Osijek
Department of Mathematics |
| Lower level organizational units | Chair of Applied Mathematics
Computer Science Research Group |
| Place | Osijek |
| State | Croatia |
| Scientific field, discipline, subdiscipline | NATURAL SCIENCES
Mathematics
Applied Mathematics and Mathematical Modeling
|
| Study programme type | university |
| Study level | graduate |
| Study programme | Mathematics; specializations in: Financial and Statistical Mathematics, Mathematics and Computer Science, Industrial and Applied Mathematics |
| Study specialization | Financial and Statistical Mathematics |
| Academic title abbreviation | mag.math. |
| Genre | master's thesis |
| Language | Croatian |
| Defense date | 2017-04-21 |
| Parallel 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. |
| Parallel keywords (Croatian) | spektralno grupiranje graf sličnosti Laplaceova matrica k-means segmentacija slike |
| Resource type | text |
| Access condition | Open access |
| Terms of use |  |
| URN:NBN | https://urn.nsk.hr/urn:nbn:hr:126:937992 |
