Algoritma pengelompokan yang beroperasi pada matriks data yang jarang [ditutup]

18

Saya mencoba menyusun daftar algoritma pengelompokan yang:

  1. Diimplementasikan dalam R
  2. Beroperasi pada matriks data jarang (bukan (dis) matriks kesamaan), seperti yang dibuat oleh fungsi matriks sparse .

Ada beberapa pertanyaan lain pada CV yang membahas konsep ini, tetapi tidak satupun dari mereka yang terhubung ke paket R yang dapat beroperasi langsung pada matriks jarang:

  1. Mengelompokkan dataset besar dan jarang
  2. Clustering data biner jarang dimensi tinggi
  3. Mencari implementasi clustering yang jarang dan berdimensi tinggi
  4. Pengelompokan yang efisien ruang

Sejauh ini, saya telah menemukan tepat satu fungsi dalam R yang dapat mengelompokkan matriks jarang:

skmeans : kmeans bola

Dari paket skmeans . km berarti menggunakan jarak kosinus . Beroperasi pada objek dgTMatrix. Menyediakan antarmuka untuk algoritma k-means genetik, pclust, CLUTO, gmeans, dan kmndirs.

Contoh:

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

Algoritme berikut mendapatkan menyebutkan terhormat: mereka tidak cukup algoritma pengelompokan, tetapi beroperasi pada matriks jarang.

apriori : asosiasi aturan penambangan

Dari paket arules . Beroperasi pada objek "transaksi", yang dapat dipaksakan dari objek ngCMatrix. Dapat digunakan untuk membuat rekomendasi.

contoh:

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 jarang

Dari paket irlba . Apakah SVD pada matriks jarang. Dapat digunakan untuk mengurangi dimensi matriks jarang sebelum pengelompokan dengan paket R tradisional.

contoh:

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 : Pengelompokan Propagasi Afinitas

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

Apa fungsi lain di luar sana?

Zach
sumber
Apakah maksud Anda jarang seperti pada "banyak nol" atau seperti "banyak nilai yang hilang"?
Cbeleites mendukung Monica
Pertanyaan ini tampaknya di luar topik menurut beberapa kriteria di stats.stackexchange.com/help/dont-ask : setiap jawaban akan sama-sama valid, Anda mengharapkan lebih banyak jawaban selain dari yang disediakan, dan tidak ada masalah aktual untuk menjadi terpecahkan.
Whuber
Saya menyadari ini sudah ditutup, tetapi saya telah tersandung semua pertanyaan Anda tentang ini ketika saya menelusuri SO karena saya memiliki masalah yang sama;) Saya menemukan perpustakaan ini yang menggunakan kecenderungan afinitas yang dapat bekerja dengan matriks jarang: bioinf.jku.at / software / apcluster
MarkeD
1
@ MarkeD, terima kasih banyak! Ini rekomendasi perangkat lunak yang benar-benar buruk di luar topik di sini, karena saya telah menemukan tempat lain untuk meminta mereka.
Zach
3
sekali lagi pertanyaan yang sangat berguna ditutup :( jika Anda tidak tahu jawabannya, jangan memilih untuk menutup!
MonsterMMORPG

Jawaban:

1

Saya tidak menggunakan R. Sering sangat lambat dan hampir tidak memiliki dukungan pengindeksan. Namun rekomendasi perangkat lunak dianggap di luar topik.

Perhatikan bahwa banyak algoritma tidak peduli bagaimana Anda menyimpan data Anda. Jika Anda lebih suka memiliki matriks yang jarang, itu harus menjadi pilihan Anda, bukan pilihan algoritma.

Orang yang menggunakan terlalu banyak R cenderung terjebak dalam pemikiran dalam operasi matriks (karena itu adalah satu-satunya cara untuk menulis kode cepat dalam R). Tetapi itu adalah cara berpikir yang terbatas. Misalnya k-means: tidak peduli. Secara khusus, itu tidak menggunakan jarak berpasangan sama sekali. Itu hanya perlu cara untuk menghitung kontribusi varians; yang setara dengan menghitung jarak Euclidean kuadrat.

Atau DBSCAN. Yang dibutuhkan hanyalah predikat "tetangga". Ini dapat bekerja dengan grafik yang berubah-ubah; hanya saja jarak Euclidean dan ambang Epsilon adalah cara paling umum untuk menghitung grafik lingkungan yang digunakannya.

PS Pertanyaan Anda tidak terlalu tepat. Apakah Anda merujuk ke matriks data jarang atau matriks kesamaan jarang ?

Anony-Mousse -Reinstate Monica
sumber
1
matriks data jarang
Zach
Sebagian besar algoritma dapat beroperasi pada matriks data yang jarang. Misalnya, AGNES, PAM, DBSCAN, OPTICS, CLARA, ...
Anony-Mousse -Reinstate Monica
Tidak yakin mengapa Anda bahkan menjawab jika Anda bahkan tidak tahu R.
user3932000
Saya tahu R. Mungkin bahkan lebih baik daripada pengguna R rata-rata. Saya tahu evaluasi non-standar dalam R dan saya tahu bahwa sebagian besar modul ditulis dalam C, jadi ketika Anda melewati matriks jarang, pertama-tama disalin ke dalam matriks indera sebelum meneruskannya ke kode aktual. Dan setiap paket menggunakan cara yang berbeda untuk melakukannya ... Itu tidak efisien. Anda tidak memilih R jika Anda membutuhkan efisiensi atau integrasi yang baik atau kompatibilitas mundur atau pengembangan terkoordinasi.
Anony-Mousse -Reinstate Monica