三支概念格中的关联规则提取算法

Extracting Association Rules in Three-Way Concept Lattices

针对基于形式概念分析的关联规则提取侧重属性之间的正关联、忽略负关联的问题,提出一种基于三支概念分析的关联规则提取算法(3ARM)。利用对象导出三支概念的内涵包括表达“共同具有”语义的正属性子集和表达“共同不具有”语义的负属性子集的特点,结合三支概念格的泛化与例化结构,高效地提取正负关联规则;基于三支概念的闭项集特性,从三支概念格中选出包含频繁项集的候选概念进行挖掘,减少不必要的搜索;通过对三支概念之间的关系进行研究,从父子概念中提取无冗余的正关联规则和负关联规则,再从兄弟概念中提取正负规则对规则集进行补充,充分挖掘三支概念格中的知识。MovieLens数据集上的实验结果表明:应用3ARM算法,在最小支持度为10%时,得到正规则86027条,负规则93685条;3ARM算法得出的正规则数量比FARM算法的多出0.9倍~1.5倍,减少了FISM算法最多28.3%的冗余负规则,分别减少了FISM和FARM算法44%~63%和27%~62%的运行时间。

Aiming at the problem that the association rule extraction based on formal concept analysis focuses on positive association and ignores negative association between attributes,an association rule extraction method based on three-way concept analysis,named 3ARM,is proposed.The intent of object-induced three-way concept is composed of two parts,including the positive attribute subset that expresses the semantics of“jointly possessed”and the negative attribute subset that expresses the semantics of“jointly not possessed”.The 3ARM algorithm uses these characteristics of object-induced three-way concept and the generalization and instantiation structure of three-way concept lattice to efficiently extract the positive and negative association rules.Based on the characteristics of the closed itemsets of three-way concepts,candidate concepts containing frequent itemsets are selected from three-way concept lattices for mining,so unnecessary searches are reduced.By studying the relationship between three-way concepts,extracting non-redundant positive and negative association rules from parent-child concepts,and then extracting the positive and negative rules from sibling concepts to supplement the rule set,the knowledge in three-way concept lattices can be fully dug up.Experimental results on the MovieLens dataset show that using the 3ARM algorithm,when the minimum support is 10%,86027 positive rules and 93685 negative rules are obtained.The number of positive rules obtained by 3ARM is 0.9-1.5 times more than that of FARM,reducing the redundant negative rules of FISM by up to 28.3%,and reducing the running time of the FISM and FARM algorithms by 44%-63%and 27%-62%respectively.