47,4
рейтинг
14 августа 2009 в 14:23

Разработка → Кластеризация: алгоритмы k-means и c-means

Добрый день!

Как и обещал, продолжаю серию публикаций о технологии Data Mining. Сегодня хочу рассказать о двух алгоритмах кластеризации (k-means и c-means), описать преимущества и недостатки, дать некоторые рекомендации по их использованию. Итак, поехали…

Кластеризация — это разделение множества входных векторов на группы (кластеры) по степени «схожести» друг на друга.

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


Меры расстояний


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

Есть множество мер расстояния, рассмотрим несколько из них:

Евклидово расстояние — наиболее распространенное расстояние. Оно является геометрическим расстоянием в многомерном пространстве.

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

Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является просто средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат).

Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как «различные», если они различаются по какой-либо одной координате (каким-либо одним измерением).

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

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

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


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

Проблемы алгоритма k-means:
* необходимо заранее знать количество кластеров. Мной было предложено метод определения количества кластеров, который основывался на нахождении кластеров, распределенных по некоему закону (в моем случае все сводилось к нормальному закону). После этого выполнялся классический алгоритм k-means, который давал более точные результаты.
* алгоритм очень чувствителен к выбору начальных центров кластеров. Классический вариант подразумевает случайный выбор класторов, что очень часто являлось источником погрешности. Как вариант решения, необходимо проводить исследования объекта для более точного определения центров начальных кластеров. В моем случае на начальном этапе предлагается принимать в качестве центов самые отдаленные точки кластеров.
* не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному.

Материалы по теме:
* Википедия — K-means
* Introduction to K-means
* Описание функции kmeans в Matlab Statistics Toolbox
* K-means — Interactive demo (Java)

Нечеткий алгоритм кластеризации с-means


С последней проблемой k-means успешно справляется алгоритм с-means. Вместо однозначного ответа на вопрос к какому кластеру относится объект, он определяет вероятность того, что объект принадлежит к тому или иному кластеру. Таким образом, утверждение «объект А принадлежит к кластеру 1 с вероятностью 90%, к кластеру 2 — 10% » верно и более удобно.

Классический пример с-means — т.н. «бабочка» (butterfly):

image

Как видно, точка с координатами (3,2) в равной степени принадлежит как первому так и второму кластеру.

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

Ссылки по теме:
* Формальное описание алгоритма и реализация на C#
* Fuzzy c-means clustering
* Fuzzy C-means cluster analysis

P.S. Я не описывал математические принципы алгоритмов, с ними легко можно ознакомиться по представленным ссылкам.

Спасибо за внимание!
Краковецкий Александр @sashaeve
карма
433,2
рейтинг 47,4
CEO DevRain Solutions
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (9)

  • +1
    >Евклидово расстояние — наиболее распространенное расстояние. Оно является геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:
    >
    > Квадрат евклидова расстояния.

    Так каким образом вычисляется евклидово расстояние?
    • –1
      Как корень квадратный из суммы разностей координат объекта, возведенных в квадрат.

      Расстояние Евклида
      • 0
        Я к тому что подправьте пост, а то как-то странно выглядит.
        • 0
          Подправил, спасибо.
  • +1
    Как-то не сложилось у меня с K-Means ибо:
    * Зачастую долго сходится
    * При каждом запуске выдаёт разные результаты. Спасает только испоьзование K-Means++
    * Но самой большой проблемой всё равно остаётся то, что далеко не всегда знаешь нужное колво кластеров на которое нужно разделить объекты, по хорошему она на то и кластеризация, что на входе ты поучаешь просто набор векторов в N-мерном пространстве, не зная на сколько групп их делить.

    Именно поэтому, в основном использую Minimal Spaning Tree, Single-/Averenge-/Complete- Link или Генетические алгоритмы. Последние люблю за то, что они прекрасно паралелятся, хоть и тоже долго сходятся. У "-Link" семейства алгоритмов бонус в простоте расчётов (особенно у Single-Link) и возможности следить за RMSE на каждом шаге алгоритма, выбирая оптимальное количество кластеров.
    • 0
      А как вычисляются расстояния при кластеризации по не числовым признакам? Например при кластеризации физ. лиц. клиентов банка может возникнуть задача кластеризации по признакам пол, образование, семейное положение, занимаемая на работе должность, сфера деятельности компании-работодателя ну и так далее? Понятно, что можно заменить показатели целочисленными величинами, интересен вопрос о том, какими по величине и как упорядоченными :)
      • 0
        В таких случаях, действительно, необходимо использовать целочисленные величины. А вот ответственность за выбор размерности лежит на исследователе. Главное требование — чтобы все характеристики имели одинаковый масштаб. Т.е. координаты в пространстве (x,y,z) имеют одинаковый масштаб, а вот мужчина (1) и $100 (2) — разные. Таким образом, необходимо иметь дополнительные данные о характере объектов и уже по этим данным переводить пол, возраст и т.д. в числовые эквиваленты.
        • 0
          ну для примера в моей задаче я решил, что доход до 500$=1; от 500 до 1000 — 2; от 1000 и выше = 3, мальчики =1; девочки =2. Все показатели целочисленные и имеют одинаковый масштаб. Если я буду рассчитывать расстояние между двумя «фактами» как геометрическое расстояние, то ведь результат будет зависеть от того, как я выбрал целочисленные показатели. Возможно для решения каких-то моих практических задач будет правильнее выбрать для величин, характеризующих доход не числа 1,2,3, а к примеру 1,2,4. Так?
          • 0
            >я решил, что доход до 500$=1; от 500 до 1000 — 2; от 1000 и выше = 3
            это уже классификация

            >Возможно для решения каких-то моих практических задач будет правильнее
            >выбрать величин, характеризующих доход не числа 1,2,3, а к примеру 1,2,4.

            Вообще, я например все значения нормализую. Например, представим рельсы у них длина много больше ширины, поэтому рельсы отличающиеся на 5% по длине и на 1200% по ширине окажутся в одном кластере. Поэтому я значения всех измерений нормализую (если это возможно, то есть данные не потоковые) и самой короткой длине выдаю значение 0, самой длинной, например, 100, все остальные длины будут в промежутке от 0 до 100, так же поступаю с остальными измерениями. Все значения после этого становятся нормализованными.

            >А как вычисляются расстояния при кластеризации по не числовым признакам?
            Когда измерение дискретно и возможно заранее получить все возможные значения измерения (как например пол), то конечно можно заменять значения заранее просчитанными нормализованными значениями, дабы прибавить производительности алгоритму. Но стандартной практикой является использование Расстояния Левенштейна

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.