在传统的监督学习框架中, 每个示例仅仅对应于唯一一个类别标记, 这类问题可称为单标记学习问题.然而在很多现实问题中, 一个示例可能并不仅仅由单个标记描述, 而是同时拥有多个类别标记.例如, 一篇文档可能属于多个预先定义的主题, 一张图片可能同时包含多个语义, 一个基因可能同时拥有多种功能等.这种单个示例拥有多个标记的学习问题称为多标记学习[1-3]问题.近年来, 多标记学习得到了许多学者的关注, 并被广泛研究应用于文本分类[1-3]、图像标注[4, 5]、音频类别标注[6]、视频自动注释[7]等多个领域.
在多标记学习问题中, 多个标记同时隶属于一个示例, 并且这些标记之间存在一定的关联性[8].举例来说, 如果一篇新闻文章已经被标记为“姚明”, 那么这则新闻也很有可能被同时标记为“篮球”; 再比如一幅图像已经被标记为“鲨鱼”, 那这幅图像也很有可能被同时标记为“海洋”.因此在多标记学习问题中, 如果忽略标记之间的关系, 将多标记学习问题转化为多个单标记学习问题, 这样虽然能够处理多标记数据, 但是会损失较多的标记关系信息, 通常分类效果不会太好.此外, 如果直接把标记之间的所有组合作为分类结果输出, 随着标记数目的增多, 输出组合呈指数级别变化, 既增加了模型的复杂性, 又容易导致样本的稀疏性.
针对上述问题, 本文采用关联规则算法挖掘标记之间的关联性, 这样既不改变样本分布, 又能避免标记增多时的“维数灾难”问题.现有研究虽然将关联规则算法应用到多标记学习中[9-11], 但得到的前项是特征, 后项是标记的关联规则, 然后, 通过一定的方式筛选出部分规则并输出到分类器中.这类方法本质上仍是把关联规则算法作为一种单标记学习的分类算法, 考虑的是特征与标记之间的关系, 而没有从标记之间的关联性入手.此外, 由于传统关联规则算法只能挖掘离散型数据之间的频繁项集, 当特征值为连续型数据时则无能为力.本文将关联规则算法用于挖掘标记之间的频繁项集, 并不涉及示例的特征, 由此可以处理不同数据类型的多标记学习问题.
本文首先针对现有经典关联规则算法需要对数据库进行多次扫描确定候选频繁集, 从而导致计算频繁项集效率较低等问题, 对关联规则算法进行改进, 提出了基于矩阵分治的频繁项集挖掘算法(matrix divide-and-conquer based frequent items mining, 简称MDC-FIM), 并对算法的正确性予以证明.其次, 基于MDC-FIM算法, 我们提出了一种基于全局关联规则挖掘的多标记分类算法(global association rule based multi-label classification, 简称GAR-MLC).该算法应用MDC-FIM算法挖掘标记之间的关联规则, 并利用该关联规则更新多标记数据的标记分布, 在此基础上, 应用现有的多标记分类算法.考虑到实际情况下标记之间的相关性只存在于部分子数据集, 比如在美食杂志中, “苹果”和“水果”存在相关性; 再比如在科技杂志中, “苹果”和“电脑”存在相关性, GAR-MLC只从标记空间进行考虑, 而不考虑样本空间, 对全局数据进行修正可能会引起原先不属于一个类别的数据被强行修正造成分类准确率降低的问题, 进而提出了一种基于局部关联规则挖掘的多标记分类算法(local association rule based multi-label classification, 简称LAR-MLC).该算法先使用聚类算法对示例特征聚类, 再利用MDC-FIM算法在每个聚类类别下挖掘关联规则并更新标记分布, 即对多标记数据作局部的修改.该算法既考虑标记之间的相关性, 又考虑样本之间的相关性, 因此能够更加合理地修正数据, 从而达到更好的分类效果.最后, 我们在6个多标记基准数据集上, 基于5种不同的多标记评价准则对本文所提算法进行了实验验证, 实验结果表明:我们所提出的MDC-FIM算法能够快速挖掘标记之间的频繁项集, 改进的GAR-MLC和LAR-MLC算法与现有的多标记算法相比具有更好的分类性能.
本文第1节介绍多标记学习和关联规则挖掘的相关概念和研究现状.第2节给出基于矩阵分治的频繁项集挖掘算法(MDC-FIM), 并对算法的正确性予以证明.第3节给出基于全局关联规则挖掘的多标记分类算法(GAR-MLC)和基于局部关联规则挖掘的多标记分类算法(LAR-MLC).第4节给出实验设置与结果分析.第5节对本文进行总结和展望.
1 相关工作 1.1 多标记学习目前, 许多学者致力于研究多标记学习问题, 基于对标记相关性的不同考虑方式, 目前的多标记学习算法主要分为以下3种.
(1) 一阶策略
该策略通过逐一考察单个标记而忽略标记之间的相关性构造多标记学习算法.这类策略效率较高并且实现简单, 但由于完全忽略标记之间可能存在的相关性, 泛化性能较差.
文献[12]提出的BR算法将多标记学习问题转化为一系列独立的两类问题, 其中, 对于第i个两类问题, 如果样本属于第i个标记, 则将其分为正类样本; 否则, 将其分为负类样本.该算法简单易行, 但忽略了标记之间的相关信息.
文献[13]将经典的KNN方法应用于多标记学习框架, 提出了多标记懒惰学习方法(ML-KNN).该算法对每个测试样本根据它与训练样本的相似度来预测所对应的类别标记集, 减少大量的训练开销, 但是并没有考虑标记之间的相关性.在此基础上, 文献[14]提出一种新型多标记学习算法.该算法考虑了标记之间的相关性, 将标记信息构造一个标记计数向量, 并提交给已训练的线性分类器进行预测.
(2) 二阶策略
该策略通过考察两两标记之间的相关性(例如相关标记与无关标记之间的排序关系等)构造多标记学习算法.这类策略由于在一定程度上考察标记之间的相关性, 其系统泛化性能较优; 然而当真实世界问题中标记之间具有超过二阶的相关性时, 该类方法的效果会受到很大影响.
文献[15]将传统的支持向量机(SVM)拓展到多标记学习中, 对每个类别标记构造一个SVM分类器, 最小化基于排序损失的经验损失函数, 提出了Rank-SVM算法.该算法的优点是考虑了每个样本中两个类别标记之间的关系, 且该优化问题可转化成一个二次规划问题, 但由于需要计算大量的变量, 训练时间比较久.
文献[16]基于神经网络, 通过改进反向传播算法来适应多标记问题, 提出了BP-MLL(back-propagation multi-label learning)算法.该算法主要引入新的误差函数计算方法来捕捉多标记的特征, 并且使用梯度下降算法来更新参数.
(3) 高阶策略
该策略通过考察高阶的标记相关性(例如处理任一标记对其他所有标记的影响等)构造多标记学习算法.该类方法虽然可以较好地反映真实世界问题的标记相关性, 但其模型复杂度往往过高, 以至于难以处理大规模学习问题.
文献[17]提出的Random k-labelsets(RAkEL)算法能够考察高阶的标记相关性.算法首先从初始的类别标记集中随机地选取包含一个类别标记的子集, 然后训练多个多类分类器, 最后, 利用集成学习的思想采用投票或阈值法来预测样本所属的类别标记集合.
文献[18]将贝叶斯网络应用于多标记学习算法中, 提出了基于贝叶斯网络的多标记学习算法LEAD.算法采用一种近似的方式首先消除特征向量对于标记空间的影响, 然后再构造相应的贝叶斯网络来对标记之间的相关性进行建模.
文献[19]认为标记之间的相关性更可能存在于局部数据中, 提出了ML-LOC算法.该算法首先基于标记向量使用聚类算法定义局部数据, 再融合局部标记相关性和全局可分性到一个统一的分类框架中, 并给出了相应的优化求解算法.
1.2 关联规则若两个或多个变量的取值之间存在某种规律性, 则称为关联[20].关联规则是寻找在同一个事件中出现的不同项的相关性, 比如在一次购买活动中, 购买的不同商品之间的相关性.在机器学习研究领域, 学者已经提出多种关联规则的挖掘算法, 如Apriori, FP-growth, Eclat[21]算法等.
文献[9]将关联规则应用于分类算法中, 提出了经典的基于分类关联规则(CARs)的分类算法.该算法首先挖掘所有规则后项是标记的分类关联规则(CARs), 然后在已发现的CARs中选择优先级高的规则来覆盖训练集.随后几年时间中, 研究人员研究出很多新的关联分类算法, 其中最有代表性的是文献[10]提出的基于多个分类关联规则的分类算法CMAR和文献[11]提出的预测型关联规则的分类算法CPAR.上述分类算法具有可解释性好、分类准确率较高的特点, 但是都只能对单标记数据进行处理.目前, 国内外对关联规则应用于多标记学习中的研究还比较少.文献[22, 23]利用最小标记准则将多标记转化为单标记, 分别使用FP-growth算法和使用改进的Apriori算法得到规则前项是示例特征、后项是标记的关联规则, 并基于关联规则进行分类预测.文献[24]利用FP-tree来分解组合生成的多标记规则, 通过集成学习的方法组合多个关联规则分类器并进行分类预测.为了解决大规模数据集上训练时间太长的问题, 文献[25]使用FP-growth算法得到关联规则, 并删除规则后项中的标记, 从而减少标记数量, 提高训练效率, 但这在一定程度上会造成消息的丢失, 降低分类性能.
2 基于矩阵分治的频繁项集挖掘算法 2.1 关联规则定义假设给定数据集DB, Item={i1, i2, …, im}是其中所有项的集合.Tr={tr1, tr2, …, trk}表示事务集, 其中, 每个事务Tri是一个非空项.若is, it是Item中的任意项集且is中含有的项数目为n, 则称为n-项集.数据集DB中的关联规则表示为蕴涵式is
规则is
$ \mathit{Support}({{\mathit{i}}_{\mathit{s}}}\Rightarrow {{\mathit{i}}_{\mathit{t}}})=|\{\mathit{Tr}:{{\mathit{i}}_{\mathit{s}}}\cup {{\mathit{i}}_{\mathit{t}}}\subseteq \mathit{Tr}, \mathit{Tr}\in \mathit{DB}\}\left| / \right|\mathit{DB}| $ | (1) |
规则is
$ \mathit{Confidence}({{\mathit{i}}_{\mathit{s}}}\Rightarrow {{\mathit{i}}_{\mathit{t}}})=|\{\mathit{Tr}:{{\mathit{i}}_{\mathit{s}}}\cup {{\mathit{i}}_{\mathit{t}}}\subseteq \mathit{Tr}, \mathit{Tr}\in \mathit{DB}\}\left| / \right|\{\mathit{Tr}:{{\mathit{i}}_{\mathit{s}}}\subseteq \mathit{Tr}, \mathit{Tr}\in \mathit{DB}\}| $ | (2) |
关联规则挖掘就是在DB中找出支持度和置信度分别大于用户给定的最小支持度(Minsup)和最小置信度(Minconf)的关联规则.当规则的置信度和支持度分别大于Minsup, Minconf时, 认为该关联规则是有效的, 称为强关联规则.
2.2 基于矩阵分治的频繁项集挖掘算法对于数据集DB, 定义事务集Tr={tr1, tr2, …, trk}, 项全集Item={it1, it2, …, itm}, 生成行向量V={v1, v2, …, vm}用于存储不同的项集名称, 生成布尔矩阵M用于存储数据库的信息.其中, 矩阵中的每项定义为
$ {{M}_{ij}}=\left\{ \begin{array}{*{35}{l}} 0, \ i{{t}_{j}}\notin t{{r}_{i}} \\ 1, \ i{{t}_{j}}\in t{{r}_{i}} \\ \end{array} \right., i\in [1, k], j\in [1, m] $ |
基于矩阵分治的频繁项集挖掘算法(MDC-FIM)的主要思想是:对布尔矩阵M进行初等变换, 在满足一定条件的情况下将其分治为若干个子矩阵, 并重复上述过程, 直至矩阵不能被分治.该算法最大的优点是只需要一遍扫描整个数据库, 运行速度较快.
MDC-FIM算法的具体步骤为:(1)将当前布尔矩阵M按列分块, 并统计每列中0的个数; (2)交换M中0元素最多的列与最后一列, 并对M进行初等变换, 使最后一列先出现0再出现1;(3)将M分治成若干个子矩阵, 并记下项集名称V; (4)重复第(1)步, 直至求出在满足最小支持度Minsup下的频繁项集V以及其出现的次数(支持数).MDC-FIM算法的详细流程见算法1.
算法1. 基于矩阵分治的频繁项集挖掘算法(MDC-FIM算法).
输入:数据库DB, 事务集Tr, 项全集Item, 最小支持度Minsup, 项集名称V.
输出:满足最小支持度的频繁项集FreItem.
1. Generate M using DB, Tr, Item
2. j=Find(M) //M中第j列0元素个数最多
3. Switch(M[:, j], M[:, end]); //交换M中第j列和最后一列
4. Switch(V[j], V[end]); //交换M中两个项集
5. Sort(M, end); //对M进行初等列变换, 使第end列先出现0再出现1
6. countend=sum(M[:, end]); //计算第end列值为1的个数
7. threshold=Minsup×row(M); //设置阈值
8. if (end > 1)
9. FreItem.add(M[:, 1:end-1]); //增加一个第1列到end-1列的新矩阵
10. FreItem.add(V[1:end-1]); //增加一个第1个到end-1的新向量
11. Goto 2);
12. endif
13. if (countend≥threshold)
14. begin=row(M)-threshold+1;
15. FreItem.add(M[begin:row(M), :]); //增加一个begin到row(M)行的新矩阵
16. FreItem.add(V[1:end]); //增加整个V向量
17. Goto 2);
18. endif
19. return FreItem
2.3 MDC-FIM算法推导频繁项集的正确性证明对于数据集DB, 事务集Tr={tr1, tr2, …, trk}, 项全集Item={i1, i2, …, im}, 布尔矩阵为M(M不全为0), 即共有事务个数为k, 项个数为m.不妨设其中一列中0元素的个数最多, 且为j个, 则M经过初等变换一定可以转化为如图 1所示的形式, 即最后一列顺序由j个0和k-j个1构成.
下面证明:原矩阵M满足最小支持度Minsup的频繁n-项集若存在, 则必在其子矩阵M1或者M2中, 如图 2所示).
首先假设频繁n-项集有N条事务.
假设满足支持度Minsup的频繁n-项集存在且不在M1和M2中, 则有如下两种情况.
1) 满足支持度Minsup的频繁n-项集在图 2所示的子矩阵M3中.
这种情况下, M3每行的最后一位均为0, 所以其n-项集由前m-1列产生, 而M3的前m-1列包含于M1中, 所以此时n-项集包含于M1中, 假设不成立.
2) 满足条件的n-项集有a(0 < a < N)条在M2中, 其余N-a条在M3中.
由情形1)已知, M3的解包含于M1的前j行之中, 所以这N-a条事务存在于M1的前j行之中.由满足支持度条件的频繁n-项集的定义可知, 这N条事务有且只有相互对应的n列值同时为1.考虑到M3的最后一列全为0, M2的最后一列全为1, 所以这a条和N-a条记录均产生于M的前m-1列中, 即这些n-项集都包含与M1中, 假设不成立.
综上所述, 满足支持度Minsup的n-项集若存在, 必在其子矩阵M1或者M2之中.因此, FI-MDC算法能够正确推导出频繁项集.
3 基于关联规则的多标记分类算法 3.1 多标记学习定义设X=Rd表示样本空间, Y={y1, y2, …, yq}表示所有可能的类别标记构成的集合, 其中, Y中的任意一项满足yi∈{0, 1}, 取值为1表示该标记为相关标记, 反之为无关标记.给定多标记数据集DS={(X1, Y1), (X2, Y2), …, (Xp, Yp)}, 多标记学习框架的目标是训练出一个多标记分类器h:X→2Y.然而在大多数情况下, 学习系统的输出往往对应于某个实值函数f:X×Y→R, 对于给定的训练样本Xi及其对应的标记集合Yi, 一个优秀的学习系统需要在属于Yi的类别标记上较大的值, 而在不属于Yi的类别标记上较小的值.也就是说, 对于任意的y1∈Yi以及y2∉Yi, 有f(xi, y1) > f(xi, y2)成立.实值函数f
现有的利用关联规则处理多标记分类问题的算法, 其主要思想是挖掘出频繁项集并产生关联规则, 然后通过一定的方式筛选出部分规则并输出到分类器中.这类算法在一定程度上可以提高多标记算法分类准确率, 但本质上仍然是将多标记学习问题转化为多个单标记问题, 并且完全忽略标记之间的相关性, 造成了标记之间信息的丢失.针对这一问题, 我们从标记之间的相关性入手, 提出一种基于全局关联规则挖掘的多标记分类算法(GAR-MLC), 将MDC-FIM算法与传统的多标记分类算法相结合, 首先对数据集的所有标记挖掘频繁项集, 得到标记之间的关联规则, 并对原有训练数据集的标记分布进行更新, 最后在更新的数据上采用传统的多标记算法进行训练.这一算法能够充分利用标记内部的相关性, 从而达到提高分类准确率的效果.
和已有工作(关联规则为从特征到标记)相比, MDC-FIM算法得到的关联规则前项和后项都是标记(从标记到标记).MDC-FIM算法通过调节支持度和置信度, 可以得到一系列强关联规则, 在GAR-MLC算法中, 最重要的一步是选择合适的关联规则, 并对原有训练数据集的标记分布进行更新, 更新的规则是:对满足前项值均为1(即前项的所有标记均为相关标记)的示例, 将规则后项修正为1(即后项的所有标记置位相关标记).举例说明, 假设已经通过MDC-FIM得到频繁项集y1, y2, y3, 并求出规则:
$ {{\mathit{y}}_{1}}\wedge {{\mathit{y}}_{2}}\Rightarrow {{\mathit{y}}_{3}}\left( \mathit{Confidence}=0.85 \right). $ |
更新流程是对数据集中所有满足y1=1并且y2=1的示例取出, 并依据关联规则将y3的值修正为1.
GAR-MLC的主要步骤如下:(1)对多标记数据集使用MDC-FIM算法, 找出标记之间满足最小支持度的频繁项集FreItem; (2)根据第(1)步得到的频繁项集生成关联规则Rule; (3)使用第(2)步得到的关联规则对多标记数据进行修改, 即根据关联规则全局修改多标记数据集; (4)采用现有的多标记算法进行训练和预测, 最终得到新的分类结果.
算法2. 基于全局关联规则挖掘的多标记分类算法(GAR-MLC).
输入:多标记数据集DS, 多标记分类算法MLC.
输出:新的多标记分类模型GAR-MLC.
1) 对多标记数据集DS使用MDC-FIM算法求出相应的频繁项集FreItem;
2) 根据频繁项集FreItem生成关联规则Rule;
3) 根据关联规则Rule修改相应的多标记子数据集DS;
4) 在新的数据集上, 使用多标记学习算法MLC得出一个新的分类模型GAR-MLC;
5) 返回新的多标记分类模型GAR-MLC.
3.3 基于局部关联规则挖掘的多标记分类算法从本质上看, GAR-MLC是对多标记数据集使用MDC-FIM算法找出满足最小支持度的频繁项集, 据此计算出标记之间的关联规则, 并基于新的关联规则修正全局多标记数据集, 再对新的数据采用传统的多标记算法进行实验, 从而达到提高分类准确率的效果.GAR-MLC中重要的一步是利用关联规则对全局多标记数据集进行修正, 假设已经根据MDC-FIM算法得出规则Rule, 并且其置信度为β, 使用该规则对标记集合修正时, 有1-β的概率修正错误.此外, 由于是基于全局数据进行挖掘关联规则, 满足一定置信度的规则数也较少.从数据上看, 每个数据的特征可以看作超平面上的一个点, 标记可以看作超平面的另一个点, 多标记分类算法的任务就是寻找从特征到标记的一个映射.类比于单标记学习, 一个分类效果好的多标记学习算法应当是在特征构成的超平面上的任意两个点越接近时, 其对应标记构造的超平面上的两个点越接近.考虑到直接利用GAR-MLC对标记进行修正, 忽略了对多标记学习问题中数据特征之间的分析, 而且挖掘出的关联规则数较少等问题, 我们进一步提出了一种基于局部关联规则挖掘的多标记分类算法(LAR-MLC), 首先使用聚类算法对样本进行聚类得到多个簇, 并利用MDC-FIM算法在每个簇下挖掘对应的关联规则, 再使用这些关联规则对相应簇内的数据标记进行修正, 修正方法与第3.2节的方法一样, 最后, 在更新后的数据上训练多标记学习分类算法.与GAR-MLC相比, LAR-MLC主要有以下优点:第一, LAR-MLC在数据集上基于特征先对样本进行聚类, 再对簇内标记使用MDC-FIM算法, 充分考虑到示例特征和标记对分类结果的影响; 第二, 使用聚类算法时, 将特征构成的超平面内接近的点归为一个类别, 每个类别对应的标记往往相同或相近, 再对每个类别寻找关联规则时, 对于相同规则, LAR-MLC计算得到的置信度大于GAR-MLC.这样就能得到较多的关联规则, 也使得对数据的修正更加合理.
LAR-MLC的主要步骤如下:(1)对多标记数据使用聚类算法进行聚类, 目的是将多标记数据转化为多个子数据集; (2)使用MDC-FIM算法找出各个子数据集内标记之间的满足最小支持度的频繁项集FreItem; (3)根据第(2)步得到的频繁项集生成局部关联规则Rule; (4)使用第(3)步中得到的局部关联规则对相应的多标记子数据进行修改; (5)整合所有子数据集, 应用相应多标记分类算法得到最终分类结果.
算法3. 基于局部关联规则挖掘的多标记分类算法(LAR-MLC).
输入:多标记数据集DS, 多标记算法MLC.
输出:新的多标记分类模型LAR-MLC.
1) 对多标记数据集DS使用聚类算法进行聚类, 并把DS转化为多个子数据集;
2) 对每个子数据集分别使用MDC-FIM算法求出相应的频繁项集FreItem;
3) 根据频繁项集FreItem生成关联规则Rule;
4) 根据关联规则Rule修改相应的多标记子数据集;
5) 在整合后的新数据集上使用多标记学习算法MLC得出一个新的分类模型LAR-MLC;
6) 返回新的多标记分类模型LAR-MLC.
GAR-MLC和LAR-MLC的本质都是对多标记数据集使用MDC-FIM算法找出满足最小支持度的频繁项集, 据此计算出标记之间的关联规则, 并基于关联规则修正多标记数据集, 再对更新后的数据采用传统的多标记算法进行实验, 从而达到提高分类准确率的效果.不同点主要在于:GAR-MLC直接基于全局数据挖掘关联规则, 再对多标记数据作全局的修改; 而LAR-MLC算法首先将多标记数据集聚类, 在每个簇内挖掘局部数据的关联规则, 再对多标记数据作局部的修改.
4 实验分析 4.1 实验数据本文在6个多标记真实数据集上进行实验比较, 这些数据来自多标记的不同领域.Emotions来自于歌曲分类, CAL-500来自于音频信号, Flags来自于图像识别, Genbase来自于蛋白质分类, Yeast来自于基因功能检测, Corel5k来自于图像标注.表 1给出了数据集的统计信息, 这些数据集都可以从开源项目Mulan[26]的主页(http://mulan.sourceforge.net/index.html)下载得到.
● LCard指的是标记基数(label cardinality), 即每个样本相关标记的平均个数:
$ LCard(DS)=\frac{1}{p}\sum\limits_{i=1}^{p}{\sum\limits_{j=1}^{q}{\langle y_{i}^{(j)}=1\rangle }} $ | (3) |
其中, 对于任意的谓词π, 当π成立时, 〈π〉取值为1;否则, 〈π〉取值为0.
● LDen指的是标记密度(label density), 即标记基数相当于标记数目的比例:
$ \mathit{LDen}\left( \mathit{DS} \right)=\mathit{LCard}\left( \mathit{DS} \right)/\mathit{q} $ | (4) |
● LDiv指的是标记多样性(label diversity), 即相关样本标记集合的总数:
$ \mathit{LDiv}\left( \mathit{DS} \right)=\left| \{\mathit{y} \right|\exists \mathit{x}:\left( \mathit{x}, \mathit{y} \right)\in \mathit{DS}\}| $ | (5) |
基于第3.1节中的符号表示, 对给定的测试集S={(X1, Y1), (X2, Y2), …, (Xs, Ys)}, 我们实验中采用如下评价指标来度量多标记学习系统的性能.
1) Hamming loss.该指标考察样本在单个标记上的误分类情况, 即隶属于该样本的概念标记未出现在现在标记集合中或不属于该样本的概念标记出现在标记集合中:
$ hlos{{s}_{s}}(h)=\frac{1}{s}\sum\limits_{i=1}^{s}{\frac{1}{q}|h({{X}_{i}})\mathit{\Delta} {{Y}_{i}}|} $ | (6) |
其中, 算子Δ用于表示两个集合之间的对称差, |·|为返回集合大小.
2) One-error.该指标考察在样本的概念标记排序序列中, 序列最前端的标记不属于样本标记的情况:
$\begin{eqnarray*} one-erro{{r}_{s}}(f)=\frac{1}{s}\sum\limits_{i=1}^{s}{\langle \arg \underset{y\in f}{\mathop{\max }}\, f({{x}_{i}}, y)\notin Y\rangle }\end{eqnarray*} $ | (7) |
3) Coverage.该指标考察在样本的概念标记排序序列中, 覆盖隶属于样本的所有概念标记所需的搜索深度情况:
$\begin{eqnarray*} coverag{{e}_{s}}(f)=\frac{1}{s}\sum\limits_{i=1}^{s}{\underset{y\in {{Y}_{i}}}{\mathop{\max }}\, ran{{k}_{f}}({{x}_{i}}, y)-1}\end{eqnarray*} $ | (8) |
4) Ranking loss.该指标考察在样本的概念标记排序序列中出现排序错误的情况:
$ rlos{{s}_{s}}(f)=\frac{1}{s}\sum\limits_{i=1}^{s}{\frac{1}{|{{Y}_{i}}||{{{\bar{Y}}}_{i}}|}}|\{{{y}_{1}}, {{y}_{2}}\}|f({{x}_{i}}, {{y}_{1}})\le f({{x}_{i}}, {{y}_{2}}), ({{y}_{1}}, {{y}_{2}})\in {{Y}_{i}}\times {{\bar{Y}}_{i}}| $ | (9) |
其中, Yi代表Yi在集合Y中的补集.
5) Average precision.该指标考察在样本的概念标记排序序列中, 排在隶属于该样本的概念标记之前的标记仍属于样本标记集合的情况:
$ avgpre{{c}_{s}}(f)=\frac{1}{s}\sum\limits_{i=1}^{s}{\frac{1}{|{{Y}_{i}}|}}\sum\limits_{y\in {{Y}_{i}}}{\frac{|{y}'|ran{{k}_{f}}({{x}_{i}}, {y}')\le ran{{k}_{f}}({{x}_{i}}, y), {y}'\in {{Y}_{i}}|}{ran{{k}_{f}}({{x}_{i}}, y)}} $ | (10) |
对于前4种评价指标而言, 指标取值越小, 则算法性能越优; 对于最后一种评价指标而言, 指标取值越大, 则算法性能越优.
我们将GAR-MLC和LAR-MLC应用于传统的多标记学习模型ML-KNN, Rank-SVM, BP-MLL中, 分别得到对应的新的多标记学习算法GAR-ML-KNN, LAR-ML-KNN, GAR-Rank-SVM, LAR-Rank-SVM, GAR-BP-MLL, LAR-BP-MLL, 通过上文提到的5种评价指标来对比新旧模型在多标记分类学习上的性能.对于本文所提算法, 在挖掘关联规则时共有两个参数需要调整.经过部分实验可知:当关联规则最小支持度值Minsup大于0.1时, 在不降低最小置信度的前提下得到的关联规则数量太少, 因此, 我们将寻找频繁项集时选用的最小支持度Minsup=0.1, 寻找关联规则时选用的Minconf=0.7.LAR-MLC算法中, 聚类使用的是k-Means算法, 聚类个数设置为5.分类器参数设置如下:在ML-KNN算法中设置近邻个数参数k=10, 平滑参数设置为1.对于Rank-SVM算法, 设置代价参数c=1, 同时选择RBF核函数.在BP-MLL中, 神经网络的隐含神经元个数为特征个数的20%, 学习率α=0.05以及训练时最大的迭代次数为100.
4.3 实验结果与分析对于每个数据集, 本文随机选取80%的数据为训练集, 余下的20%的数据为测试集, 重复实验10次.表 2~表 7显示的是不同数据集在9种不同算法下实验结果的均值与标准差.
由表 2~表 7给出的9种多标记分类算法在5个评价指标上的实验结果可以看出:相对于现有的ML-KNN, Rank-SVM, BP-MLL等多标记算法, 本文提出的GAR-MLC和LAR-MLC算法对多标记数据集修正是有效的, 对于对应的多标记分类算法都能在相应评价指标上有所提升.对于LAR-MLC和GAR-MLC之间的比较, 在6个数据集上的大部分评价指标上, LAR-MLC的表现要优于GAR-MLC.
综合比较6个数据集可以看出, Rank-SVM及其改进模型GAR-Rank-SVM, LAR-Rank-SVM在Emotions, Genbase, Yeast, Corel5k这4个数据集中, 在5个评价指标上的效果基本都优于其他算法, 在其他数据集上表现也较优.为了验证GAR-MLC和LAR-MLC算法在不同比例训练样本下的稳定性, 我们采用Rank-SVM及其改进模型GAR-Rank-SVM, LAR-Rank-SVM对相同数据集上进行实验, 实验共分3组, 训练集的数据占总数据的比例分别为40%, 60%, 80%.以Yeast数据集为例, 表 8给出在不同训练集比例下, 3种算法在5种评价指标下的分类效果.
从表 8中可以看出, 在训练集不同的数目下(40%, 60%, 80%), GAR-MLC, LAR-MLC和Rank-SVM算法相比, 在不同评价指标上都有一定程度的提升.这说明GAR-MLC, LAR-MLC算法是稳定的.另一方面, 随着训练集样本的增加, 对应的多标记算法分类效果也会有一定程度的提高.此外, 我们同样做了其他5个数据集上的稳定性对比实验, 其比较结果和表 8一致, 限于篇幅所限, 在此不再给出.
对于MDC-FIM算法挖掘出的关联规则是否有效, 我们也基于不同规模数据集进行了分析.对于只具有少量标记的数据集或标记基数较少的数据集, 以Emotions数据集为例, 该数据来源于歌曲情感分类, 数据集共有6个标记, 且标记基数仅为1.869.根据Minsup=0.1和Minconf=0.7, 我们能够得到2条关联规则, 分别为“Relaxing-Clam
MDC-FIM算法在挖掘频繁项集时共有两个参数需要调整, 即最小支持度Minsup和最小置信度Minconf.在我们之前的实验中, 这两个参数的取值分别为Minsup=0.1和Minconf=0.7.为了分析MDC-FIM算法在不同参数设置下挖掘出的关联规则的数目的变化规律, 我们对这两个参数进行敏感性分析.图 3给出了GAR-Rank-SVM和LAR-Rank-SVM在Yeast数据集上, 关联规则的数目指标随Minsup和Minconf的变化影响.
从图 3中可以看出:当固定Minsup时, 挖掘出的关联规则的数目随Minconf的增大而减小; 当固定Minconf时, 挖掘出的关联规则数目随Minsup的增大而减小.LAR-Rank-SVM算法将原始数据集分为多个类别, 并在每个类别中寻找关联规则, 因此, 得到的关联规则数目比GAR-Rank-SVM多.当Minsup大于0.2或Minconf大于0.8时, 得到的关联规则数量较少.接下来, 我们检验依据参数选取出的关联规则数量与分类准确率之间的变化情况.从图 3可以看出:当Minsup取值在0.1、Minconf取值为0.7附近时, 选取出的规则数目较多.对此, 我们检验在这两个参数值附近时分类性能的变化.图 4给出GAR-Rank-SVM和LAR-Rank-SVM在Yeast数据集上, Average Precision指标随Minconf和Minconf的变化影响.
从图 4中可以看出:当Minsup取0.1和Minconf取0.7时, GAR-Rank-SVM在Yeast数据集上能够取得最大的分类准确率; 当Minsup取0.1和Minconf取0.6时, LAR-Rank-SVM能够取得最大的分类准确率; 而在Minconf取0.7时, 能够取得次优解.
在实验的6个数据集中, CAL-500数据集的标记基数最大, 这意味着在Minsup和Minconf选取同等数值情况下, 得到的关联规则会更多, 从而带来的时间消耗也会更大.为了检验MDC-FIM算法在大规模数据标记集合上的运行效率, 我们在该数据集上设计了对比实验, 将MDC-FIM算法与其他经典关联规则对比在计算频繁项集时在时间上的消耗, 对比算法为Apriori算法、改进的Apriori算法、Eclat算法, 最小置信度Minconf设置为0.7.各算法在不同支持度计算频繁项集所消耗的时间如图 5所示.
从图 5可以看出:随着支持度的减小, 各算法所消耗的时间逐渐增加; 与其他算法相比, 本文提出的MDC-FIM算法挖掘频繁项集在时间效率上要明显占优.
通过上述4组不同实验结果可以看出:MDC-FIM算法能够快速而准确地找到标记之间的关联规则, 将GAR-MLC和LAR-MLC应用于现有的ML-KNN, Rank-SVM, BP-MLL多标记算法, 得到对应的改进多标记学习算法分类效果都要优于原先的算法; 并且大部分情况下, LAR-MLC效果要优于GAR-MLC.通过对示例数量和标记数量进行分析可以看出, MDC-FIM可以适用于各种多标记数据集.
5 总结本文提出了一种基于矩阵分治的频繁项集挖掘算法, 并将其应用于多标记学习框架中, 分别提出了基于全局关联规则挖掘和局部关联规则挖掘的多标记分类算法.这两种算法通过挖掘标记之间的关联规则, 从全局和局部两个角度出发对原有数据进行更新; 在此基础上, 可以直接应用现有的多标记学习算法得到新的多标记分类模型.多个真实的数据集上的实验结果表明:所提出的算法适用于多标记学习框架, 且能够取得良好的分类性能.当前工作主要把标记之间的关联性应用于数据更新, 在未来的工作中, 我们将结合所提出的算法对多标记分类算法做进一步的改进, 以期获得更好的分类效果.
[1] |
Schapire RE, Singer Y. BoosTexter:A boosting-based system for text categorization. Machine Learning, 2000, 39(2): 135–168.
[doi:10.1023/A:1007649029923] |
[2] |
Fürnkranz J, Hüllermeier E, Mencía EL, Brinker K. Multilabel classification via calibrated label ranking. Machine Learning, 2008, 73(2): 133–153.
[doi:10.1007/s10994-008-5064-8] |
[3] |
Rubin TN, Chambers A, Smyth P, Steyvers M. Statistical topic models for multi-label document classification. Machine Learning, 2012, 88(1): 157–208.
[doi:10.1007/s10994-011-5272-5] |
[4] |
Cabral RS, Torre FDL, Costeira JP, Bernardino A. Matrix completion for multi-label image classification. In:Proc. of the Advances in Neural Information Processing Systems. 2011. 190-198. |
[5] |
Zhou Y, Xue H, Geng X. Emotion distribution recognition from facial expressions. In:Proc. of the ACM Int'l Conf. on Multimedia. 2015. 1247-1250.[doi:10.1145/2733373.2806328] |
[6] |
Lo HY, Wang JC, Wang HM, Lin SD. Cost-Sensitive multi-label learning for audio tag annotation and retrieval. IEEE Trans. on Multimedia, 2011, 13(3): 518–529.
[doi:10.1109/TMM.2011.2129498] |
[7] |
Wang J, Zhao Y, Wu X, Hua XS. A transductive multi-label learning approach for video concept detection. Pattern Recognition, 2011, 44(10-11): 2274–2286.
[doi:10.1016/j.patcog.2010.07.015] |
[8] |
Gibaja E, Ventura S. A tutorial on multilabel learning. ACM Computing Surveys, 2015, 47(3): 1–38.
[doi:10.1145/2716262] |
[9] |
Liu B, Hsu W, Ma Y. Integrating classification and association rule mining. In:Proc. of the Knowledge Discovery and Data Mining (KDD). 1970. 80-86. |
[10] |
Li W, Han J, Pei K. CMAR:Accurate and efficient classification based on multiple class-association rules. In:Proc. of the Int'l Conf. on Data Mining. 2001. 369-376.[doi:10.1109/ICDM.2001.989541] |
[11] |
Yin X, Han J. CPAR:Classification based on predictive association rules. In:Proc. of the Int'l Conf. on Data Mining. 2003. 35-42. |
[12] |
Spyromitros E, Tsoumakas G, Vlahavas I. An empirical study of lazy multilabel classification algorithms. In:Proc. of the Artificial Intelligence:Theories, Models and Applications. 2008. 401-406.[doi:10.1007/978-3-540-87881-0_40] |
[13] |
Zhang ML, Zhou ZH. ML-KNN:A lazy learning approach to multi-label learning. Pattern Recognition, 2007, 40(7): 2038–2048.
[doi:10.1016/j.patcog.2006.12.019] |
[14] |
Zhang ML. An improved multi-label lazy learning approach. Journal of Computer Research and Development, 2012, 49(11): 2271–2282(in Chinese with English abstract).
http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201211002.htm |
[15] |
Elisseeff AE, Weston J. A kernel method for multi-labelled classification. In:Proc. of the Advances in Neural Information Processing Systems. 2002. 681-687. |
[16] |
Zhang ML, Zhou ZH. Multilabel neural networks with applications to functional genomics and text categorization. IEEE Trans. on Knowledge and Data Engineering, 2006, 18(10): 1338–1351.
[doi:10.1109/TKDE.2006.162] |
[17] |
Tsoumakas G, Vlahavas I. Random k-labelsets:An ensemble method for multilabel classification. In:Proc. of the European Conf. on Machine Learning. 2007. 406-417.[doi:10.1007/978-3-540-74958-5_38] |
[18] |
Zhang ML, Zhang K. Multi-Label learning by exploiting label dependency. In:Proc. of the ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2010. 999-1008.[doi:10.1145/1835804.1835930] |
[19] |
Huang SJ, Zhou ZH. Multi-Label learning by exploiting label correlations locally. In:Proc. of the 26th AAAI Conf. on Artificial Intelligence. 2012. 949-955. |
[20] |
Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules:Readings in Database Systems. 3rd ed.. , Morgan Kaufmann Publishers Inc., 1998: 580-592.
|
[21] |
Nguyen TL, Vo B, Snasel V. Efficient algorithms for mining colossal patterns in high dimensional databases. In:Proc. of the Knowledge-Based Systems. 2017. 75-89.[doi:10.1016/j.knosys.2017.01.034] |
[22] |
Patel K, Kapadia N, Parikh M. Discover multi-label classification using association rule mining. Int'l Journal of Advance Engineering and Research Development, 2014, 1(1): 18–23.
[doi:10.21090/ijaerd.0101004] |
[23] |
Alazaidah R, Thabtah F, Al-Radaideh QA. A multi-label classification approach based on correlations among labels. Int'l Journal of Advanced Computer Science and Applications, 2015, 6(2): 52–59.
[doi:10.14569/IJACSA.2015.060208] |
[24] |
Li B, Li H, Wu M, Li P. Multi-Label classification based on association rules with application to scene classification. In:Proc. of the Int'l Conf. for Young Computer Scientists. 2008. 36-41.[doi:10.1109/ICYCS.2008.524] |
[25] |
Charte F, Rivera A, Jesus MJ, Herrera F. Improving multi-label classifiers via label reduction with association rules. In:Proc. of the Int'l Conf. on Hybrid Artificial Intelligent Systems. 2012. 188-199.[doi:10.1007/978-3-642-28931-6_18] |
[26] |
Tsoumakas G, Vilcek J, Xioufits ES. Mulan:A Java library for multi-label learning. 2011. http://mulan.sourceforge.net/datasets.html |
[14] |
张敏灵. 一种新型多标记懒惰学习算法. 计算机研究与发展, 2012, 49(11): 2271–2282.
http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201211002.htm
|