はじめに
この実験では、Wikipedia 記事内のリンクのグラフを分析して、固有ベクトル中心性に基づいて相対的な重要性によって記事をランキング付けします。主固有ベクトルを計算する従来の方法は、パワー反復法を使用することです。ここでは、scikit-learn で実装された Martinsson のランダム化 SVD アルゴリズムを使用します。
VM のヒント
VM の起動が完了したら、左上隅をクリックしてノートブックタブに切り替えて、Jupyter Notebook を使って練習しましょう。
時々、Jupyter Notebook が読み込み終了するまで数秒待つ必要がある場合があります。Jupyter Notebook の制限により、操作の検証を自動化することはできません。
学習中に問題に直面した場合は、Labby にお問い合わせください。セッション後にフィードバックを提供してください。すぐに問題を解決いたします。
データがディスクにない場合はダウンロードする
Wikipedia コンテンツの潜在的な構造化データの抽出である DBpedia ダンプからデータをダウンロードします。
from bz2 import BZ2File
import os
from datetime import datetime
from urllib.request import urlopen
redirects_url = "http://downloads.dbpedia.org/3.5.1/en/redirects_en.nt.bz2"
redirects_filename = redirects_url.rsplit("/", 1)[1]
page_links_url = "http://downloads.dbpedia.org/3.5.1/en/page_links_en.nt.bz2"
page_links_filename = page_links_url.rsplit("/", 1)[1]
resources = [
(redirects_url, redirects_filename),
(page_links_url, page_links_filename),
]
for url, filename in resources:
if not os.path.exists(filename):
print("Downloading data from '%s', please wait..." % url)
opener = urlopen(url)
with open(filename, "wb") as f:
f.write(opener.read())
print()
リダイレクトファイルを読み込む
リダイレクションを解析し、それから推移的に閉じたマップを作成します。
DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/")
SHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)
def short_name(nt_uri):
"""< と > URI マーカーと共通の URI 接頭辞を削除する"""
return nt_uri[SHORTNAME_SLICE]
def index(redirects, index_map, k):
"""リダイレクト解決後の記事名のインデックスを見つける"""
k = redirects.get(k, k)
return index_map.setdefault(k, len(index_map))
def get_redirects(redirects_filename):
"""リダイレクトを解析し、それから推移的に閉じたマップを作成する"""
redirects = {}
print("NT リダイレクトファイルを解析中")
for l, line in enumerate(BZ2File(redirects_filename)):
split = line.split()
if len(split)!= 4:
print("整形されていない行を無視：" + line)
continue
redirects[short_name(split[0])] = short_name(split[2])
if l % 1000000 == 0:
print("[%s] 行：%08d" % (datetime.now().isoformat(), l))
## 推移的閉包を計算する
print("リダイレクト関係の推移的閉包を計算中")
for l, source in enumerate(redirects.keys()):
transitive_target = None
target = redirects[source]
seen = {source}
while True:
transitive_target = target
target = redirects.get(target)
if target is None or target in seen:
break
seen.add(target)
redirects[source] = transitive_target
if l % 1000000 == 0:
print("[%s] 行：%08d" % (datetime.now().isoformat(), l))
return redirects
## リダイレクトファイルを読み込む
redirects = get_redirects(redirects_filename)
隣接行列の計算
scipy の疎行列として隣接グラフを抽出します。まずリダイレクトを解決します。scipy の疎隣接行列 X と、記事名から記事名への Python 辞書としてのリダイレクト、および記事名から Python の int（記事インデックス）への Python 辞書である index_map を返します。
import numpy as np
from scipy import sparse
def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
"""scipy の疎行列として隣接グラフを抽出する"""
index_map = dict()
links = list()
for l, line in enumerate(BZ2File(page_links_filename)):
split = line.split()
if len(split)!= 4:
print("整形されていない行を無視：" + line)
continue
i = index(redirects, index_map, short_name(split[0]))
j = index(redirects, index_map, short_name(split[2]))
links.append((i, j))
if l % 1000000 == 0:
print("[%s] 行：%08d" % (datetime.now().isoformat(), l))
if limit is not None and l >= limit - 1:
break
print("隣接行列を計算中")
X = sparse.lil_matrix((len(index_map), len(index_map)), dtype=np.float32)
for i, j in links:
X[i, j] = 1.0
del links
print("CSR 表現に変換中")
X = X.tocsr()
print("CSR 変換完了")
return X, redirects, index_map
## 500 万のリンクで停止して RAM 内で作業できるようにする
X, redirects, index_map = get_adjacency_matrix(
redirects_filename, page_links_filename, limit=5000000
)
names = {i: name for name, i in index_map.items()}
ランダム化 SVD を使った主特異値ベクトルの計算
scikit-learn で実装された randomized_svd メソッドを使って主特異値ベクトルを計算します。
from sklearn.decomposition import randomized_svd
print("randomized_svd を使って主特異値ベクトルを計算中")
U, s, V = randomized_svd(X, 5, n_iter=3)
中心性スコアの計算
パワー反復法を使って主固有ベクトルスコアを計算します。
def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
"""主固有ベクトルのパワー反復計算"""
n = X.shape[0]
X = X.copy()
incoming_counts = np.asarray(X.sum(axis=1)).ravel()
print("グラフを正規化中")
for i in incoming_counts.nonzero()[0]:
X.data[X.indptr[i] : X.indptr[i + 1]] *= 1.0 / incoming_counts[i]
dangle = np.asarray(np.where(np.isclose(X.sum(axis=1), 0), 1.0 / n, 0)).ravel()
scores = np.full(n, 1.0 / n, dtype=np.float32) ## 初期推定
for i in range(max_iter):
print("パワー反復 #%d" % i)
prev_scores = scores
scores = (
alpha * (scores * X + np.dot(dangle, prev_scores))
+ (1 - alpha) * prev_scores.sum() / n
)
## 収束を確認する：正規化された l_inf ノルム
scores_max = np.abs(scores).max()
if scores_max == 0.0:
scores_max = 1.0
err = np.abs(scores - prev_scores).max() / scores_max
print("エラー: %0.6f" % err)
if err < n * tol:
return scores
return scores
print("パワー反復法を使って主固有ベクトルスコアを計算中")
scores = centrality_scores(X, max_iter=100)
まとめ
この実験では、scikit-learn に実装された Martinsson のランダム化 SVD アルゴリズムを使って、Wikipedia 記事内のリンクのグラフを分析し、固有ベクトル中心性に基づいて記事を相対的な重要度でランキング付けしました。また、パワー反復法を使って主固有ベクトルスコアを計算しました。