F@N Ad-Tech Blog

株式会社ファンコミュニケーションズ nend・nex8・viidleのエンジニア・技術ブログ

Rで学ぶ推薦システム[part1 類似度]

こんにちは、サービス開発部 情報科学技術研究所の h_shinです。 Rで学ぶ推薦システム(recommendation system)について記事を書きたいと思います。

推薦システム(recommendation system)

data miningの知識がなくても、下記の図1を見ると誰に何をお勧めすればいいか理解できます。 推薦システム実装する際、とりあえず理解するべきは類似度の評価です。 商品に対しての評価((購入・レビュー・興味関心など)を元に類似度を計算し、新しい商品をお勧めします。 類似度がわかれば、ビジネスの知識を加えて推薦システムをつくれます。 ※Association Rulesについてもここで紹介しようと思いましたが、今度に。。

f:id:fan_h_shin:20170226104618p:plain

[図1. Collaborative_filtering]


User-based Collaborative Filtering

f:id:fan_h_shin:20170216170033p:plain

[図2. ©recommenderlab: A Framework for Developing and Testing Recommendation Algorithms by Michael Hahsler]


類似度が高いユーザーが高く評価した商品をお勧めします。 上記の図2.では類似度が高い3人(u4, u1, u3)の評価を活用してます。 ここでは類似度が高いユーザー3人が評価した商品の平均scoreで新しい商品が推薦されます。 つまり i2(4.0),i1(3.5),i7(2.0)順でお勧めされます。 3人の類似度はそれぞれ違いますので、類似度が高い場合はweightを高くする方法もあります。

Item-based Collaborative Filtering

f:id:fan_h_shin:20170216170851p:plain

[図3. ©recommenderlab: A Framework for Developing and Testing Recommendation Algorithms by Michael Hahsler]


ユーザーが高く評価した商品と類似度が高い商品をお勧めします。 図3.は商品類似度です。推薦の際は対象ユーザーが評価したi1, i5, i8と他の商品の間の類似度が使われてます。 類似度にweightを加えて計算した結果、i3(4.6)をお勧めする結果になります。

とりあえず結果を見る

Rのライブラリrecommenderlabを使って映画をお勧めします。
ここでは簡単に目を通して行きます

> library("recommenderlab")
> data("MovieLense") #映画の評価データ
> head(as(MovieLense,"data.frame"),3) #サンプルデータを確認
> 
> #user-based Collaborative Filtering
> as(predict(Recommender(MovieLense[2:300], method = "UBCF"), MovieLense[1], n=3),"list") 
$`1`
[1] "Heathers (1989)"                                                             "Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb (1963)"
[3] "Casablanca (1942)"                                                          

> 
> #item-based Collaborative Filtering
> as(predict(Recommender(MovieLense[2:300], method = "IBCF"), MovieLense[1], n=3),"list") 
$`1`
[1] "Boy's Life 2 (1997)" "Night Flier (1997)"  "Rosewood (1997)"    

MovieLense[2:300]データを活用してMovieLense[1]にお勧めする映画を確認してます。 recommenderlabように簡単に使えるライブラリがそれぞれのプログラミング言語でたくさんあります。

Rソースについて

  • iは商品、uはユーザーを表します。例(u1,u2,u3, i1,i2,i3)
  • Rソースにはu7に新しい商品を推薦する内容が含まれてます。
  • 理解しやすくするため、できるだけ推薦ロジックをシンプル化しました。

類似度評価方法の紹介

気づいたと思いますが、recommendation systemを構築する為には類似度を計算する必要があります。 実際にここで紹介する類似度評価方法だけでも、簡単なrecommendation systemを構築することはできますが、 実際に現場では必ずいろんな問題にぶつかると思います。

Euclidean distance(ユークリッド距離)

https://ja.wikipedia.org/wiki/ユークリッド距離

f:id:fan_h_shin:20170216143140j:plain

> u1 <- c(-4,-2,3,-4,5)
> u2 <- c(5,5,-5,4,-3)
> u3 <- c(-3,-1,1,-2,4)
> 評価matrix <- rbind(u1,u2,u3)
> colnames(評価matrix) <- paste("i", c(1:5), sep = "")
> 評価matrix
   i1 i2 i3 i4 i5
u1 -4 -2  3 -4  5
u2  5  5 -5  4 -3
u3 -3 -1  1 -2  4
> (euclidean_dist = dist(評価matrix ,method="euclidean"))
          u1        u2
u2 17.944358          
u3  3.316625 14.866069
> 
> #計算式
> (u1とu2の距離は <- sqrt(sum((u1-u2)^2)))
[1] 17.94436

Cosine similarity(コサイン類似度)

http://www.cse.kyoto-su.ac.jp/~g0846020/keywords/cosinSimilarity.html f:id:fan_h_shin:20170216145535p:plain

> library(lsa)
> u1 <- c(1,0,1,0,1)
> u2 <- c(0,0,1,0,1)
> u3 <- c(1,1,0,1,1)
> cosine(cbind(u1,u2,u3))
          u1        u2        u3
u1 1.0000000 0.8164966 0.5773503
u2 0.8164966 1.0000000 0.3535534
u3 0.5773503 0.3535534 1.0000000
> 
> #計算式
> (u1とu2の類似度は <- u1 %*% u2 / (sqrt(sum(u1^2))*sqrt(sum(u2^2))))
          [,1]
[1,] 0.8164966

Pearson correlation(相関係数)

https://ja.wikipedia.org/wiki/相関係数 f:id:fan_h_shin:20170216152738p:plain f:id:fan_h_shin:20170216152740j:plain

> u1 <- c(-4,-2,3,-4,5)
> u2 <- c(5,5,-5,4,-3)
> u3 <- c(-3,-1,1,-2,4)
> (pearsonCorrelation <- cor(cbind(u1,u2,u3), method="pearson"))
           u1         u2         u3
u1  1.0000000 -0.9184400  0.9660652
u2 -0.9184400  1.0000000 -0.8192657
u3  0.9660652 -0.8192657  1.0000000
> # 1は完全に一致する(positively correlated)
> # -1は完全に不一致 (negatively correlated)
> # 0は相関関係がない(decorrelation)
> 
> #計算式
> (u1とu2の類似度は <-cov(u1,u2) / (sd(u1) * sd(u2)))
[1] -0.91844

推薦システム実装

評価データ生成

> #評価データを作ります
> u1 <- c(NA, 4.0, 4.0, 2.0, 1.0, 2.0, NA, NA)
> u2 <- c(3.0, NA, NA, NA, 5.0, 1.0, NA, NA)
> u3 <- c(3.0, NA, NA, 3.0, 2.0, 2.0, NA, 3.0)
> u4 <- c(4.0, NA, NA, 2.0, 1.0, 1.0, 2.0, 4.0)
> u5 <- c(1.0, 1.0, NA, NA, NA, NA, NA, 1.0)
> u6 <- c(NA, 1.0, NA, NA, 1.0, 1.0, NA, 1.0)
#今回お勧めする対象のユーザー :u7
> u7 <- c(NA, NA, 4.0, 3.0, NA, 1.0, NA, 5.0) 
> scorematrix = rbind(u1,u2,u3,u4,u5,u6,u7)
> colnames(scorematrix) <- paste("i",c(1:8), sep = "")
> 
>#現場ではmissing valueがよくあるのでNAをたくさん入れます。
> scorematrix
   i1 i2 i3 i4 i5 i6 i7 i8
u1 NA  4  4  2  1  2 NA NA
u2  3 NA NA NA  5  1 NA NA
u3  3 NA NA  3  2  2 NA  3
u4  4 NA NA  2  1  1  2  4
u5  1  1 NA NA NA NA NA  1
u6 NA  1 NA NA  1  1 NA  1
u7 NA NA  4  3 NA  1 NA  5

missing valueの問題点

  • 問題点1。NAがあるので計算ができない
  • 問題点2。計算できるペアが少ない場合、類似度が高くなる問題(距離が近い)
> #問題点1。NAがあるので計算ができない
> sqrt(sum((scorematrix['u7',] - scorematrix['u6',])^2))
[1] NA
> #missing valueが無いペアを作る
> (na.idx <- is.na(scorematrix['u7',]) | is.na(scorematrix['u6',]))
   i1    i2    i3    i4    i5    i6    i7    i8 
 TRUE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE FALSE 
> (u7a  <- scorematrix['u7',][!na.idx])
i6 i8 
 1  5 
> (u6a  <- scorematrix['u6',][!na.idx])
i6 i8 
 1  1 
> 
> #問題点2。計算できるペアが少ない場合、類似度が高い(距離が近い)
> (euclideanDistance <- sqrt(sum((u7a - u6a)^2)))
[1] 4
> 
> #計算できるペアが少ない場合、類似度が強くなる問題が発生するのでNA比率を考慮した上でscaleする
> scaleX <- length(scorematrix['u7',]) / length(u7a)
> 
> #scaleされた結果
> euclideanDistance * scaleX
[1] 16

類似度を求める関数作成

get_dist <- function (v1, v2, method){
  #NA比率を考慮したscaleXを作る
  na.idx <- is.na(v1) | is.na(v2)
  v1a  <- v1[!na.idx]
  v2a  <- v2[!na.idx] 
  scaleX <- length(v1) / length(v1a)
  
  if(method =="euclidean")
    #euclideanのみ距離(dissimilarity)なので、1/euclideanDistanceする
    return(1/sqrt(sum((v1a - v2a)^2) * scaleX)) 
  if(method == "cosine")
    return(v1a %*% v2a / (sqrt(sum(v1a^2))*sqrt(sum(v2a^2)))/scaleX)
  if(method == "pearson") 
    return(cov(v1a,v2a) / (sd(v1a) * sd(v2a))/scaleX)
}

user-based collaborative filtering

> ユーザー類似度 <- cbind(
+ apply(scorematrix[1:6,],MARGIN = 1, FUN= function(x) get_dist(x,scorematrix['u7',],"euclidean")),
+ apply(scorematrix[1:6,],MARGIN = 1, FUN= function(x) get_dist(x,scorematrix['u7',],"cosine")),
+ apply(scorematrix[1:6,],MARGIN = 1, FUN= function(x) get_dist(x,scorematrix['u7',],"pearson"))
+ )
> colnames(ユーザー類似度) <- c("euclidean","cosine","pearson")
> #今回はInf, NA, NaNの処理とその説明は省略
> ユーザー類似度
    euclidean    cosine   pearson
u1 0.43301270 0.3602883 0.2834734
u2        Inf 0.1250000        NA
u3 0.27386128 0.3513656 0.3247595
u4 0.43301270 0.3734663 0.3682427
u5 0.08838835 0.1250000        NA
u6 0.12500000 0.2080126       NaN

> #Infがあると、corrplotでエラーが発生するため
> ユーザー類似度[is.infinite(ユーザー類似度) ]<-NA 
> #類似度の視覚化
> library("corrplot")
> corrplot(t(ユーザー類似度),  method = "number")

f:id:fan_h_shin:20170227113409p:plain

> #今回はcosine類似度計算でTop3を使う
> (類似度TOP3ユーザー = head(sort(ユーザー類似度[,"cosine"], decreasing = TRUE),3))
       u4        u1        u3 
0.3734663 0.3602883 0.3513656 
> 
> #未評価商品をおすすめする必要があると仮定する
> 未評価商品 <- scorematrix[,is.na(scorematrix['u7',])]
> (類似度TOP3ユーザーの評価 <- 未評価商品[names(類似度TOP3ユーザー),])
   i1 i2 i5 i7
u4  4 NA  1  2
u1 NA  4  1 NA
u3  3 NA  2 NA
> 
> #今回は簡単にmeanを求めてます。
> sort(colMeans(類似度TOP3ユーザーの評価,na.rm = TRUE), decreasing = TRUE)
      i2       i1       i7       i5 
4.000000 3.500000 2.000000 1.333333 
> #i2 > i1 > i7 > i5 順でおすすめするできる。

item-based collaborative filtering

> 
> #u7の評価が高い商品TOP3を使います。
> (評価商品TOP3 <- scorematrix[,names(head(sort(scorematrix['u7',],decreasing = TRUE),3))])
   i8 i3 i4
u1 NA  4  2
u2 NA NA NA
u3  3 NA  3
u4  4 NA  2
u5  1 NA NA
u6  1 NA NA
u7  5  4  3
> (未評価商品 <- scorematrix[,is.na(scorematrix['u7',])])
   i1 i2 i5 i7
u1 NA  4  1 NA
u2  3 NA  5 NA
u3  3 NA  2 NA
u4  4 NA  1  2
u5  1  1 NA NA
u6 NA  1  1 NA
u7 NA NA NA NA
> 
> #評価商品TOP3(i8, i3, i4)にたいして未評価商品との類似度を求めます。
> 商品類似度 <- cbind(
+   apply(未評価商品, MARGIN = 2, FUN= function(x) get_dist(x,評価商品TOP3[,"i8"],"cosine")),
+   apply(未評価商品, MARGIN = 2, FUN= function(x) get_dist(x,評価商品TOP3[,"i3"],"cosine")),
+   apply(未評価商品, MARGIN = 2, FUN= function(x) get_dist(x,評価商品TOP3[,"i4"],"cosine"))
+ )
> colnames(商品類似度) <- colnames(評価商品TOP3)
> library("corrplot")
> corrplot(t(商品類似度), method="number")

f:id:fan_h_shin:20170226121321p:plain

> 商品類似度weight反映 <- 商品類似度/rowSums(商品類似度,na.rm = TRUE)
> 商品評価点数 <- t(商品類似度weight反映) * 評価商品TOP3['u7',]
> 
> #i2 > i1 > i7 > i5順でお勧めできます。
> sort(colSums(商品評価点数,na.rm = TRUE), decreasing = TRUE)
      i2       i1       i7       i5 
4.250000 4.228003 4.000000 3.950348 

最後に

類似度は何を利用することが正しいか?

実験に基づいた評価では、Pearson coefficient が全般的に精度がいいと言われてます。 Cosine similarityはitem-based collaborative filteringで精度がいいと言われてます。 データの種類とビジネスモデルに合わせて、正しい類似度評価方法を使う必要があると思われます。

推薦システム構築における問題点について

今回は類似度を中心に説明しましたが、現場のデータで推薦システムを構築しようとすると データはsparseすぎるため、確実な類似度を見つけることが厳しいです。 そのためクラスタリング方法や他のデータマイニングスキルの知識が必要です。 また、ユーザーBiasを解決するための正規化した(Normalization) データを評価データとして活用する必要が出たりすると思います。

今後の記事について

次回は推薦システムを実装するための、必要なデータマイニングスキルについて説明したいと思います。

References

recommenderlab.pdf
Building a Recommendation System With R by Suresh K. Gorakala
http://journocode.com/2016/03/10/similarity-and-distance-part-1/