2010年6月13日日曜日

グラフラプラシアンで推薦

以前縁あって小町さんと一緒に仕事をさせてもらい論文に名前を載せてもらったのですが、会社だけでなく自宅でもちょっと使いたいなーということもあり、実装してみることにしました。

参考にしたのは以下の論文です。
ラプラシアンラベル伝播による検索クリックスルーログからの意味カテゴリ獲得

元論文と違うのは、インスタンス-パターン行列の要素を単純な頻度から別の尺度に変えている点です。
元々そのまんま実装してみたところ、非常にレアな場合なのですが、ジェネリックパターン1つのみと共起するようなインスタンスがあった場合に、これが上位に出やすくなるという問題が発生し、どうにかできないかなと模索していたところ、小町さんからアドバイスを頂き、それを基に手を加えています。

とりあえず動作検証のためにMovieLens Data Setsを使って実験してみました。

最初にデータのフォーマットをツールの入力形式へ変更。
perl swap.pl < ../ml-data/u.data | LC_ALL='C' sort > mlens.data


#!/opt/local/bin/perl

# user id | item id | rating | timestamp
use warnings;
use strict;

my %dic;
my $file = "../ml-data/u.item";
open (F, $file) or die;
while ()
{
chomp;
my @t = split(/\|/);

unless (defined $dic{$t[0]})
{
$dic{$t[0]} = $t[1];
}
}
close (F);
while (<>)
{
chomp;
my @tokens = split(/\t/);
print $dic{$tokens[1]}, "\t$tokens[0]\t$tokens[2]\n";
}


入力ファイルのフォーマットは次のようにTSV形式で<インスタンス-パターン-評価値>として、インスタンスでソートしておきます。


'Til There Was You (1997) 152 4
'Til There Was You (1997) 178 3
'Til There Was You (1997) 223 1
'Til There Was You (1997) 299 2
'Til There Was You (1997) 342 1
'Til There Was You (1997) 416 3
'Til There Was You (1997) 530 2
'Til There Was You (1997) 532 3
'Til There Was You (1997) 782 2
...


で、実行。

./quetchup -f mlens.data -o test.save

デフォルトでの実行は alpha = 0.0001, iteration = 10, エッジのカットに使う閾値 0.1 としています。

./quetchup -c sample.txt -r test.save | head -50

sample.txt

Snow White and the Seven Dwarfs (1937)


白雪姫がお気に入りとすると、以下のようにディズニー系の映画を上位にレコメンドすることができます。


[Instance]
Snow White and the Seven Dwarfs (1937):0.999801
Cinderella (1950):5.19753e-07
Fantasia (1940):5.06323e-07
Dumbo (1941):4.17243e-07
Beauty and the Beast (1991):3.94127e-07
Aladdin (1992):3.88318e-07
Mary Poppins (1964):3.71035e-07
Jungle Book, The (1994):3.67852e-07
Sword in the Stone, The (1963):3.67118e-07
Lion King, The (1994):3.64219e-07
Pinocchio (1940):3.60772e-07
Robin Hood: Prince of Thieves (1991):3.5665e-07
Aristocats, The (1970):3.51889e-07
Fox and the Hound, The (1981):3.34974e-07
Star Trek VI: The Undiscovered Country (1991):3.24104e-07
Alice in Wonderland (1951):3.19468e-07
Homeward Bound: The Incredible Journey (1993):2.97177e-07
Sound of Music, The (1965):2.97109e-07
Walk in the Sun, A (1945):2.96338e-07
Very Natural Thing, A (1974):2.96338e-07
Bedknobs and Broomsticks (1971):2.93205e-07
Star Trek IV: The Voyage Home (1986):2.90837e-07
Gone with the Wind (1939):2.89412e-07
Nightmare Before Christmas, The (1993):2.85079e-07
Star Trek: Generations (1994):2.8431e-07
Winnie the Pooh and the Blustery Day (1968):2.82242e-07
101 Dalmatians (1996):2.81954e-07
Swiss Family Robinson (1960):2.6257e-07
Aladdin and the King of Thieves (1996):2.54459e-07
Grease (1978):2.53118e-07
African Queen, The (1951):2.52688e-07
Ghost (1990):2.52399e-07
Hunt for Red October, The (1990):2.4501e-07
Miracle on 34th Street (1994):2.42372e-07
Home Alone (1990):2.4004e-07
Top Gun (1986):2.35881e-07
Abyss, The (1989):2.35302e-07
Little Women (1994):2.33329e-07
Old Yeller (1957):2.32874e-07
Pocahontas (1995):2.31783e-07
Mrs. Doubtfire (1993):2.31762e-07
Jumanji (1995):2.31231e-07
Pete's Dragon (1977):2.29198e-07
Christmas Carol, A (1938):2.28481e-07
New York Cop (1996):2.28269e-07
Maltese Falcon, The (1941):2.26072e-07
Goofy Movie, A (1995):2.25177e-07
James and the Giant Peach (1996):2.23962e-07
Star Trek: The Motion Picture (1979):2.23878e-07


ですが、よく見るとスタートレックとかが入り込んでいます。
そこで、次のように嫌いなものリストを用意します。

sample2.txt

Walk in the Sun, A (1945)
Star Trek: Generations (1994)


./quetchup -c sample.txt -n sample2.txt -r test.save | head -50


[Instance]
Snow White and the Seven Dwarfs (1937):0.9998
Cinderella (1950):2.96839e-07
Fantasia (1940):2.81548e-07
Dumbo (1941):2.54658e-07
Aladdin (1992):2.4008e-07
Lion King, The (1994):2.30137e-07
Beauty and the Beast (1991):2.10186e-07
I Don't Want to Talk About It (De eso no se habla) (1993):2.01313e-07
Jurassic Park (1993):1.96396e-07
Coldblooded (1995):1.95535e-07
Robin Hood: Prince of Thieves (1991):1.74025e-07
Fox and the Hound, The (1981):1.71627e-07
African Queen, The (1951):1.69855e-07
Sound of Music, The (1965):1.69781e-07
Mary Poppins (1964):1.64425e-07
Wizard of Oz, The (1939):1.6242e-07
Swan Princess, The (1994):1.56013e-07
Homeward Bound: The Incredible Journey (1993):1.53814e-07
Mamma Roma (1962):1.52174e-07
Good Man in Africa, A (1994):1.50378e-07
Some Like It Hot (1959):1.46221e-07
Citizen Kane (1941):1.42743e-07
Anne Frank Remembered (1995):1.40035e-07
Dances with Wolves (1990):1.36046e-07
It's a Wonderful Life (1946):1.3514e-07
Hunt for Red October, The (1990):1.3501e-07
Young Frankenstein (1974):1.34608e-07
Rebecca (1940):1.32806e-07
Winnie the Pooh and the Blustery Day (1968):1.30989e-07
It Happened One Night (1934):1.30592e-07
M (1931):1.30189e-07
Maltese Falcon, The (1941):1.29532e-07
Lassie (1994):1.28929e-07
Foreign Correspondent (1940):1.28287e-07
Grease (1978):1.2729e-07
Alice in Wonderland (1951):1.23873e-07
Quiz Show (1994):1.22688e-07
Singin' in the Rain (1952):1.22222e-07
Sword in the Stone, The (1963):1.18912e-07
Lawrence of Arabia (1962):1.15236e-07
To Kill a Mockingbird (1962):1.14732e-07
Swiss Family Robinson (1960):1.14698e-07
Drop Dead Fred (1991):1.13925e-07
Vertigo (1958):1.13817e-07
Top Gun (1986):1.12622e-07
Bonnie and Clyde (1967):1.12262e-07
Blue Angel, The (Blaue Engel, Der) (1930):1.10351e-07
Annie Hall (1977):1.09473e-07
Turning, The (1992):1.07052e-07


と、無事スタートレックとか消えてくれました(スタートレック好きな人ごめんなさい!)。
ちなみに、head で出力を絞っているので見えていませんが、出力にはスコア付きのパターンリストも含まれます。
これで、どんなパターンで各インスタンスがつながっているのかも分かりやすいです。

お気に入りリストが1つしかなくても十分な精度が出そうだし、複数あっても無問題。
嫌いなものあればそれに近いものを推薦候補から外しやすい。

この手法で推薦とか悪くないなと思う今日この頃な訳です。

ソースコードを公開したいのですが、Quetchup アルゴリズムは一応特許が取られているはずなので、それがどんな内容か分からないと不安だったりします。。

0 件のコメント: