Introduction to Formal Concept Analysis

Location type
Nano fca logo
Logo Coursera
Provider rating: starstarstarstar_borderstar_border 6.3 Coursera has an average rating of 6.3 (out of 4 reviews)

Need more information? Get more details on the site of the provider.

Description

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: This course is an introduction into formal concept analysis (FCA), a mathematical theory oriented at applications in knowledge representation, knowledge acquisition, data analysis and visualization. It provides tools for understanding the data by representing it as a hierarchy of concepts or, more exactly, a concept lattice. FCA can help in processing a wide class of data types providing a framework in which various data analysis and knowledge acquisition techniques can be formulated. In this course, we focus on some of these techniques, as well as cover the theoretical foundations and algorithmic issues of FCA. Upon completion of the course, the students will be able…

Read the complete description

Frequently asked questions

There are no frequently asked questions yet.  

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: This course is an introduction into formal concept analysis (FCA), a mathematical theory oriented at applications in knowledge representation, knowledge acquisition, data analysis and visualization. It provides tools for understanding the data by representing it as a hierarchy of concepts or, more exactly, a concept lattice. FCA can help in processing a wide class of data types providing a framework in which various data analysis and knowledge acquisition techniques can be formulated. In this course, we focus on some of these techniques, as well as cover the theoretical foundations and algorithmic issues of FCA. Upon completion of the course, the students will be able to use the mathematical techniques and computational tools of formal concept analysis in their own research projects involving data processing. Among other things, the students will learn about FCA-based approaches to clustering and dependency mining. The course is self-contained, although basic knowledge of elementary set theory, propositional logic, and probability theory would help. End-of-the-week quizzes include easy questions aimed at checking basic understanding of the topic, as well as more advanced problems that may require some effort to be solved.

Who is this class for: This course will be interesting for: • Bachelor students (3rd or 4th year) • Master students • Researchers and data analysts who want to get acquainted with formal concept analysis and its potential applications

Created by:  Higher School of Economics
  • Taught by:  Sergei Obiedkov , Associate Professor

    Faculty of computer science
Level Intermediate Commitment 6 weeks, 4-6 hours per week Language English How To Pass Pass all graded assignments to complete the course. User Ratings 4.6 stars Average User Rating 4.6See what learners said Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from your peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

Higher School of Economics National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communications, IT, mathematics, engineering, and more. Learn more on www.hse.ru

Syllabus


WEEK 1


Formal concept analysis in a nutshell



This week we will learn the basic notions of formal concept analysis (FCA). We'll talk about some of its typical applications, such as conceptual clustering and search for implicational dependencies in data. We'll see a few examples of concept lattices and learn how to interpret them. The simplest data structure in formal concept analysis is the formal context. It is used to describe objects in terms of attributes they have. Derivation operators in a formal context link together object and attribute subsets; they are used to define formal concepts. They also give rise to closure operators, and we'll talk about what these are, too. We'll have a look at software called Concept Explorer, which is good for basic processing of formal contexts. We'll also talk a little bit about many-valued contexts, where attributes may have many values. Conceptual scaling is used to transform many-valued contexts into "standard", one-valued, formal contexts.


14 videos, 1 reading expand


  1. Video: Welcome to Formal Concept Analysis
  2. Video: What is formal concept analysis?
  3. Video: Understanding the concept lattice diagram
  4. Video: Reading concepts from the lattice diagram
  5. Video: Reading implications from the lattice diagram
  6. Reading: Further reading
  7. Video: Conceptual clustering
  8. Video: Formal contexts and derivation operators
  9. Video: Formal concepts
  10. Video: Closure operators
  11. Video: Closure systems
  12. Video: Software: Concept Explorer
  13. Video: Many-valued contexts
  14. Video: Conceptual scaling schemas
  15. Video: Scaling ordinal data

Graded: Reading concept lattice diagrams
Graded: Formal concepts and closure operators

WEEK 2


Concept lattices and their line diagrams



This week we'll talk about some mathematical properties of concepts. We'll define a partial order on formal concepts, that of "being less general". Ordered in this way, the concepts of a formal concept constitute a special mathematical structure, a complete lattice. We'll learn what these are, and we'll see, through the basic theorem on concept lattices, that any complete lattice can, in a certain sense, be modelled by a formal context. We'll also discuss how a formal context can be simplified without loosing the structure of its concept lattice.


8 videos expand


  1. Video: The partial order on concepts
  2. Video: Supremum and infimum
  3. Video: Lattices
  4. Video: The basic theorem (I)
  5. Video: The basic theorem (II)
  6. Video: Line diagrams
  7. Video: Context clarification and reduction
  8. Video: Context reduction: an example

Graded: Supremum and infimum
Graded: Lattices and complete lattices
Graded: Clarification and reduction

WEEK 3


Constructing concept lattices



We will consider a few algorithms that build the concept lattice of a formal context: a couple of naive approaches, which are easy to use if one wants to build the concept lattice of a small context; a more sophisticated approach, which enumerates concepts in a specific order; and an incremental strategy, which can be used to update the concept lattice when a new object is added to the context. We will also give a formal definition of implications, and we'll see how an implication can logically follow from a set of other implications.


13 videos expand


  1. Video: Finding the concepts
  2. Video: Drawing a concept lattice diagram
  3. Video: A naive algorithm for enumerating closed sets
  4. Video: Representing sets by bit vectors
  5. Video: Closures in lectic order
  6. Video: Next Closure through an example
  7. Video: The complexity of the algorithm
  8. Video: Basic incremental strategy
  9. Video: An example
  10. Video: The definition of implications
  11. Video: Examples of attribute implications
  12. Video: Implication inference
  13. Video: Computing the closure under implications

Graded: Transposed context
Graded: Closures in lectic order
Graded: Implications

WEEK 4


Implications



This week we'll continue talking about implications. We'll see that implication sets can be redundant, and we'll learn to summarise all valid implications of a formal context by its canonical (Duquenne–Guigues) basis. We'll study one concrete algorithm that computes the canonical basis, which turns out to be a modification of the Next Closure algorithm from the previous week. We'll also talk about what is known in database theory as functional dependencies, and we'll show how they are related to implications.


9 videos expand


  1. Video: Redundancy in implications
  2. Video: Pseudo-closed sets and canonical basis
  3. Video: Preclosed sets
  4. Video: Preclosure operator
  5. Video: Computing the canonical basis
  6. Video: An example
  7. Video: Complexity issues
  8. Video: Functional dependencies
  9. Video: Translation between functional dependencies and implications

Graded: Implications and pseudo-intents
Graded: Canonical basis
Graded: Functional dependencies

WEEK 5


Interactive algorithms for learning implications



What if we don't have a direct access to a formal context, but still want to compute its concept lattice and its implicational theory? This can be done if there is a domain expert (or an oracle) willing to answer our queries about the domain. We'll study an approach known as learning with queries that addresses this setting. We'll get to know a few standard types of queries, and we'll see how an implication set can be learnt in time polynomial of its size with so called membership and equivalence queries. We'll then introduce attribute exploration, a method from formal concept analysis, which may require exponential time, but which uses different queries, more suitable for building implicational theories and representative samples of subject domains.


14 videos expand


  1. Video: Basic introduction to learning with queries
  2. Video: Learning binary patterns
  3. Video: An easy case
  4. Video: The general case
  5. Video: Learning implications with queries
  6. Video: Membership and equivalence queries for implications
  7. Video: A polynomial-time algorithm
  8. Video: Learning domain implications with queries
  9. Video: Attribute exploration algorithm
  10. Video: Attribute exploration of pairs of squares
  11. Video: Object exploration
  12. Video: Variations of attribute exploration
  13. Video: Incompletely specified examples
  14. Video: Completing incomplete contexts

Graded: Learning with queries
Graded: Learning implications with membership and equivalence queries
Graded: Attribute exploration

WEEK 6


Working with real data



A concept lattice can be exponentially large in the size of its formal context. Sometimes this can be due to noise in data. We'll study a few heuristics to filter out noisy concepts or select the most interesting concepts in a large lattice built from real data: stability and separation indices, concept probability, iceberg lattices. We will also talk about association rules, which is a name for implications that are supported by strong evidence, but may still have counterexamples in data.


11 videos expand


  1. Video: Small changes in the context, big changes in the concept lattice
  2. Video: Iceberg lattices
  3. Video: Concept stability
  4. Video: Separation index
  5. Video: Concept probability
  6. Video: Nested line diagrams
  7. Video: Association rules
  8. Video: Support and confidence
  9. Video: Frequent closed sets
  10. Video: Luxenburger basis
  11. Video: Goodbye!

Graded: Concept indices
Graded: Association rules
There are no reviews yet.

Share your review

Do you have a learning experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate $1.- to Stichting Edukans.

There are no frequently asked questions yet.