Реферат: Моделирование сети кластеризации данных в MATLAB NEURAL NETWORK TOOL

--PAGE_BREAK--Результаты кластеризации должны быть представлены в удобном для обработки виде, чтобы осуществить оценку качества кластеризации. Обычно используется один из следующих способов:
·представление кластеров центроидами;

·представление кластеров набором характерных точек;

·представление кластеров их ограничениями.
<img border=«0» width=«271» height=«106» src=«ref-1_1878248015-2493.coolpic» v:shapes=«Рисунок_x0020_5»>

Рисунок 1.4 –Способы представления кластеров

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

·  ручная проверка;

·  установление контрольных точек и проверка на полученных кластерах;

·  определение стабильности кластеризации путем добавления в модель новых переменных;

·  создание и сравнение кластеров с использованием различных методов.

Разные методы кластеризации могут создавать разные кластеры, и это является нормальным явлением. Однако создание схожих кластеров различными методами указывает на правильность кластеризации.
1.3      Алгоритмы кластеризации
Следует отметить, что в результате применения различных методов кластерного анализа могут быть получены кластеры различной формы. Например, возможны кластеры «цепочного» типа, когда кластеры представлены длинными «цепочками», кластеры удлиненной формы и т.д., а некоторые методы могут создавать кластеры произвольной формы. Различные методы могут стремиться создавать кластеры определенных размеров (например, малых или крупных), либо предполагать в наборе данных наличие кластеров различного размера. Некоторые методы кластерного анализа особенно чувствительны к шумам или выбросам, другие — менее. В результате применения различных методов кластеризации могут быть получены неодинаковые результаты, это нормально и является особенностью работы того или иного алгоритма. Данные особенности следует учитывать при выборе метода кластеризации. На сегодняшний день разработано более сотни различных алгоритмов кластеризации.

Классифицировать алгоритмы можно следующим образом:

·строящие «снизу вверх» и «сверху вниз»;

·монотетические и политетические;

·непересекающиеся и нечеткие;

·детерминированные и стохастические;

·потоковые (оnline) и не потоковые;

·зависящие и не зависящие от порядка рассмотрения объектов.
<img border=«0» width=«282» height=«127» src=«ref-1_1878250508-9986.coolpic» v:shapes=«Рисунок_x0020_6»>

Рисунок1.5 – Классификация алгоритмов кластеризации
Далее будут рассмотрены основные алгоритмы кластеризации.
1.3.1 Иерархические алгоритмы

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

·single-link– на каждом шаге объединяет два кластера с наименьшим расстоянием между двумя любыми представителями;

·complete-link– на каждом шаге объединяет два кластера с наименьшим расстоянием между двумя наиболее удаленными представителями.
<img border=«0» width=«132» height=«91» src=«ref-1_1878260494-1617.coolpic» v:shapes=«Рисунок_x0020_7»>

Рисунок1.6 – Пример single-linkалгоритма

<img border=«0» width=«148» height=«97» src=«ref-1_1878262111-2045.coolpic» v:shapes=«Рисунок_x0020_8»>

Рисунок1.7 – Пример complete-linkалгоритма
1.3.2 k-Meansалгоритм

Данный алгоритм состоит из следующих шагов:

1. Случайно выбрать kточек, являющихся начальными координатами «центрами масс» кластеров (любые kиз nобъектов, или вообще kслучайных точек).

2. Отнести каждый объект к кластеру с ближайшим «центром масс».

3. Пересчитать «центры масс» кластеров согласно текущему членству.

4. Если критерий остановки не удовлетворен, вернуться к шагу 2.

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

Алгоритм чувствителен к начальному выбору «центр масс».
<img border=«0» width=«174» height=«109» src=«ref-1_1878264156-2029.coolpic» v:shapes=«Рисунок_x0020_9»>

Рисунок1.8 – Пример k-Meansалгоритма
1.3.3 Минимальное покрывающее дерево

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




<img border=«0» width=«148» height=«108» src=«ref-1_1878266185-2212.coolpic» v:shapes=«Рисунок_x0020_10»>

Рисунок1.9 – Пример алгоритмаминимального покрывающего дерева
1.3.4 Метод ближайшего соседа

Этот метод является одним из старейших методов кластеризации. Он был создан в 1978 году. Он прост и наименее оптимален из всех представленных.

Для каждого объекта вне кластера делаем следующее:

1. Находим его ближайшего соседа, кластер которого определен.

2. Если расстояние до этого соседа меньше порога, то относим его в тот же кластер. Иначе из рассматриваемого объекта создается еще один кластер.

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

Четкая (непересекающаяся) кластеризация – кластеризация, которая каждый <img border=«0» width=«20» height=«30» src=«ref-1_1878268397-99.coolpic» v:shapes="_x0000_i1035"> из <img border=«0» width=«20» height=«23» src=«ref-1_1878268496-203.coolpic» v:shapes="_x0000_i1036"> относит только к одному кластеру.

Нечеткая кластеризация – кластеризация, при которой для каждого <img border=«0» width=«20» height=«30» src=«ref-1_1878268397-99.coolpic» v:shapes="_x0000_i1037"> из <img border=«0» width=«20» height=«23» src=«ref-1_1878268496-203.coolpic» v:shapes="_x0000_i1038"> определяется <img border=«0» width=«30» height=«32» src=«ref-1_1878269001-126.coolpic» v:shapes="_x0000_i1039">. <img border=«0» width=«30» height=«32» src=«ref-1_1878269001-126.coolpic» v:shapes="_x0000_i1040">– вещественное значение, показывающее степень принадлежности <img border=«0» width=«20» height=«30» src=«ref-1_1878268397-99.coolpic» v:shapes="_x0000_i1041"> к кластеру j.

Алгоритм нечеткой кластеризации таков:

1. Выбрать начальное нечеткое разбиение объектов на nкластеров путем выбора матрицы принадлежности <img border=«0» width=«22» height=«23» src=«ref-1_1878269352-101.coolpic» v:shapes="_x0000_i1042"> размера <img border=«0» width=«35» height=«23» src=«ref-1_1878269453-130.coolpic» v:shapes="_x0000_i1043">. Обычно <img border=«0» width=«77» height=«30» src=«ref-1_1878269583-362.coolpic» v:shapes="_x0000_i1044">.

2. Используя матрицу U, найти значение критерия нечеткой ошибки. Например,

<img border=«0» width=«251» height=«52» src=«ref-1_1878269945-921.coolpic» v:shapes="_x0000_i1045">,  (1.2)
где <img border=«0» width=«22» height=«30» src=«ref-1_1878270866-103.coolpic» v:shapes="_x0000_i1046">- «центр масс» нечеткого кластера k,
<img border=«0» width=«118» height=«60» src=«ref-1_1878270969-582.coolpic» v:shapes="_x0000_i1047">.  (1.3)
3. Перегруппировать объекты с целью уменьшения этого значения критерия нечеткой ошибки.

4. Возвращаться в пункт 2 до тех пор, пока изменения матрицы <img border=«0» width=«22» height=«23» src=«ref-1_1878269352-101.coolpic» v:shapes="_x0000_i1048"> не станут значительными.
<img border=«0» width=«154» height=«93» src=«ref-1_1878271652-2171.coolpic» v:shapes=«Рисунок_x0020_25»>

Рисунок1.10 – Пример алгоритманечеткой кластеризации
1.3.6 Применение нейронных сетей

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

·искусственные нейронные сети легко работают в распределенных системах с большой параллелизацией в силу своей природы;

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

Существует масса ИНС, например, персептрон, радиально-базисные сети, LVQ-сети, самоорганизующиеся карты Кохонена, которые можно использовать для решения задачи кластеризации. Но наиболее лучше себя зарекомендовала сеть с применением самоорганизующихся карт Кохонена, которая и выбрана для рассмотрения в данном дипломном проекте.
1.3.7     Генетические алгоритмы

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

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

Общая схема данного подхода:

1. Выбрать начальную случайную популяцию множества решений и получить оценку качества для каждого решения (обычно она пропорциональна <img border=«0» width=«40» height=«27» src=«ref-1_1878273823-215.coolpic» v:shapes="_x0000_i1050">).

2. Создать и оценить следующую популяцию решений, используя эволюционные операторы: оператор выбора – с большой вероятностью предпочитает хорошие решения; оператор рекомбинации (обычно это «кроссовер») – создает новое решение на основе рекомбинации из существующих; оператор мутации – создает новое решение на основе случайного незначительного изменения одного из существующих решений.

3. Повторять шаг 2 до получения нужного результата.

Главным достоинством генетических алгоритмов в данном применении является то, что они ищут глобальное оптимальное решение. Большинство популярных алгоритмов оптимизации выбирают начальное решение, которое затем изменяется в ту или иную сторону. Таким образом получается хорошее разбиение, но не всегда самое оптимальное. Операторы рекомбинации и мутации позволяют получить решения, сильно не похожее на исходное – таким образом осуществляется глобальный поиск.
<img border=«0» width=«171» height=«122» src=«ref-1_1878274038-4184.coolpic» v:shapes=«Рисунок_x0020_27»>

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

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

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

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

Таким образом, кластеризация, во-первых, применятся для анализа данных (упрощение работы с информацией, визуализация данных). Использование кластеризации упрощает работу с информацией, так как:

·достаточно работать с kпредставителями кластеров;

·легко найти «похожие» объекты – такой поиск применяется в ряде поисковых движков;

·происходит автоматическое построение каталогов;

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

Во-вторых, для группировки и распознавания объектов. Для распознавания образов характерно:

·построение кластеров на основе большого набора учебных данных;

·присвоение каждому из кластеров соответствующей метки;

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

Для группировки объектов характерно:

·сегментация изображений

·уменьшение количества информации
<img border=«0» width=«207» height=«140» src=«ref-1_1878278222-5808.coolpic» v:shapes=«Рисунок_x0020_28»>

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

Извлечение и поиск информации можно рассмотреть на примере книг в библиотеке. Это наиболее известная система не автоматической классификации – LCC(LibraryofCongressClassification):

·метка Qозначает книги по науке;

·подкласс QA– книги по математике;

·метки с QA76 до QA76.8 – книги по теоретической информатике.

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



    продолжение
--PAGE_BREAK--2. СЕТЬ КОХОНЕНА


Сеть Кохонена — это одна из разновидностей нейронных сетей, которые используют неконтролируемое обучение. При таком обучении обучающее множество состоит лишь из значений входных переменных, в процессе обучения нет сравнивания выходов нейронов с эталонными значениями. Можно сказать, что такая сеть учится понимать структуру данных.

Идея сети Кохонена принадлежит финскому ученому Тойво Кохонену (1982 год). Основной принцип работы сетей — введение в правило обучения нейрона информации относительно его расположения.

В основе идеи сети Кохонена лежит аналогия со свойствами человеческого мозга. Кора головного мозга человека представляет собой плоский лист и свернута складками. Таким образом, можно сказать, что она обладает определенными топологическими свойствами (участки, ответственные за близкие части тела, примыкают друг к другу и все изображение человеческого тела отображается на эту двумерную поверхность). Во многих моделях ИНС решающую роль играют связи между нейронами, определяемые весовыми коэффициентами и указывающие место нейрона в сети. Однако в биологических системах, на пример, таких как мозг, соседние нейроны, получая аналогичные входные сигналы, реагируют на них сходным образом, т. е. группируются, образуя некоторые области. Поскольку при обработке многомерного входного образа осуществляется его проецирование на область меньшей размерности с сохранением его топологии, часто подобные сети называют картами (self-organizing feature map). В таких сетях существенным является учет взаимного расположения нейронов одного слоя.

Сеть Кохонена (самоорганизующаяся карта) относится к самоорганизующимся сетям, которые при поступлении входных сигналов, в отличие от сетей, использующих обучение с учителем, не получают информацию о желаемом выходном сигнале. В связи с этим невозможно сформировать критерий настройки, основанный на рассогласовании реальных и требуемых выходных сигналов ИНС, поэтому весовые параметры сети корректируют, исходя из других соображений. Все предъявляемые входные сигналы из заданного обучающего множества самоорганизующаяся сеть в процессе обучения разделяет на классы, строя так называемые топологические карты.
2.1 Структура сети Кохонена
Сеть Кохонена использует следующую модель (рисунок2.1): сеть состоит из М нейронов, образующих прямоугольную решетку на плоскости — слой.
<img border=«0» width=«181» height=«134» src=«ref-1_1878284030-5244.coolpic» v:shapes=«Рисунок_x0020_29»>

Рисунок2.1 –Модель сети Кохонена
К нейронам, расположенным в одном слое, представляющем собой двумерную плоскость, подходят нервные волокна, по которым поступает N-мерный входной сигнал. Каждый нейрон характеризуется своим положением в слое и весовым коэффициентом. Положение нейронов, в свою очередь, характеризуется некоторой метрикой и определяется топологией слоя, при которой соседние нейроны во время обучения влияют друг на друга сильнее, чем расположенные дальше. Каждый нейрон образует взвешенную сумму входных сигналов с <img border=«0» width=«59» height=«32» src=«ref-1_1878289274-275.coolpic» v:shapes="_x0000_i1054">, если синапсы ускоряющие, и <img border=«0» width=«59» height=«32» src=«ref-1_1878289549-275.coolpic» v:shapes="_x0000_i1055">  — если тормозящие. Наличие связей между нейронами приводит к тому, что при возбуждении одного из них можно вычислить возбуждение остальных нейронов в слое, причем это возбуждение с увеличением расстояния от возбужденного нейрона уменьшается. Поэтому центр возникающей реакции слоя на полученное раздражение соответствует местоположению возбужденного нейрона. Изменение входного обучающего сигнала приводит к максимальному возбуждению другого нейрона и соответственно — к другой реакции слоя. Сеть Кохонена может рассматриваться как дальнейшее развитие LVQ (LearningVectorQuantization). Отличие их состоит в способах обучения.


2.2 Обучение сети Кохонена


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

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

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

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

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

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

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

Рассмотрим это более подробнее. Кохонен существенно упростил решение задачи, выделяя из всех нейронов слоя лишь один с-й нейрон, для которого взвешенная сумма входных сигналов максимальна:
<img border=«0» width=«150» height=«40» src=«ref-1_1878289824-595.coolpic» v:shapes="_x0000_i1056">.(2.1)
Отметим, что весьма полезной операцией предварительной об работки входных векторов является их нормализация:
<img border=«0» width=«124» height=«51» src=«ref-1_1878290419-349.coolpic» v:shapes="_x0000_i1057"> (2.2)
превращающая векторы входных сигналов в единичные с тем же направлением.
<img border=«0» width=«120» height=«60» src=«ref-1_1878290768-643.coolpic» v:shapes="_x0000_i1058"> (2.3)
В этом случае вследствие того, что сумма весов каждого нейрона одного слоя <img border=«0» width=«54» height=«45» src=«ref-1_1878291411-285.coolpic» v:shapes="_x0000_i1059">для всех нейронов этого слоя одинакова и <img border=«0» width=«44» height=«23» src=«ref-1_1878291696-148.coolpic» v:shapes="_x0000_i1060">, условие (2.1) эквивалентно условию:
<img border=«0» width=«168» height=«49» src=«ref-1_1878291844-620.coolpic» v:shapes="_x0000_i1061">.(2.4)
Таким образом, будет активирован только тот нейрон, вектор весов которого w наиболее близок к входному вектору х. А так как перед началом обучения неизвестно, какой именно нейрон будет активироваться при предъявлении сети конкретного входного вектора, сеть обучается без учителя, т. е. самообучается. Вводя потенциальную функцию — функцию расстояния <img border=«0» width=«23» height=«32» src=«ref-1_1878292464-115.coolpic» v:shapes="_x0000_i1062"> («соседства») между i-м и j-м нейронами с местоположениями <img border=«0» width=«17» height=«30» src=«ref-1_1878292579-92.coolpic» v:shapes="_x0000_i1063"> и <img border=«0» width=«18» height=«32» src=«ref-1_1878292671-98.coolpic» v:shapes="_x0000_i1064"> соответственно, монотонно убывающую с увеличением расстояния между этими нейронами, Кохонен предложил следующий алгоритм коррекции весов:
<img border=«0» width=«366» height=«32» src=«ref-1_1878292769-1147.coolpic» v:shapes="_x0000_i1065">,(2.5)
где <img border=«0» width=«99» height=«27» src=«ref-1_1878293916-494.coolpic» v:shapes="_x0000_i1066">- изменяющийся во времени коэффициент усиления (обычно выбирают <img border=«0» width=«47» height=«23» src=«ref-1_1878294410-225.coolpic» v:shapes="_x0000_i1067"> на первой итерации, постепенно уменьшая в процессе обучения до нуля); <img border=«0» width=«50» height=«32» src=«ref-1_1878294635-282.coolpic» v:shapes="_x0000_i1068">- монотонно убывающая функция.

<img border=«0» width=«331» height=«40» src=«ref-1_1878294917-1027.coolpic» v:shapes="_x0000_i1069">, (2.6)
Где <img border=«0» width=«17» height=«30» src=«ref-1_1878292579-92.coolpic» v:shapes="_x0000_i1070"> и <img border=«0» width=«18» height=«32» src=«ref-1_1878292671-98.coolpic» v:shapes="_x0000_i1071">  — векторы, определяющие положение нейронов i и jв решетке. При принятой метрике <img border=«0» width=«97» height=«40» src=«ref-1_1878296134-273.coolpic» v:shapes="_x0000_i1072"> функция <img border=«0» width=«50» height=«32» src=«ref-1_1878294635-282.coolpic» v:shapes="_x0000_i1073"> с ростом времени <img border=«0» width=«17» height=«23» src=«ref-1_1878296689-97.coolpic» v:shapes="_x0000_i1074"> стремится к нулю. На практике вместо параметра времени <img border=«0» width=«17» height=«23» src=«ref-1_1878296689-97.coolpic» v:shapes="_x0000_i1075"> используют параметр расстояния <img border=«0» width=«20» height=«18» src=«ref-1_1878296883-171.coolpic» v:shapes="_x0000_i1076">, задающий величину области «соседства» и уменьшающийся с течением времени до нуля. Выбор функции <img border=«0» width=«50» height=«32» src=«ref-1_1878294635-282.coolpic» v:shapes="_x0000_i1077"> также влияет на величины весов всех нейронов в слое. Очевидно, что для нейрона-победителя <img border=«0» width=«20» height=«23» src=«ref-1_1878297336-98.coolpic» v:shapes="_x0000_i1078">:
<img border=«0» width=«185» height=«40» src=«ref-1_1878297434-655.coolpic» v:shapes="_x0000_i1079">.(2.7)
На рисунке2.2 показан пример изменения двумерных весов карты <img border=«0» width=«109» height=«27» src=«ref-1_1878298089-242.coolpic» v:shapes="_x0000_i1080">, образующей цепь. При появлении входного образа <img border=«0» width=«17» height=«19» src=«ref-1_1878298331-161.coolpic» v:shapes="_x0000_i1081"> наиболее сильно изменяется весовой вектор нейрона-победителя 5, менее сильно — веса расположенных рядом с ним нейронов 3, 4, 6, 7. А так как нейроны 1, 2, 8, 9 лежат вне области «соседства», их весовые коэффициенты не изменяются.
<img border=«0» width=«242» height=«102» src=«ref-1_1878298492-2890.coolpic» v:shapes=«Рисунок_x0020_58»>

Рисунок– 2.2 Изменение весов карты Кохонена
Таким образом, алгоритм обучения сети Кохонена может быть описан так:

1. Инициализация

Весовым коэффициентам всех нейронов присваиваются малые случайные значения и осуществляется их нормализация. Выбирается соответствующая потенциальная функция <img border=«0» width=«43» height=«25» src=«ref-1_1878301382-149.coolpic» v:shapes="_x0000_i1083"> и назначается начальное значение коэффициента усиления <img border=«0» width=«26» height=«32» src=«ref-1_1878301531-203.coolpic» v:shapes="_x0000_i1084">.

2. Выбор обучающего сигнала

Из всего множества векторов обучающих входных сигналов в соответствии с функцией распределения <img border=«0» width=«35» height=«21» src=«ref-1_1878301734-128.coolpic» v:shapes="_x0000_i1085"> выбирается один вектор <img border=«0» width=«17» height=«19» src=«ref-1_1878298331-161.coolpic» v:shapes="_x0000_i1086">, который представляет «сенсорный сигнал», предъявляемый сети.

3. Анализ отклика (выбор нейрона)

По формуле (2.1) определяется активированный нейрон.

4. Процесс обучения

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

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

Если бы с каждым нейроном слоя ассоциировался один входной вектор, то вес любого нейрона слоя Кохонена мог бы быть обучен с помощью одного вычисления, так как вес нейрона-победителя корректировался бы с <img border=«0» width=«48» height=«25» src=«ref-1_1878302023-232.coolpic» v:shapes="_x0000_i1087"> (в соответствии с (2.5) для одномерного случая вес сразу бы попадал в центр отрезка [а, b]). Однако обычно обучающее множество включает множество сходных между собой входных векторов, и сеть Кохонена должна быть обучена активировать один и тот же нейрон для каждого из них. Это достигается усреднением входных векторов путем уменьшения величины, а не при предъявлении каждого последующего входного сигнала. Таким образом, веса, ассоциированные с нейроном, усреднятся и примут значение вблизи «центра» входных сигналов, для которых данный нейрон является «победителем».
2.3 Выбор функции «соседства»
На рисунке 2.3 показан слой нейронов с нейроном-победителем, отмеченным черным кружком. Поскольку веса всех затемненных нейронов изменяются по-разному, в зависимости от их удаленности от нейрона-победителя, наиболее простым является выбор в качестве <img border=«0» width=«24» height=«33» src=«ref-1_1878302255-201.coolpic» v:shapes="_x0000_i1088"> некоторой величины, равной единице при <img border=«0» width=«39» height=«23» src=«ref-1_1878302456-200.coolpic» v:shapes="_x0000_i1089">, меньшей единицы для затемненных нейронов, т. е. нейронов, лежащих в непосредственной близости от активированного нейрона, и нулю для остальных, отмеченных светлыми кружками.
<img border=«0» width=«216» height=«82» src=«ref-1_1878302656-3962.coolpic» v:shapes=«Рисунок_x0020_66»>

Рисунок 2.3 – Слой нейронов Кохонена
На практике же в качестве <img border=«0» width=«24» height=«33» src=«ref-1_1878302255-201.coolpic» v:shapes="_x0000_i1091"> выбирают функции, использующие евклидову метрику:
<img border=«0» width=«141» height=«50» src=«ref-1_1878306819-624.coolpic» v:shapes="_x0000_i1092">, (2.8)
где <img border=«0» width=«22» height=«32» src=«ref-1_1878307443-181.coolpic» v:shapes="_x0000_i1093">, <img border=«0» width=«26» height=«33» src=«ref-1_1878307624-188.coolpic» v:shapes="_x0000_i1094"> — координаты i-гo и j-го нейронов.

К числу наиболее широко используемых потенциальных функций относятся:

а) колоколообразная функция Гаусса
<img border=«0» width=«155» height=«55» src=«ref-1_1878307812-689.coolpic» v:shapes="_x0000_i1095">, (2.9)
где <img border=«0» width=«27» height=«28» src=«ref-1_1878308501-196.coolpic» v:shapes="_x0000_i1096">- дисперсия отклонения;
<img border=«0» width=«195» height=«102» src=«ref-1_1878308697-3710.coolpic» v:shapes=«Рисунок_x0020_73»>

Рисунок 2.4 – Колоколообразная функция Гаусса
б) функция «мексиканская шляпа»
<img border=«0» width=«220» height=«58» src=«ref-1_1878312407-597.coolpic» v:shapes="_x0000_i1098">, (2.10)
<img border=«0» width=«195» height=«86» src=«ref-1_1878313004-3083.coolpic» v:shapes=«Рисунок_x0020_75»>

Рисунок 2.5 – Функция «мексиканская шляпа»
в) косинусоидная функция
<img border=«0» width=«189» height=«68» src=«ref-1_1878316087-621.coolpic» v:shapes="_x0000_i1100"> (2.11)

<img border=«0» width=«168» height=«88» src=«ref-1_1878316708-2826.coolpic» v:shapes=«Рисунок_x0020_77»>

Рисунок 2.6 – Косинусоидная функция
г) конусообразная функция
<img border=«0» width=«172» height=«67» src=«ref-1_1878319534-523.coolpic» v:shapes="_x0000_i1102"> (2.12)
<img border=«0» width=«183» height=«96» src=«ref-1_1878320057-2923.coolpic» v:shapes=«Рисунок_x0020_79»>

Рисунок 2.7 – Конусообразная функция
д) цилиндрическая функция
<img border=«0» width=«177» height=«52» src=«ref-1_1878322980-497.coolpic» v:shapes="_x0000_i1104"> (2.13)
<img border=«0» width=«183» height=«85» src=«ref-1_1878323477-3262.coolpic» v:shapes=«Рисунок_x0020_81»>

Рисунок 2.8 – Цилиндрическая функция
2.4 Карта Кохонена
Как правило, сначала строят довольно грубую карту (модель разбиения), постепенно уточняя ее в процессе обучения. Для этого необходимо медленно изменять не только параметр <img border=«0» width=«20» height=«19» src=«ref-1_1878326739-182.coolpic» v:shapes="_x0000_i1106">, но и, например, параметр <img border=«0» width=«20» height=«19» src=«ref-1_1878326921-171.coolpic» v:shapes="_x0000_i1107"> в формуле (2.9). Одним из эффективных способов изменения этих параметров является следующий:
<img border=«0» width=«121» height=«49» src=«ref-1_1878327092-523.coolpic» v:shapes="_x0000_i1108">, (2.14)

<img border=«0» width=«139» height=«56» src=«ref-1_1878327615-562.coolpic» v:shapes="_x0000_i1109">, (2.15)
где <img border=«0» width=«67» height=«21» src=«ref-1_1878328177-177.coolpic» v:shapes="_x0000_i1110">; <img border=«0» width=«61» height=«24» src=«ref-1_1878328354-157.coolpic» v:shapes="_x0000_i1111">; <img border=«0» width=«69» height=«21» src=«ref-1_1878328511-174.coolpic» v:shapes="_x0000_i1112">; <img border=«0» width=«65» height=«23» src=«ref-1_1878328685-163.coolpic» v:shapes="_x0000_i1113">  — параметры, определяющие крутизну функции <img border=«0» width=«23» height=«30» src=«ref-1_1878328848-111.coolpic» v:shapes="_x0000_i1114">; <img border=«0» width=«34» height=«29» src=«ref-1_1878328959-130.coolpic» v:shapes="_x0000_i1115">- задаваемое число итераций.

На рисунке 2.9 показан процесс построения карты Кохонена, представляющей собой двумерную решетку, образованную путем соединения соседних нейронов, находящихся в узлах решетки. Исходя из начальных условий и используя алгоритм обучения (2.5), сеть по мере увеличения числа обучающих входных образов развивается и приобретает вид решетки. Внизу каждого рисунка поставлено количество образов, на основании которых получена соответствующая сеть.
<img border=«0» width=«239» height=«273» src=«ref-1_1878329089-14960.coolpic» v:shapes=«Рисунок_x0020_92»>

Рисунок2.9 – Построение карты Кохонена

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

Нейроны карты Кохонена располагают в виде двухмерной матрицы, раскрашивают эту матрицу в зависимости от анализируемых параметров нейронов.

На рисунке 2.10 приведен пример карты Кохонена.
<img border=«0» width=«189» height=«142» src=«ref-1_1878344049-7688.coolpic» v:shapes="_x0000_i1117">

Рисунок 2.10 –Пример карты Кохонена
На рисунке 2.11 приведена раскраска карты, а точнее, ее i-го признака, в трехмерном представлении. Как мы видим, темно-синие участки на карте соответствуют наименьшим значениям показателя, красные — самым высоким.
<img border=«0» width=«202» height=«200» src=«ref-1_1878351737-4677.coolpic» v:shapes="_x0000_i1118">

Рисунок 2.11 –Раскраска i-го признака в трехмерном пространстве

Теперь, возвращаясь к рисунку 2.10, мы можем сказать, какие объекты имеют наибольшие значения рассматриваемого показателя (группа объектов, обозначенная красным цветом), а какие — наименьшие значения (группа объектов, обозначенная синим цветом).

Таким образом, карты Кохонена можно отображать:

·в двухмерном виде, тогда карта раскрашивается в соответствии с уровнем выхода нейрона;

·в трехмерном виде.

В результате работы алгоритма получаем такие карты:

а) Карта входов нейронов.

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

б) Карта выходов нейронов.

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

в) Специальные карты.

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

Координаты каждой карты определяют положение одного нейрона. Так, координаты [15:30] определяют нейрон, который находится на пересечении 15-го столбца с 30-м рядом в матрице нейронов. Важно понимать, что между всеми рассмотренными картами существует взаимосвязь — все они являются разными раскрасками одних и тех же нейронов. Каждый пример из обучающей выборки имеет одно и то же расположение на всех картах.

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

При реализации сети Кохонена возникают следующие проблемы:

1. Выбор коэффициента обучения <img border=«0» width=«18» height=«17» src=«ref-1_1878356414-168.coolpic» v:shapes="_x0000_i1119">

Этот выбор влияет как на скорость обучения, так и на устойчивость получаемого решения. Очевидно, что процесс обучения ускоряется (скорость сходимости алгоритма обучения увеличивается) при выборе <img border=«0» width=«18» height=«17» src=«ref-1_1878356414-168.coolpic» v:shapes="_x0000_i1120"> близким к единице. Однако в этом случае предъявление сети различных входных векторов, относящихся к одному классу, приведет к изменениям соответствующего вектора весовых коэффициентов. Напротив, при <img border=«0» width=«40» height=«17» src=«ref-1_1878356750-203.coolpic» v:shapes="_x0000_i1121">0 скорость обучения будет медленной, однако вектор весовых коэффициентов, достигнув центра класса, при подаче на вход сети различных сигналов, относящихся к одному классу, будет оставаться вблизи этого центра. Поэтому одним из путей ускорения процесса обучения при одновременном обеспечении получения устойчивого решения является выбор переменного <img border=«0» width=«18» height=«17» src=«ref-1_1878356414-168.coolpic» v:shapes="_x0000_i1122"> с <img border=«0» width=«40» height=«17» src=«ref-1_1878356750-203.coolpic» v:shapes="_x0000_i1123"> 1 на начальных этапах обучения и <img border=«0» width=«40» height=«17» src=«ref-1_1878356750-203.coolpic» v:shapes="_x0000_i1124"> 0 — на заключительных. К сожалению, такой подход не применим в тех случаях, когда сеть должна непрерывно подстраиваться к предъявляемым ей новым входным сигналам.

2. Рандомизация весов

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

3. Выбор начальных значений векторов весовых коэффициентов и нейронов.

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

На рисунке 2.12 показан случай, когда начальное расположение весов <img border=«0» width=«21» height=«27» src=«ref-1_1878357527-106.coolpic» v:shapes="_x0000_i1125"> и <img border=«0» width=«23» height=«27» src=«ref-1_1878357633-109.coolpic» v:shapes="_x0000_i1126"> привело к тому, что после обучения сети все предъявляемые образы классифицируют нейроны с весами <img border=«0» width=«23» height=«27» src=«ref-1_1878357742-109.coolpic» v:shapes="_x0000_i1127">, <img border=«0» width=«23» height=«27» src=«ref-1_1878357633-109.coolpic» v:shapes="_x0000_i1128">, и <img border=«0» width=«23» height=«29» src=«ref-1_1878357960-109.coolpic» v:shapes="_x0000_i1129">. Веса же <img border=«0» width=«21» height=«27» src=«ref-1_1878357527-106.coolpic» v:shapes="_x0000_i1130"> и <img border=«0» width=«23» height=«27» src=«ref-1_1878357742-109.coolpic» v:shapes="_x0000_i1131"> не изменились и могут быть удалены из сети.
<img border=«0» width=«186» height=«74» src=«ref-1_1878358284-3817.coolpic» v:shapes=«Рисунок_x0020_108»>

а                           б

Рисунок 2.12 – Начальное (а) и конечное (б) положения векторов весов
4. Выбор параметра расстояния <img border=«0» width=«18» height=«17» src=«ref-1_1878362101-165.coolpic» v:shapes="_x0000_i1133">

Если сначала параметр <img border=«0» width=«18» height=«17» src=«ref-1_1878362101-165.coolpic» v:shapes="_x0000_i1134"> выбран малым или очень быстро уменьшается, то далеко расположенные друг от друга нейроны не могут влиять друг на друга. Хотя две части в такой карте настраиваются правильно, общая карта будет иметь топологический дефект (рисунок 2.13).

5. Количество нейронов в слое

Число нейронов в слое Кохонена должно соответствовать числу классов входных сигналов. Это может быть недопустимо в тех задачах, когда число классов заранее известно.

<img border=«0» width=«125» height=«121» src=«ref-1_1878362431-4784.coolpic» v:shapes=«Рисунок_x0020_111»>

Рисунок 2.13 – Топологический дефект карты
6. Классы входных сигналов

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


    продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по информатике