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




Скачать 174.34 Kb.
НазваниеМетод перебора конъюнкций в проблеме структурного анализа многомерных данных
Дата публикации17.10.2013
Размер174.34 Kb.
ТипДокументы
skachate.ru > Информатика > Документы
УДК: 004.89:616

МЕТОД ПЕРЕБОРА КОНЪЮНКЦИЙ

В ПРОБЛЕМЕ СТРУКТУРНОГО АНАЛИЗА МНОГОМЕРНЫХ ДАННЫХ

(НА ПРИМЕРЕ РЕШЕНИЯ МЕДИЦИНСКИХ ЗАДАЧ)1

В.П. Карп 2

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

Введение

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

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

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

1. Преамбула

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

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

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

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

Объекты

исследования

D: {DТ1 Ụ DТ2}

(смешанные группы

больных, получив­шие

лечение Т1 или Т2)

Т1+ Т1+ Т2+ Т1- Т2- Т2+ Т1+ Т2+ Т1- Т2- Т1- Т2- Т2+ Т1+ Т2+ Т1- Т2- Т2- Т1- Т2- Т1- Т1- Т2- Т1- Т1- Т1- Т1- Т1+ Т2+

. . . . . . . . . . . ……….

Т2+ Т1+ Т2+ Т1- Т2+ Т2+ Т1+ Т2+ Т1- Т1

Состав групп

(после введения критерия фективности)

Т1

Т2

DТ1 = {DТ1+ Ụ DТ1- }

DТ2 = {DТ2+ Ụ DТ2- }

Кол-во объектов

N = NТ1 + NТ2

NТ1

NТ2

Кол-во и состав

Групп по эффект-ти

NТ1+

(DТ1+)

NТ1-

(DТ1-)

N Т2+

(DТ2+)

N Т2-

(DТ2-)

Рис. 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.

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

Признак

Симптом

(характеристика признака)

Номер

симптома

Пол

Мужской

1

Женский

2


Возраст (полных лет)

<= 40 лет

3

41-50 лет

4

51-60 лет

5

> 60 лет

6

. . .

. . .

. . .

Наличие экстрасистолии в момент инфаркта

Отсутствовала

26

Присутствовала

27

. . .

. . .

. . .

Были ли какие-либо

наруше­ния сердечного

ритма в момент ОИМ

Не было

30

Были

31

. . .

. . .

. . .

Характер ОИМ

Мелкоочаговый

46

Крупноочаговый

47

. . .

. . .

. . .

Заболевания в анамнезе

. . .

Гипертония

51

. . .

. . .

Недостаточность кровообращения

Имеется

63

. . .

. . .

Y

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

Табл. 2.

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

№ задания

Компо-нента 1

Компо-

нента 2

. . .

Компо-нента j

Компо-нента n

1-е задание

а11 

а12

. . .

a1j


a1n

2-е задание

а21 

а22 

. . .

a2j

a2n

i-е задание

ai1

ai2

. . .

aij


Ain

m-е задание

am1 

am2 

. . .

amj

amn,

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

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

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

Табл. 3.

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

Глубина перебора

1-й уровень

2-й уровень

. . .j-й. Уровень

n-й уровень

Конъюнкции

ai1

ai1 & ai2

ai1 & ai2. . . & aij

ai1 & ai2. . . & aij & ain

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

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

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

Таблица 4.

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

Название групп

Всего


DТ1

+

DТ2

+

DТ1



DТ2



DТ1 DТ2

+

DТ1

DТ2



DТ1

DТ2

Состав

групп

125

%

42

34

54

43

12

10

17

14

96

77

29

23

54

43

71

57

1-е задание: 27 (экстрасистолия в момент инфаркта)

В абс.

числах

18

7

2

3

6

9

9

10

8

В %

14

39

11

17

33

50

50

55

44

2 задание: 51  46 (гипертония в анамнезе и мелкоочаговый ОИМ)

В абс.

числах

19

5

10

3

1

15

4

8

11

В %

15

26

53

16

5

79

21

42

58

3-е задание: 1  31  47 (мужчина с нарушением сердечного ритма в

момент инфаркта, с крупноочаговым инфарктом)

В абс.

числах

12

4

1

1

6

5

7

5

7

В %

10

34

8

8

50

42

58

42

58

4-е задание: 63 (недостаточность кровообращения)

В абс.

числах

19

1

11

3

4

12

7

4

15

В %

15

5

58

16

21

63

37

21

79

^ 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.

1 Работа выполнена при финансовой поддержке РГНФ (№ 04-03-00069ф)

2) 119454, Москва, пр. Вернадского, 78, МИРЭА, karpvica@mail.ru






Похожие:

Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconАнализ данных науки, образования и инновационной деятельности с использованием...
В данной статье будет описан метод анализа паттернов и результаты его применения к поставленной проблеме анализа развития науки,...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconInformation technologies and systems 2013 (ITaS'13)
Совет молодых ученых и специалистов иппи ран совместно с Центром структурного анализа данных и оптимизации (страдо) и Лабораторией...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных icon: 001. 8 О представлении данных и знаний для интеллектуального анализа социологических данных
Предлагаемое представление позволяет реализовать интеллектуальный анализ социологических данных в интеллектуальных системах типа...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных icon«Моделирование территориальных систем»
Методы, используемые для анализа территориальной организации хозяйства: сравнительно-географический метод, статистический метод,...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconПриложение е (рекомендуемое) Выбор перебора грунта при моделировании проходки тпмк
При выборе значения перебора следует учитывать, что он существенно зависит от вида разрабатываемого грунта, технологии проходки (в...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconОпыт применения методов интеллектуального анализа данных в компаративистских...
В работе описываются предварительные результаты анализа данных из Базы данных “Языки мира” с применением методов DataMining и пакета...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconУстойчивый метод декомпозиции и фильтрование временных рядов
Стойкий сходящийся итерационный метод для выявления в данных компонентов imf, является более устойчивым и предсказуемым, чем эмпирический...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconКонтрольная работа Предмет, метод и содержание экономического анализа....
Структура и основные цели бизнес- плана и роль анализа в разработке бизнес-плана
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconРеализация прототипа системы мобильных агентов для решения задач...
Методы интеллектуального анализа данных (иад) сегодня широко применяются для решения актуальной задачи обнаружения в данных ранее...
Метод перебора конъюнкций в проблеме структурного анализа многомерных данных iconЛабораторная работа №2: «Решение задач корреляционного и регрессионного...
Цель работы: Познакомиться с проведением регрессионного и корреляционного анализа и использовании данных методов для обработки статистических...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница