机器学习：基于Tri-training的半监督多标记学习算法

第8卷第5期 智能系统学报 Vol.8 No.5 2013年10月 CAAI Transactions on Intelligent Systems 0ct.2013 D0L:10.3969/j.issn.1673-4785.201305033 网络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20130929.1105.006.html 基于Tri-training的半监督多标记学习算法 刘杨磊2，梁吉业2，高嘉伟2，杨静2 (1.山西大学计算机与信息技术学院，山西太原030006：2.山西大学计算智能与中文信息处理教育部重点实验室， 山西太原030006) 摘要：传统的多标记学习是监督意义下的学习，它要求获得完整的类别标记但是当数据规模较大且类别数目较多 时，获得完整类别标记的训练样本集是非常困难的.因而，在半监督协同训练思想的框架下，提出了基于Tmi-training 的半监督多标记学习算法(SMT).在学习阶段，SMLT引入一个虚拟类标记，然后针对每一对类别标记，利用协同训 练机制Ti-training算法训练得到对应的分类器：在预测阶段，给定一个新的样本，将其代入上述所得的分类器中，根 据类别标记得票数的多少将多标记学习问题转化为标记排序问题，并将虚拟类标记的得票数作为阈值对标记排序 结果进行划分.在UCI中4个常用的多标记数据集上的对比实验表明，SMLT算法在4个评价指标上的性能大多优于 其他对比算法，验证了该算法的有效性。 关键词：多标记学习：半监督学习：Tmi-training 中图分类号：TP181文献标志码：A文章编号：1673-4785(2013)05-439-07 中文引用格式：刘杨磊，梁吉业，高嘉伟，等.基于Ti-training的半监督多标记学习算法[J】.智能系统学报，2013,8(5)：439-445， 英文引用格式：LIU Yanglei,LIANG Jiye,GAO Jiawei,etal.Semi-supervised multi-.label learning algorithm based on Tri-training [J].CAAI Transactions on Intelligent Systems,2013,8(5):439-445. Semi-supervised multi-label learning algorithm based on Tri-training LIU Yanglei,LIANG Jiye2,GAO Jiawei',YANG Jing2 (1.School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China) Abstract:Traditional multi-label learning is in the sense of supervision,in which the complete category labels are required.However,when the size of data is large and there are several categories of labels,it is quite difficult to obtain the training sample sets with complete labels.Therefore,a semi-supervised multi-label learning algorithm based on Tri-training (SMLT)is proposed.In the learning stage,SMLT initially introduces a virtual label,then for each pair of virtual labels,the Tri-training algorithm is utilized to train the corresponding classifiers for each pair of labels.In the forecast stage,a new sample is given,which will be substituted into the obtained classifier described above.According to the votes of each label,the multi-label learning problem is transformed into a label ranking problem,subsequently;the votes of the virtual label are taken as the threshold for distinguishing the label ranking results.The contrast experiments on four commonly used UCI multi-label datasets show the SMLT algorithm behaves better than other comparative algorithms in four evaluation indices and the effectiveness of the proposed algorithm is verified. Keywords:multi-label learning;semi-supervised learning;Tri-training 多标记学习(muli--label learning)们是机器学习 个训练样本可能同时对应于一个或多个不同的概念 领域的重要研究方向之一.在多标记学习问题中，一 标记，以表达其语义信息，学习的任务是为待学习样 本预测其对应的概念标记集合.多标记学习问题普 收稿日期：2013-05-09.网络出版日期：2013-09-29 遍存在于真实世界中，比如在图像场景分类任务中， 基金项目：国家“973”计划前期研究专项(2011CB311805):山西省科 技攻关计划资助项目(20110321027-01)：山西省科技基础 一幅图像可能因包含“树木”、“天空”、“湖泊”以及 条件平台建设项目(2012091002-0101). 通信作者：梁吉业.E-mail:jy@sxu.cdu.cm “山峰”等语义概念，而拥有多个概念标记

第 ８ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．５ ２０１３ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０５０３３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３０９２９．１１０５．００６．ｈｔｍｌ 基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法 刘杨磊１，２ ，梁吉业１，２ ，高嘉伟１，２ ，杨静１，２ （１．山西大学 计算机与信息技术学院，山西 太原 ０３０００６； ２．山西大学 计算智能与中文信息处理教育部重点实验室， 山西 太原 ０３０００６） 摘 要：传统的多标记学习是监督意义下的学习，它要求获得完整的类别标记．但是当数据规模较大且类别数目较多 时，获得完整类别标记的训练样本集是非常困难的．因而，在半监督协同训练思想的框架下，提出了基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法（ＳＭＬＴ）．在学习阶段，ＳＭＬＴ 引入一个虚拟类标记，然后针对每一对类别标记，利用协同训 练机制 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法训练得到对应的分类器；在预测阶段，给定一个新的样本，将其代入上述所得的分类器中，根 据类别标记得票数的多少将多标记学习问题转化为标记排序问题，并将虚拟类标记的得票数作为阈值对标记排序 结果进行划分．在 ＵＣＩ 中 ４ 个常用的多标记数据集上的对比实验表明，ＳＭＬＴ 算法在 ４ 个评价指标上的性能大多优于 其他对比算法，验证了该算法的有效性． 关键词：多标记学习；半监督学习；Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０５⁃４３９⁃０７ 中文引用格式：刘杨磊，梁吉业，高嘉伟，等．基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法［Ｊ］． 智能系统学报， ２０１３， ８（５）： ４３９⁃４４５． 英文引用格式：ＬＩＵ Ｙａｎｇｌｅｉ， ＬＩＡＮＧ Ｊｉｙｅ， ＧＡＯ Ｊｉａｗｅｉ， ｅｔ ａｌ． Ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｔｒｉ⁃ｔｒａｉｎｉｎｇ ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（５）： ４３９⁃４４５． Ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｔｒｉ⁃ｔｒａｉｎｉｎｇ ＬＩＵ Ｙａｎｇｌｅｉ １，２ ， ＬＩＡＮＧ Ｊｉｙｅ １，２ ， ＧＡＯ Ｊｉａｗｅｉ １，２ ， ＹＡＮＧ Ｊｉｎｇ １，２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ； ２． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ｃｈｉｎｅｓｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ， Ｓｈａｎｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔａｉｙｕａｎ ０３０００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｒａｄｉｔｉｏｎａｌ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｉｓ ｉｎ ｔｈｅ ｓｅｎｓｅ ｏｆ ｓｕｐｅｒｖｉｓｉｏｎ， ｉｎ ｗｈｉｃｈ ｔｈｅ ｃｏｍｐｌｅｔｅ ｃａｔｅｇｏｒｙ ｌａｂｅｌｓ ａｒｅ ｒｅｑｕｉｒｅｄ． Ｈｏｗｅｖｅｒ， ｗｈｅｎ ｔｈｅ ｓｉｚｅ ｏｆ ｄａｔａ ｉｓ ｌａｒｇｅ ａｎｄ ｔｈｅｒｅ ａｒｅ ｓｅｖｅｒａｌ ｃａｔｅｇｏｒｉｅｓ ｏｆ ｌａｂｅｌｓ， ｉｔ ｉｓ ｑｕｉｔｅ ｄｉｆｆｉｃｕｌｔ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｔｒａｉｎｉｎｇ ｓａｍｐｌｅ ｓｅｔｓ ｗｉｔｈ ｃｏｍｐｌｅｔｅ ｌａｂｅｌｓ． Ｔｈｅｒｅｆｏｒｅ， ａ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｔｒｉ⁃ｔｒａｉｎｉｎｇ （ＳＭＬＴ） ｉｓ ｐｒｏｐｏｓｅｄ． Ｉｎ ｔｈｅ ｌｅａｒｎｉｎｇ ｓｔａｇｅ， ＳＭＬＴ ｉｎｉｔｉａｌｌｙ ｉｎｔｒｏｄｕｃｅｓ ａ ｖｉｒｔｕａｌ ｌａｂｅｌ， ｔｈｅｎ ｆｏｒ ｅａｃｈ ｐａｉｒ ｏｆ ｖｉｒｔｕａｌ ｌａｂｅｌｓ， ｔｈｅ Ｔｒｉ⁃ｔｒａｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｔｉｌｉｚｅｄ ｔｏ ｔｒａｉｎ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｃｌａｓｓｉｆｉｅｒｓ ｆｏｒ ｅａｃｈ ｐａｉｒ ｏｆ ｌａｂｅｌｓ． Ｉｎ ｔｈｅ ｆｏｒｅｃａｓｔ ｓｔａｇｅ， ａ ｎｅｗ ｓａｍｐｌｅ ｉｓ ｇｉｖｅｎ， ｗｈｉｃｈ ｗｉｌｌ ｂｅ ｓｕｂｓｔｉｔｕｔｅｄ ｉｎｔｏ ｔｈｅ ｏｂｔａｉｎｅｄ ｃｌａｓｓｉｆｉｅｒ ｄｅｓｃｒｉｂｅｄ ａｂｏｖｅ． Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｖｏｔｅｓ ｏｆ ｅａｃｈ ｌａｂｅｌ， ｔｈｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｐｒｏｂｌｅｍ ｉｓ ｔｒａｎｓｆｏｒｍｅｄ ｉｎｔｏ ａ ｌａｂｅｌ ｒａｎｋｉｎｇ ｐｒｏｂｌｅｍ， ｓｕｂｓｅｑｕｅｎｔｌｙ； ｔｈｅ ｖｏｔｅｓ ｏｆ ｔｈｅ ｖｉｒｔｕａｌ ｌａｂｅｌ ａｒｅ ｔａｋｅｎ ａｓ ｔｈｅ ｔｈｒｅｓｈｏｌｄ ｆｏｒ ｄｉｓｔｉｎｇｕｉｓｈｉｎｇ ｔｈｅ ｌａｂｅｌ ｒａｎｋｉｎｇ ｒｅｓｕｌｔｓ． Ｔｈｅ ｃｏｎｔｒａｓｔ ｅｘｐｅｒｉｍｅｎｔｓ ｏｎ ｆｏｕｒ ｃｏｍｍｏｎｌｙ ｕｓｅｄ ＵＣＩ ｍｕｌｔｉ⁃ｌａｂｅｌ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈｅ ＳＭＬＴ ａｌｇｏｒｉｔｈｍ ｂｅｈａｖｅｓ ｂｅｔｔｅｒ ｔｈａｎ ｏｔｈｅｒ ｃｏｍｐａｒａｔｉｖｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｆｏｕｒ ｅｖａｌｕａｔｉｏｎ ｉｎｄｉｃｅｓ ａｎｄ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ｖｅｒｉｆｉｅｄ． Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ； ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ； Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 收稿日期：２０１３⁃０５⁃０９． 网络出版日期：２０１３⁃０９⁃２９． 基金项目：国家“９７３”计划前期研究专项（２０１１ＣＢ３１１８０５）；山西省科 技攻关计划资助项目（ ２０１１０３２１０２７⁃０１）；山西省科技基础 条件平台建设项目（２０１２０９１００２⁃０１０１）． 通信作者：梁吉业． Ｅ⁃ｍａｉｌ： ｌｊｙ＠ ｓｘｕ．ｅｄｕ．ｃｎ． 多标记学习（ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ） ［１］是机器学习 领域的重要研究方向之一．在多标记学习问题中，一 个训练样本可能同时对应于一个或多个不同的概念 标记，以表达其语义信息，学习的任务是为待学习样 本预测其对应的概念标记集合．多标记学习问题普 遍存在于真实世界中，比如在图像场景分类任务中， 一幅图像可能因包含“树木”、“天空”、“湖泊”以及 “山峰”等语义概念，而拥有多个概念标记．

·440· 智能系统学报 第8卷 传统的多标记学习通常是在监督意义下进行 学习系统的泛化性能较低. 的，即要求训练数据集的训练样本必须全部是已标 2)“二阶”策略：考察两两标记之间的相关性， 记样本然而，在现实生活中，虽然获取大量的训练 将多标记学习问题转化成标记排序问题进行求解. 数据集并不十分困难，但是为这些数据提供正确的 该类方法在一定程度上考虑了标记之间的相关性， 类别标记却需要耗费大量的人力和时间.比如，在图 学习系统的泛化性能较好，但是当实际问题中标记 像场景分类任务中，现实世界中存在着海量的未标 之间具有超越二阶的相关性时，该类方法的性能将 记图像，而且一幅图像往往拥有大量的候选类别标 会受到很大影响. 记，要完整标注训练集中的每一个样本就意味着需 3)“高阶”策略：考察高阶的标记相关性，充分 要人工查看每一幅图像的所有候选类别并逐一标 利用标记之间的结构信息进行求解.该类方法可以 注.当数据规模较大且类别数目较多时，要获得完整 较好地反映真实世界问题的标记相关性，但其模型 类别标记的训练样本集是非常困难的.此时，在监督 复杂度较高，且在缺乏领域知识指导的情况下，几乎 意义下如果只使用少量已标记样本训练，则得到的 无法利用标记之间的结构信息. 模型很难具有较强的泛化能力.而半监督学习能够 另一方面，近几年来，多标记学习越来越受到机 较好地解决上述问题，它综合利用少量的已标记样 器学习领域学者的关注，研究人员对多标记学习问 本和大量的未标记样本以提高泛化性能[2) 题提出了许多学习方法和策略，对这些问题的研究 因此，本文主要以协同训练思想为核心，提出了 大致可分为2种思路：一种是问题转化，另一种是算 基于Tri-training的半监督多标记学习算法(a semi- 法改编第1种思路试图将多标记学习任务转化为 supervised multi-label learning algorithm based on Tri- 一个或多个单标记学习任务，然后利用已有的学习 training,SMLT),以解决广泛存在于实际生活中的 算法求解.代表性学习算法有一阶方法Binary Rele- 文本分类、图像场景分类以及生物信息学等半监督 vancets],它将多标记学习问题转化为二分类问题进 多标记学习问题. 行求解；二阶方法Calibrated Label Ranking将多标 1背景知识 记学习问题转化为标记排序问题求解：高阶方法 Random k-labelsets8]将多标记学习问题转化为多类 1.1多标记学习 分类问题求解.第2种思路是对现有算法进行改编 在多标记学习框架下，每个对象由一个样本描 或设计新算法，使之能直接处理多标记学习任务.代 述，该样本具有多个类别标记，学习的目的是将所有 表性学习算法有一阶方法ML-kNN),它将“惰性学 合适的类别标记赋予待学习样本〔)形式化地来说， 习”算法k近邻进行改造以适应多标记数据：二阶 令X表示样本空间，Y表示类别标记空间，给定数据 方法Rank-SVM10]将“核学习"算法SVM进行改造 集{(x1,Y),(x2,Y2),…,(xm,Ym)},目标是学得f: 用于多类别标记：高阶方法LEAD5]将“贝叶斯学 X→2'其中，x:∈X(i=1,2,…,m)为一个样本，YS 习”算法中的Bayes网络进行改造，以适应多标记 Y为x的一组类别标记{ya,ya,…,ym},y∈Y(j= 数据 1,2,…,n),n为Y:中所含类别标记的个数 上述的多标记学习算法通常为监督学习算法 如果限定每个样本只对应一个类别标记，那么 然而，为训练数据集提供正确的类别标记需要耗费 传统的2类或多类学习问题均可以看作是多标记学 大量的人力和时间因此，当只有少量已标记样本可 习问题的特例然而，多标记学习的一般性也使得其 用时，传统的多标记学习算法将不再适用 相较于传统的学习问题更加难以解决.目前，多标记 1.2半监督多标记学习 学习面临的最大挑战在于其输出空间过大，即与一 近来年，有一些研究者开始研究半监督/直推式 个待学习样本相关联的候选类别标记集合的数量将 多标记学习(semi-supervised/transductive multi-label 会随着标记空间的增大而呈指数规模增长.如何充 learning)方法.半监督学习和直推式学习都是试图 分利用标记之间的相关性是构造具有强泛化能力多 利用大量的未标记样本来辅助对少量已标记样本的 标记学习系统的关键.根据考察标记之间相关性的 学习，但二者的基本思想却有显著的不同直推式学 不同方式，已有的多标记学习问题求解策略大致可 习的测试样本是训练集中的未标记样本，测试环境 以分为以下3类) 是封闭的：而半监督学习的测试样本与训练样本无 1)“一阶”策略：将多标记学习问题分解为多个 关，测试环境是相对开放的， 独立的二分类问题进行求解.该类方法效率较高且 2006年，Liu等[基于如果样本之间具有很大 实现简单，但是由于忽略了标记之间的相关性，通常 的相似性，那么它们的标记集合之间也应该具有很

传统的多标记学习通常是在监督意义下进行 的，即要求训练数据集的训练样本必须全部是已标 记样本．然而，在现实生活中，虽然获取大量的训练 数据集并不十分困难，但是为这些数据提供正确的 类别标记却需要耗费大量的人力和时间．比如，在图 像场景分类任务中，现实世界中存在着海量的未标 记图像，而且一幅图像往往拥有大量的候选类别标 记，要完整标注训练集中的每一个样本就意味着需 要人工查看每一幅图像的所有候选类别并逐一标 注．当数据规模较大且类别数目较多时，要获得完整 类别标记的训练样本集是非常困难的．此时，在监督 意义下如果只使用少量已标记样本训练，则得到的 模型很难具有较强的泛化能力．而半监督学习能够 较好地解决上述问题，它综合利用少量的已标记样 本和大量的未标记样本以提高泛化性能［２⁃ ３］ ． 因此，本文主要以协同训练思想为核心，提出了 基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法（ ａ ｓｅｍｉ⁃ ｓｕｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｔｒｉ⁃ ｔｒａｉｎｉｎｇ， ＳＭＬＴ），以解决广泛存在于实际生活中的 文本分类、图像场景分类以及生物信息学等半监督 多标记学习问题． １ 背景知识 １．１ 多标记学习 在多标记学习框架下，每个对象由一个样本描 述，该样本具有多个类别标记，学习的目的是将所有 合适的类别标记赋予待学习样本［４］ ．形式化地来说， 令 Ｘ 表示样本空间，Ｙ 表示类别标记空间，给定数据 集｛（ｘ１ ，Ｙ１ ），（ｘ２ ，Ｙ２ ），…，（ｘｍ ，Ｙｍ ）｝，目标是学得 ｆ： Ｘ→２ Ｙ ．其中，ｘｉ∈Ｘ（ｉ ＝ １，２，…，ｍ）为一个样本，Ｙｉ⊆ Ｙ 为 ｘｉ 的一组类别标记｛ ｙｉ１ ，ｙｉ２ ，…，ｙｉｎ ｝，ｙｉｊ∈Ｙ（ ｊ ＝ １，２，…，ｎ），ｎ 为 Ｙｉ 中所含类别标记的个数． 如果限定每个样本只对应一个类别标记，那么 传统的 ２ 类或多类学习问题均可以看作是多标记学 习问题的特例．然而，多标记学习的一般性也使得其 相较于传统的学习问题更加难以解决．目前，多标记 学习面临的最大挑战在于其输出空间过大，即与一 个待学习样本相关联的候选类别标记集合的数量将 会随着标记空间的增大而呈指数规模增长．如何充 分利用标记之间的相关性是构造具有强泛化能力多 标记学习系统的关键．根据考察标记之间相关性的 不同方式，已有的多标记学习问题求解策略大致可 以分为以下 ３ 类［５］ ： １）“一阶”策略：将多标记学习问题分解为多个 独立的二分类问题进行求解．该类方法效率较高且 实现简单，但是由于忽略了标记之间的相关性，通常 学习系统的泛化性能较低． ２）“二阶”策略：考察两两标记之间的相关性， 将多标记学习问题转化成标记排序问题进行求解． 该类方法在一定程度上考虑了标记之间的相关性， 学习系统的泛化性能较好，但是当实际问题中标记 之间具有超越二阶的相关性时，该类方法的性能将 会受到很大影响． ３）“高阶”策略：考察高阶的标记相关性，充分 利用标记之间的结构信息进行求解．该类方法可以 较好地反映真实世界问题的标记相关性，但其模型 复杂度较高，且在缺乏领域知识指导的情况下，几乎 无法利用标记之间的结构信息． 另一方面，近几年来，多标记学习越来越受到机 器学习领域学者的关注，研究人员对多标记学习问 题提出了许多学习方法和策略，对这些问题的研究 大致可分为 ２ 种思路：一种是问题转化，另一种是算 法改编．第 １ 种思路试图将多标记学习任务转化为 一个或多个单标记学习任务，然后利用已有的学习 算法求解．代表性学习算法有一阶方法 Ｂｉｎａｒｙ Ｒｅｌｅ⁃ ｖａｎｃｅ ［６］ ，它将多标记学习问题转化为二分类问题进 行求解；二阶方法 Ｃａｌｉｂｒａｔｅｄ Ｌａｂｅｌ Ｒａｎｋｉｎｇ ［７］将多标 记学习问题转化为标记排序问题求解；高阶方法 Ｒａｎｄｏｍ ｋ⁃ｌａｂｅｌｓｅｔｓ ［８］将多标记学习问题转化为多类 分类问题求解．第 ２ 种思路是对现有算法进行改编 或设计新算法，使之能直接处理多标记学习任务．代 表性学习算法有一阶方法 ＭＬ⁃ｋＮＮ ［９］ ，它将“惰性学 习”算法 ｋ 近邻进行改造以适应多标记数据；二阶 方法 Ｒａｎｋ⁃ＳＶＭ ［１０］ 将“核学习”算法 ＳＶＭ 进行改造 用于多类别标记；高阶方法 ＬＥＡＤ ［５ ］ 将“贝叶斯学 习”算法中的 Ｂａｙｅｓ 网络进行改造，以适应多标记 数据． 上述的多标记学习算法通常为监督学习算法． 然而，为训练数据集提供正确的类别标记需要耗费 大量的人力和时间．因此，当只有少量已标记样本可 用时，传统的多标记学习算法将不再适用． １．２ 半监督多标记学习 近来年，有一些研究者开始研究半监督／ 直推式 多标记学习（ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ／ ｔｒａｎｓｄｕｃｔｉｖｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ）方法．半监督学习和直推式学习都是试图 利用大量的未标记样本来辅助对少量已标记样本的 学习，但二者的基本思想却有显著的不同．直推式学 习的测试样本是训练集中的未标记样本，测试环境 是封闭的；而半监督学习的测试样本与训练样本无 关，测试环境是相对开放的． ２００６ 年，Ｌｉｕ 等［１１ ］基于如果样本之间具有很大 的相似性，那么它们的标记集合之间也应该具有很 ·４４０· 智 能 系 统 学 报 第 ８ 卷

第5期 刘杨磊，等：基于Ti-training的半监督多标记学习算法 441. 大的相似性这样的假设，提出了CNMF(constrained 督多标记学习 non-negative matrix factorization)方法，通过解一个带 2 约束的非负矩阵分解问题，期望使得这2种相似性 基于Tri-training的半监督多标记学 差值最小，从而获得最优的对未标记样本的标记 习算法 2008年，姜远等2]提出了基于随机游走(random 下面提出一种基于Ti-training的半监督多标记 wak)的直推式多标记学习算法TML,并将其用于文 学习算法，该算法考察两两标记之间的相关性，将多 本分类.同年，Chen等1基于样本相似性度量与标 标记学习问题转化为标记排序问题进行求解：因此 记相似性度量构建图，提出了SMSE(semi-supervised 在一定程度上考虑了标记之间的相关性，并采用半 algorithm for multi-label learning by solving a Sylvester 监督学习中的协同训练思想，利用Tri-training过程 equation)方法，采用标记传播的思想对未标记样本 来训练分类器」 的标记进行学习，整个优化问题可采用Sylvester方 本文中相关量的定义如下：L={(x,Y:),i=1, 程进行快速求解.2010年，Sun等4]和周志华等[5] 2,…,m}是包含m个样本的已标记样本集.其中，x 考虑多标记学习中的弱标记问题，即训练样本对应 表示第i个样本的属性集合；Y={ya,y2,…,ym}表 的标记集合中只有一小部分得到了标记，或者根本 示样本x:对应的包含n个标记的类别标记集合，且 没有任何的标记，分别提出了WELL(weak label y∈{0,1}，j=1,2,…,n,若y=1,则表示第j个标 learning）方法和TML-WL(transductive multi-label 记是当前样本x:的真实标记，否则y=0.U={x, learning method for weak labeling)方法，他们同样采 k=1,2,…,t}是包含t个样本的未标记样本集.LUU 用标记传播的思想对缺失标记进行学习.2013年，周 是包含m+t个样本的训练集.为了验证所提分类算 志华等6]还采用标记传播的思想，首先将学习任务 法的有效性，构建的T={x”,s=1,2,…,0}是包含0 看作是一个对标记集合进行估计的优化问题，然后 个样本的测试集.数组R(s=1,2,…,0,j=1,2,…, 为这个优化问题找到一个封闭解，提出的TRAM算 n)用于存放测试集T中样本x"在第j类标记上的得 法为未标记样本分配其对应的标记集合.以上方法 票数 都是直推式方法，这类方法不能自然地对除测试样 为了对后续过程中产生的标记排序结果进行分 本以外的未见样本进行预测.2012年，周志华等[] 析，并得到最终的预测标记集合，需要设置一个阈值 在传统经验风险最小化原理基础上，引入2种正则 来划分上述标记排序结果因此，在算法的预处理阶 项分别用于约束分类器的复杂度和相似样本拥有相 段，为每一个训练样本x:添加一个虚拟标记y0,把 似结构化的多标记输出，针对归纳式半监督多标记 虚拟类标记的得票数作为阈值对标记排序结果进行 学习，提出了一种正则化方法MAss(multi-label 划分.此时，涉及到标记的下标应从0开始 semi-supervised learning). SMLT算法的基本思想是：首先，为已标记样本 l.3Ti-training算法 集L中的每一个样本x:添加一个虚拟标记y0,然后 从20世纪90年代末标准协同训练算法被提出 考虑两两标记之间的相关性，对L中每一对标记 开始，很多研究者对协同训练技术进行了研究，不仅 (ypyg)(0≤pR(=1, 条件.而Ti-training算法[19]是周志华等在2005年 2,…,n),则样本x,"的最后标记y”=1,否则y=0,即 提出的一种新的协同训练方法，它使用3个分类器 可得到一组测试集样本的预测结果Y 进行训练.在学习过程中，Tri-training算法采用集成 SMLT算法的流程如图1所示.SMLT算法的详 学习中经常用到的投票法，使用3个分类器对未见 细步骤如下 样本进行预测。 输入：已标记样本集L,未标记样本集U,测试 由于Ti-training对属性集和3个分类器所用监 集T 督学习算法都没有约束，而且不使用交叉验证，其适 输出：对测试集T的预测结果Y" 用范围更广、效率更高，因此本文以协同训练思想为 1)初始化R,=0(s=1,2,…,0,j=0,1,…,n)和 核心，利用Ti-training算法训练分类器，来研究半监 用于存放训练样本的集合Vm=☑(0≤p<q≤n)

大的相似性这样的假设，提出了 ＣＮＭＦ（ ｃｏｎｓｔｒａｉｎｅｄ ｎｏｎ⁃ｎｅｇａｔｉｖｅ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ）方法，通过解一个带 约束的非负矩阵分解问题，期望使得这 ２ 种相似性 差值最小，从而获得最优的对未标记样本的标记． ２００８ 年，姜远等［１２ ］ 提出了基于随机游走（ ｒａｎｄｏｍ ｗａｌｋ）的直推式多标记学习算法 ＴＭＬ，并将其用于文 本分类．同年，Ｃｈｅｎ 等［１３ ］ 基于样本相似性度量与标 记相似性度量构建图，提出了 ＳＭＳＥ（ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｂｙ ｓｏｌｖｉｎｇ ａ Ｓｙｌｖｅｓｔｅｒ ｅｑｕａｔｉｏｎ）方法，采用标记传播的思想对未标记样本 的标记进行学习，整个优化问题可采用 Ｓｙｌｖｅｓｔｅｒ 方 程进行快速求解．２０１０ 年，Ｓｕｎ 等［１４ ］ 和周志华等［１５ ］ 考虑多标记学习中的弱标记问题，即训练样本对应 的标记集合中只有一小部分得到了标记，或者根本 没有任何的标记， 分别提出了 ＷＥＬＬ （ ｗｅａｋ ｌａｂｅｌ ｌｅａｒｎｉｎｇ） 方 法 和 ＴＭＬ⁃ＷＬ （ ｔｒａｎｓｄｕｃｔｉｖｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｍｅｔｈｏｄ ｆｏｒ ｗｅａｋ ｌａｂｅｌｉｎｇ）方法，他们同样采 用标记传播的思想对缺失标记进行学习．２０１３ 年，周 志华等［１６ ］还采用标记传播的思想，首先将学习任务 看作是一个对标记集合进行估计的优化问题，然后 为这个优化问题找到一个封闭解，提出的 ＴＲＡＭ 算 法为未标记样本分配其对应的标记集合．以上方法 都是直推式方法，这类方法不能自然地对除测试样 本以外的未见样本进行预测．２０１２ 年，周志华等［１７ ］ 在传统经验风险最小化原理基础上，引入 ２ 种正则 项分别用于约束分类器的复杂度和相似样本拥有相 似结构化的多标记输出，针对归纳式半监督多标记 学习， 提出了一种正则化方法 ＭＡＳＳ （ ｍｕｌｔｉ⁃ｌａｂｅｌ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ）． １．３ Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法 从 ２０ 世纪 ９０ 年代末标准协同训练算法被提出 开始，很多研究者对协同训练技术进行了研究，不仅 提出了很多学习方式不同、限制条件强弱各异的算 法，而且对协同训练的理论分析和应用研究也取得 了不少进展，使得协同训练成为半监督学习中重要 的研究方向之一［１８ ］ ． 初期的协同训练算法引入了很多的限制和约束 条件．而 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法［ １９ ］ 是周志华等在 ２００５ 年 提出的一种新的协同训练方法，它使用 ３ 个分类器 进行训练．在学习过程中，Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法采用集成 学习中经常用到的投票法，使用 ３ 个分类器对未见 样本进行预测． 由于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 对属性集和 ３ 个分类器所用监 督学习算法都没有约束，而且不使用交叉验证，其适 用范围更广、效率更高，因此本文以协同训练思想为 核心，利用 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法训练分类器，来研究半监 督多标记学习． ２ 基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学 习算法 下面提出一种基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记 学习算法，该算法考察两两标记之间的相关性，将多 标记学习问题转化为标记排序问题进行求解；因此 在一定程度上考虑了标记之间的相关性，并采用半 监督学习中的协同训练思想，利用 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 过程 来训练分类器． 本文中相关量的定义如下：Ｌ ＝ ｛（ ｘｉ，Ｙｉ ），ｉ ＝ １， ２，…，ｍ｝是包含 ｍ 个样本的已标记样本集．其中，ｘｉ 表示第 ｉ 个样本的属性集合；Ｙｉ ＝ ｛ ｙｉ１ ，ｙｉ２ ，…，ｙｉｎ ｝表 示样本 ｘｉ 对应的包含 ｎ 个标记的类别标记集合，且 ｙｉｊ∈｛０，１｝，ｊ ＝ １，２，…，ｎ，若 ｙｉｊ ＝ １，则表示第 ｊ 个标 记是当前样本 ｘｉ 的真实标记，否则 ｙｉｊ ＝ ０．Ｕ ＝ ｛ ｘｋ ′， ｋ ＝ １，２，…，ｔ｝是包含 ｔ 个样本的未标记样本集．Ｌ∪Ｕ 是包含 ｍ＋ｔ 个样本的训练集．为了验证所提分类算 法的有效性，构建的 Ｔ ＝ ｛ｘｓ ″，ｓ ＝ １，２，…，ｗ｝是包含 ｗ 个样本的测试集．数组 Ｒｓｊ（ ｓ ＝ １，２，…，ｗ，ｊ ＝ １，２，…， ｎ）用于存放测试集 Ｔ 中样本 ｘｓ ″在第 ｊ 类标记上的得 票数． 为了对后续过程中产生的标记排序结果进行分 析，并得到最终的预测标记集合，需要设置一个阈值 来划分上述标记排序结果．因此，在算法的预处理阶 段，为每一个训练样本 ｘｉ 添加一个虚拟标记 ｙｉ０ ，把 虚拟类标记的得票数作为阈值对标记排序结果进行 划分．此时，涉及到标记的下标应从 ０ 开始． ＳＭＬＴ 算法的基本思想是：首先，为已标记样本 集 Ｌ 中的每一个样本 ｘｉ 添加一个虚拟标记 ｙｉ０ ，然后 考虑两两标记之间的相关性，对 Ｌ 中每一对标记 （ｙ∗ｐ，ｙ∗ｑ）（０≤ｐ＜ｑ≤ｎ）进行训练，并利用 Ｔｒｉ⁃ｔｒａｉｎ⁃ ｉｎｇ 过程学习得到相应的 ３ 个分类器．对一个新的测 试样本，用学习到的分类器对相应的每一对标记进 行预测，并统计每个标记所得的票数 Ｒｓｊ，得到该测 试样本的一个标记排序结果．最后以虚拟标记 ｙｓ０ ″的 得票数 Ｒｓ０作为确定类标记的依据，若 Ｒｓｊ ＞Ｒｓ０（ｊ ＝ １， ２，…，ｎ），则样本 ｘｓ ″的最后标记 ｙｓｊ ″＝ １，否则 ｙｓｊ ″＝ ０，即 可得到一组测试集样本的预测结果 Ｙ″． ＳＭＬＴ 算法的流程如图 １ 所示．ＳＭＬＴ 算法的详 细步骤如下． 输入：已标记样本集 Ｌ，未标记样本集 Ｕ，测试 集 Ｔ． 输出：对测试集 Ｔ 的预测结果 Ｙ″． １）初始化 Ｒｓｊ ＝ ０（ｓ ＝ １，２，…，ｗ，ｊ ＝ ０，１，…，ｎ）和 用于存放训练样本的集合 Ｖｐｑ ＝∅（０≤ｐ＜ｑ≤ｎ）． 第 ５ 期 刘杨磊，等：基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法 ·４４１·

·442. 智能系统学报 第8卷 2)预处理已标记样本集L对于任一对未处理 6)对于测试集T中的未标记样本x”,若R> 的标记(ypyg),遍历x∈L,将满足以下规则的x Ro(=1,2,…,n),则样本x"的最后标记y”=1,否则 放入集合Vm中若y=1,y=0则样本(x,1)放入 y,=0,最终输出预测标记集合"={y”,s=1,2, 集合V中：若yp=0,y=1则将样本(x,0)放人集 …,10}. 合V中；若y=yn则不考虑样本x:,即样本x:不放 3 实验结果及分析 入集合V中. 3)将集合V作为新的已标记样本集L",结合 本文在emotions、scene、yeast、enron这4个较为 未标记样本集U,在训练集中利用Tri-training算法 常用的多标记数据集[2]上与多标记学习的多种典 学习得到3个分类器. 型方法进行实验比较，其中包括ML-kNN[)、RANK- 4)使用投票法和得到的3个分类器对测试集T SVML10]以及TRAM6].实验数据集的相关信息如表 中的未标记样本(s=1,2,…,)进行预测，得到预 1所示. 测结果，并统计对应的标记投票个数若，=1则 表1实验数据集相关信息 表示样本x属于第p类标记，Rm=R,+1;若T=0 Table 1 The characteristics of datasets 则表示样本x"属于第q类标记，R=R+1. 数据集名称 所属领域样本个数属性个数类标记个数 5)将标记(y,y)设置为已处理，若还有未 处理的标记对，则转步骤2)，否则下一步. emotions music 593 72 6 scene image 2407 294 6 (开始 yeast biology 2417 103 14 输入数据集 L、U和7 enron text 1702 1001 53 为L中每个样本添加 实验采用4种常用的多标记学习评价指标4) 一个虚拟标记 对算法性能进行评估：Hamming Loss、One-Emor、 Coverage和Ranking Loss.以上4种评估指标的值越 针对一对未处理过的标记 小，表明该算法的性能越好 对，预处理L,得到Lnew 实验将抽取各数据集的90%作为训练样本集 根据Lew,结合U, (其中20%的训练样本是已标记样本集，80%的训 利用Tri-training得到 练样本是未标记样本集)，其余10%的数据为测试 3个分类器 样本集，重复10次统计其平均结果.由于TRAM方 对测试集样本进行预测 法是直推式方法，不能直接对测试样本集以外的未 并统计投票结果 见样本进行预测，实验中将最终测试样本作为 TRAM训练时的未标记样本集.表2~5给出了实验 结果，加粗部分为每个指标上的最佳性能。 是否有未处理 的标记对 表2数据集emotions上各算法的实验结果 Table 2 The summary results of four algorithms on emo- N tions dataset 根据投票结果 获取最后标记Y Hamming Ranking t 算法 One-Error Coverage Loss Loss 输出预测标 记集合Y MLkNN 0.2571 0.4068 2.2034 0.2399 RankSVM 0.2797 0.4237 2.2373 0.2781 结束) TRAM 0.2768 0.3390 2.1525 0.2321 图1SMLT算法 SMLT 0.2420 0.3139 1.7970 0.1845 Fig.1 Flow chart of the SMLT algorithm

２）预处理已标记样本集 Ｌ．对于任一对未处理 的标记（ｙ∗ｐ，ｙ∗ｑ），遍历 ｘｉ∈Ｌ，将满足以下规则的 ｘｉ 放入集合 Ｖｐｑ中．若 ｙｉｐ ＝ １，ｙｉｑ ＝ ０ 则样本（ ｘｉ，１）放入 集合 Ｖｐｑ中；若 ｙｉｐ ＝ ０，ｙｉｑ ＝ １ 则将样本（ ｘｉ，０）放入集 合 Ｖｐｑ中；若 ｙｉｐ ＝ ｙｉｑ则不考虑样本 ｘｉ，即样本 ｘｉ 不放 入集合 Ｖｐｑ中． ３）将集合 Ｖｐｑ作为新的已标记样本集 Ｌ ｎｅｗ ，结合 未标记样本集 Ｕ，在训练集中利用 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法 学习得到 ３ 个分类器． ４）使用投票法和得到的 ３ 个分类器对测试集 Ｔ 中的未标记样本 ｘｓ ″（ｓ ＝ １，２，…，ｗ）进行预测，得到预 测结果 ｒｓｐｑ并统计对应的标记投票个数．若 ｒｓｐｑ ＝ １ 则 表示样本 ｘｓ ″属于第 ｐ 类标记，Ｒｓｐ ＝ Ｒｓｐ ＋１；若 ｒｓｐｑ ＝ ０ 则表示样本 ｘｓ ″属于第 ｑ 类标记，Ｒｓｑ ＝Ｒｓｑ ＋１． 图 １ ＳＭＬＴ 算法 Ｆｉｇ．１ Ｆｌｏｗ ｃｈａｒｔ ｏｆ ｔｈｅ ＳＭＬＴ ａｌｇｏｒｉｔｈｍ ５）将标记（ ｙ∗ｐ，ｙ∗ｑ ） 设置为已处理，若还有未 处理的标记对，则转步骤 ２），否则下一步． ６）对于测试集 Ｔ 中的未标记样本 ｘｓ ″，若 Ｒｓｊ ＞ Ｒｓ０（ｊ ＝ １，２，…，ｎ），则样本 ｘｓ ″的最后标记 ｙｓｊ ″＝ １，否则 ｙｓｊ ″＝ ０，最终输出预测标记集合 Ｙ″ ＝ ｛ Ｙｓ ″， ｓ ＝ １，２， …，ｗ｝． ３ 实验结果及分析 本文在 ｅｍｏｔｉｏｎｓ、ｓｃｅｎｅ、ｙｅａｓｔ、ｅｎｒｏｎ 这 ４ 个较为 常用的多标记数据集［２０ ］ 上与多标记学习的多种典 型方法进行实验比较，其中包括 ＭＬ⁃ｋＮＮ ［９］ 、ＲＡＮＫ⁃ ＳＶＭ ［１０］以及 ＴＲＡＭ ［１６ ］ ．实验数据集的相关信息如表 １ 所示． 表 １ 实验数据集相关信息 Ｔａｂｌｅ １ Ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｄａｔａｓｅｔｓ 数据集名称 所属领域 样本个数 属性个数 类标记个数 ｅｍｏｔｉｏｎｓ ｍｕｓｉｃ ５９３ ７２ ６ ｓｃｅｎｅ ｉｍａｇｅ ２ ４０７ ２９４ ６ ｙｅａｓｔ ｂｉｏｌｏｇｙ ２ ４１７ １０３ １４ ｅｎｒｏｎ ｔｅｘｔ １ ７０２ １ ００１ ５３ 实验采用 ４ 种常用的多标记学习评价指标［４］ 对算 法 性 能 进 行 评 估： Ｈａｍｍｉｎｇ Ｌｏｓｓ、 Ｏｎｅ⁃Ｅｒｒｏｒ、 Ｃｏｖｅｒａｇｅ 和 Ｒａｎｋｉｎｇ Ｌｏｓｓ．以上 ４ 种评估指标的值越 小，表明该算法的性能越好［４］ ． 实验将抽取各数据集的 ９０％作为训练样本集 （其中 ２０％的训练样本是已标记样本集，８０％的训 练样本是未标记样本集），其余 １０％的数据为测试 样本集，重复 １０ 次统计其平均结果．由于 ＴＲＡＭ 方 法是直推式方法，不能直接对测试样本集以外的未 见样本 进 行 预 测， 实 验 中 将 最 终 测 试 样 本 作 为 ＴＲＡＭ 训练时的未标记样本集．表 ２ ～ ５ 给出了实验 结果，加粗部分为每个指标上的最佳性能． 表 ２ 数据集 ｅｍｏｔｉｏｎｓ 上各算法的实验结果 Ｔａｂｌｅ ２ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｅｍｏ⁃ ｔｉｏｎｓ ｄａｔａｓｅｔ 算法 Ｈａｍｍｉｎｇ Ｌｏｓｓ Ｏｎｅ⁃Ｅｒｒｏｒ Ｃｏｖｅｒａｇｅ Ｒａｎｋｉｎｇ Ｌｏｓｓ ＭＬｋＮＮ ０．２５７ １ ０．４０６ ８ ２．２０３ ４ ０．２３９ ９ ＲａｎｋＳＶＭ ０．２７９ ７ ０．４２３ ７ ２．２３７ ３ ０．２７８ １ ＴＲＡＭ ０．２７６ ８ ０．３３９ ０ ２．１５２ ５ ０．２３２ １ ＳＭＬＴ ０．２４２ ０ ０．３１３ ９ １．７９７ ０ ０．１８４ ５ ·４４２· 智 能 系 统 学 报 第 ８ 卷

第5期 刘杨磊，等：基于Ti-training的半监督多标记学习算法 .443. 表3数据集scene上各算法的实验结果 息，更能提高分类算法的性能。 Table 3 The summary results of four algorithms on scene 为了进一步验证已标记样本集的规模对SMLT dataset 算法的影响，在4个数据集上分别进行实验.训练样 Hamming One- Ranking 本集和测试样本集的构成方法与上文实验相同，但 算法 Coverage Loss Error Loss 是已标记样本集占训练数据集的比例依次调整为 10%、20%、30%、40%和50%时，SMLT算法在4项 MLkNN 0.0989 0.2531 0.5602 0.0955 评估指标上的取值与已标记样本集比例的关系如图 RankSVM 0.1127 0.2324 0.4730 0.0768 2~5所示 TRAM 0.1010 0.2697 0.5104 0.0854 0.38 0.28 0.36 SMLT 0.1141 0.2178 0.4596 0.0771 0.26 兽02 表4数据集yeast上各算法的实验结果 0.30 0.22 Table 4 The summary results of four algorithms on yeast .10.20.30.40.5 02810.203040.5 dataset 已标记样本集比例 已标记样本集比例 (a)Hamming Loss (b)One-Error Hamming One- 算法 Ranking Coverage Loss Error L088 2.1 0.24 MLkNN 0.2043 0.2356 6.4256 0.1733 1.9 0.20 1.8 RankSVM 0.2084 0.2190 6.3884 0.1778 1> 1.6 0.16 TRAM 0.2214 0.33476.5000 0.1879 0.10.20.30.4 0.5 .10.2 0.30.40.5 已标记样本集比例 已标记样本集比例 SMLT 0.2105 0.2172 6.31680.1681 (c)Coverage (d)Ranking Loss 图2数据集emotions在4项评估指标上的实验结果 表5数据集enron上各算法的实验结果 Fig.2 The summary results of four evaluation metrics Table 5 The summary results of four algorithms on enron on emotions dataset dataset One- 算法 Hamming Ranking Coverage 0.130 0.29m Loss Error Loss sso 0.125 0.27 MLkNN 0.0587 0.3706 15.3000 0.1048 月02 RankSVM 0.0747 0.3559 14.0659 0.0996 0.2 0.1 0.20.30.40.5 0.10.20.30.40.5 TRAM 0.0533 0.2412 13.8529 0.0875 已标记样本集比例 已标记样本集比伤例 (a)Hamming Loss (b)One-Error SMLT 0.0488 0.1647 13.6528 0.0857 0.60 0.11r 0.55 0.10 通过分析表2~5，在emotions和enron这2个数 0.50 0.09 据集上，提出的算法SMLT在4个评估指标上都优 于其他算法，而在scene数据集上有2个评估指标 0.4510203040 0.0 0.10.20.30.40.5 优于其他算法，但在Hamming Loss和Ranking loss 已标记样本集比例 已标记样本集比例 上略差于其他算法，在yeast数据集上有3个评估指 (c)Coverage (d)Ranking Loss 标优于其他算法，仅在Hamming Loss上略差于其他 图3数据集scene在4项评估指标上的实验结果 算法可能的原因是本文提出的算法充分利用了已 Fig.3 The summary results of four evaluation metrics 标记样本集和未标记样本集的信息，这要比不利用 on scene dataset 已标记样本集或者单纯只利用已标记样本集的信

表 ３ 数据集 ｓｃｅｎｅ 上各算法的实验结果 Ｔａｂｌｅ ３ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｓｃｅｎｅ ｄａｔａｓｅｔ 算法 Ｈａｍｍｉｎｇ Ｌｏｓｓ Ｏｎｅ⁃ Ｅｒｒｏｒ Ｃｏｖｅｒａｇｅ Ｒａｎｋｉｎｇ Ｌｏｓｓ ＭＬｋＮＮ ０．０９８ ９ ０．２５３ １ ０．５６０ ２ ０．０９５ ５ ＲａｎｋＳＶＭ ０．１１２ ７ ０．２３２ ４ ０．４７３ ０ ０．０７６ ８ ＴＲＡＭ ０．１０１ ０ ０．２６９ ７ ０．５１０ ４ ０．０８５ ４ ＳＭＬＴ ０．１１４ １ ０．２１７ ８ ０．４５９ ６ ０．０７７ １ 表 ４ 数据集 ｙｅａｓｔ 上各算法的实验结果 Ｔａｂｌｅ ４ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｙｅａｓｔ ｄａｔａｓｅｔ 算法 Ｈａｍｍｉｎｇ Ｌｏｓｓ Ｏｎｅ⁃ Ｅｒｒｏｒ Ｃｏｖｅｒａｇｅ Ｒａｎｋｉｎｇ Ｌｏｓｓ ＭＬｋＮＮ ０．２０４ ３ ０．２３５ ６ ６．４２５ ６ ０．１７３ ３ ＲａｎｋＳＶＭ ０．２０８ ４ ０．２１９ ０ ６．３８８ ４ ０．１７７ ８ ＴＲＡＭ ０．２２１ ４ ０．３３４ ７ ６．５００ ０ ０．１８７ ９ ＳＭＬＴ ０．２１０ ５ ０．２１７ ２ ６．３１６ ８ ０．１６８ １ 表 ５ 数据集 ｅｎｒｏｎ 上各算法的实验结果 Ｔａｂｌｅ ５ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｅｎｒｏｎ ｄａｔａｓｅｔ 算法 Ｈａｍｍｉｎｇ Ｌｏｓｓ Ｏｎｅ⁃ Ｅｒｒｏｒ Ｃｏｖｅｒａｇｅ Ｒａｎｋｉｎｇ Ｌｏｓｓ ＭＬｋＮＮ ０．０５８ ７ ０．３７０ ６ １５．３００ ０ ０．１０４ ８ ＲａｎｋＳＶＭ ０．０７４ ７ ０．３５５ ９ １４．０６５ ９ ０．０９９ ６ ＴＲＡＭ ０．０５３ ３ ０．２４１ ２ １３．８５２ ９ ０．０８７ ５ ＳＭＬＴ ０．０４８ ８ ０．１６４ ７ １３．６５２ ８ ０．０８５ ７ 通过分析表 ２～５，在 ｅｍｏｔｉｏｎｓ 和 ｅｎｒｏｎ 这 ２ 个数 据集上，提出的算法 ＳＭＬＴ 在 ４ 个评估指标上都优 于其他算法，而在 ｓｃｅｎｅ 数据集上有 ２ 个评估指标 优于其他算法，但在 Ｈａｍｍｉｎｇ Ｌｏｓｓ 和 Ｒａｎｋｉｎｇ ｌｏｓｓ 上略差于其他算法，在 ｙｅａｓｔ 数据集上有 ３ 个评估指 标优于其他算法，仅在 Ｈａｍｍｉｎｇ Ｌｏｓｓ 上略差于其他 算法．可能的原因是本文提出的算法充分利用了已 标记样本集和未标记样本集的信息，这要比不利用 已标记样本集或者单纯只利用已标记样本集的信 息，更能提高分类算法的性能． 为了进一步验证已标记样本集的规模对 ＳＭＬＴ 算法的影响，在 ４ 个数据集上分别进行实验．训练样 本集和测试样本集的构成方法与上文实验相同，但 是已标记样本集占训练数据集的比例依次调整为 １０％、２０％、３０％、４０％和 ５０％时，ＳＭＬＴ 算法在 ４ 项 评估指标上的取值与已标记样本集比例的关系如图 ２～５ 所示． 图 ２ 数据集 ｅｍｏｔｉｏｎｓ 在 ４ 项评估指标上的实验结果 Ｆｉｇ．２ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ｅｖａｌｕａｔｉｏｎ ｍｅｔｒｉｃｓ ｏｎ ｅｍｏｔｉｏｎｓ ｄａｔａｓｅｔ 图 ３ 数据集 ｓｃｅｎｅ 在 ４ 项评估指标上的实验结果 Ｆｉｇ．３ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ｅｖａｌｕａｔｉｏｎ ｍｅｔｒｉｃｓ ｏｎ ｓｃｅｎｅ ｄａｔａｓｅｔ 第 ５ 期 刘杨磊，等：基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法 ·４４３·

·444. 智能系统学报 第8卷 记样本集比例增加到一定程度时，监督信息不再是 0.222 0.225 o218i 影响分类性能的主要因素， 4结束语 写0.210 里0206 021s 本文针对广泛存在于实际生活中的半监督多标 0.202 0.210 .1 0.20.3 0.40.5 0.10.20.30.40.5 记学习问题，以协同训练思想为核心，以两两标记之 已标记样本集比例 已标记样本集比例 间的关系为出发点，利用Tri-training算法训练分类 (a)Hamming Loss (b)One-Eror 器，并将多标记学习问题转化为标记排序问题进行 2.78 0.178 求解，实验结果表明了该算法的有效性.但是，当多 标记的数量和规模较大时，如何进一步降低算法的 计算复杂度仍将是需要深入讨论的问题. 2.70 号0.166 参考文献： 2.66 0162 .1 0.20.30.40.5 .10.20.30.40.5 [1]TSOUMAKAS G,KATAKIS I.Multi-label classification:an 已标记样本集比例 已标记样本集比例 overview[]].International Journal of Data Warehousing and (c)Coverage (d)Ranking Loss Mining,2007,3(3):1-l3, [2]ZHU Xiaojin.Semi-supervised learning literature survey 图4数据集yeast在4项评估指标上的实验结果 [R].Madison,USA:University of Wisconsin-Madison, Fig.4 The summary results of four evaluation metrics 2008. on yeast dataset 「31常瑜，梁吉业，高嘉伟，等.一种基于Seeds集和成对约束 的半监督聚类算法[J].南京大学学报：自然科学版 0.057 0.24 2012,48(4):405-411. 0.055 CHANG Yu,LIANG Jiye,GAO Jiawei,et al.A semi-su- 0.053 0.20 pervised clustering algorithm based on seeds and pair wise 0.051 号o constraints[J].Journal of Nanjing University:Natural Sci- 0.049 0.16 ences.2012.48(4):405-411. .10.2 0.30.40.5 0.10.20.30.40.5 [4]ZHOU Zhihua,ZHANG Minling,HUANG Shengjun,et al. 已标记样本集比例 已标记样本集比例 Multi-instance multi-label learning J].Artificial Intelli- (a)Hamming Loss (b)One-Error gence,2012,176(1):2291-2320. 1.62 Q094 [5]ZHANG Minling,ZHANG Kun.Multi-label learing by ex- 1.60 1.58 0.090 ploiting label dependency C]//Proceedings of the 16th 1.56 ACM SIGKDD International Conference on Knowledge Dis- 1.54 1.52 covery and Data Mining.Washington,DC,USA,2010: 1.50 999-1007. 1.4 0.07 0.10.20.30.40.5 0.10.20.30.40.5 [6]BOUTELL M R,LUO Jiebo,SHEN Xipeng,et al.Learning 已标记样本集比例 已标记样本集比例 multi-label scene classification J].Pattern Recognition, (c)Coverage (d)Ranking Loss 2004,37(9):1757-1771. 图5数据集enron在4项评估指标上的实验结果 [7]FURNKRANZ J,HULLERMEIER E,MENCIA E L,et al. Fig.5 The summary results of four evaluation metrics Multi-label classification via calibrated label ranking J]. on enron dataset Machine Learning,2008,73(2):133-153. [8]TSOUMAKAS G,VLAHAVAS I.Random k-labelsets:an 根据图2~5可以发现，在半监督学习的意义 ensemble method for multilabel classification[C]//Proceed- 下，SMLT算法对应的4项评估指标的值大多随着 ings of the 18th European Conference on Machine Learning. 已标记样本集比例的增加而不断减小，即算法的分 Berlin:Springer,2007:406-417. 类性能越来越好.并且在已标记样本集比例较小时 [9]ZHANG Minling,ZHOU Zhihua.ML-kNN:a lazy learning approach to multi-label learning[J].Pattern Recognition, 曲线下降较快，随着已标记样本集比例的增加，曲线 2007,40(7):2038-2048. 趋于平缓.仅在yeast数据集上的One-Emor评价指 [10]ELISSEEFF A,WESTON J.A kernel method for multi-la- 标的曲线比较特殊这是因为给定的监督信息越多， belled classification M]//DIETTERICH T G,BECKER 越有助于分类，从而得到更好的分类结果，而当已标 S,GHAHRAMANI Z.Advances in Neural Information

图 ４ 数据集 ｙｅａｓｔ 在 ４ 项评估指标上的实验结果 Ｆｉｇ．４ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ｅｖａｌｕａｔｉｏｎ ｍｅｔｒｉｃｓ ｏｎ ｙｅａｓｔ ｄａｔａｓｅｔ 图 ５ 数据集 ｅｎｒｏｎ 在 ４ 项评估指标上的实验结果 Ｆｉｇ．５ Ｔｈｅ ｓｕｍｍａｒｙ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ｅｖａｌｕａｔｉｏｎ ｍｅｔｒｉｃｓ ｏｎ ｅｎｒｏｎ ｄａｔａｓｅｔ 根据图 ２ ～ ５ 可以发现，在半监督学习的意义 下，ＳＭＬＴ 算法对应的 ４ 项评估指标的值大多随着 已标记样本集比例的增加而不断减小，即算法的分 类性能越来越好．并且在已标记样本集比例较小时 曲线下降较快，随着已标记样本集比例的增加，曲线 趋于平缓．仅在 ｙｅａｓｔ 数据集上的 Ｏｎｅ⁃Ｅｒｒｏｒ 评价指 标的曲线比较特殊．这是因为给定的监督信息越多， 越有助于分类，从而得到更好的分类结果，而当已标 记样本集比例增加到一定程度时，监督信息不再是 影响分类性能的主要因素． ４ 结束语 本文针对广泛存在于实际生活中的半监督多标 记学习问题，以协同训练思想为核心，以两两标记之 间的关系为出发点，利用 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 算法训练分类 器，并将多标记学习问题转化为标记排序问题进行 求解，实验结果表明了该算法的有效性．但是，当多 标记的数量和规模较大时，如何进一步降低算法的 计算复杂度仍将是需要深入讨论的问题． 参考文献： ［１］ＴＳＯＵＭＡＫＡＳ Ｇ， ＫＡＴＡＫＩＳ Ｉ． Ｍｕｌｔｉ⁃ｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ： ａｎ ｏｖｅｒｖｉｅｗ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｄａｔａ Ｗａｒｅｈｏｕｓｉｎｇ ａｎｄ Ｍｉｎｉｎｇ， ２００７， ３（３）： １⁃１３． ［２ ］ ＺＨＵ Ｘｉａｏｊｉｎ． Ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ｌｉｔｅｒａｔｕｒｅ ｓｕｒｖｅｙ ［Ｒ］． Ｍａｄｉｓｏｎ， ＵＳＡ： Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｗｉｓｃｏｎｓｉｎ⁃Ｍａｄｉｓｏｎ， ２００８． ［３］常瑜，梁吉业，高嘉伟，等．一种基于 Ｓｅｅｄｓ 集和成对约束 的半监督聚类算法［ Ｊ］． 南京大学学报：自然科学版， ２０１２， ４８（４）： ４０５⁃４１１． ＣＨＡＮＧ Ｙｕ， ＬＩＡＮＧ Ｊｉｙｅ， ＧＡＯ Ｊｉａｗｅｉ， ｅｔ ａｌ． Ａ ｓｅｍｉ⁃ｓｕ⁃ ｐｅｒｖｉｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｓｅｅｄｓ ａｎｄ ｐａｉｒ ｗｉｓｅ ｃｏｎｓｔｒａｉｎｔｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ： Ｎａｔｕｒａｌ Ｓｃｉ⁃ ｅｎｃｅｓ， ２０１２， ４８（４）： ４０５⁃４１１． ［４］ＺＨＯＵ Ｚｈｉｈｕａ， ＺＨＡＮＧ Ｍｉｎｌｉｎｇ， ＨＵＡＮＧ Ｓｈｅｎｇｊｕｎ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ｉｎｓｔａｎｃｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ［ Ｊ ］． Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉ⁃ ｇｅｎｃｅ， ２０１２， １７６（１）： ２２９１⁃２３２０． ［５］ＺＨＡＮＧ Ｍｉｎｌｉｎｇ， ＺＨＡＮＧ Ｋｕｎ． Ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｂｙ ｅｘ⁃ ｐｌｏｉｔｉｎｇ ｌａｂｅｌ ｄｅｐｅｎｄｅｎｃｙ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １６ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓ⁃ ｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ， ２０１０： ９９９⁃１００７． ［６］ＢＯＵＴＥＬＬ Ｍ Ｒ， ＬＵＯ Ｊｉｅｂｏ， ＳＨＥＮ Ｘｉｐｅｎｇ， ｅｔ ａｌ． Ｌｅａｒｎｉｎｇ ｍｕｌｔｉ⁃ｌａｂｅｌ ｓｃｅｎｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｊ ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２００４， ３７（９）： １７５７⁃１７７１． ［７］ＦＵＲＮＫＲＡＮＺ Ｊ， ＨＵＬＬＥＲＭＥＩＥＲ Ｅ， ＭＥＮＣＩＡ Ｅ Ｌ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｖｉａ ｃａｌｉｂｒａｔｅｄ ｌａｂｅｌ ｒａｎｋｉｎｇ ［ Ｊ］． Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， ２００８， ７３（２）： １３３⁃１５３． ［８］ ＴＳＯＵＭＡＫＡＳ Ｇ， ＶＬＡＨＡＶＡＳ Ｉ． Ｒａｎｄｏｍ ｋ⁃ｌａｂｅｌｓｅｔｓ： ａｎ ｅｎｓｅｍｂｌｅ ｍｅｔｈｏｄ ｆｏｒ ｍｕｌｔｉｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ ｔｈｅ １８ｔｈ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｂｅｒｌｉｎ： Ｓｐｒｉｎｇｅｒ， ２００７： ４０６⁃４１７． ［９］ＺＨＡＮＧ Ｍｉｎｌｉｎｇ， ＺＨＯＵ Ｚｈｉｈｕａ． ＭＬ⁃ｋＮＮ： ａ ｌａｚｙ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ［ Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２００７， ４０（７）： ２０３８⁃２０４８． ［１０］ＥＬＩＳＳＥＥＦＦ Ａ， ＷＥＳＴＯＮ Ｊ． Ａ ｋｅｒｎｅｌ ｍｅｔｈｏｄ ｆｏｒ ｍｕｌｔｉ⁃ｌａ⁃ ｂｅｌｌｅｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｍ］ ／ ／ ＤＩＥＴＴＥＲＩＣＨ Ｔ Ｇ， ＢＥＣＫＥＲ Ｓ， ＧＨＡＨＲＡＭＡＮＩ Ｚ． Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ ·４４４· 智 能 系 统 学 报 第 ８ 卷

第5期 刘杨磊，等：基于Ti-training的半监督多标记学习算法 ·445. Processing Systems 14.Cambridge,USA:The MIT Press, LI Yufeng,HUANG Shengjun,ZHOU Zhihua.Regularized 2002:681-687. semi-supervised multi-label learning[J].Journal of Com- [11]LIU Yi,JIN Rong,YANG Liu.Semi-supervised multi-la- puter Research and Development,2012,49(6):1272- bel learning by constrained non-negative matrix factoriza- 1278. tion[C]//Proceedings of the 21st National Conference on [18]周志华，王珏.机器学习及其应用M].北京：清华大学 Artificial Intelligence.Menlo Park,USA,2006:421-426. 出版社，2007：259-275. [12]姜远，余俏俏，黎铭，等.一种直推式多标记文档分类方 [19]ZHOU Zhihua,LI Ming.Tri-training:exploiting unlabeled 法[J]计算机研究与发展，2008,45(11)：1817-1823. data using three classifiers[J].IEEE Transactions on JIANG Yuan,SHE Qiaogiao,LI Ming,et al.A transduc- Knowledge and Data Engineering,2005,17(11):1529- tive multi-label text categorization approach[J].Joural of 1541. Computer Research and Development,2008,45(11 ) [20]Multi-label datasets EB/OL].2013-01-06 ]http:// 1817-1823. sourceforge.net/projects/mulan/files/datasets/. [13]CHEN Gang,SONG Yangqiu,WANG Fei,et al.Semi-su- 作者简介： pervised multi-label learning by solving a Sylvester equa- 刘杨磊，男，1990年生，硕士研究 tion[C]//Proceedings of SIAM International Conference 生，主要研究方向为机器学习.发表学 on Data Mining.Los Alamitos,USA,2008:410-419. 术论文3篇，获得计算机软件著作权登 [14]SUN Yuyin,ZHANG Yin,ZHOU Zhihua.Multi-label 记3项 learning with weak label[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence.Menlo Park, USA,2010:593-598. [15]孔祥南，黎铭，姜远，等.一种针对弱标记的直推式多标 梁吉业，男.1962年生，教授.博士 记分类方法[J].计算机研究与发展，2010.47(8)： 生导师，博士，主要研究方向为机器学 1392-1399. 习、计算智能、数据挖掘等.先后主持国 KONG Xiangnan,LI Ming,JIANG Yuan,et al.A trans- 家自然科学基金重点项目1项、国家 ductive multi-label classification method for weak labeling “863”计划项目2项.国家“973”计划前 [J].Journal of Computer Research and Development, 期研究专项1项、国家自然科学基金项 2010,47(8):1392-1399. 目4项.发表学术论文150余篇，出版著作2部，获发明专利 [16]KONG Xiangnan,NG M K,ZHOU Zhihua.Transductive 8项. multi-label learning via label set propagation[J].IEEE 高嘉伟，男，1980年生，讲师，主要 Transactions on Knowledge and Data Engineering,2013, 研究方向为机器学习.参与国家“863 25(3)：704-719. 计划项目1项、国家自然科学基金项目 [17]李宇峰，黄圣君，周志华.一种基于正则化的半监督多标 3项和山西省自然科学基金项目4项. 记学习方法[J].计算机研究与发展，2012,49(6)： 发表学术论文10余篇. 1272-1278

Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ １４． Ｃａｍｂｒｉｄｇｅ， ＵＳＡ： Ｔｈｅ ＭＩＴ Ｐｒｅｓｓ， ２００２： ６８１⁃６８７． ［１１］ＬＩＵ Ｙｉ， ＪＩＮ Ｒｏｎｇ， ＹＡＮＧ Ｌｉｕ． Ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａ⁃ ｂｅｌ ｌｅａｒｎｉｎｇ ｂｙ ｃｏｎｓｔｒａｉｎｅｄ ｎｏｎ⁃ｎｅｇａｔｉｖｅ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａ⁃ ｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ Ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｍｅｎｌｏ Ｐａｒｋ， ＵＳＡ， ２００６： ４２１⁃４２６． ［１２］姜远，佘俏俏，黎铭，等．一种直推式多标记文档分类方 法［Ｊ］．计算机研究与发展， ２００８， ４５（１１）： １８１７⁃１８２３． ＪＩＡＮＧ Ｙｕａｎ， ＳＨＥ Ｑｉａｏｑｉａｏ， ＬＩ Ｍｉｎｇ， ｅｔ ａｌ． Ａ ｔｒａｎｓｄｕｃ⁃ ｔｉｖｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｔｅｘｔ ｃａｔｅｇｏｒｉｚａｔｉｏｎ ａｐｐｒｏａｃｈ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２００８， ４５ （ １１ ）： １８１７⁃１８２３． ［１３］ＣＨＥＮ Ｇａｎｇ， ＳＯＮＧ Ｙａｎｇｑｉｕ， ＷＡＮＧ Ｆｅｉ， ｅｔ ａｌ． Ｓｅｍｉ⁃ｓｕ⁃ ｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｂｙ ｓｏｌｖｉｎｇ ａ Ｓｙｌｖｅｓｔｅｒ ｅｑｕａ⁃ ｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＳＩＡＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ． Ｌｏｓ Ａｌａｍｉｔｏｓ， ＵＳＡ， ２００８： ４１０⁃４１９． ［ １４ ］ ＳＵＮ Ｙｕｙｉｎ， ＺＨＡＮＧ Ｙｉｎ， ＺＨＯＵ Ｚｈｉｈｕａ． Ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｗｉｔｈ ｗｅａｋ ｌａｂｅｌ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２４ｔｈ ＡＡＡＩ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｍｅｎｌｏ Ｐａｒｋ， ＵＳＡ，２０１０： ５９３⁃５９８． ［１５］孔祥南，黎铭，姜远，等．一种针对弱标记的直推式多标 记分类方法［ Ｊ］． 计算机研究与发展， ２０１０， ４７ （ ８）： １３９２⁃１３９９． ＫＯＮＧ Ｘｉａｎｇｎａｎ， ＬＩ Ｍｉｎｇ， ＪＩＡＮＧ Ｙｕａｎ， ｅｔ ａｌ． Ａ ｔｒａｎｓ⁃ ｄｕｃｔｉｖｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｗｅａｋ ｌａｂｅｌｉｎｇ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２０１０， ４７（８）： １３９２⁃１３９９． ［１６］ＫＯＮＧ Ｘｉａｎｇｎａｎ， ＮＧ Ｍ Ｋ， ＺＨＯＵ Ｚｈｉｈｕａ． Ｔｒａｎｓｄｕｃｔｉｖｅ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ｖｉａ ｌａｂｅｌ ｓｅｔ ｐｒｏｐａｇａｔｉｏｎ ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１３， ２５（３）： ７０４⁃７１９． ［１７］李宇峰，黄圣君，周志华．一种基于正则化的半监督多标 记学习方法［ Ｊ］． 计算机研究与发展， ２０１２， ４９ （ ６）： １２７２⁃１２７８． ＬＩ Ｙｕｆｅｎｇ， ＨＵＡＮＧ Ｓｈｅｎｇｊｕｎ， ＺＨＯＵ Ｚｈｉｈｕａ． Ｒｅｇｕｌａｒｉｚｅｄ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２０１２， ４９ （ ６）： １２７２⁃ １２７８． ［１８］周志华，王珏．机器学习及其应用［Ｍ］．北京：清华大学 出版社， ２００７： ２５９⁃２７５． ［１９］ＺＨＯＵ Ｚｈｉｈｕａ， ＬＩ Ｍｉｎｇ． Ｔｒｉ⁃ｔｒａｉｎｉｎｇ： ｅｘｐｌｏｉｔｉｎｇ ｕｎｌａｂｅｌｅｄ ｄａｔａ ｕｓｉｎｇ ｔｈｒｅｅ ｃｌａｓｓｉｆｉｅｒｓ ［ Ｊ ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００５， １７（１１）： １５２９⁃ １５４１． ［２０］ Ｍｕｌｔｉ⁃ｌａｂｅｌ ｄａｔａｓｅｔｓ ［ ＥＢ／ ＯＬ］． ［ ２０１３⁃０１⁃０６ ］． ｈｔｔｐ： ／ ／ ｓｏｕｒｃｅｆｏｒｇｅ．ｎｅｔ ／ ｐｒｏｊｅｃｔｓ／ ｍｕｌａｎ ／ ｆｉｌｅｓ／ ｄａｔａｓｅｔｓ／ ． 作者简介： 刘杨磊，男，１９９０ 年生，硕士研究 生，主要研究方向为机器学习．发表学 术论文 ３ 篇，获得计算机软件著作权登 记 ３ 项． 梁吉业，男，１９６２ 年生，教授，博士 生导师，博士，主要研究方向为机器学 习、计算智能、数据挖掘等．先后主持国 家自然科学基金重点项目 １ 项、国家 “８６３”计划项目 ２ 项，国家“９７３”计划前 期研究专项 １ 项、国家自然科学基金项 目 ４ 项．发表学术论文 １５０ 余篇，出版著作 ２ 部，获发明专利 ８ 项． 高嘉伟，男，１９８０ 年生，讲师，主要 研究方向为机器学习．参与国家“８６３” 计划项目 １ 项、国家自然科学基金项目 ３ 项和山西省自然科学基金项目 ４ 项， 发表学术论文 １０ 余篇． 第 ５ 期 刘杨磊，等：基于 Ｔｒｉ⁃ｔｒａｉｎｉｎｇ 的半监督多标记学习算法 ·４４５·