logo资料库

一种改进的Tri-training 算法.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.20M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    中国科技论文在线 http://www.paper.edu.cn 一种改进的 Tri-training 算法 胡汇涓，王雪松* （中国矿业大学信息与电气工程学院，江苏 徐州 221008） 摘要：针对传统 Tri-training 算法中使用三个相同分类器的分类精度低，泛化能力不强的局 限性，本文采用三个不同的分类器，利用不同分类器之间合作算法和投票选举的方式对未标 记数据进行标记，大大提高了算法的泛化能力；并引入自适应数据剪辑策略，消除训练数据 中的噪声。通过实验说明改进后的算法相对传统 Tri-training 算法在分类精度上有不同程度 的改进。 关键词：支持向量机；K 近邻；朴素贝叶斯； Tri-training 算法；数据剪辑；自适应策略 中图分类号：TP13 An improved Tri-training algorithm HU Huijuan, Wang Xuesong Jiangsu Xuzhou 221008, China) (School of Information and Electrical Engineering, China University of Mining and Technology, Abstract: Tri-training algorithm was developed from co-training algorithm. In order to solve the limitation of the traditional Tri-training algorithm such as low Classification Accuracy and weak Generalization ability, an improved algorithm is proposed. It greatly improved the generalization by different classifiers cooperation and the use of polling on unlabeled training data .Meanwhile , a method of data editing and adaptive is introduced to eliminate the noise of training data.This paper uses many UCI data sets to test the improved algorithm based on three different classifiers. Compared with the traditional algorithm, it uses three same KNN classifiers, Naive Bayes classifier and SVM classifier . the experiment shows that the improved algorithm advanced greatly in the classification accuracy. Key words: Support Vector Machine;K-Nearest Neighbor algorithm;Naive Bayesian;Tri-training;Data editing;Adaptive strategy 0 引言 半监督学习作为一种近年来新提出的学习策略，弥补了监督学习与无监督学习的不足， 同时利用标记数据和未标记数据,已经成为机器学习领域的研究热点，吸引着越来越多的学 者对其进行深入地研究[1]。协同训练算法是基本半监督学习算法其中之一，Blum 和 Mithchell 在 1998 年提出协同训练算法后，Goldman 等提出了一种改进算法，要求分类器所用的有监 督算法能够将实例空间划分为等价类集合，导致算法时间复杂度较高。Zhou 等于 2005 年 提出了一种既不要求充分冗余视图，也不要求使用不同类型分类器的 Tri-training 算法[2]。 Tri-training 算法。它不仅可以简便地处理标记置信度估计问题以及对未见示例的预测问题， 还利用集成学习来提高泛化能力。针对 Zhou 提出的分类算法中的三个分类器采用同一种监 督分类学习方法作为基分类器算法结果的局限性，本文引入自适应数据剪辑策略并采用三种 不同的分类算法进行学习。随机选取 UCI 数据集上的数据进行仿真实验，对比可知改进后 的方法比原来的算法分类结果更精确，泛化能力更强。 作者简介：胡汇涓（1986-），女，研究生，控制工程. E-mail: huhuijuan1012@sina.com - 1 -
    中国科技论文在线 1 Tri-training 算法训练策略 1.1 标准 Tri-training 算法简介 http://www.paper.edu.cn 1 2 , , Tri-training 分类算法的大致过程为，首先初始化少量己标记的数据集 L ，由 L 训练得到 ，x 是无标记数据集U 中的任意一点， 2H 和 3H 对 x 的分类结果一 HHH 三个分类器 3 )(2 xH 并 加 入 到 1H 的 训 练 集 中 ， 如 此 形 成 1H 的 新 训 练 集 致 ， 那 么 将 x 标 记 为 ( ) 。类似的 2H 和 3H 的训练集分别扩充为 2S′ 和 3S′ ， S ′ = = 1 然后三个分类器重新训练，如此重复迭代，直至 1H 、 2H 、 3H 没有变化，训练过程结束。 Tri-training 训练过程中，三个分类器相应训练集的迭代扩充过程就是实现训练集增大的过程 [3]。 } ( ) x x UandH x H x ∪ ∈ { L 2 3 对不同未标记样例的标记置信度进行比较，而不是显式的对标记置信度进行比较，这就 避免了频繁的使用耗时的统计测试技术[4]。但是，美中不足的是与显式估计标记置信度相比 较而言，这一隐式处理往往不够准确，特别是最初的时候出示分类器比较弱，未标记样例可 能别错误标记，从而给第三个分类器引入噪声[5]。Zhou 和 Li 通过噪声学习理论推导出了能 以较高概率确保这一做法的有效条件，直观地说，如果大多数为标记样例标记的类别是准确 的，那么引入的噪声数据所带来的负面影响可以被使用大量的未标记样例所带来的好处所抵 消。 1.2 算法改进 在 Tri-training 分类算法中，采用三个分类器按投票规则对数据进行分类，Zhou 提出的 Tri-training 分类算法的三个分类器采用同一种监督分类学习方法作为基分类器。由于使用同 一种学习方法对数据进行训练，即使训练集不同，得到的分类器对任意数据分类结果相同的 概率要大于不同的概率，同时算法的泛化能力也不强。对于任意一个未标记的数据 x ，如果 在实际中数据 x 属于类别c ，那么在正确率较高的情况下，无论采用哪一种分类算法作为学 习算法，得到的分类器对 x 进行分类时，都应该将 x 分到类别c 中。因此，如果采用三个不 同的监督分类算法作为学习算法，不仅仅可以减小任意两个数据分类结果相同的概率，同时 还可以提高算法的泛化能力。并且改进后的方法结合 RemoveOnly 剪辑操作[6]和自适应数据 剪辑策略[7]到 Tri-training 学习过程，在每次迭代生成新数据时，不仅用数据剪辑技术主动识 别并移除新标记数据中可能的误标记样例以减少新训练集的噪声，同时采用的自适应策略能 有效地控制不同迭代情况下 RemoveOnly 剪辑操作的触发和抑制时机，使剪辑操作固有的错 误率引起的负面效应不会影响分类性能迭代提高。 自适应剪辑策略：令 tL 代表第t 轮为若第 1t − 轮迭代中 1h 新标记的样例集， t 后剩余训练集， tε 和 t 第 1t − 轮迭代中 RemoveOnly 未被触发且 deε 分别为分别为 L L∪ 和 L t t deL 为剪辑 L L∪ 对 1h 训练所得假设分类错误率。若 L −> t 1 ，则在保证 情况下， t de < t < t t 1 deε ε ε− L −> t 1 L t RemoveOnly 将被触发；若第 1t − 轮迭代中 RemoveOnly 未被触发且 ；则在无法 满足 t tε ε−< 但满足 1 t t 1 deε ε−< RemoveOnly 已被触发且 L t 的情况下，RemoveOnly 将被 触发； 若第 1t − 轮迭代中 L −> t 1 de < 的情况下，RemoveOnly 将被 t t 1 ε ε ε− de de ；则在保证 < t - 2 -
    中国科技论文在线 http://www.paper.edu.cn 触发；若第 1t − 轮迭代中 RemoveOnly 已被触发且 L t L −> t 1 de ；则在无法满足 t ε ε−< 但满 1 t de 足 1 t de t ε ε−< 的情况下，RemoveOnly 将被触发；除上述情形外，RemoveOnly 将被触发。 de 改进算法伪码： 输入:未标记数据集U ，已标记数据集(初始训练集) L ，测试集T ，未训练的分类器 HHH , , 2 1 。 3 输出：分类的错误率。 (1)随机抽样 L，分成三份，即三个训练集 SSS , 1 , 2 3 分别来训练 kjHH ,( , 2 , 。 HHH , 1 ≠ 选择满足上述条 ) i 3 j k HHHH i ) (2)对于每个 3 { xHUxx / )( ( ∈ 且 = L i , , j 2 1 件的子集 ，从无标记数据集中由 })( xH k 进行标记。 = 1 2 3 , , ( ) ，若被触发则用剪辑后的新标记样例集更新训练集重新训练；若被抑制则 (3)尝试用 RemoveOnly 剪辑新标记样例集，然后计算 RemoveOnly 两个性能并根据当前 情 形 由 上 述 自 适 应 策 略 中 的 触 发 条 件 决 定 RemoveOnly 被 触 发 或 抑 制 ， 对 于 每 个 HHHH i 仍按标准 Tri-training 方式更新训练集。 ) (4)如果对于每个 (5)对任意 给定的未标记数据采用{ 在 标 准 Tri-training 基 本 训 练 过 程 能 保 证 所 得 假 设 准 确 率 迭 代 提 高 的 基 础 上 ， ADE-training 将尽可能触发 RemoveOnly 剪辑操作使准确率最大限度提高，在无法保证所得 假设准确率迭代提高的时候，将试图触发剪辑操作使准确率仍能迭代提高。 2 实验分析与比较 ，如果有一项发生变化，则转（2）. HHH 联合分类器投票规则分类。 HHHH i }3 ( , , , , 3 2 1 2 1 2.1 实验数据 本小节主要针对 Zhou 和 Li 提出的 Tri-training 模型进行实现，并分析其分类性能。为 了检验本文提出的改进的 Tri-training 分类模型与 Zhou 和 Li 提出的 Tri-training 分类算法关 于分类性能的好坏，分别对这两种分类算法进行实验，通过实验给出了这两种分类算法的分 类准确率。实验数据集来自 UCI 机器学习库，从 UCI 机器学习库中五个数据集进行测验， 该数据集的规模，属性以及类别如表 1 所示。 表 1 实验数据集信息表 Tab. 1 Information of Data Set 数据集 Sick Diabetes Ionosphere Kr-vs-Kp Australian 样本个数 3772 768 351 3196 690 维数 30 9 34 36 14 类别数 2 2 2 2 2 正负样本比例 93.8%:6.2% 65.1%:34.9% 35.9%:64.1% 52.2%:47.8% 55.4%:44.5% 本实验中从每个数据集合中随机抽取 20%数据作为测试集，用来测试标准 Tri-training 分类算法和改进后的 Tri-training 分类算法的性能。然后，从剩余的 80%的数据集合中再抽 取 10%的数据作为训练集最初的基分类器，余下的 90%的数据集作为未标记的数据样例。 注意，在测试集，已标记数据集和未标记数据集中，每一个类别所占的比例应该与最初的数 据集保持一致。 - 3 -
    中国科技论文在线 2.2 实验结果及分析 http://www.paper.edu.cn 分别选取了朴素贝叶斯分类算法和 K 近邻法作为标准 Tri-training 的基分类器，选取这 两种算法的主要原因是相对于支持向量机分类算法，这两种算法虽然性能上略低于支持向量 机，但并不特别突出。但朴素贝叶斯分类算法和 K 近邻法分类的运行效率要远远高于支持 向量机，尤其是当进行 10 层交叉验证时，支持向量机效率特别低下。所以，本实验选取这 两种分类算法训练标准 Tri-training 基分类器。 标准的 Tri-training 分类算法和改进后加入自适应数据剪辑策略用三种不同的分类器的 Tri-training 分类算法分别在每个数据集中运行。对每个实验数据集试验后的结果分别绘制 在图 1，图 2 和图 3 中，其中图的横轴代表四个测试数据集而纵轴代表对每个数据集分类的 分类错误率，标准 Tri-TrainingKNN 代表使用 KNN 作为基分类器的标准的 Tri-training 分类 算法，而 Im-Tri-Training 代表改进后的 Tri-training 分类算法的分类性能。 1 0.9 0.8 0.7 0.6 Tri-trainingKNN i i n o s c e r P 0.5 Sick Diabetes Ionosphere Dataset Kv-Vs-Kp Austrilian 图 1 Tri-trainingKNN 分类性能 Fig. 1 Classification Performance of Tri-training KNN 图 1 代表了以 K 近邻法(KNN)作为基分类器时，利用 Tri-training 分类算法对从 UCI 机 器学习库中随机抽取的五六个数据集进行测试的结果，由于各个数据集数据分布情况不同， 因而即使采用相同的基分类器进行训练，得到的分类器的分类性能依然大不相同。从图 1 中可以看出，对于表 1 中列出的数据集进行测试，最好情况下分类准确率达到 90%以上， 而最坏情况下分类准确率只达到了 60%左右，因此对于半监督 Tri-training 分类算法在不同 的数据集产生的分类效果有较大的波动性。 1 0.9 0.8 0.7 0.6 i n o si c e r P Tri-trainingBN 0.5 Sick Diabetes Ionosphere Dataset Kv-Vs-Kp Austrilian 图 2 Tri-trainingBN 分类性能 Fig. 2 Classification Performance of Tri-trainingBN - 4 -
    中国科技论文在线 http://www.paper.edu.cn 图 2 代表了已朴素贝叶斯（Naive Bays）作为基分类器时，Tri-training 分类算法分类性 能，从该图中依然可以看到分类性能如图 1 一样，对于同一个分类器，在不同的数据集分类 性能也不尽相同，分类准确率也具有较大波动。 1 0.9 0.8 0.7 0.6 i n o si c e r P Im-Tri-training 0.5 Sick Diabetes Ionosphere Dataset Kv-Vs-Kp Austrilian 图 3 Im-Tri-training 分类性能 Fig. 3 Classification Performance of Im-Tri-training 图 3 代表了用 KNN，Naive Bays 和 SVM 作为三个不同的基分类器时，Tri-training 分 类算法分类性能，从该图中可以看到对于同一个分类器对于不同的数据集，其分类性能也不 尽相同，但总体上准确率较高。 1 0.9 0.8 0.7 0.6 n o si ci e r P Tri-trainingKNN Tri-trainingBN Im-Tri-training 0.5 Sick Diabetes Ionosphere Dataset Kv-Vs-Kp Austrilian 图 4 性能比较图 Fig. 4 Classification Comparison 将上述标准 Tri-training 半监督分类算法利用朴素贝叶斯分类和 k 近邻法分类做为基分 类器对表 1 中的数据集进行测试得到的分类性能同改进后的 Tri-training 半监督分类算法进 行实验后的分类性能做一致比较得到图 4 ，从图 4 可以看出,在表 1 中给出的五个数据集作 为训练集，测试集的情况下，利用改进后的 Tri-training 分类算法的分类性能要高于 Naive Bayesian 作为基分类器的分类性能，其主要原因是算法利用三个不同的基分类器 Naive Bayesian 以及支持向量机共同训练，通过投票的方式对数据进行标记，增加训练集的数。另 外，引入的自适应数据剪辑策略能更好的消除掉训练集中的噪声。此外，K 近邻和支持向量 机分类算法的分类性能都要略高于朴素贝叶斯算法的性能，因此利用这两种算法来协作朴素 贝叶斯算法做基分类器也提高了分类的准确率。改进后的算法相对于以 KNN 作为基分类器 的 Tri-training 算法比较，在多数数据集处，改进后的算法的性能高于改进前的性能，但在 少数数据集处，改进后的算法的性能反而不如改进前的性能，其主要原因在于：本实验中改 - 5 -
    中国科技论文在线 http://www.paper.edu.cn 进前 Tri-training 算法的基分类器采用 k 近邻法，而改进后的算法则采用了三个不同的基分 类器 Naive Bayesian ,KNN 以及支持向量机共同训练，通过实验知道，K 近邻算法的性能要 高于朴素贝叶斯而略低于支持向量机，因此对于改进后的算法利用三个分类器进行协作训练 的同时，其它两种分类算法朴素贝叶斯算法和支持向量机分类算法对于 K 近邻法有可能产 生负作用，即对于大多数数据 K 近邻法可以正确的进行分类而 Naive Bayesian 则有可能产生 更多的误标记数据。从而导致了分类性能的下降，在某些数据集中甚至不如改进前的算法的 性能。 3 结论 本文对对 Tri-training 算法进行了研究，通过对上述实验数据的研究和分析可以看出， 经过改进后的算法的分类准确率要明显高于传统的 Tri-training 分类性能。其主要原因在于 Zhou 提出的 Tri-training 分类算法的三个分类器采用同一种监督分类学习方法对不同的训练 集进行训练，训练的结果作为基分类器。由于使用同一种学习方法对数据进行训练，即使训 练集不同，得到的分类器对任意数据分类结果相同的概率要大于不同的概率。因此，本实验 中对 Tri-training 分类模型中的三个相同的分类器也进行了修改，运用三个不同的分类器来 提高算法的分类准确率，并引入自适应数据剪辑操作来消除数据噪声。然而改进后的算法仍 然有缺陷，既是在初始训练集较少的情况下，利用较少的训练集得到的性能有可能较低，因 而在分类的过程中有可能产生较多的误标记数据。怎样更好的消除噪声，这将是以后研究 Tri-training 算法的重点内容。 [参考文献] (References) [1] 王汪,周志华,傲英.机器学习及其应用[C].北京:清华大学出版社,2006,pp:32-58. [2] 王磊.支持向量机学习算法若干间题研究[M].西安:电子科技大学,2007,pp:9-106. [3] 周志华,王钰.机器学习及其应用[A].北京:清华大学出版,2007,pp:259-275. [4] Deng Chao,Guo Mao-zu. ADE-Tri-training: Tri-training with adaptive data editing [J].Chinese Journal of Computers, 2007:1213-1226. [5] A. Blum, T. Mitchell. Combining labeled and unlabeled data with co-training[M]. Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT’98), Wisconsin,MI, 1998, pp: 92-100. [6] M.Belkin, P.Niyogi and V.Sindhwani. On Manifold Regularization[D].AISTATS,2005. pp: 123-140 [7] Zhu, X. Semi-supervised learning literature survey[D]. Computer Sciences TR 1530. University of Wisconsin-Madison. 2006,pp:13-20 - 6 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料