Computational Methods to Discover Sets of Patterns of Behaviors that Precede Political Events of Interest

No. 9: Technosocial Predictive Analytics

Volume

Papers from the 2009 AAAI Spring Symposium

Contents

In this paper we present an approach to identify sets of patterns of behaviors which precede political events of interest (EoIs) 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 EoI and only before the occurrences of EoIs. Not all EoIs instances exhibit the same patterns preceding their occurrence, but we hypothesize that there exist sets of patterns which, taken together, precede all EoIs of the same type. A set of patterns which taken to- gether precede all EoIs of the same type are called a "cover". We describe a computationally efficient cover discovery operation based on a randomized greedy al- gorithm which grows patterns simultaneously with the cover. This cover discovery algorithm was implemented in the Java programming language. Although the opti- mal cover discovery problem is NP-complete, our al- gorithm runs in polynomial time and returns nontrivial results.