python/final-adaboost.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline\n",
    "import numpy as np\n",
    "from sklearn.datasets import make_classification\n",
    "num_egs = 5\n",
    "num_features = 1\n",
    "num_classifiers = 3\n",
    "\n",
    "X = np.zeros((num_egs,num_features))\n",
    "labels = np.zeros(num_egs)\n",
    "X[0][0]=10; labels[0] = 1;\n",
    "X[1][0]=30; labels[1] = 1;\n",
    "X[2][0]=40; labels[2] = -1;\n",
    "X[3][0]=60; labels[3] = -1;\n",
    "X[4][0]=90; labels[4] = 1;\n",
    "\n",
    "# X[0][1]=40; \n",
    "# X[1][1]=50; \n",
    "# X[2][1]=40; \n",
    "# X[3][1]=50; \n",
    "# X[4][1]=40; \n",
    "\n",
    "# X[0][0] = -1; labels[0] = -1;\n",
    "# X[1][0] = 0; labels[1] = 1;\n",
    "# X[2][0] = 1; labels[2] = -1;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import argparse\n",
    "\n",
    "args = parser.parse_args()\n",
    "\n",
    "parser = argparse.ArgumentParser(description='Create Dataset.')\n",
    "parser.add_argument('n', metavar='N', type=int,\n",
    "                    help='num examples')\n",
    "parser.add_argument('m', metavar='M', type=int,\n",
    "                    help='num fetures'\n",
    "\n",
    "\n",
    "x,y = datasets.make_classification(n_samples=1000, n_features=200)\n",
    "y[y==0]=-1\n",
    "pd.DataFrame(x).to_csv('data/{}_{}_data.csv'.format(args.n, argms.m),index=False,header=False)\n",
    "pd.DataFrame(y).to_csv('data/{}_{}_label.csv'.format(args.n, argms.m),index=False,header=False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# C++ like data structure\n",
    "class Decision_Function():\n",
    "    def __init__(self, error, direction, split_val, feature_index = -99, alpha=1):\n",
    "        self.error = error\n",
    "        self.direction = direction\n",
    "        self.split_val = split_val\n",
    "        self.feature_index = feature_index\n",
    "        self.alpha = alpha\n",
    "\n",
    "\n",
    "class DecisionStump():\n",
    "    def __init__(self, criteria='gini'):\n",
    "        self.criteria = criteria\n",
    "\n",
    "#     def get_ginni_curr_feature_val(self, labels, weights, feature_vals, split_value):\n",
    "#         left = []\n",
    "#         right = []\n",
    "#         leftweight = []\n",
    "#         rightweight = []\n",
    "#         gini = 0\n",
    "#         for i in range(self.num_egs):\n",
    "#             if (feature_vals[i] <= split_value):\n",
    "#                 left.append(labels[i])\n",
    "#                 leftweight.append(weights[i])\n",
    "#             else:\n",
    "#                 right.append(labels[i])\n",
    "#                 rightweight.append(weights[i])\n",
    "#         for group, weight in ([(left, leftweight), (right, rightweight)]):\n",
    "#             size = float(len(group))\n",
    "#             wt_of_group = sum([i for i in weight])\n",
    "#             if size == 0:\n",
    "#                 continue\n",
    "#             score = 0.0\n",
    "#             p1 = 0\n",
    "#             p2 = 0\n",
    "#             for i, label in enumerate(group):\n",
    "#                 if label == 1:\n",
    "#                     p1 += weight[i] * 1/wt_of_group\n",
    "#                 else:\n",
    "#                     p2 += weight[i] * 1/wt_of_group\n",
    "#             score = p1 * p1 + p2 * p2 \n",
    "#             gini += (1.0 - score) * wt_of_group\n",
    "#         return gini\n",
    "        \n",
    "    def get_error_curr_feature_val(self, labels, weights, feature_vals, split_value):\n",
    "        curr_error = 0\n",
    "        for i in range(self.num_egs):\n",
    "            # x[i] < c should be -1\n",
    "            if  ((feature_vals[i] <= split_value) and (labels[i]!=-1)) or \\\n",
    "                ((feature_vals[i] > split_value) and (labels[i]!=1)):\n",
    "                curr_error += weights[i];\n",
    "            \n",
    "        sol = Decision_Function(curr_error, 1, split_value)\n",
    "#         gini1 = self.get_ginni_curr_feature_val(labels, weights, feature_vals, split_value)\n",
    "#         print(\"Error : {:.2f} \\t Gini : {:.2f}\".format(curr_error, self.get_ginni_curr_feature_val(labels, weights, feature_vals, split_value)))\n",
    "        if curr_error > 0.5:\n",
    "            sol.direction = -1\n",
    "            sol.error = 1 - curr_error\n",
    "        return sol\n",
    "        \n",
    "    \n",
    "    def get_error_curr_feature(self, labels, weights, feature_vals, feature_split_values):\n",
    "        best_decision_function_curr_feature = Decision_Function(float('inf'), 1, float('inf'))\n",
    "        \n",
    "        for i in range(len(feature_split_values)):\n",
    "            curr_decision_function = self.get_error_curr_feature_val(labels, weights, feature_vals, feature_split_values[i])\n",
    "            \n",
    "            if curr_decision_function.error < best_decision_function_curr_feature.error:\n",
    "                best_decision_function_curr_feature = curr_decision_function\n",
    "            \n",
    "        return best_decision_function_curr_feature\n",
    "    \n",
    "    def fit(self, labels, X_T, weights, feature_split_values):\n",
    "        \n",
    "        self.num_features = len(X_T)\n",
    "        self.num_egs = len(X_T[0])\n",
    "        \n",
    "        best_decision_function = Decision_Function(float('inf'), 1, float('inf'))\n",
    "        \n",
    "        for i in range(self.num_features):\n",
    "            current_feature_stump = self.get_error_curr_feature(labels, weights, X_T[i], \n",
    "                                                            feature_split_values[i])\n",
    "            if current_feature_stump.error < best_decision_function.error:\n",
    "                best_decision_function = current_feature_stump\n",
    "                best_decision_function.feature_index = i\n",
    "        return best_decision_function\n",
    "\n",
    "class AdaBoost():\n",
    "    def __init__(self, num_classifiers=3):\n",
    "        self.num_classifiers = num_classifiers\n",
    "        self.classifiers = None\n",
    "    def get_feature_split_vals(self, X_T):\n",
    "        '''\n",
    "            Args:\n",
    "                x : dataset\n",
    "                \n",
    "            Returns:\n",
    "                feature_midpoints : For each feature returns a sorted list of mid points \n",
    "                                    of every two consecutive unique features\n",
    "            \n",
    "            Complexity:\n",
    "               (Old) :  M + N * M + M * NlogN + M * N\n",
    "               (New) : M * N log N + M * N\n",
    "        '''\n",
    "        \n",
    "        X_copy = []     \n",
    "        feature_midpoints = []\n",
    "\n",
    "        # M * n log * n\n",
    "        for i in range(self.num_features):\n",
    "            X_copy.append(sorted(X_T[i]))\n",
    "        \n",
    "        # Get mid points of sorted unique values M * N\n",
    "        \n",
    "        for i in range(self.num_features):\n",
    "            current = []\n",
    "            j = 0\n",
    "            current.append(X_copy[i][0] - 1)\n",
    "            while (j < self.num_egs - 1):\n",
    "                k = j + 1\n",
    "                while(X_copy[i][j] == X_copy[i][k] and k < self.num_egs - 1):\n",
    "                    k += 1\n",
    "                midpoint = (X_copy[i][j] + X_copy[i][k])/2\n",
    "                current.append(midpoint)\n",
    "                j = k\n",
    "            current.append(X_copy[i][self.num_egs - 1] + 1)\n",
    "            feature_midpoints.append(current)\n",
    "        return feature_midpoints\n",
    "    \n",
    "    def update_weights(self, classifier, X_T, weights, labels):\n",
    "\n",
    "        Z = 0\n",
    "        feature_index = classifier.feature_index\n",
    "        \n",
    "        for i in range(self.num_egs):\n",
    "            if classifier.direction == 1:\n",
    "                if X_T[feature_index][i] <= classifier.split_val:\n",
    "                    weights[i] *= np.exp(classifier.alpha * labels[i])\n",
    "                else:\n",
    "                    weights[i] *= np.exp(-classifier.alpha * labels[i])\n",
    "            elif classifier.direction == -1:\n",
    "                if X_T[feature_index][i] >= classifier.split_val:\n",
    "                    weights[i] *= np.exp(classifier.alpha * labels[i])\n",
    "                else:\n",
    "                    weights[i] *= np.exp(-classifier.alpha * labels[i])\n",
    "            Z += weights[i]\n",
    "\n",
    "        return weights/Z\n",
    "\n",
    "    \n",
    "    def fit_weak_classifers(self, labels, X_T, feature_split_values):\n",
    "        weights = np.ones(self.num_egs)/(self.num_egs)\n",
    "        classifiers = []\n",
    "        for t in range(self.num_classifiers): \n",
    "            clf = DecisionStump()\n",
    "            classifiers.append(clf.fit(labels, X_T, weights, feature_split_values))\n",
    "            alpha = np.log((1 - classifiers[-1].error)/classifiers[-1].error) * 0.5\n",
    "            classifiers[-1].alpha = alpha\n",
    "            weights = self.update_weights(classifiers[-1], X_T, weights, labels) \n",
    "\n",
    "#             print(\"t : {} \\t alpha : {:.2f} \\t ft_index : {} \\t direction : {:2} \\t split_value : {} \\t error : {:.2f}\".format(\n",
    "#             t, classifiers[-1].alpha, classifiers[-1].feature_index, classifiers[-1].direction, classifiers[-1].split_val, classifiers[-1].error))\n",
    "            \n",
    "        return classifiers\n",
    "\n",
    "    def fit(self, X, labels):\n",
    "        self.num_egs = len(X)\n",
    "        self.num_features = len(X[0])\n",
    "        X_T = X.T\n",
    "        feature_split_values = self.get_feature_split_vals(X_T)\n",
    "        classifiers = self.fit_weak_classifers(labels, X_T,feature_split_values )\n",
    "        self.classifiers = classifiers\n",
    "    def predict(self, X):\n",
    "        a = 0\n",
    "        predicted = np.zeros(len(X))\n",
    "\n",
    "        for num, eg in enumerate(X):\n",
    "            a = 0\n",
    "            for clf in self.classifiers:\n",
    "                if clf.direction == 1:\n",
    "                    if eg[int(clf.feature_index)] <= clf.split_val:\n",
    "                        a += clf.alpha * -1\n",
    "                    else:\n",
    "                        a += clf.alpha\n",
    "                else:\n",
    "                    if eg[int(clf.feature_index)] >= clf.split_val:\n",
    "                        a += clf.alpha * -1\n",
    "                    else:\n",
    "                        a += clf.alpha\n",
    "            predicted[num] = np.sign(a)\n",
    "        return predicted\n",
    "#         for t in range(self.num_classifiers):\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "169 µs ± 18.4 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([ 1.,  1., -1., -1.,  1.])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf = AdaBoost(num_classifiers=3)\n",
    "%timeit clf.fit(X,labels)\n",
    "clf.predict(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = AdaBoost(num_classifiers=10)\n",
    "clf.fit(X,labels)"
   ]
  },
  {
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}