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

K-nearest neighbors (KNN) προβλέπει ένα αποτέλεσμα από τα επισημασμένα παραδείγματα εκπαίδευσης που είναι πιο κοντά σε ένα σημείο ερώτησης. Για ταξινόμηση, οι γείτονες ψηφίζουν για την κατηγορία. Για παλινδρόμηση, οι τιμές στόχου τους μέσονται ή συνδυάζονται με άλλο τρόπο.

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

Βασικά σημεία

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

Πώς λειτουργεί η ταξινόμηση KNN

1. Αναπαραστήστε το ερώτημα και τα παραδείγματα εκπαίδευσης στον ίδιο χώρο χαρακτηριστικών.
2. Υπολογίστε την απόσταση από το ερώτημα στα παραδείγματα εκπαίδευσης.
3. Επιλέξτε τα k πιο κοντινά παραδείγματα.
4. Προβλέψτε την πλειοψηφική κλάση ή χρησιμοποιήστε ψηφοφορία με βάρος απόστασης.

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

Παλινδρόμηση KNN

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

Μετρικές απόστασης

Η ευκλείδεια απόσταση είναι κοινή για συνεχείς χαρακτηριστικά, η απόσταση Manhattan αθροίζει τις απόλυτες διαφορές, και η απόσταση συνημιτόνου εστιάζει στην κατεύθυνση αντί στο μέγεθος. Άλλες μετρικές εφαρμόζονται σε δυαδικά, κατηγορικά, γεωγραφικά, ακολουθιακά ή δεδομένα ενσωματωμένων εκπαιδευμένων αναπαραστάσεων.

Η ονομασία του KNN ως «μη παραμετρικό» σημαίνει ότι δεν υποθέτει μια σταθερή πεπερασμένη-διάστατη λειτουργική μορφή για το όριο απόφασης. Υποθέτει όμως ότι η επιλεγμένη αναπαράσταση και η μετρική καθιστούν τα κοντινά σημεία σχετιζόμενα μεταξύ τους.

Γιατί η κλιμάκωση είναι σημαντική

Αν ένα χαρακτηριστικό κυμαίνεται από 0 έως 1 και ένα άλλο από 0 έως 100.000, η συνηθισμένη ευκλείδεια απόσταση θα κυριαρχηθεί από το δεύτερο χαρακτηριστικό. Η τυποποίηση, η κανονικοποίηση ή οι εξειδικευμένες μετασχηματίσεις πρέπει να προσαρμόζονται στο σύνολο εκπαίδευσης και να εφαρμόζονται στα σύνολα επικύρωσης, δοκιμής και παραγωγής.

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

Επιλογή του k

Με k = 1, το μοντέλο μπορεί να ακολουθήσει τον θόρυβο και παραπλανητικά παραδείγματα. Καθώς το k αυξάνεται, οι προβλέψεις γίνονται πιο ομαλές και λιγότερο ευαίσθητες σε ένα σημείο. Αν το k γίνει πολύ μεγάλο, οι απομακρυσμένες κλάσεις ή περιοχές κυριαρχούν και το μοντέλο υποπροσαρμόζεται.

Επιλέξτε το k μέσω διασταυρούμενης επικύρωσης στα δεδομένα εκπαίδευσης. Για δυαδική ταξινόμηση, ένα μονό k μειώνει αλλά δεν εξαλείφει τις ισοπαλίες. Τα βάρη κλάσεων, οι στρωματοποιημένες διαχωρισμοί, η επιλογή κατωφλίου και οι κατάλληλες μετρικές είναι σημαντικά όταν οι κλάσεις είναι ανισοκατανεμημένες.

Η κατάρα της διαστατικότητας

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

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

Απόδοση αναζήτησης

Μια ερώτηση βίας-δύναμης συγκρίνει το νέο σημείο με κάθε αποθηκευμένο παράδειγμα. Τα δέντρα KD και τα ball trees επιταχύνουν ορισμένες ακριβείς αναζητήσεις, αν και τα οφέλη τους μειώνονται σε υψηλές διαστάσεις. Τα ευρετήρια προσεγγιστικών πλησιέστερων γειτόνων ανταλλάσσουν μικρή απώλεια ανάκλησης για μεγάλη αύξηση στην ταχύτητα και τη μνήμη. Αυτή η ιδέα υποστηρίζει επίσης την αναζήτηση ομοιότητας διανυσμάτων.

Δυνάμεις και περιορισμοί

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

Απόσταση, γειτονιές και συμπεριφορά υπερπαραμέτρων

Το K-nearest neighbors αποθηκεύει τα παραδείγματα εκπαίδευσης και προβλέπει από τα k πιο κοντινά υπό μια επιλεγμένη απόσταση. Η ταξινόμηση χρησιμοποιεί πλειοψηφία ή ψήφο με βάρος απόστασης· η παλινδρόμηση μέσου όρου των στόχων των γειτόνων. Η κλιμάκωση είναι ουσιώδης επειδή ένα χαρακτηριστικό υψηλής εμβέλειας μπορεί να κυριαρχήσει στην ευκλείδεια απόσταση. Κατηγορικά, αραιά, ακολουθιακά ή γεωγραφικά δεδομένα μπορεί να απαιτούν αποστάσεις Hamming, συνημιτόνου, επεξεργασίας, μεγάλης κυκλικής ή εκπαιδευμένες αποστάσεις. Η μετρική είναι μια υπόθεση μοντελοποίησης για την ομοιότητα και πρέπει να επικυρώνεται έναντι της πραγματικής σημασίας των κοντινών περιπτώσεων.

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

Δείκτης, αβεβαιότητα και λειτουργία παραγωγής

Η απλή εκτίμηση συγκρίνει ένα ερώτημα με κάθε σημείο εκπαίδευσης. Τα δέντρα KD και τα ball trees βοηθούν σε κατάλληλες χαμηλές διαστάσεις· τα ευρετήρια προσεγγιστικών πλησιέστερων γειτόνων ανταλλάσσουν την ακρίβεια για ταχύτητα και κλίμακα. Μετρήστε την ανάκληση της αναζήτησης γειτόνων ξεχωριστά από την ποιότητα πρόβλεψης. Η μνήμη περιλαμβάνει αποθηκευμένα χαρακτηριστικά, ετικέτες και δομές ευρετηρίου. Οι ενημερώσεις είναι εννοιολογικά απλές, αλλά μπορεί να απαιτούν επανακατασκευή ευρετηρίου, συνέπεια εκδόσεων και διάδοση διαγραφών. Προστατέψτε τα ευαίσθητα παραδείγματα εκπαίδευσης επειδή η επιστροφή γειτόνων ή αποστάσεων μπορεί να αποκαλύψει εγγραφές.

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

Παράδειγμα εφαρμογής: KNN για αντικατάσταση προϊόντων

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

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

Απόδειξη υλοποίησης και ετοιμότητα λειτουργίας

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

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

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

Έχει το KNN φάση εκπαίδευσης;

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

Είναι το KNN το ίδιο με το K-means;

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

Κύριες αναφορές

• scikit-learn: Nearest Neighbors
• scikit-learn: Cross-validation