Алгоритмы и методы теории решеток и их применение в машинном обучении

• Автор: Объедков, Сергей Александрович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 157 с. : ил

ОГЛАВЛЕНИЕ
Введение

Глава 1 Теория решеток п анализ формальных понятии.

1.1 Частично упорядоченные множества и решетки

1.2 Операторы замыкания

1.3 Операторы замыкания и системы замыкания в полурешетке

1.4 Импликации.

1.5 Анализ формальных понятии

Глава 2 Решетки формальных понятии в автоматическом порождении гипотез

2.1 Импликации и ассоциативные правила.

2.2 ДСМметол

2.2.1 ДСМметод в терминах анализа формальных понятии Основные определения
2.2.2 О пользе итераций
2.2.3 Варианты ДСМшиотез
Глава 3 Алгоритмы построения решеток формальных понятий и их применение для порождения гипотез.
3.1 О принципах сравнения
3.2 Обзор алгоритмов.
3.2.1 Борда
3.2.2 Следующее замыкание
3.2.3 Замыкан по одному
3.2.4 Лнпаиг.
3.2.5 Шен
3.2.6 Нурпн
3.2.7 Норрис.
3.2.8 Голан
3.2.9 Добавь атом
3.2. Другие алгоритмы.
3.3 Эксперименты
3.4 Алгоритмы порождения понятий в машинном обучении
Глава 4 Алгоритмы построения базиса импликаций.
4.1 Алгоритм Гантера вычисления базиса ДюкениаГига.
4. 2 Пошаговый алгоритм вычисления базиса Дюксииа1 ига.
4.2.1 Тины импликаций.
4.2.2 Описание алгоритма
4.2.3 Экспериментальное сравнение.
Глава 5 Рассуждение в условиях частичной информации Неполные контексты
5.1. Постановка задачи
5.2 Оценка формул с помощью логики Клнии
5.3 Модальная дошка для неполных контекстов.
5.3.1 Модальная логика бессмыслицы
5.3.2. Применение модальной логики бессмыслицы для оценки формул в неполных контекстах
Заключение
Литература


Приведенные условия эквивалентны одному: s t <т х П /, = х = х П Д О (х П /,) П (х П Д) = х О х П (/, П Д) = х <=> х ? П Д. Следспше. Для любых х, /„ Д є У: /, 3 х & Д 3 х <4 /, П/, Э х. Будем говорить, что множество с определенной на нем полурешеточной операцией (X, П) является нижней полурешеткон (относительно частичного порядка ? Заметим, что ПТ есть точная нижняя грань множества Т относительно часпгчного порядка ? Т относительно 3. Таким образом, но частичному порядку ? Э) можно однозначно восстановить операцию П, задающую этот порядок, при условии, что такую операцию, вообще, можно определить: і П / вычисляет точную нижнюю грань {х, /} в (Д ? Собственно, миопге авторы опрелс. Говорят также о полных нижних {верхних) полурешетких,, в которых любое подмножество элементов имеет точную нижнюю (верхнюю) грань. В случае конечного множества Я, эти любая решетка является полной. Определение 1 Множество с определенными на нем полурешеточпымн операциями (З*, л, V) называется решеткой (относительно частичного порядка <Г), если (3', л) и (3, V) яв. ШІЖНСП н верхней полурешеткамп (отпоептельно <; т. Операции л н V называют операциями взятия соответственно точной нижней и верхней грани в решетке. Элемент з решетки называется л-неразложимым, если для любых / Ф / н и Ф г, не выполняегся . V //. Утверждение 1 Если (3', л, V) — решетка, то $ V / = л {// | / и & / <л //}. Доказательство. V і < л{? Л //}. Т<л 5 V /, /<л Т V /=> л{// | . Г<л //& /<л //} <л ^ V /. Из любой полурешеткн можно полнить решетку добавлением одного (максимального) элемента. Пусть (. П) — полурсіпеткл; Еа| = Є и {і*, х 1), где 3*, = 3* ^ {1} для некоторого элемента 1. Распространим операцию П на 3 естественным образом, обозначив ее П,: г П, 1 = 5. П,{// ) 5? Утверждение 1 Если (З, П) — полурешетка, то (3„ и,) — тоже. Доказательство. БЬ2) . Ы, / = П,{# | /? П,{// | /? I) и, // = Пі{г> І х и! Е, />& // Е, і) = П,{г | х и, / Е, //& // Е, /-} = П,{г> | . Е,*} = п,{у І /Є^Л/и^С,! Легко убедиться, что (3*,, и,) является верхней полурешеткоїг относительно часітічного порядка Е,. Утверждение 1 Если (З*, П) — полурешепса (относіггельно Е), то (З*,, П,, ,) — решетка (относительно Е^. Определенно 1 Пусть (З*, <) — частично упорядоченное множество. Отображение а. СІ) х<, і-=? СЗ) о[о{х)) — о(х) (ндемпотенпюсгь). Мы будем иногда опускать скобки между оператором замыкания и его аргументом. Определение 1 Для частично упорядоченного множества (. Г, <) и оператора замыкания <Т. S, элемент х є 3 называется замкнутым {относительно о), если ах — х. Множество {сух | х є ? Оператор замыкания определяет разбиение 5 на классы эквивалентности — классы замыкания. I е 3, таких что сг/ = ах.