Algorithmes de clustering qui fonctionnent sur des matrices de données clairsemées [fermé]

18

J'essaie de compiler une liste d'algorithmes de clustering qui sont:

  1. Mis en œuvre dans R
  2. Opérer sur des matrices de données éparses (pas des matrices de (dis) similitude), telles que celles créées par la fonction sparseMatrix .

Il y a plusieurs autres questions sur CV qui discutent de ce concept, mais aucune d'entre elles n'est liée à des packages R qui peuvent fonctionner directement sur des matrices clairsemées:

  1. Regroupement de jeux de données volumineux et clairsemés
  2. Regroupement de données binaires clairsemées de grande dimension
  3. Recherche d'implémentation de clustering clairsemée et de grande dimension
  4. Cluster efficace dans l'espace

Jusqu'à présent, j'ai trouvé exactement une fonction dans R qui peut regrouper des matrices clairsemées:

skmeans : kmeans sphériques

Du paquet skmeans . kmeans utilisant la distance cosinus . Fonctionne sur les objets dgTMatrix. Fournit une interface à un algorithme génétique k-means, pclust, CLUTO, gmeans et kmndirs.

Exemple:

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))

Les algorithmes suivants obtiennent des mentions honorables: ils ne sont pas tout à fait des algorithmes de clustering, mais fonctionnent sur des matrices clairsemées.

apriori : l'association règle l'exploitation minière

Du paquet arules . Fonctionne sur les objets "transactions", qui peuvent être forcés à partir d'objets ngCMatrix. Peut être utilisé pour faire des recommandations.

exemple:

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 : SVD clairsemée

Du forfait irlba . Est-ce que SVD sur des matrices clairsemées. Peut être utilisé pour réduire la dimensionnalité des matrices clairsemées avant le regroupement avec les packages R traditionnels.

exemple:

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 de propagation d'affinité

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

Quelles sont les autres fonctions disponibles?

Zach
la source
Voulez-vous dire clairsemé comme dans «beaucoup de zéros» ou dans «beaucoup de valeurs manquantes»?
cbeleites prend en charge Monica le
Cette question semble être hors sujet selon plusieurs critères sur stats.stackexchange.com/help/dont-ask : chaque réponse serait également valide, vous vous attendez à plus de réponses en plus de celles fournies, et il n'y a aucun problème réel à résoudre résolu.
whuber
Je me rends compte que cela a été fermé, mais j'ai trébuché sur toutes vos questions à ce sujet en parcourant SO car j'ai eu un problème similaire;) J'ai trouvé cette bibliothèque qui utilise la propension d'affinité qui peut fonctionner avec des matrices clairsemées: bioinf.jku.at / software / apcluster
MarkeD
1
@MarkeD Merci beaucoup! C'est vraiment dommage que les recommandations de logiciels soient hors sujet ici, car je n'ai trouvé nulle part ailleurs en ligne pour les demander.
Zach
3
une fois encore une question très utile est fermée :( si vous ne connaissez pas la réponse, ne votez pas pour fermer!
MonsterMMORPG

Réponses:

1

Je n'utilise pas R. Il est souvent très lent et n'a pratiquement aucun support d'indexation. Mais les recommandations de logiciels sont de toute façon considérées comme hors sujet.

Notez que de nombreux algorithmes ne se soucient pas de la façon dont vous stockez vos données. Si vous préférez avoir une matrice clairsemée, cela devrait être votre choix, pas le choix des algorithmes.

Les gens qui utilisent trop R ont tendance à rester coincés dans la réflexion sur les opérations matricielles (car c'est la seule façon d'écrire du code rapide dans R). Mais c'est une façon de penser limitée. Par exemple, k signifie: cela ne fait rien. En particulier, il n'utilise pas du tout les distances par paires. Il a juste besoin d'un moyen de calculer la contribution de la variance; ce qui équivaut à calculer la distance euclidienne au carré.

Ou DBSCAN. Il suffit d'un prédicat "voisin". Il peut fonctionner avec des graphes arbitraires; c'est juste que la distance euclidienne et le seuil d'Epsilon est le moyen le plus courant de calculer le graphe de voisinage qu'il utilise.

PS Votre question n'est pas très précise. Faites-vous référence à des matrices de données clairsemées ou à des matrices de similitude clairsemées ?

Anony-Mousse -Reinstate Monica
la source
1
matrices de données éparses
Zach
La plupart des algorithmes peuvent fonctionner sur des matrices de données clairsemées. Par exemple, AGNES, PAM, DBSCAN, OPTICS, CLARA, ...
Anony-Mousse -Reinstate Monica
Je ne sais pas pourquoi vous avez même répondu si vous ne connaissez même pas R.
user3932000
Je connais R. Probablement encore mieux que l'utilisateur R moyen. Je connais l'évaluation non standard dans R et je sais que la plupart des modules sont écrits en C, donc quand vous passez une matrice clairsemée, elle est d'abord copiée dans une matrice de sens avant de la passer au code réel. Et chaque paquet utilise une manière différente de le faire ... Ce n'est pas efficace. Vous ne choisissez pas R si vous avez besoin d'efficacité ou d'une bonne intégration ou d'une compatibilité descendante ou d'un développement coordonné.
Anony-Mousse -Reinstate Monica