Algoritmo HITS

El algoritmo HITS ( Hyperlink Induced Topic Search ), propuesto en 1999 por John Kleinberg , permite encontrar páginas de Internet que coincidan con la consulta del usuario a partir de la información contenida en los hipervínculos [1] .

La métrica HITS se usa a menudo para responder consultas de temas amplios y encontrar comunidades de documentos ( por ejemplo, Tightly -Knit Community ), en Internet . La idea del algoritmo se basa en la suposición de que los hipervínculos codifican un número significativo de páginas de autoridad ocultas [2] .

Un documento autorizado (página autorizada, autor) es un documento correspondiente a la solicitud del usuario, teniendo una mayor participación entre los documentos de este tema, es decir, una mayor cantidad de documentos se refieren a este documento [1] .

Un documento central (página central, intermediario) es un documento que contiene muchos enlaces a documentos autorizados.

La página a la que enlazan muchos otros puntos debe ser un buen "autor". A su vez, una página que apunta a muchas otras debería ser un buen “intermediario”. En base a esto, el algoritmo HITS calcula dos puntuaciones para cada página web : una puntuación de autoridad y una puntuación de intermediario. Es decir, para cada página, su significado como "autor" e "intermediario" se calcula recursivamente [3] [4] .

Algoritmo

El primer paso en el algoritmo HITS es obtener las páginas más relevantes en la consulta de búsqueda . Este conjunto se denomina conjunto raíz y se puede obtener tomando las n páginas más populares devueltas por el algoritmo de búsqueda de texto. El conjunto base se forma incrementando el conjunto raíz con todas las páginas web que están vinculadas a él y algunas de las páginas que lo vinculan. Las páginas web del conjunto base y todos los hipervínculos entre esas páginas forman un subgráfico agrupado. Los cálculos de HITS se realizan solo en este subgráfico.

Las puntuaciones del documento de autoridad y del mediador se definen en términos mutuos en recursividad mutua . La puntuación de autoridad de una página se calcula como la suma de las puntuaciones de las páginas proxy que apuntan a esa página. El valor de la puntuación del revendedor se calcula como la suma de las puntuaciones de las páginas autorizadas a las que apunta.

El algoritmo realiza una serie de iteraciones , cada una de las cuales consta de dos pasos principales:

Actualización de autoridad . Una actualización de la puntuación de autoridad de cada vértice en el subgrafo, equivalente a la suma de las puntuaciones de proxy de cada uno de los vértices que apuntan a ellos.
Actualización del concentrador . Actualizar la puntuación de proxy de cada vértice en el subgrafo sumando las puntuaciones autorizadas de cada uno de los vértices a los que apuntan.

La puntuación de autoridad y la puntuación de mediación para un vértice se calculan utilizando el siguiente algoritmo:

Comience con vértices cuyo puntaje de autoridad y puntaje de proxy sea 1.
Ejecución de la regla de actualización de autoridad.
Ejecute una regla de actualización de concentrador.
Normalización de valores dividiendo cada puntaje de proxy por la raíz cuadrada de la suma de cuadrados de todos los puntajes de proxy, y dividiendo cada puntaje de autoridad por la raíz cuadrada de la suma de cuadrados de todos los puntajes de credibilidad.
Repita desde el paso dos según sea necesario.

Detallado

Para comenzar a clasificar, , y . Considere dos tipos de actualizaciones: una regla de actualización de autoridad y una actualización de concentrador. Se aplican iteraciones repetidas de las reglas de actualización de autoridad y actualización de concentrador para calcular las puntuaciones de autoridad/representante . El paso k de aplicar el algoritmo implica aplicar la primera regla de actualización de autoridad k veces y luego la regla de actualización de concentrador. $\para todos p$ ${\mathrm {autorización}}(p)=1$ ${\mathrm {hub}}(p)=1$

Regla de actualización de autoridad

$\para todos p$ , obtenemos = donde n es el número total de páginas vinculadas a p e i es la página vinculada a p. Así, la puntuación de autoridad de una página se calcula como la suma de los valores de puntuación de las páginas intermedias que apuntan a esa página. ${\mathrm {autorización}}(p)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {hub}}(i)$

La regla de actualización del concentrador

$\para todos p$ , obtenemos = donde n es el número total de páginas a las que apunta p e i es la página a la que apunta p. Por lo tanto, la puntuación de proxy de una página se calcula como la suma de las puntuaciones de autoridad de las páginas a las que enlaza. ${\mathrm {hub}}(pag)$ $\displaystyle \sum _{{i=1}}^{n}{\mathrm {autorización}}(i)$

En función de estos valores, se calcula la importancia de las páginas web para una solicitud en particular y luego se muestra al usuario. El módulo HITS Rank calcula el rango de una página web sin conexión después de que se hayan descargado y almacenado en una base de datos local. [5]

Normalización

Las puntuaciones de los vértices finales se determinan después de una repetición infinita del algoritmo. La aplicación directa y coherente de las reglas de actualización de centro y actualización de autoridad da como resultado valores divergentes que la matriz debe normalizar después de cada iteración. Así, los valores obtenidos de este proceso eventualmente convergen.

Algoritmo HITS y PageRank

El algoritmo HITS tiene varias diferencias importantes con el algoritmo PageRank . [6]

El algoritmo HITS no solo calcula el rango de cada nodo, sino que también proporciona una puntuación de proxy.
El algoritmo PageRank contiene un parámetro libre α, que normalmente no se incluye en el algoritmo HITS.
La prioridad, como resultado del trabajo del algoritmo PageRank, tiende a ser los recursos más antiguos, mientras que el algoritmo HITS tiene un sesgo menor en este sentido.
El algoritmo PageRank solo puede encontrar una solución única.

A pesar de las diferencias entre HITS y PageRank, estos algoritmos tienen en común que la autoridad (peso) de un nodo depende del peso de otros nodos, y el nivel del "intermediario" depende de la autoridad de los nodos a los que se refiere.

El cálculo de la autoridad de documentos individuales es ampliamente utilizado hoy en día en aplicaciones tales como la determinación del orden de escaneo de documentos en la red por parte del robot IPS , la clasificación de resultados de búsqueda, la generación de reseñas temáticas, etc.

En la actualidad, se han generalizado las tecnologías para aumentar artificialmente las clasificaciones de documentos web individuales o de sus grupos de sitios web mediante el establecimiento de hipervínculos que no están relacionados con su contenido . Estas tecnologías, que son una variedad poco confiable de métodos SEO de optimización de motores de búsqueda ( Search Engine Optimization ), llamados "black hat" SEO, se basan en la adaptación a algoritmos existentes para clasificar documentos web por los más populares ( motores de búsqueda ).

A su vez, dichas tecnologías generan la necesidad de una mejora continua de los algoritmos de clasificación en los motores de búsqueda, centrándose en el componente de contenido de los documentos web al determinar sus clasificaciones. [cuatro]

Desventajas de HITS

Se han realizado muchas investigaciones para evaluar el algoritmo HITS y se ha demostrado que, si bien el algoritmo funciona bien para la mayoría de las consultas, no funciona para algunas otras. Hay varias razones [7] :

mediadores y autores.

No es apropiado hacer una distinción clara entre "intermediarios" y "autores", ya que muchas páginas intermediarias también son autoras.

Desviación del tema . _ _

Ubicación dominante de algunos documentos estrechamente relacionados temáticamente como resultado del algoritmo HITS. En algunos casos, estos documentos pueden no ser relevantes para la solicitud . En un caso, cuando el elemento de búsqueda era "Jaguar", el algoritmo HITS convergió en un equipo de fútbol llamado Jaguars.

Para resolver este problema, se propuso el algoritmo PHITS [4] como una extensión del algoritmo HITS estándar. En el marco de este algoritmo, se supone: — un conjunto de documentos de citas, — un conjunto de referencias, — un conjunto de clases (factores). También se supone que el evento ocurre con probabilidad . Las probabilidades condicionales y se utilizan para describir las dependencias entre la presencia de un vínculo , un factor latente y un documento . $D$ $C$ $Z$ $d\en {D}$ $P(d)$ $P(c|z)$ $P(z|d)$ $c\en {C}$ $z\in{Z}$ $d\en {D}$

La función de verosimilitud se estima :

L(C|D)=\prod_{{c\in {C},d\in {D))}^{\ }P(d,c)=\prod_{{c\in {C}, d\en {D}}}^{\ }P(d)P(c|d)

P(c|d)=\sum_{{z\in {Z}}}P(c|z)P(z|d)

El objetivo del algoritmo PHITS es ajustar , maximizar . $P(z)$ $P(c|z)$ $P(z|d)$ $L(C|D)$

Después de eso:

P(c|z)

– rangos de "autores";

P(z|d)

– filas de "intermediarios".

Para calcular los rangos, debe especificar el número de factores en el conjunto , y luego caracterizará la calidad de la página como "autor" en el contexto del tema. Las desventajas del método incluyen el hecho de que el proceso iterativo generalmente no se detiene en el máximo absoluto, sino en el máximo local de la función de probabilidad . Sin embargo, en situaciones en las que no existe un dominio claro del tema de consulta en el conjunto de páginas web encontradas, PHITS supera al algoritmo HITS. $Z$ $P(c|z)$ $L$

Enlaces generados automáticamente.

Algunos de los enlaces son generados por computadora, pero el algoritmo HITS aún les da valores iguales.

documentos irrelevantes.

Algunas consultas pueden devolver documentos irrelevantes a un lugar alto en la clasificación, lo que conduce a resultados erróneos del algoritmo HITS.

Notas

↑ 1 2 Krizhanovsky, 2008 , pág. 27
↑ La métrica de HITS, 2005 , p. 55.
↑ Kleinberg, 1999 .
↑ 1 2 3 Algoritmo HITS, 2009 .
↑ Centros y autoridades, 2010 , p. 5.
↑ PageRank y HITS, 2010 , pág. 257.
↑ Problemas con el algoritmo HITS, 2011 , p. 255.

Literatura

Lande D.V., Snarsky A.A., Bezsudnov I.V. Internet. Navegando Redes Complejas: Modelos y Algoritmos . - Librokom, 2009. - 264 p. — ISBN 978-5-397-00497-8 . (Ruso)
Cronin B. Revisión anual de ciencia y tecnología de la información . - 2004. - 674 págs. — ISBN 1573872091 .
Kleinberg J. Fuentes autorizadas en un entorno con hipervínculos . — 1999.
Kleinberg J. El algoritmo HITS: fuentes autorizadas en un entorno de hipervínculos / traducido por S. Neilenko. - 1999. Archivado el 12 de octubre de 2013. (Ruso)
Gupta GK Introducción a la minería de datos con estudios de casos : 2.ª edición . — PHI Learning Pvt. Ltd., 2011. - 491 págs. — ISBN 978-81-203-4326-9 .
Leo JG, Jonathan R.P. Cálculo discreto. Análisis Aplicado a Grafos para Ciencias Computacionales . - Springer, 2010. - 366 págs. - ISBN 978-1-84996-289-6 . (enlace no disponible)
Scime A. Web Mining : Aplicaciones y Técnicas . - Idea Group Inc., 2005. - 433 p. — ISBN 1591404150 .
Krizhanovsky A.A. Tesis doctoral. Herramientas matemáticas y de software para construir listas de palabras cercanas semánticamente basadas en la clasificación de textos wiki . - San Petersburgo. , 2008. - S. 27-30. — 188 pág.
Chandranna AK Versiones en línea del algoritmo de búsqueda de temas inducidos por hipervínculos (HITS) . — 2010.