在概念格上基于最大频繁项集关联规则提取算法|频繁项集 关联规则

　　摘要：许多研究表明概念格是数据分析与规则提取的一种有效工具。本文首先提出基于最大频繁项集幂集格上的规则提取算法。然后对此种算法进行改进，在已建好的概念格上直接从最大频繁项集进行规则提取，因而提高了挖掘关联规则的效率，适用于大型数据库中关联规则的挖掘。
　　关键词：形式背景；概念格；关联规则
　　中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)18-31644-02
　　An Algorithm of Extract Association Rules form Concept Lattice Based on the Biggest Frequent Item Sets
　　SHI Wu-lue, WANG Li-Ju
　　(Department of Information,LiaoNing University of finance & work,ShenYang 110122,China)
　　Abstract:Many research have shown that concept lattice (Galeis lattice ) is an efficient tool for data analysis and rule extraction .It is convenient to model dependence and casualty ,and provide a vivid and concise account of the relations among the variables in the universe of discourse. The paper proposes an algorithm that can extract association rules form power-set lattice based on the biggest frequent item sets. The paper also improves the algorithm to extract rules directly from the built concept lattice. Then the presented algorithm shows much better performance and is suitable to the mining of association rules in large databases.
　　Key words:formal contex;concept lattice;association rule
　　
　　1 引言
　　
　　在从数据库中获取知识的过程中，建造与应用概念层次结构具有许多优点 ，在此基础上易于建立数据间依赖或因果关系模型，对于概念间泛化与例化关系具有清晰简明的描述。概念层次结构并非局限于一般的树型结构，wille R 等提出了根据二元关系来建造概念格的基本思想 ，这种形式格结构及其Hasses 图就表示一种概念层次结构。
　　在文献[6] [7]中都提出了在概念格上进行规则提取的一种算法，[6]中提出的算法考虑了所有结点的情况，并且产生了大量的冗余规则。在[7]中对[6]中的算法进行了改进，生成频繁概念格，在频繁概念格上进行规则提取，但是关联规则只要在最大频繁项集上进行规则提取即可。所以，以往所提出的在概念格上进行规则提取的算法对于关联规则的提取还不完善。
　　本文首先介绍概念格的一些基本概念，其次提出一种基于最大频繁项集的幂集格上提取关联规则的算法，然后对这种算法进行了改进，在已经建好的概念格上直接从最大频繁项集的概念提取关联规则。所生成的结果与文献 具有相同的规则形式。
　　
　　2 基本概念[2，4，5]
　　
　　定义1（概念格）：假设给定信息表T=（O，D，R）其中O是对象集合，D是描述符（属性）集合，R是O和D之间的一个二元关系[1] ，则存在唯一的一个偏序集合与之对应，并且这个偏序集合产生一种格结构，这种由T所诱导的格L就称为一个概念格[2,5]或伽罗瓦格（Galois格）[4] 。
　　
　　3 基于最大频繁项集幂集格的关联规则提取
　　
　　下面提出了一种生成关联规则的算法：基本思想是先通过概念格求出最大频繁项集。然后求出最大频繁项集的幂集格。在幂集格上提取规则。下面给出提取规则所依据的主要定义：
　　定义3（最大频繁项集）：若{Ii1,...,Iik}是一个项集，|{Ii1,...,Iik}|≥D× Min-sup （其中D为事务总数Min-sup为最小支持度）但再增加任何一项，上式都不能满足。
　　(2)画出每个最大频繁项集S的幂集格求出最小S1作为规则的左部，推出最简规则。
　　
　　4 结束语
　　
　　本文首先提出了在最大频繁项集的幂集格上进行最简关联规则的提取，然后对其进行改进，提出了在概念格上直接从最大频繁概念推出最简关联规则，此种算法主要适用于关联规则的提取。
　　
　　参考文献：
　　[1]Hong J,Mao C Incremental discovery of rules and structure by hierarchical and parallel clustering. In:piatetsky-ShapiroG,Frawleg W J eds. .Knowledge Discovery in Databases.Menlopark, California :AAAIpress/The MIT press ,1991.177-194
　　[2]Wile R.Restructuring lattice theory:an approach based on hierarchies of concepts.In:Rival I ed.Dordrecht:reidel,1982.445-470.
　　[3]MissaouiR,Godin R.Search for concepts and dependencies in database.In:Ziarkow p ed.Rough Sets,and Fuzzy Sets and Knowledge Discovery.London: Springer-Verlag ,1994.16-23
　　[4]Godin R, MissaouiR , AlauiH .省略putational Intelligence,1995,11(2):246-267
　　[5]Wile R.Knowledge acquisition by method of formal concept analysis.In:Diday E ed .Data Analysis,learning Symbolic and Numeric Knowledge.New York:Nova Science Publisher,1989,365-380.
　　[6]胡可云,陆玉昌,石纯一.基于概念格的分类和关联规则集成挖掘方法.软件学报,2000,11(11):478-483.
　　[7]王德兴,胡学刚,王浩.基于量化概念格的关联规则挖掘.合肥工业大学学报,2002,25(5):678-682.
　　[8]Oosthuizen G D.Rough sets and Concept lattice.In: ZiarakoW P ed . Rough Sets, and Fuzzy Sets and Knowledge Discovery .London: Springer-Verlag,1994.24-31.
　　[9]Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning about data.Dordrecht :Kluwer Academic in Publisher,1991.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文