Алгоритм дыхания K-средних в Python: пошаговое руководство

Breathing K-Means — это расширение алгоритма K-Means, которое динамически обновляет центры кластеров во время итераций, позволяя им «дышать» и исследовать большее пространство поиска. Вот пошаговое руководство по реализации Breathing K-Means в Python:

Шаг 1. Импортируйте необходимые библиотеки

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

Разберем каждую строку кода:

Первая строка импортирует библиотеку NumPy, которая является основным пакетом для научных вычислений в Python.

Вторая строка импортирует модуль pyplot из библиотеки Matplotlib, которая представляет собой библиотеку для построения графиков в Python. Matplotlib позволяет создавать различные типы графиков, диаграмм и визуализаций для эффективного анализа и представления ваших данных.

Третья строка импортирует функцию make_blobs из модуля datasets библиотеки scikit-learn. Scikit-learn — это мощная библиотека машинного обучения на Python, которая предоставляет различные инструменты для анализа данных, моделирования и оценки. Функция make_blobs — это служебная функция, используемая для создания синтетических наборов данных с заданными характеристиками, такими как количество выборок, центров и стандартное отклонение.

Шаг 2. Сгенерируйте синтетические данные с помощью функции make_blobs из scikit-learn.

X, _ = make_blobs(n_samples=500, centers=4, random_state=42)

Разберем код построчно:

1. make_blobs: это функция из модуля datasets scikit-learn, которая генерирует синтетические наборы данных. Он обычно используется для создания кластеров точек данных с определенными характеристиками.
2. n_samples=500: Этот параметр указывает количество выборок или точек данных для генерации. В этом случае он генерирует 500 точек данных.
3. centers=4: этот параметр определяет количество кластеров или центров в сгенерированных данных. Каждый центр представляет отдельную группу или кластер точек данных. В этом случае он генерирует точки данных, принадлежащие 4 кластерам.
4. random_state=42: Этот параметр устанавливает случайное начальное число для воспроизводимости. Это гарантирует, что каждый раз, когда вы запускаете код, создается один и тот же набор данных с одинаковыми характеристиками. В этом случае используется случайное состояние 42.
5. X, _ = make_blobs(...): Эта строка присваивает сгенерированный набор данных переменной X. Переменная _ используется для отбрасывания второго вывода функции make_blobs, который не нужен в этом фрагменте кода.

В целом, строка кода генерирует синтетический набор данных X с использованием функции make_blobs. Набор данных состоит из 500 точек данных, которые разделены на 4 отдельных кластера.

Шаг 3. Определите функцию для вычисления квадрата евклидова расстояния между двумя точками.

def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2) ** 2))

Разберем код построчно:

1. def euclidean_distance(x1, x2):: Эта строка определяет функцию с именем euclidean_distance, которая принимает два входных параметра, x1 и x2. Эта функция вычисляет евклидово расстояние между двумя точками в многомерном пространстве.
2. return np.sqrt(np.sum((x1 - x2) ** 2)): Эта строка содержит расчет для определения евклидова расстояния между x1 и x2. Вот разбивка расчета:

• (x1 - x2): соответствующие элементы x2 вычитаются из x1, в результате чего получается новый массив, представляющий разницу между координатами двух точек.
• (x1 - x2) ** 2: возводит в квадрат каждый элемент массива разностей, что гарантирует, что все значения будут положительными.
• np.sum((x1 - x2) ** 2): вычисляет сумму всех квадратов разностей, эффективно вычисляя сумму квадратов евклидовых расстояний в каждом измерении.
• np.sqrt(np.sum((x1 - x2) ** 2)): Наконец, это берет квадратный корень из суммы квадратов разностей, что дает евклидово расстояние между x1 и x2.

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

Шаг 4: Реализуйте алгоритм Breathing K-Means

def breathing_kmeans(X, k, epsilon=0.01, max_iterations=100):
    # Initialize cluster centers randomly
    centers = X[np.random.choice(len(X), size=k, replace=False)]

    # Repeat until convergence or maximum iterations reached
    for _ in range(max_iterations):
        # Assign each data point to the nearest cluster center
        clusters = [[] for _ in range(k)]
        for x in X:
            distances = [euclidean_distance(x, center) for center in centers]
            nearest_cluster = np.argmin(distances)
            clusters[nearest_cluster].append(x)

        # Update cluster centers by taking the mean of each cluster
        prev_centers = np.copy(centers)
        for i in range(k):
            if clusters[i]:
                centers[i] = np.mean(clusters[i], axis=0)

        # Check for convergence
        center_shift = np.mean([euclidean_distance(prev_centers[i], centers[i]) for i in range(k)])
        if center_shift < epsilon:
            break

    return centers

Разберем код построчно:

def breathing_kmeans(X, k, epsilon=0.01, max_iterations=100):

def breathing_kmeans(X, k, epsilon=0.01, max_iterations=100):: Эта строка определяет функцию с именем breathing_kmeans, которая принимает четыре входных параметра: X, который представляет набор данных, k для количества кластеров, epsilon для порога сходимости и max_iterations для максимального количества итераций.

centers = X[np.random.choice(len(X), size=k, replace=False)]

centers = X[np.random.choice(len(X), size=k, replace=False)]: Эта строка случайным образом инициализирует центры кластера. Он использует np.random.choice для случайного выбора k индексов из диапазона длины X без замены. Затем он использует эти индексы для извлечения соответствующих точек данных из X и назначает их в качестве начальных центров кластеров.

for _ in range(max_iterations):

for _ in range(max_iterations):: Эта строка запускает цикл, который повторяется до тех пор, пока не будет достигнуто сходимость или максимальное количество итераций. _ используется как соглашение, чтобы указать, что переменная цикла не используется в цикле.

clusters = [[] for _ in range(k)]
for x in X:
    distances = [euclidean_distance(x, center) for center in centers]
    nearest_cluster = np.argmin(distances)
    clusters[nearest_cluster].append(x)

Код в этом блоке присваивает каждой точке данных ближайший центр кластера. Он создает пустой список для каждого кластера в переменной clusters. Затем для каждой точки данных x в X он вычисляет евклидово расстояние между x и каждым центром кластера, используя функцию euclidean_distance. Он находит индекс ближайшего центра кластера, используя np.argmin, и добавляет x к соответствующему кластеру в списке clusters.

prev_centers = np.copy(centers)
for i in range(k):
    if clusters[i]:
        centers[i] = np.mean(clusters[i], axis=0)

Код в этом блоке обновляет центры кластеров, взяв среднее значение каждого кластера. Он создает копию текущих центров кластеров как prev_centers. Затем для каждого индекса кластера i проверяется, не является ли кластер пустым (if clusters[i]:). Если кластер не пуст, он вычисляет среднее значение по каждому измерению (axis=0) точек данных в кластере и присваивает результат обновленному центру кластера.

center_shift = np.mean([euclidean_distance(prev_centers[i], centers[i]) for i in range(k)])
if center_shift < epsilon:
    break

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

return centers

return centers: Эта строка возвращает окончательные центры кластеров после сходимости или максимальное количество итераций.

В целом, функция breathing_kmeans реализует алгоритм Breathing K-Means. Он случайным образом инициализирует центры кластеров, назначает точки данных ближайшим центрам кластеров, обновляет центры кластеров на основе среднего значения каждого кластера, проверяет сходимость и повторяет процесс до тех пор, пока не будет достигнута сходимость или максимальное количество итераций. Функция возвращает окончательные центры кластеров.

Шаг 5. Визуализируйте данные и центры кластеров

def plot_clusters(X, centers):
    plt.scatter(X[:, 0], X[:, 1], color='b', s=30)
    plt.scatter(centers[:, 0], centers[:, 1], color='r', marker='*', s=200)
    plt.title('Breathing K-Means Clustering')
    plt.show()

Разберем код построчно:

1. def plot_clusters(X, centers):: Эта строка определяет функцию с именем plot_clusters, которая принимает два параметра: X представляет набор данных, а centers представляет центры кластеров.
2. plt.scatter(X[:, 0], X[:, 1], color='b', s=30): Эта линия создает точечную диаграмму набора данных X. Он отображает значения первого столбца X по оси x и значения второго столбца по оси y. Параметр color='b' задает синий цвет точек данных, а s=30 определяет размер точек данных.
3. plt.scatter(centers[:, 0], centers[:, 1], color='r', marker='*', s=200): В этой строке добавляются маркеры точечной диаграммы для представления центров кластеров. Он отображает значения первого столбца centers по оси x и значения второго столбца по оси y. Параметр color='r' задает красный цвет маркеров, marker='*' устанавливает стиль маркера в виде звезды (*), а s=200 определяет размер маркеров.
4. plt.title('Breathing K-Means Clustering'): Эта строка задает заголовок графика «Дыхательная кластеризация K-средних».
5. plt.show(): Эта строка отображает график на экране.

В целом функция plot_clusters используется для создания точечной диаграммы набора данных X, где точки данных отображаются синим цветом, а центры кластеров отмечены красными звездочками. Функция также устанавливает заголовок графика на «Дыхательная кластеризация K-средних» и отображает график на экране. Эта визуализация помогает понять распределение точек данных и расположение центров кластеров в контексте алгоритма кластеризации Breathing K-Means.

Шаг 6. Примените алгоритм Breathing K-Means к данным и визуализируйте результаты.

k = 4
final_centers = breathing_kmeans(X, k)
plot_clusters(X, final_centers)

Разберем код построчно:

1. k = 4: Эта строка присваивает значение 4 переменной k. Это указывает на то, что мы хотим выполнить кластеризацию с 4 кластерами.
2. initial_centers = kmeans_plusplus(X, k): Эта строка вызывает функцию kmeans_plusplus с набором данных X и значением k. Он присваивает возвращенное значение, представляющее начальные центры кластера, переменной initial_centers. Функция kmeans_plusplus инициализирует центры кластеров с помощью алгоритма K-Means++.
3. plot_clusters(X, initial_centers): Эта строка вызывает функцию plot_clusters с набором данных X и начальными кластерными центрами initial_centers в качестве аргументов. Эта функция создает точечную диаграмму набора данных с точками данных, окрашенными в синий цвет, и начальными центрами кластеров, отмеченными красными звездочками. График помогает визуализировать начальное распределение точек данных и положение начальных центров кластеров.

Таким образом, эти строки кода выполняют следующие шаги:

• Определите количество желаемых кластеров (k).
• Вычислите начальные кластерные центры, используя алгоритм K-Means++.
• Визуализируйте набор данных и начальные кластерные центры, используя точечную диаграмму.

Вот и все! Вы реализовали алгоритм Breathing K-Means на Python. Полученный график покажет точки данных вместе с окончательными центрами кластеров, определенными алгоритмом Breathing K-Means.

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

Заинтересованные читатели могут прочитать следующий учебник по алгоритму K-средних:

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

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:

• 👏 Хлопайте за историю и подписывайтесь на автора 👉
• 📰 Смотрите больше контента в публикации Level Up Coding
• 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
• 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"

🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу