Кластерный подход в управлении экономическими системами

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

   Рассмотрим  следующую задачу. Пусть исследуется  совокупность n объектов, каждый из которых  характеризуется по k замеренным на нем признакам Х. Требуется разбить эту совокупность на однородные в некотором смысле группы (классы).

   При этом практически отсутствует априорная  информация о характере распределения  измерений Х внутри классов.

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

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

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

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

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

   Обычной формой представления исходных данных в задачах кластерного анализа  служит прямоугольная таблица: 

                             (1)

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

   Матрица Х не является единственным способом представления данных в задачах  кластерного анализа. Иногда исходная информация задана в виде квадратной матрицы

   R=(r_ij), i,j=1, 2, ..., n,

   элемент r_ij который определяет степень близости i-го объекта к j-му.

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

   Относительно  проще решается вопрос об определении  близости между признаками. Как правило, кластерный анализ признаков преследует те же цели, что и факторный анализ – выделение групп связанных  между собой признаков, отражающих определенную сторону изучаемых  объектов. Мерами близости в этом случае служат различные статистические коэффициенты связи, например /r_mj/, mj =1, 2, ...,к. Элемент r_mj определяет степень близости m-го признака к j-му.

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

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

   В общем случае понятие однородности объектов задается либо введением правила  вычисления расстояний ρ(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); максимального сходства объекта с самим собой , при 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. Обычное Евклидово расстояние

                                   (2)

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

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

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

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

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

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

                                         (3)

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

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

           (4)

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

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

2. «Взвешенное» Евклидово пространство

           (5)

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

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

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

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

                                   (6)

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

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

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

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

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

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

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

     – среднее арифметическое векторных  наблюдений si группы, т.е. "центр тяжести" i-й группы;

   ρ (s_l ,s_m) – расстояние между группами s_l и s_m.

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

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

                       (7)

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

                       (8)

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

                        (9)

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

                  (10)

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

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

   При этом расстояние между классами и , являющиеся объединением двух других классов S_m и S_q, можно определить по формуле        (11)

   где       

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

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

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

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

     ; ,    

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

   Рассмотрим  некоторые методы кластерного анализа

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