Roll-Up and Drill-Down Building Algorithms of Layered Concept Lattice
ZHANG Jialu1, WU Xia1, ZHONG Jiaming2, LU Ruhua3
1.College of Mathematics and Finance, Xiangnan University, Chenzhou 423000 2.College of Economic and Management, Xiangnan University, Chenzhou 423000 3.College of Software and Communication Engineering, Xiangnan University, Chenzhou 423000
Abstract A model of layered concept lattice is established, when the attributes of a formal context can be decomposed into some sub-attributes. The relationship between the original concept lattice and the layered concept lattice is discussed. Two algorithms are proposed: the roll-up algorithm and the drill-down algorithm. In the roll-up algorithm, the upper concept is constructed by the lower concept, and in the drill-down algorithm, the lower concept is constructed by the upper concept. Examples and numerical experiments show that the layered concept lattice model can be used to model complex attribute data. Furthermore, the roll-up algorithm and the drill-down algorithm improve the efficiency of building concept lattice.
Fund:Supported by Natural Science Foundation of Hunan Province(No.2017JJ2241,2016JJ6138), Social Science Foundation of Hunan Province(No.16YBA329,13YBB205)
Corresponding Authors:
WU Xia(Corresponding author), master, associate professor. Her research interests include non-classical mathematical logics and approximate reasoning theory.
About author:: ZHANG Jialu, master, professor. His research interests include non-classical mathematical logics, approximate reasoning theory and intelligent information processing;ZHONG Jiaming, master, professor. His research interests include intelligent information processing;LU Ruhua, master, lecturer. Her research interests include intelligent computing.
[1] YAO Y Y. Granular Computing: Basic Issues and Possible Solutions[C/OL]. [2017-08-20]. http://www2.cs.uregina.ca/~yyao/PAPERS/basic.pdf. [2] 张文修,梁 怡,吴伟志.粗糙集与概念格.西安:西安交通大学出版社, 2006. (ZHANG W X, LIANG Y, WU W Z. Rough Sets and Concept La-ttice. Xi′an, China: Xi′an Jiaotong University Press, 2006.) [3] 周 彤,张家录.基于信息量的属性相关性及其应用.计算机工程与设计, 2012, 33(3): 1192-1196, 1217. (ZHOU T, ZHANG J L. Relativity of Attributes in Information Systems and Its Application. Computer Engineering and Design, 2012, 33(3): 1192-1196, 1217.) [4] LIN T Y. Granular Computing // Proc of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. New York, USA: Springer, 2003: 16-24. [5] PEDRYCZ W. Granular Computing: An Emerging Paradigm. Heidelberg, Germany: Physica-Verlag, 2001. [6] 张 钹,张 铃.问题求解的理论与应用.第2版.北京:清华大学出版社, 2007. (ZHANG B,ZHANG L. Theory and Application of Problem So-lving. 2nd Edition. Beijing, China: Tsinghua University Press, 2007.) [7] GANTER B, WILLE R. Formal Concept Analysis: Mathematical Foundations. Berlin, Germany: Springer-Verlag, 1999. [8] KUZNETSOV S O, OBIEDKOV S A. Comparing Performance of Algorithms for Generating Concept Lattices. Journal of Experimental and Theoretical Artificial Intelligence, 2002, 14(2/3): 189-216. [9] LI Q G, GUO L K. Formal Query Systems on Contexts and a Representation of Algebraic Lattices. Information Sciences, 2013, 239: 72-84. [10] 陈庆燕.Bordat概念格构造算法的改进.计算机工程与应用,2010, 46(35): 33-35, 38. (CHEN Q Y. Improvement on Bordat Algorithm for Constructing Concept Lattice. Computer Engineering and Applications, 2010, 46(35): 33-35, 38.) [11] 张 卓.基于形式概念分析的Web数据库抽取研究.博士学位论文.武汉:武汉大学, 2011. (ZHANG Z. Research on Web Database Extraction Based on Formal Concept Analysis. Ph.D. Dissertation. Wuhan, China: Wuhan University, 2011.) [12] 柴玉梅,张 卓,王黎明.基于频繁概念直乘分布的全局闭频繁项集挖掘算法.计算机学报, 2012, 35(5): 990-1001. (CHAI Y M, ZHANG Z, WANG L M. An Algorithm for Mining Global Closed Frequent Itemsets Based on Distributed Frequent Concept Direct Product. Chinese Journal of Computers, 2012, 35(5): 990-1001.) [13] 范淑媛,王黎明,姜 琴,等.概念格的分布式集成算法研究.计算机科学, 2016, 43(6): 223-228, 275. (FAN S Y, WANG L M, JIANG Q, et al. Research of Distributed Integration Algorithm on Concept Lattice. Computer Science, 2016, 43(6): 223-228, 275.) [14] 智慧来.不完备形式背景上的知识表示.计算机科学, 2015, 42(1): 276-278. (ZHI H L. Knowledge Representation on Incomplete Formal Context. Computer Science, 2015, 42(1): 276-278.) [15] WOLFF K E. Conceptual Interpretation of Fuzzy Theory // Proc of the 6th European Congress on Intelligent Techniques and Soft Computing. Berlin, Germany: Springer-Verlag, 1998, I: 555-562. [16] JUANDEABURRE A B, FUENTES-GONZÁLEZ R. The Study of L-Fuzzy Concept Lattices. Mathware & Soft Computing, 1994, 1(3): 209-218. [17] 强 宇,刘宗田,林 炜,等.模糊概念格在知识发现的应用及一种构造算法.电子学报, 2005, 33(2): 350-353. (QIANG Y, LIU Z T, LIN W, et al. Research on Fuzzy Concept Lattice in Knowledge Discovery and a Construction Algorithm. Acta Electronica Sinica, 2005, 33(2): 350-353.) [18] JAOUA A, ELLOUMI S. Galois Connection, Formal Concepts and Galois Lattice in Real Relations: Application in a Real Classifier. Journal of Systems and Software, 2002, 60(2): 149-163. [19] 曲开社,翟岩慧,梁吉业,等.形式概念分析对粗糙集理论的表示及扩展.软件学报, 2007, 18(9): 2174-2182. (QU K S, ZHAI Y H, LIANG J Y, et al. Representation and Extension of Rough Theory Based on Formal Concept Analysis. Journal of Software, 2007, 18(9): 2174-2182.) [20] LIU W, XU W J, FU J F, et al. An Extended Description Logic for Event Ontology // Proc of the 5th International Conference on Advances in Grid and Pervasive Computing. Berlin, Germany: Springer-Verlag, 2010: 471-481. [21] 王元卓,靳小龙,程学旗.网络大数据:现状与展望.计算机学报, 2013, 36(6): 1125-1138. (WANG Y Z, JIN X L, CHENG X Q. Network Big Data: Present and Future. Chinese Journal of Computers, 2013, 36(6): 1125-1138.) [22] 王洪艳,郭云峰.大数据技术在人工智能中的应用研究.数字技术与应用, 2015(12): 109-110. (WANG H Y, GUO Y F. Application of Big Data Technology in Artificial Intelligence. Digital Technology and Application, 2015(12): 109-110.) [23] 智慧来.面向异构数据分析的形式概念分析扩展模型.电子学报, 2013, 41(12): 2451-2455. (ZHI H L. Extended Model of Formal Concept Analysis Oriented for Heterogeneous Data Analysis. Acta Electronica Sinica, 2013, 41(12): 2451-2455.)
2018, Vol. 31 
