【机器学习】基于PageRank的主动学习算法

第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 intelli￾gent 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-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 传统的监督学习算法，如 Naïve Bayes[1] 、One￾R [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 中的网页通过超链接相互链接，Page￾Rank 算法计算每个网页的 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 的 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·

·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·

·556· 智能系统学报 第14卷 bL4中o被标记为is。所以x1、2、3、x4和x5被标 针对每个数据集，实验设置训练集以1%为步长， 记为is。 规模由1%增加到10%。在训练集规模不同的情 在本例中，查询7个样本的标签，预测4个样 况下，观察分类精度的变化。在与主动学习算法 本的标签，5个样本通过投票获得标签。无样本 的比较实验中，训练集规模均设置为10%。 被错误标记，因此，精度为100%。 设置二叉树比例R∈20%，50%]，阻尼因子 y∈[0.65,0.95]，极小值=0.01。为了降低实验的 3实验及分析 随机性误差，采用相同参数设置进行10次重复实 在本节中，通过实验将PAL算法与传统的分 验，取得平均值作为实验结果。 类算法、主动学习算法进行比较，并回答以下问题： 实验所用数据集详细信息如表3所示。 1)PAL算法选择代表样本是否具有可靠性， 表3数据集描述 尤其不同二叉树比例R的设置对精度的影响： Table 3 Description of experimental datasets 2)PAL算法是否比其他监督学习算法更精确； 数据集 条件属性 决策属性 数量 3)PAL算法是否比主动学习算法的分类效 Iris 4 3 150 Flame 2 2 240 果好。 E.coli > P 336 3.1实验步骤 Seeds > 3 210 实验结合Weka,在macOS Sierra操作系统下 Diabetes 8 2 768 运行，其硬件配置为：2.6 GHz Intel Core i5处理 Jain 373 Aggregation 2 788 器，8GB1600 MHz DDR3。 Twonorm 20 2 7400 实验采用8个公开的数据集，并将PAL算法 与J48、kNN、Naive Bayes、One-R和Logistics 3.2 参数R对分类效果的影响 这5种传统的监督学习算法进行比较，同时与 在本节中，将回答问题1)。讨论不同的二叉 QBC、KQBC和MADE这3种主动学习算法作对 树比例R对实验精度的影响。表4展现了在训练 比。实验采用分类精度accuracy作为评估指标。 集规模是数据集的10%的情况下，所得精度随 与传统的监督学习分类算法的比较实验中， R的变化情况。 表4PAL算法在不同二叉树构建比例R下分类精度的比较 Table 4 Classification accuracy comparisons of PAL based on different Binary Tree ratios R 数据集 20% 30% 40% 50% 60% 70% 80% 90% 100% Iris 0.9630 0.9556 0.9556 0.8444 0.8222 0.8222 0.8000 0.7926 0.8222 Flame 0 0.9815 0.9861 0.9907 0.9074 0.8796 0.8981 0.8565 0.9537 E.coli 0.7492 0.8086 0.8218 0.8086 0.7657 0.7426 0.7360 0.7096 0.7459 Seeds 0.9000 0.8942 0.8836 0.8783 0.8730 0.8889 0.8889 0.6296 0.8995 Diabetes 0.6488 0.6879 0.7153 0.6936 0.6517 0.6503 0.6488 0.6445 0.6965 Jain 1.0000 1.0000 0.9940 0.9881 0.9792 0.9792 0.9732 0.9673 1.0000 Aggregation 1.0000 0.9859 0.9930 0.9225 0.9183 0.9324 0.9732 0.9648 0.9563 Twonorm 0.9710 0.9653 0.9616 0.9599 0.9530 0.9384 0.9300 0.9276 0.9560 由表4可以看出，对于不同的数据集，最佳的 的分簇效果，因此二叉树比例取值较小时，能够 二叉树比例取值存在差异。但从整体来看，最佳 保证查询到的样本都具有高信息量，反而分类精 取值都集中在20,50]区间。 度更高。 实验结果符合数据集样本的分布规律，信息 较大数据集，如Twonorm、Aggregation,R比 量较高的样本所占的比例较小。二叉树比例取值 例较小，所选代表样本构成的树形结构也能很好 越大时，越多的信息量低的样本参与到二叉树的 地表现样本的层次结构，因此对分类精度不会有 构建，一些离群点、边界点影响聚类结果，而导致 较大影响。 分类错误。同时表明，将PageRank分值作为样本 在本文后续的研究讨论中，R当作经验参数 信息量的度量指标具有可靠性。 参与二叉树的构建。 Iris、Seeds、Twonorm数据集样本均匀，不存 3.3与经典算法对比 在样本倾斜问题，二叉树聚类算法能够获得很好 在本节中，将回答第二个问题。PAL在8个

bl4 中 x0 被标记为 is。所以 x1、x2、x3、x4 和 x5 被标 记为 is。 在本例中，查询 7 个样本的标签，预测 4 个样 本的标签，5 个样本通过投票获得标签。无样本 被错误标记，因此，精度为 100%。 3 实验及分析 在本节中，通过实验将 PAL 算法与传统的分 类算法、主动学习算法进行比较，并回答以下问题： 1) PAL 算法选择代表样本是否具有可靠性， 尤其不同二叉树比例 R 的设置对精度的影响； 2) PAL 算法是否比其他监督学习算法更精确； 3) PAL 算法是否比主动学习算法的分类效 果好。 3.1 实验步骤 实验结合 Weka，在 macOS Sierra 操作系统下 运行，其硬件配置为：2.6 GHz Intel Core i5 处理 器，8 GB 1600 MHz DDR3。 实验采用 8 个公开的数据集，并将 PAL 算法 与 J48、kNN、Naïve Bayes、One-R 和 Logistics[18] 这 5 种传统的监督学习算法进行比较，同时与 QBC、KQBC 和 MADE 这 3 种主动学习算法作对 比。实验采用分类精度 accuracy 作为评估指标。 与传统的监督学习分类算法的比较实验中， 针对每个数据集，实验设置训练集以 1% 为步长， 规模由 1% 增加到 10%。在训练集规模不同的情 况下，观察分类精度的变化。在与主动学习算法 的比较实验中，训练集规模均设置为 10%。 设置二叉树比例 R∈[20%, 50%]，阻尼因子 γ∈[0.65, 0.95]，极小值 ε=0.01。为了降低实验的 随机性误差，采用相同参数设置进行 10 次重复实 验，取得平均值作为实验结果。 实验所用数据集详细信息如表 3 所示。 表 3 数据集描述 Table 3 Description of experimental datasets 数据集 条件属性 决策属性 数量 Iris 4 3 150 Flame 2 2 240 E.coli 7 8 336 Seeds 7 3 210 Diabetes 8 2 768 Jain 2 2 373 Aggregation 2 7 788 Twonorm 20 2 7 400 3.2 参数 R 对分类效果的影响 在本节中，将回答问题 1)。讨论不同的二叉 树比例 R 对实验精度的影响。表 4 展现了在训练 集规模是数据集的 10% 的情况下，所得精度随 R 的变化情况。 表 4 PAL 算法在不同二叉树构建比例 R 下分类精度的比较 Table 4 Classification accuracy comparisons of PAL based on different Binary Tree ratios R 数据集 20% 30% 40% 50% 60% 70% 80% 90% 100% Iris 0.963 0 0.955 6 0.955 6 0.844 4 0.822 2 0.822 2 0.800 0 0.792 6 0.822 2 Flame 0 0.981 5 0.986 1 0.990 7 0.907 4 0.879 6 0.898 1 0.856 5 0.953 7 E.coli 0.749 2 0.808 6 0.821 8 0.808 6 0.765 7 0.742 6 0.736 0 0.709 6 0.745 9 Seeds 0.900 0 0.894 2 0.883 6 0.878 3 0.873 0 0.888 9 0.888 9 0.629 6 0.899 5 Diabetes 0.648 8 0.687 9 0.715 3 0.693 6 0.651 7 0.650 3 0.648 8 0.644 5 0.696 5 Jain 1.000 0 1.000 0 0.994 0 0.988 1 0.979 2 0.979 2 0.973 2 0.967 3 1.000 0 Aggregation 1.000 0 0.985 9 0.993 0 0.922 5 0.918 3 0.932 4 0.973 2 0.964 8 0.956 3 Twonorm 0.971 0 0.965 3 0.961 6 0.959 9 0.953 0 0.938 4 0.930 0 0.927 6 0.956 0 由表 4 可以看出，对于不同的数据集，最佳的 二叉树比例取值存在差异。但从整体来看，最佳 取值都集中在[20, 50]区间。 实验结果符合数据集样本的分布规律，信息 量较高的样本所占的比例较小。二叉树比例取值 越大时，越多的信息量低的样本参与到二叉树的 构建，一些离群点、边界点影响聚类结果，而导致 分类错误。同时表明，将 PageRank 分值作为样本 信息量的度量指标具有可靠性。 Iris、Seeds、Twonorm 数据集样本均匀，不存 在样本倾斜问题，二叉树聚类算法能够获得很好 的分簇效果，因此二叉树比例取值较小时，能够 保证查询到的样本都具有高信息量，反而分类精 度更高。 较大数据集，如 Twonorm、Aggregation，R 比 例较小，所选代表样本构成的树形结构也能很好 地表现样本的层次结构，因此对分类精度不会有 较大影响。 在本文后续的研究讨论中，R 当作经验参数 参与二叉树的构建。 3.3 与经典算法对比 在本节中，将回答第二个问题。PAL 在 8 个 ·556· 智 能 系 统 学 报 第 14 卷

第3期 邓思宇，等：基于PageRank的主动学习算法 ·557. 数据集上与J48、Naive Bayes、kNN、One-R和Lo- 以及对比算法在不同训练集比例下的分类精度变 gistics经典算法做了对比。图4展示了PAL算法 化趋势。 1.0 10 0 0.8 06 —PAL 0.6 kNN 0.4 J48 Bayes ·一PAL kNN +Bayes Onepous ★一 Onepous -J48 ■L0gi1 stics ■Logistics 0.2 0.4 0.02 0.040.06 0.08 0.10 0.02 0.04 0.06 0.08 0.10 训练集比例 训练集比例 (a)Iris (b)Flame 1.0 0.75 0.8 0.70 0.6 0.65 0.4 --PAL kNN ◆-J48 0.60 J48 0.2 Baves Bayes Onep ★-Onepous Logistics ■-Log1 stics 0.55 0.02 0.040.06 0.08 0.10 0 0.02 0.040.06 0.080.10 训练集比例 训练集比例 (c)E.coli (d)Diabetes 1.0 1.0 0.8 0.8 06 举0.6 PAL ◆-PAL kNN kNN J48 04 ◆J48 0.4 Bayes Bayes nepou Logistics LogistIcs 02 0.020.040.06 0.2 0.080.10 0.02 0.040.06 0.080.10 训练集比例 训练集比例 (e)Seeds (f)Twonorm 1.0 1.0 0.9 0.8 0.8 1 0.7 PAL kNN J48 0.4 ◆ J48 Baves Bayes 0.6 Onepous ★Onepous -Logistics ■一Logistics 0.2 0.5 0.02 0.04.0.06 0.08 0.10 0.02 0.040.06 0.080.10 训练集比例 训练集比例 (g)Aggregation (h)Jain 图4与经典算法对比 Fig.4 Comparison with classical algorithms

数据集上与 J48、Naïve Bayes、kNN、One-R 和 Lo￾gistics 经典算法做了对比。图 4 展示了 PAL 算法 以及对比算法在不同训练集比例下的分类精度变 化趋势。 1.0 0.8 0.6 0.4 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (b) Flame 精度 PAL kNN J48 Bayes Onepous Logistics 1.0 0.8 0.6 0.4 0 0.2 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (c) E.coli 精度 PAL kNN J48 Bayes Onepous Logistics 0.75 0.70 0.65 0.60 0.55 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (d) Diabetes 精度 PAL kNN J48 Bayes Onepous Logistics 1.0 0.8 0.6 0.4 0.2 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (g) Aggregation 精度 PAL kNN J48 Bayes Onepous Logistics 1.0 0.8 0.6 0.4 0.2 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (a) Iris 精度 PAL kNN J48 Bayes Onepous Logistics 1.0 0.8 0.7 0.6 0.9 0.5 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (h) Jain 精度 PAL kNN J48 Bayes Onepous Logistics 1.0 0.8 0.6 0.4 0.2 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (e) Seeds 精度 PAL kNN J48 Bayes Onepous Logistics 1.0 0.8 0.6 0.4 0.2 0 0.02 0.04 0.06 0.08 0.10 训练集比例 (f) Twonorm 精度 PAL kNN J48 Bayes Onepous Logistics 图 4 与经典算法对比 Fig. 4 Comparison with classical algorithms 第 3 期 邓思宇，等：基于 PageRank 的主动学习算法 ·557·

·558 智能系统学报 第14卷 实验结果表明，本文提出的PAL算法在Iris、 表5PAL与3种主动学习算法的比较 Flame、Ecoli、Seeds、Aggregation和Jain数据 Table 5 Accuracies of PAL and three active learning algorithms 集上，分类精度高于对比的经典算法，尤其是 Flame数据集，在实验所选的训练集比例下，分类 数据集 QBC KOBC MADE PAL 精度均高于经典分类算法。在Twonorm数据集 Iris 0.9370 0.8998 0.9185 0.9556 上也能取得较好的分类精度，分类精度达到 Flame 0.9463 0.7144 0.9861 0.9861 97%,仅略低于Naive Bayes算法。在Diabetes数 Ecoli 0.8297 0.5910 0.7152 0.8218 据集上优势不明显，尤其是在Diabetes数据集上， Seeds 0.8767 0.8458 0.8571 0.8836 PAL算法分类精度高于kNN、J48和One-R,但是 Diabetes 0.70880.6479 0.6889 0.7153 低于Naive Bayes和Logistics, Jain 0.9607 0.9182 1.0000 0.9940 图4(b)、(d)、(①显示，在实验所选的所有训练 集规模下，对应数据集上PAL算法分类精度均高 Aggregation 0.8917 0.6272 0.9944 0.9930 于kNN算法；图(a)、(c)、(e(g、(h)显示，在多数 Twonorm 0.9023 0.94290.9527 0.9616 训练集规模下，对应数据集上PAL算法分类精度 AveRank 2.5000 3.9000 2.1000 1.4000 高于kNN算法。PAL对代表样本采用主动学习 算法进行标记和预测，而对于剩余样本则采用 4结束语 kNN进行预测。因此，当二叉树比例R=O时，PAL 算法将退化成KNN算法。该结果表明，PAL的 本文提出了一种基于PageRank的主动学习 样本选择策略和主动学习算法具有可行性。 算法，为样本的选择问题提供了一种可行的方 图4(a)、(b)、(d)、(e)、(h)显示，在训练集规模 案。利用PageRank理论发现信息量较高的代表 极小的情况下，如R=10%时，PAL较其他经典算 样本，从而在该集群上构建二叉树，用来表示样 法能取得较好的分类精度；图4(a)、(b)、(e)、(g)显 本的层次结构。在二叉树上进行迭代聚类，标记 示，训练集规模为30%之前，PAL算法的分类精 和预测，能够保证查询到的样本分布均匀，同时 度快速地上升，逐渐趋于稳定，说明PageRank分 避免离群点的影响。用代表对象训练得到分类模 值作为样本信息量的度量指标具有可靠性，结合 型，采用kNN算法处理剩余样本。实验结果表 聚类算法，利用样本的分布信息能够有效地进行 明，PAL算法相比于Naive Bayes和J48等传统分 类算法，能得到更高的分类精度，且与OBC等主 样本选择。 动学习算法相比，分类效果更好。 图4(a)、(b)、(e)、(f)显示，在Iris、Flame、 Seeds数据集上分类时，训练集的规模对PAL分 参考文献： 类精度影响不明显，是因为数据集太小，训练集 [1]MNNS,傅顺开，吕天依，等.一般贝叶斯网络分类器及 比例对分类效果影响较低。在Twonorm数据集 其学习算法】.计算机应用研究，2016,33(5)：1327- 上，训练集的规模对所有算法的分类精度影响均 1334 不明显，说明在该数据集上数据分布较为均匀。 MINN S,FU Shunkai,LV Tianyi,et al.Algorithm for ex- 3.4与主动学习算法对比 act recovery of Bayesian network for classification[].Ap- 将PAL算法与流行的3种主动算法进行比 plication research of computer,2016,33(5):1327-1334. 较。表5展现了在训练集规模是数据集的10%， [2]王翔，胡学钢，杨秋洁.基于One-R的改进随机森林入侵 R设置为40%的情况下，QBC、KQBC、MADE和 检测模型研究[).合肥工业大学学报（自然科学版）， PAL的分类精度。为了更清晰地展示各个算法的 2015,38(5):627-630,711. 性能差异，设计以排名为衡量标准的评估方法。 WANG Xiang,HU Xuegang,YANG Qiujie.Research on 从总体上看，本文提出的PAL算法与其他主 improved intrusion detection model with random forest 动学习算法比较平均排名靠前。PAL算法在Iis、 based on feature evaluation of One-R[J].Journal of Hefei University of Technology (natural science),2015,38(5): Flame、Seeds、Diabetes和Twonorm数据集上，分 627-630,711. 类精度高于其他对比的主动学习算法，尤其在 [3]YANG Yi,CHEN Wenguang.Taiga:performance optim- Flame数据集上，分类精度达到98%。在Ecoli、 ization of the C4.5 decision tree construction algorithm[J] Jain和Aggregation数据集上也有很好的分类表现。 Tsinghua science and technology,2016,21(4):415-425

实验结果表明，本文提出的 PAL 算法在 Iris、 Flame、Ecoli、Seeds、Aggregation 和 Jain 数据 集上，分类精度高于对比的经典算法，尤其是 Flame 数据集，在实验所选的训练集比例下，分类 精度均高于经典分类算法。在 Twonorm 数据集 上也能取得较好的分类精度，分类精度达 到 97%，仅略低于 Naïve Bayes 算法。在 Diabetes 数 据集上优势不明显，尤其是在 Diabetes 数据集上， PAL 算法分类精度高于 kNN、J48 和 One-R，但是 低于 Naïve Bayes 和 Logistics。 图 4(b)、(d)、(f) 显示，在实验所选的所有训练 集规模下，对应数据集上 PAL 算法分类精度均高 于 kNN 算法；图 (a)、(c)、(e)、(g)、(h) 显示，在多数 训练集规模下，对应数据集上 PAL 算法分类精度 高于 kNN 算法。PAL 对代表样本采用主动学习 算法进行标记和预测，而对于剩余样本则采用 kNN 进行预测。因此，当二叉树比例 R=0 时，PAL 算法将退化成 KNN 算法。该结果表明，PAL 的 样本选择策略和主动学习算法具有可行性。 图 4(a)、(b)、(d)、(e)、(h) 显示，在训练集规模 极小的情况下，如 R=10% 时，PAL 较其他经典算 法能取得较好的分类精度；图 4(a)、(b)、(e)、(g) 显 示，训练集规模为 30% 之前，PAL 算法的分类精 度快速地上升，逐渐趋于稳定，说明 PageRank 分 值作为样本信息量的度量指标具有可靠性，结合 聚类算法，利用样本的分布信息能够有效地进行 样本选择。 图 4(a)、(b)、(e)、(f) 显示，在 Iris、Flame、 Seeds 数据集上分类时，训练集的规模对 PAL 分 类精度影响不明显，是因为数据集太小，训练集 比例对分类效果影响较低。在 Twonorm 数据集 上，训练集的规模对所有算法的分类精度影响均 不明显，说明在该数据集上数据分布较为均匀。 3.4 与主动学习算法对比 将 PAL 算法与流行的 3 种主动算法进行比 较。表 5 展现了在训练集规模是数据集的 10%， R 设置为 40% 的情况下，QBC、KQBC、MADE 和 PAL 的分类精度。为了更清晰地展示各个算法的 性能差异，设计以排名为衡量标准的评估方法。 从总体上看，本文提出的 PAL 算法与其他主 动学习算法比较平均排名靠前。PAL 算法在 Iris、 Flame、Seeds、Diabetes 和 Twonorm 数据集上，分 类精度高于其他对比的主动学习算法，尤其在 Flame 数据集上，分类精度达到 98%。在 Ecoli、 Jain 和 Aggregation 数据集上也有很好的分类表现。 表 5 PAL 与 3 种主动学习算法的比较 Table 5 Accuracies of PAL and three active learning algorithms 数据集 QBC KQBC MADE PAL Iris 0.937 0 0.899 8 0.918 5 0.955 6 Flame 0.946 3 0.714 4 0.986 1 0.986 1 Ecoli 0.829 7 0.591 0 0.715 2 0.821 8 Seeds 0.876 7 0.845 8 0.857 1 0.883 6 Diabetes 0.708 8 0.647 9 0.688 9 0.715 3 Jain 0.960 7 0.918 2 1.000 0 0.994 0 Aggregation 0.891 7 0.627 2 0.994 4 0.993 0 Twonorm 0.902 3 0.942 9 0.952 7 0.961 6 AveRank 2.500 0 3.900 0 2.100 0 1.400 0 4 结束语 本文提出了一种基于 PageRank 的主动学习 算法，为样本的选择问题提供了一种可行的方 案。利用 PageRank 理论发现信息量较高的代表 样本，从而在该集群上构建二叉树，用来表示样 本的层次结构。在二叉树上进行迭代聚类，标记 和预测，能够保证查询到的样本分布均匀，同时 避免离群点的影响。用代表对象训练得到分类模 型，采用 kNN 算法处理剩余样本。实验结果表 明，PAL 算法相比于 Naïve Bayes 和 J48 等传统分 类算法，能得到更高的分类精度，且与 QBC 等主 动学习算法相比，分类效果更好。 参考文献： MINN S, 傅顺开, 吕天依, 等. 一般贝叶斯网络分类器及 其学习算法[J]. 计算机应用研究, 2016, 33(5): 1327– 1334. MINN S, FU Shunkai, LV Tianyi, et al. Algorithm for ex￾act recovery of Bayesian network for classification[J]. Ap￾plication research of computer, 2016, 33(5): 1327–1334. [1] 王翔, 胡学钢, 杨秋洁. 基于 One-R 的改进随机森林入侵 检测模型研究[J]. 合肥工业大学学报 (自然科学版), 2015, 38(5): 627–630, 711. WANG Xiang, HU Xuegang, YANG Qiujie. Research on improved intrusion detection model with random forest based on feature evaluation of One-R[J]. Journal of Hefei University of Technology (natural science), 2015, 38(5): 627–630, 711. [2] YANG Yi, CHEN Wenguang. Taiga: performance optim￾ization of the C4.5 decision tree construction algorithm[J]. Tsinghua science and technology, 2016, 21(4): 415–425. [3] ·558· 智 能 系 统 学 报 第 14 卷

第3期 邓思宇，等：基于PageRank的主动学习算法 ·559· [4]ZHOU Xueyuan,BELKIN M.Semi-supervised [14]GILAD-BACHRACH R,NAVOT A,TISHBY N.Ker- learning[J]//ournal of the royal statistical society,2010, nel query by committee (KQBC)[R].Technical Report 172(2):530 2003-88,Leibniz Center,the Hebrew University,2003. [5]WANG Min,MIN Fan,ZHANG Zhiheng,et al.Active [15]CAI Deng,HE Xiaofei.Manifold adaptive experimental learning through density clustering[J].Expert systems with design for text categorization[J].IEEE transactions on applications,2017,85:305-317. knowledge and data engineering,2012,24(4):707-719. [6]胡小娟，刘磊，邱宁佳.基于主动学习和否定选择的垃圾 [16]MIN Fan,ZHU W.A competition strategy to cost-sensit- 邮件分类算法.电子学报，2018,46(1)：203-209， ive decision trees[Cl//Proceedings of the 7th International HU Xiaojuan,LIU Lei,QIU Ningjia.A novel spam cat- Conference on Rough Sets and Knowledge Technology. egorization algorithm based on active learning method and Chengdu,China,2012:359-368. negative selection algorithm[J].Acta electronica sinica, [17]刀张桃，吴小伟.基于PageRank的马尔可夫链研究).电 2018,46(1):203-209. 子设计工程，2017,25(9：36-38 [7]SYED A R.ROSENBERG A,KISLAL E.Supervised and ZHANG Tao,WU Xiaowei.The study of Markov chains unsupervised active learning for automatic speech recogni- based on PageRank[J].Electronic design engineering, tion of low-resource languages[C]//Proceedings of 2016 2017,25(9):36-38. IEEE International Conference on Acoustics,Speech and [18]LIU Dun,LI Tianrui,LIANG Decui.Incorporating logist- Signal Processing.Shanghai,China,2016:5320-5324. ic regression to decision-theoretic rough sets for classific- [8]SUN Shujin,ZHONG Ping,XIAO H,et al.An MRF mod- ations[J].International journal of approximate reasoning, el-based active learning framework for the spectral-spatial 2014,55(1:197-210. classification of hyperspectral imagery[J].IEEE journal of 作者简介： selected topics in signal processing,2015,9(6):1074-1088. 邓思宇，女，1993年生，硕士研究 [9]YANG Yi,MA Zhigang,NIE Feiping,et al.Multi-class 生，主要研究方向为代价敏感学习、主 active learning by uncertainty sampling with diversity 动学习。 maximization[J.International journal of computer vision. 2015,113(2):113-127. [10]XIONG Sicheng,AZIMI J,FERN X Z.Active learning of constraints for semi-supervised clustering[J].IEEE trans- actions on knowledge and data engineering,2014,26(1): 刘福伦，男，1993年生，硕土研究 43-54. 生，主要研究方向为代价敏感学习、粗 [11]BLOODGOOD M.Support vector machine active learn- 糙集、主动学习。 ing algorithms with query-by-committee versus closest- to-hyperplane selection[C]//Proceedings of 2018 IEEE 12th International Conference on Semantic Computing. Laguna Hills,USA,2018:148-155. [12]BRIN SERGEY,PAGE Lawrence.The anatomy of a 黄雨婷，女，1996年生，主要研究 方向为推荐系统。 large-scale hypertextual web search engine [J].Computer networks and ISDN systems,1998,30(1/7):107-117. [13]DENG Zhenyun,ZHU Xiaoshu,CHENG Debo,et al.Ef- ficient kNN classification algorithm for big data[J]. Neurocomputing,2016,195:143-148

ZHOU Xueyuan, BELKIN M. Semi-supervised learning[J]//Journal of the royal statistical society, 2010, 172(2): 530. [4] WANG Min, MIN Fan, ZHANG Zhiheng, et al. Active learning through density clustering[J]. Expert systems with applications, 2017, 85: 305–317. [5] 胡小娟, 刘磊, 邱宁佳. 基于主动学习和否定选择的垃圾 邮件分类算法[J]. 电子学报, 2018, 46(1): 203–209. HU Xiaojuan, LIU Lei, QIU Ningjia. A novel spam cat￾egorization algorithm based on active learning method and negative selection algorithm[J]. Acta electronica sinica, 2018, 46(1): 203–209. [6] SYED A R, ROSENBERG A, KISLAL E. Supervised and unsupervised active learning for automatic speech recogni￾tion of low-resource languages[C]// Proceedings of 2016 IEEE International Conference on Acoustics, Speech and Signal Processing. Shanghai, China, 2016: 5320–5324. [7] SUN Shujin, ZHONG Ping, XIAO H, et al. An MRF mod￾el-based active learning framework for the spectral-spatial classification of hyperspectral imagery[J]. IEEE journal of selected topics in signal processing, 2015, 9(6): 1074–1088. [8] YANG Yi, MA Zhigang, NIE Feiping, et al. Multi-class active learning by uncertainty sampling with diversity maximization[J]. International journal of computer vision, 2015, 113(2): 113–127. [9] XIONG Sicheng, AZIMI J, FERN X Z. Active learning of constraints for semi-supervised clustering[J]. IEEE trans￾actions on knowledge and data engineering, 2014, 26(1): 43–54. [10] BLOODGOOD M. Support vector machine active learn￾ing algorithms with query-by-committee versus closest￾to-hyperplane selection[C]//Proceedings of 2018 IEEE 12th International Conference on Semantic Computing. Laguna Hills, USA, 2018: 148–155. [11] BRIN SERGEY, PAGE Lawrence. The anatomy of a large-scale hypertextual web search engine [J]. Computer networks and ISDN systems, 1998, 30(1/7): 107-117. [12] DENG Zhenyun, ZHU Xiaoshu, CHENG Debo, et al. Ef￾ficient kNN classification algorithm for big data[J]. Neurocomputing, 2016, 195: 143–148. [13] GILAD-BACHRACH R, NAVOT A, TISHBY N. Ker￾nel query by committee (KQBC)[R]. Technical Report 2003–88, Leibniz Center, the Hebrew University, 2003. [14] CAI Deng, HE Xiaofei. Manifold adaptive experimental design for text categorization[J]. IEEE transactions on knowledge and data engineering, 2012, 24(4): 707–719. [15] MIN Fan, ZHU W. A competition strategy to cost-sensit￾ive decision trees[C]//Proceedings of the 7th International Conference on Rough Sets and Knowledge Technology. Chengdu, China, 2012: 359–368. [16] 张桃, 吴小伟. 基于 PageRank 的马尔可夫链研究[J]. 电 子设计工程, 2017, 25(9): 36–38. ZHANG Tao, WU Xiaowei. The study of Markov chains based on PageRank[J]. Electronic design engineering, 2017, 25(9): 36–38. [17] LIU Dun, LI Tianrui, LIANG Decui. Incorporating logist￾ic regression to decision-theoretic rough sets for classific￾ations[J]. International journal of approximate reasoning, 2014, 55(1): 197–210. [18] 作者简介： 邓思宇，女，1993 年生，硕士研究 生，主要研究方向为代价敏感学习、主 动学习。 刘福伦，男，1993 年生，硕士研究 生，主要研究方向为代价敏感学习、粗 糙集、主动学习。 黄雨婷，女，1996 年生，主要研究 方向为推荐系统。 第 3 期 邓思宇，等：基于 PageRank 的主动学习算法 ·559·