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

Формально евклидово расстояние между двумя точками x и y в n-мерном пространстве определяется как:

d(x, y) = sqrt( (x1 — y1)² + (x2 — y2)² + … + (xn — yn)² )

где xi и yi — координаты двух точек в i-м измерении.

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

Цель алгоритма — минимизировать сумму квадратов расстояний между каждой точкой данных и назначенным ей центром тяжести.

Функцию стоимости, также известную как сумма квадратов внутри кластера (WCSS), можно сформулировать следующим образом:

WCSS = Sum(distance(x, centroid)²) для всех x в кластере

Алгоритм k-средних направлен на минимизацию этой функции стоимости путем нахождения лучших центроидов.

Шаг

Предположим, у нас есть набор данных из 5 точек данных, каждая из которых имеет две функции (координаты x и y). Точки данных показаны в следующей таблице:

Мы хотим использовать алгоритм k-средних, чтобы сгруппировать эти точки данных в 2 кластера.

  1. Инициализация: мы выбираем 2 начальных центроида, по одному для каждого кластера. Например, мы можем выбрать центроид 1 в точке (1, 1) и центроид 2 в точке (8, 8).
  2. Кластеризация: мы вычисляем евклидово расстояние между каждой точкой данных и каждым центроидом. Например, расстояние между точкой данных A и центром тяжести 1 равно sqrt((1–1)² + (1–1)²) = 0, а расстояние между точкой данных A и центром тяжести 2 равно sqrt((1–8) ² + (1–8)²) = 8,83. Мы назначаем каждую точку данных кластеру с ближайшим центроидом. Таким образом, точка данных A назначается кластеру 1, а точки данных B, C, D и E назначаются кластеру 2.
  3. Обновление центроида. Мы пересчитываем центроид для каждого кластера, взяв среднее значение всех точек данных в этом кластере. Например, новый центроид для кластера 1 — (1, 1), а новый центроид для кластера 2 — (8, 8).
  4. Повторяйте шаги 2 и 3, пока центроиды не перестанут изменяться. В этом примере центроиды больше не меняются, поэтому алгоритм останавливается.
  5. Выведите окончательные кластеры: окончательные кластеры [A] и [B, C, D, E]

За и против

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

Плюсы:

  • Простой и легкий для понимания и реализации
  • Может обрабатывать большие наборы данных и многомерные данные
  • Может обнаруживать основные закономерности в данных
  • Широко используется в различных приложениях

Минусы:

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

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

Приложения

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

  1. Сжатие изображения. Можно использовать k-means для уменьшения количества цветов в изображении при сохранении общего визуального качества. Сгруппировав похожие цвета вместе, алгоритм может уменьшить количество цветов в изображении, сохранив при этом общий внешний вид.
  2. Сегментация рынка. Метод k-средних можно использовать для группировки клиентов с похожими покупательскими привычками. Это можно использовать для целенаправленных маркетинговых усилий и повышения удовлетворенности клиентов.
  3. Обнаружение аномалий. Метод k-средних можно использовать для выявления необычных точек данных, не принадлежащих ни к одному из кластеров. Эти точки данных могут представлять собой выбросы или аномалии, которые могут быть важны для обнаружения в некоторых приложениях.
  4. Кластеризация документов: k-средние можно использовать для кластеризации документов на основе схожести их содержимого. Это можно использовать для организации большой коллекции документов или выявления закономерностей в данных.
  5. Обработка естественного языка: k-means можно использовать для группировки похожих слов и фраз для определения тем в текстовом корпусе.
  6. Анализ данных об экспрессии генов: k-средние можно использовать для выявления закономерностей в данных об экспрессии генов и кластерных генов, которые имеют схожие профили экспрессии.
  7. Промышленное производство: k-средние можно использовать для кластеризации измерений и данных датчиков промышленных машин и выявления шаблонов, которые можно использовать для обслуживания и оптимизации.
  8. Обнаружение мошенничества. Метод k-mean можно использовать для кластеризации транзакций и выявления моделей необычного поведения, которые могут указывать на мошеннические действия.

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