Нормализованное расстояние Google

Нормализованное расстояние Google ( NGD ) представляет собой семантического сходства, меру полученную на основе количества обращений, возвращаемых поисковой системой Google по заданному набору ключевых слов . ^{[ 1 ]} Ключевые слова с одинаковым или похожим значением в смысле естественного языка, как правило, находятся «близко» в единицах нормализованного расстояния Google, тогда как слова с разными значениями, как правило, находятся дальше друг от друга.

В частности, NGD между двумя поисковыми запросами x и y равен

\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)\}}}

где N — общее количество веб-страниц, просматриваемых Google, умноженное на среднее количество одноэлементных поисковых запросов, встречающихся на страницах; f ( x ) и f ( y ) — количество совпадений поисковых запросов x и y соответственно; и f ( x , y ) — количество веб-страниц, на которых встречаются как x, так и y .

Если $NGD(x,y)=0$ тогда x и y рассматриваются как можно более похожими, но если $NGD(x,y)\geq 1$ тогда x и y очень разные. Если два поисковых запроса x и y никогда не встречаются вместе на одной веб-странице, а встречаются по отдельности, то NGD между ними бесконечен. Если оба термина всегда встречаются вместе, их NGD равен нулю.

Пример: 9 апреля 2013 года поиск в Google «Шекспира» дал 130 000 000 результатов; поиск в Google «Макбета» дал 26 000 000 просмотров; и гуглить за «Шекспира Макбета» набрали 20 800 000 просмотров. Количество страниц, проиндексированных Google, оценивалось по числу совпадений по поисковому запросу «the», которое составило 25 270 000 000. Предполагая на средней странице содержится около 1000 поисковых запросов, что дает $N=25,270,000,000,000$ . Следовательно

NGD(Shakespeare,Macbeth)=(26.95-24.31)/(44.52-24.63)=0.13

.

«Шекспир» и «Макбет» очень похожи согласно относительной семантике, предоставленной Google .

Введение

Нормализованное расстояние Google получается из ранее нормализованного расстояния сжатия . ^{[ 2 ]}^{[ 3 ]} А именно, объекты можно задавать буквально, как буквальный четырехбуквенный геном мыши, или буквальный текст «Макбета Шекспира » . Сходство этих объектов придает НИЗ. Для простота, мы полагаем, что весь смысл объекта представлен самим буквальным объектом. Объекты также могут быть дается по имени, например, «четырехбуквенный геном мыши», или «текст «Макбета» » Шекспира . Есть также предметы, которые нельзя дать буквально, а только по имени, и которые приобретают свое значение из контекста на общем фоне. знания в человечестве, такие как «дом» или «красный». Сходство названий предметов заключается в предоставлено НГД.

Дистрибутив Google и код Google

Вероятности поисковых запросов Google, понимаемые как частота подсчета страниц, возвращаемая Google, разделенная на количество страниц, проиндексированных Google (умноженное на среднее количество поисковых запросов на этих страницах), приблизительно соответствует фактической относительной частоте этих поисковых запросов, которые фактически используются в обществе. Основываясь на этой предпосылке, отношения, представленные нормализованным расстоянием Google, приблизительно захватывают предполагаемые истинные семантические отношения, управляющие условиями поиска. В НГД используются Всемирная паутина и Google. Другие текстовые корпуса включают Википедию короля Иакова , версию Библии или Оксфордский словарь английского языка вместе с соответствующими поисковыми системами.

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

Следующие свойства доказаны в: ^{[ 1 ]}

NGD находится примерно между 0 и $\infty$ . Оно может быть слегка отрицательным. Например, «красный красный» дает примерно на 20% больше посещений Google во Всемирной паутине, чем «красный». (В середине 2013 года было 4 260 000 000 совпадений для слова «красный» и 5 500 000 000 совпадений для «красный красный». В настоящее время «красный красный» теперь возвращает гораздо меньше результатов, чем «красный».) Если $NGD(x,y)\geq 1$ тогда мы рассматриваем x и y как очень разные.
NGD не является показателем . NGD равен нулю для x и y, которые не равны, при условии, что x и y всегда встречаются вместе на одной и той же веб-странице. Из формулы НГД мы видим, что она симметрична . Свойство треугольника не удовлетворяется NGD. Однако эти результаты являются теоретическими. Трудно придумать практические примеры Всемирной паутины с использованием Google, которые нарушают свойство треугольника.

Приложения

Приложения к цветам и числам, простым и непростым числам и т. д. даны в: ^{[ 1 ]} а также рандомизированный массовый эксперимент с использованием категорий WordNet . В случае сравнения простых и непростых чисел и эксперимента WordNet метод NGD дополняется машинным классификатором опорных векторов . Эксперименты состоят из 25 положительных примеров и 25 отрицательных. Эксперимент WordNet состоял из 100 случайных категорий WordNet. Метод NGD имел успех 87,25%. Среднее значение составляет 0,8725, а стандартное отклонение — 0,1169. Эти показатели соответствуют категориям WordNet, которые отражают знания исследователей с докторской степенью, вошедших в них. Редко можно увидеть согласие менее 75%.

Ссылки

^ Jump up to: ^а ^б ^с Р.Л. Чилибраси; ПМБ Витаний (2007). «Расстояние сходства Google». IEEE Транс. Знания и инженерия данных . 19 (3): 370–383. arXiv : cs/0412098 . дои : 10.1109/TKDE.2007.48 . S2CID 59777 .
^ Р.Л. Чилибраси; ПМБ Витаний (2005). «Кластеризация путем сжатия» . IEEE Транс. Инф. Теория . 51:12 .arXiv cs.CV/0312044 : . дои : 10.1109/TKDE.2007.48 . S2CID 59777 .
^ М. Ли; С. Чен; С. Ли; Б. Ма; ПМБ Витаний (декабрь 2004 г.). «Метрика сходства». IEEE Транс. Инф. Теория . 50 (12). IEEE : 3250–3264. дои : 10.1109/TIT.2004.838101 . S2CID 221927 .

Дальнейшее чтение

Р. Аллен и Ю. Ву (2005). «Метрики объема коллекции» . ДЖАСИСТ . 55 (10): 1243–1249. дои : 10.1002/asi.20202 .
М. Ли и PMB Витаньи (2019). Введение в колмогоровскую сложность и ее приложения (Четвертое изд.). Спрингер.
Дункан Грэм-Роу (28 января 2005 г.). «Google ищет смысл» . Новый учёный . Архивировано из оригинала 5 февраля 2005 года.
Дж. Польша и Th. Зейгманн (2006). Кластеризация расстояния Google с помощью собственных векторов и полуопределенного программирования (PDF) . Медиа-технологии знаний, Первый международный комплексный семинар. Дагштуль, Германия. стр. 61–69.
А. Гупта и Т. Оутс (2007). Использование онтологий и Интернета для изучения лексической семантики (PDF) . IJCAI'07: Материалы 20-й международной совместной конференции по искусственному интеллекту. стр. 1618–1623. Архивировано из оригинала (PDF) 19 февраля 2009 г. (Включает сравнение NGD с другими алгоритмами.)
Вонг, В.; Лю, В. и Беннамун, М. (2007). «Муравьиный алгоритм обхода деревьев для кластеризации терминов на основе невыразительных сходств». Интеллектуальный анализ данных и обнаружение знаний . 15 (3): 349–381. дои : 10.1007/s10618-007-0073-y . S2CID 14924678 . (использование NGD для кластеризации терминов)

[CV07-1] Jump up to: ^а ^б ^с Р.Л. Чилибраси; ПМБ Витаний (2007). «Расстояние сходства Google». IEEE Транс. Знания и инженерия данных . 19 (3): 370–383. arXiv : cs/0412098 . дои : 10.1109/TKDE.2007.48 . S2CID 59777 .

[CV04-2] Р.Л. Чилибраси; ПМБ Витаний (2005). «Кластеризация путем сжатия» . IEEE Транс. Инф. Теория . 51:12 .arXiv cs.CV/0312044 : . дои : 10.1109/TKDE.2007.48 . S2CID 59777 .

[Li04-3] М. Ли; С. Чен; С. Ли; Б. Ма; ПМБ Витаний (декабрь 2004 г.). «Метрика сходства». IEEE Транс. Инф. Теория . 50 (12). IEEE : 3250–3264. дои : 10.1109/TIT.2004.838101 . S2CID 221927 .

[ 1 ]

[ 2 ]

[ 3 ]