在图论中，一个经典的方法是通过计算邻接矩阵的主要特征向量来确定图中顶点的相对重要性，每个顶点的中心性得分由该特征向量的分量值给出。在网页和链接的图中，这些值被称为Google的PageRank得分。本例的目标是分析维基百科文章内部的链接图，根据这种特征向量中心性对文章进行排序。
传统的计算主要特征向量的方法是使用幂迭代法。在这里，计算是通过scikit-learn中实现的Martinsson的随机SVD算法完成的。图数据是从DBpedia转储中获取的，DBpedia是维基百科内容的潜在结构化数据的提取。
以下是使用Python和scikit-learn库进行这种分析的详细步骤。首先，需要下载并解析数据，然后构建图的邻接矩阵，最后使用随机SVD算法计算主要奇异向量，这些向量可以用来确定维基百科页面的中心性得分。
如果磁盘上还没有数据，需要从DBpedia下载重定向和页面链接的数据文件。这些文件是使用bzip2压缩的，因此需要使用相应的库来解压缩和解析它们。
# 导入必要的库
import os
from bz2 import BZ2File
from datetime import datetime
from pprint import pprint
from time import time
from urllib.request import urlopen
import numpy as np
from scipy import sparse
from sklearn.decomposition import randomized_svd
重定向文件包含了页面之间的重定向关系。需要解析这些文件并构建一个映射，以便将重定向的页面名称解析为其最终目标。这个过程涉及到迭代地跟随重定向，直到找到最终的目标页面。
# 定义一些辅助函数来处理重定向和页面名称
def index(redirects, index_map, k):
""“在解析重定向后找到文章名称的索引”""
k = redirects.get(k, k)
return index_map.setdefault(k, len(index_map))
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 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("[{}] 行: {:08d}".format(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("[{}] 行: {:08d}".format(datetime.now().isoformat(), l))
return redirects
邻接矩阵表示了图的结构，其中每个元素表示两个页面之间是否存在链接。首先需要解析页面链接文件，然后构建这个矩阵。这个过程涉及到将页面名称映射到整数索引，并记录页面之间的链接关系。
def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
""“提取邻接图作为scipy稀疏矩阵，首先解析重定向关系。
返回X，scipy稀疏邻接矩阵，重定向作为python字典从文章名称到文章名称
和index_map一个python字典从文章名称到python int（文章索引）。""
print("计算重定向映射")
redirects = get_redirects(redirects_filename)
print("计算整数索引映射")
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("[{}] 行: {:08d}".format(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()}
主要奇异向量可以用来确定维基百科页面的中心性得分。使用scikit-learn中的randomized_svd函数来计算这些向量。这个过程涉及到对邻接矩阵进行奇异值分解，并提取出最重要的奇异向量。
print("使用randomized_svd计算主要奇异向量")
t0 = time()
U, s, V = randomized_svd(X, 5, n_iter=3)
print("完成时间：{}秒".format(time() - t0))
# 打印与主要奇异向量相关的最强wikipedia页面的名称
# 这些页面应该与最高的特征向量相似
print("根据主要奇异向量排名的顶级wikipedia页面")
pprint([names[i] for i in np.abs(U.T[0]).argsort()[-10:]])
pprint([names[i] for i in np.abs(V[0]).argsort()[-10:]])
中心性得分，也称为PageRank，是使用幂迭代法计算的。这种方法也被称为Google PageRank，其实现基于NetworkX项目（也是BSD许可的）的实现，由Aric Hagberg、Dan Schult和Pieter Swart版权所有。
def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
""“使用幂迭代法计算主要特征向量
这种方法也被称为Google PageRank，实现基于NetworkX项目（BSD许可）
版权所有者：
Aric Hagberg <hagberg@lanl.gov>
Dan Schult <dschult@colgate.edu>
Pieter Swart <swart@lanl.gov>
""
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("幂迭代 #{}".format(i))
prev_scores = scores
scores = (alpha * (scores * X + np.dot(dangle, prev_scores)) + (1 - alpha) * 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}".format(err))
if err < n * tol:
return scores
return scores
print("使用幂迭代法计算主要特征向量得分")
t0 = time()
scores = centrality_scores(X, max_iter=100)
print("完成时间：{}秒".format(time() - t0))
pprint([names[i] for i in np.abs(scores).argsort()[-10:]])
以下是一些相关的示例，它们展示了不同的数据分析和机器学习技术在不同领域的应用。