clustering_kmeans.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DnAHeymRpgW6"
      },
      "source": [
        "**Description**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mnI4YC-Xp1d9"
      },
      "source": [
        "Kmeans est une technique de Machine Learning qui est utilisée pour le regroupement des données (clustering) en groupes (clusters).\n",
        "\n",
        "*Modèle:*\n",
        "\n",
        "Le modèle de Kmeans est l'ensemble des centres des clusters.\n",
        "\n",
        "*Hyperparamètre:*\n",
        "\n",
        "Kmeans a un hyperparamètre appelé K qui représente le nombre de clusters.\n",
        "\n",
        "*Apprentissage:*\n",
        "\n",
        "L'algorithme d'apprentissage de Kmeans est non supervisé : il apprend avec des données non étiquetées. Cet algorithme essaie de trouver les centres des clusters optimales. \n",
        "\n",
        "*Prédiction:*\n",
        "\n",
        "Une fois l'apprentissage est fini, Kmeans permet de prédire pour un point donné à quel groupe il appartient."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6m5N15rERu7c"
      },
      "source": [
        "**Données d'apprentissage**\n",
        "\n",
        "Soit une population ds employés qu'on veut regrouper en clusters.\n",
        "\n",
        "Créer une matrice des données d'employés X (comme étant des points de même dimension).\n",
        "\n",
        "              X=[1100.67 31\n",
        "                 3500.98 58\n",
        "                 1300.58 35\n",
        "                 3100.98 55\n",
        "                 1200.77 32]\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 60,
      "metadata": {
        "id": "BXWkHu53Rujj"
      },
      "outputs": [],
      "source": [
        "# create a matrix X with 5 rows and 2 columns\n",
        "import numpy as np\n",
        "import random\n",
        "from scipy.spatial.distance import euclidean\n",
        "\n",
        "X = np.array([  [1100.67, 31], \n",
        "                [3500.98, 58], \n",
        "                [1300.58, 35], \n",
        "                [3100.98, 55], \n",
        "                [1200.77, 32]])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jf2lQtSHt5ha"
      },
      "source": [
        "**Hyperparamètre**\n",
        "\n",
        "Choisir le nombre des clusters K"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 61,
      "metadata": {
        "id": "QmZLC8Fft-11"
      },
      "outputs": [],
      "source": [
        "k = 2"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BLSrONc9rXLY"
      },
      "source": [
        "**Modèle**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E40gTT0Kpq26"
      },
      "source": [
        "Initialiser les centres des clusters\n",
        "\n",
        "Choisir d'une façon aléatoire K points des données comme centres des clusters.\n",
        "\n",
        "Notes:\n",
        "- Mettre les centres intiales dans une matrice M\n",
        "- Utiliser la fonction random.sample()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 74,
      "metadata": {
        "id": "K8b6XPOTpt_F"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[[1200.77, 32.0], [3500.98, 58.0]]\n"
          ]
        }
      ],
      "source": [
        "#M = np.random.choice(X[:,0], k, replace=False) # choose k rows from X randomly without replacement \n",
        "\n",
        "M = random.sample(X.tolist(), k) # choose k rows from X randomly without replacement\n",
        "\n",
        "print(M)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Other Solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 67,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0, 1, 2, 3, 4]\n"
          ]
        }
      ],
      "source": [
        "NL = X.shape[0]\n",
        "indice_lignes = list(range(0,NL,1))\n",
        "print(indice_lignes)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 68,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[2, 1]\n"
          ]
        }
      ],
      "source": [
        "indice_sampled = random.sample(indice_lignes, k)\n",
        "print(indice_sampled)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2jdvBY3JuDOQ"
      },
      "source": [
        "**Apprentissage**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "huyacmnbunBt"
      },
      "source": [
        "L'algorithme est comme suit :\n",
        "\n",
        "          Pour chaque t de 0 jusqu'à T-1 faire\n",
        "            Pour chaque point p des données faire\n",
        "              Pour chaque centre m_i des clusters M faire\n",
        "                d=distance euclidienne(p,m_i)\n",
        "                Ajouter d dans distances\n",
        "              label de p = argmin(distances) \n",
        "              Ajouter label à labels\n",
        "            Pour chaque centre m_i des clusters faire\n",
        "              c=moyenne arithmétique des points ayant label egale à i"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "deqlYW8ax1CP"
      },
      "source": [
        "Etape 1: Implémenter la fonction predire_label() qui prend un point p et qui retourne le label de cluster auquel p appartient.\n",
        "\n",
        "        Pour chaque centre m_i des clusters M faire\n",
        "            d=distance euclidienne(p,m_i)\n",
        "            Ajouter d dans distances\n",
        "        label de p = argmin(distances)\n",
        "\n",
        "Notes:\n",
        "- Utiliser M comme variable globale.\n",
        "- Utiliser la fonction np.argmin()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 76,
      "metadata": {
        "id": "642iRH6UulwM"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "execution_count": 76,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "def predire_label(p):\n",
        "    distances = []\n",
        "    for m_i in M:\n",
        "        d = euclidean(p, m_i)\n",
        "        distances.append(d)\n",
        "    label = np.argmin(distances)\n",
        "    return label\n",
        "predire_label(X[1])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6pIRrZP_yoaF"
      },
      "source": [
        "Etape 2: Définir la fonction determiner_labels() qui prend un ensemble des points X et qui retourne les labels de tous les points.\n",
        "\n",
        "Cette fonction impélmente la partie de l'algorithme d'apprentissage suivante:\n",
        "\n",
        "          Pour chaque point p des données faire\n",
        "              Pour chaque centre m_i des clusters M faire\n",
        "                d=distance euclidienne(p,m_i)\n",
        "                Ajouter d dans distances\n",
        "              label de p = argmin(distances) \n",
        "              Ajouter label à labels\n",
        "Note:\n",
        "- Un label designe l'indice de groupe auquel apparetient un point.\n",
        "- Utiliser la fonction predire_label()\n",
        "- Utiliser M comme variable globale."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 64,
      "metadata": {
        "id": "Nnzb5g-50p6C"
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "[0, 1]"
            ]
          },
          "execution_count": 64,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "def determiner_lables(M):\n",
        "    labels = []\n",
        "    for p in M:\n",
        "        labels.append(predire_label(p))\n",
        "    return labels\n",
        "\n",
        "determiner_lables(M)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JPXmfBbd0u7F"
      },
      "source": [
        "Etape 3: Définir une fonction mettre_a_jour_centres() qui prend les points et leurs labels d'appartenance aux clusters.\n",
        "\n",
        "          Pour chaque centre m_i des clusters faire\n",
        "              m_i=moyenne arithmétique des points ayant label egale à i\n",
        "\n",
        "Note:\n",
        "- Utiliser np.mean()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 66,
      "metadata": {
        "id": "0gYvX6QK1yM2"
      },
      "outputs": [],
      "source": [
        "def mettre_a_jour_centres():\n",
        "    global M\n",
        "    labels = determiner_lables(M)\n",
        "    for i in range(k):\n",
        "        M[i] = np.mean(X[labels==i], axis=0)\n",
        "    return M"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R11nasb52BqU"
      },
      "source": [
        "Etape 4:\n",
        "\n",
        "Définir la fonction fit() qui implémente tout l'algorithme d'apprentissage. Elle prend l'ensemble des points X et elle met à jour M (les centres des clusters).\n",
        "\n",
        "Notes:\n",
        "- Utiliser M comme une variable globale.\n",
        "- Utiliser les fonctions determiner_labels() et les fonctions mettre_a_jour()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "q3HBBokt4Fo1"
      },
      "outputs": [],
      "source": [
        "#"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tUFCmV-u7jaF"
      },
      "source": [
        "**Prédiction**\n",
        "\n",
        "Définir une fonction predict() qui prend une matrice des points d'employés X. Elle retourne les labels de ces points.\n",
        "\n",
        "Note:\n",
        "- Utiliser la fonction predire_label\n",
        "- Utiliser M comme variable globale."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "EgkuTmPT8GGp"
      },
      "outputs": [],
      "source": [
        "#"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b4qWcMnO8HdF"
      },
      "source": [
        "**Recap**\n",
        "\n",
        "Nous allons définir Kmeans sous la forme d'une classe que vous appelez Kmeans.\n",
        "\n",
        "Elle contient les fonctions suivantes:\n",
        "- un constructeur dans lequel:\n",
        "  - L'hyperparamètre K est considéré comme attribut d'objet. Il permet de l'initialiser.\n",
        "  - Le modèle M (les centres de clusters) est initialisé aléatoirement\n",
        "- la fonction fit() définie ci-dessus\n",
        "- la fonction predict() définie ci-dessus"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "7x7LgAoG8ppV"
      },
      "outputs": [],
      "source": [
        "#"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.10.6 64-bit",
      "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.10.6"
    },
    "vscode": {
      "interpreter": {
        "hash": "9280cfe3a885ab6393e840bb0851a2b8b9319602f57c283749909a607b67fea4"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}