Làm cách nào để truy xuất hiệu quả các vectơ K-tương tự bằng cách tương tự cosin bằng R?

Question

Tôi đang làm việc trên một vấn đề cao (~ 4k điều khoản) và muốn lấy đầu k-tương tự (bằng sự tương tự cosin) và không thể đủ khả năng để làm một tính toán đôi khôn ngoan.

Bộ đào tạo của tôi là ma trận 6million x 4k và tôi muốn đưa ra dự đoán cho ma trận 600k x 4k.

Cách hiệu quả nhất để truy xuất các mục tương tự k cho mỗi mục trong ma trận 600k x 4k của tôi là gì?

Lý tưởng nhất, tôi muốn có ma trận 600k x 10 (nghĩa là các mục 10 hàng tương tự cho mỗi mục 600k).

ps: Tôi đã nghiên cứu trang web SO và tìm thấy gần như tất cả các câu hỏi "tương tự cosin trong R" tham chiếu đến cosine_sim(vector1, vector2). Nhưng câu hỏi này đề cập đến cosine_sim(matrix1, matrix2).

Cập nhật Các mã sau đây sử dụng một phương pháp ngây thơ để tìm ra sự tương đồng cosin giữa mỗi hàng trong testset và mỗi dòng trong tập huấn luyện.

set.seed(123) 
train<-matrix(round(runif(30),0),nrow=6,ncol=5) 
set.seed(987) 
test<-matrix(round(runif(20),0),nrow=4,ncol=5) 
train 

[1,] 0 1 1 0 1  
[2,] 1 1 1 1 1  
[3,] 0 1 0 1 1  
[4,] 1 0 1 1 1  
[5,] 1 1 0 1 0  
[6,] 0 0 0 1 0 

test 

[1,] 0 1 1 0 0 
[2,] 1 0 1 0 1 
[3,] 1 0 0 0 0 
[4,] 1 0 0 1 1 

coSim<-function(mat1, mat2, topK){ 
require(plyr) 
#mat2: is the testset 
#mat1: is the training set. We will find cosine similarity between each row in testset and every row in trainingset. 
#topK: user-input. for each row in testset we will return 'topk' similar rows(index) from the testset 

#set up an empty result matrix. nrow(result) will be the same as the cartesian product between mat1 & mat2. 
result<-matrix(rep(NA, nrow(mat1)*nrow(mat2)), nrow=nrow(mat1)*nrow(mat2), ncol=3) 
k=1 
for(i in 1:nrow(mat2)){ 
    for(j in 1:nrow(mat1)){ 
    result[k,1]<-i 
    result[k,2]<-j 
    result[k,3]<-crossprod(mat1[j,], mat2[i,])/sqrt(crossprod(mat1[j,]) * crossprod(mat2[i,])) 
    k<-k+1 
     } 
    } 
#sort the result matrix by cosine similarity found for each row in testset. not sure how to keep topK from each group so convert to df 
result<-as.data.frame(result) 
colnames(result)<-c("testRowId", "trainRowId","CosineSimilarity") 
result<-ddply(result, "testRowId", function(x) head(x[order(x$CosineSimilarity, decreasing = TRUE) , ], topK)) 
resultMat<-matrix(result$trainRowId, nrow=nrow(mat2), ncol=topK,byrow=T) 
finalResult<-list(similarity=result, index=resultMat) 
} 

system.time(cosineSim<-coSim(train, test, topK=2)) #0.12 secs 
cosineSim 
$similarity 
    testRowId trainRowId CosineSimilarity 
1   1   1  0.8164966 
2   1   2  0.6324555 
3   2   4  0.8660254 
4   2   2  0.7745967 
5   3   5  0.5773503 
6   3   4  0.5000000 
7   4   4  0.8660254 
8   4   2  0.7745967 

$index 
    [,1] [,2] 
[1,] 1 2 
[2,] 4 2 
[3,] 5 4 
[4,] 4 2 


set.seed(123) 
train<-matrix(round(runif(1000000),0),nrow=5000,ncol=200) 
set.seed(987) 
test<-matrix(round(runif(400000),0),nrow=2000,ncol=200) 
system.time(cosineSim<-coSim(train, test, topK=50)) #380secs 

Khi tôi chạy cùng chức năng với ma trận 5000x200 để đào tạo và ma trận 2000x200 để thử nghiệm, nó mất hơn 380 giây.

Lý tưởng nhất, tôi muốn xem một số ý tưởng mà tôi không phải tính toán sự giống nhau giữa mỗi hàng. Nếu điều đó là không thể, một số gợi ý về cách vectơ mã trên sẽ hữu ích.

Answer 1

Không cần tính toán sự giống nhau cho mỗi hàng. Bạn có thể sử dụng thay vì:

coSim2<-function(mat1, mat2, topK){ 
    #similarity computation: 

    xy <- tcrossprod(mat1, mat2) 
    xx <- rowSums(mat1^2) 
    yy <- rowSums(mat2^2) 
    result <- xy/sqrt(outer(xx,yy)) 

    #top similar rows from train (per row in test): 

    top <- apply(result, 2, order, decreasing=TRUE)[1:topK,] 
    result_df <- data.frame(testRowId=c(col(top)), trainRowId=c(top)) 
    result_df$CosineSimilarity <- result[as.matrix(result_df[,2:1])] 
    list(similarity=result_df, index=t(top)) 
} 

dữ liệu thử nghiệm (tôi đã giảm ma trận train của bạn)

set.seed(123) 
train<-matrix(round(runif(100000),0),nrow=500,ncol=200) 
set.seed(987) 
test<-matrix(round(runif(400000),0),nrow=2000,ncol=200) 

Kết quả:

> system.time(cosineSim<-coSim(train, test, topK=50)) #380secs 
    user system elapsed 
    41.71 1.59 43.72 

> system.time(cosineSim2<-coSim2(train, test, topK=50)) #380secs 
    user system elapsed 
    0.46 0.02 0.49 

Sử dụng đầy đủ 5000 x 200 train ma trận của bạn, coSim2 chạy trong 7,8 giây.

Cũng lưu ý:

> any(cosineSim$similarity != cosineSim2$similarity) 
[1] FALSE 
> any(cosineSim$index != cosineSim2$index) 
[1] FALSE 

Bạn không thể sử dụng identical vì chức năng của tôi trả về số nguyên thay vì đôi cho các ID hàng.