Всем привет,

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

Надеюсь, вам понравится читать эту статью так же, как мне понравилось ее исследовать и писать. Благодаря этой серии я увлекся машинным обучением и тем, как оно может помочь нам решать сложные проблемы и принимать более правильные решения. Если вы разделяете эту страсть, то вы попали по адресу. Давайте погрузимся!

K-Means — один из популярных и простых алгоритмов кластеризации. Это метод обучения без учителя, целью которого является разделение набора точек данных на несколько групп (называемых кластерами) на основе их сходства.

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

Нам нужно знать, что алгоритм должен работать, в этом случае K-средние требуют следующих входных данных:

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

Определение оптимального количества кластеров (k) является важным шагом в эффективном использовании алгоритма k-средних. Существует несколько методов, которые можно использовать для оценки оптимального значения k, в том числе:

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

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

Следующее, что нужно сделать, это инициализировать центроиды. В этом алгоритме существуют разные способы инициализации k центроидов, в том числе:

  • Случайная инициализация: k центроидов выбираются случайным образом из точек данных. Это простой и часто используемый метод, но он может привести к неоптимальной кластеризации, если исходные центроиды не являются репрезентативными для распределения данных.
  • Инициализация K-means++: направлена ​​на выбор k центроидов, которые находятся далеко друг от друга и представляют распределение данных. Он включает в себя выбор первого центроида случайным образом из точек данных, а затем выбор последующих центроидов на основе расстояния от ранее выбранных центроидов. Этот метод обычно приводит к более высокой производительности кластеризации, чем случайная инициализация.
  • Ручная инициализация: в некоторых случаях пользователь может иметь предварительные знания о данных и ожидаемых кластерах и может вручную указать начальные центроиды.

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

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

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

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

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

После расчета расстояния алгоритм присваивает каждую точку данных кластеру с ближайшим центроидом.

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

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

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

К его преимуществам мы можем отнести следующие:

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

Однако K-Means не лишен ограничений, в том числе:

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

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

Алгоритм K-Means имеет несколько применений в различных дисциплинах, в том числе:

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

Хотя K-Means — очень эффективный алгоритм, имеющий множество приложений, он может не подходить для некоторых ситуаций, например, для категориальных данных, как говорилось ранее. Точно так же могли быть некоторые недостатки, которые привели к разработке вариантов и расширений этого алгоритма, включая K-Modes.

K-Modes — это алгоритм кластеризации, специально разработанный для категориальных данных и основанный на тех же принципах, что и K-Means. Таким образом, алгоритм представляет собой важное расширение и подчеркивает постоянное развитие методов кластеризации для удовлетворения разнообразных потребностей исследователей и практиков.

Было предложено несколько вариантов и расширений алгоритма K-Means. Некоторыми примерами являются K-Medoids, Fuzzy C-Means и K-Prototype. Первый заменяет вычисление среднего значения выбором репрезентативной точки данных из каждого кластера, известной как медоид, что делает его более устойчивым к выбросам и шуму в данных.

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

Наконец, расширение K-Prototype представляет собой гибридный алгоритм, который сочетает в себе K-средние и K-режимы для кластеризации наборов данных как с числовыми, так и с категориальными данными. Он присваивает вес каждому объекту в зависимости от его типа и использует его для расчета расстояния между точками данных.

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

Учебник по Python

Чтобы обеспечить совместимость, для этого руководства рекомендуется использовать дистрибутив Anaconda. Однако, если у вас не установлена ​​Anaconda и вы хотите использовать доверенное ядро, вы можете вручную установить необходимые пакеты с помощью pip. Вы можете выполнить предоставленный блок кода, раскомментировав строку «import sys», чтобы автоматически установить необходимые пакеты.

Чтобы выполнить это руководство, нам нужно импортировать несколько важных библиотек в Python.

Мы импортируем NumPy, мощную библиотеку для числовых операций с массивами, которая предоставляет эффективные математические функции и инструменты. Затем мы импортируем pandas, широко используемую библиотеку обработки и анализа данных, которая позволяет нам работать со структурированными данными в табличном формате.

Чтобы визуализировать результаты нашего анализа кластеризации, мы импортируем matplotlib.pyplot, библиотеку построения графиков, которая позволяет нам создавать типы диаграмм и графиков. Это поможет нам понять закономерности и взаимосвязи внутри данных.

Для фактического процесса кластеризации мы импортируем модуль KMeans scikit-learn. Чтобы обеспечить точные результаты, мы также импортируем модуль StandardScaler из подмодуля предварительной обработки scikit-learn. Он используется для масштабирования признаков, что помогает нормализовать данные и повысить производительность алгоритма кластеризации.

Наконец, мы импортируем silhoutte_score из метрического модуля scikit-learn. Silhouette Score — это показатель, используемый для оценки качества результатов кластеризации. Он измеряет, насколько хорошо каждая точка данных вписывается в назначенный ей кластер.

Далее мы используем данные о жилье из CSV-файла под названием housing.csv, вы можете найти этот файл на следующей странице Kaggle: Цены на жилье в Калифорнии | Кэггл. Указываем интересующие столбцы (долгота, широта и median_house_value).

Затем мы удаляем все строки с пропущенными значениями (NaN). Это гарантирует, что мы работаем с чистым и полным набором данных для дальнейшего анализа.

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

Мы создаем экземпляр класса StandardScaler из модуля предварительной обработки scikit-learn. Это поможет нам нормализовать данные и привести их к стандартному масштабу.

Когда мы выполняем fit.transform, метод вычисляет среднее и стандартное отклонение каждого объекта в наборе данных и соответствующим образом применяет преобразование масштабирования. Мы сохраняем это значение в переменной data_scaled.

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

На этом этапе инициализируйте пустой список под названием «silhouette_scores» для хранения оценок. Затем мы перебираем диапазон значений k от 2 до 10. Для каждого значения k мы создаем экземпляр класса KMeans с k кластерами и подгоняем масштабированные данные к модели.

Затем мы вычисляем оценку силуэта для кластеризованных данных с помощью функции Silhouette_score, которая измеряет качество результатов кластеризации. Полученная оценка добавляется в список Silhouette_score.

Наконец, мы строим график оценок силуэта в зависимости от значений k, где ось x представляет количество кластеров (k), а ось y представляет коэффициент силуэта. График помечается соответствующими метками осей и заголовком и отображается.

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

Мы устанавливаем количество кластеров (k) равным 2, разделяя данные на две отдельные группы. Затем мы создаем экземпляр класса KMeans с указанным количеством кластеров. В качестве метода инициализации мы используем K-Means++, который широко используется и помогает улучшить сходимость алгоритма. Кроме того, мы установили случайное состояние 42, чтобы обеспечить воспроизводимость результатов.

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

Наконец, мы получаем метки кластеров и центроидов и устанавливаем метки диаграммы рассеяния, чтобы показать наш график.

Центроиды кластера отмечены красными крестиками. Для дальнейшего изучения этого алгоритма вы можете посетить наш репозиторий GitHub, где вы можете получить доступ к полному коду для удобного выполнения и настройки.

В заключение

K-Means — это популярный алгоритм кластеризации в машинном обучении, целью которого является разделение точек данных на кластеры на основе их сходства. Это метод обучения без учителя, который позволяет находить закономерности в данных.

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

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

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

Оценку результата кластеризации можно выполнить с использованием таких показателей, как сумма квадратов внутри кластера или оценка силуэта. K-Means находит применение в сегментации рынка, сегментации изображений, обнаружении аномалий, биоинформатике и анализе социальных сетей.

Хотите глубже погрузиться в увлекательный мир машинного обучения и изучить более мощные алгоритмы, такие как K-Means? Если да, то я приглашаю вас продолжить обучение и раскрыть потенциал этой захватывающей области. Вы можете изучить другие наши руководства и ресурсы, чтобы предоставить подробные объяснения и практические примеры, которые помогут вам шаг за шагом реализовать алгоритмы машинного обучения.

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

Рекомендации

Бабиц, К. (2023). Введение в кластеризацию k-средних с помощью scikit-learn в Python. https://www.datacamp.com/tutorial/k-means-clustering-python

Алгоритм кластеризации K-средних — JavatPoint. (без даты). www.javatpoint.com. https://www.javatpoint.com/k-means-clustering-algorithm-in-machine-learning

Ли Ю. и Ву Х. (2012). Метод кластеризации, основанный на алгоритме K-Means. Physics Procedia, 25, 1104–1109. https://doi.org/10.1016/j.phpro.2012.03.206

Маннор С., Джин Х., Хан Дж., Цзинь Х., Хан Дж., Цзинь Х., Хань Дж. и Чжан Х. (2011). Кластеризация K-средних. В электронных книгах Springer (стр. 563–564). https://doi.org/10.1007/978-0-387-30164-8_425

Т. Канунго, Д.М. Маунт, Н.С. Нетаньяху, К.Д. Пятко, Р. Сильверман и А.Ю. Ву, «Эффективный алгоритм кластеризации k-средних: анализ и реализация», в IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, нет. 7, стр. 881–892, июль 2002 г., doi: 10.1109/TPAMI.2002.1017616.

Вы можете быть в курсе событий с Accel.AI; семинары, исследования и социальные инициативы через наш веб-сайт, список рассылки, группу встреч, Твиттер и Фейсбук.

Присоединяйтесь к нам в реализации инициатив #ИИ для #SocialImpact по всему миру!

Если вам понравилось это читать, вы можете поделиться хорошим настроением (и помочь большему количеству людей узнать об этом посте и нашем сообществе), нажав 👏 ниже — это очень много значит!