Kontinuierliches Clustering

Ich habe also ein Problem mit dem Clustering mit Live-Daten, die kontinuierlich gestreamt werden. Da ich einen ständig wachsenden Datensatz habe, bin ich mir nicht sicher, wie ich effizientes und effektives Clustering am besten ausführen kann. Ich habe einige mögliche Lösungen gefunden, darunter:

1. Das Festlegen eines Grenzwerts für die Anzahl der zulässigen Datenpunkte wird entfernt, wenn der Grenzwert erreicht wird, wenn ein anderer Datenpunkt am ältesten Punkt eingeht. Im Wesentlichen würde dies darauf hindeuten, dass ältere Daten für uns nicht mehr relevant genug sind, um uns darum zu kümmern, was wir verlieren, wenn wir sie wegwerfen.

2. Wenn genügend Daten vorhanden sind, um ein gutes Clustering zu erstellen, betrachten Sie dies als "Setup". Wenn neue Punkte hinzukommen, müssen Sie nicht alle Daten neu gruppieren, sondern nur herausfinden, welchem ​​Clusterzentrum der neue Punkt am nächsten liegt, und ihn hinzufügen. Der Vorteil hierbei ist, dass Sie vermeiden können, bei jedem neuen Punkt ein neues Cluster zu erstellen, und dass Sie nicht alle anderen Punkte, nur die Cluster-Zentren, speichern müssen, wenn Sie dieses Clustering als "gut genug" betrachten. Der Nachteil ist, dass das erneute Ausführen des Algorithmus mit allen Datenpunkten von Anfang an genauer sein kann.

Während dies einige mögliche Lösungen sind, die ich mir überlegt habe, würde ich gerne wissen, ob es bekanntere Techniken gibt, um dieses Problem anzugehen. Ich denke, Websites wie Google mussten sich irgendwie damit auseinandersetzen (und ich hoffe, dass "mehr RAM, Server und Prozessoren hinzufügen" oder "Ihre Rechenzentren kontinuierlich erweitern" nicht die einzigen verfügbaren Antworten sind).

Es hört sich so an, als würden Sie nach Online-Algorithmen für das Clustering suchen .

Ich schlage vor, in Google Scholar nach "Online-Clustering" zu suchen. Vielleicht erweisen sich die folgenden Links als nützlich (zumindest als Ausgangspunkt).

• Guha et al.: Clustering von Datenströmen: Theorie und Praxis
• Beringer und Hüllermeier: Online-Clustering von Datenströmen

Es gibt eine Menge Arbeit am Stream-Clustering (was sich geringfügig von Online-Methoden unterscheidet, aber im Wesentlichen das ist, was Sie wollen). Die obige Referenz von Guha et al. Ist sehr gut, und für eine allgemeinere Perspektive darüber, welche Arten von Techniken funktionieren und welche Methoden in der Vergangenheit verwendet wurden (sowohl heuristisch als auch präzise), sollten Sie sich meine Umfrage ansehen beim Clustering in Streams .

Sie können sich auch die Notizen zu Vorlesung 14 und Vorlesung 15 meines Kurses über Datenstromalgorithmen ansehen .

Ich mag die obige Umfrage von Suresh und fasse verschiedene Ansätze beim Stream-Clustering zusammen. Sie haben nicht danach gefragt, aber es ist in einigen Fällen möglich, dass das Problem darin besteht, dass die fortlaufenden Daten von verteilten Servern gesehen werden, dass ein Clustering in der Mitte aufrechterhalten werden muss und nicht viele Daten verschoben werden müssen. Siehe hier .