Predicting Terrorist Attacks in the United States using Localized News Data

We formulate the task as a classification problem such that our goal is to learn a function $f:x\xrightarrow{}y$, where $x$ is a set of input features and the binary output $y$ represents the occurrence or non-occurrence of a terrorist attack at a particular location. We consider as locations the set of 51 states in the United States (including Washington D.C., excluding Puerto Rico and other non-state territories), each with $m=862$ features observed over $n=1,413$ calendar days from February 18, 2015 through December 31, 2018, inclusive (as limited by data availability). Let $X\in\mathbb{R}^{n\times m}$ be a feature matrix and $\vec{y}=\{0,1\}^{n}$ be a label vector, such that $\vec{x}_{i}$ and $y_{i}$ denote the feature vector and label, respectively, that describe the $i^{th}$ day at the location of concern. Further, we use $X_{i,j}$ to represent the $i^{th}$ observation of the $j^{th}$ feature, $X_{i:k}$ to represent the $i^{th}$ through $k^{th}$ (inclusive) observations of all $m$ features, and $X_{*,j}$ to represent the column vector that contains all observations of the $j^{th}$ feature. Unless stated otherwise, we treat locations as independent such that each has a distinct feature matrix $X$ and label vector $\vec{y}$. Finally, we use square brackets $\left[\right]$ to denote vectors.

Recall that our goal is to predict future terrorist attacks. However, the features and labels described above represent news activity and the occurrence of an attack, respectively, for the same day. In a real-world scenario, the news features for a given day would not be available until after the attack occurred. Additionally, the features only consider news activity for a single day; this precludes the discovery of any long-range temporal patterns. In other words, in its raw form the data could be used same-day terrorism detection, but not prediction.

To address both of these shortcomings, we performed an additional preprocessing step to generate new feature representations for each date and location pair using what we call an observation window (Galla and Burke, 2018). This window, represented by the hyperparameter $\Delta t\geq 1$, is the number of prior days for which news features are observed when predicting an attack. As outlined in Fig. 2, we evaluated three distinct types of observation windows: a fixed-length moving average, a variable-length moving average, and a stacked representation. Each approach is detailed below.

Recall that our task is to learn a function $f:x\xrightarrow{}\{0,1\}$ for some input $x$. Toward this end we explored two families of machine learning algorithms, ensembles and neural networks, which we detail below.

When trained on imbalanced data, the predictions of machine learning models can be biased toward the majority class. We utilized the following techniques to address this problem:

All experiments utilized Python 3.7.3 in conjunction with sklearn 0.22.2 (ensemble methods) and Keras 2.2.4 with TensorFlow 2.0 (neural networks). For the Random Forest and AdaBoost we used 3,000 estimators and Gini index as the splitting criterion for each tree. We trained all neural networks for 100 epochs using stochastic gradient descent with a learning rate of $1e^{-4}$, a decay parameter of $1e^{-6}$, a batch size of 32, and Nesterov momentum. All hidden layers (except the first hidden layer in the two-layer FFNN architecture; see Section 2.3.3) contained 8,000 neurons, and each hidden layer in the LSTM model contained 1,024 neurons. For the neural network models we used min-max normalization to scale the input. Beyond computing the observation windows, No further preprocessing was required for the ensembles. We tested the fixed-length moving average approach with the ensemble methods and the stacked representation with the neural networks. However, due to the success of the K-S moving average ($\Delta t*$) with the ensembles, we also tested this representational method with the neural networks.

We evaluated each model using 5-fold cross-validation. This was straightforward for the neural network models and when $\Delta t=1$, since each observation is independent. However, when using either moving average approach we included additional considerations in order to maintain proper separation between the training and testing sets:

1. (1)

   When testing the variable-length moving average ($\Delta t^{*}$), we used only the training data to compute the optimal observation windows for each feature. We then computed moving averages on the testing set using the same window lengths that were learned from the training set.

2. (2)

   When testing either type of moving average, we removed any examples from the training set whose values were dependent on examples in the testing set. For example, consider the case where $\Delta t=14$ and the testing fold is the 282 days from Mar. 25 through Dec. 31, 2018. The feature values for Mar. 25 will be highly correlated with the values for Mar. 11-24, which are in the training set, since their moving averages are computed using at least one of the same observations. We resolved this by dropping Mar. 11-24 from the training set. This approach handicaps the moving average models (since they are provided with fewer training examples), but ensures that the testing sets are consistent across all models.

Finally, we measured model performance on each testing set using area under the receiver operating characteristic curve (AUROC). An ROC curve plots a model’s true positive rate against its false positive rate at various discrimination thresholds, and is thus a useful measure of classification performance in an imbalanced setting. An AUROC of 1.0 indicates a perfect classifier, while a random guesser converges to 0.5. We repeated each 5-fold cross-validation experiment 10 times and report both the mean and standard deviation AUROC values for each model.

Figure 3 depicts model performance as a function of observation window (each tick on the x-axis is a separate model) for RF and FFNN. We note that the trend of RF’s performance is relatively stable with respect to increasing observation windows. FFNN, on the other hand, is relatively sensitive to small changes to the observation window. This instability is likely attributable to noise, and suggests that FFNN is much more prone to overfitting than RF. From this result we additionally note that the trend and optimal window varies between states. While this suggests that a predictive model may need to be tuned separately for each state, it is also possible that some of this variation is due to noise and/or only having a small number of events per state.

Some of the attacks recorded in the GTD are clustered in time and space. For example, in 2016 attacks were carried out in New York on August 9 (anti-Semitic extremists detonated explosives outside the houses of two Rabbis in New York City), August 10 (an arsonist targeted a private residence in Endicott), and August 13 (a man shot and killed an Imam and his assistant outside a mosque in New York City). Additionally, there are a small number of attacks that spanned a number of days and/or targets, such as in October 2018, when pro-Trump extremists sent pipe bombs to five different targets on four different dates. To test whether temporal locality had biased the model outputs, we recorded for each attack the predicted probability ($P(y=1)$) and the number of days that had elapsed since the previous attack in that state. Figures 4(a) and 4(b) visualize this distribution for RF and FFNN, respectively, along with a regression line for each state. These results, along with the correlation coefficient from Spearman’s rank test ($r_{s}$), indicate that RF still performs well on many of the attacks that are not close together in time, which is an important characteristic of a robust model. FFNN performed more poorly on attacks that were farther apart in time, which likely contributed to its weaker overall performance.

The fact that our data set is both small and highly imbalanced is almost certainly a limiting factor in model performance. Additionally, the temporal nature of our data limits our ability to use stratified cross validation, so the events are not distributed evenly across training and testing folds. In Figures 5(a) and 5(b), the AUROC of each testing fold is shown as a function of the number of events in the corresponding training fold for RF and FFNN, respectively. When computed across all states, the line of best fit and Spearman’s rank coefficient ($r_{s}$) for these results surprisingly suggest a negative correlation—i.e., that more training and testing examples is correlated with worse performance. However, in the case of RF, we can see that the folds from California—on which RF’s predictions were close to random guessing—contribute significantly to this result since they contain many events. Without California, $r_{s}$ increases from $-0.241$ to $0.136$ for RF—the positive correlation we would expect. However, for both RF and FFNN it seems that the lack of events or data is not the only limiting factor. It is likely that data quality and/or noise are additional barriers, ones that are more pronounced given the small number of events.

Understanding the role of each group of features can help us mitigate noise and more deeply understand how our features contribute to successful (or unsuccessful) predictions. Toward this end, we retrained RF and FFNN using different combinations of feature groups. Figure 6 shows the baseline classification results on each state along with results from four additional feature-filtered models, and is the basis for the following observations:

1. (1)

   In general, the importance of each feature group varied between states. This affirms the need to consider a unique model for each state.

2. (2)

   The only feature group that improved performance in all cases was CAMEO counts. Further, in most states the model without CAMEO counts performed the worst. This implies that CAMEO counts are, on average, the most potent feature group.

3. (3)

   In some cases, dropping a feature group improved model performance; for example, RF’s predictions on California. This is further evidence of the impact of noise on classification results, and creates an important point of investigation for any future work that would seek to optimize predictions for a particular state or location.

Terrorist attacks vary widely with respect to responsible party, target, method and other properties. Some types of attacks may be easier or harder to predict, or even characterized by different feature distributions. We used a Kruskal-Wallis H-test to test whether the median predictions from RF or FFNN differed significantly by each of the GTD’s prominent categorical features: attack type (e.g., armed assault, bombing), primary weapon type (e.g., firearms, explosives), target type (e.g., military, religious institutions), and responsible group. As Figure 7 shows, each test produced a $p$-value $>0.1$, so we cannot conclude that there is a correlation between the characteristics of an attack and prediction success.

Our baseline task is to predict the occurrence of a terrorist attack in a given state on a single day. Some prior work found success in making predictions over coarser periods of time, such as a week (Galla and Burke, 2018). However, we found this was not the case for our problem. We evaluated the following three methods for performing predictions over a given prediction window $\Delta p>1$:

1. (1)

   Label propagation: we propagated event labels backward to the previous $\Delta p$ observations. For example, given an attack on Jan. 3 and $\Delta p=3$, we labeled Jan. 1, 2, and 3 as attacks.

2. (2)

   Date aggregation: we aggregated the news features from $\Delta p$ dates into a single observation. For example, given $\Delta p=3$, we combined Jan. 1, 2, and 3 into a single observation: Jan. 1-3. We further used mean pooling to generate the feature values for each aggregated observation.

As shown in Figures 8, these approaches resulted in worse performance, with only a few exceptions. AUROC measures the trade-off between true positives and false positives, so whatever improvements larger prediction windows might have provided in successfully predicting attacks is counterbalanced by an increase in false positives. This is not surprising given that all of these methods run the risk of blurring the observed distinctions between classes. Date aggregation has the additional disadvantage of further reducing the number of training examples. A potential item of future work is to develop a more sophisticated method for making predictions over coarse periods of time without blurring the distinction between individual examples.

One of our key challenges is a lack of data. While our results thus far have shown that each state should be modeled independently, we also hypothesized that it could be possible to transfer knowledge between models. To evaluate the feasibility of such an approach, we trained a new set of models by combining data from multiple states. For example, when testing the New York model at baseline, we only included the training examples from New York; however, in these experiments we also supplemented the training set with additional data from another state (e.g., California) before evaluating on the New York testing set. As the heatmap in Figure 9 shows, this only proved beneficial on average for California. This is not surprising given our previous results, which have suggested that the importance of feature groups and the optimal observation windows vary between states, and further evidences the need for models to be tailored to individual states.

So far we have limited our experiments and analysis to the five states with the most attacks. While we also wanted to evaluate our model on other states, none of them experienced more than seven recorded attacks (Table 1). We found that with such a small number of minority class examples it was impossible to learn an effective model. In an attempt to address this challenge, we considered the eight states that had experienced between five and seven attacks, and used hierarchical clustering (Euclidean distance, average link) to group them based on the observed news features. We tested two different grouping methods:

1. (1)

   Single-state testing. After choosing a single state to evaluate and splitting the data into training and test dates, we used hierarchical clustering to supplement the training set with data from the states most similar to the testing state. We continued to add additional states to the training set until the number of attacks in the training set exceeded a fixed threshold. In order to maintain proper training and testing separation, we only supplemented the training set with records that matched the dates of the records in the original training set. Then the model was trained on the multi-state training set and evaluated on the testing set from only the testing state (as in Section 3.7).

2. (2)

   Group testing. In these experiments, we also added data from the clustered states to the testing set, so that the states were evaluated as a group. For example, since Missouri (MO) is the state most similar to Louisiana (LA), we trained and tested the model on data from both MO and LA.

Figure 10 presents the results from single-state testing using event thresholds between 6 and 16. Table 3 shows for each testing state the states that were most similar and thus clustered, along with the results of group testing. The inconsistent and overall poor performance of both single-state testing and group testing is not surprising given our findings in Section 3.7 that supplementing the training data with examples from additional states reduced model performance, even though in this case we only included the most similar states. These results suggest that in order to make meaningful predictions on these states, we either need more examples of attacks or a model that can identify and account for deeper differences between states.