Mining gene expression data with pattern structures in formal concept analysis

This paper addresses the important problem of efficiently mining numerical data with formal concept analysis (FCA). Classically, the only way to apply FCA is to binarize the data, thanks to a so-called scaling procedure. This may either involve loss of information, or produce large and dense binary data known as hard to process. In the context of gene expression data analysis, we propose and compare two FCA-based methods for mining numerical data and we show that they are equivalent. The first one relies on a particular scaling, encoding all possible intervals of attribute values, and uses standard FCA techniques. The second one relies on pattern structures without a priori transformation, and is shown to be more computationally efficient and to provide more readable results. Experiments with real-world gene expression data are discussed and give a practical basis for the comparison and evaluation of the methods.     

A formal concept analysis of harmonic forms and interval structures

While small concept lattices are often represented by line diagrams to better understand their full structure, large diagrams may be too complex to do this. However, such a diagram may still be used to receive new ideas about the inherent structure of a concept lattice. This will be demonstrated for a certain family of formal contexts arising from mathematical musicology. In particular, we investigate how chord patterns can be characterised by their interval structure. For such contexts of pattern structures, it turns out that each corresponding concept lattice incorporates two competing building principles, one emanating from the top the other from the bottom of the lattice.     

Similarity measures in formal concept analysis

Formal concept analysis (FCA) has been applied successively in diverse fields such as data mining, conceptual modeling, social networks, software engineering, and the semantic web. One shortcoming of FCA, however, is the large number of concepts that typically arise in dense datasets hindering typical tasks such as rule generation and visualization. To overcome this shortcoming, it is important to develop formalisms and methods to segment, categorize and cluster formal concepts. The first step in achieving these aims is to define suitable similarity and dissimilarity measures of formal concepts. In this paper we propose three similarity measures based on existent set-based measures in addition to developing the completely novel zeros-induced measure. Moreover, we formally prove that all the measures proposed are indeed similarity measures and investigate the computational complexity of computing them. Finally, an extensive empirical evaluation on real-world data is presented in which the utility and character of each similarity measure is tested and evaluated.     

Assessing semantic annotation activities with formal concept analysis

This paper describes an approach to assessing semantic annotation activities based on formal concept analysis (FCA). In this approach, annotators use taxonomical ontologies created by domain experts to annotate digital resources. Then, using FCA, domain experts are provided with concept lattices that graphically display how their ontologies were used during the semantic annotation process. In consequence, they can advise annotators on how to better use the ontologies, as well as how to refine these ontologies to better suit the needs of the semantic annotators. To illustrate the approach, we describe its implementation in @note, a Rich Internet Application (RIA) for the collaborative annotation of digitized literary texts, we exemplify its use with a case study, and we provide some evaluation results using the method.     

Nondeterministic dependencies in relations: An extention of the concept of functional dependency

In the present article, some special semantic integrity constraints—so called nondeterministic dependencies—are proposed. These dependencies can be regarded as stochastic extensions of functional dependencies. After some basic definitions, the concept of nondeterministic dependency is introduced. Examples are given and an implementation for a statistical analysis system is described. Some properties are discussed.     

The Chu construction and generalized formal concept analysis

We continue studying the connections between the Chu construction on the category ChuCors of formal contexts and Chu correspondences, and generalizations of Formal Concept Analysis (FCA). All the required constructions like categorical product, tensor product, together with its bifunctor properties are introduced and proved. The final section focuses on how the second-order generalization of FCA can be built up in terms of the Chu construction.     

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.     

Update operations in deductive databases with functional dependencies

We study the problem of updating intensional relations in the framework of deductive databases on which integrity constraints (specifically functional dependencies) are defined. First, a formalization of a model-theoretic semantics of updates is provided: the notions ofrepresentability, consistency anddeterminism are introduced to characterize the various cases. Then, a proof-theoretic approach, based on a variant of resolution integrated with the chase procedure, is defined, showing that the method exactly captures the above notions. It turns out that using functional dependencies it is possible to resolve potential ambiguities in several practical cases. Also, precomputations can be performed at definition time to execute update requests more efficiently.Work partially supported by Consiglio Nazionale delle Ricerche, within Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo, LRC Logidata+, and by System & Management S.p.A.A preliminary version of this paper appeared in [33].     

Fast factorization by similarity in formal concept analysis of data with fuzzy attributes

We present a method of fast factorization in formal concept analysis (FCA) of data with fuzzy attributes. The output of FCA consists of a partially ordered collection of clusters extracted from a data table describing objects and their attributes. The collection is called a concept lattice. Factorization by similarity enables us to obtain, instead of a possibly large concept lattice, its factor lattice. The elements of the factor lattice are maximal blocks of clusters which are pairwise similar to degree exceeding a user-specified threshold. The factor lattice thus represents an approximate version of the original concept lattice. We describe a fuzzy closure operator the fixed points of which are just clusters which uniquely determine the blocks of clusters of the factor lattice. This enables us to compute the factor lattice directly from the data without the need to compute the whole concept lattice. We present theoretical solution and examples demonstrating the speed-up of our method.     

Privacy-preserving publishing microdata with full functional dependencies

Data publishing has generated much concern on individual privacy. Recent work has shown that different background knowledge can bring various threats to the privacy of published data. In this paper, we study the privacy threat from the full functional dependency (FFD) that is used as part of adversary knowledge. We show that the cross-attribute correlations by FFDs (e.g., Phone → Zipcode) can bring potential vulnerability. Unfortunately, none of the existing anonymization principles (e.g., k-anonymity, ?-diversity, etc.) can effectively prevent against an FFD-based privacy attack. We formalize the FFD-based privacy attack and define the privacy model, (d,?)-inference, to combat the FD-based attack. We distinguish the safe FFDs that will not jeopardize privacy from the unsafe ones. We design robust algorithms that can efficiently anonymize the microdata with low information loss when the unsafe FFDs are present. The efficiency and effectiveness of our approach are demonstrated by the empirical study.     

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.     

Real formal concept analysis based on grey-rough set theory

One of the main concepts in grey system theory is how systems should be controlled under incomplete or lack of information situation. Grey number denoting an uncertain value is described in real interval from this concept. In this paper, we introduce the real formal concept analysis based on grey-rough set theory by using grey numbers, instead of binary values. We propose, to extend the notion of Galois connection in a real binary relation as well as the notions of formal concept and Galois lattice. The relationships between the new notions and old ones are discussed. Finally, we present a grey-rough set approach to Galois lattices reduction.     

Friendly web services selection exploiting fuzzy formal concept analysis

This work describes a system for supporting the user in the discovery of semantic web services, taking into account personal requirements and preference. Goal is to model an ad-hoc service request by selecting conceptual terms rather than using strict syntax formats. Through a concept-based navigation mechanism indeed, the user discovers conceptual terminology associated to the web resources and uses it to generate an appropriate service request which syntactical matches the names of input/output specifications. The approach exploits the fuzzy formal concept analysis for modeling concepts and relative relationships elicited from web resources. After the request formulation and submission, the system returns the list of semantic web services that match the user query.     

An application of formal concept analysis to semantic neural decoding

This paper proposes a novel application of Formal Concept Analysis (FCA) to neural decoding: the semantic relationships between the neural representations of large sets of stimuli are explored using concept lattices. In particular, the effects of neural code sparsity are modelled using the lattices. An exact Bayesian approach is employed to construct the formal context needed by FCA. This method is explained using an example of neurophysiological data from the high-level visual cortical area STSa. Prominent features of the resulting concept lattices are discussed, including indications for hierarchical face representation and a product-of-experts code in real neurons. The robustness of these features is illustrated by studying the effects of scaling the attributes.     

形式概念分析在Web应用测试用例选取中的应用

为了避免基于模型的Web应用测试中存在的状态组合爆炸问题,分析了经典的每个一次和基本选择的状态组合爆炸避免方法,指出了这两种方法的不足,提出了应用形式概念分析,根据给定的测试覆盖准则,精简测试用例集,避免状态组合爆炸的方法,并改进了Sampath的测试用例选取规则.最后根据形式概念分析的原理,开发了测试用例集精简工具,提高了测试过程的自动化程度,用实例说明了方法的有效性.     

Combined rough sets with flow graph and formal concept analysis for business aviation decision-making

Although business aviation has been popular in the USA, Europe, and South America, however, top economies in East Asia, including Japan, Korea, and Taiwan, have been more conservative and lag behind in the development of business aviation. In this paper, we hope to discover possible trends and needs of business aviation for supporting the government to make decision in anticipation of eventual deregulation in the near future. We adopt knowledge-discovery tools based on rough set to analyze the potential for business aviation through an empirical study. Although our empirical study uses data from Taiwan, we are optimistic that our proposed method can be similarly applied in other countries to help governments there make decisions about a deregulated market in the future.     

Exploiting functional dependencies in declarative problem specifications

In this paper we tackle the issue of the automatic recognition of functional dependencies among guessed predicates in constraint problem specifications. Functional dependencies arise frequently in pure declarative specifications, because of the intermediate results that need to be computed in order to express some of the constraints, or due to precise modeling choices, e.g., to provide multiple viewpoints of the search space in order to increase constraint propagation. In either way, the recognition of dependencies greatly helps solvers, allowing them to avoid spending search on unfruitful branches, while maintaining the highest degree of declarativeness. By modeling constraint problem specifications as second-order formulae, we provide a characterization of functional dependencies in terms of semantic properties of first-order ones, and prove undecidability of the problem of their recognition. Despite such negative result, we advocate the (in many cases effective) possibility of using automated tools to mechanize this task. Additionally, we show how suitable search procedures can be automatically synthesized in order to exploit recognized dependencies. We present opl examples of various problems, taken from bio-informatics, planning and resource allocation, and show how in many cases opl greatly benefits from the addition of such search procedures. Moreover, we also give evidence that writing sophisticated ad-hoc search procedures that handle dependencies exploiting the peculiarities of the particular problem is a very difficult and error-prone task which in many cases does not seem to pay-off.     

基于形式概念分析的煤矿事故本体构建

为解决煤矿事故知识管理混乱、联动不足等问题,构建了基于形式概念分析的煤矿事故本体。首先分别构建以煤矿领域的主题词表和文本集为数据源的形式背景,并通过并叠置运算得到异构资源的形式背景,然后利用概念格构造工具将形式背景转换为概念格,最后从概念格中抽取概念、属性和实例组织成煤矿事故本体。利用煤矿事故本体对煤矿事故知识进行组织和形式化表示,可实现煤矿事故知识的共享和重用,为煤矿安全预警提供帮助。     

Structure of closures in relational schemas with join and functional dependencies

Translations of relational schemas are extended to the set of functional and join dependencies. A basic theorem on the representation of the closure of an attribute subset is proved.Translated from Kibernetika, No. 5, pp. 18–26, September–October, 1990.     

An integration method combining Rough Set Theory with formal concept analysis for personal investment portfolios

The classical Rough Set Theory (RST) always generates too many rules, making it difficult for decision makers to choose a suitable rule. In this study, we use two processes (pre process and post process) to select suitable rules and to explore the relationship among attributes. In pre process, we propose a pruning process to select suitable rules by setting up a threshold on the support object of decision rules, to thereby solve the problem of too many rules. The post process used the formal concept analysis from these suitable rules to explore the attribute relationship and the most important factors affecting decision making for choosing behaviours of personal investment portfolios. In this study, we explored the main concepts (characteristics) for the conservative portfolio: the stable job, less than 4 working years, and the gender is male; the moderate portfolio: high school education, the monthly salary between NT$30,001 (US$1000) and NT$80,000 (US$2667), the gender is male; and the aggressive portfolio: the monthly salary between NT$30,001 (US$1000) and NT$80,000 (US$2667), less than 4 working years, and a stable job. The study result successfully explored the most important factors affecting the personal investment portfolios and the suitable rules that can help decision makers.