Синтез гибридных нечетких решающих правил принятия решений на основе логики Л. Заде и Е. Шотрлифа

Опыт решения задач с плохоформализуемыми структурами данных показал, что часто для решения такого класса задач достаточно исследовать два подхода: теорию нечеткой логики принятия решений и методы разведочного анализа, обеспечивающие изучение структуры классов с выдвижением гипотез о наилучших классификаторах [76, 196].

Каждый из этих подходов обладает определёнными достоинствами, но при решении практических задач они используются раздельно, что снижает потенциально достижимые возможности проектируемых классификаторов [76].

Следует отметить, что при решении классификационных задач, характерных для данной работы функции принадлежности, введенные в работах Л. Заде, трактуются несколько иначе, чем это необходимо для решения задач распознавания образов (классификации). В теории нечетких множеств Л. Заде функция принадлежности определяется по отношению к элементам (точкам) множеств и операции теории нечетких множеств совершаются по отношению к их элементам фактически являясь «поточечными».

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

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

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

μ (z), где z- базовая переменная, на которой определяется уверенность в том, что объект принадлежит к классу ω_f. В простейшем случае базовая переменная может определятся на информативных признаках χ, используемых для классификации.

В таком варианте функция принадлежности (уверенности) представляет собой меру доверия (степень принадлежности) к исследуемым классам состояний здоровья описываемых наборами признаков х; . Если объект исследования представляется вектором (набором) признаков X = x₁,...x_i,...,x_n,то при известных многомерных функциях принадлежности (уверенности)решение принимается в пользу гипотезы ω_e, с

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

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

Кроме того, сюда «добавляются» те же сложности, что и при построении многомерных функций распределения классов состояний в рамках статистической теории распознавания образов. С учетом этого, наиболее перспективным представляется подход, когда на основании мнения высококвалифицированных экспертов получают функции уверенности в классификации отдельно по каждому из информативных признаков μ (х.), а решающие правила для всего используемого пространства признаков получают путем агрегации частных функций уверенности в финальные решающие правила с расчетом коэффициентов уверенности Uв гипотезах

где F- функция агрегации для гипотезы ω_i; α_i- настраиваемые параметры обеспечивающие максимальное качество принятия решений по гипотезе ω_l.

В более общем случае в качестве базовой переменной по всему пространству информативных признаков или по отдельным подпространствам могут использоваться некоторые переменные У вычисляемые по величинам исходных признаков:

где f- функция связи x_iс Y_j

Тогда уверенность (коэффициент уверенности КУ_ш ) в терминологии Е. Шортлифа в принимаемых решениях определятся выражениями где b_iвекторы рассматриваемых параметров для переменных Y..

Теоритической основой для перехода от многомерных функций уверенности к системам одномерных функций является известная теорема Арнольда-Колмогорова, согласно которой любая непрерывная функция n переменных fзаданная на единичном кубе n - мерного пространства Iⁿ= I ? I ? ...I может быть представлена посредством одномерных функций

где функции h (w) непрерывные функции одной переменной, а функции

- фиксированные возрастающие, непрерывные, определенные на /=[0,1] стандартные (не зависящие от выбора функции f)функции.

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

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

Основные идеи использования методов разведочного анализа для синтеза модифицированных классификационных решающих правил приведены в работах [76, 115]

Нечёткие решающие правила формируем в три этапа.

На первом этапе изучаем геометрическую структуру классов в пространстве информативных признаков. Этот этап назовем «разведочный анализ».

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

На третьем этапе частные функции принадлежности агрегируются сетевые структуры. Агрегация осуществляется до тех пор, пока не будет обеспечено заданное качество решения задачи [76].

Примеры выбора базовых переменных и параметров функций принадлежности для различных структур классов приведены в работах [76, 115]. (линейно разделимых, кусочно-линейно разделимых, вложенных типа «шар в шаре» и др.)

Практика использования комбинированных нечетких правил принятия решений в задачах прогнозирования и медицинской диагностики показала, что для целого ряда задач одной из эффективных форм агрегации функций уверенности является итерационная формула Е. Шортлифа [76, 77, 78]: где j- номер итерации в расчетах коэфициента уверенности в гипотезе ω_l;

- функция расчета уверенности в гипотезе ω_lто одному признаку x_i с коэффициентом a_i.

Формула (3.23) получена Е. Шортлифом в ходе его длительного наблюдения за клинической логикой принятия решений, в ходе которой наиболее часто врачи выбирают такие признаки x_i, которые свидетельствуют в пользу гипотезы ω^и, по мере накопления подтверждающих гипотезу ωпризнаков, уверенность в искомой классификации растет.

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

С учетом (3.24) общая уверенность в отнесении исследуемого объекта к

классу ωопределяется выражением:

В работах [76, 115] показан вариант использования идеи Л. Заде и данных разведочного анализа для синтеза классификационных моделей типа (3.21).

В этом варианте вначале реализуется агрегация по признакам типа

С геометрической точки зрения выражение (3.26) в многомерном пространстве признаков образует область, ограниченную многомерным гиперпараллелепипедом с нечёткими границами, определяемыми переходом в ноль (носителями) значенийто каждой из базовых переменных x_i.

Величиныплавно уменьшаются при приближении к границам

гиперпараллелепипеда, аопределяется относительно границы с

меньшимі . C классификационной точки зрения не для всякой

структуры классов использование одного выражения (3.26) может обеспечить надёжную классификацию.

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

операцией объединения вида:

гдеq - номер гиперпараллелепипеда покрывающего класс ω_e; m- количество гиперпараллелипипедов класса ω_e.

Рисунок 3.1 иллюстрирует пример полного «покрытия» объектов класса ω_eс помощью трех прямоугольников в двухмерном пространстве {x_lx₂} в задаче с непересекающимися классами.

Рисунок 3.1 - Вариант «покрытия» объектов класса ω_γтремя системами функций принадлежности

Для этого примера принадлежность объектов к классу ω_llопределяется следующим набором формул агрегирования:

Общая уверенность отнесения объекта к классу ω_fопределяется формулой агрегирования типа:

Аналогично может быть построено правило определения уверенности в отнесении объектов к классу ω₂и т.д. [115].

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

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

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

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

После определения шага(например, по формуле Стерджесса) и построения гистограммы искомого (Щ и альтернативного ω_rклассов, эксперты определяют участки, где гистограммы классов не пересекаются(такие участки существуют для классов приведенных на рис.3.2.)

Рисунок 3.2 - Иллюстрация выбора функций принадлежности

1

Рисунок 3.2 иллюстрирует еще несколько особенностей признаковых гистограмм по отношению к истинному взаиморасположению классов в пространстве признаков.

1. Участки не пересекающихся гистограмм свидетельствуют о том, что в исходном пространстве признаков объекты, формирующие эти интервалы гистограмм не пересекаются.

2. По пересекающимся участкам гистограмм (на рис. 3.2 гистограммы по оси т₂ ) нельзя делать вывод о том, что классы пересекаются в пространстве признаков.

3. Амплитуда гистограммы позволяет выдвигать гипотезы о величине уверенности в классификации.

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

5. Учитывая, что гистограммы строятся для конечного числа объектов класса, его истинные границы скорее всего несколько шире, чем это представлено на гистограммах.

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

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

Устранить нехватку информации о структурных особенностях многомерных данных можно привлекая специальный разработанный механизм разведочного анализа ориентированный на синтез нечетких решающих правил. Подробнее этот метод описан в работе [115].

Для простой структуры данных аналогичной той, что представлена на рисунке 3.2, можно ограничится наборами признаковых гистограмм без привлечения средств разведочного анализа. В этом случае не всегда удается достичь требуемых показателей качества классификации, но в ряде случаев он «хорошо работает» при простом механизме синтеза правил типа (3.26).

Рассмотрим подробнее механизм такого синтеза, представив его в виде алгоритма, схема которого приведена на рисунке 3.3.

Рисунок 3.3 - Алгоритм синтеза нечетких решающих правил по

признаковым гистограммам

В соответствии с этим алгоритмом производится выбор класса ω_tдля которого синтезируется нечеткое правило типа (3.26). Выборки остальных классов объединяются в альтернативный класс ω_r(блок 1). Рассчитывается шаг гистограмм и осуществляется их построение h_ω (x_i),h_ω (x_i), блок 2). На экспертном уровне решается вопрос о том, какая может достигаться уверенность в классификации на выбранном пространстве информативных признаков для классов ωи ω_r.Эта величина определяет максимальное значение функций принадлежности (μ^_x>_l≤ 1 иμ^_xr ≤ 1 блок 3). С участием экспертов определяется величина Δx_iна которую может расширится гистограмма при увеличении объема обучающей выборки (блок 4). На рис.

2.2 за такую величину выбран один шаг гистограмм на шкале x_i.В последующих разделах будут оцениваться и другие способы выбора величины Δx. На эту величину гистограммы расширяются влево и вправо. Полученный интервал выбирается как носитель соответствующих функций принадлежности (интервал, на котором μ (x_i) > 0 и μ (x_i) > 0).

Будем считать, что вне интервала носителя противоположного класса его объекты не появляются и соответствующие функции принадлежности принимают максимальное значение (участок 0 -а на рис.2.2 для класса ω_f,).

Учитывая, что уменьшение амплитуды гистограммы может быть вызвано статистическими, а не физиологическими причинами, эксперты решают несколько продлить интервалы μ_max^ и μ_{max r}за пределами интервала носителя противоположного класса. В примере на рис. 3.2 для класса ω_r эксперты приняли решение, что за интервалом [б, в] роль признакаx_jубывает в задаче по классификации ω_r. Используя метод Делфи, эксперты соединяют границы максимальных значений функций принадлежности с границами носителей «своих» функций принадлежности, стремясь повторить тенденции «роста» и «спада» гистограмм (блок 5) по каждому из информативных признаков, формируя графики функций принадлежности для правила (3.26).

На объектах контрольной выборки или в ходе клинических испытаний рассчитывается ошибка качества классификации R_kи сравнивается с величиной допустимой ошибки R_kdon(блоки 6 и 7). При выполнении условия R_k ≤ R_kdon, если в альтернативном классе есть объекты для которых нужно строить свои решающие правила, производится выделение этого класса как ω_i(блок 8 ) и для него повторяются все этапы синтеза. В противном случае процедура синтеза может быть закончена (блок 9).

^пр^{и R}k- ^Rkdon, если принимается решение о продолжении синтеза (блок 10), используя рекомендации, описанные ниже, реализуются другие механизмы синтеза нечетких решающих правил (блок 11).

При более сложной структуре классов, когда одного гиперпараллелепипеда недостаточно для надежного выделения класса ω_i, (например при расположении классов, показанных на рис. 3.1) необходимо разработать механизм наполнения исследуемых классов множеством четких и нечетких гиперпараллелепипедов с выбором формы и параметров функций принадлежности для выражения (3.26).

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

1. В соответствии с общими рекомендациями, принятыми в теории распознавания образов в её геометрической интерпретации формируется обучающая выборка и по возможности выделяется контрольная (экзаменационная) выборка. Выделяется класс для синтеза ω_eи альтернативный класс ω_r, включающий в себя объекты всех анализируемых классов, кроме ω_f,.

2. Строятся признаковые гистограммы и методами разведочного анализа определяется взаиморасположение классов : с

раздельной структурой; с вложенной структурой. Первичную гипотезу о взаиморасположении классов можно выдвинуть по признаковым гистограммам. Чаще всего объекты с раздельной структурой имеют несколько признаков, на шкалах которых гистограммы полностью не пересекаются, а классы с «вложенной» структурой имеют «вложенные» гистограммы по всем информативным признакам. При использовании дополнительных возможностей разведочного анализа определяются гиперобласти пересечения классов 0λи ω_r.

3. Выбирается один из способов описания нечеткого представления данных: гиперпараллелепипеды с нечеткими границами (как в примере рис. 3.2); смешанный вариант (в правиле (3.27) используются гиперпараллелепипеды с четкими и нечеткими границами).

4. Выбираются начальные координаты первого гиперпараллелепипеда (для раздельных структур координаты непересекающихся участков гистограмм, для вложенных структур координата центра тяжести объектов «вложенного» класса. Выбирается шаг измерения ребер гиперпараллелепипеда из следующего рекомендуемого набора: шаг гистограммы; среднее расстояние в пространстве признаков между объектами класса ; средние расстояние между объектами класса ; при отсутствии зоны пересечения классов - расстояние между ближайшими объектами противоположных классов. Определяется условие уменьшения шага измерения ребер гиперпараллелепипеда , при приближении объектов чужого класса (удобно половинить этот шаг). Задаются условия определения максимальных значений функций принадлежности и правила формирования величин функций принадлежности промежуточных и нулевых значений. Выбирается кривая перехода от гиперпараллелепипеда к гиперпараллелепипеду (предпочтительно по изменению величины ошибки классификации или по мере

приближения к объектам противоположного класса). Определяется информативность используемых признаков.

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

6. Выбирается наиболее информативный признак и его граница последовательно увеличивается на шаг измерения ребра Δ _px_i до тех пор пока не будет достигнуто выбранное условие остановки роста ребра (нет объектов своего класса ω_t, произошел захват чужих объектов класса ω, приближение объектов чужого класса к границам формируемого гиперпараллелепипеда). Процедура 6 повторяется для всех информативных признаков от наиболее информативных к менее информативным.

7. Если выбран вариант с четким гиперпараллелепипедом , то для него выбирается величина уверенности в классификации, определенная экспериментами, как максимальное доверие к

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

8. Все объекты обучающей выборки, попадающие в полученный гиперпараллелепипед, из нее исключаются. Для оставшихся объектов строятся новые гистограммы. Если на этих гистограммах обнаруживаются участки с пересекающимися гистограммами классов ω_fи ω_r, то синтезируются семейства гиперпараллелепипедов с повторением пунктов 4 -8 до тех пор, пока на гистограммах не останется непересекающихся участков или пока не будут исчерпаны все объекты класса ω_i.

9. Существуют варианты, когда пересекающиеся признаковые гистограммы, формируются непересекающимися структурами многомерного пространства признаков. Поэтому на следующем этапе синтеза производится поиск таких областей. На наиболее информативном признаке, начиная с любой границы оставшейся гистограммы класса ω_t, выбирается ребро размером Δх. . Из обучающей выборки выбираются все объекты, формирующие это ребро, определяются минимальные и максимальные значения всех признаков, которые используются как остальные ребра нового гиперпараллелепипеда. Для этого гиперпараллелепипеда проверяется попадание в него объекта «чужого» класса и другие условия остановки его «роста». Если ошибочная классификация внутри вновь выделенного гиперпараллелепипеда отсутствует и условия остановки не сформированы, производится увеличение ребер гиперпараллелепипеда аналогично п. 6. В противном случае все ребра, кроме первого, уменьшаются до величин Δχили до выполнения условий остановки ( что наступит раньше). Если эта процедура заканчивается не сформировав искомый гиперпараллелепипед, то по

оси наиболее информативного признака производится сдвиг ребра на величину ∆_px_iс повторением описанной процедуры. Этот пункт повторяется до тех пор, пока не будет просканирован весь информативный признак.

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

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

12. Если в состав ω_rбыли включены классы являющемся предметом исследования, то производится выделение этого класса. С его объектами приводятся все процедуры описанные выше.

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

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

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

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

Перечисленные особенности достаточно хорошо поддерживаются итерационными формулами, предложенными Е. Шортлифом, для расчета коэффициентов уверенности в принимаемых решениях в соответствии с выражениями (3.23), (3.24), (3.25).

3.4