algorithm - metodos - ¿El mejor algoritmo de agrupamiento?(simplemente explicado)

clustering jerarquico

Question

Imagina el siguiente problema:

• Tiene una base de datos que contiene aproximadamente 20,000 textos en una tabla llamada "artículos"
• Desea conectar los relacionados utilizando un algoritmo de agrupamiento para mostrar artículos relacionados juntos
• El algoritmo debe hacer clustering plano (no jerárquico)
• Los artículos relacionados deben ser insertados en la tabla "relacionados"
• El algoritmo de agrupación 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 pseudo có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 (selección de los artículos de la base de datos, selección de artículos para comparar, inserción de los relacionados) también está completo. Quizás tú también puedas mejorar el resto. Pero el punto principal que es importante para mí es la función check (). Así que sería genial 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 [solo cheque ()]

<?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 agrupar en clústeres, pero en cada sitio solo hay una descripción matemática que es un poco difícil de entender para mí. Por lo tanto, los ejemplos de codificación en (pseudo) código serían excelentes.

Espero que puedas ayudarme. ¡Gracias por adelantado!

Answer 1

¿Cómo se similar_text función similar_text llamada en el Enfoque # 1? Creo que a lo que te refieres no es a la agrupación, sino a una métrica de similitud. Realmente no puedo mejorar el enfoque del histograma :-) de White Walloun: un problema interesante para leer.

Sin embargo, si implementas check() , debes usarlo para hacer al menos 200M de comparación (la mitad de 20000^2 ). El límite para los artículos "relacionados" puede limitar lo que almacena en la base de datos, pero parece demasiado arbitrario para capturar todo el agrupamiento útil de textos,

Mi enfoque sería modificar check() para devolver la métrica de "similitud" ( $prozent o rtn ). Escriba la matriz de 20K x 20K en un archivo y use un programa externo para realizar un agrupamiento en clústeres para identificar a los vecinos más cercanos para cada artículo, que podría cargar en la tabla related . Haría el agrupamiento en R - hay un buen tutorial para agrupar datos en un archivo que ejecuta R desde php .

Answer 2

Creo que necesita tomar algunas decisiones de diseño sobre el agrupamiento y continuar desde allí:

1. ¿Por qué estás agrupando textos? ¿Desea mostrar documentos relacionados juntos? ¿Quieres explorar tu corpus de documentos a través de grupos?
2. Como resultado, ¿desea agrupación flat o hierarchical ?
3. Ahora tenemos el problema de la complejidad, en dos dimensiones: primero, la cantidad y el tipo de funciones que crea a partir del texto: las palabras individuales pueden sumar decenas de miles. Es posible que desee probar alguna selección de funciones , como tomar las N palabras más informativas o las N palabras que aparecen la mayoría de las veces, después de ignorar las palabras de parada .
4. En segundo lugar, desea minimizar el número de veces que mide la similitud entre documentos. Como señala correctamente Bubaker, la verificación de la similitud entre todos los pares de documentos puede ser demasiado. Si la agrupación en un pequeño número de agrupaciones es suficiente, puede considerar la agrupación en K-medias , que básicamente consiste en elegir un K inicial como centros de agrupación, asignar cada documento a la agrupación más cercana, recalcular los centros de agrupación encontrando medios vectoriales de documentos y iterar. Esto solo cuesta K * número de documentos por iteración. Creo que también hay heurísticas para reducir el número necesario de cálculos para el agrupamiento jerárquico también.

Answer 3

La forma más estándar que conozco para hacer esto en datos de texto como lo ha hecho usted, es usar la técnica ''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 va a ser un vector (Array, Lista, Lo que sea) de tamaño 500, donde los datos son el número de veces que aparece cada palabra en el artículo. Entonces, si el primer punto en el vector representa la palabra ''preguntado'', y esa palabra apareció 5 veces en el artículo, el vector [0] sería 5:

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

Ahora, para comparar cualquiera de los dos artículos, 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 hace que sea un poco más fácil)

Esta es la idea básica. Observe que el valor de umbral es semi-arbitrario; probablemente querrá encontrar una buena manera de normalizar el producto de puntos de sus histogramas (esto casi tendrá que tener en cuenta la longitud del artículo en algún lugar) y decidir qué considera "relacionado".

Además, no solo debes poner cada palabra en tu histograma. En general, querrá incluir los que se usan con frecuencia: no en todos los artículos ni en un solo artículo. Esto le ahorra un poco de sobrecarga en su histograma y aumenta el valor de sus relaciones.

Por cierto, esta técnica se describe con más detalle here

Answer 4

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

Si desea mostrar artículos similares , utilice la búsqueda de similitud en su lugar .

Para artículos de texto, esto es bien entendido. Simplemente inserte sus artículos en una base de datos de búsqueda de texto como Lucene, y use su artículo actual como consulta de búsqueda. En Lucene, existe una consulta llamada MoreLikeThis que realiza exactamente esto: encuentra artículos similares.

La agrupación es la herramienta incorrecta, porque (en particular con sus requisitos), cada artículo debe incluirse en alguna agrupación; y los elementos relacionados serían los mismos para cada objeto en el clúster. Si hay valores atípicos en la base de datos, un caso muy probable, podrían arruinar su agrupamiento. Además, los grupos pueden ser muy grandes . No hay restricción de tamaño, el algoritmo de agrupación puede decidir poner la mitad de su conjunto de datos en la misma agrupación. Así que tienes 10000 artículos relacionados para cada artículo en tu base de datos. Con la búsqueda de similitud, ¡puede obtener los 10 artículos similares para cada documento!

Por último, pero no menos importante: olvídate de PHP para la agrupación. No está diseñado para esto, y no es lo suficientemente ejecutante. Pero probablemente puedas acceder a un índice de Lucene desde PHP lo suficientemente bien.