【作者】 王德兴；

【导师】 刘晓平； 胡学钢；

【作者基本信息】 合肥工业大学 ， 计算机应用技术， 2007， 博士

【摘要】 关联规则挖掘是数据挖掘领域的一个重要分支，在研究及应用方面已取得了很大的进展。然而，由于现实世界数据的海量、异构和数据类型的多样性、结构的复杂性等特点，对关联规则挖掘的研究提出了新的课题。本文将具有完备特性的概念格模型引入到关联规则挖掘的研究，针对关联规则挖掘的模型、方法以及数据归约等方面开展了研究，主要内容及创新工作如下：1．在研究概念格模型和频繁项目集关系的基础上，提出了基于概念格模型的项目集表示和求解方法。研究表明，每个项目集一定作为概念格中某个概念的内涵或内涵的子集出现，借助于概念之间的关系可从每个概念导出多个项目集。因此，概念格中概念的数量比事务数据库中项目集的实际数量有显著的减少，在不丢失有效信息的前提下，较利于实现更大规模的数据库中知识发现；通过删除概念格中非频繁项目集对应的概念而得到的剪枝概念格能有效地压缩数据库规模，进而为在大规模数据库中进行关联规则挖掘提供了有利的条件。2．研究了基于剪枝概念格的关联规则挖掘求解。提出顺序剪枝和同步剪枝概念格的构造算法。顺序剪枝概念格构造算法以插入记录方式的Godin概念格构造算法为基础，通过一遍扫描数据库来构造概念格，在构建完毕后，依据Apriori性质实现剪枝，得到剪枝概念格；同步剪枝概念格构造算法以插入属性方式动态地构造概念格，在插入属性构造概念格的过程中，依据Apriori性质实现剪枝，得到剪枝概念格。两种构造算法各有特点和适用性。基于剪枝概念格挖掘关联规则，减少相应的搜索空间，提高关联规则挖掘的效率。3．研究了多层、多属性的归纳。实际数据库中的属性值之间的层次差异较大，需要进行必要的数据归约。经典的属性归纳方法存在主观因素制约的问题，可能会影响到有价值模式的发现。为此，将概念格模型引入多层、多属性的归纳，提出了基于概念格的属性归纳，采用概念的爬升进行相应的泛化，并进行多层、多属性的归纳。与面向属性归纳AOI算法相比较，基于概念格的属性归纳不仅可实现AOI的单一属性归纳，也能进行多层、多属性的归纳，属性归纳的路径不惟一，并易于寻找合适的泛化路径和阈值，从而得到用户要求的、合理的属性归纳结果，以便挖掘合适颗粒度的关联规则。更多还原

【Abstract】 Association rule mining is an important branch of data mining, the research and applications on which have been already made significant progress. However, due to the immense data, heterostructure and multiplicity of data types, complicated data structures in databases are available in the real world, those have made association rule mining face a lot of challenges, therefore, the complete concept lattice model is introduced to the study of association rule mining in the dissertation, and some studies are made on concept lattice model, algorithms, and data reduction etc. Contributions of the dissertation are as follows:1. On the basis of study on the relationship of concept lattice model and frequent itemsets, the itemsets representation and their solution methods are proposed. The study shows that each itemset should be presented as the intents or sub-intents of one concept in the concept lattice, thus it is able to completely describe these itemsets, similarly, many itemsets are derived from one concept through the relations among concepts in the concept lattice, consequently, the number of concepts in the concept lattice is reduced more markedly than that of itemsets in transaction databases, which can be used in KDD effectively without any valid information loss, Besides, pruned concept lattice, derived form concept lattice by deleting the infrequent concepts, not only cuts efficiently down the sizes of databases, but also is convenient to association rule mining.2. The study is made on the solution to association rule mining algorithm based on the pruned concept lattice, the build algorithms of sequential and synchronal pruned concept lattice is proposed, the former constructs concept lattice by the records insertion on the basis of Godin build algorithm, which need scan the databases only once, finishes the pruning by the Apriori properties after having completed the concept lattice construction, whereas, the latter dynamically constructs concept lattice by the attributes insertion, which implements the pruning by the Apriori properties in the course of concept lattice construction, these concept lattice build algorithms have their own characteristics and applicabilities. Association rule mining based on pruned concept lattice reduces the search space, and the efficiency of association rules mining algorithm is improved.3. Generalization with multi-level and multi-attribute is studied. There are many differences among attribute values in the practical databases, thus data reduction should be done necessarily. However, there are subjective limits in typical generalization methods, which maybe make an impact on valued model discovery, therefore, attribute-oriented induction algorithm based on concept lattice, one of multi-attributes generalization model, is presented, which can carry out the generalization with multi-level and multi-attribute through concepts ascension in the concept lattice.Compared with Attribute-Oriented Induction (AOI) algorithm, proposed by Han Jiawei, the former can not only perform the same task of the latter, but also carry out the generalization with multi-level and multi-attribute, but the generalization paths are not one and only, and the proper generalization paths and thresholds can be easily found in the concept lattice, then the required reasonable results can be obtained so that thses proper granule association rules can be mined.更多还原