传统监督学习认为一个对象只具有一个标记类别, 属于“单示例, 单标记”类型. 在上述单一语义的情境中, 监督学习已经取得了巨大的发展成果. 然而在真实世界中, 一个对象往往同时具有多种语义信息, 属于“单示例, 多标记”类型. 例如在一篇新闻稿中可同时包含改革和经济两个主题, 一张风景图中天空和云朵往往会伴随出现, 在这种情况下很难用单一语义标记去描述对象信息. 为此, 多标记学习框架应运而生, 用于解决真实世界中一个对象同时具有多个语义标记的问题. 因其可以良好的反映真实世界中包含的多语义信息, 目前在文本分类^[1], 图像标注^[2], 生物基因分析^[3]等领域得到了广泛应用. 同时众多学者也提出了一些多标记学习算法, 并取得了一定的成功. 但是目前大部分已有的多标记学习算法所采用的共同策略是基于同一特征属性空间预测所有标记类别, 忽略了每个标记独有的特征信息, 因此这种思路存在改进优化的空间. 其中ML-KNN^[4]作为一种使用简单, 分类性能优异的多标记学习算法, 其数学形式相对简单, 模型易于优化, 在实际应用和学术科研中得到了广泛应用. 但是ML-KNN算法在模型训练过程中并没有考虑标记之间的相关性, 同时也忽略了标记特定特征信息. 因此, 在模型训练过程中考虑标记相关性和引入标记特定特征信息, 可以进一步提高算法的分类性能, 基于此提出了本文算法. 本文的整体组织结构如下: 第1部分介绍相关工作, 第2部分描述本算法的实现, 第3部分给出实验以及实验结果, 最后进行了总结.

1 相关工作

在传统“单示例, 单标记”的单语义环境中, 传统监督学习已经取得了巨大的发展^[5-8]. 然而在真实世界中, 语义信息往往是丰富多彩的, 传统监督学习已经不能对同时从属于多个标记类别下的单个示例进行很好的语义表达. 相比于传统监督学习, 多标记学习可以更好的反映真实世界中包含的语义信息. 不同于传统监督学习所假设的“单示例, 单标记”情形, 多标记学习所研究的任务场景属于“单示例, 多标记”类型. 我们假设 ${\cal{X}} = {\mathbb{R}^d}$ 代表d维特征空间, ${\cal{Y}} = \left\{ {{l_1},{l_2}, \cdots ,{l_q}} \right\}$ 代表包含q个标记类别的标记空间. 多标记学习的任务是在训练集 $D = \{ \left( {{{{x}}_i},{Y_i}} \right)|1 \le i \le m\}$ 中训练一个分类器 $h:{\cal{X}} \to {2^{\cal{Y}}}$ , 预测未知示例 ${{x}} \in {\cal{X}}$ 所从属的标记集合 $h({{x}}) \subseteq {\cal{Y}}$ , 其中 ${{{x}}_i} \in {\cal{X}}$ 为特征空间中的一个示例, 是一个d维特征向量, ${Y_i} \in {\cal{Y}}$ 为示例 ${{{x}}_i}$ 所从属的标记集合, 是标记空间 ${\cal{Y}}$ 中的一个子集.

目前多标记学习研究所面临的主要挑战是标记空间爆炸性增长的问题^[9]. 即类别标记集合数随着标记种类的增加而呈指数级增长, 假设样本中包含有q个类别标记信息, 则标记输出空间规模即可达到 ${2^q}$ 级别的大小, 为每个标记子集单独训练一个分类器是不切实际的. 为了解决这个标记空间爆炸的问题, 目前关于多标记学习的研究大都集中在通过挖掘标记之间的相关性来降低指数级别增长的标记空间. 根据标记相关性的利用策略, 可以将多标记学习算法分为3类: (1)一阶策略, 完全忽略标记之间的相关性, 只是将一个多分类问题转换为多个独立的二分类问题, 这类方法虽然实现简单但是缺少良好的泛化性能. (2)二阶策略, 考虑标记之间的成对关联, 例如相关标记与无关标记之间的排序关系, 两两标记之间的交互关系等构造多标记学习框架. 这类算法具有一定的泛化性能, 但是无法很好的解决标记之间的关系超过二阶时的问题. (3)高阶策略, 考虑单个标记与其它全部标记之间的相关性, 这类算法可以很好的反映真实世界的标记相关性, 但同时模型复杂度往往较高. 目前众多学者也提出了一些多标记学习算法, 例如由Boutell等提出的一阶策略算法BR (Binary Relevance)^[10], 由Fürnkranz等提出的二阶策略算法Calibrated Label Ranking^[11], 由Read等提出的高阶策略算法Classifer Chains^[12]等. 上述算法的共同点是将多分类问题分解为多个二分类问题进行解决, 属于问题转换型. 由Clare等提出的一阶策略算法ML-KNN, ML-DT^[13]和Elisseeff A提出的二阶策略算法Rank-SVM^[14]等算法是采用当前的机器学习算法直接处理多分类问题, 属于算法适应型. 但无论是问题转换型算法还是算法适应型算法, 上述提到的算法在预测标记时都是假设所有标记共享同一特征空间, 并未对每种类别标记独有的特征信息进行考虑. 即多标记学习框架得到的q个实值函数 $\{ {f_1},{f_2}, \cdots ,{f_q}\}$ 都是基于相同的属性特征空间训练而来. 但是这种思路可能并不是最优的, 例如在图像识别领域, 在判断“天空”和“沙漠”时, 颜色特征是需要优先考虑的, 而在判断“蓝天”和“大海”时, 考虑纹理特征相关属性会大大提高分类器的性能. 由此可见, 每个标记都可能具有与其最大相关性的属性特征, 考虑每个标记独有的属性特征对于提高算法分类性能具有一定的帮助, 这些属性特征是对该标记最有区别度的特征, 称为标记特定特征信息.

其中, ML-KNN作为一种使用简单, 分类性能高效的算法, 在实际应用中得到了广泛应用. 但是ML-KNN算法属于一阶策略, 并未对标记之间相关性进行考虑, 同时也没有考虑标记特定特征信息. 虽然该算法取得了巨大的成果, 但是并未对标记相关性和标记特定特征信息加以利用, 存在优化改进的空间. 由Zhang等提出了LIFT算法^[15]首次提出从引入标记特定特征信息这一角度出发的研究思路, 针对每一个标记信息提取其特征信息, 从而构建标记特征空间, 之后基于标记特征空间进行模型训练. 该算法基于多种公开数据集证明了其思路的有效性, 为多标记学习指明了一个新的研究方向. 但是该算法并未考虑标记之间的相关性, 属于一阶策略算法. 基于此, 我们通过融入标记相关性和引入标记特定特征信息对ML-KNN算法进行改进, 进一步提高算法分类性能.

2 ML-KNN算法以及改进算法 2.1 ML-KNN算法

ML-KNN算法是在k近邻算法的基础上, 综合贝叶斯理论提出的能够处理多标记分类问题的KNN算法. 在此引入一些符号用于对该算法进行说明. 在多标记训练数据集 $D = \left\{ {\left( {{{{x}}_i},{Y_i}} \right){\rm{|}}1 \le i \le m} \right\}$ 中, ${{{x}}_i} \in {\cal{X}}$ , ${Y_i} \in {\cal{Y}}$ , ${Y_x}$ 为示例 ${{{x}}_i}$ 所对应的 $q$ 维标记向量. 如果示例x具有类别标记 $l\left( {1 \le l \le q} \right)$ , 则定义 ${Y_x}\left( l \right) = 1$ , 否则 ${Y_x}\left( l \right) = 0$ . 另外假设 $N\left( {{x}}\right)$ 代表示例x在训练集D中的k个近邻集合, 对这k个近邻集合中拥有标记 $l$ 的样本数量用 ${C_x}\left( l \right)$ 表示, 其中:

${C_x}\left( l \right) = \mathop \sum \limits_{a \in N\left( x \right)} {Y_a}\left( l \right),\;l \in {\cal{Y}}$

(1)

其中, ${C_x}$ 代表了示例x所对应的k个近邻集合中所包含的标记信息. ML-KNN算法为懒惰算法, 当有新的测试示例t需要进行预测分类时, ML-KNN首先识别示例t在训练数据集D中的k个近邻集合 $N\left( {{t}} \right)$ , 在这里设定 $H_1^l$ 代表示例t拥有标记l, 相反, 当示例t没有标记l时用 $H_0^l$ 表示. 另外引入 $E_j^l$ 表示在 $N\left( {{t}} \right)$ 中有j个示例拥有标记l, 其中 $j \in \left\{ {0,1, \cdots ,k} \right\}$ , 基于向量 ${C_t}$ , 示例t所对应的类别向量 ${Y_{{t}}}$ 可以使用如下最大后验概率来计算.

${Y_t}\left( l \right) = \arg {\max\nolimits_{b \in \left\{ {0,1} \right\}}}\frac{{P\left( {H_b^l} \right)P\left( {E_{{C_t}\left( l \right)}^l|H_b^l} \right)}}{{P\left( {E_{{C_t}\left( l \right)}^l} \right)}}$

(2)

该式所代表的含义为已知在测试示例t的k个近邻集合中有 ${C_t}\left( l \right)$ 个样本与标记l相关, 示例t与标记l是否相关取决于 $N\left( {{t}} \right)$ 中是否与标记l相关的最大概率. 根据贝叶斯规则, 上式可以进一步变换为:

$\begin{split} {Y_t}\left( l \right) =& \arg {\max\nolimits_{b \in \left\{ {0,1} \right\}}}\frac{{P\left( {H_b^l} \right)P\left( {E_{{C_t}\left( l \right)}^l|H_b^l} \right)}}{{P\left( {E_{{C_t}\left( l \right)}^l} \right)}} \\ =& \arg {\max\nolimits_{b \in \left\{ {0,1} \right\}}}P\left( {H_b^l} \right)P\left( {E_{{C_t}\left( l \right)}^l|H_b^l} \right) \\ \end{split} $

(3)

由上述公式可知, 计算 ${Y_t}\left( l \right)$ 需要得到先验概率 $P\left( {H_b^l} \right)$ 和条件概率 $P(E_{{C_t}\left( l \right)}^l|H_b^l)$ , 这两个值都是可以从训练数据样本计算得到的.

2.2 基于ML-KNN算法的改进算法

LIFT算法是由张敏灵等学者在研究多标记学习算法时提出的一种全新的算法. 该算法不同于之前研究点集中于挖掘标记之间相关性上, 而忽略了标记特定特征信息. LIFT算法从挖掘标记特征这一角度出发, 针对每一个标记类别, 通过挖掘其特征信息构建标记特征空间, 在模型训练过程中引入标记特征, 并且经过大量实验表明LIFT算法分类性能在公开数据集上优于其它多标记学习算法, 同时也证明了在模型训练过程中引入标记特定特征信息提高算法分类性能这一思路的有效性, 为后续多标记学习研究提供了一种新的思路.

2.2.1 LIFT算法基本模型

LIFT算法通过对训练样本中的每个类别标记进行聚类操作, 分析每个标记的特征信息, 将原始样本集合根据特征标记划分为与当前标记呈正相关的样本和负相关的样本. 具体来说, 对于标记 ${l_j} \in {\cal{Y}}$ , 根据式(4)和式(5)分别计算其正相关的示例集合 ${P_j}$ 和负相关示例集合 ${N_j}$ .

$ {P_j} = \{ {x_i}|\left( {{x_i},{Y_i}} \right) \in D,{l_j} \in {Y_i}\} $

(4)

$ {N_j} = \{ {x_i}|\left( {{x_i},{Y_i}} \right) \in D,{l_j} \notin {Y_i}\} $

(5)

其中, ${Y_i}$ 表示实例 ${x_i}$ 所对应的标记向量, D为训练数据集, ${P_j}$ 代表包含标记 ${l_j}$ 的示例集合, ${N_j}$ 代表不包含标记 ${l_j}$ 的示例集合. 之后采用K-means聚类算法分别对两个示例集合进行聚类操作, 得到在 ${P_j}$ 上的 $m_j^ + $ 个聚类中心 $\left\{ {p_1^{\rm{j}},p_2^j, \cdot \cdot \cdot ,p_{m_j^ + }^j} \right\}$ 和在 ${N_j}$ 上的 $m_j^ - $ 个聚类中心 $\left\{ {n_1^{\rm{j}},n_2^j, \cdot \cdot \cdot ,n_{m_j^ - }^j} \right\}$ . 为了解决聚类中心不平衡的问题, LIFT算法设定 ${m_j} = m_j^ + = m_j^ - $ , 其中 ${m_j} = r \cdot {\rm{min}}\left( {\left| {{P_j}\left| , \right|{N_j}} \right|} \right)$ . 这两个聚类中心集合分别代表着正负相关示例集合的内在特征结构, 可作为构建标记特定特征空间的基础. 为了构建标记 ${l_j}$ 的特定特征空间 ${Z_j}$ , 采用如下映射 ${\phi _j}: {\cal{X}} \to {{{Z}}_j}$ , ${\phi _j}$ 表达如下:

${\phi _j}\left( {{x}} \right) = \left[ {d\left( {{{x}},p_1^j} \right), \cdots,d\left( {{{x}},p_{m_j^ + }^j} \right),d\left( {{{x}},n_1^j} \right), \cdots,d\left( {{{x}},n_{m_j^ - }^j} \right)} \right] $

(6)

其中, $d\left( { \cdot , \cdot } \right)$ 代表两个向量之间的欧式距离. 根据映射 ${\phi _j}$ , 可以将原始训练数据集D转换为标记 ${l_j}$ 对应的二分类训练集Z. 之后在新的训练集Z上进行模型的训练, 可以构建出一个基于标记特定特征推导出的二分类器簇 $\left\{ {{g_1},{g_2}, \cdot \cdot \cdot ,{g_q}} \right\}$ . 一般地, 对于标记 ${l_j} \in {\cal{Y}}$ , 其对应的二分类训练数据集 ${{D}}_j^*$ 可由映射 ${\phi _j}$ 表示为:

${{D}}_j^* = \left\{ {\left( {{\phi _j}\left( {{x_i}} \right),{Y_i}\left( j \right)} \right)|\left( {{x_i},{Y_i}} \right) \in D} \right\}$

(7)

其中, 如果标记 ${l_j} \in {Y_i}$ , ${Y_i}\left( j \right) = 1$ , 否则 ${Y_i}\left( j \right) = 0$ . 基于训练数据集 ${{D}}_j^*$ , 可推导出一个分类器 $g_j^*:{Z_j} \to R$ . 对于未知示例u, 其对应的标记集合可以形式化的表示为 $Y = \left\{ {{l_k}|g_k^*\left( {{\phi _k}\left( {{u}} \right)} \right) > t,1 \le k \le q} \right\}$ , 其中t代表一个阙值函数, 一般设置为常数0.

2.2.2 MLF-KNN算法

ML-KNN算法属于一阶策略算法, 在模型训练过程中没有考虑标记之间的相关性信息, 同时在预测标记时是基于相同的属性特征集合, 忽略了每个标记所独有的属性特征信息, 因此ML-KNN算法存在优化改进的空间. LIFT算法经过大量实验表明该算法的分类性能与其它多标记学习算法相比具有一定的竞争力, 证明了在模型训练过程中引入标记特定特征信息可以提高算法分类性能这一思路的可行性和有效性. 为此, 我们借鉴该思路, 对ML-KNN算法进行改进, 并且融入标记相关性信息, 提出基于标记特定特征新的多标记分类新算法MLF-KNN (Multi-Label Feature-K Nearest Neighbor). 本算法首先对多标记训练样本集合进行预处理, 通过对每个类别标记进行聚类分析构建基本标记特征, 之后通过稀疏正则化的方式协同增强与其它类别标记的信息从而增强对每个标记特征信息的表述, 进而引入当前标记与其它标记之间的相关性. 基于得到的标记特定特征, 使用改进后的ML-KNN算法进行分类. 不失一般性, 引入一些符号进行本算法的说明. 在模型训练之前, 首先需要构建每个标记所对应的正负相关示例集合. 对于训练样本中的每个标记 ${l_k} \in {\cal{Y}}\left( {1 \le k \le q} \right)$ , MLF-KNN算法根据式(4)和式(5)将原始示例集合分为 ${m_k}$ 个正相关特征集合 ${P_k}$ 和 ${m_k}$ 个负相关特征集合 ${N_k}$ , 其中 ${m_k} = r \cdot {\rm{min}}\left( {\left| {{l_k} \in {Y_k}} \right|,\left| {{l_k} \notin {Y_k}} \right|} \right)$ . 之后在集合 ${P_k}$ 和 ${N_k}$ 中采用K-means聚类算法构建聚类中心, 用于构建基本标记特征空间. 在正相关示例集合 ${P_k}$ 中聚类中心可以通过 $\left\{ {p_1^{{k}},p_2^k, \cdot \cdot \cdot ,p_{{m_k}}^k} \right\}$ 表示, 负相关特征集合 ${N_k}$ 中聚类中心可以通过 $\left\{ {n_1^k,n_2^k, \cdot \cdot \cdot ,n_{{m_k}}^k} \right\}$ 表示. 对于示例 ${{x}} \in {\cal{X}}$ , 可通过计算示例x与聚类中心之间的距离构建其基本标记特征, 最终生成的基本标记特征空间是一个大小为 $2{m_k}$ 的矩阵 ${\phi _k}:{\cal{X}} \to {\mathbb{R}^{2{m_k}}}$ .

$ {\phi _k}\left( x \right) = {\left[ {d\left( {x,p_1^k} \right), \cdot \cdot \cdot ,d\left( {x,p_{{m_k}}^k} \right),d\left( {x,n_1^k} \right), \cdot \cdot \cdot ,d\left( {x,n_{{m_k}}^k} \right)} \right]^{\rm{T}}} $

(8)

其中, $d\left( { \cdot , \cdot } \right)$ 不在采用LIFT算法中的欧式距离进行度量, 而是采用标准欧式距离进行计算, 相比于欧式距离, 标准欧式距离对于两个向量中的维度不一致的情况进行了考虑, 对于维度不一致的示例具有更好的包容性, 根据式(7), 生成标记 ${l_k}$ 的基本特定特征空间. 此时基本标记特定特征空间只是针对标记 ${l_k}$ 所构建, 并未考虑 ${l_k}$ 与其它标记之间的相关性. 假设 ${y_k} = {\left[ {{y_{k1}},{y_{k2}}, \cdot \cdot \cdot ,{y_{km}}} \right]^{\rm{T}}}$ 代表标记向量 ${l_k}$ , 类似的, 如果 ${l_k} \in {Y_i}$ , 则 ${y_{ki}} = 1$ , 否则 ${y_{ki}} = 0$ . 进一步, 设定:

${\varphi _k}\left( x \right) = {\left[ {{\phi _1}\left( x \right), \cdot \cdot \cdot ,{\phi _{k - 1}}\left( x \right),{\phi _{k + 1}}\left( x \right), \cdot \cdot \cdot ,{\phi _q}\left( x \right)} \right]^{\rm{T}}}$

(9)

其中, ${\varphi _k}\left( x \right)$ 表示除标记 ${l_k}$ 以外的其它所有类别标记的特定特征信息, 是一个维度为 ${d_k}$ 的特征向量, 其中 ${d_k} = {\displaystyle\sum\nolimits_{k' \ne k}}2{m_{k'}}$ . 将映射 ${\phi _k}$ 应用于全部训练样本上, 从而可以构建出关于标记 ${l_k}$ 并且维度为 $m \times {d_k}$ 的标记特定特征矩阵 ${{{X}}_k}$ , 其中 ${{{X}}_k} = {\left[ {{\varphi _k}\left( {{x_1}} \right),{\varphi _k}\left( {{x_2}} \right), \cdot \cdot \cdot ,{\varphi _k}\left( {{x_m}} \right)} \right]^{\rm{T}}}$ . 为了解决ML-KNN算法并未考虑标记之间相关性的问题, 我们需要对标记之间相关性进行挖掘并将相关性信息引入标记特定特征空间中. 具体来说, 需要通过引入标记 $ {l}_{k} $ 与其它类别标记之间的相关性对之前生成的基本标记特征空间 ${{{X}}_k}$ 进行增强. 在本方法中将标记之间相关性问题转换为最小二乘法优化问题, 通过引入L₁正则化项对其进行优化求解从而引入标记 $ {l}_{k} $ 与其它类别标记之间的相关性, 优化最小二乘法问题如下:

$\mathop {\min }\limits_{{\beta _k} \in {\mathbb{R}^{{d_k}}}} \left| {\left| {{y_k} - {{{X}}_k} \cdot {\beta _k}} \right|} \right|_2^2 + \lambda \cdot {\left| {\left| {{\beta _k}} \right|} \right|_1}$

(10)

其中, ${\;\beta _k} = {\left[ {{\beta _{k1}},{\beta _{k2}}, \cdot \cdot \cdot ,{\beta _{k{d_k}}}} \right]^{\rm{T}}}$ 为权值向量, 代表对每一个标记的影响程度, $ \lambda $ 代表正则系数. 使用稀疏回归方法解决上述最小二乘法问题后, 即可得到其它类别标记所独有的特征信息, 进而通过与权值向量 ${\;\beta _k}$ 结合对矩阵 ${\phi _k}$ 进行增强, 通过增强 ${\phi _k}$ 即可引入 ${l_k}$ 与其它类别标记信息之间的相关性. 使用集合 ${{\cal{I}}_k}$ 存储在 ${\varphi _k}$ 中权值大于阙值 $\gamma $ 的索引.

${{\cal{I}}_k} = \{ a|\left| {{\beta _{ka}}} \right| \ge \gamma ,1 \le a \le {d_k}\} $

(11)

根据之前生成的基本标记特征空间 ${\phi _k}$ 中的数值取值介于0到1之间, 在此我们将阙值 $\gamma $ 设定为常数值0.5. 对于标记 ${l_k}$ , 通过融合标记相关性信息后对基本标记特征进行增强, 即可生成最终标记特定特征 $ {\psi }_{k}: {\cal{X}}\to {Z}_{k}$ , 其中 ${\psi _k}\left( {{x}} \right)$ 表示形式如下:

${\psi _k}\left( {{x}} \right) = \left[ {{\phi _k}\left( {{x}} \right),{\prod\nolimits _{{{\cal{I}}_k}}}\left( {{\varphi _k}\left( {{x}} \right)} \right)} \right]$

(12)

其中, ${\displaystyle\prod \nolimits_{\cal{I}}}\left( {{u}} \right) $ 代表在索引集 ${\cal{I}}$ 上对u的投影操作. 综上, 关于标记l_k的二分类训练集合D_k能够表达为:

${{{D}}_{{k}}} = \left\{ {\left( {{\psi _k}\left( {{{{x}}_i}} \right),{y_{ki}}} \right)|1 \le i \le m} \right\}$

(13)

针对训练样本中的每一个标记类别分别构造其特定特征空间, 在标记空间集合中应用改进后的ML-KNN算法进行模型训练, 其中在计算两个标记之间距离时MLF-KNN算法不同于ML-KNN采用欧式距离直接计算, 而是采用如下r阶Minkowski距离进行计算^[16].

$dist({{x}},{{y}}) = {\left({\sum\limits_{l = 1}^d {\left\| {{{{x}}^l} - {{{y}}^l}} \right\|} ^r}\right)^{1/r}}$

(14)

其中, x^l代表示例x的第l维, ||·||表示取该实数值的绝对值. 在计算两个样本之间的距离时采用Minkowski距离度量方法的主要出发点是考虑到不同数据集内数据可能具有不同分布从而需要采取不同的距离计算方法, 采用Minkowski方法可以提高本算法对不同数据集的包容性. 当阶数取值为1时, 可以转换为曼哈顿距离. 当阶数取值为2时, 可以转换为欧氏距离. 当阶数继续增大到无穷大时可转换为切比雪夫距离. 在本实验中所采用的数据集中的数据取值规范, 分布较为独立, 因此设定r值为2转换为欧式距离进行试验. 当数据集中的数据分布具有关联性或者局限性时, 可以改变r值的取值以适配不同的数据分布. MLF-KNN算法描述如算法1所示.

算法1. MLF-KNN算法

步骤1. 构造基本标记特征集.

　　For $\scriptstyle {l_k}$ in $\scriptstyle {\cal{Y}} = \left\{ {{l_1},{l_2}, \cdots,{l_q}} \right\}$ do

　　　　利用式(4)和式(5)构建标记正相关样本集 $\scriptstyle {P_k}$ 和负相关样本集 $\scriptstyle {N_k}$ ;

　　End for

　　For $\scriptstyle {l_k}$ in $\scriptstyle {\cal{Y}} = \left\{ {{l_1},{l_2}, \cdots,{l_q}} \right\}$ do

　　　　通过式(8)构建针对 $\scriptstyle {l}_{k} $ 的标记特征映射 $\scriptstyle {\phi }_{k} $ ;

　　End for

步骤2. 增强基本标记特征集, 构建标记特征.

　　For $\scriptstyle {l_k}$ in $\scriptstyle {\cal{Y}} = \left\{ {{l_1},{l_2}, \cdots,{l_q}} \right\}$ do

　　　　通过对式(10)进行L₁-范数正则化计算权重向量 $\scriptstyle {\;\beta }_{k} $ ;

　　　　通过式(11), 式(12), 构建最终标记特征;

　　End for

步骤3. 构建二分类训练集 $ \scriptstyle {{\cal{D}}}_{k} $ .

　　For $\scriptstyle {l_k}$ in $\scriptstyle {\cal{Y}} = \left\{ {{l_1},{l_2}, \cdots,{l_q}} \right\}$ do

　　　　根据式(13)构建标记 $\scriptstyle {l}_{k} $ 的二分类训练集 $\scriptstyle {{\cal{D}}_k}$ ;

　　End for

步骤4. 计算先验概率.

　　For $\scriptstyle {l_k}$ in $\scriptstyle {\cal{Y}} = \left\{ {{l_1},{l_2}, \cdots ,{l_q}} \right\}$ do

　　　　　计算标记 $\scriptstyle {l}_{k} $ 的先验概率:

　　　　　 $\scriptstyle P\left( {H_b^l} \right)\left( {b \in \left\{ {0,1} \right\},l \in {\cal{Y}}} \right) $ ;

　　End for

步骤5. 计算示例在标记特定特征空间中的k近邻集合.

　　For $\scriptstyle x_i^k$ in $\scriptstyle {{\cal{D}}_k}$ do

　　　　通过式(14)计算k近邻集合 $\scriptstyle N\left( {{x}} \right)$ , 从而根据式(1)计算 $\scriptstyle {C_x}\left( l \right)$

　　End for

步骤6. 计算各类标记条件概率 $\scriptstyle P{\rm{(}}E_{{C_x}\left( l \right)}^l{\rm{|}}H_1^l)$ 和条件概率 $\scriptstyle P{\rm{(}}E_{{C_x}\left( l \right)}^l{\rm{|}}H_0^l)$ .

步骤7. 对待测样例t进行分类, 通过式(8)构建新的样本表达 $\scriptstyle {{{t}}_{{k}}}$ , 分别在 $\scriptstyle {{\cal{D}}_k}$ 计算 $\scriptstyle N\left( {{t}} \right)$ 和 $\scriptstyle {C_t}\left( l \right)$ , 利用式(3)计算其对应的标记向量 $\scriptstyle {Y_t}$ .

3 实验

为了检验MLF-KNN算法的分类效果, 将本算法与ML-KNN, LIFT, Rank-SVM等3个多标记学习算法在公开酵母数据集yeast和图像数据集image上进行比较. 其中ML-KNN算法基于传统k近邻技术处理多标记问题, 基于已有样本的先验概率, 通过在训练样本中寻找距离最近的k个实例从而对未知示例进行标记预测. 但是该方法没有考虑标记之间的关联信息, 属于算法适应型一阶策略算法. LIFT算法通过构造每一个标记独有的特征信息, 基于标记独有的示例集合进行模型训练, 是从标记特征信息研究的新型算法, 但是同样没有引入标记之间的相关信息, 也属于一阶策略算法. Rank-SVM算法使用最大化间隔思想处理多标记问题, 该算法的核心是通过一组线性分类器对Ranking Loss指标进行优化, 并通过引入“核技巧”处理非线性分类问题^[9], 属于算法适应型二阶策略算法. 实验所采用的数据集yeast和image在多标记学习领域是两个公开的数据集, 分别在生物领域和图像领域具有一定的代表性, 两个数据集详细信息如表1所示.

由于每个示例同时类属于多个标记, 因此传统的单标记评价指标例如精度(accuracy)、查准率(precision)和查全率(recall)等指标不再适用. 本文评价指标基于Haming Loss, One-error, Coverage, Ranking Loss, Average Precision^[17]等5种在多标记学习领域广泛使用的评价指标. 其中, 对于Average Precision指标信息, 数值越大代表分类性能越好, 在表中使用 $ \uparrow $ 表示, 其余评价指标数值越小则代表其分类性能越好, 在表中使用 $ \downarrow $ 表示. 表2为各个算法在数据集yeast上的测试结果, 表3为在数据集image上的测试结果. 本文提出的算法基于ML-KNN改进而来, 图1为MLF-KNN算法与ML-KNN算法在数据集yeast上的随k值变化的Coverage评价指标对比结果图

由图1可以看出, 本文提出的算法相比于ML-KNN算法在Coverage评价指标上表现性能十分优异, 当k值继续增大时, Coverage值可以接近最优解1.0, 代表MLF-KNN算法对于测试样本的预测所有相关性标记的平均查找深度小, 分类性能有所提高. 由表2和表3的对比实验结果图可以看出, 本文所提出的算法MLF-KNN在数据集yeast当中表现优异. 反映在具体评价指标上, MLF-KNN算法在One-error, Ranking Loss和Average Precision指标上表现不是最优, 虽然Ranking Loss指标上的表现低于LIFT算法, 但是相比ML-KNN算法而言该评价指标有所提高. 在数据集image中, 本算法同样在评价指标Haming Loss和Coverage上表现最优. 实验结果表明对ML-KNN算法引入标记特定特征和标记相关性进行改进可以进一步提高算法分类性能, 尤其在Coverage上表现更为明显, 同时也证明了从标记特定特征对算法进行改进创新这一思路的有效性.

4 结论与展望

ML-KNN算法在模型训练过程中没有考虑到标记之间的相关性, 同时在预测不同标记时基于同一特征空间, 忽略了每个标记所特定的标记特征. LIFT算法从利用每个标记所独有的特征出发, 为多标记学习研究指明了一个新的方向. 基于此, 我们对ML-KNN算法进行改进, 在构造标记特征空间的同时对其进行增强, 引入与其它标记之间的相关性, 提高了算法分类性能. 在之后的工作中, 可以进一步对构建标记特征空间的方法进行创新, 另外本算法并未对标记不平衡的问题进行考虑, 当正负标记样本数量差异过大时会制约算法的分类性能, 所以下一步工作可以将当前多标记学习领域对正负标记不平衡问题的研究^[18]引入到本算法当中.