Как сгруппировать около 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

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

Вот как я бы подошел к этому:

1. разделитьобработка текста из расчета расстояния (это предотвратит многократную обработку каждой строки)
2. используйте либо функцию R's dist, либо используйте матричные операции для вычисления матрицы расстояния (которая является индексом jaccard *)1012 *).
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)