2015年2月16日 星期一

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


在推薦系統或是文字探勘中,常常會需要比較兩個人或兩篇文章的相似性,相似性有許多種測量的方式,每種測量方式都有它的特性和適用的地方,本篇文章用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

西洋棋中,A到B點最遠的步伐數
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對於不同單位標準的值敏感度較低.