01_KMeans_Η_ιδέα
1. Πώς βρίσκουμε Κ ομάδες;
K-means: ομάδες γύρω από κέντρα

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

2. Επιλέγουμε Κ = 2
Το πλήθος ομάδων δίνεται από εμάς.
Κ = 2
Αρχικά κέντρα: C₁, C₂
Αφήγηση: Εδώ ζητάμε δύο ομάδες. Το κάπα το επιλέγουμε εμείς. Ο αλγόριθμος δεν ανακαλύπτει αυτόματα πόσες ομάδες χρειαζόμαστε.

3. Κάθε σημείο στο κοντινότερο κέντρο
Σύγκριση ευκλείδειων αποστάσεων
Σημείο → κοντινότερο κέντρο
Αφήγηση: Κάθε σημείο ανατίθεται στο κοντινότερο κέντρο, με βάση την ευκλείδεια απόσταση. Το χρώμα δείχνει την ομάδα του.

4. Το κέντρο είναι ο μέσος όρος
Υπολογίζουμε μέσο όρο ανά συντεταγμένη.
C = (μέσος x, μέσος y)
Αφήγηση: Για κάθε ομάδα υπολογίζουμε τον μέσο όρο των συντεταγμένων των μελών της. Το νέο κέντρο δεν χρειάζεται να είναι πραγματικό δείγμα.

5. Ανάθεση → νέα κέντρα → επανάληψη
Στόχος: μικρό άθροισμα τετραγωνικών αποστάσεων
SSE = Σ ‖x − Cομάδας‖²
Αφήγηση: Επαναλαμβάνουμε αναθέσεις και ενημερώσεις. Έτσι μειώνουμε το άθροισμα των τετραγωνικών αποστάσεων των σημείων από τα κέντρα τους.

02_KMeans_Αρχικοποίηση
1. Από πού ξεκινούν τα κέντρα;
Ίδια δεδομένα, διαφορετικό ξεκίνημα

Αφήγηση: Από πού ξεκινούν τα κέντρα; Πριν κάνουμε οποιαδήποτε ανάθεση, χρειαζόμαστε δύο αρχικές θέσεις.

2. Τυχαία επιλογή αρχικών κέντρων
Παράδειγμα: επιλογή δύο δειγμάτων
C₁ = (1, 1)
C₂ = (4, 3)
Αφήγηση: Μια συνηθισμένη αρχικοποίηση επιλέγει τυχαία δύο δείγματα ως κέντρα. Μπορεί όμως να βρίσκονται κοντά στην ίδια περιοχή.

3. Ένα διαφορετικό ξεκίνημα
Διαφορετικές πρώτες αναθέσεις
C₁ = (1, 1)
C₂ = (8, 9)
Αφήγηση: Αν ξεκινήσουμε με κέντρα σε διαφορετικές περιοχές, οι πρώτες αναθέσεις αλλάζουν. Το ίδιο σύνολο μπορεί να οδηγήσει σε διαφορετικό τελικό αποτέλεσμα.

4. K-means++: πιο απλωμένα κέντρα
Η επιλογή παραμένει πιθανοτική.
Πιθανότητα ∝ D(x)²
D(x): απόσταση από κοντινότερο κέντρο
Αφήγηση: Το κάπα μινς πλας πλας ξεκινά με ένα τυχαίο κέντρο. Τα επόμενα επιλέγονται με πιθανότητα ανάλογη του τετραγώνου της απόστασης από το κοντινότερο ήδη επιλεγμένο κέντρο.

5. Δοκιμάζουμε περισσότερα ξεκινήματα
Κρατάμε το αποτέλεσμα με μικρότερο SSE.
Πολλές αρχικοποιήσεις
Επιλογή μικρότερου SSE
Αφήγηση: Μπορούμε να κάνουμε πολλές αρχικοποιήσεις και να κρατήσουμε εκείνη με το μικρότερο σφάλμα. Αυτό βοηθά, αλλά δεν εγγυάται την καλύτερη δυνατή λύση.

03_Ανάθεση_Ευκλείδεια_2D
1. Σε ποιο κέντρο θα πάει το P;
Ένα σημείο, δύο κέντρα, δύο υπολογισμοί
P = (3, 4)
C₁ = (1, 1)    C₂ = (7, 7)
Αφήγηση: Σε ποιο κέντρο θα πάει το σημείο πι; Έχουμε πι ίσο με τρία, τέσσερα, και δύο κέντρα: ένα, ένα και επτά, επτά.

2. Υπολογίζουμε απόσταση από το C₁
Τετραγωνίζουμε τις διαφορές και αθροίζουμε.
d(P,C₁) = √[(3−1)² + (4−1)²]
= √(4 + 9) = √13 ≈ 3,61
Αφήγηση: Προς το πρώτο κέντρο οι διαφορές είναι δύο και τρία. Η ευκλείδεια απόσταση είναι ρίζα του τέσσερα συν εννέα, δηλαδή περίπου τρία κόμμα εξήντα ένα.

3. Υπολογίζουμε απόσταση από το C₂
Ίδιος τύπος, δεύτερο κέντρο
d(P,C₂) = √[(3−7)² + (4−7)²]
= √(16 + 9) = √25 = 5
Αφήγηση: Προς το δεύτερο κέντρο οι διαφορές είναι μείον τέσσερα και μείον τρία. Τα τετράγωνα δίνουν δεκαέξι συν εννέα. Η απόσταση είναι πέντε.

4. Συγκρίνουμε και αναθέτουμε
Το P ανήκει στην ομάδα του C₁.
3,61 < 5
P → ομάδα 1
Αφήγηση: Τρία κόμμα εξήντα ένα είναι μικρότερο από πέντε. Άρα αναθέτουμε το πι στην ομάδα του πρώτου κέντρου.

5. Για την ανάθεση αρκούν τα τετράγωνα
Η σειρά των αποστάσεων παραμένει ίδια.
d₁² = 13 < d₂² = 25
Ίδια ανάθεση χωρίς τις ρίζες
Αφήγηση: Μπορούμε να συγκρίνουμε κατευθείαν δεκατρία και είκοσι πέντε. Δεν χρειάζονται οι τετραγωνικές ρίζες για να βρούμε το κοντινότερο κέντρο.

04_Ανάθεση_Manhattan_2D
1. Τι αλλάζει με απόσταση Manhattan;
Μετράμε διαφορές ανά άξονα.
P = (3, 4)
C₁ = (1, 1)    C₂ = (7, 7)
Αφήγηση: Τι αλλάζει αν χρησιμοποιήσουμε απόσταση Μανχάταν; Στο ίδιο παράδειγμα, προσθέτουμε τις απόλυτες διαφορές των δύο συντεταγμένων.

2. Απόσταση Manhattan προς C₁
Δεν χρησιμοποιούμε τετράγωνα ή ρίζα.
d₁(P,C₁) = |3−1| + |4−1|
= 2 + 3 = 5
Αφήγηση: Προς το πρώτο κέντρο, η απόσταση είναι απόλυτο τρία μείον ένα, συν απόλυτο τέσσερα μείον ένα. Δηλαδή δύο συν τρία, ίσον πέντε.

3. Απόσταση Manhattan προς C₂
Οριζόντια διαφορά + κατακόρυφη διαφορά
d₁(P,C₂) = |3−7| + |4−7|
= 4 + 3 = 7
Αφήγηση: Προς το δεύτερο κέντρο έχουμε απόλυτο τρία μείον επτά, συν απόλυτο τέσσερα μείον επτά. Δηλαδή τέσσερα συν τρία, ίσον επτά.

4. Η ανάθεση προκύπτει από τη σύγκριση
Εδώ και τα δύο μέτρα επιλέγουν C₁.
5 < 7 → ομάδα 1
Αφήγηση: Πέντε μικρότερο από επτά, άρα το πι πηγαίνει στην πρώτη ομάδα. Εδώ η επιλογή συμφωνεί με την ευκλείδεια. Αυτό δεν συμβαίνει υποχρεωτικά σε κάθε παράδειγμα.

5. Manhattan και ενημέρωση κέντρων
K-means: μέσος όρος · K-medians: διάμεσος
K-means → τετραγωνική L₂ → μέσοι όροι
K-medians → L₁ → διάμεσοι
Αφήγηση: Προσοχή: ο κλασικός κάπα μινς ελαχιστοποιεί τετραγωνικές ευκλείδειες αποστάσεις. Για στόχο Μανχάταν, ενημερώνουμε με διαμέσους ανά χαρακτηριστικό: κάπα μίντιανς.

05_Ευκλείδεια_5D
1. Πώς κάνουμε ανάθεση σε 5 διαστάσεις;
Δεν χρειαζόμαστε εικόνα του χώρου.
P  = (1, 2, 3, 4, 5)
C₁ = (1, 2, 1, 4, 3)
C₂ = (3, 4, 3, 6, 5)
Αφήγηση: Πώς κάνουμε ανάθεση σε πέντε διαστάσεις; Δεν χρειάζεται να σχεδιάσουμε τον χώρο. Κάθε δείγμα περιγράφεται από πέντε αριθμούς.

2. Από το P στο C₁
Μία διαφορά για κάθε χαρακτηριστικό
P − C₁ = (0, 0, 2, 0, 2)
d(P,C₁) = √(0²+0²+2²+0²+2²)
= √8 ≈ 2,83
Αφήγηση: Αφαιρούμε συντεταγμένη προς συντεταγμένη. Προς το πρώτο κέντρο παίρνουμε μηδέν, μηδέν, δύο, μηδέν, δύο. Τα τετράγωνα αθροίζουν σε οκτώ.

3. Από το P στο C₂
Ο ίδιος υπολογισμός σε πέντε όρους
P − C₂ = (−2, −2, 0, −2, 0)
d(P,C₂) = √(4+4+0+4+0)
= √12 ≈ 3,46
Αφήγηση: Προς το δεύτερο κέντρο οι διαφορές είναι μείον δύο, μείον δύο, μηδέν, μείον δύο, μηδέν. Τα τετράγωνα αθροίζουν σε δώδεκα.

4. Σύγκριση → ανάθεση
Η λογική παραμένει ίδια σε κάθε διάσταση.
2,83 < 3,46
P → ομάδα 1
Αφήγηση: Η ρίζα οκτώ είναι μικρότερη από τη ρίζα δώδεκα. Άρα το πι ανήκει στην ομάδα του πρώτου κέντρου. Η ανάθεση δουλεύει όπως στις δύο διαστάσεις.

5. Προσέχουμε τις κλίμακες
Οι αριθμοί του παραδείγματος είναι συγκρίσιμοι.
d(P,C) = √Σⱼ(Pⱼ − Cⱼ)²
Συγκρίσιμες κλίμακες χαρακτηριστικών
Αφήγηση: Σε πραγματικά δεδομένα, οι μονάδες και οι κλίμακες επηρεάζουν την απόσταση. Πριν ομαδοποιήσουμε, εξετάζουμε αν χρειάζεται κατάλληλη κλιμάκωση των χαρακτηριστικών.

06_KMedoids
1. Κι αν το κέντρο πρέπει να είναι δείγμα;
K-medoids: πραγματικά σημεία ως εκπρόσωποι
A = (1, 1)   B = (2, 1)   D = (6, 1)
Αφήγηση: Κι αν το κέντρο πρέπει να είναι ένα πραγματικό δείγμα; Στον κάπα μέντοϊντς, κάθε ομάδα εκπροσωπείται από ένα μέλος της: το μέντοϊντ.

2. Ο μέσος όρος δεν είναι πάντα δείγμα
K-means: αριθμητικός μέσος όρος
C = ((1+2+6)/3, (1+1+1)/3)
= (3, 1)
Αφήγηση: Για αυτά τα τρία σημεία, ο κάπα μινς δίνει κέντρο τρία, ένα. Όμως αυτό δεν είναι κανένα από τα αρχικά δείγματα.

3. Δοκιμάζουμε κάθε πραγματικό μέλος
Ευκλείδειες αποστάσεις, χωρίς τετράγωνα
S(A) = 0 + 1 + 5 = 6
S(B) = 1 + 0 + 4 = 5
S(D) = 5 + 4 + 0 = 9
Αφήγηση: Για μέντοϊντ, συγκρίνουμε το άθροισμα αποστάσεων από κάθε υποψήφιο προς τα μέλη. Για το άλφα είναι έξι, για το βήτα πέντε, για το δέλτα εννέα.

4. Το B είναι το medoid
Έχει το μικρότερο συνολικό κόστος.
min{6, 5, 9} = 5
Medoid: B = (2, 1)
Αφήγηση: Το βήτα έχει το μικρότερο άθροισμα, πέντε. Άρα εκπροσωπεί αυτή την ομάδα. Το κέντρο παραμένει πραγματικό μέλος των δεδομένων.

5. Ανάθεση και αναζήτηση εκπροσώπων
Συγγενής ιδέα, διαφορετικό κέντρο και στόχος
K-means: Σ αποστάσεων² → μέσος
K-medoids: Σ αποστάσεων → δείγμα
Αφήγηση: Με πολλές ομάδες, αναθέτουμε στο κοντινότερο μέντοϊντ και βελτιώνουμε τους εκπροσώπους, με ενημερώσεις ή ανταλλαγές. Η ιδέα μοιάζει, αλλά αλλάζει και ο στόχος: άθροισμα αποστάσεων.

07_Σύγκλιση_και_τερματισμός
1. Πότε σταματά ο K-means;
Τι σημαίνει ότι ο αλγόριθμος συγκλίνει;

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

2. Κάθε βήμα βελτιώνει τον στόχο
Το SSE δεν αυξάνεται στα ακριβή βήματα.
SSE = Σ ‖x − Cομάδας‖²
Ανάθεση → ενημέρωση → SSE ↓ ή ίδιο
Αφήγηση: Η ανάθεση επιλέγει το κοντινότερο κέντρο. Η ενημέρωση με μέσους όρους ελαχιστοποιεί το κόστος για αυτές τις ομάδες. Έτσι το σφάλμα δεν αυξάνεται.

3. Οι αναθέσεις σταθεροποιούνται
Τα ίδια μέλη δίνουν τους ίδιους μέσους όρους.
Ίδιες αναθέσεις
→ ίδια κέντρα → σταθερή λύση
Αφήγηση: Αν οι αναθέσεις δεν αλλάζουν, τα ίδια μέλη δίνουν τα ίδια κέντρα. Με σταθερό χειρισμό ισοπαλιών, έχουμε φτάσει σε σταθερή λύση.

4. Πρακτικά κριτήρια τερματισμού
Ανοχή μικρής αλλαγής ή όριο επαναλήψεων
1. Σταθερές αναθέσεις
2. Πολύ μικρή αλλαγή κέντρων
3. Μέγιστο πλήθος επαναλήψεων
Αφήγηση: Στην πράξη σταματάμε επίσης όταν η αλλαγή των κέντρων είναι αρκετά μικρή. Βάζουμε και μέγιστο αριθμό επαναλήψεων, ως όριο υπολογισμού.

5. Σύγκλιση ≠ καλύτερη δυνατή λύση
Το όριο επαναλήψεων δεν αποδεικνύει σύγκλιση.
Σταθερή λύση ≠ παγκόσμιο ελάχιστο
Πολλά ξεκινήματα βοηθούν
Αφήγηση: Μια σταθερή λύση δεν είναι απαραίτητα η καλύτερη δυνατή. Και αν σταματήσαμε μόνο λόγω ορίου επαναλήψεων, δεν έχουμε απαραίτητα συγκλίνει.

08_KMeans_Όλα_τα_βήματα
1. Πώς δουλεύει ο K-means συνολικά;
Έξι σημεία · Κ = 2 · δύο αρχικά κέντρα
Κ = 2
C₁ = (1, 1), C₂ = (4, 3)
Αφήγηση: Πώς δουλεύει ο κάπα μινς από την αρχή μέχρι το τέλος; Έχουμε έξι σημεία, ζητάμε δύο ομάδες, και ξεκινάμε με κέντρα ένα, ένα και τέσσερα, τρία.

2. 1. Αναθέτουμε στο κοντινότερο κέντρο
Το D ξεκινά στη δεύτερη ομάδα.
Ομάδα 1: A, B, Γ
Ομάδα 2: D, E, Z
Αφήγηση: Αναθέτουμε κάθε σημείο στο κοντινότερο κέντρο. Η πρώτη ομάδα περιέχει άλφα, βήτα, γάμα. Η δεύτερη δέλτα, έψιλον, ζήτα.

3. 2. Υπολογίζουμε νέους μέσους όρους
Πράξεις χωριστά για x και y
C₁ = ((1+1+3)/3, (1+3+1)/3)
= (5/3, 5/3)
C₂ = ((4+8+8)/3, (3+7+9)/3)
= (20/3, 19/3)
Αφήγηση: Υπολογίζουμε μέσους όρους ανά συντεταγμένη. Το πρώτο κέντρο γίνεται πέντε τρίτα, πέντε τρίτα. Το δεύτερο είκοσι τρίτα, δεκαεννέα τρίτα.

4. 3. Κάνουμε ξανά ανάθεση
Το D = (4,3) αλλάζει ομάδα.
D: d₁² = 65/9 < d₂² = 164/9
D → ομάδα 1
Αφήγηση: Με τα νέα κέντρα, το δέλτα είναι πλέον πιο κοντά στο πρώτο. Οι τετραγωνικές αποστάσεις είναι εξήντα πέντε ένατα και εκατόν εξήντα τέσσερα ένατα. Άρα αλλάζει ομάδα.

5. 4. Ενημερώνουμε και ελέγχουμε
Η επόμενη ανάθεση παραμένει ίδια.
C₁ = (9/4, 8/4) = (2,25, 2)
C₂ = (16/2, 16/2) = (8, 8)
Ίδιες αναθέσεις → τερματισμός
Αφήγηση: Ενημερώνουμε ξανά. Το πρώτο κέντρο γίνεται δύο κόμμα είκοσι πέντε, δύο. Το δεύτερο οκτώ, οκτώ. Η επόμενη ανάθεση δεν αλλάζει. Σταματάμε σε σταθερή λύση.