WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 || 4 |

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

Например, простое решающее правило «к классу С1 относятся альтернативы, у которых не менее трех высших оценок» порождает следующую классификацию со следующей нижней границей первого класса: BL(C1) = {22111, 21211, 12211, 21121, 12121, 11221, 21112, 12112, 11212, 11122}. Легко заметить, что все элементы этой границы суть все возможные перестановки из трех единиц и двух двоек, и её можно Эффективность t=t=t=t=t=t=t=t=t=t=t= записать одним выражением P53(1),2(2). Такая запись весьма близка к исходному смыслу решающего правила, но представлена в более формализованном виде.

Приводится формальная постановка задачи описания границы класса в виде набора решающих правил. Вводится формальная запись ab *** + Pnk [ x1] km[ xm ], кроме {abcde,,abpqr}, (3) которая называется шаблоном правила. Шаблон правила состоит из трех частей.

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

2. Вторую часть шаблона Pnk [ x1] km[ xm ] назовём перестановочной частью правила. Она задаёт параметры перестановок, которые будут осуществляться на местах, помеченных *, и соответствует сочетаниям значений дополнительных признаков. Здесь n равно числу звёздочек, ki – числу оценок xi, участвующих в перестановке.

3. Третья часть шаблона представляет собой перечисление исключений – альтернатив, которых не хватает до полной перестановки.

Ставится задача описания некоторой заданной совокупности альтернатив B минимальным числом правил вида (3) так, чтобы каждая альтернатива попадала ровно в одно правило. Требование минимальности разложения основывается на гипотезе, что решающие правила содержатся в кратковременной памяти эксперта, имеющей ограниченный объём.

Вводятся определения.

Определение 8. Составом оценок альтернативы называется вектор s = (k1, …, kn), где n = max(q), ki – количество i-ых оценок в q альтернативе.

Определение 9. Перестановочную часть правила, порождённную составом оценок s = (k1, …, kn), назовём перестановочную часть k1[1] kn[n] PS = Pm, где m – число ненулевых компонент вектора s.

Доказаны следующие утверждения.

Утверждение 1. Правило вида (3) описывает множество альтернатив с одинаковыми составами оценок.

Утверждение 2. Множество альтернатив с одинаковым составом оценок не содержит альтернатив, находящихся в отношении доминирования (1).

Утверждение 3. Если мощность множества альтернатив с одинаковым m! составом s = (k1, …, kn) равна, где m – число ненулевых k1!… kn! компонент вектора s, то этому множеству соответствует правило, состоящее только из перестановочной части Ps.

Утверждение 4. Если мощность множества альтернатив с одинаковым m! составом s = (k1, …, kn) меньше, где m – число ненулевых k1!… kn! компонент вектора s, то этому множеству соответствует правило, состоящее из перестановочно й части Ps, кроме {некоторое множество альтернатив}.

На основании этих утверждений решающее правило следует искать только для множества альтернатив с одинаковым составом оценок. Любое множество альтернатив с одинаковым составом оценок может быть описано правилом вида (3) с перечислением альтернатив исключений.

Однако правила с большим числом исключений интереса не представляют, так как желательно найти только краткие правила. Поэтому предлагается ввести ограничение на мощность множества исключений, а именно, оно должно содержать не более kc элементов, и kc составляет от общего числа элементов, описываемых перестановочной частью правила, не более kp процентов. В реализованной системе КЛАРА было принято kc = 3 и kp = 25%.

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

Алгоритм 1 – поиск единственного правила.

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

2. Множество альтернатив с уменьшенным числом критериев подставляются в условие утверждения 4 с учетом ограничений на kc и kp 3. Если условие не удовлетворяется, то множество альтернатив B одним правилом не записывается.

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

Общий Алгоритм 2 – заключается в переборе всех возможных подмножеств множества B и применения к ним алгоритма 1 поиска единственного правила. Выбираются все варианты разбиения множества B на минимальное число подмножеств, описываемых единственным правилом, то есть описание множества B минимальным числом правил.

Указывается, что алгоритм полного перебора подмножеств имеет очень высокую вычислительную сложность. Поэтому предлагается алгоритм 3, который заключается в рекурсивном разбиении множества альтернатив B на подмножества по каждому из критериев так, что в каждом подмножестве оценки по данному критерию будут общими для всех альтернатив подмножества. Алгоритм 3 примененяется к подмножествам алгоритма 1 до тех пор, пока алгоритм 1 не выдаст единственное правило. Результатом работы алгоритма 3 также являются минимальные разбиения множества B из тех, которые были получены в процессе его работы. Показывается, что вычислительная сложность log2|B| алгоритма 3 равна = O(| B | N ). Алгоритм 3 перебирает не все возможные разбиения. Это не является существенным недостатком, поскольку исследования показывают, что решающие правила в большинстве своём имеют иерархическую структуру, основанную на различных значениях основного признака. То есть, различные правила, входящие в иерархию, имеют различные значения основного признака.

Попытаться уменьшить неточность алгоритма 3 призван алгоритм 4, который является синтезом алгоритмов 2 и 3. В процессе рекурсивного разбиения множества B на подмножества для подмножеств с небольшим числом элементов этот алгоритм использует алгоритм 2, иначе – алгоритм 3.

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

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

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

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

3. Возникло логическое противоречие. В этом случае запускается обычный механизм устранения логических противоречий. После этого возможен переход в ситуацию 1 или 2.

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

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

Пусть имеется N критериев с q оценками по q-му критерию (q=1, …, N) и M классов решений C1,…,CM. Классы решений объединяются в два kM класса, обозначенные C и C, следующим образом: C =, C = Ci C i i=1 i=k+для некоторого k. Назовем оценки, более характерные для класса C, «верхними», а оценки, более характерные для класса C, «нижними».

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

1. По каждому критерию берутся две нижние оценки.

2. По каждому критерию берутся две верхние оценки.

3. По каждому критерию берется самая верхняя и самая нижняя оценки.

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

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

Эксперт может ошибаться и тогда, когда данный конкретный случай редко встречается на практике, и у эксперта недостаточно опыта для его классификации. Такие знания называются «неустойчивыми» и не подходят для использования в ИОС. В работе выдвинута гипотеза, что эксперт неявно держит в памяти не правила разделения классов, а именно правила отнесения ситуации к конкретному классу. Предполагается, что не только нижняя граница класса A, но и верхняя граница класса B описывается небольшим числом экспертных правил. Между ними располагаются «неустойчивые знания» (см. Рис. 3 и Рис. 4).

Рис. 3. Простая задача классификации Рис. 4. Сложная задача классификации.

Присутствуют «неустойчивые знания» на границах классов A B A B – Граничные элементы класса A – Граничные элементы класса A – Граничные элементы класса B – Граничные элементы класса B – Нестабильные ситуации Была проведена серия экспериментов, подтвердивших гипотезу. На основании гипотезы становится возможным выявлять зону неустойчивых знаний эксперта.

С учетом изложенного строится общая методика извлечения достоверных экспертных знаний. Извлечение знаний происходит в диалоге с экспертом. На первом этапе производится структуризация предметной области: формулировка свойства G, задание экспертом множества критериев K, построение и упорядочение шкал критериев, определение экспертом множества упорядоченных классов решений C. Выделяются исключения, то есть из множества Y удаляются такие ситуации, которые, например, не встречаются в жизни по причине несочетаемости некоторых признаков. Невозможные сочетания могут исключаться как на первом, так и на втором этапе.

Второй этап методики выявления знаний – экспертная классификация, состоит в предъявлении эксперту последовательности векторных оценок.

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

На третьем этапе методики выполняется проверка границ классов.

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

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

В четвертой главе описываются система КЛАРА извлечения экспертных знаний, реализующая предложенный метод построения полных и непротиворечивых баз экспертных знаний; система ОСДИМ для обучения навыкам диагностики острого инфаркта миокарда (ОИМ), и система обучения диагностике расслаивающей аневризмы аорты (РАА), построенные на основе предложенных методов.

С помощью системы КЛАРА можно задавать и изменять структуру задачи классификации, которая включает в себя:

1. Список классов решений, список критериев, списки оценок по шкале каждого критерия;

2. Орграфы доминирования оценок по критериям, задаваемые списками дуг;

3. Упорядочение классов решений по характерности для свойства G.

После задания структуры задачи классификации система КЛАРА позволяет:

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

Описание альтернативы предаставлено на Рис. 5.

2. Осуществлять контроль на непротиворечивость ответов эксперта.

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

Pages:     | 1 | 2 || 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»