近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，数据资料的规模急速膨胀。于是，人们希望有新一代的技术和工具能够智能地自动地帮助人们分析已经消耗大量财力与物力所收集与整理的海量数据，以发现有用的知识，达到为决策服务的目的。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘(Data Mining)技术应运而生，并得以蓬勃发展。数据挖掘，指的是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。作为数据挖掘当前研究的主要模式之一的关联规则则用于确定数据集中不同领域或属性之间的联系，找出可信的、有价值的多个域之间的依赖关系。本文的工作在关联规则挖掘的范畴以内，根据关联规则的生成的二个主要阶段：频繁模式的获取和关联规则的生成进行了深入的拓展性研究。首先讨论的是关联规则生成的问题。通过在统一的概率论的范畴内重新定义兴趣度的概念，使得负项的引入有了理论依据，并通过对负项的进一步限定，提出产生包含负项的关联规则IAR算法，使关联规则包含的语义更加完整，规则本身也更有意义，特别是在有概念层次的情况下。这些工作的结晶就是一个基于关联规则的数据挖掘工具ARMiner。其次，在经历了近10年的发展以后，关联规则挖掘中至关重要的频繁模式获取技术得到了很大的发展。但这些工作都是以项(集)为基本操作对象的，而现实生活中，万物皆有内在的联系，彼此之间构成一张复杂的网。这时再孤立地看待每个事物就显得不太合适了。另一方面，这些内在联系可以用图的形式来表述。同时，随着各种新应用的不断推出，人们将注意力逐步向图中的频繁模式的产生问题转移。论文首先选择唯一标号图作为研究的突破口，先后提出了Matricon和SFP算法。由于唯一标号图能转换为项集的形式，这就能充分利用近10年来的研究成果。唯一不同的地方是在连通性上的进一步考虑。两个算法中，前者基于Apriori思想，后者则充分利用了FP-Growth的特点。Matricon算法中利用关联矩阵形式代表图的方法和SFP算法中利用顶点重叠判连通性的思想在下一步非唯一标号图的分析中也是一个重要工具。在应用方面，由于互联网上的节点可以被唯一标定，唯一标号图分析算法就被成功地用于对Web权威资源的分析工作中。当取消了标号唯一性限定后，论文解决了有序标号树中的模式发现问题。这里，论文先后描述了Chopper和Spanner算法。这些算法不仅在性能上要优复旦大学博士学位论文2一于同类算法，更重要的是它提出了树的序列化表示和先同分后异构的思想。这两个思想可以有效地提高算法的效率，将树的分析工作中所遇到的瓶颈——同构问题的求解延后，并最大可能地缩小了同构判定的搜索空间范围。这里的各个算法还被用在了对以XML文档为代表的半结构化文档和Web日志的分析工作中，并取得了一些很有意思的结论。 最后，论文解决了以图同构为核心的频繁子图抽取问题。通过充分惜鉴己有的较成功的ACGM和FSG算法，经过综合分析比较，描述了TOpology算法。这是一个以Apriori思想为主体，以先同分后异构为框架，以图的序列化及矩阵表示和标号连通判定等技术为手段的一个综合算法。Topology算法可以真正面对现实世界中各事物之间的内在联系分析问题，使得频繁模式的获取实现了从项到图的拓展。 论文的最后部分对全部工作进行了总结，并结合当前研究的最新进展提出了在图中考虑生成包含“负项”的关联规则，对图本身的拓展和新领域中的关联规则挖掘技术三个方向，为未来的工作提供了一个参照。