Omar Krichen

Nathalie Girard

Eric Anquetil

Simon Corbillé

Mickaël Renault

Real-time interpretation of hand-drawn sketches with extended hierarchical bi-dimensional grammar

Keywords: Online recognition of handwriting, Bidimensional structured document interpretation, Pen-based interaction, Digital learning

This paper presents a generic method for eager interpretation of online hand-drawn sketches. This work takes place within the ACTIF project, with the objective of designing an e-learning system for geometry lessons in middle-schools. The goal is to analyze on the fly the child's inputs (using a pen-based interaction on tablet), and to give real-time feedback (visual, corrective, or guidance ones). We are therefore faced with the constraint of real-time strokes interpretation. We propose to use an incremental analysis process enabling to decrease the search space size. Nevertheless, we encounter combinatorial problems given the application field is complex. For example, create subfigures from an existing one means the parser has to consider all possible combinations of connected segments that are contained in the original shape. To tackle this issue, we extend the definition and the parsing of bi-dimensional grammars by formalizing a hierarchy between production rules. Therefore, we propose alternative exploration strategies and reduce the search space of applicable production rules at any given level of the analysis. Thus, the parser is able to dynamically switch between the exploration strategies in the analysis process. The system has been tested with different drawing scenarios of geometric figures sketching. It reached interesting real-time performance, without loosing the generic aspect of the approach.

I. INTRODUCTION

This work is in the context of ACTIF, an innovative project that aims to promote active learning in middle schools. The objective is to design an intelligent tutoring system for geometry lessons, based on a stylus and thumb interaction on tablets. The popular tools used in middle schools, such as Geogebra [START_REF] Bhagat | Incorporating GeoGebra into geometry learning -A lesson from India[END_REF], which belong to the family of Dynamic Geometry Software, mostly rely on a drag-and-drop approach, i.e the child has to choose geometric objects from a graphical panel and then place their components on the drawing zone. One limitation is that these software require a training phase for the pupils since their approach is different from the traditional pen and paper setup. Another limitation is that dragging and dropping tend to limit the fluidity of the drawing process, and therefore the creative liberty of the user. In [START_REF] Fiorella | Learning as a generative activity: Eight learning strategies that promote understanding[END_REF], Fiorella and Mayer demonstrate that "generative drawing", i.e learning by drawing, has a positive impact on students learning abilities. This paper presents a new pen-based interactive system for geometry learning. To overcome the limitations explained before, our approach simulates the traditional pen and paper figure sketching which allows to avoid the training phase. Moreover, our system recognizes on the fly the child's productions, which gives them more creative liberty (see Fig. 1.a). More broadly, beyond the geometry problematic, our objective is real time recognition of handwritten sketches for different types of structured documents. That is why we propose a generic method for eager interpretation of online hand-drawn strokes. We distinguish between two types of handwritten documents interpretations methods: lazy [START_REF] Ghorbel | Interactive interpretation of structured documents : application to the recognition of handwritten architectural plans[END_REF] and eager [START_REF] Lank | On-line recognition of UML diagrams[END_REF]. Lazy interpretation consists in analyzing the user's drawing after its completion. Eager interpretation consists in analyzing the handwritten strokes on the fly, which is more suited to our goal of having real-time feedback interventions to detect the child's errors, if any, and to guide him to answer the teacher's instruction. There are two major approaches for symbol recognition: statistical and structural. Statistical approaches [START_REF] Delaye | Hbf49 feature set : A first unified baseline for online symbol recognition[END_REF] rely on classifiers and are well suited for isolated shape recognition. However, they cannot model the document structure. Since we are in Geometry context, the system has to recognize not only the geometric shapes, but also to model the spatial relations between them. Structural approaches model a symbol as a set of graphic primitives with determined structural relations. For instance, a triangle is considered as three segments linked by spacial relations. In this context, several works have been done in mathematical expressions recognition. For examples, in [START_REF] Zanibbi | Evaluating structural pattern recognition for handwritten math via primitive label graphs[END_REF] labelled graphs are used for recognition, while in [START_REF] Muñoz | Recognition of on-line handwritten mathematical expressions using 2D stochastic context-free grammars 48 and hidden Markov models[END_REF] a bi-dimensional extension to the Stochastic Context Free Grammar is used for mathematical expressions analysis. Another interesting approach is Ladder [START_REF] Hammond | LADDER, A Sketching Language for User Interface Developers[END_REF], a generic description language, which was applied in a digital learning context for truss diagrams interpretation [START_REF] Atilola | Mechanix : A natural sketch interface tool for teaching truss analysis and free-body diagrams[END_REF]. Structural approaches main limitation is the difficulty to include uncertainty, which is the advantage of the statistical approaches. In this work, to model the geometry knowledge, we use Context Driven Constraints Multi-set Grammar (CD-CMG) [START_REF] Macé | Eager interpretation of on-line hand-drawn structured documents: The DALI methodology[END_REF], a generic formalism for eager interpretation of hand-drawn documents. Actually, the advantage of CD-CMG is that this formalism is a combination between a statistical approach (to locally recognize a shape) and a structural approach (to model the spacial relations and the global document structure). The methodology is based on the compilation of the formalized knowledge in CD-CMG, the generation of the associated symbol recognition engines, and the exploitation of the compiled knowledge with a generic parser. CD-CMG has been applied on various types of documents such as architectural plans [START_REF] Ghorbel | Interactive interpretation of structured documents : application to the recognition of handwritten architectural plans[END_REF] or electrical sketches [START_REF] Macé | Eager interpretation of on-line hand-drawn structured documents: The DALI methodology[END_REF]. These application fields are close to geometric field, so this approach is well suited for our objective. However, for the creation of more complex sketches, the existent version of CD-CMG could not cope with the constraint of real-time analysis. To tackle this issue, our contribution consists in extending this formalism by defining a hierarchy between different layers of interpretation, which allows to have alternative exploration strategies in order to reduce the search space size. The paper is organized as follows. The formalism and the knowledge is explained in Sec. II. Sec. III describes the formalism extension towards a hierarchical grammar to cope with the constraint of real-time analysis. Experiments and results are presented in Sec. IV. Conclusion and future works are given in Sec. V.

II. KNOWLEDGE MODELLING

This section presents the CD-CMG formalism, and illustrates it through its adaptation to the Geometry field.

A. Context Driven Constraints Multiset Grammar

CD-CMG is formally defined as follows: Definition 1. A CD-CMG is a tuple G=( V N , V T , S, P) with:

• V N : the set of non terminal symbols = symbol classes; • V T : the alphabet, here V T = {stroke}; • S: the first symbol, or axiom; • P: the set of production rules.

And where a production rule p ∈ P is denoted as follows:

α → β      Preconditions Constraints Postconditions      | α ∈ V N + , β ∈ (V T ∪ V N ) +
Preconditions and postconditions are based on the concept of Document Structural Context (DSC) defined hereafter, and which models a zone in the document and the awaited elements in it.

Definition 2. A DSC is defined by (λ)[position](γ)[part]

where:

• λ is a set of reference elements;

• position is a zone (i.e a position) related to λ;

• γ is a set of awaited symbols in this zone;

• part is a part of the awaited symbol that has to intersect the zone.

Triangle: res → segment: s1, segment: s2, segment: s3 where:

Preconditions: (s1) [TotalLengthSegment] (s2) (s3) [extremity] & (s2) [TotalLengthSegment] (s1) (s3) [extremity] & (s3) [TotalLengthSegment] (s1) (s2) [extremity]
Constraints: LinkedSegments(s1, s2, s3) The postconditions are a set of DSCs created after the reduction of the production, to update the document's structure. This formalization enables to drive the analysis process by the context. Indeed, the preconditions represent the verification step while the postconditions represent the prediction step. The constraints model a local vision on the analyzed elements β. They have two purposes: checking that the shape of β is consistent with the production, and decide if it is pertinent to reduce β into α. Fig. 2 presents a production rule example in the Geometry field, i.e. the triangle production rule. Fig. 3 and Fig. 4 illustrate the roles of the preconditions and postconditions blocks. In Fig. 3, a new stroke is drawn, with its extremities linked with two contact zones (in green in Fig. 3). This will result in reducing this stroke to a new segment [AC] and creating its postcondition DSCs. The fact that at least one postcondition DSC relative to triangle creation is activated (blue zones in Fig. 3 + new segment DSC) will trigger the triangle production rule. This is the prediction step. The system will then check that all the precondition DSC are satisfied for the production, to verify that the context is coherent for triangle creation. This is the verification step. The constraints block (red rectangle in Fig. 2) contains a structural constraint which verifies that the segments intersect in three different points. Note that it is also possible to call a shape recognizer in the constraints block. The postcondition DSC (blue zone in Fig. 3) models the fact that an inscribed circle production will be triggered if all the points of a circle c are located in T riangleZone.

Postconditions (res)[TriangleZone] (Circle: c) [All] =⇒ [Inscribed-Circle → c]

B. Existent parser diagnostic

The analysis process, extensively explained in [START_REF] Macé | Eager interpretation of on-line hand-drawn structured documents: The DALI methodology[END_REF], is a combination of a bottom-up strategy (guided by the reduced elements) and a top-down strategy (guided by the postcondi-tions DSCs). For each new element, the parser searches the DSC it satisfies and vice versa. Consequently, a production is triggered if its β elements contain at least a new element and its precondition block contains at least a new DSC. Fig. 5 illustrates a scene composed of a new stroke t and 3 existing segments. The analysis of t leads to the construction of the analysis (or derivation) tree, presented in Fig. 6. The root represents the stroke t. The nodes and the leaves represent the triggered rules, while the blue dotted path is the sequence of reduced production rules, i.e the analysis result.

For the decision making process (see detail in [START_REF] Macé | Eager interpretation of on-line hand-drawn structured documents: The DALI methodology[END_REF]), each production rule is associated to a score which depends on the context coherence and constraint validity. The score of a production, denoted ρ p and defined in eq. 1, is a fuzzy combination between the membership degree of its preconditions (p preconditions for context coherence), and the membership degree of its constraints (p constraints for constraint validity). A production is applicable if its score is higher than a given threshold.

ρ p = p constraints . p preconditions (1)
The score of an hypothesis (or branch), which is a sequence of productions, is the fuzzy combination of the involved production scores. The exploration strategy (breadth-first or depth-first) is also explicit in CD-CMG and specific for each production rule. By default, it is breadth-first. The FirstRule operator, set on a rule for depth-first exploration, allows dynamic switching between strategies during the analysis process. For depth-first exploration, the parser will reduce the first applicable production rule and stop the search. The resulting elements and DSCs (from the production reduction) will be the starting points of the analysis rerun. For breadthfirst strategy, the parser explores all the possible interpretations and chooses the hypothesis with the highest score. As shown in Fig. 6, for the production rules that constitute an ambiguity risk, such as segment and arc, we adopt a breadth-first strategy.

For polygons rules we adopt a depth-first strategy: once a production is applicable, it is reduced (the red paths in Fig. 6 are productions that are not tested because of the type of exploration). We establish a natural hierarchy between the productions, e.g a triangle can be reduced into isosceles triangle.

C. Limits of CD-CMG

As we can see in Fig. 6, the quadrilateral production rule is triggered even if there is no coherent context for creating a quadrilateral in this scene. This is due to the fact that this production contains a new element (AD) and one of their precondition DSCs is satisfied. The impact on the combinatorics is not important here, but when the document is complex, the analysis becomes costly. Even though the formalism is generic and expressive enough to model the prior geometry knowledge, the multiple possible interactions between geometric objects, e.g creating sub-figures from existing ones, also generate combinatorial problems in the analysis process. Plus, one specificity of this field is the fact that there are multiple layers of interpretation: the basic symbol recognition layer, detecting symbol connections (such as intersections or segment divisions), and another semantic layer which recognizes geometric figures such as triangles or quadrilaterals. With CD-CMG, it is only possible to define two layers of interpretations, such that one layer stands for breadth-first type rules, and the other stands for depth-first type rule. This is not sufficient to control properly the analysis complexity. To tackle this issue, we extend the formalism and modify its associated parser such that it includes different layers of interpretation by introducing the concept of hierarchy between interpretation layers.

III. TOWARDS A HIERARCHICAL GRAMMAR

This section introduces the complexity issue of the analysis process and our proposed solution, establishing different levels of hierarchy between production rules and precondition contexts, to control the search space size for the analysis process.

A. Context hierarchization

There can be multiple coherent contexts to reduce a production rule, as shown in Fig. 7, which illustrates the segment creation production rule. The precondition block is a dis-junction of three preconditions, modeling the fact a stroke can be linked to two segments -a , one segment -b , or to nothing -c . We can see from Fig. 5 that the three preconditions are valid for segment creation. The context search space is similar to the rule search space. This means that the parser will consider these preconditions as three independent segment production rules, expand the tree in a breadth-first fashion, and choose the one with the highest score. The existent FirstPrecondition operator is similar to the FirstRule operator (c.f Sec. II), such that it specifies that the exploration strategy for context search is depth-first, i.e the parser will choose the first valid precondition without exploring the others (see Fig. 8). Within the chosen precondition, the search space is constituted of the elements that satisfy the specified precondition. In this ) that are linked to the stroke t by their extremities. A limit to the existent formalism is that there is no alternative exploration strategy in this second layer of the context search. In this example, within the first valid precondition -a , t can be linked to the couples (AB, BD), (AB, DG), (AF, BD) or (AF, DG) (c.f. Fig. 5). Since there is only one exploration strategy in this context search layer (breadth-first), the parser will consider these four hypothesises as independent segment production rules, therefore multiplying the analysis complexity by four. In order to have coherent strategies at all levels of the search (at production level, at precondition level, and context level), we extend the formalism by defining a new operator FirstContext. This operator allows a depth-first search exploration strategy for context research (c.f. Fig. 9) within the same precondition. Therefore, the combination of FirstPrecondition and FirstContext forces the parser to stop the context search at the first valid hypothesis within the first valid precondition (i.e. with (AB, BD) in the example). The impact on the analysis process is illustrated in Fig. 9. This will drastically reduce complexity, without losing information about connections. In rare cases, choosing the first context, which is not necessarily the best, can generate errors. This limit is compensated by the fact that the user can either implicitly validate the interpretation, or delete the last stroke and redraw.

B. Production hierarchization

The existent interpretation logic considers that there are two strategies for two types of production rules: the first type of rules is for basic symbol recognition, and the corresponding strategy is breadth-first to ensure a valid interpretation. The second type is low risk productions, such as segment intersections or edition rules, and the corresponding strategy is depth-first, to reduce the analysis complexity. Depth-first type production rules are prioritized, such that parser switches to breadth-first exploration if there is no applicable low risk production. This logic is valid when the application field is simple, e.g having a breadth-first strategy for graphical primitives recognition and a depth-first strategy for symbols connections. However, when considering other semantic layers, such as figure and sub-figure detection, we face the existent logic limits. Indeed, we consider polygons creation as low-risk production rules, therefore setting the FirstRule operator on these productions to specify the type of exploration is depth-first. The problem is that the parser can take time before finding the valid production to reduce, since the production rule search space size increases as the application field becomes more complex. Therefore, depth-first strategy for low risk productions is not sufficient to cope with realtime analysis. To solve this issue, we extend the CD-CMG grammar in order to include the notion of hierarchy between production rules, defining as much hierarchy levels as there are semantic interpretation layers for the application field. We define a new operator RuleLayer, such that for each production, it will specify the corresponding semantic layer. This means that at a particular level of the analysis tree, the parser will only trigger productions belonging to the same hierarchy level. Let's explain the impact of this extension for the geometry field. We establish three hierarchy layers in this case:

• RuleLayer=1: {"Classic" productions}: to recognize a basic shape, such as segment, arc, angle or a circle. The associated strategy is breadth-first, to avoid invalid shape recognition (ambiguity between segment and arc, for example); • RuleLayer=2: {Connection productions}: when the intersection between segments generates sub-segments, hence updating the document structure. The associated exploration strategy is depth-first. The experiments where realized on a windows 64bits, Intel i7 at 2.90 GHz with 16 GB RAM.

B. Impact of context hierarchization

The scene (Fig. 14) illustrates a drawn stroke that will produce an analysis process. The stroke will be first interpreted as segment [DG]. This segment will trigger the creation of two trapezoids, an isosceles triangle and one right-angled triangle (Fig. 15). TABLE I presents the comparative results between CD-CMG and our formalism extension. The classic CD-CMG cannot not cope with the constraint of real-time analysis (2.65 seconds). The addition of FirstPrecondition operator allows to control the complexity but the analysis time is still not transparent for real-time user interaction since it takes up to 1.9 seconds. This is due to the high number of triggered rules (1350), and the high number of iterations (72) which is caused by the computation of 8 equivalent interpretations at the context level. By switching the exploration strategy for context search to depth-first, F irstContext operator forces the parser to consider only the first valid interpretation, therefore reducing the analysis time down to 0.35 seconds.

C. Impact of rules hierarchization

The scene (Fig. 16) illustrates a drawn stroke that will produce an analysis process. The stroke will be first interpreted as segment [HI]. This segment will trigger 6 divisions which will create 8 new sub-segments. These new elements will trigger the creation of a right-angled triangle, two trapezoids, and one quadrilateral (Fig. 17). TABLE II presents the impact of our established hierarchy on the system performance. The prioritization of connection rules over polygon rules allows to decrease the analysis time from 2.26s to 1.02s. The number of triggered productions decreases from 1997 to 1484. Therefore, we can say that our extension of CD-CMG formalism allows the design of a system with an acceptable performance given the constraint of real-time interaction. Beyond these improvements, the user interaction conditions have an important role in our system, the following section presents the characteristics of our prototype.

D. Qualitative study 1) Edition mode: In the traditional pen and paper setup, we often use symbols or codes to explicit geometric properties such as orthogonality or equality. We extend this notion by designing command gestures that not only display properties, but also modify physically the objects, with respect to these properties. These gestures are integrated in the grammar as strokes triggering production rules, therefore modifying the geometric objects. The orthogonality command gesture is illustrated in Fig. 18. 2) Virtual tools: Pen interaction with the dominant hand is considered as better for actions that demand a high precision level, while Touch input is well suited for zooming, or object manipulation. Our virtual ruler is inspired from the one developed by Microsoft (e.g "Windows Maps" application). The user can freely move the virtual ruler on the drawing surface by dragging it with one or two fingers. The ruler will therefore follow the fingers movement (rotation, translation) (c.f Fig. 19). To manipulate the compass, the user first chooses a stationary point with the pen. Then, he sets the compass length, and finally he draws his arc on the virtual compass circle (c.f Fig. 20). These tools are going to be tested in pilot middle schools in order to evolve towards suited tools for the children. In this paper, we propose an e-learning system for geometry learning on tablets in middle-school. Our engine is based on the extension of CD-CMG formalism to analyze the user's productions in real-time. Adding the notion of hierarchy in the grammar to cope with the multiple interpretation layers had a significant impact on the system's performance, enabling to control the analysis complexity. Our future work consists in designing an teacher mode, where the instruction and all the possible solutions will be generated from the teacher's drawing. The objective is to detect the child's intentions and guide him through his realization of the exercise based on teacher's instruction. This will end in having a personalized teaching tool that will help make the child autonomous. The versions of this prototype will be tested in pilot middle schools and the works of our partners in ergonomics and cognitive science will help us to design well suited feedback to enhance learning performance.

Fig. 1 :

 1 Fig. 1: Overview of the system: Prototype interface (a), handwritten figure (b), interpreted and beautified figure (c)

Fig. 2 :

 2 Fig. 2: Triangle production rule

Fig. 6 :

 6 Fig. 5: Analysis process

Fig. 7 :

 7 Fig. 7: Part of segment production rule

FirstPreconditionFig. 9 :

 9 Fig. 8: Analysis with FirstPrecondition

Fig. 10 :

 10 Fig. 10: Drawn stroke Fig. 11: Result: 6 segments, 3 trapezoids

•

  RuleLayer=3: {Polygons productions}: for figure and sub-figure detection. The associated strategy here is depth-first. Fig. 10 and Fig. 11 illustrate the analysis of a drawn stroke t. At the stroke level, only classic productions are explored in breadth-first manner. This stroke interpretation as a segment led to the creation of 6 sub-segments by the division of [AB], [DC], [EB], and [FC]. Three new trapezoids were also created due to the new connections generated by these segments. It

Fig. 14 :

 14 Fig. 14: Drawn stroke Fig. 15: Analysis result

Fig. 16 :

 16 Fig. 16: Drawn stroke Fig. 17: Analysis results

Fig. 18 :

 18 Fig. 18: Including geometry codes as command gestures: Orthogonality command (a), result (a')

Fig. 19 :

 19 Fig. 19: Ruler tool Fig. 20: Compass tool

TABLE I :

 I First benchmark analysis results

	Approach	Iterations Interpretations	Time	Triggered
	(1): CD-CMG+F irstRule	135	15	2.65 s	2526
	(2): 1 + F irstP recondition	72	8	1.91 s	1350
	(3): 2 + F irstContext	9	1	0.35 s	289

TABLE II :

 II Second benchmark analysis results

	Approach	Iterations Interpretations	Time	Triggered
	3	14	1	2.26 s	1997
	3 + three levels of hierarchy	14	1	1.02 s	1484

• Iterations: number of reduced productions rules,• Interpretations: number of branches in the analysis tree;• Time: analysis time;• Triggered: number of triggered rules. The evaluation is done on two complex benchmarks, illustrated in Fig.14, 15, and Fig.16, 17. The performance is

ACKNOWLEDGMENT "ACTIF" is funded by the French government project e-fran (BPI) and the region of Brittany. The authors would like to thank the Caisse des Dépôts/GIP-Far, as well as the academic partners, the LP3C and LOUSTIC laboratories.

Fig. 13: Impact of hierarchy on the analysis tree is clear then that the polygon productions depend strongly on the connections between the segments, therefore on the connection productions (here the division). Without our established hierarchy, the DSCs created by each division will trigger polygons rules, which adds unnecessary complexity to the analysis process, since the connections links between the segments are not completely updated yet. Since each segment creates 21 DSCs (to manage all possible interactions with other objects), and since the division does not replace the original segment, we are rapidly confronted with a combinatorial problem when the document is complex. The analysis tree without hierarchy is illustrated in Fig. 12. By establishing our hierarchy, only the productions belonging to the same layer will be triggered, therefore polygon productions are triggered only if there is no more applicable connections productions. The prioritization of connection rules will therefore reduce the analysis complexity by reducing the number of triggered rules. The hiearchization impact on the analysis tree is illustrated in Fig. 13. By integrating the presented operators, a production rule will be defined as follows:

IV. EXPERIMENTS AND RESULTS

A. Quantitative study

To evaluate the impact of our contributions on the system performance, the following criteria are used:


Guillaume Metzler

Xavier Badiche

Brahim Belkasmi

Elisa Fromont

Amaury Habrard

Marc Sebban

Learning maximum excluding ellipsoids from imbalanced data with theoretical guarantees

Introduction

The study of imbalanced data is an active and important topic due to its huge economical impact, for example in anomaly or fraud detection in applications related to banks, medicine, intrusion detection, video-surveillance, fault detection or industrial processes [START_REF] Agrawal | Survey on anomaly detection using data mining techniques[END_REF][START_REF] Khalilia | Predicting disease risks from highly imbalanced data using random forest[END_REF][START_REF] Chandola | Anomaly detection: A survey[END_REF][START_REF] Goldstein | A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data[END_REF]. In such applications, datasets are usually composed of a large number of negative examples (e.g. genuine transactions, normal MRI, normal human behavior, etc.) and only a few positive data (e.g. frauds, faults, hacking, etc.). From a theoretical point of view, imbalanced scenarios raise two main challenging problems for the machine learning and data mining communities. First, the large majority of classic supervised learning methods optimize the accuracy by minimizing error-based loss functions, like the hinge loss in Support Vector Machines, the exponential loss in Boosting, or the logistic loss in Logistic Regression. However, if one class is rare, those methods will struggle to capture any useful information about this class and will obtain a high accuracy by simply predicting all (possibly new) examples as being of the majority class(es). Second, deriving theoretical results in an imbalanced setting is difficult and many existing approaches come without any specific guarantee. In this paper, we aim at addressing both issues by designing a new algorithm -driven by the minority class -for which generalization guarantees are derived. Unlike the state of the art, our method does not resort to sampling preprocesses. Indeed, it is worth noticing that classic methods typically consist of over/under-sampling the data [START_REF] Aggarwal | Outlier Analysis[END_REF] or creating synthetic examples in the neighborhood of the minority class [START_REF] Chawla | Smote: Synthetic minority over-sampling technique[END_REF] in order to get more balanced sets.

However, as we will see in this paper, when the datasets become highly imbalanced (i.e. no more than 2-3% positives), those methods usually fail to model the minority class because they suffer from an inability to generate enough diversity which is key for a sampling method to work well. In such extreme situations, two main families of solutions are available. The first one consists of designing alternative loss functions able to directly capture the imbalance in the data and usually based on the F-Measure, the area under the ROC curve, or the Average Precision [START_REF] Frery | Efficient top rank optimization with gradient boosting for supervised anomaly detection[END_REF]. The main pitfalls related to this line of research concern the difficulty to deal with non smoothed and non convex measures. The second category of methods aims at changing the original problem into an unsupervised anomaly detection task. This is for example done by Support Vector Data Description (SVDD) [START_REF] Azami | Robust outlier detection with L0-SVDD[END_REF][START_REF] Pauwels | One class classification for anomaly detection: Support vector data description revisited[END_REF][START_REF] Tax | Support vector data description[END_REF]) methods such as one-class SVMs (OCSVM) [START_REF] Heller | One class support vector machines for detecting anomalous windows registry accesses[END_REF] which work on unlabeled data. SVDD learns the smallest enclosing ball which includes most of the training data and excludes all examples lying in the tail of the data distribution, which are considered as anomalies. More formally, the goal is to solve the following constrained optimization problem given a sample of n instances:

min R,c,ξ R 2 + µ n n i=1 ξ i , s.t. x i -c 2 ≤ R 2 + ξ i , ∀i = 1, . . . , n, ξ i ≥ 0, (1)
where R and c are respectively the radius and the center of the ball and ξ i is the slack variable associated to the i th instance x i . µ is tuned in order to control the proportion of the data outside the sphere (considered as anomalies). Note that in [START_REF] Pauwels | One class classification for anomaly detection: Support vector data description revisited[END_REF], the authors have shown that using the radius instead of the square of the radius in this formulation is often preferable. Several refinements of the SVDD method can be found in the literature to take more than one class into account (e.g. see [START_REF] Liu | Minimum enclosing and maximum excluding machine for pattern description and discrimination[END_REF] and [START_REF] Boujnouni | New decision function for support vector data description[END_REF] for binary problems) or to use multiple local models and apply non linear transformation to the data [START_REF] Le | Fuzzy multi-sphere support vector data description[END_REF][START_REF] Boujnouni | New decision function for support vector data description[END_REF]. Even if the kernel-based methods are effective, the computation of the kernel is often expensive (according to the number of examples in the dataset) and does not scale well on most real datasets. An interesting approach, which does not suffer from this drawback, is presented in [START_REF] Wang | An effective support vector data description with relevant metric learning[END_REF]. The authors include a linear transformation of the data, in the form of a Positive Semi Definite (PSD) matrix M in the SVDD optimization problem. To avoid high computational costs, they set M to be the inverse of the covariance matrix, which allows the induction of ellipsoids rather than spheres. Such objects are able to cover a larger volume in the input space compared to the spheres. In this paper, we present a supervised machine learning method called M E 2 -for Maximum Excluding Ellipsoids -that can tackle imbalanced data without requiring sampling strategies. We exploit the idea of learning multiple local models to capture non linearity at a cheap cost as in [START_REF] Le | Fuzzy multi-sphere support vector data description[END_REF] and combine it with a metric learning formulation. However, we learn local models centered at each minority class example which exclude the examples of the majority class(es). This, contrary to the previously cited methods, allows us to consider settings where the minority class examples do not necessarily behave as anomalies but may be hidden within one of the modes of the data (e.g. in fraud detection). Unlike [START_REF] Wang | An effective support vector data description with relevant metric learning[END_REF], we optimize both the shape and the orientation of the ellipsoid by learning a Mahalanobis distance based on a PSD matrix M. This geometrical flexibility allows us to capture more accurate and potentially larger areas around the minority class examples. A nice property of our approach is that M can be obtained in closed-form solution ensuring directly (and for free) the positive definiteness of M [START_REF] Shi | Sparse compositional metric learning[END_REF][START_REF] Perrot | Regressive virtual metric learning[END_REF]. Therefore, we prevent the algorithm from having to check the positiveness of the eigenvalues of M, which has a cubic complexity in the size of M, as required by many metric learning algorithms [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF][START_REF] Bellet | Metric Learning[END_REF]. Beyond its algorithmic contribution, materialized by M E 2 , this paper also aims at providing guarantees on the learned models based on the uniform stability framework [START_REF] Bousquet | Stability and generalization[END_REF]. We prove that our algorithm is stable, i.e. robust to changes in the training set.

To sum up, our contribution is four-fold:

1. We introduce a simple strategy consisting of learning local models centered at each positive example (which can be done in parallel) allowing us to capture non linearity in the feature space. This way, our algorithm is particularly relevant in the context of imbalanced settings where (i) the number of local models to learn is very small but (ii) the minority examples (i.e. the centers of the ellipsoids) play a key role.

2. We show that M E 2 is algorithmically efficient by demonstrating that the learned matrices satisfy the PSD constraint for free.

3. We prove that M E 2 is theoretically founded by deriving generalization guarantees on the learned models.

4. We experimentally show that M E 2 is effective compared to the state of the art methods, particularly on highly imbalanced settings.

As far as we know, M E 2 is the first method able to gather all those interesting features in the field of learning from imbalanced data.

The rest of this paper is organized as follows: In Section 2, we present the convex formulation of our algorithm M E 2 with both primal and dual formulations. Section 3 is devoted to the theoretical study of our algorithm. We show that M E 2 is stable which provides some insight into the variance of the algorithm with respect to changes in the training set. In Section 4, we compare our algorithm to some state-of-the-art methods. We conclude in Section 5.

2 M E 2 : a metric learning-based algorithm for optimizing excluding ellipsoids

Problem formulation

Let S = {x i } n i=1 be a sample of n negative instances (the majority class) and P = {c j } p j=1 a set of p positive examples (the minority class), with n >> p and where x i , c j are feature vectors of R d . We aim at maximizing ellipsoids centered at each positive c ∈ P excluding (most of) the negative data x i , i = 1, ..., n. Learning such ellipsoids boils down to optimizing a Mahalanobis distance, that is finding a positive semi-definite (PSD) d × d matrix M projecting the data linearly in a new space and allowing to obtain balls centered at each positive example of maximum radius R. Let B be an upper bound of the possible expected radius. Our algorithm, called M E 2 for Maximum Excluding Ellipsoids, can be expressed in the following form: where

min R,M ,ξ 1 n n i=1 ξ i + µ(B -R) 2 + λ M -I 2 F , s.t. x i -c 2 M ≥ R -ξ i , ∀i = 1, . . . , n, ξ i ≥ 0, B ≥ R ≥ 0, (2)
x i -c 2 M = (x i -c) T M(x i -c) is the learned Mahalanobis distance, ξ is the vector of slack variables, µ(B -R) 2 + λ M -I 2
F is a regularization term with µ, λ > 0 the corresponding regularization parameters, I the Identity matrix and • F is the Frobenius nom. Note that the upper bound B of the radius is used in µ(B -R) 2 to have a convex formulation allowing us to get a unique solution. We choose two different parameters for each part of the regularization term to control the surface area of the sphere in the transformed space and the complexity of the matrix M. The parameter λ gives the possibility to control the magnitude of the entries of M, and therefore the shape/orientation of the ellipsoid. In practice, the bigger λ is, the closer x i -c 2 M to the Euclidean distance (i.e. the ellipsoid looks like a ball). On the other hand, the parameter µ controls the size of the learned ellipsoids.

An illustration of our algorithm is given in Figure 1. On the right, we constrain M E 2 to learn spheres (i.e. λ is set to a large value such that M tends to be the identity matrix). On the left, we allow M E 2 to optimize both the orientation and the size of the ellipsoid. We can see that M E 2 can capture local peculiarities of the feature space. It is worth noticing that λ and µ are key parameters to deal with anomaly/fraud detection in imbalanced settings. Indeed, we will show that they can be used to improve the F-Measure by controlling the precision and the recall.

Note that we can establish a relationship between M E 2 and a decision tree algorithm [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]. Indeed, in both cases, decision rules take the form of local geometric shapes (an ellipsoid for M E 2 and a rectangle for a decision tree). In Figure 2, we report on the same toy example as in Figure 1 the leaves learned by a decision tree algorithm containing each positive example as well as the ellipsoids optimized by M E 2 . We can notice that while decision trees build axis-parallel hyperplanes to generate the leaves, M E 2 has a better expressiveness allowing to control the shape, the orientation and the size of the ellipsoids. We think that this is an interesting feature that can be favorably exploited to capture local specificities of the feature space and better estimate the density function of the positives.

Dual version and closed-form solution

Note that Problem 2 can also be expressed in its dual form which leads to a closed form solution. The Lagrangian is given by:

L(α, β, δ, γ, R, ξ, M) = 1 n n i=1 ξ i + µ(B -R) 2 - n i=1 γ i ξ i - n i=1 α i x i -c 2 M -R + ξ i + λ M -I 2 F -βR + δ(R -B), (3)
where α = (α i ) i=1,...,n , γ = (γ i ) i=1,...,n , β and δ are the dual variables. By setting to zero all the derivatives of (3) with respect to the primal variables we get:

R = β -δ + 2µB -n i=1 α i 2µ , M = I + 1 2λ n k=1 α k (x k -c)(x k -c) T , and 0 ≤ α i ≤ 1 n ∀i.
The second equality shows that M is, by construction, positive definite (PD). Fulfilling the PD constraint for free is very important because it prevents the algorithm from performing a singular value decomposition (in O(d 3 )) at each step of the gradient descent.

The dual formulation of Problem ( 2) is then obtained by injecting the expression of both R and M in the Lagrangian (3). The dual optimization is then obtained by minimizing the opposite of the Lagrangian with respect to its dual variables:

min α,β,δ α T 1 4λ G + 1 4µ 1 n×n α + β 2 4µ + δ 2 4µ + α T diag(G) -B + β 2µ - δ 2µ 1 n + β B - δ 2µ , s.t. 0 ≤ α i ≤ 1 n , ∀i = 1, . . . , n, β, δ ≥ 0, ( 4
)
where G is the Gram matrix defined by G ij = (x i -c), (x j -c) and G is the Hadamard product of G with itself. 1 n (respectively 1 n×n ) represents a vector of length n (respectively a matrix of size n × n) where entries are equal to 1.

Generalization Guarantees

One of our main contributions in this paper takes the form of a generalization guarantee on the algorithm M E 2 . Since we learn a local model from a subset of training examples we need to prove the ability of M E 2 to perform well in generalization -that is -to exclude correctly new negative instances from the learned ellipsoid centered at this positive example. To do so, we derive in this section a generalization bound according to the theoretical framework of uniform stability [START_REF] Bousquet | Stability and generalization[END_REF].

Uniform Stability

Roughly speaking, an algorithm is stable if its output does not change significantly under a small modification of the training sample. A formal definition is given below.

Definition 1. [START_REF] Bousquet | Stability and generalization[END_REF] A learning algorithm has a uniform stability in β n with respect to a loss function and a parameter set θ, with β a positive constant if:

∀S, ∀i, 1 ≤ i ≤ n, sup x | (θ S , x) -(θ S i , x)| ≤ β n ,
where S is a learning sample of size n, θ S the model parameters learned from S, θ S i the model parameters learned from the sample S i obtained by replacing the i th example x i from S by another example x i independent from S and drawn from P . (θ S , x) is the loss suffered at x.

One can then obtain the following generalization bound1 :

Theorem 1 (from [START_REF] Bousquet | Stability and generalization[END_REF], Thm 12). Let δ > 0 and n > 1. For any algorithm with uniform stability β/n, using a loss function bounded by b, with probability 1 -δ over the random draw of S:

L(θ S ) ≤ LS (θ S ) + 2β n + (4β + b) ln 1/δ 2n ,
where L(•) is the true risk and LS (•) its empirical estimate over S.

Generalization Bound

Given a centroid c (representing a positive instance) and a learning sample S = {x i } n i=1 of negative instances drawn i.i.d. from an unknown probability distribution P -, the set of parameters to be learned by M E 2 is the pair (R, M). For convenience, we consider the following optimization problem that is equivalent to Problem 2:

min R,M 1 n n i=1 (R, M, x i ) + µ(B -R) 2 + λ M -I 2 F , s.t. B ≥ R ≥ 0.
(5)

where (•) represents the loss such that (R, M,

x i ) = 1 n [R -x i -c 2 M ] + with [•]
+ the hinge loss function: [a] + = max(a, 0). The true risk is defined by L(M, R) = E x∼P -(M, R, x) and its empirical estimate over the sample S by LS (M, R) = 1 n n i=1 (M, R, x i ) . We also denote the regularization term as

N (M, R) = µ(B -R) 2 + λ M -I 2
F and assume that data are bounded by K. F S denotes the function to be minimized, i.e.:

F S (M, R) = L(M, R) + N (M, R).
Note here that it can easily be checked that our loss function is convex with respect to M and R.

To prove a generalization bound on our algorithm M E 2 , we need to prove that our setting verifies the definition of uniform stability. For this purpose, we first prove that our loss function is actually k-lipschitz in its first two arguments.

Lemma 1. The loss is k-lipschitz with respect to M and R with k = max(1, 4K 2 ), i.e.: for any (M, R), (M , R ), ∀x:

| (M, R, x) -(M , R , x)| ≤ k (M, R) -(M , R ) , where (M, R) -(M , R ) = |R -R | + M -M F .
Proof. The proof uses successively the fact that the hinge loss is 1-lipschitz and a property of the absolute value. We then use the Cauchy-Schwarz inequality and classic properties on norms.

We now need a technical lemma on the objective function F S .

Lemma 2. Let S be a learning sample, let F S and F S i be two objective functions with respect to samples S and S i and let (M, R) and (M i , R i ) be their respective minimizers. We also define

∆(M, R) = (M i , R i ) -(M, R) and recall that N (M, R) = µ(B -R) 2 + λ M -I 2 F .
We have, for all t ∈ [0, 1]:

N (M, R) -N ((M, R) + t∆(M, R)) + N ((M i , R i ) -N ((M i , R i ) -t∆(M, R)) ≤ 2t max(1, 4K 2 ) n ∆(M, R) .
Proof. The left hand side of the previous inequality can be written as follows:

µ[(B -R) 2 + (B -R i ) 2 -(B -(R + t∆R)) 2 -(B -(R i -t∆R)) 2 ] + λ[ M -I 2 F + M i -I 2 F -M + t∆M -I 2 F -M i -t∆M -I 2 F ] = µθ(R) + λτ (M) (for the sake of simplification) (6)
The upper bound is then given by using the same development as the one given in the proof of lemma 20 from [START_REF] Bousquet | Stability and generalization[END_REF].

We are now able to prove the stability of our algorithm.

Proposition 1. It exists a positive constant κ such that the algorithm M E 2 is uniformly stable with

β = 2(max(1, 4K 2 )) 2 κ min(µ, λ) .
Proof. We give here the main steps of the proof, using notations introduced before.

Setting t = 1 2 we have from Lemma 2

µθ(R) + λτ (M) ≤ max(1, 4K 2 ) n ∆(M, R) . (7)
Then, by developping the left hand side of equation ( 7) we have:

µ(R i -R) 2 + λ M i -M 2 F ≤ 2 max(1, 4K 2 ) n ∆(M, R) . (8) Recall that ∆(M, R) = |R -R i | + M i -M F .
Because we are working in a finite space, all the norms are equivalent, i.e. it exists a positive constant κ such that,

∀(R, R i ) ∈ R + , ∀(M, M i ) ∈ R d×d
we have:

κ(|R -R i | + M i -M F ) 2 ≤ (R -R i ) 2 + M i -M 2 F . ( 9
)
The left hand side is equal to κ ∆(M, R) 2 . Thus, by multiplying ( 9) by min(µ, λ) and using the inequality (8), we have:

∆(M, R) ≤ 2 max(1, 4K 2 ) nκ min(µ, λ) .
Finally, starting from the left-hand side of Definition 1 and applying Lemma 1 and the previous inequality leads to our result.

It remains to show that our hinge-loss function is bounded, which is the case because the radius is bounded by B, so is . Given the stability constant and the fact that the loss is bounded, using Theorem 1, we obtain our final result:

Theorem 2. Let δ > 0 and n > 1. There exists a constant κ > 0, such that with probability at least 1 -δ over the random draw over S, we have for any (M, R) solution of Problem 5:

L(M, R) ≤ LS (M, R) + 4(max(1, 4K 2 )) 2 nκ min(µ, λ) + 8(max(1, 4K 2 )) 2 κ min(µ, λ) + B ln 1/δ 2n .
This generalization bound holds for any positive center c. If one has p positive centers, by the union bound, we can extend the previous result for each of the p centers with probability 1 -δ/p showing that the learned ellipsoids can exclude negative instances with high probability. We can notice that the bound implicitly depends on the dimension of the data through the hyperparameters µ and λ.

Experiments

Algorithms and Datasets

In this section, we aim at evaluating the behavior of M E 2 in comparison to some state of the art algorithms. Those methods have been selected to characterize some specificities of M E 2 .

• Since we established a link between our local ellipsoids and the rules induced by decision trees in the form of local rectangles (Figure 2), we compare M E 2 with standard decision trees (DT). The objective here is to show that the learned ellipsoids better capture the local information of the input space.

• To deal with imbalanced datasets, a commonly used strategy consists of sampling the data to fix the imbalancy problem. Therefore, we also learn a decision tree DT O (resp. DT U ) after a pre-processing step which consists of oversampling (with replacement) the minority class examples (resp. undersampling the majority class examples). We also combine the two previous approaches (DT OU ). Finally, we apply a SMOTE-like strategy [START_REF] Chawla | Smote: Synthetic minority over-sampling technique[END_REF] (DT SM OT E ) which creates synthetic minority class examples in the neighborhood of the positive data. The goal of this comparison is to show how M E2 behaves even if it does not resort to sampling processes.

• When the proportion of positive examples is too small, some Support Vector Data Description methods (SVDD) [START_REF] Azami | Robust outlier detection with L0-SVDD[END_REF][START_REF] Pauwels | One class classification for anomaly detection: Support vector data description revisited[END_REF][START_REF] Tax | Support vector data description[END_REF]) -like one-class SVMs [START_REF] Heller | One class support vector machines for detecting anomalous windows registry accesses[END_REF] -address the anomaly detection problem as an unsupervised outlier detection task. We run here one-class SVMs with two kernels: a linear kernel (LOCSVM) and a RBF kernel (KOCSVM). The objective of this comparison is to check if M E 2 makes a good use of the few positive labels compared to unsupervised methods. We also make use of the labels and run standard linear SVMs (LSVM), and RBF kernel-based SVMs (KSVM).

All the classifiers are trained using the corresponding machine learning packages in R 2 , that is C50 for the decision trees, e1071 for the SVMs, DMwR for SMOTE and Rsolnp for M E 2 .

The experiments are performed on 6 datasets coming from the UCI and KEEL databases3 and one proprietary database on a bank fraud detection task. Their characteristics (number of examples, features, imbalance ratio IR) are described in Table 1. Note that the categorical variables have been replaced by binary features.

Experimental setup

As explained in the introduction, the classic accuracy is not a suitable criterion to address issues due to the presence of imbalanced data. For this reason, we evaluate the algorithms using the F-measure defined as the harmonic mean of the Precision and Recall criteria, where F-measure = 2×Precision×Recall

Precision+Recall with P recision = T P T P +F P and Recall = T P T P +F N , where T P is the number of true positives, F P the number of false positives and T N the number of true negatives. For each series of experiments, the dataset is divided into 80%/20%. A 2-fold cross-validation is applied on the first set S (while preserving the same IR in each fold) to tune the hyperparameters. The second set is used as a test set. Each experiment is repeated 10 times and the reported results are the averages over the 10 trials.

Remember that we learn an ellipsoid centered at each positive example of S. This ellipsoid defines in some way the local region of the projection space which is under the influence of the considered positive example. In this context, at both validation (to tune the parameters) and test time, a query x is associated to its closest positive example N x (with respect to the Euclidean distance) in the training set. Then, in order to take into account the local density of positives and negatives in the corresponding ellipsoid, and following the idea suggested in [START_REF] Barandela | Strategies for learning in class imbalance problems[END_REF], we apply the following decision rule. x will be predicted as positive if: 1) It is inside the ellipsoid centered at N x . This means that x is actually under the influence of N x which occurs when the corresponding learned Mahalanobis distance verifies: x -N x M N x ≤ R N x , where M N x is the PSD matrix learned by M E 2 corresponding to the ellipsoid centered at N x and R N x is its associated radius. 2) Its nearest neighbor in the ellipsoid is a positive example with respect to the learned local distance xx M N x . Otherwise, x is predicted as negative. Note that the hyper-parameters µ and λ are tuned respectively in the range {0.75, 0.8, 0.85, 0.9, 0.95, 1, 2, 10} and {10 -6:2 } by maximizing the F-Measure for each local model according to the previous rule.

Results

The results are reported in Table 2. The datasets are sorted from the least to the most imbalance ratio to see the effect of M E 2 with a decreasing rate of positive examples. We can make the following remarks:

• On average, M E 2 outperforms all the other methods even if it does not resort to sampling processes. As shown in Figure 3, its average rank over the 7 datasets (2.6) is better than the others. If we focus on the 5 datasets with large imbalancy (Wine, Abalone17, Yeast6, Abalone20 and the Bank Fraud ), M E 2 is even better with an average rank of 1.4.

• For the first two datasets (i.e. Yeast3 and Abalone) where the rate of positive examples is greater than 10%, our method is not very useful. This behavior can be explained by two reasons: (i) when the number of learned ellipsoids grows, their overlapping is larger and larger and therefore the False Positive rate increases; (ii) a large number of ellipsoids induces an increasing risk of generating close ellipsoids with different orientations and shapes. About this second point, an interesting perspective would consist of constraining close positive examples to have similar ellipsoids.

• Compared with decision trees, these experiments show that M E 2 has a much better capacity to capture the local specificities of the feature space than the local rectangles learned by decision trees.

For three datasets, it is worth noticing that decision trees even do not capture anything (Wine, Abalone17, Abalone20 ).

• The results obtained by one-class SVMs are much worse than the other methods. This behavior shows that for all the datasets, including the bank fraud database, the positive examples cannot be considered as outliers and that their underlying distribution is likely to be multimodal.

• M E 2 works better than SVMs while the latter use a reweighting scheme in the objective function to balance the data. We also report in Table 2 the average running time for one run of each method. Note that since M E 2 can be parallelized, we report the running time required for tuning and solving the optimization problem 2. We can see that since M E 2 learns matrices that directly satisfy the positive semi definiteness, our method is efficient, i.e. very close to decision trees. However, note that if one uses M E 2 without parallelizing the learning of the p ellipsoids, the running time will be on average p times the result reported in Table 2. But M E 2 will be still efficient (at least better then kernelized-SVMs) since p is supposed to be very small in highly imbalanced scenarios.

Conclusion

We have presented a method to learn Maximum Excluding Ellipsoids in the context of imbalanced binary classification tasks. Our algorithm, called M E 2 , is based on simple local linear models. Moreover, we have proven its uniform stability which takes the form of a generalization bound on the learned matrix M. We have shown that our method is particularly efficient and robust when the rate of positive examples is very small. The reason comes from the fact that M E 2 is able to learn decision boundaries in the form of ellipsoids (via a metric learning-based strategy) that are optimized locally to better fit the specificities of the space. M E 2 is based on a very simple decision rule looking for the nearest ellipsoid to a test query. We think that this rule may benefit from further investigation, e.g. by considering a combination of ellipsoids to predict the label of a test data. This would be possible by using a graph over the ellipsoids centers where information would be shared like in an information network. Besides, from a theoretical point of view, we have derived a guarantee on the learned matrix M and radius R. Since our decision rule is close to a nearest neighbor classifier decision rule, it would be interesting to establish a link between the quality of M and R and the generalization error of such a classifier. Another perspective would be to partition the positive example space and constrain the ellipsoids to be similar in terms of orientation (using some regularization) if they have been learned from the same cluster. Finally, in a context of fraud detection where the fraud strategy tends to evolve through time, developing an online version of our algorithm might be relevant to better capture distribution shifts.

Figure 1 :

 1 Figure 1: Illustration of the interest of learning ellipsoids (on the left) rather than simple spheres (on the right). Optimizing the size and the orientation of the ellipsoids allows us to better capture local peculiarities.

Figure 2 :

 2 Figure 2: Boundaries of the decision rules with M E 2 and a decision tree algorithm. The expressiveness of M E 2 is better to capture local specificities of the density function of the positives.

Figure 3 :

 3 Figure 3: Average ranks over all the datasets (top) and over the five most imbalanced datasets (bottom).

Table 1 :

 1 Number of instances, number of features, Imbalance Ratio (i.e. number of positives over the number of instances).

	Dataset	Nb. of ex. Nb. of feat.	IR
	Yeast3	1 484	8	10.9%
	Abalone	4 177	8	10.7%
	Wine	1 599	11	3.3%
	Abalone 17	2 338	8	2.5%
	Yeast6	1 484	8	2.4%
	Abalone 20	1 916	8	1.4%
	Bank Fraud	15 000	17	1%

Table 2 :

 2 Comparison of the methods in terms of F-Measure over 10 runs. The best results are indicated in bold font. The last column reports the average running time (in sec) for one run.

	Algorithm	Yeast3	Abalone	Wine	Abalone17	Yeast6	Abalone20	Bank Fraud	Time
	DT	0.77 ± 0.06	0.64 ± 0.03	0.00 ± 0.00	0.00 ± 0.00	0.51 ± 0.23	0.10 ± 0.15	0.00 ± 0.00	3.2
	DTO	0.75 ± 0.06	0.64 ± 0.04	0.06 ± 0.09	0.35 ± 0.08	0.45 ± 0.12	0.30 ± 0.15	0.04 ± 0.03	3.5
	DTU	0.76 ± 0.08	0.67 ± 0.03	0.09 ± 0.11	0.28 ± 0.11	0.49 ± 0.11	0.19 ± 0.20	0.04 ± 0.03	2.4
	DTOU	0.72 ± 0.04	0.61 ± 0.04	0.15 ± 0.06	0.34 ± 0.05	0.36 ± 0.12	0.30 ± 0.12 0.05 ± 0.04	2.6
	DTSMOT E	0.65 ± 0.10	0.57 ± 0.07	0.14 ± 0.12	0.24 ± 0.09	0.18 ± 0.09	0.27 ± 0.13	0.04 ± 0.03	28.1
	LSVM	0.67 ± 0.05	0.62 ± 0.01	0.14 ± 0.08	0.29± 0.01	0.30 ± 0.05	0.23 ± 0.02	0.03 ± 0.02	702.5
	RBFSVM	0.66 ± 0.09	0.63 ± 0.03	0.07 ± 0.08	0.17 ± 0.06	0.36 ± 0.09	0.13 ± 0.13	0.00 ± 0.00	39.2
	LOCSVM	0.01 ± 0.02	0.11 ± 0.03	0.02 ± 0.07	0.10 ± 0.05	0.00 ± 0.00	0.05 ± 0.13	0.03 ± 0.01	28.3
	KOCSVM	0.01 ± 0.02	0.21 ± 0.04	0.01 ± 0.07	0.06 ± 0.03	0.00 ± 0.00	0.05 ± 0.11	0.00 ± 0.00	1472.0
	M E 2	0.67 ± 0.06	0.61 ± 0.03	0.20 ± 0.09 0.46 ± 0.07	0.46 ± 0.08	0.30 ± 0.07 0.05 ± 0.02	2.9

If this result was proposed in the context of regression and classification tasks, the proof techniques are general enough -by considering generic bounded and lipschitz losses -so that it also holds for the setting considered in this section.

https://www.r-project.org/

These datasets can be found either on the UCI Repository (https://archive.ics.uci.edu/ml/datasets.html) or the KEEL website (http://sci2s.ugr.es/keel/imbalanced.php?order=ir#sub60).


Grégoire Herzog
email: gregoire.herzog@lcpme.cnrs-nancy.fr

Waleed Moujahid

Karen Twomey

Conor Lyons

Vladimir I Ogurtsov
email: ogurtsov@tyndall.ie

On-chip electrochemical microsystems for measurements of copper and conductivity in artificial seawater

The fabrication and characterisation of microelectrochemical sensors for Cu 2+ , dissolved oxygen and conductivity suitable for operation in the marine environment are presented. The impact of the designs on sensor performance and their adequacy to operate in real conditions are discussed. The sensors are fabricated on silicon using photolithographic and thin film deposition techniques. They represent a complete microelectrochemical cell tailored to voltammetric, amperometric and impedimetric measurements. The impedimetric sensor is made of Pt interdigitated electrodes which are used for the measurement of conductivity. The amperometric and voltammetric sensors are based on a three electrode electrochemical cell with on-chip Ag|AgCl reference and Pt counter and working electrodes, used for detection of oxygen and copper. Dissolved oxygen is detected by chronoamperometry; Cu 2+ sensing is based on underpotential depositionstripping voltammetry at microelectrode array. The sensor operated in the Cu 2+ concentrations ranging from 0.48 to 3.97 µM with a limit of detection of 0.115 M. The impact of the temperature, the pH and the salinity of the artificial seawater on the sensitivity for Cu 2+ detection are also considered. Measurements of copper concentration and conductivity are validated using certified reference materials and standard solutions.

Introduction

Electrochemical methods are of particular interest for in-situ environmental applications as operating procedures remain simple and are without or with limited sample pre-treatment, which is essential for their implementation outside the laboratory. Miniaturised electrochemical sensors offer a number of advantages over macroscopic electrodes including (i) improved mass transport and hence increased sensitivity (due to the hemispherical diffusion); (ii) improved signal to noise ratio; (iii) reduced iR drop [1]. Thus, microfabricated electrochemical sensors can provide sufficient sensitivity and achieve required limits of detection for practical applications due to improved mass transfer and signal to noise ratio. A number of miniaturised electrochemical sensors for autonomous in-situ measurements have been developed [2][3][4][5][6][7][8][9]. Autonomous electrochemical systems were devoted to the detection of heavy metals in sea water by either cathodic stripping voltammetry [2,3] (CSV) or anodic stripping voltammetry [4][5][6][7] (ASV). Concentration of dissolved oxygen in seawater has also been monitored using electrochemical sensors [8,9]. These types of sensors have been incorporated within autonomous monitoring systems for in-situ measurements [10]. More recently, wearable electrochemical sensors and instrumentation have been integrated into a watersport wetsuit [11]. Three types of amperometric sensors (for phenol, heavy metals and trace explosive) were incorporated in the garment. Chemical and physical sensors can be integrated in autonomous environmental monitoring systems, which allow the measurements of pollution and quality levels in fixed sampling locations [11][12][13][14][15][16][17]. In our previous studies, we have investigated the impact of the microelectrode array design on the cyclic voltammetry response of ferrocene monocarboxylic acid [18]. Such microelectrode arrays have also been modified with conducting polymers or thiols for the detection of hydrogenophosphate in organic solvents [19]. More recently, reference and counter electrodes were integrated into a single chip and characterised in artificial sea water by cyclic voltammetry of ferricyanide [20]. We report here the use of microfabricated electrochemical sensors for the measurement of Cu 2+ concentration and conductivity in artificial seawater. Cu 2+ has been selected as a model pollutant present in seawater, whereas conductivity can indicate indirectly the presence of pollution. Furthermore, sensitivity for Cu 2+ can vary with conductivity value. Hence, it may be important to know the conductivity value to be able to correct the Cu 2+ concentration measured. Cu 2+ is detected by underpotential depositionstripping voltammetry (UPD-SV) as it offers a number of advantages for electroanalytical applications [21]. Underpotential deposits only covers a small portion of the electrode surface, leaving the electrode surface mainly unchanged. At the maximum, one monolayer is deposited so the preconcentration times are short; finally, it is possible to detect metals in the presence of dissolved oxygen. The microelectrochemical system was implemented with two types of microelectrochemical sensors fabricated using photolithographic techniques. The first type of sensor was a threeelectrode cell made of a platinum working microelectrode array, a Ag|AgCl reference electrode and a platinum counter electrode. The second type was made of platinum interdigitated electrodes. The three-electrode cell was characterised by cyclic voltammetry of ferricyanide in artificial seawater and was subsequently used for UPD-SV of Cu 2+ and for the reduction of dissolved oxygen. In the literature, the performance of miniaturised electrochemical sensors, and of microelectrode arrays are mostly evaluated and discussed based on cyclic voltammetry experiments [22,23]. However, this electrochemical method is seldom used for analytical applications due to its lack of sensitivity. Indeed, stripping voltammetry techniques at micro-electrode arrays are generally used for the detection of metals in solution [24]. The influence of the geometry of the microelectrode array (radius, spacing, number of electrodes) on the analytical response of Cu 2+ UPD-SV is discussed in order to optimise the microelectrode array design to achieve the best analytical performance. Conductivity of artificial seawater was measured by application of electrochemical impedance spectroscopy at the interdigitated electrodes of different designs.

Experimental Microfabrication and microelectrochemical cell design

The sensors designed for this work were: a three-electrode cell for voltammetric (copper) and amperometric (dissolved oxygen) detection and an interdigitated electrode pair for impedimetric measurements. The sensors were fabricated as described previously on individual chips [18][19][20]. The three-electrode Pt cell comprised a working microelectrode array, an L-shaped counter electrode and a pad for the reference electrode was fabricated at the first stage of the process (mentioned above). To prepare the reference electrode, a drop of silver paint was placed on the Pt pad, and the silver paint was cured at 120 °C for 1 hour. The silver paint is then oxidised by cyclic voltammetry in 1 M KCl between 0 and 1 V at scan rate 10 mV s -1 to form a Ag|AgCl electrode. Eight working microdisc electrode arrays (named A1 to A8) in a hexagonal arrangement were designed with different numbers of electrodes in the array (N = 4, 16, 64 or 256), different electrode radii (r = 5, 10, 15 and 20 m) and different interelectrode spacing (S= 200 and 400 m). Four designs of interdigitated electrodes (named I1 to I4) for conductivity measurements were fabricated with varying geometrical parameters: electrode length, width and spacing. The geometric parameters of these designs are summarised in Table 1. Each fabricated chip was made of one electrochemical cell or one set of interdigitated electrodes.

Electrochemical measurements and reagents

All electrochemical experiments were performed in a Faraday cage and each measurement was carried out four times (unless stated otherwise). The sensors were cleaned beforehand in a plasma cleaner (Harrick Plasma, New-York, USA) for five minutes at high frequency at 100 W, 600 mTorr. A CHI620A potentiostat of CH Instruments (purchased from IJ Cambria, Burry Port, Wales, UK), linked to a personal computer, was used for the voltammetric and amperometric studies. The stripping of the copper underpotential deposits was done by SW voltammetry with the following parameters: Amplitude: 25 mV; Frequency: 15 Hz, Increment: 4 mV. Impedimetric measurements were performed by electrochemical impedance spectroscopy (EIS) using an Autolab PGSTAT302N electrochemical workstation from Metrohm Ltd. The temperature of the tested solutions was set at 25 °C using a LaudaEcoline Model E-200 circulator. EIS was performed over the frequency range 0.1 Hz to 1 MHz at an applied potential of 0.2 V DC bias and a 5 mV AC amplitude. All chemicals used in this study were purchased from Sigma-Aldrich Ireland Ltd and used as received. The electrolyte solution employed in the experiments was artificial seawater with the following composition: 400 mMNaCl, 20 mM MgCl2, 20 mM MgSO4, 10 mM CaCl2 and 10 mMKCl [25,26]. The pH of the solution was adjusted to 6.5 by addition of HCl. Control of pH was performed using a Benchop pH/ISE meter Model 520A (Orion Research Inc. USA) and was calibrated before each use. Artificial seawater of varied salinity was prepared according to ratios published by Hansson [27]. The reference material "LGC6016 Estuarine water -Traces metals" used for the Cu sensor validation was purchased from LGC Standards (UK) and represented estuarine water taken from the Seven Estuary, UK, offshore from a heavily industrialised area near Avonmouth. The conductivity sensors were characterised over a range of standard KCl solutions with conductivity values equal to 1.413, 10.00, 12.90, 20.00 and 50.00 mS cm -1 within which the range of seawater conductivity coincides [28]. The conductivity standards were purchased from Sigma Aldrich and Reagecon Ltd. A standard conductometer (712 Conductometer from Metrohm, Switzerland) was used to measure the conductivity of artificial seawater and standard KCl solutions.

Results and discussion

Characterisation of the microelectrochemical cell

The fabricated microelectrochemical cells were tested by cyclic voltammetry of 1 mM ferricyanide in artificial seawater at scan rate 10 mVs -1 (Figure 1). In all cases, a sigmoidal shape was observed for each of the designs A, indicating an occurrence of hemispherical diffusion of the ferricyanide towards the microdiscs with absence of overlapping between the diffusion zones of neighbouring microdiscs for the timescale of the experiments. The limiting currents, iL, obtained experimentally for the different designs by averaging of 6 experiments were then compared to the theoretical values calculated from Equation (1) [START_REF] Bard | Eletrochemical Methods: Fundamentals and Applications[END_REF]:

r L N nFDCr = i L   + 4 4 2 (1)
Here, n is the number of electron exchanged in the reaction (n = 1), F is the Faraday constant (96,485 C mol -1 ), D is the ferricyanide diffusion coefficient (D = 7.6 × 10 -6 cm 2 s -1 [START_REF] Stackelberg | [END_REF]), C is the bulk concentration (in mol cm -3 ), r is the radius of the microdisc (in cm), N is the number of microdiscs in the array and L is the recess due to the silicon nitride layer (5 × 10 -5 cm). The equation implies that the microdiscs in the array are sufficiently spaced there is no overlap of the diffusion zones of neighbouring electrodes. The experimental and theoretical values of the limiting current were similar, which confirmed the adequate spacing and suitable fabrication process. Figure 1A shows the voltammograms for designs A1-4 with the number of microdiscs in the array varied from 4 to 256. The radius (r) and spacing (S) were kept constant (r = 10 m and S = 200 m). The limiting currents increased linearly with the number of microdiscs in the array (inset of Figure 1A) with a slope of 2.3 nA per electrode with a coefficient of determination r 2 = 0.99998. The experimental values of the limiting currents (in round brackets) in comparison with the theoretical ones obtained by using Equation (1) [in square brackets] were as follows: (10.4 ± 0.19) nA vs. [11.0nA] for design A1, (38.6 ± 2.02) nA vs. [44.1nA] for design A2, (152 ± 3.84) nA vs. [176nA] for design A3 and (594 ± 4.87) nA [706nA] for design A4. As one can see the theoretical limiting current exceeded the experimental data providing a discrepancy between current values in the range between 6 % and 18%. The discrepancy as the number of microdiscs in the array increased, which can be attributed to the presence of 'dead' or inactive µdiscs in the array, which eventually lead to a lower limiting current [31,32].

Figure 1B shows the voltammograms for designs A3, A5, A6 and A7, with the radius r varied from 5 to 20 m. The number of microdiscs in the array N was equal to 64, and the centre-to-centre spacing S was kept equal to 20r. The limiting current values increased with increasing electrode radius as expected from equation (1). However, the current density increased when the radius decreased (see Inset in Figure 1B) due to the improved mass transport at microdiscs of smaller dimension. Once again, the experimental limiting current values were in reasonable agreement with the theoretical values: (71.1 ± 5.61) nA vs. [83.3 nA] for design A5, (152 ± 3.84) nA vs. [176nA] for design A3, (267 ± 2.86) nA vs. [270nA] for design A6 and (334 ± 3.99) nA vs. [364nA] for design A7 (discrepancy between current values was between 8 and 17 %). Once more, the theoretical limiting current exceeded the experimental data but in contrary to the previous findings, the discrepancy decreased as the number of microdiscs increased. Again this discrepancy is attributed to the presence of inactive electrodes in the array.

The influence of centre-to-centre spacing between neighbouring microdiscs on the limiting current is shown in Figure 1C by example of the array with r = 10 m. The neighbouring microdiscs spacing S was 20r (design A3) and 40r (design A8). No significant differences between the experimental limiting currents were observed: (152 ± 3.84) nA for design A3 and (146 ± 4.83) nA for design A8.

UPD-SV of Cu 2+

As preliminary experiments, a series of three UPD-SV scans was performed: (1) UPD-SV in artificial seawater in the absence of copper; (2) a UPD-SV of 1.5 M Cu 2+ in artificial seawater and (3) UPD-SV in artificial seawater in the absence of copper. After the third scan, a residual underpotential deposit of Cu was stripped from the surface of the electrode (data not shown). This indicated the need to introduce electrochemical steps to produce a fresh and clean electrode surface for the subsequent experiments. The potential waveform for the UPD-SV procedure was the following [START_REF] O'mahony | Heavy Metal Sensors for Remediation of River and Sea Water[END_REF]: (1) a preconditioning step at + 0.8 V for 5 s; (2) a cleaning step at + 0.45 V for 45 s; (3) a preconcentration step at -0.15 V for 90 seconds; (4) a detection step by square wave voltammetry starting at -0.15 V and finishing at 0.6V (Figure 2A). The preconditioning and the cleaning steps are necessary to remove any residual metal underpotentially deposited during previous experiments. The application of this procedure regenerated the sensor surface and produced a consistent reference CV prior to copper detection (data not shown). The 90 s preconcentration time was selected based on previous work on the UPD-SV of copper at microelectrode arrays [20].

UPD-SV of copper at the eight different microelectrochemical cells was then undertaken for increasing concentrations of copper using the procedure described above. Figure 2B shows the UPD-SV results for design A4 for concentrations ranging from 1 to 5 M. A calibration curve for copper is shown in inset. For each concentration, the stripping peak current value was the average of 6 measurements. Table 2 displays different sensor parameters for designs A1-8.The sensitivity of UPD-SV depends on the diffusion type (hemispherical or linear) occurring at the microelectrodes during the preconcentration step. The diffusion type is itself related to the geometrical parameters of the microelectrochemical cells. As expected, the geometrical parameters of the microelectrode array had a strong influence on it as it varied from 0.38 nAM -1 for design A1 up to 13.59 nAM -1 for design A7. Good linearity between the stripping peak currents and the concentration was achieved for the designs studied. The influence of the geometry of the array (number and radius of the microdiscs and inter-electrode spacing) on the sensitivity was investigated. The sensitivity was normalised to the surface area of the microdiscs in the array for comparison purposes. The normalised sensitivity as a function of the number of microdiscs in the array is shown in Figure 3A. It can be expected that the normalised sensitivity should be constant in the case of microdiscs demonstrating independent diffusion behaviour. Nevertheless from Figure 3A, it clearly appears that the normalised sensitivity varies with the number of microdiscs in the array. Such results suggest that microdiscs do not behave independently from one another and overlap of the diffusion zones occurs. Deviation from the constant value is observed at the two arrays with the larger number of microdiscs. This can be explained by the fact that in an array, the nature of the microdiscs can be divided in two types: peripheral and central microdiscs, as illustrated in inset of Figure 3A for an array of 16 microdiscs. Central microdiscs have 6 neighbours and are more likely to suffer from overlap of the diffusion zones and hence their contribution to the total current reduces drastically. The proportion of central microdiscs in the array increases with the number of discs in the array. For design A1 (N = 4), there are no central microdiscs, whereas 56% of discs in design A3 (N = 64) and 76% of discs in design A4 (N = 256) are central microdiscs. This overlap between the diffusion zones is observed for the Cu UPD-SV experiments although CV experiments shown in Figure 1A demonstrated independent microdiscs. This was due to the difference between the timescale of the cyclic voltammetry of ferricyanide and the UPD-SV experiments for Cu 2+ detection. Indeed, the distance between neighbouring microdiscs in an array needed to be 20r to ensure hemispherical diffusion (according to the empirical rule) was valid for short timescales such as cyclic voltammetric experiments. However, in the case of UPD-SV at the end of the preconcentration step of 90s, the diffusion layer corresponded to 357 m thickness as follows from equation 2 [START_REF] Bard | Eletrochemical Methods: Fundamentals and Applications[END_REF]:

Dt = δ 2 (2)
In this equation,  is diffusion layer thickness, D is the diffusion coefficient of copper ions (D = 7.1 × 10 -6 cm 2 s -1 ) [START_REF] Marcinkowsky | [END_REF] and t is the preconcentration time. This is in agreement with previous studies by Menshykau et al. on the concept of diffusional independence [23]. Sensitivity normalised to the surface area increases when the microdiscs decreases as is shown in Figure 3B. The sensitivity values range from 16.9 µA µM -1 cm -2 (design A7, r = 20 µm) up to 40.8 µA µM -1 cm -2 (design A5, r = 5 µm). This behaviour of the sensitivity as a function of the radius is expected and was also reported elsewhere [18]. Furthermore, when the inter-electrode spacing is increased from 20 times (design A3, d = 200 µm) the radius to 40 times (design A8, d = 400 µm), the sensitivity rises from 25.5 to 39.1 µA µM -1 cm -2 . These results confirm that overlap of the diffusion zones occur during the deposition step of the UPD-SV experiments. Lee et al. have described diffusion at microdiscs arrays using two dimensionless parameters which are d / r and  / r [35]. The plot of log (d / r) vs log ( / r) can be divided in three domains where diffusion is either spherical, linear or mixed (inset of Figure 3B). These three domains are based on two equations as described by Lee et al. [35].

The limit between the hemispherical and the mixed diffusion domains is described by equation ( 3) and the limit between the mixed and the linear diffusion domains is described by equation ( 4).

3 1 2       - = r d r



Eq. ( 3)

      - = 1 2 3 2 2 2 r d r    Eq. (4)
Based on the geometrical parameters of the designs tested and the preconcentration time used for the experiments reported in this article, mixed diffusion processes are obtained and correlates the results observed. In order to achieve fully hemispherical diffusion at a microdisc array, it is necessary to either shorten  by reducing the deposition time or by increasing the inter-electrode spacing, d, or by a modification of both. Limits of detection were calculated based on the y-intercept and slope values of the calibration curves constructed plus three times the standard deviation of the y-intercept values [START_REF] Caulcutt | Statistics for Analytical Chemists[END_REF]. They ranged from 0.11 M to 0.39 M. There was no particular trend between the limits of detection achieved and the geometrical parameters of the electrode (number of microdiscs in the array, microdisc radius, inter-microdisc distance). This may have been due to the strong presence of chloride ions in seawater, which upon adsorption on the platinum surface were capable of interfering with the copper detection [START_REF] Markovic | [END_REF] as the chloride anions competed with Cu atoms underpotentially deposited on the surface. The competition between chloride ions and Cu was stronger than between sulfate ions and Cu. Therefore, the high concentration of chloride in seawater hindered the UPD of low concentration of Cu 2+ . Nevertheless, these limits of detection were within the concentration range of Cu 2+ (0.036 -0.940 µM) which can be found in polluted seawater [28] and the reference material, where the concentration of the copper was (2.96 ± 0.02) M. The reference material was analysed by standard addition method. UPD-SV scans on the sample were performed at design A6 microelectrochemical cell. Two standard additions of 3 M of Cu 2+ were added to the sample. Experiments were done in quadruplets. The standard addition linear regression was y = 1.42x + 3.44 (r 2 = 0.970) and the concentration extracted with this equation was (2.43 ± 0.50) M which coincided, within the accuracy of the analysis, with the known copper concentration in the sample provided. The relatively large difference between the certified Cu 2+ concentration and the measured one could be due to the presence of dissolved organic matter. The reference material was used as received. As no sample preparation was used, the presence of dissolved organic matter might foul the electrode surface and hence limits the sensitivity of the µdisc surface. Previous studies have shown that Cu 2+ UPD-SV can be inhibited by the presence of dissolved organic matter such as surfactants and humic acid [38][39][40]. This could be avoided by the use of a permselective gel membrane [41] or by the disorganised monolayer approach [38]. The influence of parameters such as the temperature, the pH and the salinity of the artificial seawater on the sensitivity for Cu 2+ UPD-SV for different preconcentration times (PT) of 0, 45 and 90 s was also investigated (Figure 4). The environmental conditions were selected on values recorded in the Gijón port waters [28] to allow the study of behaviour of the microelectrochemical sensors in various conditions that may be encountered in the field. Sea water temperatures can vary between 283 and 303 K during the year. pH values have been measured between 6.5 and 8.5. Salinity is defined as the salt concentration in seawater. It is measured in practical salinity units (PSU). Salinity of seawater is measured by its conductivity. The average salinity of ocean water is 35.5 PSU, varying from less than 15 PSU at river mouths to more than 40 PSU in the Dead Sea [START_REF] Talley | Encyclopedia of Global Environmental Change[END_REF]. Calibration curves for Cu 2+ at microdisc array of design A6 was built for temperatures ranging from 283 to 303 K (pH was kept constant at 6.5, salinity was 30 PSU), for pH values between 6.5 and 8.5 (T=298 K, salinity = 30 PSU)) and for salinity values between 20 and 40 PSU (pH 6.5 and T = 298 K). based Figure 4A shows that the sensitivity increases linearly with the T range under investigation as it was observed by Jerkiewicz et al. for the Cu 2+ UPD studies in acidic solutions at Pt(111) electrodes [START_REF] Jerkiewicz | [END_REF]. For pH values between 6.5 and 8.5, the maximum sensitivity was obtained for pH 7.5 and the lower sensitivity was obtained for pH 8.5 (Figure 4B), due to the increase of hydroxide ions in the artificial seawater solution. At diluted Cu 2+ concentrations (< 10 -5 M) and at pH between 6.3 and 8.5, free Cu 2+ concentration decreases and CuOH + and Cu(OH)2 forms can be found [START_REF] Baes | Hydrolysis of Cations[END_REF][START_REF] Paulson | [END_REF], which could explain the decrease in sensitivity at pH 8 and 8.5. Salinity has significant influence only at the low salinity level (less than 25 PSU). At low salinity values, the concentration of the chloride in the artificial seawater is significantly lower and there is less chloride ions adsorbed on the surface of the electrode. Cu 2+ ions do not need to overcome the presence of chloride ions adsorbed on the platinum to be underpotentially deposited [46]. Beyond 25 PSU, there is no significant differences between the sensitivities measured. It should also be noted that the sensitivity increases with the preconcentration times as it is expected. These results show the importance of environmental parameters (T and pH of the sea water essentially) on the Cu 2+ detection response.

Conductivity measurements

EIS experiments were run at the conductivity sensors of designs I1-4, where real, ReZ, and imaginary, ImZ, impedance data was recorded over the frequency range 0.1 Hz to 1 MHz. A range of different conductivity standard solutions were used for to investigate the performance of the different sensor designs. ReZ was used for the conductivity measurements. The correlation between ReZ and the conductivity, Sest, is detailed in the Supplementary Data. Figure 5 shows the conductivity values obtained experimentally using design I4 of the interdigitated electrode at 1 MHz, Sest, and using the conductometer readings versus the conductivity value of the standard solutions, Sstd. Both of the sensors operated similarly at the conductivity standards less than 20.00 mS cm -1 with regression equations y=0.9937x + 0.0626 for design I4 and y = 0.9119x -0.3197 for the conductometer. Nevertheless, as opposed to the interdigitated sensor the standard conductometer readings were significantly less than the actual conductivity value in the KCl conductivity standard 50.00 mS cm -1 . Thus, the linearity of the conductometer over the full range of the conductivity standards deteriorated compared with the interdigitated sensor (r 2 =0.9788 against r 2 = 0.9998 for the interdigitated sensor design I4).

Conclusions

Two different types of on-chip electrochemical sensors (three-electrode electrochemical cell and interdigitated electrodes) were studied with a view to using them for in-situ environmental monitoring. Cyclic voltammetry of a model redox probe at the eight different designs of microdiscs arrays have shown that microdiscs in the array behave as independent electrodes. This electrochemical behaviour is in agreement with the theory described in the literature. The different designs were then compared in terms of sensitivity and limits of detection for the detection of Cu 2+ in artificial seawater by UPD-SV. These experiments have shown that the microdiscs do not behave independently during the UPD-SV experiments and that mixed diffusion profiles are achieved. This overlapping diffusion zones could be avoided by either reducing the preconcentration time of the Cu 2+ UPD-SV, or by increasing the d / r ratio. Nevertheless, it is not always possible to reduce the preconcentration time in reason of the low levels of Cu 2+ concentration that need to be detected. Furthermore, d / r cannot be increased indefinitely as it will result in a large surface area for the array and an increase of a parasitic capacitance of the corresponding non-active array area. Sensitivity of the sensors were measured for a variety of environmental conditions (283 K < T <303 K; 6.5 < pH < 8.5 and 20 PSU < salinity < 40 PSU). T and pH had the strongest influence on the sensor response suggesting that for accurate in-situ measurements, the corresponding environmental sensors should be introduced into the sensing system. Their reading should be used to compensate the sensor measurement against T, pH and salinity. Four designs of interdigitated electrodes were tested for the measurement of conductivity of seawater. Best results were obtained for measurements at high frequencies (f > 10 kHz). The dynamic range and limit of detections achieved for Cu 2+ , dissolved oxygen and conductivity were within the range of concentration observed in real samples of port seawater.

Figure captions

Figure 1 :

 1 Figure 1: Cyclic voltammetry of 1 mM ferricyanide in artificial seawater using microelectrochemical cells of (A) designs A1-4 (voltammograms from top to bottom). Inset: ilim as a function of N; (B) designs A3, A5-7. Inset: limiting current density as a function of r; (C) designs A3 and A8. The scan rate was 10 mV s -1 .

Figure 2 :

 2 Figure 2: (A) Potential waveform for the Cu 2+ UPD-SV experiments at the different microelectrochemical cell designs. (B) UPD-SV of Cu 2+ (0 < [Cu 2+ ] < 5 µM). Inset: Calibration curve of the Cu 2+ stripping current as a function of the Cu 2+ concentration in artificial seawater.

Figure 3 :

 3 Figure 3: (A) Sensitivity normalised to the surface area as a function of microdiscs in the array (). The straight line represents the expected behaviour if microdiscs in the array were independent from one another. Inset: Schematic representation of the array (design A2) where (•) are the peripheral microdiscs and (○) are the central microdiscs. (B) Sensitivity normalised to the surface area as a function of microdisc radius. Inset: Plot of log d/r vs. lod /r for electrodes of designs A1-A4 and A8. The solid line is described by equation (3) and the dotted line by equation (4)[35].

Figure 4 :

 4 Figure 4: Sensitivity achieved using design A6 as a function of (A) temperature (pH 6.5, 30 PSU), (B) pH (T = 298 K, 30 PSU) and (C) salinity (T = 298 K, pH 6.5) of the artificial seawater. Cu 2+ concentration range was 0.5 -3.0 µM for different preconcentration times: (•)PT=0 s, (□) PT=45 s and (◼) PT=90 s).

Figure 5 :

 5 Figure 5: Experimental conductivity measured using (○) interdigitated electrodes of design I4 at 1MHz and (□) a commercial probe and conductometer at 2.4 kHz as a function of a function of the conductivity of KCl standard solutions. If not visible, the error bars are smaller than the symbols.

Table 1 :

 1 Geometrical parameters of the different microchemical cells designed (A1-8 & I1-4).

Table 2 :

 2 Analytical performances for the Cu 2+ UPD-SV at the different microelectrochemical cells designed (A1-8).

Figure 5 Table 1 r

 51 Figure 5

Table 2

 2

Acknowledgments

The authors thank the European Commission for supporting this work (Project FP7-ICT-231646 "SHOAL: Search and monitoring of harmful contaminants, other pollutants and leaks in vessels in port using a swarm of robotic fishes"). The authors are grateful to Prof. Dmitri Papkovsky and Dr Grzegorz Jasionek from the University College Cork Department of Biochemistry for access to the precision gas mixer. The authors are also grateful to the Port

Authority of Gijón for the provision of environmental data.