¿El mejor algoritmo de agrupamiento?(explicado simplemente)

https://stackoverflow.com/questions/853139

21-08-2019
|

Pregunta

Imagine el siguiente problema:

Dispones de una base de datos que contiene unos 20.000 textos en una tabla llamada "artículos"
Desea conectar los relacionados mediante un algoritmo de agrupación para mostrar artículos relacionados juntos
El algoritmo debe realizar una agrupación plana (no jerárquica)
Los artículos relacionados deben insertarse en la tabla "relacionados".
El algoritmo de agrupamiento debe decidir si dos o más artículos están relacionados o no en función de los textos.
Quiero codificar en PHP, pero los ejemplos con pseudocódigo u otros lenguajes de programación también están bien.

He codificado un primer borrador con una función check() que da "verdadero" si los dos artículos de entrada están relacionados y "falso" si no.El resto del código (seleccionar los artículos de la base de datos, seleccionar artículos para comparar, insertar los relacionados) también está completo.Quizás puedas mejorar el resto también.Pero el punto principal que es importante para mí es la función check().Sería fantástico si pudieras publicar algunas mejoras o enfoques completamente diferentes.

ENFOQUE 1

<?php
$zeit = time();
function check($str1, $str2){
    $minprozent = 60;
    similar_text($str1, $str2, $prozent);
    $prozent = sprintf("%01.2f", $prozent);
    if ($prozent > $minprozent) {
        return TRUE;
    }
    else {
        return FALSE;
    }
}
$sql1 = "SELECT id, text FROM articles ORDER BY RAND() LIMIT 0, 20";
$sql2 = mysql_query($sql1);
while ($sql3 = mysql_fetch_assoc($sql2)) {
    $rel1 = "SELECT id, text, MATCH (text) AGAINST ('".$sql3['text']."') AS score FROM articles WHERE MATCH (text) AGAINST ('".$sql3['text']."') AND id NOT LIKE ".$sql3['id']." LIMIT 0, 20";
    $rel2 = mysql_query($rel1);
    $rel2a = mysql_num_rows($rel2);
    if ($rel2a > 0) {
        while ($rel3 = mysql_fetch_assoc($rel2)) {
            if (check($sql3['text'], $rel3['text']) == TRUE) {
                $id_a = $sql3['id'];
                $id_b = $rel3['id'];
                $rein1 = "INSERT INTO related (article1, article2) VALUES ('".$id_a."', '".$id_b."')";
                $rein2 = mysql_query($rein1);
                $rein3 = "INSERT INTO related (article1, article2) VALUES ('".$id_b."', '".$id_a."')";
                $rein4 = mysql_query($rein3);
            }
        }
    }
}
?>

ENFOQUE 2 [sólo comprobar()]

<?php
function square($number) {
    $square = pow($number, 2);
    return $square;
}
function check($text1, $text2) {
    $words_sub = text_splitter($text2); // splits the text into single words
    $words = text_splitter($text1); // splits the text into single words
    // document 1 start
    $document1 = array();
    foreach ($words as $word) {
        if (in_array($word, $words)) {
            if (isset($document1[$word])) { $document1[$word]++; } else { $document1[$word] = 1; }
        }
    }
    $rating1 = 0;
    foreach ($document1 as $temp) {
        $rating1 = $rating1+square($temp);
    }
    $rating1 = sqrt($rating1);
    // document 1 end
    // document 2 start
    $document2 = array();
    foreach ($words_sub as $word_sub) {
        if (in_array($word_sub, $words)) {
            if (isset($document2[$word_sub])) { $document2[$word_sub]++; } else { $document2[$word_sub] = 1; }
        }
    }
    $rating2 = 0;
    foreach ($document2 as $temp) {
        $rating2 = $rating2+square($temp);
    }
    $rating2 = sqrt($rating2);
    // document 2 end
    $skalarprodukt = 0;
    for ($m=0; $m<count($words)-1; $m++) {
        $skalarprodukt = $skalarprodukt+(array_shift($document1)*array_shift($document2));
    }
    if (($rating1*$rating2) == 0) { continue; }
    $kosinusmass = $skalarprodukt/($rating1*$rating2);
    if ($kosinusmass < 0.7) {
        return FALSE;
    }
    else {
        return TRUE;
    }
}
?>

También me gustaría decir que sé que hay muchos algoritmos para la agrupación, pero en cada sitio solo hay una descripción matemática, lo cual me resulta un poco difícil de entender.Por lo tanto, codificar ejemplos en (pseudo) código sería genial.

Espero que puedas ayudarme.¡Gracias de antemano!

Solución

La forma más estándar que conozco de hacer esto con datos de texto como los suyos es utilizar la técnica de la "bolsa de palabras".

Primero, cree un 'histograma' de palabras para cada artículo.Digamos que entre todos tus artículos, solo tienes 500 palabras únicas entre ellos.Entonces este histograma será un vector (matriz, lista, lo que sea) de tamaño 500, donde los datos son la cantidad de veces que aparece cada palabra en el artículo.Entonces, si el primer punto en el vector representara la palabra "preguntado" y esa palabra apareciera 5 veces en el artículo, el vector [0] sería 5:

for word in article.text
    article.histogram[indexLookup[word]]++

Ahora bien, comparar dos artículos cualesquiera es bastante sencillo.Simplemente multiplicamos los dos vectores:

def check(articleA, articleB)
    rtn = 0
    for a,b in zip(articleA.histogram, articleB.histogram)
        rtn += a*b
    return rtn > threshold

(Perdón por usar Python en lugar de PHP, mi PHP está oxidado y el uso de zip lo hace un poco más fácil)

Esta es la idea básica.Observe que el valor umbral es semiarbitrario;probablemente querrás encontrar una buena manera de normalizar el producto escalar de tus histogramas (esto casi tendrá que tener en cuenta la longitud del artículo en alguna parte) y decidir qué consideras "relacionado".

Además, no deberías simplemente poner cada palabra en tu histograma.En general, querrás incluir los que se usan con poca frecuencia:No en todos los artículos ni en uno solo.Esto le ahorra un poco de gastos generales en su histograma y aumenta el valor de sus relaciones.

Por cierto, esta técnica se describe con más detalle. aquí

Otros consejos

Tal vez agrupación es la estrategia equivocada aquí?

Si desea mostrar los artículos, utilizar búsqueda de similitud en lugar .

Para artículos de texto, esto se entiende bien. Sólo tiene que insertar sus artículos en una base de datos de búsqueda de texto como Lucene, y utilizar su artículo actual como consulta de búsqueda. En Lucene, existe una de consulta llamado MoreLikeThis que realiza exactamente esto:. encontrar artículos similares

La agrupación es la herramienta equivocada, porque (en particular, con sus requisitos), todos artículo debe ser puesto en alguna agrupación; y los artículos relacionados serían los mismos para cada objeto de la agrupación. Si hay valores atípicos en la base de datos - un caso muy probable - que podría arruinar su agrupación. Por otra parte, los grupos pueden ser muy grande . No hay ninguna restricción de tamaño, el algoritmo de agrupamiento puede decidir poner la mitad de su conjunto de datos en el mismo grupo. Así que hay 10000 artículos relacionados para cada artículo en su base de datos. Con la búsqueda de similitud, se puede obtener sólo los 10 primeros artículos similares para cada documento!

Por último, pero no menos importante: se olvide de PHP para el agrupamiento. No está diseñado para esto, y no lo suficiente performant. Sin embargo, es probable que pueda acceder a un índice de Lucene desde PHP lo suficientemente bien.

Creo que es necesario hacer algunas decisiones de diseño sobre la agrupación, y continuar desde allí:

¿Por qué está aglomerando textos? ¿Quieres mostrar documentos relacionados juntos? ¿Quieres explorar su documento corpus a través de grupos?
Como resultado de ello, ¿desea plana o agrupamiento jerárquico ?
Ahora tenemos el problema de la complejidad, en dos dimensiones: en primer lugar, el número y tipo de funciones se crea a partir del texto - las palabras individuales pueden contarse por decenas de miles. Es posible que desee probar algunos selección de características - tales como tomar las palabras más informativos N, o el N palabras que aparecen la mayoría de las veces, después de ignorar dejan de palabras .
En segundo lugar, desea reducir al mínimo el número de veces que medida de similitud entre documentos. Como bubaker señala correctamente, comprobando similitud entre todos los pares de documentos puede ser demasiado. Si la agrupación en un pequeño número de grupos es suficiente, se puede considerar K- significa agrupación, que es básicamente: elegir un K documentos iniciales como centros de grupo, asignar a cada documento al grupo más cercano, volver a calcular los centros de conglomerados mediante la búsqueda de medios documento de vector, e iterar. Esto sólo cuesta número K * de documentos por iteración. Creo que también son heurísticas para reducir el número necesario de cálculos para la agrupación jerárquica también.

Lo que hace la función de llamada en similar_text Enfoque # 1 parece? Creo que lo que usted se refiere no es la agrupación, pero una métrica de similitud. Realmente no puedo mejorar el enfoque :-) histograma de la Walloun Blanco -. Un problema interesante para leer un poco sobre

Sin embargo se implementa check(), tienes que usarlo para hacer al menos 200M comparaciones (la mitad de 20000^2). El punto de corte para artículos "relacionadas" puede limitar lo que se almacena en la base de datos, pero parece demasiado arbitraria para coger toda la agrupación útil de los textos,

Mi enfoque sería modificar $prozent para devolver la "similitud" métrica (rtn o 20K x 20K). Escribir el related matriz a un archivo y utilizar un programa externo para realizar una agrupación para identificar los vecinos más cercanos para cada artículo, que se podría cargar en la tabla R. Haría la agrupación en php - hay un buen tutorial para agrupar datos en un archivo de ejecución <=> <=>.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow