«

Окт 15

Алгоритм кластеризации K-means

Введение

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

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

Исторически сложилось так, что k-means   был открыт несколькими исследователями различных дисциплин, в первую очередь Ллойдом (1957, 1982), Форджи (1965), Фридманом и Рубином (1967), и  МакКуином (1967). Детальная история k-means вместе с описанием различных изменений дана Джейном и Дабсом.

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

Алгоритм k-means

Алгоритм k-means применяется к объектам, которые представляются точками  в d-мерном векторном пространстве.  Таким  образом,  это кластеры  набора d-мерных векторов, D = {xi|i = 1, . . . , N}, где xi ∈ Rd  обозначает i-ый объект или «точку данных». Как уже говорилось во введении, k-means является алгоритмом кластеризации, который разделяет D на  k кластеров точек. То есть, алгоритм k-means объединяет все точки данных в D  так, что каждая точка xi  попадает  в один и только один из k разделов. Можно отследить, какая точка находится в каком кластере, назначив каждой точке номер кластера. Точки с таким же номером кластера находятся в одном и том же кластере, в то время как точки с различными номерами кластера находятся в разных кластерах.  Это можно обозначить как кластерный составной вектор m длинною N, где mi является номером кластера xi.

Значение k  является основным из входных данных алгоритма. Как правило,  значение k основано на критериях, таких как  предварительное знание о том, сколько на самом деле кластеров появится в D,  как много кластеров требуется для текущего приложения, или типы кластеров, найденные путем изучения/экспериментирования   с различными значениями k. Неважно, каким образом выбран k, для того чтобы понять,  как k-means разделяет набор данных D, и мы обсудим, как  выбирать k, когда он не задан,   в следующем разделе.

В k-means, каждый из k кластеров   представлен одной точкой в Rd. Обозначим этот набор представителей кластера как множество С = {сj|j=1, ….., k}. Эти представители k кластеров  также называются состояние кластера или центройды кластера: мы обсудим причину этого после описания целевой функции  k-means.

В алгоритмах кластеризации точки группируются некоторым понятием «близости» или «подобия». В k-means мера близости по умолчанию Евклидово расстояние. В частности можно с готовностью показать, что k-means пытается минимизировать следующую неотрицательную функцию стоимости

    (1)

Другими словами, k-means пытается минимизировать итоговый квадрат Евклидова расстояния между каждой точкой xi и ее самым близким представителем кластера cj. Уравнение 1 часто упоминается как целевая функция k-means.

Алгоритм k-means разделяет  D итеративным способом, чередующимся между 2 шагами: (1) переприсваивание номера кластера всем точкам в D и (2) обновление представителей кластера, основанных на точках данных в каждом кластере. Алгоритм работает следующим образом. Сначала представители кластера инициализируются, выбирая k из Rd.  Методы для выбора этих начальных источников включают случайную выборку из набора данных, устанавливая их как решение кластеризации маленького подмножества данных, или нарушая глобальное среднее значение данных k раз. В Алгоритме мы инициализируем случайно выбранные k точек.  Затем выполняется алгоритм итерации до сходимости за 2 шага.

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

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

Алгоритм сходится, когда присвоение (следовательно, и значения Сj) больше не изменяются. Можно показать, что целевая функция k-means, определенная в уравнении 1, будет уменьшаться всякий раз, когда есть изменения в присвоении или шагах измерения, и сближение  (сходимость в одной точке) гарантировано за конечное число итераций.

Как упомянуто, выбор оптимального значения k может быть трудным. Если вы что-то знаете о наборе данных, например, число разделов, которые естественно включают набор данных, тогда эти значения могут быть использованы при выборе k. Иначе, необходимо использовать другие критерии выбора k, таким образом, решая проблему выбора модели. Самое простое решение  попробовать несколько различных значений k и выбрать кластеризацию, которая минимизирует целевую функцию k-means (Уравнение 1). К сожалению, значение целевой функции не столь же информативно, как можно было бы надеяться в этом случае. Для примера, стоимость оптимального решения сокращается с увеличением k до тех пор, пока она не достигнет 0, когда число кластеров равняется числу отличных точек данных. Это делает его более трудным для использования объективной функции (а) непосредственно сравнивая решения с различным числом кластеров и (в) найти оптимальное значение k. Таким образом, если требуемое k не будет известно заранее, как правило, k-means будет запущен с различными значениями k, а затем использовать другие, более подходящие критерии для выбора одного из результатов. В качестве альтернативы, можно прогрессивно увеличивать число кластеров в соединении с подходящим критерием остановки.

 Алгоритм K-means:

Этап 1. Первоначальное распределение объектов по кластерам

  1. Выбор случайным образом k точек данных из D как начальное множество представителей кластера C
  2. Распределение объектов по кластерам в соответствие с формулой (1)

Этап 2. Перераспределение срединных элементов

  1. Вычисление центра для каждого кластера
  2. Перераспределение объектов по кластерам

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

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

Потенциальная проблема  алгоритма – проблема «пустых» кластеров. При запуске k-means, особенно с большим значением k и/или когда данные находятся в большом размерном пространстве, возможно, что в какой-то момент исполнения, существует  представитель кластера cj, такой, что все точки xi в D ближе к некоторому другому представителю кластера, который не является cj. Когда точки в D будут присвоены к ближайшему кластеру, j-му кластеру будут присвоены нулевые точки. Таким образом, кластер j является теперь пустым кластером. Стандартный алгоритм не принимает меры против пустых кластеров, но простые решения (такие как переинициализация представителя пустого кластера или «кража» некоторых точек из большого кластера) возможны.

Заключение

Исследуем производительность k-means на простом, классическом тестовом множестве данных. В нашем примере мы исследовали  множество данных Ирис (доступный в репозитории  анализа данных UCI), который состоит из 150 точек данных из 3 классов. Каждый класс представляет различную разновидность цветков Ириса, и имеем по 50 точек в каждом классе. Несмотря на то, что есть 4 размерности  (представляющие ширину чашелистика, длину чашелистики, ширину лепестков и длину лепестков), только 2 величины (ширина лепестка и длина лепестка) необходимы, чтобы отличать эти 3 класса. Набор данных Ирис изображен на рисунке 2.5а вдоль размерности ширины и длины лепестка.

На рисунке 2.5b мы показали пример работы алгоритма k-means на наборе данных Ирис с k=3, используя только атрибуты длины и ширины лепестка. Алгоритм k-means в состоянии разделить точки данных так, что каждый кластер состоит в основном из цветов одного вида.

Рисунок 2.5 (а) множество данных Ирис: каждый цвет является отдельным видом ириса; (b) Результат работы k-means на множестве данных Ирис: каждый цвет это отдельный кластер: заметим, что существует несоответствие между цветами в (а) и (b).

В заключение,  мы обсудим 2 простых расширения алгоритма k-means. Первый это вариант k-means, названный программа k-means. В стандартном алгоритме k-means, каждая точка xi принадлежит одному и только одному кластеру. В программе k-means это ограничение смягчено, и каждая точка xi может принадлежать каждому кластеру с некоторой долей вероятности.  В программе k-means для каждой точки xi одинаково  поддерживается множество k вероятностей или весов, которые описывают вероятность того, что xi принадлежит каждому кластеру. Эти веса основаны на расстоянии xi от каждого представителя кластера С, где вероятность того, что xi находится в j кластере, пропорционально сходству  между xi и cj. Представителей кластера в этом случае можно найти, взяв предполагаемое значение срединного элемента по всем точкам в наборе данных D.

Второе расширение k-means имеет  дело с обучение.  Во введении мы приводили различия  между обучением с учителем и обучением без учителя. Вкратце, обучение с учителем использует маркеры класса, тогда как обучение без учителя нет. Алгоритм k-means является алгоритмом обучения без учителя. Также существует  категория алгоритмов обучения называемых алгоритмами с частичным обучением с учителем. Такие алгоритмы способны работать с маркированными и немаркированными данными. Частичное обучение является полезным компромиссом  между методами обучения с учителем и без него. Методы обучения с учителем  обычно требуют очень большого количества помеченных данных, методы с частичным обучением  полезны, когда например, доступно очень мало помеченных данных. Методы обучения без учителя, несмотря на маркеры класса, могут обучить близкие модели, несоответствующие приложению. При запуске k-means алгоритм не имеет никакого контроля над конечными кластерами, которые обнаружил: эти кластеры могут или не могут хорошо соответствовать  некоторой основополагающей концепции, в которой он заинтересован. Для примера, на рисунке 2.5(b), плохая инициализация может быть результатом кластеров, которые не соответствуют разновидности Ириса во множестве данных. Методы с частичным обучением с учителем, которые  могут принимать рекомендации в форме маркированных данных, скорее всего, создают кластеры, которые соответствуют   данному множеству  классов маркеров.

Итоги

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

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