Η ιδέα της ιεραρχίας

Μπορούν οι ομάδες να περιέχουν άλλες ομάδες;

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

Κάθε σημείο ξεκινά ως ξεχωριστή ομάδα
{A}, {B}, {C}, {D}, {E}, {F}
Αφήγηση: Στο πιο λεπτομερές επίπεδο, κάθε σημείο είναι μία ομάδα. Εδώ έχουμε έξι σημεία και έξι ξεχωριστές ομάδες.

Οι μικρές ομάδες σχηματίζουν μεγαλύτερες
{A,B}, {C,D}, {E,F}
Αφήγηση: Ενώνουμε κοντινά σημεία. Έπειτα ενώνουμε ολόκληρες ομάδες. Κάθε νέα ομάδα περιλαμβάνει όλα τα μέλη των ομάδων που συγχωνεύσαμε.

Τα προηγούμενα επίπεδα παραμένουν στο δέντρο
{A,B,C,D}, {E,F}
Αφήγηση: Στο επόμενο επίπεδο, η ομάδα άλφα βήτα και η ομάδα γάμα δέλτα περιέχονται σε μία μεγαλύτερη. Αυτές είναι ένθετες ομάδες.

Μία ιεραρχία, πολλά επίπεδα λεπτομέρειας
{A,B,C,D,E,F}
Αφήγηση: Στην κορυφή, όλα τα σημεία ανήκουν στην ίδια ομάδα. Το δέντρο διατηρεί και τις μικρότερες ομάδες, ώστε να επιλέξουμε το επίπεδο λεπτομέρειας.

Συσσωρευτική και διαιρετική

Ξεκινάμε ενώνοντας ή χωρίζοντας;

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

Συσσωρευτική: έξι ομάδες στην αρχή

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

Οι συγχωνεύσεις συνεχίζονται

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

Διαιρετική: μία ομάδα στην αρχή

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

Η κατεύθυνση δεν καθορίζει μόνη της τη λύση

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

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

Ανάγνωση δενδρογράμματος

Πώς διαβάζουμε ένα δενδρόγραμμα;
Φύλλα: τα αρχικά δείγματα
Αφήγηση: Πώς διαβάζουμε ένα δενδρόγραμμα; Στη βάση βρίσκονται τα έξι δείγματα. Κάθε σύνδεση καταγράφει μία συγχώνευση.

Συγχώνευση 1: E και F
E + F → EF
Ύψος συγχώνευσης: 1
Αφήγηση: Η ομάδα έψιλον ενώνεται με την ομάδα ζήτα, στο ύψος ένα. Η οριζόντια σύνδεση δείχνει την απόσταση της συγχώνευσης.

Συγχώνευση 2: A και B
A + B → AB
Ύψος συγχώνευσης: 2
Αφήγηση: Η ομάδα άλφα ενώνεται με την ομάδα βήτα, στο ύψος δύο. Η οριζόντια σύνδεση δείχνει την απόσταση της συγχώνευσης.

Συγχώνευση 3: C και D
C + D → CD
Ύψος συγχώνευσης: 3
Αφήγηση: Η ομάδα γάμα ενώνεται με την ομάδα δέλτα, στο ύψος τρία. Η οριζόντια σύνδεση δείχνει την απόσταση της συγχώνευσης.

Συγχώνευση 4: AB και CD
AB + CD → ABCD
Ύψος συγχώνευσης: 4
Αφήγηση: Η ομάδα άλφα, βήτα ενώνεται με την ομάδα γάμα, δέλτα, στο ύψος τέσσερα. Η οριζόντια σύνδεση δείχνει την απόσταση της συγχώνευσης.

Συγχώνευση 5: ABCD και EF
ABCD + EF → ABCDEF
Ύψος συγχώνευσης: 5
Αφήγηση: Η ομάδα άλφα, βήτα, γάμα, δέλτα ενώνεται με την ομάδα έψιλον, ζήτα, στο ύψος πέντε. Η οριζόντια σύνδεση δείχνει την απόσταση της συγχώνευσης.

Τομή στο ύψος 3,5: τρεις ομάδες
{A,B}, {C,D}, {E,F}
3 κλάδοι στην τομή → 3 ομάδες
Αφήγηση: Ας κόψουμε το δέντρο στο ύψος τρία κόμμα πέντε. Η γραμμή τέμνει τρεις κλάδους. Οι ομάδες είναι άλφα βήτα, γάμα δέλτα, και έψιλον ζήτα.

Τομή στο ύψος 4,5: δύο ομάδες
{A,B,C,D}, {E,F}
2 κλάδοι στην τομή → 2 ομάδες
Αφήγηση: Ανεβάζουμε την τομή στο τέσσερα κόμμα πέντε. Τώρα η γραμμή τέμνει δύο κλάδους. Παίρνουμε άλφα βήτα γάμα δέλτα, και έψιλον ζήτα.

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

Πίνακας αποστάσεων Manhattan

Πώς κατασκευάζουμε τον πίνακα αποστάσεων;
A=(3,2)   B=(3,0)   C=(1,4)
D=(1,7)   E=(5,6)   F=(6,6)
Αφήγηση: Πώς κατασκευάζουμε τον πίνακα αποστάσεων; Έχουμε τα έξι σημεία των σημειώσεων. Θα υπολογίσουμε όλες τις διαφορετικές αποστάσεις Μανχάταν.

Manhattan: άθροισμα απόλυτων διαφορών
d(P,Q) = |xP−xQ| + |yP−yQ|
Η απόσταση ενός σημείου από τον εαυτό του είναι 0
Αφήγηση: Για κάθε ζευγάρι, αφαιρούμε τις πρώτες συντεταγμένες και παίρνουμε απόλυτη τιμή. Κάνουμε το ίδιο για τις δεύτερες και προσθέτουμε.

Απόσταση A–B
A=(3,2),  B=(3,0)
d(A,B) = |3−3| + |2−0|
= 0 + 2 = 2
Αφήγηση: Για τα σημεία άλφα και βήτα, οι απόλυτες διαφορές είναι μηδέν και δύο. Το άθροισμα είναι δύο. Γράφουμε δύο και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση A–C
A=(3,2),  C=(1,4)
d(A,C) = |3−1| + |2−4|
= 2 + 2 = 4
Αφήγηση: Για τα σημεία άλφα και γάμα, οι απόλυτες διαφορές είναι δύο και δύο. Το άθροισμα είναι τέσσερα. Γράφουμε τέσσερα και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση A–D
A=(3,2),  D=(1,7)
d(A,D) = |3−1| + |2−7|
= 2 + 5 = 7
Αφήγηση: Για τα σημεία άλφα και δέλτα, οι απόλυτες διαφορές είναι δύο και πέντε. Το άθροισμα είναι επτά. Γράφουμε επτά και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση A–E
A=(3,2),  E=(5,6)
d(A,E) = |3−5| + |2−6|
= 2 + 4 = 6
Αφήγηση: Για τα σημεία άλφα και έψιλον, οι απόλυτες διαφορές είναι δύο και τέσσερα. Το άθροισμα είναι έξι. Γράφουμε έξι και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση A–F
A=(3,2),  F=(6,6)
d(A,F) = |3−6| + |2−6|
= 3 + 4 = 7
Αφήγηση: Για τα σημεία άλφα και ζήτα, οι απόλυτες διαφορές είναι τρία και τέσσερα. Το άθροισμα είναι επτά. Γράφουμε επτά και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση B–C
B=(3,0),  C=(1,4)
d(B,C) = |3−1| + |0−4|
= 2 + 4 = 6
Αφήγηση: Για τα σημεία βήτα και γάμα, οι απόλυτες διαφορές είναι δύο και τέσσερα. Το άθροισμα είναι έξι. Γράφουμε έξι και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση B–D
B=(3,0),  D=(1,7)
d(B,D) = |3−1| + |0−7|
= 2 + 7 = 9
Αφήγηση: Για τα σημεία βήτα και δέλτα, οι απόλυτες διαφορές είναι δύο και επτά. Το άθροισμα είναι εννέα. Γράφουμε εννέα και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση B–E
B=(3,0),  E=(5,6)
d(B,E) = |3−5| + |0−6|
= 2 + 6 = 8
Αφήγηση: Για τα σημεία βήτα και έψιλον, οι απόλυτες διαφορές είναι δύο και έξι. Το άθροισμα είναι οκτώ. Γράφουμε οκτώ και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση B–F
B=(3,0),  F=(6,6)
d(B,F) = |3−6| + |0−6|
= 3 + 6 = 9
Αφήγηση: Για τα σημεία βήτα και ζήτα, οι απόλυτες διαφορές είναι τρία και έξι. Το άθροισμα είναι εννέα. Γράφουμε εννέα και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση C–D
C=(1,4),  D=(1,7)
d(C,D) = |1−1| + |4−7|
= 0 + 3 = 3
Αφήγηση: Για τα σημεία γάμα και δέλτα, οι απόλυτες διαφορές είναι μηδέν και τρία. Το άθροισμα είναι τρία. Γράφουμε τρία και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση C–E
C=(1,4),  E=(5,6)
d(C,E) = |1−5| + |4−6|
= 4 + 2 = 6
Αφήγηση: Για τα σημεία γάμα και έψιλον, οι απόλυτες διαφορές είναι τέσσερα και δύο. Το άθροισμα είναι έξι. Γράφουμε έξι και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση C–F
C=(1,4),  F=(6,6)
d(C,F) = |1−6| + |4−6|
= 5 + 2 = 7
Αφήγηση: Για τα σημεία γάμα και ζήτα, οι απόλυτες διαφορές είναι πέντε και δύο. Το άθροισμα είναι επτά. Γράφουμε επτά και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση D–E
D=(1,7),  E=(5,6)
d(D,E) = |1−5| + |7−6|
= 4 + 1 = 5
Αφήγηση: Για τα σημεία δέλτα και έψιλον, οι απόλυτες διαφορές είναι τέσσερα και ένα. Το άθροισμα είναι πέντε. Γράφουμε πέντε και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση D–F
D=(1,7),  F=(6,6)
d(D,F) = |1−6| + |7−6|
= 5 + 1 = 6
Αφήγηση: Για τα σημεία δέλτα και ζήτα, οι απόλυτες διαφορές είναι πέντε και ένα. Το άθροισμα είναι έξι. Γράφουμε έξι και στις δύο συμμετρικές θέσεις του πίνακα.

Απόσταση E–F
E=(5,6),  F=(6,6)
d(E,F) = |5−6| + |6−6|
= 1 + 0 = 1
Αφήγηση: Για τα σημεία έψιλον και ζήτα, οι απόλυτες διαφορές είναι ένα και μηδέν. Το άθροισμα είναι ένα. Γράφουμε ένα και στις δύο συμμετρικές θέσεις του πίνακα.

Ο πίνακας είναι έτοιμος
15 ζεύγη για 6 σημεία
Ελάχιστη απόσταση: d(E,F)=1
Αφήγηση: Ολοκληρώσαμε δεκαπέντε διαφορετικά ζεύγη. Η διαγώνιος είναι μηδενική και ο πίνακας συμμετρικός. Η μικρότερη μη μηδενική απόσταση είναι ένα, μεταξύ έψιλον και ζήτα.

MIN και MAX με τρεις ομάδες

Πώς αλλάζει η συγχώνευση με MIN και MAX;
Ίδια σημεία, ίδιο μέτρο Manhattan
Αλλάζει ο κανόνας απόστασης ομάδων
Αφήγηση: Έχουμε τρεις ομάδες με τρία σημεία η καθεμία. Ποιες δύο θα ενώσουμε; Κρατάμε τα σημεία σταθερά και αλλάζουμε μόνο τον κανόνα απόστασης ομάδων.

MIN: απόσταση ομάδων A–B
(4, 1) και (5, 1)
|4−5| + |1−1|
dMIN(A,B) = 1+0 = 1
Αφήγηση: Για τις ομάδες A και B, κοιτάζουμε τα δύο κοντινότερα σημεία. Η απόσταση Μανχάταν είναι ένα συν μηδέν, ίσον ένα.

MIN: απόσταση ομάδων A–C
(4, 1) και (10, 1)
|4−10| + |1−1|
dMIN(A,C) = 6+0 = 6
Αφήγηση: Για τις ομάδες A και C, κοιτάζουμε τα δύο κοντινότερα σημεία. Η απόσταση Μανχάταν είναι έξι συν μηδέν, ίσον έξι.

MIN: απόσταση ομάδων B–C
(7, 1) και (10, 1)
|7−10| + |1−1|
dMIN(B,C) = 3+0 = 3
Αφήγηση: Για τις ομάδες B και C, κοιτάζουμε τα δύο κοντινότερα σημεία. Η απόσταση Μανχάταν είναι τρία συν μηδέν, ίσον τρία.

MIN: ποιο ζεύγος έχει τη μικρότερη απόσταση;
MIN: AB=1, AC=6, BC=3
Επιλογή: A και B
Αφήγηση: Με τον απλό σύνδεσμο, οι τρεις αποστάσεις είναι ένα, έξι, τρία. Η μικρότερη είναι ένα. Ενώνουμε άλφα και βήτα.

MAX: απόσταση ομάδων A–B
(-4, 1) και (7, 1)
|-4−7| + |1−1|
dMAX(A,B) = 11+0 = 11
Αφήγηση: Για τις ομάδες A και B, κοιτάζουμε τα δύο πιο απομακρυσμένα σημεία. Η απόσταση Μανχάταν είναι έντεκα συν μηδέν, ίσον έντεκα.

MAX: απόσταση ομάδων A–C
(-4, 1) και (12, 1)
|-4−12| + |1−1|
dMAX(A,C) = 16+0 = 16
Αφήγηση: Για τις ομάδες A και C, κοιτάζουμε τα δύο πιο απομακρυσμένα σημεία. Η απόσταση Μανχάταν είναι δεκαέξι συν μηδέν, ίσον δεκαέξι.

MAX: απόσταση ομάδων B–C
(6, 2) και (12, 1)
|6−12| + |2−1|
dMAX(B,C) = 6+1 = 7
Αφήγηση: Για τις ομάδες B και C, κοιτάζουμε τα δύο πιο απομακρυσμένα σημεία. Η απόσταση Μανχάταν είναι έξι συν ένα, ίσον επτά.

MAX: ποιο ζεύγος έχει τη μικρότερη απόσταση;
MAX: AB=11, AC=16, BC=7
Επιλογή: B και C
Αφήγηση: Με τον πλήρη σύνδεσμο, οι αποστάσεις είναι έντεκα, δεκαέξι, επτά. Επιλέγουμε πάλι τη μικρότερη, επτά. Τώρα ενώνουμε βήτα και γάμα.

Και στις δύο περιπτώσεις επιλέγουμε το μικρότερο
MIN: το κοντινότερο ζευγάρι σημείων
MAX: το μακρινότερο ζευγάρι σημείων
Συγχώνευση: μικρότερη απόσταση ομάδων
Αφήγηση: Και οι δύο μέθοδοι συγχωνεύουν το ζευγάρι ομάδων με τη μικρότερη απόσταση. Το μιν και το μαξ ορίζουν πώς υπολογίζουμε αυτή την απόσταση.

Single linkage πλήρης λυμένη άσκηση

Πώς λύνουμε πλήρως μια άσκηση με MIN;
Αποστάσεις σημείων: Manhattan
Απόσταση ομάδων: MIN
Αφήγηση: Πώς λύνουμε πλήρως την άσκηση με τον απλό σύνδεσμο; Ξεκινάμε με έξι ομάδες. Θα δείξουμε κάθε συγχώνευση και όλες τις νέες αποστάσεις.

Βήμα 1: επιλέγουμε τη μικρότερη απόσταση
d(E,F) = 1
E + F → EF
6 ομάδες → 5 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι ένα. Ενώνουμε την ομάδα έψιλον με την ομάδα ζήτα.

Βήμα 1: νέα απόσταση EF–A
d(EF,A)
= min(d(E,A), d(F,A))
= min(6, 7)
= 6
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα άλφα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή έξι.

Βήμα 1: νέα απόσταση EF–B
d(EF,B)
= min(d(E,B), d(F,B))
= min(8, 9)
= 8
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα βήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή οκτώ.

Βήμα 1: νέα απόσταση EF–C
d(EF,C)
= min(d(E,C), d(F,C))
= min(6, 7)
= 6
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα γάμα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή έξι.

Βήμα 1: νέα απόσταση EF–D
d(EF,D)
= min(d(E,D), d(F,D))
= min(5, 6)
= 5
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα δέλτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή πέντε.

Βήμα 1: πίνακας και δενδρόγραμμα
Νέα ομάδα: EF
Ύψος συγχώνευσης: 1
Πλήθος ομάδων: 5
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει πέντε ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος ένα. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 2: επιλέγουμε τη μικρότερη απόσταση
d(A,B) = 2
A + B → AB
5 ομάδες → 4 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι δύο. Ενώνουμε την ομάδα άλφα με την ομάδα βήτα.

Βήμα 2: νέα απόσταση AB–C
d(AB,C)
= min(d(A,C), d(B,C))
= min(4, 6)
= 4
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα από την ομάδα γάμα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή τέσσερα.

Βήμα 2: νέα απόσταση AB–D
d(AB,D)
= min(d(A,D), d(B,D))
= min(7, 9)
= 7
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα από την ομάδα δέλτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή επτά.

Βήμα 2: νέα απόσταση AB–EF
d(AB,EF)
= min(d(A,EF), d(B,EF))
= min(6, 8)
= 6
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα από την ομάδα έψιλον, ζήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή έξι.

Βήμα 2: πίνακας και δενδρόγραμμα
Νέα ομάδα: AB
Ύψος συγχώνευσης: 2
Πλήθος ομάδων: 4
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει τέσσερα ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος δύο. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 3: επιλέγουμε τη μικρότερη απόσταση
d(C,D) = 3
C + D → CD
4 ομάδες → 3 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι τρία. Ενώνουμε την ομάδα γάμα με την ομάδα δέλτα.

Βήμα 3: νέα απόσταση CD–AB
d(CD,AB)
= min(d(C,AB), d(D,AB))
= min(4, 7)
= 4
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας γάμα, δέλτα από την ομάδα άλφα, βήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή τέσσερα.

Βήμα 3: νέα απόσταση CD–EF
d(CD,EF)
= min(d(C,EF), d(D,EF))
= min(6, 5)
= 5
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας γάμα, δέλτα από την ομάδα έψιλον, ζήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή πέντε.

Βήμα 3: πίνακας και δενδρόγραμμα
Νέα ομάδα: CD
Ύψος συγχώνευσης: 3
Πλήθος ομάδων: 3
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει τρεις ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος τρία. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 4: επιλέγουμε τη μικρότερη απόσταση
d(AB,CD) = 4
AB + CD → ABCD
3 ομάδες → 2 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι τέσσερα. Ενώνουμε την ομάδα άλφα, βήτα με την ομάδα γάμα, δέλτα.

Βήμα 4: νέα απόσταση ABCD–EF
d(ABCD,EF)
= min(d(AB,EF), d(CD,EF))
= min(6, 5)
= 5
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα, γάμα, δέλτα από την ομάδα έψιλον, ζήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μικρότερη τιμή, δηλαδή πέντε.

Βήμα 4: πίνακας και δενδρόγραμμα
Νέα ομάδα: ABCD
Ύψος συγχώνευσης: 4
Πλήθος ομάδων: 2
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει δύο ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος τέσσερα. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 5: επιλέγουμε τη μικρότερη απόσταση
d(ABCD,EF) = 5
ABCD + EF → ABCDEF
2 ομάδες → 1 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι πέντε. Ενώνουμε την ομάδα άλφα, βήτα, γάμα, δέλτα με την ομάδα έψιλον, ζήτα.

Βήμα 5: πίνακας και δενδρόγραμμα
Νέα ομάδα: ABCDEF
Ύψος συγχώνευσης: 5
Πλήθος ομάδων: 1
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει μία ομάδα. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος πέντε. Το πλήρες δέντρο ολοκληρώθηκε.

Διαβάζουμε τη λύση για δύο ομάδες
K = 2
{A,B,C,D}, {E,F}
Αφήγηση: Λίγο πριν την τελική συγχώνευση έχουμε δύο ομάδες. Άλφα βήτα γάμα δέλτα, και έψιλον ζήτα. Η πλήρης διαδικασία και οι ενδιάμεσοι πίνακες δείχνουν πώς προέκυψαν.

Complete linkage πλήρης λυμένη άσκηση

Πώς λύνουμε πλήρως μια άσκηση με MAX;
Αποστάσεις σημείων: Manhattan
Απόσταση ομάδων: MAX
Αφήγηση: Πώς λύνουμε πλήρως την άσκηση με τον πλήρη σύνδεσμο; Ξεκινάμε με έξι ομάδες. Θα δείξουμε κάθε συγχώνευση και όλες τις νέες αποστάσεις.

Βήμα 1: επιλέγουμε τη μικρότερη απόσταση
d(E,F) = 1
E + F → EF
6 ομάδες → 5 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι ένα. Ενώνουμε την ομάδα έψιλον με την ομάδα ζήτα.

Βήμα 1: νέα απόσταση EF–A
d(EF,A)
= max(d(E,A), d(F,A))
= max(6, 7)
= 7
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα άλφα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή επτά.

Βήμα 1: νέα απόσταση EF–B
d(EF,B)
= max(d(E,B), d(F,B))
= max(8, 9)
= 9
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα βήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή εννέα.

Βήμα 1: νέα απόσταση EF–C
d(EF,C)
= max(d(E,C), d(F,C))
= max(6, 7)
= 7
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα γάμα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή επτά.

Βήμα 1: νέα απόσταση EF–D
d(EF,D)
= max(d(E,D), d(F,D))
= max(5, 6)
= 6
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας έψιλον, ζήτα από την ομάδα δέλτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή έξι.

Βήμα 1: πίνακας και δενδρόγραμμα
Νέα ομάδα: EF
Ύψος συγχώνευσης: 1
Πλήθος ομάδων: 5
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει πέντε ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος ένα. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 2: επιλέγουμε τη μικρότερη απόσταση
d(A,B) = 2
A + B → AB
5 ομάδες → 4 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι δύο. Ενώνουμε την ομάδα άλφα με την ομάδα βήτα.

Βήμα 2: νέα απόσταση AB–C
d(AB,C)
= max(d(A,C), d(B,C))
= max(4, 6)
= 6
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα από την ομάδα γάμα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή έξι.

Βήμα 2: νέα απόσταση AB–D
d(AB,D)
= max(d(A,D), d(B,D))
= max(7, 9)
= 9
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα από την ομάδα δέλτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή εννέα.

Βήμα 2: νέα απόσταση AB–EF
d(AB,EF)
= max(d(A,EF), d(B,EF))
= max(7, 9)
= 9
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας άλφα, βήτα από την ομάδα έψιλον, ζήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή εννέα.

Βήμα 2: πίνακας και δενδρόγραμμα
Νέα ομάδα: AB
Ύψος συγχώνευσης: 2
Πλήθος ομάδων: 4
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει τέσσερα ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος δύο. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 3: επιλέγουμε τη μικρότερη απόσταση
d(C,D) = 3
C + D → CD
4 ομάδες → 3 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι τρία. Ενώνουμε την ομάδα γάμα με την ομάδα δέλτα.

Βήμα 3: νέα απόσταση CD–AB
d(CD,AB)
= max(d(C,AB), d(D,AB))
= max(6, 9)
= 9
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας γάμα, δέλτα από την ομάδα άλφα, βήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή εννέα.

Βήμα 3: νέα απόσταση CD–EF
d(CD,EF)
= max(d(C,EF), d(D,EF))
= max(7, 6)
= 7
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας γάμα, δέλτα από την ομάδα έψιλον, ζήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή επτά.

Βήμα 3: πίνακας και δενδρόγραμμα
Νέα ομάδα: CD
Ύψος συγχώνευσης: 3
Πλήθος ομάδων: 3
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει τρεις ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος τρία. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 4: επιλέγουμε τη μικρότερη απόσταση
d(CD,EF) = 7
CD + EF → CDEF
3 ομάδες → 2 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι επτά. Ενώνουμε την ομάδα γάμα, δέλτα με την ομάδα έψιλον, ζήτα.

Βήμα 4: νέα απόσταση CDEF–AB
d(CDEF,AB)
= max(d(CD,AB), d(EF,AB))
= max(9, 9)
= 9
Αφήγηση: Υπολογίζουμε την απόσταση της νέας ομάδας γάμα, δέλτα, έψιλον, ζήτα από την ομάδα άλφα, βήτα. Εξετάζουμε όλα τα ζεύγη μεταξύ των δύο ομάδων. Παίρνουμε τη μεγαλύτερη τιμή, δηλαδή εννέα.

Βήμα 4: πίνακας και δενδρόγραμμα
Νέα ομάδα: CDEF
Ύψος συγχώνευσης: 7
Πλήθος ομάδων: 2
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει δύο ομάδες. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος επτά. Οι υπόλοιπες αποστάσεις παραμένουν ίδιες.

Βήμα 5: επιλέγουμε τη μικρότερη απόσταση
d(AB,CDEF) = 9
AB + CDEF → ABCDEF
2 ομάδες → 1 ομάδες
Αφήγηση: Στον τρέχοντα πίνακα, η μικρότερη απόσταση είναι εννέα. Ενώνουμε την ομάδα άλφα, βήτα με την ομάδα γάμα, δέλτα, έψιλον, ζήτα.

Βήμα 5: πίνακας και δενδρόγραμμα
Νέα ομάδα: ABCDEF
Ύψος συγχώνευσης: 9
Πλήθος ομάδων: 1
Αφήγηση: Ο ενημερωμένος πίνακας περιέχει μία ομάδα. Προσθέτουμε τη συγχώνευση στο δενδρόγραμμα, στο ύψος εννέα. Το πλήρες δέντρο ολοκληρώθηκε.

Διαβάζουμε τη λύση για δύο ομάδες
K = 2
{A,B}, {C,D,E,F}
Αφήγηση: Λίγο πριν την τελική συγχώνευση έχουμε δύο ομάδες. Άλφα βήτα, και γάμα δέλτα έψιλον ζήτα. Η πλήρης διαδικασία και οι ενδιάμεσοι πίνακες δείχνουν πώς προέκυψαν.

Σύγκριση δύο δενδρογραμμάτων

Γιατί προέκυψαν διαφορετικές ομάδες;

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

Οι πρώτες τρεις συγχωνεύσεις συμφωνούν
{A,B}, {C,D}, {E,F}
Αφήγηση: Και στις δύο μεθόδους, ενώνουμε πρώτα έψιλον ζήτα, μετά άλφα βήτα και μετά γάμα δέλτα. Έχουμε τις ίδιες τρεις ομάδες.

Στο MIN, η επόμενη απόσταση είναι 4
MIN: d(AB,CD)=4
d(AB,EF)=6, d(CD,EF)=5
Αφήγηση: Με τον απλό σύνδεσμο, οι αποστάσεις των τριών ομάδων είναι τέσσερα, έξι και πέντε. Επιλέγουμε τέσσερα και ενώνουμε άλφα βήτα με γάμα δέλτα.

Στο MAX, η επόμενη απόσταση είναι 7
MAX: d(AB,CD)=9
d(AB,EF)=9, d(CD,EF)=7
Αφήγηση: Με τον πλήρη σύνδεσμο, οι αποστάσεις είναι εννέα, εννέα και επτά. Επιλέγουμε επτά και ενώνουμε γάμα δέλτα με έψιλον ζήτα.

Κρατάμε δύο ομάδες σε κάθε δέντρο
MIN: {A,B,C,D}, {E,F}
MAX: {A,B}, {C,D,E,F}
Αφήγηση: Για δύο ομάδες, το μιν δίνει άλφα βήτα γάμα δέλτα και έψιλον ζήτα. Το μαξ δίνει άλφα βήτα και γάμα δέλτα έψιλον ζήτα.

Η επιλογή linkage επηρεάζει όλη την ιεραρχία
Ίδια δεδομένα και απόσταση σημείων
Διαφορετικό linkage, διαφορετική ιεραρχία
Αφήγηση: Άλλαξε μόνο ο κανόνας απόστασης ομάδων. Γι αυτό η επιλογή του κανόνα πρέπει να ταιριάζει με τη δομή και τον σκοπό της ομαδοποίησης.

Average linkage με πράξεις

Πώς υπολογίζουμε average linkage;
A=(0,0), B=(2,0)
C=(5,0), D=(10,0)
Αφήγηση: Πώς υπολογίζουμε την απόσταση ομάδων με μέσο όρο; Θα δουλέψουμε με τέσσερα σημεία στην ίδια οριζόντια γραμμή.

Ξεκινάμε με τις αποστάσεις σημείων
AB=2, AC=5, AD=10
BC=3, BD=8, CD=5
Πρώτη συγχώνευση: A + B
Αφήγηση: Η απόσταση εδώ είναι η απόλυτη διαφορά των πρώτων συντεταγμένων. Η μικρότερη είναι δύο, μεταξύ άλφα και βήτα. Τα ενώνουμε πρώτα.

Απόσταση της ομάδας AB από το C
Ζεύγη: (A,C), (B,C)
d(AB,C) = (5+3)/2
= 8/2 = 4
Αφήγηση: Για την ομάδα άλφα βήτα και το γάμα, έχουμε δύο ζεύγη. Άλφα γάμα με απόσταση πέντε, και βήτα γάμα με απόσταση τρία. Ο μέσος όρος είναι τέσσερα.

Απόσταση της ομάδας AB από το D
Ζεύγη: (A,D), (B,D)
d(AB,D) = (10+8)/2
= 18/2 = 9
Αφήγηση: Από την ομάδα άλφα βήτα προς το δέλτα, οι αποστάσεις είναι δέκα και οκτώ. Τις προσθέτουμε και διαιρούμε με δύο. Το αποτέλεσμα είναι εννέα.

Επιλέγουμε το μικρότερο από 4, 9 και 5
d(AB,C)=4
d(AB,D)=9, d(C,D)=5
Νέα ομάδα: ABC
Αφήγηση: Οι τρεις αποστάσεις ομάδων είναι τέσσερα, εννέα και πέντε. Η μικρότερη είναι τέσσερα. Άρα ενώνουμε την ομάδα άλφα βήτα με το γάμα.

Η νέα ομάδα έχει τρία μέλη
Ζεύγη: (A,D), (B,D), (C,D)
d(ABC,D) = (10+8+5)/3
= 23/3 ≈ 7,67
Αφήγηση: Τώρα η ομάδα άλφα βήτα γάμα απέχει από το δέλτα σύμφωνα με τρία ζεύγη. Οι αποστάσεις είναι δέκα, οκτώ και πέντε. Διαιρούμε το άθροισμα με τρία.

Κάθε ζεύγος σημείων μετράει εξίσου
d(ABC,D) = (2×9 + 1×5)/3
= 23/3 ≈ 7,67
Δεν παίρνουμε απλώς (9+5)/2
Αφήγηση: Μπορούμε να χρησιμοποιήσουμε τις προηγούμενες αποστάσεις, με σωστά βάρη. Η ομάδα άλφα βήτα συνεισφέρει δύο ζεύγη, ενώ το γάμα ένα.

Η τελική συγχώνευση ολοκληρώνει το δέντρο
Ύψη συγχωνεύσεων:
2, 4, 23/3 ≈ 7,67
Μέσος όρος όλων των μεταξύ ομάδων ζευγών
Αφήγηση: Η τελευταία συγχώνευση γίνεται στο είκοσι τρία τρίτα. Τα ύψη του δέντρου είναι δύο, τέσσερα και περίπου επτά κόμμα εξήντα επτά.

Η συνολική διαδικασία

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

Ορίζουμε απόσταση σημείων και linkage
Απόσταση σημείων: π.χ. Manhattan
Απόσταση ομάδων: MIN, MAX ή average
Αφήγηση: Επιλέγουμε απόσταση σημείων, όπως Μανχάταν ή ευκλείδεια. Έπειτα ορίζουμε απόσταση ομάδων, όπως απλό, πλήρη ή μέσο σύνδεσμο.

Επιλέγουμε τις δύο κοντινότερες ομάδες
Ελάχιστο στοιχείο εκτός διαγωνίου
d(E,F)=1
Αφήγηση: Υπολογίζουμε τον πίνακα. Βρίσκουμε τη μικρότερη απόσταση μεταξύ διαφορετικών ομάδων. Στο παράδειγμα, ενώνουμε πρώτα έψιλον και ζήτα.

Ενημερώνουμε πίνακα και δενδρόγραμμα
Νέα ομάδα: EF
Ενημέρωση όλων των νέων αποστάσεων
Αφήγηση: Αντικαθιστούμε τις δύο ομάδες με τη νέα. Υπολογίζουμε τις αποστάσεις της από τις υπόλοιπες, με τον ίδιο κανόνα. Καταγράφουμε τη συγχώνευση στο δέντρο.

Επαναλαμβάνουμε μέχρι το κριτήριο τερματισμού
6 αρχικές ομάδες, 5 συγχωνεύσεις
Πλήρες δέντρο ή διακοπή σε K ομάδες
Αφήγηση: Για έξι σημεία, πέντε συγχωνεύσεις δίνουν το πλήρες δέντρο. Αν θέλουμε μόνο συγκεκριμένο πλήθος ομάδων, μπορούμε να σταματήσουμε νωρίτερα.

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