K-Means (К-средние), GMM (Модель смеси Гаусса), легко понять, сначала соберите!

1. Все ли алгоритмы кластеризации являются неконтролируемым обучением?

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

Обычно используемые алгоритмы включаютK-MEANS, смешанная модель Гаусса (GMM), самоорганизующаяся карта (SOM)

2. алгоритм k-средних (k-means)

2.1 Алгоритм процесса

K-means — самый популярный алгоритм кластеризации, алгоритм берет неразмеченный набор данных, а затем кластеризует данные в разные группы.

K-means — это итеративный алгоритм, предположим, что мы хотим сгруппировать данные в n групп следующим образом:

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

использовать u^1,u^2,...,u^k Чтобы представить центр кластера, используйте ?(1),?(2),...,?(?) для хранения индекса центра кластера, ближайшего к данным экземпляра ?. Псевдокод алгоритма K-средних выглядит следующим образом следует:

Repeat {
    for i = 1 to m
    c(i) := index (form 1 to K) of cluster centroid closest to x(i)
    for k = 1 to K
    μk := average (mean) of points assigned to cluster k
}

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

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

2.2 Функция потерь

Задача минимизации K-средних состоит в том, чтобы минимизировать сумму расстояний между всеми точками данных и связанными с ними центральными точками кластера, поэтому функция стоимости K-средних (также известная как функция искажения Функция искажения) имеет вид:

J(c^{(1)},c^{(2)},...,c^{(m)},u_1,...,u_k)=\frac{1}{m}\sum_{i=1}^{m}||X^{(1)}-u_{c^{(i)}}||^2

в $u_{c^{(i)}}$ представлять и $x^{(i)}$ Ближайшая точка центра кластера. Наша цель оптимизации состоит в том, чтобы найти тот, который минимизирует функцию стоимости $c^{(1)},c^{(2)},...,c^{(m)}$ и u_1,u_2,...,u_k .

2.3 Выбор значения k

Перед запуском алгоритма K-средних мы сначала случайным образом инициализируем все центральные точки кластера Вот как это сделать:

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

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

Не существует так называемого наилучшего метода выбора количества кластеров, который обычно приходится подбирать вручную по разным задачам. При выборе подумайте о нашей мотивации использования кластеризации K-средних. Существует метод, о котором можно было бы рассказать, который называется **«правило локтя»**. Что касается «правила локтя», все, что нам нужно сделать, это изменить значение ?, которое представляет собой общее количество кластеров. Мы запускаем метод кластеризации K-средних с одним кластером. Это означает, что все данные будут разделены на кластер, а затем будет рассчитана функция стоимости или функция искажения ?. ? представляет номер кластера.

Мы могли бы получить кривую, подобную этой. как локоть человека. Это то, что делает «правило локтя», давайте посмотрим на график, который выглядит так, как будто там есть явный локоть. Вы найдете этот шаблон, где значение искажения быстро падает с 1 до 2, а после 2 до 3 вы ударяетесь локтем на 3. После этого значение искажения падает очень медленно, кажется правильным использовать 3 кластера для кластеризации, ** это потому, что эта точка является изгибом кривой, значение искажения падает очень быстро, ? После = 3, снижение очень медленное, то мы выбираем ? = 3. ** Когда вы применяете «правило локтя», если вы получаете график, подобный приведенному выше, то это будет разумным способом выбора количества кластеров.

2.4 В чем разница между KNN и K-средними?

Алгоритм классификации K-ближайших соседей (KNN) является теоретически зрелым методом и одним из самых простых алгоритмов машинного обучения.

KNN	K-Means
1. KNN — это алгоритм классификации 2. Это относится к обучению с учителем 3. Набор обучающих данных — это данные с метками	1. K-Means — это алгоритм кластеризации 2. Это относится к неконтролируемому обучению 3. Набор обучающих данных представляет собой неразмеченные данные, которые дезорганизованы, после кластеризации они становятся упорядоченными, сначала неупорядоченными, затем упорядоченными.
Нет очевидного предтренировочного процесса, который относится к обучению на основе памяти.	Есть четкий предтренировочный процесс
Значение K: образец x, чтобы классифицировать его, из набора обучающих данных найдите K ближайших к нему точек данных рядом с x, эти K точек данных, категория c составляет наибольшее число, возьмите значение метки x установлено значение c.	Значение K: K — искусственно фиксированное число.Предполагая, что набор данных можно разделить на кластеры K, обучающие данные используются для обучения категорий K.

Сходство

Оба включают в себя процесс поиска точки, ближайшей к ней в наборе данных. То есть оба используют идею алгоритма NN (Nears Neighbor).

2.5 Преимущества, недостатки и улучшения K-средних

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

Уменьшить количество кластеров K. Потому что каждый образец должен рассчитывать расстояние от центра класса.
Уменьшите размер элемента выборки. Например, уменьшение размерности через PCA и т.д.
Исследуйте другие алгоритмы кластеризации и проверьте производительность различных алгоритмов кластеризации, выбирая игрушечные данные.
Кластер Hadoop, алгоритм K-средних легко выполнять параллельные вычисления.
Алгоритм может найти локально оптимальные кластеры вместо глобально оптимальных кластеров. Используйте улучшенный алгоритм k-средних пополам.

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

3. Модель гауссовой смеси (GMM)

3.1 Идея GMM

Смешанная модель Гаусса (GMM) также является распространенным алгоритмом кластеризации, похожим на алгоритм K-средних, и также использует алгоритм EM для итеративных вычислений. Модель смеси Гаусса предполагает, что данные каждого кластера соответствуют распределению Гаусса (также называемому нормальным распределением).Распределение, представленное данными, представляет собой суперпозицию гауссовых распределений отдельных кластеров.

Первое изображение является примером распределения данных.Если для подбора данных на рисунке используется только одно распределение Гаусса, эллипс, показанный на рисунке, представляет собой эллипс, соответствующий удвоенному стандартному отклонению распределения Гаусса. Интуитивно данные на рисунке, очевидно, разделены на два кластера, поэтому нецелесообразно использовать только одно распределение Гаусса для подбора, и его необходимо расширить до суперпозиции нескольких распределений Гаусса для подбора данных. Второй график является результатом подгонки суперпозиции двух распределений Гаусса. ** Это приводит к смешанной модели Гаусса, в которой используется линейная комбинация нескольких функций распределения Гаусса для соответствия распределению данных. ** Теоретически смешанная модель Гаусса может соответствовать любому типу распределения.

Основная идея смешанных моделей Гаусса состоит в том, чтобы предположить, что данные можно рассматривать как полученные из нескольких распределений Гаусса. При этом предположении каждая отдельная подмодель является стандартной гауссовой моделью, среднее значение которой u_i и дисперсия $\sum_i$ – оцениваемый параметр. Кроме того, каждая подмодель имеет параметр $\pi_i$ , что можно понимать как вес или вероятность генерации данных. Формула для модели гауссовой смеси:

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

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

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

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

Модель смеси Гаусса является генеративной моделью. Процесс генерации данных можно понять таким образом, предполагая простейший случай, то есть есть только две подмодели одномерного стандартного распределения Гаусса.N(0,1) иN(5,1) с весами 0,7 и 0,3 соответственно. Затем при создании первой точки данных сначала случайным образом выберите распределение в соответствии с долей веса, например, выбрав первое распределение Гаусса, а затем изNТочка, сгенерированная в (0,1), например -0,5, является первой точкой данных. При создании второй точки данных случайным образом выберите второе распределение Гаусса.N(5,1) формируется вторая точка 4.7. В этом цикле генерируются все точки данных.

То есть мы не знаем соответствующих 3 параметров лучших K распределений Гаусса, а также мы не знаем, из какого распределения Гаусса генерируется каждая точка данных. Следовательно, в каждом цикле сначала фиксируется текущее распределение Гаусса, и получается вероятность того, что каждая точка данных генерируется каждым распределением Гаусса. Затем зафиксируйте вероятность генерации без изменений и получите лучшее распределение Гаусса в соответствии с точками данных и вероятностью генерации. Цикл повторяется до тех пор, пока параметры не перестанут изменяться или изменение будет очень небольшим, и не будет получен более разумный набор распределений Гаусса.

3.2 GMM по сравнению с K-средними

Модель смеси Гаусса имеет те же точки, что и алгоритм K-средних:

Это все алгоритмы, которые можно использовать для кластеризации;
Оба должны указать значение K;
Все решаются с помощью алгоритма EM;
часто сходятся только к локальному оптимуму.

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

4. Как оцениваются алгоритмы кластеризации

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

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

Оцените тенденции кластеризации.

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

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

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

Коэффициент силуэта, среднеквадратичное стандартное отклонение, R-квадрат, модифицированная статистика Хьюберта Γ.

5. Реализация кода

Код модели смеси Гаусса

K-средний код

【Машинное обучение легко понять серия статей】

автор:@mantchs

Гитхаб:GitHub.com/NLP-love/ml…

Приглашаются все желающие присоединиться к обсуждению! Улучшайте этот проект вместе! Номер группы: [541954936]