Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 114
Скачиваний: 0
Этим условиям удовлетворяет, например, последовательность
Yv -= Vі1_е . где 0 < е < 42- •
В работе [7] применительно к спрямляющему пространству Z по казано, что с вероятностью 1 разбиение, задаваемое алгоритмом Б3а 2, при неограниченном увеличении объема выборочной совокупности приближается к классу разбиений, среди которых находятся оптималь
ные, |
в смысле Q' |
(S) (см. стр. 95)1. |
В |
заключение |
отметим экспериментально установленный факт: |
в довольно общих ситуациях алгоритмы Б2а ь Б 2а 2 дают при больших объемах исследуемых совокупностей устойчивые и близкие к оптималь ным (в смысле соответствующих функционалов) разбиения, хотя упо мянутые выше теоретические свойства алгоритмов и не гарантируют нам этого.
5. Последовательные кластер-процедуры и метод стохастической аппроксимации
-Большое число последовательных кластер-процедур может быть по лучено с использованием метода стохастической аппроксимации. Опи шем в чем состоит этот метод.
Пусть некоторый вектор Y является случайным вектором, инду цирующим в пространстве своих возможных значений вероятностную меру Рх, зависящую от некоторого фиксированного векторного пара
метра X . Рассмотрим функцию мую функцию регрессии Y по X. венном векторе а уравнение
т (X ) = J Y P x (d Y ) — так называе Допустим, что при некотором вещест
т (X) = а |
(3.32) |
обладает единственным корнем Ѳ. Ставится задача отыскать этот корень. Если бы распределение Р х было известно при всех значениях X, то мы могли бы найти корень Ѳпрямо из уравнения (3.32). Но часто возникают ситуации, в которых распределение Рх неизвестно и, следовательно, неизвестен вид функции т (X). Метод стохастической аппроксимации предлагает итерационную процедуру для оценки Ѳ с помощью наблю дений над случайным вектором Y при различных значениях X. Итера ционная процедура метода стохастической аппроксимации для этой задачи имеет вид:
0(v+i) = 0(v)+Yv( a _ y v), |
(3.33) |
где Ѳ<ѵ>— ѵ-е итерационное значение неизвестного параметра, а Yv — ѵ-е наблюдение исследуемого случайного вектора. В качестве началь ного значения ѲН) можно брать любой вектор.
1 Имеется в виду, что параметры разделяющей гиперплоскости данного ал горитма с вероятностью единица стремятся (при п —» оо) к параметрам а и с, оп ределяемым по формулам (3.22).
123
При определенных условиях на вид функции т (X), на Рх и на по следовательность уп доказаны теоремы о сходимости описанной процедуры к корню уравнения (3.33) ([9], [36] — [40]). Сходимость может пониматься в разных смыслах (в среднем квадратичном, почти всюду
^Легко понять, что задача поиска единственного экстремума некото рой исследуемой функции R (X), точный вид которой может быть неизвестен, сводится к задаче оценки единственного корня уравнения aR (А) = 0, которое является частным случаем уравнения (3.32).
Поэтому для оценки единственного экстремума исследуемой функ
ции можно использовать описанную выше итерационную процедуру
(3.33).
Перейдем непосредственно к задачам кластер-анализа. Пусть X (как и раньше) — пространство всевозможных значений признаков исследуемых объектов. Будем считать, что на X задана плотность ве роятности f (X ). Предположим, что задано разбиение S пространства X на k ^непересекающихся областей 5 —{Sx, ..., Sfe}. Допустим, что для каждой области 5 г разбиения S заданы функции потерь Ft (X , S), ко торые оценивают потери при попадании объекта X в область 5-
( і = 1 , ... . k ) . |
1 |
Рассмотрим выражение |
|
k |
|
R(S): V 5 Ft (X, S)f(X) dX, |
|
S; |
|
определяющее суммарные потери классификации 5 |
(суммарная функ |
ция потерь). Задача классификации в данной постановке может рас сматриваться как задача нахождения такого разбиения S пространства
X, при |
котором R (5) минимально. |
|
|
|
||
|
Пусть Е = (ег , ...,ek) — некоторые эталонные |
точки разбиения |
||||
еі |
еі |
эталонная точка^области 5 г (г = |
1, ..., |
k) |
например, пусть |
|
условные средние г'-й области разбиения 5. |
Предположим, далее, |
|||||
что |
функции потерь Ft (X, S) |
являются |
функциями лишь от эталон |
|||
ных точек Е, т. е. Ft (X, S) = |
Ft (X, Е). |
Тогда R (S) = R (Е). Задача |
||||
классификации в этом случае сводится к задаче нахождения раз биения S*, для эталонных точек которого R (Е*) минимально.
Необходимые условия минимума R (Е) имеют вид [32]. |
|
||||
|
|
V Су |
Ft (X, Е) / (X) dX = 0, |
(3.34) |
|
|
|
/= 15. |
|
|
|
|
|
Fj(X, |
E ) ~ F i (X, Е) = 0, |
(3.35) |
|
для |
всех X, |
принадлежащих границе |
областей S it Sj |
(г, j = |
|
1, |
... 9kt і ~і~у) |
|
|
|
|
(зДесь Ѵе/ = |
( ~ ф г Р’ ~ ф г Р’ - ’ |
-градиентфункции F |
|||
по направлению, задаваемому вектором |
|
|
|||
124
Уравнения (3.35) определяют границы между соседними областя ми при тех значениях эталонных точек Е, которые удовлетворяют уравнениям (3.34).
При некоторых, не очень жестких предположениях на функции потерь Ft (X , Е) [32], разбиение 5, удовлетворяющее уравнениям (3.34)
и (3.35), |
может |
однозначно восстанавливаться |
по этим функциям. |
|
А именно, |
л: £ S ;, если Ft (X, Е) — Fj (X , Е) < 0, |
для всех }фі. Вид |
||
но, что функции |
потерь Ft (X, Е) имеют при этом тот же смысл, что |
|||
и функции ф (X, |
S t) — меры типичности точки |
X, |
как представи |
|
теля группы S t |
(см. стр. 105). |
|
зная функции |
|
Таким |
образом, при некоторых предположениях, |
|||
потерь, можно строить оптимальное разбиение S по оптимальным эта лонным точкам, которые определяются как решения уравнений (3.34), (3.35).
Процедура стохастической аппроксимации для оценки корня урав
нений (3.34), (3.35) имеет вид (3.33). |
|
|
е(ѵ)= е (ѵ -1) _ 7(у) |
* |
Е(ѵ-П) |
2 %і (Ху, Е(Ѵ-1 |
||
|
.<= 1 |
|
где (е(іѵ), ..., ßfeV)) = E(v)—ѵ-я итерация в процессе |
оценивания кор |
|
ня уравнения (3.35), |
|
|
1, если X £ S 0
Х і ( Х , Е)
О, если X(£Sj.
В зависимости от вида функций Ft (X, Е), т. е. от вида экстремизируемого функционала R (S), получаются различные итерационные процедуры. Рассмотрим некоторые из них.
Воспользуемся переходом в так называемое спрямляющее про странство Z (см. стр. 94), сопоставив каждой р-мерной точке X из ис ходного пространства X Х-мерную точку
bl Фі(Х)
Z(X) =
фтѵ (X)
Здесь {фх (X), ..., фл? (X)} — набор известных функций от р перемен ных, а — некоторые константы.
Таким образом, любое множество А из X отобразится в соответствую
щее множество А ={Z (X) : X £ А} из Z. В частности, любая система эталонных точек е = {еъ ..., ek} отобразится в соответствующую ей
систему эталонных точек Е = {ех, .... eh} £ Z
Пусть FI(X, Е) = || Z (X) —'еі ||2 + 2 F j 2-
т= 1 (т Ф і)
125
Тогда алгоритм стохастической аппроксимации для поиска экс тремума функционала
|
/ |
? |
( |
Е |
) |
= |
|
v |
[ |
| |
| |
|
|
|
і= IL |
|
|
|
m= 1 |
|
|
|
|
|
|
|
|
|
|
|
(/n^ 1) |
|
|
|
|
дает следующее |
описание ѵ-й итерации |
соответствующей |
вычисли |
|
|||||||
тельной процедуры. |
|
|
|
|
|
|
|
|
|
||
После завершения предыдущей (ѵ— 1)-й итерации и по «предъяв |
|
||||||||||
лении» Х ѵ вычисляется величина Zv = Z (Х ѵ) |
и отыскивается такой |
|
|||||||||
номер г0 (1 < |
г'о < к), |
для которого |
при |
всех |
/ = 1, 2....... k |
(j=i0) |
|
||||
оказываются |
выполненными |
соотношения |
|
|
|
|
|
||||
|
|
|
( Ѵ - І ) |
— е)( V — 1 )), Zv) < |
0. |
|
|
|
|||
После этого |
определяются: |
|
|
|
|
|
|
|
|||
|
~ < Ѵ ) = е ІО |
|
|
|
|
|
|
(3.36) |
|
||
|
|
ejv) = |
g( v - i , _ _ v ( v - i ) ( ^ v - i ) _ Zv) > |
|
|
||||||
|
|
|
(/ = 1 .2 ,..., |
k\ |
j =f=io). |
|
|
|
|
||
Нетрудно убедиться в том, что если k = 2, то приведенный алгоритм при соответствующем подборе уп совпадает с алгоритмом работы [10] в том случае, когда потенциальная функция К (X, Y) может быть пред ставлена в виде ряда
К (X, У) = V X? Фг (X) фг (Y) = (Z (X), Z (У)).
|
|
/ —1 |
|
|
|
Действительно, пусть еіѵ~ D = |
^ _2Z (X), |
где суммирование |
|||
ведется по всем тем элементам множества J{X1( ..., ХѴ_ І}, которые до |
|||||
(ѵ |
1)-го шага |
относились к Sj-й группе, а (ѵ -— |
1)^- — число таких |
||
элементов (/ = |
1, 2). Согласно алгоритму [10] |
элемент Х ѵ относится |
|||
к <Sb |
если на ѵ-м шаге |
|
|
|
|
|
|
((1іѵ -1)- е (2ѵ_1>), |
Zv) > |
0. |
|
Это же можно записать в эквивалентной форме с помощью соотношений
(3.36), в которых нужно |
положить 7<ѵ_1) = (Ѵ__ ^ • |
Пусть Fi = I Z — et f |
и k = 2. Величина Z = Z (X) опреде |
ляется по X так же, как и в п. (а). Алгоритм стохастической аппрокси мации в этом случае запишется в виде:
ею
|
ß(v) = ^ v - D _ T(tv-i) ( ë ( v - l ) _ Z v), |
|
|
|||
если |
\е^ ~ 1) f —|fe<V-D f —(ё^ ~ 1>—e<v-1)) Zv < |
0, |
|
|||
|
e(V) = |
g(v-1) _ |
Y<V-1) (è(v-1) _ |
z v), |
|
|
|
|
Лѵ) |
Лѵ—I) |
|
|
|
если |
1 > l i 2 |
1— > |
I ë{v-M 1>II ^ — - i |
v ( 4 |
v - |
1 |
126
Очевидно, что этот алгоритм близок к алгоритму работы [7], когда
N
К (X, Y) = ^ Kf ф; (X ) срг (Y), хотя полностью и не совпадает с ним.
і= 1
Вописанном только что алгоритме в отличие от алгоритма из [7].
Каждое ѵ-е приближение разделяющей гиперплоскости (в спрямляющем
пространстве Z) проходит через середину отрезка е(іѵ> — е(2ѵ).
Пусть теперь Ft {X, Е) = ||Х — etf. В этом случае алгоритм стохастической аппроксимации для нахождения экстремума функцио нала R (S) совпадает с алгоритмом [56]. Действительно, алгоритм сто
хастической аппроксимации задается |
следующей итерационной |
про |
||||||
цедурой. Отыскивается такой номер і0 (1 ^ |
г0 ^ |
k), для которого при |
||||||
всех і = 1, |
2, ..., k (і Ф |
і0) оказываются выполненными соотношения: |
||||||
и полагают |
II е}ѵ~ 1f - И |
4 Г 1 ) ||я + |
( 0 < Ѵ _ ‘ ’ - е |
} Г |
1’ ) |
< |
О |
|
|
|
|
|
|
|
|
|
|
е(? = е ^ |
0 —у|ѵ |
1)—Хѵ) для |
всех |
г = 1, ..., k, |
но |
i=f=i0. |
||
6. Замечание о методах предварительной обработки классифицируемых наблюдений
Предварительная обработка данных преследует в основном две цели:
1)техническую, связанную с сокращением времени и уменьшением машинной памяти, необходимых при использовании алгоритмов клас сификации;
2)теоретическую, направленную на улучшение результатов дей ствия применяемых алгоритмов.
Косновным приемам, с помощью которых исследователь добивается достижения сформулированных выше целей, можно отнести:
—агрегирование данных, заключающееся в переходе от классифи кации исходных элементов к классификации объектов, каждый из которых представляет собой ту или иную форму выражения целой груп пы заведомо однородных исходных элементов;
■— выбор начальных приближений для эталонных точек (е<0)), для неизвестного числа классов (&(0)). для искомого разбиения (S<°>),
для пороговых значений |
и т. |
п.; |
ориентиро |
— некоторое упорядочивание |
исходных наблюдений, |
||
ванное, например, на принадлежность рядом стоящих |
элементов |
||
к одному (общему) классу, или на последовательное убывание опреде ленным образом заданной величины, характеризующей плотность на блюдений в окрестности соответствующей точки, и т. д.
Конечно, первое, что следует испробовать при решении этих за дач, — это профессиональный, экспертный подход. И лишь затем мож но воспользоваться формальными эвристическими приемами. Некото рые из них мы здесь опишем.
— некоторые методы «анализа мод».
127