论文部分内容阅读
在新兴的化学信息学、生物信息学,网络分析、XML数据等领域,需要用树或图这样的结构化数据类型来表示数据。在这些结构化数据类型中进行数据挖掘,将有助于我们获取新的信息和知识。在结构化类型的数据集合中,频繁项的挖掘是一种最基本的数据挖掘方式,如何高效地挖掘频繁子结构模式,是一个挑战性的问题。已有的高效频繁子结构挖掘算法的核心思想可以大致分为基于Apriori原则的连接方法和基于模式增长的扩展方法,但前者难以直接生成规范化的候选模式,后者又容易产生候选模式的数目过大。通过分析这两类方法的特点,提出了混合型PJE方法,该方法是研究频繁有根无序树挖掘、频繁自由树挖掘和频繁子图挖掘的基础。在频繁有根无序树的挖掘中,采用最小深度序列作为规范化标记形式,并且基于前缀结点进行扩展,在常数时间内得到新的规范化形式的候选模式树。采用深度扩展和广度连接的混合方式列举候选模式树,利用Apriori原则减少候选模式树的数目。对列举生成的候选模式树,利用Apriori原则进行剪枝,进一步减少需要进行频度统计的候选模式树数目。用规范化的嵌入出现列表表示模式树在数据库中的出现,在此基础上进行出现频度统计,不仅避免完整的子图同构判断问题,而且比使用完整出现列表节约了大量空间。综合以上技术,给出了频繁有根无序树挖掘算法Root-PJE,并且在人工数据集和真实数据集上进行性能测试,验证了性能比现有算法有较大提高。在频繁自由树的挖掘中,定义自由树的中心结点或双中心结点,将自由树转换为以中心结点为根的有根无序树。基于自由树的脊柱路径和最小脊柱串,定义自由树的脊柱串优先最小深度序列,在此基础上运用前缀结点进行深度扩展和广度连接,在常数时间内得到新的候选模式自由树。对候选模式自由树采用Apriori原理进行剪枝,并采用规范化嵌入出现列表进行频度统计。综合以上方法,给出频繁自由树挖掘算法Free-PJE,并且在人工数据集和真实数据集上进行性能测试,验证了性能比现有算法有较大提高。在频繁子图的挖掘中,将图分解为不包含叶结点的图核部分和不包含环的分支森林部分,定义分支森林在图核上的连接向量。由此定义最小“图核-分支-连接向量”三元组作为图的规范化标记形式。以扩展方法得到频繁模式图核,对一个图核由列举得到所有最小连接向量,由此将图看做是虚拟有根无序树,在此虚拟树上进行基于前缀结点的深度扩展和广度连接,从而在常数时间内得到新的候选模式图。采用基于Apriori原理的剪枝和基于规范化嵌入出现列表的出现频度统计。基于以上方法,给出频繁子图挖掘算法Graph-PJE。在人工数据集和真实数据集上进行了性能测试,验证了性能比现有算法有较大提高。为了提高图查询的效率,需要在图数据库中建立图索引。利用图数据库中的特征子图和其事务出现列表建立图索引。查询时,首先利用图索引得到查询图的候选查询结果集,然后验证每个候选结果图是否完整包含查询图。使用频繁子图挖掘结果作为图索引,可以保证候选查询结果集不大于频繁挖掘中的最小支持度。使用共享前缀树保存索引特征子图,只需保存有效事务出现列表,可以减小图索引的大小。在真实的分子结构图数据库中,将6边环和5边环看做虚拟原子,对分子结构图进行重构后建立图索引,可以大幅减小图索引的大小。利用真实数据集进行测试,验证了频繁子图索引的高效。利用新提出的频繁子结构索引和查询方法,以达梦关系数据库管理系统为平台,设计并实现了化学数据库系统的原型。在该数据库中,利用关系表存储化学结构数据和化学结构索引,利用外部存储过程,实现了化学结构数据的存储、索引、查询以及挖掘功能。