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

刘美玉; 祁建军; 刘伟

doi:10.7652/xjtuxb202109021

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- 三支概念格中的关联规则提取算法
- Extracting Association Rules in Three-Way Concept Lattices
- 西安交通大学学报 2021年55卷第9期页码：189-196
- 作者机构：
  
  西安电子科技大学计算机科学与技术学院,西安,710071
- 作者简介：
- 基金信息：
  
  : 2021-03-30。作者简介: 刘美玉(1996—),女,硕士生;祁建军(通信作者),男,副教授。基金项目: 国家自然科学基金资助项目(61772021,61976244);陕西省自然科学基础研究计划资助项目(2021JM-141)
- DOI：10.7652/xjtuxb202109021
  中图分类号： TP18
- 网络首发：2021-09-10，
  
  纸质出版：2021
- 稿件说明：
移动端阅览
刘美玉, 祁建军, 刘伟. 三支概念格中的关联规则提取算法[J]. 西安交通大学学报, 2021,55(9):189-196.

Extracting Association Rules in Three-Way Concept Lattices[J]. 2021, 55(9): 189-196.
刘美玉, 祁建军, 刘伟. 三支概念格中的关联规则提取算法[J]. 西安交通大学学报, 2021,55(9):189-196. DOI： 10.7652/xjtuxb202109021.

Extracting Association Rules in Three-Way Concept Lattices[J]. 2021, 55(9): 189-196. DOI： 10.7652/xjtuxb202109021.

摘要

针对基于形式概念分析的关联规则提取侧重属性之间的正关联、忽略负关联的问题

提出一种基于三支概念分析的关联规则提取算法(3ARM)。利用对象导出三支概念的内涵包括表达“共同具有”语义的正属性子集和表达“共同不具有”语义的负属性子集的特点

结合三支概念格的泛化与例化结构

高效地提取正负关联规则; 基于三支概念的闭项集特性

从三支概念格中选出包含频繁项集的候选概念进行挖掘

减少不必要的搜索; 通过对三支概念之间的关系进行研究

从父子概念中提取无冗余的正关联规则和负关联规则

再从兄弟概念中提取正负规则对规则集进行补充

充分挖掘三支概念格中的知识。MovieLens数据集上的实验结果表明:应用3ARM算法

在最小支持度为10%时

得到正规则86 027条

负规则93 685条; 3ARM算法得出的正规则数量比FARM算法的多出0.9倍～1.5倍

减少了FISM算法最多28.3%的冗余负规则

分别减少了FISM和FARM算法44%～63%和27%～62%的运行时间。

Abstract

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%

86 027 positive rules and 93 685 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.

关键词

Keywords

references

AGRAWAL R, IMIELISKI T, SWAMI A. Mining association rules between sets of items in large databases [C]∥Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 1993: 207-216.

GANTER B, WILLE R. Formal concept analysis: mathematical foundations [M]. Cham, Germany: Springer, 1999: 284.

ZAKI M J, HSIAO C J. Efficient algorithms for mining closed itemsets and their lattice structure [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(4): 462-478.

STUMME G, TAOUIL R, BASTIDE Y, et al. Computing iceberg concept lattices with Titanic [J]. Data Knowledge Engineering, 2002, 42(2): 189-222.

KIM E H, KIM H G, HWANG S H, et al. FARM: an FCA-based association rule miner [J]. Knowledge-Based Systems, 2015, 85: 277-297.

谢志鹏, 刘宗田. 基于概念格的关联规则发现 [J]. 小型微型计算机系统, 2000, 21(10): 1028-1031.

XIE Zhipeng, LIU Zongtian. Concept lattice based association rule discovery [J]. Mini-Micro Systems, 2000, 21(10): 1028-1031.

谢志鹏, 刘宗田. 概念格与关联规则发现 [J]. 计算机研究与发展, 2000, 37(12): 1415-1421.

XIE Zhipeng, LIU Zongtian. Concept lattice and association rule discovery [J]. Journal of Computer Research and Development, 2000, 37(12): 1415-1421.

XIE Zhipeng, LIU Zongtian. From intent reducts for attribute implications to approximate intent reducts for association rules [C]∥Proceedings of the 5th International Conference on Computer and Information Technology. Piscataway, NJ, USA: IEEE, 2005: 162-169.

WANG Dexing, HU Xuegang, LIU Xiaoping, et al. Association rules mining on concept lattice using domain knowledge [C]∥Proceedings of the 2005 International Conference on Machine Learning and Cybernetics. Piscataway, NJ, USA: IEEE, 2005: 2151-2154.

王志海, 胡可云, 胡学钢, 等. 概念格上规则提取的一般算法与渐进式算法 [J]. 计算机学报, 1999, 22(1): 66-70.

BRIN S, MOTWANI R, SILVERSTEIN C. Beyond market baskets: generalizing association rules to correlations [C]∥Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 1997: 265-276.

RODRIGUEZ-JIMENEZ J M, CORDERO P, ENCISO M, et al. Negative attributes and implications in formal concept analysis [J]. Procedia Computer Science, 2014, 31: 758-765.

MISSAOUI R, NOURINE L, RENAUD Y. Generating positive and negative exact rules using formal concept analysis: problems and solutions [C]∥Proceedings of the 6th International Conference on Formal Concept Analysis. Cham, Germany: Springer, 2008: 169-181.

YAO Yiyu. Three-way decision: an interpretation of rules in rough set theory [C]∥Proceedings of 2009 International Conference on Rough Sets and Knowledge Technology. Cham, Germany: Springer, 2009: 642-649.

QI Jianjun, WEI Ling, YAO Yiyu. Three-way formal concept analysis [C]∥Proceedings of 2014 International Conference on Rough Sets and Knowledge Technology. Cham, Germany: Springer, 2014: 732-741.

QI Jianjun, QIAN Ting, WEI Ling. The connections between three-way and classical concept lattices [J]. Knowledge-Based Systems, 2016, 91: 143-151.

祁建军, 汪文威. 多线程并行构建三支概念 [J]. 西安交通大学学报, 2017, 51(3): 116-121.

QI Jianjun, WANG Wenwei. A multithreaded parallel algorithm for constructing three-way concepts [J]. Journal of Xi'an Jiaotong University, 2017, 51(3): 116-121.

CHEN Xiaoyu, QI Jianjun, ZHU Xiaomin, et al. Unlabelled text mining methods based on two extension models of concept lattices [J]. International Journal of Machine Learning and Cybernetics, 2020, 11(2): 475-490.

REN Ruisi, WEI Ling. The attribute reductions of three-way concept lattices [J]. Knowledge-Based Systems, 2016, 99: 92-102.

WEI Ling, LIU Lin, QI Jianjun, et al. Rules acquisition of formal decision contexts based on three-way concept lattices [J]. Information Sciences, 2020, 516: 529-544.

魏玲, 赵思雨. 三支概念分析中的粒与知识结构 [J]. 西北大学学报(自然科学版), 2020, 50(4): 537-545.

WEI Ling, ZHAO Siyu. Granules and knowledge structure in three-way concept analysis [J]. Journal of Northwest University(Natural Science Edition), 2020, 50(4): 537-545.

汪文威, 祁建军. 三支概念的构建算法 [J]. 西安电子科技大学学报, 2017, 44(1): 71-76.

WANG Wenwei, QI Jianjun. Algorithm for constructing three-way concepts [J]. Journal of Xidian University, 2017, 44(1): 71-76.

刘琳, 钱婷, 魏玲. 基于属性导出三支概念格的决策背景规则提取 [J]. 西北大学学报(自然科学版), 2016, 46(4): 481-487.

LIU Lin, QIAN Ting, WEI Ling. Rules extraction in formal decision contexts based on attribute-Induced three-way concept lattices [J]. Journal of Northwest University(Natural Science Edition), 2016, 46(4): 481-487.

刘琳, 魏玲, 钱婷. 决策形式背景中具有置信度的三支规则提取 [J]. 山东大学学报(理学版), 2017, 52(2): 101-110.

LIU Lin, WEI Ling, QIAN Ting. Three-way rules extraction in formal decision contexts with confidence [J]. Journal of Shandong University(Natural Science), 2017, 52(2): 101-110.

ZHANG Chengqi, ZHANG Shichao. Association rule mining [M]. Cham, Germany: Springer, 2002: 238.

BALAKRISHNA E, RAMA B, NAGARAJU A. Efficient mining of negative association rules using frequent item set mining [C]∥Proceedings of the 1st International Conference on Artificial Intelligence and Cognitive Computing. Cham, Germany: Springer, 2018: 709-716.

HE Xu, MIN Fan, ZHU W. Top-N recommendation based on granular association rules [C]∥Proceedings of 2014 International Conference on Rough Sets and Knowledge Technology. Cham, Germany: Springer, 2014: 194-205.

李昌盛, 伍之昂, 张璐, 等. 关联规则推荐的高效分布式计算框架 [J]. 计算机学报, 2019, 42(6): 1218-1231.

LI Changsheng, WU Zhiang, ZHANG Lu, et al. An efficient distributed-computing framework for association-rule-based recommendation [J]. Chinese Journal of Computers, 2019, 42(6): 1218-1231.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

提取有效规则的关联分类算法

采用类别相似度聚合的关联文本分类方法

一种应用关联规则森林的改进贝叶斯分类算法

高效的用户访问预测新算法

多线程并行构建三支概念