WEB+DBプレスの「[速習]レコメンドエンジン」のサンプルプログラムを訂正してみる

プリファードインフラストラクチャーのid:tkngさんと岡野原さんがWEB+DBプレスvol.49に「[速習]レコメンドエンジン」という記事を書かれています。

posted with amazlet at 09.03.08

技術評論社
売り上げランキング: 359

レコメンドエンジンには前々から興味を持っていたので、早速サンプルコードを自分でも書いてみるか、と思い誌面のソースをXCodeに打ち込んで動かしていたのですが、コンパイルが通らない。

なにぶんC++なんてほとんど書いたことがないので、自分のやり方が悪いのかと疑ったのですが、代入する変数が間違っていたりミススペルがあったりなど、おそらくこれは誌面のソースが間違っているのだろうという結論に至りました。
例えば・・・
p130 リスト２より

#include <vector>
typedef vector<pair<int, int> > SparseDoc;Svec; // ←コンパイルとおりません。
typedef SparseVec::iterator Svec::iterator sit; // ←コンパイルとおりません。

p130 リスト3より

float calcInp(sparceVec& Svec& il1, sparceVec& SVec& il2) {
// ↑コンパイルとおりません。さらにtypedefではSparseVecとなっているはずなのにsparceVecです。
...
}

などなど。

僕のように、自分のかき方が悪いんじゃないかと疑って苦労している人もいるのではないかと思い、修正したソースコードをさらしておきます。

ちなみに、内容としては以下のような縦軸にユーザ番号、横軸にアイテム番号を取り、値としてユーザのアイテムに対する評価点を持った行列が与えられたときに、アイテム間の類似度を計算するというものです。

ユーザ番号\アイテム番号	0	1	2	3	4
0		1			3
1		2			3
2	3		5
3		2	2
4	3			4

以下が修正したソースコード。WEB+DBプレスvol.49の130ページ〜131ページあたりが修正の対象で、アイテム番号0に対する各アイテムの類似度を計算して出力する箇所をmain()関数として追加しています。
[main.cpp]

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef vector< pair<int,int> > SparseVec;
typedef SparseVec::iterator sit;

// 各ユーザごとにレビューしたアイテム番号とその結果を記録した結果
// idが昇順で並んでいる
vector<SparseVec> userLog;
// 各アイテムごとにレビューされたユーザ番号とその結果を記録した結果
vector<SparseVec> itemLog;

// il1とil2の内積を計算する
float calcInp (SparseVec& il1, SparseVec& il2) {
	sit it1 = il1.begin();
	sit it2 = il2.begin();
	int inp = 0;
	while (it1 != il1.end() && it2 != il2.end()) {
		int id1 = it1->first;
		int id2 = it2->first;
		if      (id1 < id2) ++it1;
		else if (id1 > id2) ++it2;
		else {
			inp += it1->second*it2->second;
			++it1;
			++it2;
		}
	}
	return inp;
}

// 各ベクトルの長さは前もって計算しておく
vector<float> norms;

void calcNorms () {
	for (size_t i = 0; i < itemLog.size(); i++) {
		float norm = sqrt(calcInp(itemLog[i], itemLog[i]));
		norms.push_back(norm);
	}
}

// i番目のアイテムとj番目のアイテム間のコサイン類似度を計算する
float calcCosSim (int i, int j) {
	float inp = calcInp(itemLog[i], itemLog[j]);
	return inp / norms[i] / norms[j];
}

// アイテムiと他のすべてのアイテムのコサイン類似度をまとめて計算してretに結果を返す
void calcMatchNum (int i, vector<float>& ret) {
	ret.resize(itemLog.size());
	SparseVec& sv(itemLog[i]);
	for (sit it = sv.begin(); it != sv.end(); it++) {
		// it->firstを購入したユーザを列挙する
		SparseVec sv2(userLog[it->first]);
		int val = it->second;
		for (sit it2 = sv2.begin(); it2 != sv2.end(); ++it2) {
			ret[it2->first] += val * it2->second;
		}
	}
	// 結果の正規化を行う
	for (size_t j = 0; j < itemLog.size(); j++) {
		ret[j] /= (norms[i] * norms[j]);
	}
	
	// ret[j]にはcalcCosSim(i,j)と同じ結果が入っている
}

int main (int argc, char * const argv[]) {	
	// itemLogを初期化
	itemLog.resize(5);
	itemLog[0].push_back(make_pair(2,3));
	itemLog[0].push_back(make_pair(4,3));
	itemLog[1].push_back(make_pair(0,1));
	itemLog[1].push_back(make_pair(1,2));
	itemLog[1].push_back(make_pair(3,2));
	itemLog[2].push_back(make_pair(2,5));
	itemLog[2].push_back(make_pair(3,2));
	itemLog[3].push_back(make_pair(4,4));
	itemLog[4].push_back(make_pair(0,3));
	itemLog[4].push_back(make_pair(1,3));
	
	// userLogを初期化
	userLog.resize(5);
	userLog[0].push_back(make_pair(1,1));
	userLog[0].push_back(make_pair(4,3));
	userLog[1].push_back(make_pair(1,2));
	userLog[1].push_back(make_pair(4,3));
	userLog[2].push_back(make_pair(0,3));
	userLog[2].push_back(make_pair(2,5));
	userLog[3].push_back(make_pair(1,2));
	userLog[3].push_back(make_pair(2,2));
	userLog[4].push_back(make_pair(0,3));
	userLog[4].push_back(make_pair(3,4));
	
	// 各ベクトルの長さを初期化
	calcNorms();
	
	// あるアイテムと他のアイテムとの類似度をそれぞれ個別に求める
	cout << "calcCosSim" << endl;
	for (size_t i = 0; i < itemLog.size(); i++) {
		cout << "itemNo:" << i << " similarity:" << calcCosSim(0,i) << endl;		
	}
	
	// あるアイテムと他のアイテムとの類似度をすべてまとめて求める
	cout << "calcMatchNum" << endl;
	vector<float> cosSimVec;
	calcMatchNum(0, cosSimVec);
	for (size_t i = 0; i < itemLog.size(); i++) {
		cout << "itemNo:" << i << " similarity:" << cosSimVec[i] << endl;
	}
	
    return 0;
}

ちなみに実行した結果は以下の通り。

calcCosSim
itemNo:0 similarity:1
itemNo:1 similarity:0
itemNo:2 similarity:0.656532
itemNo:3 similarity:0.707107
itemNo:4 similarity:0
calcMatchNum
itemNo:0 similarity:1
itemNo:1 similarity:0
itemNo:2 similarity:0.656532
itemNo:3 similarity:0.707107
itemNo:4 similarity:0

となり、calcCosSimでもcalcMatchNumでも同様の結果を得られていることが分かります。
またアイテム0と類似度が一番高いのはアイテム3だということも分かります。

なんだが揚げ足取りみたいになってしまいましたが、この記事自体はレコメンドのアルゴリズムを実際のソースコードや数式などを交えながら説明した数少ない一般紙での記事だと思いますし、LSHやSVD、RBMといった一歩踏み込んだレコメンドの手法も紹介されていて非常に面白いです。とってもすばらしい記事ですので、上のコードとかを参考により多くの人が理解を深めてくれるといいな、と思います。~~修正したら図書券とかもらえるかもしれないし。~~

id:tkngさん、岡野原さん、すばらしい記事をどうも有り難うございます！

遥かへのスピードランナー

シリコンバレーでAndroidアプリの開発してます。コンピュータービジョン・3D・アルゴリズム界隈にもたまに出現します。

WEB+DBプレスの「[速習]レコメンドエンジン」のサンプルプログラムを訂正してみる