kmeans_fast.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "ceFBFQUIsvSd"
      },
      "outputs": [],
      "source": [
        "import argparse\n",
        "import sys\n",
        "import os\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from matplotlib import transforms\n",
        "from copy import deepcopy"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This K-means implementation is much faster than sklearn version. It uses vectorization... test it yourself."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 176,
      "metadata": {
        "id": "vbLTb5NBlBGF",
        "tags": []
      },
      "outputs": [],
      "source": [
        "class k_means(object):\n",
        "    def __init__(self, data, num_clusters, normalize_data = True, rnd_seed = 42):\n",
        "        self.data = data\n",
        "        self.clusters = np.array([i for i in range(num_clusters)])\n",
        "        if num_clusters > 10:\n",
        "            print(\"This class does not support more than 10 clusters!\")\n",
        "            sys.exit()\n",
        "        if normalize_data:\n",
        "          self.normalize()\n",
        "          print(\"Data normalized: x = (x-x_mean)/x_dev\")\n",
        "\n",
        "        # Draw random data points and make them centroids\n",
        "        np.random.seed(rnd_seed)\n",
        "        self.centroids = self.data[np.array(np.round(len(self.data)*np.random.sample(num_clusters)), np.int)]\n",
        "        print(\"Cluster labels: \")\n",
        "        print(self.clusters)\n",
        "        print(\"Initial centroids: \")\n",
        "        print(self.centroids)\n",
        "\n",
        "        # Define colors for 9 possible classes on map drawing...\n",
        "        self.colors = {1:[25,25,112], 2:[100,149,237], 3:[255,70,0], 4: [255,0,255], \n",
        "                        5:[255,255,0], 6:[0,128,128], 7:[148,0,211], \n",
        "                        8:[255,20,147], 9:[220,20,60], 10:[128,0,0]}\n",
        "\n",
        "    def normalize(self):\n",
        "        for i in range(len(self.data[0,:])):\n",
        "            mean = np.mean(self.data[:,i])\n",
        "            std = np.std(self.data[:,i])\n",
        "            self.data[:,i] = (self.data[:,i] - mean)/std\n",
        "        return True\n",
        "\n",
        "    def solve(self, max_iterations):\n",
        "        for j in range(max_iterations):\n",
        "            distances = self.calc_distance()  \n",
        "            clusters = np.argmin(distances, axis=1) # get coef. of minimum distance\n",
        "            clustered_data = np.zeros([len(self.data),])\n",
        "            for i in range(len(self.data)):\n",
        "                if clusters[i] == 0:\n",
        "                    clustered_data[i] = 0\n",
        "                elif clusters[i] == 1:\n",
        "                    clustered_data[i] = 1\n",
        "                elif clusters[i] == 2:\n",
        "                    clustered_data[i] = 2\n",
        "                    if len(self.clusters) == 3:\n",
        "                        continue\n",
        "                elif clusters[i] == 3:\n",
        "                    clustered_data[i] = 3\n",
        "                    if len(self.clusters) == 4:\n",
        "                        continue\n",
        "                elif clusters[i] == 4:\n",
        "                    clustered_data[i] = 4\n",
        "                    if len(self.clusters) == 5:\n",
        "                        continue\n",
        "                elif clusters[i] == 5:\n",
        "                    clustered_data[i] = 5\n",
        "                    if len(self.clusters) == 6:\n",
        "                        continue\n",
        "                elif clusters[i] == 6:\n",
        "                    clustered_data[i] = 6\n",
        "                    if len(self.clusters) == 7:\n",
        "                        continue\n",
        "                elif clusters[i] == 7:\n",
        "                    clustered_data[i] = 7\n",
        "                    if len(self.clusters) == 8:\n",
        "                        continue\n",
        "                elif clusters[i] == 8:\n",
        "                    clustered_data[i] = 8\n",
        "                    if len(self.clusters) == 9:\n",
        "                        continue\n",
        "                elif clusters[i] == 9:\n",
        "                    clustered_data[i] = 9\n",
        "                    if len(self.clusters) == 10:\n",
        "                        continue\n",
        "                else:\n",
        "                    clustered_data[i] = 10\n",
        "            curr_centroids = deepcopy(self.centroids)\n",
        "            self.calculate_centroids(clustered_data)\n",
        "            mae = np.sum(np.absolute(np.subtract(curr_centroids, self.centroids)))\n",
        "            if mae < 0.002:     # Stop the clustering when change on centroids is very small\n",
        "                break\n",
        "        print(\"Final centroids: \")\n",
        "        print(self.centroids)\n",
        "        self.clust_data = clustered_data\n",
        "        return None\n",
        "            \n",
        "    def calculate_centroids(self, clustered_data):\n",
        "        for i in range(len(self.centroids)):\n",
        "            centroid_ind = np.where(clustered_data==i)\n",
        "            centroid_data = self.data[centroid_ind]\n",
        "            self.centroids[i, 0] = np.mean(centroid_data[:,0])\n",
        "            self.centroids[i, 1] = np.mean(centroid_data[:,1])\n",
        "        return None\n",
        "\n",
        "\n",
        "    def plot_result(self, labelx, labely, fig_title,\n",
        "                    fig_name, map_shape = (144, 72)):\n",
        "        plt.xlabel(str(labelx))\n",
        "        plt.ylabel(str(labely))\n",
        "        plt.title(str(fig_title))\n",
        "        fig_legend = []\n",
        "        img_plt = np.zeros([len(self.clust_data), 3], dtype=np.uint8)\n",
        "        for i in range(len(self.clusters)):\n",
        "            cent_ind = np.where(self.clust_data == i)\n",
        "            centroid_data = self.data[cent_ind]\n",
        "            plt.scatter(centroid_data[:,0], centroid_data[:,1], \n",
        "                        s=0.1, color=np.array(self.colors[i+1])/255.0)\n",
        "            fig_legend.append(str(\"Cluster \") + str(i))\n",
        "            img_plt[cent_ind] =np.array(self.colors[i+1])\n",
        "        img_plt = np.reshape(img_plt, (map_shape[0], map_shape[1], 3))\n",
        "        img_plt = np.rot90(img_plt)\n",
        "        fig_legend.append('Centroids')\n",
        "        plt.scatter(self.centroids[:,0], self.centroids[:,1],\n",
        "                    s=100, marker='+', c='black')\n",
        "        plt.legend(fig_legend)\n",
        "        plt.savefig(str(fig_name), format='png', dpi=200)\n",
        "        plt.show()\n",
        "        self.plot_map(img_plt, fig_title, fig_name)\n",
        "        return None\n",
        "    \n",
        "    def plot_map(self, datax, fig_title, fig_name, map_color='x', intpol = 'bilinear'):\n",
        "        plt.title(str(fig_title))\n",
        "        im = plt.imshow(datax/255.0)\n",
        "        plt.savefig(str('map_')+str(fig_name), format='png', dpi=200)\n",
        "        plt.show()\n",
        "        return None\n",
        "\n",
        "    def calc_distance(self):\n",
        "        ''' Calculate distances of data from all centroids\n",
        "            and return a matrix, with a column, which is \n",
        "            corresponding distance of the point.\n",
        "        '''\n",
        "        cdist= []\n",
        "        for centroid in self.centroids:\n",
        "            cdist.append(self.get_dist(centroid))\n",
        "        distances = cdist[0]\n",
        "        for i in range(1,len(cdist)):\n",
        "            distances = np.column_stack((distances, cdist[i]))\n",
        "        return distances\n",
        "\n",
        "    def silhouette(self):\n",
        "        S_i = []\n",
        "        for i in range(len(self.data)):\n",
        "          point_cl = self.clust_data[i]       # Get cluster of a_i\n",
        "          point = self.data[i]                # Get location of point_i\n",
        "          a_i = self.calc_a(point, point_cl)  # Calculate a_i\n",
        "          b_i = self.calc_b(point, point_cl)  # Calculate b_i\n",
        "          S_i.append((b_i - a_i)/max(b_i, a_i))\n",
        "        return np.mean(S_i)\n",
        "\n",
        "    def plot_silhouette(self, sil_array, title, fig_name):\n",
        "        plt.plot(np.arange(2, len(sil_array)+2, 1), sil_array)\n",
        "        plt.xlabel(str(\"Clusters\"))\n",
        "        plt.ylabel(str(\"Silhouette Coef.\"))\n",
        "        plt.title(str(title))\n",
        "        plt.savefig(str(fig_name), format='png', dpi=200)\n",
        "        plt.show()\n",
        "        return None\n",
        "    \n",
        "    def calc_a(self, point, cluster_):\n",
        "        ''' a_i for Silhouette calculation\n",
        "        '''\n",
        "        clust_ind = np.where(self.clust_data == cluster_)\n",
        "        cluster = self.data[clust_ind]\n",
        "        return np.nanmean(self.get_dist2(point, cluster))\n",
        "\n",
        "    def calc_b(self, point, cluster_):\n",
        "        ''' b_i for Silhouette calculation\n",
        "        '''\n",
        "        cluster_id = self.get_closest_centroid(point, cluster_)  # Get the closest cluster id\n",
        "        clust_ind = np.where(self.clust_data == cluster_id) # Get indexes of the data of that cluster\n",
        "        cluster = self.data[clust_ind]                      # Get data of that cluster\n",
        "        return np.nanmean(self.get_dist2(point, cluster))   # Calculate mean distance\n",
        "\n",
        "    def get_closest_centroid(self, point, cluster):\n",
        "        cluster_id = 100000000\n",
        "        dist_min = np.inf\n",
        "        for i, centroid in enumerate(self.centroids):\n",
        "          if i != cluster:\n",
        "             dist1 = (point- centroid)**2\n",
        "             dist =  np.sum(dist1)**0.5\n",
        "             if dist < dist_min:\n",
        "                dist_min = dist\n",
        "                cluster_id = i\n",
        "        return cluster_id\n",
        "\n",
        "    def get_dist2(self, point, xdata):\n",
        "        point_vect = np.tile(point, (len(xdata),1)) # repeate the vector to calculate all at once\n",
        "        dist1 = ((point_vect-xdata)**2)\n",
        "        dist = (dist1[:,0] + dist1[:,1])**0.5       # change this to make it multidimensional\n",
        "        return dist\n",
        "\n",
        "    def get_dist(self, centroid):\n",
        "        ''' Calculate distance of data from centroid\n",
        "        '''\n",
        "        centroid_vect = np.tile(centroid, (len(self.data),1)) # repeate the vector to calculate all at once\n",
        "        dist1 = ((centroid_vect-self.data)**2)\n",
        "        dist = (dist1[:,0] + dist1[:,1])**0.5       # change this to make it multidimensional\n",
        "        return dist"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "km = k_means(data, num_clusters, normalize_data = True)\n",
        "km.solve(max_iterations=10)"
      ]
    }
  ],
  "metadata": {
    "accelerator": "GPU",
    "colab": {
      "collapsed_sections": [],
      "name": "hw3_sol.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.6.9 64-bit",
      "metadata": {
        "interpreter": {
          "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
        }
      },
      "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.6.9-final"
    },
    "orig_nbformat": 2
  },
  "nbformat": 4,
  "nbformat_minor": 0
}