Аннотация: Деревья принятия решений являются гибким инструментом для решения задач диагностики. Целью данной статьи является разработка алгоритма для построения диагностического дерева.
Ключевые слова: дерево принятие решений, диагностическое дерево, критерий прироста информации, критерий Gini, критерий GainRatio, энтропия.
Технические науки
УДК 004(075.32)
Стрюков Руслан Константинович
аспирант
Воронежский Государственный Университет
Stryukov R. K.
postgraduate
Voronezh State University
РАЗРАБОТКА ДИАГНОСТИЧЕСКОГО ДЕРЕВА НА ОСНОВЕ КРИТЕРИЯ ПРИРОСТА ИНФОРМАЦИИ
DEVELOPMENT OF A DIAGNOSTIC TREE BASED ON INFORMATION GAIN CRITERION
Аннотация: Деревья принятия решений являются гибким инструментом для решения задач диагностики. Целью данной статьи является разработка алгоритма для построения диагностического дерева.
Ключевые слова: дерево принятие решений, диагностическое дерево, критерий прироста информации, критерий Gini, критерий GainRatio, энтропия.
Summary: Decision Trees are a flexible tool for solving diagnostic tasks. The purpose of this article is to develop a diagnostic algorithm for constructing the tree.
Keywords: decision tree, diagnostic tree information gain criterion, the Gini criterion ratio GainRatio criterion, entropy.
Введение
Под медицинской диагностикой будем понимать процесс установления диагноза, то есть заключения о сущности болезни и состоянии пациента, выраженное в принятой медицинской терминологии [1].
В качестве метода диагностики будем рассматривать дерево принятия решений или диагностическое дерево[2].
Разрабатываемый алгоритм будет решать основную проблему построения дерева: какие атрибуты необходимо выбирать для того, чтобы построенное дерево было наиболее оптимальным.
Алгоритм построения диагностического дерева
Предположим, что показатели характеризуют состояние пациента в группе заболеваний .
Для каждого показателя определена шкала в виде конечного множества возможных значений. Мощность данной шкалы обозначим , .
Под экземпляром будем понимать вектор i-ая компонента, которого соответствует показателю . Экземпляр – вектор возможных значений показателя, характеризующий состояние пациента.
Множество, состоящее из экземпляров, каждый из которых относится к некоторому заболеванию (классу), назовем обучающим множеством LearnSet.
Алгоритм построения диагностического дерева.
S1. Зафиксировать класс и отобрать экземпляры из LS, относящиеся к данному классу .
S2. Последовательно рассмотрим показатели по каждому определить частоту появления значений из шкалы .
Пусть – одно из значений, которое встречается раз, тогда
Где – количество экземпляров в данном классе .
S3. Определить количество характеристик показателей для фиксированного класса по каждому показателю [3].
Определить энтропию по формуле
S4. Процедура выбора.
Сформировать множество потенциальных корней , включив в него показатели, выбранные на основе следующих критериев [4]:
1)Выбрать те вершины, для которых энтропия минимальна;
2)Выбираются те вершину, у которых критерий прироста информации максимален
Где – множество элементов из А, на которых признак P имеет значение S.
3)Критерий GainRatio
где
Выбираются вершины для которых GainRatio максимальный.
4)Критерий Гини
Тогда в качестве вершины выбирается та, у которой критерий Gini максимальный.
S5. Повторяя шаги S1-S4, строится граф в виде разложения по уровням, причем каждому уровню соответствует показатель , всего уровней . Уровни располагаются в соответствии с ранжированием показателей.
Из каждой вершины – показателя , выходит столько дуг, сколько возможных значений содержит шкала .
Каждой дуге – значению приписывается относительная частота появления этого значения в редуцированных экземплярах обучающего множества.
Под редуцированным экземпляром обучающего множества подразумевается экземпляр, в котором оставлены компоненты, соответствующие пути из корня в данную вершину диагностического дерева.
В результате выполнения данного шага будет построено взвешенное ориентированное дерево в виде иерархии. На нижнем уровне располагаются вершины, которые соответствуют классам заболеваний .
Пример построения диагностического дерева
Пусть имеются следующие симптомы со значениями:
Головокружение: есть\нет;
Среднее содержание гемоглобина в эритроците: Сниженный (С), Нормальный (Н), Повышенный (П);
Средний диаметр эритроцитов: Сниженный (С), Нормальный (Н), Повышенный (П);
Диагнозы: Железодефицитная анемия (ЖА), Гемолитическая анемия (ГА), В12 дефицитная анемия (В12).
Имеющиеся данные представлены в таблице 1.
Таблица 1 – Исходное обучающее множество
|
Головокружение |
Среднее содержание гемоглобина в эритроците |
Средний диаметр эритроцитов |
Диагноз |
|
Есть |
П |
П |
ГА |
|
Нет |
П |
П |
В12 |
|
Нет |
Н |
Н |
ГА |
|
Нет |
С |
С |
ЖА |
|
Есть |
П |
Н |
ГА |
|
Есть |
С |
С |
ЖА |
|
Есть |
Н |
П |
ГА |
|
Есть |
П |
С |
ЖА |
Рассчитаем прирост информации
Согласно вычислениям в качестве корня дерева необходимо выбрать атрибут с максимальным приростом информации – средний диаметр эритроцитов[5]
Поделим обучающее множество на подмножества
Таблица 2 – Обучающее множество после редуцирования (СДЭ = С)
|
Головокружение |
Среднее содержание гемоглобина в эритроците |
Средний диаметр эритроцитов |
Диагноз |
|
Нет |
С |
С |
ЖА |
|
Есть |
С |
С |
ЖА |
|
Есть |
П |
С |
ЖА |
Таблица 3 – Обучающее множество после редуцирования (СДЭ = Н)
|
Головокружение |
Среднее содержание гемоглобина в эритроците |
Средний диаметр эритроцитов |
Диагноз |
|
Нет |
Н |
Н |
ГА |
|
Есть |
П |
Н |
ГА |
Как видно из таблиц 2 и 3 установка диагноза тривиальна, рассмотрим случай представленный в таблице 4.
Таблица 4 – Обучающее множество после редуцирования (СДЭ = П)
|
Головокружение |
Среднее содержание гемоглобина в эритроците |
Средний диаметр эритроцитов |
Диагноз |
|
Есть |
П |
П |
ГА |
|
Нет |
П |
П |
В12 |
|
Есть |
Н |
П |
ГА |
Рассчитаем прирост информации.
Следующим критерием в случае с повышенным диаметром эритроцитов является – головокружение.
В результате получим следующие подмножества
Таблица 5 – Обучающее множество после редуцирования (СДЭ = П и Г=есть)
|
Головокружение |
Среднее содержание гемоглобина в эритроците |
Средний диаметр эритроцитов |
Диагноз |
|
Есть |
П |
П |
ГА |
|
Есть |
Н |
П |
ГА |
Таблица 6 – Обучающее множество после редуцирования (СДЭ = П и Г=нет)
|
Головокружение |
Среднее содержание гемоглобина в эритроците |
Средний диаметр эритроцитов |
Диагноз |
|
Нет |
П |
П |
В12 |
Полученные случаи в таблицах 5 и 6 являются тривиальными. Построим диагностическое дерево.
Рисунок 1 – Пример диагностического дерева
Заключение
На основе разработанного алгоритма было построено диагностическое дерево, которое может быть использовано для:
- построения продукционных правил диагностики заболеваний;
- позволяет объяснить, как именно был поставлен конкретный диагноз.
Литература:
1. Диагностика [электронный ресурс] URL:https://ru.wikipedia.org/wiki/Диагностика
2. Леветин, А.В. Алгоритмы: введение в разработку и анализ.: Пер. с англ. – С.Г. Тригуб, И.В. Красикова. – Издательский дом «Вильямс», 2006. – 576 с.
3. Шеннон, К. Работы по теории информации и кибернетике.: Пер. с англ. – Р.Л. Добродушина, О.Б. Лупанова. – Москва: Издательство иностранной литературы, 1963. – 823 с.
4. Николенко, С. Деревья принятия решений [Электронный ресурс] // Персональный сайт Сергея Николенко. 2006. URL: http://logic.pdmi.ras.ru/~sergey/teaching/ml/notes-01-dectrees.pdf (дата обращения: 27.04.2015).
5. Паклин, Н.Б. Бизнес-аналитика: от данных к знаниям: учебное пособие. 2-е изд./ Н.Б. Паклин – СПб: Питер, 2013. – 444-459 с.
