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

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

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

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

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

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

Определение

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

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

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

${\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}}}}}},$

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

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

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

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

${\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},$

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

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

Когда расстояние между двумя векторами единичной длины определяется как длина их разности векторов, тогда $$\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} ))}}\,.$$

Тем не менее косинус расстояние часто определяется без квадратного корня или коэффициента 2:

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

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

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

Нормализованный угол, называемый угловым расстоянием , между любыми двумя векторами. $A$ и $B$ является формальной метрикой расстояния и может быть рассчитана по косинусному подобию. Дополнение к метрике углового расстояния затем можно использовать для определения функции углового подобия, ограниченной от 0 до 1 включительно.

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

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

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

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

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

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

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

L ₂ – нормированное евклидово расстояние

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

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

В биологии существует похожая концепция, известная как коэффициент Оцука-Очиай, названный в честь Яносуке Оцука (также пишется как Оцука, Оцука или Отука, Японский : Яносукэ Оцука ) и Акира Отиай ( яп .: Akira Ochiai ), также известный как Отиай-Баркман или коэффициент Очиаи, который можно представить как:

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

Здесь, $A$ и $B$ являются множествами , и $|A|$ это количество элементов в $A$. Если наборы представлены в виде битовых векторов, можно увидеть, что коэффициент Оцука-Очиай такой же, как и косинусное подобие. Она идентична партитуре, введенной Годфри Томсоном .

В недавней книге коэффициент предположительно ошибочно приписан другому японскому исследователю с фамилией Оцука. Путаница возникает потому, что в 1957 году Акира Отиай приписывал коэффициент только Оцуке (имя не упоминается). цитируя статью Икусо Хамаи ( японский : Икузо Хамаи ), который, в свою очередь, цитирует оригинальную статью Яносукэ Оцуки 1936 года.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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),$

$\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-средних. точно так же неравенство Евклидова треугольника использовалось для ускорения обычных k-средних.

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

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

Например, в области обработки естественного языка (НЛП) сходство между функциями вполне интуитивно понятно. Такие функции, как слова, n -граммы или синтаксические n -граммы. могут быть весьма похожими, хотя формально в ВСМ они считаются разными признаками. Например, слова «играть» и «игра» — это разные слова и, следовательно, отображаются в разных точках VSM; однако они семантически связаны. В случае n -грамм или синтаксических n -грамм можно применить расстояние Левенштейна (фактически расстояние Левенштейна можно применять и к словам).

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

Учитывая два N -мерных вектора $a$ и $b$, мягкое косинусное подобие рассчитывается следующим образом:

${\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 ), данное уравнение эквивалентно обычной формуле косинусного подобия.

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

См. также

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

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

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