基本信息
- 项目名称：
- 基于缺值形式背景的概念格构造算法研究
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 概念格是一个有效的形式化工具，针对传统概念格处理不完备信息的局限性，给出了一个能够处理形式背景缺值现象的概念格扩展模型—近似概念格。并在此基础上提出一个改进的概念格增量构造算法，算法通过引入哈希技术和最近父节点的增量计算方法，加速定位生成元和更新边这两个关键过程，有效的提高建格效率，采用随机数据集设计了实验，充分验证了算法的有效性，尤其对数据规模和发生关系概率较大的数据集有更好的效果。
- 详细介绍：
- 概念格是一个有效的形式化工具，针对传统概念格处理不完备信息的局限性，给出了一个能够处理形式背景缺值现象的概念格扩展模型—近似概念格。并在此基础上提出一个改进的概念格增量构造算法，算法通过引入哈希技术和最近父节点的增量计算方法，加速定位生成元和更新边这两个关键过程，有效的提高建格效率，采用随机数据集设计了实验，充分验证了算法的有效性，尤其对数据规模和发生关系概率较大的数据集有更好的效果。
作品图片
作品专业信息
撰写目的和基本思路
- 针对经典概念格不能处理不完备信息的问题，借鉴偏大近似的思想扩展概念格，构建了近似概念格，使其能够描述不完备信息，拓展了概念格理论。并在此基础上，给出了改进的概念格增量构造算法。通过分析影响概念格构造过程中的关键因素，算法从加速定位生成元和更新边这两个关键过程改进Godin算法，得到高效的概念增量格构造算法。
科学性、先进性及独特之处
- 传统的概念格不能直接描述不完备信息，并且缺乏适合大型数据库的建格算法，作品首先扩展了概念格模型，使其能够处理不完备信息，并且将哈希表和最近父节点的增量计算方法引入建格过程，提高的建格效率，拓展了概念格的应用范围。
应用价值和现实意义
- 作品研究了缺值形式背景下的概念格构造问题，改善了概念格在实际应用中对缺值信息的表示和构建效率低下的问题，为概念格研究提供理论和实践依据。
学术论文摘要
- 概念格是一个有效的形式化工具，针对传统概念格处理不完备信息的局限性，给出了一个能够处理形式背景缺值现象的概念格扩展模型—近似概念格。并在此基础上提出一个改进的概念格增量构造算法，算法通过引入哈希技术和最近父节点的增量计算方法，加速定位生成元和更新边这两个关键过程，有效的提高建格效率，采用随机数据集设计了实验，充分验证了算法的有效性，尤其对数据规模和发生关系概率较大的数据集有更好的效果。
获奖情况
- 无
鉴定结果
- 已通过鉴定
参考文献
- [1] Wille R. Restructuring lattice theory: An approach based on hierarchies of concepts[C]//Rival I. Orderd Sets. Dordrecht,Boston,1982:445-470 [2] Yadav B S. A Conceptual Model for User-centered Quality Information Retrievalon the World Wide Web[J].Journal of Intelligent Information Systems, 2010, 35(1): 91-121 [3] Tonella P. Formal Concept Analysis in Software Engineering[C].In: Proceedings of the 26th International Conference on Software Engineering. Washington DC: IEEE Computer Society, 2004:743-744 [4] Stumme G. Efficient Data Mining Based on Formal Concept Analysis[C]. In:Proceedings of the 13th International Conference on Database and Expert Systems Applications. London: Springer-Ver-lag, 2002: 534-546 [5] 强宇,刘宗田,吴强等.模糊概念格在知识发现中的应用研究[J].计算机科学,2005,32(1):182-184 [6] Formica A. Ontology-based Concept Similarity in Formal Concept Analysis[J]. Information Sciences, 2006, 176(18): 2624-2641
同类课题研究水平概述
- 概念格也称为形式概念分析，基本思想是根据二元关系来表达领域中的形式背景，从中提取概念层次结构，即概念格，本质上体现了内涵(属性集)和外延(拥有该属性集的实体集)的统一。作为数据分析和知识处理的形式化工具，概念格已被广泛用于信息检索、软件工程、知识发现、本体研究等领域。经典的概念格基于完备的形式背景，而现实生活中，信息的非完备(对象的属性值缺损)现象是广泛存在的。一旦出现缺值，传统的处理方法有删除法、补全法和扩展属性法。然而，删除法和补全法容易造成知识的缺失或增加，扩展属性法虽然能够保留原有形式背景的信息，但同时增加了形式背景的规模。因此，研究基于不完备形式背景的概念格模型具有重要的意义。概念格构造的过程实际上是概念聚类的过程，由于很多情况下需要处理大量的数据，因此，概念格构造算法始终是形式概念分析在其应用过程中首先要解决的一个基础性问题。概念格的构造算法主要分为两类：批处理算法和渐进式算法。批处理算法的思想是首先生成所有概念，然后根据它们之间的直接前驱-后继关系生成边，完成概念格的构造，如Bordat算法、Chein算法、Ganter算法等；渐进式算法是将当前要插入的对象与格中所有的概念求交，根据交的不同结果进行不同的操作。典型的渐进式构造算法有Godin算法等。批处理算法对形式背景稠密的情况下性能较好，但缺乏灵活性，增量算法能够有效的在原概念格基础上进行动态更新和维护。影响增量算法效率的关键是生成元的定位和新节点边的更新。针对该问题一些学者提出了改进的增量算法。沈夏炯等提出利用数据库内部技术来实现确定生成元的查找判断过程。Capineto提出的算法通过找到新节点的最小上界和最大下界，删除它们的边，并将其连接到新概念。这些研究都不同程度上提高了建格效率。
