Выделение класса объекта по ряду признаков (кластеризация) с помощью нейронных сетей Кохонена

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

Министерство образования и науки Российской Федерации

Казанский национальный исследовательский технический университет имени А.Н. Туполева - КАИ

кафедра АСОИУ

Курсовая работа

по дисциплине «Интеллектуальный анализ данных»

Выделение класса объекта по ряду признаков (кластеризация) с помощью нейронных сетей Кохонена

Выполнил:

студент гр. 4297

Павлов А.Д.

Проверил:

профессор кафедры АСОИУ

Ризаев И.С.

Казань 2016



Содержание

кластеризация квантование сеть кохонен

Аннотация

Summary

1. Теоретическое обоснование

2. Алгоритм решения

Вывод

Литература

Приложение



Аннотация

В проекте разработана система, производящая кластеризацию объектов по ряду признаков.

Исходными данными являются 6 входных изображений, предназначенных для обучения системы, после обучения входными данными могут являться любые изображения в формате *.png размером 45 x 45 пикселей, содержащих изображения цифр от 0 до 5.

Система основана на сети Кохонена. Количество нейронов равно количеству кластеров сети (т.к. на вход подается 6 цифр, количество кластеров равно 6). Каждый нейрон имеет 2025 (т.к. размер изображения - 45 * 45) входов. Выбор конечного результата осуществляется по правилу WTA (Winner Takes All).



Summary

The project developed a system producing clustered objects on a number of features.

The initial data are 6 input images for the training system, after the training input data can be any image in the format * .png size of 45 x 45 pixels containing images of numbers from 0 to 5.

The system based on Kohonen network. The number of neurons is equal to the number of network clusters (since the input is 6 digits, the number of clusters is equal to 6). Each neuron has a 2025 (as the picture size - 45 * 45) inputs. Selection of the result based on the WTA rule (Winner Takes All).

1. Теоретическое обоснование

Сети (слои) Кохонена (Kohonen T.) [1] относятся к самоорганизующимся нейронным сетям. Самоорганизующаяся сеть позволяет выявлять кластеры (группы) входных векторов, обладающих некоторыми общими свойствами. Кластеризация -- это разделение исследуемого множества объектов на группы «похожих «объектов, называемых кластерами. Синонимами термина «кластер» (англ. Cluster -- сгусток, пучок, группа) являются термины класс, таксон, сгущение. Задача кластеризации принципиально отличается от задачи классификации. Решением задачи классификации является отнесение каждого из объектов к одному из заранее определенных классов. В задаче кластеризации происходит отнесение объекта к одному из заранее неопределенных классов. Разбиение объектов по кластерам осуществляется при одновременном формировании кластеров. Кластеризация позволяет сгруппировать сходные данные, что облегчает решение ряда задач Data Mining:

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

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

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

Формально задача кластеризации описывается следующим образом. Дано множество объектов I = {i1, i2,..., in}, каждый из которых характеризуется вектором x, j = 1,2,3,n атрибутов (параметров):

хj = {Xj1, Хj2, xjm}.

Требуется построить множество кластеров C и отображение F множества I на множество C, то есть F: I -> C. Задача кластеризации состоит в построении множества

C = {C1, C2, ***, Ck, ***, Cg},

где ck -- кластер, содержащий "похожие" объекты из множества I:

Где сигма -- величина, определяющая меру близости для включения объектов в один кластер, d (ij, ip) -- мера близости между объектами, называемая расстоянием. Если расстояние d (ij, ip) меньше некоторого значения сигма, то объекты считаются близкими и помещаются в один кластер. В противном случае считается, что объекты отличны друг от друга и их помещают в разные кластеры. Это условие известно как гипотеза компактности.

Кластеризация основана на использовании расстояния между векторами. Неотрицательное число d(x, y) называется расстоянием (метрикой) между векторами x и у, если выполняются следующие условия:

d (x, у ) > 0 для всех x и у.

d (x, у ) = 0, тогда и только тогда, когда x = у.

d (x, у ) = d (у, x).

d (x, у) < d (x, k) + d (k, у) -- неравенство треугольника.

В сетях Кохонена обычно применяется евклидово расстояние

Сеть (слой) Кохонена (рис. 1) -- это однослойная сеть, построенная из нейронов типа WTA (Winner Takes All -- победитель получает все).

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

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

где j -- номер нейрона, i -- номер входа, sj -- выход адаптивного сумматора, wij -- вес i -го входа j -го нейрона, bj -- порог.

Каждый j -ый нейрон описывается вектором весов w j = (w1 j, w2 j, ..., wmj), где m - число компонентов входных векторов. С выходов адаптивных сумматоров сигнал поступает на функцию конкуренции, работающую по правилу "победитель получает всё". Функция конкуренции находит выход адаптивный сумматор с максимальным значением выхода. Пусть к -- номер такого сумматора. Тогда на выходе сети формируется выходной сигнал ук = 1, остальные выходные сигналы равны нулю. Если максимум достигается одновременно на выходах нескольких сумматоров, то выходной сигнал, равный единице, соответствует одному из них, например, первому.

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

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

Конкурирующая функция активации анализирует значения сумматоров и формирует выходы нейронов, равные 0 для всех нейронов, кроме одного "нейрона-победителя", имеющего на выходе максимальное значение. Таким образом, вектор выхода имеет единственный элемент, равный 1, который соответствует нейрону-победителю, а остальные равны 0. Номер активного нейрона определяет ту группу (кластер), к которой наиболее близок входной вектор.

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

Подача исходных данных на входы. Обычно это случайная выборка одного из входных векторов.

Нахождение выхода каждого нейрона.

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

Корректировка весов "выигравшего" нейрона по правилу Кохонена



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

2. Алгоритм решения

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

Пример работы представлен на рис. 2-3.

Рис. 2. Пример работы программы

Рис. 3. Пример работы программы



Вывод

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



Литература

1. В.И. Горбаченко Самоорганизация в нейронных сетях. Электронный ресурс: http://gorbachenko.self-organization.ru/articles/Self-organizing_map.pdf.

2. И.С. Ризаев, К.В. Потапова, Е.В. Январева Группировка объектов на основе кластерного анализа.



Приложение

public class NeuroNet

{

public int inputs = 0;

public List<Neuron> neurons;

public NeuroNet(int inputs_, int neurons_)

{

neurons = new List<Neuron>();

inputs = inputs_;

for (int i = 0; i < neurons_; i++)

{

Neuron neuron = new Neuron(i, inputs_);

neurons.Add(neuron);

}

}

}

public class Neuron

{

public int number = 0;

public List<double> weights;

public Neuron(int number_, int inputs_)

{

weights = new List<double>();

number = number_;

Random rand = new Random();

for (int i = 0; i < inputs_; i++)

{

weights.Add(rand.NextDouble());

}

}

}

public static class Processing

{

public static double[] ImageToVector(Bitmap img)

{

int size = img.Size.Height * img.Size.Width;

double[] vector = new double[size];

int i = 0;

for (int x = 0; x < img.Size.Width; x++)

{

for (int y = 0; y < img.Size.Height; y++)

{

Color pixel = img.GetPixel(x, y);

Byte lum = (Byte)((pixel.R * 77 + pixel.G * 151 + pixel.B * 28) >> 8);

vector[i++] = 1.0d - lum / 255.0d;

}

}

return vector;

}

public static int Check(NeuroNet net, double[] inputVector)

{

double minDistance = EuclideanDistance(net.neurons[0], inputVector);

int bmuIndex = 0;

for (int i = 1; i < net.neurons.Count; i++)

{

double tmpED = EuclideanDistance(net.neurons[i], inputVector);

if (tmpED < minDistance)

{

bmuIndex = i;

minDistance = tmpED;

}

}

return bmuIndex;

}

public static void Study(ref NeuroNet net, double[][] inputVector)

{

for (int k = 0; k < 6; k++)

{

//double minDistance = EuclideanDistance(net.neurons[0], inputVector[k]);

//int bmuIndex = 0;

//for (int i = 1; i < net.neurons.Count; i++)

//{

// double tmpED = EuclideanDistance(net.neurons[i], inputVector[k]);

// if (tmpED < minDistance)

// {

// bmuIndex = i;

// minDistance = tmpED;

// }

//}

for (int i = 0; i < net.neurons.Count; i++)

{

for (int g = 0; g < inputVector[k].Length; g++)

{

//double hfunc = hc(k, net.neurons[bmuIndex].weights[g], net.neurons[i].weights[g]);

//double normfunc = NormLearningRate(k);

net.neurons[i].weights[g] = net.neurons[i].weights[g] + 0.5 * (inputVector[i][g] - net.neurons[i].weights[g]);

}

}

//for (int y = 0; y < 6; y++)

//{

// richTextBox1.Text += "Евклидово расстояние " + y + "-го нейрона между " + y + "-м входным вектором на " + k + "-ой итерации: " + EuclideanDistance(net.neurons[y], inputVector[y]) + Environment.NewLine;

//}

//richTextBox1.Text += Environment.NewLine;

}

}

private static double hc(int k, double winnerCoordinate, double coordinate)

{

double dist = Distance(winnerCoordinate, coordinate);

double s = Sigma(k);

return Math.Exp(-dist * dist / (2 * Sqr(Sigma(k))));

}

private static double Sigma(int k)

{

return 1 * Math.Exp(-k / 5);

}

private static double NormLearningRate(int k)

{

return 0.1 * Math.Exp(-k / 1000);

}

private static double EuclideanDistance(Neuron neuron, double[] InputVector)

{

double Sum = 0;

for (int i = 0; i < InputVector.Length; i++)

{

Sum += Sqr(InputVector[i] - neuron.weights[i]);

}

return Math.Sqrt(Sum);

}

private static double Distance(double winnerCoordinate, double Coordinate)

{

return Math.Sqrt(Sqr(winnerCoordinate - Coordinate));

}

private static double Sqr(double value)

{

return value * value;

}

}

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