Подробно объясните две классические оптимизации Kmeans — мини-пакет и Kmeans++.

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

СегодняБумага 13 в темах машинного обученияВ этой статье давайте рассмотрим оптимизацию алгоритма Kmeans.

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

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

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

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

То есть мыслительный процесс анализа и решения проблем важнее, чем само решение.

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

mini batch

Идея мини-пакета очень проста.Поскольку объем данных во всей выборке слишком велик, это сделает нашу итерацию слишком длинной, тогда мыУменьшить размер данныхХорошо?

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

Мы действительно можем повысить эффективность итерации с помощью выборки, но гарантирует ли это правильность?

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

Мы использовали код, разработанный на прошлой неделе, без какой-либо оптимизации, и увеличили количество сгенерированных выборок до 50 000. Из рисунка ниже видно, что простым Kmeans потребовалось 37,2 секунды для завершения расчета. Результаты кластеризации, которые мы получаем, следующие:

Затем мы передаем random.choice под numpy,Случайным образом выберите 1000 образцов из, сравниваем время и результаты до и после.

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

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

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

Kmeans ++

Если мини-партия — это общий метод, который кажется немного сложным, то метод, который будет представлен ниже, гораздо более хардкорный. СюдаОптимизируйте непосредственно на самом алгоритме KmeansОтсюда и название Kmeans++.

Как мы уже говорили в предыдущей статье, вероятно, есть две отправные точки для оптимизации эффективности алгоритма Kmeans. Во-первых, количество выборок слишком велико, а во-вторых, слишком много итераций. Только что представленный мини-пакет предназначен для случая слишком большого количества выборок, а метод Kmeans++ — для количества итераций. каким-то образом мыСократите количество итераций, необходимых для сходимости, чтобы добиться быстрой сходимости.

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

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

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

Очевидно, что идти прямо нельзя, и нам нужно идти в обход.

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

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

Эта проблема существует, и нам нужно избегать ситуации, когда выбираются точки из одного кластера. Но поскольку мы не знаем распределения выборок, как мы можем судить?

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

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

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

Принцип алгоритма

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

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

Мы повторяем описанный выше процесс до тех пор, пока не будет выбрано в общей сложности K кластерных центров.

Рулетка

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

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

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

Выразим это формулой, вероятность быть выбранным для каждой точки:

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

Метод рулетки на самом деле представляет собой процесс имитации лотереи на поворотном столе, но мы моделируем поворотный стол с помощью массива. Мы сплющиваем сектора поворотного стола в полосы, и каждый исходный сектор соответствует интервалу. Площадь сектора соответствует длине интервала, очевидно, чем больше длина, тем больше вероятность выигрыша. Затем подходим к лотерее, умножаем сумму длины интервала на число в интервале 0-1.

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

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

Суммировать

После понимания алгоритма рулетки всю идею Kmeans++ можно увидеть с первого взгляда. Другими словами, мы сравниваем извлечение центров кластеров с лотереей в рулетке и используем рулетку для извлечения K выборок в качестве начальных центров кластеров. Тем самым максимально сокращая количество итераций и приближаясь к конечному результату.

Итак, действительно ли этот подход работает?

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

Эта функция очень проста, достаточно рассчитать расстояние и взять минимальное значение:

def get_cloest_dist(point, centroids):
    # 首先赋值成无穷大，依次递减
    min_dist = math.inf
    for centroid in centroids:
        dist = calculateDistance(point, centroid)
        if dist < min_dist:
            min_dist = dist
    return min_dist

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

import math
import random

def kmeans_plus(dataset, k):
    clusters = []
    n = dataset.shape[0]
    # 首先先选出一个中心点
    rdx = np.random.choice(range(n), 1)
    # np.squeeze去除多余的括号
    clusters.append(np.squeeze(dataset[rdx]).tolist())
    d = [0 for _ in range(len(dataset))]
    for _ in range(1, k):
        tot = 0
        # 计算当前样本到已有簇中心的最小距离
        for i, point in enumerate(dataset):
            d[i] = get_cloest_dist(point, clusters)
            tot += d[i]
        # random.random()返回一个0-1之间的小数
        # 总数乘上它就表示我们随机转了轮盘
        tot *= random.random()
        # 轮盘法选择下一个簇中心
        for i, di in enumerate(d):
            tot -= di
            if tot > 0:
                continue
            clusters.append(np.squeeze(dataset[i]).tolist())
            break
    return np.mat(clusters)

Наконец, давайте сделаем снимок и посмотрим на эффект:

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

КонечноСам Kmeans++ также является случайным, не каждая случайная отправная точка может иметь такой хороший эффект, но с помощью стратегии мы можем гарантировать, что даже в худшем случае не будет так уж плохо.

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

Вот и все на сегодняшнюю оптимизацию Kmeans.Если вы чувствуете, что что-то получили, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.