Расстояние между объектами (кластерами) и меры близости групп объектов

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

Предположим, что наблюдения Xt извлекаются из генеральных совокупностей, имеющих нормальное распределение с одной и той же ковариационной матрицей 2, тогда расстояние между наблюдениями Хг и X, может быть вычислено с помощью метрики (расстояния) Махаланобиса.

Расстояние Махаланобиса

Расстояние Махаланобиса — способ (мера, метрика) нахождения расстояния между объектами в задачах кластерного анализа. Данное расстояние было предложено в 1936 г. индийским статистиком П. Ч. Махаланобисом и рассчитывается по формуле.

(6.1).

где  — вектор-столбец, соответствующий г-му на блюдению; Хц — значение l-то показателя для г-ro наблюдения (объекта); 2 — ковариационная матрица генеральной совокупности, соответствующая^{-мерному} вектору наблюдений Хг Расстояние Махаланобиса за счет ковариационной матрицы 2 учитывает как дисперсии к признаков, так и степень их взаимосвязи. Однако формула (6.1) предполагает, что все k признаков одинаково значимы для результатов классификации. В противном случае используют обобщенное («взвешенное») расстояние Махаланобиса, которое задается формулой.

(6.1).

где Д — симметричная неотрицательно определенная матрица весовых коэффициентов, которая обычно выбирается диагональной.

Отметим, что расстояние Махаланобиса учитывает корреляции между переменными и инвариантно к масштабу. Расстояние Махаланобиса тесно связано с распределением Т2 Хотеллинга (Hotteling’s T-squared distribution) и используется в многомерном статистическом тестировании, а также в линейном дискриминантном анализе.

Следующие три вида расстояний являются частным случаем расстояния Махаланобиса.

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

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

(6.2).

где хц, Xji — величина I-й компоненты у г'-го и j-го объектов (/ = 1,2,…, к, i, j = 1,2 п).

Отмстим, что обычное евклидово расстояние получается из обобщенной метрики Махаланобиса (6. Г) в предположении о том, что:

• а) элементы вектора Х: взаимно независимы и имеют одну и ту же дисперсию а2, т. е. 2 = о2Ек
• б) все показатели одинаково важны для классификации, т. е. Д = Ек-о.

Отсюда с учетом допущений имеем.

В двумерном случае расстояние между двумя объектами X и У может быть найдено по формуле

Использование обычного евклидова расстояния предъявляет определенные требования к исходным данным, поэтому перед его применением необходимо проверить следующие условия:

• • наблюдения берутся из генеральной совокупности с ковариационной матрицей вида о2Ек, т. е. компоненты X взаимно независимы и имеют одну и ту же дисперсию, где Ек — единичная матрица &-го порядка (отметим, что взаимная независимость признаков предполагает отсутствие мультиколлинеарности признаков);
• • компоненты вектора наблюдений X однородны по физическому смыслу и одинаково важны для классификации;
• • признаковое пространство совпадает с геометрическим пространством.

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

где хи — значение /-го признака у г-го объекта; X/ — среднее значение /-го признака; - среднее квадратическое отклонение /-го признака.

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

Взвешенное евклидово расстояние

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

где  — расстояние между г-м и j-м объектами.

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

Взвешенное евклидово расстояние получается из метрики Махаланобиса в предположении, что элементы х" вектора наблюдений X, взаимно независимы и их дисперсии равны, т. е. матрица Z диагональная. Часто веса Wj выбираются пропорционально величине среднего квадратического отклонения sj признака Xj либо обратной величине 1 /&.

Хеммингово расстояние

Хеммингово, или манхэттенское, расстояние (расстояние городских кварталов), или сити-блок-расстояние, рассчитывается как среднее разностей по координатам:

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

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

Расстояние Чебышева

Расстоянием Чебышева между «-мерными числовыми векторами называется максимум модуля разности компонент этих векторов:

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

Расстояния между группами объектов и меры близости двух групп объектов

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

Введем обозначения. Пусть S) — t-я группа (класс, кластер), состоящая из пi объектов; х{ - вектор средних арифметических значений для группы 5), т. е. «центр тяжести» й группы; ¢/(6), 5,") — расстояние между группами (кластерами) 6) и 6,".

Наиболее часто для вычисления расстояния между классами объектов (кластерами) используют следующие виды расстояний.

1. Расстояние, измеряемое по методу «ближнего соседа» :

(6.3).

Стоит отметить устойчивость данного метода к появлению аномальных наблюдений или выбросов.

2. Расстояние, измеряемое по методу «дальнего соседа» , или метод максимального локального расстояния (Мак Нотой — Смит):

(6.4).

3. Расстояние, измеряемое по «центрам тяжести» групп (расстояние Сокала и Миченера):

(6.5).

4. Расстояние, измеряемое по методу «средней связи» (расстояние Соренсена), определяется как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп:

(6.6).

5. Расстояние, измеряемое по методу Варда (J. Н. Ward).

Этот метод отличается от всех других методов, поскольку он использует дисперсионный анализ для оценки расстояний между кластерами. Метод минимизирует сумму квадратов (55) расстояний для любых двух (гипотетических) кластеров, которые могут быть сформированы на каждом шаге.

Помимо перечисленных расстояний, широко используемых на практике в силу их легкой интерпретации и формализации в пакетах статистических программ (таких как, например, SPSS, STATISTICA и др.), разработаны и могут быть использованы и другие расстояния. Среди них:

• • метод групповых средних Ланса и Уильямса (G. N. Lance, W. Т. Williams);
• • двухгрупповой метод Миченера и Сокала (С. D. Michener, R. R. Sokal);
• • метод Болла и Холла (G. Н. Ball, D. J. Hall);
• • методы Боннера и Хивсринена (R. Е. Bonner, L. Hyvarinen);
• • метод Мак-Куина (J. В. MacQueen);
• • метод Себестьена (G. Sebestyen) и др.

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

При этом расстояние между классами 5/ и 5(," q), являющееся объединением двух других классов 5″, и Sq, можно определить по формуле.

(6.7).

где  — попарные расстояния между классами 5/, 5," и 5(/; а, (3, 8 и у — числовые коэффициенты, значения которых определяют специфику процедуры, ее алгоритм.

Например, при, а = (3 = -8 = ½ и у = 0 приходим к расстоянию, построенному по методу «ближнего соседа», при, а = (3 = 8 = ½ и у = 0 — к расстоянию по принципу «дальнего соседа», т. е. расстоянию между двумя самыми дальними элементами этих классов. И наконец, при.

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

Имеются некоторые рекомендации практического плана по выбору алгоритма кластеризации, полученные на основе экспериментального сравнения различных методов [32]:

• • метод «ближнего соседа» наиболее устойчив к выбросам (аномальным наблюдениям);
• • метод «средней связи» эффективен, когда объекты формируют различные «рощи», однако он работает хорошо и в случаях протяженных (цепочного типа) кластеров;
• • метод «дальнего соседа» непригоден, если кластеры имеют удлиненную форму или их естественный тип является цепочным;
• • метод Варда в целом является эффективным, однако он ориентирован на создание кластеров малого размера. Данный метод наиболее устойчив к «зашумлению» данных, когда имеются данные с трудно различимыми состояниями.

Отметим некоторые недостатки, присущие кластерному анализу:

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