Kurs:Maschinelles Lernen/k-Means Algorithmus
Vorherige Seite: K4 - Neuronale Netze trainieren
Nächste Seite: K5 - DBSCAN
Intuition
BearbeitenWenn die Eingabedaten in Clustern vorliegen, dann kann man sich dies in Form von "Datenwolken" vorstellen, die in einem -Dimensionalen Raum vorliegen. Eine solche Datenwolke/Cluster verfügt über einen Mittelpunkt. Ein Datenpunkt kann dann der Datenwolke zugeordnet werden, deren Mittelpunkt er am nächsten liegt.
Mathematische Formulierung
BearbeitenDas Risiko, das in diesem Fall zu minimieren ist, muss mit dem Abstand der Datenpunkten zu den Sphärenmittelpunkten zusammenhängen.
Clusteranzahl
BearbeitenEs wird davon ausgegangen, dass es Cluster gibt. Diese Anzahl wird nicht vom Algorithmus bestimmt, sondern muss zuvor gewählt werden, es handelt sich hierbei also um einen Hyperparameter.
Fehlerfunktion
BearbeitenDie Entfernung von Datenpunkten zu den Clustermittelpunkten kann man dabei als Fehler auffassen. Werden die Cluster mit und ihre Mittelpunkte durch mit beschrieben, so kann für das Risiko der Ansatz
gemacht werden.
Suche nach einem minimalen Fehler
BearbeitenWird hierfür das Minimum bzgl. der gesucht, also gefordert, dass der Gradient von verschwindet, so kann die Bedingung
gefunden werden. Das bedeutet, dass die Mittelpunkte eines Clusters bei bekannter Clusterzugehörigkeit durch diese Formel bestimmt werden müssen. Dabei soll die Anzahl der Datenpunkte im Cluster beschreiben.
Der Algorithmus
BearbeitenIm Jahr 1957 erarbeitete Stuart Lloyd den folgenden Algorithmus, der 1982 veröffentlicht wurde:
- Die Mittelpunkte der Cluster werden initialister. (Zum Beispiel zufällig oder durch geschicktes Schätzen)
- Für jedes des vorliegenden Datensatzes wird der nächstgelegene Mittelpunkt gefunden und der Datenpunkt dem entsprechenden Cluster hinzugefügt
- Es werden nach der obigen Formel die neuen Mittelpunkte der Cluster bestimmt.
- Wenn sich das Risiko (oder die nicht mehr "maßgeblich" verändern, wird der ALgorithmus beendet, ansonsten wird zurück zu Punkt 2 gesprungen.
Da der Algorithmus die Mittelwerte (engl. means) von Clustern findet, wird er als k-Means-Algorithmus bezeichnet.
Diskussion
BearbeitenDer Algorithmus wird zwar auf ein lokales Minimum führen, hat aber verschiedene Probleme
- Die Cluster die gefunden werden, sind abhängig von der Wahl von . Dieses Problem kann umgangen werden, wenn der Algorithmus mit verschiedenen Werten von initialisiert wird und jenes Cluster verwendet wird, dass das geringste Risiko aufweist.
- Die gefundenen Cluster sind davon abhängig, welche Startwerte für die gewählt wurden. Dieses Problem kann ebenfalls durch eine mehrfache Initialisierung umgangen werden. Es wird auch hier jene Konfiguration mit dem geringsten Risiko bevorzugt.
- Eine der Grundannahmen für den Algorithmus sind kugelförmige Cluster. Diese Annahme ist aber nicht immer gerechtfertigt, weshalb sich für das menschliche Auge offensichtliche Fehlklassifikationen ergeben können. Dementsprechend ist die Rechtfertigung dieser Annahme zu rechtfertigen, oder die Klassenzugeörigkeit aufzuweichen, wie es im folgenden Abschnitt erklärt wird.
Fuzzy-k-Means
BearbeitenStatt einer festen Zugehörigkeit zu einem Cluster können stattdessen Wahrscheinlichkeiten gesucht werden, dass der Datenpunkt zum Cluster gehört. Diese Wahrscheinlichkeit wird mit bezeichnet. Da der Datenpunkt im Datensatz vorkommt, müssen sich die Wahrscheinlichkeiten für einen Datenpunkt über alle Cluster zu Eins summieren, so dass
gilt. Falls ein Datenpunkt nun zu mehr als zu einem Cluster zugeordnet wird, wird der Ausdruck
mit einem einen Wert kleiner als Eins annehmen. Damit wird die neue Risikofunktion
eingeführt. Die Größe ist dabei ein neuer Hyperparameter. Für reduiziert sich dieses Riskio auf das im Fall des k-Means-Algorithmus. Für geht das Risiko unabhängig der Wahl der Wahrscheinlichkeiten und Mittelpunkte gegen Null, und es werden keine Unterscheidungen der Cluster mehr möglich sein. Das bedeutet, je größer ist, desto verschwommener (engl. fuzzy) werden die Grenzen zwischen den Clustern. Daher wird als Fuzziness und der Algorithmus als Fuzzy-k-Means-Algorithmus bezeichnet. Eine typische Wahl für ist .
Es lässt sich zeigen, dass in diesem Fall die Mittelpunkte der Cluster durch
bestimmt werden können.
Um die Wahrscheinlichkeiten zu finden, muss das Risiko unter der Nebenbedingung
minimiert werden. Zu diesem Zweck kann die Lagrange-Funktion
mit den Lagrange-Multiplikatoren betrachtet werden. Aus einer Minimierung und dem Ausnutzen der Nebenbedingungen kann für die Lagrange-Multiplikatoren der Zusammenhang
gefunden werden. Und damit zeigt sich, dass sich die Gewichte durch
bestimmen lassen.