らくがき入門

機械学習を始めとしたコンピュータサイエンスを主に扱っています。

ABC141の解法

本日開催されたABC141のD問題までの解法について書きます。

A: Weather Prediction

特に工夫はなく、if文を連打してAC

S = input()

if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
elif S == 'Rainy':
    print('Sunny')

B: Tap Dance

問題文から奇数のときはL以外、偶数のときはR以外を出さないとYesにならないことがわかる。 これらを判定し、もしNoが出た場合はexitするように書くことでAC。

from sys import exit


S = input()

for i in range(len(S)):
    num = i+1
    if num % 2 == 1 and S[i] == 'L':
        print('No')
        exit()
    if num % 2 == 0 and S[i] == 'R':
        print('No')
        exit()
print('Yes')

C: Attack Survival

参加者それぞれの正解数をカウントして、(全体正解数Q-参加者の正解数V)を計算することで、 参加者それぞれの不正解数がわかる(今回の問題では不正解数分だけ最初にもっていたKポイントから減算されるという問題設定)。 よって、Q-V がKを超えるかどうかを判定し、AC。

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]

victory_cnt = [0] * N 

for i in range(Q):
    victory_cnt[A[i]-1] += 1

for v in victory_cnt:
    if (Q-v) >= K:
        print('No')
    else:
        print('Yes')

D: Powerful Discount Tickets

コンテスト中に方針を立てることはできたが、TLEを解消できなかった。 コンテスト終了後、プライオリティキューを用いてsubmitすることでTLEを出さずにACできた。 方針としては、最大値に対して割引の回数だけ割引し続けるという方針でいくとうまくいく。 このとき、割引前の最大値と、その最大値に対して割引を適用したあとでは最大値が入れ替わる可能性があることが今回のポイントとなる。 それを踏まえて、プライオリティキューで最大値を取り出して、(最大値//2)をプライオリティキューに加えて、それに対してまた最大値を取り出すという処理を繰り返すことで対処する。

import heapq


N, M = map(int, input().split())
A = list(map(int, input().split()))
A_inv = [-a for a in A]
heapq.heapify(A_inv)
for _ in range(M):
    max_inv = heapq.heappop(A_inv)
    heapq.heappush(A_inv, -(-max_inv//2))

print(sum([-a for a in A_inv]))

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

atcoder ABC123 B問題"Five Dishes"解法

ABC123のB問題、"Five Dishes"のPythonでの解法を記載します。

方針

10の倍数でしか注文ができないという制約があるので、下1桁が1が最大の注文ロスになることがわかります。 また、最大の注文ロスとなる料理以外は基本的に順番は問わないと考えられるため、単純に余りで降順にソートして、 料理作成の時間と10で割ったときの余りを足していくと全ての料理が届くまでの最小時間になるといえます。

  • 余りでの降順ソートだが、10の倍数の数字は余りが0になってしまうため、10で置換し対応
  • 元の調理時間と余りをペアにして、余りに基づいて降順にソート

実装上の工夫

  • リスト内包表記内でif文を用いて0を10に置換
  • 多重リストでのある特定のカラムでのソート

実装例

以下のコードでACです。

A = [int(input()) for i in range(5)]
mod_list = [a % 10 for a in A]
mod_list = [10 if a == 0 else a for a in mod_list]

comb_list = [[a, b] for a, b in zip(A, mod_list)]
sort_list = sorted(comb_list, key=lambda x: -x[1])

res = 0

for i, a in enumerate(sort_list):
    if i < 4:
        res += a[0] + (10-a[1])
    else:
        res += a[0]

print(res)

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

アイテムベースの推薦アルゴリズム「Slope One」

今回は比較的シンプルなアイテムベースの推薦アルゴリズムながら、比較的良い推薦精度を示すSlope One予測について説明します。 概要を説明して、数式での説明を加えて、Pythonで実装するという流れで進めます。

Slope One予測とは

Slope One予測の考えとしては、ユーザーのアイテムに対する「人気度の差異」に基づいています。

Slope One予測は、2組のアイテムに対してあるアイテムの評価値を別のアイテムの評価値から予測するための関数を見つけるという考えに基づいて、 未知の評価値を算出します。 具体的には、ここのユーザーのアイテム評価値間の差分を算出し、全ユーザーについて算出されたアイテム評価値間差分の平均値を算出し、この算出結果を基に結果を算出していきます。

Slope One 予測の定式化

シンプルなSlope One予測の定式化

Slope One予測は以下のように定式化できます。

  • アイテム間での平均偏差を求めます。

 \displaystyle
dev _ {j, i} = \Sigma _ {(u _ {j}, u _ {i}) \in S _ {j, i}(R)} \frac{u _ {j} - u _ {i}}{|S _ {j, i}(R)|}

通常評価値データベース全体を Rで示し、あるユーザーの評価値は不完全な配列 uで構成されます。  u _ {i} uのアイテム iに対する評価値(つまりあるユーザーのアイテム iに対する評価値)です。  S _ {j, i}(R)はアイテム i jを両方評価したユーザーの集合 S _ {j, i}(R)の要素数を表現しています。

  • 共に評価付されたアイテムの平均値を計算します。

 \displaystyle
pred(u, j) = \frac{\Sigma _ {i \in Relevant(u, j)} (dev _ {j, i} + u _ {i})}{|Relevant(u, j)|}

関数 Relevant(u, j)はユーザー uによって jと共に少なくとも1回は評価されたアイテムと定義します。

重み付けしたSlope One予測の定式化

直感的には、1人よりも10人のユーザーと行ったようにより多くのユーザーの評価値を基に算出したほうが、信頼性の高い予測になると考えられます。 そこで個々の偏差の重みを共に評価された回数として、重み付けを行うことを考えます。

 \displaystyle
pred(u, j) =  \frac{\Sigma _ {i \in S(u) - \{j\}}(dev _ {j, i} + u _ {i} \times |S _ {j, i}(R)|)} {\Sigma _ {i \in S(u) - \{j\}} |S _ {j, i}(R)|}

Pythonでの実装

以下のような、評価値データベースを考えます。

item1 item2 item3
alice 2 5
user1 3 2 5
user2 4 3

この評価値データベースでaliceのitem3の評価値を予測することを目的とします。 今回は、上で示した重み付けをしたSlope One予測で評価値を予測します。

この例では、

  • 共に評価されている回数が2回であるitem1とitem3があります。 user1においては、item3に対してitem1よりも2ポイント高い評価付けをしています。( 5 - 3 = 2) user2においては、item3に対してitem1よりも1ポイント低い評価付をしています。( 3 - 4 = -1) よって、これらの平均距離は、 (2 + (-1)) / 2 = 0.5です。

  • 共に評価されている回数が1であるitem2とitem3があります。 user1においては、item3に対してitem2よりも3ポイント高い評価付けをしています。( 5 - 2 = 3) よって、これらの平均距離は、 3 / 1 = 3です。

総合的な予測値は、共に評価された回数を考慮に入れるため、重み付けをして計算します。  \displaystyle
pred(alice, item3) = \frac{2 \times 2.5 + 1 \times 8}{2 + 1} = 4.33

これをPythonで実装したコードを以下に示します。

import numpy as np


arr = np.array([[2, 5, np.nan], 
                [3, 2, 5], 
                [4, np.nan, 3]])

target_user_index = 0
target_item_index = 2
exist_rat_target = np.flatnonzero(~np.isnan(arr[:, target_item_index]))

top_value = 0
bottom_value = 0
for idx in range(arr.shape[1]):
    if idx != target_item_index:
        comp_arr = arr[:, target_item_index][exist_rat_target] - arr[:, idx][exist_rat_target]
        rat_cnt = np.count_nonzero(~np.isnan(arr[:, idx][exist_rat_target]))
        target_user_rat = arr[target_user_index, idx] 
        top_value += rat_cnt * (target_user_rat + np.nansum(comp_arr) / rat_cnt)
        bottom_value += rat_cnt

print('alice rating of item3: {:.2f}'.format(top_value / bottom_value))

まとめ

Slope One予測はかなり直感的でわかりやすいにも関わらず、一般的なユーザーベースやアイテムベースよりも比較的良い精度をだすみたいです(もう少しサーベイは必要だとは思いますが・・・)。 今度はMovieLensのデータセットで精度評価をしてみたいですね。 気が向けば追記します。

qiita.com

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

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

情報検索における潜在意味解析

前回はユーザーベースの協調型推薦を実装したのですが、このようなシンプルな協調フィルタリングには大きな問題があります。 それはスパースな行列に対してうまくレコメンドができないことです。システムが巨大になるほど、ユーザーが利用していないアイテムが増えたり、 あまりシステムを利用しないユーザーが増えていくため、行列が非常にスパースになっていきます。

https://leisurelab.hatenablog.com/entry/2019/02/21/073842leisurelab.hatenablog.com

潜在的意味解析の意義

協調的型推薦は主にメモリベースとモデルベースの2つに分類されます。

  • メモリベース ユーザーが評価した評価値をデータベースとして保持した評価値データベースをすべてのメモリの中に格納し、推薦を行うために直接用いる手法。

  • モデルベース 生のデータをあらかじめオフラインで処理して、推薦実行時にはオフラインで処理した前処理結果や学習済みのモデルを評価値予測のために使用する手法。

理論上、メモリベースのように存在するデータをすべて用いるほうが正確ですが、データの規模が大きくなるにつれて計算量と計算コストの問題が出てくると考えられます。

こういった実務的な要請があるために、モデルベース推薦が注目されてきたと背景があります。

モデルベース推薦において、潜在的な"意味"を表現する因子を利用するという考えが一般的です。 例えば、Google検索などの情報検索においてユーザーが入力したクエリに対して、文書とクエリそれぞれに含まれる単語の重複によって評価するという単純な手法を利用することはもちろん可能です。 しかし、この手法には問題があって"車"や"自動車"などの同義語や、"モデル"などに複数の意味を表しうる多義語が含まれる場合、うまく機能しません。

この問題を解決するために、潜在的意味解析(latent semantic analysis; LSA)という技術が発展してきました。 LSAは、すべての文書の背後に意味の構造が存在すると考え、これを行列の形に表現して、分解することが特徴です。 行列として表現することにより、多変量海鮮の考えを適用でき、文書や語句を数学的・統計的に分析することが可能になります。 また、LSAでは表現としては豊かすぎる語句・文書を、行列分解という形で除外し、複数の語句の背後に共通して存在する意味構造を抽出することを考えます。 これにより、大規模な文書ベクトルの行列に対して単語間の高い相関や共起語を1つの因子として捉えて、より小さな階数(ランク)の行列による近似に縮約することで、 生データの情報をできるだけ損なわずに、規模の問題を解決しようとしています。

LSAで使われる行列分解のうち、特異値分解(singular value decomposition; SVD)について考えてみたいと思います。

特異値分解(SVD)

特異値分解の概要

特異値分解は簡略的には以下のように表現されます。 これは与えられた行列Mを以下のように3つの行列に分割している操作です。

 \displaystyle
M = U \Sigma V^ T

 Uは左特異ベクトル、 Vは右得意ベクトル、 \Sigmaの対角成分は特異値といいます。

仮に行列 M m \times nの行列でランクが rの場合、行列 Mには冗長な要素が含まれているといえます。 以下のように、上の式を変換することで行列 Mをr次元データで表現できるようになります。

 \displaystyle
AV = U \Sigma

この分解で重要なポイントは、n次元行列をr次元行列に変換できるだけでなく、 ユークリッドノルムの大きなベクトル、つまり行列を構成する上で影響力の強いベクトルから順に列ベクトルに割り当てられることです。

SVDを使った次元削減

上述したように、 \Sigmaは対角行列なので、対角要素 \sigmaが大きければ、行列 Mに与える影響も大きくなります。 そこで上位k個の \sigmaを抽出することで、次元を削減します。この手法は低ランク近似と呼ばれます。 小さな特異値から削減することで、オリジナルの行列と低ランク近似した行列の各要素の2乗誤差が最小になることが知られています。

Pythonでの実装

情報検索の例

以下のデータベースにおいてSVDを試してみます。 例は以下のサイトから引用しています。

drive automobile car play music
document1 2 3 0 0 0
document2 2 0 2 0 0
document3 0 0 0 2 2
document4 0 0 0 3 1

この例だとdocument1にはcarの出現頻度が0であり、この文書でcarを検索してクエリと文書の重複を見ても、重複がないためdocument1を見つけることはできないということが言えます。 同様に、automobileで検索してもdocument2を得ることはできないということが言えます。 しかし、carとautomobileは同義語だと言えるため、検索で見つけられるようになる必要があると考えられます。 そこで、特異値分解(SVD)を用いることで、潜在的共起性を抽出します。

import numpy as np
import pandas as pd


arr = np.array([[2, 3, 0, 0, 0],
                [2, 0, 2, 0, 0],
                [0, 0, 0, 2, 2],
                [0, 0, 0, 3, 1]])

numpyを用いて特異値分解を行います。

u, sigma, v = np.linalg.svd(arr, full_matrices=True)

上位k個を抽出し低ランク近似を行います。 最後は結果を解釈しやすいように、小数点第3位で四捨五入しています。

k = 2
u2 = u[:, :k]
sigma2 = sigma[:k]
v2 = v[:k, :]

arr2 = np.round(np.dot(np.dot(u2, np.diag(sigma2)), v2), 2)

これによって得られた結果を以下に示します。

drive automobile car play music
document1 2.38 2.29 0.85 0 0
document2 1.32 1.27 0.47 0 0
document3 0 0 0 2.36 1.37
document4 0 0 0 2.68 1.55

以上の結果より、document1とdocument2ともにautomobileとcarの要素が正の値を取っており、 それぞれが検索として潜在的共起性を抽出できていることがわかります。

推薦システムの例

追記予定。

まとめ

次元削減に関しては、主成分分析(PCA)や非負値行列因子分解(NMF)などもあり、今後これらも比較していきたいです。 何か間違いなどを発見されましたら、コメントいただけるとありがたいです。

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

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

ユーザーベース協調フィルタリングを実装してみた

amazonNetflixで使われているレコメンドシステムに突然興味を持ったので、推薦システムの勉強をしたのでpythonで実装してみました。

勉強のアウトプットなので、間違っていたらご指摘いただけると幸いです。

推薦システムとは

amazonでモノを買ったりすると、「この商品をチェックした人はこんな商品もチェックしています」みたいな推薦をしてくれますよね。 まさにあれが推薦システムで、特定のユーザーに対してどのモノを推薦すべきかを決定するシステムのことを推薦システムといいます。 その中でも、すべてのユーザーの嗜好に応じて異なる推薦のリストを提示するシステムが個人化推薦といいます。

種類としては、

  • 協調型推薦
  • 内容ベース型推薦
  • 知識型ベース型
  • 複数のアプローチを組み合わせたハイブリッド型

があります。

今回は、協調型推薦の中のユーザーに基づいた推薦が対象です。

協調型推薦

協調型推薦は、 過去に同じ興味を共有したユーザーは将来的にも同じような興味をもつだろう 仮定しています。

なので、ユーザーAとユーザーBの購入履歴が似ていて、ユーザーBがまだ知らないモノをユーザーAが最近購入したとすると、 これをユーザーBに提案することは合理的だといえます。

ユーザーがお互いに示し合わせたわけではなく暗黙的に協調して、膨大なモノの集合から最も有望なモノをフィルタリングするため、 この技術を協調フィルタリングと呼んでいます。

協調型推薦を考える上で、以下の問いに答える必要がでてきます。

  • 類似したユーザーというけれど類似したユーザーを膨大なユーザーの中から探し出すのか?
  • そもそも類似ってなに?
  • 類似ってどうやって測る?
  • 新規のユーザーでまだシステムの利用履歴がないけどどう対処する?
  • ユーザーに関して利用できるデータが少ない場合はどうする?
  • 類似ユーザーを探す以外に特定のユーザーがあるモノを好きかどうかを予測できる手法は存在する?

ユーザーベース推薦

ユーザーベース推薦のシステムのアイディアは非常にシンプルで、

  • 対象ユーザーの評価データ入力して、過去の嗜好と似ている他のユーザー(=ピアユーザー)を特定する
  • 対象ユーザーがまだ見ていないモノに対する評価をピアユーザーの評価を用いて予測する

ユーザーベース推薦は以下の2つの仮説に基づいています。

  • ユーザーが過去に似た嗜好をもっているなら、その嗜好は将来においても似ている
  • ユーザーの好みは長い間一貫している

実際この辺りの仮定は少し無理があるので、amazonとかは別の手法を用いているみたいです。この辺りはまだ知識不足なので、よくわかってません笑

このあたりを基礎知識として、ユーザーベース推薦を実装してみました。

使用するデータセット

今回利用するのはMovieLensデータセットです。 https://grouplens.org/datasets/movielens/

MovieLensデータセットは推薦システムの開発やベンチマークとしてミネソタ大学の研究グループが公開してくれています。ありがたいですね。

今回はMovieLens 100K Datasetを使用します。

ベンチマーク(参考コード)

推薦システムの実装で使われていることが多いので、他の人のコードを眺めながらできるのは非常にありがたいです。 ちなみに以下のgithubのコードをベンチマークとして実装しています。

今回の実装はMovieLens100kに対するユーザーベース協調フィルタリングになるので、 precisionで19.69%を目標とすることになります。

実装

データの読み込み

データは手元にダウンロードして、使用しています。 ua.baseがtrain dataで、ua.testがtest dataとなっているみたいです。

import numpy as np
import pandas as pd

train = pd.read_csv('../data/input/ml-100k/ua.base', names=["user_id", "item_id", "rating", "timestamp"], sep='\t')
test = pd.read_csv('../data/input/ml-100k/ua.test', names=['user_id', 'item_id', 'rating', 'timestamp'], sep='\t')

データとしては以下のような内容です。 データの全容としては、943ユーザーによる1682アイテムに対して1~5の評価をしているレビューサイトのデータという感じです。

amazonをイメージしてもらえると理解の助けになると思うのですが、全員がすべてのアイテムのレビューをしているわけではないので、非常に疎なデータセットになっています。

user_id item_id rating timestamp
0 186 302 3 891717742
1 22 377 1 878887116
2 244 51 2 880606923
3 166 346 1 886397596
4 298 474 4 884182806
  • 類似したユーザーというけれど類似したユーザーを膨大なユーザーの中から探し出すのか?

→今回はすべてのユーザーと総当たりで類以度を計算して、上位何人かを類似したユーザーと定義します。

  • そもそも類似ってなに?

→類以度という概念を導入してユーザー間の類似を表現します。

  • 類似ってどうやって測る?

→類似度にも様々な表現方法があるのですが、今回はコサイン類以度を採用します。

  • 新規のユーザーでまだシステムの利用履歴がないけどどう対処する?
  • ユーザーに関して利用できるデータが少ない場合はどうする?
  • 類似ユーザーを探す以外に特定のユーザーがあるモノを好きかどうかを予測できる手法は存在する?

→上の3つに関しては今回は範囲外としてまた別のタイミングで扱うことにします。

とりあえず今回の記事で扱う話を整理したので、それぞれに注目して行きたいと思います。

コサイン類以度

今回類以度として採用したコサイン類以度は2つのベクトルを用いて以下のように定式化できます。  \displaystyle
  sim(\boldsymbol{a}, \boldsymbol{b}) = \frac{\boldsymbol{a} \cdot \boldsymbol{b}}{|\boldsymbol{a} |\times |\boldsymbol{b}|}

コサイン類以度は、0から1の値を取りベクトル同士の成す角度の近さを表現しています。

推薦システムの文脈でコサイン類以度を考える場合には、ユーザーが異なることを気をつける必要があります。例えば、ユーザーAは甘めに評価する一方で、ユーザーBは辛めに評価する傾向にあるといったところを考慮する必要があるということです。 これは、ユーザーの評価値の平均をそのユーザーの評価から引くことで解決でき、これを調整コサイン類以度といいます。

実装としては、以下のように実装しています。下のmean_adjustment=Trueとすると調整コサイン類以度になります。

def cosine_similarity(v1, v2, mean_adjustment=False):
    if mean_adjustment:
        v1 = v1 - np.mean(v1)
        v2 = v2 - np.mean(v2)
    return np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))

下準備

ここではindexがuser_id、columnsがitem_idになるような評価値行列を作成しています。 ユーザーが今回評価をつけていないところは0としました。調べてみると、Rの推薦システムのライブラリrecommenderlabも欠損は0としているみたいなので、とりあえずこれで進めていきます。

train_rating_mat = pd.pivot_table(train, index='user_id', columns='item_id', values='rating')
train_rating_mat.fillna(0,  inplace=True)

メインの実装部

以下がメインの実装部になっています。 user1には参考にしたコードでテスト用に5人選抜していたので、そのまま流用しています。

手順としては、

  • user1に対して全ユーザーのコサイン類以度を算出
  • 算出されたコサイン類以度の上位10人を選抜
  • 上位10人の近接性とuser1の平均評価値を使ってuser1のアイテムに対する評価値を予測
  • 予測結果からトップ10を用いてレコメンドリストを作成
  • 実際にuser1が購入したリストと比較してprecisionで評価

これを実行するとprecisionが22%になり、少し高いような気がしますが参考にしたコード付近のprecisionになりました。

# use five people for evaluation of recommend system
for user1_id in tqdm([1, 100, 233, 666, 888]):
    cos_sim_list = []
    for user2_index in range(rating_arr.shape[1]):
        user1 = rating_arr[:, user1_id-1][:, np.newaxis]
        user2 = rating_arr[:, user2_index][:, np.newaxis]
        two_users_mat = np.concatenate((user1, user2), axis=1)
        two_users_mat = two_users_mat[~np.isnan(two_users_mat).any(axis=1), :]
        # calucalate cosine similarity between user1 and user2
        cos_sim = cosine_similarity(two_users_mat[:, 0], two_users_mat[:, 1], mean_adjustment=True)
        cos_sim_list.append(cos_sim)
        cos_sim_mat = pd.Series(cos_sim_list, index=[i for i in range(1, rating_arr.shape[1] + 1)])

    # use top 10 users of cosine similarity
    top_n = 10
    top_n_sim = cos_sim_mat.sort_values(ascending=False)[1:top_n+1]
    top_n_users = top_n_sim.index

    # test data of user1
    test_user1 = test[test['user_id'] == user1_id].sort_values(by='rating', ascending=False)

    # calculate the prediction of user1
    user1_not_rating = train_rating_mat.iloc[user1_id-1, :]
    user1_not_rating = pd.Series(np.logical_not(user1_not_rating), index=user1_not_rating.index)
    mean_r = train_rating_mat.replace(0, np.nan).mean(axis=1).drop(labels=[user1_id])
    mean_r = mean_r[mean_r.index.isin(top_n_users)]

    not_user1_rating_item = train[train.index.isin(user1_not_rating[user1_not_rating == 1].index)]
    not_user1_rating_item = not_user1_rating_item[not_user1_rating_item['user_id'].isin(top_n_users)]
    not_user1_rating_item.reset_index(inplace=True)

    ra = train_rating_mat.replace(0, np.nan).iloc[0, :].mean()
    bottom_value = np.sum(top_n_sim)
    item_id_list = []
    pred_list = []
    hits = 0

    # recommend top 10 item
    for item_id in not_user1_rating_item['item_id'].unique():
        rating_by_item = not_user1_rating_item[not_user1_rating_item['item_id'] == item_id]
        top_value = np.sum([top_n_sim[uid] * (rating_by_item[rating_by_item['user_id'] == uid]['rating'].values - mean_r[uid]) for uid in rating_by_item['user_id'].values])
        pred = ra + top_value / bottom_value
        item_id_list.append(item_id)
        pred_list.append(pred)

    # check the precision of recommend list
    pred_dict = {'item_id': item_id_list, 'pred': pred_list}
    pred_df = pd.DataFrame.from_dict(pred_dict).sort_values(by='pred', ascending=False).reset_index(drop=True)
    recommend_list = pred_df[:10]['item_id'].values
    purchase_list = test_user1['item_id'].values
    for item_id in recommend_list:
        if item_id in purchase_list:
            hits += 1
    precision_ = hits / 10.0
    precision_list.append(precision_)
print('precision: {:.2f}'.format(sum(precision_list) / len(precision_list)))

最後に

コードは以下においてあります。

とりあえずユーザーベースは理解できた気がするので次はアイテムベースに挑戦します。 間違いなどがあればコメントに書いていただけると幸いです。

参考にした以下の文献に感謝です。

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

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

pandasを用いてフラグがついている列が先頭になるように行ごとにシフトする

やりたい処理は、すべての行でフラグ1が先頭にくるようにシフトしたい。

うまいやり方かどうかわからないけど、一応うまくいっているような気がする。

サンプルコード

import numpy as np
from numpy import nan
import pandas as pd
import warnings 
warnings.filterwarnings("ignore") # 実行に関係のない警告を非表示
# 左からゼロパディング
columns_list = ["a_{0:02d}".format(i) for i in range(0, 12)]
value_arr = np.array([[nan, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                      [nan, nan, 1, 0, 0, nan, nan, nan, nan, nan, nan, nan], 
                      [nan, nan, nan, 1, 0, 0, 0, nan, nan, nan, nan, nan] 
                     ])

時系列のデータを想定したDataFrameを作成。

フラグが1になるカラムが行ごとにバラバラなので、すべての行で先頭のカラムが1になるようにシフトしたい。

df = pd.DataFrame(value_arr, columns=columns_list)
df
a_00 a_01 a_02 a_03 a_04 a_05 a_06 a_07 a_08 a_09 a_10 a_11
0 NaN 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
1 NaN NaN 1.0 0.0 0.0 NaN NaN NaN NaN NaN NaN NaN
2 NaN NaN NaN 1.0 0.0 0.0 0.0 NaN NaN NaN NaN NaN

行ごとに処理を行う。

  1. 各行ごとにフラグ1がくるインデックスを取得して、その分だけ左方向にシフトする(作成されるのはSeries)

  2. 作成されたseriesを行方向に結合する

  3. 結合してできたDataFrameをtransposeして元のDataframeと形を揃える。

se_concat = pd.concat([df.ix[i].shift(val) for i, val 
                       in enumerate([-np.where(value_arr == 1)[1][j] 
                                     for j in range(len(df))])], axis=1)
se_concat.T
a_00 a_01 a_02 a_03 a_04 a_05 a_06 a_07 a_08 a_09 a_10 a_11
0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 NaN
1 1.0 0.0 0.0 NaN NaN NaN NaN NaN NaN NaN NaN NaN
2 1.0 0.0 0.0 0.0 NaN NaN NaN NaN NaN NaN NaN NaN

参考にした書籍・サイト

Pythonによるデータ分析入門 第2版 ―NumPy、pandasを使ったデータ処理

Pythonによるデータ分析入門 第2版 ―NumPy、pandasを使ったデータ処理

<Python, pandas> 縦にずらす。

numpyのarrayで複数の要素が配列内に存在するか判定する

numpy.arrayで複数の要素をリストで渡して、真偽値行列を作成してみる。

使うのは、numpy.in1dで、 指定したarray-likeな要素がある配列内に存在するかどうかを判定して、1次元の真偽値行列を返してくれる。

配列の形を合わせたいなら、reshape(arr.shape)で形を合わせることができる。

In [1]: import numpy as np

In [2]: arr = np.array([[1, 3, 5], [2, 3, 4], [2, 3, 3]])

In [3]: np.in1d(arr, [1, 3, 5])
Out[3]: array([ True,  True,  True, False,  True, False, False,  True,  True])

In [4]: np.in1d(arr, [1, 3, 5]).reshape(arr.shape)
Out[4]: 
array([[ True,  True,  True],
       [False,  True, False],
       [False,  True,  True]])

Pythonによるデータ分析入門 第2版 ―NumPy、pandasを使ったデータ処理

Pythonによるデータ分析入門 第2版 ―NumPy、pandasを使ったデータ処理