Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств

• Автор: Бабин, Михаил Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 194 с. : ил.

Оглавление
Введение
1 Построение зависимостей в данных с помощью решеток замкнутых множеств основные понятия и состояние предметной области

1.1 Основные определения.

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

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

1.1.3 Теория алгоритмов и вычислительная сложность . . .

1.2 Модели зависимостей и их вычисление

1.3 Минимальная модель знаний о предметной области минимальный базис импликаций.

1.4 Задачи и алгоритмы построения гипотез .

2 Базисы импликаций и функциональных зависимостей

2.1 Квазизамкнутые множества и псевдосодержания
2.2 Структура минимальных базисов импликаций.
2.3 Функциональные зависимости и импликации
2.4 Распознавание псевдосодержаний.
2.5 Лектически максимальные исевдосодсржання и перечисление максимальных псевдосодержаний
2.6 Распознавание существенных содержаний.
2.6.1 Посылка импликации из минимального базиса
2.7 Базис импликаций с двухэлементными посылками
2.8 Приближенный базис импликаций.
2.8.1 Результаты экспериментов
3 Базисы импликаций и общие содержания
3.1 Связь базиса импликаций с общими содержаниями
3.2 Общий метод поиска минимального базиса импликаций через общие содержания.
3.2.1 Поиск собственных посылок через общие содержания
3.3 Интенсионально связанные понятия
3.4 Понятия с общими содержаниями.
3.5 Сцепления и общие содержания .
4 Обучение гипотезам
4.1 Теоретикорешеточная интерпретация гипотез и классификации .
4.2 Перечисление гипотез и дуализация монотонных булевых функций на решетках
4.3 Распределенное обучение гипотезам.
4.4 Устойчивость понятий и гипотез.
4.5 Приближенный подсчет числа замкнутых и незамкнутых множеств
4.6 Индекс вероятностной устойчивости
4.7 Анализ результатов вычислений индекса вероятностной устойчивости .
4.8 Устойчивые гипотезы Результаты экспериментов с данными
по токсичности химических соединений.
5 Комплекс программ
5.1 Программный комплекс i
5.2 Программная реализация построения базисов импликаций .
5.3 Программная реализация алгоритма вычисления оператора замыкания общих содержаний .
5.4 Программная реализация распределенного обучения гипотезам
Заключение
Литература


Ь называется подмножество X С Ь такое, что если а € Xл Ь Е Ь и Ь > а, то Ь 6 X (соответственно, а € X, 6 € Ь и Ь < а, то Ье X). Элемент 5 решётки называется иифимум-нс]тзложгшым или А-неразложимым (или порол лож ил шм в пересечение), если для любых ? Ф 5 и и ф 5, не выполняется 5 = ? А и. Элемент 5 решётки называется супремум-перазложимым или V-неразложимым (или неразложимым в объединение), если для любых иф в, не выполняется 5 = ? V и. Подмножество О полной решётки Ь называется итфимум-плотным, если Ь = {ЛХ? Определение 1 Пусть (5, <$) и (Т, В2) = (Д] П Д2, (А 1 П А2)г). Ль В) V (Л2, #2) = ((#1 П У? П ? Такие решётки называют решёткалш понятий или решётками Галуа|]. Любая полная решетка изоморфна решётке понятий некоторого формального контекста []. Л-неразложимыс элементы, а в качестве признаков — V-неразложимые элементы исходной решётки. Тогда объект д в контексте будет обладать признаком т, если элемент решётки, соответствующий д, находится “под” элементом, соответствующим т. Определение 1 Стройно- (столбцсоо-)рсдуцировапиым называется такой формальный контекст, в котором всякое объектное (признаковое) понятие является /-неразложимым (Д-нсразложимым). Редуцированным называется формальный контекст, являющийся одновременно строчно- и столбцево-редуцированным. Определение 1 Пусть дан К = (С, М,1) — формальный контекст и А. В С М , тогда выражение А —> В называется импликацией (на множествах признаков), если А' С Л' (или В С А”), т. Аналогичным образом определяются импликации на множествах объектов. Наличие импликации А —> В в контексте К соответствует тому, что в диаграмме решётки *В(Х) формальное понятие (А'. А") находится ниже формального понятия (В', В"). Помимо определённых выше однозначных (one-valued) формальных контекстов в анализе формальных понятий изучаются многозначные (many-valued) контексты:. Определение 1 Многозначный формальный контекст, сеть четвёрка (G, М, IV', . J и (д, т. Многозначные признаки могут рассматриваться как отображения G -» W, таким образом, можно обозначать т(д) = w вместо (gem,-w) е J. Процедура сведения многозначных контекстов к однозначным называется шкалированиель (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой. Определение 1 Шкала для признака т многозначного контекста (G, Л/, IV, J) есть (однозначный) контекст §m := (Gm,Mm, 1т) такой, что tn(G) С Gm. Объекты в шкале называются значениями гикали, а признаки — признаками шкалы.