Hatena::ブログ(Diary)

konisimple log RSSフィード

はてなブログに移転しました!

2010年05月14日

jaccard係数によるerockr検索キーワードの分析

昨日やったtanimoto係数によるerockrの検索キーワード間の類似度の計算の続き。

昨日はjaccard係数よりtanimoto係数のほうが名前に親近感がもてるとかいって、tanimoto係数がいいとか言ったが、jaccard係数の方が得られる数値がイメージしやすい。jaccard係数は「和集合に対する積集合の割合」で表されるものなので、頭にベン図が思い浮かぶ。

さて、早速jaccard係数でerockrの表示ランキング上位20位間の類似度を考えてみた。

結果

f:id:konisimple:20100515011608p:image

種類の違う「エロ」

まず際立って目立つのが「エロ」だ。

全ての組み合わせで類似度が低いという評価が出ている。「エロ」だけは人間の名前ではなく、少し種類の違うデータなのでこれは妥当だろう。

類似度の高い組が多いアイテム

新垣結衣佐々木希上戸彩南明奈長澤まさみ深田恭子ほしのあき

これらは知名度も高く、万人受けする人たちのようだ。浅く広くまんべんなく多くのユーザに見られている。

類似度の低い組が多いアイテム

堀北真希堀井美月篠崎愛鈴木茜安めぐみ

堀北真希以外は、知名度が低く、かなり排他的な傾向が強い。

特に篠崎愛はひどいw

得られたデータのうち、使えそうなデータ

アイテム類似度の高いアイテム考察もどき
堀井美月篠崎愛川村ゆきえ、仲村みゆロリ巨乳
篠崎愛堀井美月ロリ巨乳
安めぐみ井上和香磯山さやか深田恭子なんか同じ香りの人たちw
蒼井優綾瀬はるか小阪由佳広末涼子深田恭子清純派?

結論

この方法はロリ巨乳系の人たちの類似アイテムを探すのに向いているw

類似度の分布

Rで、erockrの検索キーワード上位20件の類似度(jaccard係数)の分布をステムアンドリーフで書いてみたところ、以下の通り。

422356666788999
50011222234444455666678888889999
60000001111111122333333333444455556666666777777777788899999999
700000111111111111222222222233334444445555555556666667777777777777888888889999999
800000011111111111111122222222223333333334444445555555666666666777777777777888888889999999999
900000000111111111111122222222223333333334444444555555666666666777778889999
10000111112222223333444455566666777777777778888999999
11001222233344445688899
121134669
1399
144
152
summary

Min. 1st Qu. Median Mean 3rd Qu. Max.

0.04246 0.07064 0.08315 0.08362 0.09519 0.15270

2010年05月13日

tanimoto係数によるerockrの検索キーワード間の類似度の計算

amazonのレコメンデーションシステムのような、大量に蓄積したユーザが表示したり購入したデータから、ユーザの行動の傾向を統計学的に分析して、アイテムを推薦するような仕組みを、協調フィルタリングという。

協調フィルタリング - Wikipedia

これに興味を持ったことをtwitterに書いたら、「集合知プログラミング」という本を@clavicle_に紹介された*1ので、買ってみた。

集合知プログラミング

集合知プログラミング

内容は僕のような統計とか久しく使ってないような人間でもとてもわかりやすく、とても興味を持った。

erockrに協調フィルタリングを!

そして勉強も兼ねてerockrに「このアイドルを見た人はこの人も見ています」というレコメンデーションを実装してみることにした。

それで実はここ一週間ほど、以下のようなログを取ってデータを集めた。

これが大体25万行ほど集まった。

erockrの場合、ユーザが見るアイテム(=アイドル)の数はとても多い(データセットが「疎」)ので、アイテムベースのレコメンデーションにする。

レコメンデーションの流れ

大体以下のような流れでレコメンドする。

  1. アイテム間の類似度を計算。類似度の評価方法はいくつかあり、ユークリッド距離、ピアソン相関係数、Jaccard係数、Tanimoto係数などがある。
  2. 類似度で重み付けしてアイテムの推薦順番を決める。

類似度の計算

今日は類似度の計算を行ってみることにした。

いろいろな方法があるが、erockrの場合、ログはユーザがアイテムを見たというデータしかないので、

  • ページを見たら1
  • ページを見てなかったら0

ということになるので、ユークリッド距離、ピアソン相関係数よりも、Jaccard係数、Tanimoto係数などが向いている*2

ここではTanimoto係数を用いる*3

ここでMySQL上のログのテーブルから、計算に必要な表をつくる。

もとの表
uidkeyword
ユーザ1新垣結衣
ユーザ3新垣結衣
ユーザ4新垣結衣
ユーザ1上戸彩
ユーザ2上戸彩
ユーザ5上戸彩
作りたい表

新垣結衣上戸彩の類似度

s_ands_xors_or
12334564567

Tanimoto係数を求めるには、和集合、積集合、排他的論理和の集合を求めればよさそうだから*4

投げるSQL

上の表を作るために、以下のSQL文を投げる。

SELECT
(SUM(CASE WHEN tmp.a+tmp.b=2 THEN 1 ELSE 0 END) ) s_and,
(SUM(CASE WHEN tmp.a+tmp.b=1 THEN 1 ELSE 0 END) ) s_xor,
(SUM(CASE WHEN tmp.a+tmp.b>0 THEN 1 ELSE 0 END) ) s_or
FROM(
	SELECT
	uid,
	CASE WHEN SUM(CASE WHEN keyword='{$keyword[0]}' THEN 1 ELSE 0 END)>0 THEN 1 ELSE 0 END a,
	CASE WHEN SUM(CASE WHEN keyword='{$keyword[1]}' THEN 1 ELSE 0 END)>0 THEN 1 ELSE 0 END b 
	FROM `log`
	WHERE (keyword='{$keyword[0]}' OR keyword='{$keyword[1]}') AND uid!=''
	GROUP BY uid
)tmp
LIMIT 0,1

もっとスマートな書き方がありそうだけど、現状では1秒以内に帰ってくるし、期待通りに動くのでまぁいいやw

CASE文便利だなぁ。

とりあえず今日はここまでやりました。

結果は以下の通り。

f:id:konisimple:20100514034533p:image

青と赤は、それぞれ平均からの差が標準偏差*0.3以下、以上です。


ここまでやってだんだん本を読んだ直後の感動が薄れて、そして、この表が出来てなんだか満足してしまったので、ここまでにしておきます。

考察とかはまたそのうちやることにします。

注意

まだ20ページくらいしか読んでないので、ここらへん間違ってたらごめんなさい。

本読んでたらコード書きたくなっちゃって我慢できなくて書いちゃいました。

自分でも何やってるかわかんないなw

上で、全体の平均と全体の標準偏差を出してるけど、色を塗るなら、各アイテムごとの平均と標準偏差でやらないと意味ないような気がしてきた。

*1Twitter / クラビクル: @koni 集合知プログラミングなんか読むと結構面白いですよ

*2:たぶん。

*3:Jaccard係数より名前に親近感が持てたからです。何が違うかはよく知りませんwTanimoto係数もJaccard係数も計算方法はほとんど同じなので後から簡単にかきかえられる。

*4:tanimoto係数については、tanimoto係数 - 長岡技科大 自然言語処理研究室を参考にしました。

2010年04月10日

産経新聞のiPhoneアプリのパケット解析してみた

産経新聞(iPhone版)というのがあります。

これは無料で産経新聞が紙の紙面の構成のまま読めるというとても便利なアプリです。

今回、暇だったので、WireSharkというバケット解析ソフトでiPhoneウェブとの通信を盗聴?してみました。

産経新聞iPhoneアプリの仕組み

最新の新聞データを得る(current_edition.xml)

バケット解析の結果、産経新聞アプリを起動するとまず、決まったURLにアクセスする。ここには最新の紙面の情報があるxmlURLが書いてある。

http://www.sankei.co.jp/netview/iphone/current_edition.xml

<CurrentEdition Root="2010_04_10_i" XMLFileName="2010_04_10_i.xml"/>
その日の新聞の目次(日付/日付_i.xml)

上のxmlを見て、この日の新聞の何面にどの情報が書いてあるかとかの情報を得る。なんかxmlだと新聞社のウェブサイトよりとてもセマンティックって感じ。

http://www.sankei.co.jp/netview/iphone/2010_04_10_i/2010_04_10_i.xml

<Edition Newspaper="iphone" Name="2010_04_10_i" Date="2010/04/10" Version="1.01" FrontPageURL="" PageWidth="38" PageHeight="51.5">
 <Sections>
  <Section Name="総合" Index="3"/>
  <Section Name="国際" Index="4"/>
    ...
  </Sections>
 <Pages>
  <Page ID="12984" XMLLocation="pages_xml/page12984_netviews1958.xml" PageNumber="1" ThumbnailURL="thumbnails/page1.jpg" Section="総合"/>
 </Pages>
</Edition>
ページ情報

次は上のxmlからページの画像の格納されているURLを示すxmlにアクセスする。

http://www.sankei.co.jp/netview/iphone/2010_04_10_i/pages_xml/page12984_netviews1958.xml

<Pages ID="12984" PageTitle="" PageNumber="1">
 <LevelImages Level1Partitions="1" Level2Partitions="2" Level3Partitions="4" Directory="pages_images/page12984_netviews1958/" FileType="jpg" BasePixelWidth="372" BasePixelHeight="504"/>
 <Articles/>
 <Regions/>
 <RichMedias/>
 <Titles/>
 <Links/>
</Pages>
新聞紙面の画像データ

実はこれでもうすべての画像データにアクセスできるようになった。

まず、画像データの基本のURL

http://www.sankei.co.jp/netview/iphone/2010_04_10_i/pages_images/page12984_netviews1958/lv1_0_0.jpg

である。

あとは末尾のファイル名を変えればよい。

下にファイル名と内容を一覧にしてみた。

ファイル名内容
lv1_0_0.jpgページ全体
lv2_0_0.jpgズームした左上
lv2_0_1.jpgズームした左下
lv2_1_0.jpgズームした右上
lv2_1_1.jpgズームした右下
lv3_0_0.jpgもっとズームした左上
lv3_0_1.jpgもっとズームした中央
lv3_0_2.jpgもっとズームした右上
......
lv3_3_3.jpgもっとズームした右下

なるほど。ズームのレベルに応じて3つのファイルに分けてるんですね。

まとめ

というわけで、これを利用すれば別にiPhoneアプリ使わなくても産経新聞がPC上で読めるアプリも簡単に作れそうですね。

ウェブアプリとかも作れそうですね。

ここらへんもっとちゃんとガードされてるのかと思いましたが、意外に寛容でした。

まぁどう考えても著作権的にアウトなので、そんなことする人はいないと思ってるんでしょうね。

パスワードはないにしてもアプリによる正規のアクセスかどうか認証する*1ぐらいはすればいいのにという気はします。

まぁそういうのが一切ないので不正アクセス防止法とかにはひっかからないはず。

パケット解析のおもしろさがわかる(?)、産経新聞iPhoneアプリはどういう仕組み?っていう話でした。

追記(10/4/11 05:12)

結局書いちゃった。

これでいいのか!産経さん!紙面データダダ漏れですよ!(PHPで紙面を得てみる) - konisimple log

*1:チャレンジレスポンス認証してセッション処理するとか