一种基于偏序集直积的增量式概念格构造算法

目前,概念格的构造算法可分为批处理式和增量式两类.已有的增量式算法只适用于单个对象的逐个插入更新的情况,然而,在大多数的数据库中,更新操作往往是同时插入多个对象.为了适应这种情况,基于偏序集的直积运算,提出了一种新的增量式概念格构造算法,这种算法可以一次性地加入一个对象集合,而且在生成概念的同时,能够构造出概念格的Hasse图,从而完全解决了上述问题.最后,用一个实例检验了算法的正确性.     

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

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

一种渐进式概念格生成算法的优化

形式概念分析是德国的数学家Wille于1982年提出的,其核心数据结构概念格接近于自然语言,易于理解,在数据挖掘领域有巨大的潜在应用价值。构建概念格在概念格应用中有举足轻重的地位。建格算法分为两种:批处理算法和渐进式算法。着重研究渐进式算法,并介绍一种渐进式算法的优化算法,这种优化算法在一定程度上提高了原算法的运行速度。     

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

提出了一种新的基于属性的概念格快速渐进式构造算法，通过不断地渐增属性来构造概念格。以往的渐进式算法嘟是基于对象的，当数据库属性数目发生变化时，需要重新构造概念格。该算法不但解决了这个问题，而且提供了一种渐进式构造概念格的新方法和思路。给出了该算法的实例，用来说明形式背景在新添加属性后概念格的更新过程。实例与实验表明基于属性的概念格快速渐进式构造算法是快捷有效的。     

概念格构造算法的改进

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

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

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

A Lattice Conceptual Clustering System and Its Application to Browsing Retrieval

The theory of concept (or Galois) lattices provides a simple and formal approach to conceptual clustering. In this paper we present GALOIS, a system that automates and applies this theory. The algorithm utilized by GALOIS to build a concept lattice is incremental and efficient, each update being done in time at most quadratic in the number of objects in the lattice. Also, the algorithm may incorporate background information into the lattice, and through clustering, extend the scope of the theory. The application we present is concerned with information retrieval via browsing, for which we argue that concept lattices may represent major support structures. We describe a prototype user interface for browsing through the concept lattice of a document-term relation, possibly enriched with a thesaurus of terms. An experimental evaluation of the system performed on a medium-sized bibliographic database shows good retrieval performance and a significant improvement after the introduction of background knowledge.     

基于Iceberg概念格的最大频繁项集挖掘

最大频繁项集挖掘算法存在扫描数据集次数多和候选集规模过大等局限。基于Iceberg概念格模型,提出一种在Iceberg概念格上挖掘最大频繁项集的算法ICMFIA。该算法通过一次扫描数据集构建Iceberg概念格,利用Iceberg概念格中频繁概念之间良好的覆盖关系能快速计算出最大频繁项集所对应的最大频繁概念,所有最大频繁概念的内涵就是所求的最大频繁项集的集合。实验结果表明,该算法具有扫描数据集次数少和挖掘效率高的优点。     

基于扩展概念格的Web关系挖掘

针对Web服务因缺少有效的组织和管理机制而产生的应用瓶颈问题,引入基于概念覆盖度函数的扩展概念格,通过构建基于输入和输出参数的Web服务集的扩展概念格模型,给出了Web服务间等价、替代和流关系的离线挖掘算法以及增量和减量的在线更新算法.在真实Web服务集上的测试结果表明,扩展概念格模型是Web服务集的一种有效的组织形式,可用于Web服务关系的自动挖掘和维护,从而为Web服务的选择、优化和组合提供智能支持.     

采用二叉树结构生成概念格的算法

概念格是数据分析的一种有力工具。而二叉树在数据结构中具有简单的存储结构。给出了一类具有特殊结构的概念格,针对这种类型的概念格,采用二叉树的结构对概念格的节点进行重新的组织,研究了基于添加对象的渐进式生成概念格的算法。利用这种二叉树的结构,在某些情况下可以减少判断不变概念或更新概念的范围,同时,结合实例说明了这种算法的有效性。     

A lattice-free concept lattice update algorithm

Upon a change of input data, one usually wants an update of output computed from the data rather than recomputing the whole output over again. In Formal Concept Analysis, update of concept lattice of input data when introducing new objects to the data can be done by any of the so-called incremental algorithms for computing concept lattice. The algorithms use and update the lattice while introducing new objects to input data one by one. The present concept lattice of input data without the new objects is thus required by the computation. However, the lattice can be large and may not fit into memory. In this paper, we propose an efficient algorithm for updating the lattice from the present and new objects only, not requiring the possibly large concept lattice of present objects. The algorithm results as a modification of the Close-by-One algorithm for computing the set of all formal concepts, or its modifications like Fast Close-by-One, Parallel Close-by-One or Parallel Fast Close-by-One, to compute new and modified formal concepts and the changes of the lattice order relation only. The algorithm can be used not only for updating the lattice when new objects are introduced but also when some existing objects are removed from the input data or attributes of the objects are changed. We describe the algorithm, discuss efficiency issues and present an experimental evaluation of its performance and a comparison with the AddIntent incremental algorithm for computing concept lattice.     

基于同类概念的概念格横向合并算法

提出了同类概念的观点，在格的合并算法中通过利用同域概念格之间的同类概念和概念的父—子关系实现对其所有子节点的快速更新，以提高概念格横向合并算法的时间效率。并进一步论证了把节点数量较少的格插入到节点多的格中比反着做更省时间。实验表明，该算法和相关文献中的同域概念格横向合并算法相比，其时间性能有明显改善。     

基于同义概念的概念格纵向合并算法

在FCA中,如何提高概念格构造算法的效率一直是研究的重点之一。将形式背景进行分解后造格是解决这一问题的有效途径,其中概念格的合并算法是关键。提出同义概念的观点,在格的合并算法中引入了概念格的线性索引结构,通过寻找同域概念格之间的同义概念,根据父概念-子概念的关系实现对其所有父节点的快速更新。实验表明,该算法和文献中的同域概念格纵向合并算法相比,其时间性能有明显改善。     

基于量化规则格的关联规则渐进更新*

提出一种基于量化规则格的规则更新算法,重点讨论了在新增格节点的过程中规则更新的思想,实现在格的渐增生成过程中,相应的关联规则也得到渐进更新.最后给出简单实例说明规则更新算法的正确性.     

概念格对象渐减维护与关联规则更新

研究概念格对象渐减维护与关联规则更新符合动态环境下概念格应用的需求。提出了对象渐减时概念的更新原则和概念间关系调整方法,并在其基础上设计了概念格对象渐减维护算法;采用了内涵缩减来获得概念蕴含的关联规则,从父子概念内涵差集的变化中发现了对象渐减时的内涵缩减更新规律;获得了对象渐减时的关联规则更新方法。     

基于属性的相对约简格快速渐进式构造算法

相对约简格作为简化的概念格,在数据挖掘和知识发现等领域具有广泛的应用.相对约简格的构造在其应用过程中是一个主要问题.本文提出了采用树结构对相对约简格节点进行组织,研究了基于属性的相对约简格渐进式构造算法.相对约简格节点的树结构组织可以约束更新格节点、产生子格节点及新生格节点的子结点的搜索范围,从而可以有效地减少算法的执行时间.该算法不仅为相对约简格的构造提供了一种方法,还解决了在已构造好相对约简格的前提下,增加属性所带来的更新问题.在随机生成的数据集上进行的实验测试表明,本算法的时间性能更优越.     

序列模糊概念格模型及其渐进式构造

传统的序列模式挖掘主要是挖掘满足最小支持度的频繁序列,没有考虑序列在实际中的重要度。为了能够有效地挖掘重要的序列模式,提出了一种序列模糊概念格模型,对所有序列的项目引入了重要度权值,定义了序列的重要度及可以动态调整最小支持度minsup的自适应系数;扩展了模糊形式背景,使其能够方便地表示序列,定义了概念的Galois闭包连接、序列模糊概念及序列模糊格结构,并给出了序列模糊概念格的渐进式构造算法 ScqFuzCL。实验表明,序列模糊概念格模型可以方便有效地组织自适应序列模式,在时间与空间上都具有良好的性能,并为进一步挖掘自适应序列模式提供了理论支持。     

同义概念格的纵向合并

由于概念格自身的完备性,构造效率一直是制约其进一步应用的瓶颈。本文从概念格的构造入手,提出了同义概念格的观点,并利用其性质进一步提出了一种纵向合并同义概念格的算（VUSCL算法）。实验表明,随着节点数的增加,该算法与文献[8]中的纵向合并算法相比,其时间性能有明显改善。     

一种概念格渐进式构造算法

概念格是形式概念分析理论的一种数据结构,它以独特优势在许多领域获得了广泛应用,如信息检索、软件工程、知识发现等,而概念格的构造效率问题是其应用的前提。相对传统算法需要遍历原始概念格中所有结点才能确定新概念的产生子的不足,减少了概念格更新过程中需遍历的概念结点数并缩小了新概念的产生子的父概念的搜索范围,提高和改善了效率。     

概念格的渐进式维护算法

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