MapReduce环境下基于概念分层的概念格并行构造算法

doi:10.3969/j.issn.0253-2778.2018.04.002

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (4): 275-283.DOI: 10.3969/j.issn.0253-2778.2018.04.002

MapReduce环境下基于概念分层的概念格并行构造算法

蔡勇，陈红梅，

1.西南交通大学信息科学与技术学院,四川成都 611756;
2.四川省云计算与智能技术高校重点实验室,四川成都 611756

收稿日期:2017-05-23 修回日期:2017-06-24 出版日期:2018-04-30 发布日期:2018-04-30
通讯作者: 陈红梅
作者简介:蔡勇，男，1990年生，硕士生. 研究方向：数据挖掘. E-mail: yongcai@my.swjtu.edu.cn
基金资助:
国家自然科学基金(61572406)资助.

A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce

CAI Yong, CHEN Hongmei,

1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China
2. Key Laboratory of Cloud Computing and Intelligent Technology, Chengdu 611756, China）

Received:2017-05-23 Revised:2017-06-24 Online:2018-04-30 Published:2018-04-30

摘要/Abstract

摘要： 概念格是形式概念分析中的核心数据结构.对此提出运用划分分治和分层约束的方法研究MapReduce框架下概念格并行生成算法以有效地构造概念格.将形式背景按对象划分成外延独立子背景后并行计算子背景上的临时概念,融合各节点临时概念形成全局概念.全局概念按照各概念外延基数进行分层,通过分层约束计算概念父子节点的搜索范围和并行搜索各层概念的父子节点,进而构建概念格.算法基于MapReduce框架实现并在公共数据集上进行测试,实验结果表明,基于概念分层方法的概念格并行构造算法能够对大数据形式背景有效地进行处理.

关键词: 概念格, 概念分层, 并行计算, MapReduce

Abstract: Concept lattice is the core data structure of formal concept analysis. #br##br#A parallel algorithm is focused on for constructing concept lattice under the framework of MapReduce using the methods of divide and conquer based on partition and constrains in layers which aim to construct concept lattice effectively. Firstly, sub-formal contexts are formed by partitioning the formal context by objects and the concepts in each sub-formal context are calculated. Then the global concept is formed by merging concepts in different nodes. Next, different layers of concepts are formed by partitioning the global concept. Finally, constraints in different layers are used to compute the scope of search and concept lattice is constructed by searching and merging parent-son nodes in different layers of concepts. The proposed algorithm is realized in the framework of MapReduce. Extensive experiments carried out on public datasets verify the effectiveness of the parallel algorithm based on concept layer to deal with the formal context in big data.

Key words: concept lattice, hierarchical concept, parallel computing, MapReduce

中图分类号:

TP311

蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.

CAI Yong, CHEN Hongmei,. A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce[J]. Journal of University of Science and Technology of China, 2018, 48(4): 275-283.

参考文献

［1］ WILLE R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts[M]. Newtherland: Springer, 1982: 445-470.
[2] DAZ-AGUDO B， GONZLEZ-CALERO P A. Formal concept analysis as a support technique for CBR[J]. Knowledge-based Systems, 2001, 14(3): 163-171.
[3] SHIVHARE R, CHERUKURI A K. Three-way conceptual approach for cognitive memory functionalities[J]. International Journal of Machine Learning and Cybernetics, 2017, 8(1): 21-34.
[4] KONECNY J, KRIDLO O. On biconcepts in formal fuzzy concept analysis[J]. Information Sciences, 2017, 375(1): 16-29.
[5] 张磊，张宏莉，韩道军，等. 基于概念格的RBAC模型中角色最小化问题的理论与算法[J]. 电子学报, 2014, 12(42): 2371-2378.

[6] GODIN R, MISSAOUI R, ALAOUI H. Incremental concept formation algorithms based on Galois (concept) lattices[J]. Computational Intelligence, 1995, 11(2): 246-267.
[7] CARPINETO C, ROMANO G. GALOIS: An order-theoretic approach to conceptual clustering[M]// Machine Learning. Morgan: Kaufmann Publishers, 1993, 33-40.
[8] GANTER B, WILLE R. Formal concept analysis. Mathematical Foundations[M]. New York: Springer-Verlag, 1999.
[9] 谢润，李海霞，马骏，等. 概念格的分层及逐层建格法[J]. 西南交通大学学报，2005, 40(6): 837-841.
[10] 张继福，张素兰，胡立华. 约束概念格及其构造方法[J]. 智能系统学报，2006, 1(2): 31-38.
[11] 智慧来,智东杰,刘宗田.概念格合并原理与算法[J].电子学报,2010, 38(2): 455-460.
[12] 齐红，刘大有，胡成全，等. 基于搜索空间划分的并行概念生成算法[J]. 计算机科学，2005, 32(4): 55-58.
[13] 胡学刚，张玉红，唐志军，等. 一种新的概念格并行构造方法[J]. 合肥工业大学学报，2005, 28(12): 1523-1527.
[14] 李云，程伟，陈崚，等. 基于消息传递的概念格并行构造[J]. 计算机应用与软件，2006, 23(8): 3-5.
[15] 董辉，马垣，宫玺. 一种新的概念格并行构造算法[J]. 计算机科学与探索，2008, 2(6): 651-657.
[16] 王玮，张继福. 一种基于网格的概念格分布式构造算法[J]. 太原科技大学学报，2010, 31(3): 197-201.
[17] XU B, FREIN R, ROBSON E, et al. Distributed Formal Concept Analysis Algorithms based on An Iterative MapReduce Framework[M]. Berlin: Springer-Verlag, 2012: 292-308.
[18] DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters[J], Communication of ACM, 2008, 51: 107-113.
[19] 黄龙涛, 邓水光, 戴康, 等. 基于MapReduce的并行Web服务自动组合[J]. 电子学报, 2012,7(40): 1397-1403.
[20] KIM Y, SHIM K, KIM M S, et al. DBCURE-MR: An efficient density-based clustering algorithm for large data using MapReduce[J]. Information Systems, 2014, 42(6): 15-35.
[21] 张钧波, 李天瑞, 潘毅, 等. 云平台下基于粗糙集的并行增量知识更新算法[J]. 软件学报, 2015,26(5): 1064-1078.

()
(

[1]	苏浩，刘其成，牟春晓. 基于MapReduce的商品评论热点发现算法研究[J]. 中国科学技术大学学报, 2019, 49(2): 112-118.
[2]	陈锋，张智，李琴剑，陈宇强，陈国良. FCD大数据并行处理的动态任务调度算法[J]. 中国科学技术大学学报, 2018, 48(9): 718-722.
[3]	王进，王鸿，夏翠萍，欧阳卫华，陈乔松，邓欣. 基于Spark的组合分类器链多标签分类方法[J]. 中国科学技术大学学报, 2017, 47(4): 350-357.
[4]	郭景，陈贤富. 基于OpenCL的加速鲁棒特征算法并行实现[J]. 中国科学技术大学学报, 2017, 47(10): 808-816.
[5]	陈远，汪璟玢. 分布式RDF关键词近似搜索方法[J]. 中国科学技术大学学报, 2017, 47(10): 823-836.
[6]	谢青，彭威，柳瑶阁，黄涛，卢德唐. 改进的储层直接取样随机模拟方法及GPU实现[J]. 中国科学技术大学学报, 2013, 43(8): 626-630.

MapReduce环境下基于概念分层的概念格并行构造算法

A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价