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

Государственный комитет по образованию Российской Федерации Российский государственный гуманитарный университет

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

УДК 007:510.64:159.995

ГРИГОРЬЕВ Петр Александрович

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

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

Автореферат

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

Москва - 2000

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

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

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

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

доктор технических наук, профессор Шемакин Юрий Иванович,

кандидат технических наук, доцент Тарасов Валерий Борисович

Ведущая организация:

Институт проблем управления РАН.

Защита состоится 25 мая 2000 г. в 16 часов на заседании диссертационного совета Д 003.56.01 при Институте проблем информатики (ИЛИ) РАН по адресу: 117900, г. Москва, ул. Вавилова 30/6.

С диссертацией можно ознакомиться в библиотеке ИПИ РАН.

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

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

Д 003.56.01 пр$1 ИПИ РАН доктор технических наук, профессор

С.Н.Гринченко

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

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

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

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

Целью настоящей работы является разработка логико-алгоритмического аппарата, обеспечивающего эффективное решение задач ИАД в предметных областях с частично детерминированными свойствами объектов.

Для достижения поставленной цели необходимо:

1. Изучить возможности существующих методов ИАД для работы в предметных областях с частично детерминированными свойствами объектов.

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

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

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

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

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

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

Апробация работы. Основные научные выводы и результаты работы докладывались на международных конференциях НТИ-97 и НТИ-99, а также на научном семинаре Отдела теоретических и прикладных проблем информатики Всероссийского института научной и технической информации (ВИНИТИ).

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

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

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

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

Е первой главе «^М-метод как средство интеллектуального анализа данных» риводится определение ИАД как процесса извлечения знаний из данных. ассматриваются виды знаний и способы представления данных в задачах 1АД. Предлагается неформальная классификация методов ИАД. Подробно азбирается один из наиболее универсальных методов ИАД - .¡БМ-метод зтоматического порождения гипотез.

Интёллектуальный анализ данных — это процесс обнаружения в "сырых" шных: ранее неизвестных, нетривиальных, практически полезных и

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

Возможность применения конкретного метода ИАД для решения той или иной задачи зависит от следующего:

• Какого рода знания позволяет извлекать этот метод?

• С каким представлением данных работает этот метод?

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

• те, в которых доминируют случайные события и как следствие -частотные закономерности,

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

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

Рассматриваются основные способы представления данных, с которыми работают методы ИАД:

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

• структурное представление (объекты задаются типологически),

• полнотекстовое представление (анализируется информация, накопленная в виде текстов на естественном языке).

Неформально, методы ИАД целесообразно разделить на следующие группы.

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

Статистические методы ИАД исследуют числовые характеристики данных (например, частоту совместного появления фиксированного множества свойств у группы объектов) и основаны на достижениях в области математической статистики. В GUHA-методе применяется техника статистических кванторов, основанная на статистических критериях корреляции (критерий у} Пирсона, критерий Фишера и др.).

Методы мягких вычислений ориентированы на работу с нечетким, приблизительным представлением данных и знаний; они основаны на синтезе достижений в теории нейронных сетей (Neural Networks), нечеткой логике (Fuzzy Logic) и теории генетических алгоритмов (Genetic Algorithms). К методам мягких вычислений следует отнести также и методы символьного обнаружения знаний (Symbolic Knowledge Acquisition), представляющие универсальный способ формирования гипотез о зависимости целевой переменной от других переменных в виде автоматически синтезируемых программ.

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

(I) знания о структурных причинах исследуемых свойств,

(II) знания о том, какими свойствами обладают исследуемые объекты.

^М-рассуждение является синтезом познавательных процедур: индукции, аналогии и абдукции. Метод предоставляет логико-алгоритмические средства для (частично) автоматизированного построения теории о предметной области. В рамках диссертационной работы Л8М-метод рассмотрен как метод НАД.

. Бесконечнозначная логика, используемая в ^М-методе (^ЯМ-логика), имеет два языка: внутренний н внешний. Внутренний язык .18М-логики служит для описания фактоподобных высказываний, а именно гипотез о структурных причинах исследуемых свойств и гипотез о том, какими свойствами могут обладать исследуемые объекты. Формулы внутреннего языка принимают значения в бесконечном - счетном - множестве внутренних истинностных значений. Внешний язык использует ,1-операторы Россера-Тьюркетта для погружения выражений внутреннего языка в двузначную логику предикатов.

Множество внутренних истинностных значений .ТЭМ-логики образуют пары вида <!;, п>, где 4 есть тип истинностного значения, а п - натуральное число - номер шага вывода, на котором получена оцениваемая гипотеза. Имеется 4 типа внутренних значений:

• 1 - эмпирическая истина,

• -1 - эмпирическая ложь,

• 0-эмпирическое противоречие,

• т - эмпирическая неопределенность.

. Моделью для ,15М-рассуждений служит хорошо структурированный каузоид - кортеж:

О, А; й, П, Е; =>,, =>2; ©, О здесь есть множество объектов, Р - множество фрагментов, А -множество свойств, причем Р включаеч О, то есть каждый объект является (максимальным) фрагментом самого себя.

'Е' есть отношение вложения на фрагментах: (Ео означает, что фрагмент { вкладывается в объект о. ' П' есть операция сходства, сопоставляющая двум фрагментам их максимальный (по вложению) общий фрагмент. Если Б -непустое множество объектов, то П(8)=Гозначает, что (во-первых) фрагмент Г вкладывается в каждый объект из Б и (во-вторых) Г - максимальный, по отношению 'Е' такой фрагмент. Г0 называется пустым фрагментом: ^ вкладывается в каждый фрагмент. <Р, Г1> есть нижняя полурешетка. В случае, когда объекты представлены в виде множеств, ' Ег' определяется как теоретико-множественное вложение, 'П' - пересечение.

=>, и =>2 _ суть внутренние предикаты "обладать свойством" и "быть причиной свойства" соответственно. Область определения =>| есть ОхА, область определения =>2 есть РхА. Предикаты принимают значения во множестве внутренних истинностных значений .(БМ-логики. Так, например, выражение .1<1,з>(о=>1а) означает, что на третьем шаге вывода была получена гипотеза, что объект о обладает свойством а; а выражение 5)(Г =>2 а) означает, что вплоть до пятого шага вывода никаких гипотез относительно причинно-следственной связи между вхождением фрагмента ^ и проявлением свойства а порождено не было.

Если а и а' - свойства (а, а'б А), то свойства аФа', а®а' и а1 определяются следующим образом. Объект о обладает свойством аФа' тогда и только тогда, когда он обладает хотя бы одним из свойств а и а', о обладает а®а' тогда и только тогда, когда он обладает и а, и а1, о обладает а1 тогда и только тогда, когда он не обладает а.

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

Будучи примененными на п-ном шаге вывода, правила первого рода порождают гипотезы вида 3<:, п>^=>2а) или }(,, П)^=>2а), где f - фрагмент, а -свойство, \ - счетно-расщепленный тип истинностных значений - 1, -1}.

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

Система правил вывода первого рода состоит из четырех правил: (Г): Зь, п) ^ =>2 а), М+П(Г, а), -.мж а) н =>2 а),

(| ): п) ^ =>2 а),-|М+П(?, а), М „(^ а) н J<-l, п+1> (Г =>2 3), (I"): 3(т. п) (Г =>2 а), М+п(Г, а), а) н ^о.п+^^га),

(Г): п, ^ =>2 а), -,М+п(Г, а), а) I- „+1,(Г =>2 а),

где

М+„(Г, а) ^ 3 Б: ((Б 50)&(|5|>1)&а(,,п)(5=>1а))&(П(5) = а)), а) ^3 Б: ((Б сО)8.(|5|>1)&0н,п)(5^1а))&(П(5) = а)).

\Г и М" называются решающими предикатами первого рода. М+П(Г, а) истинен, когда найдется непустое множество Б положительных примеров свойства а, сходством которых является в точности фрагмент £ Аналогично, М-„(Г, а) истинен, когда найдется непустое множество отрицательных примеров свойства а, сходством которых является в точности фрагмент Содержательно, а) означает, что имеются аргументы за то, чтобы считать фрагмент f причиной наличия свойства а, М"„(Г, а)- причиной отсутствия свойства а.

Поясним суть правил первого рода на примере (Г). Правило (Г) гласит:

• если до п-ного шага вывода никакой причинно-следственной связи между фрагментом Г и свойством а обнаружено не было (выражается в и|(Г=>2а)),

• и фрагмент Г является сходством некоторого множества объектов, обладающих свойством а (выражается в М+п(^ а)),

. • и фрагмент Г не является сходством какого-либо множества объектов, не обладающих свойством а (выражается в а)),

• то фрагмент Г является причиной наличия свойства а (выражается в 3<1, п+1>((г=>2а)).

Система правил вывода второго рода состоит из четырех правил: (1Г): ](,, „)(о=>1а), п+„(о, а), ^п'„(о, а) к Л<1, п+1>(о^1 а), (1Г): J(t, П) а), П"п(о, а), -,п+п(о, а) н п+1>(о=>1 а), (И ): -1(1, п) (о=я а), П"п(о, а), п+п(о, а) ь Л<0, п+1>(о=>1 а), (10: ](,, п) (о=>1 а), ^П"„(о, а), ^п+п(о, а)н л(1/ п+1)(о=>1 а),

де:

П+п(о, а) ^ эй (ГеР) & Лц, „,(^2а) & {Г 5 о), П"п(о, а) ^ (ГеР) & ](.!, „,(^2а) & (Г = о).

Предикаты ГГ„ и П"„ называют решающими предикатами второго рода. ¡ели о - объект, а - свойство, и П+„(о, а) истинен, то это означает, что имеются ргументы за то, чтобы принять гипотезу "объект о обладает свойством а". А менно, (во-первых) имеется гипотеза, что фрагмент { является структурной ричиной свойства а (что выражается через п)(Г=>2а)), и (во-вторых) фрагмент входит в объект о (что выражается через { Е о). Предикат П"„ устроен войственным образом.

Таким образом, правило (1Г) гласит:

• если неизвестно, обладает ли объект о свойством а (3(,, П) (о=>1 а)),

• и имеются аргументы в пользу гипотезы "о обладает а" (П+п(о, а)),

• и нет аргументов в пользу противоположной гипотезы: "о не обладает а" (-|П"п(о, а)),

• то гипотеза ".о обладает а" принимается (.1<| пМ,(о=>| а)). Правило (II") устроено двойственным образом.

Правило (II0) констатирует, что если имеются как аргументы за "о эладает а", так и за "о не обладает а", то приходится зафиксировать актическое противоречие (3<о, п+1>(о=>1 а)).

Правило (1Г) констатирует, что если нет аргументов ни за "о обладает а", и за "о не обладает а", то на данном шаге вывода ни та, ни другая гипотеза не ринимается.

Компьютерную реализацию ^М-метода принято называть ^М-системой. ^М-система, как система ИАД, позволяет извлекать знания из данных. Исходные данные - базу фактов - для .¡БМ-системы составляют эмпирические сведения о свойствах исследуемых объектов, представленные таблицей, строки которой соответствуют объектам,,столбцы - свойствам. На пересечении стоит знак "+", если объект обладает свойством, "-" - не обладает, "т" — неизвестно: обладает или нет. Базу знаний ^М-системы составляют гипотезы о структурных причинах свойств. Задача .(БМ-системы - максимально восполнить как базу знаний, так и базу фактов.

Основные алгоритмы .)5М-системы представлены в диссертации как программы на процедурном языке. Такое описание наиболее распространено в «практическом» программировании, кроме того, оно позволяет оценить вычислительную сложность ^М-метода. В работе 18М-системы выделяются два этапа: Пересечение к Доопределение.

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

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

В худшем случае Пересечение имеет экспоненциальную сложность о числа объектов. Сложность Доопределения составляет О(а п к), где п количество недоопределенных примеров, к - количество гипотез первого родг а - вычислительная сложность отношения 'Е\

Во второй главе «Количественный ^М-метод» излагается основной теоретический результат настоящей работы - количественный ^М-метод. Прежде всего, уточняется область применения количественного ^М-метода. Затем предлагается формализация интуитивного понятия аргументации гипотез, исходя из которой, формулируются количественные критерии фальсификации ^М-гипотез. Строится система правил правдоподобного вывода, использующих предложенные критерии. Предлагаются алгоритмические решения, реализующие количественный .15М-метод.

Рассматриваются три "мира", с которыми имеют дело методы НАД:

"Первый мир" - стохастический. В этом мире события случайны, а закономерности носят частотный, вероятностный характер. Для решения задач ИАД в этом мире лучше всего методы мягких вычислений, статистические методы (например, ОиНА-метод).

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

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

В задачу методов ИАД в первом "мире" входит поиск частотных закономерностей, тогда как во втором и третьем "мирах" - поиск причинно-следственных закономерностей.

характеризуется следующими двумя положениями.

1. Количественный JSM-метод - это метод ИАД, позволяющий исследовать структурные причины свойств и прогнозировать проявление свойств у объектов.

2. Количественный JSM-метод применим в тех предметных областях, где свойства объектов частично детерминированы их структурой. В таких предметных областях закономерности, связывающие структуру объекта и его свойства, подвержены несистематическим исключениям.

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

Через Р, Q, R будем обозначать предикативные константы, через х, у, z -предметные переменные и через а, Ь, с - предметные константы. Будем использовать только формулы, находящиеся в предваренной нормальной форме. Любое свободное вхождение переменной будем считать связанным квантором общности. Обще-импликативной гипотезой будем называть формулу вида P(x)nQ(x). Под фактом будем понимать формулу, не содержащую вхождений предметных переменных. Рассмотрим константу с. Возможны четыре варианта взаимной истинности Р(с) и Q(c): P(c)&Q(c), P(c)&-,Q(c), -.P(c)&Q(c) и -.P(c)&-.Q(c). Рассмотрим гипотезу И: Р(х) з Q(x).

Гипотезой, противоположной h мы будем называть гипотезу h' ^ Р(х) з —iQ(x). Так, для гипотезы "Все кони - белые" противоположной является "Белых коней не существует".

Если из факта р логически выводимо P(c)&-,Q(c), будем говорить, что фактр опровергает или фальсифицирует гипотезу h. Действительно, P(c)&-,Q(c) и -i(Vx: P(x)=Q(x)). .

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

Если из факта р логически выводимо P(c)&Q(c), будем говорить, что факт р подтверждает гипотезу И. Дело в том, что P(c)&Q(c) соотносится с гипотезой h следующим образом: он опровергает противоположную ей гипотезу. Действительно, P(c)&Q(c) 1--,(Vx: Р(х) з —.Q(x)). Поэтому разумно считать этот факт аргументом в пользу гипотезы: он гарантирует, что, по крайней мере, противоположная гипотеза неверна. Кроме того, этот факт "демонстрирует" гипотезу в действии: он показывает пример того, как эффект Q вызывается причиной Р.

Рассмотрим два оставшихся случая, а именно те факты, для которых посылка гипотезы не выполняется: -,P(c)&Q(c) и -.Р(c)&-,Q(c). Ни один из этих фактов не подтверждает, но и не опровергает ни рассматриваемую гипотезу, ни гипотезу ей противоположную. Поэтому аргументами за или против этой гипотезы, с точки зрения ее истинности, эти два факта не являются. Однако каждый из этих фактов интересен с другой точки зрения: с точки зрения значимости, или объясняющей силы гипотезы.

Неформально, значимость гипотезы тем меньше, чем больше фактов, необъяснимых с ее помощью. Таким образом, разумно считать, что если из факта р логически следует -iP(c)&Q(c), то р снижает значимость гипотезы h.

Если же из факта р логически следует —.P(c)&-,Q(c), то будем говорить, что р косвенно повышает значимость гипотезы h. Несложно показать, что этот факт снижает значимость противоположной гипотезы.

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

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

Итак, основа для фальсификации гипотезы А - ее аргументационная четверка:

= <рго(й), соп(Л),

компонентами которой являются числа фактов, подтверждающих И - рго(й), опровергающих Л - соп(/>), косвенно повышающих значимость /? - s^g*(h) и понижающих значимость Ь -

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

Первое из этих отношений - отношение импликативной привлекательности. '-<Г - рассматривает только факты, имеющие отношение к истинности гипотез. Этот подход состоит в следующем: мы считаем, что гипотеза Ь| не хуже, чем гипотеза Ь2, если количество фактов, подтверждающих Ь| не меньше, чем количество фактов, подтверждающих Ь2, и количество фактов, опровергающих Ь| не больше, чем количество фактов, опровергающих И2:

• Ь2 Ь, (рго(Ь|) > рго(Ь2)) & (соп(Ь|) < соп(Ь2)).

Если Ь2 Ь|, будем говорить, что Ь| ¡-лучше, чем Ь2.

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

см. Гаек П, Гавранек Т. Автоматическое образование гипотез.— М.: Наука, 1984.

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

Примем следующее сокращение. Если С: М4->{1, Ц, а Ь - гипотеза: С(Ь) ^ С(рго(Ь), соп(И), 5!8+(Ь), з18-(Ь)).

Критерии, сохраняющие '-V называются ассоциативными. -<1 -импликативными. Любой импликативный критерий является также и ассоциативным. Обратное, однако, неверно, то есть существуют ассоциативные, но не импликативные критерии. Примером такого критерия является критерий простой ассоциации: ЗАг/гн, п2, Пз, гц) ^ гнгц > П2П3.

Если сравнить процесс фальсификации гипотез с судебным разбирательством, то количественному критерию фальсификации отводится роль судьи: он может как "осудить" (фальсифицировать) гипотезу, так и "оправдать" (верифицировать) ее. Рассмотрим свойства, которыми должен обладать С, чтобы считаться "разумным" (честным) судьей.

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

Еще один показатель "разумности" для критериев фальсификации гипотез состоит в следующем. Пусть Ь - некоторая гипотеза, а И' - гипотеза ей противоположная. Критерий фальсификации можно считать "Неразумным", если он верифицирует и Ь, и Ь'. Другими словами, если "разумный" критерий принимает (верифицирует) гипотезу Р(>{):э(}(х), то он должен отвергнуть (фальсифицировать) гипотезу Р(х) г? -10(х). Критерии фальсификации, которые удовлетворяют этому требованию, будем называть бесконфликтными. Таким образом, критерий С является бесконфликтным, если

УП1, п2, Пз, ЩеМ: -,С(П1, п2, Пз, гц) V -,С(п2, пь п4, п3).

Ассоциативность и бесконфликтность объявляется необходимыми свойством критериев фальсификации гипотез в количественном ^М-метоле. Примеры ассоциативных бесконфликтных критериев:

• критерий запрета на контрпримеры: СИ{пь п2, п3, п4) ^ (п2 = 0);

• обобщенный критерий запрета на контрпримеры : СС*.Г(П1, п2, п3, п4) ^ (П1 >к)& (п2 < г),

где к, г б N. к>г;

• критерий обоснованной р-импликации: FIp.ki.nu п2, п3, П4)^(П1> к)& (П1 >р (п!+п2)), где£е Ы,ре(2, 0.5 <р< 1;

• критерий простой ассоциации: 8АР(П1, п2, п3, п4) ^ пгп4 > ер-(п2 п3), где ре(2,р>0.

Формальное определение аргументационной четверки для .18М-гипотез первого рода строится следующим образом.

Пусть <Р, О, А; =>,, =>2; А> - каузоид. рго^ а) М |{о|(оеО) & ^=0) & У„.„,(о=>,а))}| соп„(£ а) Ш |{о](оеО) & ({Ее) & (^-1.п^о=>,а»}| яйЛЬ а) М |{о|(оеО) & ^Ео) & п)(о=>,а»}| я^ХПа) Ш |{о|(оеО)&-,№<>)& (Д„..,(<>=>,а))}| ач„(Г, а) <рго„(Г, а), сопл(П а), ^„'(Г, а), в^ДГ. а)>

Для произвольного критерия фальсификации гипотез С примем следующее сокращение: •

Сп^а) ^ С(ргоп(^ а), соПп(^ а), э^пЧЪ а), а)).

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

Кроме четырех приведенных критериев фальсификации .18М-гипотез количественный ^М-метод допускает применение и других бесконфликтных

ассоциативных критериев, например, критериев, традиционно используемых в статистических исследованиях, таких как критерий Фишера, критерий у} и др. Более того, проблема выбора критерия фальсификации, наилучшего для применения в конкретной задаче ИАД, является весьма актуальной и требует соответствующей теории (по всей видимости, статистической). Однако дальнейшее исследование этой проблемы выходит за рамки диссертационной работы. В описании правил вывода и алгоритмов количественного .15М-метода будем полагать, что соответствующий критерий фальсификации гипотез выбран, "зафиксирован", оставляя в стороне вопрос, каким именно образом это было сделано.

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

НТМЬ-документов на русском языке.

Для описания правил вывода количественного ЛвМ-метода

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

ассоциативности.

Фрагмент ( является ./верифицированным положительным сходством для свойства а, если он является сходством . непустого множества положительных примеров свойства а, и критерий .>"верифицирует гипотезу 'Т является причиной наличия а ". Понятие ./"верифицированного отрицательного сходства вводится двойственным образом.

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

Система правил первого рода количественного ^М-метода состоит из трех правил: (I/), (IД (I,1):

(I/): ^=>23), а) Ьп+1>(Г=>2а),

(|/>: „)(Г=>2а), Г/ХЬа) Ь 1<.|.„+|>(^2а),

(|.;>: V п)(£=>2а), >,/*(?, а), -.Г/"^. а) Ь п+|,(Г=>2а),

где

Правило (I/) гласит: если до п-ного шага вывода никакой причинно-следственной связи между фрагментом Г и свойством а обнаружено не было, и ( является ./-верифицированным положительным сходством, то f является причиной наличия свойства а. Правило (I,") устроено двойственным образом. Правило (Iу) констатирует, что если правила (I/) и (!,-') неприменимы, то на п-ном шаге вывода никаких гипотез относительно причинно-следственной связи между фрагментом 1 и свойством а выявить не удалось.

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

В третьей главе «Приложения количественного .18М-метода» излагается опыт применения систем ИАД, основанных на количественном .18М-методе.

Системы ИАД, основанные на количественном ^М-методе, успешно зарекомендовали себя для решения ряда практических задач, в частности: • распознавание кодировки НТМЬ-документов на русском языке (в системах просмотра документов глобальной компьютерной сети Интернет),

• прогнозирование рецидива аденомы гипофиза (в нейрохирургии),

• восстановление номинальных анкетных данных (в социологических исследованиях).

Основанная на количественном JSM-методе система распознавания кодировки русскоязычных HTML-документов используется в коммерческой версии программы просмотра документов сети Интернет (интернет-браузера) "AMSD Ариадна".

Текст HTML-документа, также как и любой другой текст, представляется в памяти компьютера как последовательность байтов - чисел от нуля до 28. Каждый байт соответствует одному символу текста - букве, пробелу, символу конца строки и т.д. Таким образом, буквы "закодированы" в памяти компьютера при помощи чисел. Кодировкой текста называется соответствие, определяющее, какая буква каким числом обозначается. Для русского алфавита существует пять наиболее распространенных кодировок: WIN (используется в ОС семейства Windows), KOI-8 (используется в ОС семейства Unix), MAC (используется в ОС Mac OS), DOS (используется в ОС DOS), ISO (также используется в ОС DOS).

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

В этой задаче объектами являются последовательности чисел, кодирующие HTML-документы. Целевыми свойствами являются: "соответствующий документ находится в кодировке WIN", "соответствующий документ находится в кодировке KOI-8", и т.д. В качестве фрагментов объекта

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

Задачей количественной JSM-системы являлось построение алгоритма распознавания кодировки. Другими словами, система должна была обучиться распознаванию кодировки HTML-документов. Для обучения системе были предъявлены примеры коротких документов (в одно-два предложения), находящиеся в различных кодировках. Случайным образом были отобраны 250 HTML-документов, размещенных в сети Интернет. Из них были изготовлены 2500 "коротких" HTML-документов (для этого из каждого исходного документа были отобраны по десять первых предложений). Полученные таким образом "короткие" документы были закодированы в каждой из пяти кодировок. В результате, для каждого целевого свойства имелось 2500 положительных примеров и 10000 отрицательных.

В процессе обучения системой было получено около 400 фрагментов -причин для каждого целевого свойства. База знаний системы содержит порядка 2000 гипотез первого рода. Эта база знаний и используется в подсистеме распознавания кодировки программы "Ариадна".

Для тестирования системы с помощью специальной программы-"робота' были отобраны около 6000 документов, в которых кодировка была указана (i теле самого документа или. HTTP-заголовка). Программа успешно распознал кодировку более чем 97% . документов. Кодировка, "рекомендованная программой, отличалась от кодировки, указанной в документе, только в те случаях, если (а) кодировка в документе была указана неверно или (I программа "рекомендовала" кодировку "WIN", а документ находился

кодировке "MAC", причем документ был относительно небольшого размера -не более четырех предложений. Случай (а) в комментариях не нуждается. Случай (Ь) объясняется тем обстоятельством, что в кодировках MAC и WIN строчным буквам соответствуют одинаковые числа. Таким образом, представления текста, не содержащего прописных букв, в кодировках MAC и WIN идентичны.

Важно отметить, что на примере задачи распознавания кодировки HTML-документов количественный JSM-метод успешно зарекомендовал себя как средство автоматизированного создания алгоритмов распознавания. Выгода применения такого подхода очевидна - он позволяет создавать эффективные ;лгоритмы при минимальных трудозатратах. Модуль распознавания кодировки в "AMSD Ариадна" был разработан менее чем за неделю силами коллектива из двух программистов. Кроме того, системой были получены вполне интерпретируемые гипотезы: большинство фрагментов-причин состояли из морфов русского языка (в основном - флексий) либо же устойчивых сочетаний морфов. Это обстоятельство обеспечило безупречное распознавание кодировки даже для документов с орфографическими ошибками и "придуманными" словами. В частности, система успешно распознает кодировку знаменитого примера Л.В.Щербы "Глокая куздра штеко будланула бокра и кудрячит бокренка".

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

обратить особое внимание на те (к сожалению, не все те) САГ, опасность рецидива которых велика.

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

Формально, в этой задаче объектами и фрагментами являются множества пар вида <а, у>, где а есть атрибут конкретного САГ, V - его значение. Например, {<злокач., +>, <размер, ср>, < ЗТв, ->} описывает САГ со следующими характеристиками: опухоль злокачественная, среднего размера, гормоны группы БТС не выделяет. Операция сходства определяется в этой задаче как теоретико-множественное пересечение атрибутивных представлений САГ. Целевым свойством в этой задаче является свойство САГ "сопровождаться рецидивом после удаления". Гипотезы о причинах целевого свойства были получены системой на основе анализа обучающей выборки, состоящей- из 240 описаний САГ, про 68 из которых было известно, что они сопровождались рецидивом. Для тестовой выборки из 400 примеров полнота прогнозирования составила 43%, точность - 76%.

Эксперты ИНХ им. Бурденко дали высокую оценку интерпретируемости полученных гипогез: каждая гипотеза была охарактеризована как класс отягчающих факторов, вызывающих рецидив аденомы. К существенным недостаткам системы была отнесена низкая (сравнительно с методами деревьев решений) полнота прогнозирования.

На кафедре логико-математических основ гуманитарного знания РГГУ была разработана основанная на количественном .18М-методе система восстановления номинальных данных "СВ-2". "СВ-2" позволяет восстанавливать пропущенные значения в таблицах номинальных данных.

Строки в таких таблицах соответствуют объектам, столбцы - номинальным параметрам этих объектов.

В диссертации приводятся результаты тестирования системы "СВ-2" на материале опроса общественного мнения, проведенного Всероссийским центром изучения общественного мнения (ВЦИОМ) в 1997 году. Результаты опроса представлены в виде таблицы, каждой строке которой соответствует конкретная заполненная анкета, а каждому столбцу - вопрос в анкете.

Тестирование "СВ-2" позволило определить точность (отношение числа правильно восстановленных значений к общему числу восстановленных значений) и полноту (отношение числа восстановленных значений к числу отсутствующих значений) восстановления данных. Для этого были выбраны 10 вопросов, для каждого из которых проведена серия из трех однотипных испытаний. В исходной таблице случайным образом выбрали п% строк (10%, 50%, 90%). Во всех остальных строках значения выбранного вопроса удалили. Предоставили системе для обучения выбранные п% строк. После обучения предоставили системе для восстановления оставшиеся (100-п)% строк. Сравнили полученные результаты с исходной таблицей. Полнота распознавания составила от 38% до 70% при среднем — 52% и моде - 65%. Точность распознавания составила от 68% до 96% при среднем - 84% и моде -85%.

При сравнении эффективности применения "СВ-2" и других систем ИАД эксперты ВЦИОМ прежде всего отметили высокую точность восстановления данных при помощи "СВ-2". К существенным недостаткам системы была отнесена сравнительно низкая полнота восстановления. В настоящее время

автором в сотрудничестве с представителями ВЦИОМ ведется разработка

I

новой версии системы, (^снованной на правилах с умолчаниями, а также фальсификации ДБМ-гипотез второго рода по схеме "победитель забирает все". Цель этой модификации - максимально повысить полноту восстановления данных.

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

Основным теоретическим результатом работы является создание метода ИАД, эффективно работающего в областях с частично детерминированными свойствами объектов - количественного ЛБМ-метода. Метод формализует .(БМ-рассуждение, обогащенное количественными критериями фальсификации гипотез. К достижениям работы следует отнести:

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

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

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

4. Разработку комплекса программного обеспечения, основанного на предложенном количественном .(БМ-методе, и внедрение его для решения задач ИАД в нескольких разнородных предметных областях: медицине, социологии, сетевом обеспечении.

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

1. Григорьев П.А. 5\У0гс1-системы или ДСМ-системы для цепочек, использующие статистические соображения. // М.: НТИ. Сер. 2.— 1996,—№5-6,—С. 45-51.

2. Григорьев П.А. Об одном методе автоматического порождения гипотез, схожем с ДСМ-методом: применение статистических соображений. // М.: НТИ. Сер. 2,— 1996,—№ 5-6.—С. 52-55.

3. Григорьев П.А. Результаты тестирования системы восстановления номинальных данных "СВ-2". // Материалы международной научной конференции "НТИ-99. Интеграция. Информационные Технологии. Телекоммуникации". М.: ВИНИТИ. — 1999,—С. 241-242.

4. Григорьев П.А. О перспективах компьютерного прогнозирования рецидива аденомы гипофиза // М.: НТИ. Сер. 2.— 1999.— № 1-2.— С. 83-88.

Введение.

Глава 1. JSM-метод, как средство интеллектуального анализа данных.,.

1. Интеллектуальный анализ данных.

1.1. Определение ИАД.

1.2. Знания в ИАД.

1.3. Данные в ИАД.

1.4. Неформальная классификация методов ИАД.

2. JSM-метод автоматического порождения гипотез.

2.1. Истинностные значения JSM-логики.

2.2. Переменные в JSM-логике: объекты, фрагменты, свойства.

2.3. Внутренние предикаты JSM-логики.

2.5. Каузоидные структуры.

2.6. Язык JSM-логики.

2.7. Правила вывода JSM-метода.

2.8. Алгоритмические средства JSM-метода.

Глава 2 Количественный JSM-метод.

1. Предметные области с частично детерминированными свойствами объектов.

2. Аргументация обще-импликативных гипотез.

3. Количественные критерии фальсификации JSM-гипотез.

4. Система правил вывода количественного JSM-метода.

5. Алгоритмические средства количественного JSM-метода.

За последнее время технические возможности для сбора и хранения больших массивов данных значительно возросли. Накоплены миллионы (!) баз данных [51], которые охватывают практически все области человеческого знания. Такой стремительный рост накапливаемых данных вызывает острую необходимость в средствах Интеллектуального анализа данных (Р1АД), которые позволяют автоматически извлекать из больших массивов данных практически полезные знания [65].

В течение последних лет методы ИАД стремительно развивались. Столь же стремительно разрабатывались профаммные средства ИАД, и расширялась область их применения. В предметных областях, где предполагается достаточно жесткий детерминизм, хорошо зарекомендовал себя один из наиболее перспективных методов ИАД - Т8М-метод автоматического порождения гипотез [1, 3, 4, 6-10,13, 23-27, 31, 34, 35, 38-43, 48, 49]. В областях, где превалируют случайные события, успешно работают методы мягких вычислений [73], статистические методы [15, 57]. Однако для обширного класса задач - задач ИАД в предметных областях, где причинно-следственные закономерности сосуществуют со случайными событиями, применение как 18М-метода, так и других известных методов ИАД оказывается недостаточно эффективным. гр u u u

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

Целью настоящей работы является разработка логико-алгоритмического аппарата, обеспечивающего эффективное решение задач ИАД в предметных областях с частично детерминированными свойствами объектов.

Для достижения поставленной цели необходимо:

1. Изучить возможности существующих методов ИАД для работы в предметных областях с частично детерминированными свойствами объектов.

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

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

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

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

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

Апробация работы. Результаты работы докладывались на международных конференциях НТИ-97 и НТИ-99, а также на научном семинаре Отдела теоретических и прикладных проблем информатики Всероссийского института научной и технической информации (ВИНИТИ). Основные результаты диссертации опубликованы в ряде статей [18, 19, 21, 22 .

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

Работа состоит из введения, трех глав и заключения.

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

Основной теоретический результат настоящей работы -количественный 18М-метод - излагается во второй главе. Прежде всего, уточняется область применения количественного 18М-метода. Затем предлагается формализация интуитивного понятия аргументации гипотез, исходя из которой, формулируются количественные критерии фальсификации 18М-гипотез. Формулируются правила правдоподобного вывода, задействующие предложенные критерии. Предлагаются алгоритмические решения, реализующие количественный 18М-метод.

Третья глава посвящена результатам применения количественного 18М-метода в конкретных задачах ИАД. Рассматриваются три направления применения метода: распознавание свойств объектов, прогнозирование свойств объектов и восстановление данных. Компьютерные системы ИАД, реализующие количественный 18М-метод, продемонстрировали универсальность метода при решении существенно различных задач:

• прогнозирование рецидива аденомы гипофиза (в нейрохирургии),

• распознавание кодировки НТМЬ-документов на русском языке (в системах просмотра документов глобальной компьютерной сети Интернет),

• восстановление номинальных анкетных данных (в социологических исследованиях).

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

JSM-метод как средство интеллектуального

1.5. Выводы

В заключение этого раздела отметим следующие обстоятельства.

Во-первых, на примере задачи распознавания кодировки НТМЬ-документов, количественный Т8М-метод успешно зарекомендовал себя, как средство автоматизированного создания алгоритмов распознавания. Выгода применения такого подхода очевидна - он позволяет создавать эффективные алгоритмы при минимальных трудозатратах. Система СЬаг8е1Весос1ег была разработана менее чем за неделюЛ силами коллектива из двух программистов.

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

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

Не считая времени, потраченного на тестирование системы, что составило еще около полутора недель. словами. В частности, система успешно распознает кодировку знаменитого примера Л.В.Щербы "Глокая куздра штеко будланула бокра и кудрячит бокренка", а также более распространенных в Интернет примеров из программистского жаргона, как то: "интеррапт слипера по таймеру", "хедер бажный - компилится с варнингами" и т.д.

2. Прогнозирование рецидива аденомы гипофиза

В 1997-98 годах автором совместно с Брускиной Д.Г. был проведен ряд компьютерных экспериментов [12], [22]. Целью этих экспериментов являлась оценка возможности создания интеллектуальной партнерской системы, которая позволяла бы определить степень риска возникновения у больного рецидива аденомы гипофиза после ее удаления. На основе количественного JSM-метода нами была разработана экспериментальная система прогнозирования рецидива аденомы гипофиза, которая носит рабочее название HTRD (Hypophisis tumor relapse diagnostics).

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

1) Партнерская система прогнозирования рецидива аденомы гипофиза (ПСП РАГ) основана на анализе случаев аденомы гипофиза (САГ).

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

3) С помощью ПСП РАГ можно частично прогнозировать рецидив аденомы гипофиза. Это означает, что по описанию САГ система может сделать: a) заключение о том, что опасность рецидива (очень) велика, b) заключение о том, что система не способна оценить опасность рецидива.

В этом смысле, практическая ценность ПСП РАГ заключается именно в том, что она позволит обратить особое внимание на те (к сожалению, не все те) САГ, опасность рецидива которых велика.

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

Формально, в этой задаче объектами и фрагментами являются множества пар вида <а, у >, где а есть атрибут конкретного САГ, V - его значение. Например, {<злокач., +>, <размер, ср>, < 8Тв, ->} описывает САГ со следуюш,ими характеристиками: опухоль злокачественная, среднего размера, гормоны группы 8ТО не выделяет.

Операция сходства определяется в этой задаче как теоретико-множественное пересечение атрибутивных представлений САГ. Пусть о, 8 суть описания САГ: о = {< злокач., +>, <размер, ср>, < 8ТО, ->, < РКОЬ, +>},

8 = {< злокач., +>, <размер, м>, < 8ТО, ->, < РКОЬ, ->}.

Тогда о П 8 = {< злокач., +>, < 8ТО, ->}. То есть, сходство этих объектов фиксирует тот факт, что обоих случаях опухоль злокачественная и не выделяет гормоны группы 8ТО.

Целевым свойством в этой задаче является свойство САГ "сопровождаться рецидивом".

Гипотезы о причинах целевого свойства были получены системой НТКО на основе анализа обучающей выборки. Последняя состояла из 240 описаний САГ, про 68 из которых было известно, что они сопровождались рецидивом.

Для тестовой выборки из 400 примеров полнота прогнозирования составила 43%, точность - 76%.

Эксперты ИЫХ им. Бурденко дали высокую оценку интерпретируемости полученных гипотез: каждая гипотеза была охарактеризована как класс отягчающих факторов, вызывающих рецидив аденомы. К существенным недостаткам системы была отнесена низкая (сравнительно с методами деревьев решений) полнота прогнозирования.

3. Восстановление номинальных анкетных данных в социологических исследованиях.

Основанная на количественном 18М-методе, система восстановления номинальных данных "СВ-2" была разработана в 1998 году на кафедре логико-математических основ гуманитарного знания Российского государственного гуманитарного университета.

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

• пол (бинарный параметр, допустимые значения суть

II ^ II II II \ мужской и женский )

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

Примером неноминального параметра является возраст, указанный в годах. Действительно, значения "51 год" и "52 года" семантически ближе друг к другу, чем "51 год" и "25 лет".

Система "СВ-2" поддерживает два режима обучения: режим полного обучения и режим ускоренного обучения.

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

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

Ниже приводятся результаты тестирования системы "СВ-2" на материале опроса общественного мнения, проведенного Всероссийским центром изучения общественного мнения (ВЦИОМ) в 1997 году. Результаты опроса представлены в виде таблицы, каждой строке которой соответствует конкретная заполненная анкета, а каждому столбцу - вопрос в анкете.

Тестирование производилось на кафедре Логико-математических основ гуманитарного знания Российского государственного гуманитарного университета. Цель тестирования - определить точность и полноту восстановления данных с помощью системы "СВ-2". Под точностью мы понимаем отношение числа правильно восстановленных значений к общему числу восстановленных значений.

Под полнотой - число восстановленных значений (правильно или не правильно) к числу изначально отсутствующих значений. Например, пусть до восстановления данных в таблице отсутствовало 100 значений, то есть, сто клеток были пусты. И пусть система восстановила 80 значений, причем 60 - правильно, а 20 - неправильно. То есть, в восьмидесяти из ста клеток появились значения, причем двадцать из этих значений не соответствовали действительности. Тогда точность восстановления есть 60/80, то есть 0.75, или 75%. Полнота же восстановления данных в этом случае составляет - 80/100, то есть 0.8, или 80%

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

1) В исходной таблице случайным образом выбрали п% строк. Для первого испытания это составило 10%, для второго - 50%, для третьего - 90%.

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

3) Предоставили системе для обучения выбранные п% строк.

4) После обучения, предоставили системе для восстановления оставшиеся (100-п)%) строк.

5) Сравнили полученные результаты с исходной таблицей

Вопрос №1. СКАЖИТЕ, ДЕЛА В СТРАНЕ ИДУТ В ПРАВИЛЬНОМ НАПРАВЛЕНИИ, ИЛИ ВАМ КАЖЕТСЯ, ЧТО СОБЫТИЯ ВЕДУТ НАС "НЕ ТУДА", В ТУПИК?

Варианты ответов:

1 дела идут в правильном направлении

2 события ведут нас в тупик 9 затрудняюсь ответить

Вопрос №9. СКАЖИТЕ, ПОЖАЛУЙСТА, КАКОЕ ИЗ СЛЕДУЮЩИХ УТВЕРЖДЕНИЙ, ПО ВАШЕМУ МНЕНИЮ, НАИБОЛЕЕ ТОЧНО ОПИСЫВАЕТ СИТУАЦИЮ В СТРАНЕ?

Варианты ответов:

1 становление диктатуры

2 сохранение прежнего политического порядка год новыми названиями

3 развитие демократии

4 утрата порядка, нарастание анархии 9 затрудняюсь ответить

Вопрос №11. в ПРИНЦИПЕ, ЕСЛИ НЕ ПРИНИМАТЬ ВО ВНИМАНИЕ НЫНЕШНЮЮ ПОЛИТИЧЕСКУЮ СИТУАЦИЮ, ДЕМОКРАТИЧЕСКАЯ СИСТЕМА УПРАВЛЕНИЯ - ЭТО ТО, ЧТО НУЖНО РОССИИ ИЛИ то, ЧТО ВРЕДНО для НЕЕ?

Варианты ответов:

1 1^жго России

2 вредно для России

9 затрудняюсь ответить

Вопрос №22А. ЕСЛИ БЫ У ВАС БЫЛА ВОЗМОЖНОСТЬ ВЫБОРА, КАКИЕ УСЛОВИЯ ВЫ БЫ ПРЕДПОЧЛИ?

Варианты ответов:

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

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

Вопрос № 40А. СКАЖИТЕ, БУДЕТЕ ЛИ ВЫ ПРИНИМАТЬ УЧАСТИЕ В "МИРНОЙ" АКЦИИ ПРОТЕСТА МИТИНГА,ДЕМОНСТРАЦИИ, РАЗРЕШЕННЫХ ВЛАСТЯМИ?

Варианты ответов:

1 скорее всего да

2 скорее всего нет

9 затрудняюсь ответить

Рисунок 7. Примеры номинальных анкетных вопросов.

Полнота распознавания составила от 38% до 70% при среднем -52% и моде - 65%. Точность распознавания составила от 68%) до 96% при среднем - 84% и моде - 85%).

При сравнении эффективности применения "СВ-2" и других систем ИАД эксперты ВЦИОМ прежде всего отметили высокую точность восстановления данных при помощи "СВ-2". К существенным недостаткам системы была отнесена сравнительно низкая полнота восстановления. В настоящее время автором в сотрудничестве с представителями ВЦИОМ ведется разработка новой версии системы, основанной на правилах с умолчаниями, а также фальсификации 18М-гипотез второго рода по схеме "победитель забирает все". Цель этой модификации - максимально повысить полноту восстановления данных.

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

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

В первой главе было дано определение интеллектуального анализа данных (ИАД); перечислены наиболее известные методы ИАД, предложена их классификация; подробно рассмотрен один из весьма перспективных методов ИАД - 18М-метод автоматического порождения гипотез.

Во второй главе была рассмотрена классификация предметных областей по типам закономерностей, в них доминирующих, а именно: частотных закономерностей, жестких причинно-следственных закономерностей и причинно-следственных закономерностей, допускающих несистематические изменения. Далее во второй главе построена формализация интуитивного понятия количественной аргументации обще-импликативных гипотез (гипотез вида \/х:Р(х)зР(х)). На основе этой формализации разработана система требований корректности к количественным критериям фальсификации гипотез: "разумный" критерий должен сохранять отношение ассоциативной привлекательности и быть бесконфликтным. Построена система схем правил правдоподобного вывода количественного 18М-метода, в которой параметром является

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

В третьей главе были изложены результаты применения количественного Т8М-метода при решении практических задач. Рассмотрено три направления применения метода: распознавание кодировки НТМЬ-документов, прогнозирование рецидива аденомы гипофиза (после удаления) и восстановление номинальных анкетных данных в социологических исследованиях.

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

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

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

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

4. Разработку комплекса программного обеспечения, основанного на предложенном количественном 18М-методе, и внедрение его для решения задач ИАД в нескольких разнородных предметных областях: медицине, социологии, сетевом обеспечении.

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

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

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

1. Аншаков О. М. О решетке данных для ДСМ-метода автоматического порождения гипотез. // НТИ. Сер. 2.-1996.-№ 5-6

2. Аншаков ОМ. 1-логики и соответствующие им классы алгебр. // Логические исследования. Вып. 5.— М.: Наука.— 1998.— С.25-52.

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

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

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

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

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

8. Аншаков О.М., Скворцов Д.П., Финн В.К. О дедуктивной имитациинекоторых вариантов ДСМ-метода автоматического порождения гипотез // Семиотика и информатика.— 1993.— Вып. 33.— С. 164-233.

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

10. Бобылева Н.В., Ивашко В.Г., Краснова В.М., Финн В.К. Применение ДСМ-систем в задачах технической диагностики // Семиотические аспекты формализации интеллектуальной деятельности: Тез. докл. школы-семинара "Боржоми-88".— М.:ВИНТИ.— 1988.—С. 178-182.

11. Братко И. Программирование на языке Пролог для искусственного интеллекта.— М.:Мир.— 1990.— 560 с.

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

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

14. Виноградов Д.В. Логические программы для квазиаксиоматических теорий // НТИ. Сер. 2.— 1999.— № 1-2.— С. 61-64.

15. Гаек П, Гавранек Т. Автоматическое образование гипотез.— М.: Наука, 1984.—280 с.

16. Гемпелъ КГ. Логика объяснения.— М.: Дом интеллектуальной книги.— 1998.—240 с.

17. Гладкий A.B. Математическая логика.— М.: РГГУ.— 1998.— 479 с.

18. Григорьев П.А. Об одном методе автоматического порождения гипотез, схожем с ДСМ-методом: применение статистических соображений // НТИ. Сер. 2.— 1996.— № 5-6.— С. 52-55.

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

20. Григорьев П.А. Об одной модернизации ДСМ-метода: применение статистических соображений.— Дипломная работа.— М:РГГУ.— 1997.

21. Григорьев П.А. Результаты тестирования системы восстановления номинальных данных "СВ-2". // Материалы международной научной конференции "НТИ-99. Интеграция. Информационные Технологии. Телекоммуникации". М.: ВИНИТИ. — 1999.— С. 241-242.

22. Григорьев П.А. О перспективах компьютерного прогнозирования рецидива аденомы гипофиза // НТИ. Сер. 2.— 1999.— № 1-2.— С. SS-SS.

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

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

25. Кузнецов СО. Интерпретация на графах и сложностные характеристики задач поиска закономерностей определенного вида // НТИ. Сер. 2.— 1989.— № 1— С. 23-28.

26. Кузнецов СО. Введение в ДСМ-метод // Семиотика и информатика.—1990. —Вып. 31.—С. 5Л0.

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

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

29. МейерД. Теория реляционных баз данных .— М.: Мир, 1987.— 608 с.

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

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

32. Объедков CA. Алгоритмические аспекты ДСМ-метода автоматического порождения гипотез // НТИ . Сер . 2.— 1999.— № 1-2.— С. 64-75.

33. Панкратов Д.В. О возможности применения ДСМ-метода в задаче распознавания химического канцерогеноза. // НТИ . Сер . 2.— 1999.— № 1-2.— С. 76-82.

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

35. СкворцовД.П. О некоторых способах построения логических языков с кванторами по кортежам // Семиотика и информатика.— 1983.— Вып. 20.—С. 102-126.

36. Уоссермен Ф. Нейрокомпьютерная техника.— М.: Мир, 1992.— 236 с.

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

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

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

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

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

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

43. Финн В.К Об интеллектуальных системах автоматизированной поддержки научных исследований // НТИ. Сер. 2.— 1996.— № 5-6.— С. 1-2.

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

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

46. Черч А. Введение в математическую логику, т. 1.— М.: ИЛ.—1961.

47. Anshakov О.М., Finn V.K., Skvortsov D.P. On axiomatization of manyvalued logics associated with formalization of plausible reasoning // Studia Logica.— 1989.— Vol. 48. N4.— pp. 423-447.

48. Bornholdt, S. and Graudenz, D. General Assymmetric Neural Networks and Structure Design by Genetic Algorithms. // Neural Networks, N5.— 1992.— pp.327-334

49. Chen M.S., Han J., Yu P.S. Data Mining: An Overview from a Database Perspective.// IEEE Transactions on Knowledge and Data Engineering. —1996. — Vol 8.— pp. 866-883.

50. Donoho, S. K. Knowledge-Guided Constructive Induction. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign.— 1996

51. Ganter B. Kapitel Algorithmen zur Formalen Begriffsanalyse.— BI-Wissenschaftsverlag.— 1987.

52. Ganter B, Wille R. Formal Concept Analysis. Mathematical Foundations.— Berlin-Heidelberg-New York: Springer.— 1999.

53. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. MA: Addison-Wesley.— 1989.

54. GotthardW., Marwick A., SeittertR. Mining Text Data // DB2 Magazine.—1997. —V2.— http://www.db2mag.com/97wiGot.htm

55. Hajek P., Havranek T., Chytil M. Metoda GUHA. Automoticka tvorba hypotez.— Praha: Academia.— 1983.

56. Haykin, S. Neural Networks: A Comprehensive Foundation.— NY: Macmillan College Publishing.— 1994.

57. KiselevM. V. PolyAnalyst a machine discovery system inferring functional programs // Proceedings of AAAI Workshop on Knowledge Discovery in Databases'94, Seattle.— 1994.— pp. 237-249.

58. KiselevM. V. PolyAnalyst 2.0: Combination of Statistical Data Preprocessing and Symbolic KDD Technique // Proceedings of ECML-95 Workshop on Statistics, Machine Learning and Knowledge Discovery in Databases, Heraklion, Greece.— 1995.— pp.187-192.

59. Kuznetsov S. O. Mathematical aspects of formal concept analysis // Journal of Mathematical Science, Series Contemporary, Mathematics and its Applications.— 1996.— no. 18.— pp. 1654-1698.

60. Leherte L., Glasgow J., Baxter K., SteegE., Fortier S. Analysis of Three-Dimensional Protein Images // Journal of Artificial Intelligence Research.— 1997.—V7.—pp. 125-159.

61. MullerB., Reinhardt J. Neural Networks. An introduction.— Berlin:Springer Verlag.— 1991.

62. Ordonez C., Omiecinski E. Discovering Association Rules Based On Image Content // IEEE Advances in Digital Libraries.—1999.—VI.—pp. 28-41.

63. Piatetsky-Shapiro G, Frawley W.J., Knowledge Discovery in Databases.-US, California: AAAI Press.— 1991.

64. Quinlan, J. R. Simplifyng decision trees // International Journal of Man-Machine Studies, N49.— 1987.— pp.221-234.

65. Quinlan. J. R. Generating production rules from decision trees. // Proceedings of the 10th International Joint Conference on Artificial Intelligence, Milan.— 1987.— pp. 304-307.

66. Rosser J.B., Turquette A.R. Many-valued logics.— Amsterdam: North-Holland.— 1951.

67. Umbreit, S. Formale Begriffsanalyse mit unscharfen Begriffen.— Dissertation an der Mathematisch-Naturwissenschaftlich-Technischen Fakultat der Martin-Luther-Universitat, Halle-Wittenberg.— 1995.

68. VogtF. Formale Begriffsanalyse mit C++.— Berlin: Springer.— 1996.

69. Wille R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts// Ordered Sets, I. Riw2A,Ed.~ Reidel.— 1982.— pp. 445-470.

70. Zadeh, Lotfi. Fuzzy Sets // Information and Control.— 8(3) .— 1965.— pp.338-353.

71. Zadeh Lotfi Fuzzy Logic, Neural Networks, and Soft Computing. Communications of the ACM.— 1994. — Vol. 37. — pp.77 84

72. Рисунок 8. Классификационное дерево: стоимость 2-х комнатнойквартиры в крупном городеА.

73. Будем называть множество гипотез, порождаемых соответствующим методом интеллектуального анализа данных

74. Треб. ремонта, да>} =i> <Цена, низкая>.

75. Теперь рассмотрим наиболее существенные преимущества МПДР перед 18М-методом.

76. Классификационные деревья зачастую являются удобным средством визуализации данных. JSM-метод не предоставляет средств для визуализации данных.

77. МПДР способны работать в условиях зашумленности данных, в то время как традиционные разновидности JSM-метода очень чувствительны к ошибкам в данных.2. Сравнение методов ИАД.

78. STRUCT ATTR NOM NUMS NUMG NOISE SMTS1. POLY1.TERPR VIS

79. Методы построения деревьев решений1. Методы мягких вычислений

80. Методы символьного обнаружения знаний1. СиНА-метод1. Анализ формальных понятий1. Л8М-метод1. Количественный Л8М-метод+