スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Wikipediaの記事でPageRankを計算してみた。

PageRankの記事の続きです。

【Python】PageRankアルゴリズム
http://zaburoapp.blog.fc2.com/blog-entry-38.html


PageRank実装だけして終わるのももったいないので
Wikipediaのページ内でPageRank計算してみました。

コードはこちら
zaburo-ch/wikipedia_analysis
https://github.com/zaburo-ch/wikipedia_analysis

前に作ったwikipedia.pyのコードとまとめてレポジトリにしました。

pagerank_wiki.pyを実行すると次のような動作をします。
http://dumps.wikimedia.orgより1日分のデータを取得
・国コードがjaのもののうち閲覧数上位10000ページを取り出す
・各ページの記事内のリンクをエッジとした有向グラフつくる
・有向グラフ内でPageRankを計算し大きい順に出力する

やってることはかなりwikipedia.pyに近いですが、
見返してみるとあまりにもなコードだったのでかなり書き換えました。
他にもリンク抽出にHTMLParser使ってみたりいろいろ変えてます。

前のやつと違って計算の部分にそれほど時間がかからないので
スペック次第ですが少なくとも寝てる間くらいには終わると思います。
リンク解析もこっちのほうがかなり早いです。

さて、肝心の実行結果はこんな感じです。
pagerankwikiresult.png
wikipedia_analysis/pagerank_wiki_data/result.txt

「特別:カテゴリ」がぶっちぎりで大きいですね。
確認してみたところほぼ全てのページの一番下に
「特別:カテゴリ」へのリンクがあったのでたぶんそのせいです。
「Wikipedia:出典を明記する」とかもこの類いかな。

「日本」や年がおおいのは人とか何かの作品の記事の
テンプレート化している右の枠内で登場することが多いためだと思います。

テレビ局が上位に多いのはテレビ番組からほぼ確実にリンクされているのと
閲覧数上位10000ページで限定しているため
そのなかでテレビ番組が多かったためではないかと考えています。

上位はほとんどが誰でも知っているような一般的な言葉なんですが、
101位のインターネット・ムービー・データベースってやつ、
全然何のことかわからないです。
「集英社」とか「台湾」より上なので、
かなり多くページがここにリンクしてるはずなんですが、
これどんなページからリンクされてるんでしょう?

全体的にPageRankはWikipediaのページの重要性判断としては
あまり向いていないように思いました。
WikipediaにはPageRankの基本的な考え方が合ってないですしね。
ほかのWebサイトでも試してみればもっと面白い結果が得られるかもしれません。
機会があればやってみたいと思います。
スポンサーサイト

【Python】PageRankアルゴリズム

PageRankというアルゴリズム、
以前からなんとなくは知ってはいたのですが、
ランダムサーファーモデルで計算する方法を聞いて、
めちゃくちゃ賢いなこれーって思ったので実際にやってみました。

ひとまずPageRankについて調べたことを纏めます。

PageRankは基本的に次の2つの考え方でページの重要度を推定します。
・多くのページからリンクされているページの質は高い
・質の高いページからリンクされているページの質は高い

これを数学的に考えるのにランダムサーファーモデルを利用します。
ランダムサーファーモデルでは
ページのリンク関係を有向グラフとして考え、
人(サーファー)にこの有向グラフをランダムに辿らせたとき、
人が居る確率が高いページを重要とします。

まず、ページの総数をNとし、N次正方行列M
M[i][j] = ページjにいるサーファーがページiに移動する確率
と定義します。
例えばページ0にページ1とページ5へのリンクしかないとすると、
サーファーはランダムに移動するので
M[i][0]は i=1or5 のとき1/2 となりそれ以外のiでは0となります。

また、ベクトルP(t)を時刻tに各ページに人がいる確率とすると
P(0)は全ての要素が 1/N のベクトルとなり
P(t+1)はMP(t)の積を取ることで計算できます。

有向グラフが強連結のとき、この遷移を無限に繰り返すことで
Pはtに依らない一定の値に収束します。よってこのP
M P = P
の解を要素の和が1になるよう正規化してあげることにより求められます。

このPの大きさが各ページの重要度となります。

----
行列計算において Ax = λx を解く、というのは固有値問題と言って
色々な方法が考えられているらしいのですが、ここについては
行列計算における高速アルゴリズム
http://www.cms-initiative.jp/ja/events/0627yamamoto.pdf

こちらのページが詳しいです。
Pythonではscipy.sparse.linalg.eigsを使うと
Implicitly Restarted Arnoldi で計算してくれます。
ただ、M P = P を解くだけのためにこれらを使うのが速いのかは
勉強不足で僕もよくわかっていません。
----

実際のウェブページでは、ページ間の関係を有効グラフにしても
必ずしも上で述べたような強連結になるわけではありません。
そのため「一定の確率でサーファーはリンクを辿らずにランダムに移動する」
という考えを新たに導入します。その時はMにあたるものを
全ての要素が 1/N である N次正方行列Uと普通にリンクを辿る確率αを用いて
M + (1-α)U) として計算することによってPが求められます。


次の図のようなリンク関係にあるページのPageRankを
Pythonを利用して実際に計算してみます。
正しく計算できれば図の通りの値が得られるはずです。

Linkstruct2.gif

The original uploader was Gnix at English Wikipedia[GFDL or CC-BY-SA-3.0]


コードはこちら
zaburo-ch/wikipedia_analysis/master/pagerank.py

get_pagerankではScipyを用いて固有ベクトルを計算しています。
get_pagerank_simpleではもっと単純に
P(0)に何度もMをかけていき、
かける前との差が十分小さくなるまで繰り返しています。

実行結果はこんな感じです。
pagerankresult.png

図の値とかなり一致していますね!
2つの方法どちらもほぼ同じ値になっているので
get_pagerank_simpleの方法でも十分実用に足りそうです。

Mac OS Xで時々ジェスチャーが反応しなくなる

普段ウインドウの切り替えはMission Controlでやっているのですが、
ときどきジェスチャーが反応しなくなってしまって、
仮想デスクトップの切り替えもできなくなるものですから
再起動しなければならなくなる、というのが近頃起こります。

原因はよくわからないのですが、
OSまるごと再起動しなくてもDockを再起動させてやるだけで
なんとかなるみたいです。

ps -x | grep Dockで出てきたPIDを指定してkillしてやると
自動で起動してくれるようなのでこれで済ませていますが
面倒なので実行ファイルへの変換の勉強がてら
ちょっと書いてアプリにしてみました。

a.png
こんな感じでDockに配置して使っています。

アイコン画像は以下のものを利用させて頂きました。
http://www.easyicon.net/language.ja/1088483-stop_icon.html

ソース等はこちら
https://github.com/zaburo-ch/DockKiller

こちらからダウンロードしてご利用ください↓
DockKiller-1.0.dmgをダウンロード

Wikipediaのページ解析に使ったpythonコード

すっかりわすれていましたがソースコードです。
とりあえずpython触ってみようくらいの気持ちで書いたコードなので
pythonに慣習みたいなものがあるならたぶんそれには従えていません。
multiprocessing、numpy、pandasあたりをちゃんと使えば
格段に早くすることもできるかもしれません。やんないけど。

python wikipedia.py 20141101
のようにして日付指定して使います。

以下のようなことをやってます。
・http://dumps.wikimedia.orgから1時間ごとの閲覧数のデータを1日分取ってくる
・国コード(?)がjaの物だけ抽出する
・標準ライブラリのCounterで各ページの1日分の閲覧数をカウントする
・閲覧数上位10000ページを取り出す
・1ページずつ開き記事内の/wiki/で始まるリンクを抽出する
・リンクがあれば距離1なければINFとして(ディクショナリで)隣接行列をつくる
・ワーシャルフロイド法で全点間最短距離を求める
・ソートして表示


Gistを使ってみました。綺麗に表示してくれますね。
過去の物をGistに置き換えたりはしませんが
今後はできるだけこれをつかっていこうと思います。

Wikipediaのアクセス上位10000ページの距離を計算した話

先日の記事の続きです。

Wikipediaでリンクを辿って遊ぶ
http://zaburoapp.blog.fc2.com/blog-entry-24.html


今回探したのはWikipediaに存在する記事のうち
最も距離のはなれている記事の組み合わせです。

ここで言う距離とは、ある記事から記事内のリンクのみを辿って行く時
何回リンクを踏めばその記事に辿り着くかを表した数字です。
複数あるルートのうち最も短いものをその組の距離としました。

さて、Wikipediaについてですが、
Wikipedia:全言語版の統計
http://ja.wikipedia.org/wiki/Wikipedia:%E5%85%A8%E8%A8%80%E8%AA%9E%E7%89%88%E3%81%AE%E7%B5%B1%E8%A8%88

によれば、2014年10月17日現在
純記事数は全言語総計でなんと33,448,472もあるそうです。
日本語のものだけで930,619もあるので
これをすべて解析するとなると人生が終わるまでに
計算し終わるかという問題が出てきます。

というわけで今回は、日本語版Wikipediaの記事のうち
ある日の閲覧数が上位の記事を一定数とって来て
その記事のみを対象にページ間距離を計算しました。

技術的なことは後日記事にするとして
早速結果を書いていきたいと思います。

まず2014年9月1日の閲覧数上位1000位に限定した場合の結果。
上位20位のみを抜粋しました。
---------------------------------------------------------

List of longest distance between Wikipedia pages
20140901 : Page view Top 1000

1: 8 続柄 -> 近江友里恵
2: 8 続柄 -> たちかぜ自衛官いじめ自殺事件
3: 8 国鉄105系電車 -> たちかぜ自衛官いじめ自殺事件
4: 8 七草 -> 近江友里恵
5: 8 七草 -> たちかぜ自衛官いじめ自殺事件
6: 8 カルトの集団自殺 -> 近江友里恵
7: 8 カルトの集団自殺 -> たちかぜ自衛官いじめ自殺事件
8: 8 特別:最近の更新 -> 近江友里恵
9: 8 特別:最近の更新 -> たちかぜ自衛官いじめ自殺事件
10: 8 カツオノカンムリ -> 近江友里恵
11: 8 カツオノカンムリ -> たちかぜ自衛官いじめ自殺事件
12: 8 城井鎮房 -> たちかぜ自衛官いじめ自殺事件
13: 8 奇皇后 -> 近江友里恵
14: 8 奇皇后 -> たちかぜ自衛官いじめ自殺事件
15: 8 標準偏差 -> 近江友里恵
16: 8 標準偏差 -> たちかぜ自衛官いじめ自殺事件
17: 8 青春18きっぷ -> たちかぜ自衛官いじめ自殺事件
18: 8 特別:検索 -> 近江友里恵
19: 8 特別:検索 -> たちかぜ自衛官いじめ自殺事件
20: 8 龍虎 -> たちかぜ自衛官いじめ自殺事件

---------------------------------------------------------

たちかぜ自衛官いじめ自殺事件の存在感が半端ないですね。
8回リンク踏むだけでいけちゃうということで
案外短くてがっかりしました。
105位まで距離8がありその後2500位くらいまで距離7が続きます。

思った以上に大したことが無い結果が出てしまったので
上位10000ページでもやりたいところですが、
上位1000ページでさえ20分程度時間がかかっていて、
最短距離の計算につかったアルゴリズムの計算量がO(n^3)なので
約1000倍の時間がかかることになります。

終わるまでの時間を計算してみた結果、
まあ現実的な時間で終わるだろうという数字が出たので
ここ数日ずっとパソコンをフル稼働させて計算していました。

そして、その結果が今日、出ました!
利用したデータは2014年10月1日の閲覧数上位10000ページ。
要した時間なんと261時間!
その結果は!

保存できませんでした!

というのも使ったパソコンには4GBしかメモリが積まれていないので
ターミナルの出力をコピーしようとした瞬間
ターミナルがフリーズして永遠の眠りについてしまいました。
何とかログの復旧を試みたのですが
89129689位以降というまったく意味のないデータしか復元できませんでした。

最も離れている距離は6だったのは確認しました。
1000ページの時より小さい結果となりましたが、
ページが増える事で新しいより短いルートが生まれたのだと思います。

結果が公開できないのは大変残念ですが、
そもそもいけないページを除けば、
6回リンクを踏むだけで大体のページ同士はいけてしまうというのは
10000ページに限られてるとはいえなかなか面白い結果だと思います。
普段みるようなページは大体10000ページの中に含まれていますしね。

250時間以上ずっと電源をつけて、ファンがまわるほど計算させていたので
使ったMacbook Airのバッテリーが心配になりました。
二度とやりません!

詳しい方法等はソースコードとともに後日記事にしたいと思います。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。