BackwardSelection.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Feature Selection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Backward Selection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv('diabetes.csv')\n",
    "del df['Outcome']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's predict BMI\n",
    "features = ['Pregnancies', 'Glucose', 'BloodPressure', 'SkinThickness', \n",
    "            'Insulin', 'DiabetesPedigreeFunction']\n",
    "X = df.loc[:, features].values\n",
    "y = df.loc[:, ['BMI']].values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Model: Linear Regression\n",
    "class LinReg:\n",
    "    \"\"\"\n",
    "    This implementation uses the Newton's Method for optimization.\n",
    "    \"\"\"\n",
    "    def __init__(self, num_iters=5, tolerance = 1e-10, epsilon = 10e-8):\n",
    "        self.num_iters = num_iters\n",
    "        self.tolerance = tolerance\n",
    "        self.epsilon = epsilon # subtracted to make hessian invertible\n",
    "        \n",
    "    def add_ones(self, X):\n",
    "        return np.concatenate((np.ones((len(X),1)), X), axis = 1)\n",
    "    \n",
    "    def cost(self, X, y_true):\n",
    "        return np.mean((X@self.theta - y_true)**2)\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        X = X.copy()\n",
    "        X = self.add_ones(X)\n",
    "        y = y.reshape(-1, 1)\n",
    "        \n",
    "        self.theta = np.zeros((len(X[0]), 1))\n",
    "        hessian_inv = np.linalg.inv(X.T@X + self.epsilon*np.eye(X.T.shape[0]))\n",
    "        current_iter = 1\n",
    "        norm = 1\n",
    "        while (norm >= self.tolerance and current_iter < self.num_iters):\n",
    "            old_theta = self.theta.copy()\n",
    "            grad = (X.T@X)@self.theta - X.T@y\n",
    "            #grad = (1/len(X)) * np.sum((X@self.theta - y)*X, axis=0)\n",
    "            grad= grad.reshape(-1, 1)\n",
    "            self.theta = self.theta - hessian_inv@grad\n",
    "            \n",
    "            #print(f'cost for {current_iter} iteration : {self.cost(X, y)}')\n",
    "            norm = np.linalg.norm(old_theta - self.theta)\n",
    "            current_iter += 1\n",
    "            \n",
    "        return self.theta\n",
    "    \n",
    "    def evaluate(self, X, y):\n",
    "        X = self.add_ones(X)\n",
    "        return self.cost(X, y)\n",
    "    \n",
    "    def predict(self, X):\n",
    "        X = self.add_ones(X)\n",
    "        \n",
    "        return X@self.theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KFoldCrossVal:\n",
    "    \"\"\"\n",
    "    Performs k-fold cross validation on each combination of hyperparameter set\n",
    "    \n",
    "    Input\n",
    "    ............\n",
    "    X : Features (m, n)\n",
    "    y : target (m, 1)\n",
    "    hyperparameter_Set : Dictionary of hyperparameters for k-fold\n",
    "    num_of_folds: Number of folds, k; default:10\n",
    "    verbose: Checks whether to print parameters on every iteration; Boolean; Default: False\n",
    "    \"\"\"\n",
    "    def __init__(self, hyperparameter_set, num_of_folds=10, verbose=True):\n",
    "        self.hyperparameter_set = hyperparameter_set\n",
    "        self.k = num_of_folds\n",
    "        self.verbose = verbose\n",
    "    \n",
    "    import sys\n",
    "    if ('numpy' not in sys.modules) and ('np' not in dir()): #import numpy if not done\n",
    "        import numpy as np\n",
    "    \n",
    "    #def get_model_no(self):\n",
    "        \n",
    "        \n",
    "    def shuffle_data(self, X, y):\n",
    "        shuffle_arr = np.random.permutation(len(X))\n",
    "        X_shuffled = X[shuffle_arr]\n",
    "        y_shuffled = y[shuffle_arr].reshape(-1, 1)\n",
    "        \n",
    "        return X_shuffled, y_shuffled\n",
    "    \n",
    "    def get_kfold_arr_index(self, subset_size, last_index):\n",
    "        array_indexes = [0]\n",
    "        for fold_no in range(self.k):\n",
    "            if fold_no != (self.k-1):\n",
    "                array_indexes.append((fold_no+1)*subset_size)\n",
    "            elif fold_no == (self.k - 1): # To accomodate examples not part of the \n",
    "                array_indexes.append(last_index) #for last index\n",
    "        return array_indexes\n",
    "    \n",
    "    def get_split_data_fold(self, X, y, array_indexes, fold_no):\n",
    "        start = array_indexes[fold_no]\n",
    "        end = array_indexes[fold_no+1]\n",
    "        X_val = X[start: end]\n",
    "        y_val = y[start: end]\n",
    "        \n",
    "        X_train = np.delete(X, [start,end], axis=0)\n",
    "        y_train = np.delete(y, [start,end]).reshape(-1,1)\n",
    "        \n",
    "        return X_train, y_train, X_val, y_val\n",
    "    \n",
    "    def get_hyperparameter_sets(self, hyperparameter_dict):   \n",
    "        \"\"\"\n",
    "        Converts the hyperparameter dictionary into all possible combinations of hyperparameters\n",
    "\n",
    "        Return\n",
    "        ..............\n",
    "        Array of hyperparameter set\n",
    "        \"\"\"\n",
    "        import itertools\n",
    "\n",
    "        parameter_keys = hyperparameter_dict.keys()\n",
    "        parameter_values = hyperparameter_dict.values()\n",
    "\n",
    "        parameter_array = []\n",
    "        for params in itertools.product(*parameter_values):\n",
    "            parameter_array.append(params)\n",
    "\n",
    "        parameter_sets = []\n",
    "        for parameter_values in parameter_array:\n",
    "            parameter_set = dict(zip(parameter_keys, parameter_values))\n",
    "            parameter_sets.append(parameter_set)\n",
    "\n",
    "        return parameter_sets\n",
    "    \n",
    "    def evaluate(self, X, y):\n",
    "        models = self.get_hyperparameter_sets(self.hyperparameter_set)\n",
    "        \n",
    "        #print(f'Performing k-fold for {len(models)} models and {len(models) * self.k} cross validations' )\n",
    "        m = len(X)\n",
    "        \n",
    "        generalization_mse = []\n",
    "        X, y = self.shuffle_data(X, y)\n",
    "        subset_size = int(m/self.k)\n",
    "        \n",
    "        array_indexes = self.get_kfold_arr_index(subset_size, m+1)\n",
    "        \n",
    "        for hyperparameters in models:\n",
    "            model = LinReg(**hyperparameters)\n",
    "            fold_mse_arr = []\n",
    "            for fold_no in range(self.k - 1):\n",
    "                X_train, y_train, X_val, y_val = self.get_split_data_fold(X, y, array_indexes, fold_no)\n",
    "                model.fit(X_train, y_train)\n",
    "                mse = model.evaluate(X_val, y_val)\n",
    "                fold_mse_arr.append(mse)\n",
    "            cv_mse = np.mean(fold_mse_arr)\n",
    "            if self.verbose:\n",
    "                print(f'{hyperparameters}, mse: {cv_mse}')\n",
    "            generalization_mse.append(cv_mse)\n",
    "            \n",
    "        lowest_gen_mse_index = np.argmin(generalization_mse)\n",
    "        lowest_mse = generalization_mse[lowest_gen_mse_index]\n",
    "        best_model = models[lowest_gen_mse_index]\n",
    "        \n",
    "        return lowest_mse, best_model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "hyp = {\n",
    "    'num_iters': [1, 2, 3, 4],\n",
    "    'tolerance': [1e-3, 1e-5, 1e-7, 1e-10],\n",
    "    'epsilon': [10e-6, 10e-8, 10e-10]\n",
    "}\n",
    "\n",
    "kcv = KFoldCrossVal(hyp, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(48.3329429265649, {'num_iters': 2, 'tolerance': 0.001, 'epsilon': 1e-05})"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kcv.evaluate(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backward Selection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Assuming this is our chosen best hyperparameters\n",
    "hyperparams = {\n",
    "    'num_iters': [4],\n",
    "    'tolerance': [1e-8],\n",
    "    'epsilon': [10e-10]\n",
    "}\n",
    "\n",
    "X_fs = df.loc[:, features]\n",
    "y_fs = df.loc[:, ['BMI']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SelectFeatureBackward:\n",
    "    \"\"\"\n",
    "    input\n",
    "    ................\n",
    "    num_of_features : Total features to return; default: 'all'\n",
    "    \"\"\"\n",
    "    def __init__(self, max_features):\n",
    "            self.max_features = max_features \n",
    "    \n",
    "    def get_best_feat_subset(self, sub_feature_map):\n",
    "        \"\"\"\n",
    "        input\n",
    "        ..........\n",
    "        sub_feature_map : dictionary of features and their mse\n",
    "        output\n",
    "        ..........\n",
    "        best_feature_set: array of features\n",
    "        \"\"\"\n",
    "        sorted_feat = sorted(sub_feature_map.items(), key=lambda x: x[1])\n",
    "        return sorted_feat[0]\n",
    "        \n",
    "    def evaluate(self, X, y):\n",
    "        \"\"\"\n",
    "        input\n",
    "        .....\n",
    "        X : Input features, dtype: DataFrame\n",
    "        y : target, dtype: DataFrame or Series\n",
    "        \n",
    "        output\n",
    "        ......\n",
    "        Best Feature Set\n",
    "        \"\"\"\n",
    "        feature_map = {}\n",
    "        #while feature_set:\n",
    "        features = X.columns.to_list()\n",
    "        feature_set = features\n",
    "        \n",
    "        while (len(feature_set)-1 >= self.max_features):\n",
    "            sub_feature_map = {}\n",
    "            for feature in feature_set:\n",
    "                sub_feature_set = list(set(feature_set) - set([feature]))\n",
    "                cv = KFoldCrossVal(hyperparams, verbose=False)\n",
    "                mse, _ = cv.evaluate(X.loc[:, sub_feature_set].values, y.values)\n",
    "                sub_feature_map[tuple(sub_feature_set)] = mse # Stores the feature sets for each n feature combinations\n",
    "                feature_map[tuple(sub_feature_set)] = mse # Stores the global feature sets\n",
    "            old_feature_set = feature_set[:]\n",
    "            feature_set = self.get_best_feat_subset(sub_feature_map)[0]\n",
    "        #print(pd.DataFrame(feature_map.items(), columns=['feature set', 'mse']))\n",
    "        return self.get_best_feat_subset(feature_map), feature_map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "fs = SelectFeatureBackward(max_features=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "best_feature, feature_map = fs.evaluate(X_fs, y_fs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(('Glucose', 'SkinThickness', 'BloodPressure', 'Insulin'), 45.184025392126976)"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_feature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>feature set</th>\n",
       "      <th>mse</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>(BloodPressure, Insulin, DiabetesPedigreeFunct...</td>\n",
       "      <td>46.922693</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>(BloodPressure, Insulin, DiabetesPedigreeFunct...</td>\n",
       "      <td>49.478214</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>(Insulin, DiabetesPedigreeFunction, SkinThickn...</td>\n",
       "      <td>49.426553</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>(BloodPressure, Insulin, DiabetesPedigreeFunct...</td>\n",
       "      <td>49.371143</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>(BloodPressure, DiabetesPedigreeFunction, Skin...</td>\n",
       "      <td>47.674274</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>(BloodPressure, Insulin, SkinThickness, Glucos...</td>\n",
       "      <td>51.265967</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>(DiabetesPedigreeFunction, Glucose, SkinThickn...</td>\n",
       "      <td>48.620183</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>(DiabetesPedigreeFunction, Glucose, SkinThickn...</td>\n",
       "      <td>48.963146</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>(Glucose, SkinThickness, BloodPressure, Insulin)</td>\n",
       "      <td>45.184025</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>(DiabetesPedigreeFunction, Glucose, BloodPress...</td>\n",
       "      <td>52.296992</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>(DiabetesPedigreeFunction, SkinThickness, Bloo...</td>\n",
       "      <td>50.744176</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>(SkinThickness, BloodPressure, Insulin)</td>\n",
       "      <td>51.359542</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>(Glucose, BloodPressure, Insulin)</td>\n",
       "      <td>54.393225</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>(SkinThickness, Glucose, Insulin)</td>\n",
       "      <td>49.717786</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>(Glucose, SkinThickness, BloodPressure)</td>\n",
       "      <td>46.835160</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>(SkinThickness, BloodPressure)</td>\n",
       "      <td>51.208994</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>(Glucose, BloodPressure)</td>\n",
       "      <td>53.035247</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>(SkinThickness, Glucose)</td>\n",
       "      <td>52.768340</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                          feature set        mse\n",
       "0   (BloodPressure, Insulin, DiabetesPedigreeFunct...  46.922693\n",
       "1   (BloodPressure, Insulin, DiabetesPedigreeFunct...  49.478214\n",
       "2   (Insulin, DiabetesPedigreeFunction, SkinThickn...  49.426553\n",
       "3   (BloodPressure, Insulin, DiabetesPedigreeFunct...  49.371143\n",
       "4   (BloodPressure, DiabetesPedigreeFunction, Skin...  47.674274\n",
       "5   (BloodPressure, Insulin, SkinThickness, Glucos...  51.265967\n",
       "6   (DiabetesPedigreeFunction, Glucose, SkinThickn...  48.620183\n",
       "7   (DiabetesPedigreeFunction, Glucose, SkinThickn...  48.963146\n",
       "8    (Glucose, SkinThickness, BloodPressure, Insulin)  45.184025\n",
       "9   (DiabetesPedigreeFunction, Glucose, BloodPress...  52.296992\n",
       "10  (DiabetesPedigreeFunction, SkinThickness, Bloo...  50.744176\n",
       "11            (SkinThickness, BloodPressure, Insulin)  51.359542\n",
       "12                  (Glucose, BloodPressure, Insulin)  54.393225\n",
       "13                  (SkinThickness, Glucose, Insulin)  49.717786\n",
       "14            (Glucose, SkinThickness, BloodPressure)  46.835160\n",
       "15                     (SkinThickness, BloodPressure)  51.208994\n",
       "16                           (Glucose, BloodPressure)  53.035247\n",
       "17                           (SkinThickness, Glucose)  52.768340"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.DataFrame(feature_map.items(), columns=['feature set', 'mse'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}