Кластерный анализ. Расстояние между объектами. Расстояние между кластерами

    Задача  кластерного анализа заключается  в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными.

    Например, пусть G включает n стран, любая из которых характеризуется ВНП на душу населения (F1), числом М автомашин на 1 тысячу человек (F2), душевым потреблением электроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 - для второй, Х3 для третьей, и т.д. Задача заключается в том, чтобы разбить страны по уровню развития.

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

    

    где xj - представляет собой измерения j-го объекта.

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

    Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Хi и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Хi и Хj из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d(Хi , Хj) называется функцией расстояния (метрикой), если:

    а) d(Хi , Хj) ³ 0, для всех Хi и Хj из Ер

    б) d(Хi, Хj) = 0, тогда и только тогда, когда Хi = Хj

    в) d(Хi, Хj) = d(Хj, Хi)

    г) d(Хi, Хj) £ d(Хi, Хk) + d(Хk, Хj), где Хj; Хi и Хk - любые три вектора из Ер.

    Значение  d(Хi, Хj) для Хi и Хj называется расстоянием между Хi и Хj и эквивалентно расстоянию между Gi и Gj соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).

    Наиболее  часто употребляются следующие  функции расстояний:

    1. Евклидово расстояние   d2(Хi , Хj) =

    2. l1 - норма    d1(Хi , Хj) =

    3. Сюпремум - норма   d¥ (Хi , Хj) = sup

    k = 1, 2, ..., р

    4. lp - норма    dр(Хi , Хj) =

    Евклидова метрика является наиболее популярной. Метрика l1 наиболее легкая для вычислений. Сюпремум-норма легко считается и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3,.

    Пусть n измерений Х1, Х2,..., Хn представлены в виде матрицы данных размером p ´ n:

    

    Тогда расстояние между парами векторов d(Хi , Хj) могут быть представлены в виде симметричной матрицы расстояний:

    

    Понятием, противоположным расстоянию, является понятие сходства между объектами  Gi. и Gj. Неотрицательная вещественная функция S(Хi ; Хj) = Sij  называется мерой сходства, если :

    1) 0£ S(Хi , Хj)<1 для Хi ¹ Хj

    2) S(Хi , Хi) = 1

    3) S(Хi , Хj) = S(Хj , Хi)

    Пары  значений мер сходства можно объединить в матрицу сходства:

    

    Величину  Sij называют коэффициентом сходства.  

1.3. Методы  кластерного анализа.

    Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).

    Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Хi и Хj определяется по формуле:

    

    1) Метод полных связей.

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

    2) Метод максимального локального расстояния.

    Каждый  объект рассматривается как одноточечный кластер. Объекты группируются по следующему правилу: два кластера объединяются, если максимальное расстояние между  точками одного кластера и точками  другого минимально. Процедура состоит из n - 1 шагов и результатом являются разбиения, которые совпадают со всевозможными разбиениями в предыдущем методе для любых пороговых значений.

    3) Метод Ворда.

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

    4) Центроидный метод.

    Расстояние  между двумя кластерами определяется как евклидово расстояние между  центрами (средними) этих кластеров:

    d2 ij  =  (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, имеющие минимальное значение d2ij Если n1 много больше  n2,  то центры объединения двух кластеров близки друг к другу и характеристики  второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Расстояние  между объектами. Расстояние между кластерами.

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

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

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

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

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

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

(1.1)

где х_ie,, x_je - величина е-ой компоненты у i-го (j-го) объекта (е=1,2,...,к, i,j=1,2,...,n)

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

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

б) компоненты вектора  наблюдений Х однородны по физическому  смыслу и одинаково важны для  классификации;

в) признаковое  пространство совпадает с геометрическим пространством.

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

  где - значение e-го признака у i-го объекта

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

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

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

“Взвешенное”  Евклидово пространство

(1.2)

применяется в  тех случаях, когда каждой компоненте x_l вектора наблюдений X удается приписать некоторый “вес” ω_l, пропорционально степени важности признака в задаче классификации. Обычно принимают 0≤ω_e≤1, где e=1,2,...k.

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

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

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

(1.3)

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

       В некоторых задачах классификации  объектов в качестве меры близости объектов можно использовать некоторые  физические содержательные параметры, так или иначе характеризующие  взаимоотношения между объектами. Например, задачу классификации отраслей народного хозяйства с целью агрегирования решают на основе матрицы межотраслевого баланса [1].

       В данной задаче объектом классификации  является отрасль народного хозяйства, а матрица межотраслевого баланса  представлена элементами s_ij, характеризующими сумму годовых поставок i-ой отрасли в j-ю в денежном выражении. В качестве меры близости {r_ij} принимают симметризованную нормированную матрицу межотраслевого баланса. С целью нормирования денежное выражение поставок i-ой отрасли в j-ю заменяют долей этих поставок по отношению ко всем поставкам i-ой отрасли. Симметризацию же нормированной матрицы межотраслевого баланса можно проводить, выразив близость между i-й и j-й отраслями через среднее значение из взаимных поставок, так что в этом случае r_ij=r_ji.