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

можных попарных расстояний между представителями рассматривае­ мых групп, т. е.

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

Изящное обобщение такого рода, основанное на понятии так на­ зываемого «обобщенного среднего», а точнее —■степенного среднего, было предложено А. Н. Колмогоровым1.

■^ Обобщенное (по Колмогорову) расстояние между классами или

Все излагающиеся ниже определения и результаты, опирающиеся на понятие

прочитанного им на семинаре по математической статистике межфакультетской лаборатории статистических методов МГУ, 27 апреля 1972 г.

83

'Очевидно, также

P(1° (Sh s m) =----Pep (Si, Sm).

Из (3.8) следует, что если S (т, q) = 5 m(jS; группа элементов, полученная путем объединения кластеров S m и S , то обобщенное /(-расстояние между кластерами S, и 5 (т, q) определяется фор­ мулой:

пт [р(*> (Sh Sm))r +n q [pW (Sf, Sg)]r 1r

pW (S „ S ( m , q))

ПтT Я-g

Отметим, что понятие расстояния между группами элементов осо­ бенно важно в так называемых агломеративных иерархических кластер-

процедурах, поскольку принцип работы таких алгоритмов состоит в последовательном объединении элементов, а затем и целых групп сначала самых близких, а потом все более и более отдаленных друг от друга. Подробнее об агломеративных иерархических процедурах см. ниже. Учитывая специфику подобных процедур для задания рас­ стояния между классами оказывается достаточным определить порядок

этими классами. В [55] предлагается следующая общая формула для

Р/ (т, q) = Р (Sx, s (m,q)) = ap,m + ßpz, + ypmg + 6 j pim —p„ |, (3.9)

где а, ß, у и б — числовые коэффициенты, значения которых и опре­ деляют специфику процедуры, ее нацеленность на решение той или

иной экстремальной задачи. Так, например, полагая а = ß = —б = ~

и у — 0, мы, как легко видеть, приходим к расстоянию, измеряемому

по принципу ближайшего соседа. Если же положить а = ß = б = у

и 7 = 0, то расстояние между двумя классами определится как рас­ стояние между двумя самыми далекими элементами этих классов, по принципу дальнего соседа. И наконец, выбор коэффициентов

•соотношения (3.9) по формулам

приводит нас к расстоянию рср между классами, вычисленному как среднее из расстояний между всеми парами элементов, один из которых берется из одного класса, а другой — из другого.

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

84

деляет ее оптимальную критерийную установку, поясняет, например, следующий результат [76]. Оказывается, если для вычисления р/ (т, 9> воспользоваться следующей модификацией формулы (3.9):

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

3. Порог

Под порогом подразумевается обычно то число, с которым сравни­ вается расстояние между объектами (классами) или мера близости объектов для того, чтобы определить, можно ли отнести рассматривае­ мые два объекта (либо объект и класс, либо два класса) к одному об­ щему классу.

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

4. Функционалы качества разбиения на классы. Экстремальная постановка задачи кластер-анализа, связь с теорией статистического оценивания параметров

Естественно попытаться определить сравнительное качество различ­ ных способов разбиения заданной совокупности элементов на классы, т. е. определить тот количественный критерий, следуя которому можно было бы предпочесть одно разбиение другому. С этой целью в поста­ новку задачи кластер-анализа часто вводится понятие так называе­ мого функционала качества разбиения Q (S), определенного на мно­ жестве всех возможных разбиений. Функционалом он называется потому, что чаще всего разбиение S задается, вообще говоря, набором дискриминантных функций бх (X), б2 (X), .... Тогда под наилучшим разбиением S* понимается то разбиение, на котором достигается экстремум выбранного функционала качества. Надо сказать, что выбор того или иного функционала качества, как правило, осуществляется весьма произвольно и опирается скорее на эмпирические и профессио­ нально-интуитивные соображения, чем на какую-либо строгую фор­ мализованную систему.'

85

Мы приведем здесь примеры наиболее распространенных функ­ ционалов качества разбиения и попытаемся обосновать выбор некото­ рых из них в рамках одной из моделей статистического оценивания параметров.

Пусть исследователем уже выбрана метрика р в пространстве X и пусть S = (5!, S 2, ..., S h) некоторое фиксированное разбиение наб­ людений Х г, ■■■, Хп на заданное число k классов S1; S2, S h.

За функционалы качества часто берутся следующие характери­ стики:

— сумма («взвешенная») внутриклассовых дисперсий

весьма широко используется в задачах кластер-анализа в качестве критерийной оценки разбиения [125], [11], [105], [107], [75], [76] и др.;

— сумма попарных внутриклассовых расстояний между элементами

в большинстве ситуаций приводит к тем же наилучшим разбиениям, что и Qx (S), и тоже используется для сравнения кластер-процедур

[70], [45], [7];

— обобщенная внутриклассовая дисперсия Q3 (S) является, как известно [4, с. 2311, одной из характеристик степени рассеивания многомерных наблюдений одного класса (генеральной совокупности) около своего «центра тяжести». Следуя обычным правилам вычисле­

где x(jV)—ѵ-я компонента многомерного наблюдения X t, ал4ѵ>(/)—сред­ нее значение ѵ-й компоненты, подсчитанное по наблюдениям I-го класса.

86