开放科学（资源服务）标志码（OSID）：

0 概述

多标签学习广泛存在于真实世界中。在文档分类问题^[1-3]中，每篇文档可能隶属于多个预定义的主题，如“经济”与“文化”；在场景分类^[4]问题中，每个场景图片可能属于多个语义类别，如“海滩”和“城市”；在ECG心电异常检测^[5]问题中，每个病人可能同时具有多种心脏疾病，如“完全性左束支阻滞”“前壁心肌梗死”以及“下壁心肌梗死”。对于上述多标签学习问题，训练集中的每条样本对应一组标签，学习系统通过对训练集进行学习从而完成对未知样本标签集的预测。

如果限定每个样本只对应一个标签，那么传统的二分类以及多分类问题均可看作多标签学习问题的特例。相较二分类以及多分类问题，多标签学习的难点在于随着标签数量的增加，待预测的标签组合数量呈指数级增长^[6]，从而导致分类器的计算成本过高，例如，一个具有20个标签的数据集，每条样本对应的标签组合一共有$ {2}^{20} $种，且各个标签组合对应的训练样本数不平衡^[7]，会进一步增加学习的难度。在解决此类问题时，一种直观的做法是将其转换为多个独立的二分类问题来求解^[8]，其中，每个二分类问题对应一个可能的标签。然而，此种做法忽略了样本标签间的相关性^[9-11]，因此，其泛化性能往往并不理想。例如，在ECG心电异常检测问题中^[5]，如果已知一个病人具有下壁心肌梗死疾病，则该病人具有前壁心肌梗死疾病的可能性将大于完全性左束支阻滞疾病^[5]。因此，有效利用标签间的相关性是解决多标签学习问题的关键。

根据多标签学习中考虑的标签关联程度，可以将现有方法分为一阶策略、二阶策略和高阶策略3类^[12]：一阶策略是将每个标签看成是独立不相关的，不考虑标签间的相关性；二阶策略利用了标签成对的关联信息；高阶策略考虑每个标签对其他标签的影响。LP算法^[13]将多标签问题转换为多分类问题，虽然其考虑了标签间的相关性，但标签组合的爆炸提高了算法的复杂度。TSOUMAKAS等^[14]提出Random k-Labelsets算法，该算法将集成学习与LP算法^[13]相结合，将原始的标签集分成若干子标签集，使用LP技术训练相应的分类器，但是，该算法对于标签子集的选择是随机的，没有充分利用标签集间的相关性。READ等^[15]提出了分类器链（Classifier Chain，CC）算法，该算法将先预测出的标签作为后续待预测标签的输入特征，CC算法虽然考虑到了标签间的相关性，但其结果依赖于标签预测的顺序，前面预测的标签误差会传递到后面的标签中，如果前面的标签误差较大，将会导致算法整体分类性能不佳。YANG等^[16]提出深度森林的多标签学习（Multi-label Learning with Deep Forest，MLDF）算法，MLDF算法通过设计多层结构来学习标签之间的相关性，使得深度森林模型适用于多标签分类场景。

本文提出一种双模态、阈值自调节的多标签学习K近邻算法，该算法的核心思想是根据标签相关性的双模态来构建预测模型，其中，一种模态是某些标签和其他标签具有多阶相关性，另一种模态是某些标签和其他标签是独立的。使用Fp_growth^[17]算法挖掘标签集的频繁项，明确数据集本身固有的标签高阶关系，然后基于本文算法为高阶标签关系建模，评估样本标签集合是每一种频繁项的可能性，如果标签高阶关系模型不能预测出样本的标签集合，说明该样本具有的标签间相关性并不强，则使用一阶策略完成该样本标签集的预测。在此基础上，提出一种阈值自学习算法，该算法采用通用的Beta分布^[18]描述阈值分布，基于每个频繁项和标签在原始特征空间上选择出对应的特征子空间，针对特征子空间中的每条样本，根据相应的评分模型获取相应的概率，用于更新Beta分布的参数$ \alpha $和$ \beta $，使得阈值更加准确地拟合样本分布，从而提高模型的预测性能。

1 问题描述与解决方案 1.1 问题描述

设$ \mathit{\boldsymbol{D}}=\left\{({\mathit{\boldsymbol{x}}}_{i}, {\mathit{\boldsymbol{Y}}}_{i})|1\le i\le m\right\}({\mathit{\boldsymbol{x}}}_{i}\in \mathit{\boldsymbol{X}}, {\mathit{\boldsymbol{Y}}}_{i}\subset \mathit{\boldsymbol{Y}}) $为给定的多标签数据集，其中，$ \mathit{\boldsymbol{X}}={\mathbb{R}}^{d} $表示$ d $维的样本空间，$ \mathit{\boldsymbol{Y}}=\left\{{l}_{1}, {l}_{2}, \cdots , {l}_{q}\right\} $表示所有可能的标签，$ q $是标签数量，$ {\mathit{\boldsymbol{x}}}_{i} $是第$ i $条训练样本实例，$ {\mathit{\boldsymbol{Y}}}_{i}\in \mathit{\boldsymbol{Y}} $为样本$ {\mathit{\boldsymbol{x}}}_{i} $对应的标签集。

本文目的是基于标签相关性的双模态分别构建2个分类器：

1）第一个分类器是$ {\mathit{\boldsymbol{h}}}_{1}\left(\mathit{\boldsymbol{x}}\right) $，该分类器输出一个实值函数$ f:\mathit{\boldsymbol{X}}\times \mathit{\boldsymbol{P}}\to \mathit{\boldsymbol{R}} $，对于给定样本$ \mathit{\boldsymbol{x}} $及频繁项$ {\mathit{\boldsymbol{P}}}_{j}(1\le j\le k) $，分类器$ {\mathit{\boldsymbol{h}}}_{1}\left(\mathit{\boldsymbol{x}}\right) $输出的函数值量化样本$ \mathit{\boldsymbol{x}} $与频繁项$ {\mathit{\boldsymbol{P}}}_{j} $相关性得分的大小，频繁项由Fp_growth^[17]算法挖掘得到，$ \mathit{\boldsymbol{P}}=\{{\mathit{\boldsymbol{P}}}_{1}, {\mathit{\boldsymbol{P}}}_{2}, \cdots , {\mathit{\boldsymbol{P}}}_{k}\} $为频繁项集，$ k $为频繁项个数。分类器$ {\mathit{\boldsymbol{h}}}_{1}(\cdot ) $可由$ f(\cdot , \cdot ) $求得：

$ {\mathit{\boldsymbol{h}}}_{1}\left(\mathit{\boldsymbol{x}}\right)={\mathit{\boldsymbol{P}}}_{\widehat{t}} $

(1)

其中$ ：\widehat{t}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{t}{\mathrm{m}\mathrm{a}\mathrm{x}}\frac{f(\mathit{\boldsymbol{x}}, {\mathit{\boldsymbol{P}}}_{t})}{\mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{t}\right)} $，$ (f(\mathit{\boldsymbol{x}}, {\mathit{\boldsymbol{P}}}_{t}) > \mathrm{C}\mathrm{T}({\mathit{\boldsymbol{P}}}_{t}), 1\le t\le k, {\mathit{\boldsymbol{P}}}_{t}\in \mathit{\boldsymbol{P}}) $。

其中：$ \mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{t}\right) $是频繁项$ {\mathit{\boldsymbol{P}}}_{t} $对应的阈值，本文称为关联阈值。

2）第二个分类器是$ {\mathit{\boldsymbol{h}}}_{2}\left(\mathit{\boldsymbol{x}}\right) $，该分类器输出一个实值函数$ g:\mathit{\boldsymbol{X}}\times \mathit{\boldsymbol{Y}}\to \mathit{\boldsymbol{R}} $，对于给定样本$ \mathit{\boldsymbol{x}} $和标签$ {l}_{j}(1\le j\le q) $，分类器$ {\mathit{\boldsymbol{h}}}_{2}\left(\mathit{\boldsymbol{x}}\right) $输出的函数值可以量化样本$ \mathit{\boldsymbol{x}} $与标签$ {l}_{j} $相关性得分的大小。分类器$ {\mathit{\boldsymbol{h}}}_{2}(\cdot ) $可由$ g(\cdot , \cdot ) $求得：

$ {\mathit{\boldsymbol{h}}}_{2}\left(\mathit{\boldsymbol{x}}\right)=\left\{{l}_{t}\left|g\right(\mathit{\boldsymbol{x}}, {l}_{t}) > \mathrm{I}\mathrm{T}({l}_{t}), {l}_{t}\in \mathit{\boldsymbol{Y}}, 1\le t\le q\right\} $

(2)

其中：$ \mathrm{I}\mathrm{T}\left({l}_{t}\right) $是标签$ {l}_{t} $对应的阈值，本文称为独立阈值。

当频繁项相关性得分大于对应的关联阈值且该频繁项得分是所有频繁项中的最大值时，样本的标签集就是该频繁项。当通过多标签分类器$ {\mathit{\boldsymbol{h}}}_{1}\left(\mathit{\boldsymbol{x}}\right) $预测样本的标签为空集时，说明样本的标签集并不在频繁项集中，验证了样本标签间的相关性并不大，此时再使用分类器$ {\mathit{\boldsymbol{h}}}_{2}\left(\mathit{\boldsymbol{x}}\right) $预测样本的标签集，从而兼顾标签间多种可能的相关性。

定义1（特征子空间）  在多标签任务中，给定标签$ {l}_{j}(1\le j\le q) $和频繁项$ {\mathit{\boldsymbol{P}}}_{j}(1\le j\le k) $，可以在原始样本空间中获得对应的特征子空间$ {\mathit{\boldsymbol{D}}}_{{l}_{j}} $和$ {\mathit{\boldsymbol{D}}}_{{\mathit{\boldsymbol{P}}}_{j}} $：

$ {\mathit{\boldsymbol{D}}}_{{l}_{j}}=\left\{{\mathit{\boldsymbol{x}}}_{i}\left|\right({\mathit{\boldsymbol{x}}}_{i}, {\mathit{\boldsymbol{Y}}}_{i})\in \mathit{\boldsymbol{D}}, {l}_{j}\in {\mathit{\boldsymbol{Y}}}_{i}\right\} $

(3)

$ {\mathit{\boldsymbol{D}}}_{{\mathit{\boldsymbol{P}}}_{j}}=\left\{{\mathit{\boldsymbol{x}}}_{i}\left|\right({\mathit{\boldsymbol{x}}}_{i}, {\mathit{\boldsymbol{Y}}}_{i})\in \mathit{\boldsymbol{D}}, {\mathit{\boldsymbol{Y}}}_{i}\subseteq {\mathit{\boldsymbol{P}}}_{j}\wedge {\mathit{\boldsymbol{P}}}_{j}\subseteq {\mathit{\boldsymbol{Y}}}_{i}\right\} $

(4)

$ {\mathit{\boldsymbol{D}}}_{{l}_{j}} $包含训练集D中含有标签$ {l}_{j} $的实例，$ {\mathit{\boldsymbol{D}}}_{{\mathit{\boldsymbol{P}}}_{j}} $包含训练集D中标签集是$ {\mathit{\boldsymbol{P}}}_{j} $的实例。

定义2（频繁项）  给定一个标签组合$ {\mathit{\boldsymbol{l}}}_{\mathit{\boldsymbol{s}}}({\mathit{\boldsymbol{l}}}_{\mathit{\boldsymbol{s}}}\subset \mathit{\boldsymbol{Y}}) $和最小支持度$ \theta (1 < \theta \le |\mathit{\boldsymbol{D}}\left|\right) $，如果标签组合$ {\mathit{\boldsymbol{l}}}_{\mathit{\boldsymbol{s}}} $在数据集$ \mathit{\boldsymbol{D}} $中出现的频数大于等于最小支持度$ \theta $，则该标签组合$ {\mathit{\boldsymbol{l}}}_{\mathit{\boldsymbol{s}}} $就是一个频繁项$ {\mathit{\boldsymbol{P}}}_{j}(1\le j\le k) $。

1.2 解决方案框架

本文提出一种基于标签相关性的多标签学习K近邻算法，其架构如图 1所示。首先，使用频繁项挖掘算法Fp_growth^[17]挖掘给定数据集的频繁项集；然后，为频繁项相关性得分和标签相关性得分建模，基于这2种评分模型使用阈值自学习算法为每一个频繁项和标签学习对应的关联阈值和独立阈值。至此，多标签学习分类模型构建完毕，最终使用预测算法完成测试样本预测。

2 训练与预测 2.1 相关性得分建模

本文对标签高阶关系和单标签分别进行建模，建模方法与ML-kNN算法^[19]相比，ML-kNN算法将标签与其他标签之间看作是相互独立的，实现了单标签的建模与模型求解，忽略了标签之间的相关性，本文在ML-kNN单标签建模算法的基础上，实现高阶标签关系建模与模型求解，兼顾了标签间多种可能的相关性。

标签高阶关系通常以频繁项的形式呈现，对频繁项相关性得分进行建模，形式化表示为：

$ {s}_{\mathit{\boldsymbol{t}}}({\mathit{\boldsymbol{P}}}_{j})=p\left({\mathit{\boldsymbol{P}}}_{j}\left|{C}_{{\mathit{\boldsymbol{P}}}_{j}}\right(\mathit{\boldsymbol{t}})\right), {\mathit{\boldsymbol{P}}}_{j}\in \mathit{\boldsymbol{P}} $

(5)

其中：$ p\left({\mathit{\boldsymbol{P}}}_{j}\left|{C}_{{\mathit{\boldsymbol{P}}}_{j}}\right(\mathit{\boldsymbol{t}})\right) $是一个后验概率，是当样本$ \mathit{\boldsymbol{t}} $的$ \mathrm{k} $近邻^[20]样本中有$ {C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right) $个样本的标签集是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $的情况下，测试样本$ \mathit{\boldsymbol{t}} $的标签集是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $的概率；$ {C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right) $统计样本$ \mathit{\boldsymbol{t}} $的$ \mathrm{k} $近邻样本中标签集是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $的样本数。使用贝叶斯准则，式（5）可以重写为：

$ {s}_{\mathit{\boldsymbol{t}}}({\mathit{\boldsymbol{P}}}_{j})=p({\mathit{\boldsymbol{P}}}_{j})p\left({C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right)|{\mathit{\boldsymbol{P}}}_{j}\right)/p\left({C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right)\right) $

(6)

其中：$ p\left({\mathit{\boldsymbol{P}}}_{j}\right) $是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $的先验概率；$ p\left({C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right)|{\mathit{\boldsymbol{P}}}_{j}\right) $表示在样本$ \mathit{\boldsymbol{t}} $的标签集是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $的条件下，样本$ \mathit{\boldsymbol{t}} $的k近邻样本中恰有$ {C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right) $个样本的标签集是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $的概率。

$ p\left({C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right)|{\mathit{\boldsymbol{P}}}_{j}\right) $的计算需要借助频数向量$ {\mathit{\boldsymbol{k}}}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\theta \right)\left(0\le \theta \le k\right), \;{\mathit{\boldsymbol{k}}}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\theta \right) $统计的是数据集$ \mathit{\boldsymbol{D}} $中样本的标签组合是频繁项$ {\mathit{\boldsymbol{P}}}_{j} $且其$ \mathrm{k} $近邻样本中正好有θ个近邻样本的标签组合是该频繁项的样本数量。

$ {s}_{\mathit{\boldsymbol{t}}}\left({\mathit{\boldsymbol{P}}}_{j}\right) $计算过程如算法1所示。

算法1  频繁项相关性得分计算算法

输入  训练集$ \mathit{\boldsymbol{T}} $，近邻个数k，样本$ \mathit{\boldsymbol{t}} $，平滑参数$ s $，频繁项$ {\mathit{\boldsymbol{P}}}_{j}\in \mathit{\boldsymbol{P}} $

输出  频繁项相关性得分$ {s}_{\mathit{\boldsymbol{t}}}\left({\mathit{\boldsymbol{P}}}_{j}\right) $

1.$ {\rm{p}}({{\rm{P}}_{\rm{j}}}) = \left( {{\rm{s}} + \sum\limits_{{\rm{i}} = 1}^{\rm{m}} {\left[\kern-0.15em\left[ {{{\rm{Y}}_{\rm{i}}} \subseteq {{\rm{P}}_{\rm{j}}} \wedge {{\rm{P}}_{\rm{j}}} \subseteq {{\rm{Y}}_{\rm{i}}}} \right]\kern-0.15em\right]} } \right)/({\rm{s}} + {\rm{m}}) $

2.$ \mathrm{p}(\neg {\mathrm{P}}_{\mathrm{j}})=1-\mathrm{p}\left({\mathrm{P}}_{\mathrm{j}}\right) $

3.$ \mathrm{确}\mathrm{认}\mathrm{N}({\mathrm{x}}_{\mathrm{i}}), \mathrm{i}\in \left\{\mathrm{1, 2}, \dots , \mathrm{m}\right\}; $

4.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{\theta }\in \left\{\mathrm{0, 1}, \dots , \mathrm{k}\right\}\mathrm{d}\mathrm{o} $

5.$ {\mathrm{k}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{\theta }\right)=0;{\stackrel{-}{\mathrm{k}}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{\theta }\right)=0; $

6.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{i}\in \left\{\mathrm{1, 2}, \dots , \mathrm{m}\right\}\mathrm{d}\mathrm{o} $

7.$ \mathrm{\delta }={\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}({\mathrm{x}}_{\mathrm{i}})=\sum\limits_{\mathrm{\alpha }\in \mathrm{N}\left({\mathrm{x}}_{\mathrm{i}}\right)}⟦{\mathrm{Y}}_{\mathrm{\alpha }}\subseteq {\mathrm{P}}_{\mathrm{j}}\bigwedge {\mathrm{P}}_{\mathrm{j}}\subseteq {\mathrm{Y}}_{\mathrm{\alpha }}⟧ $

8.$ \mathrm{i}\mathrm{f}\;({\mathrm{Y}}_{\mathrm{i}}\subseteq {\mathrm{P}}_{\mathrm{j}}\bigwedge {\mathrm{P}}_{\mathrm{j}}\subseteq {\mathrm{Y}}_{\mathrm{i}})\;\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n} $

9.$ {\mathrm{k}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{\delta }\right)={\mathrm{k}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{\delta }\right)+1 $

10.$ \mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\;{\stackrel{-}{\mathrm{k}}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{\delta }\right)={\stackrel{-}{\mathrm{k}}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{\delta }\right)+1 $

11.$ \mathrm{p}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)|{\mathrm{P}}_{\mathrm{j}}\right)=\left(\mathrm{s}+{\mathrm{k}}_{{P}_{j}}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)\right)\right)/\left(\mathrm{s}\times \left(\mathrm{k}+1\right)+\sum\limits_{\mathrm{o}=0}^{\mathrm{k}}{\mathrm{k}}_{{P}_{j}}\left(\mathrm{o}\right)\right) $

12.$ \mathrm{p}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)|\neg {\mathrm{P}}_{\mathrm{j}}\right)=\left(\mathrm{s}+{\stackrel{-}{\mathrm{k}}}_{{P}_{j}}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)\right)\right)/\left(\mathrm{s}\times \left(\mathrm{k}+1\right)+\sum\limits_{\mathrm{o}=0}^{\mathrm{k}}{\stackrel{-}{\mathrm{k}}}_{{P}_{j}}\left(\mathrm{o}\right)\right) $

13.$ \mathrm{确}\mathrm{定}\mathrm{N}\left(\mathrm{t}\right) $；

14.$ {\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)=\sum\limits_{\mathrm{\alpha }\in \mathrm{N}\left(\mathrm{t}\right)}⟦{\mathrm{Y}}_{\mathrm{\alpha }}\subseteq {\mathrm{P}}_{\mathrm{j}}\bigwedge {\mathrm{P}}_{\mathrm{j}}\subseteq {\mathrm{Y}}_{\mathrm{\alpha }}⟧ $

15.$ {\mathrm{s}}_{\mathrm{t}}\left({\mathrm{P}}_{\mathrm{j}}\right)=\mathrm{p}\left({\mathrm{P}}_{\mathrm{j}}\right)\mathrm{p}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)|{\mathrm{P}}_{\mathrm{j}}\right)/\mathrm{p}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\right(\mathrm{t}\left)\right)= $

$ \begin{array}{l}\mathrm{p}\left({\mathrm{P}}_{\mathrm{j}}\right)\mathrm{p}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)|{\mathrm{P}}_{\mathrm{j}}\right)/\left(\mathrm{p}\right({\mathrm{P}}_{\mathrm{j}})\mathrm{p}\left({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)|{\mathrm{P}}_{\mathrm{j}}\right)+\\ \mathrm{p}(\neg {\mathrm{P}}_{\mathrm{j}})\mathrm{p}({\mathrm{C}}_{{\mathrm{P}}_{\mathrm{j}}}\left(\mathrm{t}\right)|\neg {\mathrm{P}}_{\mathrm{j}}))\end{array} $

对标签相关性得分进行建模，形式化表示为：

$ {s}_{\mathit{\boldsymbol{t}}}\left({l}_{j}\right)=p\left({l}_{j}\left|{C}_{{l}_{j}}\right(\mathit{\boldsymbol{t}})\right), {l}_{j}\in \mathit{\boldsymbol{Y}} $

(7)

使用贝叶斯准则，式（7）可以重写为：

$ {s}_{\mathit{\boldsymbol{t}}}\left({l}_{j}\right)=p\left({l}_{j}\right)p\left({C}_{{l}_{j}}\left(\mathit{\boldsymbol{t}}\right)|{l}_{j}\right)/p\left({C}_{{l}_{j}}\right(\mathit{\boldsymbol{t}}\left)\right) $

(8)

$ {s}_{\mathit{\boldsymbol{t}}}\left({l}_{j}\right) $的计算过程见文献[19]。以上2种评分模型求解算法的时间复杂度类似，以算法1的时间复杂度为例进行分析，该算法是对标签高阶关系建模以评估样本标签集是该频繁项的可能性，核心步骤是计算先验$ p\left({\mathit{\boldsymbol{P}}}_{j}\right) $和似然$ p\left({C}_{{\mathit{\boldsymbol{P}}}_{j}}\left(\mathit{\boldsymbol{t}}\right)|{\mathit{\boldsymbol{P}}}_{j}\right) $，这2个概率的计算都是基于训练集$ \mathit{\boldsymbol{T}} $中样本数的统计而进行的，需要遍历整个训练集$ \mathit{\boldsymbol{T}} $，因此，该算法的时间复杂度为$ O\left(N\right) $。

2.2 阈值自学习算法

对于某个样本$ \mathit{\boldsymbol{t}} $，通过上述相关性得分建模算法，便可得到模型对各个频繁项的相关性得分以及模型对各个标签的相关性得分。在多标签分类中，每个实例对应的标签数是不同的，大多数情况下采取的做法是设置全局阈值，将标签相关性得分大于全局阈值的标签筛选出来。本文采取一种更加灵活的方法，为每个频繁项自动地学习得到适用于样本特征的关联阈值，为每个标签自动地学习得到适用于样本特征的独立阈值。关联阈值记为：

$ \begin{array}{l}f\left(\mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{j}\right)\;:\alpha , \beta \right)=\\ \frac{1}{B(\alpha , \beta )}\int \mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{j}{)}^{\alpha -1}\right(1-\mathrm{C}\mathrm{T}({\mathit{\boldsymbol{P}}}_{j}{\left)\right)}^{\beta -1}, {\mathit{\boldsymbol{P}}}_{j}\in \mathit{\boldsymbol{P}}\end{array} $

(9)

本文采用通用的Beta分布来描述关联阈值$ \mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{j}\right)({\mathit{\boldsymbol{P}}}_{j}\in \mathit{\boldsymbol{P}} $，$ \mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{j}\right)\in \left[\mathrm{0, 1}\right]) $的阈值分布。Beta分布的参数$ \alpha $和$ \beta $可以基于可用样本通过贝叶斯推断估计出。$ f\left(\mathrm{C}\mathrm{T}\right({\mathit{\boldsymbol{P}}}_{j})\;:\alpha , \beta ) $是关联阈值服从的Beta分布的密度函数，$ \alpha $和$ \beta $决定了密度函数的形状。本文利用关联阈值自学习算法求解关联阈值$ \mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{j}\right) $，关联阈值自学习算法描述如下：

算法2  关联阈值自学习算法

输入  训练集$ \mathit{\boldsymbol{T}} $，近邻个数k，平滑参数$ s $，频繁项$ {\mathit{\boldsymbol{P}}}_{j}\in \mathit{\boldsymbol{P}}, \alpha =1, \beta =1 $

输出  关联阈值$ \mathrm{C}\mathrm{T}\left({\mathit{\boldsymbol{P}}}_{j}\right) $

1.$ {\mathrm{D}}_{{\mathrm{P}}_{\mathrm{j}}}\leftarrow \mathrm{\varnothing } $

2.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{i}=1\;\mathrm{t}\mathrm{o}\;\mathrm{m}\;\mathrm{d}\mathrm{o}: $

3.$ \mathrm{i}\mathrm{f}({\mathrm{Y}}_{\mathrm{i}}\subseteq {\mathrm{P}}_{\mathrm{j}}\wedge {\mathrm{P}}_{\mathrm{j}}\subseteq {\mathrm{Y}}_{\mathrm{i}}) $

4.$ {\mathrm{D}}_{{\mathrm{P}}_{\mathrm{j}}}\leftarrow {\mathrm{D}}_{{\mathrm{P}}_{\mathrm{j}}}\bigcup {\mathrm{x}}_{\mathrm{i}} $

5.$ \mathrm{e}\mathrm{n}\mathrm{d} $

6.$ \mathrm{e}\mathrm{n}\mathrm{d} $

7.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{i}=1\;\mathrm{t}\mathrm{o}\left|{\mathrm{D}}_{{P}_{j}}\right|\mathrm{d}\mathrm{o}: $

8.$ \mathrm{由}\mathrm{算}\mathrm{法}1\mathrm{计}\mathrm{算}\mathrm{样}\mathrm{本}{\mathrm{x}}_{\mathrm{i}}\mathrm{的}\mathrm{频}\mathrm{繁}\mathrm{项}\mathrm{相}\mathrm{关}\mathrm{性}\mathrm{得}\mathrm{分}{\mathrm{s}}_{\mathrm{t}}\left({\mathrm{P}}_{\mathrm{j}}\right) $

9.$ \mathrm{\alpha }=\mathrm{\alpha }+100\times {\mathrm{s}}_{{\mathrm{x}}_{\mathrm{i}}}\left({\mathrm{P}}_{\mathrm{j}}\right) $

10.$ \mathrm{\beta }=\mathrm{\beta }+100\times (1-{\mathrm{s}}_{{\mathrm{x}}_{\mathrm{i}}}({\mathrm{P}}_{\mathrm{j}}\left)\right) $

11.end

12.$ \mathrm{C}\mathrm{T}({\mathrm{P}}_{\mathrm{j}})=\frac{\mathrm{\alpha }}{\mathrm{\alpha }+\mathrm{\beta }} $

对独立阈值进行建模，形式化表示为：

$ \begin{array}{l} f(\mathrm{I}\mathrm{T}({l}_{j}):\alpha , \beta )= \\ \frac{1}{B(\alpha , \beta )}\int \mathrm{I}\mathrm{T}({l}_{j}{)}^{\alpha -1}(1-\mathrm{I}\mathrm{T}({l}_{j}{\left)\right)}^{\beta -1}, {l}_{j}\in \mathit{\boldsymbol{Y}} \end{array} $

(10)

独立阈值自学习算法描述如下：

算法3  独立阈值自学习算法

输入  训练集$ \mathit{\boldsymbol{T}} $，近邻个数k，平滑参数$ s $，标签$ {l}_{j}\in \mathit{\boldsymbol{Y}}, \alpha =1, $ $ \beta =1 $

输出  独立阈值$ \mathrm{I}\mathrm{T}\left({l}_{j}\right) $

1.$ {\mathrm{D}}_{{\mathrm{l}}_{\mathrm{j}}}\leftarrow \mathrm{\varnothing } $

2.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{i}=1\;\mathrm{t}\mathrm{o}\;\mathrm{m}\;\mathrm{d}\mathrm{o}: $

3.$ \mathrm{i}\mathrm{f}({\mathrm{l}}_{\mathrm{j}}\subseteq {\mathrm{Y}}_{\mathrm{i}}) $

4.$ {\mathrm{D}}_{{\mathrm{l}}_{\mathrm{j}}}\leftarrow {\mathrm{D}}_{{\mathrm{l}}_{\mathrm{j}}}\bigcup {\mathrm{x}}_{\mathrm{i}} $

5.$ \mathrm{e}\mathrm{n}\mathrm{d} $

6.$ \mathrm{e}\mathrm{n}\mathrm{d} $

7.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{i}=1\;\mathrm{t}\mathrm{o}\left|{\mathrm{D}}_{{l}_{j}}\right|\mathrm{d}\mathrm{o}: $

8.$ \mathrm{计}\mathrm{算}\mathrm{样}\mathrm{本}{x}_{i}\mathrm{的}\mathrm{标}\mathrm{签}\mathrm{相}\mathrm{关}\mathrm{性}\mathrm{得}\mathrm{分}{s}_{\mathit{\boldsymbol{t}}}\left({l}_{j}\right) $

9.$ \mathrm{\alpha }=\mathrm{\alpha }+100\times {\mathrm{s}}_{{\mathrm{x}}_{\mathrm{i}}}\left({\mathrm{l}}_{\mathrm{j}}\right) $

10.$ \mathrm{\beta }=\mathrm{\beta }+100\times (1-{\mathrm{s}}_{{\mathrm{x}}_{\mathrm{i}}}({\mathrm{l}}_{\mathrm{j}}\left)\right) $

11.end

12.$ \mathrm{I}\mathrm{T}\left({\mathrm{l}}_{\mathrm{j}}\right)=\frac{\mathrm{\alpha }}{\mathrm{\alpha }+\mathrm{\beta }} $

值得注意的是，以上提到的2种阈值自学习算法都是增量式学习算法，当有新的训练样本时，可以基于已有的阈值直接进行更新，而无需重新学习。

例1 假设一个频繁项$ {\mathit{\boldsymbol{P}}}_{1} $，在训练集中有3个样本$ {\mathit{\boldsymbol{t}}}_{1} $、$ {\mathit{\boldsymbol{t}}}_{2} $、$ {\mathit{\boldsymbol{t}}}_{3} $的标签集是该频繁项，对$ {\mathit{\boldsymbol{t}}}_{1} $、$ {\mathit{\boldsymbol{t}}}_{2} $、$ {\mathit{\boldsymbol{t}}}_{3} $计算频繁项相关性得分，分别为$ {s}_{{\mathit{\boldsymbol{t}}}_{1}}\left({\mathit{\boldsymbol{P}}}_{1}\right) $=0.28，$ {s}_{{\mathit{\boldsymbol{t}}}_{2}}\left({\mathit{\boldsymbol{P}}}_{1}\right) $=0.25，$ {s}_{{\mathit{\boldsymbol{t}}}_{3}}\left({\mathit{\boldsymbol{P}}}_{1}\right) $=0.44，假设频繁项$ {\mathit{\boldsymbol{P}}}_{1} $的关联阈值Beta分布的初始参数为$ {\alpha }^{0} $=1，$ {\beta }^{0} $=1，则Beta分布参数的更新如下：

$ \begin{array}{l} {\alpha }^{1} =1+100 \times 0.28=29,\; {\beta }^{1} =1+100 \times 0.72=73\\ {\alpha }^{2} =29+100 \times 0.25=54,\; {\beta }^{2} =73+100 \times 0.75=148\\ {\alpha }^{3} =54+100 \times 0.44=98,\; {\beta }^{3} =148+100 \times 0.56=204 \end{array} $

最终，频繁项$ {\mathit{\boldsymbol{P}}}_{1} $的关联阈值为：

$ \mathrm{C}\mathrm{T}({\mathit{\boldsymbol{P}}}_{1})=\frac{{\alpha }^{3}}{{\alpha }^{3}+{\beta }^{3}}=\frac{98}{98+204}=0.325 $

2.3 预测算法

预测的思路是首先基于标签高阶关系模型，评估样本标签集合属于每一种频繁项的可能性，如果标签高阶关系模型不能预测出样本的标签集合，说明该样本具有的标签间相关性并不强，则将问题转换为多个独立的二分类问题进行解决，从而兼顾标签间多种可能的相关性。预测算法描述如下：

算法4  预测算法

输入  训练集$ \mathit{\boldsymbol{T}} $，近邻数k，测试样本$ \mathit{\boldsymbol{t}} $，平滑参数$ s $，关联阈值集合，独立阈值集合，频繁项集$ \mathit{\boldsymbol{P}} $，标签集$ \mathit{\boldsymbol{Y}} $

输出  测试样本标签集$ \mathrm{L}\mathrm{S} $

1.$ \mathrm{L}\mathrm{S}\leftarrow \mathrm{\varnothing } $

2.$ \mathrm{S}\leftarrow \mathrm{\varnothing } $

3.$ \mathrm{f}\mathrm{o}\mathrm{r}\;\mathrm{e}\mathrm{a}\mathrm{c}\mathrm{h}\;{\mathrm{P}}_{\mathrm{j}}\;\mathrm{i}\mathrm{n}\;\mathrm{P}\;\mathrm{d}\mathrm{o}: $

4.$ \mathrm{i}\mathrm{f}\;{\mathrm{s}}_{\mathrm{t}}\left({\mathrm{P}}_{\mathrm{j}}\right) > \mathrm{C}\mathrm{T}({\mathrm{P}}_{\mathrm{j}})\;\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}: $

5.$ \mathrm{S}\leftarrow \mathrm{S}\bigcup {\mathrm{P}}_{\mathrm{j}} $

6.$ \mathrm{e}\mathrm{n}\mathrm{d} $

7.$ \mathrm{e}\mathrm{n}\mathrm{d} $

8.$ \mathrm{i}\mathrm{f} $ |S| > 1 then

9.$ \mathrm{L}\mathrm{S}\leftarrow {\mathrm{s}}_{\mathrm{t}}({\mathrm{P}}_{\mathrm{j}})\mathrm{最}\mathrm{大}\mathrm{的}\mathrm{频}\mathrm{繁}\mathrm{项}{\mathrm{P}}_{\mathrm{j}} $

10.$ \mathrm{e}\mathrm{n}\mathrm{d} $

11.$ \mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\;\mathrm{i}\mathrm{f}\left|\mathrm{S}\right|==1\; \mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n} $

12.$ \mathrm{L}\mathrm{S}\leftarrow \mathrm{S} $

13.$ \mathrm{e}\mathrm{n}\mathrm{d} $

14.else

15.$ \mathrm{f}\mathrm{o}\mathrm{r}\;{\mathrm{l}}_{\mathrm{j}}\;\mathrm{i}\mathrm{n}\;\mathrm{Y}\;\mathrm{d}\mathrm{o}: $

16.$ \mathrm{i}\mathrm{f}\;{\mathrm{s}}_{\mathrm{t}}({\mathrm{l}}_{\mathrm{j}}) > \mathrm{I}\mathrm{T}({\mathrm{l}}_{\mathrm{j}})\;\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n} $

17.$ \mathrm{L}\mathrm{S}\leftarrow \mathrm{L}\mathrm{S}\bigcup {\mathrm{l}}_{\mathrm{j}} $

18.$ \mathrm{e}\mathrm{n}\mathrm{d} $

19.$ \mathrm{e}\mathrm{n}\mathrm{d} $

3 实验结果与分析 3.1 实验数据集

为了验证本文算法的有效性，选取来自Mulan Library^[21]库中的2组经典多标签数据集进行实验，多标签数据集对应的名称、领域、样本数、特征数、标签空间中标签数等详细信息如表 1所示。

Emotions^[22]数据集包含593个标注了情感的歌曲样本，每个样本由72个特征描述，即8个韵律特征和64个音色特征。每个样本对应6个情感标签，每个标签代表一个基于模型的歌曲情感聚类。

Scene^[23]数据集包含2 407个自然场景的图片样本，每个样本由294个特征描述，对应一个294维的特征向量，具体的属性向量生成过程可参见文献[23]，标签空间是6种可能的自然场景。

3.2 实验设置

实验设置具体如下：

1）实验平台。实验中所有代码都由Python编写，模型基于sklearn搭建。设备系统为Windows10，配备NVIDIA GEFORCE GTX 950M显卡，内存为16 GB。

2）数据预处理。本文算法对样本进行预测需要找出样本在训练集上相似度最高的k个样本，基于这k个样本的标签集预测测试样本的标签组合。为了度量样本之间的相似性，本文采用样本间的欧氏距离作为样本相似性的度量标准，为了消除特征之间的量纲影响，对数据特征进行归一化处理。

3）评价指标。本文算法可以直接预测出测试样本的标签集，因此，基于多标签排序^[24]的评价指标并不适用于本文算法，考虑到本文算法的特殊性，从多标签分类层面对预测结果进行评估，采用$ \mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\left(P\right) $、$ \mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}\left(R\right) $、$ \mathrm{F}1 $$ - $$ \mathrm{M}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{e}\left(\mathrm{F}1\right) $^[25]作为算法性能的评价指标。$ \mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n} $、$ \mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l} $的计算依赖于分类结果的混淆矩阵，$ \mathrm{F}1 $$ - $$ \mathrm{M}\mathrm{e}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{r}\mathrm{e} $的计算又是基于$ \mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n} $、$ \mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l} $。分类结果的混淆矩阵如表 2所示。

各评价指标的计算公式如下：

$ P=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{P}}} $

(11)

$ R=\frac{{T}_{\mathrm{T}\mathrm{P}}}{{T}_{\mathrm{T}\mathrm{P}}+{F}_{\mathrm{F}\mathrm{N}}} $

(12)

$ \mathrm{F}1=\frac{2\times P\times R}{P+R} $

(13)

$ P $指标用于衡量预测出的正样本中确实是正样本的比率，$ R $指标用于衡量正样本中有多少比例被预测出，$ \mathrm{F}1 $是$ P $和$ R $的调和平均，用于衡量算法在整体上的性能效果。

3.3 结果分析 3.3.1 本文算法与各基准方法性能比较

各方法在实验数据集上的性能比较结果如表 3、表 4所示。从表 3、表 4可以看出，本文算法在2个数据集上的$ \mathrm{F}1 $指标都取得了最优值，在Emotions数据集上，本文算法的F1比CC、LP、RAKEL、MLDF分别提高1.4、5.8、1.4、6.6个百分点，在Scene数据集上，本文算法的F1相比CC、LP分别提升1.3和8.4个百分点。相较其他基准方法对标签高阶关系建模，本文算法通过数据挖掘来明确数据集本身固有的高阶标签关系并进行建模，其考虑标签间真实存在的相关性，因此，取得了较好的分类性能。

3.3.2 关联阈值和独立阈值的有效性分析

为了验证关联阈值$ CT $和独立阈值$ IT $的有效性，本文采用3种策略分别进行实验：

1）只使用关联阈值对测试样本进行预测。

2）只使用独立阈值对测试样本进行预测。

3）结合2个阈值对测试样本进行预测。

3种策略的判别能力如表 5、表 6所示。由表 5、表 6可以看出，策略3的分类性能优于策略1和策略2。对比2组实验数据不难发现，在Emotions数据集上，只使用关联阈值就可以取得较好的分类性能，在Scene数据集上，只使用关联阈值则分类性能不理想。在Emotions数据集上，从策略1到策略3分类性能提升不是很明显，但是在Scene数据集上，从策略1到策略3的分类性能提升效果非常显著。

出现上述2种情况，最主要的原因是2组数据集标签间相关性的强弱不同。具体来说，Emotions数据集上因为标签间的相关性很强，测试样本的标签集总是以频繁项的形式呈现，因此，通过关联阈值预测就可以将绝大部分的测试样本标签集确定，剩余的样本需借助独立阈值去获取样本的标签集，即从策略1到策略3分类效果的性能提升不是很明显，验证了本文对标签高阶关系建模的有效性。在Scene数据集上，由于标签间的相关性较弱，存在挖掘出的频繁项不能覆盖所有标签的情况，通过使用关联阈值进行预测，该标签的分类指标必然为0，将大幅影响整体分类效果。在实际的预测过程中，只有很少部分的测试样本标签集是频繁项，值得注意的是，在数据集上虽然挖掘出频繁项，但一种标签组合是否属于频繁项由它在数据集上出现的频数以及设置的阈值参数共同决定，在Scene数据集上，频繁项的个数很少，通过本文算法验证了Scene数据集标签间的相关性较弱，对于测试样本，大部分都采用策略2完成标签集的获取，因此，从策略1到策略3分类效果有了很大的提升。

4 结束语

已有多标签学习算法大多将多标签学习问题转化为多个独立的二分类问题，以对每个标签进行单独求解，该过程通常忽略了标签间的相关性。本文提出一种基于标签相关性的多标签学习K近邻算法，该算法充分挖掘标签间的相关性，对标签高阶关系进行建模，基于标签高阶关系模型分析样本的标签集合，如果标签高阶关系模型不能预测出样本的标签集合，说明该样本标签间的相关性并不强，此时使用一阶策略完成该样本标签集的预测工作，从而消除仅依靠单阶或多阶模型进行预测时存在的弊端。在2个经典数据集上的实验结果表明，该算法具有较高的F1-Measure值，其能取得较好的分类效果。下一步将在确定对应于每个频繁项或标签的近邻样本时，采用不同大小的近邻参数K，从近邻样本中提取出更为有效的信息来辅助分类过程，从而提高本文算法的分类性能。