Как сгруппировать около 9000 последовательностей чисел, используя R?

Question

У меня есть CSV-файл, содержащий около 9000 числовых последовательностей, которые мне нужно кластеризовать. Первые 6 строк CSV выглядят так

id, sequence
"1","1 2"
"2","3 4 5 5 6 6 7 8 9 10 11 12 13 8 14 10 10 15 11 12 16"
"3","17 18 19 20 5 5 20 5 5"
"4","20 21"
"5","22 4 23 24 25 26"

Мой код R, который выполняет кластеризацию, выглядит следующим образом

seqsim <- function(seq1, seq2){
  seq1 <- as.character(seq1)
  seq2 <- as.character(seq2)
  s1 <- get1grams(seq1)
  s2 <- get1grams(seq2)
  intersection <- intersect(s1,s2)
  if(length(intersection)==0){
    return (1)
  }
  else{
    u <- union(s1, s2)
    score = length(intersection)/length(u)
    return (1-score)
  }  
}      
###############   
mydata <- read.csv("sequence.csv")
mydatamatrix <- as.matrix(mydata$sequence) 

# take the data in csv and create dist matrix    
rownames(mydatamatrix) <- mydata$id
distance_matrix <- dist_make(mydatamatrix, seqsim, "SeqSim (custom)")
clusters <- hclust(distance_matrix,  method = "complete")
plot(clusters)
clusterCut <- cutree(clusters, h=0.5)
# clustercut contains the clusterIDs assigned to each sequence or row of the input dataset    
# Number of members in each cluster
table(mydata$id,clusterCut)    
write.csv(clusterCut, file = "clusterIDs.csv")

Код работает для небольшого числа последовательностей, например около 900, но у меня возникают проблемы с памятью для больших наборов данных.

Мой вопрос: правильно ли я делаю кластеризацию? Существуют ли более быстрые и эффективные способы обработки кластеризации данных такого типа с использованием R? Функция seqsim фактически возвращает расстояние, а не сходство, потому что я возвращаю 1-балл. Seqsim вызывает другие методы, которые я пропустил, чтобы уменьшить длину кода.

Answer 1

Я подозреваю / предполагаю, что узким местом является расчет расстояния, а не кластеризация как таковая

Вот как я мог бы подойти к этому:

1. отделить обработку текста от вычисления расстояния (это предотвратит многократную обработку каждой строки)
2. используйте либо R dist используйте или используйте матричные операции для вычисления матрицы расстояний (которая является индексом jaccard).
3. Будьте осторожны, пытаясь собрать результаты кластеризации 9000 последовательностей, это наверняка будет невозможно расшифровать
4. Матрица 9000 x 9000 потребует много памяти, поэтому это может стать следующим узким местом, которое вам нужно преодолеть в зависимости от ресурсов памяти вашего компьютера.

Код:

library(arules)
df <- read.table(text='id, sequence
"1","1 2"
"2","3 4 5 5 6 6 7 8 9 10 11 12 13 8 14 10 10 15 11 12 16"
"3","17 18 19 20 5 5 20 5 5"
"4","20 21"
"5","22 4 23 24 25 26"', header=TRUE, sep=",")

seq <- lapply(df$sequence, get1grams) #I am assuming that get1grams produces a vector
names(seq) <- paste0("seq_", df$id)

seqTrans <- as(seq, "transactions") #create a transactions object
seqMat <- as(seqTrans, "matrix") #turn the transactions object into an incidence matrix each row represents a sequence and each column a 1gram each cell presence/absence of the 1gram
seqMat <- +(seqMat) #convert boolean to 0/1
j.dist <- dist(seqMat, method = "binary") #make use of base R's distance function

##Matrix multiplication to calculate the jaccard distance
tseqMat <- t(seqMat)
a <- t(tseqMat) %*% tseqMat
b <- t(matrix(rep(1, length(tseqMat)), nrow = nrow(tseqMat), ncol = ncol(tseqMat))) %*% tseqMat
b <- b - a
c <- t(b)
j <- as.dist(1-a/(a+b+c))

clusters <- hclust(j,  method = "complete")
plot(clusters)
clusterCut <- cutree(clusters, h=0.5)