ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

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

  • 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

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.04.002
  • Received Date: 23 May 2017
  • Rev Recd Date: 24 June 2017
  • Publish Date: 30 April 2018
    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.

    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.
    • FullText(HTML)
  • loading
    • References(21)
  • [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.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.
    Recommended articles
    TrendMD
    Volume 48 Issue 4 page: 275-283
    Cover

    Article Metrics

    Article views (894) PDF downloads(418)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return