学位论文 > 优秀研究生学位论文题录展示

概念格Hasse图布局算法研究

作　者: 杨淑玲
导　师: 祁建军
学　校: 西安电子科技大学
专　业: 计算机软件与理论
关键词: 概念格 Hasse图布局算法附加线图
分类号: TP18
类　型: 硕士论文
年　份: 2012年
下　载: 54次
引　用: 0次
阅　读: 论文下载

内容摘要

概念格理论又称为形式概念分析，用于概念的发现、排序和显示。它作为一种用于数据组织和数据分析的形式化工具，在理论研究和实际应用上都具有重要意义，已经在多个领域获得了成功的应用。概念格作为形式概念分析中核心的数据结构，本质上描述了对象和特征之间的联系，表明了概念之间的泛化和特化关系，其Hasse图则实现了对数据的可视化。而Hasse图中概念结点的布局算法对概念格的可读性、图显示的时间效率有着不可忽略的影响。本文在研究了概念格Hasse图的经典布局算法后，重点分析了使用回溯查找法的附加线图布局算法，指出其中效率低下的原因，提出了直接赋值附加线图布局算法DAAL。直接赋值附加线图法摒弃了传统的回溯查找法，采用直接赋值，间接使用概念矢量和的方法，有效地减少了给属性集寻求矢量集的过程，提高了概念格布局的效率；而其中使用的相关概念相邻的思想也使概念格的可读性得到提高。本文同时提出了一种新的概念格布局优化策略：基于线性交换的概念格Hasse图二次布局。在移动概念结点位置时，只有相邻两层的边交换情况会受到直接影响，算法根据这一点对分层结构的概念格进行隔层取概念，获得一层的概念后，线性交换概念结点位置，并计算交换前后相邻两层边的交叉数，根据边交叉数的变化来决定结点的位置。该二次布局算法使得概念格Hasse图能够处于边交叉数较少的状态下，使其可读性得到了较大提升。通过在相同数据下进行的布局算法与优化策略的实验，可以证明本文所提出的直接赋值附加线图布局算法相比于传统的附加线图布局算法在时间与“美观”性方面都有很大改进；基于线性交换的Hasse图二次布局算法对于图的可读性起到了积极的作用。本文的主要工作包括以下四个方面：1．提出了直接赋值附加线图概念格布局算法。2．提出了一种基于线性对换的概念格二次布局算法。3．通过实验对概念格布局算法进行了分析与比较，验证了本文所提出算法的有效性。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-11
  1.1 研究背景  7
  1.2 研究现状  7-8
  1.3 研究目标和意义  8
  1.4 论文的结构与组织  8-11
第二章概念格理论基础  11-17
  2.1 概念格概述  11
  2.2 概念格基础理论  11-13
  2.3 概念格研究的主要内容  13-14
  2.4 概念格应用  14-17
第三章概念格 Hasse 图布局算法  17-25
  3.1 概念格 Hasse 图布局概述  17-18
  3.2 经典概念格 Hasse 图布局算法  18-21
    3.2.1 有向力定位布局算法  18-19
    3.2.2 分层布局算法  19-20
    3.2.3 附加线图法  20
    3.2.4 混合法  20-21
  3.3 回溯查找法  21-23
    3.3.1 回溯法  21-23
  3.4 本章小结  23-25
第四章改进的 Hasse 图布局算法  25-41
  4.1 直接赋值附加线图法（DAAL）  25-33
    4.1.1 DAAL 相关定义  25-26
    4.1.2 DAAL 思想  26-28
    4.1.3 DAAL 实现  28-32
    4.1.4 DAAL 示例  32-33
  4.2 基于线性交换的 Hasse 图二次布局  33-40
    4.2.1 二次布局相关定义  34
    4.2.2 二次布局算法思想  34-36
    4.2.3 二次布局算法实现  36-38
    4.2.4 二次布局算法示例  38-40
  4.3 本章小结  40-41
第五章实验结果与分析  41-53
  5.1 实验平台及实验步骤  41-43
  5.2 时间性能方面的实验  43-47
    5.2.1 实验数据  43-47
    5.2.2 实验结论  47
  5.3 图美观性方面的实验  47-51
    5.3.1 实验数据  47-51
    5.3.2 实验结论  51
  5.4 本章小结  51-53
第六章结论与展望  53-55
  6.1 本文结论  53
  6.2 展望  53-55
致谢  55-57
参考文献  57-61
读研期间研究成果  61-62

概念格Hasse图布局算法研究

内容摘要

全文目录

相似论文