March 13, 2012

KDD Cup 2012, Track 1の訳

追記

提出方法が追記されました.

追記終わり

KDD Cup 2012は3/15から.Track 1は

訓練データ(ユーザとアイテムとユーザがアイテムをフォローしたかどうか)とユーザ・アイテムのデータを使って,テストデータ(ユーザとアイテム)が与えられてたら推薦度を推定する,

というタスク.http://www.kddcup2012.org/c/kddcup2012-track1 をざっくり翻訳.誤訳なければいいけど.Tencent WeiboはTwitterとだいぶ似てるけどちょっと違うみたい.


データセット


Item, Tweet, Retweet, Comment, Followee/Followerの定義とデータセットについて.

Item


アイテムはTencent Weiboのユーザ.ユーザは個人とか組織とかグループ.アイテムはカテゴリに整理されている.カテゴリは階層構造をもつ.

たとえば Dr. Kaifu LEE, http://t.qq.com/kaifulee は
  •  X.science-and-technology.internet.mobile
  •  X.business.Invest.Angel Investment
の2つのカテゴリに属している.Xはルートカテゴリ.

階層は「.」で区切られていて,カテゴリの情報はモデル推定に使えるかも.たとえばPeterさんがkaifuleeさんをフォローしてる時,Peterさんはkaifuleeさんが属しているカテゴリのアイテムに興味ありそう,ついでにkaifuleeさんのカテゴリの親カテゴリのアイテムにも興味ありそうだとか.

Tweet


マイクロブログのメッセージのアクション.投稿されたメッセージそのもの.

Retweet


ユーザは他のユーザのツイートにコメントをつけてリツイートできる.フォローされてるほかのユーザに共有.

Comment


ツイートに対してコメントできる.コメントは他のユーザにはプッシュされない.コメント履歴には残る.Twitterにはないかな?

Followee/follower


AがBをフォローしてたら,AはBのフォロワー(follower),BはAのフォロウィー(followee).

データセットについて


データセットはユーザに対するアイテムの推薦とフォローの履歴.めちゃでかい.プロフィールやソーシャルグラフ,アイテムカテゴリの情報といった様々なドメインの情報がある.

データセット内のユーザの数は数百万.いろんな情報(デモグラフィック,プロフィールキーワード,フォローヒストリーとか)があるから,いい推定モデルできるんじゃないかな.ユーザのプライバシーを守るため,ユーザとアイテムのIDは匿名化してる.更に,情報は,中国語の場合でも,ランダムな番号にしてる.だから中国語わかんなくてもカンケーない.推薦のタイムスタンプは与えられてます.



ファイル


7つのテキストからなる2つのデータセット.各項目はタブ区切り.

a) 訓練データ rec_log_train.txt
b) テストデータ rec_log_test.txt
(UserId)\t(ItemId)\t(Result)\t(Unix-timestamp)
  • (UserId) : ユーザID
  • (ItemId) : アイテムID
  • (Result) : 1か-1.1はUserIdが推薦されたアイテムItemIdをアクセプトしてフォローしたもの.-1はリジェクト.テストデータのResultは全部-1に設定されている.
  • (Unix-tmiestamp) : タイムスタンプ
% head rec_log_train.txt 
2088948 1760350 -1 1318348785
2088948 1774722 -1 1318348785
2088948 786313 -1 1318348785
601635 1775029 -1 1318348785
601635 1902321 -1 1318348785
601635 462104 -1 1318348785
1529353 1774509 -1 1318348786
1529353 1774717 -1 1318348786
1529353 1775024 -1 1318348786
1853982 1760403 -1 1318348789


c) ユーザとアイテムのデータ

i. ユーザプロフィール user_profile.txt
(UserId)\t(Year-of-birth)\t(Gender)\t(Number-of-tweet)\t(Tag-Ids)
  • (UserId) : ユーザID
  • (Year-of-birth) : 生まれ年.サービスに登録した時に選択
  • (Gender) “0, 1, 2” : わからない,男,女
  • (Number-of-tweet) : ツイートの数
  • (Tag-Ids) : 興味のあること.ユーザが選ぶ.山登りに興味があったら「山登り」を選ぶ.何も選ばない人もいる.「tag-id1;tag-id2;...;tag-idN」ってフォーマット.なにも選ばなかったら「0」
% head user_profile.txt 
100044 1899 1 5 831;55;198;8;450;7;39;5;111
100054 1987 2 6 0
100065 1989 1 57 0
100080 1986 1 31 113;41;44;48;91;96;42;79;92;35
100086 1986 1 129 0
100097 1981 1 75 0
100100 1984 1 47 71;51
100101 2003 1 31 0
100116 1988 2 39 35
100117 2009 2 37 0


ii. アイテム item.txt
(ItemId)\t(Item-Category)\t(Item-Keyword)
  • (ItemId) : アイテムID
  • (Item-Category) “a.b.c.d” : 階層的なカテゴリ.aはbの親カテゴリ…
  • (Item-Keyword) “id1;id2;…;idN” : キーワード.ウェイボの対応したプロフィールから抽出.数字.
% head item.txt 
2335869 8.1.4.2 412042;974;85658;174033;974;9525;72246;39928;8895;30066;2245;1670;85658;174033;6977;6183;974;85658;174033;974;9525;72246;39928;8895;30066;2245;1670;85658;174033;6977;6183;974
1774844 1.8.3.6 31449;517124;45008;2796;79868;45008;202761;2796;101376;144894;31449;327552;133996;17409;2796;4986;2887;31449;6183;2796;79868;45008;13157;16541;2796;17027;2796;2896;4109;501517;2487;2184;9089;17979;9268;2796;79868;45008;202761;2796;101376;144894;31449;327552;133996;17409;2796;4986;2887;31449;6183;2796;79868;45008;13157;16541;2796;17027;2796;2896;4109;501517;2487;2184;9089;17979;9268
1775000 1.4.2.4 259580;626835;12152;6183;561;10666;12152;6183;561;60774;21206;561;160212;539;2225;320443;12152;6183;561;10666;12152;6183;561;60774;21206;561;160212;539;2225;320443
1775024 1.4.1.4 498354;61029;60774;12318;3825;465;5788;6183;561;61029;539;71940;335;27;60774;12318;3825;465;5788;6183;561;61029;539;71940;335;27
1774455 1.4.1.2 155009;345081;12203;6183;561;9642;12203;561;3203;40075;539;345081;26124;10638;490970;12203;6183;561;9642;12203;561;3203;40075;539;345081;26124;10638;490970
1775040 1.4.2.2 100947;97714;12203;6183;3203;45782;12203;3203;46868;13;97714;12203;6183;3203;45782;12203;3203;46868;13;97714
1774505 1.4.9.2 254337;195099;974;12203;6183;974;11354;12203;974;37888;17713;62372;454;974;12203;6183;974;11354;12203;974;37888;17713;62372;454;974
1774776 8.1.4.2 239661;974;46479;17713;974;14461;46479;17713;974;31325;610;46441;143118;208450;5647;35944;70488;307170;175621;326588;46479;17713;974;14461;46479;17713;974;31325;610;46441;143118;208450;5647;35944;70488;307170;175621;326588
495072 8.1.4.2 296259;596521;4861;4385;31325;31693;12152;974;35133;205881;474444;1100;115394;76462;636390;112571;75629;4861;35639;4385;31325;136353;87610;93388;159442;146683;300971;4861;4385;31325;31693;12152;974;35133;205881;474444;1100;115394;76462;636390;112571;75629;4861;35639;4385;31325;136353;87610;93388;159442;146683;300971
2076876 1.4.9.2 239661;974;428257;6183;68271;974;6254;46479;17713;36169;6183;68271;974;50048;68271;125744;41791;30825;31325;46479;17713;60765;490251;3824;22793;102745;288673;6183;68271;974;6254;46479;17713;36169;6183;68271;974;50048;68271;125744;41791;30825;31325;46479;17713;60765;490251;3824;22793;102745;288673


iii. アクション user_action.txt
(UserId)\t(Action-Destination-UserId)\t(Number-of-at-action)\t(Number-of-retweet )\t(Number-of-comment)
  • (UserId) : ユーザID
  • (Action-Destination-UserId) : 相手のユーザID
  • (Number-of-at-action) : アクションの数
  • (Number-of-retweet ) : リツイートの数
  • (Number-of-comment) : コメントの数
たとえば
“A B 3 5 6”
だったら,AのBへの @つきアクション(リプライ?メンション?)が3回,リツイート5回,コメントが6回.
% head user_action.txt 
1000004 1000004 0 3 4
1000004 1290320 0 3 0
1000004 1675399 0 1 0
1000004 1760423 0 1 0
1000004 1774718 0 1 0
1000004 1774862 0 1 0
1000004 1775076 0 1 0
1000004 1837210 0 1 0
1000004 1928681 0 1 0
1000004 1954203 0 1 0


iv. ユーザSNS user_sns.txt

ユザーのフォロー履歴
(Follower-userid)\t(Followee-userid)
  • (Follower-userid) : フォローしたユーザのID
  • (Followee-userid) : フォローされたユーザのID.
% head user_sns.txt 
1000001 373407
1000001 461001
1000001 692475
1000002 1760423
1000002 1760426
1000002 1760642
1000002 1774712
1000002 1774861
1000002 1774957
1000002 1774963


v. ユーザキーワード user_key_word.txt

ツイート,リツイート,コメントから抽出したキーワード
(UserId)\t(Keywords)
  • (UserId)
  • (Keywords) “kw1:weight1;kw2:weight2;…kw3:weight3” : weightが大きいほどユーザは興味が有りそう.Integer.
% head user_key_word.txt 
1000000 183:0.6673;2:0.3535;359:0.304;363:0.1835;377:0.1831;10:0.1747;58:0.1725;127:0.1624;459:0.1482;54:0.142;330:0.1361;1480:0.1358;40:0.1136;672:0.1037
1000001 92:1.0
1000002 112:1.0
1000003 154435:0.746;30:0.3902;220:0.2803;238:0.2781;232:0.2717;1928:0.2479
1000004 118:1.0
1000005 157:0.484;25:0.4383;198:0.3033;185:0.3012;31:0.2991;80:0.2971;203:0.241;34:0.2347;95:0.2327;37:0.214
1000006 277:0.7815;1980:0.4825;146:0.175;103:0.1475;83:0.1382;107:0.1061;892:0.1019
1000007 4069:0.6678;2557:0.6104;137:0.4261
1000008 16:0.7164;154:0.3278;164:0.3222;246:0.2258;17:0.1943;14:0.1789;340:0.1789;366:0.1719;139:0.1587;279301:0.1139;484:0.1083;116:0.1055;193:0.1027



出力

各テストデータに対して
(UserId)\t(ItemId)\t(Prediction)
  • (UserId) : ユーザID
  • (ItemId) : アイテムID
  • (Prediction) : -1 ~ 1の値.点数が高いほど,より推薦されやすい.


評価


平均適合率で量る
ap@n = Σ k=1,...,n P(k) / (number of items clicked in m items)
  • 分母が0だったら結果は0
  • P(k)はkで足切りしたアイテムの適合率.つまりk番目までのアイテムの中でクリックされたアイテムの割合.一つもフォローされてなかったらP(k)は0
  • n=3がデフォルト
たとえば
  1. 5つのアイテムが推薦されて,ユーザが1,3,4番目をクリックしたら, ap@3 = (1/1 + 2/3)/3 ≈ 0.56
  2. 4つのアイテムが推薦されて,ユーザが1,2,4番目をクリックしたら ap@3 = (1/1 + 2/2)/3 ≈ 0.67
  3. 3つアイテムが推薦されて,ユーザが1,3番目をクリックしたら ap@3 = (1/1 + 2/3)/2 ≈ 0.83

各ユーザに対する平均適合率平均がスコア

AP@n = Σ i=1,...,N ap@ni / N

いまいちどうやって出力したらいいかわからん.テストデータは3/15公開.


提出方法


The rec_log_test.txt にはリーダーボード(順位表)用セットと評価用セットが含まれている.ファイルは一時的にソートされている.タイムスタンプが1321891200未満のデータはリーダーボードに用いられ,1321891200以上のデータは評価に用いられる.ゴールはそれぞれのセットの中であるユーザに推薦されたアイテムがユーザによってフォローされかどうかを推定してやること.

出力サンプルはダウンロード可.2種類のフォーマットが利用できる.一つはヘッダあり2列のcsvファイル(サイズは大きくなる).一つはヘッダなし1列のcsvファイル(サイズは小さくなる).圧縮して提出することが望ましい.アップロードされたら10〜20秒後にリーダーボード用のデータにスコアが付けられ,結果がリーダーボードに表示される.

2列csvフォーマットでは,1列目はユーザID(リーダーボード用,評価用,それぞれでソートされている),2列目は0~3個のスペース区切りの推薦すべきアイテムID(e.g. "647356 458026 1606609")を.n=3の平均適合率が計算される.提出ファイルのユーザIDの順番はサンプルと同じ順番に正確に対応させなくてはならない.すなわち,リーダーボードセットの結果は評価セットの前におき,それぞれのデータ内ではユーザIDでソートされていなくてはならない.

1列フォーマットでは,単純にスペース区切りでアイテムを.順番は2列の場合と同じ.

% head rec_log_test.txt
1449438 1394821 0 1321027200
1449438 372323 0 1321027200
1525431 1774707 0 1321027200
1587150 1774422 0 1321027200
1587150 1774934 0 1321027200
2064344 1505267 0 1321027200
2081969 1760410 0 1321027200
2141596 1760376 0 1321027200
2359607 1606609 0 1321027200
2359607 2105484 0 1321027200

2列
% head sub_small_header.csv 
id,clicks
100001,647356 458026 1606609
100004,647356 1606574 1774568
100005,1606574 1774532 586592
100009,647356 1760327 1606574
100010,458026 2105511 713225
100011,1774594 1774717 1774505
100012,458026 2105511 727272
100013,1870054 514413 1760401
100014,859545 2167615 715470

1列
% head sub_min.csv 
647356 458026 1606609
647356 1606574 1774568
1606574 1774532 586592
647356 1760327 1606574
458026 2105511 713225
1774594 1774717 1774505
458026 2105511 727272
1870054 514413 1760401
859545 2167615 715470
647356 458026 1606574