{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "name": "Clustering 1.1 Intro - kMeans - Evaluation.ipynb", "provenance": [], "collapsed_sections": [ "Nre7oxppyO07", "SD9NpWgPyO1Y", "PkznuNRa4-Hi" ] }, "kernelspec": { "name": "python3", "display_name": "Python 3" } }, "cells": [ { "cell_type": "code", "metadata": { "id": "wOYHDW2gmkcr" }, "source": [ " !pip install --upgrade scikit-learn\n", "!pip install --upgrade numpy" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "B7EGUG8YyOzs" }, "source": [ "# Συσταδοποίηση (Clustering)\n", "\n", "Οι αλγόριθμοι συσταδοποίησης ανήκουν στην κατηγορία της **μη-επιβλεπόμενης μάθησης**. Σε αντίθεση με ό,τι έχουμε δει μέχρι στιγμής, στα προβλήματα αυτά τα δεδομένα μας **δεν συνοδεύονται από ετικέτες**. Αυτό σημαίνει ότι δεν έχουμε τις γνωστές μετρικές (π.χ. accuracy) για να αξιολογήσουμε αντικειμενικά την επίδοση του αλγορίθμου. Χωρίς αυτές, είναι αδύνατη η εκπαίδευση των αλγορίθμων με τις τεχνικές που έχουμε μάθει (backpropagation/gradient descent). Αντίθετα, στα προβλήματα αυτά θέλουμε ο αλγόριθμος να βρει μόνος του τη δομή (την υποκείμενη κατανομή - underlying distribution) των δεδομένων εισόδου.\n", "\n", "Η [συσταδοποίηση](https://el.wikipedia.org/wiki/%CE%A3%CF%85%CF%83%CF%84%CE%B1%CE%B4%CE%BF%CF%80%CE%BF%CE%AF%CE%B7%CF%83%CE%B7) είναι ένα πρόβλημα το οποίο προσπαθεί να χωρίσει τα δεδομένα εισόδου σε ομάδες/συστάδες (clusters).\n", "\n", "![](https://cdn-images-1.medium.com/max/1600/0*9ksfYh14C-ARETav.)\n", "\n", "\n", "Μια συστάδα (ένα cluster) είναι μια συλλογή αντικειμένων που ομοιάζουν μεταξύ τους περισσότερο σε σχέση με αντικείμενα που βρίσκονται σε άλλες συστάδες.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "oBsWQnwITfmy" }, "source": [ "\n", "## Μετρική απόστασης (ή ομοιότητας)\n", "\n", "Για να μπορέσουμε να κάνουμε clustering χρειαζόμαστε απαραίτητα μια μετρική απόστασης (ή ομοιότητας).\n", "\n", "Μετρική ονομάζεται μια συνάρτηση $d:V\\longrightarrow\\mathbb{R}$, όπου $V \\neq \\emptyset$ τυχόν σύνολο, η οποία ικανοποιεί τις παρακάτω ιδιότητες για κάθε $x,y,z∈V$:\n", "\n", "* $d(x,y)=0$, αν και μόνo αν $x=y$ (ταύτιση),\n", "* $d(x,x)=0$ (συνέπεια της αυτό-ομοιότητας),\n", "* $d(x,y)=d(y,x)$ (συμμετρία), και\n", "* $d(x,y)≤d(x,z)+d(z,y)$ (τριγωνική ανισότητα).\n", "\n", "Η τιμή $d(x,y)$ ονομάζεται απόσταση των $x,y$ (ενν. μέσω της μετρικής $d$). Οποιοδήποτε σύνολο εφοδιασμένο με μία μετρική ονομάζεται μετρικός χώρος.\n", "\n", "Σε έναν μετρικό χώρο επιπλέον, μπορεί να δείξει κανείς ότι\n", "* d(x,y)≥0,\n", "\n", "για κάθε $x,y∈X$. Πράγματι, για κάθε $x$ και για κάθε $y$, η τριγωνική ανισότητα δίνει $d(x,y)+d(y,x)≥d(x,x)$ · από τα αξιώματα ταύτισης και συμμετρίας παίρνουμε $2d(x,y)≥0$, δηλαδή $d(x,y) \\geq 0$.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "GP8IFM38Thfq" }, "source": [ "\n", "### Είδη μετρικών αποστάσεων\n", "\n", "Οι μετρικές απόστασης που χρησιμοποιούμε συχνότερα στη Μηχανική Μάθηση είναι#\n", "\n", "1. Απόσταση Minkowski,\n", "2. Ευκλείδια απόσταση,\n", "3. Απόσταση Manhattan,\n", "4. Απόσταση Hamming, και\n", "5. Ομοιότητα συνημιτόνου.\n", "\n", "Η απόσταση Minkowski (1) τάξεως $p$ (όπου $p$ ακέραιος) μεταξύ δύο σημείων $ X=(x_{1},x_{2},\\ldots ,x_{n})$ και $Y=(y_{1},y_{2},\\ldots ,y_{n})\\in \\mathbb {R} ^{n}$ ορίζεται ως:\n", "$$D\\left(X,Y\\right)=\\left(\\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\\right)^{\\frac {1}{p}}.$$\n", "\n", "\n", "Συνήθως η απόσταση Minkowski χρησιμοποιείται με το $p$ να είναι ίσο με 2 ή 1, που αντιστοιχούν στην Ευκλείδια απόσταση (2) και την απόσταση Manhattan (1). Στην οριακή περίπτωση όπου $p\\rightarrow\\infty$ έχουμε την απόσταση Chebyshev ή μετρική $L_{\\infty}$ που ορίζεται ως η μέγιστη διαφορά των δύο διανυσμάτων σε οποιαδήποτε διάσταση.\n", "\n", "Από την θεωρία της πληροφορίας, η απόσταση Hamming (4) μεταξύ δύο ισομηκών συμβολοσειρών ορίζεται ως το πλήθος των θέσεων στα οποία τα αντίστοιχα σύμβολα διαφέρων μεταξύ των συμβολοσειρών. Με άλλα λόγια, είναι το πλήθος των αλλαγών σε χαρακτήρες που πρέπει να κάνουμε για να μετατρέψουμε τη μία συμβολόσειρα στην άλλη (sting-edit distance). \n", "\n", "H ομοιότητα συνημιτόνου (5) ορίζεται ως:\n", "\n", "$$ S_{C}(X,Y):=\\cos(\\theta )={\\mathbf {X} \\cdot \\mathbf {Y} \\over \\|\\mathbf {X} \\|\\|\\mathbf {Y} \\|}={\\frac {\\sum \\limits _{i=1}^{n}{X_{i}Y_{i}}}{{\\sqrt {\\sum \\limits _{i=1}^{n}{X_{i}^{2}}}}{\\sqrt {\\sum \\limits _{i=1}^{n}{Y_{i}^{2}}}}}},$$\n", "\n", "παίρνει τιμές στο $[-1,1]$ και είναι ιδιαίτερα χρήσιμη σε εφαρμογές όπως η ανάκληση πληροφοριών (Information Retrieval).\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "jUNiw1iDHA1B" }, "source": [ "# Είδη clustering\n", "\n", "![](https://scikit-learn.org/stable/_images/sphx_glr_plot_cluster_comparison_001.png)\n", "\n", "Υπάρχουν πολλά είδη clustering, το καθένα με τα δυνατά κα τα αδύνατα σημεία του. \n", "\n", "Μερικές βασικές κατηγορίες συσταδοποίησης είναι οι ακόλουθες:\n", "\n", "1. Centroids-based Clustering (Partitioning methods)\n", "2. Connectivity-based Clustering (Hierarchical clustering)\n", "3. Density-based Clustering (Model-based methods)\n", "4. Fuzzy Clustering\n", "5. Distribution-based Clustering\n", "6. Competitive (SOM)\n" ] }, { "cell_type": "markdown", "metadata": { "id": "35SlKTdNUyIb" }, "source": [ "# Centroids-based Clustering" ] }, { "cell_type": "code", "metadata": { "id": "kIwBVbj-yOzt" }, "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "%matplotlib inline" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "l8uFD0SeyOzw" }, "source": [ "Στη μη επιβλεπόμενη μάθηση δεν έχουμε κάποιο σύνολο δεδομένων εκπαίδευσης στο οποίο να γνωρίζουμε εκ των προτέρων σε ποια κατηγορία ανήκει το κάθε παράδειγμα. **Δεν γνωρίζουμε καν σε πόσες διαφορετικές κατηγορίες ανήκουν τα δεδομένα μας!**\n", "\n", "Θα ξεκινήσουμε με ένα εύκολο παράδειγμα, του οποίου τα δεδομένα μπορούμε και με το μάτι εύκολα να χωρίσουμε σε 2 κατηγορίες. Θα βάλουμε $Ν=100$ σημεία στο χώρο, 50 απ' τα οποία θα ανήκουν σε κάθε κατηγορία. Σκοπός μας είναι να υλοποιήσουμε έναν αλγόριθμο ο οποίος θα μπορεί από μόνος του να χωρίζει τα δεδομένα αυτά σε κατηγορίες. " ] }, { "cell_type": "code", "metadata": { "id": "31eI_smdyOzx" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "np.random.seed(55) # για να αναπαράγονται τα αποτελέσματα...\n", "\n", "p1 = np.random.rand(50,2) * 10 + 1 # 100 τυχαίοι αριθμοί από ομοιόμορφη κατανομή στο διάστημα [1,11), αποθηκευμένοι σε πίνακα διαστάσεων 50x2.\n", "p2 = np.random.rand(50,2) * 10 + 12 # 100 τυχαίοι αριθμοί από ομοιόμορφη κατανομή στο διάστημα [12,22), αποθηκευμένοι σε πίνακα διαστάσεων 50x2.\n", "\n", "points = np.concatenate([p1, p2]) # ενώνουμε τους αριθμούς σε έναν ενιαίο πίνακα διαστάσεων 100x2\n", " # η πρώτη στήλη του πίνακα αντιστοιχεί στη συντεταγμένη x ενώ η δεύτερη στην y\n", " # δηλαδή η 30η γραμμή του πίνακα αντιπροσωπεύει τις 2 συντεταγμένες του 30ου παραδείγματος \n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1]) # για να σχεδιάσουμε τη γραφική παράσταση διακριτών σημείων χρησιμοποιούμε την scatter\n", " # τα 2 της ορίσματα είναι οι συντεταγμένες x και y όλων των σημείων\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "yPujmf15yOz2" }, "source": [ "## Συσταδοποίηση $k$-μέσων\n", "\n", "Ο πιο απλός αλγόριθμος συσταδοποίησης είναι ο αλγόριθμος **[$k$-μέσων](https://en.wikipedia.org/wiki/K-means_clustering)** ($k$-means), ο οποίος θα δούμε βήμα βήμα πώς δουλεύει.\n", "\n", "Η λειτουργία του αλγορίθμου είναι απλή. Ορίζουμε πρώτα τον πλήθος των συστάδων($k$) στις οποίες θέλουμε να χωρίσει ο αλγόριθμος τα δεδομένα μας. Η λογική του αλγορίθμου είναι ότι χωρίζει συστάδες με βάση σημεία στο χώρο, τα οποία αναπαριστούν τα κέντρα των ομάδων αυτών. Τα κέντρα αρχικοποιούνται τυχαία. Έπειτα ελέγχουμε την απόσταση του κάθε δείγματος του σύνολου δεδομένων μας από το κάθε κέντρο. Το κέντρο το οποίο είναι πιο κοντά στο σημείο είναι και αυτό στου οποίου την συστάδα θεωρούμε ότι ανήκει. Τη διαδικασία αυτή την ονομάζουμε *ανάθεση* (assignment). Τέλος, για κάθε συστάδα, υπολογίζουμε το μέσο όρο όλων των σημείων της και μετακινούμε το κέντρο στο σημείο αυτό. Τη διαδικασία αυτή την ονομάζουμε *ενημέρωση* (update). Η ανάθεση των σημείων και η ενημέρωση των κέντρων επαναλαμβάνεται έως ότου έρθει σε σύγκλιση ο αλγόριθμος.\n", "\n", "![](http://stanford.edu/~cpiech/cs221/img/kmeansViz.png)\n", "\n", "Στο παραπάνω σχήμα:\n", "\n", "- (α): Δεδομένα εισόδου\n", "- (β): Τυχαία αρχικοποίηση κέντρων\n", "- (γ): Πρώτη ανάθεση σημείων σε συστάδες\n", "- (δ): Πρώτη ενημέρωση κέντρων\n", "- (ε): Δεύτερη ανάθεση\n", "- (στ): Δεύτερη ενημέρωση\n", "\n", "Μπορούμε να δούμε ολόκληρη τη διαδικασία της εκπαίδευσης και στο παρακάτω σχήμα.\n", "\n", "![](https://www.projectrhea.org/rhea/images/e/ef/RunyanKmeans.gif)\n", "\n", "Η μόνη παράμετρος που χρειάζεται ο αλγόριθμος αυτός για να δουλέψει είναι το $k$, δηλαδή το πλήθος των συστάδων στις οποίες θέλουμε να κατανείμει τα δεδομένα. Μόλις δώσουμε στον αλγόριθμο το $k$, αυτός δημιουργεί $k$ τυχαία σημεία στο χώρο, που αναπαριστούν τα κέντρα των συστάδων." ] }, { "cell_type": "code", "metadata": { "id": "n1bBxea1yOz2" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "k = 2 # υπερπαράμετρος του k-means --> ο αριθμός των συστάδων που θα ψάξει να βρει ο αλγόριθμος\n", "\n", "np.random.seed(55)\n", "centroids = np.random.rand(k,2) * 22 # ΒΗΜΑ 1: φτιάχνει τυχαία 2 σημεία στο ίδιο διάστημα που βρίσκονται και τα δεδομένα μας\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1]) # τυπώνουμε τα σημεία με μπλε (default)\n", "plt.scatter(centroids[:,0], centroids[:,1], color='r', s=50) # και τα 2 κέντρα με κόκκινο χρώμα και μεγαλύτερο μέγεθος\n", "axes_scaling = plt.axis('equal') # o λόγος των δύο αξόνων να είναι 1 https://matplotlib.org/gallery/subplots_axes_and_figures/axis_equal_demo.html" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "bj0sxDnRyOz5" }, "source": [ "Για να μπορέσουμε να συνεχίσουμε, χρειαζόμαστε έναν τρόπο να υπολογίζουμε πόσο κοντά είναι το ένα σημείο στο άλλο. Το μέτρο που θα χρησιμοποιήσουμε για το σκοπό αυτό είναι η [Ευκλείδεια απόσταση](https://en.wikipedia.org/wiki/Euclidean_distance). Για τις 2 διαστάσεις η απόσταση 2 σημείων $a$ και $b$ υπολογίζεται ως:\n", "\n", "$$\n", "d \\left( a, b \\right) = \\sqrt{ \\left( a_x - b_x \\right)^2 + \\left( a_y - b_y \\right)^2}\n", "$$" ] }, { "cell_type": "code", "metadata": { "id": "kBMb3JwTyOz6" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "def euclidean_distance(point1, point2):\n", " # υλοποίηση της Ευκλείδειας απόστασης από τον παραπάνω τύπο\n", " # δέχεται 2 σημεία (που το καθένα έχει 2 συντεταγμένες) και επιστρέφει την απόσταση\n", " return np.sqrt( (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2 )\n", "\n", "print('the distance from (5,2) to (2,5) is:', euclidean_distance((5,2), (2,5)))\n", "print('the distance from (3,3) to (3,3) is:', euclidean_distance((3,3), (3,3)))\n", "print('the distance from (1,12) to (12,15) is:', euclidean_distance((1,12), (12,15)))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "9fEpe7UMyOz9" }, "source": [ "Αντί της παραπάνω συνάρτησης θα μπορούσαμε εναλλακτικά να χρησιμοποιήσουμε τη μέθοδο [pdist](https://docs.scipy.org/doc/scipy-0.19.1/reference/generated/scipy.spatial.distance.pdist.html) από τη βιβλιοθήκη *scipy.spatial.distance*.\n", "\n", "Το δεύτερο βήμα του αλγορίθμου είναι να υπολογίσει για κάθε σημείο πόσο απέχει από κάθε κέντρο. Για τον υπολογισμό αυτό θα χρησιμοποιήσουμε τη βοηθητική συνάρτηση που ορίσαμε παραπάνω." ] }, { "cell_type": "code", "metadata": { "id": "bqJq3XAPyOz-" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "def calc_distances(centroids, points):\n", " # δέχεται δύο σύνολα σημείων, το πρώτο είναι το σύνολο των κέντρων των συστάδων\n", " # ενώ το δεύτερο είναι το σύνολο των σημείων που θέλουμε να ομαδοποιήσουμε\n", " distances = np.zeros((len(centroids), len(points))) # φτιάχνουμε έναν πίνακα (διαστάσεων (k x N)) που θα αποθηκεύσει τις αποστάσεις.\n", " for i in range(len(centroids)):\n", " for j in range(len(points)):\n", " distances[i,j] = euclidean_distance(centroids[i], points[j])\n", " return distances\n", " # Το παραπάνω μπορεί να γραφτεί ως εξής:\n", " # return np.reshape(np.array([euclidean_distance(centroids[i], points[j]) for i in range(len(centroids)) for j in range(len(points))]), (len(centroids), len(points)))\n", " \n", "\n", "print('first 10 distances from the first centroid:')\n", "print(calc_distances(centroids, points)[0, :10])\n", "print('...')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "D0tQpoH4yO0A" }, "source": [ "Έπειτα, χρησιμοποιεί τις αποστάσεις αυτές για να δει σε ποια συστάδα ανήκει το κάθε σημείο (δηλ. σε ποιο κέντρο βρίσκεται πιο κοντά)." ] }, { "cell_type": "code", "metadata": { "id": "SPkZfeDXyO0B" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "def assign_cluster(centroids, points):\n", " distances = calc_distances(centroids, points)\n", " return np.argmin(distances, axis=0)\n", "\n", "print('which cluster does each point belong to?')\n", "print(assign_cluster(centroids, points))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "HxN8YYv8yO0F" }, "source": [ "Επειδή έχουμε $k=2$ ο διαχωρισμός των 2 συστάδων γίνεται γεωμετρικά από τη μεσοκάθετο. Τις γραμμές (ή επίπεδα σε χώρους μεγαλύτερων διαστάσεων) που χωρίζουν τις ομάδες τις αποκαλούμε [*όρια αποφάσεων*](https://en.wikipedia.org/wiki/Decision_boundary) (decision boundaries). Για λόγους εξοικείωσης με τη matplotlib θα προσπαθήσουμε να σχεδιάσουμε τις ομάδες και τη μεσοκάθετο.\n", "\n", "Όσον αφορά την επιλογή των χρωμάτων, η matplotlib έχει δώσει σε αρκετά χρώματα [ονόματα](https://matplotlib.org/examples/color/named_colors.html) με τα οποία μπορούμε να τα καλέσουμε. Αυτός είναι και ο πιο εύκολος τρόπος να διαλέξουμε χρώμα. Δίνει βέβαια τη δυνατότητα να [δημιουργήσουμε](https://matplotlib.org/api/colors_api.html) και δικά μας (π.χ. αν γνωρίζουμε τις RGB ή HSV τιμές του χρώματος).\n" ] }, { "cell_type": "code", "metadata": { "id": "n9mC35EdyO0G" }, "source": [ "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "# Αρχικά θα υπολογίσουμε τη συνάρτηση της μεσοκαθέτου\n", "def generate_perp_bisector(centroids):\n", " midpoint = ((centroids[0,0]+centroids[1,0])/2, (centroids[0,1]+centroids[1,1])/2) # το μέσο των 2 κέντρων\n", " slope = (centroids[1,1]-centroids[0,1]) / (centroids[1,0]-centroids[0,0]) # η κλίση της ευθείας που ενώνει τα 2 κέντρα\n", " perpendicular = -1/slope # η κάθετος στην κλίση αυτή\n", " #perpendicular = slope\n", " return lambda x: perpendicular*(x-midpoint[0]) + midpoint[1] # η συνάρτηση της μεσοκαθέτου\n", " #lambda είναι μια ανώνυμη συνάρτηση δλδ lambda argument: manipulate(argument)\n", "\n", "\n", "perp_bisector = generate_perp_bisector(centroids)\n", " \n", "# Φτιάχνουμε μια απεικόνιση με το τι χρώμα θέλουμε να έχει η κάθε ομάδα και κάνουμε την αντιστοίχιση\n", "map_colors = {0:'orange', 1:'deepskyblue'}\n", "colors = [map_colors[i] for i in assign_cluster(centroids, points)]\n", "\n", "# Δίνουμε στην scatter το όρισμα c, το οποίο περιέχει μια λίστα με το χρώμα του κάθε σημείου\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points') # η παράμετρος lw=0 ορίζει ότι δεν θέλουμε πλαίσιο γύρω από τα σημεία αυτά\n", "plt.scatter(centroids[:,0], centroids[:,1], c=['orange', 'deepskyblue'], s=80, label='centroids') # την παράμετρο label θα την χρησιμοποιήσει η λεζάντα\n", "\n", "# Τυπώνουμε και με την plot το decision boundary μας με μωβ χρώμα\n", "plt.plot(range(25), [perp_bisector(x) for x in range(25)], c='purple', label='decision boundary')\n", "\n", "# Ορίζουμε τα πλαίσια της γραφικής για κάθε άξονα\n", "plt.xlim([0,22])\n", "plt.ylim([1,23])\n", "\n", "# Σβήνουμε την αρίθμηση και τα σημεία από τους άξονες\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "\n", "# Βάζουμε τίτλους στους άξονες και στο κείμενο\n", "plt.xlabel('x')\n", "plt.ylabel('y')\n", "plt.title('KMeans: Random Centroid Initialization')\n", "\n", "# Ορίζουμε την τοποθεσία της λεζάντας μας. Τα ονόματα τα πήρε από τα label των αντικειμένων παραπάνω\n", "plt.legend(loc='lower right')\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "-yBd3jp_yO0K" }, "source": [ "Το τρίτο βήμα είναι να πάρει όλα σημεία της κάθε ομάδας, να υπολογίσει τη μέση τιμή τους και να τοποθετήσει το αντίστοιχο κέντρο στη θέση που αντιστοιχεί στη μέση τιμή αυτή." ] }, { "cell_type": "code", "metadata": { "id": "h3_f4C1-yO0L" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "def update_centers(centroids, points):\n", " clusters = assign_cluster(centroids, points) # τρέχει πρώτα τη διαδικασία της ανάθεσης για να δει σε ποια συστάδα ανήκει το κάθε παράδειγμα\n", " new_centroids = np.zeros(centroids.shape) # πίνακας που θα αποθηκευτούν οι νέες θέσεις των κέντρων\n", " for i in range(len(centroids)):\n", " cluster_points_idx = [j for j in range(len(clusters)) if clusters[j] == i] # βρίσκει τις θέσεις των σημείων που αντιστοιχούν στην i-οστή συστάδα\n", " if cluster_points_idx: # αν υπάρχουν σημεία που έχουν ανατεθεί στο κέντρο, αυτό ενημερώνεται\n", " cluster_points = points[cluster_points_idx] # παίρνουμε το slice των αντίστοιχων θέσεων\n", " new_centroids[i, 1] = cluster_points[:,1].sum() / len(cluster_points) # υπολογίζουμε τη νέα θέση των κέντρων\n", " new_centroids[i, 0] = cluster_points[:,0].sum() / len(cluster_points)\n", " else: # αλλιώς κρατάμε την παλιά του θέση\n", " new_centroids[i, :] = centroids[i, :]\n", " return new_centroids\n", "\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "# Υπολογίζουμε τις νέες θέσεις των κέντρων και με βάση αυτές το νέο όριο απόφασης και τις νέες αναθέσεις\n", "new_centroids = update_centers(centroids, points)\n", "new_boundary = generate_perp_bisector(new_centroids)\n", "new_colors = [map_colors[i] for i in assign_cluster(new_centroids, points)]\n", "\n", "# Όπως είδαμε πριν δημιουργούμε τη γραφική παράσταση μετά την ενημέρωση των κέντρων\n", "plt.scatter(points[:,0], points[:,1], c=new_colors, lw=0, s=30, label='data points')\n", "plt.scatter(centroids[:,0], centroids[:,1], c=['orange', 'deepskyblue'], s=80, alpha=0.3, label='old centroids') # παλιά κέντρα\n", "plt.scatter(new_centroids[:,0], new_centroids[:,1], c=['orange', 'deepskyblue'], s=80, label='new centroids')# νέα κέντρα\n", "plt.plot(range(25), [new_boundary(x) for x in range(25)], c='purple', label='new boundary') # νέο όριο απόφασης\n", "plt.plot(range(25), [perp_bisector(x) for x in range(25)], c='black', label='old boundary', alpha=0.3) # παλιό όριο απόφασης\n", "plt.xlim([0,22])\n", "plt.ylim([1,23])\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.title('KMeans: Boundary changes after first centroid update')\n", "plt.legend(loc='lower right')\n", "axes_scaling = plt.axis('equal')\n", "\n", "# Σχεδιάζουμε και τα βελάκια που θα δούμε παρακάτω στο σχήμα\n", "for i in range(k):\n", " plt.arrow(centroids[i,0], centroids[i,1], new_centroids[i,0]-centroids[i,0], new_centroids[i,1]-centroids[i,1],\n", " length_includes_head=True, head_width=0.5, color='black')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "Fau4tHETyO0O" }, "source": [ "Τα βήματα 2 και 3 επαναλαμβάνονται μέχρι να μη μετακινούνται άλλο τα κέντρα. Ένα πολύ ωραίο visual example να δοκιμάσετε τον αλγόριθμο σε διάφορους τύπους δεδομένων και με διάφορες αρχικές συνθήκες θα βρείτε [εδώ](https://www.naftaliharris.com/blog/visualizing-k-means-clustering/).\n", "\n", "Για λόγους διευκόλυνσής μας θα γράψουμε τον αλγόριθμο αυτό σε μορφή κλάσης. Η κλάση αυτή θα αρχικοποιείται μόνο με την παράμετρο $k$, Θα έχει μια μέθοδο που θα ονομάσουμε `.fit()` η οποία θα δέχεται τα σημεία που θέλουμε να ομαδοποιήσουμε και θα εκπαιδεύει τον αλγόριθμο έως ότου έρθει σε σύγκλιση. Επίσης θα έχει μια μέθοδο `.predict()` η οποία θα δέχεται ένα ή περισσότερα σημεία και θα επιστρέφει σε ποια κλάση ανήκουν τα σημεία αυτά. " ] }, { "cell_type": "code", "metadata": { "id": "WnKZu0EAyO0O" }, "source": [ "class KMeans:\n", " \n", " def __init__(self, k, term_distance=0.05, max_steps=50, seed=None):\n", " # Constructor της κλάσης, δέχεται τις παραμέτρους και αρχικοποιεί το αντικείμενο\n", " self.k = k\n", " self.seed = seed\n", " self.history = [] \n", " # Συνθήκες τερματισμού:\n", " self.term_distance = term_distance # ελάχιστη επιτρεπτή απόσταση μετακίνησης των κέντρων\n", " self.max_steps = max_steps # μέγιστος επιτρεπτός αριθμός εποχών\n", " \n", " def initialize(self, data):\n", " # Βάζει k σημεία σε τυχαίες θέσεις στο χώρο που ορίζουν τα σημεία μας\n", " np.random.seed(self.seed)\n", " self.centroids = np.random.rand(self.k,2) * data.max()\n", " self.history = [self.centroids] # κρατάει ιστορικό με τις παλιές θέσεις των κέντρων\n", " \n", " def calc_distances(self, points):\n", " # Υπολογίζει τις αποστάσεις των σημείων points από τα κέντρα\n", " distances = np.zeros((len(self.centroids), len(points)))\n", " for i in range(len(self.centroids)):\n", " for j in range(len(points)):\n", " distances[i,j] = self.euclidean_distance(self.centroids[i], points[j])\n", " return distances\n", " \n", " def assign_cluster(self, points):\n", " # Συγκρίνει τις αποστάσεις των σημείων points από τα κέντρα και πραγματοποιεί την ανάθεση\n", " distances = self.calc_distances(points)\n", " return np.argmin(distances, axis=0)\n", "\n", " def update_centers(self, points):\n", " # Υπολογίζει τις νέες θέσεις των κέντρων\n", " clusters = self.assign_cluster(points)\n", " new_centroids = np.zeros(self.centroids.shape)\n", " for i in range(len(self.centroids)):\n", " cluster_points_idx = [j for j in range(len(clusters)) if clusters[j] == i]\n", " if cluster_points_idx:\n", " cluster_points = points[cluster_points_idx]\n", " new_centroids[i, 1] = cluster_points[:,1].sum() / len(cluster_points)\n", " new_centroids[i, 0] = cluster_points[:,0].sum() / len(cluster_points)\n", " else:\n", " new_centroids[i, :] = centroids[i, :]\n", " return new_centroids\n", " \n", " def fit(self, data):\n", " # Πραγματοποιεί όλη τη διαδικασία της εκπαίδευσης:\n", " # 1) αρχικοποιεί τα κέντρα με την initialize\n", " # 2, 3) υπολογίζει τις αποστάσεις και ενημερώνει τα κέντρα με την update_clusters\n", " # Επαναλαμβάνει τα βήματα 2 και 3 έως ότου ικανοποιηθεί η συνθήκη τερματισμού\n", " self.initialize(data)\n", " self.previous_positions = [self.centroids]\n", " step = 0\n", " cluster_movement = [self.term_distance + 1] * self.k\n", " while any([x > self.term_distance for x in cluster_movement]) and step < self.max_steps:\n", " new_centroids = self.update_centers(data)\n", " self.history.append(new_centroids)\n", " cluster_movement = [self.euclidean_distance(new_centroids[i,:], self.centroids[i,:]) for i in range(self.k)]\n", " self.centroids = new_centroids\n", " self.previous_positions.append(self.centroids)\n", " step += 1\n", " \n", " def predict(self, points):\n", " # Ελέγχει αν το points είναι πίνακας με πολλά σημεία ή οι συντεταγμένες ενός σημείου και πραγματοποιεί την ανάθεση \n", " if isinstance(points, np.ndarray):\n", " if len(points.shape) == 2:\n", " return [np.argmin([self.euclidean_distance(point, centroid) for centroid in self.centroids]) for point in points]\n", " return np.argmin([self.euclidean_distance(points, self.centroids[i]) for i in range(self.k)])\n", " \n", " \n", " def fit_predict(self, points):\n", " # Τρέχει την fit και επιστρέφει τα assignments\n", " self.fit(points)\n", " return self.predict(points)\n", " \n", " @staticmethod\n", " def euclidean_distance(point1, point2):\n", " # Υπολογίζει την Ευκλείδεια απόσταση μεταξύ 2 σημείων\n", " return np.sqrt( (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2 )" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "f-ycG7TayO0S" }, "source": [ "Στην αρχή για να δούμε αν δουλεύει σωστά θα τρέξουμε μερικές επαναλήψεις μόνοι μας (χωρίς να κάνουμε χρήση της `.fit()`. Πρώτα αρχικοποιούμε τα $k$ κέντρα των ομάδων." ] }, { "cell_type": "code", "metadata": { "id": "bXrXHXDhyO0T" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "km = KMeans(2, seed=13)\n", "km.initialize(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "colors = [map_colors[i] for i in km.predict(points)]\n", "decision_boundary = generate_perp_bisector(km.centroids)\n", "\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(km.centroids[:,0], km.centroids[:,1], c=['orange', 'deepskyblue'], s=80, label='centroids')\n", "plt.plot(range(25), [decision_boundary(x) for x in range(25)], c='purple', label='decision boundary')\n", "plt.xlim([0,22])\n", "plt.ylim([1,23])\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.legend(loc='upper left')\n", "plt.title('KMeans: Boundary after initialization')\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "sNyStph_yO0X" }, "source": [ "Και στη συνέχεια τρέχουμε μια επανάληψη και ενημερώνουμε τα κέντρα." ] }, { "cell_type": "code", "metadata": { "id": "b2mWzeDmyO0Y" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "old = km.centroids\n", "km.centroids = new = km.update_centers(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "colors = [map_colors[i] for i in km.predict(points)]\n", "decision_boundary_new = generate_perp_bisector(new)\n", "\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(old[:,0], old[:,1], c=['orange', 'deepskyblue'], s=80, label='old centroids', alpha=0.3)\n", "plt.scatter(new[:,0], new[:,1], c=['orange', 'deepskyblue'], s=80, label='new centroids')\n", "plt.plot(range(25), [decision_boundary(x) for x in range(25)], c='black', label='old boundary', alpha=0.3)\n", "plt.plot(range(25), [decision_boundary_new(x) for x in range(25)], c='purple', label='new boundary')\n", "plt.xlim([0,22])\n", "plt.ylim([1,23])\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.legend(loc='upper left')\n", "plt.title('KMeans: Boundary changes after first centroid update')\n", "axes_scaling = plt.axis('equal')\n", "\n", "for i in range(km.k):\n", " plt.arrow(old[i,0], old[i,1], new[i,0]-old[i,0], new[i,1]-old[i,1], length_includes_head=True, head_width=0.5, color='black')\n", " " ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "NJSemyvoyO0b" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "old = km.centroids\n", "new = km.update_centers(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "decision_boundary = decision_boundary_new\n", "colors = [map_colors[i] for i in km.predict(points)]\n", "decision_boundary_new = generate_perp_bisector(new)\n", "\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(old[:,0], old[:,1], c=['orange', 'deepskyblue'], s=80, label='old centroids', alpha=0.3)\n", "plt.scatter(new[:,0], new[:,1], c=['orange', 'deepskyblue'], s=80, label='new centroids')\n", "plt.plot(range(25), [decision_boundary(x) for x in range(25)], c='black', label='old boundary', alpha=0.3)\n", "plt.plot(range(25), [decision_boundary_new(x) for x in range(25)], c='purple', label='new boundary')\n", "plt.xlim([0,22])\n", "plt.ylim([1,23])\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.legend(loc='upper left')\n", "plt.title('KMeans: Boundary changes after second centroid update') \n", "axes_scaling = plt.axis('equal')\n", "\n", "for i in range(km.k):\n", " plt.arrow(old[i,0], old[i,1], new[i,0]-old[i,0], new[i,1]-old[i,1], length_includes_head=True, head_width=0.3, color='black')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "_dRnCs03yO0d" }, "source": [ "Τώρα που βλέπουμε ότι δουλεύει, μπορούμε να δοκιμάσουμε και τη μέθοδο `.fit()` η οποία αναλαμβάνει όλη τη διαδικασία εκπαίδευσης για όσες επαναλήψεις χρειαστεί." ] }, { "cell_type": "code", "metadata": { "id": "Lzz572TiyO0d" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "km = KMeans(2, seed=44)\n", "km.fit(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "colors = [map_colors[i] for i in km.predict(points)]\n", "decision_boundary = generate_perp_bisector(km.centroids)\n", "\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(new[:,0], new[:,1], c=['orange', 'deepskyblue'], s=80, label='new centroids')\n", "plt.plot(range(25), [decision_boundary_new(x) for x in range(25)], c='purple', label='new boundary')\n", "plt.xlim([0,22])\n", "plt.ylim([1,23])\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.legend(loc='upper left')\n", "plt.title('KMeans: Complete training')\n", "axes_scaling = plt.axis('equal')\n", "\n", "# Χρησιμοποιούμε την km.history για να δούμε και να σχεδιάσουμε τις προηγούμενες θέσεις των κέντρων\n", "steps = len(km.history)\n", "for s in range(steps-2): # την τελευταία θέση (όπου s==steps-1) τη σχεδιάσαμε παραπάνω, την προ-τελευταία την αγνοούμε για 2 λόγους:\n", " # 1) για να τερμάτισε σημαίνει ότι έχει μηδαμινή κίνηση από την τελευταία και\n", " # 2) γιατί τα arrow πρέπει να είναι κατά 1 λιγότερα από τα σημεία\n", " plt.scatter(km.history[s][:,0], km.history[s][:,1], c=['orange', 'deepskyblue'], s=80, label='old centroids', alpha=1.0/(steps-s))\n", "\n", " for i in range(km.k):\n", " plt.arrow(km.history[s][i,0], km.history[s][i,1], km.history[s+1][i,0]-km.history[s][i,0], km.history[s+1][i,1]-km.history[s][i,1], length_includes_head=True, head_width=0.3, color='black', alpha=1.0/(steps-s))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "clDYOj8VyO0g" }, "source": [ "Μόλις έχει εκπαιδευτεί το σύστημα, μπορούμε να χρησιμοποιήσουμε και την `.predict()` για να δούμε σε ποια ομάδα ανήκει το κάθε σημείο." ] }, { "cell_type": "code", "metadata": { "id": "qsFWmMJsyO0h" }, "source": [ "print(' (0,0) belongs to cluster:', km.predict((0,0)))\n", "print(' (5,5) belongs to cluster:', km.predict((5,5)))\n", "print('(10,10) belongs to cluster:', km.predict((10,10)))\n", "print('(15,15) belongs to cluster:', km.predict((15,15)))\n", "print('(20,20) belongs to cluster:', km.predict((20,20)))\n", "print('(25,25) belongs to cluster:', km.predict([25,25]))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "pTZbaLx8yO0j" }, "source": [ "Τι θα γίνει όμως αν βάλουμε μεγαλύτερο $k$ από αυτό που χρειάζεται;" ] }, { "cell_type": "code", "metadata": { "id": "ZDctsUs6yO0j" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "km = KMeans(5, seed=13)\n", "km.fit(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "# Ως colors μπορούμε για ευκολία να βάλουμε και τα index των αναθέσων αντί για μία λίστα με χρώματα όπως προηγουμένως\n", "plt.scatter(points[:,0], points[:,1], c=km.predict(points), s=30, lw=0)\n", "plt.scatter(km.centroids[:,0], km.centroids[:,1], c=range(5), s=80)\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "SEVYy_ZZyO0m" }, "source": [ "Ή αν έχουμε κάποιο πιο πολύπλοκο πρόβλημα όπου δεν ξέρουμε τι $k$ να χρησιμοποιήσουμε;" ] }, { "cell_type": "code", "metadata": { "id": "AwJ8RkFKyO0m" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "np.random.seed(77)\n", "\n", "# Θα φτιάξουμε 4 συστάδες από 50 σημεία με κέντρα τις θέσεις (7,7), (7,17), (17,7) και (17,17)\n", "# Θα δημιουργήσουμε τα σημεία, όμως, με πολύ μεγάλη διασπορά ώστε να μην φαίνονται οι ομάδες\n", "# με το μάτι\n", "\n", "lowb, highb, var = 2, 12, 10\n", "\n", "p1 = np.random.rand(50,2) * var + lowb\n", "p2 = np.random.rand(50,2) * var + highb\n", "\n", "a = np.array([highb]*50)\n", "b = np.array([lowb]*50)\n", "c = np.zeros((50,2))\n", "c[:,0], c[:,1] = a, b\n", "p3 = np.random.rand(50,2) * var + c\n", "c[:,1], c[:,0] = a, b\n", "p4 = np.random.rand(50,2) * var + c\n", "\n", "points = np.concatenate([p1, p2, p3, p4])\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1])\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "Ssf59U2vyO0o" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "k = 5\n", "km = KMeans(k, seed=77)\n", "km.fit(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1], c=km.predict(points), lw=0, s=30)\n", "plt.scatter(km.centroids[:,0], km.centroids[:,1], c=range(k), s=80)\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "metadata": { "id": "4RniYD5cyO0v" }, "source": [ "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "# Δημιουργούμε 4 subplots πάνω στο ίδιο διάγραμμα\n", "f, ax = plt.subplots(2, 2)\n", "seed = 55\n", "\n", "# k = 2\n", "km = KMeans(2, seed=seed)\n", "ax[0, 0].scatter(points[:,0], points[:,1], c=km.fit_predict(points), lw=0)\n", "ax[0, 0].set_title('k = 2')\n", "ax[0, 0].set_aspect('equal')\n", "\n", "# k = 3\n", "km = KMeans(3, seed=seed)\n", "ax[0, 1].scatter(points[:,0], points[:,1], c=km.fit_predict(points), lw=0)\n", "ax[0, 1].set_title('k = 3')\n", "ax[0, 1].set_aspect('equal')\n", "\n", "# k = 4\n", "km = KMeans(4, seed=seed)\n", "ax[1, 0].scatter(points[:,0], points[:,1], c=km.fit_predict(points), lw=0)\n", "ax[1, 0].set_title('k = 4')\n", "ax[1, 0].set_aspect('equal')\n", "\n", "# k = 5\n", "km = KMeans(5, seed=seed)\n", "ax[1, 1].scatter(points[:,0], points[:,1], c=km.fit_predict(points), lw=0)\n", "ax[1, 1].set_title('k = 5')\n", "ax[1, 1].set_aspect('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "DZJ2mdFGXPm9" }, "source": [ "### Υπερπαράμετρος $k$\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "Ekx1hnTLXcAA" }, "source": [ "Παρατηρούμε ότι ο αλγόριθμος kMeans έχει μια βασική υπερπαράμετρο που είναι το $k$. Προκειμένου να διαλέξουμε το βέλτισο $k$ χρειαζόμαστε κάποιον τρόπο να μπορούμε να αξιολογούμε την ποιότητα των clustering που προκύπτουν για $k=1,2,3,...$.\n", "\n", "Οι μετρικές που χρησιμοποιούμε στην επιβλεπόμενη μάθηση για την αξιολόγηση ενός αλγορίθμου (accuracy, confusion matrix, f1-score) χρειάζονται ετικέτες για να υπολογιστούν. Πώς μπορούμε, λοιπόν, να αξιολογήσουμε την επίδοση ενός αλγορίθμου συσταδοποίησης;\n", "\n", "Ένα απλό μέτρο που μπορούμε να σκεφτούμε είναι να συγκρίνουμε για κάθε συστάδα τη διασπορά των παραδειγμάτων της συγκεκριμένης συστάδας.\n", "\n", "Για τη συστάδα $C$ το παραπάνω μπορεί να υπολογιστεί ως εξής:\n", "\n", "$$\n", "I_C = \\sum_{i \\in C}{(x_i - \\bar{x}_C)^2}\n", "$$\n", "\n", "όπου $x_i$ ένα παράδειγμα που ανήκει στη συστάδα $C$ με κέντρο $\\bar{x}_C$.\n", "\n", "Όσο πιο μικρό το μέτρο αυτό, τόσο μικρότερη διασπορά έχει η αντίστοιχη συστάδα, πράγμα επιθυμητό καθώς σημαίνει ότι είναι πιο \"συμπαγής\". Μετρικές σαν αυτή τις ονομάζουμε **inertia** (αδράνεια). Για να υπολογίσω τη συνολική αδράνεια, απλά προσθέτω τις διασπορές για όλα τα cluster.\n", "\n", "$$\n", "Ι = \\sum_{C = 1}^k{I_C}\n", "$$\n", "\n", "Πολλές φορές το σταθμίζουμε και με τη συνολική διασπορά στο σύνολο δεδομένων. Ας δούμε ένα αντίστοιχο παράδειγμα με το προηγούμενο, χρησιμοποιώντας την υλοποίηση του [KMeans](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html) από το scikit-klearn..." ] }, { "cell_type": "code", "metadata": { "id": "1zJWDlfByO0x" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "from sklearn.cluster import KMeans\n", "\n", "k = 5\n", "km = KMeans(k, random_state=99)\n", "km.fit(points)\n", "\n", "print(km.inertia_)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1], c=km.predict(points), lw=0, s=30)\n", "plt.scatter(km.cluster_centers_[:,0], km.cluster_centers_[:,1], c=range(km.n_clusters), s=80)\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "WpeVa3CmyO0z" }, "source": [ "Όσο μικρότερη η αδράνεια, τόσο καλύτερο clustering έχει γίνει. Προφανώς θέλουμε να **ελαχιστοποιήσουμε** το κριτήριο αυτό. Ας τρέξουμε λοιπόν τον $k$-means για $k$ από 1 μέχρι 100 να δούμε σε ποια τιμή ελαχιστοποιείται ο δείκτης αυτός." ] }, { "cell_type": "code", "metadata": { "id": "Z1nNY9rVyO00" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "cluster_scores = []\n", "for k in range(1, 101):\n", " km = KMeans(k, random_state=77)\n", " km.fit(points)\n", " cluster_scores.append(km.inertia_)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.plot(range(1, 101), cluster_scores)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "F_CRqirgyO02" }, "source": [ "Παρατηρούμε ότι η αδράνεια μικραίνει όσο μεγαλώνει το $k$, και φτάνει στο 0 όταν $k=N$, όπου $N$ το πλήθος των παραδειγμάτων μας. Το να ορίσουμε μια συστάδα για κάθε δείγμα είναι τετριμμένη λύση, γιατί δεν μας βοηθάει να εξηγήσουμε τα δεδομένα και να εξάγουμε γνώση από αυτά, που είναι ο στόχος στην μη-επιβλεπόμενη μάθηση.\n", "\n", "Άρα δεν μπορεί να μας βοηθήσει το κριτήριο αυτό για τον υπολογισμό του βέλτιστου $k$.\n", "\n", "Ένα **εμπειρικό** κριτήριο που μπορεί να βοηθήσει είναι αυτό που αποκαλούμε [μέθοδο του \"αγκώνα\"](https://en.wikipedia.org/wiki/Elbow_method_(clustering)) (elbow). Κοιτάμε δηλαδή στη γραφική παράσταση της αδράνειας ή της διασποράς ως προς το $k$, σε ποιο σημείο σχηματίζει έναν \"αγκώνα\" η γραφική. Αυτό υπολογίζεται κοιτάζοντας και τη δεύτερη παράγωγο της αντίστοιχης γραφικής.\n", "\n" ] }, { "cell_type": "code", "metadata": { "id": "STb0jGmxyO04" }, "source": [ "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.plot(range(2,8), cluster_scores[2:8])\n", "plt.annotate(\"elbow\", xy=(3, cluster_scores[3]), xytext=(5, 4500),arrowprops=dict(arrowstyle=\"->\"))\n", "plt.annotate(\"elbow\", xy=(5, cluster_scores[5]), xytext=(5, 4500),arrowprops=dict(arrowstyle=\"->\"))\n", "plt.annotate(\"elbow\", xy=(6, cluster_scores[6]), xytext=(5, 4500),arrowprops=dict(arrowstyle=\"->\"))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "WpPHUDDcYkqc" }, "source": [ "Δηλαδή στη συγκεκριμένη περίπτωση θα ήταν $k=3$, $k=5$ ή $k=6$.\n", "\n", "Το κριτήριο που χρησιμοποιήσαμε για την εύρεση του βέλτιστου $k$ μας φέρνει στη γενικότερη συζήτηση σχετικά με την αξιολόγηση της όποιας συσταδοποίησης." ] }, { "cell_type": "markdown", "metadata": { "id": "5P5k9Vw1yO0x" }, "source": [ "# Αξιολόγηση Συσταδοποίησης\n", "\n", "Όταν διενεργούμε συσταδοποίηση θέλουμε να επιτύχουμε τα δύο ακόλουθα#\n", "\n", "* Συνοχή εντός του κάθε cluster (intra-cluster cohesion). Θέλουμε τα σημεία να απέχουν όσο γίνεται λιγότερο από τον κεντροειδή του cluster. Συνήθως χρησιμοποιούμε κάποια μετρική του τύπου αθροίσματος τετραγώνων (SSE) που θέλουμε να ελαχιστοποιήσουμε.\n", "\n", "* Διαχωρισμός μεταξύ διαφορετικών clusters (inter-cluster separation). Θέλουμε οι κεντροειδείς των διαφόρων clusters να είναι όσο το δυνατόν πιο μακριά μεταξύ τους.\n", "\n", "Σημειώστε ότι το πρόβλημα της συσταδοποίησης είναι αλγοριθμικά δύσκολο. Συγκεκριμένα για τον kMeans ακόμα και για k=2 το πρόβλημα είναι NP-hard.\n", "\n", "Yπάρχουν δύο βασικοί τρόποι [αξιολόγησης αλγορίθμων συσταδοποίησης](https://en.wikipedia.org/wiki/Cluster_analysis#Evaluation_and_assessment): η *εξωτερική* (external) και η *εσωτερική* (internal)." ] }, { "cell_type": "markdown", "metadata": { "id": "zveA4SlUyGIb" }, "source": [ "### Εξωτερική Αξιολόγηση\n", "\n", "Η εξωτερική αξιολόγηση (Extrinsic evaluation) απαιτεί την εκτέλεση του αλγορίθμου σε ένα πρόβλημα επιβλεπόμενης μάθησης (που έχουμε τις ετικέτες δλδ ποιο δείγμα ανήκει σε ποια ομάδα) και την \"εξωτερική\" του αξιολόγηση με βάση αυτές. Δεν αποτελεί τυπική περίπτωση συσταδοποίησης και δεν θα την εξετάσουμε περισσότερο.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "UO23IBPxyrwW" }, "source": [ "\n", "### Εσωτερική Αξιολόγηση\n", "Η Εσωτερική αξιολόγηση (Intrinsic Evaluation) απαιτεί την ανάλυση της δομής ή της ευστάθειας των παραγόμενων από τον αλγόριθμο συστάδων. Για να το πετύχουμε αυτό, χρησιμοποιούμε διάφορους δείκτες ή συντελεστές.\n", "\n", "\n", "- [Dunn index](https://en.wikipedia.org/wiki/Dunn_index):\n", "Ο αριθμητής του dunn index είναι ένα μέτρο της **μικρότερης απόστασης μεταξύ δυο συστάδων** (π.χ. απόσταση μεταξύ των κέντρων τους). \n", "Στον παρονομαστή μπαίνει ένα μέτρο του **μεγέθους της μεγαλύτερης συστάδας** (π.χ. η απόσταση μεταξύ των 2 πιο απομακρυσμένων παραδειγμάτων που ανήκουν στη συστάδα αυτή).\n", "\n", "$$\n", "DI= \\frac{ min \\left( δ \\left( C_i, C_j \\right) \\right)}{ max \\, Δ_p }\n", "$$\n", "\n", "όπου $C_i, C_j$ είναι δυο τυχαία κέντρα συστάδων, $δ \\left( C_i, C_j \\right)$ είναι ένα μέτρο της απόστασής τους και $Δ_p$ είναι ένα μέτρο της \"διαμέτρου\" της συστάδας $p$, όπου $p \\in [0,k]$.\n", "\n", "- [Silhouette coefficient](https://en.wikipedia.org/wiki/Silhouette_(clustering)):\n", "$$\n", "s \\left( i \\right) = \\frac{b \\left( i \\right) -a \\left( i \\right) }{max \\left( a \\left( i \\right) , b \\left( i \\right) \\right)}\n", "$$\n", "\n", "Έστω $i$ ένα σημείο (point) οποιασδήποτε συστάδας. \n", "\n", "Το $a(i)$ είναι η μέση απόσταση του $i$ από όλα τα υπόλοιπα σημεία της συστάδας στην οποία ανήκει. Όσο μικρότερο είναι το $a(i)$, τόσο περισσότερο ομοιάζει το $i$ στα υπόλοιπα δείγματα της συστάδας.\n", "\n", "To $b(i)$ είναι η μικρότερη μέση απόσταση του $i$ από όλα τα σημεία σε οποιαδήποτε άλλη συστάδα, στην οποία το $i$ δεν ανήκει. Η συστάδα με την μικρότερη μέση απόσταση από το $i$ θεωρείται \"γειτονική\" (η δεύτερη καλύτερη επιλογή ομαδοποίησης).\n", "\n", "Μικρό $a(i)$ σημαίνει ότι η συστάδα του $i$ είναι συμπαγής ενώ μεγάλο $b(i)$ σημαίνει ότι το $i$ έχει μεγάλη απόσταση από την κοντινότερη συστάδα.\n", "\n", "Το εύρος τιμών που μπορεί να πάρει το $s(i)$ είναι στο $[-1, 1]$. Όσο πιο μεγάλο, τόσο πιο ξεκάθαρες οι συστάδες μεταξύ τους. Για να είναι το $s(i) \\approx 1$, πρέπει το $b(i) >> a(i)$.\n", "\n", "Για να αξιολογήσουμε τον αλγόριθμό μας συνήθως παίρνουμε το μέσο όρο των $s(i)$ για όλα τα $i$.\n", "\n" ] }, { "cell_type": "code", "metadata": { "id": "RQLcbDvmyO07" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "from sklearn.metrics import silhouette_score\n", "\n", "silhouette_scores = []\n", "for k in range(2, 100):\n", " km = KMeans(k, random_state=77)\n", " km.fit(points)\n", " preds = km.predict(points)\n", " silhouette_scores.append(silhouette_score(points, preds))\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.plot(range(2, 100), silhouette_scores)\n", "best_k = np.argmax(silhouette_scores) + 2 # +2 γιατί ξεκινάμε το range() από k=2 και όχι από 0 που ξεκινάει η αρίθμηση της λίστας\n", "plt.scatter(best_k, silhouette_scores[best_k-2], color='r') # για τον ίδιο λόγο το καλύτερο k είναι αυτό 2 θέσεις παρακάτω από το index της λίστας\n", "plt.xlim([2,100])\n", "plt.annotate(\"best k\", xy=(best_k, silhouette_scores[best_k-2]), xytext=(50, 0.39),arrowprops=dict(arrowstyle=\"->\")) # annotation\n", "print('Maximum average silhouette score for k =', best_k)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "0pcjZPrEyO0-" }, "source": [ "Το αποτέλεσμα του clustering για $k=61$ φαίνεται στο παρακάτω σχήμα." ] }, { "cell_type": "code", "metadata": { "id": "S_PmoTKYyO0-" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "preds = KMeans(best_k, random_state=77).fit_predict(points)\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1], c=preds, lw=0)\n", "axes_scaling = plt.axis('equal')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "KweXwZO5yO1B" }, "source": [ "Το αποτέλεσμα αυτό μπορεί να μην είναι επιθυμητό λόγω του μεγάλου αριθμού των cluster που δεν μας βοηθά να κατανοήσουμε τα δεδομένα. Αυτό που κάνουμε πρακτικά είναι να ορίσουμε ένα μέγιστο $k$ και να ψάξουμε το μέγιστο silhouette score μέχρι αυτό το μέγιστο $k$. Εδώ για παράδειγμα θέτουμε μέγιστο 10 ομάδες:" ] }, { "cell_type": "code", "metadata": { "id": "nwcsgif5yO1B" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "good_k = np.argmax(silhouette_scores[:10])+2\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.scatter(points[:,0], points[:,1], c=KMeans(good_k, random_state=77).fit_predict(points), lw=0)\n", "axes_scaling = plt.axis('equal')\n", "print('A good value for k is: k =', good_k)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "r3Q2lSE6yO1E" }, "source": [ "Αν θέλουμε να δούμε και το $k$ αυτό σε σχέση με το βέλτιστο:" ] }, { "cell_type": "code", "metadata": { "id": "XdKidx-dyO1E" }, "source": [ "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "plt.plot(range(2, 100), silhouette_scores)\n", "best_k = np.argmax(silhouette_scores)+2\n", "plt.scatter([good_k, best_k], [silhouette_scores[good_k-2], silhouette_scores[best_k-2]], color='r')\n", "plt.xlim([2,100])\n", "plt.annotate(\"best k\", xy=(best_k, silhouette_scores[best_k-2]), xytext=(50, 0.39),arrowprops=dict(arrowstyle=\"->\"))\n", "plt.annotate(\"good k\", xy=(good_k, silhouette_scores[good_k-2]), xytext=(10, 0.43),arrowprops=dict(arrowstyle=\"->\"))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "XbGDK8UEyO1H" }, "source": [ "Μια άλλη στρατηγική θα ήταν να ψάξουμε τα μεγαλύτερα $k$ και να δούμε από αυτά ποιο μας κάνει περισσότερο." ] }, { "cell_type": "code", "metadata": { "id": "CcDKBJIHyO1H" }, "source": [ "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "topN = 3\n", "plt.plot(range(2, 22), silhouette_scores[:20])\n", "candidate_k = np.argpartition(silhouette_scores[:20], -topN)[-topN:]\n", "plt.scatter([k+2 for k in candidate_k], [silhouette_scores[k] for k in candidate_k], color='r')\n", "plt.xlim([2,20])\n", "for k in candidate_k:\n", " plt.annotate(\"candidate k\", xy=(k+2, silhouette_scores[k]), xytext=(6, 0.38),arrowprops=dict(arrowstyle=\"->\"))\n", " print('For k = {:<2}, the average silhouette score is: {}.'.format(k+2, silhouette_scores[k]))" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "yog5EGV7yO1J" }, "source": [ "Το scikit-klearn διαθέτει διάφορες [μετρικές](http://scikit-learn.org/stable/modules/classes.html#clustering-metrics) για την αξιολόγηση αλγορίθμων συσταδοποίησης, οι οποίες επιτελούν εξωτερική αλλά κυρίως εσωτερική. \n", "\n", "Υπάρχουν μετρικές που ενώ βασίζοντα στον υπολογισμό διασποράς των συστάδων (intra-cluster variance) και των παραδειγμάτων στη συστάδα (inter-cluster variance) δεν είναι ιδιαίτερα κατάλληλες για την εύρεση του βελτιστου $k$.\n", "\n", "Για παράδειγμα η μετρική [Calinski-Harabaz](http://scikit-learn.org/stable/modules/generated/sklearn.metrics.calinski_harabaz_score.html):\n", "\n", "$$\n", "CH \\left( x \\right) = \\frac{B \\left( x \\right) / \\left( x - 1 \\right) }{W \\left( x \\right) / \\left( n - x \\right)},\n", "$$\n", "\n", "όπου $B \\left( x \\right)$ μια μετρική διασποράς ανάμεσα στις συστάδες (π.χ. το άθροισμα των τετραγώνων των αποστάσεων μεταξύ των κέντρων των συστάδεων) και $W \\left( x \\right)$ μια μετρική διασποράς μέσα στη συστάδα (π.χ. το άθροισμα των τετραγώνων των αποστάσεων ανάμεσα στα παραδείγματα της ίδιας συστάδας), μας δίνει την ακόλουθη γραφική παράσταση για διάφορα $k$:\n" ] }, { "cell_type": "code", "metadata": { "id": "zKEsUorAyO1J" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "from sklearn.metrics import calinski_harabasz_score\n", "\n", "ch_scores = []\n", "for k in range(2, 100):\n", " km = KMeans(k, random_state=77)\n", " km.fit(points)\n", " preds = km.predict(points)\n", " ch_scores.append(calinski_harabasz_score(points, preds))\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", " \n", "plt.plot(range(2, 100), ch_scores)\n", "ch_k = np.argmax(ch_scores)+2\n", "plt.scatter(ch_k, ch_scores[ch_k-2], color='r')\n", "plt.xlim([2,100])\n", "plt.annotate(\"best k\", xy=(ch_k, ch_scores[ch_k-2]), xytext=(50, 450),arrowprops=dict(arrowstyle=\"->\"))\n", "print('Maximum Calinski Harabaz score for k =', ch_k)" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "JyUPQ2XUyO1M" }, "source": [ "# Επιπλέον παρατηρήσεις για τον kMeans\n", "\n", "## Eπιλογή του k με gap statistics\n", "\n", "Εκτός από τις μεθόδους elbow και silhouette μπορεί να χρησιμοποιηθεί και η μέθοδος [gap statistics](https://datasciencelab.wordpress.com/2013/12/27/finding-the-k-in-k-means-clustering/) (παράδειγμα σε Python)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "LTJqJcGLx5I1" }, "source": [ "### Αρχικοποίηση\n", "\n", "Η σωστή αρχικοποίηση των κέντρων έχει μεγάλη σημασία για το αποτέλεσμα του αλγορίθμου. Ας δούμε ένα παράδειγμα. " ] }, { "cell_type": "code", "metadata": { "id": "Hp8siN-xyO1N" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "# Θα φτιάξουμε 3 ομάδες των 50 σημείων με κέντρα τις θέσεις (7,7), (17,7) και (17,17)\n", "np.random.seed(77)\n", "\n", "lowb, highb, var = 2, 12, 5\n", "\n", "p1 = np.random.rand(50,2) * var + lowb\n", "p2 = np.random.rand(50,2) * var + highb\n", "\n", "a = np.array([highb]*50)\n", "b = np.array([lowb]*50)\n", "c = np.zeros((50,2))\n", "c[:,0], c[:,1] = a, b\n", "p3 = np.random.rand(50,2) * var + c\n", "\n", "points = np.concatenate([p1, p2, p3])\n", "\n", "# Τοποθετούμε 3 κέντρα στις θέσεις (0,20), (1,19) και (2,18)\n", "centroids = np.array([[0,20], [1,19], [2,18]])\n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "map_colors = {0:'orange', 1:'deepskyblue', 2:'orchid'}\n", "color_list = ['orange', 'deepskyblue', 'orchid']\n", "\n", "plt.scatter(points[:,0], points[:,1], lw=0, s=30, label='data points')\n", "plt.scatter(centroids[:,0], centroids[:,1], c=color_list, s=80, label='centroids')\n", "plt.xlim([-1,18])\n", "plt.ylim([1,23])\n", "axes_scaling = plt.axis('equal')\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.title('KMeans: Centroid Initialization')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "gPOa_k-0yO1P" }, "source": [ "Όπως βλέπουμε, έχουμε 3 ξεκάθαρες συστάδες και 3 κέντρα. Κανονικά θα θέλαμε να πέσει ένα κέντρο πάνω σε κάθε συστάδα. Τρέχουμε μια εποχή του αλγορίθμου να δούμε πώς θα τα πάει." ] }, { "cell_type": "code", "metadata": { "id": "n95Pr8USyO1Q" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "new_centroids = update_centers(centroids, points) \n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "colors = [map_colors[i] for i in assign_cluster(new_centroids, points)]\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(centroids[:,0], centroids[:,1], c=color_list, s=80, label='centroids', alpha=0.5)\n", "plt.scatter(new_centroids[:,0], new_centroids[:,1], c=color_list, s=80, label='centroids')\n", "plt.xlim([-1,18])\n", "plt.ylim([1,23])\n", "axes_scaling = plt.axis('equal')\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.title('KMeans: First step')\n", "plt.arrow(centroids[2,0], centroids[2,1], new_centroids[2,0]-centroids[2,0], new_centroids[2,1]-centroids[2,1], \n", " length_includes_head=True, head_width=0.5, color='black')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "QKwx9SssyO1S" }, "source": [ "Η πρώτη εποχή ενημέρωσε το ένα από τα 3 κέντρα. Ας συνεχίσουμε τη διαδικασία..." ] }, { "cell_type": "code", "metadata": { "id": "ccWyejbTyO1S" }, "source": [ "# ΚΩΔΙΚΑΣ:\n", "# --------------------------------------------\n", "\n", "centroids = new_centroids\n", "new_centroids = update_centers(centroids, points) \n", "\n", "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "colors = [map_colors[i] for i in assign_cluster(new_centroids, points)]\n", "\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(new_centroids[:,0], new_centroids[:,1], c=color_list, s=80, label='centroids')\n", "plt.xlim([-1,18])\n", "plt.ylim([1,23])\n", "axes_scaling = plt.axis('equal')\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.title('KMeans: N step')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "AxZDpYCyyO1U" }, "source": [ "Όσες φορές και να τρέξουμε το παραπάνω κελί, δεν θα μετακινηθούν τα κέντρα. Σχεδιάζοντας και το όριο απόφασης μπορούμε να το καταλάβουμε αυτό καλύτερα." ] }, { "cell_type": "code", "metadata": { "id": "YMI8W1CSyO1V" }, "source": [ "# ΣΧΕΔΙΑΣΗ:\n", "# --------------------------------------------\n", "\n", "decision_boundary = generate_perp_bisector(centroids[1:,:])\n", "plt.scatter(points[:,0], points[:,1], c=colors, lw=0, s=30, label='data points')\n", "plt.scatter(new_centroids[:,0], new_centroids[:,1], c=color_list, s=80, label='centroids')\n", "plt.plot(range(-1,20), decision_boundary(range(-1,20)), c='black', label='decision boundary')\n", "plt.xlim([-1,18])\n", "plt.ylim([1,23])\n", "axes_scaling = plt.axis('equal')\n", "plt.tick_params(axis='both', which='both', bottom=False, left=False, top=False, right=False, labelbottom=False, labelleft=False)\n", "plt.title('KMeans: Decision Boundary')" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "metadata": { "id": "SD9NpWgPyO1Y" }, "source": [ "Επειδή όλα τα παραδείγματα έχουν ανατεθεί στο 1 από τα 3 κέντρα, τα υπόλοιπα 2 είναι αδύνατο να ενημερωθούν. Το πρόβλημα στην περίπτωση αυτή ήταν η κακή αρχικοποίηση των κέντρων. \n" ] }, { "cell_type": "markdown", "metadata": { "id": "rSqcAAEPaIJn" }, "source": [ "\n", "#### kMeans++\n", "\n", "Η πιο γνωστή τεχνική για την αρχικοποίηση των κέντρων είναι ο [K-means++](https://en.wikipedia.org/wiki/K-means%2B%2B).\n", "\n", "Η συγκεκριμένη τεχνική είναι και η προεπιλεγμένη στην υλοποίηση του scikit-learn. Επίσης το scikit-learn τρέχει τον αλγόριθμο 10 φορές για διαφορετικές αρχικές θέσεις και επιλέγει το αποτέλεσμα που ελαχιστοποιεί την αδράνεια. \n" ] }, { "cell_type": "markdown", "metadata": { "id": "FcmaY8gnaM6x" }, "source": [ "\n", "### Πολυπλοκότητα\n", "\n", "Η μέση χρονική πολυπλοκότητα του αλγορίθμου $K$-μέσων εξαρτάται γραμμικά από:\n", "\n", "- Το πλήθος των κέντρων $k$.\n", "- Το πλήθος των παραδειγμάτων $N$.\n", "- Το πλήθος των διαστάσεων του κάθε παραδείγματος $d$.\n", "- Το πλήθος των εποχών που θα τρέξει μέχρι να συγκλίνει $i$.\n", "\n", "$$\n", "O \\left( k \\cdot N \\cdot d \\cdot i \\right)\n", "$$\n", "\n", "Στην πράξη ο $k$-means είναι ένας από τους **γρηγορότερους** αλγορίθμους συσταδοποίησης που έχουμε. To πρόβλημά του είναι ότι κολλάει πολύ εύκολα σε **τοπικά ελάχιστα** (όπως είδαμε πριν με την κακή αρχικοποίηση).\n", "\n", "Η αρχικοποίηση του αλγορίθμου με τη χρήση του k-means++ φέρει μια επιπλέον πολυπλοκότητα στο πρόβλημά μας, όμως επειδή βάζει τα κέντρα πιο στρατηγικά στο χώρο μπορεί να τερματίσει τον αλγόριθμο σε λιγότερες εποχές (πέρα από την καλύτερο συσταδοποίηση που επιτυγχάνει). Είναι προφανές πως αν τρέξουμε τον αλγόριθμο πολλές φορές (όπως κάνει το scikit-learn) για να επιτύχουμε τη βέλτιστη απόδοση, θα πάρει παραπάνω χρόνο.\n" ] } ] }