Le meilleur algorithme de classification? (Simplement expliqué)

Question

Imaginez le problème suivant:

• Vous avez une base de données contenant environ 20 000 textes dans une table appelée « articles »
• Vous voulez connecter ceux liés à l'aide d'un algorithme de classification afin d'afficher les articles liés ensemble
• L'algorithme doit faire le regroupement plat (non hiérarchique)
• Les articles connexes devraient être insérés dans la table "connexe"
• L'algorithme de clustering doit décider si deux ou plusieurs articles sont liés ou non sur la base des textes
• Je veux coder en PHP, mais des exemples avec le code pseudo ou d'autres langages de programmation sont ok aussi

J'ai codé un premier projet avec un chèque de fonction () qui donne « true » si les deux articles d'entrée sont liés et « false » sinon. Le reste du code (sélection des articles de la base de données, sélection des articles à comparer avec, en insérant les associés) est complète, aussi. Peut-être que vous pouvez améliorer le reste aussi. Mais le principal point qui est important pour moi est la vérification de la fonction (). Donc, ce serait génial si vous pouviez poster des améliorations ou des approches complètement différentes.

APPROCHE 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);
            }
        }
    }
}
?>

APPROCHE 2 [uniquement vérifier ()]

<?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;
    }
}
?>

Je voudrais également dire que je sais qu'il ya beaucoup d'algorithmes pour le regroupement mais sur chaque site il n'y a que la description mathématique qui est un peu difficile à comprendre pour moi. Ainsi, des exemples de codage dans le code (pseudo) serait grande.

J'espère que vous pouvez me aider. Merci d'avance!

Answer 1

La façon la plus classique que je connaisse pour ce faire sur des données de texte comme vous, est d'utiliser le «sac de mots de la technique.

Tout d'abord, créer un « histogramme » de mots pour chaque article. Disons entre tous vos articles, vous avez seulement 500 mots uniques entre eux. Ensuite, cet histogramme va être un vecteur (Array, liste, peu importe) de taille 500, où les données sont le nombre de fois où chaque mot apparaît dans l'article. Donc, si la première place dans le vecteur représente le mot « demandé », et ce mot est apparu 5 fois dans l'article, vecteur [0] serait 5:

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

Maintenant, pour comparer deux articles, il est assez simple. Nous multiplions simplement les deux vecteurs:

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

(Désolé pour l'utilisation de python au lieu de PHP, mon PHP est rouillé et l'utilisation de zip fait que peu plus facile)

Ceci est l'idée de base. Notez que la valeur seuil est semi-arbitraire; vous aurez probablement envie de trouver une bonne façon de normaliser le produit scalaire de vos histogrammes (ce sera presque devoir tenir compte de la longueur de l'article quelque part) et de décider ce que vous considérez comme « connexes ».

En outre, vous ne devriez pas simplement mettre chaque mot dans votre histogramme. Vous, en général, à inclure ceux qui sont utilisés fréquemment semi-: Pas dans chaque article, ni dans un seul article. Cela vous permet d'économiser un peu de frais généraux sur votre histogramme, et augmente la valeur de vos relations.

Par ailleurs, cette technique est décrite plus en détail

Answer 2

Peut-être regroupement est une mauvaise stratégie ici

Si vous voulez afficher similaires articles, utiliser recherche de similarité au lieu .

Pour les articles de texte, cela est bien compris. Il suffit d'insérer vos articles dans une base de données de recherche de texte comme Lucene, et utilisez votre article actuel comme requête de recherche. En Lucene, il existe une requête appelée MoreLikeThis qui effectue exactement ceci:. trouver des articles similaires

Clustering est le mauvais outil, parce que (en particulier avec vos besoins), tous article doit être mis en une grappe; et les éléments connexes seraient les mêmes pour tous les objets du cluster. S'il y a des valeurs aberrantes dans la base de données - un cas très probable - ils pourraient ruiner votre regroupement. En outre, grappes peut être très grand . Il n'y a pas de contrainte de taille, l'algorithme de clustering peut décider de mettre la moitié de votre ensemble de données dans le même cluster. Donc, vous avez 10000 articles connexes pour chaque article dans votre base de données. Avec la recherche de similarité, vous pouvez juste obtenir le top 10 articles similaires pour chaque document!

Last but not least: oublier PHP pour le regroupement. Il n'est pas conçu pour cela, et pas assez performant. Mais vous pouvez probablement accéder à un index de Lucene de PHP assez bien.

Answer 3

Je crois que vous avez besoin de prendre des décisions de conception sur le regroupement, et continuer à partir de là:

1. Pourquoi êtes-vous des textes en cluster? Voulez-vous pour afficher les documents liés ensemble? Voulez-vous explorer votre corpus de documents via les clusters?
2. En conséquence, voulez-vous plat ou classification hiérarchique ?
3. Maintenant, nous avons la question de la complexité, en deux dimensions: d'abord, le nombre et le type de fonctionnalités que vous créez à partir du texte - mots peut se chiffrer en dizaines de milliers. Vous pouvez essayer une fonction sélection href="http://en.wikipedia.org/wiki/Feature_selection" - comme prendre les N mots les plus informatifs, ou N mots qui apparaissent le plus temps, après avoir ignoré mots arrêter.
4. Deuxièmement, vous voulez réduire le nombre de fois que vous mesurez similitude entre les documents. Comme Boubakeur souligne à juste titre, la vérification de similitude entre toutes les paires de documents peut être trop. Si le regroupement dans un petit nombre de groupes est suffisant, vous pouvez envisager K- means , qui est essentiellement: choisir un document initial K en tant que centres de cluster, assigner tous les documents au cluster le plus proche, recalcule centres de cluster en trouvant des moyens de vecteur de documents et itérer. Cela ne coûte que K * nombre de documents par itération. Je crois qu'il ya aussi des heuristiques pour réduire le nombre nécessaire de calculs pour le regroupement hiérarchique ainsi.

Answer 4

Qu'est-ce que la fonction appelée dans l'approche similar_text # 1 ressembler? Je pense que vous faites allusion n'est pas le regroupement, mais une mesure de similarité. Je ne peux pas vraiment améliorer sur l'approche de l'histogramme :-) White Walloun -. Un problème intéressant à faire de la lecture sur

Cependant vous implémentez check(), vous devez l'utiliser pour faire au moins 200M comparaisons (la moitié des 20000^2). La coupure pour les articles « connexes » peut limiter ce que vous stockez dans la base de données, mais semble trop arbitraire pour attraper tous les clusters utiles de textes,

Mon approche serait de modifier pour retourner la $prozent métrique « similitude » (ou rtn 20K x 20K). Ecrire la matrice dans un fichier related et utiliser un programme externe pour effectuer un regroupement pour identifier les voisins les plus proches pour chaque article, vous pouvez charger dans la table R. Je ferais le regroupement dans php - il y a une belle pour les données de groupement dans un fichier en cours d'exécution à partir de <=> <=>.