随着生物信息学、化学情报学、Web分析等应用的广泛普及,图作为一种通用的数据结构,在复杂结构建模方面的重要性日益显现。与确定图相比,不确定图能够表达更加丰富的语义且能更好地表示数据本身固有的不确定性。具体而言,不确定性是指边或顶点以一定的概率存在。近年来伴随着对大量结构化数据分析需求的增长,图的分类处理作为数据挖掘的重要组成部分,已成为数据库和数据挖掘领域中的研究热点之一。由于不确定性的存在,已有的分类算法不能直接应用于不确定图数据的分类问题。基于此,围绕如何解决不确定图数据的分类问题,本文提出了一种基于ELM (Extreme Learning Machine)的不确定图分类算法,主要研究内容如下：首先,在系统介绍图数据挖掘的特点、意义及应用背景的基础上,给出了相关定义,并且对经典的频繁子图挖掘算法gSpan和高效的机器学习算法ELM进行了全面的分析、归纳和总结,为下一步的研究奠定了基础。其次,针对gSpan算法只能处理确定图数据及存储结构不能满足大规模图集的问题,提出了一种改进的gSpan算法。通过挖掘子图s在不确定图集D中每个图Gi中的所有内嵌图,将每个图中关于s的内嵌图组织成一颗搜索树,进而计算s在D中的支持度。用三层存储结构代替原来算法中的邻接表的存储结构,在每次扩展频繁子图的时候不必将整个图集都调入内存。再次,将改进的gSpan算法挖掘的频繁子图作为特征的候选集,为了选取部分非冗余并且有辨别力的频繁子图小集合作为分类特征,本文提出了一种特征提取方法。即通过频繁子图的Apriori性质以及给出的Score打分函数,进行了分类特征的提取。并且通过实验验证了改进的gSpan算法以及特征提取方法的有效性。最后,提出了一种基于ELM的不确定图分类算法。通过分析支持度和分类器预测能力之间的关系,给出了最小支持度阈值的设置策略。利用ELM算法来训练分类器,并且通过实验对分类器的性能进行了验证。