基于标记集合划分的多标记分类算法.pdf

第 卷 第 期 年 月 昆明理工大学学报（ 自然科学版） （ ） 收稿日期： 基金项目： 国家自然科学基金项目（ ） 作者简介： 何颖婧（ ） ， 硕士研究生 主要研究方向： 数据挖掘 ： 通信作者： 王志海（ ） ， 教授， 博士生导师 主要研究方向： 机器学习、 数据挖掘等 ： ： 基于标记集合划分的多标记分类算法 何颖婧， 王志海， 李 哲 （ 北京交通大学 计算机与信息技术学院， 北京 ） 摘要：在多标记学习中， 标记之间往往既不是完全独立也不是完全排斥的， 因此在构建多标记分 类器时要充分利用标记之间的依赖关系 目前利用标记间关系的方法有将标记集合划分为子集 和将各标记间关系表示为链式两种 本文提出了一种结合上述两种思想的算法， 首先根据标记对 间的依赖度量值来启发式地对标记集合进行划分， 然后在最终的划分子集合间依次建立分类器 组成分类器链 通过与其他算法的比较， 实验结果表明该算法能提升分类器性能 关键词：多标记； 标记关系； 分类器链 中图分类号： 文献标志码： 文章编号： （ ） ， ， （ ， ， ，） ： ， ： ， ， ， ， ： ； ； 引 言 传统的分类问题都假设一个实例只和一个类标相关， 然而很多现实的问题中一个实例往往可以同时 属于多个标记 比如一幅图像可能包含多个场景， 一条新闻可能同时涉及到政治和经济等 随着多标记学 习在文本、 图像、 视频场景分析、 基因功能预测等领域的广泛应用， 它受到越来越多研究者的关注， 成为机 器学习领域研究的热点之一 设 表示数据集， 表示标记集合， 多标记学习的任务是确定一个映射函数 ：（ ， ， ）， 使得对任意的未知类标的实例 ， ， 可得到适当的标记集合 ， 目前， 多标记学习方 法可分为问题转化和算法适应两类 问题转化方法将多标记分类问题转化为一个或多个单标记问题， 算法适应方法则扩展传统的分类算法， 使其能直接应用于多标记数据 事实上， 许多算法适应方法都是将 问题转化的思想内嵌在算法中， 因此， 本文接下来主要讨论问题转化方法 问题转化中最常用的两个算法 为标记幂集合算法（ ，） 和二值相关算法（ ，） 方法将每个标记间 的组合都看作一个新的类值， 若实例集中有 个标记， 则标记的可能组合就为 ， 由于标记的组合情况可 能特别多， 这样就会带来数据稀疏的问题 为解决该问题， 等人提出了 算法 ， 它保留出现次数 大于阈值的标记集合， 并对出现次数较少的标记集合进行划分， 对划分后的子集建立 分类器， 然而对 实例预测时只能得到在训练集中出现过的标记集合 等人提出 算法 随机选择多个标 记集合的子集建立 分类器， 但其时间复杂度较高 方法则将原多标记分类问题转化为多个二值分 类问题， 即对每个标记都单独训练一个分类器， 这就忽略了标记之间可能存在的依赖关系 为此， 等人提出 算法 ， 该算法为每对标记建立二值分类器， 综合每个二值分类器的投票结果 得到标记预测集合， 但可能出现有的标记对训练实例过少的问题； 等人提出 算法（ ， 分类器链） ， 算法构造多个链式结构的分类器， 所谓链式结构， 即将之前的分类器的类属性加入训 练集的特征属性中， 建立新的训练集， 后面的分类器则是在新的训练集上构建， 这样就有效地利用了标记 之间的依赖关系， 然而构建分类器链的顺序会影响分类器的性能 付彬等人提出的 算法 在分类器 链算法的基础上进行改进， 它按照一定的顺序来建立分类器链 等人提出的 算法 则 通过结合 分类器和 分类器来构建多标记分类器 综上， 在多标记学习中， 一个重要的研究问题是如 何有效地利用多标记间的关系 本文提出一个利用标记对之间的依赖关系来对标记集合进行划分的方法， 它通过多次划分， 并构建分类 器链来评价划分结果以逐步得到划分结果 本文接下来的组织如下： 第 节介绍了本文提出的基于标记集合 划分的多标记学习算法； 第 节中对本文提出的算法进行了实验并给出结果； 第 节是对本文的总结 输入： 训练集合 （ ，） ， （ ，） ， ， （ ，） ； 标记对依赖阈值 ； 损失限制 输出： 分类器链（ ， ） 训练过程： ， ， ， ， 计数 ； 所有标记对（ ， ） 计算依赖值 （ ，） ， （ ，） ； （ （ ，） ） （ ， ） （ （ ， ） ） ； （ ， ） ； ， （ ， ） 根据 建立分类器链（ ， ， ） ； （ ， ， ） ，（ ， ）（ （ ， ） ） ； （ （ ， ） （ ， ） ； （ ， ） ， 根据 建立分类器链（ ， ， ） （ ， ， ） （ ） ， ， ； ； （ ） 根据 建立分类器链（ ， ） 图 的训练过程 基于标记划分的分类器链（ ） 设计 第 节中总结现有的多标记学习算法， 从对标记 关系的角度看， 可以分为两类， 即标记集合划分为几 个子集和将标记间看作链式结构 前者能有效利用标 记之间前者的强依赖关系， 后者则间接地利用了其他 标记提供的信息 为有效利用标记间的关系来提升分 类器性能， 本文考虑将二者结合起来， 先将标记集合 划分为几个子集， 再在划分的子集间建立分类器链 我们认为这样通过对标记集合的划分能将依赖关系 较强的标记放在同一子集中处理充分利用其关系， 且 解决了 方法存在的数据稀疏问题， 在子集之间建 立分类器链则可以有效地利用当前标记子集之前的 标记集合的预测值所提供的信息， 相较于分类器链算 法和 算法则可以减少空间复杂度 算法 基于标记划分的分类器链算法首先计算类标对 之间的依赖关系， 得到对各标记对的依赖评价值， 然 后根据标记对之间的关系评价值对标记集合进行划 分， 这其实也可以看作为是一个聚类的过程， 对每次 的标记划分结果通过建立分类器链来进行评价， 逐 步更新划分结果以更好地挖掘标记间的关系， 具体 的训练过程见图 在图 对算法的描述中， 表示对标记的划分， 中组的个数就表示原标记集合被划分为子集的个 数 在步骤 中首先将标记集合划分为 个组， 每 个组仅对应一个标记， 即初始化为所有标记之间无依赖关系的状态， 通过之后步骤的操作将逐步找出标记 第 期 何颖婧， 王志海， 李 哲： 基于标记集合划分的多标记分类算法 之间的依赖关系 第 步评价标记对之间的依赖关系时， 本算法使用的是卡方值 任意给定两个标记 和 ， 其卡方检验值如公式（ ） 所示： （ ） （ ） （ ） （ ） （ ） （ ） （ ） 表 标记 和 的列联表 合计 合计 公式（ ） 中各变量的计算如表 所示 表 中 表示数 据集中实例的数量， 各变量对应在数据集中与两个标记相关 的实例的统计量， 例如 表示数据集中既与 相关又与 相 关的实例个数 训练过程中的步骤 、 步骤 以及步骤 中都有涉 及到根据标记划分的结果构造分类器链， 由于传统的分类器 链中的各分类器都只有一个类标， 而在我们构造分类器链时， 有些划分的标记子集中是含有多个标记的， 因此此处我们对分类器链算法进行了修改， 具体如图 所示 输入： （ ，） ， （ ，） ， ， （ ，） ； 标记划分 输出： 分类器链（ ， ） 构建过程： ； ； （ ， ， ， ， ） （ ， ） ， （ ）在 上建立一个 分类器 ； （ ）在 上新建一个单标记分类器 ； 图 分类器链的构建过程 步骤 和步骤 中都有对分类器链的评价 （ ，） ， 在获取分类器链的评价值 时， 采用交叉验证的方式进行评价， 评价指标 采用当前分 类器的子集精确率 步骤 所做的是选择接下来依赖值 最大的一对标记， 并根据这对标记对原标记集合的划分 进行改变， （ ， ） 对标记对 ， 的操作是： 若标记 和 都单独为一个组， 则将这两个标记合并； 若 两个标记中有一个已经和其他标记成为一组， 另一个单 独为一组， 则将单独的那个标记加入另一个标记所在的 组中； 若两个标记都分别和其他标记在一组中， 则将这两 个标记所在的两个组合并为一个组； 若两个标记在一个组 中， 则继续选取下一对依赖值最大的标记对 在对实 例进行预测时， 依照建立分类器链时按照的组顺序来依次 对待分类实例的各标记的值进行预测， 并把已经预测的标 记值作为属性加入待测实例的属性中预测接下来的标记 算法通过首先对标记对之间关系进行评价， 然后逐步得对标记集合进行划分并建立分类器链评价其好 坏以挖掘出标记间的关系， 这势必比传统的分类器链算法要增加训练时间， 但是， 它这样通过利用标记对之 间的关系将整个标记集合进行划分， 将在分类器链的基础上充分利用存在较强依赖关系的标记 的集成算法 算法在建立分类器链时， 根据的是训练集中标记的顺序， 即先对标记 所在的组建立分类器， 若 标记 和标记 不在同一个组中， 则接下来对标记 所在的组建立分类器， 依此下去， 直到对所有的组都 建立分类器组成分类器链， 然而在文献 中也提到， 构建分类器链时分类器的顺序会影响分类性能， 因此 中各组的顺序也会影响分类结果 为了减少建立分类器链时各组顺序对最后分类结果产生的影响， 本 文提出了 的集成算法 训练阶段， 该算法采用 方法步骤一样， 直至得到最终的划分结果 不同的是它根据标记集合的划分结果随机地产生多个组的序列， 对产生的每个组的序列建立一个分类器链， 多个分类器链组成 算法的分类器 分类阶段， 每个分类器分别对实例进行分类， 将所有分类器链的结 果进行汇总并取平均值， 若一个标记的平均值大于给定的阈值， 则认为其和实例相关， 否则不相关 实 验 为了验证 算法与 算法的有效性， 我们对它们在一些多标记数据集上进行了实验， 并与 其他多标记学习算法进行对比， 本节主要介绍实验的数据集、 对算法的评价指标、 实验结果以及分析等 昆明理工大学学报（ 自然科学版） 第 卷 数据集 本实验采用了 ， ， ， ， 个数据集 数据集 为描述邮件的数 据集； 数据集 为对蛋白质进行分类的数据 ； 数据集 是医学方面的数据 ； 数据集 是航空安全方面的文本 ， 它是在数据集 上对原 个属性选择出 个属性后的数据 集 数据集 描述的是基因与其所具有的功能 表 为对这 个数据集及它们统计信息的描述 表 多标记数据集及统计信息 名称领域训练实例测试实例属性个数标记个数 文本 生物 文本 文本 生物 本文在评价算法时采用的测 试方式为采用源数据集中的训练 集和测试集的方式， 因此在表 中给出了训练实例和测试实例的 个数 最后一列 表示的是与 每个实例相关的标记的平均数 其计算公式如（ ） 所示， 其中 表示整个数据集中的实例数 （ ） 评价指标 在本实验中选取的评价指标有汉明损失， 子集精确率、 值以及单一错误 我们以 表示对实例第 个标记的预测值， 以表示实例第 个标记的真实值， 表示测试实例的个数， 表示标记的个数 则以上 个评价指标的定义如下 汉明损失（ ） 的定义如公式（ ） 所示 从（ ） 中可以看出， 它表示的是在标记集合 中 被错误地预测的标记的个数， 因此汉明损失值越小， 说明多标记分类器的性能越好 （， ） （ ） 子集精确率（ ） 的定义如公式（ ） 所示， 它评价的是分类正确率 子集精确率认为当预 测标记集合和真实标记集合完全相同时才是分类正确， 否则就错误， 它统计的是测试集中被完全正确分类 的实例的比例 （ ， ） （ ）（ ） 值的定义如公式（ ） 所示， 本实验采用的是基于实例的 值 值也称为综合分类率， 它是结合 精确率和召回率得到的评价指标， 精确率统计的是在预测标记集中有多少标记是被预测正确的， 召回率则 是指在真实标记中有多少标记被正确地预测了 （ ） 单一错误（ ） 的定义如式（ ） 所示 在公式（ ） 中， （ ） 函数的定义为当 （ ） 瓝时， （ ） ， 否则 （ ） 单一错误统计的是在预测的标记序列中， 排在第一的标记不是实例真实标记的次 数， 并对整个测试集进行平均 因此， 该值越小， 表示多标记分类算法性能越高 （ ， ） （ （ ， ） ）（ ） 实验设计 本文在实现 算法时， 采用 重交叉验证评价中间建立的分类器链的性能， 标记对依赖值的阈值 则采用的是对应显著性水平为 的卡方检验值 损失限制 设置为 为了验证 算法的有 效性， 本文将其与 算法、 分类器链算法（ ） 、 算法进行了比较 所有实验在 平台下 进行， 采用的基分类器为 平台下 的决策树 在评价各算法时， 采用原始数据集中分割的训练 第 期 何颖婧， 王志海， 李 哲： 基于标记集合划分的多标记分类算法 集 测试集方法进行实验 算法中也涉及到和 算法中相同的参数设置问题， 为了更好地比较 算法和 算法， 我们对 算法中参数的设置和 算法相同 对 的集成算法 进行实验时本文将其与 算法和 的集成算法 进行 比较 的分类器链数设置为 ， 分类时被预测为相关的标记的阈值是 ； 算法的 值（ 即 随机子集的大小） 被设置为 ， 分类时被预测为相关的标记的阈值是 ， 标记集合的个数为标记个数的 倍或实例个数； 对 算法， 同样也将模型数设置为 实验结果及分析 表 各算法在 个数据集上的汉明损失 表 各算法在 个数据集上的子集精确率 表 各算法在 个数据集上的 值 表 各算法在 个数据集上的单一错误 这部分将主要介绍 算法、 算 法的实验结果以及和其他算法的比较 表 表 分别给出了 算法、 算法、 分类器 链算 法 （ ）以 及 算 法 在 ， ， ， 和 这 个 数据集上的汉明损失、 子集精确率、 值以及 单一错误 每行中黑色粗体显示的为 个算法 中在该数据集上表现最好的那个算法 从表 表 中可以看到， 算法在 个数据集的 个评价指标上有 个评价指标 都是最好的， 这说明了 算法的优越性 个评价指标中， 算法在子集精确率上的 表现最好， 对 个数据集中的 个它都是排名 第一， 对另外两个数据集也是第 ， 说明 算法在优化子集精确率上的有效性 同时， 算法在 和 上的表现较好， 尤 其是和 算法相比， 根据表 中对数据集的 描述， 这两个数据集中与每个实例相关的标记 个数分别为 和 ， 是 个数据集中值 最大的两个数据集， 这说明 算法适用那 些和实例相关标记数较多的数据集， 而与实例 相关标记数较多表明标记间的依赖关系比较 强， 因此 算法能够有效地利用依赖关系 较强的标记 算法与 算法相比， 也 比其表现要好， 这说明 将标记的预测值 加入属性， 利用了预测标记提供的潜在信息来 提升分类性能 算法属于把标记集合划 分为子集的算法， 算法属于将结构表示为链 式， 因此这说明 方法通过结合两种方法 比起只通过一种方式利用标记关系而言是会提 升分类性能的 实验结果还有值得注意的一点 是， 所有算法在数据集 上的各评价值都一样， 这是因为 数据集的属性有 个， 而每条 实例相关的标记的平均数仅为 ， 这一方面说明其标记间本身可能依赖关系就较弱， 这样挖掘标记间 的依赖关系对分类的效果就影响不大， 另一方面它的属性个数较大， 训练实例又比较少， 所以我们在建立 分类器链时加入标记以预测后面的标记也就效果不明显， 所以各算法在该数据集上的表现一样 图 给出 了 算法、 算法与 算法及 算法在数据集 ， 和 上的汉明损失、 昆明理工大学学报（ 自然科学版） 第 卷 子集精确率、 值与单一错误比较， 从中可以看到， 算法和 算法在各指标上的结果都是不同 的， 这表明分类器链顺序会影响分类性能 在 数据集上除了单一错误以外的 个指标上表现 都是最好的； 在 数据集上则是在 个指标上都比 算法和 算法要好； 在 数据集 上 算法的结果在除了单一错误以外的其他指标上都介于 算法和 算法之间 综合 上述结果， 算法相较于 和 而言也提升了分类器性能 上述实验结果表明 算法结合将标记划分为几个子集和构造链式结构这两种利用标记依赖关系的 方法提升了分类器的性能， 它通过将标记集合划分为几个子集直接利用了标记间较强的依赖关系， 通过在各 子集间构建分类器链则间接地利用了之前的标记子集提供的信息来对后续的标记子集进行预测 的 实验结果表明 算法的集成算法相较于其他的集成算法也提升了分类性能， 具有一定的优势 结 论 本文主要研究了如何更好地利用标记间的依赖关系来提高多标记分类器的性能 为此， 本文提出了基 于标记集合划分的多标记分类算法 ， 它通过划分标记集合， 并在划分的标记子集间建立分类器链来 进行多标记分类 本文将 算法与已有的几个多标记学习算法在 个多标记数据集上进行了比较， 实验结果说明 了 算法的有效性 该算法能够在多个评价指标上都取得较好的结果， 尤其是对于子集精确率 另外， 算法在和实例平均相关标记数较大的数据集上的分类性能比较好， 这说明该算法能有效地利用那 些依赖关系较强的标记 本算法可以进一步研究的是子集间的分类器链的分类器顺序对分类结果产生的 影响， 集成方法只是为减弱顺序的影响运用了多个分类器链进行分类， 而优化的分类器链可能会直接提升 算法的性能， 因此研究分类器链中各分类器之间的顺序具有一定的意义 本算法的训练时间相较其他算法 较长， 如何在保证算法性能的基础上减少时间复杂度也是值得研究的问题 参考文献： ， ， ， ， ： 第 期 何颖婧， 王志海， 李 哲： 基于标记集合划分的多标记分类算法 ， ， ： ， ， ， ： ， ， ， ， ， （ ） ： ， ， ， ： ， ： 付彬， 王志海 基于树型依赖结构的多标记分类算法 模式识别与人工智能， ， （