多关系频繁模式发现研究

频繁模式发现是数据挖掘的重要任务之一。现实数据通常存储于由多个关系组成的关系数据库中。传统的频繁模式发现方法只能直接完成单一关系中的模式发现,如果要完成多关系数据的挖掘,会产生操作复杂性和信息丢失等问题。多关系数据挖掘是当前数据挖掘研究中快速发展的重要领域之一。多关系频繁模式发现方法能够直接从复杂结构化数据中发现涉及多个关系的复杂频繁模式,避免了传统方法的局限。本文首先归纳多关系频繁模式发现方法的发生历史背景,其次分析总结多关系频繁模式发现方法,最后提出了多关系频繁模式发现将来发展需重点解决的问题和面临的挑战。

面向语义的精简化多关系频繁模式发现方法

多关系频繁模式发现能够直接从复杂结构化数据中发现涉及多个关系的复杂频繁模式,避免了传统方法的局限。有别于主流基于归纳逻辑程序设计技术的方法,提出了基于合取查询包含关系的面向语义的精简化多关系频繁模式发现方法,具有理论与技术基础的新颖性,解决了两种语义冗余问题。实验表明,该方法在可理解性、功能、效率以及可扩展性方面具有优势。

一种无背景知识的多关系频繁模式发现算法研究

在无背景知识的面向数据的频繁模式发现研究中按照关系数据库概念重新定义了面向数据的多关系频繁模式发现任务和搜索空间.同时,使用了一个优化的精化算子构建搜索空间,这一精化算子一方面有效地利用了关系数据库隐含的数据模式特征,从而能够自然地构建有趣形态的模式,另一方面能够在不过度限制搜索空间的情况下避免等价模式的产生.建立了一个候选模式评估共享计算策略,从而降低了方法评估阶段的时间复杂性.实验表明,所提出的MRFP-DA算法整体上具有良好的效率和可扩展性.

面向对象数据库中的频繁模式发现

提出了基于高阶归纳逻辑编程发现面向对象数据库中的频繁模式的算法。此算法使用高阶逻辑编程语言Escher作为数据及模式表示语言。由于高阶逻辑编程语言不仅能描述复杂结构的数据而且还能描述复杂的模式，以及Escher语言的强类型语法能有效缩小由于高阶逻辑编程语言较强表达能力所带来的较大的模式搜索空间，故此算法能充分利用面向对象数据库中丰富的语义信息引导频繁模式搜索过程且能发现复杂频繁模式。实验证明，此算法在效率和发现的频繁模式质量上都优于经典的WARMAR算法。

协议签名特征自动发现方法

数据包应用层固定位置频繁出现的字节组合是识别应用层协议的一种重要的签名特征(signature)。数据挖掘中经典的Apriori算法在提取协议签名特征时具有准确性高、覆盖面广等优势,但同时也存在候选集规模大、重复扫描数据库等问题。在运用深度包检测技术的基础上改进Apriori算法,有效降低计算复杂度,并能够自动发现一种由确定的字节值和字符类型组合而成的协议签名特征。实验表明,文章的方法产生的签名特征具有准确的协议区分能力,并且在协议版本更新情况下的适应能力强,同时具有较好的未知协议特征发现能力。