ナード戦隊データマン

機械学習と自然言語処理についてのブログ

Wikipedia記事のグラフ特徴量を求める

ページランクとは、グラフ特徴量の一つで、ネットワーク上のノードの重要性を判別するための量の一つです。ここでは、igraphというパッケージを用いてページランクを求めます。

事前準備

jawikiのダンプから、jawiki-latest-page.sql.gzとjawiki-latest-pagelinks.sql.gzをダウンロードします。前者がノードであるのに対し、後者はエッジです。

次に、これを以下のようにmysqlへインポートします。

$ mysql -u root -p
mysql> create database jawikipedia;
$ mysql -u root jawikipedia < jawiki-latest-page.sql
$ mysql -u root jawikipedia < jawiki-latest-pagelinks.sql

これは、以下を参考にしています: https://qiita.com/grachro/items/11e59d16a929d27e274e

※ pagelinksのインポートには数時間かかりました。

パイプライン

  1. ページタイトルとページIDを対応付ける。
  2. pagelinksからメモリ上にエッジを落とし込む。(pl_titleはIDに変換)
  3. エッジをグラフに落とし込む。
  4. グラフからページランクを求める。

Note: 実行するにはある程度のメモリが必要です。

コード

from igraph import *
import pickle
import mysql.connector
import os
from tqdm import tqdm
import json

def connect():
    return mysql.connector.connect(
        host = 'localhost',
        port = '3306',
        user = 'root',
        password = input("password:"),
        database = "jawikipedia"
    )

def load_title2id(conn):
    c = conn.cursor(dictionary=True)
    c.execute("select * from page where page_namespace=0")
    row = 1
    out = {}
    while row is not None:
        row = c.fetchone()
        if row is not None:
            idx = int(row['page_id'])
            out[row['page_title'].decode('utf-8')] = idx
    return out

def pagelinks2edges(conn, title2id, debug=False):
    c = conn.cursor(dictionary=True)
    c.execute("select * from pagelinks where pl_namespace=0 and pl_from_namespace=0")
    row = 1
    edges = []
    counter = -1
    maxind  = 0
    pbar = tqdm()
    errors = {}
    while row is not None:
        row = c.fetchone()
        pbar.update(1)
        counter += 1
        if debug:
            if counter >= 1000:
                break
        try:
            fv = int(row['pl_from']),
            tv = int(title2id[row['pl_title'].decode('utf-8')])
            if fv > maxind or tv > maxind:
                maxind = max(fv,tv)
            edge = (fv, tv)
            edges.append(edge)
        except Exception as e:
            errors[counter] = repr(e)
            continue
    pbar.close()
    return (edges, maxind), errors

def save_edges(edges):
    with open("edges.tsv", "w") as f:
        for edge in tqdm(edges):
            f.write(str(edge[0])+"\t"+str(edge[1])+"\n")

def solve_pagerank(edges, maxind):
    G = Graph(directed=True)
    for i in tqdm(range(maxind+1)):
        G.add_vertex(i)
    G.add_edges(edges)    
    pr = G.pagerank()
    with open("pagerank.json", "w") as f:
        json.dump(pr, f)
    return pr

def save_title2id(title2id):
    with open("title2id.json", "w") as f:
        json.dump(title2id, f)

def run():
    conn = connect()
    title2id = load_title2id(conn)
    save_title2id(title2id)
    params, errors = pagelinks2edges(conn, title2id, debug=False)
    save_edges(params[0])
    solve_pagerank(*params)
    

if __name__ == "__main__":
    run()

このように、簡単にページランクを求めることができます。

ページランク何に使えるのか

Wikipediaページの重要性を比較する際に、教師なしの方法を採用したいのであれば、ページランクを使うことができます。

教師ありの方法を使いたい場合は、pagerankは特徴量の一つにすることができます。