Alfonso Baños

Pérez Félix

Sophie Rubio

Luca Tarbouriech

Zaccarian

F Pérez Rubio

S Tarbouriech

L Zaccarian

Delay-independent stability via reset loops

come

Introduction

An important aspect that must be taken into account in many control applications is the presence of delay in the loop, which can be the source of performance degradation or even instability (see, for example, [START_REF] Sipahi | Stability and stabilization of systems with time delay[END_REF], [START_REF]Time delay systems: method, applications and new trends[END_REF] and references therein).

A control architecture that received much attention in recent years is that of reset control. Reset control systems can be represented by means of different hybrid systems formulations. Many of the previous work about systems with resets has been done by using the impulsive state dependent state formulation of [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF]. Alternatively, the hybrid formulation developed in [START_REF] Goebel | Hybrid dynamical systems[END_REF][START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF] has been also used for describing reset control systems, and formal stability results have been already obtained (see, e.g., [START_REF] Nesic | Stability properties of reset systems[END_REF][START_REF] Nešić | Stability and performance of SISO control systems with First Order Reset Elements[END_REF][START_REF] Zaccarian | Analytical and numerical Lyapunov functions for SISO linear control systems with First Order Reset Elements[END_REF]). This last framework has also been used for systems with time delays in the recent work [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF], that is inspiring for the notation followed in this chapter. This formulation will be first used for stability analysis of reset control system with time delays, and with a new characterization of flow and jump sets, inspired by [START_REF] Fichera | Using Luenberger observers and dwelltime logic for feedback hybrid loops in continuous-time control systems[END_REF], that allows us to state a Lyapunov-Krasovskii theorem for delay-independent stability of the reset control system. Alfonso Baños Departamento de Informtica y Sistemas. Facultad de Informatica. Universidad de Murcia, e-mail: abanos@um.es Félix Pérez Rubio MTorres SAU. (31119) Spain, Software Department, e-mail: Felix.Perez@mtorres.es Sophie Tarbouriech CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France and Univ de Toulouse, LAAS, F-31400 Toulouse, France, e-mail: tarbour@laas.fr Luca Zaccarian CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France, Univ de Toulouse, LAAS, F-31400 Toulouse, France, and Dipartimento di Ingegneria Industriale, University of Trento, Italy e-mail: zaccarian@laas.fr From a historical perspective, the idea of reset compensation dates back to the seminal works of Clegg and Horowitz [START_REF] Clegg | A nonlinear integrator for servomechnisms[END_REF][START_REF] Horowitz | Nonlinear design for cost of feedback reduction in systems with large parameter uncertainty[END_REF], where simple reset compensators such as the Clegg integrator or the First Order Reset Element (FORE) were first proposed with the main motivation of overcoming fundamental limitations of linear time-invariant compensators in control practice. Intuitively, within this quest, since it was observed already in [START_REF] Clegg | A nonlinear integrator for servomechnisms[END_REF] (see also [START_REF] Baños | Reset Control Systems[END_REF]) that reset compensation introduces phase lead without significantly increasing the loop gain, it seems to be appropriate to propose reset compensation for systems with time-delays due to the evident time lag introduced by the delay effect. In [START_REF] Baños | Delay-independent stability of reset systems[END_REF], a delay-independent stability analysis of reset control system is first performed, that has been extended to the more general delay-dependent case in [START_REF] Barreiro | Delay-dependent stability of reset systems[END_REF][START_REF] Baños | Reset Control Systems[END_REF] and in [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF].

In this chapter, we are interested in studying the stability of closed loops independently of the delay. In particular, our work is focused on the design of hybrid reset rules based on Lyapunov conditions and applied to time-delay continuous-time plants in order to eliminate possible instability arising from the linear interconnection. We propose a kind of hybrid controller that can guarantee delay-independent stability of the closed loop. The class of systems that we address combines two ingredients: 1) the continuous-time dynamics of a linear time-delay plant and a linear controller, enforced when the overall state belongs to a certain flow set F and 2) a discrete dynamics corresponding to an impulsive action performed on the controller state when the overall state belongs to a certain jump set J [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]. It is important to emphasize that few works are dedicated to the study of hybrid time-delay systems. Notable exceptions comprise the reset systems work in [START_REF] Baños | Delay-independent stability of reset systems[END_REF], [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF] and the framework recently proposed in [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF].

The scheme proposed in this chapter arises from adapting the hybrid augmentation paradigm recently proposed in [START_REF] Prieur | Lyapunov-based hybrid loops for stability and performance of continuous-time control systems[END_REF][START_REF] Fichera | Using Luenberger observers and dwelltime logic for feedback hybrid loops in continuous-time control systems[END_REF]. Moreover, to prove our main result, we also formulate a Lyapunov-Krasovskii theorem that complements the results issued from [START_REF] Baños | Delay-independent stability of reset systems[END_REF] and [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF], by using a different definition of flow and jumps sets and an additional dwell-time logic.

In the sequel we first introduce the problem under consideration in Section 2. Then we describe the proposed closed loop with resets in Section 3. Subsequently we prove suitable stability properties of the control scheme in Section 4 and finally we discuss a simulation example in Section 5.

Problem data and standing assumption

Consider the following strictly proper linear time-delay plant:

P : ẋp (t) = A p x p (t) + A pd x p (t -θ ) + B p u c (t) y p (t) = C p x p (t), (1)
where x p ∈ R n p is the state of the plant, θ ∈ R ≥0 is a known state delay, y p ∈ R n y is the output available for measurement and u c is the control input to be used in the controller design. It is costumary to denote the infinite dimensional state of plant (3) as

x pt = {x p (s), s ∈ [t -θ ,t]}, (2)
and to use the shortcut notation x pd (t) = x p (t -θ ) so that equation (3) can be written in compact from as

P : ẋp = A p x p + A pd x pd + B p u p y p = C p x p . (3)
For plant (3) we assume that a linear time invariant controller has been designed to ensure suitable closed-loop properties under certain operating conditions:

C : ẋc = A c x p + B c y p u p = C c x c ( 4
)
where x c ∈ R n c is the state of the controller. Controller (4) has been designed for plant (3) disregarding the effect of delay, namely in such a way to stabilize the delayfree dynamics corresponding to the transition matrix A p +A pd , which corresponds to plant (3) in the special case θ = 0. Then the goal of this paper is to introduce suitable reset rules on the controller states that ensure recovery of closed-loop asymptotic stability for any known value of the delay θ . Since we do not need the requirement that controller (4) stabilizes the plant when θ = 0, we don't make this as an explicit assumption.

In this work we will use Lyapunov-Krasovskii techniques to assess asymptotic stability of the closed loop for any value of the time delay θ , that is, stability independent of the delay. Due to this fact, we will require the following assumption on the plant data.

Assumption 1 Given the matrices in [START_REF] Baños | Delay-independent stability via reset loops[END_REF] there exist two positive definite matrices P p and Q, a gain K p and a scalar ε p > 0 such that

He P p (A p + B p C c K p ) + Q/2 P p A pd 0 -Q/2 ≤ -2ε p P p 0 0 Q (5)
Assumption 1 ensures that it is possible to prestabilize plant (3) by way of the state feedback gain u p = K p x p and obtain a delay-independent stable closed loop. The following lemma clarifies that the search for parameters P p , Q and K p in ( 5) is equivalent to a convex (LMI eigenvalue) problem.

Lemma 1. Assumption 1 holds if and only if the following LMI in the variables

Q p = Q T p > 0, S = S T > 0 and X is feasible: He A p Q p + B p C c X + S/2 A pd Q p 0 -S/2 < 0, (6)
Moreover, whenever [START_REF] Fichera | Using Luenberger observers and dwelltime logic for feedback hybrid loops in continuous-time control systems[END_REF] holds, a solution to Assumption 1 is given by P p = Q -1 p , Q = P p SP p , K p = XP p and a small enough ε p .

Proof. Consider equation ( 6) and perform the congruence transformation pre-and post-multiplying by the block-diagonal symmetric matrix diag(Q -1 p , S -1 ). Then the following equivalent relation to ( 6) is obtained, with the definitions in the lemma:

He P p (A p + B p C c K p ) + Q/2 P p A pd 0 -Q/2 < 0. ( 7
)
Assume now that Assumption 1 holds, then obviously equation ( 7) holds too, which is equivalent to [START_REF] Fichera | Using Luenberger observers and dwelltime logic for feedback hybrid loops in continuous-time control systems[END_REF]. Viceversa, if (6) (therefore ( 7)) holds, then due to the strict inequality in [START_REF] Goebel | Hybrid dynamical systems[END_REF] there exists a small enough ε p > 0 such that (5) holds with the selections in the statement of the lemma.

Remark 1. Once the feasibility condition ( 6) is verified, it might be of interest to seek for the solution to (5) corresponding to maximizing ε p while imposing that the gain K p satisfies a prescribed bound |K p | ≤ κ M , for some fixed scalar κ M > 0. This solution can be computed by solving the following optimization problem:

ε * p = max Q p ,X,S,ε p ε p subject to: Q p ≥ I, κ M I X X T κ M I ≥ 0 He A p Q p + B p C c X + S/2 A pd Q p 0 -S/2 ≤ -2ε p Q p 0 0 S (8)
which is a generalized eigenvalue problem (namely a quasi convex optimization problem) for which efficient numerical solution algorithms are available. The corresponding solution to (5) can then be computed as P p = Q -1 p , Q = P p SP p and K p = XP p , just as in Lemma 1.

Hybrid closed-loop system

In this section we design a hybrid closed-loop system whose flow dynamics corresponds to the interconnection between (3) and ( 4) and whose jump dynamics and jump and flow sets are constructed, based on a solution to (5) in Assumption 1, in such a way to guarantee uniform global asymptotic stability of the origin of the plant-controller state space. Note that this property is non-trivial because no assumption is made on the stability properties of the continuous-time interconnection (3), [START_REF] Barreiro | Delay-dependent stability of reset systems[END_REF] Adopting the notation in [START_REF] Goebel | Hybrid dynamical systems[END_REF][START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF], we propose the following dwell-time hybrid augmentation of the closed loop (3), [START_REF] Barreiro | Delay-dependent stability of reset systems[END_REF], where for convenience of notation we denote the aggregated (and transformed) state ξ = (x p , x pd , δ ) := (x p , x pd , x c -K p x p ):

     ẋp = A p x p + A pd x pd + B p C c x c ẋc = A c x c + B c C p x p τ = 1 -dz τ ρ (ξ , τ) ∈ C × [0, 2ρ]    x + p = x p x + c = K p x p τ + = 0 (ξ , τ) ∈ D × [ρ, 2ρ], (9a)
where dz(•) denotes the scalar unit deadzone function, the sets C and D are defined, based on an arbitrary positive scalar ε < ε p , as follows:

C :=    ξ : ξ T He   P p A R + Q/2 P p A pd P p B p C c 0 -Q/2 0 0 0 0   ξ ≤ -ε ξ T   P p 0 0 0 Q 0 0 0 I   ξ    (9b) D :=    ξ : ξ T He   P p A R + Q/2 P p A pd P p B p C c 0 -Q/2 0 0 0 0   ξ ≥ -ε ξ T   P p 0 0 0 Q 0 0 0 I   ξ    . (9c)
In the sets C and D, A R is defined as A R := A p + B p C c K p and matrices P p and Q are defined in Assumption 1.

Following [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF] and inspired by the definitions in [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF], we introduce the following definitions to suitably characterize solutions to hybrid system [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF]. In particular, the following definitions are slightly different from those in [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF] because we are exploiting here the property that the memory of the time-delay system is only in the directions of the plant state, which remains unchanged across jumps.

Definition 1. A subset E ⊂ R ≥0 × Z ≥0 is called a compact hybrid time domain if E = J-1 j=0 ([t j ,t j+1 ], j)
for some finite sequences of times 0 = t 0 ≤ t 1 ≤ • • • ≤ t J , called "jump times". The set E is called a hybrid time domain if for all (T, J) ∈ E, the set E ∩ ([0, T ], {0, 1, . . . , J}) is a compact hybrid time domain.

Given a positive real θ > 0, a subset E 0 ⊂ R ≥-θ × Z ≤0 is called a hybrid time domain with ordinary memory θ if

E 0 = ([-θ , 0), 0) ∪ E,
where E is a hybrid time domain.

A hybrid arc with ordinary plant memory θ is a triple consisting of a domain domφ that is a hybrid time domain with ordinary memory θ , a continuous function φ p0 (s), s ∈ [-θ , 0] representing the (infinite dimensional) initial condition of the system in the plant state direction and a function φ : dom ≥0 φ → R n p ×n c , where dom ≥0 φ := domφ ∩ (R ≥0 × Z ≥0 ), such that φ (•, j) is locally absolutely continuous on I j = {t : (t, j) ∈ dom ≥0 φ }.

Similar to [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF]Def. 4], but for the special case where the memory of the timedelay system is only in the ordinary time direction, given any hybrid arc φ = (φ p , φ c ) with ordinary plant memory θ , for each (t, j) ∈ dom ≥0 φ , we define the operator µ [t, j] φ p (s) that maps the hybrid arc φ into an ordinary memory arc of length θ (this is a function of ordinary time only). In particular, domµ [t, j] φ p = [-θ , 0] and for each s ∈ [-θ , 0] we have µ [t, j] φ p (s) = φ p (t + s, i) for some i ∈ Z ≥0 such that (ts, i) ∈ domφ . Note that such an i exists because the hybrid arc φ has ordinary plant memory θ by assumption. Note also that the definition above has no ambiguity because of the special structure in [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF] where the p component of the solution remains constant across jumps. Indeed, if there exist multiple values i 1 , i 2 , ∈ Z ≥0 such that (ts, i 1 ), (ts, i 2 ) ∈ domφ , then we have µ [t, j] φ p (s) = φ p (t + s, i 1 ) = φ p (t + s, i 2 ). Indeed, projecting the memory of the time-delay system only on the ordinary time domain axis (by way of the operator µ [t, j] ) greatly simplifies the forthcoming derivations.

Based on the above characterization, we can formulate a class of hybrid timedelay systems that generalizes the peculiar structure of ( 9) and that can be written in compact form as follows:

  ẋp ẋc τ   =    f p (x p , x c , µx p ) f c (x p , x c , µx p ) 1 -dz τ ρ    , x p x c µx p τ ∈ C × [0, 2ρ],   x + p x + c τ +   =   x p g c (x p , x c , µx p ) 0   , x p x c µx p τ ∈ D × [ρ, 2ρ], (x p (0, 0), x c (0, 0)) ∈ R n p ×n c µ [0,0] x p ∈ C 0 ([-θ , 0]), (10)
where C 0 (T ) denotes the set of continuous functions whose domain is T ⊂ R, f p , f c and g c are suitable linear functionals that, for system (9), correspond to:

f p (x p , x c , µx p ) = A p x p + A pd µx p (-θ ) + B p C c x c , f c (x p , x c , µx p ) = A c x c + B c C p x p g c (x p , x c , µx p ) = K p x p .
Moreover, the flow and jump sets C and D are suitable infinite dimensional flow and jump sets. Based on Definition 1, a solution to hybrid time-delay system (10) is a hybrid arc with ordinary plant memory θ satisfying the flow and jump constraints imposed by the hybrid dynamics. A precise formulation of this can be obtained by following the same paradigm as that used in [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF]Def. 6].

Remark 2. The extension of the formalism in [START_REF] Goebel | Hybrid dynamical systems[END_REF][START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF] to the time-delay framework is currently underdeveloped (a notable exception being the recent paper [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF]). Therefore, not much can be stated about existence of solutions or even nominal or robust well posedness of solutions to these hybrid systems in the sense of [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]Ch. 6]. Results on well posedness of a particular class of hybrid systems is given in [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF], however system [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF] goes beyond this class because in [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF] it is assumed that the flow and jump sets are subsets of the Euclidean spaces where x p and x c take values. Here we have a new direction in the jump and flow sets depending on the (infinite dimensional) memory of the plant state x p and it is not evident how to inherit the results of [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF]. However, at least from the existence viewpoint, the architecture (10) can still inherit useful properties from the classical results in [START_REF] Hale | Introduction to functional differential equations[END_REF] and from the results in [START_REF] Goebel | Hybrid Dynamical Systems: modeling, stability, and robustness[END_REF]Ch. 6], as long as the initial condition µ [0,0] x p of the plant is continuous. Remark 3. Note that differently from [START_REF] Fichera | Using Luenberger observers and dwelltime logic for feedback hybrid loops in continuous-time control systems[END_REF], the dwell-time logic is implemented in ( 9) by forcing solutions not to jump unless τ ≥ ρ, while also not allowing them to flow if their ξ component does not belong to the set C . Because of this fact, dwell time is artificially enforced on solutions by possibly terminating defective solutions that would jump too often. The natural question that arises is then whether system (9) admits complete solutions for all initial conditions starting either in the jump or in the flow set. This question is not addressed here, where we simply limit ourselves to observing that the example treated in Sect. 5 exhibits complete solutions. We regard tackling this important aspect as future work.

4 Stability properties of the reset control scheme

A Lyapunov-Krasovskii theorem

We state in this section a peculiar version of a Lyapunov-Krasovskii theorem for system [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF]. Alternative instances of this type of result have appeared in the recent literature. For example see [START_REF] Baños | Delay-independent stability of reset systems[END_REF]Prop. 3.1] or [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF]Prop. 1]. We state here a different formulation of the result, due to the special definitions and hybrid framework used in the previous section.

Since we are not interested in the evolution of the timer τ within the compact set [0, 2ρ] where it is confined, we will characterize stability properties of the following compact attractor for dynamics [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF]:

A := {0} × [0, 2ρ] ⊂ R n p +n c × R. (11)
In particular, following standard derivations in the time-delay continuous-time systems framework, given any solution φ = (φ x , φ τ ) = (φ p , φ c , φ τ ) to [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF], we introduce the following notion of distance from the set A in [START_REF] Hale | Introduction to functional differential equations[END_REF] for each (t, j) ∈ dom ≥0 φ :

φ (t, j) µ = max |φ x (t, j)|, max s∈[-θ ,0] |µ [t, j] φ p (s)| , (12)
where | • | denotes the Euclidean norm. Since we are dealing with a special class of hybrid time-delay systems, we clarify the meaning of stability in the following definition, which is inspired by [START_REF] Liu | Generalized solutions to hybrid systems with delays[END_REF] and [8, §3

.

Definition 2. The compact set A in ( 11) is 1. Globally stable (GS) for [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF] if there exists a class K ∞ function α such that any solution φ = (φ x , φ τ ) = (φ p , φ c , φ τ ) to (10) satisfies |φ x (t, j)| ≤ α( φ (0, 0) µ ) for all (t, j) ∈ dom ≥0 φ . 2. Uniformly globally attractive (UGA) for [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF] if for each pair r, ε, there exists T (r, ε) such that any solution φ satisfies:

φ (0, 0) µ ≤ r ⇒ |φ x (t, j)| ≤ ε, ∀(t, j) ∈ dom ≥0 φ such that t + j ≥ T (r, ε). (13
) 3. Uniformly globally asymptotically stable for [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF] if it is GS and UGA.

Based on Definition 2 we can state a Lyapunov-Krasovskii result that only requires the following mild uniform boundedness assumption on the functions appearing in the flow map of [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF]. This assumption is trivially satisfied by the linear flow dynamics in (9).

Assumption 2 There exists a class K ∞ function α M such that for each r ≥ 0 (where we use x = (x p , x c )),

sup (x,µx p )∈C s.t. x µ ≤r f p (x, µx p ) f c (x, µx p ) ≤ α M (r) Proposition 1. Under Assumption 2, if there exist a function V , two class K ∞ func- tions α 1 , α 2 and a positive definite function σ satisfying α 1 (|x|) ≤ V ((x, τ), µx p ) ≤ α 2 ( (x, τ) µ ), ∀(x, µx p , τ) (14)
V ((x, τ), µx p ) ≤ -ρ(|x|), ∀(x, µx p , τ) ∈ C × [0, 2ρ], (15)

V ((x + , τ + ), µx p ) -V ((x, τ), µx p ) ≤ 0, ∀(x, µx p , τ) ∈ D × [ρ, 2ρ], ( 16
)
then the compact attractor A in [START_REF] Hale | Introduction to functional differential equations[END_REF] is uniformly globally asymptotically stable for [START_REF] Haddad | Impulsive and hybrid dynamical systems: stability, dissipativity, and control[END_REF].

Proof. The proof is omitted due to space constraints but can be found in [START_REF] Baños | Delay-independent stability via reset loops[END_REF].

Main stability result

We state next our main stability result for the hybrid dynamics (9). To properly state the stability result, Theorem 1. Consider a plant (3) satisfying Assumption 1 and a controller [START_REF] Barreiro | Delay-dependent stability of reset systems[END_REF]. Then for the dwell-time hybrid time-delay dynamics [START_REF] Guo | Quadratic stability of reset control systems with delays[END_REF] there exist a functional V and class K ∞ functions α 1 , α 2 and σ satisfying ( 14)- [START_REF] Prieur | Lyapunov-based hybrid loops for stability and performance of continuous-time control systems[END_REF]. Namely, the set A in ( 11) is globally asymptotically stable.

Proof. Using P p and Q of Assumption 1, consider the following Lyapunov-Krasovskii functional for the plant state directions:

V p (x p , µx p ) = x T p P p x p + 0 -θ µx T p (s)Qµx p (s)ds. (17)
The derivative of V p along the flow dynamics of ( 9) is (for notational compactness, we use x pd := µx p (-θ ) in the rest of the proof):

Vp = 2x T p P p A p x p + B p C c (K p x p + x c -K p x p ) + A pd x pd + x T p Qx p -x T pd Qx pd = 2x T p P p   (Ap + B p C c K p A R )x p + A pd x pd + B p C c (x c -K p x p δ )    + x T p Qx p -x T pd Qx pd =   x p x pd δ   T He   P p A R + Q/2 P p A pd P p B p C c 0 -Q/2 0 0 0 0     x p x pd δ   .
(18) Then, from the definition (9b) of the flow set C we have that

Vp ≤ -ε |x p | 2 P p + |x pd | 2 Q + |δ | 2 , ∀(x p , x pd , δ ) ∈ C (19)
where |y| W = y T Wy. Now consider the following Lyapunov-Krasovskii functional for the overall system:

V = V p (x p , µx p ) + λ δ 2 , ( 20
)
where λ is a positive scalar selected later. We show next that this function satisfies ( 14)-( 16), so that the result follows from Proposition 1.

Proof of [START_REF] Nešić | Stability and performance of SISO control systems with First Order Reset Elements[END_REF]. The lower bound on the left comes from

x T p P p x p +λ δ 2 = x p x c T P p + λ K T p K p -λ K p -λ K T p λ I Σ x p x c ≥ σ m (Σ ) x p x c 2 =: α 1 x p x c
, where σ m (Σ ) > 0 because Σ is positive definite.

For the upper bound we get:

V (x, µx p ) ≤ x p x c T Σ x p x c + 0 -θ σ M (Q)|µx p (s)| 2 ds ≤ σ M (Σ ) x p x c 2 + θ σ M (Q) max s∈[-θ ,0] |µx p (s)| 2 ≤ 2 max{σ M (Σ ), θ σ M (Q)} (x, τ) 2 µ =: α 2 ( (x, τ) µ ).
where σ M (•) and σ m (•) denote, respectively, the maximum and minimum singular values of their arguments. Proof of [START_REF] Nesic | Stability properties of reset systems[END_REF]. First, we may easily compute:

V ≤ Vp + λ δ ((A c -K p B p C c A 1 )x c + (B c C p -K p A p A 2 )x p + (-K p A pd A 3 )x pd ). (21)
Since x c = δ + K p x p , then using [START_REF] Zaccarian | Analytical and numerical Lyapunov functions for SISO linear control systems with First Order Reset Elements[END_REF], equation ( 21) can be rewritten as

V ≤ -ε|x p | 2 P p -ε|x pd | 2 Q -ε|δ | 2 + λ δ (A 1 δ + (A 1 K p + A 2 )x p + A 3 x pd ) ≤ -εc|x p | 2 -εc|x pd | 2 -ε|δ | 2 + λ c(|δ | 2 + |δ | |x p | + |δ | |x pd |), where c = max{σ M (A 1 ), σ M (A 1 K p + A 2 ), σ M (A 3 )} and c = min{σ m (P p ), σ m (Q)}.
Finally, completing squares and choosing λ = ε min c c , 1 4c , we get

V ≤ -εc - λ c 2 |x p | 2 --εc + λ c 2 |x pd | 2 -(ε -2λ c)|δ | 2 ≤ - ε 2 I 0 -K p I x p x c 2 =: -σ (|(x p , x c )| 2 ),
which implies the flow condition [START_REF] Nesic | Stability properties of reset systems[END_REF].

Proof of [START_REF] Prieur | Lyapunov-based hybrid loops for stability and performance of continuous-time control systems[END_REF]. Simply observe that x p remains constant across jumps, therefore

V (x + , µx p ) -V (x, µx p ) = λ ((δ + ) 2 -δ 2 ) = -δ 2 ≤ 0,
where we used the fact that δ is reset to zero at each jump.

Simulation example

Consider the following entries for the matrices in (3):

A p = -2 0 0 -0.9 , A pd = -1 0 -1 -1 , B p = 1 1 , C p = 1 1 (22)
and the selection for controller (4):

A c = -1 0 1 0 , B c = 1 0 , C c = 0 -1 , (23)
which involves an integral action possibly to deal with constant references or disturbances. When interconnecting plant and controller, we obtain a continuous-time dynamics as in the upper equation of (9a) with

A p = -2 0 0 -0.9 , A pd = -1 0 -1 -1 , B p C c = 0 -1 0 -1 , A c = -1 0 1 0 , B c C p = 1 1 0 0 . (24)
Such a continuous-time dynamics is exponentially stable if θ = 0 (case with no delay) but for larger delays, beyond the critical value θ M = 1.6, the (linear) continuous-time closed loop becomes unstable.

Plant (3), ( 22) satisfies Assumption 1, therefore we may follow our hybrid construction to obtain GAS of the origin for any value of the delay, while preserving the continuous-time dynamics induced by ( 4), (24). To this aim, we follow the design paradigm in Remark 1 and compute a trade-off curve between the bound κ M > 0 and the decrease rate ε * p . Fig. 1 shows the optimal values of ε * p as a function of the bound κ M on |K p |. Note that if κ M is too small, then ε * p is negative and the design cannot be performed. Clearly, the curve is nondecreasing as increasing κ M one enlarges the feasible set. Table 1 The three cases addressed in the simulation example.

Table 1 shows the optimal values corresponding to the three circles reported in Fig. 1. The first value is just after the stability limit and the two other ones correspond to different trade-offs between ε * p and κ M . For these three cases we run a time simulation selecting θ = 2. The simulation results for cases 1, 2, and 3, respectively, are shown in Figs. 2 and 3 using solid, dashed, and dotted curves, respectively. In the two figures, we also show the linear response (no resets), which is diverging (dash-dotted curves) because 2 > θ M ≈ 1.6. For the simulations, we selected ρ = 0.01 s that turns out to be well below the time elapsed between any pair of consecutive resets. Therefore, with reference to Remark 3, the dwell-time logic does not prematurely terminate our solutions.

The simulation results confirm the faster convergence rate (larger ε * p ) envisioned for larger values of κ M . Quite interestingly, this faster convergence is obtained by resetting earlier, rather than using a larger control input. Indeed, for larger values of κ M , we observe a reduced amplitude of the control input u c (see the bottom plot in Fig. 2).

Fig. 1

 1 Fig.1The optimal value ε * p in (8) as a function of κ M .

Fig. 2

 2 Fig. 2 States and input of the plant for the simulation test.

Fig. 3

 3 Fig.3States of the controller for the simulation test.

Acknowledgements This work was supported by ANR project LimICoS contract number 12 BS03 005 01, by HYCON2 Network of Excellence "Highly-Complex and Networked Control Systems", grant agreement 257462 and by MICINN under the project DPI 2007-66455-C02-01.


Laure Berti-Équille

Tamraparni Dasu

New Directions for Data Quality Mining

The exact notion of data quality is multidimensional and different from one application domain to another Concomitant data quality problems increase the detection complexity

Outline

What is Data Quality Mining?

"DQM can be defined as the deliberate application of data mining techniques for the purpose of data quality measurement and improvement. The goal of DQM is to detect, quantify, explain, and correct data quality deficiencies in very large databases." [Hipp, Güntzer, Grimmer, 2001] 20

Data Quality Mining (DQM) intends to be an iterative framework for creating, adapting, and applying data mining techniques for the discovery, explanation and quantitative cleaning of data glitches and their complex patterns in large and patchy datasets.

In addition,

Motivation

Data quality problems are: Omnipresent in every application domain Interwoven and complex in any DB, DW or IS Critical to every data management, KDD and decision making project because of their massive financial impact Calculate the mean μ and the variance-covariance matrix Σ 2.

Let C be a column vector having length d, the square of the Mahalanobis distance to the mean μ is given by: 3.

Find points O in C whose value is greater than 4.

Return O.

Finding Multivariate Outliers

( ) ( ) ( ) ( ) μ σ σ σ σ σ σ σ σ σ μ μ μ - ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ′ - = - Σ ′ - = - - x x x x MD dd d d d d 1 2 1 2 22 21 1 21 11 1 2 L M O M M L L ( ) ( ) 975 . 2 d inv χ 31
Mean and standard deviation are extremely sensitive to outliers (Breakdown point=0%) Minimum Volume Ellipsoid (MVE) [START_REF] Rousseeuw | Unmasking Multivariate Outliers and Leverage Points[END_REF] Let the column vector C with the length d (d > 2) be the estimate of location and let the d-by-d matrix M be the corresponding measure of scatter. The distance of the point x i = (x i1 ,…,x id ) from C is given by: If then x i is declared an outlier. C is center of the minimum volume ellipsoid covering (at least) h points of the data set. [Rousseeuw & Driessen, 1999] Given n data points, the MCD is the mean and covariance matrix based on the sample of size h (h < n) that minimizes the determinant of the covariance matrix.

Minimum Covariance Determinant (MCD)

Robust estimators

( ) ( ) C x C x D i i i - ′ - = -1 M 32
Masking the structure of the group of MV outliers (clustered vs scattered)

Approaches

Local Outlier Factor (LOF) [Breunig et al., 2000] Connectivity Outlier Factor (COF) [START_REF] Tang | Enhancing Effectiveness of Outlier Detections for Low Density Patterns[END_REF] Multi-Granularity Deviation Factor [Papadimitriou et al., 2003] EDA -Density-based outliers 34 O1 O2 NN: O2 is outlier but O1 is not LOF: O1 is outlier but O2 is not

In high dimensional spaces, LOF values will tend to cluster because density is defined in terms of distance.

Clustering for MV Outlier Detection

Abbreviation enforcing Data consolidation based on dictionaries and constraints

Machine learning and HMM for field and record segmentation Constraint-based method [Fan et al., 2008] Goals 37 Approaches [START_REF] Christen | Probabilistic name and address cleaning and standardization[END_REF] Performance and scalability issues of most ETL tools Record Linkage (RL) [Elmagarmid et al., 2007] Probabilistic [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF] Type Authors D-Dupe [Kang et al., 2008] http://www.cs.umd.edu/projects/linqs/ddupe Duplicate search and visualization of cluster-wise relational context for entity resolution Febrl [Christen, 2008]: https://sourceforge.net/projects/febrl/ Rule-based and HMM-based standardization and classification-based record linkage techniques SEMANDAQ [Fan et al., 2008]: CFD-based cleaning and exploration HumMer [START_REF] Kriegel | Outlier Detection Techniques[END_REF]: Data fusion with various conflict resolution strategies XClean [START_REF] Weis | XClean in Action (Demo)[END_REF]

Academic and Open

Source ETL Tools X X (X) (X) (X) (X)

Inconsistent Data

Probabilistic Approximate Constraints [Korn et al., 2003] Given a legal ordered domain on an attribute, A domain PAC specifies that all attribute values x fall within ε of D with at least probability δ, as A functional dependency PAC X → Y specifies that, if

Pseudo-constraints [Ceri et al., 2007] Pair <P1,P2> where P1 and P2 are predicates on the same domain D such that if P1 holds, then usually P2 also and therefore there are few rule violations. More formally, based on the probability contingency table,

Pattern Tableaux for Conditional Functional Dependencies

A CFD is defined to be a pair [Bohannon et al. 2007, Bravo et al. 2007, Golab et al. 2008[START_REF] Fan | Relative Information Completeness[END_REF] Embedded FD Disguised Missing Data [START_REF] Hua | Cleaning Disguised Missing Data A Heuristic Approach[END_REF] 57 Assumption: On an attribute, there often exist only a small number of inliers whose values are frequently used as disguised missing data, e.g., popular DoB: Jan 1

[ ] ( ) δ ≥ ± ∈ ε Pr D x ( ) Y B B T B T X A A T A T j i j i ∈ ∀ ≥ ≤ - ∈ ∀ Δ ≤ - l l l l l l l l . . Pr then . . δ ε

Embedded Unbiased Sample Heuristic

Goal: Find the largest set M v embedding S v and maximizing a correlation-based sample quality score.

( ) Compute the principal components of the dataset 2.

v A v A v v A v A v v A v v A T T S T T A T S T S T A v = = = = = = - = ⊆ ⊆ ~ then , ~
For each test point, compute its projection on these components 3.

If y i denotes the i th component, then the following has a chi-square distribution 3.

For a given significance level α, an observation is an outlier if Outlier Mining -Robust PCA [START_REF] Shyu | A novel anomaly detection scheme based on principal component classifier[END_REF] Outlier Identification in High Dimensions [START_REF] Filzmoser | Outlier detection in high dimensions[END_REF] Works in very high-D, where dimensions > samples, e.g., gene data Differential weights to detect location and scatter outliers; weights combined in final step Based on robust statistics Probability distributions [START_REF] Eskin | Anomaly detection over noisy data using learned probability distributions[END_REF] Assumption: High probability to have the number of normal elements in a dataset D significantly larger than the number of outliers Approach:

( ) α χ λ 2 1 2 q q i i i y ∑ = ≥ p q y y y y q q q i i i ≤ + + + = ∑ = , 2 2 2 2 1 2 1 1 2 λ λ λ λ L 61
From the distribution for the dataset D given by: D= ( 1

comparisonFrom

  Rejection area: Data space excluding the area defined between 2% and 98% quantiles for X and Y Rejection area based on: Mahalanobis_dist(cov(X,Y)) > χ 2 (.98,2) • Treatment of missing values, inconsistencies, and outliers

Finding

  (A) = m(B)] = ρ(Α,Β)

  A point O in a dataset is an DB(p,d)-outlier if at least fraction p of the points in the data set lies greater than distance d from the point O.[START_REF] Knorr | Algorithms for Mining Distance-Based Outliers in Large Datasets[END_REF]] Outliers are the top n points whose distance to the k-th nearest neighbor is greatest.[[START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF] Methods failsWhen normal points do not have sufficient number of neighbours In high dimensional spaces due to data sparseness When datasets have modes with varying of particular regions and declare data points in low density regions as potential anomalies

  Variant of NN based on rules for identifying and merging duplicates (Intelliclean) Transformation Fuctions (Active Atlas)

  Thousands of network elements on an IP network Transmit data streams as they communicate to verify availability and transmit data Monitor the data streams to measure performance, and to optimize the network Finding the optimal dataset 0= Raw data 1= Median-based imputation from 4 2= De-duplicated data 3= 1+2 4= Super clean (Full deletion) 5= Strategy driven by the discovery of patterns of glitches 86 MV strategy shown with Univariate projection

Exploratory Data Analysis (EDA) EDA

	Use of simple statistical techniques for exploring and
	understanding the data (John Tukey)
	Usually for variable and model selection and for testing
	distributional assumptions

EDA for Data Quality

	EDA -Outlier Detection
	Control chart/error bounds methods Typical value (green) -
	e.g., expected value; confidence interval or error arithmetic mean, median
	bounds; 3-Sigma, Hampel bounds, IQR Error bounds (red) -
	Model-based outlier detection methods standard deviation, IQR
	e.g., regression model: outlyingness measured Underlying assumptions of Detect data glitches through residuals that capture deviation from the normality and symmetry Outliers and extremes Missing values model Simple, but potential for
	High frequency values and duplicates Multivariate statistics for outlier detection misleading conclusions Data transformation for model fitting Treatment of glitches Selecting variables and records Replacing using statistical models Non trivial to extend to e.g., density-based and geometric or distance-based outlier detection higher dimensional space

29 R chart EDA -Model-based outlier detection

	INPUT: An d X d dataset
	OUTPUT: Candidate Outliers
	Model captures relationships 1.
	between variables
	Confidence bounds/bands
	capture variability
	Points that lie outside bounds
	The choice and correctness
	of the model are critical
	Expertise required for
	parameterization

Challenges of DQM Detection of concomitant DQ problems

	46 47
	Commercial Data Quality Tools Quantitative Data Cleaning Limits of Current Methods In Particular
	DQ Tools include: • Profiling • Improvement: Standardization Cleansing Matching Enrichment • Monitoring Non Realistic Assumptions EDA -Statistics Methods Inclusion (applicable for less than 15%) Anomalies are treated as a specific category Deletion List-wise deletion omits the complete record (for less than 2%) Pair-wise deletion excludes only the anomaly value from a calculation Substitution (applicable for less than 15%) Single imputation based on mean, mode or median replacement Linear regression imputation out of the scope of the analysis Only applicable when the dataset has less than 15% of glitches Multiple imputation (MI) F M MF Data quality problems may not be rare events Methods tied to known distributions → rare class mining won't give the "complete picture" Parametric assumptions often do not hold for real datasets Joint detection of fuzzy duplicates, disguised missing Data quality problems don't occur at random Bad points can completely skew the mean and standard deviation: values, multivariate outliers, and deviants → MCAR/MAR assumptions are not applicable Data quality problems are not uniformly distributed → model-based assumptions is hazardous Different types of data quality problems may co-occur and be → potential multicollinearity problem → explanatory variables/processes may be external and X Quantitative Cleaning techniques Their (co-)occurrence should be explainable clustering and NN Locality and normality assumptions Y Poor performance of complex parameterization and settings → mutual masking-effect of concomitant DQ problems X Magic numbers, (partially) correlated Robustification of the estimators is required Detection of complex patterns of multivariate glitches Statistical methods suffer the uni-modality and locality assumptions: they consider the data set globally EDA -Clustering The arithmetic mean Interactivity, rerunnability and recoverability of DQM Y of the data set is an outlier processes
	→ Biases of imputation and regression methods Full Information Maximum Likelihood (FIML) They should be corrected with "predictable side-effects" Non negligible biases

: Declarative XML cleaning Source: Quadrant of the Magic Quadrant for Data Quality Tools, 2008.

Gartner RAS Core Research Note G00157464

DQM in high dimensional data sets Benchmarking Outline

	Part I. Introduction to Data Quality Research
	Part II. Data Quality Mining
	Part III. Case Study

Data Quality Mining: The Big Picture

	Data Quality Management
	Data Source Selection	Data Quality Mining	Generalization
	Data Quality
	Requirements				Decision Strategies
					Optimization
	Detection & Profiling Source DB	Area Staging Data	and Validation Knowledge Evaluation Knowledge Fusion bootstrap validation Cross-	j-measure
	Handling			Chi-2 Test
	DQ Problems			Mining Result	Poisson Test
					Visualization
	Extract Transform
	Load Data		Mining Methods &	Production Rules Graphics
				Thresholds Selection	Confusion Matrix
		Recommendations and Corrective	Data Preparation	Association Rules Linear Classification
		Actions		Formating Coding	Clustering Decision Trees Instance-based
					Learning
			Quality
	Upstream the KDD Process:	Metadata Repositroy	DIS/DW system	Downstream the KDD Process: Decisional Mining
	Warehousing		Objectives:
				Data Quality Measurement and Improvement

  -λ) M + λ A with M: Majority distribution and λ: Anomaly distribution Compute likelihood of D at time t: L t (D) Measure how likely each point p t is outlier at time t such as: M t =M t-1 \ {p t } and A t =A t-1 ∪ {p t } Observations: large entropy → partition into regular subsets skewness of class distribution → small entropy → high redundancies Approach: Find a k-sized subset whose removal leads to the maximal decreasing of entropy

	Probability Based Methods
	Comparison of
	telecommunications
	data sets
	Anomalous months
	Missing data
	Kdq tree partition
	Darker	greater density
	difference Entropy-based methods Automatic detection is
	speedy, provides an
	opportunity to recover and
	replace data before it is
	archived

[Lee et al., 2001][He 2005]

Attributes, every 5 minutes, over four weeks

0

Record Linkage and duplicate detection (2/2) GRAVANO, Luis, IPEIROTIS, Panagiotis G., JAGADISH, H. V., KOUDAS, Nick, MUTHUKRISHNAN, S., PIETARINEN, Lauri, SRIVASTAVA, Divesh. Using q-grams in a DBMS for Approximate String Processing. IEEE Data Eng. Bull., 24(4), [28][29][30][31][32][33][34] 2001. GRAVANO, LUIS, IPEIROTIS, PANAGIOTIS G., KOUDAS, NICK, SRIVASTAVA, DIVESH. Text Joins for Data Cleansing and Integration in an RDBMS. Proc. ICDE 2003, pp. 729-731, Bangalore, India, 2003. HERNANDEZ, M., STOLFO, S., The Merge/Purge Problem for Large Databases, Proc. SIGMOD Conf pg 127-135, 1995. LOW, WAI LUP, LEE, MONG-LI, LING, TOK WANG. A Knowledge-Based Approach for Duplicate Elimination in Data Cleaning. Inf. Syst., 26(8), 585-606, 2001. KANG, Hyunmo, GETOOR, Lise, SHNEIDERMAN, Ben, BILGIC, Mustafa, LICAMELE, Louis. Interactive Entity Resolution in Relational Data: A Visual Analytic Tool and Its Evaluation. IEEE Trans. Vis. Comput. Graph. 14(5), pp. 999-1014, 2008. MCCALLUM, ANDREW, NIGAM, KAMAL, UNGAR, LYLE H. 2000. Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching. Proc. KDD 2000, pp. 169-178. Boston, MA, USA. MONGE, ALVARO E. 2000. Matching Algorithms within a Duplicate Detection System. IEEE Data Eng. Bull., 23(4), 14-20. TEJADA, SHEILA, KNOBLOCK, CRAIG A., MINTON, STEVEN. 2002. Learning Domain-Independent String Transformation Weights for High Accuracy Object Identification. Proc. KDD 2002, pp. 350-359, 2002. WEIS, MELANIE, NAUMANN, FELIX, BROSY, FRANZISKA. 2006. A Duplicate Detection Benchmark for XML (and Relational) Data. Proc. ACM SIGMOD 2006 Workshop on Information Quality in Information Systems, IQIS 2006. Chicago, IL, USA. WINKLER, WILLIAM E. Methods for Evaluating and Creating Data Quality. Inf. Syst., 29(7), 531-550, 2004. WINKLER, WILLIAM E., THIBAUDEAU, YVES. An Application of the Fellegi-Sunter Model of Record Linkage to the 1990 U.S. Decennial Census. Tech. Rept. Statistical Research Report Series RR91/09. U.S. Bureau of the Census, Washington, DC, USA, 1991.

Data Profiling

CARUSO, FRANCESCO, COCHINWALA, MUNIR, GANAPATHY, UMA, LALK, GAIL, MISSIER, PAOLO. 2000. Telcordia's Database Reconciliation and Data Quality Analysis Tool. Proc. VLDB 2000, pp. 615-618, 2000. DASU, TAMRAPARNI, JOHNSON, THEODORE, S. Muthukrishnan, V. Shkapenyuk, Mining Database Structure; Or, How to Build a Data Quality Browser, Proc. SIGMOD 2002. Data Preparation and Data Quality Mining HIPP, J., GUNTZER, U., GRIMMER, U. Data Quality Mining -Making a Virtue of Necessity. Proc. Workshop DMKD 2001. LUBBERS, D., GRIMMER, U., JARKE, M. Systematic Development of Data Mining-Based Data Quality Tools. Proc. VLDB 2003, pp. 548-559, 2003. KLINE, R.B., Data Preparation and Screening, Chapter 3. in Principles and Practice of Structural Equation Modeling, NY Guilford Press, pp. 45-62, 2005. PEARSON, Ronald K. Surveying Data for Patchy Structure. SDM 2005. STATNOTES Topics in Multivariate Analysis. Retrieved 10/17/2008 from http://www2.chass.ncsu.edu/garson/pa765/statnote.htm

Duplicate detection

SVMs: high accuracy with limited data [Christen, 2008] Decision trees: interpretable, efficient to apply Perceptrons: efficient incremental training [START_REF] Bilenko | Adaptive Product Normalization Using Online Learning for Record Linkage in Comparison Shopping[END_REF] Classifier

Similarity distance functions

Handling Missing Data Completion Using Association Rules

Based on a consensus from rules with high confidence and user interaction Based on measures scoring the best rules to select the replacement value [Wu et al., 2004] Imputation using NN, Clustering and SVM K-Nearest Neighbour Imputation [START_REF] Batista | An analysis of four missing data treatment methods for supervised learning[END_REF] K-means Clustering Imputation [START_REF] Li | Towards Missing Data Imputation: A Study of Fuzzy K-means Clustering Method. Rough Sets and Current Trends in Computing[END_REF] Fuzzy K-means Clustering [Acuna, Rodriguez, 2004] SVM [START_REF] Feng | A SVM regression based approach to filling in missing values[END_REF]

Projection Based Methods

Projection pursuit techniques are applicable in diverse data situations although at the expense of high computational cost.

No distributional assumptions, search for useful projections Robust: [START_REF] Filzmoser | Outlier detection in high dimensions[END_REF] propose a fast method based on robust PCA with differential weights to maximally separate outliers. [START_REF] Shyu | A novel anomaly detection scheme based on principal component classifier[END_REF] use a similar theme. Time Series: [START_REF] Galeano | Outlier detection in multivariate time series by projection pursuit[END_REF] extend the idea of projecting in directions of high and low kurtosis to multivariate time series. Skewed Distributions: Hubert and Van der Veeken (2007) extend the boxplot idea by defining adjusted outlyingness followed by random projections for detecting outliers in skewed data.

Outlier Detection for Skewed Data [Hubert and Van der Veeken, 2007] For skewed distributions Key concepts

Adjusted outlyingness -different scaling on either side of median in boxplots.

MV equivalent, e.g., bagplot in 2-D Random projections to identify outliers

Distance and Depth Based Methods

Distance-based methods aim to detect outliers by computing a measure of how far a particular point is from most of the data.

Robust methods

Robust distance estimation in high-D [START_REF] Maronna | Robust estimates of location and dispersion for highdimensional data sets[END_REF] [ [START_REF] Pena | Multivariate outlier detection and robust covariance matrix estimation[END_REF] Depth based nonparametric methods

Exotic methods

Angle based detection [START_REF] Kriegel | Outlier Detection Techniques[END_REF] DDMA: Nonparametric Multivariate Moving Average Control Charts Based on Data Depth [START_REF] Liu | Ddma-charts: Nonparametric multivariate moving average control charts based on data depth[END_REF] Extends simplicity of control charts et al., 2006, 2009] Change (Detection) you can believe in: Finding Distributional Shifts in Data Streams [Dasu, Krishnan, Li, Venkatasubramanian, Yi, 2009] Compare data distributions in two windows


Knowledge Engineering IT Process and Workflow Management 4 Types of approach Prevention Diagnostic Correction Adaptation 5 Levels Dimensions Models Techniques Tools Methodologies

Motivation

Data quality problems are: Omnipresent in every application domain Interwoven and complex in any DB, DW or IS Critical to every data management, KDD and decision making project because of their massive financial impact Limitations of current tools : They are ad-hoc, specialized, rule-based, and programmatic They are specific to a single-type of data quality problem They don't catch interdependences between data quality problems Detection and cleaning tools are disconnected

Key Challenges

Dimensionality and complexity

The exact notion of data quality is multidimensional and different from one application domain to another Concomitant data quality problems increase the detection complexity

Uncertainty and ambiguity

The boundary between quality and non-quality data is not precise The boundary between a legitimate anomaly and a data quality problem is hard to define Potter's wheel [START_REF] Raman | Potter's Wheel: An Interactive Data Cleaning System[END_REF] Detection and correction of errors with data transformations: add, drop, merge, split, divide, select, fold, format Interactivity, inference of the data structure

X X

Ajax [START_REF] Galhardas | Declarative Data Cleaning Language, Model, and Algorithms[END_REF] Declarative language based on logical transformation operators: mapping, view, matching, clustering, merging 3 algorithms for record matching X X X X Arktos [START_REF] Vassiliadis | ARKTOS A Tool For Data Cleaning and Transformation in Data Warehouse Environments[END_REF] Graphical and declarative (SQL-like and XML-like) facilities for the definition of data transformation and cleaning tasks, optimization, measures of quality factors

X X

Intelliclean [START_REF] Low | A Knowledge-Based Approach for Duplicate Elimination in Data Cleaning[END_REF] Detection and correction of anomalies using a set of rules (duplicate identification, merge, purge, stemming, soundex, stemming, abbreviation) -Not scalable

X

Bellman [Dasu et al., 2002] Data quality browser collecting database profiling summaries, implementing similarity search, set resemblance, Q-gram sketches for approximate string matching

X X X

Febrl [Christen, 2008] Open source in Python, initially dedicated to data standardization and probabilistic record linkage in the biomedical domain, including Q-gram, sorted Record Linkage (RL) [Elmagarmid et al., 2007] Chaining or Spurious Linkage [START_REF] Kang | Interactive Entity Resolution in Relational Data: A Visual Analytic Tool and Its Evaluation[END_REF] http://www.cs.umd.edu/projects/linqs/ddupe Duplicate search and visualization of cluster-wise relational context for entity resolution Febrl [Christen, 2008]: https://sourceforge.net/projects/febrl/ Rule-based and HMM-based standardization and classification-based record linkage techniques SEMANDAQ [Fan et al., 2008]: CFD-based cleaning and exploration HumMer [START_REF] Kriegel | Outlier Detection Techniques[END_REF]: Data fusion with various conflict resolution strategies XClean [START_REF] Weis | XClean in Action (Demo)[END_REF]: Declarative XML cleaning

Inconsistent Data

Probabilistic Approximate Constraints [START_REF] Korn | Yunyue Checks and Balances Monitoring Data Quality Problems in Network Traffic Databases[END_REF] Given a legal ordered domain on an attribute, A domain PAC specifies that all attribute values x fall within ε of D with at least probability δ, as A functional dependency PAC X → Y specifies that, if

Pseudo-constraints [START_REF] Ceri | Mining constraint violations[END_REF] Pair <P1,P2> where P1 and P2 are predicates on the same domain D such that if P1 holds, then usually P2 also and therefore there are few rule violations. More formally, based on the probability contingency table,

Pattern Tableaux for Conditional Functional Dependencies

A CFD is defined to be a pair et al. 2007[START_REF] Bravo | Extending Dependencies with Conditions[END_REF][START_REF] Golab | On generating near-optimal tableaux for conditional functional dependencies[END_REF][START_REF] Fan | Relative Information Completeness[END_REF] Calculate the mean μ and the D X D variance-covariance matrix Σ 2.

[ ] ( ) δ ≥ ± ∈ ε Pr D x ( ) Y B B T B T X A A T A T j i j i ∈ ∀ ≥ ≤ - ∈ ∀ Δ ≤ - l l l l l l l l . . Pr then . . δ ε [Bohannon
Let C be a column vector consisting of the square of the Mahalanobis distance to the mean μ as: Return O. [START_REF] Rousseeuw | A fast algorithm for the minimum covariance determinant estimator[END_REF] Given n data points, the MCD is the mean and covariance matrix based on the sample of size h (h < n) that minimizes the determinant of the covariance matrix.

Finding Multivariate Outliers

( ) ( ) ( ) ( ) μ σ σ σ σ σ σ σ σ σ μ μ μ - ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ′ - = - Σ ′ - - - x x x x
Minimum Volume Ellipsoid (MVE) [START_REF] Rousseeuw | Unmasking Multivariate Outliers and Leverage Points[END_REF] Let the column vector C with the length d (d > 2) be the estimate of location and let the d-by-d matrix M be the corresponding measure of scatter. The distance of the point x i = (x i1 ,…,x id ) from C is given by: If then x i is declared an outlier. C is center of the minimum volume ellipsoid covering (at least) h points of the data set.

Robust estimators

( ) ( ) C x C x D i i i - ′ - = -1 M 37
Masking the structure of the group of MV outliers (clustered vs scattered)

Limits of EDA methods

The space of cleaning strategies is infinite DQ problems are domain-specific -hard to find general solutions Cleaning solutions may introduce new DQ problems Benchmarking cleaning strategies and ad hoc practices is hard (never been done)

42

Cleaning Explanation

What is Data Quality Mining?

"DQM can be defined as the deliberate application of data mining techniques for the purpose of data quality measurement and improvement. The goal of DQM is to detect, quantify, explain, and correct data quality deficiencies in very large databases." [Hipp, Güntzer, Grimmer, 2001] 43

Data Quality Mining (DQM) intends to be an iterative framework for creating, adapting, and applying data mining techniques for the discovery, explanation and quantitative cleaning of data glitches and their complex patterns in large and patchy datasets.

In addition,

Outline

Part I. [START_REF] Kriegel | Outlier Detection Techniques[END_REF]: http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/tutorial_slides.pdf

Outlier Mining

Projection Based Methods

Projection pursuit techniques are applicable in diverse data situations although at the expense of high computational cost.

No distributional assumptions, search for useful projections Robust: [START_REF] Filzmoser | Outlier detection in high dimensions[END_REF] propose a fast method based on robust PCA with differential weights to maximally separate outliers. [START_REF] Shyu | A novel anomaly detection scheme based on principal component classifier[END_REF] use a similar theme. Time Series: [START_REF] Galeano | Outlier detection in multivariate time series by projection pursuit[END_REF] extend the idea of projecting in directions of high and low kurtosis to multivariate time series. Skewed Distributions: Hubert and Van der Veeken (2007) extend the boxplot idea by defining adjusted outlyingness followed by random projections for detecting outliers in skewed data.

INPUT: An N X d dataset OUTPUT: Candidate Outliers 1.
Compute the principal components of the dataset 2.

For each test point, compute its projection on these components 3.

If y i denotes the i th component, then the following has a chi-square distribution 3.

For a given significance level α, an observation is an outlier if Outlier Mining -Robust PCA ( ) [START_REF] Shyu | A novel anomaly detection scheme based on principal component classifier[END_REF] Outlier Identification in High Dimensions [START_REF] Filzmoser | Outlier detection in high dimensions[END_REF] Works in very high-D, where dimensions > samples, e.g., gene data Differential weights to detect location and scatter outliers; weights combined in final step Based on robust statistics 50 Outlier Detection for Skewed Data [Hubert and Van der Veeken, 2007] For skewed distributions Key concepts

α χ λ 2 1 2 q q i i i y ∑ = ≥ p q y y y y q q q i i i ≤ + + + = ∑ = , 2 2 2 2 1 2 1 1 2 λ λ λ λ L 49
Adjusted outlyingness -different scaling on either side of median in boxplots.

MV equivalent, e.g., bagplot in 2-D Random projections to identify outliers

Probability distributions [START_REF] Eskin | Anomaly detection over noisy data using learned probability distributions[END_REF] Assumption:

High probability to have the number of normal elements in a dataset D significantly larger than the number of outliers

Approach:

From the distribution for the dataset D given by: D= (1-λ) M + λ

  An N X D dataset (N rows, D columns) OUTPUT: Candidate Outliers 1.

  O in C whose value is greater than 4.

  standard deviation are extremely sensitive to outliers (Breakdown point=0%) C Minimum Covariance Determinant (MCD)

  do not have sufficient number of neighbours In high dimensional spaces due to data sparseness When datasets have modes with varying density Computationally expensive

23 Source: Magic Quadrant for Data Integration Tools, Sept. 2008, Gartner RAS Core Research Note G00160825. Commercial ETL Tools

	D a t a E n r i c h m e n t D a t a P r o f i l i n g D a t a A n a l y s i s D u p l i c a t e D e t e c t i o n D a t a C l e a n i n g D a t a T r a n s f o r m a t i o n 1. Pre-processing: transformation and standardization Criteria 2. Select a blocking method to reduce the search space Ability to execute • Product/Service partitioning the dataset into mutually exclusive blocks to
	compare	• •	Overall Viability Sales Execution/Pricing
	•	Hashing, sorted keys, sorted nearest neighbors	•	Market Responsiveness
	•	(Multiple) Windowing	• •	Track Record Marketing Execution
	•	Clustering	•	Customer Experience
			•	Operations
	3. Select and compute a comparison function measuring the Completeness of vision • Market Understanding similarity distance between pairs of records
	•	• • Token-based : N-grams comparison, Jaccard, TF-IDF, cosine similarity Marketing Strategy Sales Strategy
	•	• Edit-based: Jaro distance, Edit distance, Levenshtein, Soundex Offering (Product) Strategy
	•	NN, TF-IDF methods for record linkage and HMM-based standardization Domain-dependent: data types, ad-hoc rules, relationship-aware similarity X X X X X • Business Model • Vertical/Industry Strategy • Innovation measures
	Pentaho-Kettle http://kettle.pentaho.org 4. Select a decision model to classify pairs of records as • Geographic Strategy Open source in Java for designing graphically ETL transformations and jobs such as reading, manipulating, and writing data to and X X (X) (X) (X) (X) from various data sources. Linked to Weka. Easily extensible via Java Plug-ins matching, non-matching or potentially matching
	Talend Open http://www.talend.com Studio 5. Evaluation of the method (recall, precision, efficiency) Java code. Open source based on Eclipse RCP including GUI and components for business process modeling, and technical implementations of ETL and data flows mappings. Script are generated in Perl and X X (X) (X) (X) (X)

Open Issues in DQ management Data Profiling

  ]

	30
	Exploratory Data Analysis (EDA) EDA -Outlier Detection
	Summaries refreshment Incremental re-computation strategies DQ Monitoring Continuous checking of statistical constraints Diagnostic Approaches Database profiling Exploratory data analysis (EDA) EDA Use of simple statistical techniques for exploring and Control chart/error bounds methods understanding the data e.g., expected value; confidence interval or error Usually for variable and model selection and for testing bounds; 3-Sigma, Hampel bounds, IQR distributional assumptions ETL Extending declarative languages with constraints on DQ Active warehousing: online processing operators Optimization Assistance and recommendation of alternative ETL scenarios Corrective Approaches Extract-Load-Transform (ETL) KDD Model-based outlier detection methods EDA for Data Quality e.g., regression model: outlyingness measured Detect data glitches through residuals that capture deviation from the Outliers and extremes Missing values model
	Deduplication Record linkage (RL) High frequency values and duplicates Data transformation for model fitting Multivariate statistics for outlier detection
	Benchmarks Quantitative Cleaning Treatment of glitches
	Over-matching problem Selecting variables and records
	Scalability Replacing using statistical models
	Multi-objective optimization problem
	Embedded FD

EDA -Distance-based outliers 38 O d Nearest Neighbour-based Approaches

	39 40 41
	EDA -Density-based outliers Quantitative Data Cleaning Limits of EDA methods
	A point O in a dataset is an DB(p,d)-outlier if at least fraction p of the points in the data set lies greater than Approaches Deletion (e.g., MCAR/MAR, normality, symmetry, uni-modality) distance d from the point O. Method Compute local densities of particular regions and declare data points in low density regions as potential anomalies Methods Anomalies are treated as a specific category MF Classical assumptions won't work M Inclusion (applicable for less than 15%) F Detection Explanation Cleaning
	Local Outlier Factor (LOF) [Breunig et al., 2000] List-wise deletion omits the complete record (for less than 2%) DQ problems are not necessarily rare events
	Connectivity Outlier Factor (COF) [Tang et al., 2002] Pair-wise deletion excludes only the anomaly value DQ problems may be (partially) correlated from a calculation Multi-Granularity Deviation Factor [Papadimitriou et al., 2003] Substitution (applicable for less than 15%) Explanatory variables/processes may be
	d1 Single imputation based on mean, mode or median d2 O2 external and out of reach O1 replacement Mutual masking-effects impair the detection Linear regression imputation (e.g., -missing values affects the detection of duplicates Multiple imputation (MI) -duplicate records affects the detection of outliers
	Full Information Maximum Likelihood (FIML) -imputation methods may mask the presence of duplicates)

[START_REF] Knorr | Algorithms for Mining Distance-Based Outliers in Large Datasets[END_REF]

Outliers are the top n points whose distance to the k-th nearest neighbor is greatest.

[

[START_REF] Ramaswamy | Efficient algorithms for mining outliers from large data sets[END_REF]

] O NNd NN: O2 is outlier but O1 is not LOF: O1 is outlier but O2 is not

Difficult choice between methods with contradicting results

In high dimensional spaces, factor values will tend to cluster because density is defined in terms of distance

Statistical Solutions [Little & Rubin 1987; Allison 2002; Yuan 2000]

	65
	Probability Based Methods Part II. Data Quality Mining Part II. Data Quality Mining Missing Data Example Issues remain Outline
	A with M: Majority distribution and λ: Anomaly distribution Compute likelihood of D at time t: L t (D) Compare L t (D) with LL t (D) assuming the point o t is outlier at time t Entropy-based methods [He 2003] 1. Outlier Mining 2. Change Detection 3. Handling Missing and Duplicate Data Often, an increase or decrease in outliers is the first sign of a distributional shift Serious implications for data quality -recalibrate anomaly detection methods opportunity to recover and Tools Change detection 1. Outlier Mining 2. Change Detection 3. Handling Missing and Duplicate Data Density change Comparison of telecommunications data sets Anomalous months from month to another Missing Value Imputation [Little & Rubin 1987; Allison 2002] Treat glitches in isolation Part I. Introduction to Data Quality Research No connection between detection and Point estimates cleaning Mean, median Missing data Kdq tree partition Darker greater density Model based Part II. Data Quality Mining No iteration of detection-cleaning Regression Cleaning introduces new glitches? Simulation based difference Automatic detection is speedy, provides an MCMC Cautionary Tales [Allison 2000] Optimal cleaning strategies? Part III. Case Study
	Approach: methods are critical replace data before it is SAS -PROCs MI and MIANALYZE
	Find a k-sized subset whose removal leads to the maximal decreasing of entropy archived [Yuan 2000]

Missing Outliers Duplicates Outliers 75 Interfaces Utilization_Out Utilization_In Bytes_Out Bytes_In Memory CPU Latency Syslog_Events CPU_Poll What Can Be Done?

	Cleaning strategies (ad hoc)
	Impute missing values	component-wise median?
	De-duplicate	retain a random record?
	Outliers	identify and remove? So many methods
	but contradicting results?
	Drop all records that have any imperfection
	Add special categories and analyze singularities in
	isolation
	Almost all existing approaches look at one-shot
	approaches to univariate glitches. Why?

Deletion Imputation Modeling Deletion Fusion Random Selection Deletion Winsorization Trimming Data Missing Values Duplicates Outliers So Many Choices … 77 How do we reduce the number of choices? Which one is the best? Ordering in cleaning matters Ordering in cleaning matters Cleaning Dirty dataset Input: Alternatives: poll# date time inrate outrate 1 08/31/2009 00:56:00 - - 2 09/01/2009 00:01:00 120 130 3 09/01/2009 00:01:00 130 150 4 09/01/2009 00:05:01 - - 5 09/01/2009 00:10:01 110 100 6 09/01/2009 00:10:01 140 140 7 09/01/2009 00:10:01 130 110 median 130 130 sum 630 630 Replacement Only 78 median 130 130 sum 520 520 Replacement Fusion 1 2 130 130 130 130 Ordering in cleaning matters Ordering in cleaning matters Cleaning

									79
	A Cleaning Strategy Based On A Cleaning Strategy Based On
	Dirty dataset Explainable Patterns Input: poll# date 1 08/31/2009 00:56:00 -time inrate Explainable Patterns	outrate -
	Input:					2	09/01/2009 00:01:00 120	130
	Dirty dataset	3 4 08/31/2009 00:56:00 -09/01/2009 00:01:00 130 09/01/2009 00:05:01 -poll# date time inrate outrate 1 -	150 -
			2		5 09/01/2009 00:01:00 120 09/01/2009 00:10:01 110 130	100
			3		6 09/01/2009 00:01:00 130 09/01/2009 00:10:01 140 150	140
	Alternatives: Cleaning	4 5		7 09/01/2009 00:05:01 -09/01/2009 00:10:01 130 -09/01/	110
	1	Fusion	2	Replacement	Fusion choices impact replacement and may
									mask/generate inconsistencies
		#2 #5		#2 #6	#2 #7	#3 #5	#3 #6	#3 #7
	median	115 115 130	135	125	120 120 125 135	145	130	130
	sum-before 230 230 260	270 250	240 240 250 270	290	260	260
				Constraint: Σinrate = Σoutrate

2009 00:10:01 110 100 6 09/01/2009 00:10:01 140 140 7 09/01/2009 00:10:01 130 110 80 missing missing missing missing duplicate duplicate Replacement Using the values of the first adjacent duplicates Explanation duplicate duplicate duplicate Deletion Imputation Modeling Deletion Fusion Random Selection Deletion Winsorization Trimming Data Missing Values Duplicates Outliers A particular path A sequence of strategies Overview 94

		94 96
	Data Quality Research Iterative and	Cleaned Data
	complementary
	Advanced techniques in DQM cleaning strategies	Detection Detection
	Motivating Case study Best DQM strategies Quantitative criteria	Explanation Explanation
	New Directions for DQM Resource-dependent Domain, user and	Cleaning Cleaning
	operational needs
		Patchy Dataset

Iterative Detection and Cleaning Patterns and Dependencies among Glitches Detection Cleaning Explanation Duplicates Deduplication Outliers Uni-and MV-Detection Missing Data Imputation Inconsistent Data Constraint

	Conclusion
	DQM Challenges
	Dimensionality and complexity
	Uncertainty and ambiguity Dynamic nature Thanks
	Benchmarking
	DQM Framework Multidisciplinary approach Any questions?
	Unified process
	Repeatability
	Statistical guarantees

Attributes, every 5 minutes, over four weeks Axes transformed for plotting Multivariate glitches!

Static & temporal Domain and application dependent

 pp. 187-198, 2006. TANG, J., CHEN, Z., FU, A.W.-C., CHEUNG, D.W.-L., Enhancing Effectiveness of Outlier Detections for Low Density Patterns. Proc. PAKDD 2002. LNAI 2336[START_REF] Naumann | Felix Quality-Driven Query Answering for Integrated Information Systems[END_REF]. ZHANG, J., GAO, Q., WANG, H., Spot: A system for detecting projected outliers from high-dimensional data streams. Proc. ICDE 2008, pp. 1628-1631, 2008.

Data Profiling

CARUSO, FRANCESCO, COCHINWALA, MUNIR, GANAPATHY, UMA, LALK, GAIL, MISSIER, PAOLO. 2000. Telcordia's Database Reconciliation and Data Quality Analysis Tool. Proc. VLDB 2000, pp. 615-618, 2000. DASU, TAMRAPARNI, JOHNSON, THEODORE, S. Muthukrishnan, V. Shkapenyuk, Mining Database Structure; Or, How to Build a Data Quality Browser, Proc. SIGMOD 2002. Data Preparation and Data Quality Mining HIPP, J., GUNTZER, U., GRIMMER, U. Data Quality Mining -Making a Virtue of Necessity. Proc. Workshop DMKD 2001. LUBBERS, D., GRIMMER, U., JARKE, M. Systematic Development of Data Mining-Based Data Quality Tools. Proc. VLDB 2003, pp. 548-559, 2003. KLINE, R.B., Data Preparation and Screening, Chapter 3. in Principles and Practice of Structural Equation Modeling, NY Guilford Press, pp. 45-62, 2005. PEARSON, Ronald K. Surveying Data for Patchy Structure. SDM 2005. STATNOTES Topics in Multivariate Analysis. Retrieved 10/17/2008 from http://www2.chass.ncsu.edu/garson/pa765/statnote.htm

Distance and Depth Based Methods

Distance-based methods aim to detect outliers by computing a measure of how far a particular point is from most of the data.

Robust methods

Robust distance estimation in high-D [START_REF] Maronna | Robust estimates of location and dispersion for highdimensional data sets[END_REF] [ [START_REF] Pena | Multivariate outlier detection and robust covariance matrix estimation[END_REF]

Depth based nonparametric methods

Nonparametric methods based on multivariate control charts [START_REF] Liu | Ddma-charts: Nonparametric multivariate moving average control charts based on data depth[END_REF] Outlier detection with kernelized spatial depth function [Cheng, Dang, Peng and Bart, 2008]

Exotic methods

Angle based detection [START_REF] Kriegel | Angle-Based Outlier Detection[END_REF] DDMA: Nonparametric Multivariate Moving Average Control Charts Based on Data Depth [START_REF] Liu | Ddma-charts: Nonparametric multivariate moving average control charts based on data depth[END_REF] Extends simplicity of control charts to higher dimensionsrelatively few assumptions Use any data depth, e.g., simplicial depth to map multidimensional data to a scalar and rank Apply moving average control chart techniques to data depth rank to identify outliers 53 Deepest point, e.g., simplicial depth = contained in most triangles

Other methods

Popular methods: LOF, INFLO, LOCI see Tutorial of [START_REF] Kriegel | Outlier Detection Techniques[END_REF]] Mixture distribution: Anomaly detection over noisy data using learned probability distributions [START_REF] Eskin | Anomaly detection over noisy data using learned probability distributions[END_REF] Entropy: Discovering cluster-based local outliers [START_REF] He | Discovering cluster-based local outliers[END_REF] Projection into higher dimensional space: Kernel methods for pattern analysis [START_REF] Shawne-Taylor | Kernel methods for pattern analysis[END_REF]

Stream Specific Methods

Distance based outliers: Detecting distance based outliers in streams of data. [Anguilli and Fassetti, 2007] Distributed streams: Adaptive Outlier Detection in Distributed Streams [START_REF] Su | Continuous adaptive outlier detection on distributed data streams[END_REF] A general density estimation scheme: Online outlier detection in sensor streams [Subramaniam et al , 2006] Projections and high dimensions: Projected outliers in High-D data streams [Zhang, Gao, Wang, 2008] Items of interest: Finding frequent items in data streams [START_REF] Cormode | Finding frequent items in data streams[END_REF] Online Outlier Detection in Sensor Data Using Non-Parametric Models [Subramaniam et al., 2006] Online

Change Detection Schemes

Comprehensive framework: Detecting Changes in Data Streams. [START_REF] Kifer | Detecting changes in data streams[END_REF] Kernel based: Statistical Change Detection in Multi-dimensional Data. [Song et al., 2007] Nonparametric, fast, high-D: Change Detection you can believe in: Finding Distributional Shifts in Data Streams. [Dasu et al., 2006[Dasu et al., , 2009] ] Change (Detection) you can believe in: Finding Distributional Shifts in Data Streams [Dasu, Krishnan, Li, Venkatasubramanian, Yi, 2009] Compare data distributions in two windows

Handling Missing Data Completion Using Association Rules

Based on a consensus from rules with high confidence and user interaction Based on measures scoring the best rules to select the replacement value [START_REF] Wu | Using association rules for completing missing data[END_REF] Imputation using NN, Clustering and SVM K-Nearest Neighbour Imputation [START_REF] Batista | An analysis of four missing data treatment methods for supervised learning[END_REF] K-means Clustering Imputation [START_REF] Li | Towards Missing Data Imputation: A Study of Fuzzy K-means Clustering Method. Rough Sets and Current Trends in Computing[END_REF] Fuzzy K-means Clustering [START_REF] Acuna | The treatment of missing values and its effect in the classifier accuracy[END_REF] SVM [START_REF] Feng | A SVM regression based approach to filling in missing values[END_REF] Variant of NN based on rules for identifying and merging duplicates (Intelliclean) [Elmagarmid et al., 2007] SVMs: high accuracy with limited data [Christen, 2008] Decision trees: interpretable, efficient to apply Perceptrons: efficient incremental training [START_REF] Bilenko | Adaptive Product Normalization Using Online Learning for Record Linkage in Comparison Shopping[END_REF] Classifier

Duplicate detection

Similarity distance functions

Perspectives

Since the first Data Quality Mining definition:

"Deliberate application of data mining techniques for the purpose of data quality measurement and improvement. The goal of DQM is to detect, quantify, explain, and correct data quality deficiencies in very large DBs."

• Outlier mining

• Change detection

• Constraints and CFD mining

• Imputation using K-means or SVM [Li+04,Feng+05] Recent Advances:

Focus on a single type of glitch in isolation No connection between detection and cleaning

No iteration of the detection-cleaning process [Hipp, Güntzer, Grimmer, 2001] Case

Case Study: Conclusion

IP data stream -multivariate, massive, glitchy Critical for network monitoring Patterns and dependencies in glitches are used to recover much of the data such that the treated dataset is close to the ideal dataset Discovery of explanatory variables is useful for understanding recurrent DQ problems

New Research Directions

Discovering complex and concomitant data glitches '07, pp. 667-676, 2007.


Perrine Soret
email: perrine.soret@u-bordeaux.fr

Marta Avalos

Laurence Delhaes

Rodolphe Thiébaut

A simulation framework of high-dimensional phylogenetic microbiota data

Context

The increasing quality/reducing cost of high-throughput sequencing technology, in particular, 16S rRNA gene sequencing of the bacterial component (and to a lesser extent, ITS2 sequencing of the fungal component) of the human microbial community (microbiota), has enabled researchers to investigate human diseases. Subsequently, microbiota has been associated with numerous diseases, including inflammatory bowel disease, diabetes, cancer and cystic fibrosis. The microbiota sequencing data are measured as reads' counts (often with an excess of zeros), interpreted as a taxon's abundance in a microbial community. To make the microbial abundance comparable across samples, data are typically normalized to the relative abundances of all bacteria observed, that is an example of the so-called Compositional Data (CoDa). CoDa consists of a collection of nonnegative measurements that sum to a constant value, typically, proportions that sum to 1. Because knowing the sum, one component can be determined from the sum of the remainder, the parts that make up the composition are mathematically and statistically dependent. In general, CoDa are mapped from the constrained simplex space to the Euclidian space using nonlinear transforms to allow valid inferences. Also, the microbiota data are organized under a phylogenetic structure that, if deeply assessed, lead to high-dimensionality. In parallel, in response to the needs, there is an intensive emergence of specific statistical methods and computational tools. Because of the recentness, it is still too soon to evaluate the applicability and accuracy of available methods. Simulation studies, in which a sample of random data is computationally generated many times mimicking a real data distribution, are a standard tool to compare the performance of competitive statistical methods.

Notations

n number of subjects ; q number of sample OTUs ; p number of covariates

Z ij ∈ N + raw abundance ; Zij = Z ij q j=1 Z ij ∈ [0, 1] relative abundance of patient i for OTU j Z = (Z 1 , • • • , Z n ) and Z = Z1 , • • • , Zn absolute and relative abundance matrices n × q. X = (X 1 , • • • , X n ) matrix of covariates n × p ; Y = (Y 1 , • • • , Y n ) outcome vector n × 1

Machine learning methods

Method

Penalty Phylogeny R code Lasso β = argmin β Y -Zβ 2 2 + λ|β| No glmnet Elastic-Net β = argmin β Y -Zβ 2 2 + λ α|β| + (1 -α) β 2 2
No glmnet Bayesian Spike-and-slab prior No Available

Log-Contrast β = argmin β Y -Zβ 2 2 + λ|β| p j=1 β j = 0 No Available SGSL Z = Z(1) , • • • , Z(k) , • • • , Z(L) with Z(k) ∈ M (n×p k ) Z(k) = Z(k,1) , • • • , Z(k,m) , • • • , Z(k,M k ) with Z(k,m) ∈ M (n×p k,m ) β = argmin β 1 2 Y - L k=1 Z(k) β (k) + α 1 λ L k=1 √ p k β (k) 2 + α 2 λ L k=1 M k m=1 p k,m β (k,m) 2 + (1 -α 1 -α 2 )λ β 1

levels Available

Phy-Lasso

Z = Z(1) , • • • , Z(k) , • • • , Z(L) with Z(k) ∈ M (n×p k ) t = 1, • • • , T + 1 taxonomic level β = argmin β 1 2 Y -L k=1 Z(k) β (k) -T t=1 L k=1 α t k -λ β 1

All levels Available

StructFDR

Results

CoDa

Absolute microbiome abundances are not informative

Raw abundance

Relative abundance

Z i = Z i1 , • • • , Z iq ∈ R q + Zi = Zi1 , • • • , Ziq ∈ S q C(Z i ) = Z i1 q j=1 Z ij , • • • , Z iq q j=1 Z ij = Zi1 , • • • , Ziq = Zi i = 1, • • • , n Simplex : S q = Zi = Zi1 , • • • , Ziq : Zij > 0, j = 1, • • • , q; q j=1 Zij =

Tuning parameter selection and comparison criteria

Cross-Validation : 10 fold-CV such as

CV (λ) = 1 n K i=1 1 n k i∈D k Y i -Z i β(λ) D k 2
Bootstrap : Select OTUs stably associated to the outcome (100 bootstrap samples) Selection proportion (SP) :

SP βj = 1 B B b=1 I βj,s =0 ∈ [0, 1]

Conclusion

The complexity of microbiome data makes generating realistic data challenging. The negative false rate represents the rate of relevant variable not selected and, conversely, the positive false rate represents the rate of irrelevant variable selected by the method. For the two protocols, the simplest methods (Lasso, ElasticNet) showed better results than the most complex methods (as Log-Contrast or Phylasso). SGSL and the bayesian method selected a higher number of predictors.

When the relevant variables are randomly generated (protocol S2), the selection appeared to be more instable : the rate of false negative presented higher variability between replications.

Globally, when the generated data are relatively simple, as expected, the simplest methods show a better behavior. The most complex methods may outperform in most complex situations (for example, when several OTUs are correlated or when the phylogenetic structure influences the outcome). However, the impact of generating correlated OTUs or accounting for the phylogenetic structure is unclear (Liu, 2015[START_REF] Stephen T Rush | The phylogenetic lasso and the microbiome[END_REF]. The R Code for the simulation framework is available on https ://github.com/psBiostat/SimulationMicrobiomeData.git

H

  0j : the jth OTU is not associated with Y Hierarchical model Permutation-based FDR control algorithm All levels StructFDR

1

 1 Ignoring the compositional nature of the data may induce strong incoherences in correlations and distances Conditions to apply statistical methods Permutation-invariant Scale invariance Subcompositional coherence (Main) Log-ration transformations Additive log-ratio (alr) Centered log-ratio (clr) Isometric log-ratio (ilr) Simulation Protocols π estimated on real data (mean of OTUs) Z ∼ DM(π) ∈ M n×p with n = 30, 100 and p = 75 β choosen following two protocols Y = 54 + alr Z β + ε ε ∼ N (0, σ 2 ) σ 2 determined by signal-to-noise ratio