|
|
|
| A Batch Constructing Algorithm of Frequent Weighted Concept Lattice |
| WANG Xin-Xin,ZHANG Ji-Fu,ZHANG Su-Lan |
| School of Computer Science and Technology,Taiyuan University of Science and Technology,Taiyuan 030024 |
|
|
|
|
Abstract Concept lattice is an effective tool for knowledge representation and data analysis. Weighted concept lattice is a concept lattice structure which depicts the importance of intention. A batch constructing algorithm of frequent weighted concept lattice is proposed by using the concept of virtual node. Firstly, it is proved that frequent weighted concept lattice is a complete lattice by defining the concept of virtual node, thereby the defect of having no supremum/infimum for some frequent weighted nodes in previous frequent weighted concept lattics proposed by Zhang is avoided. Secondly, frequent node, virtual node and their edges are generated from the bottom to the top. Thus, the time and the storage complexity of constructing the lattice is reduced and the efficiency of batch constructing the frequent weighted concept lattice is improved. Finally, the experimental results validate the correctness and the validity of the proposed algorithm by taking the star spectrum data as the formal contexts.
|
|
Received: 07 February 2009
|
|
|
|
|
|
[1] Wille R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts // Rival I, ed. Ordered sets. Dordrecht, Netherlands: Reidel, 1982: 415-470
[2] Hu Keyun, Lu Yuchang, Shi Chunyi. Advances in Concept Lattice and Its Application. Tsinghua Science and Technology: Natural Science, 2000, 40(9): 77-81 (in Chinese)
(胡可云,陆玉昌,石纯一.概念格及其应用进展.清华大学学报:自然科学版, 2000, 40(9): 77-81)
[3] van der Merwe D, Obiedkov S, Kourie D. AddIntent: A New Incremental Algorithm for Constructing Concept Lattices // Proc of the 2nd International Conference on Formal Concept Analysis. Sydney, Australia, 2004: 205-206
[4] Troy A D, Zhang Guoqiang, Tian Ye. Faster Concept Analysis // Proc of the 15th International Conference on Conceptual Structures. Sheffield, UK, 2007: 206-219
[5]Choi V. Faster Algorithms for Constructing a Concept (Galois) Lattice // Proc of the SIAM Conference on Discrete Mathematics. Victoria, Canada, 2006: 1-15
[6] Kuznetsov S O, Obedkov S A. Comparing Performance of Algorithms for Generating Concept Lattices. Journal of Experimental and Theoretical Artificial Intelligence, 2002, 14(2): 189-216
[7] Godin R, Missaoue R, Alaui H. Incremental Concept Formation Algorithms Based on Galois (Concept) Lattice. Computational Intelligence, 1995, 11(2): 246-267
[8] Zhang Jifu, Zhang Sulan, Zheng Lian. Weighted Concept Lattice and Incremental Construction. Pattern Recognition and Artificial Intelligence, 2005, 18(2): 171-176 (in Chinese)
(张继福,张素兰,郑 链.加权概念格及其渐进式构造.模式识别与人工智能, 2005, 18(2): 171-176)
[9] Ganter B, Will R. Formal Concept Analysis: Mathematical Foundation. Berlin, Germany: Springer, 1999
[10] Zhang Sulan, Zhang Jifu, Gao Sufang. The Construction of Weighted Concept Lattice and Association Rule Extraction. Computer Engineering and Applications, 2005, 41(7): 172-176 (in Chinese)
(张素兰,张继福,高愫邡.加权概念格的渐进式构造及其关联规则提取.计算机工程与应用, 2005, 41(7): 172-176)
[11] Wang Yumin, Li Hui, Liang Chuanjia. Information Theory and Code Theory. Beijing, China: Higher Education Press, 2005 (in Chinese)
(王育民,李 晖,梁传甲.信息论与编码理论.北京:高等教育出版社, 2005)
[12] Zuo Xiaoling. Discrete Mathematics. Shanghai, China: Shanghai Scientific and Technical Literature Press, 1981 (in Chinese)
(左孝凌.离散数学.上海:上海科学技术文献出版社, 1981) |
|
|
|
2010, Vol. 23 
