Адаптивный поиск границ классов в задачах порядковой классификации

Размещено на http://www.allbest.ru/

АДАПТИВНЫЙ ПОИСК ГРАНИЦ КЛАССОВ В ЗАДАЧАХ ПОРЯДКОВОЙ КЛАССИФИКАЦИИ

Д.Ю. Кочин

Институт Системного Анализа РАН, Москва

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

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

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

Задача экспертной классификации в постановке [Ларичев и др., 1989], [Larichev et al., 1991] предполагает определение множества критериев (признаков), которыми описывается каждый объект. Для каждого критерия задаётся конечное множество допустимых оценок - шкала критерия. Если в некоторой задаче множество оценок по одному или более критериям бесконечно, то соответствующая шкала преобразуется к конечной посредством разбиения исходного бесконечного множества оценок на конечный набор интервалов. Декартово произведение шкал всех критериев представляет собой пространство всех гипотетически возможных объектов (состояний), описываемых в рамках данной задачи. Требуется на основе экспертных знаний построить классификацию в указанном пространстве состояний, т.е. сформировать правила отнесения каждого объекта к одному из заранее определенных классов.

1. Постановка задачи порядковой классификации

Приведем формальную постановку задачи многокритериальной порядковой экспертной классификации. Дано:

1. G - свойство, отвечающее целевому критерию задачи (наличие и степень тяжести заболевания, критичность неисправности в технической системе, ценность кредитного проекта и т.д.).

2. K = {K₁, K₂, …, K_N} - множество критериев (признаков), по которым оценивается каждый объект исследования.

3. , q = 1, …, N - множество оценок по критерию K_q; _q - число градаций на шкале критерия K_q; оценки упорядочены по убыванию характерности для свойства G. То есть, на каждом множестве S_q определено рефлексивное антисимметричное транзитивное отношение Q_q (необязательно связное) такое, что .

4. Y = S₁ S₂ S_N - декартово произведение шкал критериев, которое определяет пространство состояний объектов, подлежащих классификации. Каждый объект описывается набором оценок по критериям K₁, …, K_N и представляется в виде векторной оценки y Y, где y = (y₁, y₂,,y_N), y_q - одна из оценок из множества S_q.

5. - мощность множества Y.

6. Y^* Y - множество объектов, которые требуется классифицировать. Назовём это множество допустимым, а составляющие его объекты допустимыми.

7. C = {C₁, C₂, …, C_M} - множество классов решений, упорядоченных по убыванию выраженности свойства G. То есть, на множестве C определено рефлексивное антисимметричное транзитивное отношение Q_C такое, что . Все эти классы четко определены, каждый допустимый объект может быть отнесен экспертом к одному и только к одному классу. Случаи, когда эксперт затрудняется отнести объект к одному классу, считаются недопустимыми и исключаются из классификации.

Введем бинарное отношение строгого доминирования векторных оценок:

(1.1)

Удобно также ввести отношение нестрогого доминирования:

алгоритм интеллектуальный задача многокритериальный

Отношение доминирования для краткости можно записывать эквивалентными записями (x, y)P x P y x y, отношение нестрогого доминирования: (x, y)Q x Q y x y.

Требуется: На основе знаний эксперта построить разбиение множества допустимых альтернатив Y^* на M классов решений С_i (C_iC_j= i?j, _iC_iY*) так, чтобы выполнялось свойство непротиворечивости:

x,y Y: x С_i, y С_j, (x, y) P i j. (1.2)

2. Метод ЦИКЛ

Лучшие показатели эффективности, с точки зрения числа вопросов, задаваемых эксперту для построения полной порядковой классификации, продемонстрировал метод ЦИКЛ (Цепная Интерактивная Классификация) [Асанов, 2002]. В методе была использована и обобщена идея динамического построения цепей, покрывающих пространство Y, для выбора каждого следующего векторов для предъявления эксперту, впервые предложенная в ДИФКЛАСС [Ларичев и др., 1996]. К сожалению, метод ЦИКЛ обладает довольно узкой областью применимости - он позволяет эффективно строить только полные базы экспертных знаний для предметных областей с полным порядком на шкалах критериев.

3. Метод КЛАНШ

Метод КЛАНШ (КЛАссификация при Непорядковых Шкалах) [Нарыжный, 1998] предназначен для решения задачи порядковой классификации в тех случаях, когда не выполняется требование строгой линейной упорядоченности оценок на шкалах критериев. Вводится ряд дополнительных понятий.

Говорят, что вектор x непосредственно доминирует вектор y, если (x, y)P, x?y, и не существует z, такой, что xPzPy, x?z, y?z.

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

Цепью называется последовательность векторов w = <x₁, x₂, …, x_d>, в которой x_i непосредственно доминирует x_i+1 (1?i?d-1). Число d называется длиной цепи. Отдельный вектор считается цепью длины 1.

Основные шаги алгоритма классификации КЛАНШ:

1 Поскольку классы C₁, …, C_M упорядочены по качеству, границы между ними строятся последовательно, отделяя класс большего качества C_i от класса меньшего качества C_i+1.

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

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

4 Определяется средний элемент y_m цепи w_max.

5 Эксперту предъявляется альтернатива y_m цепи w_max, и проводится распространение его решения по доминированию.

6 Из цепи w_max исключаются классифицированные альтернативы. Если цепь w_max еще не пуста, то продолжается дихотомия w_max, которая завершается, когда все входящие в цепь w_max альтернативы оказываются прямо или косвенно классифицированы относительно классов C_i и C_i+1.

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

Метод КЛАНШ позволяет строить полные базы экспертных знаний, когда предположение о наличии линейного порядка на множестве оценок по каждому из критериев заменяется предположением о наличии несвязного транзитивного бинарного отношения. Вычислительная сложность шагов 3-5 алгоритма не превышает, как показано в [Нарыжный, 1998], величину O(|Y|Чlog₂|Y|).

4. Метод КЛАРА

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

Введём несколько формальных определений.

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

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

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

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

Задача порядковой классификации может быть решена путем предъявления эксперту всех допустимых альтернатив Y* для получения искомого разбиения на классы. Однако использование отношения доминирования (1.1) и условия непротиворечивости (1.2) позволяет существенно сократить число непосредственно предъявляемых альтернатив и тем самым ускорить процедуру построения классификации. Сокращение числа предъявляемых альтернатив становится возможным благодаря использованию информации об уже классифицированных альтернативах для классификации оставшихся.

Нам понадобятся числовые функции C^U(x) и C^L(x), определенные на множестве Y соответственно, как максимальный и минимальный номер класса, допустимый для x, т.е. класса, при отнесении x к которому, не нарушается условие непротиворечивости классификации (1.2). Будем считать вектор x классифицированным и отнесенным к классу C_k, если для этого x выполняется условие: C^U(x)=C^L(x)=k. Первоначально для xY* полагается C^L(x)=1, C^U(x)=M.

Имеется множество альтернатив Y, на котором задано отношение доминирования P, а также M классов решений, упорядоченных по качеству. С каждой альтернативой xY^* связаны максимальный и минимальный номера допустимых классов решений C^U(x) и C^L(x). Перед началом классификации xY: C^L(x)=1, C^U(x)=M. Классификация считается построенной, когда xY^*: C^L(x)=C^U(x).

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

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

Множество альтернатив, непосредственно доминирующих альтернативу x, обозначается как Z^U(x), а множество непосредственно доминируемых - как Z^L(x).

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

Определение 7. Последовательность альтернатив w = <y₁, y₂, …, y_l>, в котором y_i+1 Z^L(y_i), 1 i (l - 1), называется цепью. Число L(w)=l альтернатив цепи w называется длиной цепи. Отдельная альтернатива является цепью длины 1.

Основные шаги алгоритма классификации КЛАРА:

1 В начале классификации коэффициент дихотомии d_i для поиска границы классов C_i и C_i+1 полагается равным Ѕ.

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

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

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

5 Для предъявления эксперту выделяется элемент x_d цепи w_max, где d = d_n·L(w_max), причем если альтернатива x_d оказалась недопустимой или уже классифицированной, то в качестве нового x_d берется неклассифицированный допустимый элемент цепи с ближайшим индексом.

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

7 Если цепь w_max еще содержит допустимые неклассифицированные элементы, то продолжается дихотомия цепи w_max, которая завершается, когда все входящие в нее допустимые альтернативы оказываются прямо или косвенно классифицированы относительно классов C_n и C_n+1. В противном случае, на цепи ищется следующая граница между классами (производится возврат на шаг 4). Если же цепь классифицирована относительно всех классов, то для каждого класса находится индекс k в цепи w_max, где происходит смена класса с C_n на C_n+1. Полагается d_nw=k/L(w_max). На каждом последующем шаге d_n есть среднее арифметическое всех посчитанных до этого d_nw.

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

Остановимся более подробно на шаге 7. Когда цепь w_max оказывается полностью классифицированной относительно всех классов, выполняется процедура UPDATE_DN, аккумулирующая статистику относительно деления цепей на классы.

Эта процедура подсчитывает коэффициенты деления цепи w на классы и представляет их как вектор d, который используется потом алгоритмом COMPUTE_DN (на шаге 5 КЛАРА). В компоненте 0 вектора d содержится число рассмотренных цепей (для того, чтобы COMPUTE_DN могла посчитать средний коэффициент дихотомии для нужного класса), в компоненте i - сумма всех полученных ранее коэффициентов d_i.

На шагах 1-3 UPDATE_DN инициализируются переменные счетчиков, в том числе внешний вектор d, если статистика подсчитывается впервые. Далее в цикле по всем элементам цепи w подсчитывается, сколько раз встречается каждый класс. Несмотря на то, что цепь w полностью классифицирована, может оказаться, что элемент цепи yw относится к нескольким допустимым классам (C^L(y)C^U(y)). Это может произойти в случае, если y не является допустимым. Однако, свою лепту в статистику деления классов этот элемент всё равно внесёт.

Разделив суммарный счетчик для каждого класса C_i на общий счетчик n, и просуммировав полученные коэффициенты для всех ji, получим искомые коэффициенты дихотомии для рассматриваемой цепи w (шаги 12-13 UPDATE_DN).

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

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

Алгоритм КЛАРА завершает свою работу, когда все альтернативы из множества Y* будут классифицированы, то есть yY* C^L(y)=C^U(y).

5. Оценка эффективности алгоритма КЛАРА

В работах [Нарыжный, 1998] и [Асанов, 2002] предлагается общая схема сравнения алгоритмов классификации, которую удобно использовать для оценки алгоритма КЛАРА. Схема основана на статистическом моделировании процедуры опроса эксперта и каждому алгоритму ставит в соответствие его эффективность, то есть отношение минимально возможного числа вопросов к эксперту к числу реально заданных. Было проведено сравнение различных алгоритмов порядковой классификации на задачах с бинарными шкалами критериев. Сравнивались алгоритмы ЦИКЛ, ОРКЛАСС [Ларичев и др., 1989], ДИФКЛАСС [Ларичев и др., 1996], КЛАНШ, КЛАРА [Кочин, 2006] и серия алгоритмов расшифровки монотонных функций алгебры логики [Алексеев, 1976], [Соколов, 1987].

Данные по известным алгоритмам (при N=11 (число двоичных критериев), Q=2) сведены в таблицу (Табл. 1).

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

Табл. 1.

1. Алексеев В. Б. О расшифровке некоторых классов монотонных многозначных функций. // Журнал вычислительной математики и математической физики, 1976. т.16. № 1.

2. Асанов А. А. Методы извлечения и анализа экспертных знаний. Диссертация на соискание ученой степени кандидата технических наук. - М.: ИСА РАН. 2002.

3. Кочин Д. Ю. Построение баз экспертных знаний для интеллектуальных обучающих систем. Диссертация на соискание ученой степени кандидата технических наук, - М.: ИСА РАН, 2006.

4. Ларичев О. И., Мечитов А. И., Мошкович Е. М., Фуремс Е. М. Выявление экспертных знаний. - М.: Наука, 1989.

5. Ларичев О. И., Болотов А. А. Система ДИФКЛАСС: построение полных и непротиворечивых баз экспертных знаний в задачах дифференциальной диагностики. // НТИ, Сер. 2, Информ. процессы и системы, № 9, - М.: ВИНИТИ, 1996.

6. Нарыжный Е. В. Построение интеллектуальных обучающих систем, основанных на экспертных знаниях. Диссертация на соискание ученой степени кандидата технических наук, - М.: ИСА РАН, 1998.

7. Соколов Н. А. Оптимальная расшифровка монотонных булевых функций. // Журн. вычисл. матем. и матем. физ., т. 27, № 12, 1987.

8. Larichev O. I., Moshkovich H. M., Furems E. M., Mechitov A. I., Morgoev V. K. // Knowledge Acquisition for the construction of the full and contradiction free knowledge bases, Iec ProGAMMA, Croningen, The Netherlands, 1991.

Размещено на Allbest.ru