<<
>>

5.6. Сравнение алгоритмов классификации


Для сравнительной оценки эффективности алгоритмов классификации ЦИКЛ и ОКЛАСС был проведен вычислительный эксперимент.
Для различных множеств векторов У задавались решающие правила классификации, которые имитировали распространенный тип правил, используемых ЛПР.
Такие правила сходны с примерами решающих правил из предыдущего раздела. А именно, в множестве критериев выделяются группа основных, наиболее важных критериев. Моделируемое решающее правило формулируется следующим образом: объект относится к классу Сі, если сумма его оценок по основным критериям равна г и сумма оценок по остальным критериям не превышает t. Как видно, каждое правило зависит от трех параметров: от подмножества номеров основных критериев Е C{l,...,iV}, от г и от t. Отметим, что всегда 0 < t < (N — г). Сравниваемые алгоритмы поочередно строили полные классификации, задавая вопросы о классе принадлежности объектов и получая ответы в соответствии со смоделированными решающими правилами.
Значения числа предъявлений векторов (описаний объектов) для классификации позволяют некоторым образом характериУг 4*
зовать сравниваемые алгоритмы. Однако можно предложить более показательную оценку их эффективности, а именно меру избыточности числа задаваемых вопросов.
Рассмотрим верхние и нижние границы классов: оптимальные по Парето множества соответственно недоминируемых и недоминирующих (в смысле отношения Р) объектов. Можно показать, что произвольный класс определяется своими верхней и нижней границами. Границы класса представляют собой минимальные множества объектов, которые необходимо предъявить для построения полной классификации. Поэтому количество векторов, принадлежащих границам класса, определяет минимальное количество объектов, которые достаточно предъявить для построения полной классификации.
Таким образом, в качестве эффективности алгоритма А удобно рассматривать величину
зек Q(A, і, Г, t)
Здесь Ви(Y\) и Bl(Y'2) — соответственно верхняя и нижняя границы классов С\ и С2; Q(A,3,r,t) — число вопросов, задаваемых алгоритмом А для построения классификации, определяемой правилом с параметрами H,r,t, усредненное по всевозможным вариантам выбора Б. для данных г и avg — операция усреднения по всем подмножествам основных критериев, K = {1,...,N}.
Значение эффективности алгоритма E(A,r,t) всегда больше 0 и меньше или равно 1. Оно является количественной мерой избыточности числа вопросов, задаваемых эксперту. Так, если эффективность алгоритма E(A, r,t) равна 1, то при данных г и t алгоритм задает ровно столько вопросов, сколько необходимо для построения классификации. Если эффективность E(A,r,t) равна 0,5, то алгоритм задает в 2 раза больше вопросов, чем необходимо в данном случае.
Часть данных, полученных в результате вычислительного эксперимента (для решающих правил, основанных на 6 критериях с 3 оценками на шкале каждого критерия), представлена в виде графиков на рис.5.2 и рис.5.3. Видно, что алгоритм ЦИКЛ более эффективен (задает меньше вопросов), чем алгоритм ОРКЛАСС практически для всех моделируемых решающих правил. При моделировании классификации в множествах альтернатив с другим числом критериев и оценок на шкалах были получены сходные результаты.
130-5-0.6 01)4-05 ИОЗ-04
j В 0.2-0.3І
sol о г
ІшО-ftl
индекс по ;и толнительным критериям
индекс по основным критериям - II
Рис. 5.2. Эффективность алгоритма ОРКЛАСС (6 критериев, по 3 оценки)

индекс по основным критериям
Рис. 5.3. Эффективность алгоритма ЦИКЛ (6 критериев, по 3 оценки)
09Ш
вШШ
Q 0.5-0.6
ШМі
»ft2-0.3 10.1-0.2 j !¦ 0-0.1
1 = 10 і = 8 і-б
t = 4 ИНДЄКС ПО
2 дополнительным критериям
4. Ларичев О.И. Как уже упоминалось, задача порядковой экспертной клас-сификации имеет близкий аналог в области математической логики. Если заменить эксперта безошибочным оракулом, то имеем известную задачу расшифровки монотонных функций [13] с похожим критерием оптимальности (минимум обращений к оракулу). В работе [1] предложен алгоритм А расшифровки мо-нотонных функций, определенных на множестве Y с произвольным количеством оценок по критериям. Сходство задач многокритериальной порядковой классификации и расшифровки монотонных функций алгебры логики позволило сравнить эффективности алгоритмов решения этих задач [23].
Приведем результаты итогового сравнения алгоритмов. На рис.5.4 представлен график эффективности алгоритмов А, ОРК- ЛАСС и ЦИКЛ для задач с различными числом критериев и оценок на шкалах.

Рис. 5.4. Эффективность алгоритмов А, ОРКЛАСС, ЦИКЛ
<< | >>
Источник: Ларичев О.И.. Вербальный анализ решений. 2006

Еще по теме 5.6. Сравнение алгоритмов классификации:

  1. 3.1. Алгоритм компьютерной программы прогнозированияисторических рядов(Алгоритм построен с использованием методовтригонометрического анализа)
  2. 5.3. Свойства алгоритма ЦИКЛ
  3. 5.5. Компьютерная реализация алгоритма ЦИКЛ
  4. 5.2. Описание алгоритма ЦИКЛ
  5. АЛГОРИТМ
  6. АЛГОРИТМ
  7. СРАВНЕНИЯ
  8. Алгоритм знакомства
  9. Алгоритм создания слогана
  10. 3.7. Оценка эффективности процедуры сравнения альтернатив
  11. Алгоритм вычисления страхового платежа
  12. 2.5. Сравнение альтернатив
  13. Алгоритм формирования эффективных каналов сбыта
  14. 6.1 Метод прямого сравнения
  15. 9.1. Трудности практического сравнения методов
  16. 9.5. Сравнение методологических подходов
  17. 8.2. Сравнение методов ЗАПРОС и ОРКЛАСС