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

.. . . л

РОССЙИСКАЯ АКАДЕМИЯ НАУК ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

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

Сапир Марина Валентиновна

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

Специальность 05.13.11 - математическое и программное ооеспечение вычислительных машин, комплексов и систем

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

МОСКВА - 1994

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

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

Кузнецов О.П. Официальные оппоненты: - доктор технических наук, .

профессор Поспелов Д.А. - доктор технических наук Бауман Е.В.

Ведущая организация: ВИНИТИ (г. Москва)

Зашита диссертации состоится "_"_• 1994 г.

в _ часов.на заседании Специализированного совета

Института проблем управления по адресу: 117806 Москва ул. Профсоюзная 65.

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

Автореферат разослан _"__ 199 г.

Ученый секретарь Специализированного совета

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

Актуальность проблемы.

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

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

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

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

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

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

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

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

Реализация результатов работы. Созданный пакет программ внедрён в Медицинском научном центре г. Екатеринбурга, в Свердловском областном медицинском информационно вычислительном центре, в Ереванском медицинском информационно - вычислительном центре, в Екатеринбургском филиале МНТК "Хирургия глаза".

Апробация результатов работы. Основные результаты докладывались на семинарах в Институте проблем управления, ВИНИТИ, Институте математики и механики УрОАН, Московской городской конференции Комплексного совета по проблеме "Кибернетика",• на Всесоюзной научно-технической конференции "Вопросы разработки и внедрения радиоэлектронных средств при диагностике сердечно-сосудистых заболеваний" (Свердловск, I984) на Научно - практической конференции "Математические методы в медицине и биологии" (Свердловск, 1984), на общеинститутской конференции "Применение математических методов в медицине" Медицинского научного центра (1993, Екатеринбург).

Публикации. Непосредственно по теме диссертации опубликовано 8 научных работ, в том числе 5 статей.

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

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

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

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

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

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

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

ц: г* -» к, ц(А.) - монотонна: А э В => \1(А) >

Требуется найти вен млнимчльнче по вложению г.эдмножества описательных признаков Ь, );,ля которых значение меры ■ связи выше заданного порога г:

Ъ а X: [1(1.) > г & (ЧМ М с I уцМ) < г) Требование монотонности меры связи не является слишком

сильным ограничением, .оно просто означает; что—связь— некоторого множества признаков с целевым признаком не может уменьшиться, если к этому множеству добавляется новый признак. Монотонными мерами связи являются, например, критерий Пирсона %2, энтропийная мера. В диссертации введены две удобные, легко интерпретируемы«) монототонше мера связи для дискретных признаков.

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

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

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

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

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

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

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

Алгоритм Бета перебирает подмножества в

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

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

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

получения любого заданного числа решений алгоритмом—Альфа— полиномиально зависит от числа признаков.

Чем меньше признаков входит в решение, тем оно обычно более ценно, так как простые объяснения всегда предпочтительней длинных: их проще интерпретировать и использовать на практ$Ге. В обычной ситуации, когда решений много, имеет смысл искать только достаточно короткие решения или самые короткие. Предложена модификация алгоритма Бета,-которая позволяет получать решения, ограниченные по длине, быстрее, чем все решения. Другая модификация того же алгоритма позволяет получать только вс«5 самые короткие решения, и сложность этого алгоритма также меньше, чем слокность исходного не только в худшем случае, но и в обычных, типичных ситуациях, когда много решений.

Третья глава диссертации посвящена методу максимальных информативных гиперинтервалов, который предназначен для построения оптимальных гипотез о связи целевого признака с набором произвольных описательных признаков. Гиперинтервал (ГИ) определяется как область $ в признаковом пространстве, ограниченная неравенствами по каждой переменной отдельно: VI 3 о{ 3 £>{ <хг,...,хп> € ¡8 « а{ < т{ ^ Ь{. ГИ называется информативным, если по обучающей выборке процент точек преобладающего класса в нём выше некоторого заданнсо порога; и ког^честьо точек в нём больше некоторого наперёд заданного числь. Ставится задача нахождения максимальных по вложению информативных ГИ.

Каждый найденный ГИ рассматривается как 'гипотезе о взаимосвязи признаков, характеризувдих объекты, с целевым признаком. Благодаря простоте вида зависимостей, они могут

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

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

Исследована сложность предложенного алгоритма и предложена модификация его, которая позволяет ускорить работу за оч«т большего объёма используемой памяти.

Исследована проблем?) устойчивости найденных ГИ. Предлагается 2 подхода к 01> нке устойчивости: по контрольной выборке и по размытому ГИ. Ь перром" случае ГК считается устойчи;.!(М, если процент точе: греоаьид&эдего класса в т-„-м же ГЛ на контрольной выборке больше заданного. Во втором случае строиУ'.':) ГИ, который по указанным пользователем осям

минимально шире данного, и вычисляется—процент—тшек____ преобладающего класса в этом ГИ. ГИ считается устойчивым, если процент точек преобладающего класса в размытом ГИ выше заданного порога.

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

Пользователю предоставляется возможность предварительно отобрать содержательно • наиболее-ценные из найденных ГИ-для построения правила распознавания.

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

Исследовано понятие детерминированной устойчивости метода распознавания образов, предложенное A.C. Нудельманом. Показаны некоторые особенности этого понятия, которые

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

В четвертой главе диссертации описан метод оптимальной дихотомии для выявления информативных интервалов значений. Предполагается, что целевой признак - качественный, делит все объекты на классы, тогда как описательные признаки - ранговые или количественные. Ставится задача статистически оценить и описать связь каждого из этих признаков с"целевым. Для этого рассматриваются все разбиения области значений описательного признака каким-нибудь одним его значением, и для каждого разбиения вычисляются встречаемость Р}, Р?', ?2, отпадения точек-выделенного класса и всех остальных классов в каждой из получившихся областей отдельно. Находятся все разбиения области значений описательного признака, где различие между пропорциями + ?,)> Р^/(Р'г + Р0)

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

о

V-

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

V

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

р

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

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

Пятая глава диссертации содержит описание накетч программ комплексного анализа данных "Ешр1г1с'*.

Все. предложенные методы и многие другие вошли ь разработанный автором и описанный б диссертации- пг- ут анализа данных "3«?ИиС". Кроме описанных методов в пакет ьходят Сол (-сой блок программ управления данными, блок программ традиционой статистики. В блок программ управления данный? кр т программы для разнообразного ввода данных, для корректировки данных, входит программа формирования новых признаков. Пользователь имеет возможность, задав -формулу, в

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

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

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

Кроме традиционой параметрической статистики (вычисление параметров распределения, сравнение средних между примаками и между классами, вычисление корреляционной матрицы), блок статистики содержит программу для вычисления множественных условных частот, которая может рассматриваться как развитие метода дэтерминационного анализа C.B. т1есн<>кова. В этой программе не только вычисляются условные и безусловные множественные частоты, что позволяет подробно изучать взаимоствязи между группами качественных признаков, • их сочетаниями значений, но и значение критерия %г, характеризующее связь ме:«:ду каждой парой сочетаний значений двух исследуемых групп шознакиь, а также урогонъ вероятности, с которой мокне принять гипотезу о том, что данные сочетания взаимосвязаны по критерию \г. Кроме того

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

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

В блок анализа вошли программы разработанных диссертантом методов построения эмпирических гипотез.

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

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

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

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

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

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

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

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

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

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

Z. На основе этих требований были сформулирочны три подхода к оптимальному автоматическому построению гипотез.

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

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

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

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

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

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

9. С помощью разработанного пакета программ были решены р.~.'< задач из области медицины, социологии, гигиены.

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

Г. Саяир М.В» Анализ структуры связей эмпирических дяншх // Нчучно-т^хничеокал информация. Счрия 2. Т955. ЯЗ. 0.22 -27. . 2. Санир М.В. Зкстрсмальные задачи на конечных множествах с монотонней мерой // Автоматика и телемеханика. ТЯЗ™. дб. С.149 - 155.

Я. Сапип "И.п. Алгоритм; ¡¡опека зкетр>малышх подмножеств для монотонной связи /У Автоматикя и тнмл'-мех^кикч. 1988. Ж. С.773 -

4 «.В. Сягшр. Система диалоговой ' обработки медако биологической информации. // Боег.г.»зная научно - техническая конференция "Вопросы разработки и внедрения радиоэлекторонных средств при диагностике сердечно - сосудистых заболеваний". М.: Радио и связь. 19Я4. С. 45.

5. М.В. Сапир. Зохмалиаация задач о связях признаков. /.' Научно- практическая конференция "Математические методы в медицин',* и биологии". Свердловск. 1984.

5.с Сапир М.В. 06 устойчивости алгоритмов распознавания образов. // Вычислительные системы. 1993. Вып. 146.

7. Сагшр М.В. Построение оптимальных алгоритмов для задач выбора. // Вычислительные системы. 1993. Вып. 146.

8. Венедиктов Д.И:, Сяпир М.В. Последствия односторонней оьариозктомии у женщин репродуктивного возраста. // Акуззерстьо и гинекология. 1991. >*4. С.57 - 59.

В последней работ* диссертант гтедложиля метод оптимальной дихотомии, сготсаншЯ п диссертанта.