Wie initialisiert man Zentroide in "k-means clustering", die zur Domäne der Datenpunkte gehören?

Question

Wie kann ich diesen Code ändern, um die Zentroide innerhalb der Domäne der Datenpunkte zu initialisieren?

Zum Beispiel: wenn DATA = [[2.0, 5.0], [1.0, 5.0], [22.0, 55.0], [42.0, 12.0], [15.0, 16.0]] Dann könnten Schwerpunkte (x, y) Sei ein beliebiger Wert, so dass x zu: [1,42] und y zu [5,55] gehört. Die Zentroide sollten nicht unbedingt Datenpunkte sein.

Hinweis: Der Dataipe für Daten ist float.

import random 
import math 

BIG_NUMBER = math.pow(10, 10) 
data = [] 
centroids = [] 

class Centroid: 
def __init__(self, x, y): 
    self.x = x 
    self.y = y 

def set_x(self, x): 
    self.x = x 

def get_x(self): 
    return self.x 

def set_y(self, y): 
    self.y = y 

def get_y(self): 
    return self.y 

def initialize_centroids(k,DATA): 
for j in range(k): 
    x = random.choice(DATA) 
    centroids.append(Centroid(x[0], x[1])) 

return 

Answer 1

Ihre aktuelle Methode ähnelt der Forgy-Methode zur Auswahl von Anfangsschwerpunkten. Anstatt zu loopen und zufällige Entscheidungen zu treffen, können Sie random.sample verwenden, um k Datenpunkte auszuwählen. Dies ist im Allgemeinen eine gute Methode. Ihr Kommentar widerspricht jedoch der Frage, dass die Zentroide keine Datenpunkte sein dürfen.

Eine alternative Methode wird jeder Datenpunkt in eine Anfangspartition zufällig zugewiesen werden, (beispielsweise mischen und dann die Daten in Scheiben schneiden), und Verwenden der berechneten Zentroide der k zufällig ausgewählten Partitionen

random.shuffle(data) 
random_partitions = [data[i::k] for i in range(k)] 
centroids = [ "calculate centroid of partition()" for partition in random_partitions] 

Diese Methode neigt dazu, die Schwerpunkte nahe der Mitte der Daten zu setzen, was wünschenswert sein kann.

Siehe https://en.wikipedia.org/wiki/K-means_clustering#Initialization_methods

Answer 2

Der üblicher Weg k-Mittel zur Initialisierung verwendet zufällig Punkte abgetasteten Daten.

Initialisierung durch Zeichnen von Zufallszahlen aus dem Datenbereich tut nicht Ergebnisse zu verbessern. Dies mag zunächst als eine gute Idee erscheinen, aber es ist höchst problematisch, weil es auf der falschen Annahme beruht, dass die Daten gleichmäßig verteilt sind. Im Gegensatz dazu sind Daten geclustert und die besten Zentren befinden sich in der Mitte des Clusters. Insbesondere sehen Sie leer Cluster sehr oft, so diese Initialisierung ist in der Regel Ihre schlechteste Wahl.

Wenn Sie darauf bestehen, finden Sie das Minimum und Maximum auf jeder Achse, dann ziehen Sie zufällige Werte von Uniform [min; max] jeder.