近亲结点图编辑的Self-Training算法

doi:10.3778/j.issn.1002-8331.2012-0124

摘要/Abstract

摘要： Self-Training算法的性能很大程度上取决于高置信度样本的识别准确度。受DPC算法启发，利用密度峰值定义样本间的原型关系，并构造出近亲结点图这一新型数据结构。在此基础上，提出了一种近亲结点图编辑的Self-Training算法（self-training algorithm with editing direct relative node graph-DRNG）。DRNG采用假设检验的方法选择高置信度样本，将其加入有标签样本集进行迭代训练。因误分的高密度样本点对Self-Training算法的分类性能影响较大，所以，DRNG综合考虑距离和密度两个方面定义了近亲结点图中割边的非对称权重，增大了高密度点的割边权重，使其落在拒绝域外的概率增加，减小了因其误分类而产生的风险。为了验证DRNG的性能，在8个基准数据集上与类似算法进行对比实验，实验结果验证了DRNG的有效性。

关键词: 近亲结点图, 半监督分类, 密度峰值, 自训练

Abstract: The performance of Self-Training algorithm largely depends on recognition accuracy of high-confidence samples. Inspired by the DPC algorithm, it defines the prototype relationship between samples by density peak and constructs a new data structure named direct relative node graph. On this basis, a novel self-training algorithm with editing direct relative node graph（DRNG） is proposed. DRNG employs a hypothesis test method to select high-confidence samples, and then adds them to the labeled sample set for iterative training. Because misclassified high-density sample points have a greater impact on the classification performance of the Self-Training algorithm, DRNG considers both distance and density to define the asymmetric weight of the cut edge in the direct relative node graph, which increases the cut edge weight of high-density points and the probability of high-density points falling outside the rejection domain. As a consequence, DRNG reduces the risk of high-density points being misclassified. To verify the performance of the DRNG, comparative experiments are carried out with 4 state-of-the-art algorithms on 8 benchmark datasets. The experimental results verify the effectiveness of the DRNG.

Key words: direct relative node graph, semi-supervised classification, density peak, self-training

刘学文, 王继奎, 杨正国, 易纪海, 李冰, 聂飞平. 近亲结点图编辑的Self-Training算法[J]. 计算机工程与应用, 2022, 58(14): 144-152.

LIU Xuewen, WANG Jikui, YANG Zhengguo, YI Jihai, LI Bing, NIE Feiping. Self-Training Algorithm with Editing Direct Relative Node Graph[J]. Computer Engineering and Applications, 2022, 58(14): 144-152.

参考文献

[1] 尚耐丽，王骁力，沈鹍霄，等.半监督分类方法的研究[J].计算机应用与软件，2015，32（11）：162-166.
SHANG Naili，WANG Xiaoli，SHEN Kunxiao，et al.On semi-supervised classification method[J].Computer Applications and Software，2015，32（11）：162-166.
[2] ZHU X J.Semi-supervised learning literature survey[R/OL].（2005）[2020-12-01].http：//digital.library.wisc.edu/1793/60444.
[3] KWOK K S，VENKATARAGHAVAN R，MCLAFFERTY F.Computer-aided interpretation of mass spectra.III.self-training interpretive and retrieval system[J].Journal of the American Chemical Society，1973，95（13）：4185-4194.
[4] 罗云松，吕佳.结合密度峰值优化模糊聚类的自训练方法[J].重庆师范大学学报（自然科学版），2019，36（2）：96-102.
LUO Yunsong，Lü Jia.Self-training algorithm combined with density peak optimization fuzzy clustering[J].Journal of Chongqing Normal University（Natural Science），2019，36（2）：96-102.
[5] 艾震鹏，王振友.基于数据密度的半监督自训练分类算法[J].计算机应用研究，2019，36（4）：1072-1074.
AI Zhenpeng，WANG Zhenyou.Self-training semi-supervised classification based on density of data[J].Application Research of Computers，2019，36（4）：1072-1074.
[6] 马茂源，吕佳.结合相似度的朴素贝叶斯半监督自训练方法[J].重庆师范大学学报（自然科学版），2019，36（1）：78-84.
MA Maoyuan，Lü Jia.Naive Bayes semi-supervised self-training method combine with similarity[J].Journal of Chongqing Normal University（Natural Science），2019，36（1）：78-84.
[7] 黎隽男，吕佳.基于近邻密度和半监督KNN的集成自训练方法[J].计算机工程与应用，2018，54（20）：132-138.
LI Junnan，LV Jia.Integrated self-training method based on neighborhood density and semi-supervised KNN[J].Computer Engineering and Applications，2018，54（20）：132-138.
[8] 黎隽男，吕佳.结合主动学习与置信度投票的集成自训练方法[J].计算机工程与应用，2016，52（20）：167-171.
LI Junnan，LV Jia.Ensemble self-training method based on active learning and confidence voting[J].Computer Engineering and Applications，2016，52（20）：167-171.
[9] JOACHIMS T.Transductive learning via spectral graph partitioning[C]//Proceedings of the 20th International Conference on Machine Learning（ICML-03）.Menlo Park，CA：AAAI Press，2003：290-297.
[10] 何丽，刘颖，韩克平.噪声标注下的改进TSVM学习算法[J].计算机工程与应用，2019，55（17）：44-50.
HE Li，LIU Ying，HAN Keping.Improved TSVM learning algorithm under noise labeling[J].Computer Engineering and Applications，2019，55（17）：44-50.
[11] 马蕾，汪西莉.基于支持向量机协同训练的半监督回归[J].计算机工程与应用，2011，47（3）：177-180.
MA Lei，WANG Xili.Semi-supervised regression based on support vector machine co-training[J].Computer Engineering and Applications，2011，47（3）：177-180.
[12] 龚彦鹭，吕佳.结合主动学习和密度峰值聚类的协同训练算法[J].计算机应用，2019，39（8）：2297-2301.
GONG Yanlu，LYU Jia.Co-training algorithm with combination of active learning and density peak clustering[J].Journal of Computer Applications，2019，39（8）：2297-2301.
[13] 龚彦鹭，吕佳.结合半监督聚类和加权KNN的协同训练方法[J].计算机工程与应用，2019，55（22）：114-118.
GONG Yanlu，LV Jia.Co-training method combined with semi-supervised clustering and weighted k-nearest neighbor[J].Computer Engineering and Applications，2019，55（22）：114-118.
[14] LI M，ZHOU Z H.SETRED：self-training with editing[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining.Berlin，Heidelberg：Springer，2005：611-621.
[15] MUHLENBACH F，LALLICH S，ZIGHED D A.Identifying and handling mislabelled instances[J].Journal of Intelligent Information Systems，2004，22（1）：89-109.
[16] 多滨，王旭峰.纸币识别系统设计与实现[J].哈尔滨理工大学学报，2008（4）：10-13.
DUO Bin，WANG Xufeng.The design and realization of paper currency recognition system[J].Journal of Harbin University of Science and Technology，2008（4）：10-13.
[17] GAN H，SANG N，HUANG R et al.Using clustering analysis to improve semi-supervised classification[J].Neurocomputing，2013，101：290-298.
[18] 黄东山.特征选择及半监督分类方法研究[D].武汉：华中科技大学，2011.
HUANG Dongshan.Research on feature selection and semi-supervised classification[D].Wuhan：Huazhong University of Science and Technology，2011.
[19] WU D，SHANG M，LUO X et al.Self-training semi-supervised classification based on density peaks of data[J].Neurocomputing，2018，275：180-191.
[20] RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.
[21] 卫丹妮，杨有龙，仇海全.结合密度峰值和切边权值的自训练算法[J].计算机工程与应用，2021，57（2）：70-76.
WEI Danni，YANG Youlong，QIU Haiquan.Self-training algorithm combining density peak and cut edge weight[J].Computer Engineering and Applications，2021，57（2）：70-76.
[22] 丁世飞，徐晓，王艳茹.基于不相似性度量优化的密度峰值聚类算法[J].软件学报，2020，31（11）：3321-3333.
DING Shifei，XU Xiao，WANG Yanru.Optimized density peaks clustering algorithm based on dissimilarity measure[J].Journal of Software，2020，31（11）：3321-3333.
[23] 王婷，王其兵，燕争上，等.基于改进的快速密度峰值聚类的调控系统故障定位算法[J].太原理工大学学报，2020，51（6）：860-866.
WANG Ting，WANG Qibing，YAN Zhengshang，et al.Fault location algorithm of control system based on improved density peak clustering[J].Journal of Taiyuan University of Technology，2020，51（6）：860-866.
[24] GAN H，TONG X，JIANG Q et al.Discussion of FCM algorithm with partial supervision[C]//Proceedings of the Eighth International Symposium on Distributed Computing and Applications to Business，Engineering and Science.Beijing，China：Publishing House of Electronics Industry，2009：27-31.
[25] TONG X，JIANG Q，SANG N et al.The feature weighted FCM algorithm with semi-supervised[C]//Proceedings of the Eighth International Symposium on Distributed Computing and Applications to Business，Engineering and Science.Beijing，China：Publishing House of Electronics Industry，2009：22-26.