Normalizovaná vzdálenost Google - Normalized Google distance

The Normalizovaná vzdálenost Google (NGD) je sémantická podobnost opatření odvozeno z počtu zásahů vrácených Vyhledávač Google za dané soubor z klíčová slova.^[1] Klíčová slova se stejným nebo podobným významem ve smyslu přirozeného jazyka mají tendenci být „blízká“ v jednotkách normalizované vzdálenosti Google, zatímco slova s odlišnými významy mají tendenci být dále od sebe.

Konkrétně normalizovaná vzdálenost Google (NGD) mezi dvěma hledanými výrazy X a y je

{ displaystyle operatorname {NGD} (x, y) = { frac { max { log f (x), log f (y) } - log f (x, y)} { log N- min { log f (x), log f (y) }}}}

kde N je celkový počet webových stránek prohledávaných společností Google vynásobený průměrným počtem jednotlivých vyhledávacích dotazů vyskytujících se na stránkách; F(X) a F(y) je počet požadavků na vyhledávací dotazy X a y, v uvedeném pořadí; a F(X, y) je počet webových stránek, na kterých jsou obě X a y nastat.

Pokud ${ displaystyle NGD (x, y) = 0}$ pak x a y jsou viděny co nejvíce podobné, ale pokud ${ displaystyle NGD (x, y) geq 1}$ pak x a y jsou velmi odlišné.Pokud jsou dva hledané výrazy X a y nikdy se nevyskytují společně na stejné webové stránce, ale vyskytují se samostatně, NGD mezi nimi je nekonečná. Pokud se oba termíny vyskytují vždy společně, jejich NGD je nula.

Příklad: Dne 9. dubna 2013 dal googling pro „Shakespeara“ 130 000 000 zásahů; googlování pro „Macbeth“ dal 26 000 000 zásahů; a googling pro „Shakespeare Macbeth“ poskytl 20 800 000 zásahů. Počet stránek indexovaných Googlem byl odhadnut podle počtu zásahů hledaného výrazu „the“, což bylo 25 270 000 000 zásahů. Za předpokladu, že na průměrné stránce je přibližně 1 000 hledaných výrazů ${ displaystyle N = 25 270 000 000 000}$ .Proto

{ displaystyle NGD (Shakespeare, Macbeth) = (26,95-24,31) / (44,52-24,63) = 0,13}

.

„Shakespeare“ a „Macbeth“ jsou si velmi podobní podle relativní sémantiky poskytnuté Google.

Úvod

Normalizovaná vzdálenost Google je odvozena od dřívějších Normalizovaná kompresní vzdálenost..^[2]^[3]Objekty lze jmenovat doslova, například doslovný čtyřpísmenný genom myši nebo doslovný text Macbeth podle Shakespeare. Podobnost těchto objektů je dána NCD. Forsimplicity bereme to tak, že veškerý význam objektu je představován samotným doslovným objektem. Objekty mohou také začínat podle jména, například „čtyřpísmenný genom myši“ nebo „text Macbeth podle Shakespeare " Existují také objekty, které nemohou být dány doslovně, ale pouze jménem, a které získávají svůj význam z jejich kontextů v pozadí běžného poznání v lidstvu, například „domov“ nebo „červená“. Podobnost mezi názvy objektů je dána NGD.

Distribuce Google a Google Code

Pravděpodobnosti vyhledávacích dotazů Google, koncipovaných jako četnosti počtu stránek vrácených Googlem, děleno počtem stránek indexovaných Googlem (vynásobené průměrným počtem hledaných výrazů na těchto stránkách), přibližují skutečné relativní četnosti těchto hledaných výrazů, jak se ve společnosti skutečně používají . Na základě této premisy vztahy reprezentované tehdy normalizovanou vzdáleností Google přibližně zachycují předpokládané skutečné sémantické vztahy, kterými se řídí hledané výrazy. V NGD se používá World Wide Web a Google. Jiný textový korpus může být Wikipedia, King James verzebible nebo Oxfordský anglický slovník společně s příslušnými vyhledávači.

Vlastnosti

Následující vlastnosti jsou prokázány v:^[1]

NGD je zhruba mezi 0 a ${ displaystyle infty}$ . Může to být mírně negativní. Například „červená červená“ poskytuje přibližně o 20% více požadavků Google na webu Celosvětová Síť než „červená“. (V polovině roku 2013 bylo zaznamenáno 4 260 000 000 zásahů pro „červenou“ a 5 500 000 000 zásahů pro „červenou červenou“. V současné době „červená červená“ nyní přináší mnohem méně výsledků než „červená“.) Pokud ${ displaystyle NGD (x, y) geq 1}$ pak považujeme x a y za velmi odlišné.
NGD není metrický. Na začátku jsme viděli, že NGD je nula pro x a y, které nejsou stejné, za předpokladu, že x a y se vždy vyskytují společně na stejné webové stránce. Ze vzorce NGD vidíme, že je symetrický. The trojúhelník vlastnost není uspokojena NGD. Tyto výsledky jsou však teoretické. Je těžké přijít s praktickými příklady Celosvětová Síť pomocí Google, které porušují trojúhelník vlastnictví.

Aplikace

Aplikace pro barvy versus čísla, připraví versus non-prvočísla a tak jsou uvedeny v,^[1]stejně jako náhodný masivní experiment s použitím WordNet Kategorie. V prvočíslech versus předčasně připravených a WordNet experiment NGD metoda je rozšířena o a Podporujte vektorový stroj klasifikátor. Pokusy se skládají z 25 pozitivních příkladů a 25 negativních. The WordNet experiment se skládal ze 100 náhodných WordNet Kategorie. Metoda NGD měla úspěšnost 87,25%. To je průměr 0,8725, zatímco standardní odchylka byla 0,1169. Tyto ceny jsou o dohodě s WordNet kategorie, které představují znalosti výzkumných pracovníků s PhD, kteří je zadali. Je zřídka vidět shodu méně než 75%.

Reference

^ ^A ^b ^C Vzdálenost podobnosti Google na ArXiv.org nebo R.L.Cilibrasi a P.M.B. Vitanyi, vzdálenost podobnosti Google, IEEE Trans. Znalostní a datové inženýrství, 19: 3 (2007), 370–383 nebo https://arxiv.org/abs/cs.CL/0412098
^ Clustering by Compression on ArXiv.org nebo R.L.Cilibrasi a P.M.B. Vitanyi, Clustering by Compression, IEEE Trans. Informační teorie, 51:12 (2005).
^ „M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The metricita podobnosti, IEEE Trans. Inform. Th., 50:12 (2004), 3250-3264“. Ieeexplore.ieee.org. 2011-09-27. doi:10.1109 / TIT.2004.838101. S2CID 221927. Citovat deník vyžaduje | deník = (Pomoc)

Související literatura

R. Allen a Y. Wu, Metriky pro rozsah sbírky, JASIST, (2005), 55 (10), 1243-1249
M. Li a P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer, 2019, Fourth Edition
Google hledá smysl na Newscientist.com.
J. Polsko a Th. Zeugmann (2006), Shlukování vzdálenosti Google pomocí vlastních vektorů a semidefinitního programování
A. Gupta a T. Oates (2007), Používání ontologií a webu k výuce lexikální sémantiky (Zahrnuje srovnání NGD s jinými algoritmy.)
Wong, W., Liu, W. & Bennamoun, M. (2007) Algoritmus pro procházení stromů pro seskupování termínů na základě bezvýznamných podobností. In: Data Mining and Knowledge Discovery, svazek 15, číslo 3, strany 349–381. doi:10.1007 / s10618-007-0073-r (použití NGD pro seskupování termínů)

[CV07-1] A ^b ^C Vzdálenost podobnosti Google na ArXiv.org nebo R.L.Cilibrasi a P.M.B. Vitanyi, vzdálenost podobnosti Google, IEEE Trans. Znalostní a datové inženýrství, 19: 3 (2007), 370–383 nebo https://arxiv.org/abs/cs.CL/0412098

[CV04-2] Clustering by Compression on ArXiv.org nebo R.L.Cilibrasi a P.M.B. Vitanyi, Clustering by Compression, IEEE Trans. Informační teorie, 51:12 (2005).

[Li04-3] „M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The metricita podobnosti, IEEE Trans. Inform. Th., 50:12 (2004), 3250-3264“. Ieeexplore.ieee.org. 2011-09-27. doi:10.1109 / TIT.2004.838101. S2CID 221927. Citovat deník vyžaduje | deník = (Pomoc)

[1]

[2]

[3]