【作者】 陈明；

【导师】 马骏；

【作者基本信息】 河南大学 ， 应用数学， 2008， 硕士

【摘要】 形式概念分析作为一种用于数据组织和数据分析的形式化工具,在理论研究和实际应用上都具有重要意义,它己经在多个领域获得了成功的应用。概念格作为形式概念分析中核心的数据结构,本质上描述了对象和特征之间的联系,表明了概念之间的泛化与例化关系,其相应的布局图(Hasse图)则实现了对数据的可视化。概念格的可视化给人们提供了直观的分析与观察知识单元内在关系的方法,概念格的构造和良好的布局是形式概念分析应用的前提。在概念格的构造和布局过程中,利用现有的方法布局出的概念格图形,在层与层之间产生了过多的边交叉数,使整个格图看起来杂乱无章,用户很难从中找到有用的信息,直接影响了概念格图形的可读性。因此,减少格图中的边交叉数,将概念格的可视化表示形式清晰、美观地展现出来显得尤为重要。本文在目前已有的概念格构造算法和模型的基础上,结合遗传算法对概念格图形的布局进行了研究,提出了基于遗传算法的概念格结构布局优化策略,通过一个概念格分层图模型,介绍了求解边交叉数以及最优边交叉数问题的方法。　　本文的主要成果包括:1、从概念格分层图的角度提出了“边的跨度”和“规则概念格图形”的概念。并给出了从“非规则概念格图形”到“规则概念格图形”的转换方法。2、设计了概念格的矩阵表示,通过此方法可以用二进制字符串表示出编码后的概念格。3、将遗传算法引入概念格分层图布局中边交叉数优化问题的求解,提出了基于遗传算法的概念格图形布局优化算法。并对实验结果进行了分析,然后和传统的概念格图形分层布局算法进行了比较。更多还原

【Abstract】 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.更多还原