论文部分内容阅读
随着计算机与信息技术的发展,人们在日常事务处理和科学研究中积累了大量数据。如何从中提取或“挖掘”用户所需要的信息,是当前信息科学技术领域面临的一大挑战。数据挖掘正是在这样的背景下发展而来。目前,数据挖掘及其应用己经渗透到多个学科,并在人工智能与机器学习、数据库、模式识别、生物信息学、神经网络等领域取得了丰硕的成果。频繁模式挖掘是数据挖掘领域的一个基本问题,其研究范围包括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中,如相关性分析,周期分析,最大模式,闭合模式,查询,分类,索引等等。在现实积累的大量数据中有一类诸如树、图等结构化的数据,它们具备很强的层次表达能力,几乎能够模拟所有的事物之间的联系,因此基于树的数据挖掘有着广阔的应用空间,如Web挖掘、空间数据挖掘、生物信息学中蛋白质结构挖掘、药物分子设计及其功能预测等等。如何发现挖掘频繁子树的高效算法,已日益成为数据挖掘中的一个新的研究热点,对频繁子树挖掘算法的研究将成为一个具有重要的理论意义和应用价值的研究课题。本文主要研究工作包括:(1)提出了一种基于子树向量的快速导出子树挖掘算法??ITMSV (induced subtrees mining based on subtree vector)。算法基于子树向量和哈希表构建一个多层的数据结构,在挖掘过程中能够减少树同构的判别时间,并且只需要进行一次数据库的扫描操作,减少了扫描次数,提高了算法的运行效率。(2)提出了一种可以在大型树数据库中高效挖掘无序树的算法??UTMiner(unordered trees miner),由于所挖掘的树具有无序的特性,因此为了避免挖掘出相同子树的情况,本文提出了一种高效的无序树的标准化方法,将无序树转化为标准化子树,再利用本文提出的快速有序树挖掘算法得到所有的标准化子树。(3)提出一种基于最小闭树特征集的聚类与分类方法,有效地解决了在实际应用中因数据量大而无法聚类与分类的问题。其基本思想为:提出以最小闭树特征集作为候选聚类与分类特征,并采用动态阈值按相似度聚类方法,使得树聚类快速而精确,提出树分类规则等级概念,并应用于树分类方法中,能迅速预测未知的树结构。