一种基于标记权重的MLKNN集成多标记分类算法.pdf

信息记录材料 2023 年 7 月 第 24 卷第 7 期一种基于标记权重的 MLKNN 集成多标记分类算法蔡小刚(南京机电职业技术学院 江苏 南京 211306)【摘摘要要】在多标记分类问题中,考虑标记间的相关性是提升分类器性能的主要方法之一。集成学习具有很多优势,尤其在提高学习系统的泛化能力上表现尤为突出。因此,提出了一种利用样本的特征空间的分类间隔赋予不同类标不同的权重的 Ada-MLKNN 算法。该算法基于传统 Adaboost 算法框架改进,考虑到多标记样本标记的权重以及分类器的权重,采用基于权重的汉明损失作为阈值来判断样本的分类是否正确,使其适应性扩展到 MLKNN 多标记学习算法。实验结果表明,该算法有效提升了分类器的性能。【关关键键词词】多多标标记记分分类类;集集成成学学习习;标标记记权权重重【中中图图分分类类号号】TP39 【文文献献标标识识码码】A 【文文章章编编号号】1009-5624(2023)07-0184-040 引言在机器学习领域,数据挖掘技术日趋成熟,其中分类技术是数据挖掘的一个热点研究领域。多数分类算法例如决策树、神经网络、支持向量机和贝叶斯等,是针对单一语义标记的数据1。随着大数据技术的发展,研究对象往往是多语义的,也就是多标记数据。对于多标记对象,需要我们建立与其对应的多标记学习框架,对未知的标记进行预测2。多标记分类的算法复杂度明显增加,其难点在于输出空间类别标记集合数随着标记数量的增加成指数增长3。过去,多标记分类在文本分类的应用较多,现已经发展到更多的领域4-5。经典的多标记分类方法主要分为 2 大类:问题转化和算法适应6。问题转化将一个多标记分类问题转化为多个单标记分类问题,采用单标记分类方法来处理多标记分类问题。算法适应是改造单标记分类方法,使其适应用于处理多标记问题。另有算法探索了不同标记之间的关系,提出结合类别权重的多标记学习改进算法7。集成学习的思想是将单一的学习模型组合起来,从而得到一个强大的模型。对于多标记分类中出现分类器精度偏低的问题,研究者提出多种集成多标记分类算法8。本文设计并实现了一种基于标记权重的 MLKNN 集成多标记分类算法,主要贡献如下:(1)针对传统 Adaboost分类器的特点进行改进,使其适 用于多标记 分类的MLKNN 分类器;(2)考虑样本类标权重的不同,采用基于权重的汉明损失作为阈值来判断样本的分类是否正确。1 研究背景在详细叙述本文工作之前,本节首先对多标记分类中的主流方法以及一些常用的术语进行说明。本文主要讨论多标记分类方法中的问题转化方法、算法转化算法和多标记的集成算法。1.1 多标记学习定义多标记分类的数学语言描述为:如果定义 d 维输入空间的样本为 s=Rd,样本的标签集合表示为 l=l1,l2,ld,则多标记分类问题可表示为:给定一个训练集 T=(s1,L1),(s2,L2),(si,Li)(si Rd,Li l),求解一个多标签分类器 h:Rd 2l,该分类器能够预测待预测样本的标签集。实际求解过程中,一般是通过一个实值函数f:Rd l R,分类器会对标签输出不同的实值,然后设定阈值,当实值大于等于阈值时,该标签就被样本选中,否则不被样本选中。对所有标签应用分类器 h,求出样本的标签集,完成分类任务。1.2 多标记学习方法基于问题转换策略的经典方法有 BR 算法和 CC算法。(1)BR 算法:使用一对多拆分策略将标签逐个拆分成多个二元分类器。一个待分样本的预测结果是每个基于成熟算法的单标记分类器对每个标签进行预测的标签合集的输出结果。(2)CC 算法:考虑到了标签之间的关联性,将每个二分基分类器串联起来形成一条链,预测下一个标签时,会考虑已经预测的标签集的结果,因而泛化性要优于 BR算法。算法转化的方法主要介绍几种经典的算法转化多标记分类算法。(1)ML-KNN9算法:基于 K 近邻算法进行改进,同时引进了朴素贝叶斯算法原理,根据近邻样本的标记信息,通过最大后验概率准则预测待预测的样本可能标签集。给定一个未见样本示例 x 以及样本相关标签集 Y ,N(x)代表 x 在训练集中的 K 个近邻样本构成的集合,yx为 x 的类别向量,计算示例 x 的 N(x)中第 l 个标记的个数Cx(l),公式为式(1):Cx(l)=aN(x)ya(l),l (1)进一步假设 Hl 代表示例 x 具有类别标记yx(l)这一事件,由此可以得到所需的分类器如式(2):h(x)=yxi(l)|P(Hj|Cx(l)/P(Hj|Cx(l)0.5,1 j q)(2)计算先验概率(使用 Laplace 平滑)与后验概率:481信息记录材料 2023 年 7 月 第 24 卷第 7 期P(Hl)=(s+mi=1yxi(l)/s2+m(1 j q)(3)P(Hl)=1-P(Hj)(1 j q)(4)P(Cx(l)|Hj)=(s+cj)/(s(k+1)+kp=0cp)(1 j q)(5)P(Cx(l)|Hj)=(s+cj)/(s(k+1)+kp=0cp)(1 j q)(6)最后,可以用先验概率式(3)和式(4)、条件概率式(5)和式(6)并结合贝叶斯定理,得到式(2)的多标记分类器。(2)Rank-SVM10算法:一种基于传统 SVM 改进的算法,它兼顾模型的复杂性和经验错误的最小化。Rank-SVM 算法使用一种排序损失函数来捕捉多标记学习问题,然后解决最优化问题。该算法基于标记配对至分类超平面的最小距离定义样本的分类间隔。通过最大化训练集的分类间隔、算子优化、引入松弛变量以及使用线性最小二乘法求解相应的参数,最后可以得到所需要的多标记分类器。1.3 基于多标记学习的集成算法随着多标记学习研究热度的提升,多标记集成学习也引起了关注,提出了多种多标记学习的集成算法。1.3.1 AdaBoost.MH 算法AdaBoost.MH 算法是一种经典的基于汉明损失的多标记集成分类算法。该算法首先将一个多标记分类问题转换为 M 个单标签二类分类问题,然后在迭代过程中stump 决策树同时处理这些二类问题。该方法对样本的标记比较依赖,标记数据充足的样本,往往有较好的分类效果。1.3.2 Adaboost.ML 算法李凤英10提出了一种基于稳定分类器的多标记学习集成 算 法,即 Adaboost.ML 算 法。该 算 法 对 传 统 的Adaboost 算法进行改进,用 MLKNN 多标记算法作为基分类器,在多标记数据集上的性能有一定的提高。2 基于标记权重的 MLKNN 集成多标记分类算法为了实现其适应于惰性分类器,本节提出一种基于标记权重的 MLKNN 的集成多标记分类算法,即 Ada-MLKNN算法。在实际的多标记学习中,每个样本含有多个标记,样本的不同标记的权重也是不同的。Ada-MLKNN 算法在分类器集成学习过程中考虑到了样本标签的权重,采用基于权重的汉明损失作为阈值来判断样本的分类是否正确。本节研究样本的特征空间,以其分类间隔不同的特点,分别赋予样本标记不同的权重。文献11对样本的分类间隔作了定义,假设样本空间为 U,给定样本为 x,如式(7)margin(x)=(x,NM(x)-(x,NH(x)(7)式中,NH(x)表示在 U 中样本 x 最近邻的同类样本,称为x 的 Nearest Hit(NH)。而 NM(x)表示在 U 中样本 x 最近邻的异类样本,称为 x 的 Nearest Miss(NM)。(x,NM(x)和(x,NH(x)分别表示样本 x 到 NM(x)和NM(x)的距离。假设多标记样本空间为 U=x1,x2,xn,特征集为 F=f1,f2,fd,标签集为 L=l1,l2,lt。Ada-MLKNN 算法利用样本特征空间的分类间隔给不同的类标赋予不同权重,如式(8)Wl=ni=1(F(xi,NM(xi)-F(xi,NH(xi)(8)其中,特征空间距离函数 F 式(9)F(x,y)=df=1(x(f)-y(f)2(9)式中,x(f)和 y(f)分别表示在特征 f 上,样本 x 与 y 的特征值。多标记样本的标记在其特征空间中的分类间隔越大,对应的权重就越大,说明其可分性越强;反之,在特征空间中的分类间隔越小,对应的权重就较小,说明其可分性越弱。Ada-MLKNN 算法的表达具体如下:输入:训练集 X=(x1,Y1),(x2,Y2),(xn,Yn);基分类器 MLKNN;迭代次数 T;阈值 thresh输出:对基分类器进行集成 H(x)=sign(tht(x)1.初始化每个样本的权值分布 D1(i)=1/n。2.For t=1,2,T。3.Begin。4.在 Dt下训练样本:随机从 X 无放回抽取 m 个样本,组成新的数据集 Xt,训练基分类器,得到假设 ht。5.利用式(8)计算每个标记的权重 wl。6.权重集合进行归一化处理,使得 w1+w2+.+wl=1。7.判 断 样 本 分 类 正 确 与 否,样 本 基 于 权 重 的hammingloss thresh 为分类正确,否则为错误。8.计算 Et,如果 Et 0.5,计算 ht的权重 t=0.5ln(1-Et)/Et),否则,返回。9.更新样本的权重 Dt+1增大分错和减小正确样本的权重。10.End。3 实验为了验证 Ada-MLKNN 算法的有效性,本节进行以下实验设计和对比实验,采用不同评价指标进行对比分析。3.1 评价指标该实验采用常用的 5 种多标记性能评价指标:汉明损失(HL)、排序损失(RL)、首类标错误率(OE)、覆盖率(CV)、平均查准率(AP)。HL 表示实际标签未出现在预测集中或预测集中出现581信息记录材料 2023 年 7 月 第 24 卷第 7 期了实际没有的标签,其定义如式(10)HL=1ppi=11q|h(xiYi)|(10)OE 指预测样本的类别标记排序中,序列最前面的标记不属于相关标记集合的情况,该指标越小其性能越好,定义如式(11)OE=1ppi=1arg maxyf(xi,y)Yi(11)CV 指预测样本的类别标记排序中,覆盖所有标记需要搜索的深度,该指标越小其性能越好,定义如下式(12)CV=1ppi=1maxrankf(xi,y)-1yYi(12)RL 指预测样本的类别标记排序中排列错误的情况,该指标越小其性能越好,定义如式(13)RL=1ppi=11|Yi|Y-i(y,y)|f(xi,y)f(xi,y),(y,y)Yi Y-i(13)AP 指预测样本的标记排序中,排在实际标记前面的仍然是实际标记的情况,该指标越大其性能越好,定义如式(14)AP=1ppi=11|Yi|yYi|y|rankf(x,y)rankf(xi,y),y Yi|rankf(xi,y)(14)3.2 实验数据集为了验证实验优缺点,选取了 3 个公共多标记数据集,分别为 emotions、scene 和 yeast,具体描述信息如表 1所示。表 1 多标记实验数据集描述数据集领域范围样本数属性数标记数emotionsmusic593726sceneimages24072946yeastbiology2417103143.3 实验设计采用式(8)的算法计算 3 种数据集标记的权重,分析不同的多标记数据集标记的权重关系。表 2表 4 分别给出了在 3 种数据集上的不同标记的权重。可以看出,实验数据集的标记的权重各不相等,存在个别标签的权重明显大于其余标签的权重的情况。表 5 表 7 分别列出了 Ada-MLKNN 算法与其他 2 种算法在 3 个多标记数据集上针对 HL、CV、OE、RL 和 AP等 5 个常用的多标记分类评价指标的实验结果。各种算法的最优结果已用黑体标示出。为不失实验的一般性,基分类器数目 T 选取 15,特性 K 值选择为 10 做实验的对比。表 2 emotions 实验数据集的不同标记的权重DatasetLablesemotions1234560.1830.0670.1240.3070.1240.194表 3 scene 实验数据集的不同标记的权重DatasetLablesscene1234560.1670.2380.1910.1560.1120.136表 4 yeast 实验数据集的不同标记的权重DatasetLables1234567yeast0.0570.0310.0400.0590.0550.0500.0828910111213140.0660.1060.0970.0880.0440.0430.182表 5 emotions 数据集对比算法性能比较EvaluationCriterionAlgorithmAda-MLKNNAdaboost.MLMLKNNHL0.2550.0190.2570.0210.2590.018CV2.170.2272.1870.2102.1970.200OE0.3540.0560.3640.0410.3830.046RL0.2430.0430.2460.0310.2560.041AP0.730.0380.7190.0010.6940.032表 6 scene 数据集对比算法性能比较EvaluationCriterionAlgorithmAda-MLKNNAdaboost.MLMLKNNHL0.0740.0080.0750.0090.0870.011CV0.4590.0680.4690.0780.4730.075OE0.2210.0360.220.0060.2260.035RL0.0740.0120.0740.0130.0770.014AP0.8780.020.8760.010.8560.02表 7 yeast 数据集对比算法性能比较EvaluationCriterionAlgorithmAda-MLKNNAdaboost.MLMLKNNHL0.1830.0070.185 0.0070.194 0.008CV6.2090.1376.2310.1336.2710.173OE0.2130.0240.210.0140.230.024RL0.1550.0090.1610.110.1680.01AP0.7840.0120.7730.0200.7510.022从表 5表 7 的实验结果可知,对于 3 种不同的数据集,Ada-MLKNN 算法相对于其他 2 种对比算法,无论在 5种评价指标,还是在算法的稳定性上,都有较优的表现。由于 Ada-MLKNN 算法考虑到样本的不同标记权重,在数据集 emotions 和 yeast 上表现的相对明显。对于权重相对平均的 scene 数据集,提升的效果不是很明显。综上所述,考虑到现实的多标记数据集普遍的存在标签的权重非均衡性,所有 Ada-MLKNN 算法在多标记分类的研究中具有一定的研究意义。(下转第 190 页)681信息记录材料 2023 年 7 月 第 24 卷第 7 期图 3 网络隔离架构【参考文献】1 董姚林,樊重俊.关于物联网环境下的信息安全问题探讨J.物流科技,2022,45(7):44-46.2 周立广,韦智勇.基于区块链的物联网信息安全平台设计与实现J.软件工程,2020,23(12):50-53,46.3 刘昊.物联网环境下网络信息传播安全控制技术研究 J.现代工业经济和信息化,2022,12(4):111-113.4 王辉.电子信息技术在物联网中的应用实践思考J.现代工业经济和信息化,2022,12(11):132-133,136.5 郑俊强,邵胤,瞿良勇.基于物联网的 IT 多通道信息安全监控研究J.微型电脑应用,2022,38(11):111-114.6 曹梦川,伍丹,杜朋轩.基于非对称加密算法的农业物联网 数据加密解密模块的研究 J.信息与电脑,2022(15):224-228.7 史博轩.基于信任锚的物联网身份认证系统研究D.北京:北京信息科技大学,2021.8 方晖.基于区块链技术的物联网信息安全技术J.数字技术与应用,2023,41(1):225-227.9 马骁.基于信息安全的网络隔离技术研究与应用J.电子元器件与信息技术,2020,4(5):26-27.作者简介:石井(1980),女,山东济南,硕士,讲师,研究方向:信息安全。(上接第 186 页)4 结语本文详细地描述了多标记学习和集成学习的代表性研究。从传统的单标记学习引出具有多义性的多标记学习,对多标记学习的框架、多标记分类的求解策略以及 2种问题的转化方法进行详细介绍。从传统的集成学习算法引出基于多标记算法的集成学习算法,考虑到多标记样本标记的权重以及分类器的权重,提出了 Ada-MLKNN 算法,使其适应性扩展到稳定的 MLKNN 多标记学习算法,提升了对数据集的分类效果。多标记数据集的标记之间的关系复杂,存在更高阶的相关性的可能,进一步挖掘标记之间的关系并用于集成学习也是一个很好的研究方向。【参考文献】1 周志华.机器学习 M.北京:清华大学出版社,2016.2 ALJEDANI N,ALOTAIBI R,TAILEB M.Multi-label Arabictext classification:an overview J.Int J Adv Comput SciAppl,2020,11(10):694-706.3 ZHANG M L,ZHOU Z H.A review on multi-label learningalgorithms J.IEEE Trans Knowl Data Eng,2014,26(8):1819-1837.4 ZHANG Z,LI Y K,LIU L,et al.Binary relevance for multi-label learning:an overview J.中国计算机科学前沿(英文版),2018(2):191-202.5 ABDULLAHI A,AZAH N,KAMAL S,et al.An improvedmulti-labelclassifierchainmethodforautomatedtextclassification J.Int J Adv Comput Sci Appl,2021,12(3):442-449.6 李志欣,卓亚琦,张灿龙,等.多标记学习研究综述 J.计算机应用研究,2014,31(6):1601-1605.7 RASTOGI R,KUMAR S.Discriminatory label-specific weightsfor multi-label learning with missing labels J.Neural ProcessLett,2022:1-35.8 徐继伟,杨云.集成学习方法:研究综述 J.云南大学学报(自然科学版),2018,40(6):1082-1092.9 ZHANG M L,ZHOU Z H.ML-KNN:a lazy learning approachto multi-label learning J.Pattern Recognit,2007,40(7):2038-2048.10 李凤英.针对弱标记和稳定算法的多标记集成学习 D.长沙:中南大学,2012.11 GILAD-BACHRACH R,NAVOT A,TISHBY N.Marginbased feature selection-theory and algorithms C/OL Proceedings of the twenty-first international conference onMachine learning.July 4-8,2004,Banff,Alberta,Canada.New York:ACM,2004:43.https:/doi.org/10.1145/1015330.1015352.作者简介:蔡小刚(1988),男,江苏南京,硕士,工程师,研究方向:数据挖掘。091