Алгоритмы кластеризации: от начала до современного состояния

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

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

Кластеризация K-средних

После необходимого введения курсы Data Mining всегда продолжаются с K-Means; эффективный, широко используемый универсальный алгоритм кластеризации. Прежде чем запустить его, мы должны определить функцию расстояния между точками данных (например, евклидово расстояние, если мы хотим сгруппировать точки в пространстве), и мы должны установить количество желаемых кластеров (k).

Алгоритм начинается с выбора k точек в качестве начальных центроидов («центров» кластеров). Мы можем просто выбрать любые k случайных точек или использовать какой-то другой подход, но выбор случайных точек — хорошее начало. Затем мы итеративно повторяем два шага:

1. Шаг назначения: каждая из m точек из нашего набора данных назначается кластеру, который представлен ближайшим из k центроидов. Для каждой точки мы вычисляем расстояния до каждого центроида и просто выбираем наименее удаленный.

2. Шаг обновления: для каждого кластера новый центроид вычисляется как среднее значение всех точек в кластере. Из предыдущего шага у нас есть набор точек, которые назначены кластеру. Теперь для каждого такого набора мы вычисляем среднее значение, которое мы объявляем новым центроидом кластера.

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

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

Другие подходы к выбору начальных точек могут основываться на выборе удаленных точек. Это может привести к лучшим результатам, но у нас могут возникнуть проблемы с выбросами, теми редкими отдельными точками, которые просто «не работают», которые могут быть просто некоторыми ошибками. Поскольку они далеки от какого-либо значимого кластера, каждая такая точка может оказаться своим собственным «кластером». Хорошим балансом является вариант K-Means++ [Артур и Васильвицкий, 2007], инициализация которого по-прежнему будет выбирать случайные точки, но с вероятностью, пропорциональной квадратному расстоянию от ранее назначенных центроидов. Точки, которые находятся дальше, будут иметь более высокую вероятность быть выбранными в качестве начальных центроидов. Следовательно, если есть группа точек, вероятность того, что будет выбрана точка из группы, также становится выше по мере того, как их вероятности складываются, что решает упомянутую нами проблему выбросов.

K-Means++ также является инициализацией по умолчанию для реализации Python Scikit-learn K-Means. Если вы используете Python, возможно, вам подойдет эта библиотека. Для Java хорошим началом может стать библиотека Weka:

Ява (Века)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (Scikit-learn)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

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

В этом случае мы знали, что существует три разных кластера (вида), и K-средние правильно распознали, какие из них идут вместе. Но как вообще выбрать хорошее количество кластеров k? Такого рода вопросы довольно распространены в машинном обучении. Если мы запросим больше кластеров, они будут меньше, и, следовательно, общая ошибка (сумма расстояний от точек до назначенных им кластеров) будет меньше. Итак, стоит ли просто установить большее значение k? Мы можем закончить тем, что имеем k = m, то есть каждая точка является своим собственным центроидом, а каждый кластер имеет только одну точку. Да, общая ошибка равна 0, но мы не получили более простого описания наших данных, и оно недостаточно общее, чтобы охватить некоторые новые моменты, которые могут появиться. Это называется переоснащением, и мы этого не хотим.

Способ решения этой проблемы состоит в том, чтобы включить некоторые штрафы за большее количество кластеров. Итак, мы сейчас пытаемся минимизировать не только ошибку, но и ошибку + штраф . Ошибка просто будет стремиться к нулю по мере увеличения количества кластеров, но штраф будет расти. В какой-то момент выигрыш от добавления еще одного кластера будет меньше введенного штрафа, и мы получим оптимальный результат. Решение, использующее для этой цели байесовский информационный критерий (BIC), называется X-Means [Pelleg and Moore, 2000].

Еще одна вещь, которую мы должны правильно определить, — это функция расстояния. Иногда это простая задача, логичная, учитывая характер данных. Для точек в пространстве евклидово расстояние является очевидным решением, но оно может быть сложным для характеристик различных «единиц», для дискретных переменных и т. д. Это может потребовать много знаний в предметной области. Или мы можем обратиться за помощью к машинному обучению. На самом деле мы можем попытаться изучить функцию расстояния. Если у нас есть тренировочный набор точек, о которых мы знаем, как они должны быть сгруппированы (т. е. точки, помеченные своими кластерами), мы можем использовать методы обучения с учителем, чтобы найти хорошую функцию, а затем применить ее к нашему целевому набору, который еще не сгруппирован. .

Метод, используемый в K-Means, с двумя чередующимися этапами, напоминает метод ожидания-максимизации (EM). Собственно, это можно считать очень простой версией ЭМ. Однако его не следует путать с более сложным алгоритмом кластеризации EM, несмотря на то, что он использует некоторые из тех же принципов.

Кластеризация ЭМ

Таким образом, при кластеризации K-средних каждая точка назначается только одному кластеру, а кластер описывается только его центром тяжести. Это не слишком гибко, так как у нас могут возникнуть проблемы с перекрывающимися кластерами или кластерами, которые не имеют круглой формы. С помощью EM Clustering мы можем сделать еще один шаг и описать каждый кластер по его центроиду (среднее значение), ковариации (чтобы мы могли иметь эллиптические кластеры) и весу (размеру кластера). Вероятность того, что точка принадлежит кластеру, теперь задается многомерным гауссовым распределением вероятностей (многомерным - зависящим от нескольких переменных). Это также означает, что мы можем вычислить вероятность того, что точка окажется под гауссовым «колоколом», т.е. вероятность того, что точка принадлежит кластеру.

Теперь мы начнем процедуру EM, вычислив для каждой точки вероятности ее принадлежности к каждому из текущих кластеров (которые, опять же, могут быть созданы случайным образом в начале). Это Е-шаг. Если один кластер является действительно хорошим кандидатом на получение точки, его вероятность будет близка к единице. Однако два или более кластера могут быть приемлемыми кандидатами, поэтому точка имеет распределение вероятностей по кластерам. Это свойство алгоритма точек, не принадлежащих ограниченно одному кластеру, называется «мягкой кластеризацией».

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

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

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

Распространение сходства

Affinity Propagation (AP) был опубликован Фреем и Дуеком в 2007 году и становится все более и более популярным благодаря своей простоте, универсальности и производительности. Он меняет свой статус с современного на стандарт де-факто.

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

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

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

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

И сходство, и предпочтения часто представляются с помощью одной матрицы, где значения на главной диагонали представляют предпочтения. Матричное представление хорошо подходит для плотных наборов данных. Там, где связи между точками редки, практичнее не хранить в памяти всю матрицу nxn, а вместо этого вести список сходств с соединенными точками. За кулисами «обмен сообщениями между точками» — это то же самое, что манипулирование матрицами, и это только вопрос перспективы и реализации.

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

1. Вычисление ответственности: Ответственность r(i, k) отражает накопленные данные о том, насколько хорошо точка k может служить образцом для точки i, принимая во внимание другие потенциальные образцы для точки i. Ответственность отправляется из точки данных i в точку k-кандидата-экземпляра.

2. Вычисление доступности: Доступность a(i, k) отражает накопленные данные о том, насколько целесообразно для точки i выбрать точку k в качестве своего образца, принимая во внимание поддержку других точек в отношении того, что точка k должна быть образцом. Информация о доступности передается из точки k-кандидата в точку i.

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

Таким образом, при расчете доступности используются рассчитанные обязанности в качестве доказательства того, будет ли каждый кандидат представлять собой хороший образец. Доступность a(i, k) устанавливается равной собственной ответственности r(k, k) плюс сумма положительных обязанностей, которые экземпляр-кандидат k получает от других точек.

Наконец, у нас могут быть разные критерии остановки для завершения процедуры, например, когда изменения значений падают ниже некоторого порога или достигается максимальное количество итераций. В любой точке процедуры Affinity Propagation суммирование матриц Ответственности (r) и Доступности (a) дает нам необходимую информацию о кластеризации: для точки i k с максимальным r(i, k) + a(i, k) представляет точку я образец. Или, если нам нужен просто набор экземпляров, мы можем просканировать главную диагональ. Если r(i, i) + a(i, i) > 0, то точка i является образцом.

Мы видели, что с K-средними и подобными алгоритмами определение количества кластеров может быть сложной задачей. В случае с AP нам не нужно указывать его явно, но может потребоваться некоторая настройка, если мы получим больше или меньше кластеров, чем мы считаем оптимальным. К счастью, просто изменив настройки, мы можем уменьшить или увеличить количество кластеров. Установка более высокого значения предпочтения приведет к большему количеству кластеров, поскольку каждая точка «более уверена» в своей пригодности в качестве образца, и поэтому ее труднее «превзойти» и включить ее в «доминирование» какой-либо другой точки. И наоборот, установка более низких параметров приведет к уменьшению количества кластеров; они как бы говорят «нет, нет, пожалуйста, ты пример лучше, я присоединюсь к твоему кластеру». Как правило, мы можем установить все предпочтения на среднее сходство для среднего и большого количества кластеров или на наименьшее сходство для умеренного числа кластеров. Однако может потребоваться пара прогонов с настройкой предпочтений, чтобы получить результат, точно соответствующий нашим потребностям.

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

В конце концов…

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

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

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

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

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