论文部分内容阅读
本文主要对基于概念格模型的知识发现进行研究,并对经典概念格模型进行了扩展。研究工作的重点是使用概念格结构模型对关联规则、分类规则和函数依赖的发现问题进行求解。此外,本文还对概念格的快速生成算法进行了深入的研究,提出了一些高效的算法,文章的最后提出了几种概念格扩展模型,处理了数据中可能出现的缺值和结构化属性值域的问题。 具体研究工作如下: 1)在已有算法的基础上,详细地分析了概念格的渐进式和批处理的构造过程,对于渐进式构造和批处理构造,分别提出了一种较为高效的算法。本文的渐进式算法利用一种树状结构来对概念格节点进行索引,从而有效地提高了概念格的构造速度。而本文中批生成算法通过提出的扩展等价类这一概念来有效地减少了在每个节点处计算其子节点的冗余计算量,从而达到提高算法效率的目的。实验结果表明,本文渐进式算法的时间性能要明显优于著名的Godin算法。 2)在函数取值不变性(或近似不变性)的基础上,提出了概念节点的内涵缩减(或近似内涵缩减)和内涵核(或近似内涵核)的概念,详细地研究了它们的性质,证明了它们的计算问题都可以等价地转化为族集最小覆盖集的计算问题。而对于族集最小覆盖集的计算问题,本文则提出了若干个定理刻画了其计算方法的原理并予以正确性证明,并精心设计了相应的算法。 3)对于关联规则发现这一数据挖掘的核心任务,提出了一个基于概念格的关联规则发现框架。首先,针对关联规则发现的需求,我们对概念格节点的结构进行了相应的简化修改,并给出了相应的构造算法;然后基于内涵缩减,我们给出了从格上提取关联规则的算法伪码,两个性质被用来去除冗余的关联规则;文中还分析了基于概念格的关联规则发现与传统的发现算法相比所具有一系列的优点。然而,事务数据库有时并不只是事务的简单集合,不同事物之间可能存在某种关系(如时序关系)。为了对事务数据库中不同事务之间的时序关系进行处理,我们定义了间隔基准概念格作为对经典概念格的一种扩展。从间隔基准概念格上可以提取出时序关联规则,这对于预测是非常有用的。 4)为了借助于概念格模型来对未知的新对象进行分类,我们研制了两个分类系统——LACS系统和LACS-2系统。在LACS系统中,针对分类系统的特点,我们提出两 合肥工业大学博士学位论文种重要而有效地剪枝策略来限制格构造过程中的节点生成,从而大大减少了所需生成的格节点数目.在MONK数据集上的实验结果表明,LACS系统的分类精度要明显优于其它一些著名的分类系统(例如 ID3、C4.5和 CNZ).在 LACS系统的基础上,我们还研制了LACS-2系统,它为每个决策类建立一个概念格,然后使用所有生成的概念格来共同对新对象进行分类.LACS-2系统中所使用的分类策略是相当灵活的,它可以解决LACS系统中所不能解决的问题. 5)以无序偶作为基本元素,我们给出了区分系统和不可区分背景的形式化定义.区分系统的缩减集计算统一了粗糙集合理论中信息系统的缩减集的计算问题和决策表的相对缩减集的计算问题.而不可区分背景所对应的不可区分格则可以用于信息系统中任意属性子集的缩减集计算,于是它可以用作一个框架结构来发现关系数据中所成立的函数依赖关系. 6)提出了两种扩展的概念格模型.第一种扩展模型可以用于对形式背景中所出现的缺值现象进行处理,这在本文中被称为粗糙形式概念格.我们还研究了从粗糙形式概念格上提取规则的算法.当对象通过属性一值表示方法进行描述时,针对属性值域被结构化为完全格或偏序集的情况,第二种扩展模型可以对其进行处理.文章的最后还给出了这些扩展模型在序论和格论中的理论基础.