Multi-adjoint concept lattices with heterogeneous conjunctors and hedges

This paper is related, on the one hand, to the framework of multi-adjoint concept lattices with heterogeneous conjunctors and, on the other hand, to the use of intensifying hedges as truth-stressers. Specifically, we continue on the line of recent works by Belohlavek and Vychodil, which use intensifying hedges as a tool to reduce the size of a concept lattice. In this paper we use hedges as a reduction tool in the general framework of multi-adjoint concept lattices with heterogeneous conjunctors.     

三支决策视角下概念格的分析和比较*

基于概念的构造和形式背景的构成,文中从三支决策的视角探究不同概念格之间的内在联系,分别对比不完备形式背景和经典形式背景中的概念格及直觉模糊形式背景和模糊形式背景中的概念格,展现三支决策在概念格理论中的重要价值.通过对比可以看出,相比经典形式背景和模糊形式背景中的概念格,不完备形式背景和直觉模糊形式背景中的概念格体现三支决策思想,具有数据存储所占空间更小,属性约简更简洁等优势.     

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.     

对偶区间集概念格上区间集协调集的判定方法

对偶区间集概念格是将区间集引入到对偶概念格产生的,它将对偶概念的外延与内涵从经典集合推广到区间集,使之成为一种描述不确定性概念的数学方法。而属性约简是数据挖掘的核心内容之一,是一种研究概念格本质特征的方法,它通过删除冗余属性使数据表中概念的获取与表示变得更简洁。文中主要研究对偶区间集概念格上区间集协调集的判定方法。首先基于对偶区间集概念格的同构,引入了区间集协调集,给出了对偶区间集概念格上区间集协调集的一系列判定定理,进而讨论了利用区间集协调集获取区间集属性约简的方法。     

Entropy of capacities on lattices and set systems

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.     

Factorization of fuzzy concept lattices with hedges by modification of input data

We study the problem of reducing the size of fuzzy concept lattices with hedges by means of factorization. As it has been shown previously for the case of fuzzy concept lattices without hedges, the lattice computed by factorization of a fuzzy concept lattice is isomorphic to a fuzzy concept lattice of some other data table. This means that the factor concept lattice can be computed directly as a concept lattice, whose underlying data table is obtained by a modification of the original data table. There are two known types of such a modification: first, based on factorization of residuated lattices, and second, based on computation of shifted attributes. In this paper, we extend these results to a more general case of concept lattices with hedges.     

概念格中不同类型多值背景的研究*

通过分析概念格在数据处理中所存在的局限,根据信息的不同存在方式及不同应用领域对概念格的不同要求,在三种数据类型上扩充了经典概念格;讨论了三类扩充概念格之间相互转换的方法,进而提出了扩充概念格与经典概念格的融合原理,使概念格在多种数据的处理上有了更灵活的应用。     

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.     

从文本知识源中挖掘概念格的形式分析

文本知识挖掘是数据挖掘中一个很重要的研究领域。论文主要讨论如何在不使用概念换算方法下从文本知识中抽取概念格以及分析概念格之间的结构关联。该方法有两部分构成：一是将文本中所描述的对象转化为多值上下文;二是分析多值上下文之间的各种操作以及相应概念格之间的关联。重点分析了多值上下文的增加、删除和乘积等操作以及相应概念格之间的序嵌入映射,得到了一些重要命题。知识工程师可以利用这些命题进行文本知识分析以及从概念格上进一步抽取关联规则。     

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

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

A note on Trillas' CHC models

Trillas et al. [E. Trillas, S. Cubillo, E. Castiñeira, On conjectures in orthocomplemented lattices, Artificial Intelligence 117 (2000) 255-275] recently proposed a mathematical model for conjectures, hypotheses and consequences (abbr. CHCs), and with this model we can execute certain mathematical reasoning and reformulate some important theorems in classical logic. We demonstrate that the orthomodular condition is not necessary for holding Watanabe's structure theorem of hypotheses, and indeed, in some orthocomplemented but not orthomodular lattices, this theorem is still valid. We use the CHC operators to describe the theorem of deduction, the theorem of contradiction and the Lindenbaum theorem of classical logic, and clarify their existence in the CHC models; a number of examples is presented. And we re-define the CHC operators in residuated lattices, and particularly reveal the essential differences between the CHC operators in orthocomplemented lattices and residuated lattices.     

Reduction method for concept lattices based on rough set theory and its application

Rough set theory and formal concept analysis are two complementary mathematical tools for data analysis. In this paper, we study the reduction of the concept lattices based on rough set theory and propose two kinds of reduction methods for the above concept lattices. First, we present the sufficient and necessary conditions for justifying whether an attribute and an object are dispensable or indispensable in the above concept lattices. Based on the above justifying conditions, we propose a kind of multi-step attribute reduction method and object reduction method for the concept lattices, respectively. Then, on the basis of the defined discernibility functions of the concept lattices, we propose a kind of single-step reduction method for the concept lattices. Additionally, the relations between the attribute reduction of the concept lattices in FCA and the attribute reduction of the information system in rough set theory are discussed in detail. At last, we apply the above multi-step attribute reduction method for the concept lattices based on rough set theory to the reduction of the redundant premises of the multiple rules used in the job shop scheduling problem. The numerical computational results show that the reduction method for the concept lattices is effective in the reduction of the multiple rules.     

一种基于直积运算的概念格合并算法

现有的渐进式概念格构造算法,不能有效利用已有的概念格.当形式背景的属性数目发生变化时,需要以单个属性或属性集合为对象,重新构造概念格.为此,提出了一种基于已有概念格的概念格合并算法,对已有概念格做直积运算,通过直积格和总格的映射关系,自底向上直接构造出总概念格.这个算法适用于属性交集为空的形式背景的合并.     

一种新的概念格图形布局优化策略

层与层之问边交叉数的多少在概念格层次图布局中尤为重要,它直接影响概念格的可读性和可理解性.如何既能实现人机交互方便操作,又能有效地减少边的交叉数,已成为目前概念格图形布局研究中的主要问题.分析了概述格布局的国内外发展现状,介绍了如何求解概念格图形中层与层之间边交叉数问题的方法,然后结合遗传算法,提出了一种新的在概念格图形布局过程中减少边交叉数问题的优化策略,有效地减少了二维概念格图形布局过程中边的交叉.     

Partial residuated structures and quantum structures

Residuated structures, bounded commutative residuated lattices in particular, play an important role in the study of algebraic structures of logics—classical and non-classical. In this paper, by introducing partial adjoint pairs, a new structure is presented, named partial residuated lattices, which can be regarded as a version of residuated lattices in the case of partial operations, and their basic properties are investigated. The relations between partial residuated lattices and certain quantum structures are considered. We show that lattice effect algebras and D-lattices both are partial residuated lattices. Conversely, under certain conditions partial residuated lattices are both lattice effect algebras and D-lattices. Finally, dropping the assumption on commutativity, some similar results are obtained. Project supported by the NSF of China (No. 10771524).     

Attribute reduction theory of concept lattice based on decision formal contexts

The theory of concept lattices is an efficient tool for knowledge representation and knowledge discovery, and is applied to many fields successfully. One focus of knowledge discovery is knowledge reduction. Based on the reduction theory of classical formal context, this paper proposes the definition of decision formal context and its reduction theory, which extends the reduction theory of concept lattices. In this paper, strong consistence and weak consistence of decision formal context are defined respectively. For strongly consistent decision formal context, the judgment theorems of consistent sets are examined, and approaches to reduction are given. For weakly consistent decision formal context, implication mapping is defined, and its reduction is studied. Finally, the relation between reducts of weakly consistent decision formal context and reducts of implication mapping is discussed.     

Note on generating fuzzy concept lattices via Galois connections

The aim of this paper is to compare an approach of creating fuzzy concept lattices proposed by Popescu with several other approaches. Particularly, we show that this approach is in some way equivalent to the approach of Kraj?i called generalized concept lattices. We also give a straightforward generalization of Popescu’s approach to non-homogeneous cases.     

Bit-oriented quantum public-key encryption based on quantum perfect encryption

A bit-oriented quantum public-key encryption scheme is presented. We use Boolean functions as private-key and randomly changed pairs of quantum state and classical string as public-keys. Following the concept of quantum perfect encryption, we prepare the public-key with Hadamard transformation and Pauli transformation. The quantum part of public-keys is various with different classical strings. In contrast to the typical classical public-key scheme, one private-key in our scheme corresponds to an exponential number of public-keys. We investigate attack to the private-key and prove that the public-key is a totally mixed state. So the adversary cannot acquire any information about private-key from measurement of the public-key. Then, the attack to encryption is analyzed. Since the trace distance between two different ciphertexts is zero, the adversary cannot distinguish between the two ciphertext states and also obtains nothing about plaintext and private-key. Thus, we have the conclusion that the proposed scheme is information-theoretically secure under an attack of the private-key and encryption.     

An outlier mining algorithm based on constrained concept lattice

Traditional outlier mining methods identify outliers from a global point of view. These methods are inefficient to find locally biased data points (outliers) in low dimensional subspaces. Constrained concept lattices can be used as an effective formal tool for data analysis because constrained concept lattices have the characteristics of high constructing efficiency, practicability and pertinency. In this paper, we propose an outlier mining algorithm that treats the intent of any constrained concept lattice node as a subspace. We introduce sparsity and density coefficients to measure outliers in low dimensional subspaces. The intent of any constrained concept lattice node is regarded as a subspace, and sparsity subspaces are searched by traversing the constrained concept lattice according to a sparsity coefficient threshold. If the intent of any father node of the sparsity subspace is a density subspace according to a density coefficient threshold, then objects contained in the extent of the sparsity subspace node are considered as bias data points or outliers. Our experimental results show that the proposed algorithm performs very well for high red-shift spectral data sets.