第3期 邓思宇，等：基于PageRank的主动学习算法 ·555· 7)clusterT(root.lc.Ic,count,threshold); 8)end if 2 ⑤ 0.714 0.153 0.455 0.196 9)end if ⑨ © 7 10)if (root.Ic.rc!null)then 0.667 0.333 0.556 0.3850.62 0.323 11)步骤4)、5)、6)、7)： 个) 3 ④ ⑩⑩ ② 0.588/ 0.588 0.5/ 0.478 12)end if ④ ⑧ (6 13)end clusterT(root.lc,count,threshold) (a)二叉树 14)for(i=0 to count)do bl,9 15)tempNum=0; bL,11 13 1415 16)for(j=0 to N)do bl, 6 781012 17)if(cn,=ithen bl,0 1 234 5 18)bl(i,tempNum)=j;tempNum ++ (b)聚类信息块 19)end if; 图2第一次迭代 20)end for Fig.2 First iteration of the running example 21)end for bly 9 22)return bl; bl212 算法3详细描述了基于二叉树的聚类过程。 11131415 通过遍历树的节点，同时用数组cn记录节点的簇 6 7 810 号，实现聚类。lc表示左孩子，同理rc表示右孩 bls 0 2345 子。count用于记录递归过程中最大簇数。1)定 图3第二次迭代 义聚类函数；2)记录节点的簇号：3)9)根据相似 Fig.3 Second iteration of the running example 度关系判断簇边界，如当前节点与它的孩子节点 1)根据算法1得到排名向量 的相似度小于阈值threshold,count自增后进行下 Rank=[1237141368101115041259] 一次递归；14)21)整理cn得到分块信息表bl。 根据算法2生成二叉树，如图2(a)所示。由 该方法可以解决聚类算法需要人工设定K值的 于数据集极小，设定R=100。令标记集合U,=O, 问题。 预测集合U,=0,未分类集合U=U。 2.2.4主动学习 2)选择节点间的较低相似度0.196作为当 主动学习阶段，利用二叉树聚类算法生成的 前阈值threshold,根据算法3聚类可得块信息 信息块bl对代表样本进行标记和预测。 bl=blbl2…bL]:如图2(b)所示。接着，查询bl1 1)如bl,中存在未分类样本，则查询bl,中 bl2、bl和bl中样本xg、x1、x6和xo的标签，分别 PageRank值较高的一部分样本的标签。 是iv、it、iv和is。在此次迭代后，U'={xo,x6,g,x山， 2)如bl,中已分类的样本数量足够大(P:≥v6) U1=0UU1'={xo6,},U3=U3-U1={x,2,x3 且标签一致，则可预测该块中剩余样本的标签。 X4,5,x,g,x10,2,x1B,x14,x15};在第一次迭代后， 3)增大阈值threshold,进行下一轮聚类、标记 |U≤7。增大阈值thresholdi进行第2次聚类。 和预测。达到标签查询上限后，对不纯的块，采 3)设置阈值threshold=0.323,聚类簇信息块 取投票的方式确定剩余未标记代表样本的标签。 如图3所示。查询bl1、bl2、bl和bl,中样本x12、 x13和x,的标签，分别是it、it和iv。此时，U'= 主动学习阶段结束时，代表样本均已获得标 签。将代表样本作为训练集，采用kNN算法对其 {12,x13,xl,U1=U1UU'={x0,x6,x,xg,x,x12,x3。bl 中已被标记的样本数量已经足够多，且已标记样 他样本进行分类。 本标签均为it,便可预测bl2中剩余样本x14和 2.3样例分析 x1s的标签为it。同理可预测块bl中剩余样本xg、 提供一个样例分析来进一步清楚说明PAL x1o的标签均为iV。U2=U2UU2'={xg,x1o,x14,xs}, 算法。使用表1的决策信息系统，允许查询的最 U3=U3-U1-U2={x1,2,3,x4,x}。在第2次迭代 大标签数N=7。设置阻尼=0.95，c=0.01。图2和 后，U川≥7。不再进行第3次聚类。 图3展示两次迭代聚类之后查询标签的情况。 4)U={x1,x2,,x4,}通过投票给予标签；7) clusterT (root.lc.lc, count, threshold); 8) end if 9) end if 10) if (root.lc.rc! = null) then 11) 步骤 4)、5)、6)、7)； 12) end if 13) end clusterT (root.lc，count，threshold) 14) for(i = 0 to count) do 15) tempNum= 0; 16) for( j = 0 to N) do 17) if(cnj = i)then 18) bl(i, tempNum) = j; tempNum ++; 19) end if； 20) end for 21) end for 22) return bl; 算法 3 详细描述了基于二叉树的聚类过程。 通过遍历树的节点，同时用数组 cn 记录节点的簇 号，实现聚类。lc 表示左孩子，同理 rc 表示右孩 子。count 用于记录递归过程中最大簇数。1) 定 义聚类函数；2) 记录节点的簇号；3)~9) 根据相似 度关系判断簇边界，如当前节点与它的孩子节点 的相似度小于阈值 threshold，count 自增后进行下 一次递归；14)~21) 整理 cn 得到分块信息表 bl。 该方法可以解决聚类算法需要人工设定 K 值的 问题。 2.2.4 主动学习 主动学习阶段，利用二叉树聚类算法生成的 信息块 bl 对代表样本进行标记和预测。 1) 如 bli 中存在未分类样本，则查询 bli 中 PageRank 值较高的一部分样本的标签。 Pi ⩾ √ bl 2) 如 bli 中已分类的样本数量足够大 ( i) 且标签一致，则可预测该块中剩余样本的标签。 3) 增大阈值 threshold，进行下一轮聚类、标记 和预测。达到标签查询上限后，对不纯的块，采 取投票的方式确定剩余未标记代表样本的标签。 主动学习阶段结束时，代表样本均已获得标 签。将代表样本作为训练集，采用 kNN 算法对其 他样本进行分类。 2.3 样例分析 提供一个样例分析来进一步清楚说明 PAL 算法。使用表 1 的决策信息系统，允许查询的最 大标签数 N =7。设置阻尼 γ=0.95，ε=0.01。图 2 和 图 3 展示两次迭代聚类之后查询标签的情况。 (a) 二叉树 (b) 聚类信息块 bl1 9 11 6 0 13 7 1 14 8 2 15 10 3 4 12 5 bl2 bl3 bl4 0.588 0.667 0.714 0.333 0.153 0.455 0.556 0.385 0.625 0.196 0.323 0.588 0.5 0.478 0 1 4 5 3 2 9 14 13 15 −1 11 10 7 12 8 6 图 2 第一次迭代 Fig. 2 First iteration of the running example bl1 9 11 6 0 13 7 1 14 8 2 15 10 3 4 12 5 bl2 bl3 bl4 bl5 图 3 第二次迭代 Fig. 3 Second iteration of the running example 1) 根据算法 1 得到排名向量 Rank=[1 2 3 7 14 13 6 8 10 11 15 0 4 12 5 9] Ø Ø 根据算法 2 生成二叉树，如图 2(a) 所示。由 于数据集极小，设定 R=100。令标记集合 U1= ， 预测集合 U2= ，未分类集合 U3=U。 bl = [bl1 bl2 ···bl4] U1 ′ ={x0, x6, x9, x11} U1 = Ø∪U1 ′ = {x0, x6, x9, x11} U3 = U3 −U1 = {x1, x2, x3, x4, x5, x7, x8, x10, x12, x13, x14, x15} 2) 选择节点间的较低相似度 0.196 作为当 前阈值 threshold，根据算法 3 聚类可得块信息 ；如图 2(b) 所示。接着，查询 bl1、 bl2、bl3 和 bl4 中样本 x9、x11、x6 和 x0 的标签，分别 是 iv、it、iv 和 is。在此次迭代后， ， ， ；在第一次迭代后， |U1 |≤7。增大阈值 threshold进行第 2 次聚类。 U1 ′ = {x12, x13, x7} U1 =U1 ∪U1 ′ = {x0, x6, x7, x9, x11, x12, x13} U2 =U2 ∪U2 ′ = {x8, x10, x14, x15} U3 = U3 −U1 −U2 = {x1, x2, x3, x4, x5} 3) 设置阈值 threshold = 0.323，聚类簇信息块 如图 3 所示。查询 bl1、bl2、bl3 和 bl4 中样本 x12、 x13 和 x7 的标签，分别是 it、it 和 iv 。此时， ， 。bl2 中已被标记的样本数量已经足够多，且已标记样 本标签均为 it，便可预测 bl 2 中剩余样本 x 1 4 和 x15 的标签为 it。同理可预测块 bl3 中剩余样本 x8、 x 1 0 的标签均 为 iv。 ， 。 在 第 2 次迭代 后，|U1 |≥7。不再进行第 3 次聚类。 4 ) U3 = {x1, x2, x3, x4, x5} 通过投票给予标签； 第 3 期 邓思宇，等：基于 PageRank 的主动学习算法 ·555·