第3期 邓思宇，等：基于PageRank的主动学习算法 ·553· Rank分值可作为网页重要程度的度量指标。图1 量的样本来构建高精度分类器。可供查询的标签 表示一个Web超链接图。 数量N是输人参数之一。 输入决策信息系统S=(U,C,d; 输出分类精度accuracy; 约束条件U=U,UU。 优化目标最大化精度accuracy,即 图1超链接网络 accuracy= U-error ×100% (10) Fig.1 Hyperlink network 10.A- 定义5 PageRank分值。将互联网中的网页 式中：IU,是训练集大小；IU是测试集大小；error 抽象成一个有向图G=(WE)。E是网页超链接集 是误分类样本数量。若可供查询的标签数量为 合，V是网页集合。设n=IM,网页i的PageR- N,则IU=n-N。 ank分值point()定义为 2.2PAL算法描述 point()= point() (5) PAL算法可以细分为3个子算法，分别是 .0 PageRank排名计算算法、二叉树生成算法和二叉 式中O,表示网页j的出度。此时，PageRank分值 树聚类算法。伪代码符号定义如表2。 的n维行向量可用P表示，即 P=[point(1)point(2)...point(n)] (6) 表2符号定义 Table 2 Symbol definitions 有向图G的邻接矩阵可以用A=(a)am表 示，其中： 符号 定义说明 w-{&0其eE (7) U 所有样本集合 U 排名前R的样本集合 根据式(6)、式(7)可定义n维方程组为 T 状态转移矩阵 P=ATP- (8) 式(8)是循环定义式。迭代求得分值向量P, P 分值向量 即P不再显著变化或者趋近收敛时，停止迭代。 Rank 排名向量 初始情况下，所有网页的排名是相同的，即P。= x 左孩子样本 [11…1]。极小值￡是人工设定的收敛阈值，用于 Xr 右孩子样本 验证向量P是否收敛。每轮迭代结束后，若 集合U二U”为x的样本集合 P-P-<s,则认为达到收敛条件。 在有向图G中，存在没有出度的网页”，称之 U, 集合UcU为x,的样本集合 为悬挂网页，如图1中的V。悬挂网页导致排名 setChild ( 设置子节点（函数） 下沉，PageRank分值向量P在经过i次迭代后，其 clusterT() 聚类（函数） 值均为0。将Wb图用马尔可夫链进行建模可 cn 记录簇号的数组 以解决上述问题。 bl, 第i簇信息块 将网页看作马尔可夫链的状态，超链接表示 状态转移。这样，Wb冲浪将表示成一种随机过程。 2.2.1 PageRank排名计算算法 状态转移矩阵T必须满足3个条件：随机矩阵、不 利用PageRank计算每个样本的分值，该分值 可约、非周期。因此，将邻接矩阵A进行如下修订： 可作为样本信息量的度量标准，即分值越大样本 T=yA+0-月 (9) 所含信息量越高。 式中：y是阻尼系数，一般情况下y∈(0,1)；E是 给定决策信息类系统S=(U,C,d),对于任意 个n×n阶且元素全为1的矩阵；E/n表示一网页 的xx∈U,且x∈n(x,)。根据式(4)、式(5)计算 链接其他网页的随机概率，即1/n。 样本x在PageRank模型下所获得的分数point(x): 2问题与算法 point(x)= ∑point() 。(r,j (11) 2.1问题描述 根据式(T)决策系统邻接矩阵可用A'=(a)m 在主动学习应用场景中，算法标注最具信息 表示，其中：Rank 分值可作为网页重要程度的度量指标。图 1 表示一个 Web 超链接图。 1 2 3 4 5 6 图 1 超链接网络 Fig. 1 Hyperlink network G = (V,E) n = |V| 定义 5 PageRank 分值。将互联网中的网页 抽象成一个有向图 。E 是网页超链接集 合 ，V 是网页集合。设 ，网页 i 的 PageR￾ank 分值 point(i) 定义为 point(i) = ∑ (j,i)∈E point(j) Oj (5) 式中 Oj 表示网页 j 的出度。此时，PageRank 分值 的 n 维行向量可用 P 表示，即 P = [ point(1) point(2) ··· point(n) ]T (6) 有向图 G 的邻接矩阵可以用 A = (ai j)n×n 表 示，其中： ai j = { 1/Oi , (i, j) ∈ E 0, 其他 (7) 根据式 (6)、式 (7) 可定义 n 维方程组为 Pi = A T Pi−1 (8) P0 = [1 1··· 1] |Pi − Pi−1| < ε 式 (8) 是循环定义式。迭代求得分值向量 P， 即 P 不再显著变化或者趋近收敛时，停止迭代。 初始情况下，所有网页的排名是相同的，即 。极小值 ε 是人工设定的收敛阈值，用于 验证向 量 P 是否收敛。每轮迭代结束后，若 ，则认为达到收敛条件。 在有向图 G 中，存在没有出度的网页 v，称之 为悬挂网页，如图 1 中的 V5。悬挂网页导致排名 下沉，PageRank 分值向量 P 在经过 i 次迭代后，其 值均为 0。将 Web 图用马尔可夫链[17]进行建模可 以解决上述问题。 将网页看作马尔可夫链的状态，超链接表示 状态转移。这样，Web 冲浪将表示成一种随机过程。 状态转移矩阵 T 必须满足 3 个条件：随机矩阵、不 可约、非周期。因此，将邻接矩阵 A 进行如下修订： T = γA T +(1−γ) E n (9) 式中：γ 是阻尼系数，一般情况下 γ∈(0, 1)；E 是一 个 n×n 阶且元素全为 1 的矩阵；E /n 表示一网页 链接其他网页的随机概率，即 1/n。 2 问题与算法 2.1 问题描述 在主动学习应用场景中，算法标注最具信息 量的样本来构建高精度分类器。可供查询的标签 数量 N 是输入参数之一。 输入 决策信息系统 S = (U,C,d) ； 输出 分类精度 accuracy； 约束条件 U = Ur ∪Ut。 优化目标 最大化精度 accuracy，即 accuracy = |Ut | −error |Ut | ×100% (10) |Ut | = n−N 式中：|Ur |是训练集大小；|Ut |是测试集大小；error 是误分类样本数量。若可供查询的标签数量为 N，则 。 2.2 PAL 算法描述 PAL 算法可以细分为 3 个子算法，分别是 PageRank 排名计算算法、二叉树生成算法和二叉 树聚类算法。伪代码符号定义如表 2。 表 2 符号定义 Table 2 Symbol definitions 符号 定义说明 U 所有样本集合 U' 排名前 R 的样本集合 T 状态转移矩阵 P 分值向量 Rank 排名向量 xl 左孩子样本 xr 右孩子样本 Ul Ul ⊆ U 集合 ′ 为 xl 的样本集合 Ur Ur ⊆ U 集合 ′ 为 xr 的样本集合 setChild () 设置子节点 (函数) clusterT () 聚类 (函数) cn 记录簇号的数组 bli 第 i 簇信息块 2.2.1 PageRank 排名计算算法 利用 PageRank 计算每个样本的分值，该分值 可作为样本信息量的度量标准，即分值越大样本 所含信息量越高。 S = (U,C,d) x, x ′ ∈ U x ∈ n(x ′ , θ) 给定决策信息类系统 ，对于任意 的 ，且 。根据式 (4)、式 (5) 计算 样本 x 在 PageRank 模型下所获得的分数 point(x)： point(x) = ∑ x∈(x ′ ,θ) point(x ′ ) |n(x ′ , θ)| (11) A ′ = (ai j ′ 根据式 (7) 决策系统邻接矩阵可用 )n×n 表示，其中: 第 3 期 邓思宇，等：基于 PageRank 的主动学习算法 ·553·