{"cells":[
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "import numpy as np\nimport pandas as pd\nfrom sklearn.cross_validation import train_test_split\nfrom sklearn.preprocessing import LabelEncoder\nfrom sklearn.cluster import DBSCAN"
 },
 {
  "cell_type": "markdown",
  "metadata": {},
  "source": "# Some "
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "def load_data(path):\n    df = pd.read_csv(path, index_col=0)\n    df['minute_of_day'] = (df.time + 0) % (60*24)\n    df.drop('time', axis=1, inplace=True)\n    return df\n\ndef mapk(actual, predicted):\n    matched_rows, matched_pos = np.where((predicted-actual[:,np.newaxis])==0)\n    _, unique_row_idx = np.unique(matched_rows, return_index=True)\n    return (1./(1+matched_pos[unique_row_idx])).sum()/len(actual)"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "data = load_data('../input/train.csv')\nle = LabelEncoder().fit(data.place_id)\ndata.place_id = le.transform(data.place_id)"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "train, valid = train_test_split(data, test_size=0.05)"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "def cluster(df, min_events=10, normed=False):\n    df.is_copy = False\n    keep_ids = df.groupby('place_id').x.count() >= min_events\n    sub = df.loc[keep_ids[df.place_id]][['x','y','place_id']].copy()\n    if normed:\n        sub[['x','y']] = sub.groupby('place_id')[['x','y']].transform(lambda coord: (coord - coord.mean()) / coord.std())\n    clstr = DBSCAN(eps=0.5, min_samples=min_events)\n    for place_id, subg in sub.groupby('place_id'):\n        clstr.fit(subg[['x','y']])\n        df.loc[df.place_id==place_id,'label'] = clstr.labels_"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "cluster(valid, normed=True) #takes a long time"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "cluster_means = train.loc[train.label!=-1].groupby(['place_id','label'])[['x','y']].mean()\ncluster_stds = train.loc[train.label!=-1].groupby(['place_id','label'])[['x','y']].std()"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "n_t_bin = 48\nsigma = 120\ndt = 60*24/n_t_bin\nt_bin = np.linspace(-60*24+dt/2,2*60*24-dt/2,n_t_bin*3)\nt_bin_ = t_bin[n_t_bin:n_t_bin*2]\ndef day_bin(minutes_of_day):\n    return np.exp(-(minutes_of_day[:,np.newaxis]-t_bin[:np.newaxis])**2/(2*sigma**2)).reshape(-1,3,n_t_bin).sum((0,1))"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "t_hist = train.loc[train.label!=-1].groupby(['place_id','label']).minute_of_day.apply(day_bin)"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "def xy_bin(df, n_bins_x, n_bins_y):\n    df.is_copy = False\n    xbin = np.floor(df.x/10*n_bins_x).astype(int)\n    xbin[xbin==n_bins_x] = n_bins_x - 1\n    ybin = np.floor(df.y/10*n_bins_y).astype(int)\n    ybin[ybin==n_bins_y] = n_bins_y - 1\n    if 'xybin' in df:\n        df.loc[:,'xybin'] = ybin + xbin * n_bins_y\n    else:\n        df['xybin'] = ybin + xbin * n_bins_y"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "nx, ny = 50,50\nxy_bin(train, nx, ny)\nxy_bin(valid, nx, ny)\nids_in_xybins = train.groupby('xybin').place_id.unique()\nids_in_xybins = ids_in_xybins.append(pd.Series([np.array([])],np.setdiff1d(np.arange(nx*ny),ids_in_xybins.index.values)))"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "actual = []\npredicted = []\nfor xyb, subg in valid.groupby('xybin'):\n    place_ids = list(ids_in_xybins['xyb'])\n    means = cluster_means.loc[place_ids]\n    stds = cluster_stds.loc[place_ids]\n    prob_x = np.exp(- (subg.x[:,np.newaxis] - means.x[np.newaxis,:])**2 / (2*stds.x[np.newaxis,:]**2)) / stds.x[np.newaxis,:]\n    prob_y = np.exp(- (subg.y[:,np.newaxis] - means.y[np.newaxis,:])**2 / (2*stds.y[np.newaxis,:]**2)) / stds.y[np.newaxis,:]\n    t_bin_num = np.abs(subg.minute_of_day[:,np.newaxis] - t_bin_[np.newaxis,:]).argmin(1)\n    prob_t = np.array(list(t_hist.loc[place_ids])).T[t_bin_num]\n    probs = prob_x*prob_y*prob_t\n    idxs = np.argpartition(-probs,2)[:,:3]\n    selector = np.tile(np.arange(len(subg)),(3,1)).T\n    idxs = idxs[selector, (-probs[selector,idxs]).argsort()]\n    actual.append(subg.place_id)\n    predicted.append(np.array([v[0] for v in means.index.values])[idxs])"
 },
 {
  "cell_type": "code",
  "execution_count": null,
  "metadata": {
   "collapsed": false
  },
  "outputs": [],
  "source": "mapk(np.array([ac for acs in actual for ac in acs]),np.vstack(predicted))"
 }
],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}}, "nbformat": 4, "nbformat_minor": 0}