概念格结构及布局优化方法的研究
|
摘要
形式概念分析作为一种用于数据组织和数据分析的形式化工具,在理论研究和实际应用上都具有重要意义,它己经在多个领域获得了成功的应用。概念格作为形式概念分析中核心的数据结构,本质上描述了对象和特征之间的联系,表明了概念之间的泛化与例化关系,其相应的布局图(Hasse图)则实现了对数据的可视化。
概念格的可视化给人们提供了直观的分析与观察知识单元内在关系的方法,概念格的构造和良好的布局是形式概念分析应用的前提。在概念格的构造和布局过程中,利用现有的方法布局出的概念格图形,在层与层之间产生了过多的边交叉数,使整个格图看起来杂乱无章,用户很难从中找到有用的信息,直接影响了概念格图形的可读性。因此,减少格图中的边交叉数,将概念格的可视化表示形式清晰、美观地展现出来显得尤为重要。
本文在目前已有的概念格构造算法和模型的基础上,结合遗传算法对概念格图形的布局进行了研究,提出了基于遗传算法的概念格结构布局优化策略,通过一个概念格分层图模型,介绍了求解边交叉数以及最优边交叉数问题的方法。
本文的主要成果包括:
1、从概念格分层图的角度提出了“边的跨度”和“规则概念格图形”的概念。并给出了从“非规则概念格图形”到“规则概念格图形”的转换方法。
2、设计了概念格的矩阵表示,通过此方法可以用二进制字符串表示出编码后的概念格。
3、将遗传算法引入概念格分层图布局中边交叉数优化问题的求解,提出了基于遗传算法的概念格图形布局优化算法。并对实验结果进行了分析,然后和传统的概念格图形分层布局算法进行了比较。
Formal Concept Analysis, regarding as a formalization tool which is used for data organization and date analysis, which has profound significance on both theory research and practical application, and it has received successful application in many fields. As the central data structure in Formal Concept Analysis, the concept lattices describes the connection between objects and features in essence, and it illustrates the connection between generalization and specialization of concepts. The Hasse diagram of a concept lattice implements the visualization of data.
The visualization concept lattices provide an intuitionist method for analyzing and observing the internal relation of knowledge components. The concept lattice structure and good layout are the preconditions of the analysis and application of formal concept. In the process of concept lattices construction and layout, it is difficult to use the existing method to find the useful information for users, because of the excessive number of edge crossing between layers. This kind of concept lattices structure is too complexity to read and understand. Therefore, in order to make the visualization of concept lattices clearly, a new valid and feasible method for concept lattices layout to reduce the number of edge crossing is especially in need.
On the base of the current constructure algorithms and models of concept lattices, this paper studies concept lattices graphics layout Combining genetic algorithm and proposes a optimization strategy of concept lattices structure based on genetic algorithms. Then through a layout model of concept lattices, introducing how to find the methods to calculate the number of edge crossing and the optimization number of edge corssing between layers.
the main fruits of the dissertation includes.
1. Putting forwards the concept of "regular concept lattices graphics" from the standpoint of concept lattices hierarchical graphics. Giving the conversion method from "irregular concept lattices graphics" to "regular concept lattices graphics".
2. Designing concept lattices matrix indication, which can express the encoded concept lattices through the binary strings.
3 Introducing genetic algorithm to the seeking-solving of optimization problems for the number of edge crossing in concept lattices graphics layout, and puts forwards the optimization algorithm of concept lattices graphics layout in terms of genetic algorithm. Analyzed the experimental results to compare to the traditional graphical hierarchical algorithm of concept lattices.
概念格的可视化给人们提供了直观的分析与观察知识单元内在关系的方法,概念格的构造和良好的布局是形式概念分析应用的前提。在概念格的构造和布局过程中,利用现有的方法布局出的概念格图形,在层与层之间产生了过多的边交叉数,使整个格图看起来杂乱无章,用户很难从中找到有用的信息,直接影响了概念格图形的可读性。因此,减少格图中的边交叉数,将概念格的可视化表示形式清晰、美观地展现出来显得尤为重要。
本文在目前已有的概念格构造算法和模型的基础上,结合遗传算法对概念格图形的布局进行了研究,提出了基于遗传算法的概念格结构布局优化策略,通过一个概念格分层图模型,介绍了求解边交叉数以及最优边交叉数问题的方法。
本文的主要成果包括:
1、从概念格分层图的角度提出了“边的跨度”和“规则概念格图形”的概念。并给出了从“非规则概念格图形”到“规则概念格图形”的转换方法。
2、设计了概念格的矩阵表示,通过此方法可以用二进制字符串表示出编码后的概念格。
3、将遗传算法引入概念格分层图布局中边交叉数优化问题的求解,提出了基于遗传算法的概念格图形布局优化算法。并对实验结果进行了分析,然后和传统的概念格图形分层布局算法进行了比较。
Formal Concept Analysis, regarding as a formalization tool which is used for data organization and date analysis, which has profound significance on both theory research and practical application, and it has received successful application in many fields. As the central data structure in Formal Concept Analysis, the concept lattices describes the connection between objects and features in essence, and it illustrates the connection between generalization and specialization of concepts. The Hasse diagram of a concept lattice implements the visualization of data.
The visualization concept lattices provide an intuitionist method for analyzing and observing the internal relation of knowledge components. The concept lattice structure and good layout are the preconditions of the analysis and application of formal concept. In the process of concept lattices construction and layout, it is difficult to use the existing method to find the useful information for users, because of the excessive number of edge crossing between layers. This kind of concept lattices structure is too complexity to read and understand. Therefore, in order to make the visualization of concept lattices clearly, a new valid and feasible method for concept lattices layout to reduce the number of edge crossing is especially in need.
On the base of the current constructure algorithms and models of concept lattices, this paper studies concept lattices graphics layout Combining genetic algorithm and proposes a optimization strategy of concept lattices structure based on genetic algorithms. Then through a layout model of concept lattices, introducing how to find the methods to calculate the number of edge crossing and the optimization number of edge corssing between layers.
the main fruits of the dissertation includes.
1. Putting forwards the concept of "regular concept lattices graphics" from the standpoint of concept lattices hierarchical graphics. Giving the conversion method from "irregular concept lattices graphics" to "regular concept lattices graphics".
2. Designing concept lattices matrix indication, which can express the encoded concept lattices through the binary strings.
3 Introducing genetic algorithm to the seeking-solving of optimization problems for the number of edge crossing in concept lattices graphics layout, and puts forwards the optimization algorithm of concept lattices graphics layout in terms of genetic algorithm. Analyzed the experimental results to compare to the traditional graphical hierarchical algorithm of concept lattices.
引文
[1] B.Ganter and R.Wille. Formal Concept Analysis: Mathematical Foundations[M]. Berlin Heidelberg: Springer-Verlag, 1999.
[2] J. H. Holland. Adaptation in Natural and Artificial System[M]. The Univ Michigan Press, 1975.
[3] SHEN WEI-XIANG and HUANG JING-WEI, Edge Crossing Minimization Algorithm for Hierarchical Graphs Based on Genetic Algorithms[J]. Wuhan University Journal of Natural Sciences. Vol.6 No.1-2, 555-559, 2001.
[4] 陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,164-191,1985.
[5] Richard Jeffrey Cole. Automated layout of concept lattices using layer diagrams and additive diagrams[J]. In Michael Oudshoorn, editor, 24th Australasian Computer Science Conference, IEEE Computer Society, pages 47–53, 2001.
[6] Richard Cole. Automatic Layout of Concept Lattices using Force Directed Placement and Genetic Algorithms[J]. In Proc. of the 23th Australasian Computer Science Conference, pages 47–53. Australian Computer Science Communications,IEEE Computer Society, 2000.
[7] M.R.Garey and D.S.Johnson. Crossing Number is NP-Complete. SIAM J.Algebraic Discrete Methods,4(3):312-316,1983.
[8] Ralph Freese. Automated Lattice Drawing[J]. Second International Conference on Formal Concept Analysis, ICFCA,Sydney,Australia, 2004.
[9] HUAIGUO FU, ENGELBERT MEPHU NGUIFO: A Parallel Algorithm to Generate Formal Concepts for Large Data. ICFCA: Sydney, Australia 394-401, 2004.
[10] Robert Godin, Kokia Missaoui, Hassan Alaoui, “Incremental concept formation algorithms based on Galois (Concept) lattices”, Computational Intelligence, 11(2), Page(s): 246-267, 1995.
[11] Philipp Cimiano, Andreas Hotho, Gerd Stumme, Julien Tane: Conceptual Knowledge Processing with Formal Concept Analysis and Ontologies. Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004.
[12] YUN LI, ZONGTIAN LIU, et al. Theoretical research on the distributed construction of concept lattices [A]. Proceedings of the Second International Conference on Machine Learning and Cybernetics [C]. Xian: Institude of Electrical and Electronics, 474 – 479, 2003.
[13] Nourine L, Raynaud O. A fast algorithm for building lattices. Information Processing Letters, 71: 199-204. 1999.
[14] Luksch P,Skosrksy M,Wille R.On drawing concept lattices with a computer.In W.Gaul and M.Schader,editors,Classifcation as a tool of research,North Holland,Amsterdam.269～274,1986.
[15] E. M?kinen and M. Sieranta, Genetic algorithms for drawing bipartite graphs. Intern. J. Computer Math. 53, 157-166,1994.
[16] D.I. OSTRY, Some Three-Dimensional Graph Drawing Algorithms. Master's thesis, Department of Computer Science and Software Engineering, The University of Newcastle, Australia, 1996.
[17] Freese R.Automated Lattice Drawing.Second International Conference on Formal Concept Analysis, ICFCA, Sydney, Australia, 2004.
[18] Eloranta, T. and M?kinen, E., TimGA: a genetic algorithm for drawing undirected graphs. Divulg. Mat. 155-170.
[19] R. Cimikowski. Algorithms for the fixed linear crossing number problem. Disc.Appl. Math., 122:93–115, 2002.
[20] M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Alg.Disc. Meth., 4:312–316, 1983.
[21] Huang, J., Xu, J.-M, The bondage numbers of graphs with small crossing numbers, Discrete Mathematics. 307,1881-1897,2007.
[22] P. Eades, A. Symvonis and S. Whitesides, Three-dimensional orthogonal graph drawing algorithms, Discrete Appl. Math. 103, 55–87, 2000.
[23] Wille R, Wolf A. An approach to automated drawing of concept lattices [R] . Germary : Technical University of Darmstadt , 125 – 136,1997.
[24] 马骏,沈夏炯等.基于三维空间的概念格自动布局[J].计算机科学.2006 年第 33 卷(6)期: 244-246.
[25] 胡可云,陆玉昌,石纯一.概念格及其应用进展[J],清华大学学报.2000 年第 40 卷(9)期: 77-81.
[26] Michalewicz Z.Genetic Algorithms+Data Structures=Evolution Programs. Springer-Verlag,Berlin .1992.
[27] 沈夏炯,韩道军,刘宗田,马骏,概念格构造算法的改进,计算机工程与应用,2004 年 24期:100-103.
[28] Petko Valtchev, Rokia Missaoui, Robert Godin: Formal Concept Analysis for Knowledge Discovery and Data Mining: The New Challenges. Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004.
[29] Carpineto C, Romano G. Galois: an order-theoretic approach to conceptual clustering [A]. Utgoff P ed. Proceedings of ICML-93 [C]. Amherst: Elsevier. 33-40, 1993.
[30] Juan M. Cigarrán, Anselmo Pe?as, Julio Gonzalo, Felisa Verdejo: Automatic Selection of Noun Phrases as Document Descriptors in an FCA-Based Information Retrieval System. Third International Conference on Formal Concept Analysis, ICFCA 2005, Lens, France, February 49-63, 2005.
[31] Njiwoua P, Mephu Nguifo E. A parallel algorithm to build concept lattice. In proceedings of 4th Groningen Intl. Information Technical Conference for Students, 103-107, 1997
[32] 谢志鹏,刘宗田.概念格的快速渐进式构造算法.计算机学报,2002 年第 5 期:490-496.
[33] 胡可云,陆玉昌,石纯一,基于概念格的分类和关联规则的集成挖掘方法,软件学报,2000 年11(11)期:1478-1484.
[34] Rong Long Wang, Kozo Okazaki: An efficient parallel algorithm for the minimum crossing number problem. Neurocomputing 67: 411-416, 2005.
[35] Di Battista, G., Eades, P., Tamassia, R., and Tollis, I.G., Algorithms for drawing graphs: an annotated bibliography, Computational Geometry, 4:235–282, 1994.
[36] Eades, P., McKay, B.D., and Wormald, N., On an edge crossing problem, Proc. of the 9th Australian Computer Science Conference, 327–334, 1986.
[37] Yamaguchi, A. and Sugimoto, A., An approximation algorithm for the two-layered graph drawing problem, Proc. of the 6th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 1627, 81–91, 1999.
[38] Branke, J., Bucher, F., and Schmeck, H. Using genetic algorithms for drawing ndirected graphs. Tech. Rep. 347, D-76128 Karlsruhe, Germany, 1996.
[39] C.Kosak,J.Marks,and S.Shieber. A Parallel genetic algorithm for network-diagram layout. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 458-465,1991.
[40] Corey Kosak,Joe Marks,and Stuart Shieber.Automating the layout of network diagrams with specified visual organization. IEEE Transactions on Systems,Man,and Cybernetics, 24(3): 440-454,1994.
[41] A.O.Rodriguez and A.R.Suarez. Automatic graph drawing by genetic search. In ISPE/IEE/IFAC International Conference on CAD/CAM, Robotics and Factories of the Future,Pereira, Colombia, August 1995.
[42] Wille R. Restructuring lattice theory: an approachbased on hierarchies of concepts[A]. Rival I. Ordered sets[C]. Reidel,Dordrecht,Boston, 445- 470,1982.
[43] M. Huchard, H. Dicky and H. Leblanc. Galois lattice as a framework to specify building class hierarchies algorithms. Theoretical Informatics and Applications, 34:521–548, 2000.
[44] R. Godin and R. Missaoui. An incremental concept formation approach for learning from databases. Theoretical Computer Science, 133(2):387–419, 1994.
[45] F. Le Ber and A. Napoli. Design and comparison of lattices of topological relations based on galois lattice theory. In Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR-2002), Toulouse, pages 37–46, 2002.
[46] R. Wille. Lattices in data analysis: How to draw them with a computer.Algorithms and Order, pages 33–58, 1993.
[47] R. Wille. Concept lattices and conceptual knowledge systems. Computers & Mathematics With Applications, 23(6–9):493–515, 1992.
[48] Davey B. A., Priestley H. A., Introduction to Lattices and Order, Edition: Cambridge, Cambridge University Press, 1990.
[49] Wille R., Why can Concept Lattice Support Knowledge Discovery in DataBases, First Workshop on Formal Concept Analysis Advances for KDD, 2001.
[50] Maddouri M., A Formal Concept Analysis Tool for Automatic Structuring of Fuzzy Rule Bases, Invited paper to the IEEE International Conference On Systemics, Cybernetics and Informatics SCI-2001, Orlando-Florida, USA. ,uly 2001.
[51] Wille. R. (1997): Conceptual Graphs and Formal Concept Analysis. In: Lukose, D. et. al. (eds.): Conceptual Structures: Fulfilling Peirce’s Dream, Procs. of the ICCS’97. Springer, Berlin-New York 290-303, 1997.
[52] R. Wille. Restructuring lattice theory: an approach based on hierarchies of concepts. In: I.Rival (ed.): Ordered sets. Reidel, Dordrecht-Boston, 445-470.
[53] Ganter B(1984).Two basic algorithms in concept analysis, B4-Preprint No.831,TH Darmstadt.
[54] Stumme G,Taouil R,Bastide Y,Pasquier N,and Lakhal L(2000).Fast computation of concept lattices using data mining techniques.In Proceedings of 7th International Workshop on Knowledge Representation Meets Databases, KRDB, Berlin, Germany, 129-139, 2000.
[55] Chein M.Algorithme de recherche des sous-matrices premières d'unematrice. Bull.Math.Soc.Sci.Math.R.S.Roumanie,13:21–25, 1969.
[56] Bordat J P.Calcul pratique du treillis de Galois d'une correspondance. Math.Sci.Hum.,96:31–47, 1986.
[57] Lindig C.Fast concept analysis.In Stumme G(Eds.),Working with Conceptual Structures-Contributions to ICCS 2000,Shaker Verlag, Aachen,Germany, 2000.
[58] Carpineto C, and Romano G.Galois:an order-theoretic approach toconceptual clustering.In Proceedings of ICML-93, Amherst:Elsevier, 33-40, 1993.
[59] Van Der Merwe F,and Kourie D.AddAtom:an incremental algorithm for constructing concept-and concept sublattices.Technical report of the Department of Computer Science,University of Pretoria,South Africa, 2002.
[60] Van der Merwe F,Obiedkov S,and Kourie D.AddIntent:a new incremental algorithm for constructing concept lattices.In Eklund P(Eds.),Proceedings of 2nd International Conference on Formal Concept Analysis (ICFCA 2004),Sydney,372-358, 2004.
[61] Ho T B.Incremental conceptual clustering in the framework of Galois lattice.In Lu H,Motoda H and Liu H(Eds.),KDD:Techniques and Applications.World Scientific,49-64, 1997.
[62] Godin R, Mineau G, Missaoui R,St-Germain M & Faraj N. Applying concept formation methods to software reuse. International Journal of Knowledge Engineering and Software Engineering,5(1): 119-142, 1995.
[63] Lindig C. Concept-based component retrieval. In: Proc. IJCAI-95 Workshop on Formal Approaches to the Reuse of Plans, Proofs, and Programs, Montreal, August 1995.
[64] Godin R,Mili H,Mineau G .W, Missaoui R ,Arri A&Chau T-T. Design of class hierarchies based on concept (Galois) lattices. Theory and Application of Object Systems,4(2),117-134, 1998.
[65] Lindig C,Snelting G. Assessing modular structure of legacy code based on mathematical concept analysts.In: Proc. International Conference on Software Engineering(ICSE 97),Boston, USA,349-359, May 1997.
[66] R. Godin et al, Learning algorithms using Galois lattice Proceeding of the IEEE International Conference on Tools for AL. San Jose, GA, 22-29, 1991.
[67] Deursen A,and Kuipers T.Identifying objects using cluster and concept analysis.In Proceedings of the 21st International Conference on Software Engineering(ICSE'99), Los Angeles, California, 246-255, 1999.
[68] Snelting G. Reengineering of configurations based on mathematical concept analysis.Technical Report TR-95-02, Software Technology Department, Technical University of Braunschweig, 1995.
[69] Missaoui R, Godin R. Extracting exact and approximate rules from databases. In: AlagarV S, Bergler S, Dong F Q (Eds). Incompleteness and Uncertainty in information Systems.London: Springer-Verlag. 209-222 , 1994.
[70] 王志海,胡可云,胡学钢,刘宗田,张奠成,概念格上规则提取的一般算法与渐进式算法,计算机学报, 22 (1):66-70 ,1999.
[71] Keyun Hu, Yuchang Lu,Chunyi Shi.Incremental Discovering Association Rules: A Concept Lattice Approach, PAKDD'99, LNAI 1574, pp. 109-113, 1999.
[72] Godin R,Missaoui R,and April A(1993).Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods.International Journal of Man-Machine Studies,38:747-767.
[73] Carpineto C,and Romano G.Information retrieval through hybrid navigation of lattice representations. International Journal of Human-Computer Studies,45:553-578,1996.
[74] Richards D,and Compton P.Combining formal concept analysis and ripple down rules to support reuse,In Proceedings of Software Engineering Knowledge Engineering(SEKE'97),Springer Verlag, Skokie USA,177-184, 1997.
[75] Cole R, and Stumme G.CEM-a conceptual email manager.In Proceedings of the 8th International Conference on Conceptual Structures(ICCS'2000),Springer Verlag,438-452. 2000.
[76] Fernandez-Manjon B,Cigarran J,Navarro A,and Fernandez-Valmayor A(1998).Applying formal concept analysis to domain modeling in an intelligent help system.In Proceedings of Information Technology and Knowledge Systems, 5th IFIP World Computer Congress, Vienna- Budapest,1998.
[2] J. H. Holland. Adaptation in Natural and Artificial System[M]. The Univ Michigan Press, 1975.
[3] SHEN WEI-XIANG and HUANG JING-WEI, Edge Crossing Minimization Algorithm for Hierarchical Graphs Based on Genetic Algorithms[J]. Wuhan University Journal of Natural Sciences. Vol.6 No.1-2, 555-559, 2001.
[4] 陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,164-191,1985.
[5] Richard Jeffrey Cole. Automated layout of concept lattices using layer diagrams and additive diagrams[J]. In Michael Oudshoorn, editor, 24th Australasian Computer Science Conference, IEEE Computer Society, pages 47–53, 2001.
[6] Richard Cole. Automatic Layout of Concept Lattices using Force Directed Placement and Genetic Algorithms[J]. In Proc. of the 23th Australasian Computer Science Conference, pages 47–53. Australian Computer Science Communications,IEEE Computer Society, 2000.
[7] M.R.Garey and D.S.Johnson. Crossing Number is NP-Complete. SIAM J.Algebraic Discrete Methods,4(3):312-316,1983.
[8] Ralph Freese. Automated Lattice Drawing[J]. Second International Conference on Formal Concept Analysis, ICFCA,Sydney,Australia, 2004.
[9] HUAIGUO FU, ENGELBERT MEPHU NGUIFO: A Parallel Algorithm to Generate Formal Concepts for Large Data. ICFCA: Sydney, Australia 394-401, 2004.
[10] Robert Godin, Kokia Missaoui, Hassan Alaoui, “Incremental concept formation algorithms based on Galois (Concept) lattices”, Computational Intelligence, 11(2), Page(s): 246-267, 1995.
[11] Philipp Cimiano, Andreas Hotho, Gerd Stumme, Julien Tane: Conceptual Knowledge Processing with Formal Concept Analysis and Ontologies. Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004.
[12] YUN LI, ZONGTIAN LIU, et al. Theoretical research on the distributed construction of concept lattices [A]. Proceedings of the Second International Conference on Machine Learning and Cybernetics [C]. Xian: Institude of Electrical and Electronics, 474 – 479, 2003.
[13] Nourine L, Raynaud O. A fast algorithm for building lattices. Information Processing Letters, 71: 199-204. 1999.
[14] Luksch P,Skosrksy M,Wille R.On drawing concept lattices with a computer.In W.Gaul and M.Schader,editors,Classifcation as a tool of research,North Holland,Amsterdam.269～274,1986.
[15] E. M?kinen and M. Sieranta, Genetic algorithms for drawing bipartite graphs. Intern. J. Computer Math. 53, 157-166,1994.
[16] D.I. OSTRY, Some Three-Dimensional Graph Drawing Algorithms. Master's thesis, Department of Computer Science and Software Engineering, The University of Newcastle, Australia, 1996.
[17] Freese R.Automated Lattice Drawing.Second International Conference on Formal Concept Analysis, ICFCA, Sydney, Australia, 2004.
[18] Eloranta, T. and M?kinen, E., TimGA: a genetic algorithm for drawing undirected graphs. Divulg. Mat. 155-170.
[19] R. Cimikowski. Algorithms for the fixed linear crossing number problem. Disc.Appl. Math., 122:93–115, 2002.
[20] M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Alg.Disc. Meth., 4:312–316, 1983.
[21] Huang, J., Xu, J.-M, The bondage numbers of graphs with small crossing numbers, Discrete Mathematics. 307,1881-1897,2007.
[22] P. Eades, A. Symvonis and S. Whitesides, Three-dimensional orthogonal graph drawing algorithms, Discrete Appl. Math. 103, 55–87, 2000.
[23] Wille R, Wolf A. An approach to automated drawing of concept lattices [R] . Germary : Technical University of Darmstadt , 125 – 136,1997.
[24] 马骏,沈夏炯等.基于三维空间的概念格自动布局[J].计算机科学.2006 年第 33 卷(6)期: 244-246.
[25] 胡可云,陆玉昌,石纯一.概念格及其应用进展[J],清华大学学报.2000 年第 40 卷(9)期: 77-81.
[26] Michalewicz Z.Genetic Algorithms+Data Structures=Evolution Programs. Springer-Verlag,Berlin .1992.
[27] 沈夏炯,韩道军,刘宗田,马骏,概念格构造算法的改进,计算机工程与应用,2004 年 24期:100-103.
[28] Petko Valtchev, Rokia Missaoui, Robert Godin: Formal Concept Analysis for Knowledge Discovery and Data Mining: The New Challenges. Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004.
[29] Carpineto C, Romano G. Galois: an order-theoretic approach to conceptual clustering [A]. Utgoff P ed. Proceedings of ICML-93 [C]. Amherst: Elsevier. 33-40, 1993.
[30] Juan M. Cigarrán, Anselmo Pe?as, Julio Gonzalo, Felisa Verdejo: Automatic Selection of Noun Phrases as Document Descriptors in an FCA-Based Information Retrieval System. Third International Conference on Formal Concept Analysis, ICFCA 2005, Lens, France, February 49-63, 2005.
[31] Njiwoua P, Mephu Nguifo E. A parallel algorithm to build concept lattice. In proceedings of 4th Groningen Intl. Information Technical Conference for Students, 103-107, 1997
[32] 谢志鹏,刘宗田.概念格的快速渐进式构造算法.计算机学报,2002 年第 5 期:490-496.
[33] 胡可云,陆玉昌,石纯一,基于概念格的分类和关联规则的集成挖掘方法,软件学报,2000 年11(11)期:1478-1484.
[34] Rong Long Wang, Kozo Okazaki: An efficient parallel algorithm for the minimum crossing number problem. Neurocomputing 67: 411-416, 2005.
[35] Di Battista, G., Eades, P., Tamassia, R., and Tollis, I.G., Algorithms for drawing graphs: an annotated bibliography, Computational Geometry, 4:235–282, 1994.
[36] Eades, P., McKay, B.D., and Wormald, N., On an edge crossing problem, Proc. of the 9th Australian Computer Science Conference, 327–334, 1986.
[37] Yamaguchi, A. and Sugimoto, A., An approximation algorithm for the two-layered graph drawing problem, Proc. of the 6th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 1627, 81–91, 1999.
[38] Branke, J., Bucher, F., and Schmeck, H. Using genetic algorithms for drawing ndirected graphs. Tech. Rep. 347, D-76128 Karlsruhe, Germany, 1996.
[39] C.Kosak,J.Marks,and S.Shieber. A Parallel genetic algorithm for network-diagram layout. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 458-465,1991.
[40] Corey Kosak,Joe Marks,and Stuart Shieber.Automating the layout of network diagrams with specified visual organization. IEEE Transactions on Systems,Man,and Cybernetics, 24(3): 440-454,1994.
[41] A.O.Rodriguez and A.R.Suarez. Automatic graph drawing by genetic search. In ISPE/IEE/IFAC International Conference on CAD/CAM, Robotics and Factories of the Future,Pereira, Colombia, August 1995.
[42] Wille R. Restructuring lattice theory: an approachbased on hierarchies of concepts[A]. Rival I. Ordered sets[C]. Reidel,Dordrecht,Boston, 445- 470,1982.
[43] M. Huchard, H. Dicky and H. Leblanc. Galois lattice as a framework to specify building class hierarchies algorithms. Theoretical Informatics and Applications, 34:521–548, 2000.
[44] R. Godin and R. Missaoui. An incremental concept formation approach for learning from databases. Theoretical Computer Science, 133(2):387–419, 1994.
[45] F. Le Ber and A. Napoli. Design and comparison of lattices of topological relations based on galois lattice theory. In Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR-2002), Toulouse, pages 37–46, 2002.
[46] R. Wille. Lattices in data analysis: How to draw them with a computer.Algorithms and Order, pages 33–58, 1993.
[47] R. Wille. Concept lattices and conceptual knowledge systems. Computers & Mathematics With Applications, 23(6–9):493–515, 1992.
[48] Davey B. A., Priestley H. A., Introduction to Lattices and Order, Edition: Cambridge, Cambridge University Press, 1990.
[49] Wille R., Why can Concept Lattice Support Knowledge Discovery in DataBases, First Workshop on Formal Concept Analysis Advances for KDD, 2001.
[50] Maddouri M., A Formal Concept Analysis Tool for Automatic Structuring of Fuzzy Rule Bases, Invited paper to the IEEE International Conference On Systemics, Cybernetics and Informatics SCI-2001, Orlando-Florida, USA. ,uly 2001.
[51] Wille. R. (1997): Conceptual Graphs and Formal Concept Analysis. In: Lukose, D. et. al. (eds.): Conceptual Structures: Fulfilling Peirce’s Dream, Procs. of the ICCS’97. Springer, Berlin-New York 290-303, 1997.
[52] R. Wille. Restructuring lattice theory: an approach based on hierarchies of concepts. In: I.Rival (ed.): Ordered sets. Reidel, Dordrecht-Boston, 445-470.
[53] Ganter B(1984).Two basic algorithms in concept analysis, B4-Preprint No.831,TH Darmstadt.
[54] Stumme G,Taouil R,Bastide Y,Pasquier N,and Lakhal L(2000).Fast computation of concept lattices using data mining techniques.In Proceedings of 7th International Workshop on Knowledge Representation Meets Databases, KRDB, Berlin, Germany, 129-139, 2000.
[55] Chein M.Algorithme de recherche des sous-matrices premières d'unematrice. Bull.Math.Soc.Sci.Math.R.S.Roumanie,13:21–25, 1969.
[56] Bordat J P.Calcul pratique du treillis de Galois d'une correspondance. Math.Sci.Hum.,96:31–47, 1986.
[57] Lindig C.Fast concept analysis.In Stumme G(Eds.),Working with Conceptual Structures-Contributions to ICCS 2000,Shaker Verlag, Aachen,Germany, 2000.
[58] Carpineto C, and Romano G.Galois:an order-theoretic approach toconceptual clustering.In Proceedings of ICML-93, Amherst:Elsevier, 33-40, 1993.
[59] Van Der Merwe F,and Kourie D.AddAtom:an incremental algorithm for constructing concept-and concept sublattices.Technical report of the Department of Computer Science,University of Pretoria,South Africa, 2002.
[60] Van der Merwe F,Obiedkov S,and Kourie D.AddIntent:a new incremental algorithm for constructing concept lattices.In Eklund P(Eds.),Proceedings of 2nd International Conference on Formal Concept Analysis (ICFCA 2004),Sydney,372-358, 2004.
[61] Ho T B.Incremental conceptual clustering in the framework of Galois lattice.In Lu H,Motoda H and Liu H(Eds.),KDD:Techniques and Applications.World Scientific,49-64, 1997.
[62] Godin R, Mineau G, Missaoui R,St-Germain M & Faraj N. Applying concept formation methods to software reuse. International Journal of Knowledge Engineering and Software Engineering,5(1): 119-142, 1995.
[63] Lindig C. Concept-based component retrieval. In: Proc. IJCAI-95 Workshop on Formal Approaches to the Reuse of Plans, Proofs, and Programs, Montreal, August 1995.
[64] Godin R,Mili H,Mineau G .W, Missaoui R ,Arri A&Chau T-T. Design of class hierarchies based on concept (Galois) lattices. Theory and Application of Object Systems,4(2),117-134, 1998.
[65] Lindig C,Snelting G. Assessing modular structure of legacy code based on mathematical concept analysts.In: Proc. International Conference on Software Engineering(ICSE 97),Boston, USA,349-359, May 1997.
[66] R. Godin et al, Learning algorithms using Galois lattice Proceeding of the IEEE International Conference on Tools for AL. San Jose, GA, 22-29, 1991.
[67] Deursen A,and Kuipers T.Identifying objects using cluster and concept analysis.In Proceedings of the 21st International Conference on Software Engineering(ICSE'99), Los Angeles, California, 246-255, 1999.
[68] Snelting G. Reengineering of configurations based on mathematical concept analysis.Technical Report TR-95-02, Software Technology Department, Technical University of Braunschweig, 1995.
[69] Missaoui R, Godin R. Extracting exact and approximate rules from databases. In: AlagarV S, Bergler S, Dong F Q (Eds). Incompleteness and Uncertainty in information Systems.London: Springer-Verlag. 209-222 , 1994.
[70] 王志海,胡可云,胡学钢,刘宗田,张奠成,概念格上规则提取的一般算法与渐进式算法,计算机学报, 22 (1):66-70 ,1999.
[71] Keyun Hu, Yuchang Lu,Chunyi Shi.Incremental Discovering Association Rules: A Concept Lattice Approach, PAKDD'99, LNAI 1574, pp. 109-113, 1999.
[72] Godin R,Missaoui R,and April A(1993).Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods.International Journal of Man-Machine Studies,38:747-767.
[73] Carpineto C,and Romano G.Information retrieval through hybrid navigation of lattice representations. International Journal of Human-Computer Studies,45:553-578,1996.
[74] Richards D,and Compton P.Combining formal concept analysis and ripple down rules to support reuse,In Proceedings of Software Engineering Knowledge Engineering(SEKE'97),Springer Verlag, Skokie USA,177-184, 1997.
[75] Cole R, and Stumme G.CEM-a conceptual email manager.In Proceedings of the 8th International Conference on Conceptual Structures(ICCS'2000),Springer Verlag,438-452. 2000.
[76] Fernandez-Manjon B,Cigarran J,Navarro A,and Fernandez-Valmayor A(1998).Applying formal concept analysis to domain modeling in an intelligent help system.In Proceedings of Information Technology and Knowledge Systems, 5th IFIP World Computer Congress, Vienna- Budapest,1998.