Ομαδοποίηση K-Means — Αλγόριθμος και Πώς Λειτουργεί

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

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

Τι βελτιστοποιεί η ομαδοποίηση k-means

Στην τυπική ευκλείδεια μορφή, το k-means προσπαθεί να κάνει τα σημεία μέσα σε κάθε συστάδα όσο το δυνατόν πιο κοντά στο κεντροειδές της συστάδας. Ένας συνηθισμένος στόχος είναι

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Εδώ, το $C_j$ είναι η $j$-οστή συστάδα και το $\mu_j$ είναι το κεντροειδές της.

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

Αυτός ο στόχος εξηγεί τα δύο μέρη του αλγορίθμου:

• Αν τα κεντροειδή είναι σταθερά, η καλύτερη κίνηση είναι να αναθέσουμε κάθε σημείο στο κοντινότερο κεντροειδές.
• Αν οι αναθέσεις είναι σταθερές, το καλύτερο κεντροειδές είναι ο μέσος όρος των σημείων που έχουν ανατεθεί.

Γι’ αυτό ο κανόνας ενημέρωσης δεν είναι αυθαίρετος. Τα "means" στο k-means είναι κυριολεκτικά αριθμητικοί μέσοι.

Πώς λειτουργεί ο αλγόριθμος k-means

Ο συνηθισμένος βρόχος είναι σύντομος:

1. Επίλεξε $k$ αρχικά κεντροειδή.
2. Ανάθεσε κάθε σημείο στο κοντινότερο κεντροειδές.
3. Υπολόγισε ξανά κάθε κεντροειδές ως τον μέσο όρο των σημείων που του έχουν ανατεθεί.
4. Επανάλαβε μέχρι οι αναθέσεις να σταματήσουν να αλλάζουν ή η βελτίωση να γίνει πολύ μικρή.

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

Παράδειγμα ομαδοποίησης k-means βήμα προς βήμα

Πάρε τα παρακάτω μονοδιάστατα σημεία δεδομένων:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Ας υποθέσουμε ότι θέλουμε $k = 2$ συστάδες και ξεκινάμε με κεντροειδή στα $1$ και $10$. Αυτό είναι καλό παράδειγμα επειδή τα κεντροειδή πράγματι μετακινούνται μετά την πρώτη ενημέρωση.

Βήμα 1: ανάθεσε τα σημεία στο κοντινότερο κεντροειδές

Τα σημεία $1, 2, 3$ είναι πιο κοντά στο $1$.

Τα σημεία $10, 11, 12$ είναι πιο κοντά στο $10$.

Άρα οι συστάδες είναι

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Βήμα 2: ενημέρωσε τα κεντροειδή

Το νέο κεντροειδές της πρώτης συστάδας είναι

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Το νέο κεντροειδές της δεύτερης συστάδας είναι

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Και τα δύο κεντροειδή μετακινήθηκαν, από το $1$ στο $2$ και από το $10$ στο $11$.

Βήμα 3: ανάθεσε ξανά

Τώρα έλεγξε ξανά το κοντινότερο κεντροειδές χρησιμοποιώντας τα $2$ και $11$.

Τα σημεία $1, 2, 3$ εξακολουθούν να ανήκουν στην πρώτη συστάδα και τα σημεία $10, 11, 12$ εξακολουθούν να ανήκουν στη δεύτερη συστάδα. Επειδή οι αναθέσεις δεν αλλάζουν πλέον, ο αλγόριθμος έχει συγκλίνει.

Αυτό είναι ένα καθαρό παράδειγμα επειδή τα δεδομένα χωρίζονται φυσικά σε δύο συμπαγείς ομάδες. Τα πραγματικά σύνολα δεδομένων είναι πιο ακατάστατα, και εκεί το k-means μπορεί να αρχίσει να σε παραπλανεί.

Πότε το k-means λειτουργεί καλά

Το k-means λειτουργεί καλύτερα όταν αυτές οι συνθήκες ισχύουν περίπου:

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

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

Συνηθισμένα λάθη στο k-means

Αντιμετώπιση του k-means ως καθολικής μεθόδου ομαδοποίησης

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

Παράβλεψη της κλιμάκωσης χαρακτηριστικών

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

Υπόθεση ότι η απάντηση είναι μοναδική

Το k-means μπορεί να συγκλίνει σε διαφορετικά τοπικά ελάχιστα από διαφορετικά αρχικά σημεία. Γι’ αυτό χρησιμοποιούνται συχνά επαναλαμβανόμενες εκτελέσεις ή μέθοδοι όπως η αρχικοποίηση k-means++.

Χρήση μη αριθμητικών ή κακώς κωδικοποιημένων χαρακτηριστικών

Επειδή τα κεντροειδή είναι μέσοι όροι, το τυπικό k-means είναι φτιαγμένο για αριθμητικές μεταβλητές. Αν ένα χαρακτηριστικό είναι κατηγορικό, ο αριθμητικός μέσος μπορεί να μην έχει νόημα.

Χρήση του σε έντονα μη σφαιρικές συστάδες

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

Να ξεχνάς ότι οι ακραίες τιμές μπορούν να τραβήξουν τα κεντροειδή

Επειδή τα κεντροειδή είναι μέσοι όροι, οι ακραίες τιμές μπορούν να τα μετατοπίσουν αισθητά. Αν οι ακραίες τιμές είναι σημαντικές στα δεδομένα σου, έλεγξέ το πριν εμπιστευτείς το αποτέλεσμα.

Πού χρησιμοποιείται η ομαδοποίηση k-means

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

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

Ένα απλό νοητικό μοντέλο

Φαντάσου ότι τοποθετείς $k$ κινητές πινέζες πάνω σε ένα διάγραμμα διασποράς. Κάθε σημείο συνδέεται με την κοντινότερη πινέζα. Έπειτα κάθε πινέζα γλιστρά στη μέση θέση των σημείων που έχουν συνδεθεί με αυτήν. Επανάλαβε αυτό μέχρι οι πινέζες να σταματήσουν να κινούνται σημαντικά.

Αυτή η εικόνα δεν είναι μόνο διαίσθηση. Είναι σχεδόν ολόκληρος ο αλγόριθμος.

Δοκίμασε ένα παρόμοιο πρόβλημα ομαδοποίησης

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