¿Qué algoritmos probados y verdaderos existen para sugerir artículos relacionados?

Question

Situación bastante común, apuesto.Tienes un blog o sitio de noticias y tienes muchos artículos o blogs o como los llames, y quieres, al final de cada uno, sugerir otros que parecen estar relacionados.

Supongamos muy pocos metadatos sobre cada elemento.Es decir, sin etiquetas, categorías.Trátelo como una gran masa de texto, incluido el título y el nombre del autor.

¿Cómo se pueden encontrar los documentos posiblemente relacionados?

Estoy más bien interesado en el algoritmo real, no en soluciones listas, aunque estaría bien echar un vistazo a algo implementado en Ruby o Python, o confiar en MySQL o PGSQL.

editar: La respuesta actual es bastante buena, pero me gustaría ver más.Tal vez algún código de ejemplo realmente básico para un par de cosas.

Answer 1

Este es un tema bastante amplio: además de las respuestas que la gente encuentra aquí, recomiendo buscar el programa de estudios de un par de clases de recuperación de información y consultar los libros de texto y los trabajos asignados para ellas.Dicho esto, aquí hay una breve descripción de mis días en la escuela de posgrado:

El enfoque más simple se llama bolsa de palabras.Cada documento se reduce a un vector disperso de {word: wordcount} pares, y puede lanzar un clasificador NaiveBayes (o algún otro) al conjunto de vectores que representa su conjunto de documentos, o calcular puntuaciones de similitud entre cada bolsa y todas las demás bolsas (esto se llama clasificación k-vecino más cercano).KNN es rápido para la búsqueda, pero requiere almacenamiento O(n^2) para la matriz de puntuación;sin embargo, para un blog, n no es muy grande.Para algo del tamaño de un periódico grande, KNN rápidamente se vuelve poco práctico, por lo que a veces es mejor un algoritmo de clasificación sobre la marcha.En ese caso, podría considerar un máquina de vectores de soporte de clasificación.Las SVM son interesantes porque no lo limitan a medidas de similitud lineal y aún así son bastante rápidas.

Derivado es un paso de preprocesamiento común para técnicas de bolsa de palabras;Esto implica reducir palabras relacionadas morfológicamente, como "gato" y "gatos", "Bob" y "Bob's", o "similar" y "similarmente", hasta sus raíces antes de calcular la bolsa de palabras.Existen muchos algoritmos de derivación diferentes;la página de Wikipedia tiene enlaces a varias implementaciones.

Si la similitud de la bolsa de palabras no es lo suficientemente buena, puede abstraerla en una capa hasta la similitud de la bolsa de N gramos, donde crea el vector que representa un documento basado en pares o triples de palabras.(Puede usar 4 tuplas o incluso tuplas más grandes, pero en la práctica esto no ayuda mucho). Esto tiene la desventaja de producir vectores mucho más grandes y, en consecuencia, la clasificación requerirá más trabajo, pero las coincidencias que obtenga serán mucho más cercanas. sintácticamente.OTOH, probablemente no necesites esto por similitud semántica;es mejor para cosas como la detección de plagio. fragmentación, También se puede utilizar , o reducir un documento a árboles de análisis ligeros (existen algoritmos de clasificación para árboles), pero esto es más útil para cosas como el problema de autoría ("dado un documento de origen desconocido, ¿quién lo escribió?") .

Quizás más útil para su caso de uso sea la minería de conceptos, que implica asignar palabras a conceptos (usando un diccionario de sinónimos como WordNet), luego clasificando los documentos según la similitud entre los conceptos utilizados.Esto a menudo termina siendo más eficiente que la clasificación de similitudes basada en palabras, ya que el mapeo de palabras a conceptos es reductivo, pero el paso de preprocesamiento puede llevar bastante tiempo.

Finalmente, hay análisis del discurso, que implica analizar documentos según su estructura semántica;puede ejecutar clasificadores de similitud en árboles de discurso de la misma manera que lo hace en documentos fragmentados.

Casi todos ellos implican generar metadatos a partir de texto no estructurado;Hacer comparaciones directas entre bloques de texto sin procesar es intratable, por lo que la gente preprocesa los documentos primero en metadatos.

Answer 2

Este es un caso típico de Clasificación de documentos que se estudia en todas las clases de Machine Learning.Si te gusta la estadística, las matemáticas y la informática, te recomiendo que eches un vistazo a los métodos no supervisados ​​como km significa ++, métodos bayesianos y LDA.En particular, los métodos bayesianos son bastante bien En cuanto a lo que estás buscando, su único problema es que son lentos (pero a menos que tengas un sitio muy grande, eso no debería molestarte mucho).

Desde un enfoque más práctico y menos teórico, te recomiendo que eches un vistazo a este y este otro excelentes ejemplos de código.

Answer 3

¡Debería leer el libro "Programming Collective Intellective: Building Smart Web 2.0 Aplicaciones" (ISBN 0596529325)!

Para algún método y código: Pregúntese primero, si desea encontrar similitudes directas basadas en coincidencias de palabras, o si desea mostrar artículos similares que pueden no relacionarse directamente con el actual, pero pertenecer al mismo grupo de artículos.

Ver Análisis de clúster / agrupación particionada.

Un método muy simple (pero teórico y lento) para encontrar directo Las similitudes serían:

Preprocesos:

1. Almacene la lista de palabras planas por artículo (no elimine las palabras duplicadas).
2. "Cross unirse" los artículos: Cuente el número de palabras en el artículo A que coincida con las mismas palabras en el artículo B. Ahora tiene una matriz int word_matches[narticles][narticles] (No debe almacenarlo así, la similitud de A-> B es la misma que B-> A, por lo que una matriz escasa ahorra casi la mitad del espacio).
3. Normalice los recuentos de Word_Matches para alcanzar 0..1! (Encuentre el recuento máximo, luego divida cualquier recuento por esto) - Debe almacenar flotadores allí, no ints;)

Encuentra artículos similares:

1. Seleccione los artículos X con coincidencias más altas de Word_Matches

Answer 4

Un pequeño motor de búsqueda de modelo de vector vectorial en Ruby. La idea básica es que dos documentos están relacionados si contienen las mismas palabras. Por lo tanto, contamos la ocurrencia de palabras en cada documento y luego calculamos el coseno entre estos vectores (cada términos tiene un índice fijo, si parece que hay un 1 en ese índice, si no un cero). El coseno será 1.0 si dos documentos tienen todos los términos comunes, y 0.0 si no tienen términos comunes. Puede traducirlo directamente al % valores.

terms = Hash.new{|h,k|h[k]=h.size}
docs = DATA.collect { |line| 
  name = line.match(/^\d+/)
  words = line.downcase.scan(/[a-z]+/)
  vector = [] 
  words.each { |word| vector[terms[word]] = 1 }
  {:name=>name,:vector=>vector}
}
current = docs.first # or any other
docs.sort_by { |doc| 
  # assume we have defined cosine on arrays
  doc[:vector].cosine(current[:vector]) 
}
related = docs[1..5].collect{|doc|doc[:name]}

puts related

__END__
0 Human machine interface for Lab ABC computer applications
1 A survey of user opinion of computer system response time
2 The EPS user interface management system
3 System and human system engineering testing of EPS
4 Relation of user-perceived response time to error measurement
5 The generation of random, binary, unordered trees
6 The intersection graph of paths in trees
7 Graph minors IV: Widths of trees and well-quasi-ordering
8 Graph minors: A survey

la definición de Array#cosine se deja como un ejercicio para el lector (debería lidiar con valores nulos y diferentes longitudes, pero bien para eso tenemos Array#zip ¿Correcto?)

Por cierto, los documentos de ejemplo son tomados del documento SVD por Deerwester Etal :)

Answer 5

Some time ago I implemented something similiar. Maybe this idea is now outdated, but I hope it can help.

I ran a ASP 3.0 website for programming common tasks and started from this principle: user have a doubt and will stay on website as long he/she can find interesting content on that subject.

When an user arrived, I started an ASP 3.0 Session object and recorded all user navigation, just like a linked list. At Session.OnEnd event, I take first link, look for next link and incremented a counter column like:

<Article Title="Cookie problem A">
    <NextPage Title="Cookie problem B" Count="5" />
    <NextPage Title="Cookie problem C" Count="2" />
</Article>

So, to check related articles I just had to list top n NextPage entities, ordered by counter column descending.