Generalized Discovery of Tight Space-Time Sequences
Authors: Antonio Castro, Heraldo Borges, Ricardo Campisano, Fabio Porto, Reza Akbarinia, Florent Masseglia, Esther Pacitti, Rafaelli Coutinho ans Eduardo Ogasawara
Abstract: Finding patterns is an important task for different domains. Spatio-temporal patterns brings knowledge about the time and position where a patter is frequent. But not all patterns are frequent over a entire dataset, some can be constrained in spatial positions and time range. Mining tight space-time sequences has as objective to discover frequent sequences, the time range and the set of positions in which these sequences are frequent.
Based on the Apriori algorithm and using concepts of ranged group, greedy-ranged group and solid-ranged group, this paper proposes STSM-2S1T algorithm as a solution to the discovery of frequent sequences that are constrained in one dimension in time and in two dimensions in space. Using a real-world spatio-temporal seismic dataset, STSM-2S1T was compared with a simple approach and extensively evaluated to analyze its sensitivity. As result, STSM-2S1T presented a better performance and low variation in resources usage as input parameters change.
Acknowledgments: The authors would like to thank CAPES, CNPq, and FAPERJ for partially funding this paper.
T401 dataset: The Netherlands seismic spatial-time series dataset, named F3 Block, was produced by the seismic reflection method in a region located in the Dutch sector of the North Sea. The seismic data is obtained by sending high-energy sound waves into the ground or seabed as the case. The amplitude of the reflected sound waves is registered, the later the reflected sound wave arrives deeper in the soil it was reflected.
The dataset is available in: dataset.RData
As a result, this dataset contains observations that are related to the time the sound wave arrives and attributes that are related to the position of the hydrophone which registered the reflected sound wave, a set of time series.
The results presented in this work were focused on public data of the inline 401.
It is composed by 951 spatial-time series with 462 observations.
Patterns previously set by experts: The location of these patterns is of key importance for oil and gas prospects.
The file that contains the positions of the patterns is available in: patterns.RData
An Analysis of Brazilian Flight Delays Based on Frequent Patterns
Authors: Alice Sternberg, Diego Carvalho, Leonardo Murta, Jorge Soares and Eduardo Ogasawara
Federal Center for Technological Education of Rio de Janeiro (CEFET/RJ)
Abstract: In this paper, we applied data indexing techniques combined with association rules to unveil hidden patterns of flight delays. Considering Brazilian flight data and guided by six research questions related to causes, moments, differences, and relationships between airports and airlines, we evaluated and quantified all attributes that may lead to delays, showing not only the main patterns, but also their chances of occurrence in the entire network, in each airport and airline. We observed that Brazilian flight system has difficulties to recover from previous delays and when operating under adverse meteorological conditions, delays occurrences may increase up to 216%.
Acknowledgments: The authors thank CNPq and FAPERJ for partially sponsoring this research.
Arules Package for R: Functions for mining association rules and frequent itemsets. The Apriori algorithm is intended to be used on the generation of association rules for flight delays. Restricting the right-hand side of the rule to a flight delay may show its reasons on the left-hand side. For this purpose, in order to understand domestic delays in Brazil, a data set containing flight and meteorological data was built and evaluated through the association rules generated by Apriori.
- Available at CRAN: https://cran.r-project.org/web/packages/arules/index.html
- Reference manual: https://cran.r-project.org/web/packages/arules/arules.pdf
#Install Apriori package install.packages("arules") #Load Arules package library("arules") data(flightBR) rules_delay <- apriori(flightBR,parameter=list(supp = 0.00077, conf = 0.2276, minlen=2, maxlen= 4, target = "rules"), appearance=list(rhs = c("delay_dep=1"),default="lhs"), control=NULL) #delay_dep=1 means a departure delay or a cancellation
The Arules R-Package enables the generation of association rules using the Apriori algorithm. Restricting the right-hand side of the rule to delays and setting the thresholds for support, confidence and minimum and maximum lengths, we obtain the conditions that may explain the reasons for flight delays on the left-hand side of the rules. For this purpose, we built the flightBR data set after some preprocessing stages, such as integration of multiple sources, cleaning of discrepancies and outliers, selection of the main airports and airlines and transformation, in which we created 12 derived attributes using concept hierarchies, binning, and temporal aggregation. Thus, the flightBR data set contains Brazilian domestic and commercial flights data between January 2009 and February 2015.
flightBR data set: flightBR.RData
Firstly, the apriori function was applied to this dataset considering a support of 0.00077 (approximately equivalent to once per day), a confidence of 0.2276 (the total percentage of delays of the dataset), a minimum length of 2 and maximum length from 2 to 4, generating the following three sets of rules.
Rules of maximum length = 2: rules2.csv
Rules of maximum length = 3: rules3.csv
Rules of maximum length = 4: rules4.csv
Then, the rules were evaluated based on their lifts. The lift is a correlation measure between the conditions on the left-hand side and the consequent on the right-hand side, which in our case is a flight delay. When greater than 1, the chances of experiencing a delay grow with the increase of the lift.
We also generated some specific sets of rules considering some important attributes verified on the first analysis, such as the year of departure, the time of the day and their relationship with airports and the relationship between airlines and airports. For this purpose, support and confidence were very low in order to consider all the situations experienced by the flightBR flights.
Year of departure: year.csv
Time of departure: time_of_day.csv
Time of departure and airport: time_airport.csv
Airline and airport: airline_airport.csv
Finally, we add arrival attributes to the flightBR dataset, creating the flightBR_arr dataset, in order to compare departure and arrival delays. Using very low support and confidence, we investigated when a late departure can be recovered and transformed into a punctual arrival and when a punctual departure leads to a delayed arrival.
flightBR_arr data set: flightBR_arr.RData
Late departures and punctual arrivals: late_dep_punctual_arr.csv
Punctual departures and late arrivals: punctual_dep_late_arr.csv
Flight delay review
Systematic Review Data
Reproducibility
The possibility for the reader to be able to reproduce all the results presented in papers is significant for the scientific method. Initiatives that publishes methods and experimental evaluation using active documents (such as Jupyter notebook) are relevant for support reproducibility. We have provided an example (analytics-example.ipynb) of a reproducible code that enables the comprehension of some data analytics methods presented in the paper.
Appendix
Estimation of COVID-19 under-reporting in Brazilian States through SARI
Estimation of COVID-19 under-reporting in Brazilian States through SARI
Overview
Due to its impact, COVID-19 has been stressing the academy to search for curing, mitigating, or controlling it. However, when it comes to controlling, there are still few studies focused on under-reporting estimates. It is believed that under-reporting is a relevant factor in determining the actual mortality rate and, if not considered, can cause significant misinformation.
Therefore, we condicted a study to estimate the under-reporting of cases and deaths of COVID-19 in Brazilian states using data from the Infogripe on notification of Severe Acute Respiratory Infection (SARI). The methodology is based on the concepts of inertia and the use of event detection techniques to study the time series of hospitalized SARI cases.
The methodology is based on the combination of data analytics (event detection methods) and time series modeling (inertia and novelty concepts) over hospitalized SARI cases. The estimate of real cases of the disease, called novelty, is calculated by comparing the difference in SARI cases in 2020 (after COVID-19) with the total expected cases in recent years (2016 to 2019). The expected cases are derived from a seasonal exponential moving average.
Under-reporting rates of cases of COVID-19 for the states of Brazil
Under-reporting rates of deaths by COVID-19 for the states of Brazil
Data and Code
The code description and Jupyter notebook (implemented in R) complements this work. This material can be found in the repository: Covid19_BR_underreport
In it, it is possible to check the entire process on the calculation of the under-reporting rates and all numerical and graphical results.
Event Detection
Event detection methods include the discovery of anomaly and change points. Anomalies are observations that stand out because they do not appear to have been generated by the same process as the other observations in the time series. Change points characterize a transition between different states in a process that generates the time series data.
There are several methods to address the detection of anomalies and change points. Among them, there are methods that consider the effects of inertia on time series data. As this work is based on inertial concepts, we use two methods of this group.
Change Finder
Change Finder is a technique that detects change points in univariate time series data. Given a time serie, the event detection process consists of two phases. In the first phase, outliers are detected. In the second phase, change points are detected.
For more information see:
Adaptative Normalization
Adaptive Normalization is used to detect anomalies. This technique uses inertia to address heteroscedastic non-stationary series. Given a time series, the outlier removal process consists of three stages: (i) inertia calculation, (ii) noise calculation, and (iii) anomaly identification.
For more information see:
Events detected in the SARI cases (left) and deaths (right) curves in Brazilian States. The yellow dots mark anomalies (Adaptive Normalization), and the red dotted lines mark the change points (Change Finder).
Cases
Deaths
Evolution of the under-reporting rates
In order to create a better characterize the behavior of underrates-report, we analyze them week by week.
The lack of tests for the population results in an increased rate of under-report in the beginning. Over time, tests are expected to occur more, and the rates start to decrease.
As it can be observed, under-report rates tend to stabilize throughout time. This convergence enables more confidence in computed under-report rates.
Conclusions
Data analytics ensures transparency and consistency in the choice of the adopted parameters. In contrast, novelty and inertia enable a comprehensible approach to estimate under-report.
COVID-19 causes a rupture in the SARI series inertial behavior, changing the statistical properties of the time series. Event detection techniques identify this rupture. Assuming that the change occurred is due to COVID-19, the computed novelty then corresponds to estimates of the values of cases and deaths from the disease. From this, under-reporting rates were computed for both cases and deaths.
The rates of under-reporting of cases were estimated for all states except for Mato Grosso do Sul. The values vary between 0.124 (Espírito Santo) and 1.811 (Minas Gerais), thus reaching almost two under-reported cases for each notified case. The novelty observed by our SARI analysis in the states is lower, in their majority, compared to the cases reported by the Ministry of Health. It is expected since many diagnosed cases of COVID-19 are asymptomatic.
Under-reporting rates for deaths were estimated for 25 of the 27 states in Brazil. For the states of Acre and Mato Grosso do Sul, the under-report was not verified and, therefore, death rates were not calculated for these states. Rates vary between 0.072 (Espírito Santo) and 0.983 (the Rio Grande do Sul), thus indicating that there may be more than twice as many deaths as reported. The novelties for deaths cases using SARI analysis in the states are commonly higher when compared to the deaths notified by the Ministry of Health. It helps to corroborate the justification that the death rates are better estimated since SARI covers most of the individuals who die.
No pattern of behavior was observed for the events detected or for the evolution and values of under-reporting rates between states in the same Brazilian region. Therefore, it is observed that the states behave in different and independent ways concerning the occurrence/notification of COVID-19.
The methodology developed in this paper can be adapted to support the under-report rate for other diseases as long as it exists a proxy variable that presents an inertial behavior. Besides, the methodology is also able to support the detection of outbreaks, as it uses both the combination of event detection and inertia concepts.
