结合聚类边界采样的主动学习

胡峰,  李路正,  代劲,  刘群

downloadPDF
胡峰, 李路正, 代劲, 等. 结合聚类边界采样的主动学习 [J]. 智能系统学报, 2024, 19(2): 482-492. doi: 10.11992/tis.202205020
引用本文: 胡峰, 李路正, 代劲, 等. 结合聚类边界采样的主动学习 [J]. 智能系统学报, 2024, 19(2): 482-492. doi: 10.11992/tis.202205020
shu
HU Feng, LI Luzheng, DAI Jin, et al. Active learning combined with clustering boundary sampling [J]. CAAI Transactions on Intelligent Systems, 2024, 19(2): 482-492. doi: 10.11992/tis.202205020
Citation: HU Feng, LI Luzheng, DAI Jin, et al. Active learning combined with clustering boundary sampling [J]. CAAI Transactions on Intelligent Systems, 2024, 19(2): 482-492. doi: 10.11992/tis.202205020
shu

结合聚类边界采样的主动学习

doi: 10.11992/tis.202205020

  • 重庆邮电大学 计算机科学与技术学院, 重庆 400065

基金项目: 国家重点研发计划项目（2018YFC0832102）；重庆市教委重点合作项目（HZ2021008）；重庆市自然科学基金项目（cstc2021jcyj-msxmX0849）.
详细信息
    作者简介:

    胡峰，教授，博士，主要研究方向为粗糙集、粒计算、数据挖掘。主持和参与国家自然科学基金项目4项，参与科技部重点研发计划项目3项，作为参与者获吴文俊人工智能科学技术奖、重庆市自然科学奖各1项，发表学术论文40余篇。E-mail：hufeng@ cqupt.edu.cn;

    李路正，硕士研究生，主要研究方向为数据挖掘、主动学习。E-mail：isluzheng.li@foxmail.com;

    代劲，教授，博士，重庆邮电大学软件学院副院长。主要研究方向为大数据知识工程、智能信息处理。先后承担和完成省部级科研项目4项，出版专著1部，发表学术论文20余篇。E-mail：331545392@qq.com.

    通讯作者:

    胡峰. E-mail：hufeng@cqupt.edu.cn.

  • 中图分类号: TP301

Active learning combined with clustering boundary sampling

  • School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

    摘要
  • 摘要: 主动学习是一种机器学习方法，需要选择最有价值的样本进行标注。目前，主动学习在应用时面临着一些挑战，其依赖分类器的先验假设，这容易导致分类器性能意外下降，同时需要一定规模的样本作为启动条件。聚类可以降低问题规模，是主动学习的一种有效手段。为此，结合密度聚类边界采样，开展主动学习方法的研究。针对容易产生分类错误的聚类边界区域，通过计算样本密度，提出一种密度峰值聚类边界点采样方法；在此基础上，给出密度熵的定义，并利用密度熵对聚类边界区域进行启发式搜索，提出一种基于聚类边界采样的主动学习方法。试验结果表明，与文献中的5种主动学习算法相比，该算法能够以更少标记量获得同等甚至更高的分类性能，是一种有效的主动学习算法；在标记不足，无标签样本总量20%的情况下，算法在Accuracy、F-score等指标上取得较好的结果。

     

    Abstract: Active learning is a machine learning method that requires the selection of the most valuable samples for labeling. Currently, active learning encounters certain challenges in its practical application. It relies on prior assumptions of the classifier, which can lead to unexpected declines in classifier performance and requires a specific number of samples as an initial condition. Clustering, which can reduce the complexity of a problem, serves as an effective tool in active learning. Based on density clustering boundary sampling, this study focuses on active learning methods. First, a method of sampling boundary points in density peak clustering is introduced. This method calculates the sample density for a clustering boundary region that is prone to classification errors. Subsequently, with a specified definition of density entropy, an active learning method based on cluster boundary sampling is proposed. This method employs density entropy for the heuristic search of cluster boundary regions. The experimental results show that the proposed algorithm, compared with the five active learning algorithms referenced in the literature, can achieve equal or even higher classification performance with fewer markers. This proves that it is an effective active learning algorithm. When the number of labeled samples is less than 20% of the total number of unlabeled samples, the algorithm achieves better results in the accuracy and F-score metrics.

     

    • HTML全文

  • 当前，机器学习算法所需要处理的数据规模越来越大。传统的监督学习模型在训练时需要大量的已标记数据集，然而在许多领域，标记样本依赖于特定领域的专家知识，这使得标记的成本十分高昂，如：异常流量监测[1]、医学诊断[2]、图像分割[3]、金融交易领域的欺诈识别[4]以及流体力学计算[5]等。

    作为一种机器学习方法，主动学习能够在减小标记代价的同时，以更少的样本训练得到一个满足预期指标的模型。以分类问题为例，主动学习算法可以让模型选出最难区分的样本，交付领域专家进行标记。主动学习的模型训练过程可以避免一些冗余样本的加入，在降低标记成本的同时能够使分类器的精度快速达到预期值。主动学习的核心在于如何选取最有价值的样本进行标记，根据场景可分为基于池的主动学习(pool-based)、基于流的主动学习(stream-based)以及基于成员合成查询的主动学习(membership query synthesis-based)。本研究讨论基于池的主动学习[6]，目前研究方法主要包括以下几种流行观点。

    1) 基于信息量的观点。此类方法通过不确定性实现样本的选择。不确定性的度量有多种方法，Lewis等[7]利用信息熵刻画每个样本的不确定性，优先选取熵最大的样本进行标记。Kee等[8]在批处理模式下构建多个分类器构成的委员会，选择委员会的预测分歧最大的样本进行标记。Shao等[9]将基于委员会查询的思想应用于迁移学习领域，通过维护来自源域与目标域的不同委员会成员，以提高分类准确率。

    2) 基于代表性的观点。此类方法主要通过密度计算或者聚类实现。基于密度的方法从空间中高密度区域选择具有代表性的样本，这样可以避免离群点问题。Density-Weighted方法[10]考虑某个未标记样本点与其他未标记样本之间的平均相似度，用于描述该未标记样本点的代表性。基于聚类的方法先对输入空间进行聚类，然后在各簇中选取代表性实例。如Min等[11]在文中基于三支决策思想[12]提出了TACS(three-way active learning through clustering selection)算法，其用聚类将数据集层次二分为数据块，在此过程中根据块中样本的特点又分为3种操作：如果块中没有足够的已标记样本，则查询代表性实例；如果块中有足够的同标签的已标记样本，则对块中的其他实例进行分类；如果块中有不同标签的已标记样本，则对块进一步聚类。

    3) 基于信息量和代表性的观点。一些研究人员试图结合信息量和代表性开展相关研究，但两者需要权衡，当实例的信息量较高时，其代表性通常会降低。基于min-max框架[13]，Huang等[14]在2014年提出了QUIRE(querying informative and representative examples)，该方法使用已标记样本的预测精度度量信息量，用未标记样本的预测精度度量代表性。

    4) 其他观点。一些方法不是简单的基于信息量或代表性，而是基于新的观点或理论。Dong[15]提出了基于改进的支持向量机(cost-sensitive SVM，CSSVM)的主动学习算法，以解决网络流量识别中的不平衡问题。Siddiqui等[16]提出一种用于语义分割的多视图主动学习策略（ViewAL），通过结合不同视图预测的不一致性来评估模型的不确定性，该方法能有效降低语义分割的模型训练时间和标注代价。聚类边界的几何采样是最近出现的一种观点，认为聚类边界点是潜在的标记样本，这些样本对于分类器的提升具有真正的价值。从版本空间理论来看，基于不确定性和代表性的策略可以看成是近似为超球体的版本空间上的内部体积采样和外部体积采样[17]。Cao[18]在论文中提出一种基于骑士巡游的几何边界主动学习方法——GAL(geometric active learning)，将主动学习的不确定性采样问题转为了聚类边界点的几何采样问题，摆脱了分类器的假设依赖。GAL计算各样本距离其$k$个近邻点的概率路径转移长度，并通过该值的大小区分聚类核心点与边界点。

    密度峰值聚类算法(density peak clustering，DPC)[19]是Rodriguez和Laio提出的一种聚类方法，根据数据的结构和层次关系，可以从中发现高密度点和密度更高但距离较远的点。利用聚类中心由局部较低密度点包围的基本假设，该方法可识别任意形状的数据结构，也利于发现离群点。利用密度峰值聚类算法，既可以通过密度峰值点将数据快速划分为多个密度区域，又可以在聚类边界区域获取易错分的点。如果能兼顾二者，则将是进行主动学习的有效途径。

    针对主动学习算法启动缓慢、未标记样本严重依赖初始假设的问题。本研究结合密度峰值聚类的局部密度概念和聚类边界的几何采样思想，开展了主动学习方法的研究。首先，提出了一种基于密度峰值的聚类边界点采样方法；在此基础上，提出一种主动学习算法——基于聚类边界采样的主动学习方法（boudary sampling with density entropy，BSDE），该算法使用密度熵对聚类边界区域进行启发式搜索，进而获取兼具信息量和代表性的聚类边界样本点进行标记。文中的算法与5种先进的主动学习算法进行了对比，试验结果表明，本研究提出的算法是一种有效的主动学习算法，能够以更少标记量使分类器取得更高的性能。

    1.   相关工作

    1.1   密度峰值聚类

    密度峰值聚类是一种基于密度的聚类算法，该算法建立在2个基本假设[19]之上：一是聚类中心由其局部密度较低的近邻点包围；二是这些聚类中心相比于其密度更高的点，距离较远。对于每个样本点，密度峰值算法要求计算2个量：局部密度(${\rho _i}$)和较该点密度更大的最近点距离(${\delta _i}$)。

    每个样本点$i$的数据密度${\rho _i}$是指小于截断距离的近邻样本点数，计算公式为

    $$ {\rho _i} = \rho (i) = \sum\limits_j \chi \left( {{d_{ij}} - {d_{{c}}}} \right) $$ (1)

    式中：$ {d_{ij}} $为样本点$i$和样本点$j$的距离，通常使用欧氏距离；${d_c}$为截断距离，可以人为设置或者根据样本点对距离的分布自动设置；${\delta _i}$是样本点$i$较其密度更大样本点的距离最小值，计算公式为

    $$ {\delta _i} = \delta \left( i \right) = \mathop {\min }\limits_{j:{\rho _j} > {\rho _i}} \left( {{d_{ij}}} \right) $$ (2)

    如果$i$为密度最大的样本点，那么${\delta _i}$可取距离$i$最远样本点$j$的距离${d_{ij}}$。

    利用上述2个量，可以构建横轴为$\rho $，纵轴为$\delta $的决策图。根据决策图，可将样本点分为密度峰值点、正常点和离群点，密度峰值点就是聚类中心。聚类中心数量可以由用户根据决策图选取，也可以选取$k$个$\rho \cdot \delta $(简记为$\gamma $)最大的点。当聚类中心确定后，再将其他点一次分配到最近的密度较高点所在的簇中。

    1.2   主动学习

    主动学习主要包括2个步骤：1）选择有价值的样本，将其交给专家进行标记，然后将专家标记样本与已标记样本集构成新的训练集；2）在新训练集上进行重新训练得到新模型，利用新模型对测试集进行重新测试，记录分类器的性能指标。上述2个过程不断迭代，直至分类器达到预设指标或是学习过程超出预设代价(一般用标记数量刻画)。

    定义数据集为$ \mathcal{D}\left( {\mathcal{D} = \left\{ {{\mathcal{D}_{{\rm{train}}}},{\mathcal{D}_{{\rm{test}}}}} \right\}} \right) $，训练集为$ {\mathcal{D}_{{\rm{train}}}} = \left\{ {{\mathcal{D}_l},{\mathcal{D}_u}} \right\} $，其中，$ {\mathcal{D}_l} $表示用于初始化分类器的已标记集，$ {\mathcal{D}_u} $表示主动学习起始时的无标记集(也称作未标记池)。选择有价值的样本可以看成是一个采样过程，不确定性采样和聚类边界点采样是实现该过程的2种思路，下面进行简要介绍。

    1.2.1   不确定性采样

    以多分类问题为例，不确定性采样常用信息熵[20]刻画未标记样本的不确定性，即基于熵的不确定性采样(Entropy)。在选择有价值样本标记前先使用已标记集训练一个初始分类器，随后分类器会对所有未标记样本进行预测，并选取后验概率熵值最大的样本进行标记。选取结束后更新已标记集和未标记池，再更新分类器并重复上述过程。基于熵的不确定性采样可描述为

    $$ {x_{{\text{sel}}\;}} = \mathop {{\rm{argmax}}}\limits_x - \sum\limits_i {{P_\theta }\left( {{y_i}|x} \right)} \log \left( {{P_\theta }\left( {{y_i}|x} \right)} \right) $$ (3)

    式中：${x_{{\rm{sel}}}}$表示选择标记的样本；$\theta $表示分类器的一组参数；${p_\theta }\left( {{y_i}|x} \right)$表示由参数$\theta $确定的分类器将样本$x$预测为类别${y_i}$的概率。

    1.2.2   聚类边界点采样

    聚类边界点是分布在每个聚类边缘区域的一组特殊对象，其标签由聚类结构给出，指导聚类划分。Xia等[21]给出了聚类边界点和聚类核心点的形式化描述。

    定义1　聚类边界点$b$

    1）其位于一个稠密区域$\mathcal{R}$内。

    2）存在一个$b$的近邻区域$ \mathcal{R}' $，其满足以下任意一个条件：

    $$\begin{aligned} {\rm{Density}}\left( {\mathcal{R}'} \right) \gg {\rm{Density}}\left( \mathcal{R} \right) \\ {\rm{Density}}\left( {\mathcal{R}'} \right) \ll {\rm{Density}}\left( \mathcal{R} \right) \end{aligned} $$

    定义2　聚类核心点$c$

    1）其位于一个稠密区域$\mathcal{R}$内。

    2）存在一个基于$\mathcal{R}$的拓展区域$\mathcal{R}''$，满足

    $${\rm{Density}}\left( {\mathcal{R}''} \right) - {\rm{Density}}\left( \mathcal{R} \right) \to 0。 $$

    对于一个聚类结构良好的数据集，其聚类边界点能够刻画出分类器的目标决策边界。对此，Cao[18]提出了一个几何观点，即分类器的性能是由聚类边界点决定的。

    定理1　设$\xi $和$\eta $分别表示聚类的核心点和边界点构成的集合，其并集$\Xi = \left\{ {\xi ,\eta } \right\}$；设$ {h^\Xi } $、${h^\eta }$分别表示$\Xi $和$\eta $对应的分类器解空间。则，对于泛化误差分歧$ \varDelta ' $，满足

    $$ \varDelta ' = {\rm{error}}\left( {{h^\Xi }} \right) - {\rm{error}}\left( {{h^\eta }} \right) \to 0 $$ (4)

    边界距离表示一个点到分类器超平面的距离。由于聚类核心点的边界距离较聚类边界点的距离更远，因此上述定义易证。

    聚类边界采样算法期望获取类簇的边界点，这些点真正决定了分类器的版本空间。在主动学习中，根据此特点可以选择出最有标记价值的样本。Cao[18]最早将聚类边界点采样运用到主动学习领域，提出了一种基于概率路径转移长度的聚类边界点采样算法GAL，该算法的灵感来源于图论中的Knight’s tour问题。在GAL算法中，需要计算样本点${x_i}$距离其$\varepsilon $个近邻点$M_i^j$的概率路径转移长度$ {\mathcal{M}_i} $

    $$ {\mathcal{M}_i} = \displaystyle\sum\limits_{j = 1}^\varepsilon {\frac{{\left\| {r_{1 \times 1}^{{x_i} \to M_i^j}} \right\|_2^2}}{{\displaystyle\sum\limits_{\nu = 1}^\varepsilon {{{\left\| {r_{1 \times 1}^{{x_i} \to M_i^\nu }} \right\|}_2}} }}} $$ (5)

    一般说来，聚类核心点转移到其$\varepsilon $个近邻的路径长度之和较大，即概率路径转移长度较大；而聚类边界点则相反。GAL算法通过计算各样本点的概率路径转移长度值，之后进行降序排列，依次选择前$t$的样本($t$一般大于30%)[22]作为聚类边界点。

    2.   结合聚类边界采样的主动学习

    首先介绍一种基于密度峰值的聚类边界点采样算法；在此基础上，提出一种主动学习算法。

    2.1   基于密度峰值的边界点采样算法

    本研究的采样方法基于密度峰值聚类的2个假设，满足这类假设的数据集具有核心区域比较稠密、边界区域比较稀疏的特点。假设数据集被密度峰值聚类算法划分成$k$个簇，且各个簇样本点的密度分布相似，那么可以根据决策图直接筛选若干最小密度$\rho $样本点作为边界点，这是一种基于全局的策略。GAL算法也采取了这种策略，但该方式未考虑数据局部结构。由于数据局部区域性质可能存在区别（例如某些簇的密度偏大，某些簇的密度偏小），单一的全局选择方式容易导致边界点的选取效果变得很不稳定。

    为了解决以上问题，本研究首先使用密度峰值对数据进行聚类。密度聚类之后，可以得到不同密度的聚类簇。再对聚类结果进行边界采样。

    定义3　边界离群点$o$

    如果$o$是边界样本集中的离群点，那么满足$o = \left\{ {\left| {Z\left( {{b^C}} \right)} \right| > {Z_{{\rm{th}}}},C \in \left\{ {1,2,\cdots,k} \right\}} \right\}$，其中，$Z\left( \cdot \right)$表示z分数，${b^C}$表示属于簇$C$的边界点，${Z_{{\rm{th}}}}$表示密度偏离阈值，用于刻画离群点的密度相对于所属簇的密度均值偏移了多少个标准差，一般大于2.5。

    算法1　基于密度峰值的边界点采样算法。

    输入　数据集$\mathcal{D}$，离群点的密度偏离阈值${Z_{{\rm{th}}}}$，簇数$k$，边界样本占总样本的比例$\lambda $。

    输出　聚类边界点的集合$S$

    1) 数据集$\mathcal{D}$进行密度峰值聚类，记录所有样本点的密度$\rho $以及簇标记label。

    2) $i \leftarrow 1$。

    3) $S \leftarrow \varnothing$。

    4) WHILE $i \leqslant k$。

    5)　 记录当前簇的样本点个数cnt。

    6)　 $ N \leftarrow \left\lfloor {{\rm{cnt}} \cdot \lambda } \right\rfloor $。

    7)　 $ {\rm{seq}} \leftarrow {\rm{top}}{_N}\left( {{\rm{sort}}{_\rho }\left( {{C_i}} \right)} \right) $。

    8)　 $S \leftarrow S \cup {\rm{seq}}$。

    9)　 根据定义3选取离群点 $o$。

    10)　 $S \leftarrow S \setminus o$。

    11)　 $i \leftarrow i + 1$。

    12) END WHILE。

    13) 输出$S$。

    算法1描述了聚类边界样本的采样过程。1) 表示密度峰值聚类过程，需要记录密度和样本的类簇标签；5) −6) 表示计算边界样本点的采样个数；7) −8) 表示按照$\rho $的大小对各簇的样本点进行降序排序，并取前$N$个加入到边界样本集中；9) −10) 表示去除边界样本的离群点。

    2.2   基于聚类边界点采样与密度熵的主动学习算法(BSDE)

    分类器的作用是将特征空间划分为多个类别的决策区域，这些区域的边界称为决策边界。这些边界点位于分离区域上，可以用封闭几何曲面近似拟合为类簇。与离群点不同，这些边界点具有明确的标记，并与类簇内部点相连[23]。因此，检测到聚类边界点可以使分类器版本空间最小化，更有利于模型预测。

    在GAL算法中，一旦获取到聚类边界点，便选取具有较大${\mathcal{M}_i}$的样本进行标记。该算法与分类器假设无关，性能较为稳定，但存在几个不足之处：1) GAL算法在数据规模较大时收敛较慢；2) 容易采集到离群点；3) 没有考虑数据集的局部结构信息，容易造成采样偏差。为提高算法收敛速度，降低离群点的采集率，本研究将信息熵与密度峰值聚类中的密度概念结合，提出一种新的采集函数——密度熵(density entropy-DE)，其公式如下

    $$ {\rm{DE}}\left( x \right) = {\rm{Entropy}}{\left( x \right)^{1 - \beta }} \cdot \rho {\left( x \right)^\beta } $$ (6)

    式中：${\rm{Entropy}}\left( x \right)$表示样本$x$的信息熵，用于度量不确定性；$\rho \left( x \right)$表示密度，采用式(1)进行计算，反映一个点邻域内的点的数量，可以刻画该点在局部区域中的代表性；$\beta $表示权衡参数，取值范围在0~1间，默认取0.1。密度熵也可以看作是信息熵的推广，特别的，当$ \beta $为0时，密度熵就退化为信息熵。

    这里给出一个示例对密度熵进行说明，如图1所示。由图1可知，圆形和三角形分别表示分类问题的2种类别；正方型框选的表示算法选出的边界样本；星型标注的表示初始标记样本；英文字母标注的表示主动学习选择标记的样本，按照标记次序依次记为${x_1}$，${x_2}$，${x_3}$；虚线表示分类器经初始样本集训练后的决策边界；实线表示分类器经新的训练集（包含新标记样本）训练后的决策边界。显然，图1(a)中的${x_1}$是一个离群点，不应该被优先选择。但是，根据信息熵的定义，其后验概率的信息熵较大，导致${x_1}$被优先选择。根据式(1)计算其密度为0，该点的密度熵也为0，${x_1}$将不会被优先标记。因此，在这种情况下，密度熵更符合数据的实际情况（如图1(b)所示，离群点没有被标记）。

    图  1  GAL和BSDE在合成数据集上的样本选择变化情况
    Fig.  1  Variations in sample selection for GAL and BSDE on synthetic datasets
    下载: 全尺寸图片

    为了避免局部区域采样率过高，造成采样偏差，首先，使用算法1对输入空间进行边界点采样；其次，使用密度熵对边界样本进行启发式搜索，找出信息量和代表性均较高的样本点。这里给出了一种基于聚类边界点采样与密度熵的主动学习(BSDE)算法。

    算法2　基于聚类边界点采样与密度熵的主动学习算法(BSDE算法)。

    输入　数据集$\mathcal{D}$，边界离群点的密度偏离阈值${Z_{{\rm{th}}}}$，簇数$k$，边界样本占总样本的比例$\lambda $，权衡参数$\beta $，分类器$ \theta $，初始标记样本数$p$，分类器的初始已标记样本集${D_l}$，查询样本占未标记池的比例$q$，每轮的查询量batch_size

    输出　训练后的分类器$\theta $

    1) 使用算法1获取$\mathcal{D}$的聚类边界样本集$S$。

    2) ${\rm{count}} \leftarrow 0$。

    3) ${N_q} \leftarrow \left( {\left| \mathcal{D} \right| - p} \right) \cdot q$。

    4) WHILE ${\rm{count}} < {N_q}$。

    5)　 ${\rm{DE}}\left( S \right) = \left\{ {{\rm{DE}}\left( x \right),x \in S} \right\}$。

    6)　 ${\rm{selected}} \leftarrow {\rm{top}}{_{{\rm{batch\_size}}}}\left( {{\rm{sort}}{_{{\rm{DE}}}}\left( S \right)} \right)$。

    7)　 ${\rm{selected}} \leftarrow {\rm{query}}\_{\rm{label}}\left( {{\rm{selected}}} \right)$。

    8)　 ${D_l} \leftarrow {D_l} \cup {\rm{selected}}$。

    9)　 $\theta \leftarrow{\rm{ retrain}}\left( \theta \right)$。

    10)　 $S \leftarrow S \setminus {\rm{selected}}$。

    11)　 ${\rm{count}} \leftarrow {\rm{count}} + \left| {{\rm{selected}}} \right|$。

    12) END WHILE。

    13) 输出$\theta $。

    算法2描述了基于聚类边界点采样与密度熵的主动学习过程。1) 表示获取边界样本；2) −3) 表示获取当前标记量以及标记上限；5) −6) 表示计算边界样本的密度熵并选择最大的若干样本准备标记；7) 表示专家查询样本的标签；9) 表示分类器重训练。

    算法的时间复杂度分析：设样本点个数为$n$，每个簇的样本量都是${n^C}$（$k$和${n^C}$分别表示簇数和各个簇的样本量，${n^C}$的值与簇号$C$有关）。1）表示基于密度峰值的边界采样过程，其时间复杂度是$O\left( {k \cdot {n^C} \cdot \log \left( {{n^C}} \right)} \right) + O\left( {{n^2}} \right)$。2）−12） 表示使用密度熵启发式搜索边界区域的过程，为分析方便，可以将聚类边界采样点的规模也视作$n$，这样问题就转为从$n$个样本中选取${N_q}$个密度熵最大的样本，时间复杂度为$O\left( {n\log \left( {{N_q}} \right)} \right)$。故算法时间复杂度为$O\left( {n \cdot \log \left( {{N_q}} \right)} \right) + O\left( {{n^2}} \right) + O\left( {k \cdot {n^C} \cdot \log \left( {{n^C}} \right)} \right)$，由于${N_q}$小于$n$，$ O\left( {n \cdot \log \left( {{N_q}} \right)} \right) + O\left( {{n^2}} \right) = O\left( {{n^2}} \right) $。因此，算法2的时间复杂度为$O\left( {k \cdot {n^C} \cdot \log \left( {{n^C}} \right)} \right) + O\left( {{n^2}} \right)$。

    3.   试验结果与分析

    为了验证文中算法在边界采样和主动学习方面的有效性，下面将分别进行试验。在3.1中将在flame数据集上检验文中方法的有效性；在3.2中将在Accuracy、F-score、ALC-Acc等指标上与5种先进的主动学习算法进行对比。

    3.1   基于密度峰值的聚类边界点采样的有效性

    图2给出了二分类数据集 flame 上，基于密度峰值的聚类采样算法在设置$ k=2，1，3，4 $时的边界采样效果，图2中密度峰值点和聚类核心点被聚类边界点所包络。可以看到，$k = 2$是最佳的聚类数，此时边界采样区域能够完全覆盖可行的假设空间。此外，当$k$偏离了真实最佳聚类数2(即$k \in \{ 1,3,4\} $)时，算法的整体采样效果也较为稳定。

    图  2  边界采样算法在flame数据集上的结果
    Fig.  2  Results of boundary sampling algorithm on the flame dataset
    下载: 全尺寸图片

    3.2   BSDE与几种先进主动学习算法的对比

    3.2.1   对比算法与数据集

    这里对比了5种流行的主动学习算法，分别如下。

    1）LAL[24]：LAL是一种期望错误最小化的方法，其特点在于其将训练一个回归模型用于预测特定学习状态下候选样本的预期错误减少，但只适用于二分类问题。在试验中，使用笔者提供的预提取数据训练回归器。

    2）Entropy[20]：Entropy是一种基于不确定性采样的经典方法，使用信息熵度量样本的不确定性，见式（3）。

    3）TACS[11]：TACS是基于聚类选择的主动学习算法。其将原始数据不断二分为块，并结合三支决策理论对不同状态的块进行分别处理，在块中查询标签时，选择具有密度峰值的代表性实例或总距离最大的信息实例。

    4）QUIRE[14]：QUIRE基于主动学习的min-max框架，实例的信息性通过已标记数据的预测不确定性刻画，而其代表性通过未标记数据的预测不确定性衡量。

    5）GAL[18]：GAL是基于聚类边界点采样的主动学习算法，其计算每个样本点距离$k$个近邻的概率转移长度，通过排序筛选出聚类边界点作为待标记样本。

    在12个数据集上进行了对比试验，由于LAL只能用于二分类，因此选择了5个二分类数据集，其余为多分类数据集。其具体信息详见表1。

    表  1  试验数据集
    Table  1  Experiment datasets
    数据集ID数据集名称样本数特征数类别数
    1spectfheart270132
    2flame24022
    3bupa34562
    4sonar208602
    5heart270132
    6wine178133
    7seeds21073
    8spiral32123
    9movement_libras3609015
    10yeast1484810
    11winequality-red1599116
    12thyroid7200213
    3.2.2   试验设置

    具体试验设置如下：1）许多数据集默认有序，为满足数据的独立同分布假设，对各数据集预先进行随机无放回采样（采样数等于样本总数）；2）数据集采用了标准化；3）为保证对比试验稳定性，采用随机分层10折交叉验证，统计指标的均值和标准差。此外，由于对比算法需要初始标记样本引导训练过程，因此在训练集中，从各类别中随机选择1个样本构成初始标记集；4）使用逻辑回归作为基分类器；5）使用测试集的Accuracy、F-score指标衡量不同迭代轮次下分类器的性能。为评估整个主动学习过程的性能[25]，还计算了学习曲线下区域(ALC)这一性能指标。对于Accuracy和F1-Weighed曲线，分别可以得到ALC-ACC和ALC-F1-Weighed；6）对于LAL，笔者提供了2个版本，使用其在论文中推荐的表现更好的LAL-iterative-2D；7）对于TACS，使用了笔者提供的Java源码。为满足输入要求，在保证样本内容不变的前提下将数据集由csv格式转为arff格式；8）对于QUIRE，使用了作者提供的源码，核函数采用文中建议的RBF核。在试验中发现QUIRE在规模较大的数据集上运行缓慢，由于试验条件限制，最终只在9个较小规模的数据集上对比了QUIRE；9）对于BSDE，设置参数$p = 1$，$q = 0.2$、$\lambda = 0.35$、${Z_{{\rm{th}}}} = 2.5$、$\beta \in [0,1]$(通常取0.1)；10）在真实环境下，对于带有聚类的主动学习，聚类过程可以在整个数据集上进行，但为保证试验的公平性，避免泄露测试集信息，把无标记样本池作为带有聚类过程算法(TACS、BSDE)的输入数据；11）标记预算为未标记池样本总量的20%，每次迭代的查询量(batch size)为1，即每轮查询一个样本。

    3.2.3   试验结果和分析

    6种主动学习方法的对比试验结果如图3、表2、表3所示。容易发现：本研究提出的BSDE算法在多数的数据集上取得领先(如spectheart、sonar、yeast)，在12个数据集上的ALC-ACC与ALC-F1-Weighted值的平均排名取得第一，在6种主动学习算法中取得了最好的表现。

    图  3  12个数据集上Accuracy和F1-score的变化曲线
    Fig.  3  Accuracy and F1-score variation curves on 12 datasets
    下载: 全尺寸图片
    表  2  主动学习算法在不同标注比例下的F1-Weighted
    Table  2  F1-Weighted of active learning algorithms at different labeling ratios
    数据集ID数据集名称标注比例
    1%3%5%7%10%13%15%20%
    1LAL0.536±0.1020.597±0.0680.637±0.0590.681±0.0670.704±0.0650.739±0.0490.725±0.0660.716±0.060
    Entropy0.525±0.0770.604±0.0730.614±0.0810.636±0.1060.660±0.0720.690±0.0710.686±0.0600.711±0.077
    TACS0.554±0.1000.599±0.0830.603±0.0980.593±0.1010.564±0.1030.582±0.1080.554±0.0790.600±0.109
    GAL0.552±0.1280.555±0.1070.570±0.1130.570±0.0960.569±0.0910.603±0.0980.616±0.0890.657±0.089
    QUIRE0.570±0.1020.632±0.1050.660±0.1060.632±0.0880.632±0.0880.641±0.0750.704±0.0710.704±0.088
    BSDE0.622±0.0690.601±0.1060.631±0.0970.664±0.0930.718±0.1020.720±0.1050.727±0.0840.744±0.055
    2LAL0.724±0.1480.818±0.0910.844±0.0720.870±0.0760.885±0.0610.873±0.0690.861±0.0700.878±0.070
    Entropy0.724±0.1480.809±0.1010.841±0.0960.850±0.0980.854±0.0750.866±0.0720.866±0.0800.867±0.067
    TACS0.724±0.1480.813±0.1060.831±0.0830.855±0.0920.860±0.0760.860±0.0800.848±0.0830.852±0.081
    GAL0.724±0.1480.847±0.0850.851±0.0700.848±0.0670.852±0.0680.873±0.0600.877±0.0550.892±0.049
    QUIRE0.724±0.1480.782±0.0930.812±0.1140.858±0.0780.878±0.0760.870±0.0730.854±0.0870.828±0.058
    BSDE0.724±0.1480.827±0.0830.849±0.0630.856±0.0820.890±0.0720.870±0.0720.868±0.0730.882±0.076
    3LAL0.521±0.1100.554±0.1210.556±0.1080.536±0.0990.581±0.0970.595±0.0780.583±0.0880.585±0.054
    Entropy0.517±0.0710.510±0.0540.521±0.0630.529±0.0900.574±0.0710.601±0.0840.617±0.0730.615±0.103
    TACS0.470±0.0850.575±0.0930.572±0.0730.570±0.0630.597±0.0610.600±0.0720.624±0.0750.635±0.061
    GAL0.496±0.1000.553±0.1150.546±0.1090.511±0.0870.552±0.0940.617±0.1140.621±0.0990.607±0.092
    QUIRE0.510±0.1010.561±0.0850.527±0.0840.542±0.0750.558±0.0770.577±0.0750.554±0.0970.579±0.087
    BSDE0.545±0.0900.561±0.0520.545±0.0630.592±0.0690.603±0.0680.632±0.0600.617±0.0840.646±0.086
    4LAL0.552±0.0810.656±0.1390.598±0.1130.622±0.0940.628±0.1200.708±0.1480.719±0.1280.702±0.085
    Entropy0.552±0.0810.634±0.1820.607±0.1250.662±0.1530.747±0.1090.743±0.0960.739±0.0900.722±0.131
    TACS0.552±0.0810.677±0.1380.676±0.1270.673±0.1240.680±0.1220.728±0.0870.740±0.0810.749±0.059
    GAL0.552±0.0810.605±0.1430.643±0.1440.614±0.1440.666±0.1730.683±0.1340.692±0.1160.730±0.141
    QUIRE0.552±0.0810.618±0.1360.667±0.1650.682±0.1320.684±0.1140.669±0.1180.640±0.1240.691±0.152
    BSDE0.552±0.0810.654±0.1290.687±0.1290.696±0.1150.732±0.1040.742±0.1010.730±0.1110.777±0.108
    续表 2
    数据集ID数据集名称标注比例
    1%3%5%7%10%13%15%20%
    5LAL0.733±0.0880.721±0.1350.746±0.1470.766±0.1130.747±0.0740.774±0.0850.806±0.0520.821±0.042
    Entropy0.753±0.0610.722±0.0760.727±0.0800.765±0.0720.791±0.0560.801±0.0480.820±0.0390.828±0.036
    TACS0.736±0.0680.718±0.0770.773±0.0510.751±0.0620.767±0.0950.772±0.0800.773±0.0540.806±0.076
    GAL0.743±0.0740.741±0.0780.803±0.0790.822±0.0550.837±0.0580.830±0.0780.822±0.0650.822±0.074
    QUIRE0.743±0.0540.755±0.0760.772±0.0660.799±0.0670.770±0.0680.781±0.0870.818±0.0560.825±0.097
    BSDE0.758±0.0840.762±0.1500.798±0.0600.824±0.0560.831±0.0410.825±0.0580.848±0.0590.840±0.047
    6Entropy0.885±0.0620.914±0.1070.930±0.0730.925±0.0550.961±0.0530.977±0.0410.977±0.0420.988±0.025
    TACS0.885±0.0620.829±0.1040.877±0.0900.878±0.0840.895±0.0760.920±0.0640.926±0.0680.954±0.063
    GAL0.885±0.0620.868±0.0820.875±0.0650.879±0.0760.895±0.1120.878±0.0890.889±0.0890.960±0.056
    QUIRE0.885±0.0620.908±0.1080.913±0.0910.902±0.0870.926±0.0390.914±0.0310.925±0.0400.960±0.039
    BSDE0.885±0.0620.930±0.0680.919±0.0580.936±0.0650.971±0.0410.983±0.0280.988±0.0240.994±0.018
    7Entropy0.770±0.1760.804±0.1120.872±0.0560.899±0.0580.924±0.0330.928±0.0410.928±0.0410.933±0.034
    TACS0.770±0.1760.737±0.1740.710±0.1810.701±0.1300.783±0.1320.864±0.0900.885±0.0580.918±0.065
    GAL0.770±0.1760.862±0.0590.822±0.1120.855±0.0860.908±0.0620.917±0.0470.913±0.0510.923±0.053
    QUIRE0.770±0.1760.771±0.1740.807±0.1710.853±0.1330.866±0.0640.880±0.0730.894±0.0590.888±0.052
    BSDE0.770±0.1760.855±0.0840.883±0.0560.913±0.0600.922±0.0540.918±0.0400.933±0.0400.928±0.051
    8Entropy0.309±0.0810.274±0.0650.254±0.0560.290±0.0820.325±0.1060.265±0.0900.247±0.0960.295±0.113
    TACS0.278±0.1110.356±0.1210.314±0.0860.310±0.0970.296±0.1190.320±0.1000.343±0.0910.339±0.100
    GAL0.290±0.1050.358±0.0670.352±0.0940.333±0.0810.324±0.0770.321±0.0830.312±0.0830.301±0.089
    QUIRE0.284±0.0850.305±0.0780.290±0.0640.309±0.0760.301±0.0740.299±0.0680.307±0.0840.312±0.084
    BSDE0.291±0.0990.243±0.0880.293±0.1110.292±0.1090.318±0.0840.339±0.0780.354±0.0850.371±0.082
    9Entropy0.360±0.0990.396±0.0840.373±0.0880.402±0.0930.423±0.1250.426±0.0870.430±0.0710.456±0.060
    TACS0.351±0.0970.380±0.0880.393±0.0650.421±0.0930.433±0.1030.469±0.1010.478±0.0940.460±0.090
    GAL0.370±0.1100.376±0.0760.393±0.0980.397±0.0890.434±0.0850.413±0.1120.424±0.0960.431±0.094
    QUIRE0.341±0.1010.389±0.0840.407±0.0740.399±0.0750.408±0.0930.413±0.0880.427±0.0950.439±0.087
    BSDE0.358±0.1020.372±0.0870.398±0.0970.426±0.1060.452±0.0830.469±0.0730.485±0.0620.496±0.096
    10Entropy0.441±0.0620.476±0.0540.484±0.0350.492±0.0290.518±0.0410.522±0.0440.532±0.0510.551±0.056
    TACS0.419±0.0640.427±0.0720.470±0.0430.497±0.0300.520±0.0330.515±0.0220.498±0.0360.527±0.033
    GAL0.350±0.0550.486±0.0540.479±0.0450.483±0.0530.533±0.0410.544±0.0370.538±0.0470.543±0.054
    BSDE0.431±0.0990.490±0.0470.499±0.0600.528±0.0590.539±0.0670.544±0.0560.556±0.0370.545±0.045
    11Entropy0.402±0.0620.445±0.0570.464±0.0460.482±0.0470.495±0.0560.497±0.0460.493±0.0410.506±0.034
    TACS0.393±0.0730.471±0.0530.506±0.0310.515±0.0290.528±0.0450.520±0.0440.533±0.0330.518±0.020
    GAL0.359±0.0800.465±0.0520.481±0.0380.495±0.0370.496±0.0330.499±0.0310.519±0.0440.516±0.037
    BSDE0.433±0.0520.482±0.0460.501±0.0390.505±0.0320.513±0.0360.513±0.0330.513±0.0420.515±0.033
    12Entropy0.866±0.0840.780±0.1090.760±0.0900.851±0.0600.937±0.0220.955±0.0090.956±0.0060.951±0.007
    TACS0.873±0.0120.908±0.0060.911±0.0040.913±0.0040.914±0.0040.917±0.0050.918±0.0060.919±0.007
    GAL0.823±0.0600.916±0.0070.916±0.0040.918±0.0020.918±0.0030.919±0.0020.918±0.0030.921±0.004
    BSDE0.866±0.0330.871±0.0160.934±0.0090.943±0.0090.940±0.0070.931±0.0060.930±0.0060.927±0.005
    注：黑体表示最好结果，下同。
    表  3  主动学习算法的ALC-F1-Weighted
    Table  3  ALC-F1-Weighted of active learning algorithms
    数据集IDLALEntropyTACSGALQUIREBSDE
    129.011±1.46727.939±2.49924.821±2.88925.305±3.93928.119±2.7829.392±2.705
    233.315±2.22533.105±2.51632.871±2.78233.363±2.02332.667±2.43233.548±2.287
    331.656±3.01131.388±3.10232.482±2.90731.443±4.63830.864±3.60533.321±2.898
    421.712±3.12822.95±3.02522.953±2.36521.929±3.75821.743±3.38823.539±3.156
    533.053±2.97333.719±1.53332.873±2.04134.644±1.92133.789±2.60135.037±1.976
    6—26.653±0.94925.164±1.6925.222±1.78225.773±1.23926.843±0.795
    7—30.413±1.33827.478±2.7829.955±1.19829.016±2.44930.708±1.639
    8—14.408±2.60616.489±3.74516.041±3.25815.06±3.26515.943±3.565
    9—20.722±3.78321.637±4.08620.587±4.04520.447±3.23121.881±3.752
    10—116.602±7.14112.643±7.37116.409±9.55—120.335±9.949
    11—102.347±8.972109.021±5.667104.985±6.097—108.586±6.006
    12—1017.49±28.6831037.681±5.1341035.1±6.399—1050.47±5.864
    平均值29.749123.145124.676124.58226.386127.467
    平均排名3.8 3.5 3.417 3.25 4.333 1.25

    分析其原因，可以发现：1) TACS在分块过程中进行标注，如果分块过程出现问题，容易导致整个块产生错误标记，如seeds数据集；2) Entropy容易陷入空间中难以学习的局部区域，造成分类器性能的意外下降[26]，如thyroid数据集，在迭代前期分类器的性能产生骤降，导致整体的学习曲线不佳；3) QUIRE在大部分数据集上的排名不高，主要由于数据集局部区域的样本性质存在差异，违背算法的基本假设；4) LAL从简单的二维合成数据集训练随机森林回归器，并预测预期误差减少，每轮主动学习迭代开始前，LAL都需要重新训练回归器，时间效率较低，且由于该算法只能用于二分类，进一步限制了其应用范围；5) GAL在缩减到稳定的版本空间前需要查询足够的聚类边界样本点，导致分类器收敛速度较慢。从图3中可以看到，GAL在大部分数据集上的学习曲线都较为平缓(如spectheart和winequality-red)。

    4.   结束语

    许多基于池的主动学习方法根据当前分类假设和标记样本挑选样本标记，在标记样本量较少的情况下，学习曲线未能显著提升。受到分类器性能由聚类边界点决定这一观点的启发，本研究首先提出一种基于密度峰值的聚类边界点采样方法；在此基础之上，为解决聚类边界采样主动学习收敛缓慢的问题，定义了一种名为密度熵的采集函数，其具有不确定性采样适用性强、收敛快的特点，同时避免了其容易陷入局部区域查询的问题；最后，提出了一种新的主动学习算法——BSDE。试验结果表明，本研究算法能够有效发掘聚类边界点、启发式搜索有价值的样本进行标记，能在少量标记条件下有效提高分类器性能，在对比试验中取得了较好结果。但是，本研究提出的算法使用了经典的密度峰值算法版本，存在时间复杂度较高、高维性能退化的问题，这些因素可能会限制BSDE的性能。可以考虑采用更适用的距离定义，如MMD或Wasserstein距离，或者基于度量学习的方法来获得更准确的样本空间表征，这是未来的主要工作。

  • 图  1   GAL和BSDE在合成数据集上的样本选择变化情况

    Fig.  1   Variations in sample selection for GAL and BSDE on synthetic datasets

    下载: 全尺寸图片

    图  2   边界采样算法在flame数据集上的结果

    Fig.  2   Results of boundary sampling algorithm on the flame dataset

    下载: 全尺寸图片

    图  3   12个数据集上Accuracy和F1-score的变化曲线

    Fig.  3   Accuracy and F1-score variation curves on 12 datasets

    下载: 全尺寸图片

    表  1   试验数据集

    Table  1   Experiment datasets

    数据集ID数据集名称样本数特征数类别数
    1spectfheart270132
    2flame24022
    3bupa34562
    4sonar208602
    5heart270132
    6wine178133
    7seeds21073
    8spiral32123
    9movement_libras3609015
    10yeast1484810
    11winequality-red1599116
    12thyroid7200213

    表  2   主动学习算法在不同标注比例下的F1-Weighted

    Table  2   F1-Weighted of active learning algorithms at different labeling ratios

    数据集ID数据集名称标注比例
    1%3%5%7%10%13%15%20%
    1LAL0.536±0.1020.597±0.0680.637±0.0590.681±0.0670.704±0.0650.739±0.0490.725±0.0660.716±0.060
    Entropy0.525±0.0770.604±0.0730.614±0.0810.636±0.1060.660±0.0720.690±0.0710.686±0.0600.711±0.077
    TACS0.554±0.1000.599±0.0830.603±0.0980.593±0.1010.564±0.1030.582±0.1080.554±0.0790.600±0.109
    GAL0.552±0.1280.555±0.1070.570±0.1130.570±0.0960.569±0.0910.603±0.0980.616±0.0890.657±0.089
    QUIRE0.570±0.1020.632±0.1050.660±0.1060.632±0.0880.632±0.0880.641±0.0750.704±0.0710.704±0.088
    BSDE0.622±0.0690.601±0.1060.631±0.0970.664±0.0930.718±0.1020.720±0.1050.727±0.0840.744±0.055
    2LAL0.724±0.1480.818±0.0910.844±0.0720.870±0.0760.885±0.0610.873±0.0690.861±0.0700.878±0.070
    Entropy0.724±0.1480.809±0.1010.841±0.0960.850±0.0980.854±0.0750.866±0.0720.866±0.0800.867±0.067
    TACS0.724±0.1480.813±0.1060.831±0.0830.855±0.0920.860±0.0760.860±0.0800.848±0.0830.852±0.081
    GAL0.724±0.1480.847±0.0850.851±0.0700.848±0.0670.852±0.0680.873±0.0600.877±0.0550.892±0.049
    QUIRE0.724±0.1480.782±0.0930.812±0.1140.858±0.0780.878±0.0760.870±0.0730.854±0.0870.828±0.058
    BSDE0.724±0.1480.827±0.0830.849±0.0630.856±0.0820.890±0.0720.870±0.0720.868±0.0730.882±0.076
    3LAL0.521±0.1100.554±0.1210.556±0.1080.536±0.0990.581±0.0970.595±0.0780.583±0.0880.585±0.054
    Entropy0.517±0.0710.510±0.0540.521±0.0630.529±0.0900.574±0.0710.601±0.0840.617±0.0730.615±0.103
    TACS0.470±0.0850.575±0.0930.572±0.0730.570±0.0630.597±0.0610.600±0.0720.624±0.0750.635±0.061
    GAL0.496±0.1000.553±0.1150.546±0.1090.511±0.0870.552±0.0940.617±0.1140.621±0.0990.607±0.092
    QUIRE0.510±0.1010.561±0.0850.527±0.0840.542±0.0750.558±0.0770.577±0.0750.554±0.0970.579±0.087
    BSDE0.545±0.0900.561±0.0520.545±0.0630.592±0.0690.603±0.0680.632±0.0600.617±0.0840.646±0.086
    4LAL0.552±0.0810.656±0.1390.598±0.1130.622±0.0940.628±0.1200.708±0.1480.719±0.1280.702±0.085
    Entropy0.552±0.0810.634±0.1820.607±0.1250.662±0.1530.747±0.1090.743±0.0960.739±0.0900.722±0.131
    TACS0.552±0.0810.677±0.1380.676±0.1270.673±0.1240.680±0.1220.728±0.0870.740±0.0810.749±0.059
    GAL0.552±0.0810.605±0.1430.643±0.1440.614±0.1440.666±0.1730.683±0.1340.692±0.1160.730±0.141
    QUIRE0.552±0.0810.618±0.1360.667±0.1650.682±0.1320.684±0.1140.669±0.1180.640±0.1240.691±0.152
    BSDE0.552±0.0810.654±0.1290.687±0.1290.696±0.1150.732±0.1040.742±0.1010.730±0.1110.777±0.108
    续表 2
    数据集ID数据集名称标注比例
    1%3%5%7%10%13%15%20%
    5LAL0.733±0.0880.721±0.1350.746±0.1470.766±0.1130.747±0.0740.774±0.0850.806±0.0520.821±0.042
    Entropy0.753±0.0610.722±0.0760.727±0.0800.765±0.0720.791±0.0560.801±0.0480.820±0.0390.828±0.036
    TACS0.736±0.0680.718±0.0770.773±0.0510.751±0.0620.767±0.0950.772±0.0800.773±0.0540.806±0.076
    GAL0.743±0.0740.741±0.0780.803±0.0790.822±0.0550.837±0.0580.830±0.0780.822±0.0650.822±0.074
    QUIRE0.743±0.0540.755±0.0760.772±0.0660.799±0.0670.770±0.0680.781±0.0870.818±0.0560.825±0.097
    BSDE0.758±0.0840.762±0.1500.798±0.0600.824±0.0560.831±0.0410.825±0.0580.848±0.0590.840±0.047
    6Entropy0.885±0.0620.914±0.1070.930±0.0730.925±0.0550.961±0.0530.977±0.0410.977±0.0420.988±0.025
    TACS0.885±0.0620.829±0.1040.877±0.0900.878±0.0840.895±0.0760.920±0.0640.926±0.0680.954±0.063
    GAL0.885±0.0620.868±0.0820.875±0.0650.879±0.0760.895±0.1120.878±0.0890.889±0.0890.960±0.056
    QUIRE0.885±0.0620.908±0.1080.913±0.0910.902±0.0870.926±0.0390.914±0.0310.925±0.0400.960±0.039
    BSDE0.885±0.0620.930±0.0680.919±0.0580.936±0.0650.971±0.0410.983±0.0280.988±0.0240.994±0.018
    7Entropy0.770±0.1760.804±0.1120.872±0.0560.899±0.0580.924±0.0330.928±0.0410.928±0.0410.933±0.034
    TACS0.770±0.1760.737±0.1740.710±0.1810.701±0.1300.783±0.1320.864±0.0900.885±0.0580.918±0.065
    GAL0.770±0.1760.862±0.0590.822±0.1120.855±0.0860.908±0.0620.917±0.0470.913±0.0510.923±0.053
    QUIRE0.770±0.1760.771±0.1740.807±0.1710.853±0.1330.866±0.0640.880±0.0730.894±0.0590.888±0.052
    BSDE0.770±0.1760.855±0.0840.883±0.0560.913±0.0600.922±0.0540.918±0.0400.933±0.0400.928±0.051
    8Entropy0.309±0.0810.274±0.0650.254±0.0560.290±0.0820.325±0.1060.265±0.0900.247±0.0960.295±0.113
    TACS0.278±0.1110.356±0.1210.314±0.0860.310±0.0970.296±0.1190.320±0.1000.343±0.0910.339±0.100
    GAL0.290±0.1050.358±0.0670.352±0.0940.333±0.0810.324±0.0770.321±0.0830.312±0.0830.301±0.089
    QUIRE0.284±0.0850.305±0.0780.290±0.0640.309±0.0760.301±0.0740.299±0.0680.307±0.0840.312±0.084
    BSDE0.291±0.0990.243±0.0880.293±0.1110.292±0.1090.318±0.0840.339±0.0780.354±0.0850.371±0.082
    9Entropy0.360±0.0990.396±0.0840.373±0.0880.402±0.0930.423±0.1250.426±0.0870.430±0.0710.456±0.060
    TACS0.351±0.0970.380±0.0880.393±0.0650.421±0.0930.433±0.1030.469±0.1010.478±0.0940.460±0.090
    GAL0.370±0.1100.376±0.0760.393±0.0980.397±0.0890.434±0.0850.413±0.1120.424±0.0960.431±0.094
    QUIRE0.341±0.1010.389±0.0840.407±0.0740.399±0.0750.408±0.0930.413±0.0880.427±0.0950.439±0.087
    BSDE0.358±0.1020.372±0.0870.398±0.0970.426±0.1060.452±0.0830.469±0.0730.485±0.0620.496±0.096
    10Entropy0.441±0.0620.476±0.0540.484±0.0350.492±0.0290.518±0.0410.522±0.0440.532±0.0510.551±0.056
    TACS0.419±0.0640.427±0.0720.470±0.0430.497±0.0300.520±0.0330.515±0.0220.498±0.0360.527±0.033
    GAL0.350±0.0550.486±0.0540.479±0.0450.483±0.0530.533±0.0410.544±0.0370.538±0.0470.543±0.054
    BSDE0.431±0.0990.490±0.0470.499±0.0600.528±0.0590.539±0.0670.544±0.0560.556±0.0370.545±0.045
    11Entropy0.402±0.0620.445±0.0570.464±0.0460.482±0.0470.495±0.0560.497±0.0460.493±0.0410.506±0.034
    TACS0.393±0.0730.471±0.0530.506±0.0310.515±0.0290.528±0.0450.520±0.0440.533±0.0330.518±0.020
    GAL0.359±0.0800.465±0.0520.481±0.0380.495±0.0370.496±0.0330.499±0.0310.519±0.0440.516±0.037
    BSDE0.433±0.0520.482±0.0460.501±0.0390.505±0.0320.513±0.0360.513±0.0330.513±0.0420.515±0.033
    12Entropy0.866±0.0840.780±0.1090.760±0.0900.851±0.0600.937±0.0220.955±0.0090.956±0.0060.951±0.007
    TACS0.873±0.0120.908±0.0060.911±0.0040.913±0.0040.914±0.0040.917±0.0050.918±0.0060.919±0.007
    GAL0.823±0.0600.916±0.0070.916±0.0040.918±0.0020.918±0.0030.919±0.0020.918±0.0030.921±0.004
    BSDE0.866±0.0330.871±0.0160.934±0.0090.943±0.0090.940±0.0070.931±0.0060.930±0.0060.927±0.005
    注：黑体表示最好结果，下同。

    表  3   主动学习算法的ALC-F1-Weighted

    Table  3   ALC-F1-Weighted of active learning algorithms

    数据集IDLALEntropyTACSGALQUIREBSDE
    129.011±1.46727.939±2.49924.821±2.88925.305±3.93928.119±2.7829.392±2.705
    233.315±2.22533.105±2.51632.871±2.78233.363±2.02332.667±2.43233.548±2.287
    331.656±3.01131.388±3.10232.482±2.90731.443±4.63830.864±3.60533.321±2.898
    421.712±3.12822.95±3.02522.953±2.36521.929±3.75821.743±3.38823.539±3.156
    533.053±2.97333.719±1.53332.873±2.04134.644±1.92133.789±2.60135.037±1.976
    6—26.653±0.94925.164±1.6925.222±1.78225.773±1.23926.843±0.795
    7—30.413±1.33827.478±2.7829.955±1.19829.016±2.44930.708±1.639
    8—14.408±2.60616.489±3.74516.041±3.25815.06±3.26515.943±3.565
    9—20.722±3.78321.637±4.08620.587±4.04520.447±3.23121.881±3.752
    10—116.602±7.14112.643±7.37116.409±9.55—120.335±9.949
    11—102.347±8.972109.021±5.667104.985±6.097—108.586±6.006
    12—1017.49±28.6831037.681±5.1341035.1±6.399—1050.47±5.864
    平均值29.749123.145124.676124.58226.386127.467
    平均排名3.8 3.5 3.417 3.25 4.333 1.25
    • 参考文献(26)
  • [1] SHAHRAKI A, ABBASI M, TAHERKORDI A, et al. Active learning for network traffic classification: a technical study[J]. IEEE transactions on cognitive communications and networking, 2021, 8(1): 422–439.
    [2] NATH V, YANG Dong, LANDMAN B A, et al. Diminishing uncertainty within the training pool: active learning for medical image segmentation[J]. IEEE transactions on medical imaging, 2021, 40(10): 2534–2547. doi: 10.1109/TMI.2020.3048055
    [3] 陈立伟, 房赫, 朱海峰. 多视图主动学习的多样性样本选择方法研究[J]. 智能系统学报, 2021, 16(6): 1007–1014. doi: 10.11992/tis.202007037

    CHEN Liwei, FANG He, ZHU Haifeng. Diversity sample selection method of multiview active learning classification[J]. CAAI transactions on intelligent systems, 2021, 16(6): 1007–1014. doi: 10.11992/tis.202007037
    [4] CARCILLO F, LE BORGNE Y A, CAELEN O, et al. Streaming active learning strategies for real-life credit card fraud detection: assessment and visualization[J]. International journal of data science and analytics, 2018, 5(4): 285–300. doi: 10.1007/s41060-018-0116-z
    [5] OWOYELE O, PAL P, VIDAL TORREIRA A. An automated machine learning-genetic algorithm framework with active learning for design optimization[J]. Journal of energy resources technology, 2021, 143(8): 082305. doi: 10.1115/1.4050489
    [6] AGGARWAL C C, KONG X, GU Q, et al. Active learning: A survey [M]. [S. l. ]: Algorithms and Applications, 2014: 571−605.
    [7] LEWIS D D, GALE W A. A sequential algorithm for training text classifiers[C]//Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.[S.l.]: SIGIR 1994, 29: 3−12.
    [8] KEE S, DEL CASTILLO E, RUNGER G. Query-by-committee improvement with diversity and density in batch active learning[J]. Information sciences, 2018, 454/455: 401–418. doi: 10.1016/j.ins.2018.05.014
    [9] SHAO Hao. Query by diverse committee in transfer active learning[J]. Frontiers of computer science, 2019, 13(2): 280–291. doi: 10.1007/s11704-017-6117-6
    [10] SETTLES B, CRAVEN M. An analysis of active learning strategies for sequence labeling tasks[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing. New York: ACM, 2008: 1070−1079.
    [11] MIN Fan, ZHANG Shiming, CIUCCI D, et al. Three-way active learning through clustering selection[J]. International journal of machine learning and cybernetics, 2020, 11(5): 1033–1046. doi: 10.1007/s13042-020-01099-2
    [12] YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences, 2010, 180(3): 341–353. doi: 10.1016/j.ins.2009.09.021
    [13] HOI S C H, JIN Rong, ZHU Jianke, et al. Semi-supervised SVM batch mode active learning for image retrieval[C]//2008 IEEE Conference on Computer Vision and Pattern Recognition. Anchorage: IEEE, 2008: 1−7.
    [14] HUANG Shengjun, JIN Rong, ZHOU Zhihua. Active learning by querying informative and representative examples[J]. IEEE transactions on pattern analysis and machine intelligence, 2014, 36(10): 1936–1949. doi: 10.1109/TPAMI.2014.2307881
    [15] DONG Shi. Multi class SVM algorithm with active learning for network traffic classification[J]. Expert systems with applications, 2021, 176: 114885. doi: 10.1016/j.eswa.2021.114885
    [16] SIDDIQUI Y, VALENTIN J, NIESSNER M. ViewAL: active learning with viewpoint entropy for semantic segmentation[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Seattle: IEEE, 2020: 9430−9440.
    [17] CAO Xiaofeng. A structured perspective of volumes on active learning[J]. Neurocomputing, 2020, 377: 200–212. doi: 10.1016/j.neucom.2019.10.056
    [18] CAO Xiaofeng. A divide-and-conquer approach to geometric sampling for active learning[J]. Expert systems with applications, 2020, 140: 112907. doi: 10.1016/j.eswa.2019.112907
    [19] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492–1496. doi: 10.1126/science.1242072
    [20] SETTIES B. Curious machines: active learning with structured instances[J]. Journal of chemical information and modeling, 2013, 53(9): 1689–1699.
    [21] XIA Chenyi, HSU W, LEE M L, et al. BORDER: efficient computation of boundary points[J]. IEEE transactions on knowledge and data engineering, 2006, 18(3): 289–303. doi: 10.1109/TKDE.2006.38
    [22] QIU Baozhi, CAO Xiaofeng. Clustering boundary detection for high dimensional space based on space inversion and Hopkins statistics[J]. Knowledge-based systems, 2016, 98: 216–225. doi: 10.1016/j.knosys.2016.01.035
    [23] AGGARWAL C C. An introduction to outlier analysis[M]//Outlier Analysis. Cham: Springer International Publishing, 2016: 1−34.
    [24] KONYUSHKOVA K, SZNITMAN R, FUA P. Learning active learning from data[J]. Conference and workshop on neural information processing systems, 2017, 31(12): 4226–4236.
    [25] HE Deniu, YU Hong, WANG Guoyin, et al. A two-stage clustering-based cold-start method for active learning[J]. Intelligent data analysis, 2021, 25(5): 1169–1185. doi: 10.3233/IDA-205393
    [26] KARAMCHETI S, KRISHNA R, LI Feifei, et al. Mind your outliers! investigating the negative impact of outliers on active learning for visual question answering[C]//Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing. Stroudsburg: Association for Computational Linguistics, 2021: 7265−7281.
WeChat 点击查看大图
图(3)  /  表(4)
出版历程
  • 收稿日期:  2022-05-17
  • 网络出版日期:  2023-11-20

目录

    /

    返回文章
    返回