Кластеризация K-средних и евклидово расстояние: званый обед с друзьями (и волшебный джинн, и…

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

K-means похож на волшебного джинна, который берет все предпочтения ваших друзей в еде и волшебным образом организует их в группы или «кластеры». Например, допустим, у вас есть три друга:

• Друг 1 любит пиццу и гамбургеры
• Друг 2 любит суши и салат
• Друг 3 любит тако и буррито

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

Конечно, это просто глупый пример, но k-means — это мощный алгоритм машинного обучения, который можно использовать во всех видах реальных приложений, таких как маркетинг, финансы и здравоохранение. Так что в следующий раз, когда вам нужно будет организовать что-то в группы, просто помните: k-means — ваш дружелюбный соседский джинн!

Но давайте сначала разберемся с евклидовым расстоянием.

продолжим ту же историю :)

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

Эвклидово расстояние похоже на линейку, с помощью которой можно измерить «расстояние» между двумя точками. В этом случае баллами являются ваши друзья и их предпочтения в еде.

Чтобы использовать евклидово расстояние, вы должны присвоить числовое значение каждому типу продуктов. Например, вы можете присвоить пицце значение 1, гамбургерам — значение 2, суши — значение 3 и т. д. Затем рассчитать расстояние между каждой парой друзей на основе их предпочтений в еде.

Например, расстояние между другом 1 (пицца и гамбургеры) и другом 2 (суши и салат) будет составлять:

sqrt((1–3)² + (2–4)²) = sqrt(4 + 4) = 2,828

Это говорит о том, что у Друга 1 и Друга 2 расстояние предпочтения в еде составляет 2,828, что означает, что они не очень похожи с точки зрения их пищевых предпочтений. С другой стороны, расстояние между Другом 1 и Другом 3 (оба любят пиццу и гамбургеры) будет намного меньше, что указывает на то, что у них схожие предпочтения в еде.

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

Формальное определение

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

1. Это простой и эффективный метод кластеризации данных: алгоритм К-средних относительно прост для понимания и реализации, что делает его популярным выбором для задач кластеризации. Он также относительно эффективен, особенно для больших наборов данных, поскольку для сходимости требуется лишь небольшое количество итераций.
2. Его можно использовать для широкого круга приложений: Алгоритм K-средних можно применять к широкому спектру типов данных, включая непрерывные переменные, категориальные переменные и смешанные типы данных. Это делает его универсальным инструментом для кластеризации данных в различных контекстах.
3. Он может дать представление о базовых закономерностях в данных: группируя данные в кластеры, алгоритм K-средних может помочь выявить закономерности и взаимосвязи в данных, которые могут быть не очевидны сразу. Это может быть полезно для исследовательского анализа данных и для выработки гипотез о данных.
4. Его можно использовать в качестве этапа предварительной обработки для других алгоритмов машинного обучения: алгоритм K-средних можно использовать в качестве этапа предварительной обработки для повышения производительности других алгоритмов машинного обучения. Например, его можно использовать для уменьшения размерности данных или для создания функций для использования в алгоритме обучения с учителем.
5. В целом, алгоритм K-средних является мощным и широко используемым инструментом для кластеризации данных и выявления закономерностей в больших наборах данных. Это важный алгоритм, с которым нужно ознакомиться в области науки о данных и машинного обучения.

Вот общий план того, как работает алгоритм K-средних:

1. Инициализировать K центроидов случайным образом: первый шаг в алгоритме K-средних состоит в случайной инициализации K центроидов, где K — количество кластеров, которые вы хотите сформировать. Эти центроиды будут использоваться для представления кластеров.
2. Назначьте каждую точку данных ближайшему центроиду: после инициализации центроидов алгоритм будет перебирать каждую точку данных и назначать ее кластеру, представленному ближайшим центроидом.
3. Пересчитайте центроиды: после того, как все точки данных будут назначены кластеру, алгоритм пересчитает центроиды на основе среднего значения всех точек в каждом кластере.
4. Повторяйте шаги 2 и 3 до сходимости: алгоритм будет продолжать выполнять эти шаги до тех пор, пока центроиды не перестанут двигаться или сумма расстояний между точками данных и назначенными им центроидами не достигнет минимума. Это указывает на то, что кластеры сошлись и алгоритм нашел устойчивое решение.

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

Вот пример того, как вы могли бы реализовать алгоритм K-средних с нуля в Python:

import numpy as np

def kmeans(data, k, max_iterations=100):
  # Initialize centroids randomly
  centroids = [data[i] for i in np.random.randint(0, len(data), k)]
  
  # Initialize empty clusters
  clusters = [[] for _ in range(k)]
  
  # Iterate until convergence
  for _ in range(max_iterations):
    # Assign each data point to the closest centroid
    for datapoint in data:
      distances = [np.linalg.norm(datapoint - centroid) for centroid in centroids]
      closest_centroid = np.argmin(distances)
      clusters[closest_centroid].append(datapoint)
      
    # Recalculate the centroids as the mean of the points in each cluster
    for i in range(k):
      centroids[i] = np.mean(clusters[i], axis=0)
      
  return centroids, clusters

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

Чтобы использовать эту функцию, вы должны просто вызвать ее с вашими данными и желаемым количеством кластеров, например:

centroids, clusters = kmeans(data, k)

Надеюсь, это поможет!