François Le

Radar, without tears

François Le Chevalier1

May 2017

Originally invented to facilitate maritime navigation and avoid icebergs, at the beginning of the last century, radar took off during the Second World War, especially for aerial surveillance and guidance from the ground or from aircraft. Since then, it has continued to expand its field of employment.

1 What is it, what is it for?

Radar is used in the military field for surveillance, guidance and combat, and in the civilian area for navigation, obstacle avoidance, security, meteorology, and remote sensing.

For some missions, it is irreplaceable: detecting flying objects or satellites, several hundred kilometers away, monitoring vehicles and convoys more than 100 kilometers round, making a complete picture of a planet through its atmosphere, measuring precipitations, marine currents and winds at long ranges, detecting buried objects or observing through walls -as many functions that no other sensor can provide, and whose utility is not questionable. Without radar, an aerial or terrestrial attack could remain hidden until the last minute, and the rain would come without warning to Roland-Garros and Wimbledon ... Curiously, to do this, the radar uses a physical phenomenon that nature hardly uses: radio waves, which are electromagnetic waves using frequencies between 1 MHz and 100 GHz -most radars operating with wavelength ( = c / f,  being the wavelength, c the speed of light, 3.10 8 m/s, and f the frequency) between 300 m and 3 mm (actually, for most of them, between 1m and 1cm): wavelengths on a human scale ... Indeed, while the optical domain of electromagnetic waves, or even the ultraviolet and infrared domains, are widely used by animals, while the acoustic waves are also widely used by marine or terrestrial animals, there is practically no example of animal use of this vast part, known as "radioelectric", of the electromagnetic spectrum (some fish, Eigenmannia, are an exception to this rule, but they use frequencies on the order of 300 Hz, and therefore very much lower than the "radar" frequencies). Generators, receivers, antennas, etc. therefore have no equivalent in nature, and had to be invented « from scratch ».

The main interest of this "radioelectric" frequency band is that they easily propagate in the atmosphere, even in the presence of rain or fog or smoke: Figure 1 shows that the attenuation is less than one dB/km (Remind : 1dB is a factor 1.25, 3dB is a factor 2, 10dB is a factor 10) over almost all this frequency band -the lowest frequencies being considerably less attenuated. Moreover, since the corresponding wavelengths are of the centimeter type, the antennas remain of reasonable dimensions, as will be seen hereinafter.

Overall, this same part of the electromagnetic spectrum, whose propagation and reflection properties were highlighted by Hertz at the end of the 19 th century, are used by all modern means of communication (radio, communications, localization). Nowadays, all of these radioelectric means are used, often jointly, to carry out the main tasks of surveillance, navigation and guidance; For example, for air traffic control, satellite positioning systems (using radio waves at 1 GHz) are complemented by surveillance radars (often around 3 GHz), for airport security, and weather radars (at 3, 5, or 10 GHz) for weather monitoring.

-Figure 1 : Electromagnetic propagation in the atmosphere -2 How does it work?

Principle

The principle of radar is that of the echo: a wave is created and sent, propagates in the vacuum or in the atmosphere, then is reflected by the object -the "target" in the martial vocabulary that radar has inherited from its warlike origins -and captured in return. This principle, well known in acoustics as sonar (and used by bats, dolphins, and ... mountaineers), is also valid in electromagnetism, and in particular for these "radioelectric" waves, since most of the obstacles, natural or artificial, send back a radioelectric echo -it is indeed difficult to reduce this echo, as the modern "stealth" technology demonstrates.

It is thus an "active" system, implementing a transmitter and a receiver, according to the principle diagram represented in Figure 2: an electric oscillation, of roughly sinusoidal shape, is created (waveform generator), amplified and shaped by a transmitter: until then, one remains in the domain of electrical (or electronic) circuits. This signal is then transmitted by the antenna to the external environment in the form of an electromagnetic wave which propagates towards the target and then returns (partly, because it is strongly attenuated by propagation and by the reflection on the target) and is detected by the receiving antenna (generally common with the transmitting antenna), and transmitted again to the receiver as an electrical signal. This receiver compares the very small received signal with the transmitted signal (to check that it is indeed an echo, and to extract it from the surrounding noise), and transmits this information to a display console or, more generally, to the system in charge of exploitation of the information.

- The presence of this echo provides, besides the index of presence of a target ("detection"), its distance, by measuring the delay between transmission and reception (extremely short delay, given the high speed of the light: c = 3. 10 8 m/s: a delay of 1μs for the round trip on a target at 150m), and its direction, by the knowledge of the angular sector illuminated by the antenna. RAdio Detection And Ranging , RADAR -one could then add "and angular localization", but also "and velocity measurement", because the radar measures the speeds of the targets thanks to the Doppler effect: indeed, this measurement of speed is essential to separate the "fixed" echoes (on buildings, trees, mountains, etc.) from "mobile" echoes, which are generally echoes of interest to the user.

Doppler effect

The Doppler effect, which indeed plays a crucial role in radar, can be understood simply by considering a sinusoidal wave of frequency f (ie f oscillations per second) emitted by a fixed transmitter and propagating at a speed c -with a wavelength λ= c/fand received by a sensor traveling at a velocity v relatively to the transmitter: due to its regular movement towards the source, the sensor will see a duration of each oscillation (period) slightly shorter; More precisely, in 1s, it will count a number of oscillations no longer equal to f, but to f+v/ : indeed, from the point of view of the target, the apparent speed of the wave is c+v : the apparent covered distance by the wave during 1s is c*1s + v*1s hence a count of oscillations, each of length lambda, given by c/+ v/ = f + v/ . In other words, if the sensor has approached k wavelengths in 1s, it will count a number of oscillations equal to f + k.

The Doppler effect is thus an apparent shift of the emitted frequency equal to v/(ie equal to the radial velocity -the velocity component parallel to the direction of propagation -expressed in wavelengths per second), positive if the sensor moves to the transmitter, and negative if not. It does not depend on the nature of the wave which is transmitted, and is also observed for sound waves, hence the well-known effect on sirens of ambulances ... This frequency shift occurs on the path from the antenna to the target, but also on the return path, resulting in a total shift of 2v/ of the radar frequency. In order of magnitude, this corresponds to an offset of 200 Hz for a target traveling at a radial speed of 10 m/s (36 km/h), as seen by a radar operating at 10 cm wavelength (at a carrier frequency of 3 GHz): this shift is therefore significant, but very delicate to measure, since the relative accuracy required is 200/(3.10 9 ), or 6.10 -8 : to achieve such an accuracy, the generated sinusoid must be extremely pure, which leads radarists to design systems built on a single clock, of high spectral purity, from which are generated all the necessary signals: pulse cutting, signal sampling, local oscillators, etc.

With these orders of magnitude, it can be seen that not only, as mentioned above, the transmitters, receivers, antennas, etc. have no equivalents in nature, but also that the quality of the requirements required to perform a correct detection is very high.

Thus, the radar operates on the principle of echo using radio waves, these echoes being affected by a Doppler effect which makes it possible to measure their velocities. Before constructing a generic radar, we still have to say a word about the antenna, which is an essential component of the radar, -the most visible on the outside -, and which is a key factor for the "power budget", ie to determine the required power and the corresponding maximum ranges.

The antenna

As mentioned above, the antenna transforms the electrical signal leaving the transmitter into a wave propagating in the surrounding environment, in a certain angular sector -and ensures the inverse transformation on receive. It thus fulfills two functions: the adaptation between the waveguide or the coaxial cable carrying the electrical signal and the external environment, and the focusing of the emitted wave in a certain (usually narrow) angular sector.

For "centimeter" waves -typical of radar -, a quasi-optical approximation can be used to analyze the propagation of waves: this approximation makes it possible to understand simply the operation of the parabolic antennas of traditional radars (Figures 3 and4): The waveguide disposed after the transmitter is terminated by a horn which provides the adaptation with the external medium. This horn is placed at the focus of a parabola which makes it possible to generate a plane wave propagating in the direction of the xx' axis of the parabola.

-Figure 3 : Parabolic reflector antenna -Indeed, by virtue of the basic geometrical property of the parabola, the paths FMP, FM'P', FM''P'', etc. are of the same length, so that the signal emitted from the focus F simultaneously arrives at P, P', and P'': yy' defines the trace of the wave front (perpendicular to the propagation axis xx' ) in the figure, and this reflector antenna emits a plane wave in the direction of its xx' axis.

- In fact, this wave is emitted in a certain angular sector (cone) around the direction x x'. It can be shown that the opening of this angular sector, expressed in radians, is equal to  / D being the wavelength used and D the dimension of the antenna: in other words, the antenna ability to focus the emitted energy is directly proportional to its dimension, expressed in wavelengths. Similarly, for a two-dimensional antenna, one obtains an ability to focus in azimuth proportional to the width of the antenna, and in elevation proportional to its height:

𝜃 = , 𝑎𝑛𝑑 𝜃 = ;
Typically, for a wavelength of 10 cm and an antenna dimension of 2 m, an angular selectivity of the order of 1/20 radian is obtained, ie approximately 3°: this allows an approximate angular localization, but with limited resolution (1/20 radian is equivalent to 5 km at 100 km range!). We see that it is interesting to choose small wavelengths to improve this angular resolution -but then, it is the propagation losses (Figure 1) that limit the maximum range of the radar ... This compromise between angular resolution and propagation losses explains that short-range radars generally use small wavelengths, between 3 mm and 3 cm, especially for applications where the available volume is severely constrained, on board aircraft or vehicle in particular. Conversely, for long range radars, larger wavelengths, typically between 10 cm and 1 m, are generally chosen and large antennas are used.

Nowadays, this rotating parabola for successively exploring the different directions is increasingly replaced by an "active antenna" network, according to Figure 5: rather than a wave emitted by a single source and then reflected by a parabola, one uses a quantity of elementary sources (typically one thousand) transmitting simultaneously the same signal: this produces in the same way a plane wavefront of trace P P'P'' in the figure, perpendicular to the axis x x', with the same angular selectivity (/D) as in the case of a parabola.

-Figure 5 : Array antenna, boresight looking -The advantage of this solution is that if there are suitable programmable delays before the transmitters, , ', '', etc., it is possible to orient the wave front in any direction, according to Figure 6: it thus becomes possible to carry out a very agile "electronic scanning" without any mechanical movement. Another advantage is that the single highpower transmitter placed at the focal point of the parabola has been replaced by a series of low-power elementary transmitters which can be realized in solid state technology: this system is more tolerant of elementary failures, and now feasible at an acceptable cost thanks to the series effects (1 antenna = 1000 transmitters / receivers, typically).

-Figure 6 : Array antenna, squint looking -Two examples of radars using this so-called active-transmitting-receiving antenna technique are shown in Figure 7: a rotating antenna, combining mechanical scanning and electronic scanning for sectorial observation (COBRA radar for counterbattery), and a fixed antenna, for airborne front radar (RBE2 radar of the Rafale aircraft).

-Figure 7 : Modern radar active antennas (Courtesy of Thales): on the left, an active electronic scanning antenna (COBRA radar), and on the right an airborne fixed electronic scanning antenna (RBE2 radar of the Rafale) -

The waveforms

Since the received echo is very low compared to the transmission, it is necessary to shut the transmission during reception (not easy to listen while screaming...). Moreover, to measure the distance with precision, it is obviously preferable to use a pulse as short as possible. Most radars therefore transmit short pulses of the order of one microsecond (if the duration of the pulse is 1 microsecond, then its "length" is 300 m, that is to say 150 m taking into account the two-way path of the wave). For a long-range radar, for example 150 km, the echo returns after 1 ms: it is therefore possible to transmit these pulses with a repetition period of at least 1 ms. Such a radar then typically transmits pulses with duration 1 µs, on a carrier around 3 GHz (leading to 3000 oscillations per pulse : it looks indeed like a portion of a continuous wave ! See Figure 9 below)), repeated every ms.

In the real world, the received echo is in fact the superposition of many distinct echoes contained within the 150m range resolution cell : a real target produces many elementary echoes (coming from reflexions from different parts, eg wings, fuselage, cockpit, etc.) summing up to an equivalent echo, itself being mixed up with ground echoes from the same resolution cell as the antenna beam may illuminate the ground as well as the target : the Doppler effect can help discriminating the useful echoes : actually, one carrier is emitted, but multiple (slightly different) frequencies are received from the moving targets -and then separated on receive, by spectral analysis, just as different notes are separated in audio.

The measurement of the velocity by the Doppler effect is not possible with sufficient accuracy (on the order of 10 to 100 Hz, typically, as described in paragraph 2.2) over the duration of a pulse: actually, over a duration T, it is possible to measure a frequency shift f with a resolution 1/T, ie it is possible to measure one more (or one less) oscillation: 2f T ≥ 2 (see Figure 8). The Doppler will therefore be measured by analysis of a train of 10 to 100 consecutive pulses -and therefore the radar antenna must remain pointed (mechanically or electronically) in each direction for typically 10 to 100 ms.

-Figure 8 : Two discernible sinusoids (for example counting zero crossings): 20 oscillations for the first, 19 for the second -It is thus seen that a fine analysis of speed requires a rather long observation time in each direction, and therefore a rate of renewal of the information not too high: this is one of the compromises to which the radar must comply (such as that mentioned above linking the angular resolution and the maximum range in rainy weather, via the choice of the wavelength).

Another compromise appears quickly with this type of pulse waveform: improving the range resolution leads to shortening the emitted pulses and thus reducing the energy sent to the target2 -and thus the energy received from this target: it then becomes difficult to obtain a good resolution in range, necessary to separate close planes, for example, at long distance. Fortunately, there is a way out of this dilemma, by modulating the pulse (phase or frequency modulation): instead of emitting a "pure" sinusoid, a sinusoid modulated in frequency is emitted, (for example a linear modulation, for the signal known as « Chirp » -which, by the way, is a typical waveform used by bats for ultrasound echolocation), which allows to decouple the pulse duration from the range resolution, because a long but very modulated pulse makes it possible to measure the distance with a good resolution. Without going into details, however, it should be noted that on receive, the signal processing will obviously have to take account of this a priori knowledge of the shape of the transmitted pulse, in order to extract from the received signal "what looks like the transmitted signal".

Power budget

Consider a radar having a transmitter with power Pt , and seeking to detect a target at a distance R, with a rectangular antenna of area A = Dhorizontal . Dvertical , hence of angular resolutions 𝜃 = , 𝑎𝑛𝑑 𝜃 = ;

Let us assume first that the emission antenna is isotropic, thus illuminating 4π steradians3 . The target is characterized by its "radar cross section", that is to say that it intercepts the fraction of the transmitted power,  being the effective cross-section 4 and 4𝜋R 2 surface of the sphere radiated from the emitter at the distance R. This intercepted power is re-radiated from the target in all directions and the receiving antenna in turn intercepts the fraction . The received power is thus written :

𝑃 = 𝑃 𝜎 4𝜋𝑅 𝐴 4𝜋𝑅
In practice, the transmitting antenna is not isotropic (it is generally the same as the receiving antenna), it can be characterized by its gain G, which simply measures its ability to focus the energy, with respect to an isotropic antenna: the gain is therefore the ratio between the 4 steradians covered by an isotropic antenna and the 𝜃 . 𝜃 steradians covered by the directive antenna (for small angles, the steradians are simply the product of the radians in 2 orthogonal directions), or 𝐺 =

. We obtain :

𝑃 = 𝑃 𝐺 𝜎 4𝜋𝑅 𝐴 4𝜋𝑅 = 𝑃 𝜎 𝐴 4𝜋𝜆 𝑅
This radar transmits a pulse, which can be seen as a « portion of plane wave », illustrated on Figure 9, with widths 𝜃 and 𝜃 -typically a few degrees each -and depth R (range resolution, equal to the length of the pulse -typically 150m -, when there is no specific modulation) ; this pulse is transmitted, reflected by the target, and received with the residual power Pr.

The power budget is therefore proportional to 1/R 4 , decreasing very rapidly with distance. Typically, for a radar cross-section of 1 m² and a surface antenna 1 m², the power received at 10 km is about 150 dB lower than the transmitted power! If one transmits kilowatts, one receives picowatts: it is indeed necessary to shut the transmission during the reception.

It is also necessary to use an amplifier of excellent quality in reception, so as not to mask the very low received signal by the noise of this receiver: the radar is a school for high quality: high spectral purity, low noise factor, suitable signal processing, etc.

-Figure 9 : Baseline radar transmission -

Future radars

The principles of radar are now well established, but the required technologies (miniaturization of transceivers and increased performance of analog-to-digital converters, in particular) are rapidly evolving: radars are now being designed with signals emitted simultaneously in different directions (Figure 10), in order to better resolve the compromises mentioned above.

There is also a trend towards widening the bandwidth of signals used, in order to improve the accuracy of targets analysis of and to discriminate, for example, a lowaltitude drone from a vehicle, even in urban environments returning very strong fixed echoes.

q azimuth q elevation R Finally, all the available information processing resources (including multisensor fusion, and deep learning analysis for reliable identification of targets) are used to improve the management of these very agile sensors, and extract the best knowledge about the targets and their environment. In general, the main enemy of the surveillance radar remains fixed echoes (buildings, trees) or slowly mobile echoes (rain, foliage, sea). For this reason, the development of new sensors requires very fine simulations of environments and nuisances (including other emissions, telephony, Wifi, radar, etc.), and real-world testing to take full account of the infinite variety of real situations. These severe constraints also drive the search for high quality integrated transmitters and receivers in radar frequency bands.

Figure 2 :

 2 Schematic diagram of a radar -

Figure 4 :

 4 Rotating antenna with reflector, to monitor air traffic in the terminal area (range: 100 km) of an airport; We note the presence of 2 horns in the vicinity of the focus, to create 2 beams slightly offset in elevation -

-

  Figure 10 (by J.P. Guyvarch) : Multiple simultaneous transmissions -Multiple Input Multiple Output (MIMO), providing better angular resolution and adaptation of the radar to its environment, both for emission and for reception.

Many thanks to my colleagues who reviewed and improved an earlier version of this essay : Y. Blanchard, E. Chamouard, C. Enderli, F. Gosselin, N. Petrov, L. Savy

Since the peak power of the transmitter is generally limited, the shortening of a pulse cannot be compensated for by increasing the peak power.

According to Wikipedia, the steradian (symbol: sr) is the unit of solid angle. It is used in threedimensional geometry, and is analogous to the radian which quantifies planar angles.A steradian can be defined as the solid angle subtended at the center of a unit sphere by a unit area on its surface. For a general sphere of radius r, any portion of its surface with area A = r 2 subtends one steradian.Because the surface area A of a sphere

is 4πr 2 , the definition implies that a sphere measures 4π (≈ 12.56637) steradians. By the same argument, the maximum solid angle that can be subtended at any point is 4π sr.4 Typical orders of magnitudes for radar cross sections are 1 m 2 for a pedestrian, a few m 2 for a fighter aircraft, 10 m 2 a vehicle, and thousands of m 2 for a ship.


Victor Codocedo

Guillaume Bosc

Mehdi Kaytoue

Jean-François Boulicaut

Amedeo Napoli

A Proposition for Sequence Mining Using Pattern Structures

In this article we present a novel approach to rare sequence mining using pattern structures. Particularly, we are interested in mining closed sequences, a type of maximal sub-element which allows providing a succinct description of the patterns in a sequence database. We present and describe a sequence pattern structure model in which rare closed subsequences can be easily encoded. We also propose a discussion and characterization of the search space of closed sequences and, through the notion of sequence alignments, provide an intuitive implementation of a similarity operator for the sequence pattern structure based on directed acyclic graphs. Finally, we provide an experimental evaluation of our approach in comparison with state-of-the-art closed sequence mining algorithms showing that our approach can largely outperform them when dealing with large regions of the search space.

Introduction

Sequence mining is an interesting application of data analysis through which we aim at finding patterns in strings of symbols, sets or events [START_REF] Agrawal | Mining sequential patterns[END_REF]. One of the simplest incarnations of this problem is finding, within a database of words, a set of substrings that appear more frequently among them, e.g. prefixes or suffixes are usually "frequent substrings".

Traditional algorithms for sequence mining rely on prefix enumeration [START_REF] Wang | BIDE: efficient mining of frequent closed sequences[END_REF][START_REF] Yan | Clospan: Mining: Closed sequential patterns in large datasets[END_REF][START_REF] Zaki | SPADE: An Efficient Algorithm for Mining Frequent Sequences[END_REF] exploiting the fact that the longest a prefix is, the fewer words contain it (e.g. prefix pr-is contained in prehistoric, prehispanic and primitive, while the prefix pri-is only contained in primitive).

While these techniques are usually very efficient at finding frequent subsequences, there are some issues they do not address. Firstly, frequent sequences are usually short and very simple in structure. Because of this, current sequence miners are not able to find patterns with certain complexity restrictions such as minimal length. Secondly, prefix enumeration techniques usually provide numerous sequences as a result of the mining process. In this regard, we may be interested in a subset of the results using notions of maximality (what are known as closed subsequences) which provide a succinct representation of the patterns in a database (CloSpan, ClaSP or BIDE [START_REF] Yan | Clospan: Mining: Closed sequential patterns in large datasets[END_REF][START_REF] Wang | BIDE: efficient mining of frequent closed sequences[END_REF][START_REF] Gomariz | ClaSP: An Efficient Algorithm for Mining Frequent Closed Sequences[END_REF]).

In this article we present a novel approach for rare subsequence mining using the FCA framework. We adapt the pattern structures extension to deal with complex object descriptions [START_REF] Ganter | Pattern structures and their projections[END_REF] to build a mining tool that naturally models "closed sequences". By defining a similarity operator between sequence sets we are able to derive a rare sequence mining tool that is able to retrieve large subsequences within a dataset.

The remainder of this article is organized as follows. Section 2 introduces the main notions behind the problem of sequence mining. Section 3 models the problem in the framework of pattern structures. Section 4 formalizes the implementation of our mining technique. Section 5 presents a discussion on the stateof-the-art algorithms for sequence mining. Section 6 presents the experimental evidence to support our findings and a discussion about their implications. Finally, Section 7 concludes the article with a summary of our work.

Formalization

Before introducing our contributions, let us provide some basic definitions of the sequence mining problem. Let M be a set of items or symbols, a sequence of itemsets is an ordered set denoted as < α 1 , α 2 , α 3 ..., α n > where α i ⊆ M, i ∈ [1, n]. Alternatively, we will use a bar notation α 1 |α 2 |α 3 |...|α n . A sequence with ID (SID) α is denoted as α := α 1 |α 2 |α 3 |...|α n and is referred as well as sequence α. The size of sequence α is denoted as size(α) = n while its length is denoted as len(α) = |α i | with i ∈ [1, n] where | • | indicates set cardinality. A set of sequences A is called a sequence database. For the sake of simplicity we will drop the set parentheses for the itemsets within a sequence using the bar notation, e.g. {a, b}|{c, d} is denoted as ab|cd.

Definition 1 Subsequence. Sequence β := β 1 |β 2 |....|β m is a subsequence of sequence α := α 1 |α 2 |...|α n (denoted as β α) iff m ≤ n and if there exists a a sequence of natural numbers i 1 < i 2 < i 3 < ... < i m such that β j ⊆ α ij with j ∈ [1, m] and i j ∈ [1, n].
We denote as β ≺ α when β α and β = α. For example, consider sequence β := a|b|a and sequence with SID α 2 in Table 1. In this particular case, there exists a sequence of numbers 1, 3, 4 where we have: The first itemset of β is a subset of the first itemset of α 2 ({a} ⊆ {a, d}). The second itemset of β is a subset of the third itemset of α 2 ({b} ⊆ {b, c}). The third itemset of β is a subset of the fourth itemset of α 2 ({a} ⊆ {a, e}). We conclude that β ≺ α 2 (since β = α 2 ). Given a sequence database A we will consider the set of all sub-sequences of elements in A denoted as S where β ∈ S ⇐⇒ ∃α ∈ A s.t. β α (A ⊆ S). Definition 2 Support of a sequence. Let β ∈ S be a sequence. The support of β w.r.t. A is defined as:

σ(β) = |{α ∈ A | β α}| With β := a|b|a we have that β ≺ α 1 , α 2 and thus σ(β) = 2. Definition 3 Closed Sequence. β 1 ∈ S is a closed sequence w.r.t A iff β 2 ∈ S such that β 1 ≺ β 2 and σ(β 1 ) = σ(β 2 ).
Consider sequences β 1 := a|b|a and β 2 := a|bc|a as subsequences of elements in A of Table 1. It is easy to show that σ(β 2 ) = 2. Given that β 1 ≺ β 2 and that they have the same support, we conclude that β 2 is not a closed sequence w.r.t.

A = {α 1 , α 2 , α 3 , α 4 }.
When mining subsequences, those that are closed in the sense of Definition 3 provide a succinct result, critically compacter than the set of all possible subsequences [START_REF] Yan | Clospan: Mining: Closed sequential patterns in large datasets[END_REF][START_REF] Wang | BIDE: efficient mining of frequent closed sequences[END_REF]. Consequently, in what follows we will be interested only in sets of closed sequences.

3 The Pattern Structure of Sequences.

The pair (S, ) composed of a sequence set and a subsequence order constitutes a partially ordered set. However, it does not conform a proper lattice structure, since in general, two sequences have more than one common subsequence (the infimum of two sequences is not unique).

In the context of sequence mining, this fact has been already noticed in [START_REF] Zaki | SPADE: An Efficient Algorithm for Mining Frequent Sequences[END_REF], where the space of sequences and their order is denominated a hyper-lattice. In the context of FCA, this problem is analogous to the one introduced in [START_REF] Ganter | Pattern structures and their projections[END_REF] for graph pattern mining. Indeed, we can properly embed the hyper-lattice of partially ordered sequences into a lattice of sequence sets using the framework of pattern structures. Definition 4 Set of Closed Sequences. Let d ⊆ S be a set of sequences, we call d + ⊆ d a set of closed sequences iff

d + = {β i ∈ d | β j ∈ d s.t. β i ≺ β j }.
The intuition behind Definition 4 is that given a set of sequences d, we can consider every sequence inside it as having the same support. Thus, d + contains closed sequences in the sense of Definition 3. Definition 5 Set of Common Closed Subsequences (SCCS). Consider two sequences β i , β j ∈ S, we define their meet ∧ as follows:

β i ∧ β j = {β ∈ S | β β i and β β j } +
Intuitively, β i ∧ β j corresponds to a set of common subsequences to β i and β j . As indicated by the notation, we will require this set to contain only closed sequences (Definition 4) and thus we will denote it as the set of common closed subsequences (SCCS) of β i and β j . Definition 6 SCCS for sequence sets. Given two sets of closed sequences d 1 , d 2 ⊆ S, the similarity operator between them is defined as follows:

d 1 d 2 = β i ∈d 1 β j ∈d 2 β i ∧ β j +
In a nutshell, is the SCCS between the elements within two sets of closed sequences. Let D = {d ⊆ S | d = d + } denominate the set of all sets of closed sequences in S , then we have ∧ : S 2 → D and : D 2 → D.

For a sequence β ∈ S, δ(β) = {β i ∈ S | β i β} + denotes its set of closed subsequences. Trivially, the set of closed subsequences of a single sequence β contains a single element which is itself, i.e. δ(β) = {β}. From this, it follows that given any three sequences β i , β j , β k ∈ S we have that β i ∧β j = δ(β i ) δ(β j ) and (δ(β i ) δ(β j )) δ(β k ) properly represents the SCCS of β i , β j and β k . For example, consider sequences with α 1 and α 3 in Table 1.

δ(α 1 ) δ(α 3 ) = {a|abc|ac|d|cf } {ef |ab|df |c|b} = {ab|d|c, ab|f, a|b}
Clearly, is idempotent and commutative as it inherits these properties from ∧. Furthermore, it can be easily shown that is also associative. Using these properties, we can provide a more complex example. Consider δ(α 1 ) δ(α 2 ) δ(α 3 ) δ(α 4 ) from Table 1. Since we already have the result for δ(α 1 ) δ(α 3 ), we re-arrange and proceed as follows:

δ(α 1 ) δ(α 2 ) δ(α 3 ) δ(α 4 ) = (δ(α 1 ) δ(α 3 )) (δ(α 2 ) δ(α 4 )) δ(α 1 ) δ(α 3 ) = {ab|d|c, ab|f, a|b} δ(α 2 ) δ(α 4 ) = {a|c|b, a|c|c, e}
Now, we need to calculate {ab|d|c, ab|f, a|b} {a|c|b, a|c|c, e} which requires 9 SCCS calculations. We show those with non-empty results. The union of these results gives us {a, b, a|b, a|c} from which we remove a and b which are not closed subsequences in the set. Finally, we have:

δ(α 1 ) δ(α 2 ) δ(α 3 ) δ(α 4 ) = {a|b, a|c}
Indicating that the set of closed subsequences common to all sequences in Table 1 only contains a|b and a|c. Definition 7 Order in D. Let d 1 , d 2 ∈ D, we say that d 1 is subsumed by d 2 (denoted as d 1 d 2 ) iff:

d 1 d 2 ⇐⇒ ∀β i ∈ d 1 ∃β j ∈ d 2 s.t. β i β j d 1 d 2 ⇐⇒ d 1 d 2 and d 1 = d 2
Proposition 1 Semi-lattice of sequence descriptions. Let D be the set of all sets of closed sequences (hereafter indistinctly referred to as "the set of sequence descriptions") built from itemset M. The pair (D, ) is a semi-lattice of sequence descriptions where

d 1 d 2 ⇐⇒ d 1 d 2 = d 1 for d 1 , d 2 ∈ D. The proof of d 1 d 2 ⇐⇒ d 1 d 2 = d 1 in
Proposition 1 is straightforward and follows from Definitions 6 and 7.

Definition 8

The pattern structure of sequences. Let A be a sequence database, (D, ) the semi-lattice of sequence descriptions and δ : S → D a mapping assigning to a given sequence its corresponding set of closed subsequences (recall that A ⊆ S). The pattern structure of sequences is defined as:

K = (A, (D, ), δ)
For the sake of brevity we do not provide the development of the pattern structure framework which can be found in [START_REF] Ganter | Pattern structures and their projections[END_REF]. However, let us introduce some concepts and notation that will result important in the remainder of the article. The pair (A, d) with A ⊆ A and d ∈ D is a sequence pattern concept where A = d and d = A. The derivation operator (•) is defined dually for extents and pattern descriptions. The order of sequence pattern concepts is denoted as

(A 1 , d 1 ) ≤ K (A 2 , d 2 ) iff A 1 ⊆ A 2 and d 2 d 1 where A 1 , A 2 ⊆ A and d 1 , d 2 ∈ D.
Finally, the set of all sequence pattern concepts with the order ≤ K defines a sequence pattern concept lattice denoted as (B(K), ≤ K ).

Within a sequence pattern concept we have that d = d, i.e. the set of sequences d is closed. This should not be confused with the notion of set of closed sequences given in Definition 4 which is a property of the elements inside d. Actually, d is a set of common closed subsequences (SCCS) when d + = d. With this new constraint, the correct denomination for d would be a closed set of common closed subsequences. To avoid confusions, hereafter we will denominate a set d such that d + = d and d = d as a maximal SCCS. A sequence pattern concept represents a set of sequences A in the database and their maximal SCCS, i.e. closed subsequences of elements in A are contained in d. Consider from the previous example that {e|a|c|b} = {α 3 , α 4 }. Now, we can calculate {α 3 , α 4 } = {e|a|c|b, e|f |c|b, e|b|c, f |b|c}. From this it follows that {e|a|c|b} is not a maximal SCCS and that ({α 3 , α 4 }, {e|a|c|b, e|f |c|b, e|b|c, f |b|c}) is a sequence pattern concept. Figure 1 shows the sequence pattern concept lattice built from entries in Table 1. The bottom concept in the figure is a fake element in the lattice since there is no definition for the meet between pattern concepts. We have included it to show that it represents the concept with empty extent, i.e. the "subsequences of no sequences". The indefinition of the meet between formal concepts also means that we can only join sequence pattern concepts starting from object concepts γ(α) = ({α}, δ(α)). Consequently our mining approach is a rare sequence mining technique.

The concept lattice structure allows proving a characterization of an important property of sequences, namely we can show that all sequences in an intent are closed w.r.t. the database A. Proposition 2 Given a sequence pattern concept (A, d) any sequence β ∈ d is not only closed w.r.t. A but it is also closed w.r.t. A.

Proof. Consider two sequence pattern concepts (

A 1 , d 1 ), (A 2 , d 2 ) ∈ B(K) such as (A 1 , d 1 ) < K (A 2 , d 2 ) (then A 1 ⊂ A 2 and d 2 d 1 ). Particularly, the latter relation indicates that ∀β j ∈ d 2 ∃β i ∈ d 1 s.t. β j β i and d 1 = d 2 (Definition 7). In the case that β j ≺ β i , the fact that A 1 ⊂ A 2 =⇒ |A 1 | < |A 2 |
secures that both sequences have different supports making β j closed. In the case that β j = β i , there are two different cases. Either a third concept (A 3 , d 3 ) ∈ B(K) exists such that (A 2 , d 2 ) < K (A 3 , d 3 ) where β j ∈ d 2 and β j / ∈ d 3 and thus, we fall in the previous case and β j is closed, or β j ∈ A and β j is closed with support |A|. Indeed, since (A ) = (A ) + , any β ∈ A is closed w.r.t. A, even when we may not know the support for that particular sequence. Moreover, the support of any closed sequence β is given by the cardinality of the extent of the concept (A 1 , d 1 ) where

β ∈ d 1 s.t. (A 2 , d 2 ) where (A 1 , d 1 ) < K (A 2 , d 2 ) and β ∈ d 2 .
For example, consider Figure 1 and the concept labelled as {α 1 , α 2 } containing sequence a|c|c. While we can be sure that a|c|c is a closed subsequence w.r.t. A, the support is not 2. Actually, a|c|c exists also in the intent of the concept labelled {α 1 , α 2 , α 4 }. Since it does not exists in the suprema (the only superconcept of the latter), we can conclude that the support of a|c|c is 3.

Finally, we briefly mention the pattern complexity filtering capabilities of our approach. For a relation (A 1 , d 1 ) < K (A 2 , d 2 ), sequences in d 2 will be shorter and with fewer items per itemset than those in d 1 . Given thresholds for size and lenght, the sequence search space can be pruned similarly to support pruning .

Implementing the similarity operator

So far we have taken for granted the ability to calculate the set of common closed subsequences (SCCS) of two sequence sets (i.e. d 1 d 2 ). In what follows, we will describe and discuss our approach to achieve this.

Rationale

Sequences are composed of two parts, firstly the elements in the sequence and secondly, the order they have. Considering the latter, we can think about how a "common subsequence" (an element in the SCCS) β of two sequences β 1 , β 2 relates to them. Given the definition of subsequence (Definition 1), since β β 1 we have a sequence of integers i

1 1 < i 1 2 < i 1 3 < ... < i 1 m such that β j ⊆ β 1 ij with i 1 j ∈ [1, n] and j ∈ [1, m] with size(β) = m, size(β 1 )
= n, and m < n. A similar sequence of integers can be derived from the relation β β 2 , namely i 2 1 < i 2 2 < i 2 3 < ... < i 2 m . Since both sequence of integers have the same length, we can arrange them in a sequence of tuples P = (i 1 1 , i 2 1 ), (i 1 2 , i 2 2 ), . . . , (i 1 m , i 2 m ) . Furthermore, given that β j ⊆ β 1 ij and β j ⊆ β 2 kj , it is only natural to define

β j = β 1 ij ∩ β 2 kj (notice that defining β j ⊂ β 1 ij ∩ β 2
kj would render β not a closed sequence). Consequently, tuple P is a possible characterization of β in terms of its parents supersequences β 1 and β 2 . Actually, given any set of sequences A, a common subsequence of them β ∈ A has one or more characterizations P .

Generally, we call P := t 1 , t 2 , . . . , t m an alignment with size m of sequences in A where r = |A|, n k is the size of the k-th sequence in A with k ∈ [1, r], t j = (i k j ), and j ∈ [1, m] (t j ∈ {1, 2, . . . , n} r ). Furthermore, we will require that with k ∈ [1, r] and j ∈ [1, (m -1)] we have that:

(i) (∃i k 1 ∈ t 1 ) s.t. i k 1 = 1, (ii) (∃i k m ∈ t m ) s.t. i k m = n k , (iii)(∃i k j+1 ∈ t j+1 ) s.t. i k j+1 = i k j + 1, and (iv) (∀i k j+1 ∈ t j+1 ) i k j < i k j+1
. Conditions (i), (ii) and (iii) secure that alignments always begin with the first element of at least one sequence in A, always end with the last element of a least one sequence in A, and that they are maximal, e.g. (1, 1), [START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF][START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF] is not a maximal alignment if (1, 1), (2, 2), (3, 3) exists. Condition (iv) secures that alignments only consider incremental tuples, e.g. (1, 2), (2, 1) is not an alignment. P r n is the space of all maximal alignments of sequences in A. It is possible to show that |A | ≤ |P r n | provided that conditions (i), (ii), (iii) and (iv) hold for alignments in P r n and that |M| = n r . This is demonstrated by showing that there exists a scenario (however unlikely) where for each different closed subsequence there exists a unique alignment, i.e. (∀β ∈ A )(∃! t 1 , t 2 , . . . , t m ∈ P r n ) s.t. β j = α i t i j = π(t j ) where π : N r → N is pairing function encoding tuples in {1, 2, . . . , n} r into M = {π(t j ) | t j ∈ {1, 2, . . . , n} r }. Thus, given a set of sequences A we only need to compute all possible alignments in order to obtain their complete set of common closed subsequences A (SCCS). Notably, this relation allows calculating the number of possible closed subsequences between two sequences of arbitrary length4 . Table 2 shows this number with n ∈ [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Pei | PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth[END_REF]. For example, for two sequences of size 10 we have a maximum of 26797 alignments/closed subsequences (requiring |M| = 2 10 = 1024 items).

Enumerating all possible alignments may look an extremely naive strategy considering how the space of alignment grows w.r.t. the number of sequences in A and their size, however the way we encode alignments makes the representation of subsequences more compact than simply listing them. In addition, the sparsity of sequence element intersections (most β j = β 1 ij ∩β 2 kj are empty) provides a very efficient pruning method. In the following, we show how to encode alignments in P r n as paths of a directed acyclic graph (DAG). Definition 9 DAG of Alignments. We call G r n = (V, E, λ) a directed acyclic graph of alignments P r n (DAG of alignments) for a set of r sequences A ⊆ A of size n, if the set of vertices,edges and labelling function λ : V → ℘(M) are:

V = {t j = i k j | t j ∈ {1, 2, . . . , n} r } ∪ {0 r , (n + 1) r } E = {(t a , t b ) ⇐⇒ (∃i k b ∈ t b ) i k b = i k a + 1 and (∀i k b ∈ t b ) i k a < i k b } λ(t j ) = i∈[1,r] α i i i j 0 r , (
n+1) r are r-tuples filled with 0 and n+1 values respectively. We denominate 0 r the source vertex (or source node) and (n + 1) r the sink vertex (or sink node).

Notice that conditions (iii) and (iv) for alignments in P r n described above are encoded in the definition of edges E in G r n . The inclusion of the source and sink nodes ensure that all paths between them corresponds to alignments in P r n that also respect conditions (i) and (ii). Thus, the DAG G r n is designed so that all possible maximal alignments among r sequences of size n correspond to paths between the source and sink nodes. In addition, all possible common subsequences can be read from the graph by means of the labelling function λ. Trivially, for a set of sequences with different sizes, a DAG of alignments can be built with n corresponding to the maximal sequence size in the set. Figure 2 shows the DAG G 2 4 without labels, where the number of paths between (0, 0) and (5, 5) is 27 (as predicted by Table 2).

Calculating

δ(α 1 ) δ(α 2 )
Consider sequences α 1 = ab|cd|e|f , α 2 = b|ac|d|ef and their itemset intersections shown in Table 3 (empty cells indicate an empty intersection) Since both sequences have size 4, we can use the DAG G 2 4 shown in Figure 2 to obtain all possible alignments between these sequences. Then, we can derive associated subsequences using the labelling function given by Table 3. In these subsequences the SCCS must be included. In this case more than half the itemset intersections are empty which makes the task of deriving paths easier. Figure 3 shows a subgraph of G 2 4 , where vertex (i, j) is labelled as λ((i, j)) = α 1 i ∩ α 2 j . Vertices v ∈ V for which λ(v) = ∅ were removed from Figure 3. We have also connected (2, 2) with (4, 4) since vertex (3, 3) is among those vertices removed.

(0, 0) (1, 1) (2, 2) (3, 3) (4, 4) (5, 5) (1, 2) (2, 1) (1, 3) (3, 1) (1, 4) (4, 1) (2, 3) (3, 2) (2, 4) (4, 2) (3, 4) (4, 3)
A path between (0, 0) and (5, 5) is (1, 1), (2, 2), (4, 4) (removing the source and sink nodes). Thus, a subsequence can be derived using the labels of the vertices in the path, i.e. β = λ((1, 1))|λ((2, 2))|λ((4, 4)) or β = b|c|f . All the subsequences of α 1 and α 2 are shown in Table 4 from which we can derive that the SCCS of α 1 and α 2 is δ(α 1 ) δ(α 2 ) = {b|c|e, b|c|f, b|d|e, b|d|f, a|d|e, a|d|f }.

This result illustrates the usefulness of the DAG of alignments in Figure 2. Indeed, instead of enumerating all possible sequences (like in usual subsequence mining algorithms) we just need to intersect the itemsets of two sequences and later interpret them using the corresponding DAG.

To extend the example, let us consider a third sequence α 3 = ab|c|d|ef and the SCCS of α 1 , α 2 and α 3 . We need to calculate the table of intersections that in this case corresponds to a cube of intersections where the cell (i, j, k) in the cube contains α 1 i ∩ α 2 j ∩ α 3 k . While the construction of this cube requires 4 3 = 64 intersections, using the results in Table 4 we need only to calculate 24 intersections (those with empty intersections in Table 4 can be disregarded). Using the DAG of alignments G 3 4 , we can obtain the SCCS such that δ(α 1 ) δ(α 2 ) δ(α 3 ) = {b|c|e, b|c|f, b|d|e, b|d|f, a|d|e, a|d|f }.

Discussion

In the previous example, one important thing to notice is that we did not need to interpret the sequences from the intersection table of d = {α 1 , α 2 } in order to calculate d δ(α 3 ). This information is encoded in the table itself in the form of Table 3. Intersection table for sequences α 1 = ab|cd|e|f and α 2 = b|ac|d|ef . 4. List of paths in the DAG of Figure 3 and subsequences derived.

α 2 1 α 2 2 α 2 3 α 2 4 α 1 1 b a α 1 2 c d α 1 3 e α 1 4 f Table
Path Sequence (1, 1), (2, 2), [START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF][START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] b|c|f (1, 1), (2, 2), [START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF][START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] b|c|e (1, 1), [START_REF] Ayouni | Mining closed gradual patterns[END_REF][START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF], [START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF][START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] b|d|f (1, 1), (2, 3), [START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF][START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] b|d|e (1, 2), (2, 3), [START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF][START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] a|d|e (1, 2), (2, 3), [START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF][START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] a|d|f index tuples of the itemsets we had intersected and can be recovered at any time using the corresponding DAG. Nevertheless, we are not spared from interpreting the sequences out of the table of intersections. This is because we still need the sequences to establish the order between two sequence sets. We have not found a property that would allow us to compare sequence sets from their intersection tables or from their DAG of alignments. Actually, this may not be possible. In this work we use the DAG of alignments just as a tool to explore and store the space of common closed subsequences. Implementation details of the DAG (such as the canonical order in the node tuples) were left out of the scope of this article for the sake of brevity, as well as some other elements of the search space exploration, e.g. the DAG allows filtering out sequences below a threshold of size and length.

(0, 0) b (1, 1) c (2, 2) f (4, 4) (5, 5) a (1, 2) d (2, 3) e (3, 4)

Related Work

Sequence mining is usually based on what is called "prefix enumeration" or "pattern growth". This is, given a vocabulary M and a lexicographical order in it, we proceed by enumerating prefixes (using two main operations, namely iextension and s-extension of sequences) and counting in a sequence database A how many elements contain them. The seminal paper in sequence mining is [START_REF] Agrawal | Mining sequential patterns[END_REF] introduces an Apriori-based algorithm to cut down the search space in a similar way to how it is done for standard itemset mining. A very popular extension of this idea was implemented in the PrefixSpan algorithm [START_REF] Pei | PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth[END_REF] using the notion of "projected databases" to decrease the number of comparisons in the database of sequences to calculate pattern support. PrefixSpan inspired different extensions such as CloSpan [START_REF] Ganter | Pattern structures and their projections[END_REF] to mine closed subsequences, OrderSpan [START_REF] Fabrègue | Mining closed partially ordered patterns, a new optimized algorithm[END_REF] to mine partiallyordered subsequences, and CCSpan [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF] to mine subsequences with a restriction of "contiguity" in the items they contain.

A different approach was taken in [START_REF] Zaki | SPADE: An Efficient Algorithm for Mining Frequent Sequences[END_REF] using a "vertical database format" in an algorithm called SPADE (PrefixSpan-based algorithms are considered based on a "horizontal database format"). A rather interesting element of [START_REF] Zaki | SPADE: An Efficient Algorithm for Mining Frequent Sequences[END_REF] is the characterization of the sequence search space as a hyperlattice which can be factored allowing parallel computation of patterns. A similar approach was adopted in BIDE [START_REF] Wang | BIDE: efficient mining of frequent closed sequences[END_REF] and ClaSP [START_REF] Gomariz | ClaSP: An Efficient Algorithm for Mining Frequent Closed Sequences[END_REF] for closed subsequence mining based on a vertical database format.

Partially-ordered subsequences is an idea introduced in [START_REF] Casas-Garriga | Summarizing sequential data with closed partial orders[END_REF] based on the notion that the subsumption order among sequences allows integrating different subsequences into a single pattern by means of a directed acyclic graph, which may provide a richer representation to an end user. This is closely related to our own model for sequence mining. Indeed, our own representation of sequence sets is through the DAG of alignments which are themselves partially-ordered patterns. This work inspired Frecpo [START_REF] Pei | PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth[END_REF] and OrderSpan [START_REF] Fabrègue | Mining closed partially ordered patterns, a new optimized algorithm[END_REF] for mining closed partially-ordered subsequence patterns.

A comprehensive review on the sequence pattern mining techniques can be found in [START_REF] Mooney | Sequential pattern mining -approaches and algorithms[END_REF]. To the author's knowledge, our work is the first attempt to ap-proach the problem of sequence mining in a general unrestricted manner using the framework of formal concept analysis. In this regard, an interesting work is presented in [START_REF] Ayouni | Mining closed gradual patterns[END_REF] where an FCA-based technique for mining Gradual patterns is introduced. Gradual patterns consider a total order between attribute values generating sequences of objects. The technique introduced allows characterizing sequences derived from these gradual patterns. However, much like BIDE, sequences are restricted to strings of elements, not sequences of itemsets. In [START_REF] Buzmakov | On Projections of Sequential Pattern Structures (with an application on care trajectories)[END_REF], a different sequence mining framework based on pattern structures is introduced for dealing with medical records. These sequences contain complex elements composed of taxonomical elements and attribute sets. The authors decided to simplify the problem by considering subsequences containing just contiguous elements.

Experiments & Discussion

In this section, we present an experimental evaluation on our sequence mining approach over a series of synthetic datasets generated using the IBM Quest Dataset Generator software hosted in the SPMF Website5 . Our approach was implemented in Python and embedded into a system named Pypingen available through a subversion repository6 .

Datasets and experimental setup

Pypingen was applied over 34 different datasets in 4 four groups. Each group allows showing how our algorithm handle different settings. The first group, denoted as D nseqi , i ∈ [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Gomariz | ClaSP: An Efficient Algorithm for Mining Frequent Closed Sequences[END_REF], contains datasets of different size |A|, i.e. the number of sequences inside a dataset. The second group, D nitemsi , i ∈ [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Yan | Clospan: Mining: Closed sequential patterns in large datasets[END_REF], contains datasets where the size of the itemset |M| varies. The third group, D sizei , i ∈ [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Mooney | Sequential pattern mining -approaches and algorithms[END_REF], contains datasets of sequences that have different average sizes mean(size), i.e. number of itemsets in a given sequence. Finally, the last group, D lengthi , i ∈ [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Ganter | Pattern structures and their projections[END_REF], consists of datasets where sequences have a varying average number of items by itemset, i.e. a variation in the length of sequences mean(length/size) for a fixed size. Table 5 displays the different settings for each synthetic dataset generated. The variation in the parameters is a consequence of considering outputs that took less than 15 minutes to calculate. Experiments were performed on a 3.10 GHz processor with 8 GB main memory running Ubuntu 14.04.1 LTS.

Performance study -Comparison

All 34 datasets were also processed using "closed sequence pattern mining" algorithms ClaSP, CM-ClaSP, CloSpan and BIDE implemented in the SPMF soft-ware 7 (written in Java) under the same conditions of the execution of Pypingen. Algorithms were given a threshold value of 0 to obtain all closed sequence patterns. From all four algorithms, only CloSpan and BIDE were able to obtain results in less than 15 minutes. However, we do not report on these results for two reasons. Firstly, with respect to CloSpan, it was only able to obtain results for just a single dataset, namely D length1 which is the simplest. Secondly, with respect to BIDE, even when it was able to obtain results in less time, these results were incorrect and incomplete. This is due to the fact that even when BIDE is catalogued as a "closed sequence miner", its formalization actually corresponds to that of a "closed string miner", that is, sequences where each itemset has cardinality 1. This simplification of the problem greatly reduces the search space and makes any comparison unfair. More importantly, in datasets where this condition is not met such as those in our evaluation, it produces incorrect (in the form of non-closed sequences) and incomplete results.

Execution times for Pypingen can be visualized in Figure 4 (execution times are given in logarithmic scale). The curves presented are consistent with the description of the algorithm. Runtimes when varying the size of the sequences (Figure 4c) grow exponentially due to the fact that the search space grows w.r.t. n r where |A| = r and n is the maximum size of the sequences in the dataset. When varying the sequence length (Figure 4d), the search space does not change (it remains at n r which in this case is 5 36 ). However, the larger the itemset cardinalities, the less empty intersections we can expect in the intersection table, and thus, the more closed subsequences for a sequence set.

Figure 4a is very interesting because it is more related to scalability. We can see that as the number of sequences grows, the time grows polynomially and not exponentially, which is desirable for a mining technique. Finally, Figure 4b 7 Version 0.97d / 0.97e -2015-12-06 Table 5. Characteristics of the datasets where |A| is the number of sequences in the dataset, |M| the cardinality of the set of items or symbols, mean(size) the average size of the sequences of the dataset and mean(length/size) the average number of items in the itemsets of the sequences. shows that the execution time gets lower as the cardinality of itemset M gets larger. Indeed, since the remainder dataset parameters are left unchanged, the increase in the number of possible items leads to sparser datasets where most intersections are empty.

Figure 5 presents the relation between the number of closed subsequences and the execution time to calculate them using Pypingen over 1200 different synthetic datasets (each circle represents a dataset) created for 60 different configurations of vocabulary size (M), average size of sequences and average length of itemsets. All datasets contained only 10 sequences (|A| = 10). Axes in the figure are provided in logarithmic scale, while the curve is the best fit to the data w.r.t. the coefficient of determination R 2 = 0.97 (a quadratic curve has R 2 = 0.78 while an exponential has R 2 = 0.29). We can appreciate that the curve is a power function with an exponent very close to 1 indicating a quasilinear relation between the number of closed sequences in a dataset and execution time required to calculate them, which is a desirable property for a pattern mining algorithm. Nevertheless, the performance of the algorithm slowly degrades as the number of patterns in a dataset increases. The radius of each point in the figure represents the ratio between the number of closed sequences and the number of sequence patterns found for that dataset.

Discussion

Algorithms CloSpan, ClaSP, CM-ClaSP and BIDE are frequent sequence miners, while Pypingen is a rare sequence miner. This means that the only "fair" comparison requires for all algorithms to explore the entire search space and mine all possible closed sequences. Under this circumstances, Pypingen clearly outperforms all of them as they are not able to achieve this task for all but one dataset in our experiments.

Arguably, our comparison can be understood as "fair" considering that all the algorithms are set to the worst case scenario. Frequent mining algorithms are designed under the assumption that results are in the "upper" part of the search space. Thus, asking them to explore the entire search space goes against the very assumption behind their designs and it becomes unfair to evaluate their performance under the worst of the conditions. On the other hand, Pypingen was designed to begin its search from the "bottom" part of the search space and thus, it is also an evaluation in the worst case scenario. The conclusion that follows is that, compared with the state-of-the-art algorithms, Pypingen is able to explore a much larger region of the search space.

It is clear nonetheless that given a large enough dataset Pypingen will not be able to explore the entire search space and thus, it will be unable to mine frequent subsequences. Under these circumstances, frequent miners have the advantage of obtaining a set of results out of reach for a rare pattern miner such as Pypingen. In this light, we highlight the benefits of our approach. Like frequent miners use a threshold for support, we can provide a threshold for sequence size to mine large sequences. Using a proper value for this threshold, we can obtain all sequences for this restriction and particularly, those that are most frequent. Mining this type of frequent large sequences is not possible for frequent miners. Another threshold that Pypingen can easily support is the minimum cardinality per itemset of a sequence pattern, adding in the capabilities of restricting the complexity of the desired patterns.

Finally, one of the main features of Pypingen is its flexibility. Consider the intersection table that we use to generate the DAG of alignments such as the one shown in Table 3. In here, the intersection operation may be easily replaced by an abstract similarity operator that holds under idempotence, commutativity and associativity to support sequences of elements other than itemsets, in the same way that it is done when defining pattern structures. Such adaptation would allow supporting sequences of complex elements such as intervals, taxonomical elements or heterogeneous representations [START_REF] Kaytoue | Pattern structures and concept lattices for data mining and knowledge processing[END_REF]. This kind of sequences of complex elements would be hard to mine in current sequence mining algorithms designed for prefix enumeration.

Conclusions

In this article we have introduced the main notions behind rare sequence pattern mining using the framework of formal concept analysis, particularly the "pattern structures" extension to deal with complex object descriptions. Indeed, we have modelled patterns as sequence sets where the similarity operator allows formalizing an algorithm for extracting closed subsequences.

We have shown how the similarity operator can be implemented using a directed acyclic graph (DAG) of sequence alignments where a set of sequences can be easily encoded. The DAG of alignments also allows for an easy interpretation of sequence patterns as well as for pruning procedures that allows cutting down the search space.

We have implemented our approach in a system called Pypingen and showed that w.r.t. state-of-the-art closed sequence mining algorithms, it performs better in the worst of the cases, this is, when obtaining the full set of closed subsequences from a database.

Finally, we have discussed the implications of our system and its possible extensions regarding the mining of sequences composed by elements other than itemsets.

  ab|d|c ∧ a|c|b = {a|c, b} ab|d|c ∧ a|c|c = {a|c} ab|f ∧ a|c|b = {a, b} ab|f ∧ a|c|c = {a} a|b ∧ a|c|b = {a|b} a|b ∧ a|c|c = {a}

Fig. 2 .

 2 Fig. 2. DAG for the alignments of two sequences of size 4

Fig. 3 .

 3 Fig. 3. DAG for sequences α 1 = ab|cd|e|f, α 2 = b|ac|d|ef .

Fig. 4 .

 4 Fig. 4. Runtimes results for each dataset group.

yFig. 5 .

 5 Fig. 5. Number of closed subsequences vs execution time for 1200 datasets.

Table 1 .

 1 An example sequence database.

		{α 1 , α 3 }
		{ab|d|c,
		ab|f, a|b}
		{α 1 }	{α 2 }	{α 3 }	{α 4 }
	sid Sequence	{a|abc|ac|d|cf }	{ad|c|bc|ae}	{ef |ab|df |c|b}	{e|g|af |c|b|c}
	α 1 a|abc|ac|d|cf
	α 2 ad|c|bc|ae
	α 3 ef |ab|df |c|b α 4 e|g|af |c|b|c	Fig. 1. Extents & Intents of the sequence pattern structure built from Table 1.

Table 2 .

 2 Number of maximal alignments for n ∈ [1, 10].

	n |P 2 n |
	1	1
	2	3
	3	9
	4 27
	5 83
	6 259
	7 817
	8 2599
	9 8323
	10 26797

{α 1 , α 2 } {a|c|c, a|bc|a, d|c} {α 1 , α 4 } {a|c|c, a|b|c} {α 2 , α 3 } {a|c|b, d|c|b, e} {α 2 , α 4 } {a|c|b, a|c|c, e} {α 3 , α 4 } {e|a|c|b, e|b|c, e|f |c|b, f |b|c} {α 1 , α 2 , α 3 } {a|c, a|b, d|c} {α 1 , α 2 , α 4 } {a|c|c, a|b} {α 1 , α 3 , α 4 } {a|b, a|c, b|c, f } {α 2 , α 3 , α 4 } {a|c|b, e} {α 1 , α 2 , α 3 , α 4 } {a|b, a|c} ∅

https://oeis.org/A171155

Open-source data mining libraryhttp://www.philippe-fournier-viger.com/ spmf/

http://gforge.inria.fr/projects/pypingen


Marcus Beck

Paul Uwe Thamsen
email: paul-uwe.thamsen@tu-berlin.de

How to design a centrifugal pump with constant power consumption for all flow rates

Keywords:

INTRODUCTION

The power consumption of centrifugal pumps depends mainly on the type of impeller. Typically it increases with the flow rate of radial impellers and it decreases with the flow rate of axial impellers. However, as shown in Figure 1, each type of impeller shows a significant maximal power consumption, which defines the adequate motor power for the driver. Constant power consumption for a centrifugal pump is a new approach for impeller design because until today design of centrifugal pumps is focused on high efficiency performance. Additional challenge for this project was the application of a drum pump, which is a relative small pump with an impeller diameter of about 38 mm. It is known, that the design method for such small pump deviates significantly from the standard design process, whereas the slip factor is much higher.

Liu, Nishi and Yoshida [START_REF] Liu | Impeller Geometry Suitable for Mini Turbo Pump[END_REF] report about new semi-axial impeller designs for mini pumps and Bischoff [START_REF] Bischoff | Miniaturisierte Hochdrehzahl-Kühlmittelpumpen für Kfz-Motoren[END_REF] presents the design process for small cooling pumps. Mini pumps have limited efficiency, so other priorities like small motor size are interesting too.

Semi-axial impellers already show relative horizontal power consumption. Gülich [START_REF] Gülich | Centrifugal pumps -Detailed design procedures for pumps[END_REF] presents a diagram in his book, which recommends a specific speed of about n q = 100 as a good starting point (Figure 2). The onset and behaviour of recirculation at part load has a tremendous influence on the Head generation as well as the power consumption at part load for semi-axial pumps. This is reported in Troskolanski et. al. [START_REF] Troskolanski | Kreiselpumpen -Berechnung und Konstruktion[END_REF] and also in Gülich [START_REF] Gülich | Centrifugal pumps -Detailed design procedures for pumps[END_REF]. The later introduces a recirculation power as a power loss that is demonstrated in Figure 4. The left sides of the diagrams show the large influence of part load recirculation on the power consumption. So it is obvious to focus on this effect to design the impeller for constant power consumption. There are only few aspects reported to influence recirculation flow:

decreasing impeller inlet diameter d s decreasing inlet cross section d s /d 1i -generate rotation before inlet increasing blade inlet diameter d 1i -changing inlet cross section of diffuser Because of its complex 3d-characteristic until today recirculation flow and the influence on power curves is not completely understand.

PUMP DESIGN

Standard impellers of drum pumps are typically radial for low flow and higher pressure or axial for large flow and moderate head. The electrical motor is selected due to maximum power consumption of the pump, which is for both impeller types significantly above the required consumption for the duty point. Additionally the speed of the motor follows the power consumption curve, so at high motor load, the speed of the motor and moreover the speed of the cooling fan is low. This affects the cooling of the motor and its lifetime.

The constant power consumption requires obviously a semiaxial design, which also gives the advantage of only one universal impeller design for all required operation points.

Based on the relative large axial tolerance of the long shaft of a drum pump, the impeller gap needs also a large tolerance. Last, the inlet and outlet of the semi-axial impeller should be in axial direction, because the complete pump is mounted in a relatively simple pipe as pump housing. Based on the said boundary conditions, the best impeller design in meridional sketch is shown in Additionally the influence of backup blades is investigated.

Other geometric parameters like outlet diameter or blade angels of impeller and diffuser remain constant.

Figure 6. Overview of investigated design parameters

The design point is illustrated in Figure 7 and the specific speed number is n q = 90.

Figure 7. Selected design point

The design process follows the same procedure for all impellers according to Figure 8. It is based on stream line theory with a slip factor, described in standard literature like Pfleiderer [START_REF] Pfleiderer | Die Strömungsmaschinen[END_REF], Neumann [START_REF] Neumann | Interaction between geometry and performance of a centrifugal pump; mechanical engineering publications limited[END_REF] Troskolanski [START_REF] Troskolanski | Kreiselpumpen -Berechnung und Konstruktion[END_REF] or Gülich [START_REF] Gülich | Centrifugal pumps -Detailed design procedures for pumps[END_REF].

Figure 8. Impeller design procedure

Finally, eleven different impellers were designed and manufactured via rapid prototyping. Figure 9 gives the overview of all manufactured impellers and their diversified characteristics. All designed impellers and one new diffuser were tested in a special designed closed test loop as shown in Figure 10. A horizontal acrylic pipe in same dimensions like the drum pump casing is installed in a larger pipe, which is similar to a drum pump application. A long shaft sealed within a 90°-bend and carried by a bearing arrangement is driven by a high speed power unit via a torque sensor. Flow measurement with magnetic inductive flowmeter and pressure transducers on suction and discharge characterize all required performance data from the pump. The measurements of the test stand allow a detailed loss analysis.

RESULTS

Impellers are characterised by the head, power at shaft and the pump efficiency. All measurements are taken at the same speed n = 10.000 rpm. The comparison of the three blade numbers (Figure 12) represents that nearly constant power consumption could be reached with 4 blades. Power consumption increases with 3 blades and decreases with 5 blades at higher flow rates. Highest efficiency could also be reached with 4 blades. Additionally, it could be pointed out, that the impeller with 3 blades is close to axial and with 5 blades is already close to radial characteristic.

From literature the enormous influence of the blade number is known. That means flow control, vortex areas, friction loss and effects by slip. Together these have oppositional influences so that finally a compromise between all factors allows finding the optimum regarding efficiency and pump power.

In this development, the blade number 4 was selected as the best compromise and all further investigations are done with 4 blades. The comparison of the three suction mouth diameters (Figure 13) represents that nearly constant power consumption could be reached with all three impellers. The amount of power is approximately 20 W -50 W less for suction mouth diameter 27 mm than other sizes so there could be reached highest efficiency.

Measurements show that impeller with d S = 28 mm has superficial recirculation and the higher circumferential velocity may result in higher shock losses. The impeller with d S = 25 mm has higher inlet speed, which also tends to higher inlet losses. This means a suction mouth diameter with d S = 27 mm is the best compromise.

The comparison of the three inlet inner diameters (Figure 14) shows that nearly constant power consumption could be reached with all three impellers. The power consumption of inlet inner diameter d 1i = 10 mm is approximately 20 W less resulting in the highest efficiency for this setup.

A displacement of the leading edge into suction mouth or blade channel has direct influence on blade length linked to friction loss, flow deviation and slip.

The measurement shows that the position of leading edge is elected well for inlet diameter d 1i = 10 mm. The comparison of the impellers with 3 and 4 blades and impellers with additional backup-blades (Figure 15) demonstrates that nearly constant power consumption could be reached by the impellers with backup-blades. The power curves have lower bandwidth over flow than without backup blades and decrease with higher flow rates. Highest efficiency could be reached with 4 blades and without backup-blades.

Backup-blades improve flow control. At the same time lower blade pressure develops linked to minor slip that increased head and tends to bold head curves as recognized in Figure 15. The increase of friction loss as a consequence of more blades limits the flow rate noticeable.

The measurements show that backup-blades improve flow control especially for lower blade numbers and reach constant power consumption. However, the additional blades increase power loss that finally reduces efficiency.

No impeller with backup-blades is preferred because there is still one impeller without backup-blades that has constant power consumption with higher efficiency. The comparison of the impellers with different outlet width (Figure 16) displays for both outlet widths nearly constant power consumption. For outlet width 7 mm, a higher head and in conjunction, the power consumption increased. Highest efficiency could be reached with both impellers unlike highest amount is displaced to higher flow rates for outlet width 7 mm.

The proportion between inlet and outlet cross section is influenced with increasing outlet width to that effect that simultaneous meridian speed is decreasing and rotation speed linked to head is increasing. Through resulting enhanced blade channel flow loss is increased too. This correlation is also shown in Figure 15.

Altogether there is no direct correlation seen between outlet with and power curve trend. In that case the impeller with outlet width b 2 = 5 mm is preferred because of lower power consumption reaching the required head.

Finally impeller B4-0-27-10-5 has been elected as the best result of all impellers. It should be pointed out, that the rotational speeds of the standard impeller are significantly higherup to 2.000rpm above the new semi-axial impeller. Thus, the generated noise is also reduced.

The comparison of the curves underlines the tremendous improvement of the new impeller design for the drum pump: -constant power consumption for all operation points, -coverage of head-flow requirement radial/axial and efficiency increase by more than 20 points.

Overall the new impeller reduces the required motor power significantly and there will be no speed change during operation. Thus the cooling effect remains good for all operation points and the lower speed reduces the noise emission.

DISCUSSION

The project demonstrates that it is possible to find an impeller design with nearly constant power consumption for all flow rates.

Regarding literature a semi-axial impeller around n q = 100 could bring high potential for this investigation n q = 90 the intention has been reached. Using the standard design process based on the stream line theory was suitable for the special designed semi-axial impellers.

The variation of a number of design parameters shows that complex interactions of several effects influence the power curve so it is necessary to equilibrate them.

It could be shown that for this impeller within a drum pump application blade number has to be four and symmetrical. Unlike the constant power consumption couldn't be reached. Additional backup-blades are usefully for low blade numbers to generate nearly constant power curve. The disadvantage of backup-blades is the increase of power linked to decreasing efficiency.

The inlet needs an optimization process. This investigation shows that smaller inlets increase head with less efficiency and bigger inlets loose the effect of constant power with less efficiency. The outlet has no influence to reach a constant power curve.

Figure 1 .

 1 Figure 1. Schematic diagram of typical power consumption curves for axial and radial impeller pumps

Figure 2 .

 2 Figure 2. Diagram of theoretical power curves for different specific speed numbers

Figure 4 .

 4 Figure 4. Power curve separated in power shares: recirculation loss, hydraulic power, friction loss and mechanical loss

Figure 5 .

 5 It results in a semi-axial impeller with open axial inflow and diagonal outflow into a bladed diffuser. The impeller has a rotating inflow contour and a constant axial gap.

Figure 5 .

 5 Figure 5. basic concept for the new impeller designTo influence the recirculation power of the impeller to reach nearly constant power consumption a variation of a number of design parameters is necessary. Comparable to Figure6the following design parameters are varied:

Figure 9 .

 9 Figure 9. Impellers of study (left: front view without shroud right: meridian view)

Figure 10 .

 10 Figure 10. Test stand

Figure 11 .

 11 Figure 11. Drum pump test stand

Figure 12 .

 12 Figure 12. Head, power and efficiency over flow for blade numbers 3, 4 and 5

Figure 13 .

 13 Figure 13. Head, power and efficiency over flow for d s = 25 mm, 27 mm and 28 mm

Figure 14 .

 14 Figure 14. Head, power and efficiency over flow for d 1i = 9 mm, 10 mm and 11 mm

Figure 15 . 4 Figure 16 .

 15416 Figure 15. Head, power and efficiency over flow for blades 3 and 4 and backup-blades 3 and 4

Figure 17 .

 17 Figure 17. Head, power and efficiency over flow for radial, axial and new semi-axial impeller Figure 17 shows the results of the measurements in the second test stand in a real drum pump operation and comparison with standard radial and axial impellers.

ACKNOWLEDGEMENTS

The authors like to thank the industrial partner Lutz Pumps for the support of this project. Additional we thank all students and colleagues for their valuable contributions to this research work.