{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Intro\n\nThe nice thing about the NCAA basketball championship is that we have plenty of dats available. The format of the tournament was changed in 1985, but that still leaves us with 35 years of data. The Kaggle competition has been going on for 6 years now. So there is also plenty of information on Kaggel. This Notebook was inspired by a few of them, so thanks to the Kaggle community for all the valuable information shared!\n\nWe set up the basics first."},{"metadata":{"trusted":true},"cell_type":"code","source":"import pandas as pd\nimport numpy as np\nimport os\n\nimport matplotlib.pyplot as plt\n%matplotlib inline\n\n# this is the base directory so you can switch between local, Kaggle Notebook, etc.\ndata_directory = \"../input/google-cloud-ncaa-march-madness-2020-division-1-mens-tournament/MDataFiles_Stage1\"","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Evaluate and Compare\n\nThe basic idea of this notebook is that with all the historic data available we can evaluate our algorithms easily. We just us the appropriate data and compare the performance of a variety of possible solutions on all available historic tournaments.\n\nWe are doing this by creating a set of predict functions which given a season and two teams give the probability that the first team wins. This can then be applied to the actual brackets for the finals and we can calculate the logloss of our potential submission in historic competitions.\n\nThe actual format for submissions are different since not all games played are known beforehand. Therefore in the submission we have to give all possible combinations. Our predict function is generic and can also be used for the actual submission. Only the games actually played are considered for the overall logloss so we calculate the actual logloss by looking at the games played in former tournaments and their results.\n\n## Known Unkowns\n\nIf we do know nothing about the teams we can always assume a 50% win probability for each team. So this is a benchmark for our algorithm. Scoring worth than that means something went awfully wrong. "},{"metadata":{"trusted":true},"cell_type":"code","source":"# this is a template for the core function\n# predict the probability that in a given season (year) lteam beats gteam \ndef predict_dummy(season, lteam_id, gteam_id):\n    return(0.5)\n\npredict_dummy(2019, 1115, 1118)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### What Really Happened\n\nWe test our predictions on the actual tourney results available from 1985 onwards. First we load them and remove the play ins since they are not scored. They are marked as days 134 and 135 in the tourney results.\n\nWe will use this data frame and add all our predictions so we can later compare the logloss."},{"metadata":{"trusted":true},"cell_type":"code","source":"tourney_results = pd.read_csv(os.path.join(data_directory,'MNCAATourneyCompactResults.csv'))\n\ntourney_results = tourney_results.loc[(tourney_results[\"DayNum\"] != 134) & (tourney_results[\"DayNum\"] != 135)]\n\ntourney_results.index = range(len(tourney_results.index))\n\ntourney_results","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"The ground truth is is easily created since the tourney results are always given as winning team first and loosing team second. So the result is always 1 for the first team winning. We apply our dummy predictions of 0.5 as a separate column and also test our logic for applying the prediction function.\n\nThis is it, our first prediction is ready. But we can do better."},{"metadata":{"trusted":true},"cell_type":"code","source":"tourney_results[\"Truth\"] = (tourney_results[\"WScore\"] > tourney_results[\"LScore\"]).astype(\"float\")\n\ntourney_results[\"Pred_Dummy\"] = \\\n    tourney_results.apply(lambda row: \n                          predict_dummy(row['Season'], row['WTeamID'], row[\"LTeamID\"]), \n                          axis=1)\n\ntourney_results","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Get the Experts\n\nAmong the multitude of data files we get there are also the tournament seeds. The seeds are a ranking of teams generated by experts before the tournament to prevent strong teams knocking each other out in the early stages of the tournament. So probably they give some reasonable hint on which team might win a game. It is a bit more complicated since the teams are ranked separately for different areas. To get the numerical seeds we need to parse them from the string. For predictions we are actually interested in the seed differences, so we calculate them. On Kaggle you find formulas for calculating the win probability from the seed difference."},{"metadata":{"trusted":true},"cell_type":"code","source":"seeds = pd.read_csv(os.path.join(data_directory,'MNCAATourneySeeds.csv'))\n\nseeds['SeedInt'] = [int(x[1:3]) for x in seeds['Seed']]\n\n# Merge the seeds file with itself on Season.  This creates every combination of two teams by season.\nseed_diff = seeds.merge(seeds, how='inner', on='Season')\n\nseed_diff['ID'] = seed_diff['Season'].astype(str) + '_' \\\n              + seed_diff['TeamID_x'].astype(str) + '_' \\\n              + seed_diff['TeamID_y'].astype(str)\n\n# formula found on Kaggle for getting probabilities out of seed differences\nseed_diff['Pred'] = 0.5 + 0.030975*(seed_diff['SeedInt_y'] - seed_diff['SeedInt_x'])\n\nseed_diff","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Using the information calculated above based on the seed information our predict function just has to select the right probability for two teams in a given season."},{"metadata":{"trusted":true},"cell_type":"code","source":"def predict_seed(season, lteam_id, gteam_id):\n    return(seed_diff.loc[(seed_diff.TeamID_x == lteam_id) &\n                 (seed_diff.TeamID_y == gteam_id) &\n                 (seed_diff.Season == season)].Pred.mean())\n\npredict_seed(1985, 1207, 1210)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"As with our trivial prediction we apply the function to all relevant historic matches."},{"metadata":{"trusted":true},"cell_type":"code","source":"tourney_results[\"Pred_Seed\"] = \\\n    tourney_results.apply(lambda row: \n                          predict_seed(row['Season'], row['WTeamID'], row[\"LTeamID\"]), \n                          axis=1)\n\ntourney_results","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Chess is like Basketball\n\nAt least as far as the relevance of Elo ratings is concerned. Elo as a measurement of strength for chess players is heavily used in match making in professional chess. Since the only input parameter are wins of player A against player B it can be applied to many areas of sports. Let's try with NCAA basketball. We need some basic functions for calculating the Elo values which I copied from yet another interesting notebook on Kaggle."},{"metadata":{"trusted":true},"cell_type":"code","source":"# based on https://www.kaggle.com/lpkirwin/fivethirtyeight-elo-ratings\n\n# a parameter for elo changes\nelo_k = 20\n# the home advantage\nelo_home = 100\n\n# functions taken for Elo calculation\n# this function calculates a wind probability from the elo ratings\ndef elo_pred(elo1, elo2):\n    return(1. / (10. ** (-(elo1 - elo2) / 400.) + 1.))\n\n# this calculates an expexted score difference for a given elo difference\ndef expected_margin(elo_diff):\n    return((7.5 + 0.006 * elo_diff))\n\n# this calculates the update (and the prediction) taking into account home advantage\ndef elo_update(w_elo, l_elo, margin, wloc):\n    if wloc == \"H\":\n        w_elo += elo_home\n    elif wloc == \"A\":\n        l_elo += elo_home\n    elo_diff = w_elo - l_elo\n    pred = elo_pred(w_elo, l_elo)\n    mult = ((margin + 3.) ** 0.8) / expected_margin(elo_diff)\n    update = elo_k * mult * (1 - pred)\n    return(pred, update)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"For actually calculating the Elo values we still have some alternatives. Like the notebook I based this on we are calculating them on all the season games. Each season adjusts the Elo values from the end of the previous season so we calculate a rating based on the history of the team back to 1985. Since players change frequently in college basketball some people might consider this not necessarily as the best idea."},{"metadata":{"trusted":true},"cell_type":"code","source":"season_results = pd.read_csv(os.path.join(data_directory,'MRegularSeasonCompactResults.csv'))\n\nseason_results[\"ScoreDiff\"] = season_results.WScore - season_results.LScore\nseason_results[\"WElo\"] = 0\nseason_results[\"LElo\"] = 0\n\nseason_results","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"To make the code a bit simpler and probably also more efficient we use a cache for the current Elo of all the teams. Based on this cache we look at each match, update the cache and store the current after match Elo of both teams with the match. Note that this might take some time as we are looking at quite a few games. You can restrict the seasons if it takes to long. "},{"metadata":{"trusted":true},"cell_type":"code","source":"# We initialise the ELOs to 1500 before the season\nteam_ids = set(season_results.WTeamID).union(set(season_results.LTeamID))\n\n# cache for the current elo of all teams\ncurrent_elo = dict(zip(list(team_ids), [1500] * len(team_ids)))\n\nfor index, row in season_results.iterrows():\n    pred, update = elo_update(current_elo[row.WTeamID],\n                              current_elo[row.LTeamID],\n                              row.ScoreDiff,\n                              row.WLoc)\n    current_elo[row.WTeamID] += update\n    current_elo[row.LTeamID] -= update\n    season_results.loc[index, \"WElo\"] = current_elo[row.WTeamID]\n    season_results.loc[index, \"LElo\"] = current_elo[row.LTeamID]\n\nseason_results","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"While this is a data structure well suited to analyse how Elo affected match outcomes for our purpose it is not practical. The challenge is that we have to search the teams in two columns. So we use another data frame where we just have teams and the Elo. This is also well suited for analysing historic development of team strengths. \n\nHowever for the prediction we are only interested in the Elo at the end of each season for all teams. This we can get by looking at the Elo at the maximum day for each season for each team. Sounds more complicated than it actually is. "},{"metadata":{"trusted":true},"cell_type":"code","source":"elo_summary = season_results[[\"Season\", \"DayNum\", \"WTeamID\", \"WElo\"]].copy()\nelo_summary.rename(columns={\"WTeamID\" : \"LTeamID\", \"WElo\" : \"LElo\"}, inplace=True)\nelo_summary = pd.concat((elo_summary, season_results[[\"Season\", \"DayNum\", \"LTeamID\", \"LElo\"]]), axis=0, ignore_index=True)\nelo_summary.rename(columns = {\"LTeamID\" : \"TeamID\", \"LElo\" : \"Elo\"}, inplace=True)\n\nidx = elo_summary[(elo_summary.Season == 2015) & (elo_summary.TeamID == 1433)][\"DayNum\"].idxmax()\nelo_summary.iloc[idx].Elo","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Using all this our predict function is quite compact. We againapply it to all tournament matches. Since we only used information before the tournament this also works in the actual Kaggle competition."},{"metadata":{"trusted":true},"cell_type":"code","source":"def predict_elo(season, lteam_id, gteam_id):\n    idx_l = elo_summary[(elo_summary.Season == season) & (elo_summary.TeamID == lteam_id)][\"DayNum\"].idxmax()\n    idx_g = elo_summary[(elo_summary.Season == season) & (elo_summary.TeamID == gteam_id)][\"DayNum\"].idxmax()\n\n    return(elo_pred(elo_summary.iloc[idx_l].Elo, elo_summary.iloc[idx_g].Elo))\n\npredict_elo(1985, 1207, 1210)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"tourney_results[\"Pred_Elo\"] = \\\n    tourney_results.apply(lambda row: \n                          predict_elo(row['Season'], row['WTeamID'], row[\"LTeamID\"]), \n                          axis=1)\n\ntourney_results","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## And the Winner is ...\n\nNow our tourney_results data frame also has our predictions using the different prediction algorithms we have tried. Now the question is which one would have performed best had we actually submitted in that particular season. Kaggle uses logloss to calculate the scores for the leaderboard. It is calculated per game and can then be averaged to get the actual result.\n\nSo first we define two functions to calculate the logloss as specified by Kaggle in the competition rules. Again I found it in a Notebook on Kaggle."},{"metadata":{"trusted":true},"cell_type":"code","source":"def kaggle_clip_log(x):\n    '''\n    Calculates the natural logarithm, but with the argument clipped within [1e-15, 1 - 1e-15]\n    '''\n    return np.log(np.clip(x,1.0e-15, 1.0 - 1.0e-15))\n\ndef kaggle_log_loss(pred, result):\n    '''\n    Calculates the kaggle log loss for prediction pred given result result\n    '''\n    return -(result*kaggle_clip_log(pred) + (1-result)*kaggle_clip_log(1.0 - pred))","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Now we just calculate the logloss per game for each of our predictions and list the mean per season. This would have been our score had we submitted. As mentioned before: It is only fair if we only use data already available just before the actual tournament had taken place. This is the case for both the seed information and our way of calculating the Elo."},{"metadata":{"trusted":true},"cell_type":"code","source":"tourney_results[\"LogLoss_Dummy\"] = kaggle_log_loss(tourney_results[\"Pred_Dummy\"], tourney_results[\"Truth\"])\ntourney_results[\"LogLoss_Seed\"] = kaggle_log_loss(tourney_results[\"Pred_Seed\"], tourney_results[\"Truth\"])\ntourney_results[\"LogLoss_Elo\"] = kaggle_log_loss(tourney_results[\"Pred_Elo\"], tourney_results[\"Truth\"])\n\ntourney_results.groupby('Season').agg({'LogLoss_Dummy' : 'mean', 'LogLoss_Seed' : 'mean', \n                                       \"LogLoss_Elo\" : \"mean\"})","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Here's Looking at Your Results\n\nFinally we plot our prediction results. You can easily see that algorithms like these perform better some seasons and worse others. A difference in logloss of 0.1 is quite a lot! Fortunately for sports fans everywhere the games do not always follow the logic of team strength. If in a given tournament there were more surprise winners our predictions are significantly worse as opposed to the favorites taking the game.\n\nHopefully you can use this code to evaluate you predictions and find more clever and better performaning ones than the examples given here. Please upvote if you found it useful and comment if you have suggestions.\n\nGood luck for the competition!"},{"metadata":{"trusted":true},"cell_type":"code","source":"df_plt = tourney_results.groupby('Season').agg({'LogLoss_Dummy' : 'mean', 'LogLoss_Seed' : 'mean', \n                                                \"LogLoss_Elo\" : \"mean\"})\n\nplt.plot(df_plt.LogLoss_Seed, label=\"Seed\")\nplt.plot(df_plt.LogLoss_Elo, label=\"Elo\")\nplt.axhline(df_plt[[\"LogLoss_Seed\", \"LogLoss_Elo\"]].values.mean())\nplt.legend()\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## Creating a Submission\n\nAfter all this work you can easily create a submission based on the sample submission provided by Kaggle. We parse out our parameters for the predict function and make our prediction. For the submission we only need the ID and the prediction. Good luck in the competition!"},{"metadata":{"trusted":true},"cell_type":"code","source":"submission = pd.read_csv(os.path.join(data_directory,'../MSampleSubmissionStage1_2020.csv'))\n\n# parse year and the two teams out of it\nsubmission['season'] = [int(x[0:4]) for x in submission['ID']]\nsubmission['lteam'] = [int(x[5:9]) for x in submission['ID']]\nsubmission['gteam'] = [int(x[10:14]) for x in submission['ID']]\n\nsubmission[\"Pred\"] = \\\n    submission.apply(lambda row: \n                          predict_elo(row['season'], row['lteam'], row[\"gteam\"]), \n                          axis=1)\n\nsubmission","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submission[[\"ID\", \"Pred\"]].to_csv(os.path.join(data_directory, \"/kaggle/working/my_submission.csv\"), index=False)","execution_count":null,"outputs":[]}],"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.7.6"}},"nbformat":4,"nbformat_minor":1}