Кластерный анализ с применением самоорганизующихся карт Кохонена

Размещено на http://www.allbest.ru/

Курсовая работа на тему:

«Кластерный анализ с применением

самоорганизующихся карт Кохонена»



Содержание

Кластерный анализ и его применение

Сети и карты Кохонена

Сети Кохонена

Карты Кохонена

Кластерный анализ с применением карт Кохонена основных социально-экономических показателей административных районов Ставропольского края

Список литературы



Кластерный анализ и его применение

анализ кластерный край ставропольский

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

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

Кластерный анализ - это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как «сгустков» этих точек (кластеров, таксонов). «Кластер» (cluster) в английском языке означает «сгусток», «гроздь винограда», «скопление звезд» и т.д. Данный метод исследования получил развитие в последние годы в связи с возможностью компьютерной обработки больших баз данных.

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

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

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

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

Задача кластерного анализа.

Кластерный анализ выполняет следующие основные задачи:

Разработка типологии или классификации.

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

Порождение гипотез на основе исследования данных.

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

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

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

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

Вычисление значений той или иной меры сходства (или различия) между объектами.

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

Проверка достоверности результатов кластерного решения.

Можно встретить описание двух фундаментальных требований предъявляемых к данным -- однородность и полнота. Однородность требует, чтобы все кластеризуемые сущности были одной природы, описываться сходным набором характеристик. Если кластерному анализу предшествует факторный анализ, то выборка не нуждается в «ремонте» -- изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство -- z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.

Пусть множество I={I1,I2,…,In} обозначает n объектов. Результат измерения i-й характеристики Ij объекта обозначают символом xij, а вектор Xj=[xij] отвечает каждому ряду измерений (для j-го объекта). Таким образом, для множества I объектов исследователь располагает множеством векторов измерений X={X1, X2,…,Xn}, которые описывают множество I. Множество X может быть представлено как n точек в p-мерном евклидовом пространстве Ер.

Пусть m - целое число, меньшее чем n. Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов I на m кластеров (подмножеств) р1,р2,…, рm так, чтобы каждый объект Ij принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие разным кластерам, были разнородными (несходными).

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

Основные понятия кластерного анализа

N измерений X1, X2,…,Xn могут быть представлены в виде матрицы

(1)

Аналогичным образом расстояния между парами векторов d(Xi,Xj) могут быть представлены в виде матрицы расстояний:

(2)

dii=0 для i=1,2,…,n.

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

(3)

Понятием, противоположным понятию расстояния между объектами Xi и Xj, является понятие близости (сходства) между Xi и Xj. Точнее, мера близости между объектами Xi и Xj - это вещественная функция м(Xi,Xj)=мij со свойствами:

0?м(Xi,Xj)<1 для Xi?Xj;

м(Xi,Xi)=1;

м(Xi,Xj)=м(Xj,Xi)

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

(4)

Величину мij называют коэффициентом близости. Примером линейной близости является коэффициент корреляции.

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

Метрики для количественных шкал (расстояние).

а) Линейное расстояние:

(5)

б) евклидово расстояние:

(6)

в) обобщенное степенное расстояние Минковского (универсальная метрика):

(7)

Метрики для качественных шкал (мера близости).

К качественным шкалам относят:

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

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

Расстояние для номинальных шкал вводится следующим образом. Пусть имеются два объекта X и Y с N признаками. Введем координаты xi и yi (i=1,2,…,N) как логические переменные, принимающие значение 1, если объект обладает i-м признаком, и 0, если признак с номером i у объекта отсутствует.

Выбор конкретного измерителя близости объектов X и Y должен осуществляться из содержательных соображений: если предполагается значимость совпадения единичных и нулевых свойств, то применяют расстояние Хемминга - отношение количества совпадающих значений к числу всех значений N. Если же важно наличие свойства, а не его отсутствие, то применяют коэффициенты Рао или Роджерса-Танимото, в которых учитываются только совпадающие единичные значения, а совпадающие нулевые игнорируются.

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

Сети и карты Кохонена

Сети Кохонена.

Сети Кохонена (Kohonen T.) относятся к самоорганизующимся нейронным сетям. Самоорганизующаяся сеть позволяет выявлять кластеры (группы) входных векторов, обладающих некоторыми общими свойствами. При этом выделяют сети с неупорядоченными нейронами (часто называемые слоями Кохонена) и сети с упорядочением нейронов (часто называемые самоорганизующимися картами, или SOM - self-organizing map). Карты Кохонена наглядно отражают на двумерной карте объекты с близкими свойствами.

Сеть Кохонена (рис. 1) - это однослойная сеть, каждый нейрон которой соединен со всеми компонентами n -мерного входного вектора. Входной вектор - это описание одного из объектов, подлежащих кластеризации. Количество нейронов совпадает с количеством кластеров, которое должна выделить сеть. В качестве нейронов сети Кохонена применяются линейные взвешенные сумматоры. Каждый j -ый нейрон описывается вектором весов wj=(w1j ,w2j ,…, wmj ), где m - число компонентов входных векторов.

Входной вектор имеет вид xi=(xi1, xi2, …, xim).

Рис. 1. Структура сети Кохонена

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

(8)

где n - количество нейронов, j - номер нейрона-победителя, d (x,w) - расстояние (в смысле выбранной метрики) между векторами x и w. Чаще всего в качестве меры расстояния используется евклидова мера:

(9)

Используются и другие меры расстояния (метрики).

Вокруг нейрона-победителя образуется окружение (neighborhood), или радиус обучения (radius of learning). Радиус обучения определяет сколько нейронов кроме нейрона-победителя участвуют в обучении (т.е. корректируют свои веса) на данной итерации. Под радиусом в данном случае подразумевается расстояние в пространстве векторов весов нейронов. Т. е. любой нейрон, расстояние от вектора весов которого до вектора весов нейрона-победителя менее радиуса обучения, участвует в коррекции весов на данной итерации. Радиус обучения максимален на первой итерации и уменьшается с увеличением числа итераций таким образом, что в конце обучения корректирует свои веса только нейрон победитель.

Веса нейрона-победителя и всех нейронов, лежащих в пределах его радиуса обучения, подвергаются обучению (адаптации) по правилу Кохонена

(10)

где x - входной вектор, k - номер цикла обучения, - коэффициент скорости обучения i -го нейрона из радиуса обучения в k -ом цикле обучения.

Веса нейронов, находящихся за пределами радиуса обучения не изменяются.

Коэффициент скорости обучения разбивается на две части: функцию соседства и функции скорости обучения a(k).

(11)

В качестве функции соседства применяется или константа:

(12)

или Гауссова функция:

(13)

При этом лучший результат получается при использовании Гауссовой функции расстояния. В (11) и (12) di - расстояние между i -м нейроном и нейроном-победителем. При этом (k) является убывающей функцией от номера цикла обучения. Наиболее часто используется функция, линейно убывающая от номера цикла обучения.

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

(14)

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

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

Обучение продолжается до тех пор, пока погрешность сети (погрешность квантования) при p входных векторах не станет малой величиной (wj - вектор весов нейрона-победителя).

(15)

При обучении сети Кохонена возникает проблема так называемых "мертвых" нейронов. Одно из ограничений всякого конкурирующего слоя состоит в том, что некоторые нейроны оказываются незадействованными. Это проявляется в том, что нейроны, имеющие начальные весовые векторы, значительно удаленные от векторов входа, никогда не выигрывают конкуренции, независимо от того, как долго продолжается обучение. В результате оказывается, что такие векторы не используются при обучении и соответствующие нейроны никогда не оказываются победителями. Такие "нейроны-неудачники" называют "мертвыми" нейронами, поскольку они не выполняют никакой полезной функции. Таким образом, входные данные будут интерпретироваться меньшим числом нейронов, а погрешность квантования (15) увеличивается. Поэтому надо дать шанс победить всем нейронам. Для этого алгоритм обучения модифицируют таким образом, чтобы нейрон-победитель терял активность. Одним из приемов учета активности нейронов является подсчет потенциала pi каждого нейрона в процессе обучения. Первоначально нейронам присваивается потенциал pi(0)=1/n, где n - число нейронов (кластеров). В k-том цикле обучения потенциал определяется по правилам:

(16)

где j - номер нейрона-победителя.

Если значение потенциала pi(k) падает ниже уровня pmin, то нейрон исключается из рассмотрения - "отдыхает". При pmin = 0 нейроны не исключаются из борьбы. При pmin =1 нейроны побеждают по очереди, так как в каждый цикл обучения только один из них готов к борьбе. На практике хороший результат получается при pmin ~ 0.75.

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

В сети Кохонена входные значения желательно (хотя и не обязательно) нормировать. Для этого следует воспользоваться одной из следующих формул:

(17)

где xнi - нормированный компонент входного вектора.

Карты Кохонена

Карты Кохонена (самоорганизующиеся карты, или SOM - selforganizing map) предназначены для визуального представления многомерных свойств объектов на двумерной карте.

Карта Кохонена состоит из ячеек прямоугольной или шестиугольной (рис. 2) формы.

Рис. 2. Шестиугольные ячейки сети Кохонена

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

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

Рис. 3. Шестиугольные и прямоугольные ячейки

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

Кластерный анализ с применением карт Кохонена основных социально-экономических показателей административных районов Ставропольского края

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

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

Для проведения анализа применяется рабочее место аналитика Deductor Studio, которое входит в состав аналитической платформы Deductor. Данное приложение содержит набор механизмов импорта, обработки, визуализации и экспорта данных для быстрого и эффективного анализа информации. Будем использовать 14 наиболее важные показателя социально-экономического положения административных районов края (рис. 6, 7), которые представим относительными величинами интенсивности в зависимости от численности населения. Такой перевод является важным для объективной оценки территорий по уровню социально-экономического развития. Анализ других показателей затрудняется отсутствием числовых или категорийных значений по районам края.

Рис. 4. Кластеризация районов Ставропольского края по социально-экономическому положению за 2010 г. с указанием плотности населения

Таблица 1. Результаты кластеризации районов Ставропольского края

Рис. 5. Карты Кохонена показателей социально-экономического положения районов

На рис.5 курсивом выделены сокращенные названия районов представителей кластера 0, подчеркнуты - представители кластера 2, по оси Х выделены значения для Красногвардейского района.

Рис. 6. Профили кластеров районов Ставропольского края по показателям уровня социально-экономического положения

Рис. 7. Нормализованная столбчатая диаграмма кластеров по показателям уровня социально-экономического положения районов края

Результаты по сформированным кластерам наиболее удобно рассматриваются с помощью визуализатора "Куб", в котором встроена кросс-диаграмма, изображающая полученные кластеры в графическом виде, что существенно упрощает анализ.

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

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

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

Аутсайдером являются представители третьего кластера с низкими уровнями значений почти по всем показателям.

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

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

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



Список литературы

BaseGroup Labs. Технологии анализа данных: сайт. URL: http://www.basegroup.ru (дата обращения: 06.12.2012).

Дюран Б., Оделл П. Кластерный анализ / Б. Дюран, П. Оделл - М.: Статистика, 1977. 128 с.

Жамбю М. Иерархический кластер-анализ и соответствия. / М. Жамбю - М.: Финансы и статистика, 1988. 342 с.

Кохонен, Т. Самоорганизующиеся карты / Т. Кохонен. - М.: БИНОМ. Лаборатория знаний, 2008. - 655 с.

Мандель И.Д. Кластерный анализ. / И.Д. Мандель- М.: Финансы и статистика, 1988. 176 с.

Осовский, С. Нейронные сети для обработки информации / С. Осовский. - М.: Финансы и статистика, 2002. - 244 с.

Ставропольский край в цифрах, 2011. Статистический ежегодник/ Территориальный орган федеральной службы государственной статистики по Ставропольскому краю. 2011. 288 с.

Хайкин, С. Нейронные сети: полный курс / С. Хайкин. - М.: Вильямс, 2006. - 1104 с.

Размещено на Allbest.ru

...