Pythonでレコメンドシステムを作る(アイテムベース協調フィルタリング)

今回もお寿司データセットを使って、推薦システムを作ります。

www.kamishima.net

前回と同様、上記サイトのAll Data Setからsushi3-2016.zipをダウンロード・展開して、sushi3b.5000.10.scoreファイルをpythonファイルと同じディレクトリにコピーしておきます。

import numpy as np


scores = np.loadtxt('sushi3b.5000.10.score', delimiter=' ')

print('scores.shape: {}'.format(scores.shape))
# scores.shape: (5000, 100)

print('scores[0]:\n{}'.format(scores[0]))
# scores[0]:
# [-1.  0. -1.  4.  2. -1. -1. -1. -1. -1. -1. -1.  1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1.  1. -1. -1. -1. -1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1.  4. -1.  2. -1. -1. -1. -1. -1. -1.  0. -1. -1. -1. -1.
#  -1. -1.  0. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.  2. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.]

アイテムベース協調フィルタリング

前回は、類似したユーザの評価値を基に評価値を予測するユーザベース協調フィルタリングを実装しました。

今回は、協調フィルタリングのもう一つの代表的な手法であるアイテムベースの協調フィルタリングを実装します。
アイテムベース協調フィルタリングは、ユーザではなく、評価が類似しているアイテムを探し、そのアイテムの評価値から未知のアイテムの評価値を予測する方法です。 ユーザベースと比較すると、一般的にアイテム数はユーザ数よりも少なく、増減の頻度も低いため、類似度の行列をバッチ的に前もって作成しておくことでオンライン環境でも現実的な時間で推薦アイテムを計算できるという利点があります。 このため、Amazon等の大規模なECサイトでも用いられています。

コサイン類似度

アイテム間の類似度を比較する方法として、コサイン類似度が使われます。

アイテムaとbのコサイン類似度は以下の式に表されます。 r_{u,a}はアイテムaに対するユーザuの評価値、\overline{r_u}はuの評価値の平均です。 なお、平均値で引いて-1(負の相関)〜+1(正の相関)となるように調整しています(通常のコサイン類似度はこの調整を行いません)。

類似度の計算処理を示します。

最初にmean_adjustmentで行毎に平均値で引いて補正します。 (平均値による減算処理を一括して行ってしまいます。)

後は素直にコサイン類似度を計算しています。 分子は内積、分母はL2ノルムの積のため、それぞれnumpy.dotnumpy.linarg.normで簡単に計算できます。

0番目のアイテム(エビ)と類似したアイテムを見てみますと、カニ(22番目)、甘エビ(9番目)、ボタンエビ(41番目)が並んでおり、納得できそうな結果になっています。 (この他にも、マグロと中トロと鉄火巻、イカとタコ、アジとイワシなどが類似度の高い組み合わせとなっていました。)

def mean_adjustment(scores):
    """
    行単位で平均値を引いて補正した行列を返す(NaNは0とする)
    """
    scores_nan = np.copy(scores)
    scores_nan[scores_nan < 0] = np.nan
    
    adjusted_scores = np.ndarray(shape=scores_nan.shape)
    for i, score in enumerate(scores_nan):
        adjusted_scores[i] = score - np.nanmean(score)
    
    return np.nan_to_num(adjusted_scores)


def get_cos_similarities(scores, target_item_index):
    """
    アイテム間のコサイン類似度を計算し、(アイテムのインデックス, 類似度)のタプルリストを類似度順にして返す
    """
    similarities = []
    # ユーザごとに平均値で補正し、アイテムを行(ユーザを列)に変換する
    items = mean_adjustment(scores).transpose()
    target_item = items[target_item_index]
    
    for i, item in enumerate(items):
        if i == target_item_index:
            continue
            
        similarity = np.dot(target_item, item.T) / (np.linalg.norm(target_item) * np.linalg.norm(item))
        similarities.append((i, similarity))
        
    return sorted(similarities, key=lambda s: s[1], reverse=True)
    
    
target_item_index = 0 # 0番目のアイテム(エビ)
    
similarities = get_cos_similarities(scores, target_item_index)

print('Similarities: {}'.format(similarities))
# Similarities: [(22, 0.074712607710488529), (9, 0.067591790210210778), (41, 0.061560317333338818), ...

評価値の予測

予測は以下の式で計算します。 iは評価したアイテムです。
なお、全てのアイテムから計算するのではなく、類似度の高い上位k個などというように絞ります。

続いてPythonでの実装です。 ここでは類似度の上位3個、かつ、類似度が0以上のアイテムのみを使って計算しています。

上で得られた類似度を使って、0番目のユーザのエビの評価値について予測すると、予測値は4となりました。 0番目のユーザが評価しており、かつ、エビと正の相関関係にあるのが、1つ(3番目のアイテム=イカ)しかなく、その評価値がそのまま使われる結果となりました。

def predict(scores, similarities, target_user_index):
    """
    評価の予測値を返す
    """
    numerator = 0.0
    denominator = 0.0
    k = 0
    
    target = scores[target_user_index]
    
    for similarity in similarities:
        # 類似度の高い順から5つのアイテムの評価値を使う
        if (k >= 5 or similarity[1] <= 0):
            break
        if (target[similarity[0]] < 0):
            continue
            
        numerator += similarity[1] * target[similarity[0]]
        denominator += similarity[1]
        k += 1
    
    return numerator / denominator if denominator != 0.0 else -1
        
    
target_user_index = 0 # 0番目のユーザ

print('Predict score: {}'.format(predict(scores, similarities, target_user_index)))
# Predict score: 4.0

ランキング

最後に全ての寿司ネタ100種類について評価値を予測し、ランキングにします。

0番目のユーザについては、0番目(エビ)、8番目(トロ)、9番目(甘エビ)、31番目(カツオ)、41番目(ボタンエビ)、53番目(とろサーモン)の評価が4と予測されており、これらをおすすめするのが良さそうです。

def rank_items(scores, target_user_index):
    """
    (アイテムのインデックス, 予測した評価値)のタプルリストを評価値降順で返す
    """
    ranking = []
    similarities_list = []
    
    # 寿司ネタ100種類について評価値を予測
    for i in range(100):
        if scores[target_user_index][i] >= 0:
            continue
        
        similarities =  get_cos_similarities(scores, i)
        
        predict_score = predict(scores, similarities, target_user_index)
        
        ranking.append((i, predict_score))
        
    return sorted(ranking, key=lambda r: r[1], reverse=True)


target_user_index = 0 # 0番目のユーザ

print('Ranking: {}'.format(rank_items(scores, target_user_index)))
# Ranking: [(0, 4.0), (8, 4.0), (9, 4.0), (31, 4.0), (41, 4.0), (53, 4.0), (5, 3.5194984228119655), 

情報推薦システム入門 -理論と実践-

情報推薦システム入門 -理論と実践-

Pythonでレコメンドシステムを作る(ユーザベース協調フィルタリング)

Python協調フィルタリングを実装して、お寿司を推薦するシステムを作ってみます。

データセット

今回は寿司ネタの嗜好評価を集めたSUSHI Preference Data Setsを使います。

5000人が寿司ネタ100種類に対して5段階で評価(欠測値有り)したデータセットで、以下で公開されています。

www.kamishima.net

まずはデータをロードします。
上記サイトのAll Data Setからsushi3-2016.zipをダウンロード・展開して、sushi3b.5000.10.scoreファイルをカレントディレクトリにコピーしておきます。

全体では5000行100列(5000人×寿司ネタ100種類)の構成となっており、各要素には評価値0〜4(値が大きいほど、好き)と、欠測値-1がセットされています。

import numpy as np

scores = np.loadtxt('sushi3b.5000.10.score', delimiter=' ')

print('scores.shape: {}'.format(scores.shape))
# scores.shape: (5000, 100)

print('scores[0]: \n{}'.format(scores[0]))
# scores[0]: 
# [-1.  0. -1.  4.  2. -1. -1. -1. -1. -1. -1. -1.  1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1.  1. -1. -1. -1. -1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1.  4. -1.  2. -1. -1. -1. -1. -1. -1.  0. -1. -1. -1. -1.
#  -1. -1.  0. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.  2. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.]

ユーザベースの協調フィルタリング

あるユーザの評価が高くなりそうなアイテムを推薦するために、協調フィルタリングと呼ばれる手法が使われます。 これは、他のユーザのアイテムAの評価(既知)から、おすすめしたいユーザのアイテムAの評価(未知)を推定する方法です。 アイテムそのものの内容やユーザの属性などを必要としないため、多種多様な商品を販売するECサイトなどで使われています。

協調フィルタリングには、ユーザベースとアイテムベースの2つの代表的な方法がありますが、今回はユーザベースの方法を実装してみます。
ユーザベースの協調フィルタリングでは、対象の(おすすめしたい)ユーザと、評価が類似するユーザを探して、そのユーザの評価値から計算します。

相関係数

ユーザベースの協調フィルタリングで、ユーザ同士の評価が類似している度合い(類似度)を計算するために、ピアソンの積率相関係数が使われます。

ユーザaとユーザbの相関係数は以下の式で求まります。 r_{a,p}はユーザaのアイテムpに対する評価値で、 \overline{r_a}はユーザaの評価値の平均です。
相関係数は-1〜+1の値となり、-1が負の相関、+1が正の相関があることを表します。

f:id:ohke:20170917131724p:plain:w500

相関係数を求める実装を示します。

全ユーザのスコアをscores、予測したいユーザのインデックスをtarget_user_indexとして受け取り、ユーザのインデックスと類似度のタプルのリストを、類似度の高い順で返します。
類似度の計算にはnumpy.corrcoefを使っています。
また、共通のアイテムを3つ以上評価しているユーザのみを算出対象としています。 そうしないと、共通で評価しているアイテムが1つしかないのに、その1つの評価値が一致しただけで、類似度は1.0となってしまうためです。

0番目のユーザとその他のユーザで類似度を求めたところ、類似度が1.0となっているユーザが何人か発見できました。
186番目のユーザのスコアを見てみますと、4番目(イカ)、60番目(かんぴょう巻)、87番目(トビウオ)の値が完全に一致していることがわかります。

def get_correlation_coefficents(scores, target_user_index):
    similarities = []
    target = scores[target_user_index]
    
    for i, score in enumerate(scores):
        # 共通の評価が少ない場合は除外
        indices = np.where(((target + 1) * (score + 1)) != 0)[0]
        if len(indices) < 3 or i == target_user_index:
            continue
        
        similarity = np.corrcoef(target[indices], score[indices])[0, 1]
        if np.isnan(similarity):
            continue
    
        similarities.append((i, similarity))
    
    return sorted(similarities, key=lambda s: s[1], reverse=True)


target_user_index = 0 # 0番目のユーザ
similarities = get_correlation_coefficents(scores, target_user_index)

print('Similarities: {}'.format(similarities))
# Similarities: [(186, 1.0), (269, 1.0), (381, 1.0), ...

print('scores[186]:\n{}'.format(scores[186]))
# scores[186]:
# [-1. -1. -1.  4. -1. -1. -1.  2. -1.  3. -1. -1. -1. -1. -1. -1.  4. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.  4. -1.
#  -1. -1.  4. -1. -1. -1. -1. -1. -1. -1. -1.  1. -1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1. -1. -1.  2. -1. -1. -1.  2. -1. -1. -1. -1. -1. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.  2. -1. -1.
#  -1. -1. -1. -1. -1. -1. -1. -1. -1. -1.]

予測

次に相関係数から、ユーザaのアイテムpに対する評価値を予測する式を示します。
Nはユーザ数ですが、全てのユーザと比較するのではなく、類似度の高いユーザからN人、あるいは、類似度が閾値以上のユーザN人というように絞り込みます。

実装では、全スコアscoresと先程の計算で得られた類似度similarities、予測したいユーザのインデックスtarget_user_indexとアイテムのインデックスtarget_item_indexをそれぞれ渡し、スコアを予測します。
類似度が0より大きく、かつ、類似度の高い上位5人のユーザの評価値のみを使って、計算します。

0番目のユーザの0番目のアイテム(エビ)の評価を予測すると、2.761となりました。

def predict(scores, similarities, target_user_index, target_item_index):
    target = scores[target_user_index]
    
    avg_target = np.mean(target[np.where(target >= 0)])
    
    numerator = 0.0
    denominator = 0.0
    k = 0
    
    for similarity in similarities:
        # 類似度の上位5人の評価値を使う
        if k > 5 or similarity[1] <= 0.0:
            break
            
        score = scores[similarity[0]]
        if score[target_item_index] >= 0:
            denominator += similarity[1]
            numerator += similarity[1] * (score[target_item_index] - np.mean(score[np.where(score >= 0)]))
            k += 1
            
    return avg_target + (numerator / denominator) if denominator > 0 else -1


target_item_index = 0 # 3番目のアイテム(エビ)

print('Predict score: {:.3f}'.format(predict(scores, similarities, target_user_index, target_item_index)))
# Predict score: 2.761

ランキング

最後に予測される評価値が高い順にランキングを生成します。 実利用では、このランキングの順番でユーザにおすすめすることになります。

0番目のユーザには、92番目(キャビア)、61番目(ネギトロ巻き)、0番目(エビ)のアイテムを薦めると良さそうということがわかります。
この結果に対する考察は難しいところですが、ユーザ0は納豆巻(58番目のアイテム)の評価が高い(4)ので、ネギトロ巻きもなんとなく大丈夫そうです。
一方で、いくら(6番目)やとびっこ(42番目)などの魚卵系の寿司ネタに対する評価がない中、キャビアを薦めるのはギャンブルにも思えます。

def rank_items(scores, similarities, target_user_index):
    rankings = []
    target = scores[target_user_index]
    # 寿司ネタ100種類の全てで評価値を予測
    for i in range(100):
        # 既に評価済みの場合はスキップ
        if target[i] >= 0:
            continue

        rankings.append((i, predict(scores, similarities, target_user_index, i)))
        
    return sorted(rankings, key=lambda r: r[1], reverse=True)


target_user_index = 0 # 0番目のユーザ

rank = rank_items(scores, similarities, target_user_index)
print('Ranking: {}'.format(rank))
# Ranking: [(92, 2.8500000000000001), (61, 2.7935924227841857), (0, 2.7609467700985615), ...

情報推薦システム入門 -理論と実践-

情報推薦システム入門 -理論と実践-

scikit-learnでスパムメッセージを分類する(TfidfVectorizer + PorterStemmer + BernoulliNB)

前回に引き続き、今回も↓のデータセットを使って、スパムメッセージの分類を行います。

UCI Machine Learning Repository: SMS Spam Collection Data Set
SMS Spam Collection Dataset | Kaggle

TF-IDF

scikit-learnでは、前回使ったCountVectorizer以外に、TF-IDFで特徴量を抽出するTfidfVectorizerが提供されています。

TF-IDFはBag-of-Wordsで得られたベクトルから、以下の計算式で抽出される特徴量です。 tf(w,d)は学習サンプル(文書)dの中で語wが現れる回数、Nは学習サンプル数(文書数)、N_wは語wが現れる学習サンプル数(文書数)です。

tfidf(w, d) = tf(w, d)×\log(\frac{N+1}{N_w+1})+1

つまり、TF-IDFは「ある文書内での出現頻度が高く、かつ、他の文書での出現頻度が低い」語に高い重要度を与えるように重み付けを行う方法です。 たくさんの文書で使われている語は、文書の特徴を表しにくいために、重み付けを小さくする方法とも言い換えられます。
TF-IDFについてはこちらの方の記事が参考になります。

TF-IDFで文書内の単語の重み付け | takuti.me

学習データを使ってfitさせてみますと、"Are you wet right now?“は、0.36、0.22、0.66、0.51、0.33の重みとなっていることがわかります。 また、よく使われるであろう"you"には小さい値、逆に使われる頻度が低いであろう"wet"には大きい値が割り当てられています。 オプションnormでL2正則化を指定しているので、二乗して総和すると1になることも確認できます。

import pandas as pd
pd.set_option("display.max_colwidth", 1000)
from sklearn.model_selection import train_test_split
from sklearn.feature_extraction.text import TfidfVectorizer

# CSVからDataFrameへロード
original_df = pd.read_csv('spam.csv', encoding='latin-1')
# ゴミカラムの除去
original_df.drop(['Unnamed: 2', 'Unnamed: 3', 'Unnamed: 4'], axis=1, inplace=True)

# 文章と目的変数(スパムならば1)を抽出
X = pd.DataFrame(original_df['v2'])
y = original_df['v1'].apply(lambda s: 1 if s == 'spam' else 0)

# 学習データとテストデータを1:9で分割
X_train, X_test, y_train, y_test = train_test_split(X, y, train_size=0.1, random_state=6)

# TfidfVectorizerをL2正則で初期化・学習
vectorizer = TfidfVectorizer(norm='l2')
vectorizer.fit(X_train['v2'])

# 1つを取り出して変換させてみる
print(X_train.ix[X_train.index[0], 'v2'])
# Are you wet right now?
print(vectorizer.transform(X_train.ix[X_train.index[0]]))
#   (0, 2295)  0.223346777887
#   (0, 2206)  0.665796698325
#   (0, 1664)  0.514782102841
#   (0, 1387)  0.334883227937
#   (0, 267)   0.360116069549
print(vectorizer.vocabulary_)
# {'are': 267, 'you': 2295, 'wet': 2206, 'right': 1664, 'now': 1387, ...

TfidfVectorizerを使って、前回同様BernoulliNBで分類させてみます。

TfidfVectorizerでもmin_dfオプションが用意されており、今回はmin_dfに3を指定しています。
結果を見ると、学習データにおいてはCountVectorizerで得られた精度98.2%より低い97.5%でしたが、テストデータにおいては97.0%をマークし、CountVectorizerの精度よりも0.3%だけ上回りました。

from sklearn.naive_bayes import BernoulliNB

# TfidfVectorizerの生成・学習
vectorizer = TfidfVectorizer(min_df=3, norm='l2')
vectorizer.fit(X_train['v2'])
print('Vocabulary size: {}'.format(len(vectorizer.vocabulary_)))
# Vocabulary size: 501

# ベクトル化して特徴量を抽出
X_train_bow = vectorizer.transform(X_train['v2'])
X_test_bow = vectorizer.transform(X_test['v2'])

# ベイズモデルの生成・学習
model = BernoulliNB()
model.fit(X_train_bow, y_train)

# 結果
print('Train accuracy: {:.3f}'.format(model.score(X_train_bow, y_train)))
print('Test accuracy: {:.3f}'.format(model.score(X_test_bow, y_test)))
# Train accuracy: 0.975
# Test accuracy: 0.970

ステミング

トークン化の処理に、ステミング(stemming: 語幹抽出)を加えてみます。

例えば"likes"と"liked"はスペルとしては異なりますが、いずれも元は"like"で、意味的にも同じため、同じ語として特徴抽出できたほうが分類では望ましいです。 そうした単複や時制による語形の違いを除去するのがステミングで、PorterやSnowball、Lancasterなどのアルゴリズムなどの方法が提案されています。

今回はNeural Language Toolkit(nltk)PorterStemmerを使ってステミングしてみます。

nltkのインストール

まずはnltkをインストールします。
また実行に必要なデータは別途ダウンロードが必要で、 nltk.download() でダウンロードする必要があります。 (全体で数GBのファイルサイズになりますので注意してください。)

$ pip install nltk
$ python
>>> import nltk
>>> nltk.download()

PorterStemmer

ダウンロードができたら、word_tokenizeとPorterStemmerをインポートします。

word_tokenizeは文章となっているstringから語を切り出し、PorterStemmerのstemメソッドでステミングします。
この後、TfidfVectorizerと組み合わせるため、クラス化しておきます。

試しにPorterStemmerのコメントの1文をステミングさせてみますと、'has'は'ha'、'original'は'origin'などに変形していることが確認できます。 (変形の結果、実際に存在しない語になることもあります。)

from nltk import word_tokenize
from nltk.stem.porter import PorterStemmer

class PorterTokenizer(object):
    def __init__(self):
        self.porter = PorterStemmer()
        
    def __call__(self, doc):
        return [self.porter.stem(w) for w in word_tokenize(doc)]

tokenizer = PorterTokenizer()
print(tokenizer('Martin Porter has endorsed several modifications to the Porter algorithm since writing his original paper, '))
# ['martin', 'porter', 'ha', 'endors', 'sever', 'modif', 'to', 'the', 'porter', 'algorithm', 'sinc', 'write', 'hi', 'origin', 'paper', ',']

最後にTfidfVectorizerで特徴ベクトル化して、ナイーブベイズで学習・テストさせてみます。

tokenizerオプションでトークン化処理を関数として渡せますので、先程定義したPorterTokenizerをセットします。 また、ステミングによって、同じ語に集約されることが多くなります(被りやすくなる)ので、min_dfも3から6へ大きくします。

テストデータで97.1%の精度となり、ステミング無しの場合よりも0.1%だけ向上しました。

vectorizer = TfidfVectorizer(min_df=6, norm='l2', tokenizer=PorterTokenizer())

vectorizer.fit(X_train['v2'], y_train)

print('Vocabulary size: {}'.format(len(vectorizer.vocabulary_)))
# Vocabulary size: 275

X_train_bow = vectorizer.transform(X_train['v2'])
X_test_bow = vectorizer.transform(X_test['v2'])

model.fit(X_train_bow, y_train)

print('Train accuracy: {:.3f}'.format(model.score(X_train_bow, y_train)))
print('Test accuracy: {:.3f}'.format(model.score(X_test_bow, y_test)))
# Train accuracy: 0.975
# Test accuracy: 0.971

Pythonではじめる機械学習 ―scikit-learnで学ぶ特徴量エンジニアリングと機械学習の基礎

Pythonではじめる機械学習 ―scikit-learnで学ぶ特徴量エンジニアリングと機械学習の基礎