IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Perl Discussion :

Besoin d'aide pour implementer un algo


Sujet :

Langage Perl

  1. #1
    Membre actif Avatar de mobscene
    Profil pro
    Inscrit en
    Avril 2005
    Messages
    331
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2005
    Messages : 331
    Points : 234
    Points
    234
    Par défaut Besoin d'aide pour implementer un algo
    Je voudrais implementer l'algorithme du "backrank" que voila.

    http://www2005.org/cdrom/docs/p1122.pdf

    Je suis donc partie de la lib Algorithm:ageRank et j'ai effectué deux modif que voila

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # ajout du paramètre $b_factor
    our $d_factor = undef; # dampening factor
    my  $b_factor = undef;
     
    sub factor
    {
      $d_factor = $_[1]; # dampening factor
      $b_factor = $_[2]; # back button dampening factor
    }



    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    sub _iterate
    {
      my $self = shift;
      my $iter = shift || 100;
      my $normal_factor = $d_factor/$self->{size};
      # j'ai ajouté sa aussi
      my $inv_d_factor = 1 - ($d_factor + $b_factor);
      print $self->{prvect}->slice(":");
      print $self->{graph}->slice(":");
      
      foreach (1..$iter)
      {
          # Original pagerank
          $self->{prvect} = $inv_d_factor * $self->{prvect} x $self->{graph} + $normal_factor * $self->{prvect};
          
          #$self->{prvect} = $inv_d_factor * $self->{prvect} x $self->{graph} + $normal_factor * $self->{prvect};
          #print $self->{prvect}->slice(":");
          #print sdump (($d_factor/$self->{size}) * $self->{prvect});
       }
    }

    Ma question est l'algo est il bien implémenté ?

    merci d'avance
    Everybody have in their the potential to be their own god : Marilyn Manson

  2. #2
    Membre actif Avatar de mobscene
    Profil pro
    Inscrit en
    Avril 2005
    Messages
    331
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2005
    Messages : 331
    Points : 234
    Points
    234
    Par défaut
    Personne pour m'aider ?
    Everybody have in their the potential to be their own god : Marilyn Manson

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    427
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 427
    Points : 459
    Points
    459
    Par défaut
    pour te repondre il faudrait lire le paier (et connaitre l'algo page rank...)
    ce que je peux te conseiller en tous cas c'est d'utiliser PDL pour ce genre de choses (je ne sais pas si le module PageRank l'utilise deja, mais en tous cas le module HITS l'utilise)
    si tu cherche un bon algo de ranking en tous cas le pagerank c'est pas la folie (et ca coute cher en calcul), le HITS est plu rentable

    http://search.cpan.org/~xern/Algorit...orithm/HITS.pm
    Recherche staigiaire(s) motivé(s) sur projet perl/reseau a grande echelle. Me contacter par mp.

  4. #4
    Membre actif Avatar de mobscene
    Profil pro
    Inscrit en
    Avril 2005
    Messages
    331
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2005
    Messages : 331
    Points : 234
    Points
    234
    Par défaut
    L'algo du pagerank en perl utilise déjà la pdl le truc c'est que j'aimerai faire ajouter "le back button" dans l'algo pour voir qu'elle différence cela induit dans mon moteur. J'ai déjà essayé Hits.

    Ce document est plus parlant http://www.www2004.org/proceedings/docs/2p352.pdf

    Il semblerai déjà qu'en faisant 1 - ( a + b ) je ne me soit pas tromper


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    use strict;
    use List::Util;
    use PDL;
    my $VERSION = '1.0';
     
     
     
    use fields qw(graph prvect size);
     
     
     
    sub new
    {
       my $class = shift;
       return bless {
       },$class;
    }
     
     
     
     
    our $d_factor = undef; # dampening factor
    my  $b_factor = undef;
     
    sub factor
    {
      $d_factor = $_[1]; # dampening factor
      $b_factor = $_[2]; # back button dampening factor
    }
     
     
     
     
     
    sub graph
    {
        my $self  = shift;
        my $graph = shift;
     
        die "Odd number of node numbers is not valid\n" if scalar(@$graph)%2;
     
        my $size = List::Util::max(@$graph)+1;
        $self->{size} = $size;
     
        # Create web graph
        $self->{graph} = zeroes($size, $size);
        for (my $i = 0; $i<@$graph ; $i+=2)
        {
    	  $self->{graph}->index2d(
    				    $graph->[$i],
    				    $graph->[$i+1],
    				   ) .= 1;
        }
     
        foreach my $i (0..$self->{size}-1)
        {
    	   my $outdeg_sum = sum $self->{graph}->slice(join q/:/, $i, $i); 
    	   if($outdeg_sum)
    	   {
    	     $self->{graph}->slice(join q/:/, $i, $i) /=
    		 $outdeg_sum;
    	   }
        }
     
        $self->{graph} = transpose $self->{graph};
        $self->{prvect} = ones($size) / $size;    # the initial pagerank
        #print $self->{graph}->slice(":");
        #print sdump $self;
        #print $self->{prvect}->slice(":");
    }
     
     
     
     
    sub iterate
    {
        my $self = shift;
        my $iter = shift || 100;
        my $normal_factor = $d_factor/$self->{size};
        my $inv_d_factor = 1 - $d_factor;
        print $self->{prvect}->slice(":");
        print $self->{graph}->slice(":");
     
        foreach (1..$iter)
        {
          # Original pagerank
          $self->{prvect} = $inv_d_factor * $self->{prvect} x $self->{graph} + $normal_factor * $self->{prvect};
     
          #print $self->{prvect}->slice(":");
          #print sdump (($d_factor/$self->{size}) * $self->{prvect});
        }
    }
     
     
    sub _iterate
    {
      my $self = shift;
      my $iter = shift || 100;
      my $normal_factor = $d_factor/$self->{size};
      my $inv_d_factor = 1 - ($d_factor + $b_factor);
      print $self->{prvect}->slice(":");
      print $self->{graph}->slice(":");
     
      foreach (1..$iter)
      {
          # modif
          $self->{prvect} = $inv_d_factor * $self->{prvect} x $self->{graph} + $normal_factor * $self->{prvect};
       }
    }
     
     
    sub result
    {
        my $self = shift;
        $self->{prvect};
    }
     
    1;
    __END__
    Everybody have in their the potential to be their own god : Marilyn Manson

  5. #5
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    427
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 427
    Points : 459
    Points
    459
    Par défaut
    il fait quoi ton moteur?
    il est visible? (ca m'interesse!)

    pour le ranking des resultats le pagerank (ou autre) est finalement peu utilisé (meme par google). Ce qui compte le plus c'est le score semantique, avec une emphase particulieres sur les termes venant du texte des liens pointant sur la page, du texte de l'url, et du titre.
    Deja si tu indexe le texte des liens entrants (ce qui n'est pas forcement facil...) tu aura de tres bons resultats (et plus une page aura de liens entrant et plus elle aura de texte à indexer, donc la topologie entre aussi en jeu). C'est notamment ce que fait Nutch.
    En fait pour avoir un pagerank efficace il faudrait qu'il soit thematisé (c'est ce que dit faire Ask.com).
    Recherche staigiaire(s) motivé(s) sur projet perl/reseau a grande echelle. Me contacter par mp.

  6. #6
    Membre actif Avatar de mobscene
    Profil pro
    Inscrit en
    Avril 2005
    Messages
    331
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2005
    Messages : 331
    Points : 234
    Points
    234
    Par défaut
    Je trouve que le backrank apporte un plus en prenant en charge le "back button", l'algo ne me sert qu'a savoir l'importance d'une page dans un bloc "sémantique", le reste du classement je l'effectue avec d'autres algo
    Everybody have in their the potential to be their own god : Marilyn Manson

  7. #7
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    427
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 427
    Points : 459
    Points
    459
    Par défaut
    ok
    tiens nous au courant des resultats que tu obtient stp, ca m'interesse!
    Recherche staigiaire(s) motivé(s) sur projet perl/reseau a grande echelle. Me contacter par mp.

  8. #8
    Membre actif Avatar de mobscene
    Profil pro
    Inscrit en
    Avril 2005
    Messages
    331
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2005
    Messages : 331
    Points : 234
    Points
    234
    Par défaut
    Ok
    Everybody have in their the potential to be their own god : Marilyn Manson

Discussions similaires

  1. Besoin d'aide pour un Algo
    Par Spinoza23 dans le forum Mathématiques
    Réponses: 10
    Dernier message: 16/02/2007, 16h35
  2. Besoin d'aide pour passage d'un algo au langage JAVA
    Par Spinoza23 dans le forum AWT/Swing
    Réponses: 6
    Dernier message: 16/02/2007, 16h33
  3. Besoin d'aide pour algo
    Par vodevil dans le forum Langage
    Réponses: 8
    Dernier message: 08/03/2006, 14h45
  4. besoin d'aide pour des algos
    Par mathieu77 dans le forum Algorithmes et structures de données
    Réponses: 23
    Dernier message: 08/11/2005, 19h33

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo