¿Qué algoritmos probados y verdaderos para sugerir artículos relacionados están por ahí?

Question

Situación bastante común, apostaría. Usted tiene un blog o sitio de noticias y tiene muchos artículos o blags o como quiera que los llame, y desea, al pie de cada uno, sugerir otros que parezcan estar relacionados.

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

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

Estoy bastante interesado en el algoritmo real, las soluciones no listas, aunque estaría bien si echara un vistazo a algo implementado en ruby ​​o python, o confiando en mysql o pgsql.

editar: la respuesta actual es bastante buena, pero me gustaría ver más. Tal vez algunos realmente muestran un código de ejemplo para una cosa o dos.

Answer 1

Este es un tema bastante importante: además de las respuestas que las personas presentan aquí, les recomiendo buscar un par de clases de recuperación de información y revisar los libros de texto y los documentos asignados para ellos. Dicho esto, aquí hay una breve descripción de mis propios días de graduación:

El enfoque más simple se llama bag of words. Cada documento se reduce a un vector disperso de {word: wordcount} pares, y puede lanzar un clasificador NaiveBayes (u otro) en el conjunto de vectores que representa su conjunto de documentos, o calcular puntajes de similitud entre cada bolsa y cada otra bolsa (esto es llamada clasificación k-vecino más cercano). KNN es rápido para la búsqueda, pero requiere O (n^2) almacenamiento para la matriz de puntaje; 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 un algoritmo de clasificación sobre la marcha es a veces mejor. En ese caso, puede considerar un ranking support vector machine. Las SVM son ordenadas porque no te limitan a medidas de similitud lineal, y aún son bastante rápidas.

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

Si la similitud de palabras no es lo suficientemente buena, puedes resumirla en una capa para similitud de bolsa de N gramos, donde creas el vector que representa un documento basado en pares o triples de palabras . (Puedes 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 la clasificación en consecuencia requerirá más trabajo, pero las coincidencias que obtengas estarán mucho más cerca. sintácticamente OTOH, probablemente no necesites esto para similitud semántica; es mejor para cosas como la detección de plagio. Chunking, o reducir un documento a árboles de análisis ligeros, también se puede usar (hay 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 es la minería de conceptos, que consiste en asignar palabras a los conceptos (utilizando un diccionario de sinónimos como WordNet) y luego clasificar 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 consumir bastante tiempo.

Finalmente, está discourse parsing, que implica el análisis de documentos para su estructura semántica; puede ejecutar clasificadores de similitud en árboles de discursos de la misma manera que puede hacerlo en documentos fragmentados.

Casi todos implican la generación de metadatos a partir de texto no estructurado; hacer comparaciones directas entre los bloques de texto sin formato es insoluble, por lo que las personas preprocesan documentos en metadatos primero.

Answer 2

Hace algún tiempo implementé algo similar. Tal vez esta idea ahora está desactualizada, pero espero que pueda ayudar.

Ejecuté un sitio web ASP 3.0 para programar tareas comunes y comencé desde este principio: el usuario tiene una duda y permanecerá en el sitio web siempre que pueda encontrar contenido interesante sobre ese tema.

Cuando llegó un usuario, inicié un objeto ASP 3.0 Session y grabé toda la navegación del usuario, al igual que una lista vinculada. En Session.OnEnd caso, tomo primer enlace, mira para el próximo enlace e incrementado una columna de contador como:

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

Así, para comprobar artículos relacionados sólo tenía al inicio nNextPage entidades, ordenados por el contador descendente columna .

Answer 3

Este es un caso típico de Document Classification que se estudia en todas las clases de Machine Learning. Si le gustan las estadísticas, las matemáticas y la informática, le recomiendo que eche un vistazo a los métodos no supervisados ​​como kmeans++, Bayesian methods y LDA. En particular, los métodos Bayesianos son pretty good en lo que estás buscando, su único problema es ser lento (pero a menos que ejecutes un sitio muy grande, eso no debería molestarte demasiado).

En un enfoque más práctico y menos teórico, le recomiendo que eche un vistazo a this y this other excelentes ejemplos de código.

Answer 4

Un pequeño motor de búsqueda de vector-espacio-modelo en Ruby. La idea básica es que dos documentos están relacionados si contienen las mismas palabras. Entonces contamos la ocurrencia de palabras en cada documento y luego calculamos el coseno entre estos vectores (cada término tiene un índice fijo, si aparece hay un 1 en ese índice, si no un cero). Coseno será 1.0 si dos documentos tienen todos los términos comunes, y 0.0 si no tienen términos comunes. Puedes traducirlo directamente a% values.

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 ejercicio para el lector (debe hacer frente a los valores nulos y diferentes longitudes, sino también para los que tenemos Array#zip ¿verdad?)

Por cierto, se toman los documentos de ejemplo del documento SVD de Deerwester etal :)

Answer 5

Debería leer el libro "Programación de la inteligencia colectiva: creación de aplicaciones Web 2.0 inteligentes" (ISBN 0596529325).

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

Ver Cluster analysis/Partitional clustering.

Un método muy simple (pero teórica y lento) para encontrar similitudes directa sería:

preproceso:

1. tienda lista de palabras plana por artículo (no quite palabras duplicadas).
2. "Unir" los artículos: cuente el número de palabras en el artículo A que coincidan con las mismas palabras en el artículo B. Ahora tiene una matriz int word_matches[narticles][narticles] (no debe almacenarla así, la similitud de A-> B es igual a B -> A, entonces una matriz dispersa ahorra casi la mitad del espacio).
3. ¡Normalice los conteos de word_matches al rango 0..1! (Encontrar recuento máximo, luego dividir cualquier conteo por esto) - usted debe almacenar los flotadores allí, no enteros;)

Buscar artículos similares:

1. selecciona los artículos X con más partidos de word_matches