第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201804052 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180627.1529.002.html 基于PageRank的主动学习算法 邓思宇，刘福伦，黄雨婷，汪敏2 (1.西南石油大学计算机科学学院，四川成都610500,2.西南石油大学电气信息学院，四川成都610500) 摘要：在许多分类任务中，存在大量未标记的样本，并且获取样本标签耗时且昂贵。利用主动学习算法确定 最应被标记的关键样本，来构建高精度分类器，可以最大限度地诚少标记成本。本文提出一种基于PageRank 的主动学习算法(PAL),充分利用数据分布信息进行有效的样本选择。利用PageRank根据样本间的相似度关 系依次计算邻域、分值矩阵和排名向量：选择代表样本，并根据其相似度关系构建二叉树，利用该二叉树对代 表样本进行聚类，标记和预测；将代表样本作为训练集，对其他样本进行分类。实验采用8个公开数据集，与 5种传统的分类算法和3种流行的主动学习算法比较，结果表明PAL算法能取得更好的分类效果。 关键词：分类；主动学习；PageRank;邻域；聚类；二叉树 中图分类号：TP181 文献标志码：A文章编号：1673-4785(2019)03-0551-09 中文引用格式：邓思宇，刘福伦，黄雨婷，等.基于PageRank的主动学习算法J.智能系统学报，2019,14(3)：551-559 英文引用格式：DENG Siyu,LIU Fulun,HUANG Yuting,etal.Active learning through PageRankJ]..CAAI transactions on intelli- gent systems,.2019,14(3:551-559. Active learning through PageRank DENG Siyu',LIU Fulun',HUANG Yuting',WANG Min2 (1.School of Computer Science,Southwest Petroleum University,Chengdu 610500,China;2.School of Electrical Engineering and Information,Southwest Petroleum University,Chengdu 610500,China) Abstract:In many classification tasks,there are a large number of unlabeled samples,and it is expensive and time-con- suming to obtain a label for each class.The goal of active learning is to train an accurate classifier with minimum cost by labeling the most informative samples.In this paper,we propose a PageRank-based active learning algorithm(PAL), which makes full use of sample distribution information for effective sample selection.First,based on the PageRank the- ory,we sequentially calculate the neighborhoods,score matrices,and ranking vectors based on similarity relationships in the data.Next,we select representative samples and establish a binary tree to express the relationships between repres- entative samples.Then,we use a binary tree to cluster,label,and predict representative samples.Lastly,we regard the representative samples as training sets for classifying other samples.We conducted experiments on eight datasets to compare the performance of our proposed algorithm with those of five traditional classification algorithms and three state-of-the-art active learning algorithms.The results demonstrate that PAL obtained higher classification accuracy Keywords:classification;active learning;PageRank;neighborhood;clustering;binary tree 传统的监督学习算法，如Naive Bayes!、One-实的数据分析场景下，大量的无标注样本较易获 R和J48等，其分类效果依赖于训练数据的有效取，而已标注样本数量稀少且难以获取。对海量 性。通常情况下，使用已标记的样本作为训练 数据进行标注是耗时、昂贵且困难的。在此情况 集，学习算法以此训练出分类模型。然而，在真 下，半监督学习(semi-supervised learning)和主动 学习(active learning)被提出并得到快速发展，已 收稿日期：2018-04-26.网络出版日期：2018-06-28. 基金项目：国家自然科学基金项目(61379089). 经被广泛地应用在文本分类向、语音识别和图像 通信作者：汪敏.E-mail:wangmin80616@163.com. 分类等领域
DOI: 10.11992/tis.201804052 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180627.1529.002.html 基于 PageRank 的主动学习算法 邓思宇1 ，刘福伦1 ，黄雨婷1 ，汪敏2 （1. 西南石油大学 计算机科学学院，四川 成都 610500; 2. 西南石油大学 电气信息学院，四川 成都 610500） 摘 要：在许多分类任务中，存在大量未标记的样本，并且获取样本标签耗时且昂贵。利用主动学习算法确定 最应被标记的关键样本，来构建高精度分类器，可以最大限度地减少标记成本。本文提出一种基于 PageRank 的主动学习算法 (PAL)，充分利用数据分布信息进行有效的样本选择。利用 PageRank 根据样本间的相似度关 系依次计算邻域、分值矩阵和排名向量；选择代表样本，并根据其相似度关系构建二叉树，利用该二叉树对代 表样本进行聚类，标记和预测；将代表样本作为训练集，对其他样本进行分类。实验采用 8 个公开数据集，与 5 种传统的分类算法和 3 种流行的主动学习算法比较，结果表明 PAL 算法能取得更好的分类效果。 关键词：分类；主动学习；PageRank；邻域；聚类；二叉树 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2019)03−0551−09 中文引用格式：邓思宇, 刘福伦, 黄雨婷, 等. 基于 PageRank 的主动学习算法[J]. 智能系统学报, 2019, 14(3): 551–559. 英文引用格式：DENG Siyu, LIU Fulun, HUANG Yuting, et al. Active learning through PageRank[J]. CAAI transactions on intelligent systems, 2019, 14(3): 551–559. Active learning through PageRank DENG Siyu1 ，LIU Fulun1 ，HUANG Yuting1 ，WANG Min2 (1. School of Computer Science, Southwest Petroleum University, Chengdu 610500, China; 2. School of Electrical Engineering and Information, Southwest Petroleum University, Chengdu 610500, China) Abstract: In many classification tasks, there are a large number of unlabeled samples, and it is expensive and time-consuming to obtain a label for each class. The goal of active learning is to train an accurate classifier with minimum cost by labeling the most informative samples. In this paper, we propose a PageRank-based active learning algorithm (PAL), which makes full use of sample distribution information for effective sample selection. First, based on the PageRank theory, we sequentially calculate the neighborhoods, score matrices, and ranking vectors based on similarity relationships in the data. Next, we select representative samples and establish a binary tree to express the relationships between representative samples. Then, we use a binary tree to cluster, label, and predict representative samples. Lastly, we regard the representative samples as training sets for classifying other samples. We conducted experiments on eight datasets to compare the performance of our proposed algorithm with those of five traditional classification algorithms and three state-of-the-art active learning algorithms. The results demonstrate that PAL obtained higher classification accuracy. Keywords: classification; active learning; PageRank; neighborhood; clustering; binary tree 传统的监督学习算法，如 Naïve Bayes[1] 、OneR [2]和 J48[3]等，其分类效果依赖于训练数据的有效 性。通常情况下，使用已标记的样本作为训练 集，学习算法以此训练出分类模型。然而，在真 实的数据分析场景下，大量的无标注样本较易获 取，而已标注样本数量稀少且难以获取。对海量 数据进行标注是耗时、昂贵且困难的。在此情况 下，半监督学习 (semi-supervised learning)[4]和主动 学习 (active learning)[5]被提出并得到快速发展，已 经被广泛地应用在文本分类[6] 、语音识别[7]和图像 分类[8]等领域。 收稿日期：2018−04−26. 网络出版日期：2018−06−28. 基金项目：国家自然科学基金项目 (61379089). 通信作者：汪敏. E-mail：wangmin80616@163.com. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019
·552· 智能系统学报 第14卷 主动学习模拟一种人机交互场景，允许学习 属性。表1是1个决策信息系统，U={x0,x1,x,…,xs 算法根据查询策略，主动获取选取样本的真实类 C=a,az,a3,aslo 标签，对主动标注的样本进行训练，不断修正已 表1决策信息系统 有分类模型，从而提高分类器的泛化能力和分类 Table 1 Example of decision system 精度。因此，主动学习的主要挑战是制定有效的 U 42 d 样本选择策略。目前，比较常见的主动学习方法 Xo 5.1 3.5 1.4 0.2 is 有不确定抽样(sampling uncertainty,UC)9,基于聚 X1 4.9 3.0 1.4 0.2 is 类(clustering-.based approaches,CBA)Io和基于委员 4.7 3.2 1.3 0.2 is 会投票采样法(query-by-committee,QBC)l。其 4.6 3.1 1.5 0.2 is 中，不确定性抽样方法选择当前分类器中不确定 X4 5.0 3.6 1.4 0.2 is 度最高的未标注样本进行标注，并将其添加到训 5.4 3.9 4 is 练集中。由于单一分类器存在分类偏好，使得泛 X6 7.0 iv 化能力产生定式，而QBC通过多种同质或异质分 7 6.4 1.5 iv 类器共同参与分类，一般选取冲突性（不一致 6.9 4. 1.5 iv 性)最高的未标注样本进行标注。基于聚类的样 Xg 5.5 4.0 1.3 iv 本选择方法旨在通过分析样本间的内在相似性， x10 6.5 2.8 4.6 1.5 对样本进行划簇，而后从每簇中选择代表样本进 6.3 3.3 6.0 2.5 it 行标注。 X12 5.8 2.7 5.1 1.9 PageRank"建立在随机冲浪模型上，通过计 x13 7.1 3.0 5.9 2.1 it 算网页的PageRank分值，解决了互联网搜索引擎 X14 6.5 3.0 5.8 2.2 it 的网页排名问题。PageRank理论基于两个简单 x15 7.6 3.0 6.6 2.1 it 的假设：1)较重要的网页被更多的网页链接； 定义2 2)PageRank分值越高的网页将传递更高的权重。 曼哈顿距离。向量x=[a1a2…am]与 y=[b1b2…bm]的曼哈顿距离为 本文结合PageRank理论，将PageRank分值作为 样本信息量的度量指标，同时充分考虑样本的分 dis(x,y）= (2) 布信息，提出一种基于PageRank的主动学习算法 式(2)表示在多维空间中两个点之间的距 (PageRank-based active learning algorithm,PAL). 主动学习算法中样本的选择问题提供一种可行的 离。信息表的样本可以用向量表示。相应地，可 以定义任意一组样本的相似度。 方案。 实验在8个公开数据集上进行，通过设置不 定义3相似度。给定一个决策信息系统S= 同规模的训练集，测试PAL算法的分类性能。实 (U,C,d,任意x,y∈U的相似度记为 验结果表明，PAL算法较Naive Bayes、.J48、kNN 1 (3) 和One-R等经典分类算法，通常能得到更高的分 sim(x,y）=1+dis(x,y) 根据式(2)、式(3)，可计算表1的决策信息系 类精度，且与QBC、KQBC和MADETS1等主动学 习算法相比，有更好的分类性能。 统中sim(xox6)=0.13,sim(x3,x2)=0.127。 定义4邻域。对于任意的样本x∈U,可以 1数据模型 通过设置相似度阈值0的方式确定其邻域，样本 的邻域定义为 在本节中，主要介绍决策信息系统、PageRank n(x,)=y∈sim(x,y)≥ (4) 理论等基本概念。 相似度阈值0越小，样本的邻域越大。根据 1.1决策信息系统 定义1决策信息系统6。决策信息系统定 表1所示的决策信息系统可以计算出(xo,0.5)= 义成一个三元组： {x1,,3x4}0 S=(U,C,d) (1) 1.2 PageRank模型 式中：U代表一个非空样本集合，也称论域；C代 Web中的网页通过超链接相互链接，Page- 表一个非空条件属性集合；d指的是样本的决策 Rank算法计算每个网页的PageRank分值。Page
主动学习模拟一种人机交互场景，允许学习 算法根据查询策略，主动获取选取样本的真实类 标签，对主动标注的样本进行训练，不断修正已 有分类模型，从而提高分类器的泛化能力和分类 精度。因此，主动学习的主要挑战是制定有效的 样本选择策略。目前，比较常见的主动学习方法 有不确定抽样 (sampling uncertainty, UC)[9] ，基于聚 类 (clustering-based approaches, CBA)[10]和基于委员 会投票采样法 (query-by-committee, QBC)[11]。其 中，不确定性抽样方法选择当前分类器中不确定 度最高的未标注样本进行标注，并将其添加到训 练集中。由于单一分类器存在分类偏好，使得泛 化能力产生定式，而 QBC 通过多种同质或异质分 类器共同参与分类，一般选取冲突性 (不一致 性) 最高的未标注样本进行标注。基于聚类的样 本选择方法旨在通过分析样本间的内在相似性， 对样本进行划簇，而后从每簇中选择代表样本进 行标注。 PageRank[12]建立在随机冲浪模型上，通过计 算网页的 PageRank 分值，解决了互联网搜索引擎 的网页排名问题。PageRank 理论基于两个简单 的假设： 1) 较重要的网页被更多的网页链接； 2)PageRank 分值越高的网页将传递更高的权重。 本文结合 PageRank 理论，将 PageRank 分值作为 样本信息量的度量指标，同时充分考虑样本的分 布信息，提出一种基于 PageRank 的主动学习算法 (PageRank-based active learning algorithm, PAL)，为 主动学习算法中样本的选择问题提供一种可行的 方案。 实验在 8 个公开数据集上进行，通过设置不 同规模的训练集，测试 PAL 算法的分类性能。实 验结果表明，PAL 算法较 Naïve Bayes、J48、kNN[13] 和 One-R 等经典分类算法，通常能得到更高的分 类精度，且与 QBC、KQBC[14]和 MADE[15]等主动学 习算法相比，有更好的分类性能。 1 数据模型 在本节中，主要介绍决策信息系统、PageRank 理论等基本概念。 1.1 决策信息系统 定义 1 决策信息系统[16]。决策信息系统定 义成一个三元组： S = (U,C,d) (1) 式中：U 代表一个非空样本集合，也称论域；C 代 表一个非空条件属性集合；d 指的是样本的决策 U ={x0, x1, x2,··· , x15} C = {a1,a2,a3,a4} 属性。表1是1个决策信息系统， ， 。 表 1 决策信息系统 Table 1 Example of decision system U a1 a2 a3 a4 d x0 5.1 3.5 1.4 0.2 is x1 4.9 3.0 1.4 0.2 is x2 4.7 3.2 1.3 0.2 is x3 4.6 3.1 1.5 0.2 is x4 5.0 3.6 1.4 0.2 is x5 5.4 3.9 1.7 0.4 is x6 7.0 3.2 4.7 1.4 iv x7 6.4 3.2 4.5 1.5 iv x8 6.9 3.1 4.9 1.5 iv x9 5.5 2.3 4.0 1.3 iv x10 6.5 2.8 4.6 1.5 iv x11 6.3 3.3 6.0 2.5 it x12 5.8 2.7 5.1 1.9 it x13 7.1 3.0 5.9 2.1 it x14 6.5 3.0 5.8 2.2 it x15 7.6 3.0 6.6 2.1 it x = [a1 a2 ··· am] y = [b1 b2 ··· bm] 定义 2 曼哈顿距离。向量 与 的曼哈顿距离为 dis(x, y) = ∑m i=1 |ai −bi | (2) 式 (2) 表示在多维空间中两个点之间的距 离。信息表的样本可以用向量表示。相应地，可 以定义任意一组样本的相似度。 (U,C,d) x, y ∈ U 定义 3 相似度。给定一个决策信息系统 S = ，任意 的相似度记为 sim(x, y) = 1 1+dis(x, y) (3) sim(x0, x6) = 0.13 sim(x3, x12) = 0.127 根据式 (2)、式 (3)，可计算表 1 的决策信息系 统中 ， 。 定义 4 邻域。对于任意的样本x ∈ U ，可以 通过设置相似度阈值 θ 的方式确定其邻域，样本 的邻域定义为 n(x, θ) = {y ∈ U|sim(x, y) ⩾ θ} (4) n(x0,0.5) = {x1, x2, x3, x4} 相似度阈值 θ 越小，样本的邻域越大。根据 表 1 所示的决策信息系统可以计算出 。 1.2 PageRank 模型 Web 中的网页通过超链接相互链接，PageRank 算法计算每个网页的 PageRank 分值。Page- ·552· 智 能 系 统 学 报 第 14 卷
第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 的 PageRank 分值 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·
·554· 智能系统学报 第14卷 ={h其 1/ln(x,6儿，x∈n(x, (12) 4)root.setChild (,x); 5)U=U-{x,x 算法1 PageRank排名计算算法 6)else then 输入决策信息系统S=(U,C,d): 7)计算与root最相似的样本xeU; 输出排名向量Rank。 8)计算与x最不相似的样本x,∈U； l)for(eachx∈U)do 9)root.setChild () 2)for (eachyU)do 10)U=U-{x,x, 3)根据式(2)计算dis(xy; 11)end if 4)根据式(3)计算sim(x,y 12)U=0,U,=0 5)end for l3)for(eachx∈U)do 6)根据式(4)计算n(x): 14)if (sim(x,x )sim(x,x,))then 7)end for 15)U,=U,U{x: 8)根据式(12)计算邻接矩阵A: 16)else then 9)k=1: 17)U,=U,U{x 10)T=A+(1-y)E1m: 18)end if 11)P=111 19)end for 12)while (IP -Pl >do 20)对x,U继续调用算法2： 13)P=TPML 21)对x,U继续调用算法2； 14)k++: 22)end while 15)end while 23)return root; 16)Rank sort(P); 35)寻找root的孩子节点，即U中最不相似 17)return Rank: 的一对样本；7)~10)寻找非root节点的孩子节点； 算法1描述了样本的排名向量的计算过程。 12)定义x和x,的样本集合；13)19)通过比较集 1)人7通过计算样本间的相似度，确定每个样本的 合U”中样本与x、x相似度大小，实现集合的划 邻域；10)根据式(9)计算状态转移矩阵T;11) 分：20小21)递归调用算法2。 定义初始分值向量Po;12)15)计算收敛条件下分 2.2.3二叉树聚类算法 值矩阵P:16)对分值矩阵P进行降序排序。 ·般来说，聚类簇数K与聚类质量关系密 2.2.2二又树生成算法 切，然而大多数聚类算法只能通过经验或者试凑 主动学习阶段在二叉树上进行，为了避免离 指定簇数K。本文采用一种执行边缘分离的聚类 群点对该阶段标签查询、预测的影响，保证查询 策略，不需要将K作为输入，而是根据二叉树的 到的样本均具有较高的信息量，仅利用排名前 内部结构自然地分簇。 R的代表样本去构建二叉树。同时，树形结构能 通过计算二叉树节点间的相似度，将二叉树 够充分体现数据的层次关系，便于数据分析，从 的边划分为分割边或者非分割边。假设两节点足 而得到更好的聚类结果。 够相似，可将该连边定义成非分割边，反之定义 二叉树生成算法是一个典型递归算法。其构 为分割边。这种边界划分方式基于一个阈值。第 建过程分为两步：寻找孩子节点，根据孩子节点 一轮迭代时，阈值是二叉树相连节点间相似度的 划分集合。根结点root的孩子节点是U中最不 最小值。 相似的两个样本，其余节点x的左孩子是当前集 算法3二叉树聚类算法 合中与x最相似的样本x,右节点是当前集合中 输入二叉树根节点root: 与x最不相似的节点x,。 输出聚类信息块bl=blbl2bl]o 算法2二叉树生成算法 1)clusterT(root.Ic,count,threshold)start 输入排名前R的代表集合U; 2)cnroot.lc]count; 输出二叉树root。 3)if (root.Ic.Ic!null)then 1)while(U!=0)then 4)if (sim (root.lc,root.lc.lc)s threshold) 2)if(root)then 5)clusterT (root.Ic.Ic.++count,threshold): 3)计算最不相似的一对样本x,x,∈U; 6)else then
a ′ i j = { 1/|n(xi , θ)|, xj ∈ n(xi , θ) 0, 其他 (12) 算法 1 PageRank 排名计算算法 输入 决策信息系统 S = (U, C, d)； 输出 排名向量 Rank。 1) for (each x∈U) do 2) for (each y∈U) do 3) 根据式 (2) 计算 dis(x y); 4) 根据式 (3) 计算 sim(x, y); 5) end for 6) 根据式 (4) 计算 n(x); 7) end for 8) 根据式 (12) 计算邻接矩阵 A; 9) k = 1; 10) T = γA T + (1 − γ)E/n; P0 = [11···1] T 11) 1×n ; 12) while (|Pk − Pk-1| > ε) do 13) Pk = TPk-1; 14) k++; 15) end while 16) Rank = sort(Pk ); 17) return Rank; 算法 1 描述了样本的排名向量的计算过程。 1)~7) 通过计算样本间的相似度，确定每个样本的 邻域； 10) 根据式 (9) 计算状态转移矩阵 T；11) 定义初始分值向量 P0；12)~15) 计算收敛条件下分 值矩阵 P；16) 对分值矩阵 P 进行降序排序。 2.2.2 二叉树生成算法 主动学习阶段在二叉树上进行，为了避免离 群点对该阶段标签查询、预测的影响，保证查询 到的样本均具有较高的信息量，仅利用排名前 R 的代表样本去构建二叉树。同时，树形结构能 够充分体现数据的层次关系，便于数据分析，从 而得到更好的聚类结果。 二叉树生成算法是一个典型递归算法。其构 建过程分为两步：寻找孩子节点，根据孩子节点 划分集合。根结点 root 的孩子节点是 U′中最不 相似的两个样本，其余节点 x 的左孩子是当前集 合中与 x 最相似的样本 xl，右节点是当前集合中 与 xl 最不相似的节点 xr。 算法 2 二叉树生成算法 输入 排名前 R 的代表集合 U′； 输出 二叉树 root。 1) while (U′ != Ø) then 2) if (root) then 3) 计算最不相似的一对样本 xl , xr∈U′; 4) root. setChild (xl , xr ); 5) U′ = U′ − {xl , xr}; 6) else then 7) 计算与 root 最相似的样本 xl∈U′; 8) 计算与 xl 最不相似的样本 xr∈U′; 9) root. setChild (xl , xr ); 10) U′ = U′ − {xl , xr}; 11) end if 12) Ul = Ø, Ur = Ø; 13) for (each x∈U′) do 14) if (sim(x, xl ) > sim(x, xr )) then 15) Ul = Ul ∪ {x}; 16) else then 17) Ur = Ur ∪ {x}; 18) end if 19) end for 20) 对 xl，Ul 继续调用算法 2; 21) 对 xr，Ur 继续调用算法 2; 22) end while 23) return root； 3)~5) 寻找 root 的孩子节点，即 U′中最不相似 的一对样本；7)~10) 寻找非 root 节点的孩子节点； 12) 定义 xl 和 xr 的样本集合；13)~19) 通过比较集 合 U′中样本与 xl、x 相似度大小，实现集合的划 分；20)~21) 递归调用算法 2。 2.2.3 二叉树聚类算法 一般来说，聚类簇数 K 与聚类质量关系密 切，然而大多数聚类算法只能通过经验或者试凑 指定簇数 K。本文采用一种执行边缘分离的聚类 策略，不需要将 K 作为输入，而是根据二叉树的 内部结构自然地分簇。 通过计算二叉树节点间的相似度，将二叉树 的边划分为分割边或者非分割边。假设两节点足 够相似，可将该连边定义成非分割边，反之定义 为分割边。这种边界划分方式基于一个阈值。第 一轮迭代时，阈值是二叉树相连节点间相似度的 最小值。 算法 3 二叉树聚类算法 输入 二叉树根节点 root； bl = [bl1 bl2 ···bl 输出 聚类信息块 k]。 1) clusterT (root.lc，count，threshold) start 2) cn[root.lc] = count; 3) if (root.lc.lc! = null) then 4) if (sim (root.lc, root.lc.lc) ≤ threshold) 5) clusterT (root.lc.lc, ++count, threshold); 6) else then ·554· 智 能 系 统 学 报 第 14 卷
第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·