[R] 各種相似性(Similarity) 演算法實作

圖片來源：http://blog.comsysto.com/2013/04/03/background-of-collaborative-filtering-with-mahout/

在推薦系統或是文字探勘中，常常會需要比較兩個人或兩篇文章的相似性，相似性有許多種測量的方式，每種測量方式都有它的特性和適用的地方，本篇文章用R來實作並簡單比較幾種常用到的相似性．

Euclidean Distance

測量兩點之間的直線距離

sim_Eu <- function(x,y){
  sqrt((x-y) %*% (x-y))
}

sim_Eu(x,y) #11.18
sim_Eu(x,z) #6.32
sim_Eu(y,z) #12.85
sim_Eu(x,x1) #95
sim_Eu(x,x) #0

Manhattan Distance

在街區中間，兩點之間無法直線前進，只能透過街角轉彎前進，測量的是直角距離

sim_man <- function(x,y){
  sum(abs(x-y))
}

sim_man(x,y) #25
sim_man(x,z) #12
sim_man(y,z) #25
sim_man(x,x1) #95
sim_man(x,x) #0

Chebyshev Distance

西洋棋中，Ａ到Ｂ點最遠的步伐數

sim_che <- function(x,y){
  max(abs(x-y))
}

sim_che(x,y) #5
sim_che(x,z) #4
sim_che(y,z) #9
sim_che(x,x1) #95
sim_che(x,x) #0

Minkowski Distance

當p為1是曼哈頓距離，p為二是歐式距離，p無窮大時近似切比雪夫距離

sim_min <- function(x, y, p) {
  sum(abs(x-y) ** p) ** (1/p)
}

Pearsen’s r

測量兩組變量之間的相關性，值域介於1~-1 數字越接近1和-1，表示兩組數字越相關，正值為正相關，負值為負相關．

sim_pear <- function(x, y) {
  (((x - mean(x)) %*% (y - mean(y)))) / 
    (sqrt((x - mean(x)) %*% (x - mean(x))) * 
       sqrt((y - mean(y)) %*% (y - mean(y))))
}

sim_pear(x,y) #1
sim_pear(x,z) #-1
sim_pear(y,z) #-1
sim_pear(x,x1) #0.725
sim_pear(x,x) #1

cosine similarity

測量兩組向量之間夾角的大小，數值也介於1~-1之間．

sim_cos <- function(x, y) {
  x %*% y / (sqrt(x %*% x) * sqrt(y %*% y))  
}

sim_cos(x,y) #0.96
sim_cos(x,z) #0.64
sim_cos(y,z) #0.82
sim_cos(x,x1) #0.71
sim_cos(x,x) #1

adjusted cosine similarity

透過除以平均數，可以測量兩組數字的方向性

sim_acos <- function(x, y) {
  x <- x - mean(x)
  y <- y - mean(y)
  x %*% y / (sqrt(x %*% x) * sqrt(y %*% y))  
}

sim_acos(x,y) #1
sim_acos(x,z) #-1
sim_acos(y,z) #-1
sim_acos(x,x1) #0.72
sim_acos(x,x) #1

總和比較

# 初始化幾個向量距離
x = c(1,2,3,4,5)
y = c(6,7,8,9,10)
z = c(5,4,3,2,1)
x1 = c(1,2,3,4,100) #放一個測量單位明顯不同的值

Pair	Euc	Man	Che	Pear	Cos
(x, y)	11.18	25	5	1	0.96
(x, z)	6.32	12	4	-1	0.64
(y, z)	12.85	25	9	-1	0.82
(x, x1)	95	95	95	0.725	0.71
(x, x)	0	0	0	1	1

前三種（Euc, Man. Che）測量的是距離，數字都大於0，對於不同單位的值的敏感度高（x , x1），但是測不出方向性；相反的Pearson r雖然能看得出方向性，但是看不出像是（x, y）的差異；cos對於不同單位標準的值敏感度較低．