近似概念格及其增量构造算法研究*

针对传统概念格处理不完备信息的局限,给出了处理形式背景有缺值现象的概念格扩展模型———近似概念格,在此基础上提出改进的概念格增量构造算法。该算法引入哈希技术和最近父节点的增量计算方法,从加速定位生成元和更新边这两个关键过程改进Godin算法。采用随机数据集设计实验,实验表明,改进的算法可有效提高对形式背景有缺值现象概念格的建格效率,尤其是对数据规模和发生关系概率较大的数据集,算法的高效性更明显。     

一种构造概念格的改进算法

Chein算法是一种批处理概念格构造算法,它构造过程中层次清楚,易于生成Hasse图,但是造格的过程中生成大量冗余的概念,降低了构造概念格的效率.提出一种对Chein算法的改进算法,保留了原算法层次清晰的优点,同时避免了冗余概念的产生,从而降低了构造概念格的时间复杂度.     

一种基于概念矩阵的概念格生成算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习和数据挖掘等领域有着广泛的应用.构造概念格十分重要,针对此引入了概念矩阵思想,提出了基于概念矩阵的概念格生成算法CMCG(Concept-Matrix Based Concepts Generation).该算法从格的顶端节点开始构造,基于概念矩阵,利用属性的秩为每个节点生成它的所有子节点,完成子节点到父节点之间的链接,并生成哈斯图.给出了这种算法的理论依据.最后提供了这一算法的伪码,并通过实验证明了CMCG算法的时间性能优于Lattice算法.     

粗糙概念格构造的算法

针对形式背景,利用概念外延与内涵之间特殊的关系,结合粗糙集上下近似概念,提出一种粗糙概念格构造算法,属性约简后运用粗糙度进行挖掘,获取可靠性知识。在构造过程中,对节点属性进行判断,有效地降低算法的时间复杂度。实际案例分析结果表明,通过属性约简与粗糙度的结合,该算法可以有效地挖掘获取可靠性知识,为数据分析挖掘知识提供了一种可行的思路和方法。     

树状结构组织的属性优先的概念格渐进式算法

通过对概念格渐进式构造过程的分析,采用树结构对概念格节点进行组织,研究了利用这种树状组织的渐进式生成属性优先的概念格的构造算法。并结合实例说明了概念格的树结构组织在属性优先的渐进式生成概念格时,能有效地缩小产生子格节点的搜索范围和新增格节点的父节点和子节点的搜索范围,从而能快速生成概念格。     

基于约束的模糊概念格构造算法

一般的模糊概念格在构造过程中没有考虑用户的需求,用户对模糊概念格节点中一些属性集形成的内涵并不感兴趣。为了增强模糊概念格的针对性,降低模糊概念格构造的时空复杂性,构造满足用户需求的模糊概念格,首先将用户感兴趣的背景知识定义为约束条件,根据用户关心的属性间关系,将约束条件分为3类:单约束、与约束及或约束,并采用谓词公式表示,进而提出了基于约束的模糊概念格(Constrained Fuzzy Concept Lattice,CFCL)构造算法。该算法自底向上构造模糊概念格,利用模糊概念格父子节点内涵的单调关系,采用剪枝技术来减少构造过程中判断模糊概念是否满足约束的次数,提高了模糊概念格的构造效率。实验结果表明,该算法能够有效地减少模糊概念格的存储空间和构格时间。     

基于属性消减的模糊概念格渐进式构造算法

当前模糊概念格的直接构造具有指数时间复杂度,且随着真值集合L大小的增加,模糊概念格的规模变得越来越庞大。为此提出了FMBUAD算法,它能够在原有模糊概念格的基础上消去多个消减属性(冗余或者无效属性)得到新的模糊概念格,且不考虑真值集合L的大小。基于模糊概念格的基础理论证明了FMBUAD算法的正确性。该算法首先将所有概念节点内涵中的消减属性隶属度移除;然后找出模糊概念格中所有的删除节点;最后集中处理删除节点父子节点之间的偏序关系。理论证明和实验结果表明:FMBUAD算法构造L-模糊概念格具有较好的时间性能。     

基于权值最大圈的概念格构造算法

概念格作为一种有效的知识发现与数据处理的工具,在许多领域得到了广泛应用。寻找形式背景下的所有概念是概念格理论研究的一个基本问题。对于一个给定的形式背景,在属性拓扑图的基础上,结合图论的思想,给出了一种概念格的构造算法。算法过程如下:首先,构造弱化的属性拓扑图;其次,通过寻找弱化的属性拓扑图中的每个权值最大圈方法来生成概念,形式背景的所有概念被生成;最后,构造出概念格。通过分析说明此算法复杂度比以往的一些算法复杂度低。此外,用一个实例验证了这一算法的有效性与正确性。为知识获取提供了有益的思路与方法。     

基于属性的概念格快速渐进式构造算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用,概念格的构造在其应用过程中是一个主要问题.提出了采用树结构对概念格节点进行组织,研究了基于属性的概念格渐进式构造算法.概念格节点的树结构组织可以约束更新格节点和产生子格节点的搜索范围,从而可以有效地减少算法的执行时间.在随机生成的数据集上进行的实验测试表明,本算法的时间性能更优越.     

概念格的属性渐减原理与算法研究

渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖ L ‖·G ‖·‖M ‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.     

概念格的快速渐进式构造算法

概念格作为形式概念分析理论中的核心数据结构，已经在知识工程和软件工程等领域得到了广泛的应用。概念格的快速构造在其应用过程中具有重要的意义，研究人员已经提出了一系列构造概念格的算法，其中渐进式算法是很有前途的一类。该文通过对概念格渐进式构造过程的分析，识别出要解决的基本问题，提出了采用树结构对概念格节点进行组织，研究了基于这种树状组织的概念格快速渐进式算法，并给出了算法的伪码。概念格节点的树结构组织有利于识别出格节点的类型以及约束新生格节点的父节点和子节点的搜索范围，从而可以有效地减少算法的执行时间。实验结果表明，基于这种树状索引的渐进式构造算法的时间性能要明确优于著名的Godin算法。     

基于属性的概念格渐进式生成算法

提出了一种新的基于属性的渐进式概念格生成算法 ,通过不断地渐增属性来构造概念格 .该算法不仅为概念格的构造提供了一种新的方法 ,还解决了在已构造好概念格的前提下 ,增加属性所带来的概念格更新问题 .给出了算法的实现方法 ,并结合实例说明了概念格的更新过程 .试验表明 ,在通常情况下 ,基于属性的渐进式概念格生成算法的性能往往更优越     

一种模糊概念格构造算法研究

基于有限L_背景的模糊格在扩展和时空复杂度上有局限。该文定义了广义的模糊概念格和其上的截运算以简化格构造,提出了一种模糊格构造算法。在概念格结点级上定义了两个模糊参数α和δ粎,以避免提取因高偏差导致的无效规则。给出一个实例,说明了从模糊概念格提取不确定规则、计算规则支持度、置信度的原则、方法。实现了构造算法与Godin算法的对比实验,结果表明本算法在时空性能上要优于Godin算法。     

一种频繁加权概念格的批处理构造算法

概念格是知识表示和数据分析的一种有效工具,加权概念格是一种刻画内涵重要性的概念格结构。文中通过引入虚结点的概念,提出一种频繁加权概念格的批处理构造算法。该算法首先通过引入虚结点概念,证明频繁加权概念格是一个完全格,从而纠正先前张继福提出的频繁加权概念格结构中某些频繁加权概念结点不存在上下确界的缺陷。其次,采用自底向上的方法来生成频繁结点和虚结点,以及对应的边关系,从而降低频繁加权概念格构造的时空复杂性,提高批处理构造效率。最后在恒星光谱数据上的实验验证算法的正确性和有效性。     

基于二元关系消减的概念格维护算法

针对有限空间下如何快速维护概念格的问题,提出一种消减形式背景中冗余二元关系的概念格维护算法。传统的算法删除冗余关系后需要重新构造概念格,这种方式较为费时。而所提算法能够在原始概念格的基础上直接调整得到新概念格的方法,可以处理任意位置的二元关系消减的情况。它采用自底向上广度优先方式遍历格节点,首先根据当前节点是否同时包含冗余关系对象和冗余关系属性,将当前节点分为受影响的节点和不变节点;然后根据当前节点与父子节点的外延和内涵的关系,再将受影响的节点细分为4类,即减对象节点、减属性节点、分割节点、删除节点;最后根据父子节点的类型更新边。实验结果表明,在一定程度上与传统算法相比,所提算法能够获得更好的时间性能。     

基于改进概念格的无冗余关联规则提取

在介绍概念格相关理论的基础上,提出改进概念格构造算法——Godin算法,在构造概念格的同时增加索引链表,有利于概念格的剪枝。把量化概念格、剪枝概念格与改进算法相结合,给出基于该改进算法的无冗余关联规则提取算法,并证明改进算法和无冗余规则提取算法的正确性和有效性。     

概念格的渐进式维护算法

由二元关系导出的概念格是一种非常有用的形式化工具,也很适合于发现数据中潜在的概念。概念格的算法一直是数据挖掘领域研究的热点。本文根据需要对概念格的结构进行一定的修改,采用一个带头、尾指针的链表作为整个算法的数据结构,提出概念格的渐进式维护算法,该算法中包含两个算法,即渐进式构造算法和渐进式删除算法。最后,通过将该算法和其他算法进行比较,得出较好的时间和空间效率。     

模糊概念因子格的子格构造算法

为了完善因子格的构造,提出了一种基于模糊伽罗瓦联系的模糊概念因子格的子格算法(Factor Lattice Algorithm算法)。该算法依据已给出的模糊概念因子格的上下界限,采用批处理的方式自顶向下根据模糊下邻生成因子,计算出模糊概念节点的直接下邻集合,将模糊概念格进行局部构建,逐步完成局部完备模糊概念因子格的构造得到完备的模糊概念格的子格。并从理论分析和实验结果证明此算法构造得到的模糊概念因子格具备了完备性。     

概念格构造算法的改进

概念格作为形式概念分析理论中的核心数据结构,已经在知识工程和软件工程等领域得到了广泛的应用。概念格的构造在其应用过程中具有重要的意义,研究人员已经提出了一系列构造概念格的算法,主要是批处理和渐进式算法,其中渐进式算法是很有前途的一类。文章通过对概念格渐进式构造过程的分析,对Godin算法做了部分改进,给出了算法的伪码并加以实现,最后,根据运行数据进行了算法的性能分析。     

基于矩阵秩的概念格生成算法

形式概念分析的核心是概念格,它在本质上描述了对象和属性之间的联系,表明了概念之间的泛化和例化关系。利用矩阵行秩的概念及概念格上的二元运算提出了一种基于矩阵秩的概念格生成算法,实例表明该算法行之有效。