Algoritmos de cluster que operam em matrizes de dados esparsas [fechado]

18

Estou tentando compilar uma lista de algoritmos de clustering que são:

  1. Implementado em R
  2. Opere em matrizes de dados esparsas (não matrizes de (des) similaridade), como aquelas criadas pela função sparseMatrix .

Existem várias outras perguntas no CV que discutem esse conceito, mas nenhuma delas se vincula aos pacotes R que podem operar diretamente em matrizes esparsas:

  1. Agrupando conjuntos de dados grandes e esparsos
  2. Agrupando dados binários esparsos de alta dimensão
  3. Procurando implementação de cluster esparsa e de alta dimensão
  4. Cluster com economia de espaço

Até agora, encontrei exatamente uma função no R que pode agrupar matrizes esparsas:

skmeans : km esféricos

Do pacote skmeans . kmeans usando a distância do cosseno . Opera em objetos dgTMatrix. Fornece uma interface para um algoritmo genético k-means, pclust, CLUTO, gmeans e kmndirs.

Exemplo:

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

Os algoritmos a seguir recebem menções honrosas: não são algoritmos de cluster, mas operam em matrizes esparsas.

apriori : associação regras mineração

Do pacote arules . Opera em objetos "transações", que podem ser coagidos a partir de objetos ngCMatrix. Pode ser usado para fazer recomendações.

exemplo:

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 esparso

Do pacote irlba . Faz SVD em matrizes esparsas. Pode ser usado para reduzir a dimensionalidade de matrizes esparsas antes do agrupamento com pacotes R tradicionais.

exemplo:

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 : Agrupamento de propagação de afinidade

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

Que outras funções existem por aí?

Zach
fonte
Você quer dizer esparso como em "muitos zeros" ou como "muitos valores ausentes"?
Cbeleites suporta Monica
Esta pergunta parece estar fora do tópico de acordo com vários critérios em stats.stackexchange.com/help/dont-ask : cada resposta seria igualmente válida, você espera mais respostas além das fornecidas e não há nenhum problema real a ser solucionado. resolvido.
whuber
Sei que isso foi encerrado, mas eu tropeço em todas as suas perguntas sobre isso enquanto navego pelo SO, pois tive um problema semelhante;) Encontrei esta biblioteca que usa propensão à afinidade que pode trabalhar com matrizes esparsas: bioinf.jku.at / software / apcluster
MarkeD
1
@MarkeD Muito obrigado! É realmente ruim as recomendações de software não serem abordadas aqui, pois não encontrei nenhum outro lugar on-line para solicitá-las.
Zach
3
mais uma vez pergunta muito útil é fechado :( Se você não sabe a resposta apenas voto não faça por perto!
MonsterMMORPG

Respostas:

1

Eu não uso R. Geralmente, é muito lento e quase não tem suporte à indexação. Mas as recomendações de software são consideradas fora de tópico de qualquer maneira.

Observe que muitos algoritmos não se importam com a maneira como você armazena seus dados. Se você preferir ter uma matriz esparsa, essa deve ser sua escolha, não a escolha dos algoritmos.

Pessoas que usam muito R tendem a ficar presas no pensamento em operações de matriz (porque essa é a única maneira de escrever código rápido em R). Mas essa é uma maneira limitada de pensar. Por exemplo, k-significa: não se importa. Em particular, ele não usa distâncias aos pares. Ele só precisa de uma maneira de calcular a contribuição da variação; o que equivale a calcular a distância euclidiana ao quadrado.

Ou DBSCAN. Tudo o que precisa é de um predicado "vizinho". Pode trabalhar com gráficos arbitrários; a distância euclidiana e o limiar de Epsilon é a maneira mais comum de calcular o gráfico de vizinhança que ele usa.

PS Sua pergunta não é muito precisa. Você se refere a matrizes de dados esparsas ou matrizes de similaridade esparsas ?

Anony-Mousse -Reinstate Monica
fonte
1
matrizes de dados esparsos
Zach
A maioria dos algoritmos pode operar em matrizes de dados esparsas. Por exemplo, AGNES, PAM, DBSCAN, OPTICS, CLARA, ...
Anony-Mousse -instala Monica
Não sei por que você respondeu, se você nem conhece R.
user3932000 31/07
Eu conheço R. Provavelmente até melhor do que o usuário médio de R. Conheço avaliação não padrão em R e sei que a maioria dos módulos é escrita em C; portanto, quando você passa uma matriz esparsa, ela é copiada primeiro em uma matriz sensorial antes de passá-la para o código real. E todo pacote usa uma maneira diferente de fazer isso ... Isso não é eficiente. Você não escolhe R se precisar de eficiência, boa integração ou compatibilidade com versões anteriores ou desenvolvimento coordenado.
Anony-Mousse -Reinstate Monica