Ιεραρχική ομαδοποίηση

Εισαγωγή

Σε αυτό το κεφάλαιο, εξετάζουμε την ιεραρχική ομαδοποίηση (hierarchical clustering), μια ευρέως χρησιμοποιούμενη μέθοδο για την αποκάλυψη φυσικών ομαδοποιήσεων στα δεδομένα. Σε σύγκριση με την ομαδοποίηση K-means, η ιεραρχική ομαδοποίηση είναι συχνά πιο εύκολη στην κατανόηση και στην υλοποίηση. Δεν απαιτεί να οριστεί εκ των προτέρων ο αριθμός των clusters, αλλά παράγει ένα δενδροειδές διάγραμμα γνωστό ως δενδρόγραμμα (dendrogram), το οποίο δείχνει πώς ομαδοποιούνται οι παρατηρήσεις σε διάφορα επίπεδα ομοιότητας.

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

Παρόλο που υπάρχουν δύο κύριοι τύποι ιεραρχικής ομαδοποίησης, εστιάζουμε στην προσέγγιση από κάτω προς τα πάνω (bottom-up), η οποία ξεκινά αντιμετωπίζοντας κάθε παρατήρηση ως ένα δικό της cluster και στη συνέχεια συγχωνεύει διαδοχικά τα πλησιέστερα ζεύγη clusters με βάση μια ορισμένη μετρική απόστασης, χτίζοντας σταδιακά μια ιεραρχική δομή.

Η ιεραρχική ομαδοποίηση σε βάθος

Για αρχή, ας εξετάσουμε το ακόλουθο φανταστικό παράδειγμα. Ας υποθέσουμε ότι θέλουμε να δημιουργήσουμε clusters για τις ακόλουθες παρατηρήσεις με βάση δύο μεταβλητές, τις \(X\) και \(Y\):

Εικόνα 22.1: Διάγραμμα διασποράς των σημείων δεδομένων του παραδείγματος με βάση τις μεταβλητές X και Y.

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

Στο παραπάνω διάγραμμα, είναι σαφές ότι τα δύο σημεία κάτω αριστερά βρίσκονται πιο κοντά το ένα στο άλλο. Αυτά τα δύο σημεία σχηματίζουν λοιπόν το πρώτο cluster:

Εικόνα 22.2: Πρώτο βήμα της ιεραρχικής ομαδοποίησης: οι δύο πλησιέστερες παρατηρήσεις συγχωνεύονται και σχηματίζουν το αρχικό cluster.

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

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

Εικόνα 22.3: Δεύτερο βήμα της ιεραρχικής ομαδοποίησης: σχηματίζεται ένα νέο cluster με τη συγχώνευση των δύο πλησιέστερων παρατηρήσεων.

Τώρα έχουμε δύο clusters που έχουν σχηματιστεί και ένα σημείο δεδομένων που δεν έχει ομαδοποιηθεί. Ο αλγόριθμος συνεχίζει ενώνοντας το μη ομαδοποιημένο σημείο με το πρώτο cluster:

Εικόνα 22.4: Τρίτο βήμα της ιεραρχικής ομαδοποίησης: η παρατήρηση που απομένει χωρίς cluster συγχωνεύεται με το πλησιέστερο υπάρχον cluster.

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

Εικόνα 22.5: Τελικό βήμα της ιεραρχικής ομαδοποίησης: τα δύο μεγαλύτερα clusters συγχωνεύονται σε ένα ενιαίο cluster που περιέχει όλες τις παρατηρήσεις.

Ο αλγόριθμός μας έχει πλέον ολοκληρωθεί. Έχουν δημιουργηθεί όλα τα πιθανά clusters, από το μικρότερο δυνατό (τα μεμονωμένα σημεία δεδομένων) έως το μεγαλύτερο δυνατό (ένα ενιαίο cluster με όλα τα σημεία δεδομένων).

Επειδή ξεκινήσαμε από τα μεμονωμένα σημεία δεδομένων και στη συνέχεια σχηματίσαμε clusters σε όλο και υψηλότερο επίπεδο, ονομάζουμε αυτόν τον τύπο από κάτω προς τα πάνω (bottom-up) ή συσσωρευτική (agglomerative) ομαδοποίηση. Η εναλλακτική θα ήταν μια προσέγγιση από πάνω προς τα κάτω (top-down) ή διαιρετική (divisive), η οποία ξεκινά με όλες τις παρατηρήσεις σε ένα ενιαίο cluster και τις χωρίζει αναδρομικά σε μικρότερα clusters. Η διαιρετική ομαδοποίηση χρησιμοποιείται λιγότερο συχνά από τη συσσωρευτική, κυρίως επειδή είναι υπολογιστικά απαιτητική, αλλά μπορεί να είναι χρήσιμη σε ορισμένες περιπτώσεις όπου η συνολική δομή των δεδομένων αποτυπώνεται καλύτερα με διαδοχικούς διαχωρισμούς παρά με διαδοχικές συγχωνεύσεις. Αυτό μπορεί να φαίνεται παρόμοιο με τα μοντέλα βασισμένα σε δέντρα (βλ. Κεφάλαιο Μοντέλα βασισμένα σε δέντρα), όπου κάθε επόμενος κόμβος αναπαριστά έναν διαχωρισμό των δεδομένων με βάση ένα συγκεκριμένο κριτήριο. Ωστόσο, η βασική διαφορά είναι ότι η διαιρετική ομαδοποίηση είναι μη επιβλεπόμενη και βασίζεται αποκλειστικά στις αποστάσεις ή στις ανομοιότητες μεταξύ των παρατηρήσεων, ενώ τα μοντέλα βασισμένα σε δέντρα είναι επιβλεπόμενα και χωρίζουν τα δεδομένα σύμφωνα με μια μεταβλητή-στόχο, ώστε να βελτιστοποιήσουν την ακρίβεια πρόβλεψης.

Δενδρόγραμμα

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

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

Το δενδρόγραμμα του προηγούμενου παραδείγματός μας είναι το εξής:

Εικόνα 22.6: Δενδρόγραμμα του συνόλου δεδομένων του παραδείγματος, που δείχνει ολόκληρη τη διαδικασία της ιεραρχικής ομαδοποίησης.

Σε αυτό το δενδρόγραμμα, ο οριζόντιος άξονας εμφανίζει τους δείκτες των παρατηρήσεων (αριθμούς γραμμών), ενώ ο κατακόρυφος άξονας δείχνει το ύψος (height) στο οποίο συγχωνεύονται τα clusters, το οποίο αντιστοιχεί στην απόσταση μεταξύ των clusters τη στιγμή της συγχώνευσης.

Αυτό το δενδρόγραμμα αναπαριστά την ίδια ακολουθία συγχωνεύσεων που απεικονίσαμε οπτικά:

  1. Το πρώτο cluster συνδυάζει τις παρατηρήσεις 0 και 1 (το πλησιέστερο ζεύγος).

  2. Στη συνέχεια, συγχωνεύονται οι παρατηρήσεις 2 και 3.

  3. Έπειτα, η παρατήρηση 4 ενώνεται με το cluster που σχηματίζουν τα σημεία 0 και 1.

  4. Τέλος, όλες οι παρατηρήσεις συγχωνεύονται σε ένα cluster στο υψηλότερο επίπεδο.

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

Για παράδειγμα, αν σχεδιάσουμε μια οριζόντια γραμμή κοντά στη μέση του δενδρογράμματος, μπορεί να πάρουμε τρία clusters. Μια χαμηλότερη τομή μπορεί να δώσει περισσότερα (αλλά μικρότερα) clusters, ενώ μια υψηλότερη τομή δίνει λιγότερα (αλλά μεγαλύτερα) clusters.

Αν κόψουμε το δέντρο στο ύψος 4, παίρνουμε 2 clusters, καθώς υπάρχουν δύο γραμμές σε αυτό το ύψος. Σε αυτή την περίπτωση, οι παρατηρήσεις 2 και 3 θα ανήκαν στο πρώτο cluster, ενώ οι υπόλοιπες θα ανήκαν στο δεύτερο cluster:

Εικόνα 22.7: Δενδρόγραμμα με οριζόντια τομή στο ύψος 4, που δίνει δύο clusters.

Τι γίνεται αν αποφασίσουμε να κόψουμε το δέντρο στο ύψος 2 αντί για το ύψος 4;

Εικόνα 22.8: Δενδρόγραμμα με οριζόντια τομή στο ύψος 2, που δίνει τρία clusters.

Αν κόψουμε το δέντρο στο ύψος 2, θα δημιουργηθούν τρία clusters, με το σημείο δεδομένων 4 να εμφανίζεται ως μη συγχωνευμένο ακόμη σε κανένα cluster σε αυτό το ύψος. Ωστόσο, είναι σημαντικό να διευκρινίσουμε ότι το σημείο δεδομένων 4 δεν είναι πραγματικά εκτός cluster: στην ιεραρχική ομαδοποίηση, όλες οι παρατηρήσεις είναι πάντα μέρος της ιεραρχίας. Αυτό που συμβαίνει στην πραγματικότητα είναι ότι μια τομή σε χαμηλότερο ύψος απομονώνει σημεία δεδομένων στα δικά τους μεμονωμένα clusters. Έτσι, στο ύψος 2, το σημείο δεδομένων 4 σχηματίζει ένα cluster ενός στοιχείου (singleton), ενώ τα σημεία 0 και 1, καθώς και τα σημεία 2 και 3, σχηματίζουν τα άλλα δύο clusters.

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

Τομή του δέντρου ακριβώς σε ένα ύψος

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

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

Προσδιορισμός της απόστασης ενός cluster

Ο υπολογισμός της απόστασης μεταξύ δύο μεμονωμένων σημείων δεδομένων είναι απλός με τυπικά μέτρα απόστασης, όπως η ευκλείδεια απόσταση. Ωστόσο, η ιεραρχική ομαδοποίηση αντιμετωπίζει γρήγορα ένα πιο σύνθετο ερώτημα: πώς υπολογίζουμε την απόσταση μεταξύ ενός cluster (που μπορεί να περιέχει πολλά σημεία δεδομένων) και ενός άλλου σημείου ή cluster;

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

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

Εικόνα 22.9: Επιστροφή στο διάγραμμα διασποράς με τα δύο clusters που δημιουργήθηκαν, μαζί με ένα επιπλέον κεντρικό σημείο.

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

  • Απλή σύνδεση (single linkage): Η απόσταση μεταξύ των δύο πλησιέστερων σημείων κάθε cluster (μπλε γραμμή)

  • Πλήρης σύνδεση (complete linkage): Η απόσταση μεταξύ των δύο πιο απομακρυσμένων σημείων κάθε cluster (πράσινη γραμμή)

  • Κεντροειδής σύνδεση (centroid linkage): Η απόσταση μεταξύ των κεντροειδών (γεωμετρικών κέντρων) των δύο clusters (κόκκινη γραμμή)

  • Μέση σύνδεση (average linkage): Η μέση απόσταση μεταξύ όλων των ζευγών σημείων των δύο clusters (δεν φαίνεται ρητά στο διάγραμμα, αλλά εννοιολογικά βρίσκεται ανάμεσα στην απλή και στην πλήρη σύνδεση).

Αυτές είναι γνωστές ως μέθοδοι σύνδεσης (linkage methods), επειδή ορίζουν πώς «συνδέονται» τα clusters κατά τη διαδικασία συγχώνευσης. Κάθε μέθοδος σύνδεσης μπορεί να δώσει διαφορετικό αποτέλεσμα ομαδοποίησης, ακόμη και στο ίδιο σύνολο δεδομένων. Για παράδειγμα, η απλή σύνδεση συχνά παράγει επιμήκη clusters που μοιάζουν με αλυσίδες, ενώ η πλήρης σύνδεση τείνει να σχηματίζει συμπαγή, σφαιρικά clusters. Η μέση και η κεντροειδής σύνδεση βρίσκουν μια ισορροπία ανάμεσα στα δύο άκρα.

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

Υποθέσεις

Η ιεραρχική ομαδοποίηση λειτουργεί με βάση ένα σύνολο υποθέσεων που επηρεάζουν την αποτελεσματικότητά της και, αντίστοιχα, την εγκυρότητα των αποτελεσμάτων της. Η κατανόηση αυτών των υποθέσεων μάς βοηθά να αναγνωρίζουμε πότε η ιεραρχική ομαδοποίηση είναι κατάλληλη και πότε μπορεί να μην είναι η καλύτερη επιλογή (Murtagh & Contreras, 2012· Tan, Steinbach, Karpatne, & Kumar, 2019).

  • Υπάρχει ιεραρχική δομή: Η μέθοδος υποθέτει ότι τα δεδομένα μπορούν να ομαδοποιηθούν φυσικά σε εμφωλευμένα clusters. Δηλαδή, τα μικρά clusters πρέπει να συγχωνεύονται ομαλά σε μεγαλύτερα. Αν η υποκείμενη δομή δεν είναι ιεραρχική, η μέθοδος μπορεί να παράγει παραπλανητικά ή ασταθή αποτελέσματα. Για παράδειγμα, φανταστείτε ένα σύνολο σημείων που είναι όλα διασκορπισμένα τυχαία, χωρίς σαφείς ομάδες. Σε αυτή την περίπτωση, δεν υπάρχουν φυσικά clusters προς συγχώνευση, οπότε η ιεραρχική ομαδοποίηση θα επιβάλει ομαδοποιήσεις που στην πραγματικότητα δεν υπάρχουν.

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

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

Αυτές οι υποθέσεις υπογραμμίζουν τη σημασία του συνδυασμού της ιεραρχικής ομαδοποίησης με τη γνώση του αντικειμένου και την οπτική εξέταση του δενδρογράμματος (Everitt, Landau, Leese, & Stahl, 2011).

Η ιεραρχική ομαδοποίηση στην Python

Για να εφαρμόσουμε την ιεραρχική ομαδοποίηση στην Python, θα εργαστούμε με το σύνολο δεδομένων website_visits, το οποίο χρησιμοποιήθηκε επίσης στο Κεφάλαιο K-Means. Επειδή το σύνολο δεδομένων έχει ήδη παρουσιαστεί, δεν θα το περιγράψουμε ξανά. Ο στόχος μας εδώ είναι να συγκρίνουμε πώς οργανώνει τα δεδομένα η ιεραρχική ομαδοποίηση σε σχέση με το K-means, το οποίο σχημάτισε τέσσερα clusters.

Για αρχή, εισάγουμε το σύνολο δεδομένων και τυποποιούμε τις μεταβλητές Website_Visits και Purchased_Products με το StandardScaler:

import pandas as pd
from sklearn.preprocessing import StandardScaler

# Εισαγωγή του website_visits
website_visits = pd.read_csv("https://raw.githubusercontent.com/Datakortex/Datasets/refs/heads/main/website_visits.csv")

# Εφαρμογή τυποποίησης στις μεταβλητές
scaler = StandardScaler()
website_visits[["Website_Visits", "Purchased_Products"]] = scaler.fit_transform(
  website_visits[["Website_Visits", "Purchased_Products"]]
  )

Το ακόλουθο διάγραμμα διασποράς απεικονίζει τα τυποποιημένα δεδομένα του website_visits:

import seaborn as sns
import matplotlib.pyplot as plt

# Διάγραμμα του website_visits
sns.scatterplot(
  data = website_visits,
  x = "Website_Visits",
  y = "Purchased_Products",
  color = "skyblue",
  )

# Αλλαγή των ετικετών των αξόνων
plt.xlabel("Website Visits");
plt.ylabel("Purchased Products");

# Εμφάνιση του διαγράμματος
plt.show()

Για να εκτελέσουμε την ιεραρχική ομαδοποίηση, χρησιμοποιούμε τη συνάρτηση linkage() από το module scipy.cluster.hierarchy, περνώντας της τις τυποποιημένες στήλες και ένα όρισμα method που ορίζει τη μέθοδο σύνδεσης. Η συνάρτηση linkage() υπολογίζει τις αποστάσεις και εκτελεί την ομαδοποίηση σε μία μόνο κλήση:

from scipy.cluster.hierarchy import linkage

# Ιεραρχική ομαδοποίηση με πλήρη σύνδεση
hclust_website_visits_complete = linkage(
  website_visits[["Website_Visits", "Purchased_Products"]],
  method = "complete"
  )

Σημειώστε ότι η προεπιλεγμένη μέθοδος σύνδεσης στη linkage() είναι η απλή σύνδεση, γι’ αυτό ορίζουμε ρητά method = "complete" παραπάνω. Μπορούμε να επιλέξουμε διαφορετική μέθοδο αλλάζοντας το όρισμα method. Για παράδειγμα, ο ακόλουθος κώδικας χρησιμοποιεί τη μέθοδο της μέσης σύνδεσης:

# Ιεραρχική ομαδοποίηση με μέση σύνδεση
hclust_website_visits_average = linkage(
  website_visits[["Website_Visits", "Purchased_Products"]],
  method = "average"
  )

Τώρα έχουμε δύο διαφορετικά δενδρογράμματα: ένα που δημιουργήθηκε με τη μέθοδο της πλήρους σύνδεσης και ένα με τη μέθοδο της μέσης σύνδεσης. Για να τα οπτικοποιήσουμε, χρησιμοποιούμε τη συνάρτηση dendrogram(), επίσης από το scipy. Αυτή η συνάρτηση δέχεται απευθείας το αποτέλεσμα της linkage() και σχεδιάζει το δέντρο με το matplotlib. Από προεπιλογή, η dendrogram() βάζει επίσης ως ετικέτα σε κάθε φύλλο τον δείκτη της παρατήρησης, αλλά με περίπου 100 παρατηρήσεις αυτές οι ετικέτες επικαλύπτονται και γίνονται δυσανάγνωστες κατά μήκος του άξονα x. Επειδή η ταυτότητα των μεμονωμένων παρατηρήσεων δεν είναι το ζητούμενο εδώ (αυτό που μετράει είναι η δομή των συγχωνεύσεων), ορίζουμε no_labels = True για να τις αφαιρέσουμε εντελώς:

from scipy.cluster.hierarchy import dendrogram

# Διάγραμμα του δενδρογράμματος πλήρους σύνδεσης
dendrogram(hclust_website_visits_complete, no_labels = True);

# Αλλαγή των ετικετών των αξόνων
plt.xlabel("");
plt.ylabel("Height");

# Εμφάνιση του διαγράμματος
plt.show()

# Διάγραμμα του δενδρογράμματος μέσης σύνδεσης
dendrogram(hclust_website_visits_average, no_labels = True);

# Αλλαγή των ετικετών των αξόνων
plt.xlabel("");
plt.ylabel("Height");

# Εμφάνιση του διαγράμματος
plt.show()

Τα δύο δενδρογράμματα είναι παρόμοια, αλλά εξακολουθούν να παρουσιάζουν κάποιες διαφορές. Και στις δύο περιπτώσεις, πολλές παρατηρήσεις ομαδοποιούνται κοντά στο κάτω μέρος, κάτι που δυσκολεύει τη σαφή διάκριση των clusters που σχηματίστηκαν. Για λόγους απλότητας, ας εστιάσουμε στο δενδρόγραμμα που δημιουργήθηκε με τη μέθοδο της πλήρους σύνδεσης. Είναι φανερό ότι η τομή του δέντρου στο ύψος 4 θα έδινε δύο clusters, ενώ η τομή στο ύψος 3 θα έδινε τέσσερα clusters. Μπορούμε να οπτικοποιήσουμε αυτές τις τομές στο δενδρόγραμμα με τη plt.axhline(), η οποία σχεδιάζει μια οριζόντια γραμμή σε ένα διάγραμμα. Για να ορίσουμε το ύψος (την τιμή στον άξονα y), δίνουμε στο όρισμα y την επιθυμητή τιμή:

# Διάγραμμα του δενδρογράμματος πλήρους σύνδεσης με οριζόντιες γραμμές
dendrogram(hclust_website_visits_complete, no_labels = True)

# Προσθήκη οριζόντιων γραμμών στα ύψη 4 και 3
plt.axhline(y = 4, color = "blue")
plt.axhline(y = 3, color = "blue")

# Αλλαγή των ετικετών των αξόνων
plt.xlabel("")
plt.ylabel("Height")

# Εμφάνιση του διαγράμματος
plt.show()

Αυτές οι τομές απλώς απεικονίζονται στο διάγραμμα· το ίδιο το δέντρο δεν έχει κοπεί ακόμη. Για να κόψουμε πραγματικά το δέντρο, χρησιμοποιούμε τη συνάρτηση fcluster() από το scipy, δίνοντας το object hclust_website_visits_complete και ορίζοντας το ύψος της τομής με το όρισμα t μαζί με criterion = "distance":

from scipy.cluster.hierarchy import fcluster

# Τομή του δέντρου στο ύψος 3
clusters_height_3 = fcluster(hclust_website_visits_complete,
                             t = 3,
                             criterion = "distance")

# Εμφάνιση του clusters_height_3
clusters_height_3
array([2, 2, 2, 2, 4, 1, 2, 2, 3, 3, 2, 3, 2, 3, 2, 2, 2, 4, 4,
       4, 4, 4, 2, 1, 3, 2, 3, 2, 2, 3, 2, 2, 4, 3, 2, 2, 2, 2,
       3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 4, 2, 4, 2, 2, 2, 3,
       3, 4, 1, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4], dtype=int32)

Αντί να ορίσουμε το ύψος της τομής, μπορούμε να ορίσουμε απευθείας τον αριθμό των clusters, δίνοντας στο t τον επιθυμητό αριθμό clusters και αλλάζοντας το criterion σε "maxclust". Για παράδειγμα, για να κόψουμε το δέντρο σε 4 clusters, θα χρησιμοποιούσαμε τον ακόλουθο κώδικα:

# Τομή του δέντρου ώστε να σχηματιστούν 4 clusters
fcluster(hclust_website_visits_complete,
         t = 4,
         criterion = "maxclust")
array([2, 2, 2, 2, 4, 1, 2, 2, 3, 3, 2, 3, 2, 3, 2, 2, 2, 4, 4,
       4, 4, 4, 2, 1, 3, 2, 3, 2, 2, 3, 2, 2, 4, 3, 2, 2, 2, 2,
       3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4, 2, 4, 2, 4, 2, 2, 2, 3,
       3, 4, 1, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4], dtype=int32)

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

Η συνάρτηση fcluster() επιστρέφει ένα array που δείχνει σε ποιο cluster ανήκει κάθε παρατήρηση, με τιμές όπως 1 και 2 στην περίπτωση δύο clusters. Για να προσθέσουμε αυτή την πληροφορία στο website_visits, την αποδίδουμε ως νέα στήλη. Τη μετατρέπουμε επίσης σε string, ώστε το Seaborn να την αντιμετωπίζει ως διακριτή κατηγορία και όχι ως συνεχή τιμή κατά τη δημιουργία του διαγράμματος:

# Προσθήκη των clusters στο website_visits
website_visits["Clusters_Height_3"] = clusters_height_3.astype(str)

# Εμφάνιση των πρώτων γραμμών
website_visits.head()
Website_Visits Purchased_Products Clusters_Height_3
0 -1.10 0.71 2
1 -1.00 0.28 2
2 -0.79 0.39 2
3 -0.58 0.39 2
4 1.73 0.71 4

Η στήλη που προστέθηκε δείχνει το cluster στο οποίο ανήκει κάθε παρατήρηση. Με το Seaborn, μπορούμε να οπτικοποιήσουμε τα δεδομένα χρωματίζοντας τα σημεία ανάλογα με τα clusters στα οποία έχουν αντιστοιχιστεί:

# Διάγραμμα του website_visits με τα clusters που σχηματίστηκαν
sns.scatterplot(
  data = website_visits,
  x = "Website_Visits",
  y = "Purchased_Products",
  hue = "Clusters_Height_3",
  hue_order = ["1", "2", "3", "4"]
  )

# Αλλαγή των ετικετών των αξόνων και του υπομνήματος
plt.xlabel("Website Visits")
plt.ylabel("Purchased Products")
plt.legend(title = "Cluster")

# Ορισμός των ορίων των αξόνων
plt.xlim(-3, 3)
plt.ylim(-3, 3)

# Εμφάνιση του διαγράμματος
plt.show()

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

# Τομή του δέντρου ώστε να σχηματιστούν 5 clusters
clusters_k_5 = fcluster(hclust_website_visits_complete,
                        t = 5,
                        criterion = "maxclust")

# Εμφάνιση του clusters_k_5
clusters_k_5

# Προσθήκη των clusters στο website_visits
website_visits["Clusters_K_5"] = clusters_k_5.astype(str)

# Διάγραμμα του website_visits με τα clusters που σχηματίστηκαν
sns.scatterplot(
  data = website_visits,
  x = "Website_Visits",
  y = "Purchased_Products",
  hue = "Clusters_K_5",
  hue_order = ["1", "2", "3", "4", "5"]
  )

# Αλλαγή των ετικετών των αξόνων και του υπομνήματος
plt.xlabel("Website Visits")
plt.ylabel("Purchased Products")
plt.legend(title = "Cluster")

# Ορισμός των ορίων των αξόνων
plt.xlim(-3, 3)
plt.ylim(-3, 3)

# Εμφάνιση του διαγράμματος
plt.show()

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

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

  • Cluster 1 – Πολλές επισκέψεις, λίγες αγορές: Πελάτες που επισκέπτονται συχνά τον ιστότοπο αλλά κάνουν λίγες αγορές

  • Cluster 2 – Λίγες επισκέψεις, λίγες αγορές: Πελάτες που επισκέπτονται σπάνια τον ιστότοπο και κάνουν λίγες αγορές

  • Cluster 3 – Λίγες επισκέψεις, μέτριες αγορές: Πελάτες που επισκέπτονται σπάνια τον ιστότοπο αλλά κάνουν έναν κανονικό/μέτριο αριθμό αγορών

  • Cluster 4 – Λίγες επισκέψεις, πολλές αγορές: Πελάτες που επισκέπτονται σπάνια τον ιστότοπο αλλά κάνουν πολλές αγορές

  • Cluster 5 – Πολλές επισκέψεις, πολλές αγορές: Πελάτες που επισκέπτονται συχνά τον ιστότοπο και κάνουν πολλές αγορές

Πλεονεκτήματα και περιορισμοί

Η ιεραρχική ομαδοποίηση είναι μια ευρέως χρησιμοποιούμενη μέθοδος για την αποκάλυψη φυσικών ομαδοποιήσεων στα δεδομένα, ιδίως όταν η δομή των δεδομένων είναι άγνωστη. Όπως και το K-means, έχει τόσο πλεονεκτήματα όσο και περιορισμούς, που πρέπει να λαμβάνονται υπόψη κατά την εφαρμογή της (Johnson, 1967· Everitt et al., 2011).

Ένα από τα κύρια πλεονεκτήματα της ιεραρχικής ομαδοποίησης είναι η ευελιξία της. Ο αλγόριθμος δεν απαιτεί να επιλεγεί εκ των προτέρων ο αριθμός των clusters· το δενδρόγραμμα αναπαριστά όλες τις πιθανές ομαδοποιήσεις, από τις μεμονωμένες παρατηρήσεις έως ένα ενιαίο cluster που περιέχει ολόκληρο το σύνολο δεδομένων. Αυτό επιτρέπει στους αναλυτές να εξερευνήσουν διαφορετικά επίπεδα λεπτομέρειας και να αποφασίσουν αργότερα πόσα clusters έχουν νόημα. Η ιεραρχική ομαδοποίηση είναι ντετερμινιστική: η εκτέλεση του αλγορίθμου στα ίδια δεδομένα δίνει πάντα το ίδιο αποτέλεσμα, σε αντίθεση με το K-means, το οποίο μπορεί να δώσει διαφορετικά αποτελέσματα ανάλογα με την αρχικοποίηση. Το δενδροειδές δενδρόγραμμα προσφέρει επίσης μια ερμηνεύσιμη οπτική σύνοψη του τρόπου με τον οποίο σχηματίζονται και σχετίζονται τα clusters, κάτι που είναι ιδιαίτερα χρήσιμο στη διερευνητική ανάλυση δεδομένων και σε τομείς όπως η βιοπληροφορική, το μάρκετινγκ και οι κοινωνικές επιστήμες.

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

Παρά τα πλεονεκτήματα αυτά, η ιεραρχική ομαδοποίηση έχει αξιοσημείωτους περιορισμούς. Είναι υπολογιστικά απαιτητική, ιδίως για μεγάλα σύνολα δεδομένων, επειδή εξετάζει όλες τις αποστάσεις μεταξύ ζευγών. Όπως και τα δέντρα αποφάσεων, η ιεραρχική ομαδοποίηση είναι άπληστη (greedy) και μη αναστρέψιμη (irreversible): μόλις συγχωνευθούν δύο clusters, αυτή η απόφαση δεν μπορεί να αναιρεθεί, ακόμη κι αν αποδειχθεί μη βέλτιστη. Τα πρώιμα λάθη στη συγχώνευση μπορούν να μεταδοθούν σε όλη την ιεραρχία, οδηγώντας ενδεχομένως σε κακές αντιστοιχίσεις σε clusters. Η μέθοδος είναι ευαίσθητη στον θόρυβο και στις ακραίες τιμές, οι οποίες μπορούν να αλλοιώσουν το δενδρόγραμμα. Επιπλέον, η επιλογή της μετρικής απόστασης και της μεθόδου σύνδεσης επηρεάζει έντονα τα clusters που προκύπτουν, οδηγώντας ενδεχομένως σε διαφορετικές ερμηνείες των ίδιων δεδομένων. Τέλος, αν και τα δενδρογράμματα είναι κατατοπιστικά, μπορεί να γίνουν φορτωμένα και δύσκολα στην ερμηνεία για μεγάλα σύνολα δεδομένων.

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

Ανακεφαλαίωση

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