Επεξήγηση Αλγορίθμου K-NN (K-Κοντινότερων Γειτόνων με k=3)

Τι σημαίνουν τα αρχικά K-NN;

Τα αρχικά K-NN προέρχονται από τον αγγλικό όρο K-Nearest Neighbors (στα ελληνικά: k-Κοντινότεροι Γείτονες) και ο τίτλος Distance-Weighted K-NN (k=3) σημαίνει: 3 Κοντινότεροι Γείτονες με Στάθμιση Απόστασης.:

NN (Nearest Neighbors): Περιγράφει τη γεωμετρική φύση της μεθόδου. Ο αλγόριθμος αντιμετωπίζει κάθε σενάριο ως σημείο σε έναν πολυδιάστατο χώρο. Όταν εισάγονται νέα δεδομένα, υπολογίζεται η μαθηματική τους απόσταση από τα ήδη γνωστά σημεία.
K: Αντιπροσωπεύει το πλήθος των γειτονικών σημείων που λαμβάνονται υπόψη για την εξαγωγή του συμπεράσματος (στην περίπτωσή μας k=3, ο αλγόριθμος εξετάζει τους 3 πλησιέστερους γείτονες).

Στον δικό μας κώδικα ο αλγόριθμος αναζητά τους 3 πλησιέστερους γείτονες, επομένως πρόκειται για την περίπτωση 3-NN (k=3).

Η βασική αρχή λειτουργίας είναι η εξής: Ο αλγόριθμος δεν επιλέγει απλώς ένα μεμονωμένο σενάριο, αλλά εντοπίζει τα 3 πλησιέστερα "σενάρια" (γραμμές δεδομένων) που βρίσκονται μαθηματικά πιο κοντά στις τρέχουσες καιρικές συνθήκες. Στη συνέχεια, αποφασίζει την τελική ετικέτα της κατηγορίας με βάση τη στάθμιση των αποστάσεών τους (Weighted K-NN), υπολογίζοντας το ειδικό βάρος κάθε γείτονα αντί να βασίζεται σε απλή πλειοψηφία.

1. Αγνόηση των Κατηγοριών

Όταν τρέχει ο κώδικας, ο K-NN δεν ομαδοποιεί αρχικά τα αποτελέσματα σε "ΥΨΗΛΟΣ", "ΑΚΡΑΙΟΣ" κ.λπ. Βλέπει όσα συμπεράσματα περιλαμβάνει η βάση γνώσης ως απλά σημεία σε έναν τρισδιάστατο χώρο. Οι τρεις διαστάσεις αυτού του χώρου είναι:

2. Υπολογισμός "Ευκλείδειας Απόστασης" & Κανονικοποίηση

Ο υπολογισμός της απόστασης ξεκινάει βρίσκοντας τη μαθηματική διαφορά (Δ) μεταξύ των τρεχουσών συνθηκών και των ιστορικών δεδομένων, κάνοντας απλές αφαιρέσεις. Για να κατανοήσουμε πώς ακριβώς λειτουργεί αυτό στην πράξη, ας δούμε ένα παράδειγμα. Ας υποθέσουμε ότι η δική μας βάση δεδομένων περιέχει στο ιστορικό της 70 καταγραφές από το δίκτυο FLAME, και ο σταθμός μας μόλις έστειλε τις εξής ζωντανές μετρήσεις:

Ο αλγόριθμος κάνει την αφαίρεση 70 φορές, συγκρίνοντας το "τώρα" με κάθε μία από τις 70 καταγραφές ξεχωριστά:

...η διαδικασία συνεχίζεται με τον ίδιο τρόπο...

Τι είναι λοιπόν το "Πρότυπο"; Ο όρος πρότυπο (ή σενάριο) αναφέρεται απλώς στην εκάστοτε καταγραφή (π.χ. στην #1, στη #2... μέχρι την #70) με την οποία κάνει την αφαίρεση ο αλγόριθμος στο κάθε βήμα.

Επειδή οι τρεις δείκτες μετριούνται σε εντελώς διαφορετικές κλίμακες (το DFMC παίζει συνήθως στο 0-15, το VPD στο 0-45 και το HDW μπορεί να φτάσει μέχρι 400-600), αν βάζαμε τις διαφορές Δ απευθείας στον τύπο, η τεράστια τιμή του HDW θα «έπνιγε» μαθηματικά τα άλλα δύο.

Για τον λόγο αυτό, ο κώδικας εφαρμόζει κανονικοποίηση (normalization). Διαιρεί την κάθε διαφορά Δ με τη μέγιστη αναμενόμενη τιμή της (45 για το VPD, 15 για το DFMC, 450 για το HDW). Έτσι εξασφαλίζεται ότι και οι τρεις δείκτες έχουν ίση βαρύτητα όταν υπολογίζεται η τελική Ευκλείδεια απόσταση (d) για την κάθε καταγραφή:

3. Η Τελική Επιλογή (Στάθμιση Αποστάσεων - Weighted K-NN)

Ο αλγόριθμος έχει πλέον υπολογίσει την απόσταση d και για τις 70 καταγραφές του ιστορικού.

Αντί να κρατήσει μόνο μία, η λογική του k=3 διαλέγει τις 3 καταγραφές εκείνες που έβγαλαν τις μικρότερες τιμές d. Στη συνέχεια, αντί να εφαρμόσει απλή πλειοψηφία, εισάγει την απόσταση του κάθε γείτονα στον μαθηματικό τύπο w = 1 / d² για να βρει το "βάρος" (w) της ψήφου του. Όσο μικρότερη είναι η απόσταση (d), τόσο ισχυρότερη (μεγαλύτερο βάρος) είναι η ψήφος του. Τέλος, ο αλγόριθμος αθροίζει τα βάρη για κάθε προτεινόμενη κατηγορία κινδύνου και επιλέγει εκείνη με το μεγαλύτερο συνολικό άθροισμα.

Παράδειγμα Στάθμισης (1ο - Άθροιση Βαρών Ίδιων Κατηγοριών): Αν οι 3 κοντινότεροι γείτονες προτείνουν τις κατηγορίες "Υψηλός", "Μέτριος" και "Υψηλός", ο αλγόριθμος υπολογίζει το βάρος (w) του καθενός. Επειδή ο 1ος και ο 3ος γείτονας προτείνουν την ίδια κατηγορία κινδύνου ("Υψηλός"), τα μαθηματικά τους βάρη προστίθενται μαζί. Το τελικό αποτέλεσμα κρίνεται συγκρίνοντας το αθροισμένο βάρος της κατηγορίας "Υψηλός" με το μεμονωμένο βάρος της κατηγορίας "Μέτριος".

Παράδειγμα Στάθμισης (2ο - Υπερίσχυση του Πλησιέστερου): Αν οι 3 γείτονες δώσουν τα αποτελέσματα "Υψηλός", "Μέτριος" και "Μέτριος", στην απλή πλειοψηφία θα κέρδιζε ο "Μέτριος". Όμως, εφαρμόζοντας τη Στάθμιση Αποστάσεων (Weighted K-NN), αν ο γείτονας που δίνει "Υψηλός" ταυτίζεται σχεδόν απόλυτα με τις τρέχουσες συνθήκες (η απόστασή του d τείνει στο μηδέν), το κλάσμα του βάρους του γίνεται τεράστιο (καθώς διαιρούμε με το τετράγωνο μιας πολύ μικρής απόστασης). Έτσι, το βάρος του ενός ξεπερνά με ευκολία το άθροισμα των βαρών των δύο "Μέτριων" (που βρίσκονται πιο μακριά), και το σύστημα επιλέγει σωστά την κατηγορία "Υψηλός". Αυτό εξασφαλίζει ότι το σύστημα "ακούει" πιο δυνατά τις περιπτώσεις που ταυτίζονται απόλυτα με το παρόν.

Παράδειγμα Στάθμισης (3ο - Τρεις εντελώς διαφορετικές προτάσεις): Τι συμβαίνει αν και οι 3 γείτονες προτείνουν εντελώς διαφορετικά αποτελέσματα (π.χ. "Μέτριος", "Υψηλός", "Πολύ Υψηλός"); Σε αυτή την περίπτωση δεν υπάρχει καμία άθροιση βαρών, αφού κάθε κατηγορία εμφανίζεται μόνο μία φορά. Ο αλγόριθμος απλώς συγκρίνει τα τρία μεμονωμένα βάρη (w). Νικητής αναδεικνύεται αυτόματα ο γείτονας με το μεγαλύτερο βάρος, δηλαδή εκείνος που βρέθηκε σε ελάχιστη μαθηματική απόσταση (d) από τα δεδομένα του σταθμού μας.

Τι γίνεται σε περίπτωση ισοπαλίας μεταξύ των βαρών;

Επειδή οι υπολογισμοί των αποστάσεων (d) και των βαρών (w) παράγουν δεκαδικούς αριθμούς με πολύ μεγάλη ακρίβεια (floating points), οι περιπτώσεις απόλυτης μαθηματικής ισοπαλίας μεταξύ των συνολικών βαρών δύο διαφορετικών κατηγοριών είναι πρακτικά απίθανες. Αν ωστόσο προκύψει τέτοιο σπάνιο ενδεχόμενο κατά την άθροιση, ο κώδικας έχει σχεδιαστεί ώστε να δίνει αυτόματα προτεραιότητα στον πλησιέστερο γείτονα που εξετάστηκε πρώτος κατά τη σειρά σάρωσης των δεδομένων.

4. Προσθήκη Υβριδικού Μοντέλου Ασφαλείας (Προστασία Βάσης)

Για την περαιτέρω προστασία του συστήματος από αστοχίες της βάσης, έχει ενσωματωθεί ένα Υβριδικό Μοντέλο Ασφαλείας που λειτουργεί ως δικλείδα. Αυτός ο μηχανισμός παρακάμπτει τη διαδικασία των γειτόνων (K-NN) υπό συγκεκριμένες, ακραίες συνθήκες.

Το μοντέλο αξιολογεί τρεις αυστηρές προϋποθέσεις (οι οποίες ευθυγραμμίζονται με τα πρότυπα του μοντέλου FLAME του Εθνικού Αστεροσκοπείου Αθηνών και τις βαθμονομήσεις από τα πραγματικά δεδομένα των σταθμών του δικτύου Pyromet) και κηρύσσει απευθείας "ΑΚΡΑΙΟ" κίνδυνο εφόσον ισχύει τουλάχιστον μία από αυτές:

Η υγρασία νεκρής καύσιμης ύλης (DFMC) πέσει κάτω από 4.0: Όταν η υγρασία στα λεπτά νεκρά καύσιμα (όπως τα ξερά χόρτα και τα πεσμένα φύλλα) πέφτει κάτω από το 4%, η ευφλεκτότητα της βλάστησης περνάει σε κρίσιμο στάδιο, επιτρέποντας ακαριαία ανάφλεξη από την παραμικρή σπίθα. ή
Ο δείκτης HDW φτάσει ή ξεπεράσει το 600: Ο δείκτης Hot-Dry-Windy σταθμίζει τον συνδυασμό ακραίας ζέστης, ξηρασίας (μέσω του VPD) και ισχυρού ανέμου. Η υπέρβαση του 600 αποτελεί δείκτη-κλειδί για περιβάλλον που μπορεί να δημιουργήσει εκρηκτική, μη ελεγχόμενη εξάπλωση πυρκαγιάς. ή
Το έλλειμμα τάσης υδρατμών (VPD) ξεπεράσει το 40: Αυτό το νούμερο υποδηλώνει μια εξαιρετικά «διψασμένη» ατμόσφαιρα. Ο αέρας έχει τεράστια ικανότητα να απορροφά ραγδαία την υγρασία από το περιβάλλον, ξηραίνοντας ταχύτατα την ύπαιθρο και αυξάνοντας κατακόρυφα τον κίνδυνο.

Λόγω της χρήσης του λογικού τελεστή "ή" (OR - ||) στον κώδικα, η συνθήκη ικανοποιείται με την εμφάνιση έστω και ενός ακραίου παράγοντα. Δεν χρειάζεται να ισχύουν και οι 3 ταυτόχρονα. Αυτό εξασφαλίζει τη μέγιστη δυνατή ευαισθησία, προστατεύοντας άμεσα την περιοχή σε περίπτωση που έστω και ένας δείκτης βρεθεί σε εξαιρετικά κρίσιμο επίπεδο.