Ludovic Liétard
email: ludovic.lietard@univ-rennes1.fr

Nouredine Tamani
email: tamani@enssat.fr

Daniel Rocacher
email: rocacher@enssat.fr

Fuzzy Bipolar Conditions of Type "or else"

Keywords: Flexible querying, bipolar conditions, negation of bipolar conditions, fuzzy sets theory

Previously studied fuzzy bipolar conditions of type "and if possible" are made of a mandatory condition c and an optional condition w. They allow expressing complex preferences of a conjunctive nature. We define in this paper, a new kind of fuzzy bipolar conditions of the form "or else" which express complex preferences of a disjunctive nature. We show that the "or else" form can be used as a negation operator of the "and if possible" form and vice versa. We also show that these both forms are compatible and, therefore, fuzzy bipolar conditions of both types can be used together in the same bipolar query.

I. INTRODUCTION

Flexible querying allows expressing preferences in user queries, which are addressed to regular databases and deliver a set of ranked answers from the most to the least preferred. In this context, the fuzzy sets theory [START_REF] Zadeh | Fuzzy sets[END_REF] provide a general framework for the expression and the interpretation of queries involving preferences modelled by fuzzy predicates (or conditions). It is also possible to consider fuzzy bipolar conditions to model complex preferences [START_REF] Dubois | Bipolarity in flexible querying[END_REF], [START_REF] Dubois | An introduction to bipolar representations of information and preference[END_REF]. In this context, a bipolar condition is made of two components: a constraint and a wish. More precisely, for the expression of user preferences, we rely on fuzzy bipolar conditions in which the constraint and the wish are defined by fuzzy sets. We define then a bipolar query as a query that involves bipolar conditions.

Several interpretations have been introduced for the evaluation of queries involving fuzzy bipolar conditions of type "and if possible" (see [START_REF] Dubois | Bipolarity in flexible querying[END_REF], [START_REF] Dubois | An introduction to bipolar representations of information and preference[END_REF], [START_REF] Tré | Dealing with positive and negative query criteria in fuzzy database quering bipolar satisfaction degrees[END_REF], [START_REF] Zadrozny | Bipolar queries using various interpretations of logical connectives[END_REF], [START_REF] Zadrozny | Bipolar queries: An approach and its various interpretations[END_REF]). The algebraic operators (selection, projection, join, union, intersection) have also been extended to fuzzy bipolar conditions [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF], [START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] of type "and if possible". It is therefore possible to express the usual query statements over relational bipolar relations, but in order to build a bipolar relational algebra, it stills to define a global operator for the negation of bipolar conditions. Several operators have been proposed in the literature but none of them fits in well with the framework of flexible querying.

We introduce in this paper a new kind of fuzzy bipolar conditions noted "or else", which expresses fuzzy bipolar conditions of a disjunctive nature. Its definition and properties allow us to define a negation operator of fuzzy bipolar conditions of the form "and if possible".

We show that each of these forms of bipolarity expresses a negation form of one another. These forms of bipolarity are also compatible in the sense that it is possible to mix in the same bipolar queries an "and if possible" fuzzy bipolar condition with an "or else" fuzzy bipolar condition.

The remainder of this paper is organized as follows. In section II, a short reminder about fuzzy bipolar conditions of type "and if possible" is introduced. In section III, we sum up different negation operators of fuzzy bipolar conditions of the form "and if possible", which have been proposed. Section IV is dedicated to our contribution; we introduce, firstly, the definition of fuzzy bipolar conditions of type "or else" and we show, secondly, that such fuzzy bipolar conditions can be used to define a negation operator for fuzzy bipolar conditions of type "and if possible". In section V, we show that these forms of fuzzy bipolar conditions are mutually compatible and can be used together in the same bipolar query. Section VI recalls our contribution and draws some lines for future works.

II. FUZZY BIPOLAR CONDITIONS

A bipolar condition is an association of a negative condition (negative pole) and positive condition (positive pole). In this paper, a bipolar condition is made of two conditions defined on the same universe: i) a constraint c, which describes the set of acceptable elements, ii) a wish w which defines the set of desired or wished elements. The negation of c is the set of rejected elements since it describes non-acceptable elements. Since it is not coherent to wish a rejected element, the following property of coherence holds: w ⊆ c.

In addition, condition c is mandatory since an element which does not satisfy c is rejected; ¬c is then considered as the negative pole of the bipolar condition. Condition w is optional because its non-satisfaction does not automatically mean the rejection; w is then considered as the positive pole of the bipolar condition. In this paper, a bipolar condition is noted (c, w) and means, "to satisfy c and if possible to satisfy w" [START_REF] Dubois | Bipolarity in flexible querying[END_REF], [START_REF] Dubois | An introduction to bipolar representations of information and preference[END_REF].

If c and w are boolean conditions, the satisfaction with respect to (c, w) is an ordered pair from {0, 1} 2 . When querying a database with such a condition, tuples satisfying the constraint and the wish are returned in priority to the user. If such answers do not exist, tuples satisfying only the constraint are delivered.

If c and w are fuzzy conditions (defined on the universe U), the property of coherence becomes: ∀u ∈ U, µ w (u) ≤ µ c (u).

The satisfaction with respect to (c, w) is an ordered pair of degrees from the unit interval [0, 1] 2 . Each element u from U is then attached with a pair of grades (µ c (u), µ w (u)) that expresses the degrees of its satisfaction respectively to the constraint and the wish.

When querying a relation R with a fuzzy bipolar condition, each tuple t from R is then attached with a pair of grades (µ c (t), µ w (t)) that expresses the degrees of its satisfaction respectively to the constraint c and the wish w (and a so-called fuzzy bipolar relation is obtained). A tuple t is then denoted (µ c , µ w )/t. Any tuple u such that µ c (u) = 0 does not belong to the fuzzy bipolar relation.

In such a context, tuples cannot be ranked from the most preferred to the least preferred using an aggregation of µ c and µ w because the constraint and the wish are not commensurable. However, they can be ranked using the lexicographical order: t 1 is preferred to t 2 if and only if:

µ c (t 1 ) > µ c (t 2 ) or (µ c (t 1 ) = µ c (t 2 ) ∧ µ w (t 1 ) > µ w (t 2 )), which is noted (µ c (t 1 ), µ w (t 1 )) > (µ c (t 2 ), µ w (t 2 )).
In this case, the satisfaction with respect to the constraint is firstly used to discriminate among answers (the constraint being mandatory). The satisfactions with respect to the wish being optional, they can only be used to discriminate among answers having the same evaluation with respect to the constraint. A total order is then obtained on µ c and µ w (with (1, 1) as the greatest element and (0, 0) as the least element).

Based on the lexicographical order, the lmin and lmax operators [START_REF] Liétard | On the definition of extended norms and conorms to aggregate fuzzy bipolar conditions[END_REF], [START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] are introduced in order to define the conjunction (resp. intersection) and the disjunction (resp. union) of bipolar conditions (resp. relations). They are respectively defined as follows:

([0, 1] × [0, 1]) 2 → [0, 1] × [0, 1] ((µ, η), (µ , η )) → lmin((µ, η), (µ , η )) = (1)
(µ, η) i f µ < µ ∨ (µ = µ ∧ η < η ), (µ , η ) else. ([0, 1] × [0, 1]) 2 → [0, 1] × [0, 1] ((µ, η), (µ , η )) → lmax((µ, η), (µ , η )) = (2)
(µ, η) i f µ > µ ∨ (µ = µ ∧ η > η ), (µ , η ) else.
The lmin (resp. lmax) operator is commutative, associative, idempotent and monotonic. The pair of grades (1, 1) is the neutral (resp. absorbing) element of the operator lmin (resp. lmax) and the pair (0, 0) is the absorbing (resp. neutral) element of the operator lmin (resp. lmax).

Remark 1: Fuzzy bipolar conditions generalize fuzzy conditions since a fuzzy condition C can be rewritten (C,C) to express "to satisfy C and if possible to satisfy C". As a consequence, a fuzzy relation R is a particular case of a fuzzy bipolar relation such that ∀t ∈ R, µ R (t) = µ c (t) = µ w (t). Therefore, it is easy to demonstrate that the lmin (resp. lmax) generalizes the triangular norm min (resp. the triangular conorm max).

More formally, bipolar conditions of the form "C and if possible W " can be defined with the following properties:

1) ¬C corresponds to the rejection (C denotes acceptable elements), 2) W corresponds to the optimal values, 3) The acceptability condition C is more important than the optimality (the condition W ), 4) The set of optimal values is included in the set of acceptable values (W ⊆ C).

Remark 2: The property 3 means that the non-rejection (or the acceptability) is more important than the optimality, therefore, the lexicographical order can be used to rank between elements.

III. THE NEGATION OF FUZZY BIPOLAR CONDITIONS

Many works have been carried out to define a negation operator of fuzzy bipolar conditions.

To be consistent, any negation operator must verify the following properties, which have been introduced in [START_REF] Bosc | A propos de la négation de conditions bipolaires floues. on the negation of fuzzy bipolar conditions[END_REF]:

Let (C ,W ) denotes the negation of a fuzzy bipolar condition (C,W ).

a) Property 1. Order reversing: The negation operator must deliver tuples in reverse order in which they are delivered by the condition (C,W ):

∀t 1 ,t 2 , (µ C (t 1 ), µ W (t 1 )) < (µ C (t 2 ), µ W (t 2 )) ⇔ (µ C (t 2 ), µ W (t 2 )) < (µ C (t 1 ), µ W (t 1 )). (3)
b) Property 2. Consistency condition: The negation operator must deliver a consistency bipolar condition, which means: ∀t, µ W (t) ≤ µ C (t).

This property means that the negation of a bipolar condition of the form "and if possible" must also be a bipolar condition.

c) Property 3. Involutivity: The negation operator must be an involutive operator, it means that: ¬(¬(C,W )) = (C,W ).

Several negation operators have been proposed in the literature. Some of them are summarized in what follows.

A. The Negation Operator Inspired by Twofold Fuzzy Sets

This negation operator is proposed in [START_REF] Dubois | Twofold fuzzy sets and rough sets-some issues in knowledge representations[END_REF]. In this context, the negation of the wish corresponds to the constraint and the negation of the constraint defines the wish of the obtained condition. More formally, let (C,W ) be a bipolar condition, its negation is:

¬(C,W ) = (¬W, ¬C).
This kind of negation is not intuitive and does not satisfy the property of order reversing as it is shown in the following example 1.

Example 1: Let (C,W ) be a bipolar condition and R a relational table containing tuples t 1 and t 2 such that:

(µ C (t 1 ), µ W (t 1 )) = (0.8, 0) and (µ C (t 2 ), µ W (t 1 )) = (0.6, 0.6), we obtain t 1 > t 2 .
The negation of (C,W ) delivers the following result:

(µ C (t 1 ), µ W (t 1 )) = (1, 0.2) and (µ C (t 2 ), µ W (t 2 )) = (0.4, 0.4),
we obtain, then t 1 > t 2 . @ B. The Negation Operator Based on the Product and the Division This operator has been proposed in [START_REF] Bosc | A propos de la négation de conditions bipolaires floues. on the negation of fuzzy bipolar conditions[END_REF]. It is defined as follows: ¬(C,W ) = (C ,W ), where:

µ C = 1 -µ C , (4)
and

µ W = (1 -µ C ) * (1 -µ W µ C ) i f µ C = 0, 1 else. ( 5
)
This operator is not involutive; indeed:

¬(¬(1, b = 0)) = ¬(0, 0) = (1, 1) = (1, b = 0).
In order to make this operator involutive, it is necessary to accept ordered pairs of grades of the form (0, b > 0) and to define the negation as follows:

µ C = 1 -µ C (6) µ W = 1 -µ W i f µ C = {0, 1}, (1 -µ C ) * (1 -µ W µ C ) else. (7)
The above properties 1, 2 and 3 hold only if the following conditions are satisfied:

• do not substitute

(C,W ) by (C,C ∧W ) when µ C = 0, • substitute (C,W ) by (C,W ∧ (C ∨ (¬C ⇒ RG true)))
, where ⇒ RG is the Rescher-Gaines fuzzy implication, • do not discard from the bipolar relation, tuples which have an ordered pair of grades of the form (0, b = 0). Despite the satisfaction of properties 1, 2 and 3 under above conditions, the following drawbacks are pointed out:

• this operator does not express a natural negation form from the user point of view, • its implementation is difficult and complex,

• the three added conditions can be seen as an infringement to properties of fuzzy bipolar conditions.

C. The Negation Operator of the Form (¬C, false)

This operator is proposed in [START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] and it is defined as follows:

) = (¬C, false) (8)
This operator means that if tuples satisfying the constraint are discarded, then the wish becomes meaningless.

This form of negation is not involutive:

¬(¬(C,W )) = ¬(¬C, false) = (C, false) = (C,W ).

D. The Negation Operator of the Form (¬C, ¬W )

This operator is proposed in [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF], [START_REF] Liétard | On the definition of extended norms and conorms to aggregate fuzzy bipolar conditions[END_REF]. The negation operator in this approach is defined as follows: ¬(C,W ) = (¬C, ¬W ).

This operator does not satisfy the consistency condition because ¬W ¬C. The obtained operator is no more bipolar and can leads to non-consistent queries as in the following example 2.

Example 2: The negation of "Train tickets which cost less than 100 $ and if possible less than 75 $" is defined in this context as "Train tickets which cost more than 100 $ and if possible more than 75 $". This query is not consistent because the set of tickets which cost more than 75 $ in not included in the set of tickets which cost more than 100 $, but rather the opposite. @ IV. FUZZY BIPOLAR CONDITIONS OF THE FORM "OR ELSE"

We introduce in this section a new kind of fuzzy bipolar conditions. They are of the form "or else". We, firstly, provide a formal definition for such bipolar conditions; then, we study semantic relationships and similarities between "or else" and "and if possible" fuzzy bipolar conditions. Finally, we show that these two forms can be used in a negation context to define a global negation operator for fuzzy bipolar conditions.

A. Definition

A bipolar condition of the form "E, or else F" is made of two parts: (i) a positive pole corresponding to the condition E, which expresses perfect values and (ii) a negative pole corresponding to the condition F that expresses acceptable values (any element does not satisfy F is discarded).

We define bipolar conditions of the form "E, or else F", denoted [E, F], with the following properties:

1) ¬F corresponds to the rejection (F denotes acceptable elements), 2) E corresponds to the optimal values, 3) The optimality condition E is more important than the acceptability condition F, 4) The set of optimal values is included in the set of acceptable values (E ⊆ F): ∀x, µ E (x) ≤ µ F (x). The ordered pair of grades, denoted [µ E (x), µ F (x)], expresses the satisfaction of an element x to the condition "E, or else F".

Since the satisfaction with respect to the optimality E is more important than the satisfaction with respect to the acceptability F, the lexicographical order can be used to rank between elements. Indeed, if an element x satisfies completely the optimal condition E then it gets a pair of grades [1, 1] because ∀x, µ E (x) ≤ µ F (x), and by definition, the lexicographical order shows that this element is optimal. If the satisfaction to the optimal condition E of an element x 1 is better than the satisfaction to the same condition by another element x 2 , then x 1 is more preferred than x 2 .

Finally, if both x 1 and x 2 have the same satisfaction to the optimal condition E, for want of anything better, the condition F is used to distinguish between them.

Remark 3: It is worth noticing that a fuzzy condition C can be expressed "C or else C" within the framework of bipolar conditions of the form "or else". This generalization of fuzzy conditions expresses that perfect and acceptable values are the same.

As is the case of fuzzy conditions of the form "and if possible", the lmin (resp. lmax) operator applied on bipolar conditions of the form "or else" defines an extended triangular norm (resp. co-norm).

B. Relationships Between "or else" and "and if possible" Fuzzy Bipolar Conditions

Let "E, or else F" and "C, and if possible W " be two fuzzy bipolar conditions. The former is denoted [E, F], with ∀x, µ E (x) ≤ µ F (x) and the latter is denoted (C,W ), with ∀x, µ W (x) ≤ µ C (x). We notice strong similarities between these two formalisms, since in both cases we have:

• C and F express the acceptable values (or a non rejected values), • ¬C and ¬F correspond to the discarded values, • W and E express the perfect or optimal values, • the set of perfect values is included in the set of acceptable values. Moreover, these two conditions generalize fuzzy conditions in the same way: a fuzzy condition

C is expressed (C,C) or [C,C].
Since W (resp. C) plays the same role as E (resp. F), it is interesting to study the behavior of (C,W ) and [W,C]. First of all, we notice that in the boolean case, both formalisms have the same meaning, as shown in the example 3.

Example 3: Let x, y and z be three elements attached respectively to the following pair of grades: (1, 1), (1, 0) and (0, 0) with respect to conditions C and W .

The lexicographical order delivers the same order in both situations (C,W ) and [W,C]: x > y > z. @ However, when C and W are fuzzy conditions, the two formalisms do not express the same semantic because the lexicographical order does not deliver the same order.

Tables I andII show that tuples t 1 ,t 2 ,t 3 and t 4 are not sorted according to the same order, depending on whether the formalism (C,W ) or [W,C] is used.

The basic difference between these two formalisms is the fact that the formalism "C, and if possible W " gives more importance to the non rejected elements (that means the satisfaction with respect to the condition of acceptance C is privileged), whereas the formalism "E, or else F" gives more importance to the optimal elements (i.e. the satisfaction with respect to the optimal condition E is privileged).

In this context, a fuzzy bipolar condition of the form (C,W ) can be defined as a pair of fuzzy conditions, which define a set of optimal values (W ) and a set of acceptable values (C) under the consideration that the non-rejection is more important than the optimality; and a fuzzy bipolar condition of the form [E, F] is defined as a pair of fuzzy conditions, which define a set of optimal values (E) and a set of acceptable values (F) under the consideration that the optimality is more important than the non-rejection.

C. The Negation Context

In this subsection, we show that the negation of the fuzzy bipolar condition (C,W ) is the fuzzy bipolar condition [¬C, ¬W ] and, reciprocally, the negation of the fuzzy bipolar condition [E, F] is the fuzzy bipolar condition (¬E, ¬F).

1) Negation of (C,W ): We recall that a bipolar condition (C,W ) is defined by the following properties:

1) ¬C corresponds to the rejection (C denotes acceptable elements), 2) W corresponds to the optimal values, 3) The acceptability condition C is more important than the optimality condition W . In addition, the set of optimal values is included in the set of acceptable values (W ⊆ C).

If we express these properties in the context of a negation ¬(C,W ), we obtain:

1) ¬C corresponds to the optimal values (C contains rejected and acceptable elements), 2) W corresponds to the rejected values (¬W denotes acceptable elements), 3) The optimality condition ¬C is more important than the acceptability condition ¬W . In addition, since W ⊆ C, we have ¬C ⊆ ¬W . Therefore, we obtain a fuzzy bipolar condition which fits within the definition of the "or else" fuzzy bipolar conditions and we denote it by [¬C, ¬W ]. That means:

¬(C,W ) = [¬C, ¬W ]. (9)
It is important to notice that in (C,W ), the importance is put on C and the concept attached to C stills the most important for ¬(C,W ). As an example, when considering "young and if possible young and well-paid employees", the importance is put on the age (young). In its negation, the age stills the most important aspect to consider.

Example 4: Let (Young,Young ∧ WellPaid) be a fuzzy bipolar condition of type "and if possible" which defines young and if possible young and well-paid employees. Let table III be a set of returned tuples from a relational table. The negation of the fuzzy bipolar condition (Young,Young ∧ WellPaid) is defined as [notYoung, not(Young ∧ WellPaid)], which corresponds to employees which are not young, or else are not (young and well-paid). We notice that concepts used to define the fuzzy bipolar condition (Young,Young ∧ 2) Negation of [E, F]: We recall that a fuzzy bipolar condition [E, F] is defined by the following properties:

• ¬F corresponds to the rejection (F denotes the acceptable elements), • E corresponds to the optimal values, • The optimality condition E is more important than the acceptability. In addition, the set of optimal values is included in the set of acceptable values (E ⊆ F).

If we express these properties in the context of a negation, we obtain:

• ¬F corresponds to the optimal values, • E corresponds to the rejected values (¬E denotes the acceptable elements), • The acceptability condition ¬E is the more important condition. In addition, since E ⊆ F, we have ¬F ⊆ ¬E. This property states that, in the context of negation of a fuzzy bipolar condition of the form [E, F], the set of optimal values is included in the set of acceptable values.

Therefore, we obtain a fuzzy bipolar condition, which fits within the definition of the "and if possible" fuzzy bipolar conditions and we denote it by (¬E, ¬F). That means:

¬[E, F] = (¬E, ¬F). (10)
As for bipolar conditions of type "and if possible", we notice that in [E, F], the importance is put on E and the concept attached to E stills the most important for ¬

[E, F].
This form of negation is involutive and reverses the lexicographical order (either for ¬(E, F) or ¬[E, F]).

Proof: Reversing of the lexicographical order. The proof is based on the following properties:

(x 1 , y 1 ) > (x 2 , y 2 ) ⇒ (1 -x 1 , 1 -y 1 ) < (1 -x 2 , 1 -y 2 ).
Let [E, F] or (E, F) be a fuzzy bipolar condition. A tuple t i is preferred to t j means that:

(µ E (t i ), µ F (t i )) > (µ E (t j ), µ F (t j )), or [µ E (t i ), µ F (t i )] > [µ E (t j ), µ F (t j )]
From the definition of the lexicographical order, we get:

(t i is preferred to t j ) ⇔ µ E (t i ) > µ E (t j ) or (µ E (t i ) = µ E (t j ) and µ E (t i ) > µ F (t j )) ⇔ (1 -µ E (t i ) < 1 -µ E (t j )) or ((1 -µ E (t i ) = 1 -µ E (t j ))
and (1µ E (t i ) < 1µ F (t j ))) ⇔ t j is preferred to t i for (¬E, ¬F) or [¬E, ¬F], with (¬E, ¬F) = ¬[E, F] and [¬E, ¬F] = ¬(E, F). The order is then reversed for the negation.

Proof:

Involutivity. ¬(¬(C,W )) = ¬[¬C, ¬W ] = (¬¬C, ¬¬W ) = (C,W ) and ¬(¬[E, F]) = ¬(¬E, ¬F) = [¬¬E, ¬¬F] = [E, F].
V. MUTUAL COMPATIBILITY OF "AND IF POSSIBLE" AND "OR ELSE" FUZZY BIPOLAR CONDITIONS It is possible to express fuzzy bipolar conditions of both forms "and if possible" and "or else" together in the same bipolar query. This means that it is possible to use lmin and lmax operators to compare and to handle ordered pairs of scores of these types of fuzzy bipolar conditions. This is due to the fact that both of them are semantically equivalent in the sense that they are defined similarly. Indeed, fuzzy bipolar conditions of types "and if possible" and "or else" consist of two parts: a first part which corresponds to the most important concept (the concept attached to C for the fuzzy bipolar condition (C,W ) and the concept attached to E or the fuzzy bipolar condition [E, F]) and a second part which corresponds to the least important concept of the bipolar condition. Therefore, in order to rank between tuples, the first choice is made on the condition which corresponds to the most important concept in the fuzzy bipolar condition, and the second choice is made on the condition which corresponds to the least important concept of the same fuzzy bipolar condition. We show in the following example a bipolar query in which both forms of fuzzy bipolar conditions are used, and its returned tuples with their attached ordered pairs of degrees.

Example 5: Let R be a relational table about journeys from Paris to Brest (see table V), delivered from a multimodal transport information system.

One can express a bipolar query about preferred journeys in the following terms:

"Find journeys from Paris to Brest which are (fast, and if possible fast and cheap), or journeys with (an early departure and a late arrival, or else an early departure)".

In the above query, the preferred journeys are those which have a short duration and cost as low as possible, or journeys in which the user takes the time to travel, which correspond to journeys having an early departure and a late arrival, otherwise journeys which have an early departure.

Based on the fuzzy predicates fast, cheap, early and late, we define from the relation R the following bipolar relations Journey (Fast,Fast∧Cheap) (see The ordered pair of grades of satisfaction, with regard to the combination of the fuzzy bipolar conditions (Fast, Fast ∧ Cheap) and [Early ∧ Late, Early], attached to each tuple is obtained by the application of the lmax operator on each tuple of both fuzzy bipolar relations as follows: We notice that journeys are delivered depending on the grade of satisfaction w.r.t the most important fuzzy condition: fast for the fuzzy bipolar condition (Fast, Fast ∧ Cheap) and early for the fuzzy bipolar condition [Early ∧ Late, Early]. In the case where the two most important conditions have the same satisfaction, the distinction is made on the least important conditions.

The maximum ordered pair of degrees is attached to tuples #10 and #16, because the corresponding fuzzy bipolar condition is completely satisfied (both are fully satisfactory and not distinguishable).

In the case of tuples #11, #12, #14, #15, the returned ordered pair of grades corresponds to the ordered pair in which the In the case of tuple #13, the satisfaction is the same with regard to the most important fuzzy condition in both fuzzy bipolar conditions; therefore, the least important condition is used to determine which ordered pair of degrees to attach to the resulting tuple.

Finally, journeys are delivered in the following order: (1, 1)/#10, [1, 1]/#16, [0.8, 1]/#15, (0.8, 0.64)/#11, (0.8, 0.25)/#12, [0.6, 1]/#13, [0.6, 0.7]/#14.

VI. CONCLUSION AND FUTURE WORKS

A new kind of fuzzy bipolar conditions is introduced in this paper. These conditions are of the form "or else" and allow users to express complex preferences of a disjunctive nature in their queries. We showed that this form of fuzzy bipolar conditions are compatible with fuzzy bipolar conditions of the form "and if possible" in the sense that (i) each one can be used as the negation form of the other and that (ii) it is possible to combine them in the same query and to handle them using the lexicographical order based operator lmin and lmax.

As future work, we aim at studying this form of negation within the scope of a bipolar relational language and at integrating it into the bipolar SQLf language, which is an extension of the SQLf language to fuzzy bipolar conditions.

•

  #journey = 10: lmax((1, 1), [0.25, 0.6])= (1, 1), • #journey = 11: lmax((0.8, 0.64), [0.25, 0.5]) = (0.8, 0.64), • #journey = 12: lmax((0.8, 0.25), [0.3, 1])= (0.8, 0.25), • #journey = 13: lmax((0.6, 0.36), [0.6, 1])= [0.6, 1], • #journey = 14: lmax((0.4, 0.36), [0.6, 0.7]) = [0.6, 0.7], • #journey = 15: lmax((0.4, 0.16), [0.8, 1])= [0.8, 1], • #journey = 16: lmax((0.25, 0.25), [1, 1]) = [1, 1],

TABLE I EXAMPLE

 I OF THE BEHAVIOR OF THE (C,W ) FORMALISM.

		µ C (x i )	µ W (x i )
	t 1	1	1
	t 2	0.8	0.2
	t 3	0.7	0.5
	t 4	0.4	0.3
		TABLE II
	EXAMPLE OF THE BEHAVIOR OF THE [W,C] FORMALISM.
		µ W (x i )	µ C (x i )
	t 1	1	1
	t 3	0.5	0.7
	t 4	0.3	0.4
	t 2	0.2	0.8

TABLE III EXAMPLE

 III OF TUPLES ATTACHED WITH THEIR ORDERED PAIRS OF GRADES W.R.T THE FUZZY BIPOLAR CONDITION (Young,Young ∧WellPaid).

	#Employee	µ Young (#Employee)	µ Young (#Employee)∧
			µ WellPaid (#Employee)
	10	1	1
	11	0.75	0.56
	12	0.6	0.36
	13	0.5	0.25

TABLE IV EXAMPLE

 IV OF TUPLES ATTACHED WITH THEIR ORDERED PAIRS OF GRADES W.R.T THE FUZZY BIPOLAR CONDITION [notYoung, not(Young ∧WellPaid)].WellPaid) are the same ones used to express its negation [notYoung, not(Young ∧ WellPaid)]. More precisely, the concept age is used to define the most important fuzzy condition in both fuzzy bipolar condition (Young,Young ∧WellPaid) and [notYoung, not(Young ∧WellPaid)].The obtained ordered pairs of degrees for the fuzzy bipolar condition [notYoung, not(Young ∧ WellPaid)] are summed up in the table IV. The tuple #10 is completely discarded. @

	#Employee	µ notYoung (#Employee)	µ not(Young and WellPaid) (#Employee)
	13	0.5	0.75
	12	0.4	0.64
	11	0.25	0.44

  table VI), which corresponds to fast and if possible cheap journeys, and Journey [Early∧Late,Early] (see table VII), which corresponds journeys having an early departure and a late arrival or else an early departure. Tuples of these relations are ranked from the most satisfactory to the least satisfactory with regard to fuzzy bipolar conditions (Fast, Fast ∧Cheap) and [Early ∧ Late, Early] respectively.

TABLE V EXAMPLE

 V OF EXTENSION OF THE RELATION R.

	#Journey	Duration	Departure	Mode Cost	...
	10	2h	11h30 am	Plane	60	...
	11	2h45	11h am		Plane	150	...
	12	2h30	8h30 am	Plan	260	...
	13	3h10	8h am		Train	80	...
	14	3h30	10h am		Train	80	...
	15	4h10	7h30 am	Train	90	...
	16	5h15	7h15 am	Bus	85	...
		TABLE VI
	THE FUZZY BIPOLAR RELATION Journey (Fast,Fast∧Cheap) .
	#Journey	µ Fast (#Journey)	µ Fast∧Cheap (#Journey)
	10	1			1
	11	0.80			0.64
	12	0.80			0.25
	13	0.60			0.36
	14	0.40			0.36
	15	0.40			0.16
	16	0.25			0.25

TABLE VII THE

 VII FUZZY BIPOLAR RELATION Journey [Early∧Late,Early] . w.r.t the most important fuzzy condition in both used fuzzy bipolar conditions is the highest.

	#Journey	µ Early∧Late (#Journey)	µ Early (#Journey)
	16	1	1
	15	0.80	1
	13	0.60	1
	14	0.60	0.70
	12	0.30	1
	10	0.25	0.60
	11	0.25	0.50

satisfaction

ACKNOWLEDGMENTS

This work is funded by the Brittany region and the department of Côtes-d'Armor and is partially supported by the National Agency for Research (AOC Ref. ANR-08-CORD-009).


Abdullah Oueslati
email: abdullah.oueslati@gmail.com

Olivier Lopez
email: olivier.lopez0@upmc.fr.

A two-tier proportional hazards regression model with change-points in the baseline function

Keywords: proportional hazards regression, change-point detection, iterative procedures, dynamic programming, revenue-management, survival analysis

A two-tier proportional hazards regression model with change-points in the baseline function

Abdullah Oueslati, Olivier Lopez

Introduction

In Yield-Management, a critical issue is to infer on the stochastic behaviour of a counting process (representing, for example, the number of reservations for a transportation company, or the number of reservations in an hotel) in order to be able to develop strategies that optimize the profit. In this paper, we develop a statistical model that has been firstly designed to apply to the study of the amount of reservations in a public transport company. The key feature of our new approach stands in the fact that we try to identify two different factors that influence the general dynamics of reservations. The first one is a classical capacity constraint: when some types of seats become unavailable, the consumers change their behaviour, by either preferring another category of seats, or by not buying any ticket. The second one is a time evolution, caused by the proximity of the date of departure. In the model that we consider, the number of reservations is considered as a counting process that evolves through a multiplicative hazard model. Multiplicative hazard regression models are a very common tool when one wants to model the influence of some set of covariates, which, in the particular situation that we will latter consider, will consist of informations on the availability of the different types of seats. In these models, a baseline hazard function determines some general behaviour of the process, while the influence of the covariates appears only through a multiplicative term. Back to our example, the baseline hazard function will represent some general evolution of the behaviour of the consumers, that is not caused by the lack of availability, but only by a general time evolution.

If such a multiplicative hazard model holds, it becomes very easy to determine the influence of a specific covariate, identifying its contribution to the increase of the hazard rate. In the literature of multiplicative hazard models, one must distinguish between two major types of approaches. The fully parametric approach consists of specifying the baseline hazard function. See for example Martinussen and Sheike (2006) for a review of the different techniques in this framework. On the other hand, the semiparametric approach initially developed by [START_REF] Cox | Regression models and life-tables[END_REF] (see also [START_REF] Andersen | Cox's regression model for counting processes: a large sample study[END_REF] does not require the specification of the baseline hazard rate, whose estimation relies on nonparametric approaches. The most classical of these approaches is developed by [START_REF] Breslow | Contribution to the discussion of the paper by Dr. Cox[END_REF], which introduces a nonparametric estimator of the cumulative baseline hazard rate, but other approaches have been developed, as the one proposed by [START_REF] Dabrowska | Smoothed Cox regression[END_REF] using kernel smoothing, or the one based on regression splines in [START_REF] Sleeper | Regression splines in the Cox model with application to covariate effects in liver disease[END_REF].

One of the drawbacks of such techniques stands in the difficulty of interpretation of the resulting estimator of the baseline hazard function.

The approach that we develop in this paper is parametric, and is close to Cox's regression model in the sense that Cox's regression model can be seen as a limit case. We propose to model the baseline hazard function as a piecewise constant function, without prior knowledge of the times at which the jumps occur. This methodology is inspired by multiple change-point techniques (see e.g. [START_REF] Csörgo | Limit Theorems in Change-Point Analysis[END_REF][START_REF] Basseville | Detection of Abrupt Changes: Theory and Application[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of Gaussian process by model selection[END_REF], which are particularly adapted to our problem, since they will allow to estimate some time of change of behaviour of the consumers. Moreover, this framework allows us to develop test procedures that consists of detecting the presence or absence of change-points. From a practical viewpoint, such type of test procedure will allow to distinguish between changes of behaviours that are only caused by the covariates (that is, the changes in the availability), and changes which represent a general evolution of the dynamics. Moreover, compared to Cox's regression model, our approach can be seen as a reasonable compromise between additional assumptions and computational efficiency. Indeed, our estimation procedure is expected to outperform Cox's partial likelihood maximization in situations where the number of tied event times can be high, which is shown through simulations.

The rest of this paper is organized as follows. In section 2, we introduce our hazard regression model. Section 3 is devoted to the estimation of the parameters, which relies on maximum likelihood estimation. We especially focus on the practical implementation, developing a dynamic programming strategy for the estimation of the change-points, and an iterative algorithm to perform the joint estimation of the change-points and of the regression parameters. We also propose a test procedure to perform the change-point detection, and discuss how to compute the critical values through a simulation approach.

In section 4, we investigate the practical behaviour of our technique. Through a simulation study, we first compare the behaviour of our estimation procedure to the use of Cox's partial likelihood when we only focus on the influence of covariates, before investigating on the change-point estimation. Next, we apply our technique to a real case provided by the French national railway company SNCF.

Proportional hazards model with change-point detection and parametric regression

In this section, we present the statistical model that will be used throughout this paper, and the procedure that we propose to estimate its parameters. Section 2.1 details notations and assumptions that will be used in the following. As announced in the introduction, our model combines a proportional hazards regression model, with a change-point approach in order to estimate the baseline intensity. A small discussion to compare our model to Cox's regression model is provided in section 4.2.

Model

We consider observations made of m independent counting processes, observed at discrete

dates t 0 < • • • < t n , that is we observe N j (t i ) 0≤i≤n 1≤j≤m
, where t n = τ is the total time of observation. Since all processes may not be observed during the same amount of time, we also observe indicators Y ij Y j (t i ) taking the value 1 if N j is at risk at time t i , and Y j (t i ) = 0 otherwise. In addition, one observes a time-dependent vector of covariates

(X ij ) 0≤i≤n 0≤j≤m (X j (t i )) 0≤i≤n 0≤j≤m .
Data are modelized through a proportional regression model, that is the hazard intensity of the process N j (t) 0≤t≤τ is

λ j (t) = Y j (t)λ 0 (t)e βX j (t) , (2.1)
where Y j (t) is the "at risk" process , λ 0 (t) is the baseline hazard function, β is a some unknown regression parameter to estimate and X j (t) is a time-dependent variable.

Such type of regression models have been widely used for the study of recurrent events processes (see [START_REF] Ghosh | Semiparametric analysis of recurrent events in the presence of dependent censoring[END_REF]. An important version is the semiparametric Cox regression model [START_REF] Cox | Regression models and life-tables[END_REF][START_REF] Andersen | Cox's regression model for counting processes: a large sample study[END_REF]. In Cox's model, the baseline hazard function λ 0 is not specified. Compared to a fully parametric model, Cox's approach provides additional flexibility to the model. Nevertheless, one of the disadvantages stands in the difficulty of interpreting the estimation of the nonparametric part. In our approach, we therefore chose to rely on a fully parametric model, which is adapted to some specific situations such as the one we consider in our application in section 4.3 below. We assume that the function λ 0 is piecewise constant, with jumps only at l unknown times t ks 1≤s≤l , that is

λ 0 (t) = l s=0 µ s 1{t ks ≤ t < t k s+1 }, (2.2)
which can be seen as a multiple change-point model on the baseline hazard function. The values µ s of the intensity on [t ks , t k s+1 ) are also unknown in our framework. An interesting feature of this model stands in the fact that the time of change can be interpreted as structural changes in the hazard rate that are not caused by the covariates, but which come from a change in the global dynamics. In the example we provide below in section 4.3, this change is interpreted by a structural and global increase (or decrease) in the number of bookings pro period of time. In a Cox-regression model, the classical way to estimate the nonparametric part consists of using the estimator of [START_REF] Breslow | Contribution to the discussion of the paper by Dr. Cox[END_REF]. In this case, the resulting estimator is a piecewise constant hazard function with n jumps (at each time of observation), hence it can be seen as a limit case of model (2.2).

Estimation procedure

We now present our methodology to estimate the different parameters of the model considered in section 2. Our procedure consists of applying maximum likelihood inference (see section 3.1). Since this approach leads to numerical optimization problems when it comes to implementation, we provide an iterative algorithm, detailed in section 3.2, to perform this maximization. The principle of this strategy consists of distinguishing between the two different structures present in our model. This is done by separating the estimation of the regression parameters from the estimation of the change-points. Section 3.3 proposes a numerical method involving dynamic programming in order to perform change-point estimation. Finally, a test procedure for change-point detection is provided in section 3.4.

Maximum likelihood estimation

From a statistical point of view, we have to estimate the following parameters θ = β, k 1 , . . . , k l , µ 0 , . . . , µ l . In this type of parametric problems, it is natural to rely on a maximum likelihood approach. Following Martinussen and Scheike (2006), Aalen et al.

(2008), the log-likelihood in our model can be expressed as,

L l (θ) = - l s=0 µ s k s+1 -1 i=ks d i m j=1 Y ij e βX ij + l s=0 log(µ s ) ks≤i≤k s+1 -1 1≤j≤m Z ij + β 1≤i≤n 1≤j≤m X ij Z ij ,
where

Z ij N j (t i )-N j (t i-1
) is the variation of the process N j on [t i-1 , t i ), and (d 1 , . . . , d n )

(t 1 -t 0 , . . . , t n -t n-1 ) denotes the length of the different time intervals (which may not be equal in practice). The maximum likelihood estimator is then defined as

θl = argmax θ L l (θ).
Unfortunately, direct maximization of a functional of the type of the log-likelihood leads to technical problems, due to the complexity of the numerical techniques that would be involved if one wishes to achieve exact maximization of this functional. Therefore, we provide in the following section an iterative procedure that allows to fill this gap.

Estimation algorithm

The algorithm detailed in this section is based on the separation of the parameter θ into two parts: the regression parameter β and the change-point parameters (k, µ) with k = (k 1 , . . . , k l ) and µ = (µ 0 , . . . , µ l ). Similar approaches are classically developed in semiparametric regression (see e.g. [START_REF] Xia | An adaptive estimation of dimension reduction space[END_REF]. In our framework, the model is fully parametric. Nevertheless, in our approach, regarding the estimation of the baseline, we are close to a nonparametric problem, in the sense that the number of parameters to estimate may be high if we increase the number l of change-points.

Therefore, to optimize L l β, (k, µ) , we develop the following iterative algorithm, containing two steps in each iteration: 1) , µ (1) ) ← argmax (k,µ) L l β (1) , (k, µ)

Algorithm 1 Find θ which maximizes L l (θ) β (0) ← β 0 (k (0) , µ (0) ) ← argmax (k,µ) L l β (0) , (k, µ) θ (0) ← β (0) , (k (0) , µ (0) ) β (1) ← argmax β L l β, (k (0) , µ (0) ) (k (
θ (1) ← β (1) , (k (1) , µ (1) )

p ← 1 while |L l θ (p) -L l θ (p-1) | > ε do p ← p + 1 Change-point step : (k (p) , µ (p) ) ← argmax (k,µ) L l β (p-1) , (k, µ)
Regression step :

β (p) ← argmax β L l β, (k (p) , µ (p) ) θ (p) ← β (p) , (k (p) , µ (p) ) end while
At the regression step, the problem

argmax β L l β, (k, µ) ,
can be solved by a quasi-Newton algorithm (available on the stat package of R software), while, at the change-point step, the maximization problem

argmax (k,µ) L l β, (k, µ) , (3.1)
requires high computational time to be solved. Indeed, the likelihood has to be maximized for all combinations of vector (k 1 , . . . , k l ). Dynamic programming has been used by [START_REF] Bellman | On the approximation of curves by line segments using dynamic programming[END_REF] and [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF] to fix some similar kind of problems. The algorithm developed in the next section is a direct extension of these approaches, but with a different contrast to minimize, which is adapted to our particular framework.

Dynamic programming for change-point detection

Solving the problem (3.1) is equivalent to solving

argmax k L l β, k, µ(k) with µ(k) = µ 0 (k 0 , k 1 ), . . . , µ l (k l , k l+1 ) and µ s (k s , k s+1 ) = m j=1 k s+1 -1 i=ks Z ij k s+1 -1 i=ks d i m j=1
Y ij e βX ij . Indeed, µ(k) is the maximum likelihood estimator of the vector of intensities µ if we assume that the changes occur at times t k 1 , . . . , t k l for a fixed vector k = (k 1 , . . . , k l ).

Therefore, solving (3.1) consists of solving an optimization problem of the following type:

argmax k l ∈C l n-1 f (k l ), where C l n-1 is the set of n-1 l vector combinations k l = (1, k 1 , . . . , k l , n + 1) such that (1 < k 1 < k 2 < • • • < k l < n + 1), with f (k l ) = l s=0 g(k s , k s+1 ),
where g is defined as,

g(k s , k s+1 ) = log m j=1 k s+1 -1 i=ks Z ij k s+1 -1 i=ks d i m j=1 Y ij e βX ij m j=1 k s+1 -1 i=ks Z ij .
To define our dynamic programming procedure, we also need to introduce,

V (b, i) max k i ∈C i (1,b) f (k i ),
V (b, 1) argmax

k i ∈C i (1,b) f (k i ),
where

C i (1, b) is the set of possible vectors k i = (1, k 1 , . . . , k i , b) such that 1 < k 1 < • • • < k i < b.
The following l + 1 steps algorithm provides the vector of right combination k l which maximizes the objective function f . The main idea of the algorithm can be summarized in the following way : assuming that we know, for each possible possible location of the i th change-point, the optimal combination of i -1 first change-points, we just have to choose the i th change-point that maximizes the function f . We then apply iteratively this procedure to get the optimal position of i = 1 change-point, then i = 2,. . . , until i = l change-points.

Algorithm 2 Find k l which maximizes f (k l ) Step 0 : ∀b ∈ {2, . . . , n + 1}, solve V (b, 0) : ∀b, V (b, 0) ← g(1, b)
Step 1 : ∀b ∈ {3, . . . , n + 1}, solve V (b, 1) :

V (b, 1) ← max 2≤x<b V (x, 0) + g(x, b) V (b, 1) ← argmax 2≤x<b V (x, 0) + g(x, b) . . . . . . . . . . . . Step i : ∀b ∈ {i + 2, . . . , n + 1}, solve V (b, i) : V (b, i) ← max i+1≤x<b V (x, i -1) + g(x, b) V (b, i) ← argmax i+1≤x<b V (x, i -1) + g(x, b) . . . . . . . . . . . .
Step l :

V (n + 1, l) ← max l+1≤x<n+1 V (x, l -1) + g(x, n + 1) V (n + 1, l) ← argmax l+1≤x<n+1 V (x, l -1) + g(x, n + 1)
Final step : get the vector

k l = (1, k 1 , . . . , k l , n + 1) which maximizes f (k l ) k l ← V (n + 1, l), k l-1 ← V ( k l , l -1), . . . , k i ← V ( k i+1 , i), . . . , k 1 ← V ( k 2 , 1)
Then, we get the estimated intensity vector µ = µ( k l ) from k l . The pair ( k l , µ) is the exact solution of initial problem (3.1).

Change-point detection and testing

Since our model (2. In this section, we focus on the one-change point detection, that is we wish to test the following null hypothesis, H 0 : ∃µ 0 s.a. λ 0 (t) ≡ µ 0 , against the following alternative,

H 1 : ∃(k, µ 0 , µ 1 ) s.a. λ 0 (t) = µ 0 1{t < t k } + µ 1 1{t ≥ t k }.
A natural way to proceed consists of using a likelihood ratio test. Let θ1 (resp. θ2 ) denote the maximum likelihood estimators developed in the previous sections in the case where one assumes that there is no change-point (resp. one change-point), that is under H 0 (resp. under H 1 ). The likelihood ratio test procedure consists of rejecting H 0 when

T n = L 2 ( θ2 ) -L 1 ( θ1
) is larger than some critical value s α that permits to achieve the proper level α. Rather than rely on an asymptotic approximation of T n , we suggest to use a bootstrap procedure to compute this critical value.

The test procedure described below can be extended to test the presence of k-change-

Application : simulations and SNCF study

In this section, we investigate the empirical behaviour of our procedure. In section 4.1, we consider a fixed value of the regression parameter β and we observe how the changepoint modeling influences the quality of estimation of this parameter. Moreover, we investigate the quality of our final estimators of the intensities λ j . In section 4.2, we develop a comparison with Cox's regression model, which suffers, in our framework, from the presence of tied event times. Section 4.3 presents the application of our model to the study of bookings in the French company SNCF.

Estimation

The simulation setting that we propose in order to enlighten the practical behaviour of our procedure is inspired by the situation that is considered in the study developed in section 4.3. We consider n = 20, m = 42, β = 2, and at-risk processes Y j ≡ 1. The lines of the matrix X are made of vectors X i. with components equal to zero up to some index j 0 (i), and equal to 1 for the remaining components. The choice of such a structure for the matrix X is motivated by our example in the case of the SNCF study, in which a value 1 corresponds to a class of seats which is unavailable. For all our simulation study, we considered the same matrix X, which has been randomly generated in order to match the structure observed in the real data set, that is a proportion of 31.07% of 1 in the coefficients. The interval between t i and t i+1 is assumed to be constant and equal to one.

For different values of λ 0 (that is different values of (k, µ)), we simulate q = 1000 samples and estimate the parameters from our estimation procedure for each simulated sample. We compare our estimator with the one obtained by maximizing Cox's partial likelihood. Since there is a significant number of tied event times in the simulated datasets, one requires to use approximations of this partial likelihood. In our simulations, we consider the case of Efron's approximation (1977) and of Breslow's approximation (1974).

The performance of each technique is measured through different error criterions. We focus first on the quality of estimation for each separated parameter, and then look at the global estimator of the intensities. For a parameter x ∈ R, and an estimate x (p) ∈ R of this quantity, we consider the following criterions:

e 1 (x) = 1 q q p=1 | x (p) -x|, e 2 (x) = 1 q q p=1 ( x (p) -x) 2 , e ∞ (x) = max 1≤p≤q | x (p) -x|.
Similarly, we define errors for an estimator λ of the matrix λ = (λ j (t i , θ)) 1≤i≤n 1≤j≤m as

e 1 ( λ) = 1 q q p=1 m j=1 n i=1 | λ j (t i , θ (p) ) -λ j (t i , θ)|, e 2 ( λ) = 1 q q p=1 m j=1 n i=1 ( λ j (t i , θ (p) ) -λ j (t i , θ)) 2 , e ∞ ( λ) = 1 q q p=1 max 1≤i≤n 1≤j≤m | λ j (t i , θ (p) ) -λ j (t i , θ)|.
Compared to the separate study of the estimation of each parameter, evaluating some distance between our estimated λ and the true intensity matrix λ presents the interest to have a global view on the performance of the estimation procedure in our model. More precisely, we will compare the estimated intensity to the one that would be obtained in a model with no change-point, to try to understand if the improvement obtained through our approach is significant or not.

We consider different settings, first in the case where there is one change-point, and the two change-points situation.

First case: one change-point.

In this case, we need three additional parameters to characterize the processes, that is the intensity µ 0 before the "jump", the intensity µ = 1 after the jump, and the rank k of the time of the change t k . In all our simulations, we take µ 0 = 1. Clearly, the performance of our approach will depend on our faculty to properly identify the jump, which depends on the size of the jump |µ 1 -µ 0 | and of the time at which the jump occurs. For this reason, we consider intensity jumps of 20 %, 10 % and 5 % between µ 0 and µ 1 . We consider, for each case, the situation of a "late" (resp. "early") change-point date, that is k = 17 (resp. denotes the estimated intensity obtained by our procedure, and λ 0 denotes the estimated intensity without considering any change-point.

In this study, it clearly appears that, when we increase the size of the jump, the behaviour of our method in significantly improved for each parameter of the model and for each criterion. Compared to Cox's partial likelihood approximations, the estimation of β obtained by our method leads to far better estimation results. Besides, estimates of the intensities µ 0 and µ 1 are more accurate when the change-point occurs later (i.e.

when k increases). Concerning the global estimation of the hazard function λ, our changepoint model (λ TRUE ) leads to significant improvements compared to the approach with no change-point (λ 0 ), except for small sizes of jumps and early date of change-point. In this latter case, we observe slightly poorer results. This mainly comes from the fact that the error in estimating µ 0 , µ 1 and k is higher. However, the estimation of β seems still relevant even in this extreme case.

Second case: two change-points.

In the two change-points case, the process is characterized by

θ = (β, k 1 , k 2 , µ 0 , µ 1 , µ 2 ),

Comparison with Cox's proportional hazards model

The continuous one-jump counting process that we modelize by (2.1) is only observed at n + 1 dates t i 0≤i≤n . The event times are thus grouped into intervals and it implies many tied event times, especially in the case defined in the application of section 4.3. In this context, as explained by [START_REF] Therneau | Modeling Survival Data, Extending the Cox Model[END_REF], two options are possible to apply Cox maximum partial likelihood estimation. The first one is to consider the process as a discrete time process. In addition to this incorrect assumption, the maximization of the exact partial likelihod requires a much important computation time. The second one is to keep the continuous time scale and maximize an approximation of the partial likelihood either from Breslow's or Efron's method [START_REF] Breslow | Covariance analysis of censored survival data[END_REF][START_REF] Efron | The efficiency of Cox's likelihood function for censored data[END_REF]. Computationally, these two methods require also an increasing time when the number of ties becomes high. Hertz-Picciotto and Rockhill (1997) compared the two approximations, showing that Efron's method is more accurate especially for a high number of ties.

Our model is neither based on the assumption of discrete time scale nor on an approximate likelihood. Moreover, the algorithm described in section 3.2 does not require a high computational time.

Besides, the specification of the form of the baseline hazard allows a more accurate estimation than in classical semi-parametric context and an easier interpretation of this part of the model. The baseline function represents the intrinsic dynamics of the process while the regression part stands for the influence of the variable on the dynamics. Assumption 2.2 means that we assume l + 1 homogeneous periods in the internal dynamics of the process.

In our model, if we increase β, we mechanically increase the number of tied event times. Therefore, we illustrate in Table 3 We considered different models with a fixed number l of change-points. The table 4 below presents the results for l = 1, . . . , 8. We explain later how we selected the model that seemed to us the most appropriate.

We observe that, the more change-points are estimated, the less important is the influence of the "rival" class. If we assume 3 change-points (i.e. 4 homogeneous reservation periods), the risk of reservation is multiplied by e 0.660 = 1.93 as soon as the "rival" class is closed to reservation.

Model selection

In the following figure, we plotted the values of the maximized log-likelihood, with respect to the number of change-points l that are considered in the model. Since the models are nested, this log-likelihood increases with l. After a fast increase between 1 and 5, the increase slows down, and the curve becomes almost linear. A possible model choice would consist of taking l = 5 or 6, since after that, the improvement of the log-likelihood does not seem particularly important. Alternatively to this graphical method, one can rely on techniques such as "slope heuristic", see e.g. Baudry, Maugis and Michel (2012). The technique consists of determining the slope p of the linear part of the log-likelihood curve (here, the part of the curve between l = 5 and l = 16), and use this slope to determine a penalized criterion. The penalized criterion which is recommended is obtained as follows,

l = argmax l max θ L l (θ) -2pl.
In our application, we estimate the following value p = 10.662 of the slope. In the following table, the penalized criterion max θ L l (θ) -2pl is shown for different values of l. q q q q q q q q q q q q q q q q q Number of change-points Log-likelihood q q q q q q q q q q q q q q q q q 0 5 10 15 l = 8 3000 4000 5000 6000 7000 8000 q q Log-likelihood Slope estimation Penalized log-likelihood It appears that, according to this criterion, the selected model would be l = 8. However, since the penalized criterion does not increase strongly between l = 6 and l = 8, it may suggest that the models with 6 or 7 change-points are still reasonable candidates, if one wishes to promote models with fewer parameters.

Testing procedure results

Simulations and one-change-point detection

In order to assess the validity of the test procedures that we used on the real data-set, we can try to determine through simulation the power of our test procedure. In table 4.4 below, we present the results of this evaluation in the most simple case, that is when we consider the simplest situation mentioned in section 3.4, where the null hypothesis corresponds to the no change-point situation, which is tested against an alternative corresponding to the one-change point situation. To simulate the law under the null hypothesis, we considered the value of β obtained on the sample, and we took µ 0 = 1. For each testing case (each compartment of the following table), we simulate 1000 samples either from hypothesis H 0 (µ 0 = 1 ; column 1) or from hypothesis H 1 (µ 0 = 1 and various jumps to µ 1 ; see columns 3-5). In the latter case, we test different positions for the change-point: 7: Tests results for hypothesis H l : "There are l change-points" against H l+1 : "There are l + 1 change-points" (l = 0, . . . , 16) at the level α = 5%.

Compared to the model selection defined in section 4.3 above, the forward procedure leads to l = 10 change-points at the level of α = 5%.

Conclusion

In this paper, we proposed a statistical model that is adapted to the study of a counting process which is influenced by some covariates and structural changes in the baseline hazard function. Estimation is performed through an iterative algorithm that combines dynamic programming for the change-point part, and a regular maximum likelihood estimation phase in a multiplicative hazard regression model. Numerical investigation show that our procedures seems to behave correctly, even for small sample sizes. In the particular case of the SNCF data that we studied, they allowed us to detect some change in the dynamics of the reservation which is not completely caused by the fluctuations of the availability for the different categories of seats. They provide a simple modelization of the characteristics of the reservation process, which then can be used in a simulation phase, in order to simulate the impact of different commercial strategies, making this approach quite valuable for Yield-Management.

  2) is inspired by the field of change-point analysis, it is quite natural to use the estimators we develop to perform change-point detection in the baseline hazard rate. Change-point detection (see Csorgo and Horvath 1997; or Basseville and Nikiforov 1993) aims to identify abrupt changes in some parameter. In our framework, detecting a change-point will conclude to an instability of the baseline which is not due to the influence of the covariates.

2 . 3 .

 23 points, against the model with (k -1)-change-points. Then, it can be used as a forward procedure to decide what number of change-points should be considered (see application in section 4.4).Simulation technique to compute the critical value1. Estimation : first, we estimate θ1 from the data. If H 0 is true, the probability law defined by θ1 should be close to the true probability distribution. Simulation : for b = 1, . . . , B simulate a multivariate process according to the law defined by θ1 and (X ij , Y ij ) 0≤i≤n1≤j≤m , where we used the matrix X and Y observed on the data-set. Computation of the critical value : for each of the simulated trajectory, compute θb 1 (the estimator based on the b-th simulated trajectory, with the assumption that there is no change-point), and θb 2 (the estimator based on the b-th simulated trajectory, with the assumption that there is one change-point), and compute the corresponding test statistic T b n . Take s α such as a proportion α of the (T b n ) 1≤b≤B is larger than s α .

k = 7 )

 7 over a total number n = 20 of dates, and an intermediate situation (k = 11).

where (k 1 , k 2 )

 12 are the ranks of the times of change t k 1 , t k 2 and (µ 0 , µ 1 , µ 2 ) are the intensities in the three periods defined by the change-points. As in the previous case, we considered different values of these parameters in order to assess the quality of the estimations. We have first simulated datasets where the ranks of the two change-points are quite close (separated by 3 ranks). The change-points are assumed to occur "late" ((k 1 , k 2 ) = (14, 17)) or at an intermediate date ((k 1 , k 2 ) =[START_REF] Breslow | Covariance analysis of censored survival data[END_REF][START_REF] Dabrowska | Smoothed Cox regression[END_REF]). We also consider the case where the two change-points divide the time in three approximately equal periods ((k 1 , k 2 ) =[START_REF] Breslow | Contribution to the discussion of the paper by Dr. Cox[END_REF][START_REF] Dabrowska | Smoothed Cox regression[END_REF]). The same jump of 10% is applied at the first change point and jumps of size 0.05, 0.1 or 0.2 from the value 1.1 are used at the second change-point.

  denotes the estimated intensity obtained by our procedure, and λ 0 denotes the estimated intensity without considering any change-point.Comparing the estimations for (k 1 , k 2 ) =[START_REF] Hertz-Picciotto | Validity and efficiency of approximation methods for tied survival times in Cox regression[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of Gaussian process by model selection[END_REF] and (k 1 , k 2 ) =[START_REF] Breslow | Covariance analysis of censored survival data[END_REF][START_REF] Dabrowska | Smoothed Cox regression[END_REF], we observe, as in previous case, that the estimates of µ 0 , µ 1 are more accurate when the changepoints occur later. According to the e i (λ TRUE ) and e i (λ 0 ) criterions, as in the previous case, the improvement of global estimation of λ is stronger when change-points occur later ((k 1 , k 2 ) =[START_REF] Hertz-Picciotto | Validity and efficiency of approximation methods for tied survival times in Cox regression[END_REF][START_REF] Lebarbier | Detecting multiple change-points in the mean of Gaussian process by model selection[END_REF]) and weaker or non-existent when changes are smaller and occur earlier ((k 1 , k 2 ) =[START_REF] Breslow | Covariance analysis of censored survival data[END_REF][START_REF] Dabrowska | Smoothed Cox regression[END_REF]).However, in the case where the change-points are uniformly located ((k 1 , k 2 ) = (7, 15)) our model with the change-points (λ TRUE ) provides the best improvement to the nochange-point model (λ 0 ).

  below how the quality of estimation of the Estimation We fix a model by determinating the number l of change-points in the baseline hazard function and then estimate the parameter θ = β, (k, µ) . The regression parameter β represents the influence of "rival" tariff class or train while the change-point parameters (k, µ) explain the structural increase (or decrease) of the reservations in the considered tariff class or train.

Figure 1 :

 1 Figure 1: Log-likelihood, penalized likelihood and estimation of linear regression coefficients (slope: 10.66172, intercept: 8096.505).

Table 1

 1 below presents the results for the different settings.

	k = 11
	k = 17

Table 1 :

 1 Estimation performance in several situations in the one-change-point case, β (Ef.) (resp. β (Br.

)) denotes estimator of β using Efron's (resp. Breslow's) approximation of Cox's partial likelihood, λ TRUE

Table 2

 2 below presents the results for the different settings.

	(k1, k2) = (7, 15)	e1 e2 e∞	0.062534508 0.005973307 0.237327399	1.311279 1.723167 1.477761	1.753362 3.075044 1.832443	0.072414961 0.009407029 0.500000000	0.10711075 0.01917136 0.53349325	0.10035438 0.01467417 0.33134670	117.93811 49.19202 919.02605	202.1427 131.6136 1522.3824	e1 e2 e∞	0.064078998 0.006029081 0.232295462	1.291754 1.672550 1.462749	1.742895 3.038508 1.818627	0.08234189 0.01205407 0.47619048	0.10808110 0.02115315 0.60000000	0.09388448 0.01306089 0.35813276	120.11474 47.19206 889.99899	122.17310 42.38263 1062.88695	e1 e2 e∞	0.061757848 0.005693481 0.220565021	1.279627 1.641281 1.460097	1.738093 3.021759 1.809625	0.09013876 0.01472177 0.50000000	0.11863639 0.02557955 0.57619048	0.0933072 0.0130673 0.3777881	117.51992 44.05131 915.34084	87.96409 20.06260 846.32478
			β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0		β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0		β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0
	(k1, k2) = (8, 11)	e1 e2 e∞	0.057574912 0.005021856 0.208565731	1.370795 1.882647 1.563088	1.779649 3.167793 1.856412	0.07724306 0.01202679 0.47619048	0.13692390 0.02955524 0.59181152	0.09173299 0.01279416 0.34997984	118.39842 50.53192 936.53635	157.05333 79.28889 1735.06326	e1 e2 e∞	0.059986231 0.005482251 0.242598120	1.321616 1.750359 1.509318	1.756059 3.084520 1.832974	0.08362933 0.01356685 0.52380952	0.13430696 0.02873167 0.52514781	0.0919037 0.0126769 0.3263178	117.22853 46.53641 947.02413	107.33235 32.49791 1177.55438	e1 e2 e∞	0.063798466 0.006068773 0.237228090	1.291749 1.672146 1.447051	1.742821 3.038196 1.820148	0.08784710 0.01502091 0.52380952	0.13949539 0.03164465 0.60000000	0.09287966 0.01340663 0.44032470	114.43641 43.64743 946.78327	87.85115 19.70437 891.63818
			β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0		β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0		β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0
	(k1, k2) = (14, 17)	e1 e2 e∞	0.064817713 0.006190545 0.219135497	1.229069 1.514848 1.397504	1.707914 2.917884 1.790513	0.06612649 0.01004802 0.61904762	0.08908864 0.01414965 0.46696570	0.10179238 0.01535896 0.38695007	120.06754 52.40541 716.98462	269.0137 248.2904 1217.5827	e1 e2 e∞	0.064260237 0.005961951 0.223232609	1.219214 1.490809 1.417622	1.703353 2.902389 1.787137	0.07482665 0.01169863 0.52380952	0.08821589 0.01389789 0.54378136	0.09488646 0.01298862 0.30831266	121.72250 51.53993 735.02953	174.2237 107.9067 863.8115	e1 e2 e∞	0.065146666 0.006358655 0.267650610	1.213334 1.476361 1.415002	1.704309 2.905729 1.791570	0.08330602 0.01432253 0.57142857	0.0981028 0.0173706 0.5854899	0.09547936 0.01377333 0.36256315	119.08308 48.22871 753.01141	130.93558 62.17867 685.58948
			β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0		β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0		β	β (Ef.)	β (Br.)	µ0	µ1	µ2	λ TRUE	λ 0
					µ0 = 1,	µ1 = 1.1,	µ2 = 1.3						µ0 = 1,	µ1 = 1.1,	µ2 = 1.2						µ0 = 1,	µ1 = 1.1,	µ2 = 1.15

Table 2 :

 2 Estimation performance in several situations in the two-change-points case, β (Ef.) (resp. β (Br.)) denotes estimator of β using Efron's (resp. Breslow's) approximation of Cox's partial likelihood, λ TRUE

Table 4 :

 4 Estimates of θ = β, k

	k
	β
	l

1 , . . . , k l , µ 0 , . . . , µ l for l = 1, . . . , 8 for the real data set.

Table 5 :

 5 Log-likelihood and penalized log-likelihood for l = 0, . . . , 16.

	l Log-likelihood L l	L l -2pl
	0	2806.6728312	2806.6728312
	1	6716.8506334	6695.527
	2	7477.5020833	7434.855
	3	7687.344	7623.374
	4	7876.631	7791.337
	5	8102.203	7995.586
	6	8140.190	8012.249
	7	8174.818	8025.554
	8	8208.273	8037.685
	9	8219.261	8027.35
	10	8228.928	8015.694
	11	8235.892	8001.334
	12	8237.372	7981.491
	13	8238.118	7960.913
	14	8238.532	7940.004
	15	8238.85936440	7919.008
	16	8238.99457638	7897.82

Table

	l	Test statistic Threshold sα Rejection of H0
	0	3910.17780	3.79950	Yes
	1	760.65144	4.01493	Yes
	2	209.84210	4.35410	Yes
	3	189.2871	4.36418	Yes
	4	225.5715	3.99669	Yes
	5	37.98701	4.184904	Yes
	6	34.62845	4.128622	Yes
	7	33.45466	4.014498	Yes
	8	10.98819	4.050255	Yes
	9	9.666715	3.830744	Yes
	10	6.964444	3.595357	Yes
	11	1.479882	3.321706	No
	12	0.7458188	2.506621	No
	13	0.4144982	1.873998	No
	14	0.3268795	1.269713	No
	15	0.1352120	0.9744056	No
	16	0.3290045	0.6506319	No

The proportional hazards model presented in this paper has been developed to describe reservation process but can also be used in recurrent event data analysis as well as survival data analysis as an alternative for parametric and Cox proportional hazards model.

regression parameter evolves when we increase β. The errors are normalized in order to be able to compare each case. We consider a one change-point situation, with k = 11, µ 0 = 1 and µ 1 = 1.2.

In this table, the error criterions are normalized with respect to β. The approximations of [START_REF] Efron | The efficiency of Cox's likelihood function for censored data[END_REF] and [START_REF] Breslow | Covariance analysis of censored survival data[END_REF] seem to lead to relative errors that increase with β, which is not the case using our procedure. Moreover, the computation time increases considerably for Cox's approximations when β increases, while the computation is not impacted in our approach.

Real data set: reservations to train (SNCF)

The model presented in this paper has been applied in the practical case of reservations data in the French railway company Sncf. Booking process is observed, for a determined tariff class, on n+1 = 21 dates t i 0≤i≤n . N j (t) denotes the cumulated number of bookings in the train j (for j = 1, . . . , m = 42) between 0 and time t. In our particular dataset, we have Y j (t) ≡ 1, although the techniques applies for more general situations. The aim of the study is to identify the impact of "rival" tariff classes on the booking process. We considered the case of a single rival class, corresponding to a less expensive tariff. To measure the impact of this class, we consider the process X(t), taking value 0 if the rival class is still open at time t, and taking value 1 otherwise. In the situation we considered, rival classes do not re-open after being closed, although this situation could be considered through our model. late (k = 17), middle (k = 11) or early (k = 5). For every sample, we simulate B = 100 observations (T j n ) 1≤j≤B of the test statistic and compare T n to the obtained threshold s α (α = 5%). We report in the table the proportion of rejection of H 0 over the 1000 simulated samples.

No change point

One change-point

Table 6: Tests results under hypothesis H 0 and H 1 .

We observe that, under the null hypothesis (which corresponds to the case k = 21), the simulation approach almost achieves the expected level which was 5%. The earlier change-point occurs, easier is the detection. Indeed, the results show an increase of the power of the test when the alternative is k = 11. Nevertheless, the size of the change, that is the difference between µ 0 and µ 1 , has a more significant impact. In the case where