{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"This notebook demonstrates a post-processing strategy for the\n[Indoor Location & Navigation](https://www.kaggle.com/c/indoor-location-navigation)\ncompetition.\n\nTo combine machine learning (wifi features) predictions with sensor data (acceleration, attitude heading),\nI defined cost function as follows,\n$$\nL(X_{1:N}) = \\sum_{i=1}^{N} \\alpha_i \\| X_i - \\hat{X}_i \\|^2 + \\sum_{i=1}^{N-1} \\beta_i \\| (X_{i+1} - X_{i}) - \\Delta \\hat{X}_i \\|^2\n$$\nwhere $\\hat{X}_i$ is absolute position predicted by machine learning and $\\Delta \\hat{X}_i$ is relative position predicted by sensor data.\n\nSince the cost function is quadratic, the optimal $X$ is solved by linear equation $Q X = c$\n, where $Q$ and $c$ are derived from above cost function.\nBecause the matrix $Q$ is tridiagonal,\neach machine learning prediction is corrected by *all* machine learning predictions and sensor data.\n\nThe optimal hyperparameters ($\\alpha$ and $\\beta$) can be estimated by expected error of machine learning and sensor data,\nor just tuned by public score.","metadata":{}},{"cell_type":"markdown","source":"## References\n+ [Simple 99% Accurate Floor Model](https://www.kaggle.com/nigelhenry/simple-99-accurate-floor-model)\n+ [Indoor Location Competition 2.0 (Sample Data and Code)](https://github.com/location-competition/indoor-location-competition-20)","metadata":{}},{"cell_type":"code","source":"!git clone --depth 1 https://github.com/location-competition/indoor-location-competition-20 indoor_location_competition_20\n!rm -rf indoor_location_competition_20/data","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"import multiprocessing\nimport numpy as np\nimport pandas as pd\nimport scipy.interpolate\nimport scipy.sparse\nfrom tqdm import tqdm\n\nfrom indoor_location_competition_20.io_f import read_data_file\nimport indoor_location_competition_20.compute_f as compute_f","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"INPUT_PATH = '../input/indoor-location-navigation'","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# parameter(加速度计, 旋转矢量)\n# return(每一步的相对位移[timestamp, x, y])\ndef compute_rel_positions(acce_datas, ahrs_datas):\n    step_timestamps, step_indexs, step_acce_max_mins = compute_f.compute_steps(acce_datas)\n    headings = compute_f.compute_headings(ahrs_datas)\n    stride_lengths = compute_f.compute_stride_length(step_acce_max_mins)\n    step_headings = compute_f.compute_step_heading(step_timestamps, headings)\n    rel_positions = compute_f.compute_rel_positions(stride_lengths, step_headings)\n    return rel_positions","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# 每个进程是同一个path\n# parameter(args{path: path_df})\n# return(dfs[site_path_timestamp, floor, x, y])\ndef correct_path(args):\n    path, path_df = args\n    \n    # path_df[site_path_timestamp, floor, x, y, site, path, timestamp]\n    \n    # get timestamp and prediction of x,y\n    T_ref  = path_df['timestamp'].values\n    xy_hat = path_df[['x', 'y']].values\n    \n    example = read_data_file(f'{INPUT_PATH}/test/{path}.txt')\n    # path_df是test数据处理过的路径和楼层预测，example是未处理的test数据\n    rel_positions = compute_rel_positions(example.acce, example.ahrs)\n    # rel_positions[timestamp, x, y]\n    if T_ref[-1] > rel_positions[-1, 0]:\n        rel_positions = [np.array([[0, 0, 0]]), rel_positions, np.array([[T_ref[-1], 0, 0]])]\n    else:\n        rel_positions = [np.array([[0, 0, 0]]), rel_positions]\n    rel_positions = np.concatenate(rel_positions)\n    \n    T_rel = rel_positions[:, 0]\n    # Temp[abs_pos_x, abs_pos_y] # 其实是相对于起始点的相对位置\n    Temp = np.cumsum(rel_positions[:, 1:3], axis=0)\n    delta_xy_hat = np.diff(scipy.interpolate.interp1d(T_rel, Temp, axis=0)(T_ref), axis=0)\n\n    N = xy_hat.shape[0]\n    delta_t = np.diff(T_ref)\n    alpha = (8.1)**(-2) * np.ones(N)\n    beta  = (0.3 + 0.3 * 1e-3 * delta_t)**(-2)\n    # 构造对角矩阵（含偏移量）\n    A = scipy.sparse.spdiags(alpha, [0], N, N)\n    B = scipy.sparse.spdiags( beta, [0], N-1, N-1)\n    D = scipy.sparse.spdiags(np.stack([-np.ones(N), np.ones(N)]), [0, 1], N-1, N)\n    \n#     print(\"A:\",A)\n#     print(\"B:\",B)\n#     print(\"D:\",D)\n\n    Q = A + (D.T @ B @ D)\n    c = (A @ xy_hat) + (D.T @ (B @ delta_xy_hat))\n    \n#     print(\"Q:\",Q)\n#     print(\"c:\",c)\n    \n    xy_star = scipy.sparse.linalg.spsolve(Q, c)\n\n    return pd.DataFrame({\n        'site_path_timestamp' : path_df['site_path_timestamp'],\n        'floor' : path_df['floor'],\n        'x' : xy_star[:, 0],\n        'y' : xy_star[:, 1],\n    })","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"sub = pd.read_csv('../input/simple-99-accurate-floor-model/submission.csv')\ntmp = sub['site_path_timestamp'].apply(lambda s : pd.Series(s.split('_')))\nsub['site'] = tmp[0]\nsub['path'] = tmp[1]\nsub['timestamp'] = tmp[2].astype(float)\n\n# sub[site_path_timestamp, floor, x, y, site, path, timestamp]\n\nprocesses = multiprocessing.cpu_count()\nwith multiprocessing.Pool(processes=processes) as pool:\n    # 按path分配数据，调用correct_path方法，多进程计算\n    dfs = pool.imap_unordered(correct_path, sub.groupby('path'))\n    # 进度条\n    dfs = tqdm(dfs)\n    dfs = list(dfs)\nsub = pd.concat(dfs).sort_values('site_path_timestamp')\nsub.to_csv('submission.csv', index=False)","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"scipy.sparse.spdiags  diags(diagonals[, offsets, shape, format, dtype])：构造对角矩阵（含偏移量）","metadata":{}}]}