<<
>>

5.3. Свойства алгоритма ЦИКЛ


Укажем некоторые важные свойства алгоритма ЦИКЛ.
Лемма 5.1. Для любых векторов х, у Є Y таких, что (х, у) Є Р, и для любой цепи ©~{х, ...,у} мощность множества ©nL(x, у) равна единице.
Доказательство.
Т. к. для любого вектора vG 0 верно, что (x,v)€ Q и (v,y)G Q, то из определения цепи (5.1) следует, что © С А(х, у), и в множестве 0 существует ровно один вектор с каждым значением индекса из диапазона ||х||... ||у||, а значит, И С индексом IMWMI .?
Утверждение 5.1. Построенная алгоритмом ЦИКЛ классификация являєшся полной, т. е. для каждого вектора ує Ya выполняется условие полноты классификации (4-4) и справедливо равенство CL{y)=Cu (у).
Доказательство. Рассмотрим какую-либо цепь вида
{у' У У"}Если CL(x)=Cu (х.) —к, то будем записывать С(х)~к. Векторы у' и у" классифицируются ЛПР на шаге 2 алгоритма ЦИКЛ. Будем предполагать, что либо С(у')=0, либо С(у")—0. либо ()• С\у')<С(у"). Действительно, если С(у')>0, С {у") 0. С(у') С(у"), то нарушается условие непротиворечивости (4.5), а если С(у'); 0, С(у")>0, С(у')=-С(у"), то классификация является вырожденной (все векторы отнесены к одному классу).
При выполнении процедуры классификации D(у', у") на шаге 1 " выбирается, а затем классифицируется экспертом некоторый вектор х° = ©°nL(y',y"). Это пересечение состоит ровно из одного вектора в силу леммы 5.1. Для определенности будем считать, что
y'Px°QyPy". Случай уQx° рассматривается со-вершенно аналогично. Из условия непротиворечивости (4.5) следует, что либо С(х°)--0, либо С(у")=0, либо 0<С(х°) < С {у"). Возможны два варианта:
0- С(х°) = С(у"). В этом случае все векторы на участке цепи 9° между векторами х° и у" принадлежат одному классу, а значит и вектор у также классифицирован;
либо С(х°)=0, либо С(у")—0, либо 0<С(х°)<С(у")- Рас- СМ0'1'1)НМ цепь Э1 -{х°....,у, ...,у"} и повторим для нее те же рассуждения, что и для цепи 0°. А именно: выполняется процедура классификации ?)(х°, у"), выбирается и классифицируется вектор XІ = Є1 П L(x°, у"), и т. д.
В случае yQx° имеем С(у')< С(х°), и также возможны варианты: либо 0<С(у')=С(х°), либо рассматривается цепь ©1:={у', ...,у,...,х0}, выполняется процедура D(y',x°), выбирается х1 = е'ПЦу'^0), ит. д.
Таким образом, последовательно строя цепи 0°, 01,..., либо находим полностью классифицированный участок цепи, на котором находится вектор у, как в варианте 1), либо доходим до содержащей вектор у цепи ©J длины 2, т. к. нетрудно видеть, что |0J + 1|----l4 |в-?|/2. Но алгоритм гарантирует, что к моменту выполнения процедуры классификации ?)(а, Ь) оба вектора а и b уже классифицированы, а значит, будет классифицирован и вектор у.П
Утверждение 5.2. Построенная алгоритмом ЦИКЛ классификация является непротиворечивой, т. е. для любых вект,о- ров х,уЄ Ya выполняется условие непротиворечивости классификации (4.5).
Доказательство. Допустим, что существуют некоторые векторы х* у* Є Ya такие, что для них нарушается условие непротиворечивости (4.5), т. е.
(х* У*) Є Р, х* Є Yfc, у* Є У/, к > I. (5.1)
Вектор х*был либо непосредственно классифицирован экс-пертом, т. е. относится к множеству Уе, либо существуют векторы XІ,х2 Є Ye такие, что х1Рх*Рх2 и х:,х2 Є Уд,- В первом случае будем считать, что х1=х2=х*. Точно так же либо век- тор у* є У, либо существуют векторы у1,у2 Є Ye такие, что у1Ру*Ру2 и у1, у2 Є У;. Однако процедура устранения противоречий R гарантирует выполнение условия (4.5) для множества Уе. Т. е., в .частности, из того, что (хг,у2) Є Р в силу транзитивности отношения Р(поскольку х1Рх*Ру*Ру2), XІ Є Yk, у2 Є У; следует к. < I, а это противоречит соотношениям (5.4). Таким образом, условие непротиворечивости (4.5) выполняется для всего множества У".?
Оценки вычислительной сложности алгоритма ЦИКЛ приведены в работе [4].
<< | >>
Источник: Ларичев О.И.. Вербальный анализ решений. 2006

Еще по теме 5.3. Свойства алгоритма ЦИКЛ:

  1. 5.5. Компьютерная реализация алгоритма ЦИКЛ
  2. 5.2. Описание алгоритма ЦИКЛ
  3. 3.1. Алгоритм компьютерной программы прогнозированияисторических рядов(Алгоритм построен с использованием методовтригонометрического анализа)
  4. 2.1. Не-стабильность и неустойчивость как свойства современной экономики и связь данных свойств с изменениями на мировых фондовых рынках в конце XX – начале XXI вв
  5. 5.6. Сравнение алгоритмов классификации
  6. 5.7. Особенности метода ЦИКЛ
  7. АЛГОРИТМ
  8. АЛГОРИТМ
  9. 2.8. Палитра свойств
  10. 5.1. Свойства конфигурации
  11. Алгоритм знакомства
  12. ГЛАВА 1. Цикл продаж
  13. Некоторые свойства обобщенных функций
  14. Алгоритм вычисления страхового платежа
  15. Алгоритм создания слогана
  16. 10. ПРАВОСУДИЕ И ЕГО ОТЛИЧИТЕЛЬНЫЕ СВОЙСТВА
  17. 5.6. Общие свойства объектов конфигурации
  18. 1.6. Объекты криминалистической идентификации. Их свойства и признаки
  19. 17.1. Понятие и свойства приговора
  20. 58.2. ЖИЗНЕННЫЙ ЦИКЛ ТОВАРА