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.     

变精度对偶概念格的构造及其性质

形式概念分析作为进行数据分析的有效工具,吸引了世界各地研究者的关注。由于二值形式背景的局限性,人们将模糊集引入形式概念分析。但是模糊形式背景生成的模糊概念数量庞大。讨论了基于模糊形式背景的模糊对偶概念格的概念约简,构造出了模糊对偶概念格的三种变精度概念格,讨论了它们的关系。结果表明每一种变精度概念格都保留了模糊对偶概念格中相对重要的概念。变精度对偶概念格的概念数量远远少于模糊对偶概念格的概念数。     

On basic conditions to generate multi-adjoint concept lattices via Galois connections

This paper introduces sufficient and necessary conditions with respect to the fuzzy operators considered in a multi-adjoint frame under which the standard combinations of multi-adjoint sufficiency, possibility, and necessity operators form (antitone or isotone) Galois connections. The underlying idea is to study the minimal algebraic requirements so that the concept-forming operators (defined using the same syntactical form than the extension and intension operators of multi-adjoint concept lattices) form a Galois connection. As a consequence, given a relational database, we have much more possibilities to construct concept lattices associated with it, so that we can choose the specific version which better suits the situation.     

A local approach to concept generation

Generating concepts defined by a binary relation between a set of properties and a set of objects is one of the important current problems encountered in Data Mining and Knowledge Discovery in Databases. We present a new algorithmic process which computes all the concepts, without requiring an exponential-size data structure, and with a good worst-time complexity analysis, which makes it competitive with the best existing algorithms for this problem. Our algorithm can be used to compute the edges of the lattice as well at no extra cost.      

Isotone fuzzy Galois connections with hedges

We study isotone fuzzy Galois connections and concept lattices parameterized by particular unary operators. The operators represent linguistic hedges such as “very”, “rather”, “more or less”, etc. Isotone fuzzy Galois connections and concept lattices provide an alternative to their antitone counterparts which are the fundamental structures behind formal concept analysis of data with fuzzy attributes. We show that hedges enable us to control the number of formal concepts in the associated concept lattice. We also describe the structure of the concept lattice and provide a counterpoint to the main theorem of concept lattices.     

A new algebraic structure for formal concept analysis

Formal concept analysis (FCA) originally proposed by Wille [39], is an important theory for data analysis and knowledge discovery. Concept lattice is the core of the mathematical theory of formal concept analysis. To address the requirements of real word applications, concept lattice has been extended to many other forms from the theoretical point of view and possible applications. In this paper, with the aim of deriving the mathematical properties of formal concepts from the point of algebra, we propose a new algebra system for the formal context. Under the frame of the proposed system, some interesting properties of formal concepts are explored, which could be applied to explore concept hierarchy and ontology merging.     

Residuated lattices of block relations: size reduction of concept lattices

We deal with size reduction of concept lattices by means of factorization by block relations defined on corresponding formal context. We show that all block relations with a multiplication defined by means of relational composition form a (non-commutative) residuated lattice. Such residuated lattice can be then thought of as a scale of truth degrees using which we evaluate formulas of predicate logic specifying the desired parameters of the factorization. We also introduce efficient algorithms computing operations on a residuated lattice of block relations. The naive way how to design such algorithms is to compute all the formal concepts of a given context in advance, and then apply some well-known properties of residuated lattices. Our algorithms get rid of the time-consuming precomputation of all concepts.     

一种区间数分解与定标算法及其扩展形式背景的概念格生成方法

现有的概念格模型无法处理既包含以布尔值表示的信息,又包含以标量、模糊数及区间数表示的信息。因此,针对包含所有这些信息类型的扩展的形式背景提出它的处理方法,在此基础上,生成经扩展的概念格,是一项有意义的工作。提出了一种新的区间数分解与定标算法,以处理含有多种类型的扩展形式背景,并给出了相应的扩展格生成算法。最后,实验表明,该方法具有良好的效果。     

Evaluation of IPAQ questionnaires supported by formal concept analysis

The paper presents a method for evaluation of questionnaires supported by formal concept analysis. Formal concept analysis provides an expert with a structured view on the data contained in the questionnaires. The method results from experiments with IPAQ (International Physical Activity Questionnaire). The structured view on the data provided by the method suggests various hypotheses which can later be tested. In addition, the structured view on data itself proved to be sufficiently informative to the expert. In addition to the method, the paper presents experiments with evaluation of IPAQ.     

Study of decision implications based on formal concept analysis

In this paper, the notions of decision table and decision rule in Rough Set Theory are introduced naturally into Formal Concept Analysis as decision context and decision implication. Since extracting decision implications directly from decision context takes time, we present an inference rule called α-decision inference rule to eliminate the superfluous decision implications. Moreover, based on the inference rule we introduce the notion of α-maximal decision implication and prove that the set of all α-maximal decision implications is complete (α-complete) and non-redundant (α-non-redundant). Finally, we present a method to generate the set.     

基于形式概念分析的依赖簇检测方法研究

依赖簇是相互依赖的程序组件的最大集合,大尺寸依赖簇已被证实在程序中普遍存在。依赖簇中任意一点产生变动都会引起其他组件的连锁反应,进而对整个系统造成潜在的影响,这将会阻碍软件理解、测试、维护等方面的工作。检测出依赖簇是消除不良影响的前提,目前通过单调切片尺寸图近似检测依赖簇的方法的准确度较低,会出现漏报和误报。提出了一种基于形式概念分析的依赖簇检测方法,通过概念包含度选取的大型概念来检测大尺寸依赖簇,并进一步提出轻量化策略以有针对性地选取大型概念,降低计算开销。在12个不同规模和领域的开源程序上,将所提方法与单调切片尺寸图法进行对比实验,结果表明所提方法及其轻量化策略能够有效地检测大尺寸依赖簇,可以提高依赖簇检测的准确度和效率。     

形式背景同构判定的等价类算法

同构生成概念格是获取概念格的另一途径,而形式背景同构判定是这一方法的前提,也是决定整个算法时间复杂度的关键。本文提出的基于等价类法的形式背景同构判定算法,有效地提高了同构判定的效率。结合形式背景的分解和约简等手段,为概念格的构造提供了一种有实用价值的方法。本文对该方法的原理和算法设计进行了较详细的讨论,并通过实验,验证了算法的正确性和有效性。     

一种基于模糊聚类的模糊本体生成方法

本文研究了一种从模糊背景生成模糊本体的方法。模糊本体由以下几部分组成,分别是：模糊形式概念分析、模糊概念聚类及模糊本体生成。首先,模糊形式概念分析将模糊逻辑嵌入形式概念分析以构成模糊概念格。其次,模糊概念聚类从模糊概念格构造概念层次。最后,模糊本体生成部分从概念层次生成模糊本体。     

基于形式概念的语义网本体的构建与展现

作为语义网基础的本体是共享概念模型的明确的形式化规范说明,它提供一种让计算机可以交换、搜寻和认同文字信息的方式。有效地构建、展现本体成为应用本体的关键问题,然而,现有构建本体的各种方法都在不同方面存在着限制。经过分析比较,本文采用形式概念分析理论构造本体阶层来弥补缺陷,并结合机率模式展现本体,用于表达概念之间及概念、资料间的相关性,利用文件与概念的相关性排序结果,以便于用户找到最相关的信息,从而有效地提高了信息查找的效率。本文通过实例来演示本体的构造与表达。     

基于形式概念分析的词义理解研究

探讨了形式概念分析在自然语言理解中的多义词分析及义素分析中的应用。在对多义词进行分析时,根据词性与词义之间的二元关系,构造词性与词义的决策背景,进而发现了词性与词义之间的决策规则,并对这些决策规则进行了解释;在对义素分析进行研究时,根据语言对象及其语义特征之间的二元关系构造形式背景,并在此背景上分析语言对象,实例表明了形式概念分析既可以很容易地对词语进行分类,又可以很直观地反映词类之间的关系,是进行义素分析的一种有效工具。     

基于优势关系的概念格

对基于优势关系的形式背景进行了讨论,在基于优势关系的形式背景上建立了对象偏序集、属性偏序集以及对象-属性偏序集,提出了基于优势关系的概念格的定义及构建方法.这些结论进一步丰富了概念格的理论,对研究基于优势关系的信息系统的规则提取提供了新的思路.     

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

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

基于三维空间的概念格自动布局

论文讨论了几种常见的概念格自动布局形式,通过对各种自动布局方式特点的分析,提出了概念格的三维自动布局策略,对三雏空间中的层次布局与层内节点自动布局问题进行探讨并加以实现,较好地解决了二维布局中格节点横向过度扩张和线段交叉的问题。     

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

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

基于概念格的非数值型数据聚类稳定性分析

概念稳定性的计算是一个NP-完全问题,且概念稳定性在聚类分析中具有十分重要的意义。概念格自身特点决定了其适合作为概念稳定性分析的工具。为了获得一个形式化的计算概念稳定性的方法,定义了概念的核心对象集,并给出了计算核心对象集的方法,进而得到了计算概念稳定性的方法。另外,根据概念格的对偶原理,得到了一个计算类标签的方法。最后用例子说明概念稳定性在聚类分析中的应用。