Авторы контента: Shray Khanna, Honghui Wang и Chhavi Verma

Разминка

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

Итак, по сути, k -means помогает вам формировать группы из немаркированных данных. Эти группы в техническом выражении называются «k кластерами», что помогает вам выполнять классификацию, которая должна быть произведена вами.

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

Почему важно k-средство?

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

Создание Spark, вдохновленное K-means

Есть интересная история о k -средствах. Когда Матей Захария учился в Калифорнийском университете в Беркли AMPlab в качестве доктора философии. студент, он реализовал параллельный алгоритм k -means, основанный на MapReduce, и запустил его в кластере. Оказалось медленнее, чем запускать на одном компьютере. После обсуждения со своими коллегами Матей Захария выяснил, что проблема заключается в повторении загрузки и сохранения данных с диска и на диск. Затем Матей Захария создал Spark.

Намочите ноги

Что такое алгоритм K-средних?

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

Например, если K = 3 и данные, k -means разделит набор данных на три группы, как показано ниже.

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

  1. Учитывая набор данных из m точек, случайным образом выберите K точек как центроиды кластера.
  2. Назначьте каждую точку данных ближайшему центроиду.
  3. Обновите центроиды кластера, каждый равен среднему значению всех назначенных ему точек данных.
  4. Повторяйте шаги 2 и 3 до тех пор, пока не будут выполнены некоторые условия завершения (т. Е. Центроид больше не изменится).

Начать дайвинг

Сходимость k-средних

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

Чтобы ответить на этот вопрос, мы прибегаем к математике.

Мы видим, что целью k -means является минимизация такой функции стоимости:

Итак, k -means - это, по сути, координатный спуск на J. В частности, второй шаг k -means многократно минимизирует J по отношению к c, удерживая фиксированное значение µ, и третий шаг минимизирует J относительно µ при фиксированном c. Очевидно, J монотонно убывает. Значит, значение J должно сходиться. (Как отметил Эндрю Нг в своем блестящем курсе машинного обучения Coursera, это означает, что c и µ тоже будут сходиться. Теоретически это возможно для k - означает колебание между несколькими различными кластерами, т. е. несколькими разными значениями для c и / или µ, которые имеют точно такое же значение J, но на практике этого почти не бывает.)

Гарантированно ли найти оптимальное решение?

К сожалению, это не так. Поскольку функция объекта не является выпуклой, мы можем застрять на локальных оптимумах.

Например, если нам повезет, мы можем получить начальные точки, как показано в (a), но иногда мы можем придумать инициализацию, как показано в (b) и (c), что, очевидно, даст нам локальное минимальное решение.

Мы видим, что k-средних уязвимо для выбора центроидов. Чтобы решить эту проблему, мы можем запустить k-средних много раз (50–10000) и выбрать то, которое имеет минимальную стоимость искажения.

Другой способ - использовать K-средство ++.

K-означает ++

Глядя на (a), (b) и (c), мы можем получить эту интуицию: каждый из k начальных центроидов кластера должен держаться подальше друг от друга как можно дальше. Другими словами, распределение начальных центроидов кластера k - это хорошо [4]. K -means ++ следует этой интуиции. Он выбирает центроиды один за другим. Каждый раз он вычисляет расстояние от каждой точки данных до ближайшего центроида. Чем больше расстояние, тем больше вероятность, что он будет выбран в качестве следующего центроида.

Вот алгоритм:

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

2. Вычислите квадратное расстояние от каждой точки до ближайшего к ней центроида и обозначьте его как d (x).

3. Выберите одну точку данных в качестве нового центроида с вероятностью, пропорциональной d (x).

4. Повторяйте шаги 2 и 3, пока не найдете k центроидов.

5. Отсюда мы можем использовать стандартные k-средства для кластеризации набора данных.

Дэвид Артур и Сергей Васильвицкий пришли к выводу в своей статье, что k -средний ++ постоянно превосходит k -средний [6]. Это не только дает гораздо лучшие результаты, но и ускоряет сходимость алгоритма. Когда K мало по сравнению с количеством точек данных, k -значает ++ улучшает производительность на несколько порядков.

Как определить количество кластеров?

На практике специалисты по обработке данных получают это число вручную, путем настройки параметров или по требованию задачи.

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

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

Быстрый взгляд в бездну

ISODATA

Предлагается алгоритм ISODATA для автоматического определения количества кластеров. Он имеет две операции: разделить и объединить. Он выбирает разделение кластера или объединение двух кластеров в зависимости от положения точек данных в кластерах.

Требуется еще четыре параметра:

  1. k₀: начальное количество кластеров, и он определяет диапазон конечного числа кластеров, который будет [ k₀ / 2, 2 * k₀]
  2. Nmin: минимальный размер каждого кластера.
  3. σ: когда дисперсия кластера больше, чем это, кластер будет разделен.
  4. Dmin: если расстояние между двумя центроидами кластера меньше Dmin, объедините эти два кластера.

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

Параллельная версия k-means.

K-means хорошо работает с процессом MapReduce. Используйте map (point) = (point, c), чтобы сопоставить каждую точку с ее ближайшим центроидом, затем объедините их, чтобы получить новый центроид.

K-средства для очень большого набора данных

Для поиска оптимального решения функции стоимости с большим набором данных мы обычно прибегаем к последовательным методам. Боттон и Бенжио предложили вариант k -средних [1] в режиме онлайн со стохастическим градиентом (SGD). Алгоритм вычисляет шаг градиентного спуска по одной случайно выбранной точке данных за раз. Из-за стохастического шума этот алгоритм находит решения более низкого качества, чем стандартные k-средних, хотя сходится гораздо быстрее.

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

Шлифовка

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

Мы использовали k -means в трех разных ситуациях, основанных на scikit-learn, и в основном использовали предустановленный набор данных scikit-learn, так что любой может реализовать без проблем с получением данных со сторонних веб-сайтов.

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

Далее мы использовали k -средство для распознавания рукописных цифровых данных. Простое применение k- означает, что мы видим точность 73%, что не так уж и плохо. После некоторой предварительной обработки мы можем достичь 93%.

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

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

У Джейка Вандерпласа есть замечательная книга по науке о данных: Справочник по науке о данных Python Джейка Вандерпласа (O’Reilly Media, 2016). Мы реализовали K-means, используя его книги и заметки по алгоритму. Ссылка на его сайт: https://jakevdp.github.io/pages/about.html

Ссылка

[1] Ботто, Леон и Йошуа Бенджио. «Свойства сходимости алгоритмов k-средних». Достижения в области нейронных систем обработки информации. 1995 г.

[2] Скалли, Дэвид. «Кластеризация k-средних в веб-масштабе». Материалы 19-й международной конференции во всемирной паутине. ACM, 2010.

[3] Эндрю Н.Г.; Онлайн-курс по машинному обучению; https://www.coursera.org/learn/machine-learning

[4] K-означает ++; wikipedia; https://en.wikipedia.org/wiki/K-means%2B%2B

[5] ВНЕДРЕНИЕ SCI-KIT: https://scikit-learn.org/stable/index.html

[6] Артур, Дэвид и Сергей Васильвицкий. «K-means ++: преимущества тщательного посева». Материалы восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2007.

[7] Лю, Хунфу, Цзюнь Ли, Юэ У и Юнь Фу. «Кластеризация с удалением выбросов». Препринт arXiv arXiv: 1801.01899 (2018).

[8] Кристи, А., Г. Мира Ганди и С. Вайтьясубраманян. «Кластерный алгоритм обнаружения выбросов для медицинских данных». Процедуры информатики 50 (2015): 209–215.