clustering von sehr großen Datensätzen in R

Ich habe einen Datensatz, bestehend aus 70.000 numerische Werte, die für Entfernungen im Bereich von 0 bis 50, und ich möchte cluster diese zahlen, jedoch, wenn ich versuche, die klassischen clustering-Ansatz, dann würde ich zum einrichten 70,000X70,000 Distanz-matrix repräsentieren die Entfernungen zwischen jeweils zwei zahlen in meinem Datensatz, die nicht in den Speicher passt, also ich Frage mich, ob es ist eine smart Möglichkeit, um dieses problem zu lösen, ohne die Notwendigkeit zu tun, geschichtete Stichprobe?
Ich habe auch versucht, bigmemory und big analytics-Bibliotheken in R, aber immer noch nicht fit der Daten in den Speicher

  • Ist diese Lösung (mit cluster::clara) relevant/nützlich?
  • Nein nicht wirklich die Ursache des Problems ist, dass die Distanz-matrix wird zu groß, passen in jede Speicher
InformationsquelleAutor DOSMarter | 2014-02-24
  1. 5

    Können Sie kmeans, die in der Regel geeignet für diese Menge an Daten zu berechnen, eine große Zahl von Zentren (1000, 2000, ...) und führen Sie eine hierarchische Cluster-Konzept auf die Koordinaten der Zentren.Die Distanz-matrix wird kleiner sein.

    ## Example
# Data
x <- rbind(matrix(rnorm(70000, sd = 0.3), ncol = 2),
           matrix(rnorm(70000, mean = 1, sd = 0.3), ncol = 2))
colnames(x) <- c("x", "y")

# CAH without kmeans : dont work necessarily
library(FactoMineR)
cah.test <- HCPC(x, graph=FALSE, nb.clust=-1)

# CAH with kmeans : work quickly
cl <- kmeans(x, 1000, iter.max=20)
cah <- HCPC(cl$centers, graph=FALSE, nb.clust=-1)
plot.HCPC(cah, choice="tree")
    InformationsquelleAutor Victorp
  2. 16

    70000 ist nicht groß. Es ist nicht klein, aber es ist auch nicht besonders groß... Das problem ist die begrenzte Skalierbarkeit von matrix-orientierte Ansätze.

    Aber es gibt viele clustering-algorithmen, die nicht-Matrizen und tun keine Notwendigkeit O(n^2) (oder noch schlimmer, O(n^3)) runtime.

    Möchten Sie vielleicht, um zu versuchen,ELKI, die große index-Unterstützung (versuchen Sie, den R*-Baum mit SortTimeRecursive bulk-loading). Die index-Unterstützung macht es viel viel viel schneller.

    Wenn Sie darauf bestehen, mit R, geben zumindest kmeans versuchen und die fastcluster Paket. K-means hat die Laufzeit-Komplexität O(n*k*i) (wobei k der parameter k, und i die Anzahl der Iterationen); fastcluster hat eine O(n) Speicher und O(n^2) - runtime-Implementierung von single-linkage-clustering vergleichbar mit der SLINK-Algorithmus im ELKI. (Die R "agnes" hierarchische clustering verwenden O(n^3) Laufzeit und O(n^2) Speicher).

    Umsetzung ankommt. Oft Implementationen in R sind nicht die besten, IMHO, außer für core-R, die in der Regel mindestens eine wettbewerbsfähige numerischen Präzision. Aber R wurde von Statistikern, nicht von data-Minern. Es konzentriert sich auf die statistische Aussagekraft, nicht auf die Skalierbarkeit. Also die Autoren sind nicht Schuld. Es ist einfach das falsche Werkzeug für große Daten.

    Oh, und wenn Ihre Daten ist 1-dimensional, kein clustering verwenden überhaupt. Verwenden von kernel-Dichte-Schätzung. 1-dimensionale Daten ist das Besondere: es ist bestellt. Jeder gute Algorithmus für das brechen der 1-dimensionalen Daten in inverals sollten ausnutzen, dass Sie können die Daten Sortieren.

    InformationsquelleAutor Anony-Mousse
  3. 0

    Weitere nicht-matrix-orientierten Ansatz, zumindest für die Visualisierung der cluster in großen Datenmengen, ist die largeVis Algorithmus von Tang et al. (2016). Die largeVis R-Paket wurde leider verwaist, auf CRAN aufgrund fehlender Paket-Wartung, aber ein (Pflege?) version noch kompiliert aus seinem gitHub-repository über (nach der Installation Rtools), z.B.,

    library(devtools)     
install_github(repo = "elbamos/largeVis")

    Python-version des Pakets ist auch vorhanden. Der zugrunde liegende Algorithmus verwendet Segmentierung Bäume und ein Nachbarschafts-Verfeinerung zu finden, die K meisten ähnlich Instanzen für jede Beobachtung und dann die Projekte, die daraus resultierenden Nachbarschafts-Netzwerk in dim niedrigeren Dimensionen. Seine Umsetzung erfolgte in C++ und verwendet OpenMP (wenn unterstützt beim kompilieren) für multi-processing; es wurde somit ausreichend schnell für den clustering-alle größeren Daten-sets die ich bisher getestet habe.

    InformationsquelleAutor martin
Schreibe einen Kommentar