Об этом курсе: 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.
Для кого этот курс: 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
Автор: Национальный исследовательский университет "Высшая школа экономики"
Преподаватели: Sergei Obiedkov , Associate Professor
Faculty of computer science
| Уровень | Intermediate |
| Выполнение | 6 weeks, 4-6 hours per week |
| Язык | English |
| Как пройти курс | Чтобы пройти курс, выполните все оцениваемые задания. |
| Оценки пользователей |
Программа курса
НЕДЕЛЯ 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 видео, 1 материал для самостоятельного изучения
- Видео: Welcome to Formal Concept Analysis
- Видео: What is formal concept analysis?
- Видео: Understanding the concept lattice diagram
- Видео: Reading concepts from the lattice diagram
- Видео: Reading implications from the lattice diagram
- Reading: Further reading
- Видео: Conceptual clustering
- Видео: Formal contexts and derivation operators
- Видео: Formal concepts
- Видео: Closure operators
- Видео: Closure systems
- Видео: Software: Concept Explorer
- Видео: Many-valued contexts
- Видео: Conceptual scaling schemas
- Видео: Scaling ordinal data
Оцениваемый: Reading concept lattice diagrams
Оцениваемый: Formal concepts and closure operators
НЕДЕЛЯ 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 видео
- Видео: The partial order on concepts
- Видео: Supremum and infimum
- Видео: Lattices
- Видео: The basic theorem (I)
- Видео: The basic theorem (II)
- Видео: Line diagrams
- Видео: Context clarification and reduction
- Видео: Context reduction: an example
Оцениваемый: Supremum and infimum
Оцениваемый: Lattices and complete lattices
Оцениваемый: Clarification and reduction
НЕДЕЛЯ 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 видео
- Видео: Finding the concepts
- Видео: Drawing a concept lattice diagram
- Видео: A naive algorithm for enumerating closed sets
- Видео: Representing sets by bit vectors
- Видео: Closures in lectic order
- Видео: Next Closure through an example
- Видео: The complexity of the algorithm
- Видео: Basic incremental strategy
- Видео: An example
- Видео: The definition of implications
- Видео: Examples of attribute implications
- Видео: Implication inference
- Видео: Computing the closure under implications
Оцениваемый: Transposed context
Оцениваемый: Closures in lectic order
Оцениваемый: Implications
НЕДЕЛЯ 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 видео
- Видео: Redundancy in implications
- Видео: Pseudo-closed sets and canonical basis
- Видео: Preclosed sets
- Видео: Preclosure operator
- Видео: Computing the canonical basis
- Видео: An example
- Видео: Complexity issues
- Видео: Functional dependencies
- Видео: Translation between functional dependencies and implications
Оцениваемый: Implications and pseudo-intents
Оцениваемый: Canonical basis
Оцениваемый: Functional dependencies
НЕДЕЛЯ 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 видео
- Видео: Basic introduction to learning with queries
- Видео: Learning binary patterns
- Видео: An easy case
- Видео: The general case
- Видео: Learning implications with queries
- Видео: Membership and equivalence queries for implications
- Видео: A polynomial-time algorithm
- Видео: Learning domain implications with queries
- Видео: Attribute exploration algorithm
- Видео: Attribute exploration of pairs of squares
- Видео: Object exploration
- Видео: Variations of attribute exploration
- Видео: Incompletely specified examples
- Видео: Completing incomplete contexts
Оцениваемый: Learning with queries
Оцениваемый: Learning implications with membership and equivalence queries
Оцениваемый: Attribute exploration
НЕДЕЛЯ 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 видео
- Видео: Small changes in the context, big changes in the concept lattice
- Видео: Iceberg lattices
- Видео: Concept stability
- Видео: Separation index
- Видео: Concept probability
- Видео: Nested line diagrams
- Видео: Association rules
- Видео: Support and confidence
- Видео: Frequent closed sets
- Видео: Luxenburger basis
- Видео: Goodbye!
Оцениваемый: Concept indices
Оцениваемый: Association rules
Часто задаваемые вопросы
Как это работает
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.
Авторы
Национальный исследовательский университет "Высшая школа экономики"
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
Рейтинги и отзывы
This course is a great introduction to Formal concept analysis. You might need some knowledge of mathematics, but I think you do not need so much. If you get accustomed to the way mathematicians do, it would be very helpful.
Since there were no exercises, I treated the quiz questions as exercises. But, that meant I could not see the correct results for answers I had gotten wrong, and I could not see a correct solution (i.e., method of arriving at the correct answer). While the instructor did provide examples in each lecture, these were often much easier than the quiz questions. So, for the future, I recommend a set of exercises with worked solutions to enable the students to sharpen their skill before taking a quiz. Other than that, this was the perfect introduction to FCA for me. I noted down a few ideas I have on some of the topics and methods discussed in the course, but I haven't had time to examine these ideas in detail. Is there some way to contact the instructor later to get his reaction to these ideas?
Great Course. Explained nicely.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
The last probability excercise was tough, but worth it.
Go ahead!!