¿Cómo funciona un buscador? Parte 2

En la Parte 1 aprendíamos las diferencias entre los diversos tipos de buscadores y como se pueden buscar cosas de forma muy rápida cuando tenemos mucha información. En esta segunda parte vamos ver el último paso de funcionamiento de un buscador, no por ello menos importante. Se trata de la ordenación de los resultados de una búsqueda. Para esta tarea existen cientos de algoritmos y métodos de los cuales vamos a ver una pequeña introducción intuitiva.

Según la eficacia de estos métodos el usuario obtendrá una satisfacción mayor o menor. ¿Os molesta que el Google no encuentre lo que buscáis? ¿Os molesta encontrar el mejor resultado en la segunda página?

El primer método que nos viene a todos a la cabeza es el de poner antes las páginas web donde más veces aparezca la palabra que buscamos. Supongamos que buscamos “Albert Einstein”, aplicamos los métodos descritos en la Parte 1, y solo exisen 3 páginas en Internet que contienen alguna de las dos palabras:

-Página web 1: ” Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.”

-Página web 2: ” Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.”

-Página web 3: “Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.”

Si aplicamos el método de contar las palabras clave y poner antes las páginas web en las que más aparezcan las palabras buscadas obtendríamos la siguiente ordenación:

-PRIMERA POSICIÓN (Las Palabras Albert y Einstein aparecen 5 veces): ” Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.”

-SEGUNDA POSICIÓN (Las Palabras Albert y Einstein aparecen 4 veces):”Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.”

-TERCERA POSICIÓN (Las Palabras Albert y Einstein aparecen 3 veces): “Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.”

Fijaros que si el Google nos diera este resultado no estaríamos muy satisfechos con la primera página obtenida ya que no habla de Albert Einstein. Debemos mejorar nuestro algoritmo de ordenación de resultados. ¿Qué es mejor GENERALMENTE, una web con 50.000 palabras donde aparece Albert Einstein una vez, o una web con 50 palabras donde aparece Albert Einstein una vez? Yo creo que todos escogeríamos la segunda web. Veamos como podemos mejorar nuestro método para tener en cuenta este factor.

Además de tener en cuenta el número de apariciones de las palabras clave, vamos a contar el número de palabras de cada web. Calculamos el número de palabras de cada web y lo dividimos entre el número de apariciones de las palabras para obtener la puntuación final. Cuanto más palabras tenga la web menor será la puntuación a no ser que la palabra clave aparezca muchas veces.

-PRIMERA POSICIÓN (Número de palabras:21. Número apariciones: 3 . Puntuación: 3/21=0.14): “Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.”

-SEGUNDA POSICIÓN (Número de palabras:38. Número apariciones: 4 . Puntuación: 4/38=0.10 ):”Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.”

-TERCERA POSICIÓN (Número de palabras:53. Número apariciones: 5 . Puntuación: 5/53=0.09): ” Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.”

Fijaros que hemos conseguido que las páginas con mayor Densidad de palabras clave aparezcan primero. Seguramente hayáis notado esta característica al buscar con Google, generalmente los primeros resultados muestran webs donde las palabras que hemos buscado están muy cercanas y aparecen muchas veces.

Tened en cuenta que ésta es una pequeña descripción del método de forma intuitiva. La fórmula completa tiene en cuenta otros factores importantes, ya que según lo descrito una web que pusiera “Albert Einstein” a secas sería la ganadora. Este no es un método definitivo ni mucho menos, hay muchos algoritmos que utilizan técnicas muy avanzadas para intentar darnos los mejores resultados. Una mejora sería aplicar este método para cada frase, e ir sumando la puntuación de cada frase para obtener una puntuación final.

A este método se le pueden encontrar muchos defectos, pero por lo general funciona bastante bien. Además, debéis tener en cuenta que la ordenación de los resultados finales es algo muy subjetivo. Quizás un resultado no le sirva para nada a la persona X, pero a la persona Y le sea de mucha utilidad. Por ello Google, además de utilizar algoritmos básicos de ordenación como el que acabamos de explicar, usa también el famoso PageRank para mejorar aún más a disposición de los resultados.

Recién aprendimos como los resultados de una búsqueda se ordenan según su importancia usando una serie de algoritmos. Pero estos algoritmos son totalmente autómaticos y simplemente se basan en la correspondencia del texto de las páginas con la búsqueda que estamos realizando. Para poder obtener una ordenación mejor debemos introducir componentes más “subjetivos”, como por ejemplo el número de enlaces que apunta a determinada página web. Cuantos más enlaces hacia nuestra página mayor será nuestra puntuación (Con ciertas restricciones importantes que veremos a continuación).

Veamos la fórmula básica (No os asustéis que es muy sencillita) con la que se calcula la puntuación (PageRank) de una página web:

• -PR(A) significa que vamos a calcular el PageRank de la web A.
• -T1, T2, T3 … Tn son las páginas web que tienen un link hacia la página web A.
• -d es una constante que suele vale 0.85
• -C(T1), C(T2), C(T3) … C(Tn) son el número de links al exterior de las webs T1,T2,T3 etc…

Vemos que la fórmula tiene en cuenta el PageRank que cada página que nos apunta, además, cuantos más enlaces al exterior tiene la página que nos apunta menor es la puntuación que nos da. Teóricamente la fórmula calcula la probabilidad de que un usuario llegue a tu página navegando haciendo clicks aleatoriamente, cuantos más enlaces hacia tu página más probable es que llegue un navegante despistado. Pero será aún más probable si hay enlaces a tu página desde una web famosa con mucho PageRank. Para verlo más claro vamos a utilizar un ejemplo, imaginaros las siguientes webs:

-Página Web A (PageRank = ¿?¿?)
-Página Web T1 (PageRank = 5):
   -Link hacia A.
   -Link a slashdot
   -Link a barrapunto
   -Link a la nasa
-Página Web T2 (PageRank=3):
   -Link hacia A
   -Link a google

Deseamos conocer el valor del PageRank de la Web A y ver si nos beneficia más la Web T1 o la Web T2. Procedemos a aplicar la fórmula:

PageRank(A)=(1-0.85) + 0.85*(PageRank(T1)/C(T1)) + 0.85*(PageRank(T2)/C(T2))

Nos falta saber C(T1) y C(T2) que simplemente se calculan sumando el número de links al exterior de ambas páginas, C(T1)=4 y C(T2)=2.

PageRank(A)=(1-0.85) + 0.85*(5/4) + 0.85*(3/2)

PageRank(A)=(1-0.85) + 1 + 1.275

Observad que la página T2 con PageRank 3 nos beneficia algo más que T1 con PageRank 5 porque no tiene tantos links al exterior. Si terminamos de operar obtenemos nuestra puntuación final:

PageRank(A)=2.425=2(Redondeando hacia abajo)

Ya sabemos calcular el PageRank a mano (Algo bastante inútil, aquí te lo calculan automáticamente), pero ¿Qué conclusión práctica podemos sacar de la fórmula? Veámoslo con un par de ejemplos prácticos:

- Si tenemos una web con PageRank 2 y nos enlazan 20 nuevas páginas con PageRank 1 seguramente sigamos con PageRank 2, pero si hay una web que nos enlaza con PageRank 6 seguro que subiremos a PageRank 3. Cuanto mayor sea el PageRank de la web que nos enlaza mayor es la puntuación que nos da.

-Si tenemos una web con PageRank 2 y nos enlaza una web con PageRank 3 que tiene enlaces a otras 5000 webs seguramente sigamos con PageRank 2, pero si la misma web solo tiene nuestro enlace seguro que subiremos a PageRank 3. Cuanto menos enlaces al exterior tenga la web que nos enlaza mayor es la puntuación que nos da.

Hoy en día el algoritmo para calcular el PageRank es mucho más complicado que el explicado y tiene en cuenta muchas más variables para dar puntuaciones lo más fiables posibles. Pero la base sigue siendo parecida a la fórmula de este artículo. ¿Cómo mejoraríais la fórmula del PageRank? ¿Qué factores creéis que son importantes a la hora de evaluar una web de forma automática?

Más información en los papers orginales escritos por los creadores de Google en The Anatomy of a large-scale hypertextual Web search engine y The PageRank citation ranking: Bringing order to the Web.

Fuente: Kirai Bitácoras