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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.10.2024

Просмотров: 110

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Приведем в заключение результаты исследования некоторых типов иерархических и параллельных кластер-процедур с точки зрения их допустимости в различном смысле [42]. Через Пъ 1І2, П 3 будем обозна­ чать иерархические алгоритмы, использующие понятие близости между группами с pmln (Si, Sm), pmax (St, Sm), p (St, S m) соответственно, че­ рез П будем обозначать алгоритмы, минимизирующие функционалы

типа Qx, Q2 путем простого перебора;

через П5—алгоритмы,

условно

минимизирующие функционалы типа

и Q2. Это отвечает

ситуаци­

ям, когда поиск оптимального алгоритма приводится лишь в пределах некоторого специального класса алгоритмов. Ниже дана таблица с ре­ зультатами исследования алгоритмов — П5 на допустимость.

4. Последовательные кластер-процедуры

Если число п классифицируемых наблюдений X lt Х 2, .... Х п до­ статочно велико (от несколько сотен и более), то как мы уже отмечали, реализация кластер-процедур иерархического и параллельного типов практически невозможна. В этих случаях пользуются итерационными алгоритмами, на каждом шаге которых последовательно обсчитывается лишь небольшая часть исходных наблюдений, например одно из них. В том, что п велико, имеются не только неудобства, но и свои преиму­ щества. В частности, это позволяет исследовать асимптотические (по п) свойства соответствующих процедур, аналогичные, например, свойст­ вам состоятельности, асимптотической несмещенности и т п., анализи­ руемым в теории статистического оценивания и статистической провер­ ки гипотез.

Как и в параллельных алгоритмах, основными средствами и идея­ ми, при конструировании последовательных кластер-процедур явля­ ются: мера близости или расстояние между группами; порог; эталон­ ные множества или точки; функционал качества разбиения.

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

Именно такую задачу решает, например, простой последовательный алгоритм [70], [73], использующий понятие порога с. В этом алгоритме случайным образом выбирается точка Х г, которая объявляется центром ег первой группы. Затем точка Х2 относится к первой группе, если р (Х2, Cj) ^ с. В противном случае Х 2 принимается за центр второй

группы Х 2 = е2 и т. д. На 1-м шаге, когда уже имеется г групп, точка

Х г либо

становится центром (г + 1)-й

группы, либо относится к той

из групп,

для которой р (Xi, ej)^c. Если таких групп несколько, то

выбирается та, к центру которой точка

ближе всего; если и таких

групп несколько, то устанавливаются некоторые соглашения о том, куда относить X г в этом случае.

114

Остановимся далее на описании двух наиболее общих и наиболее исследованных последовательных кластер-процедурах (и некоторых их модификациях), допускающих, в частности, интерпретацию в вероят­

ностных терминах.

 

 

 

а)

Алгоритм Б 2а1.

Метод ^-средних [56]. Пусть

наблюдения

Х г, Х 2,

...,

Хп требуется разбить на заданное число k (&<я) однород­

ных (в смысле некоторой метрики р) классов.

уточнении

Смысл описываемого алгоритма — в последовательном

эталонных

точек Е<ѵ>=

{е[ѵ\ е<ѵ)> ..., 4 Ѵ)} (ѵ — номер

итерации,

V = 0,

1,2,

...) с соответствующим

пересчетом приписываемых им

«весов»

 

= {со<ѵ>, (ü<v>,

..., соГ}.

При этом нулевое приближение

Е<°> строится с помощью случайно выбранных первых k точек исследуе­ мой совокупности, т. е.

е-0> =-Х.

а>}°> = 1, і = 1, 2, ... , k.

Затем на 1-м шаге «извлекается» точка Х к+1 и выясняется, к какому из эталонов е)0> она оказалась ближе всего. Именно этот, самый близкий к X k+1 эталон заменяется эталоном, определяемым как центр тяжести старого эталона и присоединенной к нему точки Xfe+1 (с увеличением на единицу соответствующего ему веса), а все другие эталоны остаются неизменными (с прежними весами) и т. д. Таким образом, пересчет эта­

лонов и весов на ѵ-м шаге, т. е. при извлечении очередной точки Х^+ѵ, происходит по следующему правилу:

СО,(V)

„ ( ѵ — 1) -X

 

 

 

 

 

 

 

— - , если р (Xk+v, ß/v+1)) =

с!ѵ) =

 

со)ѵ) + 1

= min

р(Хft+ v’

g(v-D)

 

/

h

 

 

 

i « / < *

'

 

 

 

 

( V — 1)

в противном случае,

 

 

 

ei

 

 

 

 

„(v—1)\

co<T—и = co|i*v ^ +

l, если p(Xé+v, ejv

‘^ m

i n

p(X,k +

V ;

СО|v_1)

, в противном случае,

 

 

 

i =

1,

2, ...,

k.

 

 

 

 

При этом если обнаруживается несколько (по і) одинаковых мини­

мальных значений р (Х*+ѵ, ej-1), то можно условиться относить точку Xk+v к эталону с минимальным порядковым номером.

При достаточно большом числе итераций, или при достаточно боль­ ших объемах классифицируемых совокупностей п и при весьма широких ограничениях на природу исследуемых наблюдений, дальнейший пересчет эталонных точек практически не приводит к их изменению, т. е. имеет место сходимость (в определенном смысле) Е<ѵ>к некоторому пределу при ѵ->оо.

Если же в какой-то конкретной задаче исследователь не успел доб­ раться до стадии практически устойчивых (по ѵ) значений эталонных точек, то пользуются одним из двух вспомогательных приемов. Либо «зацикливают» алгоритм, «прогоняя» его после рассматривания послед-

115

ней точки Х п = Х к+(П-к) снова через точку Х ъ затем Х 2, и т. д., либо производят многократное повторение алгоритма, используя в ка­ честве начального эталона Е<°> различные комбинации из k точек ис­ следуемой совокупности и выбирая для дальнейшего наиболее повто­ ряющийся (в некотором смысле) финальный эталон E(n- fe>.

Окончательное разбиение 5 исследуемой совокупности многомерных наблюдений на k классов производится в соответствии с правилом опи­ санного выше минимального дистанционного разбиения S (Е) отно­ сительно центров тяжести (эталонов) Е = которое, кстати, яв­ ляется частным случаем разбиений ранее описанной общей схемы эта­ лонных алгоритмов, получающихся при

т. е.

ф(*. Еі) = Р(Х,

Et),

 

 

 

 

S l (E) = {X:p(X,

Е ')< р(Х, £,);

/== 1, 2,

, k; }ф /}.

Если оказывается, что

р (X, E t) — р (X, Ej), то точку X относят к то­

му из классов Si и Sj, который обладает меньшим порядковым номером. Свойства алгоритма Б2а1. Для описания интересных свойств метода ^-средних введем, следуя [33] и [56], некоторые понятия и опреде­

ления.

Условимся интерпретировать исходное множество наблюдений Х и Х 2, ..., Хп как случайную выборку из п независимых наблюдений, извлеченную из генеральной совокупности, описываемой некоторой (неизвестной нам) вероятностной мерой, определенной в рассматривае­ мом р-мерном факторном пространстве X исследуемых признаков. Под­ робнее о смысле меры Р см. на стр. 14. При этом будем предполагать, что мера Р сосредоточена на замкнутом, ограниченном, выпуклом мно­

жестве X, т. е. §ХР (dX) = 1, причем для каждого открытого множе­

ства AS Р (AS) > 0.

Пусть S = (Sx.......S/;} — некоторое разбиение пространства X на

k непересекающихся множеств Sb

...,

S k, так что теоретико-множест­

венная сумма (объединение) всех этих множеств дает X.

Под k —средним X(S) = (X1(S),

Xa(S), ..., X k(S)), порожденным

разбиением S = {S1, S2, ... , S h}

будем понимать набор векторов

4 l)(S)

 

і = 1,2, ..., k,

X t (S) =

 

х \ р) (S)

каждый из которых является условным средним (центром тяжести)

наблюдений своего класса, т.

е.

 

 

 

I

ХР (dX)

 

(5)

ft_______

(3.30)

 

I

P(dX)

 

 

S;

 

116

В покомпонентной записи формула (3.30) имеет вид

5 *<'> Pt (dxM)

5 Pl(dx(0)

Sil

 

Здесь Sn — проекция р-мерного множества S t на ось

а Р г (dxW)

вероятностная мера на прямой, задающая частное распределение ком­

поненты

в соответствии с законом P(dX),

т.

е.

 

р ,<*«>)= $

$ ...

$

$

...

5

p(dX).

 

х (1)

д.(2)

x ( l - 1) x (l + 1)

 

х (р)

 

Под

S(E) = {S1(E),

3 2 (Е), ...,

S h(Е)}

 

будем подразумевать разбиение, полученное в соответствии с общей схемой эталонных алгоритмов на основании эталонов Е = {£1( £ 2, ...,

Ek) и функции ф(Х, Ег) = р(Х, Ег).

Группа эталонных точек Е = {Ех, Е2......Eh) называется несмещен­ ной &-точкой, если

X[S(E)] = E,

т. е. если центры тяжести классов, построенных с помощью эталонных точек Е ={ Е1, Е2, Eh}, совпадают с самими эталонными точками.

В тех случаях, когда это не вызовет путаницы, будем для упроще­ ния записи обозначать

X [S (Е)] =-- X (Е).

Введем в рассмотрение следующие характеристики внутриклассо­ вого рассеяния, соответствующие разбиению S(E):

Qi(E)=

2

5 Р2(*, Xi(E))P(dX),

 

'■=l s i

Qi(E) =

2

^ Р2(х > ei)p (dX)-

 

г=|і

st

Описанный выше метод ^-средних при довольно широких пред­ положениях относительно вероятностной меры Р обладает следую­ щими свойствами1:

— свойство несмещенности метода ^-средних. Оказывается, что применительно к методу ^-средних имеет место следующий аналог за­

1 Соответствующие доказательства и точную формулировку условий, накла­ дываемых на вероятностную меру Р, читатель может найти в [56].

1 1 7

кона

больших чисел:

 

 

 

 

 

 

 

 

 

 

-----------" ff

S

Р™ Р (*і (£(Ѵ))’

е‘Ѵ>) ^ °

прн Я->00

 

 

 

n - k + l v=0

t=

1

 

 

 

 

 

 

 

 

с вероятностью единица.

 

 

 

 

 

 

 

 

Здесь

Е(ѵ) = {е(Г \

4 Ѵ), . 4 Ѵ)) —эталоны

на ѵ-м

шаге алгоритма,

Â7(E(v)) = X; [S (Е(ѵ))] —условные средние

классов S\v),

получен­

ных

с помощью минимального

дистанционного

разбиения

относи­

 

В

 

 

тельно

 

эталонов

Е(ѵ),

а

Рг-Ѵ) =

 

 

 

= p(lS<v>) — вероятностная мера со­

 

 

 

 

 

 

 

 

ответствующих классов;

 

 

 

 

 

 

 

— свойство

 

стационарности

 

 

 

 

функционала качества

разбиения.

 

 

 

 

Последовательность случайных ве­

 

 

 

 

личин Q1 (Е<ѵ>) сходится

почти

 

 

 

 

всюду и lim Qi (Е<ѵ>) равен

(с

ве-

 

 

 

 

 

 

V -> оо

 

 

 

для не­

 

 

 

 

роятностью единица) Qx (Е)

 

 

 

 

которого разбиения 5 (Е), для ко­

 

 

 

 

торого

X [5 (Е)]

является

несме­

 

 

 

 

щенной ^-точкой.

 

алгоритма

 

 

 

 

Указанное

свойства

 

 

 

 

Б 2а1 означает,

что разбиение,

за­

Рис. 3.5. Пример действия

алгоритма

даваемое

этим

алгоритмом, с рос­

Бгаі:

при неограниченном

увеличении

том объема п исследуемой выборки

выборочной совокупности получаются

стремится к некоторому несмещен­

разбиения с максимальным значением

 

Qi (Е)

 

 

ному разбиению, на котором значе­

 

 

 

 

ние функционала Q*(Е) совпадает

 

 

 

 

со значением функционала Qx (Е).

Очевидно, что Qi(E)

 

Q1 (Е) для любых Е. Кроме того, как указыва­

лось выше (см. стр. 93), минимальное значение функционала Qx (Е) до­ стигается на несмещенных разбиениях. Все это позволяет надеяться, что в достаточно общих ситуациях при больших объемах выборочных совокупностей алгоритм Б 2а1 строит разбиение, близкое к наилучшему в смысле функционала (Д(Е), а следовательно, и в смысле функцио­

нала (Д(Е).

Возможны случаи, когда в результате действия алгоритма Б 2а1 при неограниченном увеличении объема выборочной совокупности будут получаться разбиения, на которых значение функционала Qx (Е) не минимально, а максимально. Рассмотрим следующий пример. Допус­ тим, что исследуемая выборка является выборкой из генеральной сово­ купности, распределение которой сосредоточено в вершинах прямо­ угольника, одна сторона которого несколько больше другой, и зададим­ ся целью разбить исследуемое пространство на два класса. Перенуме­ руем точки генеральной совокупности, в которых сосредоточено рас­ пределение, так как это показано на рис. 3.5. Пусть вероятности появ­ ления каждой из точек 1, 2, 3, 4 одинаковы. Предположим, что при слу-

118

Смотрите также файлы