结合主动学习和密度峰值聚类的协同训练算法

龚彦鹭 吕佳

摘 要：针对协同训练算法对模糊度高的样本容易标记错误导致分类器精度降低和协同训练在迭代时选择加入的无标记样本隐含有用信息不够的问题，提出了一种结合主动学习和密度峰值聚类的协同训练算法。在每次迭代之前，先选择模糊度高的无标记样本主动标记后加入有标记样本集，然后利用密度峰值聚类对无标记样本聚类得到每个无标记样本的密度和相对距离。迭代时选择具有较高密度和相对距离较远的无标记样本交由朴素贝叶斯（NB）分类，反复上述过程直到满足终止条件。利用主动学习标记模糊度高的样本能够改善分类器误标记识别问题，利用密度峰值聚类能够选择出较好表现数据空间结构的样本。在UCI的8个数据集和Kaggle的pima数据集上的实验表明，与SSLNBCA算法相比，所提算法的准确率最高提升6.7个百分点，平均提升1.46个百分点。

关键词：协同训练;主动学习;密度峰值;朴素贝叶斯;视图

中图分类号： TP181

文献标志码：A

Co-training algorithm with combination of active learning and density peak clustering

GONG Yanlu1，2，LYU Jia1，2*

1.College of Computer and Information Sciences， Chongqing Normal University， Chongqing 401331， China;

2.Chongqing Center of Engineering Technology Research on Digital Agriculture Service， Chongqing Normal University， Chongqing 401331， China

Abstract： High ambiguity samples are easy to be mislabeled by the co-training algorithm， which would decrease the classifier accuracy， and the useful information hidden in unlabeled data which were added in each iteration is not enough. To solve these problems， a co-training algorithm combined with active learning and density peak clustering was proposed. Before each iteration， the unlabeled samples with high ambiguity were selected and added to the labeled sample set after active labeling， then density peak clustering was used to cluster the unlabeled samples to obtain the density and relative distance of each unlabeled sample. During iteration， the unlabeled samples with higher density and further relative distance were selected to be trained by Naive Bayes （NB） classification algorithm. The processes were iteratively done until the termination condition was satisfied. Mislabeled data recognition problem could be improved by labeling samples with high ambiguity based on active learning algorithm， and the samples reflecting data space structure well could be selected by density peak clustering algorithm. Experimental results on 8 datasets of UCI and the pima dataset of Kaggle show that compared with SSLNBCA （Semi-Supervised Learning combining NB Co-training with Active learning） algorithm， the accuracy of the proposed algorithm is up to 6.67 percentage points， with an average improvement of 1.46 percentage points.

Key words： co-training; active learning; density peak; Naive Bayes （NB）; view

0 引言

半監督学习（Semi-Supervised Learning， SSL）[1-2]包括自训练、协同训练、生成式模型、基于图的半监督学习等，旨在利用少量的有标记样本和大量的无标记样本来训练分类器。其中，协同训练在多个视图上训练出多个分类器，通过分类器之间的协同作用得到无标记样本的类标号。经典的协同训练方法在两个充分冗余且独立的视图上进行，然而现实生活中的数据很少能够满足充分冗余且独立的条件，因此提出了其他假设的协同训练方法来放松条件。文献[3]中的研究表明，当数据集充分大时，在随机划分的特征集上进行协同训练会具有很好的效果，但该算法不具有稳定性。Du等[4]提出了启发式分割方法，将一个视图分割为两个视图，但这种方法在有标记样本数量很少时表现很差。tri-training[5]是一种新的具有协同训练模式的算法，这种算法既不需要用足够冗余的视图表现数据空间，也没有对监督学习算法提出任何约束，因此具有较强的适用性，但是在协同训练的过程中，分类器易误标记模糊度高的样本导致错误累积，而如何从无标记样本中选择可靠的样本加入训练集，也是学者研究的热点问题。

主动学习通过选择最有用的无标记样本交由专家标记来提高分类器的性能[6]。Sener等[7]将主动学习的问题定义为核心集的选择，并将这种方法运用到卷积神经网络中;Piroonsup等[8]通过聚类来实现主动学习，利用改进后的k-means聚类算法得到无标记种群的质心，再选择离质心近的样本进行主动标记;Wang等[9]研究表明，分类器输出的具有较高模糊度的样本意味着更大的错误分类风险，处理高模糊度的樣本是促进分类器性能的有效方法。

在协同训练方法中，无标记样本的有效选取也是提高分类器性能的重要步骤。Zhang等[10]根据高置信度和最近邻两个准则选择最可靠的实例，以此来增强分类器的性能;但该算法在非小样本数据集上性能表现不佳。考虑到无标记样本隐含的空间结构信息，Gan等[11]用半监督模糊C均值聚类选取隐含有用信息量高的无标记样本来辅助训练分类器;但欧氏距离对于反映属性之间的相关性效果很差，而且很难确定合适的参数。龚彦鹭等[12]考虑到无标记样本隐含的空间结构信息和协同标记的一致性，提出了结合半监督聚类（Semi-supervised Metric-based fUzzy Clustering， SMUC）和加权KNN（K-Nearest Neighbor）的协同训练方法，该方法能够有效地选择无标记样本，但计算成本较高。Rodriguez等[13]提出了密度峰值聚类，这种方法将聚类中心定义为密度高且相对距离较大的点，实验表明其具有不受数据集形状影响的良好性能，基于此特性，密度峰值聚类在数据空间表现上得到了广泛的应用。Wu等[14]利用密度峰值聚类发现数据空间结构，提出了一种自训练半监督分类框架，将数据空间的结构融入自训练迭代过程中，以此帮助训练更好的分类器。罗云松等[15]将密度峰值聚类与模糊聚类结合起来，用密度峰值优化模糊聚类，并将改进后的方法用在自训练中，提高了自训练方法的泛化性。

基于以上考虑，本文提出了结合主动学习和密度峰值聚类的协同训练方法，实验结果表明，该方法相比改进前的方法具有更好的性能。

1 本文算法

传统的协同训练算法在选择无标记样本时未考虑到高模糊度样本对分类器的影响，在迭代的过程中会造成分类器的错误累积问题。针对这种具有较高误判风险的高模糊度样本，如果能够正确处理，不仅可以避免分类器的错误累积而且能够利用高模糊度样本的信息，从而提高分类器的性能。故采用主动学习的方法去标记高模糊度的样本使分类器的性能得到提升。此外，考虑到无标记样本中隐含的空间结构信息以及密度峰值聚类在任意数据集上良好的性能表现，采用密度峰值聚类计算每一个无标记样本的密度和相对距离，以此来作为无标记样本的选择依据。因挑选的无标记样本是具有代表性的密度较高且相对距离较远的样本，故分类器在训练的过程中能够利用这些有用信息来提高性能。

1.1 主动学习

主动学习的思想是通过选择一些有价值的样本给专家主动标记从而获得性能更好的分类器，降低领域专家的工作量。如何高效地选择有价值的样本是主动学习领域一直在探讨的问题。本文将模糊度高的样本定义为有价值的样本，而对于模糊度的计算，先采用朴素贝叶斯（Naive Bayes， NB）对无标记样本进行分类得到属于每个类的概率，再用同一样本的不同类别概率的方差来表示模糊度。同一样本属于不同类别概率的方差越小，表示该样本的不确定性越大，模糊度越高，越有价值。本文主动学习算法的流程如图1所示，其中，参数ε是控制主动学习标记的无标记样本个数。

1.2 密度峰值聚类

密度峰值聚类基于两个简单、直观的假设：1）类簇中心点的密度大于周围邻居点的密度;2）类簇中心点与更高密度点之间的距离相对较大。根据这两个假设，密度峰值聚类首先发现密度峰，将其标为聚类中心，然后将其他的点分类到相应的簇中，因此，该方法能自动发现数据集的聚类中心，实现任意形状数据集的高效聚类。

在密度峰值聚类里，对于每一个样本点，都需要计算局部密度ρ和相对距离δ。

局部密度ρ的计算公式如下：

ρi=∑ j≠i χ（dij-dc） （1）

其中dc是截断距离。

dij=‖xi-xj‖2 （2）

χ（x）= 1，  x<00， 其他   （3）

为了避免dc的影响，密度峰值聚类采用如下方式计算ρ：

ρi=∑ j≠i exp（-（dij/dc）2） （4）

相对距离δ的计算公式如下：

δi=min j：ρj>ρi （dij） （5）

对于具有局部密度最大的数据点，相对距离δ的计算公式如下：

δi=max j （dij） （6）

利用得到的局部密度ρ和相对距离δ，画出ρ和δ的决策图，然后手动选择密度高且相对距离大的点作为聚类中心，并将其他的样本点归入局部密度大于自身且距离最近的样本点所在的类簇中，完成对剩余样本的分配。图2是密度峰值聚类的一个例子，该例子表现了选择聚类中心的过程，其中，图2（a）表示二维空间中的28个样本点，图2（b）是利用密度峰值聚类得到的决策图。

1.3 本文算法流程

考虑到分类器对高模糊度样本有较高的误判风险，本文先计算每个样本属于不同类别概率的方差，再选择方差小的样本作为高模糊度样本，并将这些样本交给专家主动标记后加入有标记样本集。为了利用无标记样本中的隐含信息，对无标记样本进行密度峰值聚类得到每个样本的密度和相对距离，而后迭代地选取密度较高且相对距离较远的无标记样本给分类器标记。具体算法流程如下所示。

输入：有标记样本集L，无标记样本集U，模糊度参数ε，每次从U中挑选样本的个数c，dc。

输出：最终训练好的分类器h1、h2。

步骤1  在L上训练得到朴素贝叶斯分类器h。

步骤2  用h对U分类得到每个类的隶属度u。

步骤3  计算U中每个样本隶属度的方差得到var。

步骤4  选择满足var<ε的无标记样本U′。

步骤5  将U′交给专家标识，得到类别号l′。

步骤6  L=L+（U′+l′），U=U-U′。

步驟7  对U进行密度峰值聚类，得到每个样本的密度ρ和相对距离δ。

步骤8  按照ρ+δ从大到小的顺序对U排序。

步骤9  选择U中前c个样本构造样本集R。

步骤10  如果U中样本数不足c个，则U=R。

步骤11  在采用属性集合互补方式产生的两个不同视图上，利用L分别训练出两个分类器h1和h2，用训练得到的分类器对R分类。

步骤12  若h1和h2对R中的样本分类一致，则将该样本加入到L中;否则，用加权K最近邻对该样本分类得到类标号，然后再将其加入到L。

步骤13  U=U-R，若U集不为空，返回步骤9。

2 实验结果与分析

为了说明本文算法的有效性，选择NB协同训练（NB Co-Training， NBCT）算法、结合SMUC的NB协同训练（NB Co-Training combined SMUC， NBCTSMUC）算法、结合主动学习的NB协同训练（NB Co-Training combined Active Learning，NBCTAL）算法和基于文献[10]的NB协同训练（Semi-Supervised Learning combining Co-training with Active learning， SSLNBCA）算法与本文算法进行对比实验。实验数据集来源于UCI中的8个数据集和Kaggle数据集中的pima数据集，数据集描述如表1所示。

为了保证实验准确性，实验采用十折交叉验证，将数据集随机划分为10折，其中训练集由其中的9折组成，测试集由剩下的1折组成。实验参数设置如下：dc=2，c为主动学习后无标记样本数的10%。实验中，在训练集中随机选取10%的样本作为初始有标记样本，其余样本去除类标记作为无标记样本。

2.1 实验一

为了分析参数ε的变化对本文提出算法的影响，实验一在有标记样本占比为15%时，得到了在9个数据集上当ε=0，0.01，0.03，0.05，0.07，0.09时本文算法的准确率，实验结果如图3所示。为表示方便，图3中数据集名称用缩写表示。

从图3可以看出，当ε=0.01时，本文算法在9个数据集上的准确率比ε=0时高。随着参数ε的增加，虽然在多数情况下准确率比ε=0时高，但是对比ε=0.01，准确率并没有表现出明显稳定上升。在分类器的性能表现方面，ε=0.01和ε=0.09时要更优，考虑到利用主动学习标记无标记样本的成本，选择ε=0.01。

2.2 实验二

为了说明本文算法在时间成本上低于NBCTSMUC，实验二在数据集wine计算了当十折交叉验证运行次数为1、2、3、4、5时，本文算法与NBCTSMUC需要的时间，实验结果如图4所示。

图4表明，本文算法在时间消耗方面要远低于文献[12]中提出的利用SMUC选择无标记样本的方法，因此对比SMUC，密度峰值聚类明显具有更低的计算成本。

2.3 实验三

为了说明本文算法的有效性，表2给出了5种算法在9个数据集上两个视图平均分类正确率的实验结果。

如表2所示，当有标记样本比例为10%时，除了数据集ionosphere和banknote authentication，本文算法在其他7个数据集上性能均优于对比算法。在数据集Ecoli、Iris、seeds上的准确率分别提升了3.8个百分点、5.3个百分点、4.29个百分点。这是因为算法在迭代之前选择模糊度高的样本主动标记，避免了样本错误的类标签造成的分类器错误累积问题，对于在迭代过程中加入的无标记样本，本文算法在此之前按照密度和相对距离对这些样本进行了排序，保证了每次给分类

器分类的样本都比下一次的更具代表性;而在数据集

ionosphere和banknote authentication上，本文算法的性能表现得比对比算法弱，这可能是因为按密度峰值选择无标记样本进行标记这种方式并不适合该样本集，而NBCTAL的准确率高于NBCT，这表明利用主动学习扩充训练集的方式是可行性。在数据集wine上，NBCTAL的准确率略低于NBCT，这可能是因为wine数据集本身并不具有模糊度高的较难分的样本，故利用主动学习去标记模糊度高的样本可能并不适用此数据集。

2.4 实验四

为了说明5种算法在9个数据集上的分类准确率与有标 记样本比率的关系，图5给出了当初始有标记样本比例分别为10%、20%、30%、40%、50%时5种算法在9个数据集上的分类准确率。

从图5可以看出，在数据集pima、Ecoli、Breast Cancer Wisconsin （Original）、Iris、wine上，本文算法的性能均高于对比算法。在数据集abalone和数据集banknote authentication，随着有标记比例的增加，本文算法的性能弱于对比算法，这可能是因为当有标记比例增加后，未标记样本中的模糊数据变少，利用主动学习标记模糊数据方法的效果变差。在数据集ionosphere上，虽然当有标记比例为10%和20%时，本文算法在性能上表现得比对比算法差;但随着有标记样本数的增加，当有标记比例为30%、40%和50%时，本文算法分类性能要高于对比算法。这可能是因为在数据集ionosphere上，过少的初始有标记样本导致分类器学习的效果不好。

2.5 时间复杂度分析

表3给出了5种算法的时间复杂度，其中n为数据集样本个数，m为NBCTSMUC迭代过程中每次选择无标记样本的个数。从表3可以看出，除NBCTSMUC外，其他算法的时间复杂度皆为O（n2）。

本文算法的时间复杂度由主动学习、密度峰值聚类和朴素贝叶斯协同训练三个部分组成，各部分的时间复杂度都为O（n2），故本文算法总的时间复杂度为O（n2）;NBCT迭代计算每一个样本的概率，时间复杂度为O（n2）;NBCTAL的时间复杂度由主动学习和朴素贝叶斯协同训练两部分组成，其时间复杂度分别为O（n）和O（n2），所以NBCTAL總的时间复杂度为O（n2）;SSLNBCA的时间复杂度为O（n2），由样本选取、主动标记和朴素贝叶斯协同训练三部分组成;NBCTSMUC在n/m次迭代中计算每个样本的每个类别的马氏距离，时间复杂度为O（n5/m）。

3 结语

针对协同训练方法对模糊度高的样本容易误标记和在迭代过程中加入的无标记样本所含有用信息量不高的问题，本文提出了一种结合主动学习和密度峰值聚类的协同训练方法。该方法在每次迭代之前，先选择出模糊度高的无标记样本主动标记后加入有标记样本集，然后用密度峰值聚类对训练集进行聚类，迭代地选取密度较高且相对距离较远的无标记样本给NB分类，最后在UCI数据集上验证了算法的有效性。在后续的工作中，将讨论最优参数以及如何判别噪声点和如何减少噪声点对算法的影响。

参考文献

[1] GOUTTE C， CANCEDDA N， DYMETMAN M， et al. Semi-supervised learning for machine translation[J]. Journal of the Royal Statistical Society， 2017， 172（2）： 530-530.

[2] ZHU S， SUN X， JIN D. Multi-view semi-supervised learning for image classification [J]. Neurocomputing， 2016， 208（10）： 136-142.

[3] XU C， TAO D， XU C. Large-margin multi-view information bottleneck[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2014， 36（8）： 1559-1572.

[4] DU J， LING C X， ZHOU Z H. When does cotraining work in real data？[J]. IEEE Transactions on Knowledge and Data Engineering， 2011， 23（5）： 788-799.

[5] QIAN T， LIU B， CHEN L， et al. Tri-training for authorship attribution with limited training data： a comprehensive study[J]. Neurocomputing， 2016， 171（1）： 798-806.

[6] DEKEL O， GENTILE C， SRIDHARAN K. Selective sampling and active learning from single and multiple teachers[J]. Journal of Machine Learning Research， 2016， 13（1）： 2655-2697.

[7] SENER O， SAVARESE S. Active learning for convolutional neural networks： a core-set approach[J]. arXiv E-print， 2017： arXiv：1708.00489.

[8] PIROONSUP N， SINRHUPINVO S. Analysis of training data using clustering to improve semi-supervised self-training[J]. Knowledge-Based Systems， 2018， 143（2）： 65-80.

[9] WANG X Z， ASHFAG R A R， FU A M. Fuzziness based sample categorization for classifier performance improvement[J]. Journal of Intelligent and Fuzzy Systems， 2015， 29（3）： 1185-1196.

[10] ZHANG Y， WEN J， WANG X， et al. Semi-supervised learning combining co-training with active learning[J]. Expert Systems with Applications， 2014， 41（5）： 2372-2378.

[11] GAN H， SANG N， HUANG R， et al. Using clustering analysis to improve semi-supervised classification[J]. Neurocomputing， 2013， 25（3）： 290-298.

[12] 龚彦鹭，吕佳.结合半监督聚类和加权KNN的协同训练方法[J/OL].计算机工程与应用，2019：1-9[2018-12-28]. http：//kns.cnki.net/kcms/detail/11.2127.TP.20181218.1748.032.html. （GONG Y L， LYU J. Co-training method combined semi-supervised clustering and weighted K nearest neighbor[J/OL]. Computer Engineering and Applications，2019： 1-9[2018-12-28]. http：//kns.cnki.net/kcms/detail/11.2127.TP.20181218.1748.032.html.）

[13] RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks[J]. Science， 2014， 344（6191）： 1492-1496.

[14] WU D， SHANG M S， LUO X， et al. Self-training semi-supervised classification based on density peaks of data[J]. Neurocomputing， 2018， 275（1）： 180-191.

[15] 罗云松，吕佳.结合密度峰值优化模糊聚类的自训练方法[J].重庆师范大学学报（自然科学版），2019，36（2）：74-80. （LUO Y S， LYU J. Self-training algorithm combined with density peak optimization fuzzy clustering[J]. Journal of Chongqing Normal University （Natural Science）， 2019， 36（2）： 74-80.）