Besoin d'aide pour implementer un algo

Version imprimable

Je voudrais implementer l'algorithme du "backrank" que voila.

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

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

Code:

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:

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é ? :aie:

merci d'avance

29/11/2006, 18h39
mobscene

Personne pour m'aider ? :cry:
29/11/2006, 22h14
pospos

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

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:

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__

30/11/2006, 09h33
pospos

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).
30/11/2006, 10h07
mobscene

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
30/11/2006, 10h56
pospos

ok
tiens nous au courant des resultats que tu obtient stp, ca m'interesse!
30/11/2006, 16h17
mobscene

Ok 8-)