Diskussion:K-Means-Algorithmus

Die Grafiken,auf die verwiesen wird (z.B. Bild:K_Means_Example_Step_1.svg) existieren nicht.

Algorithmus ist zweifelhaft

Ich beschäftige mich jetzt seit einigen Wochen mit Clustering-Algorithmen und in der gesamten Literatur wird MacQueens Artikel "Some Methods for classification and Analysis of Multivariate Observations" referenziert. Deshalb laß ich mir das Original jetzt durch und muss feststellen, dass dieser nicht dem Algorithmus entspricht, der hier genannt wird. Der Algorithmus der hier genannt wird, wird in der Literatur als "Minimaldistanzverfahren" bezeichnet. Der entscheidende Unterschied besteht darin, dass im Minimaldistanzverfahren, die Zentroide nach der Neuzuweisung ALLER Datenpunkte zum nächsten Zentroid neu berechnet werden, wohingegen beim K-Means, die Zentroide nach JEDER Neuzuweisung EINES Datenpunktes zum nächsten Zentroid neu berechnet werden.

Gibt es Gegenmeinungen? Falls nicht, sollte dies geändert werden! --TU München-Diplomand (nicht signierter Beitrag von 85.181.138.214 (Diskussion) 12:53, 3. Nov. 2012 (CET))

Nicht unerhebliche Teile der Literatur schreiben sogar MacQueen falsch (als McQueen)... - oder geben den Lloyd-Algorithmus an, aber als Quelle MacQueen... wenn ein Buch sehr sauber geschrieben ist, so wird es zwischen der Problemstellung ("k-means") und den verschiedenen Algorithmen zum Suchen einer konkreten Lösung unterscheiden (unter anderem MacQueen, Lloyd, Hartigan, diverse Variationen, diverse Initialisierungen ...) - genau wie Wikipedia sind auch Bücher nicht fehlerfrei.

Du wirst du den Artikel nochmal lesen müssen. Insbesondere den Abschnitt "Historische Entwicklung von K-Means", den hier direkt anschließenden Diskussionsabschnitt "Der" k-Means-Algorithmus (übrigens hängt man neue Diskussionen unten an!) sowie folgenden Satz im Artikel:

Der am häufigsten verwendete k-Means-Algorithmus ist der Lloyd-Algorithmus

denn während der Name auf MacQueen (1967) zurückgeht, die Idee der Distanzminimierung von Hugo Steinhaus (1957), wird in der Tat öfter der Algorithmus von Lloyd verwendet (1957 Bell-intern publiziert, 1982 öffentlich). Auch das Buch von Hartigan 1979 müsste man erwähnen. Lloyds algorithmus kann man grob gesagt als "bulk iteration k-means" im Gegensatz zum "incremental k-means" von MacQueen abgrenzen ist in der Praxis oft praktischer. Als Hausaufgabe (da du ja Diplomand bist) für dich: Vergleiche die Komplexität der Algorithmen von MacQueen und Lloyd, und überlege, wann welcher Algorithmus zur Suche eines lokalen Optimums für das k-means-Problem vorteilhafter ist.

Für Wikipedia ist erstmal interessant, was man in der Praxis unter "k-means" versteht, und das ist nun mal der Algorithmus von Lloyd. Und in einem separaten Paragraphen natürlich auch die ganze Geschichte dazu, wie MacQueens Version (von der eben der Name stammt) und auch wie die Arbeit von Lloyd verspätet/nachträglich öffentlich zugänglich gemacht wurde.

Wenn du dich schon gerade mit dem Artikel von MacQueen beschäftigst, hier noch eine Fragestellung um den Artikel wirklich zu verbessern (das von dir eben erwähnte ist durchaus bekannt, und zwar im Artikel noch nicht breitgetreten, aber der Artikel ist keineswegs falsch, höchstens unvollständig weil er eben sich primär auf den in der Praxis als "k-means" bezeichneten und relevanteren Lloyd-Algorithmus bezieht):

Hat MacQueen in seiner Publikation vorgesehen, dass Objekte _mehrmals_ neu zugeordnet werden, oder wird nur eine einzige Iteration gemacht? - das war mir damals nämlich nicht ganz klar. Üblicherweise iteriert man in der Praxis auc MacQueen - wenn man denn MacQueen verwendet und nicht Lloyd - auch bis zur Konvergenz. Beim ersten Überfliegen des MacQueen Artikels sah es für mich aber so aus, als ob jedes Objekt genau ein mal zugeordnet würde. Ich hatte das aber damals nicht verifizieren können, dass das von MacQueen schon so vorgesehen war, dass man den Algorithmus iterativ verwendet. --Chire (Diskussion) 22:56, 3. Nov. 2012 (CET)

Danke für deine Antwort, die ich eben gerade gelesen habe. Inzwischen bin ich auch ein bisschen schlauer. Genau das was du ansprichst scheint der Fall zu sein: Die Autoren beziehen sich auf der Artikel von MacQueen, beschreiben aber den Lloyd-Algorithmus. (Ehrlich gesagt bin ich deswegen gerade etwas genervt von den Professoren, die ihre eigenen Bücher falsch schreiben - mag ja richtig gemeint sein, aber der Leser kann nur erkennen was geschrieben wurde, nicht was gemeint wurde. Aber zurück zum Thema.)

Zum MacQueen-Arikel: Den laß ich inzwischen fünf mal durch in der Hoffnung es stände etwas von Iteration da, aber ich kann dies beim besten Willen nicht erkennen. MacQueens K-Means ist daher meiner Ansicht nach eben kein Expectation-Maximization Algorithm und daher noch weniger als Referenz zum Standart K-Means geeignet. Shame on you, dear authors, shame on you (bezogen auf die Buchautoren.) Auch wenn man den in der Tat in der Praxis iteriert - im Artikel ist das eine einmalige Zuordnung und witziger Weise werden in der Praxis für die erste Zuordnung Zufallswerte verwendet, wenn ich das richtig weiß. Letzendlich hat dann der Artikel, mit dem scheinbaren MacQueen-K-Means gar nichts gemeint.

Zu deiner Frage: Das incremental k-means sollte deutlich komplexer sein und spielt seinen Voretil bei schlechter getrennten Clustern aus. Eine Idee wäre also erstmal ein bulk k-means und dann ein incremental k-means laufen zu lassen.

Jetzt habe ich aber auch noch eine Frage: Ich laß/überflog den Artikel von Lloyd nun auch. Wo steht der k-means algorithmus darin? Der scheint mir ein wenig in den Formeln vergraben zu sein - so wirklich gebündelt und anschaulich wie hier auf der Wikipedia-Seite konnte ich den nicht erkennen. Hast du da eine konkrete Stelle? (Im Vergleich dazu gab es im eine solche Stelle durchaus im MacQueen-Paper.) --TU München-Diplomand (nicht signierter Beitrag von 92.228.62.226 (Diskussion) 17:16, 6. Nov. 2012 (CET))

Der original Lloyd-Artikel ist IMHO auch unleserlich. Aber da geht es eben auch um Pulse Code Modulation. Hartigan ist daher m.E. die zeitlich erste brauchbare Quelle. --Chire (Diskussion) 22:15, 6. Nov. 2012 (CET)

Könntest du ein Paper bzw. ein Buch angeben? Am Besten eines, dass man im Netz bekommen kann. --TU München-Diplomand (nicht signierter Beitrag von 92.224.202.151 (Diskussion) 10:05, 7. Nov. 2012 (CET))

Also wenn du recherchieren willst: Hartigan, Clustering Algorithms, 1975. Wenn du etwas neueres lesen willst: Ester und Sander, Knowledge Discovery in Databases. Techniken und Anwendungen. Springer, Berlin 2000, ISBN 3540673288. Die waren aber an der LMU München, ich weiß nicht ob das für dich in Ordnung ist... aber: sie unterscheiden zwischen "Clustering durch Varianzminimierung" (nach Forgy 1965), haben den korrekten MacQueen (also inkrementell) gehen aber natürlich recht schnell weiter zu PAM, CLARANS, EM, DBSCAN usw. - m.E. das beste deutsche Buch dazu. Wenn ich es richtig in Erinnerung habe, unterscheiden sich Forgy/Hartigan/Lloyd im Wesentlichen durch die Initialisierung oder so. Bei GNU R scheint Forgy == Lloyd zu sein. Hartigan ist ein Fortran-Program, die anderen C. Genauer habe ich mir da den Unterschied auch noch nicht angeschaut. --Chire (Diskussion) 14:34, 7. Nov. 2012 (CET)

"Der" k-Means-Algorithmus

Es gibt nicht "den" k-Means-Algorithmus. Gemeint ist der Lloyd-Algorithmus. Hier muss der Artikel noch besser unterteilt werden. --E. Sinclair 23:54, 12. Jun. 2009 (CEST)

erledigtErledigt schon länger geschehen. --Chire 16:06, 10. Aug. 2011 (CEST)

Leider ist die Anmerkung von Sinclair falsch. MAcQueen hat in dem Paper von 1967 k-means eingeführt, siehe: MacQueen Some methods for classification and analysis of multivariate observations

Der Algorithmus von LLoyd entspricht auch nicht dem K-means Algorithmus, sondern beschreibt allgemein partitionierendes Clustering. Außerdem ist mir aufgefallen, das nur eine Distanzfunktion gefordert wird, k-Means (und andere partitionierende Verfahren) benötigt aber eine Metrik. Leider verweist der Link von Distanzfunktion zur Metrik, obwohl es sich dabei um sehr verschiedene Dinge handelt. Das ist auch der Unterschied zu k-mediod Verfahren. Ein Median macht an der Stelle leider keinen Sinn, da er führ Mehrdimensionale Daten nicht definiert ist. (nicht signierter Beitrag von 134.102.206.230 (Diskussion) 18:29, 28. Nov. 2011 (CET))

Das war genau die Aussage, dass man wenn man vom "k-means-Algorithmus" spricht, eben meistens nicht MacQueen spricht, sondern meistens den Algorithmus von Lloyd meint - die populärste Approximation für dieses Problem. Und im Artikel steht nun wirklich eindeutig Lloyd-Algorithmus. Mein Vorschlag an dich: füge doch einfach einen Abschnitt hinzu, der den originalen Algorithmus von MacQueen erklärt. Ansonsten, siehe die diversen Referenzen, bspw. MathWorld über die gängige Verwendung des Begriffs. Für Wikipedia ist zunächst mal die gängige Verwendung des Begriffs entscheidend, und da wird meistens k-means mit Lloyd gleichgesetzt, nicht mit dem Original-Ansatz von MacQueen. Es spricht aber natürlich nichts dagegen, MacQueens Algorithmus in den Artikel mit aufzunehmen, als alternativen Ansatz - relevant ist er unzweifelhaft. --Chire 22:13, 28. Nov. 2011 (CET)

P.S. Distanzfunktion verweist bewussst auf "Distanzfunktion" im Sinne der Mathematik, und das ist eben eine Metrik; auch wenn in der Informatik der Begriff (mangels einer weit akzeptierten Alternative) auch für nicht-metrische Unähnlichkeitsfunktionen verwendet wird. k-Means nach Lloyd kann man wunderbar ohne Metrik laufen lassen - nur die Konvergenz ist halt dann nicht mehr sichergestellt, und man muss entsprechende Abbruchkriterien bereithalten (die aber auch für numerische instabilitäten gut sein können). K-medoid hat hingegen eine ganz andere Begründung als das fehlen der Dreiecksungleichung. Viel mehr hat man hier nicht das Problem interpolieren zu müssen, wodurch man es auch für nicht-numerische und nicht-kontinuierliche Attribute verwenden kann. Da hilft es aber auch nichts, wenn man auf diesen Daten eine Metrik hätte, wenn man einfach keinen sinnvollen Mittelwert berechnen kann... Nur ein paar Anmerkungen. Wie gesagt, du bist herzlich eingeladen, den Algorithmus von MacQueen in einem eigenen Paragraph zu dokumentieren und seine Vorteile zu diskutieren. Das bringt mehr als hier auf der Diskussion über den Namen zu streiten... --Chire 22:13, 28. Nov. 2011 (CET)

Nemen wir einmal den ersten Satz:"Das war genau die Aussage, dass man wenn man vom "k-means-Algorithmus" spricht, eben meistens nicht MacQueen spricht, sondern meistens den Algorithmus von Lloyd meint - die populärste Approximation für dieses Problem."(nicht signierter Beitrag von 134.102.206.230 (Diskussion) 11:25, 29. Nov. 2011 (CET))

In dem Artikel taucht MacQueen nicht auf, obwohl er den Begriff in seiner Arbeit von 1967 eingeführt hat. Also wo genau wird denn von einem K-means Problem gesprochen, gibt es dazu Originalarbeiten? Einen k-means Algorithmus gibt es, siehe MacQueen, einen Llyod Algorithmus auch, da fehlt zumindestens ein Verweis auf die Arbeit von Llyod und wieso er als k-means gezeichnet wird. (nicht signierter Beitrag von134.102.206.230 (Diskussion) 11:25, 29. Nov. 2011 (CET))

Ich stimme dir zu, dass die Arbeit von MacQueen erwähnt werden sollte, deswegen habe ich dich ja eingeladen, diese Lücke im Artikel zu ergänzen! Dass der Algorithmus von Lloyd wichtiger ist, findest du in zahlreichen Quellen, wo eben k-means synonym zu Lloyd (und nicht MacQueen) verwendet wird. --Chire 13:25, 29. Nov. 2011 (CET)

Können Sie dazu Quellen angeben, die wirklich wissenschaftliche Paper sind, oder wird nach Mehrheitsentscheid über die Richtigkeit entschieden? Der angegebene Algorithmus taucht übrigens auch nicht in dem Paper von Lloyd auf. Ich kann den Artikel umschreiben, finde aber nicht, das MacQueen nur eine Randnotiz ist. In der Wissenschaftlichen Literatur taucht er übrigens auch auf, mit dem k-means Algorithmus. Bei Google Scholar zum Beispiel 8000 mal zitiert im Gegensatz zu knapp 600 Zitaten des Lloyd papers. Siehe auch unter anderem: Knowledge Discovery in Databases - Martin Ester; Jörg Sander. Die Frage ist also soll es so bleiben, weil Lloyd im Internet oft als k-means bezeichnet wird, oder nicht?--134.102.206.230 15:07, 29. Nov. 2011 (CET)

Ich habe nirgendwo gesagt, dass MacQueen nur eine Randnotiz bleiben soll. Er soll genauso wie Lloyds auftauchen. Daher nochmal mein Vorschlag: statt hier zu versuchen einen Konflikt zu provozieren, warum fügst du nicht einfach den Algorithmus von MacQueen in den Artikel ein (wie zuvor schon vorgeschlagen)? Ich habe schonmal die Quellenangaben aus der englischen Wikipedia in den Artikel übernommen ... --Chire 18:37, 29. Nov. 2011 (CET)

Bei dem bereits beschriebenen Algorithmus handelt es sich übrigens wirklich nicht um den von MacQueen - dieser beginnt explizit mit 1-elementigen Clustern, und fügt dann iterativ die verbleibenden Punkte hinzu. Daher wäre die Zuordnung von Ester und Sander auch nicht ganz korrekt, der Algorithmus wäre anscheinend besser Lloyd zugeordnet worden. Das Buch "Data Mining" von Witten, Frank, Hall scheint das einfach zu umgehen und zu sagen "existiert in vielen Varianten". Hartigan ("Clustering Algorithms", 1975) spricht von k-means, als referenzen werden aber Cox "Note on grouping" 1957, Dalenius und Tore "The problem of optimum stratification" 1951, Engelman and Hartigan "Percentage points of a test for clusters" 1969, Fisher und Van Ness "Admissible clustering procedures" 1971 und erst dann MacQueen genannt. Nach seiner Beschreibung beginnt MacQueen auch mit k Elementen und fügt dann iterativ jeweils 1 Element hinzu - doch erheblich anders als Lloyds Algorithmus, und auch nicht das, was Hartigan hier selbst als k-Means-Algorithmus bezeichnet. --Chire 18:37, 29. Nov. 2011 (CET)

Fazit: Für eine absolut korrekte Zuordnung ist eine ausführliche Literaturrecherche notwendig. Ganz so einfach wie ein "erfunden hat es aber MacQueen, und nur den darf man k-means nennen" ist es jedenfalls nicht. Insbesondere, da zum einen die populäre Methode eher die von Lloyd zu sein scheint, und diese zum anderen auch noch 10 Jahre älter ist. Da aber MacQueen wohl das erste mal dies explizit als "k-means" bezeichnet hat, verdient er zweifellos auch eine entsprechende Erwähnung. Wenn du willst, kannst du diese Punkte aber gerne genauer recherchieren, belegen und im Artikel dokumentieren! Nur: hier auf der Diskussionsseite rumzustreiten bringt uns kaum weiter! Du solltest dir dazu dann umbedingt das Buch von Hartigan von 1975 besorgen und seine Publikation von 1969. Cox sowie Fisher und Van Ness wären auch relevant. Oh, und Hartigan schreibt auch in dem Buch "Varieties of the k-Means Algorithm [...] changeable components are (i) the starting clusters (ii) the movement rule (iii) the updating rule". Also wenn er schon 1975 akzeptiert, dass es nicht nur "den" k-means von MacQueen gibt, warum hast du heutzutage so große Probleme damit? --Chire 18:37, 29. Nov. 2011 (CET)

Ich weiß nicht, wieso Sie mir unterstellen, ich will nur MacQueen zulassen, alles andere nicht? Jetzt wird er als Namensgeber genannt, wunderbar. Der unterschied zu dem Argorithmus von MacQueen ist, das dort nach jedem Schritt die Zentroiden aktualisiert werden. Jetzt bleibt nur noch die Frage, ob der Algorithmus, wirklich Lloyd zugeschrieben werden kann, denn dazu habe ich bis jetzt keine Primärliteratur gesehen, in dem Paper von 1982 taucht er schonmal nicht auf.--134.102.206.230 09:13, 30. Nov. 2011 (CET)

So wie ich in der Literatur hier MacQueens Algorithmus verstehe ist ein weiterer wesentlicher Unterschied die Wahl der Ausgangssituation (die ersten k Punkte) und - so wie ich ihn verstehe - immer nur der neue Punkt neu klassifiziert wird; es werden also (n-k) durchläufe gemacht, und in jedem wird der k+i te Punkt dem nächstgelegenen Cluster zugeweisen und dessen Mittelpunkt aktualisiert. Vorherige Punkte werden nicht erneut angeschaut? --Chire 18:50, 30. Nov. 2011 (CET)

Ansonsten funktioniert auch der Llyod Algorithmus nicht, wenn man keinen Metrischen Raum hat, denn wie sollen sonst x_i summiert werden? (nicht signierter Beitrag von 134.102.206.230 (Diskussion) 11:25, 29. Nov. 2011 (CET))

Einen Mittelwert kann ich auch ohne Metrik oder metrischen Raum berechnen, ich brauche dazu nur einen Körper (Algebra) (technisch gesehen sind übrigens die Fließkommazahlen weder ein metrischer Raum noch ein Körper; ich kann auch den Mittelwert nur approximativ genau berechnen). Die Frage, ob der Mittelwert zur Konvergenz führt, ist auch weniger eine Frage ob die Unähnlichkeitsfunktion metrisch ist, sondern viel mehr ob der Mittelwert für die Distanz garantiert die mittleren Distanzen reduziert (bzw. zumindest nicht vergrößert). Ob man um dies zu zeigen nicht sogar einen normierten Raum braucht, da wäre ich mir nicht so sicher, denn erst dann habe ich eine stabile Skalarmultiplikation ... Kennst du eine Quelle, die die Konvergenz von k-means für beliebige Metriken beweist? Ich kenne das nur für $L_{p}$-Normen und Quadratische Formen (beide erzeugen einen normierten Raum). --Chire 13:25, 29. Nov. 2011 (CET)

Ich gehe erst mal auf das Nebensächlichste (weil es nichts mit meiner Frage zu tun hat) ein: Die Fließkommazahlen mit der Euklidischen Distanz sind ein Metrischer Raum, wollen Sie dazu einen Beweis sehen? Ein Körper hilft mir nicht bei einem Mittelwert, für F_2, den Körper, der nur aus Null und eins besteht ist ein Mittelwert nicht definiert, das viele Körper auch metrische Räume sind hat ja erst einmal nichts damit zu tun.--134.102.206.230 15:07, 29. Nov. 2011 (CET)

Mal von double-besonderheiten wie NaN, +0, -0 etc. ganz abgesehen: was ist die Euklidische Distanz der $double^{2}$-Vektoren $(1.7976931348623157E308,1.7976931348623157E308)$ zu $(0,0)$ in double? Was ist der Mittelwert von $0d$ und $4.9E-324d$ in double? Ich würde deinen Beweis, dass die Fließkommazahlen ein (unter multiplikation und division abgeschlossener!) Körper sind gerne sehen ... meiner Meinung nach approximieren sie lediglich den Körper der reellen Zahlen. --Chire 18:37, 29. Nov. 2011 (CET)

metrischer Raum, nicht Körper. Aber die 32 bit Fließkommazahlen bilden auch einen Körper, denn sie besitzen 2^32 Elemente und können somit isomorph in einen Galoiskörper mit Charackteristik 2 überführt werden. Wie bereits gesagt, weiß ich nicht, was das mit Mittelwerten oder Abständen zu tun haben soll.--134.102.206.230 15:03, 30. Nov. 2011 (CET)

Aber nicht mit der Addition und Multiplikation von "double"; es ist eine Überführung von "32 bit", nicht des Konstruktes "Fließkommazahlen", da dessen Addition nicht beibehalten wird. --Chire 18:50, 30. Nov. 2011 (CET)

Und was ist der Median einer mehrdimensionalen Menge? (nicht signierter Beitrag von 134.102.206.230 (Diskussion) 11:25, 29. Nov. 2011 (CET))

Über K-medians habe ich gar nichts gesagt (den brauche ich einfach nicht, daher habe ich ihn nie nachgelesen; zum Thema Mehrdimensionale Mediane empfehle ich aber bspw. C.G. Small: A Survey of Multidimensional Medians, 1990). Welche(r) davon eine Konvergenz bei K-medians sicherstellen: keine Ahnung. Auch das kannst du, wenn du es recherchierst, gerne im Artikel nachtragen. --Chire 13:25, 29. Nov. 2011 (CET)

Danke aber für deinen ersten Beitrag bzgl. Silhouettenkoeffizient. Das war im Artikel nämlich auch nur ganz marginal angeschnitten. Der Artikel hat einfach noch einige Lücken... (P.S. nutze bitte auf Diskussions-Seiten die Signaturfunktion. Sind nur 6 Zeichen: --~~~~) --Chire 13:25, 29. Nov. 2011 (CET)

Verwendung des Silhouettenkoeffizienten

Der Silhouettenkoeffizient, der bis vor kurzem ein verwaister Artikel war, spielt eine wichtige Rolle beim k-Means-Algorithmus, wenn man mehrere Ergebnisse mit unterschiedlichem k vergleichen will. Es wäre toll wenn das jemand in der Artikel einbauen könnte. Danke! --Chire 16:01, 10. Aug. 2011 (CEST)

Dieser Abschnitt kann archiviert werden. --Chire 18:37, 29. Nov. 2011 (CET)

Distanz oder Metrik

In distanzmaß wird sehr schön erklärt, was Distanz und Metrik unterscheidet. Und ohne Dreiecksungleichung kann man leider keine Mittelwerte oder Schwerpunkte berechnen, weil es kein dazwischen geben muss. Menge = A,B,C d(A,B) = 1, d(B,C) = 1 und d(A,C) = 4 ist eine Distanzfunktion, wie soll da k-means, in welcher Ausprägung auch immer funktionieren? Wie werden die means berechnet? --134.102.206.230 15:25, 29. Nov. 2011 (CET)

Ich brauche überhaupt keine Distanz oder Unähnlichkeit oder Metrik um den arithmetischen Mittelwert zu berechnen. Das arithmetische Mittel wird nach $\mu _{i}={\frac {1}{N}}\sum _{n\in N}x_{i}$ berechnet, ohne dass dabei eine Distanzfunktion verwendet wird. Die Frage ist nur, ob dieser Mittelwert die Distanzen minimiert, also ein Minimum-Varianz-Schätzer ist (und dadurch der Algorithmus terminiert); das ist aber eine ganz andere Frage als ob die Distanz jetzt die Dreiecksungleichung erfüllen muss. --Chire 18:37, 29. Nov. 2011 (CET)

P.S. mit der diskreten Metrik $\delta$ kann ich dein obengenanntes Beispiel zu einem metrischen Raum machen (siehe Metrischer Raum#Beispiele: nicht durch Normen erzeugte Metriken). Halt mit d(A,B)=1, d(B,C)=1, d(A,C)=1. Die Dreiecksungleichung ist erfüllt! Wie berechne ich jetzt den Mittelwert? -- ich bleibe dabei, es geht nicht einfach nur darum, ob die Unähnlichkeitsfunktion metrisch ist oder nicht. Für eine $L_{p}-Norm$ kennen wir halt mit dem arithmetischen Mittelwert eine geeignete Schätzfunktion, daher terminiert und konvergiert das dann ganz auch (wenn man von Fließkommazahlenproblemen mal absieht). Ich glaube auch, dass man für eine noch größere Klasse von Normen (mindestens offensichtlich alle gewichteten $L_{p}$-Normen; ich denke auch alle von quadratischen Formen induzierten Normen) zeigen kann, dass das arithmetische Mittel hier ein geeigneter Schätzer ist. Auf $\mathbb {R} ^{n}$ mit diskreter Metrik denke ich wird das arithmetische Mittel, obwohl man es berechnen kann nicht funktionieren (und ich glaube ich kann dir einen ML-Schätzer nennen). --Chire 19:02, 29. Nov. 2011 (CET)

Es ist wunderbar, wie wir aneinander vorbeireden, leider oft ein Problem der asynchronen Kommunikation. Der Artikel ist aber bereits viel besser geworden. Die Diskussion Distanz und Metrik bringt uns wahrscheinlich nicht weiter, weil Sie immer wieder von Körper reden, und bis jetzt noch nicht erwähnt haben, wieso dieses algebraische Konstrukt irgendetwas mit Abständen oder Mittelwerten (von dem ich übrigens nie gesprochen habe) zu tun hat. Ich werde noch an ein paar Stellen verbessern und hoffe das der Artikel noch besser wird.--134.102.206.230 09:05, 30. Nov. 2011 (CET)

Nie vom Mittelwert gesprochen? Siehe erste Zeile von diesem Abschnitt, da behauptest du "ohne Dreiecksungleichung kann man leider keine Mittelwerte ... berechnen"! In einem Körper mit Skalaren aus mindestens $\mathbb {N}$ kann ich offenbar das arithmetische Mittel berechnen (da ich dann durch die Anzahl der Objekte dividieren kann). Aber ja, wir reden aneinaner vorbei, deswegen lade ich ja zu konstruktiven Änderungen am Artikel ein! --Chire 18:39, 30. Nov. 2011 (CET)

Voraussetzungen oder Probleme

Bisher werden in beiden Abschnitten zum teil ähnliche Probleme angesprochen, ich denke der Silhouettenkoeffizent, die gleiche Größe und Noise sollten nach Probleme verschoben werden.

Ich habe den Abschnitt über Varianzminimierung gelöscht, weil er das Problem mit unterschiedlichen k nicht löst. Wenn dann ist es eine Möglichkeit zur Wahl von geeigneten Startwerten.--134.102.206.230 10:41, 30. Nov. 2011 (CET)

Defekter Weblink (erl.)

• http://www.cs.umd.edu/~mount/Papers/kmlocal.pdf (Internet Archive)

– GiftBot (Diskussion) 22:22, 17. Sep. 2012 (CEST)