一种基于频繁稠密模式的图分类方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106203468A(43)申请公布日2016.12.07(21)申请号201610478455.3(22)申请日2016.06.22(71)申请人南京航空航天大学地址211106江苏省南京市江宁区将军大道29号(72)发明人张道强屠黎阳(51)Int.Cl.G06K9/62(2006.01)权利要求书1页说明书4页附图2页(54)发明名称一种基于频繁稠密模式的图分类方法(57)摘要本发明公开了一种对图进行分类的方法。图作为一种通用的数据集结构，在许多科学应用中，可以用来表示数据对象之间的各种复杂关系。在本发明的方法中，首先提出一种新的图特征，也就是频繁稠密模式。频繁稠密模式可以保留图内的权重信息以及局部拓扑结构，是一种理想的图特征。然后，通过一系列算法，从图中提取具有判别性的有序模式，并将判别性频繁稠密模式作为特征。最后基于支持向量机(supportvectormachine，SVM)，构建出对图分类的分类器。本发明公开的方法可以高效且准确地实现图的分类。CN106203468ACN106203468A权利要求书1/1页1.一种基于频繁稠密模式对图数据进行分类的方法，其特征在于，包括如下步骤：步骤一、从图数据集中挖掘频繁稠密模式；步骤二、从众多的频繁稠密模式中选择出拥有较高判别性的频繁稠密模式，作为判别性频繁稠密模式；步骤三、基于判别性频繁稠密模式构建特征矩阵，然后使用支持向量机训练分类器。训练出的分类器可用于对图进行分类；步骤四、对未知类型的图，使用步骤四训练出的分类器对其进行分类。2.如权利要求1所述的一种基于频繁稠密模式对图数据进行分类的方法，其特征在于：所述步骤一中，在频繁稠密模式的挖掘过程中，构建出一棵深度优先搜索树对所有的频繁稠密模式进行搜索，判断其是否满足频繁度条件。在搜索过程中，使用频繁稠密模式的Apriori性质，也就是一个频繁稠密模式的频繁度不低于基于它衍生出的任意频繁稠密模式的频繁度。这样，如果已经判断一个频繁稠密模式不是频繁稠密模式，则可以判断它的衍生的任意频繁稠密模式都不是频繁稠密模式，也就可以直接将这些频繁稠密模式进行剪枝，不需要再对它们进行搜索。这可以大大加快频繁稠密模式的搜索过程。3.如权利要求1所述的一种基于频繁稠密模式对图数据进行分类的方法，其特征在于：所述步骤二中，从数量众多的频繁稠密模式中挑选出判别性较高的频繁稠密模式时，使用RatioScore函数来衡量频繁稠密模式的判别性。一个频繁稠密模式的RatioScore得分越高，证明它的判别性越强，反之亦然。然后，挑选出RatioScore得分最高的前n个频繁稠密模式做为判别性频繁稠密模式。4.如权利要求1所述的一种基于频繁稠密模式对图数据进行分类的方法，其特征在于：所述步骤三中，利用步骤四挑选出的判别性频繁稠密模式，为每一个图数据构建出一个特征向量，最后将所有图数据的特征向量结合在一起，构建出特征矩阵。然后，使用支持向量机(SVM)训练出分类器。训练好的分类器可以实现对图数据的分类。5.如权利要求1所述的一种基于频繁稠密模式对图数据进行分类的方法，其特征在于：所述步骤四中，对于一个未知类别的图数据，在构建好图数据之后，使用步骤三选择出的判别性图数据构建特征向量。然后使用步骤四训练好的分类器，对其进行分类，预测出该图数据的类别。2CN106203468A说明书1/4页一种基于频繁稠密模式的图分类方法技术领域[0001]本发明公开了一种基于频繁稠密模式的图分类分类方法，涉及到神经影像处理、社交网络、频繁项挖掘、分类器构建等方面，旨在实现对图数据进行准确、高效的分类。背景技术[0002]图作为一种通用的数据集结构，可以在许多问题中用以表示数据对象之间的复杂结构关系。比如基于神经影像构建出图数据，再通过复杂网络等技术对图进行分析研究，或者使用图结构表示化合物的结构。目前，图分类问题主要研究二分类问题，即正类和负类，主要目标在于构筑一个分类模型，将两者分开。近年来，已经有许多种图特征被用于图分类。例如，节点的度(degree)、聚类系数(clusteringcoefficient)、判别性子图(discriminativesubnetwork)等，许多基于这些特征的图分类方法被提出。然而，这些图特征具有两个很大的缺点。首先，这些图特征都是基于无权图，而大部分图数据是有权数据。所以在提取这些特征时，需要将图进行阈值化，从而将有权图转化为无权图。然而，阈值化会损失极大的损失图中的权值信息，这会影响最终的分类结果。第二，大部分图特征(节点的度，聚类系数等)都只考虑单个节点的信息，而忽视了多个节点之间的信息。而许多研究表明，在大部分中，多个节点之间的连接对大脑的功能有重要的作用。