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

 

 

 

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

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

карт Кохонена»

 

 

 

 

 

Содержание

 

 

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

 

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

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

Кластерный анализ – это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как «сгустков» этих точек (кластеров, таксонов). «Кластер» (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. Если же важно наличие свойства, а не его отсутствие, то применяют коэффициенты Рао или Роджерса-Танимото, в которых учитываются только совпадающие единичные значения, а совпадающие нулевые игнорируются.

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

 

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

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

Сети Кохонена (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). Радиус обучения определяет сколько нейронов кроме нейрона-победителя участвуют в обучении (т.е. корректируют свои веса) на данной итерации. Под радиусом в данном случае подразумевается расстояние в пространстве векторов весов нейронов. Т. е. любой нейрон, расстояние от вектора весов которого до вектора весов нейрона-победителя менее радиуса обучения, участвует в коррекции весов на данной итерации. Радиус обучения максимален на первой итерации и уменьшается с увеличением числа итераций таким образом, что в конце обучения корректирует свои веса только нейрон победитель.

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

h       (10)

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

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

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

hh          (11)

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

h       (12)

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

h          (13)

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

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

           (14)

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

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

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

         (15)

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