Min Value: Πώς να εκτιμήσεις το πλήθος των διακριτών τιμών

Στο προηγούμενο άρθρο για το Linear Counting είδαμε βασικούς αλγόριθμους για τον υπολογισμό και την εκτίμηση του πλήθους των διακριτών τιμών σε ένα σύνολο δεδομένων. Σήμερα μας περιμένει ένας ακόμη πιθανοτικός αλγόριθμος, που επιτρέπει να εκτιμήσουμε το πλήθος των διακριτών τιμών με αξιοπρεπή ακρίβεια και μικρές απαιτήσεις μνήμης.

Min Value

Σε αυτό το άρθρο θα δουλεύουμε μόνο με πραγματικούς αριθμούς από το μοναδιαίο διάστημα (0, 1). Ας φανταστούμε ένα σύνολο αριθμών από αυτό το διάστημα, που είναι ομοιόμορφα κατανεμημένο, π.χ. το σύνολο αριθμών {0,25; 0,5; 0,75}. Οι γειτονικοί αριθμοί απέχουν πάντα μεταξύ τους (και από το μηδέν και από το ένα) ακριβώς 0,25. Πώς μας βοηθά αυτό να μετρήσουμε το πλήθος των διακριτών στοιχείων;

Αν σου πω ότι έχουμε ένα τέτοιο ομοιόμορφα κατανεμημένο σύνολο αριθμών από το μοναδιαίο διάστημα και ότι οι αριθμοί αυτοί απέχουν μεταξύ τους ακριβώς 0,2 – μπορείς να υπολογίσεις πόσα στοιχεία έχει ένα τέτοιο σύνολο; Φυσικά, πρόκειται για το σύνολο {0,2; 0,4; 0,6; 0,8}, του οποίου ο πληθάριθμος είναι ίσος με τέσσερα. Αν έχουμε στην είσοδο ομοιόμορφα κατανεμημένους αριθμούς από το μοναδιαίο διάστημα και γνωρίζουμε την απόσταση των γειτονικών αριθμών, μπορούμε εύκολα να υπολογίσουμε το πλήθος των στοιχείων.

Η απόσταση ανάμεσα σε γειτονικούς αριθμούς είναι μάλιστα ίση με το ελάχιστο στοιχείο του συνόλου – η απόσταση των γειτονικών στοιχείων του συνόλου {0,25; 0,5; 0,75} είναι 0,25 κ.ο.κ. Για να υπολογίσουμε το πλήθος των στοιχείων ομοιόμορφα κατανεμημένων αριθμών, μας αρκεί να βρούμε με κάποιον τρόπο το ελάχιστο στοιχείο. Τότε μπορούμε να υπολογίσουμε το πλήθος των στοιχείων p με έναν απλό τύπο:

$p = \frac{1}{m} - 1$

όπου m είναι το εν λόγω ελάχιστο στοιχείο.

Και πάλι θα κάνουμε hashing…

Ναι, αλλά πώς να το αξιοποιήσουμε αυτό, αν στην είσοδο έχουμε strings ή άλλες τιμές που δεν ικανοποιούν την προϋπόθεση της ομοιόμορφης κατανομής στο μοναδιαίο διάστημα; Θα βοηθηθούμε πάλι από την παλιά καλή συνάρτηση κατακερματισμού, που για οποιαδήποτε είσοδο μπορεί να μας επιστρέψει έναν ρητό αριθμό από το μοναδιαίο διάστημα. Η κατασκευή μιας τέτοιας συνάρτησης κατακερματισμού θα είναι εύκολη.

Έτσι θα πάρουμε από τα δεδομένα ρητούς αριθμούς, αλλά πώς να φροντίσουμε ώστε αυτοί οι αριθμοί να είναι ομοιόμορφα κατανεμημένοι; Αυτό δεν γίνεται, μπορούμε όμως να βοηθηθούμε αλλιώς. Η συνάρτηση κατακερματισμού, από τη δική μας σκοπιά, συμπεριφέρεται αρκετά «τυχαία». Για πολύ παρόμοιες λέξεις, όπως «ahoj», «ahok» και «ahol», η συνάρτηση κατακερματισμού πιθανότατα θα μας επιστρέφει πολύ διαφορετικά checksum. Με άλλα λόγια: αν κατακερματίσουμε χίλιες διαφορετικές τιμές στο μοναδιαίο διάστημα, είναι πολύ απίθανο η συντριπτική πλειονότητα των αριθμών να είναι π.χ. μικρότερη από το ένα δεύτερο. Αντίθετα, είναι πολύ πιθανό αυτοί οι αριθμοί να είναι κατανεμημένοι λίγο-πολύ κανονικά. Όσο περισσότερα δεδομένα κατακερματίσουμε, τόσο πιο κανονική θα γίνεται η κατανομή.

Από αυτή την ιδέα προκύπτει ένας απλός αλγόριθμος: διατρέχουμε τα δεδομένα εισόδου, κατακερματίζουμε κάθε στοιχείο στο μοναδιαίο διάστημα και θυμόμαστε το ελάχιστο στοιχείο. Το πλήθος των διακριτών στοιχείων το εκτιμάμε με τον προηγούμενο τύπο. Υλοποίηση σε Python:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Η συνάρτηση unit_interval_hash μας επιστρέφει δεκαδικό αριθμό από το διάστημα (0, 1]. Η συνάρτηση count_unique_using_minimum πρώτα μετατρέπει όλες τις τιμές εισόδου ακριβώς σε αυτόν τον αριθμό, βρίσκει το ελάχιστο και επιστρέφει 1 / minimum - 1. Πρόσεξε ότι δεν έχει καμία σημασία πόσες ίδιες τιμές υπάρχουν στο σύνολο δεδομένων – για δύο ίδιες τιμές η συνάρτηση κατακερματισμού θα μας επιστρέψει τον ίδιο ρητό αριθμό, κάτι που δεν επηρεάζει με κανέναν τρόπο το τελικό ελάχιστο. Γι' αυτό με αυτόν τον αλγόριθμο μετράμε το πλήθος των διακριτών στοιχείων.

Ποια είναι τα αποτελέσματα; (Σε κάθε γραμμή βρίσκεται η εκτιμώμενη πληθικότητα· η σωστή πληθικότητα είναι 10.000.)

Μμμ, τίποτα το ιδιαίτερο, έτσι δεν είναι; Ο αλγόριθμος πέρασε δέκα διαφορετικά σύνολα αναγνωριστικών, στα οποία υπήρχαν πάντα δέκα χιλιάδες διακριτές τιμές. Οι εκτιμήσεις που υπολογίστηκαν είναι έτσι ως επί το πλείστον αρκετά εκτός στόχου. Αν τις βγάλουμε μέσο όρο, παίρνουμε την τιμή 18.352. Και πάλι είναι αρκετά εκτός, από την άλλη όμως δες τις απαιτήσεις μνήμης – είναι σταθερές! Για να βρεις το ελάχιστο, σου αρκεί να κρατάς στη μνήμη μία μεταβλητή, στην οποία αποθηκεύεις το τρέχον ελάχιστο, και αυτό είναι όλο. Άρα ναι, η εκτίμηση είναι για τα μπάζα, αλλά πάλι δεν κοστίζει σχεδόν τίποτα.

Βελτιώνουμε

Βλέπουμε ότι ο αλγόριθμος είναι κυρίως ασταθής – μια φορά μας επιστρέφει αρκετά καλή εκτίμηση (9362), την άλλη μια εκτίμηση εντελώς εκτός (65536). Πώς να ξεφύγουμε; Μπορούμε να βοηθηθούμε χωρίζοντας τα δεδομένα εισόδου σε περισσότερα μέρη, υπολογίζοντας το πλήθος των διακριτών στοιχείων για κάθε μέρος και στο τέλος βγάζοντας όλα μαζί ωραία μέσο όρο. Θα μπορούσαμε να αποφασίσουμε με βάση τον πρώτο χαρακτήρα του αναγνωριστικού μας. Έτσι θα υπολογίσουμε χωριστά το πλήθος των διακριτών για τα αναγνωριστικά που αρχίζουν από το γράμμα «a», μετά για αυτά που αρχίζουν από το γράμμα «b» κ.ο.κ. Κώδικας:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Οι αλλαγές βρίσκονται στη συνάρτηση count_unique_using_minimum. Στη μεταβλητή min_values φυλάμε τα ελάχιστα για κάθε ομάδα. Στο τέλος αθροίζουμε όλα τα ελάχιστα και τα διαιρούμε με το πλήθος όλων των αποθηκευμένων τιμών – παίρνουμε το μέσο ελάχιστο. Με την έκφραση 1/average_minimum βρίσκουμε ποιο είναι το μέσο πλήθος των διακριτών τιμών σε κάθε ομάδα – αυτή την τιμή την πολλαπλασιάζουμε ακόμη με το πλήθος των ομάδων και παίρνουμε το εκτιμώμενο πλήθος των διακριτών τιμών στο σύνολο δεδομένων που δόθηκε. Και πώς δουλεύει αυτή η τροποποιημένη διαδικασία;

Λοιπόν, ακόμη δεν είναι καλό, αλλά είναι σίγουρα καλύτερο. Ο αλγόριθμος είναι πιο σταθερός. Μπορούμε να δοκιμάσουμε να τροποποιήσουμε τη συνάρτηση, ώστε οι ομάδες να μην σχηματίζονται με βάση τον πρώτο χαρακτήρα, αλλά π.χ. με βάση τους δύο πρώτους χαρακτήρες του αναγνωριστικού, δηλαδή ως εξής:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Τα αποτελέσματα θα ήταν τότε τέτοια:

Ωωω, αυτό δεν είναι πια και τόσο άσχημο, ε; Αν δοκιμάσουμε ακόμη εκατό χιλιάδες διακριτές τιμές, τους πρώτους δύο χαρακτήρες και n = 24, παίρνουμε αυτά τα αποτελέσματα:

Αρκετά αξιοπρεπές. Αλλά εξακολουθούν να υπάρχουν καλύτεροι αλγόριθμοι, μην ανησυχείς.

Και ποιες είναι οι απαιτήσεις σε μνήμη; Πρέπει να φυλάμε το ελάχιστο για κάθε ομάδα, τίποτα παραπάνω. Αν τα αναγνωριστικά είναι σε δεκαεξαδική μορφή, αυτό σημαίνει ότι πρέπει να θυμόμαστε το πολύ 16^x ελάχιστα, όπου x είναι το πλήθος των χαρακτήρων από τους οποίους φτιάχνουμε το κλειδί της ομάδας. Ένα ελάχιστο είναι ένας ρητός αριθμός, δηλαδή κάποιος τύπος double ή float.

Σημείωση για το τέλος: τον διαχωρισμό της εισόδου σε περισσότερες ομάδες μπορέσαμε να τον κάνουμε επειδή στην είσοδο είχαμε αναγνωριστικά που συμπεριφέρονταν σαν τυχαίο string. Αν στην είσοδο δεν είχαμε τυχαίο string, αλλά δεδομένα σε κάποια συγκεκριμένη μορφή, θα έπρεπε να κάνουμε τον διαχωρισμό αλλιώς. Αν για παράδειγμα κάθε αναγνωριστικό άρχιζε με το πρόθεμα userid-, τότε ο διαχωρισμός σε ομάδες με βάση τον πρώτο χαρακτήρα μάλλον δεν θα δούλευε και πολύ, έτσι δεν είναι;

Κεφάλαια: Linear counting, Min Value, LogLog, HyperLogLog

« Προηγούμενο: Εκτίμηση πλήθους μοναδικών τιμών

Επόμενο: LogLog »