Ο αλγόριθμος της Google - Part 1

 Πολύς λόγος γίνεται τα τελευταία χρόνια, για το SEO (Search Engine Optimization),για το οποίο κάναμε μία νύξη εδώ. Το SEO στην ουσία είναι η βελτιστοποίηση των αποτελεσμάτων όσον αφορά την ιστοσελίδα μας στις μηχανές αναζήτησης ,με πρώτη τη Google.

Πώς λειτουργεί η μηχανή αναζήτησης της Google;

 Η Google μέσω προγραμμάτων ανίχνευσης  χαρτογραφεί όλες τις ιστοσελίδες.   Οι  σελίδες κατηγοριοποιούνται και στην καθεμία ανατίθεται μία αριθμητική τιμή PageRank.Όταν κάνουμε μία αναζήτηση, οι σελίδες που εντοπίζονται ως απάντηση εμφανίζονται σε εμάς ανάλογα με την τιμή  PageRank που τους έχει ανατεθεί. Η κλίμακα διαβάθμισης του PageRank είναι από το 1 έως το 10 (PR1 - PR10). Όσο μεγαλύτερο Pagerank προσλαμβάνει μια ιστοσελίδα, τόσο υψηλότερη θέση έχει στην κατάταξη στα αποτελέσματα αναζήτησης.Το PageRank αντανακλά την πιθανότητα που έχει ένας χρήστης κάνοντας τυχαίες αναζητήσεις σε συνδέσμους να καταλήξει σε μία ιστοσελίδα ή εναλλακτικά το χρόνο που μακροπρόθεσμα θα αφιερώσει στη σελίδα αυτή.

 Το PageRank ουστιαστικά είναι ένας αλγόριθμος που αναπτύχθηκε στο πανεπιστήμιο Stanford από τον Larry Page και τον Sergey Brin.Οι Brin και Page ήταν οι πρώτοι που σκέφτηκαν να χρησιμοποιήσουν τους συνδέσμους, που δρώντας ως κόμβοι συνδέουν τις ιστοσελίδες μεταξύ τους και δομούν το οικοδόμημα του web, για να προσδιορίσουν την ποιότητα του περιεχομένου μιας ιστοσελίδας. Το ερευνητικό έργο ξεκίνησε το 1995 και οδήγησε στη Google το 1998. Από τότε ο αλγόριθμος PageRank βελτιώνεται συνεχώς και συνεχίζει να αποτελεί την βάση για όλες τις αναζητήσεις της Google. 

 Η Google για να καθορίσει ποιες ιστοσελίδες πιο συναφείς με την εκάστωτε αναζήτηση και συνδυάζοντας την συνολική σπουδαιότητα και συνάφεια για τη συγκεκριμένη αναζήτηση, κατατάσσει στις πρώτες θέσεις τα πιο συναφή και αξιόπιστα αποτελέσματα,ανάλογα με τους συνδέσμους που έχει η κάθε ιστοσελίδα από και προς άλλες σελίδες,αλλά και την ποιότητα των εισερχόμενων συνδέσμων προς στην ιστοσελίδα.Αυτό μπορεί να γίνει κατανοητό ως μια αλυσίδα Markov στην οποία οι καταστάσεις είναι οι σελίδες, ενώ οι μεταβάσεις είναι όλες εξίσου πιθανές και υλοποιούνται μέσω των συνδέσμων μεταξύ των σελίδων. Αν μια σελίδα δεν έχει κανένα σύνδεσμο προς άλλες σελίδες, τότε γίνεται τερματική και τερματίζεται η διαδικασία. Εάν ο χρήστης φτάσει σε μια τερματική σελίδα, τότε θα πληκτρολογήσει μια καινούργια διεύθυνση και η διαδικασία θα ξεκινήσει από την αρχή.Όταν υπολογίζεται η τιμή PageRank για τις σελίδες που δεν έχουν κανένα εξωτερικό σύνδεσμο γίνεται η υπόθεση ότι έχουν συνδέσμους προς όλες τις σελίδες της συλλογής. Η τιμή PageRank τους επομένως αρχικοποιείται διαιρούμενη εξίσου με όλες τις ιστοσελίδες.

Αλυσίδες Markov

 Οι Αλυσίδες Markov είναι ένα είδος στοχαστικών διαδικασιών με τις οποίες μπορούμε να μοντελοποιήσουμε τη συμπεριφορά ενός τυχαία εξελισσόμενου συστήματος, με σκοπό να βρούμε μακροπρόθεσμα την ισορροπία κατάστασης του. Το κύριο χαρακτηριστικό στις αλυσίδες Markov είναι ότι δεν έχουν μνήμη,δηλαδή δεν λαμβάνεται υπόψη το παρελθόν του συστήματος για τις μελλοντικές του καταστάσεις αλλά μόνο η παρούσα κατάσταση.Αυτή η θεωρία είναι βασική στην προσωμείωση τραπεζικών συστημάτων,στο management,ακόμη και στη βιολογία και την αποκρυπτογράφηση του γενετικού υλικού.

Mία απλουστευμένη ανάλυση του αλγορίθμου PageRank

Ας φανταστούμε το web ως ένα κατευθυνόμενο γράφο,όπου η κάθε σελίδα είναι ένας κόμβος και οι σύνδεσμοι μεταξύ των σελίδων ενώνουν τους κόμβους μεταξύ τους.Το PageRank ορίζει αναδρομικά την τιμή κατάταξης για μία ιστοσελίδα i ως :

• r_j είναι η τιμή κατάταξης της ιστοσελίδας j

•I_i είναι το σύνολο των σελίδων που παραπέμπουν στη σελίδα i

• O_j είναι το σύνολο των σελίδων στα οποία παραπέμπει η σελίδα i

Στο παράδειγμά μας στο γράφο της εικόνας(έστω το web έχει 6 μόνο ιστοσελίδες):

To PageRank αρχικοποιεί όλες τις ιστοσελίδες με τιμή κατάταξης :

Έστω  q^(k) είναι ο φορέας του PageRank στην επανάληψη k και T  είναι ο στοχαστικός πίνακας της Google για το web. Ο T είναι ο πίνακας με στοιχείο t_ij την πιθανότητα να μεταφερθούμε απευθείας από τη σελίδα j στη σελίδα i.

Tα t_ij είναιαν υπάρχει σύνδεσμος από τη σελίδα j στη σελίδα i ,ειδάλλως είναι 0.Τότε ισχύει :  q^(k+1)= T q^(k).

^{Στο παράδειγμά μας ο πίνακας Τ είναι:}

Για να απαλλαγούμε από τους κόμβους που ¨κρέμονται¨, απλά αντικαθιστούμε τη στήλη των μηδενικών με μία στήλη που έχει ως στοιχεία τα 1/n,όπου n είναι ο αριθμός όλων των ιστοσελίδων.

 Προσθέτοντας στον άνωθι πίνακα έναν πίνακα Ε (perturbation matrix)  με στοιχεία 1/n και θεωρώντας α=0.85 (damping factor-η πιθανότητα ο χρήστης να συνεχίσει να κλικάρει αντί να σταματήσει) προκύπτει ο περιβόητος πίνακας Google:

Μετά από 25 επαναλήψεις από το PageRank (δηλαδή ο πίνακας Google στην 25^η) διαπιστώνουμε ότι η τελευταία στήλη, (που είναι το διάνυσμα μόνιμης κατάστασης-με ιδιοτιμή 1 κατά το θεώρημα Perron-Frobenius), έχει σταθεροποιηθεί σε μία ¨μόνιμη κατάσταση¨.

με διάνυσμα μόνιμης κατάστασης την τελευταία στήλη:

Πώς η Google χρησιμοποιεί αυτό το διάνυσμα μόνιμης κατάστασης;

•Έστω ότι κάνουμε αναζήτηση τους όρους 1 και 2 (πχ. Αγοράζω - παγωτό)

•Έστω ότι το PageRank για τον όρο 1 βρίσκει ως αποτέλεσμα τις ιστοσελίδα 3,2 και 6 ,ενώ για τον όρο 2 ,βρίσκει τις ιστοσελίδα 1 και 3.

•Το σύνολο με τις ιστοσελίδες που προκύπτουν ως αποτελέσμα προκύπτει λοιπόν {1, 2, 3, 6} με ¨συντελεστές βαρύτητας¨ s₁=.2066, s₂=.1770, s₃=.1773, s₆=.1309 ως στοιχεία του διανύσματος μόνιμης κατάστασης s που βρήκαμε παραπάνω.

•Άρα η ιστοσελίδα 1 θα ταξινομηθεί πρώτη αφού το s₁ είναι μεγαλύτερο από το s_2, s₃ , s_6.

_{Μία ενδιαφέρουσα διάλεξη για το Google PageRank και τις αλυσίδες Markov από τον Joe Blitzstein του Harvard University:}

To be continued..

Posted in: algorithm,damping,Google,Google Matrix,Markov chain,PageRank,Seo,αλγόριθμος,αλυσίδα Markov,κατάταξη,μηχανή αναζήτησης,στοχαστικός πίνακας