Java k-Means clustering Algorithmus für 1D Daten

Helios co.

Lt. Commander
Registriert
März 2005
Beiträge
1.863
Hallo Community,

ich habe eine interessante Aufgabe, die ich gerne mit einem Clustering Algorithmus lösen würde (nur für den Fall der Fälle: es handelt sich nicht um eine Schulaufgabe oder ähnliches!)

Und zwar habe ich eine feste und geringe Anzahl ganzer numerischer Werte, der Art: 28,28,28,24,23,18,15,16,8,4,4,1,0.

Diese Daten möchte ich auf drei (oder mehr) Cluster verteilen (die Anzahl der Cluster möchte ich jedoch vorgeben dürfen!). Der k-Means Algorithmus könnte sich meines Erachtens dafür eignen, Alternativen sind natürlich erwünscht!

Ich würde sehr ungerne den k-Means Algorithmus von Grund auf selber implementieren, da es einfach meine Freizeit nicht zulässt und ich mir nicht einmal sicher bin, ob ich das Ergebnis gebrauchen kann. Darüber hinaus hat meine Suche im Netz zwar viele Beispielimplementierungen geliefert, die aber entweder nicht funktionierten weil notwendige Bibliotheken fehlten, oder aber hat der Code nicht wirklich zu meiner Problemstellung gepasst und ein Umschreiben ebenfalls wieder zu zeitfressend gewesen wäre.

Falls jemand von euch eine simple Implementierung hat/kennt, wäre ich ihr/ihm dankbar dafür (gerne auch via PM).

Im Voraus vielen Dank für jeden Rat.
 
ich kann dir zwar keine implementierung liefern, aber es gibt einen einfachen exakten algorithmus mit laufzeit O(n^2 * k) für den eindimensionalen fall, siehe
http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf

edit: wenn man eine laufzeit von O(n^3 * k) in kauf nimmt, wird die implementierung nochmals einfacher und meines erachtens in jedem fall weniger aufwand als die suche nach einer bestehenden implementierung. bei der von dir beschriebenen größenordnung von n sollte das ja überhaupt kein problem darstellen. übrigens liefert der algorithmus optimale j-clusterings für alle 1 <= j <= k in einem lauf gleich mit, sodass du auch siehst, wieviel du verlierst, wenn du weniger cluster erlaubst.
 
Zuletzt bearbeitet:
Zurück
Oben