Als Anfänger im maschinellen Lernen habe ich eine Reihe von Trajektorien, die unterschiedlich lang sein können. Ich möchte sie zusammenfassen, weil einige von ihnen eigentlich den gleichen Pfad haben und sie aufgrund des Rauschens einfach SEEM anders sind.
Außerdem sind nicht alle von ihnen gleich lang . Also vielleicht, obwohl Trajektorie A ist nicht das gleiche wie Trajektorie B, aber es ist Teil von Trajektorie B. Ich möchte diese Eigenschaft auch nach dem Clustering präsentieren.
Ich habe nur wenig Ahnung von K-means Clustering und Fuzzy N-means Clustering . Wie kann ich zwischen beiden wählen? Oder sollte ich andere Methoden übernehmen?
Jede Methode, die die "Zugehörigkeit" berücksichtigt?
(ZB nach dem Clustering habe ich 3 Cluster A, B and C . Ein bestimmtes trajectory X gehört zu cluster A . Und ein kürzeres trajectory Y , obwohl nicht in A geclustert, wird als Teil von trajectory B identifiziert. )
=================== UPDATE =======================
Die oben genannten Trajektorien sind die Flugbahnen der Fußgänger. Sie können entweder als eine Reihe von (x, y) -Punkten oder als eine Reihe von Schrittvektoren (length, direction) dargestellt werden. Das Präsentationsformular steht unter meiner Kontrolle.
Es könnte ein bisschen spät sein, aber ich arbeite auch an dem gleichen Problem. Ich schlage vor, dass Sie sich TRACLUS ansehen, einen Algorithmus, der von Jae-Gil Lee, Jiawei Han und Kyu-Young Wang auf SIGMOD'07 veröffentlicht wurde. Ссылка
Dies ist bisher der beste Ansatz, den ich für die Clusterbildung von Trajektorien gesehen habe, weil:
Grundsätzlich ist ein 2-Phasen-Ansatz:
Phase eins - Partition: Unterteilen Sie die Trajektorien in Segmente. Dies geschieht mit Hilfe der MDL-Optimierung mit der Komplexität von O (n) wobei n die Anzahl der Punkte in einer gegebenen Trajektorie ist. Hier ist die Eingabe eine Menge von Trajektorien und Ausgabe ist eine Menge von Segmenten.
Phase zwei - Gruppe: In dieser Phase werden die Cluster mit einer Version des dichtebasierten Clusterings wie in DBSCAN entdeckt. Die Eingabe in dieser Phase ist die Menge der Segmente, die aus der ersten Phase erhalten werden, und einige Parameter dessen, was eine Nachbarschaft ausmacht, und die minimale Anzahl von Linien, die einen Cluster bilden können. Ausgabe ist eine Menge von Clustern. Die Clusterbildung erfolgt über Segmente. Sie definieren ihr eigenes Distanzmaß aus 3 Komponenten: Parallelabstand, Senkrechtabstand und Winkelabstand. Diese Phase hat eine Komplexität von O (n log n) wobei n die Anzahl der Segmente ist.
Schließlich berechnen sie für jeden Cluster eine repräsentative Trajektorie , die nichts anderes ist als eine gemeinsame Sub-Trajektorie in jedem Cluster .
Sie haben ziemlich coole Beispiele und das Papier ist sehr gut erklärt. Auch dies ist nicht mein Algorithmus, also vergiss nicht, sie zu zitieren, wenn du forschst.
PS: Ich habe einige Folien basierend auf ihrer Arbeit gemacht, nur für Bildungszwecke: Ссылка
Jeder Clustering-Algorithmus benötigt eine Metrik. Sie müssen den Abstand zwischen Ihren Proben definieren. In Ihrem Fall ist eine einfache euklidische Distanz keine gute Idee, besonders wenn die Bahnen unterschiedliche Länge haben können.
Wenn Sie eine Metrik definieren, können Sie einen beliebigen Clusteralgorithmus verwenden, der benutzerdefinierte Metrik zulässt. Wahrscheinlich kennen Sie vorher nicht die richtige Anzahl von Clustern, dann ist hierarchisches Clustering eine gute Option. K-means erlaubt keine benutzerdefinierte Metrik, aber es gibt Modifikationen von K-means, die (wie K-medoids) tun
Der schwierigste Teil ist die Definition der Entfernung zwischen zwei Trajektorien (Zeitreihen). Üblicher Ansatz ist DTW (Dynamic Time Warping). Um die Leistung zu verbessern, können Sie Ihre Flugbahn um eine kleinere Anzahl von Punkten (viele Algorithmen dafür) annähern.
Es wird nicht funktionieren. Weil hier ein richtiger Mittelwert ist?
Sehen Sie sich distanzbasierte Clustering -Methoden an, z. B. hierarchisches Clustering (für kleine Datensätze, aber Sie haben wahrscheinlich nicht Tausende von Trajektorien) und DBSCAN.
Dann müssen Sie nur eine geeignete Entfernungsfunktion wählen, die z.B. Unterschiede in der zeitlichen und räumlichen Auflösung von Trajektorien.
Abstandsfunktionen wie dynamic time warping (DTW) distance können dies berücksichtigen.
Dies ist ein gutes Konzept und die Möglichkeit für Echtzeitanwendungen. Meiner Ansicht nach kann man jedes Clustering übernehmen, muss aber ein geeignetes Unähnlichkeitsmaß auswählen, muss später über rechnerische Komplexität nachdenken. Papier ( Ссылка ) verwendet Hausdorff und schlägt die Technik zur Reduzierung von Komplexität und Papier vor ( Ссылка ) ) beschrieb die Verwendung der "Trajektorie-Clustering-Technik basierend auf Multi-View-Similarity"
Tags und Links algorithm cluster-analysis machine-learning data-mining