Algorythme de pondération TF-IDF en PHP pour MapReduce

Voir wikipedia TF-IDF pour la définition.

Dans cette activité, nous devons appliquer MapReduce à l'algorithme au coeur des moteurs de recherche du web : Le schéma de pondération TF-IDF pour calculer la pertinence d'un document par rapport à un terme d'un dictionnaire donné. Vous pourrez trouver plus de détail de cette activité sur Openclass room.

Formule :

w_t,d = (tf_t,d / n_d) × log(N/df_t)

avec :

• tf_t,d qui représente la fréquence d'un mot t dans un document d.
• n_d qui représente le nombre de mots dans un document d (on pourra l'appeler WordPerDoc).
• df_t qui représente la fréquence du terme dans la collection, soit le nombre de documents dans lequel le mot t est présent (dans notre cas, ce sera 1 ou 2).
• Enfin N est le nombre de documents dans notre collection, soit ici 2.

Sources :

• Une collection de 2 documents textuels à récupérer sur le site textfiles.
• Filtrage des mots inutiles à l'aide de cette liste de stop words.

Pour le mappeur, nous allons simplement récupérer le flot de données sur STDIN, le filtrer, et produire en sortie des couples clef valeurs (mot, doc_ID), où l'ID du document résulte de la césure sur l'occurence "THE END" présente dans les documents, marquant la fin de chaque document.

mappeur.php

        #!/usr/bin/php
        <?php

        $exclude = file('./stopwords_en.txt');
        $doc = 0;
        $datas = file_get_contents("php://stdin");
        $blocks = explode("THE END",$datas);
        $docs = count($blocks)-1;

        for ($i=$docs;$i>0;$i--) {
            $doc++;
            $block = preg_replace("/[^a-z]/"," ",strtolower($blocks[$i-1]));
           
            foreach(explode(" ",$block) as $mot) {
                if (strlen($mot) > 3) {
                    if (!in_array($mot,$exclude)) {
                        echo "$mot,$doc".PHP_EOL;
                    }
                }
            }
        }

        ?>

Le réduceur va aggréger depuis STDIN les couples clef valeur dans différents tableaux à plusieurs dimensions, ce qui permettra de déduire les 4 permutations possibles à partir de ces couples (2^2).
Le suite est facile car il suffira d'exploiter ces 4 permutations pour les calculs, puis enfin produire le résultat par mot et par document au format ((mot, doc_ID), TF-IDF.

reduceur.php

        #!/usr/bin/php
        <?php

        // Stockage des mots, numéro de document,
        // nombre de mots par document et nombre de documents par mot
         while($ligne = trim(fgets(STDIN))) {
            $tab = explode(",",$ligne);
            $dict[$tab[1]][$tab[0]] = (isset($dict[$tab[1]][$tab[0]])) ? $dict[$tab[1]][$tab[0]]+=1 : 1;
            $motspardoc[$tab[1]] = (isset($motspardoc[$tab[1]])) ? $motspardoc[$tab[1]]+=1 : 1;
            $docsparmot[$tab[0]][$tab[1]] = 1;
        }

        // Calcul du TF-IDF par mot et par document
        // selon la formule donnée par le TD, à savoir ;
        // w_t,d = (tf_t,d / n_d) × log(N/df_t)
        foreach ($dict as $doc=>$mots) {
            foreach ($mots as $mot=>$freqmot) {
                $TFIDF[$doc][$mot] = ($freqmot/$motspardoc[$doc]) * (log(count($dict)/count($docsparmot[$mot])));
            }
        }

        // Classement des 20 premiers TF-IDF par document
        $str = "";
        foreach ($TFIDF as $doc=>$val) {
            $i = 0;
            arsort($TFIDF[$doc]);
            $str .= "Liste des 20 mots qui ont la plus forte pondération TF-IDF du document nr $doc".PHP_EOL.PHP_EOL;
            foreach ($TFIDF[$doc] as $k=>$v) {
                if ($i < 20) {
                    $i++;
                    $str .= $k.", $doc, TD-IDF: ".$v.PHP_EOL;
                } else { break; }
            }
            $str .= PHP_EOL;
        }
        $str .= "Format en sortie du mapper : (mot, doc_ID)".PHP_EOL;
        $str .= "Format en sortie du reducer : ((mot, doc_ID), TF-IDF";
        file_put_contents("./fichiers/README", $str);

        ?>

Auteur : Michael Nandzik