Kriteriji kompleksnosti za k-means algoritam

master's thesis

• Author: Stela Šeperić
• Mentor: Pavle Goldstein (mentor)
• Committee member: Pavle Goldstein (predsjednik povjerenstva)
• Committee member: Juraj Šiftar (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: k-means algoritam; klasteriranje podataka; G-means algoritam; ponašanje funkcije cilja
• Keywords (english): k-means algorithm; data clustering; G-means algorithm; behaviour of the objective function
• Language: croatian
• URN:NBN: urn:nbn:hr:217:213762
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-02-13 10:17:45