Algoritmo PageRank per un motore di ricerca personalizzato

bobighorus

Algoritmo PageRank per un motore di ricerca personalizzato

Salve a tutti gli utenti di questa splendida community!:)
Per un lavoro accademico mi è stato chiesto di implementare l'algoritmo PageRank nel motore di ricerca interno in un CMS personalizzato da me costruito e ottimizzato per il SEO; a questo punto vorrei chiedere a quanti più esperti di me: è possibile fare una cosa del genere? Cioè calcolare il PR interno delle pagine del sito in modo da ordinare i risultati della query?:? E se si, come è possibile scrivere una cosa del genere in PHP con interazione su un database MySql o PostgreSql (architettura del CMS)?
Inoltre, se non vado errato, la formulazione originale del PR non è correlata alla query; cioè il PR è "solo" un algoritmo per l'ordinamento dei risultati ma che non tiene traccia della pertinenza alla ricerca: questo mi lascia capire che devo prima scrivere un algoritmo di pertinenza della query e poi integrare l'algoritmo PR per ordinare i risultati ottenuti; giusto?
Scusate le troppe domande ma, come potrete immaginare, in questi casi non si sa davvero a chi chiedere.
Grazie mille a chi vorrà aiutarmi!

criss

Ciao bobighorus e benvenuto,

se ho ben capito la tua richiesta forse a chi ti ha commissionato il lavoro accademico non è ben chiara la funzione del Pagerank.

Mi spiego meglio: il PR non è assolutamente un algoritmo di ordinamento risultati, ma un fattore che concorre assieme a molti altri (i più oscuri a noi "normali umani") al posizionamento e al trust (prendila come affermazione generalizzata quest'ultima) di un sito per il motore di ricerca google.

Questo fattore è calcolato in base al numero di link che riceve una pagina, alla "bontà" di questi, alla rilevanza e da che pagina arrivano (tra l'altro differenze ci sono anche tra link che arrivano dall'interno e link dall'esterno).

Già con queste poche righe direi di averti smontato il lavoro purtroppo.

Se invece il lavoro che ti hanno commissionato fosse il dover ordinare le pagine a seconda dai link interni ricevuti e tenendo conto della "profondità" di questi allora il lavoro è fattibile e ci si può senz'altro ragionare per ricavarne un algoritmo abbastanza veritiero.

Fai sapere che il lavoro è carino e se è come ho supposto ti aiuto volentieri a ragionarci.

lowlevel

@bobighorus said:

è possibile fare una cosa del genere? Cioè calcolare il PR interno delle pagine del sito in modo da ordinare i risultati della query?:?

Certo che sì, ma presta attenzione a quanto ti ha detto Criss perché le cose sono distinte: la formula del PageRank assegna un valore numerico a ciascuna risorsa, che poi l'ordinamento si basi anche su quel valore (e in che modo) è una scelta da fare in fase di definizione della formula/algoritmo che verrà usata per ordinare i risultati.

E se si, come è possibile scrivere una cosa del genere in PHP con interazione su un database MySql o PostgreSql (architettura del CMS)?

Hai bisogno di una tabella in cui memorizzare le informazione su come le pagine del sito si linkano tra loro. Per iniziare sarebbe sufficiente una tabella con due campi:

id_pagina_che_offre_il_link
id_pagina_che_riceve_il_link

...ogni riga della tabella conterrebbe dunque le informazioni su un link, specificando quale pagina linka quale altra pagina.

Queste informazioni di interlinking puoi ottenere con un crawler che si sciroppa le pagine del sito.

Poi applichi la formula del PageRank a quelle informazioni. C'è molta documentazione in merito sul Web. Inizia con una bella ricerca ed ovviamente con Wikipedia.

devo prima scrivere un algoritmo di pertinenza della query e poi integrare l'algoritmo PR per ordinare i risultati ottenuti; giusto?

Esatto. Una prima semplice pertinenza con la query la puoi ottenere con una formuletta tipo questa http://en.wikipedia.org/wiki/PageRank

Ciao!

bobighorus

Ciao ragazzi!
Rispondo ad entrambi; innanzitutto grazie per le vostre risposte.
Ho avuto modo in passato di leggere dei post molto interessanti di LowLewel, sul rapporto stretto tra i motori di ricerca e l'Information Retrieval.
Il mio scopo è quello, come ha supposto Criss nella seconda ipotesi, di ordinare i risultati del mio motore di ricerca interno al CMS in base all'algoritmo PR applicato ai soli link interni del sito, tenuto conto della formulazione originale del PR (quella della pagina di Wikipedia, per intenderci).
Premetto che per il mio lavoro ho dovuto leggere decine di articoli in inglese su questi argomenti :x, incluso l'articolo originale sul PageRank.
Qui sorge un dubbio su quello che ha scritto LowLewel: nella formulazione originale del PR non c'è correlazione alla query, ma solo il proposito di offrire un ranking dei risultati - ottenuti mediante altri algoritmi a noi ignoti - in base alla "popolarità" di una pagina, secondo lo schema della "citation analysis".
Tornando alla fase implementativa: io ho già sviluppato un algoritmo per il motore interno del sito (basato sulla legge di Zipf e sul modello booleano esteso) che, dopo aver eliminato le "stop word", calcola la similarità alla query e poi assegna un peso a secondo della posizione delle parole della query nel corpo del testo (10 punti se si trova nel titolo, 8 nel <h1> e così via...), calcolando a partire da questi dati una percentuale di "rilevanza"; successivamente ordino i dati con un ORDER BY rilevanza DESC.
Per un sito di medie dimensioni questo meccanismo funziona bene, tenuto conto anche che essendo un CMS scritto dall'utente si suppone che la quantità di spam sia pari a 0.
A questo punto mi è stato chiesto di ordinare i risultati non solo in base a questo meccanismo, ma tenendo conto anche della link popularity interna di ogni pagina, mediante lo schema dell'algoritmo originale del PR, al fine di ottenere un ORDER BY rilevanza DESC, pagerank DESC.
Quindi come dovrei muovermi, adesso, per cercare di fare questo? :bho:
Tenendo conto di quello che ha scritto LowLewel immagino che dovrei:

scrivere un crawler che tiene traccia di tutti i link esterni ed interni per ogni pagina;
inserire i dati in due tabelle nel db;
calcolare il ranking in base a questi dati.
Giusto?
Grazie mille ragazzi per la pazienza e per l'attenzione; spero di essere stato più chiaro adesso.

criss

Ciao bobighorus,

la situazione è alquanto ingarbugliata.
Se dovessi decidere io come farti fare questo algoritmo ti farei "sommare" la rilevanza da te già citata con quella "del PR" (link ricevuti) in luogo di ordinare prima per rilevanza e poi per PR.

Che peso però vuoi dare ai vari fattori ancora non mi è chiaro.

Sono in ogni caso tutti link interni, quindi potresti dare un valore iniziale a seconda della "profondità" della pagina. Più è vicina alla index e più ha valore.
Questo valore diviso per il numero di link della pagina ti darebbe il "peso" del link. Peso del link che andrebbe moltiplicato ad un fattore di rilevanza keyword dell'anchor text e/o del title, e anche alla posizione del link nella pagina (stando alle ultime notizie ricevute in modo più o meno frammentario da Mountain View).

In questo modo (poi puoi aggiungere altre discriminanti ovviamente) avresti un coefficente da poter moltiplicare alla "rilevanza" che hai già calcolato e riordinare i risultati.

Però questa è solo una mia idea per un algoritmo che potrebbe risultare performante, sempre tenendo conto del fatto che magari non è questo l'obiettivo reale che si vuole ottenere.

Se non è chiaro provo a spiegarmi meglio

lowlevel

@bobighorus said:

A questo punto mi è stato chiesto di ordinare i risultati non solo in base a questo meccanismo, ma tenendo conto anche della link popularity interna di ogni pagina, mediante lo schema dell'algoritmo originale del PR, al fine di ottenere un ORDER BY rilevanza DESC, pagerank DESC.

In realtà ciò che si fa solitamente è:
ORDER BY (rilevanza * pagerank) DESC

Ovvero una semplice moltiplicazione.
Spesso si aggiungono alla formula anche dei moltiplicatori per fattori, per stabilire quanto peso assegnare al fattore rilevanza e quanto assegnarne al fattore pagerank.

scrivere un crawler che tiene traccia di tutti i link esterni ed interni per ogni pagina;

Questo sarebbe il metodo più esaustivo. In aggiunta, se la struttura del sito non è troppo incasinata, le informazioni sull'interlinking possono in parte essere estratte interrogando il DB del CMS stesso, ad esempio osservando le strutture di navigazione (menu) comuni a tutte le pagine. Ma se hai un crawler che scarica tutto, questa aggiunta sarebbe superflua.

Siccome la progettazione di un crawler non è qualcosa di banale, prova a cercarne prima uno open source o comunque già esistente.

Ciao!

bobighorus

@criss: Credo di aver capito il tuo concetto; la prima parte mi sembra che vada nella stessa direzione di quanto scritto anche da LowLewel.
Quello che invece mi sfugge è il perchè consigli di attribuire una maggiore rilevanza ai link più vicini alla home e una inferiore a quelli più lontani (immagino link in sottocategorire e via dicendo)...

bobighorus

@LowLevel said:

In realtà ciò che si fa solitamente è:
ORDER BY (rilevanza * pagerank) DESC

Ovvero una semplice moltiplicazione.
Spesso si aggiungono alla formula anche dei moltiplicatori per fattori, per stabilire quanto peso assegnare al fattore rilevanza e quanto assegnarne al fattore pagerank.

Stai facendo riferimento alla famosa moltiplicazione "tf * idf "?

Siccome la progettazione di un crawler non è qualcosa di banale, prova a cercarne prima uno open source o comunque già esistente.

Sono d'accordo con te, un crawler non è una cosa semplice da progettare...
Quindi mi sembra di capire che ho afferrato cosa fare...una cosa che ancora non mi è chiara, però, è come fare ad esprimere in codice (in questo caso PHP) la formula matematica del PR...qualche suggerimento?
Grazie.

criss

@bobighorus said:

Quello che invece mi sfugge è il perchè consigli di attribuire una maggiore rilevanza ai link più vicini alla home e una inferiore a quelli più lontani

Ciao bob (scusa se ti "eviro" di qualche lettera il nick ),
per un discorso empirico sul PR solitamente se hai una home a PR4 di solito le pagine linkate da questa hanno PR3 e quelle linkate a loro volta PR2.
Quindi più vicino sei alla home più hai rilevanza.
Dando un coefficente esponenziale tipo 10 alla 4 per la home e 10 alla 3 per quelle linkate direttamente dalla home secondo me ti avvicini molto ad una rilevanza similare a quella del PR.
La misura della base del coefficente esponenziale sta a te deciderla ovviamente, ma è per variare il valore a seconda del "peso" della pagina.

Spero di non essere stato troppo enigmatico (leggasi: non mi son spiegato bene per nulla probabilmente).

Fa sapere

lowlevel

@bobighorus said:

Stai facendo riferimento alla famosa moltiplicazione "tf * idf "?

No. La formula tf*idf può essere modificata introducendo dei parametri di moltiplicazione che assegnano peso tra le varie componenti della formula.

Io mi riferivo all'introduzione di parametri nella moltiplicazione (rilevanza * pagerank). Esempio:

( (rilevanza * 0.5) * (pagerank * 0.2) )

Nell'esempio, assegni un peso (ovvero un'influenza) maggiore alla rilevanza calcolata attraverso una formula tipica (tf*idf) ed un peso minore alla componente PageRank.

Sono d'accordo con te, un crawler non è una cosa semplice da progettare...

Ci si può anche industriare... dai un'occhiata a Xenu Link Sleught, ha un'opzione di esportazione in un formato che elenca i link trovati in forma di coppie linkante/linkato.

Quindi mi sembra di capire che ho afferrato cosa fare...una cosa che ancora non mi è chiara, però, è come fare ad esprimere in codice (in questo caso PHP) la formula matematica del PR...qualche suggerimento?

Per quello (e a prescindere dal linguaggio di programmazione usato) ti serve un algoritmo.

Dai un'occhiata a questa pagina, in particolare al metodo iterativo di Jacobi:
http://pagerank.suchmaschinen-doktor.de/index/math.html

bobighorus

Grazie ragazzi per le vostre risposte.
Mi avete fornito sicuramente delle buone indicazioni.
Non mi resta che mettermi al lavoro.
Vi aggiornerò sui progressi (spero)
Grazie ancora.
A presto.