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

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

Бог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⁽ⁱ⁾ = (х_i1 ,x_i2 , ...,х_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 – количество выделенных кластеров.

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

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