Υπολογιστής Εντροπίας - Υπολογισμός Εντροπίας Shannon Online Δωρεάν

Τι είναι ένας υπολογιστής εντροπίας;

Ένας υπολογιστής εντροπίας βρίσκει την εντροπία Shannon ενός συνόλου αριθμών. Η εντροπία Shannon είναι ένας τρόπος μέτρησης του πόσο απρόβλεπτο είναι ένα σύνολο δεδομένων. Ένα σύνολο δεδομένων όπου κάθε τιμή είναι ίδια έχει μηδενική εντροπία, επειδή δεν υπάρχει καμία αβεβαιότητα. Ένα σύνολο δεδομένων όπου κάθε τιμή είναι εξίσου πιθανό να εμφανιστεί έχει τη μεγαλύτερη δυνατή εντροπία για το μέγεθός του.

Η ιδέα προέρχεται από τη θεωρία πληροφορίας, έναν κλάδο που ξεκίνησε ο Αμερικανός μαθηματικός Claude Shannon το 1948. Ο Shannon ήθελε να μετρήσει πόση πληροφορία μεταφέρει ένα μήνυμα. Όρισε την εντροπία ως τη μέση ποσότητα «έκπληξης» σε μια ακολουθία συμβόλων. Ο ίδιος τύπος χρησιμοποιείται πλέον στην επιστήμη δεδομένων, στην κρυπτογραφία, στη βιολογία και στη μηχανική μάθηση, οπουδήποτε χρειάζεται να μετρηθεί η τυχαιότητα σε ένα σύνολο αποτελεσμάτων.

Τύπος της εντροπίας Shannon

Για ένα σύνολο δεδομένων με μοναδικές τιμές x₁ έως xₙ, καθεμία από τις οποίες εμφανίζεται με πιθανότητα p(xᵢ), η εντροπία Shannon H είναι:

$H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)$

Με λόγια: για κάθε μοναδική τιμή, πολλαπλασιάστε την πιθανότητά της με τον λογάριθμο με βάση 2 της πιθανότητας, προσθέστε όλα αυτά τα γινόμενα και, στη συνέχεια, αλλάξτε το πρόσημο. Το αποτέλεσμα είναι πάντα μηδέν ή θετικό.

Αυτός ο υπολογιστής χρησιμοποιεί πάντα λογαρίθμους με βάση 2, επομένως το αποτέλεσμα μετριέται σε bits. Υπάρχουν και άλλες βάσεις για άλλους σκοπούς: ο φυσικός λογάριθμος δίνει μονάδες που ονομάζονται nats, ενώ η βάση 10 δίνει μονάδες που ονομάζονται hartleys. Τα bits είναι η τυπική μονάδα στην πληροφορική και στη θεωρία πληροφορίας, γι’ αυτό ο υπολογιστής χρησιμοποιεί τη βάση 2.

Γιατί το αποτέλεσμα δεν μπορεί να είναι αρνητικό

Κάθε πιθανότητα p(xᵢ) βρίσκεται μεταξύ των 0 και 1, επομένως ο λογάριθμός της είναι μηδενικός ή αρνητικός. Ο πολλαπλασιασμός μιας πιθανότητας με αρνητικό ή μηδενικό λογάριθμο δίνει αρνητικό ή μηδενικό αριθμό. Η άθροιση αυτών των τιμών και η αλλαγή του προσήμου δίνουν πάντα αποτέλεσμα μηδέν ή μεγαλύτερο.

Η μέγιστη δυνατή εντροπία

Για ένα σύνολο δεδομένων με n μοναδικές τιμές, η εντροπία είναι μεγαλύτερη όταν κάθε τιμή εμφανίζεται εξίσου συχνά. Αυτή η μέγιστη τιμή είναι log₂(n) bits. Ένα σύνολο δεδομένων με 4 μοναδικές τιμές που εμφανίζονται εξίσου συχνά μπορεί να φτάσει το πολύ τα 2 bits εντροπίας, επειδή log₂(4) = 2. Οποιαδήποτε άνιση κατανομή των ίδιων 4 τιμών δίνει μικρότερη εντροπία.

Πώς υπολογίζεται η εντροπία: βήμα προς βήμα

1. Καταγράψτε τις μοναδικές τιμές του συνόλου δεδομένων και μετρήστε πόσες φορές εμφανίζεται καθεμία.
2. Διαιρέστε κάθε πλήθος με το συνολικό πλήθος τιμών για να βρείτε την πιθανότητα κάθε μοναδικής τιμής.
3. Υπολογίστε τον λογάριθμο με βάση 2 κάθε πιθανότητας και, στη συνέχεια, πολλαπλασιάστε τον με την ίδια πιθανότητα.
4. Προσθέστε όλα αυτά τα γινόμενα και, στη συνέχεια, πολλαπλασιάστε το άθροισμα με −1.

Αυτός ο υπολογιστής εκτελεί αυτόματα τα ίδια τέσσερα βήματα. Πληκτρολογήστε αριθμούς στο πεδίο εισαγωγής, χωρισμένους με κενά ή κόμματα, επιλέξτε την αντίστοιχη μορφή και η εντροπία, ο πίνακας πιθανοτήτων και ένα ραβδόγραμμα εμφανίζονται αμέσως. Ένας πίνακας κάτω από το αποτέλεσμα εμφανίζει την τιμή, το πλήθος, την πιθανότητα και το p(x) × log₂(p(x)) για κάθε μοναδικό αριθμό, ώστε να φαίνονται οι υπολογισμοί και όχι μόνο η τελική απάντηση.

Κανόνες εισαγωγής

• Γίνονται δεκτές μόνο αριθμητικές τιμές: ακέραιοι, δεκαδικοί και αρνητικοί αριθμοί λειτουργούν κανονικά.
• Οι τιμές χωρίζονται με κενά (παράδειγμα: 1 2 3 4) ή με κόμματα (παράδειγμα: 1,2,3,4), ανάλογα με την επιλεγμένη μορφή.
• Ένα σύνολο δεδομένων μπορεί να περιέχει έως 100.000 τιμές. Η εισαγωγή περισσότερων εμφανίζει μήνυμα σφάλματος που ζητά μικρότερο σύνολο δεδομένων.
• Η επιστημονική γραφή γίνεται δεκτή, επομένως το 1e3 διαβάζεται ως 1000.
• Κείμενο, σύμβολα ή κενές καταχωρίσεις μεταξύ διαχωριστών απορρίπτονται με σφάλμα και δεν αγνοούνται σιωπηρά.
• Απορρίπτεται επίσης ένας αριθμός που είναι υπερβολικά μεγάλος για αποθήκευση από υπολογιστή, όπως το 1e400. Η μεγαλύτερη τιμή που μπορεί να αποθηκεύσει ο υπολογιστής είναι περίπου 1,8 x 10^308.

Λυμένο παράδειγμα

Έστω το σύνολο δεδομένων 1 2 3 1 2 1, το οποίο έχει έξι αριθμούς.

Αρχικά, μετρήστε κάθε μοναδική τιμή:

Στη συνέχεια, εφαρμόστε τον τύπο σε κάθε γραμμή και προσθέστε τα αποτελέσματα:

$H = -(0.5 \log_2 0.5 + 0.3333 \log_2 0.3333 + 0.1667 \log_2 0.1667)$ $H = -(0.5 \times -1 + 0.3333 \times -1.585 + 0.1667 \times -2.585)$ $H \approx 1.4591 \text{ bits}$

Το σύνολο δεδομένων έχει 3 μοναδικές τιμές, επομένως η μέγιστη δυνατή εντροπία είναι log₂(3) ≈ 1,585 bits. Το πραγματικό αποτέλεσμα, 1,4591 bits, είναι μικρότερο από αυτή τη μέγιστη τιμή, επειδή η τιμή 1 εμφανίζεται συχνότερα από τις άλλες, καθιστώντας το σύνολο δεδομένων ελαφρώς λιγότερο τυχαίο από μια απολύτως ομοιόμορφη κατανομή.

Ένα σύνολο δεδομένων χωρίς αβεβαιότητα

Το σύνολο δεδομένων 5 5 5 5 5 έχει μόνο μία μοναδική τιμή, επομένως η πιθανότητά της είναι 1. Εφόσον log₂(1) = 0, κάθε όρος του αθροίσματος είναι μηδενικός και η εντροπία είναι ακριβώς 0 bits. Δεν υπάρχει καμία αβεβαιότητα σε ένα σύνολο δεδομένων όπου κάθε τιμή είναι ίδια.

Ερμηνεία του αποτελέσματος

• Εντροπία κοντά στο 0 σημαίνει ότι τα δεδομένα είναι επαναλαμβανόμενα και προβλέψιμα. Μία ή λίγες τιμές κυριαρχούν.
• Εντροπία κοντά στο log₂(n), όπου n είναι το πλήθος των μοναδικών τιμών, σημαίνει ότι τα δεδομένα είναι σχεδόν ομοιόμορφα κατανεμημένα σε όλες τις μοναδικές τιμές τους.
• Εντροπία ακριβώς ίση με 0 σημαίνει ότι κάθε τιμή του συνόλου δεδομένων είναι ίδια.

Η εντροπία από μόνη της δεν δείχνει αν ένα σύνολο δεδομένων είναι «καλό» ή «κακό». Μια γεννήτρια κωδικών πρόσβασης θέλει υψηλή εντροπία, επειδή έτσι ο κωδικός γίνεται δύσκολο να μαντευτεί. Ένας αισθητήρας που πρέπει να καταγράφει σταθερή θερμοκρασία θέλει χαμηλή εντροπία, επειδή αυτό σημαίνει ότι η ένδειξη είναι σταθερή.

Πού χρησιμοποιείται η εντροπία Shannon

• Μηχανική μάθηση: οι αλγόριθμοι δέντρων αποφάσεων χρησιμοποιούν την εντροπία για να αποφασίσουν ποιο χαρακτηριστικό χωρίζει καλύτερα ένα σύνολο δεδομένων σε προβλέψιμες ομάδες.
• Συμπίεση δεδομένων: η εντροπία θέτει το θεωρητικό όριο για το πόσο μικρό μπορεί να γίνει ένα αρχείο μέσω συμπίεσης χωρίς απώλεια πληροφοριών.
• Κρυπτογραφία: η εντροπία μετρά πόσο απρόβλεπτος είναι ένας κωδικός πρόσβασης ή ένα κρυπτογραφικό κλειδί.
• Γενετική: η εντροπία μπορεί να αναδείξει ασυνήθιστες ή ιδιαίτερα μεταβλητές περιοχές σε μια ακολουθία DNA.
• Ανάλυση κειμένου: αν τα γράμματα ή οι λέξεις θεωρηθούν «τιμές», η εντροπία μπορεί να μετρήσει πόσο προβλέψιμο είναι ένα τμήμα κειμένου.

Συχνές ερωτήσεις

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

Πώς υπολογίζεται η εντροπία Shannon με το χέρι; Μετρήστε πόσο συχνά εμφανίζεται κάθε μοναδική τιμή, διαιρέστε κάθε πλήθος με το σύνολο για να βρείτε τις πιθανότητες, πολλαπλασιάστε κάθε πιθανότητα με τον λογάριθμό της με βάση 2, προσθέστε τα αποτελέσματα και πολλαπλασιάστε με −1.

Μπορεί η εντροπία να είναι αρνητική; Όχι. Η μικρότερη δυνατή τιμή είναι 0 bits, και προκύπτει όταν κάθε τιμή του συνόλου δεδομένων είναι ίδια.

Ποια είναι η μέγιστη εντροπία για ένα σύνολο δεδομένων; Η μέγιστη τιμή είναι log₂(n) bits, όπου n είναι ο αριθμός των μοναδικών τιμών, και εμφανίζεται μόνο όταν κάθε μοναδική τιμή εμφανίζεται εξίσου συχνά.

Υπάρχει όριο στο μέγεθος του συνόλου δεδομένων; Ναι. Αυτός ο υπολογιστής δέχεται έως 100.000 τιμές σε ένα σύνολο δεδομένων. Οι μεγαλύτερες εισόδους επιστρέφουν σφάλμα.

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

Παραπομπές

1. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423.
2. Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2η έκδ.). Wiley-Interscience.
3. MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.