Abdelhak Imoussaten
email: abdelhak.imoussaten@mines-ales.fr

An Approach Based on MCDA and Fuzzy Logic to Select Joint Actions

Keywords: MCDA, Fuzzy logic, Constraint programming, Debate modeling

To satisfy a fluctuating demand and achieve a high level of quality and service, companies must take into account several features when designing new products in order to become or remain market leaders. When a single company is unable to meet this objective alone, it is appropriate for it to join its actions with other companies. The product design consists of the complex task to select from various potential actions that allowing the fulfilment of several requirements: functional, technical, environmental, economic, security, etc. Furthermore, the task is even more difficult when actions are related to distinct services or companies that do not necessarily know the capacities of each others which makes complex the coordination of joint actions. Interactions between services may be affected by antagonist personal interests. Based on a multiple criteria decision analysis (MCDA) framework and a fuzzy model that links actions to the satisfaction of objectives, this paper proposes to treat two extreme views related to the collective selection of the necessary actions to design a product: 1) The first point of view corresponds to an ideal situation where each service reveals its capacities and the unique objective is to succeed in the realization of the common goal ; 2) the second point of view corresponds to a more realistic situation where only necessary information for the progress of collective action are shared and where collective and personal goals coexist and are to be taken into account. The first situation corresponds to a classical case where a single decision maker (DM) has to express his preferences then a classical optimization problem under constraints has to be solved in order to efficiently select actions. In the second situation the services do not share the same preferences and each service wants to maximize its gain, in this case we propose to build a negotiated solution between services.

Introduction

When company designers/operators choose a new product or system, they have to check whether the new system satisfy company's strategic goals, customers needs and technical specifications. Furthermore, these issues are obviously not devoid of budgetary constraints.

MCDA is an interesting setting to evaluate and compare all alternatives for the new system based on their satisfaction of the previous multiple requirements.

The MCDA setting provides approaches for rigorous multidimensional evaluation. Indeed a set of non correlated attributes are carefully defined to measure the characteristics of the candidate solutions. Then the measures are mixed up with the subjectivity of the decision maker (DM) to deduce the degree of satisfaction provided by each candidate solution. In MCDA we distinguish several methods depending on the number of candidate solutions, number of attributes, compensation hypothesis, etc (see [START_REF] Greco | Multiple criteria decision analysis[END_REF] for more details). In this paper we focus on Multi objective Optimisations methods. Let denote by: S = {s 1 , s 2 , ...} a set of finite or infinite candidate solutions for the new system, {X 1 , X 2 , ..., X n } a finite set of attributes where X i is the space of values taken by the i th characteristic, N = {1, . . . , n} and X = i∈N X i . Each element of S can be represented by its results obtained on the set of attributes, then s k ∈ S can be represented by the vector (x k 1 , . . . , x k n ) where ∀i ∈ N , x k i is the result of s k on the i th characteristic. Thus, the satisfaction provided by the solution s k can be represented by a real v(s k ) where v is a bounded function (v : X → [0, 1]). Finally, the problem of choosing the new system can be setted as follows:

max v(s) s.t: s ∈ S c(s) ≤ c 0 (1)
where c : S →]0, +∞[ is the function associating to each candidate solution its cost and c 0 > 0 is the maximal cost allocated to the new system. When functions c and v are known we are faced to a classical optimization problem under constraints. Usually in MCDA, a single DM holds the preferential information that allows to build the function v. Particularly, in Multi Attribute Value Theory (MAVT [START_REF] Keeney | Decision with multiple objectives[END_REF] [START_REF] Dyer | Multiattribute utility theory (maut)[END_REF]) the existence of a such value function is guaranteed when DM preference relation over S denoted , s k s k means s k is at least as good as s k , is a weak order. In this case, v represents the DM preferences over S and we have :

∀s k , s k ∈ S, s k s k ⇔ v(s k ) ≥ v(s k ).
(

) 2
The easiest way to find v is to build it from the DM preference relation on each attribute i ∈ N denoted i and represented by a value function v i :

X i → [0, 1].
In [START_REF] Krantz | Foundations of measurement (additive and polynomial representations[END_REF] the conditions of a such construction are given. Furthermore, a single DM who has a perfect knowledge about implementation actions of a solution can estimate their costs. Thus, in this case of a single DM, c and v can be identified.

Unfortunately, this hypothesis of the existence of a single decision maker who knows the costs of actions and with whom we can build the utility function, is not adapted to all companies configurations. Indeed, in many cases, these actions are generally spread/distributed onto several services which are then in charge of their own actions.

Classically in MCDA, the behavioural relationship between actions related to a candidate solution and the results obtained on the system characteristics are not considered. As mentioned previously, in this case, a candidate solution is represented only by its results obtained on the set of attributes. In the case of several services, the reference to the actions composing the candidate solution is required. Indeed, it would be difficult to establish with certainty the consequences of a set of actions on the attributes since actions are related to several services and applied jointly. This is because no services has complete information about all actions.

In this situation two models are envisaged, based on distinct hypothesis. Either, services collaborate fully then they share their knowledge between each others such that all services will have complete information. The problem to resolve here is to select the subset of actions guaranteeing the "best" satisfaction of common goals at minimal cost (see [START_REF] Montmain | Multi-criteria improvement of complex systems[END_REF] for more details). Or, services act as autonomous agents but are cooperating: they make their possible to reach collective objectives although they have also personal interests in the project. The more actions are carried out in a service, the greater his budget. It is a thorny problem because each service has only a partial information and don't necessarily know the capacities of other services. The problem to resolve here is to build a solution by selecting a subset of actions from all services guaranteeing the satisfaction of all services and respecting budget constraints.

The aim of this paper is to propose two different models for these two situations. In the first situation the decision process is stated in the form of an multi objective optimisation problem under constraints and in the second situation, the decision process is modelled as a debate.

The paper is structured as follows. First, section 2 establishes the model of relationships between actions and objectives satisfaction. Sections 3 and 4 presents the formalization of the problem of defining joint actions composing the solution satisfying all services and respecting cost constraints respectively on the collaborative and cooperative situations.

Fuzzy Relationship Between Actions and the Satisfaction of Objectives

We consider a group of services denoted D = {d 1 , ..., d l } that are in charge of building a common solution for the design of a new product or system. Each service d is in charge of a set of actions A d . For instance, an action consists in a person performing a task, a mechanical or software component, etc. Each service proposes his actions to compose a candidate solution with other services. Thus the set of candidate solutions S = {s 1 , s 2 , ...} is composed of all admissible joint actions. These actions must guarantee a good performance of the new system. We assume here that the performance of the new system induced by a set of joint actions s ∈ S is measured by v(s) where the value function v is defined in formula 2. The function v represents the overall satisfaction of the objectives set for the new system. Here, v will be built on the basis of what the services will provide as information about the effects of their actions on the satisfaction of the objectives of the system. Moreover, we consider that the value function v may be obtained through the partial value functions v i , i ∈ N representing the satisfaction on each single objective using an appropriate aggregation operator.

The transformation that links actions in A d and the i th objective, i ∈ N , is composed of two transformations: 1) The transformations T i (i ∈ N ) that represents the behavioral relation between inputs (actions) and each of its outputs (characteristics); 2) the value functions v i expressing the satisfaction of the service related to the achievement of the i th objective.

Most of the time, the transformation T = (T 1 , . . . , T n ) cannot be precisely known in a complex system. In some cases, the acquisition of T requires complex simulations or experiments, which are costly and time consuming (example of military architecture, [?]). Hence transformation T generally needs to be approximated. We will use a fuzzy behavioral model. Indeed, as the gathered information originates from the experts or managers perception rather than being factually measured, it is intrinsically imprecise [START_REF] Montmain | Multi-criteria improvement of complex systems[END_REF].

Furthermore, each action considered must allow the satisfaction of at least one objective but it is not excluded that this action may have a negative impact on other objectives. Thus, the scale used for the evaluation of each objective must be bivariate allowing positive and negative evaluation [START_REF] Grabisch | Bipolar and bivariate models in multicriteria decision analysis: Descriptive and constructive approaches[END_REF]. For instance, in the automotive industry, the action of "using modular platform" reduce the weight of cars and then has a positive impact on the objective "reducing the shock with a pedestrian, animal or cyclist" but this action could impact the stability of the vehicles then it has a negative impact on the objective "safety of the driver". In our setting, we propose to use two linguistic variables to represents the impact of actions on each objective: satisfaction and dissatisfaction variables.

In [START_REF] Imoussaten | Multi-criteria improvement of options[END_REF] [5] [8] a degree in ]0, 1] called the "degree of belief" for positive or negative impact of an action on an objective is introduced. The semantic of this degree is unclear and then not easy to provide by experts. In addition, the imprecision inherent to expert knowledge is not taken into account. In this paper we propose to represent the impact of actions on objectives within the setting of fuzzy logic. Thus several linguistic terms can be associated to each of the two previous linguistic variables. For example, terms low, medium and strong can be used. Definition 1. Consider the i ih objective, denoted Obj i where i ∈ N , and an action a ∈ A. Either, action a induce a satisfaction on Obj i in a such case S a i denote the associated linguistic term describing the degree of a such satisfaction. Or, action a induce a dissatisfaction on Obj i in a such case D a i denote the associated linguistic term describing the degree of a such dissatisfaction.

The bivariate fuzzy model described in Definition 1 can be represented through a digraph between A and N , denoted Dig(A, N ), such that (Fig. 1 shows an example): the arc between a and Obj i defined As we can remark in the example given above of automotive industry, a single action can not satisfy all the objectives. Thus several actions are required. Let consider a subset of actions ap and an objective Obj i . Several actions in ap may induce satisfaction on Obj i and several other actions in ap may induce dissatisfaction on Obj i . We denote by A S i (ap) (resp. A D i (ap)) the crisp subset of actions in ap that induce satisfaction (resp. dissatisfaction) on Obj .

Arc(a, Obj i ) = +S a i in case of satisfaction -D a i in case of dissatisfaction (3) a1 a2 • • • aj • • • aq Obj1 Obj2 • • • Obji • • • Objn T +very low Q -low
To obtain the overall satisfaction and dissatisfaction of the joint implementation of actions in ap, it is important to consider all the interactions and results emerging from the joint implementation of some actions. The simplest solution is to evaluate the impact of all possible combinations of actions. However, when the set of actions is very large, this solution seems unrealistic. To simplify, we consider again a soft model based on mathematical operator applied to fuzzy subsets. In order to reduce the number of actions that do the same thing, we consider that the satisfaction and dissatisfaction caused by the joint actions can not be additive. Thus, based on cautious behaviour, we keep all the maximum possibility degrees of satisfaction and dissatisfaction in the aggregated result by using a conjunctive operator. Finally, we propose to synthesize the satisfaction and dissatisfaction of ap on Obj i as follows:

µ S ap i = a∈A S i (ap) µ S a i ; (4)
µ D ap i = a∈A D i (ap) µ D a i . (5)
where µ S a i (resp. µ D a i ) is the fuzzy subset associated to linguistic term S a i (resp. D a i ). The next step is to verify if service is satisfied by the impact of actions in ap on Obj i . This is done here by comparing the center of area of the resulting two fuzzy subsets µ S ap i and µ D ap i to two thresholds α i , β i ∈]0, 1] fixing the limits of satisfaction and dissatisfaction degrees. Equations ( 4), ( 5) and definition 2 concerns a single objective but can be extended to any subset of objectives.

The principle extension of Zadeh allows aggregating satisfactions and dissatisfactions as follows:

µ S ap N (y) = (y1,...,yn) φ S (y1,...,yn)=y i∈N µ S ap i (y i ). ( 6
)
where φ S is an aggregation operator representing the DM trade-off on the satisfaction of

µ D ap N (y) = (y1,...,yn) φ D (y1,...,yn)=y i∈N µ D ap i (y i ). ( 7
)
where φ D is an aggregation operator representing the DM trade-off on the dissatisfaction of objectives. Note that φ S and φ D are two operators applied to a vector of real values from [0, 1] n to [0, 1]. They can be a classical operators like min, max or weighted average operator or more sophisticated operators like Choquet integral or Sugeno integral.

We can also define the satisfaction and dissatisfactions of ap on a subset of objectives I ⊂ N by fixing the results of ap on the remaining objectives, i.e., N \ I, at given values:

µ S ap I (y) = y I φ S (y I ,y 0 N \I )=y i∈I µ S ap i (y i ). ( 8
)
µ D ap I (y) = y I φ D (y I ,z 0 N \I )=y i∈I µ D ap i (y i ). ( 9
)
where the notation y I represents the components of the vector (y 1 , . . . , y n ) for the indices in I and the notation (y I , y 0 N \I ) represents the vector z where z i = y i if i ∈ I and z i = y 0 i if i ∈ N \ I. In the similar way as in definition 2, we verify if ap satisfy the subset of objectives I. Note that the dissatisfaction degree will be less mentioned than the satisfaction degree in the following. Indeed, the satisfaction the degree is the aggregated s I (ap) result of ap, including dissatisfaction degree, and if s I (ap) = 0 it means that d I (ap) ≤ β I .

Selecting Joint Actions from Collaborative Services

An operational cost c(ap) is associated with each action plan ap. We assume for any action a, c({a}) > 0 and: c(ap) = a∈ap c({a}).

In most instances, a cost constraint is applicable to the new system such that the cost of an action plan cannot exceed a predetermined budget denoted b 0 ∈]0, ∞]. In addition, the new system may require a degree of satisfaction higher than a predetermined threshold α 0 ∈]0, 1]. Nevertheless, services of course prefer the solution with the highest satisfaction degree when the cost is the same; inversely, they prefer the cheapest solutions when the satisfaction degree is the same.

Let us define the Pareto order ≺ Pareto over action plans: In collaborative approach where service share all their knowledge of the system before collective action, the complete digraph Dig(A, N ) is known and the multi-objective optimization problem of formula ( 1) is adapted for our fuzzy model as follows:

(s N (ap), -c(ap)) ≺ Pareto (s N (ap ), -c(ap )) ⇔ [(s N (ap) < s N (
max (s N (ap), -c(ap)) s.t:      ap ⊆ A = d∈D A d s N (ap) ≥ α 0 c(ap) ≤ b 0 (11)
When the number of actions is very large the resolution of this optimization problem clearly raises a combinatorial problem.

The hypothesis of collaboration leading to the optimisation problem of formula (11) means that the services involved in the process of designing the new system share their partial knowledge on the fuzzy model of relationship between action and objectives so that all services have full knowledge of the model before committing collective action. This assumption is not always valid; service heads are not always willing to share knowledge of their own design service. However, they are willing to cooperate to build a common solution. Thus collaborative approach is not often feasible in practice. It seems more natural to consider that the teams will cooperate more than collaborate. In the following section, we address the problem of selecting joint actions from cooperative services.

Selecting Joint Actions from Cooperative Services to Achieve Common Goals

In the case of cooperating services, the model is constructed gradually: each service contributes when it is required, there is no a priori planning. The collective choice of action plan is thus modelled as a debate. Services exchange knowledge and negotiate the way actions will be distributed. The more actions are carried out in a service the greater his budget. We consider that no service is able to possess the action plan satisfying all the objectives. Thus, each service needs actions from others to build joint action plan.

General Principle for Debate Structure

Let consider a service d ∈ D. Actions in A d induce impacts only on a subset For simplification purpose and to limit the information required from the experts, we consider that the thresholds of satisfaction and dissatisfaction for subsets of objectives can be deduced from those of single objective as follows: ∀I ⊆ N , α I = min Services would propose their actions in order to increase their budget, then we need to manage the turn of propositions. This is done by selecting the service having the best offer for the common objective at the current stage. Then services have to learn from the previous propositions in order to make adequate next proposition.

I d = {i d 1 , . . . , i d |I d | } ⊆ N . The partial digraph Dig(A d , I d ) of service d is presented in figure 2. a d 1 a d 2 • • • a d j • • • a d |A d | Obj d 1 Obj d 2 • • • Obj d i • • • Obj d |I d | T +very low Q -low
Indeed, at the beginning, the services do not know the impacts induced by the actions of others services. At this stage, the information shared between the services are: the set of objectives to be satisfied N , the constraints α i , β i , ∀i ∈ N and the constraint concerning the cost of the proposed actions that should not exceed the budget b 0 . However, each service d start with a fictive complete digraph by introducing fictive actions that are supposed to be owned by other services and satisfying objectives that are not satisfied by d.

When a proposal is made, the service reveals required information on the proposed actions. Each service has to take advantage from this information and complete his partial digraph to make successful propositions.

Let us introduce time variable t explicitly in the notations. Let ap t be the common action plan build at time t and I t the subset of objectives satisfied, i.e., s It (ap t ) ≥ α 0 , by ap t . The debate organization is broken down into the following steps:

-At t = 0, ap 0 = ∅ and I 0 = ∅.

-At t ≥ 1, the current action plan is ap t-1 and the satisfied objectives are in I t-1 . -When at t ≥ 1 no proposal can be made by services because of cost constraint, the debate starts from the beginning, i.e. the resulting common action plan is emptied, and services update their information. -The debate ends when I t+1 = N and cost constraint is respected.

Note that when a joint action plan satisfying all the objectives is found all other remaining actions are no longer receivable.

Individual Action Plan Choice Strategies

At each step t, all the services with available actions must adopt an appropriate strategy to propose the most relevant actions. The stake is twofold: i) the actions proposed by a service must be chosen at time t and, 2) the common action plan must be successful.

Let AP d (t) the Pareto front of solutions for the optimisation problem (11) for the digraph Dig(A d (t -1), I d (t -1)). The following criteria may be introduced to select a solution sap d (t) from AP d (t) depending on the debate stage:

-sap d (t) may maximize the number of satisfied objectives, i.e., there is no cost conflict; -sap d (t) may maximize the satisfaction degree; -sap d (t) has minimal cost.

Fair Resources Sharing

Let denote props(t) the set containing the next propositions of the services (each service propose a single sub action plan).

Let consider the following notations: To quantify the loss of earnings for service d with respect to ap t we can use the following formula: G max d -G d (ap t ). However, for homogeneity reasons, the formula (12) is preferred.

-G max d = a∈A d c (
ρ(d, ap t ) = (G max d -G d (ap t ))/G max d . (12)
We assume that each service have at least an action with strictly positive cost. We consider in our approach that the group tries to avoid an unfair sharing of the allocated budget by minimizing the loss of earnings of the worst paid service. The worst paid service with respect to to common action plan ap t is defined as follow:

d(ap t ) = arg max d∈D [ρ(d, ap t )]. (13)
It comes that the new proposition sap(t) should verify:

sap(t) = arg min sap∈props(t) max d∈D [ρ(d, sap ∪ ap t-1 )]. (14)
The new common action is ap t = sap(t) ∪ ap t-1 .

Digraphs Updating

Let d(t) the service owner of the proposal sap(t) ⊆ A d(t) . Service d ∈ D \{d(t)} a priori don't know satisfactions and dissatisfactions induced by actions in sap(t).

The service d(t) must give the necessary information about his actions so that the other services can complete their digraph and make the next proposals. d(t) should reveal the following information:

the new satisfied objectives I s d(t) ; the new dissatisfied objectives I d d(t) ; the maximum dissatisfaction degree induced on I d d(t) ;

the cost of actions in sap(t); the new satisfaction degree.

From those information and from the fact that new actions should guarantee s I(t) > 0, services in D \{d(t)} have a quantity of helpful information to continue the construction of their complete digraph.

Conclusion

This article offers an aid to the evaluation of the degree of satisfaction of a new product or system to a set of expected objectives when various candidate solution are possible and several teams are involved in the project. The evaluation focuses on the actions leading to the implementation of new product or system. We have shown the link between this problem and a classical decision-making process based on MCDA approach and we have distinguished two configurations of services in a company: collaborative services and cooperative services. In the first configuration a multi-objective optimisation problem is stated to resolve the problem of selecting the optimal set of actions with regard to cost and satisfaction degree constraints. In the second configuration, the problem is stated as a debate between services where the objective is to build a common action plan satisfying a set of objectives under the same previous constraints. The debate modelling is better suited to practical situations where each service controls his own knowhow, and only shares the part of his knowledge which is required achieving the global objective, defending his own interests and not necessarily revealing his weaknesses. The debate model can be also seen as a decision-support system used by a service (or a group of services) during the real debate to optimize his own interest. In the two cases fuzzy logic and MCDA tools are used to represent the relationship between actions and objectives satisfaction. This is a preliminary work. In order to complete our debate modelling, several points in our approach deserve to be deepened in the future works. For instance, we are currently working on refining and finalizing the knowledge updating phase. In addition, we are working to provide an illustrative example of the approach. Furthermore, we will work to establish links between this work and existing approach dealing with debate modelling as the fields of game theory and theory of argumentation.

Fig. 1 .

 1 Fig. 1. Digraph of actions-objectives relationships

Definition 2 .

 2 Let consider an action plan ap, an objective Obj i and two thresholds α i , β i ∈]0, 1] . We consider that ap satisfies Obj i if:1.

  dy ≤ β i .

Definition 3 .

 3 Let consider an action plan ap, a subset of objectives I ⊆ N and two thresholds α I , β I ∈]0, 1] . We consider that ap satisfies objectives in I if:1. s I (ap) = dy ≤ β I .If the two previous conditions are satisfied, s I (ap) is considered as the degree of satisfaction of objectives on I by ap, otherwise s I (ap) = 0.

  ap )) and (c(ap) ≥ c(ap ))] or [(s N (ap) ≤ s N (ap )) and (c(ap) > c(ap ))] (10) Action plan ap is dominated by action plan ap if (s N (ap), -c(ap)) ≺ Pareto (s N (ap ), -c(ap )).

Fig. 2 .

 2 Fig. 2. Partial digraph of actions-objectives relationships

  i∈I α i , and β I = max i∈I β i . It comes α 0 = min i∈N α i . This is an optimistic way of considering aggregated satisfaction and dissatisfaction thresholds.

  a) the maximal expected gain for service d, -G d (ap t ) = a∈apt∩A d c(a) the individual gain of service d from the common action plan ap t .

  1. Each service propose an action plan to complete ap t-1 . The new proposal should satisfy new objectives in N \ I t-1 and should guarantee s I(t) > 0. He adopts a suitable strategy to make a proposal that maximizes his earnings (see subsection (4.2)). The algorithm solving the optimisation problem (11) is used locally by the service to select actions forming his proposal; 2. A selection is made for the next action plan to add to ap t-1 (see subsection 4.3); 3. Action plan ap t satisfying I t is built by adding new actions to ap t ; 4. Each service updates his information about the proposed actions (see subsection 4.4). Thus the partial digraph of a service is time depending, denoted Dig(A d (t), I d (t)).


Abdelhak Imoussaten
email: abdelhak.imoussaten@mines-ales.fr

Lucie Jacquin
email: lucie.jacquin@mines-ales.fr

Cautious classification based on belief functions theory and imprecise relabelling

Keywords:

The performances of standard classifiers, i.e., any method of point prediction for classifi-cation, decline in case of imperfect data. In some sensitive domains where these imper-fections are present, these classifiers need to be adapted in order to avoid any misclassification that has serious consequences. Recent works proposed to deal with this problem by using cautious classification techniques. This paper is in line with these works, espe-cially with imprecise classifiers, i.e., the output of the classifier for an input sample that is subject to considerable imperfections is a subset of classes. The distinctive feature of our imprecise classification proposition is that it considers that in some applications, data im-perfection is not limited to new samples to be classified but can also be present in training data. We therefore propose a relabelling procedure which allows us to identify imperfect samples in the training data and relabel them with an appropriate subset of candidate classes. This approach to imprecise classification is close, in some aspects, to hierarchical classification where a "parent" can be considered as a subset of classes that are the "chil-dren" in the leaves. Furthermore, the belief functions framework is considered to represent the uncertainty and imprecision about the class of a new sample where the focal elements are contained in the set of new labels of the training data. A criterion based on a gener-alised F β score and the obtained mass function is established to decide which subset of classes should be associated to the new sample. Several options are presented to build our classifier for the relabelling procedure and for the reasoning step. Thus, the performances of each option are presented before comparison with state-of-the-art imprecise classifiers' performances. The comparisons are conducted first on randomly generated data and then on 11 UCI datasets based on five measures of imprecise classification performances. They show that our classifier achieves performances close to, sometimes better than, the best on the five measures.

Introduction

Several causes can lead to imperfect data such as measurement inaccuracy due to the quality of sensors, data unreliability, partial data, etc. In [START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: data disambiguation through generalized loss minimization[END_REF] the distinction is made when representing imperfect data between ontic and epistemic views [START_REF] Couso | Statistical reasoning with set-valued information: ontic vs. epistemic views[END_REF]. In the ontic view, the imperfect data representation is interpreted as the "true value", i.e., a precise representation of reality while, in the epistemic view, the imperfect data representation is used to describe imperfection of knowledge about the data. In this paper we consider a representation of data imperfection that is consistent with the epistemic view. In the cases where the data are imperfect, classical machine learning techniques reach their limits. Indeed, in the case of supervised classification, for example, a method of point prediction for classification can misclassify a new sample. This can have serious consequences when a classification task is involved in applications that are sensitive, as in medical diagnosis applications when the classifier has to detect early-stage cancer; or in autonomous car applications when the classifier has to distinguish between a human or animal and an object in dangerous situations; or in environmental compliance when a classifier has to sort plastics for recycling purposes, and identification errors will cause serious recycling difficulties and significant degradation of the secondary raw material performances [START_REF] Jacquin | Control of waste fragment sorting process based on mir imaging coupled with cautious classification[END_REF], etc. The misclassification of some samples can be caused by the existence of overlapping regions in the feature space representation [START_REF] Xiong | Classification algorithm based on nb for class overlapping problem[END_REF] [START_REF] Lee | An overlap-sensitive margin classifier for imbalanced and overlapping data[END_REF] due to the imperfect data. This problem occurs when the obtained characteristics of some samples are very similar even if they are labelled using different class labels. The misclassification can also be caused when the samples belong to an isolated region, i.e., a region that is represented by very few samples in the training data.

Facing the issue of imperfect data, recent works focus on cautious classification. Cautious classification aims to minimize errors by providing a reliable output based on an appropriate representation of uncertainty. The idea of favouring the reliability of the information rather than the precision of its content was initially introduced in the work of R. A. Fisher [START_REF] Fisher | The fiducial argument in statistical inference[END_REF] and J. Neyman [START_REF] Neyman | X-outline of a theory of statistical estimation based on the classical theory of probability[END_REF] in the fields of statistical/Bayesian inference with the concept of confidence interval/region by associating a confidence threshold to the set provided as an estimation of a parameter. A particular case of cautious classification is imprecise classification, which consists in predicting a subset of candidate classes for a sample in the event of imperfect data. This can be beneficial, for example, in medical diagnosis applications by orienting the investigation toward a small set of candidate alternatives; or in the case of plastics sorting by adding a container dedicated to a given family of plastics [START_REF] Jacquin | Control of waste fragment sorting process based on mir imaging coupled with cautious classification[END_REF], etc. The first works were proposed in the probability theory framework and consisted in predicting a subset of classes for a sample when the maximal probability is below a fixed threshold [START_REF] Chow | An optimum character recognition system using decision functions[END_REF] [9] [START_REF] Ha | The optimum class-selective rejection rule[END_REF]. The predicted subset is the smallest whose cumulative probability exceeds a given threshold [START_REF] Ha | The optimum class-selective rejection rule[END_REF]. In a recent work [START_REF] Coz | Learning nondeterministic classifiers[END_REF], the latter approach was adapted to propose the non-deterministic classifier (ndc) by taking into account a gain function when maximising the expected gain. Based also on the framework of probability theory and statistics, conformal prediction [START_REF] Vovk | Conformal prediction[END_REF] [13] provides confidence regions based on statistical hypothesis testing. More recently, the authors of [START_REF] Ma | Partial classification in the belief function framework[END_REF] proposed, within the framework of belief functions, an extension of the utility matrix that considers the gains in the case of point prediction classification to an utility matrix considering gains in the case of imprecise prediction using aggregation functions. Within the framework of imprecise probabilities, imprecise classification is mainly based on a binary relation defined on the set of classes and the pre-order inferred from this relation. The subset of the non-dominated classes is considered as the prediction for the new sample. The Naive Credal Classifier (ncc) [START_REF] Zaffalon | Statistical inference of the naive credal classifier[END_REF] [START_REF] Zaffalon | A credal approach to naive classification[END_REF] is an example of a classifier based on this approach where the dominance relation is inferred from the credal set representing the imprecision and uncertainty about the true class of a sample. The difficulty in this approach lies in the step of building the credal set. In [START_REF] Zaffalon | Statistical inference of the naive credal classifier[END_REF] the credal set is built using the Imprecise Dirichlet Model (IDM) [START_REF] Bernard | An introduction to the imprecise Dirichlet model for multinomial data[END_REF] while in [START_REF] Zaffalon | A credal approach to naive classification[END_REF] the credal set is built using an interval constraints approach [START_REF] De Campos | Probability intervals: a tool for uncertain reasoning[END_REF]. Following the same principle, [START_REF] Nguyen | Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty[END_REF] proposes an imprecise classifier where the dominance relation is based on different quantifications of uncertainty based on a binary classifier [START_REF] Senge | Reliable classification: learning classifiers that distinguish aleatoric and epistemic uncertainty[END_REF] trained to distinguish aleatory and epistemic uncertainty. Furthermore, [START_REF] Quost | Dealing with atypical instances in evidential decision-making[END_REF] proposed building a pre-order on the set of class labels based on a mass function. This approach uses interval dominance, where the intervals are represented by the belief and plausibility functions. The same principle of dominance is also used in [START_REF] Fürnkranz | Preference learning and ranking by pairwise comparison[END_REF] [START_REF] Hüllermeier | Learning valued preference structures for solving classification problems[END_REF], where a fuzzy preference relation is deduced from the scores of a binary classifier in a "one-against-one" scheme. This fuzzy relation is exploited to obtain a pre-order on the set of classes.

Regarding what has been proposed in the state-of-the-art works, the distinguishing features of our proposition are as follows. First, we consider that imperfection can be present not only in the new samples but also in the training data. A relabelling procedure is therefore proposed to relabel the samples that are in overlapping or in isolated regions. Second, a gain matrix that incorporates the specialisation gain to control the trade-off between cautiousness and efficiency of the imprecise prediction is proposed. The second point is inspired both from the matrix gain proposed in [START_REF] Coz | Learning nondeterministic classifiers[END_REF] and the performance measures used in hierarchical classification. The specialisation gain is employed to penalise predictions that are more precise than the information available about a sample could allow. Moreover, the relabelling step allows us to directly learn labels in the form of subsets of classes, including singletons. This differentiates our approach from the other ones as only the subsets of classes identified in the relabelling step can be predicted to the new samples. The proposed approach is named eclair (Evidential CLAssification with Imprecise Relabelling) and uses the belief functions framework [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] to represent the uncertainty and imprecision present in the data. It is built in three steps: 1) the relabelling step which is applied to the learning data and serves to assign new labels, in the form of subsets of class labels, to the samples belonging to the overlapping and isolated regions in the feature space; 2) the learning step consists in training a standard classifier on the resulting new training data; 3) and the reasoning step which takes a mass function and a gain function as inputs and provides a subset of classes as output. When applying the reasoning step to process a new sample, the mass function corresponds to the chances quantified by the trained classifier for each subset of classes to be the "true" label of the sample. As one can notice in the mentioned works about imprecise classification, the classifiers fall in two categories. The dominance-relation based classifiers and the expected-gain based classifiers. The comparisons of eclair performances are presented related to two classifiers each representing one of the two categories: ncc for the first category and ndc for the second one.

This paper is organised as follows. In Section 2, some reminders are given about imprecise and hierarchical classification, elements of belief functions theory, and the evaluation measures of imprecise classifiers. In Section 3, the proposed approach is detailed. Section 4 is dedicated to comparing firstly the different options of the eclair classifier, and secondly times to comparing eclair to the approaches of state-of-the-art imprecise classifiers. The comparison uses both a simulated dataset and UCI datasets. Finally a discussion is proposed in Section 3.4.

Background

In this section, background notions are briefly presented and notations are introduced. The imprecise classification is first presented in Section 2.1, in Section 2.2 the link between hierarchical classification and the imprecise classification is briefly discussed, some reminders about the theory of belief functions are given in Section 2.3 and the evaluation measures for the imprecise classifiers are presented in Section 2.4.

Imprecise classification

Imprecise classification is a kind of cautious classification that enables the prediction of a subset of candidate classes for difficult samples, i.e., samples for which the available information is highly affected by imperfections and make the assignment to a single class label too uncertain. More precisely, let us consider the case of a supervised classification task where the samples represented by P characteristics X 1 , X 2 , . . . , X P should be classified using a set of n class labels = {θ 1 , θ 2 , . . . , θ n }. Let us also consider a set of interest A ⊆ 2 \ ∅. An imprecise classifier δ ic is a mapping from the Cartesian product X = P i=1 X i ⊆ R P to A:

δ ic : X → A,
where for a sample x ∈ X , δ ic (x) ∈ A is a subset of classes. Note that the number of elements in δ ic (x) is not necessary strictly greater than one and unlike what is usually considered in the state of the art, we consider that the set of interest

A is not necessary equal to 2 \ ∅. Indeed, with regard to the interest of the user or the constraints of the application, the set A can be reduced to a very small part, necessarily including the singletons, of 2 .

Hierarchical classification vs imprecise classification

In the hierarchical classification setting, the classes correspond to structured nodes governed by "IS-A" links called parents-children where the class children is included in the class parents. The nodes that have no children are called leaves of the hierarchical structure. Imprecise classification can be connected to hierarchical classification by considering that the prediction of a parent node in the hierarchy corresponds to the imprecise prediction of the subset containing all the child leaves attached to this node. Nevertheless, two main differences between these two classification techniques have to be mentioned. First, in the case of hierarchical classification, the predictions are elements of the pre-established hierarchical structure whereas for imprecise classification the outputs can be any non-empty subset of , even if it has no particular semantics in reality. Second, according to [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF], the case of partially labelled samples, i.e., whose true class label is not necessarily a leaf of the hierarchy, has been considered in several hierarchical classification works [START_REF] Punera | Enhanced hierarchical classification via isotonic smoothing[END_REF][START_REF] Binder | Efficient classification of images with taxonomies[END_REF]. For this second point, the difference lies in the fact that in the hierarchical classification the nodes are governed by a conceptual representation [START_REF] Harispe | On the consideration of a bring-to-mind model for computing the information content of concepts defined into ontologies[END_REF] and a parent node could be the true class label for a sample in the training data. Consequently, two types of supervised classification errors are considered in hierarchical classification. The first one is the generalisation error [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF] [29] that occurs when a classifier predicts a class that is the antecedent of the true class of a sample. The second one is the specialization error [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF] [29] that occurs when a classifier predicts a class that is the descendant of the true class of a sample. Note that the term of generalisation error introduced in the hierarchical classification techniques should not be confused with the notion of the generalisation error that is central in machine learning and that quantifies the ability of an algorithm to predict the outcome of new samples. In the case of imprecise classification, the situation of partially labelled sample in training data occurs when this sample could not be precisely assigned to a single class label due to lack of knowledge. In this case, the generalisation error correspond to the error of predicting a subset of candidate class labels that is wider than the partial label of the sample. While the specialization error can be interpreted in the imprecise classification as the error of predicting a subset of candidate class labels that is smaller than the available information allows. Thus, when resolving an imprecise classification problem the situation can be similar to that of hierarchical classification in the case where the class labels of some samples in the training data are partially known.

Belief functions theory

In this Section we give a brief reminder about belief functions theory. Let us consider a reference set where each element θ ∈ represents the lowest level of discernible information in . The set is called a frame of discernment. Belief functions theory, is an interesting framework to represent and process uncertain and imprecise information and can be seen as an extension of many uncertainty theories. The recent growing interest in this theory has allowed techniques to be developed to resolve a diverse range of problems such as estimation [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF] [31] [START_REF] Kanjanatarakul | Prediction of future observations using belief functions: a likelihood-based approach[END_REF], standard classification [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF][START_REF] Sutton-Charani | Evidential bagging: combining heterogeneous classifiers in the belief functions framework[END_REF], or even hierarchical classification [START_REF] Alshamaa | A hierarchical classification method using belief functions[END_REF][START_REF] Naeini | Learning by abstraction: hierarchical classification model using evidential theoretic approach and bayesian ensemble model[END_REF]. Three main set functions are involved in the belief functions framework. The mass function which assigns probabilities to imprecise information, leading to the distinction between equiprobability and imprecision or ignorance. More precisely, a mass function, also called basic belief assignment (bba), is a set function m : 2 → [0, 1] satisfying m(∅) = 0 and A⊆ m( A) = 1.

The elements A ∈ 2 , such that m( A) > 0, are called focal elements and they form a set denoted F . The pair (m, F) is called the body of evidence. The belief function measures the quantity of evidence proving an event, Bel : 2 → [0, 1], satisfying

Bel( A) = B⊆ ,B⊆A m(B).
The plausibility function measures the quantity of evidence that makes an event possible, Pl : 2 → [0, 1], satisfying

Pl( A) = B⊆ ,B∩A =∅ m(B).
The above-defined set functions constitute the credal level where beliefs are captured and quantified. A second level considered in the belief functions framework is the pignistic level or decision level where beliefs are quantified using probability distributions. In this latter level, the pignistic probability distribution is computed as follows: ∀θ ∈ ,

pig m (θ) = A⊆ ,A θ m( A) |A| ,
where |A| denotes the number of elements in A.

Evaluation measures for the imprecise classifiers

When a classifier provides an imprecise prediction for a new sample, the evaluation of its performance is not straightforward and the classical measure of accuracy is not appropriate. The task of evaluating the performance of an imprecise classifier can be formulated as the problem of defining a performance measure that takes into account the trade-off between the criterion of cautiousness, i.e., the classifier should predict a subset of classes including the "true" classes of a sample that has imperfect data, and the criterion of efficiency, i.e., the predicted subset of classes should be as small as possible depending on the sample data. Several works have studied this problem and provide some measures to model this trade-off [START_REF] Zaffalon | A credal approach to naive classification[END_REF], [START_REF] Abellan | Imprecise classification with credal decision trees[END_REF], [START_REF] Yang | The costs of indeterminacy: how to determine them?[END_REF]. Discounted accuracy [START_REF] Tsoumakas | Random k-labelsets: an ensemble method for multilabel classification[END_REF] seems to be an interesting measure as it takes into account the size of the predicted subset. However, as pointed out in [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF], this measure rewards a predicted subset as if a random assignment had been made in this subset. Thus the discounted accuracy fails to recognize the benefit of cautious decisions over hazardous decisions. To handle this problem new measures were proposed to increase the cautiousness reward to the necessary extent, i.e., the degree to which the decision maker prefers to fix the reward of cautiousness depending on his application and the quality of the information obtained for the samples. These measures are represented by a function g of the discounted accuracy taking its values in [0, 1] and guaranteeing g(z) ≥ z, i.e., the reward with g is at least the same as the one given by the discounted accuracy, g(0) = 0 and g(1) = 1 (see [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF] for more details).

Let us consider a dataset of test samples dst = (x l , θ l ) 1≤l≤M where x l ∈ X and θ l ∈ and an imprecise classifier δ ic . The formula of the above-mentioned performance evaluation measures applied to classifier δ ic and the test data dst are given as follows:

• the classical accuracy measure that quantifies the proportion of good predictions:

accurac y(δ ic , dst) = 1 M M l=1 1 {θ l } (δ ic (x l )).
• the imprecise accuracy (imprAcc) measure that quantifies the predictions containing the true class labels of the test samples:

impr Acc(δ ic , dst) = 1 M M l=1 1 δ ic (x l ) (θ l ).
• the discounted accuracy (discAcc) measure that quantifies the mean of the proportions of the good predictions in the predicted subsets and corresponds to the function

g(z) = z: disc Acc(δ ic , dst) = 1 M M l=1 1 δ ic (x l ) (θ l ) |δ ic (x l )| .
This measure is denoted also u 50 .

• The u 65 measure that corresponds to the function g

(z) = -0.6 • z 2 + 1.6 • z: u 65 (δ ic , dst) = -0.6 • [disc Acc(δ ic , dst)] 2 + 1.6 • disc Acc(δ ic , dst).
• The u 80 measure that corresponds to the function

g(z) = -1.2 • z 2 + 2.2 • z: u 80 (δ ic , dst) = -1.2 • [disc Acc(δ ic , dst)] 2 + 2.2 • disc Acc(δ ic , dst).
Where for a subset A of , the function 1 A : → {0, 1} is the characteristic function such that:

1 A (θ) = 1 if θ ∈ A;
and 0 otherwise. The u 50 measure is considered as well suited to binary classification problems while u 65 and u 80 are well suited to classification problems with more than two class labels [START_REF] Zaffalon | Evaluating credal classifiers by utility-discounted predictive accuracy[END_REF].

The eclair classifier

As it is briefly presented in Section 1, the eclair approach is built in three steps: 1) the relabelling step, 2) the learning step, 3) and the reasoning step. This Section presents these three steps. More precisely, let us consider a data set of L learning samples (x l , θ l ) 1≤l≤L where for each l, 1 ≤ l ≤ L, x l ∈ X and θ l ∈ . The relabelling of a learning sample x l consists of assigning to it the smallest subsets of classes expressing the imprecision of its characteristics if it belongs to the overlapping or the isolated regions in the training data. We assume that the new subset of classes, denoted A l , associated to the sample x l necessarily contains the original class label θ l .

Once the relabelling step is performed, we obtain a new learning samples (x l , A l ) 1≤l≤L where for each l, provided by a method of point prediction quantifying the chance of each element from A to be the "true" label of x. The focal elements of m(.|x) are necessarily elements in A. Note also that the idea of using a method of point prediction in an imprecise classification task is also used in [START_REF] Coz | Learning nondeterministic classifiers[END_REF] and [START_REF] Vovk | Conformal prediction[END_REF]. In the following subsections the relabelling, the training and the reasoning steps are presented in detail.

1 ≤ l ≤ L, x l ∈ X and A l ∈ A. The set of interest A ⊆ 2 \ ∅ mentioned in the Subsection 2.

Relabelling step

The relabelling procedure is usually used to identify suspect samples with the intention to remove or relabel them into a concurrent, more appropriate class label [START_REF] Kanj | Editing training data for multi-label classification with the k-nearest neighbor rule[END_REF] [42] [START_REF] Muhlenbach | Identifying and handling mislabelled instances[END_REF]. Closer to our work are the relabelling procedures proposed in [START_REF] Jiao | Evidential editing k-nearest neighbor classifier[END_REF] and [START_REF] Zhang | A novel belief theoretic association rule mining based classifier for handling class label ambiguities[END_REF] that are taking advantage of the information provided by the k nearest neighbours (knn) of the treated sample. In [START_REF] Zhang | A novel belief theoretic association rule mining based classifier for handling class label ambiguities[END_REF] the sample is relabelled using the majority vote of the k nearest neighbours but this technique may not be effective when some neighbours of the sample are non-representative of their classes or when the sample belongs to an isolated region. In [START_REF] Jiao | Evidential editing k-nearest neighbor classifier[END_REF] an evidential relabelling is performed on the training data using the evidential k nearest neighbours (EKNN) [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF]. This evidential relabelling is not suitable for the implementation of the two other steps of eclair classifier where the partially labelled training samples are used to learn a point prediction for classification method.

Two new relabelling procedures are proposed in this paper as a generalisation of the one based on the knn of the sample. Both procedures are based on the posterior probability distribution provided by a method of point prediction for classification and the cross-validation technique. Indeed, knowing that the posterior probability distribution summarizes the information about the chances of each class to be the "true" class of a sample, one can use it to identify the subsets of classes that are candidates to be the new label of the sample.

Let us consider a sample x l from the learning dataset and a method of point prediction δ c . Using the leave-one-out technique, x l is removed from the learning data and its predicted class is δ c (x l ). We denote by p c (θ i |x l ) the posterior probability quantifying the chances of each class label θ i , i ∈ {1, . . . , n}, to be the "true" class of x l . Let us denote by A l the new label of x l . The first method, called the rank method, consists in including in A l the classes having a posterior probability at least equal to the one obtained by the true class θ l :

A l = {θ ∈ , p c (θ|x l ) ≥ p c (θ l |x l )}. (1)
Obviously, δ c (x l ) and θ l are in A l . In the most of cases, i.e., when data are perfect, A l = {δ c (x l )} = {θ l }. The second method, called the entropy method, is based on the Shannon entropy index and is detailed below. The Shannon entropy, also called entropy index denoted H , quantifies for a probability distribution the degree of perfection with which an outcome is pre-

dicted. If H(p c (.|x l )) = -n i=1 p c (θ i |x l ) log(p c (θ i |x l )) (only coefficients with p c (θ i |x l ) > 0 are considered) is close to 0 then
{θ 3 } { θ 3 } x 3 θ 1 0.1 0 0 .9 0 0 .325 {θ 1 , θ 3 } x 4 θ 1 0.2 0 0 .8 0 0 .5004 {θ 1 , θ 3 } { θ 1 , θ 3 } x 5 θ 2 0.2 0 .25 0.5 0 .05 1.165 {θ 2 , θ 3 } { θ 1 , θ 2 , θ 3 } the prediction from p c (.|x l ) is perfect while if H(p c (.|x l )
) is high the uncertainty about the predicted class for x l is also too high. The proposition of relabelling x l consists in fixing a threshold ρ of the entropy index beyond which the degree of uncertainty is considered too high. When the entropy is greater than ρ, the predicted class of x l is questionable. To simplify the notations, we introduce the following quantity related to the entropy index for a subset B ⊂ :

H B (p c (.|x l )) = -P c (B|x l ) log(P c (B|x l )) - θ i ∈ \B p c (θ i |x l ) log(p c (θ i |x l )), ( 2
)
where P c (.|x l ) is the probability measure associated to the probability distribution p c (.|x l ). The Equation ( 2) can be seen as the entropy index of a new probability distribution deduced from p c (.|x l ) where all the classes in B are considered as the same single class. Thus, the choice of the new label A l of x l depends on ρ, δ c (x l ) and p c (.|x l ). According to whether δ c (x l ) is equal to θ l or not, two thresholds can be considered and respectively denoted ρ 1 and ρ 2 . In the case where δ c (x l ) is θ l , the proposed new label A l is:

A l = A ρ 1 , if H(p c (.|x l )) > ρ 1 , {θ l } elsewhere. (3)
In the case where δ c (x l ) is different from θ l , the proposed new label A l is:

A l = {θ l } ∪ A ρ 2 , if H(p c (.|x l )) > ρ 2 , elsewhere, (4)
where

A ρ = argmin B⊂ {|B|, H B (p c (.|x l )) ≤ ρ},
is the smallest subset for which if all its classes are considered as the same, the new entropy index, H A ρ , is below the threshold ρ for p c (.|x l ).

In the case of the relabelling defined in Equation ( 3), the new label A l is composed initially by θ l and other classes are added until the new entropy H A ρ 1 becomes lower than ρ 1 and if A l contains more than one class, x l is considered as non-representative of the class θ l . While, in the case of the relabelling defined in Equation ( 4), x l is considered as nonrepresentative of the class θ l . If the entropy index is higher than ρ 2 , then x l is relabelled as the union of {θ l } and A ρ 2 ( A ρ 2 can contain θ l ). Otherwise, x l is considered as too ambiguous and is relabelled by .

Example 3.1. Let us consider five training samples and the corresponding posterior probability distribution presented in Table 1. These samples are part from the training samples (x l , θ l ) 1≤l≤L and | | = 4. Note that the entropy method is performed using the parameters ρ 1 = ρ 2 = 0.5.

More generally, from Equation (3) the more the entropy threshold ρ 1 is very small, i.e., close to 0, the more the samples are relabelled with subsets of classes and from Equation (4), the more the entropy threshold ρ 2 is high, the more the samples are relabelled with . Consequently, if a significant quantity of uncertain and ambiguous information is present in the training data, a large number of the samples are relabelled with subsets of classes. The choice of A l in Equations ( 3) and ( 4) is governed by the assumption considered in this work that the original class θ l of the sample is provided by a reliable source. Thus, this information is considered certain. Whereas, the measured characteristics of the sample are considered as potentially imperfect. It is certain that this choice leads to a loss of information in the training data mainly for the isolated samples and the samples belonging to overlapping regions, i.e., regions corresponding to boundaries between the classes. More precisely, adding another class to the original class θ l when constituting the new label A l impoverishes the original information. Nevertheless, as mentioned in the introduction of this paper, the proposition of this paper is designed to tackle decision problems involving sensitive applications where cautiousness is privileged. In such an application we assume that one prefers to be cautious than to bet on a class when the information is imperfect. A second assumption is made to simplify the approach which consists in also considering that the new label A l is provided by a reliable source, i.e., the relabelling procedure. However, a more general approach could cover the cases of non-reliable sources for the new labels. Such an approach could consist in assigning to each learning sample a mass function taking into account the reliability of the relabelling method.

Training step

Let us consider a learning samples (x l , A l ) 1≤l≤L where for each l, 1 ≤ l ≤ L, x l ∈ X and A l ∈ A where A is a subset of 2 \ ∅ that necessary includes all the singletons, i.e., for each θ ∈ , {θ} ∈ A. Let us consider a point prediction for classification method δ c . Each label A l ∈ A is a subset of , so some labels can have intersections. When training δ c on the data (x l , A l ) 1≤l≤L , the method considers that the elements of A are independent and the intersections of its elements are ignored in this step. Consequently, when dealing with a new sample x, δ c provides a posterior probability distribution p(.|x) : A → [0, 1] quantifying the chances of each element from A to be the "true" label of x. When x is classified as a non-singleton label A, this means that the true class of x belongs to A and that the available information of the training data and the characteristics observed on x do not allow more precise classification for x. As p(.|x) quantifies the chances of subsets of to contain the true class of x, it can be considered as a mass function m(.|x) : 2 → [0, 1] whose focal elements are included in A. Note that all the point prediction for classification methods are adapted to provide a posterior probability distribution when dealing with a new sample to classify. Furthermore, this step could as well be performed using the evidential k -N N rule for partially supervised data [START_REF] Zouhal | An evidence-theoretic k-nn rule with parameter optimization[END_REF] [START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF].

The reasoning step

This Section presents the reasoning step used in the eclair approach. It consists in associating a class or a subset of classes to a new sample x based on 1) a posterior mass function m(.|x) : 2 → [0, 1] where the set of focal elements F(.|x) is such that F(.|x) ⊆ A ⊆ 2 ; and 2) a gain matrix g : A × A → R + that associates to each pair (T x , B) of two elements in A the obtained gain when the prediction is A such that the "true" label of x is T x . Three methods are proposed to perform the reasoning step in our approach: 1) the 01 gain method which consists in predicting for x the subsets A ∈ A having the maximum mass function coefficient; 2) the pignistic ndc method which is similar to the decision step of ndc where the posterior probability distribution is replaced by the pignistic probability distribution obtained from m(.|x) (see Subsection 3.3.1); 3) the generalised ndc-based F β -score method that is presented in the Subsection 3.3.2. In the remainder of this section, the construction of the gain matrix in the case of the second and the third methods are presented. The gain matrix of the first method is obvious and is defined for (T x , B) ∈ A × A as follows:

g(T x , B) = g 01 (T x , B) = 1, if B = T x , 0 elsewhere. ( 5
)
Finally, in the Subsection 3.3.3, the objective function used as the criterion to choose the optimal subsets in A as the prediction for x is presented for the three methods.

ndc based F β -score

The gain matrix proposed in [START_REF] Coz | Learning nondeterministic classifiers[END_REF] is based on the F β measure which is function of the recall and precision measures introduced in the domain of information retrieval. More precisely, the gain obtained when predicting A ∈ A such that the true class label is θ ∈ (θ ∈ A) is given as follows:

F β (θ, A) = (1 + β 2 ) • recall(θ, A) • precision(θ, A) β 2 • precision(θ, A) + recall(θ, A) , ( 6
)
where the recall is defined as the proportion of relevant classes included in A and the precision is defined as the proportion of retrieved classes in A that are relevant. In the case of imprecise classification these measures are given as: recall(θ, A) = 1 A (θ) the proportion, i.e. 0% or 100%, of relevant classes that are included in A and precision(θ, A) = 1 A (θ)

|A| the proportion of retrieved classes in A that are relevant which correspond respectively to the discounted accuracy and imprecise accuracy defined in the Subsection 2.4. Thus, we have:

F β (θ, A) = (1 + β 2 ) • 1 A (θ) β 2 + |A| . ( 7
)
The gain matrix defined by the F β measure in Equation ( 7) is a trade-off between the imprecise accuracy, i.e., measure of cautiousness, and the discounted accuracy, i.e., measure of efficiency, where the parameter β is used to control the required levels of relevance and cautiousness.

Table 2

The quantification of the gain matrix using the function F g,β .

The predicted subset A

{θ 1 } { θ 2 } { θ 3 } { θ 1 , θ 2 } { θ 1 , θ 3 } { θ 2 , θ 3 } T x {θ 1 } 1 0 0 1 + β 2 2 + β 2 1 + β 2 2 + β 2 0 1 + β 2 3 + β 2 {θ 2 } 0 1 0 1 + β 2 2 + β 2 0 1 + β 2 2 + β 2 1 + β 2 3 + β 2 {θ 3 } 0 0 1 0 1 + β 2 2 + β 2 1 + β 2 2 + β 2 1 + β 2 3 + β 2 {θ 1 , θ 2 } 1 + β 2 1 + 2β 2 1 + β 2 1 + 2β 2 0 1 1 2 1 2 1 + β 2 3 /2 + β 2 {θ 1 , θ 3 } 1 + β 2 1 + 2β 2 0 1 + β 2 1 + 2β 2 1 2 1 1 2 1 + β 2 3 /2 + β 2 {θ 2 , θ 3 } 0 1 + β 2 1 + 2β 2 1 + β 2 1 + 2β 2 1 2 1 2 1 1 + β 2 3 /2 + β 2 1 + β 2 1 + 3β 2 1 + β 2 1 + 3β 2 1 + β 2 1 + 3β 2 1 + β 2 1 + 3 /2β 2 1 + β 2 1 + 3 /2β 2 1 + β 2 1 + 3 /2β 2 1

The generalised F β -score

The gain matrix defined in Equation ( 7) is based on the definition of the gain obtained in the case where only the chances of single class to be the true label of x are quantified. Considering that the chances of the element of A to be the "true" label of x are quantified by the mean of the mass function m(.|x), the Equation ( 7) defining the gain matrix needs to be extended. A subset A ∈ A is considered as the "true" label of x means that the true class of x belongs to A. More precisely, when the true class is known precisely, we check if the information "θ x = θ " is true or false, where θ x is the unknown true class of x and θ ∈ . In the case of imprecise information A, the information to check is "θ x ∈ A". In the approach proposed in this paper, we take advantage of the specialisation and generalisation errors proposed in the hierarchical classification [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF] to build the gain matrix. The generalisation gain is already exploited in Equation ( 7), i.e., rewarding the predictions that are efficient. We consider the same gain and we enrich it using the specialisation gain, i.e., rewarding the predictions that are cautious or penalize random choices in the predicted subsets of classes when the available information about the true class of x is imprecise. Let us consider that given the available information, the appropriate but unknown label to associate to the sample x is T x ∈ A. Each prediction A ∈ A such that A ⊂ T x should be penalized in the specialisation gain and each prediction B ∈ A such that B ⊇ T x should be penalized in the generalisation gain. The new gain matrix, denoted F g,β , F g,β : A × A → R + is then defined for a "truth" T x ∈ A, a prediction A ∈ A and a parameter β ≥ 0 as follows:

F g,β (T x , A) = (1 + β 2 )|A ∩ T x | β 2 |T x | + |A| . ( 8
)
In this case the definitions of the measures of recall and imprecision are extended as follows:

recall(T x , A) = |A∩T x | |T x | and precision(T x , A) = |A∩T x | |A| .
In other words, recall(T x , A) is the proportion of relevant class labels T x that are predicted and precision(T x , A) the proportion of the predicted class labels A that are relevant. Example 3.2. In the following an example, in the case of three classes = {θ 1 , θ 2 , θ 3 }, is given to show the quantification of the gain matrix especially to highlight the impact of specialisation and generalisation gains in Equation [START_REF] Chow | An optimum character recognition system using decision functions[END_REF]. As shown in Table 2, the first extreme case corresponds to the worst case that occurs when the "truth" T x does not intersect with the predicted subset A, i.e., T x ∩ A = ∅. In such a case the gain is minimal, i.e., F g,β (T x , A) = 0 regardless the value of β. The second extreme case occurs when T x = A and the gain is quantified as maximal F g,β (T x , A) = 1 regardless the value of β. Concerning the intermediate cases, the generalisation gain guarantee the same results as in Equation ( 7), i.e.,

F g,β (T x , A) = (1+β 2 ) 1 A (T x ) β 2 +|A|
(T x is a single class). The new gains capturing the specialization gain can be seen in the cases where A ⊂ T x . For instance, if A = {θ 1 } and T x = {θ 1 , θ 2 }, the associated gain is F g,β ({θ 1 , θ 2 }, {θ 1 }) = 1 + β 2 1 + 2β 2 and in the case where T x = , the gain is F g,β ( ,

{θ 1 }) = 1 + β 2 1 + 3 β 2 .
Thus, the larger the "truth" containing the prediction the smaller the gain function rewarding the good predictions. Also, with the new gain matrix, predictions containing more than one element can receive the maximal gain 1 in the case where they are equal to the "truth" T x which is not possible when restricting the "truth" to the single classes. More generally, the value of β can be used to control the cautiousness and the relevance:

• when β is small, the prediction that is not efficient is penalised. Especially for β = 0, F β boils down to precision.

• when β is large, the prediction that is not cautious is penalised. Especially for β → ∞, F β tends towards recall.

The objective function

Finally, the objective function used as the criterion to choose the optimal subsets in A as the prediction for x is the expected gain function based on the gain matrix defined for each method and the posterior mass function. For the 01 gain method, the expected gain EG( A|x) when choosing the imprecise prediction A ∈ A for x is:

EG( A|x) := EG 01 (A|x) = T x ∈A m(T x |x) • g 01 (T x , A) = m(T x |x), (9)
where the gain matrix g 01 is defined in Equation ( 5). In the case of the pignistic ndc method, the expected gain is defined as follows for A ∈ A:

EG( A|x) := EG β (A|x) = θ x ∈ pig m (T x |x) • F β (θ x , A), ( 10
)
where the gain matrix F β is defined in Equation ( 7). The expected gain for the generalised F β -score based method is a generalisation of the expected gain defined in Equation ( 9) and is defined as follows for A ∈ A:

EG( A|x) := EG gβ (A|x) = T x ∈A m(T x |x) • F g,β (T x , A), ( 11
)
where the gain matrix F g,β is defined in Equation ( 8). Finally, for the three methods, the eclair imprecise prediction δ eclair

β (x)
for the sample x is given as:

δ eclair β (x) = argmax A∈A EG( A|x). ( 12
)

Discussion

The proposed classifiers based on the eclair approach are comparable to the approaches of the state of the art on some aspects. On the one hand, they are close to the approaches of the hierarchical classification related to the idea of the imprecise or partial labelling of the training data and close to the approaches based on the imprecise probabilities concerning the representation of imprecision [START_REF] Zaffalon | Statistical inference of the naive credal classifier[END_REF]. On the other hand, they are close to those using a gain matrix based on the F β score to model the trade-off between cautiousness and efficiency [START_REF] Coz | Learning nondeterministic classifiers[END_REF]. However, the computational complexity of the eclair classifiers and ncc classifier, as for any approach representing imprecision in the data, can be very high. Indeed, if n = | | is very large and |A| n, the computational complexity of the reasoning step of the eclair classifiers becomes very high, i.e., O (|A| 2 ), at worst exponential and at best quadratic. The computational complexity is lower when the gain function is 01, i.e., O (|A|), or when the gain function is based on the pignistic probability distribution, i.e., O (n • |A|).

These two last types of classifiers can be preferred when n is very large. The ndc classifier has the lowest computational complexity, i.e., at worst O (n) [START_REF] Coz | Learning nondeterministic classifiers[END_REF], and the ncc one is quadratic, i.e., O (n 2n) [START_REF] Zaffalon | Statistical inference of the naive credal classifier[END_REF]. Furthermore, the imprecise predictions provided by the eclair classifiers are based on the maximisation of the expected gain where the chances are quantified by the posterior mass function and the matrix gain is built using the F β score. For other choices, some criteria can be found in [START_REF] Ma | Partial classification in the belief function framework[END_REF] that could be used to decide on the imprecise classification when the information concerning the possible states of nature is presented by a mass function.

Illustration and comparisons

In this illustration Section we present two parts. The first part is dedicated to analysing the imprecise classifiers' results on a simulated data and the second part presents the comparisons on the UCI data benchmark. Table 3 summarises some information about the methods of point prediction for classification and the imprecise classifiers that are involved in this section. Note that all the implementations are performed using R packages with the default parameters for the methods of point prediction. Note also that for the illustrations where the parameters ρ 1 and ρ 2 involved in the entropy based relabelling method are considered equal, they are both denoted ρ. Furthermore, in the studied data, some new labels obtained from the relabelling step could be less represented in the learning data set so we are faced with an imbalanced data problem. To deal with this problem, the Synthetic Minority Over-sampling Technique (SMOTE) [START_REF] Chawla | Smote: synthetic minority over-sampling technique[END_REF], which consists in creating synthetic examples to increase the representativeness of minority class labels, is used.

Illustration using simulated data

In this first illustration, a simulated data for three classes a, b, and c is considered. For each class 500 training samples of a bivariate Gaussian distribution are considered: N (μ a = (0.2, 0.65), a = 0.01I 2 ) for the class a, N (μ b = (0.5, 0.9), b = 0.01I 2 ) for the class b, and N (μ c = (0.8, 0.6), c = 0.01I 2 ) for the class c. First, the results of the relabelling procedure are presented. Table 4 and Fig. 1 give the resulting new labels for four methods: method rank, method entropy with ρ = 0.2, ρ = 0.5, and ρ = 0.7. Note that, for the four methods, the logistic classifier is used to perform cross-validation. The rank method relabels few samples compared to the entropy methods which can be explained by the fact that in most cases the obtained posterior probability gives the maximum value to the true class of the sample. In such cases the rank method does not relabel the samples whereas with the entropy methods, even if this situation is encountered, the samples are relabelled when the entropy is high. As one can expect, with the entropy methods a large number of samples are relabelled when ρ decreases. One can see in Fig. 1 that the relabelled samples with a subset of two classes constitute a large boundary between the two original classes. It is more obvious when ρ = 0.2 for the subsets {a, b} and {b, c}. All the samples that are on the wrong side of the boundary are relabelled with the whole set {a, b, c}. In the case of a high entropy threshold, all the samples, where the posterior probability does not give the maximum value to the true class, are relabelled by the whole set, {a, b, c} (see Equation ( 4)).

In order to evaluate the performance of the imprecise classifiers built from the considered training data, a dataset of 50 samples for each class label are generated using the same bivariate Gaussian distributions with a Gaussian noise N (μ = (0, 0), = 0.001I 2 ). Note that, again the logistic classifier is used to provide the posterior probability distribution for eclair rank, eclair entropy and ndc. Moreover, several values of the parameters presented in Table 3 are tested and the results are shown in Table 5. Note that, for the considered testing data, the methods of point prediction obtain the following accuracies: logistic, ann: 94.67%; svm, rfc, eknn: 95.33%; nbc, lda, cart: 96%; and knn: 96.67%.

As one can see in Table 5, the imprecise classifiers have performances close to those of the point prediction classifiers for some fixed parameters but in these cases they are not cautious enough, the eclair and ndc performances are better compared to those of ncc. Furthermore, eclair and ndc can reach very good performances for some values of β. For instance, eclair rank GFB and eclair entropy GFB have the best accuracy, u 65 and u 50 performances for small values of β while ndc has good imprecise accuracy and u 80 performances. If one wants to be very cautious, it is better to choose eclair entropy classifiers as they can provide predictions with 100% good imprecise predictions for some parameters but in return they avoid precise predictions for several samples and then have a low accuracy performance. Generally, ndc and eclair classifiers give good average performances (see the last column of Table 5). This shows the trade-off that those imprecise classifiers are able to guarantee between cautiousness and efficiency.

To see the effect of these hyper-parameters more closely, Figs. 2 and3 show the performances of the eclair classifiers related to two different point prediction methods and the hyper-parameters ρ and β using the same simulated data. Fig. 2 shows the results obtained when using the svm point prediction method while Fig. 3 shows the results obtained when using the logistic point prediction method. The first remark that can be made about the two figures is that regardless the performances of the two point prediction methods related to those data, the behaviours of the five performance measure curves are the same in the two figures. For that reason only Fig. 2 is commented. The first classifier studied is the eclair entropy 01 classifier presented in the part "ENTR.01" in the Fig. 2 that has only the entropy threshold ρ as hyper-parameter (ρ 1 = ρ and ρ 2 = ρ -0.05). As expected, when ρ is very close to 0 the number of relabelled samples is very large and the size of the label subsets is also large thus the chance to contain the true class is close to 1, i.e. imprecise accuracy performance close to 100%, and the chance to predict the true class of a sample is low, i.e., accuracy performance is low.

The performances measures u 50 , u 65 , u 80 and the accuracy performance increase until ρ reaches a value ρ * close to 0.25 while imprecise accuracy performance is rather constant. Above the value ρ * all the performance measures curves become almost constant. Concerning the other three parts of Fig. 2 "RANK.PIG", "ENTR.PIG" and "ENTR.GFB" the hyper-parameter ρ is fixed (ρ 1 = 0.25 and ρ 2 = 0.2) and the hyper-parameter β is considered as variable. For those classifiers, the effect of the values of the hyper-parameter β on the performance measures is important. Indeed, with "ENTR.GFB" the imprecise accuracy reaches the performance close to 100% for values of β that are close to 0 while the accuracy decreases quickly.

This behaviour is the same for the two other classifiers "RANG.PIG" and "ENTR.PIG" but the decrease and the increase in performance is lower. Thus the advantage of the "ENTR.GFB" classifier is to offer an optimal cautiousness with an accuracy very high, i.e., β is close to 0.

To highlight the good or bad predictions of the imprecise classifiers for some specific samples that are in overlapping or isolated regions, Fig. 4 shows the predictions for each sample of the test data provided by some imprecise classifiers. Ten samples among the 150 samples seem to be difficult to classify, i.e., the methods of point prediction fail to correctly classify them. The ten difficult samples are labelled by their numbers in Fig. 4. It can be noted that with β = 0.1 for the eclair rank GFB classifier, three samples have precise and correct predictions, five have precise and incorrect predictions, and two have "correct", i.e., contain the true class, imprecise predictions with two classes. The three other classifiers of Fig. 4 are more cautious but less efficient. The classifiers ncc (s = 0.08) and ndc (β = 3) provide less number of imprecise predictions than eclair entropy (ρ = 0.5 and β = 1). eclair entropy (ρ = 0.5 and β = 1) is the only one that does not provide incorrect predictions.

Comparing the imprecise classifiers' performances using UCI data

The second illustration concerns the comparison of the performances of four imprecise classifiers: ndc, ncc, eclair rank GFB and eclair entropy GFB using 11 UCI data and the same performances measures used in the first illustration of Subsection 4.1 (see the definition in Section 2.4). A brief description of the selected UCI data is given in Table 6.

Each of those classifiers has hyper parameters that should be optimized and some of them use a method of point prediction. Table 7 presents a summary of those parameters, the steps in which they are involved and the sets from which they are selected. Note that the methods of point prediction are selected from the list presented in Table 3: PRCL={nbc, knn, eknn, cart, rfc, lda, svm, ann and logistic }.

As the aim is to build a classifier that offers the best trade-off between cautiousness and efficiency, the criterion that is used to optimize the parameter of the four classifier is the average of the five measures of performance: accuracy, imprecise accuracy, u 80 , u 65 and u 50 . The experimentation procedure is conduct as follows. Each dataset is split randomly 10 times to obtain a learning set (80%) and a testing set (20%). The parameters are optimized, each time, using the cross-validation technique on the learning dataset. Each cell in Table 8 presents the average performance of the classifiers on the test data of the 10 splits. As shown in Table 8, the most important observation is that even if some samples are classified with subsets of classes, the accuracy performance of the imprecise classifiers remains close to that of the methods of point prediction. The exception is the ncc classifier that has accuracy performances far from the best ones. Indeed, ncc is too cautious and in some situations, it has the best imprecise accuracy performances. It is the case for the Wine and PID data. As mentioned Fig. 2. eclair classifiers' performances using svm point prediction method. -ENTR.01: eclair classifier using the entropy relabelling method (ρ 1 = ρ, ρ 2 = ρ -0.05) and the 01 gain reasoning method. -RANK.PIG: eclair classifier using the rank relabelling method and the pignistic ndc reasoning method. -ENTR.PIG: eclair classifier using the entropy relabelling method (ρ 1 = 0.25, ρ 2 = 0.2) and the pignistic ndc reasoning method. -ENTR.GFB: eclair classifier using the entropy relabelling method (ρ 1 = 0.25, ρ 2 = 0.2) and the generalised F β score reasoning method. (For interpretation of the colours in the figure(s), the reader is referred to the web version of this article.)

∈ P RC L β ∈ [0, 3] ncc - I D M ( s ∈ [10 -10 , 2]) - eclair rank GFB cl ∈ P RC L cl β ∈ [0, 3] eclair entropy GFB cl ∈ P RC L cl β ∈ [0, 3] ρ ∈ [0.1, 1]
Fig. 3. eclair classifiers' performances using logistic point prediction method. -ENTR.01: eclair classifier using the entropy relabelling method (ρ 1 = ρ, ρ 2 = ρ -0.05) and the 01 gain reasoning method. -RANK.PIG: eclair classifier using the rank relabelling method and the pignistic ndc reasoning method. -ENTR.PIG: eclair classifier using the entropy relabelling method (ρ 1 = 0.25, ρ 2 = 0.2) and the pignistic ndc reasoning method. -ENTR.GFB: eclair classifier using the entropy relabelling method (ρ 1 = 0.25, ρ 2 = 0.2) and the generalised F β score reasoning method. (For interpretation of the colours in the figure(s), the reader is referred to the web version of this article.) in the case of the simulated data of Subsection 4.1, eclair classifiers obtain accuracy scores close to the best ones of the methods of point prediction and the imprecise predictions of the difficult samples are all almost as good for several datasets. This can be seen for the following data: Iris, BC, IS, DBT, Seeds, Forest and Ecoli. Generally, the ndc and eclair classifiers obtain close results except for the u 50 measure where ndc obtains slightly better performances.

Furthermore, we can also compare these results to those of the imprecise classifier named preorder in [START_REF] Nguyen | Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty[END_REF]. As it is mentioned in the introduction Section, this classifier constructs a binary relation on the set of classes and the subset of the non-dominated classes is considered as the prediction for the new sample. The dominance relation is based on different quantifications of uncertainties. The authors conducted the experiments for some UCI data under the same conditions as those considered in our experiments but only two measures are used: u 80 and u 65 . Table 9 presents the comparisons between the performances of preorder reported in [START_REF] Nguyen | Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty[END_REF] and the performances of eclair classifiers and shows that except the "Forest" data, the eclair classifiers have the best performances on the other five datasets. In addition, we tested the five measures with a version of eclair where the training step is performed using the evidential k-nearest neighbourhoods EKNN with partially labelled samples [START_REF] Zouhal | An evidence-theoretic k-nn rule with parameter optimization[END_REF] [START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF]. Unfortunately, the obtained performances of this version fall far short of what is measured for the other versions of the eclair classifiers.

Conclusion

This paper proposes an approach for imprecise classification based on an imprecise relabelling of the training data and a generalisation of the F β score within the framework of belief functions. Several imprecise classifiers can be built from the approach depending on the choice of the method of relabelling and the choice of the gain function involved in the reasoning step. Some choices appear preferable as they have less hyper parameters, i.e., eclair rank 01, but they do not obtain the best performances. Two illustrations are proposed to compare the proposed approach to the state-of-the-art approaches. First, simulated data are used to show how those classifiers deal with difficult samples. The eclair classifiers offer the best compromise between cautiousness and efficiency on this data. Second, the comparisons are conducted using the UCI data. The results show that the eclair classifiers have accuracy performances close to those of the point prediction classifiers while their performances on the other measures of cautiousness remain very competitive. Concerning the hyper parameters, the eclair classifiers can be improved by making them free from the methods of point prediction. However, the other hyper parameters are required because during the relabelling step they enable the detection of difficult samples in the training data and those involved in the reasoning step enable control of the trade-off between cautiousness and efficiency. Those parameters can be considered as user-control parameters whose values depend on the targeted application.

  1 is constituted by the distinct labels A l of the training data set. The learning step then consists in training a learning algorithm of point prediction for classification to recognize the labels in A. Finally, using the reasoning step we assign to a new sample x an element in A based on 1) the posterior mass function m(.|x); 2) and an appropriate gain matrix representing the trade-off between cautiousness and efficiency. Note that the mass function m(.|x) is obtained from the posterior probability mass function p(.|x) : A → [0, 1]

Fig. 1 .

 1 Fig. 1. Relabelling the training data using two methods with different parameters. (For interpretation of the colours in the figure(s), the reader is referred to the web version of this article.)

Fig. 4 .

 4 Fig. 4. The predictions of four selected imprecise classifiers: a large size is given to the points symbols representing predictions that are errors or imprecise. (For interpretation of the colours in the figure(s), the reader is referred to the web version of this article.)

Table 1

 1 The relabelling of some samples using the two methods.

	sample	class	posterior probability			H	relabelling
			θ 1	θ 2	θ 3	θ 4		rank method	entropy method
	x 1	θ 4	0.2	0 .25	0.25	0.3	1 .376	{θ 4 }
	x 2	θ 3	0	0	0 .99	0.01	0.056

Table 3

 3 The classifiers involved in the illustrations.

	use a method

Table 4

 4 The new labels after relabelling.

		{a}	{b}	{a,b}	{c}	{a,c}	{b,c}	{a,b,c}
	Rank method	481	482	31	494	0	12	0
	Entropy method (ρ = 0.2)	430	392	132	465	0	69	12
	Entropy method (ρ = 0.5)	468	444	61	482	0	28	17
	Entropy method (ρ = 0.7)	481	480	0	493	0	2	44

Table 5

 5 The performances of the imprecise classifiers for different parameters.

			Performances
		Parameters	accuracy	imprAcc	u 80	u 65	u 50	average
	eclair rank 01	-	88.67	98.67	96.67	95.17	93.67	94.57
	eclair rank PIG	β ∈ [0, 0.17]	96	96	96	96	96	96
		β = 0.5	94	97.33	96.67	96.17	95.67	95.97
		β = 2.1	86	98.67	96.13	94.23	92.33	93.47
		β = 3	83.33	98.67	95.6	93.3	91	92.38
	eclair rank GFB	β ∈ [0, 0.08]	96	96	96	96	96	96
		β = 0.1	95.33	96.67	96.4	96.2	96	96.12
		β = 0.5	91.33	98	96.67	95.67	94.67	95.27
		β = 2.1	86	98.67	96.13	94.23	92.33	93.47
		β = 3	83.33	98.67	95.6	93.3	91	92.38
	eclair entropy 01	ρ = 0.2	8 1 . 3 3	100	95.47	92.73	90	91.91
		ρ = 0.5	86.67	100	96.27	94.36	92.44	93.95
		ρ = 0.6	86.67	99.33	95.6	93.8	92	93.48
		ρ = 0.7	87.33	99.33	94.53	92.93	91.33	93.09
	eclair entropy PIG	ρ = 0.2, β ∈ [0, 0.09]	95.33	95.33	95.33	95.33	95.33	95.33
		ρ = 0.2, β = 0.5	90	97.33	95.87	94.77	93.67	94.33
		ρ = 0.5, β ∈ [0, 0.21]	94.67	94.67	94.67	94.67	94.67	94.67
		ρ = 0.5, β = 0.5	91.33	97.33	96	95.11	94.22	94.8
		ρ = 0.5, β = 1.3	8 6	100	96.8	94.73	92.67	94.04
		ρ = 0.5, β = 2	8 1 . 3 3	100	95.07	92.37	89.67	91.69
	eclair entropy GFB	ρ = 0.2, β ∈ [0, 0.01]	96	96	96	96	96	96
		ρ = 0.2, β = 0.5	88	99.33	96.67	95	93.33	94.47
		ρ = 0.5, β ∈ [0, 0.1]	94.67	94.67	94.67	94.67	94.67	94.67
		ρ = 0.5, β = 1	84.00	100	96	93.67	91.33	93
		ρ = 0.5, β = 2	76.67	100	93.2	89.88	86.56	89.26
		ρ = 0.6, β = 0.2	93.33	96.67	96	95.5	95	95.3
		ρ = 0.7, β = 0.2	94	95.33	94.8	94.62	94.44	94.64
	ncc	s = 0.1	83.33	96.67	93.07	91.14	89.22	90.69
		s = 0.08	88.00	96.67	94.13	92.90	91.67	92.67
		s = 0.05	88.0	96.0	94.4	93.2	92.0	92.72
		s = 0.01	91.33	94.00	93.47	93.07	92.67	92.91
		s = 0.005	91.33	92.00	91.87	91.77	91.67	91.73
		s = 0.0001	92	92	92	92	92	92
	ndc	β ∈ [0, 0.36]	94.67	94.67	94.67	94.67	94.67	94.67
		β = 0.37	94.67	95.33	95.20	95.1	95	95.06
		β = 0.5	94	96	95.6	95.3	95	95.18
		β = 2.1	92	98	96.67	95.78	94.89	95.47
		β = 3	90.67	99.33	97.47	96.18	94.89	95.71
		β = 4	88.67	99.33	97.07	95.48	93.89	94.89
		β = 5	88.67	99.33	96.93	95.36	93.78	94.81

Table 6

 6 Information about the considered UCI data.

	nom	# instances	# inputs	# class	abbreviation
	Iris	150	4	3	Iris
	Breast Cancer	683	9	2	BC
	Wine	178	13	3	Wine
	Ionosphere	351	32	2	IS
	Diabetes	145	5	3	DBT
	Glass	214	9	6	Glass
	Pima Indians Diabetes	392	9	2	PID
	Sonar	208	60	2	Sonar
	Seeds	210	7	3	Seeds
	Forest	523	27	4	Forest
	Ecoli	327	5	5	Ecoli

Table 7

 7 The hyper parameters involved in the models of the imprecise classifiers.

	classifier	relabelling	posterior probabilities	reasoning step
	ndc	-	cl

Table 8

 8 The imprecise classifiers' performances on the UCI data.

			Iris	BC	Wine	IS	DBT	Glass	PID	Sonar	Seeds	Forest	Ecoli
	Accuracy	svm	95.67	96.15	98.53	94.57	85	68.5	7 5 .51	84.15	94	90.19	90
		rfc	96	97.19	98.24	93.86	98.93	77	79.10	83.9	9 2 .62	91.17	90.16
		lda	97.67	95.85	99.41	85.29	91.07	62.5	7 9 .1	7 0 .73	97.38	89	90.62
		nbc	96	95.93	97.35	83.71	93.21	38	77.69	67.32	92.86	87.28	88.91
		knn	96.33	96.59	65.59	83.71	91.07	61.5	7 4 .36	63.66	90.48	90	89.53
		cart	94	94.81	91.76	89	97.86	70.25	77.18	73.17	92.38	87.96	84.69
		ann	96.33	94.67	90	86.14	95.36	64.75	78.08	80	95.48	86.89	81.09
		eknn	97	96.67	72.06	92.86	92.14	67	72.95	81.46	87.62	91.55	89.84
		logistic	96	96.59	93.82	83.43	96.07	64.25	79.62	71.71	95.71	87.77	89.53
		eclair rank GFB	96	94.6	9 7 .35	92.28	98.21	65.25	70.51	67.32	94.04	89.7	8 8 .12
		eclair entropy GFB	96	96.22	97.94	91.71	95.71	52.5	6 6 .8	7 3	9 4 .04	88.44	87.34
		ndc	96.67	96.51	97.64	94.28	98.93	72	73.84	76.58	96.66	89.41	88.12
		ncc	91	95.55	88.82	62.57	87.85	23.25	15.76	30.97	83.57	24.85	38.28
	imprAcc	eclair rank GFB	96	97.85	97.35	94.57	98.93	78.25	84.49	94.88	97.86	90.98	90.62
		eclair entropy GFB	98.33	96.88	97.94	95.57	98.21	77.5	8 6 .02	89.51	98.1	90.87	89.53
		ndc	96.67	96.88	97.94	95.42	98.93	80.5	82.43	88.3	9 7 .85	91.84	92.5
		ncc	96.67	96	99.11	87.14	95.35	65.5	95.38	90.48	94.76	87.57	85
	u80	eclair rank GFB	96	97.2	97.35	94.11	98.64	75.16	81.7	89.36	97.1	9 0 .65	89.8
		eclair entropy GFB	97.86	96.75	97.94	94.8	9 7 .21	69.1	82.18	86.2	9 6 .57	90.32	89.09
		ndc	96.67	96.81	97.88	95.2	98.93	78.75	80.71	85.95	97.62	91.26	91.62
		ncc	95.4	9 5 .91	95.47	82.2	9 3 .57	39.84	79.46	78.58	92.33	71.23	72.24
	u65	eclair rank GFB	96	96.75	97.35	93.78	98.54	73.27	79.6	85.23	96.52	90.47	89.47
		eclair entropy GFB	97.51	96.65	97.94	94.22	96.88	65.82	79.3	8 3 .7	9 6 .02	89.96	88.76
		ndc	96.67	96.75	97.83	95.02	98.93	77.48	79.43	84.19	97.44	90.91	90.96
		ncc	94.56	95.84	94.05	78.54	92.47	35.88	67.51	69.65	90.67	62.20	65.58
	u50	eclair rank GFB	96	96.2	9 7 .35	93.43	98.45	71.37	77.5	8 1 .1	9 5 .95	90.3	8 9 .14
		eclair entropy GFB	97.16	96.55	97.94	93.64	96.54	62.54	76.41	81.22	95.47	89.61	88.43
		ndc	96.67	96.7	97.79	94.85	98.93	76.2	78.14	82.44	97.26	90.55	90.31
		ncc	93.72	95.77	92.64	74.85	91.36	31.93	55.57	60.73	89	53.17	58.92

Table 9

 9 Comparison of the performances of preorder classifier reported in[START_REF] Nguyen | Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty[END_REF] and eclair classifiers' performances on some UCI data.

			Iris	Wine	Glass	Seeds	Forest	Ecoli
	u80	eclair rank GFB	96	97.35	75.16	97.1	90.65	89.8
		eclair entropy GFB	97.86	97.94	69.1	96.57	90.32	89.09
		preorder	90.45	95.89	67.32	92.15	92.15	80.66
	u65	eclair rank GFB	96	97.35	73.27	96.52	90.47	89.47
		eclair entropy GFB	97.51	97.94	65.82	96.02	89.96	88.76
		preorder	83.29	93.18	57.24	88.16	88.82	75.25

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.