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

 

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

В общем случае понятие однородности объектов задается введением либо правила вычисления расстояний ρ(x_i, х_j) между любой парой исследуемых объектов (x₁, x₂,...,x_n), либо некоторой функцией r(х_i, x_j), характеризующей степень близости i -го и j -го объектов.

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

Аналогично используется и мера близости r (x_i, х_j), при задании которой мы должны помнить о необходимости выполнения следующих условий: симметрии r (x_i, х_j) = r(x_j, х_i); максимального сходства объекта с самим собой r (x_i, х_i) = r (x_i, х_j), 1 ≤ i, j ≤ п, и монотонного убывания r (x_i, х_j) по мере увеличения ρ (x_i, х_j), т.е. из ρ (x_k, х_l) ≥ ρ (x_i, х_j) должно следовать неравенство r (x_k, х_l) ≤ ρ (x_i, х_j).

Выбор метрики, или меры близости, является узловым моментом исследования, от которого в значительной степени зависит окончательный вариант разбиения объектов на классы при данном алгоритме разбиения. В каждом конкретном случае этот выбор должен производиться по-своему, в зависимости от целей исследования, физической и статистической природы наблюдений, априорных сведений о характере вероятностного распределения 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 расстояние между классами определяется по принципу «дальнего соседа», т.е. как расстояние между двумя самыми дальними элементами этих классов.