From 8a9c5cc9cd62425d7f6d4571429f1c7a0e85cf51 Mon Sep 17 00:00:00 2001 From: itsGarrin Date: Mon, 6 Nov 2023 13:52:30 -0500 Subject: Added route minimization for 2 routes. --- Clustering.ipynb | 658 +++++++++++++++++++++++++++++++--------------------- Clustering2.0.ipynb | 313 +++++++++++++++++++++++++ utils.py | 161 ++++++++++++- 3 files changed, 864 insertions(+), 268 deletions(-) create mode 100644 Clustering2.0.ipynb diff --git a/Clustering.ipynb b/Clustering.ipynb index e658dcf..a84f8e7 100644 --- a/Clustering.ipynb +++ b/Clustering.ipynb @@ -2,31 +2,26 @@ "cells": [ { "cell_type": "code", - "execution_count": 78, + "execution_count": 1, "id": "initial_id", "metadata": { "collapsed": true, "ExecuteTime": { - "end_time": "2023-11-06T01:14:10.536728Z", - "start_time": "2023-11-06T01:14:10.525881Z" + "end_time": "2023-11-06T17:13:47.429577Z", + "start_time": "2023-11-06T17:13:46.508767Z" } }, "outputs": [], "source": [ "import folium\n", - "import matplotlib.pyplot as plt\n", - "import numpy as np\n", "import pandas as pd\n", - "from scipy.cluster.hierarchy import dendrogram, linkage\n", - "from scipy.cluster.hierarchy import fcluster\n", - "from sklearn.metrics import silhouette_score\n", "from sklearn.cluster import KMeans\n", "import utils" ] }, { "cell_type": "code", - "execution_count": 79, + "execution_count": 2, "outputs": [], "source": [ "# Load the data\n", @@ -38,15 +33,34 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:10.821794Z", - "start_time": "2023-11-06T01:14:10.808507Z" + "end_time": "2023-11-06T17:13:47.436966Z", + "start_time": "2023-11-06T17:13:47.428637Z" } }, "id": "bb6f57eef695cf76" }, { "cell_type": "code", - "execution_count": 80, + "execution_count": 3, + "outputs": [], + "source": [ + "# Create two centroids, one in the North End and one in the Financial District\n", + "centroids = [[42.364506, -71.054733], [42.358894, -71.056742]]\n", + "\n", + "northeastern_coordinate = \"-71.09033,42.33976;\"" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:13:47.446315Z", + "start_time": "2023-11-06T17:13:47.437257Z" + } + }, + "id": "fe8a5b9bc06cf2e0" + }, + { + "cell_type": "code", + "execution_count": 4, "outputs": [ { "data": { @@ -70,15 +84,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:11.326041Z", - "start_time": "2023-11-06T01:14:11.322857Z" + "end_time": "2023-11-06T17:13:47.449096Z", + "start_time": "2023-11-06T17:13:47.439983Z" } }, "id": "dc434958d5e4a3a8" }, { "cell_type": "code", - "execution_count": 81, + "execution_count": 5, "outputs": [], "source": [ "# Remove all columns but name and gps\n", @@ -87,15 +101,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:12.014736Z", - "start_time": "2023-11-06T01:14:12.007694Z" + "end_time": "2023-11-06T17:13:47.455551Z", + "start_time": "2023-11-06T17:13:47.449946Z" } }, "id": "2873c16423fe3119" }, { "cell_type": "code", - "execution_count": 82, + "execution_count": 6, "outputs": [], "source": [ "# Convert the gps column to a list of lists for k-means\n", @@ -105,117 +119,53 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:12.457221Z", - "start_time": "2023-11-06T01:14:12.448967Z" + "end_time": "2023-11-06T17:13:47.455655Z", + "start_time": "2023-11-06T17:13:47.452798Z" } }, "id": "29f9155ef8d75fda" }, { "cell_type": "code", - "execution_count": 83, - "outputs": [ - { - "data": { - "text/plain": " name gps list\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A\n1 Acorn St [42.3576234, -71.0688746] A\n2 Arlington's Great Meadows [42.4299758, -71.2038948] A\n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A\n4 BU Beach [42.3511927, -71.1060828] A\n.. ... ... ...\n28 The Clam Box [42.2763168, -71.0092883] C\n29 The Partisans [42.3478375, -71.0404428] C\n30 Union Oyster House [42.361288, -71.056908] C\n31 Victoria's Diner [42.3270498, -71.0667744] C\n32 Wollaston Beach [42.2806539, -71.0119933] C\n\n[131 rows x 3 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslist
0521 Commercial Street #525[42.3688272, -71.0553792]A
1Acorn St[42.3576234, -71.0688746]A
2Arlington's Great Meadows[42.4299758, -71.2038948]A
3Arthur Fiedler Statue[42.3565057, -71.0754527]A
4BU Beach[42.3511927, -71.1060828]A
............
28The Clam Box[42.2763168, -71.0092883]C
29The Partisans[42.3478375, -71.0404428]C
30Union Oyster House[42.361288, -71.056908]C
31Victoria's Diner[42.3270498, -71.0667744]C
32Wollaston Beach[42.2806539, -71.0119933]C
\n

131 rows × 3 columns

\n
" - }, - "metadata": {}, - "output_type": "display_data" - } - ], + "execution_count": 7, + "outputs": [], "source": [ - "display(TotalList)" + "# Create a new column with normalized gps coordinates and centroids\n", + "TotalList['normalized_gps'], norm_centroids = utils.normalize_gps(TotalList['gps'].values.tolist(), centroids)" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:13.043659Z", - "start_time": "2023-11-06T01:14:13.030154Z" + "end_time": "2023-11-06T17:13:47.472084Z", + "start_time": "2023-11-06T17:13:47.454865Z" } }, - "id": "a03a7c5dacebddd0" - }, - { - "cell_type": "markdown", - "source": [ - "# Dendrogram" - ], - "metadata": { - "collapsed": false - }, - "id": "72e85d219be8c635" + "id": "5b985f1a6df84a6c" }, { "cell_type": "code", - "execution_count": 84, + "execution_count": 8, "outputs": [ { "data": { - "text/plain": "
", - "image/png": "iVBORw0KGgoAAAANSUhEUgAAB9gAAANcCAYAAAAU0nQ9AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAACOy0lEQVR4nOz9e5TWdb3//z8GhhkGlMlDIhoiaSKGJoI7we2hUtTUDu6CsrQSSxdlm8iviZgHtDA109qp0c7QXSqZ5kcNLXaJWWqlQSfNnaaCCKKkYDICA9fvD3/McuTgi2HgGpjbba1rrZn3vA/Pa5hZhXde73dNpVKpBAAAAAAAAABYpy7VHgAAAAAAAAAANgcCOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AADAZmTKlCmpqanJgw8+uMavH3PMMdl1111bbdt1113zyU9+cuMPtxHMmDEjNTU1+fGPf/yG+37yk59c7b23p/POOy81NTXF+997770ZOXJkdt5559TV1aWxsTHDhw/PVVddlZdffrllv4395/PVr341t95660Y595NPPpmamppMmTJlo5y/5NqrXt26dct2222X/fffP1/4whfy17/+dZPP9Fob++cRAACA6hDYAQAAtnA/+clP8uUvf7naY2x0X/7yl/OTn/yk2mMkSc4999wcfPDBmTt3bi644IJMnz49N954Y97znvfkvPPOy9lnn73JZtmYgb1Pnz65//77c/TRR2+U85c47bTTcv/99+eee+7J//zP/+QDH/hAbrvttrzjHe/IJZdcUrW5AAAA2DLVVnsAAAAANq7Bgwe327kqlUpeeeWVNDQ0bNB5mpqaNvgcr7fbbru16/na6qabbsrEiRMzevTofPe732216v2oo47KGWeckfvvv7+KE264FStWpLm5OfX19TnggAOqOssuu+zSaob3vve9GTduXI477ricccYZGTRoUI466qgqTrh2r/0+bmzt9bsLAADQ2VnBDgAAsIVb0y3IFy9enNNPPz39+/dPXV1ddt5554wdO7bVrcuTpKamJp/73Ody9dVXZ+DAgamvr8+1116bJDn//PPzzne+M9tuu2169eqV/fbbL9/73vdSqVRWu/4xxxyTW265JYMHD0737t1z/vnnJ0nmzp2bz3zmM+nbt2/q6uqy00475UMf+lCeffbZVudYvnx5JkyYkJ122im9evXKYYcdlkcffbTVPmu6JffKlSvzrW99K/vuu28aGhrypje9KQcccEBuu+22ln2mTp2aESNGpE+fPmloaMjAgQNz5plnrva9KDVx4sRss802+eY3v7nGW8pvvfXWGTFixFqPX/UYgCeffLLV9lW3y58xY0bLtpkzZ+aYY47JDjvskPr6+uy00045+uij8/TTTyd59c/v5ZdfzrXXXttyK/VDDz205fj58+fnlFNOyVve8pbU1dWlf//+Of/889Pc3Nyyz6pbsV988cW58MIL079//9TX1+fuu+9e4y3iV91K/69//Ws++tGPprGxMb17985JJ52URYsWtXpPL774YkaPHp1tt902W221VY4++uj84x//SE1NTc4777w3/mavRUNDQ773ve+lW7duq61iX5/3fOmll+ayyy5L//79s9VWW2XYsGF54IEHVrvelClTMmDAgNTX12fgwIG57rrrVttnXd/HJLntttsybNiw9OjRI1tvvXUOP/zwNf5DjP/3//5f9tlnn9TX1+etb31rrrjiijU+vqA9f3fvuOOODB48uOX344477mh53wMHDkzPnj3zb//2b2t9dAUAAMCWxAp2AACAzdCqla+v9/pAtiZLlizJIYcckqeffjpnnXVW9tlnn/z1r3/NOeeckz//+c/53//931ax7tZbb829996bc845JzvuuGN22GGHJK8Gw1NOOSW77LJLkuSBBx7Iaaedlrlz5+acc85pdc0//OEPeeSRR3L22Wenf//+6dmzZ+bOnZv9998/y5cvb5lj4cKF+dnPfpYXXnghvXv3bjn+rLPOyoEHHpj//u//zuLFi/OlL30pxx57bB555JF07dp1re/1k5/8ZH7wgx9k9OjRmThxYurq6vKHP/yhVbz++9//nve+970ZO3Zsevbsmb/97W/52te+lt/97nf55S9/+Ybfz9eaN29e/vKXv2TUqFHp0aPHeh27vl5++eUcfvjh6d+/f7797W+nd+/emT9/fu6+++689NJLSZL7778/7373u/Oud72r5TEBvXr1SvJqaP63f/u3dOnSJeecc05222233H///bnwwgvz5JNP5vvf/36r633zm9/MHnvskUsvvTS9evXK2972tnXO9x//8R8ZNWpURo8enT//+c8ZP358kuSaa65J8uo/fjj22GPz4IMP5rzzzst+++2X+++/P0ceeWS7fH922mmnDBkyJPfdd1+am5tTW1u73u/529/+dvbcc89cfvnlSV59DMF73/vePPHEE2lsbEzyamT+1Kc+lfe///35+te/nkWLFuW8887L0qVL06XL6usa1vR9vP766/Oxj30sI0aMyA033JClS5fm4osvzqGHHppf/OIX+fd///ckyV133ZXjjjsuBx98cKZOnZrm5uZceumlq/2DlFXa43f3j3/8Y8aPH58JEyaksbEx559/fo477riMHz8+v/jFL/LVr341NTU1+dKXvpRjjjkmTzzxhFXyAADAlq0CAADAZuP73/9+Jck6X/369Wt1TL9+/Sqf+MQnWj6fNGlSpUuXLpXf//73rfb78Y9/XElSmTZtWsu2JJXGxsbKP//5z3XOtWLFisry5csrEydOrGy33XaVlStXtrp+165dK48++mirY0466aRKt27dKg8//PBaz3v33XdXklTe+973ttr+ox/9qJKkcv/997ds+8QnPtHqvf/qV7+qJKlMmDBhnbO/1sqVKyvLly+v3HPPPZUklT/+8Y8tXzv33HMrb/TX6AceeKCSpHLmmWcWX/P1fz6r/oyfeOKJVvut+l7cfffdlUqlUnnwwQcrSSq33nrrOs/fs2fPVudf5ZRTTqlstdVWlaeeeqrV9ksvvbSSpPLXv/61UqlUKk888UQlSWW33XarLFu2rNW+q772/e9/v2Xbqu/TxRdf3GrfMWPGVLp3797ys/HTn/60kqRy1VVXtdpv0qRJlSSVc889d53va9W1L7nkkrXuM2rUqEqSyrPPPtum97z33ntXmpubW/b73e9+V0lSueGGGyqVyqs/9zvttFNlv/32a/Uz/+STT1a6devW6udxbd/HVefYe++9KytWrGjZ/tJLL1V22GGHyvDhw1u27b///pW+fftWli5d2mq/7bbbbrWfzfb63W1oaKg8/fTTLdtmzZpVSVLp06dP5eWXX27Zfuutt1aSVG677bZ1Xg8AAGBz5xbxAAAAm6Hrrrsuv//971d7rVrpui533HFHBg0alH333TfNzc0tryOOOGK1W5Anybvf/e5ss802q53nl7/8ZQ477LA0Njama9eu6datW84555wsXLgwCxYsaLXvPvvskz322KPVtjvvvDPvete7MnDgwDec+X3ve99q50uSp556aq3H3HnnnUmSz372s+s89z/+8Y8cf/zx2XHHHVvexyGHHJIkeeSRR95wtmrZfffds8022+RLX/pSrr766jz88MPrdfwdd9yRd73rXdlpp51a/Rysel75Pffc02r/973vfenWrVvx+df0Z/bKK6+0/GysOv/IkSNb7ffRj350vd7HulRed0eH9X3PRx99dKs7JLz+5+7RRx/NM888k+OPP77VXR/69euX4cOHr3Gm138fV53jhBNOaLXifauttsp//Md/5IEHHsiSJUvy8ssv58EHH8wHPvCB1NXVtdrv2GOPXeO12uN3d999983OO+/c8vmq39dDDz201V0aVm1f1+8kAADAlsAt4gEAADZDAwcOzNChQ1fb3tjYmDlz5qzz2GeffTaPPfbYWmPp888/3+rzPn36rLbP7373u4wYMSKHHnpovvvd77Y8z/rWW2/NV77ylTQ1Nb3hOZ577rm85S1vWeesq2y33XatPq+vr0+S1a7z+vN37do1O+6441r3+de//pWDDjoo3bt3z4UXXpg99tgjPXr0yJw5c3Lcccet8/xrsuqW20888cR6HdcWjY2Nueeee/KVr3wlZ511Vl544YX06dMnn/70p3P22We/YQx/9tlnc/vtt2/Qz8G6vNGf2cKFC1NbW5ttt9221X6vfTTAhnrqqadSX1/fco31fc8l7yHJGn/Gdtxxx1aPIljl9d/HVedY0/d3p512ysqVK/PCCy+kUqmkUqms8fuztu9Ze/zuvv7PZ1XcX9v2V155ZY2zAAAAbCkEdgAAgE5m++23T0NDQ8uzsNf09dd67crcVW688cZ069Ytd9xxR7p3796y/dZbb13jOdd0jje/+c15+umn12Py9fPmN785K1asyPz589cah3/5y1/mmWeeyYwZM1pWrSfJiy++2KZr9unTJ3vvvXd+/vOfZ8mSJW16Dvuq7+fSpUtbbX99/E2SvffeOzfeeGMqlUr+9Kc/ZcqUKZk4cWIaGhpy5plnrvM622+/ffbZZ5985StfWePXd9ppp1afr+nPcENst912aW5uzj//+c9WsXb+/Pntcv65c+fmoYceyiGHHJLa2lf/88f6vuc3sirAr2nmtb2P138fV51j3rx5q+37zDPPpEuXLtlmm21SqVRSU1Ozxuetl14rWf/fXQAAAFpzi3gAAIBO5phjjsnjjz+e7bbbLkOHDl3tteuuu77hOWpqalJbW9vq9tlNTU35n//5n+I5jjrqqNx999159NFH2/I2is6fJFddddVa91kVIFetTF7lO9/5Tpuv++UvfzkvvPBCPv/5z692i/Lk1VXzP//5z9d6/Krv/5/+9KdW22+77ba1HlNTU5N3vOMd+cY3vpE3velN+cMf/tDytfr6+jWuxD/mmGPyl7/8Jbvtttsafw7WNzavr1X/oGHq1Kmttt94440bfO6mpqacfPLJaW5uzhlnnNGyvb3f84ABA9KnT5/ccMMNrf6sn3rqqdx3333F59h5551z/fXXtzrHyy+/nJtvvjnDhg1Ljx490rNnzwwdOjS33nprli1b1rLfv/71r9xxxx3FM7fH7y4AAEBnZgU7AABAJzN27NjcfPPNOfjgg/OFL3wh++yzT1auXJnZs2fn5z//eb74xS/mne985zrPcfTRR+eyyy7L8ccfn8985jNZuHBhLr300tVC9bpMnDgxd955Zw4++OCcddZZ2XvvvfPiiy/mrrvuyrhx47Lnnntu0Ps86KCDcsIJJ+TCCy/Ms88+m2OOOSb19fWZOXNmevTokdNOOy3Dhw/PNttsk1NPPTXnnntuunXrlh/+8If54x//2ObrfvjDH86Xv/zlXHDBBfnb3/6W0aNHZ7fddsuSJUvy29/+Nt/5zncyatSojBgxYo3H77///hkwYEBOP/30NDc3Z5tttslPfvKT/PrXv2613x133JErr7wyH/jAB/LWt741lUolt9xyS1588cUcfvjhLfvtvffemTFjRm6//fb06dMnW2+9dQYMGJCJEydm+vTpGT58eD7/+c9nwIABeeWVV/Lkk09m2rRpufrqq4tv4d8WRx55ZA488MB88YtfzOLFizNkyJDcf//9ue6665Kk1fPI12X27Nl54IEHsnLlyixatCgzZ87MNddck6eeeipf//rXW32f2/s9d+nSJRdccEFOPvnkfPCDH8ynP/3pvPjiiznvvPPW+WiC15/j4osvzsc+9rEcc8wxOeWUU7J06dJccsklefHFF3PRRRe1mv/oo4/OEUcckf/8z//MihUrcskll2SrrbbKP//5z6LrtcfvLgAAQGcmsAMAAHQyPXv2zL333puLLrookydPzhNPPJGGhobssssuOeyww4pWsL/73e/ONddck6997Ws59thjs/POO+fTn/50dthhh4wePbpojp133jm/+93vcu655+aiiy7KwoUL8+Y3vzn//u//vtrzndtqypQp2W+//fK9730vU6ZMSUNDQ/baa6+cddZZSV69PfdPf/rTfPGLX8zHP/7x9OzZM+9///szderU7Lfffm2+7sSJE3PYYYflW9/6ViZMmJDnn38+DQ0Nefvb355x48bllFNOWeuxXbt2ze23357Pfe5zOfXUU1NfX5+PfOQj+a//+q8cffTRLfu97W1vy5ve9KZcfPHFeeaZZ1JXV5cBAwZkypQp+cQnPtGy3xVXXJHPfvaz+chHPpIlS5bkkEMOyYwZM9KnT588+OCDueCCC3LJJZfk6aefztZbb53+/fvnyCOPzDbbbNPm91+iS5cuuf322/PFL34xF110UZYtW5YDDzwwP/jBD3LAAQfkTW96U9F5vvWtb+Vb3/pWunbtml69euWtb31rjj322Hz605/OXnvt1WrfjfGeV/28f+1rX8txxx2XXXfdNWeddVbuueeezJgxo+gcxx9/fHr27JlJkyZl1KhR6dq1aw444IDcfffdGT58eMt+Rx55ZG6++eacc845GTVqVHbccceMGTMmzzzzTPEK9Pb43QUAAOjMaiprul8dAAAAQBVcf/31+djHPpbf/OY3reIya7Z8+fLsu+++2Xnnndf56AEAAADahxXsAAAAQFXccMMNmTt3bvbee+906dIlDzzwQC655JIcfPDB4vpajB49Oocffnj69OmT+fPn5+qrr84jjzySK664otqjAQAAdAoCOwAAAFAVW2+9dW688cZceOGFefnll9OnT5988pOfzIUXXljt0Tqsl156Kaeffnqee+65dOvWLfvtt1+mTZuWww47rNqjAQAAdApuEQ8AAAAAAAAABbpUewAAAAAAAAAA2BwI7AAAAAAAAABQoNM9g33lypV55plnsvXWW6empqba4wAAAAAAAABQZZVKJS+99FJ22mmndOmy9nXqnS6wP/PMM+nbt2+1xwAAAAAAAACgg5kzZ07e8pa3rPXrnS6wb7311kle/cb06tWrytMAAAAAAAAAUG2LFy9O3759W3ry2nS6wL7qtvC9evUS2AEAAAAAAABo8UaPGV/7zeMBAAAAAAAAgBYCOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFqh7Yr7zyyvTv3z/du3fPkCFDcu+9965z/6VLl2bChAnp169f6uvrs9tuu+Waa67ZRNMCAAAAAAAA0FnVVvPiU6dOzdixY3PllVfmwAMPzHe+850cddRRefjhh7PLLrus8ZiRI0fm2Wefzfe+973svvvuWbBgQZqbmzfx5AAAAAAAAAB0NjWVSqVSrYu/853vzH777ZerrrqqZdvAgQPzgQ98IJMmTVpt/7vuuisf+chH8o9//CPbbrtt0TWWLl2apUuXtny+ePHi9O3bN4sWLUqvXr02/E0AAAAAAAAAsFlbvHhxGhsb37AjV+0W8cuWLctDDz2UESNGtNo+YsSI3HfffWs85rbbbsvQoUNz8cUXZ+edd84ee+yR008/PU1NTWu9zqRJk9LY2Njy6tu3b7u+DwAAAAAAAAA6h6rdIv7555/PihUr0rt371bbe/funfnz56/xmH/84x/59a9/ne7du+cnP/lJnn/++YwZMyb//Oc/1/oc9vHjx2fcuHEtn69awQ4A0NlVKpU0LV9R7TEAgC1AQ7euqampqfYYAAAAG11Vn8GeZLW/fFUqlbX+hWzlypWpqanJD3/4wzQ2NiZJLrvssnzoQx/Kt7/97TQ0NKx2TH19ferr69t/cACAzVilUsmHrr4/Dz31QrVHAQC2AEP7bZObTh0msgMAAFu8qt0ifvvtt0/Xrl1XW62+YMGC1Va1r9KnT5/svPPOLXE9efWZ7ZVKJU8//fRGnRcAYEvStHyFuA4AtJsHn3rBnXEAAIBOoWor2Ovq6jJkyJBMnz49H/zgB1u2T58+Pe9///vXeMyBBx6Ym266Kf/617+y1VZbJUn+7//+L126dMlb3vKWTTI3AMCW5sGzD0uPuq7VHgMA2AwtWbYiQy/832qPAQAAsMlU9Rbx48aNywknnJChQ4dm2LBhmTx5cmbPnp1TTz01yavPT587d26uu+66JMnxxx+fCy64IJ/61Kdy/vnn5/nnn8//9//9fznppJPWeHt4AADeWI+6rulRV/UnBwEAAAAAdHhV/S+po0aNysKFCzNx4sTMmzcvgwYNyrRp09KvX78kybx58zJ79uyW/bfaaqtMnz49p512WoYOHZrtttsuI0eOzIUXXlittwAAAAAAAABAJ1H1pUpjxozJmDFj1vi1KVOmrLZtzz33zPTp0zfyVAAAAAAAAADQWpdqDwAAAAAAAAAAmwOBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFqh7Yr7zyyvTv3z/du3fPkCFDcu+996513xkzZqSmpma119/+9rdNODEAAAAAAAAAnVFVA/vUqVMzduzYTJgwITNnzsxBBx2Uo446KrNnz17ncY8++mjmzZvX8nrb2962iSYGAAAAAAAAoLOqamC/7LLLMnr06Jx88skZOHBgLr/88vTt2zdXXXXVOo/bYYcdsuOOO7a8unbtuokmBgAAAAAAAKCzqlpgX7ZsWR566KGMGDGi1fYRI0bkvvvuW+exgwcPTp8+ffKe97wnd9999zr3Xbp0aRYvXtzqBQAAAAAAAADrq2qB/fnnn8+KFSvSu3fvVtt79+6d+fPnr/GYPn36ZPLkybn55ptzyy23ZMCAAXnPe96TX/3qV2u9zqRJk9LY2Njy6tu3b7u+DwAAAAAAAAA6h9pqD1BTU9Pq80qlstq2VQYMGJABAwa0fD5s2LDMmTMnl156aQ4++OA1HjN+/PiMGzeu5fPFixeL7AAAAAAAAACst6qtYN9+++3TtWvX1VarL1iwYLVV7etywAEH5O9///tav15fX59evXq1egEAAAAAAADA+qpaYK+rq8uQIUMyffr0VtunT5+e4cOHF59n5syZ6dOnT3uPBwAAAAAAAACtVPUW8ePGjcsJJ5yQoUOHZtiwYZk8eXJmz56dU089Ncmrt3efO3durrvuuiTJ5Zdfnl133TVvf/vbs2zZsvzgBz/IzTffnJtvvrmabwMAAAAAAACATqCqgX3UqFFZuHBhJk6cmHnz5mXQoEGZNm1a+vXrlySZN29eZs+e3bL/smXLcvrpp2fu3LlpaGjI29/+9vz0pz/Ne9/73mq9BQAAAAAAAAA6iZpKpVKp9hCb0uLFi9PY2JhFixZ5HjsA0GktWdacvc75WZLk4YlHpEddVf/dJQCwmfL/KQAAgC1FaUeu2jPYAQAAAAAAAGBzIrADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFqh7Yr7zyyvTv3z/du3fPkCFDcu+99xYd95vf/Ca1tbXZd999N+6AAAAAAAAAAJAqB/apU6dm7NixmTBhQmbOnJmDDjooRx11VGbPnr3O4xYtWpQTTzwx73nPezbRpAAAAAAAAAB0dlUN7JdddllGjx6dk08+OQMHDszll1+evn375qqrrlrncaecckqOP/74DBs2bBNNCgAAAAAAAEBnV7XAvmzZsjz00EMZMWJEq+0jRozIfffdt9bjvv/97+fxxx/PueeeW3SdpUuXZvHixa1eAAAAAAAAALC+qhbYn3/++axYsSK9e/dutb13796ZP3/+Go/5+9//njPPPDM//OEPU1tbW3SdSZMmpbGxseXVt2/fDZ4dAAAAAAAAgM6nqreIT5KamppWn1cqldW2JcmKFSty/PHH5/zzz88ee+xRfP7x48dn0aJFLa85c+Zs8MwAAAAAAAAAdD5ly8A3gu233z5du3ZdbbX6ggULVlvVniQvvfRSHnzwwcycOTOf+9znkiQrV65MpVJJbW1tfv7zn+fd7373asfV19envr5+47wJAAAAAAAAADqNqq1gr6ury5AhQzJ9+vRW26dPn57hw4evtn+vXr3y5z//ObNmzWp5nXrqqRkwYEBmzZqVd77znZtqdAAAAAAAAAA6oaqtYE+ScePG5YQTTsjQoUMzbNiwTJ48ObNnz86pp56a5NXbu8+dOzfXXXddunTpkkGDBrU6focddkj37t1X2w4AAAAAAAAA7a2qgX3UqFFZuHBhJk6cmHnz5mXQoEGZNm1a+vXrlySZN29eZs+eXc0RAQAAAAAAACBJUlOpVCrVHmJTWrx4cRobG7No0aL06tWr2uMAAFTFkmXN2eucnyVJHp54RHrUVfXfXQIAmyn/nwIAANhSlHbkqj2DHQAAAAAAAAA2JwI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoEBttQcAAACAzqpSqaSpuanaY0CbLVm+4jUfNyU1Xas4DWy4htqG1NTUVHsMAAA6MIEdAAAAqqBSqeTEO0/MrOdmVXsUaLPKym5JLkiSHPqjQ1LTZXl1B4INNHiHwbn2yGtFdgAA1kpgBwAAgCpoam4S19ns1XRZnq0HnlntMaDdzFwwM03NTenRrUe1RwEAoIMS2AEAAKDKZoyckYbahmqPAdBpNTU35dAfHVrtMQAA2AwI7AAAAFBlDbUNVksCAADAZqBLtQcAAAAAAAAAgM2BwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQoLbaAwBAkUolWb6k2lPAlmPZitd8vCRJ16qNAlukbj2SmppqTwEAAABAOxPYAej4KpXkmiOSOb+t9iSw5ajUJ/n+qx9fsntSs7Sq48AWp+8ByUl3iewAAAAAWxiBHYCOb/kScR3aWY+apXmy+/HVHgO2XHMeePV/v+p6VnsSAAAAANqRwA7A5uX0x5K6HtWeAgDWbNmS5NLdqz0FAAAAABuJwA7A5qWuh9WAAAAAAABAVXSp9gAAAAAAAAAAsDkQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAgQ0K7MuWLcujjz6a5ubm9poHAAAAAAAAADqkNgX2JUuWZPTo0enRo0fe/va3Z/bs2UmSz3/+87nooovadUAAAAAAAAAA6AjaFNjHjx+fP/7xj5kxY0a6d+/esv2www7L1KlT2204AAAAAAAAAOgoatty0K233pqpU6fmgAMOSE1NTcv2vfbaK48//ni7DQcAAAAAAAAAHUWbVrA/99xz2WGHHVbb/vLLL7cK7gAAAAAAAACwpWhTYN9///3z05/+tOXzVVH9u9/9boYNG9Y+kwEAAAAAAABAB9KmW8RPmjQpRx55ZB5++OE0NzfniiuuyF//+tfcf//9ueeee9p7RgAAAAAAAACoujatYB8+fHh+85vfZMmSJdltt93y85//PL17987999+fIUOGtPeMAAAAAAAAAFB1bVrBniR77713rr322vacBQAAAAAAAAA6rDatYJ82bVp+9rOfrbb9Zz/7We68884NHgoAAAAAAAAAOpo2BfYzzzwzK1asWG17pVLJmWeeucFDAQAAAAAAAEBH06bA/ve//z177bXXatv33HPPPPbYYxs8FAAAAAAAAAB0NG0K7I2NjfnHP/6x2vbHHnssPXv23OChAAAAAAAAAKCjaVNgf9/73pexY8fm8ccfb9n22GOP5Ytf/GLe9773tdtwAAAAAAAAANBRtCmwX3LJJenZs2f23HPP9O/fP/3798/AgQOz3Xbb5dJLL23vGQEAAAAAAACg6mrbclBjY2Puu+++TJ8+PX/84x/T0NCQffbZJwcffHB7zwcAAAAAAAAAHUKbAnuS1NTUZMSIERkxYkR7zgMAAAAAAAAAHVKbA/svfvGL/OIXv8iCBQuycuXKVl+75pprNngwAAAAAAAAAOhI2hTYzz///EycODFDhw5Nnz59UlNT095zAQAAAAAAAECH0qbAfvXVV2fKlCk54YQT2nseAAAAAAAAAOiQurTloGXLlmX48OHtPQsAAAAAAAAAdFhtCuwnn3xyrr/++vaeBQAAAAAAAAA6rDbdIv6VV17J5MmT87//+7/ZZ5990q1bt1Zfv+yyy9plOAAAAAAAAADoKNoU2P/0pz9l3333TZL85S9/afW1mpqaDR4KAAAAAAAAADqaNgX2u+++u73nAAAAAAAAAIAOrU3PYAcAAAAAAACAzqZNK9iT5Pe//31uuummzJ49O8uWLWv1tVtuuWWDBwMAAAAAAACAjqRNK9hvvPHGHHjggXn44Yfzk5/8JMuXL8/DDz+cX/7yl2lsbGzvGQEAAAAAAACg6toU2L/61a/mG9/4Ru64447U1dXliiuuyCOPPJKRI0dml112ae8ZAQAAAAAAAKDq2hTYH3/88Rx99NFJkvr6+rz88supqanJF77whUyePLldBwQAAAAAAACAjqBNgX3bbbfNSy+9lCTZeeed85e//CVJ8uKLL2bJkiXtNx0AAAAAAAAAdBC1bTnooIMOyvTp07P33ntn5MiR+c///M/88pe/zPTp0/Oe97ynvWcEAAAAAAAAgKprU2D/r//6r7zyyitJkvHjx6dbt2759a9/neOOOy5f/vKX23VAAAAAAAAAAOgI2hTYt91225aPu3TpkjPOOCNnnHFGuw0FAAAAAAAAAB1Nm57B3rVr1yxYsGC17QsXLkzXrl03eCgAAAAAAAAA6GjaFNgrlcoaty9dujR1dXUbNBAAAAAAAAAAdETrdYv4b37zm0mSmpqa/Pd//3e22mqrlq+tWLEiv/rVr7Lnnnu274QAAAAAAAAA0AGsV2D/xje+keTVFexXX311q9vB19XVZdddd83VV1/dvhMCAAAAAAAAQAewXoH9iSeeSJK8613vyi233JJtttlmowwFAAAAAAAAAB1Nm57Bfvfdd7eK6ytWrMisWbPywgsvtNtgAAAAAAAAANCRtCmwjx07Nt/73veSvBrXDz744Oy3337p27dvZsyYsV7nuvLKK9O/f/907949Q4YMyb333rvWfX/961/nwAMPzHbbbZeGhobsueeeLbetBwAAAAAAAICNqU2B/aabbso73vGOJMntt9+eJ598Mn/7298yduzYTJgwofg8U6dObTlm5syZOeigg3LUUUdl9uzZa9y/Z8+e+dznPpdf/epXeeSRR3L22Wfn7LPPzuTJk9vyNgAAAAAAAACgWJsC+8KFC7PjjjsmSaZNm5YPf/jD2WOPPTJ69Oj8+c9/Lj7PZZddltGjR+fkk0/OwIEDc/nll6dv37656qqr1rj/4MGD89GPfjRvf/vbs+uuu+bjH/94jjjiiHWuel+6dGkWL17c6gUAAAAAAAAA66tNgb137955+OGHs2LFitx111057LDDkiRLlixJ165di86xbNmyPPTQQxkxYkSr7SNGjMh9991XdI6ZM2fmvvvuyyGHHLLWfSZNmpTGxsaWV9++fYvODQAAAAAAAACv1abA/qlPfSojR47MoEGDUlNTk8MPPzxJ8tvf/jZ77rln0Tmef/75rFixIr179261vXfv3pk/f/46j33LW96S+vr6DB06NJ/97Gdz8sknr3Xf8ePHZ9GiRS2vOXPmFM0HAAAAAAAAAK9V25aDzjvvvAwaNChz5szJhz/84dTX1ydJunbtmjPPPHO9zlVTU9Pq80qlstq217v33nvzr3/9Kw888EDOPPPM7L777vnoRz+6xn3r6+tb5gMAAAAAAACAtmpTYE+SD33oQ6tt+8QnPlF8/Pbbb5+uXbuutlp9wYIFq61qf73+/fsnSfbee+88++yzOe+889Ya2AEAAAAAAACgPRQH9m9+85v5zGc+k+7du+eb3/zmOvf9/Oc//4bnq6ury5AhQzJ9+vR88IMfbNk+ffr0vP/97y8dK5VKJUuXLi3eHwAAAAAAAADaojiwf+Mb38jHPvaxdO/ePd/4xjfWul9NTU1RYE+ScePG5YQTTsjQoUMzbNiwTJ48ObNnz86pp56a5NXnp8+dOzfXXXddkuTb3/52dtlll5bnvP/617/OpZdemtNOO630bQAAAAAAAABAmxQH9ieeeGKNH2+IUaNGZeHChZk4cWLmzZuXQYMGZdq0aenXr1+SZN68eZk9e3bL/itXrsz48ePzxBNPpLa2NrvttlsuuuiinHLKKe0yDwAAAAAAAACsTXFgHzduXNF+NTU1+frXv148wJgxYzJmzJg1fm3KlCmtPj/ttNOsVgcAAAAAAACgKooD+8yZM1t9/tBDD2XFihUZMGBAkuT//u//0rVr1wwZMqR9JwQAAAAAAACADqA4sN99990tH1922WXZeuutc+2112abbbZJkrzwwgv51Kc+lYMOOqj9pwQAAAAAAACAKuvSloO+/vWvZ9KkSS1xPUm22WabXHjhhet1e3gAAAAAAAAA2Fy0KbAvXrw4zz777GrbFyxYkJdeemmDhwIAAAAAAACAjqZNgf2DH/xgPvWpT+XHP/5xnn766Tz99NP58Y9/nNGjR+e4445r7xkBAAAAAAAAoOqKn8H+WldffXVOP/30fPzjH8/y5ctfPVFtbUaPHp1LLrmkXQcEAAAAAAAAgI6gTYG9R48eufLKK3PJJZfk8ccfT6VSye67756ePXu293wAAAAAAAAA0CG0KbCv0rNnz+yzzz7tNQsAAAAAAAAAdFhtegY7AAAAAAAAAHQ2AjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFKit9gAAAABVVakky5e0z7mWLVnzxxuqW4+kpqb9zgcAAABAmwjsAABA51WpJNcckcz5bfuf+9Ld2+9cfQ9ITrpLZAcAAACoMreIBwAAOq/lSzZOXG9vcx5ov1X2AAAAALSZFewAAABJcvpjSV2Pak/R2rIl7bsSHgAAAIANIrADAAAkr8b1up7VngIAAACADswt4gEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABSoemC/8sor079//3Tv3j1DhgzJvffeu9Z9b7nllhx++OF585vfnF69emXYsGH52c9+tgmnBQAAAAAAAKCzqmpgnzp1asaOHZsJEyZk5syZOeigg3LUUUdl9uzZa9z/V7/6VQ4//PBMmzYtDz30UN71rnfl2GOPzcyZMzfx5AAAAAAAAAB0NlUN7JdddllGjx6dk08+OQMHDszll1+evn375qqrrlrj/pdffnnOOOOM7L///nnb296Wr371q3nb296W22+/fRNPDgAAAAAAAEBnU7XAvmzZsjz00EMZMWJEq+0jRozIfffdV3SOlStX5qWXXsq222671n2WLl2axYsXt3oBAAAAAAAAwPqqWmB//vnns2LFivTu3bvV9t69e2f+/PlF5/j617+el19+OSNHjlzrPpMmTUpjY2PLq2/fvhs0NwAAAAAAAACdU1VvEZ8kNTU1rT6vVCqrbVuTG264Ieedd16mTp2aHXbYYa37jR8/PosWLWp5zZkzZ4NnBgAAAAAAAKDzqa3Whbfffvt07dp1tdXqCxYsWG1V++tNnTo1o0ePzk033ZTDDjtsnfvW19envr5+g+cFAAAAAAAAoHOr2gr2urq6DBkyJNOnT2+1ffr06Rk+fPhaj7vhhhvyyU9+Mtdff32OPvrojT0mAAAAAAAAACSp4gr2JBk3blxOOOGEDB06NMOGDcvkyZMze/bsnHrqqUlevb373Llzc9111yV5Na6feOKJueKKK3LAAQe0rH5vaGhIY2Nj1d4HAAAAAAAAAFu+qgb2UaNGZeHChZk4cWLmzZuXQYMGZdq0aenXr1+SZN68eZk9e3bL/t/5znfS3Nycz372s/nsZz/bsv0Tn/hEpkyZsqnHBwAAAAAAAKATqWpgT5IxY8ZkzJgxa/za66P5jBkzNv5AAAAAAAAAALAGVXsGOwAAAAAAAABsTgR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQoLbaAwAAAAB0RJVKJU3NTdUeA9gEXvu77vceOo+G2obU1NRUewwANjMCOwAAAMDrVCqVnHjniZn13KxqjwJsYof+6NBqjwBsIoN3GJxrj7xWZAdgvbhFPAAAAMDrNDU3iesAsIWbuWCmu1YAsN6sYAcAAABYhxkjZ6ShtqHaYwAA7aSpucndKgBoM4EdAAAAYB0aahvSo1uPao8BAABAB+AW8QAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAAChQW+0BgLWoVJLlS6o9BXQMy5as+WPo7Lr1SGpqqj0FAAAAAECnIbBDR1SpJNcckcz5bbUngY7n0t2rPQF0HH0PSE66S2QHAAAAANhE3CIeOqLlS8R1AN7YnAfc7QQAAAAAYBOygh06utMfS+p6VHsKADqSZUvczQEAAAAAoAoEdujo6nokdT2rPQUAAAAAAAB0em4RDwAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAArUVnsAAAAAAAA2jUqlkqbmpmqPAVX12t8Bvw90dg21Dampqan2GLBZEdgBAAA2hkolWb5kw86xbMmaP26rbj0S/+EEADqtSqWSE+88MbOem1XtUaDDOPRHh1Z7BKiqwTsMzrVHXiuyw3oQ2AEAANpbpZJcc0Qy57ftd85Ld9/wc/Q9IDnpLpEdADqppuYmcR2AVmYumJmm5qb06Naj2qPAZkNgBwAAaG/Ll7RvXG8vcx54dba6ntWeBACoshkjZ6ShtqHaYwBQJU3NTe7gAG0ksAMAAGxMpz+W1FV5JcCyJe2zAh4A2GI01DZYrQgA0AYCOwAAwMZU18OKcQAAAIAtRJdqDwAAAAAAAAAAmwOBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQoLbaAwAAm6FKJVm+pNpTdF7Llqz5Yzatbj2SmppqTwEAAAAAbEICOwCwfiqV5Jojkjm/rfYkJMmlu1d7gs6r7wHJSXeJ7AAAAADQibhFPACwfpYvEdchSeY84E4OAAAAANDJWMEOALTd6Y8ldT2qPQVsWsuWuHMAAAAAAHRSAjsA0HZ1PZK6ntWeAgAAAAAANgm3iAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAK1FZ7AAAAAAAAANgcVSqVNDU3VXuM9fbamTfH+VdpqG1ITU1NtcegkxHYAQAAAAAAYD1VKpWceOeJmfXcrGqPskEO/dGh1R6hzQbvMDjXHnmtyM4m5RbxAAAAAAAAsJ6amps2+7i+uZu5YOZmvQKfzZMV7AAAAAAAALABZoyckYbahmqP0Wk0NTdt1ivv2bwJ7AAAAAAAALABGmob0qNbj2qPAWwCbhEPAAAAAAAAAAUEdgAAAAAAAAAoILADAAAAAAAAQAGBHQAAAAAAAAAKCOwAAAAAAAAAUEBgBwAAAAAAAIACAjsAAAAAAAAAFBDYAQAAAAAAAKCAwA4AAAAAAAAABQR2AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQQGAHAAAAAAAAgAICOwAAAAAAAAAUENgBAAAAAAAAoIDADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFCg6oH9yiuvTP/+/dO9e/cMGTIk995771r3nTdvXo4//vgMGDAgXbp0ydixYzfdoAAAAAAAAAB0alUN7FOnTs3YsWMzYcKEzJw5MwcddFCOOuqozJ49e437L126NG9+85szYcKEvOMd79jE0wIAAAAAAADQmVU1sF922WUZPXp0Tj755AwcODCXX355+vbtm6uuumqN+++666654oorcuKJJ6axsXETTwsAAAAAAABAZ1a1wL5s2bI89NBDGTFiRKvtI0aMyH333ddu11m6dGkWL17c6gUAAAAAAAAA66tqgf3555/PihUr0rt371bbe/funfnz57fbdSZNmpTGxsaWV9++fdvt3AAAAAAAAAB0HlW9RXyS1NTUtPq8Uqmstm1DjB8/PosWLWp5zZkzp93ODQAAAAAAAEDnUVutC2+//fbp2rXraqvVFyxYsNqq9g1RX1+f+vr6djsfAAAAAAAAAJ1T1Vaw19XVZciQIZk+fXqr7dOnT8/w4cOrNBUAAAAAAAAArFnVVrAnybhx43LCCSdk6NChGTZsWCZPnpzZs2fn1FNPTfLq7d3nzp2b6667ruWYWbNmJUn+9a9/5bnnnsusWbNSV1eXvfbaqxpvAQAAAAAAAIBOoqqBfdSoUVm4cGEmTpyYefPmZdCgQZk2bVr69euXJJk3b15mz57d6pjBgwe3fPzQQw/l+uuvT79+/fLkk09uytEBAAAAAAAA6GSqGtiTZMyYMRkzZswavzZlypTVtlUqlY08EQAAAAAAAACsrmrPYAcAAAAAAACAzYnADgAAAAAAAAAFBHYAAAAAAAAAKCCwAwAAAAAAAEABgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAUEdgAAAAAAAAAoUFvtAQAAAFgPlUqyfMn6HbNsyZo/LtWtR1JTs/7HAQAAAGxhBHYAAIDNRaWSXHNEMue3bT/Hpbuv/zF9D0hOumuLj+yVSiVNzU2b7HqvvdamvG5DbUNqtvA/SwAAANhYBHYAAIDNxfIlGxbX22rOA69eu67npr/2JlKpVHLinSdm1nOzqnL9Q3906Ca71uAdBufaI68V2QEAAKANBHYAAIDN0emPJXU9Nu41li1p24r3zVBTc1PV4vqmNnPBzDQ1N6VHt4388wMAAABbIIEdAABgc1TXY4teUV5NM0bOSENtQ7XHaHdNzU2bdKU8AAAAbIkE9s6iUnn1lo5sHpYtWfPHdHzdemzxzyYFANjSNdQ2WN0NAAAArJHA3hlUKsk1R1TnWY1suE5yS84tRt8DkpPuEtkBAKCdVCqVNDU3bfLrvvaa1bj+Kg21Danx9wsAAIAOQ2DvDJYvEddhU5nzwKu/c27XCgAAG6xSqeTEO0/MrOdmVXWOat5af/AOg3PtkdeK7AAAAB2EwN7ZnP7Yq89qBNrXsiXuNgAAAO2sqbmp6nG92mYumJmm5iaPLQAAAOggBPbOpq6HlbUAAABsdmaMnJGG2oZqj7HJNDU3VXXlPAAAAGsmsAMAAAAdXkNtg1XcAAAAVF2Xag8AAAAAAAAAAJsDgR0AAAAAAAAACgjsAAAAAAAAAFBAYAcAAAAAAACAAgI7AAAAAAAAABQQ2AEAAAAAAACggMAOAAAAAAAAAAVqqz0AAAAAAAAA0D4qlUqampuqPcZG9dr3t6W/1yRpqG1ITU1Ntcfg/09gBwAAAAAAgC1ApVLJiXeemFnPzar2KJvMoT86tNojbHSDdxica4+8VmTvINwiHgAAAAAAALYATc1NnSqudxYzF8zsFCv1NxdWsAMAAAAAAMAWZsbIGWmobaj2GGyApuamTrFCf3MjsAMAAAAAAMAWpqG2IT269aj2GLDFcYt4AAAAAAAAACggsAMAAAAAAABAAYEdAAAAAAAAAAoI7AAAAAAAAABQoLbaAwAAAABAZ1epVNLU3FTtMdjCvfZnzM8bm0JDbUNqamqqPQYAtCuBHQAAAACqqFKp5MQ7T8ys52ZVexQ6kUN/dGi1R6ATGLzD4Fx75LUiOwBbFLeIBwAAAIAqampuEteBLdLMBTPdLQGALY4V7AAAAADQQcwYOSMNtQ3VHgNggzQ1N7lLAgBbLIEdAAAAADqIhtqG9OjWo9pjAAAAayGwAwDQMVUqyfIl1Z5idcuWrPnjjqZbj8RzDgEAAACgXQnsAAB0PJVKcs0RyZzfVnuSdbt092pPsHZ9D0hOuktkBwAAAIB21KXaAwAAwGqWL+n4cb2jm/NAx7wDAAAAAABsxqxgBwCgYzv9saTOc0iLLVvSsVfWAwAAAMBmTGAHAKBjq+uR1PWs9hQAAAAA8P9r797joyruxo9/g9wSAohcRIEkVIzGJFDkGqwIFLlZq6JgL48oPPLor1ZEiuKtLZQqvWhL6632USqXWlFUWizQKpcoj4IECChgBREDgtwpmIRA4Pv7gyf7bC67e86Zszu72c/79eL1CtmdzJw5c2bmzJyZA7BFPAAAAAAAAAAAAAAATrCCHUB8UE3s98SeLKv750TUKE0kJcV2KgAAAAAAAAAAAOIOE+wA7FMVmTVUZNca2ynxR6K/97ZTX5FxS5lkBwAAAAAAAAAAqIEt4gHYd6qs/kyu1we7Vif2bgIAAAAAAAAAAABRwgp2APFl8naRxmm2U5GcTpYl/up7AAAAAAAAAACAKGKCHUB8aZwm0riZ7VQAAAAAAAAAAAAAtTDBDgAAAADJQtXdq2BOltX9sxON0kRSUtyFAQAAAAAAiHNMsAMAAABAMlAVmTVUZNcab+HdvkqmU1+RcUuZZAcAAAAAAPVKA9sJAAAAAADEwKky75PrXuxa7W61PAAAAAAAQAJgBTsAAAAAJJvJ20Uap0Xnb58sc7/aHQAAAAAAIEEwwQ4AAAAAyaZxmkjjZrZTAQAAAAAAkHCYYAcAAAAAAAAAoAZVlfLKctvJSEjB+UYemkltmCopKSm2kwEACMIEOwAAAAAAAAAAQVRVxiwZI8UHim0nJeENeGWA7SQktO7tusvsYbOZZAeAONLAdgIAAAAAAAAAAIgn5ZXlTK4jLmzYv4FdAAAgzrCCHQAAAAAAAACAEFaOXimpDVNtJwNJpryynNX/ABCnmGAHAAAAAK9URU6V1f79ybK6fw7WKE2EbR4BAADiXmrDVElrlGY7GQAAIE4wwQ4AAAAAXqiKzBoqsmtN+O893qXu33fqKzJuKZPsMKaqjrYNDf6Om21GUxum8s5PAAAAAAD+FxPsAAAAAODFqbLIk+vh7Fp99m80buZfmpB0VFXGLBnj+h2xbrYb7d6uu8weNptJdgAAAAAAhAl2AAAAADA3ebtIY4fbhp4sC72qHXCpvLLc9eS6Wxv2b5DyynK2xg3B6Q4CbnndccApdiYAAAAAAG+YYAcAAAAAU43TWIkO61aOXimpDVN9+3vlleWuVronI687CLgVjfPAzgQAAAAA4A0T7AAAAAAA1AOpDVNZZR5jsdhBIFrYmQAAAAAAvGGC3Q+qZ9+dGK9OltX9czxqlCbC0/MAAAAAgATj9w4C0cLOBAAAAABghgl2U6ois4aK7FpjOyXOxPu7Hjv1FRm3lEl2AAAAAEBCYQcBAAAAAEgODWwnIOGdKkucyfVEsGt1fO8GAAAAAAAAAAAAACBpsYLdT5O3izTmaXVPTpbF/+p6AAAAL2L9OiHbrwfilT8AAAAAAACox5hg91PjNJHGzWynAgAAAPHC9uuEbDzAyCt/AAAAAAAAUI8xwQ4AgA2xXtHqJ9urY/3ESltEWzK+TqjqlT88eAoAAAAAAIB6iAl2AABizfaKVj8l+us9WGmLWKrvrxPilT8AAAAAAABIAkywAwAQa8m4ojVesdIWscTrhAAgQFWlvLI84veCv+Pk+yIiqQ1TJYWH5wAAAAAAUcIEOwAANtX3Fa3xipW2AABYo6oyZskYKT5Q7CrcgFcGOPpe93bdZfaw2UyyAwAAT5w+CBhtXh40jDYeZER9Fy/Xf7B4rAuCJWu9wAQ7AAA2saIVAICocDswYjJokawDCl6VV5a7nlx3Y8P+DVJeWS5pjXiIEQAAuOP1QcBoc/qgYbTxICPqs3i9/oPFS10QLFnrBSbYAQAAAAD1iunAiNtBi2QdUPDDytErJbVhqi9/q7yyPC4HnAAAQOKI9oOAiY4HGVGfcf17k6z1AhPsAAAAAIB6JdYDI8k6oOCH1Iap5BsAAIhLfj4ImOh4kBHJhus/smSvF5hgBwAAAADUW9EcGEn2AQUAAID6jAcBYZvX94H78c7uZH8NFtc/ImGCHQAAAABQbzEwAgAAACDR+PU+cK8PBPMaLCC8BrYTAAAAAAAAAAAAAOAs2+8Dr3oNFoC6sYIdAAAAAAAAAAAAiEOxfB84r8ECnGGCHQAAAAAAAAAAAIhDvPYKiD9sEQ8AAAAAAAAAAAAAgAOsYAcAAAAAAAAAAACAJKSqUl5Z7ipM8PfdhhU5uzNDSkqK63Dxggl2AAAQfaoip8psp+L/nCyr+2fbGqWJJHDHEgAAIB54GSC0zXSA0qZEHxwFAABIZqoqY5aMkeIDxZ7/xoBXBrgO071dd5k9bHbC9iOZYAcAANGlKjJrqMiuNbZTUrfHu9hOwf/p1Fdk3FIm2QEAADzyY4DQNi8DlDYl+uAoAABAMiuvLLfSd96wf4OUV5ZLWqO0mMftBybYAQBAdJ0qi9/J9Xiza/XZ/GrczHZKAAAAEpKtAcJkluiDowAAADhr5eiVktowNapxlFeWJ9wDpXVhgh0AAMTO5O0ijRl4q+VkWXytpPeT19cDmG7jz3b7AIB6zus26H5sRZ4oW4LHYoAwmdWXwVEAAACcldowlYcmHWKCHQDqAz/eb+33O6mZ3EJdGqexOjuZ+PV6AC8PH7DdPgCgHvNrG3Svk6OJsiU4A4TVRfPd9NH4u4nyIAcAAACSDxPsqJsfk3Vu+D2x5xQTgKgPovF+az9W0jK5BcDm6wHYbh+AAaeTUF5WAjNhBD/Y3gadLcETT7TfTR+NleyJ8iAHAAAAkg8T7DW5nVg2mRiO18ndaEzWuRHLLXKZAER9EK/vt2ZyC0CwWL0eoD5vtw8gJrxOQjmdXGLCCH6L5TbobAmeuGw/lOEFD3IAgHPR3KVExJ9XzDjFA6kAEgET7MFMJ5bdDubG6+RuvE7WRQMTgKhv/J7AUhU55bLTfKpM5Hddz/7Me5MBVOH1AEDic/owspeHkOOo/Y/2JBQTRvAb26DDrXh/Nz0PciS3aE8SuhHLCUU3mHxETdHepaSmaNfRPJAKIBEwwR4s1hPLiTC5G6vVZrHG6jbUV35OYPmxmwXvTQYAoH7w2i9w2heI0/bfz0koJowAxAseykC8ivUkoRvx1IYz+YiaEnGXknB4IBVAImCCPZRoTiwn0uQuq82A5GVrN4tEePgIAJIBr05CsGj3C+K0/WcSCgCA2Klvk4TRwuQjwon3XUrC4YHU2Am3W4iT3TvYSQNggj00JpaB6twOsrthMiDvFAP3ZmKxm0UiPXwEAPUdr05COH72C2j/AQBAHRJ5kjBamHyEEzwgikjc7BYSqs5hJw2ACXbEu2hN6jKh644fW4U7Fa0BVgbuzfDQEYB4E6qP4LSN99pOx2pVt+1+BK9OQjj0CwAgqcT6ndg233vNirz4wSQhAESHH7uFsJMGwAQ74lmsJnWZ0I3M1lbhfmLgHgDqD6d9hHBtvJd2OparuuOpH8GrkwAASFq234kd69W6rMgDACQTt7uFsJMG8H+YYPeT0xVNXlYy2V7FZEOiT+rW1wndWGwV7icG7hELvKcYNVEmosuPPoKXdjqWfZN46kewWhkAkgrv5ESwZHsn9ob9G+TwicMx3ZqcawYAYAu7hQDeMcHuF68rmpxO/MXTKiYbEmlSt75P6DLIDqeSZYKR9xSjJspEbLntI/jVTkerb1Lf+xFIXiavdUjGB4kAS3gnJ8KJxTuxVVXGvzVePjz4YVTjCYdV8wAAxI9YvqqG19TADSbY/RLtFU3xtIrJBiZ1gcSSTBOMvKcYNVEmYstWH8FtvG4fOhJJrHe218TOTghm+lqHZH+QCIgh3smJcGKxyq3sVJnVyXUbuGYAVPE6kejHpGA0JvfcHo/JcTA5WT/ZfFUND9whEibYo8HPFU2sYrIvWVbhAn5K1glG3lOMmigTEIn+Tkci8TUByc5OqMm0XxAv7TyQZGL9Tk6/VidFa+URA/exF4sV8zbxHtv6IRlWVlL/xYZfE4le6xW/J/dMj8ftcTA5WT8l06tqeOAu8TDBHg2stq4/kmkVLhAtyTTB6KX+j+aq1mg8tGOaXrcPHokk9sNH9AkgEpuHjuJpApKdnRCOm35BvLXz9RTv20YosXwnZ7RWJ/k5ecnAfewl2nthTSZaWamZmJJlZSX1X2zYnkj0e3Iv1sfD5GT9V18fvKsPD9wl624VTLAD4STrKlzEp0R9dykTjKEl2ipP04eORLxNlPDwEeoTvx86ivcJSHZ2Qk30C+IK79tGvLA9qeDEhv0b5PCJw54HduNpMBD+Y6VmckqEussP9XXiMtSEkNOJn2jW67GcSIzF5J7b41FVOXH6hKPvlleWy/DXhwd+doI2OTEl2oN3ySKZ+0BMsANOJdMqXMQf3l1aPyXaKs9YP3RUZddqkdKD7urgRF71jvot2SYXk+14AYnvwdqaeN+2c4l0XhOdn5MKqirj3xrv2zu9TSYg4mkwEP5jpSZsrqx0MxnphpeJSzdsto1OJ4TC1fvRrNfr20Sim+Mxmaxz2k7TJgP+sdEHcvrQa7TbGSbYAacYILbDy3bUwUKt7lYVOeXi5sD2xB7vLq3/Em2Vp9v0qorMuU7kiyJv8fHKDQBAAoj3wdpwYv2+7USSyOc1Efk5qVB2qsy3yXVTyTohmoxbhkZzojVR6l6v2+WbvmPcZhmwNSEaq23qo1HubLaNPGQYv2IxWce5Qyw4bQu9tH3x0uepyctuFV4eho2Xh2mYYAcQv/zYjjpYrHYJiPbEHu8urZ8S7SEet+k9Wep9ct0LHioBAFiQyIO19W2llJ9snleTlfPxOvBmi63VpYkyIRoNybplaLLXp35N+Hq5bqJVBuK5Lk7kberjZZKThwzjl5e2O9yODk52ZaD/BD94bQvjZeLYK7d9oGg/DBvtdoYJdsSe0xXJTt4rXVO8bQmcTMcaDba2ozYVaTtr03OXaBOxiJ5QdYzTOsVWPeJltb7TXSdOlYn8ruvZn6lPYyNcW+ekLJL/AOopBmvrp1ieV9OV8/E68GaL35OeXlboJvqqJLfYNt25+rTKzeaEbzTKQCLVxTa3qXcj3vo8sX4oxsYDG+HqmHh4UCQUt+fGzaRmPFyzVeL5IR6/JcvONtFuCyNtk55o5ULE3zYsVu0ME+zJzMbEjNcVyU5X4HbsJXLLwrrTFesB/Ggfa33a/thJWbxn09lzWFOjVPd5ELyqe8ImZxN9Vd9xus11uPNYn85dtPBwSmRO65h4LItuHxJJtvrUpPxHehAhUn3n9vpwc25CnY94y38A8Emyr2Csr2J5Xk0H5hJ5stGtWA9MJ+uqJBN+r0IM5uU90fE08Fyfy5PfE76hyoTTMuDlvCdSXWy77+H1wSMn13q4chRP13MkNh7YSNRJZy8ScTepRHqIx1Ssd7bp2rar/HHwHx3lTTTrkWhtm17fXk9luw3zwvoE+zPPPCO//vWvZe/evZKbmyszZ86UK6+8MuT3CwsLZdKkSbJ582a58MIL5f7775c777wzhimuJ2xNzER7RfLutSIzOtT9WawH8KN9rOFWSSfSBKLTsli1IrUm0/Oa3ib221yzdXV4yfQgjgk/6phEKYvJVJ9Gu/xH4rZOTaZyCACIG8m0yqeKm4G5eFsZGG02BqZZleReNFchBnNa9iMNuscyj2NRnqKxqtvJathQovlgSzQnHGJZFyfargbRvmbDSaSJJBsPbCTipLMfEmU3qUR6iMdUrHc42XRgk/T9S19H341mPWJj2/REKhcmTO4LRczbQ6sT7PPnz5eJEyfKM888I1dccYU899xzMnz4cNmyZYtkZGTU+v5nn30mI0aMkPHjx8u8efPkf/7nf+QHP/iBtG3bVm688UYLR+Cjk6Uhfu9gdaaXAel4GBCP9XukbQ7guzlWpyukRaKzGrCusuh0lbCNspgo51WE96E7lUwP4vglmcqi22M13XWivj2cFYlJnZpM5dCGWPcVbUqmYwXgWjKt8gmWiCs6YsX2wDSrkqIj2oPwkQbdbeWx1xXfoQaXnazqdlv2ba2GjYdJwljVxbYfMPFyjPXt1QCxYOPhuUSZdPZDIvadkumByngri+EebrRZjuItn+JJPDx4Z3WC/Te/+Y3853/+p9x+++0iIjJz5kz5xz/+Ic8++6zMmDGj1vf/8Ic/SEZGhsycOVNERHJycqSoqEgef/zxkBPsFRUVUlFREfj/v//9bxEROXbsWO0vnywVqVD53y+IND7t/GBMwoqIzOgY+TuPXlT37x/c7S4ukerpvbtYpLGLzvvJcpEnv372Z5N8OlEpcsZh2JOV9tMbs2MtFdmx1nk8ddn+vsihL70NMkcqi6HKoUhsy2KinVeR6uU4Vmm2Va/5FdbkevfCy7UTD/kUq7KYkMdqWKfaLBMm5f+O9+qe7A7197zWqYlWJ9oKa9pPFLHbV0ymfnEilIlkCmsQZ9mpMjldfvp/gx6TykaV9TZsoqXXj7DrStY5/n5NRZ8Xyb7D+1yvIkmkfEq09PoZdvENi6Vpw6aOwp2oPCEj3hhhHOepslPSqFEjV2GLdxU7/n5dYlmOE+28ilQ/t165zWO/jtVteapy5UuhdwMVEblydujPV39vtau4TOthEfMybFImEqUuNs3jcDaUbJBes3qF/NxtmRDxpy5+7drXQk4k1fX3bJxXP8O6ud5PnTplpY7xK95Ea3eSqUwkwrGKVD9et22AiMigVwdF/E6ottK0TkyEazYeyoSNtjJUf6Rq/lhVw4ZP0UjfiJKTJ09KWlqavPrqq3LDDTcEfn/PPfdIcXGxFBYW1grTv39/6d69u/zud78L/O6NN96Q0aNHS1lZWZ0FberUqTJt2rToHAQAAAAAAAAAAAAAoN7YtWuXdOwYehGItRXsBw8elNOnT8v5559f7ffnn3++fPnll3WG+fLLL+v8fmVlpRw8eFAuuOCCWmEefPBBmTRpUuD/Z86ckcOHD0vr1q3r9VZaAAAAAAAAAAAAAABnVFWOHz8uF154YdjvWd0iXkRqTXKratiJ77q+X9fvqzRp0kSaNGlS7Xfnnnuuh5QCAAAAAAAAAAAAAOqrli1bRvxOgxiko05t2rSRc845p9Zq9f3799dapV6lffv2dX6/YcOG0rp166ilFQAAAAAAAAAAAAAAaxPsjRs3lh49eshbb71V7fdvvfWW9OvXr84wBQUFtb7/z3/+U3r27Fnn+9cBAAAAAAAAAAAAAPCLtQl2EZFJkybJ888/L7NmzZKtW7fKvffeKyUlJXLnnXeKyNn3p48ZMybw/TvvvFM+//xzmTRpkmzdulVmzZolL7zwgkyePNnWIQAAAAAAAAAAAAAAkoTVd7DffPPNcujQIfnZz34me/fulby8PFm8eLFkZmaKiMjevXulpKQk8P3OnTvL4sWL5d5775Wnn35aLrzwQvn9738vN954o61DAAAAAAAAAAAAAAAkiRRVVduJAAAAAAAAAAAAAAAg3lndIh4AAAAAAAAAAAAAgETBBDsAAAAAAAAAAAAAAA4wwQ4AAAAAAAAAAAAAgANMsAMAAAAAAAAAAAAA4AAT7ACAsP7xj3/YTgIAJJ3S0lKprKwUEZGjR49KYWGh7N2713Kqou/QoUPyzjvvyL59+2wnBQAQx44ePWo7CUnnyJEjtpOAJFZSUiKrVq2SVatWSUlJie3kwCfFxcWycOFC+fvf/y47duywnRwAAFxhgt0nlZWVsmHDBvn3v/8d8bsfffSRlXhr8uvmKNLf+fjjj2X//v0iIrJt2zaZPXu2rFu3zlNcL7zwgqdwImbH6ySszfNaUVEhCxculJkzZ8rTTz8tK1asiEm8NXnNYzfnNV6O1U2az5w5I++8847MmzdP5s2bJ++8846cOXPGVXxbtmyROXPmSHFxsaPve73utmzZUuvf7bffLlu3bpUtW7a4SnOwQ4cOuQ5jcr17idNtHtfkR53qJZ+iPdBlUre9+uqrgZ8PHjwo11xzjbRs2VIGDBhgNCjiJJ+81hV+XK81uT1HJmXRtBzblAiDtrGqJ+bMmSNt2rSRzp07y/LlyyUvL0/uu+8+yc/Pr3ZdxUqka86knhgzZkxgMn358uWSk5Mj9913n3Tt2lX+9re/RQzv1zXrps0pKSmRoUOHSnZ2tkyePFlOnDgR+KygoMB13CJ22kmRyGXSJH/9vAdwml4kFjf9cb/uAdyKRr/ALdttu5f6yQ2vdUW7du3kuuuuk0WLFrk+J7bKU7BY3Xt7zd+NGzdKjx49pHfv3rJ161a55pprpEOHDpKRkSGbNm3ylGYnbI2rxMO17pdEaCvd1Gsff/yx9OvXT/r06SM/+tGPZNKkSdKnTx/p16+fbN26NWxYr9e6aTm01X+KRt/Lq0htx6ZNmyQ/P1/69+8vN954ozzwwAPSs2dPGTVqlBw7diyqabNRLkzOjZ/1UyzuH/wK56ae8LPtAJB4nNZtUbkHUOiJEyf0jTfe0N/+9rf61FNP6fLlyyOGWbZsmbZp00bbtWunhYWF2qtXL7300ku1devWunLlyrBhU1JStGvXrvq73/1ODx065CqtXuOdOXNm4OcdO3boZZddpk2bNtWsrCzdtGlTxHiLi4s1OztbmzZtqiNHjtQDBw4EPuvevXvIcL/61a+0Xbt22qlTJ503b55mZGToqFGjtFOnTvrkk0+GjfPvf/97rX/t27cP/ByOyfF6DWvjvKqqLl++XDt16qT5+fnapEkTHTx4sObk5GivXr109+7dUYvXaz6ZnFdbx2qS5lWrVmlmZqb26dNHR48eraNGjdLevXtrZmamvvvuuyHDDRw4UL/88ktVVZ0/f7526NBBR48erVlZWfrf//3fYeM0ue5SUlI0Kyur2r+GDRtqVlaWdu7cOWzYcDp16hT2c5M89hqnSR6b1qle02wa75IlS7S4uFhVVVesWKFTp07VBQsWhA1jUrcFtw/jx4/XKVOm6N69e/WJJ57Q66+/3tXfChYpn7zWFV6vV1Xv7aSqWVk0CVtTaWmprl+/Xo8dO+bo+1u3btV9+/apquonn3yiL774ohYVFYUNY5JPNZ06dUrXr1+vR48ejfjdDz/80NXfrmKrnsjPz9edO3fqxo0btWXLlrp27VpVVd22bZt269bN07Goqh4+fNhTuEjXnEk9kZeXF/i5f//+unHjRlVV3blzZ8Qy4fWaNW1zhg8frk899ZQWFRXpmDFjtF+/foHr5utf/7qTw64lmu2k1+vOpE406Yv4WU/U/LuR7NmzR3/729/qPffco5MnT9ZZs2bpiRMnIoarqKjQM2fOBP6/ZMkSnTZtmi5cuNBR2o4ePaqzZ8/W6dOn6/Tp03X27Nl65MiRqMdbxW39X1FRoV988UWt33/00Udhw3ntj5vcA6h6z1+Ta0DVe3kybdu99PfCiVQ/qXovEyZ1RXZ2tj7++OOam5urF1xwgU6ZMkX/9a9/RUyraXkKtnnzZp09e7Zu2LAh4ndt3Hub5G///v114cKF+uKLL2pGRobOmTNHVVVff/11vfrqqyMebygXX3xx2M9tjKuYXus1Pf/8867DVHHaVzNtK73Wi+EcPHgw5Gcm9VqfPn3qrMNeffVV7dWrV8hwJte6STm01X8yCasa+7ajoKBACwsLVfVsvTJx4kStqKjQhx9+WMeMGRPx758+fVoLCwt17ty5OnfuXC0sLNTTp09HDGejXJicG5PyZOP+wda4iMk1u2jRIj158qSrME5E895D9Ww9XtVmHD58WF9//XX9+OOPw4YxPVY/246pU6d6Cuf2viWUSOfHa9/Wr/uzKl7zyW1YL+XJJJxJWfRat/l5DxAs6SfYvWZs7969tbi4WFesWKGtW7fWZcuWqarqmjVr9IorrggbZ15eni5YsEBHjBihzZo105tvvlnfeustR+n1Gm9wI/ad73xHn3rqKVVVXbBggQ4ePDhivFdddZW++eabevDgQX3kkUf00ksvDeRPuIHEyy67TA8fPqwlJSWalpamO3bsUFXVAwcOaG5ubtg4U1JStF+/fjpgwIDAv6ZNm+qAAQN04MCBYcOaHK/XsDbOa1V6qyqu1atX62233aaqqn/84x/1uuuui2q8Vdzkk+l5tXGsJmnOz88PTIwE++CDD6pNKtQU/FlBQYGWlJSo6tnGKj8/P2ycJtfd1KlTdfjw4bpz587A77KyssKGqVJXA1f1r23btmHDes1jkzhN8tikjjFJs0m8kydP1vz8fM3JydEZM2ZoXl6e3nfffdqjRw99+OGHQ4YzqduC24euXbtqZWVltf+HY5pPXuoKr9erqvd2UtWsLJqEvf/++wM/FxcX6wUXXKCXXHKJtm3bNjDYEYrXQQKTfLLxcKOteiI4bGZmZrXPIuWT10EN0/rUaz0RPNDes2fPap9FymOv16xJu65aOx8fffRR7dWrlx49ejRqeWySZq/XnUmdaNIXMaknwok00Dt//nzNyMjQa6+9Vlu3bq3f+c53dNiwYZqZmalbtmwJG7Zbt26Ba+33v/+95ufn6/333699+vTRn/3sZ2HDvv7669q+fXu9+eab9f7779f77rtPR48ere3bt9fXX389KvGa1P/Lly/XVq1aacuWLfXyyy/Xbdu2BT6LNHBqci/r9R7AJH9NrgGT8mTS9njt75nUTyZlwqSuCP7b7733no4fP15btGihV155pc6ePTtsOK/lyWTw38a9t0n+Bte3NevPSA/7bd68OeS/Cy64IGxYG+MqJte6rYUhJm2lSb0YTrh21qRey87O9vSZybVuUg5t9Z9MwtpoO2rWI8H3AZEexDGZdLZRLkzOjUl5snH/YHNcxOs126BBA23btq3ee++9ESdP3Yjmvcf8+fO1RYsWeu655+orr7yi+fn5OmzYMG3fvr2+9tprIcOZHKtJ2/H000/X+temTZvAz+GY3LeEE+78mPRtTe4LTfLJJKzX8uQ1nKpZWfRat5nU/+Ek/QS714wNbhQuuuiiap9FutkIvhB3796tjz76qHbp0kUzMzN12rRpYcN6jbfmJIeb9NZMs6rq3LlzNTs7W0tKSsJWLMGfZWRkhExTXV588UXt16+ffvDBB4HfOZ3oMzler2FtnNe60tijR4/Az+FuNkzj9ZpPJufV1rGapDncjUG4z7KzswOTkX379q32WaROtMl1p6q6fv16LSgo0GeffVZV1fHK9QYNGujAgQOrNXDBDV04XvPYJE6TPDapY0zSbBJvTk6OVlRU6OHDhzUtLS3Q4fvqq6/0sssuCxnOpG7LycnRLVu26ObNm2uVvWjmk9e6wuv1quq9naxKk9ey6Fddce211+obb7yhqqrvv/++9uvXL2xYr4MEJvlk4+FGW/VEjx499KOPPtJ3331X27Rpo++//76qqv7rX/+KOLjgdVDD5JozqSd++MMf6j333KOlpaX6wAMP6Lx58/TMmTO6ePFiHTBgQNiwXq9Zk3ZdVfWSSy6p9btf//rX2qNHD+3SpUvIcDbaSVXv151fdaLbvohJPVHXwMLTTz+tTz31lJ533nlhw+bl5QV25di+fbveeOONqqq6dOlSHTRoUMSwVXr16hV4ir+8vDxiXXHJJZfoZ599Vuv3O3bsqLOs+RGvSf3fp08f3bhxo545c0aff/55zczMDOwSEunceu2Pm9wDmOSvyTVgUp5M2h6v/T2T+smkTPhZV6ieXdX0pz/9Sfv37x8ynEl5Mhn8t3HvbZK/wX+35mrSSA/KpqSkaOfOnWvtjJaVlaWNGjUKG9bGuIrJtR4PC0NU3bWVJvWi1wlVk3qtX79+OmfOnGqrk0+fPq0vvviiFhQUhAxncq2blMN46D+5DWuj7ejZs2dg15E1a9ZU6/dfeumlYcOaTDrbKBcm58akPNm4f7A1LmLadhQVFekPfvADbdWqlfbp00f/+Mc/6vHjx8OGU7V379G9e3fds2ePfvzxx5qenh54KGv79u1hd/YwOVaTtuOcc87Ra6+9Vm+77bbAv/T0dL3tttt07NixEY+1itv7Fq/nx6Rva3JfaJJPpnnspTx5DadqVha91m0m9X84ST/B7jVjg8M98MAD1T5zs6Ip2IoVK/SWW24JG9ZrvF/72td08eLF+uabb9bqHEW6OVI9W4nW3Grn5Zdf1osvvrhW5yBYQUGBvvnmmzp37lzNzMwMbC9UWFhYLa9D2b17t44YMUKnTJmiJ06ccDzRZ3K8XsPaOK+qqldccUW1bZWGDx8e+CxS5WASr0keez2vto7VJM3Dhg3TadOmVdsu7eDBgzp16lQdMmRIyHA//elP9aabbtJPP/1Uf/3rX+vPf/5z/eyzz/SZZ57Ra6+9Nmycpted6tktbaZMmaKDBg3SDh06OApzySWXBCbZaurYsWPE8F7y2CTOmnk8ffp0x3lsUv5N0mwSb3An8MILL6z2mdOBuWBO6rbMzMxqg2u7du1SVY24ylPVLJ+81hVer9eq9HppJ1XNrneTsMHnoGYZiNYAjkk+2Xi40SR/Ta7XpUuXauvWrbVNmza6bNkyHTx4sObm5mrLli315Zdfdnysqs4HNUyuOZN6oqKiQidOnKjnnnuuXnTRRZqSkqINGzbUoUOHhkxPFZNr1mu7rqp6/fXX65IlS2r9/oknntCUlJSQ4Wy0k1XxernuTPLXpC9iUk80bNhQb7311moDC8EDDOHUrEeCy3VOTk7YsDk5OYHBgCuuuKLatoDhBqZVNexDGeE+M4nXpP6v+fnbb7+tmZmZWlxcHLFt99ofN7kHMMlfk2vApDyZtD1e+3sm9ZNJmTCpK7zuaGFSnkwG/23ce5vk75AhQ/Tf//53rd/v2bNHe/fuHTZsVlZWnduqqka3T+E1j02udVsLQ0zaSpN60euEqkm9tm3bNh00aJC2atVKc3NzNS8vT88991wdOHBg2NdCmFzrJuXQVv/Jr/o0Vm3HkiVLtE2bNpqbm6vt2rULrDzfu3ev3n777WHDmkw62ygXJufGpDypxv7+wda4iMk1Gxz2xIkTOm/ePB00aJA2b9484sSkrXuP4Gu25uR2uP6RybGatB0rVqzQPn36VFvV7OVhD7f3LV7Pj0nf1uS+0CSfTMJ6LU9ew6malUVVb3WbSf0fTtJPsHvN2LFjx9Z5s7Ft27aIq6giPV0Tjtd4r7rqqmod36qVTPv27au1HWddxo0bp4sWLar1+/nz54d9Annt2rXavXt3vfzyy7W4uFi///3va1paWrWVZ048++yzevnll0fcTqyKyfF6DWvjvKqefUKzY8eOmpaWpl/72tcCT1R9+eWXEZ/SM4nXtEypuj+vVcfarFmzmB6rSZr379+vY8eO1fT0dG3WrJmmp6drenq6jh07NvCkYigzZ87Ujh07apMmTTQlJUVbtGihd9xxR9h3m6n6d92pnn0i8Be/+IWj7z722GPVBhaCzZgxw3GcbvLYNE6veWxS/k3SbBLvN7/5TX3yySf15z//uXbt2lUff/xxPXDggM6ePTvsNWBSt4VSWloaceLMJJ+81os1r9eqa9bJ9eq1nazitSyahO3YsWPg6d2aE9aRJoC9DhKY5JOthxtr5m/z5s2jXk/UVFlZqUVFRRHLoar3QQ2Ta86PeqK0tFQ3bdqk69atc1TuVc9es+PGjfN0zVZx266rnr0BDPVuvHCvmLLRTqp6v+5q5q+bPoxJX8SknsjPzw/5zrdIA71XX321zpkzRw8cOKC//e1vddSoUYHPIg0aPf300/qNb3xDly1bpr/4xS/0v/7rv3TFihV6//33R3yP6He/+10dO3asFhUV6YEDB/TgwYNaVFSkY8eO1Ztvvjkq8ZrU/zk5ObXK/8qVKzUjI0Pbt28fNqzX/rjJPYBJ/pr0403Kk6r3tt1rf8+kfjIpEyZ1xdGjR8N+HorJ/bPJ4L+Ne28/7wurHDt2LPDQbCgTJkwIuU3zXXfdFTasjXGVuvoTzZo1c9yfsLEwxKStNKkXTSZUTe53VM+ep3Xr1um6det0//79Eb9v0naYlEOTtqOoqCjkNfv222+HDWtyvdtoO1RVjxw5okVFRXVet+GYTDrbKBcm58ZkjCJYrO4fbI2LmFyzocYKduzYoT/+8Y/DhrV17xE8/vH73/++2mdOd7EK5uRYTdoOVdXjx4/r+PHjdfTo0XrgwAHHbaXJfYvX82PStzW5L1T1nk8mYb2WJ6/hVM3KYjA3dZtJ/R9O0k+w+5mxS5cu1dOnT2tFRYXrdCxdutR1GNWzHYjCwkLdvXu363ir0ltaWhrxu0eOHPGUvpoOHDigCxYs0D179riO87PPPtOXXnrJUTyh0ltZWenoeIMF53GksF999ZWeOnUqkIaVK1c6OtZQYUtKShyd1+PHjwduMNzEGy6fnJan9evX6xtvvKFvvvmmfvrpp47LVJW1a9fqX/7yl8C77Jyk1+kNWF02bNhQK71OjjX4/Kxbt05feuklx+dW9Ww+vfbaazp79mz99NNPHYX56quv9OTJk3rs2DE9dOiQrlixwlN5Onz4sL766quu0muiZh57Cfvkk0/q9OnTI37fj7pp/fr1OmfOHFfnJhQvdYypw4cPO4r3008/1RtuuEFHjhypn3/+uT700EOanp6u3bp10+Li4hil1h2TOlXVrK44dOhQ4J9XVVtBuVF1vZuEdarmE7xVebt79+6I21KaDP54Zevhxipu8zcUt+2kW6aDGlWq+j9O2ue6eCnDJg4dOqT79u3TlStXuk6zmz6m37zeA7hNs2l9WlUf1rVy36l9+/bVevjDKaf5NGvWrJDvrZ03b17YsFV1SXp6ug4aNCiw9fO+ffv0+eefjxj3woUL9Rvf+Iaed9552qJFC83Pz9cZM2ZoeXl52HBlZWX6s5/9THNzc7V58+baokULzcvL06lTpzqqK7zEa1L/P/TQQ3Wej8LCwoirxkJx2h//4IMPXPcxa+Zv8+bNXeVvFbd9ApPyFNy/ddv2+Nnfc1qP+10mDh486LmucBtPFTdtlukkYbCqfrzb+9Hg8QK3fYq5c+fGJH/jSWVlpZ48edLRd036/24nsGquADd5GNMNk3bHj4cFq+o1kz6FG8HXpunYq5txK1Wz8hQct5trNniMbt26dY7CJtpYgclDoFWqyoXXc+tGXeHcnNeqscGq8uRmbDDYZ599pn/5y19ch1N1f29oMi6oerae8HJv5yXem266yXX6qvh57/H555+rqrO+4sMPP1zn2MjWrVvDvvLY5FhN71mqLF68WLt166bnn3++o++b3Ld4PT+mfVuv94XB3OaTSViv5clrOFWzsliT27ERk7HiuiT9BHsVtxm7efPmWv86duwYeNdstMLecsstgYZl2bJl2rZtW+3du7e2a9dO//rXv0YlTlXVRo0a6be//W3929/+5qpj5zW9wXH+9a9/dX0D6DW9JmmeM2eONm3aVDt27KjLli3TDh06aK9evbR169b6yiuvhI3TJOzs2bM9hzXJp02bNmleXp42b95cGzRooHl5edqqVSu96aabwj59alomrrvuupimV9Usjzdu3Kh5eXnaokWLQLznnXeejho1Kmy8JnGahDVhksdV+eQ2rEkZritOJ+dGVfXzzz/XoUOH6sUXX6w/+tGPqnWSam4XWVfYIUOGeAq7ceNGvfzyy7V37966ZcsWHTFihKampmqnTp1CdhpNmaTXhEk59np+iouLa+VvWlqadurUSTdu3Bg2zqpz06tXL9fnxiTenTt3Wjk/dXEySBCN8uRm0NSt4LJ28OBBveaaa7RFixZ61VVXBW6AnYYdMWKE47A2mLTP4cp/pDLsZ5rbtWsXk36xVybxmlw7XvuZJumtq15zWifaOj+IvuDyduDAAcf1otd+oilbbaxJ/9Yrk36MiVBlYsCAAVFrK6vqJ9Njdfvwg0ke26jHbfFaT6hWbysnTZrk+Jo16e/V5MdDe5WVlVpWVhb2O+HyqeqBnnhioyzaGHtVNavDTcYZTMY3vDK5Xv3i9iGG4HO7fPnymJxbk7FMk3GRuu5Hmzdv7uj8eL0GTMYFvd7bmcaL2Dt69KiuWrXKdjLinkk+1ec8DteXDzf+FK0xOibYwwj3REpKSkrgnbJV/xo2bKhZWVkRt18wCRu8vUL//v0DhWbnzp1h3wFhEqfq2e3yH3/8cc3NzdULLrhAp0yZEvZdR6bpDRXnJ598EjFOk/SapDk/P1937typGzdu1JYtW+ratWtV9ewTaZHen2UrrEk+FRQUVHu9wsSJE7WiokIffvjhsFue+F0mop1eVbM89hqvrTJhwiSPvYa1VSaGDx+uTz31lBYVFemYMWO0X79+euzYMVWN/J4Zk7D9+/fXhQsX6osvvqgZGRk6Z86cQPqvvvpqR8ddl3APmZmk14RJOfaaZpP8tRU2WufHZPVxuP5TtNLrddVkpLDB7dL48eN1ypQpunfvXn3iiSf0+uuvD/t3TcJGS7hjNWmfo1U3RWKrX+yVSbwm147X+tQkvSZlIlrnx+RJdZOwbuvTU6dO6fr16x1vf3369GktLCzUuXPn6ty5c7WwsNBoUjaax+q1XjTps6l6zyNbbaxJ/1bV2/Ga1uNe89hGWxmtNitSX8QkXhv1uC0mZcLrNRutchit/qlq9NJs0gZEawzVKxtjr6pmdbhJu2PaVoYSrs1KtPsdVTvn1qRMmIyLmJwfr/lkUg5Nzo2tvmI4Tu4BbMVbl2jf75gcq62wdbF1TxnL+1E38doow1771NFqs5J+gr2uJxqr/oXb1mnq1Kk6fPhw3blzZ+B3WVlZjuI0CRvcUai5ZVS494+axKlavQC+9957On78eG3RooVeeeWVOnv2bN/TaxKnaVivaQ6OMzMzs9pnkTrC8RDWbT7V7MgF51W4Dq2tMuE1vTXjdZvHXuO1VSZMmOSxH/lkq0yoqj766KPaq1cvPXr0aMSOv0nY4PPXqVOnap+ZPDxR828FM0mvCb+uAVXnaTbJX1thTc5PcXGxZmdna9OmTXXkyJF64MCBkH+3plB9p48++ihs/8kkvV77bCZhg89N165dtbKystr/wzEJa8LrsZq0z9GqmyKx1S/2yiRev9odN/WpSXpNykS0zk+4ts40rEl9umzZMm3Tpo22a9dOCwsLtVevXnrppZdq69atdeXKlWHDrlq1SjMzM7VPnz46evRoHTVqlPbu3VszMzNDvv84kmgeq9d60aTPZpJHttpYk/6t1+M1uWZN8thGW2lyrCZ9Eb/6e7Gqx20xKRN+3AO4jdNG/9Q0zeFEagNsjKF6ZWPsVdW/sUxVd+2OSVvptc1KtPsdVTvn1q8y4XZcxOT8eM0nk3Jocm5s9RVN+nu24g0lmvcAJsdqK2wo0bynNAkbjTIRKV5bZdhrnzpabVZDSXJ5eXmSlZUlqlrrs4MHD4YM99Of/lQ2bNgg3/3ud2XMmDFy5513SkpKiqM4TcIOHTpUJk6cKI899pgMHjxY/vznP8v3vvc9Wbp0qbRu3ToqcdZUUFAgBQUFMnPmTHnllVfkhRdekDFjxviaXpM4TcN6TXODBg1k8+bNcuTIESktLZXVq1dL37595ZNPPpHTp0+HTaOtsMHc5lOjRo3kk08+kezsbPnggw8kPT098Nk555wTMpytMuE1vSJmeew13ngoE26Z5LFJ2CqxLBNlZWXV/v/QQw9J48aN5Zvf/KYcP348amGD26qBAweG/KwuixcvDvnZiRMnQn5mkl4TJuXYa5pN8tdWWJPzc88998hvfvMb6du3r8ycOVOuvPJKefvtt6VDhw4R4/XafzJJr9c4TcJWVFTI1q1bRVWlQYMG1eqGSP0ok7AmvB6rSftsUoZNxEO/2A2TeE2uHa/1qUl6TcqESbxe2zrTsCb16YMPPihvv/22HDlyREaOHCmvvPKKDBo0SD744AOZNGmSrFq1KmTY//f//p8sWLBAevbsWe33a9eulXHjxsmHH35YZzhbx+q1XjTps3nNIxF7bWwwt/1br8drcs2a5LGNttLkWE36Iibx2qjHbTEpE16vWZM4bfRPTdNs0gbYGEP1ysbYa01u63CTdsekrfTaZiXa/Y6I/XFqt+FMxkVMzo/XfDIphybnxlZf0aS/ZyNeW/cAJsdqI6yte0pb58drvLauHa996qi1WZ6n5uuJrKws/eKLL+r8rGPHjhHDV1RU6JQpU3TQoEHaoUMHV3F7CVtRUaETJ07Uc889Vy+66CJNSUnRhg0b6tChQ3XHjh1RS6/XVa8m6TVZaWsS1mualy5dqq1bt9Y2bdrosmXLdPDgwZqbm6stW7bUl19+OWyctsKa5NOSJUu0TZs2mpubq+3atQs8mbR37169/fbbQ4azVSa8plfVLI+9xmurTJgwyWOvYW2Vieuvv16XLFlS6/dPPPGEpqSkRC3skCFD6nx/1J49e7R3795hwzZo0EAHDhyoAwYMqPWvadOmUUmvCZNy7DXNJvlrK6zJ+an5VOjcuXM1OztbS0pKIj4x6rX/ZJJekz6b17CZmZnauXPnwLaSu3btUlV1tIrEJKwJr8dq0j6blGETtvrFprzEa3LtmPYLvKTXjzLhJV6vbZ1pWJP6NLgvc9FFF1X7LNKqVqe7RtVk61i91osmfTaveaRqr42N1itTwn1mcs2a5LGNttLkWE36Iibx2qjHbTEpE16vWZM4bfRPTdNs0gbYHEP1KtZjryZ1uEm7Y9JWem2zEu1+R9XOuTUpEyb1v8n58ZpPJuXQ5NzY6iua9PdsxGvrHsDkWG2EtXVPaev8eI3X1rXjtU8drTYr6SfYJ0yYEHLLgrvuusvx33n//ff1F7/4hac0eAlbWlqqmzZt0nXr1nl6B4PbOJ2+AzAUL+k1idM0varmeVxZWalFRUW6b9++uA1rmk9HjhzRoqKiOiu1SGJdJlTN0hvM7fnxI15b5cktk2P1EtZWmThx4oSeOHGizs92794dtbChHDt2LNAxCOWSSy4JeVMS7iY0Gun1wk059jvNTvLXVliTY73kkktqvRvp5Zdf1osvvlgzMjLChvXafzJJr0mfza/+XpXS0lJHE7h+h3XC9FhN+z/BTMq/G7HuF/vFTbx+1mte+wV+5JOXMuEmXq9tnR9hvdanwdvRPfDAA9U+i7Qd5rBhw3TatGnVyv3Bgwd16tSpOmTIkLDptXGsoTipF7322bzmkaq9Ntakf2tyvHVxcs36Hadq9NvKujg5Vr/7E07jrclmPW6LkzLh9z2AkzjjqX+q6izNJm1APIyhehWrsVeTOty0DHttK/1u2+P9fkc1tufWjzHqKn6M77k5P17yyXQM1Ou9nY2+osm1YyNeW/cAJsdqI6zNe0ob58drvLaunVC8jj+ZtllJP8EOAEAyeOyxx/SDDz6o87MZM2bEODWIB+PGjdNFixbV+v38+fO1UaNGFlIEAGZM2jqTsCb16dixY+scCNy2bZteccUVYcPu379fx40bp+np6dqsWTNNT0/X9PR0HTt2bNiBV1vHaoPXPDJlK59sHK+tPAbgDfeFqCnR2nbATyb9GJNrx0a8tu4BTI7VRlhb95S2zo/XeG1dO/EmRTWKL0YEAAAAAACunD59Ws6cOSONGjVy9P3Dhw+LiMh5550XzWQltGTLIxvHm2x5DAAA6g9b/Zhk6j+ZHKutsIgsmfO3ge0EAAAAu7Kzs20nAXGGMgGgvjGp12yEPeeccyQ3N9fx988777xqAxpe47WVT7HgVx6ZilW8No43XvIYgDdcs6iJMoFk4mc/xk1YW/H6Ec5tWJNjtRU2WKLdU8YqbDyUYVsa2k4AAACIvi1btoT87KuvvophShAvKBMA6huTei2ZwtpKrw220ptM8SZamQCSHdcsaqJMIJklWj/eJGyipddW2ERLr62wyXRPGQ5bxAMAkAQaNGggWVlZUlez/8UXX8jJkyctpAo2USYA1Dcm9VoyhbWVXhtspTeZ4k20MgEkO65Z1ESZQDJLtH68SdhES6+tsImWXlthk+meMhxWsAMAkAQyMzNl1apVcuGFF9b6rFOnThZSBNsoEwDqG5N6LZnC2kqvDbbSm0zxJlqZAJId1yxqokwgmSVaP94kbKKl11bYREuvrbDJdE8ZDu9gBwAgCXz729+WHTt21PnZddddF+PUIB5QJgDUNyb1WjKFtZVeG2ylN5niTbQyASQ7rlnURJlAMku0frxJ2ERLr62wiZZeW2GT6Z4yHLaIBwAAAAAAAAAAAADAAVawAwAAAAAAAAAAAADgABPsAAAAAAAAAAAAAAA4wAQ7AAAAAAAAAAAAAAAOMMEOAAAAAAAAAAAAAIADTLADAAAAAFDP3XbbbXL99dcb/Y2srCyZOXOm0d9YuXKlpKSkyNGjR43+DgAAAAAAtjS0nQAAAAAAABD/1q5dK82aNbOdDAAAAAAArGKCHQAAAAAARNS2bVvbSQAAAAAAwDq2iAcAAAAAwCcLFiyQ/Px8SU1NldatW8vgwYOltLRURM6uAL/66qulTZs20rJlS7nqqqtk/fr11cKnpKTIc889J9/61rckLS1NcnJy5P3335ft27fLgAEDpFmzZlJQUCCffvppIMzUqVPl61//ujz33HPSqVMnSUtLk1GjRoXdhl1V5Ve/+pV87Wtfk9TUVOnWrZssWLAg7LHV3CI+JSVFnn/+ebnhhhskLS1NLr74Yvnb3/5WLczixYslOztbUlNTZeDAgbJz585af/e9996T/v37S2pqqnTq1EkmTJgQyLM5c+ZIenq6bNu2LfD9u+++W7KzswPfAQAAAAAglphgBwAAAADAB3v37pXvfve7Mm7cONm6dausXLlSRo4cKaoqIiLHjx+XW2+9Vd59911ZvXq1XHzxxTJixAg5fvx4tb8zffp0GTNmjBQXF8ull14q3/ve9+SOO+6QBx98UIqKikRE5Ic//GG1MNu3b5dXXnlFFi1aJEuXLpXi4mK56667Qqb1kUcekT/96U/y7LPPyubNm+Xee++V//iP/5DCwkJXxzxt2jQZPXq0bNq0SUaMGCHf//735fDhwyIismvXLhk5cqSMGDFCiouL5fbbb5cHHnigWvgPP/xQhg4dKiNHjpRNmzbJ/PnzZdWqVYHjGzNmTODvVlZWytKlS+W5556TP//5z2xXDwAAAACwIkWr7vQBAAAAAIBn69evlx49esjOnTslMzMz4vdPnz4trVq1kpdeekm+9a1vicjZVeGPPPKITJ8+XUREVq9eLQUFBfLCCy/IuHHjRETk5ZdflrFjx0p5ebmInF3B/vOf/1x27twpHTt2FBGRpUuXyjXXXCNffPGFtG/fXm677TY5evSoLFy4UEpLS6VNmzayfPlyKSgoCKTn9ttvl7KyMnnppZfqTG9WVpZMnDhRJk6cWGdaS0tLpXnz5rJ48WIZNmyYPPTQQ7Jw4ULZvHmzpKSkiIjIAw88IL/85S/lyJEjcu6558qYMWMkNTVVnnvuuUA8q1atkquuukpKS0uladOmcuTIEenatatce+218vrrr8vdd98tDz/8sOPzAgAAAACAn3gHOwAAAAAAPujWrZt885vflPz8fBk6dKgMGTJEbrrpJmnVqpWIiOzfv19+8pOfyPLly2Xfvn1y+vRpKSsrk5KSkmp/p2vXroGfzz//fBERyc/Pr/a7EydOyLFjx6RFixYiIpKRkRGYXBcRKSgokDNnzsi//vUvad++fbW/v2XLFjlx4oRcffXV1X5/8uRJ6d69u6tjDk5rs2bNpHnz5rJ//34REdm6dav07ds3MLlela5g69atk+3bt8uf//znwO9UVc6cOSOfffaZ5OTkSKtWreSFF16QoUOHSr9+/WqtggcAAAAAIJaYYAcAAAAAwAfnnHOOvPXWW/Lee+/JP//5T3nyySfl4YcfljVr1kjnzp3ltttukwMHDsjMmTMlMzNTmjRpIgUFBXLy5Mlqf6dRo0aBn6smp+v63ZkzZ0Kmpeo7wZPbVarC/f3vf5cOHTpU+6xJkyZuDrlauqriq/r7TjbMO3PmjNxxxx0yYcKEWp9lZGQEfn7nnXfknHPOkT179khpaWngwQIAAAAAAGKNd7ADAAAAAOCTlJQUueKKK2TatGmyYcMGady4sbzxxhsiIvLuu+/KhAkTZMSIEZKbmytNmjSRgwcP+hJvSUmJ7NmzJ/D/999/Xxo0aCDZ2dm1vnvZZZdJkyZNpKSkRLp06VLtX6dOnXxJT1U8q1evrva7mv+//PLLZfPmzbXS0aVLF2ncuLGIiLz33nvyq1/9ShYtWiQtWrSQu+++27c0AgAAAADgFivYAQAAAADwwZo1a2TZsmUyZMgQadeunaxZs0YOHDggOTk5IiLSpUsXmTt3rvTs2VOOHTsm9913n6SmpvoSd9OmTeXWW2+Vxx9/XI4dOyYTJkyQ0aNH19oeXkSkefPmMnnyZLn33nvlzJkz8o1vfEOOHTsm7733nqSnp8utt97qS5ruvPNOeeKJJ2TSpElyxx13yLp16+TFF1+s9p0pU6ZI37595a677pLx48dLs2bNZOvWrfLWW2/Jk08+KcePH5dbbrlF7r77bhk+fLhkZGRIz5495Vvf+paMGjXKl3QCAAAAAOAGK9gBAAAAAPBBixYt5J133pERI0ZIdna2PPLII/LEE0/I8OHDRURk1qxZcuTIEenevbvccsstMmHCBGnXrp0vcXfp0kVGjhwpI0aMkCFDhkheXp4888wzIb8/ffp0+clPfiIzZsyQnJwcGTp0qCxatEg6d+7sS3pEzm7x/tprr8miRYukW7du8oc//EEee+yxat/p2rWrFBYWyrZt2+TKK6+U7t27y49//GO54IILRETknnvukWbNmgXC5ebmyi9/+Uu588475YsvvvAtrQAAAAAAOJWiTl6KBgAAAAAA4tLUqVNl4cKFUlxcbDspAAAAAADUe6xgBwAAAAAAAAAAAADAASbYAQAAAAAAAAAAAABwgC3iAQAAAAAAAAAAAABwgBXsAAAAAAAAAAAAAAA4wAQ7AAAAAAAAAAAAAAAOMMEOAAAAAAAAAAAAAIADTLADAAAAAAAAAAAAAOAAE+wAAAAAAAAAAAAAADjABDsAAAAAAAAAAAAAAA4wwQ4AAAAAAAAAAAAAgANMsAMAAAAAAAAAAAAA4MD/B1A6LBgehBw5AAAAAElFTkSuQmCC" + "text/plain": " name gps list \\\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A \n1 Acorn St [42.3576234, -71.0688746] A \n2 Arlington's Great Meadows [42.4299758, -71.2038948] A \n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A \n4 BU Beach [42.3511927, -71.1060828] A \n.. ... ... ... \n28 The Clam Box [42.2763168, -71.0092883] C \n29 The Partisans [42.3478375, -71.0404428] C \n30 Union Oyster House [42.361288, -71.056908] C \n31 Victoria's Diner [42.3270498, -71.0667744] C \n32 Wollaston Beach [42.2806539, -71.0119933] C \n\n normalized_gps \n0 [0.7251058917247415, 0.8141430878559053] \n1 [0.6747391031099019, 0.778052752104061] \n2 [1.0, 0.41697235794883575] \n3 [0.6697144722136962, 0.7604611403245493] \n4 [0.6458298305822171, 0.6785480000609988] \n.. ... \n28 [0.30922451563130937, 0.9374025730216268] \n29 [0.6307464973238023, 0.8540870458656248] \n30 [0.6912133469876947, 0.8100546647415456] \n31 [0.5372951958288665, 0.7836692527743693] \n32 [0.32872198960456106, 0.9301686741961767] \n\n[131 rows x 4 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistnormalized_gps
0521 Commercial Street #525[42.3688272, -71.0553792]A[0.7251058917247415, 0.8141430878559053]
1Acorn St[42.3576234, -71.0688746]A[0.6747391031099019, 0.778052752104061]
2Arlington's Great Meadows[42.4299758, -71.2038948]A[1.0, 0.41697235794883575]
3Arthur Fiedler Statue[42.3565057, -71.0754527]A[0.6697144722136962, 0.7604611403245493]
4BU Beach[42.3511927, -71.1060828]A[0.6458298305822171, 0.6785480000609988]
...............
28The Clam Box[42.2763168, -71.0092883]C[0.30922451563130937, 0.9374025730216268]
29The Partisans[42.3478375, -71.0404428]C[0.6307464973238023, 0.8540870458656248]
30Union Oyster House[42.361288, -71.056908]C[0.6912133469876947, 0.8100546647415456]
31Victoria's Diner[42.3270498, -71.0667744]C[0.5372951958288665, 0.7836692527743693]
32Wollaston Beach[42.2806539, -71.0119933]C[0.32872198960456106, 0.9301686741961767]
\n

131 rows × 4 columns

\n
" }, "metadata": {}, "output_type": "display_data" } ], "source": [ - "# Create the linkage matrix\n", - "linkage_matrix = linkage(TotalList['gps'].values.tolist(), 'ward')\n", - "\n", - "# Plot the dendrogram\n", - "plt.figure(figsize=(25, 10))\n", - "plt.title('Hierarchical Clustering Dendrogram')\n", - "plt.xlabel('sample index')\n", - "plt.ylabel('distance')\n", - "dendrogram(linkage_matrix, leaf_rotation=90., leaf_font_size=8.)\n", - "plt.show()" - ], - "metadata": { - "collapsed": false, - "ExecuteTime": { - "end_time": "2023-11-06T01:14:14.540031Z", - "start_time": "2023-11-06T01:14:14.088884Z" - } - }, - "id": "9e215df3a350e3cf" - }, - { - "cell_type": "code", - "execution_count": 85, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Number of clusters: 7\n", - "Silhouette score: 0.42876627286716495\n" - ] - } - ], - "source": [ - "# Set the threshold distance\n", - "threshold_distance = 0.15\n", - "\n", - "# Cut the dendrogram to get cluster labels\n", - "cluster_labels_hc = fcluster(linkage_matrix, t=threshold_distance, criterion='distance')\n", - "\n", - "# Now, you have the number of clusters determined by the dendrogram\n", - "num_clusters = len(np.unique(cluster_labels_hc))\n", - "print(\"Number of clusters:\", num_clusters)\n", - "\n", - "# Calculate the silhouette score to evaluate the clustering\n", - "silhouette_avg = silhouette_score(TotalList['gps'].values.tolist(), cluster_labels_hc)\n", - "print(\"Silhouette score:\", silhouette_avg)" + "display(TotalList)" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:14.556841Z", - "start_time": "2023-11-06T01:14:14.545269Z" + "end_time": "2023-11-06T17:13:47.531619Z", + "start_time": "2023-11-06T17:13:47.459977Z" } }, - "id": "2f52d83746e670d" + "id": "a03a7c5dacebddd0" }, { "cell_type": "markdown", @@ -229,64 +179,7 @@ }, { "cell_type": "code", - "execution_count": 86, - "outputs": [], - "source": [ - "# Cluster the data using Gaussian Mixture Models\n", - "# Create two centroids, one in the North End and one in the Financial District\n", - "centroids = [[42.364506, -71.054733], [42.358894, -71.056742]]" - ], - "metadata": { - "collapsed": false, - "ExecuteTime": { - "end_time": "2023-11-06T01:14:15.329931Z", - "start_time": "2023-11-06T01:14:15.325838Z" - } - }, - "id": "45b59d81ae2de84e" - }, - { - "cell_type": "code", - "execution_count": 87, - "outputs": [ - { - "data": { - "text/plain": " name gps list weights\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A 0.018132\n1 Acorn St [42.3576234, -71.0688746] A 0.008032\n2 Arlington's Great Meadows [42.4299758, -71.2038948] A 0.000676\n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A 0.005410\n4 BU Beach [42.3511927, -71.1060828] A 0.002145\n.. ... ... ... ...\n28 The Clam Box [42.2763168, -71.0092883] C 0.001136\n29 The Partisans [42.3478375, -71.0404428] C 0.005315\n30 Union Oyster House [42.361288, -71.056908] C 0.037200\n31 Victoria's Diner [42.3270498, -71.0667744] C 0.003055\n32 Wollaston Beach [42.2806539, -71.0119933] C 0.001198\n\n[131 rows x 4 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistweights
0521 Commercial Street #525[42.3688272, -71.0553792]A0.018132
1Acorn St[42.3576234, -71.0688746]A0.008032
2Arlington's Great Meadows[42.4299758, -71.2038948]A0.000676
3Arthur Fiedler Statue[42.3565057, -71.0754527]A0.005410
4BU Beach[42.3511927, -71.1060828]A0.002145
...............
28The Clam Box[42.2763168, -71.0092883]C0.001136
29The Partisans[42.3478375, -71.0404428]C0.005315
30Union Oyster House[42.361288, -71.056908]C0.037200
31Victoria's Diner[42.3270498, -71.0667744]C0.003055
32Wollaston Beach[42.2806539, -71.0119933]C0.001198
\n

131 rows × 4 columns

\n
" - }, - "metadata": {}, - "output_type": "display_data" - } - ], - "source": [ - "# Create a weights column that increases as the location gets closer to the centroids\n", - "\n", - "# Compute the distance from each point to each centroid\n", - "TotalList['weights'] = TotalList['gps'].apply(lambda x: [np.linalg.norm(np.array(x) - np.array(centroids[0])), np.linalg.norm(np.array(x) - np.array(centroids[1]))])\n", - "\n", - "# Invert the weights so that the locations closest to the centroids have the highest weights\n", - "TotalList['weights'] = TotalList['weights'].apply(lambda x: [1/i for i in x])\n", - "\n", - "# Sum the weights\n", - "TotalList['weights'] = TotalList['weights'].apply(lambda x: sum(x))\n", - "\n", - "# Normalize the weights\n", - "TotalList['weights'] = TotalList['weights'].apply(lambda x: x/sum(TotalList['weights']))\n", - "\n", - "display(TotalList)" - ], - "metadata": { - "collapsed": false, - "ExecuteTime": { - "end_time": "2023-11-06T01:14:15.942150Z", - "start_time": "2023-11-06T01:14:15.938980Z" - } - }, - "id": "2f2975484d00129c" - }, - { - "cell_type": "code", - "execution_count": 88, + "execution_count": 9, "outputs": [ { "name": "stderr", @@ -300,20 +193,20 @@ } ], "source": [ - "kmeans = KMeans(n_clusters=2, init=centroids).fit(TotalList['gps'].values.tolist())" + "kmeans = KMeans(n_clusters=2, init=norm_centroids).fit(TotalList['normalized_gps'].values.tolist())" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:16.878902Z", - "start_time": "2023-11-06T01:14:16.865126Z" + "end_time": "2023-11-06T17:13:47.552787Z", + "start_time": "2023-11-06T17:13:47.462389Z" } }, "id": "db1ef4b14a1da5f5" }, { "cell_type": "code", - "execution_count": 89, + "execution_count": 10, "outputs": [], "source": [ "# Add the cluster labels to the dataframe\n", @@ -322,20 +215,20 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:17.887765Z", - "start_time": "2023-11-06T01:14:17.880353Z" + "end_time": "2023-11-06T17:13:47.654801Z", + "start_time": "2023-11-06T17:13:47.534432Z" } }, "id": "99891fae96a2fff7" }, { "cell_type": "code", - "execution_count": 90, + "execution_count": 11, "outputs": [ { "data": { - "text/plain": " name gps list weights \\\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A 0.018132 \n1 Acorn St [42.3576234, -71.0688746] A 0.008032 \n2 Arlington's Great Meadows [42.4299758, -71.2038948] A 0.000676 \n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A 0.005410 \n4 BU Beach [42.3511927, -71.1060828] A 0.002145 \n.. ... ... ... ... \n28 The Clam Box [42.2763168, -71.0092883] C 0.001136 \n29 The Partisans [42.3478375, -71.0404428] C 0.005315 \n30 Union Oyster House [42.361288, -71.056908] C 0.037200 \n31 Victoria's Diner [42.3270498, -71.0667744] C 0.003055 \n32 Wollaston Beach [42.2806539, -71.0119933] C 0.001198 \n\n cluster \n0 1 \n1 1 \n2 0 \n3 1 \n4 0 \n.. ... \n28 1 \n29 1 \n30 1 \n31 1 \n32 1 \n\n[131 rows x 5 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistweightscluster
0521 Commercial Street #525[42.3688272, -71.0553792]A0.0181321
1Acorn St[42.3576234, -71.0688746]A0.0080321
2Arlington's Great Meadows[42.4299758, -71.2038948]A0.0006760
3Arthur Fiedler Statue[42.3565057, -71.0754527]A0.0054101
4BU Beach[42.3511927, -71.1060828]A0.0021450
..................
28The Clam Box[42.2763168, -71.0092883]C0.0011361
29The Partisans[42.3478375, -71.0404428]C0.0053151
30Union Oyster House[42.361288, -71.056908]C0.0372001
31Victoria's Diner[42.3270498, -71.0667744]C0.0030551
32Wollaston Beach[42.2806539, -71.0119933]C0.0011981
\n

131 rows × 5 columns

\n
" + "text/plain": " name gps list \\\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A \n1 Acorn St [42.3576234, -71.0688746] A \n2 Arlington's Great Meadows [42.4299758, -71.2038948] A \n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A \n4 BU Beach [42.3511927, -71.1060828] A \n.. ... ... ... \n28 The Clam Box [42.2763168, -71.0092883] C \n29 The Partisans [42.3478375, -71.0404428] C \n30 Union Oyster House [42.361288, -71.056908] C \n31 Victoria's Diner [42.3270498, -71.0667744] C \n32 Wollaston Beach [42.2806539, -71.0119933] C \n\n normalized_gps cluster \n0 [0.7251058917247415, 0.8141430878559053] 1 \n1 [0.6747391031099019, 0.778052752104061] 1 \n2 [1.0, 0.41697235794883575] 0 \n3 [0.6697144722136962, 0.7604611403245493] 1 \n4 [0.6458298305822171, 0.6785480000609988] 0 \n.. ... ... \n28 [0.30922451563130937, 0.9374025730216268] 1 \n29 [0.6307464973238023, 0.8540870458656248] 1 \n30 [0.6912133469876947, 0.8100546647415456] 1 \n31 [0.5372951958288665, 0.7836692527743693] 1 \n32 [0.32872198960456106, 0.9301686741961767] 1 \n\n[131 rows x 5 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistnormalized_gpscluster
0521 Commercial Street #525[42.3688272, -71.0553792]A[0.7251058917247415, 0.8141430878559053]1
1Acorn St[42.3576234, -71.0688746]A[0.6747391031099019, 0.778052752104061]1
2Arlington's Great Meadows[42.4299758, -71.2038948]A[1.0, 0.41697235794883575]0
3Arthur Fiedler Statue[42.3565057, -71.0754527]A[0.6697144722136962, 0.7604611403245493]1
4BU Beach[42.3511927, -71.1060828]A[0.6458298305822171, 0.6785480000609988]0
..................
28The Clam Box[42.2763168, -71.0092883]C[0.30922451563130937, 0.9374025730216268]1
29The Partisans[42.3478375, -71.0404428]C[0.6307464973238023, 0.8540870458656248]1
30Union Oyster House[42.361288, -71.056908]C[0.6912133469876947, 0.8100546647415456]1
31Victoria's Diner[42.3270498, -71.0667744]C[0.5372951958288665, 0.7836692527743693]1
32Wollaston Beach[42.2806539, -71.0119933]C[0.32872198960456106, 0.9301686741961767]1
\n

131 rows × 5 columns

\n
" }, "metadata": {}, "output_type": "display_data" @@ -348,8 +241,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:19.060647Z", - "start_time": "2023-11-06T01:14:19.051699Z" + "end_time": "2023-11-06T17:13:47.690379Z", + "start_time": "2023-11-06T17:13:47.562147Z" } }, "id": "49fc751352022ad1" @@ -366,7 +259,7 @@ }, { "cell_type": "code", - "execution_count": 91, + "execution_count": 12, "outputs": [], "source": [ "# Create a map in Boston\n", @@ -375,21 +268,21 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:20.184965Z", - "start_time": "2023-11-06T01:14:20.177057Z" + "end_time": "2023-11-06T17:13:47.690503Z", + "start_time": "2023-11-06T17:13:47.606732Z" } }, "id": "48d76bd40c44cc61" }, { "cell_type": "code", - "execution_count": 92, + "execution_count": 13, "outputs": [], "source": [ "# Plot the centroids on the map\n", "for i in range(len(centroids)):\n", " folium.Marker(centroids[i], popup='Centroid ' + str(i), icon=folium.Icon(color='black')).add_to(m)\n", - " \n", + "\n", "# Add the points to the map with different colors for each cluster\n", "for i, row in TotalList.iterrows():\n", " if row['cluster'] == 0:\n", @@ -418,22 +311,22 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:20.573947Z", - "start_time": "2023-11-06T01:14:20.558985Z" + "end_time": "2023-11-06T17:13:47.690797Z", + "start_time": "2023-11-06T17:13:47.629116Z" } }, "id": "3c8a7d2b34d4f22d" }, { "cell_type": "code", - "execution_count": 93, + "execution_count": 14, "outputs": [ { "data": { - "text/plain": "", - "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" }, - "execution_count": 93, + "execution_count": 14, "metadata": {}, "output_type": "execute_result" } @@ -445,21 +338,21 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:23.580878Z", - "start_time": "2023-11-06T01:14:23.507152Z" + "end_time": "2023-11-06T17:13:47.812439Z", + "start_time": "2023-11-06T17:13:47.668506Z" } }, "id": "d6941d1f0a203ee7" }, { "cell_type": "code", - "execution_count": 94, + "execution_count": 15, "outputs": [ { "data": { - "text/plain": "1 74\n0 57\nName: cluster, dtype: int64" + "text/plain": "1 83\n0 48\nName: cluster, dtype: int64" }, - "execution_count": 94, + "execution_count": 15, "metadata": {}, "output_type": "execute_result" } @@ -471,191 +364,426 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:28.465028Z", - "start_time": "2023-11-06T01:14:28.461813Z" + "end_time": "2023-11-06T17:13:47.814584Z", + "start_time": "2023-11-06T17:13:47.761699Z" } }, "id": "479ba8f36cdafbf8" }, { "cell_type": "code", - "execution_count": 73, + "execution_count": 16, "outputs": [], "source": [ - "# create a method to move n number of locations from the largest cluster to the smallest cluster, taking distance into account\n", - "def equalize_clusters(df, n):\n", - " # Get the number of locations in each cluster\n", - " cluster_counts = df['cluster'].value_counts()\n", - " \n", - " # Get the largest and smallest clusters\n", - " largest_cluster = cluster_counts.index[0]\n", - " smallest_cluster = cluster_counts.index[-1]\n", - " \n", - " # Get the locations in the largest cluster\n", - " largest_cluster_locations = df[df['cluster'] == largest_cluster]\n", - " \n", - " # Get the locations in the smallest cluster\n", - " smallest_cluster_locations = df[df['cluster'] == smallest_cluster]\n", - " \n", - " # Create a list of distances from each location in the largest cluster to each location in the smallest cluster\n", - " distances = []\n", - " for i, row in largest_cluster_locations.iterrows():\n", - " for j, row2 in smallest_cluster_locations.iterrows():\n", - " distances.append([i, j, np.linalg.norm(np.array(row['gps']) - np.array(row2['gps']))])\n", - " \n", - " # Sort the distances by distance\n", - " distances.sort(key=lambda x: x[2])\n", - " \n", - " # Move the n closest locations from the largest cluster to the smallest cluster\n", - " for i in range(n):\n", - " df.loc[distances[i][0], 'cluster'] = smallest_cluster\n", - " df.loc[distances[i][1], 'cluster'] = largest_cluster\n", - " \n", - " return df" + "# Return the list of locations in each cluster\n", + "route_1 = TotalList[TotalList['cluster'] == 0]\n", + "route_1_stops = len(route_1['gps'].values.tolist())\n", + "route_1_str = utils.list_to_string(route_1['gps'].values.tolist())" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:13:47.814649Z", + "start_time": "2023-11-06T17:13:47.767185Z" + } + }, + "id": "89297f77828e8ed8" + }, + { + "cell_type": "code", + "execution_count": 17, + "outputs": [], + "source": [ + "route_2 = TotalList[TotalList['cluster'] == 1]\n", + "route_2_stops = len(route_2['gps'].values.tolist())\n", + "route_2_str = utils.list_to_string(route_2['gps'].values.tolist())" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:08:43.493687Z", - "start_time": "2023-11-06T01:08:43.480182Z" + "end_time": "2023-11-06T17:13:47.815014Z", + "start_time": "2023-11-06T17:13:47.770253Z" } }, - "id": "4b79215a12bf36e2" + "id": "6ff82e29a0366d9e" }, { "cell_type": "code", - "execution_count": 74, + "execution_count": 18, "outputs": [ { - "data": { - "text/plain": "0 97\n1 72\nName: cluster, dtype: int64" - }, - "execution_count": 74, - "metadata": {}, - "output_type": "execute_result" + "name": "stdout", + "output_type": "stream", + "text": [ + "The trip will take 9.129166666666666 hours\n", + "The trip will take 11.833055555555555 hours\n" + ] } ], "source": [ - "# Equalize the clusters\n", - "TotalList = equalize_clusters(TotalList, 20)\n", + "# Get the time for each route\n", + "trip_hrs_1 = utils.get_trip_time(northeastern_coordinate + route_1_str, route_1_stops)\n", + "print(\"The trip will take {} hours\".format(trip_hrs_1))\n", + "trip_hrs_2 = utils.get_trip_time(northeastern_coordinate + route_2_str, route_2_stops)\n", + "print(\"The trip will take {} hours\".format(trip_hrs_2))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:13:49.614158Z", + "start_time": "2023-11-06T17:13:47.772345Z" + } + }, + "id": "7949bddd34b6731" + }, + { + "cell_type": "code", + "execution_count": 19, + "outputs": [], + "source": [ + "# Move a coordinate from one cluster to the other and see how the trip time changes\n", + "# Find the closest coordinate between the two clusters\n", "\n", - "# Display the number of locations in each cluster\n", - "TotalList['cluster'].value_counts()" + "closest_coordinate = utils.move_coordinate(route_2['gps'].values.tolist(), route_1['gps'].values.tolist())" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:13:49.620559Z", + "start_time": "2023-11-06T17:13:49.614687Z" + } + }, + "id": "47ee7033f93c4d2b" + }, + { + "cell_type": "code", + "execution_count": 20, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "The closest coordinate is [42.3446263, -71.0969274]\n" + ] + } + ], + "source": [ + "print(\"The closest coordinate is {}\".format(closest_coordinate))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:13:49.620803Z", + "start_time": "2023-11-06T17:13:49.617173Z" + } + }, + "id": "f77340f4382a886f" + }, + { + "cell_type": "code", + "execution_count": 21, + "outputs": [], + "source": [ + "# Change the cluster of the closest coordinate array\n", + "TotalList.loc[TotalList['gps'].astype(str) == str(closest_coordinate), 'cluster'] = 0" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:08:43.649954Z", - "start_time": "2023-11-06T01:08:43.542655Z" + "end_time": "2023-11-06T17:13:49.623360Z", + "start_time": "2023-11-06T17:13:49.621229Z" } }, - "id": "176d5f92130c67b8" + "id": "7d9f2216c1c0e80f" }, { "cell_type": "code", - "execution_count": 75, + "execution_count": 22, "outputs": [ { "data": { - "text/plain": "'-71.0553792,42.3688272;-71.0688746,42.3576234;-71.2038948,42.4299758;-71.0754527,42.3565057;-71.1060828,42.3511927;-71.0969274,42.3446263;-71.130887,42.35304;-71.0620802,42.3579151;-71.1459593,42.3501823;-71.0586014,42.357357;-71.0572023,42.3587627;-71.0556268,42.36521;-71.1460435,42.3495825;-71.1217152,42.3426377;-71.0720926,42.3489004;-71.067859,42.3500079;-71.0632036,42.3556154;-71.1258765,42.331864;-71.1095021,42.3364675;-71.133103,42.3890049;-71.0620134,42.3248471;-71.0851891,42.3500031;-71.1123834,42.3360385;-71.066414,42.354296;-71.2273649,42.3145041;-71.0834061,42.341987;-71.0992038,42.3306454;-71.0990577,42.3381442;-71.0569649,42.3604952;-71.0949218,42.3419564;-71.0942861,42.3413301;-71.0498714,42.3256817;-71.0908104,42.329969;-71.0616035,42.3537983;-71.0359433,42.3485465;-71.0913583,42.3490205;-71.1000217,42.3323776;-71.1241295,42.3518397;-71.1618052,42.3245965;-71.0638101,42.3587772;-71.1625829,42.340795;-71.167854,42.4107892;-71.155555,42.3317473;-71.1227278,42.3965778;-71.3598149,42.3140229;-71.1126695,42.3836229;-71.0555003,42.3640137;-71.119149,42.3884;-71.0712561,42.3407613;-71.0561781,42.3668968;-71.0664019,42.3554589;-71.059228,42.359349;-71.0668408,42.3524116;-71.0872846,42.2961434;-71.062146,42.366198;-71.1427371,42.3433772;-71.1438455,42.3569102;-71.0651214,42.3553972;-71.0596124,42.3509517;-71.0359354,42.3478381;-71.1313443,42.3525708;-71.1284677,42.3631904;-71.061757,42.3691906;-71.119301,42.388547;-71.097883,42.381008;-71.1107166,42.3741209;-71.0609962,42.3803747;-71.0516339,42.3609921;-71.1194344,42.3754427;-71.0809932,42.3675275;-71.0545357,42.3597994;-71.1013044,42.3627462;-71.1108423,42.3838224;-71.1026937,42.3820702;-71.1189467,42.373465;-71.1208817,42.3732344;-71.0342146,42.316274;-71.0756902,42.3695046;-71.0678704,42.3701829;-71.0968274,42.3799095;-71.0656594,42.3718401;-71.094048,42.339381;-71.1854722,42.3621177;-71.1146697,42.3782386;-71.0935443,42.3817274;-71.0611749,42.3551807;-71.0906355,42.3616095;-71.1161887,42.3766442;-71.0962734,42.3627993;-71.1155576,42.3784629;-71.0949101,42.3797674;-71.1087411,42.3640287;-71.0554239,42.3739796;-71.09476,42.37736;-71.1014951,42.3614115;-71.1024769,42.3822934;-71.1011111,42.3636597;-71.0631664,42.3741694;-71.056823,42.361531;-71.0632852,42.2857047;-71.0637877,42.2845163;-71.0496839,42.3519736;-71.0454645,42.3162356;-71.0336324,42.3441918;-71.0487437,42.3508756;-71.0512911,42.3521821;-71.0013637,42.2075316;-71.0607764,42.3763541;-71.0374911,42.316031;-71.0125206,42.3378699;-71.0672898,42.3523158;-71.02832,42.2576602;-71.0502126,42.3516479;-71.0331956,42.3639107;-71.0432778,42.3528151;-71.0035279,42.2392354;-71.0470633,42.3537343;-71.0352443,42.3291218;-71.0898829,42.3463992;-71.0240951,42.2743442;-71.0234949,42.3358743;-70.985881,42.420226;-71.0005483,42.2454086;-71.0096371,42.3367603;-71.0447796,42.3509709;-71.0983169,42.3319001;-71.0092883,42.2763168;-71.0404428,42.3478375;-71.056908,42.361288;-71.0667744,42.3270498;-71.0119933,42.2806539;-71.0618764,42.4074484;-71.0612182,42.3986053;-71.0392667,42.3855456;-71.0515875,42.4025721;-70.9903023,42.3917606;-71.055873,42.4206339;-71.0433886,42.4222989;-71.06088,42.3761612;-71.0412802,42.3936888;-71.0714924,42.3968978;-71.0282154,42.3778389;-71.0350852,42.3809511;-71.0331398,42.3734483;-70.9693867,42.3895122;-71.0945712,42.3253252;-71.0280157,42.398422;-71.0155516,42.4114215;-70.993656,42.4110462;-71.0355621,42.3976519;-71.0056995,42.390191;-71.0589219,42.403759;-71.037937,42.3698284;-71.0386285,42.3903823;-71.0316196,42.4122481;-71.0328839,42.3861321;-71.0270609,42.4213082;-71.0366491,42.391236;-71.0361399,42.3649623;-71.0116946,42.3827415;-70.9973058,42.4183123;-71.1122037,42.4008442;-70.997123,42.390501;-71.0506461,42.41826;-71.0359889,42.3670906;-71.0414523,42.3649544;-71.0371343,42.3711266;-71.033703,42.3891835;-70.9799864,42.3803348;'" + "text/plain": "1 82\n0 49\nName: cluster, dtype: int64" }, - "execution_count": 75, + "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "utils.list_to_string(TotalList['gps'].values.tolist())" + "# Display the number of locations in each cluster\n", + "TotalList['cluster'].value_counts()" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:08:43.650401Z", - "start_time": "2023-11-06T01:08:43.622162Z" + "end_time": "2023-11-06T17:13:49.632625Z", + "start_time": "2023-11-06T17:13:49.624757Z" } }, - "id": "2d83e5db093608d2" + "id": "175937590bf5d19" }, { "cell_type": "code", - "execution_count": 95, + "execution_count": 23, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "57\n" + "The trip will take 9.216666666666667 hours\n", + "The trip will take 11.710277777777778 hours\n" ] - }, + } + ], + "source": [ + "# Calculate the new trip time\n", + "new_route_1 = TotalList[TotalList['cluster'] == 0]\n", + "new_route_2 = TotalList[TotalList['cluster'] == 1]\n", + "new_route_1_stops = len(new_route_1['gps'].values.tolist())\n", + "new_route_1_str = utils.list_to_string(new_route_1['gps'].values.tolist())\n", + "new_route_2_stops = len(new_route_2['gps'].values.tolist())\n", + "new_route_2_str = utils.list_to_string(new_route_2['gps'].values.tolist())\n", + "\n", + "new_trip_hrs_1 = utils.get_trip_time(northeastern_coordinate + new_route_1_str, new_route_1_stops)\n", + "print(\"The trip will take {} hours\".format(new_trip_hrs_1))\n", + "new_trip_hrs_2 = utils.get_trip_time(northeastern_coordinate + new_route_2_str, new_route_2_stops)\n", + "print(\"The trip will take {} hours\".format(new_trip_hrs_2))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:13:51.356749Z", + "start_time": "2023-11-06T17:13:49.629464Z" + } + }, + "id": "1eddc12b846d259" + }, + { + "cell_type": "code", + "execution_count": 24, + "outputs": [ { "data": { - "text/plain": "'-71.2038948,42.4299758;-71.1060828,42.3511927;-71.0969274,42.3446263;-71.130887,42.35304;-71.1459593,42.3501823;-71.1460435,42.3495825;-71.1217152,42.3426377;-71.1258765,42.331864;-71.1095021,42.3364675;-71.133103,42.3890049;-71.1123834,42.3360385;-71.2273649,42.3145041;-71.0992038,42.3306454;-71.0990577,42.3381442;-71.0949218,42.3419564;-71.0942861,42.3413301;-71.0913583,42.3490205;-71.1000217,42.3323776;-71.1241295,42.3518397;-71.1618052,42.3245965;-71.1625829,42.340795;-71.167854,42.4107892;-71.155555,42.3317473;-71.1227278,42.3965778;-71.3598149,42.3140229;-71.1126695,42.3836229;-71.119149,42.3884;-71.1427371,42.3433772;-71.1438455,42.3569102;-71.1313443,42.3525708;-71.1284677,42.3631904;-71.119301,42.388547;-71.097883,42.381008;-71.1107166,42.3741209;-71.1194344,42.3754427;-71.1013044,42.3627462;-71.1108423,42.3838224;-71.1026937,42.3820702;-71.1189467,42.373465;-71.1208817,42.3732344;-71.0968274,42.3799095;-71.094048,42.339381;-71.1854722,42.3621177;-71.1146697,42.3782386;-71.0935443,42.3817274;-71.0906355,42.3616095;-71.1161887,42.3766442;-71.0962734,42.3627993;-71.1155576,42.3784629;-71.0949101,42.3797674;-71.1087411,42.3640287;-71.09476,42.37736;-71.1014951,42.3614115;-71.1024769,42.3822934;-71.1011111,42.3636597;-71.0898829,42.3463992;-71.0983169,42.3319001;'" + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" }, - "execution_count": 95, + "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "# Return the list of locations in each cluster\n", - "print(len(TotalList[TotalList['cluster'] == 0]['gps'].values.tolist()))\n", - "utils.list_to_string(TotalList[TotalList['cluster'] == 0]['gps'].values.tolist())" + "# Create a new map with the new coordinates\n", + "m = folium.Map(location=[42.3601, -71.0589], zoom_start=12)\n", + "\n", + "# Plot the centroids on the map\n", + "for i in range(len(centroids)):\n", + " folium.Marker(centroids[i], popup='Centroid ' + str(i), icon=folium.Icon(color='black')).add_to(m)\n", + "\n", + "# Add the points to the map with different colors for each cluster\n", + "for i, row in TotalList.iterrows():\n", + " if row['cluster'] == 0:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='red')).add_to(m)\n", + " elif row['cluster'] == 1:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='blue')).add_to(m)\n", + " elif row['cluster'] == 2:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='green')).add_to(m)\n", + " elif row['cluster'] == 3:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='purple')).add_to(m)\n", + " elif row['cluster'] == 4:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='orange')).add_to(m)\n", + " elif row['cluster'] == 5:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='darkred')).add_to(m)\n", + " elif row['cluster'] == 6:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='lightred')).add_to(m)\n", + " elif row['cluster'] == 7:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='beige')).add_to(m)\n", + " elif row['cluster'] == 8:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='darkblue')).add_to(m)\n", + " elif row['cluster'] == 9:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='lightblue')).add_to(m)\n", + " elif row['cluster'] == 10:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='cadet')).add_to(m)\n", + "\n", + "# Display the map\n", + "m" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:35.829990Z", - "start_time": "2023-11-06T01:14:35.821619Z" + "end_time": "2023-11-06T17:13:51.474500Z", + "start_time": "2023-11-06T17:13:51.364744Z" } }, - "id": "89297f77828e8ed8" + "id": "e02dfb4cc414066a" + }, + { + "cell_type": "code", + "execution_count": 25, + "outputs": [], + "source": [ + "# Attempt to minimize the trip time by moving a coordinate from one cluster to the other\n", + "new_route_2_coordinates, new_route_1_coordinates = utils.minimize_route_time_diff(route_2['gps'].values.tolist(), route_1['gps'].values.tolist(), northeastern_coordinate, 0.5)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:14:15.930771Z", + "start_time": "2023-11-06T17:13:51.471954Z" + } + }, + "id": "fa09560bd996ad9c" }, { "cell_type": "code", - "execution_count": 96, + "execution_count": 26, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "74\n" + "The trip will take 10.150555555555556 hours\n", + "The trip will take 10.488888888888889 hours\n" ] - }, + } + ], + "source": [ + "# Calculate the new trip time\n", + "new_route_1_stops = len(new_route_1_coordinates)\n", + "new_route_1_str = utils.list_to_string(new_route_1_coordinates)\n", + "new_route_2_stops = len(new_route_2_coordinates)\n", + "new_route_2_str = utils.list_to_string(new_route_2_coordinates)\n", + "\n", + "new_trip_hrs_1 = utils.get_trip_time(northeastern_coordinate + new_route_1_str, new_route_1_stops)\n", + "print(\"The trip will take {} hours\".format(new_trip_hrs_1))\n", + "new_trip_hrs_2 = utils.get_trip_time(northeastern_coordinate + new_route_2_str, new_route_2_stops)\n", + "print(\"The trip will take {} hours\".format(new_trip_hrs_2))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:14:17.697174Z", + "start_time": "2023-11-06T17:14:15.937708Z" + } + }, + "id": "cb4c9f02d769c5b2" + }, + { + "cell_type": "code", + "execution_count": 27, + "outputs": [], + "source": [ + "# Edit the dataframe to reflect the new coordinate clusters\n", + "TotalList.loc[TotalList['gps'].astype(str).isin(map(str, new_route_1_coordinates)), 'cluster'] = 0\n", + "TotalList.loc[TotalList['gps'].astype(str).isin(map(str, new_route_2_coordinates)), 'cluster'] = 1" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:14:17.713355Z", + "start_time": "2023-11-06T17:14:17.702484Z" + } + }, + "id": "ccda123bae5a7fe2" + }, + { + "cell_type": "code", + "execution_count": 28, + "outputs": [ { "data": { - "text/plain": "'-71.0553792,42.3688272;-71.0688746,42.3576234;-71.0754527,42.3565057;-71.0620802,42.3579151;-71.0586014,42.357357;-71.0572023,42.3587627;-71.0556268,42.36521;-71.0720926,42.3489004;-71.067859,42.3500079;-71.0632036,42.3556154;-71.0620134,42.3248471;-71.0851891,42.3500031;-71.066414,42.354296;-71.0834061,42.341987;-71.0569649,42.3604952;-71.0498714,42.3256817;-71.0908104,42.329969;-71.0616035,42.3537983;-71.0359433,42.3485465;-71.0638101,42.3587772;-71.0555003,42.3640137;-71.0712561,42.3407613;-71.0561781,42.3668968;-71.0664019,42.3554589;-71.059228,42.359349;-71.0668408,42.3524116;-71.0872846,42.2961434;-71.062146,42.366198;-71.0651214,42.3553972;-71.0596124,42.3509517;-71.0359354,42.3478381;-71.061757,42.3691906;-71.0609962,42.3803747;-71.0516339,42.3609921;-71.0809932,42.3675275;-71.0545357,42.3597994;-71.0342146,42.316274;-71.0756902,42.3695046;-71.0678704,42.3701829;-71.0656594,42.3718401;-71.0611749,42.3551807;-71.0554239,42.3739796;-71.0631664,42.3741694;-71.056823,42.361531;-71.0632852,42.2857047;-71.0637877,42.2845163;-71.0496839,42.3519736;-71.0454645,42.3162356;-71.0336324,42.3441918;-71.0487437,42.3508756;-71.0512911,42.3521821;-71.0013637,42.2075316;-71.0607764,42.3763541;-71.0374911,42.316031;-71.0125206,42.3378699;-71.0672898,42.3523158;-71.02832,42.2576602;-71.0502126,42.3516479;-71.0331956,42.3639107;-71.0432778,42.3528151;-71.0035279,42.2392354;-71.0470633,42.3537343;-71.0352443,42.3291218;-71.0240951,42.2743442;-71.0234949,42.3358743;-70.985881,42.420226;-71.0005483,42.2454086;-71.0096371,42.3367603;-71.0447796,42.3509709;-71.0092883,42.2763168;-71.0404428,42.3478375;-71.056908,42.361288;-71.0667744,42.3270498;-71.0119933,42.2806539;'" + "text/plain": "1 70\n0 61\nName: cluster, dtype: int64" }, - "execution_count": 96, + "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "print(len(TotalList[TotalList['cluster'] == 1]['gps'].values.tolist()))\n", - "utils.list_to_string(TotalList[TotalList['cluster'] == 1]['gps'].values.tolist())" + "# Display the number of locations in each cluster\n", + "TotalList['cluster'].value_counts()" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:14:36.909798Z", - "start_time": "2023-11-06T01:14:36.904157Z" + "end_time": "2023-11-06T17:14:17.725481Z", + "start_time": "2023-11-06T17:14:17.710476Z" } }, - "id": "6ff82e29a0366d9e" + "id": "c871a41d003d72ee" + }, + { + "cell_type": "code", + "execution_count": 29, + "outputs": [ + { + "data": { + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + }, + "execution_count": 29, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "# Create a new map with the new coordinates\n", + "m = folium.Map(location=[42.3601, -71.0589], zoom_start=12)\n", + "\n", + "# Plot the centroids on the map\n", + "for i in range(len(centroids)):\n", + " folium.Marker(centroids[i], popup='Centroid ' + str(i), icon=folium.Icon(color='black')).add_to(m)\n", + "\n", + "# Add the points to the map with different colors for each cluster\n", + "for i, row in TotalList.iterrows():\n", + " if row['cluster'] == 0:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='red')).add_to(m)\n", + " elif row['cluster'] == 1:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='blue')).add_to(m)\n", + " elif row['cluster'] == 2:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='green')).add_to(m)\n", + " elif row['cluster'] == 3:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='purple')).add_to(m)\n", + " elif row['cluster'] == 4:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='orange')).add_to(m)\n", + " elif row['cluster'] == 5:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='darkred')).add_to(m)\n", + " elif row['cluster'] == 6:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='lightred')).add_to(m)\n", + " elif row['cluster'] == 7:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='beige')).add_to(m)\n", + " elif row['cluster'] == 8:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='darkblue')).add_to(m)\n", + " elif row['cluster'] == 9:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='lightblue')).add_to(m)\n", + " elif row['cluster'] == 10:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='cadet')).add_to(m)\n", + "\n", + "# Display the map\n", + "m" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T17:14:17.803413Z", + "start_time": "2023-11-06T17:14:17.723348Z" + } + }, + "id": "76538bc325ff80b0" }, { "cell_type": "code", - "execution_count": 77, + "execution_count": 29, "outputs": [], "source": [], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-06T01:08:43.651470Z", - "start_time": "2023-11-06T01:08:43.640872Z" + "end_time": "2023-11-06T17:14:17.803513Z", + "start_time": "2023-11-06T17:14:17.800565Z" } }, - "id": "7949bddd34b6731" + "id": "438c323e29e25031" } ], "metadata": { diff --git a/Clustering2.0.ipynb b/Clustering2.0.ipynb new file mode 100644 index 0000000..5ff2d63 --- /dev/null +++ b/Clustering2.0.ipynb @@ -0,0 +1,313 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "id": "initial_id", + "metadata": { + "collapsed": true, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.475082Z", + "start_time": "2023-11-06T18:51:21.667023Z" + } + }, + "outputs": [], + "source": [ + "import folium\n", + "import pandas as pd\n", + "from sklearn.cluster import KMeans\n", + "import utils" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "outputs": [], + "source": [ + "# Load the data\n", + "ListA = pd.read_csv('List A.csv')\n", + "ListB = pd.read_csv('List B.csv')\n", + "ListC = pd.read_csv('List C.csv')\n", + "ListD = pd.read_csv('List D.csv')" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.495242Z", + "start_time": "2023-11-06T18:51:22.473334Z" + } + }, + "id": "bb6f57eef695cf76" + }, + { + "cell_type": "code", + "execution_count": 3, + "outputs": [], + "source": [ + "# Create two centroids, one in the North End and one in the Financial District\n", + "centroids = [[42.364506, -71.054733], [42.358894, -71.056742]]\n", + "\n", + "northeastern_coordinate = \"-71.09033,42.33976;\"" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.495492Z", + "start_time": "2023-11-06T18:51:22.483246Z" + } + }, + "id": "fe8a5b9bc06cf2e0" + }, + { + "cell_type": "code", + "execution_count": 4, + "outputs": [ + { + "data": { + "text/plain": " name gps \\\n0 521 Commercial Street #525 42.3688272,-71.0553792 \n1 Acorn St 42.3576234,-71.0688746 \n2 Arlington's Great Meadows 42.4299758,-71.2038948 \n3 Arthur Fiedler Statue 42.3565057,-71.0754527 \n4 BU Beach 42.3511927,-71.1060828 \n.. ... ... \n28 The Clam Box 42.2763168,-71.0092883 \n29 The Partisans 42.3478375,-71.0404428 \n30 Union Oyster House 42.361288,-71.056908 \n31 Victoria's Diner 42.3270498,-71.0667744 \n32 Wollaston Beach 42.2806539,-71.0119933 \n\n googleUrl \\\n0 https://maps.google.com/maps?q=+%4042.3688272,... \n1 https://maps.google.com/maps?q=+%4042.3576234,... \n2 https://maps.google.com/maps?q=+%4042.4299758,... \n3 https://maps.google.com/maps?q=+%4042.3565057,... \n4 https://maps.google.com/maps?q=+%4042.3511927,... \n.. ... \n28 https://maps.google.com/maps?q=+%4042.2763168,... \n29 https://maps.google.com/maps?q=+%4042.3478375,... \n30 https://maps.google.com/maps?q=+%4042.361288,-... \n31 https://maps.google.com/maps?q=+%4042.3270498,... \n32 https://maps.google.com/maps?q=+%4042.2806539,... \n\n originalUrl info types \\\n0 https://www.google.com/maps/place/521+Commerci... NaN NaN \n1 https://www.google.com/maps/place/Acorn+St/dat... NaN NaN \n2 https://www.google.com/maps/place/Arlington's+... NaN NaN \n3 https://www.google.com/maps/place/Arthur+Fiedl... NaN NaN \n4 https://www.google.com/maps/place/BU+Beach/dat... NaN NaN \n.. ... ... ... \n28 https://www.google.com/maps/place/The+Clam+Box... NaN NaN \n29 https://www.google.com/maps/place/The+Partisan... NaN NaN \n30 https://www.google.com/maps/place/Union+Oyster... NaN NaN \n31 https://www.google.com/maps/place/Victoria's+D... NaN NaN \n32 https://www.google.com/maps/place/Wollaston+Be... NaN NaN \n\n address \\\n0 NaN \n1 NaN \n2 Minuteman Commuter Bikeway, Lexington, MA 0242... \n3 Charles River Esplanades, Boston, MA 02114, Un... \n4 270 Bay State Rd, Boston, MA 02215, United States \n.. ... \n28 789 Quincy Shore Dr, Quincy, MA 02170, United ... \n29 Boston, MA 02210, United States \n30 41 Union St, Boston, MA 02108, United States \n31 1024 Massachusetts Ave, Boston, MA 02118, Unit... \n32 Quincy, MA, United States \n\n description type \\\n0 NaN NaN \n1 NaN NaN \n2 183-acres of wet meadows & uplands with trails... Nature preserve \n3 NaN Sculpture \n4 A sloping, grassy plaza on the university grou... Park \n.. ... ... \n28 Classic beachfront joint with a rustic vibe di... Seafood restaurant \n29 NaN Sculpture \n30 Historic eatery serving chowder & other New En... Seafood restaurant \n31 Long-standing classic diner for breakfast & sa... Diner \n32 Historic 2.3-mi.-long beach with a paved prome... Beach \n\n phone website \\\n0 NaN NaN \n1 NaN NaN \n2 +1 781-863-5385 http://www.foagm.org/ \n3 +1 617-332-2433 http://helmicksculpture.com/portfolio/arthur-f... \n4 NaN https://www.bu.edu/today/2009/icons-among-us-t... \n.. ... ... \n28 +1 617-302-3474 http://www.clamboxquincy.com/ \n29 NaN https://www.bostonseaport.xyz/venue/the-partis... \n30 +1 617-227-2750 http://www.unionoysterhouse.com/?y_source=1_Mj... \n31 +1 617-442-5965 http://www.victoriasdiner.com/ \n32 NaN NaN \n\n ratingsAverage ratingsTotal plusCode list \n0 NaN NaN NaN A \n1 NaN NaN NaN A \n2 4.6 171.0 CQHW+XC Lexington, Massachusetts, USA A \n3 4.6 14.0 9W4F+JR Boston, Massachusetts, USA A \n4 4.5 133.0 9V2V+FH Boston, Massachusetts, USA A \n.. ... ... ... ... \n28 4.3 2145.0 7XGR+G7 Quincy, Massachusetts, USA C \n29 4.8 6.0 8XX5+4R Boston, Massachusetts, USA C \n30 4.3 8497.0 9W6V+G6 Boston, Massachusetts, USA C \n31 4.1 1797.0 8WGM+R7 Boston, Massachusetts, USA C \n32 4.4 171.0 NaN C \n\n[131 rows x 15 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpsgoogleUrloriginalUrlinfotypesaddressdescriptiontypephonewebsiteratingsAverageratingsTotalplusCodelist
0521 Commercial Street #52542.3688272,-71.0553792https://maps.google.com/maps?q=+%4042.3688272,...https://www.google.com/maps/place/521+Commerci...NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNA
1Acorn St42.3576234,-71.0688746https://maps.google.com/maps?q=+%4042.3576234,...https://www.google.com/maps/place/Acorn+St/dat...NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNA
2Arlington's Great Meadows42.4299758,-71.2038948https://maps.google.com/maps?q=+%4042.4299758,...https://www.google.com/maps/place/Arlington's+...NaNNaNMinuteman Commuter Bikeway, Lexington, MA 0242...183-acres of wet meadows & uplands with trails...Nature preserve+1 781-863-5385http://www.foagm.org/4.6171.0CQHW+XC Lexington, Massachusetts, USAA
3Arthur Fiedler Statue42.3565057,-71.0754527https://maps.google.com/maps?q=+%4042.3565057,...https://www.google.com/maps/place/Arthur+Fiedl...NaNNaNCharles River Esplanades, Boston, MA 02114, Un...NaNSculpture+1 617-332-2433http://helmicksculpture.com/portfolio/arthur-f...4.614.09W4F+JR Boston, Massachusetts, USAA
4BU Beach42.3511927,-71.1060828https://maps.google.com/maps?q=+%4042.3511927,...https://www.google.com/maps/place/BU+Beach/dat...NaNNaN270 Bay State Rd, Boston, MA 02215, United StatesA sloping, grassy plaza on the university grou...ParkNaNhttps://www.bu.edu/today/2009/icons-among-us-t...4.5133.09V2V+FH Boston, Massachusetts, USAA
................................................
28The Clam Box42.2763168,-71.0092883https://maps.google.com/maps?q=+%4042.2763168,...https://www.google.com/maps/place/The+Clam+Box...NaNNaN789 Quincy Shore Dr, Quincy, MA 02170, United ...Classic beachfront joint with a rustic vibe di...Seafood restaurant+1 617-302-3474http://www.clamboxquincy.com/4.32145.07XGR+G7 Quincy, Massachusetts, USAC
29The Partisans42.3478375,-71.0404428https://maps.google.com/maps?q=+%4042.3478375,...https://www.google.com/maps/place/The+Partisan...NaNNaNBoston, MA 02210, United StatesNaNSculptureNaNhttps://www.bostonseaport.xyz/venue/the-partis...4.86.08XX5+4R Boston, Massachusetts, USAC
30Union Oyster House42.361288,-71.056908https://maps.google.com/maps?q=+%4042.361288,-...https://www.google.com/maps/place/Union+Oyster...NaNNaN41 Union St, Boston, MA 02108, United StatesHistoric eatery serving chowder & other New En...Seafood restaurant+1 617-227-2750http://www.unionoysterhouse.com/?y_source=1_Mj...4.38497.09W6V+G6 Boston, Massachusetts, USAC
31Victoria's Diner42.3270498,-71.0667744https://maps.google.com/maps?q=+%4042.3270498,...https://www.google.com/maps/place/Victoria's+D...NaNNaN1024 Massachusetts Ave, Boston, MA 02118, Unit...Long-standing classic diner for breakfast & sa...Diner+1 617-442-5965http://www.victoriasdiner.com/4.11797.08WGM+R7 Boston, Massachusetts, USAC
32Wollaston Beach42.2806539,-71.0119933https://maps.google.com/maps?q=+%4042.2806539,...https://www.google.com/maps/place/Wollaston+Be...NaNNaNQuincy, MA, United StatesHistoric 2.3-mi.-long beach with a paved prome...BeachNaNNaN4.4171.0NaNC
\n

131 rows × 15 columns

\n
" + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "# Combine the two lists and add a column to indicate the list\n", + "ListA['list'] = 'A'\n", + "ListB['list'] = 'B'\n", + "ListC['list'] = 'C'\n", + "ListD['list'] = 'D'\n", + "\n", + "TotalList = pd.concat([ListA, ListB, ListC])\n", + "display(TotalList)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.496051Z", + "start_time": "2023-11-06T18:51:22.487941Z" + } + }, + "id": "dc434958d5e4a3a8" + }, + { + "cell_type": "code", + "execution_count": 5, + "outputs": [], + "source": [ + "# Remove all columns but name and gps\n", + "TotalList = TotalList[['name', 'gps', 'list']]" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.504898Z", + "start_time": "2023-11-06T18:51:22.496235Z" + } + }, + "id": "2873c16423fe3119" + }, + { + "cell_type": "code", + "execution_count": 6, + "outputs": [], + "source": [ + "# Convert the gps column to a list of lists for k-means\n", + "TotalList['gps'] = TotalList['gps'].apply(lambda x: x.strip('[]').split(','))\n", + "TotalList['gps'] = TotalList['gps'].apply(lambda x: [float(i) for i in x])" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.522522Z", + "start_time": "2023-11-06T18:51:22.498651Z" + } + }, + "id": "29f9155ef8d75fda" + }, + { + "cell_type": "code", + "execution_count": 7, + "outputs": [], + "source": [ + "# Create a new column with normalized gps coordinates and centroids\n", + "TotalList['normalized_gps'], norm_centroids = utils.normalize_gps(TotalList['gps'].values.tolist(), centroids)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.548654Z", + "start_time": "2023-11-06T18:51:22.503769Z" + } + }, + "id": "5b985f1a6df84a6c" + }, + { + "cell_type": "code", + "execution_count": 8, + "outputs": [ + { + "data": { + "text/plain": " name gps list \\\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A \n1 Acorn St [42.3576234, -71.0688746] A \n2 Arlington's Great Meadows [42.4299758, -71.2038948] A \n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A \n4 BU Beach [42.3511927, -71.1060828] A \n.. ... ... ... \n28 The Clam Box [42.2763168, -71.0092883] C \n29 The Partisans [42.3478375, -71.0404428] C \n30 Union Oyster House [42.361288, -71.056908] C \n31 Victoria's Diner [42.3270498, -71.0667744] C \n32 Wollaston Beach [42.2806539, -71.0119933] C \n\n normalized_gps \n0 [0.7251058917247415, 0.8141430878559053] \n1 [0.6747391031099019, 0.778052752104061] \n2 [1.0, 0.41697235794883575] \n3 [0.6697144722136962, 0.7604611403245493] \n4 [0.6458298305822171, 0.6785480000609988] \n.. ... \n28 [0.30922451563130937, 0.9374025730216268] \n29 [0.6307464973238023, 0.8540870458656248] \n30 [0.6912133469876947, 0.8100546647415456] \n31 [0.5372951958288665, 0.7836692527743693] \n32 [0.32872198960456106, 0.9301686741961767] \n\n[131 rows x 4 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistnormalized_gps
0521 Commercial Street #525[42.3688272, -71.0553792]A[0.7251058917247415, 0.8141430878559053]
1Acorn St[42.3576234, -71.0688746]A[0.6747391031099019, 0.778052752104061]
2Arlington's Great Meadows[42.4299758, -71.2038948]A[1.0, 0.41697235794883575]
3Arthur Fiedler Statue[42.3565057, -71.0754527]A[0.6697144722136962, 0.7604611403245493]
4BU Beach[42.3511927, -71.1060828]A[0.6458298305822171, 0.6785480000609988]
...............
28The Clam Box[42.2763168, -71.0092883]C[0.30922451563130937, 0.9374025730216268]
29The Partisans[42.3478375, -71.0404428]C[0.6307464973238023, 0.8540870458656248]
30Union Oyster House[42.361288, -71.056908]C[0.6912133469876947, 0.8100546647415456]
31Victoria's Diner[42.3270498, -71.0667744]C[0.5372951958288665, 0.7836692527743693]
32Wollaston Beach[42.2806539, -71.0119933]C[0.32872198960456106, 0.9301686741961767]
\n

131 rows × 4 columns

\n
" + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "display(TotalList)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:22.609058Z", + "start_time": "2023-11-06T18:51:22.509542Z" + } + }, + "id": "a03a7c5dacebddd0" + }, + { + "cell_type": "markdown", + "source": [ + "# Cluster and Minimize" + ], + "metadata": { + "collapsed": false + }, + "id": "ee3ab1c81ea71b0" + }, + { + "cell_type": "code", + "execution_count": 9, + "outputs": [ + { + "name": "stderr", + "output_type": "stream", + "text": [ + "/Users/garrinshieh/anaconda3/lib/python3.11/site-packages/sklearn/cluster/_kmeans.py:1412: FutureWarning: The default value of `n_init` will change from 10 to 'auto' in 1.4. Set the value of `n_init` explicitly to suppress the warning\n", + " super()._check_params_vs_input(X, default_n_init=10)\n", + "/Users/garrinshieh/anaconda3/lib/python3.11/site-packages/sklearn/cluster/_kmeans.py:1412: RuntimeWarning: Explicit initial center position passed: performing only one init in KMeans instead of n_init=10.\n", + " super()._check_params_vs_input(X, default_n_init=10)\n" + ] + } + ], + "source": [ + "# Cluster and minimize the data\n", + "df, route_1_coordinates, route_2_coordinates = utils.cluster_and_minimize(TotalList, centroids, norm_centroids, 0.5)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:45.784650Z", + "start_time": "2023-11-06T18:51:22.513160Z" + } + }, + "id": "a1a3e446594e8c20" + }, + { + "cell_type": "markdown", + "source": [ + "# Map" + ], + "metadata": { + "collapsed": false + }, + "id": "dc35d41885a19079" + }, + { + "cell_type": "code", + "execution_count": 10, + "outputs": [ + { + "data": { + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "# Create a new map with the new coordinates\n", + "m = folium.Map(location=[42.3601, -71.0589], zoom_start=12)\n", + "\n", + "# Plot the centroids on the map\n", + "for i in range(len(centroids)):\n", + " folium.Marker(centroids[i], popup='Centroid ' + str(i), icon=folium.Icon(color='black')).add_to(m)\n", + "\n", + "# Add the points to the map with different colors for each cluster\n", + "for i, row in df.iterrows():\n", + " if row['cluster'] == 0:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='red')).add_to(m)\n", + " elif row['cluster'] == 1:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='blue')).add_to(m)\n", + " elif row['cluster'] == 2:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='green')).add_to(m)\n", + " elif row['cluster'] == 3:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='purple')).add_to(m)\n", + " elif row['cluster'] == 4:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='orange')).add_to(m)\n", + " elif row['cluster'] == 5:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='darkred')).add_to(m)\n", + " elif row['cluster'] == 6:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='lightred')).add_to(m)\n", + " elif row['cluster'] == 7:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='beige')).add_to(m)\n", + " elif row['cluster'] == 8:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='darkblue')).add_to(m)\n", + " elif row['cluster'] == 9:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='lightblue')).add_to(m)\n", + " elif row['cluster'] == 10:\n", + " folium.Marker([row['gps'][0], row['gps'][1]], popup=row['name'], icon=folium.Icon(color='cadet')).add_to(m)\n", + "\n", + "# Display the map\n", + "m" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:45.869346Z", + "start_time": "2023-11-06T18:51:45.791672Z" + } + }, + "id": "de9c2f7b892b1bee" + }, + { + "cell_type": "code", + "execution_count": 10, + "outputs": [], + "source": [], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-06T18:51:45.869482Z", + "start_time": "2023-11-06T18:51:45.865159Z" + } + }, + "id": "b50ee3d4d6e09be9" + } + ], + "metadata": { + "kernelspec": { + "display_name": "Python 3", + "language": "python", + "name": "python3" + }, + "language_info": { + "codemirror_mode": { + "name": "ipython", + "version": 2 + }, + "file_extension": ".py", + "mimetype": "text/x-python", + "name": "python", + "nbconvert_exporter": "python", + "pygments_lexer": "ipython2", + "version": "2.7.6" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} diff --git a/utils.py b/utils.py index 880dd2a..7f6a408 100644 --- a/utils.py +++ b/utils.py @@ -1,9 +1,53 @@ import folium import pandas as pd import requests +from sklearn.cluster import KMeans + + +# Given a dataframe of coordinates and centroids, cluster the coordinates, minimize the time difference, and return the routes +def cluster_and_minimize(df, centroids, norm_centroids, time_diff): + # Cluster the coordinates + kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) + + # Fit the coordinates to the clusters + kmeans.fit(df['normalized_gps'].values.tolist()) + + # Add the cluster labels to the dataframe + df['cluster'] = kmeans.labels_ + + # Create centroid strings + centroid_1 = list_to_string([centroids[0]]) + ';' + centroid_2 = list_to_string([centroids[1]]) + ';' + + # Return the list of locations in each cluster + route_1 = df[df['cluster'] == 0] + route_1_stops = len(route_1['gps'].values.tolist()) + route_1_str = list_to_string(route_1['gps'].values.tolist()) + + route_2 = df[df['cluster'] == 1] + route_2_stops = len(route_2['gps'].values.tolist()) + route_2_str = list_to_string(route_2['gps'].values.tolist()) + + # Get the trip time for each route + trip_hrs_1 = get_trip_time(centroid_1 + route_1_str, route_1_stops) + trip_hrs_2 = get_trip_time(centroid_2 + route_2_str, route_2_stops) + + # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference + if abs(trip_hrs_1 - trip_hrs_2) > time_diff: + route_1_coordinates, route_2_coordinates = minimize_route_time_diff(route_1['gps'].values.tolist(), + route_2['gps'].values.tolist(), + centroid_1, centroid_2, time_diff) + else: + route_1_coordinates = route_1['gps'].values.tolist() + route_2_coordinates = route_2['gps'].values.tolist() + + # Edit the dataframe to reflect the new coordinate clusters + df.loc[df['gps'].astype(str).isin(map(str, route_1_coordinates)), 'cluster'] = 0 + df.loc[df['gps'].astype(str).isin(map(str, route_2_coordinates)), 'cluster'] = 1 + + return df, route_1_coordinates, route_2_coordinates -# make a function that turns a list of lists of coordinates into a string def list_to_string(list_of_lists): """ Takes a list of lists of coordinates and returns a string of the coordinates @@ -11,6 +55,8 @@ def list_to_string(list_of_lists): string = '' for i in list_of_lists: string += str(i[1]) + ',' + str(i[0]) + ';' + + string = string[:-1] return string @@ -33,11 +79,120 @@ def create_json_df(coordinate_string): return df -def get_trip_time(coordinate_string): +def get_trip_time(coordinate_string, num_waypoints): """ Takes a list of lists of coordinates and returns the time of the trip in hours """ coordinates = requests.get('http://acetyl.net:5000/trip/v1/bike/' + coordinate_string) coordinates = coordinates.json() - return int(coordinates['trips'][0]['duration']) / 3600 + travel_time_seconds = int(coordinates['trips'][0]['duration']) + waypoint_time_seconds = num_waypoints * 60 + + total_time_hours = (travel_time_seconds + waypoint_time_seconds) / 3600 + + return total_time_hours + + +def normalize_gps(coordinates, centroids): + """ + Takes a list of lists of coordinates and centroids and returns a list of lists of normalized coordinates and centroids + """ + + # Create a list of latitudes and longitudes + latitudes = [i[0] for i in coordinates] + longitudes = [i[1] for i in coordinates] + + # Find the minimum and maximum latitudes and longitudes + min_lat = min(latitudes) + max_lat = max(latitudes) + min_lon = min(longitudes) + max_lon = max(longitudes) + + # Normalize the coordinates and centroids using min-max normalization + normalized_coordinates = [] + normalized_centroids = [] + + for i in coordinates: + normalized_coordinates.append( + [__min_max_normalize__(i[0], min_lat, max_lat), __min_max_normalize__(i[1], min_lon, max_lon)]) + for i in centroids: + normalized_centroids.append( + [__min_max_normalize__(i[0], min_lat, max_lat), __min_max_normalize__(i[1], min_lon, max_lon)]) + + return normalized_coordinates, normalized_centroids + + +def __min_max_normalize__(value, min_value, max_value): + """ + Takes a value, min value, and max value and returns the normalized value + """ + return (value - min_value) / (max_value - min_value) + + +def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_start, route_2_start, + time_diff): + """ + Takes two routes and a time difference and returns a route that is the same length as the shorter route but has a time difference that is less than the time difference + """ + # Find the difference in time between the two routes + route_1_time = get_trip_time(route_1_start + list_to_string(route_1_coordinates), + len(route_1_coordinates)) + route_2_time = get_trip_time(route_2_start + list_to_string(route_2_coordinates), + len(route_2_coordinates)) + route_time_diff = abs(route_1_time - route_2_time) + + # If the difference in time is greater than the time difference, move the closest coordinate from the longer route to the shorter route + if route_time_diff > time_diff: + # Find which route is longer + if len(route_1_coordinates) > len(route_2_coordinates): + longer_route = route_1_coordinates + shorter_route = route_2_coordinates + + # Move the closest coordinate from the longer route to the shorter route + closest_coordinate = move_coordinate(longer_route, shorter_route) + longer_route.remove(closest_coordinate) + shorter_route.append(closest_coordinate) + + # Recursively call the function + return minimize_route_time_diff(longer_route, shorter_route, route_1_start, route_2_start, time_diff) + + else: + longer_route = route_2_coordinates + shorter_route = route_1_coordinates + + # Move the closest coordinate from the longer route to the shorter route + closest_coordinate = move_coordinate(longer_route, shorter_route) + longer_route.remove(closest_coordinate) + shorter_route.append(closest_coordinate) + + # Recursively call the function + return minimize_route_time_diff(shorter_route, longer_route, route_1_start, route_2_start, time_diff) + + # If the difference in time is less than the time difference, return the routes + return route_1_coordinates, route_2_coordinates + + +# Given two clusters and their respective lists of coordinates, move one coordinate from the larger centroid to the smaller centroid +def move_coordinate(larger_centroid_coordinates, smaller_centroid_coordinates): + # Calculate the centroid of the smaller cluster + smaller_centroid = [sum([i[0] for i in smaller_centroid_coordinates]) / len(smaller_centroid_coordinates), + sum([i[1] for i in smaller_centroid_coordinates]) / len(smaller_centroid_coordinates)] + + # Find the coordinate in larger_centroid_coordinates that is closest to smaller_centroid + closest_coordinate = larger_centroid_coordinates[0] + closest_coordinate_distance = __distance__(closest_coordinate, smaller_centroid) + + for coordinate in larger_centroid_coordinates: + if __distance__(coordinate, smaller_centroid) < closest_coordinate_distance: + closest_coordinate = coordinate + closest_coordinate_distance = __distance__(coordinate, smaller_centroid) + + return closest_coordinate + + +def __distance__(coordinate1, coordinate2): + """ + Takes two coordinates and returns the distance between them + """ + return ((coordinate1[0] - coordinate2[0]) ** 2 + (coordinate1[1] - coordinate2[1]) ** 2) ** 0.5 -- cgit v1.2.3