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

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

МАКСИН Михаил Владиславович

СОЗДАНИЕ КОМПЬЮТЕРНОЙ СИСТЕМЫ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ФАРМАКОЛОГИЧЕСКИХ ДАННЫХ

Специальность 05,25.05

ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ПРОЦЕССЫ, ПРАВОВЫЕ АСПЕКТЫ ИНФОРМАТИКИ

АВТОРЕФЕРАТ ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДАТА ТЕХНИЧЕСКИХ НАУК

Москва 2006

Работ* выполнена

во Всероссийском институте научной я технической информации РАН

Научный руководитель:

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

Официальные оппоненты:

доктор технических наук, профессор Еремеев Александр Павлович кандидат технических наук Шапкия Александр Владимирович

Ведущая организация: Институт системного анализа РАН

Защита состоится « уз » декабря 2006 г. в 10.00 часов на заседании диссертационного совета Д 002.026.01 при Всероссийском институте научной я технической информации РАН по адресу: 125190, Москва, ул. Усиевича, д. 20.

С диссертацией можно ознакомиться в библиотеке Всероссийского института научной и технической информации РАН.

Автореферат разослан « » Ноября 2006 г.

Ученый секретарь диссертационного совета доктор биологических наук, АЛ

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

По данным Национальной токсикологической программы США (U.S. National Toxicology Program, NTP), в настоящее время зарегистрировано около 100,000 химических веществ, используемых в производстве, и ежегодно в этот список добавляется около 1,000 соединений. Влияние на человеческий организм известно лишь для 15% из них, хотя человек может быть подвержен ах воздействию во время производства, использования продуктов л утилизации отходов, и все она, так или иначе, становятся частью окружающей нас среды - воздуха, воды и почвы. Ещё меньше известно о канцерогенности этих веществ, так как экспериментальные исследования в данной области являются весьма дорогостоящими и времяёмкими: стандартный тест на канцерогенность одного химического вещества в рамках NTP включает а себя 2 года биопроб на грызунах и стоит около 2 миллионов долларов. Компьютерные системы янвлшя контрпродуктнвпых свойств химических соеднпеннй, предоставляющие прогноз этих свойств, позволили бы значительно сократить время и стоимость таких исследований. Особое место среди этих систем занимают системы интеллектуального Анализа давних (НАД), характеризующиеся способностью использовать существующие знания и приводить обоснование сделанного прогноза.

<

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

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

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

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

• возможность распараллеливания вычнслктельво-сложных этапов работы системы с целью снижения времени работы и требований к аппаратному обеспечению

• возможность работы в условиях, когда не все данные могут быть размещены в оперативной памяти - для масштабируемости системы в зависимости от объёма анализируемых данных

• возможность сохранения результатов работы системы (в том числе и промежуточных) перманентно

2. Исследование возможных путей учйта числовых характеристик в рамках логико-комбинаторного анализа

3. Систематизация числовых характеристик химических соединений, релевантных решаемым задачам прогноза, а также методов вычислений этих характеристик

4. Апробация системы в решении задач прогнозирования контрпродуктивных свойств выделенного класса химических соединений

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

Разработанная в диссертации система прогнозирования контрпродуктивных свойств химических соединений является интеллектуальной системой типа ДСМ (ИнтС-ДСМ) [1].

Интеллектуальные системы типа ДСМ основаны на ДСМ-методе автоматического порождения гипотез (АПГ), реализующим автоматизированные правдоподобные

А

рассуждения (порождение гипотез о причинах свойств, вывод по аналогии, процедуры объяснения начального состояния БД) [2].

ИитС-ДСМ представляет собой интерактивную систему, в которой на базе развитого логико-математического обеспечения, реализующего ДСМ-петод АПГ, осуществляется интеллектуальный анализ данных из БД с неполной информацией (БДНИ). ИнтС-ДСМ применяются для прогнозирования свойств структурированных объектов в Б ДНИ дня задач фармакологии, медицины, технической диагностики и социологии.

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

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

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

3. Задачи анализа гибридных данных сведены к классу задач, решаемых ДСМ-мето, '.'ом

4. Спроектирована и реализована расширяемая, масштабируемая и распараллеливав1 м «я версия ДСМ-рещателя, включая модель данных и алгоритмы работа на разные этапах.

5. Реализован модуль для квантовомеханического расчёта числовых характеристик класса химических соединений

При разработке ИнтС-ДСМ использовались:

• принципы гибридного представления химических соединений, предложенные в стат ыгх Маневича С.И. [3,4];

- модель какцерогенности ПАУ, разработанная в НИИ экологии человека и Гигвет сы окружающей среды [3];

• версия решателя задач для ИнтС-ДСМ, представленная в диссертации Панкратова ДБ .

[5];

- версия ФКСП-кодировщика структур химических соединений, разработанная в ходе диссертационных исследований Добрыниным ДА. [6);

Следующие особенности работы определяют се научную новизну:

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

2. Разработан распараллеливаемый алгоритм поуровневого построения решйтки ДСМ-гипотеэ, о игам изнрованннй для применения в задачах с трудоёмкими операциями нахождения сходства

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

Практическая значимость работы заключается в создании интеллектуальной

партнерской системы для анализа экспериментальных данных, которая:

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

2. Реализует важные элементы ДСМ-рассуждения - итерационное применение правил правдоподобного вывода (шага ДСМ-рассуждения) и стратегии ДСМ-рассуждения

3. Позволяет использовать статистический (вычислительный) анализ в сочетании с ДОМ-анализом

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

3. Является основой для создания ДСМ-систем И АД промышленного масштаба

По теме диссертации в настоящее время опубликовано б статей и 2 тезисов докладов.

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

Результаты диссертационной работы были доложены на следующих конференциях:

1. Международный форум "Информационные технологии и общество - 2003", Турция, Кемер, 20-27 сентября 2003г.

2. II съезд токсикологов России. Москва 10-13 ноября 2003 г.

Структур« работы. Диссертация состоит из введения, трех глав, заключения, списка

литературы и приложения.

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

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

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

Извлечение знаний из баз данных (Knowledge Discovery in Databases, KDD), как определяется основателями этого подхода [7], есть нетривиальный процесс обнаружения обоснованных, ранее неизвестных, потенциально полезных и объяснимых закономерностей в данных. Поиск закономерностей в данных (Data Mining, DM) - например, в виде дерева решений, кластеров данных или параметров регрессии - является ключевым этапом процесса KDD. Под методами интеллектуального анализа данных (Intelligent Data Analysis, ЮА) [8] понимают методы, способные использов&'ть существующие знания о предметной области или звания о собственно принципах анадчза данных. Это определение можно назвать определением интеллектуальности метода НАД в слабом смысле, по сравнению с определением, данным в [1].

Раздел 1.2 характеризует задачи, цели и инструменты интеллектуального анализа данных. Среди задач НАД выделяют следующие:

• Классифицирование - отнесение объекта (элемента данных) к одной из заранее определенных категорий. Автоматизация этого вида анализа состоит в использовании машиной запрограммированного алгоритма к яассифицирования, а «интеллектуализация» — в автоматическом порождении классификатора на основе примеров объектов из различных категорий,

• Регрессия - определение значения некоторой числовой характернее член объекта.

• Кластеризация — выделение группы категорий, или кластеров, для описания данных -относится к направлению неконтролируемого обучения (unsupervised I earning).

• Характеризация - нахождение минимального описания группы объекте в

• Моделирование зависимостей - нахождение моделей, отражающих зависимости между данными об одном объекта

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

Конкретные инструменты, а точнее, программы для ИАД рассматриваются в свете 3" аспектов - структуры входных данных (язык примеров и язык существующих знаний), структура искомой модели данных (язык гипотез) и собственно алгоритм анализа (обучения). .

Язык примеров - это форма представления обучающих примеров (данных), существенно используемая алгоритмом обучения. Раздел 1.2.1 приводит описание различных языков примеров, среди которых есть числовые векторы, пропозициональные и языки логических фактов. Язык гипотез служит для представления результатов обучения -модели данных, В разделе 1.2.2 приводится краткий обзор используемых языков гипотез, таких как числовые функции, деревья решений, решающие правила, языки различных сужений логики 1" порядка, а также языки ДСМ-логнк [9], расширяющие логику 1™ порядка. Раздел 1.2.3 содержит классификацию алгоритмов машинного обучения, в рамках концепции «обучение как поисх» (learning as search) [10]. В задачах МО пространство поиска (гипотез) задается не явным перечислением возможных состояний, а через начальное состояние (начальную гипотезу) и оператор перехода (порождения гипотез), определяемого текущим множеством обучающих примеров в имеющимися на данный момент знаниями. Конечное же состояние считается достигнутым, когда все возможные гипотезы рассмотрены и сформирован набор гипотез, удовлетворяющих некоторому критерию отбора гипотез.

Раздел 1.23.1 проводит классификацию по способу формирования текущего набора обучающих примеров. Фактически наличие такого отбора делает алгоритм эвристическим, так как при этом некоторое число гипотез «насильно» исключается из рассмотрения. Стратегия «разделяй и властвуй» лежит в основе почти всех методов построения деревьев решений (ID3 [11], SRT [12]). Стратегия «покрытие» используется во многих методах построения решающих правил (CN2 [13], AQ [14], GOLEM [15]).

Раздел 1.2.3.2 классифицирует алгоритмы по способам порождения гипотез, среди которых можно выделить 4 основных подхода. Наиболее часто встречается подход «сверху

вниз» (top-down), или «от общего — к частному» (gentral-to-specific), при котором в качестве начальной гипотезы выбирается наиболее общяя гипотеза, покрывающая как положительные, так и отрицательные примеры (решающие правила - FOIL 116], деревья решений - ГОЗ [И], SRT [12]). Двойственным к подходу' «сверху вниз» является подход «снизу-вверх» (bottom-up) - AQ (HI. GOLEM [15], PROGOL [17]. Подход, комбинирующий два вышеупомянутых, реализован в алгоритме CANDIDATE-ELIMINATION [17] обучения понятиям в рамках концепции Version Space [10]. И, наконец, возможен вариант (как, например, в CN2 [13]) порождения гипотез не на базе конкретн ых примеров, а на основе предопределённой их структуры (например, каждый объект описывается кортежем 4* атрибутов с заданным доменом дли каждого из атрибутов) - в этом случае примеры служат исключительно для проверки критерия отбора гипотез, например, статистической значимости.

Раздел 1.233 приводит некоторые критерии отбора гипотез, которые выражают некие «субъективные» представления о природе задачи или об искомом решении, и, на сутн, являются элементом индуктивной склонности (inductive bias) [IS] алгоритма. Наиболее часто встречается критерии, следующие принципу «бритвы Оскама» (Occam's tazot) , т.е. простоты гипотезы. Более содержательными примерами являются различные условия, расширяющие прямой метод сходства в ДСМ-системах [19).

Раздел 13 рассматривает некоторые задачи интеллектуального анализа данных в науках о жвзин, удовлетворяющие условиям применимости систем типа ДСМ f20].

Раздел 1.3.1 посвящен задаче исследования капцерогснно^тн веществ (токсикологии). Целая галерея методов машинного обучения в применении к этой задаче была представлена в рамках открытых проектов Predictive-Toxicology Evaluation (PTE) [21] 1993-1997 гг. и 1998-1999 гг. Массив содержал около 400 веществ, как органического, так и неорганического происхождения. Для каждого из соединений, помимо структурной формулы, имелись дополнительные экспериментальные данные, п£ «вставленные значениями 189 атрибутов. Для обучающих соединений был также известен уровень канцерогенности.

Алгоритм SRT {Structural Regression "Лее) [12] был создан как попытка соединить подходы статистического построения регрессионных деревьев н индуктивного логического программирования (ИЛП), и тем самым научиться решать задачу «реляционной регрессии» • построение теории для прогнозирования численных величин на основе реляционных данных и, возможно, существующих знаний в данной предметной области. Метод ТЕРТ

(Tree Induction for Prédictive Toxicology) [22] является приложением известного алгоритма построения деревьев решений С4.5 [23] к предложенной задаче. ИЛП алгоритм PROGOL [17] реализует принцип обратного следования (inverse entailment) для генерализации множества положительных примеров относительно теории. Обучающие примеры задаются в виде дефинитных дизъюнктов.

Прогноз LRD выполнен с помощью алгоритма Distill [24], который представляет собой объединение метода DiVS (Disjunctive Version S расе) со стохастическим согласованием. Прогноз OUCL-2 сделан с помощью дерева, построенного системой С4.5. Каждое вещество было описано значениям« 417 атрибутов, причём некоторые наборы атрибутов основаны на правилах, построенных ИЛП-системами PROGOL и WARMR (W. Association Rules over Multiple Relations) [23]. Прогноз OAJ построси па независимом прогнозе двумя методами - C4,5rules и неким простым байесовским классификатором - и последующем голосовании. Прогноз LEU3 сделан при помощи алгоритма ICL (Inductive Constraint Logic) [26] с использованием теории для мутагенеза, построенной ранее системой PROGOL Прогноз LEU2 выполнен системой MACCENT (MAxjmum ENTropy modeling with Clausal Constraiots) [27] с использованием ассоциативных правил, найденных методом WARMR.

В целом, анализ построенных моделей показывает, что они скорее выделяют наиболее значимые сопутствующие признаки (в виде результатов краткосрочных тестов, как, например, результат теста на мутагенез бактерий Salmonella, которому придается большой вес практически в каждой модели), чем выявляют структурные причины канцерогенеза. Принимая это во внимание, организаторы конкурса РТС 2000-2001 предложили использовать в качестве обучающих только данные, касающиеся химической структуры веществ непосредственно.

Модель VIN1TI [28] была получена ДСМ-системой исследования задач «структура-активность» с использованием представления химических соединений в виде ФКСП (фрагментарный код суперпозиции подструктур) [30]. ДСМ-метод автоматического порождения гипотез (АПГ) [29] является методом обучения понятиям, основанным на формализации важного класса правдоподобных рассуждений [19] и реализующим синтез познавательных процедур — индукции, аналогии и абдукции. Модели LEU* получены с помощью алгоритма Tilde [31] построения логических деревьев решений, основанного на алгоритме С4.5. Модель WAI1 [32] представляет собой набор семи независимых линейных классификаторов, каждый из которых использует свой набор атрибутов — один из семи,

предоставленных различными группами исследователей, принимавшими участие в конкурсе. Соединение считалось канцерогенным, если хотя бы один из классификаторов голосовал за это. Модель GONS для прогноза MR была построена с помощью системы обучения понятиям SubdueCL [33], основанной на системе обнаружения подструктур в структурных данных Subdue, Обе системы используют представление реляционных данных в виде графа для нахождения повторяющихся образцов (в виде подграфов).

Раздел 13.2 посвящен задачам НАД в медицине. Эта область стала одним из главных полигонов испытания н применения методов ИАД с самых ранних этапов их развития. Можно выделить два класса методов ИАД, отвечающих главным аспектам применения таких методов в медицине [34]:

1, Методы абстракции данных (data abstraction), призванные поддерживать принятие решений посредством извлечения полезных абстракций (обобщений) из «сырых», по большей части числовых, данных.

2. Методы собственно анализа данных (data mining), предназначенные для извлечения знаний, сокрытых в массивах данных, в понятной «символической» форме.

Основными особенностями применения ИАД в медицине являются следующие:

• «Добытые» закономерности должны быть выражены в терминах, понятных медицинскому эксперту, и подкреплены конхрепшми примерами - только при этих условиях они могут быть взяты па вооружение и использоваться в повседневной практике.

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

• Наличие неполных и защушгбнных данных, снижающих надежность прогноза.

• Для принятия ответственных решений требуется очень детальное описание объектов анализа (состояния пациента и наблюдаемых симптомов), гораздо более детальное, чем обычно предоставляют деревья решений — традиционный инструмент диагностики — после «прореживания» с целью получения дерева большей общности и меньшего размера.

• Для увеличения шансов получения значимых результатов, такие методы должны уметь взаимодействовать с экспертом, который может «поделиться» существующими

знаниями, предоставить необходимые данные и оценить результаты работы [34] (т.е.

быть человеко-машинными [29]).

Раздел подводит итоги сделанного обзора. Отмечаются следующие тенденции в развитии методов анализа данных;

• Вс£ более активное использование представления данных в виде отношений -«естественного» представления для реляционных БД - для работы в рамках систем извлечения знаний из баз данных.

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

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

• Возрастает интерес к системам, строящим избыточные модели, которые позволяют эффективно работать в условиях неполных и зашумлённых данных.

Проведанный анализ предъявляемых требований и используемых методов И АД позволяет описать системы типа ДСМ в терминах их отличительных особенностей.

• ДСМ-системы являются интеллектуальными в сильном смысле.

• Системы типа ДСМ выхолят за рамки систем анализа данных; реализуя предварительное преобразование данных, они являются системами извлечения знаний.

• Кроме того, ДСМ-системы обладают способностью идентифицировать «белые пятна» разрабатываемой эмпирической теории — способность уникальная, не упоминаемая в литературе.

• Логическая. корректность ДСМ-гнпотез выступает как альтернатива статистической доверительности, и, в отличие от последней, требовательна не к объему имеющихся данных, а именно к составу.

• Разделение «положительных» и «отрицательных» гипотез позволяет отказаться от правила «исключённого третьего» и увеличить точность и надёжность результатов за

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

• Модели данных, создаваемые ДСМ-методом, избыточны в том смысле, что один объект-пример может попадать под действие нескольких результирующих гипотез (во многих системах это невозможно из-за требования минимальности описания). Эта избыточность позволяет выполнить последующий прогноз с большей полнотой и надежностью.

• ДСМ-системы предоставляют четкое обоснование сделанного прогноза в терминах подобъектов-<(Структурных причин», что роднит их с системами обучения, основанными на анализе ситуаций—case-based leaming [35].

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

ДОМ как средства интеллектуального анализа данных и извлечения знаний из баз

данных:

• Соединение логико-комбинаторного ДСМ-мето.аа н численных статистических методов позволило бы учитывать как структурные, так числовые характеристики исследуемых объектов.

» ДСМ-метод, не использующий статистических критериев, может быть «введен в ,заблуждение» шумовыми данными (единичными «выбросами» неправильных данных) и в случае его применения для анализа данных в промышленных масштабах эта проблема должна быть адресована.

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

• Другой аспект систем извлечения знаний из баз данных — распараллеливание алгоритмов - также должен быть изучен (в применении к алгоритмам ДСМ-метода, например, алгоритму нахождения глобальных сходств).

В главе П предлагается подход к проблеме интеллектуального аналн-за гибридных (структурно-числовых) данных на примере ДСМ-системы прогнозирования контрпродуктивиых свойств химических соединений. В разделе 2.1 приводится краткое

описание логико-комбинаторного ядра системы - ДСМ-метода автоматического порождения гипотез, и используемых им аппарата квазиаксиоматических теорий (КАТ) [38] и бесконечнозначной логики р",'"' [37]. Раздел 2,2 описывает специализированную ДСМ-систему прогнозирования контрпродуктивных свойств химических соединений, реализованную в отделении интеллектуальных систем ВИНИТИ и ставшую лауреатом международного конкурса Predictive Toxicology Challenge 2000 в трех из четырех категорий. В этой системе для представления химических соединений применялся язык ФКСП (фрагментарный код суперпозиции подструктур) [30], специально разработанный для задачи «структура-активность».

Однако большинство моделей в данной задаче являются числовыми. В качестве примера, Раздел 2.3 приводит числовую модель канцерогенное™ полиароматнческих углеводородов (ПАУ), разработанную в НИИ экологии человека и гигиены окружающей среды им. А, Н. Сысина. В этой модели полагается, что контрпродуктивная - канцерогенная или мутагенная - активность ПАУ будет тем выше, чем ниже энергия образования соответствующего ему метаболита, т.е. вещества, получающегося в результате превращений, которые претерпевает исходное вещество в организме. В процессе эксплуатации этой модели были обнаружены соединения, выпадающие из общего рада. Оказалось, что такие соединения имеют специфическую структуру, в качество результатов значительно повышается, если произвести предварительный отбор соединений по структуре, а уж затем применять регрессионный анализ. Таким образом, возникает задача анализа гибридных - структурно-числовых - данных. Первым шагом в этом направлении становится разработка квантовомехапического модуля, реализующего вышеупомянутую модель. Он использует метод Хюккеля (39) для извлечения из структуры ПАУ числовых характеристик, составляющих числовую компоненту описания объекта.

Раздел 2.4 посвящен следующей проблеме — адаптация ДСМ-метода к анализу многокомпонентных объектов. Описываемый здесь подход является первым приближением (в рамках ДСМ-метода) к проблеме анализа гибридных данных и состоит в попытке использования в анализе так называемых мульти-ДСМ-объектов, т.е. ДСМ-объектов, представляющих собой упорядоченный набор компонентов, каждый из которых в свою очередь представляет собой ДСМ-обьект. Операции вложения а нахождения сходства для мулъти-ДСМ-объекта определяются естественным образом через соответствующие операции для каждого из компонентов.

Раздел 2.5 лосвицен проблеме формализации числовой величины как ДСМ-объекта. Здесь в качестве решения было выбрано введение алгебры интервалов [40].

В разделе 2.6 описываются эксперименты, проведенные с модернизнро) «анной ДСМ-системой прогнозирования кошрпродуятивных свойств соединени!) Первым отличительным результатом применения этой системы явилось то, что получемная система гипотез объясняла все обучающие примеры из тестового массива (т.е. выполвя лея критерий достаточности оснований принятия этих гипотез), чего не удавалось достичь, ¡усматривая только структуру соединений. Кроме того, учёт числовой характеристики соединений сделал прогноз 3-х соединений более полным по числу доопределенных свойств и, таким образом, более точным по описанию свойств соединения в целом. В дру гой ,«ерии экспериментов была сделана попытка доопределить свойства 14-ти ещё не изученных соединений. Для 9-тн из них были получены прогнозы, причём они совпали с пр о птозами, сделанными с помощью группы правил, предложенной экспертами в [41].

Раздел 2.7 подводит итоги данного этапа исследований. Наряду с преиму! зествами выявляется рад недостатков .чанного подхода. Среди них отмечается знач; ягельное увеличение числа порождаемых гипотез, связанное с тем, что фактически сходм-во двух числовых ДСМ-обьектов ие бывает пусто. Указывается также, что система, в которой можно переопределить лишь операцию нахождения сходства (т.е. сходство 2-х объ ектов), не позволяет использовать статистические методы в полной мере и, таким образом, не вполне отвечает поставленной задаче совместного использования логико-комбинатор ных и статистических методов в анализе данных. Дальнейшее развитие системы вишитса в изменении ее архитектуры в соответствии с новыми требованиями.

Глава III посвящена разработке новой архитектуры ДСМ-систем, предназначенных для анализа гибридных данных, а также реализации на основе этой архитектуры новой версии ДСМ-системы прогнозирования контрпродуктившах свойств химических соединений.

Попытка расширения существующей программной реализации ДСМ-метода [4] -интеллектуальной системы типа ДСМ (ИнтС-ДСМ) прогнозирования конгрпрадукгивных свойств химических соединений - выявила некоторые архитектурные недостатке данной реализации, которые стали препятствием для развития системы. Главными из них являются следующие:

* Структуры объектов к их сходств считаются одинаковыми. Однакс это не так в случае статистического анализа, где объектами являются числовые векто,ры, а в качестве их

сходства могут выступать всевозможные статистические модели - от кластеров до регрессии и факторов.

• Отсутствие возможности переопределения процедуры нахождения локального сходства нескольких объектов. Сейчас, при настройке ДСМ-системы на конкретную предметную область, происходит переопределение операции (попарного) сходства, т.е. предоставляется доступ к информации о не более чем двух объектах одновременно. В случае же применения статистических методов, для нахождения существенного сходства часто требуется иметь одновременный доступ к информации обо всех объектах-'родителях" сходства.

• Необходимость хранить в оперативной памяти компьютера все порождаемые гипотезы. Используемый алгоритм построения решетки понятий следует подходу "добавляй по одному" [36], в котором новые гипотезы порождаются пересечением всех существующих гипотез с новым объектом. При таком построении на каждом шаге необходимо иметь доступ ко всем порождённым гипотезам и нет возможности отложить "законченные" гипотезы в сторону (на диск) и освободить занимаемую ими память для новых гипотез. Как упоминалось, значительное увеличение числа порождаемых гипотез является одной из проблем интегрированной ДСМ-системы (в её текущей реализации), и необходимость экономить оперативную памяти становится актуальной.

■ Программа останавливает свою работу после первого шага применения правил правдоподобного вывода {п.п.в.). В [42] были сформулированы необходимые и достаточные условия появления новых гипотез при добавлении к множеству исходных объектов данного класса нового объекта, приписанного к этому классу. (Этот объект может быть добавлен в систему экспертом или являться результатом классификации на предыдущем шаге). Тем самым была показана целесообразность перехода к последующим шагам применения п.п.в., и дело лишь за его реализацией.

• Программа не поддерживает дополнительные эмпирические зависимости (ЭЭ) н их комбинации (стратегии) как подключаемые модули, хотя это является важным элементом настройки ДСМ-системы, Ядро системы монолитно, что не позволяет использовать отдельные его элементы для реализации вариаций ДСМ-метода.

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

тем самым способствовать с4 развитию, а также заложить основу для создания ДСМ-систем промышленного масштаба.

Раздел 3.1 посвящен вопросу обобщения понятия сходства для случая, когда структуры изучаемого объекта и искомы* гипотез не совпадают, В этом случае предлагается использовать набор функций сходства yr{x¡¡„ fes, х«}. областью значений которых является С (множество сходств), а областями определения - S*S, S*C и ОС соответственно (где 5 — множество объектов). При этом функция Хн обладает свойствами операции сходства на множестве объектов С, а функции X» и Xsc - свойствами (квази)коммутативности н (квази)ассоциативности:

(1) fc.Ov, sj) = X« (sj, J(), ej) = Si),

(2) XscOh йа (Sj, S¿)) ~ XaíXss C*/> sj), S¿).

Проверка на сходства на пустоту («неинформативность») осуществляется не сравнением с эталонным «пустым» сходством, а более абстрактным образом - посредством специального предиката Е(с). При этом должны выполняться следующие условия:

(1) VcVí{((ceC)4(í eS)&£(c))-> E(Z„(s,c))),

(2) V^fe eC)&(Cj € C)&£(cf))-> £(лги<с(,е,))), т.е. сходство с пустым сходством всегда пусто.

Отношение вложнмостя на множестве объектов обобщается до соответствия вложимостя сходства в объект /(с, i) такого, что выполняются следующие условия:

(1) Vsl4sjfl(s¡es)&(sj б«;))), т.е. сходство всегда вложимо в породившие его объекты;

(2) Ve V,r(((cnC)&(s eS)&E(c))-> (l(c, J,))), т.е. пустое сходство вложимо в любой объект.

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

На уровне языха программирования (С++), в качестве механизма настройки н расширения программной системы используется механизм шаблонов (templates), а не более

часто употребляемый для этих целей механизм наследования классов (subclassing). Механизм шаблонов является более общим по сравнению с механизмом подклассов: достаточно объединить все методы, требуемые контрактом для некоторого шаблона, в один (абстрактный) класс, и создать экземпляр шаблона с использованием этого класса - я мы получаем класс, обладающий функциональностью исходного шаблона Н поддерживающего механизм подклассов.

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

В разделе 3.2.1 обсуждаются структуры данных. Фундаментальными являются объект и сходство. Система позволяет, во-первых, использовать сколь угодно сложные описания объектов и сходств и, во-вторых, иметь независимые описания для объектов и для сходств. Всё это возможно, конечно, при условии, что операции нахождения сходства, предикат вхождения сходства в объект и критерий «пустоты» сходства (реализованные во вспомогательных алгоритмах) определены корректно.

К вспомогательным структурам данных относятся структуры представления множеств свойств и множеств идентификаторов объектов. Эти структуры независимы от предметной области и система предоставляет «стандартные решения» для них, но они могут быть легко заменены любым альтернативным решением. Такая необходимость может возникнуть при настройке системы на конкретную задачу в данной предметной области.

Наконец, при разработке библиотеки делались минимальные предположения о контейнерах данных, т.е. о способах хранения данных и доступа к ним. В экспериментальной системе используются контейнеры STL, которые хранят все данные в оперативной памяти. Однако, интерфейс (контракт) между ядром системы н контейнерами, а главное, разработанный алгоритм «поуровневого» построения решетки понятий, который исключает необходимость оперативного доступа одновременно ко всем порождённым гипотезам, позволяют применять контейнеры, использующие оперативную память лишь для кэширования, и хранящие основную массу данных на диске или в базе данных. К разряду

контейнеров относится структура, используемая для хранения элементов отношений и

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

Раздел 3.2.2 посвящен описанию программных компонентов ядра системы.

Обсбщатеяь (Inductor) реализует этап порождения гипотез II™ рода (о причинах наличия свойств в объектах). Процесс состоит в (параллельном) применении Генератора I" рада для построения отношений, соответствующих решающим предикатам сходства и M'Ijt, с последующим вызовом Управителя 1™ рода, который порождает гипотезы, применяя п.п.в. Ira рода к элементам полученных отношений.

Генератор f° рода (Generator I) строит отношение для решающего предиката сходства M'j, (для указанных шага л применения п.п.в., знака а и Усилителя х).

Фшыпр (Rejecter) выполняет проверку наличия определенной ЭЗ для пары (сходство, свойства). В настоящее время реализованы фильтры (а) простого метода сходства и (4) «запрета на контрпримеры».

Усилитель (Enhancer) представляет собой набор Фильтров, соответствующих искомым эмпирическим зависимостям (ЭЗ). Расширение тривиального набора (включающего лишь ЭЗ простого метода сходства (а)) фактически приводит к усилению пл. в. Г° рода, отсюда и название.

Управитель 1-го рода (Ruler I) доопределяет отношение =>j посредством

применения пл.в, 1го рода к элементам отношений М*^ и Используемый в

экспериментальной системе Управитель соответствует методу «ДСМ-АПГ без отношения порядка», но так как, во-первых, Генератор и Управитель разделены, и, во-вторых, Генератор уже поддерживает механизм усилителей, то для создания системы типа «ДСМ-АПГ с отношением порядка» достаточно модернизировать лишь логику Управителя.

Уточнитель (Analoger) реализует этап порождения гипотез Г* рода (о наличии свойств в объектах).

Контролёр (Abductor) реализует этап проверки выполнимости критерия достаточного основания принятия гипотез (к-Д.о.п.г,) в полученной БЗ. Процесс состоит в

попытке «доопределить» все фактические свойства объектов с помощью результирующего отношения =>j,

Рассуждатель (Reasoner) объединяет все вышеописанные процедуры в итерационную процедуру ДСМ-рассуждення: Обобщатель и Уточнитель поочередно доопределяют соответствующие отношения, пока это возможно, а затем Контролер проводит проверку качества результатов работы.

Раздел 3.2 J посвящен описанию программных компонентов настройки системы.

Помощник предметной области (DomainHelpcr) должен предоставлять следующие процедуры:

• Нахождение локального сходства объектов (collate). Для этого процедуре передается два итератора - одни по объектам-родителям, а другой — по «соседям снизу» искомого сходства (в смысле частично упорядоченного множества, образовываемого множествами объектов-родителей). Итератор по объектам-родителям универсален (например, итератор по «соседям снизу» пуст для уровня 2) и предоставляет непосредственный доступ к данным об объектах. С помощью же итератора по «соседям снизу» в некоторых случаях можно значительно ускорить процедуру (например, если объекты представлены множеством дескрипторов, то для нахождения сходства достаточно «пересечь» любые два «соседа снизу»). Ядро передаёт оба итератора, и тем самым даёт возможность использовать тот, который в данном конкретном случае более удобен.

• Нахождение сходства между объектом и сходством (collatejsc). Этот частный случай процедуры нахождения локального сходства объектов реализуется отдельно — из практических соображений (в силу потенциальной простоты его реализации). Кроме того, эту процедуру часто бывает удобно использовать в реализации предыдущей.

• Определение эквивалентности сходств (equal). Тривиальный в случае множеств, этот предикат может становиться довольно сложным в случае числовых моделей. Например, прямое сравнение действительных чисел чаще всего не имеет смысла — как минимум, нужно рассуждать в терминах £-0 крести остей.

• Определение «пустоты» сходства (empty). В простых случаях «пустоту» можно определить как эквивалентность эталонному «пустому» сходству (например, пустому множеству дескрипторов), но в общем случае реализация этого предиката может включать вычисления (как, например, в случае со статистическими моделями, где мерой

«неинтересности» может служить дисперсия).

• Определение вложимости сходства в объект (include). Хотя ^^ормально этот предают можно было бы (неявно) реализовать через предикат эквивалентности схсщсп» и операцию нахождения сходства между сходством и объектом, с н реализуется явно -- с тем, чтобы была возможность оптимизации.

Помощник для работы с множествами свойств (PtopettiesHelpei) уже реализован как часть библиотеки, но должен пересматриваться тогда, когда меняется внутренне!; представление для множеств свойств. Существующая реализация — дл и представления в вице 32-бнтиых полей, где каждому биту соответствует свойство и наличк е/отсутствие бита означает наличие/отсутствие свойства. Это позволяет выполнять теоретике-множественные операции со скоростью побитовых операций, но накладывает ограничение ни число свойств - не более 32 (что должно быть более чем достаточно для большннств.1 практических задач). Этот помощник должен предоставлять процедуры для пересечения, объединения и разности множеств, а также определения равенства множеств и пустого множества,

В случае же множества идентификаторов (порядковых номеров) объектов ограничение на их число может быть существенным. Включенная в библиотеку реализация (основанная на представлении в виде б4-битного поля) поддерживает до 64 объектов, что может быть недостаточно для решения практических задач. Альтернативное р< штение может содержать либо фиксированное число 64-битных полей, либо их переменное ч исло. Первый вариант гораздо проще и производительней второго, ко такая реализация лишь смягчает ограничение (л полей позволяют анализировать до 64п объектов), а не устраняет его. Помощник для работы с множествами идентификаторов объектов (ExtentHelper), помимо теоретико-множественных операций и предикатов, позволяет преобразовывать идентификатор объекта во множество, состоящее из одного этого идентификатора, а также множество - в итератор по идентификаторам.

Раздел 3.2.4 подробно описывает алгоритм работы Обобщгяеля. Его распараллеливаемой частью является алгоритм построения решетки сходств. Сразу поясним, что рассматриваемые множества подмножеств (некоторого множеству О) чаще всего не являются решетками в строгом смысле слова. Они представляют собой част ично упорядоченные множества, которые становятся решетками, если к ним добавить элеме пи 0 и £1. Тем не менее, для простоты мы также будем называть их решетками.

Элементом множества порождаемых гипотез является тройка (Е, С, /'), где I' -множество идентификаторов объектов-родителей гипотезы, С - их локальное сходство, i ' -

St

структура, описывающая множество свойств, причиной наличия (или отсутствия) которых данное сходство является. В любой момент времени это множество является решеткой как множество всех подмножеств множества рассматриваемых объектов (т.е. в части Е), н это его свойство используется для порождения новых элементов. В процессе работы множество «прореживается» с тем, чтобы в конечном итоге остались только элементы, в которых локальное сходство является также глобальным, и тогда эта решётка становится также реш&ткой понятий, как определяется в рамках анализа формальных понятий. При этом Е исполняет роль объёма формального понятия, а (С, Р) - его содержания [42].

Структура Р, описывающая множество свойств, представляет массив структур, приписывающих истинностные значения на каждом шаге применения п.п.в. То есть, п-ный элемент массива Р есть набор множеств свойств И<*,я> таких, что формула имеет

оценку (у,п), где V е {1,0,-1, г}. Это позволяет хранить данные, необходимые обоим решающим предикатам - М^ и М'^ - без дублирования общих данных (главным образом, сходства С), и обрабатывать положительные и отрицательные примеры единым образом.

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

Тот же подход применялся при разработке алгоритма - делая минимум предположений относительно предметной области, перенести как можно больше вычислений на внутренние структуры данных - те, которые мы можем оптимизировать независимо от "пользовательских" структур данных, и тем самым контролировать эффективность алгоритма в смысле времени работы и требуемой памяти. Основным является предположение, что операция сходства является дорогой (в смысле времени выполнения), гораздо дороже операции пересечения множеств (тем более что множества могут быть представлены посредством битовых масок со всеми вытекающими преимуществами). Поэтому, прежде чем вычислять сходство для некоторой гипотезы, проверяется необходимое условие того, что оно не пусто, а именно, то, что все ее соседи снизу не пусты. (Соседи снизу/сверху определяются посредством отношения частичного порядка на множествах Е, естественным образом связанным с операциями объединения и пересечения; именно здесь используются решеточные свойства множества множеств £). Точнее, на уровне / алгоритм пытается найти элементов, которые являются соседями

снизу некоторого элемента (по построению, уровень содержит только непустые элементы, т.е. фактически ищутся 1+1 непустых соседей снизу); в случае успеха вычисляется сходство соответствующих 1+1 объектов, и если оно не пусто, на уровень /+/ помещается новая гипотеза. При этом перебираются все возможные сочетания (числом где IV - число элементов на уровне I) и тем самым гарантируется, что все непустые элементы уровня 1+1 будут рассмотрены. Как видно, при таком подходе достаточно иметь оперативный доступ лишь к элементам уровней / и 1+1.

Эксперименты доказали, что гораздо эффективнее разделять построение (+) и (-) решеток, чем пытаться формировать конечную решетку за один проход. Возможное дублирование выполнения операции сходства с лихвой окупается возможностью немедленного исключения неверных гипотез из дальнейшего рассмотрения (в случае же одного прохода гипотеза будет исключена, только если она «неверна», ■ сразу по обоим знахам). Кроме того, разделение этих двух шагов позволяет выполнять их п араллельно.

Раздел 3,2.5 подробно описывает алгоритм работы Уточнителя, В этом алгоритме также существенно используется частичная упорядоченность множества гш »тез 11-го рода. А именно, поиск сходств-кандидатов осуществляется поуровпево, начиная с самого верхнего уровня, и перед проверкой вложения сходства в объект проверяется-., не было ли неудачных проверок для «соседей сверху» данного сходства. Отсутствие таких неудачных проверок является необходимым условием успешной проверки для текущего сходства: каждое сходство из «соседних сверху» вкладывается в текущее сходство, и если хотя бы одно из них не вложилось в данный объект, то и текущее сходство не влдакимо в него. С целью выполнения этой проверки, для каждого объекта хранится список сходств (с предыдущего уровня), которые в него не вкладываются. Каждое сходство идентифицируется множеством идентификаторов объектов-родителей. В итоге, проверка состоит в поиске среди элементов этого списка сходств, являющихся «с оседями сверху» данного (в смысле множества идентификаторов объектов).

Таким образом, операция определения вложнмости сходств а в объект (вычислительная сложность которой в общем случае может превышать сложность процедуры нахождения сходства между сходством и объектом) заменяется -'«сколькими (до п-к на уровне к) операциями пересечения множеств идентификаторов об ъектов. Эта замена имеет смысл в случае, когда операция определения вложимости существенно дороже операции пересечения множеств. Это и было основополагающим предположением при разработке данного алгоритма. Оно должно быть подкреплено эф фехтивной

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

С использованием разработанного ядра была заново реализована экспериментальная ДСМ-система для прогнозирования контрпродуктивных свойств химических соединений. Ей посвящен раздел 3.3. Представление изучаемого объекта в ней осталось прежним: набор кодов ФКСП химического соединения в качеетве структурной компоненты н некая физико-химическая характеристика соединения (предоставляемая извне или вычисляемая в процессе работы) - в качестве числовой компоненты. Однако теперь представление сходства может изменяться независимо. В экспериментальной системе числовая компонента сходства представлена в двух вариантах — посредством алгебры интервалов и в виде линейной регрессионной модели. Раздел 3.3.1 занимается вопросом использования линейной регрессии в качестве сходства числовых величин. В этом случае числовая компонента объекта должна быть парой чисел (зду), а сходство 2-х (или больше) таких пар выражается параметрами Ро и р| линейной регрессии у = ро + Р1Х + е. В качестве значений этих параметров используются робастные оценки:

Эквивалентность сходств определяется как равенство соответствующих параметров регрессии. В качестве оценки «информативности» сходства при этом используется коэффициент детерминации г1:

, ^ К-ЗА?

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

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

Еще одним вариантом комбинирования численного и логико-комбинаторного анализа, реализованным в системе, является «регрессионный фильтр». Здесь объект включает числовую компоненту для регрессионного анализа, а сходство — лишь структурную компоненту. Соответственно, при определении эквивалентности н вложимости сходств принимается во внимание лишь структурная часть. Однако сходство считается также пустым, если коэффициентом детерминации для соответствующей регрессионной модели меньше заданного порога. Этот подход является воплощением идеи контролирования комбинаторной «лавины» статистическими «поглотителями»,

В разделе 3.3.2 приводятся результаты экспериментов с системой. Показывается, что применение «регрессионного фильтра» может несколько улучшить степень покрытия исходных фактов результирующим набором гипотез. Применение же регрессионной модели на всех этапах ДСМ-анализа позволяет добиться 100% покрытия. Вместе с тем наблюдается следующие эффекты. Во-первых, поскольку у всех «-1» гипотез регрессионная модель одна и та же (у — 0), то она не оказывает никакого влияния на формирование набора «-1» гипотез. Во-вторых, в силу того, что эта регрессионная модель «сильно» отличается от всех моделей «+1» гипотез, то фактически пропадает отбор по «запрету на контр-примеры». Этим, в частности, объясняется значительное увеличение числа «+1» гипотез. (Последний эффект наблюдается также при использовании модели интервалов).

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

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

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

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

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

3, Разработан распараллеливаемый алгоритм поуровневого построения решетки ДСМ-гипотез, оптимизированный для применения в задачах с трудоемкими операциями нахождения сходства.

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

5. Реализован модуль для квантовомеханического расчета числовых характеристик класса химических соединений.

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

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

1. Максик М.В., Харчевникова Н.В. Кваиговомеханический модуль системы, реализующей комбинаторно-численный подход к проблеме прогнозирования свойств химических соединений. // НТИ. Сер.2. - 2002. • № б- С. 57-62.

2. Максин МЛ. Интеллектуальный анализ данных в науках о жизни. // НТИ. Сер.2. -

2003.-№9.-С. 16-27.

3. Харчевникова Н.В., Максин М.В., Блинова В.Г., Добрынин Д.А., Жсщдакова З.И. Прогноз канцерогенности полициклических ароматических углеводородов с использованием кьавтово-химического модуля генерации метаболитов интеллектуальной ДСМ-спстемы.//НТИ.Сер.2.-2003.-Ка П.-С. 12-17.

4. М.В. Максин, Н.В. Харчевникова, ВТ. Блинова, ДА. Добрынин, З.И. Жолдакова Система, реализующая комбинаторно-численный подход к проблеме прогноза свойств химических соединений. Прогноз канцерогенности поли циклических ароматических углеводородов (ПАУ).//НТИ. Сер.2. - 2004. - № 1.-С. 14-18.

5. Максин М.В. Об одном подходе к проблеме комбинированного использования логических и численных методов в интеллектуальном анализе данных. // НТИ. Сер.2. •

2004.-№10.-С. 14-19.

6. Харчевникова Н.В., Блинова В.Г., Добрынин Д.А., Максин МЗ., Жолдакова З.И. Применение ДСМ-метода и квантово-химических расчетов для прогноза

канцерогенностн и хронической токсичности галогензамещенных алифатических углеводородов. // НТИ. Сер.2. - 2004.12.- С. 21-28.

7. Максин М.В. Архитектура интегрированной ДСМ-снстемы интеллектуального анализа гибридных данных. // НТИ. Сер.2. - 2006. - № 9,- С. 10-17.

ЛИТЕРАТУРА

1. Финн В. К. «Об особенностях ДСМ-метода как средства интеллектуального анализа данных»//НТИ. Сер. 2-2001 5-стр. 1-3.

2. Финн В. К. Синтез познавательных процедур и проблема индукции. // НТИ. Сер. 2. — 1999.1-2.-С. 8-45.

3. Маневич С. И„ Харчсвникова Н. В., Дьячков П. Н. «Прогнозирование контрпродуктивных свойств химических соединений при комбинированном использовании структурных формул и численных энергетических параметров» // НТИ. Сер,2. - 2000. - № 5.

4. Маневич С.И. Расчет дескрипторов соединений органической химии // НТИ, Сер.2. -199б.-Вып,5-б,

5. Панкратов Д.В. Логические и программные средства качественного анализа социологических данных. Автореферат диссертации на соискание ученой степени к. т. н. М. 2001

6. Блинова В.Г., Добрынин A.A. Языки представления химических структур в интеллектуальных системах для конструирования лекарств // НТИ. Сер. 2. - 2000. - № 6.-С. 14-21.

7. Fayyad, U. М., Piatetsky-Shapiro, G., Smyth, P. "From Data Mining to Knowledge Discovery in Databases" // AI Magazine 17(3); 37-54,1996.

8. Lavrac, N., Keiavnou, E., Zupan B. "Intelligent Data Analysis in Medicine" it Encyclopedia of Computer Science and Technology 42:113-157 / Eds. A. Kent et al., Dekker, New York, 2000.

9. Виноградов Д. В. "Формализация правдоподобных рассуждений в логике предикатов" //НТИ. Сер. 2. - 2000.-№11. - С. 17-20.

10. Mitchell, Т. Machine Learning, McGrow Hill, 1997.

11. Qumlan,R. J. "Induction of decision trees" //Machine Learning, 1: SI - 106,1986.

12. Kramer, S. "Structural Regression Trees" // Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), 812-819, AAAI Press/MIT Press, 1996.

13. Clark, P., Niblett, T. "The CN2 Induction Algorithm'' П Machine Learning, 3(4):261 - 283, 1989.

14. Michalski, R. S., Mozetic, I., Hong, J., Lavrac, N. "The multi-purpose incremental teaming system AQ15 and its testing application on three medical domains." // Proceedings of 5th National Conference on Artificial Intelligence, 1041-1045, Morgan Kaufmann, I9S6.

15. S. Muggleton, S., Feng, C. "Efficient induction of logic programs" //Proceedings of the 1st Conference on Algorithmic Learning Theory^ 368 -381,1990.

16. Quintan, J. R., Cameron-Jones, R. M. "FOIL: A Midterm Report" H Proceedings of the 6th European Conference on Machine Learning 667:3 - 20, Springer-Verlag, 1993.

17. Muggleton, S. "Inverse Entailment and Piogol" // New Generation Computing, Special Issue on Inductive Logic Programming 13(3-4): 245 - 286, Ohmsha, 1995.

18. DesJardins, M., Gordon D. F. "Evaluation and selection of biases in machine teaming" ¡1 Machine Learning Journal 5:1—17,1995.

19. Финн В. К. "Правдоподобные выводы н правдоподобные рассуждения" // Итога науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 2S. - М.: ВИНИТИ, 1988-С. 3-84.

20. Забежайло М. И. "Формальные модели рассуждений в принятия решений: приложение ДСМ-метода в системах интеллектуального управления и автоматизации научных исследований" // НТИ. Сер. 2. -1996. - № 5-6. - С. 20 - 33.

21. Bristol, D.W., Wachsman, J.T., Greenwell, A. "Introduction: The NIEHS Predictive-Toxicology Evaluation Project" // Environmental Health Perspectives, 104 (Supplement 5): 1001-1010,1996.

22. Bahler, D., Bristol, D.W. "The induction of rules for predicting chemical carcinogenesis in rodents" // Intelligent Systems for Molecular Biology, 29-37 / Eds. L. Hunter, D. Searls, and J. Shavlick, Menlo Park, CA: AAAI/MIT Press, 1993.

23. Quinlan, J.R. C4.5 Programs for Machine Learning, Morgan Kaufmann, 1993.

24. Sebag, M., Rouveirol, C. "Tractable induction and classification in first-order logic via stochastic matching" // Proceedings of the ISth International Joint Conference on Artificial Intelligence 888-893, Morgan Kaufinann, 1997.,

2S

25. Dehaspe, L,, De Raedt, L. "Mining Association Rules in Multiple Relations" // Proceedings of the 7th International Workshop on Inductive Logic Programming, 1297:125 - 132,1997.

26. De Raedt, L„ Van Laer, W. "Inductive Constraint Logic" H Proceedings of the 5th ■ Workshop on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence,

Springer Verlag, 1995.

27. Dehaspe, L. "Maximum Entropy Modeling with Clausal Constraints" // Proceedings of the 7th International Workshop on Inductive Logic Programming, 1297:109-124, 1997.

28. Blinova, V.O., Dobiynin, D.A., Finn, V.K., Kuznetsov, S.O., Pankratova, E.S. "Toxicology Analysis by Means of the JSM-method" // Proceedings of PTC Workshop at the 5th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2001), 2001.

29. Финн В. К. «Правдоподобные рассуждения в интеллектуальных системах типа ДСМ» //Итоги науки и техники. Сер. Информатика. -М,: ВИНИТИ, 1991 — Вып. 15

30. Blinova, V., Dobrynin, D.A. "Languages for Representing Chemical Compounds for Intelligent Systems of Chemical Design" // Automated Documentation and Mathematical Linguistics, 3,2000.

31. Blockeel, H., De Raedt, L. "Top-Down Induction of First-Order Logical Decision Trees" // Artificial Intelligence, 101(1-2): 285 - 297, 1998,

32. Pfahringer, B. "(Tbe Futility of) Trying to Predict Carcinogenicity of Chemical Compounds" // Proceedings of PTC Workshop at the 5th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2001), 2001.

33. Gonzalez, J. A., Holder, L. В., Cook, D. J. "Application of Graph-Based Concept Learning to the Predictive Toxicology Domain" // Proceedings of PTC Workshop at the 5th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2001), 2001.

34. Lavrac, N,, Keravnou, E., Zupan B. "Intelligent Data Analysis in Medicine" // Encyclopedia of Computer Science and Technology 42:113-157 / Eds. A. Kent et al., Dekker, New York, 2000.

35. Aba, D.W. "Case-Based Learning Algorithms" // Proceedings of Case-Based Reasoning Workshop, 147 -158/Ed. Ray Bareiss, Morgan Kaufmann, 1991

36. Kuznetsov, S., Obiedkov, S. Comparing performance of algorithms for generating concept lattices. Journal t>f Experimental and Theoretical Artificial Intelligence, 14 (2-3): pp. 189 -216,2002.

37. А ишаков О. M., Скворцов Д. П., Финн В. К. "Логические средства экспертных систем типа ДСМП // Семистика и информатика. - 1986 - В lin. 28. - С. 65 - 101.

38. Фини В. К. "Правдоподобные выводы и проблемы автоматического порождения теорий из базы фактов" // Интенсиональные логики и логическая структура теорий: Тезисы докладов IV соь етско-финсхого коллоквиума но логике, Телави, 1985, - С, 108 -

. 114.

39. М. В. Базилеьский. Метод молекулярных орбит и реакционная способность органических молекул. - М,: Химия, 1969

40. Кузнецов С. О. ДСМ-метод как система автоматического обучения // Итоги науки и техники. Сер. Информатика--М.: ВИНИТИ, 1991 - Вып. 15

41. Flesher J.W., Horn J., Lehner A.F. Molecular modeling of carcinogenic potential in polycyclic hydrocarbons ¡/J. A{olec. Struct. (Theochem) -1996. -V,362,-P.29-49.

42. Объедков С .А. "Алгоритмы н методы теории решеток и их применение в машинном обучении" П Автореферат диссертации на соискание учЕной степени кандидата технических наук, Москва, 2003

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ В НАУКАХ О ЖИЗНИ.

1.1 Немного о терминологии.

1.2 Задачи, цели и инс i румен i ы ИАД.

1.2.1 Язык примеров.

1.2.2 Язык гипотез.

1.2.3 Алгоритм обучения.

1.3 Примеры задач для ИАД в науках о жизни.

1.3.1 Исследование канцерогенности веществ (токсикоюгия).

1.3.2 Медицина.

1.4 выводы.

ГЛАВА 2. КОМБИНИРОВАННОЕ ИСПОЛЬЗОВАНИЕ ЛОГИЧЕСКИХ И ЧИСЛЕННЫХ МЕТОДОВ В ИНТЕЛЛЕКТУАЛЬНОМ АНАЛИЗЕ ДАННЫХ: ДСМ + ХЮККЕЛЬ.

2.1 ДСМ-мг/год АПГ.

2.2 ДСМ-сис1ема прогнозирования контрпродуктивых свойс1в химичгских соединений.

2.3 квантово-механическии модуль сис1емы.

2.4 модуль ДСМ-анализа числовых характеристик (мыод интервалов).

2.5 Числовая величина как ДСМ-оьъг.к1.

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

2.7 Итоги.

ГЛАВА 3. АРХИТЕКТУРА ИНТЕГРИРОВАННОЙ ДСМ-СИСТЕМЫ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ГИБРИДНЫХ ДАННЫХ.

3.1 Обобщгнип понятия сходства.

3.2 Архи i еюура программной сис i емы.

3.2 1 Структуры данных.

3.2 2 Компоненты ядра системы.

3.2.3 Компоненты настройки системы.

3.2.4 Алгоритм построения решетки сходств для ДСМ-гипотез 11-го типа.

3.2.5 Алгоритм доопределения объектов с помощью решетки сходств.

3.3 ФКСП и регрессия (реализация и экспсримеш).

3.3.1 Линейная регрессия как сходство числовых величин.

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

По данным Национальной токсикологической программы США (U.S. National Toxicology Program, NTP), в настоящее время зарегистрировано около 100,000 химических веществ, используемых в производстве, и ежегодно в этот список добавляется около 1,000 соединений. Влияние на человеческий организм известно лишь для 15% из них, хотя человек может быть подвержен их воздействию во время производства, использования продуктов и утилизации отходов, и все они, так или иначе, становятся частью окружающей нас среды -воздуха, воды и почвы. Ещё меньше известно о канцерогенности этих веществ, так как экспериментальные исследования в данной области являются весьма дорогостоящими и времяёмкими: стандартный тест на канцерогенность одного химического вещества в рамках NTP включает в себя 2 года биопроб на грызунах и стоит около 2 миллионов долларов. Компьютерные системы анализа кон1рпродуктивных свойств химических соединений, предоставляющие прогноз этих свойств, позволили бы значительно сократить время и стоимость таких исследований. Особое место среди этих систем занимают системы интеллектуального анализа данных (ИАД), характеризующиеся способностью использовать существующие знания и приводить обоснование сделанного прогноза.

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

Целыо диссертационных исследований являлось создание интегрированной системы интеллектуального анализа гибридных данных, и её апробация в прогнозировании контрпродуктивных свойств классов химических соединений.

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

1. Разработка архитектуры интегрированной системы интеллектуального анализа гибридных данных, с учётом следующих технических требований:

• возможность распараллеливания вычислительно-сложных этапов работы системы с целью снижения времени работы и требований к аппаратному обеспечению

• возможность работы в условиях, когда не все данные могут быть размещены в оперативной памяти - для масштабируемости системы в зависимости от объёма анализируемых данных

• возможность сохранения результатов работы системы (в том числе и промежуточных) перманентно

2. Исследование возможных путей учёта числовых характеристик в рамках логико-комбинаторного анализа

3. Систематизация числовых характеристик химических соединений, релевантных решаемым задачам прогноза, а также методов вычислений этих характеристик

4. Апробация системы в решении задач прогнозирования контрпродуктивных свойств выделенного класса химических соединений

Актуальность работы определяется тем, что для качественного изучения объекта необходимо использование наукоемких его моделей и моделей процессов, в которых он участвует, и численные модели исторически являются наиболее широким классом таких моделей. Гибридное (структурно-числовое) описание объекта является более информативным, а интегрированные методы должны сделать анализ более полным и точным. Разработанная интеллектуальная система позволяет обогащать имеющиеся данные о контрпродуктивных свойствах химических соединений числовыми характеристиками этих соединений (которые вычисляются автоматически или предоставляются экспертом), а затем проводить анализ с целью выявления причин наличия таких свойств и прогнозирования. Архитектура же, в которой выполнена система, делают её легко расширяемой в смысле используемых методов анализа и легко масштабируемой в смысле применимости для решения практических задач разного объёма данных.

Разработанная в диссертации система прогнозирования контрпродуктивных свойств химических соединений является интеллектуальной системой типа ДСМ (ИнтС-ДСМ) [12].

Интеллектуальные системы типа ДСМ основаны на ДСМ-методе автоматического порождения гипотез (АПГ), реализующем автоматизированные правдоподобные рассуждения (порождение гипотез о причинах свойств, вывод по аналогии, процедуры объяснения начального состояния БД) [84].

ИнтС-ДСМ представляет собой интерактивную систему, в которой на базе развитого логико-математического обеспечения, реализующего ДСМ-метод АПГ, осуществляется интеллектуальный анализ данных из БД с неполной информацией (БДНИ). ИнтС-ДСМ применяются для прогнозирования свойств структурированных объектов в БДНИ для задач фармакологии, медицины, технической диагностики и социологии.

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

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

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

3. Задачи анализа гибридных данных сведены к классу задач, решаемых ДСМ-методом

4. Спроектирована и реализована расширяемая, масштабируемая и распараллеливаемая версия ДСМ-решателя, включая модель данных и алгоритмы работы на разных этапах.

5. Реализован модуль для квантово-механического расчёта числовых характеристик класса химических соединений

При разработке ИнтС-ДСМ использовались:

- принципы гибридного представления химических соединений, предложенные в статьях Маневича С.И. [75,79];

- модель канцерогенности ПАУ, разработанная в ПИИ экологии человека и гигиены окружающей среды;

- версия решателя задач для ИнтС-ДСМ, представленная в диссертации Панкратова Д.В. [87];

- версия ФКСП-кодировщика структур химических соединений, разработанная в ходе диссертационных исследований Добрыниным Д.А. [55];

Следующие особенности работы определяют ее научную новизну:

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

2. Разработан распараллеливаемый алгоритм поуровневого построения решётки ДСМ-гинотез, оптимизированный для применения в задачах с трудоёмкими операциями нахождения сходства

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

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

1. Позволяет осуществлять внеэкспериментальный прогноз контрпродуктивных свойств химических соединений с учётом их структурных и числовых характеристик

2. Реализует важные элементы ДСМ-рассуждения - итерационное применение правил правдоподобного вывода (шага ДСМ-рассуждения) и стратегии ДСМ-рассуждения

3. Позволяет использовать статистический (вычислительный) анализ в сочетании с ДСМ-анализом

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

5. Является основой для создания ДСМ-систем НАД промышленного масштаба

По теме диссертации в настоящее время опубликовано 6 статей и 2 тезисов докладов.

Структура работы. Диссертация состоит из введения, трёх глав и заключения, приложений и списка литературы.

Основные результаты работы.

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

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

3. Разработан распараллеливаемый алгоритм иоуровневого построения решётки ДСМ-гииотез, оптимизированный для применения в задачах с трудоёмкими операциями нахождения сходства

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

5. Реализован модуль для квантовомеханического расчёта числовых характеристик класса химических соединений

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

Заключение

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

Частью системы является квантовомеханический модуль, позволяющий (для класса химических соединений) вычислять энергетические характеристики соединения и строить структуру его метаболита; этот шаг реализует идею «обогащения» исходных данных перед последующим шагом поиска закономерностей (data mining). Надо заметить, что в данном случае происходит именно «обогащение» данных (а не просто их клонирование/проецирование), так как при этом используется содержательная модель некоей части изучаемого явления (а именно, процесса метаболизма как составляющей процесса проявления канцерогенных свойств вещества).

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

Разработанная программная ДСМ-система также претворила в жизнь важные элементы ДСМ-рассуждения, не реализовывавшиеся ранее -итерационное применение правил правдоподобного вывода (шага ДСМ-рассуждения) и стратегии ДСМ-рассуждения. Кроме того, лежащая в основе её архитектура обладает следующими важными свойствами:

• Стабильное высокопроизводительное ядро с элементами распараллеливания наиболее трудоёмких операций

• Гибкий механизм настройки на задачи предметной области - без ущерба для производительности системы в целом

• Чёткий интерфейс доступа к данным, позволяющий работать с данными безотносительно того, где эти данные фактически находятся (в оперативной памяти, на диске, в базе данных и т.д.)

• «Поуровневый» алгоритм построения решетки гипотез, предъявляющий минимальные требования к объему «одновременно» доступных данных и тем самым позволяющий эффективное кэширование данных.

Дальнейшее развитие системы видится как раз в реализации заложенного в её архитектуре потенциала - как в области программного воплощения достижений ДСМ-науки, так и в придании ей характеристик программной системы промышленного масштаба. Среди таких характеристик видятся следующие:

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

• Удобный пользовательский интерфейс как важный элемент человеко-машинной системы. Интуитивный графический интерфейс превращает программную систему в настоящею помощника исследователя.

• Интеграция с современными системами квантовомеханических расчётов и моделей изучаемых процессов с целыо повышения содержательности входных данных.

• Интеграция с современными системами статистического анализа данных с целыо расширения доступных системе инструментов анализа.

1. Bristol, D.W., Wachsman, J.T., Greenwell, Л. "1.troduction: The NIEIIS Predictive-

2. Toxicology Evaluation Project" // Environmental Health Perspectives, 104 (Supplement 5): 1001-1010, 1996.

3. Srinivasan, A., King, R.D., Muggleton, S.H., Sternberg, M.J.E. "'I he predictivetoxicology evaluation challenge" // Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, 1 -6, Morgan-Kaufmann, 1997.

4. Tennant, R.W., Spalding, J., Stasiewicz, S., Ashby, J. "Prediction of the outcome ofrodent carcinogenicity bioassays currently being conducted on 44 chemicals by the National Toxicology Program" // Mutagenesis, 5:3-14, 1990.

5. Bahler, D., Bristol, D.W. "The induction of rules for predicting chemicalcarcinogenesis in rodents" // Intelligent Systems for Molecular Biology, 29-37 / Eds. L. Hunter, D. Searls, and J. Shavlick, Menlo Park, CA: AAAI/MIT Press, 1993.

6. Srinivasan, A., King, R.D., Muggleton, S., Sternberg, M.J.E. "Carcinogenesis

7. Predictions Using ILP" // Proceedings of the 7th International Workshop on Inductive Logic Programming, 1297:273-287, 1997.

8. Kramer, S., Pfahringer, В., Helma, C. "Mining for Causes of Cancer: Machine1.arning Experiments at Various Levels of Detail" // Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97), AAAI Press, 1997.

9. Quinlan, J.R. C4.5 Programs for Machine Learning, Morgan Kaufmann, 1993.

10. Kramer, S. "Structural Regression Trees" // Proceedings of the Thirteenth National

11. Conference on Artificial Intelligence (AAAI-96), 812-819, AAAI Press/MIT Press, 1996.

12. Fayyad, U. M., Piatetsky-Shapiro, G., Smyth, P. "From Data Mining to Knowledge

13. Discovery in Databases" IIA1 Magazine 17(3): 37-54, 1996.

14. Codd, E. F. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate, E. F. Codd and Associates, 1993.

15. Lavrac, N., Keravnou, E., Zupan B. "Intelligent Data Analysis in Medicine" // Encyclopedia of Computer Science and Technology 42:113-157 / Eds. A. Kent et al, Dekker, New York, 2000.

16. Финн В. К. «Об особенностях ДСМ-метода как средства интеллектуального анализа данных» // НТИ. Сер. 2 2001 - № 5 - стр. 1 -3.

17. Компания RuleQuest Research, http://wwvv.rulequest.com/

18. Muggleton, S. "Inverse Entailment and Progol" // New Generation Computing, Special issue on Inductive Logic Programming 13(3-4): 245 286, Ohmsha, 1995.

19. Финн В. К. «Правдоподобные выводы и правдоподобные рассуждения» // Ито1и науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 28. М.: ВИНИТИ, 1988 - С. 3 -84.

20. Desjardins, М., Gordon D. F. "Evaluation and selection of biases in machine learning" // Machine Learning Journal 5:1—17, 1995.

21. Rissanen, J. "Modeling by shortest data description" // Automatica 14:465 471,1978.

22. Srinivasan, A., King, R.D., Bristol, D.W. "An assessment of submissions made to the Predictive Toxicology Evaluation Challenge" // Proceedings of the 16th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1999.

23. Sebag, M. "Delaying the Choice of Bias: A Disjunctive Version Space Approach" // Proceedings of International Conference on Machine Learning 444 452, 1996.

24. Sebag, M., Rouvcirol, С. "Tractable induction and classification in first-order logicvia stochastic matching" // Proceedings of the 15 th International Joint Conference on Artificial Intelligence 888-893, Morgan Kaufmann, 1997.

25. Mitchell, T. Machine Learning, McGrow I Iill, 1997.

26. King, R. D., Srinivasan, A., Dehaspe L. "WARMR: A Data Mining Iool for Chemical Data"

27. Ileima, C., Gottmann, I:., Kramer, S. "Knowledge Discover}' and Data Mining in Toxicology" // Statistical Methods in Medical Research 9: 329 358, 2000.

28. De Raedt, L., Van Laer, W. "Inductive Constraint Logic" // Proceedings of the 5th Workshop on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence, Springer Verlag, 1995.

29. Mannila, H., Toivonen, II. "Levelwise Search and Borders of Theories in Knowledge Discovery" // Data Mining and Knowledge Discovery 1(3): 241 258, 1997.

30. Алгоритм поиска глобального сходства в системах типа ДСМ.

31. Han, П.Н., Kumar, V., Shekhar, S., Ganesh, M., Srivastava, J. "Search framework for mining classification decision trees" // Technical Report TR-96-023, Department of Computer Science, University of Minnesota, Minneapolis, 1996.

32. Provost, F., Aronis, J., Buchanan, B. "Rule-space search for knowledge-based discovery" // CIIO Working Paper IS 99-012, New York University, 1999.

33. Korf, R. II. "Artificial Intelligence Search Algorithms" // Algorithms and Theory of Computation Handbook, CRC Press, 1999

34. Кузнецов С. О. «ДСМ-метод как система автоматического обучения» // Итогинауки и техники. Сер. Информатика.-М.: ВИНИТИ, 1991 Вып. 15

35. Финн В. К. «Правдоподобные рассуждения в интеллектуальных системах типа

36. ДСМ» // Итоги науки и техники. Сер. Информатика. М.: ВИНИТИ, 1991 -Вып. 15

37. Виноградов Д. В. «Формализация правдоподобных рассуждений в логике предикатов» // НТИ. Сер. 2. 2000. - № 11. - С. 17-20.

38. De Raedt, L., Van Laer, W. "How to Upgrade Propositional Learners to First Order Logic: Л Case Study" // Machine Learning and Its Applications 102-126, 2001.

39. Clark, P., Niblett, T. "The CN2 Induction Algorithm" // Machine Learning, 3(4):261 -283, 1989.

40. Dehaspe, L. "Maximum Entropy Modeling with Clausal Constraints" // Proceedings of the 7th International Workshop on Inductive Logic Programming, 1297:109-124, 1997.

41. Dehaspe, L., De Raedt, L. "Mining Association Rules in Multiple Relations" // Proceedings of the 7th International Workshop on Inductive Logic Programming, 1297:125-132, 1997.

42. Plotkin, G. "A note on inductive generalization" // Machine Intelligence, 5:153 -163 / Eds. B. Meltzer and D. Mitchie, Edinburgh University Press, 1970.

43. Agrawal, R., Srikant, R. "Fast Algorithms for Mining Association Rules" // Proceedings of the 20th International Conference on Very Large Databases, 487 -499, 1994.

44. Michalski, R. S., "A Theory and Methodology of Inductive Learning," // Machine Learning: An Artificial Intelligence Approach / Eds. R. S. Michalski, J. Carbonell and T. Mitchell, TIOGA Publishing Co., Palo Alto, pp. 83-134, 1983.

45. Provost, I7. J., Fawcett, T. "Robust Classification Systems for Imprecise Environments" // Machine Learning Journal, 42 (3), March 2001.

46. Woo, Y.-T. "Predictive Toxicology Challenge (PTC) 2000-2001: Л Toxicologist's View and Evaluation" // Proceedings of PTC Workshop at the 5th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD2001), 2001.

47. Blinova, V., Dobrynin, D.A. "Languages for Representing Chemical Compounds for1.telligent Systems of Chemical Design" // Automated Documentation and Mathematical Linguistics, 3, 2000.

48. Blockeel, II., De Raedt, L. 'Top-Down Induction of First-Order Logical Decision Trees" // Artificial Intelligence, 101(1 -2): 285 297, 1998.

49. Blockeel, II. et al "First order models for the Predictive Toxicology Challenge 2001" // Proceedings of PTC Workshop at the 5th European Conference on Principles and Practice of Knowledge Discoveiy in Databases (PKDD 2001), 2001.

50. Pfahringer, В. "('I he Futility of) Trying to Predict Carcinogenicity of Chemical Compounds" // Proceedings of PTC Workshop at the 5th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2001), 2001.

51. Gonzalez, J. A., Holder, L. В., Cook, D. J. "Predictive Toxicology Challenge: Modelof Toxicology Prediction for Male Rats" // http://www.informatik.uni-freiburg.de/~ml/ptc/comprehensiblemodels/uta.pdf

52. Cook, D. J., Holder, L. B. "Substructure Discovery Using Minimum Description Length and Background Knowledge" // Journal of Artificial Intelligence Research, 1:231-255, 1994.

53. Bunke, II., Allermann, G. "Inexact graph matching for structural pattern recognition" // Pattern Reognition Letters, 1(4): 245 253, 1983.

54. Burch, R. W. "Semeiotic Data Fusion" // Proceeding of 3rd International Conference of Information Fusion (Fusion-2000)

55. Финн В. К. «Правдоподобные выводы и проблемы автоматическою порождения теорий из базы фактов» // Интенсиональные логики и логическая структура теорий: Тезисы докладов IV советско-финского копоквиума по логике, Телави, 1985. С. 108 - 114.

56. Аншаков О. М., Скворцов Д. П., Финн В. К. «Логические средства экспертныхсистем типа ДСМ» // Семиотика и информатика. 1986 - Вып. 28. - С. 65 -101.

57. Лейбов А. Е. «Автоматическое кодирование химических структур кодом ФКСП» // Итоги науки и техники.

58. Блинова В. Г., Добрынин Д. А. «Язык ФКСП описания химической структуры соединения» //1ГГИ. Сер. 2. 2001. - № 6. - С. 14-21.

59. Gamberger, D., Lavrac, N., Groselj, С. "Diagnostic Rules of Increased Reliability for Critical Medical Applications" // AIMDM, 361 365, 1999.

60. Datta, P., Kibler, D. F. "Learning Prototypical Concept Descriptions" // Machine Learning • Proceedings of the 12th International Conference ICML-95, 158 166 / Eds. A. Prieditis and S. Russell, Morgan Kaufmann, 1995.

61. Lavrac, N. "Data Mining in Medicine: Selected Techniques and Applications"

62. Quinlan, R. J. "Induction of decision trees" // Machine Learning, 1: 81 106, 1986.

63. Newell, A., Simon, II. A. Human problem solving Prentice-Hall, Englewood Cliffs, NJ, 1972.

64. Quinlan, J. R., Cameron-Jones, R. M. "FOIL: A Midterm Report" // Proceedings of the 6th European Conference on Machine Learning 667: 3 20, Springer-Verlag, 1993.

65. S. Muggleton, S., Feng, C. "Efficient induction of logic programs" // Proceedings of the 1st Conference on Algorithmic Learning Theory, 368 -381, 1990.

66. Вирт H. Алгоритмы + Структуры данных = Программы. М.: Мир. 1985

67. Langley, P., Simon, Н., Bradshaw, G. "Heuristics for empirical discovery" // Computational Models of Learning. / Ed. Bole, L., Springer, Berlin, 1987

68. Morin, J. "Learning relational cliches with contextual generalization", PhD thesis, School of Information Technology and Engineering, University of Ottawa, Ontario, Canada, 1999.

69. Забежайло М. И. «Формальные модели рассуждений в принятии решений: приложение ДСМ-метода в системах интеллектуального управления и автоматизации научных исследований» // НТИ. Сер. 2. 1996. - № 5-6. - С. 20 -33.

70. Aha, D.W. "Case-Based Learning Algorithms" // Proceedings of Case-Based Reasoning Workshop, 147 158 / Ed. Ray Bareiss, Morgan Kaufmann, 1991

71. Miller, G. A. "'I he magical number seven, plus minus two: Some limits on our capacity for processing information", Psychological Review, 63, 81-97, 1956.

72. Григорьев П. A. «Sword-системы или ДСМ-системы для цепочек, использующие статистические соображения» // НТИ. Сер. 2. 1996. - № 5-6. -С. 45-51.

73. Маневич С. И., Харчевникова Н. В., Дьячков Г1. II. «Прогнозирование контрпродуктивных свойств химических соединений при комбинированном использовании структурных формул и численных энергетических параметров» // НТИ. Сер.2. 2000. - Вып.5.

74. Маневич С. И. «Расчет дескрипторов соединений органической химии» // НТИ. Сер.2, 1996.-Вып.5-6.

75. Аншаков О. М. Об одной интерпретации ДСМ-метода автоматического порождения гипотез. // НТИ. Сер. 2. 1999. - № 1-2. - С. 45-53.

76. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М: Наука, 1984. 312с. Решение полной проблемы собственных значений методом вращений.

77. Дьячков II.II., Маневич С.И. Автоматизированная система прогнозирования канцерогенности полициклических углеводородов и их производных методом Хюккеля //ИТИ. Сер.2. 1996. - Вып.7.

78. Маневич С.И., Н.В. Харчевникова, II.H. Дьячков. Прогнозирование контриродуктивных свойств химических соединений при комбинированном использовании структурных формул и численных энергетических параметров //НГИ. Сер.2. 2000. - Вып.5.

79. М. В. Базилевский. Метод молекулярных орбит и реакционная способность органических молекул. М.: Химия, 1969

80. Путрин А.В. Диссертация на соискание степени кандидата технических наук. ВИНИТИ, 2000

81. Kuznetsov, S., Obiedkov, S. Comparing performance of algorithms for generating concept lattices. Journal of Experimental and Theoretical Artificial Intelligence, 14 (2-3): pp. 189-216,2002.

82. Объедков C.A. "Алгоритмы и методы теории решеток и их применение в машинном обучении" // Автореферат диссертации на соискание учёной степени кандидата технических наук, Москва, 2003

83. Финн В. К. Синтез познавательных процедур и проблема индукции. // НТИ. Сер. 2.- 1999.-№ 1-2.-С. 8-45.

84. Дьячков П.Н. Квантово-химические расчеты в изучении механизма действия и прогнозе токсичности чужеродных соединений. // Итоги науки и техники. Сер. Токсикология. Т. 16. М.: ВИНИТИ, 1990.

85. Von Szentpaly, L. Carcinogenesis by polycyclic aromatic hydrocarbons: a multilinear regression on new type PMO indexes II J Am Chemo. Soc. 1984. -Vol. 106 (20).-6021-6028.

86. Панкратов Д.В. Логические и программные средства качественного анализа социологических данных. Автореферат диссертации на соискание ученой степени к. т. н. М. 2001