Машинное обучение на узорных структурах

• Автор: Самохин, Михаил Валерьевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 124 с.

Оглавление
Введение

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

1.1 Теория решток и Анализ Формальных Понятий.

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

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

1.1.3 Узорные структуры и их проекции.

1.1.3.1 Проекции узорных структур.

1.2 Машинное обучение и анализ данных.

1.2.1 Анализ Формальных Понятий и ДСМметод.

1.2.1.1 Стратегия последовательного покрытия гипотезами в ДСМметоде.

1.2.2 Метод порождения правил с исключениями. I
1.2.3 Наивный метод Байеса iv
1.2.4 Метода индуктивного порождения деревьев решений.
Ф 2 Графы и их проекции
2.1 Общий взгляд
2.2 Графы и узорные структуры.
2.3 Различные варианты проекций на графах.
3 Алгоритмическая реализация приближенного описания узорных структур
3.1 Общий взгляд
3.2 Подробное описание
3.2.1 Порождение кандидатов.
щ 3.2.2 Алгоритмы для различных вариантов проекции .
3.2.3 Использование алгоритма в ДСМметоде
3.2.4 Оценка быстродействия
4 Машинные эксперименты и результаты
4.1 Эксперименты с химическими данными.
4.1.1 Эксперименты на массиве РТС
О 4.1.2 Проекции графов на ИОСдиаграмме результаты для массива РТС
4.1.3 Эксперименты по исследованию токсичности спиртов.
4.1.4 Эксперименты по исследованию канцерогенности ариламинов
4.1.5 Эксперименты по поиску достаточных условий прохождения биотрансформации химических соединений в организме.
4.2 Анализ канцерогенности и токсичности в рамках модели структураактивность. Использование комбинированного подхода.
4.2.1 Эксперименты по хронической токсичности и канцерогенности гало
гензамещнных алифатических углеводородов ГАУ.
4.2.2 Результаты и обсуждение.
4.3 Эксперименты на массивах ПАУ
4.3.1 Результаты и обсуждение
4.3.2 Эксперимент на массиве ТЬеосНет 9.
4.4 Прогнозирование биологической активности гликозидов.
4.5 Эксперименты с графами жалоб
Заключение
Литература


Глава 4 — “Машинные эксперименты и результаты” описывает результаты применения предлагаемого подхода приближенного описания помеченных графов в серии экспериментов на реальных массивах данных — предсказание нескольких биологических активностей химических соединений д ля различных классов соединений и анализ графов жалоб. Определение 1. Множество S с определённым на нем отношением частичного порядка < (частично упорядоченное множество) обозначается (S, <). Если s < /, то говорят, что элемент s меньше чем t или равен ему. Если для s не существует /, такого что s < /, то s называют максимальным элементом 5 (относительно <). Если s < / и s Ф /, то пишут s < t и говорят, что s строго меньше чем t. Определение 1. Пусть (S, <) частично упорядоченное множество. Элемент I € S называется соседом снизу элемента и е S, если / < и и jSo € S(l < v < и). I (обозначается / ^ и). Графически, конечное частично упорядоченное множество (S, <) может быть представлено с помощью диаграммы Хассе (или просто диаграммы []). Элементы S изображаются в виде точек. Если / ^ w, то и размещается “над” / (вертикальная координата и больше вертикальной координаты /), и две точки соединяются линией. Определение 1. Верхней гранью подмножества X в упорядоченном множестве S называется элемент I е S, такой что I > х для всех х G X. А') есть верхняя грань / такая, что I <1 для любой верхней грани 1 подмножества X. Двойственным образом (с заменой > на <) определяется понятие точной (наибольшей) нижней грани или инфимума ЫХ. Определение 1. Пе = е. Для X = {х, С 5 и п є N мы пишем ПГ вместо ^ П. ГИ„. ПТ = /. Определение 1. Множество 5 с определённой на нем полурешёточной операцией П называется полу решёткой (5, П). П задает два частичных порядка С и ? С/<Ф5П/=5И/4Ф-5П/ = /. Тогда множество с определённой на нем полурешёточной операцией (5, П) будем называть нижней полу решёткой (относительно частичного порядка С) и верхней полу решёткой (относительно частичного порядка ? Определение 1. Пусть (5, П) — полурешётка. Множество С с 5 называется системой замыканий [] или семейством Мура [] (относительно П), если Ус, й є С (с П й е С). Очевидно, что система замыканий (относительно П) С с определённой на ней операцией, А:СхС->С\с/й = сГ(1, образует полурешётку. Определение 1. Упорядоченное множество (Д <) с определёнными на нем полурсшё-точными операциями А и V называется решёткой, если (/-, Л) и (/. V) являются, соответственно, нижней и верхней полурсшётками (относительно <). Операции А и V называют операциями взятия точной нижней и верхней грани в решётке или инфимума и супремума, соответственно. Определение 1. Подрешёткой решётки Ь называется подмножество X С Ь такое, что если а€Х,ЬеХ,тоаЛЬеХиа/ЬеХ. А и V удовлетворяют в решётках следующему условию: х А (х V у) — х V (х А у) = х (поглощение). Из любой конечной полурешётки можно получить решётку добавлением одного (максимального или минимального в зависимости от типа полурешетки) элемента. Определение 1. Интервал [а, Ь] состоит из всех элементов х е X которые удовлетворяют неравенствам а < х < Ь. Порядковым фильтром (идеалом) решётки ? X С Этакое, что если а е Х,Ь е ЬиЬ > а, то Ь € X (соответственно, а е X, Ь е Ь и Ь < а, то Ъ 6 X). Элемент 5 решётки называется инфимум-неразложимым или А-неразложимым (или неразложимым в пересечение), если для любых ( ^ 5 и ц / 5, не выполняется 5 = / Ли. Элемент 5 решётки называется супремум-неразложимым или V-неразложимым (или неразложимым в объединение), если для любых / ф э и и ^ 5, не выполняется я = / V и. Подмножество П полной решётки /, называется инфимум-плотным, если /, = [ЛхеХхХ С ? Ь — {ухеххХ С ? Определение 1 Пусть (5, <$) и (Т, <т) — частично упорядоченные множества. Пара отображений (р : Б Тигр :Т н-» 5 называется соответствием Галуа между частично упорядоченными множествами (5, <$) и (Г, <г). Приведённые условия эквивалентны одному: 5 <$ грЦ) / <т р(з) [—]. Определение 1 Формальный контекст К есть тройка (О, М, /), где й — множество, называемое множеством объектов, М — множество, называемое множеством признаков, I С О х М — отношение.