Введение в k-средних, иерархических k-средних и его родственников в мини-пакетах
K -средний кластеризация - это широко используемый метод в машинном обучении, используемый как форма векторного квантования для разделения векторного пространства точек на k кластеров. Это чрезвычайно полезный неконтролируемый метод кластеризации нескольких точек в набор центроидов, который впоследствии можно использовать для многих последующих задач с глубоким обучением. Однако иногда стандартные k -средства слишком затратны с точки зрения вычислений или требуют нескольких дней для работы с большими наборами данных. Именно здесь такие методы, как использование k -средств иерархически или использование данных в мини-пакетах, значительно повышают эффективность, сохраняя при этом сопоставимую производительность.
K-означает
Ванильный алгоритм k -means начинается с данных в векторном пространстве, которое мы назовем X, где X состоит из r очки (x₁, x₂,…, xᵣ). Мы хотели бы по существу подогнать k центроидов на X, чтобы для каждого кластера центроидов дисперсия была минимальной. С точки зрения непрофессионала, это означает, что набор точек каждого центроида образует красивый кластер, отличный от кластера любого другого центроида.
Так как же это сделать на практике? Есть много способов сделать это, но k -means использует так называемый алгоритм Ллойда. Сначала центроиды инициализируются случайными точками в векторном пространстве. Каждой точке в X назначается центроид, который вычисляется путем нахождения ближайшего центроида к каждой точке. После этого положение каждого центроида обновляется до среднего значения всех точек, с которыми он связан, или его кластера. Однако после этого шага некоторые точки в X будут присвоены другому центроиду, учитывая, что положения центроида были обновлены. Итак, мы повторяем предыдущие шаги, обновляя положение каждого центроида, чтобы отразить изменение среднего значения точек в его кластере. Мы делаем это до тех пор, пока положение центроидов больше не изменится, или, другими словами, когда они не сойдутся. Это позволяет центроидам тяготеть к средствам присущих кластеров, присутствующих в данных. Вот гифка, которая иллюстрирует весь процесс:
Как видите, этот наивный метод кластеризации k -значений довольно хорошо работает для небольших наборов данных. Однако есть много способов сделать это быстрее и эффективнее.
Иерархические k -средства
Иерархическая k -значит кластеризацию (также известную как hk -создаёт кластеризацию), не путать с иерархической кластеризацией (которая представляет собой нечто совершенно иное), является более эффективным родственником vanilla k - означает. Это рекурсивный метод, включающий выполнение k -средств для данных, при этом k относительно мал, а затем выполнение k -средств для каждого кластера центроидов с использованием то же k для h иерархий. Центроиды последней иерархии объединяются в центроиды всего набора данных. Этот метод полезен при большом k и когда обновление центроидов k требует больших вычислительных ресурсов. Наглядное представление этого метода показано ниже:
Минибатчи к-средние
Как следует из названия, minibatch k -means и minibatch hk -means используют мини-пакеты, чтобы сделать этот алгоритм применимым к очень большим наборам данных. Подобно тому, как нейронная сеть потребляет данные пакетами, это ответвление k -means выполняет итерацию и обновляет центроиды после каждого пакета. Это упрощает использование k -средств для больших наборов данных и получения результатов, относительно похожих на результаты, которые дает обычное k -средство. Чтобы увидеть закодированный пример minibatch hk-means, ознакомьтесь с этим пакетом python:
Вывод
K -means - полезный метод, который можно использовать в качестве метода кластеризации, векторного квантования и многого другого. Он также имеет несколько ответвлений, которые могут повысить производительность и эффективность работы с большими наборами данных в реальном мире. Двумя из этих вариантов являются иерархические k -средства и мини-пакетные k -средства, но есть бесчисленное множество других способов дальнейшего улучшения этой производительности, например, разумная инициализация центроидов. При таком большом количестве применений и стольких улучшений неудивительно, что k -means остается одним из самых известных алгоритмов кластеризации в машинном обучении.
