{"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":"# Simple 99% accurate Bayesian floor inference\n\nThis is my first public notebook on kaggle ;). Please, vote if you find it interesting!\n\n*Note: Code from this notebook produced 100% accurate floor prediction with more advanced private dataset I used in the actual competition (wifi + beacons + magnetic data). Here I'm using a public dataset for the sake of simplicity.*\n\n\nFor each waypoint the floor could be predicted using any multiclass classification model, where features are wifi RSSI values and the class is a floor number. The model presented in this notebook improves on top of it by utilizing the fact that all waypoints of the same path are always located on the same floor.\nThe most obvious postprocessing to make sure it is the case would use some kind of majority voting. E.g. for each path choose the most frequently predicted floor. This might work, but there is a better solution rooted in \n\n<img src=\"https://i.imgflip.com/59ykp9.jpg\" alt=\"drawing\" width=\"400\"/>\n\n\nFirst recall that multiclass classification models with softmax output layers and cross entropy loss functions produce probabilities of each class along with the most probable class. Let's look at an example of such predictions for an imaginary path:\n\n\n| Path      | Timestamp     | B1 | F1 | F2  |  Max probability floor |\n| ----------- | ----------- | -- | -- | --  |  -------- |\n| path1       | 100         |0.1 | 0.3 | 0.6 |  **F2** |\n| path1       | 5000        |0.1 | 0.4 | 0.1 |  F1 |\n| path1      | 10000        |0.3 | 0.3 | 0.4 | **F2** |\n\nMajority voting produces floor F2 wich we are going to challenge with the following observations. \n\nLet's assume each waypoint prediction is an independent random event with probability $p_{ij}$ where $i$ is the waypoint number within a single path ($1$ to $n$) and $j$ is the floor. Then according to Bayes theorem probability of a floor $f_j$ given a set of predictions $p_{ij}$ is:\n\n$$Pr(f_j|p_{ij}) = Pr(p_{ij}|f_j) * Pr(f_j) / Pr(p_{ij})$$\n\nGiven independence of waypoint predictions and the fact that $Pr(p_{ij})$ doesn't actually depend on the floor number, the formula can be transformed to:\n\n$$Pr(f_j|p_{ij}) \\infty \\prod\\limits_{i=1}^{n} p_{ij} * Pr(f_j)$$\n\nBut what is $P(f_j)$?. In Bayes theory it is called \"prior\" and in our case it can be simply calculated as normalized frequency of floor occurences in the training data. Let $P(f_j)$ be $0.33$ for each of the floors in the example above. \n\n\nFor the example above theh final floor probability is\n\n| Floor | Probability |\n| ----- | -------------------------- |\n| B1    | 0.1 * 0.1 * 0.3 * 0.33 = 0.00099  |\n| **F1**    | **0.3 * 0.4 * 0.3 * 0.33 = 0.01188**  |\n| F2    | 0.6 * 0.1 * 0.4 * 0.33 = 0.00792  |\n\nAs you can see the most probable floor F1 is different (and likely more accurate) from the result of majority voting: F2. \n\nFor more details search for Naive Bayes classifiers.","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"markdown","source":"## Cross validation","metadata":{}},{"cell_type":"code","source":"import pandas as pd\nimport re \nimport glob\nimport os\nimport numpy as np\n\ndef buildings():    \n    return np.unique([re.match('([^_]*)_.*', os.path.basename(f)).group(1) \n                      for f in glob.glob('/kaggle/input/indoor-navigation-and-location-wifi-features/*')])\n\n\ndef train_building_features(building):\n    return pd.read_csv(f'/kaggle/input/indoor-navigation-and-location-wifi-features/{building}_train.csv')\n\ndef parse_site_path_timestamp(spt):\n    return np.array(spt.str.split('_').tolist()).transpose()\n    \ndef test_building_features(building):\n    df = pd.read_csv(f'/kaggle/input/indoor-navigation-and-location-wifi-features/{building}_test.csv')\n    df['site'], df['path'], df['timestamp'] = parse_site_path_timestamp(df['site_path_timestamp'])\n    return df\n\n\nprint('List of used buildings', buildings())\n    ","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"import xgboost \nimport numpy as np\n\nimport zlib\n\ndef get_priors(df):\n    df = df[['f', 'path']].drop_duplicates().groupby('f').count()\n    return (df / df['path'].sum()).to_dict()['path']\n\ndef train_floor_model(df, eta=0.06, colsample_bytree=0.25, max_depth=25, n_estimators=100):\n    model = xgboost.XGBClassifier(eval_metric='mlogloss', \n                                  eta=eta, \n                                  colsample_bytree=colsample_bytree, \n                                  max_depth=max_depth,\n                                  n_estimators=n_estimators)    \n    model.fit(df.select_dtypes(include=int).drop(columns=['f']), df['f'])\n    return model\n        \n\n\ndef predict_floor(df, model, priors):\n    floors = model._le.inverse_transform(list(range(model.n_classes_)))    \n    def predict_path_floor(df_path):\n        \"\"\"\n        This method implements the logic outlined above. \n        1. The probability matrix is generated by predict_proba\n        2. Products for each floor are generated with np.prod\n        3. We choose the best foor using np.argmax\n        \"\"\"\n        proba = model.predict_proba(df_path.select_dtypes(include=int).drop(columns='f', errors='ignore'))\n        prod1 = np.prod(proba, axis=0)\n        prod2 = [p * priors[int(floors[idx])] for idx, p in enumerate(prod1)]\n        return floors[np.argmax(prod2)]\n        \n    df = df.set_index('path').copy()\n    df['predicted_floor'] = df.groupby('path').apply(lambda df_path: predict_path_floor(df_path))\n    return df\n\n \ndef train_test_split(df, fold=0, nfolds=10):\n    is_holdout = df['path'].apply(lambda path: zlib.crc32(path.encode()) % nfolds == fold)\n    return df[~is_holdout], df[is_holdout]\n","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\nfrom tqdm import tqdm\nimport warnings\nwarnings.filterwarnings(\"ignore\")\n\nNFOLDS = 10\n\n# add more folds to achive higher confidence\nfor fold in [7]:   \n    df_result = []\n    for building in tqdm(buildings(), total=len(buildings())):\n        df_train, df_test = train_test_split(train_building_features(building).drop(columns=['x', 'y']), fold, NFOLDS)        \n        priors = get_priors(df_train)    \n        model = train_floor_model(df_train)    \n        pred = predict_floor(df_test, model, priors)[['f', 'predicted_floor']]\n        df_result.append(pred)\n\n    df_result = pd.concat(df_result)\n    print(f'Floor prediction cross validation fold {fold} accuracy: ', (df_result['f'] == df_result['predicted_floor']).mean())","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Produce test predictions","metadata":{}},{"cell_type":"code","source":"df_test = pd.read_csv('/kaggle/input/indoor-location-navigation/sample_submission.csv')\ndf_test['site'], df_test['path'], df_test['timestamp'] = parse_site_path_timestamp(df_test['site_path_timestamp'])\ndf_test = df_test.set_index('path')\ndf_test","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\nfor site in tqdm(buildings(), total=len(buildings())):\n    df_features = train_building_features(site)\n    df_features_test = test_building_features(site)\n    model = train_floor_model(df_features)\n    prior = get_priors(df_features)\n    df_pred = predict_floor(df_features_test, model, prior)[['predicted_floor']].drop_duplicates()\n    df_test.loc[df_pred.index, 'floor'] = df_pred['predicted_floor']","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"df_sub = df_test[['site_path_timestamp', 'floor', 'x', 'y']]\ndf_sub.to_csv('submission.csv', index=False)\ndf_sub","metadata":{"trusted":true},"execution_count":null,"outputs":[]}]}