Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных
Разработан аппарат генетического программирования для прогнозирования СВСГД. Предложен метод получения продукционных правил для прогнозирования высокой степени риска СВСГД в условиях неопределенности некоторых параметров. Проведены исследования и приведены результаты использования методов на реал...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/7674 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных / Т.А. Васяева, Ю.А. Скобцов // Штучний інтелект. — 2008. — № 4. — С. 631-637. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-7674 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-76742010-04-07T12:01:01Z Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных Васяева, Т.А. Скобцов, Ю.А. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Разработан аппарат генетического программирования для прогнозирования СВСГД. Предложен метод получения продукционных правил для прогнозирования высокой степени риска СВСГД в условиях неопределенности некоторых параметров. Проведены исследования и приведены результаты использования методов на реальных медицинских данных. Розроблено апарат генетичного програмування для прогнозування СРСН. Запропоновано метод отримання продукційних правил для прогнозування високого ступеня ризику СРСН при деяких нез’ясованих параметрах. Виконано експерименти та наведено результати використання методу на реальних медичних даних. 2008 Article Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных / Т.А. Васяева, Ю.А. Скобцов // Штучний інтелект. — 2008. — № 4. — С. 631-637. — Бібліогр.: 3 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/7674 004.048:004.622 ru Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| spellingShingle |
Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Васяева, Т.А. Скобцов, Ю.А. Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| description |
Разработан аппарат генетического программирования для прогнозирования СВСГД. Предложен метод
получения продукционных правил для прогнозирования высокой степени риска СВСГД в условиях
неопределенности некоторых параметров. Проведены исследования и приведены результаты использования
методов на реальных медицинских данных. |
| format |
Article |
| author |
Васяева, Т.А. Скобцов, Ю.А. |
| author_facet |
Васяева, Т.А. Скобцов, Ю.А. |
| author_sort |
Васяева, Т.А. |
| title |
Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| title_short |
Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| title_full |
Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| title_fullStr |
Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| title_full_unstemmed |
Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| title_sort |
эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2008 |
| topic_facet |
Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/7674 |
| citation_txt |
Эволюционный подход к формированию знаний для медицинских экспертных систем с учетом неопределенности данных / Т.А. Васяева, Ю.А. Скобцов // Штучний інтелект. — 2008. — № 4. — С. 631-637. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT vasâevata évolûcionnyjpodhodkformirovaniûznanijdlâmedicinskihékspertnyhsistemsučetomneopredelennostidannyh AT skobcovûa évolûcionnyjpodhodkformirovaniûznanijdlâmedicinskihékspertnyhsistemsučetomneopredelennostidannyh |
| first_indexed |
2025-07-02T10:27:55Z |
| last_indexed |
2025-07-02T10:27:55Z |
| _version_ |
1836530612412874752 |
| fulltext |
«Штучний інтелект» 4’2008 631
8В
УДК 004.048:004.622
Т.А. Васяева, Ю.А. Скобцов
Донецкий национальный технический университет, г. Донецк, Украина
vasyaeva_tanya@tr.dn.ua, skobtsov@kita.dgtu.donetsk.ua,
Эволюционный подход к формированию
знаний для медицинских экспертных систем
с учетом неопределенности данных
Разработан аппарат генетического программирования для прогнозирования СВСГД. Предложен метод
получения продукционных правил для прогнозирования высокой степени риска СВСГД в условиях
неопределенности некоторых параметров. Проведены исследования и приведены результаты использования
методов на реальных медицинских данных.
Формирование базы знаний является одной из наиболее трудоемких задач при
разработке экспертных систем (ЭС). Один из подходов формирования знаний заклю-
чается в разработке программ, способных обучаться под руководством эксперта-учителя.
При этом учитель предъявляет программе примеры реализации некоторого концепта,
а задача программы состоит в том, чтобы извлечь из предъявленных примеров
набор атрибутов и значений, определяющих этот концепт. Данная работа является
развитием [1], где для извлечения знаний в виде системы продукций используется
аппарат генетического программирования. В отличие от предыдущих работ, где
фактически используется двоичная логика, в настоящей работе применяется троичная
логика, которая позволяет учитывать неопределенность (или отсутствие) значений
некоторых параметров как на этапе обучения, так и в процессе эксплуатации ЭС.
Неопределенность данных
При работе с медицинскими данными, достаточно часто возникает ситуация, когда
некоторые параметры неизвестны. Это затрудняет как и обучение системы, так и ее
тестирование, а также использование. При формировании обучающих данных исполь-
зуются данные, предоставленные медицинскими работниками. Как правило, эти данные
собираются по карточкам пациентов, которые находились на лечении несколько лет
назад. Поэтому при отсутствии некоторой информации практически невозможно ее
восстановить. Классические автоматизированные методы формирования знаний на базе
машинного обучения (machine learning) работают, если известны все выделенные
факторы риска для каждого пациента. Поэтому, если какой-нибудь параметр неизвестен
только у одного пациента, необходимо либо удалить пациента из обучающей выборки,
либо удалить данный параметр из списка факторов риска. Так как в большинстве случаев
у разных пациентов отсутствуют данные о различных факторах риска, формирование
обучающей выборки в этом случае выполняется с существенной потерей данных.
После разработки системы список входных параметров, как правило, уже
определен и для корректной работы системы все информативные составляющие
должны быть заполнены. При тестировании отсутствие информации сказывается на
достоверности результата или невозможности диагностирования в целом.
Васяева Т.А., Скобцов Ю.А.
«Искусственный интеллект» 4’2008 632
8В
Целью проектируемой системы в данной статье является получение продук-
ционных правил для диагностирования заболевания в условиях неопределенности
некоторых входных данных (на примере определения высокой степени риска
синдрома внезапной смерти грудных детей – (СВСГД) – одного из малоизученных и
загадочных заболеваний).
В данной задаче в качестве обучающего множества используются реальные
данные обследования 240 пациентов (120 детей, которые умерли в Донецкой области от
СВСГД, и контрольная группа из 120 живых детей на первом году жизни). Данные
составляют информацию общего характера и образа жизни беременных, а также
перенесенные заболевания и результаты некоторых анализов.
Генетическое программирование
Для решения поставленной задачи предложено использовать генетическое
программирование (ГП) [2]. Решение задачи на основе ГП можно представить
следующей последовательностью действий.
1. Установка параметров эволюции;
2. Инициализация начальной популяции;
3. T:=0;
4. Оценка особей, входящих в популяцию;
5. T:=Т+1;
6. Отбор родителей;
7. Создание потомков выбранных пар родителей – выполнение оператора
кроссинговера;
8. Мутация новых особей;
9. Расширение популяции новыми порожденными особями;
10. Сокращение расширенной популяции до исходного размера;
11. Если критерий остановки алгоритма выполнен, то выбор лучшей особи в
конечной популяции – результат работы алгоритма. Иначе переход на шаг 4.
Предлагается следующий метод кодирования особей для генетического програм-
мирования. Каждая особь представляет собой дерево, которое соответствует синтакси-
ческому выражению, представляющее множество правил в дизъюнктивной нормальной
форме.
На рис. 1 представлен пример дерева в дизъюнктивной нормальной форме.
Дерево представлено 3-мя правилами. Такое представление особи значительно упро-
щает интерпретацию результата. В данном примере расшифровка будет следующей:
ЕСЛИ правило 1 ИЛИ правило 2 ИЛИ правило 3, ТО результат 1, ИНАЧЕ
результат 2.
Популяция особей (потенциальных решений) состоит из набора деревьев, сгенери-
рованных случайным образом. Генерация каждого дерева, как описано ниже, происходит
рекурсивно, начиная с первого функционального узла ИЛИ и его аргументов.
По построенному специальным образом дереву можно получить систему продукций,
которая классифицирует с заданной точностью данные обучающей выборки.
Входное обучающее множество должно быть представлено в виде булевых
переменных. Для этого исходные данные были преобразованы следующим образом:
место жительства (город – 1, село – 0);
возраст матери на момент родов (полных лет) <17;
возраст матери на момент родов (полных лет) <25;
Эволюционный подход к формированию знаний...
«Штучний інтелект» 4’2008 633
8В
возраст матери на момент родов (полных лет) <30;
возраст матери на момент родов (полных лет) >31;
место работы матери, профвредность (да – 0 , нет – 1);
и др.
Терминальное множество состоит из факторов риска, которые после предобра-
ботки представляют собой булевые переменные и соответствуют листьям дерева.
Функциональное множество состоит из логических операций: AND, OR, NOT, которые
представляют внутренние вершины дерева.
В качестве фитнесс-функции рассматривается: доля пациентов с правильно
поставленным диагнозом. Переменная диагноза принимает булевые значения 0 или 1.
Единица соответствует положительному диагнозу (высокой степени риска СВСГД) и
ноль отрицательному (низкой степени риска СВСГД). Значение фитнесс-функции для
особей с правильным диагнозом принимает значение 1, а для особей с неправильным
диагнозом принимает значение 0.
Рисунок 1 – Пример дерева в дизъюнктивной нормальной форме
С целью минимизации потери данных при обучении и расширения возмож-
ностей диагностирования при неизвестных значениях некоторых факторов риска
предлагается использовать троичную логику. При этом переменные могут прини-
мать три логические значения {0,1,*}, где ‘*’ представляет неопределенное значение
(это 0 или 1, но неизвестно, что именно). Подобный подход применяется во многих
отраслях науки и техники, например, при проектировании цифровых систем с исполь-
зованием логического моделирования в троичной (или многозначной) логике [3].
Ni
ИЛИ
И
Ni
Ni
И
Ni
Ni
И
И
ИЛИ
НЕ
НЕ Ni
И
Ni
И
Ni
Ni
И
НЕ
НЕ НЕ
Ni
Правило 1 Правило
N
…
Васяева Т.А., Скобцов Ю.А.
«Искусственный интеллект» 4’2008 634
8В
В табл. 1 – 3 приведены таблицы истинности для следующих логических функций:
И, ИЛИ и НЕ.
Таблица 1
Таблица 2
Таблица 3
Применение системы, которая оперирует с неизвестными состояниями, позволит
выполнять диагностику даже при отсутствии некоторых параметров, что не приведет к
невозможности функционирования разработанной системы. На этапе обучения такой
подход позволит сформировать оптимально полный набор входных параметров и не
упустить важные, информативные параметры.
Генерация начальной популяции
На данном этапе происходит генерация начальной популяции, в соответствии с
заданными параметрами. Популяция состоит из набора деревьев, сгенерированных
случайным образом. Генерация каждого дерева происходит рекурсивно, начиная с
генерации первым функционального узла ИЛИ и его аргументов. В качестве аргументов
на первом шаге может быть только узел ИЛИ. Далее для каждого дочернего узла случай-
ным образом определяется тип и значения его аргументов по следующим принципам:
после узла ИЛИ может быть только функциональный узел (значениями которого
могут быть – ИЛИ или И);
после узла И может быть функциональный узел (значениями которого могут быть –
И или НЕ) или терминальные узлы;
после узла НЕ может быть только терминальный узел.
N1 N2 И
0 0 0
0 1 0
1 0 0
1 1 1
* 0 0
* 1 *
* * *
N1 N2 ИЛИ
0 0 0
0 1 1
1 0 1
1 1 1
* 0 *
* 1 1
* * *
N1 НЕ
0 1
1 0
* *
Эволюционный подход к формированию знаний...
«Штучний інтелект» 4’2008 635
8В
Процесс выполняется по левой ветви до тех пор, пока не будет выбран
дочерним терминальный узел. Затем генерируются правые ветви.
Вероятность функционального и терминального узлов меняется по следующему
принципу: чем ниже вершина, тем больше вероятность терминального узла и меньше
функционального. Для функционального узла на каждом последующем шаге увеличи-
вается вероятность узла И и уменьшается вероятность узла ИЛИ.
При формировании дерева в одной ветви ИЛИ (т.е. для одного правила) не
используется один и тот же терминальный символ более одного раза.
Предусмотрены методы создания деревьев: полный, растущий и комбинированный.
Отбор родителей. Предложено использовать отбор пропорционально значению
целевой функции, реализованный методом рулетки или турниром. При этом если два
или более потомка имеют одинаковую фитнесс-функцию, то выбирается дерево мини-
мальной сложности.
Кроссинговер
Для древообразной формы представления используются следующие три основ-
ных оператора кроссинговера:
узловой кроссинговер;
кроссинговер поддеревьев;
смешанный.
Учитывая строго определенное представление дерева необходимо модифици-
ровать операторы кроссинговера.
В узловом операторе кроссинговера обмен возможен только для терминальных
узлов.
В кроссинговере поддеревьев родители могут обмениваться только поддеревья-
ми ветви И.
При смешанном операторе кроссинговера для некоторых узлов выполняется
узловой оператор кроссинговера, а для других – кроссинговер поддеревьев.
Также предлагается выполнять оператор кроссинговера для худшего правила в
дереве. Правило считается худшим, у которого целевая функция имеет минимальное
значение. Каждое правило можно рассматривать как отдельное дерево, способное
решать поставленную задачу, поэтому вычисление фитнесс-функции для каждого
правила в отдельности логически обосновано.
Вычисление фитнесс-функции не только для каждого правила в отдельности,
но и каждого узла И также имеет смысл. При выполнении оператора кроссинговера
поддеревьев предлагается осуществлять поиск точки разрыва следующим образом:
вычисляется фитнесс-функция для каждого узла И начиная с первого снизу. Если
значение фитнесс-функции для узла И, находящегося выше, хуже, чем на предыду-
щем шаге, то обмену подлежит один из узлов аргументов данного узла И.
Мутация
Для деревьев используются следующие операторы мутации:
узловая;
усекающая;
растущая.
Как и в случае с оператором кроссинговера оператор мутации должен быть
модифицирован.
Васяева Т.А., Скобцов Ю.А.
«Искусственный интеллект» 4’2008 636
8В
Узловая мутация выполняется для терминального узла или первой снизу
вершины ИЛИ.
Усекающая мутация выполняется только для узлов И или НЕ.
При растущей мутация ветви наращиваются согласно правилам инициализации
деревьев.
Сокращение дерева
Предлагается использовать оператор сокращения дерева. Как и оператор кроссинго-
вера или мутации, данный оператор выполняется с определенной вероятностью. Если
количество правил в дереве превышает определенный порог, то обрезается целое
правило. Если количество правил не превышает указанное число, то обрезается худшая
часть дерева в худшем правиле, т.е. выполняется усекающая мутация.
Редукция
Предлагается использовать выполнения следующих вариантов редукции:
элитная стратегия;
чистая замена;
равномерная случайная замена (с указанием количества заменяемых особей в %).
При тестировании на реальных медицинских данных получили следующие
результаты. На рис. 2 представлены результаты экспериментов: зависимость правильной
классификации от количества неизвестных состояний на входах в %. На рис. 3 представ-
лены результаты экспериментов: зависимость нераспознанных диагнозов от количества
неизвестных состояний на входах в %.
Рисунок 2 – Зависимость правильной классификации от количества неизвестных
состояний на входах в %
Ошибка обучения
0,84
0,86
0,88
0,9
0,92
0,94
0,96
0,98
1
3 6 9 12 15 18 21 24 27 30
ош на обуч выб
ош на пров выб
Эволюционный подход к формированию знаний...
«Штучний інтелект» 4’2008 637
8В
% неопределенных диагнозов
Рисунок 3 – Зависимость нераспознанных диагнозов от количества неизвестных
состояний на входах в %
Выводы
Таким образом, получил дальнейшее развитие метод прогнозирования на основе
генетического программирования, что позволило получить продукционные правила для
прогнозирования высокой степени риска СВСГД в условиях неопределенности неко-
торых параметров. Предложенный метод протестирован на примере прогнозирования
СВСГД, но может быть использован и при решении других задач медицинской
диагностики и прогнозирования.
Литература
1. Васяева Т.А., Скобцов Ю.А. Разработка экспертных систем медицинской диагностики с явным
представлением продукционных правил на основе ГП // Тези міжнародної наукової конференції
«Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту (ISDMCI’2008)». –
Т. 3, Ч. 1. – Херсон: ХНТУ, 2008. – 192 с.
2. Скобцов Ю.А. Основы эволюционных вычислений: Навчальний посібник. – Донецьк: ДонНТУ,
2008. – 326 с.
3. Скобцов Ю.А., Скобцов В.Ю. Логическое моделирование и тестирование цифровых устройств. –
Донецк: ИПММ НАНУ, ДонНТУ, 2005. – 436 с.
Т.О. Васяєва, Ю.О. Скобцов
Еволюційний підхід до формування знань для медичних експертних систем з урахуванням
нез’ясованості даних
Розроблено апарат генетичного програмування для прогнозування СРСН. Запропоновано метод
отримання продукційних правил для прогнозування високого ступеня ризику СРСН при деяких
нез’ясованих параметрах. Виконано експерименти та наведено результати використання методу на
реальних медичних даних.
Статья поступила в редакцию 17.07.2008.
0
0,05
0,1
0,15
0,2
0,25
0,3
0,35
0,4
0,45
0,5
3 6 9 12 15 18 21 24 27 30
% * на обуч
% * на пров
|