Разница между стандартным и сферическим алгоритмами k-средних

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

На каждом шаге k-means вычисляет расстояния между векторами элементов и центроидами кластера и переназначает документ этому кластеру, центроид которого является ближайшим. Затем все центроиды пересчитываются.

В сферических k-средних все векторы нормированы, а мера расстояния - косинусное различие.

Это все или есть что-то еще?

Вопрос в том:

В чем разница между классическим k-средним и сферическим k-средним?

Классический K-означает:

В классических k-средних мы стремимся минимизировать евклидово расстояние между центром кластера и членами кластера. Интуиция за этим заключается в том, что радиальное расстояние от центра кластера до местоположения элемента должно быть «одинаковым» или «быть одинаковым» для всех элементов этого кластера.

Алгоритм:

• Установить количество кластеров (иначе количество кластеров)
• Инициализация путем случайного присвоения точек в пространстве индексам кластера
• Повторите, пока не сходятся
  • Для каждой точки найдите ближайший кластер и назначьте точку кластеру
  • Для каждого кластера найдите среднее число членов и среднее значение центра обновлений.
  • Ошибка - норма расстояния кластеров

Сферическое К-средство:

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

Более техническая версия:

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

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

Если мы переместим все данные так, чтобы их хвост находился в одной и той же точке, мы можем сравнить «векторы» по их углу и сгруппировать похожие в один кластер.

Для ясности длины векторов масштабируются, чтобы их было легче сравнивать.

Вы можете думать об этом как о созвездии. Звезды в одном скоплении в некотором смысле близки друг к другу. Это мои глазные яблоки считаются созвездиями.

Ценность общего подхода заключается в том, что он позволяет нам создавать векторы, которые в противном случае не имеют геометрической размерности, например, в методе tf-idf, где векторы представляют собой частоты слов в документах. Два добавленных слова "и" не равны "the". Слова не являются непрерывными и не числовыми. Они являются нефизическими в геометрическом смысле, но мы можем придумать их геометрически, а затем использовать геометрические методы для их обработки. Сферические k-средства могут быть использованы для кластеризации на основе слов.

$$\begin{bmatrix} x1&y1&x2&y2&group\\ 0&-0.8&-0.2013&-0.7316&B\\ -0.8&0.1&-0.9524&0.3639&A\\ 0.2&0.3&0.2061&-0.1434&C\\ 0.8&0.1&0.4787&0.153&B\\ -0.7&0.2&-0.7276&0.3825&A\\ 0.9&0.9&0.748&0.6793&C\\ \end{bmatrix}$$

Некоторые моменты:

• Они проецируются в единичную сферу для учета различий в длине документа.

Давайте проработаем реальный процесс и посмотрим, насколько (плохо) было мое «зрелище».

Процедура такова:

1. (подразумевается в задаче) соединить векторы хвосты в начале координат
2. проект на единичную сферу (для учета различий в длине документа)
3. использовать кластеризацию, чтобы минимизировать " косинусное различие" »

$$J = \sum_{i} d \left( x_{i},p_{c\left( i \right)} \right)$$
$$d \left( x,p \right) = 1- cos \left(x,p\right) = \frac{\langle x,p \rangle}{\left \|x \right \|\left \|p \right \|}$$

(скоро появятся новые правки)

Ссылки:

1. http://epub.wu.ac.at/4000/1/paper.pdf
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8125&rep=rep1&type=pdf
3. http://www.cs.gsu.edu/~wkim/index_files/papers/refinehd.pdf
4. https://www.jstatsoft.org/article/view/v050i10
5. http://www.mathworks.com/matlabcentral/fileexchange/32987-the-spherical-k-means-algorithm
6. https://ocw.mit.edu/courses/sloan-school-of-management/15-097-prediction-machine-learning-and-statistics-spring-2012/projects/MIT15_097S12_proj1.pdf