Fast and near-optimal monitoring for healthcare acquired infection outbreaks
Since the time of Hippocrates , the “father of western medicine” , a central tenet of medical care has been to “do no harm . ”, Unfortunately , the scourge of healthcare acquired infections ( HAI ) challenges the medical system to honor this tenet ., When patients are hospitalized they are seeking care and healing , however , they are simultaneously being exposed to risky infections from others in the hospital , and in their weakened state are much more susceptible to these infections than they would be normally ., Acquiring these infections increases the chances of either dying or becoming even sicker , which also lengthens the time the patient needs to stay in the hospital ( increasing costs ) ., These infections can range from pneumonia and gastro-intestinal infections like Clostridium difficile to surgical site infections and catheter associated infections , which puts nearly any patient in the hospital at risk ., Antibiotic treatments intended to aid in recovery from one infection , may open the door for increased risk of infection from another ., Healthcare acquired infections are a significant problem in the United States and around the world ., Some estimates put the annual cost between 28 and 45 billion US dollars per year in the US 1 ., More importantly , they inflict a significant burden on human health ., A recent study estimated more than 2 . 5 million new cases per year in Europe alone , inflicting a loss of just over 500 disability-adjusted life years ( DALYS ) per 100 , 000 population 2 ., Given their burden and cost , their prevention is a high priority for infection control specialists ., A simple approach to monitor HAI outbreaks would be to test every patient and staff in the hospital and swab every possible location for HAI infection ., However , such a naive process is too expensive to implement ., A better strategy is required to efficiently monitor HAI outbreaks ., A recent review article 3 included 29 hospital outbreak detection algorithms described in the literature ., They found these fall into five main categories: simple thresholds , statistical process control , scan statistics , traditional statistical models , and data mining methods ., Comparing the performance of these methods is challenging given the myriad diseases , definitions of outbreaks , study environments , and ultimately the purpose of the studies themselves ., However , the authors identify that few of these studies were able to leverage important covariates in their detection algorithms ., For example , including the culture site or antibiotic resistance was shown to boost detectability ., Past simulation based approaches 4 tackle optimal surveillance system design , by choosing clinics as sensors , to increase sensitivity and time to detection for outbreaks in a population ., In contrast , our approach selects most vulnerable people and locations to infections as sensors to detect outbreaks in a hospital setting ., Different kinds of mechanistic models have also been used for studying HAI spread 5 , 6 , 7 , 8 ., Most of these are differential equation based models ., We refer to 9 for a review of mechanistic models of HAI transmission ., On a broader level , sensor selection problem for propagation ( of contents , disease , rumors and so on ) over networks has gained much attention in the data mining community ., Traditional sensor selection approaches 10 , 11 typically select a set of nodes which require constant monitoring ., Instead , in this paper , we select sensor set as well as the rate to monitor each sensor ., Hence , our approach is novel from the data mining perspective as well ., Recently Shao et al . 12 proposed selecting a set of users on social media to detect outbreaks in the general population ., Similarly , Reis et al . 13 proposed an epidemiological network modeling approach for respiratory and gastrointestinal disease outbreaks ., Other closely related data mining problems include selecting nodes for inhibiting epidemic outbreaks ( vaccination ) 14 , 15 , 16 and inferring missing infections in an epidemic outbreak 17 ., We employ a simulation and data optimization based approach to design our algorithm and to provide robust bounds on its performance ., Additionally , our simulation model is richly detailed in terms of the class of individuals and locations where sampling can occur ., None of the prior works explicitly model the multiple pathways of infections for HAI outbreaks and fail in separating the location contamination and infections in people ., We formalize the sensor set problem as an optimization problem over the space of rate vectors , which represent the rates at which to monitor each location and person ., We consider two objectives , namely the probability of detection and the detection time , and show that the prior satisfies a mathematical property called submodularity , which enables efficient algorithms ., In addition , we leverage data generated from a carefully calibrated simulation using real data collected from a local hospital ., Our extensive experiments show that our approach outperforms the state-of-the-art general outbreak detection algorithm ., We also show that our approach achieves the minimum outbreak detection time compared to other alternatives ., To the best of our knowledge , we are the first to provide a principled data-driven optimization based approach for HAI outbreak detection ., Though we validate our approach for a specific HAI , namely C . difficile , our general approach is applicable for other HAIs with similar disease model as well ., As previously mentioned , we propose a data-driven approach in selecting the sensors ., There are multiple challenges in obtaining actual HAI spread data such as high cost , data sparsity , and the ability to safeguard patient personal information ., For this reason , we rely on simulated HAI contagion data ., We use a highly-detailed agent-based simulation that employs a mobility log obtained from local hospitals 18 , 19 to produce realistic contagion data ., All the steps of this methodology are described in detail in 18 , and we summarize them below for completeness ., Fig 1 shows a visualization of simulated HAI spread ., In this simulation , people ( human agents ) move across various locations ( static agents ) as defined by the mobility log and spread HAI in stochastic manner ., The simulation was developed in the following three steps: design of an in-silico or computer-based population and its activities , conceptualization of a disease model for a pathogen of interest , and the employment of a highly-detailed simulation ., The following sections describe the data creation process in more detail ., Recall that our goal is to select a set of agents as sensors , and the rate at which each such sensor should be monitored , such that future HAI outbreaks are detected with high probability , and as early as possible ., However , these have to be selected within given resource constraints ., We start with a formalization of these problems ., Finding a minimum cost sensor set is a challenging optimization problem , and we present efficient algorithms by using the notion of submodularity ., We first define some notations ., Let bold letters represent vectors ., Let P and L denote the sets of human agents and locations respectively; let n = |P ∪ L|—this will be the total number of agents in our simulations ., Let B denote the budget on a number of samples that is permitted ( weighted by cost of agents ) , i . e , it is the sum of expected number of swabs to detect whether a location is contaminated or a human is infected ., As mentioned earlier , the mobility logs are represented as a bipartite temporal network G ( P , L , E , T ) , with two partitions P and L representing agents , E representing who-visits-what-location relationship and T representing time/duration of the visit ., We consider each agent to be a node in the temporal network G . Hence we use the terms node and agent interchangeably ., Now , let c ∈ Rn , be the vector of costs , i . e . , cv is the cost of monitoring node v . Let r ∈ Rn be the vector of monitoring rates , where rv denotes that the probability that node v is monitored ( e . g . , swabbed ) each day ., Finally , let Tmax denote the maximum time in each simulation instance ., Unfortunately , Problems 1 and 2 are both computationally very challenging ., In fact , both the problems can be proven to be NP-hard ., Lemma 1 . Problem 1 is NP-hard ., Lemma 2 . Problem 2 is NP-hard ., We provide the proofs for both the lemmas in the supplementary , where we show that the NP-Complete SetCover problem can be viewed as a special case of both the Problems 1 and 2 . Since our problems are in the computational class NP-hard , they cannot be solved optimally in polynomial time even for simplistic instances , unless P = NP ., The instances we need to consider are pretty large , so a naive exhaustive search for the optimal solution is also not feasible and will be too slow ., Therefore , we focus on designing efficient near-optimal approximate solutions ., We begin with Problem 1 . The function we are trying to optimize for problem 1 is defined over a discrete lattice , i . e . the rate vector r ., Our approach is to show that this function is a submodular lattice function ., The notion of submodularity , which is typically defined over set functions , can be extended to discrete lattice functions ( e . g . recenty in 32 ) ., Informally , submodularity means that the objective value has a property of diminishing returns for a small increase in the rate in any dimension ., It is important to note that submodularity for lattice functions is more nuanced than for simple set functions ( we define it formally in the Supplementary Information section ) ., Fortunately , it turns out that this property implies that a natural greedy algorithm ( which maximizes the objective marginally at each step ) gurantees a ( 1 − 1/e ) -approximation to the optimal solution ., Without such a property , it is not clear how to solve Problem 1 efficiently even for a small budget ., We have the following lemma ., Lemma 3 ., The objective in Problem 1 is a submodular lattice function ., The detailed description of the submodularity property and proof of lemma 3 are presented in the supplementary ., Our HaiDetect algorithm for Problem 1 selects the sensors to be monitored and rates such that nodes which tend to get infected across multiple simulation instances have higher infection rates ., Specifically , at each step , HaiDetect selects the node v and the rate r among all possible candidate pairs of nodes and rates , such that the average marginal gain is maximized ., HaiDetect keeps adding nodes and/or increasing the rates to monitor the selected nodes until the weighted sum of the rates is equal to the budget B . The detailed pseudocode is presented in Algorithm 1 . Algorithm 1 HaiDetect Require: I , budget B 1: for each feasible initial vector r0 do 2: Initialize the rate vector r = r0 3: while ∑v rv ⋅ cv < B do 4: Find a node v and rate r maximizing average marginal gain 5: Let rv = r 6: Remove all candidate pairs of nodes and rates which are not feasible 7: Return the best rate vector r HaiDetect has desirable properties in terms of both effectiveness and speed ., The performance guarantee of HaiDetect is given by the following lemma ., Lemma 4 ., HaiDetect gives a ( 1-1/e ) approximation to the optimal solution ., The lemma above gives an offline bound on the performance of HaiDetect , i . e . , we can state that the ( 1-1/e ) approximation holds even before the computation starts ., We can actually obtain a tighter bound by computing an empirical online bound ( once the solution is obtained ) which can be derived using the submodularity and monotonicity of Problem 1 . For us to state the empirical bound , let us define some notations ., Let the solution selected by HaiDetect for a budget B be r ^ ., Similarly , let the optimal vector for the same budget be r* ., For simplicity , let the objective function in Problem 1 be R ( ⋅ ) ., For all nodes v and for a ∈ 0 , 1 , let us define Δv as follows:, Δ v = max a R ( r ^ ∨ a · χ { v } ) - R ( r ^ )  ( 8 ) Similarly let us define σv as the argument which maximizes Δv σ v = arg max a R ( r ^ ∨ a · χ { v } ) - R ( r ^ )  ( 9 ) Now , let δ v = Δ v c  v  · σ v . Note that for each node v , there is a single δ ., Let the sequence of nodes s1 , s2 , … , sn be ordered in decreasing order of δv ., Now let K be the index such that θ = ∑ i = 1 K - 1 c  s i  σ s i ≤ B and ∑ i = 1 K c  s i  σ s i > B . Now the following lemma can be stated ., Lemma 5 . The online bound on R ( r* ) in terms of the current rate r ^ assigned by HaiDetect is as follows:, R ( r * ) ≤ R ( r ^ ) + ∑ i = 1 K - 1 Δ s i + B - θ c  s K  σ s K Δ s K The lemma above allows us to compute how far the solution given by HaiDetect is from the optimal ., We compute this bound and explore the results in detail in the Results section ., In addition to the performance guarantee , HaiDetect’s running time complexity is as follows ., Lemma 6 . The running time complexity of HaiDetect is O ( c ⋅ B2 ( |P| + |L| ) ) , where c is the number of unique initial vectors r0 , B is the budge , P is the set of human agents and L is the set of locations ., Note that the constant c is much smaller than the total population , i . e . , c << |P| + |L| in our case as infections are sparse and we do not need to consider agents and locations which never get infected ., The most expensive computational step in Algorithm 1 is the estimation of the node v and rate r that gives the maximum average marginal gain ( Step ( i ) of 1, ( b ) ) ., This can be expedited using lazy evaluations and memoization ., Hence , the algorithm is also quite fast in practice ., Moreover , it also embarrassingly parallelizable ., The steps, ( a ) and, ( b ) for each initial vector can be performed in parallel ., We also propose a similar algorithm HaiEarlyDetect for Problem 2 . The main idea here is that we assign higher rates to nodes which tend to get infected earlier in many simulation instances ., The pseudocode for HaiEarlyDetect is presented in Algorithm 2 . Algorithm 2 HaiEarlyDetect Require: I , budget B 1: for each feasible initial vector r0 do 2: Initialize the rate vector r = r0 3: while ∑v rv ⋅ cv < B do 4: Find a node v and rate r minimizing the average detection time 5: Let rv = r 6: Remove all candidate pairs of nodes and rates which are not feasible 7: Return the best rate vector r As shown in Algorithm 2 , HaiEarlyDetect optimizes the marginal gain in the objective in Problem 2 in each iteration ., It turns out that the objective in Problem 2 is not submodular ., However , as shown by our empirical results , the greedy approach we propose works very well in practice and outperforms the baselines ., Moreover , it too runs fast in practice as the same optimization techniques discussed earlier for HaiDetect applies to HaiEarlyDetect as well ., In the previous section , we discussed two types of bounds on the performance of HaiDetect ., Here we show how far the solution given by HaiDetect is from the optimal value for various budgets ., For this experiment , we ran HaiDetect on a set of 100 simulations and computed the value of the objective in Problem 1 for the resulting rate vector ., We also computed the overall bound , based on ( 1 − 1/e ) approximation and the empirical bound as per Lemma 5 ., Since the objective value cannot exceed the number of simulations , we also compute the lowest bound as the minimum of two bounds and the number of simulations ., We repeat the experiment for budget size from 1 to 50 ., The resulting plot is presented in Fig 5 ., Fig 5 highlights several interesting aspects ., First of all , we can see that the online bound is always tighter than the offline bound ., Moreover , we also observe that as the performance of HaiDetect reaches close to the optimal ( with increase in budget ) , the online bound becomes more and more tight until both the performance and bound are equal , indicating the values of the budget for which HaiDetect solves Problem 1 optimally ., This results demonstrates that HaiDetect can accurately find sensors which can detect any observed outbreaks given sufficient budget ., Given that HaiDetect is near-optimal for the observed outbreaks , we evaluate its effectiveness in detecting unseen ( “future” ) outbreaks ., Here , we compare the performance of HaiDetect and Celf with respect to the budget on “unobserved” simulations ., For this experiment , we performed a 5-fold cross validation on 200 simulations ., Specifically , we divided the simulations into 5 groups , and at each turn we selected the sensors in the first four groups and computed the sum of outbreak detection probability as shown in Eq 1 in the fifth group ( the test set ) ., Then we normalize the resulting sum of outbreak detection probability by total number of simulation instances in the the same group ., The normalized value can be intuitively described as the average probability of detecting a future outbreak ., We repeat this process five times ensuring each group is used for success evaluation ., We then compute the overall average and its standard error ., We repeat the entire process for the budgets from 1 to 50 ., The result of our experiment is show in Fig 6 ., The first observation is that HaiDetect consistently outperforms Celf for all values of the budget ., The disparity between the methods is more apparent for larger values of budget ., The difference in quality of the sensors can be explained by the fact that Celf only assigns rate of 0 or 1 ., However , HaiDetect can strategically assign non-integer rates so as to maximize the likelihood of detection ., We can also observe that the standard error for the HaiDetect decreases and is negligible for larger budgets ., However , it is not the case for Celf ., This shows that not only the quality of sensors detected by HaiDetect is better , but it is more stable as well ., Finally , we see that probability of an outbreak being detected by sensors selected by HaiDetect is 0 . 96 when budget is equal to 50 , whereas it is only around 0 . 75 for Celf ., Similarly , a budget of only 25 is required to detect an outbreak with probability of 0 . 8 for HaiDetect ., For the same budget , sensors selected by Celf detect cascades with probability of 0 . 55 ., The result highlights that HaiDetect produces more reliable monitoring strategy for HAI outbreak detection ., Here , we investigate the change in performance of HaiDetect and Celf as the number of simulations used to detect the sensor increases ., For this experiment , we used 150 distinct simulations ., We divided the simulations into two categories , training and testing sets ., We used the cascades in the training set to select the sensors and used the ones in the testing set to measure quality ., First we decided on a budget of 10 and training size of 10 cascades ., We ran both HaiDetect and Celf for this setting and measured the quality using the cascades in the testing set ., We then increased the training size by 10 till we reached the size of 100 ., We repeated the same procedure for budgets of 30 and 50 ., We compute the average probability of detection in the same manner as described above ., Fig 7 summarizes the result ., We can observe that HaiDetect outperforms Celf consistently ., It reinforces the previous observation that HaiDetect selects good sensors for the HAI outbreak detection ., An interesting observation is that the performance tails off after training size of 20 for larger budgets , which implies that not many cascades have to be observed before we can select good quality sensors ., This is an encouraging finding as gathering large number of real cascades of HAI spread is not feasible ., Next we study the change in performance of HaiDetect with the training size for various budget sizes ., Here we tracked the performance of HaiDetect for budgets of 10 , 30 , and 50 for training sets of various size ., The result is summarized in Fig 8 ., As shown in the figure , the difference between peformance of HaiDetect for budgets 30 and 10 is much larger than that for budgets 50 and 30 ., The normalized objective , or the probability of detection , is close to 1 at budget 50 , indicating that monitoring sensors at rates assigned by HaiDetect detects almost all the HAI outbreaks ., Hence , in expectation , roughly 50 swabs a day is enough to monitor an outbreak in a hospital wing ., Again , we observe that performance of HaiDetect tails off after the training size of 20 ., It provides extra validation for the observation that a limited number of observed cascades are enough to select high quality sensors ., A desirable property of sensors is that they aid in early detection of outbreaks ., Here we study the average detection time of future outbreaks using the sensors and rates selected by HaiEarlyDetect ., In this experiment , we first divided our simulations into equally sized training and testing sets , each having 100 simulations ., We ran HaiEarlyDetect on the training set to detect sensors and rates at which to monitor them ., Then , we monitored the selected sensors at the inferred rates and measured the detection time for each simulation in the testing set ., We repeated the entire process for various budgets ., The detection time averaged over 100 simulated outbreaks in the testing set is summarized in Fig 9 and the variance in the detection time is shown in Fig 10 ., As shown in the figure , as the budget increases the average detection time decreases ., According to our results , the average time to detect an outbreak in the testing set while monitoring sensors selected for budget of 1000 is roughly six days ., This is impressive considering the fact that monitoring all agents results in detection time of 4 days monitoring all of more than 1200 nurses results in detection time of 8 days ., Hence , monitoring these sensors detect the outbreak earlier with fewer budget ., Another advantage of our sensors is that they are diverse ., Significant proportion of the selected sensors include patients and fomites , which are easier to monitor than the nurses ., Hence , monitoring the sensors selected by HaiEarlyDetect also has an economic advantage ., An interesting observation seen in Fig 10 is that the variablity in average detection time decreases with the increase in budget ., Hence , we expect the performance of our sensors to be fairly consistent in detecting future outbreaks for larger budgets ., Moreover , the median time to detect an outbreak ( as shown by the box plots ) is always less than the average ., Hence , we expect that performance of HaiEarlyDetect to be generally better than that suggested by the average detection time ., For budget of 1000 , the median detection time is just 5 days ., Note that monitoring all agents results in detection time of 4 days ., This implies that in practice our approach requires only 1000 swabs per day to detect an outbreak within a single day of the first infection ., An interesting question is how many potential cases can be prevented by monitoring the sensors selected by HaiEarlyDetect ., Here we study how many nodes get infected before an outbreak is detected and how many potential infections can be prevented by monitoring our sensors for various budgets ., As in the previous experiment , for a given budget , we leverage 100 simulations to select sensors and their monitoring rates ., Once the sensors are selected , we count the number of infections that occur in a test simulation before a sensor is infected and how many further infections occur following the infections of sensors ., We then average these numbers over 100 test simulations ., The results are summarized in Table 2 ., As shown in Table 2 , for the budget of 10 samples/swabs , 4 . 31 potential future infections could prevented ., Note that there are only 23 infections on average per simulation ., For the budget of only 200 , 15 . 02 infections could be prevented , which is about 66% of potential infections ., The number goes up to 17 , or 74% for the budget of 1000 ., The result shows that even for a low budget ( less than 200 swabs per day ) , our approach could help prevent a significant number of future infections ., Next we study the types of agents that are selected by HaiDetect as sensors ., For this experiment , we use 100 randomly selected simulations to detect sensors for a wide range of budgets ., After the sensors are selected , we sum up the rates of each category of agents like nurses , doctors , patients , and so on ., Fig 11, ( a ) shows the distribution of sensor allocation for each category of agents at low budgets ., We observe that for a budget of 10 , nearly 60% of the total budget is spent on selecting nurses ., Since nurses are the most mobile agents , the result highlights the fact that HaiDetect selects the most important agents as sensors early on ., Similarly , Fig 11, ( b ) shows the distribution of sensors for higher budgets ., Here we observe that nearly 35% of the budget is allocated for nurses ., Fomites and patients have roughly equal allocations of about 20% ., 17% of the budget is allocated to doctors ., The rest of the categories have minimal allocation ., The distribution shows that HaiDetect selects heterogeneous sensors including both people and objects/locations as intended ., Finally , we are also interested on the scheduling implications of the sensors selected by HaiDetect ., To this end , we measure the aggregated proportion of budget assigned to each rate for the sensors we select ., The results are summarized in Fig 12 ., As shown in Fig 12, ( a ) , most of the sensors have rate of 0 . 1 ., Very few sensors have rate from 0 . 2 to 0 . 5 ., Finally , there is a sudden spike at rate = 1 . 0 ., When we look at rate distribution for each category separately , interestingly we observe that only nurses have rates of 1 . 0 ., This implies that certain nurses have to be monitored each day to detect HAI outbreak ., The reason behind this unexpected behaviour can be attributed to the fact that the hospital from where the mobility log was collected , required all the nurses to attend a daily meeting ., Hence , all the nurses were in contact with each other every day and it is likely that nurses infect each other in case of an outbreak ., Hence , there is an advantage in monitoring some of the nurses everyday to quickly detect HAI outbreak ., Effective and early detection of HAI outbreaks are important problems in hospital infection control , and have not been studied systematically so far ., While these are challenging problems , understanding their structure can help in designing effective algorithms and optimizing resources ., Current practices in hospitals are fairly simple , and do not attempt to optimize resources ., Our algorithms perform better than many natural heuristics , and our results show that a combination of data and model driven approach is effective in detecting HAIs ., Since there is limited data on disease incidence , good models and simulations play an important role in designing algorithms and evaluating them .
According to the Centers for Disease Control and Prevention ( CDC ) , one in twenty five hospital patients are infected with at least one healthcare acquired infection ( HAI ) on any given day ., Early detection of possible HAI outbreaks help practitioners implement countermeasures before the infection spreads extensively ., Here , we develop an efficient data and model driven method to detect outbreaks with high accuracy ., We leverage mechanistic modeling of C . difficile infection , a major HAI disease , to simulate its spread in a hospital wing and design efficient near-optimal algorithms to select people and locations to monitor using an optimization formulation ., Results show that our strategy detects up to 95% of “future” C . difficile outbreaks ., We design our method by incorporating specific hospital practices ( like swabbing for infections ) as well ., As a result , our method outperforms state-of-the-art algorithms for outbreak detection ., Finally , a qualitative study of our result shows that the people and locations we select to monitor as sensors are intuitive and meaningful .
Healthcare acquired infections ( HAIs ) lead to significant losses of lives and result in heavy economic burden on healthcare providers worldwide ., Timely detection of HAI outbreaks will have a significant impact on the health infrastructure ., Here , we propose an efficient and effective approach to detect HAI outbreaks by strategically monitoring selected people and locations ( sensors ) ., Our approach leverages outbreak data generated by calibrated mechanistic simulation of C . difficile spread in a hospital wing and a careful computational formulation to determine the people and locations to monitor ., Results show that our approach is effective in detecting outbreaks .
medicine and health sciences, gut bacteria, medical personnel, sociology, social sciences, health care, simulation and modeling, health care providers, systems science, mathematics, network analysis, social networks, nosocomial infections, bacteria, allied health care professionals, research and analysis methods, clostridium difficile, infectious diseases, computer and information sciences, epidemiology, agent-based modeling, people and places, professions, nurses, population groupings, biology and life sciences, physical sciences, organisms