Что такое k means

Реализация алгоритма k-means (k-средних) на примере работы с пикселями

Всем привет! Недавно нужно было написать код для реализации сегментации изображения с помощью метода k – средних (англ. k-means). Ну, первым делом Google в помощь. Нашел много информации, как и с математической точки зрения (всякие там сложные математические каракули, хрен поймёшь, что там написано), так и некоторые программные реализации, которые есть в английском интернете. Эти коды конечно прекрасны – спору нет, но саму суть идеи сложно поймать. Как – то оно там все сложно, запутано, да и пока сам, ручками, не пропишешь код, ничего не поймешь. В этой статье хочу показать простую, не производительную, но, надеюсь, понятную реализацию этого чудесного алгоритма. Ладно, погнали!

Итак, что такое кластеризация с точки зрения нашего восприятия? Приведу пример, допустим, есть милое изображение с цветочками с дачи твоей бабушки.

Есть много алгоритмов кластеризации, но самый простой из них — k – средних, о котором дальше и пойдет речь. K-средних – простой и эффективный алгоритм, который легко реализовать программным методом. Данные, которые мы будем распределять по кластерам — пиксели. Как известно, цветной пиксель имеет три составляющих — red, green и blue. Наложение этих составляющих и создает палитру существующих цветов.

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

На примере пикселей мы и реализуем наш алгоритм. K-средних – итерационный алгоритм, то есть он даст правильный результат, после энного количества повторов некоторых математических вычислений.

Алгоритм

Реализация

Реализовывать данный проект я буду на С++. Первый файл – «k_means.h», в нем я определил основные типы данных, константы, и основной класс для работы — «K_means».
Для характеристики каждого пикселя создадим структуру, которая состоит из трех составляющих пикселя, для которых я выбрал тип double для более точных расчетов, а также определил некоторые константы для работы программы:

Пробежимся по составляющим класса:

vectorpixcel — вектор для пикселей;
q_klaster – количество кластеров;
k_pixcel – количество пикселей;
vectorcentr – вектор для центров кластеризации, количество элементов в нем определяется q_klaster;
identify_centers() – метод для случайного выбора начальных центров среди входных пикселей;
compute() и compute_s() встроенные методы для расчета расстояния между пикселями и пересчета центров соответственно;
три конструктора: первый по умолчанию, второй — для инициализации пикселей из массива, третий — для инициализации пикселей из текстового файла (в моей реализации сначала файл случайно заполняется данными, и потом с этого файла считываются пиксели для работы программы, почему не напрямую в вектор – просто так нужно в моем случае);
clustering(std::ostream & os) – метод кластеризации;
метод и перегрузка оператора вывода для публикации результатов.

Это метод для выбора начальных центров кластеризации и добавления их в вектор центров. Осуществляется проверка на повтор центров и замена их в этих случаях.

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

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

Основной метод кластеризации.

Вывод начальных данных.

Пример вывода

Начальные пиксели:
255 140 50 — №0
100 70 1 — №1
150 20 200 — №2
251 141 51 — №3
104 69 3 — №4
153 22 210 — №5
252 138 54 — №6
101 74 4 — №7

Случайные начальные центры кластеризации:
150 20 200 — #0
104 69 3 — #1
100 70 1 — #2

Количество кластеров: 3
Количество пикселей: 8

Расстояние от пикселя 0 к центру #0: 218.918
Расстояние от пикселя 0 к центру #1: 173.352
Расстояние от пикселя 0 к центру #2: 176.992
Минимальное расстояние к центру #1
Пересчитываем центр #1: 179.5 104.5 26.5
Расстояние от пикселя 1 к центру #0: 211.189
Расстояние от пикселя 1 к центру #1: 90.3369
Расстояние от пикселя 1 к центру #2: 0
Минимальное расстояние к центру #2
Пересчитываем центр #2: 100 70 1
Расстояние от пикселя 2 к центру #0: 0
Расстояние от пикселя 2 к центру #1: 195.225
Расстояние от пикселя 2 к центру #2: 211.189
Минимальное расстояние к центру #0
Пересчитываем центр #0: 150 20 200
Расстояние от пикселя 3 к центру #0: 216.894
Расстояние от пикселя 3 к центру #1: 83.933
Расстояние от пикселя 3 к центру #2: 174.19
Минимальное расстояние к центру #1
Пересчитываем центр #1: 215.25 122.75 38.75
Расстояние от пикселя 4 к центру #0: 208.149
Расстояние от пикселя 4 к центру #1: 128.622
Расстояние от пикселя 4 к центру #2: 4.58258
Минимальное расстояние к центру #2
Пересчитываем центр #2: 102 69.5 2
Расстояние от пикселя 5 к центру #0: 10.6301
Расстояние от пикселя 5 к центру #1: 208.212
Расстояние от пикселя 5 к центру #2: 219.366
Минимальное расстояние к центру #0
Пересчитываем центр #0: 151.5 21 205
Расстояние от пикселя 6 к центру #0: 215.848
Расстояние от пикселя 6 к центру #1: 42.6109
Расстояние от пикселя 6 к центру #2: 172.905
Минимальное расстояние к центру #1
Пересчитываем центр #1: 233.625 130.375 46.375
Расстояние от пикселя 7 к центру #0: 213.916
Расстояние от пикселя 7 к центру #1: 150.21
Расстояние от пикселя 7 к центру #2: 5.02494
Минимальное расстояние к центру #2
Пересчитываем центр #2: 101.5 71.75 3

Проведем классификацию пикселей:
Расстояние от пикселя №0 к центру #0: 221.129
Расстояние от пикселя №0 к центру #1: 23.7207
Расстояние от пикселя №0 к центру #2: 174.44
Пиксель №0 ближе всего к центру #1
Расстояние от пикселя №1 к центру #0: 216.031
Расстояние от пикселя №1 к центру #1: 153.492
Расстояние от пикселя №1 к центру #2: 3.05164
Пиксель №1 ближе всего к центру #2
Расстояние от пикселя №2 к центру #0: 5.31507
Расстояние от пикселя №2 к центру #1: 206.825
Расстояние от пикселя №2 к центру #2: 209.378
Пиксель №2 ближе всего к центру #0
Расстояние от пикселя №3 к центру #0: 219.126
Расстояние от пикселя №3 к центру #1: 20.8847
Расстояние от пикселя №3 к центру #2: 171.609
Пиксель №3 ближе всего к центру #1
Расстояние от пикселя №4 к центру #0: 212.989
Расстояние от пикселя №4 к центру #1: 149.836
Расстояние от пикселя №4 к центру #2: 3.71652
Пиксель №4 ближе всего к центру #2
Расстояние от пикселя №5 к центру #0: 5.31507
Расстояние от пикселя №5 к центру #1: 212.176
Расстояние от пикселя №5 к центру #2: 219.035
Пиксель №5 ближе всего к центру #0
Расстояние от пикселя №6 к центру #0: 215.848
Расстояние от пикселя №6 к центру #1: 21.3054
Расстояние от пикселя №6 к центру #2: 172.164
Пиксель №6 ближе всего к центру #1
Расстояние от пикселя №7 к центру #0: 213.916
Расстояние от пикселя №7 к центру #1: 150.21
Расстояние от пикселя №7 к центру #2: 2.51247
Пиксель №7 ближе всего к центру #2

Массив соответствия пикселей и центров:
1 2 0 1 2 0 1 2

Результат кластеризации:
Кластер #0
150 20 200
153 22 210
Кластер #1
255 140 50
251 141 51
252 138 54
Кластер #2
100 70 1
104 69 3
101 74 4
Новые центры:
151.5 21 205 — #0
233.625 130.375 46.375 — #1
101.5 71.75 3 — #2

Расстояние от пикселя 0 к центру #0: 221.129
Расстояние от пикселя 0 к центру #1: 23.7207
Расстояние от пикселя 0 к центру #2: 174.44
Минимальное расстояние к центру #1
Пересчитываем центр #1: 244.313 135.188 48.1875
Расстояние от пикселя 1 к центру #0: 216.031
Расстояние от пикселя 1 к центру #1: 165.234
Расстояние от пикселя 1 к центру #2: 3.05164
Минимальное расстояние к центру #2
Пересчитываем центр #2: 100.75 70.875 2
Расстояние от пикселя 2 к центру #0: 5.31507
Расстояние от пикселя 2 к центру #1: 212.627
Расстояние от пикселя 2 к центру #2: 210.28
Минимальное расстояние к центру #0
Пересчитываем центр #0: 150.75 20.5 202.5
Расстояние от пикселя 3 к центру #0: 217.997
Расстояние от пикселя 3 к центру #1: 9.29613
Расстояние от пикселя 3 к центру #2: 172.898
Минимальное расстояние к центру #1
Пересчитываем центр #1: 247.656 138.094 49.5938
Расстояние от пикселя 4 к центру #0: 210.566
Расстояние от пикселя 4 к центру #1: 166.078
Расстояние от пикселя 4 к центру #2: 3.88306
Минимальное расстояние к центру #2
Пересчитываем центр #2: 102.375 69.9375 2.5
Расстояние от пикселя 5 к центру #0: 7.97261
Расстояние от пикселя 5 к центру #1: 219.471
Расстояние от пикселя 5 к центру #2: 218.9
Минимальное расстояние к центру #0
Пересчитываем центр #0: 151.875 21.25 206.25
Расстояние от пикселя 6 к центру #0: 216.415
Расстояние от пикселя 6 к центру #1: 6.18805
Расстояние от пикселя 6 к центру #2: 172.257
Минимальное расстояние к центру #1
Пересчитываем центр #1: 249.828 138.047 51.7969
Расстояние от пикселя 7 к центру #0: 215.118
Расстояние от пикселя 7 к центру #1: 168.927
Расстояние от пикселя 7 к центру #2: 4.54363
Минимальное расстояние к центру #2
Пересчитываем центр #2: 101.688 71.9688 3.25

Проведем классификацию пикселей:
Расстояние от пикселя №0 к центру #0: 221.699
Расстояние от пикселя №0 к центру #1: 5.81307
Расстояние от пикселя №0 к центру #2: 174.122
Пиксель №0 ближе всего к центру #1
Расстояние от пикселя №1 к центру #0: 217.244
Расстояние от пикселя №1 к центру #1: 172.218
Расстояние от пикселя №1 к центру #2: 3.43309
Пиксель №1 ближе всего к центру #2
Расстояние от пикселя №2 к центру #0: 6.64384
Расстояние от пикселя №2 к центру #1: 214.161
Расстояние от пикселя №2 к центру #2: 209.154
Пиксель №2 ближе всего к центру #0
Расстояние от пикселя №3 к центру #0: 219.701
Расстояние от пикселя №3 к центру #1: 3.27555
Расстояние от пикселя №3 к центру #2: 171.288
Пиксель №3 ближе всего к центру #1
Расстояние от пикселя №4 к центру #0: 214.202
Расстояние от пикселя №4 к центру #1: 168.566
Расстояние от пикселя №4 к центру #2: 3.77142
Пиксель №4 ближе всего к центру #2
Расстояние от пикселя №5 к центру #0: 3.9863
Расстояние от пикселя №5 к центру #1: 218.794
Расстояние от пикселя №5 к центру #2: 218.805
Пиксель №5 ближе всего к центру #0
Расстояние от пикселя №6 к центру #0: 216.415
Расстояние от пикселя №6 к центру #1: 3.09403
Расстояние от пикселя №6 к центру #2: 171.842
Пиксель №6 ближе всего к центру #1
Расстояние от пикселя №7 к центру #0: 215.118
Расстояние от пикселя №7 к центру #1: 168.927
Расстояние от пикселя №7 к центру #2: 2.27181
Пиксель №7 ближе всего к центру #2

Массив соответствия пикселей и центров:
1 2 0 1 2 0 1 2

Результат кластеризации:
Кластер #0
150 20 200
153 22 210
Кластер #1
255 140 50
251 141 51
252 138 54
Кластер #2
100 70 1
104 69 3
101 74 4
Новые центры:
151.875 21.25 206.25 — #0
249.828 138.047 51.7969 — #1
101.688 71.9688 3.25 — #2

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

Интереснее случаи при рандомной генерации пикселей. Сгенерировав 50 точек, которые нужно поделить на 10 кластеров, я получил 5 итераций. Сгенерировав 50 точек, которые нужно поделить на 3 кластера, я получил все 100 максимально допустимых итераций. Можно заметить, что чем больше кластеров, тем легче программе найти наиболее схожие пиксели и объединить их в меньшие группы, и наоборот — если кластеров мало, а точек много, часто алгоритм завершается только от превышения максимально допустимого количества итераций, так как некоторые пиксели постоянно прыгают из одного кластера в другой. Тем не менее, основная масса все равно определяются в свои кластеры окончательно.

Ну а теперь давайте проверим результат кластеризации. Взяв результат некоторых кластеров из примера 50 точек на 10 кластеров, я вбил результат этих данных в Illustrator и вот что получилось:

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

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

А это 8 кластер, но в уменьшенном варианте, результат аналогичен:

Полную версию программы можно посмотреть на моем GitHub.

Источник

Обнаружение аномальных данных методом k-средних

Продукты и технологии:

C#, Visual Studio 2010

В статье рассматриваются:

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

Лучший способ прочувствовать, для чего нужна кластеризация k-средних, и понять, к чему я клоню в этой статье, — взглянуть на рис. 1. Демонстрационная программа начинает с создания фиктивного набора из 20 элементов данных. В терминологии кластеризации элементы данных иногда называют последовательностью из n-чисел (tuples). Здесь каждая такая последовательность представляет некое лицо (person) и имеет два числовых атрибута: рост в дюймах и вес в фунтах. Одно из ограничений алгоритма k-средних в том, что он применяется только в случаях, где последовательности данных полностью числовые.

Рис. 1. Кластеризация с применением k-средних

Фиктивные данные загружаются в память в виде массива. Затем количество кластеров задается равным трем. Хотя существуют более совершенные методы кластеризации, способные предложить оптимальное количество кластеров, в целом, кластеризация данных — процесс исследовательский, и подходящее число кластеров обычно подбирается методом проб и ошибок. Как вы вскоре увидите, кластеризация k-средних — это итеративный процесс. В демонстрационной программе есть переменная maxCount, которая ограничивает количество выполнений основного цикла кластеризации. Здесь это значение произвольно выбрано равным 30.

Потом «за кулисами» демонстрационная программа использует алгоритм k-средних, чтобы поместить каждую последовательность данных в один из трех кластеров. Способов кодирования кластеризации много. В данном случае кластеризация определяется массивом значений типа int, где индекс массива представляет последовательность данных (tuple), а связанное с массивом значение — идентификатор кластера с нумерацией от 0. Итак, на рис. 1 последовательность 0 (65.0, 220.0) назначена кластеру 0, последовательность 1 (73.0, 160.0) — кластеру 1, последовательность 2 (59.0, 110.0) — кластеру 2, последовательность 3 (61.0, 120.0) — кластеру 2 и т. д. Обратите внимание на то, что восемь последовательностей назначено кластеру 0, пять последовательностей — кластеру 1, а семь последовательностей — кластеру 2.

Далее демонстрационная программа отображает данные, сгруппированные по кластерам. Если вы изучите кластеризованные данные, то заметите, что кластер 0 можно было бы назвать кластером полных людей, кластер 1 — высоких людей, а кластер 2 — низкорослых людей. Анализируя последовательности, назначенные кластеру 0, демонстрационная программа определяет по некоему критерию, что последовательность 5 (67.0, 240.0) является наиболее аномальной.

В следующих разделах я пошагово пройду по коду, с помощью которого был получен результат на экране (рис. 1), чтобы вы смогли потом модифицировать этот код под свои потребности. В этой статье предполагается, что вы по крайней мере на среднем уровне владеете навыками программирования на языках семейства C, но ничего не знаете о кластеризации данных. Я кодировал демонстрационную программу на C#, но избегал стиля объектно-ориентированного программирования (ООП), поэтому у вас не возникнет особых трудностей в рефакторинге этой программы под другой язык. Весь исходный код демонстрационной программы представлен в этой статье; его также можно скачать по ссылке archive.msdn.microsoft.com/mag201302kmeans.

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

По крайней мере в принципе, алгоритм k-средних довольно прост. Но, как вы еще увидите, некоторые детали реализации весьма изощренные. Главной концепцией алгоритма k-средних является центроид (centroid), или центр масс. В кластеризации данных центр масс набора последовательностей данных — это одна из последовательностей, которая является наиболее репрезентативной в группе. Эту идею лучше пояснить на примере. Допустим, у вас есть три последовательности «рост, вес», аналогичные показанным на рис. 1:

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

А теперь, какая из трех последовательностей ближе всего к (65.0, 130.0)? Есть несколько способов определить ближайшую последовательность. Самый распространенный способ, применяемый в демонстрационной программе, — использование евклидового расстояния, или метрики (Euclidean distance). Если на словах, то евклидово расстояние между двумя последовательностями является корнем квадратным суммы квадратов разностей между соответствующими компонентами каждой последовательности. И вновь это лучше пояснить на примере. Евклидово расстояние между последовательностью (61.0, 100.0) и средней последовательностью (65.0, 130.0) равно:

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

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

Поищите в Интернете — найдете несколько хороших онлайновых анимаций, демонстрирующих алгоритм k-средних в действии. Изображение на рис. 2 показывает, к какой кластеризации приводит демонстрационная программа. Элемент данных, обведенный в кружок в каждом кластере, является центром масс этого кластера.

Рис. 2. Кластерные данные и центры масс

Общая структура программы

Общая структура демонстрационной программы с рис. 1 с небольшими правками показана на рис. 3. С помощью Visual Studio 2010 я создал новое консольное приложение на C# под названием «ClusteringKMeans»; для работы с этим проектом подойдет любая недавняя версия Visual Studio. В окне Solution Explorer я переименовал файл Program.cs в ClusteringKMeansProgram.cs, что автоматически повлекло переименование класса, генерируемого шаблоном. Я удалил ненужные выражения using в начале файла.

Рис. 3. Общая структура программы

Для простоты я использовал подход со статическими методами и убрал всю проверку на ошибки. Первая часть демонстрационного кода подготавливает данные по росту и весу к кластеризации. Поскольку последовательностей всего 20, я «зашил» эти данные в код и помещаю их в памяти в виде массива rawData. Обычно данные хранятся в текстовом файле или SQL-таблице. В таких случаях вы должны написать вспомогательную функцию для загрузки данных в память. Если ваш источник данных слишком велик, вам придется модифицировать код так, чтобы он перебирал источник внешних данных, а не массив.

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

После подготовки исходных данных демонстрационная программа вызывает вспомогательную функцию ShowMatrix для отображения данных. Затем переменным numAttributes, numClusters и maxCount присваиваются значения 2 (height и weight), 3 и 30 соответственно. Вспомните, что maxCount ограничивает число итераций основного цикла обработки алгоритма. Алгоритм k-средних имеет тенденцию к быстрому схождению, но вам может понадобиться немного поэкспериментировать со значением maxCount.

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

Демонстрационная программа заканчивает анализом кластеризованных данных на выпадающие, возможно, аномальные последовательности, используя метод Outliers. Этот метод принимает идентификатор кластера и возвращает значения из последовательности данных, которые находятся дальше всего (по евклидовой метрике) от центра масс кластера (наиболее репрезентативной последовательности). В данном случае для кластера 0 выпадающей последовательностью является (67.0, 240.0).

Вычисление центров масс кластеров

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

Рис. 4. Метод UpdateMeans

Метод UpdateMeans предполагает, что массив массивов с именем means уже существует, а вовсе не создает его и не возвращает. Так как предполагается, что массив means имеется, вы, вероятно, предпочтете сделать его параметром, передаваемым по ссылке (ref parameter). Массив means создается вспомогательным методом Allocate:

Первый индекс массива means представляет идентификатор кластера, а второй — указывает атрибут. Например, если means[0][1] = 150.33, то среднее значение веса (1) в последовательности в кластере 0 составляет 150.33.

Метод UpdateMeans сначала обнуляет существующие значения в массиве means, затем перебирает каждую последовательность данных, увеличивая их счетчик в каждом кластере, подсчитывает суммы по каждому атрибуту, а затем делит каждую сумму на соответствующее количество последовательностей в кластере. Заметьте, что этот метод сгенерирует исключение, если счетчик какого-либо кластера окажется равным 0, поэтому здесь нужно добавить проверку на ошибку.

Метод ComputeCentroid (рис. 5) определяет значения центра масс, т. е. значения одной последовательности, ближайшей к последовательности с усредненными значениями для данного кластера.

Рис. 5. Метод ComputeCentroid

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

Метод UpdateCentroids вызывает ComputeCentroid для каждого кластера, чтобы определить центры масс всех кластеров:

Метод UpdateCentroids предполагает, что массив массивов с именем centroids уже существует. Массив centroids очень похож на массив means: первый индекс представляет идентификатор кластера, а второй — указывает атрибут данных.

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

Функция Distance и нормализация данных

Метод ComputeCentroid вызывает метод Distance, чтобы определить, какая последовательность данных ближе всего к центру масс кластера. Как уже описывалось, самый распространенный способ измерить расстояния от последовательностей до средней — использовать евклидову метрику:

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

Другой важный фактор, связанный с выбором функции вычисления метрики в алгоритме кластеризации k-средних, — нормализация данных. Демонстрационная программа использует исходные, ненормализованные данные. Поскольку значения веса в последовательностях — это обычно величины вроде 160.0, а значения роста — на уровне 67.0, разница в значениях веса имеет гораздо большее влияние, чем разница в значениях роста. Во многих ситуациях, исходные данные полезно нормализовать перед кластеризацией. Сделать это можно разными методами. Распространенный способ — вычисление среднего (m) и стандартного отклонения (standard deviation, sd) для каждого атрибута, а затем вычисление для значения каждого атрибута (v) нормализованного значения nv = (v–m)/sd.

Назначение каждой последовательности кластеру

Располагая методом вычисления центроида каждого кластера, можно написать метод для назначения каждой последовательности кластеру. Метод Assign представлен на рис. 6.

Рис. 6. Метод Assign

Метод Assign принимает массив centroids и перебирает каждую последовательность данных. Для каждой из последовательностей вычисляется расстояние до каждого центроида кластера и сохраняется локальный массив с именем distances, индекс которого представляет идентификатор кластера. Затем вспомогательный метод MinIndex определяет индекс в массиве distances, где хранится наименьшее значение метрики, и это соответствует кластеру, центр масс которого находится ближе всего к данной последовательности.

Вот как выглядит вспомогательный метод MinIndex:

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

Эта реализация алгоритма k-средних предполагает, что каждому кластеру всегда назначена хотя бы одна последовательность данных. Как видно на рис. 6, метод Assign не предотвращает ситуации, где кластеру вообще не назначается ни одной последовательности. На практике это обычно не проблема. Предотвратить ошибочную ситуацию не так-то просто. Подход, который я обычно применяю, заключается в создании массива centroidIndexes, работающий в сочетании с массивом centroids. Вспомните, что массив centroids содержит значения центров масс, например (61.0, 120.0) — это центр масс для кластера 2 на рис. 2. Массив centroidIndexes хранит сопоставленный индекс последовательности, скажем [3]. Затем в методе Assign мы первым делом назначаем каждому кластеру последовательность данных, которая содержит значения центра масс, и только после этого метод перебирает остальные последовательности и назначает их кластерам. Такой подход гарантирует, что в каждом кластере будет минимум одна последовательность.

Метод Cluster

Метод Cluster (рис. 7) — высокоуровневая процедура, которая вызывает все вспомогательные методы, выполняющие реальную работу по кластеризации данных.

Рис. 7. Метод Cluster

Основной цикл while повторно назначает каждую последовательность данных кластеру, вычисляет новую последовательность усредненных значений для каждого кластера, а затем использует ее для вычисления новых значений центра масс для каждого кластера. Цикл прекращается, когда не происходит изменений в назначениях кластеров или когда достигается максимальное количество итераций. Поскольку массив means применяется только для вычисления центров масс, вы, возможно, захотите провести рефакторинг Cluster, поместив вызов UpdateMeans внутрь метода UpdateCentroids.

Перед запуском цикла обработки метод InitClustering инициализирует массив clustering:

Метод InitClustering сначала назначает последовательности от 0 до numClusters–1 кластерам от 0 до numClusters–1 соответственно, благодаря чему изначально в каждом кластере будет минимум одна последовательность. Остальные последовательности назначаются случайно выбранным кластерам.

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

Поиск аномальных данных

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

Рис. 8. Метод Outlier

После инициализации массивов means и centroids метод Outlier перебирает каждую последовательность в указанном кластере и вычисляет евклидово расстояние (метрику) от текущей последовательности до центра масс (центроида) кластера, а затем возвращает значения последовательности, которая имеет наибольшее расстояние до центроида. В качестве альтернативы можно возвращать индекс самой дальней последовательности данных.

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

Процедуры отображения

Для полноты картины ниже показаны некоторые упрощенные процедуры отображения. В пакете исходного кода эти процедуры посложнее. Если вы используете упрощенные процедуры, то должны будете модифицировать их вызовы в методе Main. Чтобы отобразить исходные данные, средние и центры масс, вы можете применить:

Для вывода массива clustering можно использовать:

Чтобы показать выпадающие данные:

А для отображения исходных данных, сгруппированных по кластерам:

Заключение

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

Джеймс Маккафри (Dr. James McCaffrey) — руководит в компании Volt Information Sciences Inc. повышением квалификации инженеров ПО из Microsoft, работающих в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и MSN Search. Автор книги «.NET Test Automation Recipes» (Apress, 2006). С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи эксперту Даррену Герингу (Darren Gehring).

Источник