メインコンテンツまでスキップ

サンプル間の類似性指標

推薦システムにおける対象同士の類似度を評価する研究についてまとめ。

  • アイテムやユーザーの類似性を測るための指標
  • 協調フィルタリングやK-NNで、『類似した』ユーザー・アイテムを見つける際に主に使う

古い指標​

Peason correlation​

  • いわゆる相関係数
  • -1〜+1までの値を取る
ρ=σXYσxσy=E[(X−E[X])(Y−E[Y])]E[(X−E[X])2]E[(Y−E[Y])2]\begin{aligned} \rho &= \frac{\sigma_{XY}}{\sigma_x \sigma_y} \\ &= \frac{E\bigl[ (X-E[X])(Y-E[Y]) \bigr]}{\sqrt{E[(X-E[X])^2]}\sqrt{E[(Y-E[Y])^2]}} \end{aligned}

cosine​

  • ベクトルAとベクトルBの角度のコサイン
  • -1~1までの値を取る
cosineSim=∑i=1naibi∑i=1nai2∑i=1nbi2cosineSim = \frac{\sum^n_{i=1} a_ib_i}{\sqrt{\sum^n_{i=1} a_i^2}\sqrt{\sum^n_{i=1} b_i^2}}

adjusted cosine​

  • ユーザーベースCF（協調フィルタリング）とアイテムベースCFの類似度計算の基本的な違いは、計算する方向が行か列か
  • アイテムベースの場合、cosineを使って類似度を計算するには一つの重大な欠陥がある
    • cosineは角度は反映するが、位置を問わない
  • Adjusted cosineは、各共評価ペアから対応するユーザーの平均値を差し引くことで、この欠点を相殺する
sim(i,j)=∑u∈U(Ru,i−Rˉ)(Ru,j−Rˉu)∑u∈U(Ru,i−Rˉu)2∑u∈U(Ru,j−Rˉu)2where  Rˉu:u番目のユーザーの平均評価\begin{aligned} sim(i,j) &= \frac{\sum_{u \in U}(R_{u,i}-\bar R)(R_{u,j}-\bar R_u)}{\sqrt{\sum_{u \in U}(R_{u,i}-\bar R_u)^2}\sqrt{\sum_{u \in U}(R_{u,j}-\bar R_u)^2}} \\ \text{where} \ \ \bar R_u&: \text{u番目のユーザーの平均評価} \end{aligned}

Euclidean​

  • ユークリッド距離

  • 類似度として評価するため、通常は正規化する

sim=1/(1+∑i=1n(pi−qi)2)sim = 1 / (1+\sqrt{\sum^n_{i=1}(p_i-q_i)^2})

Jaccard similarity​

  • グローバルな評価を対象にしている
  • 両ユーザーが評価した全てのアイテムのカーディナリティに対する評価のカーティナリティの割合
Sim(u,v)jaccard=(Iu∩Iv)Iu∪IvSim(u,v)^{jaccard} = \frac{(I_u \cap I_v)}{I_u \cup I_v}

Mean Square Distance​

  • 平均二乗距離は共評価項目の評価の差と共評価項目のカーディナリティの比で算出される
  • 平均二乗類似度は、1からMSDを差し引いて計算する
Sim(u,v)MSD=1−∑i∈I(u,v)(R(u,i)−R(v,i))2∣I(u,v)∣Sim(u,v)^{MSD} = 1 - \frac{\sum_{i\in I(u,v)}(R(u,i)-R(v,i))^2}{|I(u,v)|}

新しい指標​

JMSD​

  • MSDによる数値情報とJaccardによる非数値情報を組み合わせて計算
  • JaccardとMSDの部分的な類似度を計算し、これら２つの類似度測定値の乗算から生成される
Sim(u,v)JMSD=(Sim(u,v)Jaccard)(Sim(u,v)MSD)=((Iu∩Iv)Iu∪Iv)(∑i∈I(u,v)(R(u,i)−R(v,i))2∣I(u,v)∣)\begin{aligned} Sim_{(u,v)}^{JMSD} &= (Sim(u,v)^{Jaccard})(Sim(u,v)^{MSD}) \\ &=\Bigl( \frac{(I_u \cap I_v)}{I_u \cup I_v} \Bigr) \Bigl( \frac{\sum_{i\in I(u,v)}(R(u,i)-R(v,i))^2}{|I(u,v)|} \Bigr) \end{aligned}

SING​

  • メモリベース協調フィルタリングに特化した類似指標

  • 論文が公開されておらず（AbstractとReferencesしか公開されていない）

GEN​

  • 遺伝的アルゴリズムに基づいた類似性指標

  • CFベースの推薦システムの精度を向上させ、CFの結果を向上させるのが目的

simw(x,y)=1M−m+1∑i=0M−mwivx,yiwhere  m:評価の最小値（通常は1）M:評価の最大値（通常は5や10）v:2人の評価ベクトルの差w:推薦システムのMAEが最小となるような類似性関数の係数\begin{aligned} sim_w(x,y) &= \frac{1}{M-m+1}\sum^{M-m}_{i=0}w^{i}v^{i}_{x,y} \\ \text{where} \ \ m&: \text{評価の最小値（通常は1）} \\ M&: \text{評価の最大値（通常は5や10）}\\ v&: \text{2人の評価ベクトルの差} \\ w&: \text{推薦システムのMAEが最小となるような類似性関数の係数} \end{aligned}

  • 例

    • r_1 = (4, 5, x, 3, 2, x, 1, 1, 4)
    • r_2 = (4, 3, 1, 2, x, 3, 4, x, 2)の評価ベクトルを仮定
    • 評価の差はr_d = (0, 2, x, 1, x, x, 3, x, 2)
    • 評価の差の割合をカウントして、v = (1/5, 1/5, 2/5, 1/5, 0)となる（差が0の割合、差が1の割合、差が2の割合...）
    • wは(1, 0.5, 0, -0.5, -1)のいずれかを取る
      • 1なら非常に似ており、-1なら非常に似ていない
      • 0は、その評価の差が、類似性に関連しないと推定される

  • wは、システム全体のMAEを最小とするように、遺伝的アルゴリズムで学習する

TRUST​

  • ユーザーの信頼度を評価値データから得る
  • 論文が公開されておらず（AbstractとReferencesしか公開されていない）

古い指標の問題​

  • 例えば、U=(2, 0, 3, 0)とV=(5, 2, 0, 2)の評価ベクトルを考える
    • 両ユーザーがともに評価しているアイテムは1つのみ
    • ピアソンの類似度だと0になる
    • コサイン類似度だと1になる
  • U=(2, 1, 3, 2), V=(1, 2, 2, 3)などは似ているようだが、ピアソンの類似度は0
  • U=(2, 2, 0, 1), V=(4, 4, 0, 2)だと、コサイン類似度は1になる
    • 評価が複数ある場合、コサイン類似度は高くなりやすい
    • 1などのあまり重要でない評価値にひっぱられる
  • U=(5, 5, 1, 1), V=(1, 1, 5, 5)だと、Jaccardは非常に高い数値を出すが、実際には明らかに異なる
    • 評価の値を無視し、共評価の有無のみに注目すると情報を大量に捨てることになる