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

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

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

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

Їx_i - среднее арифметическое векторных наблюдений s_i группы, т.е. "центр тяжести" i-й группы; ρ(s_l,s_m) - расстояние между группами s_l и s_m.

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

- расстояние, измеряемое  по принципу “ближайшего соседа” 

(1.4)

- расстояние, измеряемого  по принципу “дальнего соседа” 

(1.5)

- расстояние, измеряемое  по “центрам тяжести” групп 

(1.6)

- расстояние, измеряемое  по принципу “средней связи”, определяется как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп

(1.7)

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

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

       При этом расстояние между классами s_l и s_(m,q), являющиеся объединением двух других классов s_m и s_q, можно определить по формуле

(1.8)

где ρρ

- расстояния  между классами s_l, s_m и s_q;

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

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

       И, наконец, при 

γ=δ=0

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

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

                                        Квадрат евклидова расстояния.

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

       Манхэттенское расстояние (расстояние городских кварталов), также называемое "хэмминговым" или "сити-блок" расстоянием.

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

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

       Процент несогласия. Это расстояние вычисляется, если данные являются категориальными. 

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

       Когда каждый объект представляет собой отдельный  кластер, расстояния между этими объектами определяются выбранной мерой. Возникает следующий вопрос - как определить расстояния между кластерами?

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

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

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

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

       Метод невзвешенного попарного среднего (метод невзвешенного попарного арифметического среднего - unweighted pair-group method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)).

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

       Метод взвешенного попарного среднего (метод взвешенного попарного арифметического среднего - weighted pair-group method using arithmetic averages, WPGM A (Sneath, Sokal, 1973)). Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере).

       Этот  метод рекомендуется использовать именно при наличии предположения  о кластерах разных размеров.

       Невзвешенный центроидный метод (метод невзвешенного попарного центроидного усреднения - unweighted pair-group method using the centroid average (Sneath and Sokal, 1973)).

       В качестве расстояния между двумя  кластерами в этом методе берется  расстояние между их центрами тяжести.

       Взвешенный  центроидный метод (метод взвешенного попарного центроидного усреднения - weighted pair-group method using the centroid average, WPGMC (Sneath, Sokal 1973)). Этот метод похож на предыдущий, разница состоит в том, что для учета разницы между размерами кластеров (числе объектов в них), используются веса. Этот метод предпочтительно использовать в случаях, если имеются предположения относительно существенных отличий в размерах кластеров. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

           

                     3. Применение кластерного анализа.

    Рассмотрим  некоторые приложения кластерного  анализа.

    Деление стран на группы по уровню развития.

    Изучались 65 стран по 31 показателю (национальный доход на душу населения, доля населения  занятого в промышленности в %, накопления на душу населения, доля населения, занятого в сельском хозяйстве в %, средняя продолжительность жизни, число автомашин на 1 тыс. жителей, численность вооруженных сил на 1 млн. жителей, доля ВВП промышленности в %, доля ВВП сельского хозяйства в %, и т.д.)

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

    Первый  шаг подобного анализа заключается  в выявлении пары народных хозяйств, учтенных в матрице сходства, расстояние между которыми является наименьшим. Это, очевидно, будут наиболее сходные, похожие экономики. В последующем рассмотрении обе эти страны считаются единой группой, единым кластером. Соответственно исходная матрица преобразуется так, что ее элементами становятся расстояния между всеми возможными парами уже не 65, а 64 объектами – 63 экономики и вновь преобразованного кластера – условного объединения двух наиболее похожих стран. Из исходной матрицы сходства выбрасываются строки и столбцы, соответствующие расстояниям от пары стран, вошедших в объедение, до всех остальных, но зато добавляются строка и столбец, содержащие расстояние между кластером, полученным при объединении и прочими странами.

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

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

    Дальнейшие  процедуры аналогичны описанным  выше: на каждом этапе матрица преобразуется  так, что из нее исключаются два  столбца и две строки, содержащие расстояние до объектов (пар стран или объединений – кластеров), сведенных воедино на предыдущей стадии; исключенные строки и столбцы заменяются столбцом  и строкой, содержащими расстояния от новых объединений до остальных объектов; далее в измененной матрице выявляется пара наиболее близких объектов. Анализ продолжается до полного исчерпания матрицы (т. е. до тех пор, пока все страны не окажутся сведенными в одно целое). Обобщенные результаты анализа матрицы можно представить в виде дерева сходства (дендограммы), подобного описанному выше, с той лишь разницей, что дерево сходства, отражающее относительную близость всех рассматриваемых нами 65 стран, много сложнее схемы, в которой фигурирует только пять народных хозяйств. Это дерево в соответствии  с числом сопоставляемых объектов включает 65 уровней. Первый (нижний) уровень содержит точки, соответствующие каждых стране в отдельности. Соединение двух этих точек на втором уровне показывает пару стран, наиболее близких по общему типу народных хозяйств. На третьем уровне отмечается следующее по сходству парное соотношение стран (как уже упоминалось, в таком соотношении может находиться либо новая пара стран, либо новая страна  и уже выявленная пара сходных стран). И так далее до последнего уровня, на котором все изучаемые страны выступают как единая совокупность.

    В результате применения кластерного  анализа были получены следующие  пять групп стран:

    афро-азиатская  группа;

    латино-азиатская  группа;

    латино-среднеземнаморская группа;

    группа  развитых капиталистических стран (без США)

    США

    Введение  новых индикаторов сверх используемого  здесь 31 показателя или замена их другими, естественно, приводят к изменению  результатов классификации стран.

    2. Деление стран по критерию  близости культуры.

    Как известно маркетинг должен учитывать  культуру стран (обычаи, традиции, и т.д.).

    Посредством кластеризации были получены следующие  группы стран:

    арабские;

    ближневосточные;