ПРИМЕНЕНИЕ МЕТОДОВ ДИСКРЕТНОЙ МАТЕМАТИКИ ОТЫСКАНИЯ МИНИМАЛЬНЫХ ТЕСТОВ В МЕДИЦИНЕ

Введение:

В медицинской практике для правильной постановки диагноза болезни приходится рассматривать ряд симптомов, проводить исследования: ЭКГ, ФГС, анализы крови, и пр. Всё время встаёт практический вопрос: как поставить правильный диагноз и наметить путь лечения, используя наименьшее количество всевозможных анализов, процедур и пр., для ускорения и удешевления процесса лечения больного.

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

Математическая модель:

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

Булевой функцией называется функция , каждая переменной которой может принимать лишь значения из множества {0;1}, и сама функция   может принимать лишь значения из множества {0;1}. Булевы функции можно задавать с помощью таблиц.

 Дизъюнкцией  называется булева функция, которая обозначается как , и которая задаётся таблицей:

Таблица 1.

Таблица истинности для дизъюнкции

Конъюнкцией  называется булева функция, которая обозначается как  или , и которая задаётся таблицей: 

Таблица 2.

Таблица истинности для конъюнкции

Для конъюнкции и дизъюнкции справедливы следующие формулы:

Таблица 3.

Формулы для конъюнкции и дизъюнкции

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

Таблица 4.

Таблица истинности одного из законов поглощения

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

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

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

Пусть дан класс  попарно различных векторов.

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

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

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

Опишем алгоритм построения минимального теста:

1. Выпишем все векторы класса в таблицу, пронумеровав координаты:

Таблица 5.

Векторы класса 

В данной таблице символ   обозначает значение -й  координаты  вектора с номером .

2. Для каждой пары различных векторов запишем символическую дизъюнкцию, составленную из номеров координат, на которых эти векторы различаются.
3. Составим из всех полученных символических дизъюнкций КНФ.
4. Преобразуем символическую КНФ в ДНФ с помощью различных законов, описанных ранее. Тогда каждой символической конъюнкции будет соответствовать тест, а символической конъюнкции минимальной длины – минимальный тест.

Постановка задачи

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

Построение и исследование модели.

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

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

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

Реальный пример:

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

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

Рассмотрим несколько болезней с их симптомами:

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

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

Экзема: интенсивный зуд, волдыри, шелушение, повышение температуры, сыпь,

Туберкулёз: общая слабость, повышение температуры, интенсивный зуд, сыпь.

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

Введём обозначение симптомов: 1- красные пятна; 2- интенсивный зуд; 3- отечность; 4- общая слабость; 5- повышение температуры; 6- болевой синдром; 7- волдыри; 8- шелушение; 9- сыпь.

Построим таблицу:

Таблица 6.

Таблица заболеваний и симптомов

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

Таблица 7.

Таблица классов заболеваний и симптомов

Отличия классов ,  и  друг от друга по симптомам:        

Составим КНФ:

Упростим выражение, преобразовав КНФ в ДНФ, используя соответствующие формулы и законы, справедливые для конъюнкции и дизъюнкции:=   

В качестве минимального теста достаточно проверить наличие двух симптомов в любой из пар (1 и 4, или, 1 и 5, или 1 и 7 и т.д. согласно полученному выражению, где «» - дизъюнкция, а «» - конъюнкция). Данный метод значительно ускоряет процедуру постановки диагноза.

Программа:

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

Рисунок 1. Интерфейс программы

Соответствующими кнопками можно добавить новое заболевание (появится новое окно, рисунок 2). Или удалить выделенное в левом окне заболевние.

Рисунок 2. Добавление заболевания

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

Рисунок 3. Добавление заболевания

С помощью кнопок «Сохранить в файл» и «Загрузить из файла» можно сохранить текущий набор заболеваний и симптомов в файл расширения *.csv или загрузить сохраненный ранее список заболеваний из файла соответственно.

Кнопка «Тест» запускает непосредственно саму программу на текущем наборе. Результаты выводятся в нижнее текстовое поле в двух форматах:

1. Выводится предложение, в котором указываются варианты наборов симптомов, которые необходимо проверить, чтобы отличить заболевания друг от друга.
2. Выводится символическое выражение, где символ «V» - дизъюнкция, «*» - конъюнкция, а числами обозначены номера симптомов (номера указываются в окне добавления заболеваний (рисунок 2)). 

Работа программы основана на преобразовании КНФ в ДНФ с использованием формул поглощения, дистрибутивных и ассоциативных законов. Программа реализована с помощью списков и ООП на языке программирования C#.

Вывод:

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

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

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

1. Тишин В.В. Дискретная математика в примерах и задачах: электрон. учеб. пособие– Самарский государственный аэрокосмический университет им. С. П. Королева (национальный исследовательский университет), 2007.