Υπολογισμός του Πλήθους των Απαντήσεων μιας Μηχανής Αναζήτησης


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

results from google
Στο ερώτημα "Προπτυχιακές Σπουδές Ιχθυοκαλλιέργειας" η μηχανή αναζήτησης εκτίμησε ότι υπάρχουν 289 σχετικά κείμενα

Στη συνέχεια θα υποθέσουμε ότι ένα κείμενο ανήκει στη λίστα των αποτελεσμάτων όταν περιέχει όλες τις λέξεις του ερωτήματος. Για τον υπολογισμό του πλήθους των απαντήσεων θα κάνουμε μία ακόμη υπόθεση. Θα υποθέσουμε ότι οι λέξεις εμφανίζονται ανεξάρτητα η μια από την άλλη τότε η πιθανότητα ένα κείμενο να περιέχει όλες τις λέξεις του ερωτήματος ισούται με το γινόμενο των πιθανοτήτων εμφάνισης στο κείμενο καθεμιάς από τις λέξεις. Για παράδειγμα, αν το ερώτημα έχει τρεις λέξεις Q={ a, b, c}, τότε η πιθανότητα ένα κείμενο να περιέχει και τις τρεις λέξεις είναι:

indepentent

Η πιθανότητα ένα κείμενο να περιέχει μια λέξη, a, ισούται με:
probability of occurence

όπου Να δηλώνει το πλήθος των κειμένων που περιέχουν την λέξη a και Ν είναι το πλήθος των κειμένων στη συλλογή. Όλες οι μηχανές αναζήτησης έχουν τα στοιχεία αυτά για κάθε όρο στα ευρετήρια. Επομένως μπορούν εύκολα καί γρήγορα να υπολογιστούν οι πιθανότητες. Από τη σχέση (1) προκύπτει ότι:
indepententcount
Η σχέση (2) δίνει μια προσέγγιση της απάντησης. Ως παράδειγμα θα χρησιμοποιήσουμε την βάση του συστήματος i-score του εργαστηρίου Επεξεργασίας πληροφοριών. Η βάση αυτή περιέχει 77400 κείμενα. Στον πίνακα 4 δίδεται το πλήθος των κειμένων που περιέχουν διάφορους συνδιασμούς των όρων του ερωτήματος Q=”vascular gene therapy”.
results from google
Πίνακας 4 Πλήθος κειμένων για συνδυασμούς λέξεων στη βάση του συστήματος i-score.

Με βάση τις τιμές του πίνακα το εκτιμώμενο πλήθος απαντήσεων από τον τύπο (2) είναι μηδέν!. Πράγματι η προσέγγιση αυτή είναι πολύ κακή γιατί η υπόθεσή μας (της ανεξαρτησίας των όρων) είναι κακή επίσης. Μια καλύτερη προσέγγιση του πλήθους των απαντήσεων θα μπορούσε να εκτιμηθεί αν υπολογίζαμε το πλήθος των συνεμφανίσεων δύο λέξεων στα κείμενα. Ωστόσο και αυτή η λύση είναι περιορισμένη, έχει το μειονέκτημα ότι δεν είναι κλιμακώσιμη δηλαδή δεν μπορεί να εφαρμοστεί για ερωτήματα με περισσότερους όρους από τρεις.

Μια τρίτη και πιο αποτελεσματική μέθοδος που χρησιμοποιείται από τις μηχανές αναζήτησης εκτιμά το πλήθος των απαντήσεων σε ένα ερώτημα χρησιμοποιώντας μόνο τις συχνότητες των λέξεων και το μέγεθος του συνόλου των αποτελεσμάτων. Οι μηχανές συνήθως αξιολογούν ένα πολύ μικρό υποσύνολο των αποτελεσμάτων τα οποία έχουν την μεγαλύτερη πιθανότητα να είναι σχετικά. Το υποσύνολο αυτό περιέχει όλα τα κείμενα της συλλογής που έχουν τουλάχιστον ένα κοινό όρο με το ερώτημα. Γενικά δεχόμαστε την υπόθεση ότι ένα κείμενο που περιέχει όλους τους όρους του ερωτήματος είναι σχετικό. Επομένως το πλήθος των σχετικών κειμένων σε ένα ερώτημα ισούται με το min(df(t)), t ∈ Q. Η διαδικασία της αξιολόγησης των κειμένων σε σχέση με ένα ερώτημα ξεκινά από τον όρο του ερωτήματος με τη μικρότερη συχνότητα κειμένων (πλήθος κειμένων που περιέχουν τη λέξη). Έτσι ξεκινώντας από την λέξη του ερωτήματος με τη μικρότερη συχνότητα κειμένων (dfmin) αξιολογούμε ένα μικρό πλήθος κειμένων, έστω s. Ταυτόχρονα υπολογίζουμε το πλήθος των κειμένων από τα s τα οποία περιέχουν όλους τους όρους του ερωτήματος, έστω k. Στη συνέχεια υποθέτουμε ότι τα κείμενα που περιέχουν όλες τις λέξεις του ερωτήματος είναι ομοιόμορφα κατανεμημένες στα κείμενα της απάντησης. Τέλος η εκτίμηση του πλήθους των κειμένων που περιέχουν όλους τους όρους του ερωτήματος γίνεται με αναγωγή από τον τύπο:

min df

Πειραματικά αποτελέσματα με την τελευταία αυτή μέθοδο δίνουν τα καλύτερα αποτελέσματα.

Άσκηση. Υπολογίστε το πλήθος των σχετικών κειμένων στο ερώτημα "vascular gene therapy” για το σύστημα i-score.Λάβετε υπόψη τις συχνότητες συνεμφάνισης των λέξεων που δίδονται στον πίνακα 4 και ότι το μέγεθος της βάσης είναι 77400 κείμενα.