KMediods_Scratch_VN.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "KMediods-Scratch-VN",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "k8ZhLK1QWX3q",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 384
        },
        "outputId": "2c794e33-3f82-441f-9ecb-a5bae87d5553"
      },
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "#a={'F1':[1.5,2,1.6,1.2,1.5],'F2':[1.7,1.9,1.8,1.5,1]}\n",
        "a={'F1':[10,15,50,80,10,90],'F2':[20,18,80,80,6,100]}\n",
        "df=pd.DataFrame(a)\n",
        "print(df.head())\n",
        "\n",
        "\n",
        "plt.scatter(df['F1'],df['F2'])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "   F1  F2\n",
            "0  10  20\n",
            "1  15  18\n",
            "2  50  80\n",
            "3  80  80\n",
            "4  10   6\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<matplotlib.collections.PathCollection at 0x7f8bd4f24e80>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 1
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAQb0lEQVR4nO3dbYxc5XnG8f9d20kW0mYxbC17TWpXoEUICiYrSmQapTitIY2CZaUpUdpaiNZfUANp5NRu1UZ8gshRCP2CZIUkTkQJKXEXRKo41CZqGqlEaxZig9lCefVg8KZhoUpWiTF3P5zjdL0sL/Pindln/z9pNXOeMzPn0pzja2eeOeONzESSVJZf63YASVLnWe6SVCDLXZIKZLlLUoEsd0kq0OJuBwA444wzctWqVd2OIUnzyr59+36SmQOzreuJcl+1ahWjo6PdjiFJ80pEPPNG65yWkaQCWe6SVCDLXZIKZLlLUoEsd0kq0FuWe0R8JSKORMSBaWNLI+K+iHi8vjytHo+I+MeIeCIifhwRF53M8JI0X42MNVh7015Wb/0Oa2/ay8hYo6OP/3ZeuX8NuHzG2FZgT2aeDeyplwGuAM6ufzYDt3YmpiSVY2SswbZd+2lMTpFAY3KKbbv2d7Tg37LcM/PfgZ/OGL4S2Flf3wlsmDb+9az8J9AfEcs7FVaSSrB99zhTR4+dMDZ19Bjbd493bButzrkvy8zD9fUXgGX19UHguWm3O1SPvU5EbI6I0YgYnZiYaDGGJM0/z09ONTXeirY/UM3qr300/Rc/MnNHZg5n5vDAwKzfnpWkIq3o72tqvBWtlvuLx6db6ssj9XgDOHPa7VbWY5Kk2pb1Q/QtWXTCWN+SRWxZP9SxbbRa7vcAm+rrm4C7p43/eX3WzCXAy9OmbyRJwIY1g9y48XwG+/sIYLC/jxs3ns+GNbPOYrfkLf/jsIi4A/ggcEZEHAI+B9wEfCsirgGeAT5e3/xfgQ8DTwA/B67uWFJJKsiGNYMdLfOZ3rLcM/MTb7Bq3Sy3TeDadkNJktrjN1QlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAi9u5c0R8GvgLIIH9wNXAcuCbwOnAPuDPMvOXbeaU5tTIWIPtu8d5fnKKFf19bFk/xIY1g92OpRYs1H3Z8iv3iBgEPgUMZ+Z5wCLgKuDzwM2ZeRbwEnBNJ4JKc2VkrMG2XftpTE6RQGNyim279jMy1uh2NDVpIe/LdqdlFgN9EbEYOAU4DFwG3FWv3wlsaHMb0pzavnucqaPHThibOnqM7bvHu5RIrVrI+7Llcs/MBvAF4FmqUn+ZahpmMjNfrW92CJj1/U9EbI6I0YgYnZiYaDWG1HHPT041Na7etZD3ZTvTMqcBVwKrgRXAqcDlb/f+mbkjM4czc3hgYKDVGFLHrejva2pcvWsh78t2pmU+BDyVmROZeRTYBawF+utpGoCVQPmTWyrKlvVD9C1ZdMJY35JFbFk/1KVEatVC3pftlPuzwCURcUpEBLAOeBS4H/hYfZtNwN3tRZTm1oY1g9y48XwG+/sIYLC/jxs3nr8gzrAozULel5GZrd854gbgT4BXgTGq0yIHqU6FXFqP/Wlm/uLNHmd4eDhHR0dbziFJC1FE7MvM4dnWtXWee2Z+DvjcjOEngYvbeVxJUnv8hqokFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBWorXKPiP6IuCsiHouIgxHx/ohYGhH3RcTj9eVpnQorSXp72n3lfgvw3cw8B7gAOAhsBfZk5tnAnnpZkjSHWi73iHgP8AHgNoDM/GVmTgJXAjvrm+0ENrQbUpLUnHZeua8GJoCvRsRYRHw5Ik4FlmXm4fo2LwDLZrtzRGyOiNGIGJ2YmGgjhiRppnbKfTFwEXBrZq4BfsaMKZjMTCBnu3Nm7sjM4cwcHhgYaCOGJGmmdsr9EHAoMx+ol++iKvsXI2I5QH15pL2IkqRmtVzumfkC8FxEDNVD64BHgXuATfXYJuDuthJKkpq2uM37/xVwe0S8A3gSuJrqF8a3IuIa4Bng421uQ5LUpLbKPTMfAoZnWbWunceVJLXHb6hKUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KB2i73iFgUEWMRcW+9vDoiHoiIJyLizoh4R/sxJUnN6MQr9+uAg9OWPw/cnJlnAS8B13RgG5KkJrRV7hGxEvgj4Mv1cgCXAXfVN9kJbGhnG5Kk5rX7yv1LwGeB1+rl04HJzHy1Xj4EDM52x4jYHBGjETE6MTHRZgxJ0nQtl3tEfAQ4kpn7Wrl/Zu7IzOHMHB4YGGg1hiRpFovbuO9a4KMR8WHgXcBvALcA/RGxuH71vhJotB9TktSMll+5Z+a2zFyZmauAq4C9mflJ4H7gY/XNNgF3t51SktSUk3Ge+98Afx0RT1DNwd92ErYhSXoT7UzL/Epmfh/4fn39SeDiTjyuJKk1fkNVkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKtLjVO0bEmcDXgWVAAjsy85aIWArcCawCngY+npkvtR/1RCNjDbbvHuf5ySlW9PexZf0QG9YMdnozkjQvtfPK/VXgM5l5LnAJcG1EnAtsBfZk5tnAnnq5o0bGGmzbtZ/G5BQJNCan2LZrPyNjjU5vSpLmpZbLPTMPZ+aD9fX/BQ4Cg8CVwM76ZjuBDe2GnGn77nGmjh47YWzq6DG27x7v9KYkaV7qyJx7RKwC1gAPAMsy83C96gWqaZvZ7rM5IkYjYnRiYqKp7T0/OdXUuCQtNG2Xe0S8G/g2cH1mvjJ9XWYm1Xz862TmjswczszhgYGBpra5or+vqXFJWmjaKveIWEJV7Ldn5q56+MWIWF6vXw4caS/i621ZP0TfkkUnjPUtWcSW9UMtPd7IWIO1N+1l9dbvsPamvc7dS5r3Wi73iAjgNuBgZn5x2qp7gE319U3A3a3Hm92GNYPcuPF8Bvv7CGCwv48bN57f0tkyfjgrqURRzZy0cMeIS4EfAPuB1+rhv6Wad/8W8F7gGapTIX/6Zo81PDyco6OjLeVo19qb9tKYZa5+sL+PH269rAuJJOntiYh9mTk827qWz3PPzP8A4g1Wr2v1ceeaH85KKtGC/4aqH85KKtGCL/dOfzgrSb2g5WmZUhz/ENb/ykBSSRZ8uUNV8Ja5pJIs+GkZSSqR5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKtC8/UtMI2MN/zSeJL2BeVnuI2MNtu3az9TRYwA0JqfYtms/gAUvSczTaZntu8d/VezHTR09xvbd411KJEm9ZV6W+/OTU02NS9JCMy/LfUV/X1PjkrTQzMty37J+iL4li04Y61uyiC3rh7qUSJJ6y7z8QPX4h6aeLSNJs5uX5Q5VwVvmkjS7eTktI0l6c5a7JBXIcpekAlnuklQgy12SChSZ2e0MRMQE8EyLdz8D+EkH43SKuZpjrub1ajZzNaedXL+VmQOzreiJcm9HRIxm5nC3c8xkruaYq3m9ms1czTlZuZyWkaQCWe6SVKASyn1HtwO8AXM1x1zN69Vs5mrOSck17+fcJUmvV8Ird0nSDJa7JBVoXpV7RHwlIo5ExIFpY0sj4r6IeLy+PK0Luc6MiPsj4tGIeCQiruuFbBHxroj4UUQ8XOe6oR5fHREPRMQTEXFnRLxjLnNNy7coIsYi4t5eyRURT0fE/oh4KCJG67FeOMb6I+KuiHgsIg5GxPu7nSsihurn6fjPKxFxfbdz1dk+XR/zByLijvrfQi8cX9fVmR6JiOvrsZPyfM2rcge+Blw+Y2wrsCczzwb21Mtz7VXgM5l5LnAJcG1EnNsD2X4BXJaZFwAXApdHxCXA54GbM/Ms4CXgmjnOddx1wMFpy72S6/cz88Jp5x53ez8C3AJ8NzPPAS6get66miszx+vn6ULgfcDPgX/pdq6IGAQ+BQxn5nnAIuAqunx8RcR5wF8CF1Ptw49ExFmcrOcrM+fVD7AKODBteRxYXl9fDoz3QMa7gT/opWzAKcCDwO9SfRtucT3+fmB3F/KsrA/ky4B7geiRXE8DZ8wY6+p+BN4DPEV9AkSv5JqR5Q+BH/ZCLmAQeA5YSvU3K+4F1nf7+AL+GLht2vLfA589Wc/XfHvlPptlmXm4vv4CsKybYSJiFbAGeIAeyFZPfTwEHAHuA/4bmMzMV+ubHKL6xzDXvkR1YL9WL5/eI7kS+F5E7IuIzfVYt/fjamAC+Go9jfXliDi1B3JNdxVwR329q7kyswF8AXgWOAy8DOyj+8fXAeD3IuL0iDgF+DBwJifp+Sqh3H8lq199XTu3MyLeDXwbuD4zX5m+rlvZMvNYVm+bV1K9HTxnrjPMFBEfAY5k5r5uZ5nFpZl5EXAF1fTaB6av7NJ+XAxcBNyamWuAnzHjrXs3j/167vqjwD/PXNeNXPWc9ZVUvxRXAKfy+uncOZeZB6mmhr4HfBd4CDg24zYde75KKPcXI2I5QH15pBshImIJVbHfnpm7eikbQGZOAvdTvR3tj4jjf2JxJdCY4zhrgY9GxNPAN6mmZm7pgVzHX/WRmUeo5o8vpvv78RBwKDMfqJfvoir7buc67grgwcx8sV7udq4PAU9l5kRmHgV2UR1zvXB83ZaZ78vMD1DN+/8XJ+n5KqHc7wE21dc3Uc13z6mICOA24GBmfrFXskXEQET019f7qD4HOEhV8h/rVq7M3JaZKzNzFdXb+b2Z+clu54qIUyPi149fp5pHPkCX92NmvgA8FxFD9dA64NFu55rmE/z/lAx0P9ezwCURcUr9b/P489XV4wsgIn6zvnwvsBH4J07W8zWXHyh04AOJO6jm0I5SvZq5hmqudg/wOPBvwNIu5LqU6q3Uj6neaj1ENZ/W1WzA7wBjda4DwD/U478N/Ah4guqt9Du7uE8/CNzbC7nq7T9c/zwC/F093gvH2IXAaL0vR4DTeiTXqcD/AO+ZNtYLuW4AHquP+28A7+z28VXn+gHVL5qHgXUn8/nyvx+QpAKVMC0jSZrBcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkF+j8TxQidlkmO1gAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kESMkRtbZnPe"
      },
      "source": [
        "from collections import defaultdict \n",
        "distances_dict=defaultdict()\n",
        "\n",
        "distances=np.zeros([2,6])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yZMQm_L7kxzS"
      },
      "source": [
        "for q in range(len(df)):\n",
        "for i in range(len(df)-1):\n",
        "  medoids=[]\n",
        "  medoids.append(list(df.iloc[i]))\n",
        "  medoids.append(list(df.iloc[i+1]))\n",
        "  for j in range(len(medoids)):\n",
        "    for k in range(len(df)):\n",
        "      dist=abs(np.array(df.iloc[k,0])- np.array(medoids[j][1]))  +  abs(np.array(df.iloc[k,1])-np.array(medoids[j][1]))\n",
        "      distances[j,k]=dist\n",
        "  cost=0\n",
        "  for v in range(len(df)):\n",
        "    if distances[0,v]<=distances[1,v]:\n",
        "      cost=cost+distances[0,v]\n",
        "    else:\n",
        "      cost=cost+distances[1,v]\n",
        "  distances_dict[cost]=medoids\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GKtS8CzjahZy"
      },
      "source": [
        "for q in range(len(df)):\n",
        "  for i in range(len(df)-1):\n",
        "    medoids=[]\n",
        "    medoids.append(list(df.iloc[q]))\n",
        "    medoids.append(list(df.iloc[i+1]))\n",
        "    for j in range(len(medoids)):\n",
        "      for k in range(len(df)):\n",
        "        dist=abs(np.array(df.iloc[k,0])- np.array(medoids[j][1]))  +  abs(np.array(df.iloc[k,1])-np.array(medoids[j][1]))\n",
        "        distances[j,k]=dist\n",
        "    cost=0\n",
        "    for v in range(len(df)):\n",
        "      if distances[0,v]<=distances[1,v]:\n",
        "        cost=cost+distances[0,v]\n",
        "      else:\n",
        "        cost=cost+distances[1,v]\n",
        "    distances_dict[cost]=medoids\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YKxIR2V6einr",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 312
        },
        "outputId": "7ed833c0-691a-4999-db3c-3a9dc9c48064"
      },
      "source": [
        "print(\"Cost of all possible medoids\\n\")\n",
        "distances_dict"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Cost of all possible medoids\n",
            "\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "defaultdict(None,\n",
              "            {93.0: [[80, 80], [15, 18]],\n",
              "             101.0: [[10, 20], [80, 80]],\n",
              "             103.0: [[10, 6], [80, 80]],\n",
              "             153.0: [[90, 100], [15, 18]],\n",
              "             161.0: [[10, 20], [90, 100]],\n",
              "             163.0: [[90, 100], [10, 6]],\n",
              "             381.0: [[10, 20], [10, 6]],\n",
              "             389.0: [[10, 6], [15, 18]],\n",
              "             393.0: [[10, 20], [15, 18]],\n",
              "             405.0: [[15, 18], [15, 18]],\n",
              "             441.0: [[90, 100], [80, 80]],\n",
              "             461.0: [[80, 80], [80, 80]],\n",
              "             487.0: [[10, 6], [10, 6]],\n",
              "             641.0: [[90, 100], [90, 100]]})"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 65
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QvTgK_8LoPEd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "5b633465-e843-4283-8036-a6d6ee9a8487"
      },
      "source": [
        "medoids=distances_dict[min(distances_dict.keys())]\n",
        "print(\"Medoids with least cost : \",medoids)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Medoids with least cost :  [[80, 80], [15, 18]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "InlU2I_2rERU"
      },
      "source": [
        "for j in range(len(medoids)):\n",
        "    for k in range(len(df)):\n",
        "      dist=abs(np.array(df.iloc[k,0])- np.array(medoids[j][1]))  +  abs(np.array(df.iloc[k,1])-np.array(medoids[j][1]))\n",
        "      distances[j,k]=dist\n",
        "cluster=[[],[]]\n",
        "for i in range(len(df)):\n",
        "  if distances[0,i]<=distances[1,i]:\n",
        "    cluster[0].append(i)\n",
        "  else:\n",
        "    cluster[1].append(i)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v2etT_TTsUFx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "095c2b95-5c2e-4c8b-c234-4eaa971c01f4"
      },
      "source": [
        "distances"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[130., 127.,  30.,   0., 144.,  30.],\n",
              "       [ 10.,   3.,  94., 124.,  20., 154.]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 59
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qVKgFENmsVkB",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "3583272e-1f3f-4f71-865f-2ffa57905650"
      },
      "source": [
        "print(\"Cluster 1 \",medoids[0],\"  :\",cluster[0])\n",
        "print(\"Cluster 2 \",medoids[1],\"  :\",cluster[1])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Cluster 1  [80, 80]   : [2, 3, 5]\n",
            "Cluster 2  [15, 18]   : [0, 1, 4]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3vBuoOKMtgwe"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}