Логико-вероятностный метод извлечения знаний и его применение в задачах прогнозирования и управления тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Демин, Александр Викторович

• Демин, Александр Викторович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Демин, Александр Викторович

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ ДАННЫХ.

1.2. Реляционный подход к извлечению знаний.

1.3. Постановка задачи разработки метода извлечения знаний и метода предсказания.

ГЛАВА 2. МЕТОД ИЗВЛЕЧЕНИЯ ЗНАНИЙ И МЕТОД ПРЕДСКАЗАНИЯ.

2.1. Метод извлечения знаний из данных.

2.1.1. Формализация способа задания классов гипотез.

2.1.2. Определение вероятностной закономерности.

2.1.3. Метод обнаружения вероятностных закономерностей.

2.1.4. Алгоритм поиска вероятностных закономерностей.

2.2. Метод предсказания и метод принятия решений.

2.2.1. Общая формулировка метода предсказания.

2.2.2. Метод предсказания.

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

2.2.4. Метод принятия решений.

ГЛАВА 3. СИСТАМА «DISCOVERY» И ЕЕ ПРИМЕНЕНИЯ.

3.1. Программная система «Discovery».

3.1.1. Описание системы «Discovery».

3.1.2. Технология решения задач в системе «Discovery».

3.2. Применение системы «Discovery» в медицине.

3.2.1. Проблема диагностики фолликулярной опухоли щитовидной железы.

3.2.2. Диагностика по цитологическим признакам.

3.2.3. Диагностика по УЗИ признакам.

3.2.4. Обсуждение и заключение.

3.3. Применение системы «Discovery» в финансах.

3.3.1. Разработка торговой системы.

3.3.2. Тестирование торговой системы.

3.3.3. Сравнение с другими методами.

3.3.4. Выводы.

3.4. Применение системы «Discovery» в биоинформатике.

3.4.1. Задача распознавания ССТФ.

3.4.2. Применение системы «Discovery» для распознавания ССТФ.

3.4.3. Обсуждение.

ГЛАВА 4. МОДЕЛЬ АДАПТИВНОЙ СИСТЕМЫ УПРАЛЕНИЯ.

4.1. Обзор адаптивных систем управления и проблемы их разработки.

4.2. Система управления аниматом.

4.2.1. Теория функциональных систем.

4.2.2. Архитектура системы управления.

4.2.3. Модель работы функциональной системы.

4.2.4. Схема работы системы управления.

4.2.5. Метод самообучения.

4.2.6. Метод обнаружения подцелей.

4.3. Эксперименты.

Введение диссертации (часть автореферата) на тему «Логико-вероятностный метод извлечения знаний и его применение в задачах прогнозирования и управления»

В настоящее время в различных областях человеческой деятельности накоплено множество разнообразных данных. Эти данные содержат в себе большое количество скрытых знаний в виде различного рода закономерностей и структур. Поэтому все более актуальной становиться задача корректной обработки этих данных и извлечения из них знаний. Методами обработки данных и извлечения знаний занимается интенсивно развиваемое направление Knowledge Discovery in Databases and Data Mining (KDD&DM) [1-8]. В настоящее время разработано достаточно большое количество KDD&DM методов и реализующих их программных систем. Однако существующие на данный момент KDD&DM методы обладают рядом ограничений, не позволяющих извлечь из данных знания в полном объеме. Впервые эта проблема была сформулирована на международной конференции «Philosophies and Methodologies for Knowledge Discovery» (25 августа 2005, Копенгаген) и продолжает активно обсуждаться.

В результате анализа выясняются следующие основные ограничения существующих KDD&DM методов [7-10]:

1. Информация, содержащаяся в данных, определяется множеством отношений и операций, интерпретируемых в онтологии предметной области. Каждый метод ориентирован на работу с вполне определенными типами данным и использует конкретные виды отношений и операций. Тем самым они, во-первых, не могут использовать всю информацию, содержащуюся в данных, во-вторых, могут получать результаты, не интерпретируемые в онтологии предметной области.

2. Каждый метод явно или неявно обнаруживает на данных только вполне определенные типы закономерностей.

Тем самым становится актуальной проблема разработки такого метода извлечения знаний, который обладал бы достаточно универсальностью, чтобы использовать всю информацию, содержащуюся в данных, и обнаруживать любые виды закономерностей. Задача разработки такого «универсального» метода сталкивается с необходимостью разрешения целого ряда сложных теоретических и философских вопросов, поэтому разработку такого метода целесообразно осуществлять, основываясь на некотором общем универсальном подходе к проблеме извлечения знаний. На данный момент единственным подходом, в котором в достаточно полном объеме разрешены все теоретические и философские аспекты для разработки такого метода, является реляционный подход к извлечению знаний, предложенный в работах Е.Е. Ви-тяева и Б.Я. Ковалерчука [7-13]. Данный подход использует язык логики первого порядка с вероятностной мерой для представления данных и формулировки различных видов закономерностей. В рамках реляционного подхода был разработан семантический вероятностный вывод [7-8,14-15], который следует идее семантического подхода к программированию [16], разработанного академиком Ю.Л. Ершовым, чл.-корр. С.С. Гончаровым и д.ф.-м.н. Д.И. Свириденко, и позволяет находить все закономерности заданного вида.

Идеи реляционного подхода позволяют преодолеть большинство ограничений существующих KDD&DM методов. Однако реляционный подход не был сформулирован в виде конкретного метода извлечения знаний, пригодного для практической реализации в виде программной системы. Таким образом, задача разработки «универсального» метода остается актуальной.

В данной работе предложен логико-вероятностный метод извлечения знаний, основанный на идеях реляционного подхода. Данный метод пригоден для реализации в виде программной системы и обладает достаточной универсальностью, чтобы использовать всю информацию, содержащуюся в данных, и обнаруживать любые виды закономерностей.

В настоящее время все чаще оказывается целесообразным использовать обнаруженные при помощи KDD&DM методов знания для осуществления прогноза в различных научно-прикладных задачах. Предложенный метод обладает радом преимуществ по сравнению с существующими KDD&DM методами, однако пока еще отсутствует необходимый опыт применения данного метода для решения задач прогноза. Поэтому важной задачей является разработка методов предсказания, использующих предложенный метод, и их исследование на примере решения реальных прикладных задач. В данной работе рассматривается применение разработанного метода извлечения знаний для построения прогнозирующих систем, предназначенных для решения ряда актуальных прикладных задач: 1) диагностика фолликулярного рака щитовидной железы (в медицине); 2) прогнозирования курсов ценных бумаг (в финансах); 3) распознавание сайтов связывания транскрипционных факторов (в биоинформатике).

Важным применением различных KDD&DM методов является разработка алгоритмов самообучения для адаптивных систем управления. В последнее время постоянно увеличивается число задач, для решения которых оказывается целесообразно или необходимо использовать автоматические системы управления. Постоянная тенденция к увеличению сложности и разнообразия подобных задач определяет повышенную потребность в разработке универсальных интеллектуальных систем управления, способных единообразно решать различные задачи, основываясь на общих моделях управления. Для эффективного решения широкого класса задач подобные универсальные системы управления должны уметь прогнозировать достижимость конечной цели и любых промежуточных подцелей, формировать план действий на основе полученного прогноза, и, наконец, выявлять новые подцели, если достижение этих подцелей способствует достиженшо конечной цели. Однако ни один из существующих на данный момент методов построения систем управления не обладает достаточной универсальностью и не позволяет создать систему, обладающую указанными способностями, что делает проблему разработки подобных систем управления актуальной как с практической, так и с теоретической точки зрения.

Исследование и создание универсальной интеллектуальной системы управления целесообразно проводить, отталкиваясь от общих концептуальных теорий и схем. Одной из таких общих концепций является теория функциональных систем [17-22], разработанная в 1930-70-х годах советским нейрофизиологом П.К. Анохиным. Несмотря на то, что изначально эта теория была введена для описания общей схемы управления поведением живых организмов, на ее ociioie можно предложить общую кибернетическую модель управления целенаправленным адаптивным поведением. В данной работе предлагается новая модель универсальной адаптивной системы управления, которая включает схему управления на основе теории функциональных систем, алгоритм самообучения на основе разработанного логико-вероятностного метода извлечения знаний и возможность автоматического обнаружения новых подцелей.

Целью работы является разработка логико-вероятностного метода извлечения знаний из данных и его применение для создания прогнозирующих систем и разработки модели адаптивной системы управления. Для достижения этой цели необходимо:

1. Разработать метод обнаружения на данных полного множества закономерностей для заданного класса гипотез, выраженных в языке логики первого порядка, пополненного вероятностными оценками. Для решения этой задачи необходимо: а) Разработать спецификацию фрагмента языка логики первого порядка для задачи обнаружения знаний в таблицах данных; б) Разработать интерактивный способ задания классов гипотез для рассматриваемых данных; в) Разработать алгоритм обнаружения на данных полного множества закономерностей заданного класса.

2. Разработать метод предсказания, использующий множество вероятностных закономерностей, обнаруженных на данных.

3. Разработать и реализовать программную систему, позволяющую задавать класс обнаруживаемых закономерностей, извлекать из дан ных множество закономерностей заданного класса, использовать найденные закономерности для прогноза и принятия решений.

4. Используя разработанный метод и программную систему, провести ряд вычислительных экспериментов в исследованиях, связанных с решением следующих задач: 1) диагностика фолликулярного рака щитовидной железы; 2) прогнозирование финансовых временных рядов; 3) распознавание сайтов связывания транскрипционных факторов.

5. Разработать модель адаптивной системы управления, основанной на логико-вероятностном методе извлечения знаний из данных и обладающей возможностями самообучения, формирования иерархии целей и автоматического обнаружения новых подцелей.

6. Провести ряд вычислительных экспериментов по исследованию возможностей разработанной модели адаптивной системы управления.

Методы исследования

В работе использовались аппарат и методы математической логики, теории вероятности и математической статистики. Основным методом исследования являлось представление информации, содержащейся в данных, в виде множества отношений и операций в языке логики первого порядка и разработке специальных методов вычисления и обнаружения вероятностных закономерностей, выраженных в терминах этих отношений и операций.

Разработка модели адаптивной системы управления осуществлялась путем формализации основных принципов организации и работы функциональных систем организма, изложенных в теории функциональных систем П.К. Анохина.

При проектировании и разработки программных систем использовались методы объектно-ориентированного программирования, проектирования и анализа алгоритмов и программ.

Научная новизна

Следующие результаты, полученные в данной диссертации, раскрывают научную новизну работы:

1. Разработана спецификация фрагмента языка логики первого порядка для задачи обнаружения знаний в таблицах данных.

2. Разработан способ представления классов гипотез для рассматриваемых данных, позволяющий реализовать интерактивную систему задания классов гипотез.

3. Разработан алгоритм обнаружения вероятностных закономерностей, реализующий семантический вероятностный вывод.

4. Разработан метод предсказания и принятия решений, использующий множество вероятностных закономерностей, обнаруженных на данных.

5. Разработана архитектура программной системы, реализующей предложенный метод обнаружения закономерностей.

6. Разработана новая модель адаптивной системы управления, основанной на теории функциональных систем ПК. Анохина.

7. Разработан метод самообучения системы управления, основанный на методе обнаружения по истории деятельности системы множества вероятностных закономерностей, дающих максимально вероятный прогноз достижения цели.

8. Разработан метод автоматического обнаружения новых подцелей и формирования иерархии целей.

Практическая ценность

Разработана программная система «Discovery», предназначенная для обнаружения закономерностей на данных и осуществления прогноза на основе обнаруженных закономерностей. Разработанная система была успешно применена для решения следующих задач:

1. В медицине для диагностики фолликулярного рака щитовидной железы. Автор работы вместе с д.м.н. Т.Л. Полоз и проф. В.А. Шкуру-пием являются авторами патента на изобретение № 2293524 «Способ дифференциальной диагностики фолликулярной аденомы и фолликулярного рака щитовидной железы».

2. В финансах для прогнозирования курсов ценных бумаг.

3. В биоинформатике для распознавания сайтов связывания транскрипционных факторов. Результаты работы были использован в работах по гранту РФФИ 05-07-90185в «Разработка научно-исследовательского комплекса программ "Expert Discovery" познания строения всех уровней геномной ДНК» и интеграционному проекту СО РАН № 115 «Разработка интеллектуальных информационных технологий генерации и анализа знаний для поддержки фундаментальных научных исследований в области естественных наук».

Результаты работы по разработке модели адаптивной системы управления использовались в работах по программе президента Российской Федерации поддержки научных школ 4413.2006.1.

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях: Международная конференция «Мальцевские чтения», Новосибирск, 2006 г.; Конференция-конкурс «Технологии Microsoft в теории и практике программирования», Новосибирск, 2007 г.; Всероссийская конференция с международным участием «Знания — Онтологии - Теория», Новосибирск, 2007 г.

Кроме того, полученные результаты обсуждались на семинарах в Институте систем информатики СО РАН и в Институте математики СО РАН.

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Объем работы составляет 171 страницу. Список литературы содержит 85 наименований. Работа включает 25 рисунков и графиков, полученных в результате расчетов на ЭВМ.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Демин, Александр Викторович

3.3.4. Выводы

Таким образом, эксперименты, представленные в этой главе, показывают, что логико-вероятностные методы извлечения знаний в языке логики первого порядка в состоянии обнаружить закономерности в таких сильно за-шумленных данных как финансовые временные ряды. Эти финансовые задачи уже на протяжении многих лет представляют серьезный вызов для всех KDD&DM методов.

Предложенный нами метод извлечения знаний имеет практически неограниченные возможности в формулировании и проверки различных гипотез, которые не могут быть сформулированы другими методами. Класс гипотез (15), описанный в этой главе, уже показал преимущества перед гипотезами, используемыми другими методами.

3.4. Применение системы «Discovery» в биоинформатике

3.4.1. Задача распознавания ССТФ

Исследование механизмов регуляции транскрипции генов является одной из актуальных проблем современной молекулярной биологии и биоинформатики. Обработка данных на уровне нуклеотидных последовательностей — распознавание, поиск и разметка функциональных сайтов и регуляторных районов генов представляет собой область для широкого применения различных методов анализа данных и извлечения знаний. В данной главе мы рассмотрим применение системы «Discovery» для анализа нуклеотидных последовательностей ДНК, а конкретно — для распознавания сайтов связывания транскрипционных факторов.

Для удобства дальнейшего описания введем некоторые определения и дадим краткое описание некоторых общепринятых биологических терминов.

Дезоксирибонуклеиновая кислота (ДНК) представляет собой полимерную молекулу, состоящую из повторяющихся блоков, называемых нуклеоти-дами. В ДНК встречаются четыре вида нуклеотидов: аденин, цитозин, гуанин и тимин. Согласно общепринятым буквенными кодам нуклеотидных оснований, они обозначаются соответствующими буквами: А, С, G, Т. Последовательностью нуклеотидов будем называть любое слово в алфавите элементов {A,C,G,T}; биологически оно соответствует какому-либо фрагменту генома. Последовательности нуклеотидов позволяют кодировать информацию о различных типах рибонуклеиновых кислот (РНК).

Геномом называется подцепочка ДНК, несущая какую-либо целостную информацию о строении одной молекулы белка или одной молекулы РНК. По информации, содержащейся в гене, происходит синтез матричной РНК (мРНК), которая затем используется в качестве матрицы в процессе синтеза белка. Транскрит{ией называется первый этап формирования белка по информации, содержащейся в гене. В процессе транскрипции происходит биологический синтез молекулы РНК по матрице ДНК (перенос генетической информации с ДНК на РНК). Считывание РНК с ДНК начинается с определенного места (нуклеотида) в гене, которое называется стартом транскрипции. Область выше старта транскрипции называется промотором. Промотор идентифицируется специальным ферментом, называемым РНК-полимеразой, и позволяет определить место старта транскрипции. Область ниже старта транскрипции содержит чередующиеся экзоны (области, копируемые в РНК) и интроны (области, не содержащие информации для производства белка и удаляемые из РНК в процессе т. н. сплайсинга). Завершается ген специальной последовательностью, которую называют терминатором. Промотор сверху ничем не ограничен.

Фактором называется белковая молекула, катализирующая либо инги-бирующая реакции в живых системах. Транскрипционный фактор — это белок, который, взаимодействуя с РНК-полимеразой, активирует или подавляет генную активность. Понятие активности гена тесно связано с понятием экспрессии. Экспрессией гена называется процесс реализации информации, закодированной в гене. В ряде случаев экспрессия может быть измерена экспериментально и представлена в численном виде (например, количество РНК, произведенной с данного гена за единицу времени).

Транскрипционный фактор взаимодействует с ДНК в определенных районах, которые обычно называют регуляторными. Такие районы часто лежат внутри промоторов недалеко от старта транскрипции (в пределах порядка 1000 нуклеотидов), а также непосредственно после старта транскрипции.

Непосредственное взаимодействие транскрипционного фактора с ДНК осуществляется связыванием в определенной позиции с некоторой подцепочкой регуляторного района. Такая подцепочка называется сайтом связывания транскрипционного фактора, ССТФ (transcription factor binding site, TFBS). Установлено, что определенные факторы имеют тенденцию соединяться на определенном гене с определенным сайтом. Более того, цепочки нуклеотидов сайтов в разных генах, с которыми соединяется один и тот же фактор, зачастую оказываются похожими. Если же подобной цепочки в регу-ляторной области данного гена нет, то фактор не сможет связаться с геном, и экспрессия гена окажется ниже: РНК будет хуже считываться с него или не будет считываться вообще. За счет того, что в клетках различных органов и тканей в разное время присутствуют разные наборы факторов, достигается действие различных генов в разных местах организма. Транскрипционные факторы имеют свои символьные идентификаторы, например, EGR-1, АР-1, HNF-4 и т. д. Сайт определяется подцепочкой нуклеотидов и фактором, к которому он относится.

Задача обнаружение ССТФ очень важна для понимания механизмов регуляции транскрипции генов. Однако экспериментальный поиск сайтов связывания - это достаточно трудоемкий и дорогостоящий процесс. В связи с чем становиться актуальной разработка компьютерных методов распознавания потенциальных ССТФ.

В настоящее время разработано несколько подходов к распознаванию ССТФ, к которым относятся статистические методы, марковские модели, нейронные сети и др. [64]. Однако, несмотря на разнообразие подходов, проблема распознавания ССТФ в настоящее время не может считаться окончательно решенной. Причина этого состоит в большом разнообразии контекстных, физико-химических и конформационных особенностей ССТФ; механизмов ДНК-белковых взаимодействий между ССТФ и транскрипционными факторами; специфичности контекста, окружающего ССТФ, в регуляторных районах различного типа; степени консервативности нуклеотидного контекста и др. Существенной проблемой для статистического анализа сайтов связывания также является ограниченность экспериментальных данных по ССТФ. Следствием этого является большое число ложных предсказаний, что приводит к значительным трудностям при обработке результатов поиска ССТФ в протяженных геномных последовательностях.

Традиционным методом предсказания ССТФ является позиционная весовая матрица (positional weight matrix, PWM) [65]. Метод является наиболее простым и легко интерпретируемым, и основан на предположении о независимости нуклеотидных позиций. Элементы матрицы соответствуют вероятностям наблюдения нуклеотидов в определенных позициях. Однако рад работ [66-67] указывает на то, что предположение о независимом вкладе каждой позиции в энергию связывания фактора с сайтом не соответствует сущности биологического процесса. Точность предсказания может быть увеличена за счет учета окружающего контекста, в котором встретился сайт, и учета зависимости между нуклеотидами.

В отличие от PWM система «Discovery» способна обнаружить взаимосвязь между нуклеотидами, которые, в общем случае, могут находиться на значительном удалении друг от друга. При помощи системы «Discovery» мы провели несколько экспериментов по распознаванию ССТФ для трех семейств транскрипционных факторов.

3.4.2. Применение системы «Discovery» для распознавания ССТФ

В качестве исходных данных для системы «Discovery» нами использовались нуклеотидные последовательности фиксированной длины, представляющие собой примеры сайтов связывания определенного транскрипционного фактора. Нуклеотидные последовательности были представлены в виде таблицы объект-признак, строки которой соответствовали отдельной последовательности, а столбцы — позициям иуклеотидов внутри этих последовательностей. Значения в ячейках таблицы соответствовали кодам иуклеотидов: А, С, G или Т. Для примера рассмотрим несколько последовательностей нуклеотидов сайтов связывания фактора EGR1, известных из экспериментальных данных (слева от последовательностей приведены их идентификаторы из базы данных TRRD [68]):

31916 GTCCGTGGGT

S4 809 TTGGGGGCGA

S6067 GAGGGGGCGG

S6069 GCGGGGGCGG

S5824 ACGGAGGCGG

Для решения задачи распознавания ССТФ мы использовали один предиктор PR, предсказывающий, что данная последовательность нуклеотидов является сайтом связывания рассматриваемого транскрипционного фактора. Соответствующий целевой предикат имеет вид (TFBS(s) = 1), где s — рассматриваемая последовательность нуклеотидов.

Мы использовали систему «Discovery» для поиска вероятностных закономерностей следующего вида:

PoSj^^N,)'1 &(Pos2(s) = N2)e2 &. & (Posk (s) = Nk )ек -> (TFBS(s) = 1), где (Pos,(s) = N)' - предикат, означающий, что в позиции / последовательности нуклеотидов s находится (при е = 0) или не находится (при е = 2) символ N е {А, С, G,T}; (TFBS(s) = 1) - целевой предикат, означающий, что последовательность нуклеотидов s является сайтом связывания.

Процедура принятия решения о том, является ли анализируемая последовательность нуклеотидов сайтом связывания рассматриваемого транскрипционного фактора, основана на расчете показателя согласованности прогноза предиктора PR. Система «Discoveiy» поддерживает несколько различных способов формирования прогнозов предикторов и расчета их согласованности. Для задачи распознавания ССТФ мы использовали следующий способ расчета согласованности:

Z #**)

Z PVO

Re PR где С/г(5) - согласованность прогноза для последовательности нуклеотидов 5, jPfl(s) - множество правил предиктора PR, применимых к последовательности s. Легко видеть, что данный способ принятия решения, по сути, является голосованием правил, когда голос каждого правила учитывается с весом, равным его вероятности.

На основе рассчитанного значения согласованности Ctr{s) для данной последовательности нуклеотидов s принимается решение о том, является ли она ССТФ, путем сравнения значения Ctr(s) с пороговой величиной Se[0,l]. Если значение Ctr(s) для данной последовательности больше указанного порога, значит она является сайтом связывания рассматриваемого транскрипционного фактора. Увеличение порога S ведет к тому, что для распознавания последовательности нуклеотидов в качестве ССТФ необходимо, чтобы к ней одновременно могло быть применено большее число правил, имеющих высокую вероятность. Это, в свою очередь, приводит к уменьшению числа ложных распознаваний, однако при этом также будет уменьшаться и общее число распознанных ССТФ. С дргой стороны, уменьшение порога S увеличивает число распознанных ССТФ, однако ведет и к увеличению числа ложных распознаваний. Таким образом, регулируя порог S, мы получаем возможность контролировать уровень перепредсказания (ошибка второго рода) по отношению к уровню недопредсказания (ошибка первого рода).

Мы проанализировали ДНК мишени трех семейств транскрипционных факторов: sterol regulatory element binding protein (SREBP), early growth response factor 1 (EGR1) и Hepatocyte nuclear factor 4 (HNF4). Обучающие выборки последовательностей (сайты с флангами) были извлечены из базы данных TRRD [68].

Качество распознавания сайтов связывания факторов SREBP, EGR1 и HNF4 оценивалось в сравнении с качеством распознавания метода оптимальной весовой матрицы (PWM), путем осуществления специальной процедуры скользящего контроля, известной в литературе как метод «складного ножа» (jeckknife) [69].

Суммарно, выборки данных были представлены 38 последовательностями сайта связывания SREBP , 22 последовательностями EGR1 и 30 последовательностями HNF4 (Таблица 10). Прежде всего, мы испытывали метод PWM на разной длине последовательностей, чтобы достичь наилучшей точности для PWM. Когда оптимальная длина сайтов для весовых матриц была установлена, и составила 18 нуклеотидов для данных по сайтам SREBP, 10 нуклеотидов для EGR1 и 13 нуклеотидов для HNF4, мы подготовили позитивные обучающие выборки ССТФ соответствующей длины (18, 10, и 13 нуклеотидов). Выборка контрастных последовательностей (негативная выборка) была сгенерирована случайным образом с сохранением нуклеотидных частот, как в анализируемой выборке сайтов (марковская модель нулевого порядка).

Скользящий контроль по методу «складного ножа» осуществлялся следующим образом. При каждой итерации скользящего контроля методы обучались на выборках ССТФ, оставляя ровно одну последовательность для контроля качества распознавания. Далее обученные методы (совокупность обнаруженных закономерностей системы «Discovery» и весовая матрица с фиксированными весами) применялись к контрольной последовательности, и оценивался уровень перепредсказания (ошибка второго рода) для контрольных негативных объектов (100 000 последовательностей, сгенерированных случайным образом с сохранением нуклеотидного состава). Количество итераций проводимой процедуры соответствовало объему обучающей выборки ССТФ.

Далее, по окончании скользящего контроля, мы упорядочили контрольные сайты по уровням перепредсказания. Зависимости ошибок перепредсказания от ошибок недопредсказания для HNF4, представлены на рисунке 18. Из рисунка видно, что ошибка перепредсказания, соответствующая

1.Е-02

§ g. 1,E-03 e 0

1 1,E"04 s e 1,E-05 О

1.E-06 1.E-07

0 0,2 0,4 0.6 0,8 1

Ошибка первого рода

Рисунок 18. Качество распознавания системы «Discovery» и PWM для сайтов связывания HNF4 программе «Discovery» меньше таковой для матрицы при каждом уровне ошибки недопредсказания.

ССТФ Объем выборки ССТФ Длина сайтов Ошибка второго рода

PWM Discovery

SREBP 38 18 4.70Е-04 3.90Е-04

EGR1 22 10 4.06Е-03 2.39Е-03

HNF4 30 13 2.14Е-04 7.00Е-05

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

1. Разработан метод обнаружения на данных полного множества закономерностей для заданного класса гипотез.

2. Разработан метод предсказания и принятия решений, использующий множество вероятностных закономерностей, обнаруженных на данных.

3. Разработана и реализована программная система «Discovery», позволяющая задавать вид обнаруживаемых закономерностей, извлекать из данных множество закономерностей заданного вида, использовать найденные закономерности для прогноза и принятия решений.

4. Получены положительные результаты о возможности применения разработанного метода и системы «Discovery» для решения задач: 1) диагностика фолликулярного рака щитовидной железы; 2) прогнозирования финансовых временных рядов; 3) распознавания сайтов связывания транскрипционных факторов.

5. Разработана модель адаптивной системы управления, обладающей возможностями самообучения, формирования иерархии целей и автоматического обнаружения новых подцелей. Проведены вычислительные эксперименты по исследованию возможностей разработанной системы управления и сравнению с другими подходами.

Список литературы диссертационного исследования кандидат физико-математических наук Демин, Александр Викторович, 2008 год

1. David Hand, Heikki Mannila, Padhraic Smyth. Principles of Data Mining. - The M1. Press, 2001. - p.546.

2. Hussein A. Abbass, Ruhul A. Sarker, Charles S. Newton. Data Mining: a heuristic approach. Idea Group Publishing, 2002. - p. 300.

3. Man Leung Wong, Kwong Sak Leung. Data Mining using grammar based genetic programming and applications. — Kluwer Academic Publishers, 2002. -p.213.

4. Mueller J.-A., Lemke F. Self-Organizing Data Mining. An intelligent approach to extract knowledge from data. — Berlin, Dresden, 1999. — p. 225.

5. Nong Ye. The handbook of Data Mining. — Lawrence Erlbaum Associates Publishers, 2003. -p.689.

6. Olivia Parr Rud. Data Mining Cookbook. Modeling Data for Marketing, Risk, and Customer Relationship Management. Wiley Computer Publishing, 2001.-p. 367.

7. Витяев E.E. Извлечение знаний из данных. Компьютерное познание. Модели когнитивных процессов. Новосибирск: НГУ, 2006. - 293 с.

8. Kovalerchuk В., Vityaev Е. Data Mining in Finance: Advances in Relational and Hybrid methods. Kluwer Academic Publishers, 2000. - p.308.

9. Vityaev E., Kovalerchuk B. Empirical Theories Discovery based on the Measurement Theory 11 Mind and Machine, Vol.14, N 4. 2004. - pp.551573.

10. Витяев E.E., Москвитин А.А. Введение в теорию открытий. Программная система Discovery // Логические методы в информатике. — Новосибирск, 1993. Вып. 148: Вычислительные системы. - С.117-163.

11. Kovalerchuk В., Vityaev E., Ruiz J.F. Consistent and Complete Data and "Expert" Mining in Medicine // Medical Data Mining and Knowledge Discovery. Springer, 2001. - pp. 238-280.

12. Vityaev E., Kovalerchuk B. Data Mining For Financial Applications // Data Mining and Knowledge Discovery Handbook: A Complete Guide for Practitioners and Researchers / Ed. by Maimon O., Rokach L. — Springer, 2005. -pp. 1203-1224.

13. Витяев Е.Е. Метод обнаружения закономерностей и метод предсказания // Эмпирическое предсказание и распознавание образов. — Новосибирск, 1976. Вып. 67: Вычислительные системы. — С. 54-68.

14. Goncharov S.S., Ershov Yu.L., Sviridenko D.I. Semantic programming // 10th World Congress Information Processing 86, Dublin, Oct., 1986. Amsterdam, 1986.-pp. 1093-1100.

15. Судаков K.B. Общая Теория Функциональных Систем. М.: Медицина, 1984.-222 с.

16. Анохин П.К. Принципиальные вопросы общей теории функциональных систем // Принципы системной организации функций. — М.: Наука, 1973. -С. 5-61.

17. Анохин П.К. Проблема принятия решения в психологии и физиологии // Проблемы принятия решения. — М.: Наука, 1976. — С. 7-16.

18. Анохин П.К. Принципиальные вопросы теории функциональных систем // Философские аспекты теории функциональных систем. М.: Наука, 1978.-С. 49-106.

19. Анохин П.К. Опережающее отражение действительности // Философские аспекты теории функциональных систем. М.: Наука, 1978. - С. 7165

20. Анохин U.K. Роль ориентировочно-исследовательской реакции в образовании условного рефлекса // Системные механизмы высшей нервной деятельности: Избр. тр. М.: Наука, 1979. — С. 338-352.

21. Mitchell Т. Machine Learning. McGraw-Hill, NY, 2002. - p. 432.

22. Bratko I., Muggleton S. Applications of inductive logic programming // Communications of ACM, Vol. 38, N 11. 1995. - pp. 65-70.

23. Dzeroski S. Inductive Logic Programming and Knowledge Discovery in Databases // Advances in Knowledge Discovery and Data Mining / Eds. U. Fayad U., Piatetsky-Shapiro G., Smyth P., Uthurusamy R. AAAI, MIT Press, 1996.-pp. 117-152.

24. Mitchell Т., Keller R., Kedar-Cabelli S. Explanation-based learning: A unifying view // Machine Learning, 1. 1986. - pp. 47-80.

25. Danyluk A. Finding new rules for incomplete theories: Explicit biases for induction with contextual information // Proceedings of the Sixth International Workshop on Machine Learning, Ithaca, NY: Morgan Kaufmann. 1989. -pp. 34-36.

26. Mooney R., Ourston D. Induction over the unexplained: Integrated learning of concepts with both explainable and conventional aspects // Proceedings of the Sixth International Workshop on Machine Learning, Ithaca, NY: Morgan Kaufmann. 1989. - pp. 5-7.

27. Pazzani M. Explanation-based learning with weak domain theories // Proceedings of the Sixth International Workshop on Machine Learning, Ithaca, NY: Morgan Kaufinann. 1989. - pp. 72-74.

28. Quinlan J.R. Learning logical definitions from relations // Machine Learning, 5.-1990.-pp. 239-266.

29. Muggleton S. Bayesian inductive logic programming // Proceedings of the Eleventh International Conference on Machine Learning / Eds. W. Cohen W., Hirsh H. 1994. - pp. 371-379.

30. Koller D., Pfeffer A. Learning probabilities for noisy first-order rules // Proc.of the 15th Int. Joint Conf. on Artificial Intelligence, Nagoya, Japan. — 1997. — pp. 1316-1321.

31. Fenstad J J. Representation of probabilities defined on first order languages // Sets, Models and Recursion Theory: Proceedings of the Summer School in Mathematical Logic and Tenth Logic Colloguium / Ed. Crossley J.N. 1967. -pp. 156-172.

32. Пфанцагль И. Теория измерений. М.: Мир, 1976. - 248 с.

33. Krantz D.H., Luce R.D., Suppes P., Tversky A. Foundations of measurement. -N.Y.: Acad. Press, 1971, 1989-1990-Vol. 1-3.

34. Narens L. Abstract measurement theory. — Cambridge: MIT Press, 1985. — p. 334.

35. Витяев E.E. Конструктивное числовое представление величин // Методы анализа данных. — Новосибирск, 1985. — Вып. 111: Вычислительные системы. — С. 23-32.

36. Витяев Е.Е. Обнаружение закономерностей (методология, метод, программная система SINTEZ). 1. Методология // Методологические проблемы науки. Новосибирск, 1991. - Вып. 138: Вычислительные системы. - С. 26-60.

37. Model-theoretic logics / Ed. by J. Barwise J., Feferman S. NY:Springer-Verlag, 1985.

38. Ершов Ю.Л., Палютин E.A. Математическая логика: Учеб. Пособие для вузов. 2-е изд., испр. и доп. - М.: Наука, 1987. - 336 с.

39. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. - 392 с.

40. Витяев Е.Е. Логвиненко А.Д. Обнаружение законов на эмпирических системах и тестирование систем аксиом теории измерений // Социология: методология, методы, математические модели № 10, Научный журнал РАН. 1998. - С. 97-121.

41. Кендал М., Стюарт А. Статистические выводы и связи. М.: Наука, 1973. - 899 с.

42. Дискретная математика и математические вопросы кибернетики / Под ред. Яблонского С.В., Лупанова О.Б., т. 1. — М.: Наука, 1974. — 311 с.

43. Scheffe Н., Tukey J.M. Non-parametric estimation 1. Validation of order statistics. Ann. Math. Stat., v.16, 1945. - pp. 187-192.

44. Богин Ю.Н., Бондаренко B.O., Шапиро H.A., Орлов В.М. Комплексная экспресс-диагностика заболеваний щитовидной железы // Метод, рекомендации. Москва, 1992. — 175 с.

45. Пупышева T.JI., Митерева Н.Г. Проблемы цитологической диагностики фолликулярных пролифератов щитовидной железы во время срочного интеропреационного исследования // Новости клин, цитологии России. — 2000. Т.4. - № 3-4. - С. 88-89.

46. Пупышева Т.Л. Морфометрия клеток фолликулярных пролифератов щитовидной железы в тонкоигольных аспиратах // Новости клин, цитологии России. 2002. - Т.6. - № 1-2. - С. 24-26.

47. Полоз Т.Л., Шкурупий В.А. Проблемы дифференциальной цитологической диагностики фолликулярных опухолей щитовидной железы (обзор литературы) // Сибирский Консилиум. 2006. - №3(50). — С. 15-20.

48. Kovalerchuk В., Vityaev E., Ruiz J. Consistent knowledge discovery in medical diagnosis // IEEE Engineering in Medicine and Biology Magazine (special issue "Data Mining and Knowledge Discovery"), July/August 2000. -2000. -pp.26-37.

49. Kovalerchuk В., Triantaphyllou E., Ruiz J., Torvik V., Vityaev E. The

50. Reliability Issue of Computer-Aided Breast Cancer Diagnosis // Computers and Biomedical Research, August 2000, 33(4). 2000. - pp. 296-313.

51. Ежов А., Чечеткин В. Нейронные сети в медицине // Открытые системы. 1997.-4.-С. 34-37.

52. Щетинин В.Г., Соломаха А.А. Применение искусственных нейронных сетей в клинической лабораторной диагностики // Клиническая лабораторная диагностика. М.: 1998. — 10. — С. 21-23.

53. Щетинин В.Г., Комаров В.Т. Дифференциальная диагностика при помощи искусственных нейронных сетей // Клиническая лабораторная диагностика. -М.: 1998. 11. - С. 34-37.

54. Каллан Р. Основные концепции нейронных сетей. — М.: «Вильяме», 2001.-287 с.

55. Горбань А.Н., Дунин-Барковский В.Л., Кирдин А.Н. и др. Нейроин-форматика. Новосибирск: Наука., 1998. — 296 с.

56. Бэстенс Д.Э., Ван Ден Берг В.М., Вуд Д. Нейронные сети и финансовые рынки. М.: ТВП «Научное издательство», 1997. - 236 с.

57. Ежов А.А., Шумский С.А. Нейрокомпьютинг и его применения в экономике и бизнесе. М.: МИФИ, 1998. - 224 с.

58. Vince R. The mathematics of money management. New York: John Wiley & Sons, 1992.-p. 377.

59. Андерсон Т. Статистический анализ временных рядов. — М.: Мир, 1976. 760 с.

60. Baxt W. G. Improving the accuracy of an artificial neural network using multiple differently trained networks // Neural Computation, Vol. 4. 1992. - pp. 772-780.

61. Тан A.C., Gilbert D. An empirical comparison of supervised machine learning techniques in bioinformatics // Proceedings of First Asia Pacific Bioin-formatics Conference (APBC 2003). 2003. - pp. 219-222.

62. Chen Q.K., Hertz G.Z., Stormo G.D. MATRIX SEARCH 1.0: a computer program that scans DNA sequences for transcriptional elements using a database of weight matrices // Bioinformatics. — 1995. — Vol. 11(5). — pp. 563566.

63. Benos P.V., Bulyk M.L., Stormo G.D. Additivity in protein-DNA interactions: how good an approximation is it? // Nucleic Acids Res, 30. 2002.pp. 4442-4451.

64. Barash Y., Elidan G., Friedman F., Kaplan T. Modeling dependencies in protein-DNA binding sites // RECOMB. 2003. - pp. 28-37.

65. Efron В., Gong G. A leisurely look at the bootstrap, the jackknife, and cross-validation // American Statistician, 37. 1983. - pp. 36-48.

66. Wilson S.W. The Animat Path to AI // From animals to animats: Proceedings of the First International Conference on Simulation of Adaptive Behavior. — Cambridge, MA: MIT Press, 1991. pp. 15-21.

67. Редько В.Г. От моделей поведения к искусственному интеллекту // Серия «Науки об искусственном» / под ред. Редько В.Г. М.: УРСС, 2006. -456 с.

68. Ziemke Tom. Adaptive Behavior in Autonomous Agents // Presence: Teleop-erators and Virtual Environments. Cambridge: MIT Press. — 1998. - Vol. 7(6).-pp. 564-587.

69. Maes Pattie. Modeling adaptive autonomous agents // Artificial Life. 1994. -Vol. l.-pp. 135-162.

70. Brooks R. A. A robust layered control system for a mobile robot // IEEE Transactions on Robotics and Automation. 1986. - V. 2. - pp. 14-23.

71. Brooks R.A. Intelligence without representation // Artificial Intelligence. — 1991.-V. 47. -pp.139-159.

72. Brooks, R. A. A Robot That Walks: Emergent Behavior from a Carefully

73. Evolved Network // Neural Computation. 1989. - V. 1(2). - pp. 253-262.

74. Sharkey N. E., Heemskerk J. N. H., Neary J. Training Artificial Neural Networks for Robot Control // Solving Engineering Problems with Neural Networks / Eds. by Bulsari A., Kallio S., Tsaptsinos D. 1996. - pp. 190-196.

75. Steels L. The artificial life roots of artificial intelligence // Artificial Life Journal. 1994. - V. 1. - pp. 75-100.

76. Steinhage A., Bergener T. Dynamical Systems for the Behavioral Organization of an Anthropomorphic Mobile Robot // Proceedings of the Fifth International Conference on Simulation of Adaptive Behavior. — Cambridge, MA: MIT Press, 1998.-pp. 147-152.

77. Sutton R., Barto A. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998.-p. 342.

78. Barto A., Mahadevan S. Recent advances in hierarchical reinforcement learning // Discrete event dynamic systems: theory and applications. — Kluwer Academic Publishers, 2003. pp. 41-77.

79. Holland, J.H., Holyoak K.J., Nisbett R.E., Thagard P. Induction: Processes of Inference, Learning, and Discovery. Cambridge, MA: MIT Press, 1986. -p. 416.

80. Витяев E.E. Формальная модель работы мозга, основанная на принципе предсказания // Модели когнитивных процессов. — Новосибирск, 1998. — Вып. 164: Вычислительные системы. С. 3-61.

81. Витяев Е.Е. Объяснение Теории Движений Н.А.Бернштейна // VII Всероссийская научно-техническая конференция «Нейроинформатика-2005». Сборник научных трудов. -М.: МИФИ, 2005. 4.1. - С. 234-240.р/