GA-K-Means.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.metrics import silhouette_score\n",
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "data=pd.read_csv('iris.csv')\n",
    "stddata=np.array(data.drop('classification',axis=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   # Code initialization & defining all functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "cp=0.8\n",
    "mp=0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValid(sample,this):\n",
    "    if(set(sample)==this):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "##    Calculating cluster centers for given population \n",
    "\n",
    "def SCenters(samp):\n",
    "    centers={}\n",
    "    for i in set(samp):\n",
    "        A=[]\n",
    "        for j in samp:\n",
    "            if(j==i):\n",
    "                A.append(True)\n",
    "            else:\n",
    "                A.append(False)\n",
    "        centers[i]=np.array(stddata[A].mean())\n",
    "    return centers\n",
    "\n",
    "\n",
    "def getCenters(Gen):\n",
    "    GenCenters=[]\n",
    "    for samp in Gen:\n",
    "        GenCenters.append(SCenters(samp))\n",
    "    return GenCenters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  Calculating Fitness\n",
    "from scipy.spatial import distance\n",
    "                                        ##Calculating the Euclidean distance for within clusters and summing them\n",
    "def getFit(sample,centers):\n",
    "    fit=0\n",
    "    for i in range(0,len(sample)):\n",
    "        fit = fit + distance.euclidean(    stddata[i]  ,  centers[  sample[i]  ]        )\n",
    "    return fit\n",
    "def getFitness(Gen):\n",
    "    GenCenters=getCenters(Gen)\n",
    "    fitness=[]                                                #Euclidian dist as fitness\n",
    "    for i in range(0,len(Gen)):\n",
    "        fitness.append(      getFit(Gen[i],GenCenters[i])         )\n",
    "    return fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  CrossOver function\n",
    "def crossOver(c1,c2):\n",
    "    pos=np.random.randint(1,len(c1))\n",
    "    c1[pos:],c2[pos:]=c2[pos:],c1[pos:]\n",
    "    return c1,c2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  Mutation function\n",
    "def mute(samp):\n",
    "    tget=np.random.randint(0,R)\n",
    "    by=np.random.randint(0,K) \n",
    "    if(samp[tget]!=by):\n",
    "        samp[tget]=by\n",
    "    else:\n",
    "        samp[tget]=(samp[tget]+by)%K\n",
    "def mutate(Gen):\n",
    "    for samp in Gen: \n",
    "        pb=np.random.random()\n",
    "        if(pb<mp):\n",
    "            mute(samp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   # INITIAL POPULATION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "{0, 1, 2}\n{0, 1, 2}\n{0, 1, 2}\n{0, 1, 2}\n{0, 1, 2}\n{0, 1, 2}\n"
     ]
    }
   ],
   "source": [
    "K=3\n",
    "\n",
    "R=len(stddata)   ##--> No.of rows\n",
    "c=set(np.linspace(0,K-1,K))\n",
    "\n",
    "P=6     ##CHOOSE P-value (Population size)\n",
    "i=0\n",
    "currentGen=[]\n",
    "nextGen=[]\n",
    "while(i<P):\n",
    "        nextGen.append([])\n",
    "        currentGen.append(      list( np.random.randint(0,K,R)    )  )\n",
    "        print(set(currentGen[i]))\n",
    "        i=i+1\n",
    "thebest=currentGen[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2,\n",
       "       2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2,\n",
       "       2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 1], dtype=int32)"
      ]
     },
     "metadata": {},
     "execution_count": 20
    }
   ],
   "source": [
    "kmeans=KMeans(K).fit(stddata)\n",
    "klabels=kmeans.labels_\n",
    "klabels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#        LOOP BEGINS FROM HERE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "scrolled": true,
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "generation- 1 START\n",
      "\t\tEND silhouette score= -0.02194917379741539\n",
      "generation- 2 START\n",
      "\t\tEND silhouette score= -0.02277123698413875\n",
      "generation- 3 START\n",
      "\t\tEND silhouette score= -0.02553972287519187\n",
      "generation- 4 START\n",
      "\t\tEND silhouette score= -0.02194917379741539\n",
      "generation- 5 START\n",
      "\t\tEND silhouette score= -0.028462331209894217\n",
      "generation- 6 START\n",
      "\t\tEND silhouette score= -0.024469704223696157\n",
      "generation- 7 START\n",
      "\t\tEND silhouette score= -0.023924378631121422\n",
      "generation- 8 START\n",
      "\t\tEND silhouette score= -0.014087835271548681\n",
      "generation- 9 START\n",
      "\t\tEND silhouette score= -0.018936503177819117\n",
      "generation- 10 START\n",
      "\t\tEND silhouette score= -0.017028948941163982\n",
      "generation- 11 START\n",
      "\t\tEND silhouette score= -0.007736494085172202\n",
      "generation- 12 START\n",
      "\t\tEND silhouette score= -0.007736494085172202\n",
      "generation- 13 START\n",
      "\t\tEND silhouette score= -0.007736494085172202\n",
      "generation- 14 START\n",
      "\t\tEND silhouette score= -0.015226491955926201\n",
      "generation- 15 START\n",
      "\t\tEND silhouette score= -0.010093091722178137\n",
      "generation- 16 START\n",
      "\t\tEND silhouette score= -0.020731139849258676\n",
      "generation- 17 START\n",
      "\t\tEND silhouette score= 0.0038976779842084083\n",
      "generation- 18 START\n",
      "\t\tEND silhouette score= -0.0038598709394242845\n",
      "generation- 19 START\n",
      "\t\tEND silhouette score= 0.0038976779842084083\n",
      "generation- 20 START\n",
      "\t\tEND silhouette score= 0.0038976779842084083\n",
      "generation- 21 START\n",
      "\t\tEND silhouette score= 0.0007966185012777712\n",
      "generation- 22 START\n",
      "\t\tEND silhouette score= 0.006255631944002182\n",
      "generation- 23 START\n",
      "\t\tEND silhouette score= 0.006255631944002182\n",
      "generation- 24 START\n",
      "\t\tEND silhouette score= 0.006255631944002182\n",
      "generation- 25 START\n",
      "\t\tEND silhouette score= 0.0026533732551138733\n",
      "generation- 26 START\n",
      "\t\tEND silhouette score= 0.005923259425002835\n",
      "generation- 27 START\n",
      "\t\tEND silhouette score= 0.006255631944002182\n",
      "generation- 28 START\n",
      "\t\tEND silhouette score= 0.006255631944002182\n",
      "generation- 29 START\n",
      "\t\tEND silhouette score= 0.005923259425002835\n",
      "generation- 30 START\n",
      "\t\tEND silhouette score= -0.0006040790544353551\n",
      "generation- 31 START\n",
      "\t\tEND silhouette score= 0.012928502762821814\n",
      "generation- 32 START\n",
      "\t\tEND silhouette score= 0.012928502762821814\n",
      "generation- 33 START\n",
      "\t\tEND silhouette score= 0.016682892223203585\n",
      "generation- 34 START\n",
      "\t\tEND silhouette score= 0.016682892223203585\n",
      "generation- 35 START\n",
      "\t\tEND silhouette score= 0.014947818770384475\n",
      "generation- 36 START\n",
      "\t\tEND silhouette score= 0.01343086828633954\n",
      "generation- 37 START\n",
      "\t\tEND silhouette score= 0.01892051506715378\n",
      "generation- 38 START\n",
      "\t\tEND silhouette score= 0.01892051506715378\n",
      "generation- 39 START\n",
      "\t\tEND silhouette score= 0.01892051506715378\n",
      "generation- 40 START\n",
      "\t\tEND silhouette score= 0.0214315070285859\n",
      "generation- 41 START\n",
      "\t\tEND silhouette score= 0.012857874444609584\n",
      "generation- 42 START\n",
      "\t\tEND silhouette score= 0.022319915616797945\n",
      "generation- 43 START\n",
      "\t\tEND silhouette score= 0.03286103824888288\n",
      "generation- 44 START\n",
      "\t\tEND silhouette score= 0.023993790655284578\n",
      "generation- 45 START\n",
      "\t\tEND silhouette score= 0.03286103824888288\n",
      "generation- 46 START\n",
      "\t\tEND silhouette score= 0.02672333217459629\n",
      "generation- 47 START\n",
      "\t\tEND silhouette score= 0.037660571126818136\n",
      "generation- 48 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 49 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 50 START\n",
      "\t\tEND silhouette score= 0.041653341212447174\n",
      "generation- 51 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 52 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 53 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 54 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 55 START\n",
      "\t\tEND silhouette score= 0.03999521752422831\n",
      "generation- 56 START\n",
      "\t\tEND silhouette score= 0.04460182468779503\n",
      "generation- 57 START\n",
      "\t\tEND silhouette score= 0.04508476925469685\n",
      "generation- 58 START\n",
      "\t\tEND silhouette score= 0.05044963873499559\n",
      "generation- 59 START\n",
      "\t\tEND silhouette score= 0.05044963873499559\n",
      "generation- 60 START\n",
      "\t\tEND silhouette score= 0.05044963873499559\n",
      "generation- 61 START\n",
      "\t\tEND silhouette score= 0.05044963873499559\n",
      "generation- 62 START\n",
      "\t\tEND silhouette score= 0.05201006628763672\n",
      "generation- 63 START\n",
      "\t\tEND silhouette score= 0.055988269812708664\n",
      "generation- 64 START\n",
      "\t\tEND silhouette score= 0.04745588461692451\n",
      "generation- 65 START\n",
      "\t\tEND silhouette score= 0.05294756617402458\n",
      "generation- 66 START\n",
      "\t\tEND silhouette score= 0.049510164595146886\n",
      "generation- 67 START\n",
      "\t\tEND silhouette score= 0.060523094337187236\n",
      "generation- 68 START\n",
      "\t\tEND silhouette score= 0.06563509095998545\n",
      "generation- 69 START\n",
      "\t\tEND silhouette score= 0.06563509095998545\n",
      "generation- 70 START\n",
      "\t\tEND silhouette score= 0.06802591793808156\n",
      "generation- 71 START\n",
      "\t\tEND silhouette score= 0.06802591793808156\n",
      "generation- 72 START\n",
      "\t\tEND silhouette score= 0.06802591793808156\n",
      "generation- 73 START\n",
      "\t\tEND silhouette score= 0.06802591793808156\n",
      "generation- 74 START\n",
      "\t\tEND silhouette score= 0.06196556028932431\n",
      "generation- 75 START\n",
      "\t\tEND silhouette score= 0.06802591793808156\n",
      "generation- 76 START\n",
      "\t\tEND silhouette score= 0.06802591793808156\n",
      "generation- 77 START\n",
      "\t\tEND silhouette score= 0.07811996910130557\n",
      "generation- 78 START\n",
      "\t\tEND silhouette score= 0.08130487685983208\n",
      "generation- 79 START\n",
      "\t\tEND silhouette score= 0.08130487685983208\n",
      "generation- 80 START\n",
      "\t\tEND silhouette score= 0.07708706639456897\n",
      "generation- 81 START\n",
      "\t\tEND silhouette score= 0.0774178472965915\n",
      "generation- 82 START\n",
      "\t\tEND silhouette score= 0.07143816956299842\n",
      "generation- 83 START\n",
      "\t\tEND silhouette score= 0.08301824502775455\n",
      "generation- 84 START\n",
      "\t\tEND silhouette score= 0.08130487685983208\n",
      "generation- 85 START\n",
      "\t\tEND silhouette score= 0.07350480927247008\n",
      "generation- 86 START\n",
      "\t\tEND silhouette score= 0.07439443708389279\n",
      "generation- 87 START\n",
      "\t\tEND silhouette score= 0.08398925798816666\n",
      "generation- 88 START\n",
      "\t\tEND silhouette score= 0.08398925798816666\n",
      "generation- 89 START\n",
      "\t\tEND silhouette score= 0.08398925798816666\n",
      "generation- 90 START\n",
      "\t\tEND silhouette score= 0.07252150049733175\n",
      "generation- 91 START\n",
      "\t\tEND silhouette score= 0.07315214105508798\n",
      "generation- 92 START\n",
      "\t\tEND silhouette score= 0.10012528407078647\n",
      "generation- 93 START\n",
      "\t\tEND silhouette score= 0.10012528407078647\n",
      "generation- 94 START\n",
      "\t\tEND silhouette score= 0.0927703776501455\n",
      "generation- 95 START\n",
      "\t\tEND silhouette score= 0.08961387782071609\n",
      "generation- 96 START\n",
      "\t\tEND silhouette score= 0.09155268697442924\n",
      "generation- 97 START\n",
      "\t\tEND silhouette score= 0.09413491040912603\n",
      "generation- 98 START\n",
      "\t\tEND silhouette score= 0.09413491040912603\n",
      "generation- 99 START\n",
      "\t\tEND silhouette score= 0.09413491040912603\n",
      "generation- 100 START\n",
      "\t\tEND silhouette score= 0.09299883250952062\n"
     ]
    }
   ],
   "source": [
    "stop=1\n",
    "while(stop<=10000):\n",
    "    print(\"generation-\",stop,'START')\n",
    "    \n",
    "    \n",
    "    # Selection\n",
    "    fit=np.array(getFitness(currentGen))\n",
    "    pool=fit.argsort()\n",
    "\n",
    "\n",
    "    # Cross-over\n",
    "    for i in range(0,P,2):\n",
    "        pb=np.random.random()\n",
    "        if(pb<cp):\n",
    "            while(True):\n",
    "                ch1,ch2=crossOver(currentGen[pool[i]],currentGen[pool[i+1]])\n",
    "                if( isValid(ch1,c) and isValid(ch2,c) ):\n",
    "                    break\n",
    "        else:                                                        # if no crossover, sends as it is\n",
    "            ch1,ch2=currentGen[pool[i]],currentGen[pool[i+1]]\n",
    "        nextGen[i]=ch1\n",
    "        nextGen[i+1]=ch2\n",
    "\n",
    "\n",
    "    # Mutation\n",
    "    mutate(nextGen)\n",
    "\n",
    "    curr_fit=list(fit)\n",
    "    next_fit=np.array(getFitness(nextGen))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    s0=currentGen[fit.argmin()].copy()     #best string of currentGen\n",
    "    \n",
    "    if( silhouette_score(stddata,thebest)  <  silhouette_score(stddata,s0)  ):\n",
    "        thebest=s0.copy()                       #Storing the best string in all generations generated so far\n",
    "    if(max(next_fit)>min(curr_fit)):              \n",
    "        nextGen[next_fit.argmax()]=thebest.copy()\n",
    "    \n",
    "    currentGen=nextGen.copy()\n",
    "    #print('\\t\\tEND',\"Best Fitness=\",min(curr_fit))\n",
    "    print('\\t\\tEND',\"silhouette score=\",silhouette_score(stddata,s0))\n",
    "    stop=stop+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Best of last Gen--> 0.09299883250952062\nOverall Best--> 0.10012528407078647\nActual-----> 0.5032506980665505\nWith KMeans--> 0.5525919445499757\n"
     ]
    }
   ],
   "source": [
    "print('Best of last Gen-->',silhouette_score(stddata,s0))\n",
    "print('Overall Best-->',silhouette_score(stddata,thebest))\n",
    "print('Actual----->',silhouette_score(stddata,data['classification']))\n",
    "print('With KMeans-->',silhouette_score(stddata,klabels))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python385jvsc74a57bd0916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1",
   "display_name": "Python 3.8.5 64-bit"
  },
  "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.5"
  },
  "metadata": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}