剥いだ布団とメモランダム.old

情報系のことをかいてゆく

Pythonでレコメンド・システムをつくる

Python 息抜き 協調フィルタリング

協調フィルタリングっていうやつですね。

Last.fmユーザのデータセットを使って、
アーティストをレコメンドしてくれるプログラムを作ってみた。

$ recommend.py 274
＜あなたが再生したことのあるアーティスト:再生数＞
Depeche Mode : 7386
浜崎あゆみ : 2046
X JAPAN : 1365
Michael Jackson : 1261
倖田來未 : 1024
hide : 910
GACKT : 746
安室奈美恵 : 689
ZARD : 560
Céline Dion : 552
Emilie Autumn : 487
MALICE MIZER : 483
the GazettE : 462
L'Arc~en~Ciel : 373
KAT-TUN : 316
宇多田ヒカル : 295
Aerosmith : 274
AAA : 264
アンティック-珈琲店- : 247
モーニング娘。 : 241
清春 : 222
Marilyn Manson : 216
Cristina D'Avena : 212
SUGIZO : 210
YOSHIKI : 199
LUNA SEA : 197
Martin L. Gore : 184
DIR EN GREY : 175
é›…-MIYAVI- : 169
Tommy february6 : 165
Dave Gahan : 164
YUI : 152
Lucio Battisti : 145
大塚愛 : 145
hitomi : 143
Alphaville : 137
T.M.Revolution : 128
SADS : 126
Wonder Girls : 124
NEWS : 118
Fabrizio De André : 118
Capsule : 109
883 : 105
동방신기 : 104
RENTRER EN SOI : 99
KOKIA : 95
倉木麻衣 : 94
ポルノグラフィティ : 94
いきものがかり : 90
DJ OZMA : 86
＜あなたにオススメのアーティスト:推薦度＞
Luzmelt : 702
Lady Gaga : 591
Eths : 584
BoA : 509
嵐 : 470
BIG BANG : 422
KOTOKO : 370
The Horrors : 344
Perfume : 298
Dark Schneider : 295

こんな感じで、再生履歴に応じて、おすすめの聴いていないアーティストをレコメンドしてくれます。

やってること

データセットから、ユーザとその嗜好（今回は再生数）を取得して、
ユーザ間のユークリッド距離もしくはピアソン相関係数を求めて、類似度を判定。

求められたユーザ間の類似度から、ユーザが再生したことのないアーティストの推薦度を求める。
そしてその推薦度TOP10のアーティストを出力する。

ユークリッド距離による類似度導出

いろいろな距離指標（ユークリッド、マンハッタン、マハラノビス…）があるけども、
一番ポピュラーなやつっすね。三平方の定理を利用したあれです。
n次元の嗜好空間上のユーザ間の距離を調べ、その逆数を類似度とする方法です。

ユーザsによるアーティストiの再生数をp_{s,i}として、
ユーザs, t間の類似度$Sim_{s,t}$は
\begin{eqnarray} Sim_{s,t} = \frac{1}{1 + \sqrt{\sum_{i=1}^{n} (p_{s,i} - p_{t,i})^2}} \end{eqnarray}
で求められる。
ゼロ除算を回避するために分母に1を加算しています。

ここで、共通するアーティストを聴いていないユーザ間では1が出力されることに注意です。
つまり、類似度が1として出力された場合は同一ユーザか類似度が全くない場合と考え、
このあとで行うアーティストの推薦度導出式には含めるべきではないということ。

ピアソン相関係数による類似度導出

データセットを見てみると、全体的に再生数が多い人、少ない人がいるわけです。
この人たちが同じような嗜好だとしても、再生数によるユークリッド距離を調べてみると、
数式の性質上、どうしても距離が大きくなってしまい、類似度が低くなってしまう。

そこで、ユーザ間の嗜好の相関を見よう、いうことで出てくるのがピアソン相関係数。

ユーザsによるアーティストiの再生数をp_{s,i}、
ユーザsの再生数の平均をE[p_{s}]、と表すとき、
ユーザs, t間の類似度$Sim_{s,t}$は

\begin{eqnarray} Sim_{s,t} = \frac{\sum_{i=1}^{n} (p_{s,i} - E[p_{s}]) (p_{t,i} - E[p_{t}])} {\sqrt{\sum(p_{s,i} - E[p_{s}])^2} \sqrt{\sum(p_{t,i} - E[p_{t}])^2}} \end{eqnarray}
で求められる。

相関なので、-1〜1の値が求められる。
1は相関があり、0は無相関、-1は真逆の嗜好（つまりユーザsが好きなアーティストをユーザtは嫌う傾向にある）ということを意味するわけだ。

実装時には、ゼロ除算となる場合は0と返すようにしないといけない。
あと、この数式では、共通する再生アーティストが1人の場合でも相関係数が1となるときがある。
なので、共通アーティストがある一定数以上に満たない場合は計算しないなどの処理が必要だと思う。

アーティストの推薦度の導出

ユーザ間の類似度を導出できたら、今度はアーティストの推薦度を求める。
これはいろいろな考え方や方法があると思うが、今回は以下の数式を使って求めた。
ここでU_{i}はあるアーティストiを再生する全ユーザの集合。
\begin{eqnarray} Recom_{s,i} = \frac{\sum_{t \in U_{i}}(p_{t,i} - E[p_{t}]) Sim_{s,t}}{\sum_{t \in U_{i}} |Sim_{s,t}|} \end{eqnarray}

この式は、いろいろな人に再生されているような場合、
推薦度が高くなる傾向をある程度抑えることができる。

データセット

今回は、HetRec2011用に用意されたデータを使ってみた。
商用利用でなければ使っていいというライセンス。
HetRec2011 http://grouplens.org/datasets/hetrec-2011/

基本的にタブ区切りになっているので、
csvモジュールをインポートして、delimiterをタブに変えてあげればパースできる。

詳しいフォーマットについてはreadme.txtを覗いてみてください。
なんか再生数データ以外にもいろいろはいってました。

ソースコード

上のことを踏まえてコーディングした。長いので少々見辛い…

# -*- coding: utf-8 -*-
import csv
import sys

class User:
	"""
	ユーザIDと再生したアーティストのIDのディクショナリを保持
	usrId...<int>生成するユーザのID
	artists...<dictionary>ユーザが再生したことのあるアーティスト
	"""	
	def __init__(self, usrId, playedArtistsDic):
		"""
		コンストラクタ
		usrId...<int>生成するユーザのID
		playedArtistsDic...<dictionary>ユーザが再生したことのあるアーティスト
		"""
		self.usrId = usrId
		self.artists = playedArtistsDic.copy()

	def getSimilar1(self, target, thld=0):
		"""
		あるユーザとの類似度を計算(ユークリッド距離)
		target...<User>類似度を計算するユーザインスタンス
		thld...<int>ユーザ同士で共通アーティスト数の閾値
				thld未満の共通アーティスト数では類似度は0と考える
		return...<float>類似度
		"""
		distance = 0.0	#ユークリッド距離
	        unionArtistN = 0
		for myArtist in self.artists:
			for targetArtist in target.artists:
				if(myArtist==targetArtist):
					#アーティストIDが一致すれば距離計算に加味
                                        unionArtistN += 1
					myWeight = self.artists.get(myArtist)
					targetWeight = target.artists.get(targetArtist)
					distance += (myWeight - targetWeight)**2
					print distance
		distance = 1 + distance**0.5
		if(distance==1.0 or unionArtistN<thld):
			#ユークリッド距離が1の場合は類似度がないので、0をreturn
			#一定数共通アーティストがいなければ類似度は0
			return 0.0
		return 1 / distance

	def getSimilar2(self, target, thld=0):
		"""
		ピアソン相関係数によるユーザ間類似度計算
		target...<User>類似度を計算するユーザインスタンス
		thld...<int>ユーザ同士で共通アーティスト数の閾値
				thld未満の共通アーティスト数では類似度は0と考える
		"""
		#それぞれのユーザの再生数平均を導出
		myMean = 0.0
		targetMean = 0.0
		for i in self.artists.values(): myMean += i
		for i in target.artists.values(): targetMean += i
		myMean = myMean / float(len(self.artists))
		targetMean = targetMean / float(len(target.artists))

		#ピアソン相関係数を導出
		coVar = 0.0
		mySd = 0.0
		targetSd = 0.0
		unionArtistN = 0
		for myArtist in self.artists:
			for targetArtist in target.artists:
				if(myArtist==targetArtist):
					unionArtistN += 1
					myWeight = float(self.artists.get(myArtist))
					targetWeight = float(target.artists.get(targetArtist))
					mySd+= (myWeight - myMean)**2
					targetSd += (targetWeight - targetMean)**2
					coVar += (myWeight - myMean) * (targetWeight - targetMean)
		mySd = mySd**0.5
		targetSd = targetSd**0.5
		if(mySd*targetSd==0.0 or unionArtistN<thld):
			#ゼロ除算を避ける/一定数共通アーティストがいなければ類似度は0
			return 0.0
		return coVar / (mySd * targetSd)

	def getSimilarUsrs(self, usrsDic, thld=0, pearson=True):
		"""
		各ユーザの類似度を計算したタプルリスト（ソート済み）を返す
		usrsDic...<dictionary>ユーザデータディクショナリ
		thld...<int>ユーザ同士の共通アーティスト数の閾値
				thld未満の共通アーティスト数では類似度は0と考える
		mode...<bool>pearson相関係数による類似度関数を使うか
		return...<taple list>類似順にソートされた類似ユーザリスト
		"""
		simDic = {}
		for targetId in usrsDic:
			if(targetId!=self.usrId):
				#自分自身との類似度は計算しない
				#ターゲットのユーザインスタンスを生成	
				target = User(targetId, usrsDic.get(targetId))
				if(pearson):
					sim = self.getSimilar2(target, thld)	#ターゲットとの類似度
				else:
					sim = self.getSimilar1(target, thld)
				if(sim > 0.0):
					#類似度があればディクショナリに追加
					simDic[target.usrId] = sim
		if(len(simDic)==0):
			#類似するユーザが全く見つからなかった場合
			print "Could not find your similar user."
			quit()
		return sorted(simDic.items(), key=lambda d:d[1], reverse=True)

	def getRecommendArtists(self, simUsrs, usrsDic):
		"""
		類似ユーザの再生アーティスト情報から各アーティストの推薦度を返す
		simUsrs...<taple list>類似ユーザ
		usrsDic...<dictionary>ユーザデータディクショナリ
		return...<taple list>推薦度順にソートされた推薦アーティストリスト
		"""
		recomArtists = {}
		totalSim = {}			#アーティストごとにユーザの類似度の合計を持つ
		for usr in simUsrs:
			simUsr = User(usr[0], usrsDic.get(usr[0]))
			for artist in simUsr.artists:
				if(artist not in self.artists):
					#自分が再生しているアーティストは推薦しない
					if(artist not in recomArtists):
						#recomArtistsにartistがいなければ追加する	
						recomArtists[artist] = 0.0
						totalSim[artist] = 1.0
					simUsrMean = sum([i for i in simUsr.artists.values()]) / len(simUsr.artists)
					recomPoint = usr[1] * (simUsr.artists.get(artist) - simUsrMean)
					recomPoint += recomArtists.get(artist)
					recomArtists[artist] = recomPoint
					#同様に再生しているユーザの類似度の合計を求める
					totalSim[artist] = totalSim.get(artist) + abs(usr[1])

		for artist in recomArtists:
			#各アーティストの推薦度を計算する
			recomArtists[artist] = recomArtists.get(artist) / totalSim.get(artist)
		return sorted(recomArtists.items(), key=lambda d:d[1], reverse=True)

def readUsersData(path):
	"""
	TSV型のユーザデータファイルを読み込み、全ユーザデータをディクショナリで返す
	path...<string>データパス
	return...<dictionary>ユーザデータディクショナリ
	"""
	tsv = csv.reader(file(path, 'r'), delimiter = '\t')
	firstRow = True
	secondRow = False
	dic = {}
	usrsDic = {}
	usrId = 0
	for row in tsv:
		if(firstRow):
			#一行目は読み飛ばし
			firstRow = False
			secondRow = True
		else:
			if(secondRow):
				usrId = int(row[0])
				secondRow = False
			nowUsrId = int(row[0])
			if(nowUsrId!=usrId):
				#現在チェックしているIDと前までのIDが一致しているか
				#一致しなければユーザが変わっているので、ここでusrsDicに追加
				usrsDic[usrId] = dic.copy()
				dic = {}
			dic[int(row[1])] = int(row[2])
			usrId = nowUsrId
	#最後のユーザの書き込み
	usrsDic[usrId] = dic.copy()
	return usrsDic.copy()

def readArtistsData(path):
	"""
	TSV型のアーティストデータファイルを読み込み、全アーティストデータをディクショナリで返す
	ディクショナリのkeyはアーティストのID、valueはアーティスト名
	path...<string>データパス
	return...<dictionary>アーティストデータディクショナリ
	"""
	tsv = csv.reader(file(path, 'r'), delimiter = '\t')
	firstRow = True
	artistsDic = {}
	for row in tsv:
		if(firstRow):
			#一行目は読み飛ばし
			firstRow = False
		else:
			artistsDic[int(row[0])] = row[1]
	return artistsDic

def getArg():
	"""
	コマンドライン引数(ユーザID)を取得
	return...<int>ユーザID
	"""
	argv = sys.argv
	argc = len(argv)
	if (argc != 2):
		#引数がない場合は終了	
		print 'Usage: python %s userId' %argv[0]
		quit()
	return int(argv[1])

def main(usrId):
	#ユーザデータの取得
	usrsDic = readUsersData("hetrec2011-lastfm-2k/user_artists.dat")

	#アーティスト名ディクショナリの取得
	artistsName = readArtistsData("hetrec2011-lastfm-2k/artists.dat")
	
	#レコメンドするユーザインスタンスを生成
	if(usrId not in usrsDic):
		#存在しないユーザIDが指定されているときは終了
		print 'usrId: %d does NOT exist.' %usrId
		quit()	
	usr = User(usrId, usrsDic.get(usrId))

	#類似ユーザの取得
	simUsrs = usr.getSimilarUsrs(usrsDic, 5)

	#レコメンドアーティストの取得
	recommendArtists = usr.getRecommendArtists(simUsrs, usrsDic)

	#ユーザが再生したことのあるアーティストを表示
	print "＜あなたが再生したことのあるアーティスト:再生数＞"
	#weightが高い順にソート
	artists = sorted(usr.artists.items(), key=lambda d:d[1], reverse=True)
	for artist in artists:
		print "%s : %d" %(artistsName.get(artist[0]), artist[1])

	#推薦度上位10のアーティストをレコメンドする
	depth = 10
	print "＜あなたにオススメのアーティスト:推薦度＞"
	for i in range(depth):
		artistId = recommendArtists[i][0]
		print "%s : %d" %(artistsName.get(artistId), recommendArtists[i][1])

	#一番似ているユーザが再生しているアーティストを表示
	# simUsr = User(simUsrs[0][0], usrsDic.get(simUsrs[0][0]))
	# print "＜あなたに一番似ているユーザ%d(%f)のプレイリスト＞" %(simUsr.usrId, simUsrs[0][1])
	# artists = sorted(simUsr.artists.items(), key=lambda d:d[1], reverse=True)
	# for artist in artists:
	# 	print "%s : %d" %(artistsName.get(artist[0]), artist[1])

if __name__ == '__main__':
	usrId = getArg()
	main(usrId)

readUsersData関数で返されるディクショナリは、
valueがまたディクショナリだったりすので、少しややこしいです。

あと、ディクショナリに順序という概念がないので、
類似度や推薦度が高い順にデータが得られるように、
sorted関数使ってタプルリストで返しているとこもあります。

雑感

やはり類似度指標を求める際に、共通する再生アーティスト数でフィルタしないと、どうしても、1,2アーティストしか被っておらずそいつがあまり関係なさそうなアーティストのレコメンドの傾向を作ることが起きる。
共通する再生アーティスト数をどの程度にすればいいかは難しいところ…。

あと、これはこのデータセットの特徴かもしれないが、
全体的に日本のアーティストを聴くユーザが少なく、どうしても日本人アーティストへの評価数が少ないという点は気になった。
つまり、評価数（聴いている人）が少ないと、そのアーティストを共通して聴く人が少ないため、そのアーティストを再生しているというデータを活かしたレコメンドを提示できないということ。
例えば、アニソンをよく歌う日本人アーティストをよく聴くユーザデータを作ってレコメンドさせてみても、他の聴いていないアニソン系アーティストがなかなかレコメンドされなかったりした。

あとは、全体として聴くジャンルは偏っているんだけども、各ジャンルの有名アーティストをやや再生しているようなユーザの場合、なかなか上手くレコメンドが働いていないように見えた。確かに、共通アーティスト数の閾値を上げれば良くなるんだけども、かなり（7人以上）上げないと良さそうな結果が得られなかった。
これは、灰色の羊なんていう呼ばれ方をする問題で、複数のユーザタイプに属してしまうユーザに対しては、最適なレコメンドができないという。（コンテンツベースフィルタリングによる解決策は示されている）

ざっと感じたことをまとめると、様々なタイプに対応するなら、非常に多くのデータが必要になるんだなっていうこと。
今回は約2K人でしたが、全然足りないっすね。ビッグデータほしい。
（しかし、今回のプログラムは実装上、計算量的にも膨大なデータには対応できない…）

ただ、アルゴリズム自体は簡単ですぐにコードに起こせたので、とてもおもしろいものだと思った。

＋α

レコメンドエンジンなんていうと、Gunosyなんかもこういうアルゴリズムなんだろうか…
にしてもAmazonのアイテムレコメンドとか、Twitterでのユーザレコメンドとか、
webのいろいろなところでレコメンドシステムは動いてそうなので、少し勉強できてよかった。

今回取り上げたものは、おそらく協調フィルタリングの中でもかなり単純なものっぽい。
ベイジアンネットワークを使ったものやクラスタリング手法を利用したものもあるみたい。


そういえば、フィルターバブル問題っていう言葉もあったねー。

このあたりの研究はまだまだ進んでいく感じなんでしょうか。
また機会があればもう少し勉強してみたい。

集合知プログラミング

集合知プログラミング