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

doi:10.3969/j.issn.0253-2778.2018.04.002

Abstract

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

CLC Number:

TP311

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.

References

［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]	SU Hao, LIU Qicheng, MU Chunxiao. Research on product reviews hot spot discovery algorithm based on MapReduce [J]. Journal of University of Science and Technology of China, 2019, 49(2): 112-118.
[2]	CHEN Feng, ZHANG Zhi, LI Qinjian, CHEN Yuqiang, CHEN Guoliang. Dynamic task scheduling algorithm of parallel computing for FCD big data [J]. Journal of University of Science and Technology of China, 2018, 48(9): 718-722.
[3]	WANG Jin, WANG Hong, XIA Cuiping, OUYANG Weihua, CHEN Qiaosong, DENG Xin. Ensembles of classifier chains for multi-label classification based on Spark [J]. Journal of University of Science and Technology of China, 2017, 47(4): 350-357.
[4]	GUO Jing, CHEN Xianfu. Parallel implementation of surf algorithm based on OpenCL [J]. Journal of University of Science and Technology of China, 2017, 47(10): 808-816.
[5]	CHEN Yuan, WANG Jingbin. Distributed keyword approximate search method for RDF [J]. Journal of University of Science and Technology of China, 2017, 47(10): 823-836.
[6]	XIE Qing, PENG Wei, LIU Yaoge, HUANG Tao, LU Detang. Improvements for direct sampling stochastic simulation and GPU implementation [J]. Journal of University of Science and Technology of China, 2013, 43(8): 626-630.