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

наблюдений А и для произвольного I = 1,

2,

k

заданы некоторые

специальные функции ф (Хг, А)

и ф (Хг,

Е),

характеризующие

меру типичности точки Хг как

представителя

группы точек А

руется из наблюдений,

наиболее типичных с точки зрения представи­

тельства эталона Е\й\

т. е.

Sj0) = \X t : ф {Хи E\Q)) <

ф (Хг, £ /0>), / = 1 ,2 ...... k, } ф і ) .

Если оказывается, что ф (Хг,

Е\0)) = ф(Хь £ /0)), то

м о ж н о условиться

относить наблюдение X; к тому из классов S)0) и

который обладает

минимально возможная

нетипичность

двух разных

классов1. Как

и прежде, вначале подсчитываются ф(Хг, £)0))

для всех наблюдений

(г =

1, 2, .... л) и для всех эталонов (/==1,2, ..., /г<0)). Последовательно

для каждого і определяются

эталоны

£ ;“/), для которых данное і-е

наблюдение является наиболее типичным, т. е.

ф(Хг, £ {% )=

min

ф(Хг, £ /0)).

1< I< ft(°)

1

В наиболее общих процедурах «пороги»

<р0 и ф0,

так же как и общее число

«<ѵ)

элементов (nSv^ < и),

составляющих

классы

,

...,

задаются

Если

ф(Хх, Е/0^)) ^

сро,

то

наблюдение

Х г

включается

в

состав

класса S'% ; если же ф(Хх, Е(/о)) >

Фо.

т0

наблюдение

Х г прини­

мается

одновременно

за

новый

эталон

о)+ 1

и

за

новый

класс

5^(0) .

Затем

та

же

процедура

сравнения

производится

с ф (Х2, Е\% )

и

т.

д. до ф(Хп, £'%)). Пусть

в результате

у нас

образовалась на этом этапе алгоритма &(0) (0)

классов

и столько же

эталонов Е=^{£І0),

.... Е*°о)(0)}. очевидно

/г(0) (0 )> k{0). После этого

полученные классы

S<0),

S<2°>,

S^(o){0)

проверяются

на

значимое

попарное различие с помощью порога ф0, а именно, если

фГ <

- Ж 0),

s\0))= ^ Г -

2

E(0)) +

*

Lna4

xiX.eаs<

ф(Х,; S q,

.;<°Л

__

E(0))

<Фо>

'q>

Щ XjfiSt

то классы S q0)

и S\0) объединяются

в

один

класс S{<7>

с

номером

z (q,

I),

равным

min

(q,

/),

и

с

эталоном

Е ^ , п,

состоящим

из max (mq, т{)

наблюдений,

дающих

соответствующее число наи­

меньших

значений

функции

ф (X,

Sz { 4 f Е(0)). Последовательное

вычисление величин ф (S(q0), Sj0>)

и

их сравнение с ф0

производится

до тех пор, пока не окажется,

что

новой системы эталонов Е<'>

= {El1*,

E^J)} и

соответствующих

значимо различимых классов S (0) =

{Si0), S 20), ....

д.

Затем процеду­

ра повторяется применительно к эталонам Е<‘) и т.

до

получения

устойчивого разбиения S (v)

всех

исходных элементов

на

некоторое

число классов k(v+lK

Е<л>= (Е^),

,.м Е<,п>} сходящейся

к

Е (lim Е(п) =

Е),

если, начиная

с некоторого

достаточно

большого

П^-ОО

Е<л>=

Е, при всех

номера я0

я ^ я0.

называть набор

эталонных

множеств

Е =

{Ех, .... Eh}

Будем

1,

локально

оптимальным, если для

всех

X t (і =

2,

..., я) любого

эталонного

элемента I из множества

Ej

(т.

е. I ^Ej) и любого /

= 1,

2, .... k.

S],

Е )> ф (/,

Sj,

Е).

Заметим,

кстати, что в алгоритме работы [33] (см. пример

1) набор

эталонных точек Е = {е1г

е2,

...,

eh}

будет

локально оптимальным,

если эталонные точки еъ е2, ..,

eh совпадают

со средними групп зада­

ваемого ими разбиения, т. е. являются несмещенными.

...,

Eh}

Определим

далее для

любых

двух

наборов Е = {Еъ

и Е = {Elt

...,

Eh} величину

А(Е, Ё )=

2

2

ф (*,

Sj, Ё).

і= 1Xе Е.

класс функций, среди

которых следует вести поиски

нужных нам

Ф и ф.

Одно из таких условий сформулируем следующим образом:

из А (Е, Е) ^ А (Е, Е)

должно всегда следовать, что

А(Е, Е )< А (Е , É).

(3.26)

определять

Ф ( X , E j

) =

2

p ( X , X t),

х; ея.

ф(Х, S j ,

Е) = ф ( X , S j ) .

И наконец, будем полагать,

что

ф(Хг, 5 ^ ф №

, 5 , )

при І ф і .

(3.27)

Ф(Х, S„ Е)

ф(Х, S;)-(p(X, El)

к

2 ’

2

Ф (X, Ej)

./=1

Ф(Х, S;, Е) =

ф (X, S,).

в)

Примеры

параллельных

кластер-процедур,

укладывающихся

в описанную общую схему.

П рГгГме р 1.

Если каждое из эталонных множеств Е\оу состоит

лишь из одной точки е\0), т. е.

тг =

т2 = ... =

mk =

1, а исследуе­

мое р-мерное факторное пространство является евклидовым, то при

выборе функции ф и ф по формулам

ф (Х ,£ ;) = Р в(^ еО ,

Ф (X, S i , Е) =

S P Se ( X , X

{) ,

Xi^ Sl

'

_

1

п

Х - 0 .

X =

—

2

п

i t 1

*

рых

состоит

из

произвольно

выбранной

единственной точки,

т.

е.

£(°)

_ |g(1°))

е р) .

На нулевом шаге алгоритма отнесение наблюдения

Хг (i — 1, 2,

..., п) к одному из двух классов S li0) и S 20) зависит от знака

скалярного произведения (Хг, а„), где а0 —

— е20))- Так что класс

5І0) будет состоять из всех тех Хг, для которых (Хг, а 0) >

0,

а класс

5^0) — из всех тех Хг, для которых (Хг, а 0) <

0. Далее производится

пересчет эталонов по формулам

е\Х) = 2

р і 1 ) х „ еі 1 ) =

-

2

ß l 1 ) x 1,

xie s l

xt es'2

V с с ( ° )

( 0)

где

=

(Xj, а0)

и т. д.

На

(ѵ+

1)-м

шаге

алгоритма

эталоны

определяются по формулам

(ѵ + і)=

2

ßjv) X.

Лѵ+і>

=

2

ß i v , x i(

е\

eh

V

с

V

c

c(V)

Xi 6 Si

Xi

GS2

где

ßjv) =

(Xj, av).

Заметим,

что

«ѵ-и =

с(Г+І)- 4

ѵ+1)=

i

2 (Xj, a v) X j =

2 (2 x p{

air ) )

X„

T. e.

=

1

t = l

\ r = l

a v + 1 = A x A x’ a v — nW av,

где

A x — (p X n) — матрица

наблюденных

компонент

xjr) (i =

1,

2, ..., n\ r =

1,2, ...,p), a

W — выборочная ковариационная матрица

исследуемого признака X. Легко видеть, что если в вышеописанной об­

щей схеме (при k =

2) определить <p (X, Е{) =

(X, ег), / =

1, 2, а в ка­

честве функции ф (X, Sj,

Е) взять любую функцию,

принимающую

(при фиксированном I) минимальное значение в точках Х<;>=

Б

х

Х(Хг, е±— е2) Xj, то мы придем

к только что описанному алгоритму

разделения исходной совокупности на два класса1.

объединенных

П р и м е р 3.

Рассмотрим теперь серию алгоритмов,

Пусть совокупность {Хх, Х2, ....

Х п} нужно разбить каким-то об­

разом на некоторое число классов

(заранее не известное). Пусть

— 1 л

_

ный радиус R <

R0 и рассмотрим процедуру выделения классов для

заданного R. Из любой точки Хг =

Хх, принятой за центр, радиусом

1 В

качестве

ф (X, Si, Е) можно

взять, например, ф (X, Si, Е) =

= Ре (

2 (Xi, ei- e 2) Xi, X ) .