7

私は高次元の問題 (〜 4k 項) に取り組んでおり、(コサイン類似度によって) 最上位の k 類似を取得したいと考えており、ペアごとの計算を行う余裕がありません。

私のトレーニング セットは 600 万 x 4k マトリックスで、600k x 4k マトリックスの予測を行いたいと考えています。

600k x 4k マトリックスの各アイテムの k 類似アイテムを取得する最も効率的な方法は何ですか?

理想的には、600k x 10 のマトリックスを取得したいと考えています (つまり、600k の各アイテムの上位 10 個の類似アイテム)。

ps: SO Web サイトを調査したところ、ほぼすべての「R のコサイン類似性」の質問が参照されていることがわかりましたcosine_sim(vector1, vector2)。しかし、この質問はcosine_sim(matrix1, matrix2).

更新 次のコードは、単純な方法を使用して、テストセットの各行とトレーニング セットのすべての行の間のコサイン類似度を見つけます。

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

トレーニング用に 5000x200 マトリックス、テスト用に 2000x200 マトリックスで同じ関数を実行すると、380 秒以上かかりました。

理想的には、すべての行の類似性を計算する必要がないいくつかのアイデアを見たいと思っています。それが不可能な場合は、上記のコードをベクトル化する方法に関するいくつかの指針が役立ちます。

4

1 に答える 1

4

すべての行の類似度を計算する必要はありません。代わりにこれを使用できます：

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

trainテストデータ（マトリックスを縮小しました）

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)

結果：

> 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

完全な 5000 x 200trainマトリックスを使用するcoSim2と、7.8 秒で実行されます。

また、次の点に注意してください。

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

identical私の関数は、行 ID の double ではなく整数を返すため、使用できません。

于 2013-09-22T22:57:45.157 に答える