「統計学関連なんでもあり」の過去ログ--- 048

No.22606　【Ｒ】　二重繰り返し処理の高速化　　【明石】　2018/09/01(Sat) 10:42

青木先生　様；

お忙しいところを失礼いたします，明石と申します。
毎々，ご丁寧なご教示をいただき，誠にありがとうございます。
改めて，御礼を申し上げます。

青木先生にご教示いただきたいことが出てきました。
何卒どうぞよろしくお願いいたします。

---------------------------

記事 No.22590 「繰り返し処理の高速化」では，ベクトル化を用いた，劇的な高速化のご教示をいただきました。
ありがとうございました。

今回は，二重繰り返し処理です。

例示データは，先生のサイトからお借りいたします。

http://aoki2.si.gunma-u.ac.jp/R/my-cor.html
単相関係数，偏相関係数，重相関係数を計算する

x <- matrix(c(	# 5ケース，4変数のデータ行列例（ファイルから読んでも良い）
	1,  5, 6, 4,
	2, 14, 5, 3,
	3,  3, 4, 2,
	4,  2, 6, 6,
	3,  4, 3, 5
), ncol=4, byrow=TRUE)

ここでは，相関係数行列を計算していますが，
今回，私がやりたいのは，ケース（行ベクトル）同士のコサイン類似度行列です。

以下，プログラムを作成しました。

x <- matrix(c(	# 5ケース，4変数のデータ行列例（ファイルから読んでも良い）
	1,  5, 6, 4,
	2, 14, 5, 3,
	3,  3, 4, 2,
	4,  2, 6, 6,
	3,  4, 3, 5
), ncol=4, byrow=TRUE)

nr <- nrow(x)
mx <- matrix(0,ncol=nr,nrow=nr)
diag(mx) <- 1

for(i in 1:(nr-1))　{
   for(j in (i+1):nr)　{
      s <- (x[i,] %*% x[j,]) / (sqrt(sum(x[i,]^2)) * sqrt(sum(x[j,]^2)))
      mx[i,j] <- s
      mx[j,i] <- s
   }
 }

> mx
          [,1]      [,2]      [,3]      [,4]      [,5]
[1,] 1.0000000 0.8438196 0.9183979 0.8735555 0.8992005
[2,] 0.8438196 1.0000000 0.7847512 0.5725026 0.7829858
[3,] 0.9183979 0.7847512 1.0000000 0.9132886 0.9081355
[4,] 0.8735555 0.5725026 0.9132886 1.0000000 0.9229730
[5,] 0.8992005 0.7829858 0.9081355 0.9229730 1.0000000

私が扱いたいデータでは，
ケース数は，数千
属性数は，数百
ですので，高速化処理ができれば大変にありがたいです。

ご教示をいただければ，大変に助かります。
どうぞよろしくお願いいたします。

No.22607　Re: 【Ｒ】　二重繰り返し処理の高速化　　【青木繁伸】　2018/09/02(Sun) 11:31

二重 for-loop の内側で使われる x[i,] %*% x[j,] は，行ベクトルの積和ですから
for-loop なしの z <- x%*%t(x) です。

同じく，分母は sqrt(sum(x[i,]^2)) という積和の平方根ですから x%*%t(x) の対角要素の平方根です d <- sqrt(diag(z))。二重 for-loop で使われる sqrt(sum(x[i,]^2)) * sqrt(sum(x[j,]^2)) は，d2 <- outer(d, d) です。
以上をまとめて，ループなしで答えが求まります。
z <- x%*%t(x)
d <- sqrt(diag(z))
d2 <- outer(d, d)
mx2 <- z / d2
5000x500の行列だと，私のマシンではfor-loop プログラムは約400秒，ベクトル演算を使ったプログラムは約10秒で，およそ40倍速くなります

No.22608　Special Thanks !（Re: 【Ｒ】　二重繰り返し処理の高速化）　　【明石】　2018/09/02(Sun) 12:24

青木先生　様；

お忙しいところを失礼いたします，明石と申します。

劇的な改善方法をご教示をいただき，誠にありがとうございます。

表層的ではなく，計算の本質を見抜くことの重要性を教えていただきました。

心から，心より，御礼を申し上げます。
本当にありがとうございました。