WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 | 4 |

x, y Y таких, что x Сi, y Сj, (x, y) P i j. (2) Сделан обзор подходов к решению поставленной задачи, которые можно разбить на четыре группы. К первой группе относятся подходы к построению экспертных баз знаний, когда эксперт явно формулирует логические рассуждения и заключения, которые ложатся в основу базы знаний. Недостаток этого подхода в том, что значительная часть экспертных навыков, как отмечалось ранее, находится на подсознательном уровне и не может быть корректно извлечена в явном виде.

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

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

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

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

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

Приводится обзор методов ВАР, как наиболее подходящих для построения баз экспертных знаний для интеллектуальных систем обучения, описаны методы ОРКЛАСС, КЛАНШ, STEPCLASS и ЦИКЛ, указаны их достоинства и недостатки. Среди недостатков отмечаются высокая вычислительная сложность, узкая область применения или неэффективная работа с разреженными пространствами объектов, когда допустимые объекты Y* составляют малую часть объектов полного пространства Y. Последний недостаток существенен для задач медицинской диагностики, когда множество комбинаций симптомов исключаются из рассмотрения ввиду невозможности такого сочетания в реальности.

Далее рассматривается проблема достоверности извлеченных знаний.

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

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

На основании проведенного анализа делаются выводы и формулируются цели исследования.

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

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

Определение 1. Альтернативы x, y Y называются сравнимыми: x~y, если x y или y x, иначе они называются несравнимыми: x y.

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

Определение 2. Подмножество альтернатив ВU(Cn) класса Cn называется верхней границей этого класса, если xCn yВU(Cn) такой, что y x и x, yВU(Cn), x y x y.

Определение 3. Подмножество альтернатив ВL(Cn) класса Cn называется нижней границей этого класса, если xCn yВL(Cn) такой, что x y и x, yВL(Cn), x y x y.

Определение 4. Альтернатива x Y непосредственно доминирует альтернативу yY, если x y и zY: x z y.

/ Определение 5. Альтернатива x Y непосредственно доминируется альтернативой yY, если x y и zY: x z y.

/ Множество альтернатив, непосредственно доминирующих альтернативу x, обозначается как ZU(x), а множество непосредственно доминируемых – как ZL(x).

Определение 6. Орграфом G(Y, E) непосредственного доминирования альтернатив называется ориентированный ациклический граф, в котором множество вершин есть множество альтернатив Y, а в множество дуг EYY состоит из элементов (x, y), в которых альтернатива xY непосредственно доминирует альтернативу yY.

Определение 7. Последовательность альтернатив w = , в которой yi+1 ZL(yi), 1 i (l – 1), называется цепью. Число L(w)=l альтернатив цепи w называется длиной цепи. Отдельная альтернатива является цепью длины 1.

Алгоритм КЛАРА основан на идее дихотомии цепей альтернатив, начиная с цепи максимальной длины, впервые использованной в алгоритме ДИФКЛАСС, а затем в КЛАНШ, и адаптирует эту идею на случай разреженных пространств Y. Кроме того, в алгоритме КЛАРА используется новая идея адаптивной дихотомии, позволяющая быстрее находить границы классов решений и ускоряющая классификацию.

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

Использование отношения доминирования (1) и условия непротиворечивости (2) позволяет существенно сократить число непосредственно предъявляемых альтернатив и тем самым ускорить процедуру построения классификации. Действительно, согласно этим условиям, альтернатива x, имеющая более характерные для свойства G оценки, чем y, то есть x y, не может быть отнесена к классу с менее выраженным свойством G. Таким образом, благодаря использованию информации об уже классифицированных альтернативах для классификации оставшихся, становится возможным сократить число предъявляемых альтернатив.

Приводится общая схема алгоритма КЛАРА.

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

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

3. В текущей компоненте связности (к которой принадлежит альтернатива xS) орграфа G(Y, E) строится цепь wmax альтернатив максимальной длины, проходящая через исходную альтернативу xS и содержащая максимальное число ещё неклассифицированных альтернатив из допустимого множества Y*.

4. Поскольку классы {Cn} упорядочены по качеству, границы между классами на цепи строятся последовательно, отделяя класс большего качества Cn от класса меньшего качества Cn+1.

Начало Инициализация данных, нумерация альтернатив, установка значений коэффициентов дихотомии равными di = Выбор первой неклассифицированной альтернативы xS из множества допустимых альтернатив Y* Построение цепи максимальной длины wmax, проходящей через исходную альтернативу xS Выбор пары соседних классов Cn и Cn+1, между которыми надо построить границу.

Выделение элемента xl цепи wmax, где l = dn·L(wmax), и выбор ближайшего к нему неклассифицированного относительно Cn и Cn+1 элемента цепи. Предъявление эксперту. Распространение его ответа по доминированию.

Удаление из wmax нет классифицированных Цепь wmax полностью классифицирована альтернатив да нет Все классы разделены да Пересчет коэффициентов дихотомии с учетом нового деления цепи wmax да Есть ещё неклассифицированные альтернативы нет Классификация построена Рис. 1. Блок-схема алгоритма КЛАРА 5. Для предъявления эксперту выделяется элемент xl цепи wmax, где l = dn·L(wmax), причем если альтернатива xl оказалась недопустимой или уже классифицированной, то в качестве нового xl берется неклассифицированный допустимый элемент цепи с ближайшим индексом.

6. Эксперту предъявляется допустимая альтернатива xl цепи wmax и проводится распространение его решения на максимально возможное число элементов, принадлежность которых к классам Cn и Cn+остается неопределенной.

7. Если wmax еще содержит допустимые неклассифицированные элементы, то продолжается дихотомия цепи wmax, которая завершается, когда все входящие в нее допустимые альтернативы оказываются прямо или косвенно классифицированы относительно классов Cn и Cn+1. В противном случае, на цепи ищется следующаю граница между классами (производится возврат на шаг 4). Если же цепь классифицирована относительно всех классов, то для каждого класса находится индекс k в цепи wmax, где происходит смена класса с Cn на Cn+1.

Полагается dnw=k/L(wmax). На каждом последующем шаге dn есть среднее арифметическое всех посчитанных до этого dnw.

8. Цикл выполняется до тех пор, пока все допустимые альтернативы из допустимого множества Y* не окажутся классифицированными относительно этой пары классов.

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

Идея адаптивной дихотомии цепи состоит в том, что для поиска границы классов на ней применяется не деление пополам, а деление в определенной пропорции, которая подсчитывается исходя из истории деления цепи на классы.

Процедура поиска максимальной цепи основана на процедуре, аналогичной методу КЛАНШ, и адаптирована для поиска цепи, содержащей максимальное число допустимых ещё не классифицированных альтернатив. Доказана математическая корректность этой процедуры.

Показано, что если каждый критерий характеризуется только двумя оценками, упорядоченными по характерности, а число классов решений фиксировано, то вычислительная сложность процедуры поиска очередной альтернативы для предъявления эксперту, которая представляет собой итерацию главного цикла алгоритма КЛАРА, не превышает O(|Y|log2|Y|).

Эта оценка совпадает с аналогичным показателем алгоритмов КЛАНШ и ДИФКЛАСС.

Рассмотрен механизм проверки согласованности ответов эксперта с условием непротиворечивости классификации (2), выявления и оперативного устранения возникающих противоречий по мере построения полной классификации.

Проведено сравнение алгоритма КЛАНШ с другими алгоритмами порядковой классификации по следующей методике сравнения.

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

Пусть даны два класса решения: С1 и С2. Зафиксируем N – число двоичных критериев. Обозначим через r – число основных критериев, а через t – число 1-оценок по дополнительным критериям, причем 1 t <(N-r). Если альтернатива y имеет 1-оценки по всем r основным критериям и не менее t 1-оценок по дополнительным, то она принадлежит классу С1, в противном случае – классу С2. Сформулированное правило используется при статистическом моделировании работы алгоритма в качестве решающего правила для подсчета числа обращений к эксперту, необходимого для построения полной классификации. Будем называть средним числом обращений Q(R, r, t) алгоритма R среднее число обращений данного алгоритма среди всевозможных вариантов выбора r r основных критериев, число которых равно CM.

Число обращений к эксперту никогда не может быть меньше суммы числа элементов нижней границы первого класса решений BL(C1) и верхней границы второго класса BU(C2). Поэтому можно определить эффективность алгоритма классификации следующим образом:

BU (C1) + BL(C2) E(R,r,t) = ;

Q(R,r,t) Приводятся данные и графики, отражающие среднее число обращений к эксперту, а также эффективность сравниваемых алгоритмов при решении задач классификации с различными типами границ между двумя классами решений. График эффективности алгоритма КЛАРА при 11 двоичных признаках показан на Рис. 2:

Алгоритм КЛАРА 1,0,0,0,0,0,0,0,r=0,r=0,Число основных r=0,признаков r=Число дополнительных признаков Рис. 2: Эффективность алгоритма КЛАРА при 11 двоичных признаках.

Для однозначного сравнения алгоритмов определим среднюю эффективность Eср.(R, N) алгоритма классификации R на N двоичных критериях как его эффективность E(R, r, t), усредненную по всевозможным сочетаниям r и t, где r = 0, …, (N–1) и t = 0, …, (N–1) за исключением пары (r = 0, t = 0).

Численное моделирование работы алгоритма КЛАРА по общей методике сравнения алгоритмов классификации показало, что по средней эффективности КЛАРА превосходит алгоритм КЛАНШ, имеющий такую же область применимости, и уступает алгоритмам ДИФКЛАСС и ЦИКЛ, имеющим более узкую область применимости.

Pages:     | 1 || 3 | 4 |






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