Kriteriji kompleksnosti za k-means algoritam

diplomski rad

• Autor: Stela Šeperić
• Mentor: Pavle Goldstein (mentor)
• Član povjerenstva: Pavle Goldstein (predsjednik povjerenstva)
• Član povjerenstva: Juraj Šiftar (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2014-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu obrađena je metoda za određivanje \(k\) u k-means algoritmu, što je vrlo česti problem u klasteriranju podataka. Pokazano je da funkcija cilja u k-means algoritmu konvergira. Nadalje, u potpoglavlju (1.3) pokazano je da su koordinate težišta skupa jednake aritmetičkim sredinama odgovarajućih koordinata elemenata tog skupa, te se u slučaju standardnog k-means algoritma novi centri određuju na takav način. U lemama smo dokazali da ako su podaci ekvidistantni, odnosno uniformno distribuirani, onda se optimizirana funkcija cilja ponaša odprilike kao \(C\cdot\frac{1}{k^2}\). Pretpostavka o ekvidistantnosti, odnosno uniformnoj distribuiranosti podataka, nije tako jaka kao pretpostavka o normalnoj distribuiranosti podataka u G-means algoritmu. Ovime smo pokazali da uz relativno nezahtjevne prepostavke, lijepo možemo opisati ponašanje funkcije cilja u ovisnosti o broju klastera \(k\). Na kraju, rezultati testiranja vrlo dobro potvrđuju naša teorijska saznanja o ponašanju funkcije cilja.

Sažetak (engleski)

In this thesis, we have studied method for determining \(k\) in k-means algorithm, which is a well known problem. It is shown that the objective function coverges. Furthermore, a couple of lemmas proved that, if data follow a uniform distribution, then the objective function behaves as \(C\cdot\frac{1}{k^2}\). Assumption about data is not as strong as assumption in G-means algorithm which requires normal distribution of data. We have shown that with relatively limited assumptions, we can neatly describe behaviour of the objective function with respect to \(k\) - the number of clusters. Finally, a series of tests on simulated data sets confirmed our theoretical results about behaviour of the objective function.

• Ključne riječi: k-means algoritam; klasteriranje podataka; G-means algoritam; ponašanje funkcije cilja
• Ključne riječi (engleski): k-means algorithm; data clustering; G-means algorithm; behaviour of the objective function
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:213762
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-02-13 10:17:45