Health history pattern extraction from textual medical records

Health History Pattern Extraction from Textual Medical Records Submitted October 2019, in partial fulfillment of the conditions for the award of the degree Master in Innovation and Research in Informatics. Natacha Andrea Quintero Vallejos Supervised by Llu´ıs Padr´o and Jordi Turmo Barcelona School of Informatics (FIB) of Polytechnic University Of Catalonia (UPC) BarcelonaTech Abstract Healthcare systems are using Electronic Medical Records (EMR), promoting the use of long datasets that contain relevant information about the life of a patient. The increasing availability of this longitudinal electronic data, represents an impact on the potential discovery of patterns of new diseases, helping the personalized care and increasing the quality of life. An EMR contains the history of hospital encounters, diagnoses, interventions, lab tests and clinical narratives. Extracting frequent patterns from EMR represents a huge challenge in Data Mining, especially since the addition of the concept of time series. Finding if there is any kind of relationship between a drug and a diagnostic or discovering frequent hidden patterns are relevant important areas of interest in healthcare. In this work, a recursive algorithm called KarmaLego has been implemented for extracting frequent pattern in medical records using data mining techniques. From the modeling point of view, each medical record event is treated as a time point and transformed in an abstract symbol. Each event is connected with another through time relationships using Allen’s temporal relations, “before, overlaps and contains”. Each abstract symbol is linked to an end date and a start date, representing a time interval series in lexicographic order. The algorithm process these sequences to a 2-size relationships with their counting support. Then, this 2-size sequences goes for undermining patterns recursive increasing its size, to finally obtain the patterns that are frequent. i ii Acknowledgements I wish to express my sincere gratitude to Llu´ıs Padr´o and Jordi Turmo, supervisors of this project, for giving me the opportunity and advices to work in the area that I love: Healtcare <3. I also want to say thanks to the professors Masun Homsni (USB) and Oscar Romero (UPC). Besides my professors, I would like to say thanks to my friends, Hector Lop´ez and Iv´an Aveiga for all the emotional support during all the process.I also want to express my gratitude towards my parents, Jos´e Ignacio Quintero and Maria Consuelo Vallejos, but especially to my second father Jorge Navarro Chac´on, who was an important inspiration for me and incredible support during the process. Finally I want to say thanks to several people who are no longer here, but represented an important stage of my life. Thank you! iii iv Contents Abstract i Acknowledgements iii 1 Introduction 2 1.1 Motivation.................................... 2 1.2 Approachproposal ............................... 3 1.3 Objectives.................................... 4 1.3.1 General Objective: . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 Specificobjectives............................ 4 1.4 DocumentStructure:.............................. 4 2 Background 5 2.1 TemporalDataMining............................. 5 2.2 Allen’sintervalalgebra............................. 6 2.3 TemporalAbstraction ............................. 6 2.4 Knowledge Base temporal Abstraction . . . . . . . . . . . . . . . . . . . . 7 2.5 Temporal Discretization ............................ 7 2.6 TimeIntervalMining.............................. 8 2.7 Definitions.................................... 8 3 State of the Art 11 3.1 Association Rule Mining in Transactional Databases . . . . . . . . . . . . . 11 3.1.1 AprioriAlgorithm............................ 12 v vi CONTENTS 3.1.2 Apriori improvements . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Sequential Pattern Matching and Sequence Databases . . . . . . . . . . . . 14 3.2.1 Sequential Pattern Matching algorithms . . . . . . . . . . . . . . . 15 3.2.2 Sequential Pattern Matching and Projected Sequence Databases . 18 3.2.3 Pattern Matching Sequences using Time Data Mining Techniques . 19 4 Data Description 21 4.1 DataSource................................... 21 4.2 DataQuality .................................. 23 4.3 DataExploration................................ 26 5 Approach proposal 30 5.1 Extended Definition Problem . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 Data Temporal Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2.2 Phases of transformation . . . . . . . . . . . . . . . . . . . . . . . . 31 5.3 KarmaLegoAlgorithm ............................. 32 5.3.1 KarmaAlgorithm............................ 33 5.3.2 Karma Algorithm Vertical Support . . . . . . . . . . . . . . . . . . 34 5.3.3 Karma Algorithm Horizontal Support Relaxed . . . . . . . . . . . . 35 5.3.4 LegoAlgorithm............................. 35 5.3.5 Candidate Generation using Transitivity . . . . . . . . . . . . . . . 36 5.3.6 Supporting Count Vertical Support . . . . . . . . . . . . . . . . . . 37 5.3.7 Supporting Count Horizontal Support Fixed . . . . . . . . . . . . . 37 5.3.8 Adding the duration of the Time Interval into the Abstracts Symbols 38 6 Experiments and results 39 6.0.1 Performance of KarmaLego . . . . . . . . . . . . . . . . . . . . . . 39 6.0.2 TIRPs, shape and behavior . . . . . . . . . . . . . . . . . . . . . . 45 7 Evaluation: Selecting temporal patterns for classification 48 7.1 SelectionMethods................................ 48 8 Implementation and tools 55 8.0.1 DataStructures............................. 55 8.0.2 Tools................................... 55 9 Conclusions 57 10 Future Work 60 Bibliography 60 Appendices 65 A A: Data Quality Table 65 B B: Patterns 69 B.0.1 Vertical Support 1000 patients. 0.1 Minimal Support . . . . . . . . 69 B.0.2 Vertical Support 2000 patients. 0.1 Minimal support . . . . . . . . 70 B.0.3 Vertical Support. 3000 patients. 0.1 Minimal Support . . . . . . . . 70 B.0.4 Vertical Support. 1000 patients. 0.3 Minimal Support . . . . . . . . 71 B.0.5 Vertical Support. 2000 patients. 0.2 Minimal support . . . . . . . 71 B.0.6 Vertical Duration Support. 1000 patients. 0.1 min support . . . . . 72 B.0.7 Horizontal Support. 0.1 min support. 2000 patients . . . . . . . . . 73 B.1 Vertical Support. 8000 patients. Minimal support 0.3 . . . . . . . . . . . . 73 B.2 Vertical Support. 10.000 patients. 0.05 min support (only Diagnose) . . . . 74 C C: TIRPS, shapes and behaviours extra charts 75 vii xiv Abbreviations BFS Breadth-First Search. 12, 33 DAG Directed Acyclic Graph. 13–16, 33, 45 DFS Depth-first search. 17, 33 EMR Electronic Medical Records. i, 2, 57 TIRP Time Intervals Relations Pattern. 9, 20, 33, 58 1 Chapter 1 Introduction 1.1 Motivation Data Science is the science of applying techniques and theories with the goal of collecting, managing, and analyzing large and complex datasets, extracting knowledge and answers from them. In recent years, this science has represented the base for development in many areas such as finance, education, cyber security, Healthcare, etc. With the arrival of the big data, where data grow more and more, and at full speed, data mining is facing challenging problems. The data mining principal goal is the extraction of information from data, searching hidden patterns and tendencies to explain unknown behaviors in a specific domain. The pattern matching problem is one of the most interesting challenges of Data mining. This problem is represented as association rules for discovering relationships between variables in large datasets, sets of items, or transaction databases. Another pattern matching problem is related to solving sequential pattern mining, which is associated with finding statistically relevant patterns in items in sequence databases. The approach can become complex adding the time constraint, extending the problem to temporal data mining techniques. Focus in medical records, finding frequent relationships between events that occurs in patients during their life, it is one of the most important problems in Healthcare. Currently Healthcare systems are using EMR, promoting the use of large datasets with 2 1.2. Approach proposal 3 health information. The increasing availability of this longitudinal electronic data represents an impact on the potential discovery of patterns, helping the personalized care of each patient and increasing the life’s quality. An EMR contains the history of hospital encounters, diagnoses, interventions, lab tests and clinical narratives. An interesting part of EMRs is the temporal information. Thanks to this information, new analysis can be done to discover new frequent temporal patterns or treatment pathways, allowing the doctors and experts to gain years in this area. The pattern search problem in medical records is reduced to a pattern matching problem using time data mining techniques in a raw-data with a time-oriented study. In [27] the introduction of the problem for sequential pattern recognition for medical record analysis is explained. The algorithm proposed by Robert Moskovitch and Yuval [25] KarmaLego represents a good approach for solving pattern matching with temporal constraints, including in the processing phase, the addition of the concept of knowledge-based temporal abstraction [23], focus on raw data and time-stamped. 1.2 Approach proposal The work on this thesis is focused on the development of the algorithm KarmaLego with some improvements respective of the structure and design using MIMIC III[14].MIMIC III[14] database has the information of the medical records of the patients who stayed in critical care units of the Beth Israel Deaconess Medical Center between 2001 and 2012.The problem is divide in two phases.The first problem that is encountered as a challenge is the design and modeling of raw-date data. Taking into account that it is data with a high-level of abstractions, the method of Temporal Abstraction through the process of “discretization” is used and the raw-date is transformed into abstract concept with clear meanings. The second problem is the recursive mining process for finding the frequent patterns. Each of these steps will be explained in the next chapters. 4Chapter 1. Introduction 1.3 Objectives 1.3.1 General Objective: Research and develop methods to perform behaviour pattern extraction from electronic health records in the framework of the Graph-MED project. 1.3.2 Specific objectives •Process textual records that were extracted using NLP techniques. •Model the data using a good approach of Data Structure. •Apply Temporal Data Mining •Extract frequent patient behavior to detect new counter-indications, secondary effects, and hidden relationships between the events of a medical records. 1.4 Document Structure: The rest of the thesis is structured as follows. Chapter two discusses the background of the thesis. Chapter three discuss the state of the art, all the previous solutions and their improvements. Chapter four is data description, understand the data used, scope and pre-processing. Chapter five, explains the algorithm and their different approaches. Chapter six contains the experiments and results. Chapter seven describes the evaluation method used. Chapters eight presents the information about the implementation and tools, Chapters nine contains the conclusion and chapter 10 contains some research lines and possible features for further work. Chapter 2 Background 2.1 Temporal Data Mining The goal of data mining is the extraction of information from data, searching hidden patterns and tendencies to explain unknown behaviors in a specific domain. Adding the concept of time to data mining, it comes temporal data mining, a set of time-orient data techniques for discovering temporal knowledge, relationships between raw data. The challenge of this sub-field is the application of different methods with the addition of time to find patterns between sequences and sub-sequences of an event with the representation and modeling of a data sequence. One of the domains, where the challenges and applications of temporal data mining has been growing exponentially has been Healthcare. The data extracted from electronic devices and medical records is represented as temporal sequences and used to study the relationship between events of patient’s life. Actually the concept of time is representing the end of a gap and the beginning of the exploration of new horizons for the science. Not only static data, also, the study of data coming on real-time need to be studied and analyzed for finding abnormal behaviors at big scale. 5 6Chapter 2. Background 2.2 Allen’s interval algebra Allen’s interval algebra is a set of thirteen jointly exhaustive and pairwise disjoint binary relations, based on seven basic temporal relations and their inverses. These relations are temporal relationships between pairs of time intervals. Allen’s [7][2] thirteen relations over temporal intervals explain the base of the study qualitative temporal concepts and representation. The interval relations are meets, before, starts, ends, overlaps, during, their inverses met by, after, started by, ended by, overlapped by, contains, and equality. In Algebra, these relations model the intersection, union and composition between two pair of temporal relations. In the Figure 2.1 are the seven general Allen’s temporal relations. Figure 2.1: Allen’s Temporal Relations 2.3 Temporal Abstraction The concept of temporal abstraction for clinical data analysis represents an important practice of getting qualitative concepts and definition of an abstract concept. Temporal abstraction is the process of giving description as a symbolic definition for a time-point series, making possible to achieve a piece of knowledge and coherent meaning. This definition was studied in [25][23] for applying in medical records raw-data. Focus on the particular problem of medical records as raw data, suppose the study of an element “Hemoglobin in the blood with an X value”, also adding the constraint of “taking a 2.4. Knowledge Base temporal Abstraction 7 blood sample during the last week obtaining the same value X”. This can be explain like for a period of time “one week, the hemoglobin value is high”, “is low”, “is normal”, is “abnormal”, represented as a symbol “high hemoglobin during a week”. 2.4 Knowledge Base temporal Abstraction Knowledge-based Temporal Abstraction (KBTA) is a problem-solving method, based on artificial intelligence techniques, developed by Shahar [23]. This method can be used in a lot of domains, but originally was developed only for the medical domain. This technique works at the point-based raw data. As an example of raw-data timestamp input, let’s say that the element Hemoglobin have as an output, the constitution of a symbol “normal or“abnormal,“high,“low of specific elements, giving a temporal interpretation of the context. [18] [24]. In [24] there is two primary output classes of abstractions generated by the KBTA method: •State Abstraction: the values of one or more variables that hold over the same time point are classified into a symbolic state value (e.g., High) according to the state abstractions cutoff definitions (or, in general, a state-abstraction function). •Gradient Abstraction: the first derivative of each vector of consecutive time point values is classified into the values Increasing (I), when it is sufficiently positive, Decreasing (D) when it is sufficiently negative, and otherwise Stable (S), using a significant-change cutoff value. In the Figure 2.2 there is an example of how time points look like and their representation in Gradient or State. 2.5 Temporal Discretization This refers to the process of “discretization” for the time series-values in an unsupervised method performed in the pre-processing step, transforming the raw data in a symbolic, stated-based time interval. Basically, it is the process of applying the KTBA used by 8Chapter 2. Background Figure 2.2: Gradient, States and Time Points Hoppner in [12]. The important point regarding ”discretization” is the transformation of numeric time-series respecting the order of the values for more meaningful interpretations. 2.6 Time Interval Mining The importance of Time Data Mining and the addition of the concept of time was already explained, also the use of abstract concept applied to raw data for ”discretization” to be able to model the data mining problem. Now the problem is multivariate symbolic time intervals that work with Allens temporal relations. The addition of a symbolic time intervals called AI pattern was proposed by Kam and Fu [15]. AI pattern is finding a problem of an ambiguity taking into account that the temporal relations between the components that were not successive. Hoppner [11] was the first in explain time intervals without ambiguity using a matrix k2to represent all of the pair-wise relations of kintervals. 2.7 Definitions The following definitions were described by Robert Moskovitch and Yuval Shahar. 2.7. Definitions 9 Definition 2.1 Flexible framework of Allen’s temporal relations. Given two relations in time-stamped data and an epsilon value: (1) t1=t2iif |t2−t1|≤ epsilon (2) t1<t2iff t2−t1> epsilon The Epsilon parameter to Allen’s temporal relations maintain the Jointly Exhaustive and Pairwise Disjoint (JEPD) conditions that refers to the probability theory and explain that ”two sets A and B are disjoint if their intersection is the empty set”. This maintains the relation A and B mutually exclusive. Definition 2.2 Symbolic Time interval. A symbolic time interval I=< s, e, sym > is an ordered pair of time points, start-time (s) and end-time (e), and a symbol (sym) that represents one of the domain’s symbolic concepts. Definition 2.3 Symbolic Time Tnterval Series. A symbolic time interval series IS ={I1, I2, In. . . }, where each Iiis a symbolic time interval, represents a series of symbolic time intervals, over each of which holds a symbolic concept. Definition 2.4 Lexicographic symbolic time-interval series A lexicographic symbolic time-interval series is a time-interval series, sorted in the order of the start-time, end-time using the relations <,=and a lexicographic order of the symbols IS ={I1, I2, In. . . }, such that: ∀Ii,Ii∈IS |(i<j)∧((Ii s<Ij s)∨(Ii s=Ij s∧Ii e<Ij e)∨(Ii s=Ij s∧Ii e=Ij e∧Isymi< Isymi)) Definition 2.5 Non-ambiguous lexicographic Time Intervals Relations Pattern (TIRP) A non-ambiguous lexicographic Time Intervals Relations Pattern (TIRP) P is defined as P={I, R}, where I=I1, I2, Ik. . . is a set of k symbolic time intervals ordered lexicographically and defines all the temporal relations among each of the (k2−k)/2 pairs of symbolic time intervals in I. Defined as: R=Tk i=1 Tk j=1+ir(Ii, Ij) = ={r1,2(I1, I2), r1,3(I1, I3). . . r1,k(I1, Ik), r2,3(I2, I3), r2,4(I2, I4). . . r2,k(I1, Ik), rk−1,k(Ik−1, Ik)} Example of a TIRP in the Figure 2.3. 16 Chapter 3. State of the Art Let I={i1, i2...id. . . }be a set of literals, called items. Let Tbe a DAG on the literals. An edge in Trepresents an is-a relationship, and Trepresents a set of taxonomies. If there is an edge in Tfrom pto c, it call pa parent of cand ca child of p. (p represents a generalization of c.). The taxonomy is model as a DAG rather than a tree to allow for multiple taxonomies. Le’ts call xban ancestor of x (and x a descendant of xb) if there is an edge from xbto x in transitive-closure(T). An itemset is a non-empty set of items. A sequence is an ordered list of itemsets. A sequence is denoted as s={s1s2...sn. . . }i, where sjis an itemset. We also call sj an element of the sequence. We denote an element of a sequence by (x1, x2, ..xm), where xjis an item. An item can occur only once in an element of a sequence, but can occur multiple times in different elements. An itemset is considered a sequence with a single element. We assume without loss of generality that items in an element of a sequence are in lexicographic order.A sequence < a1a2...an>is a subsequence of another sequence < b1b2...bm>if there exist integers i1< i2< ... < in such that a1∈bi1, a2∈bi2, ...,an∈bin. The algorithm makes multiple passes over the database. The first pass is to determine if an item is frequent; These items represent the 1-itemset. After this, each subsequent takes one seed, and this seed generates all the new potential frequent sequences, called candidates sequences, that basically are one size bigger than the current sequence. Once the sequence is created, the support count passing through the data again, determining if the new sequence is actually frequent. These new sequences become the seeds for the next pass. It follows the same steps as Apriori, with the difference that the supporting count is now defined for a sequence as the faction of the total data-sequence that actually contains the sequence, adding taxonomies (ancestor concept) and sliding windows (when a datasequence contribute to the support count of a sequence by allowing a set of transactions to count an element of a sequence). Another algorithm called SPAM [3] resolves the sequence pattern matching, also adding time constraints using a bitmap representation. The description of the algorithm assumes a lexicographic ≤of the items in a database, so if an item ioccurs before jin the ordering, 3.2. Sequential Pattern Matching and Sequence Databases 17 then we denote i≤j. This ordering is extensible to sequences. This approach considers all sequences arranged in a sequence tree or as a DAG, where if i comes before j, then i≤j and jis a child of a node i. In Figure 3.2, there is an example of a lexicographic tree. The algorithm works with Depth First Tree Traversal approach to traverse the tree to extend the sequences, where at each node n, the support of each sequence-extended child and each itemset-extended child is tested. If it is above the minimal support, then the sequence is stored, if not, it will stop following the Apriori principle [16]. Depth-first search (DFS) Figure 3.2: Lexicographic Tree 18 Chapter 3. State of the Art 3.2.2 Sequential Pattern Matching and Projected Sequence Databases FreeSpan [9] proposed a novel efficient sequence pattern mining method using a projected sequence database. It follows the same approach as GSP, at the first part of the algorithm, scanning the database to find the length-1 sequential pattern, and sorting in descending order, b:5,c:4, then the complete set of sequential patterns are divided into six subsets. Lets say after the first pass of the database there is something like b:5 c:4 , a:3, d:3, e:3, f:3, so we can do: (1) those having an item f, (2) those having an item e, but not f, (3) those that having item d but no e or f, and so on. FreeSpan uses a divide-conquer method to find the complete sets. Then, they use a matrix to construct the length-2 sequence formed with the list of frequent 1-length before. This matrix is a triangular matrix and is used to generate length-3 and longer sequential patterns. For an itemset, the X-projected dataset is the collection of a sequence having all the items in X. PrefiXSpan [13] made an improvement of FreeSpan creating a pseudo projection technique trying to avoid, at every possible position, a potential candidate. Thinking that the item within an element of a sequence can be listed in any order, it can be assumed that they are always listed alphabetically. So, after doing the first pass of the database and having the 1-length frequent, they find the subsets of the projected databases using a prefix, as in the Figure 3.3. The pseudo projection technique, instead of performing physical projection, registers the index (ID) of the corresponding sequence and the starting position of the projected suffix of the database. With this, the physical projection of the sequence will be replaced by the sequence ID. Another approach it can be found in PSPM [17], this algorithm uses Apriori property to delete the non-frequent items and divide search space and at the second step It records projected position to locate project sequence position for mining local frequent items and mines each one recursively. 3.2. Sequential Pattern Matching and Sequence Databases 19 Figure 3.3: Prefix Span pseudo projected Database 3.2.3 Pattern Matching Sequences using Time Data Mining Techniques There are algorithms like SPADE [29] and UDDAG [6] that resolve the problems of finding pattern sequence, as well as the use of transaction time base constraints, taxonomies, and slide windows. Following the same approach of sequence data mining, some improvement are made using different data structures and techniques to reduce the candidate generation, projection databases, and physical storage. Let’s introduce the new constrains of using time data mining techniques with time in the raw-data. It is important to mention the ingest of new limitations on specific case of study of patterns in medical records. In [27] there is an introduction of the problem for sequential pattern recognition for medical record analysis, and and a good proposal has been made by Robert Moskovitch1 and Yuval [25] with an algorithm called KarmaLego, including in the processing phase the concept of knowledge-based temporal abstraction [23], focus on raw and time-stamped data. 20 Chapter 3. State of the Art This algorithm works with temporal relations between pairs of intervals called TIRP. Papapetrou et al. (2009)[19] proposed a hybrid approach H-DFS, which combines the first indexing pairs of time intervals and then mining the extended TIRPs in a candidate generation. Papapetrou et al. used five temporal relations: meets, matches (equal, in terms of Allens relations), overlaps, contains, and followed and introduced an epsilon threshold, to make the temporal relations more flexible. ARMADA, by Winarko and Roddick (2007)[28] projected works with for mining non-ambiguous temporal patterns from interval-based events. KarmaLego took the idea introduced by Patel et al. (2008) IEMiner - a method inspired by Papapetrous method, which extends the patterns directly, using transitivity. Basically, this algorithm takes the improvement of each of their phases of candidate generation and support counting. Chapter 4 Data Description 4.1 Data Source The data used during the realization of this work were obtained from Physionet and is called of MIMIC-III [14]. MIMIC III is a relational database that initially contains 26 tables. The dataset is health-related data associated with patients who stayed in critical care units of the Beth Israel Deaconess Medical Center between 2001 and 2012. The data were transformed into XML format,and represents a medical record that has a series of events that describe the clinical life of a patient. In total, it contains information about 40,000 patients, but 10,422 patients with cardiovascular problems were selected for the study. The data includes demographic information, vital signs, laboratory measures, microbiology, examinations, results, procedures, medications, hospital entrance and exit, diagnoses, patient mortality information, among other data of a clinical resume. This dataset is rich in information of each of their events in a large population of patients, so its granularity allows to make more accurate studies and obtain much more interesting and relevant results. The general information of a patient is distributed as: •Diagnosis Event: This event represents the information about the diagnosis that has been given to at patient in a certain time (EVENT TIME) and the identification is ICD9 CODE, which is the reference code of a disease. 21 22 Chapter 4. Data Description Figure 4.1: Example of Event Diagnose •Prescription Event: This event has information about a prescription of a drug given to a patient. STARTDATE and ENDDATE represent the beginning of the treatment and the end respectively. It also has information on the name of the drug, generic name, the dose, the type of drug, and the NDC identification of the drug supplied. Figure 4.2: Example of Event Prescription •Procedure Event: This event has information about procedures applied to the patient during their stay in a hospital, the category of the procedure performed and comments on the procedure. Figure 4.3: Example of Event Procedure 4.2. Data Quality 23 •Laboratory Event: This event contains all the information related to laboratory test made for a patient, category of the test, event time, fluid of the body where the test was done (Urine, Blood,etc.), label description, etc. Figure 4.4: Example of Event Laboratory •Microbiology Event: this event represents the microbiology’s test made to a patient. The ORG NAME is the name Specimen, which is tested for bacterial growth. ORG ITEMID,ORG NAME is the organism, if any,that grew when tested. If NULL, no organism grew (i.e. negative culture). INTERPRETATION contains the result of the antibiotic sensitivity, and indicates the results of the test. S is sensitive, R is resistant, I is intermediate, and P is pending. Figure 4.5: Example of Event Microbiology •Admission Event: This event contains information about the entrance of a patient in a hospital. It also has demographic information like ethnicity, marital status, languages, etc.. 4.2 Data Quality The MIMIC dataset initially has 26 tables that were pre-processed with XML during a prestudy phase for the beginning of the thesis. From the XML, only the events that represent 24 Chapter 4. Data Description Figure 4.6: Example of Event Admission I Figure 4.7: Example of Event Admission II relevance for the pattern search were extracted. In order to reduce the complexity of the algorithm and obtain information that is relevant to the study, only six events were used for each medical record. The events mentioned in the data sources section were preprocessed and their features were reduced until finding the elements whose selection were adapted for the approach. During the first phase of the pre-processing phase, the data passed for a first round to reduce complexity. For that reason, the first approach was to count the number of times that a diagnosis appeared in the total of patients. A diagnosis has a unique value called ICD9 CODE. Those diagnoses that appeared less than 20 times were eliminated represeting the 0.7470 % of the total diagnoses. The same approach was applied for the laboratory event using LOINC CODE as a key. A total of 165 LOINC CODE was eliminated from a total of 702, representing 0.2350 % deletion. In the prescribed event, the drugs that appeared less than 20 times (1952 out of a total of 3028), were eliminated, representing a 0.6446 % of the deletion. 4.2. Data Quality 25 The event laboratory has an important point to explain. Extracting the information from the Physionet’s description ”VALUE represents the value measured for the concept identified by the ITEMID. If this value is numeric, then VALUENUM contains the same data in a numeric format. If this data is not numeric, VALUENUM is null. In some cases, VALUENUM contains the score and VALUE contains the score and text describing the meaning of the score. is the unit of measurement for the VALUE, if appropriate. FLAG indicates whether the laboratory value is considered abnormal or not, using pre-defined thresholds ” In the data quality phase, we wanted to check if the pre-defined thresholds were working correctly and check if the FLAG provided a match our flag. The following steps were carried out: Figure 4.8: Data Quality Table Example •Take a sample of 10 % of patients. ˜ 1042 •Extract the differents LOINC CODE presented in the patients. •Create a table with min and max range of values of each LOINC CODE depending the gender. The values were added by standard input. •Check each values and compared with the original one( abnormal or null). The match was 98 % successful, with the sample size, so as a conclusion, the data provided was correct. The 2 % can be related to false negatives for a typo insertion of the values. (The insertion of the values was done manually). 32 Chapter 5. Approach proposal tion. This means that if a time series has the same symbol contiguous, the times are merged into a time interval with the corresponding startdate and enddate. Example: –“Maria went to the hospital for a blood test 02/03/2016 14:00. The leukocytes were abnormal” –“Maria went to the hospital again for a second blood text 03/03/2016 14:00. The leukocytes were abnormal” –“Maria went to the hospital for the third time for a third blood test on 04/03/2016 14:00. The leukocytes were normal” –“Maria went to the hospital for the first time for a fourth blood test an 05/03/2016 14:00. The leukocytes were normal too” In the first two time-series points, the leukocytes were abnormal, so between 03/03/2016 14:00 and 4/03/2016 14:00 the “leukocytes were abnormal” and between 04/03/2016 and 05/03/2016 they were normal. It is assumed that the abstract domain information was done by an expert. Example: Hemoglobin comes with a flag that said is abnormal. Urine comes with a flag that say is yellow. •Once each event of a patient is processed and transformed into a time interval, the time interval series for a patient looks like I=< I1, I2, I3, I4> •The last step is transforming this time interval series into a Lexicographic time interval series, as explained in the background. This part was done using Mergesort, following the definition given in the background chapter with the framework of Allens temporal relation, with epsilon =0, using only the relations of “contains,”, “before,” and “overlaps”. The explanation can be found in Figure 2.1. 5.3 KarmaLego Algorithm The algorithm KarmaLego was proposed for Robert Moskovitch and Yuval Shahar [22] and divide the problem into two phases. In the first phase,are found the most frequent 5.3. KarmaLego Algorithm 33 two-sized items TIRP, or (I1, I2) where each item is a symbolic time interval ordered lexicographic, and which each edge is connected with one of the three Allen temporal relations as before, contains, or overlap. For this step, it performs a BFS. The second phase of the algorithm calls Lego and is a recursive process of encountering the k-TIRPS extending the 2-sized searched in Karma, using a candidate generation with Transitivity approach. This second approach apply a DFS procedure. Algorithm 1 KarmaLego Require: database |P|and all the I={I1, I2, In, . . . }for each p ∈P. Require: ms - minimal support = the minimal support. DAGt =Karma(db,ms) 1: for all t∈DAGt do 2: Lego(DAGt,t,ms) 3: end for 4: return DAGtTIRPS The KarmaLego algorithm 1 receives for each patient P, the intervals series in lexicographic order and the minimal support. So the first step is execute Karma for calculate the 2-sized TIRPS using a BFS approach, and this will return a DAG represented as a Double HashMap. The line 1 is a loop for each TIRP t contain in DAGt, that will be extended with Lego. 5.3.1 Karma Algorithm At the begging of the algorithm 2, when the temporal abstraction is done, the supporting count of each symbols is calculated, and only the symbols that are above the minimal support are taking in account. For that reason, at line 1, these symbols are already calculated. The interesting part is that the cost of calculating this first phase comes along the temporal abstraction phase (lets say the first pass for the database). In lines 3-6, all the patients have their I as interval ordered in lexicographic, then the creation of each TIRP of 2-sized is stored in a HashMap that represents the DAG where the Symbol A goes to the Symbol B, depending of the relationship that they have(before, contains or overlap). This process is done as: 34 Chapter 5. Approach proposal Algorithm 2 Karma Require: database |P|and all the I={I1, I2, In, . . . }for each p ∈P. Require: ms - minimal support = the minimal support. 1: SymbolsP = The symbols above the minimal support. 2: DAGt is empty 3: for all p∈Pdo 4: for all I∈IS, IS ∈p|Ii.syml, Ij.sym and i <j and sym ∈SymbolsP |do 5: r = AllenTemporalRelation(Ii, Ij) 6: HashMap(DAGt,< Ii.symbol, r, Ij.symbol >,pID,i,j) 7: end for 8: end for 9: for all t∈DAGt do 10: if support(t) <ms then 11: Prune(t) 12: end if 13: end for 14: return DAGt R=Tk i=1 Tk j=1+ir(Ii, Ij) = ={r1,2(I1, I2), r1,3(I1, I3). . . r1,k(I1, Ik), r2,3(I2, I3), r2,4(I2, I4). . . r2,k(I1, Ik), rk−1,k(Ik−1, Ik) In the double Hashmap it is stored the symbols as keys and not the time interval. It is important to mention that the ID of the patients and the index of the position of the symbol of the two Intervals are stored. This means that (i, j),it the symbol Ii.sym happens in the position i the symbol of Ij.sym happens in position j. The reason is explained in the supporting count phase (Projected Database) in this chapter. It is important to mention that the search for the existence of a 2-sized TIRP is O (1), thanks to the structure used. Once the DAG is built with the TIRPS of size two, all the relationships between nodes whose support is below that given by the user, are eliminated. For reasons of efficiency it is possible not to eliminate them, just ignore them when executing the second part of the algorithm. Also, the fact of not eliminating them will represent an important part for the future of the design of the algorithm incrementally. 5.3.2 Karma Algorithm Vertical Support Let N≥1 be the number of patients. Let 1 ≤n≤N, and let tbe a TIRP. Then, we define ϕ=n/N as the minimal support. Let us consider the following function: y(t, i) =        1 if the patient ihas never experienced t 0 otherwise 5.3. KarmaLego Algorithm 35 Then, we say a TIRP is frequent when 1 N N X i=1 y(t, i)≥ϕ(5.1) This function explains that a pattern is frequent, if its vertical support must be equal to or greater than the minimum support given. The pattern must appear at least once in a patient, and this must appear in a significant nnumber, formed between n / N as the one given as minimal support. This solution was based on the premise that is important to know how many different patients satisfy the pattern vs. a few patients meeting the same pattern many times (Horizontal Relax support). A vertical support is between 0 and 1. 5.3.3 Karma Algorithm Horizontal Support Relaxed This configuration is done focus in how frequent is a pattern globally. The Horizontal support is a integer. 5.3.4 Lego Algorithm Algorithm 3 Lego Require: DAGt with 2-sized TIRP Require: A TIRP to be extended Require: min support Require: SymbolsP 1: for all s∈SymbolsP do 2: for all r∈Rdo 3: tirpnew =CreateATirp(t.size + 1) 4: AddSymbolToTheEnd(tirpnew, s 5: AddRelationOfNewSymbol(tirpnew, r) 6: Candidate = ∅ 7: Candidate = Generate Candidate Transitivy(tirpnew,1) 8: for all c∈Cdo 9: if SupportingCounts(c, tirpnew)> min support then 10: tirpnew is frequent 11: Lego(DAGt, c, min support) 12: end if 13: end for 14: end for 15: end for The second phase of the algorithm 3 called Lego is basically a recursive algorithm to extend a 36 Chapter 5. Approach proposal TIRP. The extension proposed by Hopner with the H-DFS method using a data structure similar to the HashMap, where the symbols are stored. In this method, candidate generation is created each time, extending the TIRP with the symbols found in SymbolP (the ones that are frequent) with the relations used. In the first step, in line 2-5, all the frequent symbols are generated after the last time interval t using one of the relations in R. An example of this extension can be found in Figure 5.2. The extension phase is conformed for a candidate generation using transitivity and perform a support counting of each TIRPS encountered. 5.3.5 Candidate Generation using Transitivity In line 3 of algorithm Lego, an extended candidate TIRP tirpnew is created based on TIRP t, a symbolic time interval s and a temporal relation r. It is a recursive process that exploits the transitivity property of temporal relations. An input received the extended TIRP with the new r to index at the end. It given only the last relation between the two last symbols, now the relation between the new symbol is added and the rest of the symbols should be calculated using the transition table and the actual disjunction of temporal relations. For example, in Figure 5.2, the TIRP of sized 4 want to be extended to size 5, so the Aˆ 2 is the new symbol to add at the end of the TIRP. It needs to check if there is a relationship between the last symbol of the Interval series (C), and the new TIRP to be added (A2). There are three options, it can be before, contains or overlaps. Using the structured approach developed in the thesis, an optimization is made making possible to know exactly which relationship exist. Before sending this to the Supporting Counting algorithm, the “?” missing information must be “fill”. For this reason, the algorithm generate them using a transitivity table proposed [?]. This part of the algorithm is done recursive, indexing each row of the Candidate. Once all the candidates are generated, the support counting is done. If the support is above that the minimal support, this TIRP is frequent and pass to Lego for extension. In the proposal solution, the number of the size of the TIRP is given by the user, in other case the recursive process can last infinite. It is possible to use brute force and prove all the possible combinations with the tree Allens temporal relations. With brute force, 33different TIRPS are generated; for this reason, we worked using transitivity and reduced the problem to two possible candidates in the example. 5.3. KarmaLego Algorithm 37 Figure 5.2: TIRP size 4 to be extend with A2 5.3.6 Supporting Count Vertical Support To count the frequency of a specific TIRP using the vertical support concept,it is mandatory to store the ID of the patient and the index of the position of the Symbols in pairs in our HashMap(Projected Database). For a TIRP of with K >= 3 be able to be extended, it must check,that each pair of combination exist in HashMap with a vertical support above the minimal given by the user. For example if TIRP A—B is going to be extend with the symbol “C”, it should check the existence of A—B, B—C and A—C, so for this reason the ID of the patient and the position of their appearance of the symbol in their interval series of the corresponding patient is stored. As the Intervals of a patient is lexicographic ordered, knowing the positions of the symbols, it is possible to count their appearance. In this case, it only calculate once per patient, and ignore if the same TIRP appeared more than one in specific patient. This phase is incremental for the rest of the TIRPS. This approach is in the case of interest of the study “How many different patients satisfied the pattern ?”. 5.3.7 Supporting Count Horizontal Support Fixed This approach uses the same Index position of the symbols stored with the ID of the patients. In this case, the frequency per pattern, per patients take part in the final calculation. This means that a pattern occurs three times in a patient, this three times counts for the final calculations of the horizontal support that must be above the minimal support. This gives us information about how frequently is a pattern globally. 38 Chapter 5. Approach proposal Figure 5.3: Different Time Interval of the same TIRP 5.3.8 Adding the duration of the Time Interval into the Abstracts Symbols Adding the duration of the Interval into the abstract symbol as a solution for having instances where the importance of the duration makes sense for a doctor. The problem with this is that some TIRPS that are actually frequent can be lost if their duration are not frequent. An example can be found in the Figure 5.3. Three different instances of the same TIRP definition. For doctors, such as for these quantitatively different instances of the same TIRP might represent quite qualitatively different scenarios. Chapter 6 Experiments and results The experiments performed were divided into two studies. The first study is related to the performance of the algorithm and the second was related to the shape of the TIRPS. The first study consisted in the execution of the algorithm in medium groups of patients (1000,2000,3000) using input variables such as epsilon (The Epsilon parameter to Allen’s temporal relations maintain the Jointly Exhaustive and Pairwise Disjoint (JEPD) conditions that refer to the probability theory and explain that “two sets A and B are disjoint if their intersection is the empty set”. This maintains the relation A and B mutually exclusive.), pattern length (how long the pattern can be), number of patients, minimal support, to obtain information about memory (memory requested for the case), run time and number of patterns (TIPS). Each of these experiments were applied with three configurations: Vertical Support, Vertical Duration Interval Support and Horizontal Support. The first case was using vertical support with different combinations of pattern length, minimal support and number of patients. The second case was using the horizontal support relaxed. The third case was the combination of vertical support with the addition of the duration of the interval in the abstract symbols. 6.0.1 Performance of KarmaLego During the evaluation phase of the algorithm, the epsilon variable was always used as 0. The length of the patterns were tested with 4,5 and 6 with minimal support configurations of 0.1,0.2 and 0.3. For the case of horizontal support (the minimal support is an integer between 0 and infinite), it was tested with 100, 200,300,600 and 900. It was also found that the mean of the length of the time interval series per patients was 543. 39 40 Chapter 6. Experiments and results Let’s call “Vertical” the configuration of vertical support, “Vertical Duration Interval” the configuration where the concept of vertical support was used adding the duration of the interval as an abstract symbol. Finally, “Horizontal” to the configuration of using Horizontal support relaxed. As explained previously, it is possible to choose the pattern length and the algorithm recursively add a symbol using a Depth Breath First (DFS). It is also important to remember that when a pattern is frequent, all instances covered by that pattern as sub-patterns are also frequent too, as part of the mining process. Figure 6.1: TIRPS3 VS Minimal support The graphic in Figure 6.1 shows the comparison using 1000 patients with a minimal support of 0.1, 0.2 and 0.3 respectively. It is important to mention that the Horizontal support received 100 patients as input (it was added here to see the comparison, but this configuration works different than the other ones). The graphic is in logarithmic scale. This figure shows comparison between the number of TIRPS of size 3 generated vs minimal support. The behaviour found was that the lower the minimal support is, more TIRPS are obtained. The vertical support with duration interval was the one that generated more TIRPS with respect to the other two. Comparing vertical support and vertical support duration interval, it was expected that this one would generate more TIRPS, because you can find different patterns with different duration intervals definition, but was not expected that this one generated more than the horizontal one. The comparison between the number of TIRPS of size 3 and number of TIRPS of size 4 VS the 41 number of patients in vertical support and the vertical duration interval, can be found in Figure 6.2 and Figure 6.3 respectively. In both cases while the number of patients grew, the number of TIRPS also grew. This behaviour explains that some patterns can reach the indicated threshold (minimal support) by adding more patients. An interesting event, is that in the case of TIRPS of size 4 (which occurs based on the TIRPS of size 3), at one point the amount of these ones created by vertical support exceeds the ones of interval duration. This scenario, is due to the pruning processes that in the interval duration failed by little. Figure 6.2: TIRPS3 VS Number of Patients The case of horizontal support deserves to be treated separately since the nature of its concept is different. The horizontal support consists in knowing the number of frequent patterns globally (a pattern can occur n times in a patient and this number counts to reach the total threshold). Using a minimal support of 100,200,600,900 in 1000 and 2000 patients, the differences between the number of TIRPS 3 and TIRPS 4, in 1000 and 2000 patients were not much. By the other hand, it showed the expected behaviors that increasing the number of patients, many patterns are reached the minimal. This comparison can be found in Figure 6.4 and in the Figure 6.5. Respect to the vertical support, in the Figure 6.6 there is a comparison between the number of TIRPS of different sizes and the number of patients. As expected as the number of patients increased, the number of TIRPS increased respectively in each case. As long the length of the Chapter 7 Evaluation: Selecting temporal patterns for classification Applying frequent temporal pattern mining can result in a very large number of patterns, and most of them can be not relevant. It is important to develop effective methods to select small subset of patterns and evaluate them. The Pattern selection is a complex task because when a pattern P is frequent, all the sub patterns inside in P are frequent too (as a results of the frequent pattern mining method), having a lot of redundant information. In the chapter on experiments and results, the performance of the algorithm and the shape of TIRPS were studied. In this chapter, a selection and a classification process were executed. 7.1 Selection Methods Determine the sample size is an important process in research. Some scenarios are possible, the first one can be insufficient number of sample elements, giving bad estimation and no significant results. The second one can be a very large sample number that does not provide any type of relevant information. The MIMICIII database initially had information on 40,000 patients, of which 10,000 were selected with cardiovascular problems. In general, a pattern selection phase has high complexity since a pattern that appear many times does not mean that it is a pattern that gives relevant information. In fact, using a minimal support of 0.1, it is possible to find patterns that may be rare or unknown, but relevant, unlike others that may be very frequent and do not provide any information. 48 7.1. Selection Methods 49 For the selection of each of the TIRPS, the following cases were followed: •Two Phased approach: Select the top 2 or one for each case of study . In the case of smaller thresholds, select those that are close to this threshold. This selection processed was used too in [4]. •Non-probabilistic sampling: The selection of the elements of the sample was not made randomly, it was made by the researcher. These samples are less representative than those obtained by probabilistic sampling, but are easy to get. The principal disadvantage is the risk of obtaining too much bias with no possibility to generalize the results. Samples were taken following the mentioned approaches of the different cases submitted for analyzed the quality of the patterns obtained. The results obtained from the selection phase can be found in the appendices B. After the selection phase, the classification phase was done with the researcher and a health staff(two doctors). It is important to mention that the health staff were not experts in cardiovascular domain and were not researchers, so the classification error can be high. A study using the confusion matrix must be done in the future repeating the study with an expert in the domain and a specialize researcher. The classification process was a complex task, but an important one for two different reasons. The first one was the difficulty of knowledge transfer between the researcher and the health staff. The second one was to be able to understand their needs as a potential users. One of the cases that were executed for this study, was to skew the algorithm to study patterns between diagnoses exclusively. The configuration used was vertical support with a minimal support of 0.05 in 1000 patients. In the table 7.1 are the cases obtained. Originally in the abstract symbols, the ICD 10 code of the diagnosis number is stored. The table 7.2 has the same information, but with the diagnosis name translated according to the respective code. EventI RelI EventII RelII EventIII Diagnosis 99592 before Diagnosis 0389 before Diagnosis 51881 Diagnosis 99592 before Diagnosis 78552 before Diagnosis 51881 Diagnosis 4280 before Diagnosis 99592 before Diagnosis 78552 Table 7.1: Example of Diagnosis pattern (ICD 10 code) 50 Chapter 7. Evaluation: Selecting temporal patterns for classification EventI RelI EventII RelII EventIII Severe sepsis before Salmonella infection before Acute respiratry failure Severe sepsis before Septic shock before Acute respiratry failure Congestive heart failure before Acute respiratory failure before Septic shock Table 7.2: Example of Diagnosis pattern Taking this pattern as an example, several questions were asked to the health staff. The first one was regarding the relationship between the events. “Is there any relationship between sepsis and the rest of the diagnosis?” Answer:Sepsis is a generalized infection of the human body. A septic patient has an infection that radiates through the blood, transmitting this to all organs of the body. This produces a multi-organ failure. The heart, lungs and other organs are not exempt from that failure. The bacteria that caused the Sepsis are going to attack the organs causing nephritis, endocarditis and lung problems. It settles, colonizes and multiplies. Sepsis is nothing more than an expression to encompass the entire infected human body. Analyzing the event found, it was classify as known because there is a fairly strong relationship. Sepsis, Salmonella, and another consequences and complications are related as previously expressed. The interesting thing is that in the chapter of data exploration, sepsis appeared as the first cause of death in the population studied( the different was this information was taken from the admission and in this case the diagnosis were extracted from Diagnose event). Given the nature of the algorithm, it is not possible to know the time between each event, only to know its relationship in time. In the table 7.3, there is another example found as a pattern. In this case, a little more complex to understand. Related questions were asked between the use of the drug Iso-Osmotic Dextrose (infections), Heparin Sodium (anticoagulant) and the existence of abnormal Ph. Answer:Ph is normally neutral in humans, around 6.5. In infections it tends to decrease, becoming more acid. Even though there are cases with respiratory conditions that alkalosis occurs instead of acidosis. In the case of urine infections this occurs: Is normally acid, and with the infection of the urine it becomes alkaline. The truth is that in the sepsis or infection independently of the pathogen that causes it, it alters the Ph. Osmocitc medicine is used for bacterial infections. Having an abnormal Ph may be related to having an infection. 7.1. Selection Methods 51 EventI RelI EventII RelII EventIII RelIII EventIV INR(PT) normal before Pantoprazole before Phosphate normal before Heparin Sodium Iso-Osmotic Dextrose before NS:500 ml. before Heparin Sodium before pH abnormal Iso-Osmotic Dextrose before NS:500 ml. before Heparin Sodium before Hematocrite abnormal Pantoprazole before Phosphate normal before Heparin Sodium before INR(PT) normal Table 7.3: Example of a TIRP For each of the selected patterns, the same analysis was made. Five patterns of each case were selected and the following classification results were obtained. In the table 7.4, there is the classification of patterns using vertical support. It was interesting that the in the case of using 1000 patients with a lowest minimal support, a 100 % of known classification was found. This was the case of using only diagnosis events. By the other hand in the case of 3000 patients, the classification was 0 % as known event. Number of patients Threshold Class #1: Not information Class #2: Known 1000 0.1 40 % 60 % 1000 0.3 80 % 20 % 2000 0.1 60 % 40 % 2000 0.2 40% 60% 3000 0.1 100 % 0% 8000 0.3 60 % 40% 10000 0.05 0% 100% Table 7.4: Classification Table of Patterns with Vertical Support Number of patients Threshold Class #1: Not information Class #2: Known 2000 0.1 60 % 40 % Table 7.5: Classification Table of Patterns with Horizontal Support In the table 7.5 are the patterns classified with horizontal support. 40 % was classified as known and 60 % as not provide information. The general appreciation during the review of several patterns was that a large part of the patterns found in this configuration had information on laboratory tests that were mostly normal, so they did not provide information that was relatively interesting. In vertical duration interval support, the sample taken (5) did not provided any 52 Chapter 7. Evaluation: Selecting temporal patterns for classification information.In general, when these patterns were observed, many patterns had 0 in the difference of intervals. This is caused because many time points in the raw data, started and ended at the same moment. In the FIgure 7.6 there is the classification table of patterns using duration vertical support. Number of patients Threshold Class #1: Not information Class #2: Known 1000 0.1 100% 0 % Table 7.6: Classification table of Patterns with Vertical Duration Interval Support For the selection of the patterns in the case of wanting to search for a specific diagnosis, it is possible to make queries in the database where they are stored. In the figure 8.1, there is an example asking for the diagnosis in position two of a TIRP with an specific diagnosis. Figure 7.1: Query Example On the other hand, in case of looking for a more user friendly interface, an approach to an implementation was made using Neo4j to visualize the data. Neo4j is a graph-oriented database, but gave certain limitations during its use, so it was used for a particular case of visualization. Figure 7.2: Lab prescription TIRP in Neo4j 7.1. Selection Methods 53 Figure 7.3: Lab prescription query in Neo4j Figure 7.4: Lab prescription information in Neo4j Figure 7.5: Example of TIRP in Neo4j In Figure 7.2 there is the representation of a relationship between a laboratory event and prescription event. In Figure 7.3 and 7.4 are the query and the information related to the TIRP 54 Chapter 7. Evaluation: Selecting temporal patterns for classification selected. In the Figure 7.5 there is another example of a TIRP. Chapter 8 Implementation and tools 8.0.1 Data Structures The design of a solution is one of the most important aspects to achieve the success in the development of a problem. There must be a balance between some variables as performance, memory cost, CPU cost, results, etc. Depending of the design solution, one variable can be sacrificed respecting to another one. Choosing the correct data structure is an important decision for solving complex problems as working with large datasets. For the solution of the 2-sized TIRPS, a double dimension HashMap was used. HashMap<Symbol,Symbol>=[]. A Hashmap is represented as a dictionary in Python. For creating the TIRPS of k-sized, where k≤3, an object called TIRP was created, having the information of symbols, relations, and frequencies of appearance. 8.0.2 Tools The thesis was developed using the Computer Science department High Performance Computing system (HPC). This is running a queue manager environment that collects all the user requests / jobs and scheduler them prioritizing every user task using several defined criteria (user quota, estimated execution time, RAM, CPU cores). As the thesis was done using private information, all the data were stored in the node of the servers. The code of the algorithm was implemented using Python 2.7. The data were coming from a XML and was transformed in a data frame using Pandas. 55 56 Chapter 8. Implementation and tools Figure 8.1: Final Visualization of the TIRPS This algorithm, even with the optimization, took a lot of time processing, so the code was implemented with parallelism using multiprocessing. Multiprocessing is a package of python that supports spawning processes using an API similar to the threading module. The design consisted in divided the numbers of 2-sized symbols in 10 blocks, so each block was taken for a process. About the Databases used, the first approach was used Ne04j for storing the TIRPS. Neo4j is a free graph-oriented database software, implemented in Java.1 2. It works as a motor of persistence oriented to transactions that stored structure data in Graphs instead of tables. Then, the approach was used Neo4j as a data visualization tool for experimental purpose. The reason of this was that one of the limitations of Neo4j was that only support one database per instance. For this reason, for an experimental purpose, only one instance was used for visualization. The experiments were run using Mysql (Relation Database) to store the information of the TIRPS as sized, pattern, relations, frequencies, etc. Chapter 9 Conclusions Pattern matching problems in medical records is one of the most important problems of the last decades in healthcare. The availability of medical records and the arrival of big data, have allowed to do better studies for analysis, predictions and search for hidden behaviors in data. Thanks to the information contained in EMR, new analysis can be done to discover new frequent temporal patterns or treatment pathways. Temporal pattern matching problems can be solved using temporary data mining techniques, analyzing the data in time intervals. The work in this thesis focused on the implementation of the KarmaLego algorithm with some improvements respectively of the structure and design adapted to our problem. Originally, the proposed algorithm was designed for few entities, but in our cases it was implemented using a large number of different entities and different events in MIMIC III, which increases computational complexity.The first challenge was the processing phase. The raw data arrived in XML format and each event had huge granularity. For this, abstract concepts were created by extracting important information from each event. We had to observe each event to take only the most important characteristics for the creation of each abstract symbol. For the generation of patterns, several configurations were developed and modified to achieve the analysis of our study: Vertical Support, Horizontal Support and Vertical Duration Interval Support. Regarding the performance of the algorithm, in the three configurations was quite slow and consumed a large amount of memory. Of the three configurations, the configuration that had information of the time interval in the abstract symbol Vertical Duration Interval support 57 64 BIBLIOGRAPHY [21] Rao, A. V. V., and Eedala Rambabu, B. Association rule mining using fptree as directed acyclic graph. In IEEE-International Conference On Advances In Engineering, Science And Management (ICAESM -2012) (March 2012), pp. 202–207. [22] Robert Moskovitch, Y. S. Fast detection of time intervals related patterns. [23] Shahar, Y. A framework for knowledge-based temporal abstraction. Artificial Intelligence 90, 1 (1997), 79 – 133. [24] Sheetrit, E., Nissim, N., Klimov, D., Fuchs, L., Elovici, Y., and Shahar, Y. Temporal pattern discovery for accurate sepsis diagnosis in ICU patients. CoRR abs/1709.01720 (2017). [25] Shknevsky, A., Shahar, Y., and Moskovitch, R. Consistent discovery of frequent interval-based temporal patterns in chronic patients data. Journal of Biomedical Informatics 75 (2017), 83 – 95. [26] Srikant, R., and Agrawal, R. Mining sequential patterns: Generalizations and performance improvements. In Advances in Database Technology — EDBT ’96 (Berlin, Heidelberg, 1996), P. Apers, M. Bouzeghoub, and G. Gardarin, Eds., Springer Berlin Heidelberg, pp. 1–17. [27] Tolarczyk, A., and Siwek, K. Sequential pattern recognition for medical records analysis. In 2016 17th International Conference Computational Problems of Electrical Engineering (CPEE) (Sep. 2016), pp. 1–3. [28] Winarko, E., and Roddick, J. F. Armada an algorithm for discovering richer relative temporal association rules from interval-based data. Data Knowledge Engineering 63, 1 (2007), 76 – 90. Data Warehouse and Knowledge Discovery (DAWAK 05). [29] Zaki, M. J. Spade: An efficient algorithm for mining frequent sequences. Machine Learning 42, 1 (Jan 2001), 31–60.