Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняБумага 12 в темах машинного обученияВ этой статье давайте рассмотрим алгоритм кластеризации Kmeans.
В предыдущей статье мы обсуждали алгоритм KNN.Алгоритм KNN очень нагляден.Он находит ближайшие K соседей по формуле расстояния и выводит текущий результат по результатам соседей. Алгоритм, который мы рассмотрим сегодня, также очень интуитивно понятен и является одним из самых классических алгоритмов кластеризации — Kmeans.
Мы все знаем, что Means означает средний на английском языке, так что это также переводится наК-означаеталгоритмический. Конечно, смысл тот же, и кластеры выборок получаются путем вычисления среднего значения.
Теперь, когда мы знаем, что алгоритм Kmeans связан со средним значением и кластером, остается только два вопроса: во-первых, как нам прийти кВычислить среднее значение, и, во-вторых, когда мы получим среднее значение, как мы его сгруппируем?
Алгоритм кластеризации
Давайте сначала поставим два вышеприведенных вопроса.Для начала рассмотрим пример.Предположим,у нас есть ряд выборок доходов пользователей.Мы хотим разделить эту группу пользователей на богатых и средний класс в зависимости от их дохода,места проживания и потребления. класс и рабочий класс.
В этой задаче мы знаем только, что хотим разделить выборки на три категории, но не знаем, как их разделить.Это то, что мы хотим, чтобы модель делала за нас. Другими словами, мы надеемся, что модель сможет автоматически определить корреляцию между этими выборками и собрать вместе выборки с сильной корреляцией, чтобы получитькластер. В этой задаче мы хотим, чтобы модель классифицировала данные для нас по трем категориям.
Если мы позволим разделить эту задачу вручную, конечно, это очень просто, и мы разделим ее напрямую по доходам этих пользователей. Непосредственно нарисуйте линейный график доходов пользователя, а затем найдите две лучшие точки разделения, и это будет сделано быстро, путем деления трех и пяти на два. Но что, если в наших фичах нет дохода пользователя? Если бы мы могли знать, есть ли у пользователя машина, дом, сбережения дома и все внешние долги, это не так интуитивно понятно, но легко, и нам легко просто смоделировать это. Кроме того, если у нас даже нет информации о гараже, мы можем получить только то, где пользователь работает и где он живет? Является ли этот вопрос более абстрактным?
Когда функции относительно абстрактны и неясны, нам часто бывает нелегко разделить их напрямую, поскольку мы не знаем реальных меток, мы не можем использовать модель с учителем. Чтобы решить проблему, Kmeans может сделать только наоборот, мы больше не разделяем данные, аПусть относительно близкие данные собираются вместе сами по себе. На этой идее основан алгоритм Kmeans.Метод сбора данных по определенному алгоритму без их разделения называетсяАлгоритм кластеризации.
В задаче кластеризации серия выборок агрегируется моделью в соответствии с атрибутами данных и становится одной и той же категорией. Категории здесь называются кластерами этих выборок. Центральная точка каждого кластера называется центром кластера. Следовательно, алгоритм KMeans, как следует из названия, заключается в использовании выборки в соответствии со значением K, установленным пользователем.Всего K кластеров.
Принцип K-средних
Не знаю, слышали ли вы о такой теории.Люди и компьютеры на самом деле противоположности. Некоторые проблемы, сложные для человека, очень просты для компьютера. Например, память: людям трудно запомнить большое количество вещей за одно мгновение, а компьютерам - нет. Пока пропускная способность и емкость достаточны, никакие данные не могут быть запомнены. Его можно не только запомнить, но и никогда не ошибиться. Другим примером является вычисление. Людям трудно быстро вычислять сложные формулы. В основном, умножение и деление более чем двух цифр должны использовать инструменты. Но компьютеры - нет.Пока ресурсов процессора достаточно, можно выполнить большой объем вычислений.
Однако то, что легко для человека, очень сложно для компьютера. Например, в зрении мы, люди, легко различаем кошек и собак на картинках, а компьютеры — нет. Даже сегодня, когда популярны глубокое обучение и искусственный интеллект, нам приходится специально разрабатывать сложные модели и тренироваться с большим объемом данных, чтобы компьютеры могли научиться различать содержимое изображений. Другой пример — созидание.Люди могут создавать то, чего не было у предшественников, а компьютеры — нет.Так называемое компьютерное сочинение и письмо — всего лишь результат комбинированного действия программ плюс каких-то случайно колеблющихся величин по фиксированному шаблону. Другой пример — мышление: люди могут думать о проблемах, с которыми они никогда раньше не сталкивались, а компьютеры, очевидно, не могут.
Например, картинка выше,Мы, люди, видим эти три категории с первого взгляда, но компьютеры не могут. Данные в компьютере дискретны, а компьютер не видит и не может видеть связь между данными. Итак, когда мы смотрим на простые задачи, это не так просто, но по сути, мы уже указали суть в анализе только что: раз компьютер не видит связи, то мы должны найти способ сделать это "видеть", сказать Это не должно быть достаточно точным, если быть точным.
Вспомните, как мы быстро определили, что на графике три категории? Вы бы сказали, что это очень просто, потому что три области имеют наибольшее количество очков. Это утверждение правильное, но оно недостаточно количественное, если его количественно определить, должно быть три области.максимальная плотность. Как только выражение определено количественно, становится ясно, что мы делаем кластеризацию по плотности. Kmeans основан на этой простой идее, но она слишком проста, и алгоритм расчета количества кластеров не разработан, поэтому количество категорий K должен быть предоставлен пользователем.
то естьАлгоритм не знает, сколько классов нужно сгруппировать в, мы говорим, что несколько категорий — это несколько категорий.
Мы игнорируем эту деталь.Предположим, мы знаем, что данные разделены на три категории каким-то странным способом, так как же Kmeans разделяет их?
Когда мы глубоко подумаем, мы обнаружим, что хотя мы и говорим, что хотимколичественная плотность, но плотность трудно определить количественно. Поскольку само определение плотности основано на результатах после кластеризации, мы уже должны знать, что такой пакет данных объединяется вместе для вычисления их плотности, а не наоборот. Так что эта идея надежна, но сделать это напрямую невозможно. Но если вы не можете сделать это напрямую, это не значит, что вы не можете сделать это в обратном порядке Эта идея очень распространена в математике, и здесь мы сталкиваемся с ней снова.
Так как мы не можем сделать кластеризацию по плотности, то мыМожно ли сначала провести кластеризацию, а затем вычислить плотность и настроить ее в соответствии с результатом плотности??
Я долго гуглил и не мог найти никакой информации об оригинальном авторе Kmeans, но я думаю, что тот, кто может придумать такую гениальную идею, должен быть очень остроумным. Kmeans происходит от такой простой и остроумной идеи.
инициализация
В начале работы алгоритма Kmeans будет находиться в диапазоне набора данныхПроизвольно выберите K центральных точек, а затем выполнить кластеризацию по K центральным точкам. На самом деле кластеризовать центральные точки очень просто, для каждого образца нужно только рассчитать расстояние между ним и всеми центрами и выбрать ближайший.
Конечно, полученный таким образом результат заведомо неточен, но это не беда, мы можем завершить кластеризацию даже по недостоверному центру.Наносим положение случайно полученной центральной точки и окончательный результат кластеризации на график , вы можете видеть, что хотя выбранная в начале позиция не кажется такой надежной, мы все же можем добиться хорошего результата.
Первоначальный результат кластеризацииопределенно не разрешено, но это не беда, мы не боимся неточностей, мы боимся, что результатов не будет. Это легко сделать с результатом, мы можем проанализировать результат, чтобы увидеть направление оптимизации. С направлением оптимизации результаты могут становиться все более и более точными, как и в линейной регрессии, мы не первые, кто получает лучшее значение выбора параметра, но и итерируем градиентный спуск по крупицам.
повторять
Прежде чем мы представим конкретный итерационный метод, давайте проанализируем ситуацию. Очевидно, что из-за отношения случайного выбора результат кластеризации заведомо неточный, причина неточности в том, что расстояние между случайно выбранным центром и кластером слишком велико. То есть мы должны найти способ приблизить центр к кластеру.
Итак, как мы можем приблизиться?Давайте сначала посмотрим на ситуацию после идеальной кластеризации.
Посмотрим, когда идеальная кластеризацияЦентральная точка и кластер перекрываются. Так какова природа этой центральной точки? Если вы знакомы с физикой, вы должны быть в состоянии думать, что эта центральная точка должна быть образцом этого класса.Центроид. Даже если вы не знакомы с этой концепцией, не беда, мы можем наблюдать на картинке выше, что точки выборки равномерно распределены вокруг центра. Какова характеристика равномерного рассеивания? Также легко думать, что количество и распределение точек, появляющихся слева и справа от центральной точки, сверху и снизу и в других направлениях, одинаковы. Давайте оценим это понятие количественно, мы можем получить категориюСреднее значение координат всех точек - это положение центральной точки.
Итак, вопрос в том, будет ли в случае ошибки кластеризации среднее значение координат выборки (т. е. центр тяжести) совпадать с выбранной нами центральной точкой? Какое будет отклонение, если оно не совпадает?
На самом деле мы можем догадаться из приведенного выше рисунка, что, поскольку выбранная нами центральная точка находится не в правильном положении, она не должна совпадать с центроидом выборки после кластеризации.Направление отклонения между ними является направлением его расстояния от центра масс.
Этот вывод тоже очень прост, потому что чем ближе к реальному скоплению, чем плотнее точки, то вычисляемый центроид заведомо будет ближе к направлению реального скопления. С этим выводом все очень просто: нам нужно только вычислить центроид каждого класса после каждой кластеризации, а затем повторно сгруппировать вычисленный центроид в качестве центральной точки следующей кластеризации и повторить описанный выше процесс. Когда центр до кластеризации и центроид после кластеризации перекрываются, это означает, что кластеризация сошлась, и мы нашли кластер.
На рисунке ниже показанЦентр категорий изменяется с итерациейВ случае , мы можем интуитивно видеть, что по мере итерации наш центр класса становится все ближе и ближе к реальному центру кластера, и после трех итераций он очень близок к конечному результату. Таким образом, этот вывод верен, и центроид можно использовать в качестве нового центра для итерации.
Код
После того, как принцип Kmeans и тяга Hou Gui ясны, реализовать их на Python становится очень просто.
Конечно, мы можем написать логику для генерации данных самостоятельно, но библиотека sklearn предоставляет нам API для создания данных, вызывая API, мы можем легко создавать нужные нам данные. Мы можем создавать кластеризованные данные, используя dataset.make_blobs. Передавая количество образцов и признаков, координаты реальных кластеров и стандартное отклонение образцов, можно получить партию соответствующих образцов.
def createData():
X, y = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[-1,-1],[1,1],[2,2]], cluster_std=[0.2,0.3,0.4])
return X, y
После создания данных мы можем приступить к реализации алгоритма.
Во-первых, мы сначала разрабатываем основной метод всего алгоритма, чтобы упростить последующую разработку. В задаче KMeans мы уже знаем, что корректируем категорию выборки по расстоянию между вектором и центром каждого кластера в пространстве выборки. Итак, сначала разрабатываем между векторамикак рассчитать расстояние.
Используя numpy, весь процесс расчета становится очень простым:
def calculateDistance(vecA, vecB):
return np.sqrt(np.sum(np.square(vecA - vecB)))
В этой строке кода мы сначала вычисляем разностный вектор двух векторов. Затем мы возводим в квадрат каждый член этого разностного вектора, а затем получаем квадратный корень из векторов A и B.Евклидово расстояние.
Далее нам понадобятся координаты центров случайных K кластеров. Хотя выбор кластеров в алгоритме KMeans случайный, следует отметить, что нашДиапазон случайности не бесконечен. Поскольку кластеризация предназначена для нахождения K позиций с наибольшей плотностью выборки, естественно, невозможно найти допустимые кластеры, в которых отсутствует распределение выборки. Таким образом, мы можем ограничить случайный диапазон диапазоном распределения выборки, что может значительно упростить расчет.
def randomCenter(samples, K):
m,n = np.shape(samples)
centers = np.mat(np.zeros((K, n)))
for i in range(n):
# 通过np.max获取i列最大值
mxi = np.max(samples[:, i])
# 通过np.min获取i列最小值
mni = np.min(samples[:, i])
rangeI = mxi - mni
# 为簇中心第i列赋值
centers[:, i] = np.mat(mni + rangeI * np.random.rand(K, 1))
return centers
Приведенную выше логику понять несложно: сначала мы создаем матрицу координат для K центров кластера и инициализируем ее значением 0, где n — количество измерений выборки. Затем мы проходим по этим n измерениям, чтобы найти максимальное и минимальное значения каждого измерения в выборке. С этими двумя значениями мы знаем диапазон значений центра кластера в каждом измерении выборки. Наконец, мы вызываем метод random.rand для случайного получения конкретных координат.
На данный момент разработаны два основных инструмента, необходимых для алгоритма. Затем, пока реализуется итеративный процесс, все KMeans завершается.
Прежде чем мы продолжим разработку, давайте протестируем два разработанных нами интерфейса.
Сначала сгенерируем данные:
Видим, что есть вывод данных, значит наши данные сгенерированы.Далее по сгенерированным данным случайным образом выбираются K центров кластеров.
Когда мы генерируем данные, передаются три центральные точки выборки, поэтому количество центров кластера равно 3, что означает, что наш K равен 3, затем мы вызываем метод randomCenter для просмотра результатов.
Конечно же, мы набрали 3 очка. Чтобы быть в безопасности, нам нужно вывести диапазон выборки и проверить, находятся ли координаты точек, которые мы генерируем, в пределах диапазона нашей выборки.
Используя методы max и min numpy в сочетании с операцией нарезки языка Python, мы можем очень удобно вычислить эти четыре значения. Очевидно, нашЦентры кластеров находятся в пределах досягаемости. С нашим кодом проблем нет.
После того, как эти два метода не станут проблемой, мы можем приступить к разработке базовой логики KMeans, то есть кластеризации.вычислительная логика.
Согласно приведенному ранее псевдокоду, мы начинаем со случайного извлечения центров кластеров. Затем каждый образец помечается классом в соответствии с центром кластера. Наконец, положение центра кластера обновляется по отмеченным образцам, вся логика на самом деле очень проста, и написать код несложно:
def KMeans(dataset, k):
m, n = np.shape(dataset)
# 最后的返回结果，一共两维，第一维是所属类别，第二维是到簇中心的距离
clusterPos = np.zeros((m, 2))
centers = randCenter(dataset, k)
clusterChange = True
while clusterChange:
clusterChange = False
# 遍历所有样本
for i in range(m):
minD = inf
idx = -1
# 遍历到各个簇中心的距离
for j in range(k):
dis = calculateDistance(centers[j,:], dataset[i, :])
if dis < minD:
minD = dis
idx = j
# 如果所属类别发生变化
if clusterPos[i,0] != idx:
clusterChange = True
# 更新样本聚类结果
clusterPos[i,:] = idx, minD
# 更新簇中心的坐标
for i in range(k):
nxtClust = dataset[np.nonzero(clusterPos[:,0] == i)[0]]
centers[i,:] = np.mean(nxtClust, axis=0)
return centers, clusterPos
Затем давайте проверим наш код, чтобы увидеть, можем ли мы сгруппировать правильные результаты.
centers, clusterRet = KMeans(x, 3)
plt.scatter(x[:,0],x[:,1],c=clusterRet[:,0] ,s=3,marker='o')
plt.scatter(centers[:, 0].A, centers[:, 1].A, c='red', s=100, marker='x')
plt.show()
Рисуем все точки в выборке по результатам после кластеризации, а затем отмечаем положение центра кластера на том же графике.Результаты следующие.
Нетрудно заметить, что на приведенном выше рисунке, будь то положение центра кластера или окончательный результат кластеризации, в основномТо же, что и наша ручная оценка. Это показывает, что написанный нами алгоритм KMeans работает успешно и выводит правильный результат.
Суммировать
На этом этапе были представлены принцип и код алгоритма Kmeans. Я не знаю, как вы себя чувствуете. Когда я впервые изучил этот алгоритм, самым большим чувством было то, чтоПростой,этот алгоритм слишком "детская игра",и в нем легко разобраться.Никаких хитросплетений и сложностей.Все проблемы и идеи прямые.
Алгоритм прост, и нам легко научиться, но часто слишком простые алгоритмы оставляют недостатки. Недостатки Kmeans тоже очевидны, и я думаю, все это чувствуют. Каждый раз, когда мы повторяем, нам нужновсе образцыРассчитайте категорию, к которой он относится, это полный расчет. Так как наша начальная центральная точка выбирается случайным образом, это также приводит к тому, что положение центра в начале может быть далеко от конечного кластера,Очевидно, что чем больше расстояние, тем больше итераций требуется., то вычислительные затраты, естественно, будут больше.
Итак, есть ли способ повысить эффективность kmeans?
Вы можете сначала подумать об этом, и я обсужу это с вами в теме машинного обучения на следующей неделе.
Точно так же, поскольку алгоритм Kmeans прост в принципе и легко реализуем, он часто используется в крупных компаниях.Письменные тестовые вопросы по набору персоналасреди. Насколько я знаю, письменные тестовые вопросы Alibaba в течение нескольких лет просят игроков написать от руки кластер kmeans. Поэтому, хотя этот алгоритм прост, мы не можем относиться к нему легкомысленно. Кроме того, алгоритм не может довольствоваться пониманием принципа, можно больше все обдумать и задать больше вопросов, чтобы понимание было более глубоким, а собеседование в дальнейшем более гибким.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.