K_Means.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOjCv9LCnjwCoeYs1+lkP/L"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "## IMPORT LIBRARY 📚"
      ],
      "metadata": {
        "id": "VMSNhUaBXmoo"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "yttkrM_CrmmP"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from scipy.spatial import distance"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Hitung Jarak Titik Euclidean 📏"
      ],
      "metadata": {
        "id": "YiI1DxMkXzWe"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def euclidean(x, p):\n",
        "  return distance.euclidean(x, p)"
      ],
      "metadata": {
        "id": "_m8HpaI6xcka"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## K-Means Algorithm For K Cluster ⚡"
      ],
      "metadata": {
        "id": "maSmJ3GXYC6E"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def kmeans(cluster, x, y, px, py, itr):\n",
        "  n = len(x)\n",
        "  d = np.zeros([cluster, n])\n",
        "  g = np.zeros([cluster, n])\n",
        "  nsum = np.zeros(cluster)\n",
        "  xsum = np.zeros(cluster)\n",
        "  ysum = np.zeros(cluster)\n",
        "  compareMin = np.zeros(cluster)\n",
        "  pxnew = np.zeros(cluster)\n",
        "  pynew = np.zeros(cluster)\n",
        "\n",
        "  for i in range(0, n):\n",
        "    # Mencari jarak titik dengan centroid\n",
        "    xy = np.array([x[i], y[i]])\n",
        "    for j in range(0, cluster):\n",
        "      cent = np.array([px[j], py[j]])\n",
        "      d[j][i] = euclidean(xy, cent)\n",
        "      compareMin[j] = d[j][i]\n",
        "    # Clustering berdasarkan nilai paling dekat dengan 0\n",
        "    idxMin = 0\n",
        "    minValue = compareMin[0]\n",
        "    for k in range(0, cluster):\n",
        "      if ( minValue > compareMin[k] ):\n",
        "        idxMin = k\n",
        "        minValue = compareMin[k]\n",
        "    g[idxMin][i] = 1\n",
        "\n",
        "  # Membuat nilai centroid baru\n",
        "  for i in range(0, cluster):\n",
        "    for j in range(0, n):\n",
        "      if (g[i][j] == 1):\n",
        "        nsum[i] = nsum[i] + 1\n",
        "        xsum[i] = xsum[i] + x[j]\n",
        "        ysum[i] = ysum[i] + y[j]\n",
        "  for i in range(0, cluster):\n",
        "    xmean = xsum[i]/nsum[i]\n",
        "    ymean = ysum[i]/nsum[i]\n",
        "    pxnew[i] = xmean\n",
        "    pynew[i] = ymean\n",
        "\n",
        "  # Print Detail Komputasi\n",
        "  print(\"iterasi ke-\", itr)\n",
        "  print('x = ', x)\n",
        "  print('y = ', y)\n",
        "  for i in range(0, cluster):\n",
        "    cent = np.array([px[i], py[i]])\n",
        "    print(\"P ke-\", i+1, ': ', cent)\n",
        "  print(\"\\n\")\n",
        "  \n",
        "  print(\"Hasil distance: \")\n",
        "  print(d)\n",
        "  print(\"\\n\")\n",
        "\n",
        "  print(\"Hasil clustering: \")\n",
        "  print(g)\n",
        "  print(\"\\n\")\n",
        "\n",
        "  for i in range(0, cluster):\n",
        "    print(\"nsum cluster ke-\", i, ': ', nsum[i])\n",
        "    print(\"xsum cluster ke-\", i, ': ', xsum[i])\n",
        "    print(\"ysum cluster ke-\", i, ': ', ysum[i])\n",
        "    print('\\n')\n",
        "\n",
        "  print('pnew:')\n",
        "  for i in range(0, cluster):\n",
        "    cent = np.array([pxnew[i], pynew[i]])\n",
        "    print(\"P new ke-\", i+1, ': ', cent)\n",
        "  print(\"\\n==============================================================\\n\")\n",
        "\n",
        "  # Cek centroid awal dan centroid baru apakah sama\n",
        "  loop = 0\n",
        "  valid = True\n",
        "  while(valid and loop < cluster):\n",
        "    if((px[loop] != pxnew[loop]) or (py[loop] != pynew[loop])):\n",
        "      valid = False\n",
        "    loop = loop + 1\n",
        "  \n",
        "  # Jika nilai centroid baru dan lama berbeda maka lakukan rekursif\n",
        "  if(valid == False):\n",
        "    itr = itr + 1\n",
        "    kmeans(cluster, x, y, pxnew, pynew, itr)\n",
        "\n"
      ],
      "metadata": {
        "id": "_yozJJhdwFaa"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Contoh Eksekusi 2 Cluster ⛏"
      ],
      "metadata": {
        "id": "4d6PXfsiZmtq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "cluster = 2\n",
        "itr = 0\n",
        "x = np.array([0.40, 0.22, 0.35, 0.26, 0.08, 0.45])\n",
        "y = np.array([0.53, 0.38, 0.32, 0.19, 0.41, 0.30])\n",
        "px = np.array([0.4, 0.2])\n",
        "py = np.array([0.3, 0.3])"
      ],
      "metadata": {
        "id": "hf3xf1cOZxEy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "kmeans(cluster, x, y, px, py, itr)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "45Vx-2UAY1AX",
        "outputId": "86f6838a-4f12-4850-b35c-76ffb58e3e98"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "iterasi ke- 0\n",
            "x =  [0.4  0.22 0.35 0.26 0.08 0.45]\n",
            "y =  [0.53 0.38 0.32 0.19 0.41 0.3 ]\n",
            "P ke- 1 :  [0.4 0.3]\n",
            "P ke- 2 :  [0.2 0.3]\n",
            "\n",
            "\n",
            "Hasil distance: \n",
            "[[0.23       0.19697716 0.05385165 0.17804494 0.33837849 0.05      ]\n",
            " [0.30479501 0.08246211 0.15132746 0.12529964 0.16278821 0.25      ]]\n",
            "\n",
            "\n",
            "Hasil clustering: \n",
            "[[1. 0. 1. 0. 0. 1.]\n",
            " [0. 1. 0. 1. 1. 0.]]\n",
            "\n",
            "\n",
            "nsum cluster ke- 0 :  3.0\n",
            "xsum cluster ke- 0 :  1.2\n",
            "ysum cluster ke- 0 :  1.1500000000000001\n",
            "\n",
            "\n",
            "nsum cluster ke- 1 :  3.0\n",
            "xsum cluster ke- 1 :  0.5599999999999999\n",
            "ysum cluster ke- 1 :  0.98\n",
            "\n",
            "\n",
            "pnew:\n",
            "P new ke- 1 :  [0.4        0.38333333]\n",
            "P new ke- 2 :  [0.18666667 0.32666667]\n",
            "\n",
            "==============================================================\n",
            "\n",
            "iterasi ke- 1\n",
            "x =  [0.4  0.22 0.35 0.26 0.08 0.45]\n",
            "y =  [0.53 0.38 0.32 0.19 0.41 0.3 ]\n",
            "P ke- 1 :  [0.4        0.38333333]\n",
            "P ke- 2 :  [0.18666667 0.32666667]\n",
            "\n",
            "\n",
            "Hasil distance: \n",
            "[[0.14666667 0.18003086 0.08069146 0.23870018 0.32110919 0.09718253]\n",
            " [0.29471267 0.06289321 0.16346933 0.15509853 0.1353596  0.2646801 ]]\n",
            "\n",
            "\n",
            "Hasil clustering: \n",
            "[[1. 0. 1. 0. 0. 1.]\n",
            " [0. 1. 0. 1. 1. 0.]]\n",
            "\n",
            "\n",
            "nsum cluster ke- 0 :  3.0\n",
            "xsum cluster ke- 0 :  1.2\n",
            "ysum cluster ke- 0 :  1.1500000000000001\n",
            "\n",
            "\n",
            "nsum cluster ke- 1 :  3.0\n",
            "xsum cluster ke- 1 :  0.5599999999999999\n",
            "ysum cluster ke- 1 :  0.98\n",
            "\n",
            "\n",
            "pnew:\n",
            "P new ke- 1 :  [0.4        0.38333333]\n",
            "P new ke- 2 :  [0.18666667 0.32666667]\n",
            "\n",
            "==============================================================\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Contoh Eksekusi 3 Cluster ⛏"
      ],
      "metadata": {
        "id": "fNRJk5xuaCI4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "cluster = 3\n",
        "itr = 0\n",
        "x = np.array([0.40, 0.22, 0.35, 0.26, 0.08, 0.45])\n",
        "y = np.array([0.53, 0.38, 0.32, 0.19, 0.41, 0.30])\n",
        "px = np.array([0.4, 0.2, 0.3])\n",
        "py = np.array([0.3, 0.3, 0.1])"
      ],
      "metadata": {
        "id": "V0SFWGgbaF-7"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "kmeans(cluster, x, y, px, py, itr)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "k1lxev2EaH0d",
        "outputId": "74a952b8-18f1-45f5-cd62-8f63ddf19b51"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "iterasi ke- 0\n",
            "x =  [0.4  0.22 0.35 0.26 0.08 0.45]\n",
            "y =  [0.53 0.38 0.32 0.19 0.41 0.3 ]\n",
            "P ke- 1 :  [0.4 0.3]\n",
            "P ke- 2 :  [0.2 0.3]\n",
            "P ke- 3 :  [0.3 0.1]\n",
            "\n",
            "\n",
            "Hasil distance: \n",
            "[[0.23       0.19697716 0.05385165 0.17804494 0.33837849 0.05      ]\n",
            " [0.30479501 0.08246211 0.15132746 0.12529964 0.16278821 0.25      ]\n",
            " [0.4414748  0.2912044  0.22561028 0.09848858 0.38013156 0.25      ]]\n",
            "\n",
            "\n",
            "Hasil clustering: \n",
            "[[1. 0. 1. 0. 0. 1.]\n",
            " [0. 1. 0. 0. 1. 0.]\n",
            " [0. 0. 0. 1. 0. 0.]]\n",
            "\n",
            "\n",
            "nsum cluster ke- 0 :  3.0\n",
            "xsum cluster ke- 0 :  1.2\n",
            "ysum cluster ke- 0 :  1.1500000000000001\n",
            "\n",
            "\n",
            "nsum cluster ke- 1 :  2.0\n",
            "xsum cluster ke- 1 :  0.3\n",
            "ysum cluster ke- 1 :  0.79\n",
            "\n",
            "\n",
            "nsum cluster ke- 2 :  1.0\n",
            "xsum cluster ke- 2 :  0.26\n",
            "ysum cluster ke- 2 :  0.19\n",
            "\n",
            "\n",
            "pnew:\n",
            "P new ke- 1 :  [0.4        0.38333333]\n",
            "P new ke- 2 :  [0.15  0.395]\n",
            "P new ke- 3 :  [0.26 0.19]\n",
            "\n",
            "==============================================================\n",
            "\n",
            "iterasi ke- 1\n",
            "x =  [0.4  0.22 0.35 0.26 0.08 0.45]\n",
            "y =  [0.53 0.38 0.32 0.19 0.41 0.3 ]\n",
            "P ke- 1 :  [0.4        0.38333333]\n",
            "P ke- 2 :  [0.15  0.395]\n",
            "P ke- 3 :  [0.26 0.19]\n",
            "\n",
            "\n",
            "Hasil distance: \n",
            "[[0.14666667 0.18003086 0.08069146 0.23870018 0.32110919 0.09718253]\n",
            " [0.28412145 0.07158911 0.21360009 0.2326478  0.07158911 0.31468238]\n",
            " [0.36769553 0.19416488 0.15811388 0.         0.28425341 0.21954498]]\n",
            "\n",
            "\n",
            "Hasil clustering: \n",
            "[[1. 0. 1. 0. 0. 1.]\n",
            " [0. 1. 0. 0. 1. 0.]\n",
            " [0. 0. 0. 1. 0. 0.]]\n",
            "\n",
            "\n",
            "nsum cluster ke- 0 :  3.0\n",
            "xsum cluster ke- 0 :  1.2\n",
            "ysum cluster ke- 0 :  1.1500000000000001\n",
            "\n",
            "\n",
            "nsum cluster ke- 1 :  2.0\n",
            "xsum cluster ke- 1 :  0.3\n",
            "ysum cluster ke- 1 :  0.79\n",
            "\n",
            "\n",
            "nsum cluster ke- 2 :  1.0\n",
            "xsum cluster ke- 2 :  0.26\n",
            "ysum cluster ke- 2 :  0.19\n",
            "\n",
            "\n",
            "pnew:\n",
            "P new ke- 1 :  [0.4        0.38333333]\n",
            "P new ke- 2 :  [0.15  0.395]\n",
            "P new ke- 3 :  [0.26 0.19]\n",
            "\n",
            "==============================================================\n",
            "\n"
          ]
        }
      ]
    }
  ]
}