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

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

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

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

Добавлен: 21.10.2024

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

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

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

Естественно точку X j отнести к классу

1, если Р (1 | X j ) >

Р (2 [ X j ) .

Это означает, что Р (1 | X j )

>

1/2. Отсюда следует, что X j

будет от­

несена к классу 1, если

 

+

ß ■< 0,

или к классу 2, если a'Xj +

+ ß Д> 0. Следовательно,

а Х

+

ß = 0

будет оценкой, разделяющей

поверхности классов 1 и 2, а а и ß — оценками параметров разделяю­ щей поверхности (см. § 2 главы I).

Основные трудности этого метода классификации состоят в том, что скорость сходимости итерационного процесса зависит от расстоя­ ния Махаланобиса р (аъ а2) между классами и от начальных значений. Более того, может быть несколько локальных максимумов и требуется, изменяя начальные данные, определить абсолютный максимум. Грубо

говоря, итеративный процесс сходится к абсолютному максимуму а ,

ß (при k = 2), из точек а (0), ß (0), если угол между а и а (0) менее 45°. Это ясно показывает возрастание трудностей при росте размер­ ности. Если точка а (0) выбрана случайно, то вероятность выполнения

этого

условия

при

р =

5

равна 0,076,

при

р = 10 — 0,01, при

р =

15— 0,001,

при

р =

20 — 0,0002 [3]. Поэтому при больших раз­

мерностях наблюдений >

10) требуется

эту

размерность снизить

(например, методом главных компонент; см. ниже, главу

IV).

П р и м е р

неограниченной функции правдоподобия.

Рассмотрим

простейший случай, когда число классов k = 2 и наблюдаемые ве­

личины X j

(/ = 1, 2, ..., п )

являются одномерными ( р = 1). Плотность

распределения

 

 

 

 

 

 

 

 

 

 

h {U1я г, аи о;) = h (U) =

1

e

9а2

+

 

 

 

 

ях ———

1

 

 

 

 

 

 

 

y2n ax

 

 

 

 

 

 

 

 

 

(С/-а,)а

 

 

 

 

 

 

 

I

1

 

2(Jo

 

 

 

 

 

 

 

+

--------- e

2

 

 

 

 

 

 

 

 

V * i o 2

 

 

 

 

 

 

где я ь

я 2, au a2, оъ o2 являются

неизвестными параметрами (ях -f

+ я 2 =

1).

 

 

 

 

 

 

 

 

В этом случае функция правдоподобия

 

 

 

 

 

 

 

п h (Xj) :

L ( я х, я 2, üx, ß2,

ох,

02).

 

 

 

 

 

i =i

 

 

 

 

 

 

 

Рассмотрим поведение h (U) как функции от Ѳ = (яг,

аІУог). Если

йі Ф Xj,

то h (X,-1 я ^ а ,)

является ограниченной функцией, так как

 

 

 

 

(x j ~ ai)2

 

 

 

 

 

 

 

 

 

я.

2of

<

 

■е—1/2

 

 

 

 

 

 

 

 

 

 

Уг2л а.

 

 

Ѵ2л\ Xj-йі

 

 

 

ДЛЯ

любых я г И ( J ; . ЕСЛИ

Ж е Я ; >

 

0 и Ö; =

X j ,

ТО h ( Ѵ х | я ъ

Я 2, X j ,

а2,

аи (т2)

стремится к бесконечности как (l/o-J

при огх

0.

Однако,

73


учитывая конечность предела h

(Х;)

при

I Ф j

 

 

 

 

 

 

 

 

(■хі~Ч)г

 

lim h (Xl I я 1; я 2,

Xj,

а2,

а 1;

сг2)

- Д — е

2ff2

,

°1^°

 

 

 

 

Ѵ2ЛСТ2

 

 

получаем, что при ах =

и

-> 0, функция L (я1( я 2, Xj,

а2, оъ а 2)

стремится к бесконечности как

l/оу для

любого ях Ф 1 и любых а2

и о2, чего не происходит при о2 = аь так как при а 2 = ах = а

HitiL(k1, я2, Xj, аг, о, о) 0.

Таким образом, любой

набор я х, я 2, ах = Xj, а2, ах = 0, ст2 > 0,

я х + я 2 = 1 и 0 < ях <

1 обращает в бесконечность функцию прав­

доподобия.

 

Обобщение примера на многомерные смеси нормальных классов не представляет труда. Для этого достаточно рассмотреть случай, когда компоненты наблюдений Xj какого-либо класса і линейно зависимы, т. е. | 2 | -> 0 при at = Xj.

Пример показывает, что возможны ситуации, когда не выполня­ ются условия теоремы 2 (п. 1 § 3) — условия сходимости итерацион­ ной процедуры для получения оценок максимального правдо­ подобия.


Г л а в a III ^

КЛАССИФИКАЦИЯ БЕЗ ОБУЧЕНИЯ. НЕПАРАМЕТРИЧЕСКИЙ СЛУЧАЙ:-— ■---- -

МЕТОДЫ КЛАСТЕР-АНАЛИЗА, ТАКСОНОМИЯ

§ 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

В этой части работы рассматривается следующая задача. Совокупность исследуемых объектов, каждый из которых задан

многомерным наблюдением, т. е. набором из р замеренных на нем признаков X, требуется разбить на однородные в некотором смысле группы. Так же, как и в главе II, мы не располагаем здесь обучаю­ щими выборками. Более того, в отличие от главы II в данном случае практически отсутствует и априорная информация о характере рас­ пределения измерений X внутри классов (если не считать самых общих предположений, относящихся либо к компактности или ограничен­ ности диапазона изменений компонент вектора X, либо к свойствам непрерывности и гладкости соответствующих законов распределе­ ния). Полученные в результате разбиения группы обычно называются кластерами (таксонами, образами)1, методы их нахождения — кластер-анализом (соответственно численной таксономией или распоз­ наванием образов с самообучением).

При этом исследователь с самого начала должен четко представ­ лять, какую из двух задач классификации он решает. Решает ли он обычную задачу типизации, при которой исследуемую совокупность элементов (наблюдений) следует разбить на сравнительно небольшое число областей группирования (аналоги интервалов группирования при обработке одномерных наблюдений) так, чтобы элементы одной такой области лежали друг от друга по возможности на небольшом расстоянии. Либо он пытается определить естественное расслоение исходных наблюдений на четко выраженные кластеры, лежащие друг от друга на некотором расстоянии, но не разбивающиеся на столь же удаленные друг от друга части.

1 Cluster (англ.) — скопление, группа элементов, характеризуемых какимлибо общим свойством. Taxon (англ.) — систематизированная группа любой ка­ тегории.

75

Заметим сразу, что если первая задача, задача типизации, всегда имеет решение, то при второй постановке результат может быть отри­ цательным: может оказаться, что множество исходных наблюдений не обнаруживает естественного расслоения на кластеры, например образует один кластер.

В некоторых случаях исследуемые наблюдения Хь ..., Х п нам бу­ дет удобно интерпретировать в качестве выборки из р-мерной гене­ ральной совокупности, определяемой, как правило, неизвестной нам вероятностной мерой Р, задание которой, как известно (см. § 1 главы I), равносильно заданию определенного правила однозначного сопостав­

ления

каждой, представляющей

практический интерес подобласти

AS из исследуемого факторного пространства X некоторого неотри­

цательного, действительного,

не

превосходящего

единицы

числа

Р (AS),

являющегося мерой

достоверности события

{XgAS},

т. е.

события, заключающегося в том, что случайно извлеченное из гене­ ральной совокупности наблюдение окажется принадлежащим именно заданной подобласти AS1. Тогда задача классификации заключается в разбиении факторного пространства X на какое-то число непересекающихся областей. Для упрощения дальнейших обозначений будем называть такую схему вероятностной модификацией задачи кластеранализа. Заметим, что эта модификация используется, как правило, лишь при исследовании свойств различных процедур.

Необходимость разбиений совокупности объектов на однородные группы часто возникает как в социально-экономических исследова­ ниях (см. «Введение» и главу V настоящей работы, а также [25], [24], [26], [75], [18]), так и в научно-технических, приводимых в биоло­ гии [8], [62], [71], палеонтологии, геологии и географии [11], [46], медицине [44], почвоведении [65], документалистике [60], [61], метеоро­ логии [29].

1.Расстояния между отдельными объектами

имеры близости объектов

Наиболее трудным и наименее формализованным в данной задаче является пункт, связанный с определением понятия однородности объектов.

В общем случае понятие однородности объектов задается либо введением правила вычислений расстояния р (X*, Xj) между любой парой объектов исследуемого множества {Хь Х2, ..., Х п}, либо

1 Для сравнительно широкого класса так называемых непрерывных случай­ ных величин задание вероятностной меры Р может быть осуществлено с помощью

некоторой специальной функции f (іА1*, .... tAp'), называемой функцией плот­ ности распределения от р переменных, где р — размерность исследуемого при­ знака X. В этом случае при заданном AS вероятность р (AS) подсчитывается по формуле

Р (AS )= J f (гА!\ ... , и^р^)du^lK ... , du(рК

AS

.76


заданием некоторой функции г (Хь Xj), характеризующей степень близости (сходства, подобия) объектов с номерами і и /. Если задана функция р (Xi,Xj), то близкие в смысле этой метрики объекты счита­ ются однородными, принадлежащими к одному классу. Естественно, при этом необходимо сопоставление р (Хг, Х7-) с некоторым пороговым значением, определяемым в каждом конкретном случае по-своему.

Аналогично используется для формирования однородных классов и упомянутая выше мера близости г (Xiy Xj), при задании которой мы должны помнить о необходимости соблюдения следующих естествен­

ных требований: требования симметрии

(Xiy

Xj) =

г (Xj,

Хг));

требования максимального сходства

объекта с

самим

собой

(г (Хіу

Х і) = шах г (Xj, Xj))

и требования при заданной метрике монотонно-

1</

по р (Хь Xj),

т. е.

из р (Xh, X t) > р (ХІУXj)

го убывания г (Xit Xj)

должно с необходимостью следовать выполнение неравенства г (Хь, Xj) < г (Xj, Xj).

Конечно, выбор метрики (или меры близости) является узловым моментом исследования, от которого решающим образом 'зависит окончательный вариант разбиения объектов на классы при заданном алгоритме разбиения. В каждой конкретной задаче этот выбор должен производиться по-своему. При этом решение данного вопроса зависит в основном от главных целей исследования, физической и статисти­ ческой природы вектора наблюдений X, полноты априорных сведений о характере вероятностного распределения X. Так, например, если из конечных целей исследования и из природы вектора X следует, что понятие однородной группы естественно интерпретировать как генеральную совокупность с одновершинной плотностью (полигоном частот) распределения и если, к тому же, известен общий вид этой плотности, то естественно воспользоваться общим подходом, описан­ ным в главе II настоящей работы. Кстати, если известно, что наблю­ дения X извлекаются из нормальных генеральных совокупностей с одной и той же матрицей ковариаций, то естественной мерой отда­ ленности двух объектов друг от друга является, как видели в § 4 гла­ вы I, так называемое расстояние Махаланобиса.

В качестве примеров расстояний и мер близости, сравнительно широко используемых в задачах кластер-анализа, приведем здесь следующие:

общий вид метрики махаланобисского типа.

В общем случае зависимых компонент х<2>, ..., х ^ вектора наб­ людений X и их различной значимости в решении вопроса об отнесе­ нии объекта (наблюдения) к тому или иномуч классу обычно пользу­ ются обобщенным («взвешенным») расстоянием махаланобисского

типа, задаваемым формулой

 

Po (Xj, X,) / IX j -

Xjу Л' Я-* А (Xj - Xj) .

Здесь Б — ковариационная

матрица генеральной совокупности,

из которой извлекаются наблюдения Х ІУ а Л — некоторая симметрич­ ная неотрицательно-определенная матрица «весовых» коэффициентов Я, которая чаще всего выбирается диагональной [38], [57].

77