Partitionierung eines Float-Arrays in ähnliche Segmente (Clustering)

8

Ich habe ein Array von Schwimmern wie folgt:

%Vor%

Nun möchte ich das Array wie folgt partitionieren:

%Vor%

// [200] wird aufgrund der geringeren Cluster-Unterstützung als Ausreißer betrachtet

Ich muss diese Art von Segment für mehrere Arrays finden und ich weiß nicht, was die Partitionsgröße sein sollte. Ich habe versucht, es zu tun, indem ich hierarchisches Clustering (Agglomerating) verwende und es gibt zufriedenstellende Ergebnisse für mich. Das Problem ist jedoch, dass ich vorgeschlagen wurde, keine Clustering-Algorithmen für eindimensionale Probleme zu verwenden, da sie keine theoretische Begründung (wie sie für mehrdimensionale Daten sind) dazu verwenden.

Ich habe viel Zeit gebraucht, um eine Lösung zu finden. Die Vorschläge scheinen jedoch ganz anders zu sein als: dies und dies VS. dies und dies und das .

Ich habe einen anderen Vorschlag gefunden als Clustering, d. h. Optimierung natürlicher Brüche . Dies muss jedoch auch die Partitionsnummer wie K-means (richtig?) Deklarieren.

Es ist ziemlich verwirrend (besonders weil ich diese Art der Segmentierung auf mehreren Arrays durchführen muss und es unmöglich ist, die optimale Partitionsnummer zu kennen).

Gibt es irgendwelche Möglichkeiten, Partitionen zu finden (so können wir die Varianz innerhalb von Partitionen reduzieren und die Varianz zwischen Partitionen maximieren) mit einer gewissen theoretischen Begründung?

Irgendwelche Hinweise auf Artikel / Artikel (wenn verfügbar C / C ++ / Java-Implementierung) mit ein paar theoretischen Begründungen sind sehr hilfreich für mich.

    
alessandro 05.07.2013, 01:33
quelle

2 Antworten

8

Ich denke, ich würde die Daten sortieren (wenn es nicht schon ist), dann nimm benachbarte Unterschiede. Teilen Sie die Unterschiede durch die kleinere der Zahlen, es ist ein Unterschied zwischen einer prozentualen Änderung zu erhalten. Setzen Sie einen Schwellenwert und wenn die Änderung diesen Schwellenwert überschreitet, starten Sie einen neuen "Cluster".

Bearbeiten: Schneller Demo-Code in C ++:

%Vor%

Ergebnis:

%Vor%     
Jerry Coffin 05.07.2013, 01:57
quelle
2

Clustering nimmt normalerweise multidimensionale Daten an.

Wenn Sie eindimensionale Daten haben, sortieren und verwenden Sie dann entweder die Kerndichteschätzung oder suchen Sie einfach nach den größten Lücken.

In einer Dimension wird das Problem wesentlich einfacher, weil die Daten sortiert werden können. Wenn Sie einen Clustering-Algorithmus verwenden, wird dies leider nicht genutzt, verwenden Sie stattdessen eine 1-dimensionale Methode!

Überlegen Sie, die größte Lücke in eindimensionalen Daten zu finden. Es ist trivial: sort (n log n, aber in der Praxis so schnell wie es geht), dann schauen Sie sich zwei benachbarte Werte für die größte Differenz an.

Versuchen Sie jetzt, "größte Lücke" in zwei Dimensionen zu definieren, und einen effizienten Algorithmus, um sie zu finden ...

    
Anony-Mousse 05.07.2013 07:44
quelle