{"cells":[{"metadata":{},"cell_type":"markdown","source":"This notebook summarizes my approach to clustering player movement in the NFL 1st and Future - Analytics competition. The approach works as follows:\n1. Due to the complexity of the approach, we are here only going to sample a small random subset of the data.\n2. We then run the DBSCAN algorithm with a distance function based on the longest common subsequence algorithm.\n3. We manually analyze the clusters found and compare different clusters and their risk of injuries.\n\nThis notebook was inspired by the paper \"*Discovering similar multidimensional trajectories*\" by Michail Vlachos, George Kollios, and Dimitrios Gunopulos from 2002 publishd at the International Conference on Data Engineering. This seminal work is definitely worth a read when starting to look into the analysis of object trajectories.\n\nThe following code is also based on the implementation of the LCS algorithm from GeeksforGeeks:\nhttps://www.geeksforgeeks.org/python-program-for-longest-common-subsequence/\nGeeksforGeeks provide a nice tabulated implementation for the LCS problem and their implementation was adapted to work with trajectory data.\n\nSince sklearn's implementation of the DBSCAN scan algorithm was not flexible enough for our needs, we adapated Chris McCormick's DBSCAN implementation for our purposes. Chris describes the DBSCAN algorithm nicely in the following blog post:\nhttps://mccormickml.com/2016/11/08/dbscan-clustering/\n\nLastly, our visualization of the footbal field was taken form Rob Mulla's notebook on the same challenge:\nhttps://www.kaggle.com/robikscube/nfl-1st-and-future-analytics-intro\nHe did an excellent job of using matplotlib to draw a football field and makes it super simple to adjust it. Kudos to Rob for making this available!"},{"metadata":{"trusted":true},"cell_type":"code","source":"import numpy as np\nimport pandas as pd\nimport functools\nimport matplotlib.pyplot as plt\nimport matplotlib.patches as patches\nfrom collections import Counter","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# this code handles the random subsampling of the player track data\n\ndef sample_player_track_data(\n        path_player_tracks, path_plays, nr_random, downsampling=None,\n        chunk_size=2*1e5):\n    plays = pd.read_csv(path_plays)\n    play_ids = np.random.choice(plays.PlayKey.unique(), nr_random)\n    chunks = pd.read_csv(path_player_tracks, chunksize=chunk_size)\n    player_df = pd.concat(valid_find(chunks, play_ids))\n    print(\"Extracted %d rows\" % len(player_df))\n    return extract_trajectories(player_df, downsampling)\n\n\ndef valid_find(chunks, tracks):\n    tracks_found = set()\n    for chunk in chunks:\n        mask = chunk.PlayKey.isin(tracks)\n        if mask.all():\n            res = chunk\n        else:\n            res = chunk.loc[mask]\n        tracks_found.update(res.PlayKey.unique())\n        if len(tracks_found) == len(set(tracks)) and not mask.any():\n            break\n        yield res\n        \ndef extract_trajectories(player_df, downsampling):\n    print(\"downsampling:\", downsampling)\n    trajectories = []\n    keys = []\n    for key, player_track in player_df.groupby('PlayKey'):\n        keys.append(key)\n        if downsampling is not None:\n            trajectories.append(player_track[['x', 'y']].values[0::downsampling])\n        else:\n            trajectories.append(player_track[['x', 'y']].values)\n    return trajectories, keys\n\n\ndef valid_find(chunks, tracks):\n    tracks_found = set()\n    for chunk in chunks:\n        mask = chunk.PlayKey.isin(tracks)\n        if mask.all():\n            res = chunk\n        else:\n            res = chunk.loc[mask]\n        tracks_found.update(res.PlayKey.unique())\n        if len(tracks_found) == len(set(tracks)) and not mask.any():\n            break\n        yield res\n\n\ndef find_players_tracks(data_path, tracks, chunk_size=2*1e5):\n    chunks = pd.read_csv(data_path, chunksize=chunk_size)\n    player_df = pd.concat(valid_find(chunks, tracks))\n    return extract_trajectories(player_df, None)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# This code follows the LCS implementation by GeeksforGeeks (see above for more information)\n\ndef lcs(X, Y, eps, delta):\n    m = len(X)\n    n = len(Y)\n    L = np.zeros((m+1, n+1))\n    for i in range(m + 1):\n        for j in range(n + 1):\n            if i == 0 or j == 0:\n                L[i][j] = 0\n            elif abs(X[i-1][0] - Y[j-1][0]) <= eps and abs(X[i-1][1] - Y[j-1][1]) <= eps and abs(i - j) < delta:\n                L[i][j] = L[i-1][j-1]+1\n            else:\n                L[i][j] = max(L[i-1][j], L[i][j-1])\n    return L[m][n]\n\n\n# We need a distance function for two trajectories to be used in the clustering\n# This follows the idea from Vlachos et al.\ndef lcs_dist(x, y, eps, delta):\n    return 1 - lcs(x, y, eps, delta) / min(len(x), len(y))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# This code follow the DBSCAN implementation by Chris McCormick (see above for more information)\ndef dbscan(D, eps, MinPts, dist):\n    labels = [0]*len(D)\n    C = 0\n    for P in range(0, len(D)):\n        if not (labels[P] == 0):\n           continue\n        NeighborPts = regionQuery(D, P, eps, dist)\n        if len(NeighborPts) < MinPts:\n            labels[P] = -1\n        else:\n            C += 1\n            growCluster(D, labels, P, NeighborPts, C, eps, MinPts, dist)\n    return labels\n\n\ndef growCluster(D, labels, P, NeighborPts, C, eps, MinPts, dist):\n    labels[P] = C\n    i = 0\n    while i < len(NeighborPts):\n        Pn = NeighborPts[i]\n        if labels[Pn] == -1:\n            labels[Pn] = C\n        elif labels[Pn] == 0:\n            labels[Pn] = C\n            PnNeighborPts = regionQuery(D, Pn, eps, dist)\n            if len(PnNeighborPts) >= MinPts:\n                NeighborPts = NeighborPts + PnNeighborPts\n        i += 1\n\n        \ndef regionQuery(D, P, eps, dist):\n    neighbors = []\n    for Pn in range(0, len(D)):\n        if dist(D[P], D[Pn]) < eps:\n            neighbors.append(Pn)\n    return neighbors\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"nr_plays = 10\ndownsampling = 4\n\nlcs_eps = 1.0\nlcs_delta = 10\nlcs_dist_param = functools.partial(lcs_dist, eps=lcs_eps, delta=lcs_delta)\n\ndbscan_eps = 0.3\ndbscan_min_samples = 5","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"trajectories, ids = sample_player_track_data(\"/kaggle/input/nfl-playing-surface-analytics/PlayerTrackData.csv\", \"/kaggle/input/nfl-playing-surface-analytics/PlayList.csv\", nr_plays, downsampling=downsampling)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"labels = dbscan(trajectories, dbscan_eps, dbscan_min_samples, lcs_dist_param)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"print(\"Found %d clusters\" % max(labels))\nlabels_df = pd.DataFrame(zip(ids, labels), columns=['Key', 'Cluster'])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Code for plotting trajectory clusters on a football field\n# The implementation of `create_football_field` is based on Rob Mulla's notebook (see above for more information)\ndef create_football_field(\n        linenumbers=True, endzones=True, highlight_line=False,\n        highlight_line_number=50, highlighted_name='Line of Scrimmage',\n        fifty_is_los=False, figsize=(12, 6.33)):\n\n    rect = patches.Rectangle((0, 0), 120, 53.3, linewidth=0.1, edgecolor='r', facecolor='darkgreen', zorder=0)\n    fig, ax = plt.subplots(1, figsize=figsize)\n    ax.add_patch(rect)\n    plt.plot(\n        [10, 10, 10, 20, 20, 30, 30, 40, 40, 50, 50, 60, 60, 70, 70, 80, 80, 90, 90, 100, 100, 110, 110, 120, 0, 0, 120, 120],\n        [0, 0, 53.3, 53.3, 0, 0, 53.3, 53.3, 0, 0, 53.3, 53.3, 0, 0, 53.3, 53.3, 0, 0, 53.3, 53.3, 0, 0, 53.3, 53.3, 53.3, 0, 0, 53.3],\n        color='white')\n    if fifty_is_los:\n        plt.plot([60, 60], [0, 53.3], color='gold')\n        plt.text(62, 50, '<- Player Yardline at Snap', color='gold')\n    if endzones:\n        ez1 = patches.Rectangle((0, 0), 10, 53.3, linewidth=0.1, edgecolor='r', facecolor='blue', alpha=0.2, zorder=0)\n        ez2 = patches.Rectangle((110, 0), 120, 53.3, linewidth=0.1, edgecolor='r', facecolor='blue', alpha=0.2, zorder=0)\n        ax.add_patch(ez1)\n        ax.add_patch(ez2)\n    plt.xlim(0, 120)\n    plt.ylim(-5, 58.3)\n    plt.axis('off')\n    if linenumbers:\n        for x in range(20, 110, 10):\n            numb = x\n            if x > 50:\n                numb = 120 - x\n            plt.text(x, 5, str(numb - 10), horizontalalignment='center', fontsize=20, color='white')\n            plt.text(x - 0.95, 53.3 - 5, str(numb - 10), horizontalalignment='center', fontsize=20, color='white', rotation=180)\n    if endzones:\n        hash_range = range(11, 110)\n    else:\n        hash_range = range(1, 120)\n    for x in hash_range:\n        ax.plot([x, x], [0.4, 0.7], color='white')\n        ax.plot([x, x], [53.0, 52.5], color='white')\n        ax.plot([x, x], [22.91, 23.57], color='white')\n        ax.plot([x, x], [29.73, 30.39], color='white')\n    if highlight_line:\n        hl = highlight_line_number + 10\n        plt.plot([hl, hl], [0, 53.3], color='yellow')\n        plt.text(hl + 2, 50, '<- {}'.format(highlighted_name), color='yellow')\n    return fig, ax\n\ndef plot_cluster_on_field(cluster, plays, trajectory_dict):\n    fig, ax = create_football_field(figsize=(16, 6.33))\n    c_trajectories = []\n    for trajectory_id in cluster:\n        c_trajectories.append(trajectory_dict[trajectory_id])\n    count_injuries = 0\n    positions = Counter()\n    for i, t in enumerate(c_trajectories):\n        play = plays[plays.PlayKey == cluster[i]]\n        injury = injuries[injuries.PlayerKey == play.iloc[0].PlayerKey]\n        injured = len(injury) > 0\n        print(\n            cluster[i], play.iloc[0].PlayerKey, play.iloc[0].RosterPosition,\n            play.iloc[0].StadiumType, play.iloc[0].PlayType, injured)\n        color = 'orange'\n        if injured:\n            color = 'red'\n            count_injuries += 1\n        positions[play.iloc[0].PositionGroup] += 1\n        pd.DataFrame(t, columns=['x', 'y']).plot(\n            kind='scatter', x='x', y='y', ax=ax, color=color, alpha=0.7, s=3)\n\n    positions_str = 'Positions:\\n'\n    for key, value in positions.most_common():\n        positions_str += \"%s: %2d (%.2f%%)\\n\" % (\n            key, value, value / len(c_trajectories) * 100)\n\n    ax.text(122.5, 53.3, \"%d Plays\\n%d from injured (%2.f%%)\\n%s\" % (\n        len(c_trajectories), count_injuries,\n        count_injuries / len(c_trajectories) * 100, positions_str),\n        verticalalignment='top')\n    plt.subplots_adjust(left=0.05, right=0.85, top=0.95, bottom=0.05)\n    plt.show()\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# the code in the above will produce a labeling akin to the following data structure:\nlabels_df = pd.DataFrame([\n    [\"26624-1-18\", -1],\n    [\"27363-17-60\", 0],\n    [\"26624-1-26\", -1],\n    [\"26624-1-30\", -1],\n    [\"27363-24-38\", 0],\n    [\"26624-1-37\", -1],\n    [\"26624-1-42\", -1],\n    [\"35577-27-19\", 0],\n    [\"33474-20-25\", 0],\n    [\"26624-1-46\", -1],\n    [\"32103-8-31\", 0],\n    [\"26624-1-48\", -1],\n    [\"35648-15-4\", 0],\n    [\"33474-25-44\", 0],\n    [\"26624-1-59\", -1],\n    [\"34214-20-60\", 0],\n    [\"26624-1-77\", -1],\n    [\"33337-15-3\", 0],\n    [\"34230-18-32\", 0],\n    [\"36555-5-54\", 0]], columns=['Key', 'Cluster'])\n# Each positive number represents one cluster which can visualized with the following code\n\nplays = pd.read_csv(\"/kaggle/input/nfl-playing-surface-analytics/PlayList.csv\")\ninjuries = pd.read_csv(\"/kaggle/input/nfl-playing-surface-analytics/InjuryRecord.csv\")\ntrajectories, ids = find_players_tracks(\n    \"/kaggle/input/nfl-playing-surface-analytics/PlayerTrackData.csv\",\n    labels_df[labels_df.Cluster > -1].Key.tolist())\ntrajectory_dict = {}\nfor i, trajectory_id in enumerate(ids):\n    trajectory_dict[trajectory_id] = trajectories[i]\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# let's visualize a cluster\ncluster_id = 0\nkeys_of_tracks = labels_df[labels_df.Cluster == cluster_id].Key.tolist()\nplot_cluster_on_field(keys_of_tracks, plays, trajectory_dict)","execution_count":null,"outputs":[]}],"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":4,"nbformat_minor":1}