Distancia normalizada de Google

La distancia normalizada de Google ( NGD ) es una medida de similitud semántica derivada del número de resultados devueltos por el motor de búsqueda de Google para un conjunto determinado de palabras clave . ^[1] Las palabras clave con significados iguales o similares en un sentido de lenguaje natural tienden a estar "cerca" en unidades de distancia normalizada de Google, mientras que las palabras con significados diferentes tienden a estar más separadas.

En concreto, la NGD entre dos términos de búsqueda x e y es

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

donde N es el número total de páginas web buscadas por Google multiplicado por el número promedio de términos de búsqueda únicos que aparecen en las páginas; f ( x ) y f ( y ) son el número de resultados para los términos de búsqueda x e y , respectivamente; y f ( x ,  y ) es el número de páginas web en las que aparecen x e y .

Si x e y se consideran tan parecidos como sea posible, pero si x e y son muy diferentes. Si los dos términos de búsqueda x e y nunca aparecen juntos en la misma página web, pero sí aparecen por separado, la NGD entre ellos es infinita. Si ambos términos aparecen siempre juntos, su NGD es cero. ${\displaystyle NGD(x,y)=0}$ ${\displaystyle NGD(x,y)\geq 1}$

Ejemplo: el 9 de abril de 2013, al buscar en Google "Shakespeare" se obtuvieron 130.000.000 de resultados; al buscar en Google "Macbeth", se obtuvieron 26.000.000 de resultados; y al buscar en Google "Shakespeare Macbeth", se obtuvieron 20.800.000 de resultados. La cantidad de páginas indexadas por Google se estimó a partir de la cantidad de resultados del término de búsqueda "the", que fue de 25.270.000.000 de resultados. Suponiendo que hay alrededor de 1.000 términos de búsqueda en la página promedio, esto da . Por lo tanto ${\displaystyle N=25,270,000,000,000}$

${\displaystyle NGD(Shakespeare,Macbeth)=(26.95-24.31)/(44.52-24.63)=0.13}$.

"Shakespeare" y "Macbeth" son muy parecidos según la semántica relativa proporcionada por Google .

Introducción

La distancia normalizada de Google se deriva de la distancia de compresión normalizada anterior . ^{[2] [3]} Es decir, los objetos pueden darse literalmente, como el genoma literal de cuatro letras de un ratón, o el texto literal de Macbeth de Shakespeare . La similitud de estos objetos está dada por la NCD. Para simplificar, asumimos que todo el significado del objeto está representado por el objeto literal en sí. Los objetos también pueden darse por nombre, como 'el genoma de cuatro letras de un ratón' o 'el texto de Macbeth de Shakespeare '. También hay objetos que no pueden darse literalmente, sino solo por nombre, y que adquieren su significado de sus contextos en el conocimiento común de fondo en la humanidad, como "hogar" o "rojo". La similitud entre los nombres de los objetos está dada por la NGD.

Distribución de Google y código de Google

Las probabilidades de los términos de búsqueda de Google, concebidas como las frecuencias de los recuentos de páginas devueltas por Google divididas por el número de páginas indexadas por Google (multiplicado por el número promedio de términos de búsqueda en esas páginas), se aproximan a las frecuencias relativas reales de esos términos de búsqueda tal como se usan realmente en la sociedad. Con base en esta premisa, las relaciones representadas por la distancia normalizada de Google capturan aproximadamente las supuestas relaciones semánticas verdaderas que gobiernan los términos de búsqueda. En la NGD, se utilizan la World Wide Web y Google. Otros corpus de texto incluyen Wikipedia , la versión King James de la Biblia o el Oxford English Dictionary junto con los motores de búsqueda apropiados.

Propiedades

Las siguientes propiedades se prueban en: ^[1]

• El NGD se encuentra aproximadamente entre 0 y . Puede ser ligeramente negativo. Por ejemplo, "rojo rojo" da aproximadamente un 20% más de resultados de Google en la World Wide Web que "rojo". (A mediados de 2013, hubo 4.260.000.000 de resultados para "rojo" y 5.500.000.000 de resultados para "rojo rojo". Actualmente, "rojo rojo" ahora arroja muchos menos resultados que "rojo"). Si entonces consideramos que x e y son muy diferentes. ${\displaystyle \infty }$ ${\displaystyle NGD(x,y)\geq 1}$
• La NGD no es una métrica . La NGD es cero para x e y que no son iguales, siempre que x e y aparezcan siempre juntos en la misma página web. De la fórmula de la NGD se desprende que es simétrica . La NGD no satisface la propiedad del triángulo. Sin embargo, estos resultados son teóricos. Es difícil encontrar ejemplos prácticos de la World Wide Web utilizando Google que violen la propiedad del triángulo.

Aplicaciones

^{En [1]} se dan aplicaciones a colores versus números, primos versus no primos, etc., así como un experimento masivo aleatorio que utiliza categorías de WordNet . En el caso de primos versus no primos y en el experimento de WordNet, el método NGD se amplía con un clasificador de máquina de vectores de soporte . Los experimentos consisten en 25 ejemplos positivos y 25 negativos. El experimento de WordNet consistió en 100 categorías aleatorias de WordNet. El método NGD tuvo una tasa de éxito del 87,25 %. La media es 0,8725, mientras que la desviación estándar fue 0,1169. Estas tasas se refieren a la concordancia con las categorías de WordNet, que representan el conocimiento de los investigadores con doctorados que las introdujeron. Es raro ver una concordancia inferior al 75 %.

Referencias

1. RL Cilibrasi; PMB Vitanyi (2007). "La distancia de similitud de Google". IEEE Trans. Conocimiento e ingeniería de datos . 19 (3): 370–383. arXiv : cs/0412098 . doi :10.1109/TKDE.2007.48. S2CID  59777.
2. RL Cilibrasi; PMB Vitanyi (2005). "Agrupamiento por compresión". IEEE Trans. Inf. Theory . 51 : 12. arXiv : cs.CV/0312044 . doi :10.1109/TKDE.2007.48. S2CID  59777.
3. M. Li; X. Chen; X. Li; B. Ma; PMB Vitanyi (diciembre de 2004). "La métrica de similitud". IEEE Trans. Inf. Theory . 50 (12). IEEE : 3250–3264. doi :10.1109/TIT.2004.838101. S2CID  221927.

Lectura adicional

• R. Allen y Y. Wu (2005). "Métricas para el alcance de una colección". JASIST . 55 (10): 1243–1249. doi :10.1002/asi.20202.
• M. Li y PMB Vitanyi (2019). Introducción a la complejidad de Kolmogorov y sus aplicaciones (cuarta edición). Springer.
• Duncan Graham-Rowe (28 de enero de 2005). «La búsqueda de significado de Google». New Scientist . Archivado desde el original el 5 de febrero de 2005.
• J. Poland y Th. Zeugmann (2006). Agrupamiento de la distancia de Google con vectores propios y programación semidefinida (PDF) . Knowledge Media Technologies, primer taller internacional de núcleo a núcleo. Dagstuhl, Alemania. págs. 61–69.
• A. Gupta y T. Oates (2007). Uso de ontologías y la Web para aprender semántica léxica (PDF) . IJCAI'07: Actas de la 20.ª conferencia conjunta internacional sobre inteligencia artificial. pp. 1618–1623. Archivado desde el original (PDF) el 19 de febrero de 2009.(Incluye comparación de NGD con otros algoritmos).
• Wong, W.; Liu, W. y Bennamoun, M. (2007). "Algoritmo de hormigas que atraviesa árboles para la agrupación de términos basada en similitudes sin características". Minería de datos y descubrimiento de conocimiento . 15 (3): 349–381. doi :10.1007/s10618-007-0073-y. S2CID  14924678.(el uso de NGD para agrupar términos)