李程文　刘波

摘要：如今，图数据分类变得越来越重要。最近几十年对它的研究也越来越多，并且得到了广泛应用。传统的图数据分类研究主要集中在单标签集，然而在很多应用中，每个图数据都会同时具有多个标签集。这篇文章研究了关于图数据的多标签特征提取问题，并提出基于模糊测量函数的多标签图数据特征提取算法，用于搜索最优子图集。算法采用模糊测量函数作为评估标准评估子图特征的重要性，然后通过边枝界定算法修剪子图搜索空间有效地搜索最优子图特征。实验证明，该方法在现实应用中有较高的精度。

关键词：图数据；模糊测量；多标签；特征选取；边枝界定

1.多标签图数据分类研究背景

传统分类方法主要研究单标签分类问题，使用的数据样本只拥有单个标签，如C4.5，SVM，K近邻算法等。然而在许多实际问题中，样本数据可能拥有多个标签。多标签分类就是针对多标签数据的特点，利用数据的多个标签获取相应的数学模型，并依此将一个实例准确地划分到某一个类别中。多标签分类算法广泛地应用于医疗诊断、音乐分类和场景分类中，在这些分类中每一个输入数据样本都拥有多个标签。就像音乐分类系统，一首音乐可能同时属于多个标签，如古典音乐，轻音乐，流行音乐，爵士乐，钢琴曲。对于多标签数据，传统的单标签分类方法已无法满足需求。

图是一种最常用的数据结构之一，用于表示事物之间复杂的关系。……