{"cells":[
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "\r\n__author__ = 'Michael Hartman'\r\n\r\n'''Inspired by several scripts at:\r\nhttps://www.kaggle.com/c/facebook-v-predicting-check-ins/scripts\r\nSpecial thanks to Sandro for starting the madness. :-)\r\nhttps://www.kaggle.com/svpons/facebook-v-predicting-check-ins/grid-plus-classifier\r\n'''\r\n\r\nimport numpy as np\r\nimport pandas as pd\r\nfrom sklearn.neighbors import KNeighborsClassifier\r\nimport time\r\nfrom datetime import timedelta\r\nimport gc\r\n\r\n# Found at: https://www.kaggle.com/rshekhar2/facebook-v-predicting-check-ins/xgboost-cv-example-with-small-bug\r\ndef mapkprecision(truthvalues, predictions):\r\n    '''\r\n    This is a faster implementation of MAP@k valid for numpy arrays.\r\n    It is only valid when there is one single truth value. \r\n\r\n    m ~ number of observations\r\n    k ~ MAP at k -- in this case k should equal 3\r\n\r\n    truthvalues.shape = (m,) \r\n    predictions.shape = (m, k)\r\n    '''\r\n    z = (predictions == truthvalues[:, None]).astype(np.float32)\r\n    weights = 1./(np.arange(predictions.shape[1], dtype=np.float32) + 1.)\r\n    z = z * weights[None, :]\r\n    return np.mean(np.sum(z, axis=1))\r\n\r\ndef load_data(data_name):\r\n    types = {'row_id': np.dtype(np.int32),\r\n         'x': np.dtype(float),\r\n         'y' : np.dtype(float),\r\n         'accuracy': np.dtype(np.int16),\r\n         'place_id': np.int64,\r\n         'time': np.dtype(np.int32)}\r\n    df = pd.read_csv(data_name, dtype=types, index_col = 0, na_filter=False)\r\n    return df\r\n\r\ndef process_one_cell(df_cell_train, df_cell_test, fw, th, n_neighbors):\r\n    \r\n    # Remove infrequent places\r\n    df_cell_train = remove_infrequent_places(df_cell_train, th).copy()\r\n    \r\n    # Store row_ids for test\r\n    row_ids = df_cell_test.index\r\n    \r\n    # Preparing data\r\n    y = df_cell_train.place_id.values\r\n    X = df_cell_train.drop(['place_id'], axis=1).values\r\n    \r\n    #Applying the classifier\r\n    clf = KNeighborsClassifier(n_neighbors=n_neighbors,\r\n                            weights=calculate_distance, p=1, \r\n                            n_jobs=2, leaf_size=20)\r\n    clf.fit(X, y)\r\n    y_pred = clf.predict_proba(df_cell_test.values)\r\n    y_pred_labels = np.argsort(y_pred, axis=1)[:,:-6:-1]\r\n    pred_labels = clf.classes_[y_pred_labels]\r\n    cell_pred = np.column_stack((row_ids, pred_labels)).astype(np.int64) \r\n    \r\n    return cell_pred\r\n    \r\ndef calculate_distance(distances):\r\n    return distances ** -2\r\n    \r\n# Generate a dictionary of the time limits so it doesn't have to be \r\n# recalculated each loop\r\ndef create_time_dict(t_cuts, time_factor, time_aug):\r\n    \r\n    t_slice = 24 / t_cuts\r\n    time_dict = dict()\r\n    for t in range(t_cuts):\r\n        \r\n        t_min = 2 * np.pi * (t * t_slice * 12 / 288)\r\n        t_max = 2 * np.pi * (((t + 1) * t_slice * 12 - 1) / 288)\r\n        sin_t_start = np.round(np.sin(t_min)+1, 4) * time_factor\r\n        sin_t_stop = np.round(np.sin(t_max)+1, 4) * time_factor\r\n        cos_t_start = np.round(np.cos(t_min)+1, 4) * time_factor\r\n        cos_t_stop = np.round(np.cos(t_max)+1, 4) * time_factor\r\n        #print(t, (sin_t_start, sin_t_stop, cos_t_start, cos_t_stop))\r\n        sin_t_min = min((sin_t_start, sin_t_stop))\r\n        sin_t_max = max((sin_t_start, sin_t_stop))\r\n        cos_t_min = min((cos_t_start, cos_t_stop))\r\n        cos_t_max = max((cos_t_start, cos_t_stop))\r\n\r\n        time_dict[t] = [sin_t_min, sin_t_max, cos_t_min, cos_t_max]\r\n        t_min = 2 * np.pi * ((t * t_slice - time_aug) * 12 / 288)\r\n        t_max = 2 * np.pi * ((((t + 1) * t_slice + time_aug)* 12 - 1) / 288)\r\n        sin_t_start = np.round(np.sin(t_min)+1, 4) * time_factor\r\n        sin_t_stop = np.round(np.sin(t_max)+1, 4) * time_factor\r\n        cos_t_start = np.round(np.cos(t_min)+1, 4) * time_factor\r\n        cos_t_stop = np.round(np.cos(t_max)+1, 4) * time_factor\r\n        sin_t_min = min((sin_t_start, sin_t_stop, sin_t_min))\r\n        sin_t_max = max((sin_t_start, sin_t_stop, sin_t_max))\r\n        cos_t_min = min((cos_t_start, cos_t_stop, cos_t_min))\r\n        cos_t_max = max((cos_t_start, cos_t_stop, cos_t_max))\r\n        time_dict[t] += [sin_t_min, sin_t_max, cos_t_min, cos_t_max]\r\n        \r\n    return time_dict\r\n\r\ndef process_grid(df_train, df_test, x_cuts, y_cuts, t_cuts,\r\n                 x_border_aug, y_border_aug, time_aug, fw, th, n_neighbors):\r\n    preds_list = []\r\n    x_max = 250.0 # df_train['x'].max()\r\n    #print('x_max', x_max)\r\n    x_slice = x_max / x_cuts\r\n    y_max = 590.0 #df_train['y'].max()\r\n    #print('y_max', y_max)\r\n    y_slice = df_train['y'].max() / y_cuts\r\n    time_max = 1.28282 #df_train['minute_sin'].max()\r\n    #print('time_max', time_max)\r\n    time_factor = time_max / 2\r\n    time_dict = create_time_dict(t_cuts, time_factor, time_aug)\r\n    print('Time dictionary prepared')\r\n\r\n    for i in range(x_cuts):\r\n        row_start_time = time.time()\r\n        x_min = x_slice * i\r\n        x_max = x_slice * (i+1)\r\n        x_max += int((i+1) == x_cuts) # expand edge at end\r\n\r\n        mask = (df_test['x'] >= x_min)\r\n        mask = mask & (df_test['x'] < x_max)      \r\n        df_col_test = df_test[mask]\r\n        x_min -= x_border_aug\r\n        x_max += x_border_aug\r\n        mask = (df_train['x'] >= x_min)\r\n        mask = mask & (df_train['x'] < x_max)\r\n        df_col_train = df_train[mask]\r\n\r\n        for j in range(y_cuts):\r\n            y_min = y_slice * j\r\n            y_max = y_slice * (j+1)\r\n            y_max += int((j+1) == y_cuts) # expand edge at end\r\n\r\n            mask = (df_col_test['y'] >= y_min)\r\n            mask= mask & (df_col_test['y'] < y_max)\r\n            df_row_test = df_col_test[mask]\r\n            y_min -= y_border_aug\r\n            y_max += y_border_aug\r\n            mask = (df_col_train['y'] >= y_min)\r\n            mask = mask & (df_col_train['y'] < y_max)\r\n            df_row_train = df_col_train[mask]\r\n\r\n            for t in range(t_cuts):\r\n                #print(df_row_test.shape, df_row_train.shape)\r\n                t_lim = time_dict[t]\r\n                mask = df_row_test['minute_sin'].between(t_lim[0], t_lim[1])\r\n                mask = mask & df_row_test['minute_cos'].between(t_lim[2], t_lim[3])\r\n                df_cell_test = df_row_test[mask].copy()\r\n                mask = df_row_train['minute_sin'].between(t_lim[4], t_lim[5])\r\n                mask = mask & df_row_train['minute_cos'].between(t_lim[6], t_lim[7])\r\n                df_cell_train = df_row_train[mask].copy()\r\n                cell_pred = process_one_cell(df_cell_train.copy(), \r\n                                             df_cell_test.copy(), \r\n                                             fw, th, n_neighbors)\r\n                preds_list.append(cell_pred)\r\n        elapsed = (time.time() - row_start_time)\r\n        print('Row', i, 'completed in:', timedelta(seconds=elapsed))\r\n    preds = np.vstack(preds_list)\r\n    return preds\r\n\r\n# Thank you Alex!\r\n# From: https://www.kaggle.com/drarfc/facebook-v-predicting-check-ins/fastest-way-to-write-the-csv\r\ndef generate_submission(preds):    \r\n    print('Writing submission file')\r\n    print('Pred shape:', preds.shape)\r\n    with open('KNN_submission.csv', \"w\") as out:\r\n        out.write(\"row_id,place_id\\n\")\r\n        rows = ['']*8607230\r\n        n=0\r\n        for num in range(8607230):\r\n            rows[n]='%d,%d %d %d %d %d\\n' % (preds[num,0],preds[num,1],preds[num,2],preds[num,3],preds[num,4],preds[num,5])\r\n            n=n+1\r\n        out.writelines(rows)\r\n\r\ndef validation_split(df, val_start_day):\r\n    day = df['time']//1440\r\n    df_val = df.loc[(day>=val_start_day)].copy()\r\n    df = df.loc[(day<val_start_day)].copy()\r\n    return df, df_val\r\n\r\ndef remove_infrequent_places(df, th=5):\r\n    place_counts = df.place_id.value_counts()\r\n    mask = (place_counts[df.place_id.values] >= th).values\r\n    df = df.loc[mask]\r\n    return df\r\n    \r\ndef prepare_data(datapath, val_start_day):\r\n    val_label = None\r\n    df_train = load_data(datapath + 'train.csv')\r\n    if val_start_day > 0:\r\n        # Create validation data\r\n        df_train, df_test = validation_split(df_train, val_start_day)\r\n        val_label = df_test['place_id']\r\n        df_test.drop(['place_id'], axis=1, inplace=True)\r\n        print('Feature engineering on train')\r\n        df_train = feature_engineering(df_train)\r\n        print('Feature engineering on validation')\r\n        df_test = feature_engineering(df_test)\r\n    else:\r\n        print('Feature engineering on train')\r\n        df_train = feature_engineering(df_train)\r\n        gc.collect()\r\n        df_train = remove_infrequent_places(df_train)\r\n        df_train = df_train.copy()\r\n        gc.collect()\r\n        df_test = load_data(datapath + 'test.csv') \r\n        print('Feature engineering on test')\r\n        df_test = feature_engineering(df_test)\r\n    df_train = apply_weights(df_train, fw)\r\n    df_test = apply_weights(df_test, fw)\r\n    return df_train, df_test, val_label\r\n        \r\n\r\ndef apply_weights(df, fw):\r\n    df['accuracy'] *= fw[0]\r\n    df['day_of_year_sin'] *= fw[1]\r\n    df['day_of_year_cos'] *= fw[1]\r\n    df['minute_sin'] *= fw[2]\r\n    df['minute_cos'] *= fw[2]\r\n    df['weekday_sin'] *= fw[3]\r\n    df['weekday_cos'] *= fw[3]\r\n    df.x *= fw[4]\r\n    df.y *= fw[5]\r\n    df['year'] *= fw[6]\r\n    return df\r\n    \r\ndef feature_engineering(df):\r\n    minute = 2*np.pi*((df[\"time\"]//5)%288)/288\r\n    df['minute_sin'] = (np.sin(minute)+1).round(4)\r\n    df['minute_cos'] = (np.cos(minute)+1).round(4)\r\n    del minute\r\n    day = 2*np.pi*((df['time']//1440)%365)/365\r\n    df['day_of_year_sin'] = (np.sin(day)+1).round(4)\r\n    df['day_of_year_cos'] = (np.cos(day)+1).round(4)\r\n    del day\r\n    weekday = 2*np.pi*((df['time']//1440)%7)/7\r\n    df['weekday_sin'] = (np.sin(weekday)+1).round(4)\r\n    df['weekday_cos'] = (np.cos(weekday)+1).round(4)\r\n    del weekday\r\n    df['year'] = (((df['time'])//525600))\r\n    df.drop(['time'], axis=1, inplace=True)\r\n    df['accuracy'] = np.log10(df['accuracy'])\r\n    return df\r\n    \r\nprint('Starting...')\r\nstart_time = time.time()\r\n# Global variables\r\ndatapath = '../input/'\r\n# Change val_start_day to zero to generate predictions\r\nval_start_day = 455 # Day at which to cut validation\r\nth = 6 # Threshold at which to cut places from train\r\nfw = [0.5, 0.272, 0.64141, 0.29367, 25, 59, 0.52074]\r\n\r\n# Defining the size of the grid\r\nx_cuts = 21 # number of cuts along x \r\ny_cuts = 20 # number of cuts along y\r\n#TODO: More general solution for t_cuts. For now must be 4.\r\nt_cuts = 4 # number of cuts along time. \r\nx_border_aug = 0.03 # expansion of x border on train \r\ny_border_aug = 0.01 # expansion of y border on train\r\ntime_aug = 2\r\nn_neighbors = 25\r\n\r\ndf_train, df_test, val_label = prepare_data(datapath, val_start_day)\r\ngc.collect()\r\n\r\nelapsed = (time.time() - start_time)\r\nprint('Data prepared in:', timedelta(seconds=elapsed))\r\n    \r\npreds = process_grid(df_train, df_test, x_cuts, y_cuts, t_cuts,\r\n                     x_border_aug, y_border_aug, time_aug, \r\n                     fw, th, n_neighbors)\r\nelapsed = (time.time() - start_time)\r\nprint('Predictions made in:', timedelta(seconds=elapsed))\r\n\r\n#del df_train, df_test\r\n\r\nif val_start_day > 0:\r\n    preds = preds[preds[:, 0] > 0] # only use rows predicted\r\n    labels = val_label.loc[preds[:, 0]].values\r\n    score = mapkprecision(labels, preds[:, 1:])\r\n    print('Final score:', score)\r\nelse:\r\n    generate_submission(preds)\r\nelapsed = (time.time() - start_time)\r\nprint('Task completed in:', timedelta(seconds=elapsed))"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "x_cuts"
 }
],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}}, "nbformat": 4, "nbformat_minor": 0}