Kosinová podobnost - Cosine similarity

Kosinová podobnost je míra podobnosti mezi dvěma nenulovými vektory an vnitřní produktový prostor. Je definován tak, aby se rovnal kosinus úhlu mezi nimi, který je také stejný jako vnitřní produkt stejných vektorů normalizováno oba mají délku 1. Kosinus 0 ° je 1 a pro jakýkoli úhel v intervalu je menší než 1 (0, π] radiány. Jde tedy o úsudek o orientaci a ne o velikost: dva vektory se stejnou orientací mají kosinovou podobnost 1, dva vektory orientované 90 ° vzájemně vůči sobě mají podobnost 0 a dva diametrálně odlišné vektory mají podobnost - 1, nezávisle na jejich velikosti. Kosinová podobnost se používá zejména v pozitivním prostoru, kde je výsledek úhledně ohraničen ${displaystyle [0,1]}$. Název je odvozen od výrazu „kosinový směr“: v tomto případě jednotkové vektory jsou maximálně „podobné“, pokud jsou paralelní, a maximálně „odlišné“, pokud jsou ortogonální (kolmý). To je analogické s kosinem, což je jednota (maximální hodnota), když segmenty mají nulový úhel a nula (nekorelující), když jsou segmenty kolmé.

Tyto hranice platí pro libovolný počet dimenzí a kosinová podobnost se nejčastěji používá v pozitivních prostorech vysokých rozměrů. Například v vyhledávání informací a dolování textu, každému výrazu je teoreticky přiřazena jiná dimenze a dokument je charakterizován vektorem, kde hodnota v každé dimenzi odpovídá počtu, kolikrát se výraz v dokumentu objeví. Kosinová podobnost pak poskytuje užitečné měřítko toho, jak podobné dva dokumenty budou pravděpodobně z hlediska jejich předmětu.^[1]

Tato technika se také používá k měření soudržnosti v klastrech v oblasti dolování dat.^[2]

Termín kosinová vzdálenost se často používá pro doplněk v pozitivním prostoru, to znamená: ${displaystyle D_ {C} (A, B) = 1-S_ {C} (A, B),}$ kde ${displaystyle D_ {C}}$ je kosinová vzdálenost a ${displaystyle S_ {C}}$ je kosinová podobnost. Je však důležité si uvědomit, že to není správné vzdálenost metrická protože nemá nerovnost trojúhelníku majetek - nebo, formálněji, Schwarzova nerovnost —A porušuje axiom shody okolností; k opravě vlastnosti nerovnosti trojúhelníku při zachování stejného pořadí je nutné převést na úhlovou vzdálenost (viz níže).

Jednou výhodou kosinové podobnosti je její nízká složitost, zejména pro řídké vektory: je třeba brát v úvahu pouze nenulové rozměry.

Jiná jména kosinové podobnosti jsou Orchini podobnost a Tucker koeficient shody; Ochiai podobnost (viz níže) je kosinová podobnost aplikovaná na binární data.

Definice

Kosinus dvou nenulových vektorů lze odvodit pomocí Euklidovský tečkovaný produkt vzorec:

${displaystyle mathbf {A} cdot mathbf {B} = left | mathbf {A} ight | left | mathbf {B} ight | cos heta}$

Vzhledem k tomu dva vektory atributů, A a Bkosinová podobnost, cos (θ), je znázorněno pomocí a Tečkovaný produkt a velikost tak jako

${displaystyle {ext {podobnost}} = cos (heta) = {mathbf {A} cdot mathbf {B} nad | mathbf {A} || mathbf {B} |} = {frac {limity součtu _ {i = 1} ^ {n} {A_ {i} B_ {i}}} {{sqrt {součet limitů _ {i = 1} ^ {n} {A_ {i} ^ {2}}}}} {sqrt {součet limitů _ { i = 1} ^ {n} {B_ {i} ^ {2}}}}}},}$

kde ${displaystyle A_ {i}}$ a ${displaystyle B_ {i}}$ jsou komponenty vektoru ${displaystyle A}$ a ${displaystyle B}$ resp.

Výsledná podobnost se pohybuje od −1, což znamená přesně opačný, do 1, což znamená přesně to samé, přičemž 0 označuje ortogonalita nebo dekorelace, zatímco mezilehlé hodnoty označují střední podobnost nebo odlišnost.

Pro shoda textu, vektory atributů A a B jsou obvykle četnost termínů vektory dokumentů. Podobnost kosinu lze chápat jako metodu normalizace délka dokumentu během srovnání.

V případě vyhledávání informací, kosinová podobnost dvou dokumentů se bude pohybovat od 0 do 1, protože termín frekvence (použití tf – idf váhy) nemohou být záporné. Úhel mezi dvěma členy kmitočtových vektorů nemůže být větší než 90 °.

Pokud jsou vektory atributů normalizovány odečtením vektorových průměrů (např. ${displaystyle A- {ar {A}}}$), míra se nazývá středová kosinová podobnost a je ekvivalentní s Pearsonův korelační koeficient. Jako příklad centrování ${displaystyle {ext {if}}, A = [A_ {1}, A_ {2}] ^ {T}, {ext {then}} {ar {A}} = vlevo [{frac {(A_ {1} + A_ {2})} {2}}, {frac {(A_ {1} + A_ {2})} {2}} ight] ^ {T}, {ext {so}} A- {ar {A }} = vlevo [{frac {(A_ {1} -A_ {2})} {2}}, {frac {(-A_ {1} + A_ {2})} {2}} vpravo] ^ {T }.}$

Úhlová vzdálenost a podobnost

Termín „kosinová podobnost“ se někdy používá k označení jiné definice podobnosti uvedené níže. Nejběžnější použití „kosinové podobnosti“ je však definováno výše a metriky podobnosti a vzdálenosti definované níže jsou označovány jako „úhlová podobnost“ a „úhlová vzdálenost“. Normalizovaný úhel mezi vektory je formální vzdálenost metrická a lze ji vypočítat z výše uvedeného skóre podobnosti.^[3] Tuto metriku úhlové vzdálenosti lze poté použít k výpočtu funkce podobnosti ohraničené mezi 0 a 1 včetně.

Když mohou být vektorové prvky pozitivní nebo negativní:

${displaystyle {ext {angular distance}} = {frac {cos ^ {- 1} ({ext {cosine podobnost}})} {pi}}}$

${displaystyle {ext {úhlová podobnost}} = 1- {ext {úhlová vzdálenost}}}$

Nebo pokud jsou vektorové prvky vždy pozitivní:

${displaystyle {ext {angular distance}} = {frac {2cdot cos ^ {- 1} ({ext {cosine podobnost}})} {pi}}}$

${displaystyle {ext {úhlová podobnost}} = 1- {ext {úhlová vzdálenost}}}$

Ačkoli pro tuto úhlovou vzdálenost byl použit termín „kosinová podobnost“, používá se jako kosinus úhlu pouze jako vhodný mechanismus pro výpočet úhlu samotného a není součástí významu. Výhodou koeficientu úhlové podobnosti je, že při použití jako rozdílového koeficientu (odečtením od 1) je výsledná funkce vlastní vzdálenost metrická, což neplatí pro první význam. Pro většinu použití to však není důležitá vlastnost. Pro každé použití, kde je důležité pouze relativní uspořádání podobnosti nebo vzdálenosti v sadě vektorů, je potom použitá funkce nepodstatná, protože výsledné pořadí nebude ovlivněno volbou.

Otsuka-Ochiai koeficient

V biologii existuje podobný koncept známý jako Otsuka-Ochiaiho koeficient pojmenovaný po něm Yanosuke Otsuka (také hláskováno jako Ōtsuka, Ootsuka nebo Otuka,^[4] japonský: 大 塚 弥 之 助)^[5] a Akira Ochiai (japonský: 落 合 明),^[6] také známý jako Ochiai-Barkman^[7] nebo Ochiaiho koeficient,^[8] které lze reprezentovat jako:

${displaystyle K = {frac {| Acap B |} {sqrt {| A | ti | B |}}}}$

Tady, ${displaystyle A}$ a ${displaystyle B}$ jsou sady, a ${displaystyle | A |}$ je počet prvků v ${displaystyle A}$. Pokud jsou množiny reprezentovány jako bitové vektory, lze vidět, že Otsuka-Ochiaiův koeficient je stejný jako kosinová podobnost.

V nedávné knize^[9] koeficient je nesprávně přiřazen jinému japonskému výzkumníkovi s příjmením Otsuka. Zmatek nastává, protože v roce 1957 Akira Ochiai přisuzuje koeficient pouze Otsuce (jméno není uvedeno)^[6] citováním článku Ikusa Hamai (japonský: 浜 井 生 三),^[10] který zase cituje původní článek Yanosuke Otsuka z roku 1936.^[5]

Vlastnosti

Kosinová podobnost souvisí Euklidovská vzdálenost jak následuje. Označte euklidovskou vzdálenost obvyklým způsobem ${displaystyle | A-B |}$a dodržujte to

${displaystyle | A-B | ^ {2} = (A-B) ^ {mathsf {T}} (A-B) = | A | ^ {2} + | B | ^ {2} -2A ^ {mathsf {T}} B}$

podle rozšíření. Když A a B jsou normalizovány na délku jednotky, ${displaystyle | A | ^ {2} = | B | ^ {2} = 1}$ takže tento výraz se rovná

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

Euklidovská vzdálenost se nazývá vzdálenost akordů (protože se jedná o délku akordu na jednotkové kružnici) a jedná se o euklidovskou vzdálenost mezi vektory, které byly normalizovány na jednotkový součet čtvercových hodnot v nich.

Nulová distribuce: U dat, která mohou být záporná i kladná, se použije hodnota nulová distribuce pro kosinovou podobnost je distribuce Tečkovaný produkt dvou nezávislých náhodných jednotkové vektory. Tato distribuce má a znamenat nula a a rozptyl z ${displaystyle 1 / n}$ (kde ${displaystyle n}$ je počet rozměrů), ai když je distribuce ohraničena mezi -1 a +1, jako ${displaystyle n}$ roste do velké míry je distribuce čím dál tím lépe aproximována normální distribuce.^[11][12] Jiné typy dat, jako např bitové proudy, které mají pouze hodnoty 0 nebo 1, má nulová distribuce jinou formu a může mít nenulovou střední hodnotu.^[13]

Mírný kosinový rozměr

Měkký kosinus nebo („měkká“ podobnost) mezi dvěma vektory bere v úvahu podobnosti mezi dvojicemi prvků.^[14] Tradiční kosinová podobnost bere v úvahu vektorový vesmírný model Funkce (VSM) jsou nezávislé nebo zcela odlišné, zatímco opatření měkkého kosinu navrhuje zvážit podobnost funkcí ve VSM, které pomáhají zobecnit koncept kosinu (a měkkého kosinu) i myšlenku (měkké) podobnosti.

Například v oblasti zpracování přirozeného jazyka (NLP) je podobnost mezi funkcemi docela intuitivní. Funkce jako slova, n-gramy nebo syntaktické n-gramy^[15] mohou být docela podobné, i když formálně jsou ve VSM považovány za různé funkce. Například slova „hrát“ a „hra“ jsou různá slova, a proto jsou mapována do různých bodů VSM; přesto jsou sémanticky příbuzné. V případě n-gramy nebo syntaktické n-gramy, Levenshteinova vzdálenost lze použít (ve skutečnosti lze Levenshteinovu vzdálenost použít i na slova).

Pro výpočet měkkého kosinu, matice s se používá k označení podobnosti mezi funkcemi. To lze vypočítat z Levenshteinovy ​​vzdálenosti, WordNet podobnost nebo jiné opatření podobnosti. Pak tuto matici pouze vynásobíme.

Vzhledem k tomu dva N-dimenzionální vektory ${displaystyle a}$ a ${displaystyle b}$, podobnost měkkého kosinu se vypočítá takto:

${displaystyle {egin {aligned} operatorname {soft _cosine} _ {1} (a, b) = {frac {sum olimits _ {i, j} ^ {N} s_ {ij} a_ {i} b_ {j} } {{sqrt {sum olimits _ {i, j} ^ {N} s_ {ij} a_ {i} a_ {j}}} {sqrt {sum olimits _ {i, j} ^ {N} s_ {ij} b_ {i} b_ {j}}}}}, konec {zarovnáno}}}$

kde s_ij = podobnost (funkce_i, Vlastnosti_j).

Pokud neexistuje podobnost mezi funkcemi (s_ii = 1, s_ij = 0 pro i ≠ j), daná rovnice je ekvivalentní konvenčnímu kosinusovému podobnému vzorci.

The časová složitost tohoto opatření je kvadratické, díky čemuž je použitelné pro úkoly v reálném světě. Všimněte si, že složitost lze snížit na subkvadratickou.^[16]

Viz také

• Sørensen – koeficient kostky
• Hammingova vzdálenost
• Korelace
• Jaccardův index
• SimRank
• Získávání informací

Reference

externí odkazy

• Vážená kosinová míra
• Výukový program o kosinové podobnosti pomocí Pythonu