Алгоритмы кластеризация по методу к-средних в пространствах с метрикой Минковского

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

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению
01.03.02 Прикладная математика и информатика

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Алгоритмы кластеризация по методу к-средних в пространствах с метрикой Минковского

Косякина Светлана Станиславовна

Нижний Новгород, 2019



СОДЕРЖАНИЕ

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

Введение

Постановка задачи кластеризация

Метрика Минковского

Нахождение центра Минковского

Описание алгоритмов нахождения центра Минковского

Алгоритм градиентного спуск

Метод инспирированный природой

Основные обозначения

Практическая часть

Алгоритм к-средних

Общее представление алгоритма к-средних

Подробное описание алгоритма с использованием метрики

Минковского

Практическая часть

Эксперимент №1

Эксперимент №2

Эксперимент №3

Заключение

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

Приложения



ВВЕДЕНИЕ

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

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

В статьях Charu C. Aggarwal, Alexander Hinneburg, Daniel A.Keim. On the surprising behavior of distance metrics in high dimensional space / Proceedings of the Eighth International Conference on Database Theory, 2001. Pp. 420-434. Renato Cordeiro de Amorim, Boris Mirkin. Minkowski metric, feature weighting and anomalous cluster initializing in k-means clustering / Journal Elsevier Ltd. All rights reserved, 2011. P. 15. авторы затрагивали тему кластеризации метрикой Минковского, также были предложены некоторые алгоритмы решений, но их конкретное применение описывалось лишь для определённых значений степени больше единицы.

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

Постановка задачи

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

Цели кластеризации:

1) Анализ данных с помощью определения структуры кластера. Обработка данных существенно упрощается с помощью разделения данных на кластеры. Также после разделения на группы можно применять к каждому из полученных кластеров определённые методы.

2) Сокращение данных. Данная выборка объектов может оказаться слишком велика, тогда её можно уменьшить. Это значит, что необходимо оставить только типичные представители каждого кластера.

3) Обнаружение выбросов. То есть обнаружение нестандартных объектов, которые нельзя добавить ни в один кластер.

Существуют различные алгоритмы, которые решают проблему:

1. Иерархические алгоритмы К.В. Воронцов. Лекции по алгоритмам кластеризации и многомерного шкалирования / К.В. Воронцов, 2007, P. 18.

* агломерационные алгоритмы

* разделяющие алгоритмы

2. Неиерархические алгоритмы Д.С. Черезов, Н.А. Тюкачев. Обзор основных методов классификации и кластеризации данных / Вестник ВГУ, серия: системный анализ и информационные технологии, 2009. Р. 29.

* итеративный

* модельный

* концептуальный

* сетевой

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

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

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

Цели исследования

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



ПОСТАНОВКА ЗАДАЧИ КЛАСТЕРИЗАЦИИ

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

Обозначим за некоторую функцию расстояния относительно объектов .

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

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



МЕТРИКА МИНКОВСКОГО

Метрика Минковского является параметрической метрикой на евклидовом пространстве, рассматриваемая в виде обобщения двух расстояний: манхэттенское расстояние, называемое расстоянием городских кварталов и евклидового расстояния. Немецкий математик Герман Минковский первый кто изучил поведение семейства функций расстояния, и именно в честь него и названа данная метрика.

Расстояние Минковского между двумя точками выглядит следующим образом:

Для порядка - расстояние Минковского не является метрикой из-за того, что не выполняются следующие неравенства: неравенства треугольника (если взять одну длину любой из трёх сторон треугольника, то она будет меньше, чем сумма длин двух других сторон этого треугольника).

Для порядка - расстояние Минковского будет являться метрикой.

Для порядка же - расстояние Минковского превращается в расстояние Чебышева:

Метрики расстояний используются для того, чтобы измерить сходство между объектами. При кластеризации в высокой размерности точки становятся малоразличимыми. Использование метрики Минковского со значением степени меньше единицы, как описывается в ранее упомянутой статье Ш. Аггарвала, помогает лучше различать объекты в пространствах высокой размерности. С этой точки зрения, Манхэттенская метрика является более предпочтительной, чем Евклидова метрика



НАХОЖДЕНИЕ ЦЕНТРА МИНКОВСКОГО

Задача состоит в том, что необходимо найти центр в метрике Минковского для любого параметра степени m для данных больших размерностей.

Пусть у нас есть множество значений признака и также задана некоторая величина m, которая является положительной. Возьмём . Теперь необходимо вычислить значение а, которое и будет являться центром Минковского, то есть будет минимизировать критерий Минковского:

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

Описание алгоритмов нахождения центра Минковского

Алгоритм градиентного спуска

Рассмотрим первый из алгоритмов минимизации - градиентный спуск.

Будем опираться на критерий . Для удобства возьмём чётные . Проведём упорядочивание всех чисел из У таким образом, что

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

Доказательство проведём от противного, то есть возьмём, например, . Тогда получается, что , ведь . Рассмотрим , которое находится в интервале от . Рассматриваемый критерий принимает следующий вид:

где - множество индексов таких, при которых значение , - соответственно множество таких идексов при которых

Вычислим производную из

Теперь вычислим вторую производную:

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

Далее представлено описание алгоритма градиентного спуска:

1) Проводится инициализация:

и задаётся шаг , который является положительным ().

2) Вычисляется разность по критерию Минковского

, если найденное значение попало в интервал, то , иначе следует уменьшить и затем повторить шаги до того момента, когда вычисленная разность не попадёт в интервал

3) Затем проверяются на совпадение и с заранее заданной точностью. Если происходит совпадение, то возвращается значение и оно будет являться оптимальным. В случае несовпадения -продолжаются вычисления.

4) Далее проверяется следующее условие:

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



Блок-схема алгоритма градиентного спуска:

Метод инспирированный природой

Вторым алгоритмом для нахождения центра Минковского является метод, инспирированный природой. Реализация данного алгоритма представлена в приложении №4.

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

Описание алгоритма, инспирированного природой:

1) Определяется некоторая область в которой лежат допустимые решения. Среди точек, принадлежащих этой области, есть точка, которая является оптимальным решением или даже несколько оптимальных решений.

2) Затем идёт инициализация популяции:

Задаётся р - размер популяции и выбираются случайным образом точки . Точки, выбранные случайным образом, принадлежат допустимому интервалу.

3) Проводится инициализация “элиты”:

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

4) Осуществляется переход к следующему из поколений:

Добавляется случайный Гауссовый шум:

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

5) Происходит поддерживание “элиты”:

Находятся все значения критерия Минковского для нового поколения и затем выбираются - наилучшее значение и - наихудшее значение. Если значение лучше значения , тогда запоминается в Но если же значение и даже хуже значения тогда заменяется на

6) Условие, при котором происходит остановка алгоритма:

Если полученное количество итераций не превосходит заданного числа итераций, то происходит переход к четвёртому шагу. Иначе, выводится значение “элиты” и это значение будет являться искомым решением.

Далее представлена блок-схема для алгоритма, инспирированного природой:

Для многомерного случая всё рассчитывается аналогично:

Имеется n векторов размерности d

Искомый центр Минковского будет иметь следующий вид:

а = ().

Центр Минковского находится для каждой координаты с помощью минимизации критерия Минковского.

То есть, для первой координаты находим центр:

для второй координаты:

для третьей:

для координаты :

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

Основные обозначения

Step count	Число итераций подсчёта
M	Значение степени, используемой при подсчёте расстояния Минковского
Offset start/end	Диапазон для случайного значения , используемого для зашумления популяции
Best step	Последняя итерация, на которой поменялось значение минимального расстояния
Min distance	Полученное минимальное расстояние от заданных точек до вероятной искомой точки
Found center	Координаты искомого центра

Практическая часть

Эксперимент для одномерных данных:

На вход программы подаётся одномерный вектор из двадцати элементов:

points = {-9; -8; -7; -6; -5; -4; -3; -2; -1; 0; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9}.

И начальный вектор a = {3; -3; 1; -1; 2; -2; 4; -4; 5; -5}.

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

Диапазон для случайного значения был взят в промежутке от 0,01 до 0,05, так как на этом промежутке показывались лучшие результаты.

Такие входные данные были выбраны специально для того, чтобы центр Минковского был равен нулю. Вывод программы изображён на следующих графиках для различных степеней m = 0.2; 0.3; 0.5; 0.7; 2; 10

m=0.2 :

Найденный программой центр Минковского = {-0,000009}. Минимальная дистанция = 90,000017. Полученный результат является ожидаемым, так как данный центр максимально приближен к искомому значению - нулю.

m=2 :

Полученный центр Минковского = {-0,000130}. Минимальная дистанция = 90,000277. Результат также является ожидаемым.

m=10 :

Полученный центр Минковского = {-0,000251}. Минимальная дистанция = 90,000522. Результат является ожидаемым.

В приложении №1 приведён график точности вычислений для степени m = 0.3, в приложении №2 график для степени m = 0.5, а в приложении №3 приведён график для степени m = 0.7.

По приведённым графикам можно сделать вывод о том, что в данном примере все искомые центры Минковского для разных степеней m = 0.2; 0.3; 0.5; 0.7; 2; 10 получились ожидаемыми. В конкретном примере видно, что в одномерном случае с ростом степени ухудшается точность полученного значения центра Минковского, то есть возрастает погрешность. В данном примере для степени m=0.2 - результат получился более точным, чем для других рассматриваемых степеней.



ОПИСАНИЕ АЛГОРИТМА КЛАСТЕРИЗАЦИИ -СРЕДНИХ С МЕТРИКОЙ МИНКОВСКОГО

Общее представление алгоритма -средних.

Алгоритм -средних решает задачу кластеризации данных и относится к алгоритмам машинного обучения.

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

Подробное описание алгоритма -средних с использованием метрики Минковского

Пусть задано:

- набор, состоящий из наблюдений:

.

- и также число кластеров - , где .

Необходимо разбить множество наблюдений кластеров:

таким образом, что

Работа алгоритма:

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

где - это центры кластеров, - функция расстояния между

Программная реализация алгоритма кластеризации по метрике Минковского представлена в приложении №4.

Описание алгоритма:

1) Производим инициализацию кластеров.

Произвольно выбираем множество точек

будем рассматривать в качестве начальных кластеров:

2) Распределяем вектора по кластерам.

Каждая точка относится к кластеру по наименьшему расстоянию до его центра, то есть рассчитывается расстояние между векторами , и центрами кластеров :

3) Пересчитываем центры кластеров.

На данном шаге используется реализованный ранее (в части 4) алгоритм поиска центра Минковского для пересчёта центров кластеров.

4) Проверяем критерий остановки.

Если перестают перемещаться центры кластеров - тогда останавливаемся, иначе переходим ко второму шагу:

и If :

и than

и goto 2.

Далее представлена блок-схема для алгоритма кластеризации k-средних:

Практическая часть

Эксперимент №1

Количество кластеров = 3;

Количество итераций = 100;

Размер популяции = 3;

Даны начальные данные, которые требуется разбить на три кластера. Данные были сгенерированы в виде пятнадцати десятимерных точек с тремя центрами по многомерному нормальному распределению, специально для того, чтобы наглядно показать работу программы алгоритма к-средних для различных степеней m = 0.1; 0.6; 2.0. Данные необходимо разбить на три кластера.

Центр1: 1 1 1 1 1 1 1 1 1 1;

Центр2: 5 5 5 5 5 5 5 5 5 5;

Центр3: 9 9 9 9 9 9 9 9 9 9.

Сгенерированные данные представлены в приложении №5.

Для генерирования данных использовалась ковариационная матрица:

[1 0 0 0 0 0 0 0 0 0,

0 1 0 0 0 0 0 0 0 0,

0 0 1 0 0 0 0 0 0 0,

0 0 0 1 0 0 0 0 0 0,

0 0 0 0 1 0 0 0 0 0,

0 0 0 0 0 1 0 0 0 0,

0 0 0 0 0 0 1 0 0 0,

0 0 0 0 0 0 0 1 0 0,

0 0 0 0 0 0 0 0 1 0,

0 0 0 0 0 0 0 0 0 1]

Для каждого значения степени m = 0.1; 0.6; 2.0 приведено по одному выводу программы, затем представлена средняя точность правильных разбиений на кластеры по двадцати экспериментам.

Разделение на кластеры для m = 0.1:

"[5.0373989319,5.5071348397,5.8217937972,5.2372836053,5.2527306589,5.3004991977,5.2510248466,5.6145986996,5.8118275660,4.4003457591] {size=5}"

"[9.0506814454,9.4006739993,9.4654589075,8.2460454871,9.1296026755,7.9761294264,8.7078789318,8.8995835361,8.4886446981,9.3160676905] {size=5}"

"[1.0536004891,0.0845215244,1.8983202282,0.4726139708,1.4374093799,0.9683685141,1.3320114196,1.2385398635,0.4118210374,0.9127371747] {size=5}"

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

Полученные усреднённые центры по двадцати экспериментам:

"[0.7583939040,1.6726483883,0.9385892021,0.6972810199,1.6472900492,0.5572829388,1.6372738802,0.7112993824,0.7584839208,1.2341662737]"

"[9.6637380083,9.0637478311,9.0673849929,7.6472838842,8.5628473958,8.3729109392,9.1848392901,9.4773200843,8.3671828305,9.8594938499]"

"[5.4783483002,5.9478473802,5.7239919002,5.7493890023,5.8458272110,6.1038924849,5.7483882100,4.9843000103,4.7582939211,4.9858939432]"

Далее представлено усреднённое процентное соотношение по количеству точек в кластере:

5 - 98.5%

4 - 0.75%

6 - 0.75%

Это значит, что точки равномерно распределились по кластерам в 98.5% случаев.

Разделение на кластеры для m = 0.6:

"[9.0406100470,9.2025522685,8.9273207328,8.4652885910,9.1693324721,8.6457665773,9.1991590023,8.8582511029,8.8866459962,8.9435825653] {size=5}"

"[3.2785408042,2.9436084216,3.7398792808,2.5430957501,1.5248983238,3.3673569551,3.5302045650,3.6424689900,1.5863591945,2.5946903486] {size=4}"

"[2.7563499887,2.2508610947,2.8407911542,2.8519534448,3.3204308171,2.1456969274,2.7235244857,3.2168509970,3.4215721615,3.2493543305] {size=6}"

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

Усреднённые центры по двадцати экспериментам:

"[9.1499462312,5.0777002118,9.0595043979,7.9900130429,8.6446814440,6.4028298387,9.3412413313,9.2694401142,8.8936538227,9.5443888887]"

"[5.3568493281,5.9688199841,5.5711459330,9.4463987109,5.4933814149,6.1007614693,5.7684927643,4.8937786368,4.2885833631,4.7014407495]"

"[0.5116632043,1.0173339172,0.9316652806,0.6954287178,1.0491956202,0.5550054131,1.6907847104,0.7677601932,0.7244449685,1.1131654443]"

Усреднённое процентное соотношение по количеству точек в кластере:

5 - 94.4%

3 - 1.2%

7 - 1.2%

4 - 1.6%

6 - 1.6%

Видно, что точки равномерно распределились по кластерам в 94.4% случаев. Отсюда получается, что в данном примере для m = 0.6 алгоритм работает менее точно, чем для степени m = 0.1.

Разделение на кластеры для m = 2:

"[9.0365423650,9.1540852124,8.9994377137,8.9995308131,8.6439716614,8.8130249026,9.2237483556,8.8466384915,8.6490327037,9.1715425942] {size=4}"

"[9.0517000000,9.4006000000,8.6343000000,6.3234000000,11.2515000000,7.9749000000,9.1029000000,8.8986000000,9.8408000000,8.0096000000] {size=1}"

"[2.9652959730,2.5310082598,3.2017885542,2.7293399562,2.5999676678,2.6322252821,3.0452963536,3.3848067718,2.6900496358,2.9864896575] {size=10}"

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

Получились следующие усреднённые центры по двадцати экспериментам:

"[0.5845838290,4.3920012993,0.4030288020,0.7492939940,1.7583824822,0.5883883222,1.5848382919,0.4788383271,5.8969984531,1.9838927485]"

"[5.8959394578,1.8237849953,5.8969694003,5.7858838203,8.7758382110,6.3004873777,5.4888913879,2.7583827726,4.7758458232,4.7482746824]"

"[9.5879347902,9.7483456322,9.0777432311,7.9947384828,8.7539475299,8.9283749284,5.8732664663,9.2765312366,8.4367277497,9.3475645834]"

Усреднённое процентное соотношение по количеству точек в кластере:

5 - 69.8%

3 - 5.8%

10 - 3.1%

7 - 2.8%

4 - 7.9%

6 - 5.5%

1 - 1.9%

0 - 3.2%

В данном случае точки равномерно распределились по кластерам в 69.8% случаев.

Следовательно, полученные эксперименты показывают, что для данного примера алгоритм кластеризации к-средних с метрикой Минковского даёт лучшие результаты для меньших степеней: для степени m = 0.1 алгоритм работает более точно, чем для степени m = 0.6 и для m = 2. Также видно, что для степени m = 2 возрасла погрешность разделения на кластеры. Среднее по количествам точек в кластерах говорит о качестве разбиения на кластеры. То есть чем меньше разных точек присутствует, тем больше происходит точных попаданий в кластеры.

Эксперимент №2

На основе сгенерированных данных по многомерному нормальному распределению вокруг определённых центров были проведены исследования, целью которых было выявление ошибочных переходов данных в чужие кластеры. Cгенерированные данные были получены с помощью среды Matlab.

Ошибка распределения в данном примере - это присутствие в кластере несвойственных ему точек.

Были сгенерированы данные: 150 точек вокруг центров нормального распределения (по 50 точек вокруг каждого центра):

Центр 1: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1;

Центр 2: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4;

Центр 3: 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9.

Для генерирования данных также задавалась ковариационная матрица, которая представлена в приложении №6.

Для сгенерированных данных получен график вероятности хотя бы одной ошибки в зависимости от степени на 100 экспериментов:

По графику видно, что для степени в данном примере вероятность хотя бы одной ошибки равна 0.03, для степени равна 0.07, для равна 0.09, для равна 0.13, для равна 0.17 и для степени вероятность хотя бы одной ошибки равна 0.23. Таким образом, можно сделать вывод о том, что в данном примере вероятность хотя бы одной ошибки возрастает с ростом степени m, то есть чем больше степень, тем больше получается ошибка. Это значит, что в рассмотренном случае алгоритм кластеризации k-средних по метрике Минковского со степенями меньше единицы разбивает данные на кластеры точнее.

Далее центры нормального распределения были приближены друг к другу:

Центр 1: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2;

Центр 2: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4;

Центр 3: 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6.

График вероятности хотя бы одной ошибки в зависимости от степени на 100 экспериментов для сгенерированных данных после сближения:

Полученный график показывает, что для степени в данном примере вероятность хотя бы одной ошибки равна 0.09, для степени равна 0.11, для равна 0.13, для равна 0.24, для равна 0.33 и для степени равна 0.41. По графику можно сделать вывод о том, что вероятность хотя бы одной ошибки в данном случае падает с понижением степени.

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

Эксперимент №3

Для данного эксперимента было сгенерировано 150 точек (по 50 точек вокруг каждого из трёх центров) по многомерному нормальному распределению вокруг центров:

Центр 1: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2;

Центр 2: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4;

Центр 3: 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6.

Для генерирования данных была также задана ковариационная матрица, которая находится в приложении №6.

Все точки были сгенерированы вокруг трёх центров и были помечены соответствующей меткой кластера (- если точка принадлежит кластеру, полученному вокруг центра 1, - кластеру 2 и - кластеру 3 соответственно). Затем запускался алгоритм кластеризации k-средних с использованием метрики Минковского для степеней . На вход алгоритма подавались сгенерированные данные без меток. После работы алгоритм выводил количество объектов каждой метки, которое содержится в каждом из получившихся на выходе трёх кластеров.

Выводы алгоритма представлены в виде Confusion Matrices (Confusion Matrix- это матрица, которая показывает, сколько объектов каждой метки попало в каждый кластер).

Confusion Matrix для степени 0.1:

	L1	L2	L3
Cluster 1	0	50	0
Cluster 2	50	0	0
Cluster 3	0	0	50

Данная матрица иллюстрирует, что 150 исходных точек равномерно распределились по трём кластерам. В первый кластер вошло 50 точек с меткой L₂ , во второй кластер вошло 50 точек с меткой L₁ , а в третий кластер вошло 50 точек с меткой L₃ .

Confusion Matrix для степени 0.3:

	L1	L2	L3
Cluster 1	0	50	0
Cluster 2	0	0	50
Cluster 3	50	0	0

Данные также распределись равномерно по трём кластерам: в первый кластер вошло 50 точек с меткой L₂ , во второй кластер вошло 50 точек с меткой L₃ , а в третий кластер вошло 50 точек с меткой L₁ .

Confusion Matrix для степени 0.5:

	L1	L2	L3
Cluster 1	45	2	4
Cluster 2	2	1	43
Cluster 3	3	47	3

По матрице видно, что для степени m = 0.5 в данном примере некоторые точки попали не в свой кластер: в первый кластер вошло 45 точек с меткой L₁, 2 точки с меткой L₂ и 4 точки с меткой L₃, во второй кластер вошло 2 точки с меткой L₁, 1 точка с меткой L₂ и 43 точки с меткой L₃, а в третий кластер вошло 3 точки с меткой L₁, 47 точек с меткой L₂ и 3 точки с меткой L₃.

Confusion Matrix для степени 1:

	L1	L2	L3
Cluster 1	1	5	39
Cluster 2	9	37	4
Cluster 3	40	8	7

В первый кластер наиболее точно были определёны 39 точек с меткой L₃, во второй кластер - 37 точек с меткой L₂ и в третий кластер - 40 точек с меткой L₁.

Confusion Matrix для степени 2:

	L1	L2	L3
Cluster 1	5	41	2
Cluster 2	35	7	16
Cluster 3	10	2	32

В первый кластер наиболее точно были определёны 41 точка с меткой L₂, во второй кластер - 35 точек с меткой L₁ и в третий кластер - 32 точек с меткой L₃.

Затем была посчитана точность у каждой Confusion Matrix:

Accuracy1 для степени 0.1 = (50+50+50)/150 = 1,

Accuracy2 для степени 0.3 = (50+50+50)/150 = 1,

Accuracy3 для степени 0.5 = (45+43+47)/150 = 0.9,

Accuracy4 для степени 1 = (40+37+39)/150 = 0.77,

Accuracy5 для степени 2 = (35+41+32)/150 = 0.72.

Далее приведён график зависимости точности работы алгоритма от степеней (график строится на основе вычисленных Accuracy1, Accuracy2, Accuracy3, Accuracy4, Accuracy5):

По данному графику можно сделать вывод о том, что для данного эксперимента с уменьшением степени m в алгоритме кластеризации k-средних с метрикой Минковского увеличивается точность вычислений. В приведённом примере более высокая точность достигается для значений степени m=0.1 и m=0.3. Таким образом, график показывает эффективность алгоритма k-средних по метрике Минковского для меньших степеней m в рассматриваемом примере.



ЗАКЛЮЧЕНИЕ

Подводя итоги, можно сделать вывод о том, что для приведённых в работе экспериментов, использование метрики Минковского хорошо подходит для данных больших размеров. Используя показатель степени m меньше единицы, появляется возможность получить более точные результаты в алгоритме кластеризации k-средних с использованием метрики Минковского. Для больших значений степени m могут возникать большие ошибки, но в моей исследовательской работе при использовании степени меньше единицы метрика Минковского в алгоритме кластеризации k-средних показывает более точные результаты. Данные полученные в результате экспериментов были отображены графически. На графиках видно, что точность вычислений падает с увеличением степени m в метрике Минковского.



СПИСОК ЛИТЕРАТУРЫ

1. Котов А., Красильников Н. Кластеризация данных / Котов А., Красильников Н., 2016. P. 16.

2. Колпак Е.А. Вычисления в Matlab / Издательство Бук, 2016. P. 186. ISBN: 978-5-906873-47-7.

3. Миркин Б.Г. Введение в анализ данных / Издательство Юрайт, 2016. - P.174. - ISBN 978-5-9916-5009-0.

4. Сирота А.А. Методы и алгоритмы анализа данных и их Моделирование в Matlab / Издательство БХВ-Петербург, 2016. P.376.- ISBN: 978-5-9775-3778-0.

5. Boris Mirkin. (2010). Core Concepts in Data Analysis: Summarization, Correlation and Visualization / Springer-Verlag London Limited, 2011. Pp. 221 - 281. - ISBN 978-0-85729-286-5.

6. Charu C. Aggarwal, Alexander Hinneburg, and Daniel A. Keim. On the surprising behavior of distance metrics in high dimensional space / Proceedings of the Eighth International Conference on Database Theory, 2001. Pp. 420 - 434.

7. Renato Cordeiro de Amorim, Boris Mirkin. Minkowski metric, feature weighting and anomalous cluster initializing in k-means clustering / Journal Elsevier Ltd. All rights reserved, 2011. P. 15.

8. К.В. Воронцов. Лекции по алгоритмам кластеризации и многомерного шкалирования / К.В. Воронцов, 2007, P. 18.

9. Д.С. Черезов, Н.А. Тюкачев. Обзор основных методов классификации и кластеризации данных / Вестник ВГУ, серия: системный анализ и информационные технологии, 2009. Р. 29.



ПРИЛОЖЕНИЯ

Приложение №1:



Приложение №2:



Приложение №3:



Приложение №4:

#include "engine.h"

#include <memory>

#include <math.h>

#include "common.h"

#include "random.hpp"

#include "minkovsky_model.h"

#include <QDebug>

#include <random>

#include <QMessageBox>

#include <QCoreApplication>

#include <QSet>

using Random = effolkronium::random_static;

using namespace std;

Engine::Engine(shared_ptr<MinkovskyModel> model)

{

mModel = model;

}

void Engine::run()

{

if (mModel->getPoints().empty() || mModel->getA().empty()) {

return;

}

auto M = mModel->getMstart();

for (; M < mModel->getMend(); M += mModel->getMstep()) {

find_center(M);

}

}

void Engine::split_to_clusters()

{

const double experiment_count = 100;

vector<double> m_vector = {0.1, 0.5, 1, 2, 10};

read_from_file();

for (unsigned long i = 0;i<m_vector.size();i++) {

mModel->setMstart(m_vector[i]);

double collisions = 0;

for (uint i=0;i<experiment_count;i++) {

qDebug() << "+++ New iteration " << QString::number(i) << " current collisions: " << QString::number(collisions) << " +++";

generate_cluster_centers(mModel, mClustersFromFile.count());

while (true) {

// qDebug() << "+++ New iteration +++";

distribute_points_to_clusters();

// print_clusters();

auto cluster_centers_before = mClusters.keys();

recalculate_cluster_centers();

mModel->setA(mClusters.keys().toVector().toStdVector());

auto cluster_centers_after = mClusters.keys();

// qDebug() << "Centers are recalculated";

// print_clusters();

bool all_points_stopped = true;

for (int i = 0;i<cluster_centers_after.size();i++) {

auto sum_before = cluster_centers_before.at(i).getCoordSum();

auto sum_after = cluster_centers_after.at(i).getCoordSum();

auto points_diff = abs(sum_before - sum_after);

// qDebug() << "Points diff: " << QString::number(points_diff, 'f', 30);

if (points_diff > 0.000000001) {

// qDebug() << "Continuing calculations";

all_points_stopped = false;

break;

} else {

// qDebug() << "Point stopped moving, looking to others...";

continue;

}

}

if (all_points_stopped) {

// qDebug() << "Clusters are found";

// print_clusters_data();

print_clusters();

auto hasCollisions = analyse_clusters();

if (hasCollisions) {

collisions++;

}

break;

} else {

// qDebug() << "Recalculation...";

continue;

}

}

}

double error_rate = collisions/experiment_count;

qDebug() << "Error rate: " << QString::number(error_rate, 'f', 10) << " with m=" << QString::number(mModel->getMstart(), 'f', 2);

mModel->addMtoZeroProximityEntry(QPointF(mModel->getMstart(), error_rate));

}

}

void Engine::read_from_file()

{

QString path = QCoreApplication::applicationDirPath();

path.append("/points.txt");

QFile points_file(path);

if (!points_file.open(QIODevice::ReadOnly)) {

QMessageBox::information(nullptr, "error", points_file.errorString());

return;

}

mModel->setPoints(read_file(&points_file));

points_file.close();

}

vector<Point> Engine::read_file(QFile *file)

{

QTextStream stream(file);

vector<Point> result;

Point curr_clust_id;

while(!stream.atEnd()) {

QString line = stream.readLine();

if (line.contains(":")) {

QStringList fields = line.split(":");

vector<double> point_v;

QString center_point = fields[1];

QStringList center_point_fields = center_point.split(",");

for (int i=0;i<center_point_fields.size();i++) {

point_v.push_back(center_point_fields.at(i).toDouble());

}

auto point = Point(point_v);

mClustersFromFile.insert(point, {});

curr_clust_id = point;

continue;

}

QStringList fields = line.split(",");

vector<double> point_v;

for (int i=0;i<fields.size();i++) {

point_v.push_back(fields.at(i).toDouble());

}

auto point = Point(point_v);

point.setCluster_num(curr_clust_id.getId());

result.push_back(point);

mClustersFromFile[curr_clust_id].push_back(point);

}

return result;

}

vector<Elite> Engine::min_max_distance(vector<double> points, vector<double> a_points, double current_m)

{

vector<Elite> result;

result.push_back(Elite());

result.push_back(Elite());

result[0].setSum(numeric_limits<double>::max());

result[1].setSum(numeric_limits<double>::min());

for (uint i = 0; i < a_points.size(); i++) {

auto a_point = a_points.at(i);

auto distance = get_distance(points, a_point, current_m);

if (distance < result[0].getSum()) {

result[0].setSum(distance);

result[0].setA_value(a_point);

result[0].setPopulationArrayPosition(i);

}

if (distance > result[1].getSum()) {

result[1].setSum(distance);

result[1].setA_value(a_point);

result[1].setPopulationArrayPosition(i);

}

}

return result;

}

vector<double> Engine::add_noise(vector<double> population)

{

default_random_engine generator;

vector<double> scrumbled;

for (uint i = 0; i < population.size(); ++i) {

normal_distribution<double> distribution(population[i], 0.1);

scrumbled.push_back(distribution(generator));

}

return scrumbled;

}

double Engine::get_distance(vector<double> x, double a, double m)

{

double result = 0;

for (uint i = 0; i < x.size(); i++) {

result += pow(abs(x.at(i) - a), m);

}

return pow(result, 1 / m);

}

double Engine::get_distance(Point a, Point b, double m)

{

double result = 0;

for (uint i = 0; i < a.size(); i++) {

result += pow(abs(a.get(i) - b.get(i)), m);

}

return pow(result, 1 / m);

}

void Engine::distribute_points_to_clusters()

{

mClusters.clear();

for (auto &clust_center : mModel->getA()) {

mClusters.insert(clust_center, {});

}

for (auto &point : mModel->getPoints()) {

auto min_distance = numeric_limits<double>::max();

uint found_i = 0;

for (uint i = 0;i < mModel->getA().size();i++) {

auto dist = get_distance(point, mModel->getA().at(i), mModel->getMstart());

if (dist < min_distance) {

min_distance = dist;

found_i = i;

}

}

auto found_clust_center = mModel->getA().at(found_i);

if (mClusters.contains(found_clust_center)) {

auto cluster = mClusters.value(found_clust_center);

cluster.push_back(point);

mClusters.remove(found_clust_center);

mClusters.insert(found_clust_center, cluster);

}

}

}

QString Engine::build_coordinates_log(Point point)

{

QString dim_log;

auto coordinates = point.getCoordinates();

for (uint k = 0; k < point.size(); ++k) {

dim_log.append(QString::number(coordinates[k], 'f', 10));

if (k != point.size() - 1) {

dim_log.append(",");

}

}

return dim_log;

}

void Engine::print_clusters_data()

{

QHashIterator<Point, vector<Point>> i(mClusters);

while (i.hasNext()) {

i.next();

qDebug() << "Cluster point number: " << i.key().getId();

for (auto &point : i.value()) {

qDebug() << build_coordinates_log(point) << " init clust num: " << point.getCluster_num();

}

}

}

bool Engine::analyse_clusters()

{

if (mClusters.size() < mClustersFromFile.size()) {

return true;

}

QHashIterator<Point, vector<Point>> i(mClusters);

bool hasCollisions = false;

while (i.hasNext()) {

i.next();

QSet<long long> cluster_nums;

for (auto &point : i.value()) {

cluster_nums.insert(point.getCluster_num());

}

qDebug() << "Cluster " << i.key().getId() << " has collisions: " << (cluster_nums.size() > 1 ? "true" : "false");

if (cluster_nums.size() > 1) {

hasCollisions = true;

}

}

return hasCollisions;

}

QString Engine::build_cluster_log(QPair<Point, vector<Point>> cluster)

{

QString result;

result.append("[")

.append(QString(build_coordinates_log(cluster.first)))

.append("] {size=").append(QString::number(cluster.second.size())).append("}");

return result;

}

void Engine::print_clusters()

{

QHashIterator<Point, vector<Point>> i(mClusters);

while (i.hasNext()) {

i.next();

QPair<Point, vector<Point>> pair;

pair.first = i.key();

pair.second = i.value();

qDebug() << build_cluster_log(pair);

}

}

void Engine::find_center(double m)

{

find_center(mModel, m);

}

void Engine::find_center(shared_ptr<MinkovskyModel> model, double m)

{

vector<double> result_point;

auto capacity = model->getPoints()[0].size();

for (uint digit = 0; digit < capacity; digit++) {

vector<double> current_a;

vector<double> current_x;

Elite result;

// auto minDistance = numeric_limits<double>::max();

for (auto &point : model->getA()) {

current_a.push_back(point.get(digit));

}

for (auto &point : model->getPoints()) {

current_x.push_back(point.get(digit));

}

// qDebug() << "Current a = " << build_coordinates_log(current_a);

// qDebug() << "Current x = " << build_coordinates_log(current_x);

// qDebug() << "Bit count = " << QString::number(digit);

for (uint step = 0; step < model->getStepCount(); step++) {

// qDebug() << "Step " << QString::number(step);

auto distance = min_max_distance(current_x, current_a, m);

auto newPop = add_noise(current_a);

auto distanceNew = min_max_distance(current_x, newPop, m);

if (distanceNew[0].getSum() < distance[0].getSum()) {

current_a[distance[0].getPopulationArrayPosition()] = distanceNew[0].getA_value();

result = distanceNew[0];

}

if (distanceNew[1].getSum() > distance[0].getSum()

&& distanceNew[0].getSum() > distance[0].getSum()) {

newPop[distanceNew[1].getPopulationArrayPosition()] = distance[0].getA_value();

result = distance[0];

current_a = newPop;

}

}

// qDebug() << "result_a[" << QString::number(digit) << "] = " << QString::number(result.getA_value());

result_point.push_back(result.getA_value());

}

model->setA({Point(result_point)});

// qDebug() << "Result point: " << build_coordinates_log(result_point);

// double zeroProximity = 0;

// for (uint i = 0;i < result_point.size(); i++) {

// zeroProximity += abs(result_point.at(i));

// }

// model->addMtoZeroProximityEntry(QPointF(m, zeroProximity));

}

void Engine::recalculate_cluster_centers()

{

QHash<Point, vector<Point>> tmp_map;

QHashIterator<Point, vector<Point>> i(mClusters);

while (i.hasNext()) {

i.next();

if (i.value().empty()) {

tmp_map.insert(i.key(), i.value());

continue;

}

auto model = make_shared<MinkovskyModel>(mModel);

model->setPoints(i.value());

generate_cluster_centers(model, 5);

auto a = model->getA();

a.push_back(i.key());

model->setA(a);

find_center(model, model->getMstart());

tmp_map.insert(model->getA().at(0), i.value());

}

mClusters.swap(tmp_map);

}

void Engine::generate_cluster_centers(shared_ptr<MinkovskyModel> model, int count_to_generate)

{

if (model->getPoints().empty()) {

return;

}

vector<Point> result;

for (int i = 0;i < count_to_generate; i++) {

result.push_back(Point());

}

auto capacity = model->getPoints().at(0).size();

for (uint digit = 0; digit < capacity; digit++) {

vector<double> current_coordinate;

for (auto &point : model->getPoints()) {

current_coordinate.push_back(point.get(digit));

}

auto max = numeric_limits<double>::min();

auto min = numeric_limits<double>::max();

for (auto &coord : current_coordinate) {

if (coord > max) {

max = coord;

}

if (coord < min) {

min = coord;

}

}

for (auto &result_p : result) {

result_p.append(Random::get(min, max));

}

}

model->setA(result);

}



Приложение №5:

0.5140,1.0186,0.3695,2.3936,3.6378,-0.5313,1.6901,1.0092,1.2528,0.3136

1.1606,2.8492,0.1493,0.6888,1.9914,1.1817,-0.2584,0.3180,-1.2497,1.1095

1.7291,1.5147,0.9299,1.6805,0.8783,0.3901,-0.0291,1.1781,0.3014,2.0983

0.2685,-1.0736,2.3549,0.6982,1.0494,1.3494,2.8523,0.7909,0.6193,-1.4784

2.9278,-0.3221,1.6538,0.0248,1.7849,0.5517,1.7680,0.7676,0.7242,0.6431

3.5947,6.0602,5.5689,4.0397,3.7351,4.0015,2.9527,4.8890,4.1708,4.7005

5.1921,4.0840,6.1236,5.4480,6.7485,5.3216,3.2359,4.1451,6.9851,5.9373

5.1582,4.7775,5.1554,5.5001,6.2765,5.9530,5.4881,5.3827,4.6819,3.9027

4.4272,5.9704,4.5675,5.1567,5.4934,5.5156,5.5817,5.2202,4.2864,5.3072

5.3569,6.9175,2.7871,5.7855,4.7458,6.1007,4.9376,4.9409,4.9134,4.7974

10.2006,10.7870,8.4682,7.8555,9.3479,9.5654,9.3425,9.0856,8.5190,9.9668

9.1507,7.5802,10.0686,9.3081,8.6872,8.4031,9.4475,10.6294,8.8940,9.5443

8.0847,10.0533,8.3409,8.6713,7.2592,9.2790,9.7815,9.6382,9.0750,7.5798

8.7279,9.0779,9.0573,7.9905,8.6442,8.6064,7.8406,8.8218,9.9927,9.4805

11.1320,8.4657,9.4999,11.2295,8.4686,7.1823,8.7118,9.2667,7.9395,8.9662



Приложение №6

[ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

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