Τι είναι η ομαδοποίηση K-Means;

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

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

Ορισμός Ομαδοποίησης

Πριν εξετάσουμε τους ακριβείς αλγόριθμους που χρησιμοποιούνται για την εκτέλεση της ομαδοποίησης K-means, ας αφιερώσουμε λίγο χρόνο για να ορίσουμε την ομαδοποίηση γενικά.

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

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

Οι αλγόριθμοι ομαδοποίησης ομαδοποιούν τα στοιχεία με βάση κάποια μέτρηση ομοιότητας. Αυτό γίνεται συχνά με την εύρεση του «κεντρικού» των διαφορετικών πιθανών ομάδων στο σύνολο δεδομένων, αν και όχι αποκλειστικά. Υπάρχει μια ποικιλία διαφορετικών αλγορίθμων ομαδοποίησης, αλλά ο στόχος όλων των αλγορίθμων ομαδοποίησης είναι ο ίδιος, ο προσδιορισμός των εγγενών ομάδων σε ένα σύνολο δεδομένων.

Ομαδοποίηση K-Means

Το K-Means Clustering είναι ένας από τους παλαιότερους και πιο συχνά χρησιμοποιούμενους τύπους αλγορίθμων ομαδοποίησης και λειτουργεί με βάση διανυσματική κβαντοποίηση. Υπάρχει ένα σημείο στο διάστημα που επιλέγεται ως αρχή και, στη συνέχεια, σχεδιάζονται διανύσματα από την αρχή σε όλα τα σημεία δεδομένων στο σύνολο δεδομένων.

Γενικά, η ομαδοποίηση K-means μπορεί να αναλυθεί σε πέντε διαφορετικά βήματα:

• Τοποθετήστε όλα τα στιγμιότυπα σε υποσύνολα, όπου ο αριθμός των υποσυνόλων είναι ίσος με K.
• Βρείτε το μέσο σημείο/κέντρο των κατατμήσεων συμπλέγματος που δημιουργήθηκαν πρόσφατα.
• Με βάση αυτά τα κεντροειδή, αντιστοιχίστε κάθε σημείο σε ένα συγκεκριμένο σύμπλεγμα.
• Υπολογίστε τις αποστάσεις από κάθε σημείο προς τα κεντροειδή και αντιστοιχίστε σημεία στα συμπλέγματα όπου η απόσταση από το κέντρο είναι η ελάχιστη.
• Αφού τα σημεία έχουν αντιστοιχιστεί στα συμπλέγματα, βρείτε το νέο κέντρο των συστάδων.

Τα παραπάνω βήματα επαναλαμβάνονται μέχρι να ολοκληρωθεί η εκπαιδευτική διαδικασία.

Στην αρχική φάση, τα κεντροειδή τοποθετούνται κάπου ανάμεσα στα σημεία δεδομένων.
Φωτογραφία: Weston.pace μέσω wikimedia commons, άδεια GNU Free Documentation (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Εναλλακτικά, μετά την τοποθέτηση των κεντροειδών, μπορούμε να συλλάβουμε την ομαδοποίηση K-means ως εναλλαγή μεταξύ δύο διαφορετικών φάσεων: επισήμανση σημείων δεδομένων και ενημέρωση κεντροειδών.

Στο δεύτερο βήμα, χρησιμοποιείται μια μέτρηση απόστασης όπως η Ευκλείδεια απόσταση για να υπολογιστεί σε ποιο κέντρο βρίσκεται πιο κοντά ένα δεδομένο σημείο και, στη συνέχεια, τα σημεία εκχωρούνται στην κατηγορία αυτού του κέντρου. Φωτογραφία: Weston.pace μέσω Wikimedia Commons, άδεια GNU Free Doc (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

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

Στο τρίτο βήμα, τα centroid μετακινούνται στον μέσο όρο όλων των σημείων δεδομένων. Στη συνέχεια, οι τάξεις επανατοποθετούνται. Φωτογραφία: Weston.pace μέσω Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

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

Πώς να επιλέξετε τη σωστή τιμή για το "K"

Λαμβάνοντας υπόψη ότι η ομαδοποίηση K-means είναι ένας αλγόριθμος χωρίς επίβλεψη και ο αριθμός των κλάσεων δεν είναι γνωστός εκ των προτέρων, πώς αποφασίζετε για τον κατάλληλο αριθμό κλάσεων/τη σωστή τιμή για το K;

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

Ο όρος «τεχνική αγκώνα» προέρχεται από το γεγονός ότι όταν σχεδιάζετε το SSE σε σχέση με τις διαφορετικές τιμές του K, το προκύπτον γραμμικό διάγραμμα θα έχει συχνά σχήμα «αγκώνα», όπου το SSE μειώνεται γρήγορα για τις πρώτες λίγες τιμές του K, αλλά μετά κατεβαίνουν τα επίπεδα. Σε τέτοιες συνθήκες, η τιμή του K που βρίσκεται στον αγκώνα είναι η καλύτερη τιμή για το K, καθώς υπάρχουν ταχύτατα μειωμένες αποδόσεις μετά από αυτήν την τιμή.

Mini-Batch K-Means Clustering

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

Mini-Batch K-σημαίνει ομαδοποίηση είναι μια παραλλαγή της ομαδοποίησης K-means όπου το μέγεθος του συνόλου δεδομένων που εξετάζεται είναι περιορισμένο. Η κανονική ομαδοποίηση K-means λειτουργεί σε ολόκληρο το σύνολο δεδομένων/παρτίδα ταυτόχρονα, ενώ η Mini-batch K-means ομαδοποίηση αναλύει το σύνολο δεδομένων σε υποσύνολα. Οι μίνι-παρτίδες δειγματοληπτούνται τυχαία από ολόκληρο το σύνολο δεδομένων και για κάθε νέα επανάληψη επιλέγεται ένα νέο τυχαίο δείγμα και χρησιμοποιείται για την ενημέρωση της θέσης των κεντροειδών.

Στην ομαδοποίηση Mini-Batch K-Means, τα συμπλέγματα ενημερώνονται με συνδυασμό των τιμών mini-batch και ενός ρυθμού εκμάθησης. Ο ρυθμός εκμάθησης μειώνεται με τις επαναλήψεις και είναι το αντίστροφο του αριθμού των σημείων δεδομένων που τοποθετούνται σε ένα συγκεκριμένο σύμπλεγμα. Το αποτέλεσμα της μείωσης του ρυθμού μάθησης είναι ότι μειώνεται ο αντίκτυπος των νέων δεδομένων και επιτυγχάνεται σύγκλιση όταν, μετά από πολλές επαναλήψεις, δεν υπάρχουν αλλαγές στα clusters.

Αποτελέσματα μελετών σχετικά με την αποτελεσματικότητα της ομαδοποίησης Mini-batch K-means υποδηλώνουν ότι μπορεί να μειώσει επιτυχώς τον υπολογιστικό χρόνο με μια μικρή αντιστάθμιση στην ποιότητα του cluster.

Εφαρμογές K-Means Clustering

Η ομαδοποίηση K-means μπορεί να χρησιμοποιηθεί με ασφάλεια σε οποιαδήποτε κατάσταση όπου τα σημεία δεδομένων μπορούν να τμηματοποιηθούν σε διακριτές ομάδες/τάξεις. Ακολουθούν μερικά παραδείγματα περιπτώσεων κοινής χρήσης για ομαδοποίηση K-mean.

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

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