автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Машинное обучение на узорных структурах

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

САМОХИН Михаил Валерьевич МАШИННОЕ ОБУЧЕНИЕ НА УЗОРНЫХ СТРУКТУРАХ

Специальность 05.13.17 Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Москва - 2006

Работа выполнена во Всероссийском институте научной и технической информации (ВИНИТИ) Российской академии наук.

Научный руководитель: доктор физико-математических наук

Кузнецов Сергей Олегович

Официальные оппоненты: доктор технических наук,

профессор

Вагин Вадим Николаевич

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

им. В. А. Трапезникова РАН

Защита состоится " ' " июня 2006 г. в 11 ч. на заседании диссертационного совета Д 002.026.01 во Всероссийском институте научной и технической информации (ВИНИТИ) Российской академии наук по адресу: 125190, Москва, ул. Усиевича, д. 20.

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

Автореферат разослан " ^^ " мая 2006 г.

Учёный секретарь диссертационного совета

кандидат физико-математических наук1 Филимонов Дмитрий Алексеевич

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

Каменская М. А.

zoojzA

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

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

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

При решении задач типа "структура-активность" (Structure-Activity Relationship, см., например, [4]) структуры соединений часто представляются различными дескрипторными языками (например, язык ФКСП — фрагментарный код суперпозиции подструктур [5]), имеющих простую, программную, реализацию на основе теоретико-множественных операций и отношений над объектами.

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

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

Цель и задачи исследования. Разработка методов приближенного представления помеченных графов — проекций, реализация эффективных алгоритмов вычисления проекций графов, интеграция процедур вычисления проекций на графах с различными методами машинного обучения, а также расширение решателя ДСМ-метода автоматического порождения гипотез добавлением подсистемы, реали^д^ц^ onopawiH— сходства на проекциях. Предлагаемый алгебраический под>^дтовВдЙет1 д

С.-Петербург ОЭ 200Ся кт УШ

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

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

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

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

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

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

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

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

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

3. Сочетание математических и программных средств построения решеток и средств обработки данных, представленных помеченными графами.

Практическая значимость работы связана с созданием программ автоматического построения приближенного описания помеченных графов, интегрированных в систему интеллектуального анализа данных ОиОА [7] для решения задач из различных предметных областей (фармакология, химия) с использованием различных методов машинного обучения. Использование разработанного средства построения приближенного описания помеченных графов вместе с методами машинного обучения позволяет эффективнее решать задачи анализа данных, представленных помеченными графами. Например, при решении задач прогнозирования

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

Личный вклад диссертанта. Работа продолжает развитие методов обобщённого представления данных, на которых операция сходства, (определяемая как алгебраическая операция с некоторыми свойствами) задана как полурешёточная операция сходства [8,9]. Личный вклад диссертанта состоит в разработке эффективных методов решения задачи построения приближенного описания помеченных графов и реализации эффективных программных средств, а также проведении исследований с использованием этих средств.

АПРОБАЦИЯ РАБОТЫ

Результаты работы докладывались на научных семинарах ВИНИТИ РАН и Механико-математического факультета МГУ им. М.В. Ломоносова, 8-й национальной конференции по искусственному интеллекту (КИИ'2002), Коломна, 2002; 6-й международной конференции "Информационное общество, интеллектуальная обработка информации, информационные технологии" (НТИ-2002), Москва, 2002; 12-й международной конференции по понятийным структурам (12th International Conference on Conceptual Structures (ICCS'04)), Huntsville, AL, USA, 2004; 9-й национальной конференции по искусственному интеллекту (КИИ'2004), Тверь, 2004; 13-й международной конференции по понятийным структурам (13th International Conferenece on Conceptual Structures (ICCS'05)), Kassel, Germany, 2005; 15-й международной конференции по индуктивному логическому программированию (15th International Conferenece on Inductive Logic Programming (!LP'05)), Bonn, Germany, 2005; 12-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-12), Звенигород, 2005; 1-ой международной конференции "Системный анализ и информационные технологии" (САИТ-2005), Переславль-Залесский, 2005; Научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в бизнесе" (диплом "Лучший доклад"), Москва, ГУ-ВШЭ, 2006; XIII Российском национальном конгрессе "Человек и лекарство" (3 место в конкурсе работ молодых учёных на симпозиуме "Биоинформатика и компьютерное конструирование лекарств"), Москва, 2006.

Публикации. Основное содержание диссертационной работы изложено в 11 публикациях, среди которых 5 работ — в трудах российских конференций, 3 работы — в рецензируемых трудах международных конференций, и 3 работы — в рецензируемых российских периодических изданиях.

Структура и объем диссертации. Диссертация состоит из четырёх глав, заключения и списка литературы. Общий объем работы — 125 стра-

ниц. Список литературы включает 124 названия.

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

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

В первой главе приведены основные определения и результаты из области теории упорядоченных множеств и теории решеток, анализа формальных понятий (АФП), узорных структур, а также рассмотрены основные идеи и методы машинного обучения на графах. Сформулированы определения и даны характеристики четырёх методов машинного обучения — ДСМ-метода автоматического порождения гипотез, индуктивного построения деревьев решений (метода С4.5), наивного метода Байеса (в котором применяется формула Байеса в предположении, что вероятности значений признаков распределены независимо) и метода порождения правил с исключениями RIPPER, которые были использованы для экспериментальных проверок возможностей приближенного метода описания помеченных графов (проекций), предложенного в настоящей работе.

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

Пусть G и М суть множества, называемые соответственно множествами объектов и признаков, а / С G х М — отношение. Для g <Е G, т £ М имеет место glm если объект g обладает признаком т. Тройка К = (G, М, /) называется формальным контекстом. Для произвольных А С G и В С М соответствие Галуа определяется следующей парой отображений:

А' •= {т е М | glm для всех g с Л}, В' - {g е G | glm для всех т е В}.

Пара множеств (А, В) таких, что А С G, В С М, А' = В и В' = А называется формальным понятием контекста К с (формальным) объёмом А и (формальным) содержанием В.

Множество всех понятий формального контекста К образует решётку (обозначаемую через ®(/Q) со следующими операциями:

Л(а„В,) = (ПлдПл)'), = ((fW-f>/)-

/е/ /е/ jeJ /е/ /е/ j<=J

По основной теореме АФП любая полная решётка изоморфна решётке понятий некоторого формального контекста. В качестве объектов этого контекста можно, например, выбрать Л-неразложимые элементы, а в качестве признаков — V-неразложимые элементы исходной решётки.

Многозначный формальный контекст есть четвёрка (G, М, W, I), где G, М, W — множества (объектов, признаков и значений признаков, соответственно), а / — тернарное отношение J С G х М х W, задающее значение w признака т, причём:

(g,m,w) £ J и (g,m,v) € J влечёт w — v

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

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

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

Пусть Е есть множество, называемое множеством объектов, (D, П) — нижняя полурешётка, а 5 \ Е ь-у D — отображение, сопоставляющее каждому объекту из Е его описание в полурешётке (D, П), которая полна, т.е. инфимум ПБ определён для каждого подмножества В множества D. Тогда (£, (D, \ 1), 6) называется узорной структурой {pattern structure).

Элементы D называются узорами. Порядок на узорах задаётся обычным образом через операцию инфимума: cCd<=>cC\d = с, и называется порядком поглощения (субсумирования).

Для узорной структуры (£, (Д П), <$) и произвольных А С Е и d, е D определена пара отображений:

А° .= ПееА6(е), d° .= {е е Е | d О 6(e)},

которые задают соответствие Галуа между множествами (2е, С) и (D, Q.

Узорное понятие узорной структуры (E,(D,n),5) есть пара (A,d), где А С Е, d £ D, Л° = d и А — d°. Множество А называется объёмом, а d — узорным содержанием узорного понятия.

В силу определения узора, для d £ D d00 = d, а операция (-)00 является операцией замыкания (она идемпотентна, монотонна и экстенсивна).

Узорные понятия структуры (Е, (D, П), находятся во взаимнооднозначном соответствии с формальными понятиями некоторого контекста (Е,М,1), называемого контекстом представления. Формальные понятия контекста представления имеют те же формальные объёмы, что и узорные понятия.

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

множество признаков в исходных данных в явном виде отсутствует, и поэтому вычисление узорных понятий возможно лишь в стратегии "снизу-вверх" (в смысле отношения порядка С на узорных понятиях), т.е. от минимальных объёмов (и максимальных содержаний) к максимальным объёмам (и минимальным содержаниям). Во-вторых существенным отличием является вычислительная сложность. Например, задача вычисления отношения С для множеств помеченных графов является NP-полной (поскольку задача проверки изоморфизма графа подграфу NP-полна [10]), а вычисление операции Г NP-трудно. В то же время вычисление отношения С и операции Л в формальных контекстах связано с выполнением элементарных операций на битовых строках.

Отображение ф ■ D —> D называется оператором проекции, если выполнены следующие условия:

1. если х С у, то ф(х) L ф(у) (монотонность),

2. а) ф(х) Q х

b) Vx, Vy, lz: у П. ф(х) =Ф- у = ф(г) (равномерное сжатие)

3. ф(ф(х)) = ф{х) (идемпотентность).

Любая проекция ф полной полурешётки (D, П) сохраняет операцию Р, т.е., \/Х, У G D, ф(Х П Y) - ф{Х) Л ф{У).

Каждый объем узорной структуры (Е, (D, П), ф о 5) есть объем контекста представления (£,(ДГ),<5). Если d есть узорное содержание структуры (£, (Д П), 5), то ф{й) есть узорное содержание структуры {Е, (А Р), ф о <5), для которого ф{й)00 С d.

В этой же главе обсуждаются проблемы и задачи машинного обучения на данных, представленных помеченными графами, объясняется необходимость разработки и использования помеченных графов для решения практических задач. Для проведения машинных экспериментов, результаты которых обсуждаются в четвёртой главе, были выбраны четыре метода машинного обучения (ДСМ-метод, метод С4.5, наивный метод Байеса (Naïve Bayes) и метод RIPPER), а их краткие описания также представлены в этой главе.

Наш подход к обучению на такого рода данных, представленных помеченными графами, основан на порождении замкнутых множеств помеченных графов и их приближений. С одной стороны, этот подход связан с вычислением наиболее частных (наименее общих) обобщений положительных и отрицательных примеров, который зарекомендовал себя б реальных практических приложениях ДСМ-метода [11], в том числе в открытом соревновании по предсказательной токсикологии [12]. С другой стороны, порождение (частых) замкнутых подмножеств признаков (или замкнутых фрагментов описаний) в последние годы интересует исследователей благодаря своей связи с вычислением ассоциативных правил, имеющих хорошую поддержку (support) и правдоподобие

(iconfidence) [13]. Этот факт объясняет недавний рост интереса к вычислению замкнутых графов в области разработки данных (Data Mining) [2].

В работе [8] была предложена полурешёточная операция сходства П на множествах помеченных графов.

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

В работе [9] были введены обобщённые определения ДСМ-гипотез для данных, на которых задана полурешёточная операция сходства, для этих целей используется понятие узорной структуры (Е, (Д П), 6). В случае бинарного объектно-признакового представления (формальные контексты), функция 6 сопоставляет каждому объекту множество бинарных признаков, а операция П является теоретико-множественной операцией пересечения f"), действующей на подмножествах множества признаков (т.е. образует систему замыканий [14] или семейство Мура [15] на подмножествах множества признаков).

Другим примером определения операции П может быть следующая полурештка на замкнутых интервалах [8]: для a,b,c,d С R, где а < Ь, с < d, [а, b)V\[c, d) — [min {а, с}, max {b, d}]. Такая полурешётка, где числа были значениями энергии активации, использовалась в экспериментах по предсказанию токсичности и канцерогенности различных классов химических соединений, описанных в четвёртой главе.

В [16] было определено несколько правил правдоподобного вывода, из которых в ДСМ-методе чаще всего используется метод сходства с запретом на контрпример.

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

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

Пусть (£, (D, П), <5) есть узорная структура, a w есть целевой при-

знак, разбивающий множество всех объектов Е на три непересекающиеся подмножества: положительных примеров Е+, отрицательных примеров Е и недоопределенных примеров ЕТ. Это разбиение задаёт три узорных подструктуры структуры (Е, (Д П), 8): (£+, (Д П), (Е ,(ДП),<5), (Е7, (Д П), д), где Ех П Е, =0 для г,/ е {+,-,г}, а Е+ и £_. и Ет--Е.

Узор /г € В есть положительная гипотеза, если ЗЛ с Е+ ■ А° = к, к°ПЕ = 0 и |/г°! > 1 (т.е. узорное содержание структуры (£+, (Д П), <5), которое не поглощается ни одним отрицательным примером, и входит не менее чем в два положительных примера).

Гипотеза Л покрывает пример в, если Л С 5(е). Если г р — недоопределенный пример, то К есть гипотеза в пользу положительной классификации объекта е, если к есть положительная гипотеза и к покрывает е. Аналогично определяется гипотеза в пользу отрицательной классификации объекта е.

Пример е € ЕТ классифицируется положительно, если есть положительная гипотеза в пользу его положительной классификации и нет гипотез в пользу его отрицательной классификации. Отрицательная классификация определяется аналогично. Объект остаётся недоопределенным, если нет гипотез в пользу отрицательной или положительной классификации или классификация противоречива, т.е. имеются гипотезы как в пользу положительной так и в пользу отрицательной классификации.

В [17] описаны модификации простого ДСМ-метода сходства, в которых гипотезы определяются иначе. Один из вариантов ДСМ-метода — метод последовательного покрытия гипотезами на основе структурного сходства, который использовался нами в экспериментах (см. ниже). Эта стратегия порождает подмножество множества всех минимальных гипотез, которое покрывает примеры в обучающей выборке. Хотя подобная стратегия зависит от заданного на множестве объектов порядка, использование такой процедуры вместо процедуры порождения всех гипотез является оправданным по нескольким причинам: процедура имеет хорошую вычислительную сложность и хорошую точность приближения к "полной" стратегии (построения ДСМ-гипотез с запретом на контрпример) на многих реальных массивах данных.

Использование графов для представления данных в машинном обучении сопряжено с необходимостью решения таких задач, как проверка изоморфизма графа графу (не доказана ни ЫР-полнота проверки изоморфизма графов, ни возможность ее полиномиального решения в общем случае), графа подграфу (МР-полная задача), а также поиск максимальных общих подграфов множества графо&. Для некоторых классов графов доказано существование полиномиальных алгоритмов для решения этих задач. Например, в работе [18] приведён алгоритм проверки изоморфизма графов для класса графов с ограниченной степенью вершин, имеющего полиномиальную временную сложность. В работе [19]

предложен алгоритм проверки изоморфизма планарных графов за линейное время.

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

Помеченный граф Г есть пятёрка вида {(V,1),(Е,Ь), £), где V — множество вершин, Е С V х V - множество рёбер, I: V С - функция, сопоставляющая метки вершинам, Ь: Е —> £ - функция, сопоставляющая метки рёбрам.

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

Для пары помеченных графов Г| := ((Уь 1{), (£ь Ь{), С) и Гг = ((1/2, /2), (£2. Ьч), С) будем говорить, что Г] доминирует над Г2 или Гг < Г1 (или Г2 является подграфом Г)), если существует взаимнооднозначное соответствие : ¥2 • У\ такое, что оно 1) сохраняет ребра: (и, да) е £2 =>• с Е\, 2) учитывает равенство (порядок) на

метках.

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

На множествах графов с метками вершин и рёбер из некоторого множества С определим операцию пересечения П следующим образом:

Для помеченных графов X, У, {X} П {У} = {7\1 < X, У, < X, У ¿„ ^ (множество всех максимальных общих подграфов графов X и У). В общем случае, для помеченных графов Х\,. .,Хь,У1,. ,Ут, {*!, П {Г,,..., Гт} := МАХ<(Ц.ДШ П {ВД, где МАХ<&) вы-

бирает максимальные элементы из множества 2 относительно заданного порядка <.

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

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

смысле отношения доминирования) общих подграфов графов из первых двух, а элементами множества й являются всевозможные множества Я = {Гь • • • ,Г„} помеченных графов такие, что для любой пары помеченных графов Г,,Г; е О, Г, ^ Г;.

Узором в таком случае будет замкнутое множество графов, т.е. множество графов X, обладающее свойством X = Х°°.

Рассмотрим ДСМ-гипотезы для массива данных, где положительные примеры описаны графами Г[,..,Г4, а отрицательные — графами Г5 и Г6. В данном случае {Г,} П {Г2} П {Г3} и {Г2} П {Г3} П {Г4} являются минимальными положительными гипотезами, в то время как {Г]} Г {Г2} П {Г3} П {Г4} не является положительной гипотезой (мы можем не использовать скобок в силу ассоциативности операции П).

Положительные примеры:

СН} — Г-ОН <"Н* — с — он СНз — с- ОН СИ) — г - п

„ II „ II ^ II - II © © © ©

NHг он а си» ОН С

а

Отрицательные примеры

СНз — с — Nb2 NH, — С — он МН; — с — 04

„I! ^11 I!

(Cs) с (о,) С (о,) с

NHi NH, ГЧз С NH, CI

Понятие замкнутого множества графов тесно связано с понятием замкнутого графа [2], используемого для вычисления ассоциативных правил на парах графов. Замкнутые графы определяются в работе [2] (в терминах так называемого "counting inference") следующим образом: для массива данных D (содержащего данные в форме помеченных графов), поддержка графа g, или support(g) есть множество (или размер множества) графов в D, у которых есть подграф, изоморфный графу g.

полурешётку по отношению к оператору П, а всякая конечная нижняя полурешётка может быть пополнена до решётки введением единичного (максимального) элемента. На замкнутых графах такая операция не может быть определена. В общем случае, в частично упорядоченном множестве замкнутых графов нельзя однозначно определить инфинумы и супремумы двух замкнутых графов. Тем не менее, существует тесная связь между понятием замкнутого графа и понятием замкнутого множества графов: для любого замкнутого графа g существует замкнутое множество графов Q такое, что g е Q. Для замкнутого множества графов Q любой граф g £ Q есть замкнутый граф.

Далее в этой главе обсуждаются вопросы и алгоритмы, предложенные различными авторами (например, [20,21]), связанные с канонической нумерацией графов, необходимые, в частности, для эффективного решения задачи проверки изоморфизма графов:

Графы Г! = ({VuU),{ExM),C) и Г2 = ((У2, /2), (Е2, Ь2), С) изоморфны (Г[ = Г2), если Г[ < Г2 и Г2 < Гь где < — порядок на графах (см. выше).

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

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

Путь в графе есть последовательность вершин, в которой каждая пара соседних вершин инцидентна: (vo, V\,..., u„)|Vl < k < n : (иц, vk) e E. Цикл — путь, в котором концы совпадают, т.е. vq = vn. Остовное дерево графа Г = (V,E) есть дерево Т = (V,E'),E' С Е.

Цикл в графе Г называется элементарным, если путь (vo, Vi, . , Vk), образовывающий его, содержит каждую вершину и, не более одного раза (иными словами это подграф, степень каждой вершины которого равна 2).

Для графа Г = {V,E),\V\ = п,\Е\ — т множество элементарных циклов может быть расширено так, чтобы образовать векторное пространство над {0,1}т. Если Г — связный граф, тогда размерность этого векторного пространства задаётся цикломатическим числом v — т — п + \.

Простейший способ определения этого векторного пространства (обозначаемого как С) заключается в поиске фундаментального базиса, связанного с остовным деревом. Напомним, что для остовного дерева Т = (V,E') графа Г = (V,E) добавление к дереву Т любого ребра из множества Е\Е' приводит к образованию одного цикла. Множество циклов, построенных таким образом, задаёт базис векторного пространства С. Большое количество работ посвящено поиску фундаментального ба-

зиса, например, [22] и в большинстве работ это понятие используется для перечисления множества элементарных циклов графа. В работе [23] было показано, что, к сожалению, таким способом может быть порождено 2" векторов, только малая часть из которых являются элементарными циклами.

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

Наша реализация операции П основана на использовании обычного теоретико-множественного пересечения П следующим образом. Для каждого примера е, описанного узором 6{в) = {Г} для некоторого помеченного графа Г, вычисляется множество всех связных подграфов, удовлетворяющих условию на размер проекции k = N. Каждый такой подграф объявляется бинарным признаком, а каждый пример е представляется множеством S(e) бинарных признаков, которые соответствуют подграфам Г. Тогда для примеров в\ и е2 пересечение S(ei) П5(е2) будет эквивалентно вычислению сходства описаний ф(5(е¡)) П тр(ё(е2)).

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

Эффективность процедуры порождения всех подграфов произвольного графа также связана с эффективностью проверок изоморфизма графу и изоморфизма подграфу. Существует несколько известных алгоритмов для решения этих задач, в частности, алгоритм В. D. McKay [20] проверки изоморфизма графу и алгоритм J. R. Ullmann [25] для проверки изоморфизма подграфу. В связи со сложностью указанных проверок в нашем подходе мы используем ¿-проекции исходных графов. Идея проекции, описанная для общей полурешётки, может быть уточнена для случая полурешётки на графах следующим образом.

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

Пусть Г = ((1/, 1), (£, Ь),С) — помеченный граф, тогда множество Sj = {Г, = ((V,, /•), (£*, М) I Г» - связный граф, Г, < Г и Щ < k} будем называть k-вершинной проекцией (или просто k-проекцией) графа Г.

Таким образом, ¿-проекция помеченного графа Г есть множество всех подграфов (с точностью до изоморфизма) графа Г с числом вершин не более, чем k. Тогда, fe-проекция множества помеченных графов определяется так:

Пусть Q = {Гь ,Г„}, где Г, = ((V,, /),(£,, Ь)) — помеченный граф, тогда множество Sg = MAX.'('_:"=lS- J будем называть k-вершинной проекцией (или просто k-проекцией) множества графов Q.

тогда множество Бд = будем называть И-вершинной про-

екцией (или просто 1г-проекцией) множества графов 0.

Пусть Г - помеченный граф, 5Г = /(Г) есть множество подграфов из ¿-проекции, тогда /(Г) - есть оператор проекции.

Отметим, что в определении ¿-проекции выбирается антицепь (множество несравнимых элементов) в соответствующей решётке (25г,П), однако при программной реализации, основанной на порядковом шкалировании, графы вначале представляются множеством всех своих подграфов (используется порядковый идеал соответствующей решётки (25г, П)). Формально это соответствует переходу к модификациям определений операции П на множестве графов, ¿-проекции графа и множества графов, в которых применение оператора МАХ< устраняется.

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

Число порождаемых таким образом бинарных признаков может быть достаточно велико. В связи с этим мы используем ещё один метод сокращения числа признаков — редуцирование [14].

Признак т г М контекста К = (С,7И,/) редуцируем, если т' = (~]{п' { п € М & п' э т'} или т' — О. В [14] показано, что, если т - редуцируем, то решётки контекстов с признаком т и без признака т изоморфны: »(б.Л!,/) = <В(0,М\{т}, I Г) (в х (М\{т}))).

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

4-проекция

|111 о

Пусть Г = {(У,1),{Е,Ь),С) — помеченный граф, тогда множество 7г = {Г, = ((К, /*), (£*, ¿>*)) | Г, - связный граф, 1\ < Г и / < |К| < к} будем называть (1,1г)-вершинной проекцией (или просто {I, ^-проекцией) графа Г.

Тогда определение /¿-проекции эквивалентно определению (1, АО-вершинной проекции. Поскольку УГ(Тг С то верно следующее: ТГ = /(Г) есть множество подграфов из (/, ^-проекции, тогда /(Г) -есть оператор проекции.

Ещё один вариант определения оператора проекции на графах возникает при рассмотрении циклических систем, состоящих из элементарных циклов.

Пусть Г = ((V,/),(£, &)>£) — помеченный граф, VI», Е V >

2, тогда множество Ср — {Г, = ((К,/»),(£», М) I — связный граф, ••/■и, е V, deg{v,) >2, Г* < Г, \Е,\ - |К| +1 < к} называется к-циклической проекцией (1 < /г < |£| - |У| +1) помеченного графа Г = ((У, I), (£, Ь),С), V», € V ¿ецЫ > 2.

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

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

Пусть Г = {{V, 1),{Е,Ь),С) - помеченный граф, 1/(Г) = |У| - |£| + 1 > 0, тогда множество В* = {Г* = ((К, /*)> (£*, К), С) | Г» — связный граф, < с, Г« £ Г, |К| < к} называется с-циклической к-проекцией (1 < с < |£|-|У| + 1, 1 < к < |У|) помеченного графа Г - ((V,/),(£,£>), £).

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

Общая схема предлагаемого алгоритма построения проекции (для всех вариантов определения) на графах выглядит следующим образом:

Этап 1. Для каждого графа Г е 0 порождается множество всех подграфов "размером" не более, чем к (в качестве "размера" может быть взято число вершин, число минимальных циклов и т.д., в зависимости от

вида выбранной проекции). Строится множество Бд — Угее^г-

Этап 2. Используя построенное множество подграфов Эд для множества графов алгоритм порождает бинарную таблицу размером \0\ х |5<;|, в которой строки соответствуют графам из множества 0, столбцы подграфам из множества Бд. На пересечении строки г и столбца / стоит 1, если граф Л е Бд изоморфен подграфу графа Г, (Л < Г,), иначе стоит 0.

Очевидным недостатком такого подхода можно назвать необходимость перечисления всех подграфов с заданными ограничениями на размер — поиска множества, которое образует покрытие каждого графа из 0. В тоже время, в определении ^-проекции предлагается компактное представление проекции графа в виде множества максимальных подграфов с заданными ограничениями на размер. Для нас основной целью разработки приближенного описания графов (проекции) была реализация такого описания, на котором можно было бы эффективно реализовать операцию сходства (поиска максимальных общих подграфов исходных графов). Поскольку поиск максимальных общих подграфов является с вычислительной точки зрения более сложной, чем проверка изоморфизма графа подграфу, оказалось целесообразным свести трудоёмкие операции на графах к операциям на битовых строках, которые соответствуют проекциям. Таким образом, самым сложным в предлагаемом подходе является Этап 1. Этап 2 имеет линейную сложность и по памяти и по времени. На Этапе 1 последовательно обходятся все вершины графа Г = (V, Е) и начиная с одновершинного подграфа, состоящего только из выбранной вершины, последовательно расширяется до множества подграфов с заданным ограничением на число вершин.

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

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

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

множества, которое определяет в графе А подграф, изоморфный графу Г (в случае проверки изоморфизма графа подграфу). В тоже время алгоритм применим для определения изоморфизма графов. Для проверки неизоморфности графов используются различные инварианты графов, которые позволяют в большом количестве случаев не использовать точного поиска изоморфизма.

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

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

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

На этом шаге порождается множество кандидатов размера т + 1 по заданному множеству кандидатов размера т графа Г. Подграф Л' размера т + 1 порождается путем добавления вершин и рёбер из графа Г \ Л к подграфу Л размера т. Простым, но эффективным средством избежать построения одних и тех же подграфов несколько раз при порождении кандидатов является использование порядка, заданного на множестве вершин графа. В нашей реализации на множестве вершин был задан линейный порядок, соответствующий последовательности вершин на входе алгоритма.

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

Далее в этой главе описываются алгоритмы вычисления различных определений проекций.

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

Алгоритм, реализующий определение с-циклической ¿-проекции, объединяет в себе алгоритмы вычисления ¿-проекции и циклической k-проекции. Сначала алгоритм вычисляет элементарные циклы, как на первом шаге алгоритма вычисления ¿-циклической проекции. Из подграфа Л графа Г, множество рёбер которого £Л - Er\ UceR^c) (на "древесной" части графа Г), выбираются все одновершинные подграфы. Затем алгоритм достраивает подграфы из множества кандидатов, начиная с одновершинных подграфов и подграфов, состоящих из одного элементарного цикла, как в алгоритме построения ¿-проекции.

Как уже было отмечено, основой для появления и применения предлагаемого подхода описания данных является ДСМ-метод автоматического порождения гипотез [11]. В работах [27-29] были описаны подходы с использованием графов для представления исходных данных, а в [27] описывается операция сходства на графах. Кроме того графы используются для построения ФКСП-кодов [5,30]. Собственно обучение на графах с помощью ДСМ-метода было программно реализовано только в работе [27] (подход основан на поиске сходства в виде установления общих изоморфных подграфов), в остальных случаях для решения задач использовался язык ФКСП-кодов и определённая на нем операция сходства. Использование сходства на основе поиска максимальных общих подграфов для исходных графов не всегда является тривиальной задачей (из-за размера графов), а ФКСП-коды не достаточно гибки для описания некоторых задач, поэтому использование приближенного описания графов и определение сходства на основе проекций является одним из удобных способов описания.

Все алгоритмы были реализованы на языке Java и тестировались на компьютере с процессором Pill МоЫ1е-1ГГц, 640Мб ОЗУ, установленными операционной системой Windows 2000 SP4 и Java 2 VM фирмы Sun (версия 1.4.2).

По результатам ряда экспериментов были получены некоторые значения, характеризующие скорость работы описанных алгоритмов. Так, в среднем для вычисления ¿-проекции графов с числом вершин не более 100 и значением ¿ < 50 требуется не более 1 секунды. Для вычисления циклической ¿-проекции эксперименты проводились на относительно небольших графах (число элементарных циклов — не больше 20). Для значений k < 10 время вычисления проекции варьировалось от 1 до 10 секунд. Такие показатели в первую очередь связаны с тем, что в практических задачах подобные графы пока исследовались только в химических задачах. Поскольку метки почти всех вершин в подобных графах совпадают, то время вычисления проекции зависит от времени работы

процедуры проверки изоморфизма графов.

Другой характеристикой является число подграфов, составляющих проекцию множества графов. В таблице (см. ниже) приведены значения числа подграфов в ¿-проекции для множества графов из массива РТС для различных значений k. Обучающая выборка массива содержала 409 молекулярных графа и тестовая — 185 соединений, средний размер графов составлял 25 вершин и 26 рёбер для обучающей выборки, 45 вершин и 46 рёбер — для тестовой. При k = 9 для вычисления множества проекций потребовалось около 30 часов, однако построение бинарной объектно-признаковой таблицы пришлось прервать после почти 70 часов работы алгоритма (см. описание выше), общее число порождённых к этому моменту подграфов составило 561921. С ростом величины k число признаков в результирующей таблице быстро растёт, но процедура редуцирования на практике позволяет сократить эту величину в несколько раз.

проекция____1123 4 S 6 7 8

# признаков в таблице 22 95 329 1066 3275 9814 28025 76358

# признаков вредуц. таблице 22 72 153 373 812 1548 2637 3981

время редуцирования (сек.) j 1 1 2 5 16 57 219 883

При построении циклической ¿-проекции на данных, на которых проводились наши эксперименты, число порождённых подграфов было относительно небольшим (не превышало 30-50 подграфов для графов с не более чем 20 элементарными циклами). Основной причиной таких значений является большое число симметрий молекулярных графов массива.

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

Поскольку основной задачей этой работы является разработка и реализация метода описания данных, представленных помеченными графами, для сравнения результатов применения различных методов машинного обучения была использована система интеллектуального анализа данных QuDA [7]. В этой системе реализуется фрагмент ДСМ-метода и используется коллекция методов машинного обучения WEKA [31] (в частности, методы С4.5, Naïve Bayes и RIPPER).

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

одним из лучших методов во всех четырёх поло-видовых группах был вариант ДСМ-метода с запретом на контрпример (вместе с ФКСП-кодами в качестве языка описания соединений). В свою очередь, в нашей работе было указано, что использование проекций в качестве языка представления вместе со стратегией последовательного покрытия на основе структурного сходства (варианта ДСМ-метода) приводит к улучшению результата прогноза. Кроме того, были представлены результаты для группы крыс (самцов и самок), из которых видно, что использование проекций улучшает качество прогноза для всех методов машинного обучения на группе самцов крыс (МЯ). В тоже время для группы самок крыс (Р1?) качество прогноза не изменилось.

Развитием стало применение предлагаемого подхода при решении других химических задач. Качество результатов во всех экспериментах сравнивалось с аналогичными результатами, полученными с применением ФКСП-кодов в качестве языка описания. Так, были проведены эксперименты по исследованию токсичности спиртов. В этом эксперименте 89 соединений составляли обучающую выборку, 22 соединения были даны на прогноз, из которых 14 было предсказано правильно с применением ДСМ-метода, 1 соединение было предсказано ошибочно. Аналогичные показатели с использованием дескрипторного языка ФКСП для описания молекул были 8 и 2, соответственно.

В другой серии из четырёх экспериментов решалась задача поиска достаточных условий прохождения биотрансформации химических соединений в организме (использовались данные, представленные в [6]). Необходимое условие прохождения реакции в этой задаче определяется как наличие некоторого подграфа (реакционного центра) в молекулярном графе соединения, а достаточное условие как окрестность реакционного центра. Для описания соединений использовался вариант (I, /г)-проекций. Во всех четырёх экспериментах применением ДСМ-метода были получены результаты, совпавшие с результатами, полученными на ФКСП-кодах.

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

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

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

В качестве экспериментальных данных использованы структурные формулы веществ из классов бисиндолов и индолокарбазолов и данные по их цитотоксической активности in vitro и противоопухолевой активности in vivo из базы данных по противоопухолевым агентам ГУ РОНЦ им. H.H. Блохина РАМН. В проведённом эксперименте на массиве из 176 соединений (из которых 51 соединение было дано на прогноз) с применением ДСМ-метода 20 соединений были предсказаны (предсказания активности 19 соединений полностью совпали с экспертной оценкой, 1 соединение было предсказано ошибочно) и 31 соединение не предсказано. Несмотря на очень низкую полноту прогноза, которая связана с недостатком информации в обучающей выборке, предлагаемый метод описания является адекватным решаемой задаче.

Другой задачей, при решении которой был опробован предлагаемый метод, является задача анализа жалоб. Жалоба представляется в виде направленного ациклического графа, множество вершин которого V = Vp U V0 (Vp и V0 описывают действия жалобщика и его оппонента, соответственно), а множество рёбер представляют процесс коммуникации (ребра ориентированы от более ранних действий к более поздним). Решаемая задача состоит в поиске подсценариев, определяющих правомерность жалобы. В проведённых экспериментах было установлено, что почти все использованные методы обучения показывают относительно высокую точность предсказаний (60-71%). Процент предсказанных примеров не для всех методов оказывается достаточно высоким. Например, ДСМ-метод оказался самым "осторожным" методом, предсказав только 30% примеров, но с малым числом ошибок.

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

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

1. Кузнецов С. О., Самохин М. В. Порождение ДСМ-гипотез для данных, представленных раскрашенными графами // Труды 8-й национальной конференции по искусственному интеллекту (КИИ'2002). - М.: Физматлит, 2002. - С. 147-153.

2. Самохин М. В. Алгоритмы поиска сходства графов в системах

автоматического порождения гипотез с помощью ДСМ-метода при решении задач поиска связи структура-активность // Труды 6-й международной конференции "Информационное общество, интеллектуальная обработка информации, информационные технологии" (НТИ-2002). - М.: ВИНИТИ, 2002. - С. 424-427.

3. Ganter В., Grigoriev P. A., Kuznetsov S. О., Samokhin М. V. Concept-Based Data Mining with Scaled Labeled Graphs // Proc. 12th International Conference on Conceptual Structures (ICCS'04) / Ed. by H. Delugach, H. Pfeiffer, K. Wolff. - Springer-Verlag, 2004. -Vol. 3127. - P. 94-108. (Lecture Notes in Artificial Intelligence).

4. Самохин M. В. Анализ биоактивности химических соединений с использованием ДСМ-метода и приближенного описания молекулярных графов соединений // Труды 9-й национальной конференции по искусственному интеллекту (КИИ'2004). — М.: Физматлит, 2004. - С. 172-178.

5. Galitsky В. A., Kuznetsov S. О., Samokhin М. V. Analyzing Conflicts with Concept-Based Learning // Proc. 13th International Conferenece on Conceptual Structures (ICCS'05) / Ed. by F. Dau, M.-L. Mugnier, G. Stumme. - Springer-Verlag, 2005. - Vol. 3596. - P. 307-322. (Lecture Notes in Artificial Intelligence).

6. Kuznetsov S. O., Samokhin M. V. Learning Closed Sets of Labeled Graphs for Chemical Applications // Proc. 15th International Conferenece on Inductive Logic Programming (ILP'05) / Ed. by S. Kramer, B. Pfahringer. — Springer-Verlag, 2005. — Vol. 3625. — P. 190-208. (Lecture Notes in Artificial Intelligence).

7. Кузнецов С. О., Самохин М. В. Машинное обучение на данных, представленных помеченными графами // Труды 12-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-12) / ВЦ РАН. - М.: МАКС Пресс, 2005. - С. 150153.

8. Кузнецов С. О., Самохин М. В. Обучение на помеченных графах и их проекциях // Труды 1-й Международной конференции "Системный анализ и информационные технологии" (САИТ-2005) / ИСА РАН. - М.: КомКнига, 2005. - Т. 2. - С. 207-210.

9. Кузнецов С. О., Самохин М. В., Харчевникова Н. В. Прогнозирование контрпродуктивных свойств химических соединений на основе узорных структур: сравнительный анализ подходов. Часть 1 // НТИ, Сер. 2. - 2006. - № 1. - С. 1-8.

10. Кузнецов С. О., Самохин М. В., Харчевникова Н. В. Прогнозирование контрпродуктивных свойств химических соединений

на основе узорных структур: сравнительный анализ подходов. Часть 2 // НТИ, Сер. 2. - 2006. - № 2. - С. 1-10.

11. Самохин М. В. Вычисление сходства помеченных графов и их проекций // НТИ, Сер. 2. - 2006. - № 3. - С. 1-12.

СПИСОК ЛИТЕРАТУРЫ

[1] Kuznetsov S. О. Learning of Simple Conceptual Graphs from Positive and Negative Examples // Proc. 3rd European Conference on Principles of Data Mining and Knowledge Discovery (PKDD'99) / Ed. by J. Zytkow, J. Rauch. - Berlin; Heidelberg: Springer-Verlag, 1999,— Vol. 1704. — P. 384-392. (Lecture Notes in Artificial Intelligence).

[2] Yan X., Han J. CloseGraph: mining closed frequent graph patterns // Proc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD'03) / Ed. by L. Getoor, T. Senator, P. Domingos, С. Faloutsos. — New York, NY: ACM Press, 2003. — P. 286-295.

[3] Gonzalez J. A., Holder L. В., Cook D. J. Application of graph-based concept learning to the predictive toxicology domain // Proc. Workshop on Predictive Toxicology Challenge at the 5th Conference on Data Mining and Knowledge Discovery (PKDD'01) [Электронный ресурс] / Ed. by С. Helma, R. King, S. Kramer, A. Srinvasan. — 2001. Режим доступа: http://www.predictive-toxicology.org/ptc/.

[4] Molecular Similarity in Drug Design / Ed. by P. M. Dean. — London: Blackle Academic, 1995.

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

[6] Фабрикантова Е. Ф. Применение ДСМ-рассуждений для интеллектуального анализа данных и автоматического порождения гипотез о путях биотрансформации // НТИ, Сер. 2. — 2002. — No. 2. - Р. 8-44.

[7] Grigoriev P. A., Yevtushenko S. А., Grieser G. QuDA, а data miner's discovery environment: Tech. Rep. AIDA 03 06: FG Intellektik, FB Informatik, Technische Universität Darmstadt, September 2003. Режим доступа: http://www.intellektik.informatik.tu-darmstadt.de/ peter/QuDA.pdf.

[8] Кузнецов С. О. ДСМ-метод как система автоматического обучения // Итоги науки и техники. Сер. Информатика.— 1991.— Т. 15. - С. 17-54.

[9] Ganter В., Kuznetsov S. Pattern Structures and Their Projections // Proc. 9th International Conference on Conceptual Structures (ICCS'01) / Ed. by G. Stumme, H. Delugach. — Berlin; Heidelberg: Springer-Verlag, 2001,— Vol. 2120.- P. 129-142. (Lecture Notes in Artificial Intelligence).

[10] Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи, — М.: Мир, 1982.

[11] Финн В. К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ // Итоги науки и техники. Сер. Информатика. — 1991.- Т. 15. - С. 54-101.

[12] Blinova V. G., Dobrynin D. A., Finn V. К., Kuznetsov S. О., Pankrato-va E. S. Toxicology analysis by means of the JSM-method // Bioinfor-matics. - 2003. - Vol. 19. - P. 1201-1207.

[13] Pasquier N., Bastide Y., Taouil R., Lakhal L. Efficient Mining of Association Rules Using Closed Itemset Lattices // J. Inf. Systems. — 1999. — Vol. 24, No. 1.- P. 25-46.

[14] Ganter В., Wille R. Formal Concept Analysis: Mathematical Foundations. — Berlin; Heidelberg: Springer-Verlag, 1999.

[15] Биркгоф Г. Теория решеток. — М.: Наука, 1989.

[16] Mill J. S. A System of Logic, Ratiocinative and Inductive: Being a Connected View of the Principles of Evidence, and Methods of Scientific Integration. — London: J.W. Parker, 1843.

[17] Григорьев П. А., Евтушенко С. А. ДСМ-рассуждение как средство интеллектуального анализа данных. Результаты тестирования на наборах данных UCI // Труды 8-й национальной конференции по искусственному интеллекту (КИИ'2002). — М.: Физматлит, 2002. — С. 112-122.

[18] Luks Е. М. Isomorphism of graphs of bounded valence can be tested in polynomial time // J. Сотр. Syst. Sci. - 1982. - Vol. 25. - P. 42-65.

[19] Hopcroft J. E., Wong J. K. Linear time algorithm for isomorphism of planar graphs (preliminary report) // Proc. of the 6th annual ACM symposium on Theory of computing. — New York, NY: ACM Press, 1974.- P. 172-184.

[20] McKay B. D. Practical Graph Isomorphism // Congressus Numeran-tium. - 1981. - Vol. 30. - P. 45-87.

[21] Morgan H. L. The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service // J. Chem. Doc. - 1965. - Vol. 5, No. 2. - P. 107-113.

[22] Paton К. An algorithm for finding a fundamental set of cycles of a graph // Communications of the ACM. - 1969. - Vol. 12. — P. 514518.

[23] Mateti P., Deo N. On algorithms for enumerating all circuits of a graph // SIAM J. on Computing. - 1975. - Vol. 5. — P. 90-101.

[24] Deo N., Prabhu G. M., Krishnamoorthy M. S. Algorithms for generating fundamental cycles in a graph // ACM Transanctions on Mathematical Software. - 1982. - Vol. 8. - P. 26-42.

[25] Ullmann J. R. An algorithm for subgraph isomorphism // J. Association for Computing Machinery. - 1976. - Vol. 23, No. 1. - P. 31-42.

[26] Vismara P. Union of all the minimum cycle bases of a graph // Electronical J. of Combinatorics. - 1997,- Vol. 4, No. 1.— P. 73-87. Режим доступа: http://www.combinatorics.org.

[27] Лейбов A. E. Некоторые способы реализации операции сходства для химически ориентированных экспертных систем типа ДСМ // НТИ, Сер. 2. - 1996. - № 5-6. - С. 37-44.

[28] Забежайло М. И., Ивашко В. Г., Кузнецов С. О., Михеенкова М. А., Хазановский К. П., Аншаков О. М. Алгоритмические и программные средства ДСМ-метода автоматического порождения гипотез // НТИ, Сер. 2. - 1987. - № 10. - С. 1-13.

[29] Матвеев А. А. Алгоритм построения метаболической сети // НТИ, Сер. 2. - 2002. - № 6. - С. 35-45.

[30] Добрынин Д. А. Алгоритмы поиска фрагментов в молекулярных графах для автоматического кодирования химических структур в интеллектуальных системах для конструирования лекарств // НТИ, Сер. 2. - 2002. - № 6. - С. 51-57.

[31] Witten I. Н., Frank Е. Data Mining: Practical Machine Learning Tools with Java Implementations. — San Fransisco, CA: Morgan Kaufmann, 2000.

[32] Proc. Workshop on Predictive Toxicology Challenge at the 5th Conference on Data Mining and Knowledge Discovery (PKDD'01) [Электронный ресурс] / Ed. by C. Helma, R. D. King, S. Kramer, A. Srinvasan. — 2001. Режим доступа: http://www.predictive-toxicology.org/ptc/.

ООО "Алфавит 2000" Тираж 100 экз. Усл.-печ. л. 1,56 Формат 60x84 1/8 Подписано в печать 28.04.2006 г. тел.: 623-93-18, 623-08-10 www.alfavit2000.ru

IM 04 oi

Введение

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

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

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

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

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

1.1.3.1 Проекции узорных структур. 1.2 Машинное обучение и анализ данных.

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

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

ДСМ-методе.

1.2.2 Метод порождения правил с исключениями. RIPPER.

1.2.3 Наивный метод Байеса (Naive Bayes).

1.2.4 Методы индуктивного порождения деревьев решений.

Ф 2 Графы и их проекции

2.1 Общий взгляд.

2.2 Графы и узорные структуры.

2.3 Различные варианты проекций на графах.

3 Алгоритмическая реализация приближенного описания узорных структур

3.1 Общий взгляд.

3.2 Подробное описание.

3.2.1 Порождение кандидатов. f 3.2.2 Алгоритмы для различных вариантов проекции

3.2.3 Использование алгоритма в ДСМ-методе

3.2.4 Оценка быстродействия

4 Машинные эксперименты и результаты

4.1 Эксперименты с химическими данными.

4.1.1 Эксперименты на массиве РТС. ф 4.1.2 Проекции графов "на ROC-диаграмме" (результаты для массива РТС)

4.1.3 Эксперименты по исследованию токсичности спиртов.

4.1.4 Эксперименты по исследованию канцерогенности ариламинов

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

4.2 Анализ канцерогенности и токсичности в рамках модели "структура-активность". Использование комбинированного подхода.

4.2.1 Эксперименты по хронической токсичности и канцерогенности галогензамещённых алифатических углеводородов (ГАУ).

4.2.2 Результаты и обсуждение.

4.3 Эксперименты на массивах ПАУ.

4.3.1 Результаты и обсуждение.

4.3.2 Эксперимент на массиве Theochem [119].

4.4 Прогнозирование биологической активности гликозидов.

4.5 Эксперименты с графами жалоб.

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

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

В ряде работ последних лет в области машинного обучения и разработки данных (Machine Learning, Data Mining) внимание исследователей сосредоточено на проблеме обучения на данных, заданных помеченными графами (например, [1—7]).

При решении задач типа "структура-активность" (Structure-Activity Relationship, см., например, [8]) структуры соединений часто представляются различными дескриптор-ными языками (например, язык ФКСП — фрагментарный код суперпозиции подструктур [9]), имеющих простую, с вычислительной точки зрения, реализацию теоретико-множественных операций и отношений над объектами.

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

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

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

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

2. Исследовать особенности приближенного представления помеченных графов;

3. Разработать на основе метода алгоритмы и программные модули построения проекций;

4. Провести анализ особенностей разработанного подхода на большом экспериментальном материале.

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

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

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

3. Сочетание математических и программных средств построения решёток и средств обработки данных, представленных помеченными графами.

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

Положения, выносимые на защиту:

1. Метод приближенного представления помеченных графов;

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

3. Практическая значимость метода в машинном обучение и обработке данных

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

1. 8-й национальной конференции по искусственному интеллекту (КИИ'2002), Коломна, 2002;

2. 6-й международной конференции "Информационное общество, интеллектуальная обработка информации, информационные технологии" (НТИ-2002), Москва, 2002;

3. 12-й международной конференции по понятийным структурам (12th International Conference on Conceptual Structures (ICCS'04)), Huntsville, AL, USA, 2004;

4. 9-й национальной конференции по искусственному интеллекту (КИИ'2004), Тверь, 2004;

5. 13-й международной конференции по понятийным структурам (13th International Conferenece on Conceptual Structures (ICCS'05)), Kassel, Germany, 2005;

6. 15-й международной конференции по индуктивному логическому программированию (15th International Conferenece on Inductive Logic Programming (ILP'05)), Bonn, Germany, 2005;

7. 12-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-12), Звенигород, 2005;

8. 1 -ой международной конференции "Системный анализ и информационные технологии" (САИТ-2005), Переславль-Залесский, 2005;

9. Научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в бизнесе" (диплом "Лучший доклад"), Москва, ГУ-ВШЭ, 2006;

10. Х111 Российском национальном конгрессе "Человек и лекарство" (3 место в конкурсе работ молодых учёных на симпозиуме "Бионинформатика и компьютерное конструирование лекарств"), Москва, 2006

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

Заключение

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

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

В работе проведены сравнения классификации данных ряда массивов с использованием представления соединений в виде графов и в виде ФКСП с помощью четырёх методов машинного обучения. Результаты компьютерных экспериментов позволяют утверждать о состоятельности подхода, основанного на операторе проекции графов, поскольку он значительно сокращает временные затраты на анализ данных обучающей выборки и последующее применение полученных гипотез, с целью классификации, к данным тестовой выборки, в тоже время не приводя к большим информационным потерям (т.е. неправильным классификациям). Вместе с тем, эксперименты показывают оправданность применения техники редуцирования контекстов. Редуцирование контекста не приводит к изменениям результатов ДСМ-метода, приводит к несущественным изменениям результата метода порождения деревьев решений (5-10%) и приводит к малым изменениям (5-20%) для наивного метода Байеса и RIPPER.

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

Преложенный в этой работе подход требует решения ещё достаточно большого количества задач, которые можно разделить на два направления. Первое из них связано с представлением данных. Среди прочих выделим задачу, связанную с использованием 3D представления и различных вариантов представлений "между" чисто теоретико-графовым и 3D представлениями, позволяющие описывать пространственное расположение связей молекул (включая проблему изомерии). В Разделе 4 был приведён простой вариант решения и первые результаты на примере задачи прогнозирования биологической активности гликозидов.

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

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

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

2. применение в системе стандартных алгоритмов машинного обучения для выбора значимых признаков (feature selection) и/или разработка специального алгоритма, который позволит преодолеть проблему снижения точности предсказания с ростом размера проекций.

1. Borgelt C., Berthold M. R. Mining Molecular Fragments: Finding Relevant Substructures of Molecules // Proc. 2nd IEEE International Conference on Data Mining (ICDM'02)/Ed. by N. Zhong, P. Yu. — Piscataway, NJ: IEEE Press, 2002. — P. 51-58.i

2. Inokuchi A., Washio Т., Motoda H. Complete Mining of Frequent Patterns from Graphs:

3. Mining Graph Data // Machine Learning. — 2003. — Vol. 50, No. 3. — P. 321-354.

4. Washio Т., Motoda H. State of the art of graph-based data mining// j-SIGKDD-EN. — 2003. — Vol. 5, No. 1. — P. 59-68.

5. Yan X., Han J. gSpan: Graph-Based Substructure Pattern Mining // Proc. IEEE International Conference on Data Mining(ICDM'02). — Los Alamitos, CA: IEEE Computer Society, 2002. — P. 721-724.

6. Yan X., Han J. CloseGraph: mining closed frequent graph patterns // Proc. of the 9th

7. G ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

8. SIGKDD'03)/ Ed. by L. Getoor, T. Senator, P. Domingos, C. Faloutsos. — New York, NY: ACM Press, 2003. — P. 286-295.

9. Molecular Similarity in Drug Design / Ed. by P. M. Dean. — London: Blackie Academic, 1995.

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

11. Фабрикантова Е. Ф. Применение ДСМ-рассуждений для интеллектуального анализа данных и автоматического порождения гипотез о путях биотрансформации // НТИ, Сер. 2. — 2002. — No. 2. — Р. 8-44.

12. Биркгоф Г. Теория решеток. — М.: Наука, 1989.

13. Ganter В., Wille R. Formal Concept Analysis: Mathematical Foundations. — Berlin; Heidelberg: Springer-Verlag, 1999.

14. Davey B. A., Priestley H. A. Introduction to Lattices and Order. — Cambridge: Cambridge University Press, 2002.

15. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival. — Dordrecht;Boston: Reidel, 1982. — P. 445-470.

16. Кузнецов С. О. ДСМ-метод как система автоматического обучения // Итоги науки и техники. Сер. Информатика. — 1991. — Т. 15. — С. 17—54.

17. LiquiereM., Sallantin J. Structural Machine Learning with Galois Lattice and Graphs// Proc. 15th International Conference on Machine Learning (ICML'98)/ Ed. by J. Shav-lik. — San Fransisco, С A: Morgan Kaufmann, 1998. — P. 305—313.

18. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи.— М.: Мир, 1982.

19. Mitchell Т. Machine Learning. — The McGraw-Hill Companies, 1997.

20. Кузнецов С. О. Модели и методы автоматического обучения // Итоги науки и техники. Сер. Вычислительные науки. — 1991. — Т. 7. — С. 89—137.

21. Hutchinson A. Algorithmic Learning. — Oxford: Claredon Press, 1994.

22. King R. D., Srinivasan A., Dehaspe L. WARMR: A Data Mining tool for chemical data // J. Computer-Aided Molecular Design.— 2001.— Vol. 15, No. 2. — P. 173-181.

23. Kramer S. Structural Regression Trees // Proc. 13th National Conference on Artificial . Intelligence (AAAI'96). — Cambridge; Menlo Park: AAAI Press : MIT Press, 1996. —1. P. 812-819.

24. Финн В. К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ//Итоги науки и техники. Сер. Информатика.— 1991.— Т. 15.— С. 54—101.

25. Blinova V. G., Dobrynin D. A., Finn V. К., Kuznetsov S. О., Pankratova E. S. Toxicology analysis by means of the JSM-method//Bioinformatics.— 2003.— Vol. 19.— P. 1201-1207.

26. Pasquier N., Bastide Y., Taouil R., Lakhal L. Efficient Mining of Association Rules Using Closed Itemset Lattices //J. Inf. Systems. — 1999. — Vol. 24, No. 1. — P. 25-46.

27. Avidon V. V., Pomerantsev A. B. Structure-activity relationship oriented languages for chemical structure representation // J. Chem. Inf. Comput. Sci. — 1982. — Vol. 22, No. 4.— P. 207-214.

28. Kuznetsov S. O., Obiedkov S. A. Comparing performance of algorithms for generating concept lattices // J. of Experimental and Theoretical Artificial Intelligence. — 2002. — Vol. 14, No. 2-3. — P. 189-216.

29. Кузнецов С. О., Финн В. К. О модели обучения и классификации, основанной на операции сходства // Обозрение прикладной и промышленной математики. — 1996. — Т. 3, № 1.— С. 66-90.

30. Anshakov О. М., Finn V. К., Skvortsov D. P. On axiomatization of many-valued logics associated with the formalization of plausible reasonings // Stud. Log. — 1989. — Vol. 25, No. 4. — P. 23-47.

31. Mill J. S. A System of Logic, Ratiocinative and Inductive: Being a Connected View of the Principles of Evidence, and Methods of Scientific Integration. — London: J.W. Parker, 1843.

32. Michalski R., Stepp R. Machine Learning: An Artifical Intelligence Approach / Ed. by J. C. R.S.Michalski, T. Mitchell. — San Mateo, CA: Morgan Kaufmann, 1983.

33. Fisher D. Iterative optimization and simplification of hierarchical clusterings // J. Artificial Intelligence Research. — 1996. — Vol. 4. — P. 147-179.

34. Cohen W. W. Fast Effective Rule Induction // Proc. 12th International Conference on Machine Learning (ICML'95).— San Fransisco, CA: Morgan Kaufmann, 1995.— P. 115-123.

35. Furnkranz J., Widmer G. Incremental Reduced Error Pruning// Proc. 11th International Conference on Machine Learning (ICML'94).— San Fransisco, CA: Morgan Kaufmann, 1994.

36. Witten I. H., Frank E. Data Mining: Practical Machine Learning Tools with Java Implementations. — San Fransisco, CA: Morgan Kaufmann, 2000.

37. Quinlan J. R. Induction on Decision Trees //Machine Learning.— 1986.— Vol. 1, No. 1.— P. 81-106.

38. Quinlan J. R. C4.5: Programs for Machine Learning. — San Fransisco, CA: Morgan Kaufmann, 1993.

39. Quilllian M. R. Semantic Memory // Semantic Information Processing/ Ed. by M. Min-sky. — Cambridge, MA: MIT Press, 1968. — P. 227-270.

40. Sowa J. F. Conceptual Structures — Information Processing in Mind and Machine. — Reading, MA: Addison-Wesley, 1984.

41. Luks E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time//J. Сотр. Syst. Sci. — 1982. — Vol. 25. — P. 42-65.

42. Hopcroft J. E., Wong J. K. Linear time algorithm for isomorphism of planar graphs (preliminary report)// Proc. of the 6th annual ACM symposium on Theory of computing. — New York, NY: ACM Press, 1974. — P. 172-184.

43. Bron C., Kerbosch J. Finding all cliques of an undirected graph // Communications of the ACM. — 1974.

44. Raymond J. W. Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm // J. Chem. Inf. Comput. Sci. — 2002. — Vol. 42, No. 2.— P. 305-316.

45. McKay B. D. Practical Graph Isomorphism // Congressus Numerantium.— 1981.— Vol. 30. — P. 45-87.

46. Ullmann J. R. An algorithm for subgraph isomorphism // J. Association for Computing Machinery. — 1976. — Vol. 23, No. 1. — P. 31-42.

47. Kuramochi M., Karypis G. An efficient algorithm for discovering frequent subgraphs: Tech. Rep. 02-026. — Minneapolis, MN: University of Minnesota, 2002.

48. Inokuchi A., Washio Т., Nishimura K., Motoda H. A fast algorithm for mining frequent connected subgraphs: Research Report RT0448. — Tokyo: IBM Research, Tokyo Research Labaratoiy and Osaka University, 2002.

49. Кузнецов С. О., Самохин М. В., Харчевникова Н. В. Прогнозирование контрпродуктивных свойств химических соединений на основе узорных структур: сравнительный анализ подходов. Часть 1 // НТИ, Сер. 2. — 2006. — № 1. — С. 1-8.

50. Cook D. J., Holder L. В. Graph-Based Data Mining // IEEE Intelligent Systems. — 2000. — Vol. 15, No. 2. — P. 32-41.

51. Cameron-Jones R. M., Quinlan J. R. Efficient top-down induction of logic programs // SIGART Bulletin. — 1994. — Vol. 5, No. 1. — P. 33-42.

52. Muggleton S. Inverse Entailment and Progol // New Generation Computing.— 1995. — Vol. 13. — P. 245-286.

53. Provost E, Fawcett T. Robust classification for imprecise environments // Machine Learning. — 2001. — Vol. 42. — P. 203-231.

54. Braun J., Gugisch R., Kerber A., Laue R., Meringer M., Rucker C. MOLGEN-CID -A Canonizer for Molecules and Graphs Accessible through the Internet // J. Chem. Inf. Comput. Sci. — 2004. — Vol. 44, No. 2. — P. 542-548.

55. Nagle J. F. On ordering and identifying undirected linear graphs // J. Mathematical Physics. — 1966. — Vol. 7. — P. 1588-1592.

56. Арлазаров В. JI., Зуев И. В., Усков А. В., Фараджев И. А. Алгоритм приведения конечного неориентированного графа к каноническому виду // Журнал Вычислительной Математики и Математической Физики. — 1974. — Т. 14, № 4. — С. 734—747.

57. Randic М. On the recognition of identical graphs representing molecular topology // J. Chem. Phys. — 1974. — Vol. 1974. — P. 3920-3928.

58. Randic M. On canonical numbering of atoms in a molecule and graph isomorphism // J. Chem. Inf. Сотр. Sci. — 1977. — Vol. 17, No. 3. — P. 171-180.

59. Randic M., Brissey G. M., Wilkins C. L. Computer perception of topological symmetry via canonical numbering of atoms // J. Chem. Inf. Comput. Sci.— 1981. — Vol. 21, No. 1. — P. 52-59.

60. Hendrickson J. В., Toczko A. G. Unique numbering and cataloging of molecular structures//J. Chem. Inf. Comput. Sci. — 1983. — Vol. 23, No. 4. — P. 171-177.

61. Kvasnicka V., Pospichal J. Canonical indexing and constructive enumeration of molecular graphs //J. Chem. Inf. Comput. Sci. — 1990. — Vol. 30, No. 2. — P. 99-105.

62. Kvasnicka V., Pospichal J. An improved method on constructive enumeration of graphs//J. of Mathematical Chemistry. — 1992. — Vol. 9, No. 2. — P. 181-196.

63. Lukovits I. Isomer generation: Syntactic rules for detection of isomorphism // J. Chem. Inf. Comput. Sci. — 1999. — Vol. 39, No. 3. — P. 563-568.

64. Lukovits I. Isomer generation: Symantic rules for detection of isomorphism // J. Chem. Inf. Comput. Sci. — 1999. — Vol. 40, No. 2. — P. 361-366.

65. Morgan H. L. The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service // J. Chem. Doc. — 1965. — Vol. 5, No. 2.—P. 107-113.

66. Weininger D. SMILES, a chemical language and information system. 1. introduction to methodology and encoding rules // J. Chem. Inf. Comput. Sci. — 1988. — Vol. 28, No. 1.— P. 31-36.

67. Weininger D., Weininger A., Weininger J. L. SMILES. 2. algorithm for generation of unique SMILES notation // J. Chem. Inf. Comput. Sci. — 1989. — Vol. 29, No. 2. — P. 97-101.

68. Paton K. An algorithm for finding a fundamental set of cycles of a graph // Communications of the ACM. — 1969. — Vol. 12. — P. 514-518.

69. Mateti P., Deo N. On algorithms for enumerating all circuits of a graph // SIAM J. on Computing. — 1975. — Vol. 5. — P. 90-101.

70. Read R. C., Taijan R. E. Bounds on backtrack algorithms for listing cycles, paths and spanning trees// Networks. — 1975. — Vol. 5. — P. 90-101.

71. Syslo A. A. An efficient cycle vector space algorithm for listing all cycles of planar graph// SIAM J. on Computing. — 1981. — Vol. 10. — P. 797-808.

72. Deo N., Prabhu G. M., KrishnamoorthyM. S. Algorithms for generating fundamental cycles in a graph // ACM Transanctions on Mathematical Software. — 1982. — Vol. 8. — P. 26-42.

73. Horton J. D. A polynomial-time algorithm to find the shortest cycle basis of a graph // SIAM J. on Computing. — 1987. — Vol. 16, No. 2. — P. 358-366.

74. Dijkstra E. W. A note on two problems in connection with graphs // Numerische Math-ematik.— 1959.— Vol. 1. — P. 269-271.

75. Tierman J. An efficient search algorithm to find the elementary circuits of a graph // Communications of the ACM. — 1970. — Vol. 13. — P. 722-726.

76. Vismara P. Union of all the minimum cycle bases of a graph // Electronical J. of Combinatorics.— 1997.— Vol. 4, No. 1.— P. 73-87. Режим доступа: http://www.combinatorics.org.

77. Plotkin M. Mathematical basis of ring-finding algorithms in CIDS // J. Chem. Doc. — 1971.—Vol. 11.—P. 60-63.

78. Степанец Г. Ф. Базисные системы вектор-циклов с экстремальными свойствами в графах // Успехи математических наук АН СССР.— 1964.— Т. 19, № 2.— С. 171-175.

79. Зыков А. А. Теория конечных графов. I. — Новосибирск: Наука, 1969.

80. Filimonov D. A., Poroikov V. V. PASS: Computerized prediction of biological activity spectra for chemical substances // Bioactive Compound Design: Posibilities for Industrial Use. — Oxford: BIOS Scientific Publishers, 1996. — P. 47-56.

81. Filimonov D., Poroikov V., Borodina Y., Gloriozova T. Chemical similarity assessment through multilevel neighborhoods of atoms: Definition and comparison with the other descriptors //J. Chem. Inf. Comput. Sci. — 1999. — Vol. 39, No. 4. — P. 666-670.

82. Poroikov V. V., Filimonov D. A. PASS: Prediction of Biological Activity Spectra for Substances // Predictive Toxicology / Ed. by C. Helma. — N.Y.: Taylor & Frensis, 2005. — P. 459-478.

83. Нечепуренко M. И., Попков В. К., Майнагашев С. М., Кауль С. Б., Проскуряков В. А., Кохов В. А., Грызунов А. Б. Алгоритмы и программы решения задач на графах и сетях.— Новосибирск: Наука, 1990.

84. Лейбов А. Е. Некоторые способы реализации операции сходства для химически ориентированных экспертных систем типа ДСМ // НТИ, Сер. 2. — 1996. — № 5—6. — С. 37-44.

85. Забежайло М. И., Ивашко В. Г., Кузнецов С. О., Михеенкова М. А., Хазанов-ский К. П., Аншаков О. М. Алгоритмические и программные средства ДСМ-метода автоматического порождения гипотез // НТИ, Сер. 2. — 1987. — № 10. — С. 1—13.

86. Матвеев А. А. Алгоритм построения метаболической сети // НТИ, Сер. 2. — 2002. — №6.—С. 35-45.

87. Добрынин Д. А. Алгоритмы поиска фрагментов в молекулярных графах для автоматического кодирования химических структур в интеллектуальных системах для конструирования лекарств // НТИ, Сер. 2. — 2002. — № 6. — С. 51-57.

88. Кузнецов С. О., Самохин М. В., Харчевникова Н. В. Прогнозирование контрпродуктивных свойств химических соединений на основе узорных структур: сравнительный анализ подходов. Часть 2 // НТИ, Сер. 2. — 2006. — № 2. — С. 1-10.

89. Блинова В. Г., Добрынин Д. А., Жолдакова 3. И., Харчевникова Н. В. Изучение соотношений структура-токсичность спиртов с использованием ДСМ-метода // НТИ, Сер. 2. — 2001. — № 10. — С. 13-18.

90. Guilian W., Naibin В. Structure-activity relationships for rat and mouse LD50 of miscellaneous alcohols// Chemosphere. — 1998. — Vol. 35, No. 7. — P. 1475-1483.

91. Franke R., Grushka A., Benigni R. Prediction of rodent carcinogenecity of aromatic amins: a quantitative structure activity relationships model // Carcinogenesis.— 2001. — Vol. 22. — P. 1561-1571.

92. Korzekwa К. R., Jones J. R, Gillette J. R. Theoretical studies on cytochrome p-450 mediated hydroxylation: a predictive model for hydrogen atom abstractions // J. American Chemical Society. — 1990. — Vol. 112. — P. 7042-7070.

93. Yin H., Anders M., Korsekwa K-, Higgins L. A., Thummel К- E. Predicting safer chemicals: Predicting the rates of metabolism of halogenated alkanes // Proc. National Academy of Sciences of the USA.— 1995. — Vol.92. — P. 11076-11080.

94. Woo Y.-T., Lai D., McLain J. L., et al. Use of mechanism-based structure-activity relationships analysis in carcinogenic ranking for drinking water desinfection by-products // Environ. Health Perspect. — 2002. — No. 1. — P. 75-87.

95. The Carcinogenic Potency Database (CPDB), University of California, Berkley, USA. Режим доступа: http://potency.berkeley.edu/cpdb.html.

96. ГН 2.1.5.1315-03. Предельно допустимые концентрации (ПДК) химических веществ в воде водных объектов хозяйственно-питьевого и культурно-бытового водопользования. — 2003.

97. Канцерогенные вещества. Справочник. Материалы международного агентства по изучению рака / Под ред. А. Ф. Карамашевой. — Медицина, 1987.

98. Dipple A. Polynuclear Aromatic Carcinogens // Chemical Carcinogens / Ed. by С. E. Searle.— ACS Monograph No. 172. Washington, DC: Amer. Chem. Soc., 1976.— P. 245-314.

99. Yan L.-S. Study of carcinogenic mechanism of polycyclic aromatic hydrocarbons-extended bay region theory and its quantitative model // Carcinogenesis. — 1985. — No. 1. —

100. Badger G. M. The Chemical Basis of Carcinogenic Activity. — 1962.

101. Jerina D. M., Lehr R. E. Microsomes and Drug Oxidation / Ed. by V. Ullrich. — Oxford: Pergamon Press, 1977. — P. 709-720.

102. Lowe J. P., Silverman B. D. MO theory of ease of formation of carbocations derived from nonalternant polycyclic aromatic hydrocarbons // J. American Chemical Society.— 1984. — Vol. 106, No. 20. — P. 5955-5958.

103. Дьячков П. H. Квантовохимические расчеты в изучении механизма действия и токсичности чужеродных веществ // Итоги науки и техники. Сер. Токсикология. — 1990. — Т. 16.— С. 280.

104. Flesher J. W., Horn J., Lehner A. F. Molecular modeling of carcinogenic potential in polycyclic hydrocarbons // J. Molecular Structure (Theochem). — 1996. — Vol. 362, No. 1. — P. 29-49.

105. N-гликозиды производных индоло2,3-а.карбазола / А. А. Бахмедова, Л. Д. Гараева, О. В. Горюнова, Т. Д. Миникер, И. Л. Плихтяк, Л. В. Эктова, Т. П. Иванова и др. // Биоорганическая химия. — 1997. — Т. 23, № 8. — С. 667-674.

106. Мельник С. Я. Экспериментальная онкология на рубеже веков // Синтез и изучение гликозидов, производных бисиндола и родственных индоло2,3-а.карбазолов / Под ред. М. И. Давыдова, А. Ю. Барышникова. — М., 2003. — С. 281-293.

107. Апрышко Г. Н. Информационная система по противоопухолевым агентам // Российский биотерапевтический журнал. — 2002. — № 2. — С. 7—10.