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

Богданов, А. И.

Бог73 Эконометрика (продвинутый уровень): учеб. пособие. – СПб.: СПГУТД, 2015. – 80 с.

ISBN

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

Учебное пособие предназначено для изучения магистрантами экономических специальностей дисциплины «Эконометрика (продвинутый уровень)».

ИПЦ СПГУТД, 2015

Богданов А. И., 2015

ISBN

ВВЕДЕНИЕ

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

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

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

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

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

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

1. МНОГОМЕРНЫЕ РАСПРЕДЕЛЕНИЯ

1.1. Многомерная нормально распределенная генеральная совокупность

При рассмотрении различных моделей статистического анализа часто предполагается нормальное распределение всех или некоторых признаков генеральной совокупности. Говорят, что непрерывная k-мерная случайная величина распределена нормально, если плотность распределения имеет вид

(x-μ (1.1)

где µ=(µ₁, µ₂, …,µ_k)^T– k -мерный вектор математических ожиданий;

Σ^-1 –матрица, обратная ковариационной матрице Σ размерности k*k;

– определитель ковариационной матрицы Σ.

Известно, что матрица Σ является симметрической.

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

Пример

Покажем, что при k =\ имеет место одномерный нормальный закон распределения. В самом деле, при k =1 Σ = = σ². Тогда |Σ| = σ², а обратная матрица . Подставив найденные значения в выражение (1.1), получим

Мы получили плотность распределения одномерного нормального закона, зависящего от двух параметров: математического ожидания μ и среднего квадратичного отклонения σ.

Плотность двумерного нормального закона распределения определяется пятью параметрами: математическими ожиданиями и случайных величин и X₂, их средними квадратичными отклонениями , и коэффициентом корреляцииr.

1.2. Выборка из многомерной генеральной совокупности

Выборкой из генеральной совокупности (X) называют результаты ограниченного ряда наблюдений x₁,,х₂,...,х_n где п – объем выборки.

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

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

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

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

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

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

• генеральная совокупность настолько многочисленна, что проведение обследования всех элементов совокупности (сплошное обследование) слишком трудоемко. С такой ситуацией приходится встречаться при контроле качества продукции крупносерийного и массового производства;

• в процессе проведения испытания происходит разрушение отбираемых образцов (например, испытание срока службы изделия, предела прочности и т. д.);

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

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

В математической статистике существуют два взгляда на выборку. С одной стороны (практической), х₁,х₂,...,х_п есть п наблюденных значений случайной величины X, т. е. конкретные числа или векторы. С другой стороны, это п независимых наблюдений, каждое из которых имеет один и тот же закон распределения. Отсюда следует, что последовательность наблюдений можно представить как п независимых случайных величин X₁, X₂, …, X_n с одинаковой плотностью распределения вероятностей f(х) (если X – непрерывная величина) или набором вероятностей (если X – дискретна). Такая выборка называется случайной и представляет собой n-мерную случайную величину (X₁,х₂,..., хn) с плотностью распределения вероятностей

В этом случае говорят, что выборка взята из генеральной совокупности X с законом распределения f (х).

Статистикой (выборочной характеристикой) называют функцию, зависящую только от результатов наблюдения х₁,,х₂,...,х_п:

Отсюда следует, что статистика представляет собой случайную величину с законом распределения, определяемым законом распределения величины X.

Выборка объема п из многомерной генеральной совокупности X, имеющей функцию распределения

F(x) = F(x₁,x₂,...,x_i,...,x_k),

называется nk -мерной случайной величиной.

Из определения следует:

1) каждая наблюдаемая k -мерная точка

x⁽ⁱ⁾ = (х_i₁,x_i₂,...,х_ik)

является случайной величиной, распределенной так же, как и генеральная совокупность;

2) наблюдаемые точки х⁽ⁱ⁾ представляют собой независимые случайные величины.

2. КЛАСТЕРНЫЙ АНАЛИЗ

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

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

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

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

Различия между схемами решения задач классификации во многом определяются тем, что понимают под понятиями "сходство" и "степень сходства".

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

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

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

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

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

Рассмотрим формы представления исходных данных и определение мер близости.

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

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

Числовые значения, входящие в матрицу X, могут соответствовать трем типам переменных: количественным, ранговым и качественным.

Желательно, чтобы таблица исходных данных соответствовала одному типу переменных. В противном случае разные типы переменных стараются свести к какому-то одному типу переменных.

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

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

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

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

Относительно просто определяется близость между признаками. В этом случае мерами близости служат различные статистические коэффициенты связи.

Если признаки количественные, то можно использовать оценки обычных парных выборочных коэффициентов корреляции r_ij, i,j=1,2,...,k. Однако коэффициент корреляции измеряет только линейную связь, поэтому если связь не линейна, то следует использовать корреляционное отношение.

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

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

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

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

Аналогично используется имера близости r (Х_i, Х_j), при задании которой надо помнить о необходимости выполнения условий симметрии r(X _i,X_j)=r(X _j,X_i), максимального сходства объекта с самим собой r(X _i,X_i)=mах r (Х_i, Х_j), при 1 < j < п и монотонного убывания r (Х_i, Х_j) по р (Х_i, Х_j), т. е. из р (X_k,X_l)> р (Х_i, Х_j) должно следовать неравенство r (X_k,X_l)< r (Х_i, Х_j).

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

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

Расстояние Махаланобиса (общий вид)

В случае зависимых компонент x₁,x₂,...x_k вектора наблюдений X и их различной значимости в решении вопроса классификации обычно используют обобщенное (взвешенное) расстояние Махаланобиса, задаваемое формулой

где Σ – ковариационная матрица генеральной совокупности, из которой извлекаются наблюдения;

𝛬 – некоторая симметрическая матрица "весовых" коэффициентов, которая чаще всего выбирается диагональной.

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

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

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

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

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

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

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

,

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

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

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

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

В качестве меры расстояния между объектами можно использовать взвешенное евклидово расстояние, когда каждой компоненте x_l вектора наблюдений X удается приписать некоторый "вес" w_l, пропорциональный степени важности показателя в задаче классификации.

(2.4)

где s_l² – выборочная дисперсия значений l- го признака, которая определяется по формуле

(2.5)

Обычно принимают 0< w_l <1, где l =1,2,.., к.

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

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

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

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

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

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

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

Пусть S_i – i -я группа (класс, кластер), состоящая из n_i объектов; – среднее арифметическое векторных наблюдений S_i группы, т. е. "центр тяжести" i -й группы;

d(S_l,S_m) – расстояние между группами S_l и S_m.

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

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

;(2.7)

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

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

(2.9)

где – центры кластеров S_l и S_m;

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

где – количество объектов в кластере ;

– количество объектов в кластере .

2.4. Функционалы качества разбиения

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

Наилучшее разбиение S* представляет собой такое разбиение, при котором достигается экстремум выбранного функционала качества. Следует отметить, что выбор того или иного функционала качества разбиения, как правило, опирается на эмпирические соображения.

Рассмотрим некоторые наиболее распространенные функционалы качества разбиения. Пусть исследователем выбрана метрика 𝛒 в пространстве X и S = (S₁,S₂,...,S_k) некоторое фиксированное разбиение наблюдений Х₁,Х₂,...,Х_n на заданное число k классов S_1,S₂,...,S_k.

Существуют следующие функционалы качества:

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

(2.11)

где k – количество выделенных кластеров.

• сумма попарных внутриклассовых расстояний между элементами.

Последний критерий минимизирует сумму квадратов расстояний между объектами одного кластера.