The paper studies the application of sequential pattern mining techniques to medical data from MIMIC-IV, a large healthcare dataset. Sequences of prescribed drugs to a large number of patients are analyzed in order to find out if there are patterns or temporal relationships which are general or specific to a particular disease. The PrefixSpan and Spade algorithms were applied to mine sequential patterns on all sequences or on a subset of them. The extracted patterns could be used to suggest the next prescribed drug. The experimental results show that the predictions obtained have a good accuracy for some diagnoses.
The correct use of a drug is dependent upon several conditions. Each drug has some characteristics,
such as indications, possible risk factors and contraindications, like the use with other drugs or the
existence of certain medical conditions. The improper use of drugs and self-medication can be
dangerous [
The advancement of technology has made it possible to digitally collect and store patient data for
their subsequent use. The manipulation of this large amount of data could bring new knowledge to
the medical field [
Sequential pattern mining can be a solution to this problem because it can identify patterns of
ordered events [
In this paper, we used sequential pattern mining to predict the next medication for a patient. Other
existing studies in the literature are based on machine-learning methods. In [
A similar study to ours is presented in [
mining algorithms, PrefixSpan and SPADE, were considered. Although the predictions are made in a similar way by constructing some rules from the frequent patterns, the analysis of the mining algorithms on the MIMIC-IV dataset and the evaluation of the results on several diagnoses such as "heart attack" are two other elements that distinguish the current paper from the existing works.
The paper is organized as follows. A formal description of the problem of mining sequential patterns and the algorithms used to solve the problem is givenin Section 2. In Section 3 we present the dataset used and in Section 4 the experimental settings and results. We conclude with a summary and future improvements in Section 5.
The problem that sequential pattern mining is trying to solve can be describedas follows: knowing
that many events occur in time, can we learn more about this data if we analyse any ordered sequence
encountered? [
In the following we formally describe the problem. Let = { 1, 2, … , } be a set of elements, also called an alphabet. An event ( 1
, 2, … , ), 1 ≤ ≤ , ∀ ∈ {1, … , } is a nonempty subset of and an unordered collection of elements. A sequence 〈 1, 2, … , 〉 is an ordered collection of events. A sequence that contains k elements is known as a k-sequence. A sequence = 〈 1, 2, … , 〉 is a subsequence of the sequence = 〈 1, 2, … , 〉 if there exist integers 1 ≤ 1 < 2 < ⋯ < ≤ such that 1 ⊆ 1, 2 ⊆ 2, … , ⊆ . A sequence database is a set of sequences that have associated
identifiers. The support of a sequence s, denoted sup(s), in a sequence database represents the number of sequences containing s, i.e., for which s is a subsequence. Giving a value for the minimum support, , a sequence is considered frequentin a database if its support is at least equal to the . Sequential pattern mining aims to find these frequent sequences. denoted 2.1. SPADE
SPADE (Sequential PAttern Discovery using Equivalence classes) [
sequence is also a frequent sequence. SPADE works with data organized in vertical format, by transforming the initial sequence database into a table composed of all events where a row is an event linkedwith the corresponding sequence identifier (SID) and its position in the sequence(EID).
At each step k, the algorithm searches for k-sequences that have the chance to be frequent, by generating id-lists. The first step is to find the 1-frequent sequences. Support is calculated for each element of the alphabet, counting the entries in the vertical formatted table that contains it. Those entries will be included in its id-list. Subsequently, only items that reach the minimum support are frequent and will be considered for finding 2-frequent sequences. In the general case, candidate ksequences are found by joining the id-lists of any two frequent (k-1)-sequences, that have the same SID and have ordered sequential positions (EIDs). The algorithm stops when no more frequent sequences have been found or no more candidate sequences have been constructed.
PrefixSpan (Prefix-Projected Sequential Patterns Mining) [15] is a Pattern-Growth-based algorithm, because it does not generate candidate sequences, but instead uses partitioning of the data set into projections, which will be explored separately to extend the already known frequent sequences.
The PrefixSpan algorithm includes the following steps: 1. Find 1-frequent sequences in the dataset that will later be concatenated to the current frequent sequence (or the current frequent prefix) to form new frequent sequences. Initially, the current frequent sequence is an empty sequence, = 〈_〉 . 2. The search space is partitioned according to the sequences found in the previous step. For each new, frequent sequence obtained, a projection is created, considering that sequence as a prefix. 3. For each projection, look for the elements with support at least equal to which will be used to extend the previous frequent sequences.
These steps are repeated recursively, the algorithm operating on a divide et impera strategy.
MIMIC (Medical Information Mart for Intensive Care) is a relational database, publicly accessible
which documents the hospitalizations of patients at Beth Israel Deaconess Medical Center (BIDMC)
in Boston, MA, USA. MIMIC-IV [
The prescriptions table contains 17008053 records, i.e., drugs that were individually prescribed. In most prescriptions, the drug type was in the MAIN category. Prescriptions were made for 232064 patients, with 452115 hospitalizations. A distribution of the number of drugs per hospitalization is available in Figure 1. In most cases, this number falls in the range [0,400], although there are also much higher values (a maximum of 2156).
There are 5280351 diagnoses in the associated table diagnoses_icd, established for 255106 patients who had 521111 hospitalizations. A patient may have several hospitalizations, and for each hospitalization, several diagnoses. The distribution of the number of diagnoses per hospitalization is given in Figure 2.
The d_icd_ diagnoses table contains 109775 lines, or possible diagnoses. Table 1 shows the ranking of the most common diagnoses.
This section describes the steps followed in generating predictions using Sequential Pattern Mining algorithms on the MIMIC-IV dataset, as shown in Figure 3. The steps are the following: finding the list of distinct drugs, filtering hospitalizations by diagnoses, building sequences of drugs, running sequential pattern algorithms and building rules.
The cases where the predictions are relevant and the parameters that influence their accuracy are analyzed.
The same drug may appear in prescriptions in several forms, such as various abbreviations (‘hepa’, ‘hepar’, ‘hepari’, ‘heparin’), some of the letters are capitalized (‘acetaZOLAMIDE’, ‘Acetazolamide’, ‘AcetaZOLamide’), more or less spaces and special characters (’Dextromethorphan-’, ’Dextromethorphan’), additional words, such as ’pain’, ’bulk’, ’extended release’ (’vancomycin’, ’vancomycin (bulk)’). Another, more complex problem, is that medicines may appear under completely different names, i.e. with the generic name, or with the name used by the brand. A solution to all these inconsistencies is the usage of the gsn field, which contains one or more 6 digit Generic Sequence Number (GSN) codes. GSN identifies a product based on its formula, dose, method of administration and concentration and can be used to group generally equivalent products, which may differ only through the manufacturer. In order to reduce the existence of several equivalent elements, we created a list of drugs with a unique id associated with the help of the GSN codes. Since a drug or other equivalent drugs can be associated with several GSN codes, groups of GSN codes will be established so that one group contains all codes that have been mentioned together directly or indirectly. Two drugs will be considered equivalent if at least one of their GSN codes (not necessarily identical) is found in the same group of GSN codes. Thus, starting from a list of 16970 pairs (drug, gsn), we obtained a list of 3398 drugs with a unique id after preprocessing.
A sequence is an ordered list of events of the form 〈 1, 2, … , 〉 and initially the events are empty subsets of the alphabet I. In our case, the alphabet is the set of drugs ids = {0,1,2, … ,3397}. A sequence corresponds to a hospitalization and is represented by the list of ids of the drugs prescribed, grouped and sorted by time. For example, the sequence 〈(2624), (2624), (2769, 539, 1100)〉 specifies that in the case of a hospitalization, the drug with id 2624 was prescribed first, then again, the same drug, and then followed by a group of three drugs.
We considered two cases for the generation of sequences: the sequences are built for all hospitalizations, or only on a subset of hospitalizations. In the first case, the list of distinct hospitalizations that have at least one prescription can beeasily found by querying the prescriptions table. For each element of the list, the events of the corresponding sequence are considered. Given that there are 452 115 distinct hospitalizations, the number of generated sequences is high, fact which limits the competence of mining algorithms. Consequently, for the second case, we considered filtering the hospitalizations after one or more diagnoses. Given a set of keywords, we will search for hospitalizations that have diagnoses that contain all the keywords. For example, for the words ‘heart’ and ‘pneumonia’, hospitalization with the following diagnoses ‘Pneumonia due to adenovirus’, ‘Aneurysm of heart’, ‘Other and unspecified hyperlipidemia’ will be selected. In addition to this filtering, when constructing sequences, only prescriptions with a drug type equal to MAIN will be considered.
This filtering is meant to facilitate the use of fewer resources (time and memory) by algorithms and to obtain better results, because the selection of hospitalizations by diagnoses can increase the chance of finding more common patterns.
The frequent sequences of prescribed drugs were extracted using two sequential pattern mining algorithms, SPADE and PrefixSpan, available in the open-source Java library SPMF [16]. We run the algorithms on an instance based on Windows 10 Pro that has an Intel(R) Core (TM) i7-8550U CPU @ 1.80GHz processor with8 GiB of memory.
SPADE cannot be applied to the entire dataset due to the additional memory the algorithm requires to transform the sequence database into a verticalformat. SPADE is suitable to be used for a subset of hospitalizations. The results of SPADE are given in Table 2.
We considered six use cases, i.e., hospitalizations that had the following diagnoses: Heart failure, Born in hospital, Acute kidney failure, Need for prophylactic vaccination and inoculation against viral hepatitis, circumcision and Encounter for immunization. We selected the hospitalizations for a diagnosis based on some terms. The chosen terms are contained in or represent the names for the most common diagnoses. We consider diagnoses with _ ≥ 5 because of the higher chance that they will be the main reason for the hospitalization. For example, there are 73 different diagnoses containing the term 'heart failure' and for which this diagnosis is important ( _ ≥ 5). One of the most common diagnoses is Congestive heart failure, unspecified, according to Error! Reference source not found.. The number of resulted sequences is 52086, with an average of 21,04 events. A number of 80983 frequent sequences were found by applying the algorithm on the sequences. The selected values for the minimum support are specified in Table 2. The value of is empirically chosen for practical time limits. A lower number of events means that fewer medications are prescribed for those hospitalizations, which allows the choice of a lower minimum support.
PrefixSpan The parameters of the algorithm are the value of the minimumsupport and, optionally, the maximum length of the sequences.
We tested the algorithm for all hospitalizations, using a minimum supportof 0.025 (10891 sequences) and a maximum length of a sequence of 20. The number of frequently found sequences is equal to 9771. Some of the most frequently used drugs are: lactated ringers (Ringer’s Lactate Solution), hydralazine (Hydralazine), tylenol (Paracetamol), 0.9% sodium chloride, potassium chloride, heparin flush, etc.
A small decrease in the minimum support can significantly increase the number of sequences and thus the execution time. For example, for a minimum support of 0.02 (8713 sequences), the number of frequent sequences increases to 20968.
Next, we repeated the tests made with SPADE, but using the PrefixSpan algorithm instead.
86110 99975 268516 93614 Time (s) 319 29.59 726.23 0.77 1.68 6.4 The results are given in Table 3.
execution time is significantly shorter for SPADE when we have long sequences, and shorter for PrefixSpan in case of short sequences.
We next analyzed the frequent sequences that resulted from the application of the algorithms. We considered two cases: with a high minimum support (for example, hospitalizations with heart failure diagnosis) and with a low minimum support (for example, hospitalizations with Need for prophylactic vaccinationand inoculation against viral hepatitis diagnosis).
Some frequent sequences found for hospitalizations with Need for prophylactic vaccination and inoculation against viral hepatitis diagnosis are given in Table 4.
Sequential patterns ‘erythromycin ophthalmic’ ’erythromycin ophthalmic’ ’phytonadione (vitamin k1)’ → ’erythromycin ophthalmic’ ’hepatitis b vaccine’ ’phytonadione (vitamin k1)’ ’triple dye’ ’erythromycin ophthalmic’ ’hepatitis b immune globulin’ ’phytonadione (vitamin k1)’
’hepatitis b vaccine’ ’phytonadione (vitamin k1)’ → ’gentamicin’ ’phytonadione (vitamin k1)’ → ’acetaminophen’ ’lidocaine’ ’acetaminophen’ → ’hepatitis b vaccine’
’triple dye’ → ’hepatitis b vaccine’ ’triple dye’ ’erythromycin ophthalmic’ ’hepatitis b immune globulin’ ’erythromycin ophthalmic’ ’phytonadione (vitamin k1)’→’phytonadione (vitamink1)’
We analyzed the sequential patterns in order to identify the most commonly used medications. For heart failure diagnoses, the most common drugs among the frequent sequences are: tylenol, senna laxative, aspirin, docusate sodium, dextrose, furosemide, metoprolol tartrate, glucagon, etc. Most of these drugs are also common in all hospitalizations, making difficult to say whether they are specific to these types of hospitalizations or not. Consequently, we manually searched for drugs known to be common for the treatment of heart failure2. We give next some of the results: • from the class Angiotensin-Converting Enzyme (ACE) Inhibitors: lisinopril is often found, being contained in over 400 sequences, captopropyl is found in 6 sequences, with support in the range [10002200] • from the Beta Blockers class: carvedilol appears in over 100 sequences; metoprolol is one of the most frequently found drug • from the class of Vasodilators: hydralazine is found in many different forms, nitroglycerin is found in over 500 sequences • from the class of Diuretics: furosemide is one of the most common drugs, torsemide is found in over 500 sequences, metallozone is found only individually
For patients diagnosed with Need for prophylactic vaccination and inoculation against viral hepatitis, the drugs prescribed are less varied, most of them being hepatitis b immune globulin (bayhep b), hepatitis b vaccine, vitamin k, gentamicin, erythromycin ophthalmic, tylenol, heparin, triple dye. In addition to the vaccine itself (current diagnosis indicates the need for hepatitis vaccination), usual drugs are found, or drugs specific to newborns, because the hepatitis B vaccine is administered to them immediately after birth.
As we previously specified, the frequent sequences can be utilised to identify drugs used for different diagnoses. But when the number of sequencesis huge, this approach becomes less relevant and time expensive. Frequent drug sequences can reveal which drugs or combinations of drugs are more likely to be recommended when we know the previous prescriptions. We will predict the most likely drugs to be prescribed and compare the result with the real valuesto determine the accuracy of the predictions.
Rules construction To describe the links between the drugs from frequent sequences, we will generate rules of form (antecedent, consequent, support) withthe following meanings:
• For a sequence = 〈 1, 2, … , 〉, the antecedent will contain the first (n−1) events 〈 1, 2, … , −1〉, and the consequent will be the last event . Only sequences containing at least two elements are considered. • The support of the rule will correspond to the sequence support.
Some examples of rules generated from frequent sequences for Need for prophylactic vaccination and inoculation against viral hepatitis diagnosis are given in Table 5. {’erythromycin ophthalmic’, ’phytonadione (vitamin k1)’} {’phytonadione (vitamin k1)’} {’phytonadione (vitamin k1)’} {’lidocaine’, ’acetaminophen’}
{’triple dye’} {’erythromycin ophthalmic’, ’phytonadione (vitamin k1)’}
Consequent {’erythromycin ophthalmic’ ’hepatitis b vaccine’ ’phytonadione (vitamin k1)’}
{’gentamicin’} {’acetaminophen’} {’hepatitis b vaccine’} {’hepatitis b vaccine’} {’phytonadione (vitamin k1)’}
Predictions using rules Before making any predictions, the list of rules is sorted using a multilevel approach: first, descending by the number of events from the antecedent and then descending by support. To narrow the search space, we also created athreshold dictionary as follows: for each length of the antecedent that exists in the previously sorted list, store the index of the first corresponding rule. For example, the following threshold dictionary, denoted ℎ ℎ = {8: 0, 7: 97, 6: 1178, 5: 6174, 4: 17020, 3: 29901, 2: 39094, 1: 43006, 0: 43908} reveals that there are eight distinct lengths of the rules’ antecedent. The rules that have an antecedent containing x events, 1 ≤ ≤ 8, will be found in the list starting with position ℎ ℎ [ ] and up to position ℎ ℎ [ − 1] − 1.
Having a patient’s prescribed medication sequence during a hospitalization = 〈 1, 2, … , 〉 and a sorted list of rules, the predictions will be made as follows: 1. If ≥ 1, iterate through the rules with the number of events from the antecedent equal to the number of events in s. The threshold list will be used. 2. For each rule, check if there is a match between the antecedent and the sequence s. If a match is found, the event from the consequent is added to a list. 3. If five matches are found, the search ends. Otherwise, the first event from the sequence s is removed and the previous steps are repeated. Deleting the first item from s means, in fact, that we are trying to test on the patient’s more recent history.
At the end, the list of maximum five events represents the predictions of drugs for the patient with the sequence s as history.
To test the accuracy of the predictions, we used the hospitalizations for whichthe frequent sequences were found and which, implicitly, were used to generate the rules and the dictionary of thresholds. Denote by the maximum value of a key in the threshold dictionary, or the maximum length of an antecedent for the current rules. The sequences of each hospitalization are divided into segments of length . If they are not divided exactly, the last segment willbe considered if its length is at least two. The last event is removedfrom each segment, as it will be used to verify the correctness of the predictions. Predictions are made based on these segments, and if at least one of the drugs contained in the predicted events is found in the event set aside, then we will consider the prediction is correct. Accuracy is computed as the percentage of correct predictions out of the total predictions made.
For the heart failure diagnosis, for example, for 5718 sequences at least one correct prediction was obtained, meaning an accuracy of 25.83%, and for 4704 we could not find any prediction. If we take into account only the sequences on which predictions were found, then the accuracy would be 32.79%.
For certain diagnostics, like Need for prophylactic vaccination and inoculation against viral hepatitis and Circumcision the accuracy is high, while for other diagnoses like Heart failure it is small. Statistically, the number of prescriptions increases with age [17]. Intuitively, a diagnosis that contains the term ‘born in hospital’ refers to newborns, in which case certain standard medicines are required. The number of allowed drugs is lower (many drugs have age restrictions). In this case, it is easier to identify which drugs are more likely to be prescribed. The diagnoses Need for prophylactic vaccination and inoculation against viral hepatitis and Encounter for immunization indicate that a person needs administration of a vaccine. The person is not necessarily ill, so the number of drugs is not expected to be high. Instead, diagnoses that contain ’heart failure’ indicate a serious, complex condition that is often found in the population over the age of 65.
To better clarify the possible reasons that affect the accuracy of predictions, we analysed other measures detailed in Table 7. The second column contains the total number of different drugs encountered in the sequences. The next column contains the average number of drugs per sequence. The last column contains the average difference between the date of the last prescription and the date of the first prescription.
According to Table 7, when there is a wider range of drugs to choose from, theaccuracy tends to decrease. The average number of drugs per sequence influences the sequential pattern mining algorithms: it is necessary to usually choose a larger support, so as not to use too much memory, fact which also influences theaccuracy. Another parameter that could influence the results is the length of the period in which prescriptions were made. This may indicate complex diagnoses or, conversely, less severe cases.
The choice of the minimum support can influence the accuracy of the predictions, and indirectly the runtime and the memory. Table 8 exemplifies theway the support influences the accuracy. The last column is the time needed to compute the predictions.
As the minimum support decreases, the accuracy increases slightly, and the runtime also increases. Lowering the support is useful up to a certain limit, for which a reasonable execution time is obtained
Sequential Pattern Mining represents an effective technique to make predictions of medications based on the patient’s past prescription history. This paper studies in particular the application of two algorithms, SPADE and PrefixSpan, as a means to find frequent sequences that reveal temporal relationships between medications. The resulting frequent sequences are general or specific to one or more diseases and are used to construct rules. Predictions are made by finding matches of a patient’s medication history in the list of rules. According to the experimental results, there are situations in which the predictions made can reach a satisfactory accuracy. Such a solution is especially useful for routine cases, for instance, immunizations, or for the treatment of newborns. Instead, for more complex diagnoses, additional study is needed to optimize the results.
Some improvements that can be made are the addition and the usage of supplementary patient information, such as laboratory results, age and supplementary medication details, like the dose, the method of administration.
[15] Pei, J., Han, J., Mortazavi-Asl, B., Wang, J., Pinto, H., Chen, Q., & Hsu, M.C. Mining sequential patterns by pattern-growth: The prefixspan approach. IEEE Transactions on knowledge and data engineering, 16(11), 1424-1440 (2004). doi: 10.1109/TKDE.2004.77 [16] Fournier-Viger, P., Lin, J. C. W., Gomariz, A., Gueniche, T., Soltani, A., Deng,Z., & Lam, H. T. The SPMF open-source data mining library version 2. In Joint European conference on machine learning and knowledge discovery in databases (pp. 36-40) (2016). [17] Martin, C. B., Hales, C. M., Gu, Q., & Ogden, C. L. Prescription drug use in the United States, 2015– 2016, (2019): 1-8.