Computational methods to discover sets of patterns of behaviors that precede political events of interest

In this paper we present an approach to identify sets of patterns of behaviors which precede political events of interest (Eols) such as the the onset of regime change, insurgency, ethnic violence, etc.. We define a pattern to be an identified set of values of sampled, quantized factor data which occurs before at least two instances of an Eol and only before the occurrences of Eols. Not all Eols instances exhibit the same patterns preceding their occurrence, but we hypothesize that there exist sets of patterns which, taken together, precede all Eols of the same type. A set of patterns which taken together precede all Eols of the same type are called a "cover". We describe a computationally efficient cover discovery operation based on a randomized greedy algorithm which grows patterns simultaneously with the cover. This cover discovery algorithm was implemented in the Java programming language. Although the optimal cover discovery problem is NP-complete, our al-gorithm runs in polynomial time and returns nontrivial results.