基于k近邻的多标签分类算法性能比较

2022-03-28程大勇

太原学院学报(自然科学版) 2022年1期

程大勇

(安徽工业职业技术学院信息工程系,安徽铜陵 244000)

0 引言

多标签分类作为分类问题中的一种,在现实生活中广泛存在。目前,多标签分类问题的算法有两大类[1]:一类是基于数据集分解的方法,将多标签分类问题分解成多个单标签分类问题,通过处理这些单标签分类问题最终得到多标签分类问题的解[2];另一类是基于单个优化问题的方法,通过对一般的多类分类算法进行改造,完成能够直接处理多标签分类问题的任务[3]。k近邻法是模式识别中比较常用的分类方法,与一般分类算法需要训练分类器模型不同,它通过计算样本之间的距离,结合已知样本类别投票来决定新样本的类别[4]。基于k近邻的多标签分类算法是对基本k近邻算法的直接扩展,可以直接用于多标签分类问题[5]。本文利用k近邻的多标签分类算法训练已知样本,使用k/2法、Bayes法、Logistic回归法、线性阈值函数法以及多输出线性回归法5种方法进行后处理并作进一步的比较研究。为了比较不同情况下各类算法的性能差异,实验中将测试欧氏、曼哈顿和余弦等3种距离,同时会使用酵母(Yeast)、图像(Image)和基因(Scene)3种类型的数据集进行测试,以求准确分析出不同算法的适用情景以及不同算法之间的差异。

1 基于k近邻法的多标签分类算法概述

1.1 基本原理

假设存在独立同分布的训练样本集为:

{(x1,y1),…,(xi,yi),…,(xl,yl)}

(1)

式中:xi∈Rd是d维的特征向量。Q={1,2,…,c}是类标签集(c是类别总数)。对于经典的多类问题,yi只能取Q中的一个类别号,而对于多标签问题,yi可能取Q中的若干类别(即一个标签相关子集)。

1.1.1基于k近邻法的多标签分类算法[5]

传统的k近邻法主要针对单标签分类,多标签分类则需要对算法进行两方面的改造:1)将多标签样本看成同时属于多个不分主次的类别,在计算判别函数时,给不同的类别计算近邻样本数。2)需要增加一个后处理的学习算法来确定样本的相关标签。对于某一待分类样本x,同样先寻找其k个近邻样本。由于现在近邻样本都可能包含多个标签,故将判别函数定义为：

gi(x)=| {j|i∈yj′,j=1,…,k}|,i=1,…,c

(2)

即计算在k个近邻中第i个类标签出现的次数。

1.1.2k近邻法的多标签分类流程

多标签分类主要分为两个阶段:训练阶段和测试阶段。在训练阶段,需要对数据进行预处理,即利用留一法,通过欧氏距离(曼哈顿距离、余弦距离)计算训练样本的k个近邻,统计每一类标签的得票数,从而将原始训练数据集转化成一个新的数据集,再将转化得到的新的数据集用于5种后处理算法模型中进行训练。在测试阶段,也需要按照训练阶段的数据集转化方法对原始测试数据集进行转化,再将转化好的数据集代入已经训练好的模型,得出新的准则函数预测测试样本的标签集,并且计算各项评价指标。具体的流程如图1所示。

图1 k近邻多标签算法测试阶段流程图

为了建立确定x的相关标签集的后处理模型,本文收集与编程4种学习方法:离散Bayes方法、线性阈值法、多输出线性回归法与Logistic回归法,而且对各个算法进行训练与测试。

1.2 样本距离计算方法概述

为了对原始数据集进行转化,需要计算每个样本的k个近邻,也即计算每个样本到其他样本的距离。

1.2.1欧氏距离

欧氏距离[6]描述的是在d维空间中两点的真实距离,设x=(x1,x2,…,xd)T和y=(y1,y2,…,yd)T之间的距离D(x,y)定义为式(3)

(3)

1.2.2余弦距离

余弦距离的值介于0～1之间,描述的是两个向量之间的夹角,定义的公式为：

(4)

因为直接计算内积,强度低,误差较大,适用于文本分类中。

1.2.3曼哈顿距离

曼哈顿距离用以标明两个点在标准坐标系上的绝对轴距总和,定义的公式为

(5)

1.3 算法评价的准则

多标签分类算法的评价准则与一般的单标签分类系统有所不同。在单标签系统中常用的评价准则包括精度、准确度、recall以及F measure。在多标签分类系统中,评价的准则变得更加复杂。本文中将采用3种类型(基于排序、基于样本、基于标签)的评价准则对实验的数据做评价,以求更加全面准确的分析实验结果和算法性能。

1.3.1基于样本的评价准则

Hamming损失(Hamming Loss):评价样本标签对错分的次数;召回率(Recall):对于一个样本来说,指它的真实标签有多少被正确预测出来,评价的是预测结果的全面性,也即查全率,该值在0～1之间,值越大,性能愈好;精度(Presicion): 对于一个样本来说,指它预测的准确性,也即预测出来的标签中有几个是正确的,该值在0～1之间,值越大,性能愈好;正确率(Accuracy):评价的是预测正确的样本在整个样本集中所占的比例。该值在0～1之间,值越大,性能愈好;子集正确率(Subset Accuracy):是严格的评价准则,它要求预测的标签集与样本的实际标签完全相同。该值在0～1之间,值越大越好;F度量(F measure):它是召回率和精度的调和平均,该值在0～1之间,值越大越好。

1.3.2基于排序的评价准则

错误率(One Error):评价预测出的样本标签排序最靠前的标签不属于样本实际标签的的次数。该评价为0,表明分类的结果是最好的,该指标的值越小,预测效果越好;覆盖率(Coverage):评价对于预测出的标签排序,要将样本的所有实际标签都包含进去至少需要几个标签。这个值越小,预测效果越好;排序损失(Ranking Loss):评价的是相关标签排在不相关标签之后的次数。当排序是完美时,它的值为0。值越小,预测效果越好;平均精度(Average Precision):评价的是样本实际标签排序的平均分数。

1.3.3基于标签的评价准则

Accuracy,Roc曲线下面的区域AUC,precision和recall在两类评价中经常使用。对所有标签计算这些评价值可以获得两类操作符,称作macro averaging和micro averaging。这些方法在信息查询任务中会考虑平均的accuracy,recall,F measure。

2 实验结果与分析

2.1 数据来源

实验数据分别为3组不同类型的数据集,包括yeast,image135和scene。yeast数据集包括训练样本1 500个,测试样本917个,样本最多包含103个特征值,共有14个标签,每个样本平均拥有4个标签;image135数据集共有1 200个训练样本,800个测试样本,135个特征向量维数,5个类别,每个样本平均拥有1.3个标签;scene数据集也是图像数据集,包括1 211个训练样本,1 196个测试样本,294个特征向量,6个类别,样本平均标签1个。

2.2 5种算法性能分析

为了比较5种后处理算法的性能差异,采用欧氏距离计算样本之间的距离,分别对3个数据集(yeast,image135,scene)的数据进行测试。其中,k值过小,整体模型变得复杂,估计误差较大,容易出现过拟合;k值过大,近似误差较大,预测结果可信度较低,所以实验中将k值设为经验值10。为了清晰显示各算法之间的差异,将k/2法作为基准,将其设为1,其他算法的评价值分别与k/2法中的各个评价值相除,得到相对改进量。对于值越大越好的标准,值大于1则表示有改进;对于值越小越好的指标,值小于1表示有改进。如图1所示,在yeast数据集上(图2),可以发现离散bayes法、多输出线性回归以及logistic回归法都有不错的表现,其中logistic回归法的性能最优,而线性阈值函数法的各项指标值都不是很好。原因可能是用最小平法误差法估计系数的过程中,可能出现奇异矩阵。而在image135数据集上(图3),线性阈值函数法比在yeast数据集上表现优越很多,相反,logistic回归法表现的却不是很好,bayes法和多输出线性回归表现相近。在scene数据集上(图4),5种算法的性能没有太大差异,相对较好的是Bayes法,相对较差的是线性阈值函数法和Logistic回归。

图2 yeast数据集5种算法性能比较图

图3 image135数据集5种算法性能比较图

图4 scene数据集5种算法性能比较图

2.3 距离对算法性能的影响

在基于k近邻的多标签算法中,选择的k个近邻对于寻找未知样本的所属标签有非常重要的影响。寻找的k个近邻与未知样本特征越相近,预测的准确性就越高。目前比较常用的计算k近邻的方法有:欧氏距离、曼哈顿距离以及余弦距离。为了比较不同距离对算法性能的影响,在yeast数据集上计算5种算法在hamming-loss,ranking-loss,macro-precision,micro-precision指标的值,比较它们的时间性能差异。

由图5分析可得,不同算法的3种不同距离对算法性能的影响不是特别明显,但存在一定影响。对k/2法而言,余弦距离的性能最好;对Bayes法而言,曼哈顿距离性能最好;对线性阈值函数法而言,欧氏距离和曼哈顿距离一样好;对多输出线性回归而言,曼哈顿距离最好;对Logistic回归法而言,欧氏距离最好。同时,采用欧氏距离进行多标签分类时,Logistic回归法性能最好;采用曼哈顿和余弦距离进行多标签分类时,离散Bayes法性能最好。因此相同的距离计算方法在不同的算法上效果不同,相同的算法不同的距离计算方法性能也有差异。