有限内存下概念格二元关系消减维护算法研究

作     者：王春月 

作者单位：郑州大学 

学位级别：硕士

导师姓名：王黎明;张卓

授予年度：2017年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：有限内存空间 概念格 二元关系消减 外存算法 概念簇 最近最少使用调度策略 

摘      要：概念格(也叫形式概念分析)作为一种概念聚类的方法,已被证明有利于机器学习、信息检索和知识发现等。在实际应用中,随着时间的推移生成概念格的形式背景会产生大量冗余的对象、属性或是对象与属性之间的二元关系,这导致概念格中无效概念增多,而去除这些无效概念,有利于降低概念格的规模,从而有助于更快更准确地获取知识。现阶段大多数研究学者关注于对象或属性的渐减式维护工作,对于二元关系粒度的渐减式维护工作的研究却很少。为降低概念格的规模,提高概念格的构造效率,本文提出了基于二元关系消减的概念格维护方法。与传统的基于新形式背景下重新构造概念格不同,该方法通过调整原始概念格而得到新概念格,故节省了大量的构格时间。文中首先分析了原始概念格和新概念格中概念节点之间的对应关系以及概念节点之间边的变化规律,在此理论基础上提出了自底向上广度优先的概念格二元关系消减算法,该算法可以处理形式背景中任意位置二元关系消减的情况。实验表明在一定程度上与传统算法相比能明显提高概念格的构造效率。以上概念格维护算法基于无限大内存这一假设为前提条件运行的。然而在有限内存下,当概念格的规模太大而无法全部载入内存时,使得以上基于二元关系消减的概念格维护算法不再适用。因此为解决超出内存容量的概念格的二元关系消减的维护问题,本文进一步提出了一种有限内存空间下基于外存的概念格维护算法。该算法以概念簇为基本单位划分概念格,同时利用最近最少使用调度策略释放内存中无用的概念节点,并从外存中调入所需的概念块,从而有效地降低了内存消耗,解决了内存不足的现象,为概念格的具体应用提供保障。文中从理论与实验结果两个方面表明,在限定的内存资源条件下,该方法以较小的内存消耗和时间代价,实现了概念格的有效维护。