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

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

ЛИПКИН Александр Аркадьевич

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2008

003447090

Работа выполнена в Российском государственном гуманитарном университете Научный руководитель доктор физико-математических наук,

профессор АНШАКОВ Олег Михайлович Официальные оппоненты доктор технических наук,

профессор ЕРЕМЕЕВ Александр Павлович кандидат технических наук, доцент ТАРАСОВ Валерий Борисович

Ведущая организация Вычислительный центр

Российской академии наук Защита состоится 22 октября 2008 г в 13-30 часов на заседании диссертационного совета Д 002 026 01

во Всероссийском институте научной и технической информации по адресу 125190, Москва, ул Усиевича, д 20а

С диссертацией можно ознакомиться в библиотеке ВИНИТИ РАН Автореферат разослан 15 сентября 2008 г

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

доктор технических наук, ЦВЕТКОВА

профессор Валентина Алексеевна.

Общая характеристика диссертации

ДСМ-метод1 автоматического порождения гипотез — это один из методов ИАД (Интеллектуального анализа данных)2 ДСМ-метод позволяет с помощью анализа имеющейся базы фактов сделать предположения о причинах наличия или отсутствия определенных свойств (целевые свойства) у объектов предметно области Этот метод предложил В К Финн [11-13] Примером задач, решаемых ДСМ-методом, может служить выявление причинно-следственных закономерностей вида структура-активность в фармакологии, анализ сложных химических соединений и белковых структур в химии [10], медицинская диагностика[9], криминалистика, анализ социального поведения[5]

ДСМ-метод решает две задачи

1) обнаружить закономерную связь между структурой объектов и множествами целевых свойств,

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

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

Характерной чертой ДСМ-метода является сочетание трех разновидностей правдоподобных рассуждений

' Формализация структурной индукции ДСМ-метода, или JSM-метода, как его иногда еще называют, берет свое начало от известного английского философа, логика, историка и социолога Д С Милля, чьи инициалы и составляют название метода [7]

2 Интеллектуальный анализ данных (англ Data Mining, Knowledge Discovery) - выявление скрытых закономерностей или взаимосвязей между переменными в больших массивах необработанных данных Подразделяется на задачи классификации, моделирования и прогнозирования и другие

Термин "Data Mining" веден Григорием Пятецким-Шапиро в 1989 году Английский термин "Data Mining" не имеет однозначного перевода на русский язык (добыча данных, вскрытие данных, информационная проходка, извлечение данных/информации) поэтому в большинстве случаев используется в оригинале Наиболее удачным непрямым переводом считается термин "интеллектуальный анализ данных" (ИАД)[14]

и N

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

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

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

Актуальность

За последние два десятилетия произошел стремительный рост технических возможностей для сбора и хранения больших массивов данных И этот рост продолжается Созданы миллионы баз данных, которые охватывают практически все области человеческого знания Подобный рост объема хранимых данных остро поднимает проблему поиска данных, а также, что еще более важно, порождает необходимость в средствах, позволяющих автоматически извлекать полезные знания из больших массивов данных Именно к таким средствам и относится Интеллектуальный анализ данных (ИАД)

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

Особенно актуальным является разработка методов ИАД, которые могут действовать в условиях неполноты данных, а также когда эти данные содержат объекты, характеризуемые семантически неравнозначными атрибутами, т е какая-то часть атрибутов считается более значимой, а какая-то - менее, что позволяет ранжировать атрибуты по их значимости

Цель работы

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

Новизна

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

Автору неизвестно работ, содержащих описание подобной разновидности стратегии ДСМ-метода

Теоретическая значимость

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

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

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

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

На данный момент существует множество систем НАД, однако лишь незначительная их часть занимается работой с контестно-зависимыми данными Также невелика доля систем, работающих с объектами, описываемыми атрибутами, неравнозначными между собой При этом, как правило, два этих множества не пересекаются

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

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

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

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

3 Был построен алгоритм работы ДСМ-системы на основе упомянутого выше варианта ДСМ-метода

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

Апробация

Промежуточные результаты и итоги проведенной работы докладывались на 49-й научной конференции МФТИ [Л2] и на 50-й юбилейной научной конференции МФТИ [ЛЗ], а также на научном семинаре "Вычислимые методы прогнозирования" при ВЦ РАН Основные результаты диссертации опубликованы в [Л4] Итоговые результаты докладывались и обсуждались в ВИНИТИ на семинаре В К Финна

Структура работы

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

I Основное содержание работы

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

В первой главе рассматриваются различные виды ДСМ-метода автоматического порождения гипотез в своей обычной формулировке

Во второй главе излагается формализация методов, рассмотренных в первой главе, на языке алгебры и теории множеств ! Определение 1. ДСМ-структурой будем называть кортеж

| ] = <А,0,Р,У,Р,Н>, где

• А - непустое конечное множество атомов,

• Ос р (А) - непустое конечное множество объектов (каждый объект представлен в виде множества атомов)3,

, • Р - непустое конечное множество (возможных целевых) свойств объектов4,

I • V = {+1,-1, 0, г} - множество (типов) внутренних истинностных значений (+1

I - эмпирически истинно, -1 - эмпирически ложно, 0 - эмпирически противоре-

чиво, х - неопределенно),

• Р О х Р —> V, отображение Р будем называть функцией обладания свойством,

• Н р (А) х Р —>У, отображение Н будем называть функцией причинности5 Определение 2 Утверждение о наличии или отсутствии у объекта целевого свойства

будем называть фактом Множество фактов образует базу фактов (БФ) Математическим | представлением базы фактов является отображение Р из Определения 1

Интуитивный смысл функции И можно описать следующим образом

3 Через р(А) обозначено множество всех подмножеств множества А

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

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

• F(о, p) - +1, если объект о е О обладает свойством р е Р (утверждение о том, что объект о обладает свойством р, истинно) Объект о будем называть плюс-примером свойства р Множество всех плюс-примеров для свойства р будем обозначать через 0+(р)

• Р(о,р) = -1, если объект о не обладает свойством р Объект о будем называть минус-примером свойства р Множество всех минус-примеров для свойства р будем обозначать через О~(р)

• F(о, р) = т, если неизвестно обладает ли объект о свойством р Объект о будем называть т-примером свойства р Множество всех т-примеров для свойства р будем обозначать через От(р)

• F(o, р) = 0, если для объекта о и свойства р установлено фактическое противоречие Объект о будем называть нуль-примером свойства р Множество всех нуль-примеров для свойства р будем обозначать через О°(р)

Определение 3. Любое подмножество множества атомов А будем называть фрагментом6

Интуитивный смысл функции Н можно описать следующим образом

• H(s, р) = +1, если фрагмент scA является причиной наличия свойства р е Р (плюс-причиной для свойства р) Множество всех плюс-причин для свойства р будем обозначать через S+(p)

• H(s, р) = -1, если фрагмент i является причиной отсутствия свойства ре Р (минус-причиной для свойства р) Множество всех минус-причин для свойства р будем обозначать через S~(р)

• H(s, р) = 0, если фрагмент i является нуль-причиной для свойства р е Р Множество всех нуль-причин для свойствар будем обозначать через S°(p)

• H(s, р) = т, если фрагмент 5 является т-причиной для свойства ре Р Множество всех т-причин для свойствар будем обозначать через S'(p)

Определение 4. Будем говорить, что между двумя объектами o¡, 02 е О имеется сходство, если o¡ П 02 * 0

Простой ДСМ-метод

Введем нижний индекс п для обозначения номера шага, на котором получен результат Например 0+„(р) будет означать множество плюс-примеров свойства р, имеющихся на момент прохождения л-го шага Аналогично понимаются 0\(р), О0п(р), Отп(р)

Следуя данному соглашению, мы будем обозначать через S+„(p) множество плюс-причин свойства р, известных после завершения л-го шага. Аналогично понимаются обозначения S\(p), S°„(p) и S\(p)

Теперь опишем перечисленные на Рис 1 этапы ДСМ-метода

6 Заметим, что согласно последнему определению объект является частным случаем фрагмента

Yes +

^Эавершение^

Рис I Схема работы ДСМ-решателя

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

примеров и для минус-примеров Для полученных множеств пересечений введем специальные обозначения ( Обозначение 1.

Х+„(р) = { пС # 0 | С с 0+„(р), |С| > 2 } Х~»(р) = {пС * 0 | С с 0-„(р), |С|*2}

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

Сначала вводятся вспомогательные предикаты (они же - решающие предикаты) М^

и1УГп

Обозначение 2. М+„(3,Р) О 5 6 Х+„(р) М-П(8,р) «ее Х~„(р)

Определение 5 Следующие правила называются правилами индукции или правилами правдоподобного вывода (ППВ) первого рода

(Г) в е 8>) & м+„(8,р) & - М-„(8,р) -> 8 е 8+„+1(р) (П * е в\(р) & М~„(*,р) & - М+„(8,р) 8 е 8"п+1(р) (1°) в е 8тп(р) & М\(5,р) & М"„(8,р) -> 8 б 8°п+1(р) (Г) в 6 в» & - м+„(5,р) & - М-„(8,р) -» 8 6 8т„+1(р) Словами это можно выразить так

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

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

Если фрагмент принадлежит одновременно и множеству пересечений плюс-примеров, и минус-примеров, то выдвигается гипотеза, что наличие этого фрагмента ведет к противоречию (противоречивая причина)

Если фрагмент не принадлежит ни множеству пересечений плюс-примеров, ни множеству пересечений минус-примеров, то он остается в числе неопределенных

Аналогия В данном блоке на основании найденных ранее причин происходит выдвижение гипотез о наличии / отсутствии искомого свойства у объекта Или же о имеющем место фактическом противоречии

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

I ГГ„+1(о,р) о (3« 6 в^+Кр)) (в с о)

1Гп+1(о,р) <=> (Зв е 8-„+,(р)) (в с о) П°п+1(о,р) О (Зв б 80о+,(р)) (5 с о) 1 Определение 6 Сами правила правдоподобного вывода второго рода выглядят сле-

| дующим образом

(II4) о е ОУр) & П+„+1(о,р) & - 1Г„+,(о,р) -> о е 0+„+1(р) (1Г) о е От„(р) & 1Гп+1(о,р) & - ГГ„+1(о,р) 0-п+1(р)

(II0,) о е 0\(р) & П+0+1(о,р) & 1Гп+1(о,р) ->ое О0п+)(р) (И02) о е От„(р) & П°п+1(о,р) -> о € 0°„+1(Р)7 0Г> о б От„(р) & -П+п+1(о,р) & -П „+1(о,р) ->об От„+1(р)

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

Двойственно, если установлено, что для такого объекта есть минус-причины и нет плюс-причин, утверждается, что объект искомым свойством не обладает ; Если для данного объекта имеются как плюс-причины, так и минус-причины, то для

данного объекта выявляется наличие фактического противоречия устанавливается фактическое противоречие Также противоречие устанавливается, если для данного объекта существуют противоречивые причины (см сноску 7)

Если для объекта не удается обнаружить никаких причин, он остается среди тех, для ! которых факт обладания искомым свойством не определен Условие завершения

Процесс работы ДСМ-алгоритма может быть как одношаговым, так и итеративным, те имеющим несколько шагов, в ходе каждого из которых последовательность процедур "пересечение"-»"индукция"-У'аналогия" работает заново, беря за основу данные, имеющиеся на текущий момент, т е как исходные, так и полученные на предыдущих шагах работы В таком случае условием завершения будет то обстоятельство, что на очередном шаге исходная и доопределенная база фактов совпадают, те не удалось установить факт наличия/отсутствия целевого свойства ни для одного нового объекта

Проверка (проверка каузальной полноты) состоит в том, что все уже известные факты должны быть объяснимы В противном случае утверждается, что База Фактов нуждается в пополнении извне

Простой ДСМ-метод с запретом на контрпример

7 В классическом ДСМ-методе данного правила нет, однако для кажется естественным определить его и использовать полученный выше П°п+1(о,р)

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

Существенное отличие данного метода от простого обнаруживается на этапе индукции в правилах первого рода фрагмент определяется как плюс-причина (минус-причина) в том случае, если он входит в множество пересечений плюс-примеров (минус-примеров) и не существует такого минус-примера (плюс-примера), в который бы данный фрагмент входил (I+) s е S» & M+„(s,p) & 3 о е 0-(р) (sco)->se S+„+1(p) (Г) s б S» & M-„(s,p) & 3 о б 0+(р) (Sco)-»ss S-n+1(p) Правило для противоречивости не вводится, а правило, сохраняющее неопределенность, выглядит так же, как и в случае простого метода без запрета на контрпример (Г) s е S» & M+n(s,p) & -, M~„(s,p) -> STn+,(p)

Рассуждение по аналогии (правила второго рода) для ДСМ-метода с запретом на контрпример выглядят так же, как и в простом методе

Несимметричный и обобщенный ДСМ-методы

Теперь рассмотрим теоретико-множественных подход к наиболее интересной, с точки зрения автора, модификации ДСМ-метода - обобщенном ДСМ-методе, и несимметричном ДСМ-методе8, как разновидности обобщенного ДСМ-метода

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

(i) О*n(s,p) - множество плюс-примеров свойства р, содержащих фрагмент s Формально это можно записать как

0+a(s,p) = {о б 0+„(р)|seo}

(и) 0'„(sp) - множество минус-примеров свойства р, содержащих фрагмент s Формально это можно записать как

0~„(jy>) = {о е 0"„(р)| s с о}

(ш) Ot„(s,/j) - множество объектов, содержащих фрагмент j, для которых факт наличия / отсутствия свойствар не установлен Формально это можно записать как OTn(S,/0 = {о Е От„(р)| sgo)

8 Его каноническая формулировка была предложена Д В Виноградовым [3]

9 То есть эти минус-причины при любых условиях, если они входят в объект, влекут отсутствие целевого свойства

В решающие предикаты М+ и МГ добавляется еще один параметр - возможная причина

Обозначение 5.

(1) Через М+г,($1,р)[з] будем обозначать тот факт, что ¿'1 является сходством не менее двух объектов, обладающих свойством р и содержащих фрагмент 5

(и) Через М~п(8|,р)И будем обозначать тот факт, что 5] является сходством не менее двух объектов, не обладающих свойством р и содержащих фрагмент 5

Определение 7. Фрагмент ^ называется тормозом фрагмента з для свойства р, если выполняется следующее условие он является сходством хотя бы двух объектов, содержащих 5 и не обладающихр Те фрагмент ¿'1 является тормозом фрагмента .г для свойствар если справедливо условие М~а(81,р)[к]

Правила правдоподобного вывода обобщенного ДСМ-метода также делятся на правила первого рода и правила второго рода

Несимметричный ДСМ-метод

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

(Г,) в е 8т„(р) & М+„(8,р) & (Г„(8,р)=0 ->■ в е 8+п+,(р) Этим правилом порождаются кандидаты в абсолютные плюс-гипотезы, т е в гипотезы, не имеющие тормозов"

Обозначение 6 Введем обозначение Т+„(8, р) которое следует понимать как множество тормозов возможной причины л1 наличия свойства р, где п — номер шага ДСМ-метода, не позднее которого были обнаружены эти тормоза

Через Т'Дв, р) обозначим множество кандидатов в тормоза для гипотезы £ и свойства р, где п — номер шага ДСМ-метода, вплоть до которого не было выяснено, являются ли эти фрагменты тормозами

I е Тт„(8, р) & М „(1,р)[51 -> 1 б Т+„+|(5,р) Замечание Можно заметить, что множество кандидатов в тормоза Т,„(8, р) является множеством пересечений минус-примеров для свойства р, содержащих фрагмент л По аналогии с обозначением 1. это множество можно обозначить как X п(р)[$]

Правило для кандидатов в гипотезы, имеющие тормоза, можно записать так

10 В обобщенном и несимметричном ДСМ-меггодах под фактическим противоречием понимается то же, что и в простом ДСМ-метода, о котором говорилось выше

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

(Г2) в е 8т„(р) & м+„(8,р) & О п(з,р) * 0 & Т+„+1(в,р) * 0 -> в б 8+„+1(р) Существенная модификация данного метода заключается в том, что при такой формулировке ППВ первого рода отслеживается случай, когда множество минус-примеров не пусто, но при этом сходства между минус-примерами найти не удается Это означает, что, не смотря на наличие контрпримеров, тормоза выделить не удается, множество тормозов пусто В подобном случае утверждается, что для выявления тормозов недостаточно данных, а значит недостаточно данных и для выдвижения гипотезы с такой фрагмент-причиной В результате, данный кандидат в гипотезы отвергается

При этом противоречия не порождаются ни одним из правил вывода Правила второго рода содержат всего два правила (1Г) о 6 оу^р) & в б 8+„+)(р) & -.310 еТ+0+,(5,р) &

(£о)->ое 0+пИ(5,р) Правило 1Г имеет два варианта для одношагового метода и итеративного Для одношагового метода это правило выглядит просто (1Г) о е ОУв, р)&Ь8б 8+„+1(р) V В1 е Т^.р) &

1со))-юе СГц+^р) Словами это можно описать так если не П+, то 1Г, т е если к данному объекту не удалось ни разу применить ни одну из гипотез и правило И+ ни разу не сработало, данный объект считается не обладающим искомым свойством

В итеративном методе данное правило менее строго, обозначим его IIх (1Г) о е От„(5,р)&(-,5е 8+„+,(р) V 31 (I е Т+„+,(з,р) &

1со))-юе От„+1(з,р) т е если для объекта не удается применить ни одной гипотезы о наличии свойства, сохраняется неопределенность, которая переходит на следующую итерацию, и только на последнем шаге итерации данное правило работает аналогично тому, как оно работает для одношагового случая

Обобщенный ДСМ-метод

Обобщенный ДСМ-метод отличается от несимметричного ДСМ-метода тем, что рассматривает как причины наличия свойства, так и причины отсутствия свойства у объекта. Так что все определения, равно как и формулировки правил Г4-!, 1+2,1Г1", 1Г, Т+„(8, р) и Т*,,(8> р) остаются те же, что и в итеративной модификации несимметричного ДСМ-метода

Обозначение 7 Введем обозначение Г„(8,р) которое следует понимать как множество тормозов возможной причины ^ отсутствия свойства р, где л — номер шага ДСМ-метода, не позднее которого были обнаружены эти тормоза С 6 Г„(«, р) & М+„((,р)[5] I е Г„+1(«,р) Правила первого рода для причин отсутствия свойства у объекта (Г,) 8 б вУр) & М^р) & О+„(5,р)=0 -» в е 8"п+1(р) (Г2)з б 8т„(р)&М\(8,р) & 0+„(5,р)Ф0&

Тп+1(*, р) * 0 -»5 6 8~„+,(р)

Вводится третье правило второго рода, двойственное к Н+ (1Г) о е От„(5,р) & в е 8^,(р) & -.31 0 б Тпмвр) &

I с о) -> о е 0"пц(8,р) Как несложно заметить, правила Н+ и 1Г не являются взаимоисключающими, те | обобщенный ДСМ-метод, в отличии от несимметричного, допускает наличие противоречий | А значит, необходимо четвертое правило II0

. (II0) о е О'^р) & 35 (о е 0+„(5,р)) & Вй1 (о 6 О-^ьр)) о е О0п+1(р)

Интуитивный смысл этого правила в следующем если про объект о не известно, обладает ли он искомым свойством р или нет, но известно, что а) о содержит такой фрагмент что было установлено, что объект о входит в множество плюс-примеров, содержащих фраг-1 мент л, Ь) о содержит такой фрагмент что было установлено, что объект о входит в множество минус-примеров, содержащих фрагмент Л| Иными словами, один и тот же объект оказывается занесен как в множество объектов, обладающих свойством р, так и не обладающих им В таком случае устанавливается факт противоречия I В третьей главе рассматривается работа с объектами, характеризуемыми семантиче-

ски неравнозначными атрибутами

Будем предполагать, что объект представлен в виде множества признаков и значимость разных признаков для характеризации объекта может быть различной В таком случае ! будем говорить, что признаки семантически неравнозначны В качестве примера предметной I области, где наблюдается подобная семантическая неравнозначность признаков, можно привести страхование и связанную с ним оценку рисков Так при описании потенциального клиента для задачи медицинского страхования есть некоторые параметры, которые более важны (например, "работает на вредном производстве" или "является активным курильщиком"), а есть некоторые параметры, которые не столь существенны (например, "живет на верхних I этажах в доме, где нет лифта" или "в детстве болел ветрянкой")

Разделим все имеющиеся признаки на категории, в зависимости от их значимости, и этим категориям присвоим некоторые числовые веса Множество возможных значений весов I составляет отрезок от 0 до 1 Признаки, относящиеся к одной и той же категории, имеют одинаковые веса12

Однако ДСМ-метод работает не с отдельными признаками, а с фрагментами Соот-| ветствие между значимостью фрагмента и значимостью составляющих его признаков проводится при помощи численных весов, которые ставятся в соответствие каждому фрагменту Определение 8 Введем функцию оценки фрагмента \У(в) Б -> И,

| 12 На основании того, что признаки делятся на категории, т е ранжируются, описы-

ваемый далее ДСМ-метод предлагается называть ранжированным ДСМ-методом

которая будет ставить в соответствие каждому фрагменту s его вес Эта функция определяется через S-норму Например, через максимум - весь фрагмент имеет такой же вес, как и наиболее значимый из признаков, входящих в его состав W(s) = max (W(a) | а е s}

Замечание Возможны другие подходы к реализации функции оценки (другие S-нормы), зависящие от конкретной предметной области и предпочтительпой стратегии Чаще всего интуитивно выбирается именно максимум, однако это может быть и алгебраическая сумма и другие S-нормы

Определение 9. С каждым объектом о свяжем некоторый числовой параметр, назовем его "правдоподобность наличия свойства" Этот параметр будет отражать то, насколько правдоподобным мы считаем факт обладания свойством р для данного объекта Будем обозначать этот параметр через р„(о,р), где о - объект, р - свойство, п - номер текущего шага индукции.

Определение 10 С каждым объектом о свяжем некоторый числовой параметр, назовем его " правдоподобность отсутствия свойства" Этот параметр будет отражать то, насколько правдоподобным мы считаем факт отсутствия обладания свойством р для данного объекта Будем обозначать этот параметр через р „(о,р)

Каждый из этих двух параметров будет отвечать за то, сколько у нас имеется "свидетельств" в пользу наличия / отсутствия свойства у объекта, а также насколько они "сильны"

Рассмотрим сначала первый из них, "правдоподобность наличия свойства" Очевидно, что данный параметр связан с правилом второго рода обобщенного ДСМ-метода, которое устанавливает наличие свойства у объекта Напомню это правило о е 0T„(s,p)& s е S+n+i(p) & -at (t е T+n+I(s,p) &

t с о) -> о 6 0+„+i(s,p) "Если для объекта не установлено наличие или отсутствие свойства р и он содержит фрагмент s, являющийся причиной наличия свойства р, а также не содержит ни одного тормоза причины s для свойства р, то устанавливается, что данный объект обладает свойством Р"

А правило для случая, когда найдется тормоз причины s для свойства р, утверждало, что установить обладает ли объект свойством невозможно

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

Определение 11. Введем функцию оценки множества фрагментов W(M) W(M) -также определяется через S-норму Данная функция будет ставить в соответствие некоторому множеству фрагментов М число, являющееся результатом применения S-нормы ко всем фрагментам из М

Например W(M) = шах (W(s) | s е М}

' Замечание В случае, если М - пустое множество, будем считать его оценку равной

нулю Wmax(0) = O

Напомню, что гипотезу мы рассматриваем как пару <фрагмент-причина, множество тормозов> Тогда можно ввести следующие термины

Определение 12 Будем говорить, что гипотеза (s, T+„+i(s,p)) применима к объекту о, ( если объект о содержит фрагмент s

! Будем говорить, что гипотеза (s, T+„+1(s,p)) для объекта о блокируется тормозами,

если данная гипотеза применима к объекту о (т е объект о содержит фрагмент s) но также содержит и один или несколько тормозов из T\,+i(s,p)

Будем говорить, что гипотеза (s, T+„+i(s,p)> срабатывает для объекта о, если она применима к объекту о и не блокируется тормозами

Обозначение 8 Через 1пс(р+„(о,р), а) обозначим операцию увеличения параметра Рп(о,р) на величину сг Эта операция новому значению параметра р „(о,р) присваивает старое его значение, увеличенное на число сг, о котором речь пойдет ниже Для увеличения значения параметра Рп(о,р) будет использоваться еще одна S-норма - алгебраическая сумма13 1пс(р*„(о,р), а) <=> р+„(о,р) = р+„(о,р) + а

Обозначение 9 Через 1пс(рп(о,р), а) обозначим операцию увеличения параметра р п(о,р) на величину а \ 1пс(р~„(о,р), а) р"„(о,р) = р"„(о,р) + о

Теперь рассмотрим первую группу правил, правила взвешивания Приведем первое правило ] (А+) о е 0Tn(s,p)& s е S+„+,(p) & 3t (t € T+„+i(s,p) &

tco)-»/яс(р+п+1(о,р), a), где сг - число, на которое увеличивается значение р+(о,р) Будем называть его инкре-\ ментом

I Примечание. Можно рассматривать операции ¡пс(р ¡(о,р), а) и Inc(p„+i(o,p), cr) как

своего рода операторы присваивания, которые увеличивают значение шкалы правдоподобности pa„+i(o,p) на инкремент <т

Обозначение 10 Через T(s,p)[o] будем обозначать множество тех тормозов из T(s,p), которые содержатся в объекте о

Тогда правило, позволяющее вычислить инкремент сг из правила (А4) можно записать следующим образом ' а = шах ((W(s) - Wmai(T(s,p)[o])), 0)

Как мы видим выше, даже если причина блокируется, значение "правдоподобности j наличия свойства" может возрасти' Действительно, если, например, фрагмент-причина, по

13 Алгебраическая сумма определяется как а + Ь = а + Ь- аЬ

которой данный объект должен бы был обладать этим свойством - сильный фрагмент14, а блокируется она только слабыми фрагментами-тормозами, то это еще не значит, что нельзя говорить, что этот объект данным свойством обладает Однако субъективная вероятность обладания свойством все же ниже, чем если бы сильная причина не блокировалась тормозами, пусть и слабыми

Также заметим, что в случае, когда гипотеза срабатывает, множество T(s,p)[o] будет пусто, а значит Wmax(T(s,p)[o])) будет равно нулю, а значит параметр pn+i(o,p) возрастет на число, соответствующее весу фрагмента-причины сработавшей гипотезы - W(s)

Замечание Интуитивно понятно, почему значение параметра "правдоподобности наличия свойства" накапливается и все время возрастает если для одного объекта существует только одна сильная плюс-причина, а для другого - две сильных и еще три слабых, то правдоподобность наличия искомого свойства у второго объекта будет заведомо выше

Аналогично ведет себя и параметр "правдоподобность отсутствия свойства" Здесь также два правила взвешивания

(AI о е 0T„(s,p)& s е S~„+i(p) & 3t (t s T"„+i(s,p) &

t с o) 7/ic(p"„H(o,p), а), где а определяется аналогично тому, как оно задавалось в правиле А+ После того, как закончат работу все правила взвешивания, начинают применяться по- ' роговые правила

Порогом будем называть такое численное значение, начиная с которого значения параметров "правдоподобность наличия свойства" и "правдоподобность отсутствия свойства" будем считать значимыми Будем обозначать порог через X

Пороговыми правилами будем называть правила, доопределяющие наличие и отсутствие свойствар у объекта о Пороговые правила имеют следующий вид (II") о б От„(р) & pVi(o,p) >h& p~n+i(o,p) <J.2^oe 0+n+i(p) (1Г) о е От„(р) & p+„+i(o,p) <Х,& p""„+i(o,p) > Я.2 о 6 OVi(p) (И°) о е От„(р) & pVi(o,p) >h& PWo,p) > Х2 ->■ о б O0„t,(p) (1Г) о е От„(р) & p+n+i(o,p) < & p~„+i(o,p) < 5.2 -> о е OVi(p) Значение параметров "правдоподобность наличия свойства р п+ ¡(о,р) и "правдоподобность отсутствия свойства" p*„+i(o,p) обнуляются для каждого объекта перед началом очередной итерации ДСМ-процедуры, так что в расчет принимаются только результаты ра- ' боты правил рассуждения по аналогии на текущем шаге итерации, однако заметим, что общее количество гипотез будет только возрастать, по мере роста количества плюс-примеров и минус-примеров

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

14 Под более сильным фрагментом здесь и далее понимается фрагмент с большим весом

гии разделяются на два этапа применение правил взвешивания и применение пороговых правил

Для несимметричного метода набор пороговых правил будет несколько иной Несимметричный ДСМ-метод работает только с причинами наличия свойства у объекта Поэтому не будет правил А-, П° и параметра рп+1(о,р) Несимметричный ДСМ-метод в своем классическом виде не предполагает итеративности, поэтому не будет правила И1, а из правил П+ и 1Г уходит та часть, которая связана с параметром р„+1(о,р) В результате итоговая система правил, доопределяющих наличие и отсутствие свойства р у объекта о, приобретает следующий вид

(П1) о б От„(р) & р+п+1(о,р) > X о б 0+„+1(р)

(1Г) о б 0'„(р) & р+п+1 (о,р) < X о е СГ„+,(р)

Если мы хотим сделать допустимыми итерации, то правило 1Г применяется только на последнем шаге, а до этого работает правило П\ из которого также убрана часть, связанная с параметром р„+1(о,р)

(П>е ОУр) & р+1ит(о,р) < X о е 0'„+1(р)

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

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

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

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

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

Пример Пусть установлено, что злоупотребление алкоголем ведет к уменьшению срока жизни (вес этой гипотезы возьмем 0,5), а частое пребывание на свежем воздухе ведет к продлению оного (вес этой гипотезы - 0,2) Целевое свойство обозначим как "имеет длительный срок жизни" Допустим, про Ивана Ивановича известно, что он часто бывает на свежем воздухе, но злоупотребляет алкоголесодержащими напитками Получается, что для Ивана Ивановича установлено противоречие - есть доводы, как говорящие в пользу его длительного срока жизни, так и в пользу короткого Но это противоречие легко снимается за счет большой разности в значениях параметров правдоподобия 0,2 и 0,5 Таким образом, после применения пороговых правил с порогом, скажем, имеющим значение 0,4, получаем, что срок жизни будет коротким

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

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

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

Заключение

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

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

2 Разработанный вариант ДСМ-метода позволяет существенно сократить число порождаемых противоречий

■ 3 Предложенный метод является весьма гибким и легко настраиваемым за счет из-

1 менения весов и значений порогов можно получить реализацию не какой-то одной, а целой группы стратегий

4 Данный метод позволяет учитывать не только качество, но и количество гипотез, ^ т е число гипотез "за" и "против" может ока-зать влияние на конечный результат

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

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

В области теории дальнейшая работа видится в следующих на-правлениях

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

2 Определение четкого круга задач и конкретных предметных областей, где предла-I гаемый вариант ДСМ-метода работает оптимально и является предпочтительным

3 Исследование перспектив по созданию обратного ДСМ-метода для работы в условиях семантической неравнозначности данных

I

Литература

1 1 Аншаков О М Об одной интерпретации ДСМ-метода автоматического порождения

гипотез // НТИ, сер 2, № 1-2 - М ВИНИТИ РАН, 1999

2 Аншаков О М Логико-математические основания ДСМ-метода автоматического порождения гипотез Диссертация на соискание ученой степени доктора физико' математических наук. - М ВИНИТИ, 2000

3 Виноградов Д В Несимметричный ДСМ-метод с учетом контекста // Пятая национальная конференция с международным участием Искусственный интеллект-96 - Казань 1996 -КИИ-96 Сб науч тр ВЗт - Казань Ассоц искусств интеллекта, 1996

4 Григорьев П А Методы интеллектуального анализа данных в предметных областях с частично детерминированными свойствами объектов Диссертация на соискание степени кандидата технических наук - М ИППИ РАН, 2000

5 Данилова Е H , Ивашко В Г , Климова С Г , Михеенкова M А , Финн В К , Ядов В А Применение ДСМ-мстода автоматического порождения гипотез для исследования социального действия (соотношение индвидуально-личностных и социальных факторов) // Интеллектуальные системы и общество Сборник статей M РГГУ - 2000

6 Кузнецов С О Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки //НТИ Сер 2- 1993 -№1

7 Милль Д С Система логики силлогистической и индуктивной - M Книжное дело, 1900

8 Объедков С А Алгоритмические аспекты ДСМ-метода и формального анализа понятий - M РГГУ, 1999

9 Применение ДСМ-метода порождения гипотез для прогноза противоопухолевой активности и токсичности соединений, принадлежащих к различным классам химических соединений /ЕС Панкратова, В Г, Ивашко, В Г Блинова, Д В Попов II Экспертные системы состояние и перспективы / Под ред Д А Поспелова M Наука, 1989

10 Путрин А , Панкратова Е, Программная реализация интелектуальной системы типа ДСМ для распознавания химической канцерогенности // НТИ Сер 2 - 1997 - № 3

11 Финн В К Базы данных с неполной информацией и новый метод автоматического порождения гипотез // Диалоговые и фактографические системы информационного обеспечения -М, 1981

12 Финн В К О возможностях формализации правдоподобных рассуждений средствами многозначных логик // Всесоюзный симпозиум по логике и методологии науки - Киев Наукова думка, 1976

13 Финн В К О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф Бэкона - Д С Милля // Семиотика и информатика - Вып 20 - 1983

14 W Frawley and G Piatetsky-Shapiro and С Matheus "Knowledge Discovery in Databases An Overview" // Al Magazine - La Canada, CA American Association for Artificial Intelligence, 1992 (ISSN 0738-4602)-Fall 1992

15 Noms E M An Algorihm for Computing the Maximal Rectangles in Binary Relation. // Revue Roumaine de Mathématiques Pures et Appliquées - 23 (2), 1978

Публикации автора по теме диссертации

Л1 О теоретико-множественной формулировке несимметричного ДСМ-метода // Искусственный интеллект философия, методология, инновации Материалы Первой Всероссийской конференции студентов, аспирантов и молодых ученых, г Москва, МИРЭА, 6-8 апреля 2006г Под ред ДИ Дубровского и Е А Никитиной-M ИИнтеЛЛ, 2006

Л2 Теоретико-множественный подход в ДСМ-методе // Труды 49 научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" Часть VII Управление и прикладная математика M "Солар", 2007

ЛЗ Работа с несимметричным ДСМ-методом в условиях неравнозначности признаков // Труды 50-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" Часть VII Управление и прикладная математика Том 2 М МФТИ, 2007

Л4 Об одном методе анализа больших массивов структур с частично детерминированными свойствами объектов // Вестник РУДН Серия "Математика Информатика Физика" М РУДН, 2008 -N22

Заказ № 86 Тираж 100 экз Отпечатано в ООО "Дом печати "Столичный бизнес" г Москва, ул Покровка, 47/24, тел (495) 916-3984 www stbusmess ru

Введение.

Глава 1.

Глава 2.

Глава 3.

Глава 4.

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

1. Данный метод позволяет лучше учитывать специфику некото рых предметных областей, например, страхование и расчет рисков.В подобных предметных областях есть факторы, которые не име .ют большого веса, однако которые все же необходимо учитывать.Подобная дифференциация факторов-признаков по значимости позволяет уменьшить погрешность при принятии решения.2. Разработанный вариант ДСМ-метода позволяет существенно сократить число порождаемых противоречий.3. Предложенный метод является весьма гибким и легко на страиваемым: за счет изменения весов и значений порогов можно получить реализацию не какой-то одной, а целой группы страте гий.4. Данный метод позволяет учитывать не только качество, но и количество гипотез, т.е. число гипотез "за" и "против" может ока зать влияние на конечный результат.Кроме того, был сделан обзор и предложена теоретико множественная формализация большинства основных существующих разновидностей ДСМ-метода (подробнее об этом можно прочитать в первой и во второй главах соответственно). А также предложен ряд мер и модификаций, призванных оптимизировать производительность про граммных реализаций ДСМ-процедуры. Подробнее об этом и ряде дру 78 гих соображений можно прочитать в четвертой главе. Там же можно прочитать краткое описание экспериментальной программной реализа ции, созданной на основании вышеизложенной теории и реализующей вариант обобщенного ДСМ-метода, предназначенный для работы в ус ловиях семантической неравнозначности данных.В рамках создания этой программной реализации были получены следующие результаты:

1. Разработана объектная модель ДСМ-системы, позволяющая наиболее эффективно работать с контекстными методами.2. Реализован ДСМ-рсшатель со встроенной возможностью из менения стратегии за счет параметров, заданных в конфигураци онном файле (перенастройка весов и пороговых значений, опреде ление S-норм для вычисления весов и правил суммирования).3. Разработан набор правил для вычисления весов.4. Создана интеллектуальная система, позволяющая проводить вычисления по оценке рисков.Из вышеперечисленного можно сделать вывод, что цель и задачи, ' поставленные в начале диссертационной работы были в полной мере достигнуты и раскрыты. Напоследок хотелось бы очертить круг задач и перспектив, открытых перед ДСМ-методом для работы в условиях се мантической неравнозначности структурных элементов.В области теории дальнейшая работа видится в следующих на правлениях:

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

1. Создание удобного пользовательского интерфейса.2. Переход от конфигурационного файла к настройкам, встроен ным в интерфейс.3. Увеличение числа реализованных S-норм.4. Возможность более гибко ранжировать категории признаков и их веса.5. Возможность выбирать используемый вариант ДСМ-метода.6. Возможность выбрать несколько вариантов ДСМ-метода с по следующим сопоставлением полученных результатов.

1. Burch, Robert. Introduction to modern Peircean Logic with applications to automated reasoning. Publications of the Army Research Laboratory, White Sands, New Mexico, 1996

2. Frawley W., Piatetsky-Shapiro G., Matheus C. "Knowledge Discovery in Databases: An Overview" // AI Magazine La Canada, CA: American Association for Artificial Intelligence, 1992. (ISSN: 0738-4602)-Fall 1992.

3. Kantardzic, Mehmed. Data Mining: Concepts, Models, Methods, and Algorithms. John Wiley & Sons, 2003 (ISBN 0471228524)

4. Kosko B. Fuzzy systems as universal approximators // IEEE Transactions on Computers. Vol. 43. - № 11, November 1994.

5. Norris E.M. An Algorihm for Computing the Maximal Rectangles in Binary Relation. // Revue Roumaine de Mathématiques Pures et Appliquées .-23 (2), 1978.7. Zadeh, Lotfi. Fuzzy Sets // Information and Control- 8(3). -1965.

6. Zadeh, L. A., Fuzzy Sets as a Basis for a Theory of Possibility // Fuzzy Sets and Systems. Vol. 1. - № 1, 1978.

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

8. Аншаков О.М., Скворцов Д. П., Финн В.К., Ивашко В.Г. Логические средства ДСМ-метода автоматического порождения гипотез: основные понятия и система правил вывода. // НТИ. Сер. 2. -1987.- №9.

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

10. Аншаков О.М. Логико-математические основания ДСМ-метода автоматического порождения гипотез. Диссертация на соискание ученой степени доктора физико-математических наук. -М.: ВИНИТИ, 2000.

11. Аншаков О.М. Каузальные модели предметных областей. // М:НТИ. Сер. 2,- 2000.- № 3.

12. Аншаков О.М. Об одном подходе к порождению гипотез в ДСМ-методе. //Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006 г., Обнинск): Труды конференции. В 3-т. М: Физ-матлит, 2006.

13. Блинова В.Г., Ивашко В.Г., Скитер П.В., Финн В.К, Хазанов-ский К.П. Об интеллектуальных системах типа ДСМ // Семиотика и информатика-М 1990 - Вып. 31.

14. Брускина Д.Г. ДСМ-подобная система для компьютерного прогнозирования рецидива аденомы гипофиза Дипломная работа.- М.:РГГУ- 1998.

15. Виноградов Д.В. Несимметричный ДСМ-метод с учетом контекста // Пятая национальная конференция с международным участием .Искусственный интеллект-96. Казань: 1996. - КИИ-96: Сб. науч. тр.: В 3 т. - Казань : Ассоц. искусств, интеллекта, 1996.

16. Виноградов Д.В. Алгебраическая модель связанных свойств ДСМ-метода // НТИ-97. Информационные ресурсы. Интеграция. Технологии. Материалы конференции-М.:ВИНИТИ 1997.

17. Виноградов Д.В. Корректные логические программы для правдоподобных рассуждений // НТИ, сер 2., № 5, ВИНИТИ РАН, М., 2001.

18. Григорьев П.А. Методы интеллектуального анализа данных в предметных областях с частично детерминированными свойствами объектов. Диссертация на соискание степени кандидата технических наук. М.: ИППИ РАН, 2000.

19. Заде JT. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976.

20. Кузнецов С.О. Сходство в обобщенном ДСМ-методе и алгоритмы его порождения. // НТИ. Сер. 2 — 1995 -№6.

21. Кузнецов С.О. Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки. // НТИ. Сер. 2.- 1993 — №1.

22. Липкин A.A. Теоретико-множественный подход в ДСМ-методе // Труды 49 научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук": Часть VII Управление и прикладная математика. М.: "Солар", 2007.

23. Липкин A.A. Работа с несимметричным ДСМ-методом в условиях неравнозначности признаков // Труды 50-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук": Часть VII Управление и прикладная математика. Том 2 М.: МФТИ, 2007.

24. Липкин A.A. Об одном методе анализа больших массивов структур с частично детерминированными свойствами объектов //Вестник РУДН. Серия "Математика. Информатика. Физика". М.: РУДН, 2008.-№2

25. Мельников Н.И. Решатель интеллектуальных задач типа ДСМ. //НТИ Сер. 2.-2001.-№4.

26. Милль Д.С. Система логики силлогистической и индуктивной.- М.: Книжное дело, 1900.

27. Михеенкова М.А. ДСМ-метод правдоподобного рассуждения как средство анализа социального поведения // Известия РАН. Сер. "Теория и системы управления".- 1997-№ 5.

28. Михеенкова М.А., Финн В.К. Анализ мнений и многоагентные системы. // Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006 г., Обнинск): Труды конференции. В 3-т. М: Физматлит, 2006.

29. Объедков С.А. Алгоритмические аспекты ДСМ-метода и формального анализа понятий. М.: РГГУ, 1999.

30. Поспелов Д.А. Десять "горячих точек" в исследованиях по искусственному интеллекту // Интеллектуальные системы (МГУ). М.- 1996, -Т.1.

31. Путрин А., Панкратова Е., Программная реализация интелек-туальной системы типа ДСМ для распознавания химической канцерогенное™ // НТИ . Сер . 2 1997.- № 3.

32. Финн В.К. О возможностях формализации правдоподобных рассуждений средствами многозначных логик // Всесоюзный симпозиум по логике и методологии науки. Киев: Наукова думка, 1976.

33. Финн В.К. Об обобщенном методе автоматического порождения гипотез // Семиотика и информатика 1989.- Вып. 29.

34. Финн В. К. Интеллектуальные системы: проблемы их развития и социальные последствия // Будущее искусственного интеллекта. М., 1991.

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

36. Финн В.К. Об интеллектуальном анализе данных //Новости искусственного интеллекта. М. 2004. - №3

37. Финн В.К. Об одном варианте логики аргументации // НТИ. Сер. 2.- 1996.-№ 5-6.