Введение
1. Введение 4
1.1. Теория упорядоченных множеств и теория решеток 8
1.2. Анализ формальных понятий (АФП) 10
1.3. Машинное обучение 13
1.4. ДСМ-метод 17
1.5. Теория алгоритмической сложности 20
2. Гипотезы и классификации: теоретико- решеточная и теоретико-графовая интерпретации, связь с родственными понятиями 27
2.1. Основные определения: гипотезы и классификации 27
2.2. Теоретико-решеточная интерпретация гипотез и классификаций 34
2.3. Теоретико-графовая интерпретация гипотез 37
2.4. Теоретико-графовая интерпретация классификаций — 41
2.5. Гипотезы и родственные понятия из анализа данных и искусственного интеллекта 44
2.5.1. Гипотезы и импликации в АФП 45
2.5.2. Импликации и зависимости в реляционных базах данных 47
2.5.3. Пространство версий между минимальными гипотезами и минимальными посылками 49
2.5.4. Гипотезы, решетки понятий и деревья решений 54
3. Алгоритмические проблемы порождения понятий, гипотез и классификаций 58
3.1. Число всех формальных понятий 58
3.2. Число минимальных гипотез 60
3.3. Задачи распознавания для понятий с ограничениями на размер 61
3.4. Задачи распознавания для гипотез с ограничениями на размер 68
3.5. Сложность классификации и проверки критерия достаточного основания 73
3.6. Алгоритмы порождения формальных понятий,
решеток понятий, гипотез и классификаций 78
3.6.1. Алгоритм Замыкай-по-Одному 78
3.6.2. Алгоритм порождения решетки понятий 82
3.6.3. Алгоритмы порождения гипотез и минимальных гипотез 87
3.6.4. Пошаговый алгоритм для вычисления минимальных гипотез 89
3.6.5. Вычисление классификаций и проверка критерия достаточного основания 92
3.6.6. Вычисление предгипотез и обобщенных гипотез 93
4. Устойчивость формальных понятий и гипотез 95
4.1. Мотивация и прецеденты 95
4.2. Индексы устойчивости: определения и основные свойства 96
4.3. Изменение устойчивости с ростом числа примеров 99
4.4. Алгоритмическая сложность вычисления индексов устойчивости 105
4.5. Алгоритм с полиномиальной задержкой для вычисления индексов устойчивости 108
4.6. Приближенное вычисление индексов устойчивости 110
5. Узорные структуры и их проекции 117
5.1. Узорные структуры: определение и связь с формальными контекстами 117
5.2. Вычисления в узорных структурах 120
5.3. Проекции узорных структур 121
5.4. Порождение гипотез в проекциях 124
5.5. Приложения в области графов 128
6. Заключение 133
7. Список литературы
