最高效的R余弦计算

我有两个向量值和一个向量向量，我需要计算余弦相似度。由于复杂的原因，我一次只能计算一对余弦。但我必须做好几百万次。最高效的R余弦计算

cosine_calc <- function(a,b,wts) { 
    #scale both vectors by the weights, then compute the cosine of the scaled vectors 
    a = a*wts 
    b = b*wts 
    (a %*% b)/(sqrt(a%*%a)*sqrt(b%*%b)) 
}

的作品，但我想尝试更好地表现出来。

实施例的数据：

a = c(-1.2092420, -0.7053822, 1.4364633, 1.3612304, -0.3029147, 1.0319704, 0.6707610, -2.2128987, -0.9839970, -0.4302205) 
b = c(-0.69042619, 0.05811749, -0.17836802, 0.15699691, 0.78575477, 0.27925779, -0.08552864, -1.31031219, -1.92756861, -1.36350112) 
w = c(0.26333839, 0.12803180, 0.62396023, 0.37393705, 0.13539926, 0.09199102, 0.37347546, 1.36790007, 0.64978409, 0.46256891) 
> cosine_calc(a,b,w)[,1] 
[1,] 0.8390671

此question指出有R中可用的其他预定义的余弦函数，但没有关于它们的相对效率说。

来源

2011-11-16 ansate

只能够做到这一点，在一次一对将是一个主要的瓶颈...... –

我不想打破它给你，但在我的经验中，R似乎没有所要构建表现（相对而言）。如果这些数据来自关系数据库，那么您可能需要考虑计算其中的相似性，然后将其导出到R.我使用R的大部分数据都是小规模分析（即，在我完成了大量聚合）并生成图形。 – 2011-11-16 21:42:01

为什么你不要继续和基准http://stackoverflow.com/questions/2535234/find-cosine-similarity-in-r/2536149#2536149中列出的例子（即你链接的问题; @JoshUlrich显示你如何在他的答案），并为自己看？ –

您使用的所有函数都是.Primitive（因此已经直接调用编译好的代码），所以除了用优化的BLAS重新构建R之外，很难找到一致的速度增益。随着中说，这里是一个选项，它可能会为大载体更快：

cosine_calc2 <- function(a,b,wts) { 
    a = a*wts 
    b = b*wts 
    crossprod(a,b)/sqrt(crossprod(a)*crossprod(b)) 
} 

all.equal(cosine_calc1(a,b,w),cosine_calc2(a,b,w)) 
# [1] TRUE 

# Check some timings 
library(rbenchmark) 
# cosine_calc2 is slower on my machine in this case 
benchmark(
    cosine_calc1(a,b,w), 
    cosine_calc2(a,b,w), replications=1e5, columns=1:4) 
#     test replications user.self sys.self 
# 1 cosine_calc1(a, b, w)  100000  1.06  0.02 
# 2 cosine_calc2(a, b, w)  100000  1.21  0.00 

# but cosine_calc2 is faster for larger vectors 
set.seed(21) 
a <- rnorm(1000) 
b <- rnorm(1000) 
w <- runif(1000) 
benchmark(
    cosine_calc1(a,b,w), 
    cosine_calc2(a,b,w), replications=1e5, columns=1:4) 
#     test replications user.self sys.self 
# 1 cosine_calc1(a, b, w)  100000  3.83  0 
# 2 cosine_calc2(a, b, w)  100000  2.12  0

UPDATE：

剖析表明，相当多的时间花费在权重向量每个向量乘以。

> Rprof(); for(i in 1:100000) cosine_calc2(a,b,w); Rprof(NULL); summaryRprof() 
$by.self 
      self.time self.pct total.time total.pct 
*     0.80 45.98  0.80  45.98 
crossprod   0.56 32.18  0.56  32.18 
cosine_calc2  0.32 18.39  1.74 100.00 
sqrt    0.06  3.45  0.06  3.45 

$by.total 
      total.time total.pct self.time self.pct 
cosine_calc2  1.74 100.00  0.32 18.39 
*     0.80  45.98  0.80 45.98 
crossprod   0.56  32.18  0.56 32.18 
sqrt    0.06  3.45  0.06  3.45 

$sample.interval 
[1] 0.02 

$sampling.time 
[1] 1.74

如果您可以在调用函数数百万次之前进行加权，它可以为您节省相当多的时间。使用小矢量的cosine_calc3比原始函数稍快。字节编译函数应该给你另一个边际加速。

cosine_calc3 <- function(a,b) { 
    crossprod(a,b)/sqrt(crossprod(a)*crossprod(b)) 
} 
A = a*w 
B = b*w 
# Run again on the 1000-element vectors 
benchmark(
    cosine_calc1(a,b,w), 
    cosine_calc2(a,b,w), 
    cosine_calc3(A,B), replications=1e5, columns=1:4) 
#     test replications user.self sys.self 
# 1 cosine_calc1(a, b, w)  100000  3.85  0.00 
# 2 cosine_calc2(a, b, w)  100000  2.13  0.02 
# 3 cosine_calc3(A, B)  100000  1.31  0.00

来源

2011-11-16 21:43:23

我读的结果正确吗？ 1,000次输入100,000次需要3秒钟？似乎很难相信这可能是某人代码中的瓶颈！ – hadley

最高效的R余弦计算

回答

相关问题