# Detecting Traffic Incidents Using Persistence Diagrams
## 3 Description of the Algorithm  
Our algorithm is motivated by the intuition that if we take a data set of vectors that represent typical behavior and one of the vectors were replaced with an anomalous observation, the topology of the data set would be significantly altered. The topology of the set is understood by computing persistence diagrams of randomly chosen subsets \(\beta\subset\{\mathbf{x}_{i}\}_{i=1}^{m}\). When we modify a bag \(\beta\) by randomly replacing one of its vectors with \(\mathbf{x}_{j}\) we denote the resulting modified bag by \(\beta^{(j)}\). Figure 2 depicts the data points in the reference and modified bags. We then let \(D\) and \(D^{(j)}\) denote the persistence diagrams for vectors in \(\beta\) and \(\beta^{(j)}\), respectively. Figure 3 depicts the persistence diagrams for the reference and modified bags for a specfic data point. The bottleneck distance quantifies how much the topology of a set has changed. We say there is evidence that \(\mathbf{x}_{j}\) is anomalous if \(W(D,D^{(j)})\) is relatively large compared to the values in \(\{W(D,D^{(j)})\}_{j=1}^{m}\). There are some undesirable cases that may occur due to the random sampling used to form \(\beta\). It may be that the observations contained in \(\beta\) do not adequately represent the entire data set, or if the reference bag contains an anomaly, we might replace an anomaly with a non-anomalous vector when forming the modified bag. To mitigate issues such as these, the algorithm uses multiple bags of the same size. We select hyperparameters \(S,N\in\mathbb{N}\) and repeat \(N\) times the process of randomly choosing \(S\) vectors to form \(\beta\). This creates a collection of reference bags \(\{\beta_{k}\}_{k=1}^{N}\). For each of the \(N\) bags, we form \(m\) distinct modified bags \(\{\beta_{k}^{(j)}\}_{j=1}^{m}\) by randomly choosing \(\mathbf{y}\in\beta_{k}\) and replacing it with \(\mathbf{x}_{j}\). We calculate the summary statistics mean, median, and standard deviation for the bottleneck distances, and choose a function \(f:\mathbb{R}^{3}\rightarrow\{0,1\}\) that identifies anomalies from the summary statistics. The entire algorithm is presented in Algorithm 1. Figure 3: A plot of the persistence diagram for 20 th reference diagram (left) and the modified persistence diagram (right) when week 6 replaces one of the randomly chosen observations in the 7 th reference bag. This corresponds to the traffic behavior at sensor 5314402 on Monday, 6 February 2017 from 7:55–8:55 AM. Figure 2: The left side represents one of the reference bags, while the right side represents the corresponding modified bag for week 6. The summary statistics of the bottleneck distances \(\{d_{j,k}\}_{k=1}^{N}\) can be used in various ways depending on the application. In our application to traffic data, we set thresholds for each summary statistic based on training data. Thus, we set thresholds \(\tau_{1},\tau_{2},\tau_{3}\) for the three summary statistics, and we defined \(f(\overline{d}_{j},h_{j},s_{j})=1\) if and only if \(\overline{d}_{j}\geq\tau_{1},h_{j}\geq\tau_{2}\), and \(s_{j}\geq\tau_{3}\). In addition to those previously mentioned, we may also encounter the issue when the modified bag \(\beta^{(k)}\) is formed by replacing the same vector \(\mathbf{x}_{k}\). This would make an anomaly look much less anomalous based on our bottleneck distance measurement. Fortunately, if \(N\) is chosen to be sufficiently large, then the effect can be very small since the summary statistics converge in probability. Let us formalize the probability distribution here. The sample space consists of ordered pairs  
\[\Omega=\{(\beta,\mathbf{y}):\beta\subset\mathbf{D},|\beta|=S,\mathbf{y}\in \beta\}.\]  
We place the uniform distribution on \(\Omega\) and denote this by \(\mathbb{P}\). **Theorem 1**. : _Let \(\overline{d}_{j}\), \(s_{j}\), and \(h_{j}\) be denote the mean, standard deviation, and median respectively of bottleneck distance associated with \(\mathbf{x}_{j}\) as computed in Algorithm 1.