автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Логико-вероятностный метод извлечения знаний и его применение в задачах прогнозирования и управления

Российская Академия Наук Сибирское Отделение Институт Систем Информатики

На правах рукописи —

ДЕМИН Александр Викторович

ЛОГИКО-ВЕРОЯТНОСТНЫЙ МЕТОД ИЗВЛЕЧЕНИЯ ЗНАНИЙ И ЕГО ПРИМЕНЕНИЕ ВЗАДАЧАХ ПРОГНОЗИРОВАНИЯ И УПРАВЛЕНИЯ

Специальность 05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико - математических наук

Новосибирск 2008

003458205

Работа выполнена в Институте Систем Информатики имени А.П. Ершова СО РАН

Научные руководители: Марчук Александр Гурьевич,

доктор физико-математических наук, профессор

Витяев Евгений Евгеньевич, доктор физико-математических наук

Официальные оппоненты: Загоруйко Николай Григорьевич,

доктор технических наук, профессор

Васючкова Татьяна Сергеевна, кандидат физико-математических наук, доцент

Ведущая организация: Институт автоматики и процессов

управления ДВО РАН

Защита состоится 26 декабря 2008 г. в 15 ч 00 мин на заседании диссертационного совета К003.032.01 в Институте систем информатики имени А. П. Ершова Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ИСИ СО РАН (пр. Лаврентьева, 6)

Автореферат разослан 24 ноября 2008 г.

Ученый секретарь

диссертационного совета КООЗ .032.01, п

к.ф.-м.н. 1^4 Мурзин Ф.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Тем самым становится актуальной проблема разработки такого метода извлечения знаний, который обладал бы достаточно универсальностью, чтобы использовать всю информацию, содержащуюся в данных, и обнаруживать любые виды закономерностей. Разработку такого метода целесообразно осуществлять, основываясь на некотором общем универсальном подходе к проблеме извлечения знаний. На данный момент единственным подходом, в котором в достаточно полном объеме разрешены все теоретические и философские аспекты для разработки такого метода, является реляционный подход к извлечению знаний, предложенный в работах Е.Е. Ви-тяева и Б.Я. Ковалерчука. Данный подход использует язык логики первого порядка с вероятностной мерой для представления данных и формулировки различных видов закономерностей. Идеи реляционного подхода позволяют преодолеть большинство ограничений существующих KDD&DM методов. Однако реляционный подход не был сформулирован в виде конкретного метода извлечения знаний, пригодного для практической реализации в виде программной системы. Таким образом, задача разработки «универсального» метода остается актуальной.

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

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

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

В последнее время КХЮ&ОМ методы активно используются в алгоритмах самообучения адаптивных систем управления. Однако анализ показывает, что в сложившихся условиях постоянной тенденции к увеличению сложности и разнообразия задач управления, существующие подходы к построению адаптивных систем управления уже не способны обеспечить необходимый уровень управления и адаптации. Становится актуальной задача разработки универсальной системы управления, основанной на некоторых общих универсальных принципах управления и адаптации.

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

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

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

а) разработать спецификацию фрагмента языка логики первого порядка для задачи обнаружения знаний в таблицах данных;

б) разработать интерактивный способ задания классов гипотез для рассматриваемых данных;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях: Меж-

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

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

Публикации. По материалам диссертации опубликовано 20 печатных работ, среди которых 10 статей в периодических изданиях и журналах, 3 статьи в трудах конференций, 6 тезисов докладов научных конференций, 1 патент на изобретение.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Раздел 2.1 посвящен описанию логико-вероятностного метода извлечения знаний.

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

Предполагается, что исходные данные представлены в виде таблицы значений D, строки которой соответствуют объектам, а колонки - признакам объектов.

Зафиксируем фрагмент многосортного языка логики первого порядка с сигнатурой = (S,P,F), где

• ^И«.*'5«' - множество сортов, scbt - сорт объектов таблицы D, -сорт действительных чисел;

• Р — множество предикатных символов, все аргументы которых имеют сорт ;

• F= F,kjF2kjF3 - множество функциональных символов, где

F, — множество функциональных символов, аргументы которых имеют сорт s^j или , а значения - сорт sotJ;

F2 — множество функциональных символов, таких, что все символы из F\ одноместные, их аргументы сорта salj, а значения - сорта sx. F, — множество функциональных символов, аргументы и значения которых имеют сорт sR;

Введем многосортную алгебраическую систему /=((йД)д) сигнатуры £', где D - таблица данных, являющаяся носителем сорта s„4/, R -множество действительных чисел, являющееся носителем сорта sR, я - интерпретация сигнатуры £* на {ОД}.

Введем понятия шаблона термов и шаблона предикатов.

Шаблон термов - это пара Tf = (/,{¥,,...,Ч/„}), где /ef„ и - арность символа /, ^¥, = {1,.....r„ }, i = l,...,n, tt(k = l,...,m,)-терм сорта sR языка первого порядка, такой, что любая переменная, входящая в терм tk имеет сорт

soV. Шаблон терма Tf = {/,{Ч'/.....VP„}) определяет множество всех термов

вида /(<,,...,/„)> гДе '/ еЧ/и ' = 1.....п ■ Будем обозначать через [Tf] - множество термов, определяемое шаблоном Tf.

Шаблон предикатов - это пара Тр = (Р,{©,,...,©„}), где РеР, п — арность символа Р, 0, ={7у„...,7/"„}, i = l,...,n, Tfi(k = l,...,ml) - некоторый шаблон терма. Шаблон предиката Тр = [Р,{0,,.,0„}) определяет множество

всех атомарных формул вида P(t,,...,tm), где e[7y,]u...u[7£,(], i = l.....п,

TfkeOn k = l,...,ml. Будем обозначать через [Тр] - множество атомарных формул, определяемых шаблоном Тр.

Теперь, используя понятие шаблона предикатов, мы можем определить понятие класса гипотез.

Класс гипотез - это пара Th = ({Tp......Трт},Р,;*), где Тр, - шаблоны предикатов, Р,' - целевая литера, Р„ - атомарная формула, е е {0,1} - обозначает наличие отрицания формулы.

Класс гипотез Th = ({Tp,,...,Tpm),p;} определяет множество правил вида

->/»,'), к>0 (1) где 1,, -Л -переменные сорта е[7р,]ы...и[7>„], 1 = 7,...,л.

Формулы вида (1) будем записывать в более удобном виде

А,&...&АП ->А„ А, = /»,*,/ = 0.....и, (2)

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

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

В разделе 2.1.2 вводяться понятия эксперимента, вероятности на множестве экспериментов и вероятностной закономерности.

Подправилом правила Л, = А, &....&. Ат -> А, будем называть любое правило Д., =Л,,&...&/!,» ->А> такое что (А,,.....Ал}<= {А,,...,АЯ}.

Вероятностной закономерностью называется правило А, &...&Ат -> А,, удовлетворяющее следующим условиям:

1. условная вероятность правила определена, т.е. р{А,&...&Ат)>0;

2. условная вероятность правила строго больше условных вероятностей

каждого из его подправил.

Сильнейшей вероятностной закономерностью называется вероятностная закономерность, которая не является подправилом никакой другой вероятностной закономерности.

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

В разделе 2.1.4 приводится алгоритм поиска вероятностных закономерностей. Предложенный алгоритм основан на семантическом вероятностном выводе, который был определен в работах Е.Е. Витяева в рамках реляционного подхода к извлечению знаний.

Семантическим вероятностным выводом (СВВ) некоторой сильнейшей вероятностной закономерности Д„ называется такая последовательность вероятностных закономерностей Л„, Л, = А,&...&Ак ->А„, ¡ = 1,2,...,п,п> 1, что правило Л, является подправилом правила р(К„1)>р(Я1),1 = 1,2,...,п-1.

В работе выводится, что для нахождения множества всех закономерностей Reg(Th), которые могут быть получены на основе класса гипотез 77», достаточно обнаружить множество базовых закономерностей Вахе(П) с Reg(Th). Все остальные закономерности могут быть найдены путем последовательного уточнения всех базовых закономерностей с проверкой выполнимости условий для вероятностных закономерностей. Основы-

ваясь на данном свойстве, в работе был предложен алгоритм направленного перебора правил вида (2), позволяющий обнаружить множество Reg(Th).

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

В разделе 2.2.1 приводится общая формулировка метода предсказания. Пусть Reg(Th) - множество закономерностей, найденное алгоритмом поиска закономерностей на основе заданного класса гипотез ГА = {{Tp„...,TpJ,p;). Пусть P(Th) = [Tp,}u...^[TpJ.

Пусть нам дано множество объектов D и некоторый новый объект Ь. Предположим, что значения части атомарных формул Р" <= P(Th) на объектах D и Ь нам известны. Требуется, используя закономерности из Reg(Th), по известным значениям атомарных формул из Р" предсказать неизвестные значения остальных атомарных формул из Рп = P(Th)\Ри. Таким образом, задача предсказания сводится к тому, чтобы по модели ргв ={p,P(Th)) и модели рт" =(Ви6,Р") восстановить модель pr = {Hub,P(T/t)).

Методом предсказания называется алгоритм

АР:(Reg(Th),pr„pr") —> v, преобразующий каждую тройку (Reg(Th),prt,pr

в частично определенное отображение у: PS -»[0,1], сопоставляющее каждой модели рт е PS некоторую оценку её вероятности v(pr). Где PS - множество всех возможных восстановлений модели рг = {Ш^Ь,Р(ТН)).

В разделе 2.2.2 описывается способ определения метода предсказания в общем случае. Все закономерности из Reg(Th) можно разбить на три группы: 1) Reg, - множество закономерностей, которые содержат только одну индивидную константу; 2) Reg, - множество закономерностей, заключение которых содержит только одну индивидную константу, а посылка содержит по крайней мере две различные индивидные константы; 3) Reg, - множество закономерностей, у которых в заключении есть хотя бы две различные индивидные константы. Reg(TK) = Reg, u Reg, и Reg,, Reg, n Reg, = 0, i* j.

Для каждой группы закономерностей Reg,, Reg2 и Reg3 в работе предложены способы определения прогнозов для их закономерностей.

Чтобы оценить вероятность v(pr) некоторой модели pre PS, метод прогноза должен основываться на прогнозах всех закономерностей из Reg{TK). Таким образом, для построения метода предсказания необходимо задать частично определенную функцию X\{{pr,Reg{pr)))->[0,1], которая для каждой модели pr € PS на основании множества закономерностей Reg(pr) е Reg(Th), предсказывающих данную модель, вычисляет оценку вероятности v(pr). Тогда v(pr) = X({pr,Reg(pr))).

В работе приводится несколько примеров задания функции Л.

В разделе 2.2.3 рассматривается метод предсказания, основанный на оценке максимальной вероятности. Для всех трех видов закономерностей Reg,, Reg, и Reg, подсчитываются вероятностные оценки, необходимые для получения предсказаний. Полученные оценки затем используются для определения итоговой оценки вероятности v(pr). В работе приводятся доказательства ряда утверждений, позволяющих установить отображение v и получить оценки вероятности для итогового предсказания v(pr).

В разделе 2.2.4 описывается общий механизм принятия решений на основе предсказания. Пусть нам известно множество вариантов решений S = {s,.....s„}, и для каждого решения sei можно указать множество моделей PS(s) с PS, для которых должно быть выбрано данное решение. Будем называть множества PS(st), i = l.....п вариантами исхода.

Для построения метода принятия решений, необходимо задать функцию оценки вероятностей исходов k:{PS(s,),...,PS(s.)} -+[0,1], которая для любого исхода PS(s) с PS вычисляет результирующую оценку вероятности данного исхода, основываясь на оценках v(pr) всех моделей prePS(s), входящих в этот исход PS(s). В работе приводится несколько примеров определения функции .

Методом принятия решений называется функция Dec: {{k(PS(s,)),...,k(PS(s,)))} которая для каждого набора оценок

вероятностей исходов (k(PS(Sj)),...,k:(PS(sm))) возвращает один выбранный вариант решения s е S либо 0, если решение не может быть принято.

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

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

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

Раздел 3.2 описывает применение системы «Discovery» для решения задачи диагностики фолликулярной опухоли щитовидной железы. Совершенствование дооперационной диагностики фолликулярной аденомы и рака является актуальной задачей, поскольку, как показывает опыт, в настоящее время совпадение цитологических и окончательных гистологических диагнозов не превышает 56%. Помимо повышения точности цитологической диагностики, особый интерес также вызывает предварительная диагностика заболевания по данным УЗИ обследования. При помощи системы «Discovery» мы провели два исследования возможности диагностики фолликуляр-

ной опухоли, основанные на использовании данных цитологического анализа и данных УЗИ обследования.

Исходными данными для первого исследования послужили цитологические препараты 197 больных (86 раков и 111 аденом), которые были проанализированы по 30 цитологическим признакам. Во втором исследовании были использованы данные об УЗИ обследовании 170 больных (70 раков и 100 аденом), которые были проанализированы по 9 УЗИ признакам.

В обоих исследованиях тестирование системы методом скользящего контроля показало, что обнаруженные системой правила позволяют осуществлять диагностику с точностью до 96 %. Мы провели сравнение точности прогнозов системы «Discovery» с прогнозами, полученными при помощи нейронной сети. На скользящем контроле нейронная сеть показала точность, равную 91% на цитологических данных и 86% - на данных УЗИ. Таким образом, система «Discovery» показала более высокую точность прогнозов, чем нейронные сети.

В разделе 3.3 описывается применение системы «Discovery» для прогнозирования финансовых временных рядов. В данном исследовании рассмотрено применение системы «Discovery» для разработки торговой системы, основанной на предсказании увеличения или уменьшения котировок индекса S&P500 через пять дней по отношению к текущей цене.

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

Vtßt2,...,tm : {ext{t„...,tj =<8,,...,8„ >)&(с(/,) <c(/y))&...&(c(/t) < <■(/,)) Т, где i,j,k,le {/,...,«}, t, >... > tK, c(tj) - значение временного ряда в точке ti

Предикат ext(t„...,tm)=<8„...,8m>, öt е {-/; /}, / = /,...,/я определяет условие, проверяющее, являются ли точки tn i = l,...,m локальными минимумами (при 8, =-1) или локальным максимумами (при 8i = 1).

Т - целевой предикат, Т = (c(t,) < c(t, + 5)) или Т = (c(t,) > c(t, + 5)).

Данные гипотезы проверяют, сформировалась ли в прошлом временного ряда определенная фигура из локальных минимумов и максимумов, и если такая фигура найдена, делают прогноз на пять дней вперед.

Тестирование разработанной нами торговой системы осуществлялось методом скользящего контроля на временном интервале из 2065 торговых дней. Чтобы оценить эффективность работы системы «Discovery», мы также провели сравнение данной системы с методом скользящей линейной регрессии и комитетом нейронных сетей. В результате тестирования система «Discovery» показала лучшие результаты как по проценту правильных прогнозов, так и по показателям финансовой эффективности. Процент прибыльных сделок у системы «Discovery» достигает 69% по сравнению с 57% у нейронных сетей и 41% у линейной регрессии.

В разделе 3.4 описывается применение системы «Discovery» в биоинформатике для распознавания сайтов связывания транскрипционных факто-

ров (ССТФ). Задача обнаружения ССТФ очень важна для понимания механизмов регуляции транскрипции генов. Традиционным методом предсказания ССТФ является позиционная весовая матрица (PWM), основанная на предположении о независимости нуклеотидных позиций. Однако точность предсказания может быть увеличена за счет учета взаимосвязи между нук-леотидами. При помощи системы «Discovery» мы исследовали три семейства транскрипционных факторов: SREBP, EOR1 и HNF4.

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

(Pos,(s) = А',)"&.(Pos,(s) = N3)" 8i...&.(Post(s) = ЛГ,)" -» (TFBS(s) = 1), где (Pos,(s) = N)' - предикат, означающий, что в позиции / последовательности нуклеотидов s находиться (при е = 0) или не находиться (при е = 1) символ /V е\ A,C,GJ\; (TFliS(s) = i) - целевой предикат, означающий, что последовательность нуклеотидов s является сайтом связывания.

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

В четвертой главе описывается разработанная модель адаптивной системы управления.

В разделе 4.1 представлен обзор существующих подходов и проблем построения адаптивных систем управления. Представлен анализ существующих в рамках направления исследований «Адаптивное поведение» подходов к построению систем управления с точки зрения возможности организации самообучения и адаптации.

В разделе 4.2 приведено описание разработанной модели адаптивной системы управления аниматом (искусственным организмом).

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

В разделе 4.2.2 описывается общая архитектура системы управления. Предполагается, что анимат имеет некоторый набор сенсоров

5 = {5,,5'J.....SJ и набор возможных действий А =-{А,,А2,...,Ат}. Информации

06 окружающей среде подается в систему управления в виде набора сенсорных предикатов Р = {Р,,Р!,...,Рк), описывающих текущее состояние сенсоров.

Архитектура системы управления представляет собой иерархию функциональных систем, при которой функциональные системы верхнего

уровня ставят цели системам нижнего уровня. Отдельная функциональная система ФС определяется следующим набором: ФС =< РО,С,РЯ >.

РО - предикат-цель, описывающий цель, достижение которой является задачей данной функциональной системы, РС = Р,&Р1&...&Р1, /> е Р.

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

РЯ - множество закономерностей, принадлежащих данной функциональной системе и имеющих вид:

Р,&...&Р.&Рв,&...&РС„&А,&...&Ак ->Рв, (3)

где Р, е Р, РС1 е С, А, е А. Эти закономерности предсказывают, что если из ситуации Р„...,Р, достичь цели />С,,..., РСт, и затем выполнить действия А,,...,А,, то с некоторой вероятностью р будет достигнута цель РО.

В разделе 4.2.3 описывается работа отдельной функциональной системы. Задачей каждой функциональной системы ФС =<РС,С, РЯ> является нахождение наиболее оптимального способа достижения цели РС. Для этого анализируется множество закономерностей РЯ и для каждой закономерности Я = Р,&...&Р11&РС1&...&РСа&А,&...&АЛ-+РС, применимой в текущей ситуации, рассчитывается оценка вероятности достижения цели /(Л) по формуле: /(Я) = р(Я) /(РС,) /(РС!\РС,):.,/(РСт\РСт_,), где ДРС,,) -оценка вероятности достижения подцели РС, из текущей ситуации; /(.РС,\РС,_,) - оценка вероятности достижения подцели РС. после достижения подцели Рв,_,. Расчет оценок /(РО,) ,/(РС, | РО,),...,/(РОт ¡РСт ,) осуществляется аналогичным образом путем отправки запросов соответствующим функциональным системам. На основании полученных оценок выбирается закономерность Яка, имеющая максимальную оценку вероятности, которая и будет определять оптимальные действия по достижению цели.

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

В разделе 4.2.5 описывается метод самообучения системы управления, который позволяет для каждой функциональной системы ФС=< РС,&,РЯ > обнаруживать множество закономерностей РЯ на множестве данных истории деятельности анимата. Метод самообучения основан на адаптированном варианте разработанного логико-вероятностного метода обнаружения закономерностей, учитывающего специфику правил вида (3).

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

Для выявления подцелей у каждой функциональной системы ФС -< PG,G,PR> анализируется множество ее правил PR. Если ситуация, описываемая предикатом PGHtw = Р, &...&Р„, Р,<= Р удовлетворяет определенным условиям, то она будет являться подцелью и для нее создается новая функциональная система ФСКт, находящаяся ниже по иерархии системы ФС и реализующая достижение этой подцели.

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

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

В первом эксперименте агент, двигаясь по плоскости, должен был научиться эффективно собирать пищевые объекты. Результаты первого эксперимента показали, что все системы управления способны научиться решать классическую задачу фуражирования. Однако предложенная система обучается значительно быстрее (примерно в 12 раз).

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

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

В заключении приведены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССРЕТАЦИИ

1. Витяев Е.Е., Ковалерчук Б.К., Федотов A.M., Барахнин В.Б., Белов С.Д., Дурдин Д.С., Демин A.B. Обнаружение закономерностей и распознавание аномальных событий в потоке данных сетевого трафика // Вестник НГУ, серия: Информационные технологии. - 2008. - Т. 6. - Вып. 2. - С. 57-68.

2. Khomicheva I.V., Demin A.V., Vityaev Е.Е. Transcription Factor Binding Site Discovery by the Probabilistic Rules. Proceedings of the 2nd workshop in data mining in functional genomics and proteomics. The 18th European conference on machine learning and the 11th European conference on principles and practice of knowledge discovery in databases. Warsaw, Poland, September 17-21,2007.-2007.-p.104-109.

3. Демин A.B., Витяев E.E., Полоз Т.Л., Реализация универсальной системы извлечения знаний «Discovery» и ее применение в задачах медицинской диагностики // Труды Всероссийская конференция с международным участием «Знания - Онтологии - Теории». - Новосибирск, 2007. - Т. 1. -С. 63-70.

4. Демин A.B., Реализация универсальной версии системы «DISCOVERY» // Тез. докл. конференции-конкурса «Технологии Microsoft в теории и практике программирования», Новосибирск, 24-26 февраля 2007. - 2007.

-С. 106-108.

5. Dcmin А.V., Vityaev E.E., Animât control system based on semantic probabilistic inference // Bull. Nov. Comp. Center, Computer Science, 24 (2006). -NCC Publisher, 2006. - p. 57-72.

6. Демин A.B., Витяев E.E., Разработка модели адаптивного поведения анимата на основе семантического вероятностного вывода // Молодая информатика. - Новосибирск, 2006. - Выпуск 2. - С. 121-133.

7. Демин A.B., Витяев Е.Е. Реализация модели анимата на основе семантического вероятностного вывода // VIII Всероссийская научно-техническая конференция «Нейроинформатика-2006». - Москва, 2006. -Т. 2.-С. 16-24.

8. Демин A.B., Витяев Е.Е. Система управления аниматом, основанная на теории функциональных систем П.К.Анохина // Анализ структурных закономерностей. - Новосибирск, 2005. - Вып. 174: Вычислительные системы. - с. 93-113.

9. Shapiro N.A., Poloz T.L., Shkurupij V.A., Tarkov M.S., Poloz V.V., Demin A.V. Application of Artificial Neural Network for Classification of Thyroid Follicular Tumors // Anal. Quant. Cytol. Histol. - 2007. - V. 29, - P. 122-119.

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

11.Полоз Т.Л., Шкурупий В.А., Полоз В.В., Демин A.B. Результаты количественного цитологического анализа строения фолликулярных опухолей щитовидной железы с помощью компьютерных и нейросетевых технологий // Вестник Российской Академии Медицинских Наук. - Москва, 2006. - № 8. - С.7-10.

12.Демин A.B., Использование нейросетевых технологий для диагностики фолликулярного рака щитовидной железы. // Студент и научно-технический прогресс: тез. докл. XLII международной научной студенческой конференции, Новосибирск, 2004. - 2004. - С. 240-241.

13.Полоз Т.Л., Демин A.B. Опыт применения нейросетевых технологий для цитологической диагностики некоторых заболеваний щитовидной железы // ZEISS СЕГОДНЯ. - 2004. - № 24. - С. 4.

14.Полоз В.В, Полоз Т.Л., Демин A.B. Морфометрия в нейросетевой технологии для цитологической диагностики фолликулярных пролифератов щитовидной железы // Новости клинической цитологии России: тез. докл. VI междунар. семинара патологоанатомов и клинических цитологов, Нижний Новогород, 2004. - 2004. - Т.8 - № 1-2. - С. 56.

15.Пупышева Т.Л., Демин A.B. Применение нейросетевых технологий в цитологической диагностике фолликулярных пролифератов щитовидной железы // Новости клинической цитологии России: тез. докл. V всероссийского съезда Ассоциации клинических цитологов России, Псков, 2003. - 2003. - Т. 7. - № 1-2. - С. 70.

16.Пупышева Т.Л., Демин A.B. Использование ассоциативных правил для решения задач цитологической диагностики фолликулярных новообразований щитовидной железы // Системный анализ и управление в биомедицинских системах. -2003. - Т.2. - №2. - С. 116-119.

17.Пупышева Т.Н., Демин A.B. Возможности нейросетевой технологии при дифференциальной диагностике фолликулярных пролифератов щитовидной железы // Новости клинической цитологии России. - 2003. - Т.7. - № 1-2.-С. 4-7.

18.Пупышева Т.Л., Демин A.B. Цитологическая диагностика фолликулярных неоплазий щитовидной железы с использованием нейросетевых технологий // Актуальные вопросы онкологии: Современные проблемы морфологической диагностики опухолей: тез. докл. междунар. научно-практ. конф., Иркутск, 2003. - 2003. - С.59.

19.Пупышева Т.Л., Демин A.B. Возможности использования искусственных нейронных сетей в цитологической диагностике фолликулярных неоплазий щитовидной железы // Новые направления и разработки в онкоморфологии: тез. докл. IX науч. конф., Москва, 2003. - 2003. -С.50.

20.Пупышева Т.Л., Демин A.B. Применение искусственных нейронных сетей в цитологической диагностике фолликулярных пролифератов щитовидной железы // Системный анализ и управление в биомедицинских системах. -2003. - Т.2. - Ksl.-C. 38-40.

Демин А. В.

ЛОГИКО-ВЕРОЯТНОСТНЫЙ МЕТОД ИЗВЛЕЧЕНИЯ ЗНАНИИ И ЕГО ПРИМЕНЕНИЕ В ЗАДАЧАХ ПРОГНОЗИРОВАНИЯ И УПРАВЛЕНИЯ

Автореферат

Автореферат:

60*84 1/8, 1 п. л. Тираж 100 экз. Заказ № 86. 20.11. 2008

Отпечатано ЗАО РИЦ «Прайс-курьер» ул. Кутателадзе, 4г, т. 330-7202

ВВЕДЕНИЕ.

ГЛАВА 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. Разработана модель адаптивной системы управления, обладающей возможностями самообучения, формирования иерархии целей и автоматического обнаружения новых подцелей. Проведены вычислительные эксперименты по исследованию возможностей разработанной системы управления и сравнению с другими подходами.

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.р/