GatewayNet: a form of sequential rule mining

Abstract

Background: The gateway hypothesis (and particularly the prediction of developmental stages in drug abuse) has been a subject of protracted debate since the 1970s. Extensive research has gone into this subject, but has yielded contradictory findings. We propose an algorithm for detecting both association and causation relationships given a discrete sequence of events, which we believe will be useful in addressing the validity of the gateway hypothesis. To assess the gateway hypothesis, we developed the GatewayNet algorithm, a refinement of sequential rule mining called initiation rule mining. After a brief mathematical definition, we describe how to perform initiation rule mining and how to infer causal relationships from its rules ("gateway rules"). We tested GatewayNet against data for which relationships were known. After constructing a transaction database using a first-order Markov chain, we mined it to produce a gateway network. We then discuss various incarnations of the gateway network. We then evaluated the performance of GatewayNet on urine drug screening data collected from the emergency department at LSU Health Sciences Center in Shreveport. A de-identified database of urine drug screenings ordered by the department between August 1998 and June 2011 was collected and then restricted to patients having at least one screening succeeding their first positive drug screening result.

Results: In the synthetic data, a chain of gateway rules was found in the network which demonstrated causation. We did not find any evidence of gateway rules in the empirical data, but we were able to isolate two documented transitions into benzodiazepine use.

Conclusions: We conclude that GatewayNet may show promise not only for substance use data, but other data involving sequences of events. We also express future goals for GatewayNet, including optimizing it for speed.

Keywords: Association rule mining; Causal network; Gateway hypothesis; Initiation rules; Structure learning.

Fig. 1

Rule proposal algorithm using the a priori principle

Fig. 2

The domain of cert (x→y).Certainty approaches ∞ (i.e., becomes absolute) as sup (x→y) approaches sup (y). Color gradient represents certainty value for cert (x→y)

Fig. 3

The synthetic data set expressed as a gateway network. This network is generated for l_sup=0.05, l_conf=0.5, and l_lift=1.0. It is not apparent if any events qualify as gateway rules in this graph

Fig. 4

The gateway network for l_sup=0.025. Expectedly, this network generates additional interactions. Color gradient represents the certainty of gateway rules

Fig. 5

Windowed initiation rules for z∈{1,2,3}. In this particular case, windowing did not remove any vertices from the graph; however, additional edges are added as their support increases. Color gradient represents the certainty of gateway rules

Fig. 6

Gateway Network for LSUHSC-S data. No gateway rules were found; however, the initiations TCA → BENZODI- AZEPINES and BARBITURATES → BENZODIAZEPINES were discovered. Additionally, benzodiazepines, barbiturates, cocaine are seen to initiate cannabinoids

Fig. 7

LSUHSC-S data over a year-long window. TCAs were eliminated when windowing was applied, and barbiturates no longer directly initiate cannabinoids

Fig. 8

LSUHSC-S data with initiation of opiates removed. Rules with opiates in the antecedent were still retained. Cannabinoids remain the terminal initiation in this graph

Fig. 9

The gateway network with gateway rules highlighted. From this graph, we can tell that I₁, 1₃, and I₅ are gateway events. Because of their blue color, I₁ serves as a strong gateway into I₆ and I₃ into I₅. Color gradient represents the certainty of gateway rules

Fig. 10

The gateway network with all non-gateway rules removed. Color gradient represents the certainty of gateway rules

Fig. 11

The gateway network in Fig. 6, except processed using SPMF. Two gateway rules, $I_1⇝I_3$ and $I_1⇝I_5$ remain highlighted, but other rules have dropped out because of incomplete item set counts