推荐星级：
- 1
- 2
- 3
- 4
- 5
一种利用关联规则挖掘的多标记分类算法
资料介绍
多标记学习广泛存在于现实生活中,是当今机器学习领域的研究热点.在多标记学习框架中,每个对象由一个示例构成,但可能同时属于多个类别标记,并且各个标记之间相互关联,所以挖掘多标记之间的关联性对于多标记学习框架具有重要的意义.首先对经典的关联规则算法进行改进,提出了基于矩阵分治的频繁项集挖掘算法,并证明了该算法挖掘频繁项集的正确性;进而将该算法应用于多标记学习框架中,分别提出了基于全局关联规则挖掘和局部关联规则挖掘的多标记分类算法;最后对所提出的算法与现有多标记算法进行实验对比,结果表明,算法在5种不同的评价准则下能够取得更好的效果.
部分文件列表
| 文件名 | 大小 |
| 一种利用关联规则挖掘的多标记分类算法.pdf | 311K |
部分页面预览
（完整内容请下载后查看）软件学报ISSN 1000-9825, CODEN RUXUEW
Journal of Software,2017,28(11):2865-2878 [doi: 10.13328/j.cnki.jos.005341]
©中国科学院软件研究所版权所有.
E-mail:
Tel: +86-10-62562563
一种利用关联规则挖掘的多标记分类算法∗
刘军煜
,
贾修一
(南京理工大学 计算机科学与工程学院,江苏 南京 210094)
通讯作者: 贾修一, E-mail:
摘
要: 多标记学习广泛存在于现实生活中,是当今机器学习领域的研究热点.在多标记学习框架中,每个对象由
一个示例构成,但可能同时属于多个类别标记,并且各个标记之间相互关联,所以挖掘多标记之间的关联性对于多标
记学习框架具有重要的意义.首先对经典的关联规则算法进行改进,提出了基于矩阵分治的频繁项集挖掘算法,并证
明了该算法挖掘频繁项集的正确性;进而将该算法应用于多标记学习框架中,分别提出了基于全局关联规则挖掘和
局部关联规则挖掘的多标记分类算法;最后对所提出的算法与现有多标记算法进行实验对比,结果表明,算法在 5 种
不同的评价准则下能够取得更好的效果.
关键词: 多标记学习;关联规则;矩阵分治;频繁项集
中图法分类号: TP181
中文引用格式: 刘军煜,贾修一.一种利用关联规则挖掘的多标记分类算法.软件学报,2017,28(11):2865-
org.cn/1000-9825/5341.htm
英文引用格式: Liu JY, Jia XY. Multi-Label classification algorithm based on association rule mining. Ruan Jian Xue Bao/
Journal of Software, 2017,28(11):2865-
Multi-Label Classification Algorithm Based on Association Rule Mining
LIU Jun-Yu, JIA Xiu-Yi
(School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China)
Abstract: In the real world, multi-label learning has become a hotspot in machine learning research area. In the multi-label learning
problem, each instance is usually described by multiple class labels, which could be correlated with each other. It is well known that
exploiting label correlations is important for multi-label learning. In this paper, an improved association rule mining algorithm based is
designed on the matrix divide-and-conquer strategy. In addition, a proof is given to show the proposed algorithm in finding correct
frequent items, and an application of the algorithm to the multi-label learning framework is also provided. Moreover, a global association
rule mining and a local association rule mining based multi-label classification methods are proposed. Experimental results on several
datasets show that the proposed methods can obtain a better classification performance on 5 different evaluation criteria.
Key words: multi-label learning; association rule; matrix divide-and-conquer; frequent item
在传统的监督学习框架中,每个示例仅仅对应于唯一一个类别标记,这类问题可称为单标记学习问题.然而
在很多现实问题中,一个示例可能并不仅仅由单个标记描述,而是同时拥有多个类别标记.例如,一篇文档可能
属于多个预先定义的主题,一张图片可能同时包含多个语义,一个基因可能同时拥有多种功能等.这种单个示例
∗ 基金项目: 国家自然科学基金(61773208, 61403200, 71671086); 浙江省海洋大数据挖掘与应用重点实验室资助项目(OBDMA
201602)
Foundation item: National Natural Science Foundation of China (61773208, 61403200, 71671086); Foundation of Key Laboratory
of Oceanographic Big Data Mining and Application of Zhejiang Province (OBDMA201602)
本文由复杂环境下的机器学习研究专刊特约编辑张道强教授推荐.
收稿时间: 2017-04-13; 修改时间: 2017-06-16; 采用时间: 2017-08-23
2866
Journal of Software 软件学报 Vol.28, No.11, Novermber 2017
拥有多个标记的学习问题称为多标记学习[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 个两类问题,如果
全部评论(0)