2019, Vol. 51
2. 华南理工大学 计算机科学与工程学院, 广州 510006
2. School of Computer Science & Engineering, South China University of Technology, Guangzhou 510006, China
传统监督学习假设一个实例只属于一个标签类别[1].虽然传统监督学习在许多学习任务中得到广泛的应用，但是对于某些学习任务，其假设并不成立.因为随着数据量的不断增大，数据标签的复杂度也在增加，单一的样本可能同时具有多个语义含义.例如，在语义场景分类中，一篇新闻报道可能同时分类到社会、体育和娱乐等多个主题；在音乐类型分类中，一首歌可能同时属于摇滚和抒情类别; 在图片标注中，一张图片可能同时被标注为建筑和城市.为了解决一个实例同时具有多个语义含义的问题，一个直接的方法是对一个实例赋予多个标签，以显式表达它的多个语义.基于以上考虑，多标签学习已经成为当代研究的一个热点.在多标签学习中，由于考虑了一个实例可能同时被标记为多种标签类别的情况，它与传统监督学习相比较，更适合用于实际生活中.多标签学习的早期研究主要集中在多标签文本分类问题[2].但随着多标签学习的发展，如今多标签学习已被广泛应用在自动注释的各种问题上，比如图像分类[3]、生物信息学[4]、网络挖掘[5]、规则挖掘[6]、信息检索[7]以及标记推荐[8]等.
多标签学习算法主要分为问题转换方法和算法适应方法.问题转换方法将多标签问题转换成其他已知的学习问题进行求解.问题转换方法的代表性算法有二元关联(Binary Relevance, BR)、组合分类器链[9] (Ensembles of Classifier Chains, ECC)、校准的标签排序算法[10](Calibrated Label Ranking, CLR)和随机k标签集[11](Random K-labelsets, RAKEL)等.算法适应方法改进已有的流行算法，直接处理多标签数据.算法适应方法的代表性算法有多标签k最近邻分类算法[12-15](ML-KNN)、多类多标记组合分类[16] (MMAC)、条件随机场[17-18] (Conditional Random Fields, CRF)、反向传播多标签学习法[19](BP-MLL)等方法.
现今，多标签学习热点研究中存在两个问题.其一，在多标签学习中，随着标签类别数量的增加，实例预测的可能标签集合的数量会指数增长.例如，在多标签学习中，标签空间有20个标签类别，则实例可能的标签集合将超过1百万(即220)个.为了解决该问题，现有的算法主要研究标签类别间的联系[20].其二，由于类的正样本/负样本数量可能远远少于负样本/正样本数量，多标签学习存在类的不平衡问题，该问题也导致大多数分类方法性能的下降[21].例如在预测肺癌的场景中，肺癌患者在所有来诊病人中所占的比例非常低.在该场景下如果直接构建模型，会导致数据集以负样本为主，只有很少的正样本.由于分类模型的目标是希望准确率尽可能达到最高，因此该场景问题最终会导致预测的结果全部偏向负样本，但在实际生活中，医生和病人往往更加关注肺癌患者的情况，对非肺癌患者的关注度并没有那么高.所以类不平衡问题会严重影响到分类的效果.长期以来，类不平衡一直被视为危及机器学习算法性能的一个基本威胁.在多标签学习中，已有的算法基本没有充分考虑类不平衡问题.
本文在学习多标签问题时，提出了同时考虑多标签间相关性与多标签不平衡问题的学习模型.该学习模型针对每个标签类别，通过耦合其他标签类别以考量标签间的关联性，并缓解标签间不均衡比率，是一个将当前标签的二类不平衡学习器和多个与其他标签耦合的多类不平衡学习器结合的集成分类器(multi-label learning model based on label correlation and imbalance, MLCI).
1 方法描述 1.1 多标签问题的定义在多标签学习中，一个实例被赋予多个标签.假设X = Rn表示n维的实例空间，Y ={y1, y2, …, yq}表示标签空间，该标签空间有q个可能的标签类别.多标签学习的任务是，从多标签训练数据集D ={(xi, Yi)|1≤i≤m}中学习一个函数h: X →2Y.对于每个多标签实例(xi, Yi)，xi∈ X是一个n维的特征向量(xi1，xi2，…，xin)T，Yi∈ Y是实例xi的标签集合.对于任何一个测试实例x ∈ X，多标签分类器h(·)预测x的标签集合h(x)∈ Y.在一般的情况下，多标签学习系统学习的实数值函数一般返回一个实数：fk: X → R，fk(X)表示X被yk标记的信心，每个标签类别伴随着一个阈值函数tk: X → R.因此，预测标签集合的函数h(x)一般等价于
| $ h\left( \mathit{\boldsymbol{x}} \right) = \left\{ {{y_k}\left| {{f_k}\left( \mathit{\boldsymbol{x}} \right) > {t_k}\left( \mathit{\boldsymbol{x}} \right)} \right.,1 \le k \le q} \right\}. $ |
该算法不仅考虑了标签类别之间的相关性，也考虑了标签的类不平衡问题.令D k+和D k-分别表示根据标签类别yk，对数据集D进行划分得到的正训练样本数据集和负训练样本数据集.
| $ \mathit{\boldsymbol{D}}_k^ + = \left\{ {\left( {{\mathit{\boldsymbol{x}}_i}, + 1} \right)\left| {{y_k} \in {\mathit{\boldsymbol{Y}}_i}} \right.,1 \le i \le m} \right\}, $ |
| $ \mathit{\boldsymbol{D}}_k^ - = \left\{ {\left( {{\mathit{\boldsymbol{x}}_i}, + 1} \right)\left| {{y_k} \notin {\mathit{\boldsymbol{Y}}_i}} \right.,1 \le i \le m} \right\}. $ |
标签yk的类不平衡率为
| $ {\rm{I}}{{\rm{R}}_k} = \max \left( {\left| {\mathit{\boldsymbol{D}}_k^ + } \right|,\left| {\mathit{\boldsymbol{D}}_k^ - } \right|} \right)/\min\left( {\left| {\mathit{\boldsymbol{D}}_k^ + } \right|,\left| {\mathit{\boldsymbol{D}}_k^ - } \right|} \right). $ |
式中IRk表示标签yk的类不平衡率.由于类的不平衡，IRk的值将会很大.例如，在本文实验中所采用的4个多标签数据集中，标签空间的最大类不平衡率从3.0到24.4.
为了同时解决标签类别之间存在关联性和类不平衡问题，本文对于每个标签类别，构建一个对应于当前标签的二类不平衡学习器，以及多个与其他标签耦合的多类不平衡学习器.之后，通过聚合二类学习器和多类学习器产生的输出，获得对每个类标签的最终预测.
1.2.1 二类不平衡学习器该算法对多标签数据集进行处理，采用问题转换方法，将多标签问题转换为q个独立互不影响的二元分类问题.
令Dk表示根据第k个类标签yk, 划分数据集D而得到的二类训练数据集，则Dk为
| $ {\mathit{\boldsymbol{D}}_k} = \left\{ {\left( {{\mathit{\boldsymbol{x}}_i},\mathit{Ø}\left( {{\mathit{\boldsymbol{Y}}_i},{y_k}} \right)} \right)\left| {1 \le i \le m} \right.} \right\}. $ | (1) |
式中
因此，Dk+表示了二类训练数据集Dk的正样本数据集，Dk-表示了二类训练数据集Dk的负样本数据集，IRk表示了二类训练数据集的类不平衡率.
对于分解后的二元分类问题，为了解决Dk+和Dk-之间的数据量不平衡问题，可以采用已有的二元类不平衡学习方法解决，比如过采样、欠采样方法.由于本文针对yeast、scene、emotions和CAL500这4个开放数据集进行分类处理，而这4个开放数据集的样本数量过少，因此本文采用了合成少数样本过采用算法[22] (Synthetic Minority Over-sampling Technique，SMOTE)，添加部分样本的副本.
SMOTE算法对少数类样本进行分析并根据少数类样本人工合成新样本添加到数据集中. SMOTE算法流程如下：
1) 以欧式距离为基准，根据样本到少数类样本集中所有样本的距离，计算得到少数类样本集中每一个样本x的k个近邻.
2) 根据类不平衡比例设置采样倍率r，对于少数类中的每一个样本x，从其K近邻中随机选择r个样本.
3) 对于每一个随机选出的近邻xk，分别与原样本x构建新的样本添加到数据集中：
| $ \mathit{\boldsymbol{x'}} = \mathit{\boldsymbol{x}} + {\rm{rand}}\left( {0,1} \right) * \left| {\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{xk}}} \right|. $ |
本文对数据集Dk采用二元类不平衡方法中的SMOTE算法来学习二元分类器gk，即gk←§(Dk).令gk(+1| x)表示对于标签类别yk，样本x被预测为正样本的信心.换而言之，实数值函数fk(x)=gk(+1| x).而阈值函数tk(x)可以被简单设置为常数函数，比如tk(x)=0.
1.2.2 多类不平衡学习器考虑到标签类别之间存在关联性，本文随机选择2个标签ya，yb作为yk的耦合标签.
令Dkab表示根据标签对(yk，ya，yb)划分数据集D而得到的多类训练数据集，则Dkab为
| $ {\mathit{\boldsymbol{D}}_{kab}} = \left\{ {\left( {{\mathit{\boldsymbol{x}}_i},\varphi \left( {{\mathit{\boldsymbol{Y}}_i},{y_k},{y_a},{y_b}} \right)} \right)\left| {1 \le i \le m} \right.} \right\}, $ |
式中φ(Yi, yk, ya, yb)表示数据集Dkab中实例的类别，即
| $ \begin{array}{l} \varphi \left( {{\mathit{\boldsymbol{Y}}_i},{y_k},{y_a},{y_b}} \right) = \\ \;\;\;\;\;\;\left\{ \begin{array}{l} 0,\;\;\;{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \notin {\mathit{\boldsymbol{Y}}_i};\\ + 1,{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \in {\mathit{\boldsymbol{Y}}_i};\\ + 2,{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \notin {\mathit{\boldsymbol{Y}}_i};\\ + 3,{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \in {\mathit{\boldsymbol{Y}}_i};\\ + 4,{\rm{if}}\;{y_k} \in {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \notin {\mathit{\boldsymbol{Y}}_i};\\ + 5,{\rm{if}}\;{y_k} \in {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \in {\mathit{\boldsymbol{Y}}_i};\\ + 6,{\rm{if}}\;{y_k} \in {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \notin {\mathit{\boldsymbol{Y}}_i};\\ + 7,{\rm{if}}\;{y_k} \in {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \in {\mathit{\boldsymbol{Y}}_i}. \end{array} \right. \end{array} $ |
在学习过程中，尽管利用Dkab考虑了标签类别间的关联性，但是联合考虑yk，ya，yb将会放大类的不平衡问题.假设在二类训练数据集Dk(Da, Db)中，Dk+(Da+, Db+)是相应的少数类样本集，则在多类训练数据集Dkab中，第一个类φ(Yi, yk, ya, yb)=0的样本数将会是最多的，而第八个类φ(Yi, yk, ya, yb)=7的样本数将会是最少的.
令Nkabj表示数据集Dkab中，φ(Yi, yk, ya, yb)=j的样本数，即Nkabj为
| $ {N_{kabj}} = \left| {\left\{ {{\mathit{\boldsymbol{x}}_i}\left| {1 \le i \le m,\varphi \left( {{\mathit{\boldsymbol{Y}}_i},{y_k},{y_a},{y_b}} \right)} \right. = j} \right\}} \right|. $ | (2) |
IRk，IRa，IRb分别表示二类训练数据集Dk，Da，Db的类不平衡率，因此，在假设样本分布均匀的条件下，在Dkab数据集中，第一个类φ(Yi, yk, ya, yb)=0的样本数与第八个类的样本数的比例IRkab07为
| $ {\rm{I}}{{\rm{R}}_{kab07}} = \frac{{{N_{kab0}}}}{{{N_{kab7}}}} = \frac{{{N_{kab0}}}}{{{N_{kab1}}}} \times \frac{{{N_{kab0}}}}{{{N_{kab3}}}} \times \frac{{{N_{kab3}}}}{{{N_{kab7}}}}. $ | (3) |
根据式(2)和式(3)，可知IRkab07为
| $ {\rm{I}}{{\rm{R}}_{kab07}} \approx {\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_a} \times {\rm{I}}{{\rm{R}}_k}. $ |
为了解决IRb×IRa×IRk即IRkab07过大的问题，本文将第五、六、七、八类合并成一个新类，将Dkab转换成一个新的数据集
| $ {\mathit{\boldsymbol{D}}_{kab}}^\prime = \left\{ {\left( {{\mathit{\boldsymbol{x}}_i},\varphi '\left( {{\mathit{\boldsymbol{Y}}_i},{y_k},{y_a},{y_b}} \right)} \right)\left| {1 \le i \le m} \right.} \right\}, $ |
式中，
| $ \begin{array}{l} \varphi '\left( {{\mathit{\boldsymbol{Y}}_i},{y_k},{y_a},{y_b}} \right) = \\ \;\;\;\left\{ \begin{array}{l} 0,\;\;\;\;\;{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \notin {\mathit{\boldsymbol{Y}}_i};\\ + 1,\;\;\;{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \in {\mathit{\boldsymbol{Y}}_i};\\ + 2,\;\;\;{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \in {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \notin {\mathit{\boldsymbol{Y}}_i};\\ + 3,\;\;\;{\rm{if}}\;{y_k} \notin {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_a} \in {\mathit{\boldsymbol{Y}}_i}\;{\rm{and}}\;{y_b} \in {\mathit{\boldsymbol{Y}}_i};\\ + 4,\;\;\;{\rm{if}}\;{y_k} \in {\mathit{\boldsymbol{Y}}_i}. \end{array} \right. \end{array} $ |
令IRkabzw′表示在新的数据集Dkab′中，类φ′(Yi, yk, ya, yb)=z的样本数与类φ′(Yi, yk, ya, yb)=w的样本数的比例.因此第一类φ′(Yi, yk, ya, yb)=0的样本数与第五类类φ′(Yi, yk, ya, yb)=4的样本数的比例IRkab04′为：
| $ {\rm{I}}{{{\rm{R'}}}_{kab04}} = \frac{{{N_{kab0}}}}{{{N_{kab4}} + {N_{kab5}} + {N_{kab6}} + {N_{kab7}}}}, $ |
| $ \frac{1}{{{\rm{I}}{{{\rm{R'}}}_{kab04}}}} = \frac{{{N_{kab4}} + {N_{kab5}} + {N_{kab6}} + {N_{kab7}}}}{{{N_{kab0}}}} $ |
| $ \frac{1}{{{\rm{I}}{{{\rm{R'}}}_{kab04}}}} = \frac{{{N_{kab4}}}}{{{N_{kab0}}}} + \frac{{{N_{kab5}}}}{{{N_{kab0}}}} + \frac{{{N_{kab6}}}}{{{N_{kab0}}}} + \frac{{{N_{kab7}}}}{{{N_{kab0}}}} $ |
| $ \begin{array}{l} \frac{1}{{{\rm{I}}{{{\rm{R'}}}_{kab04}}}} = \frac{{{N_{kab4}}}}{{{N_{kab0}}}} + \frac{{{N_{kab5}}}}{{{N_{kab1}}}} \times \frac{{{N_{kab1}}}}{{{N_{kab0}}}} + \frac{{{N_{kab6}}}}{{{N_{kab2}}}} \times \frac{{{N_{kab2}}}}{{{N_{kab0}}}} + \frac{{{N_{kab7}}}}{{{N_{kab3}}}} \times \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{{N_{kab3}}}}{{{N_{kab2}}}} + \frac{{{N_{kab2}}}}{{{N_{kab0}}}}. \end{array} $ | (4) |
根据式(2)和式(4)，可知
| $ \begin{array}{l} \frac{1}{{{\rm{I}}{{{\rm{R'}}}_{kab04}}}} \approx \frac{1}{{{\rm{I}}{{\rm{R}}_k}}} + \frac{1}{{{\rm{I}}{{\rm{R}}_k}}} \times \frac{1}{{{\rm{I}}{{\rm{R}}_b}}} + \frac{1}{{{\rm{I}}{{\rm{R}}_k}}} \times \frac{1}{{{\rm{I}}{{\rm{R}}_a}}} + \frac{1}{{{\rm{I}}{{\rm{R}}_k}}} \times \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{{\rm{I}}{{\rm{R}}_b}}} \times \frac{1}{{{\rm{I}}{{\rm{R}}_a}}}.\\ {\rm{I}}{{{\rm{R'}}}_{kab04}} = \frac{{{\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_a} \times {\rm{I}}{{\rm{R}}_k}}}{{{\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_b} + 1}}. \end{array} $ | (5) |
同理可得，第二类φ′(Yi, yk, ya, yb)=1、第三类φ′(Yi, yk, ya, yb)=2、第四类φ′(Yi, yk, ya, yb)=3的样本数与第五类类φ′(Yi, yk, ya, yb)=4的样本数的比例分别为
| $ {\rm{I}}{{{\rm{R'}}}_{kab14}} \approx \frac{{{\rm{I}}{{\rm{R}}_a} \times {\rm{I}}{{\rm{R}}_k}}}{{{\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_b} + 1}}, $ | (6) |
| $ {\rm{I}}{{{\rm{R'}}}_{kab24}} \approx \frac{{{\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_k}}}{{{\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_b} + 1}}, $ | (7) |
| $ {\rm{I}}{{{\rm{R'}}}_{kab34}} \approx \frac{{{\rm{I}}{{\rm{R}}_k}}}{{{\rm{I}}{{\rm{R}}_b} \times {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_a} + {\rm{I}}{{\rm{R}}_b} + 1}}. $ | (8) |
由式(5)~(8)可知，IRkab04′、IRkab14′、IRkab24′、IRkab34′都远小于IRkab07，因此该算法在一定程度上减轻了多标签学习过程中的类不平衡性.
该算法对数据集Dkab′采用多类不平衡方法￡来学习多类分类器gkab，即gkab←￡(Dkab′).相应地，令gkab(+4| x)表示对于标签类别yk，样本x被预测为正样本的信心.
1.2.3 二类学习器和多类学习器的聚合对于每一个标签类别yk，该算法随机选取r个标签对(ya, yb)(a≠k, b≠k, a≠b)，分别与yk耦合成标签对(yk, ya, yb).数据集D根据标签对(yk, ya, yb)的值构建新的数据集Dkab′，进而根据多类不平衡方法￡来学习r个多类分类器gkab，基于集成学习的线性组合思想，实数值函数fk(x)线性集成了二类分类器和r个多类分类器的预测结果，即fk(x)=gk(+1| x)+
表 1总结了本文提出的算法的完整过程.对于每一个标签类别yk，该算法通过处理多标签训练数据集D，学习一个二类不平衡分类器和r个耦合的多类不平衡分类器.之后，该算法通过集成二类分类器和多类分类器的预测信心，构建针对标签类别yk的预测模型.最后，对测试实例，分别查询每个标签类别的预测模型，从而获取测试实例的预测标签集.
|
表 1 MLCI算法伪代码 Table 1 The pseudo-code of MLCI |
对于每一个标签类别yk，该算法在一个多类分类器中考察了2个标签与该标签yk的关联性，该算法针对一个标签类别，学习r个多类分类器，因此实际上，该算法考察了多个标签与该标签yk的关联性，属于高阶策略思想.
2 实验及分析通过对4个真实多标签数据集进行广泛的实验来验证方法的有效性.在实验中，将MLCI与几个先进的多标签学习方法做对比，并且以20次交叉的方式进行验证，10次实验的平均结果表明，所提的MLCI优于其他算法.
2.1 数据集和评价标准 2.1.1 数据集为了测评算法的性能，本文在Mulan (Mulan网址：http://mulan.sourceforge.net/datasets-mlc.html)平台上调用了4个真实多标签数据集，分别来自图像、音乐和生物信息等方面，对于每个数据集D，我们采用T(D)、I(D)、L(D)、F(D)、C(D)分别表示数据集D的域类型、样本数、标签类别的数量、样本的特征数量以及基数.各个数据集具体的参数详见表 2.
|
|
表 2 数据集的相关信息 Table 2 Characteristics of the data sets |
基于此，分析每个数据集中的数据不均衡问题，各个数据集具体的参数详见表 3，其中，min_IR表示数据集中最小的类不平衡率(min_IR=
|
|
表 3 数据集的类不平衡信息 Table 3 Class-imbalance of the data sets |
在实验中，为了更全面度量本算法与其他算法的效果，本文采用了2种度量方法：基于样本的度量方法和基于标签的度量方法[23].将(xi, Yi)(i=1, .., m)表示为测试数据集中的样本，其中xi是第i个测试样本的特征向量，Yi是测试集中第i个样本的标签集合，γi(λ)表示测试集合中第i个样本标签λ在Yi中的排位.
在基于样本的度量方法中，主要选取了Average-Precision和Ranking-Loss.
Average-Precision方法衡量了分类器对测试集中所有样本的预测标签排序中，排在相关标签前面的标签，也是相关标签概率的平均值.
| $ \begin{array}{l} {\rm{Average}} - {\rm{Precision}} = \\ \frac{1}{m}\sum\limits_{i = 1}^m {\frac{1}{{\left| {{\mathit{\boldsymbol{Y}}_i}} \right|}}} \sum\limits_{\lambda \in {\mathit{\boldsymbol{Y}}_i}} {\frac{{\left| {\left\{ {\lambda ' \in {\mathit{\boldsymbol{Y}}_i}:{\gamma _i}\left( {\lambda '} \right) \le } \right\}{\gamma _i}\left( \lambda \right)} \right|}}{{{\gamma _i}\left( \lambda \right)}}} . \end{array} $ |
Ranking-Loss方法衡量了分类器对测试集中所有样本的预测标签排序中，排在相关标签前面的标签，是不相关标签概率的平均值.
| $ \begin{array}{l} {\rm{Ranking}} - {\rm{Loss}} = \frac{1}{m}\sum\limits_{i = 1}^m {\frac{1}{{\left| {{\mathit{\boldsymbol{Y}}_i}} \right|\left| {{{\mathit{\boldsymbol{\bar Y}}}_i}} \right|}}\left| {\left\{ {\left( {{\lambda _a},{\lambda _b}} \right):} \right.} \right.} \\ \;\;\;\;\;\left. {\left. {{\gamma _i}\left( {{\lambda _a}} \right) > {\gamma _i}\left( {{\lambda _b}} \right)\left( {{\lambda _b}} \right),\left( {{\lambda _a},{\lambda _b}} \right) \in {\mathit{\boldsymbol{Y}}_i},{{\mathit{\boldsymbol{\bar Y}}}_i}} \right\}} \right|. \end{array} $ |
基于标签的度量方法是预测每个单独的标签，然后对所有标签的结果取平均值进行度量，在单标签度量方法中，将tpλ, tnλ, fpλ, tpλ分别表示第λ标签的正阳例(true positives, TP)，负阳例(true negatives, TN)，正阴例(false positives, FP)，负阴例(true negatives, TN)的数目.在这种度量方法中有2种方法用以实现平均值：宏观平均(Macro-Averaging)和微观平均(Micro-Averaging)：
| $ {\rm{Macro}} - {\rm{Averaging}} - {\rm{B}} = \frac{1}{m}\sum\limits_\lambda ^m {B\left( {{\rm{t}}{{\rm{p}}_\lambda },{\rm{t}}{{\rm{n}}_\lambda },{\rm{f}}{{\rm{p}}_\lambda },{\rm{t}}{{\rm{p}}_\lambda }} \right)} , $ |
| $ {\rm{Micro}} - {\rm{Averaging}} - {\rm{B}} = B\left( {\sum\limits_{\lambda = 1}^m {{\rm{t}}{{\rm{p}}_\lambda }} ,\sum\limits_{\lambda = 1}^m {{\rm{t}}{{\rm{n}}_\lambda }} ,\sum\limits_{\lambda = 1}^m {{\rm{f}}{{\rm{p}}_\lambda }} ,\sum\limits_{\lambda = 1}^m {{\rm{t}}{{\rm{p}}_\lambda }} } \right). $ |
其中，B代表的是二元分类器中F1和AUC评价标准.
2.2 对比算法及实验分析为了全面的进行对比，本文选取了7个对比算法，分别是交叉耦合的聚合算法[24] (Cross-coupling Aggregation, COCOA)，ML-kNN[12]，BP-MLL[19]，结合实例和逻辑回归的多标签分类[25](Combining Instance-Based Learning and Logistic Regression for Multilabel classification, IBLR)，ECC[9]，CLR[10]，RAKEl[11].
实验结果包括MLCI与对比算法在4组数据集上的性能测评结果，结果采用度量标准的平均值和标准差表示，在表中，符号↑表示测评结果的值越大，对应的算法性能越好；符号↓表示测评结果的值越小，对应的算法性能越好.由于文章边幅有限，本文不详细描述每次实验的性能测试结果，仅描述10次实验的平均性能测评结果.
2.2.1 基于样本的度量方法上的性能评判在基于样本的度量方法中，MLCI与对比算法在4个数据集上的性能测评结果如表 4，表 5所示.在Average-Precision评价标准中，MLCI在4个数据集中此评测标准整体高于其他对比算法.具体分析中，MLCI在scene和CAL500数据集上的平均差值要更优于在数据集yeast和emotions上的平均差值，说明数据集标签分布越不均衡，MLCI得到的相关标签的概率越高，效果越好.在Ranking-Loss评价标准中，MLCI在4个数据集中此评测标准整体高于其他对比算法.此外，MLCI在yeast数据集和CAL500数据集和yeast数据集上的表现要更由于另2个数据集，说明数据集Cardinality值越大，MLCI得到的不相关标签概率越低，效果越好.
|
|
表 4 在每个数据集上，每种算法的Average-Precision性能(↑) Table 4 Performance of each algorithm in terms of Average-Precision in each data set(↑) |
|
|
表 5 在每个数据集上，每种算法的Ranking-Loss性能(↓) Table 5 Performance of each algorithm in terms of Ranking-Loss in each data set(↓) |
在基于标签的度量方法中，MLCI与对比算法在4个数据集上的性能测评结果如表 6~9所示.在Macro-Averaging F1评价标准中，MLCI在4个数据集中此评测标准整体高于其他对比算法.但是在Micro-averaging F1评价标准中，MLCI的效果略有下降，特别是在数据集上yeast数据集上的表现并不理想.在Macro-Averaging AUC和Micro-Averaging AUC评价标准中，MLCI在4个数据集中此评测标准整体都高于其他对比算法，并且效果表现的较为平均.
|
|
表 6 在每个数据集上，每种算法的Macro-Averaging F1性能(↑) Table 6 Performance of each algorithm in terms of Macro-Averaging F1 in each data set(↑) |
|
|
表 7 在每个数据集上，每种算法的Micro-Averaging F1性能(↑) Table 7 Performance of each algorithm in terms of Micro-Averaging F1 in each data set(↑) |
|
|
表 8 在每个数据集上，每种算法的Macro-Averaging AUC性能(↑) Table 8 Performance of each algorithm in terms of Macro-Averaging AUC in each data set(↑) |
|
|
表 9 在每个数据集上，每种算法的Micro-Averaging AUC性能(↑) Table 9 Performance of each algorithm in terms of Micro-Averaging AUC in each data set(↑) |
为进一步提高多标签学习中的预测效果，本文提出一种改进多标签学习的算法，针对多标签中标签不平衡问题，考量标签与标签之间相互关联性，提出了一种二类不平衡分类器，与多类不平衡分类器结合的耦合分类器.为验证本文提出的算法的有效性，在4种不同类型的数据集上进行不同评价标准的测评.实验结果表明，本文提出的算法比其他7种对比算法优势明显.下一阶段将围绕如何解决在线多标签学习中标签不均衡的问题开展研究.
| [1] |
ZHANG Minling, ZHOU Zhihua. A review on multi-label learning algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1819. DOI:10.1109/TKDE.2013.39 |
| [2] |
UEDA N, SAITO K. Parametric mixture models for multi-label text[C]//Proceedings of the 15th International Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2002: 721
|
| [3] |
ZHU Zijiang, CHEN Hang, HU Yi, et al. Age estimation algorithm of facial images based on multi-label sorting[J]. EURASIP Journal on Image and Video Processing, 2018, 2018(1): 114. |
| [4] |
WANG Xiao, ZHANG Weiwei, ZHANG Qiuwe, et al. MultiP-SChlo: multi-label protein subchloroplast localization prediction with Chou's pseudo amino acid composition and a novel multi-label classifier[J]. Bioinformatics, 2015, 31(16): 2639. DOI:10.1093/bioinformatics/btv212 |
| [5] |
AGRAWAL R, GUPTA A, PRABHU Y, et al. Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages[C]//WWW'13 Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro: ACM, 2013: 13
|
| [6] |
CHEN Chunling, TSENG F S C, LIANG T, et al. Editorial: an integration of WordNet and fuzzy association rule mining for multi-label document clustering[J]. Data & Knowledge Engineering, 2010, 69(11): 1208. |
| [7] |
MA Haiping, CHEN Enhong, XU Linli, et al. Capturing correlations of multiple labels: a generative probabilistic model for multi-label learning[J]. Neurocomputing, 2012, 96(1): 116. |
| [8] |
WU Yu, WU Wei, ZHANG Xiang, et al. Improving recommendation of tail tags for questions in community question answering[C]//Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2016: 3066
|
| [9] |
RRAD J, PFAHRINGER B, HOLMES G, et al. Classifier chains for multi-label classification[J]. Machine Learning, 2011, 85(3): 333. DOI:10.1007/s10994-011-5256-5 |
| [10] |
FURNKRANZ J, HULLERMEIER E, MENCIA E L, et al. Multi-label classification via calibrated label ranking[J]. Machine Learning, 2008, 73(2): 133. DOI:10.1007/s10994-008-5064-8 |
| [11] |
TSOUMAKAS G, VLAHAVAS I. Random k-labelsets: an ensemble method for multi-label classification[C]//Proceedings of the 18th European Conference on Machine Learning. Berlin Heidelberg: Springer Berlin Heidelberg, 2007: 406
|
| [12] |
ZHANG Minling, ZHOU Zhihua. Ml-kNN: a lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7): 2038. DOI:10.1016/j.patcog.2006.12.019 |
| [13] |
WIECZORKOWSKA A, SYNAK P, RAS Z. Multi-label classification of emotions in music[C]//Proceedings of the 2006 International Conference on Intelligent Information Processing and Web Mining (ⅡPWM). Berlin Heidelberg: Springer Berlin Heidelberg, 2006: 307
|
| [14] |
LUO Xiao, ZINCIR A N. Evaluation of two systems on multi-class multi-label document classification[C]// Proceedings of the 15th International Symposium on Methodologies for Intelligent Systems (ISMIS). Berlin Heidelberg: Springer-Verlag, 2005: 161
|
| [15] |
XU Jianhua. Multi-label weighted k-nearest neighbor classifier with adaptive weight estimation[C]// Proceedings of the 18th international conference on Neural Information Processing Volume Part Ⅱ. Berlin Heidelberg: Springer Berlin Heidelberg, 2011: 79
|
| [16] |
THABTAH F, COWLING P, PENG Y. MMAC: a new multi-class, multi-label associative classification approach[C]//Proceedings of the 4th IEEE International Conference on Data Mining (ICDM). Brighton: IEEE, 2004: 217
|
| [17] |
XU Xinshun, JIANG Yuanp, PENG Liang, et al. Ensemble approach based on conditional random field for multi-label image and video annotation[C]//Proceedings of the 19th ACM international conference on Multimedia. Scottsdale: ACM, 2011: 1377
|
| [18] |
GHAMRAWI N, MCCALLUM A. Collective multi-label classification[C]//Proceedings of the 2005ACM Conference on Information and Knowledge Management (CIKM). Bremen Germany: ACM, 2005: 195
|
| [19] |
ZHANG Minling, ZHOU Zhihua. Multi-label neural networks with applications to functional genomics and text categorization[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1338. DOI:10.1109/TKDE.2006.162 |
| [20] |
TSOUMAKAS G, ZHANG Minling, ZHOU Zhihua. Learning from multi-label data[Z]. Bled Slovenia: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2009
|
| [21] |
HE Haibo, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1263. DOI:10.1109/TKDE.2008.239 |
| [22] |
NITESH V C, KEVIN W B, LAWRENCE O H, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2002, 16(1): 321. |
| [23] |
LI Sinan, LI Ning, LI Zhanhuai. Multi-label data mining: a survey[J]. Computer Science, 2013, 40(4): 14. |
| [24] |
ZHANG Minling, LI Yukun, LIU Xuying. Towards class-imbalance aware multi-label learning[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence IJCAI 2015. Buenos Aires: AAAI Press, 2015: 4041
|
| [25] |
CHENG Weiwei, HVLLERMEIER E. Combining instance-based learning and logistic regression for multilabel classification[J]. Machine Learning, 2009, 76(2): 211. |