Partitionieren eines Schwimmers Array in ähnlichen Segmenten (Clustering)

Question

Ich habe eine Reihe von Schwimmern wie folgt aus:

[1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200] 

Nun, ich möchte das Array wie folgt aufzuteilen:

[[1.91, 2.87, 3.61] , [10.91, 11.91, 12.82] , [100.73, 100.71, 101.89] , [200]] 

// [ 200] wird als ein Ausreißer wegen weniger Cluster-Unterstützung betrachtet werden

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

Ich verbrachte viel Zeit, um eine Lösung zu finden. Allerdings scheinen die Vorschläge ganz anders zu sein: this und this VS. this und this und this.

Ich fand einen anderen Vorschlag als Clustering, d.h. natural breaks optimization. Dies muss jedoch auch die Partitionsnummer wie K-means (richtig?) Deklarieren.

Es ist ziemlich verwirrend (besonders weil ich diese Art von 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 einigen theoretischen Begründung?

Alle Hinweise auf Artikel/Artikel (wenn verfügbar C/C++/Java-Implementierung) mit einigen theoretischen Begründung wird sehr hilfreich für mich sein.

Answer 1

Ich denke, ich würde die Daten sortieren (wenn es nicht schon), dann nehmen Sie 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".

Edit: Schnell Demo-Code in C++:

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <numeric> 
#include <functional> 

int main() { 
    std::vector<double> data{ 
     1.91, 2.87, 3.61, 10.91, 11.91, 12.82, 100.73, 100.71, 101.89, 200 
    }; 

    // sort the input data 
    std::sort(data.begin(), data.end()); 

    // find the difference between each number and its predecessor 
    std::vector<double> diffs; 
    std::adjacent_difference(data.begin(), data.end(), std::back_inserter(diffs)); 

    // convert differences to percentage changes 
    std::transform(diffs.begin(), diffs.end(), data.begin(), diffs.begin(), 
     std::divides<double>()); 

    // print out the results 
    for (int i = 0; i < data.size(); i++) { 

     // if a difference exceeds 40%, start a new group: 
     if (diffs[i] > 0.4) 
      std::cout << "\n"; 

     // print out an item: 
     std::cout << data[i] << "\t"; 
    } 

    return 0; 
} 

Ergebnis:

1.91 2.87 3.61 
10.91 11.91 12.82 
100.71 100.73 101.89 
200 

Answer 2

Clustering übernimmt in der Regel mehrdimensionale Daten.

Wenn Sie eindimensionale Daten haben, sortieren Sie es, und verwenden Sie dann entweder Kernel-Dichte-Schätzung oder nur für die größten Lücken suchen.

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

Betrachten Sie die größte Lücke in 1-dimensionalen Daten zu finden. Es ist trivial: sort (n log n, aber in der Praxis so schnell wie es geht), dann betrachten Sie zwei benachbarte Werte für die größte Differenz.

Jetzt versuchen „größte Lücke“ in zwei Dimensionen definiert, und einen effizienten Algorithmus es zu finden ...