Теория алгоритмов с простым объяснением.

Что такое кластер?

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

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

Теперь в будущем, когда мы получим данные Y для прогнозирования, мы просто проверяем, с какой группой совпадают наши данные Y (проверим сходство) и что данные Y будут предсказаны как эта конкретная часть группы. Вот так мы прогнозируем.

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

Применения кластеризации

  • Для сегментации клиентов. Вы можете группировать своих клиентов на основе их покупок, действий на вашем веб-сайте и т. д. Это полезно, чтобы понять, кто ваши клиенты и что им нужно, чтобы вы могли порекомендовать им правильный продукт в соответствии с их бюджетом.
  • Для анализа данных. При анализе нового набора данных часто бывает полезно сначала обнаружить кластеры похожих экземпляров, так как зачастую проще анализировать кластеры по отдельности.
  • Для обнаружения аномалий (также называемого обнаружением выбросов): любой экземпляр, который имеет низкое сходство со всеми кластерами, скорее всего, будет аномалией. Например, если вы группируете пользователей своего веб-сайта на основе их поведения, вы можете обнаружить пользователей с необычным поведением, например необычным количеством запросов в секунду и т. д. Обнаружение аномалий особенно полезно при обнаружении дефектов в производстве или для обнаружения мошенничества.
  • Для поисковых систем: всякий раз, когда мы ищем запрос в Google, существует алгоритм кластеризации, который сопоставляет наш запрос с кластерами запросов, и если он совпадает с каким-либо кластером, мы соответственно получаем ответ.

Помимо этого, существует множество приложений кластеризации.

Подходы к кластеризации:

Существует два подхода к кластеризации

  1. Агломеративный. Этот подход сначала рассматривает все точки как отдельные кластеры, затем выясняет сходство между двумя точками и, если обнаруживает некоторое сходство, помещает их в один и тот же кластер. Это также называется подходом «снизу вверх».
  2. Разделение: это противоположно агломеративному подходу. Он считает все точки частью большого кластера и на следующем шаге пытается найти точки, наименее похожие друг на друга, а затем разбивает большой кластер на маленькие. Это также называется подходом «сверху вниз».

Ниже приведены 3 мощных алгоритма кластеризации в ML.

1. DBSCAN (пространственная кластеризация приложений с шумом на основе плотности)

2. Кластеризация K-средних

3. Иерархическая кластеризация

Начнем с того, что легко понять.

Кластеризация K-средних:

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

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

Теория:

Теория, обсуждавшаяся выше, может быть математически выражена как:

  • Пусть C1, C2, Ck — k кластеров
  • Тогда мы можем написать: C1UC2UC3U……. CkU = {1,2,3,…,n}, то есть каждая точка данных была назначена кластеру. Объединение всех кластеров должно представлять наш полный набор данных.

Здесь U→ союз,

  • Кроме того, пересечение одного кластера с другим кластером не должно давать вам никаких данных.
  • Идея, лежащая в основе подхода кластеризации K-средних, заключается в том, что вариация внутри кластера среди точек должна быть минимальной. Дисперсия внутри кластера обозначается: W(Ck). Следовательно, согласно приведенному выше утверждению, нам нужно минимизировать эту дисперсию для всех кластеров. Просто оставьте это, если вы не поняли этот момент.

Давайте рассмотрим несколько шагов для расчета K, это развеет все ваши сомнения.

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

Что такое wcss?

Вот очень простой подход, он сначала найдет центроид точек данных (центроид — это точка, в которой мы можем сбалансировать объект). Давайте рассмотрим черную точку как наш центроид в этом наборе данных.

Шаг 2. От центроида каждая точка данных находится на определенном расстоянии, поэтому теперь с помощью формулы wcss рассчитывается расстояние между каждой точкой.

1-е суммирование дает сумму расстояний по n точкам от центроида, а 2-е суммирование - от всех кластеров.

Где,

х → n-точка

х | → центр тяжести

Nc → количество кластеров/K

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

При К = 2:

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

Теперь создано 2 кластера, но все точки набора данных не покрыты.

Шаг 4. Теперь найдите центр тяжести новых кластеров, а также найдите ближайшие n точек из вновь созданного центроида.

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

Когда K=2, мы в конечном итоге создадим 2 кластера C1 и C2 из всего набора данных, но поскольку мы продолжаем увеличивать значение K, в одной точке k будет равно к количеству точек данных, например, если у нас есть 100 записей в наборе данных и K = 100, можете ли вы угадать в этом случае, каково будет наше расстояние wcss? Наверняка будет ноль. Здесь, если K = точки данных, то каждая точка станет кластером сама по себе, поскольку расстояние точки данных от центроида равно нулю. Так что мы будем продолжать следовать этому подходу, т. е. мы начнем с кластера K = 1 и так далее. Максимальное значение wcss, которое мы получим, когда кластер только один (т.е. K=1), потому что у него будет только один центроид, и от этого центроида будет рассчитано расстояние до всех точек данных. Это уменьшение значения wcss по отношению к увеличению числа значений кластера можно визуализировать на графике, называемом График локтя.

По этому графику мы пытаемся найти, в какой точке мы получаем дисперсию (то есть после определенной точки линия будет почти гладкой) на графике, это механизм, основанный на наблюдении. На приведенном выше графике мы видим почти K=4 дисперсию, и именно так мы выбираем значение K в кластеризации K-средних. сильный>.

Как только мы получим значение K, нам просто нужно указать значение k= (число, полученное из диаграммы локтя) в формуле wcss, и наша кластеризация завершена.

Я завершил все шаги в шотэ, чтобы помнить.

  1. Случайным образом назначьте K центров.
  2. Вычислите расстояние всех точек от всех центров K и распределите точки по кластеру на основе кратчайшего расстояния. Инерция модели – это среднеквадратичное расстояние между каждым экземпляром и ближайшим к нему центроидом. Цель состоит в том, чтобы иметь модель с низкими интервалами.
  3. Как только все точки будут назначены кластерам, пересчитайте центроиды.
  4. Повторяйте шаги 2 и 3, пока расположение центроидов не перестанет меняться, а распределение точек в кластере не станет постоянным.

Итак, вот как работает кластеризация K-средних.

Иерархическая кластеризация:

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

Этот алгоритм использует восходящий (или агломеративный) подход к построению кластера. Мы начнем с определения сходства между точками данных. Точки, которые находятся ближе друг к другу, более похожи, чем точки, которые находятся дальше. Алгоритмы начинаются с рассмотрения всех точек как отдельных кластеров, а затем группировки точек вместе для формирования кластеров. Давайте разберемся на примере:

Рассмотрим набор данных о городах, в котором у нас есть несколько ИТ-городов из Северной Индии и Южной Индии.

Названия городов → Дели, Варанаси, Нойда, Бангалор, Карнатака, Ченнаи, Хайдарабад, Мумбаи, Пуна.

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

Как и в этом примере, в реальном мире Мумба и Пуна очень близки друг к другу, поэтому связь между ними можно увидеть, и здесь связь показана путем объединения 2 кластеров в один новый кластер. Аналогично для других.

Итак, Дели и Нойда — кластер 1, Варанаси и Калькутта — кластер 2, Хайдарабад — 3-й, Бангалор и Ченнаи — кластер 4, Мумбаи и Пуна — наш кластер 5. Мы снова проверим расстояние между кластерами, как мы это делали раньше.

Итак, предположим, что кластер 1 и кластер 2 расположены близко друг к другу и образуют новый кластер, такой же, как кластеры 3 и 4. Вот как теперь будет выглядеть наша дендрограмма.

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

Теперь на дендрограмме создается несколько горизонтальных линий, которые будут пересекать вертикальные линии, как показано ниже:

X → отображение пересечений

Несколько горизонтальных линий показывают различные пересечения, например, линия 1 имеет 2 точки пересечения, линия 2 имеет 3 пересечения и так далее. Эти пересечения линий подскажут, на сколько кластеров можно разделить данные, но здесь какую линию пересечения выбрать? Таким образом, ответ на этот вопрос таков: на основе расстояния или высоты вертикальной линии, которая представляет собой расстояние между кластерами, линиями зеленого цвета.

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

Примечание: существует множество алгоритмов, которые помогут в выборе линий.

Количество кастеров окончательно определяется на основе пересечений, здесь у нас есть 2 пересечения i1 и i2, что означает, что набор данных можно разделить на 2 кластера, как показано на рисунке ниже, и наверняка у нас будет 2 кластера, потому что мы взяли набор данных, в котором некоторые города из южной Индии, а некоторые из северной Индии.

Итак, в итоге мы строим 2 кластера.

Я упростил весь этот процесс иерархической кластеризации в алгоритме sudo следующим образом:

  1. Начните с n наблюдений и меры (например, евклидова расстояния) всех n (n−1)/2 попарных различий (или вообще евклидовых расстояний). Рассматривайте каждое наблюдение как отдельный кластер. Изначально у нас есть n кластеров.
  2. Сравните все расстояния и поместите две самые близкие точки/кластеры в один и тот же кластер. Несходство (или евклидовы расстояния) между этими двумя кластерами указывает на высоту в дендрограмме, на которой должна располагаться линия слияния.
  3. Вычислите новые попарные различия между кластерами (или евклидовы расстояния) среди оставшихся кластеров.
  4. Повторяйте шаги 2 и 3, пока у нас не останется только один кластер.

Ниже приведен еще один пример, в котором я пытался рассматривать числа как набор данных:

DBSCAN:

Это неконтролируемый алгоритм машинного обучения. Этот алгоритм определяет кластеры как непрерывные области высокой плотности. Этот алгоритм способен обрабатывать набор данных, содержащий шум/выбросы. Но как?. Давайте поймем, что это работает, на все ваши вопросы будут даны ответы автоматически.

Есть некоторые термины, которые вы должны знать, прежде чем продолжить:

Epsilon: также называется eps. Это расстояние, до которого мы ищем соседние точки.

Min_points: минимальное количество баллов, указанное пользователем.

Основные точки. Если количество точек внутри радиуса eps точки больше или равно min_points, эта точка называется центральной. .

Точки границы. Если количество точек внутри радиуса eps точки меньше, чем min_points, и она находится в пределах радиуса eps радиус области центральной точки, она называется граничной точкой.

Шум. Точка, которая не является ни центральной, ни граничной точкой, является точкой шума.

Не беспокойтесь, если вы не понимаете, мы тщательно изучим это,

Итак, давайте предположим, что у нас есть n точек данных, пользователь определяет радиус и минимальное количество точек, которые должны быть в радиусе, и только когда он удовлетворяет некоторым критериям, мы можем назвать его кластером, и помня об этом. пользователи должны установить критерии Min_points & radius, т.е. EPS.

Если мы создаем кластер, наверняка кластер имеет некоторый радиус, а здесь радиус не что иное, как Эпсилон или eps.

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

Шаг 1.Алгоритм начинается со случайной точки в наборе данных, которая еще не была посещена, и ее соседние точки определяются на основе значения EPS.

Рассмотрим набор данных:

Из набора данных выбирается случайная точка данных d1, и предположим, что мы сохраняем eps=2, поэтому создается круг с радиусом 2, d1в качестве центроида.

Шаг 2.Если точка содержит больше или равно количеству точек, чем min_pts, начинается формирование кластера, и эта точка становится основной точкой, иначе это считается шумом. Здесь следует отметить, что точка, первоначально классифицированная как шум, может позже стать граничной точкой, если она находится в радиусе eps от центральной точки.

Здесь предположим, что пользователь назначил min_pts =1, что означает, что круг, созданный в точке d1, в этом круге должен быть в списке 1 точка данных, и если он удовлетворяет условию, круг теперь является кластером и d1 станет ключевым моментом.

Если круг создается в другой случайной точке и если он не удовлетворяет критерию min_points, установленному пользователем, он рассматривается как Шум. В будущем возможно, что шум может стать пограничной точкой, когда он попадает под другие случайные точки eps и в случае, если точка данных находится очень далеко от набор данных (т.е. выбросы) останется как Noise.

Пограничная точка: если основная точка и ее eps удовлетворяют критерию min_point, то точки внутри eps называются граничными точками.

Шаг 3.Если точка является центральной, то все ее соседи становятся частью кластера. Если точки в окрестности оказываются основными точками, то их соседи также являются частью кластера.

Здесь b1 — граничная точка, снова она создаст eps в этой точке и проверит, удовлетворяет ли она критерию min_point, если она удовлетворяет этой граничной точке, а затем преобразует ее в основную точку.

Кроме того, сосед старой базовой точки и сосед новой базовой точки являются частью одного кластера. Если какая-либо пограничная точка не удовлетворяет критериям, она остается пограничной точкой.

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

Так вот как создаются кластеры DBSCAN.

Эти 3 алгоритма считаются мощными алгоритмами кластеризации.

Спасибо, что прочитали. Пожалуйста, нажмите "Нравится" и оставьте свой отзыв.

Надеюсь, эта статья окажется вам полезной.