论文部分内容阅读
随着计算机与信息技术的发展,数据挖掘技术已经广泛应用到数据仓库、人工智能、模式识别、生物信息等许多领域。在研究逐步深入的过程中,愈来愈多的问题也呈现在我们面前。生物信息技术、社会网络模型分析、XML查询路径研究的迅速崛起,使事物之间的关系越来越复杂,人们开始意识到用树和图能更好地描述这些数据结构,进而在此基础上进行挖掘可以得到更多的有用信息。在树和图中,顶点对应对象中的实体,边对应实体之间的关系。但是,传统的针对序列、事务、文本等非结构化数据的挖掘方法已经不能满足不断出现的结构化数据的挖掘要求。因此,针对树、图等结构化数据,并结合非结构化数据挖掘方面的经验和方法论,来实现结构化数据高效挖掘的研究,已经成为数据挖掘研究领域的重要的研究方向。本文针对结构化数据的挖掘与处理目前研究的主要问题进行了研究,包括有序树和无序树的频繁Induced与Embedded子树的挖掘、子图同构的判断以及频繁子图挖掘、图结构数据的索引查询以及图的编辑距离的度量,具体做了以下一些工作:(1)研究了数据挖掘和频繁模式挖掘的相关知识和主要技术,其中,在树挖掘和图挖掘算法方面,分析了现有树和图的表示方式及标准化算法、频繁树和频繁图的增长模式以及影响树挖掘和图挖掘效率的关键因素,并分别对现有的树挖掘和图挖掘算法在这些关键因素中的处理方法进行了阐述和比较,指出它们所做的贡献,同时指出算法中仍需改进的地方。(2)考虑到现有树挖掘算法中,树的表示方式虽然能够等价地表示一棵树,但是这些表示方式并不能直观地表达一棵树,这样会导致精炼的频繁树挖掘思想在复杂的表示方式面前难以实施,从而使频繁树增长过程变得复杂,进而影响到了树挖掘整体的挖掘效率。本文提出了基于父子关系标识的前序遍历码的概念,能够简单直观地表示树结构,并针对有序树中的两个重要问题频繁Induced与Embedded子树挖掘,提出了基于先序等价码和模式增长思想的频繁子树挖掘算法ITMA和ETMA,提高了树挖掘的效率。此外,我们基于父子关系标识的前序遍历码的结构特点,提出了无序树中无序等价码的标准化算法UTS,并结合有序树中频繁子树的挖掘算法,提出了无序树中的频繁子树挖掘的算法UITMA和UETMA。(3)图同构判断是图挖掘算法中的一个关键问题,解决该问题的现有算法虽然在既有的图表示方式上都提出了相应的标准化的方法,从而使每一个图都对应唯一的编码,但这些同构判断算法在效率上存在一定的局限性。因为在频繁子图生成过程中,每一次从k项频繁图增长到k+1频繁图时,都要调用同构判断算法,因此判断效率的高低会直接影响到图挖掘算法整体的效率。我们提出了基于关联矩阵标准化的子图同构判断算法,有效地降低了判断的复杂度;在子图扩展方面,我们采用了深度优先的子图增长策略,从而显著地提高了图挖掘算法的效率。(4)图结构数据的查询是图挖掘中有着广泛应用背景的一个问题,我们提出了以边映射和频繁图分级建立图索引以及图库筛选的方法,有效地提高了查询速度。同时,在图像比对中发挥重要作用的问题——图的相似性度量与编辑距离求解方面,根据现有的代价矩阵,我们提出了用遗传算法解决求解最优编辑路径的算法,经实验证明,此方法可以快速有效地计算图之间的编辑距离。