{ "metadata": { "name": "", "signature": "sha256:a412dda13c83e684c564bce0e34d5571ccc26ea6455d6deffa8e86ca20337c35" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "K-means" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans cette d\u00e9mo nous allons impl\u00e9menter K-means avec la librairie Numpy. Pas de Theano aujourd'hui, et probablement pas pour le reste de la session mis \u00e0 part dans vos projets, ceux qui sont \u00e0 la ma\u00eetrise.\n", "\n", "\n", "Qu'est-ce qu'on va faire?\n", "\n", "- Impl\u00e9menter le mod\u00e8le\n", " - Calculer les assignations $z$\n", " - Calculer les mise \u00e0 jours de $mu$\n", " - Calculer le co\u00fbt $J$\n", "- Tester sur un ensemble de 2 gaussiennes\n", "- Tester sur un ensemble de 5 gaussiennes\n", "- Am\u00e9liorer l'initialisation\n", "- Tester sur un ensemble de 5 gaussiennes\n", "- Entra\u00eener plusieurs k-means et s\u00e9lectionner le meilleur\n" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Court rappel" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous pouvez relire vos notes de cours pour plus d'explications. Sinon, voici un court rappel.\n", "\n", "Les param\u00e8tres du k-means sont les moyennes des centro\u00efdes $\\mu_j$ o\u00f9 $j\u00a0\\in \\{1, 2, \\dots, k\\}$.\n", "\n", "$z_{n,k}$ ne sont pas des param\u00e8tres, se sont des variables latentes, donc non-observ\u00e9es. Pour comparaison, un exemple $x_n \\in Data$ est une variable observ\u00e9e. Le mod\u00e8le **n'apprend pas** les variables latentes, il les inf\u00e8re \u00e0 partir de la valeur des param\u00e8tres.\n", "\n", "**1)** Les variables latentes, $z_{n,k}$, sont calcul\u00e9es de la mani\u00e8re suivante\n", "\n", "$ z_{n,k} = \\left\\{ \n", " \\begin{array}{l l}\n", " 1 & \\quad \\text{si } k=\\text{arg min}_j \\|x_n-\\mu_j||^2\\\\\n", " 0 & \\quad \\text{sinon}\n", " \\end{array} \\right.$\n", " \n", "o\u00f9 $x_n$ est le $n$-i\u00e8me exemple et $\\mu_j$ la moyenne du $j$-i\u00e8me centro\u00efde.\n", "\n", "**2)** Sachant les variables latentes, on peut optimiser les param\u00e8tres $\\mu_k$. On obtient alors\n", "\n", "$\\displaystyle \\mu_k = \\frac{1}{\\sum_n z_{n,k}}\\sum_n z_{n,k}x_n$\n", "\n", "Ces deux phases correspondent \u00e0 l'algorithme EM. La premi\u00e8re est le calcul de l'esp\u00e9rance \u00e0 partir des param\u00e8tres estim\u00e9 $\\mu_k$ \u00e0 une it\u00e9ration donn\u00e9e et la deuxi\u00e8me est la maximisation de la (log-)vraisemblance.\n", "\n", "\n", "La fonction de co\u00fbt utilis\u00e9e sera\n", "\n", "$\\displaystyle J = \\sum_{n=1}^N\\sum_{k=1}^K z_{n,k}\\|x_n-\\mu_k\\|^2$" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Impl\u00e9mentation des fonctions de base pour le mod\u00e8le" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous impl\u00e9menterez les fonctions de base du mod\u00e8le une \u00e0 une. Suivez les instructions et lisez attentivement les messages d'erreur et tout devrait bien aller. " ] }, { "cell_type": "code", "collapsed": false, "input": [ "%load_ext autoreload\n", "%autoreload 2\n", "%pylab inline\n", "import numpy as np\n", "import utilitaires8 as utilitaires\n", "import time" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Initialisation des centro\u00efdes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Un mani\u00e8re bien simple d'initialiser les centro\u00efdes est de g\u00e9n\u00e9rer au hasard des points contenus \u00e0 l'int\u00e9rieur de l'espace occup\u00e9e par les donn\u00e9es. Pour ce faire, vous devez \n", "\n", "1. calculer le minimum et le maximum pour chaque dimension dans les donn\u00e9es\n", "2. g\u00e9n\u00e9rer les donn\u00e9es avec la fonction model.rng.uniform en sp\u00e9cifiant le bon format (size = ?)\n", "\n", "Une fonction de test est pr\u00e9sente \u00e0 la fin de la cellule, vous ne pourrez pas ex\u00e9cuter la fonction tant qu'elle produira des erreurs! :) Un test similaire sera pr\u00e9sent dans toutes les fonctions que vous impl\u00e9menterez \u00e0 l'int\u00e9rieur de cette section." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_centroids_naif(model, data):\n", " \"\"\"\n", " Initialise les param\u00e8tres mu du mod\u00e8le.\n", " \n", " Arguments\n", " ---------\n", " model: objet Kmeans\n", " une instance de la classe Kmeans \n", " le nombre de centro\u00efde est donn\u00e9 par model.k\n", " les param\u00e8tres sont sous model.mu\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " \n", " Notes\n", " -----\n", " La fonction ne renvoie rien\n", " \"\"\"\n", " \n", " # utilisez model.rng.uniform pour g\u00e9n\u00e9rer les poids au hasard\n", " model.mu = np.zeros((model.k, data.shape[1]))\n", " \n", "utilitaires.Tests().test_init_centroids_naif(init_centroids_naif)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Calcul des assignations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour calculer les assignations, nous avons besoin de $X$ et $\\mu$, nous aurons donc les arguments `data` et `mu` pour la fonction `z()`.\n", "\n", "Rappel:\n", "\n", "$ z_{n,k} = \\left\\{ \n", " \\begin{array}{l l}\n", " 1 & \\quad \\text{si } k=\\text{arg min}_j \\|x_n-\\mu_j||^2\\\\\n", " 0 & \\quad \\text{sinon}\n", " \\end{array} \\right.$\n", " \n", "Commencez par faire une impl\u00e9mentation simple, o\u00f9 vous bouclez sur tout les \u00e9l\u00e9ments un \u00e0 un. Vous devez donc\n", "\n", "1. initialiser un liste z vide\n", "2. boucler sur chaque \u00e9l\u00e9ment $x_n \\in Data$\n", " 3. boucler sur chaque centro\u00efde $\\mu_j$, $j \\in \\{1,2,\\dots,k\\}$\n", " 4. Pour chaque pair $(x_n, \\mu_j)$, calculer la distance $\\|x_n-\\mu_j\\|^2$\n", " 5. Trouver la distance la plus petite et construire un vecteur one-hot repr\u00e9sentant l'index respectif\n", " 6. ajouter le vecteur one-hot \u00e0 z" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def z(data, mu):\n", " \"\"\"\n", " Inf\u00e8re les variables latentes \u00e0 partir de mu\n", " \n", " Arguments\n", " ---------\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " mu: ndarray\n", " matrice de dimension (k, d)\n", " \n", " Returns\n", " -------\n", " ndarray\n", " matrice de dimension (n, k) repr\u00e9sentant les variables latentes\n", " \"\"\"\n", " \n", " # la liste des vecteurs one-hot\n", " zs = []\n", " # le nombre de centro\u00efde\n", " K = mu.shape[0]\n", " \n", " # \u00c9crivez le code ici\n", " \n", " return np.array(zs)\n", "\n", "utilitaires.Tests().test_z(z)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "(bonus) Calcul *rapide* des assignations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'impl\u00e9mentation pr\u00e9c\u00e9dente, si vous avez suivi les indications, est tr\u00e8s lente inutilement. Ce n'est pas grave cependant, alors ne perdez pas votre temps ici et passez \u00e0 la mise \u00e0 jour des centro\u00efdes si vous ne comprenez pas le *broadcasting*.\n", "\n", "Le *broadcasting* est la *diffusion* d'un *array* de plus petite dimension sur un plus grand. L\n", "\n", ">**R\u00e8gle**\n", ">\n", ">Pour pouvoir *broadcaster*, le format des axes de qui se chevauchent pour chaque *array* doivent avoir la m\u00eame dimension ou \n", "> une d'entre elle doit \u00eatre de dimension 1.\n", "\n", "Regardez la prochaine cellule et jouez avec les dimensions des matrices pour voir l'effet sur le *broadcasting*\n", "\n", "Vous pouvez lire ce cours tutoriel (en anglais) pour une explication plus d\u00e9taill\u00e9 du broadcasting.\n", "http://wiki.scipy.org/EricsBroadcastingDoc" ] }, { "cell_type": "code", "collapsed": false, "input": [ "# Code pour tester le broadcasting\n", "try:\n", " print (np.zeros((10, 2)) * np.zeros((50, 2))).shape\n", "except ValueError as e:\n", " print str(e)\n", "\n", "try:\n", " print (np.zeros((10, 50, 2)) * np.zeros((50, 2))).shape\n", "except ValueError as e:\n", " print str(e) \n", " \n", "try:\n", " print (np.zeros((10, 50, 2)) * np.zeros((50, 2))).shape\n", "except ValueError as e:\n", " print str(e) " ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le broadcasting permet de calculer la diff\u00e9rence entre chaque exemple $x_n$ et chaque centro\u00efde $\\mu_j$ en une seule op\u00e9ration. Il suffit de transformer le format de `data` de mani\u00e8re \u00e0 ce que le broadcasting soit possible. Le r\u00e9sultat sera alors de format $(N, K, D)$ o\u00f9 $N$ est le nombre d'exemple, $K$ le nombre de centro\u00efdes et $D$ le nombre de dimensions de $X$.\n", "\n", "Le calcul de la distance est ensuite trivial si vous avez r\u00e9ussi \u00e0 calculer la distance grace au broadcasting. Pas d'aide pour le reste dans le bonus. :)" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def z_rapide(data, mu):\n", " \"\"\"\n", " Inf\u00e8re *rapidement* les variables latentes \u00e0 partir de mu\n", " \n", " Arguments\n", " ---------\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " mu: ndarray\n", " matrice de dimension (k, d)\n", " \n", " Returns\n", " -------\n", " ndarray\n", " matrice de dimension (n, k) repr\u00e9sentant les variables latentes\n", " \"\"\"\n", " \n", " # \u00c9crivez le code ici.\n", " \n", " return \n", " \n", "utilitaires.Tests().test_z(z_rapide)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\u00c7a ne sert \u00e0 rien d'impl\u00e9menter une version plus rapide si on ne compare pas le temps de calcul! Testez votre impl\u00e9mentation ici. Vous devriez voir une am\u00e9lioration de plus de 100x." ] }, { "cell_type": "code", "collapsed": false, "input": [ "utilitaires.Tests().time_z(init_centroids_naif, z, z_rapide)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Mise \u00e0 jour des centro\u00efdes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La mise \u00e0 jour n\u00e9cessite les donn\u00e9es et les variables latentes $z_{n,k}$.\n", "\n", "Rappel :\n", "\n", "$\\displaystyle \\mu_k = \\frac{1}{\\sum_n z_{n,k}}\\sum_n z_{n,k}x_n$\n", " \n", "Commencez encore par faire une impl\u00e9mentation simple, o\u00f9 vous bouclez sur tout les \u00e9l\u00e9ments un \u00e0 un. Vous devez donc\n", "\n", "1. initialiser un accumulateur $A$ \u00e0 0, de dimension $(K, D)$ o\u00f9 $K$ est le nombre de centro\u00efdes et $D$ est le nombre de dimension de $X$\n", "2. boucler sur chaque \u00e9l\u00e9ment $x_n \\in Data$\n", " 3. trouver $\\text{arg min}_k z_{n,k}$\n", " 4. \u00e0 partir du $k$ trouv\u00e9, additionner la valeur de $x_n$ \u00e0 $A_k$\n", "5. Diviser l'accumulateur par la somme des variables latentes pour chaque centro\u00efdes ($\\sum_n z_{n,k}$)" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def mise_a_jour(model, data, z):\n", " \"\"\"\n", " Fait la mise \u00e0 jour des param\u00e8tres \u00e9tant donn\u00e9 les variables latentes\n", " \n", " Arguments\n", " ---------\n", " model: objet Kmeans\n", " une instance de la classe Kmeans \n", " les param\u00e8tres sont sous model.mu\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " z: ndarray\n", " matrice de dimension (n, k)\n", " \n", " Notes\n", " -------\n", " La fonction ne renvoie rien\n", " \"\"\"\n", " \n", " # Initialisation de l'accumulateur\n", " accum = np.zeros(model.mu.shape)\n", " \n", " # \u00c9crivez votre code ici\n", " \n", " # Mise \u00e0 jour des poids\n", " model.mu = accum\n", " \n", "utilitaires.Tests().test_mise_a_jour(mise_a_jour)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "(bonus) Mise \u00e0 jour *rapide* des centro\u00efdes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le calcul $\\sum_n z_{n,k}x_n$ peut \u00eatre vu comme un produit matriciel. En effet, soit $X$, une matrice de dimension $(N,D)$ repr\u00e9sentant les exemples et $Z$, une matrice de dimension $(N, K)$ repr\u00e9sentant les variables latentes. Alors \n", "\n", "$\\displaystyle \\sum_n z_{n,k}x_n = Z^TX$\n", "\n", "La mise \u00e0 jour s'\u00e9crit donc sur une seule ligne \u00e0 l'aide de `numpy`. " ] }, { "cell_type": "code", "collapsed": false, "input": [ "def mise_a_jour_rapide(model, data, z):\n", " \"\"\"\n", " Fait la mise \u00e0 jour *rapide* des param\u00e8tres \u00e9tant donn\u00e9 les variables latentes\n", " \n", " Arguments\n", " ---------\n", " model: objet Kmeans\n", " une instance de la classe Kmeans \n", " les param\u00e8tres sont sous model.mu\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " z: ndarray\n", " matrice de dimension (n, k)\n", " \n", " Notes\n", " -------\n", " La fonction ne renvoie rien\n", " \"\"\"\n", " \n", " # Remplacez la ligne suivante par votre code\n", " model.mu = np.zeros((model.k, data.shape[1]))\n", " \n", "utilitaires.Tests().test_mise_a_jour(mise_a_jour_rapide)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous devriez voir une am\u00e9liration de l'ordre de 100x." ] }, { "cell_type": "code", "collapsed": false, "input": [ "utilitaires.Tests().time_mise_a_jour(init_centroids_naif, z, mise_a_jour, mise_a_jour_rapide)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Calcul du co\u00fbt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour le calcul du co\u00fbt, nous avons de nouveau besoin des donn\u00e9es et des variables latentes $z_{n,k}$, mais aussi des param\u00e8trs $\\mu_j$.\n", "\n", "Rappel :\n", "\n", "$\\displaystyle J = \\sum_{n=1}^N\\sum_{k=1}^K z_{n,k}\\|x_n-\\mu_k\\|^2$\n", " \n", "Commencez \u00e0 nouveau par impl\u00e9mentater une version simple, o\u00f9 vous bouclez sur tout les \u00e9l\u00e9ments un \u00e0 un. Vous devez donc\n", "\n", "1. initialiser un accumulateur `accum` (scalaire) \u00e0 0\n", "2. boucler sur chaque \u00e9l\u00e9ment $x_n \\in Data$\n", " 3. trouver $\\text{arg min}_k z_{n,k}$\n", " 4. \u00e0 partir du $k$ trouv\u00e9, additionner la distance $\\|x_n-\\mu_k\\|^2$ \u00e0 `accum` " ] }, { "cell_type": "code", "collapsed": false, "input": [ "def cout(mu, data, z):\n", " \"\"\"\n", " Calcule le co\u00fbt \u00e0 partir des param\u00e8tres et des variables latentes.\n", " \n", " Arguments\n", " ---------\n", " mu: ndarray\n", " matrice de dimension (k, d)\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " z: ndarray\n", " matrice de dimension (n, k)\n", " \n", " Returns\n", " -------\n", " float\n", " Renvoie un scalaire repr\u00e9sentant le co\u00fbt\n", " \"\"\"\n", " \n", " # Initialise l'accumulateur\n", " accum = 0\n", " \n", " # \u00c9crivez votre code ici\n", " \n", " return accum\n", "\n", "utilitaires.Tests().test_cout(cout)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "(bonus) Calcul *rapide* du co\u00fbt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'astuce pour calculer le co\u00fbt $J$ rapidement est essentiellement la m\u00eame que celle pour calculer $z_{n,k}$ rapidement. Calculez la diff\u00e9rence d'une seule op\u00e9ration \u00e0 l'aide du broadcasting. Une fois la distance calcul\u00e9, la matrice des distances et la matrice $Z$ auront les m\u00eames dimensions. Il ne reste donc qu'\u00e0 faire une multiplication terme \u00e0 terme et sommer tous les \u00e9l\u00e9ments." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def cout_rapide(mu, data, z):\n", " \"\"\"\n", " Calcule *rapidement* le co\u00fbt \u00e0 partir des param\u00e8tres et des variables latentes.\n", " \n", " Arguments\n", " ---------\n", " mu: ndarray\n", " matrice de dimension (k, d)\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " z: ndarray\n", " matrice de dimension (n, k)\n", " \n", " Returns\n", " -------\n", " float\n", " Renvoie un scalaire repr\u00e9sentant le co\u00fbt\n", " \"\"\"\n", " \n", " # \u00c9crivez votre code ici\n", " \n", " return \n", "\n", "utilitaires.Tests().test_cout(cout_rapide)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous devriez voir \u00e0 nouveau une am\u00e9lioration de l'ordre de 100x." ] }, { "cell_type": "code", "collapsed": false, "input": [ "utilitaires.Tests().time_cout(init_centroids_naif, z, cout, cout_rapide)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Compl\u00e9ter la classe `Kmeans`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous devez maintenant ins\u00e9rer les fonctions impl\u00e9ment\u00e9 pr\u00e9c\u00e9demment dans la classe `Kmeans` d\u00e9j\u00e0 \u00e9crite en bonne partie pour vous. \n", "\n", "**Tout le code \u00e0 \u00e9crire se trouve dans la m\u00e9thode `train`**.\n", "\n", "Vous devez:\n", "\n", "1. Initialiser les param\u00e8tres $\\mu_k$\n", "2. Pour chaque it\u00e9ration\n", " 3. Inf\u00e9rer la valeur de $z_{n,k}$\n", " 4. Mettre \u00e0 jour $\\mu_k$ \u00e0 partir de $z_{n,k}$\n", "\n", "Si vous avez impl\u00e9ment\u00e9 les versions rapides des fonctions, **vous devez changez les m\u00e9thodes utilis\u00e9es dans `Kmeans.compute_z()`, `Kmeans.compute_cost()`.** Autrement, vous aurez un mod\u00e8le inutilement lent." ] }, { "cell_type": "code", "collapsed": false, "input": [ "class Kmeans:\n", " \"\"\"\n", " Mod\u00e8le K-means\n", " \n", " Attributes\n", " ---------\n", " mu: ndarray\n", " matrice de dimension (k, d) repr\u00e9sentant les param\u00e8tres\n", " k: int\n", " le nombre de centro\u00efde\n", " rng: numpy.random.RandomState\n", " un objet pour \u00e9chantillonner les valeurs initiales des param\u00e8tres\n", " \n", " Methods\n", " -------\n", " compute_z(data)\n", " Inf\u00e8re la valeur des variables latentes\n", " \"\"\"\n", " def __init__(self, k, rng=None):\n", " \"\"\"\n", " Constructeur de la classe.\n", " \n", " Prend les param\u00e8tres donn\u00e9es \u00e0 la constuction de la classe et initialise ses attribues.\n", " \"\"\"\n", " \n", " if rng is None:\n", " rng = np.random.RandomState(np.random.random_integers(4294967295))\n", " \n", " self.rng = rng\n", " self.k = k\n", " \n", " def compute_z(self, data):\n", " \"\"\"\n", " Inf\u00e8re la valeur des variables latentes \u00e0 partir de mu\n", " \n", " Arguments\n", " ---------\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " \n", " Returns\n", " -------\n", " ndarray\n", " matrice de dimension (n, k) repr\u00e9sentant les variables latentes\n", " \"\"\"\n", " \n", " return z_rapide(data, self.mu)\n", " \n", " def compute_cost(self, data):\n", " \"\"\"\n", " Calcule le co\u00fbt \u00e0 partir des param\u00e8tres et des variables latentes.\n", " \n", " Arguments\n", " ---------\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " \n", " Returns\n", " -------\n", " float\n", " Renvoie un scalaire repr\u00e9sentant le co\u00fbt\n", " \"\"\"\n", " \n", " return cout_rapide(self.mu, data, self.compute_z(data))\n", " \n", " def train(self, train_data, num_iter, monitor_per_iter=1, patience=0):\n", " \"\"\"\n", " Entraine le mod\u00e8le d'apprentissage\n", " \n", " Prend en entr\u00e9e une matrice de donn\u00e9es et entra\u00eene le mod\u00e8le. D'autre param\u00e8tres peuvent \u00eatre d\u00e9fini ici \n", " tel que le nombre d'iteration d'entra\u00eenement par exemple.\n", " \n", " Parameters\n", " ----------\n", " train_data : array\n", " matrice de dimension (n,d) o\u00f9 n est le nombre d'exemples et d le nombre de dimensions\n", " num_iter: int\n", " le nombre d'it\u00e9ration sur l'ensemble d'entra\u00eenement\n", " monitor_per_iter: int, default=1\n", " nombre d'it\u00e9ration entre chaque affichage des graphiques\n", " patience: int, default=0\n", " la patience pour l'initialisation des param\u00e8tres\n", " \"\"\"\n", " \n", " # Vous verrez plus tard pourquoi il y a une variable patience ici\n", " # contentez vous d'ajouter la fonction pour initialiser les centro\u00efdes avec les bons arguments\n", " # Pour donner en argument le mod\u00e8le, on envoie self dans la fonction init_centroids_naif\n", " # init_centroids_naif(self) signifie init_centroids_naif(mon model)\n", " if patience <= 0:\n", " # \u00e9crire la fonction d'initialisation ici.\n", " else:\n", " # \u00e9crire la fonction d'initialisation stable ici. (avant-derni\u00e8re section de la d\u00e9mo)\n", " \n", " if any(self.compute_z(train_data).sum(0)==0):\n", " raise RuntimeError((\"Le mod\u00e8le n'a pas r\u00e9ussie \u00e0 initialiser %d centro\u00efdes \"\n", " \"valide apr\u00e8s %d essaies\") % (self.k, patience+1))\n", " \n", " # On calcule le co\u00fbt avant les it\u00e9rations\n", " self.costs = [self.compute_cost(train_data)]\n", " self.iterations = [0]\n", " \n", " for i in xrange(1, num_iter+1):\n", " \n", " # Pour chaque it\u00e9ration de EM, on commence par inf\u00e9rer la valeur de Z\n", " # z = ?\n", " \n", " if monitor_per_iter>0 and i % monitor_per_iter == 0:\n", " utilitaires.plot_costs_and_clusterings(i, self.iterations, self.costs,\n", " self.mu, z, train_data, u\"Esp\u00e9rance\")\n", " \n", " # On conserve l'ancienne valeur de mu pour pouvoir dessiner les fl\u00e8ches sur\n", " # le graphique\n", " dmu = self.mu\n", " \n", " # La deuxi\u00e8me phase de EM est la mise \u00e0 jour des param\u00e8tres sachant les variables latentes z\n", " # Ajouter votre fonction ici\n", " \n", " # On calcule le co\u00fbt maintenant que les param\u00e8tres sont mis \u00e0 jour\n", " self.costs.append(self.compute_cost(train_data))\n", " self.iterations.append(i)\n", " \n", " # On affiche le graphique pour chaque it\u00e9ration % monitor_per_iter ==0\n", " if monitor_per_iter>0 and i % monitor_per_iter == 0:\n", " \n", " utilitaires.plot_costs_and_clusterings(i, self.iterations, self.costs,\n", " self.mu, z, train_data, \"Maximisation\", dmu=dmu)\n", " \n", " # Oh! :( C'est des choses qui arrivent, \u00e7a ne veut pas n\u00e9cessairement \n", " # dire que votre code est mauvais.\n", " if any(self.compute_z(train_data).sum(0)==0):\n", " raise RuntimeError(\"Oh non! Un centro\u00efde est mort! :(\")" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Vous pouvez tester votre mod\u00e8le en ex\u00e9cutant la cellule suivante. Les donn\u00e9es sont g\u00e9n\u00e9r\u00e9es au hasard et changeront donc d'une ex\u00e9cution \u00e0 une autre. Les g\u00e9n\u00e9rateurs de nombres al\u00e9atoires peuvent avoir un comportement d\u00e9terministe si on leur donne un germe (seed) de d\u00e9part. Dans ce cas ci, on g\u00e9n\u00e9re au hasard un germe et l'affiche pendant l'ex\u00e9cution. Si \u00e0 un moment donn\u00e9 vous souhaitez travailler avec les m\u00eames donn\u00e9es ou avec la m\u00eame initialisation du mod\u00e8le, prenez en note le germe correspondant et remplacez la variable `germe` \u00e0 la ligne \n", "\n", "```python\n", "X = utilitaires.generate_data(K,N=200, rng=np.random.RandomState(germe))\n", "```\n", "\n", "pour garder les donn\u00e9es comme tel. Ou \u00e0 la ligne \n", "\n", "```python\n", "kmeans = Kmeans(K, rng=np.random.RandomState(germe))\n", "```\n", "\n", "pour garder la m\u00eame initialisation du mod\u00e8le." ] }, { "cell_type": "code", "collapsed": false, "input": [ "K = 2\n", "\n", "germe = np.random.random_integers(4294967295)\n", "print \"Germe courrant des donn\u00e9es : %d\" % germe\n", "X = utilitaires.generate_data(K,N=200, rng=np.random.RandomState(germe))\n", "\n", "germe = np.random.random_integers(4294967295)\n", "print \"Germe courrant du mod\u00e8le : %d \\n\\n\\n\" % germe\n", "kmeans = Kmeans(K, rng=np.random.RandomState(germe))\n", "kmeans.train(X, num_iter=5, monitor_per_iter=1)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\u00c7a fonctionne bien normalement avec K=2, essayez maintenant avec K=5. Lancez plusieurs exp\u00e9rience, vous finirez par avoir un probl\u00e8me. Un centro\u00efd est mort! C'est des choses qui arrivent, repose en paix petit centro\u00efde. Mais pourquoi est-ce qu'il est mort? Parce que lors de la premi\u00e8re inf\u00e9rence de $z_{n,k}$, **aucun** exemple n'a \u00e9t\u00e9 assign\u00e9 \u00e0 ce centro\u00efde. Et puisque les centro\u00efdes sont des \u00eatres tr\u00e8s sociaux, et bien il est mort d'isolement :(. De mani\u00e8re plus formelle, lorsqu'on calcul $\\mu_k$, aucun \u00e9l\u00e9ment n'est somm\u00e9 pour ce centro\u00efde, mais surtout, on le divise par 0! La moyenne devient alors nan (Not a number), et si on d\u00e9sire continuer l'all\u00e9gorie, il est expuls\u00e9 vers les cieux." ] }, { "cell_type": "code", "collapsed": false, "input": [ "K = 5\n", "\n", "germe = np.random.random_integers(4294967295)\n", "print \"Germe courrant des donn\u00e9es : %d\" % germe\n", "X = utilitaires.generate_data(K,N=200, rng=np.random.RandomState(germe))\n", "\n", "germe = np.random.random_integers(4294967295)\n", "print \"Germe courrant du mod\u00e8le : %d \\n\\n\\n\" % germe\n", "kmeans = Kmeans(K, rng=np.random.RandomState(germe))\n", "kmeans.train(X, num_iter=5, monitor_per_iter=1)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Stabiliser l'initialisation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour s'assurer qu'aucun centro\u00efde ne meurt, on peut tester que pour une initialisation donn\u00e9e, tous les centro\u00efdes ont au moins un point assign\u00e9. Si ce n'est pas le cas, on g\u00e9n\u00e8re un nouveau $\\mu_j$ au hasard. \n", "\n", "Une autre fa\u00e7on est d'initialiser les $\\mu_j$ \u00e0 partir des donn\u00e9es au hasard. Disons qu'on pige l'index $50$ au hasard pour le premier centro\u00efde, alors $\\mu_1 = x_{50}$. Et ainsi de suite pour tous les $\\mu_j$.\n", "\n", "Vous pouvez choisir laquelle des deux vous pr\u00e9f\u00e9rez impl\u00e9menter. Si vous choisissez la deuxi\u00e8me version, veilliez bien \u00e0 changer les arguments de la m\u00e9thode `train` de mani\u00e8re \u00e0 pouvoir choisir la technique na\u00efve d'initialisation ou la plus stable. \n", "\n", "Pour la premi\u00e8re technique, l'argument `patience` repr\u00e9sente combien de g\u00e9n\u00e9ration sera support\u00e9, au-del\u00e0 de quoi la fonction s'arr\u00eatera et l'entra\u00eenement lancera l'annonce du d\u00e9c\u00e8s d'un brave centro\u00efde." ] }, { "cell_type": "code", "collapsed": false, "input": [ "def init_centroids_patience(model, data, patience):\n", " \"\"\"\n", " Initialise de mani\u00e8re *stable* les param\u00e8tres mu du mod\u00e8le.\n", " \n", " Arguments\n", " ---------\n", " model: objet Kmeans\n", " une instance de la classe Kmeans \n", " le nombre de centro\u00efde est donn\u00e9 par model.k\n", " les param\u00e8tres sont sous model.mu\n", " les variables latentes sont g\u00e9n\u00e9r\u00e9es avec model.compute_z(data)\n", " data: ndarray\n", " matrice de dimension (n, d)\n", " patience: int\n", " nombre d'essais pour g\u00e9n\u00e9rer des param\u00e8tres de d\u00e9part\n", " \n", " Notes\n", " -----\n", " La fonction ne renvoie rien\n", " \"\"\"\n", " # initialisation de d\u00e9part\n", " # model.mu = ?\n", " \n", " # bouclez tant qu'il y a un centro\u00efde sans assignation ou que la patience n'est pas d\u00e9pass\u00e9e" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Testez avec votre nouvelle version de l'initialisation. Veilliez \u00e0 bien d\u00e9finir l'argument de la m\u00e9thode `train` pour choisir la nouvelle initialisation. \n", "\n", "On a donn\u00e9 la valeur `monitor_per_iter=6` \u00e0 la m\u00e9thode `train` afin de ne montrer que l'\u00e9tat final de l'entra\u00eenement." ] }, { "cell_type": "code", "collapsed": false, "input": [ "K = 5\n", "\n", "X = utilitaires.generate_data(K,N=200)\n", "\n", "germe = np.random.random_integers(4294967295)\n", "print \"Germe courrant : %d \\n\\n\\n\" % germe\n", "kmeans = Kmeans(K, rng=np.random.RandomState(germe))\n", "kmeans.train(X, num_iter=6, monitor_per_iter=6, patience=10)" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Varier les initialisations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finalement, en plus de pouvoir mourrir, tous les centro\u00efdes ne naissent pas \u00e9gaux. Vous avez sans doutes d\u00e9j\u00e0 remarqu\u00e9 qu'\u00e0 certains entrainements le k-means reste pris dans un minimum local. Il est commun d'entra\u00eener plusieurs k-means avec diff\u00e9rentes initialisations sur un m\u00eame ensemble afin de pouvoir s\u00e9lectionner le meilleur. On ne parle pas de diff\u00e9rentes techniques d'initialisation, mais simplement des initialisations diff\u00e9rentes au hasard. \n", "\n", "Entrainez 10 mod\u00e8les diff\u00e9rents (ou plus, \u00e0 votre guise) et enregistrez les mod\u00e8les ainsi que leur co\u00fbt final sur l'ensemble d'entra\u00eenement. Les derniers \u00e9tats du pire et du meilleur mod\u00e8le seront affich\u00e9s automatiquement \u00e0 la fin." ] }, { "cell_type": "code", "collapsed": false, "input": [ "NUM_ITER = 6\n", "\n", "X = utilitaires.generate_data(5, N=200, rng=np.random.RandomState(3537681316))\n", "\n", "modeles = []\n", "couts = []\n", "for i in range(10): # ou plus, \u00e0 votre guise.\n", " # cr\u00e9ez un nouveau Kmeans\n", " # entra\u00eenez le\n", " # calculez le cout et ajouter le cout et le mod\u00e8le aux listes couts et modeles\n", "\n", "meilleur_modele = modeles[np.argmin(couts)]\n", "pire_modele = modeles[np.argmax(couts)]\n", "\n", "for nom_du_modele, modele in [(u\"Pire mod\u00e8le\", pire_modele), (u\"Meilleur mod\u00e8le\", meilleur_modele)]:\n", " oz = modele.compute_z(X)\n", " utilitaires.plot_costs_and_clusterings(NUM_ITER, modele.iterations, modele.costs,\n", " modele.mu, oz, X, u\"\u00c9tat final - %s\" % nom_du_modele)" ], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }