基于相似度的多标签分类算法优化*

刘 云 肖 添 肖 雪

（昆明理工大学信息工程与自动化学院 昆明 650500）

1 引言

近年来，多标签分类问题被广泛研究，不同于传统分类问题，多标签分类的每个样本实例同时包含两个及两个以上标签数量。因此，这些标签不再互斥［1～2］。为了更深入研究多标签分类问题，很多学者提出了许多多标签分类方法，主要包括基于支持向量机［3］，神经网络［4］，朴素贝叶斯［5］，决策树［6］，K 近邻（KNN）［7］等方法。现存的分类算法存在分类精度不高，不能有效处理类别不均衡数据等问题［8］。

Elisseeff 等［9］提出一种向量机的多标签分类算法（a Ranking Multi-class Support Vector Machine，RankSVM），此方法中利用排序函数计算值决定顺序排名，求解二次规划的凸目标函数得出类标签集合。Zhang［10］等研究了一种多标签K 近邻算法（Multi-label K Nearest Neighbor Algorithm，ML-KNN），此方法的目标是寻找每类训练样本的近邻标签数，对构建实例概率函数，计算贝叶斯类先验概率和类条件概率预测测试实例的类标签集合。

本文提出基于相似度的多标签分类算法（Multi-label Classification based on Similarity，SMLC），首先对实例进行相似度函数的构建，同时进行并行计算，然后利用决策函数加权或学习阈值函数预测实例类标签集合。仿真结果表明，与RankSVM 和ML-KNN 算法进行对比分析，SMLC 算法在多标签分类任务中的各性能指标上表现最优。

2 模型建立

式中·,· 代表两个实例向量的内积，d表示多项式次数，c 表示代价函数多项式由高阶项转化为低阶项的正则项。计算测试实例xi的标签权重f(xi)，xi所包含的标签集标签权重计算公式如下式所示：

3 SMLC算法

3.1 算法描述

为进一步预测实例标签集，本文研究提出一种

根据训练数据D'={(x1,y1),…,(xN,yN)}，预测未知实例xi的类标签集合。首先，根据前文的相似度多项式函数（4）可知每个训练实例(xj,yj)∈D′相似度为Φ(xi,xj)（1 ≤j≤N），若训练实例属于同一个标签集k∈y′（即大小相同），则实例相似性可通过加权计算。相同类标签k∈y′的训练数据D′的实例xi的相似性可通过式（6）表示：

式中|fk(x)表示未知测试实例xi标签k∈y的置信度。假设线性模型t(x)=w,f(x) +b（t(·)为阈值函数），给定训练集D，可根据式（10）学习阈值函数：

上式中，

3.2 复杂度分析

计算训练实例xi中每个非零元素xj的相似度值，并且计算对应测试实例特征值时间复杂度仅为

4 仿真分析

4.1 数据集和评价指标

为了评估本文研究的多标签分类算法有效性，选取了著名的Mulan Library［12］多标签数据集进行仿真测试，表1描述了测试数据集的具体信息。

表1 仿真数据集

在多标签分类任务中，其性能评价指标比单标签分类更为复杂和全面，下面对算法评价指标进行定义，给定测试数据集D，测试实例xi∈RM，需预测标签集为h:χ→2K，多标签学习算法输出函数f:χ×y→R，其中fk( )xi为标签k∈y对于未知测试实例xi的置信度，多标签分类中把有效预测最大标签集合作为评价一个分类算法好坏。为了证明算法的有效性，选取了多标签分类的常用评价指标如下［13～15］。

1）汉明损失（Hamming Loss，HL）：

对于任何p，指标函数Ⅱ[ ]p=1 且p 成立，否则为0。ED(f)=0 时性能最佳，该指标评估排名最高的标签不在相关标签集中的次数。该指标值越小则说明算法性能越好。该指标衡量测试样本平均包含多少标签。指标值越大表明算法性能越优。

4.2 仿真分析

将所提出的SMLC算法与Rank-SVM、ML-KNN算法进行仿真分析的结果统计于表2和表3中。

表2 在emotions数据集中性能分析

表3 在CLA500数据集中性能分析

从上表2、3 可看出，与RankSVM 和ML-KNN算法对比，SMLC 算法在汉明损失、1-错误率、覆盖率、排名损失、平均准确率五个多标签分类性能指标上表现最优。

5 结语

有效提高多标签分类准确度成为重要研究方向。本文提出基于相似度的多标签分类算法SMLC，该算法首先构建实例相似度函数，再采用并行计算方式算出相似值，最后通过加权计算类标签集合权重或者学习阈值方法预测类标签集合。仿真结果表明，对比RankSVM、ML-KNN 算法，SMLC算法在多标签分类任务中多个评价指标上表现更好。