1 Введение

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

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

Существует несколько основных методов разбиения групп объектов на кластеры. В данной статье описан кластеризатор на основе нейронной сети Кохонена.

2 Нейронная сеть Кохонена

Искусственная нейронная сеть Кохонена [1] или самоорганизующаяся карта признаков (SOM) была предложена финским исследователем Тойво Кохоненом в начале 1980-х годов.

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

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

2.1 Функционирование сети

Система работает по принципу соревнования [2] – нейроны второго слоя соревнуются друг с другом за право наилучшим образом сочетаться с входным вектором сигналов, побеждает тот элемент-нейрон, чей вектор весов ближе всего к входному вектору сигналов. За меру близости двух векторов можно взять квадрат евклидова расстояния(1). Таким образом, каждый входной вектор относится к некоторому кластерному элементу.

(1)

2.2 Обучение сети

Для обучения сети Кохонена используется соревновательный метод[1, 2]. На каждом шаге обучения из исходного набора данных случайно выбирается один вектор. Затем производится поиск нейрона выходного слоя, для которого расстояние между его вектором весов и входным вектором - минимально.

По определённому правилу производится корректировка весов для нейрона-победителя и нейронов из его окрестности, которая задаётся соответствующей функцией окрестности. В данном случае в качестве функцией окрестности была использована функция Гаусса (2).

Рис. 2: функция Гаусса

(2)

где u - номер нейрона в двумерной решетке второго слоя сети, для которого вычисляем значение h;
c - номер нейрона-победителя в двумерной решетке второго слоя сети;
t - параметр времени;

Радиус окрестности h должен уменьшаться с увеличением параметра времени .

Алгоритм обучения сети Кохонена выглядит следующим образом:

1. Инициировать матрицу весов малыми случайными значениями (на отрезке [-1,1]).


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


3. Выбрать первый необработанный элемент x из очереди.


4. Для каждого выхода j вычислить расстояние d_j (1) между его вектором весов w_j и входным вектором x.
   


5. Найти номер выходного нейрона j_m с минимальным расстоянием d_j
   


6. Вычислить изменение весов ΔW = {Δw_u} для всех нейронов u выходного слоя

   (3)

   где
   c - номер (пара индексов) нейрона победителя j_m в двумерной решетке второго слоя;
   u - номер (пара индексов) нейрона с вектором весов w_u в двумерной решетке второго слоя;
   w_u - вектор весовых коэффициентов связи входного слоя и выходного нейрона номер u;
   x - текущий вектор входов сети;
   h(u,c,t) - значение функции окрестности для нейрона номер u в момент времени t;
   η - коэффициент скорости обучения;



7. скорректировать матрицу весов


8. пометить элемент входной очереди x как обработанный


9. если в очереди остаются не обработанные точки
   то переход на п.3


10. если критерий остановки обучения не достигнут
    то переход на п.2


11. конец

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

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


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


• Изменения весов становятся незначительными.

3 Реализация

Результат работы алгоритма зависит от начальных значений его параметров.

Определим функцию оценки Q качества работы кластеризатора.

Q= c ^. d_i / d_o

где

c – количество кластеров;
d_i – среднее внутрикластерное расстояние;
d_o – среднее межкластерное расстояние;

Для получения наилучшего результата можно несколько раз выполнить алгоритм кластеризации, после чего выбрать результат с наименьшим значением.

Рис. 1: начальное состояние

Рис. 2: результат кластеризации: нейронов - 4, кластеров - 4, Q=0.35

 
 

Рис. 3: результат кластеризации: нейронов - 4, кластеров - 4, Q=0.06

Рис. 4: результат кластеризации: нейронов - 9, кластеров - 7, Q=0.04

 
 

Реализация в системе Octave [  здесь  ].
 

Реализация на языке C [  здесь  ].

 
 

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

При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.