Curve clustering methods and their applications to sports analytics

Robert Bajons | Joint work with Kurt Hornik | 17 Dec. 2023

Vienna University of Economics and Business

CMStatistics 2023

1 / 24

Motivation2 / 24

Motivation

Curves (spatio-temporal observations) are common in sports analysis:
- Movement of players on the pitch.
- Sequences of actions on the pitch.
$\Rightarrow$ studying patterns in curves allows for interesting insights.

3 / 24

Motivation

Curves (spatio-temporal observations) are common in sports analysis:
- Movement of players on the pitch.
- Sequences of actions on the pitch.
$\Rightarrow$ studying patterns in curves allows for interesting insights.
Depending on use case: assign weights to curves at each time point.
Finding structure in augmented data $\Rightarrow$ clustering algorithm for weighted curves needed.
Weights helpful to distinguish curves according to their worth $\Rightarrow$ obtain more representative patterns.

3 / 24

Motivation

Curves (spatio-temporal observations) are common in sports analysis:
- Movement of players on the pitch.
- Sequences of actions on the pitch.
$\Rightarrow$ studying patterns in curves allows for interesting insights.
Depending on use case: assign weights to curves at each time point.
Finding structure in augmented data $\Rightarrow$ clustering algorithm for weighted curves needed.
Weights helpful to distinguish curves according to their worth $\Rightarrow$ obtain more representative patterns.
Examples:
- Pass rush in the NFL: Derive pressure weights for each defender at each point in time.
- Possessions in soccer: Assign a threat value at each point in time, e.g. probability of scoring a goal after $i$ more actions.

3 / 24

Motivation

Routes in the NFL: focus on pass rush.

4 / 24

Motivation

Pass rush in the NFL: add pressure weights.

5 / 24

Motivation

Possessions in soccer.

6 / 24

Motivation

Possessions in soccer with goal scoring weights.

7 / 24

Motivation

Possessions in soccer with goal scoring weights.

8 / 24

Methodology9 / 24

Formal Description of the Problem

Observed data: $Z = {z_{1}, \dots, z_{n}}$ , set of $n$ curves.
Each $z_{i}$ is comprised of observations $z_{i t}$ , $t = 1, \dots, T$ .
- In our use cases: $z_{i t} = (x_{i}, y_{i})_{t}$ 2-dimensional.
At each $t$ : a weight $w_{i t}$ is assigned to $z_{i t}$ .

10 / 24

Formal Description of the Problem

Observed data: $Z = {z_{1}, \dots, z_{n}}$ , set of $n$ curves.
Each $z_{i}$ is comprised of observations $z_{i t}$ , $t = 1, \dots, T$ .
- In our use cases: $z_{i t} = (x_{i}, y_{i})_{t}$ 2-dimensional.
At each $t$ : a weight $w_{i t}$ is assigned to $z_{i t}$ .

Formal goal: Cluster curves $z_{i}$ ( $(x, y)$ -coordinates) while accounting for information from weights $w$ $\Rightarrow$ estimate good prototypes (cluster representants).

10 / 24

Formal Description of the Problem

Observed data: $Z = {z_{1}, \dots, z_{n}}$ , set of $n$ curves.
Each $z_{i}$ is comprised of observations $z_{i t}$ , $t = 1, \dots, T$ .
- In our use cases: $z_{i t} = (x_{i}, y_{i})_{t}$ 2-dimensional.
At each $t$ : a weight $w_{i t}$ is assigned to $z_{i t}$ .

Formal goal: Cluster curves $z_{i}$ ( $(x, y)$ -coordinates) while accounting for information from weights $w$ $\Rightarrow$ estimate good prototypes (cluster representants).

Initial idea: Use a $K$ -means type of algorithm for clustering.
Two adjustment of usual procedure necessary:
- Curve data adjustment (multiple time point).
- Weighted $K$ -means adjustment (weights at each time point).
Note: In many applications data preprocessing necessary to use $K$ -means algorithm.

10 / 24

From $K$ -means to weighted $K$ -means

Given a set of observations $X$ . Find partition into $K$ clusters represented by centroids/prototypes $p_{k}$ , $k = 1, \dots, K$ , by minimizing the within cluster sum of squares

$S = \sum_{k = 1}^{K} \sum_{i : g_{i} = k} (x_{i} - p_{k})^{2} \to min_{(p_{k}), (g_{i})}$

Hard problem to solve $\Rightarrow$ iterative procedure:
- Fix cluster assignment: each observation is assigned to the closest cluster
- Update optimal prototypes $p_{k}$ for a given assignment:

$p_{k} = \frac{1}{N_{k}} \sum_{i : g_{i} = k} x_{i}$

Repeat until convergence:
- Guaranteed to not increase objective function $S$ .
- Convergence only to local optimum $\Rightarrow$ vary starting assignments or use heuristics / prior information for starting values.

Given a set of observations $X$ , with each $x_{i} \in X$ associated with weight $w_{i}$ . Find partition into $K$ clusters by minimizing the weighted within cluster sum of squares

$S_{w} = \sum_{k = 1}^{K} \sum_{i : g_{i} = k} w_{i} (x_{i} - p_{k})^{2} .$

Solve via iterative procedure:
- assignment based on weighted squared distance.
- Prototypes (centers) $p_{k}$ are weighted cluster means:

$p_{k} = \frac{\sum_{i : g_{i} = k} w_{i} x_{i}}{\sum_{i : g_{i} = k} w_{i}} .$

Weights emphasize clustering on important observations.

11 / 24

$K$ -means for weighted curves

Observations: time series objects of the same length $z_{i} = (z_{i 1}, \dots, z_{i T})$ (component-wise weighted object).
Additional information from weights $w_{i} = (w_{i 1}, \dots, w_{i T})$ :
- Indicate how interesting observations are (use case dependent).
- Differ at each time point $\Rightarrow$ more and less important time points.

In the spirit of $K$ -means type of algorithms:

$\sum_{k = 1}^{K} \sum_{i : g_{i} = k} \sum_{t = 1}^{T} w_{i t} (z_{i t} - p_{t k})^{2} \to min_{(p_{t k}), (g_{i})} .$

12 / 24

$K$ -means for weighted curves

Iterative refinement procedure:

Initialize appropriate starting assignments of clusters.
For given cluster assignment find the optimal prototypes (component-wise): $p_{k t} = \frac{\sum_{i : g_{i} = k} w_{i t} z_{i t}}{\sum_{i : g_{i} = k} w_{i t}} .$
Given prototypes find optimal cluster assignments by minimizing $\sum_{t = 1}^{T} w_{i t} (z_{i t} - p_{k t})^{2}$ over $k$ .
Repeat steps 2-3 until convergence, i.e. until change in function to optimize is below some tolerance level.

13 / 24

Implementation in R

Implementation hinges on three functions:

Consensus function C: computes the optimal prototypes for given cluster assignment.
Dissimilarity function D: computes (weighted) distance for each observation to cluster.
Error function E: evaluates objective function for given assignments and prototypes.

Advantages:

Simplicity: easy implementation, easily adoptable for use cases with weighted curves (component-wise weighted objects).
Efficiency: Only looping over clusters necessary, making use of vectorized R operation.
Flexibility:
- Extendable to allow for soft clustering.
- Implementation of other distance measures intuitive (adjustment of C, D and E).

14 / 24

Extensions

What about soft clustering?

Fuzzy $K$ -means: derive optimal prototypes and allow for mixed membership of the observations to clusters.
Fuzzy extension of weighted $K$ -means:

$\sum_{i = 1}^{N} \sum_{k = 1}^{K} \sum_{t = 1}^{T} u_{i k}^{m} w_{i t} (z_{i t} - p_{k t})^{2} \to min_{(u_{i k}), (p_{t k})}$

15 / 24

Extensions

What about soft clustering?

Fuzzy $K$ -means: derive optimal prototypes and allow for mixed membership of the observations to clusters.
Fuzzy extension of weighted $K$ -means:

$\sum_{i = 1}^{N} \sum_{k = 1}^{K} \sum_{t = 1}^{T} u_{i k}^{m} w_{i t} (z_{i t} - p_{k t})^{2} \to min_{(u_{i k}), (p_{t k})}$

Solve via adapted iterative procedure:
- optimal prototypes given membership degrees: $p_{k t} = \frac{\sum_{i = 1}^{N} u_{i k}^{m} w_{i t} z_{i t}}{\sum_{i = 1}^{N} u_{i k}^{m} w_{i t}}$ .
- derive membership degrees given prototypes: $u_{i k} = (\sum_{j = 1}^{K} (\frac{d (z_{i}, w_{i}, p_{k})}{d (z_{i}, w_{i}, p_{j})})^{\frac{1}{m - 1}})^{- 1}$ , where $d (z_{i}, w_{i}, p_{k}) = \sum_{t = 1}^{T} w_{i t} (z_{i t} - p_{k t})^{2}$ .
Implementation in R follows similar idea as before $\Rightarrow$ adjust C and E, implement function U for membership degrees.

15 / 24

Application16 / 24

Pass rush in the NFL

NFL tracking data:
- Routes for every player on every passing play of the first half of the 2021/22 season (~ 7200 plays).
- Route information from start of the play until relevant event (pass/fumble).
- $\sim$ 80000 Routes of defensive players to cluster.
Initial preprocessing:
- Standardize each play to line of scrimmage ( $x$ -axis) and football ( $y$ -axis).
- Plays of different lengths $\Rightarrow$ Use Bézier approximations to transform data to same dimension (necessary for $K$ -means type algorithms).
Augment data with pressure weights:
- Estimate probability of defender being able to pressure the quarterback $\Rightarrow$ gradient boosting tree model.

17 / 24

Pass rush in the NFL

18 / 24

Pass rush in the NFL

19 / 24

Possessions in soccer

Event stream data:
- Events from all matches from the 2017/18 season of 5 top leagues in Europe (Bundesliga, La Liga, Ligue 1, Premier League, Seria A)
Preprocessing:
- Standardize such that offense always plays from left to right.
- Build data set of possession: Sequence of consecutive actions by one team.
- Consider only possession of length 6 $\Rightarrow$ around 27000 possessions to cluster.
Augment data with goal scoring weights:
- Combine models that value actions (VAEP, xT and xG).

20 / 24

Possessions in soccer

21 / 24

Conclusion22 / 24

Conclusion

Sports data is full of spatio-temporal measurements (curves) $\Rightarrow$ Finding patterns in the data allows interesting insights.
In most cases: augmenting curves with weights is quite intuitive $\Rightarrow$ allows for clustering of interesting routes.
We derived a weighted $K$ -means type of algorithm for component-wise weighted curves/objects.
- Derivation of iterative refinement procedure.
- Implementation in R.
- Extension to fuzzy $K$ -means for weighted curve data.
Applications:
- Pass rush in the NFL, Possessions in soccer.
- Weighted $K$ -means provides more desirable clustering.
- Clustering can be used for analyses or in downstream task.
Future work:
- Time dependent fuzzy clustering.

23 / 24

Thank You!

Contact: robert.bajons@wu.ac.at

24 / 24

Curve clustering methods and their applications to sports analytics

Robert Bajons | Joint work with Kurt Hornik | 17 Dec. 2023

Vienna University of Economics and Business

CMStatistics 2023

1 / 24

Motivation2 / 24

Motivation

Curves (spatio-temporal observations) are common in sports analysis:
- Movement of players on the pitch.
- Sequences of actions on the pitch.
$\Rightarrow$ studying patterns in curves allows for interesting insights.

3 / 24

Motivation

Curves (spatio-temporal observations) are common in sports analysis:
- Movement of players on the pitch.
- Sequences of actions on the pitch.
$\Rightarrow$ studying patterns in curves allows for interesting insights.
Depending on use case: assign weights to curves at each time point.
Finding structure in augmented data $\Rightarrow$ clustering algorithm for weighted curves needed.
Weights helpful to distinguish curves according to their worth $\Rightarrow$ obtain more representative patterns.

3 / 24

Motivation

Curves (spatio-temporal observations) are common in sports analysis:
- Movement of players on the pitch.
- Sequences of actions on the pitch.
$\Rightarrow$ studying patterns in curves allows for interesting insights.
Depending on use case: assign weights to curves at each time point.
Finding structure in augmented data $\Rightarrow$ clustering algorithm for weighted curves needed.
Weights helpful to distinguish curves according to their worth $\Rightarrow$ obtain more representative patterns.
Examples:
- Pass rush in the NFL: Derive pressure weights for each defender at each point in time.
- Possessions in soccer: Assign a threat value at each point in time, e.g. probability of scoring a goal after $i$ more actions.

3 / 24

Motivation

Routes in the NFL: focus on pass rush.

4 / 24

Motivation

Pass rush in the NFL: add pressure weights.

5 / 24

Motivation

Possessions in soccer.

6 / 24

Motivation

Possessions in soccer with goal scoring weights.

7 / 24

Motivation

Possessions in soccer with goal scoring weights.

8 / 24

Methodology9 / 24

Formal Description of the Problem

Observed data: $Z = {z_{1}, \dots, z_{n}}$ , set of $n$ curves.
Each $z_{i}$ is comprised of observations $z_{i t}$ , $t = 1, \dots, T$ .
- In our use cases: $z_{i t} = (x_{i}, y_{i})_{t}$ 2-dimensional.
At each $t$ : a weight $w_{i t}$ is assigned to $z_{i t}$ .

10 / 24

Formal Description of the Problem

Observed data: $Z = {z_{1}, \dots, z_{n}}$ , set of $n$ curves.
Each $z_{i}$ is comprised of observations $z_{i t}$ , $t = 1, \dots, T$ .
- In our use cases: $z_{i t} = (x_{i}, y_{i})_{t}$ 2-dimensional.
At each $t$ : a weight $w_{i t}$ is assigned to $z_{i t}$ .

Formal goal: Cluster curves $z_{i}$ ( $(x, y)$ -coordinates) while accounting for information from weights $w$ $\Rightarrow$ estimate good prototypes (cluster representants).

10 / 24

Formal Description of the Problem

Observed data: $Z = {z_{1}, \dots, z_{n}}$ , set of $n$ curves.
Each $z_{i}$ is comprised of observations $z_{i t}$ , $t = 1, \dots, T$ .
- In our use cases: $z_{i t} = (x_{i}, y_{i})_{t}$ 2-dimensional.
At each $t$ : a weight $w_{i t}$ is assigned to $z_{i t}$ .

Formal goal: Cluster curves $z_{i}$ ( $(x, y)$ -coordinates) while accounting for information from weights $w$ $\Rightarrow$ estimate good prototypes (cluster representants).

Initial idea: Use a $K$ -means type of algorithm for clustering.
Two adjustment of usual procedure necessary:
- Curve data adjustment (multiple time point).
- Weighted $K$ -means adjustment (weights at each time point).
Note: In many applications data preprocessing necessary to use $K$ -means algorithm.

10 / 24

From $K$ -means to weighted $K$ -means

Given a set of observations $X$ . Find partition into $K$ clusters represented by centroids/prototypes $p_{k}$ , $k = 1, \dots, K$ , by minimizing the within cluster sum of squares

$S = \sum_{k = 1}^{K} \sum_{i : g_{i} = k} (x_{i} - p_{k})^{2} \to min_{(p_{k}), (g_{i})}$

Hard problem to solve $\Rightarrow$ iterative procedure:
- Fix cluster assignment: each observation is assigned to the closest cluster
- Update optimal prototypes $p_{k}$ for a given assignment:

$p_{k} = \frac{1}{N_{k}} \sum_{i : g_{i} = k} x_{i}$

Repeat until convergence:
- Guaranteed to not increase objective function $S$ .
- Convergence only to local optimum $\Rightarrow$ vary starting assignments or use heuristics / prior information for starting values.

Given a set of observations $X$ , with each $x_{i} \in X$ associated with weight $w_{i}$ . Find partition into $K$ clusters by minimizing the weighted within cluster sum of squares

$S_{w} = \sum_{k = 1}^{K} \sum_{i : g_{i} = k} w_{i} (x_{i} - p_{k})^{2} .$

Solve via iterative procedure:
- assignment based on weighted squared distance.
- Prototypes (centers) $p_{k}$ are weighted cluster means:

$p_{k} = \frac{\sum_{i : g_{i} = k} w_{i} x_{i}}{\sum_{i : g_{i} = k} w_{i}} .$

Weights emphasize clustering on important observations.

11 / 24

$K$ -means for weighted curves

Observations: time series objects of the same length $z_{i} = (z_{i 1}, \dots, z_{i T})$ (component-wise weighted object).
Additional information from weights $w_{i} = (w_{i 1}, \dots, w_{i T})$ :
- Indicate how interesting observations are (use case dependent).
- Differ at each time point $\Rightarrow$ more and less important time points.

In the spirit of $K$ -means type of algorithms:

$\sum_{k = 1}^{K} \sum_{i : g_{i} = k} \sum_{t = 1}^{T} w_{i t} (z_{i t} - p_{t k})^{2} \to min_{(p_{t k}), (g_{i})} .$

12 / 24

$K$ -means for weighted curves

Iterative refinement procedure:

Initialize appropriate starting assignments of clusters.
For given cluster assignment find the optimal prototypes (component-wise): $p_{k t} = \frac{\sum_{i : g_{i} = k} w_{i t} z_{i t}}{\sum_{i : g_{i} = k} w_{i t}} .$
Given prototypes find optimal cluster assignments by minimizing $\sum_{t = 1}^{T} w_{i t} (z_{i t} - p_{k t})^{2}$ over $k$ .
Repeat steps 2-3 until convergence, i.e. until change in function to optimize is below some tolerance level.

13 / 24

Implementation in R

Implementation hinges on three functions:

Consensus function C: computes the optimal prototypes for given cluster assignment.
Dissimilarity function D: computes (weighted) distance for each observation to cluster.
Error function E: evaluates objective function for given assignments and prototypes.

Advantages:

Simplicity: easy implementation, easily adoptable for use cases with weighted curves (component-wise weighted objects).
Efficiency: Only looping over clusters necessary, making use of vectorized R operation.
Flexibility:
- Extendable to allow for soft clustering.
- Implementation of other distance measures intuitive (adjustment of C, D and E).

14 / 24

Extensions

What about soft clustering?

Fuzzy $K$ -means: derive optimal prototypes and allow for mixed membership of the observations to clusters.
Fuzzy extension of weighted $K$ -means:

$\sum_{i = 1}^{N} \sum_{k = 1}^{K} \sum_{t = 1}^{T} u_{i k}^{m} w_{i t} (z_{i t} - p_{k t})^{2} \to min_{(u_{i k}), (p_{t k})}$

15 / 24

Extensions

What about soft clustering?

Fuzzy $K$ -means: derive optimal prototypes and allow for mixed membership of the observations to clusters.
Fuzzy extension of weighted $K$ -means:

$\sum_{i = 1}^{N} \sum_{k = 1}^{K} \sum_{t = 1}^{T} u_{i k}^{m} w_{i t} (z_{i t} - p_{k t})^{2} \to min_{(u_{i k}), (p_{t k})}$

Solve via adapted iterative procedure:
- optimal prototypes given membership degrees: $p_{k t} = \frac{\sum_{i = 1}^{N} u_{i k}^{m} w_{i t} z_{i t}}{\sum_{i = 1}^{N} u_{i k}^{m} w_{i t}}$ .
- derive membership degrees given prototypes: $u_{i k} = (\sum_{j = 1}^{K} (\frac{d (z_{i}, w_{i}, p_{k})}{d (z_{i}, w_{i}, p_{j})})^{\frac{1}{m - 1}})^{- 1}$ , where $d (z_{i}, w_{i}, p_{k}) = \sum_{t = 1}^{T} w_{i t} (z_{i t} - p_{k t})^{2}$ .
Implementation in R follows similar idea as before $\Rightarrow$ adjust C and E, implement function U for membership degrees.

15 / 24

Application16 / 24

Pass rush in the NFL

NFL tracking data:
- Routes for every player on every passing play of the first half of the 2021/22 season (~ 7200 plays).
- Route information from start of the play until relevant event (pass/fumble).
- $\sim$ 80000 Routes of defensive players to cluster.
Initial preprocessing:
- Standardize each play to line of scrimmage ( $x$ -axis) and football ( $y$ -axis).
- Plays of different lengths $\Rightarrow$ Use Bézier approximations to transform data to same dimension (necessary for $K$ -means type algorithms).
Augment data with pressure weights:
- Estimate probability of defender being able to pressure the quarterback $\Rightarrow$ gradient boosting tree model.

17 / 24

Pass rush in the NFL

18 / 24

Pass rush in the NFL

19 / 24

Possessions in soccer

Event stream data:
- Events from all matches from the 2017/18 season of 5 top leagues in Europe (Bundesliga, La Liga, Ligue 1, Premier League, Seria A)
Preprocessing:
- Standardize such that offense always plays from left to right.
- Build data set of possession: Sequence of consecutive actions by one team.
- Consider only possession of length 6 $\Rightarrow$ around 27000 possessions to cluster.
Augment data with goal scoring weights:
- Combine models that value actions (VAEP, xT and xG).

20 / 24

Possessions in soccer

21 / 24

Conclusion22 / 24

Conclusion

Sports data is full of spatio-temporal measurements (curves) $\Rightarrow$ Finding patterns in the data allows interesting insights.
In most cases: augmenting curves with weights is quite intuitive $\Rightarrow$ allows for clustering of interesting routes.
We derived a weighted $K$ -means type of algorithm for component-wise weighted curves/objects.
- Derivation of iterative refinement procedure.
- Implementation in R.
- Extension to fuzzy $K$ -means for weighted curve data.
Applications:
- Pass rush in the NFL, Possessions in soccer.
- Weighted $K$ -means provides more desirable clustering.
- Clustering can be used for analyses or in downstream task.
Future work:
- Time dependent fuzzy clustering.

23 / 24

Thank You!

Contact: robert.bajons@wu.ac.at

24 / 24

↑, ←, Pg Up, k	Go to previous slide
↓, →, Pg Dn, Space, j	Go to next slide
Home	Go to first slide
End	Go to last slide
Number + Return	Go to specific slide
b / m / f	Toggle blackout / mirrored / fullscreen mode
c	Clone slideshow
p	Toggle presenter mode
t	Restart the presentation timer
?, h	Toggle this help
o	Tile View: Overview of Slides
Alt + f	Fit Slides to Screen

Curve clustering methods and their applications to sports analytics

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Methodology

Formal Description of the Problem

Formal Description of the Problem

Formal Description of the Problem

From KK-means to weighted KK-means

KK-means for weighted curves

KK-means for weighted curves

Implementation in R

Extensions

Extensions

Application

Pass rush in the NFL

Pass rush in the NFL

Pass rush in the NFL

Possessions in soccer

Possessions in soccer

Conclusion

Conclusion

Thank You!

Motivation

Help

Curve clustering methods and their applications to sports analytics

Curve clustering methods and their applications to sports analytics

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Motivation

Methodology

Formal Description of the Problem

Formal Description of the Problem

Formal Description of the Problem

From KK-means to weighted KK-means

KK-means for weighted curves

KK-means for weighted curves

Implementation in R

Extensions

Extensions

Application

Pass rush in the NFL

Pass rush in the NFL

Pass rush in the NFL

Possessions in soccer

Possessions in soccer

Conclusion

Conclusion

Thank You!

From $K$ -means to weighted $K$ -means

$K$ -means for weighted curves

$K$ -means for weighted curves

From $K$ -means to weighted $K$ -means

$K$ -means for weighted curves

$K$ -means for weighted curves