K_mean_and_related_evaluation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "import numpy as np"
      ],
      "metadata": {
        "id": "xEMvw5lW3eFG"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "CpWzzWopl9de"
      },
      "outputs": [],
      "source": [
        "D= [[3,3],[1,1],[-1,0],[2,2],[-2,2],[-2,-2],[0,-2]]"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "index = len(D)\n",
        "index"
      ],
      "metadata": {
        "id": "0uel4o-amBzg",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "74c94f7f-76e5-4bb9-e301-e4859ac0779e"
      },
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "7"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "cost_similarity = [[0 for i in range(index)] for j in range( index)]\n",
        "cost_similarity"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vYPwQ2y-2sj0",
        "outputId": "e9539882-e124-4f90-e6db-ec8e3857a3e4"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[0, 0, 0, 0, 0, 0, 0],\n",
              " [0, 0, 0, 0, 0, 0, 0],\n",
              " [0, 0, 0, 0, 0, 0, 0],\n",
              " [0, 0, 0, 0, 0, 0, 0],\n",
              " [0, 0, 0, 0, 0, 0, 0],\n",
              " [0, 0, 0, 0, 0, 0, 0],\n",
              " [0, 0, 0, 0, 0, 0, 0]]"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "for i in range(index):\n",
        "  for j in range(index):\n",
        "    dot_product = np.dot(D[i],D[j])\n",
        "    l2Norm =np.linalg.norm(D[i])*np.linalg.norm(D[j])\n",
        "    cost_similarity[i][j] =dot_product/l2Norm"
      ],
      "metadata": {
        "id": "upo3TJe9mFYa"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "cost_similarity"
      ],
      "metadata": {
        "id": "hPgFtrnrm85K",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b8f9ee70-82cf-4263-f69c-a7e256c25c11"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1.0000000000000002,\n",
              "  1.0,\n",
              "  -0.7071067811865476,\n",
              "  1.0,\n",
              "  0.0,\n",
              "  -1.0,\n",
              "  -0.7071067811865476],\n",
              " [1.0,\n",
              "  0.9999999999999998,\n",
              "  -0.7071067811865475,\n",
              "  0.9999999999999998,\n",
              "  0.0,\n",
              "  -0.9999999999999998,\n",
              "  -0.7071067811865475],\n",
              " [-0.7071067811865476,\n",
              "  -0.7071067811865475,\n",
              "  1.0,\n",
              "  -0.7071067811865475,\n",
              "  0.7071067811865475,\n",
              "  0.7071067811865475,\n",
              "  0.0],\n",
              " [1.0,\n",
              "  0.9999999999999998,\n",
              "  -0.7071067811865475,\n",
              "  0.9999999999999998,\n",
              "  0.0,\n",
              "  -0.9999999999999998,\n",
              "  -0.7071067811865475],\n",
              " [0.0,\n",
              "  0.0,\n",
              "  0.7071067811865475,\n",
              "  0.0,\n",
              "  0.9999999999999998,\n",
              "  0.0,\n",
              "  -0.7071067811865475],\n",
              " [-1.0,\n",
              "  -0.9999999999999998,\n",
              "  0.7071067811865475,\n",
              "  -0.9999999999999998,\n",
              "  0.0,\n",
              "  0.9999999999999998,\n",
              "  0.7071067811865475],\n",
              " [-0.7071067811865476,\n",
              "  -0.7071067811865475,\n",
              "  0.0,\n",
              "  -0.7071067811865475,\n",
              "  -0.7071067811865475,\n",
              "  0.7071067811865475,\n",
              "  1.0]]"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from scipy.spatial.distance import pdist, squareform, cdist\n"
      ],
      "metadata": {
        "id": "QYUA77AEABjz"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "dist = pdist(D, 'euclidean')\n",
        "dist"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7lMr_6_2_plh",
        "outputId": "721a77d9-939d-4938-d145-3ae142bfd053"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([2.82842712, 5.        , 1.41421356, 5.09901951, 7.07106781,\n",
              "       5.83095189, 2.23606798, 1.41421356, 3.16227766, 4.24264069,\n",
              "       3.16227766, 3.60555128, 2.23606798, 2.23606798, 2.23606798,\n",
              "       4.        , 5.65685425, 4.47213595, 4.        , 4.47213595,\n",
              "       2.        ])"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "D = np.array(D)"
      ],
      "metadata": {
        "id": "VYSeBi-uCYo0"
      },
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "D"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AI0U4UztChf9",
        "outputId": "cc76423f-9039-4862-fef1-d45de9cf5ea5"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 3,  3],\n",
              "       [ 1,  1],\n",
              "       [-1,  0],\n",
              "       [ 2,  2],\n",
              "       [-2,  2],\n",
              "       [-2, -2],\n",
              "       [ 0, -2]])"
            ]
          },
          "metadata": {},
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def k_mean(centroids, D, max_iter, convergence, metric):\n",
        "  \"\"\"\n",
        "    Calculate the k_mean with-in limited iteration and convergence threadhold.\n",
        "\n",
        "    D: array of data points\n",
        "    centroids: array of cluster centroids\n",
        "    max_iter: max iteration\n",
        "    convergence: threadhold to decide if the centroid converged\n",
        "    metric: e for euclidean, c for cosine similarity\n",
        "    \"\"\"\n",
        "  k = centroids.shape[0]\n",
        "  iteration = 0\n",
        "  while iteration < max_iter:\n",
        "    if metric == \"e\":\n",
        "\n",
        "      distances = cdist(centroids, D, metric='euclidean')\n",
        "    else:\n",
        "\n",
        "      cosine_distances = cdist(centroids, D, metric='cosine')\n",
        "      # Since the cosine distance is 1 - cosine similarity, we can recover the similarities:\n",
        "      distances = 1 - cosine_distances\n",
        "\n",
        "    closest_centroids = np.argmin(distances, axis=0)\n",
        "    clusters = [[] for _ in range(k)]\n",
        "    for point_idx in range(len(D)):\n",
        "      centroid_idx = closest_centroids[point_idx]  # this is the correct centroid index\n",
        "      clusters[centroid_idx].append(D[point_idx])\n",
        "    #update centroid\n",
        "    cluster_means = []\n",
        "\n",
        "    # Re-calculate centroids\n",
        "    new_centroids =[]\n",
        "    empty_clusters = False\n",
        "\n",
        "    for idx, cluster in enumerate(clusters):\n",
        "        if len(cluster) == 0:  # cluster is empty\n",
        "            empty_clusters = True\n",
        "            # One approach to handle empty clusters: reassign to random point from the data\n",
        "            new_centroids.append(D[np.random.choice(D.shape[0]), :])\n",
        "        else:\n",
        "            new_centroids.append(np.mean(cluster, axis=0))\n",
        "\n",
        "    new_centroids = np.array(new_centroids)\n",
        "\n",
        "    # If we reassigned any centroids, we skip the convergence check for this iteration\n",
        "    if not empty_clusters:\n",
        "        differences = np.linalg.norm(new_centroids - centroids, axis=1)\n",
        "        if np.max(differences) < convergence:\n",
        "            print(\"Convergence achieved.\")\n",
        "            break\n",
        "\n",
        "    centroids = new_centroids\n",
        "    iteration += 1\n",
        "\n",
        "\n",
        "  print(\"Iteration: \", iteration)\n",
        "  print(\"Clusters: \\n\", clusters)\n",
        "  print(\"Centroids: \\n\", centroids)\n",
        "  return iteration, clusters, centroids"
      ],
      "metadata": {
        "id": "ZVZ3CgNAACDl"
      },
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def simplified_silhouette(D, clusters, centroids):\n",
        "    \"\"\"\n",
        "    Calculate the simplified silhouette score.\n",
        "\n",
        "    D: array of data points\n",
        "    clusters: list of arrays with data points associated with each cluster\n",
        "    centroids: array of cluster centroids\n",
        "    \"\"\"\n",
        "    all_silhouettes = []\n",
        "\n",
        "    # Iterate through each data point in D to calculate silhouette scores\n",
        "    for point in D:\n",
        "        # Find the cluster to which the point belongs\n",
        "        distances_to_centroids = np.linalg.norm(centroids - point, axis=1)\n",
        "        own_cluster_idx = np.argmin(distances_to_centroids)\n",
        "\n",
        "        # a is the distance from point to its own cluster's centroid\n",
        "        a = distances_to_centroids[own_cluster_idx]\n",
        "\n",
        "        # Calculate b, the average distance of point to the centroids of the other clusters\n",
        "        sum_other_distances = np.sum(distances_to_centroids) - a\n",
        "        # We subtract 1 to exclude the own cluster's centroid from the count\n",
        "        b = sum_other_distances / (len(centroids) - 1)\n",
        "\n",
        "        # Calculate the silhouette score for the current point\n",
        "        silhouette = (b - a) / max(a, b) if max(a, b) > 0 else 0  # handle the edge case to avoid division by zero\n",
        "        all_silhouettes.append(silhouette)\n",
        "\n",
        "    # Sum all silhouette scores\n",
        "    total_silhouette = np.sum(all_silhouettes)\n",
        "    return total_silhouette\n",
        "\n"
      ],
      "metadata": {
        "id": "vA7vIEV55jI3"
      },
      "execution_count": 60,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def calculate_wss(clusters, centroids):\n",
        "    total_wss = 0.0\n",
        "\n",
        "    # For each cluster and its corresponding centroid\n",
        "    for idx, cluster in enumerate(clusters):\n",
        "        if len(cluster) == 0:  # Skip if cluster is empty\n",
        "            continue\n",
        "        # Calculate squared distances from points to the centroid\n",
        "        squared_distances = np.linalg.norm(cluster - centroids[idx], axis=1) ** 2\n",
        "        # Sum up squared distances for this cluster\n",
        "        total_wss += np.sum(squared_distances)\n",
        "\n",
        "    return total_wss\n"
      ],
      "metadata": {
        "id": "LohxHaiwAlj6"
      },
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "centroids = np.array([[3,3],[2,2]])"
      ],
      "metadata": {
        "id": "6J75F8iRCmlO"
      },
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"e\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1cvP6eOmAv0l",
        "outputId": "cf60ae3a-8e7c-4c3b-801f-2ff25c56f46f"
      },
      "execution_count": 58,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Convergence achieved.\n",
            "Iteration:  3\n",
            "Clusters: \n",
            " [[array([3, 3]), array([1, 1]), array([2, 2])], [array([-1,  0]), array([-2,  2]), array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[ 2.    2.  ]\n",
            " [-1.25 -0.5 ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8IoFB1987IXj",
        "outputId": "91c1cef7-9458-4ef4-acb3-5c907def08da"
      },
      "execution_count": 61,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4.679526784405805"
            ]
          },
          "metadata": {},
          "execution_count": 61
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-ruOFEy-AuQo",
        "outputId": "977bbd41-1d5e-49c7-a5bd-b92ed8208e01"
      },
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "17.750000000000004"
            ]
          },
          "metadata": {},
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JzunSSIkLMEZ",
        "outputId": "4880ccc6-9454-4376-d288-0c6c51e86fb1"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration:  100\n",
            "Clusters: \n",
            " [[array([3, 3]), array([1, 1]), array([2, 2])], [array([-1,  0]), array([-2,  2]), array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[ 2.    2.  ]\n",
            " [-1.25 -0.5 ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PlpbLNAQ-6a6",
        "outputId": "76bc19d3-f5ef-49d0-e2ff-730ee9f99b36"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4.679526784405805"
            ]
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MlJXwWAzAwgm",
        "outputId": "cea86595-1983-4a70-a564-9c7658e61602"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "17.750000000000004"
            ]
          },
          "metadata": {},
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "centroids = np.array([[3,3],[2,2],[-2,-2]])"
      ],
      "metadata": {
        "id": "0Jr2R8QLNiv8"
      },
      "execution_count": 21,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"e\")"
      ],
      "metadata": {
        "id": "UDz7sWcgQiu4",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bcecd208-30a0-433b-cabd-c98fceccd0cc"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Convergence achieved.\n",
            "Iteration:  2\n",
            "Clusters: \n",
            " [[array([3, 3]), array([2, 2])], [array([1, 1]), array([-2,  2])], [array([-1,  0]), array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[ 2.5         2.5       ]\n",
            " [-0.5         1.5       ]\n",
            " [-1.         -1.33333333]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uq8_V-8p-81f",
        "outputId": "6f8e14e9-d2c0-4bd7-cd82-6b3424470109"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4.683092063446775"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eygH37D4Axee",
        "outputId": "da3e8ff1-f68e-4619-a95d-3db92f9cbe0d"
      },
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "10.666666666666668"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9zj-VMXsOFlI",
        "outputId": "f10071f6-5b48-42a4-aeac-fe03c4e6d836"
      },
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration:  100\n",
            "Clusters: \n",
            " [[array([-2,  2])], [array([3, 3]), array([1, 1]), array([2, 2])], [array([-1,  0]), array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[-2.          2.        ]\n",
            " [ 2.          2.        ]\n",
            " [-1.         -1.33333333]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RqheAsRz-_PG",
        "outputId": "349e9ae0-a3f3-4db8-b456-27d9acdf48b5"
      },
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.315032070682842"
            ]
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qCL1UetaAyE4",
        "outputId": "490cb686-1316-4b00-fe78-df4b70edb23e"
      },
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "8.666666666666668"
            ]
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "centroids = np.array([[3,3],[2,2],[0,-2],[-2,-2]])"
      ],
      "metadata": {
        "id": "4Ka2NT8h4OxE"
      },
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"e\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "e3p392apORpM",
        "outputId": "35a752a1-5f32-4454-831c-11f86a136b00"
      },
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Convergence achieved.\n",
            "Iteration:  2\n",
            "Clusters: \n",
            " [[array([3, 3]), array([2, 2])], [array([1, 1]), array([-2,  2])], [array([-1,  0]), array([ 0, -2])], [array([-2, -2])]]\n",
            "Centroids: \n",
            " [[ 2.5  2.5]\n",
            " [-0.5  1.5]\n",
            " [-0.5 -1. ]\n",
            " [-2.  -2. ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KHhzaBRQ_Bvh",
        "outputId": "2a34dd2f-c712-4e87-c8df-407f1dcfefc5"
      },
      "execution_count": 30,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.032398567152775"
            ]
          },
          "metadata": {},
          "execution_count": 30
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DajsmekkAzAY",
        "outputId": "2e32845d-9d27-424c-9452-b2e28a7587c3"
      },
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "8.500000000000002"
            ]
          },
          "metadata": {},
          "execution_count": 31
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "g88v_3JF4YfG",
        "outputId": "7e2a0534-442b-4375-ae24-f992b1d04851"
      },
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration:  100\n",
            "Clusters: \n",
            " [[array([-2,  2])], [array([3, 3]), array([1, 1]), array([2, 2])], [array([ 0, -2])], [array([-1,  0]), array([-2, -2])]]\n",
            "Centroids: \n",
            " [[-2.   2. ]\n",
            " [ 2.   2. ]\n",
            " [ 0.  -2. ]\n",
            " [-1.5 -1. ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "M6GJCUZg4ez4",
        "outputId": "bb2b2d6d-14d0-4f7f-9e6b-799afb69029c"
      },
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.601371778656567"
            ]
          },
          "metadata": {},
          "execution_count": 33
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-FntKxRl_D6p",
        "outputId": "33306bb3-7672-4cc3-c21f-d7cae63ef707"
      },
      "execution_count": 34,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6.500000000000002"
            ]
          },
          "metadata": {},
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Try different initialization"
      ],
      "metadata": {
        "id": "7JMRyuSxBjdN"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Try k=2"
      ],
      "metadata": {
        "id": "IVPxsc7mCcKw"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "centroids = np.array([[-10,2.5],[2.5,-1.5]])"
      ],
      "metadata": {
        "id": "UaLIe2IiBiq0"
      },
      "execution_count": 91,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"e\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8c4c2baf-22d2-47ca-b202-1ca97a6e2c38",
        "id": "S6vl0X6vBiq1"
      },
      "execution_count": 92,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Convergence achieved.\n",
            "Iteration:  2\n",
            "Clusters: \n",
            " [[array([-2,  2])], [array([3, 3]), array([1, 1]), array([-1,  0]), array([2, 2]), array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[-2.          2.        ]\n",
            " [ 0.5         0.33333333]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "264abd6e-7e80-4805-995a-90b0f4cafff0",
        "id": "7LeByoR2Biq1"
      },
      "execution_count": 93,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3.383342274686864"
            ]
          },
          "metadata": {},
          "execution_count": 93
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6d3b3b8c-db57-45c7-94b1-534d5a1d063a",
        "id": "OV7NaAwSBiq1"
      },
      "execution_count": 94,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "38.833333333333336"
            ]
          },
          "metadata": {},
          "execution_count": 94
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fe9069f4-bfc1-4ab6-8491-6314213aaf25",
        "id": "u3mDnKQ7CEs4"
      },
      "execution_count": 80,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration:  100\n",
            "Clusters: \n",
            " [[array([3, 3]), array([1, 1]), array([2, 2])], [array([-1,  0]), array([-2,  2]), array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[ 2.    2.  ]\n",
            " [-1.25 -0.5 ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "86a7e1e4-e947-45dd-8cf8-7c6bb7f0b0dc",
        "id": "tQ2yYTyMCEs_"
      },
      "execution_count": 81,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4.679526784405805"
            ]
          },
          "metadata": {},
          "execution_count": 81
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "789262a8-1fb3-492c-cfc2-3627544138d2",
        "id": "4twjmN5lCEs_"
      },
      "execution_count": 82,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "17.750000000000004"
            ]
          },
          "metadata": {},
          "execution_count": 82
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Try k=3"
      ],
      "metadata": {
        "id": "3-eJgusaCXfq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "centroids = np.array([[2,1],[8,3],[-2,-6]])"
      ],
      "metadata": {
        "id": "B8LQSR9jCfzS"
      },
      "execution_count": 42,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"e\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "cf53f153-540f-400c-c68e-d792a700cca2",
        "id": "HZ_UcAQZCfzY"
      },
      "execution_count": 43,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Convergence achieved.\n",
            "Iteration:  2\n",
            "Clusters: \n",
            " [[array([-1,  0]), array([-2,  2])], [array([3, 3]), array([1, 1]), array([2, 2])], [array([-2, -2]), array([ 0, -2])]]\n",
            "Centroids: \n",
            " [[-1.5  1. ]\n",
            " [ 2.   2. ]\n",
            " [-1.  -2. ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1806df1c-ffa9-4996-e1bc-e19cd2a088be",
        "id": "NOplTEDnCfzY"
      },
      "execution_count": 44,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.127393271728211"
            ]
          },
          "metadata": {},
          "execution_count": 44
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a388a985-aa58-42c7-8016-8541fa242215",
        "id": "Pn7xdm_1CfzZ"
      },
      "execution_count": 45,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "8.500000000000002"
            ]
          },
          "metadata": {},
          "execution_count": 45
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f7a73d8d-e254-4877-e559-02d6a7b784fa",
        "id": "Mm6EXmZRCfzZ"
      },
      "execution_count": 46,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration:  100\n",
            "Clusters: \n",
            " [[array([-2,  2])], [array([-1,  0]), array([-2, -2]), array([ 0, -2])], [array([3, 3]), array([1, 1]), array([2, 2])]]\n",
            "Centroids: \n",
            " [[-2.          2.        ]\n",
            " [-1.         -1.33333333]\n",
            " [ 2.          2.        ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "86f8ba30-ed95-4da7-926d-1f904fc23ade",
        "id": "PVWz-TV0CfzZ"
      },
      "execution_count": 47,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.315032070682842"
            ]
          },
          "metadata": {},
          "execution_count": 47
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f578c6d1-01eb-46ff-b414-2c55b91fac12",
        "id": "sYOJnBlCCfzZ"
      },
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "8.666666666666668"
            ]
          },
          "metadata": {},
          "execution_count": 48
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Try k=4"
      ],
      "metadata": {
        "id": "lrtUyDNVDDNA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "centroids = np.array([[2,1],[8,3],[-2,-6],[9,0.5]])"
      ],
      "metadata": {
        "id": "9GmwR-umDDNA"
      },
      "execution_count": 49,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"e\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4130a69b-b75a-4020-f72f-c190340bcb27",
        "id": "x3I4VCXgDDNA"
      },
      "execution_count": 50,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Convergence achieved.\n",
            "Iteration:  2\n",
            "Clusters: \n",
            " [[array([3, 3]), array([1, 1]), array([2, 2])], [array([-2,  2])], [array([-2, -2]), array([ 0, -2])], [array([-1,  0])]]\n",
            "Centroids: \n",
            " [[ 2.  2.]\n",
            " [-2.  2.]\n",
            " [-1. -2.]\n",
            " [-1.  0.]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4d699d60-69ba-416b-dad7-2d04433d8067",
        "id": "N7JA4U-KDDNA"
      },
      "execution_count": 51,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.751124139825558"
            ]
          },
          "metadata": {},
          "execution_count": 51
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8faa69bb-99fa-4634-f495-0a87632fbd61",
        "id": "d8XtozpuDDNA"
      },
      "execution_count": 52,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6.000000000000001"
            ]
          },
          "metadata": {},
          "execution_count": 52
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "iteration, clusters, final_centroid = k_mean(centroids, D, 100, 0.1, \"c\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b68198d7-5b65-4f01-bdf6-1cc758c34d5e",
        "id": "wmvwweuzDDNB"
      },
      "execution_count": 53,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Iteration:  100\n",
            "Clusters: \n",
            " [[array([-2,  2])], [array([3, 3]), array([1, 1]), array([2, 2])], [array([ 0, -2])], [array([-1,  0]), array([-2, -2])]]\n",
            "Centroids: \n",
            " [[-2.   2. ]\n",
            " [ 2.   2. ]\n",
            " [ 0.  -2. ]\n",
            " [-1.5 -1. ]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "simplified_silhouette(D, clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9b19b3eb-ab71-48ca-d199-bfdfda419253",
        "id": "gpZa7_D8DDNB"
      },
      "execution_count": 54,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5.601371778656567"
            ]
          },
          "metadata": {},
          "execution_count": 54
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "calculate_wss(clusters, final_centroid)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5ada3086-7fc5-4c42-9027-409175b051ee",
        "id": "xmCI_mWQDDNB"
      },
      "execution_count": 55,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6.500000000000002"
            ]
          },
          "metadata": {},
          "execution_count": 55
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "InS7eP1tDINn"
      },
      "execution_count": 55,
      "outputs": []
    }
  ]
}