Boosting for Multi-Graph Classification
Boosting for Multi-Graph Classification
复制标题
DOI：
10.1109/tcyb.2014.2327111
复制
发表时间：
2015-03
影响因子：
11.8
通讯作者：
Jia Wu;Shirui Pan;Xingquan Zhu;Z. Cai
中科院分区：
文献类型：
--
作者：
Jia Wu;Shirui Pan;Xingquan Zhu;Z. Cai
在本文中，我们提出了一种新颖的基于图的学习问题，即多图分类（MGC），其目的是从一组标记袋中学习分类器，每个标记袋内包含多个图。如果袋中至少有一张图为正，则该袋被标记为正，否则为负。这种多图表示可用于许多现实世界的应用，例如网页分类，其中网页可以被视为一个袋子，网页内的文本和图像被表示为图。这个问题是多实例学习（MIL）的泛化，但存在重大差异，主要是因为 MIL 中的实例共享公共特征空间，而没有可用的特征来表示多图包中的图。为了解决这个问题，我们提出了一种基于提升的多图分类框架（bMGC）。给定一组带标签的多图包，bMGC 在包级别和图级别上采用动态权重调整，以在每次迭代中选择一个子图作为弱分类器。在每次迭代中，都会调整包和图的权重，以便错误分类的包将获得较高的权重，因为其预测的包标签与真实标签冲突，而如果图位于正袋中，则错误分类的图将获得较低的权重值（如果图位于负袋中，则错误分类的图将获得较高的权重）。因此，bMGC 能够区分正袋和负袋中的图，从而导出有效的分类器，从而形成 MGC 的增强模型。对现实世界多图学习任务的实验和比较证明了算法的性能。
In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.