Косинусное расстояние как векторная функция расстояния для k-средних

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

например. для графика:

вектор:

v1 = {100, 50, 0 30, 0}

означает, что мы потратили:

100secs at vertex 1
50secs at vertex 2 and 
30secs at vertex 4

(вершины 3 и 5, где не были посещены, таким образом, 0s).

Я хочу запустить k-мерную кластеризацию, и я выбрал cosine_distance = 1 - cosine_similarity как метрику для расстояний, где формула для cosine_similarity:

как описано здесь.

Но я заметил следующее. Предположим, что k=2 и один из векторов:

v1 = {90,0,0,0,0}

В процессе решения задачи оптимизации минимизации общего расстояния от кандидатов-центроидов предположим, что в какой-то момент 2 кандидата-центроиды:

c1 = {90,90,90,90,90}
c2 = {1000, 1000, 1000, 1000, 1000}

Запуск формулы cosine_distance для (v1, c1) и (v1, c2) мы получаем точно такое же расстояние 0.5527864045 для обоих.

Я бы предположил, что v1 больше похож (ближе) на c1, чем на c2. По-видимому, это не так.

Q1. Почему это предположение неверно?

Q2. Является ли расстояние косинуса правильной функцией расстояния для этого случая?

Q3. Что было бы лучше, учитывая характер проблемы?

Ответ 1

Позвольте разделить косинус-сходство на части и посмотреть, как и почему оно работает.

Косинус между двумя векторами - a и b - определяется как:

cos(a, b) = sum(a .* b) / (length(a) * length(b))

где .* - умножение по элементам. Знаменатель здесь только для нормализации, поэтому просто назовите его L. С его помощью наши функции превращаются в:

cos(a, b) = sum(a .* b) / L

который, в свою очередь, может быть переписан как:

cos(a, b) = (a[1]*b[1] + a[2]*b[2] + ... + a[k]*b[k]) / L = 
          = a[1]*b[1]/L + a[2]*b[2]/L + ... + a[k]*b[k]/L

Позвольте получить более абстрактную информацию и заменить x * y / L на функцию g(x, y) (L здесь постоянна, поэтому мы не ставим ее как аргумент функции). Таким образом, наша косинусная функция становится:

cos(a, b) = g(a[1], b[1]) + g(a[2], b[2]) + ... + g(a[n], b[n])

То есть каждая пара элементов (a[i], b[i]) обрабатывается отдельно, а результат - просто сумма всех обработок. И это хорошо для вашего случая, потому что вы не хотите, чтобы разные пары (разные вершины) были беспорядочны друг с другом: если пользователь1 посещал только vertex2 и user2 - только vertex1, то у них нет ничего общего, и сходство между ними должно быть нуль. То, что вам на самом деле не нравится, - это то, как рассчитывается сходство между отдельными парами, т.е. Функция g().

С косинусной функцией сходство между отдельными парами выглядит следующим образом:

g(x, y) = x * y / L

где x и y представляют время, затраченное пользователями на вершину. И вот главный вопрос: умножение означает сходство между отдельными парами хорошо? Я так не думаю. Пользователь, который потратил 90 секунд на какую-то вершину, должен быть близок к пользователю, который провел там, скажем, 70 или 110 секунд, но гораздо более далеким от пользователей, которые тратят там 1000 или 0 секунд. Умножение (даже нормализованное на L) совершенно вводит в заблуждение. Что это означает даже умножить 2 периода времени?

Хорошая новость заключается в том, что именно вы создаете функцию сходства. Мы уже решили, что нас удовлетворяет независимое обращение с парами (вершинами), и мы хотим только, чтобы функция индивидуального подобия g(x, y) делала что-то разумное с ее аргументами. И что разумная функция для сравнения периодов времени? Я бы сказал, что вычитание является хорошим кандидатом:

g(x, y) = abs(x - y)

Это не функция подобия, но вместо этого функция расстояния - чем ближе значения друг к другу, тем меньше результат g(), но в конечном итоге идея одинакована, поэтому мы можем их менять, когда нам нужно.

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

g(x, y) = (x - y)^2

Эй! Мы только что заново изобрели (средняя) квадратная ошибка! Теперь мы можем придерживаться MSE для вычисления расстояния, или мы можем продолжить поиск хорошей функции g().

Иногда мы можем не увеличивать, а вместо этого разглаживать разницу. В этом случае мы можем использовать log:

g(x, y) = log(abs(x - y))

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

g(x, y) = sign(x)*sign(y)*abs(x - y)   # sign(0) will turn whole expression to 0

Или мы можем вернуться от расстояния к подобию, инвертируя разницу:

g(x, y) = 1 / abs(x - y)

Обратите внимание, что в последних параметрах мы не использовали коэффициент нормировки. Фактически, вы можете придумать хорошую нормализацию для каждого случая или просто опустить это - нормализация не всегда необходима или хороша. Например, в формуле подобия косинуса, если вы измените константу нормализации L=length(a) * length(b) на L=1, вы получите разные, но все же разумные результаты. Например.

cos([90, 90, 90]) == cos(1000, 1000, 1000)  # measuring angle only
cos_no_norm([90, 90, 90]) < cos_no_norm([1000, 1000, 1000])  # measuring both - angle and magnitude

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

Ответ 2

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

Расстояние косинуса тесно связано с квадратичным евклидовым расстоянием (единственным расстоянием, для которого действительно определено k-средство); поэтому работает сферическое k-средство.

Связь довольно проста:

Квадратичное евклидово расстояние sum_i (x_i-y_i)^2 может быть учтено в sum_i x_i^2 + sum_i y_i^2 - 2 * sum_i x_i*y_i. Если оба вектора нормализованы, т.е. Длина не имеет значения, то первые два члена равны 1. В этом случае квадратичное евклидово расстояние 2 - 2 * cos(x,y)!

Другими словами: Расстояние косинуса равно квадрату Евклидова расстояние с данными, нормированными на единицу длины.

Если вы не хотите нормализовать свои данные, не используйте косинус.

Ответ 3

Q1. Why is this assumption wrong?

Как видно из определения, подобие косинуса измеряет угол между двумя векторами.

В вашем случае вектор v1 лежит на первом измерении, а c1 и c2 оба одинаково выровнены по осям, и, следовательно, подобие косинуса должно быть одинаковым.

Обратите внимание, что проблема заключается в том, что c1 и c2 указывают в одном направлении. Любой v1 будет иметь одинаковое сходство с косинусом с обоими из них. Для иллюстрации:

Q2. Is the cosine distance a correct distance function for this case?

Как видно из приведенного примера, возможно, нет.

Q3. What would be a better one given the nature of the problem?

Рассмотрим Euclidean Distance.