Complex Data Analytics with Formal Concept Analysis

Description

FCA is an important formalism that is associated with a variety of research areas such as lattice theory, knowledge representation, data mining, machine learning, and semantic Web. It is successfully exploited in an increasing number of application domains such as software engineering, information retrieval, social network analysis, and bioinformatics. Its mathematical power comes from its concept lattice formalization in which each element in the lattice captures a formal concept while the whole structure represents a conceptual hierarchy that offers browsing, clustering and association rule mining. Complex data analytics refers to advanced methods and tools for mining and analyzing data with complex structures such as XML/Json data, text and image data, multidimensional data, graphs, sequences and streaming data. It also covers visualization mechanisms used to highlight the discovered knowledge. This edited book examines a set of important and relevant research directions in complex data management, and updates the  contribution of the FCA community in analyzing complex and large data such as knowledge graphs and interlinked contexts.  For example, Formal Concept Analysis and some of its extensions are exploited, revisited and coupled with recent processing parallel and distributed paradigms to maximize the benefits in analyzing large data. Foreword Preface Acknowledgments Contents List of Contributors Acronyms 1 Formal Concept Analysis and Extensions for Complex DataAnalytics 1.1 Introduction 1.2 Background 1.2.1 Formal Concepts and Line Diagrams 1.2.2 Non Binary Data 1.2.2.1 Many-Valued Contexts 1.2.2.2 Pattern Structures 1.2.3 Implication Computation 1.3 Extensions to FCA 1.3.1 Logical FCA 1.3.2 Fuzzy FCA 1.3.3 Relational Concept Analysis 1.3.4 Triadic Concept Analysis 1.3.5 Approximation 1.4 Complex Data Analytics 1.5 Contributions References 2 Conceptual Navigation in Large Knowledge Graphs 2.1 Introduction 2.2 Graph-FCA: Extending FCA to Knowledge Graphs 2.2.1 Graph Context 2.2.2 Graph Patterns 2.2.3 Graph Concepts 2.2.4 Graph Concept Lattice 2.3 Conceptual Navigation in Graph-FCA Lattices 2.3.1 Abstract Conceptual Navigation (ACN) 2.3.2 Graph-ACN: Instantiating ACN to Knowledge Graphs 2.4 Scaling to Large RDF Graphs with SPARQL Endpoints 2.4.1 From Graph-FCA to RDF and SPARQL 2.4.2 Computing the Result, Index, and Links 2.4.3 Living with Partial Results 2.5 Rising in Expressivity 2.5.1 An Algebraic Form of Queries 2.5.2 Extensions of the Query Algebra 2.6 The Sparklis Tool and Application Cases 2.6.1 Sparklis 2.6.2 Application Cases 2.7 Conclusion and Perspectives References 3 FCA2VEC: Embedding Techniques for Formal Concept Analysis 3.1 Introduction 3.2 Related Work 3.3 Foundations 3.3.1 Formal Concept Analysis 3.3.2 Word2Vec 3.3.2.1 The Skip-Gram and the Continuous Bag of Words Architecture 3.4 Modeling 3.4.1 Retrieving FCA Features Through Closure2Vec 3.4.1.1 Exact Representation of the Closure Operator 3.4.1.2 Considering the Unconstraint Problem 3.4.1.3 Representing Closure Operators Using Linear Functions 3.4.1.4 Linear Representable Part of Closure Operators 3.4.1.5 Non-linear Embedding Through Closure2Vec 3.4.2 Object2Vec and Attribute2Vec 3.4.2.1 SG and CBOW in the Realm of Object2Vec 3.5 Experiments 3.5.1 Object2Vec and Attribute2Vec 3.5.1.1 Link Prediction Using Object2Vec 3.5.1.2 Clustering Attributes with Attribute2Vec 3.5.1.3 Discussion 3.5.2 FCA Features Through Closure2Vec 3.5.2.1 Distance of Covering Relation 3.5.2.2 Distance of Canonical Bases 3.5.2.3 Discussion 3.5.2.4 Empirical Structural Observations 3.6 Conclusion References 4 Analysis of Complex and Heterogeneous Data Using FCA and Monadic Predicates 4.1 Introduction 4.2 The NextPriorityConcept Algorithm 4.2.1 Formal Concept Analysis 4.2.1.1 Concept Lattice 4.2.1.2 Pattern Structures 4.2.2 NextPriorityConcept 4.2.2.1 Predicates for Heterogeneous Data 4.2.2.2 Descriptions and Strategies 4.2.2.3 Bordat's Algorithm, Priority Queue and Propagation of Constraints 4.2.2.4 Description of the Algorithm 4.2.2.5 The GALACTIC Platform 4.3 Use Cases 4.3.1 Binary and Categorical Characteristics with the Lenses Dataset 4.3.1.1 Lenses with the Entropy as Strategy 4.3.1.2 Lenses with the Minimal Logic Formulae as Description 4.3.2 Numerical Characteristics with the Iris Dataset 4.3.2.1 Iris with the Entropy as Strategy. 4.3.2.2 Iris with the Convex Hull as Description 4.3.3 Sequential Characteristics with the Daily-actions Dataset 4.3.3.1 Daily-actions with the Common Subsequences 4.3.4 Sequential Characteristics with the Wine City Dataset 4.3.4.1 Wine City Dataset with the Prefix Description and Strategy 4.4 Conclusion References 5 Dealing with Large Volumes of Complex Relational Data UsingRCA 5.1 Introduction 5.2 Background 5.3 Related Work 5.4 RCA for Environmental Data 5.4.1 Two Complex Datasets from the EnvironmentalDomain 5.4.1.1 Pesticidal and Antimicrobial Data 5.4.1.2 Water Data 5.4.2 Experimenting RCA Algorithms 5.4.2.1 Experiments on Knomana Dataset 5.4.2.2 Experiments on Fresqueau Dataset 5.4.3 Discussion 5.5 Analysing Sequences from Water Quality Monitoring UsingRCA 5.5.1 RCA-Seq 5.5.1.1 Modelling Hydro-Ecological Sequential Data. 5.5.1.2 Exploring Hydro-Ecological Sequential Data with RCA 5.5.1.3 Extracting DAG by Navigating the RCA Output 5.5.2 Experiments 5.5.3 Navigating the Resulting Hierarchy of Graphs 5.6 Conclusion References 6 Computing Dependencies Using FCA 6.1 Introduction 6.2 Notation 6.2.1 Equivalence Relation 6.2.2 Tolerance Relations 6.3 FCA and Database Dependencies 6.3.1 Functional Dependencies 6.3.2 Similarity Dependencies 6.3.3 Formal Concept Analysis 6.3.4 Functional Dependencies as Implications 6.3.5 Pattern Structures 6.4 Results 6.4.1 Characterization of Functional Dependencies with Pattern Structures 6.4.2 Similarity Dependencies 6.5 Discussion 6.6 Conclusions References 7 Leveraging Closed Patterns and Formal Concept Analysis for Enhanced Microblogs Retrieval 7.1 Introduction 7.2 Related Work 7.3 FCA-Based Query Expansion 7.3.1 Patterns Discovery 7.4 Patterns and Word Embeddings Based Query Expansion 7.4.1 Word Embeddings: Word2Vec Model 7.4.2 Expansion Terms Selection 7.5 Experiments 7.5.1 Dataset Description 7.5.2 Retrieval Model 7.5.3 Experimental Protocol 7.5.4 Experimental Results 7.6 Conclusion References 8 Scalable Visual Analytics in FCA 8.1 Introduction 8.1.1 Scalable Visual Analytics in FCA 8.1.2 Organisation 8.2 Graph-Theoretic Introduction to FCA 8.2.1 Formal Context 8.2.2 Formal Concepts 8.2.3 Concept Lattice Digraph 8.2.4 Line Diagram 8.2.5 Simplifying Implications 8.2.6 Visualising Implications 8.2.7 Coordinating Views of Implications and Concepts 8.3 Introduction to Visual Analytics 8.3.1 Algorithmic Analysis 8.3.2 Graph Drawing 8.3.3 Information Visualisation 8.3.4 Multiple Coordinated Views 8.3.5 Tight Coupling 8.4 Layout, Visualisation and Interaction 8.4.1 Reducing Digraph Size 8.4.2 Layout of Line Diagram 8.4.3 Interactive Visualisation 8.4.4 Discovering or Imposing Tree Structure 8.4.5 Demand for Enhanced Tool Support 8.4.6 Implications 8.5 Three FCA Prototypes 8.5.1 Hierarchical Parallel Decomposition 8.5.2 User-Guided FCA 8.5.3 Structural Navigation 8.6 Discovering Insightful Implications 8.6.1 Visualisation of Implications 8.6.2 Our Data Visualisation Approach 8.6.2.1 Attribute Plot 8.6.2.2 Implication Plot 8.6.2.3 Rules Data Table 8.7 Conclusions and Future Work References 9 Formal Methods in FCA and Big Data 9.1 Introduction 9.2 Context and Concept Lattice Reduction Methods 9.3 Improved Management of Implications 9.4 Minimal Generators to Represent Knowledge 9.5 Probably Approximately Correct Implication Bases 9.6 Summary and Possible Future Trends References 10 Towards Distributivity in FCA for Phylogenetic Data 10.1 Motivation 10.2 Models: Lattices, Semilattices, Median Algebras and Median Graphs 10.2.1 Lattices and FCA 10.2.2 Distributive Lattices 10.2.3 Median Graphs 10.3 Algorithm to Produce a Distributive -Semilattice 10.4 A Counter-Example for the Existence of a Minimum Distributive -Semilattice 10.5 Discussion and Perspectives References 11 Triclustering in Big Data Setting 11.1 Introduction 11.2 Prime Object-Attribute-Condition Triclustering 11.3 Triclustering Extensions 11.3.1 Multimodal Clustering 11.3.2 Many-Valued Triclustering 11.4 Implementations 11.4.1 Map-Reduce-Based Multimodal Clustering 11.4.2 Implementation Aspects and Used Technologies 11.4.3 Parallel Many-Valued Triclustering 11.5 Experiments 11.5.1 Datasets 11.5.2 Results 11.6 Experiments with Parallelisation 11.7 Conclusion References Index