Computer Science ›› 2016, Vol. 43 ›› Issue (6): 223-228.doi: 10.11896/j.issn.1002-137X.2016.06.045

Previous Articles     Next Articles

Research of Distributed Integration Algorithm on Concept Lattices

FAN Shu-yuan, WANG Li-ming, JIANG Qin and ZHANG Zhuo   

  • Online:2018-12-01 Published:2018-12-01

Abstract: With the advent of the era of big data,the distributed storage and computing of massive data are increasingly important,and the distributed integration of concept lattices is particularly urgent.In order to solve the problem of long constructing time of concept lattice.This paper put forward the concept lattices oriented distributed integration algorithm.Integration of concept lattice are defined as follows:concepts in sub-concept lattice are sorted according to the decreases of intent number,and then the sub-concept lattices are integrated into a global concept lattice. Two types of integration are selected to construct the global concept Lattice in this paper:one is the add lattice merge,the master node receives and integrates sub-concept lattices that come from all child nodes;the other way is called two-way merge,firstly,its sub-concept lattices from all child nodes are integrated,and then the master node receives and integrates the sub-concept lattices.The experiments show that two kinds of distributed integration strategy of concept lattice have their advantages and disadvantages,but both of them can effectively reduce the time of constructing concept lattice.

Key words: Sub-concept lattice,Global concept lattice,Distributed,Add lattice merge,Two way merge

[1] Ganter B,Wille R.Formal Concept Analysis:Mathematical Foun-dations[M].Germany:Springer-Verlag,1999
[2] Chai Yu-mei,Wang Chun-li,Wang Li-ming.An Algorithm for Mining Complement-Alternative Relationship Based on Frequent Itemsets[J].Pattern Recognition and Artificial Intelligence,2012,25(1):157-165(in Chinese) 柴玉梅,王春丽,王黎明.基于频繁项集的互补替代关系挖掘算法[J].模式识别与人工智能,2012,25(1):157-165
[3] Wang Li-ming,Zhang Zhuo.An Algorithm for Mining ClosedFrequent Itemsets Based on Apposition Assembly of Iceberg Concept Lattices [J].Journal of Computer Research and Deve-lopment,2007,44(7):1184-1190(in Chinese) 王黎明,张卓.基于iceberg概念格并置集成的闭频繁项集挖掘算法[J].计算机研究与发展,2007,44(7):1184-1190
[4] Zhang Zhuo.Research on Web Database Extraction Based onFormal Concept Analysis[D].Wuhan:Wuhan University,2011(in Chinese) 张卓.基于形式概念分析的Web数据库抽取研究[D].武汉:武汉大学,2011
[5] Fu H,Nguifo M.A parallel algorithm to generate formal concepts for large data[C]∥New York:Springer-Verlag,2004.2014:394-401
[6] Kuznetsov S O,Obiedkov S A.Comparing performance of algorithms for generating concept lattices[J].Journal of Experimental and Theoretical Artificial Intelligence,2002,14(2/3):189-216
[7] Lindig C.Fast Concept Analysis:2000[C]∥Aachen.Germany:Shaker-Verlag,2000:152-161
[8] Godin R,Missaoui R,Alaoui H.Incremental concept formation algorithms based on Galois (concept)lattices[J].Computational Intelligence,1995,11(2):246-267
[9] Belohlavek R.Fuzzy Galois Connections[J].Math.LogicQuarterly,1999,45(4):497-504
[10] Valtchev P,Missaoui R.Building Concept (Galois) Latticesfrom Parts:Generalizing the Incremental Methods[M]∥Conceptual Structures:Broadening the Base.Springer Berlin Heidelberg,2001:290-303
[11] Valtchev P,Missaoui R,Lebrun P.A partition-based approach towards constructing Galois (concept) lattices[J].Discrete Mathematics,2002,256(3):801-829
[12] Zhi Hui-lai,Zhi Dong-jie,Liu Zong-tian.Theory and Algorithm of Concept Lattice Union[J].Actaelectronica Sinica,2010,38(2):455-459(in Chinese) 智慧来,智东杰,刘宗田.概念格合并原理与算法[J].电子学报,2010,38(2):455-459
[13] Chai Yu-mei,Zhang Zhuo,Wang Li-ming.An Algorithm forMining Global Closed Frequent Itemsets Based on Distributed Frequent Concept Direct Product[J].Chinese Journal of Computers,2012,35(5):990-1001(in Chinese) 柴玉梅,张卓,王黎明.基于频繁概念直乘分布的全局闭频繁项集挖掘算法[J].计算机学报,2012,35(5):990-1001
[14] Krajca P,Outrata J,Vychodil V.Parallel Recursive Algorithm for FCA[J].Concept Lattices and Their Applications,2008,433(2008):71-82
[15] Liu Bao-xiang,Li Yan.Construction Principles and Algorithms of Concept Lattice Generated by Random Decision Formal Context[J].Conputer Science,2013,40(6A):90-92(in Chinese) 刘保相,李言.随机决策形式背景下的概念格构建原理与算法[J].计算机科学,2013,40(6A):90-92
[16] Krajca P,Outrata J,Vychodil V.Parallel algorithm for computing fixpoints of Galois connections[J].Annals of Mathematics and Artificial Intelligence,2010,59(2):257
[17] Zhang Zhuo,Du Juan,Wang Li-ming.Load balance-based algorithm for parallelly generating fuzzy formal concepts[J].Control and Decision,2014,29(11):1935-1942(in Chinese) 张卓,杜鹃,王黎明.基于负载均衡的模糊概念并行构造算法[J].控制与决策,2014,29(11):1935-1942
[18] Ma F,Yu J,Zeng Z,et al.A Distributed Concept Lattices Vertical Union Method[J].International Conference on Artificial Intelligence & Computational Intelligence,2010,3:469-473

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!