结合半监督聚类和数据剪辑的自训练方法

吕 佳，黎隽男

(重庆师范大学 计算机与信息科学学院，重庆 401331)(*通信作者电子邮箱lvjia@cqnu.edu.cn)

0 引言

自训练方法[1]是半监督学习[2]算法中的一种，它利用少量的有标记样本和大量的无标记样本共同去训练一个分类器，用来解决数据标注的瓶颈问题。由于它不需要特定的假设条件且简单有效，受到了不少学者青睐。

Hady等[3]提出Co-Training by Committee自训练学习框架，该方法集成多个分类器共同进行自训练学习，其中置信度为多个分类器的平均后验概率。针对选取最大后验概率时，可能出现重复的最大后验概率的问题，Wang等[4]引入了Naive Bayes(NB)[5]，最大后验概率取平均后验概率与NB后验概率之和。同时针对这个问题，Liu等[6]引入了一种基于距离的度量方式，即当平均后验概率相同的时候，离类别中心越近的样本的置信度越高，越可靠。Shi等[7]提出集成SVM(Support Machine Vector)[8]、NB和Rocchio[9]三个异构分类器自训练的方式对文本进行分类，通过按类别投票的方式选取可靠的样本。Hajmohammadi等[10]提出结合主动学习与自训练的方法去解决跨语言分类问题，该方法用自训练方法选取置信度高的样本，同时用平均余弦相似度和熵结合的方法去选取一些信息量大的样本。Leng等[11]提出结合主动学习和自训练方法去构建SVM分类器，用SVM分类器去选择类中心且标记改变率为0的样本，同时用主动学习去选择离决策边界近的样本。然而，在上述自训练方法中，如果误标记的无标记样本被作为可靠样本加入到训练集中，不仅会降低自训练方法的性能，还会造成错误累积问题，使样本原本数据空间结构发生扭曲。

数据剪辑是一种统计过滤技术，它一般用KNN(KNearest Neighbors)[12]作为基分类器，来去除样本中潜在的噪声，同时保留正确的样本。不少学者用数据剪辑技术来去除自训练方法中的潜在的误标记样本。Fan等[13-14]提出结合KNN数据剪辑技术的NB自训练算法，用KNN数据剪辑技术过滤掉NB自训练的噪声样本点。黎隽男等[15]提出结合加权KNN(WeightedKNearest Neighbors, WKNN)数据剪辑技术的NB自训练算法，把WKNN和NB分类器投票一致且置信度都高的样本加入到训练集。Triguero等[16]总结数十种数据剪辑技术，并把它们结合到自训练方法中进行了实验性分析。

针对自训练方法选出置信度高的无标记样本中，所含信息量可能不大的问题，Gan等[17]提出用半监督模糊C均值(Semi-supervised Fuzzy C Means, SFCM)去改进自训练方法。他认为无标记样本可能含有数据空间结构潜在信息，利用好这些潜在的信息，能更好地辅助自训练方法，从而提高自训练方法的泛化性。

为了解决自训练方法中的错误累积问题和自训练选出置信度高的无标记样本所含信息量不大，从而导致自训练方法泛化性不强的问题，并受聚类和数据剪辑技术的共同启发，本文提出结合SMUC(Semi-supervised Metric-based fUzzy Clustering)[18]和SKNN(Semi-supervisedKNearest Neighbor)[19]数据剪辑技术的NB自训练方法(Naive Bayes Self-Training combined SMUC and SKNN Data Editing, NBSTSMUCSKNNDE)。实验结果表明，本文提出方法相比改进前方法具有更好的性能。

1 提出算法

传统的数据剪辑技术仅仅利用有标记样本的信息，而假设无标记样本的类标号是不可预测的，但是自训练方法中，有标记样本是很少的，那么数据剪辑的性能可能因有标记样本的数量的匮乏而下降。陈日新等[19]提出SKNN方法，它能同时利用有标记样本信息和无标记样本信息对待测样本进行分类。他认为，如果无标记样本和有标记样本来自一个共同的序列，那么有效利用无标记样本信息，能提高KNN算法的性能，因此，本文提出的NBSTSMUCSKNNDE引入了一种新的数据剪辑方法，用SKNN作为数据剪辑的基分类器。它能够同时利用有标记样本信息和无标记样本信息进行数据剪辑，在有标记样本不足的情况下，利用额外无标记样本信息来提高数据剪辑的性能，从而更好地解决自训练方法中的错误累积问题。

传统的自训练方法会随机选择一些无标记样本给自训练方法学习，而选择更具有信息量的无标记样本给自训练方法学习，能提高自训练方法的性能，所以本文提出的NBSTSMUCSKNNDE用半监督聚类SMUC方法去选择一些聚类隶属度高的无标记样本给自训练方法学习。聚类隶属度高的无标记样本离样本真实的类中心越近，它包含着原始样本空间结构信息。NBSTSMUCSKNNDE的自训练学习器如果能正确标记这样的无标记样本，并加入到训练集，则可以提高自训练方法的泛化性。

2 SKNN数据剪辑技术

传统的数据剪辑技术有ENN(Edited Nearest Neighbor)[20]、RENN(Repeated Edited Nearest Neighbor)[21]、ALLKNN(AllKNearest Neighbors)[21]、MENN(Modified Edited Nearest Neighbor)[22]等，它们都是利用KNN或WKNN分类的结果与给定样本的类标号进行对比，如果类标号不一致，就判断为噪声样本，但是KNN或WKNN只考虑到了k个有标记近邻样本对待测样本的类别的贡献，没有考虑到无标记近邻样本对待测样本的影响，如果待测样本和无标记样本来自一个共同的序列，它们的类别就会存在一定的联系，根据待测样本和无标记样本的相关性，可以提高数据剪辑的精度，从而提高算法性能。如图1所示，如果用KNN或WKNN进行分类，待测样本x会被分到A类，实际上样本x应该属于B类。针对这个问题，SKNN在对待测样本分类时，考虑有标记样本和无标记样本对待测样本的共同影响。

图1 采用KNN或WKNN分类时的错误分类的情况

在SKNN中，设无标记样本x0，x1，…，xt，那么对待测样本xt进行分类的时候，考虑到xt与x0:t-1的样本存在一定的相关性，为此SKNN采用联合概率密度P(ωk|xt,x0:t-1)作为分类依据，其中ω为类标记。

首先从已标记样本集中找出与xt的k1+1个最近的样本，用xt(1)，xt(2)，…，xt(k1+1)表示，类标号为t(1)，t(2)，…，t(k1+1)。从无标记样本集中找出与待测样本最近的k2个无标记样本，分别用xt-1，xt-2，…，xt-k2表示，组成测试样本本序列。

接着用第k1+1个近邻样本xt(k1+1)到测试样本xt的距离d(xt,xt(k1+1))来标准化前k1个近邻样本xt(1)，xt(2)，…，xt(k1)到测试样本{xj，j=t，t-1，…，t-k2}的距离：

(1)

然后用高斯核函数核化标准后的距离：

(2)

最后确定xt样本的类别表达式如下，具体推导见文献[19]。

(3)

SKNN数据剪辑技术算法流程如下所示。

输入：有标记近邻样本数k1，无标记近邻样本数k2，数据集D。

输出：过滤后的样本集Filtered_D。

过程：

forxi∈D

1)SKNN分类xi得到类标号ti，依据式(1)～(3)。

2)如果ti与xi本身的类标号不一致，则视xi为噪声样本，丢弃。

end

3 半监督模糊C均值聚类

Gan等[17]提出用SFCM去辅助自训练方法，实验结果表明SFCM作为一种知识发掘工具，能挖掘大量无标记样本所暗含的数据空间结构信息。新标记的有标记样本不仅可以改善自训练方法，而且也可以改善SFCM的性能，从而让SFCM更好地优化自训练方法。SFCM损失函数如下：

(4)

其中：c为类别个数，n为样本个数，m为参数。如式(4)所示，对于SFCM，m值的选取一直是一个棘手的问题，并且用欧氏距离来计算样本间的距离，没有考虑到样本属性之间的关联性。Yin等[18]提出SMUC，它用正则熵的方法来解决SFCM的m值选取问题，同时用马氏距离代替欧氏距离，考虑到实际应用中属性之间的关系，因此，NBSTSMUCSKNNDE用SMUC替代SFCM辅助自训练方法，能选出更具有信息量的无标记样本交给自训练方法进行学习。SMUC推导如下。

给定先验隶属度矩阵：

U′={uik′|uik′∈[0,1];i=1,2,…,n;k=1,2,…,c}

(5)

同时满足如下条件：

(6)

首先获得先验质心：

(7)

接着计算协方差矩阵：

(8)

根据式(8)的协方差矩阵，给定两个样本x1，x2，马氏距离计算如下：

(9)

SMUC的损失函数如下，其中等式右边加入了熵正则表达式：

(10)

式(10)是一个凸优化问题，进行拉格朗日优化：

(11)

根据式(11)，对uik和vk求偏导后，得到隶属度uik和vk的计算公式，如下：

(12)

(13)

SMUC算法流程如下所示。

输入：数据集D，先验隶属度uik′，聚类数量c。

输出：成员隶属度uik。

过程：

依据式(7)计算先验质心。

依据式(8)计算协方差矩阵C。

while ‖uk-uk-1‖≥ε

依据式(12)计算uik。

依据式(13)计算vk。

end

4 算法流程

首先，NBSTSMUCSKNNDE用少量的有标记样本和大量的无标记样本进行SMUC聚类，从而选出隶属度高的无标记样本给NB自训练方法分类。然后，NBSTSMUCSKNNDE用SKNN数据剪辑技术来过滤掉聚类隶属高但是NB自训练方法误分类无标记样本。聚类隶属度高的无标记样本，更接近每一个聚类簇的中心，这样的无标记样本更好地反映了每一个聚类簇的结构。如果把这些聚类隶属度高的无标记样本正确标记，并加入到训练集，能使训练集更好地代表原始样本空间的结构，从而提高NB自训练方法的泛化性，但是聚类隶属度高的无标记样本可能是每次自训练方法迭代中离决策边界近的样本，NB自训练方法难以把这样聚类隶属度高的样本分类正确。如果错误标记这样的样本，然后加入到训练集，不仅会扭曲数据空间原始结构而且会使NB自训练方法性能下降。SKNN数据剪辑技术能过滤掉聚类隶属高但是NB自训练方法误分类无标记样本，使标记正确的所含信息量大的无标记样本加入到训练集，因此，本文提出的方法通过SMUC和SKNN数据剪辑技术结合的方式，既解决了自训练方法选出置信度高的无标记样本所含信息量不大的问题，又解决了自训练方法的错误累积问题。新标记的无标记样本加入到训练集，不仅可以提高自训练方法的性能，而且可以更好地让半监督聚类和数据剪辑为自训练方法服务。

NBSTSMUCSKNNDE算法流程如下所示。

输入：有标记样本集L，无标记样本集U，有标记近邻样本k1，无标记近邻样本k2，参数ε1，参数ε2，参数η。

输出：训练好的NB。

过程：

whileU集不为空

用样本集L和U进行SMCU聚类，选出隶属度uik≥ε1的样本集R1；

whileR1为空

ε1=ε1-0.05，选出隶属度uik≥ε1的样本集R1；

end

用样本集L和U训练分类器NB，用训练后的分类器对R1分类，选出置信度大于ε2的样本集R2，并得到其类标号Tag2；

whileR2为空

ε2=ε2-0.05，选出置信度大于ε2的样本集R2，并得到其类标号Tag2；

end

用SKNN数据剪辑技术过滤掉R2中的噪声样本，得到可靠样本集R3；

L=L+R3，U=U-R3；

end

5 实验仿真

为了说明本文算法的有效性，选用对比算法如下：

1)NB自训练(NB Self-Training, NBST)。

2)结合SFCM的NB自训练(NB Self-Training combined SFCM, NBSTSFCM)。

3)结合SMUC的NB自训练(NB Self-Training combined SMUC, NBSTSMUC)。

4)本文提出的结合SMUC和SKNN数据剪辑技术的NB自训练(Naive Bayes Self-Training combined SMUC and SKNN Data Editing, NBSTSMUCSKNNDE)。

实验数据集来源于UCI数据集，共8个，如表1。把每一个数据集随机分为测试集和训练集两部分，其中训练集为80%，测试集为20%。在训练集中随机选取10%的样本作为初始化的有标记样本，其余样本去除类标记作为无标记样本。NBSTSFCM中的参数m=2。NBSTSMUCSKNNDE中的参数ε1=0.95，ε2=0.95，η=1，其他参数在各个数据集调整至最优进行实验，如表2。实验重复10次，取10次的平均分类正确率±标准差，如表3所示。为了说明有标记样本数对算法的影响，图2给出了当初始化的有标记样本比例为10%～50%的时候，实验重复10次，4个算法在8个数据集上的平均分类正确率。

表1 UCI数据集描述

表2 实验参数设置

表3 有标记率为10%时，4个算法在8个数据集上的性能对比

从表3总体可以看出，当有标记样本比例为10%的时候，本文提出的NBSTSMUCSKNNDE算法整体上性能好于对比算法。具体地看，当有标记样本率为10%时：在数据集Vertebral Column、Haberman’s Survival、Blood Transfusion Service Center、Breast Cancer Wisconsin (Original)和Indian Liver Patient Dataset上，本文提出算法均优于对比算法；但在数据集IRIS、Seeds和Wine上，本文提出算法弱于对比算法。这可能是数据集IRIS、Seeds和Wine中的样本数太少，用过少的有标记样本来指导SMUC聚类，难以找到信息量大的无标记样本给NB自训练标记。而且在迭代初期，有标记样本过少也影响SKNN数据剪辑技术对无标记样本利用的准确率，最终使SMUC和SKNN数据剪辑技术难以有效辅助NB自训练方法。在8个UCI数据集上，NBSTSFCM性能微弱于NBSTSMUC，这是因为NBSTSMUC用SMUC代替SFCM，考虑到了实际应用中属性之间的关联性。NBSTSFCM、NBSTSMUC的分类正确率在数据集Haberman’s Survival和Blood Transfusion Service Center上高于NBST，但在其他6个数据集上，分类正确率低于NBST。这是因为聚类算法能选出无标记样本中一些暗含数据空间结构的样本，但是这样的样本可能是NB自训练每次迭代很难正确标记的样本。如果用SKNN数据剪辑技术过滤掉这些样本，则能更好地提高NB自训练性能，因此本文提出的NBSTSMUCSKNNDE优于对比算法。

从图2可以看出，在数据集Vertebral Column、Haberman’s Survival、Blood Transfusion Service Center、Breast Cancer Wisconsin (Original)和Indian Liver Patient Dataset上，本文提出的NBSTSMUCSKNNDE算法在有标记样本比例为10%～50%的情况下，分类正确率都优于对比算法。虽然当有标记样本为10%的时候，在IRIS、Seeds数据集上，和当有标记样本比例为10%、20%的时候，在Wine数据集上，NBSTSMUCSKNNDE算法在分类正确率上低于NBST，但是随着有标记比例的增加，也能好于对比算法。这可能是因为IRIS、Seed和Wine样本量过少的缘故。同时，当有标记样本比例为10%～50%的情况下，NBSTSMUC在8个数据集上，整体性能也好于NBSTSFCM。这也证明了本文NBSTSMUCSKNNDE算法用SMUC的优势。

6 结语

本文针对自训练方法在迭代中选出的置信度高的无标记样本所含信息量不大和自训练方法容易误标记无标记样本的问题，提出NBSTSMUCSKNNDE算法。在自训练每次迭代中，该算法用SMUC选取暗含数据空间结构信息的无标记样本给NB分类，同时用SKNN数据剪辑技术来过滤掉聚类信息量大但是NB误分类的无标记样本。相比传统的半监督聚类，SMUC考虑到了实际应用中属性之间的关联性，并且用熵正则化来优化物理表达式，克服了SFCM难找到一个最优参数来发掘更具有信息量的无标记样本的问题。同时，本文首次提出了一种新的数据剪辑技术，相比以往的数据剪辑技术，SKNN能同时利用有标记样本和无标记样本信息进行噪声过滤，在有标记样本不足的情况下，它能利用额外的无标记样本信息来过滤掉自训练方法中误标记的无标记样本。最后在UCI数据集上验证了算法的有效性。在后续的工作中，将研究如何降低本文提出方法的时间复杂度和如何提高自训练方法在迭代中的预测准确率问题。

References)

[1] YAROWSKY D. Unsupervised word sense disambiguation rivaling supervised methods [C]// ACL ’95: Proceedings of the 33rd Annual Meeting on Association for Computational Linguistics. Stroudsburg: Association for Computational Linguistics, 1995: 189-196.

[2] ZHU X, GOLDBERG A B, BRACHMAN R, et al. Introduction to Semi-Supervised Learning [M]. San Rafael, CA: Morgan and Claypool Publishers, 2009: 130.

[3] HADY M F A, SCHWENKER F. Co-training by committee: a new semi-supervised learning framework [C]// ICDMW ’08: Proceedings of the 2008 IEEE International Conference on Data Mining Workshops. Washington, DC: IEEE Computer Society, 2008: 563-572.

[4] WANG S, WU L, JIAO L, et al. Improve the performance of co-training by committee with refinement of class probability estimations [J]. Neurocomputing, 2014, 136(8): 30-40.

[5] LEWIS D D. Naive (Bayes) at Forty: the independence assumption in information retrieval [C]// ECML ’98: Proceedings of the 10th European Conference on Machine Learning. Berlin: Springer, 1998: 4-15.

[6] LIU K, GUO Y, WANG S, et al. Semi-supervised learning based on improved co-training by committee [C]// IScIDE 2015: Proceedings of the 5th International Conference on Intelligence Science and Big Data Engineering. Big Data and Machine Learning Techniques. Berlin: Springer, 2015: 413-421.

[7] SHI L, MA X, XI L, et al. Rough set and ensemble learning based semi-supervised algorithm for text classification [J]. Expert Systems with Applications, 2011, 38(5): 6300-6306.

[8] JOACHIMS T. A statistical learning model of text classification with support vector machines [C]// SIGIR ’01: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2001: 128-136.

[9] JOACHIMS T. A probabilistic analysis of the Rochhio algorithm with TFIDF for text categorization [C]// ICML ’97: Proceedings of the Fourteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 1997: 143-151.

[10] HAJMOHAMMADI M S, IBRAHIM R, SELAMAT A, et al. Combination of active learning and self-training for cross-lingual sentiment classification with density analysis of unlabelled samples [J]. Information Sciences, 2015, 317: 67-77.

[11] LENG Y, XU X, QI G. Combining active learning and semi-supervised learning to construct SVM classifier [J]. Knowledge-Based Systems, 2013, 44(1): 121-131.

[12] COVER T M. HART P E. Nearest neighbor pattern classification [J]. IEEE Transactions on Information Theory, 1967, 13(1): 21-27.

[13] FAN X, GUO Z, MA H. An improved EM-based semi-supervised learning method [C]// IJCBS ’09: Proceedings of the 2009 International Joint Conference on Bioinformatics, Systems Biology and Intelligent Computing. Washington, DC: IEEE Computer Society, 2009: 529-532.

[14] FAN X, GUO Z, MA H. A semi-supervised text classfification method based on incremental EM algorithm [C]// ICIE ’10: Proceedings of the 2010 WASE International Conference on Information Engineering. Washington, DC: IEEE Computer Society, 2010: 211-214.

[15] 黎隽男,吕佳.结合主动学习与置信度投票的集成自训练方法[J].计算机工程与应用,2016,52(20):167-171.(LI J N, LYU J. Ensemble self-training method based on active learning and confidence voting [J]. Computer Engineering and Applications, 2016, 52(20): 167-171.)

[16] TRIGUERO I, SáEZ J A, LUENGO J, et al. On the characterization of noise filters for self-training semi-supervised in nearest neighbor classification [J]. Neurocomputing, 2014, 132(13): 30-41.

[17] GAN H, SANG N, HUANG R, et al. Using clustering analysis to improve semi-supervised classification [J]. Neurocomputing, 2013, 101(3): 290-298.

[18] YIN X, SHU T, HUANG Q. Semi-supervised fuzzy clustering with metric learning and entropy regularization [J]. Knowledge-Based Systems, 2012, 35(15): 304-311.

[19] 陈日新,朱明旱.半监督K近邻分类方法[J].中国图象图形学报,2013,18(2):195-200.(CHEN R X, ZHU M H. Semi-supervisedK-nearest neighbor classification method [J]. Journal of Image and Graphics, 2013, 18(2): 195-200.)

[20] WILSON D L. Asymptotic properties of nearest neighbor rules using edited data [J]. IEEE Transactions on Systems Man & Cybernetics, 1972, SMC- 2(3): 408-421.

[21] TOMEK I. An experiment with the edited nearest-neighbor rule [J]. IEEE Transactions on Systems Man & Cybernetics, 1976, 6(6): 448-452.

[22] HATTOR K, TAKAHASHI M. A new editedk-nearest neighbor rule in the pattern classification problem [J]. Pattern Recognition, 2000, 33 (3): 521-528.

This work is partially supported by Chongqing Natural Science Foundation of China (cstc2014jcyjA40011), Science and Technology Project of Chongqing Municipal Education Commission (KJ1400513), Chongqing Scientific Research Project (CYS17176), Chongqing Normal University Research Project (YKC17001).

LYUJia, born in 1978, Ph. D., professor. Her research interests include machine learning, data mining.

LIJunnan, born in 1992, M. S. candidate. His research interests include machine learning, data mining.