basic_leader_follower.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "binary-receipt",
   "metadata": {},
   "source": [
    "# Basic leader follower"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "eastern-pakistan",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "legitimate-speaking",
   "metadata": {},
   "outputs": [],
   "source": [
    "def euc(x, y):\n",
    "    return np.linalg.norm(x - y)\n",
    "\n",
    "def classify(x, centers):\n",
    "    dist = np.Infinity\n",
    "    center = None\n",
    "    for i, c in enumerate(centers):\n",
    "        d = euc(c, x)\n",
    "        if d < dist:\n",
    "            center = i\n",
    "            dist = d\n",
    "    return (center, dist)\n",
    "\n",
    "def basic_leader_follower_no_norm(X, lr=0.1, treshold=3, iterations=100, end_treshold=0.5):\n",
    "    centers = []\n",
    "    old_centers = []\n",
    "    iteration = 0\n",
    "    max_dist = np.Infinity\n",
    "    while iteration < iterations and max_dist > end_treshold:\n",
    "        # accept new x finding the nearest center or creating it if no center\n",
    "        for i, x in enumerate(X):\n",
    "            old_centers = centers\n",
    "            iteration += 1\n",
    "            print('------------------------')\n",
    "            print('ITERATION', iteration)\n",
    "            print('------------------------')\n",
    "            print('sample: ', x)\n",
    "            if len(centers) == 0:\n",
    "                centers.append(x)\n",
    "                print('created cluster', 0, ':', centers[0])\n",
    "            else:\n",
    "                dists = []\n",
    "                for center in centers:\n",
    "                    dists.append(euc(x, center)) \n",
    "                # assign the closest center\n",
    "                c = dists.index(min(dists))\n",
    "                print('nearest cluster is', c, ':', centers[c])\n",
    "                if dists[c] < treshold:\n",
    "                    centers[c] = centers[c] + lr * (x - centers[c])\n",
    "                    print('distance is:', dists[c], '- x belongs to the cluster')\n",
    "                else:\n",
    "                    centers.append(x)\n",
    "                    print('distance is:', dists[c], '- x creates a new cluster')\n",
    "                print('centers:', centers)\n",
    "                if len(old_centers) == len(centers):\n",
    "                    c_dists = []\n",
    "                    for c, center in enumerate(centers):\n",
    "                        c_dists.append(euc(center, old_centers[c]))\n",
    "                    print('dists:', c_dists)\n",
    "                    max_diff = max(c_dists)\n",
    "                    \n",
    "        return centers\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eae6266e",
   "metadata": {},
   "source": [
    "## Examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "suspended-rolling",
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.array([\n",
    "    [-1, 3],\n",
    "    [1, 4],\n",
    "    [0, 5],\n",
    "    [4, -1],\n",
    "    [3, 0],\n",
    "    [5, 1]\n",
    "])\n",
    "\n",
    "X_ord = np.array([\n",
    "    [0, 5],\n",
    "    [-1, 3],\n",
    "    [-1, 3],\n",
    "    [3, 0],\n",
    "    [5, 1]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "inappropriate-eclipse",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------\n",
      "ITERATION 1\n",
      "------------------------\n",
      "sample:  [0 5]\n",
      "created cluster 0 : [0 5]\n",
      "------------------------\n",
      "ITERATION 2\n",
      "------------------------\n",
      "sample:  [-1  3]\n",
      "nearest cluster is 0 : [0 5]\n",
      "distance is: 2.23606797749979 - x belongs to the cluster\n",
      "centers: [array([-0.5,  4. ])]\n",
      "dists: [0.0]\n",
      "------------------------\n",
      "ITERATION 3\n",
      "------------------------\n",
      "sample:  [-1  3]\n",
      "nearest cluster is 0 : [-0.5  4. ]\n",
      "distance is: 1.118033988749895 - x belongs to the cluster\n",
      "centers: [array([-0.75,  3.5 ])]\n",
      "dists: [0.0]\n",
      "------------------------\n",
      "ITERATION 4\n",
      "------------------------\n",
      "sample:  [3 0]\n",
      "nearest cluster is 0 : [-0.75  3.5 ]\n",
      "distance is: 5.129571132170798 - x creates a new cluster\n",
      "centers: [array([-0.75,  3.5 ]), array([3, 0])]\n",
      "dists: [0.0, 0.0]\n",
      "------------------------\n",
      "ITERATION 5\n",
      "------------------------\n",
      "sample:  [5 1]\n",
      "nearest cluster is 1 : [3 0]\n",
      "distance is: 2.23606797749979 - x belongs to the cluster\n",
      "centers: [array([-0.75,  3.5 ]), array([4. , 0.5])]\n",
      "dists: [0.0, 0.0]\n"
     ]
    }
   ],
   "source": [
    "centers = basic_leader_follower_no_norm(X_ord, lr=0.5, treshold=3, iterations=5, end_treshold=0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "funky-couple",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "classify(np.array([0, -2]), centers)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "focal-patient",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1  3] : cluster 0\n",
      "[1 4] : cluster 0\n",
      "[0 5] : cluster 0\n",
      "[ 4 -1] : cluster 1\n",
      "[3 0] : cluster 1\n",
      "[5 1] : cluster 1\n"
     ]
    }
   ],
   "source": [
    "y = []\n",
    "for i, x in enumerate(X):\n",
    "    y.append(classify(x, centers)[0])\n",
    "for i in range(len(y)):\n",
    "    print(X[i], ': cluster', y[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "compact-universe",
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}