Τι είναι το KNN (K-Κοντινότεροι Γείτονες);

Τι είναι το K-Nearest Neighbors (KNN);

Το K-Nearest Neighbors είναι μια τεχνική και αλγόριθμος μηχανικής μάθησης που μπορεί να χρησιμοποιηθεί τόσο για εργασίες παλινδρόμησης όσο και για εργασίες ταξινόμησης. K-Κοντινότεροι γείτονες εξετάζει τις ετικέτες ενός επιλεγμένου αριθμού σημείων δεδομένων γύρω από ένα σημείο δεδομένων στόχου, προκειμένου να γίνει μια πρόβλεψη σχετικά με την κλάση στην οποία εμπίπτει το σημείο δεδομένων. Το K-Nearest Neighbors (KNN) είναι ένας εννοιολογικά απλός αλλά πολύ ισχυρός αλγόριθμος και για αυτούς τους λόγους, είναι ένας από τους πιο δημοφιλείς αλγόριθμους μηχανικής μάθησης. Ας κάνουμε μια βαθιά βουτιά στον αλγόριθμο KNN και ας δούμε πώς ακριβώς λειτουργεί. Η καλή κατανόηση του τρόπου λειτουργίας του KNN θα σας επιτρέψει να εκτιμήσετε τις καλύτερες και χειρότερες περιπτώσεις χρήσης για το KNN.

Επισκόπηση των K-Nearest Neighbors (KNN)

Φωτογραφία: Antti Ajanki AnAj μέσω Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Ας οπτικοποιήσουμε ένα σύνολο δεδομένων σε ένα επίπεδο 2D. Φανταστείτε μια δέσμη σημείων δεδομένων σε ένα γράφημα, απλωμένα κατά μήκος του γραφήματος σε μικρές ομάδες. Το KNN εξετάζει την κατανομή των σημείων δεδομένων και, ανάλογα με τα επιχειρήματα που δίνονται στο μοντέλο, διαχωρίζει τα σημεία δεδομένων σε ομάδες. Στη συνέχεια, σε αυτές τις ομάδες αποδίδεται μια ετικέτα. Η κύρια υπόθεση που κάνει ένα μοντέλο KNN είναι ότι τα σημεία/στιγμιότυπα δεδομένων που υπάρχουν σε κοντινή απόσταση μεταξύ τους είναι πολύ παρόμοια, ενώ εάν ένα σημείο δεδομένων είναι μακριά από μια άλλη ομάδα είναι ανόμοιο με αυτά τα σημεία δεδομένων.

Ένα μοντέλο KNN υπολογίζει την ομοιότητα χρησιμοποιώντας την απόσταση μεταξύ δύο σημείων σε ένα γράφημα. Όσο μεγαλύτερη είναι η απόσταση μεταξύ των σημείων, τόσο λιγότερο όμοια είναι. Υπάρχουν πολλοί τρόποι υπολογισμού της απόστασης μεταξύ σημείων, αλλά η πιο κοινή μέτρηση απόστασης είναι απλώς η Ευκλείδεια απόσταση (η απόσταση μεταξύ δύο σημείων σε ευθεία γραμμή).

Το KNN είναι ένας εποπτευόμενος αλγόριθμος εκμάθησης, που σημαίνει ότι τα παραδείγματα στο σύνολο δεδομένων πρέπει να έχουν ετικέτες που τους έχουν εκχωρηθεί/ οι τάξεις τους πρέπει να είναι γνωστές. Υπάρχουν δύο άλλα σημαντικά πράγματα που πρέπει να γνωρίζετε για το KNN. Πρώτον, το KNN είναι ένας μη παραμετρικός αλγόριθμος. Αυτό σημαίνει ότι δεν γίνονται υποθέσεις σχετικά με το σύνολο δεδομένων όταν χρησιμοποιείται το μοντέλο. Αντίθετα, το μοντέλο κατασκευάζεται εξ ολοκλήρου από τα παρεχόμενα δεδομένα. Δεύτερον, δεν υπάρχει διαχωρισμός του συνόλου δεδομένων σε σύνολα εκπαίδευσης και δοκιμών κατά τη χρήση του KNN. Το KNN δεν κάνει γενικεύσεις μεταξύ ενός συνόλου εκπαίδευσης και δοκιμής, επομένως όλα τα δεδομένα εκπαίδευσης χρησιμοποιούνται επίσης όταν ζητείται από το μοντέλο να κάνει προβλέψεις.

Πώς λειτουργεί ένας αλγόριθμος KNN

Ένας αλγόριθμος KNN διέρχεται από τρεις κύριες φάσεις καθώς εκτελείται:

1. Ρύθμιση K στον επιλεγμένο αριθμό γειτόνων.
2. Υπολογισμός της απόστασης μεταξύ ενός παρεχόμενου παραδείγματος/δοκιμής και των παραδειγμάτων δεδομένων.
3. Ταξινόμηση των υπολογισμένων αποστάσεων.
4. Λήψη των ετικετών των κορυφαίων K καταχωρίσεων.
5. Επιστρέφοντας μια πρόβλεψη για το παράδειγμα δοκιμής.

Στο πρώτο βήμα, το K επιλέγεται από τον χρήστη και λέει στον αλγόριθμο πόσοι γείτονες (πόσα γύρω σημεία δεδομένων) πρέπει να ληφθούν υπόψη κατά την απόδοση μιας κρίσης για την ομάδα στην οποία ανήκει το παράδειγμα στόχος. Στο δεύτερο βήμα, σημειώστε ότι το μοντέλο ελέγχει την απόσταση μεταξύ του παραδείγματος στόχου και κάθε παράδειγμα στο σύνολο δεδομένων. Στη συνέχεια, οι αποστάσεις προστίθενται σε μια λίστα και ταξινομούνται. Στη συνέχεια, ελέγχεται η ταξινομημένη λίστα και επιστρέφονται οι ετικέτες για τα κορυφαία στοιχεία K. Με άλλα λόγια, εάν το K οριστεί στο 5, το μοντέλο ελέγχει τις ετικέτες των κορυφαίων 5 πιο κοντινών σημείων δεδομένων στο σημείο δεδομένων στόχου. Κατά την απόδοση μιας πρόβλεψης σχετικά με το σημείο δεδομένων προορισμού, έχει σημασία αν η εργασία είναι α οπισθοδρόμηση or ταξινόμηση έργο. Για μια εργασία παλινδρόμησης, χρησιμοποιείται ο μέσος όρος των κορυφαίων ετικετών K, ενώ ο τρόπος λειτουργίας των κορυφαίων ετικετών K χρησιμοποιείται στην περίπτωση ταξινόμησης.

Οι ακριβείς μαθηματικές πράξεις που χρησιμοποιούνται για την εκτέλεση του KNN διαφέρουν ανάλογα με την επιλεγμένη μέτρηση απόστασης. Εάν θέλετε να μάθετε περισσότερα σχετικά με τον τρόπο υπολογισμού των μετρήσεων, μπορείτε να διαβάσετε για μερικές από τις πιο συνηθισμένες μετρήσεις απόστασης, όπως π.χ. Ευκλείδειος, Μανχάταν, να Minkowski.

Γιατί η αξία του K έχει σημασία

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

Φωτογραφία: Agor153 μέσω Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Οι χαμηλότερες τιμές του K σημαίνουν ότι οι προβλέψεις που παρέχονται από το KNN είναι λιγότερο σταθερές και αξιόπιστες. Για να καταλάβετε γιατί συμβαίνει αυτό, εξετάστε μια περίπτωση όπου έχουμε 7 γείτονες γύρω από ένα σημείο δεδομένων στόχου. Ας υποθέσουμε ότι το μοντέλο KNN λειτουργεί με μια τιμή Κ 2 (του ζητάμε να κοιτάξει τους δύο πλησιέστερους γείτονες για να κάνει μια πρόβλεψη). Εάν η συντριπτική πλειονότητα των γειτόνων (πέντε στους επτά) ανήκει στην κατηγορία Μπλε, αλλά οι δύο πιο κοντινοί γείτονες τυχαίνει να είναι Κόκκινοι, το μοντέλο θα προβλέψει ότι το παράδειγμα ερωτήματος είναι Κόκκινο. Παρά την εικασία του μοντέλου, σε ένα τέτοιο σενάριο το Blue θα ήταν καλύτερη εικασία.

Εάν συμβαίνει αυτό, γιατί να μην επιλέξουμε απλώς την υψηλότερη τιμή K που μπορούμε; Αυτό οφείλεται στο γεγονός ότι λέγοντας στο μοντέλο να λάβει υπόψη πάρα πολλούς γείτονες θα μειώσει επίσης την ακρίβεια. Καθώς αυξάνεται η ακτίνα που θεωρεί το μοντέλο KNN, θα αρχίσει τελικά να εξετάζει σημεία δεδομένων που είναι πιο κοντά σε άλλες ομάδες από ό,τι είναι το σημείο δεδομένων στόχος και θα αρχίσει να εμφανίζεται λανθασμένη ταξινόμηση. Για παράδειγμα, ακόμα κι αν το σημείο που επιλέχθηκε αρχικά βρισκόταν σε μία από τις κόκκινες περιοχές παραπάνω, εάν το K ήταν πολύ ψηλά, το μοντέλο θα έφτανε στις άλλες περιοχές για να εξετάσει τα σημεία. Όταν χρησιμοποιείτε ένα μοντέλο KNN, δοκιμάζονται διαφορετικές τιμές του K για να δουν ποια τιμή δίνει στο μοντέλο την καλύτερη απόδοση.

KNN Πλεονεκτήματα και Μειονεκτήματα

Ας εξετάσουμε μερικά από τα πλεονεκτήματα και τα μειονεκτήματα του μοντέλου KNN.

Πλεονεκτήματα:

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

Το KNN είναι εξαιρετικά ακριβές και απλό στη χρήση. Είναι εύκολο να ερμηνευτεί, να κατανοηθεί και να εφαρμοστεί.

Το KNN δεν κάνει υποθέσεις σχετικά με τα δεδομένα, που σημαίνει ότι μπορούν να χρησιμοποιηθούν για μια μεγάλη ποικιλία προβλημάτων.

Μειονεκτήματα:

Το KNN αποθηκεύει τα περισσότερα ή όλα τα δεδομένα, πράγμα που σημαίνει ότι το μοντέλο απαιτεί πολλή μνήμη και είναι υπολογιστικά ακριβό. Τα μεγάλα σύνολα δεδομένων μπορεί επίσης να κάνουν τις προβλέψεις να διαρκέσουν πολύ.

Το KNN αποδεικνύεται πολύ ευαίσθητο στην κλίμακα του συνόλου δεδομένων και μπορεί να απορριφθεί από άσχετα χαρακτηριστικά αρκετά εύκολα σε σύγκριση με άλλα μοντέλα.

Σύνοψη των K-Nearest Neighbors (KNN)

Το K-Nearest Neighbors είναι ένας από τους απλούστερους αλγόριθμους μηχανικής εκμάθησης. Παρά το πόσο απλό είναι το KNN, στην ιδέα, είναι επίσης ένας ισχυρός αλγόριθμος που δίνει αρκετά υψηλή ακρίβεια στα περισσότερα προβλήματα. Όταν χρησιμοποιείτε το KNN, φροντίστε να πειραματιστείτε με διάφορες τιμές του K για να βρείτε τον αριθμό που παρέχει την υψηλότερη ακρίβεια.