ACO Ant Colony Optimization CPU Central Processing Unit CRUD Create Read Update Delete FuzzTX Fuzzy Temporal Crossing GP Gradual Pattern GRAANK GRAdual rANKing GRITE GRadual ITemset Extraction IoT Internet of Things JSON JavaScript Object Notation MQTT MQ Telemetry Transport O&M Obervations and Measurements OASIS Organization for Advancement of Structured Information Standards ISO International Organization for Standardization

Résumé

La recherche de motifs fréquents permet d'extraire les corrélations d'attributs par le biais de règles graduelles comme: "plus il y a de X, plus il y a de Y". Ces corrélations sont utiles pour identifier et isoler des relations entre les attributs qui peuvent ne pas être évidentes grâce à des analyses rapides des données. Par exemple, un chercheur peut appliquer une telle recherche pour déterminer quels attributs d'un ensemble de données présentent des corrélations inconnues afin de les isoler pour une exploration plus approfondie ou une analyse. Supposons que le chercheur dispose d'un ensemble de données qui possède les attributs suivants : âge, montant du salaire, du nombre d'enfants et du niveau d'éducation. Un motif graduel extrait peut prendre la forme "plus le niveau d'éducation est bas, plus le salaire est élevé". Étant donné que cette relation est rare, il peut être intéressant pour le chercheur de mettre davantage l'accent sur ce phénomène afin de comprendre. Dans ce travail, nous proposons une technique d'optimisation par des colonies de fourmis qui utilise une approche probabiliste imitant le comportement des fourmis biologiques en cherchant le chemin le plus court pour trouver de la nourriture afin de résoudre des problèmes combinatoires. Nous appliquons la technique d'optimisation des colonies de fourmis afin de générer des candidats des motifs graduels dont la probabilité d'être valide est élevée. Ceci, couplé avec la propriété anti-monotonie, se traduit par le développement d'une méthode efficace. Dans notre deuxième contribution, nous étendons l'extraction de modèles graduels existante à l'extraction de motifs graduels avec un décalage temporel approximatif entre ses attributs affectés. Un tel modèle est appelé motif graduel temporel flou. Cela peut prendre par exemple la forme: "plus il y a de X, plus il y a de Y presque 3 mois plus tard" Ces modèles ne peuvent être extraits que de séries de données chronologiques car ils impliquent la présence de l'aspect temporel. Dans notre troisième contribution, nous proposons une donnée modèle de croisement qui permet l'intégration d'implémentations d'algorithmes d'exploration de modèle graduel dans une plateforme Cloud. Cette contribution est motivée par la prolifération des applications IoT dans presque tous les domaines de notre société, ce qui s'accompagne de la fourniture de données chronologiques à grande échelle de différentes sources. Il peut être intéressant pour un chercheur de croiser différentes données de séries chronologiques dans le but d'extraire des motifs graduels temporels des attributs cartographiés. Par exemple un ensemble de données 'humidité' peut être temporairement croisé avec un ensemble de données indépendant qui enregistre 'Population de mouches', et un schéma peut prendre la forme: "plus l'humidité est élevée, plus vole presque 2 heures plus tard". Notre méthode met l'accent sur l'intégration de l'exploitation des techniques les plus récentes de plate-formes Cloud, car cela facilite l'accès à nos méthodes en allégeant l'installation et la configuration pour les utilisateurs, permettant ainsi aux utilisateurs de passer plus de temps à se concentrer sur les phénomènes qu'ils analysent.

Abstract

Gradual pattern mining allows for extraction of attribute correlations through gradual rules such as: "the more X, the more Y". Such correlations are useful in identifying and isolating relationships among the attributes that may not be obvious through quick scans on a data set. For instance a researcher may apply gradual pattern mining to determine which attributes of a data set exhibit unfamiliar correlations in order to isolate them for deeper exploration or analysis. Assume the researcher has a data set which has the following attributes: age, amount of salary, number of children, and education level. An extracted gradual pattern may take the form "the lower the education level, the higher the salary". Since this relationship is uncommon, it may interest the researcher in putting more focus on this phenomenon in order to understand it. As for many gradual pattern mining approaches, there is a key challenge to deal with huge data sets because of the problem of combinatorial explosion. This problem is majorly caused by the process employed for generating candidate gradual item sets. One way to improve the process of generating candidate gradual item sets involves optimizing this process using a heuristic approach. In this work, we propose an ant colony optimization technique which uses a popular probabilistic approach that mimics the behavior biological ants as they search for the shortest path to find food in order to solve combinatorial problems. We apply the ant colony optimization technique in order to generate gradual item set candidates whose probability of being valid is high. This coupled with the anti-monotonicity property, results in the development of a highly efficient ant-based gradual pattern mining technique. In our second contribution, we extend an existing gradual pattern mining technique to allow for extraction of gradual patterns together with an approximated temporal lag between the affected gradual item sets. Such a pattern is referred to as a fuzzy-temporal gradual pattern and it may take the form: "the more X, the more Y, almost 3 months later". The addition of temporal dimension into the proposed approach makes it even worse regarding combinatorial explosion due to added task of searching for the most relevant time gap. In our third contribution, we propose a data crossing model that allows for integration of mostly gradual pattern mining algorithm implementations into a Cloud platform. This contribution is motivated by the proliferation of IoT applications in almost every area of our society and this comes with provision of large-scale time-series data from different sources. It may be interesting for a researcher to cross different time-series data with the aim of extracting temporal gradual patterns from the mapped attributes. For instance a 'humidity' data set may be temporally crossed with an unrelated data set that records the 'population of flies', and a pattern may take the form: "the higher the humidity, the higher the number of flies, almost 2 hours later". Again, the study emphasizes integration of gradual pattern mining techniques into a Cloud platform because this will facilitate their access on a subscription basis. This alleviates installation and configuration hustles for the users; therefore, it allows them to spend more time focusing on the phenomena they are studying. 2.12 The 8 sensing entities that make OGC SensorThings framework [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF]

List of Figures

"If I have seen further it is by standing on the shoulders of Giants"

-Sir Isaac Newton (1642 -1727)

Introduction

"Data mining is a nontrivial process of extracting knowledge from data sets" [START_REF] Cios | Trends in Data Mining and Knowledge Discovery[END_REF]. Experts employ data mining techniques to pull out hidden information from large-scale data sets, which may otherwise take human analysts very long to find. Gradual pattern discovery is a recent extension of the data mining field that allows linguistic expressions of attribute correlations in the form of gradual rules such as "the more X, the less Y", as illustrated in Figure 1.1 [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF], Di-Jorio et al., 2009, Laurent et al., 2009, Aryadinata et al., 2013, Aryadinata et al., 2014]. We live in the 21st century where research is characterized by analysis of large-scale data. A great deal of research activities involve correlating different aspects of a data set in order to understand the relationships existing in the observed phenomena. Given such large-scale data, the exploring of every attribute combination for possible correlation proves to be time consuming. However, gradual patterns render the possibility of isolating correlating attributes within a short time [START_REF] Aryadinata | Mining Epidemiological Dengue Fever Data from Brazil: A Gradual Pattern Based Geographical Information System[END_REF].

With that in mind, gradual pattern mining offers many benefits to businesses, companies and other service-oriented domains. For instance in a medical domain, a medical practitioner may carry out tens of tests which may generate data with hundreds of attributes. From this data useful knowledge may be extracted through a gradual rule like: "the lower the population of organism X, the higher the population of organism Y". If this correlation is uncommon, then the practitioner can isolate the two organisms from hundreds of attributes for a deeper analysis. Of course, the need to constantly analyze the performance of existing gradual pattern mining techniques with the aim of improving them should never be abandoned. Researchers in the data mining field should embrace this challenge in order to keep this field active.

Unlike classical mining techniques (such as associative mining) that calculate the frequency of an item set occurrence in a data set, gradual pattern mining calculate the frequency at which gradual attribute correlations occur in a data set. For example in Table 1.1, at all 4 tuples the values of X and Y are both increasing in a subsequent manner. Therefore, a gradual rule may take the form: "the more X, the more Y" [Agrawal andSrikant, 1994, Di-Jorio et al., 2009]. Time X Y 13:00 1 10 13:30 2 20 14:00 3 30 14:30 4 40 Table 1.1: A sample timestamped data set There has been a great deal works for the last 10 years regarding gradual pattern mining. Many of these works do not consider any approach that allows for estimation of the temporal lag among the attributes' correlations. For instance given Table 1.1, classic gradual pattern techniques would extract the pattern "the more X, the more Y" and they would not exploit values of Time attribute for additional knowledge discovery. It may be possible that a temporal lag may exist between an attribute's change and the impact of that change on another attribute's change. Such a pattern that additionally captures the temporal tendencies between gradual item sets is referred to as a temporal gradual pattern.

With respect to Table 1.1, a temporal gradual pattern may take the form: "the more X, the more Y, 30 minutes later". Further, temporal gradual pattern mining may be extended to allow for extraction of emerging temporal gradual patterns. A temporal gradual pattern may be said to be emerging if its frequency of occurrence varies from one data set to another [START_REF] Laurent | Mining emerging gradual patterns[END_REF]. For the reason that any temporal gradual pattern rely on the temporalorientation of the data set, their discovery is only possible in time-series data sets. Time-series data can be defined as a sequence of data points that are temporally-oriented. Sources of time-series data are numerous; for instance it may be obtained from from internal sources (e.g. a data warehouse collecting IoT sensor data) or from an external source (e.g. data distributed by government institutions such as weather stations) et cetera. Time-series data can also be defined as a data stream when it becomes a potentially infinite sequence of precise data points recorded over a period of time [START_REF] Pitarch | Summarizing multidimensional data streams: A hierarchy-graph-based approach[END_REF].

Today, IoT applications have spread to almost every domain of our society and these applications come with the provision for large-scale time-series data and data streams. Therefore, by adding temporal information to gradual correlations, temporal gradual pattern mining may greatly aid researchers who are interested in identifying the temporal aspects of attribute relationships.

It is also important to mention that due to the increased provision of IoT -related time-series data, frameworks and standards such as the (Open Geospatial Consortium) OGC SensorThings have emerged to facilitate easy management and sharing of such data among different research institutions [START_REF] Hajj-Hassan | Exploiting interand intra-base crossing with multi-mappings: Application to environmental data[END_REF], Liang et al., 2016]. These standards aim to integrate sensor data into Spatial Data Infrastructures (SDI) so that they become additional sources of geospatial information besides traditional data types like maps.

SDIs are used to implement frameworks that allow geospatial data to be FAIR (Findable, Accessible, Interoperable and, Reusable). As a result, time-series data offer great potential for integrating real-time observations into geospatial data for richer map visualization. It is now possible for research scientists to remotely monitor environmental sensors, collect and map their readings to specific geographical areas [START_REF] Hajj-Hassan | Integrating sensor data using sensor observation service: Towards a methodology for the o-life observatory[END_REF], Kotsev et al., 2018, Ronzhin et al., 2019]. With this current trend, the need arises to integrate gradual pattern mining algorithms into Cloud platforms that implement such frameworks. In the research community, great interest has also been expressed regarding crossing timeseries data from different sources in order to discover new knowledge about phenomena that otherwise could not be discovered by analyzing the individual data sets in isolation. Data crossing enables the matching of different data sets using a predefined criteria and combining their data points to form a new data set [START_REF] Da Costa | Use of data warehouse to manage data from wireless sensors networks that monitor pollinators[END_REF][START_REF] Hajj-Hassan | Integrating sensor data using sensor observation service: Towards a methodology for the o-life observatory[END_REF], Hajj-Hassan et al., 2016]. For example, let us assume that both data sets shown in Figure 1.2 contain data points recorded at simultaneous times. It is easy to see that a new data set may be formed by matching data points that occur at almost similar timestamps as illustrated in Table 1 Even further, Figure 1.3 illustrates how the 'room temperature' time-series data set and the 'dozing students' time-series data set may be crossed to form a new data set which is mined to extract temporal gradual patterns such as: "the higher the room temperature, the higher the number of dozing students, 15 minutes later". This is an abstract example, but it goes to show that data crossing and gradual pattern mining techniques can be combined to develop a powerful automated data analysis tool.

Problem Statement

In the previous section, we mentioned that gradual pattern mining technique is a recent extension in the data mining field and its popularity as a research item has been on the rise since the early 2000s. It is important to highlight that many works on gradual pattern mining approaches employ two main strategies for mining gradual rules: (1) depth-first search (DFS) which builds the longest set enumeration tree of gradual candidates and, (2) breath-first search (BFS) which generates gradual item set candidates in a level-wise manner. Nonetheless, DFS-based approaches employ recursion (which is computationally complex) to find the longest set enumeration tree and, BFSbased algorithms suffer from the problem of combinatorial candidate explosion when presented with huge data sets.

However, the anti-monotonicity property (which holds for gradual item sets) is employed as an efficient pruning strategy in gradual pattern mining. The anti-monotonicity property states that: "if a pattern containing k item-sets is not frequent then all supersets of the pattern are also not frequent" [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF], Di-Jorio et al., 2009, Laurent et al., 2009]. The anti-monotonicity property allows many gradual pattern mining techniques to automatically eliminate gradual item set candidates that are supersets of infrequent item sets or subsets of frequent item sets. In this way, the efficiency of the process of validating candidate gradual item sets is improved.

In reality, the anti-monotonicity property partially solves the problem of combinatorial candidate number explosion that may occur when dealing with large-scale data sets having great numbers of attributes. It should be remembered that for n attributes, there exists 2 n combinations of gradual item set candidates to consider. For instance, assume {A, B} are attributes of a data set. The following candidates are possible: {moreA, lessB}, {lessA, moreB}, {lessA, lessB}, and {moreA, moreB}. Therefore, as the number of attributes increase, the number of gradual item set candidates to consider also increase exponentially.

We have also discussed in the previous section how the increasing popularity of IoT applications in this century has led to more provision of time-series data. In light of this fact, the need arises to extend gradual pattern mining techniques so that they allow extraction of gradual correlations among the attributes of a time-series data set together with an estimated temporal lag. Such patterns may take the form: "the more Y, the less Z 2 years later". Many works have been accomplished regarding gradual pattern mining techniques; however, these works do not take into account the possibility of estimating the temporal lag between gradual item sets.

In addition, it may be interesting to cross time-series data from unrelated sources in order to discover any uncommon relationships. There exists numerous techniques for crossing time-series data from different sources and the most popular techniques rely on a SQL-based querying models to achieve this [START_REF] Wang | Query Processing in Wireless Sensor Networks[END_REF], Boukerche et al., 2016, Małysiak-Mrozek et al., 2018a]. However, many certified frameworks for managing time-series data (such as OGC SensorThings framework for managing sensor data) are implemented on APIs that support NoSQL querying models.

To shed more light, most research institutions across the world (especially Europe) comply with directives given by a common governing body such as INSPIRE (Infrastructure for Spatial Information in the European Community) [START_REF] Grellet | Workshop: Integration of O&M data in the INSPIRE SDI -Benefits, challenges and prospects[END_REF]. One of the most common directive involves encouraging member institutions to use a common certified framework such as OGC SensorThings to manage sensor data [van de Crommert et al., 2004, Kotsev et al., 2018].

It is important to emphasize the adoption of Cloud platforms that implement certified data managing frameworks since consumers of these data (mostly researchers) obviously wish to spend more time studying phenomena than configuring data mining (or analysis) tools. In that case, integrating gradual patterns mining techniques into a Cloud platform such as Docker allows researchers to access them on a subscription basis.

Contributions

With the intention of grappling with the problems discussed in the previous section, the objective of this research study is to address three main gradual pattern mining aspects and they are briefly described as follows.

Mining Temporal Gradual Patterns

With regards to exploiting the timestamped attributes in order to estimate temporal lag between extracted gradual item sets, this thesis introduces a fuzzy model for estimating time lag as an additional procedure of gradual pattern mining. The process involves transforming a data set through its tuples stepwisely, and applying a fuzzy triangular membership function to estimate time lag. So, a (fuzzy) temporal gradual pattern may take the form "the more Y, the less Z, almost 2 years later".

Moreover, this thesis extends (fuzzy) temporal gradual patterns in order to introduce emerging temporal gradual patterns. Emerging patterns (EPs) are item sets whose frequency changes significantly from one data set to another. EPs are described using growth rate, which is the ratio of an EP's frequency support in one data set to its frequency support in another data set [Dong and Li, 1999]. Therefore, a temporal gradual emerging pattern my take the form: "the more Y, the less Z, almost 2 years later" with a frequency support of 0.006 and "the more Y, the less Z almost, 2 years later" with a frequency support of 0.84. This pattern has a growth rate of 140.

Optimizing Generation of Candidate Gradual Item Sets

In this work, we propose a heuristic solution that is based on ant colony optimization (ACO) to the problem of ( 1) combinatorial candidate explosion and, (2) finding longest set tree for the case of gradual pattern mining. For instance, the problem of combinatorial explosion can be solved by optimizing the process candidate generation. The proposed approach involves learning from a given data set the most occurring nature for every attribute (i.e. increasing, decreasing or irrelevant) as illustrated in Figure 1.4, and using this knowledge to generate highly probable candidates.

Figure 1.4: Illustration of ACO for gradual candidate generation. (+ implies attribute is increasing, -implies attribute is decreasing and x implies attribute is irrelevant) ACO is a popular heuristic approach that imitates the positive feedback reinforcement behavior of biological ants as they search for food: where the more ants following a path, the more pheromones are deposited on that path and, the more appealing that path becomes for being followed by other ants [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | [END_REF]. In other words, ACO exploits the behavior of artificial ants in order to search for approximate solutions to discrete optimization problems [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF].

Cloud Integration of Gradual Pattern Mining Techniques

In view of the fact that there exists institutions such as INSPIRE which encourages member institutions to use a common certified frameworks such as OGC SensorThings to manage sensor data, this work is curious about integrating gradual pattern mining techniques into an OGC SensorThings framework implementation for the purpose of offering them as additional data analysis tools to research institutions that comply with directives from such governing bodies. Again, the OGC SensorThings stands out as one of the best API to interconnect IoT devices, sensor data and applications over the Docker Cloud platform [van de Crommert et al., 2004[START_REF] Hajj-Hassan | Integrating sensor data using sensor observation service: Towards a methodology for the o-life observatory[END_REF], Grellet et al., 2017, Kotsev et al., 2018].

In addition, this work introduces a fuzzy model that crosses time-series data that can be integrated into an OGC SensorThings API implementation. Achieving that integration makes it possible for automatically crossing time-series data from different sources and applying gradual pattern mining algorithms on the crossed data (as illustrated in Figure 1.3) within the same Cloud platform.

Thesis Outline

The rest of the thesis document is organized as follows:

In Chapter 2, we describe the preliminary concepts and definitions about gradual patterns, mining techniques for extracting gradual patterns specifically GRITE and GRAANK approaches and, the traversal strategies employed by existing gradual pattern mining techniques for candidate item set generation. We review literature relating to temporal data mining, data crossing of time-series data from different sources, Cloud platforms into which gradual pattern mining algorithms may be integrated. The concepts discussed in this chapter lays the foundation for the proposed approaches in Chapter 3, Chapter 4, Chapter 5, Chapter 6 and Chapter 7.

In Chapter 3, we adopt the essential definitions of gradual patterns from Chapter 2 and propose formal definitions for temporal gradual patterns. In addition to this contribution, we propose a fuzzy approach for mining temporal gradual patterns. We develop an algorithm to implement the approach and test on real data. We test the computational performance of the algorithm both when it implements a traversal strategy and an ant-based strategy for candidate generation and discuss the results we obtained.

In Chapter 4, we explore the possibility of employing an ant colony optimization technique that uses a probabilistic strategy to generate gradual item set candidates. Further, we propose a representation of generating gradual item set candidates and finding the longest set enumeration tree as optimization problems and, define probabilistic rules through which we may extract gradual patterns more efficiently. Additionally, we develop algorithms that implement this approach to mine for gradual patterns. We compare the computational performance of proposed algorithms against existing gradual pattern mining algorithms and discuss the results we obtained.

In Chapter 5, we adopt definitions of temporal gradual patterns from Chapter 3 and propose formal definitions for temporal gradual emerging patterns. Further, we describe two different strategies (border-based strategy and ant-based strategy) for extracting temporal gradual emerging patterns. We develop two algorithms to implement both strategies and test them on real data. We analyze the test results in order to compare the efficiency of both strategies.

In Chapter 6, we propose a fuzzy approach that crosses time-series data from different sources with the ultimate goal of exploiting the crossings for temporal gradual pattern mining. We implement parallel processing on the developed algorithm implementation in order to improve its efficiency. We test the computational performance of the proposed algorithm and discuss the results we obtained.

In Chapter 7, we describe a software model architecture that integrates the proposed data crossing model implementation together with temporal gradual pattern mining algorithm implementations into a Cloud platform which implements the OGC SensorThings API. We develop a Web application software that achieves this task as proof of concept.

In Chapter 8, we conclude this research study and emphasize the applicability of our models in real-life settings. In future perspectives, we discuss the possible research extensions that may be envisaged based on the contributions made by this study.

"Begin at the beginning," the King said, gravely, "and go on till you come to an end; then stop."

-Lewis Carroll, Alice in Wonderland

Introduction

In this chapter we briefly review the history of gradual pattern mining and describe how it emerged from association rule mining. We describe the preliminary concepts and formal definitions about gradual patterns. Moreover, we describe existing GRITE and GRAANK approaches and the traversal search strategies that they apply for generating gradual item set candidates. In addition, we review related works: temporal data mining, data crossing and Cloud platforms into which gradual pattern mining algorithms may be integrated.

Gradual Patterns

Gradual pattern mining is a research extension in the data mining field and it is a process for extracting gradual correlation knowledge from a numeric data set. Gradual pattern mining seeks to identify gradual dependencies that express correlations between attribute variations in a linguistic manner. For instance a gradual dependency may take the form: "the more A, the less B" where A and B are gradual item sets. The gradual dependence between attributes is a type of tendency expression formed by gradual rules [Hüllermeier, 2002].

To put it another way, gradual pattern mining exploits a quantitative rule-based model that allows a simple and expressive way of knowledge representation using the attributes of a data set [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF], Laurent et al., 2009, Aryadinata et al., 2013, Owuor et al., 2019]. A closely related concept to gradual rules that has been developed is association rules, which expresses relationships between frequent item sets as association dependencies [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]Srikant, 1994]. In fact, gradual rule mining borrows a great deal of its conceptual basis from association rule mining [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF], Hüllermeier, 2002, Laurent et al., 2009]. We expound on this in Section 2.2.2.

Association Rules

Association rule mining was first introduced in [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] and an association rule may take an implicative expression of the form {Y ⇒ Z}, where Y and Z are item sets. This rule may be interpreted as "Y implies Z", intuitively meaning that in a transactional database: items in set Y tend to also contain items in set Z or the existence of item set Y implies the existence of item set Z.

We describe some formal definitions taken from literature about association rule mining as follows: let D be a set of transactions,

c(Y ⇒ Z) = P(Z ⊂ T | Y ⊂ T ) (2.1)
Definition 2.4 (Support). Support s is the probability that any transaction T contains both item sets Y and Z. Therefore, the rule Y ⇒ Z has a support of s if s% of the transactions in

data set D contain Y Z. s(Y ⇒ Z) = P(Y ⊂ T ∧ Z ⊂ T ) (2.2)
Confidence is also be referred to as the accuracy of an association rule and support is also referred to as the frequency of an association rule. In reality, association rule mining is applied on transactional databases in order to generate all association rules whose confidence and support is greater than user-defined thresholds: minimum confidence and a minimum support respectively. Henceforth, an association rule can be termed as frequent if its support is greater than a respective user-specified threshold [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], Agrawal and Srikant, 1994, Hüllermeier, 2002]. Using the transactions in Table 2.1, we may define an association rule: bread ⇒ milk which has a support of 75% with a confidence of 100%. This may be interpreted as 100% of customers who purchase bread also purchase milk and the frequency of this occurrence 75% of the time. We calculate support s by counting all the transactions that have both bread and milk (i.e. 3) and dividing it by the total number of transactions (i.e. 4). We calculate confidence c through dividing the number of transactions that have both bread and milk (i.e. 3) by the number of transactions that have bread (i.e. 3).

As can be seen, such an analysis may be very useful to the shopkeeper especially when it comes to re-stocking the inventory. It comes as no surprise that applications of association rule mining are more popular in the business domain. These rules aid in decisions that the management or owners of businesses (such as supermarkets) need to make in order to design purchase offers such as including items that are frequently bought together with the aim of maximizing profit [Srikant andAgrawal, 1997, Aggarwal, 2015]. [Hüllermeier, 2002] elaborated the theory on quantitative association rule in order to allow for expression of gradual dependence between attributes of a data set in the form of a fuzzy partition. The study by [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] advocates the same view that transforms attributes as fuzzy linguistic variables in order to form fuzzy gradual items. For instance, let us assume we have two attributes: air temperature and mosquito population.

Gradual Rules

Three fuzzy membership sets {low, moderate, high} may be designed for attribute air temperature and, fuzzy membership sets {small, medium, huge} for attribute mosquito population may be designed. Applying the membership degrees of the attributes, a fuzzy gradual association rule may take the form: "the more air temperature is high, the more mosquito population is huge". It is important to realize that a fuzzy gradual item is composed of the attribute together with a corresponding membership to a fuzzy set.

According to [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF], association rules can be extended to express causality relationships between pairs of gradual item sets. For instance, let A 1 be a gradual item: "the more fast foods" and, A 2 be a gradual item: "the greater the danger of obesity". A gradual association dependency may be denoted as A 1 ⇒ A 2 which may be interpreted as: "the more the fast food, then the greater the danger of obesity". This dependency means that more consumption of fast foods implies an increase in the risk of obesity.

In this study, we hold the same position as [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] when it comes to representing gradual item sets since this technique does not require that fuzzy modalities be formed for each gradual item set. As shown in Figure 2.1, the principal aim of gradual rule mining is to relate the attributes of a data set using a gradual dependency whose quality is measured by the tuple count.

Formal Definitions for Gradual Patterns

We describe formal definitions taken from literature about gradual rule mining as follows: Definition 2.5 (Gradual Item). A gradual item is a pair (i, v) where i is an attribute and v is a variation v ∈ {↑, ↓}. ↑ stands for an increasing variation while ↓ stands for a decreasing variation.

For example, (temperature, ↑) is a gradual item that can be interpreted as "the higher temperature". Definition 2.6 (Gradual Pattern). A gradual pattern GP is a set of gradual items.

GP = {(i 1 , v 1 ), ..., (i n , v n )} (2.3)
For example, {(temperature, ↑), (mosquitoes, ↑), (sleep, ↓)} is a gradual pattern that can be interpreted as "the more temperature, the more mosquitoes, the less sleep". Definition 2.7 (Support). Support sup of a gradual pattern is the ratio of the proportion of tuples that respect the pattern to the total number of tuples. It must be remembered that deriving the support of gradual patterns involves the ordering of at least two or more tuples, since the patterns are built on the increasing or decreasing nature of attributes [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF].

To elaborate further, there are two main approaches for deriving the support of a gradual pattern. The compliant subset approach proposed in [Di Jorio et al., 2008, Di-Jorio et al., 2009] identifies tuple subsets D * that can be ordered so that all couples from D * satisfy the order induced by the pattern. Formally, the support is defined as follows:

sup(GP ) = max D * ∈L(GP ) | D * | | D | (2.4)
where L(GP ) denotes the set of all maximal subsets D * = x 1 , ..., x m ⊆ D for which there exists a permutation π such that ∀l ∈ [1, gp -1], x πl GP x πl+1 .

The second approach proposed in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] considers the number of tuples that are concordant by exploiting the Kendall's τ rank correlation. Instead of tuple subsets, it counts the number of tuple couples that satisfy the order induced by the pattern. Therefore, the support is defined by the following formula:

sup(GP ) = | {(x, x ) ∈ D 2 /x GP x } | | D | (| D | -1)/2 (2.5)
where x is such that: for attribute A, for any object x ∈ D, A(x) denotes the value A takes for x and x proceeds x .

Another key point to emphasize is that support describes the quality of a gradual pattern and it is measured as the extent to which the pattern holds for a given data set. Therefore, given a user-specified threshold of minimum support a gradual pattern GP is said to be frequent if:

sup(GP ) ≥ (2.6)

Anti-monotonicity Property

It is easy to observe that the definition of support for gradual rule mining is conceptually similar to that for association rule mining, in the sense that both are determined by the proportion of transactions or tuples that respect the respective rule. [Aggarwal, 2015] further elaborates association rule support by establishing that when an item set Y is contained in a transaction T , all its subsets will also be contained in the transaction. This property is known as the support monotonicity property.

Property 2.1 (Support Monotonicity Property). The support of every subset X of Y is at least equal to that of the support of item set Y .

sup(X) ≥ sup(Y ) ∀X ⊆ Y
(2.7) [Aggarwal, 2015] concludes that the support monotonicity property implicitly indicates that every subset of a frequent item set is also frequent. This is known as downward closure property. Property 2.2 (Downward Closure Property). Every subset of a frequent item set is also frequent.

In the case of gradual pattern mining, if a pattern GP 1 with gradual item set {i 1 , i 2 , i 3 } is not frequent, then it is impossible for a pattern GP 2 whose gradual items is superset of set {i 1 , i 2 , i 3 } to be frequent. This is referred to as the anti-monotonicity property of frequent gradual patterns [START_REF] Aryadinata | M2LGP : Mining Multiple Level Gradual Patterns[END_REF]. . No frequent gradual pattern containing n attributes can be built over an infrequent gradual pattern containing a subset of these n attributes. An infrequent gradual pattern is that pattern whose support is less than the user-specified threshold as implied in Equation (2.6). It is obvious that this property closely resembles the downward closure property of association rule mining. To illustrate using an example, if the gradual pattern {(temperature, ↑), (mosquitoes, ↑ ), (sleep, ↓)} has a support that is less than the user-specified threshold, then any gradual pattern that is a superset of this pattern (i.e. {(temperature, ↑), (mosquitoes, ↑), (sleep, ↓), (risk, ↑)}) will also have a support that is less than the threshold.

Altogether, all supersets of a gradual pattern that is infrequent are likewise infrequent and all subsets of a frequent gradual pattern are likewise frequent [START_REF] Ayouni | Fuzzy gradual patterns: What fuzzy modality for what result[END_REF], Aryadinata et al., 2014, Laurent et al., 2009, Owuor et al., 2019].

Traversal Strategies for Item Set Search

For the purpose of aiding the discussion, we recall the following definitions from literature: Definition 2.9 Minimal Frequent Pattern. an item set A is said to be minimal if A is frequent and there exists at least one of its superset that is also frequent [Bayardo, 1998]. It should be noted that a frequent item set is defined by Equation (2.6).

Definition 2.10 Closed Frequent Pattern. Let I be a finite set of objects in data set D. An item set C ⊆ I is a closed item set iff: h(C) = C (where h is Galois closure operator) [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF]. If C is also frequent then it is a closed frequent pattern. Definition 2.11 Maximal Frequent Pattern. an item set A is said to be maximal if A is frequent and none of its supersets is frequent [Bayardo, 1998].

Figure 2.2 illustrates the population of frequent item sets, closed frequent item sets and maximal frequent item sets in a typical data mining data set. It is important to point out that a maximal frequent pattern includes largest possible number of member item sets. For example let {A, B, C, D} be individual frequent item sets, if pattern {ABCD} is frequent then it is a maximal pattern since there can exist no other pattern with more item set members. If pattern {ABC} is also frequent and its support is greater than that of pattern {ABCD}, then it is a closed pattern. Maximal frequent gradual item sets produce the richest knowledge about the relationships of a data set's attributes since they do not miss any member item set that is relevant to the pattern. Consequently, it makes good sense to optimize a gradual pattern mining technique such that it quickly retrieves maximal item sets. This will eliminate the need to search for any subset of the maximal item set, hence improving the efficiency of the technique.

Classical Traversal Techniques

A lot of research work has been done with the aim of improving the efficiency of mining maximal item sets from data sets. According to [START_REF] Mabroukeh | A taxonomy of sequential pattern mining algorithms[END_REF] and [START_REF] Chand | Sequential pattern mining : Survey and current research challenges[END_REF], in association rule mining and sequential pattern mining, researchers have put a lot of effort into optimizing the pruning technique from which maximal or closed item sets are generated. Specifically in the pattern mining realm, algorithms that are based on depth-first search (DFS) have proven to be more efficient than algorithms that are based on breadth-first search (BFS) since they do not generate useless candidate item sets.

The BFS strategy employs a level-wise candidate generation technique [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] The DFS strategy employs a set enumeration tree (also known as a frequent pattern tree: FP-Tree) to recursively grow long frequent item sets from short ones [START_REF] Han | Mining frequent patterns without candidate generation[END_REF]. Numerous advancements have been made on both Apriori and FP-tree pattern mining techniques with the aim of improving their computational performance and memory utilization. For example Max-Miner is an Apriori-based algorithm that employs a "look ahead" traversal method instead of the previous "bottom-up" traversal method in order to quickly identify maximal item sets as early as possible [Bayardo, 1998].

By the same token, LCM (Linear time Closed item-set Miner) is a pattern growth-based algorithm that uses a set enumeration tree to traverse a depth-first search of frequent closed item sets [START_REF] Uno | Lcm: An efficient algorithm for enumerating frequent closed item sets[END_REF], Uno et al., 2004]. Similarly, COFI-tree (Co-Occurrence Frequent Item tree) algorithm proposed by [START_REF] El-Hajj | Cofi-tree mining: a new approach to pattern growth with reduced candidacy generation[END_REF]] is a pattern growth-based algorithm that is aimed at reducing memory search space.

Gradual Rule Traversal Techniques

With regards to gradual pattern mining, two aspects complicate its mining process: (1) determining frequency support (see Section 2.2.3) and ( 2) the complementary notion of gradual item sets (for each attribute, there exist two gradual item sets). These two challenging aspects are brought about by the nature of patterns and thus traversal because we need to compare lines. As can be seen in Table 2.2 (a) and (b), association rule mining deals with the transactions of a data set while gradual rule mining deals with the attributes of a data set respectively. id items t1 {d, a, c, b} t2 {a, d} t3 {b, c, a} t4 {d, a, c} To elaborate, in association rule mining a single transaction is enough to determine the occurrence frequency of an item set. For instance in Table 2.2 (a) given transaction t3 only, we can tell that item set d is not frequent. In gradual rule mining at least two or more transactions are needed to determine the frequency occurrence of an item set. For instance in Table 2.2 (b) given transaction r3 only, either (a, ↑) or (a, ↓) is possible. Further in order to mine gradual item sets, the complementary notion requires that: for each attribute, there exists two gradual item sets. For instance attribute a creates gradual item sets (a, ↑) and (a, ↓). This is not the case in association rule mining.

In spite of this, techniques have been developed that allow for gradual rule mining through BFS and DFS strategies. In the case of BFS strategy for gradual rule mining, [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF], Laurent et al., 2009] propose approaches GRITE and GRAANK. We describe these approaches in Section 2.2.6 and Section 2.2.7 respectively. In the case of DFS strategy for gradual rule mining, [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF] extends LCM presented by [START_REF] Uno | Lcm: An efficient algorithm for enumerating frequent closed item sets[END_REF], Uno et al., 2004] to propose ParaMiner. We describe this approach in Section 2.2.8 However, both BFS-based and DFS-based approaches have demerits. BFS-based approaches generate large numbers of candidates when dealing with data sets having huge numbers of attributes. This may lead to a combinatorial candidate explosion which overwhelms the algorithm. DFS's major drawback involves finding the parent node of the set enumeration tree with the longest length. DFS-based techniques employ recursion methods (which have exponential computational complexity) to achieve this.

GRITE Approach

GRITE is an acronym standing for GRadual ITemset Extraction and it is a gradual pattern mining technique proposed by [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF]. This technique exploits the anti-monotonicity property in order to efficiently extract all frequent gradual item sets. GRITE technique employs a complementary notion in order generate two gradual items (a ↑, a ↓) for every attribute a of the data set D.

The complementary notion advocates the definition that the frequency support of complementary gradual item sets is equal as established in Equation (2.8). Further, this notion allows the GRITE technique to avoid the consideration of combining complementary gradual items.

sup({a, ↑}) = sup({a, ↓})

(2.8)

The GRITE technique applies three main approaches in order to extract gradual patterns from a numeric data set:

• application of binary matrices in order to represent tuple orders that respect a particular gradual pattern;

• application of a level-wise (k -1-itemset) technique to generate (k-itemsets) as candidates then, applying the bitwise AND operator to join gradual item sets;

• application of a precedence graph method in order to calculate the frequency support of gradual patterns.

Binary Matrix of Orders

As stated earlier, support derivation for a gradual pattern involves tracing an ordered list of tuples that respect the pattern. [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] proposes a binary representation of these orders, which is defined as follows: let i be a gradual item set, G i be the list of objects respecting it and T G i be the set of tuples in G i , Definition 2.8 (Binary Matrix of Orders). G i can be represented by a binary matrix

M G i = (m a,b )a ∈ T G i , b ∈ T G i ,
where m ∈ {0, 1}. If there exists an order relation between a and b, then the bit corresponding to the tuple of a and the column of b is set to 1, and to 0 otherwise. For example using Table 2.3, let us consider a gradual 1-itemset i1 = (temp, ↓). We have G i1 = {(r1, r2, r3, r4), (r1, r2, r4, r3)} and T G i1 = {r1, r2, r3, r4}. The set of orders may be modeled using a binary matrix of size 4 × 4 as illustrated in Figure 2.5 (a). Figure 2.5 (b) and (c) shows the binary matrices of gradual items (hum, ↑) and (mos, ↑) respectively. r1 r2 r3 r4 r1 0 1 1 1 r2 0 0 1 1 r3 0 0 0 0 r4 0 0 0 0

(a) r1 r2 r3 r4 r1 0 1 1 1 r2 0 0 1 1 r3 0 0 0 1 r4 0 0 0 0 (b) r1 r2 r3 r4 r1 0 1 1 1 r2 0 0 0 1 r3 0 1 0 1 r4 0 0 0 0 (c)

Level-wise Candidate Generation

The GRITE algorithm implements a level-wise technique that uses (k -1)-itemset to generate kitemsets using a join operation which is repeated an exponential number of times. For instance, two 1-itemset gradual items may be joined to generate one 2-itemset gradual item: (temp, ↓) and (hum, ↑) may be joined to form {(temp, ↓), (hum, ↑)}. Similarly, four 1-itemset may be joined to form six 2-itemset gradual items and so on.

Granted that every gradual 1-itemset has a bitmap representation of the tuple orders that respect it, bitmap representation of any generated k-itemset may be obtained by performing a bitwise AND operation of the corresponding 1-itemset bitmaps. [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] proposes a theorem that defines this operation as follows:

Theorem 2.1. Let i be a gradual item set generated by joining two gradual item sets i and i . The following relation holds:

M G i = M G i AND M G i .
It comes as no surprise that the theorem relies heavily on the bitwise AND which has a good computational performance. r1 r2 r3 r4 r1 0 1 1 1 r2 0 0 1 1 r3 0 0 0 0 r4 0 0 0 0 For example using the data set D 2.2 in Table 2.3, we can join the 1-itemsets: (temp, ↓), (hum, ↑) and (mos, ↑) in order to generate two 2-itemset candidates {(temp, ↓), (hum, ↑)} and {(hum, ↑), (mos, ↑)} and obtain their bitmap representation through a bitwise AND operation as illustrated in Figure 2.6 (a) and (b) respectively.

Deriving Frequency Support for GRITE

For the purpose of deriving the support of gradual item sets, the GRITE technique arranges the tuples in a lexicographical order which is characterized by the size of the tuple values. This technique can also be referred to as a precedence graph technique. To illustrate this technique we use the following Hasse Diagram: if the value of tuple r1 is greater than that of r2, then the r1 is placed upward of r2 and an arrow drawn from r1 to r2.

[Di- Jorio et al., 2009] holds the position that given a gradual item set i and its associated binary matrix M G i , the frequency support sup(i) is derived from the longest list in M G i . For instance Figures 2. ), (mos, ↑)}) = 3 4 .

GRAANK Approach

GRAANK is an acronym standing for GRAdual rANKing and it is a gradual pattern mining technique proposed by [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]. Similar to GRITE, this technique also exploits the anti-monotonicity property in order to efficiently extract all frequent gradual patterns. Again it maintains the complementary notion established in the GRITE technique of frequency support.

GRAANK technique is an advancement of the GRITE technique; therefore, it similarly applies binary matrices for bitmap representation of tuple orders, it also applies a level-wise technique for generation of gradual item set candidates, and it also applies the bitwise AND operator to join the gradual item sets [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]. However, it should be noted that derivation of frequency support is implemented differently in the GRAANK technique.

Deriving Frequency Support for GRAANK

In contrast to the GRITE approach, the GRAANK approach applies a different technique in order to derive the frequency support of gradual item sets. It exploits Kendall's τ rank correlation to evaluate the support of gradual item sets through concordant pairs. Kendall's τ can be referred to as the frequency of pair-wise inversions and [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] defines it as "the proportion of discordant pairs". It is important to note that the gradual item set support definition given in Equation (2.5) equals the proportion of concordant pairs of tuples that respect the gradual item set.

Let n be objects to be ranked by σ k and k ∈ 1, 2 where σ k (x) gives the rank of object x in σ k ranking. Then, concordant pairs (i, j) are pairs for which rankings agree as follows: either σ 1 (i) ≤ σ 1 (j) and σ 2 (i) ≤ σ 2 (j), or σ 1 (i) ≥ σ 1 (j) and σ 2 (i) ≥ σ 2 (j). The sum of ranks for rankings that are not correlated is given by the formula that follows:

n(n -1) 2m (2.9)
In the case of gradual item set extraction, tuples can be arranged in pairs to form couples which are then tested for respecting the corresponding gradual pattern. It is important to realize that complementary gradual items (i.e. (i, ↑) and (i, ↓)) are distinguished by respectively switching couple numbers (i.e. (i, j) and (j, i). Since none of couple rankings are correlated; then we modify Equation (2.9) as: the total sum of pairs that can be formed is given by n(n -1)/2 (where n is the number of tuples in the data set). For example given that the data set in Table 2.3 has 4 tuples, we have a maximum of 6 couples which are: The Kendall's τ rank correlation technique applied by the GRAANK approach is more efficient computationally and memory-wise than GRITE's precedence graph technique for deriving the frequency support of gradual patterns [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]. The concordant couples can be easily represented as a binary matrix as shown in Figure 2.9 (a), (b), (c), (d) and (e). As can be seen the proportion of concordant couples respecting the corresponding gradual item set can be obtained by summing up all the binary 1s in the respective matrices.

{[r1, r2], [r1, r3], [r1, r4], [r2, r3], [r2, r4], [r3, r4]}.
[r1, r2], [r1, r3], [r1, r4], [r2, r4], [r3, r4]} 5/6 {(temp, ↓), (hum, ↑)} {[r1, r2], [r1, r3], [r1, r4], [r2, r3], [r2, r4]} 5/6 {(hum, ↑), (mos, ↑)} {[r1, r2], [r1, r3], [r1, r4], [r2, r4], [r3, r4]} 5/6
r1 r2 r3 r4 r1 - 1 1 1 r2 0 - 1 1 r3 0 0 - 0 r4 0 0 0 - (a) r1 r2 r3 r4 r1 - 1 1 1 r2 0 - 1 1 r3 0 0 - 1 r4 0 0 0 - (b) r1 r2 r3 r4 r1 - 1 1 1 r2 0 - 0 1 r3 0 1 - 1 r4 0 0 0 - (c) r1 r2 r3 r4 r1 - 1 1 1 r2 0 - 1 1 r3 0 0 - 0 r4 0 0 0 - (d) r1 r2 r3 r4 r1 - 1 1 1 r2 0 - 0 1 r3 0 0 - 1 r4 0 0 0 - (e)
Figure 2.9: Binary matrices representing the sets of concordant object pairs for gradual item sets:

(a) i1 = (temp, ↓), (b) i2 = (hum, ↑), (c) i3 = (mos, ↑), (d) i4 = {(temp, ↓), (hum, ↑)}, (e) i5 = {(hum, ↑), (mos, ↑)}
In the final analysis, GRAANK algorithm performs better than GRITE algorithm for gradual pattern mining. This is because GRAANK algorithm inherits the binary matrix of orders technique; therefore benefiting from its efficiency. GRAANK replaces the precedence graph technique with the Kendall's τ rank correlation technique whose computation cost for calculating the support of gradual item sets is lower.

Equally important, both approaches exploit an efficient bitmap representation technique in order to store validated candidate item sets as matrices. Consequently, this reduces the number of multiple scans through the data set to just one initial scan for every attribute since this technique allows representation of resulting gradual item sets through the binary AND operator.

ParaMiner Approach

ParaMiner is a generic approach that exploits parallel processing for mining closed patterns proposed by [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF]. It extends Linear time Closed itemset Miner (LCM) approach described by [START_REF] Uno | Lcm: An efficient algorithm for enumerating frequent closed item sets[END_REF], Uno et al., 2004] First, ParaMiner encodes a numeric data set into a transactional data set containing variations (i.e. ↑, ↓) of the attributes between each record. For example data set D 2.3 can be encoded into a transactional data set as shown in Table 2.6 (a). Second, ParaMiner applies a data set reduction technique to shrink the size of the encoded transaction data set. Table 2.6 (b) illustrates how a data set is reduced by grouping similar gradual items (with weights). id item-sets

t (r1,r2) {a ↓ , b ↑ , c ↓ , d ↓ } t (r1,r3) {a ↓ , b ↑ , c ↓ , d ↑ } t (r1,r4) {a ↓ , b ↑ , c ↑ , d ↓ } t (r2,r3) {a ↓ , b ↑ , c ↑ , d ↑ } t (r2,r4) {a ↓ , b ↑ , c ↑ , d ↓ } t (r3,r4) {a ↓ , b ↑ , c ↑ , d ↓ } (a)
tids weight item-sets In order to remove infrequent 1-itemset gradual items, the transactional data set (Table 2.6 (b)) is sorted by item occurrence as shown in Table 2.7 (a). For example, if we set the minimum length of tids to 3, we remove infrequent items as illustrated in Table 2.7 (b).

t (r1,r2) 1 {a ↓ , b ↑ , c ↓ , d ↓ } t (r1,r3) 1 {a ↓ , b ↑ , c ↓ , d ↑ } t (r1,r4) , t (r3,r4) , t (r2,r4) 3 {a ↓ , b ↑ , c ↑ , d ↓ } t (r2,r3) 1 {a ↓ , b ↑ , c ↑ , d ↑ } (b)
Third and last, ParaMiner employs a recursive method to find the longest set enumeration tree using the reduced data set (Table 2.7 (b)). Deriving fractional frequency support for the extracted patterns is relatively simple in comparison to GRITE and GRAANK. This support is obtained through dividing the length of the set enumeration tree by the tuple size of the numeric data set. However, it is important to note that the process of encoding a numeric data set into a transactional data set significantly increases its size. For example, if the original numeric data set has n tuples, the encoded data set will have at least n(n -1)/2 tuples. item tids

a ↓ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } b ↑ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } c ↑ {t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } d ↓ {t (r1,r2) , t (r1,r4) , t (r2,r4) , t (r3,r4) } c ↓ {t (r1,r2) , t (r1,r3) } d ↑ {t (r1,r3) , t (r2,r3) } a ↑ {∅} b ↓ {∅} (a)
item tids

a ↓ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } b ↑ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } c ↑ {t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } d ↓ {t (r1,r2) , t (r1,r4) , t (r2,r4) , t (r3,r4) } (b)
Table 2.7: (a) sorted items by occurrence and, (b) sorted reduced transactional data set

One contribution of this study entails proposing a heuristic solution that is based on ant colony optimization to the problem of ( 1) combinatorial candidate explosion and, (2) finding longest set tree for the case of gradual pattern mining.

Temporal Data Mining

Another contribution of this research study involves proposing and describing a fuzzy model that extends the GRAANK approach in order to extract temporal gradual rules from numeric data sets. A temporal gradual rule may take the form: "the higher the temperature, the more mosquitoes almost 4 hours later". In this section, we review related literature concerning temporal data mining. [START_REF] Roddick | A bibliography of temporal, spatial and spatio-temporal data mining research[END_REF] state that temporal data mining deals with the analysis of events by one or more dimensions of time. They distinguish temporal data mining into two main fields: one concerns extracting similar patterns within the same or among different time sequences, this is referred to as trend analysis; the other concerns extracting causal relationships among temporally oriented events.

Trend analysis was introduced by [START_REF] Agrawal | Mining sequential patterns[END_REF] as they tried to solve the problem of 'absence of time constraint' in their proposed algorithm AprioriAll for extracting sequential patterns [START_REF] Chand | Sequential pattern mining : Survey and current research challenges[END_REF]. For example this problem may be represented by the scenario that follow: a shop does not care if someone bought 'bread', followed by 'bread and jam' three weeks later; they may want to specify that a customer should support a sequential pattern only if adjacent elements occur within a specified interval, say 3 days. Therefore, for a customer to support this pattern, the customer should have bought 'bread and jam' within 3 days of buying 'bread'. [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] proposed Generalized Sequential Pattern (GSP) that utilizes a user-specified time gap to generate candidates for temporally-oriented frequent patterns. GSP is 5 times faster than AprioriAll since it generates less candidates. However, [START_REF] Masseglia | Efficient mining of sequential patterns with time constraints: Reducing the combinations[END_REF] proposed Graph for Time Constraint (GTC) that is more efficient than GSP because it handled time constraints prior to and separately from the counting step of the data sequence.

It should be noted that for both GSP and GTC, a pattern is considered to be relevant, if its item sets occur at a minimum time interval determined by a user-specified sliding-window size. We shy away from this approach since it locks out any frequent pattern whose time constraint is larger or smaller than the specified window size. For example given the previous scenario, since the window size is set at '3 days' any element occurring slightly above 3 days (i.e. 3 days and 4 hours) is not considered.

The latter field that deals with discovering causal relationships may be conceptualized by a gradual pattern that correlates the causal effect among the attributes of a data set. [START_REF] Fiot | Evolution patterns and gradual trends[END_REF] proposed an 'trend evolution' approach that extracted gradual trends which are represented in the form: "An increasing number butter purchases during a short period is frequently followed by a purchase of cheese a few hours later." This approach involves converting a numeric database into a fuzzy membership degree database (referred to as a trend database) using a user-specified fuzzy partition.

Example 2.4. Let us consider an example adopted from [START_REF] Fiot | Evolution patterns and gradual trends[END_REF]. Specifically, the trend database is generated from the evolution procedure that is applied on two tuples that are related to the same attribute within the original data set. For example Table 2.9 is generated by applying a user-defined fuzzy set partition on Table 2.8. We comment that the evolution procedure may be improved by the avoidance of relating all the tuples of the data set by themselves, since this may lead to a combinatorial explosion in the number of evolved (or generated) tuples.

oil
month price, high consumption, medium sales, low Feb .1

r 1 Mar .2 .3 .4 r 2 Apr .4 .5 .7 r 3 May 1 .2 .3 r 4
Table 2.9: Generated trend data sequence

In conclusion, the trend evolution technique represents the fuzziness of temporal correlations among frequent item sets by using a linguistic format (i.e. "a few hours later"). However, we propose an approach in Chapter 3 that represents the temporal fuzziness of frequent gradual item sets through a numeric format (i.e. "almost 3 hours later").

Data Crossing for Pattern Mining

The third contribution of this study encompasses proposing and describing a fuzzy model that crosses time-series data from different sources in order to exploit the crossings for gradual pattern mining. In this section, we review existing techniques concerning crossing time-series data.

To begin with, data crossing may be defined as:

"a process that enables the matching of different data sets using a pre-defined criteria and combining their data points to form a new data set" [START_REF] Hajj-Hassan | Integrating sensor data using sensor observation service: Towards a methodology for the o-life observatory[END_REF], Hajj-Hassan et al., 2016[START_REF] Da Costa | Use of data warehouse to manage data from wireless sensors networks that monitor pollinators[END_REF].

It should be remembered that the main reason for crossing different data set is to attempt to discover hidden correlations that otherwise cannot be discovered by analyzing the individual data sets in isolation. Several previous work exist related to crossing data from different sensors in a WSN (Wireless Sensor Network) via query processing [START_REF] Vaidehi | Distributed database management and join of multiple data streams in wireless sensor network using querying techniques[END_REF], Gonçalves et al., 2012, Wang et al., 2013].

Query processing allows users to retrieve information about sensed data values by issuing pre-defined queries to the storage engine. In fact, the nature of storage engine used by a WSN determines which type of query processing is applicable [START_REF] Gonçalves | Dystoa dynamic storage model for wireless sensor networks[END_REF], Wang et al., 2013].

According to [START_REF] Gonçalves | Dystoa dynamic storage model for wireless sensor networks[END_REF], there are 3 groups of storage models: local storage model where sensors keep their on data in a distributed manner, external storage model, where all sensors store data in a common database in a centralized manner, and data-centric storage model which combines both models.

It is important to highlight that query processing relies on declarative languages (e.g. SQL -Structured Query Language) in all these models. Q1 shows an example of a query. Therefore, most research work relate to increasing the efficiency of query processing in either a distributed or a centralized WSN model [START_REF] Vaidehi | Distributed database management and join of multiple data streams in wireless sensor network using querying techniques[END_REF], Gonçalves et al., 2012, Boukerche et al., 2016]. However, many works on these techniques do not consider crossing data sets by approximating the 'date-time' attribute.

Q1: SELECT MAX HUMIDITY FROM SENSOR_DATA WHERE SAMPLE INTERVAL = 1 min

However, the emergence of the term fuzzy join, which enables declarative languages such as SQL to generate views based on textual similarity (i.e. through approximations). A fuzzy-search model is proposed in [Małysiak-Mrozek et al., 2018b] and [Małysiak-Mrozek et al., 2018a] which extends U-SQL to allow fuzzy join approximations on numeric data sets. This is implemented by representing attribute values as fuzzy members and assigning them to a linguistic variable. U-SQL1 is big data query language created by Microsoft for (Azure Data Lake Analytics) ADLA service and it is a combination of SQL and C# languages as illustrated in Figure 2.10 (Q2 shows a sample U-SQL excerpt). It is important to note that @RESULT and @SENSOR_DATA are variables and @SENSOR_DATA may include a separate code excerpt which extracts data from different sources. U-SQL can be applied on the following data storage engines: Azure Data Lake Storage, Azure Blob Storage, and Azure SQL DB, Azure SQL Data Warehouse. It should be underlined that currently it is extremely difficult to apply U-SQL on non-Microsoft storage engines such as Postgres.

Q2:

@RESULT = SELECT temperature, humidity, COUNT(*) AS DataSize FROM @SENSOR_DATA FETCH FIRST 10 ROWS;

However, data management frameworks especially the OGC SensorThings are built on top of NoSQL models. Therefore, SQL -based or U-SQL-based querying models are difficult to integrate into such frameworks. To provide one solution to this problem, we propose a model that is based on a NoSQL fuzzy model. This allows for our technique for crossing unrelated data sets to be easy to integrate into OGC SensorThings API which is built on Postgres data storage engine and its querying model does not support U-SQL.

[da [START_REF] Da Costa | Use of data warehouse to manage data from wireless sensors networks that monitor pollinators[END_REF] proposes another model that extracts, transforms and loads (ETL) into a data warehouse different time-series data collected in a WSN, as illustrated in Figure 2.11. In this work, they demonstrate how to transform the data by normalizing the data types of its attributes including date-time before loading it into a data warehouse. In this research study, we propose a fuzzy model in Chapter 6 that will extract time-series data from unrelated sources, transform them using a fuzzy membership function so that crossing is possible through estimation even when the date-time values do not match. Additionally, we apply this model on an OGC SensorThings API implementation since it offers provision for numerous unrelated time-series data.

OGC SensorThings Framework

OGC2 is an international consortium consisting of over 530 companies, government agencies, research organizations and universities driven to make geospatial data and services FAIR (Findable, Accessible, Interoperable and Reusable). The OGC SensorThings API is an open standard that is built on top of the OGC Sensor Web Enablement (SWE) and International Organization for Standardization Observation and Measurement (ISO/OGC O&M) data model [van de Crommert et al., 2004, Liang et al., 2016].

The SensorThings API is specifically designed for constrained IoT (Internet of Things) devices; therefore, it employs the use of efficient technologies such as RESTful (Representational State Transfer) API, JSON (JavaScript Object Notation) encoding, MQTT protocol, OASIS OData (Open Data protocol) and flexible URL conventions. The OGC SensorThings framework is an advancement of the OGC SOS (Sensor Observation Service) framework. In contrast to its predecessor, the SensorThings framework is specifically designed for resource-constrained IoT devices and web-based platforms [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF].

The SensorThings API is composed of 2 parts: (1) the Sensing part and ( 2) the Tasking part. The Tasking part provides a standard way for parameterizing (also called tasking) of IoT devices such as: sensors and actuators, smart cities in-situ platforms, wearable devices, drones, autonomous vehicles and so forth. This research study is interested in the Sensing part which allows IoT devices and applications to perform CRUD operations through HTTP requests. The Sensing part is designed based on the ISO/OGC O&M data model and it defines 8 entities for IoT sensing applications. Figure 2.12 depicts the 8 entities together with their properties and relationships [START_REF] Hajj-Hassan | Integrating sensor data using sensor observation service: Towards a methodology for the o-life observatory[END_REF], Liang et al., 2016].

Figure 2.12: The 8 sensing entities that make OGC SensorThings framework [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF] According to [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF] the 8 entities are defined as follows:

(1) Thing: with regard to IoT, a thing is an object of the physical world or the information world (i.e. virtual) that is capable of being identified and integrated into communication networks. The properties of the Thing entity include: name, description, and properties.

(2) Location: is a geographical description that locates the Thing or the Things it associates with. This entity is defined as the last known location of the Thing. It should be noted that a Thing's Location may be similar to the Thing's Observation's FeatureOfInterest. The properties of the Location entity include: name, description, encoding type and location (whose type is defined by the encoding type property).

(3) HistoricalLocation: provides the times of the last known and previous locations of the Thing entity. This entity has one property, that is time which records the time of the Thing's known Location.

(4) Datastream: this entity groups a collection of Observations measuring the same ObservedProperty and produced by the same Sensor. The properties of the Datastream entity include: name, description, unit of measurement, observation type, observed area, phenomenon time and result time.

(5) Sensor: is an instrument that observes a property or phenomenon with the aim of producing an estimated value of the phenomenon. The properties of the Sensor entity include: name, description, encoding type and meta-data.

(6) ObservedProperty: this entity specifies the phenomenon of an Observation. The properties of the ObservedProperty entity include: name, definition and description. (7) Observation: this entity defined as the act of measuring or determining the value of a phenomenon. The properties of the Observation entity include: phenomenon time, result, result time, result quality, valid time and parameters.

(8) FeatureOfInterest: this entity is described together with the Observation entity in this way: an Observation leads to a phenomenon being assigned a value. A phenomenon can also be described as a 'property of feature' or the FeatureOfInterest of the Observation. The FeatureOfInterest entity has the following properties: name, description, encoding type and feature.

For example if we are interested in observing the room temperature of a building as a phenomenon, we may install a WI-FI connected thermostat inside the building. The sensing entities of our experiment are illustrated in Figure 2.13. According to [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF], the OGC SensorThings API offers three main benefits listed as follows:

1. it allows the proliferation of new high value services with lower overhead of development and wider reach, 2. it lowers the risks, time and cost across a full IoT product cycle and, 3. it simplifies the connections between devices-to-devices and devices-to-applications.

Popular certified software implementations of the SensorThings API are accomplished: (1) in Java language by 52 o North Initiative for Geospatial Open Source Software3 and ( 2) in Google's golang (GO) language by GOST (golang SensorThings) IoT Platform4 . When the SensorThings API is implemented on a Cloud platform, it exposes a service document resources (which offers the 8 entity sets) that allows its clients to navigate the entities in a hyper-media driven manner.

All things considered, this research study recommends the GOST software implementation of the SensorThings API because it is utilizes the Docker Cloud platform. The Docker Cloud platform provides good support integrating our gradual pattern mining algorithms which are implemented in Python language.

Cloud Platforms for Gradual Pattern Mining

This research study's fourth contribution includes describing a software architecture model which integrates gradual pattern mining algorithms into a Cloud platform that implements an OGC SensorThings API. The SensorThings API provides an efficient framework for managing and sharing unrelated time-series sensor data. For this reason the study emphasizes the implementation of the API in order to exploit the availability of time-series data from different sources for extraction of temporal gradual patterns.

It is important to highlight that existing algorithm implementations of any version of GRITE and GRAANK is either in Python, C++, Java or R language. These implementation languages are preferred because they allow for parallel computing which improves performances of the algorithms. However, these algorithm implementations are not scalable therefore in this section, we examine Cloud platforms that may support integration of such algorithm implementations. We also discuss the benefits that may come with such a Cloud integration.

To begin with, there exist numerous formal definitions of Cloud computing. [Bernstein, 2014] provides two of these definitions that are internationally accepted:

(1) "Cloud computing is form of resources pooling where a provider's computing resources are pooled to serve multiple consumers using a multi-tenant model, with different physical and virtual resources dynamically assigned and re-assigned according to customer demand", (2) "Cloud computing is a form of rapid elasticity where computing capabilities can be elastically provisioned and released, in some cases automatically, to scale rapidly and inward commensurate with demand".

Both definitions involve provision of computing services to a customer rapidly and on demand basis. There exists two fundamental virtualization technologies in Cloud computing for providing such services: the hypervisor and the container. The hypervisor technology provides virtual machines which can execute directly on bare metal hardware or on an additional software layer. A container is a virtualization technology that avails protected portions of the operating system (i.e. containers virtualize the operating system) [Merkel, 2014, Bernstein, 2014, Anderson, 2015]. Figure 2.14 illustrates the difference between these two technologies. [Bernstein, 2014] In the recent years the popularity of the container virtualization technology has exceeded that of hypervisor virtualization technology by a large margin. The increase in popularity is largely attributed to the benefits provided by Docker platform, which implements a container virtualization technology [Merkel, 2014]. Different from its hypervisor-based counterparts, Docker is comes with light-weight computing resource which allows consumers to enjoy improvements in computation speed and memory performance.

Docker is an open source project that was started in early 2013 offering a systematic deployment of Linux applications inside portable containers. Docker containers provide hardware abstraction for both developers and users since multiple containers can independently run on the same Operating System without affecting each other. This feature make allows developers to build and test their applications on any environment and execute it on all platforms without any modification [Merkel, 2014, Bernstein, 2014, Anderson, 2015].

Commercially, there are many providers of Cloud computing services. These services are categorized into three main models: (1) Infrastructure-as-a-service (IaaS), ( 2) Platform-as-aservice (PaaS) and ( 3) Software-as-a-service (SaaS). Microsoft Azure and Amazon Web Service are two of the largest Cloud computing services providers. Both of them allow for deployment of Docker through their platforms and they provide it as PaaS.

It is important to highlight that integrating gradual pattern mining algorithms into a Docker platform enables the access of these algorithms through a SaaS (Software-as-a-service) model as illustrated in Figure 2.15. In a SaaS distribution model, software is centrally hosted and licensed on a subscription basis. This introduces a flexibility that spares users the agony of spending hours trying to install analysis software [START_REF] Joshi | Sentiment Analysis Tool on Cloud: Software as a Service Model[END_REF]. In addition, integration of gradual pattern mining algorithms into the Cloud allows users to utilize servers that are more secure, reliable and flexible than on-premises servers at a cheaper subscription price. Again due to replicability, server downtime is almost non-existence. Computing resources can be scaled up or down depending on the demand of the gradual pattern mining algorithm.

All in all, this study aims to avail gradual pattern mining on a light-weight platform that is easily configurable by different research observatories (such as OREME 5 ) and institutions around the World. For this reason Docker is the most suitable Cloud platform to achieve this because of the benefits mentioned above and the GOST implementation of the OGC SensorThings API is recommended because it provides a functional Docker Web application. In Chapter 7, we present a system architecture that is built on top of Docker OGC SensorThings API.

Summary

To sum up, we began by describing association rules and how gradual rules are built on top of association rules.

We presented definitions for gradual rules and we discussed two (breadth-first and depth-first) traversal techniques for item set search in association rule mining. In the case of gradual rule mining, the breadth-first search technique is easier to implement than the depth-first search due to the complexity presented in (1) determining frequency support of gradual item sets and ( 2) the complementary notion of gradual item sets. Next, we described three popular existing approaches (GRITE GRAANK and ParaMiner) for mining gradual rules. As a result we propose a heuristic solution to the problem of combinatorial candidate explosion and the problem of finding parent node of an FP-Tree.

We review existing literature relating to temporal pattern mining. We discuss two existing techniques for mining temporal frequent item sets: the first one employs a sliding-window size technique; the second one employs an evolution trend with a user-specified fuzzy partition. Many of the existing approaches do not represent temporal gradual patterns using approximated numeric values. Therefore, we propose an approach that employs a fuzzy model to extract gradual patterns of the form: "the more X, the more Y, almost 3 minutes later".

We review existing literature concerning crossing time-series data from different sources. We discover that query processing is the most popular approach. However, it relies on a U-SQL-based fuzzy-join model for crossing unrelated data sets in a Microsoft Azure data lake environment. We intend to construct a crossing model that may be integrated into an OGC SensorThings framework whose querying model does not support U-SQL.

Finally, we review existing Cloud technologies that best suit integration for gradual pattern mining algorithm implementations. We recommend the Docker Cloud platform and the GOST certified implementation of the OGC SensorThings API since they will be easier for research institutions to adopt. We propose a system architecture model to demonstrate proof of concept.

Chapter 3

Temporal Gradual Patterns

Introduction

In this chapter, we propose and describe a fuzzy modality that extends the GRAANK approach (which is described in Section 2.2.7) in order to extract fuzzy-temporal gradual patterns. We propose definitions for temporal gradual patterns and use them to describe the proposed temporal gradual pattern mining technique referred to as T-GRAANK (Temporal-GRAANK). We implement an algorithm for the proposed technique and test it on real data.

Temporal Gradual Patterns

We begin by recalling that gradual pattern mining allows for retrieval of correlations between attributes of a numeric data set through rules such as: "the more exercise, the less stress". However, it is possible that a temporal lag may exist between changes in the attributes and their impact on others, existing gradual pattern mining techniques do not take this aspect into account. We illustrate the possibility of this temporal aspect of gradual item sets in the example that follows.

Example 3.1. We consider an arbitrary data set D 4.1 in Table 3.1, containing the number of physical exercises that a person performed along with the stress levels together with the corresponding dates. For instance in Table 3.1, we may extract a gradual pattern of the form: {(exercise, ↑ ), (stress, ↓)} sup=3 , the support is 3 because tuples <r1, r2, r5> can be ordered successively to match the gradual rule. As can be seen, the extracted gradual pattern has not utilized the 'date' attribute to include it in the representation of retrieved knowledge. It may be interesting to include the extraction of this attribute in the gradual pattern mining technique in order to show the time specificity of the extracted gradual pattern.

In this chapter, we propose and describe a fuzzy approach that handles such situations in order to retrieve patterns such as: "the more exercise, the less stress almost 1 month later". In order to allow for extraction of this kind of patterns, we propose three main steps: (1) transform the data set in a step-wise manner in order to retrieve 'time differences', (2) apply a modified GRAANK algorithm implementation on the transformed data set in order to extract gradual patterns and ( 3) apply a fuzzy model on the 'time differences' in order to estimate a time lag between the extracted gradual patterns.

Proposed Definitions for Temporal Gradual Patterns

For the purpose of describing temporal gradual patterns, we propose the definitions that follow: Definition 3.1. Time Lag. A time lag αt is the amount of time t that elapses before or after the changes in a one gradual item affects the changes in another gradual item.

α ∈ {= +, = -, ≈ +, ≈ -} (3.1)
where '= +t' implies 'exactly t time later', '= -t' implies 'exactly t time before', '≈ +t' implies 'almost t time later' and, '≈ -t' implies 'almost t time before'. For example '≈ +5sec' is a time lag that may interpreted as 'almost 5 seconds later'. The time tag's value t is derived from the formula that follows:

t = m ∈ M (3.2)
where m is the center value of a fuzzy triangular membership function of the fuzzy set M which is composed of time differences deduced from a date-time attribute as: M = {|r 1 -r 1+s |, ..., |r nr n+s |}. We fully describe M in Section 3.3.1 and, m in Section 3.3.2.

For example given a date-time sequence: {3, 3, 4, 5, 5}, the center of a triangular membership function spanning that universe may be taken to be 4. Definition 3.2. Temporal Gradual Item. A temporal gradual pattern g can be defined as a gradual pattern that includes a crisp time lag. A temporal gradual item is made up of two parts: a gradual item and a crisp time lag.

g = (i, v) αt (3.3)
where (i, v) is a gradual item and αt is a time lag where α ∈ {= +, = -} such that '= +t' implies a time lag of t later and, '= -t' implies a time lag of t earlier. For example (stress, ↓) =+2weeks is a temporal gradual item interpreted as the "the less stress 2 weeks later".

Definition 3.3. Fuzzy Temporal Gradual Item. A temporal gradual pattern g f can be defined as a gradual pattern that includes a fuzzy time lag. A temporal gradual item is made up of two parts: a gradual item and a fuzzy time lag. (3.4) where α ∈ {≈ +, ≈ -} such that '≈ +t' implies a time lag of almost t later and, '≈ -t' implies a time lag of almost t earlier. For example (exercise, ↑) ≈-1week is a fuzzy-temporal gradual item that can be interpreted as the "the more exercise almost 1 week earlier".

g f = (i, v) αt
Definition 3.4. Reference Gradual Item. A reference gradual item (i 0 , v 0 ) is a gradual item from which other temporal gradual items are varied with time. It should be understood that a reference gradual item is specified by the user, it cannot be the 'date-time' attribute and it is part of fuzzy-temporal gradual pattern or a temporal gradual pattern. Definitions 3.6 and 3.7 elaborate this definition. Definition 3.5. Temporal Gradual Pattern. A temporal gradual pattern TGP is a set of temporal gradual items with one the reference gradual item set.

T GP = {(i 0 , v 0 ), (i 1 , v 1 ) αt 1 , ..., (i n , v n ) αtn } (3.5)
where (i 0 , v 0 ) is the reference gradual item and (i n , v n ) αtn are temporal gradual items.

Definition 3.6. Fuzzy-Temporal Gradual Pattern. A fuzzy temporal gradual pattern TGP f is a set of fuzzy temporal gradual items with one the reference gradual item set.

T GP f = {(i 0 , v 0 ), (i 1 , v 1 ) αt 1 , ..., (i n , v n ) αtn } (3.6)
For example {(jogging, ↑), (walking, ↑), (stress, ↓) ≈+2weeks } is a fuzzy temporal gradual item set that can be interpreted as "the more jogging, the more walking, the less stress almost 2 weeks later". Definition 3.7. Representativity. The representativity rep of a fuzzy-temporal gradual pattern is the ratio of the number of transformed tuples to the number of all tuples.

rep(T GP

f ) = |R | |R| (3.7)
where R is tuple subsets in the transformed data set and, R is tuple subsets in original data set.

Given a threshold of minimum representativity δ, a fuzzy-temporal gradual pattern TGP f is said to be relevant if:

rep(T GP f ) ≥ δ (3.8)
Definition 3.7 also holds for temporal gradual patterns.

Mining Temporal Gradual Patterns

Our goal is to transform a time-series data set into a temporal format that allows for extraction of gradual patterns with the corresponding time lag information. We propose a fuzzy model that uses a membership function to estimate the time lag of a temporal gradual pattern. We describe these three approaches in the sections that follow.

Data Transformation Model

In this section, we demonstrate how a typical time-series data set can be transformed into a temporal format in order to allow for extraction of fuzzy temporal gradual patterns based on a user-specified minimum representativity threshold.

Let D be a time-series data set with a set of attributes {a t , a 1 , a 2 , ..., a k }: a t is 'date-time' attribute and every attribute a k is composed of a set of tuples R = {r 1 , r 2 , ..., r n }. We provide a function notation f for data transformations in Equation (3.9), which requires two inputs: a r a user-specified reference attribute, s a transformation step derived from the minimum representativity threshold.

D s = {f (s, a r , D) | s ∈ N} = {a s k } (3.9)
such that:

a s k =      a k = {|r 1 -r 1+s |, ..., |r n -r n+s |} if a k == a t a k = {r 1 , ..., r n-s } if a k == a r a k = {r 1+s , ..., r n } otherwise
where D s is a set of transformed data sets; N = 1, ..., Z and Z ≈ |R|(1 -δ), R is all tuple subsets in data set D.

We propose the pseudocode steps that follow for transforming time-series data sets (the algorithm is shown in Algorithm 1):

1. Calculate maximum number of integer transformation steps using the minimum representativity threshold.

2. For every transformation step, transform the data set in a step-wise manner with respect to the reference attribute as elaborated in Equation (3.9).

3. On every transformed data set, apply the T-GRAANK algorithm to mine for fuzzytemporal gradual patterns. We discuss this algorithm in Section 3.3.3.

4. Repeat steps 2 and 3 until all transformation steps are exhausted.

Example 3.2. We consider an arbitrary data set containing the number of hours a person spent performing physical exercises together with the stress levels after irregular number of days, as shown in Table 3 If we take attribute 'exercise' as the reference attribute (a r ) and a minimum representativity threshold of 0.8, then the attributes may be applied to the transformation function f to generate a transformed data set as illustrated in Table 3.2 (b).

After this transformation, we mine the Table 3.2 (b) for gradual patterns. For instance the longest path that match gradual pattern {(exercise, ↑), (stress, ↓)} is <t2, t3>, so the support is 2 4 . We observe that a representativity of 0.8 constitutes 4 out of 5 tuples. On the negative side, there is a decrease in the representativity of the data as we progress our transformations to larger steps. On the positive side, representativity has a less significant effect on large data sets because of their great number of tuples.

Next, we approximate a time lag for the extracted pattern {(exercise, ↑), (stress, ↓)} using the values of attribute 'days lag' (i.e. {3, 1, 5, 2}). It is important to note that our interest is to estimate time lag using tuples from which we derived our pattern, in this case <t2, t3>. In order to approximate the most relevant time lag, we apply a fuzzy model which is described in the section that follows.

Building the Fuzzy Model

Generally, there exists a great number of membership modalities that one can build functions from (for instance triangular, trapezoidal, Gaussian among others), and it is very difficult to determine which one will fit the data set perfectly. However, it is enough to pick modalities that span the whole universe and remain scalable [Zadeh, 1965, Schockaert et al., 2008, Ayouni et al., 2010, Nath Mandal et al., 2012].

Since our goal is to represent the fuzziness of the 'time lag' numerically, we focus on identifying a membership function (MF) that allows the peak position to accommodate a single numerical value. This automatically eliminates MFs whose peaks accommodate a range of values (such as the trapezoidal MF) and leaves us two options shown in Figure 3.1.

x min

x max membership degree (a)

x min

x max membership degree (b) Equally important, our approach seeks to approximate the peak position (also called TRUE center ), minimum and maximum extremes of a MF, such that the MF includes a majority of members in the population of calculated time differences. For this reason, the triangular MF is better justified for this study than the Gaussian MF, since the latter allows false values outside the minimum and maximum extremes to have small membership degrees (illustrated by shaded areas in Figure 3.1b).

Slide, Re-calculate Technique for Time Lag Estimation

The TRUE center of a distribution is established when the largest proportion of members are closely spaced around it [START_REF] Montgomery | Applied Statistics and Probability for Engineers[END_REF]. In light of this, we propose the algorithm in Algorithm 2 which initially takes the median as the center and slides the MF step-wisely to left or/and right until we find this value.

We point out that our "slide re-calculate" technique is conjectural. However, through simulation we observed that its accuracy is greatly improved when an optimum "slice" (or gap) is chosen by which the MF is slid. In our case, at line4 : slice = 0.1 of M edian. This implies that at worst, the algorithm will slide a total of 20 times: 10 times to the left and 10 times to the right. Each slide is equivalent to a single loop iteration. As an illustration, Figure 3.2 (a) shows the MF for the data set in Table 3.2 (b). Applying the MF to the 'days lag' population {3, 1, 5, 2} with respect to members of path <t2, t3>: {1, 5}, we generate the fuzzy data set: {((1, 0), (5, 0)}. Therefore, the membership degree support for '≈ 2.5days' is 0 2 . As it can be seen, the problem may be that the MF in Figure 3.2 (a) is either be too narrow or is pivoted on a wrong medial value. We shy away from widening the MF boundaries since this increases the size of the universe. However, if we slide the MF to the left by "1day slice" as shown in Figure 3.2 (b) we now observe the fuzzy set with respect to path <t2, t3> becomes: {(1, .8), (5, 0)}. Altogether, pattern: {(exercise, ↑), (stress, ↓) ≈+1.5days } has a support of 2 4 , a representativity of 4 5 and a time lag: '≈ +1.5days' whose support is 1 2 .

Large Data Sets With Outliers

The data set in Example 3.2 is small and the distribution of time differences between the tuples tend to be almost uniform. However, most real life data sets are huge and the time differences may have one or more outliers. Under those circumstances, designing a membership function that spans the entire universe of time lags may lead to extremely false approximations of the actual time lag.

We propose the use of quartiles or percentiles in order to narrow the span of the MF, so that the extreme outliers to the left and/or right of the universe are ignored as illustrated in Figure 3.3. Once the MF has been determined, the successive steps for approximating time lag are similar to the ones in Section 3.

T-GRAANK Technique

We recall that the overall procedure for extracting temporal gradual patterns involves 3 steps:

(1) transforming the data set (2) applying a variant of GRAANK technique to fetch gradual patterns from the transformed data set and ( 3) applying a fuzzy model to estimate the time lag of gradual item sets. In this section, we describe the second step.

T-GRAANK denotes Temporal-GRAANK since it modifies the GRAANK technique proposed in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]. The algorithm applies a breadth-wise search strategy to generate gradual item set candidates as shown in Algorithm 3. It should be noted that the methods at line12 and line13 are implemented by Algorithm 2.

Algorithm 3: T -GRAAN K Algorithm

Input : D -transformed data set, T d -time differences, minSup-minimum support Result: T GP -set of (fuzzy) temporal gradual patterns

1 foreach Attribute A in D do 2 G ← build concordance matrices A ↑ and A ↓ ; 3 end foreach 4 G ← APRIORIgen (G) ; /*

Experiments

In this section, we present an experimental study of computational performance of our proposed T-GRAANK approach for mining temporal gradual patterns. We implement T-GRAANK algorithm in Python language.

Source Code

The Python source code for T-GRAANK algorithm is available at our GitHub repository https: //github.com/owuordickson/t-graank.git.

Computational Complexity

In this section, we derive the asymptotic computational time complexity of the T-GRAANK algorithm shown in Algorithm 3 using the Big-O analysis technique.

It is important to mention that since our proposed approach is a variant of the GRAANK approach proposed in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF], it similarly benefits from the binary matrix representation. However, the T-GRAANK technique has a higher computational complexity since it processes multiple transformed data sets whose computation is approximately equivalent to the combined computation of successively repeated GRAANK operations.

We derive the asymptotic complexity of each algorithm by focusing on the number loops and assuming that other steps are computationally relatively constant. Therefore, in Table 3.3: n denotes number of tuples, m denotes number of columns, r denotes representativity, C denotes constant statements [START_REF] Vaz | Automated Big-O analysis of algorithms[END_REF].

Algorithm Asymptotic Complexity Bound Algorithm 2 X = 20(C) + C O(20) Algorithm 3 Y = n 4 + n 3 + X + C O(n 4 ) Algorithm 1 Z = n(1 -r)(nm + Y + C) O(n 5 )

Table 3.3: Asymptotic time complexity of T-GRAANK algorithm

From Table 3.3, it should be noted that the complexities of Algorithms 2 and 3 are successively nested in Algorithm 1. Therefore, the overall time complexity is given by: f (Z) whose upper bound is slightly greater than O(n 5 ) which deduces the worst-case performance of the algorithm.

Data Set Description

We test the computational performance of the T-GRAANK algorithm implementation in order to determine the behavior of the Algorithm with respect to a user-specified minimum representativity and minimum support thresholds in Section 3.4.4. We execute the T-GRAANK algorithm on a synthetic data set with 50 tuples and 3 attributes. The test runs were performed on a 2.9 GHz Intel Core i7 MacBook Pro 2012 model, with 8 GB 1600 MHz DDR3 RAM.

We further test the computational performance of the T-GRAANK algorithm by applying it on a larger 'Power Consumption' data set, obtained from UCI Machine Learning Repository [START_REF] Dua | UCI machine learning repository[END_REF]. This is a time-series numerical data set with 9 attributes and 2075259 tuples has describes the electric power consumption in one household (located in Sceaux, France) in terms of active power, voltage and global intensity with a one-minute sampling rate between 2006 and 2010. We performed test runs on 4 node instances of a HPC (High Performance Computing) Meso@LR platform1 each made up of 14 cores and 128GB of RAM.

In order to prove the applicability of the T-GRAANK technique, we performed two separate tasks: (1) harvest NDVI data from a satellite positioned over 4 regions in Kenya; (2) obtain rainfall amount data about the 4 regions from a weather report and apply T-GRAANK on the data in order to determine if they will match the conclusion obtained from analyzing the NDVI data. The aim is to confirm the conclusions made in [START_REF] Davenport | On the relation between rainfall and the normalized difference vegetation index for diverse vegetation types in east africa[END_REF], that the NDVI (Normalized Difference Vegetation Index) is a sensitive indicator of the interannual variability of rainfall in the East African region. Data employed in this use case come from the data-cube Open Source framework tool provided by https://www.opendatacube.org and the results were confirmed using data from the Kenya Meteorological Service repository http://www.meteo.go.ke/index.php?q=archive. We present the results in Section 3.4.4.

Experiment Results

In this section, we present results of our experimental study of 3 data sets. First, we show computational performance results and, the extracted patterns results when T-GRAANK algorithm is applied on a synthetic data set and UCI power consumption data set. These results are available at: https://github.com/owuordickson/meso-hpc-lr/tree/master/results/tgps/uci. Second, we show results of a use case example.

Computational Performance Results

The run time performance of T-GRAANK is shown in Figure 3.4. In both Figure 3.4 (a) and (b), it can be seen that as representativity threshold decreases, there is an increase in run time. This behavior is due to the fact that the number of data set transformations to be mined is inversely proportional to the minimum representativity threshold; therefore, as representativity decreases the number of transformed data sets increase and this increases the run-time. It can also be observed that as minimum support threshold decreases, the run time increases. This is because as support reduces, the number of gradual pattern candidates increase; consequently, increasing the run-time. T-GRAANK algorithm is an extension of GRAANK algorithm proposed in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]. On one hand, the T-GRAANK algorithm is more computationally intensive than GRAANK algorithm. On the other hand, the increase in computations can be justified by the fact that new knowledge about temporal tendencies is extracted which was not possible previously.

Extracted Temporal Gradual Patterns

In Figure 3.5 (a), the number of temporal gradual patterns reduce significantly as minimum support increases. This is because as minimum support increases, it demands only gradual patterns whose quality surpass the respective threshold. In Figure 3.5 (b), the number of extracted patterns significantly reduce as minimum representativity increases. One reason for this is that as representativity increases fewer transformed data sets are generated; consequently, the algorithm is provided with fewer transformed data sets from which it can extract temporal gradual patterns.

Use Case Example

In order to test applicability of the T-GRAANK technique, we performed two separate tasks related to weather and compared their results. The aim of the use case is to confirm the conclusions of [START_REF] Davenport | On the relation between rainfall and the normalized difference vegetation index for diverse vegetation types in east africa[END_REF], that the NDVI (Normalized Difference Vegetation Index) is a sensitive indicator of the inter-annual variability of rainfall in the East African region. In the first task, we retrieved the historical (October-December) rainfall distribution amounts of 4 towns in Kenya from a weather report in [Archive1, 2014[START_REF] Archive2 | Review of weather in kenya during the octoberdecember 2015[END_REF], shown in Table 3.4. Here, we chose two observable patterns: {(M AK, ↓), (W AJ, ↑)} =+2years and {(ELD, ↑ ), (N RB, ↑)} =+2years .

town
In the second task, we first generated NDVI data (for year 2013 and 2015) from LAND-SAT 7 satellite images over Kenya using a novel tool known as data-cube2 . Data-cube is a Python-based platform for the expanded use of satellite data in an Open Source framework. The generated NDVI data is a time-series data with 4 attributes (Makueni, Wajir, Eldoret and Nairobi) and 13 tuples (containing NDVI values of the respective 4 towns). Lastly in the second task, we applied our proposed approach on the NDVI data and we obtained the results shown in Table 3.5. As can be seen, the patterns generated by our algorithm match the selected patterns in Table 3 We emphasize that it is difficult to get clear satellite images between short intervals due to cloud coverage; therefore, the data-cube tool runs an algorithm that re-creates the image based on previous images. It may be for this reason that the time approximation for the pattern {W AJ+, M AK-} is slightly less than 2 years.

Summary

In this chapter, we propose an approach for extending the existing GRAANK algorithm in order to extract fuzzy temporal gradual patterns. This approach combines two main concepts: (1) a fuzzy model for estimating temporal tendencies of the patterns and (2) a gradual pattern mining technique for extracting the temporal gradual patterns.

It is important to mention that we also test the T-GRAANK algorithm on another time-series data set and present the results in Chapter 4.4.3. We do not show these results in this chapter because they include a comparative study of ACO-TGRAANK algorithm which is built on top of an Ant Colony Optimization approach that is introduced in Chapter 4.

Chapter 4

Ant Colony Optimization for Gradual Pattern Mining "One day I will find the right words, and they will be simple" -Jack Kerouac, The Dharma Bums

Introduction

In this chapter, we propose a heuristic solution that is based on ant colony optimization to the problem of ( 1) combinatorial candidate explosion and, (2) finding the longest set tree for the case of gradual pattern mining. We use definitions in Chapter 2.2.3 to aid discussions in this chapter. Finally, we perform experiments to analyze the performance of our proposed algorithms.

Ant Colony Optimization

Gradual pattern mining is a technique in the data mining realm that maps correlations between attributes of a data set as gradual dependencies. A gradual dependency may take a form of "the more Attribute K , the less Attribute L ". In order to formulate such rules, a candidate rule is generated from respective attribute combinations and its quality tested against a user-specified frequency support threshold.

Many gradual pattern mining approaches extend either a breadth-first search (BFS) or depthfirst search (DFS) strategy for mining gradual item sets. In this chapter, we propose an ant colony optimization (ACO) strategy that uses a probabilistic approach to improve efficiency of both BFS-based and DFS-based approaches for mining gradual item sets. ACO, as originally described by [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF], is a general-purpose heuristic approach for optimizing various combinatorial problems. It exploits the behavior of a colony of artificial ants in order to search for approximate solutions to discrete optimization problems [START_REF] Cicirello | Ant colony control for autonomous decentralized shop floor routing[END_REF], Silva et al., 2002, Blum, 2005, Runkler, 2005, Dorigo and Stützle, 2019]. The application areas for ACO are vast; for instance in the telecommunication domain, [START_REF] Sim | Multiple ant colony optimization for load balancing[END_REF]] employed it to optimally load balance circuit-switched networks.

ACO imitates the positive feedback reinforcement behavior of biological ants as they search for food: where the more ants following a path, the more chemical pheromones are deposited on that path and, the more appealing that path becomes for being followed by other ants [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | [END_REF]. In order to make an accurate interpretation of ant colony system, assume that the paths between nodes B and D, D and E have longer lengths than paths between nodes B and C, C and E (as indicated by the weighted distances in Figure 4.1a). Let us consider what happens at regular discrete time intervals: t = 0, 1, 2... . Suppose that 12 new ants come to node B from A and, 12 new ants come to node E from F at each time interval. Each ant travels at a speed of 2 weighted distance per time interval and, that by moving along at time t it deposits pheromones of intensity 1, which completely and instantaneously evaporates in the middle of the successive time interval (t + 1, t + 2). b) at time t = 0 there is no pheromone intensity on any path; so ants choose all paths with equal probability and, (c) at time t = 1 the pheromone intensity is stronger on the shorter paths; therefore more ants prefer these paths.

At time t = 0 no path has any pheromone intensity and, there are have 12 new ants at node B and 12 new ants at node E. The ants select between nodes C and D randomly; therefore, on average 6 ants from each node move towards C and 6 ants towards D -as shown in Figure 4.1b.

At time t = 1 there are 12 new ants at node B and 12 new ants at node E. The 12 new ants at node B will find a pheromone intensity of 6 on the path that leads to node D deposited by the 6 ants that used it previously from node B and, a pheromone intensity of 12 on the path that leads to node C deposited by 6 ants that used it coming from node B and 6 that arrived from node E. Therefore, the ants will find the path to node C more desirable than that to node D. The probability of the ants choosing to move towards node C is 2/3, while that of moving towards node D is 1/3 and, 8 ants will move towards node C and 4 ants towards node D. The same is true for the 12 new ants at node E, as shown in Figure 4.1c.

Preliminary Mathematical Notations

In this section, we introduce formal mathematical notations taken from literature concerning ant colony system (ACS). We use the traveling salesman problem (TSP) [START_REF] Jünger | Chapter 4 the traveling salesman problem[END_REF] in order to describe these preliminary mathematical notations [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | [END_REF].

Given a set of n towns, the TSP problem can be stated as the problem of finding the shortest route that visits each town once. The path between town i and j may be represented as d i,j and, an instance of the TSP may also be presented as a graph composed of nodes and edges as shown in Figure 4 .n be the number of ants in town i at time t and, q = n i=1 b i (t) be the total number of ants. Each ant is a simple agent that:

• chooses a town to go to based on the probability that is a function of the town distance and amount of pheromone present on the connecting edge,

• is prohibited from returning to already visited towns until a tour visit of all towns is completed (this is managed by a tabu list) and,

• deposits pheromone trails on each visited edge (i, j), once it completes the tour.

Let τ i,j (t) be the pheromone intensity on edge (i, j) at time t and, each ant at time t chooses the next town to visit, where it will be at time t + 1. We define q movements made by q ants in the interval (t, t + 1) a single iteration of the ACS algorithm. Therefore, every n iterations of the algorithm each ant completes a visit of all the towns (tour cycle) and, at this point the pheromone intensity is updated according to the formula in Equation (4.1). τ i,j (t + n) = ρ . τ i,j (t) + ∆τ i,j (4.1) where ρ (usually < 1) is a coefficient such that (1 -ρ) represents the evaporation of pheromone intensity between time t and t + n,

∆τ i,j = q k=1 ∆τ k i,j
where ∆τ k i,j is the quantity per unit of length of pheromone substance laid on edge (i, j) by the kth ant between time t and t + 1 and it is given by:

∆τ k i,j = C L k
if kth ant uses path(i, j) in its tour (between time t and t + n)

0 otherwise
where C is a constant and L k is the tour length of the kth ant.

In order to satisfy the constraint that an ant visits all the n towns, each ant is associated with a tabu list (tabu k ) that stores the towns already visited by the ant up to time t and forbids it from re-visiting them until the tour cycle is complete. At the end of the tour cycle, the tabu list is used to compute the distance of the path followed by the ant then, it is emptied and, the next tour cycle begins.

We introduce the term visibility (η i,j = 1/d i,j ) which we use to define the probability p k i,j (t) of the kth ant moving from town i to j as shown in Equation (4.2).

p k i,j (t) =    [τ i,j (t)] α . [η i,j ] β k∈allowed k [τ i,k (t)] α . [η i,k ] β if j ∈ allowed k 0 otherwise (4.2)
where allowed k = {N -tabu k } and α and β are parameters that control the relative importance of the pheromone intensity against visibility.

Therefore, the probability p k i,j (t) is a trade-off between visibility η i,j (which instructs that the closest town should be selected with highest probability -implements a greedy constructive heuristic) and, pheromone intensity at time t τ i,j (t) (which instructs that the edge (i, j) with most ant traffic should be selected with highest probability -implementing an autocatalytic process).

According to [START_REF] Hartmann | Online optimization of a color sorting assembly buffer using ant colony optimization[END_REF], Ant colony optimization (ACO) utilizes a set of artificial ants to probabilistically contrive solutions S through a collective memory, pheromones stored in matrix T , together with a problem specific heuristic η. In this chapter, we will consider one variant of ACO called 'MAX-MIN ant system' [START_REF] Stützle | Max-min ant system[END_REF] to optimize both BFS and DFS for the case of gradual pattern mining.

ACO for BFS Candidate Generation

In this section we describe ACO-GRAANK technique which is an optimized version of the GRAANK technique described in Chapter 2.2.7. The ACO-GRAANK technique inherits the efficient bitwise binary representation of concordant tuple couples that respect a gradual item set, but utilizes an ant-based technique for generating candidate item sets. In order to apply ACO to the GRAANK approach, we need to identify a suitable heuristic representation of the gradual item set candidate generation problem that can be solved using an ant colony system. 4.1), gradual BFS techniques seek to find frequent gradual patterns M = {m 1 , m 2 , ..., m k } (where ∀m ∈ M : m ⊆ n) by generating and testing numerous candidates. It is important to recall that a non-trivial gradual pattern m k is set of at least 2 gradual items and, a singleton gradual item is a pair composed of an attribute and variation (increasing/decreasing) -see Chapter 2.2.3.

Example 4.2. We consider a sample graphs of artificial ants moving on the edges of gradual items a+, a-, b+, b-, c+ and, c-(where + denotes 'increasing', -denotes 'decreasing' and minimum support threshold = 0.5) as shown in Figure 4.3. For the sake of simplicity, we remove all edges connecting to nodes (or gradual items) whose frequency support < and, assume that support({a+, c+}) > but support({a+, c+, b+}) < .

In order to make an accurate interpretation of the ACS, assume that the distances of all node edges are equal. Let us consider what happens at regular discrete time intervals: t = 0, 1, 2, ... . Suppose that 12 new ants come to nodes a and b respectively at time t = 0 and another 119 new ants to nodes a and b at time t = 1, 2, ... . Each ant travels at a speed of 2 edge distances per time interval and, that by moving along at time t it deposits pheromones of intensity 1 only if all the nodes visited up to that time t form a gradual item set whose support ≥ . The pheromone instantaneously evaporates in the middle of the successive time interval (t + 1, t + 2). there is no pheromone intensity on any path; so ants choose paths with equal probability, and (c) at time t = 1 the pheromone intensity is stronger on paths with cheapest gradual variations; therefore, ants prefer these paths.

At time t = 0 no path has any pheromone intensity; therefore, the 12 news ants at nodes a and b choose all paths with equal probability as shown in Figure 4.3b. Since support({a+, c+, b+}) < the ant from a that chose edges between nodes a+, c+ and b+ and the 3 ants from b that chose edges between nodes b+, c+ and c+ do not deposit any pheromone on any of these edges.

At time t = 1 119 new ants arrive at nodes a and b. The 119 new ants at node a will find a pheromone intensity 6 on the path that leads to a-deposited by ants that used it previously from node a-and, a pheromone intensity of 15 at node a+: 6 on the path that leads to b+ (3 deposited by ants that departed from a+ and 3 deposited by ants that arrived from b+), 9 on the path that leads to c+ (3 deposited by ants that departed from a+ and 6 deposited by ants that arrived from c+). The probability of the ants choosing to move towards node a-is 6/21, that of moving towards node a+ is 15/21, that of moving towards node b+ is 6/15 and, that of moving towards c+ 9/15. The same is true for the new 119 ants at node b, as shown in Figure 4.3c. Therefore, the best variation routes (or candidates) are: {a+, c+, b-}, {a+, b+}, {a-, c-}.

Similarly, each ant is associated with a tabu list tabu k that stores the nodes already visited up to time t and forbids the ant from revisiting them until the tour cycle is complete. In addition, the tabu list also keeps track of node edges which do not meet the minimum frequency support requirement. Since we modify notation d i,j in Equation ( 4.3), visibility (η i,j = 1/d i,j ) is consequently affected. The probability p k i,j (t) of the kth ant moving from node i to j becomes:

p k i,j (t) =    [τ i,j (t)] α k∈allowed k [τ i,k (t)] α if j ∈ allowed k and (sup(i) ≥ & sup(j) ≥ ) 0 otherwise (4.5)
where allowed k and α are similar to Equation (4.2).

Therefore, the probability p k i,j (t) is a function of pheromone intensity at time t: τ i,j (t) (which instructs that the edge (i, j) with most ant traffic should be selected with highest probability -implementing an autocatalytic process). In gradual pattern mining visibility between nodes i and j can be compared to the possibility of forming a candidate by combining node i and j; and, it is either 'visible' to the ant if both nodes are frequent or 'invisible' to the ant if one of the nodes is infrequent. So, η i,j is denoted as either 1 or 0 for 'visible' or 'invisible' respectively.

ACO for DFS FP-Tree Search

In this section, we describe ACO-ParaMiner technique which is an optimized version of the existing DFS-based ParaMiner technique proposed by [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF] (see Chapter 2.2.8). ACO-ParaMiner inherits the technique of transactional encoding from ParaMiner, but utilizes an ant-based technique to find the longest frequent pattern tree (FP-Tree). Similarly, for the purpose of applying ACO to a DFS-based approach, we identify a suitable heuristic representation to the problem of finding the parent node of the longest FP-tree. In order to make an accurate interpretation of ant colony system, assume that the paths between nodes r 1 and r 3 , r 3 and r 2 have longer lengths than paths between nodes r 1 and r 4 , r 4 and r 2 (as indicated by the distances in Figure 4.4a). Let us consider what happens at regular discrete time intervals: t = 0, 1, 2... . Suppose that 12 new ants come to node r 1 and, 12 new ants come to node r 2 at each time interval. Each ant travels at a speed of 0.5 distance per time interval and, that by moving along at time t it deposits pheromones of intensity 1, which completely and instantaneously evaporates in the middle of the successive time interval (t + 1, t + 2). no pheromone intensity on any path; so ants choose all paths with equal probability and, (c) at time t = 1 the pheromone intensity is stronger on the shorter paths; therefore more ants prefer these paths.

At time t = 0 no path has any pheromone intensity and, there are have 12 new ants at node r 1 and 12 new ants at node r 2 . The ants select between nodes r 4 and r 3 randomly; therefore, on average 6 ants from each node move towards r 4 and 6 ants towards r 3 -as shown in Figure 4.4b.

At time t = 1 there are 12 new ants at node r 1 and 12 new ants at node r 2 . The 12 new ants at node r 1 will find a pheromone intensity of 6 on the path that leads to node r 3 deposited by the 6 ants that used it previously from node r 1 and, a pheromone intensity of 12 on the path that leads to node r 4 deposited by 6 ants that used it coming from node r 1 and 6 that arrived from node r 2 . Therefore, the ants will find the path to node r 4 more desirable than that to node r 3 . The probability of the ants choosing to move towards node r 4 is 2/3, while that of moving towards node r 3 is 1/3 and, 8 ants will move towards node r 4 and 4 ants towards node r 3 . The same is true for the 12 new ants at node r 2 , as shown in Figure 4.4c. Therefore, the most appealing FP-Tree is {(r 1 , r 4 ), (r 2 , r 4 )} which both appear in transactions with gradual items {b ↑ , c ↑ , d ↓ } ⇔ {b+, c+, d-}.

Proposed Mathematical Notations of ACS for GPFP-Tree Problem

The gradual pattern FP-Tree (GPFP-Tree) problem can be stated as:

"the problem of finding the longest FP-Tree from which frequent gradual patterns can be constructed."

In the case of DFS for gradual pattern mining, we inherit the concept of encoding data sets into transactional data sets and harness this to represent the GPFP-Tree problem as a slightly different version of the TSP problem. Given a set of n tuples of a data set, we seek to find the cheapest route that visits the most tuples once. The path between tuples i and j may be represented as d i,j and an instance of the GPFP-Tree may also be represented as a graph composed of tuples (or nodes) and edges. Each edge distance is derived from the formula:

d i,j = 1 1 + (r i , r j ) count (4.6)
where (r i , r j ) count is the occurrence count of tuple pair (r i , r j ) in an encoded transactional data set.

Let b i (t) | i = 1, 2, ...n be the number of ants in node i at time t and, q = n i=1 b i (t) be the total number of ants. Each ant is a simple agent that:

• chooses a node to go to based on the probability that is a function of the node distance and amount of pheromone present on the connecting edge,

• is prohibited from returning to already visited nodes until a tour visit of all allowed nodes is completed (this is managed by a tabu list) and,

• deposits pheromone trails on each visited edge (i, j), once it completes the tour.

Let τ i,j (t) be the pheromone intensity on edge (i, j) at time t and, each ant at time t chooses the next node to visit, where it will be at time t + 1. We define q movements made by q ants in the interval (t, t + 1) a single iteration of the ACS algorithm. Therefore, every n iterations of the algorithm each ant completes a visit of all the nodes (tour cycle) and, at this point the pheromone intensity is updated according to the formula in Equation (4.7).

τ i,j (t + n) = ρ . τ i,j (t) + ∆τ i,j (4.7)
where ρ and ∆τ i,j are similar to Equation (4.1).

Similar to the original ACS, each ant is associated with a tabu list (tabu k ) that stores the nodes already visited by the ant up to time t and forbids it from re-visiting them until the tour cycle is complete. At the end of the tour cycle, the tabu list is used to compute the distance of the path followed by the ant then, it is emptied and, the next tour cycle begins. The probability p k i,j (t) of the kth ant moving from node i to j as shown in Equation (4.8).

p k i,j (t) =    [τ i,j (t)] α . [η i,j ] β k∈allowed k [τ i,k (t)] α . [η i,k ] β if j ∈ allowed k 0 otherwise (4.8)
where allowed k and α and β are similar to Equation (4.2).

Therefore, in the GPFP-Tree problem probability p k i,j (t) is a trade-off between η i,j and τ i,j (t). Put differently, it a trade-off between a greedy constructive heuristic and an autocatalytic process.

Convergence Proof

There exist two main ant colony optimization techniques: (1) Ant Colony System (ACS) proposed in [START_REF] Dorigo | Ant colony system: a cooperative learning approach to the traveling salesman problem[END_REF]] and ( 2) MAX-MIN Ant System (MMAS) proposed in [START_REF] Stützle | Max-min ant system[END_REF]. We recommend the MMAS over ACS for the problem of gradual pattern mining since it offers a better performance for finding an optimal solution for either a combinatorial problem or finding the longest FP-Tree problem.

In the case of BFS gradual pattern mining we wish to find an optimal solution (which is a valid maximal gradual item set) that updates the matrix such that the preceding generated solutions are either subsets of or similar to the optimal solution. Such a characteristic may also be referred to as a Convergence Property. The study of [START_REF] Stutzle | A short convergence proof for a class of ant colony optimization algorithms[END_REF] illustrates a convergence proof that applied directly to MMAS. The proof holds that:

"for any small constant > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P * (t) ≥ 1 -and that the probability tends to 1 for t → ∞."

Further, [START_REF] Stutzle | A short convergence proof for a class of ant colony optimization algorithms[END_REF] establishes that after an optimal solution has been found, it takes a limited number of algorithm iterations for the pheromone trails that belong to the found optimal solution to grow higher than any other pheromone trail. With regard to BFS gradual pattern mining, this implies that the values of the pheromone matrix will no longer change significantly after such iterations. Therefore, we propose that this convergence property of ACO techniques can be harnessed to determine the limit of algorithm iterations for generating gradual item set candidates. With regard to DFS gradual pattern mining, after an optimal parent node is found, it takes a limited number of algorithm iterations for the pheromone trails corresponding to the optimal parent node to grow higher than other pheromone trails. Therefore, the algorithm should generate similar nodes subsequently.

However, the proofs do not hint at any time required to find an optimal gradual item set solution. It is equally important to point out that for both ACS and MMAS approaches, if no ant finds a better "best-so-far" trail within a finite number of iterations, all ants tend to construct a similar pheromone trail. This may also be referred to as the local minima phenomenon [START_REF] Satukitchai | An early exploratory method to avoid local minima in ant colony system[END_REF]. In the case of BFS gradual pattern mining, this may imply that a non-optimal gradual item set solution may be found to be optimal if no ant finds the best maximal item set solution within a limited number of iterations.

Proposed ACO-based Approaches

In this section, we present two approaches: ACO-GRAANK and ACO-ParaMiner which optimize GRAANK and ParaMiner algorithms respectively. Both algorithms are variants of "MAX-MIN ant system" [START_REF] Stützle | Max-min ant system[END_REF].

ACO-GRAANK Approach

The chief aim of gradual pattern mining approaches is to extract (if possible maximal) gradual item sets whose quality surpass a user-specified threshold. Classical GRITE and GRAANK techniques employ a level-wise search (BFS) traversal and join strategy to build maximal gradual item sets by combining minimal item sets. This strategy has a high time complexity especially when presented with a huge number of minimal gradual item sets.

On the contrary, it can be shown that a heuristic approach can generate, with extremely high efficiency, gradual item set candidates whose probability of being valid is high [Kalpana andNadarajan, 2008, Li et al., 2016]. Moreover, this eliminates the repetition that comes with combining minimal item sets. In this chapter, we present an ant-based approach that guides artificial ants to find highly probably valid gradual item set candidates.

In order to represent the gradual pattern mining problem as a combinatorial problem, we take the position that a gradual item set may also be referred to as a pattern solution. In that case all possible gradual item set solutions (S n ) are admissible and can be generated based on the pheromone matrix (T a,j ). Notwithstanding, all the gradual item sets in a generated solution will be evaluated and the solution updated with only valid item sets.

First we mention that initially there exists an equal chance for any attribute A (of data set D) to either increase (+) or decrease (-) or be irrelevant (×). As the algorithm acquires more knowledge about valid patterns, the possibilities of the 3 options are adjusted accordingly. We propose an artificial pheromone matrix as shown in Equation (4.9). The matrix contains knowledge about pheromone proportions of the 3 gradual options for each attribute.

T a,j = q × 3 (4.9)

where q: number of attributes, a = 1, ..., q and, j ∈ {+, -, ×}

At the beginning all artificial pheromones p a,j in matrix T a,j are initialized to 1, then they are updated as follows at time interval (t, t + 1):

• every generated gradual item set solution is evaluated and only valid solutions are used to update the artificial pheromone matrix. Invalid solutions are stored and used to reject their supersets;

• in a given valid solution, each gradual item set is used to update the corresponding artificial pheromone p a,j (t) (where j is either + or -) by formula: p a,j (t) = p a,j (t) + 1.

The probability rule P a,j (t) is given by calculating the proportions of its artificial pheromones p a * , as shown in Equations ( 4 Instead of applying a breadth-first search strategy to generate temporal gradual patterns (i.e. applied in T-GRAANK approach), this algorithm applies the ACO-GRAANK approach as shown at line 1 in Algorithm 5. The rest of the steps in the algorithm remain the same as the ones described in the T-GRAANK approach in Chapter 3.3.

ACO-ParaMiner Approach

The principal aim of DFS-based approaches is to extract frequent closed item sets. ParaMiner extends LCM (Linear time Closed item-set Miner) proposed by [START_REF] Uno | Lcm ver. 2: Efficient mining algorithms for frequent/closed/maximal itemsets[END_REF] to the case of gradual pattern mining. ParaMiner derives its efficiency from (1) a data set reduction process which reduces the size of input the algorithm has to process and ( 2) parallelizing the recursive function of finding the parent node of the longest FP-Tree.

Despite this, it should be remembered that for the case of gradual pattern mining, encoding of a numeric data set into a transactional data set is required (see Chapter 2.2.5). In reality, the size of encoded transactional data set is almost squared the size of the original data set. For example, if the original numeric data set has n tuples, the encoded data set will have n(n -1)/2 tuples. This surge in the input data set size impacts the efficiency of the approach negatively.

We propose the following ACO optimizations to the ParaMiner approach (described in Chapter 2.2.8): (1) in addition to reducing the transactional data set by combining similar item set transactions and removing infrequent ones, we construct a cost matrix of all corresponding nodes. ( 2) we replace the parallelized recursive function with a non-recursive heuristic function that quickly learns the longest FP-tree with the help of the cost matrix.

To illustrate, we use data set D 4.3 in Table 4.3. In order to remove infrequent items, the transactional data set is sorted by item occurrence as shown in Table 4.4 (b). If we set the minimum length of tids to 3, we remove infrequent items as illustrated in Table 4.5 (a).

1 {a ↓ , b ↑ , c ↓ , d ↓ } t (r1,r3) 1 {a ↓ , b ↑ , c ↓ , d ↑ } t (r1,r4) , t (r2,r4) 3 {a ↓ , b ↑ , c ↑ , d ↓ } t (r3,r4) t (r2,r3) 1 {a ↓ , b ↑ , c ↑ , d ↑ } (a)
item tids

a ↓ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } b ↑ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } c ↑ {t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } d ↓ {t (r1,r2) , t (r1,r4) , t (r2,r4) , t (r3,r4) } c ↓ {t (r1,r2) , t (r1,r3) } d ↑ {t (r1,r3) , t (r2,r3) } a ↑ {∅} b ↓ {∅} (b)
} b ↑ {t (r1,r2) , t (r1,r3) , t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } c ↑ {t (r1,r4) , t (r2,r3) , t (r2,r4) , t (r3,r4) } d ↓ {t (r1,r2) , t (r1,r4) , t (r2,r4) , t (r3,r4) } (a) r1 r2 r3 r4 r1 1 1/4 1/3 1/5 r2 1 1 1/4 1/5 r3 1 1 1 1/5 r4 1 1 1 1 (b)
We define a cost matrix: C i,j = n × n (where n is number of tuples in the original numeric data set i.e. Table 4.3) and initialize it to 1. Using the sorted and reduced transactional data set in Table 4.5 (a), we update elements of cost matrix that correspond to the inverse of occurrence count of tids as shown in Equation (4.11). Table 4.5 (b) illustrates the cost matrix of Table 4.5 (a). In this case we observe that tids with more occurrences have least costs; therefore, they are better candidates for parent nodes. (4.11) where (ri, rj) count is the occurrence count of tid pair (ri, rj).

C i,j = 1 1 + (ri, rj) count
We define an artificial pheromone matrix as shown in Equation ( 4.12). This matrix contains knowledge about the pheromone proportions of every node of the data set.

Γ i,j = n × n (4.12)
where n: number of tuples in numeric data set

At the beginning all artificial pheromones p i,j in matrix Γ i,j are initialized to 1, then they are updated as follows at time interval (t, t + 1):

• every generated node, is used to retrieve the corresponding attributes from the sorted reduced transactional data set. A set intersection of the tids of all these attributes provides an FP-Tree whose length is tested against the specified threshold;

• if the length of the FP-tree surpasses the specified threshold, the pheromones corresponding to the tids are incremented by 1: p i,j = p i,j (t) + 1;

• if the length of the FP-Tree falls below the specified threshold, the pheromones corresponding to the tids are evaporated by a factor : (1 -)p i,j (t).

We propose a probabilistic rule that allows us to learn a parent node of the longest FP-Tree in a non-recursive manner. This rule is shown in Equation (4.13).

P i,j (t) = p i,j (1/C i,j ) n k=1 p k i,j (t)(1/C k i,j ) (4.13)
Algorithm 6 illustrates an implementation of ACO-Paraminer technique. As can be seen, the main steps are:

1. Encode a numeric data set D into a transactional data set and reduce it by combining similar item sets and removing infrequent item sets. Use the reduced transactional data set D red to construct a Cost Matrix C.

2. Generate nodes that have high probability of being parent nodes using the Cost Matrix and Pheromone Matrix Γ i,j .

3. For each generated node, retrieve corresponding attributes from D red and determine the intersection of their tids. If the length of the resulting intersection surpasses the minimum length threshold ς, then update the pheromones.

4. Repeat steps 2-3 until the algorithm starts to generate similar nodes. 18 end while 19 return GP ;

Experiments

In this section, we present an experimental study of computational performance of our algorithms. We implemented BFS-based GRAANK (as described in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]) and ACO-GRAANK; and DFS-based ParaMiner (as described in [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF]) and ACO-ParaMiner algorithms in Python language. All experiments were conducted on a (High Performance Computing) HPC platform Meso@LR1 . We used one node made up of 14 cores and 128GB of RAM.

Source Code

The Python source code of all the 4 algorithms is available at: https://github.com/owuordickson/ ant-colony-gp.git. Since [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF] does not provide a Python implementation of ParaMiner, we extended a Python source code of LCM (https://github.com/scikit-mine.git) to implement our ParaMiner as described by [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF]. Table 4.6 shows the features of the numerical data sets used in the experiments for evaluating the computational performance of the algorithms. The 'Breast Cancer' data set, obtained from UCI Machine Learning Repository [START_REF] Patrício | Using resistin, glucose, age and bmi to predict the presence of breast cancer[END_REF], is composed of 10 quantitative predictors and binary variable indicating the presence or absence of breast cancer. The predictors are recordings of anthropometric data gathered from the routine blood analysis of 116 participants (of whom 64 have breast cancer and 52 are healthy).

Data Set Description

The 'Cargo 2000' data set, obtained from UCI Machine Learning Repository [START_REF] Metzger | Comparing and combining predictive business process monitoring techniques[END_REF], describes 98 tracking and tracing events that span 5 months of transport logistics execution. The 'Power Consumption' data set, obtained from UCI Machine Learning Repository [START_REF] Dua | UCI machine learning repository[END_REF], describes the electric power consumption in one household (located in Sceaux, France) in terms of active power, voltage and global intensity with a one-minute sampling rate between 2006 and 2010.

The 'Directio' data set is one of 4 data sets obtained from OREMES's data portal2 that recorded swell sensor signals of 4 buoys near the coast of the Languedoc-Roussillon region in France between 2012 and 2019 [Bouchette, 2019].

Experiment Results

In this section, we present results of our experimental study on the 4 data sets described in Section 4.4.2 using implemented algorithms: GRAANK, ParaMiner, ACO-GRAANK, ACO-ParaMiner. The results reveal behaviors of the 4 algorithms when applied on different data sets that vary in tuple and attribute size. We use these results to compare computational performances of the 4 algorithms in Section 4.4.3 and extracted gradual patterns in Section 4.4.3. We discuss the results in Section 4.4.4. All experiment results can be obtained from: https: //github.com/owuordickson/meso-hpc-lr/tree/master/results/gps/14cores.

Comparative Computational Experiments

This experiment compares the computational runtime and memory usage of algorithms ACO-GRAANK, ACO-ParaMiner, GRAANK, ParaMiner when applied on data sets: B&C, C2K, Buoys, UCI. 4.5 (a) shows the runtime and, Figure 4.5 (b) shows the memory usage of these 4 algorithms when applied on B&C data set. We observe that ParaMiner (black triangular curve) has the slowest runtime followed (in order) by GRAANK (brown square curve), ACO-ParaMiner (blue circle curve) and, ACO-GRAANK (red cross curve). Again ParaMiner has the highest memory usage followed (in order) by ACO-ParaMiner, ACO-GRAANK and, GRAANK. In Figure 4.7 (a), ParaMiner has a runtime greater than 72 hours and it does not appear in the graph plot. GRAANK has the slowest runtime at support 0.5 which reduces significantly below ACO-ParaMiner's runtime and, ACO-GRAANK has the fastest runtime. In ACO-ParaMiner has the slowest runtime followed (in order) by ACO-GRAANK and GRAANK. Error outputs on UCI data set with 46774 tuples; so, we use a UCI data set with 1000 tuples as shown in Figure 4.11. In Figure 4.11 (a) we observe that ParaMiner has the slowest runtime followed by ACO-ParaMiner and GRAANK and ACO-GRAANK have relatively low runtimes. In 4.7 shows consistent gradual patterns extracted by all algorithms from the 4 data sets whose support is high. It is important to remember that the higher the value of support, the better the quality of the gradual pattern. Figure 4.12 compares the number of extracted gradual patterns by all algorithms.

In Figure 4.12 (a), B&C data set: we observe that GRAANK extracts the most pattern at support 0.5 followed (in order) by ACO-ParaMiner, ParaMiner and ACO-GRAANK. For other supports ParaMiner and ACO-ParaMiner have the most extracted patterns. In Figure 4.12 (b), C2K data set with 200 tuples: we observe that with exemption of support 0.5, ACO-ParaMiner extracts more patterns than GRAANK and ACO-GRAANK. In Figure 4.12 (c), Buoys data set with 200 tuples: we observe that GRAANK extracts the most pattern for supports 0.5 and 0.6 relative to ACO-ParaMiner, ACO-GRAANK and ParaMiner. For the other supports ParaMiner extracts the most patterns. In Figure 4.12 (d), UCI data set with 1000 tuples: we observe that ParaMiner extracts the most patterns followed (in order) by GRAANK, ACO-GRAANK and ACO-ParaMiner.

Comparative Computational Experiment: T-GRAANK vs ACO-TGRAANK

The aim of this experiment is to determine which algorithm implementation performs better: (1) T-GRAANK implementation based on GRAANK technique proposed in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] or (2) ACO-TGRAANK implementation based on ACO-GRAANK technique proposed in Section 4.3.2. We applied the Buoys data set on both T-GRAANK and ACO-TGRAANK algorithms in order to compare their performances.

Using the results we obtained, we plot the graphs in Figure 4.13. We mention that at the 15k-line data set the T-GRAANK algorithm exceeded the limit on the total run time we set (3 days) for each job allocation in the HPC node. We observe that the run time performance of ACO-TGRAANK algorithm implementation is better than that of the T-GRAANK algorithm especially for large data sets. From this, we can make the conclusion that the ACO-based technique is more efficient at extracting temporal gradual patterns than classical technique especially when dealing with huge data sets.

Buoys: attributes=11/cpus=28/tuples=3k-15k/min-sup=0.5/min-rep=0.9995

Memory Usage

We observe that ParaMiner and ACO-ParaMiner have higher requirements for memory size than GRAANK and ACO-GRAANK. This phenomenon explains why ParaMiner and ACO-ParaMiner (1) yield Memory Error outputs for relatively large data sets and, (2) have slower runtimes for relatively small data sets. As described in Section 2.2.5, ParaMiner is based on a DFS strategy whose drawbacks (for the case of gradual pattern mining) are as follows:

1. a numeric data set has to be encoded into a transactional data set before DFS can be applied. This significantly increases the size of the data set and consequently size of usage memory required;

2. DFS employs a recursive approach to find all the longest paths. However, we notice from the experiment results that ACO-ParaMiner has improved runtime since it uses a nonrecursive heuristic approach to achieve this.

For the case of GRAANK and ACO-GRAANK, their relatively low memory usages can be largely attributed to the modeling of tuple orders using a binary matrix. However, ACO-GRAANK has higher memory usage requirement than GRAANK since it generates numerous and random maximal gradual items.

Execution Runtime

We observe that generally BFS-based algorithms (GRAANK and ACO-GRAANK) have relatively faster runtimes than DFS-based algorithms. This mainly is due to low memory usage requirements explained in the previous section. We also observe that ACO-GRAANK has relatively faster runtimes than GRAANK because it employs a heuristics approach that learns high quality gradual patterns quicker than the classical level-wise approach.

Extracted Gradual Patterns

It is important to recall from Chapter 2.2.5 that maximal and closed patterns provide the richest knowledge of attribute correlations because such patterns combine all the attributes of the data set that have gradual relationships. Having mentioned that, we observe that generally the number of patterns extracted by ParaMiner is relatively constant against different supports because it searches for all closed patterns (which are more rich in terms of attribute correlation knowledge) [START_REF] Negrevergne | Paraminer: a generic pattern mining algorithm for multi-core architectures[END_REF], while the number of patterns extracted by GRAANK varies significantly with support since it searches for all patterns that surpass the support threshold. However, ACO-GRAANK searches for most maximal patterns (which are fewer but provide more rich knowledge of attribute correlations) and, ACO-ParaMiner searches for most frequent closed patterns.

Summary

In this chapter, we describe an ant colony optimization technique for BFS-based and DFS-based approaches for mining gradual patterns. Given the computational results in Section 4.4, we establish that ACO-GRAANK and ACO-ParaMiner algorithms out-perform classical GRAANK and ParaMiner algorithms and, they mine fewer but high quality maximal and closed patterns respectively. Additionally, we establish that ACO-TGRAANK algorithm implementation which extends the ACO strategy proposed in this Chapter is the best performing algorithm implementation for mining temporal gradual patterns.

"The important thing in science is not so much to obtain new facts as to discover new ways of thinking about them" -William Lawrence Bragg (1890 -1971)

Introduction

In this chapter, we extend temporal gradual patterns to introduce and describe temporal gradual emerging patterns. We propose to extend a border-based manipulation technique to the case of mining temporal gradual emerging patterns. In addition, we extend ant colony optimization strategy described in Chapter 3 to propose a more efficient technique for constructing temporal gradual emerging patterns.

Emerging Patterns

Emerging patterns (EPs) are item sets whose frequency increases significantly from one data set to another. EPs are described using growth rate, which is the ratio of an EP's frequency support in one data set to its frequency support in another data set. For instance, suppose a car shop in 2017 had 200 purchases of {F OG_LAM P S, BAT T E-RY, T Y RES} out of 1000 transactions, and in 2018 it had 500 such purchases out of 1000 transactions. This purchase is an EP with a growth rate of 2.5 from the year 2017 to 2018.

More specifically, an EP is present if its growth rate across data sets is larger than a given specified minimal numerical threshold. EPs can be applied to discover distinctions that exist amongst a collection of data sets with classes such as "hot vs cold", "poisonous vs edible". In other words, EPs are a powerful tool for capturing discriminating characteristics between the classes of different data sets [Dong et al., 1999, Li et al., 2001, Kotagiri and Bailey, 2003].

Mining gradual emerging patterns (GEPs) aims at identifying distinctions between numerical data sets in terms of attribute correlations [START_REF] Laurent | Mining emerging gradual patterns[END_REF]. For instance, given 'windspeed' and 'atmospheric temperature' as attributes of two numerical data sets, a GEP may take the form: "the higher the windspeed, the lower the temperature" with a frequency support of 0.01 in one data set, and "the higher the windspeed, the lower the temperature" with a frequency support of 0.8 in another data set. However, many correlations appear over time, as for instance it is the case when phenomena appear after some meteorological situation due to latency. Many previous works have not taken this into account.

In this chapter, we introduce a new pattern category called temporal gradual emerging patterns (TGEPs), which extends temporal gradual patterns (TGPs), for knowledge discovery in numeric timestamped data sets. It is important to mention that apart from the study presented in Chapter 3, many other research works exist that allow for transformation of a single timestamped data set into numerous data sets based on date-time attribute. Therefore, we may define TGEPs as: temporal gradual item sets whose frequency supports increase significantly between transformed data sets. TGEP mining unearths a new possibility for discovering gradual trends with respect to time in timestamped numerical data sets.

For instance a TGEP may take the form: "the higher the windspeed, the lower the temperature, almost 3 minutes later" with a frequency support of 0.005 in the first transformed data set, and "the higher the windspeed, the lower the temperature, almost 3 minutes later" with a frequency support of 0.75 in the second transformed data set. Most often, apart from the significant increase in frequency support, it may also be possible for a drift of time gap to additionally occur. For instance the second transformed data set may produce the pattern: "the higher the windspeed, the lower the temperature, almost 7 minutes later" with a frequency support of 0.75.

The latter delivers a more meaningful pattern knowledge from the data set, since it may also be interpreted as the amount of time that elapses before/after a temporal gradual item emerges. This pattern has a growth rate of 150 after approximately 4 minutes. Apart from this simple example, numerous real-life timestamped data sets from unrelated sources may be crossed and mined for interesting TGEPs. In spite of this, it should be emphasized that TGEPs are extracted from transformed data sets. As illustrated in Chapter 3.3.1, a timestamped data set may be transformed into numerous data sets each of which can be mined for TGPs.

For this same reason, the complexity of dealing with more than 2 transformed data sets when extracting TGEPs arises. The process of mining all TGPs from each of these data sets and comparing the patterns against each other to identify emerging ones proves to be computationally time-consuming. Consequently, we introduce contributions in the sections that follow that propose and describe 2 more efficient approaches for mining TGEPs.

Preliminary Concepts and Notations

In order to describe TGEPs, we recall the definitions of gradual patterns as given in Chapter 2.2.3. Additionally in this section, we provide some preliminary definitions of emerging patterns (as given by [Dong and Li, 1999, Li and Wong, 2001, Kotagiri and Bailey, 2003]) and gradual emerging patterns (as given by [START_REF] Laurent | Mining emerging gradual patterns[END_REF]).

In the case of emerging patterns, assume a data set D is defined by item set I = {i 1 , i 2 , ..., i n } and it consists of transactions {t 1 , t 2 , ..., t n }. Every transaction is a subset of item set I (as shown in Figure 5.1 (a)). For example, (as illustrated in Figure 5.1) {bread, milk, sugar} is an emerging item set since its frequency occurrence count in transactions (or frequency support) is significantly greater in data set D 2 than in data set D 1 . Definition 5.2. Growth Rate. Growth rate (gr) of an emerging pattern (EP ) is the ratio of frequency support of the pattern in data set D 2 to another data set D 1 . The quality of an emerging pattern is measured by growth rate.

For example, given data sets D 1 and D 2 , the growth rate of item set EP in favour of data set D 2 is given as follows:

gr(EP ) = sup(EP ) D 2 sup(EP ) D 1 (5.1)
Therefore, given a user-specified minimum numerical threshold ρ, a pattern EP is said to be emerging only if:

gr(EP ) ≥ ρ (5.2)
It is important to emphasize that growth rate is derived from frequency support of the involved patterns [Dong and[START_REF] Dong | [END_REF][START_REF] Dong | [END_REF]. Similar to transactional frequent pattern mining, frequency support as a quality measure for extracted patterns also applies to gradual pattern mining. It is for this reason that the concept of emerging patterns can be extended to the case of gradual pattern mining [START_REF] Laurent | Mining emerging gradual patterns[END_REF]. Therefore, a gradual emerging pattern may be defined as follows:

Definition 5.3. Gradual Emerging Pattern. A gradual emerging pattern (GEP ) is a set of gradual item sets whose support sup(GEP ) D g2 > sup(GEP ) D g1 . Where D g is a numeric data set whose attributes hold singleton values/items per transaction (i.e. Table 5.1 in Section 5.3).

For example, GP = {(rain, ↑), (wind, ↑)} is a gradual emerging pattern if support sup(GP ) is significantly greater in data set D g2 than in data set D g1 . It should be underlined that gradual patterns cannot be extracted from data sets whose attributes hold a set of items/values (i.e. Figure 5.1) due to tuple pairing that occurs during extraction.

Temporal Gradual Emerging Patterns

In this section, we seek to describe temporal gradual emerging patterns (TGEPs). We begin by briefly recalling the extraction process of temporal gradual patterns (TGPs) (see Chapter 3 for full description) because an emerging TGP makes up a TGEP. TGP mining extends gradual pattern mining in order to additionally estimate the time lag that may exist between gradual item sets. For instance, a TGP may take the form "the higher X, the higher Y, almost 3 months later".

Example 5.2. Let us consider a data set (D g ) shown in Table 5 The first process in the extraction of TGPs is to transform a timestamped numerical data set step-wisely into a temporal format. This process requires that one attribute be selected as a reference attribute and transformation step be set. For example, (using data set in Table 5.1) if 'rain' is selected as the reference attribute and a transformation step be set at 1; then the data set (D g ) in this table will be transformed into data set (D g ) in Table 5.2 such that:

• every tuple (r n ) of 'rain' attribute is mapped to tuple (r n+1 ) of 'wind' attribute, and It is observable that a transformation step of 1, leads to generation of a transformed data set (D g ) that represents 4 out of the 5 tuples of the original data set (D g ). Therefore, D g has a representativity of 0.8. Representativity (rep) of a TGP is the ratio of tuple size in a transformed data set (D g ) to tuple size in the original data set (D g ). Therefore, given a minimum numerical threshold δ, a T GP is relevant only if:

• date difference is calculated as (r n -r n+1 ).
rep(T GP ) ≥ δ (5.
3)

The second process in the mining of TGPs is to extract gradual patterns from the transformed data set and approximate a time lag associated with the extracted gradual patterns.

As shown above, TGPs are extracted from transformed data sets. The value of the specified minimum representativity (δ) determines the number of transformation steps; consequently, the number of transformed data sets. It may be the case that a particular TGP occurs frequently in more than one transformed data set; as a result, it becomes an emerging TGP. Under those circumstance, we may define a TGEP as follows.

Definition 5.4. Temporal Gradual Emerging Pattern. A temporal gradual emerging pattern (T GEP ) is a set of temporal gradual patterns that appear more frequently in one transformed data set D g and less frequently in another transformed data set D g .

Border-based Discovery of TGEPs

In this section, we propose an approach that exploits border manipulation for extraction of TGEPs. First, we describe how border manipulation technique may be applied to the case of frequent item sets and gradual item sets. Finally, we propose to extend it to the case of temporal gradual item sets.

Border Representation of Frequent Item Sets

The border-based approach was introduced by [Dong and Li, 1999] and it offers condensed representation and efficient manipulation of large interval closed item sets. In considerations of clearly describing the border-based approach for discovery of TGEPs, we formalize the notion of intervalclosed sets and provide the definition of a border as given by [Li et al., 2001, Dong and Li, 1999, Dong et al., 1999, Laurent et al., 2015].

Property 5.1. Interval Closed Sets. Collections of sets C are said to be interval closed if: ∀X, Z ∈ C; ∀Y such that X ⊆ Y ⊆ Z, it also holds that Y ∈ C. Such sets are also referred to as convex sets.

Definition 5.5. Border. A border is an ordered pair < L, R >, (where L -left-hand bound of the border and R -right-hand bound of the border) if: (a) each of L and R is an antichain1 collection of sets, and (b) each element of L is a subset of some element in R and each element of R is a superset of some element in L.

For example, a collection of sets [L, R] may be represented by (or is said to have) a border

< L, R >, where [L, R] = {Y | ∃X ∈ L, ∃Z ∈ R such that X ⊆ Y ⊆ Z}.
For the purpose of relating Property 5.1 to Definition 5.5, [Dong and Li, 1999] presents three main propositions: (a) the collection of all large item sets with respect to a minimum threshold (σ) is interval closed, (b) each interval-closed collection C of sets has a unique border < L, R >, where L is the collection of minimal item sets in C and R is the collection of maximal item sets, and (c) the collection of large item sets with respect to a minimum threshold (σ) in a data set has a left-rooted border.

To clarify, a border < L, R > is called left-rooted if L is a singleton set (i.e. the left-hand bound is {∅} and its right-hand bound is the collection of maximal item sets) and it is right-rooted if R is a singleton set. As a result of these propositions, [Dong and Li, 1999] illustrates that an efficient maximal set pattern mining algorithm (i.e. Max-Miner) may be used to extract collections of large item sets from data sets which in-turn provide left-rooted borders for each data set with respect to a minimum support threshold.

All in all, [Dong and Li, 1999] demonstrates how an efficient discovery of left-rooted borders from two data sets (i.e. D 1 and D 2 ) through Max-Miner algorithm, followed by a repetitive border differential procedure (implemented as BORDER-DIFF algorithm) on the two borders allows for extraction of emerging patterns. The overall algorithm is known as MBD-LLBORDER algorithm.

Border Representation of Gradual Item Sets

It should be noted that the MBD-LLBORDER algorithm cannot be applied directly to the case of gradual item sets, since the nature of gradual item sets is slightly different from that of classical frequent item sets. Unlike frequent item sets, (in terms of tuple transactions and gradual items) gradual item sets in both cases deal with pairs and not singletons. We demonstrate this in Chapter 2.2.

As demonstrated in Section 2.2: (a) deriving the frequency support of a gradual pattern involves ordering tuples in concordant pairs; and (b) discovering any meaningful correlation knowledge among attributes of a data set involves extracting non-trivial gradual patterns composed of at least 2 gradual items. It should be remembered that the border representation of large item sets presented by [Dong and Li, 1999] (see Section 5.4.1) is most suitable for classic frequent item sets that are each composed of singleton items.

For example, in the classic item set case a 4-length pattern {A, B, C, D} may fully be decomposed into its 4 items: {A}, {B}, {C}, {D}. In the gradual item set case a 4-length pattern {(A, ↑), (B, ↓), (C, ↑), (D, ↓)} at best may be decomposed into its 6 gradual items: {(A, ↑), (B, ↓ )}, {(A, ↑), (C, ↑)}, {(A, ↑), (D, ↓)}, {(B, ↓), (C, ↑)}, {(B, ↓), (D, ↓)}, {(C, ↑), (D, ↓)}.

Nevertheless, [START_REF] Laurent | Mining emerging gradual patterns[END_REF] identifies two properties of gradual patterns that allow for border representation of gradual patterns. They are: (a) a collection of frequent gradual patterns is interval-closed, and (b) a collection of frequent gradual patterns may be represented as a left-rooted border < {∅}, R >, where R is the set of maximal gradual item sets in the collection broken down into gradual items of length 2.

With reference to the first identified property of gradual patterns, it derives explicitly from anti-monotonicity feature of gradual patterns. The anti-monotonicity property states that: "no frequent gradual pattern containing n items can be built over an infrequent gradual pattern containing a subset of these n items." For instance, if a maximal gradual pattern {(A, ↑), (B, ↓ ), (C, ↑)} is frequent (support surpasses the minimum specified threshold), then all subsets of this pattern are also frequent [Di Jorio et al., 2008, Owuor et al., 2019].

With reference to the second identified property of gradual patterns, it derives from pairings that come with mining non-trivial gradual patterns. Consequently, [START_REF] Laurent | Mining emerging gradual patterns[END_REF] proposes a subsequent representation of maximal gradual item sets into its smaller gradual items of length 2. That is to say, a maximal gradual pattern of length k may be re-represented by a set of k(k -1)/2 gradual items of length 2.

Border Representation of Temporal Gradual Item Sets

Temporal gradual patterns (TGPs) (as described in Section 5.3) are simply gradual patterns that have been improved to indicate an estimated time lag among the gradual item sets. In fact [Owuor et al., 2019] presents T-GRAANK approach which extends the GRAANK approach (presented in [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] for mining gradual patterns) for mining TGPs.

It should be clarified that the distinctive feature of approximated time lag of TGPs is majorly introduced by the data set transformation process. As an advantage, the transformation process allows for generation of multiple transformed data sets from the original timestamped data set using a specified representativity threshold [Owuor et al., 2019]. The novel idea of harnessing this process so as to mine a single data set for emerging TGPs (or TGEPs) is quite interesting. In fact, we propose Algorithm 7, BT-GRAANK stands for MBD-LLBORDER Temporal GRAdual rANKing. 1. Build multiple transformed data sets D g , D g , ..., D * g from a timestamped data set D g from a specified representativity threshold δ (see Section 5.3).

2. Extract all TGPs from each transformed data set with a specified support threshold σ.

Construct border representations of all maximal

TGPs from the transformed data sets as described in Section 5.4.2.

4. Apply a modified MBD-LLBORDER algorithm (using modified a union operator) to the borders obtained in Step 3 (two borders at a time).

It is important to note that this border-based strategy is an efficient technique for mining TGEPs; however, the search space grows exponentially with respect to the number of attributes [START_REF] García-Vico | An overview of emerging pattern mining in supervised descriptive rule discovery: taxonomy, empirical study, trends, and prospects[END_REF], Owuor et al., 2019]. Therefore, this strategy is not suitable for discovering patterns in huge data sets.

• In a given valid solution, each gradual item set is used to update the corresponding artificial pheromone p a,j (t) (where j is either + or -) using Equation (5.5).

• Again using the same valid solution, for every attribute that does not have a gradual item set appearing in the solution -we update the corresponding irrelevant pheromone p a,j (where j is ×) using Equation (5.5).

p a,j (t) = p a,j (t) + sup(Sol) (5.5) where sup(Sol) is the frequency support of the generated pattern solution

It should be highlighted that the proposed modification only affects Equation (5.5). Previously in Chapter 4.3.1 pheromone p a,j is incremented by 1; here, it is incremented by sup(Sol).

It is important to point out that as long as pheromones are incremented, the ACO technique effectively learns how to generate highly probable gradual item set candidates. However, since the value of sup(Sol) is always less than 1; the ACO technique takes a little longer to converge, consequently slightly reducing its efficiency.

Equally important, the proposed modification allows for accumulation of the frequency supports of validated temporal gradual patterns. Therefore, matrix T a,j may also be referred to as support-based pheromone matrix. We exploit this matrix for constructing TGEPs in the section that follows.

Growth-rate Manipulation for Mining TGEPs

It should be noted that applying the proposed ACO-based approach on a data set extracts numerous GPs or TGPs, but only one pheromone matrix for every data set or transformed data set respectively (see Equation (5.4)). As illustrated in the Section 5.5.1, the values of the matrix depend on the patterns extracted since each valid pattern increments it by its support (see Equation (5.5)). In that case, a single matrix cumulatively stores support values of all extracted patterns. The matrix can be normalized using the number of algorithm iterations determined by the convergence property.

The definitions given in Section 5.2 about emerging patterns (EPs) and their growth-rate validates the idea that: if two data sets each provide its support-based pheromone matrix, then dividing the two matrices element-wisely generates a growth-rate matrix. Through division, the growth-rate matrix reduces any irrelevant EPs to zero but allows for construction of relevant EPs. To this end, there exists no reason to keep the gradual patterns previously extracted. In this chapter, our main aim is to extend the ACO strategy to the case of TGEP mining and compare its performance to the border-based strategy. Although mining TGPs using an ACObased approach is easily achievable (see Section 5.5.1), constructing TGEPs from growth-rate matrices is difficult since the matrices do not provide information about associated time-lags. For this reason, we propose an additional time-lag matrix which is updated with approximated time-lags of validated patterns every time the pheromone matrix is updated with support values of these patterns. Finally, the combined content of the growth-rate matrix and the time-lag matrix allow for the construction of TGEPs.

Example 5.4. Let T GP 1 = {(Rain ↑ , W ind ↓ ) ≈+2mins , sup = 0.8} be extracted from a transformed data set D g , and T GP 2 = {(Rain ↑ , W ind ↓ ) ≈+6mins , sup = 0.4} be extracted from a transformed data set D g . Figure 5.4 shows the support pheromone matrices and the corresponding time-lag matrices for the transformed data sets. 2. From each transformed data set, build a normalized support pheromone matrix along with corresponding time-lag matrices.

3. Generate growth-rate matrices from the pheromone matrices obtained in Step 2 (two pheromone matrices at a time).

4. Combine each growth-rate matrix with the two corresponding time-lag matrices to construct TGEPs.

Experiments

In this section, we implement the border-based BT-GRAANK algorithm (described in Section 5.4) and the ant-based TRENC algorithm (described in Section 5.5) for mining TGEPs and analyze their computational performances. All experiments were conducted on a (High Performance Computing) HPC platform Meso@LR2 . We used one node made up of 112 cores and 128GB of RAM.

Source Code

The Python source code of our proposed algorithms are available at our GitHub repository: https://github.com/owuordickson/trenc.git.

Data Set Description

Table 5.3 shows the features of the data sets used in the experiments for evaluating the computational performance of our proposed algorithms. The 'Power Consumption' (UCI) data set, obtained from UCI Machine Learning Repository [Dheeru and Karra Taniskidou, 2017], describes the electric power consumption in one household (located in Sceaux, France) in terms of active power, voltage and global intensity with a oneminute sampling rate between December 2006 and November 2010.

The 'Directio' data set is one of 4 data sets obtained from OREMES's data portal3 that recorded swell sensor signals of 4 buoys near the coast of the Languedoc-Roussillon region in France between 2012 and 2019 [Bouchette, 2019]. These data sets can be retrieved from: https: //github.com/owuordickson/trenc/tree/master/data.

Experiment Results

In this section, we present the results of our experimental study on the two data sets (described in Section 5.6.2) using our proposed algorithms with a minimum growth-rate threshold ρ = 1.0. These results reveal that the two algorithms behave differently when applied on different data sets (especially if they vary in number of attributes). We use these results to analyze and compare the computational efficiency and parallel efficiency of the algorithms as presented in Section 5.6.3 and Section 5.6.3 respectively. We discuss these results in Section 5.6.4. All the experiment results can be obtained from: https://github.com/owuordickson/meso-hpc-lr/ tree/master/results/tgeps/112cores.

Comparative Experiments: computational efficiency

This experiment compares the run-time and number of temporal gradual emerging patterns (TGEPs) extracted by TRENC and BT-GRAANK from data sets UCI and Directio. We mention that the minimum representativity threshold is set at 0.99 so that very few transformations are applied on the original data sets, which improves the quality of TGEPs (see Section 5.3). 5.6 (a) shows run-time and, Figure 5.6 (b) shows the number of TGEPs extracted by TRENC and BT-GRAANK algorithms when applied on the UCI data set. We observe that the run-time of BT-GRAANK (blue curve) is lower than that of TRENC (red curve) and it reduce significantly (as well as the number of TGEPs) as support threshold is increased. For the case of TRENC, the run-time and number of TGEPs are almost constant. It should be remembered that support threshold plays an important role in determining the quality and quantity of extracted frequent patterns (see Chapter 2.2). The higher the threshold, the higher the quality of the patterns; consequently, trivial patterns are ignored. This explains why the run-time and number of TGEPs reduce significantly for the case of BT-GRAANK. Concerning TRENC, it is based on ACO strategy (see Chapter 4.3.1) which mines for maximal patterns first. For this particular case, it may seem that the maximal patterns mined are of high quality; therefore, it seems that the support threshold has little effect on the quantity of TGEPs.

Comparative Experiments: parallel efficiency

This experiment compares the run-time of BT-GRAANK and TRENC algorithms against different number of CPU cores on data sets UCI and Directio. In Figure 5.8, the run-time of both algorithms reduce as the number of cores increase. We use these results to analyze their multiprocessing behavior using the speedup and parallel efficiency performance measures. (1) Speedup S(n) may be defined as: "the ratio of the execution time of a single processor to the execution time of n processors" (S(n) = T 1 /T n ).

(2) Parallel efficiency E(n) may be defined as: "the average utilization of n processors" (E(n) = S(n)/n) [START_REF] Eager | Speedup versus efficiency in parallel systems[END_REF]. In Figure 5.9 (a), we observe that BT-GRAANK (in comparison to TRENC) has a highest Speedup and, in Figure 5.9 (b) has a highest parallel efficiency when both are applied on the UCI data set. Again, in Figure 5.10 (a), we observe that BT-GRAANK (in comparison to TRENC) has a highest Speedup and, in Figure 5.10 (b) has a highest parallel efficiency when both are applied on the Directio data set. However, it should be observed, from Figure 5.8 (b), that the run-time of BT-GRAANK is higher than that of TRENC on data set Directio.

Directio data set: #attributes=21/#tuples=6K/min-rep=0.99/min-sup=0.8 In this section, we present the consistent TGEPs (see Section 5.3 for Definition) extracted from the two data sets described above.

Computation Run-time Complexity

Unlike BT-GRAANK, we observe that the run-time for TRENC on both data sets is almost constant. As described in Section 5.5.1 is based on a heuristic technique for efficiently generating maximal gradual item sets. Therefore, the run-time required for extracting patterns through this technique is determined by how long the pheromone matrix takes to converge. Again, this property enables TRENC to have a lower run-time than BT-GRAANK (see Section 5.4.3) when executed on a data set with a large number of attributes. For example since data set Directio has more attributes than data set UCI, there is a significant increase in run-time for the case BT-GRAANK and a relatively small change for the case of TRENC (see Figure 5.6 (a) and Figure 5.7 (a).

Finally, we observe that BT-GRAANK has a higher Speedup and parallel efficiency than TRENC for both data sets as shown in Figure 5.9 and Figure 5.10. Majorly, this is due the fact that TRENC's run-time is almost constant despite the variations in support threshold and number of cores. This implies the advantage that TRENC can extract high quality TGEPs using few processors and at any support threshold.

Extracted TGEPs

We observe that BT-GRAANK extracts more TGEPs than TRENC from the UCI data set. It should be emphasized that BT-GRAANK identifies borders from two maximal items. For this reason, numerous borders are used to construct few TGEPs (see Section 5.4.3). In fact, we discover that both algorithms identify similar consistent TGEPs from the UCI data set as shown in Table 5.4.

"You must stay drunk on writing so reality cannot destroy you" -Ray Bradbury, Zen in the Art of Writing

Introduction

In this chapter, we propose and describe a fuzzy model for crossing unrelated time-series data sets with the ultimate goal of exploiting them for temporal gradual pattern mining. By using a fuzzy model, our proposed approach becomes more robust than other crisp models that could miss a phenomenon because of small data variations. We develop an algorithm that implements our proposed model and we test it on real data. In addition, we apply parallel processing on the algorithm implementation and measure its computational performance. We specifically test our model on numeric time-series data sets so as to extract temporal gradual patterns afterwards.

Crossing Time-series Data

Today, with the proliferation of Internet of Things (IoT) applications in almost every area of our society comes the trouble of deducing relevant information from real-time time-series data (from different sources) for decision making. A possible solution to this may be data crossing. We recall the definition of data crossing given in Section 2.4 as "a process that enables the matching of different data sets using a pre-defined criteria and combining their data points to form a new data set". Figure 6.1 illustrates the process of crossing two time-series data sets to form one data set through a fuzzy model. The date-time attribute reveals how closely simultaneous the occurrence of data points of the 2 data sets are. For example, time-series data sets having most of their data points occurring at almost the same time, when crossed, yield a data set that maps almost all the data points of the individual sets.

In this example, we notice that there exists a degree of fuzziness for any time interval that matches respective tuples in both data sets. For instance if we use a triangular membership function and we pick '1200 hours' as the center of this function -the membership degrees (MDs) of humidity data set's 'time' attribute may be approximated as: {(1200, 1.0), (1202, 0.8), (1204, 0.6), (1208, 0.4), (1208, 0.2)}.

Similarly, the MDs of the number of flies data set's 'time' attribute may be approximated as: {(1201, 0.9), (1202, 0.8), (1203, 0.7), (1204, 0.6), (1205, 0.5)}. Therefore, for any center that we pick between '1200 hours' and '1208 hours', the MD in the population of time attribute decreases from closest value to the furthest value. This interesting (MD) feature can be harnessed and applied on a fuzzy model that may cross time-series data from different sources. We describe this model in the section that follows.

Building the Fuzzy Model

In this section, we construct a fuzzy model for crossing time-series data sets from different sources. We cross them with the intention of extracting temporal gradual patterns.

In Fuzzy sets theory, there exists a great number of membership functions that one can apply on a data set for fitting purposes [Zadeh, 1965, Ayouni et al., 2010, Nath Mandal et al., 2012]. In this chapter, we pick a triangular membership function (MF) so that we can order the MDs of date-time population with reference to a single-value center. Automatically, this eliminates any MF whose center includes more than one value.

It is important to mention that we pick a triangular MF over the Gaussian MF since it is simpler to implement and, moreover our interest is not in fitting the data set perfectly [Nath Mandal et al., 2012]. For instance, it is easy to construct an initial triangular MF for the date-time population of each time-series data by using the minimum value as the center and the smallest difference in the population to calculate the minimum and maximum extremes as shown in Figure 6 As an illustration, we apply the pseudo-code steps on the data sets in Table 6.1 (a) and (b) to obtain the data set in Table 6 Having crossed the 2 data sets, it is possible to apply gradual pattern mining techniques especially T-GRAANK (Temporal GRAdual rANKing) (see Chapter 3.3) to extract the gradual correlation between humidity and population of flies. For instance a relevant pattern may be: {(humidity, ↑), (f lies, ↑) ≈+2mins } which may be interpreted as "the higher the humidity, the higher number of flies, almost 2 minutes later".

FuzzTX Algorithm

In this section, we present Algorithm 9 which implements the FuzzTX model described in Section 6.2.1. In this algorithm, we first extract the date-time values from each time-series data set and store them in individual arrays (line 4). The smallest difference between elements in each date-time array is added to the boundary array B (line 8). This array is used to determine the boundaries of the MF (line 10). Next, we build a triangular MF that initially starts from the smallest date-time value and it is positively slid by a specific boundary until it is equal to the largest date-time value (line 13). Finally, the for-loop implements the pseudo-code, described in Section 6.2.1, to determine the tuple indices of each data set that has the largest MD. The indices are used to cross data sets (line 24).

Experiments

In this section, we analyze the efficiency of FuzzTX algorithm and discuss its performance results. It is important to mention that we implemented the algorithm using Python language in order to benefit from the language's dynamism especially when dealing with large data sets.

Source Code

The Python source code for our FuzzTX algorithm is available at our GitHub repository: https: //github.com/owuordickson/data-crossing.git.

Computational Complexity

We apply the Big-O notation to determine the limiting behavior of the FuzzTX algorithm as the number and size of the time-series data sets increase [START_REF] Vaz | Automated Big-O analysis of algorithms[END_REF], Bae, 2019]. A part from the control structures (i.e. for-loop, while-loop and if-statements), we assume that the computational complexity of other statements are relatively constant and they are denoted as C. This is because the average time taken to execute these statements is approximately equal in every repetition.

The FuzzTX Algorithm 9 has: 2 for-loop statements, 1 while-loop statement and 2 if statements. If we let n denote the number of time-series data sets and x denote the number of tuples in the data set with the largest date-time difference, then we approximate the asymptotic time complexity as: 2nxC + nx 2 C. This is because the first for-loop iterates through all the tuples of each data set in order to build the T arr .

The while-loop approximately increments its boundaries as many times as the number of tuples of the data set with the largest date-time difference and each time it iterates through all the tuples of each data set. Therefore, the upper bound is slightly higher than O(nx 2 ). This implies if the number of time-series data sets are few, the computational time performance of the FuzzTX algorithm is almost proportional to the square of its input size.

Parallel Multiprocessing

We analyze the multiprocessing behavior of the FuzzTX algorithm using the speedup and parallel efficiency performance measures.

Experiment Results

In this section, we present results of our experimental study on 2 data sets obtained from OREME data portal. We show the computational performance results and the parallel performance results. All the results of our test runs are available at our GitHub link: https://github.com/ owuordickson/meso-hpc-lr/tree/master/results/fuzztx. We also show the results of a use case example when the crossed data set is mined for gradual patterns.

Computational Performance Results

In order to deduce the computational time efficiency of FuzzTX algorithm, we apply the algorithm on the Puéchabon data set. In Figure 6.3, run time increases with increase in both the number of data sets and the number of the data sets' tuples. For the purpose of getting a clearer picture of the algorithm's computational performance, we plot axes shown in Figure 6.4 (a) and (b). As can be observed the growth rate of run time is almost linearly proportional to the growth rate of the data set size. This linear growth rate performance is better than the deduced performance in Section 6.3.2 which implied a quadratic growth rate.

In order to test the parallel efficiency of the FuzzTX algorithm, we applied the algorithm on the Buoys data sets and we use the results to plot Figure 6.5 and Figure 6.6. Figure 6.5 shows the overall behavior of the FuzzTX algorithm when we apply parallel processing. Generally, run time decreases as the number of cores increase from 1 to 28. -Wernher von Braun (1912-1977)

Introduction

In this chapter, we describe a software architecture model that integrates two algorithm implementations: (1) the fuzzy data crossing algorithm implementation described in Chapter 6 and (2) the temporal gradual pattern mining algorithm implementation described in Chapter 3 into a Cloud platform which implements OGC SensorThings API. We build the model on top of the SensorThings API in order to exploit the time-series data sets it manages for extraction of temporal gradual patterns.

Gradual Pattern Mining Tools on Cloud

Scientific researchers are constantly collecting, crossing and analyzing data in order to help them understand various phenomena. For example environmental data is important for helping to understand phenomena like global warming, typhoons, rainfall patterns among others; biological data is important for helping to understand phenomena like cancer cells, Ebola virus among others. Most of such data is collected using sensors that are enabled to upload data into Cloud platforms [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF][START_REF] Hajj-Hassan | Exploiting interand intra-base crossing with multi-mappings: Application to environmental data[END_REF], Joshi and Simon, 2018].

Temporal gradual pattern mining is an instance of a data analysis technique that allows for extraction of gradual correlations among attributes of a data set. For instance given a data set with attributes {A, B}, a temporal gradual pattern may take the form: "the more A, the less B almost 6 days later". Under those circumstances, it comes as no surprise that temporal gradual pattern mining algorithms are largely applied on time-series data sets.

Again, this research study advocates the view that different time-series data sets may be crossed with the aim of exploiting the crossings for extraction of temporal gradual patterns. This allows for identification of interesting correlations among time-series data sets from different sources which otherwise would have been difficult to retrieve from the individual data sets [START_REF] Hajj-Hassan | Exploiting interand intra-base crossing with multi-mappings: Application to environmental data[END_REF]. For example, let us assume that a researcher has: (1) set up an IoT-based data collection station which has numerous sensors monitoring different environmental phenomena (such as temperature, humidity, wind speed) and ( 2) a time-series data set that records the population of birds in same geographical location.

If the researcher uses a Cloud platform to store all the time-series data sets, then it would be very convenient as well to integrate a time-series data analysis tool into the Cloud platform. The existence of the tool in the Cloud platform saves the researcher the trouble of retrieving, cleaning and preparing the raw time-series data for analysis on an offline software. This is because the tool allows for data analysis within the same Cloud platform that stores the data. It is for such a similar reason that we propose in this chapter a software model that allows crossing of time-series data for the purpose of exploiting the crossings for temporal gradual pattern mining.

The motivation of the study emerges from the proliferation of IoT in research institutions and with this, comes the provision of large-scale time-series data from different sources. Timeseries data can also be defined as a data stream when it becomes a potentially infinite sequence of precise recorded over a period of time [START_REF] Pitarch | Summarizing multidimensional data streams: A hierarchy-graph-based approach[END_REF]. As a result of this proliferation, frameworks such as OGC SensorThings have emerged to allow for (FAIR) Findable, Accessible, Interoperable and Reusable time-series data [START_REF] Liang | OGC SensorThings API part 1: Sensing[END_REF][START_REF] Hajj-Hassan | Integrating sensor data using sensor observation service: Towards a methodology for the o-life observatory[END_REF]. We implement our proposed model on top of the OGC SensorThings API because, to the best of our knowledge, it stands out as the best API to interconnect IoT devices, sensor data and applications over the Cloud. As shown in Figure 7.2, the proposed software model is composed of 5 items described below. (1) OGC SensorThings Service exposes the document resources of the 8 entity sets (we explain them in Section 2.5) for the SensorThings clients. This is the core task of the SensorThings API since every CRUD (Create, Read, Update, Delete) operation goes through it. The GOST Server implements the OGC SensorThings API and it provides the OGC SensorThings Service. It is implemented using Google's Go language (golang).

(2) Data Collection Tool implements MQTT protocol which is a lightweight publish/subscribe protocol designed for constrained devices. This tool is used to connect to sensors in order to collect data from the environment and send them to OGC SensorThings Service. The Mosquitto Server provides the Data Collection services. It is implemented on Mosquitto which supports an MQTT broker that allows sensors to publish their data into the system.

(3) Data Storage Tool serves an object-relational database which implements the schema of the 8 OGC SensorThings sensing entities. This tool provides storage services for all the timeseries data collected by the sensors. The GOST Database Server provides the Data Storage services. It is implemented on top of PostGIS which is a spatial object-relational database software that supports PostgreSQL language. This server stores all the real-time sensor data collected in form of Observations which belong to Datastreams.

(4) Data Crossing Tool serves a HTTP Dashboard Server which enables users to interact with our system. Through this tool users are able to send HTTP requests to the OGC SensorThings Service and the Pattern Mining tool. Equally important, this tool integrates the fuzzy data crossing algorithm described in Chapter 6 into this software model. The Dashboard server is implemented using Angular.js which creates all the HTML views and it is served by NGINX (engine x) to enable users to interact with the system.

(5) Pattern Mining Tool (implemented by GRAANK server) serves the gradual pattern mining algorithms which are variants of the T-GRAANK technique described in Chapter 3 and are implemented in Python. This tool runs services that receive HTTP P OST requests from the Data Crossing tool and responds with the extracted patterns. The GRAANK Server provides the Pattern Mining services. It is implemented using Python and deployed with uWSGI2 server which enables it to accept HTTP POST requests forwarded by the Dashboard Server and respond with extracted temporal gradual patterns.

The uWSGI is a software application named after Web Server Gateway Interface (WSGI) plugin which supports the uwsgi protocol, and it is popularly used to serve Python web applications since it offers multiprocessing capabilities and efficient usage of computing resources. The GRAANK Server exploits these benefits to improve the performance of gradual pattern mining algorithms.

Benefits of Integrating Pattern Mining Tools into Cloud

It is important to highlight that the pattern mining tool enables the access of gradual pattern mining algorithms through a SaaS (Software-as-a-service) model. In a SaaS distribution model, software is centrally hosted and licensed on a subscription basis. This introduces a flexibility that spares users the agony of spending hours trying to install analysis software [START_REF] Joshi | Sentiment Analysis Tool on Cloud: Software as a Service Model[END_REF].

The Data Crossing Tool allows the user to select multiple data streams to cross them to form a single data set from which the Pattern Mining Tool is employed to extract temporal gradual patterns. For instance the user can cross a "temperature" data stream with a "no. of bees" data stream to test for a pattern like: "the higher the temperature, the higher the population of bees almost 3 days later". As can be noted, all these tools are executed on top of a Docker Cloud platform meaning that the user can access the services from any terminal device that has Internet connection (i.e. computer, smartphone, tablet among others). Figure 7.3 shows the web implementation of this software model.

With regard to Chapter 3 the computational complexity of mining temporal gradual patterns increases with the size of the data set. For this reason, the algorithms are implemented in Python language in order to harness Python's ability to improve efficiency through multi-core parallel processing. As a result, we argue that a SaaS model is best suited for offering gradual pattern mining tools to users since they are installed on one powerful mainframe which may be accessed on a subscription basis.

The proposed software model enables a Python implementation of these algorithms on a single server and also provides a user-friendly HTTP API for access. Again, the Cloud implementation of the proposed software model allows for a configuration setting that limits access of these tools to a subscription basis. Further, usage analytics may also be easily generated since every user request and operation is recorded in log files. These analytics may be used to improve user experience or identify and fix software bugs. The entire source code for this work is available at our GitHub repository: https://github. com/owuordickson/cloud-api.git. The GRAANK Server image is available at our Docker repository: https://hub.docker.com/r/owuordickson/graank:ogc. OREME complies with INSPIRE4 Implementing Rules which requires that common frameworks are implemented by member research institutions in order to ensure that collected spatial data is made FAIR (Findable, Accessible, Interoperable and Reusable). Therefore, it currently implements in its data portal5 OGC geospatial standards like WFS (Web Feature Service) and WMS (Web Map Service) which standardizes the creation, modification and exchange of geographic information over the Internet.. However, OREME has not yet implemented data stream standards like the OGC Sensor-Things API into its data portal due to data entity incompatibility. One solution may involve installing IoT sensors at the data collection stages, which integrate into an MQTT instance to generate compatible data streams [START_REF] Grellet | Workshop: Integration of O&M data in the INSPIRE SDI -Benefits, challenges and prospects[END_REF], Kotsev et al., 2018].

Summary

In this chapter, we propose and develop a software architecture model that allows gradual pattern mining algorithms to be accessed over a Cloud platform. This allows for these algorithms to be applied on real-time sensor data that is collected over the Cloud through frameworks such as the OGC SensorThings. In future, we intend to implement the proposed software model into the OREME's data portal.

Chapter 8

Conclusions and Perspectives

Summary

This research study mainly addresses the aspect of mining temporal gradual patterns and the integration of gradual mining techniques into a cloud platform. We summarize the main contributions made by this study in field of knowledge discovery and data mining through points that follow:

• We reviewed literature concerning two existing gradual pattern mining techniques: GRITE and GRAANK. We discover that: (1) both techniques apply a breadth-first search strategy in order to generate gradual item set candidates and ( 2) both strategies do not address the question of additionally extracting the temporal tendencies of gradual patterns.

• We introduce and propose formal definitions of temporal and fuzzy-temporal gradual item sets and temporal gradual emerging pattens.

• We describe an ant colony optimization technique for breath-first search-based and depthfirst search-based approaches for mining gradual patterns. Given the computational results in, we establish that ACO-GRAANK and ACO-ParaMiner algorithms out-perform classical GRAANK and ParaMiner algorithms and, they mine fewer but high quality maximal and closed patterns respectively.

• We propose and describe T-GRAANK approach that is an extension of the GRAANK approach. The T-GRAANK approach allows for extraction of temporal gradual patterns through a fuzzy model. We establish that ACO-TGRAANK which is based on the ACO-GRAANK approach offers a better computational run time performance than T-GRAANK which based on the classic GRAANK technique.

• We propose and describe two approaches for mining temporal gradual emerging patterns:

(1) an ant colony optimization approach and, (2) a border manipulation approach. We develop algorithm implementations for both approaches: TRENC and BorderT-GRAANK respectively. We compare the computational performance of both algorithm implementations and establish that TRENC is the more efficient algorithm.

• We propose and describe FuzzTX approach that allows for crossing of time-series data sets from different sources through a fuzzy model. We show that through the FuzzTX approach, it is possible to cross unrelated time-series data sets and mine for temporal gradual patterns.

• Finally, we propose and describe a software model architecture that allows for integration into a Docker Cloud platform that implements the OGC SensorThings API: (1) the FuzzTX data crossing algorithm implementation and (2) temporal gradual pattern mining algorithm implementations. In addition to the Cloud platform, we develop a Desktop and Web application that allows users to upload numeric data sets in CSV format then it may extract gradual patterns, or temporal gradual patterns, or emerging patterns. A screenshot of this application is shown in Figure 8.1. We provide installation instructions about all our software tools in Appendix A.

Perspectives

In consideration of the contributions made by this work in the field of knowledge discovery and data mining, we present the following research perspectives which can be taken as future research directions.

Further Efficiency Optimization of Gradual Pattern Mining Technique

In Chapter 4, we propose and describe an ant colony optimization strategy for optimizing the efficiency GRAANK (GRAdual rANKing) which is a classical gradual pattern mining technique proposed by [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF]. Ant colony optimization is a general purpose heuristic approach mainly used to optimize combinatory problems [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF]. For the reason that generation of gradual item set candidates may be represented as a combinatory problem (especially when dealing with data sets that have large numbers of attributes), we extend an ant colony optimization strategy to the case of gradual pattern mining in order to provide a solution to this problem.

In Chapter 4.2 We fully describe an ant colony optimization approach for the case of gradual pattern mining and temporal gradual patten mining, and develop an algorithms: ACO-GRAANK and ACO-TGRAANK respectively. We test and compare the computational performance of these two algorithms to their classical counterparts GRAANK and T-GRAANK (Temporal-GRAANK proposed in Chapter 3). We establish that the ACO-based algorithms significantly outperform their classical counterparts in terms of computational run-time efficiency.

However, we observe that as the size of the data set increases by number of tuples; the computational run-time efficiency of the ACO-based algorithms reduces. Although the situation is relatively worse in the case of the classical gradual pattern mining algorithms, it is significant enough to draw attention. It should be remembered that the frequency of a gradual pattern is determined by number of tuple pairs or size of tuple orders, and many classical gradual pattern mining techniques employ a bitmap representation for capturing tuples pairs/orders that respect a gradual pattern.

As described in Chapter 2.2.6, bitmap representation allows for the modeling of a gradual pattern as a n × n binary matrix (where n is the total number of tuples in a data set). In the matrix, tuple pairs that respect a pattern are set to 1, and tuple pairs that do not respect the pattern are set to 0. For example given the data set in Table 8.1 (which has 4 tuples), a gradual pattern "the lower the temperature, the higher the humidity" (denoted as {(temp, ↓), (hum, ↑)}) may be represented as a 4 × 4 matrix as shown in Figure 8.2. r1 r2 r3 r4 r1 0 1 1 1 r2 0 0 1 1 r3 0 0 0 0 r4 0 0 0 0 Under those circumstances, it should be observed that tuple-size of a data set directly determines the sizes of binary matrices of its patterns. Therefore, the computational complexity that is introduced by the size of binary matrices negatively affects the efficiency of the gradual pattern mining technique as the tuple-size of the data set increases.

With regard to the points given above, future works may involve proposing approaches for optimizing gradual pattern mining techniques by reducing the size of binary matrices needed to represent respective gradual patterns. One such approach may extend a heuristic technique that constructs a binary matrix which carries only significant representation knowledge of a gradual pattern using a randomly selected portion of the tuple pairs. As a result, tuple pairs with less significant representation knowledge do not form any part of the binary matrix. If a portion of few tuples are selected to successfully represent frequent gradual patterns then, the computational complexity may be reduced to a constant regardless of the size of the data set.

Memory Limitation

In Chapter 4.4.3, we observe from the experiment results that ParaMiner and ACO-ParaMiner algorithms yield Memory Error when applied on slightly large data sets. GRAANK and ACO-GRAANK algorithms perform relatively better in terms of memory usage; however, they also yield Memory Error when applied to BigData. As mentioned in the previous section, these algorithms rely on a technique that represents tuple gradual relationships in the form of binary matrices. This implies that the greater the number of tuples in a data set, the larger the size of the binary matrices that is stored in primary memory. As result, this introduces a memory limitation on these algorithms (GRAANK, ParaMiner, ACO-GRAANK, ACO-ParaMiner) that undermines their computational efficiency.

Concerning the memory limitation, we propose as future works a more efficient data format for dealing with huge binary matrices that may be constructed from BigData. Version 5 of Hierarchical Data Format (HDF5) is an instance of a high performing data software library that allow for management, processing and storage of BigData. Another advantage of HDF5 is that it allows for execution of Map-Reduce jobs. Map-Reduce is a program model that employed on BigData which performs filtering and sorting operations on a Map phase and summary operations on a Reduce phase. In the case of gradual pattern mining, the Map phase may identify all gradual relationships between tuples and the Reduce phase may summarize the relationships into a binary matrix with an efficient HDF5 data format.

Detecting Interesting Data Crossings

In Chapter 6, we propose and describe an approach that extends a fuzzy model in order to cross time-series data sets from unrelated sources. It should be noted that this approach is designed to allow as input, only data sets that are manually specified by a user. Therefore, the proposed approach: (1) may require some modification to allow it to operate in an automated environment, also (2) it crosses all data sets that a user specifies without pre-testing if the resulting crossing may be of significant interest to the user. For instance, it may be the case that crossing two unrelated data sets generates a crossed data set that does not produce any non-trivial (or interesting) pattern or knowledge when mined.

In relation to this, future works may involve extending the approach through a heuristic bot that mines a data lake's catalog in order to identify relevant time-series data sets that may produce interesting knowledge when crossed. A data lake might contain thousands of large and unrelated data sets; therefore, identifying and crossing only interesting data sets instead of crossing all the available data sets is a prudent strategy for saving time and computational resources.

1. 1

 1 Data mining techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 (a) A sample time-series data set recording the room temperature of a class, and (b) a sample time-series data set recording the number of dozing students . . . . 1.3 Data crossing model for gradual pattern mining . . . . . . . . . . . . . . . . . . . 1.4 Illustration of ACO for gradual candidate generation. (+ implies attribute is increasing, -implies attribute is decreasing and x implies attribute is irrelevant) . 2.1 Illustration of attribute dependency . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Illustration of frequent item set boundaries . . . . . . . . . . . . . . . . . . . . . 2.3 Lattice diagram of possible candidate item sets through a breadth-first search . . 2.4 Lattice diagram of sample FP-tree . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Binary matrices M G i1 , M G i2 and M G i3 for gradual items: (a) i1 = (temp, ↓), (b) i2 = (hum, ↑), (c) i3 = (mos, ↑) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Binary matrices M G i4 and M G i5 for gradual items: (a) i4 = {(temp, ↓), (hum, ↑)}, (b) i5 = {(hum, ↑), (mos, ↑)} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Hasse Diagrams for 1-itemset gradual items: (a) i1 = (temp, ↓), (b) i2 = (hum, ↑), (c) i3 = (mos, ↑) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Hasse Diagrams for 2-itemset gradual items: (a) i4 = {(temp, ↓), (hum, ↑)}, (b) i5 = {(hum, ↑), (mos, ↑)} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Binary matrices representing the sets of concordant object pairs for gradual item sets: (a) i1 = (temp, ↓), (b) i2 = (hum, ↑), (c) i3 = (mos, ↑), (d) i4 = {(temp, ↓ ), (hum, ↑)}, (e) i5 = {(hum, ↑), (mos, ↑)} . . . . . . . . . . . . . . . . . . . . . . xviii List of Figures 2.10 Relationship between U-SQL and C# & SQL . . . . . . . . . . . . . . . . . . . . . 29 2.11 Illustration of ETL process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

31 2 . 4 . 3 4 . 4

 24344 13 An illustration of the sensing entities in real life . . . . . . . . . . . . . . . . . . . 32 2.14 Comparison of (a) hypervisor and (b) container-based deployments[Bernstein, 2014] 34 2.15 Illustration of SaaS for GP mining algorithms . . . . . . . . . . . . . . . . . . . . 35 3.1 (a) Triangular MF, (b) Gaussian MF . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2 (a) Membership function for r n+1 , (b) modified membership function for r n+1 . . 44 3.3 Triangular membership function for large data sets . . . . . . . . . . . . . . . . . 45 3.4 (red graph) Plot of run-time against minimum representativity (min-rep) with min-sup held constant at 0.9. (blue graph) Plot of run-time against minimum support (min-sup) with min-rep held constant at 0.9. (a) UCI data set: 9 attributes, 10k tuples on 14 HPC CPU cores and, (b) Synthetic data set: 3 attributes, 50 tuples on 4 CPU cores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.5 Patterns extracted from the UCI data set: (a) no. of patterns vs min-sup with min-rep held constant at 0.9, (b) no. of patterns vs min-rep with min-sup held constant at 0.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1 An example of artificial ants: (a) initial paths with weighted distances, (b) at time t = 0 there is no pheromone intensity on any path; so ants choose all paths with equal probability and, (c) at time t = 1 the pheromone intensity is stronger on the shorter paths; therefore more ants prefer these paths. . . . . . . . . . . . . . . 53 4.2 A sample TSP towns graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 An example of artificial ants for BFS gradual pattern mining: (a) initial paths, (b) at time t = 0 there is no pheromone intensity on any path; so ants choose paths with equal probability, and (c) at time t = 1 the pheromone intensity is stronger on paths with cheapest gradual variations; therefore, ants prefer these paths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 An example of artificial ants for DFS: (a) initial paths with distances, (b) at time t = 0 there is no pheromone intensity on any path; so ants choose all paths with equal probability and, (c) at time t = 1 the pheromone intensity is stronger on the shorter paths; therefore more ants prefer these paths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.5 Breast Cancer (B&C) data set: (a) plot of run time against minimum support threshold and, (b) plot of memory usage against minimum support. . . . . . . . . 69 Introduction 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Mining Temporal Gradual Patterns . . . . . . . . . . . . . . . . . . . . . 1.3.2 Optimizing Generation of Candidate Gradual Item Sets . . . . . . . . . 1.3.3 Cloud Integration of Gradual Pattern Mining Techniques . . . . . . . . 1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Data mining techniques

Figure 1 . 2 :

 12 Figure 1.2: (a) A sample time-series data set recording the room temperature of a class, and (b) a sample time-series data set recording the number of dozing students

Figure 1 . 3 :

 13 Figure 1.3: Data crossing model for gradual pattern mining

Definition 2 . 1 (

 21 Item). An item is a set of literals denoted by I = {i 1 , i 2 , ..., i n }. Each transaction T in D is a set of items such that T ⊆ I and, a transaction T contains Y , a set of some items in I if Y ⊆ T . Definition 2.2 (Association Rule). An association rule is an implication of the form Y ⇒ Z, where Y ⊂ I, Z ⊂ I and Y Z = ∅. Definition 2.3 (Confidence). Confidence c is the probability that every transaction T in data set D which contains Y also contains Z. Therefore, the association rule Y ⇒ Z holds with a confidence of c if c% of the transactions in D that contain Y also contain Z.

Example 2 . 1 .

 21 Let us consider an arbitrary data set D 2.1 containing sales transactions of a shopkeeper. Let us set both the minimum support and minimum confidence to 0.75. t-id item list t101 bread, milk t102 bread, eggs, milk t103 cheese, milk t104 sugar, milk, coffee, bread

Figure 2 . 1 :

 21 Figure 2.1: Illustration of attribute dependency

Figure 2 . 2 :

 22 Figure 2.2: Illustration of frequent item set boundaries

Figure 2 . 4 :

 24 Figure 2.4: Lattice diagram of sample FP-tree

Figure 2 . 5 :

 25 Figure 2.5: Binary matrices M G i1 , M G i2 and M G i3 for gradual items: (a) i1 = (temp, ↓), (b) i2 = (hum, ↑), (c) i3 = (mos, ↑)

Figure 2 . 6 :

 26 Figure 2.6: Binary matrices M G i4 and M G i5 for gradual items: (a) i4 = {(temp, ↓), (hum, ↑)}, (b) i5 = {(hum, ↑), (mos, ↑)}

  7

Figure 2 . 7 :Figure 2 . 8 :

 2728 Figure 2.7: Hasse Diagrams for 1-itemset gradual items: (a) i1 = (temp, ↓), (b) i2 = (hum, ↑), (c) i3 = (mos, ↑)

Figure 2 .

 2 Figure 2.10: Relationship between U-SQL and C# & SQL

Figure 2 .

 2 Figure 2.11: Illustration of ETL process

Figure 2 .

 2 Figure 2.13: An illustration of the sensing entities in real life

Figure 2 .

 2 Figure 2.14: Comparison of (a) hypervisor and (b) container-based deployments[Bernstein, 2014]

Figure 2 .

 2 Figure 2.15: Illustration of SaaS for GP mining algorithms

3. 1

 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Temporal Gradual Patterns . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Proposed Definitions for Temporal Gradual Patterns . . . . . . . . . . . 3.3 Mining Temporal Gradual Patterns . . . . . . . . . . . . . . . . . . . 3.3.1 Data Transformation Model . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Building the Fuzzy Model . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 T-GRAANK Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Data Set Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "Whether you think you can or think you can't, you are right"-Henry Ford (1863 -1947)

Algorithm 1 : 7 C

 17 Transforming Time-Series Data Sets Input : D-data set, ref Column-reference column, minSup-minimum support, minRep-minimum representativity Output: T GP -set of (fuzzy) Temporal Gradual Patterns 1 S M ax ← maximum number of steps w.r.t minRep; 2 R M ax ←totalRows (D); 3 for s ← 1 to S M ax do 4 for i ← 0 to (R M ax -s) do 5 d ← tblCell [i+s] -tblCell [i] ; /* column with time */ 6 tempRow ←append (ref Column); M ax ← totalCols (Row [i] ); 8 for j ← 1 to C M ax do 9 if Column [j] = (ref Column or timeColumn) then 10 tempRow ←append (tblCell [j][i+s] ); -GRAANK(D , T d , minSup); 17 T GP ←append (tgps); 18 end for 19 return T GP ;

Figure 3 . 1 :

 31 Figure 3.1: (a) Triangular MF, (b) Gaussian MF

Algorithm 2 :

 2 Fuzzy Slide, Re-calculate Pseudocode Input : selT s-selected time-lags, allT s-all time-lags, minSup-minimum support Output: q2-approximated time lag value, sup-support1 q1 ← quartile (1, allT s), q2 ← quartile (2, allT s),and q3 ← quartile (3, allT s); 2 boundaries ← append (q1, q2, q3); 3 center ← quartile (2, selT s); 4 lef t, right ← F alse, slice ← (0.1 * q2), and sup ← 0; 5 while sup < minSup do 6 memberships ← fuzzTrimf (selT s, boundaries); 7 sup ← countAverage (memberships); 8 if sup >= minSup then 9 return q2, sup; else if lef t is F alse then if center <= q2 then 13 q1 ← (q1 -slice), q2 ← (q2 -slice), q3 ← (q3 -slice); 14 boundaries ← append (q1, q2, q3); else 16 lef t ← T rue; end if else if right is F alse then if center >= q2 then 20 q1 ← (q1 + slice), q2 ← (q2 + slice), q3 ← (q3 + slice); 21 boundaries ← append (q1, q2, q3);

Figure 3 . 2 :

 32 Figure 3.2: (a) Membership function for r n+1 , (b) modified membership function for r n+1

Figure 3 . 3 :

 33 Figure 3.3: Triangular membership function for large data sets

Figure 3 . 4 :

 34 Figure 3.4: (red graph) Plot of run-time against minimum representativity (min-rep) with minsup held constant at 0.9. (blue graph) Plot of run-time against minimum support (min-sup) with min-rep held constant at 0.9. (a) UCI data set: 9 attributes, 10k tuples on 14 HPC CPU cores and, (b) Synthetic data set: 3 attributes, 50 tuples on 4 CPU cores.

Figure 3 . 5 :

 35 Figure 3.5: Patterns extracted from the UCI data set: (a) no. of patterns vs min-sup with min-rep held constant at 0.9, (b) no. of patterns vs min-rep with min-sup held constant at 0.5.

4. 1

 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Preliminary Mathematical Notations . . . . . . . . . . . . . . . . . . . . 4.2.2 ACO for BFS Candidate Generation . . . . . . . . . . . . . . . . . . . . 4.2.3 ACO for DFS FP-Tree Search . . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Convergence Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Proposed ACO-based Approaches . . . . . . . . . . . . . . . . . . . . 4.3.1 ACO-GRAANK Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 ACO for Temporal Gradual Pattern Mining . . . . . . . . . . . . . . . . 4.3.3 ACO-ParaMiner Approach . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Data Set Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.4 Discussion of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Example 4 . 1 .

 41 We consider a sample graph of artificial ants moving along on the edges of nodes A, B, C, D, E and F as shown in Figure4.1.

Figure 4 . 1 :

 41 Figure 4.1: An example of artificial ants: (a) initial paths with weighted distances, (b) at time t = 0 there is no pheromone intensity on any path; so ants choose all paths with equal probability and, (c) at time t = 1 the pheromone intensity is stronger on the shorter paths; therefore more ants prefer these paths.

  .

2

 2

  .

Figure 4 . 2 :

 42 Figure 4.2: A sample TSP towns graph

Table 4 . 1 :

 41 Sample data set D 4.1 with 3 attributes: n = {a, b, c}. of n = {a 1 , a 2 , ...} attributes of a data set D (as shown in Table

Figure 4 . 3 :

 43 Figure 4.3: An example of artificial ants for BFS gradual pattern mining: (a) initial paths, (b) at time t = 0

Example 4 . 3 .

 43 We consider a sample graphs of artificial ants moving on the edges of nodes (or tuples) r 1 , r 2 , r 3 and r 4 as shown in Figure4.4. For the case of DFS in gradual pattern mining, we propose to use the occurrence count of tuples in the encoded transactional data set to determine the length of distance between nodes (i.e. d i,j = 1 1+ (r i ,r j )count ).

Figure 4 . 4 :

 44 Figure 4.4: An example of artificial ants for DFS: (a) initial paths with distances, (b) at time t = 0 there is

Algorithm 5 : 7 T

 57 ACO -T GRAAN K Algorithm Input : D -transformed data-set, T d -time differences, minSup-minimum support Result: T GP -set of (fuzzy) temporal gradual patterns 1 W ← ACO-GRAANK (D , minSup) ; /* generates gradual item-set solutions */ 2 foreach Pattern C in W do 3 pos indices ← concordantPositions (C pairs ); 4 time lags ← timeDifferences (pos indices , T d ); 5 boundaries ← buildTriMembership (T d ); 6 t lag ← fuzzyFunc (time lags , boundaries); GP ←append (C, t lag ); 8 end foreach 9 return T GP ;

Algorithm 6 : 8 T 15 Γ

 6815 ACO-ParaMiner algorithmInput : D-numeric data set, ς-minimum length threshold Output: GP -gradual patterns1 N ← ∅, C ← 1, Γ ← 1 ; /* Nnode set, C-C-matrix, Γ-P-matrix */ 2 GP ← ∅, repeated ← 0; 3 D enc ← encode-data (D) ; /* D encencoded data set */ 4 D red , C ← reduce-data (D enc , C) ;/* D redreduced data set */ 5 while (repeated == 0) do 6 n i,j ← gen-node (C, Γ); 7 if (n i,j ∈ N ) then * , gp ← get-tids (n i,j , D red ) ; /* T * -TIDs, gpgradual pattern */ 9 len ← intersection (T * ); 10 if (len ≥ ς) then 11 N ← N ∪ n i,j ; 12 GP ← GP ∪ gp; 13 Γ ← update-pheromones (T * , Γ); 14 else ← evaporate-pheromones (T * , Γ, );

Figure 4 . 5 :

 45 Figure 4.5: Breast Cancer (B&C) data set: (a) plot of run time against minimum support threshold and, (b) plot of memory usage against minimum support.

Figure

  Figure 4.5 (a) shows the runtime and,Figure 4.5 (b) shows the memory usage of these 4 algorithms when applied on B&C data set. We observe that ParaMiner (black triangular curve) has the slowest runtime followed (in order) by GRAANK (brown square curve), ACO-ParaMiner (blue circle curve) and, ACO-GRAANK (red cross curve). Again ParaMiner has the highest memory usage followed (in order) by ACO-ParaMiner, ACO-GRAANK and, GRAANK.

Figure 4 .

 4 Figure 4.6 (a) and (b) show runtime and memory usage of ACO-GRAANK and GRAANK on C2K data set. We observe that GRAANK has a slower runtime than ACO-GRAANK that reduces as the minimum support increases but, it has a lower memory usage than ACO-GRAANK. Using C2K data set with 3942 tuples, ParaMiner and ACO-ParaMiner yield Memory Error outputs; so, we use C2K data set with 200 tuples as shown in Figure 4.7.

Figure 4 Figure 4 . 6 :

 446 Figure 4.6: Cargo 2000 (C2K) data set: (a) plot of run time against minimum support threshold and, (b) plot of memory usage against minimum support.

Figure 4 . 7 :

 47 Figure 4.7: Cargo 2000 (C2K) data set: (a) plot of run time against minimum support threshold and, (b) plot of memory usage against minimum support.

Figure 4 .

 4 Figure 4.8 (a) and (b) show the runtime and memory usage of ACO-GRAANK and GRAANK algorithms on Buoys data set with 15402 tuples. For supports 0.5 and 0.6 GRAANK yields a Out of Memory Error output and no runtime. For ACO-GRAANK runtime and memory usage slightly increase with support. ParaMiner and ACO-ParaMiner both yield Memory Error outputs on Buoys data set with 15402 tuples; so, we use a data set with 200 tuples as shown in Figure 4.9. In Figure 4.9 (a) and (b), ParaMiner has the slowest runtime and memory usage while ACO-GRAANK, GRAANK and ACO-ParaMiner have relatively low runtimes and memory usages.

Figure 4 .Figure 4 . 8 :Figure 4

 4484 Figure 4.10 (a) and (b) show the runtime and memory usage of ACO-GRAANK and GRAANK algorithms on UCI data set with 46774 tuples. ACO-GRAANK has a lower runtime than GRAANK but, a higher memory usage. ParaMiner and ACO-ParaMiner both yield Memory

Figure 4 .Figure 4 .Figure 4 .

 444 Figure 4.10: Power consumption (UCI) data set: (a) plot of run time against minimum support and, (b) plot of memory usage against minimum support. UCI data set: #attributes=9/#tuples=1K/cores=14

Figure 4 .

 4 Figure 4.12: Bar graph of number of patterns against minimum support for data sets: (a) B&C, (b) C2K, (c) Buoys and, (d) UCI

Figure 4 .

 4 Figure 4.13: Buoys data set: graph plot of run time against size of data set for T-GRAANK and ACO-TGRAANK algorithms

Example 5 . 1 .

 51 We consider two data sets: (D 1 ) in Figure 5.1 (a), and (D 2 ) in Figure 5.1 (b).

Figure 5 . 1 :

 51 Figure 5.1: Two sample data sets containing transactions

2 :

 2 Data set (D g ) transformed from data set D g by step: s = 1.

Algorithm 7 :

 7 BT-GRAANK algorithmInput : D-data set, ref Col-reference column, σ-minimum support, δ-minimum representativity Output: T GEP s-TGEPs represented as borders 1 D * , T * d ← transform (D, δ, ref Col) ; /* Dtransformed data set, T dtime differences, * denotes multiple */ 2 tgps * ← extract-tgps (D * , T * d , σ); 3 lef tBdr * ← maximal (tgps * ); /* maximal TGPs as left-rooted borders */ 4 T GEP s ← MBD-LLBORDER (lef tBdr * ); 5 return T GEP s;

Example 5 . 3 .Figure 5 . 2 :Figure 5 . 3 :

 535253 Figure 5.2: (a) normalized support values of P 1 , and (b) normalized support values of P 2 ↑ ↓ × Rain 2 0 0 Wind 0 1.5 0 Temp 0 0 ∞ Figure 5.3: Growth-rate matrix from pheromone matrix P 1 to P 2

Figure 5 . 4 :Figure 5 . 5 :

 5455 Figure 5.4: (a) pheromone matrix for D g , (b) time-lag matrix for D g , (c) pheromone matrix D g , and (d) time-lag matrix for D g ,A growth-rate matrix in favor of the support-based pheromone matrix of transformed data set D g is shown in Figure5.5. This growth-rate matrix is mapped element-wisely onto time-lag matrices of D g and D g in order to eliminate irrelevant time-lag elements; in this case none of the

Figure 5 . 6 :

 56 Figure 5.6: UCI data set (ρ = 1.0): (a) plot of run time against minimum support threshold and, (b) bar graph of number of patterns against minimum support threshold.

Figure

  Figure 5.6 (a) shows run-time and,Figure 5.6 (b) shows the number of TGEPs extracted by TRENC and BT-GRAANK algorithms when applied on the UCI data set. We observe that the run-time of BT-GRAANK (blue curve) is lower than that of TRENC (red curve) and it reduce significantly (as well as the number of TGEPs) as support threshold is increased. For the case of TRENC, the run-time and number of TGEPs are almost constant.

Figure 5 .

 5 Figure 5.7 (a) shows run-time performance and,Figure 5.7 (b) shows the number of TGEPs extracted by TRENC and Border-TGRAANK algorithms when applied on the Directio data set. In this instance, BT-GRAANK (in comparison to TRENC) has the highest run-time (which reduces) and fewest TGEPs as the support threshold is increased. Again, the run-time and number of extracted of TGEPs are almost constant for the case of TRENC.

Figure 5 . 7 :

 57 Figure 5.7: Directio data set (ρ = 1.0): (a) plot of run time against minimum support threshold and, (b) bar graph of number of patterns against minimum support threshold.

Figure 5 . 8 :

 58 Figure 5.8: Plot of run time versus no. of cores on data sets (a) UCI and, (b) Directio

Figure 5

 5 Figure 5.9: UCI data set (ρ = 1.0): (a) plot of speed up versus number of cores (b) plot of parallel efficiency versus number of cores

Figure 5 .

 5 Figure 5.10: Directio data set (ρ = 1.0): (a) plot of speed up versus number of cores (b) plot of parallel efficiency versus number of cores

Figure 6 . 1 :

 61 Figure 6.1: Illustration of crossing 'no. of flies' and 'humidity' data sets using a fuzzy model

Figure 6 . 2 :

 62 Figure 6.2: (a) Membership function for temperature time-series data (b) membership function for humidity time-series data

Figure 6 . 4 :

 64 Figure 6.4: (a) Plot of run time versus data sets' tuples with number of data sets held at 7 (b) plot of run time versus data sets with number of tuples held at 216

Figure 6 . 5 :Figure 6 . 6 :

 6566 Figure 6.5: Plot of run time versus number of cores

Figure 6 .

 6 Figure 6.6 (a) and (b) show the speedup and parallel efficiency of the FuzzTX algorithm. We observe that for each data set, there is an optimum number of processors where parallel efficiency is highest. For the 15k-line data set this is approximately 2 processors; for the 100k-line and 200k-line data set this is approximately 5 processors.

7. 2 . 1

 21 Proposed Software Architecture Model We propose to extend GOST 1 (golang SensorThings), a certified software implementation of the OGC SensorThings API, through: (1) a Data Crossing software component that provides a user interface and allow users to cross numerous datastreams (2) a gradual Pattern Mining software component as illustrated in Figure 7.1.

Figure 7 . 1 :

 71 Figure 7.1: Proposed software model architecture for Cloud integration

Figure 7 . 2 :

 72 Figure 7.2: Docker architecture of a Cloud API for integrating GP mining algorithms into a Docker implementation of the OGC SensorThings API

Figure 7 . 3 :

 73 Figure 7.3: Screenshot of OGC SensorThings API Web interface

7. 3 . 2

 32 Use Case Example: OREME OREME 3 (Observatory of Mediterranean Research of the Environment) is a scientific observatory recognized by INSU (National Institute of Science of the Universe) and INEE (Ecology and Environment Institute) of CNRS (National Center for Scientific Research) and the IRD (French national Institute for Sustainable Development). OREME supports research activities that involve continuous observation of the natural environment over long periods in the Mediterranean region. It is constituted by 8 laboratories: CEFE (Functional and Evolutionary Ecology Center), UMR WMAU (Water Management, Actors, Uses), Geosciences Montpellier, HSM (HydroSciences Montpellier), ISEM (Institute of Evolution Sciences of Montpellier), LUPM (Laboratory Universes and Particles of Montpellier), MARBEC (Marine Biodiversity, Exploitation and Conservation) and UMR TETIS (Territories, Environment, Remote Sensing and Spatial Information).

8. 1

 1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.1 Further Efficiency Optimization of Gradual Pattern Mining Technique . 8.2.2 Memory Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.3 Detecting Interesting Data Crossings . . . . . . . . . . . . . . . . . . . . "Better is the end of a thing than the beginning thereof " -Ecclesiastes 7:8 (KJV)

Figure 8 . 1 :

 81 Figure 8.1: Screenshot of desktop application for gradual pattern mining tools

Figure 8 . 2 :

 82 Figure 8.2: Binary matrix M G for gradual pattern {(temp, ↓), (hum, ↑)}

Table 1 .

 1 .2. 2: A new data set formed by crossing 2 data sets temporally

	time (approx.)	room	number of
		temperature dozing students
	07:00	22.0	0
	07:15	22.5	1
	07:30	23.6	2
	07:45	25.0	6
	08:00	26.8	10

Table 2 . 1 :

 21 Sample data set D 2.1

  . Figure2.3 illustrates how candidate item sets may be generated in a level-wise manner from minimal item sets (i.e. {a}) to a maximal item set (i.e. {a, b, c, d}). The frequency support of each candidate is calculated and validated only if it surpasses a user-specified threshold.

			{}
	{a}		{b}	{c}	{d}
	{a, b} {a, c} {a, d}	{b, c}	{b, d}	{c, d}
	{a, b, c} {a, b, d} {a, c, d}	{b, c, d}
	{a, b, c, d}
	Figure 2.3: Lattice diagram of possible candidate item sets through a breadth-first search

Table 2 .

 2

	2: (a) Sample data set transactions for association rule mining (b) sample numeric data
	set gradual rule mining

Table 2 .

 2 4 illustrates a list of concordant couples that respect corresponding gradual item sets and the support which is calculated through dividing the number of concordant couples by the total sum of couples.

	item set	list of concordant couples	support
	{temp, ↓}	{[r1, r2], [r1, r3], [r1, r4], [r2, r3], [r2, r4]}	5/6
	{hum, ↑}	{[r1, r2], [r1, r3], [r1, r4], [r2, r3], [r2, r4], [r3, r4]}	6/6
	{mos, ↑}	{

Table 2 .

 2 4: List of concordant couples and support for some gradual item sets from data set D 2.2 in Table 2.3

Table 2 .

 2 to the problem of gradual pattern mining.Example 2.3. In order to describe this approach, let us consider a numeric data set D 2.3 . 5: Sample data set D 2.3

	id a b	c	d
	r1 5 30 43 97
	r2 4 35 33 86
	r3 3 40 42 108
	r4 1 50 49 27

Table 2 .

 2

6: (a) Transactional encoding of data set D 2.3 , (b) reduced encoded data set

Table 2 .

 2

			price	oil consumption car sales
		month ($ per 100 L)	(KL per day)	(K)
	d1	Feb	112	330	150
	d2	Mar	115	315	145
	d3	Apr	125	300	143
	d4	May	120	320	140

8: Sample numeric data sequence

Table 3 .

 3 1: Sample data set D 4.1

	Correlation between exercise and stress level
	id	date	activity	stress
		(day/month) (exercise)	level
	r1	01/06	1	4
	r2	02/06	2	2
	r3	03/06	2	3
	r4	04/06	1	5
	r5	05/06	3	1

  .2 (a).

	id	date	exercise stress	id	days lag	exercise stress
		(day/month)	(hours)	levels		(rn -rn+1)	(rn)	(rn+1)
	r1	01/06	1	4	t1	3	1	2
	r2	04/06	2	2	t2	1	2	3
	r3	05/06	3	3	t3	5	3	2
	r4	10/06	1	2	t4	2	1	3
	r5	12/06	3	3	t5	-	-	-
		(a)					(b)

Table 3 .

 3 2: (a) A sample data set D 4.2 , (b) transformed data set D 4.2

  generates frequent gradual item-set candidates */

	15	end if
	16 end foreach
	17 return T GP ;

5 foreach Candidate C in G do 6 sup ← calculateSupport (C); 7 if sup < minSup then 8 discard C; 9 else 10 pos indices ← concordantPositions (C pairs ); 11 time lags ← timeDifferences (pos indices , T d ); 12 boundaries ← buildTriMembership (T d ); 13 t lag ← fuzzyFunc (time lags , boundaries); 14 T GP ←append (C, t lag );

Table 3 .

 3 .4; except for pattern {W AJ+, M AK-}, where the time lag is slightly less.

	Ref. Item Pattern : Sup	Time Lag : Sup Rep
	NRB	{ELD+, N RB+} : 0.666	≈ +1.999yrs : 1.0	50%
		{W AJ+, N RB+, M AK+} : 0.666 ≈ +1.999yrs : 1.0	50%
	WAJ	{ELD+, W AJ+} : 0.600	≈ +1.223yrs : 0.5 62.5%
		{W AJ+, M AK-} : 0.600	≈ +1.747yrs : 0.5 62.5%

5: NDVI fuzzy-temporal gradual pattern results

Table 4 .

 4 2: (a) Sample data set D 4.2 and, (b) its corresponding sorted reduced transactional data set when minimum length of tid is 3 -see Chapter 2.2.8. = {r 1 , r 2 , ...} (as shown in Table 4.2a), gradual DFS techniques seek to find frequent gradual patterns M = {m 1 , m 2 , ...} (where ∀m ∈ M : m ⊆ n) by encoding the data set into a transactional data set (as shown in Table 4.2b) and recursively searching the transactional data set for the longest FP-Tree -see Chapter 2.2.8.

				item tids
				a ↓	{t (r1,r2) , t (r1,r3) , t (r1,r4) ,
	id a b	c	d		t (r2,r3) , t (r2,r4) , t (r3,r4) }
	r1 5 30 43 97	b ↑	{t (r1,r2) , t (r1,r3) , t (r1,r4) ,
	r2 4 35 33 86		t (r2,r3) , t (r2,r4) , t (r3,r4) }
	r3 3 40 42 108	c ↑	{t (r1,r4) , t (r2,r3) , t (r2,r4) ,
	r4 1 50 49 27		t (r3,r4) }
		(a)		d ↓	{t (r1,r2) , t (r1,r4) , t (r2,r4) , t (r3,r4) }
					(b)

Given a set of n = {a 1 , a 2 , ..., a k } attributes of a data set where each attribute has a set of tuples a k

  .10). Build binary matrices of 1-itemset from input data set D (see Chapter 2.2.7).2. Generate gradual item sets from pheromone matrix τ aj and validate each generated item set by comparing its support against the minimum support .3. If the generated pattern is valid, use gradual items to update the pheromone matrix.4. Repeat steps 2-3 until the algorithm starts to generate similar gradual item sets (see Convergence Proof in Section 4.2.4).

	4.3.2 ACO for Temporal Gradual Pattern Mining
	ACO-TGRAANK implementation based on ACO-GRAANK technique proposed in this Chap-
	P a,j (t) = ter. ACO-TGRAANK denotes Ant Colony Optimization Temporal-GRAANK algorithm since p a,j k∈{+,-,×} p a,k (t) (4.10) it modifies the T-GRAANK technique proposed in Chapter 3.
	Algorithm 4 illustrates an implementation of ACO-GRAANK technique. As can be seen, the
	main steps are:
	1. 15	else

Algorithm 4: ACO-GRAANK algorithm Input : D-numeric data set, σ-minimum support threshold Output: W -winner gradual patterns 1 W ← ∅, L ← ∅, τ ← 1 ; /* Wwinner set, Lloser set, τ -P-matrix */ 2 B * ← bin-gp-matrices (D) ; /* B *binary representations */ 3 repeated ← 0; 4 while (repeated == 0) do 5 gp gen ← gen-gp-soln (A, τ ) ; /* Aattributes of D */

6 if (gp gen ∈ W ) then 7 repeated ← 1; 8 else if (gp gen ⊇ L) OR (gp gen ⊂ W ) then 9 continue; 10 else 11 supp ← evaluate-gp (gp gen , B * ); 12 if (supp ≥ σ) then 13 W ← W ∪ gp gen ; 14 τ ← update-pheromones(gp gen , τ );

Table 4 .

 4 3: Sample data set D 4.3

		id a b	c	d
		r1 5 30 43 97
		r2 4 35 33 86
		r3 3 40 42 108
		r4 1 50 49 27
	Table 4.4: (a) example of a reduced transactional data set, (b) sorted items by occurrence
	tids	w item-sets
	t (r1,r2)

Table 4 .

 4

	5: (a) sorted reduced transactional data set, (b) corresponding cost matrix
	item tids
	a ↓	{t (r1,r2) , t (r1,r3) , t (r1,r4) ,
		t (r2,r3) , t (r2,r4) , t (r3,r4)

Table 4 .

 4 6: Experiment data sets

	Data set	#tuples #attributes Timestamped	Domain
	Breast Cancer (B&C)	116	10	No	Medical
	Cargo 2000 (C2K)	3942	98	No	Transport
	Directio (Buoys)	948000	21	Yes	Coastline
	Power Consumption (UCI) 2075259	9	Yes	Electrical

Table 4 .

 4 7: Consistent gradual patterns

	Data set Consistent gradual patterns
	B&C	{(Insulin, ↓), (HOM A, ↓)}, support: 0.94
	C2K	{(i1_rcf _1_p, ↑), (i1_rcf _1_e, ↑)}, support: 0.837
	Buoys	{(T z, ↓), (T av, ↓)}, support: 0.945
	UCI

{(Global_activepower, ↑), (Global_intensity, ↑)}, support: 0.954

Table

Table 5 .

 5 .1. 1: Sample data set of rainfall amount and wind speed recorded at different dates.

	id	date	rain	wind
		(day/month) (mm) (km/h)
	r1	01/06	10	42
	r2	04/06	13	21
	r3	05/06	18	35
	r4	10/06	10	21
	r5	12/06	18	35

Table 5 .

 5 3: Experiment data sets

	Data set	#tuples #attributes Timestamped	Domain
	Buoys (Directio)	6121	21	Yes	Coastline
	Power Consumption (UCI)	10001	9	Yes	Electrical

Table 5 .

 5 4: Consistent TGEPs extracted from data sets UCI and Directio

	Data set	Consistent TGEPs (ρ = 1.0)
	Buoys (Directio)	{(T z, ↑), (Hm0, ↑)}: growth-rate 1.0
		after every 2.5 hours
	Power Consumption (UCI) {(activepower, ↑), (voltage, ↓)}: growth-rate 1.04
		after every 24 hours
	5.6.4 Discussion of Results

Table 6 .

 6 1.

	time no. of flies	time humidity
	r1 12:01	50	r1 12:00	30
	r2 12:02	160	r2 12:02	35
	r3 12:03	230	r3 12:04	40
	r4 12:04	243	r4 12:06	50
	r5 12:05	259	r5 12:08	52
	(a)		(b)

Table 6 .

 6 1: (a) Sample of population of flies time-series data (b) sample of humidity time-series data

  .2 (b).

	center humidity	flies
		index	index
		(max. MD) (max. MD)	time humidity no. of flies
	12:00	r1 (1.0)	r1 (0.9)	12:00	30	50
	12:02	r2 (1.0)	r2 (1.0)	12:02	35	160
	12:04	r3 (1.0)	r4 (1.0)	12:04	40	243
	12:06	r4 (1.0)	r5 (0.9)	12:06	50	259
		(a)			(b)

Table 6 .

 6

2: (a) Tuple indices of humidity and pop. of flies data sets after applying steps 1 and 2 (b) crossed data set after applying steps 3 and 4

  Algorithm 9: FuzzTX algorithm Input : time-series data sets DS * Output: data set D 1 B ← ∅, D ← ∅; 2 T min , T max ; 3 for ds in DS * do BuildTriMF(t -bound sel , t, t + bound sel ); tuple ← x tuple ∪ ds tuple [index];

	9 end for
	10 bound sel ← max(B) ; /* largest boundary	*/
	11 t ← T min ;
	12 while t ≤ T max do
	18	Delete(ds tuple [index]);
	19	else
	20	x tuple ← F alse;
	21	Break();
	22	end for
	23	if x tuple then
	24	D tuples ← D tuples ∪ x tuple ;
	25	end if
	26	t ← t + bound sel ;
	27 end while
	28 return D

4

T arr ← ExtractTime(ds); 5 T max ← max(T arr ) ; /* iff greater */ 6 T min ← min(T arr ) ; /* iff lesser */ 7 min d ← MinDiff(T arr ); 8 B ← B ∪ min d ; 13 mf ← 14 for T arr of each ds in DS * do 15 index ← max(FuzzyX(mf, T arr )) ; /* index with largest membership degree */ 16 if index then 17 x

Table 8 .

 8 Example 8.1. An arbitrary data set D 8.1 containing recordings of atmospheric temperature, atmospheric humidity. 1: Sample data set D 8.1

	id temperature humidity
	r1	30	.2
	r2	28	.4
	r3	26	.5
	r4	26	.8

https://docs.microsoft.com/en-us/u-sql/

https://www.opengeospatial.org/

https://52north.org/

https://www.gostserver.xyz/

https://oreme.org/

https://meso-lr.umontpellier.fr

https://www.opendatacube.org

return W ;

https://meso-lr.umontpellier.fr

https://data.oreme.org

A collection of sets C is an antichain if ∀X, Y ∈ C, X ⊆ Y and Y ⊆ X

https://meso-lr.umontpellier.fr

https://data.oreme.org

Puéchabon is city located in southern France

http://www.anaee-france.fr/fr/

https://meso-lr.umontpellier.fr

https://www.gostserver.xyz

https://uwsgi-docs.readthedocs.io/en/latest/

https://oreme.org

https://inspire.ec.europa.eu

https://data.oreme.org

We submitted our work on "ant colony optimization for mining gradual patterns" to the 'International Journal of Machine Learning and Cybernetics' in July 2020. We are awaiting feedback from the reviewing committee.

The work "gradual pattern mining tools on Cloud" will be submitted as a demo paper in an International conference and could also be submitted to the 2021 conférence Extraction et Gestion des Connaissances (EGC) to be held in Montpellier, France.

Acknowledgements

The road to attaining this Ph.D. degree has been intense and it has required a great deal of hard work and unwavering perseverance. I sincerely thank my chief advisor Prof. Anne Laurent for all the good guidance and personal assistance she offered me throughout the Ph.D. journey especially when I worked from LIRMM at Montpellier, France. In addition, I thank my second advisor Dr. Joseph Orero for his constructive recommendations and for creating a favorable working environment for me at Strathmore University (Nairobi, Kenya) which allowed me to put enough focus on the Ph.D. studies.

Proposed Mathematical Notations of ACS for GPCG Problem

The gradual pattern candidate generation (GPCG) problem can be stated as:

"the problem of finding the cheapest variation routes that connect all gradual items that satisfy the minimum frequency requirement once."

In gradual pattern mining, a potential candidate must not include any infrequent singleton gradual item set (anti-monotonicity property -see Chapter2. 2.4). Therefore, when apply ant colony system (ACS) to the case of GPCG problem, we define each node of the ACS graph as a singleton gradual item derived from its attribute and the variation edge distance d i,j between nodes i, j is given by formula in Equation (4.3):

where sup(i) is the frequency support of gradual item set {i}, is a user-specified minimum support threshold -see Chapter 2.2.3. The possibility of gradual item (i, j) being frequent is either visible '1' or not visible '∞'.

Let b i (t) | i = 1, 2, ...n be the number of ants at node i at time t and, q = n i=1 b i (t) be the total number of ants. Each ant is a simple agent that:

• chooses a node to go to based on the probability that is a function of the amount of pheromone present on the connecting edge,

• is prohibited from returning to already visited nodes until a tour visit of all nodes is completed (this is managed by a tabu list) and,

• deposits pheromone trails on all visited edges if support of all visited nodes sup(N) ≥ , once it completes the tour. This is because a gradual candidate is formed by combining all the visited nodes into a set; and, if the candidate is not frequent then its path is also not appealing. Lastly, every edge (i, j) is removed if: sup(i) < and sup(j) < .

Let τ i,j (t) be the pheromone intensity on edge (i, j) at time t and, each ant at time t chooses the next node to visit, where it will be at time t + 1. We define q movements made by q ants in the interval (t, t + 1) a single iteration of the ACS algorithm. Therefore, every n iterations of the algorithm each ant completes a visit of all valid nodes (tour cycle) and, at this point the pheromone intensity is updated according to the formula in Equation (4.4).

where ρ and ∆τ i,j are similar to Equation (4.1) and, N n is the set of all nodes visited by the ant at end of n iterations

Ant-based Discovery of TGEPs

In this section, first we introduce an alternative approach that is based on ant colony optimization (ACO) for mining gradual patterns (GPs) and temporal gradual patterns (TPGs), and second we extend this approach in order to mine for temporal gradual emerging patterns (TGEPs).

ACO for TGEP Mining

In Chapter 4, we have proposed an ACO strategy that uses a probabilistic approach to efficiently generate gradual item set candidates from a data set's attributes. Ant colony optimization (ACO), as originally described by [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF], is a general-purpose heuristic approach for optimizing various combinatorial problems. It exploits the behavior of a colony of artificial ants in order to search for approximate solutions to discrete optimization problems.

In order to apply ACO to the problem of gradual pattern mining, we have described in Chapter 4.2: (1) a suitable representation of the gradual item set candidate generation problem, (2) a probabilistic rule P for generating solutions S n , (3) a technique for updating the pheromone matrix T a,j , (4) a convergence proof for confirming that this approach finds an optimal gradual pattern from a data set.

It should be remembered that not only may the ACO strategy be applied to the case of gradual pattern mining but also to the case of TGP mining. As described in Chapter 3.3, TGP mining involves two main processes: (1) transforming a timestamped data set into multiple data sets using a specified representativity threshold, and (2) applying a modified GRAANK algorithm that extracts gradual patterns together with an approximated time lag. Therefore, the modified GRAANK algorithm is substitute for a modified ACO-based algorithm.

For the purpose of applying ACO strategy to the case of TGEPs, we propose a modification of the technique for updating the pheromone matrix T a,j shown in Equation (5.4). The matrix contains knowledge about pheromone proportions of the 3 gradual options for each attribute. In fact, it is through the pheromone matrix that the algorithm learns how to generate highly probably valid gradual item set candidates.

where q: number of attributes, a = 1, ..., q and, j ∈ {+, -, ×}

At the beginning all artificial pheromones p a,j in T a,j are initialized to 1, then we modify the manner in which the pheromone matrix is updated as follows at time interval (t, t + 1):

• Every generated gradual item set solution is evaluated and only valid solutions are used to update the artificial pheromone matrix. Invalid solutions are stored with aim of using them to reject their supersets.

Summary

In this work, first we have introduced the concept of temporal gradual emerging patterns; second, we have proposed two strategies for mining temporal gradual emerging patterns; third, we have proposed an experimental computational performance comparison including a parallel implementation of these two approaches on a HPC supercomputer. Finally, we recommend ant-based strategy as the most suitable strategy for mining temporal gradual emerging patterns especially when dealing with huge data sets.

(1) Speedup S(n) may be defined as: "the ratio of the execution time of a single processor to the execution time of n processors" as shown in Equation (6.1).

where n is the number of available processors

(2) Parallel efficiency E(n) may be defined as: "the average utilization of n processors" as shown in Equation ( 6.2) [START_REF] Eager | Speedup versus efficiency in parallel systems[END_REF]].

In the FuzzTX algorithm (see Pseudocode 9, we implement parallel processing at 2 code segments: (1) the for-loop between lines 3 -8 and ( 2) the while-loop between lines 12 -26 since each of their steps can be executed in isolation. We record the results in Table ?? and we use the results to plot the speedup and parallel efficiency in Figure 6.6 (a) and (b). We discuss these results in Section 6.3.5.

Data Set Description

In order to test computational efficiency, the FuzzTX algorithm was executed on 7 time-series data sets obtained from OREME's data portal that recorded meteorological observations at the Puéchabon 1 weather station between the years 2000 and 2017 [Ecofor, 2019]. This data is licensed under a Creative Commons Attribution 4.0 License and the site is annually supported by Ecofor, Allenvi and ANAEE-F 2 . For this experiment, each data set has 4 attributes and 216 tuples. We performed test runs on a 2.9 GHz Intel Core i7 MacBook Pro 2012 model, with 8 GB 1600 MHz DDR3 RAM.

In order to test parallel processing efficiency, the FuzzTX algorithm was executed on 3 timeseries data sets obtained from OREMES's data portal that recorded swell sensor signals of 4 buoys near the coast of the Languedoc-Roussillon region in France between the years 2012 and 2019. The data is available at https://oreme.org/observation/ltc/. For this experiment, each data set has 30 attributes and tuples ranged 15,000, 100,000 and 200,000. The test runs were performed on a (High Performance Computing) HPC platform Meso@LR 3 . We used one node made up of 28 cores and 128GB of RAM.

Use Case Example: Mining Temporal Gradual Patterns

We applied the T-GRAANK algorithm proposed in Chapter 3 on the crossed data we obtained after applying our FuzzTX algorithm on the time-series data sets from the Puéchabon weather station. We obtained temporal gradual patterns shown in Figure 6.7. For instance the pattern {('2+','1+') : 0.5121 | ∼ +4.0 weeks : 0.5} may be interpreted as: "the higher the evapotranspiration, the higher the rainfall amount, almost 4 weeks later".

Summary

In this chapter, we propose a fuzzy model that applies a triangular membership function to cross time-series data sets. This model is most suitable for adoption by research observatories (such as OREME) that support data lakes which store time-series data or data streams from different sources.

In order to emphasize the applicability of our model, we integrated the FuzzTX algorithm into a Docker implementation of the OGC SensorThings framework to cross different data streams and extract relevant gradual patterns. We describe this implementation in Chapter 7. The source code for this work is available at our Github repository: https://github.com/owuordickson/ cloud-api.git.

B.1.1 Requirement

You will be required to install Docker.

B.1.2 Installation

B.2 Installing Web GRAANK Tool

Graank tool is a gradual pattern mining Web application implemented in Node.js. It allows users to:

• Extract gradual patterns, fuzzy-temporal gradual patterns and emerging gradual patterns from numeric data sets (csv format).

• Cross different time-series data sets (in csv format).

B.2.1 Installation

Download/clone into a local package from https://github.com/owuordickson/graank-tool-nodejs. git. There are two options for installing this application (through a command line program with the local package):

B.2.2 Usage

Launch your Browser and go to: http://localhost:80 or http://localhost:80/x