{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algoritam K-sredina"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Algoritam `k-sredina` (engl. k-means) pronalazi `k` klastera u skupu podataka. Svaki od klastera je predstavljen pomoću centroide koja se dobija uprosečavanjem instanci koje sadrži. \n",
    "\n",
    "Polaznih `k` centroida se bira nasumično, a potom se ponavljaju sledeći koraci:\n",
    "\n",
    "1. instance se raspoređuju u nove klastere tako što se svaka instanca pridruži najbližoj centroidi\n",
    "\n",
    "2. izračunavaju se nove centroide kao prosek instanci koje su im pridružene\n",
    "\n",
    "\n",
    "Ovi koraci se izvršavaju sve dok se centroide menjaju. Kada su centroide iste u dve uzastopne iteracije, algoritam se zaustavlja.\n",
    "\n",
    "Ukoliko korisnik zna nešto o strukturi svojih podataka, početni centroidi se mogu i pažljivije odabrati.\n",
    "\n",
    "<img src='assets/k-means.png'>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Scikit-learn` biblioteka omogućava korišćenje algortima k-sredina kroz `KMeans` klasu `cluster` paketa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sledeći skup sadrži dva klastera podataka - prvi klaster prati x-koordinatu sa vrednošću 1, a drugi x-koordinatu sa vrednošću 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 6180 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(data[:, 0], data[:, 1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`KMeans` funkcija očekuje broj klastera i inicijalizaciju kojom se utiče na izbor početnih centroida. Postoje i druga podešavanja algoritma kroz maksimalan broj iteracija, izbor pozadinskog algoritma, paralelizaciju i slično. Ovako kreirani model poštuje `fit - predict` princip rada metoda nadgledanog učenja koje smo upoznali u uvodnom delu kursa. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KMeans(n_clusters=2, random_state=0)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans = KMeans(n_clusters=2, random_state=0)\n",
    "kmeans.fit(data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obeležja pripisana instancama se mogu pročitati kroz `labels_` svojstvo naučenog modela ili pozivom funkcije `predict`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 1, 1, 0, 0, 0])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 1, 1, 0, 0, 0])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "labels_predicted = kmeans.predict(data)\n",
    "labels_predicted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Informacije o centroidima klastera se mogu dobiti pomoću svojstva `cluster_centers_`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[10.,  2.],\n",
       "       [ 1.,  2.]])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans.cluster_centers_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans.cluster_centers_[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ako labelama pridružimo boje, možemo prikazati i kako dobijeni klasteri izgledaju. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.collections.PathCollection at 0x1499c80b048>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 7192 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(data[:, 0], data[:, 1], c=labels_predicted)\n",
    "plt.scatter(kmeans.cluster_centers_[0][0], kmeans.cluster_centers_[0][1], marker='x')\n",
    "plt.scatter(kmeans.cluster_centers_[1][0], kmeans.cluster_centers_[1][1], marker='x')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obeležja novih instanci takođe dobijamo korišćenjem `predict` metode."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 0])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans.predict([[0, 0], [12, 3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Odabir parametra `k` za broj klastera"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "U praksi obično radimo sa većim skupovima podataka u kojima nije baš uvek intuitivno pretpostaviti broj postojećih klastera. Optimalan broj klastera određujemo tako što pratimo ponašanje modela za različite vrednosti ovog parametra, a potom odaberemo najoptimalniju tj. onu za koju se dobija najmanja vrednost funkcije cilja. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='assets/k-means_objective.png'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcija `make_blobs` biblioteke scikit-learn omogućava kreiranje testnih skupova podataka. Njeni argumenti su ukupan broj instanci skupa (`n_samples` parametar), veličina prostora atributa (`n_features` parametar), broj centroida tj. klastera (`centers` parametar) i parametar kojim se utiče na izbor njihovog raspoređivanja (`random_state` parametar). Povratne vrednosti funkcije su generisani skup podataka oblika `n_samples x n_features` i njima pridružene labele."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_blobs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "X, y = make_blobs(n_samples=100, n_features=2, centers=4, random_state=6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(100, 2)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3, 1, 0, 2, 1, 3, 1, 3, 2, 3, 0, 2, 3, 2, 0, 2, 0, 1, 0, 2, 0, 1,\n",
       "       3, 0, 0, 2, 1, 1, 3, 3, 0, 2, 3, 1, 0, 2, 1, 1, 3, 3, 0, 3, 2, 2,\n",
       "       2, 1, 3, 0, 2, 2, 1, 1, 1, 1, 1, 0, 0, 2, 3, 0, 0, 3, 0, 3, 2, 1,\n",
       "       3, 1, 2, 0, 2, 3, 0, 2, 0, 0, 1, 2, 0, 3, 2, 2, 0, 1, 1, 3, 2, 3,\n",
       "       2, 1, 0, 1, 1, 1, 2, 3, 3, 0, 3, 3])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 21112 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.title('Generisani podaci')\n",
    "plt.scatter(X[:, 0], X[:, 1], c=y, cmap='viridis')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tražićemo optimalni broj klastera u opsegu od 1 do 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "Ks = range(1, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zatim ćemo za svaku vrednost parametra `k` kreirati poseban model i oceniti ga. Ocenu ćemo dobiti korišćenjem bibliotečke funkcije `score` kojom se dobija negativna vrednost funkcije cilja. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "kms = [KMeans(n_clusters=i, random_state=7) for i in Ks]\n",
    "score = [km.fit(X).score(X) for km in kms]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sada možemo generisati grafik dobijenih ocena. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 10708 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(Ks, score)\n",
    "plt.scatter(4, score[3], c='red')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Možemo da zaključimo da je `k = 4` najbolja vrednost jer se nakon toga funkcija cilja stabilizuje, a pre toga ima značajno nepoželjnije vrednosti."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prikazaćemo rezultate koji se dobijaju korišćenjem ovog modela."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KMeans(n_clusters=4)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans = KMeans(n_clusters=4)\n",
    "kmeans.fit(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_predicted = kmeans.predict(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 23096 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.title('Rezultat grupisanja podataka KMeans algoritmom')\n",
    "plt.scatter(X[:, 0], X[:, 1], c=y_predicted, cmap='viridis')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
