基于属性偏序结构图的关联规则提取方法

针对Apriori算法生成大量冗余关联规则的问题，本文提出了一种基于属性偏序结构图的关联规则提取方法。该方法旨在寻找相同支持度下的最大频繁项目集，进而提取无冗余关联规则。本文提出的方法不仅减少了挖掘频繁项目集的数量，从而提高关联规则提取的效率，而且将关联规则转换成属性偏序结构图中的知识表示形式，实现了频繁项分层的关联规则可视化展示。具有较强的可读性，有助于用户对关联规则进行深入分析，提高对潜在知识的利用和发掘程度。

关联规则挖掘是数据挖掘研究中的一个重要部分，旨在挖掘数据库中有意义的关联。1993 年由Agrawal 等[1]提出的Apriori 算法，是经典的挖掘布尔型频繁项目集的算法并得到广泛使用。

利用Apriori算法获得的关联规则往往存在大量的冗余，而且对规则的可视化存在不足。关联分析与规则的可视化结合，有利于人们发现隐藏的知识，已经引起了许多学者的关注。概念格是一种从形式背景进行数据分析和规则提取的强有力工具，通过生成Hasse 图能够直观表示出概念之间的层次关系，并且能够体现概念之间的泛化和例化关系[2]。因此在形式概念分析理论下，基于概念格的关联规则提取的研究倍受学者关注[3] [4]。目前，已有很多基于概念格的规则提取算法。胡可云[5]等提出一个从概念格上提取关联规则和分类规则的算法，实现了关联规则和分类规则的挖掘在概念格框架下的统一。王德兴等[6]利用量化概念格获取频繁项目集， 方法直观， 表示简洁。

杨葛英等[7]提出了以概念格为背景的关联规则可视化方法， 在概念格中展现关联规则路径。

形式概念分析强调的是属性与对象之间严谨的充要关系，与形式概念分析理论不同，关联规则注重的是属性间联系的紧密程度，而属性偏序结构图恰好提供了较为松散的属性关联研究视角。属性偏序结构图[8]是从形式概念分析理论发展而来的不同原理的知识发现数学方法，它从认知事物的角度出发，挖掘形式背景中对象之间、属性之间以及属性与对象之间的关系。属性偏序结构图中边与边之间不交叉， 当形式背景中对象和属性增加时，概念格的复杂程度增大，可读性降低，而属性偏序结构图仍然层次关系明确，因此有助于更直观地进行知识模式发现和规则提取。目前属性偏序结构图在中医药数据挖掘、模式识别分类等相关研究中取得了很好的应用效果[9] [10] [11]。本文主要研究无冗余关联规则提取方法和关联规则可视化表现形式，提出了一种基于属性偏序结构图的关联规则提取方法。将无冗余关联规则提取问题转化成挖掘数据集中相同支持度下的最大频繁项目集问题，并把频繁项转化成属性偏序结构图中的知识表示，为关联规则的提取提供了新的发现视角。理论分析证明，本文提出的方法是有效的。

2. 预备知识 定义1 [1]称(), , KU A I=为一个形式背景，其中U 为对象集，A 为属性集，I 为U 和A 之间的二元