● 摘要
随着网络技术和各行业信息化的发展，复杂结构数据的管理和挖掘在许多应用领域中的重要性越来越高，例如：电子商务、金融证券、生物信息、地震监测、地质勘探、航天器测试等。在这些应用领域中，其积累的数据量极其巨大、数据格式各种各样，例如：文本数据，数据库数据，XML数据等等，数据之间的关系复杂，例如序列数据、树数据、图数据等等。由于这些海量数据之间的复杂关系，复杂结构数据的模式挖掘变得非常困难。对这些复杂结构的数据进行数据挖掘，尤其是进行频繁生成器模式挖掘，从而探寻其中的规律，是极其具有挑战性的工作。针对上述问题，本文重点研究了复杂结构生成器模式挖掘中的静态数据集上的序列生成器模式挖掘、数据流环境下的序列生成器模式挖掘、子树生成器模式挖掘等关键问题。主要研究成果如下：(1)提出了一种高效的序列生成器模式挖掘算法在电子商务、商业智能、生物信息、金融银行、地震监测预报等应用领域中，如何在海量的序列数据库中挖掘出有用的序列生成器模式是一个研究热点。现有的序列生成器挖掘方法由于未能充分利用序列及其子序列之间关联关系而造成挖掘算法的时间开销较大，针对这个问题，分析了序列生成器模式的一些性质，提出了一种基于深度优先搜索策略的序列生成器挖掘算法，给出了有效的LSI剪枝策略，并设计了快速的序列生成器检查机制。在模拟数据集以及国际公认的实际数据集上进行了大量的实验，结果表明，该算法比已有的最好的算法具有时间开销较低，在不同规模的序列数据库上具有可扩展性。(2)提出了一种流滑动窗口中的序列生成器模式挖掘算法数据流中的数据具有高速、无界、数据分布随时间不断变化、只能一次性扫描等特点，在动态的数据流环境中如何有效挖掘频繁序列生成器模式是一个新的挑战。针对该挑战，分析了序列生成器在数据流环境中的一些性质，提出了在一种滑动窗口上的动态序列数据环境中如何有效的维护序列生成器模式的方法StreamSeqGen，设计了一个序列生成器候选集枚举树用于存储序列生成器候选集，当流滑动窗口随时间变化时，它能在该枚举树中有效维护序列生成器和非生成器之间的边界变化。在不同的流数据集上对该算法进行了大量实验，结果表明算法StreamSeqGen在运行时间上具有高效性，并优于现有的一些其他算法，并在滑动窗口规模上具有可扩展性。(3)提出了一种高效的子树生成器模式挖掘算法Internet网络的快速发展以及XML数据的特点促进了XML数据等树结构数据的广泛应用。XML树型数据的广泛应用及XML子树信息提取的复杂性导致了难以有效挖掘频繁子树生成器模式的问题。由于频繁模式的向下闭的性质，挖掘所有的频繁子树模式可能导致指数级规模的结果集。子树生成器模式非常适合对频繁子树模式结果集进行有效的压缩。因此，如何有效的挖掘树结构数据集中的子树生成器模式是一个挑战性的问题。针对该问题，分析了子树生成器模式的一些性质，提出了一种有效的基于深度优先搜索的挖掘算法RTGener。设计了两个有效的剪枝策略--左空间剪枝策略和右路径剪枝策略来减少搜索空间，避免冗余计算。最后在实际数据集上进行了大量的实验，实验结果表明提出的算法RTGener在运行时间上具有高效性，在数据集规模上具有可扩展性。