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

Размещено на http://www.allbest.ru/

МЕТОД ПЕРЕБОРА КОНЪЮНКЦИЙ В ПРОБЛЕМЕ СТРУКТУРНОГО АНАЛИЗА МНОГОМЕРНЫХ ДАННЫХ (НА ПРИМЕРЕ РЕШЕНИЯ МЕДИЦИНСКИХ ЗАДАЧ)

В.П. Карп

Аннотация

Рассматривается метод перебора конъюнкций (МПК) в проблеме анализа структуры данных. Формулируется постановка задачи выявления логических связей в заданных группах объектов на заданном множестве признаков. Описан алгоритм (ALOST), реализующий решение задачи. Приведены результаты использования алгоритма на реальных медицинских данных.

Введение

В настоящее время в арсенале методов анализа данных широко используются различные программные продукты: статистические пакеты, нейросети, так называемые эволюционные методы, алгоритмы поиска логических закономерностей и др. [Дюк, 2001]. Такие компьютерные разработки представляют собой «инструмент» для анализа данных. Основная их задача - обеспечить корректность анализа, учитывая особенности медицинских данных (многообразие проявления заболевания, наличие большого количества пропущенных данных, их зашумленность и т.д.).

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

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

1. Преамбула

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

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

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

После введения критерия «хорошего исхода» группы больных разделяются на тех, для которых метод T1 хорош (Т1⁺), и на тех, для которых он плох (Т1^-); и аналогично метод лечения T2 - для некоторых больных хорош (Т2⁺), а для некоторых - плох (Т2^-). На рис.1 представлена схема возможного распределения состава групп больных и их количеств в группах, получивших сравниваемые методы лечения.

Рис. 1 Распределение объектов по группам сравнения

D - объединенный состав больных {DТ1 ? DТ2}, т.е. получивших один из методов лечения (Т1 или Т2) и имеющих либо хороший исход (DТ1⁺ или DТ2⁺), либо плохой (DТ1^- или DТ2^-);

DТ1 - состав больных, получивших Т1;

DТ2 - состав больных, получивших Т2;

DТ1⁺ - состав больных из группы Т1, имеющих «хороший исход»;

DТ1^- - состав больных из группы Т1, имеющих «плохой исход»;

DТ2⁺ - состав больных, из группы Т2, имеющих «хороший исход»;

DТ2^- - состав больных из группы Т2, имеющих «плохой исход»;

N - общее количество больных, участвующих в исследовании,

т.е., N = NТ1 + NТ2;

NТ1 - количество больных, получивших метод лечения Т1;

NТ2 - количество больных, получивших метод лечения Т2;

NТ1⁺ - количество больных в группе DТ1⁺ ;

NТ1^- - количество больных в группе DТ1^-;

NТ2⁺ - количество больных в группе DТ2⁺ ;

NТ2^- - количество больных в группе DТ1^-.

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

Важно выяснить также существуют ли закономерности, общие для хорошего (или плохого) исходов и при T1, и при T2. В этом случае, обнаруженные закономерности могут определить хороший и плохой прогноз вне зависимости от выбранного метода лечения. Выделение таких групп очень важная задача, так как очевидно, что оценивать эффективность применения какого-либо метода лечения (или препарата) в группе с плохим прогнозом нельзя по тем же критериям, что и в группе с хорошим прогнозом. Так, в рассматриваемом примере представляет интерес рассмотреть и сопоставить связи признаков (симптомов) в следующих парах групп: (DТ1⁺ ? DТ2⁺) и (DТ1^- ? DТ2^-); (DТ1⁺) и (DТ1^- ); (DТ2⁺) и (DТ2^-); а также (DТ1) и (DТ2).

Если обнаружатся сочетания симптомов, характерные для больных с плохим исходом (DТ1^- ? DТ2^-), отличные от группы с хорошим исходом (DТ1⁺ ? DТ2⁺), то тем самым, могут определиться факторы плохого прогноза, вне зависимости от предлагаемых методов лечения. Если удастся выявить закономерности, различающие гр. (DТ1⁺) и гр. (DТ1^-), то можно будет сформулировать показания и противопоказания к применению метода T1. Аналогично, при сравнении гр. (DТ2⁺) и гр. (DТ2^-), выявленные устойчивые связи симптомов позволят ориентироваться в показаниях и противопоказаниях к использованию метода T2. Сопоставление частоты (или доли) выявленных сочетаний симптомов в группах (DТ1) или (DТ2), позволят сделать суждение о распространенности обнаруженных связей, иными словами, о границах их применимости.

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

Рассматриваемый пример является типичным в круге задач, стоящих перед врачом-исследователем, особенно в проблеме выбора наиболее эффективной тактики лечения конкретного больного. Следует заметить, что аналогичные задачи в практике проведения предварительных исследований возникают достаточно часто и в других областях [например, Губерман, 1987].

2. Алгоритм структурного анализа данных

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

2.1 Метод перебора конъюнкций в структурном анализе данных

конъюнкция перебор алгоритм структурный

Естественно было предположить, что искомые связи (закономерности) в группах следует искать в виде различных логических функций симптомов исходного описания, и в первую очередь, в виде конъюнкций этих симптомов. Такой подход, предложенный в 1964 г. Бонгардом М.М. [Бонгард, 1967], получил название «метод перебора конъюнкций» (МПК). В публикациях [Карп, 2005, Чернавский и др., 2004] подробно описаны процедуры перебора конъюнкций и принципы их отбора в решающие правила диагностики. МПК хорошо зарекомендовал себя в построении различных диагностических алгоритмов (и в медицинских, и в не медицинских задачах). Основные преимущества МПК состоят в том, что при его использовании отпадает необходимость задания всех координат объектов, что позволяет использовать объекты с неполной информацией; обнаруженные закономерности сформированы в виде конъюнкций (из симптомов, предложенных самим врачом-исследователем), которые легко интерпретируются, что существенно при содержательном анализе выявленных закономерностей.

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

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

2.2 Задание групп объектов

В ALOST каждая группа может быть задана либо перечислением объектов, либо логическим условием, которому должны удовлетворять все входящие в нее объекты. В общем случае, группа задается именем и «маской». Маска группы - логическая функция компонент. Компоненты задаются: перечислением номеров объектов или симптомов; интервалом номеров объектов или симптомов. Каждой группе присваиваются «имена», отражающие, по возможности, их смысловое содержание. Если какая-либо группа (Gi) уже сформирована, то предусмотрен также вариант задать новую группу, например (Gj), так: «все, которые не вошли в данную группу (Gi)» или «все, которые попали одновременно и в группу с именем Gj, и в группу с именем Gk», и т.д.

2.3 Задание симптомов для перебора

Все симптомы исходного описания перенумерованы от 1 до Y. В таблице 1 приведен фрагмент описания больных острым инфарктом миокарда (ОИМ) для решения задачи сравнительной оценки эффективности применения различных лекарственных средств (Т1 и Т2) к этой категории больных.

Табл. 1

Фрагмент карты описания больных острым инфарктом миокарда

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

Табл. 2

Задания для перебора имеют вид

где aij компонента -- либо симптом, либо дизъюнкция отдельных симптомов, либо объединение интервалов симптомов, т.е. Si Si+k; n-глубина перебора.

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

2.4 Реализация перебора

Схема, по которой происходит перебор конъюнкций для каждого задания, представлена в таблице 3.

Табл. 3

Схема реализации перебора

Так, например, для 1-го задания перебор будет осуществлен сначала для единичного компонента (a11); и если суммарное число больных, имеющих этот компонент, будет превышать заданный порог Ed (параметр алгоритма), то будет произведен перебор для следующего уровня, т.е., для конъюнкции двух компонент (a11 a12). Затем, при тех же условиях, перебор либо будет продолжен и выполнен в полном объеме (a11 a12 a13... a1n), либо завершится на каком-либо промежуточном этапе. Результат будет представлен для каждого уровня перебора.

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

2.5 Выходная информация

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

Таблица 4

Распределение количества объектов по группам с заданным сочетанием симптомов

3. Анализ результатов исследования

Из таблицы следует: в приведенном примере материал исследования составил 125 больных ОИМ (приняты за 100%). Исследованию на эффективность подлежали два препарата (Т1 и Т2), которые назначались больным на фоне стандартной базовой терапии. Требовалось оценить эффективность двух вариантов комплексного лечения: «Т1+базовая терапия» (Т1) и «Т2+базовая терапия» (Т2) больных с различными проявлениями (симптомами) заболевания. Количество больных, получивших Т1, оказалось 54, что составило 43% от общего числа, а получивших Т2 - 71 больной (57%). Прогноз «хорошего исхода» на всей группе исследования составил 96 больных из 125, т.е., 77%, а прогноз «плохого исхода», соответственно, - 29 человек из 125 (23%). Из общего числа больных с «хорошим» исходом, оказалось 42 человека (34%), получивших Т1, и 54 человека, т.е., 43 %, получивших Т2.

Анализируя полученные результаты, можно сделать, например, следующие выводы.

1. Метод лечения T1 предпочтительней чем Т2, если в момент инфаркта у больного была экстрасистолия (1-е задание). Такое заключение можно сделать из того наблюдения, что прогноз «хорошего» исхода у больных с наличием экстрасистолии в момент инфаркта составил 50%. Однако, в группе больных, получивших лечение Т1, «хороший исход» составил 39% (7 человек из 18 в группе DТ1⁺) по сравнению с 11% (2 человека из 18 в группе DТ2⁺), получивших лечение T2.

2. Лечение T1 значительно предпочтительнее T2 для мужчин, имевших какие-либо нарушения сердечного ритма при крупноочаговом инфаркте (3-е задание). Это следует из того, что положительный прогноз для таких больных составил 42%, при этом, доля больных с «хорошим» исходом в группе Т1 составила ~34% (4 человека) в отличие от 8% (1 человек), если применяли T2. Правда, этот результат получен на столь малой выборке, что требует дополнительного материала для анализа.

3. С другой стороны, метод лечения T2 показан, если у больных случился мелкоочаговый инфаркт и в анамнезе отмечена гипертония (2-е задание). Таких больных оказалось 19 человек, что составило 15% группы исследования. Прогноз «хорошего исхода» для этой категории больных составил 79% (15 больных из 19), а в группах сравнения - 26% (5 больных из 19 в группе «DT1⁺») и 53% (10 больных из 19 в группе «DT2⁺»).

4. Аналогичный вывод можно сделать при наличии недостаточности кровообращения (4-е задание). Прогноз «хорошего исхода» составил 63% (12 человек из 19), при этом, в группе DТ2⁺ - 58% (11 человек из 19), а в группе DТ1⁺ - 5% (1 человек из 19).

Заключение

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

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

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

Метод МПК продемонстрировал свою эффективность в решении многих исследовательских и прикладных задач медицины.

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

1. Бонгард М.М. Проблемы узнавания. М.: Наука, 1967.

2. Губерман Ш.А. Неформальный анализ данных в геологии и геофизике. М., Недра, 1987.

3. Дюк В., Самойленко А. Data Mining. СПб: Питер, 2001.

4. Карп В.П. Метод направленного обучения в системах поддержки врачебных решений // Новости Искусственного интеллекта. 2005. № 2.

5. Чернавский Д.С. и др. Распознавание. Аутодиагностика. Мышление. Синергетика и наука о человеке. М.: ИПРЖР, 2004.

Размещено на Allbest.ru