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

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

Волкова Анна Юрьевна

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

05.13.17 - Теоретические основы информатики

5 г:12014

АВТОРЕФЕРАТ

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

005549568

Москва - 2014

005549568

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Российский государственный гуманитарный университет» (РГГУ).

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

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

Официальные оппоненты: Вагин Вадим Николаевич

доктор технических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Национальный исследовательский университет «МЭИ», Институт автоматики и вычислительной техники, кафедра прикладной математики, профессор

Забежайло Михаил Иванович

кандидат физико-математических наук, доцент, Центр прикладных исследований компьютерных сетей «Сколково», управляющий директор

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

Федеральное государственное бюджетное учреждение науки Институт Системного Анализа Российской Академии Наук (ИСА РАН)

Защита состоится «26» июня 2014 г. в 16-00 часов на заседании диссертационного совета Д. 212.198.13, созданного на базе РГГУ, по адресу: 125993, ГСП-3, Москва, Миусская площадь, д. 6, ауд. 206.

С диссертацией можно ознакомиться в библиотеке РГГУ по адресу 125993, ГСП-3, Москва, Миусская площадь, д. 6 и на официальном сайте организации по адресу http://dissovet.rggu.ru/section.html7icNl 1325.

Автореферат разослан «21» мая 2014 г.

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

кандидат технических наук, старший научный сотрудник

Халяпин Дмитрий Борисович

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

Важную роль в развитии направления исследований «искусственный интеллект» играет интеллектуальный анализ данных (ИАД). Под ИАД мы понимаем извлечение нового знания на основе анализа данных посредством интеллектуальной системы (ИС).

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

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

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

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

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

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

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

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

• реализованы различные версии ДСМ-метода АПГ (прямой / обратный ДСМ-метод, ситуационное расширение ДСМ-метода);

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

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

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

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

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

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

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

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

Основные научные результаты, полученные в ходе исследования:

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

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

• Установлено, что разработанные алгоритмические и программные средства ИС применимы для различных предметных областей: фармакологии, медицины и социологии.

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

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

• Осуществлено сравнение результатов различных индуктивных процедур ДСМ-рассуждений на примере анализа фармакологических и медицинских данных.

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

Первая ДСМ-система для анализа данных медицинской диагностики была создана в ВИНИТИ РАН. ДСМ-метод применялся для прогнозирования и диагностики различных заболеваний. На текущий момент в ВИНИТИ РАН действующие системы для анализа медицинских данных программно реализованы Д.А. Добрыниным и О.П. Шестерниковой. Действующая система для анализа фармакологических данных программно реализована Д.А. Добрыниным. ДСМ-Решатель этих систем поддерживает прямой атомарный ДСМ-метод АПГ, включающий процедуры простого метода сходства и запрета на контрпримеры. Первая ДСМ-система для анализа социологических данных была разработана М.А. Михеенковой, а ее первое программное обеспечение было реализовано С.С. Московским. Позже разработкой программных средств в этой области занимались Д.В. Панкратов, Ж.И. Бурковская, Т.Л. Феофанова.

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

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

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

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

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

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

ИС, применяемой в Российском Онкологическом Научном Центре РАМН имени H.H. Блохина.

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

Впервые были реализованы средства для распознавания непротиворечивости множеств порожденных гипотез. Было разработано представление социологических данных, допускающее разбиение характеристик респондента на четыре компоненты (описание респондента, мнение по заданным вопросам, ситуация (контекст, внешние обстоятельства), исследуемый эффект(ы)) и удовлетворяющее условиям применимости ДСМ-метода. Представление используется для нестатистического анализа — для выявления детерминант поведения и мнений, а также для исходных массивов данных небольших размеров, что исключает возможность использования статистических средств. Как было отмечено, впервые создан Решатель задач, реализующий ДСМ-рассуждения, которые используют четыре метода индукции: сходства, различия, сходства-различия, остатков с возможностью добавления условий запрета на контрпримеры и единственности причины/следствия (ранее методы различия, сходства-различия и остатков не были реализованы посредством программ). Этот Решатель задач является главным модулем впервые созданной компьютерной интеллектуальной системы типа ДСМ JSM-Socio для качественного анализа социологических данных. JSM-Socio позволяет использовать упомянутые методы, а также разработанное многокомпонентное представление знаний о субъекте поведения, включающее описание субъекта (социальный характер субъекта, индивидуальные черты личности биографические данные), его мнение (о ситуации, о возможном поведении), ситуацию (контекст поведения) и эффект поведения (действие или установка к действию). ИС JSM-Socio является эффективным практическим инструментом для социологических

исследований. Она обладает важными функциональными возможностями, обеспечивающими комфортную работу для социолога-исследователя. Среди них следует отметить следующее: автоматический перевод файлов с данными из формата программы SPSS в формат, используемый системой (MS Excel); разделение вопросов анкеты на компоненты; автоматическое разделение респондентов на группы в соответствии с эффектом, выделенным для исследования; применение различных стратегий (прямой/ обратный, ситуационный ДСМ-метод); графический интерфейс, разработанный с учетом требований эксперта. С помощью JSM-Socio были исследованы данные с многокомпонентной структурой, сформированные на материале анкет работников промышленных предприятий, а также проведены эксперименты для сравнения стран по уровню одобрения населением протестного поведения.

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

Практическая значимость диссертационного исследования состоит в следующем:

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

• В разработанном Решателе реализованы методы ДСМ-рассуждений, в том числе методы, отсутствующие в других системах: метод различия, метод сходства-различия, метод остатков [1]. В системе доступны прямой и обратный тип ДСМ-рассуждений, а для анализа социологических данных реализовано ситуационное расширение ДСМ-метода.

• Разработанные средства позволили сравнить новые стратегии на разных предметных областях. Кроме того, при исследовании медицинских данных

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

Апробация результатов диссертации. Основные положения диссертационной работы были изложены на российско-британской конференции "J. S. Mill's ideas on Induction and Logic of the Humanities in Cognitive Research and Artificial Intelligence Systems" (15 - 17 июля 2011 г., РГГУ). Во время выступления была представлена презентация «Интеллектуальная система, реализующая четыре индуктивных метода Д.С. Милля» и продемонстрирована ДСМ-система для анализа разных предметных областей: фармакологии и медицинской диагностики. Результаты, полученные в ходе работы с социологическими данными, были представлены на межвузовской конференции «20 лет научных исследований и образовательных программ отделения интеллектуальных систем в гуманитарной сфере» (14 декабря 2012 г., РГГУ). В рамках выступления «Интеллектуальные системы типа ДСМ и их приложения» было продемонстрировано приложение-интерфейс, созданное для просмотра социологических данных, обработанных с использованием реализованной ДСМ-системы.

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

(JSM-Socio), реализующая стратегии ДСМ-метода АПГ. Система была официально зарегистрирована Федеральной службой по интеллектуальной собственности (РОСПАТЕНТ) и внесена в Реестр программ для ЭВМ (№ 2013614978, от 24 мая 2013 года).

Система JSM-Socio была представлена на XVI-м Междисциплинарном ежегодном научном семинаре «Математическое моделирование и информатика социальных процессов» им. Героя Социалистического труда академика А.А. Самарского (21 ноября 2013 г., МГУ им. М.В.Ломоносова, факультет ВМиК) в рамках доклада «О подходах к формализации качественного анализа социологических данных». Кроме того, система была продемонстрирована на семинаре «Принципы, логические средства и опыт применения в социологии ДСМ-метода автоматического порождения гипотез» (6 декабря 2013 г., Институт социологии РАН, Центр теоретических и историко-социологических исследований).

Интеллектуальная система JSM-Socio используется в Институте социологии РАН для решения задач формализованного качественного анализа социологических данных: выявления детерминаций социального поведения и мнений, учёта влияния ситуационных параметров на социальное поведение, прогнозирования социального поведения и общественного мнения.

Публикации. По теме диссертации в настоящее время опубликовано 5 статей в сборниках Научно-техническая информация, Серия 2 (Информационные процессы и системы), рекомендованных ВАК. Три статьи были переведены на английский язык и опубликованы в журнале Automatic Documentation and Mathematical Linguistic.

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

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

ДСМ-метод автоматического порождения гипотез (АПГ) включает 6 компонент [2]: условия применимости, ДСМ-рассуждения, квазиаксиоматические теории (КАТ) как средство организации базы фактов (БФ) и базы знаний (БЗ), метатеоретические исследования предметной области (дедуктивная имитация индукции, аналогии и абдукции, определения исходных предикатов, препроцессинг), средства распознавания эмпирических закономерностей (ЭЗК) и интеллектуальные системы типа ДСМ (ИС-ДСМ). Все компоненты ДСМ-метода представлены в диссертации.

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

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

В ходе диссертационного исследования была создана универсальная ДСМ-система: она может применяться для различных предметных областей и разных структур данных. Архитектура системы представлена в первой главе «ДСМ-Решатель для анализа данных различных предметных областей». Решатель задач подробно описан в первой главе. Модули Информационной среды

12

рассмотрены в первой главе (раздел «Внутреннее представление данных») и во второй главе «Визуальное представление данных». В третьей главе «Графический интерфейс ДСМ-Решателя» описан интерфейс системы, который реализует диалог пользователя и ИС. Он позволяет загрузить подготовленные данные в систему и провести эксперимент с выбранными параметрами. Четвертая глава «Анализ фармакологических и медицинских данных: экспериментальная проверка» демонстрирует применение ДСМ-системы для анализа фармакологических и медицинских данных. Наконец, в пятой главе «ДСМ-система JSM-Socio для анализа социологических данных» рассмотрена независимая компьютерная ИС-ДСМ JSM-Socio для анализа социологических данных, которая является спецификацией универсальной ДСМ-системы. Система состоит из 4 функциональных модулей: модуль предобработки данных (перекодировка данных, обработка файлов Statistical Package for the Social Sciences (SPSS) формата .sav), интерфейс пользователя подготовки данных для эксперимента, ДСМ-Решатель и интерфейс пользователя для просмотра полученных результатов. Система является средством поддержки и проведения социологических исследований, требующих использования БФ с эмпирическими данными. Она позволяет исследовать данные социологического опроса посредством формализованного качественного анализа данных. JSM-Socio подтвердила плодотворность применимости ДСМ-метода-АПГ и ИС-ДСМ. JSM-Socio была официально зарегистрирована Федеральной службой по интеллектуальной собственности (РОСПАТЕНТ) и внесена в Реестр программ для ЭВМ (№ 2013614978, от 24 мая 2013 года). JSM-Socio является единственной отечественной компьютерной системой для формализованного качественного анализа социологических данных.

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

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

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

ДСМ-система JSM-Socio применялась для исследования данных конкретных социологических задач: анализ трудовых отношений на российских предприятиях (в ходе исследования в рамках проекта «Методология и методы ситуационного анализа на предприятии» 1 , проводимого Институтом Социологии РАН и Самарским Государственным Университетом) [3, 4] и (в качестве тестирования системы) сравнение стран по уровню одобрения населением протестного поведения (в рамках диссертационного исследования A.B. Кученковой [5]).

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

1 Проект № 10-06-00033 финансировался Российским фондом фундаментальных исследований. Руководитель проекта - С. Г. Климова. Участники проекта: Н.В. Авдошина, В.Ю. Бочаров, И.А. Климов, М.А. Михееенкова, Б.Г. Тукумцев, В.К. Финн, В.А. Ядов.

для индукции (п.п.в.-1) и правил правдоподобного вывода второго рода для аналогии (п.п.в.-2). Этап I ДСМ-рассуждения - это последовательное применение тактов (п.п.в.-1 -> п.п.в.-2)1 —>(п.п.в.-1 —> п.п.в.-2)2—» ... (п.п.в.-1 —» п.п.в.-2)„ , где п - номер такта стабилизации Этапа I ДСМ-рассуждения. БФ содержит описание предметной области и образована высказываниями (фактами) вида «объект X имеет множество свойств У» (представимых посредством предиката Х=>1 У), которым приписаны оценки (типы истинностных значений) «фактически истинно» (1), «фактически ложно» (-1), «фактически противоречиво» (0), «неопределенно» (т)». Множество свойств У называют эффектом. Положительные примеры (с типом истинностного значения, равным 1) обладают исследуемым эффектом, отрицательные примеры (с типом истинностного значения, равным -1) — не обладают. Неопределенные примеры (с типом истинностного значения, равным т) - это примеры, требующие доопределения. В БФ неявно должны содержаться зависимости причинно-следственного типа: позитивные и негативные причины ((+)- и (-)-причины) исследуемых эффектов. (О)-примеры выражают фактические противоречия или конфликты, образованные «противодействием» (+)- и (-)-причин.

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

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

Простой метод сходства прямого ДСМ-метода формализуется посредством предикатов М ° я (У,\У), образованных пятью условиями: экзистенциальным (ЭУ), сходства (СХ), зависимости (ЭЗ), исчерпываемости (УИ) и нижней границы числа сходных примеров к; ае{+, -, 0}. (СХ) выражает принцип сходства и детерминации, при этом сходство фактов обозначают через переменную V, а «эффект» - через XV. Предикаты вида («V есть причина

\У») используются для представления полученных гипотез, а примеры, их породившие, называются родителями гипотез. (ЭУ) выражает существование (+)-, (-)- или (О)-примеров в БФ или БЗ в достаточном количестве, заданным нижней границей к. Параметр к обычно подбирается экспериментально, но его значение должно быть не меньше двух. (УИ) требует, чтобы при нахождении сходства учитывалось максимально возможное количество сходных примеров. Наконец, (ЭЗ) для предиката М +ап (У,\У) формализует причинную обусловленность наличия эффекта, для предиката М~„(У,\У) - причинную обусловленность отсутствия эффекта или отсутствие причин исследуемого эффекта, для предиката М °а „ (У,\У) - причинную обусловленность

одновременного проявления и отсутствия исследуемого эффекта. (В социологии исследуемый эффект, по которому респонденты разбиваются на (+)-, (-)-, (0)- и (т)-примеры, может иметь следующие ответы на вопросы в анкете: 1 - Да; 0 - И да, и нет; -1 - Нет; т - Нет данных (нет ответа).)

Для простого обратного сходства определены Мс -предикаты. Главное их отличие от предикатов прямого сходства выражено в (ЭЗ): сначала ищется сходство эффектов, а затем — сходство объектов. Гипотезы о причинах представлены посредством предиката \У3<=У («XV есть следствие V»), Влияние ситуации отображается тернарным предикатом Р(Х,У,8) - «субъект X демонстрирует эффекты поведения У в ситуации Б», а предикат причинности

16

принимает вид II,((V, Б'),XV) - «пара (подмножество характеристик субъекта V и характеристики ситуации Б') есть причина эффектов поведения

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

Индуктивный метод сходства с условием существования единственной причины V для следствия \У определяется как усиление (е) простого метода сходства: М°„(У,\У) ^ М^„(У^)&(е)а, где (е)° ~ Уг(М°„(2,\У) -> (У=г)),

сте{+, -}. Единственность следствия задается с помощью усиления предиката М°„ (У,\У): М:с.„ (У,\У) - М:,„ (V, \У)&(с)°, где (с)а - VU ( М°„ (V,

и)-»(и=\У)). Запрет на контрпримеры также является усилением простого метода сходства и задается добавочным условием (Ь)°, где (Ь)+ определяется формулой УХУУ (((УсХ) & (\VciY)) -» (У(М)(Х^,У) V У(тМ(Х=>,V))), а (Ь)" -это УХУУ (((УсХ) & (\УсУ)) -> (./^(Х^У) V ^¿Х=>хУ))). Сходным образом запрет на контрпримеры представлен для обратного и ситуационного ДСМ-метода. Суть условия (Ь)" заключается в том, что ни одна гипотеза о причинах данного знака (+ или -) не должна вкладываться в пример противоположного знака.

В диссертации впервые реализованы новые индуктивные процедуры [1]: два варианта метода различия (второе правило Д.С. Милля и упрощение метода соединенного сходства-различия), метод сходства-различия (третье правило Д.С. Милля), метод остатков (четвертое правило Д.С. Милля) и процедура, упрощающая метод остатков («усеченный метод остатков»), применявшаяся для анализа медицинских данных. Эти процедуры реализованы симметрично для (+)- и для (-)-предикатов.

В общей формулировке для вывода гипотезы о причинах У=>2^У из БФ посредством метода различия Д.С. Милля требуется найти в БФ два факта: факт

17

(Х=>1 У), в котором причина V наличия/отсутствия искомого эффекта XV наблюдается, и факт (2=>,и) с другой оценкой, в котором V не наблюдается, но разность объекта X и причины V не пуста ((Х\У)*0) и входит в Ъ ((Х\У)сг). Миллевский метод различия определяется предикатами О" (У,\У), которые предполагают сравнение всего лишь двух фактов без условий выполнимости подформул Ма-предикатов, остальные методы ДСМ-рассуждений содержат в качестве подформулы предикаты сходства М'ДУ^) или их усиления.

Упрощение метода сходства-различия задается с помощью дополнительного условия (с1о) к предикату простого сходства. Эта условие подтверждает гипотезу о причине У=>2\У, найденную с помощью простого сходства или его усиления, в том случае, если для любого факта (Х=>,У), участвовавшего в порождении гипотезы («родителя»), в БФ не удастся найти фактов ^=>¡1!) с той же оценкой, для которых причина V в объект Ъ не входит (-,(У<г2)), разность объекта X и причины V не пуста и входит в Ъ ((Х\У)*0, (Х\У)с2), эффект V/ включается в множество свойств и (\VclJ).

Положительный метод сходства-различия включает нахождение кандидатов в гипотезы с помощью метода сходства (простого метода или его усилений) и проверку существования множества примеров №=>[И) для каждого родителя Х=>1 У каждой найденной зависимости таких, что: причина V в

объект Ъ не входит; разность объекта X и причины V не пуста и входит в примеры (2=^и) являются отрицательными или «т», если эффект входит в У, и оценка не важна, если эффект в У не входит. Отрицательный метод сходства-различия определяется симметрично. Метод сходства-различия формулируется посредством условия ((10, если V - единственная причина эффекта XV, и (сУ, если V - не единственная причина.

Метод остатков позволяет найти дополнительные гипотезы и определяется предикатами (V, XV), где се {+, -}. «Остатки» получаются после

стабилизации процесса ДСМ-рассуждений в результате просмотра всех

полученных гипотез о причинах и вычисления разностей X\V и YYW для каждого родителя X=>]Y и соответствующей ему гипотезы V=>2\V. К множеству остатков вида (X\V)=>i(Y\W) применяется простой метод сходства. Если найденные на остатках гипотезы непротиворечивы, то они добавляются к общему массиву гипотез, иначе гипотезы не принимаются.

Наконец, «усеченный метод остатков» - это вспомогательная процедура, реализующая упрощение индуктивного метода остатков. Эта процедура может использоваться для выявления среди признаков, описывающих объекты, таких, которые необходимы для наличия исследуемого эффекта. Требуется провести три эксперимента. В первом эксперименте получают гипотезы, которые содержат необходимые признаки (признаки, которые определены экспертом в конъюнктивные фильтры), во втором — получают гипотезы, которые могут как содержать, так и не содержать интересующие эксперта признаки, в третьем -признаки из фильтров вообще не участвуют. «Остатки» получают в результате вычисления разностей каждой (а)-гипотезы из первого эксперимента со всеми (ст)-гипотезами из второго эксперимента, ое{+, —}. Далее остатки сравниваются с гипотезами, полученными в третьем эксперименте Если найдена хоть одна равная пара гипотез, то это значит, что признаки, определенные в конъюнктивные фильтры, не являются необходимыми.

Стратегия ДСМ-рассуждения Str^, характеризуется парой позитивного и негативного предикатов (М ^ (V,W), М (V, W)), используемых для

формулировки правил правдоподобного индуктивного вывода (п.п.в.-1), где х, у - имена предикатов. Буквенные обозначения (а)с, (b)a, (е)°, (d0)a, (dj)", (d2)° соответствуют принятым обозначениям для подформул предикатов, где ае{+,

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

аналогии» приводятся предикаты (V, (ое{+, 0, т}) и реализующий их алгоритм, необходимые для осуществления шага аналогии (п.п.в.-2). Предикат п; (V, XV) доопределяет (т)-пример относительно исследуемого эффекта как положительный и состоит из двух условий: (ЭУ) (+)-гипотез (полученных на шаге индукции), которые доопределяют (т)-примеры из БФ (причина (+)-гипотезы содержится в объекте (т)-примера, а объединение свойств всех таких (+)-гипотез совпадает с эффектом (т)-примера), и условия отсутствия

конфликтующих с ними (-)- или (О)-гипотез. Пй (V, \У) доопределяет (т)-

пример как отрицательный и определяется аналогично. П°0/, \У) доопределяет (т)-пример как противоречивый и требует выполнения (ЭУ) (О)-гипотез (полученных на шаге индукции) или условия одновременного присутствия в БЗ (+)- и (-)-гипотез, у которых причины и свойства содержатся в (т)-примере, при этом эти свойства имеют непустое пересечение. Если ни один из перечисленных предикатов не выполнен, то имеет место V/).

Наконец, абдукция - это процедура объяснения исходного множества фактов и принятия или непринятия на этом основании порождённых гипотез. Реализация абдукции представлена в разделе первой главы «Абдукция и степень абдуктивности». Объяснение примеров из БФ с помощью порожденных гипотез о причинах формализуется посредством аксиом каузальной полноты АКП(а), ае{+, -, 0}. АКП1 выражает объясняемость для (+)-фактов: для каждого (+)-факта (Х=>]У) исходной БФ проверяется наличие экзистенциального условия (ЭУ) (+)-гипотез о причинах (\^=>2\У,), которые в него вкладываются (причина V/ входит в объект X, а объединение всех XV, совадает с У). Аналогично определяется АКПЧ Для исходных (О)-фактов АКП<0) ищет объяснение посредством проверки выполнения условий предиката \У): в БЗ должны либо присутствовать (О)-гипотезы о причинах, которые вкладываются в (О)-факт, либо в БЗ есть и (+)-, и (-)-гипотезы, у которых причины и свойства содержатся в (О)-факте, а свойства этих (±)-гипотез имеют

непустое пересечение. Отношение числа исходных (+)-, (-)- и (О)-фактов из БФ, объяснённых порожденными гипотезами о причинах, к общему числу фактов соответствующего знака в БФ называется степенью каузальной полноты или степенью абдуктивности р", где ае{+, 0} [1]. При проверке АКП(0) вводят некоторое пороговое значение, с которым сравнивают полученные значения степени абдуктивности (обычно оптимальным принято считать пороговое значение, равное 0.8). Если степень абдуктивности оказывается меньше допустимого порога, то гипотезы не принимаются.

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

Третья компонента ДСМ-метода состоит в представлении данных (БФ) и знаний (гипотезы, ДСМ-процедуры). В первой главе «ДСМ-Решатель для анализа данных различных предметных областей» описана общая структура разработанной компьютерной ДСМ-системы; рассмотрено внутреннее представление данных в программе, включая классы, которые используются для анализа данных разных ПО (фармакологии, медицинской диагностики и социологии); описана общая структура ДСМ-Решателя, представлены различные процедуры ДСМ-рассуждений и описана их программная реализация.

Структуру созданной ДСМ-системы можно представить в виде трех блоков, которые соответствуют трем компонентам ИС:

Графический интерфейс пользователя

Представление данных ДСМ-Решатель

ДСМ-Решатель для анализа данных различных ПО был создан на языке программирования С++ с использованием библиотеки классов MFC (Microsoft Foundation Classes) и библиотеки стандартных шаблонов STL (Standard

Template Library), а также интерфейса для доступа и манипулирования внешними данными ADO и языка запросов SQL.

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

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

«Графический интерфейс пользователя» предоставляет пользователю системы возможности настройки параметров и проведения экспериментов.

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

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

Здесь -► представляет отношение «родительский - производный

классы», О - отношение «содержит».

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

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

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

медицинских данных с помощью неатомарного ДСМ-метода используется класс оЬуес1Мес1_попА1огшс.

Факт медицинских данных - это пациент, которому сопоставлен набор признаков. Каждый признак имеет свой тип.

Рисунок 1- Иерархия классов внутреннего представления данных

Как следует из представленного рисунка, этот класс основан на атомарном классе оЬуес1Мес1_а1огтс. В его состав входят два объекта класса оЬцеЛМеё аЮгшс: один для представления правой части факта (изучаемого эффекта в языке ДСМ-метода), другой - левой (объекта).

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

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

23

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

objectX_unary_compound - класс, который представляет собой левую или правую часть факта (описание объекта или его свойств, соответственно) и содержит динамический массив элементов класса objectX. При заполнении данных в качестве элемента класса objectX создается объект класса objectSocio. Таким образом, представление объекта становится легко конфигурируемым: мы можем с легкостью выбирать, какую из компонент необходимо определить в правую или левую часть и добавлять новые компоненты. objectX_binary_compound - класс, который используется для применения неатомарного ДСМ-метода. В качестве членов класса он включает два объекта типа objectX_unary_compound. Для атомарного ДСМ-метода класс objectX_unary_compound можно использовать в качестве класса, который описывает факт.

Модуль «ДСМ-Решатель» реализует различные версии ДСМ-метода: атомарную/неатомарную, прямую/обратную версии; ситуационное расширение (среди параметров выделяют признаки, описывающие ситуацию) ДСМ-метода АПГ. «ДСМ-Решатель» включает базовый класс algorithmJSM (содержит общие настройки и необходим для унифицированной работы с разными версиями ДСМ-метода), algorithmJSM_atomicDirect (содержит процедуры атомарного прямого ДСМ-метода), aIgorithmJSM_nonAtomicDirect (включает процедуры неатомарного прямого ДСМ-метода), aIgorithmJSM_reverse (содержит процедуры обратного ДСМ-метода). Вспомогательными классами для реализации всех необходимых процедур ДСМ-рассуждений являются: hypothesis (класс, представляющий гипотезу), truncResid (класс, который реализует усеченный метод остатков), filter (класс, который содержит информацию о фильтрах, применяемых в эксперименте), ContradictionCalculation_Algorithm (алгоритм вычисления (не)противоречивости

массивов гипотез), а^огкИп^НуроЛезеБВизЬ (алгоритм для восстановления данных о «дереве» гипотез). При реализации процедур ДСМ-метода используется класс, представляющий абстрактный объект (класс о!уес1Х). Благодаря такому представлению данных ситуационная версия автоматически поддерживается и для прямого, и для обратного ДСМ-метода. Заметим, что алгоритмическая и программная реализации ситуационной версии ДСМ-метода АПГ осуществлены в диссертации впервые.

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

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

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

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

Во второй главе «Визуальное представление данных» детально описана структура обрабатываемых системой файлов, в которых представлена информация о фармакологических, медицинских и социологических данных. Файлы на вход системы поступают в формате Microsoft Office Excel (фармакология, медицина, социология) или в Microsoft Office Access (медицина). При обработке медицинских данных в формате Microsoft Office Excel также необходим файл формата .txt, в котором заполнена информация о признаках, по которым описаны пациенты. Порожденные гипотезы записываются в файлы MS Excel (фармакология, медицина), или MS Access (медицина), или .txt (социология). Параметры выбранной стратегии и результаты доопределения (т)-примеров сохраняются в файлах MS Excel (фармакология, медицина, социология) или MS Access (медицина). Также представлен интерфейс просмотра результатов для медицинских данных, разработанный в MS Access. Описана схема базы данных для считывания данных о признаках и пациентах и записи полученных результатов работы ДСМ-Решателя.

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

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

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

при применении метода соединенного сходства-различия были получены (+)-гипотезы на фармакологических данных;

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

с помощью усеченного метода остатков была подтверждена важная причинно-следственная связь на данных больных меланомой между протеином S100 и продолжительностью жизни больного: при значении уровня S100 меньше 0,12 нг/мл продолжительность жизни больного - больше 5 лет, при значении уровня S100 больше 0,12 нг/мл - меньше 5 лет. Впервые эта связь была обнаружена Добрыниным Д.А. и Панкратовой Е.С. в результате компьютерных экспериментов с использованием ДСМ-системы, созданной в ВИНИТИ РАН [б];

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

• Впервые создан ДСМ-Решатель, который не только реализует Этап I ДСМ-расуждений для различных версий ДСМ-метода АПГ (прямой/обратный ДСМ-метод, ситуационное расширение ДСМ-метода) и базовые методы индуктивного вывода (метод простого сходства, метод поиска единственности причины/следствия, запрет на контрпримеры), но и методы Д.С. Милля, отсутствующие в других системах: метод различия, метод сходства-различия, метод остатков, и, кроме того, процедуру абдукции. ДСМ-Решатель содержит и вспомогательные процедуры. Для автоматического отбора гипотез с требуемой структурой вводятся конъюнктивные и дизъюнктивные фильтры. Для более глубокого анализа достоверности выбранной стратегии и порожденных гипотез реализованы процедура «доопределение по одному» и процедура вычисления непротиворечивости массивов гипотез. Для удобной визуализации гипотез, необходимой для работы эксперта, создана процедура построения дерева гипотез.

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

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

29

наличие корреляции между уровнем белка Б100 и продолжительностью жизни больных меланомой. • Гибкость архитектуры системы позволила создать спецификацию универсальной ДСМ-системы - независимую ИС-ДСМ для качественного анализа социологических данных ^М-Босю, которая на текущий момент используется в Институте социологии РАН. ЛБМ-Босю имеет комплексное представление данных (разбиение признаков на описание субъекта, мнение, ситуацию и эффекты), развитый Решатель задач, способный анализировать такие данные с помощью впервые реализованных методов индуктивного вывода (методов различия, сходства-различия и метода остатков), и удобный предметно-ориентированный интерфейс пользователя. Таким образом, ^М-Босю является эффективной интеллектуальной системой типа ДСМ и полезным практическим инструментом социолога-эксперта. Программа получила свидетельство о государственной регистрации в Реестре программ для ЭВМ (№ 2013614978, от 24 мая 2013 года).

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

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

1) Волкова А.Ю. Алгоритмизация процедур ДСМ-метода автоматического порождения гипотез // Научно-техническая информация. Сер. 2.-2011 -№ 5 - С. 6-12; Volkova A. Yu. Algorithmization of Procedures of the JSM Method for Automatic Hypothesis Generation II Automatic Documentation and Mathematical Linguistics, 2011, Vol. 45, No. 3, pp. 113-120.

2)Волкова А.Ю. Анализ данных различных предметных областей с помощью процедур ДСМ-метода автоматического порождения гипотез // Научно-техническая информация. Сер. 2. - 2011. - № 6. - С. 9-18; Volkova A. Yu. Analyzing the Data of Different Subject Fields Using the Procedures of the JSM Method for Automatic Hypothesis Generation // Automatic Documentation and Mathematical Linguistics. - 2011. - Vol. 45. - No. 3. - pp. 127-139.

3) Волкова А.Ю., Шестерникова О.П. О создании интеллектуальных систем, реализующих ДСМ-метод автоматического порождения гипотез, и результатах их применения для анализа медицинских данных // Научно-техническая информация. Сер. 2. -2012. -№ 5. - С. 10-15.

А)Михеенкова М.А., Волкова А.Ю. Спецификация интеллектуальной системы типа ДСМ // Научно-техническая информация. Сер. 2. - 2013. -№ 7. - С. 5-19; Mikheenkova М.А., Volkova A. Yu. Specification of the JSM Intelligent System // Automatic Documentation and Mathematical Linguistics. - 2013. - Vol. 47. - No. 4. - pp. 135-150.

5) Волкова А.Ю. Опыт создания интеллектуальной ДСМ-системы для исследования данных различных предметных областей // Научно-техническая информация. Сер. 2. -2013. -№ 11,— С. 12-26.

Список использованной литературы:

1. Финн В.К. Индуктивные методы Д.С. Милля в системах искусственного интеллекта // Часть I. Искусственный интеллект и принятие решений. -2010. - № 3. - С. 3 - 21. Часть II. Искусственный интеллект и принятие решений.- 2010.-№ 4.-С. 14-40.

2. Финн В.К. Эпистемологические основания ДСМ-метода автоматического порождения гипотез. Часть I // Научно-техническая информация. Сер. 2. -2013. -№ 9. - С.1-29.

3. Климова С.Г., Михеенкова М.А. Формальные средства ситуационного анализа: опыт применения И Научно-техническая информация. Сер. 2. -2012.-№ 10.-С.1-13.

4. Климова С.Г., Михеенкова М.А., Финн В.К. Возможности применения ДСМ-метода для анализа данных о социальной ситуации на предприятии // Социология и общество: глобальные вызовы и региональное развитие [Электронный ресурс]: Материалы IV Очередного Всероссийского социологического конгресса, Уфа, 20 - 23 октября, 2012. - С.4557-4565.

5. Кученкова A.B. Логико-комбинаторные методы анализа социологических данных: эвристический потенциал и методическая специфика: Автореферат диссертации на соискание ученой степени кандидата социологических наук по специальности 22.00.01 - теория, методология и история социологии / Минобрнауки России, Федер. гос. бюджет, образоват. учреждение высш. проф. образования "Рос. гос. гуманитарный ун-т"; науч. рук. Г. Г. Татарова. - М., 2012. - 25 с.

6. Михайлова И. Н., Панкратова Е.С., Добрынин Д.А., Самойленко И.В., Решетникова В.В., Шелепова В.М., Демидов JJ.B., Барышников А.Ю., Финн В.К. О применении интеллектуальной компьютерной системы для анализа клинических данных больных меланомой. // Российский Биотерапевтический Журнал. - 2010. - № 2. - С.54.

Подписано в печать 12.05.2014. Формат 60x84/16. Бумага офсетная. Усл. печ. л. 1,25. Тираж 100 экз. Заказ № 1487.

Издательский центр Российского гуманитарного университета. Отпечатано в Печатно-множительной лаборатории РГГУ. 125993, ГСП-3, Москва, Миусская площадь, д. 6

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования «Российский государственный гуманитарный университет»

(РГГУ)

Отделение интеллектуальных систем в гуманитарной сфере Кафедра математики, логики и интеллектуальных систем в гуманитарной сфере

042014589о1 Яа правах рукописи

Волкова Анна Юрьевна

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

ПОРОЖДЕНИЯ ГИПОТЕЗ

05.13.17-Теоретические основы информатики

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

Научный руководитель: д.т.н., профессор В.К. Финн

Москва - 2014

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.............................................................................................................................5

1 ДСМ-РЕШАТЕЛЬ ДЛЯ АНАЛИЗА ДАННЫХ РАЗЛИЧНЫХ ПРЕДМЕТНЫХ ОБЛАСТЕЙ...........................................................................................................................22

1.1 Внутреннее представление данных........................................................................23

1.2 ОБЩАЯ СТРУКТУРА ДСМ-РЕШАТЕЛЯ И РЕАЛИЗАЦИЯ СТРАТЕГИЙ ДСМ-МЕТОДА АПГ..........................................................................................................28

1.2.1 Общая структура ДСМ-Решателя..................................................................28

1.2.2 ДСМ-РАССУЖДЕНИЯ...................................................................................31

1.2.2.1 ИНДУКТИВНЫЙ ВЫВОД ДСМ-РАССУЖДЕНИЙ...............................32

1.2.2.1.1 Базовые методы ДСМ-рассуждений.....................................................33

1.2.2.1.1.1 Простой метод сходства..................................................................34

1.2.2.1.1.2 Единственность причины (следствия).............................................49

1.2.2.1.1.3 Запрет на контрпримеры...................................................................51

1.2.2.1.2.1 Метод различия: миллевский вариант.............................................53

1.2.2.1.2.2 Метод различия: упрощение метода сходства - различия............58

1.2.2.1.2 Метод соединенного сходства - различия.............................................60

1.2.2.1.2.1 Метод соединенного сходства-различия с единственной причиной ...............................................................................................................................62

1.2.2.1.2.2 Общий метод соединенного сходства-различия............................65

1.2.1.1.3 Метод остатков.........................................................................................72

1.2.1.1.3.1 Общий метод остатков......................................................................72

1.2.2.1.3.2 Усеченный метод остатков...............................................................77

1.2.2.2 ПРАВИЛА ПРАВДОПОДОБНОГО ВЫВОДА ПО АНАЛОГИИ.............79

1.2.2.3 АБДУКЦИЯ И СТЕПЕНЬ АБДУКТИВ1ЮСТИ.......................................82

1.2.3 ВСПОМОГАТЕЛЬНЫЕ ПРОЦЕДУРЫ..............................................................86

1.2.3.1 Фильтры...........................................................................................................86

1.2.3.2 Доопределение по одному.............................................................................89

1.2.3.3 «Дерево» гипотез............................................................................................90

1.2.3.4 Проверка непротиворечивости гипотез........................................................93

2 ВИЗУАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ДАННЫХ.........................................................99

2.1 Представление данных в фармакологии...................................................................101

2.2 Представление данных в медицине...........................................................................105

2.2.1 Представление в Microsoft Office Excel.............................................................105

2.2.2 Представление в Microsoft Office Access..........................................................109

2.3 Представление данных в социологии.......................................................................120

3 ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ДСМ-РЕШАТЕЛЯ..............................................125

4 АНАЛИЗ ФАРМАКОЛОГИЧЕСКИХ И МЕДИЦИНСКИХ ДАННЫХ: ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА.......................................................................136

4.1 Стандартные стратегии ДСМ-метода АПГ............................................................151

4.1.1 Простой метод сходства..........................................................................................151

4.1.2 Единственность (+)-причины................................................................................154

4.1.3 Запрет на контрпримеры.......................................................................................155

4.2 Метод различия.........................................................................................................159

4.2.1 Метод различия: миллевский вариант.................................................................159

4.2.2 Метод различия: упрощение метода сходства - различия.................................162

4.3 Метод соединенного сходства - различия.............................................................170

4.4 Метод остатков..........................................................................................................175

4.4.1 Общий метод остатков............................................................................................175

4.4.2 Усеченный метод остатков.....................................................................................176

4.5 Проверка непротиворечивости гипотез..................................................................177

5 ДСМ-СИСТЕМА JSM-SOCIO ДЛЯ АНАЛИЗА СОЦИОЛОГИЧЕСКИХ ДАННЫХ.............................................................................................................................181

5.1 ДСМ-система JSM-Socio и современные программы для качественного анализа социологических данных.................................................................................................182

5.2 Описание возможностей ДСМ-системы JSM-Socio................................................191

5.3 Применение ДСМ-системы JSM-Socio на практике..............................................198

5.4 Средства предсказания изучаемых эффектов ДСМ-системы JSM-Socio..............201

ЗАКЛЮЧЕНИЕ..................................................................................................................206

Список литературы...........................................................................................................209

Список иллюстраций........................................................................................................215

Приложение А. Классы для реализации процедур и стратегий ДСМ-метода АПГ......219

Приложение Б. ДСМ-Решатель: Руководство пользователю..........................................241

Приложение В. Компьютерная интеллектуальная система JSM-Socio: Руководство пользователю........................................................................................................................250

ВВЕДЕНИЕ

Огромную роль в развитии направления исследовании «искусственным интеллект» играет интеллектуальный анализ данных (ИАД). В англоязычной литературе ему обычно соответствуют термины «data mining» и «knowledge discovery», однако, по-видимому, это верно лишь при широком толковании ИАД как извлечения нового полезного знания из неформализованных данных посредством различных формальных методов (статистические процедуры, нейронные сети, генетические алгоритмы, деревья решений и др.). Мы же под ИАД понимаем анализ данных посредством интеллектуальной системы (ИС) [1].

Структуру интеллектуальной системы можно представить в виде трех основных блоков. Информационная среда, Решатель задач и Интеллектуальный интерфейс [2]. Информационная среда состоит из базы фактов (БФ) и базы знаний (БЗ). БФ содержит множество фактов, которые являются результатами эмпирического исследования. БЗ включает аксиомы, характеризующие исследуемую предметную область, аксиомы структуры данных и процедуры, которые реализует Решатель задач.

Решатель задач в свою очередь состоит из трех модулей: Рассуждатель, Вычислитель и Синтезатор. Они осуществляют, соответственно, правдоподобные выводы, вычисления, необходимые для решения поставленной задачи, объединение рассуждений, вычислений и комбинаторных алгоритмов. Синтезатор также выбирает стратегии решения задач [3].

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

Интеллектуальные системы типа ДСМ (ДСМ-системы) являются примером ИС, которые реализуют когнитивные правдоподобные эмпирические (КПЭ) рассуждения типа «индукция + аналогия + абдукция» (с возможным применением дедукции). Как рассмотрено в [1], КПЭ-рассуждения можно эффективно использовать для имитации познавательных способностей естественного интеллекта, а именно - цикла «анализ данных - порождение гипотез (предсказание) - объяснение» [3].

ДСМ-рассуждения формализуются средствами бескоиечнозначной логики предикатов с кванторами по кортежам переменной длины [5] и реализуются в ИС с использованием машинного (индуктивного) обучения для knowledge discovery в базах фактов [3].

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

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

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

(б) База фактов содержит описание предметной области и «..образована фактоподобными высказываниями вида «объект С имеет множество свойств А», которым приписаны оценки «фактически истинно» (1), «фактически ложно» (-1), «фактически противоречиво» (0), «неопределенно» (т)» [7, С.400]. Множество свойств А называют эффектом. Положительные примеры (с типом истинностного значения, равным 1) обладают исследуемым эффектом, отрицательные примеры (с типом истинностного значения, равным -1) - не обладают. Неопределенные примеры (с типом истинностного значения, равным т) - это примеры, требующие доопределения.

(в) В БФ неявно должны содержаться зависимости причинно-следственного типа: (±)-причины исследуемых эффектов.

ДСМ-метод АПГ отвечает принципам компьютерного интеллектуального анализа данных (knowledge discovery), а именно [6]:

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

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

3. ДСМ-метод включает несколько этапов фальсификации, встроенные в процедуры индукции и аналогии.

4. ДСМ-рассуждение завершается применением абдукции - процедуры объяснения исходного множества фактов и принятия на этом основании порождённых гипотез.

5. Знания в базах знаний (БЗ) представлены в виде квазиаксиоматических теорий (КАТ), которые содержат формализованное представление множества аксиом (частично характеризующих предметную область), расширяемые БФ и множество гипотез, а также множество правил вывода.

6. ДСМ-метод АГТГ фактически реализует схему роста знаний эволюционной эпистемологии K.P. Поппера [8, С. 164-165].

Таким образом, ДСМ-метод АПГ является формализованной эвристикой, которая позволяет создавать компьютерные системы, решающие определенный круг задач для различных предметных областей. ДСМ-системы успешно применялись к таким предметным областям, как фармакология, медицинская и техническая диагностика, социология, криминалистика, робототехника [5, 7, 9, 10, 11, 12]. Перечень основных публикаций можно найти в [12].

Эффективность ИС-ДСМ зависит как от возможностей Решателя, так и представления данных в БФ и знаний в БЗ. Созданные ранее ДСМ-системы обычно применялись для решения практических задач одной предметной области и имели Решатель, реализующий базовые методы ДСМ-рассуждений: простой метод сходства и его усиления - запрет на контрпримеры.

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

медицинской диагностики и социологии. Архитектура системы позволила применить к ним один и тот же Решатель, что делает систему «универсальной» относительно рассматриваемых БФ и БЗ.

В Решателе впервые было реализовано четыре индуктивных метода Д.С. Милля [13]. Созданные методы были протестированы на данных фармакологии и медицинской диагностики. Проведенные эксперименты показали интересные результаты и позволили сравнить различные стратегии между собой. В процессе работы с социологическими данными были реализованы процедуры обратного ДСМ-метода и предусмотрена поддержка ситуационного расширения ДСМ-рассуждений.

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

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

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

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

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

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

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

• реализованы различные версии ДСМ-метода АПГ (прямой [13] /обратный [14] ДСМ-метод, ситуационное расширение [15] ДСМ-метода);

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

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

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

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

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

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

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

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

Основные научные результаты, полученные в ходе исследования:

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