{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c5b50809-6c85-420c-b68f-2798319f31d0",
   "metadata": {},
   "source": [
    "Le partitionnement en $k$-moyennes est une méthode de partitionnement d'objets en $k$ *clusters* (groupe  en français) de façon à faire des regroupements d'objets *qui se ressemblent* ou qui potentiellement appartiennent à la même catégorie.\n",
    "\n",
    "On suppose que chaque objet est caractérisé par un vecteur de $\\mathrm{R}^d$ comme dans l'algorithme des $k$ plus proches voisins. On a un certain nombre $n$ d'objets que l'on veut répartir en $k$ clusters. Dans l'exemple qui suit $d=2$, $n=12$ et on prendra $k=3$.\n",
    "\n",
    "Etant donné une répartition des objets en clusters $S_1, S_2, \\ldots S_k$, on considère les points moyens $\\mu_1, \\mu_2, \\ldots, \\mu_k$ de ces clusters et on s'intéresse à la quantité, appelée parfois *fonction de coût*:\n",
    "$$\n",
    "C= \\sum_{i=1}^k \\sum_{x \\in S_i} \\Vert x - \\mu_i \\Vert^2\n",
    "$$\n",
    "où $\\Vert \\cdot \\Vert$ désigne la norme euclidienne de $\\mathrm{R}^d$.\n",
    "\n",
    "L'objectif est de trouver le partionnement qui rende cette quantité $C$ minimale. Malheureusement, lorsque le nombre de données est trop grand, il n'est pas possible de chercher tous les partionnements pour trouver le meilleur. Le temps de calcul serait trop long! \n",
    "\n",
    "**Exercice 1**\n",
    "Donner l'ordre de grandeur du nombre de partionnements de $n$ objets en 3 clusters numérotés $0$, $1$, $2$.\n",
    "\n",
    "On obtient en général un partionnement *acceptable* en procédant de la façon suivante.\n",
    "\n",
    "On commence par choisir un ensemble $E_0$ de  $k$ points $\\mu_1, \\mu_2, \\ldots, \\mu_k$ pris, en général, au hasard (ou arbitrairement) dans le jeu de données et on fait un premier partionnement en mettant dans le cluster $i$, les données les plus proches de $\\mu_i$ pour tout $i$ compris entre $1$ et $k$.\n",
    "On calcule les points moyens de chaque cluster, ce qui donne un ensemble de $k$ nouveaux points donnant lieu à un nouveau partionnement du jeu de données en $k$ clusters avec une fonction coût inférieur. \n",
    "A chaque itération du processus, la fonction coût diminue. Donc, après un certain d'itérations, on peut espérer avoir un bon partionnement du jeu de données en $k$ clusters.\n",
    "\n",
    "Comme mentionné plus haut, cette algorithme ne fournit pas obligatoirement le meilleur partionnement en $k$ clusters mais il donne souvent de bons résultats. Le résultat peut d'ailleurs dépendre du choix initial des points $\\mu_1, \\ldots, \\mu_k$.\n",
    "\n",
    "On dispose de 12 objets que l'on veut répartir en trois catégories.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9fa51437-0200-4d56-9427-979324dc32ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "Objets=[[0,0],[1,1],[3,4],[3,6],[4,2],[10,6],\n",
    "        [0,2],[10,7],[8,4],[6,8],[1,0],[9,6]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47d7a2db-d189-4894-9d89-4698c46f9738",
   "metadata": {},
   "source": [
    "On dit qu'une liste d'entiers définit une partition de la liste *Objets* en $k$ clusters lorsqu'elle est de même longueur que la liste *Objets* et contient des entiers compris entre $0$ à~$k-1$.\n",
    "\n",
    "Par exemple, la liste $(0,1,0,0,1,2,2,2,1,1,0,2)$ définit une partition de *Objets* en trois clusters. \n",
    "\n",
    "Le cluster $0$ contient les objets de coordonnées $(0,0)$, $(3,4)$, $(3,6)$, $(1,0)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be63d833-b0e3-455f-94ce-690475b676dd",
   "metadata": {},
   "source": [
    "**Exercice 2**\n",
    "\n",
    "Ecrire une fonction `clusters` qui prend en argument une liste d'objets, une partition de cette liste et un numéro de cluster. Cette fonction renvoie la liste des objets du cluster et les coordonnées du point moyen de ce cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "718217ee-9d25-46b2-9b73-b07524007040",
   "metadata": {},
   "outputs": [],
   "source": [
    "def clusters(Objets,partition,i):\n",
    "    ...\n",
    "    return L,[xm,ym]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c5c25c86-c6d8-4e45-8035-a456a27a78bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([[0, 0], [3, 4], [3, 6], [1, 0]], [1.75, 2.5])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clusters(Objets,[0,1,0,0,1,2,2,2,1,1,0,2],0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "929ff88a-f8b0-474c-b9ea-56c39e8ccd17",
   "metadata": {},
   "source": [
    "**Exercice 3**\n",
    "\n",
    "Ecrire une fonction `affiche_clusters` qui prend en argument des objets et une partition, et qui affiche les objets d'un même cluster de la même couleur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "bf982952-da5f-4194-8896-3b1bb9e3678c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "Couleurs=['blue','green','red','yellow']\n",
    "\n",
    "def affiche_clusters(Objets,partition):\n",
    "    for k in range(len(Objets)):\n",
    "        plt.plot(...)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be02257d-57f7-41d9-bce2-fcacccba82f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "affiche_cluster(Objets,[0,1,0,0,1,2,2,2,1,1,0,2])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff692cb4-e1e7-4418-851a-86ae060d7b11",
   "metadata": {},
   "source": [
    "**Exercice 4**\n",
    "\n",
    "Ecrire une fonction `cout` qui prend en argument des objets et une partition, et qui calcule le coût de la partition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "416ab655-a01b-4ca3-9a42-d9ea1a25f6bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dist2(A,B):\n",
    "    s=0\n",
    "    for i in range(len(A)):\n",
    "        s+=(A[i]-B[i])**2\n",
    "    return s\n",
    "\n",
    "def cout(Objets,partition):\n",
    "    C=0\n",
    "    k=max(partition)+1\n",
    "    ...\n",
    "    return C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "1042926e-dda9-46f7-98f7-5f9e09da0a58",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "174.75"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cout(Objets,[0,1,0,0,1,2,2,2,1,1,0,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0c9699d5-335a-4ab8-9a0c-1991943f50e6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "196.5"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cout(Objets,[0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f1982ce-e015-4678-aa7d-b7084258e0d3",
   "metadata": {},
   "source": [
    "A chaque cluster d'une partition, on associe un point. \n",
    "Si la partition est composée de $k$ clusters,\n",
    "on dispose d'une liste $C$ de $k$ points (représentés par une liste de deux réels) et on associe \n",
    "le point $C[0]$ au cluster $0$, le point $C[1]$ au cluster $1$, etc. \n",
    "\n",
    "Les points $C[0], \\ldots, C[k-1]$ doivent être distincts.\n",
    "\n",
    "Dans l'exercice ci-dessous, on pourra prendre la liste des points $(0,0)$, $(0,1)$, $(0,2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a5b719a-2a44-4314-9c2f-ffa9400e09fb",
   "metadata": {},
   "source": [
    "**Exercice 5**\n",
    "\n",
    "Ecrire une fonction `affichage` qui prend en argument une liste d'objets et une partition de cette liste, et qui relie chaque point d'un même cluster à son point moyen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "cad1c543-756a-431d-8e89-11ee9647ebaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "# plt.plot([x0,x1],[y0,y1]) pour tracer le segment dont les extrémités\n",
    "# sont les points de coordonnées (x0,y0) et (x1,y1)\n",
    "\n",
    "def affichage(Objets, partition):\n",
    "    k=max(partition)+1\n",
    "    ...\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c3f73b9-b827-46a0-bbf8-13987509a6b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "affichage(Objets,[0,1,0,0,1,2,2,2,1,1,0,2])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23bba7c4-98b3-45c4-9e41-4167b8b3ed76",
   "metadata": {},
   "source": [
    "**Exercice 6**\n",
    "\n",
    "Ecrire une fonction `repartition` qui prend en argument deux listes de points `L1` et `L2` qui cherche pour chaque point de `L1` le numéro du point de `L2` le plus proche.\n",
    "\n",
    "La fonction renvoie la liste `D` de ces numéros.\n",
    "\n",
    "Par exemple si `D[2]` vaut $0$ cela signifie que le point numéro $0$ de `L2` est le point de `L2` le plus proche du point numéro $2$ de `L1`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "96b1b420-1e96-40d5-89c3-0b2e5c2286cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def repartition(L1,L2):\n",
    "    n=len(L1)\n",
    "    D=[]\n",
    "    for i in range(n):\n",
    "        ....\n",
    "    return D        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "bf77dd63-64c9-4764-97f7-1f39046a2842",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 0, 0, 2, 0, 1, 0, 2, 0, 1, 0]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "repartition(Objets,[Objets[3],Objets[1],Objets[4]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da125407-adbe-44cc-8121-1f3d1b105a17",
   "metadata": {},
   "source": [
    "**Exercice 7**\n",
    "\n",
    "Ecrire une fonction `kmoyennes` qui prend en paramètre une liste d'objet, une partition de cette liste et un entier $N>0$, et qui réalise $N$ itérations de l'algorithme des $k$ moyennes.\n",
    "\n",
    "Pour les partitions proposées dans les applications numériques, on supposera qu'aucun cluster ne devient vide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ec8b843-5ab4-48b3-99d5-b9761c9a8acd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def kmoyennes(Objets,partition,N):\n",
    "    n=max(partition)+1\n",
    "    for l in range(N):\n",
    "        ....\n",
    "    affichage(Objets,partition)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd977c60-63f8-4b56-94e8-43d3878631f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "kmoyennes(Objets,[0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0],6)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1baf6aaf-5a5e-4f4a-a64a-5b579b2a485b",
   "metadata": {},
   "source": [
    "**Exercice 8**\n",
    "\n",
    "Afficher l'évolution de la fonction coût pour mettre en évidence qu'elle diminue à chaque itération de l'algorithme des $k$ moyennes et qu'elle converge. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "005af541-029a-4ee4-b4a6-3bc1d5bff6f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def kmoyennes2(Objets,partition,N):\n",
    "    Couts=[cout(Objets,partition)]\n",
    "    n=max(partition)+1\n",
    "    for l in range(N):\n",
    "        ...\n",
    "    return Couts        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f653e094-6aa6-40bb-a406-a58c2b8ff9bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "L=kmoyennes2(Objets,[0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0],9)\n",
    "plt.plot(L)"
   ]
  }
 ],
 "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.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}