автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Построение классификационных решающих правил на основе фактографических данных и экспертных знаний
Автореферат диссертации по теме "Построение классификационных решающих правил на основе фактографических данных и экспертных знаний"
ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА РОССИЙСКАЯ АКАДЕМИЯ НАУК
- О*-
лЛ на правах оукописк
УДК 519.81
БОЛОТОВ Александр Александрович
ПОСТРОЕНИЕ КЛАССИФИКАЦИОННЫХ РЕШАЮЩИХ ПРАВИЛ НА ОСНОВЕ ФАКТОГРАФИЧЕСКИХ ДАННЫХ И ЭКСПЕРТНЫХ ЗНАНИЙ
Специальность 05.13.10 - управление з социальных экономических системах {технические наукр-
Автореферат диссертации на соискание ученой стелет кандидата технических наук
Москва 1995
Работа выполнена в 32 Центральном Военно-морском
клиническом госпитале
Научный руководитель - член-корреспондент РАН, доктор
технических наук, профессор ' Ларичев 0.14.
Официальные оппоненты: - д.т.н., профессор
Емельянов Н. Е.
- к. т.н. А.Н. Путинцев
Ведущая организация - Институт проблем управления
(автоматики и телемеханики) РАН
Защита состоится &Я7 1995 г. в АО- час.
на заседании специализированного совета К 003.63.ul в Институте системного анализа РАН по адресу : Москва, 117312, Проспект 60-ти летия Октября, дом 9. С диссертацией можно ознакомиться в библиотеке ИСА РАН.
Автореферат разослан "_" __ 1995 г.
Ученый секретарь специализированного совета доктор физ.-мат. наук
Коростелев А.П.
, ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность Значительные усилия исследователей в области искусственного интеллекта в настоящее время сконцентрированы в направлении разработки методов решения задач с так называемой плохой структурой, представляющих значительные трудности при решении их человеком. Наиболее важной и часто рассматриваемой задачей такого рода является задача классификации. Анализ литературных данных показал, что существует широкий спектр методов и подходов к ее решению. Выделяются несколько направлений таких исследований: методы, характерные для подходов теории распознавания образов (ТРО), методы так называемого машинного обучения и подходы и методы, характерные для систем, основанных на знаниях.
Традиционно задача классификации рассматривалась з ТРО. Особенностью .подходов ТРО является наличие множества обучающих примеров (объектов с известной классификацией), на основе которых строится та или иная система формальных решающих правил. Достоинством таких подходов является то, что система таких"правил позволяет получить решение для любой комбинации признаков и поэтому может быть отнесена к полной системе решающих правил. Однако, в зависимости от объема обучающей выборки (ОВ), ее разнообразия меняется и система решающих правил.
Методы так называемого машинного обучения используют множество обучающих примеров для извлечения логических решающих правил. Однако, они не всегда гарантируют получение полных баз решающих правил, а также, как и для методов ТРО, система решающих правил зависит от параметров ОВ: ее объема, разнообразия и непротиворечивости данных.
В системах, основанных на знаниях (СОЗ) делается попытка моделирования содержательного процесса решения задачи, осуществляемого экспертом на основе личностных знаний. При этом они. как правило, не обеспечивают построения полных баз решающих правил. В этом направлении одной из"самых актуальных на данный момент является задача построения больших баз знаний, позволяющих наиболее точно имитировать суждения-эксперта.
Такая задача приводит к необходимости дополнительного изучения возможностей различных направлений исследований и наиболее полного использования всех имеющихся знаний при решении
сложных практических задач.
Целью работы является исследование возможностей объединения, методов теории распознавания образов и систем, основанных на знаниях для построения больших, полных и непротиворечивых баз решающих правил; разработка интеллектуальных компьютерных систем, предназначенных для решения задачи классификации и основанных на экспертных знаниях и верифицированных данных; разработка и исследование программно-алгоритмического обеспечения, сочетающего в себе эти возможности.
Для достижения цели данной работы необходимо решить ряд следующих вопросов:
1. Исследовать поведение распознающих алгоритмов (РА) в зависимости от объема обучающей выборки и сложности задачи, для чего необходимо разработать критерии и методику оценки качества работы различных систем; провести исследование этой методики для конкретных задач и известных РА; г
2. Разработать логико-теоретическую модель взаимодействия фактографических данных (примеров) и базы знаний (БЗ), позволяющую объединить подходы различных направлений при построений полных и непротиворечивых баз решающих правил;
-3. Разработать и исследовать новые алгоритмы и методы рационального опроса эксперта при построении больших баз знаний; :
4. Разработать программное обеспечение, позволяющее эффективно строить полные и непротиворечивые базы знаний большого объема с использованием. • фактографических данных и экспертных знаний. На его основе осуществить решение ряда сложных практических задач. ,
Научная новизна. Предложен новый критерий - точность аппроксимации разделяющих гиперплоскостей (ТАРГ) для сравнения качества функционирования РА. который позволяет получать надежные оценки в-полном пространстве признаков.
Разработана к исследована методика оценки качества функци-. онированйя распознающих алгоритмов, основанная на принципах статистического моделирования. Получены новые данные о качестве работы распознающих алгоритмов на базе линейного дискриминант-ного анализа и метода Байеса для задач различного размера, отличающихся сложностью границ между классами решений и объемом обучающей выборки.
Предложена логико-теоретическая модель взаимодействия базы
фактографических данных (БФД) и базы знаний в рамках подходов создания полных и непротиворечивых БЗ. Разработан и исследован подход к их объединению.
Предложена и исследована методика рационального опроса эксперта при построении экспертных решающих правил, использующую эвристику средних объектов, под которыми понимаются объекты, содержащие одну половину признаков наиболее характерных для одного класса решений, а другую половину - наиболее характерных для другого класса.
Для подтверждения этой эвристики для самой сложной границы при двух классах решений и N двоичных признаков доказано утверждение: ,
Классификация экспертом {2/Ш+2)}-г (2Л/(1?-4)} части средних объектов позволяет косвенно классифицировать все доминирующие их по характерности объекты.
Предложена и исследована методика выявления эвристических правил эксперта на его повторяющихся решениях.
.Методы исследований. Для решения перечисленных задач использовались методы математической статистики и теории вероятностей, теории распознавания образов, теории построения алгоритмов и систем..
Практическая ценность. Основной практический результат диссертационной работы заключается в следующем :
Разработанные методы построения классификационных решающих правил на основе фактографических данных и экспертных знаний могут быть использованы в таких областях как медицина, геология, техническая диагностика и др.
На основе предложенных методик и подходов разработано программное обеспечение, позволяющее создавать полные и непротиворечивые базы решающих правил. На его основе были созданы базы знаний для четырех задач медицинской диагностики.
Разработанный комплекс алгоритмов и программ позволяет создавать полные и непротиворечивые базы знаний достаточно большого объема (около 20000 возможных объектов) с высокой скоростью, а также проводить анализ БЗ, исследовать границы между классами решений и выявлять обобщенные решающие правила эксперта.
Предложенные способы проверки данных на непротиворечивость могут быть использованы для анализа ОБ в рамках ТРО и других
подходов, так или иначе базирующихся на ряде примеров при построении решающих правил.
Реализа^й рёзультатов работы. На основе проведенных исследований разработано и внедрено программно-алгоритмическое обеспечение для построения полных и непротиворечивых баз знаний для ПЭВМ типа IBM PC, состоя]дее__из трех модулей:
- основной системы;
- утилит;
- редактора базы знаний.
Общий объем программного обеспечения составляет приблизительно 20000 операторов языка "Си" и около 5000 операторов языка "Клиппер".
Завершенный программный продукт реализован и внедрен в 32 Центральном Военно-морском клиническом госпитале.
Апробация работы. Основные положения диссертации и материалы исследований докладывались и обсуждались на :
- XXXII научной конференции преподавателей и студентов МИФИ в 1987 г.;
- научно-практической конференции "Актуальные вопросы специализированной медицинской помощи" ЦВМУ и ЦВКГ им. Вишневского в 1988 г.; •..
- научно-практической конференции "Состояние и перспектива применения ЭВМ в лечебных учреждениях СА и ВМФ" ЦВМУ и ГВКГ им. Бурденко в 1988 г.;
- научно-практической конференции "Организация и пути совершенствования специализированной медицинской помощи на ВМФ" 32 ЦВМГ 20-21 декабря 1988 г.;
- научно-практической конференции "Итоги научно-практической работы ЦВМГ в 1989 г. " 32 ®f'l4 декабря 1989 г. :
- научно-практической конференции "Актуальные проблемы диагностики и лечения заболеваний на ВМФ" 32 ЦВМГ 13-14 декабря 1990 г.;
- юбилейной научно-практической конференции "Проблемы клинической и военно - морской медицины" 32 ЦВМГ 17-18 декабря 1993 г.;
- Всероссийской научной конференции "Кардиология: успехи, проблемы и задачи (актуальные вопросы ишемической болезни сердца и артериальных гипертензий)" 23-25 ноября 1993 г., Санкт-Петербург;
- научно-практической конференции "Актуальные проблемы военной и экстремальной медицины" НИИ Медицины Катастроф МО РФ, 23-24 мая 1994 г.
Публикации. По результатам диссертационной работы опубликовано 12 печатных работ.
Структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (116 наименований), одного приложения. Объем работы - 127 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении подчеркнута актуальность проблемы, обоснована _ постановка цели диссертационной работы и решаемых научных задач, изложены направления научных исследований, отраженных в глазах диссертации, приведены основные положения, выдвигаемые на защиту.
В первой главе рассматривается место и роль задачи классификации в. интеллектуальных компьютерных системах. Проведен обзор двух принципиально отличных подходов к задаче классификации: характерных для теории распознавания образов и систем, основанных на знаниях.
Проанализированы 4 научных направления, сложившиеся в ТРО: статистическое распознавание; структурная (лингвистическая) теория распознавания; алгебраическая теория распознавания; теоретико-игровая (стратегическая) теория распознавания. Рассмотрена специфика каждого из них.
В рамках СОЗ рассмотрена проблема приобретения знаний. Выделяются и анализируются 5 направлений исследований в рамках решения этой проблемы. Рассмотрен ряд важных характеристик процессов извлечения знаний: психологическая корректность; полнота и непротиворечивость.
Анализируются методы машинного обучения и методы извлечения экспертных знаний. Приведены общие проблемы, присущие методам машинного обучения. Рассмотрены системы выявления экспертных знаний: их подходы, достоинства и недостатки. Показана важность решения задачи создания полных и непротиворечивых баз ■ знаний большого объема для более точной имитации суждений эксперта.
При создании таких баз решающих правил является актуальным исследование вопросов объединения подходов из различных направ-
.пений и наиболее полного использования всех имеющихся "островков знаний".
Сформулирована цель диссертационного исследования, и определен круг вопросов, которые необходимо при этом решить.
Вторая глава посвящена исследованию поведения распознающих алгоритмов в зависимости от объема обучающей выборки, размерности задачи и сложности границы между классами решений. Данный вопрос приводит к необходимости разработки критериев оценки точности работы РА и методов их сравнения.
Рассматриваются те задачи распознавания образов, в которых объекты описываются совокупностью дискретных признаков и есть эксперт, дающий классификацию для подмножества объектов (выборки).
Предположим, что задача решена в том идеальном случае, когда задана вся совокупность объектов (выборка совпадает с совокупностью объектов), и эксперт безошибочно распределил их между классами решений. Тогда можно сказать, что имеются точные границы между классами решений в многомерном пространстве признаков, описывающих объекты.
Если задача классификации полностью решена, то границы построены. Возникает возможность использовать точность аппроксимации этих границ как тестовый пример для сравнения методов классификации. Такой критерий получил название - точность аппроксимации разделяющих гиперплоскостей (ТАРГ).
Приводится формальная постановка такой задачи.
Дано:
N - признаков, описывающих объекты;
И - число опенок на шкале 1-го признака;
ХК.1 - к.-я оценка по 5.-му признаку (1-1.....К;к=1.....Н1);
у - число объектов, входящих в выборку;
I - число классов, к которым должны быть отнесены объекты;
РЛ(X) - граница для ¿-го класса решений, ,]=!,..., и;
X (Х}.. Лы) ~ векторы оценок признаков, принадлежащие границе о-го класса;
М1, М2 - методы классификации, строящие разделяющие гиперплоскости на основе выборки из 0 объектов.
Требуется : сравнить методы М1 и М2 по точности аппроксимации истинной границы Гз(Х).
Однако, б общем случае для целей сравнения методов совсем
не обязательно восстанавливать истинные границы между классами. Такие границы могут быть заданы любым формальным способом.
В качестве сравниваемых методов Mi и М2 были выбраны классификатора на базе линейной дискриминантной функции (ЛДФК) и на формуле Байеса (БК).
В случае использования байесовского метода задача классификации сводится к статистической задаче выбора гипотез при заданной априорной информации о каждом классе и условных вероятностях каждой оценки всех признаков по всем классам. Решение выбирается по максимуму апостериорной вероятности среди возможных классов для конкретного набора признаков. Аналитически это выражается известной формулой Байеса:
P(Zj) PiS/Zj) (1) P(Zj/S)=—-
Т. P(Zj) P(s/zj) J
где P (Zj) - априорная вероятность j-го класса;
P(Zj/S) - апостериорная вероятность j-ro класса при наборе признаков S;
Р(S/Zj) - условная вероятность набора признаков S для j-ro класса. Будем полагать, что признаки независимы, тогда:
W W
Р (S/ZJ) = П Р(Si/Zj), где Р(Si/Zj) - условная
и вероятность w оценка
(градации) 1-го признака.
В качестве априорных вероятностей каждого класса использовались оценки частоты их встречаемости, при этом:
Р(Zj) =п• /£ nj где г- число объектов j-ro класса
среди всех возможных объектов.
В качестве условных вероятностей возможных оценок признаков использовались оценки:
W W W
Р(Si/Zj) = / r где г'.¿j - число объектов, имеющих
i-ый признак с w шкалой для J-ro класса в заданной обучающей выборке.
Линейный дискримикантный анализ позволяет построить разделяющую гиперплоскость когда заданы классы, признаки и имеется обучающая выборка. При этом граница между классами ищется з ви-
де : '
(2) Y =11 Ai Xi + С
l
где Ai - коэффициент при i-ом признаке;
Xi - значение (или градация) i-ro признака;
С - константа.
В качестве оптимальной выберем гиперплоскость, которая
максимизирует отношение U:
U = (межклассовая вариация)/(внутриклассовая вариация)
Межклассовая вариация определяется квадратами расстояний
(mv - mv ) и тем больше, чем дальше отстоят средние поедстави-ч h
тели (центры) ту. первого и второго классов. Внутриклассовая вариация определяется суммой квадратов расстояний от всех объектов обучающей выборки каждого класса до их центра.
В итоге коэффициенты линейной дискриминантной функции находятся из матричного уравнения :
(3) !А| = IS I (IX,! - |X2I) : с = 1/2 |а! (|xf! + |х21)
-1
где |S I - матрица, обратная ковариационной матрице;
IX,|. |Х9| - матрицы (векторы) средних для первого и второго классов соответственно.
Методика сравнения Под термином "задача" будем понимать описание ее струк-ту-ры: число признаков, градаций (оценок; к возможных классов. Каядая задача будет характеризоваться двумя параметрами: объемом обучающей выборки и виде;/ границ между классами.
Рассматриваются четыре вида границ, заданных в форме правил :
1/ если Х1 .> т/2, то зте будут объекты 2-го класса, иначе 1-го класса, где Х1 - номер градации первого признака:
21 если 21 Xi < ii*(l+Wk)/2 - 1-ый класс, иначе - 2-ой. с
где Xi-значение 1-го признака данного объекта;
3) если £ XI < К*П+'л'к)/2 или XI 4 Ш/2 - --ый класс.
с
иначе - второй.
4) если XI < К* (1+!А'к) /2 или XI ^ Ж/2 или
XI - Ц XI > 0 - 1-ый класс, иначе второй.
Граница 1 задает границу типа "отсечка", вторую назовем "линейной", третью - "комбинированной из двух правил", а четвертую - "комбинированной из трех правил".
Для оценки точности аппроксимации разделяющей гиперплоскости ЛДФК и БК использовался метод статистических испытаний (метод Монте-Карло). Разработана методика сравнения РА. по ТАРГ, которая формулируется следующим образом:
1.1. Задается структура задачи, т.е. указывается число признаков и градаций;
1.2. Для каждой из четырех рассматриваемых типов границ строится информационная база, содержащая все возможные объекты для заданного пространства признаков. При этом каждый объект характеризуется вектором признаков, истинным значением номера класса, аттрибутом принадлежности его к граничному элементу. Принадлежность каждого объекта к тому или иному классу устанавливается на основании решающих правил, приведенных зыше, для конкретной границы. Из них же определяются и отмечаются граничные объекты.
1.3. Задается процент обучающей выборки Шр от всех возможных объектов решаемой задачи. При этом число объектов каждого класса ш • в обучающей выборке определяется следующим образом:
т- = шлп»Р(2^)/1'00 . где п> - общее число объектов -го ■! Р J 4
класса для рассматриваемой задачи и определенном типе границы;
1.4. С помощью генератора случайных чисел определяется конкретный набор объектов каждого класса. При этом вначале выбираются объекты, находящиеся около наиболее типичных представителей каждого класса;
1.5. По данной обучающей выборке определяются величины, необходимые для построения обоих классификаторов {коэффициенты линейной дискркминантной функции и матрица условных вероят-
ностей):
1.6. Производится классификация всех возможных объектов для данной задачи с помощью ЛДФК и БК. В базе знаний отмечается номер класса (а для БК еще и апостериорная вероятность), полученного в результате работы каждого классификатора;
1.7. Находятся расхождения для обоих методов между заданной классификацией и осуществленной методами М1 и М2 среди всех возможных объектов и отдельно для граничных. Информация о расхождениях запоминается. Для БК подсчитываются также объекты, для которых вероятность определения каждого класса составляет величину 0.5. Это считается как отказ от классификации и относится к разряду расхождений;
1.8. Последовательность действий 1.4-1.7 повторяется 300-500 раз (задается количество циклов Монте-Карло), а результаты расхождений суммируются;
1.9. Вычисляются и распечатываются средние значения расхождений для данной задачи среди всех циклов Монте-Карло по всем объектам и отдельно по граничным.
Результаты моделирования для девяти задач при различных объемах обучающей выборки и границ различной сложности приведены в табл. 1.
Такое моделирование показало, что метод Байеса имеет лучшие характеристики по сравнению с линейным дискриминантным анализом по критерию ТАРГ, особенно при более сложных границах; при малых объемах 0В точность аппроксимации истинной границы между классами решений "етода Байеса недостаточно высока, а при больших ОВ (не менее 50? от общего числа возможных объектов) точность ее аппроксимас:;: вполне удовлетворительна.
Известно, что мощность СОЗ, з первую очередь определяется полнотой и непротиворечивсстью ее базы знаний.
Третья глава посвяысна вопросам разработки и исследованию методов построения полных и непротиворечивых баз решающих правил, основанных на фактографических данных и экспертных знаниях.
Приводится формальная постановка такой задачи:
Дано:
И - число дискретных признаков;
Wi - (1 = 1.....Ni - число градаций для 1-го признака;
L - число классов ;
Таблица 1
Общие сведения по расхождениям (в линейного дискриминантного анализа и метода Байеса для 4 гсанип и обучающих выборок различного объема
Зада ча Чис- Л С объект. Обучающая Выбо рка % Процент расхождений для заданных границ
Граница 1 Граница 2 Граница 3 Граница 4
ЛДФК БК ЛДФК БК ЛДФК БК ЛДФК БК
Общ Гр Общ Гр Общ Гр Общ Гр Общ Гр Общ Гр Общ Гр Общ Гр
2*4 ±. 0 12.5 25 37.5 50 39 39 31 31 6.3 6 1.5 2 50 50 36 36 30 30 19 19 25 45 15 28 17 33 11 21 6.3 14 11 24 11 23 10 21 20 30 12 18 15 23 10 19 25 50 18 31 15 29 14 25 25 36 19 28 13 21 _ 31 42 22 37 21 41
4*2 16 12.5 25 37.5 50 31 31 4 д л 0 0 50 50 33 33 24 24 4 4 12 15 15 22 1 1 9.3 15 12 19 10 20 6 6 6 6 25 27 19 20 17 18 11 ' 1 12 13 30 33 24 26 12 13
6*2 64 5 12.5 25 37.5 СП 10 10 0 0 0 0 0 0 50 50 23 23 2 2 0 0 0 0 18 22 17 22 11 21 7 13 12 21 16 26 16 25 8 13 5 8 18 18 15 17 9 10 6 7 25 28 18 21 11 12 7 8 5 5 19 19 15 15 14 15 28 3и 25 28 18 19 12 14 12. 13
4*4 256 5 12. 5 25 37.5 50 7 13 6 11 3 6 1 2 0 0 26 28 12 13 2 2 0 0 0 0 19 37 7 20 3 8 2 7 2 6 14 33 14 31 10 24 6 17 £ 1 С 1 ^ 19 -31 12 23 12 24 12 22 9 19 20 30 15 23 10 17 8 16 6 14 24 34 22 29 20 23 18 22 16 28 23 33 16 22 12 17 11 15 10 15
8*2 256 5 12.5 25 37. 5 50 8 8 0 0 0 0 0 0 С 0 12 12 0 0 0 0 0 0 0 0 21 29 11 21 7 14 4 8 3 5 21 33 9 16 4 8 1 2 1 1 24 26 15 17 9 11 6 7 6 7 22 26 8 9 8 9 8 9 5 6 29 33 22 25 17 19 14 15 14 15 23 29 16 20 14 17 13 15 12 14
10*2 1024 5 12.5 25 37. 5 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 и 10 20 5 10 2 д 1 2 0 0 10 21 3 6 0.4 1 0 0 0 0 18 21 14 19 10 13 8 10 6 7 10 12 8 12 7 12 5 3 5 8 24 25 21 24 18 18 13 13 12 12 15 18 13 16 12 15 12 14, 11 14
6*4 4096 12. 5 25 37.5 50 8 15 7 14 4 8 2 0 0 0 0 0 0 0 0 0 0 0 3 12 1 3 0.2 1 0 0 7 24 3 12 2 3 1 2 0 0 18 32 17 31 15 30 15 28 7 15 6 14 6 1 -л 1 Г' -т. х ^ 2 5 19 19 15 15 14 15 16 28 14 27 13 25 12 23 11 23
12*2 л па А 5 12. 5 <¿0 37. 5 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 9 1 3 3 7 11 14 0.4 3 0. 1 1 0. 1 0 17 22 11 14 8 9 7 9 о Ь 2 2 0.1 0 25 28 23 27 14 18 13 17 12 15 11 13 9 12:
Поимечание: Общ - процент расхождений по всем возможным объектам, а Гп" - только для гпаничных объектов.
- 12 -
О » П N1 - число возможных объектов в данной предметной ^ области:
ао - число объектов в базе фактографических данных;
Хк - объект из множества всех возможных объектов
( К= 1.....б)
Требуется:
На основе данных Оо и экспертной информации для каждого Хк найти соответствующий класс решений.
Рассмотрены основные идеи системы КЛАСС (Ларичев О.И., Ме-читов А.И.. Мошкович Е.М., Фуремс Е.М. Выявление экспертных знаний. - М.: Наука, 1989.) , предназначенной для поддержки извлечения знаний в задачах эвристической классификации и направленной на быстрое построение полных и непротиворечивых баз знаний. В ней впервые было предложено использовать отношение доминирования признаков по характерности для неявного назначения класса ряда объектов с неизвестной классификацией, осуществлять контроль непротиворечивости получааемой экспертной информации, выявлять и устранять появляющиеся в ней ошибки. Отношение доминирования по характерности вполне естественно предполагает, что если есть один объект с известной классификацией и есть другой объект со значениями признаков, более характерных для того же класса, что и первый объект, то второй объект должен быть отнесен к тому же классу, что и первый объект.
Однако, в этой системе не использовались фактографические данные, и алгоритм опроса эксперта является переборным, что не позволяет использовать его для создания больших баз знаний.
Возникает вопрос, как наиболее эффективно использовать фактографические данные до привлечения эксперта.
БЗ в системе КЛАСС состоит из набора элементарных' правил (ЭП) з виде продукций: вектора признака и номера класса, выражающих правит: - если Хк то Из сравнения данных ОВ и множества ЭП из базы знаний вытекает вывод очень близкого сходства их структур, т.к. по существу пара /Хо.23о4- из ОВ представляет правиле вида: если Хо то 2Эо. Этот факт был положен в основу механизма извлечения правил из базы фактографических данных, а для создания логико-теоретической модели взаимодействия таких данных и базы знаний оказалось достаточно рассмотреть процедуры выделения непротиворечивых объектов из имеющихся данных и процедуры обобщения ЗП, полученных из них.
Для выделения непротиворечивых объектов из ОВ рассмотрены 3 вида возможных противоречий в ней:
1) когда векторы признаков одинаковые, а классы разные:
2) при наличии известных отношений несовместности ряда значений признаков, такие сочетания признаков не должны иметь в базе знаний правил с номером основного класса;
3) для всех объектов базы данных (примеров) должно соблюдаться отношение доминирования: если один объект имеет набор признаков более характерных для класса решений, к которому принадлежит другой объект, тс первый из них должен иметь тот же класс решений, что и второй.
Для анализа данных ОВ на противоречивость было предложено использовать 3 информационные матрицы Р, Н, к. в которые вносятся его результаты и одна матрица (вектор-столбец) ?, в которой для каждого объекта из ОВ просуммировано число идентичных случаев и оценка его сложности (атипичности), если она имеется.
Использование матриц Р, Н, К и Б позволяет дать формальнее определение процедуры выделения ЗП из имеющихся примеров ОВ: объект XI выражает элементарное правило, если одновременно выполняется:-.
¿г
(4) (Р13 + ИЗ) + Н13= О
3=1 3=1
(г) >с
где С-некоторое числс, ¡ее порог отбора. С>=1 и
чем оно выше, тем более ребовакия предъявляются к
объектам СВ. Например.' мы адазать для получения ЗП
т:лъко такие объекты, :-:;т мн^ число идентичных случаев не менее 2. 3 к т.д. Урав. означает, чте если в 1-ой
строке матриц Р. Р. и Н нее нулевые, то нет противоре-
чий всех трех уровней', и данный объект может рассматриваться для дальнейшего анализа (5).
Одной из наиболее трудных и важных проблем в индуктивном обучении является проблема обобщения. т.е. расширения базы знаний при имеющихся данных на достаточном основании. Лля процедуры обобщения было предложено использовать отношение доминкрева-
ния по характерности, удачно используемое в системе КЛАСС.
В итоге методика извлечения решающих правил из базы фактографических данных Формулируется следующим образом:
1. Создается база данных случаев с известной классификацией (ОВ):
2. Осуществляется проверка на противоречия 1-го. 2-го. и 3-го уровней с помощью соответствующих программ. При этом формируются информационные матрицы противоречий Р, Н, Р:
3. С помощью специальной программы проводится анализ на идентичность (схожесть) и сложность каждого случая из ОВ, заполняется матрица Г;
4. Проводится (зкспертно) анализ противоречий, исправляются случайные ошибки;
5. Проводится (эксперта») анализ уникальных, одиночных случаев из базы данных. При наличии каких-либо сомнений в истинности таких объектов целесообразно исключить их из ОВ, задается порог С, если это необходимо (по умолчанию С=1);
6. Повторяются, если это необходимо, пункты 2, 3 до стабилизации оценок в матрицах Р, К, й и V:
7. Запускается процедура переноса и обобщения ЭП из непротиворечивой.-базы данных, т. е. объектов, удовлетворяющих условию (4), (5).
После извлечения решающих правил из базы фактографических данных возникает следующая проблема: каким образом использовать знания эксперта для полного заполнения базы знаний.
При отсутствии дополнительной информации о структуре задачи и классах решений на начальных этапах опроса эксперта было предложено использовать эвристику средних объектов. Основная идея такого подхода заключается в весьма эффективном использовании отношения доминирования признаков по характерности для неявной классификации ряда других объектов и исключения переборных задач.
. Для подтверждения этой эвристики для самой сложной границы при двух классах решений и N двоичных признаков доказано утверждение: 2
Классификация экспертом (2/Ш+2)} -г- (2М/(М-4)} части средних объектов позволяет косвенно классифицировать все доминирующие их по характерности объекты.
Пусть средний объект доминирует по характерности макси-
мальное число объектов ектов к ^
Ц . Тогда отношение числа средних объ-
'1
(7)
"V
(8)
К/2-1
о _ г — и
N ! (N/2+1)! (N/2-1)! (N/2)! (N/2)! (N-1)! 2
+ 1
2
Пусть средний объект доминирует минимальное число объектов Тогда отношение числа средних объектов к X,- :
^N/2-1
12 =
N ! (N/2+1)! (N/2-1)!(N-2) N 2 (N/2)! (N/2)! N1 2 2 N
Тогда после предъявления (1/В(4-1/Вг) части средних объектов эксперту все объекты, кроме оставшихся средних, будут классифицированы. Следует заметить, что опрос эксперта в такой задаче производится по объектам из двух так называемых средних слоев, расположенных наиболее близко к границе между классами решений и содержащих все средние объекты. При нечетном N эти слои одинаковы по числу средних объектов, содержащихся в них. Расчетные значения показателей эффективности работы алгоритма опроса эксперта по средним объектам в зависимости от числа признаков приведены в таблице 2.
Таблица 2
Число признаков Ъ1 1г ЧИСЛО объектов в средн.слоях 1-1 ц 2
д 2 2 10 3 1. 5
6 о 7 35 4 гС . О
8 1 4 ' г. : 1 ¿6 с 3. 75
1С: 42 52. 5 452 6 4. 3
12 132 ! ¿у _1 • 7 ; с 7 С о О . •о
Общая формулировка методики рационального опроса эксперта, с использованием эвристики средних к результатов моделирования (см. главу 2) заключается з следующем:
1) Определяются так называемые средние объекты, содержащие половину признаков, наиболее характерных для одного класса, а вторую половину - наиболее характерных для другого"класса:
2) Эксперту последовательно предъявляются эти объекты. Он
- 16 -
осуществляет их классификацию;
3) Осуществляется контроль ответа эксперта на непротиворечивость.
4) При отсутствии противоречий осуществляется программное распространение классификации на ряд объектов с неизвестной классификацией (с использованием отношения доминирования признаков.) , повторяются пункты 2-4 до полного завершения средних объектов;
5) Если классификация не завершена, для дальнейшего поиска объектов и представления их эксперту используется метод Байеса, с помощью которого находятся предполагаемые граничные объекты (имеющие максимально близкие друг к другу апостериорные вероятности по каким либо двум классам возможных решений).
На основе изложенного подхода была предложена методика выявления эвристических правил эксперта на его повторяющихся решениях, смысл которой заключается в поиске устойчивых причинно-следственных отношений между признаками и классами решений.
1) эксперту на экране дисплея последовательно предъявляются описания случаев, представленных средними объектами;
2) при обнаружении когнитологом закономерностей в решениях эксперта вырабатывается обобщенное правило, которое записывается в специальный файл эвристик з виде: класс решений + соответствующее сочетание признаков в виде вектора признаков, где' несущественные значения тех или иных признаков отмечены символом "*";
3) это правило предъявляется эксперту в расшифрованном виде и при его согласии передается на проверку;
4) осуществляется проверка на противоречивость по трем уровням, и при их отсутствии, заполняется база знаний. При наличии противоречий -указываются объекты в базе знаний, с которыми это правило несовместно. При этом эксперт анализирует возникшее противоречие и при возможности корректирует эвристическое правило, возвращаясь к пункту 2. При невозможности устранить противоречие следует возвратиться на первый этап и продолжать опрос эксперта по средним объектам.
На основе изложенных выше подходов была разработаны система ДКЛАСС для построения полных и непротиворечивых баз.классификационных решающих правил большого объема.
В четвертой главе „приводятся структура и состав такой
1 7 -
системы, обладающей средствами извлечения правил из фактографических данных и широкого использования эвристик эксперта.
В основу построения системы ДКЛАСС положен модульный принцип. Система реализована в виде трех программных комплексов:
1. Основная система;
2. Утилиты;
3. Редактор базы знаний.
Основная система имеет модульную структуру и состоит из отдельных подпрограмм (функций) общим объемом около 10000 операторов (команд и функций) "Си". Она включает в себя следующие блоки : настройки системы; задания структуры задачи - множества признаков и класссов решений; задания отношений на множестве признаков: на несовместность, характерность и т.п.; создания и ведения базы данных, если она имеется; анализа и проверки базы данных на противоречивость, схожесть, статистика по базе данных; извлечения правил из базы данных, их обобщение; проведения экспертного опроса; выделения граничных объектов; проведения повторных опросов; статистика по базе знаний.
Утилиты содержат набор программ для ряда различных манипуляций с базой знаний, среди которых можно выделить следующие наиболее важные блоки : формирования базы- знаний с помощью эвристических правил эксперта; удаления из базы знаний продукций на основе информации от эксперта; удаления празил по их номерам или векторам признаков; подготовки файлов для повторных опросов эксперта. Весь комплекс программ реализован на языке "Си" объемом около ЮООО операторов.
Редактор DBASE файлов системы ДКЛАСС позволяет работать с любыми файлами такого формата. Т.к. вся информация в системе ДКЛАСС хранится в DBASE файлах, она становится доступной для обработки этим редактором. Он позволяет в диалоговом режиме выбирать тот или иной Файл, просматривать его, редактировать, добавлять и удалять данные. Имеет удобную систему выбора данных по запросу любой сложности, копирования, реструктурирования данных, вывода на принтер к в файлы как DBASE так, и ASCII (текстовый) форматов, вычислять сложные выражения с использованием данных зыбракнсго Файла и многое другое.. Комплекс написан на языке "Клиппер" и содержит около 5000 операторов.
Рассмотрены 4 задачи по созданию полных и непротиворечивых баз знаний, решенные с помощью системы ДКЛАСС. Дана постановка
задачи эксперимента по созданию полной и непротиворечивой БЗ большого объема для дифференциальной диагностики острого аппендицита и почечной колики с числом возможных объектов - 0=16334 при следующих параметрах:
N = 14: W1 = 2: L = 3:
Qof = 111 - число случаев в базе данных с диагнозом острый аппедицит:
0ог = 80 - число случаев в базе данных с диагнозом почечная колика:
Qo = ücf + Qo2= 191 - общее число случаев в базе данных. Для ее создания использовались реальные данные из историй болезни пациентов, лечившихся в 32 ЦВМКГ за период с 1989 по 1991 г.
Подробно описана схема проведения такого эксперимента.
Рассмотрен вопрос целесообразности использования средних объектов для первоочередного представления их эксперту. В данном эксперименте средних объектов было 3442. Из них на границу между 1-ым и 2-ым классами попало 83. К третьему вспомогательному классу их было отнесено 2580. Всего эксперту было предъявлено 415 средних объектов.
В таблице 3 приведено распределение правил для - трех классов решений по всей базе знаний этой задачи для различных источников порождения правил.
Из таблицы 3 видно, что значительная часть правил получена с использованием эвристических правил эксперта, поскольку они имеют большую обобщающую способность. Основная масса таких, правил принадлежит 3-му - вспомогательному классу. Значительное количество правил этим же способом сформировано и для острого аппендицита - 1-го класса решений.
Таблица 3
Источник правила 1 класс 2 класс с класс Всего
1. База данных (БД) 28 47 - 75
2. Обобщенные из БД 42 1029 ' - 1071
3. Эксперт 70 21 193 284
4. Обобщенные от эксперта 1015 324 - 1339
5. Из эвристических правил 3229 652 9734 13615
ВСЕГО 4464 2053 9927 16384
Были оценены динамические свойства процесса накопления правил в БЗ при сравнении его с методом Вайеса по критерию ТАРГ.
Проведен содержательный анализ базы знаний и получены новые данные о поведении эксперта при классификации объектов как на границе классов, так и вдали от нее.
В заключении изложены основные результаты и выводы по диссертационной работе, заключающиеся з следующем:
1. Проведенный анализ литературных данных показал, что несмотря на обилие методов и подходов к задаче классификации не существует универсальных средств ее решения. Наибольшие усилия в настоящий момент времени сконцентрированы в направлении систем, основанных на человеческих знаниях. Подходы и методы, применяемые для создания СОЗ, пока еще несовершенны и находятся на этапе накопления и обобщения эмпирического опыта. На первый план в таких системах выходит проблема построения больших баз знаний. Одним из перспективных направлений в СОЗ является мето-логия построения полных и непротиворечивых баз знаний, реализованная в системе КЛАСС. Для построения больших, полных и непротиворечивых баз знаний эта методология должна быть дополнена рядом методов, включающих процедуры извлечения решающих правил из базы фактографических данных, широкого использования эвристических' правил эксперта и других приемов, позволяющих в ряде случаев избежать переборных задач;
2. На основе материалов литературного обзора сформулирована цель работы и определен круг вопросов, которые необходимо при этом решить.
3. Предложен критерий - точность аппроксимации разделяющих гиперплоскостей {ТАРГ), обеспечивающий надежную и устойчивую оценку качества работы распознающих алгоритмов (РА) во всем диапазоне изменения значений признаков.
4. Разработана методика оценки качества работы РА по критерию ТАРГ,. основанная на принципах статистического моделирования (Монте-Карло).
5. С использованием этой методики для двух РА, основанных на линейном дискриминантном анализе (ЛДА) и методе Байеса (МБ), было проведено моделирование девяти задач, отличающихся числом возможных объектов, признаков, их дискретных значений, сложностью границ, объемом обучающей выборки и классов решений. Од-
ределены области целесообразного использования этих двух РА. Методом статистического моделирования показано, что в задачах классификации:
- На сложных границах МБ имеет лучшие показатели по критерию ТАРГ. чем ЛДА.
- Для ОБ небольшого объема метод Байеса не позволяет с точки зрения ТАРГ надежно аппроксимировать истинную границу между классами решений.
- При больших обучающих выборках (более 31%) метод Байеса достаточно точно аппроксимирует истинную границу между классами решений.
6. Разработана методика извлечения правил из базы данных. Она органически и естественно включается в систему построения полных и непротиворечивых баз знаний. Для этого было предложено использовать три уровня проверки данных на противоречивость совместно с оценкой уникальности и сложности объектов базы данных. В качестве механизма обобщения правил предложено использовать отношение доминирования по характерности.
7. Была предложена и исследована методика рационального опроса эксперта при построении баз знаний большого объема с использованием эвристики "средних объектов" (объектов, имеющих половину признаков наиболее характерных для одного класса решений, а другую половину - наиболее характерных для другого класса решений). Такой подход позволяет снизить требования к производительности компьютера и дает возможность создавать большие базы знаний рациональным образом на компьютерах с невысокой производительностью (типа IBM AT 286).
8. Для подтверждения этой эвристики для самой сложной границы при двух классах решений и К двоичных признаков доказано утверждение: 2.
Классификация экспертом {2/-'N+2)} -г- i2N/(N-4)} части средних объектов позволяет косвенно классифицировать все доминирующие их по характерности объекты.
9. Впервые предложена и исследована методика выявления эвристических правил эксперта на его повторяющихся решениях, позволяющая значительно ускорить создание полных и непротиворечивых баз знаний большого объема.
10. Разработанный комплекс программ позволяет весьма эффективно создавать полные и непротиворечивые базы знаний боль-
- 21 -
шого объема (около 1000 правил за час работы эксперта).
11. Программное обеспечение системы ДКЛАСС обладает достаточной функциональной полнотой и имеет широкий спектр методик для извлечения и анализа знаний.
12. Построены полные и непротиворечивые базы знаний для четырех задач медицинской диагностики, отличающихся по числу признаков, классов решений и числу возможных объектов в базе знаний, с использованием примеров (БФД) и без них.
13. Компьютерные системы диагностики острого аппендицита и почечной колики, а также травм глаз, построенные с помощью системы ДКЛАСС внедрены в клиническую практику 32 Центрального Военно-морского клинического госпиталя, что подтверждено соответствующими справками о внедрении.
В приложении приведены исходные данные и результаты моделирования ряда задач по оценке апорстериорной вероятности граничных объектов и объектов вспомогательных классов методом Байеса.
Основные результаты исследований, проведенных в рамках диссертации, отражены в работах:
1. Баранников A.C., Болотов A.A., Попов'A.C., Берус О.П. Автоматизированная диагностика-невротических и неврозоподобных нарушений в позднем возрасте. // Тезисы докладов юбилейной научно-практической конференции 32 ЦВМКГ "Проблемы клинической и военно-морской медицины" Москва, Воениздат, 1993. с. 26-27.
2. Баранников A.C., Болотов A.A., Попов A.C. и др. К вопросу о многомерном подходе к диагностике невротических и неврозоподобных расстройств у офицеров позднего возраста. // Материалы юбилейной научно-практической конференции "Актуальные вопросы авиационной и военной медицины" Москва, ЦВНИ.АГ, 1993. с. 34-35.
3. Барчуков В.Г., Болотов A.A., Герасименко В.Д.. Умеров Е.Х. Использование математических методов в системе поддержки врача при оказании специализированной помощи. // Тезисы докладов научно-практической конференции "Актуальные проблемы военной и экстремальной медицины". Москва, Воениздат, 1993. с. 67-68.
4. Болотов A.A., Лазаренко Т.В.. ХрамцовВ.Г. Некоторые вопросы построения диагностических систем на базе ЭВМ. //Численные методы и информатика. Сб.науч.тр. - М.: Университет
- 22 -
дружбы народов. 1987. - с. 91--94.
, „ '5.; Боло|§!М>#а-- KSim.B.H. . Храмцов В.Г., Лазаренко Т. В. Медицинская интерактивная система врача, основанная на знаниях. //Численные методы и информатика. Сб.науч. тр. - М.: Университет Дружбы народов. 1988. - с. 94-98.
V 6.; Болотов А. А.. Ким ИГН"."""" Медицинская информационно-консультативная система врача. //Сборник материалов научно-практиЧеской конференции 32-го Центрального военно-морского госпиталя. -М.: Военное издательство, 1990. - с. 58-59.
7. Болотов A.A., барчуков В.Г., Ларичев О.И., Барчук В.А., Ким В. Н. Компьютерная диагностика острых форм ишемической болезни сердца для войскового (корабельного) врача. //Тезисы докладов Всероссиской научной конференции "Кардиология: успехи, проблемы и задачи (актуальные вопросы ишемической болезни сердца и артериальных гипертензий)" (23-25 ноября 1993 г.) Санкт-Петербург. 1993. с. 21-22.
8. Болотов A.A., Барчуков В.Г. Современные математические методы в диагностике, лечении и профилактике различных форм заболеваний у моряков. // Тезисы докладов юбилейной научно-практической конференции 321ЦВМКГ "Проблемы клинической и военно-морской медицины" Москва, Воениздат, 1993. с. 23-25.
9. Болотов A.A.. Герасименко В.Д. Медицинская экспертная система по острым заболеваниям глаз. // Тезисы докладов юбилейной научно-практической конференции 32 ЦВМКГ "Проблемы клинической и военно-морской медицины" Москва, Воениздат, 1993. с. 23-25.
- - 10. Болотов A.A. Некоторые аспекты разработки автоматизированных диагностических систем дяг~"коксультативного медицинского центра ВМФ. //Сборник материалов научно-практической конференции 32-го центрального военно-морского госпиталя. - М.: Военное издат§ль®тво, 1^90. - с. 56 - 58.
И. Хилько В. А., УсановЕ.И.. Умерев Е.Х., Барчуков В.Г., Болотов А.А., Еелозеров В.В. Прогнозирование исходов краниоп-ластики после огнестрельных ранений черепа и головного мозга. Военно-медицинский журнал", N2, Москва, 1994. с. 32-34.
12. Болотов A.A., Ларичев О.И. Сравнение методов распознавания по точности аппроксимации разделяющих гиперплоскостей. //Автоматика и телемеханика. 1995, N 6. ...(15 с).
L
-
Похожие работы
- Организация структур данных и технологическая реализация фактографических информационно-поисковых систем в автоматизированных системах научной и технической информации
- Систематизация, разработка методов и коллективов решающих правил классификации библиографических текстовых документов
- Методы и алгоритмы синтеза нечетких моделей анализа состояния сложных систем на дистальных шкалах многомерных пространств
- Решение задач классификации при двух оценках по каждому признаку для построения полных баз экспертных знаний
- Деревья решений в задачах распознавания образов
-
- Системный анализ, управление и обработка информации (по отраслям)
- Теория систем, теория автоматического регулирования и управления, системный анализ
- Элементы и устройства вычислительной техники и систем управления
- Автоматизация и управление технологическими процессами и производствами (по отраслям)
- Автоматизация технологических процессов и производств (в том числе по отраслям)
- Управление в биологических и медицинских системах (включая применения вычислительной техники)
- Управление в социальных и экономических системах
- Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
- Системы автоматизации проектирования (по отраслям)
- Телекоммуникационные системы и компьютерные сети
- Системы обработки информации и управления
- Вычислительные машины и системы
- Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)
- Теоретические основы информатики
- Математическое моделирование, численные методы и комплексы программ
- Методы и системы защиты информации, информационная безопасность