Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf

чайном извлечении наблюдений из генеральной совокупности первые четыре точки извлечены последовательно из вершин с номерами соот­ ветственно 1, 2, 3, 4. Тогда, если стороны а и b прямоугольника удовлет-

те действия алгоритма Б 2а1 после обработки первых четырех точек эта­ лонные точки Е<2>= (е(2>, е^2)) будут лежать одна против другой на серединах длинных сторон прямоугольника. Нетрудно показать, что в какой бы последовательности ни появились затем выборочные точки (из вершин 1, 2, 3 и 4), эталонные точки е[11 и e[l>(I = 3, 4,...) бу­ дут двигаться по соответствующим длинным сторонам прямоугольника до тех пор, пока они не подойдут слишком близко к вершинам этого пря­ моугольника. Из усиленного закона больших чисел следует, что с по­

ному классу, а точки 2, 4 — к другому классу. А при этом разбиении значение функционала Qx (Е) максимально.

И, наконец, приведем пример ситуаций, в которых может произой­ ти определенного рода «зацикливание» алгоритма Б2а1. Рассмотрим двумерную генеральную совокупность, распределение которой сов­ падает с равномерным распределением на круге. Пусть Хь ..., Х п — выборка из этой генеральной совокупности. Мы хотим с помощью ал­ горитма Б 2а1, используя выборку Х ъ ..., Хп, разбить совокупность на два класса. Нетрудно видеть, что в этом случае множество несмещенных точек совпадает с семейством точек Е = (еъ е2), лежащих друг против друга на диаметре круга на одинаковом фиксированном расстоянии от центра круга, и значение функционала (Е) для всех этих точек одно и то же. Кроме того, в этом случае можно показать, что с вероятностью 1

2 Р\ѵ)Рв(е\ѵ), X t (Е<ѵ)))-^0, при v-^oo. i = 1

Здесь Xi (E<v>)-—среднее і-й части минимального дистанционного раз­ биения S (Е(ѵ>) (і ~ 1, 2).

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

Прежде чем переходить к описанию следующих последовательных алгоритмов, заметим, что алгоритм Б 2а1 близок к параллельному ал­ горитму типа Дидея, а именно, к алгоритму примера 1 стр. 108. Разни­ ца этих двух алгоритмов состоит лишь в том, что в алгоритме Б2а1 на ѵ-м шаге эталонные точки выбираются с помощью k + ѵ первых рас­

119

Для этого следует задаться двумя константами Ф0 и Yq, названными в [54] соответственно мерой грубости и мерой точности. Работа алгорит­

может меняться при этом от итерации к итерации.

На нулевом шаге итерации берется любое начальное k (0) и по­ лагается

© / - I , E? = Xj (/==1, ..., k(0)).

Затем производится процедура «огрубления» эталонных точек. А имен­ но, подсчитывается расстояние между двумя ближайшими эталонными точками и сравнивается это расстояние с заданной мерой грубости Ф0. Если это минимальное расстояние меньше Ф0, то соответствующая пара эталонных точек заменяется их взвешенным средним с весом, рав­ ным сумме соответствующих двух весов. Процедура огрубления за­ канчивается тогда, когда расстояние между любыми двумя эталонными точками не меньше чемФ0. Пусть в результате процедуры огрубления

E°j (і — 1, ..., k (0)). При этом если это расстояние больше¥0, ToAé(0) + i

объявляется новой эталонной точкой Е ң о> + 1 = -Х'д(о)+ 1 с весом соГ(0)+1 = 1, а все остальные эталонные точки и соответствующие им

веса остаются неизменными.

Если это минимальное расстояние меньше чем ¥,,, то самый близкий к Х*(0)+і эталон заменяется эталоном, определяемым как центр тя­ жести старого эталона и присоединенной к нему точки ХА(0) + і. Вес точки А*(0)+і считается равным 1. Вес этого нового эталона равен сумме весов объединяемых точек (старого эталона и точки ХА(0) + і).

Все остальные эталоны и соответствующие веса остаются неиз­ менными. Таким образом, пересчет эталонов и весов в этом случае происходит точно так же, как и в алгоритме Б 2а1.

После процедуры огрубления эталонных точек переходят ко 2-му шагу итерации и так далее.

Выбирая различные константы Ф0, ¥ 0, мы будем с помощью алго­ ритма Б2б1 получать различные разбиения. Выбор величин Ф0 и Ч'о можно считать удачным, если разбиение, соответствующее этим вели­ чинам, признается оптимальным или с точки зрения экспертов, или в смысле принятых функционалов качества разбиения.

в) Алгоритм Б 2а2 [7]. В этом алгоритме для задачи разделения совокупности на два класса на каждом шаге итерации строятся разде­ ляющие гиперповерхности произвольного вида, а не только гиперпло­ скости, как это делается в алгоритмах Б 2а1, Б 2б1. Опишем работу этого алгоритма. Пусть на элементах факторного пространства X задана по­ тенциальная функция специального вида, а именно:

К(Х, К )= 2 ь?Ф і(*)Ф і(П

і = 1

120

отнесены к 5<ѵ> иѵ2 = ѵ —Ѵібыли отнесены к S<v>. На (ѵ+1)-м шаге

Ф<ѵ+і)(Х)=ф<ѵ> (Х) + уѴі [К(х, Хѵ+1)-Ф < ѵ>(X)],

а(ѵ+і) = й (ѵ)+7ѵі [ф<ѵ)(Хѵ+1) _ 2fl(v)], ф(ѵ+і) (Х)=ФМ (X),

а( Ѵ + 1 ) — а (Ѵ) ;

(3.31)

б) если Хѵ+і 6S^V), то

ф(ѵ+і) (*) = ф(ѵ> (X),

а(ѵ+і) — а[ѵ\

Ф<ѵ+ О (X) = ф(ѵ) (X) + уѴ2 [К (X, Хѵ+ ,)-Ф < ѵ>(X)], а<ѵ+ О = fl(v> + 7ѵ2 [ф(ѵ) (Хѵ+ ,) - 2 а « ] .

Начальные значения величин, входящих в рекуррентные соотношения (3.31), определяются по точкам Х ъ Х2, а именно:

Ф<2> (X) = К (X, Xt), а<2>= K(Z21,Xl)- ,

Ф<2) (X) = К (X, Х2),

В качестве последовательности 7ѵ выбирается некоторая убываю­

а (ѵ+і) .= а(2ѵ>;

121

б) если Zv+1 f 5М, то

с(ѵ+1) ==с(ѵ);

а(ѵ+ 1) __ ß(v)j

Если /С (X, У) = (X, У) — является скалярным произведением векторов X и У, то спрямляющее пространство Z совпадает с простран­ ством X. Тогда алгоритм Б2а 2 на каждом шаге разбивает совокупность X на два класса гиперплоскостями. Только в начальный момент это разбиение является минимальным дистанционным разбиением, т. е. совпадает с разбиением, задаваемым алгоритмом Б 2а

Свойства алгоритма Б2а 2. Пусть плотность распределения f (X ) — дифференцируемая функция, обращающаяся в нуль вне некоторого ограниченного множества. За функционал качества возьмем Q'2 (S)

Пусть последовательность уѵ, участвующая в работе алгоритма Б2а 2> удовлетворяет следующим пяти условиям:

1) последовательность уѵ монотонно не возрастает;

оо

2) ряд 2 Тѵ расходится;

V — 1

3) существуют два таких числа а > 0 и А, > 0 и такой номер п0,

что

5) для любого L2> 0 найдутся N (Ь2) и х (L2) > 0, такие, что

/= [хѵ]

122