Косинусное подобие

Мера сходства числовых последовательностей

В анализе данных косинусное сходство — это мера сходства между двумя ненулевыми векторами, определенными в пространстве внутреннего произведения . Косинусное сходство — это косинус угла между векторами; то есть это скалярное произведение векторов, деленное на произведение их длин. Отсюда следует, что косинусное сходство не зависит от величин векторов, а только от их угла. Косинусное сходство всегда принадлежит интервалу Например, два пропорциональных вектора имеют косинусное сходство 1, два ортогональных вектора имеют сходство 0, а два противоположных вектора имеют сходство -1. В некоторых контекстах значения компонентов векторов не могут быть отрицательными, и в этом случае косинусное сходство ограничено в . ${\displaystyle [-1,1].}$ ${\displaystyle [0,1]}$

Например, в информационном поиске и анализе текста каждому слову назначается отдельная координата, а документ представляется вектором числа появлений каждого слова в документе. Косинусное сходство затем дает полезную меру того, насколько похожими могут быть два документа с точки зрения их предмета и независимо от длины документов. ^[1]

Этот метод также используется для измерения сплоченности внутри кластеров в области интеллектуального анализа данных . ^[2]

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

Другие названия косинусного подобия включают подобие Орчини и коэффициент конгруэнтности Таккера ; подобие Оцуки–Очиаи (см. ниже) — это косинусное подобие, примененное к двоичным данным .

Определение

Косинус двух ненулевых векторов можно вывести, используя формулу скалярного произведения Евклида :

${\displaystyle \mathbf {A} \cdot \mathbf {B} =\left\|\mathbf {A} \right\|\left\|\mathbf {B} \right\|\cos \theta }$

Для двух n -мерных векторов атрибутов, A и B , косинусное сходство, cos(θ) , представляется с помощью скалярного произведения и величины как

${\displaystyle {\text{cosine similarity}}=S_{C}(A,B):=\cos(\theta )={\mathbf {A} \cdot \mathbf {B} \over \|\mathbf {A} \|\|\mathbf {B} \|}={\frac {\sum \limits _{i=1}^{n}{A_{i}B_{i}}}{{\sqrt {\sum \limits _{i=1}^{n}{A_{i}^{2}}}}\cdot {\sqrt {\sum \limits _{i=1}^{n}{B_{i}^{2}}}}}},}$

где и - -ые компоненты векторов и соответственно. ${\displaystyle A_{i}}$ ${\displaystyle B_{i}}$ ${\displaystyle i}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {B} }$

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

Для сопоставления текста векторы атрибутов A и B обычно являются векторами частот терминов документов. Косинусное сходство можно рассматривать как метод нормализации длины документа при сравнении. В случае поиска информации косинусное сходство двух документов будет варьироваться от , поскольку частоты терминов не могут быть отрицательными. Это остается верным при использовании весов TF-IDF . Угол между двумя векторами частот терминов не может быть больше 90°. ${\displaystyle 0\to 1}$

Если векторы атрибутов нормализуются путем вычитания векторных средних (например, ), мера называется центрированным косинусным сходством и эквивалентна коэффициенту корреляции Пирсона . Для примера центрирования, ${\displaystyle A-{\bar {A}}}$

${\displaystyle {\text{if}}\,A=[A_{1},A_{2}]^{T},{\text{ then }}{\bar {A}}=\left[{\frac {(A_{1}+A_{2})}{2}},{\frac {(A_{1}+A_{2})}{2}}\right]^{T},}$

${\displaystyle {\text{ so }}A-{\bar {A}}=\left[{\frac {(A_{1}-A_{2})}{2}},{\frac {(-A_{1}+A_{2})}{2}}\right]^{T}.}$

Косинусное расстояние

Если расстояние между двумя векторами единичной длины определяется как длина их векторной разности, то $${\displaystyle \operatorname {dist} (\mathbf {A} ,\mathbf {B} )={\sqrt {(\mathbf {A} -\mathbf {B} )\cdot (\mathbf {A} -\mathbf {B} )}}={\sqrt {\mathbf {A} \cdot \mathbf {A} -2(\mathbf {A} \cdot \mathbf {B} )+\mathbf {B} \cdot \mathbf {B} }}={\sqrt {2(1-S_{C}(\mathbf {A} ,\mathbf {B} ))}}\,.}$$

Тем не менее, косинусное расстояние ^[3] часто определяется без квадратного корня или множителя 2:

${\displaystyle {\text{cosine distance}}=D_{C}(A,B):=1-S_{C}(A,B)\,.}$

Важно отметить, что в силу пропорциональности квадрату евклидова расстояния косинусное расстояние не является истинной метрикой расстояния ; оно не демонстрирует свойство неравенства треугольника — или, более формально, неравенство Шварца — и нарушает аксиому совпадения. Чтобы исправить свойство неравенства треугольника, сохранив тот же порядок, можно преобразовать в евклидово расстояние или угловое расстояние θ = arccos( SC ( A , B )) . В качестве альтернативы, треугольное неравенство, которое работает для угловых расстояний _, можно выразить непосредственно через косинусы; см. ниже. ${\textstyle {\sqrt {2(1-S_{C}(A,B))}}}$

Угловое расстояние и подобие

Нормализованный угол, называемый угловым расстоянием , между любыми двумя векторами , является формальной метрикой расстояния и может быть вычислен из косинусного подобия. ^[4] Затем дополнение метрики углового расстояния может быть использовано для определения функции углового подобия, ограниченной между 0 и 1 включительно. ${\displaystyle A}$ ${\displaystyle B}$

Когда элементы вектора могут быть положительными или отрицательными:

${\displaystyle {\text{angular distance}}=D_{\theta }:={\frac {\arccos({\text{cosine similarity}})}{\pi }}={\frac {\theta }{\pi }}}$

${\displaystyle {\text{angular similarity}}=S_{\theta }:=1-{\text{angular distance}}=1-{\frac {\theta }{\pi }}}$

Или, если элементы вектора всегда положительны:

${\displaystyle {\text{angular distance}}=D_{\theta }:={\frac {2\cdot \arccos({\text{cosine similarity}})}{\pi }}={\frac {2\theta }{\pi }}}$

${\displaystyle {\text{angular similarity}}=S_{\theta }:=1-{\text{angular distance}}=1-{\frac {2\theta }{\pi }}}$

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

Л2-нормализованное евклидово расстояние

Другой эффективный прокси для косинусного расстояния может быть получен путем нормализации векторов с последующим применением нормального евклидова расстояния . Используя эту технику, каждый член в каждом векторе сначала делится на величину вектора, что дает вектор единичной длины. Тогда евклидово расстояние по конечным точкам любых двух векторов является надлежащей метрикой, которая дает тот же порядок, что и косинусное расстояние ( монотонное преобразование евклидова расстояния; см. ниже) для любого сравнения векторов, и, кроме того, позволяет избежать потенциально дорогостоящих тригонометрических операций, необходимых для получения надлежащей метрики. После того, как нормализация произошла, векторное пространство можно использовать со всем спектром методов, доступных для любого евклидова пространства, в частности, со стандартными методами снижения размерности . Это нормализованное расстояние формы часто используется во многих алгоритмах глубокого обучения . ${\displaystyle L_{2}}$

Коэффициент Оцуки–Очиаи

В биологии существует аналогичная концепция, известная как коэффициент Оцука-Очиай, названная в честь Яносукэ Оцука (также пишется как Оцука, Оцука или Отука, ^[5] японский :大塚 弥之助) ^[6] и Акира Отиай ( японский :落合 明), ^[7] также известный как коэффициент Очиаи–Баркмана ^[8] или коэффициент Очиаи, ^[9] который можно представить как:

${\displaystyle K={\frac {|A\cap B|}{\sqrt {|A|\times |B|}}}}$

Здесь и — множества , а — число элементов в . Если множества представлены в виде битовых векторов, то коэффициент Оцуки–Очиаи можно считать таким же, как и косинусное сходство. Он идентичен оценке, введенной Годфри Томсоном . ^[10] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |A|}$ ${\displaystyle A}$

В недавней книге ^[11] коэффициент предварительно ошибочно приписывается другому японскому исследователю с фамилией Оцука. Путаница возникает из-за того, что в 1957 году Акира Очиаи приписывает коэффициент только Оцуке (имя не упоминается) ^[7], цитируя статью Икусо Хамаи ( яп. :浜井 生三), ^[12] который в свою очередь цитирует оригинальную статью 1936 года Яносукэ Оцуки. ^[6]

Характеристики

Наиболее примечательным свойством косинусного сходства является то, что оно отражает относительное, а не абсолютное, сравнение отдельных векторных измерений. Для любой положительной константы и вектора векторы и максимально похожи. Таким образом, эта мера наиболее подходит для данных, где частота важнее абсолютных значений; в частности, частота терминов в документах. Однако более поздние метрики, основанные на теории информации, такие как Дженсена–Шеннона , SED и треугольная дивергенция, как было показано, улучшили семантику, по крайней мере, в некоторых контекстах. ^[13] ${\displaystyle a}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle aV}$

Косинусное подобие связано с евклидовым расстоянием следующим образом. Обозначим евклидово расстояние как обычно , и заметим, что ${\displaystyle \|A-B\|}$

${\displaystyle \|A-B\|^{2}=(A-B)\cdot (A-B)=\|A\|^{2}+\|B\|^{2}-2(A\cdot B)\ }$( поляризационная идентичность )

путем расширения . Когда A и B нормализованы к единичной длине, то это выражение равно ${\displaystyle \|A\|^{2}=\|B\|^{2}=1}$

${\displaystyle 2(1-\cos(A,B)).}$

Короче говоря, косинусное расстояние можно выразить через евклидово расстояние как

${\displaystyle D_{C}(A,B)={\frac {\|A-B\|^{2}}{2}}\quad \mathrm {when} \quad \|A\|^{2}=\|B\|^{2}=1}$.

Евклидово расстояние называется хордовым расстоянием (потому что это длина хорды на единичной окружности) и представляет собой евклидово расстояние между векторами, которые были нормализованы к единичной сумме квадратов значений внутри них.

Нулевое распределение: Для данных, которые могут быть как отрицательными, так и положительными, нулевое распределение для косинусного подобия является распределением скалярного произведения двух независимых случайных единичных векторов . Это распределение имеет среднее значение , равное нулю, и дисперсию ( где — число измерений), и хотя распределение ограничено диапазоном от -1 до +1, по мере увеличения распределение все лучше аппроксимируется нормальным распределением . [ ^{14] [15]} Для других типов данных, таких как потоки битов , которые принимают только значения 0 или 1, нулевое распределение принимает другую форму и может иметь ненулевое среднее значение. ^[16] ${\displaystyle 1/n}$ ${\displaystyle n}$ ${\displaystyle n}$

Неравенство треугольника для косинусного подобия

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

${\displaystyle |~\angle {AC}-\angle {CB}~|\leq ~\angle {AB}~\leq ~\angle {AC}~+~\angle {CB}~.}$

Поскольку функция косинуса уменьшается с увеличением угла в [0, π ] радиан, смысл этих неравенств меняется на противоположный, когда мы берем косинус каждого значения:

${\displaystyle \cos(\angle {AC}-\angle {CB})\geq \cos(\angle {AB})\geq \cos(\angle {AC}+\angle {CB}).}$

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

${\displaystyle \cos(A,C)\cdot \cos(C,B)+{\sqrt {\left(1-\cos(A,C)^{2}\right)\cdot \left(1-\cos(C,B)^{2}\right)}}\geq \cos(A,B),}$

${\displaystyle \cos(A,B)\geq \cos(A,C)\cdot \cos(C,B)-{\sqrt {\left(1-\cos(A,C)^{2}\right)\cdot \left(1-\cos(C,B)^{2}\right)}}.}$

Эту форму неравенства треугольника можно использовать для ограничения минимального и максимального сходства двух объектов A и B, если сходство с эталонным объектом C уже известно. Это используется, например, в индексации метрических данных, но также использовалось для ускорения сферической кластеризации k-средних ^[17] таким же образом, как неравенство евклидова треугольника использовалось для ускорения обычных k-средних.

Мягкая косинусная мера

Мягкий косинус или («мягкое» сходство) между двумя векторами учитывает сходство между парами признаков. ^[18] Традиционное косинусное сходство рассматривает признаки модели векторного пространства (VSM) как независимые или совершенно разные, в то время как мягкая косинусная мера предлагает учитывать сходство признаков в VSM, что помогает обобщить концепцию косинуса (и мягкого косинуса), а также идею (мягкого) сходства.

Например, в области обработки естественного языка (NLP) сходство между признаками вполне интуитивно понятно. Такие признаки, как слова, n -граммы или синтаксические n -граммы ^[19], могут быть весьма похожи, хотя формально они считаются разными признаками в VSM. Например, слова «play» и «game» являются разными словами и, таким образом, отображаются в разные точки в VSM; тем не менее, они семантически связаны. В случае n -грамм или синтаксических n -грамм можно применить расстояние Левенштейна (фактически, расстояние Левенштейна можно применить и к словам).

Для вычисления мягкого косинуса матрица s используется для указания сходства между признаками. Она может быть рассчитана через расстояние Левенштейна, сходство WordNet или другие меры сходства . Затем мы просто умножаем на эту матрицу.

Для двух векторов размерности N и мягкое косинусное сходство вычисляется следующим образом: ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle {\begin{aligned}\operatorname {soft\_cosine} _{1}(a,b)={\frac {\sum \nolimits _{i,j}^{N}s_{ij}a_{i}b_{j}}{{\sqrt {\sum \nolimits _{i,j}^{N}s_{ij}a_{i}a_{j}}}{\sqrt {\sum \nolimits _{i,j}^{N}s_{ij}b_{i}b_{j}}}}},\end{aligned}}}$

где s _ij = сходство (признак _i , признак _j ) .

Если между признаками нет сходства ( s _ii = 1 , s _ij = 0 для i ≠ j ), данное уравнение эквивалентно обычной формуле косинусного сходства.

Временная сложность этой меры квадратична, что делает ее применимой к реальным задачам. Обратите внимание, что сложность может быть снижена до субквадратичной. ^[20] Эффективная реализация такого мягкого косинусного подобия включена в библиотеку Gensim с открытым исходным кодом.

Смотрите также

• Коэффициент Сёренсена-Дайса
• Расстояние Хэмминга
• Корреляция
• индекс Жаккара
• SimRank
• Поиск информации

Ссылки

1. Сингхал, Амит (2001). «Современный информационный поиск: краткий обзор». Бюллетень Технического комитета по инжинирингу данных IEEE Computer Society 24 (4): 35–43.
2. П.-Н. Тан, М. Штайнбах и В. Кумар, Введение в интеллектуальный анализ данных , Addison-Wesley (2005), ISBN  0-321-32136-7 , глава 8; страница 500.
3. Wolfram Research (2007). «CosineDistance – Центр документации по языку и системам Wolfram». wolfram.com .{{cite web}}: CS1 maint: numeric names: authors list (link)
4. "КОСИНУСНОЕ РАССТОЯНИЕ, КОСИНУСНОЕ ПОДОБИЕ, УГЛОВОЕ КОСИНУСНОЕ РАССТОЯНИЕ, УГЛОВОЕ КОСИНУСНОЕ ПОДОБИЕ". www.itl.nist.gov . Получено 11 июля 2020 г.
5. Омори, Масаэ (2004). «Геологическая идея Яносукэ Отука, заложившего основы неотектоники (геолог)». Наука о Земле . 58 (4): 256–259. дои : 10.15080/agcjchikyukagaku.58.4_256.
6. Otsuka, Yanosuke (1936). «Характер фауны японских морских моллюсков плейстоцена как свидетельство похолодания климата в Японии в плейстоцене». Бюллетень биогеографического общества Японии . 6 (16): 165–170.
7. Ochiai, Akira (1957). «Зоогеографические исследования солеоидных рыб, обнаруженных в Японии и соседних регионах-II». Бюллетень Японского общества научного рыболовства . 22 (9): 526–530. doi : 10.2331/suisan.22.526 .
8. Баркман, Ян Дж. (1958). Фитосоциология и экология криптогамных эпифитов: включая таксономическое исследование и описание их растительных единиц в Европе . Ассен: Van Gorcum.
9. Ромесбург, Х. Чарльз (1984). Кластерный анализ для исследователей. Белмонт, Калифорния: Lifetime Learning Publications. стр. 149.
10. Томсон, Годфри (1916). «Иерархия без общего фактора» (PDF) . British Journal of Psychology . 8 : 271–281.
11. Ховарт, Ричард Дж. (2017). Словарь математических наук о Земле: с историческими примечаниями. Cham: Springer. стр. 421. doi : 10.1007/978-3-319-57315-1. ISBN 978-3-319-57314-4. S2CID  67081034. […] приписано им «Оцуке» [?А. Оцуке из Департамента рыболовства Университета Тохоку].
12. Хамаи, Икусо (1955). «Стратификация сообщества с помощью «коэффициента сообщества» (продолжение)». Японский журнал экологии . 5 (1): 41–45. doi :10.18960/seitai.5.1_41.
13. Коннор, Ричард (2016). История о четырех метриках. Поиск сходства и его применение. Токио: Springer. doi :10.1007/978-3-319-46759-7_16.
14. Spruill, Marcus C. (2007). «Асимптотическое распределение координат на многомерных сферах». Electronic Communications in Probability . 12 : 234–247. doi : 10.1214/ECP.v12-1294 .
15. "Распределение скалярных произведений между двумя случайными единичными векторами в RD". CrossValidated .
16. Грэм Л. Гиллер (2012). «Статистические свойства случайных потоков битов и выборочное распределение косинусного сходства». Исследовательские заметки Giller Investments (20121024/1). doi :10.2139/ssrn.2167044. S2CID  123332455.
17. Шуберт, Эрих; Ланг, Андреас; Фехер, Глория (2021). Рейес, Нора; Коннор, Ричард; Криге, Нильс; Каземпур, Даниял; Бартолини, Илария; Шуберт, Эрих; Чен, Цзянь-Цзя (ред.). «Ускорение сферических k-средних». Поиск по сходству и его применение . Конспект лекций по информатике. 13058. Cham: Springer International Publishing: 217–231. arXiv : 2107.04074 . doi : 10.1007/978-3-030-89657-7_17. ISBN 978-3-030-89657-7. S2CID  235790358.
18. Сидоров, Григорий; Гельбух, Александр; Гомес-Адорно, Хелена; Пинто, Дэвид (29 сентября 2014 г.). «Мягкое подобие и мягкая косинусная мера: подобие признаков в векторной пространственной модели». Вычисления и системы . 18 (3): 491–504. дои : 10.13053/CyS-18-3-2043 . Проверено 7 октября 2014 г.
19. Сидоров, Григорий; Веласкес, Франциско; Стамататос, Эфстатиос; Гельбух, Александр; Чанона-Эрнандес, Лилиана (2013). Достижения в области вычислительного интеллекта . Конспекты лекций по информатике. Том. 7630. LNAI 7630. стр. 1–11. дои : 10.1007/978-3-642-37798-3_1. ISBN 978-3-642-37798-3.
20. Novotný, Vít (2018). Implementation Notes for the Soft Cosine Measure . 27th ACM International Conference on Information and Knowledge Management. Торунь, Италия: Association for Computing Machinery. стр. 1639–1642. arXiv : 1808.09407 . doi : 10.1145/3269206.3269317. ISBN 978-1-4503-6014-2.

Внешние ссылки

• Взвешенная косинусная мера
• Учебник по косинусному подобию с использованием Python