Meghyn Bienvenu

Camille Bourgaux

Query-Driven Repairing of Inconsistent DL-Lite Knowledge Bases

We consider the problem of query-driven repairing of inconsistent DL-Lite knowledge bases: query answers are computed under inconsistency-tolerant semantics, and the user provides feedback about which answers are erroneous or missing. The aim is to find a set of ABox modifications (deletions and additions), called a repair plan, that addresses as many of the defects as possible. After formalizing this problem and introducing different notions of optimality, we investigate the computational complexity of reasoning about optimal repair plans and propose interactive algorithms for computing such plans. For deletion-only repair plans, we also present a prototype implementation of the core components of the algorithm.

Introduction

Ontology-mediated query answering (OMQA) is a promising recent approach to data access in which conceptual knowledge provided by an ontology is exploited when querying incomplete data (see [START_REF] Bienvenu | Meghyn Bienvenu and Magdalena Ortiz. Ontology-mediated query answering with data-tractable description logics[END_REF] for a survey). As efficiency is a primary concern, significant research efforts have been devoted to identifying ontology languages with favorable computational properties. The DL-Lite family of description logics (DLs) [START_REF] Calvanese | [END_REF], which underlies the OWL 2 QL profile [START_REF] Motik | [END_REF], has garnered significant interest as it allows OMQA to be reduced, via query rewriting, to standard database query evaluation.

Beyond efficiency, it is important for OMQA systems to be robust to inconsistencies stemming from errors in the data. Inspired by work on consistent query answering in databases [Bertossi, 2011], several inconsistency-tolerant semantics have been developed for OMQA, with the aim of providing meaningful answers in the presence of inconsistencies. Of particular relevance to the present paper are the brave semantics [START_REF] Bienvenu | Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access[END_REF], which returns all query answers that are supported by some internally consistent set of facts, and the more conservative IAR semantics [START_REF] Lembo | [END_REF] that requires that facts in the support not belong to any minimal inconsistent subset. Both semantics have appealing computational properties: for most DL-Lite dialects, including the dialect DL-Lite R considered in this paper, conjunctive query answering is tractable in data complexity and can be implemented using query rewriting techniques [START_REF] Lembo | [END_REF][START_REF] Bienvenu | Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access[END_REF].

While inconsistency-tolerant semantics are essential for returning useful results when consistency cannot be achieved, they by no means replace the need for tools for improving data quality. That is why in this paper we propose a complementary approach that exploits user feedback about query results to identify and correct errors. We consider the following scenario: a user interacts with an OMQA system, posing conjunctive queries and receiving the results, which are sorted into the possible answers (i.e., those holding under the weaker brave semantics) and the (almost) sure answers (holding under IAR semantics). When reviewing the results, the user can indicate that some of the retrieved answer tuples are erroneous, whereas other tuples should definitely be considered answers. Ideally, the unwanted tuples should not be returned as possible (brave) answers, and all of the desired tuples should be found among the sure (IAR) answers. The aim is thus to construct a set of atomic changes (deletions and additions of facts), called a repair plan, that achieves as many of these objectives as possible, subject to the constraint that the changes must be validated by the user.

There are several reasons to use queries to guide the repairing process. First, we note that it is typically impossible (for lack of time or information) to clean the entire dataset, and therefore reasonable to focus the effort on the parts of the data that are most relevant to users' needs. In the database arena, this observation has inspired work on integrating entity resolution into the querying process [Altwaijry et al., 2013]. Second, expert users may have a good idea of which answers are expected for queries concerning their area of expertise, and thus queries provide a natural way of identifying flaws. Indeed, Kontokostas et al. (2014) recently proposed to use queries to search for errors and help evaluate linked data quality. Finally, even non-expert users may notice anomalies when examining query results, and it would be a shame not to capitalize on this information, and in this way, help distribute the costly and time-consuming task of improving data quality, as argued in [START_REF] Bergman | QOCO: A query oriented data cleaning system with oracles[END_REF].

The contributions of this paper are as follows. In Section 3, we formalize query-driven repairing problems and illustrate the main challenges, in particular, the fact that there may not exist any repair plan that resolves all identified errors. This leads us to introduce in Section 4 different notions of optimal repair plan. Adopting DL-Lite R as the ontology language, we study the complexity of reasoning about the different kinds of optimal repair plan and provide interactive algorithms for constructing such plans. In Section 5, we focus on the important special case of deletion-only repair plans, for which all of the optimality notions coincide. We take advantage of the more restricted search space to improve the general approach, and we analyze the complexity of the decision problems used in our algorithm. Finally, in Section 6, we present preliminary experiments about our implementation of the core components of the algorithm for the deletion-only case. We conclude with a discussion of related and future work.

Omitted proofs and additional information about the experiments can be found in [Bienvenu et al., 2016b].

Preliminaries

Following the presentation of [Bienvenu et al., 2016a], we recall the basics of DLs and inconsistency-tolerant semantics.

Syntax A DL knowledge base (KB) consists of an ABox and a TBox, both constructed from a set N C of concept names (unary predicates), a set N R of role names (binary predicates), and a set N I of individuals (constants). The ABox (dataset) is a finite set of concept assertions A(a) and role assertions R(a, b), where

A ∈ N C , R ∈ N R ,
inclusion G H if G I ⊆ H I ; it sat- isfies A(a) (resp. R(a, b)) if a I ∈ A I (resp. (a I , b I ) ∈ R I ). We call I a model of K = (T , A) if I satisfies all axioms in T and assertions in A. A KB is consistent if it has a model, and an ABox A is T -consistent if the KB (T , A) is consistent.
Example 1. As a running example, we consider a simple KB K ex = (T ex , A ex ) about the university domain that contains concepts for postdoctoral researchers (Postdoc), professors (Pr) of two levels of seniority (APr, FPr), PhD holders (PhD), and graduate courses (GradC), as well as roles to link advisors to their students (Adv), instructors to their courses (Teach) and student to the courses they attend (TakeC). The ABox A ex provides information about an individual a:

T ex ={Postdoc PhD, Pr PhD, Postdoc ¬Pr, FPr Pr, APr Pr, APr ¬FPr, ∃Adv Pr} A ex ={Postdoc(a), APr(a), Adv(a, b), Teach(a, c)} Observe that A ex is T ex -inconsistent.

Queries We focus on conjunctive queries (CQs) which take the form q( x) = ∃ y ψ( x, y), where ψ is a conjunction of atoms of the forms A(t) or R(t, t ), with t, t individuals or variables from x ∪ y. A CQ is called Boolean (BCQ) if it has no free variables (i.e. x = ∅). Given a CQ q with free variables x = (x 1 , . . . , x k ) and a tuple of individuals a = (a 1 , . . . , a k ), we use q( a) to denote the BCQ resulting from replacing each x i by a i . A tuple a is a certain answer to q over K, written K |= q( a), iff q( a) holds in every model of K. When we use the generic term query, we mean a CQ.

Causes and Conflicts A cause for a BCQ q w.r.t. KB K = (T , A) is a minimal T -consistent subset C ⊆ A such that (T , C) |= q. We use causes(q, K) to refer to the set of causes for q. A conflict for K is a minimal T -inconsistent subset of A, and confl(K) denotes the set of conflicts for K.

When K is a DL-Lite R KB, every conflict for K has at most two assertions. We can thus define the set of conflicts of a set of assertions C ⊆ A as follows:

confl(C, K) = {β | ∃α ∈ C, {α, β} ∈ confl(K)}. Inconsistency-Tolerant Semantics A repair of K = (T , A) is an inclusion-maximal subset of A that is T -consistent.
We consider two previously studied inconsistency-tolerant semantics based upon repairs. Under IAR semantics, a tuple a is an answer to q over K, written K |= IAR q( a), just in the case that (T , B ∩ ) |= q( a), where B ∩ is the intersection of all repairs of K (equivalently, B ∩ contains some cause for q( a)). If there exists some repair B such that (T , B) |= q( a) (equivalently: causes(q( a), K) = ∅), then a is an answer to q under brave semantics, written K |= brave q( a). Example 2. There are two repairs of the example KB K ex : {Postdoc(a), Teach(a, c)} {APr(a), Adv(a, b), Teach(a, c)} Evaluating the queries q 1 = ∃yTeach(x, y) and q 2 = Prof(x) on K ex yields the following results: K ex |= IAR q 1 (a), K ex |= IAR q 2 (a), but K ex |= brave q 2 (a). Indeed, intersecting the repairs yields {Teach(a, c)}, which contains a cause for q 1 (a) but no cause for q 2 (a). On the other hand, the second repair contains two causes for q 2 (a) (namely {APr(a)} and {Adv(a, b)}), which shows K ex |= brave q 2 (a).

In DL-Lite R , CQ answering under IAR or brave semantics is in P w.r.t. data complexity (i.e. in the size of the ABox) [START_REF] Lembo | [END_REF][START_REF] Bienvenu | Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access[END_REF].

Query-Driven Repairing

A user poses questions to a possibly inconsistent KB and receives the sets of possible answers (i.e. those holding under brave semantics) and almost sure answers (those holding under IAR semantics). When examining the results, he detects some unwanted answers, which should not have been retrieved, and identifies wanted answers, which should be present. To fix the detected problems and improve the quality of the data, the objective is to modify the ABox in such a way that the unwanted answers do not hold under the (more liberal) brave semantics and the wanted answers hold under the more cautious IAR semantics.

A first way of repairing the data is to delete assertions from the ABox that lead to undesirable consequences, either because they contribute to the derivation of an unwanted answer or because they conflict with causes of some wanted answer. Example 3. Reconsider the KB K = (T ex , A ex ), and suppose a is an unwanted answer for Pr(x) but a wanted answer for PhD(x).

Deleting the assertions APr(a) and Adv(a, b) achieve the objectives since (T ex , {Postdoc(a), Teach(a, c)})

|= brave Pr(a) and (T ex , {Postdoc(a), Teach(a, c)}) |= IAR PhD(a).

The next example shows that, due to data incompleteness, it can also be necessary to add new assertions. Example 4. Consider K = (T ex , {APr(a)}) with the same wanted and unwanted answers as in Ex. 3. The assertion APr(a) has to be removed to satisfy the unwanted answer, but then there remains no cause for the wanted answer. This is due to the fact that the only cause of PhD(a) in K contains an erroneous assertion: there is no 'good' reason in the initial ABox for PhD(a) to hold. A solution is for the user to add a cause he knows for PhD(a), such as Postdoc(a).

We now provide a formal definition of the query-driven repairing problem investigated in this paper. Definition 1. A query-driven repairing problem (QRP) consists of a KB K = (T , A) to repair and two sets W, U of BCQs that K should entail (W) or not entail (U). A repair plan (for

A) is a pair R = (E -, E + ) such that E -⊆ A and E + ∩ A = ∅; if E + = ∅, we say that R is deletion-only.
The sets U and W correspond to the unwanted and wanted answers in our scenario: q( a) ∈ U (resp. W) means that a is an unwanted (resp. wanted) answer for q. Slightly abusing terminology, we will use the term unwanted (resp. wanted) answers to refer to the BCQs in U (resp. W). We say that a repair plan (E -, E + ) addresses all defects of a QRP (K, W, U) if the KB K = (T , (A\E -) ∪ E + ) is such that K |= IAR q for every q ∈ W, and K |= brave q for every q ∈ U.

The next example shows that by considering several answers at the same time, we can exploit the interaction between the different answers to reduce the search space. Example 5. Consider the KB K = (T ex , A) with ABox A = {Pr(a), APr(b), FPr(b), Teach(a, c), Teach(b, c), GrC(c), TakeC(s, c)}. It is easy to see that K is inconsistent, and its two repairs are obtained by removing either APr(b) or FPr(b). Evaluating the queries q 1 (x) = PhD(x) and q 2 (x) = ∃yzPr(x) ∧ Teach(x, y) ∧ GrC(y) ∧ TakeC(z, y) over this KB yields:

K |= brave q 1 (b) K |= brave q 2 (b) K |= IAR q 2 (a)
. We consider the QRP (K, W, U) with wanted answers W = {q 1 (b), q 2 (a)} and unwanted answers U = {q 2 (b)}.

Two deletion-only repair plans address all defects: {APr(b), Teach(b, c)} and {FPr(b), Teach(b, c)}. Indeed, we must delete exactly one of APr(b) and FPr(b) for q 1 (b) to be entailed under IAR semantics, and we cannot remove GrC(c) or TakeC(s, c) without losing the wanted answer q 2 (a). Thus, the only way to get rid of q 2 (b) is to delete Teach(b, c).

If we consider only U (i.e. W = ∅), there are additional possibilities such as {GrC(c)} and {TakeC(s, c)}, and there is no evidence that Teach(b, c) has to be deleted.

If we want to avoid introducing new errors, a fully automated repairing process is impossible: we need the user to validate every assertion that is removed or added in order to remove (resp. add) only assertions that are false (resp. true). Example 6. Reconsider the problem from Ex. 5, and suppose that the user knows that TakeC(s, c) is false and every other assertion in A is true. An automatic repairing will remove the true assertion Teach(b, c). The problem is due to the absence of a 'good' cause for the wanted answer q 2 (a) in A.

Since we will be studying an interactive repairing process, in which users must validate changes, we will also need to formalize the user's knowledge. For the purposes of this paper, we assume that the user's knowledge is consistent with the considered TBox T , and so can be captured as a set M user of models of T . Instead of using M user directly, it will be more convenient to work with the function user induced from M user that assigns truth values to BCQs in the obvious way: user(q) = true if q is true in every I ∈ M user , user(q) = false if q is false in every I ∈ M user , and user(q) = unknown otherwise. We will assume throughout the paper the following truthfulness condition: user(q) = false for every q ∈ U, and user(q) = true for every q ∈ W.

We now formalize the requirement that repair plans only contain changes that are sanctioned by the user. Definition 2. A repair plan (E -, E + ) is validatable w.r.t. user1 just in the case that user(α) = false for every α ∈ E - and user(α) = true for every α ∈ E + .

Unfortunately, it may be the case that there is no validatable repair plan addressing all defects. This may happen, for instance, if the user knows some answer is wrong but cannot pinpoint which assertion is at fault, as we illustrate next. Example 7. Consider the QRP given by: K =(T ex , {FPr(a), Teach(a, c), GrC(c)}) U ={∃xPr(a) ∧ Teach(a, x) ∧ GrC(x)}, W = {Pr(a)} Suppose that user(FPr(a)) = false, user(Teach(a, c)) = unknown, user(GrC(c)) = unknown, user(APr(a)) = true. It is not possible to satisfy the wanted and unwanted answers at the same time, since adding the true assertion APr(a) creates a cause for the unwanted answer that does not contains any assertion α with user(α) = false: the user does not know which of Teach(a, c) and GrC(c) is erroneous.

As validatable repair plans addressing all defects are not guaranteed to exist, our aim will be to find repair plans that are optimal in the sense that they address as many of the defects as possible, subject to the constraint that the changes must be validated by the user.

Optimal Repair Plans

To compare repair plans, we consider the answers from U and W that are satisfied by the resulting KBs, where:

-q ∈ U is satisfied by K if K |= brave q; -q ∈ W is satisfied by K if there exists C ∈ causes(q, K)
such that confl(C, K) = ∅ and there is no α ∈ C with user(α) = false.

Remark 1. Observe that for q ∈ W to be satisfied by K, we require not only that K |= IAR q, but also that there exists a cause for q that does not contain any assertions known to be false, i.e. K |= IAR q should hold 'for a good reason'. We impose this additional requirement to avoid counterintuitive situations, e.g. preferring repair plans that remove fewer false assertions in order to retain a conflict-free (but erroneous) cause for a wanted answer.

We say that a repair plan R = (E -, E + ) satisfies q ∈ U ∪W if the KB K R = (T , (A\E -) ∪ E + ) satisfies q, and we use S(R) (resp. S U (R), S W (R)) to denote the sets of answers (resp. unwanted answers, wanted answers) satisfied by R.

Two repair plans R and R can be compared w.r.t. the sets of unwanted and wanted answers that they satisfy: for A ∈ {U, W}, we define the preorder A by setting R A R iff S A (R) ⊆ S A (R ), and obtain the corresponding strict order (≺ A ) and equivalence relations (∼ A ) in the usual way. If the two criteria are equally important, we can combine them using the Pareto principle: R {U ,W} R iff R U R and R W R . Alternatively, we can use the lexicographic method to give priority either to the wanted answers ( W,U ) or unwanted answers ( U ,W ):

R A,B R iff R ≺ A R or R ∼ A R and R B R , where {A, B} = {U, W}.
For each of the preceding preference relations , we can define the corresponding notions of -optimal repair plan. Definition 3. A repair plan (E -, E + ) is globally (resp. locally) -optimal w.r.t. user iff it is validatable w.r.t. user and there is no other validatable repair plan

(E -, E + ) such that (E -, E + ) ≺ (E -, E + ) (resp. such that E -⊆ E -, E + ⊆ E + and (E -, E + ) ≺ (E -, E + )).
Globally -optimal repair plans are those that are maximal with respect to the preference relation , whereas locallyoptimal repair plans are those that cannot be improved in the ordering by adding further assertions to E -or E + .

Remark 2. If a repair plan is validatable and addresses all defects of a QRP, then it is globally U -optimal. If it additionally satisfies every q ∈ W (ensuring that there is a 'good' cause for every q ∈ W), then it is globally -optimal for every ∈ { W , {U ,W} , U ,W , W,U }.

The following example illustrates the difference between local and global optimality. It can be verified that the repair plan R 1 = ({Teach(a, e), GrC(e)}, {Teach(a, c)}) satisfies the first answer in W and the (only) answer in U. It is locally {U ,W}optimal since the only way to satisfy the second wanted answer would be to add GrC(c), which would create a cause for the unwanted answer, which could not be repaired by removing additional assertions as the user does not know which of Adv(a, b) and takeC(b, c) is false. However, R 1 is not globally {U ,W} -optimal because R 2 = ({Teach(a, e), GrC(e)}, {Teach(a, d), GrC(c)}) satisfies all answers in W ∪ U.

In order to gain a better understanding of the computational properties of the different ways of ranking repair plans, we study the complexity of deciding if a given repair plan is optimal w.r.t. the different criteria. Since validatability of a repair plan depends on user, in this section, we measure the complexity w.r.t. |A|, |U|, |W|, as well as the size of the set T rue rel user ={α ∈ T rue user | there exists q ∈ W such that α ∈ C for some C ∈ causes(q, A ∪ T rue user )}

where T rue user = {α | user(α) = true}. We make the reasonable assumption that T rue user (hence T rue rel user ) is finite. Theorem 1. Deciding if a repair plan is globally -optimal is coNP-complete for ∈ { {U ,W} , U ,W , W,U }, and in P for ∈ { W , U }. Deciding if a repair plan is locallyoptimal is in P for ∈ { U , W , {U ,W} , U ,W , W,U }.

For the coNP upper bounds, we note that to show that R is not -optimal (for ∈ { {U ,W} , U ,W , W,U }), we can guess another repair plan R and verify in P that both plans are validatable and that R satisfies more answers than R. The lower bounds are by reduction from (variants of) UNSAT.

To establish the tractability results from Theorem 1, we provide characterizations of optimal plans in terms of the notion of satisfiability of answers, defined next. Definition 4. An answer q ∈ U ∪ W is satisfiable if there exists a validatable repair plan that satisfies q. We say that q is satisfiable w.r.t. a validatable repair plan R = (E -, E + ) if there exists a validatable repair plan R = (E -, E + ) such that E -⊆ E -, E + ⊆ E + , q ∈ S(R ), and R {U ,W} R . Proposition 1. Deciding if an answer is satisfied, satisfiable, or satisfiable w.r.t. a repair plan is in P.

Combining Prop. 1 with the following characterizations yields polynomial-time procedures for optimality testing. Proposition 2. A validatable repair plan R is: globally U -(resp. W -) optimal iff it satisfies every satisfiable q ∈ U (resp. q ∈ W). locally U ,W -optimal iff it is locally {U ,W} -optimal iff it satisfies every q ∈ U ∪ W that is satisfiable w.r.t. R. locally W,U -optimal iff it satisfies every satisfiable q ∈ W and every q ∈ U that is satisfiable w.r.t. R.

Our complexity analysis reveals that the notions of global optimality based upon the preference relations {U ,W} , U ,W , and W,U have undesirable computational properties: even when provided with all relevant user knowledge, it is intractable to decide whether a given plan is optimal. Moreover, while plans globally U -(resp. W -) optimal can be interactively constructed in a monotonic fashion by removing further false assertions (resp. and adding further true assertions), building a globally optimal plan for a preference relation that involves both U and W may require backtracking over answers already satisfied (cf. the situation in Example 8).

ALGORITHM OptRP U Input: QRP (K=(T ,A), U, W) Output: repair plan A. E -← ∅, E + ← ∅ B. Display the assertions of q∈U ∪W causes(q, K) and q∈W,C∈causes(q,K) confl(C, K) 1. Ask user to mark all false (F ) and true (T ) assertions 2.

E -← E -∪ F ∪ confl(T, K) C. While W = W\S W (E -, E + ) = ∅: q ← first(W )
1. Ask the user for true assertions T q (not already provided) to complete (or create) a cause for q 2. If T q = ∅ (nothing to add): W ← W\{q}, go to C.

3. E + ← E + ∪ T q , E -← E -∪ confl(T q , (T , A ∪ T q )) 4. Show assertions of every cause C of q such that T q ∩ C = ∅ and its conflicts: user indicates false, true assertions F , T : E -← E -∪ F ∪ confl(T , K) 5. Show assertions of causes of every q ∈ U in A\E -∪ E + : user gives false assertions F :

E -← E -∪ F 6. If there is q ∈ U such that (T , A\E -∪E + ) |= brave q and (T , A\E -) |= brave q : E + ← E + \T q (revert E + ) D. Return (E -, E + )
Figure 1: Algorithm for constructing a globally U and locally {U ,W} -optimal repair plan For the preceding reasons, we target validatable repair plans that are both globally optimal for U or W (depending which is preferred) and locally optimal for {U ,W} . In Fig. 1, we give an interactive algorithm OptRP U for building such a repair plan when U is preferred; if W is preferred, we use the algorithm OptRP W obtained by removing Step C.6 from OptRP U . The algorithms terminate provided the user knows only a finite number of assertions that may be inserted. In this case, the algorithms output optimal repair plans: Theorem 2. The output of OptRP U (resp. OptRP W ) is globally U (resp. W ) and locally {U ,W} -optimal.

Proof. We give the proof for OptRP U . First observe that at every point during the execution of the algorithm, the current repair plan is validatable, since only true assertions are added to E + and false assertions are added to E -(they are either marked as false by the user or are in conflict with assertions that have been marked as true).

Step B adds to E -all assertions known to be false that belong to a cause of some q ∈ U ∪ W or a conflict of some cause of q ∈ W. Thus, at the end of this step, E -satisfies every satisfiable answer in U, that is, every answer in U every cause of which contains at least one false assertion. Hence (E -, E + ) is globally U -optimal at the end of step B. Moreover, every false assertion that occurs in a cause or conflict of a cause of a wanted answer has been removed, so if q ∈ W is not satisfied at this point, then it has no cause without any conflict in A\{α | user(α) = false}.

The purpose of Step C is to add new true assertions to create causes for the wanted answers not satisfied after Step B, while preserving S U (E -, E + ). For every q ∈ W, while q is not satisfied, the user is asked to input true assertions to complete a cause for q in Step C.1. If he is unable to do so, at Step C.2, we remove q from W (since it cannot be satisfied w.r.t. user); otherwise, we update E -and E + using T q (C.3). Note that since T q contains only true assertions, we can remove its conflicts without affecting already satisfied wanted answers; this step is necessary because T q may conflict with assertions of A that are not involved in the causes and conflicts presented at Step B. In Step C.4, we remove false assertions appearing in a new cause for q or its conflicts (such assertions may not have been examined in Step B). Step C.5 removes false assertions of new causes of unwanted answers, and Step C.6 undoes the addition of T q if it affects S U (E -, E + ). Thus, at the end of Step C, for every wanted answer, either it is satisfied, or the user is unable to supply a cause that does not deteriorate S U (E -, E + ). It follows that (E -, E + ) is locally {U ,W} -optimal.

Optimal Deletion-Only Repair Plans

In this section, we restrict our attention to constructing optimal deletion-only repair plans. In this simpler setting, all of the previously introduced notions of optimality collapse into the one characterized in the following proposition. Proposition 3. A validatable deletion-only plan is optimal iff it satisfies every q ∈ U such that every C ∈ causes(q, K) has α ∈ C with user(α) = false, and every q ∈ W for which there exists C ∈ causes(q, K) such that user(α) = false for every α ∈ C and user(β) = false for every β ∈ confl(C, K).

Constructing such repair plans can be done with one of the preceding algorithms, omitting Step C that adds facts. However, it is possible to further assist the user by taking advantage of the fact that subsets of the ABox whose removal addresses all defects of the QRP can be automatically identified, and then interactively transformed into optimal repair plans. We call such subsets potential solutions.

An assertion is said to be relevant if it appears in a cause of some q ∈ U ∪ W or in the conflicts of a cause of some q ∈ W. If an assertion α appears in every potential solution, either user(α) = false, or there is no validatable potential solution. We call such assertions necessarily false. If α appears in no potential solution, it is necessary to keep it in A to retrieve some wanted answers under IAR semantics, so either user(α) = false, or it is not possible to satisfy all wanted answers. We call such assertions necessarily nonfalse.

When a potential solution does not exist, a minimal correction subset of wanted answers (MCSW) is an inclusionminimal subset W ⊆ W such that removing W from W yields a QRP with a potential solution. Because of the truthfulness condition, we know that the absence of a potential solution means that some wanted answers are supported only by causes containing erroneous assertions (otherwise the wanted and unwanted answers would be contradictory, which would violate the truthfulness condition). Moreover, since removing all such answers from W yields the existence of a potential solution, there exists a MCSW which contains only such answers, which we call an erroneous MCSW. This is why MC-SWs can help identify the wanted answers that cannot be satisfied by a deletion-only repair plan.

Theorem 3. For complexity w.r.t. |A|, |U| and |W|, deciding if a potential solution exists is NP-complete, deciding if an assertion is necessarily (non)false is coNP-complete, and

deciding if W ⊆ W is a MCSW is BH 2 -complete.
The lower bounds are proven by reduction from propositional (un)satisfiability and related problems. For the upper bounds, we construct in polynomial time a propositional CNF ϕ = ϕ U ∧ ϕ W with:

ϕ U = q∈U C∈causes(q,K) α∈C x α ϕ W = q∈W C∈causes(q,K) w C ∧ q∈W C∈causes(q,K) α∈C ¬w C ∨ ¬x α ∧ q∈W C∈causes(q,K) β∈confl(C,K) ¬w C ∨ x β
which has the following properties:

there exists a potential solution iff ϕ is satisfiable (satisfying assignments correspond to potential solutions); -α is necessarily false iff ϕ ∧ ¬x α is unsatisfiable; -α is necessarily nonfalse iff ϕ ∧ x α is unsatisfiable; there exist disjoint subsets S, H of the clauses in ϕ such that the MCSWs correspond to the minimal correction subsets (MCSs) of S w.r.t. H, i.e. the subsets M ⊆ S such that (i) (S\M )∪H is satisfiable, and (ii) (S\M )∪ H is unsatisfiable for every M M .

We present in Fig. 2 an algorithm OptDRP for computing optimal deletion-only repair plans. Within the algorithm, we denote by R(K, U, W, A ) (resp. N f (K, U, W, A ), N ¬f (K, U, W, A )) the set of assertions from A ⊆ A that are relevant (resp. necessarily false, nonfalse) for the QRP (K, U, W) when deletions are allowed only in A (the set A will be used to store assertions whose truth value is not yet determined). The general idea is that the algorithm incrementally builds a set of assertions that are false according to the user. It aids the user by suggesting assertions to remove, or wanted answers that might not be satisfiable there is no potential solution, while taking into account the knowledge the user has already provided. If there exists a potential solution, the algorithm computes the necessarily (non)false assertions and asks the user either to validate them or to input false and nonfalse assertions to justify why they cannot be validated, and then to input further true or false assertions if the current set of false assertions does not address all defects. When a potential solution is found, the user has to verify that each wanted answer has a cause that does not contain any false assertion. If there does not exist a potential solution at some point, either initially or after some user inputs, the algorithm looks for an erroneous MCSW by computing all MC-SWs, then showing for each of them the assertions involved in the causes of each query of the MCSW. If there is a query which has a cause without any false assertion, the MCSW under examination is not erroneous, nor are the other MCSWs that contain that query. Otherwise, the MCSW is erroneous ALGORITHM OptDRP Input: QRP (K=(T ,A), U, W) Output: repair plan (Note: below K is a macro for (T , A\E-), using the current E-.)

A. K 0 ← K, A ← A, E -← ∅ B. If a potential solution for (K, U, W) exists in A : 1. R ← R(K, U, W, A ), N f ← N f (K, U, W, A ), N ¬f ← N ¬f (K, U, W, A ) 2.
If the user validates user(α) = false for every α ∈ N f and user(α) = false for every α ∈ N ¬f : a.

E -← E -∪ N f , A ← A \(N f ∪ N ¬f ) b.
If E -is a potential solution for (K 0 , U, W):

i. For each q ∈ W: the user gives all false assertions

F ⊆ C∈causes(q,K),confl(C,K)=∅ C, E -← E -∪ F ii. If E -is still a potential solution: output E - iii. Else: A ← A \E -, go to B c. Else: user selects some F, T ⊆ R\(N f ∪ N ¬f ) i. If F = T = ∅ (nothing left to input): return E - ii. Else: E -← E -∪F ∪confl(T, K), A ← A \(E -∪ T ), go to B 3. Else: user gives F ⊆ {α ∈ N ¬f | user(α) = false} and N F ⊆ {α ∈ N f | user(α) = false} with F ∪ N F = ∅, E -← E -∪ F , A ← A \(E -∪ N F ) C.
Search for a MCSW containing only answers that are supported only by erroneous causes: 1. M ← M CSW s(K, U, W, A ) ordered by size 2. While erroneous MCSW not found and M = ∅:

a. M ← first(M) b. For every q ∈ M : i. the user selects F, T ⊆ C∈causes(q,K) C

ii. Proof idea. Termination follows from the fact that every time we return to Step B, something has been added to E -or deleted from W, and nothing is ever removed from E -or added to W. Since we only add false assertions to E -, the output plan is validatable. If the algorithm ends at Step B.2.b.ii, then E -satisfies every answer characterized in Prop. 3. Indeed, since E -is a potential solution, it satisfies every unwanted answer. Moreover, the answers removed from W at Step C.2.c do not fulfill the conditions of Prop. 3 since all their causes contain some false assertion, and for every remaining q ∈ W, we ensure that there is a conflict-free cause of q that contains no false assertions. If the algorithm ends at

E -← E -∪ F ∪ confl(T, K), A ← A \(E -∪ T ) iii.
Step B.2.c.i, the user was asked to indicate false or true assertions at Step B.2.c and was not able to input anything, so the user has deleted all false assertions he knows among the relevant assertions, and thus it is not possible to improve the current repair plan further. A similar argument applies if the algorithm ends at Step C.3.

To avoid overwhelming the user with relevant assertions at Step B.2.c, it is desirable to reduce the number of assertions presented at a time. This leads us to propose two improvements to the basic algorithm. First, we can divide QRPs into independent subproblems. Two answers are considered dependent if their causes (and conflicts in the case of wanted answers) share some assertion. Independent sets of answers do not interact, so they can be handled separately. Second, at

Step B.2.c, the assertions can be presented in small batches. Borrowing ideas from work on reducing user effort in interactive revision, we can use a notion of impact to determine the order of presentation of assertions. Indeed, deleting or keeping an assertion may force us to delete or keep other assertions to get a potential solution. Relevant assertions can be sorted using two scores that express the impact of being declared false or true. For the impact of an assertion α being false, we use the number of assertions that becomes necessarily (non)false if α is deleted. The impact of α being true also takes into account the fact that the conflicts of α can be marked as false: we consider the number of assertions that are in conflict with α or become necessarily (non)false when we disallow α's removal. We can rank assertions by the minimum of the two scores, using their sum to break ties.

Preliminary Experiments

We report on experiments made on core components of the above OptDRP algorithm. We focused on measuring the time to decide whether a potential solution exists (Step B), to compute necessarily (non)false and relevant assertions (Step B.1), to rank the relevant assertions w.r.t. their impact (Step B.2.c), and to find the MCSWs (Step C).

The components were developed in Java using the CQAPri system (www.lri.fr/ ˜bourgaux/CQAPri) to compute query answers under IAR and brave semantics, with their causes, and the KB's conflicts. We used SAT4J (www. sat4j.org) to solve the (UN)SAT reductions in Section 5.

We borrowed from the CQAPri benchmark [Bienvenu et al., 2016a] available at the URL above its: (i) TBox which is the DL-Lite R version of the Lehigh University Benchmark [START_REF] Lutz | [END_REF] augmented with constraints allowing for conflicts, (ii) c5 and c29 ABoxes with ∼10 million assertions and, respectively, a ratio of assertions involved in conflicts of 5%, that we found realistic, and of 29%, and (iii) queries q 1 , q 2 , q 3 , q 4 , shown below. We slightly modified the original queries by changing some constants or variables in order to obtain dependent answers (whose causes and conflicts of causes share some assertions). We built 13 QRPs per ABox, by adding more and more answers of these queries to U or W; the size of U ∪ W varies from 8 to 121. q 1 = ∃y Person(x) ∧ takesCourse(x, y) ∧ Person(G131)∧ GraduateCourse(y) ∧ takesCourse(G131, y) q 2 = ∃x Employee(x) ∧ memberOf(x, D2)∧ degreeFrom(x, y) q 3 = ∃y teacherOf(x, y) ∧ degreeFrom(x, U 532) q 4 = ∃z Employee(x) ∧ degreeFrom(x, U 532)∧ memberOf(x, z) ∧ Employee(y)∧ degreeFrom(y, U 532) ∧ memberOf(y, z) In all of our experiments, deciding if a potential solution exists, as well as computing the set of relevant assertions, takes just a few milliseconds. The difficulty of computing the necessarily (non)false assertions correlates with the number of relevant assertions induced by the QRP. For the c5 QRPs involving 85 to 745 relevant assertions, this computation took between 30ms to 544ms, while it took 24ms to 1333ms for the c29 QRPs involving 143 to 1404 relevant assertions. While these times seem reasonable in practice, ranking the remaining relevant assertions based on their impact is time consuming as it requires a number of calls to the SAT solver quadratic in the number of assertions: it took less than 10s up to ∼150 assertions, less than 5mn up to ∼480 assertions, and up to 25mn for 825 assertions. For all of the QRPs we built, computing the MCSWs takes a few milliseconds; somewhat surprisingly, we always found at most one MCSW.

Discussion

The problem of modifying DL KBs to ensure (non)entailments of assertions and/or axioms has been investigated in many works, see e.g. [De Giacomo et al., 2009;[START_REF] Calvanese | Evolution of DL-Lite knowledge bases[END_REF][START_REF] Gutierrez | [END_REF].

Our framework is inspired by that of [START_REF] Jiménez-Ruiz | [END_REF], in which a user specifies two sets of axioms that should be entailed or not by a KB. Repair plans are introduced as pairs of sets of axioms to remove and add to obtain an ontology satisfying these requirements. Deletion-only repair plans are studied in [START_REF] Jiménez-Ruiz | [END_REF] where heuristics based on the confidence and the size of the plan are used to help the user to choose a plan among all minimal plans.

When axiom (in)validation can be partially automatized, ranking axioms by their potential impact reduces the effort of manual revision [START_REF] Meilicke | Christian Meilicke, Heiner Stuckenschmidt, and Andrei Tamilin. Supporting manual mapping revision using logical reasoning[END_REF][START_REF] Nikitina | Nadeschda Nikitina, Sebastian Rudolph, and[END_REF]. In our setting, we believe that validating sets of necessarily (non)false assertions requires less effort than hunting for false assertions among all relevant assertions, leading us to propose a similar notion of impact to rank assertions to be examined.

Compared to prior work, distinguishing features of our framework are the specification of changes at the level of CQ answers, the use of inconsistency-tolerant semantics, and the introduction of optimality measures to handle situations in which not all objectives can be achieved.

In future work, two aspects of our approach deserve further attention. First, when insertions are needed, it would be helpful to provide users with suggestions of assertions to add. The framework of query abduction [START_REF] Calvanese | Reasoning about explanations for negative query answers in DL-Lite[END_REF], which was recently extended to inconsistent KBs [Du et al., 2015], could provide a useful starting point. Second, our experiments revealed the difficulty of ranking relevant assertions, so we plan to develop optimized algorithms for computing impact and explore alternative definitions of impact.

  a, b ∈ N I . The TBox (ontology) is a finite set of axioms whose form depends on the particular DL. In DL-Lite R , TBox axioms are either concept inclusions B C or role inclusions P S built according to the following syntax (where A ∈ N C and R ∈ N R ): B := A | ∃P, C := B | ¬B, P := R | R -, S := P | ¬P Semantics An interpretation has the form I = (∆ I , • I ), where ∆ I is a non-empty set and • I maps each a ∈ N I to a I ∈ ∆ I , each A ∈ N C to A I ⊆ ∆ I , and each R ∈ N R to R I ⊆ ∆ I × ∆ I . The function • I is extended to general concepts and roles in the standard way, e.g. (R -) I = {(d, e) | (e, d) ∈ R I } and (∃P ) I = {d | ∃e : (d, e) ∈ P I }. An interpretation I satisfies an

Example 8 .

 8 Consider the QRP ((T ex , A), W, U) where A ={Teach(a, e), Adv(a, b), TakeC(b, c), TakeC(b, e),GrC(e)} W ={∃xTeach(a, x), ∃xtakeC(b, x) ∧ GrC(x)} U ={∃xyTeach(a, x)∧Adv(a, y)∧TakeC(y, x)∧GrC(x)} Suppose that user(Teach(a, e)) = user(GrC(e)) = false, user(α) = unknown for the other α ∈ A, and the user knows that Teach(a, c), Teach(a, d) and GrC(c) are true.

  Figure 2: Algorithm for optimal deletion-only repair plans

In what follows, we often omit 'w.r.t. user' and leave it implicit.

Acknowledgements

This work was supported by contract ANR-12-JS02-007-01.


Julien Jacques
email: julien.jacques@univ-lyon2.fr

Cyril Ruckebusch
email: cyril.ruckebusch@univ-lille1.fr

MODEL-BASED CO-CLUSTERING FOR HYPERSPECTRAL IMAGES

Keywords: co-clustering, latent block model, hyperspectral images

A model-based co-clustering algorithm for hyperspectral images is presented. This algorithm, which relies on the probabilistic latent block model for continuous data, aims to cluster both the pixels and the spectral features of the images. This approach has been applied to a benchmark Raman imaging dataset and revealed relevant information for spatial-spectral exploratory investigation of the data.

Introduction

Co-clustering methods aim to design simultaneously a clustering of the rows and of the columns of a large array of data. The combination of row-clusters and column-clusters leads to the construction of a small number of homogeneous data blocks (see Figure 1), which are useful to summarize and interpret large data sets. In the era of big data and knowledge harvesting, co-clustering techniques have recently spotted a lot of interest from statisticians leading to the development of many algorithms and models. An extensive list of co-clustering methods is provided in reference, [START_REF] Madeira | Biclustering algorithms for biological data analysis: A survey[END_REF] distinguishing deterministic [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF] and model-based techniques. [START_REF] Govaert | Co-Clustering[END_REF] Model-based approaches are attractive since they provide parsimonious data modeling in a probabilistic framework. This allows choosing the number of relevant co-clusters and opens possibilities for interpretation. In particular, the Latent Block Model (LBM [START_REF] Govaert | Block clustering with bernoulli mixture models: Comparison of different approaches[END_REF] ) is a powerful approach to find relevant block clustering and useful representations of the data.

In chemometrics, co-clustering can be viewed as an exploratory approach which allows to simultaneously group observations and variables of a data set, or, in other terms, to simultaneously group rows and columns of a two-way data matrix. [START_REF] Bro | Coclustering-a useful tool for chemometrics[END_REF] This results in homogeneous blocks, which do not only share information about variable similarity as in classical one way clustering with e.g. k-means [START_REF] Hartigan | Algorithm as 1326 : A k-means clustering algorithm[END_REF] but also information about sample similarity. These blocks (co-clusters) can be used to summarize the data, to facilitate their interpretation or for feature selection. Being applied to hyperspectral images (HSI), co-clustering generates blocks that share simultaneously spatial (pixel) and spectral (variable) information to improve both the reliability and interpretability of the analysis. A statistical approach is sounded in HSI considering the huge number of pixels (individuals).

The potential of co-clustering in HSI analysis has only been pointed out very recently. [START_REF] Liu | Spectral-spatial co-clustering of hyperspectral image data based on bipartite graph[END_REF][START_REF] Izquierdo-Verdiguier | Introducing co-clustering for hyperspectral image analysis[END_REF] In this work we propose using LBM to apply co-clustering to the investigation of Raman HSIs. LBM is a probabilistic model which assumes that the data from the same block share the same probability distribution. Consequently, the whole dataset is assumed to be issued from a mixture model in which each component corresponds to the probability distribution of a block. These blocks are the most informative ones with the best spectral-spatial information.

The paper is organized as follows: Section 2 introduces the LBM model, its inference and model selection criteria for choosing the number of co-clusters. In Section 3, the proposed approach is applied to a HSI benchmark dataset consisting of Raman imaging of an oil-in-water emulsion. The results obtained are discussed in Section 4.

Latent block model for continuous data co-clustering 2.1 Latent block model

The latent block model assumes local independence i.e., the n × d random variables x are assumed to be independent once the row partition v = (v ik ) 1≤i≤n,1≤k≤K and the column partition w = (w h ) 1≤h≤d,1≤ ≤L are fixed (note that a standard binary partition is used for v and w):

p(x; θ) = v∈V w∈W p(v; θ)p(w; θ)p(x|v, w; θ) (1)
with (below the straightforward range for i, h, k and are omitted):

• V the set of all possible partitions of rows into K groups, W the set of partitions of the columns into L groups,

• p(v; θ) = ik α v ik k and p(w; θ) = h β w h where α k and β are the row and column mixing proportions, belonging to [0, 1] and summing to 1,

• p(x|v, w; θ) = ihk p(x ih ; µ k , σ 2 k ) v ik w h where p(•; µ k , σ 2 k ) is the Gaussian density with mean µ k and variance σ 2 k , • θ = (µ k , σ 2 k , α k , β
) is the whole mixture parameter.

This local independence assumption (independence of the n × d random variables x once the row and column partitions are known), which is usual in mixture model for categorical data, [START_REF] Celeux | Clustering criteria for discrete data and latent class models[END_REF] allows to write the probability of the observed data matrix p(x|v, w; θ) as a product of the probabilities of all the cells x ih of the matrix. Without this assumption, the joint distribution of x would be intractable. Finally, since the row and column partitions are unknown in practice, we have to marginalize this product of probabilities over all the possible row partitions v ∈ V and column partitions w ∈ W .

Model inference

The aim is to estimate θ by maximizing the observed log-likelihood

(θ; x) = v,w ln p(x; θ). (2)
Due to the presence of missing data (v, w), this observed log-likelihood cannot be maximized analytically. The Expectation Maximization algorithm (EM [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] ) is generally used to maximise loglikelihood in presence of missing data. This algorithm consists in maximizing the complete data log-likelihood:

log p(x, v, w; θ) = ik v ik log α k + j w j log β + ijk v ik w j log p(x ij ; µ k , σ 2 k ) (3)
by an iterative procedure which alternates an E step, in which the expectation of (3) conditionally on the observed data and the current value of θ is computed, and an M step in which this conditional expectation is maximized according to θ. But in case of co-clustering, the E step is computationally untractable, and some derivative of this algorithm should be used. [START_REF] Govaert | Co-Clustering[END_REF] In this work we opt for the Block EM algorithm. [START_REF] Bhatia | blockcluster: Coclustering package for binary, contingency, continuous and categorical data-sets[END_REF] Choice of the number of clusters In order to select the numbers of clusters, K in rows and L in columns, we propose to use the ICL-BIC criterion [START_REF] Lomet | Sélection de modèle pour la classification croisée de données continues[END_REF] for LBM with continuous data:

ICL-BIC(K, L) = log p(x, v, ŵ; θ) - K -1 2 log n - L -1 2 log d - 2KL 2 log(nd)
where v, ŵ and θ are the respective estimations of the row partition, column partition and model parameters obtained at the end of the estimation algorithm and log p(x, v, ŵ; θ) is the complete data log-likelihood given by:

log p(x, v, ŵ; θ) = ik vik log αk + j ŵj log β + ijk vik ŵj log p(x ij ; μk , σ2 k ).
This criterion is expected to select the true numbers of clusters under given theoretical conditions. In practice, it can be used as a starting point for data exploration, the practician may change these numbers according to its interpretation.

Exploring all the possible combinations for (K, L) with 1 ≤ K ≤ K max and 1 ≤ L ≤ L max requires to estimate and to compute the ICL-BIC criterion K max × L max times. It can rapidly become computationally expensive. We propose here a greedy search in order to minimise the number of explored values for (K, L):

1. start with (K, L) = (1, 1)
2. compute ICL-BIC(K + 1, L) and ICL-BIC(K, L + 1).

• if both are lower than ICL-BIC(K, L), then stop the search and return ( K, L) = (K, L).

• else, if ICL-BIC(K + 1, L) > ICL-BIC(K, L + 1), then K ← K + 1, else L ← L + 1.

return in 2.

Software The Block EM algorithm for estimating the Gaussian LBM model is implemented in the blockcluster 11 package for the R software.

Application

The Raman HSI data provided in Figure 2 corresponds to an oil-in-water emulsion sample analyzed in the fingerprint region of the spectral range. This data has been already used in previous works to benchmark data analysis methods. Full details about the dataset and the experimental setup can be found in earlier work. [START_REF] Andrew | Raman imaging of emulsion systems[END_REF] The dataset is available at: https://mcrals.word press.com/download/example-data-sets/examples-of-analytical-methods (last accessed September 13th 2016). The image in Figure 2 (left) is formed by 60 × 60 pixels and the spectra consists of 125 points in the range from 900 to 1400 cm -1 . The interest in analyzing this data is that the composition of the spectroscopic mixture is known. [START_REF] Andrew | Raman imaging of emulsion systems[END_REF] In the sampled area, according to previous work, [START_REF] Andrew | Raman imaging of emulsion systems[END_REF][START_REF] Hugelier | Constraining shape smoothness in multivariate curve resolution-alternating least squares[END_REF][START_REF] Juan | Use of local rank-based spatial information for resolution of spectroscopic images[END_REF] four different components can be extracted using multivariate curve resolution approaches corresponding to a structural phase, two droplet phases, and an aqueous phase. However, it should be noted that the structural and aqueous phases are mixtures of multiple chemical components. Thus, the chemical complexity of these emulsion should not be underestimated (10 to 12 different chemical compounds with relative concentration from 0.1% to 80%). [START_REF] Andrew | Raman imaging of emulsion systems[END_REF] The co-clustering results are provided in Figures 3 and4. In Figure 3 (top), the results obtained for pixel clustering (left) with K = 9 pixel-clusters and L = 6 spectral-clusters, as well as the mean spectra for each of the 9 pixel-clusters, are shown. These numbers of pixel-and spectral-clusters were obtained using the ICL-BIC criterion described in Section 2.2. Considering the chemical complexity of the investigated sample, these results do not seem out of range. However, as already mentioned, this automatic procedure can be refined. Indeed, inspection of the mean spectra obtained for the different pixel-clusters reveals that some of them have a pair-wise correlation coefficient greater than 0.99. Adding to this the a priori information available about the investigated data, it was thus decided to merge these pixel clusters which leads to the 4 pixel-clusters representation shown in Figure 3 (bottom). The corresponding mean spectra for each cluster are also given.

One can observe that the different structures expected in this sample are revealed. The two droplet oil phases are clearly seen (blue and red pixels). These clusters were already identified individually before cluster averaging and they consist of different oil mixtures. After cluster averaging, the structural (purple) and aqueous phases (orange) which consist of around 80% water (plus two chemicals) are more clearly depicted.

In Figure 4 the results obtained for variable-clusters are shown. In the way chosen to represent the results, one plot is provided for each cluster and each plot contains the mean spectral value for each of the 4 pixel-clusters for the features that were retained for the construction of the block. The spectral-clusters which are the most relevant for the distinction of the spatial information are clusters 2 and 3 for which a clear distinction of the different mean cluster spectra is observed.

These spectral-clusters highlight spectral band where essentially difference intensities is observed for the main spectral features peaking at variable number 25, 50 and 105 (spectral cluster 2) and on the side of these bands (spectral cluster 3). On the other hand, the spatial-clusters 4 and 6 can be interpreted as the ones for which specific information regarding the droplet oil phase (coded in red) is obtained. Information around spectral variables 60 and 90 are of particular relevance, the latter corresponding to a shoulder observed on the original spectra.

Discussion

Whereas clustering groups objects according to the similarity of their features (variables), coclustering groups both objects and variables simultaneously, it looks for which samples are related to which variables at the same time. In contrast to other approaches that have been proposed in the chemometric literature based on constrained outer product decomposition with sparsity on the latent factor of the bilinear model [START_REF] Papalexakis | From k-means to higher-way co-clustering: Multilinear decomposition with sparse latent factors[END_REF] that are not necessary well-suited for spectral data (collinearities of the variables and the lack of sparsity), the proposed LBM provided reliable and useful (interpretable) results for Raman HSI data. More in general, co-clustering approaches provides results on the line of recent advances in spectral-spatial analysis of HSI images. [START_REF] Fauvel | Advances in spectralspatial classification of hyperspectral images[END_REF] Comparison of the results obtained for co-clustering with K = 4 pixel clusters (see Figure

Figure 1 :

 1 Figure 1: Example of data matrix x of dimension n × d (left image) and of the co-clustering results for a partition of K = 3 row-clusters and L = 3 column-clusters leading to the representation of the data by 9 blocks (right image).

Figure 2 :

 2 Figure 2: Raman HSI data of an oil-in-water emulsion. Mean image (60 × 60 µm) and overlaid spectra in the range 900 to 1400 cm -1 .

3) can be made with the ones applying k-means. For this purpose, Figure 5 provides the results obtained for k-means pixel clustering considering 4 clusters. Overall it can be noticed that the images obtained are quite similar. However a closer inspection reveals that the two droplet oil phases are quite different. The structure of the smaller droplet is less clearly identified on the image obtained Figure 5. This is confirmed by the inspection of the spectra provided for the kmeans clusters. They do not allow to clearly point the spectral differences in the region around the spectral variable 90, which role in the discrimination of this compound has been clearly identified from the interpretation of the spectral-cluster provide Figure 4. The aim of this work was to demonstrate the applicability of the LBM co-clustering approach for HSI analysis and to illustrate the potential of the co-clustering for data investigation and spatialspectral interpretation. It should be clear that co-clustering results cannot directly compare to the ones obtained applying multivariate resolution and unmixing methods which provide factorial data decomposition into pure component distribution maps and corresponding spectral features. However, in the example shown co-clustering has revealed interesting information that can be extremely useful for preliminary spatial-spectral investigation and that could potentially be used for further analysis.

Summing up, we believe that co-clustering can provide an efficient alternative for the investiga- tion of HSI data. The LBM framework could in future works be modified to allow the consideration of pixel neighborhood (sets of pixels) and account for spatial or morphological information.


Dimitar Minovski

Eric Rondeau

Jean-Philippe Georges

Monitoring the

Keywords: Energy efficient modelling, Green technologies and IT, Network Management, Software Defined Networking

come

INTRODUCTION

The energy-efficient network infrastructures have recently become a hot topic in the business world, as the concept of Green IT strives to reduce the overall operational costs, but in the same time also to eliminate the inefficiencies from the enterprises' IT systems. The network infrastructures are already massively deployed and even projected to have exponential growth (Cisco, 2011) due to the evolution of the Internet, user demands and trending topics such as Internet of Things (Ovidiu and Friess, 2013). Thus, as a shared resource they have to be constantly available, which exacerbates the sustainability issues. Researchers have already proposed different network-wide energy management schemes targeting various areas such as datacenters [START_REF] Koutitas | Challenges for energy efficiency in local and regional data centers[END_REF], mobile networks [START_REF] Wang | A survey of green mobile networks: Opportunities and challenges[END_REF] and WANs [START_REF] Gupta | Greening of the Internet[END_REF]. However, it is quite challenging to tackle the energy efficiency issues within the households and from small to large enterprises. One obstacle in making enterprise networks more energy efficient is the range of devices from multiple vendors deployed on the network. Also, it is difficult to operate with enterprise networks because of their unpredictable growth, frequently changed topology and architecture, regarding the energy consumption.

Current research and developed Network Management Systems (NMS) are not fully automated when executing energy-efficiency policies. The introduction of SDN paradigm brought new opportunities for managing networks through abstraction of lower-level functionality. This means that a centralized SDN controller with only one transaction is able to reconfigure a group of devices. However, the monitoring process of existing NMS to report for changes in the state of the devices is based on point-to-point (p2p) communication with every device on the network. This creates a great deal of traffic and puts additional burden on the network, which raises a sustainable issue in complex networks. Due to improvements in the field of Green IT and smart meters, it is feasible to build a NMS that recons only on power data fetched from the power distribution unit. A pattern for augmenting the values extracted from the power consumption of the network could provide useful information about different network states, for instance detecting changes in the topology. The idea is to use Fault Detection and Isolation (FDI) approach to monitor the network state based on the energy usage. Figure 1 shows that we need two information, a model representing the expected behavior of the devices and the real-time measurements to analyze deviation between the two processes. A deviation corresponds to fault detection in the network, which is in a form of misconfiguration or improper use of the equipment. This means that monitoring the energy consumption could be used not only for Green IT purposes, for raising awareness and reducing the electricity costs, but as well for a classical ICT monitoring system. Also, as the concept of Smart Grid is making use of digital networks to improve the transportation of energy, the work presented in this paper could be explained as the reverse process -how the use of energy could improve the data transport.

Figure 1. The general approach of the paper

The remaining part of this paper is organized as follows: Section 2 presents the related work, while the Section 3 presents the objective of the paper. The system is described in Section 4, which includes the architecture for network management, the design of the experiments and the implementation of the developed application. In Section 5 the obtained results are presented and discussed, while the Section 6 concludes the paper.

RELATED WORK

In recent years a new approach for network management emerged under the name of Software Defined Networking (SDN) that allows the network operators to manage the network services through abstraction of high-level functionality. A study by [START_REF] Kim | Improving network management with software defined networking[END_REF] proposes an event-driven network control framework based on SDN paradigm and OpenFlow protocol to manage a complex campus network. The focus is on enabling frequent changes to network conditions and states, providing support for network configuration in high-level language, and providing better visibility and troubleshooting. Having a global knowledge of the network state, the developed control framework introduces a centralized approach for network configuration, opposed to distributed management. Meaning that the network operators will not have to configure all the devices individually, but instead let the software make network-wide traffic forwarding decision from a logically single location. Moreover, the network operators provide high-level network policies which are translated by the controller in a centralized manner into a set of forwarding rules, which are used to enforce the policy on the underlying network equipment, by using OpenFlow, as depicted on Figure 2. They offer a set of control domains which can be used by the network operators to define conditions by assigning a suitable packet forwarding actions which corresponds to each condition. Even though the proposed solution reduces the workload of network configuration and management due to the SDN paradigm, the study mainly focuses on the algorithm for translating the policies into a set of reconfigurations of the devices. The system is based on event sources that dynamically collects the current state of the devices, which are inputs to the controller for forming the policies. The event sources monitor the network state and report the changes to the controller, such as bandwidth usage of every end-host device. The monitoring is based on the SNMP and OpenFlow for pulling data with p2p communication which is difficult to manage especially during an expansion of the network, when adding new devices to the network, or during changes to the physical network topology which alters IP address modifications.

Figure 2. Classical SDN architecture

The strategy presented in [START_REF] Aubrun | Network calculus based fault diagnosis decisionmaking for Networked Control Systems[END_REF] for studying the effects of unknown induced delays in network architecture suggests the use of concepts such as Fault Detection and Isolation (FDI) and Fault Tolerance Control (FTC). The study defines a threshold for the expected delay on the basis of the network characteristic and network calculus theory. A faulty situation is then generated and compared to the defined threshold in order to successfully detect which elements are causing the delays and deals with them in a controlled manner. Similarly, (Riekstin et al., 2016) proposes the use of power profiles for each device on the network to determine their expected energy usage under different circumstances. However, the power profiles are considered in special case when the real-time energy measurements are not accessible. They suit as a backup figure to proceed with the FDI's calculations to determine a faulty situation and produce energy efficient policies for the network.

The study by [START_REF] Drouant | Designing green network architectures using the ten commandments for a mature ecosystem[END_REF] proposes models that gives a global overview of the impact that the network and the ICT equipment is having on the environment, developing the following equation:

E = Em + Eu + Ed E m + ∫ 𝑃𝑃𝑃𝑃(𝑡𝑡)𝑑𝑑𝑡𝑡 𝑒𝑒𝑒𝑒𝑒𝑒 𝑜𝑜𝑜𝑜 𝑙𝑙𝑙𝑙𝑜𝑜𝑒𝑒𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑒𝑒 𝑡𝑡=0 + Ed (1)
Where Em is the energy required for manufacturing and transportation of the equipment, Eu is a factor related to the energy consumed during the usage of the equipment, and the energy required to dismantle the equipment is Ed. For the second part of (1), Pu is related to the power consumption by the network architecture during its use phase.

Two strategic approaches exist for modeling the energy consumed during the usage phase of the devices.

The first involves a high-level modelling [START_REF] Foll | TIC et Energetique: techniques d'estimation de consommation sur la hauteur, la structure et l'evolution de l'impact des TIC en France[END_REF] of the whole architecture and the second approach is more precise, meaning that it provides power models for each of the devices part of the network. A highlevel model has less interactions with the devices and therefore fails to give accurate estimations how much energy a network architecture consumes at a particular point of time. On the other hand, the use of energy consumption models developed for a particular device would require constant p2p interactions and cause certain amount of additional traffic in the network. However, by giving a more precise figure on the expected behavior of the devices the system would be more responsive to minor changes, faults and anomalies, which is the purpose of the experiments part of this paper. Therefore, the power models for Switch [START_REF] Reviriego | An Energy Consumption Model for Energy Efficient Ethernet Switches Riekstin[END_REF])(Hossain et al., 2015), Router [START_REF] Ahn | Measurement and modeling the power consumption of router interface[END_REF], PC [START_REF] Agarwal | Somniloquy: Augmenting Network Interfaces to Reduce PC Energy Usage[END_REF] and Access Point [START_REF] Demir | An energy consumption model for 802.11ac access points[END_REF] are added to the Power Model Registry, as shown on the Figure 5, explained in the next sections.

OBJECTIVE

The goal is to develop sustainable software application suitable for network monitoring systems, which operates only with the retrieved energy consumption data from the ICT devices part of the network infrastructure. The developed application communicates with the Power Grid illustrated on the Figure 3, and by following the FDI approach shown on the Figure 1 is able to detect different states that are occurring on the ICT devices. The network of the power grid includes the Raritan Power Distribution Unit (PDU), which provides the real-time measures for the energy consumption through SNMP periodic pulling. With this, the PDU grid forms the power monitoring process. The detection of the states is achieved by the developed application, which analyzes the retrieved raw power data to distinguish possible faulty situations and anomalies in the usage phase of the ICT devices. The output of the application, or the detected new state suits as an input parameter to the SDN controller. This means that the developed application is envisioned to replace the classical event sources, part of Figure 2, which are using point-to-point communication to report for changes in the state of the devices. To achieve this, the developed software requires two information to be considered: (i) power data from real-time measurement procedure and (ii) values for the expected power consumption of each device extracted from the power models.

(i) The process of real-time measurement requires probes and standardized protocols to access the needed metrics which are altogether coupled in a monitoring system. In practice, Raritan Power Distribution Unit (PDU) is the monitored equipment which has a predefined energy Management Information Base (MIB) as a hierarchical structure with properties that is pulled out periodically. The monitoring system itself is then able to collect, analyze and modify the information stored in the MIB through SNMP. It is important to note that the PDU in this case acts as a separate network from the existing network architecture. This means that the monitoring process has a separate channel to the PDU and the packets does not cross the existing network architecture, which releases the burden on the network.

(ii) From the other side, as discussed in the section II, the selected power models represent the expected behavior of the equipment. Therefore, currently there is an open field to combine the real-time measures, which are translated to the real behavior of a device, with the developed models. A deviation between the models and the monitored power data is used to detect anomalies and to anticipate fault according to a trend analysis.

Figure 3. Objective of the developed system

The output of the developed system is a continuous detection of changes in the network infrastructure, for instance detecting new device on the network, changes in the Spanning tree protocol, detection in changing the operating state of a switch port, etc. Finally, the objective is the developed monitoring system based on the power grid as shown on the figure 3, which will be a replacement for the existing monitoring system in [START_REF] Kim | Improving network management with software defined networking[END_REF] which does a p2p communication with every device part of the network.

Building a knowledge base

The developed application that incorporates the monitoring system and the power models has to form thorough foreknowledge in order to successfully anticipate and interpret the readings for the energy consumption. Mostly because the power data is just a raw value and does not contain rich information. As suggested by [START_REF] Kazandjieva | Measuring and analyzing the energy use of enterprise computing systems[END_REF], some types of computing systems within the enterprise can exhibit large variations on the power data even when comparing two instances of the same device model. More precisely, two Dell Optiplex 760 PCs were observed to have over 40% discrepancy in their average power draw. To remedy this, the application has to augment new ways to isolate the problem with the inconsistent energy consumption of the devices, to locate the fault or the anomaly and to classify the problem. One way to deal with this is to predict the fault that may occur during the usage of the equipment. It is important to test the responsiveness of the application by generating different faults and misconfigurations that may occur during a typical workday in an enterprise network. Thus, closely observe the figures for energy consumption and build a knowledge base. A system with such knowledge comprised with smart algorithms is capable of analyzing the deviations and benchmark the faulty situations. From there a pattern could emerge to later detect the problem of aberrant values regarding the energy consumption of the devices during the real-life usage phase of the equipment.

List 1 represents the states which are chosen as most common during a typical enterprise workday, tested on a various heterogeneous combinations of network architectures, prior building the knowledge base. To identify where the faults are applied, a classification based on the objective is depicted on the Figure 4.

The logic behind the monitoring system

The states illustrated on the Figure 6 represent the logic throughout the execution process. Having developed a standalone application able to monitor the energy consumption as a first state allows further analysis process on the retrieved and stored data. The analysis engine as a second state is tightly coupled with the learning model of the system by developed smart algorithms which are able to detect and identify the changes in the power data. Big part of the analysis process plays the inclusion of the power models, discussed in the related work, which are defining the power profiles of the devices and are calculating their expected behavior. The output of the models is then validated with the retrieved real-time measurements for possible deviations. Raritan PDU offers the possibility to monitor its overall consumption as well as the individual power consumption per socket. This means that if a deviation is detected in the comparison process of the overall consumption, the analysis engine will further seek for the device causing the energy disparity. A recent history of energy consumption is retrieved from a database for the detected device and the results are logically passed to the third state, where they are further dismantled towards understanding and interpreting the power data values. The emphasis of the third state, the learning process, is given to the simulation of the faults that are most frequent during the regular usage phase of the ICT equipment. The established knowledge base is used as a baseline on which the learning model is constructed. This means that series of experiments have to be conducted for a range of different network states and faults in the interest of acquiring the desired foreknowledge to benchmark the anticipated states. The benchmarking process is also the key concept for the isolation part as a last state of the logic depicted on the Figure 6.

Ever since the commencement period of the learning process, the system is constantly updating its knowledge base depending on the behavior of the devices, and by following the figures for the energy consumption it is able to discern the aberrant states of the devices. For instance, a possible overloading on the devices, detecting sleep/hibernate states, physical or logical changes in the configuration of the devices, etc. To have seamless operations and accurate output, the learning process also needs to update the static values in the power models based on the detected new state of a particular device. Namely, as seen on the Figure 1, the equations in the power models depend on static parameters from the network planification, which are gathered during one-time measurement. This means that the learning model has to re-compute the input parameters in the power models after a detection of a new network state. For instance, the equation in the power model of a switch has to be updated with new value if a switch port transitioned from offline to online state and vice versa. The outcome of the learning process regarding the benchmarking part concludes the fourth state of the logic behind the experiment, the engine for power management. An accurate benchmarking provides the possibility to identify the changes that occurred on the network infrastructure and suggests a recuperation, or a reconfiguration of the network.

SYSTEM DESCRIPTION

This section provides more technical explanation of the developed application. The architecture of the system has been previously described in [START_REF] Minovski | Using ICT Energy consumption for monitoring ICT usage in an enterprise[END_REF].

Implementation

The application, which includes the power models and the monitoring module is implemented in Java language using the SNMP library and MySql database. The energy monitoring task is developed in a multithreaded fashion to periodically pull the energy values from the Raritan PDU, by importing Java libraries for SNMP to access the functions for requesting the right Raritan's MiB OIDs. There is an ability to optimize the frequency of the probes send to the Raritan PDU throughout a developed GUI, thus the accuracy of the measures is practically defined by the operator. During the test phase of the application, probes were requested every second and the responses are stored locally with the interest to enable further analysis on the data. The response from each probe is a group of values in the following format: I(A) -Electric current significant with 10 -3 amps (A) base; V(V) -Voltage; PF -Power factor. To get the current energy consumption (W) the following equation has to be performed:

W = I(A) x V(V) x PF (2)
Moreover, the probe response does not only contain data for the total energy consumed by the whole PDU, but also it reports the consumption of each socket individually. This means that the application with additional analysis can successfully build its own schemas and detect what kind of device is connected to a certain socket. Giving this ability, the process flow can successfully discover which device specifically is not consuming the energy as it is expected. Algorithm 1 describes the process flow of the application.

Algorithm 1: the process flow input: PM, the power models; PR, the probe response output: Ffault, detected fault, Iisolation, isolating the fault R is the Raritan PDU E denotes the attached equipment KB represents the knowledge base in a form of database

foreach X in PR do Wtotal ← X(I(A)) * X(V) * X(PF) Store(W total) if Wtotal > PMtotal then foreach E in R do Windividual ← E(I(A)) * E(V) * E(PF) Store(W individual) if Windividual > PMindividual then Ffault ← Detection(E, KB, History(Windividual) Iisolation ← Isolation(Ffault) Store(Ffault, Iisolation) return Ffault, Iisolation
The support of power models (PM) in the application creates the premises to set the expected threshold regarding the energy spent by each detected device. The discussed power models are represented with a static parameters gathered by one-time measurement at the initialization phase of the application or when a new device is plugged to the PDU socket.

Having a real-time availability probes enables the application to perform parallel comparison on the retrieved data for individual sockets, and as a whole, with the data provided by the power models. In case of aberrant values, the application tries to locate the device with the unexpected behavior, load the latest stored power data history of the device and perform analysis for fault detection. The FDI concept is based on calculations directed by the predefined fault foreknowledge, achieved by the experiments for generating the faults in order to benchmark the consumption that a particular occurring state is causing. The knowledge base (KB) is also integrated in the algorithm in a form of a database.

The Detection() function is the core of the algorithm due to the fact that it couples the analysis and the learning process, described in the previous section. It begins by locating the device that is observed to have disparity in the energy consumption. Also, a recent history of the spotted device is passed to the function, which includes two separate components. First is the recent energy consumption history of the device and secondly is the recent history of the noted running states and configuration of the device. This process maps the previous running configuration and understands the current states of the devices that might be causing the energy disparity. Moreover, the knowledge base is as well loaded which can interpret the difference in the expected and the real energy measures into a new network state. The function combines the above mentioned parameters and the calculations result with detection of the changed state. For instance, a switch is detected to have powered off a port, changed the link speed, or perhaps reevaluated the STP.

The Isolation() function as a input parameter receives the detected new state and performs further analyses to examine the implications, especially on the energy consumption. The analysis determines the actions that have to be taken upon detection of new state. For instance, if a switch port is detected to transition from online to offline mode, this function re-computes the input parameters of the static power models to make them having accurate calculations of the expected energy consumption of the switch. This means that the examination of the implications result with discovery whether the detected new state is a misconfiguration of the network, a faulty situation or just changes in the network state that have to be noted. As an output, the Isolation() function updates the database of the spotted device recent history and the knowledge base, and reports to the network operator for the changes.

The first version of the GUI is show on the Figure 7. The network operator is able to see live chart of the energy consumption of the whole network, as well as select specific PDU and monitor the consumption. Based on the detected states, the network operator could map the running configuration of the whole network, as well as separately for each PDU. When a specific PDU is selected, the operator could monitor the individual sockets, see the detected device and read the changes in the state. There is a possibility to download a report with a complete history of the changes on the network. The obtained results are discussed in the next section.

RESULTS AND DISCUSSION

This section refers to the List 1, presenting the obtained results during the test phase of the developed application. Each of the experiments were tested on different network architectures, monitored for 10 minutes continuously, as well as under different amount of load generated to flow through the network.

(i) The possibility to automatically detect the working hours of an enterprise allows the application dynamically to report on the equipment that was left in an operational state. For instance, if a wireless access point is observed to consume constant level of energy during non-working hours, the application will indicate that the device is powered, but does not transmit any data, meaning that it should transition into a sleep mode. The cost of powering the hardware components of each device dominates the overall power profile and therefore the opportunity for energy savings are the highest. The difference in the energy consumption between the operational and the sleeping mode is illustrated on the Figure 8. Typically, there is a burst of energy consumption when a device goes to operational state, either from sleep/hibernate or offline mode. Those values are also used to benchmark the current state of the device. (ii) Managing the active ports on a switch is one important and exquisite objective because it is the only way of providing network accessibility. Therefore, to have an overview on the status of the ports at one point of the time by observing the switch's values for the energy consumption is a delicate task. Mainly because of the introduction of EEE as a set of enhancements able to dynamically put a single link temporarily to sleep when not in use. The difference in the power consumption after a transition from active to inactive switch port is observed to be from 0.3 to 0.4 W, as illustrated on the Figure 9. This result allows the developed application to benchmark the state and have detailed matrix of the port statuses of each switch. Having this feature allows issuing reports for possible unnecessarily active ports, but also is part of the analysis for a possible misconfiguration of the network.

(iii) The utilization of the Ethernet links is, on average, extremely low [START_REF] Gunaratne | Reducing the Energy Consumption of Ethernet with Adaptive Link Rate (ALR)[END_REF]. This suggests that there is ample opportunity for energy savings by operating Ethernet links at a low data rate for most of the time with no perceivable performance impact to the user. To keep track of the each switch's port assigned speed, by following the energy consumption, means an opportunity for adjustments according to the needs. But it also helps the application to correlate the assigned link speed with the congestion, or the load on the switch, which is as well affecting the overall power consumption. During the observations, there is no notable change in the consumption when comparing 10Mb/s to 100Mb/s speed link, but the difference when making a transition from 1Gb/s to 100Mb/s is from 0.2 to 0.4 W per port. Thus, the developed application by benchmarking this value is forming a schema of each port link speed that is assigned. The outcome is a suggestion when to reduce the speed of a link when a low utilization is perceived.

(iv) Energy-Efficient Ethernet is not yet a feature supported by many network devices currently on the market, however it is important to observe its impact on the energy consumption. During an idle period of a switch with no traffic flowing through the ports, EEE will put all of the active ports in the Low Power Idle (LPI) state, and therefore achieve the same result as the second (ii) experiment of 0.3 to 0.4 W savings per port. Hence, the developed application has to be aware of the possibilities of EEE to dynamically, for a temporary time, put a port to idle mode.

(v) Spanning Tree Protocol (STP) is commonly used Layer 2 protocol that runs on switches and bridges, with purpose to ensure that there are no loops created on a redundant paths in the network. By default STP dynamically manages the elimination of the loops with the process of electing a tree based on priorities with a particular switch as a root. This means that there is a possibility of a network reconfiguration without the assistance of the operator, which could lead to additional power demands if it is not well managed. STP, enabled between the switches on the Figure 6, does not save any energy with its ability to block certain port in order to discard the loops in the network. Namely, a port in a blocking state is consuming the same amount of 0.4 W as the other active ports. The only noticeable difference is the spike of energy consumption when STP is trying to re-evaluate the tree. Namely, during a physical or a logical generated error, STP will elect a new root and construct the new tree, thus will add up to 1 W for few seconds to the overall consumption of the switch, depending on the architecture. This burst of energy, also shown on the Figure 9, is used to benchmark a change in the STP, with the interest of reporting it for possible misconfiguration of the network.

CONCLUSION AND FUTURE WORK

This paper presents the achieved results from evaluating the proposed novel extension for energy-efficient network management application emulated in a heterogeneous network environment. The results shows that a reliable application can be designed to monitoring the changes in the state of the devices with minor impact on the network regarding the traffic. The proposed monitoring process is designated as a replacement for the existing p2p pulling process, part of the SDN typical systems. The SDN controller, and thus the network operator, has the ability to receive reports for the changed state of the network in an energy-efficient way by following the energy consumption of the network infrastructure. The approach of monitoring the power consumption directly from the PDU, instead of p2p communication with every device, brings own complexity as the network grows. For instance, in a scenario of multiple faults happening simultaneously, the FDI concept presented in this paper is able to cope with the occurring situation. This is achieved by the possibility of following each PDU's socket individually from a centralized application. The support for real-time availability calculation enables the operator to take service-centric decisions, rather than network centric as proposed currently in the literature.

As future work, we envision a deployment of the proposed application as part of a SDN controller. Moreover, the application should be scalable in terms of network size and adapt to any SDN software controller developed on different programming language, with diverse libraries. The anticipation is also to include other common network anomalies and to follow their impact on the energy consumption, for instance the packet loss rate and highly congested networks, which could possibly trigger a use of other techniques in order to gather all the necessary information for the analysis process, rather than just monitoring the energy values.

List 1 :

 1 Figure 4. The classification of the faults One possible case study of network architecture is depicted on Figure 5, where the generated faults are represented as the 'Y' input parameter. At disposal for the experiments there were 8 Cisco switches from the series 2960 and 3560, 8 Cisco 1941 Routers, 10 Dell Precision T1700 stations, 2 HP Pavilion laptops, 6 Raritan PX2 PDUs and 2 Raritan PX3 PDUs.

Figure 5 .

 5 Figure 5. System behavior

Figure 6 .

 6 Figure 6. The experiment's logic

Figure

  Figure 7. Developed GUI

Figure 8 .

 8 Figure 8. Obtained results -experiment (i)

Figure 9 .

 9 Figure 9. Obtained results -experiments (ii) and (v)

ACKNOWLEDGEMENT

This work is part of the Erasmus Mundus Master programme in Pervasive Computing and Communication for Sustainable Development (PERCCOM) (Klimova et al., 2013) of the European Union (www.perccom.eu). The authors thank all the partner institutions, sponsors and researchers of the PERCCOM programme.