Data mining : pageRank

1. Intro

Nous avons vu en cours quelques concepts reliant matrices et graphes, que nous allons brièvement revoir ici.

1.1 Matrice d'adjacence

En général on peut représenter un graphe orienté (collection de n sommets, ou noeuds, ou points -- ici pages web -- reliés par des "flêches" -- ici hyperliens) avec une matrice carrée n x n M ainsi

   M_i,j = 1 si et seulement si la page j a un lien vers la page i

Autrement dit, dans la colonne j on mettra des 1 sur les lignes des pages pointées par la page j. Ou encore, pour une ligne donnée, les colonnes des 1 indiquent les pages qui pointent vers la page de numéro celui de la ligne. Donc les lignes et les colonnes de la matrices représentent nos pages. Exemple Voici un graphe avec trois pages numérotées 1,2 et 3, et sa matrice d'adjacence

  /   0    0    1   \
  |                 |
  |   1    1    0   |
  |                 |
  \   0    0    0   /

Travail à faire

Soit la matrice d'adjacence suivante, dessinnez-en le graphe correspondant

  /   1    1    0   \
  |                 |
  |   0    0    0   |
  |                 |
  \   1    0    1   /

Soit le graphe suivant, , donnez-en la matrice d'adjacence

1.2 Matrice sous-stochastique-par-colonne

Pour notre contexte, la matrice d'adjacence sera un peu transformée, pour que les sommes par colonnes soient toutes égales à 1 pour toutes les colonnes qui contiennent au moins une valeur non-nulle. Une telle transformation qui est parmi les plus simples consiste à diviser toutes les entrées par le nombre initial de 1. Ainsi, par exemple,

  /   1    1    0   \              /  1/2   1/3     0    \
  |                 |              |                     |
  |   1    1    1   |   devient    |  1/2   1/3    1/2   |  
  |                 |              |                     |
  \   0    1    1   /              \   0    1/3    1/2   /

Travail à faire

Donnez les matrices sous-stochastiques-par-colonne pour les exercices 1.1.1 et 1.1.2 ci-dessus.

1.3 Ajustements de primitivité et stochastique

Nous avons vu en cours que le but de ce jeu est en fait la modélisation d'un "surf aléatoire" sur les pages web, les valeurs de la matrice représentant des probabilités pour le choix de la page suivante (et leur somme est bien 1 pour chaque colonne non-nulle). Par contre, le surfeur peut, de temps en temps, s'interrompre et ensuite aller à une page absolument quelconque, sans nécessairement suivre un lien. De même, s'il arrive sur une page impasse (page sans liens sortants), il peut également choisir une page absolument quelconque pour continuer. Pour prendre ces aspects en compte, on va dire

qu'avec probabilité β (par exemple 0.8) le surfeur choisit un des liens existants, et alors avec 1-β il va "n'importe-où"
que depuis une page "impasse" (colonne avec uniquement des zéros) il peut à nouveau aller "n'importe-où"

Soit S une des matrices n x n stochastiques-par-colonnes calculées au point 1.2. Soit R la matrice((1-β)/n)*[1]_n,n (c'est-à-dire une matrice carrée n x n qui contient la valeur (1-β)/n partout).

on calcule T=β*S+ R
on calcule G=T + P, où P est une autre matrice carrée n x n qui a des zéros partout, sauf pour les colonnes des impasses, qui ont toutes la valeur β/n.

Par exemple, soit la matrice stochastique-par-colonnes initiale

    /  1/2   1/3     0    \ 
    |                     | 
S = |  1/2   1/3     0    | 
    |                     | 
    \   0    1/3     0    /

et soit β=4/5, et notre n=3. Alors (1-β) / n = 1/15 et β/n = 4/15, et alors on aura

    /  1/15   1/15   1/15   \ 
    |                       | 
R = |  1/15   1/15   1/15   | 
    |                       | 
    \  1/15   1/15   1/15   /

    /   0     0    4/15   \ 
    |                     | 
P = |   0     0    4/15   | 
    |                     | 
    \   0     0    4/15   /

et donc G = β*S + R + P, c'est-à-dire

  /  2/5   4/15    0   \   /  1/15   1/15   1/15   \   /  0     0    4/15   \   /  7/15   1/3   1/3  \
  |                    |   |                       |   |                    |   |                    |
  |  2/5   4/15    0   | + |  1/15   1/15   1/15   | + |  0     0    4/15   | = |  7/15   1/3   1/3  | 
  |                    |   |                       |   |                    |   |                    |
  \   0    4/15    0   /   \  1/15   1/15   1/15   /   \  0     0    4/15   /   \  1/15   1/3   1/3  /

Travail à faire

Soit le graphe et β=0.8. Donnez sa matrice G en détaillant tous les pas depuis la matrice d'adjacence, comme expliqué aux points précédents.
Est-il toujours vrai que les sommes des colonnes sont égales à 1 pour la matrice G aussi ? (On sait qu'elles le sont pour les colonnes non-nulles de S, de par sa construction). Justifiez votre réponse.

2. Algorithme

Nous avons vu en cours que le principe de base de l'algorithme est de se prendre un vecteur r de dimension n, initialisé à 1/n partout :

            /  1/n  \
            |  1/n  |
    r₀   =  |  ...  |
            |       |
            \  1/n  /

et d'itérer la multiplication de notre matrice avec ce vecteur

r₂ = G * r, puis r₃ = G * r₂, puis r₄ = G * r₃, ...

On a donc en général

    r_k = G * r_k-1

On rappelle que la multiplication d'une matrice M_n,n avec un vecteur colonne V_n donne un vecteur colonne ainsi

           /  m_1,1*v₁+m_1,2*v₂+...m_1,n*v_n  \
           |  m_2,1*v₁+m_2,2*v₂+...m_2,n*v_n  |
           |  ...                       |
           |                            |
           \  m_n,1*v₁+m_n,2*v₂+...m_n,n*v_n  /

On continue donc notre processus de multiplication itérative jusqu'à ce que, pour un ε fixé,

    |r_k  - r_k-1| < ε

et alors ce vecteur représente le vecteur de pageRank, qui donnera le score des pages, donc les pages les plus "intéressantes". Pour nous ici on pourra utiliser la norme abs -- donc la somme des valeurs absolues --

    |r_1,k  - r_1,k-1| + |r_2,k  - r_2,k| + ... + |r_n,k  - r_n,k| < ε

Travail à faire

Calculez r₂ pour la matrice G que vous avez obtenu au 1.3.1

3. Implémentation

Nous allons compléter le code de la classe SimplePageRank avec plusieurs méthodes. Les données-membres essentielles sont

double[][]     matrix; 
private double beta = 0.8;
private double epsilon = 0.0001;
double[]       pR;  // le vecteur pageRank resultat

Travail à faire

Créez un répertoire nommé rank, dans lequel vous écrirez dans le fichier SimplePageRank.java le code nécessaire selon les points suivants. Mettez tout en haut du fichier

package rank;

import org.apache.lucene.index.IndexReader;
import org.apache.lucene.document.Document;
import org.apache.lucene.store.FSDirectory;
import java.io.*;
import java.util.*;
import index.SimpleLuceneIndex;

Écrivez la méthode public void calculate() (qui ne prend donc aucun paramètre et qui ne rend rien) et qui change matrix (qui est déjà remplie au moment de l'appel de calculate() avec la matrice d'adjacence -- donc des 1 et des 0) pour la rendre sous-stochastique-par-colonnes. Donc cette méthode ne fait que ce qui est décrit au point 1.2. Le nombre n peut être obtenu en Java en faisant matrix.length.
Écrivez la méthode public int[] getDangling() (qui ne prend donc aucun paramètre) qui rend un vecteur de n entrées, toutes zéro sauf celles correpondant aux colonnes des "impasses" (donc aux colonnes nulles de matrix).
Écrivez la méthode private double[][] getDanglingNodeMatrix() (qui ne prend donc aucun paramètre) qui rend la matrice P telle qu'elle est décrite au point 1.3 ci-avant. Cette méthode se servira de getDangling().
Écrivez la méthode private double norm(double[] a, double[] b) qui calcule la norme de a-b au sens vectoriel comme expliqué au point 2 ci-avant.
Écrivez la méthode public void findPageRank() selon les explications du point 2 ci-avant. Cette méthode sera appelée après que la méthode calculate() est appelée, donc matrix sera bien la matrice sous-stochastique du point 1.2.
- initialise pR
- appelle getDanglingNodeMatrix() pour obtenir P
- calcule la matrice G à partir de matrix, de P, de β (donnée-membre) etc.
- itère la multiplication de G avec pR tant que la norme de deux instances consécutives du vecteur de pageRank est plus grande qu'ε (donnée-membre) (prenez un autre vecteur temporaire pour sauvegarder l'instance précédente, calculez la multiplication et puis calculez la norme de la différence).
- après que la boucle est terminée, calculez la valeur m = 1 - 1/n.
- dans une autre boucle, pour chaque entrée k de pR, sauvegardez dans son fichier rankscore_<k>.txt correspondant la puissance pR[k]^m -- ceci est une astuce anti-spam à utiliser pour rééquilibrer les scores lorsqu'on a à faire à peu de pages (comme dans nos exemples ici) (rappel : il y a autant de fichiers rankscore que de documents, tout comme les autres fichiers qu'on avait lu lors de la création d'index dans le tp précédent).

Solution partielle : à télécharger.

4. Intégration avec l'indexation et la recherche

Pour que notre programme puisse être facilement utilisé avec les programmes des TPs précédents, on initialisera la matrice matrix d'adjacence depuis l'index construit au TP précédent, et on écrira ensuite un nouvel index -- dans lequel on pourra chercher toujours avec les programmes des TPs précédents.
Ceci est le code du constructeur, précédé par des déclarations de quelques données-membres.

    final int            nTotDocs; 
    final String         docPath;
    final String         indexPath;
    final String         newIndexPath;

    public SimplePageRank(String dcP, String idxP) throws Throwable {
	docPath      = dcP;
	indexPath    = idxP;
	newIndexPath = indexPath + "/rankIndex";
	Scanner scanner  = new Scanner(new FileInputStream(docPath + "/nTotDocs.txt"));
	if (scanner . hasNextInt()){
	    nTotDocs = scanner . nextInt();
	}
	else {
	    throw new Exception("OOPS Pas de fichier '" + docPath + "/nTotDocs.txt' pour lire...");
	}
	setIniMatrix();
	calculate();
	findPageRank();
	SimpleLuceneIndex luceneReIndex = new SimpleLuceneIndex(docPath, "crawl.txt", newIndexPath);
    }

Travail à faire

Écrivez la méthode setIniMatrix() qui
- commence par ouvrir l'index créé auparavant, mais en lecture, avec
```
	
IndexReader indexReader = IndexReader . open(FSDirectory.open (new File(indexPath)),true); 
```
- initialise la donnée-membre matrix
- dans une boucle pour tous les documents (indexReader . maxDoc())
Que va faire le constructeur à sa dernière ligne ?
Finissez le main(), récupérez le nouveau fichier makefile, compilez le tout et testez-le. Faites attentions aux chemins (indexPath, etc.)
Changez le nom du répertoire index (avec les .java et tout) en old.index et faites un nouveau répertoire index. Copiez le fichier SimpleLuceneIndex.java depuis old.index dans index -- c'est le seul qui ne change pas. Téléchargez également IndexSearch.java et SimpleLuceneSearcher.java dans le même répertoire index. Faites make (comme d'habitude).
Le but de la manipulation précédente a été de mettre àjour le programme du TP précédent, pour avoir la possibilité de chercher aussi selon le rang. Un exemple, du début à la fin, est le suivant. On lance le server java (comme au premier tp, donc e.g. java -jar server.jar 8123, dans un shell différent) et on exécute les commandes suivantes.
```
mkdir testTpComplet
java -jar crawler.jar 8123 indexAll.html  testTpComplet
java -jar index.jar index testTpComplet crawl.txt 
java -jar rank.jar testTpComplet testTpComplet/luceneIndex
java -jar index.jar search testTpComplet/luceneIndex armstrong 5
java -jar index.jar ranksearch testTpComplet/luceneIndex/rankIndex armstrong 5
```
Solution
Vous pouvez télécharger l'archive complète avec la solution à partir d'ici. Vous devez la décompresser, par exemple en faisant
```
    zcat nomDuFichierQueVousAvezTelecharge | tar xvf -
```
et ensuite faire un make, et enfin, suivre toutes les étapes du test complet. Surtout, on met en évidence le traitement différent des articles selon qu'on cherche avec l'indexation faite sur le contenu des documents avec l'infrastructure mise à disposition par Lucene d'une part, ou bien utilisant le pageRank, c'est-à-dire l'algorithme type Google d'analyse des liens entre les documents, indépendamment de leur contenu:
```
  java -jar index.jar search testTpComplet/luceneIndex armstrong 5
```
donnera plein de résultats contenant également du spam, tandis que
```
java -jar index.jar ranksearch testTpComplet/luceneIndex/rankIndex armstrong 5
```
donnera des résultats plus significatifs et propres.