BACKGROUND
the main objective of pharmacovigilance is the early detection of novel adverse drug events  with minimal patient exposure.
the impact of ades results in significant social costs estimated in several billion dollars annually, and inflicts unnecessary, often fatal, harm to patients  <cit> .
hence, their identification is paramount to health care.
spontaneous reporting systems  are database resources encompassing reports of suspected post-marketed ades, and are currently the mainstay in pharmacovigilance.
among the major srss are: the united states food and drug administration’s  adverse event reporting system   <cit> , and the world health organization  programme for international drug monitoring  <cit> .
the fda receives voluntary reports of suspected adverse drug events directly from health care professionals and consumers, as well as mandatory reports from manufacturers, which after a manual review are entered into the aers database.
each report contains patient demographic information, drug information for as many medications as were reported for the event, including suspected drugs and concomitant drugs, coded adverse events using the meddra terminology  <cit>  , patient outcomes, drug therapy dates, meddra coded indications for the reported drugs, and report sources.
the aers database, which is available online, contains over four million reports of adverse events and reflects data from  <dig> to the present.
traditional methods of ade detection in srs databases relied on manual case reviews by clinical/pharmacological experts.
however, due to the increasing size and complexity of srs databases, and limitations in human resources, recently, more efficient methods have been proposed consisting of automated, and quantitative approaches that are commonly referred to as data mining algorithms  or signal detection algorithms.
dmas are generally designed to identify statistically strong associations between drugs and adverse effects .
these associations, also referred to as signals, are not necessarily true ades but rather hypotheses that warrant further investigation to qualify them as credible ades.
they allow evaluators to peruse the large volume of reports and focus their attention on potentially important safety issues.
in recent years a wide range of dmas have been developed to screen potential ades  <cit> .
to estimate incidence rates, dmas use the population of reports in the srs as a proxy for the true population.
the majority of dmas rely on the use of disproportionality measures, such as the relative reporting ratio , which attempt to quantify the degree of “unexpectedness” of a drug-ae association  <cit> .
typically, a pre-defined disproportionality threshold will be used to screen potential ades for further review.
both the fda and who use an adjusted version of rr as a basis for monitoring safety signals in their srs  <cit> .
typical srs databases contain tens of thousands of drugs and adverse effects .
enumerating all possible combinations of ades for statistical analysis, although feasible, is a daunting task and rarely done.
as a result, most published work focuses on subsets of the data, e.g., specific drugs or demographic groups, avoiding data base wide studies.
additionally, most current dmas are designed to identify only binary  associations, i.e., pairs including only one drug and one ae, such as
vioxx→ heart attack,
excluding from analysis the possibility of multi-item associations, e.g.
an association between two drugs and one or two aes, such as
aspirin + warfarin → bleeding.
multi-item ade associations are rarely reported but are important because they could indicate possible drug-drug interactions.
the limitations of bivariate analysis, as well as the importance of and difficulty of multi-item ade detection, also referred to as higher-order ade associations, was emphasized in  <cit>  noting that srs databases provide an opportunity to uncover them as they contain populations that are not well represented in clinical trials.
studies that did consider multi-item ade associations, such as drug-drug interactions, did so only after a careful selection of a small subset of drugs  <cit> .
association rule mining is a well established method for discovering interesting relationships between variables hidden in large databases.
an association rule is an implication expression of the form a→b, where a and b are disjoint itemsets.
in the case of ade detection, a denotes a set of drugs and b a set of aes, e.g.
a= aspirin, warfarin, b= bleeding.
the strength of an association rule is determined by its support and confidence.
the support of an itemset s is the number of records containing a. the support of an association rule s is equal to s, i.e., support determines how often a rule, which in this case is the combination of drugs and aes, is observed in the data.
low support may indicate that a rule has simply occurred by chance, and thus support is often one of the parameters used to screen uninteresting rules.
the confidence of a rule c is equal to s/s, that is, confidence determines how often items in b appear in records that contain a. confidence provides an estimate of pr the conditional probability of b given a, and therefore is used to measure the reliability or interestingness of the rule.
it should be emphasized that the inference made by an association rule does not imply causality.
nevertheless, association rule mining provides a natural setting for ade detection and analysis, and in recent years, has been adopted to various problems in the area of biomedical surveillance.
brossette et al.
and ma et al.
<cit>  applied association rule mining to hospital infection control.
chen et al.
<cit>  applied association rules mining to a linked dataset comprised of a pharmaceutical prescribing dataset and a hospital admissions dataset in order to identify groups of patients who are more likely to have an adverse effect to ace inhibitors.
rouane et al.
applied  <cit>  association rules mining to identify ades related to anti-hiv drugs.
two key issues need to be addressed when applying association rule mining.
first, the search space of interesting multi-item associations is extremely large, and discovering these associations in large databases is computationally expensive, often intractable.
for example, assuming  <dig>  unique drugs and aes are under consideration , then the number of possible multi-item associations made of  <dig> drugs and  <dig> aes that need to be examined is approximately  <dig>  = <dig> , and for each, incidence rates and other association statistics need to be computed.
second, some of the associations discovered may be spurious , or due to confounding factors.
both of these issues have been addressed to a certain extent in this work.
the objective of this paper is twofold.
first, to demonstrate the feasibility and value of association rule mining to identify interesting multi-item ades.
second, to demonstrate that multi-item ades exist in the aers database and can be discovered by our method.
mining the aers database for multi-item associations is to the best of our knowledge a study that has not yet been done for the scale and generality proposed in this paper.
unlike other studies, our approach is general and is not restricted to a particular group of drugs or set of specific conditions, while examining tens of thousands of reports submitted over several years.
the exploration of such a large space of possible multi-item associations was made possible partly due to an optimized and tailored implementation of the apriori  <cit>  algorithm.
we propose the use of association rule mining as an important and promising first step in a multi-step process where subsequent steps include rigorous statistical analysis and clinical/pharmacological expert judgment.
methods
data sources
for the purpose of this study we selected a large sample of reports published in the year  <dig>  representing a sample from the latest complete set of yearly aers reports available.
selecting from the latest available set of reports offers the opportunity to study novel multi-item ades.
in addition we selected reports which were categorized as having a “serious” patient outcome , and reports which contained more than one drug.
the reason for the latter being that we wanted to explore multi-item associations corresponding to possible drug-drug interactions.
mining process
the overall mining process consisted of three steps depicted in figure  <dig>   drug names were mapped to their corresponding generic names to reduce drug naming redundancy and strengthen the signals, as well as reduce algorithmic complexity,  a set of candidate multi-item ade associations were generated using an optimized and tailored implementation of the apriori algorithm,  the set of candidate multi-item ade associations generated in the second step were filtered to remove spurious associations, whereupon the final set of potential multi-item ades were obtained.
our method was implemented in python and required approximately  <dig> hours to complete a full run on a standard desktop with an intel core  <dig> duo processor running at  <dig> ghz.
drug name mapping
one of the main challenges presented to dmas is the granularity and large variation in the terminology used to describe drugs and adverse effects in aers, which in turn may dilute ade signals across multiple similar drugs or events.
unlike the suspected ades and the indications which are coded using meddra, the drugs are entered as free text and include a variety of different formats as well as typographical errors, which must first be mapped into a standardized form.
for example, in aers  <dig>  there were several dozen different variations for the drug avandia, some of which were: avandia, avandia , avandia /sch/ , avandia /unk/ , avandia , avandia /01445801/ , avandia /sch/  , avandia /sch/  , avandia , and rosiglitazone maleate .
each drug obtained from a report was first assigned a umls drug code using medlee <cit> , an existing nlp system.
if the drug name included a dose or route, e.g.
“avandia  tablets”, the more general umls code consisting of only the drug name was chosen over the more specific code, e.g., c <dig>  corresponding to “avandia”.
if the drug name could not be mapped, it was left as is.
finally, umls codes were mapped to generics using rxnorm <cit> .
hence, c <dig> corresponding to the brand name avandia, would be mapped to c <dig> corresponding to the generic name for rosiglitazone.
associations rules mining
the space of possible multi-item associations in a large database, such as the aers database, is generally so large that the number of possible rules to search over is computationally intractable.
therefore, it was necessary to use an efficient algorithm, and also to employ additional criteria specific to the application, in order to reduce the search space.
these additional criteria restrict the search space to rules that not only have high support and confidence but that are of high priority to the application, such as rules containing a certain number or set of items.
in this work we used the general apriori algorithm, which was optimized and tailored to this specific application.
the apriori algorithm is a method designed to efficiently identify association rules in large databases.
the apriori algorithm prunes the search space of associations based on the basic downward closure property of frequency.
in our context this means that if a certain combination of drugs and aes is infrequent, then any larger combination that builds upon the smaller infrequent one, will also be infrequent, and thus need not be considered.
for example, if the combination of drugs aspirin and metformin is in frequent, then any association rule that builds upon it, such as aspirin + metformin→headache, will also be infrequent and therefore does not need to be considered.
the general apriori algorithm works in two steps.
the first step searches for item sets that have more than a given minimum support, while in the second step, rules are generated by selecting “confident” item sets  from those found in the first step.
it is the first step that presents the bottleneck and greater challenge, as it is in this step that all possible rules are enumerated.
in order to deal with the very large set of reports from aers and make the problem tractable we made the following two changes and enhancements to the basic apriori configuration.
<dig>  imposing the constraint that only item sets that had a set of drugs in the antecedent and a set of aes in the consequent were considered as potential association rules in the first step.
otherwise, many of the associations generated by the algorithm would contain either only drugs or only aes, which is not aligned with the definition of an ade association.
by imposing this constraint the search space for possible multi-item ade associations and candidate rules that needed to be considered was significantly reduced.
<dig>  instead of scanning the entire database in order to compute the support of each candidate association rule, hashing  based on drugs/aes was implemented to reduce the number or reports that need to be examined for each rule.
the scale of computational gain achieved by these optimizations was several thousand folds, and without them the method was intractable.
filtering
similar to other studies  <cit> , we have found that the standard criterion of confidence is not indicative of the set of interesting rules.
the inappropriateness of confidence for this case stems from the fact that frequent aes, such as nausea, are likely to generate large confidence values regardless of the drugs associated with it, and infrequent aes are likely to produce small confidence despite being strongly associated with certain drugs.
moreover, unlike typical applications of association rule mining the type of associations sought in ade mining are by definition rare, especially multi-item associations, which would manifest themselves as rules having relatively low support and confidence.
on the other hand, an ade association with high confidence would most likely already be known, e.g., discovered during the clinical trial process.
we therefore chose to use the relative reporting ratio  as a proxy for rule interestingness and association strength instead of confidence.
rr is defined as the ratio between a rule’s observed frequency to a baseline expected frequency under the assumption of independence, the latter servings as a control.
in terms of our existing definitions of support and confidence, rr can formally be defined as,
where n is the total number of reports in the data.
in this setting s  is viewed as the observed frequency of a rule, and ss/n as its expected frequency under the assumption of independence.
it is also easy to see that in this setting rr can be viewed as confidence normalized by the support of a rule’s consequent , correcting the shortcoming of confidence discussed above.
in the context of ade detection, high values of rr indicate that the occurrence of a set of adverse effects in conjunction with a certain set of drugs is larger than occurrence of the adverse effects in the general population of drugs.
under a probabilistic interpretation, rr is an estimate of
therefore, rr can also be viewed as the amount of deviation of the joint probability of the drugs and aes from statistical independence.
large values indicate that the occurrence of the drugs-aes combination has unlikely occurred by chance and that a plausible reason is behind the association.
roughly, rr= <dig> indicates that the drugs and aes are statistically independent, rr> <dig> that the drugs and aes are positively correlated, and rr< <dig> that the drugs and aes are negatively correlated.
although having its limitations, as do other measures, we found rr to be a more informative criterion than confidence for screening interesting ades.
additionally, we found that an adjustment that accounts for low variance, such as the gamma poission shrinker  <cit>  used by the fda, would not be necessary in this case due to a high enough support that we selected.
for large enough support the adjusted and unadjusted rr are almost equal  <cit> .
the support and rr thresholds used in this work to screen ade association rules were set to  <dig> and  <dig> respectively.
in the absence of a gold standard  which would have enabled us to calibrate or determine the most appropriate thresholds in a quantitative manner, we resorted to a data driven and heuristic approach guided by domain expert knowledge.
the support threshold was set to a high enough value to highlight the more frequent patterns and at the same time to accommodate for the size of the database.
the threshold  was found to be a balancing point between the number of associations generated, their size, and variation in content .
setting the threshold to a lower value resulted in a much larger set of associations at a more granular level , with a higher risk of containing spurious ones.
a larger value resulted in less variation in content.
although there is no consensus as to the most appropriate rr threshold  <cit> , the rr threshold used in this work was set to the value of  <dig> based suggestions noted in similar studies  <cit>
evaluation
following common practice in pharmacovigilance <cit>  the clinical validity of the multi-item ade associations identified by the proposed method were reviewed by a clinical subject matter expert.
the findings and conclusions were based on a random evaluation sample of  <dig> multi-item ade associations.
known ades were validated by the expert using micromedex  <cit> , which is considered a reliable reference for medications and their associated ades.
RESULTS
data statistics
the full set of aers reports published in  <dig> contains  <dig>  reports.
our overall data collection process resulted in a sample of  <dig>  individual reports used for analysis, containing  <dig>  unique drug names, and  <dig>  meddra coded unique aes.
the step which mapped drug mentions to generics reduced the set of drug names from  <dig>  to  <dig>  unique umls coded drugs.
each report contained on average  <dig>  different drugs associated with the report and an average of  <dig>  different aes, yielding an average number of  <dig>  items per item set.
the median number of different drugs and different aes per report was  <dig> for each.
it was found that 60% of the reports contained more than one drug, 70% of the reports contained more than one ae, and 84% of the reports contained at least  <dig> items  providing one of the main motivations for this study.
additionally, we found that 27% of the drugs were reported as the primary suspect for the ae, 15% as secondary suspect, 58% as concomitant, and that all reports in our sample were classified as having a “serious” patient outcome.
multi-item ade associations
using the proposed thresholds our method produced a set of  <dig> association rules.
of those,  <dig> were multi-item associations containing item sets of size  <dig> or more, i.e., at least  <dig> drugs or  <dig> aes.
based on the evaluation sample of  <dig> associations, we developed a taxonomy that characterizes the set of multi-item ade associations  that were identified.
the taxonomy along with estimated proportions of each category in the taxonomy is presented in table  <dig>  whereas table  <dig> provides representative examples of potential multi-item ades classified according to the taxonomy, together with the support and rr value for each.
discussion
the taxonomy and examples provided in table  <dig> illustrate several interesting patterns of drugs and adverse effect combinations that can be found in aers.
the associations in examples a, b and c describe drug-drug interactions that are known, drugs that are frequently prescribed together, or associations that seem to be due to confounding respectively.
for example, in association a, metformin and metoprolol are known drug-drug interactions, and because each is associated with nausea, it can be predicted that nausea is more common in patients taking both drugs.
the three drugs identified in association b are used together to treat certain types of cancer and the ade, febrile neutropenia, is a known complication of the treatment.
prednisone is given with the other drugs in association c to treat various medical conditions, such as to induce immunosuppression, but does not cause the reported outcome.
based on historical documentation, this suggests our method has the potential to uncover important ades that have not yet been recognized.
associations d and e describe drugs known to be given together or drug-drug interactions that are known  with events that are clinically unknown .
both drugs in association d are commonly prescribed together in patients with various medical conditions , but the reported event dyspnoea is not expected.
if dyspnoea was a typical manifestation of a disease , then it is likely that the report would not have been submitted to aers.
association e reports the same ade but with a different antecedent.
there are preliminary reports that drugs of the first class  interact with metabolism and thus augment the action of drugs of the second class .
the observed outcome, dyspnea, is not known to be due to either of these two drugs.
if dyspnea were due to congestive heart failure, for which simvastatin might be prescribed, it would be expected and not submitted to the aers database as an adverse drug event.
after sorting the associations by their rr we came across a case that is reflective of data quality issues associated with the aers database.
association f received the highest rr value among all associations found.
the extremely high value  assigned to it raised our suspicion, and its corresponding  <dig> reports  were pulled from the aers database for further inspection.
each of the patients was on  <dig> or more drugs.
yet, despite the very many combinations that would result from a random combination of these drugs, the varenicline-darvocet combination was much more commonly associated than any of the other combinations.
out of  <dig> reports containing both drugs,  <dig> also contained the aes listed.
furthermore, only a small subset of  <dig> aes were associated with these drugs.
six of them are related to mental functioning.
this suggests that the method may have identified a potential drug-drug interaction which augments the effect of either on the brain.
this has face validity: both of these drugs influence the central nervous system so that it is feasible that some of the aes are related to the combination.
the only caveat is that it appears that all patients are nearly identical; all have same diseases, all were taking nearly all of same drugs and reported nearly all of same aes.
this suggests duplicity in reporting of the event/s, a well known issue with aers  <cit> .
a plausible explanation for this duplicity is that different reporters  reported the same patient, possibly from different arms of a clinical trail, or  that follow-up reports for the patient were not properly linked to the patient’s earlier reports.
in any case, such duplicity may severely bias the statistics and lead to erroneous conclusions.
our findings show that the majority of associations  were composed of drugs that are usually given together, such as antibiotics, or drugs that treat the same disease, e.g.
cancer .
the findings also show that the majority of associations  were recognized  multi-item ade associations, where each of the drugs is known to cause each of the reported adverse effect .
this finding demonstrates that multi-item ade associations exist in aers, and that our method was able to reveal them, in turn suggesting that our method is a valid approach for the initial identification of multi-item ades.
we note that a substantial proportion of associations included ades that have not yet been recognized .
however, this does not necessarily indicate that these associations are incorrect, but that currently support for them is scarce and that further investigation is required.
a much smaller proportion of associations  included drugs that are known to interact .
this may or may not be indicative of the true number of drug-drug interactions contained in aers.
the exact number is unknown, but there are studies <cit>  that suggest a larger number .
regardless, drug-drug interactions are a special case of multi-item ades, and our methodology was not designed for this specific case but for the more general case.
nonetheless, we believe that this methodology can be used as a basis for a method designed to identify drug-drug interactions, and we plan to investigate its potential in future work.
the experiment also revealed several limitations and challenges that can be attributed to both the method and quality of data.
based on statistical criteria, the method was able to expose multi-item potential ades that would otherwise go unforeseen by conventional methods, achieving its preliminary goal.
however, without a rather tedious manual review of an expert none of the associations found could be validated or interpreted in the right context.
ideally, a dma should be able reduce the amount of manual expert intervention by perhaps being able to classify the associations detected based on some taxonomy, such the one developed in this study.
this however is still an open problem and beyond the scope of this study.
in future research we intend to develop a dma based on association rule mining supplemented by additional statistical methods that would reduce the amount of intervention and produce associations of higher quality.
one aspect of this problem we are currently exploring is the detection of confounded associations.
there is no gold standard regarding which statistical measures are to be used in order to facilitate accurate ade screening, especially multi-item ades, where little research has been reported.
this problem is exacerbated in srs databases due to unknown incidence rates in the general population.
we believe it is likely that interesting associations went undetected by our method due the specific statistical measures we used.
in future research we plan to explore the applicability, strengths and limitations of various measures to the application of multi-item ade screening.
there are several algorithmic improvements that would enable our method to cope with a larger volume of associations.
for example, lowering the support threshold would have produced a larger and more granular amount of associations, some of which would have likely been classified as interesting potential ades.
at its current state this action would be prohibitive.
due to the mostly voluntary nature of reporting in srs databases dmas are susceptible to biases inherent in the data  <cit> .
common phenomena include under reporting, and over reporting of aes, and reporting duplicity as illustrated by association f in table  <dig>  there were other reports where over  <dig> aes or drugs were included in one report.
all these may generate spurious ade association, and without taking into account data quality issues the results are questionable.
CONCLUSIONS
in a comparative study of dmas applied to pharmacovigilance  <cit>  the authors state: ”if dmas have value, it is because they achieve one or more of the following … detection of aes that would otherwise have gone undetected ”.
the current standard in pharmacovigilance is bivariate association analysis, where each drug-ae combination is studied separately.
in this paper we propose a fundamentally different approach taking into account multi-variate associations.
we examined the feasibility of a well known data mining method that we adopted and tailored to the problem of multi-item ade detection in srs.
we demonstrated its incremental value as part of a larger scheme of operation, which would include additional statistical methods supplemented with domain expert knowledge.
the method was applied in a database-wide-manner to fdas aers with minimal restrictions and no prior expectations on its output, an experiment which to the best of our knowledge has not been done previously.
the findings demonstrate that multi-item ades are present and could be extracted from aers using our methodology.
there are several challenges concerning our approach that should be addressed.
in future research we plan to address some of these issues such as: the statistical measures that should be used to qualify ades, algorithmic improvements, a more automated and streamlined detection process, and incorporating data quality into analysis.
authors' contributions
rh designed the study, collected data, implemented the algorithm, carried out the experiment, performed statistical analysis, and drafted the manuscript.
hc participated in the design of the study, provided clinical domain expertise, validated results, and helped draft the manuscript.
cf conceived of the study, participated in the design and coordination of the study, and helped draft the manuscript.
all authors read and approved the final manuscript.
competing interests
the authors declare that they have no competing interests.

 the main objective of pharmacovigilance is the early detection of novel adverse drug events with minimal patient exposure. the impact of ades results in significant social costs estimated in several billion dollars annually, and inflicts unnecessary, often fatal, harm to patients. hence, their identification is paramount to health care. spontaneous reporting systems are database resources encompassing reports of suspected post-marketed ades, and are currently the mainstay in pharmacovigilance. among the major srss are: the united states food and drug administration’s adverse event reporting system, and the world health organization programme for international drug monitoring. the fda receives voluntary reports of suspected adverse drug events directly from health care professionals and consumers, as well as mandatory reports from manufacturers, which after a manual review are entered into the aers database. each report contains patient demographic information, drug information for as many medications as were reported for the event, including suspected drugs and concomitant drugs, coded adverse events using the meddra terminology, patient outcomes, drug therapy dates, meddra coded indications for the reported drugs, and report sources. the aers database, which is available online, contains over four million reports of adverse events and reflects data from to the present. traditional methods of ade detection in srs databases relied on manual case reviews by clinical/pharmacological experts. however, due to the increasing size and complexity of srs databases, and limitations in human resources, recently, more efficient methods have been proposed consisting of automated, and quantitative approaches that are commonly referred to as data mining algorithms or signal detection algorithms. dmas are generally designed to identify statistically strong associations between drugs and adverse effects. these associations, also referred to as signals, are not necessarily true ades but rather hypotheses that warrant further investigation to qualify them as credible ades. they allow evaluators to peruse the large volume of reports and focus their attention on potentially important safety issues. in recent years a wide range of dmas have been developed to screen potential ades. to estimate incidence rates, dmas use the population of reports in the srs as a proxy for the true population. the majority of dmas rely on the use of disproportionality measures, such as the relative reporting ratio, which attempt to quantify the degree of “unexpectedness” of a drug-ae association. typically, a pre-defined disproportionality threshold will be used to screen potential ades for further review. both the fda and who use an adjusted version of rr as a basis for monitoring safety signals in their srs. typical srs databases contain tens of thousands of drugs and adverse effects. enumerating all possible combinations of ades for statistical analysis, although feasible, is a daunting task and rarely done. as a result, most published work focuses on subsets of the data, e.g., specific drugs or demographic groups, avoiding data base wide studies. additionally, most current dmas are designed to identify only binary associations, i.e., pairs including only one drug and one ae, such as vioxx→ heart attack, excluding from analysis the possibility of multi-item associations, e.g. an association between two drugs and one or two aes, such as aspirin + warfarin → bleeding. multi-item ade associations are rarely reported but are important because they could indicate possible drug-drug interactions. the limitations of bivariate analysis, as well as the importance of and difficulty of multi-item ade detection, also referred to as higher-order ade associations, was emphasized in noting that srs databases provide an opportunity to uncover them as they contain populations that are not well represented in clinical trials. studies that did consider multi-item ade associations, such as drug-drug interactions, did so only after a careful selection of a small subset of drugs. association rule mining is a well established method for discovering interesting relationships between variables hidden in large databases. an association rule is an implication expression of the form a→b, where a and b are disjoint itemsets. in the case of ade detection, a denotes a set of drugs and b a set of aes, e.g. a= aspirin, warfarin, b= bleeding. the strength of an association rule is determined by its support and confidence. the support of an itemset s is the number of records containing a. the support of an association rule s is equal to s, i.e., support determines how often a rule, which in this case is the combination of drugs and aes, is observed in the data. low support may indicate that a rule has simply occurred by chance, and thus support is often one of the parameters used to screen uninteresting rules. the confidence of a rule c is equal to s/s, that is, confidence determines how often items in b appear in records that contain a. confidence provides an estimate of pr the conditional probability of b given a, and therefore is used to measure the reliability or interestingness of the rule. it should be emphasized that the inference made by an association rule does not imply causality. nevertheless, association rule mining provides a natural setting for ade detection and analysis, and in recent years, has been adopted to various problems in the area of biomedical surveillance. brossette et al. and ma et al. applied association rule mining to hospital infection control. chen et al. applied association rules mining to a linked dataset comprised of a pharmaceutical prescribing dataset and a hospital admissions dataset in order to identify groups of patients who are more likely to have an adverse effect to ace inhibitors. rouane et al. applied association rules mining to identify ades related to anti-hiv drugs. two key issues need to be addressed when applying association rule mining. first, the search space of interesting multi-item associations is extremely large, and discovering these associations in large databases is computationally expensive, often intractable. for example, assuming unique drugs and aes are under consideration, then the number of possible multi-item associations made of drugs and aes that need to be examined is approximately =, and for each, incidence rates and other association statistics need to be computed. second, some of the associations discovered may be spurious, or due to confounding factors. both of these issues have been addressed to a certain extent in this work. the objective of this paper is twofold. first, to demonstrate the feasibility and value of association rule mining to identify interesting multi-item ades. second, to demonstrate that multi-item ades exist in the aers database and can be discovered by our method. mining the aers database for multi-item associations is to the best of our knowledge a study that has not yet been done for the scale and generality proposed in this paper. unlike other studies, our approach is general and is not restricted to a particular group of drugs or set of specific conditions, while examining tens of thousands of reports submitted over several years. the exploration of such a large space of possible multi-item associations was made possible partly due to an optimized and tailored implementation of the apriori algorithm. we propose the use of association rule mining as an important and promising first step in a multi-step process where subsequent steps include rigorous statistical analysis and clinical/pharmacological expert judgment. methods data sources for the purpose of this study we selected a large sample of reports published in the year representing a sample from the latest complete set of yearly aers reports available. selecting from the latest available set of reports offers the opportunity to study novel multi-item ades. in addition we selected reports which were categorized as having a “serious” patient outcome, and reports which contained more than one drug. the reason for the latter being that we wanted to explore multi-item associations corresponding to possible drug-drug interactions. mining process the overall mining process consisted of three steps depicted in figure drug names were mapped to their corresponding generic names to reduce drug naming redundancy and strengthen the signals, as well as reduce algorithmic complexity, a set of candidate multi-item ade associations were generated using an optimized and tailored implementation of the apriori algorithm, the set of candidate multi-item ade associations generated in the second step were filtered to remove spurious associations, whereupon the final set of potential multi-item ades were obtained. our method was implemented in python and required approximately hours to complete a full run on a standard desktop with an intel core duo processor running at ghz. drug name mapping one of the main challenges presented to dmas is the granularity and large variation in the terminology used to describe drugs and adverse effects in aers, which in turn may dilute ade signals across multiple similar drugs or events. unlike the suspected ades and the indications which are coded using meddra, the drugs are entered as free text and include a variety of different formats as well as typographical errors, which must first be mapped into a standardized form. for example, in aers there were several dozen different variations for the drug avandia, some of which were: avandia, avandia, avandia /sch/, avandia /unk/, avandia, avandia /01445801/, avandia /sch/, avandia /sch/, avandia, and rosiglitazone maleate. each drug obtained from a report was first assigned a umls drug code using medlee, an existing nlp system. if the drug name included a dose or route, e.g. “avandia tablets”, the more general umls code consisting of only the drug name was chosen over the more specific code, e.g., c corresponding to “avandia”. if the drug name could not be mapped, it was left as is. finally, umls codes were mapped to generics using rxnorm. hence, c corresponding to the brand name avandia, would be mapped to c corresponding to the generic name for rosiglitazone. associations rules mining the space of possible multi-item associations in a large database, such as the aers database, is generally so large that the number of possible rules to search over is computationally intractable. therefore, it was necessary to use an efficient algorithm, and also to employ additional criteria specific to the application, in order to reduce the search space. these additional criteria restrict the search space to rules that not only have high support and confidence but that are of high priority to the application, such as rules containing a certain number or set of items. in this work we used the general apriori algorithm, which was optimized and tailored to this specific application. the apriori algorithm is a method designed to efficiently identify association rules in large databases. the apriori algorithm prunes the search space of associations based on the basic downward closure property of frequency. in our context this means that if a certain combination of drugs and aes is infrequent, then any larger combination that builds upon the smaller infrequent one, will also be infrequent, and thus need not be considered. for example, if the combination of drugs aspirin and metformin is in frequent, then any association rule that builds upon it, such as aspirin + metformin→headache, will also be infrequent and therefore does not need to be considered. the general apriori algorithm works in two steps. the first step searches for item sets that have more than a given minimum support, while in the second step, rules are generated by selecting “confident” item sets from those found in the first step. it is the first step that presents the bottleneck and greater challenge, as it is in this step that all possible rules are enumerated. in order to deal with the very large set of reports from aers and make the problem tractable we made the following two changes and enhancements to the basic apriori configuration. imposing the constraint that only item sets that had a set of drugs in the antecedent and a set of aes in the consequent were considered as potential association rules in the first step. otherwise, many of the associations generated by the algorithm would contain either only drugs or only aes, which is not aligned with the definition of an ade association. by imposing this constraint the search space for possible multi-item ade associations and candidate rules that needed to be considered was significantly reduced. instead of scanning the entire database in order to compute the support of each candidate association rule, hashing based on drugs/aes was implemented to reduce the number or reports that need to be examined for each rule. the scale of computational gain achieved by these optimizations was several thousand folds, and without them the method was intractable. filtering similar to other studies, we have found that the standard criterion of confidence is not indicative of the set of interesting rules. the inappropriateness of confidence for this case stems from the fact that frequent aes, such as nausea, are likely to generate large confidence values regardless of the drugs associated with it, and infrequent aes are likely to produce small confidence despite being strongly associated with certain drugs. moreover, unlike typical applications of association rule mining the type of associations sought in ade mining are by definition rare, especially multi-item associations, which would manifest themselves as rules having relatively low support and confidence. on the other hand, an ade association with high confidence would most likely already be known, e.g., discovered during the clinical trial process. we therefore chose to use the relative reporting ratio as a proxy for rule interestingness and association strength instead of confidence. rr is defined as the ratio between a rule’s observed frequency to a baseline expected frequency under the assumption of independence, the latter servings as a control. in terms of our existing definitions of support and confidence, rr can formally be defined as, where n is the total number of reports in the data. in this setting s is viewed as the observed frequency of a rule, and ss/n as its expected frequency under the assumption of independence. it is also easy to see that in this setting rr can be viewed as confidence normalized by the support of a rule’s consequent, correcting the shortcoming of confidence discussed above. in the context of ade detection, high values of rr indicate that the occurrence of a set of adverse effects in conjunction with a certain set of drugs is larger than occurrence of the adverse effects in the general population of drugs. under a probabilistic interpretation, rr is an estimate of therefore, rr can also be viewed as the amount of deviation of the joint probability of the drugs and aes from statistical independence. large values indicate that the occurrence of the drugs-aes combination has unlikely occurred by chance and that a plausible reason is behind the association. roughly, rr= indicates that the drugs and aes are statistically independent, rr> that the drugs and aes are positively correlated, and rr< that the drugs and aes are negatively correlated. although having its limitations, as do other measures, we found rr to be a more informative criterion than confidence for screening interesting ades. additionally, we found that an adjustment that accounts for low variance, such as the gamma poission shrinker used by the fda, would not be necessary in this case due to a high enough support that we selected. for large enough support the adjusted and unadjusted rr are almost equal. the support and rr thresholds used in this work to screen ade association rules were set to and respectively. in the absence of a gold standard which would have enabled us to calibrate or determine the most appropriate thresholds in a quantitative manner, we resorted to a data driven and heuristic approach guided by domain expert knowledge. the support threshold was set to a high enough value to highlight the more frequent patterns and at the same time to accommodate for the size of the database. the threshold was found to be a balancing point between the number of associations generated, their size, and variation in content. setting the threshold to a lower value resulted in a much larger set of associations at a more granular level, with a higher risk of containing spurious ones. a larger value resulted in less variation in content. although there is no consensus as to the most appropriate rr threshold, the rr threshold used in this work was set to the value of based suggestions noted in similar studies evaluation following common practice in pharmacovigilance the clinical validity of the multi-item ade associations identified by the proposed method were reviewed by a clinical subject matter expert. the findings and conclusions were based on a random evaluation sample of multi-item ade associations. known ades were validated by the expert using micromedex, which is considered a reliable reference for medications and their associated ades.  data statistics the full set of aers reports published in contains reports. our overall data collection process resulted in a sample of individual reports used for analysis, containing unique drug names, and meddra coded unique aes. the step which mapped drug mentions to generics reduced the set of drug names from to unique umls coded drugs. each report contained on average different drugs associated with the report and an average of different aes, yielding an average number of items per item set. the median number of different drugs and different aes per report was for each. it was found that 60% of the reports contained more than one drug, 70% of the reports contained more than one ae, and 84% of the reports contained at least items providing one of the main motivations for this study. additionally, we found that 27% of the drugs were reported as the primary suspect for the ae, 15% as secondary suspect, 58% as concomitant, and that all reports in our sample were classified as having a “serious” patient outcome. multi-item ade associations using the proposed thresholds our method produced a set of association rules. of those, were multi-item associations containing item sets of size or more, i.e., at least drugs or aes. based on the evaluation sample of associations, we developed a taxonomy that characterizes the set of multi-item ade associations that were identified. the taxonomy along with estimated proportions of each category in the taxonomy is presented in table whereas table provides representative examples of potential multi-item ades classified according to the taxonomy, together with the support and rr value for each. discussion the taxonomy and examples provided in table illustrate several interesting patterns of drugs and adverse effect combinations that can be found in aers. the associations in examples a, b and c describe drug-drug interactions that are known, drugs that are frequently prescribed together, or associations that seem to be due to confounding respectively. for example, in association a, metformin and metoprolol are known drug-drug interactions, and because each is associated with nausea, it can be predicted that nausea is more common in patients taking both drugs. the three drugs identified in association b are used together to treat certain types of cancer and the ade, febrile neutropenia, is a known complication of the treatment. prednisone is given with the other drugs in association c to treat various medical conditions, such as to induce immunosuppression, but does not cause the reported outcome. based on historical documentation, this suggests our method has the potential to uncover important ades that have not yet been recognized. associations d and e describe drugs known to be given together or drug-drug interactions that are known with events that are clinically unknown. both drugs in association d are commonly prescribed together in patients with various medical conditions, but the reported event dyspnoea is not expected. if dyspnoea was a typical manifestation of a disease, then it is likely that the report would not have been submitted to aers. association e reports the same ade but with a different antecedent. there are preliminary reports that drugs of the first class interact with metabolism and thus augment the action of drugs of the second class. the observed outcome, dyspnea, is not known to be due to either of these two drugs. if dyspnea were due to congestive heart failure, for which simvastatin might be prescribed, it would be expected and not submitted to the aers database as an adverse drug event. after sorting the associations by their rr we came across a case that is reflective of data quality issues associated with the aers database. association f received the highest rr value among all associations found. the extremely high value assigned to it raised our suspicion, and its corresponding reports were pulled from the aers database for further inspection. each of the patients was on or more drugs. yet, despite the very many combinations that would result from a random combination of these drugs, the varenicline-darvocet combination was much more commonly associated than any of the other combinations. out of reports containing both drugs, also contained the aes listed. furthermore, only a small subset of aes were associated with these drugs. six of them are related to mental functioning. this suggests that the method may have identified a potential drug-drug interaction which augments the effect of either on the brain. this has face validity: both of these drugs influence the central nervous system so that it is feasible that some of the aes are related to the combination. the only caveat is that it appears that all patients are nearly identical; all have same diseases, all were taking nearly all of same drugs and reported nearly all of same aes. this suggests duplicity in reporting of the event/s, a well known issue with aers. a plausible explanation for this duplicity is that different reporters reported the same patient, possibly from different arms of a clinical trail, or that follow-up reports for the patient were not properly linked to the patient’s earlier reports. in any case, such duplicity may severely bias the statistics and lead to erroneous conclusions. our findings show that the majority of associations were composed of drugs that are usually given together, such as antibiotics, or drugs that treat the same disease, e.g. cancer. the findings also show that the majority of associations were recognized multi-item ade associations, where each of the drugs is known to cause each of the reported adverse effect. this finding demonstrates that multi-item ade associations exist in aers, and that our method was able to reveal them, in turn suggesting that our method is a valid approach for the initial identification of multi-item ades. we note that a substantial proportion of associations included ades that have not yet been recognized. however, this does not necessarily indicate that these associations are incorrect, but that currently support for them is scarce and that further investigation is required. a much smaller proportion of associations included drugs that are known to interact. this may or may not be indicative of the true number of drug-drug interactions contained in aers. the exact number is unknown, but there are studies that suggest a larger number. regardless, drug-drug interactions are a special case of multi-item ades, and our methodology was not designed for this specific case but for the more general case. nonetheless, we believe that this methodology can be used as a basis for a method designed to identify drug-drug interactions, and we plan to investigate its potential in future work. the experiment also revealed several limitations and challenges that can be attributed to both the method and quality of data. based on statistical criteria, the method was able to expose multi-item potential ades that would otherwise go unforeseen by conventional methods, achieving its preliminary goal. however, without a rather tedious manual review of an expert none of the associations found could be validated or interpreted in the right context. ideally, a dma should be able reduce the amount of manual expert intervention by perhaps being able to classify the associations detected based on some taxonomy, such the one developed in this study. this however is still an open problem and beyond the scope of this study. in future research we intend to develop a dma based on association rule mining supplemented by additional statistical methods that would reduce the amount of intervention and produce associations of higher quality. one aspect of this problem we are currently exploring is the detection of confounded associations. there is no gold standard regarding which statistical measures are to be used in order to facilitate accurate ade screening, especially multi-item ades, where little research has been reported. this problem is exacerbated in srs databases due to unknown incidence rates in the general population. we believe it is likely that interesting associations went undetected by our method due the specific statistical measures we used. in future research we plan to explore the applicability, strengths and limitations of various measures to the application of multi-item ade screening. there are several algorithmic improvements that would enable our method to cope with a larger volume of associations. for example, lowering the support threshold would have produced a larger and more granular amount of associations, some of which would have likely been classified as interesting potential ades. at its current state this action would be prohibitive. due to the mostly voluntary nature of reporting in srs databases dmas are susceptible to biases inherent in the data. common phenomena include under reporting, and over reporting of aes, and reporting duplicity as illustrated by association f in table there were other reports where over aes or drugs were included in one report. all these may generate spurious ade association, and without taking into account data quality issues the results are questionable.  in a comparative study of dmas applied to pharmacovigilance the authors state: ”if dmas have value, it is because they achieve one or more of the following … detection of aes that would otherwise have gone undetected ”. the current standard in pharmacovigilance is bivariate association analysis, where each drug-ae combination is studied separately. in this paper we propose a fundamentally different approach taking into account multi-variate associations. we examined the feasibility of a well known data mining method that we adopted and tailored to the problem of multi-item ade detection in srs. we demonstrated its incremental value as part of a larger scheme of operation, which would include additional statistical methods supplemented with domain expert knowledge. the method was applied in a database-wide-manner to fdas aers with minimal restrictions and no prior expectations on its output, an experiment which to the best of our knowledge has not been done previously. the findings demonstrate that multi-item ades are present and could be extracted from aers using our methodology. there are several challenges concerning our approach that should be addressed. in future research we plan to address some of these issues such as: the statistical measures that should be used to qualify ades, algorithmic improvements, a more automated and streamlined detection process, and incorporating data quality into analysis. authors' contributions rh designed the study, collected data, implemented the algorithm, carried out the experiment, performed statistical analysis, and drafted the manuscript. hc participated in the design of the study, provided clinical domain expertise, validated results, and helped draft the manuscript. cf conceived of the study, participated in the design and coordination of the study, and helped draft the manuscript. all authors read and approved the final manuscript. competing interests the authors declare that they have no competing interests. 
our findings demonstrate that multi-item ades are present and can be extracted from the fda’s adverse effect reporting system using our methodology, suggesting that our method is a valid approach for the initial identification of multi-item ades. the current standard in pharmacovigilance is bivariate association analysis, where each single drug-adverse effect combination is studied separately. the importance and difficulty in the detection of multi-item ade associations was noted in several prominent pharmacovigilance studies. based on a set of reports of suspected ades reported to aers and published in the year our method identified multi-item ade associations. a significant number of potential multi-item ade associations identified were characterized and clinically validated by a domain expert as previously recognized ade associations. a smaller proportion of associations were characterized and validated as known drug-drug interactions. the method was applied to the fdas spontaneous adverse event reporting system with minimal restrictions and expectations on its output, an experiment that has not been previously done on the scale and generality proposed in this work. in this paper we examine the application of a well established data mining method known as association rule mining, which we tailored to the above problem, and demonstrate its value.
 multi-item adverse drug event associations are associations relating multiple drugs to possibly multiple adverse events. the current standard in pharmacovigilance is bivariate association analysis, where each single drug-adverse effect combination is studied separately. the importance and difficulty in the detection of multi-item ade associations was noted in several prominent pharmacovigilance studies. in this paper we examine the application of a well established data mining method known as association rule mining, which we tailored to the above problem, and demonstrate its value. the method was applied to the fdas spontaneous adverse event reporting system with minimal restrictions and expectations on its output, an experiment that has not been previously done on the scale and generality proposed in this work.  based on a set of reports of suspected ades reported to aers and published in the year our method identified multi-item ade associations. a taxonomy that characterizes the associations was developed based on a representative sample. a significant number of potential multi-item ade associations identified were characterized and clinically validated by a domain expert as previously recognized ade associations. several potentially novel ades were also identified. a smaller proportion of associations were characterized and validated as known drug-drug interactions.  our findings demonstrate that multi-item ades are present and can be extracted from the fda’s adverse effect reporting system using our methodology, suggesting that our method is a valid approach for the initial identification of multi-item ades. the study also revealed several limitations and challenges that can be attributed to both the method and quality of data. 10– march amia summit on translational bioinformatics san francisco, ca, usa 