基于三元互关联后继树的Web日志挖掘

针对二元的互关联后继树模型进行改进,构造三元互关联后继树,并结合Web日志的特点,构造Web事务集的互关联后继树和增量更新模型,设计基于三元互关联后继树的频繁路径挖掘算法,挖掘Web日志中的频繁路径。通过实验证明了基于三元互关联后继树和改进后的模型的出色插入查询性能。     

约束概念格及其构造方法

概念格是一种有效的数据分析和知识提取的形式化工具．然而，随着要处理的数据量的剧增，基于原始形式背景构造出的概念格结点数目庞大，占用大的存储空间，同时概念格结点中一些属性集形成的内涵，用户并不都感兴趣，因而从中提取用户需求知识费时．为了降低概念格构造的时空复杂性，增强实用性和针对性，首先采用谓词逻辑描述用户感兴趣的背景知识，并将背景知识引入到概念格结构中，提出了一种新的概念格：约束概念格．在此基础上，提出了基于背景知识的约束概念格构造算法CCLA．理论分析表明，该算法能有效地减少概念格的存储空间和建格时间．最后，采用恒星天体光谱数据作为形式背景，实验验证了该算法的有效性．     

基于概念格的最简规则挖掘算法

概念格是知识处理和数据分析的重要数学工具.概念格快速构造算法对挖掘关联规则非常重要.本文构造了决策表对应的形式背景和概念格模型,分析了扩展不可分辨矩阵、概念格和最简决策规则发现之间的关系:概念格的内涵都来自于扩展不可分辨矩阵的特征元,最简决策规则的条件元一定是概念格某个结点的内涵缩减.本文给出了形式概念格的快速渐进式构造算法和基于概念格的最简规则获取算法,该算法直观简捷.最后以一个工程实例对本算法的有效性作出了证明.     

基于互关联后继树的多时间序列关联模式挖掘

时间序列是现实生活中常见的数据形式之一，在时间序列中发现频繁模式是分析时间序列变化规律的一项重要任务．提出基于互关联后继树的多时间序列关联模式挖掘算法．该算法首先用Allen逻辑位置关系来描述序列状态关系，根据这些关系在时间窗口内顺序或并行出现情况，获得一个由这些关系组成的特殊序列．在此基础上提出了一个基于互关联后继树的新型挖掘模型，实现了序列间关联模式的挖掘．与其他方法相比，该算法简单、直观，而且整个挖掘过程不需要生成候选模式，大大提高挖掘效率．     

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

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

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

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

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

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

基于剪枝的概念格渐进式构造

概念格是形式概念分析中的核心数据结构。然而，随着需要分析处理的数据量日益剧增，概念格的构造效率成为一个关键问题。采用剪枝方法，消除了概念格构造过程中产生的冗余信息，提出了一种基于剪枝的概念格渐进式构造算法（Pruning based Concept Lattice，PCL），从而减少了概念格内涵的比较次数，提高了概念格的构造效率。采用恒星天体光谱数据作为形式背景，实验验证了算法PCL的正确性和有效性。     

基于消息传递的概念格并行构造

作为形式概念分析的主要工具，概念格已在知识发现、软件工程等诸多领域取得广泛的应用。但是由于概念格自身的完备性：构造复杂性一直是困扰其进一步发展的一大难题。利用高性能并行计算机的计算与存储能力来构造和存储是解决这一问题的有效途径。首先介绍外延独立的同域概念格相关概念及其合并运算，在此基础上提出了一种基于MPI（Message Passing Interface）消息传递机制的概念格并行构造算法。分析表明，该算法是高效、可行的。     

概念特化的概念格更新构造算法

概念格是形式概念分析中的核心数据结构,概念格应用的瓶颈之一是其构造效率. 针对形式背景的某个属性分解为多个新属性得到更加特化的概念,给出了一种基于概念特化的渐进式更新构造算法. 该算法利用分解后的新属性及其相应的形式背景,构造出的概念格与原概念格的某个子概念格作比较,来更新构造概念格,从而减少了比较次数,提高了更新构造的效率. 以天体光谱数据作为形式背景,实验验证了该算法的正确性和有效性.     

基于不同蕴涵算子的模糊概念格建格算法研究

概念格是进行数据分析的有力工具,模糊集是数据处理的有效方法之一,模糊概念格有重要的理论与应用价值,但它的结构与性质依赖于蕴涵算子的选择,基于此,介绍了基于下半连续三角模生成的剩余蕴涵以及模糊概念格的算子和定义,提出了基于不同蕴涵算子的模糊概念格的实现算法,分析了算法的复杂度等性能,最后通过实例说明了基于Godel 蕴涵和Lukasiewicz 蕴涵的模糊概念格的建格方法。     

Variable threshold concept lattices

In this paper, the definition of a variable threshold concept lattice is introduced. Based on a Galois connection, three kinds of variable threshold concept lattices, in which diverse requirements of knowledge discovery can be satisfied by adjusting a threshold, are defined. The number of formal concepts in a variable threshold concept lattice is far less than that in a fuzzy concept lattice. The three kinds of variable threshold concept lattices are constructed between two crisp sets, between a crisp set and a fuzzy set, and between a fuzzy set and a crisp set. Their properties are analogous to that of the classical concept lattices, and can be induced by the fuzzy concept lattice.     

基于iceberg概念格并置集成的闭频繁项集挖掘算法

由于概念格的完备性,在基于概念格的数据挖掘过程中,构造概念格的时间复杂度和空间复杂度一直是影响其应用的主要因素.结合iceberg概念格的半格特性和概念格的集成思想,首先在理论上分析并置集成后的iceberg概念格与由完备概念格裁剪得到的iceberg格同构;然后分析了iceberg概念格集成过程中的映射关系;最终提出一个新颖的基于iceberg概念格并置的闭频繁项集挖掘算法(Icegalamera).此算法避免了完备概念格的计算,并且在构造过程中采用集成和剪枝策略,从而显著提高了挖掘效率.实验证明其产生的闭频繁项集的完备性.使用稠密和稀疏数据集在单站点模式下进行了性能测试,结果表明稀疏数据集上性能优势明显.     

同义概念格的纵向合并

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

概念格研究进展

概念格理论是一种有效的知识表示与知识发现的工具,已被成功应用于许多领域.介绍了国内外现有的建格算法及概念格上分类规则和关联规则提取方法,比较了各种建格算法的优缺点,讨论了概念格属性约简理论的研究方法和研究进展.另外,还介绍了概念格在数据挖掘、信息检索、软件工程等领域的应用,给出了与粗糙集的关系及其它的一些研究成果.最后,给出了概念格有待完善的研究领域.     

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.     

构造概念格的权值优化改进算法

针对基于信息熵与偏差的加权概念格在合并加权概念子格时,所得多属性内涵集权值较其整体在形式背景中的实际权重偏大,权重取值阈值的设置受主观因素干扰导致合并后的概念格规模过大的问题,提出了一种构造概念格的权值优化改进算法.以多属性内涵集在形式背景中的整体信息熵来设置其权值;采用方差计算各概念结点属性内涵集权值的阈值区间,克服了主观意识对阈值设置的影响;通过剪除不满足阈值区间的冗余概念结点,缩小了构造概念格的整体规模,减少了构造概念格的时间消耗.实验结果表明:对比基于信息熵与偏差的加权概念格减少了9.87％的冗余结点,构造整体概念格的时间消耗减少了7.36％,有效提高了加权概念格的构造效率.     

概念格属性约简的判定

引入Galois联络,利用Galois联络深入研究了概念格的基本性质。指出概念格同构是格同构。为了寻求更为简洁、合理的约简算法,在更一般的形式背景（即对象集和属性集有限或无限）中,给出协调集的四类判定定理,将已有结果做了推广而且丰富了协调集的判定。举例说明在一般的形式背景中,约简不一定存在。     

概念格与粗糙集的关系研究

概念格理论和粗糙集理论是两种不同的知识表示与知识发现的工具，都已被成功应用于许多领域.粗糙集理论的数据表现方式是信息系统，其研究基础是对象之间的等价关系;概念格理论的数据表现方式是形式背景，其研究基础是一种有序的层次结构--概念格.本文讨论了概念格理论与粗糙集理论之间的基本联系;重点分析了形式概念与等价类之间、概念格与分划之间的关系;证明了概念格与分划之间可以相互转换，给出了转换算法，并用例子加以说明.     

一种新颖的概念格属性约简算法

概念格是知识处理与分析的一个有力的工具,在知识约简方面有着重要的利用。首先给出了概念格中不同类型属性的等价刻画定理,在此基础上得到了一种新颖的概念格属性约简算法,最后通过实例表明了该约简算法的可行性与有效性。