{ "cells": [ { "cell_type": "markdown", "id": "f739280c-1c48-437e-b8f6-beef3fc13def", "metadata": {}, "source": [ "# 11 septembre 2023 : *clustering*\n", "## Qu'est-ce que le *clustering* (aussi appelé *quantification vectorielle*) ?\n", "Le *clustering* consiste à **regrouper** des données (ou des vecteurs) qui sont similaires. On cherche à identifier des groupes (*clusters*), à diviser l'espace en différentes zones. Les points centraux (centres de masse) de ces zones sont appelés *centroïdes*. Ce sont de bons représentants des propriétés de leur groupe.\n", "Une fois les groupes trouvés, on peut associer à chacun d'eux un label.\n", "\n", "Quelques exemples :\n", "\n", "- regrouper des patients sur base de caractéristiques physiques, de résultats, de symptômes, etc. ;\n", "- regrouper des livres en catégories sur base de la fréquence des mots qu'ils contiennent ;\n", "- identifier des profils d'acheteurs sur base de leur historique d'achats.\n", "\n", "Difficultés à souligner :\n", "\n", "- on n’a aucune idée de quelles données vont dans quel groupe (c’est de l'apprentissage **non supervisé**)\n", "- le nombre de *clusters* n'est pas forcément connu d'avance et peut faire l'objet d'une phase préalable exploratoire.\n", "\n", "Inspiration :\n", "\n", "- S. Boyd et L. Vandenberghe, *Introduction to \n", "Applied Linear Algebr: Vectors, Matrices, and Least Squares*, Cambridge University Press, 2018.\n", "- M. Verleysen, *LELEC2870: Machine Learning*, UCLouvain, 2012." ] }, { "cell_type": "markdown", "id": "e9a7ffd3-5b10-4e02-8a20-8167fecc216b", "metadata": {}, "source": [ "## Le jeu de données : les fleurs d'iris\n", "Ce jeu de données contient 150 observations réalisées sur trois espèces d’iris (l’*iris setosa*, l’*iris versicolor* et l’*iris virginica*). Chaque observation correspond à un vecteur à quatre composantes : largeur et longueur du pétale ainsi que largeur et longueur du sépale. On a aussi à disposition, pour chaque observation, l'espèce d'iris. On n'utilisera pas cette information lors de l'apprentissage du modèle mais elle permettra de quantifier les performances de l'algorithme. \n", "\n", "\"Iris\n", "\n", "### Exercice 0 : visualisation des données\n", "Le jeu de données est téléchargé ci-dessous. Visualise sur une figure les 150 observations sur base de la taille des pétales (longueur des pétales en abscisses et largeur en ordonnées)." ] }, { "cell_type": "code", "execution_count": 1, "id": "6695aad5", "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "C:\\Users\\s.guerit\\AppData\\Local\\mambaforge\\lib\\site-packages\\scipy\\__init__.py:155: UserWarning: A NumPy version >=1.18.5 and <1.25.0 is required for this version of SciPy (detected version 1.25.0\n", " warnings.warn(f\"A NumPy version >={np_minversion} and <{np_maxversion}\"\n" ] } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import pandas\n", "import sklearn\n", "from sklearn import datasets\n", "\n", "iris = datasets.load_iris()\n", "data = pandas.DataFrame(iris.data)\n", "data.columns = ['Sepal_Length','Sepal_Width','Petal_Length','Petal_Width']\n", "true_labels = pandas.DataFrame(iris.target)\n", "true_labels.columns = ['Targets']\n", "\n", "# Visualisation des données\n", "# ..." ] }, { "cell_type": "markdown", "id": "da0109b3-716c-4ef5-b5db-fe499ee35dd7", "metadata": {}, "source": [ "## Les ingrédients du clustering\n", "Pour pouvoir réaliser du clustering dans un espace à $n$ dimensions (chaque donnée est un vecteur $x$ qui possède $n$ composantes, c'est-à-dire $x\\in\\mathbb R^n$), on a besoin \n", "\n", "1. d'un ensemble de $Q$ centroïdes (appelé *codebook*) : $m = \\{y^j \\in \\mathbb R^n,1\\le j\\le Q\\}$ ;\n", "2. d'une fonction de quantification $q$ : $\\mathbb R^n \\to \\mathbb R^n, x^i \\mapsto q(x^i) = y^j$.\n", "\n", "On va donc commencer par implémenter fonction d'initialisation du codebook `codebook_initialization` et la fonction de quantification `centroids_assignment`." ] }, { "cell_type": "markdown", "id": "695da9c1-ffeb-4577-bc79-199166609116", "metadata": {}, "source": [ "### Exercice 1 : initialiser le *codebook*\n", "Il existe plusieurs façons de choisir le *codebook* initial. Un choix assez répandu est de choisir aléatoirement $Q$ données du jeu de données et d'en faire des centroïdes. D'autres approches existent pour vérifier, par exemple, que les centroïdes choisis sont suffisamment espacés les uns des autres.\n", "\n", "Écris la fonction `codebook_initialization` qui prend comme input le jeu de données `data` et le nombre de clusters souhaité `Q` et renvoie les centroïdes initiaux dans `centroids`. Fais en sorte que les trois centroïdes soient choisis aléatoirement et soient distincts." ] }, { "cell_type": "code", "execution_count": 2, "id": "e4a48714-e5f7-4658-95e0-bd39b3a6233d", "metadata": {}, "outputs": [], "source": [ "def codebook_initialization(data,Q):\n", " # ...\n", " return centroids" ] }, { "cell_type": "markdown", "id": "91220cbd-d4f5-42f5-809c-6a09e2e3a659", "metadata": {}, "source": [ "Tu peux maintenant initialiser le codebook qui servira pour le jeu de données des iris. On choisit $Q=3$. Affiche ensuite les observations et les centroïdes en plus grand et dans une autre couleur (une couleur par centroïde)." ] }, { "cell_type": "code", "execution_count": null, "id": "05a97cb8-2df7-42a4-880c-b6256940e7b6", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "6a08d519", "metadata": {}, "source": [ "### Exercice 2 : implémenter la fonction de quantification \n", "En général, la fonction de quantification consiste à associer une donnée au centroïde *le plus proche*. Cette notion de *plus proche voisin* dépend de la mesure de distance considérée. Ici, nous allons considérer la distance basée sur la norme euclidienne (comme vu ce matin).\n", "\n", "Complète la fonction de quantification `centroids_assignment` donnée ci-dessous. Celle-ci prend en entrée une liste `data` contenant l'ensemble des données et une liste `centroids`. Chaque élément de ces listes sont des vecteurs de dimension $n$ (soit une donnée, soit un centroïde). La sortie est le vecteur `group_labels` contenant les numéros des centroïdes associés à chaque donnée." ] }, { "cell_type": "code", "execution_count": 3, "id": "f577b81a", "metadata": {}, "outputs": [], "source": [ "def centroids_assignment(data,centroids):\n", " # ...\n", " return group_labels" ] }, { "cell_type": "markdown", "id": "e9a43a19-cb01-4278-9af8-b8f9630afe1f", "metadata": {}, "source": [ "Pour voir si cela fonctionne bien, applique cette fonction au jeu de données et affiche les données avec la couleur correpondant au centroïde le plus proche." ] }, { "cell_type": "code", "execution_count": null, "id": "9c768c5c-d229-4e3f-af90-e4c621cc30ae", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "becfde17-7c92-48ac-9b8c-f9c8c6bfc6d2", "metadata": {}, "source": [ "## L'algorithme $k$-means\n", "L'algorithme $k$-means se base sur le principe de Lloyd. Il contient par conséquent les étapes suivantes :\n", "\n", "1. Initialisation du codebook.\n", "2. Application de la fonction de quantification à *toutes les données* et évaluation de l'erreur de quantification $E$.\n", "3. Si $E$ est assez faible, l'algorithme s'arrête.\n", "4. Les centroïdes sont mis à jour via le *centre de gravité des données* $x^i$ associées à $y^j$ à l'étape 2.\n", "5. Retour à l'étape 2.\n", "\n", "Quelques points d'attention : \n", "\n", "- le codebook est modifié sur base de l'ensemble de la base de données ;\n", "- $E$ diminue à chaque itération (on va le montrer sur l'exemple) ;\n", "- il y a un risque de tomber dans un minimum local ;\n", "- l'initialisation est très importante !\n", "\n", "Dans la suite, on va donc implémenter :\n", "\n", "- la fonction de mise à jour des centroïdes `centroids_update` ;\n", "- la fonction d'évaluation de l'erreur de quantification `E`.\n", "\n", "### Exercice 3 : implémenter la fonction de mise à jour des centroïdes\n", "Dans l'algorithme $k$-means, les centroïdes sont mis à jour sur base de *l'ensemble des données*. Implémente la fonction `centroids_update` ci-dessous. Celle-ci a pour arguments d'entrées `data`, `centroids` et `group_labels` (l'output de la fonction `centroids_assignment`). En sortie, elle renvoie les nouveaux centroïdes, `new_centroids`. Nous verrons plus loin d'autres algorithmes qui mettent à jour le codebook pour chaque nouvelle donnée (et pas en utilisant l'entièreté du jeu de données)." ] }, { "cell_type": "code", "execution_count": 4, "id": "2ae982c6-5722-430c-b572-f13baaf13b0c", "metadata": {}, "outputs": [], "source": [ "def centroids_update(data, centroids, group_labels):\n", " # ...\n", " return new_centroids" ] }, { "cell_type": "markdown", "id": "16889efa-4706-4f92-b905-2623524582b6", "metadata": {}, "source": [ "Applique cette fonction aux centroïdes initiaux et visualise ensuite les nouveaux centroïdes obtenus. Est-ce que ta fonction fonctionne correctement ?" ] }, { "cell_type": "code", "execution_count": null, "id": "f52643ce-77d3-419a-96f9-3f3342665443", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "3b1a8f4e-4492-4ed9-9ef4-d9567169003a", "metadata": {}, "source": [ "### Exercice 4 : évaluer l'erreur de quantification\n", "Comme dans une régression, on essaie ici de *minimiser* la somme des distances au carré entre chaque observation et le représentant (centroïde) du cluster auquel elle appartient. Cette erreur de quantification (aussi appelée *fonction objectif* que l'on souhaite minimiser) est notée $E$. Supposons qu'il y a $P$ observations,\n", "$$E = \\frac{1}{P}\\sum_{i=1}^P \\| x^i - q(x^i) \\|^2.$$\n", "Écris la fonction `quantification_error` qui prend comme arguments d'entrée `data`, `centroids` et `group_labels` et renvoie en sortie un nombre réel positif `E`." ] }, { "cell_type": "code", "execution_count": 5, "id": "fffdf986-f040-4d1a-a53b-c699b5c6a160", "metadata": {}, "outputs": [], "source": [ "def quantification_error(data,centroids,group_labels):\n", " # ...\n", " return E" ] }, { "cell_type": "markdown", "id": "18c852d9-200d-4251-ac0f-0f83aec6ea8e", "metadata": {}, "source": [ "Quelle est l'erreur de quantification commise avec le clustering actuel du jeu de données de l'iris ?" ] }, { "cell_type": "code", "execution_count": null, "id": "2b7c2659-ef72-4a02-9029-e4a908bde5e3", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "abddc618-d7fa-488d-87a6-ef18855f4b69", "metadata": {}, "source": [ "### Exercice 5 : on teste k-means !\n", "Maintenant, tu peux écrire la fonction `kmeans_algorithm` qui procède tel que décrit en début de section et qui utilise les fonctions décrites précédemment. Concernant le critère d'arrêt de l'algorithme, tu peux par exemple t'arrêter à l'iteration $k$ lors $\\frac{E_{k-1}-E_k}{E_k} \\le 10^{-3}$. Dans ce cas, on peut dire que l'erreur de quantification se stabilise et que l'algorithme a quasiment convergé.\n", "\n", "La fonction prend comme arguments d'entrée le jeu de données `data` et les centroïdes initiaux `centroids`. Elle renvoie les nouveaux centroïdes `new_centroids`, les labels `group_labels` correspondant à chaque observation, un vecteur `E_iter` contenant les erreurs de quantification obtenues à chaque itération de l'algorithme et un entier `iteration` correspondant au nombre d'itérations avant l'arrêt de l'algorithme." ] }, { "cell_type": "code", "execution_count": 6, "id": "5cb7dd6c-cb18-4cf1-9fed-06e6306bfbd3", "metadata": {}, "outputs": [], "source": [ "def kmeans_algorithm(data, centroids):\n", " # ...\n", " return new_centroids, group_labels, E_iter, iteration" ] }, { "cell_type": "markdown", "id": "335d805f-e7ca-4780-863a-d1b2355700a9", "metadata": {}, "source": [ "Visualise les clusters obtenus ainsi que leurs centroïdes. Affiche également sur un plot l'évolution de l'erreur de quantification en fonction des itérations de l'algorithme." ] }, { "cell_type": "code", "execution_count": null, "id": "559c0911-760d-4ba8-aa28-294f2abdc268", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "68e60c7e", "metadata": {}, "source": [ "**Pour information** : l'algorithme converge mais n'atteint pas forcément le minimum global (souvent, il atteint même plutôt un minimum *local*). Cela dépend des conditions initiales de l'algorithme (le choix du *codebook* initial). Une pratique courante est d'exécuter plusieurs fois l'algorithme $k$-means (par exemple, 10 fois) et de considérer l'occurence qui mène à la plus petite erreur de quantification $E$." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.7" }, "vscode": { "interpreter": { "hash": "4a2701644a567983fe4c710d2a706eee629c52060847d7c704aa57db76d57a44" } } }, "nbformat": 4, "nbformat_minor": 5 }