Участник:Адиев Тохтар/Алгоритм кластеризации, основанный на сетях Кохоннена

Алгоритм кластеризации, основанный на сетях Кохонена

Алгоритм кластеризации, основанный на сетях Кохонена
Последовательный алгоритм
Последовательная сложность	[math]O(NMn)[/math]
Объём входных данных	v
Объём выходных данных	v
Параллельный алгоритм
Высота ярусно-параллельной формы	v
Ширина ярусно-параллельной формы	v

Рис.1

Основные авторы описания: Логвиненко Александра 613 и Адиев Тохтар 616

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Рис.2 Массив узлов в двумерной SOM сетке.

Cамоорганизующиеся карты Кохонена (Self-Organizing Map (SOM)), представляет собой вычислительный метод, представленный финским ученным Теуво Кохоненом в 1984 году, для визуализации и анализа многомерных данных, прежде всего для экспериментально полученной информации.

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

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

Рис.3 a)

Рис.3 б)

SOM подразумевает использование упорядоченной структуры нейронов. Обычно используются одно и двумерные сетки. При этом каждый нейрон представляет собой [math]n[/math]-мерный вектор-столбец [math] w= [w_1,...,w_n]^T [/math], где [math]n[/math] определяется размерностью исходного пространства (размерностью входных векторов). Применение одно и двумерных сеток связано с тем, что возникают проблемы при отображении пространственных структур большей размерности (при этом опять возникают проблемы с понижением размерности до двумерной, представимой на мониторе). Обычно нейроны располагаются в узлах двумерной сетки с прямоугольными или шестиугольными ячейками. При этом, как было сказано выше, нейроны также взаимодействуют друг с другом. Величина этого взаимодействия определяется расстоянием между нейронами на карте. На рисунках а) и б) дан пример расстояния для шестиугольной и четырехугольной сеток.

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

Алгоритм обучения Кохонена и карты Кохонена послужили основой для большого количества исследований в области нейронных сетей, благодаря чему Кохонен считается самым цитируемым финским ученым. Количество научных работ по картам Кохонена составляет около 8 000. Т. Кохонен — автор более 300 публикаций и 4 монографий

Общим недостатком всех рассмотренных алгоритмов обучения нейронной сети Кохонена является наличие в них большого числа эвристических параметров и искусственность предлагаемых решений проблемы «мертвых» нейронов.

Структура алгоритма - двухслойная нейронная сеть.

1.2 Математическое описание алгоритма

Каждый нейрон сети соединен со всеми компонентами n - мерного входного вектора [math] x(t)=[\xi_1(t),\xi_2(t),...,\xi_n(t)][/math] Входной вектор— это описание одного из объектов, подлежащих кластеризации. Количество нейронов совпадает с количеством кластеров, которое должна выделить сеть.

Каждый j-ый нейрон описывается вектором весов [math] w_j(t)=(w_{j1}(t),...,w_{jn}(t))[/math], где n– число компонентов входных векторов.

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

1.2.1 Алгоритм обучения

шаг 0: Подача исходных данных на входы. Весовой вектор [math]w[/math] выбирается случайным образом. Величины [math] \alpha [/math], [math] h_{kc}[/math] известны.

шаг 1: Выбрать произвольное наблюдение [math] x ( t ) [/math] из множества входных данных.

шаг 2: Определить расстояние между между входным вектором и каждого вектора весовых коэффициентов

[math] d_k(t)=||x(t)-w_k(t)||, k=1,...,n[/math],

шаг 3: Определение нейрона -победителя (веса которого в наименьшей степени отличаются от соответствующих компонентов входного вектора)

[math] d_w(t)=\min\limits_{k}(d_k(t)), k=1,...,n[/math]

шаг 4: Векторы весовых коэффициентов обновляются с помощью функции соседства по формуле

[math] w_k(t+1)=w_k(t)+\alpha(t)h_{kc}(t)||x(t)-w_k(t)||,[/math]

шаг 5: Прекратите, если максимальное число итераций достигнуто; в противном случае изменить параметры [math] \alpha [/math] и [math] h_{kc} [/math] продолжите с шага 1 .

Переменные

• [math]t [/math] -текущая итерация
• [math]\lambda [/math] -предельное значение итераций
• [math]x(t)[/math] -вектор входных данных
• [math]k[/math] -индекс узла в карте
• [math]w_k[/math] -текущий вектор веса в узле k
• [math]c[/math] -индекс нейрона-победителя
• [math] h_{kc}(t)[/math]- функция "соседства", определяет расстояние между нейроном [math] w_k [/math] и [math] w_c [/math]
• [math]\alpha (t)[/math]- монотонно убывающий коэффициент обучения .
• [math]M [/math]- число входных векторов в обучающейся выборке
• [math]N[/math] -число нейронов
• [math]n[/math] - размерность входных векторов

Инициализация начальных весов

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

• Инициализация случайными значениями, когда всем весам даются малые случайные величины.

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

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

Задание [math]h[/math]

Часто в качестве функции соседства используется гауссовская функция:

• [math]h_{kc}(t)=\alpha(t)\cdot\exp(-\frac{\|r_c-r_k\|^2}{2\sigma^2(t)})[/math]

где [math]0\lt \alpha(t)\lt 1[/math] — обучающий сомножитель, монотонно убывающий с каждой последующей итерацией (то есть определяющий приближение значения векторов веса нейрона-победителя и его соседей к наблюдению; чем больше шаг, тем меньше уточнение);
[math]r_k[/math], [math]r_c[/math] — координаты узлов [math]W_k(t)[/math] и [math]W_c(t)[/math] на карте;

[math]\sigma(t)[/math] — сомножитель, уменьшающий количество соседей с итерациями, монотонно убывает. Параметры [math]\alpha[/math], [math]\sigma[/math] и их характер убывания задаются аналитиком.

Более простой способ задания функции соседства:

• [math]h_{kc}(t)=\alpha(t)[/math],

если [math]W_k(t)[/math] находится в окрестности [math]W_c(t)[/math] заранее заданного аналитиком радиуса, и 0 в противном случае. Функция [math]h(t)[/math] равна [math]\alpha(t)[/math] для BMU и уменьшается с удалением от BMU.

Задание [math]\alpha[/math]

Функция обучения обычно задается следующим образом

• [math]\alpha(t)=\alpha_0 \cdot \exp(\frac{-t}{\tau_\alpha})[/math]

• [math]\alpha(t)=\alpha_0 \cdot (1-\frac{t}{T})[/math]

1.3 Вычислительное ядро алгоритма

Вычислительная сложность SOM как правило, высока, что зависит от конструкции слоя, участвующего в алгоритме;

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

Вычислительная сложность сети SOM [math]O(NMn)[/math],

где [math]M[/math] –число векторов в обучающей выборке , [math]N[/math] - число нейронов в слое Кохонена, [math]n[/math] – размерность входных векторов.

Если [math]M[/math]=[math]N[/math], то [math]O(N^2n)[/math]

1.4 Макроструктура алгоритма

Некоторые алгоритмы, относящиеся к семейству Кохонена могут быть суммированы следующими тремя фазами:

• Фаза [math] D [/math] вычисляет расстояние между входом и вектором весовых коэффициентов с помощью уравнения в шаге 1, возвращает матрицу [math] D [/math]
• Фаза [math] W [/math] вычисляет нейрон-победителя уравнением в шаге 2, и возвращает вектор [math] b [/math]
• Фаза [math] U [/math] обновляет вес по уравнению в шаге 3, используя уравнение для функции соседства.

Также выполняются такие макрооперации как:

• умножение вектора на скаляр
• поиск минимального элемента
• сложение векторов
• скалярное произведение векторов

1.5 Схема реализации последовательного алгоритма

1. Задать параметры [math] \alpha_0, \sigma_0,\tau_1,\tau_2,k,t_{max} [/math]
   
2. Инициализировать все [math]w\in W [/math] случайным образом
   
3. for [math]t=1[/math] to [math]t_{max}[/math] do
   
   1. Выбрать случайно [math]\mathbf{x}\in D[/math]
      
   2. Найти [math] \mathbf{w}[/math] так, что [math] d(\mathbf{x},\mathbf{w})= min\{d(\mathbf{x},\mathbf{w})|\mathbf{x}\in D\} [/math]
      
   3. for all [math] \mathbf{w}[/math] в функции [math] h[/math] do
      
   4. Обновить вектор весов по формуле [math]\mathbf{w}=\mathbf{w}+\alpha h(\mathbf{x}-\mathbf{w})[/math]
      
   5. Уменьшить коэффициент обучаемости [math]\alpha [/math]
      
4. end for
   
5. end for
   

1.6 Последовательная сложность алгоритма

• Во время выполнения фазы [math]\mathbf{ D} [/math] треуется выполение [math] O(NMn) [/math] операций
• Во время выполения фазы [math]\mathbf{ W} [/math] выполняется [math]O(M-1)[/math] сравнение

1.7 Информационный граф

Следующий граф описывает выполнение алгоритма в общем виде

Рис.4 Граф для формального выполнения алгоритма

Основными узлами графа были выбраны следующие операции:

• [math]||x-w||[/math] - нахождение евклидового расстояния между вектором [math]\mathbf{x} [/math] и вектором весов [math]\mathbf{w}[/math]
• min - нахождение минимального расстояния из всех полученных расстояний
• Фаза U - обновление значения весов

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

Детально граф выглядит так:

Рис.5 Информационный граф выполнения алгоритма

1.8 Ресурс параллелизма алгоритма

Рис.6 Схема параллелизации на уровне слоя

Основные уровни, где проводится параллелизации при фазе обучения:

1. уровень фазы обучения
2. уровень обучающей выборки
3. уровень слоя
4. уровень нейрона
5. уровень весов

Все эти уровни параллелизации находятся в нейронной сети и могут использоваться одновременно

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

Рис.7 Схема параллелизации фазы обучения

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

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

Таким образом, сложность параллельных вычислений расстояний [math]O(Mn)[/math]. Тем не менее, вычисления минимальных расстояний выполняются последовательно (в рамках одного процесса отсутствуют расстояния до всех нейтронов), и сложность равна [math]O(MN)[/math]. Сложность же обновления весов процесса корректирования равна [math]O(Mn)[/math]. В результате всего вышеописанного оценка параллельной сложности алгоритма равна [math]O(M(N+n))[/math]

1.9 Входные и выходные данные алгоритма

Входные данные алгоритма:

• [math]\{X_i\}\in\mathbb{R}^n[/math] - обучающая выборка

- векторы данной выборки размерности [math]n[/math] образуют матрицу [math]\mathbf{X} \in \mathbb{R}^{M \times n}[/math] из [math]M[/math] обучающих векторов

• [math]h_{kc}[/math] - расстояние между нейронами (положения нейронов на карте)
• [math]\alpha[/math] - коэффициент обучения
• количество итераций [math]t[/math]

Вычислительная сложность хранения входных данных равна [math]O(Mn)[/math].

Выходные данные алгоритма:

• матрица [math]\mathbf{W}[/math], представляющая веса нейронов [math]{w}_j[/math]

Вычислительная сложность хранения выходных данных равна [math]O(Nn)[/math].

1.10 Свойства алгоритма

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

Упорядоченное отображение элементов данных облегчает понимание структур в наборе данных.

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

Визуализация кластеров.

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

Преимущества

• Простой и легкий для понимания алгоритм, который работает.
• Топологическая кластеризация
• Бесконтрольный алгоритм, который работает с нелинейным набором данных.
• Отличная возможность для визуализации многомерных данных на 1 или 2-мерные пространства делает его уникальным в плане уменьшения размерности.

• Также стоит отметить и следующие моменты:

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

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

Недостатки

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

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

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

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

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Последовательные реализации:

• R Supervised and Unsupervised Self-Organising Maps for R.
• Java: Self-Organizing Maps in Java.
• Python:Basic implementations of Kohonen-style vector quantizers for Python
• Matlab: A Matlab toolbox for Self-Organizing Maps (SOM) and others.
• JKNNL: Java Kohonen Neural Network Library.
• C++: C++ Kohonen Neural Network Library.

Параллельные реализации:

• MapReduce-MPI: Parallel implementation of Self-Organizing Map (SOM) algorithm with MapReduce-MPI.
• Somoclu: Massively parallel self-organizing maps: accelerate training on multicore CPUs, GPUs, and clusters.
• Parallel-SOM: Parallel Implementation of Self Organzing Map in OpenCL.