Курс социально-экономической статистики (стр. 172 из 182)

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

Рассмотрим наиболее широко используемые в задачах кластерного анализа расстояния и меры близости.

Обычное евклидово расстояние определяется по формуле

(53.43)

где x_il, х_jl — значения l-го признака у i-го (j-го) объекта (l = 1, 2, ..., k, i,j = 1, 2, .... п).

Оно используется в следующих случаях:

а) наблюдения берутся из генеральной совокупности, имеющей многомерное нормальное распределение с ковариационной матрицей вида σ²E_k, где Е_k — единичная матрица, т.е. исходные признаки взаимно независимы и имеют одну и ту же дисперсию;

б) исходные признаки однородны по физическому смыслу и одинаково важны для классификации.

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

где x_il — значение l-го признака у i-го объекта;

— среднее значение l-го признака;

— среднее квадратическое отклонение l-го признака.

Однако эта операция может привести к нежелательным последствиям. Если кластеры хорошо разделимы по одному признаку и не разделимы по другому, то после нормирования дискриминирующие возможности первого признака будут уменьшены в связи с усилением «шумового» эффекта второго.

«Взвешенное» евклидово расстояние определяется из выражения

(53.44)

Оно применяется в тех случаях, когда каждой l-й компоненте вектора наблюдений Х удается приписать некоторый «вес» ω₁, пропорциональный степени важности признака в задаче классификации. Обычно принимают 0 ≤ ω_l ≤ 1, где l = 1,2, ..., k.

Определение весов, как правило, связано с дополнительными исследованиями, например с организацией опроса экспертов и обработкой их мнений. Определение весов ω_l только по данным выборки может привести к ложным выводам.

Хеммингово расстояние используется как мера различия объектов, задаваемых дихотомическими признаками. Это расстояние определяется по формуле

(53.45)

и равно числу несовпадений значений соответствующих признаков в рассматриваемых i-м и j-м объектах.

Как правило, решение задач классификации многомерных данных предусматривает в качестве предварительного этапа исследования реализацию методов, позволяющих выбрать из k исходных признаков x₁, x₂, ..., x_k сравнительно небольшое число наиболее информативных, т.е. уменьшить размерность наблюдаемого пространства.

В ряде процедур классификации (кластер-процедур) используют понятия расстояния между группами объектов и меры близости двух групп объектов.

Пусть S_i — i-я группа (класс, кластер), состоящая из n_i объектов;

— среднее арифметическое векторных наблюдений группы S_i, т.е. «центр тяжести»;

ρ(S_l, S_m) — расстояние между группами S_l и S_m.

Наиболее употребительными расстояниями и мерами близости между классами объектов являются:

• расстояние, измеряемое по принципу «ближайшего соседа»:

(53.46)

• расстояние, измеряемое по принципу «дальнего соседа»:

(53.47)

• расстояние, измеряемое по «центрам тяжести» групп:

(53.48)

где x_l и x_m — векторы средних соответственно S_l и S_m кластеров;

• расстояние, измеряемое по принципу «средней связи», определяемое как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп:

(53.49)

Академиком А.Н. Колмогоровым было предложено «обобщенное расстояние» между классами, которое включает в себя в качестве частных случаев все рассмотренные выше виды расстояний.

Расстояния между группами элементов — особенно важный параметр в так называемых агломеративных иерархических кластер-процедурах, так как принцип работы таких алгоритмов состоит в последовательном объединении элементов, а затем и целых групп: сначала — самых близких, а впоследствии — все более и более отдаленных друг от друга. При этом расстояние между кластером S_l и кластером S_(m,q), являющимся объединением двух других кластеров — S_m и S_q можно определить по формуле

(53.50)

где ρ_lm = ρ (S_l, S_m); ρ_lq = ρ (S_l, S_q) и ρ_mq = ρ (S_m, S_q) - расстояния между кластерами S_l, S_m и S_q;

α, β, γ и δ — числовые коэффициенты, значения которых определяют специфику процедуры, ее алгоритм.

Например, при α = β = -δ = 1/2 и γ = 0 приходим к расстоянию, построенному по принципу «ближайшего соседа». При α = β = δ = 1/2 и γ = 0 расстояние между классами определяется по принципу «дальнего соседа», т.е. как расстояние между двумя самыми дальними элементами этих классов.

Функционалы качества разбиения

Существует большое количество различных способов разбиения заданной совокупности элементов на классы. Поэтому представляет интерес задача сравнительного анализа качества этих способов разбиения Q(S), определенного на множестве всех возможных разбиений.

Тогда под наилучшим разбиением S* понимаем такое разбиение, при котором достигается экстремум выбранного функционала качества. Следует отметить, что выбор того или иного функционала качества, как правило, опирается на эмпирические соображения.

Рассмотрим наиболее распространенный функционал качества разбиения. Пусть исследователем выбрана метрика ρ в пространстве Х и пусть S = (S₁, S₂,..., S_p) — некоторое фиксированное разбиение наблюдений x₁, ..., x_n на заданное число p классов S₁, S₂, ..., S_p.

За функционал качества берут сумму («взвешенную») внутриклассовых дисперсий

(53.51)

где x_l — вектор средних для l-го кластера.

Иерархические кластер-процедуры

Иерархические (древообразные) процедуры являются наиболее распространенными (в смысле реализации на ЭВМ) алгоритмами кластерного анализа. Они бывают двух типов: агломеративные и дивизимные. В агломеративных процедурах начальным является разбиение, состоящее из п одноэлементных классов, а конечным — состоящее из одного класса; в дивизимных — наоборот.

Принцип работы иерархических агломеративных (дивизимных) процедур состоит в последовательном объединении (разделении) групп элементов, сначала самых близких (далеких), а затем — все более отдаленных (близких) друг от друга. Большинство этих алгоритмов исходит из матрицы расстояний.

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

В качестве примера рассмотрим агломеративный иерархический алгоритм. На первом шаге алгоритма каждое наблюдение x_i (i = 1, 2, ..., п) рассматривается как отдельный кластер. В дальнейшем на каждом шаге работы алгоритма происходит объединение двух самых близких кластеров, и с учетом принятого расстояния по формуле пересчитывается матрица расстояний, размерность которой, очевидно, снижается на единицу. Работа алгоритма заканчивается, когда все наблюдения объединены в один класс.

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

Пример. Классификация стран по уровню жизни населения

В табл. 53.4 представлены значения следующих шести показателей, характеризующих условия жизни населения двадцати стран в 1994 г.: