소개
이 실습에서는 위키피디아 문서 내 링크 그래프를 분석하여 고유벡터 중심성에 따라 문서의 상대적 중요도를 평가합니다. 주요 고유벡터를 계산하는 전통적인 방법은 멱법입니다. 여기서는 scikit-learn 에 구현된 Martinsson 의 무작위 SVD 알고리즘을 사용할 것입니다.
VM 팁
VM 시작이 완료되면 왼쪽 상단 모서리를 클릭하여 Notebook 탭으로 전환하여 연습을 위한 Jupyter Notebook에 접속합니다.
때때로 Jupyter Notebook 이 완전히 로드되기까지 몇 초 정도 기다려야 할 수 있습니다. Jupyter Notebook 의 제한으로 인해 작업 검증은 자동화될 수 없습니다.
학습 중 문제가 발생하면 Labby 에게 문의하십시오. 세션 후 피드백을 제공하면 문제를 신속하게 해결해 드리겠습니다.
데이터 다운로드 (이미 디스크에 있는 경우 제외)
위키피디아 콘텐츠의 잠재 구조화된 데이터 추출인 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("'%s'에서 데이터를 다운로드 중입니다. 잠시 기다려주십시오..." % 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 희소 행렬로 추출합니다. 먼저 리디렉션을 해결합니다. X(scipy 희소 인접 행렬), 문서 이름에서 문서 이름으로의 파이썬 딕셔너리인 리디렉션, 그리고 문서 이름에서 파이썬 정수 (문서 인덱스) 로의 파이썬 딕셔너리인 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
## RAM 에서 작업할 수 있도록 5 백만 개의 링크 이후에 중지
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("무작위 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 알고리즘을 사용하여 위키피디아 문서 내 링크 그래프를 분석하고, 고유 벡터 중심성에 따라 문서의 상대적 중요도를 기준으로 문서를 랭킹했습니다. 또한, 멱승 반복법을 사용하여 주요 고유 벡터 점수를 계산했습니다.