Clustering-Algorithmen, die mit spärlichen Datenmatrizen arbeiten [geschlossen]

18

Ich versuche, eine Liste von Clustering-Algorithmen zu erstellen, die Folgendes umfassen:

  1. Implementiert in R
  2. Arbeiten Sie mit Datenmatrizen mit geringer Dichte (keine (Nicht-) Ähnlichkeitsmatrizen), wie sie mit der Funktion sparseMatrix erstellt wurden .

Es gibt mehrere andere Fragen im Lebenslauf, die dieses Konzept behandeln, aber keine davon ist mit R-Paketen verknüpft, die direkt mit dünnen Matrizen arbeiten können:

  1. Clustering von großen und spärlichen Datensätzen
  2. Clustering von hochdimensionalen, spärlichen Binärdaten
  3. Auf der Suche nach einer spärlichen und hochdimensionalen Clustering-Implementierung
  4. Platzsparendes Clustering

Bisher habe ich in R genau eine Funktion gefunden, die spärliche Matrizen gruppieren kann:

Skmeans : sphärische kmeans

Aus dem skmeans-Paket . KMeans Verwendung Cosinus Abstand . Funktioniert mit dgTMatrix-Objekten. Bietet eine Schnittstelle zu einem genetischen k-means-Algorithmus, pclust, CLUTO, gmeans und kmndirs.

Beispiel:

library(Matrix)
set.seed(42)

nrow <- 1000
ncol <- 10000
i <- rep(1:nrow, sample(5:100, nrow, replace=TRUE))
nnz <- length(i)
M1 <- sparseMatrix(i = i,
                   j = sample(ncol, nnz, replace = TRUE),
                   x = sample(0:1 , nnz, replace = TRUE), 
                   dims = c(nrow, ncol))
M1 <- M1[rowSums(M1) != 0, colSums(M1) != 0]

library(skmeans)
library(cluster)
clust_sk <- skmeans(M1, 10, method='pclust', control=list(verbose=TRUE))
summary(silhouette(clust_sk))

Die folgenden Algorithmen werden lobend erwähnt: Sie sind keine reinen Cluster-Algorithmen, sondern arbeiten mit spärlichen Matrizen.

apriori : Verbandsregeln Bergbau

Aus dem Paket arules . Funktioniert mit "Transaktionen" -Objekten, die aus ngCMatrix-Objekten erzwungen werden können. Kann verwendet werden, um Empfehlungen abzugeben.

Beispiel:

library(arules)
M1_trans <- as(as(t(M1), 'ngCMatrix'), 'transactions')
rules <- apriori(M1_trans, parameter = 
list(supp = 0.01, conf = 0.01, target = "rules"))
summary(rules)

irlba : spärliche SVD

Aus dem irlba-Paket . Führt SVD auf spärlichen Matrizen durch. Kann verwendet werden, um die Dimensionalität von dünnen Matrizen vor dem Clustering mit herkömmlichen R-Paketen zu reduzieren.

Beispiel:

library(irlba)
s <- irlba(M1, nu = 0, nv=10)
M1_reduced <- as.matrix(M1 %*% s$v)
clust_kmeans <- kmeans(M1, 10)
summary(silhouette(clust_kmeans$cluster, dist(M1_reduced)))

apcluster : Clustering der Affinitätsausbreitung

library(apcluster)
sim <- crossprod(M1)
sim <- sim / sqrt(sim)
clust_ap <- apcluster(sim) #Takes a while

Welche anderen Funktionen gibt es da draußen?

Zach
quelle
Meinen Sie spärlich wie bei "vielen Nullen" oder wie bei "vielen fehlenden Werten"?
cbeleites unterstützt Monica am
Diese Frage scheint nach mehreren Kriterien unter stats.stackexchange.com/help/dont-ask nicht zum Thema zu gehören : Jede Antwort ist gleichermaßen gültig, Sie erwarten zusätzlich zu den angegebenen Antworten weitere Antworten, und es besteht kein tatsächliches Problem gelöst.
Whuber
Ich habe festgestellt, dass dies abgeschlossen wurde, aber ich habe alle Ihre Fragen dazu durchgesehen, als ich SO stöberte, da ich ein ähnliches Problem hatte;) Ich habe diese Bibliothek gefunden, die Affinitätsneigung verwendet und mit spärlichen Matrizen arbeiten kann: bioinf.jku.at / software / apcluster
MarkeD
1
@MarkeD Vielen Dank! Es ist wirklich schade, dass Software-Empfehlungen hier nicht zum Thema gehören, da ich nirgendwo anders online nach ihnen gefragt habe.
Zach
3
wieder einmal sehr nützliche Frage ist geschlossen :( Wenn Sie die Antwort nicht wissen, nur nicht für schließen abstimmen!
MonsterMMORPG

Antworten:

1

Ich benutze R nicht. Es ist oft sehr langsam und hat so gut wie keine Indizierungsunterstützung. Software-Empfehlungen werden jedoch ohnehin als nicht thematisch betrachtet.

Beachten Sie, dass es vielen Algorithmen egal ist, wie Sie Ihre Daten speichern. Wenn Sie eine spärliche Matrix bevorzugen, sollten Sie diese wählen, nicht die Wahl des Algorithmus.

Menschen, die zu viel R verwenden, neigen dazu, beim Denken in Matrixoperationen hängen zu bleiben (weil dies die einzige Möglichkeit ist, schnellen Code in R zu schreiben). Aber das ist eine eingeschränkte Denkweise. Zum Beispiel bedeutet k: es ist egal. Insbesondere werden keine paarweisen Abstände verwendet. Es muss nur ein Weg gefunden werden, um den Varianzbeitrag zu berechnen. Dies entspricht der Berechnung der euklidischen Quadratdistanz.

Oder DBSCAN. Alles was es braucht, ist ein "Nachbar" -Prädikat. Es kann mit beliebigen Graphen arbeiten; Es ist nur so, dass die euklidische Entfernung und der Epsilon-Schwellenwert die gebräuchlichste Methode zur Berechnung des von ihr verwendeten Nachbarschaftsgraphen sind.

PS Ihre Frage ist nicht sehr präzise. Beziehen Sie sich auf spärliche Datenmatrizen oder spärliche Ähnlichkeitsmatrizen ?

Anony-Mousse - Setzen Sie Monica wieder ein
quelle
1
spärliche Datenmatrizen
Zach
Die meisten Algorithmen können mit spärlichen Datenmatrizen arbeiten. ZB AGNES, PAM, DBSCAN, OPTICS, CLARA, ...
Anony-Mousse
Nicht sicher , warum Sie selbst beantwortet , wenn Sie nicht einmal wissen , R.
user3932000
Ich kenne R. Wahrscheinlich sogar besser als der durchschnittliche R-User. Ich kenne die nicht standardmäßige Auswertung in R und weiß, dass die meisten Module in C geschrieben sind. Wenn Sie also eine dünne Matrix übergeben, wird sie zuerst in eine Sinnesmatrix kopiert, bevor sie an den eigentlichen Code übergeben wird. Und jedes Paket verwendet eine andere Methode ... Das ist nicht effizient. Sie wählen R nicht, wenn Sie Effizienz oder gute Integration oder Abwärtskompatibilität oder koordinierte Entwicklung benötigen.
Anony-Mousse