Lianmeng Jiao
email: lianmeng.jiao@utc.fr

Quan Pan
email: panquannpu@gmail.com

Xiaoxue Feng
email: xiaoxue.feng@utt.fr

Multi-hypothesis nearest-neighbor classifier based on class-conditional weighted distance metric

Keywords: Pattern classification, Weighted distance metric, Multi-hypothesis nearest-neighbor classifier, Dempster-Shafer theory

The performance of nearest-neighbor (NN) classifiers is known to be very sensitive to the distance metric used in classifying a query pattern, especially in scarce-prototype cases. In this paper, a class-conditional weighted (CCW) distance metric related to both the class labels of the prototypes and the query patterns is proposed. Compared with the existing distance metrics, the proposed metric provides more flexibility to design the feature weights so that the local specifics in feature space can be well characterized. Based on the proposed CCW distance metric, a multi-hypothesis nearest-neighbor (MHNN) classifier is developed. The scheme of the proposed MHNN classifier is to classify the query pattern under multiple hypotheses in which the nearest-neighbor sub-classifiers can be implemented based on the CCW distance metric. Then the classification results of multiple sub-classifiers are combined to get the final result. Under this general scheme, a specific realization of the MHNN classifier is developed within the framework of Dempster-Shafer theory due to its good capability of representing and combining uncertain information. Two experiments based on synthetic and real data sets were carried out to show the effectiveness of the proposed technique.

Introduction

The nearest-neighbor (NN) rule, first proposed by Fix and Hodges [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF], is one of the most popular and successful pattern classification techniques. Given a set of N labeled samples (or prototypes) T = {(x (1) , ω (1) ), • • • , (x (N) , ω (N) )} with input vector x (i) ∈ R D and class label ω (i) ∈ {ω 1 , • • • , ω M }, the NN rule classifies a query pattern y ∈ R D to the class of its nearest neighbor in the training set T . The basic rationale of the NN rule is both simple and intuitive: patterns close in feature space are likely to belong to the same class. The good behavior of the NN rule with unbounded numbers of prototypes is well known [START_REF] Cover | Nearest neighbor pattern classification[END_REF]. However, in many practical pattern classification applications, only a small number of prototypes are available. Typically, under such a scarce-prototype framework, the ideal asymptotical behavior of the NN classifier degrades dramatically [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]. This problem has driven the growing interest in finding variants of the NN rule and adequate distance measures (or metrics) that help improve the NN classification performance in small data set situations.

As the core of the NN rule, the distance metric plays a crucial role in determining the classification performance.

To overcome the limitations of the original Euclidean (L2) distance metric, a number of adaptive methods have recently been proposed to address the distance metric learning issue. According to the structure of the metric, these methods can be mainly divided into two categories: global distance metric learning and local distance metric learning [START_REF] Wang | Globality and locality incorporation in distance metric learning[END_REF]. The first learns the distance metric in a global sense, i.e., to share the same simple weighted (SW) distance metric for all of the prototypes:

d S W (x, y) = D ∑ j=1 λ 2 j (x j -y j ) 2 , ( 1
)
where x is a prototype in the training set, y is a query pattern to be classified, and λ j is the weight of the j-th feature.

Based on the above distance metric, the feature weights learning in [START_REF] Bar-Hillel | Learning distance functions using equivalence relations[END_REF][START_REF] Zhang | Parametric distance metric learning with label information[END_REF] is formulated as a linear programming problem that minimizes the distance between the data pairs within the same classes subject to the constraint that the data pairs in different classes are well separated. Eick et al. [START_REF] Eick | Using clustering to learn distance functions for supervised similarity assessment[END_REF] introduce an approach to learn the feature weights that maximize the clustering accuracy of objects in the training set, and similarly, the classification error rate of objects in the training set is employed to evaluate the feature weights in [START_REF] Han | Text categorization using weight-adjusted nearest-neighbor classification[END_REF]. Although the above global distance metric learning methods are intuitively correct, they are too coarse, as the feature weights of the distance metric are irrelevant with the prior-known class labels of the prototypes. This issue becomes more severe when some features behave distinctly for different classes (for example, one feature may be more discriminative for some classes but less relevant for others) [START_REF] Friedman | Flexible metric nearest neighbor classification[END_REF]. Thus, many methods [START_REF] Domeniconi | Locally adaptive metric nearest neighbor classification[END_REF][START_REF] Wang | Improving nearest neighbor rule with a simple adaptive distance measure[END_REF][START_REF] Jahromi | A method of learning weighted similarity function to improve the performance of nearest neighbor[END_REF][START_REF] Zhang | Semi-supervised distance metric learning based on local linear regression for data clustering[END_REF][START_REF] Jiao | An evidential k-nearest neighbor classification method with weighted attributes[END_REF] have been developed to learn a distance metric in a local setting, i.e., the feature weights may be different for different prototypes. The most representative method is the class-dependent weighted (CDW) distance metric proposed by Paredes and Vidal [START_REF] Paredes | A class-dependent weighted dissimilarity measure for nearest neighbor classication problems[END_REF][START_REF] Paredes | Learning weighted metrics to minimize nearest-neighbor classification error[END_REF], which is related to the class index of the prototype:

d CDW (x, y) = D ∑ j=1 λ 2 c, j (x j -y j ) 2 , ( 2
)
where c is the class index of prototype x. Although the above CDW distance metric provides more freedom than the SW metric, the following example illustrates that this distance metric is insufficient to reflect the local specifics in feature space for query patterns in different classes. Fig. 1 illustrates a simple three-class classification problem, where the data in each class are uniformly distributed. (x (1) , A), (x (2) , B) and (x (3) , C) are two-dimensional data points in training set T . y 1 and y 2 are the query data to be classified. Considering the classification of data y 1 , when calculating the distance between x (2) and y 1 , intuitively, to avoid classifying it to Class B mistakenly, the feature value in the X-axis should be given a larger weight. However, in classifying data y 2 , it is reasonable that the feature value in the Y-axis should be given a larger weight to determine the distance between x (2) and y 2 . That is, the feature weights x (1) (9,6)

x (2) (11,9)

x (3) [START_REF] Jiao | An evidential k-nearest neighbor classification method with weighted attributes[END_REF][START_REF] Wang | Improving nearest neighbor rule with a simple adaptive distance measure[END_REF] y 1 [START_REF] Friedman | Flexible metric nearest neighbor classification[END_REF][START_REF] Friedman | Flexible metric nearest neighbor classification[END_REF] • y 2 [START_REF] Wang | Improving nearest neighbor rule with a simple adaptive distance measure[END_REF][START_REF] Wang | Improving nearest neighbor rule with a simple adaptive distance measure[END_REF] Figure 1: A three-class classification example.

should also be related to the class labels of the query patterns to be classified.

Motivated by the above consideration, in this paper we propose a more general distance metric that associates with both the class labels of the prototypes and the query patterns. As in classification problems the class label of the query pattern is not prior-known, this general distance metric only makes sense when conditioned on the assumption that the query pattern belongs to a specified class. Therefore, we define this type of variant as a class-conditional weighted (CCW) distance metric. Compared with the existing distance metrics mentioned above, the CCW metric provides more flexibility to design the feature weights so that the local specifics in feature space can be well characterized.

Based on the CCW distance metric, this paper develops a multi-hypothesis nearest-neighbor (MHNN) classifier.

The main scheme of this method is to classify the query pattern under multiple hypotheses in which the nearestneighbor sub-classifiers can be implemented based on the CCW distance metric and then to combine the classification results of multiple sub-classifiers to obtain the final result. A variety of schemes have been proposed for deriving a combined decision from individual decisions, such as majority voting [START_REF] Ruta | Classifier selection for majority voting[END_REF], Bayes combination [START_REF] Kuncheva | Decision templates for multiple classifier fusion: an experimental comparison[END_REF], multilayered perceptrons [START_REF] Suen | The combination of multiple classifiers by a neural network approach[END_REF], and the Dempster-Shafer theory (DST) [START_REF] Quost | Classifier fusion in the Dempster-Shafer framework using optimized t-norm based combination rules[END_REF][START_REF] Tabassian | Combination of multiple diverse classifiers using belief functions for handling data with imperfect labels[END_REF][START_REF] Naeini | Learning by abstraction: Hierarchical classification model using evidential theoretic approach and bayesian ensemble model[END_REF]. In this paper, a specific realization of the MHNN classifier is developed within the framework of DST due to its good capability of representing and combining uncertain information which is always encountered in classification problems.

The rest of this paper is organized as follows. In Section 2, the class-conditional weighted distance metric is defined and then both a heuristic method and a parameter optimization procedure are designed to derive the involved feature weights. The multi-hypothesis nearest-neighbor classifier is designed and realized within the framework of DST in Section 3. Two experiments are given to evaluate the performance of the proposed method in Section 4.

Finally, Section 5 concludes the paper.

Class-conditional weighted distance metric

Definition

Before defining the class-conditional weighted distance metric for the purpose of classification, we will first give a general weighted distance metric between two patterns with prior-known class labels as follows.

Definition 1 (General weighted distance metric). Suppose x (m) and x (n) are two D-dimensional patterns with class labels ω p and ω q . A general weighted distance metric between x (m) and x (n) can be defined as

d(x (m) , x (n) ) = D ∑ j=1 λ 2 p,q, j (x (m) j -x (n) j ) 2 , (3)
where λ p,q, j is a constant that weights the role of the j-th feature in the distance metric between class ω p and class ω q .

This definition includes, as particular cases, the distance metrics revisited in the Introduction. If λ p,q, j = 1 for all

p = 1, • • • , M, q = 1, • • • , M, j = 1, • • • , D,
the above distance metric is just the L2 distance metric. Moreover, the SW and CDW distance metrics correspond to the cases where the metric weights are not relevant to the class labels or are only dependent on the class label of the first pattern, respectively. Therefore, the above weighted distance metric provides a more general dissimilarity measure than the L2, SW or CDW metrics because the weights depend on both class labels of the two considered patterns.

In NN-based classification, the problem is to calculate the distance between a prototype and a query pattern, while the class label of the latter is not prior-known. So, for the purpose of classification, the above general distance metric only makes sense conditioned on the assumption that the query pattern belongs to a specified class ω q . We will define this type of variant as follows.

Definition 2 (Class-conditional weighted distance metric). Let T = {(x (1) , ω (1) ), • • • , (x (N) , ω (N) )} be a set of prototypes. The class-conditional weighted (CCW) distance metric between a query pattern y and a prototype x ∈ T can be defined as

d CCW (x, y) = D ∑ j=1 λ 2 p,q, j (x j -y j ) 2 , (4)
where, p is the class index of the prototype x and q is the hypothesized class index of the query pattern y.

Remark 1. The defined CCW distance metric has some advantages over the existing metrics. The most obvious advantage is that it provides more flexibility to design the feature weights so that the local specifics in feature space can be well characterized. Take the three-class classification problem studied in the Introduction, for example. In Fig. 1, using the CCW distance metric, to classify y 1 to Class A, λ B,A,X (the first two subscripts denote the class labels, while the third subscript denotes the feature index) can take a much larger value than λ B,A,Y , while one can assign smaller value for λ B,C,X than λ B,C,Y to classify y 2 to Class C.

Heuristically deriving feature weights

In the previous subsection, the definition of the CCW distance metric was given and the advantages of this proposed distance metric were noted. The only open parameters in the CCW distance metric are the feature weights that associate with both the class labels of the prototypes and the query patterns. This section aims to derive the feature weights λ p,q, j (p = 1,

• • • , M, q = 1, • • • , M, j = 1, • • • , D) from the
T k = {x (i) } (i ∈ I k ), (5)
where I k is the set of indices of the training data x (i) belonging to the class ω k .

Let us take into consideration the feature mean vector µ k and feature variance vector Σ k estimated on the set T k

µ k = ∑ i∈I k x (i) /n k , Σ k = ∑ i∈I k (x (i) -µ k ) 2 /(n k -1), (6)
where, the feature mean vector

µ k denotes {µ k,1 , • • • , µ k,D } and the feature variance vector Σ k denotes {σ 2 k,1 , • • • , σ 2 k,D }.
Here, the feature weights associated with classes ω p and ω q are derived based on the following two commonsense rules:

• The closer the feature centers (approximately represented by the feature mean vectors), the more difficult the classification by this feature.

• The more dispersive the feature distributions (approximately represented by the feature variance vectors), the more difficult the classification by this feature.

Based on the above rules, in determining the CCW distance metric between two different classes ω p and ω q (p q), the feature weights should monotonically increase with the distance of the feature centers (i.e., |µ p, j -µ q, j |) and monotonically decrease with the sum of the feature distributions (i.e., σ p, j + σ q, j ). Intuitively, we can construct λ p,q, j as

λ p,q, j = |µ p, j -µ q, j |/(σ p, j + σ q, j ), for j = 1, • • • , D. ( 7
)
When measuring the CCW distance between two patterns belong to the same class ω p (i.e., p = q), the first commonsense rule no longer takes effect, and the feature weights λ p,p, j can be constructed as

λ p,p, j = 1/σ p, j , for j = 1, • • • , D. (8)
Lastly, the feature weights should be normalized so that ∑ D j=1 λ p,q, j = 1. Similarly, we can obtain the feature weights λ p,q, j , j = 1, • • • , D for all other class sets T p , p = 1, • • • , M and T q , q = 1, • • • , M, which are prepared for the classifying process.

Remark 2. From Eqs.( 7)-( 8), we can see that ∀p ∈ {1, • • • , M} and ∀q ∈ {1, • • • , M}, λ p,q, j = λ q,p, j for all j = 1, • • • , D. That is, the proposed CCW metric satisfies the symmetry property, which reduces the number of parameters to M(M + 1)D/2.

Feature weight optimization

In the above subsection, a heuristic derivation of feature weights λ p,q, j (p = 1,

• • • , M, q = 1, • • • , M, j = 1, • • • , D)
was given, and it is supposed that the performance of the classification procedure can be further improved if these parameters are learned from the training set via optimizing certain criteria. A simple way of defining the criteria for the desired metric is to keep the data pairs from the same class close to each other while separate those data pairs from different classes far from each other.

Let the set of data pairs from the same class ω p be denoted by

S p,p = {(x (m) , x (n) )|m, n ∈ I p ; m n}
and the set of data pairs from different classes ω p and ω q be denoted by

D p,q = {(x (m) , x (n) )|m ∈ I p ; n ∈ I q ; p q}.
To measure the CCW distance between two patterns belonging to the same class ω p , the feature weights λ p,p, j

( j = 1, • • • , D) can be optimized via minimizing the inner-class distance criterion min λ p,p, j ∑ (x (m) ,x (n) )∈S p,p d 2 CCW (x (m) , x (n) ) s.t. λ p,p, j > 0, j = 1, • • • , D and ∑ D j=1 λ p,p, j = 1. (9)
In determining the CCW distance metric between two different classes ω p and ω q (p q), the feature weights λ p,q, j ( j = 1, • • • , D) can be optimized via maximizing the between-class distance criterion max

λ p,q, j ∑ (x (m) ,x (n) )∈D p,q d 2 CCW (x (m) , x (n) ) s.t. λ p,q, j > 0, j = 1, • • • , D and ∑ D j=1 λ p,q, j = 1. ( 10
)
Remark 3. For the above two optimization problems, the objectives are quadratic functions of the feature weights λ p,p, j or λ p,q, j , and both constraints are easily verified to be convex. Thus, the optimization problems are convex and can be solved using existing optimization software packages, such as the MATLAB optimization toolbox [START_REF] Coleman | Optimization Toolbox -For Use With MATLAB[END_REF].

Moreover, the feature weights derived heuristically in the previous subsection can be used as the initial estimates to shorten the optimization time.

Multi-hypothesis nearest-neighbor classifier

As in the classification process the class label of the query pattern is not prior-known, the proposed CCW distance metric should be used based on the hypothesized class label. For this consideration, this section develops a multihypothesis nearest-neighbor (MHNN) classifier based on the CCW distance metric. This approach first classifies the query pattern under multiple hypotheses in which the nearest-neighbor sub-classifiers can be implemented based on the proposed CCW distance metric and then combines the classification results of multiple sub-classifiers to obtain the final result. In Section 3.1, the general scheme of the proposed MHNN classifier is illustrated and analyzed, and then a specific realization within the framework of Dempster-Shafer theory is developed in Section 3.2. classifier is implemented based on the proposed CCW distance metric with the corresponding weights λ p,i, j ,

General scheme

p = 1, • • • , M, j = 1, • • • , D.
• Stage 2: Combination of multiple sub-classifiers. The classification results ω (1) , ω (2) , • • • ,ω (M) of the M subclassifiers under different hypotheses are fused to obtain the final result. with CDW-NN. Thus, it can be expected that through combination, the MHNN classifier will yield a much better performance.

Realization within the framework of Dempster-Shafer theory

Depending on the different combination methods employed in Stage 2 of the MHNN classification scheme, different types of realizations can be obtained. In this paper, we combine the output of multiple sub-classifiers within the framework of Dempster-Shafer theory (DST) [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], as it provides powerful tools for representing and combining uncertain information.

Using DST to solve a specific problem generally involves three processes: constructing the mass functions (or basic belief assignments) representing the uncertainties in the problem with independent items of evidence, then combining multiple mass functions into a single one, and lastly, making a decision based on the combined result.

Thus, after a brief introduction of the basics in DST, we will focus on the construction and combination of the basic belief assignments as well as the decision-making strategies in the MHNN classifier.

Basic concepts in DST

In DST, a problem domain is represented by a finite set For decision-making support, Smets [START_REF] Smets | Decision making in the TBM: the necessity of the pignistic transformation[END_REF] proposed the pignistic probability BetP(A) 1 to approximate the unknown probability in [Bel(A), Pl(A)], given by

Θ = {θ 1 , θ 2 , • • • , θ n } of
BetP(A) = ∑ B⊆Θ A∩B ∅ |A ∩ B| |B| m(B), (13)
where |X| stands for the cardinality of the set X.

1 from the Latin word pignus meaning a bet 8

Several distinct bodies of evidence characterized by different BBAs can be combined using Dempster's rule.

Mathematically, the Dempster's rule of combination of two BBAs m 1 (•) and m 2 (•) defined on the same frame of

discernment Θ is m(A) =              0, for A = ∅ ∑ B,C∈2 Θ ;B∩C=A m 1 (B)m 2 (C) 1- ∑ B,C∈2 Θ ;B∩C=∅ m 1 (B)m 2 (C) , for A ∈ 2 Θ and A ∅. (14)
As described in [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], Dempster's rule of combination is both commutative and associative.

The construction of BBAs in the MHNN classifier

This section aims to construct the BBAs from the M sub-classifier output Being affected by the noises of the patterns, the classification results of the sub-classifiers do not always have full accuracy. For any sub-classifier under hypothesis H i , the result ω (i) = ω q can be regarded as a piece of evidence that increases the belief that the query pattern y belongs to ω q . However, this piece of evidence does not by itself provide 100% certainty. In DST formalism, this can be expressed by saying that only some part of the belief is committed to ω q . Because ω (i) = ω q does not point to any other particular class, the rest of the belief should be assigned to the frame of discernment Ω representing global ignorance. Therefore, this item of evidence can be represented by a BBA

ω (i) , i = 1, • • • , M.
m(• | H i ) verifying:                  m({ω q } | H i ) = α i m(Ω | H i ) = 1 -α i m(A | H i ) = 0, ∀A ∈ 2 Ω \ {Ω, {ω q }}, (15)
where α i ∈ [0, 1] represents the belief that the sub-classifier under the hypothesis H i provides the correct classification result.

Remark 5. Eq.( 15) can be seen as a discounting operation that discounts the classification result of each sub-classifier with its classification reliability. After discounting, only some part of the belief is assigned to the classification result of the sub-classifier and the rest of the belief is assigned to the frame of discernment which represents global ignorance.

Thus, with the discounting operation, the conflict among different pieces of evidence from different sub-classifiers can be highly reduced.

In determining the belief factors α i , i = 1, • • • , M, we divide the M sub-classifiers into two groups: sub-classifier with the correct hypothesis (i.e., ω (i) = ω i ), and those with incorrect hypotheses (i.e., ω (i) ω i ). As indicated in Section 3.1, the sub-classifiers with incorrect hypotheses reduce to CDW-NN and thus, on average, have larger classification error rates than the one with the correct hypothesis which is based on the proper CCW distance metric.

The belief factors can therefore be determined as

α i =          α CCW , if ω (i) = ω i α CDW , if ω (i) ω i for i = 1, • • • , M, (16)
where, α CCW and α CDW denote the classification accuracy based on the CCW and CDW distance metrics, respectively.

These parameters can be obtained via the leave-one-out (LOO) test2 on the training set.

The combination of BBAs in the MHNN classifier

To make a decision regarding the output of the M sub-classifiers, the corresponding BBAs constructed in the above part can be combined using Dempster's rule. However, as indicated in [START_REF] Wilson | Algorithms for Dempster-Shafer theory[END_REF], the direct use of the Dempster's rule will result in an exponential increase in computational complexity for the reason of enumerating all subsets or supersets of a given subset A of Ω, and the operation becomes impractical when the frame of discernment has more than 15 to 20 elements. The following part is intended to develop an operational algorithm for evidence combination, which reduces the computational complexity to linear time considering the fact that the focal elements of each associated BBA are all singletons except the ignorance set Ω.

Define I(i) as the set of the former i hypotheses

I(i) = {H 1 , H 2 , • • • , H i }. (17)
Let m(• | I(i)) be the BBA after combining all of the former i BBAs associated with I(i). Given the above definitions, a recursive evidence combination algorithm can be developed as follows

m({ω q } | I(i + 1)) = K I(i+1) [ m({ω q } | I(i)) • m({ω q } | H i+1 ) + m(Ω | I(i)) • m({ω q } | H i+1 ) +m({ω q } | I(i)) • m(Ω | H i+1 ) ] , q = 1, 2, • • • , M m(Ω | I(i + 1)) = K I(i+1) [m(Ω | I(i)) • m(Ω | H i+1 )] K I(i+1) = [ 1 - M ∑ j=1 M ∑ p=1,p j m({ω j } | I(i)) • m({ω p } | H i+1 ) ] -1 i = 1, 2, • • • , M -1, (18)
where K I(i+1) is a normalizing factor, so that

M ∑ q=1 m({ω q } | I(i + 1)) + m(Ω | I(i + 1)) = 1. Note that m({ω q } | I(1)) = m({ω q } | H 1 ) for q = 1, 2, • • • , M and m(Ω | I(1)) = m(Ω | H 1 )
, so this recursive evidence combination algorithm can initiate with the BBA under the first hypothesis H 1 . Accordingly, when the recursive index i comes to M -1, the final results m({ω q } | I(M)) and m(Ω | I(M)) (m({ω q }) and m(Ω) for short, respectively) are obtained by combining all of the M BBAs.

Decision-making strategies

For decision-making with hard partition, the belief function Bel(•), plausibility function Pl(•) and pignistic probability BetP(•) are common alternatives. Because the focal elements of the combined BBA m(•) are all singletons except the ignorance set Ω, the credibility, plausibility and pignistic probability of each class ω q are derived as follows

Bel({ω q }) = m({ω q }) Pl({ω q }) = m({ω q }) + m(Ω) BetP({ω q }) = m({ω q }) + m(Ω) M . (19)
for q = 1, 2, • • • , M. It is supposed that, based on this evidential body, a decision has to be made assigning query pattern y to one of the classes in Ω. Denote A q the action of assigning y to class ω q . Further suppose the loss incurred in the case of wrong classification is equal to one, while the loss corresponding to correct classification is equal to zero. Then, the lower, upper and pignistic expected losses [START_REF] Denoeux | A k-nearest neighbor classification rule based on dempster-shafer theory[END_REF] associated to action A q are given as follows

R * (A q ) = 1 -Bel({ω q }) R * (A q ) = 1 -Pl({ω q }) R bet (A q ) = 1 -BetP({ω q }). ( 20
)
Because of the particular structure of the combined BBA (i.e., the focal elements are either singletons or the whole frame Ω), it can be easily discovered that ω = arg min

ω q ∈Ω R * (A q ) = arg min ω q ∈Ω R * (A q ) = arg min ω q ∈Ω R bet (A q ) = arg max ω q ∈Ω m({ω q }). (21)
That is, the three strategies minimizing R * , R * , and R bet lead to the same decision, in which case the pattern is assigned to the class with the maximum basic belief assignment.

Some merits of the realization

Combining multiple sub-classifiers within the framework of DST has some potential benefits.

First, due to the noises of the patterns and the unfitness of the distance metrics, great uncertainty may exist in the classification results of the multiple sub-classifiers. Compared with the previously mentioned majority voting, Bayes combination and multilayered perceptions methods, the DST framework provides more powerful tools for representing and combining uncertain information [START_REF] Tabassian | Combination of multiple diverse classifiers using belief functions for handling data with imperfect labels[END_REF]. On the one hand, by representing each sub-classifier output with a BBA structure, different types of uncertainty (probability uncertainty and ignorance) can be well characterized.

On the other hand, with Dempster's rule of combination, the uncertain information of multiple pieces of evidence can be well considered to obtain the final results.

Second, this method can tackle the classification problem in which the class memberships of the training data are only partially known. 3 Well-labeled data are often difficult to obtain due to limitations of the underlying equipment, partial or uncertain responses in surveys, and so on [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF][START_REF] Jiao | Combining sources of evidence with reliability and importance for decision making[END_REF]. In this case, the classification results of the sub-classifiers will have imprecise and/or uncertain soft labels. Because both soft and crisp labels can easily be recast as BBAs, the uncertainty of the training sample can be well addressed within the framework of DST.

Third, the combined result based on DST gives more freedom to make decisions. In addition to the hard partition studied above, the soft partition [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF] is occasionally also needed when the conditional error of making a hard decision is high. In some applications (especially those related to defense and security, as in target classification [START_REF] Jiao | A belief-rule-based inference method for carrier battle group recognition[END_REF]), it is better to obtain a robust (and eventually partially imprecise) result that will become more precise with additional techniques than to obtain a precise result directly with high risk [START_REF] Liu | A new belief-based k-nearest neighbor classification method[END_REF][START_REF] Liu | Classification of uncertain and imprecise data based on evidence theory[END_REF]. Fortunately, the DST-based sub-classifier combination result is expressed in the form of BBA, which is originally a type of soft partition.

Fourth, this DST-based sub-classifier combination method can be applied to classify a query pattern with priori information if it is available, such as when a query pattern belonging to some classes with larger probability is known in advance. For our method, the priori information can be used to make decisions by providing an additional subclassifier with a proper output in the form of BBA, and this priori information can take effect in the combination process.

Experiments

The capabilities of the proposed MHNN classifier based on the CCW distance metric will be empirically assessed through two different types of experiments. In the first experiment, a synthetic data set is used to show the behavior of the proposed approach in a controlled setting. In the second experiment, several standard benchmark data sets from the well-known UCI Repository of Machine Learning Databases [START_REF] Merz | UCI Repository of Machine Learning Databases[END_REF] are considered to show that the proposed technique is uniformly adequate for a variety of tasks involving different data conditions, such as large/small training sets and large/small dimensionality.

Synthetic data

The three-class classification problem mentioned in the Introduction is evaluated here to compare our method with the original NN classifier based on the L2 distance metric (L2-NN) [START_REF] Fix | Discriminatory analysis, nonparametric discrimination: consistency properties[END_REF] and the NN classifier based on the CDW distance metric (CDW-NN) [START_REF] Paredes | A class-dependent weighted dissimilarity measure for nearest neighbor classication problems[END_REF][START_REF] Paredes | Learning weighted metrics to minimize nearest-neighbor classification error[END_REF]. The following class-conditional uniform distributions are assumed. Class A: training sets randomly drawn from the above distributions. A fixed test set of 300 query patterns, independently drawn from the same distributions, is used for error statistics. As seen from the result, the CDW-NN classifier is only slightly better than the original L2-NN classifier for small training sets. This is mainly because the CDW distance metric only characterizes the local specifics of the features with respect to the prototypes, while in this particular simulation scenario, for each class the statistical variances of the prototypes in different features (i.e., X-axis, Y-axis) are nearly the same. Under this circumstance, the CDW distance metric becomes asymptotically approximate to the L2 distance metric as the amount of training data increases. The proposed MHNN classifier produces a much lower error rate, as the CCW distance metric provides more local specifics of the features related to both the prototypes and the query patterns. Moreover, the performance improvement is particularly significant for small training sets, in which case the ideal asymptotical behavior of NN classifier degrades dramatically. We can also see that through feature weight optimization, the performance of the proposed method can be further improved, but not significantly. Thus, for highly time-constrained classification problems, the heuristic feature weight derivation method may be a better choice considering both the classification rate and the computation burden.

Benchmark data sets

In this second experiment, ten well-known benchmark data sets from UCI repository are used to evaluate the performance of the MHNN classifier. The main characteristics of the ten data sets are summarized in Table 1. classification result on the test data is calculated. For the relatively larger data sets, such as Letter and Satimage, the single partition into training and test sets specified in the UCI repository is adopted.

The classification results of the ten benchmark data sets are shown in Table 2. The significance of the differences between results is evaluated using a Mc Nemar test [START_REF] Dietterich | Approximate statistical tests for comparing supervised classification learning algorithms[END_REF] at the 5% level. For each data set, the best classification accuracy is underlined, and those that are significantly improved over the baseline L2-NN method are printed in bold.

As seen from these results, the MHNN classifier (with feature weights derived heuristically) presented in this paper outperforms the baseline L2-NN or CDM-NN in most of the data sets. Moreover, for the Balance, Diabetes, Liver, and Wine data sets, the improvements are statistically significant because the local distance metric plays a more crucial role in determining the NN-based classification performance for these scarce-prototype and large-dimensionality cases. To evaluate the computational consumption of the proposed MHNN method, the average classification CPU times of the different methods are listed in Table 3. The numerical experiments are executed by MATLAB7.12 in an HP EliteBook 8570p with an Intel(R) Core(TM) i7-3540M CPU @3.00 GHz and 8 GB memory. From the results, it can be seen that the proposed MHNN classifier has a relatively higher computational consumption, approximately M (the total number of classes) times higher than the original L2-NN classifier (because the MHNN classifier is quite time-saving in both the heuristic feature weight derivation and the multiple sub-classifier combination process, the time is mainly consumed in the classification process under multiple hypotheses). Fortunately, for most classification problems, such as the benchmark data sets studied here, the number of considered classes is not very large, so the computation cost of the MHNN classifier is not a significant problem.

To verify the performance of the proposed method more generally, we compare our results against several stateof-the-art classification methods tested in [START_REF] Michie | Machine Learning, Neural and Statistical Classification[END_REF]. These methods can be categorized into decision tree based methods (CART, Cal5, C4.5) and statistical methods (ALLOC80, Discrim, NBayes, Quadisc). For a complete description of these methods, the reader may refer to [START_REF] Michie | Machine Learning, Neural and Statistical Classification[END_REF]. Table 4 compares our results with those using the above methods on several data sets under the same experimental arrangement 4 . From these comparisons, it can be seen that the proposed MHNN classifier exhibits a uniformly good behavior for all of the data sets, while other procedures may work very well for some data sets but typically tend to worsen (dramatically in many cases) for the rest. a The numbers in brackets denote the accuracy orders of the eight methods.

Conclusion

To improve the performance of the NN-based classifier in small data set situations, a new distance metric, called the CCW distance metric, is proposed in this paper. Compared with the existing distance metrics, the CCW metric provides more flexibility to design the feature weights so that the local specifics in feature space can be well characterized. Based on the CCW distance metric, an MHNN classifier is developed that mainly includes two stages. In the first stage, the query pattern is classified under multiple hypotheses in which the nearest-neighbor sub-classifiers can be implemented based on the proposed CCW distance metric. In the second stage, the classification results of multiple sub-classifiers are combined within the framework of DST to obtain the final result. From the results reported in the last section, we can conclude that the proposed technique achieved a uniformly good performance when applied to a variety of classification tasks, including those with high dimensionality and sparse prototypes.

  training set in a heuristic way. We divide the training set T into M subsets T k , k = 1, • • • , M, with each T k containing all of the n k training data labeled to the same class ω k :

Figure 2 :•

 2 Figure 2: General scheme of the MHNN classifier

Remark 4 .

 4 As illustrated in Section 2, the proposed CCW distance metric provides more local specifics in feature space than the CDW metric, so the sub-classifier with the correct hypothesis in MHNN will have a lower classification error rate than the existing NN classifier based on CDW distance metric (CDW-NN for short) intuitively. Moreover, the other M -1 sub-classifiers with incorrect hypotheses are actually equivalent to CDW-NN because the CCW distance metric reduces to the CDW metric when the hypothesis about the class label of the query pattern fails (in which case, the class label of the query pattern has no effect for either distance metric in determining the feature weights). Therefore, any sub-classifier in MHNN has a better or at least equal classification performance compared

Elements A ∈ 2 Θ

 2 mutually exclusive and exhaustive hypotheses called the frame of discernment. A mass function or basic belief assignment (BBA) expressing the belief assigned to the elements of 2 Θ by a given source of evidence is a mapping function m(•): 2 Θ → [0, 1], such that m(∅) having m(A) > 0 are called focal elements of the BBA m(•). The BBA m(A) measures the degree of belief exactly assigned to a proposition A and represents how strongly the proposition is supported by evidence. The belief assigned to all of the subsets of 2 Θ is summed to unity, and there is no belief left to the empty set. The belief assigned to Θ, or m(Θ), is referred to as the degree of global ignorance. Shafer [25] also defines the belief function and plausibility function of A ∈ 2 Θ as follows Bel(A) = ∑ B⊆A m(B) and Pl(A) ) represents the exact support to A and its subsets, and Pl(A) represents all of the possible support to A and its subsets. The interval [Bel(A), Pl(A)] can be seen as the lower and upper bounds of support to A. The belief functions m(•), Bel(•) and Pl(•) are in one-to-one correspondence.

  From the view of DST, the class set Ω = {ω 1 , • • • , ω M } can be regarded as the frame of discernment of the problem.

[ 2 ,

 2 10] × [2, 10]; Class B: [10, 18] × [2, 10]; Class C: [10, 18] × [10, 18].

Fig. 3

 3 Fig.3 shows classification error rates of L2-NN, CDW-NN, MHNN and MHNN with optimized feature weights (MHNN Opt.) for different training set sizes. For each size, each classification algorithm runs 100 times with different

Figure 3 :

 3 Figure 3: Classification error rates of our proposed method in comparison with other methods with different training set sizes.

Figure 4 :

 4 Figure 4: Classification results for different methods with 30 training data and 30 test data. (a)Training data and test data. (b) Classification results by L2-NN. (c) Classification results by CDW-NN. (d) Classification results by MHNN. (The blue makers represent the training data, and the red makers represent the test data, with circle for class A and square for class B and triangle for class C, respectively. The filled makers represent the data mistakenly classified.)

Table 1 :

 1 Statistics of the benchmark data sets used in the experiment. For Cancer data set, the samples with missing feature values are discarded.As displayed in Table1, some UCI data sets are small. In these cases, B-Fold Cross-Validation (B-CV)[START_REF] Raudys | Small sample effects in statistical pattern recognition: recommendations for practitioners[END_REF] is applied to estimate the error rates by different classification methods. Each data set is divided into B blocks using B -1 blocks as a training set and the remaining block as a test set. Therefore, each block is used exactly once as a test set. We use the simplest 2-CV here, because it has the advantage that both the training and test sets are large, and each sample is used for both training and testing on each fold. The 2-CV test is repeated 10 times, and the average

	Data set	# of instances	# of features	# of classes
	Balance	625	4	3
	Cancer a	683	9	2
	Diabetes	768	8	2
	Glass	214	9	6
	Letter	20,000	16	26
	Liver	345	6	2
	Satimage	6,435	36	6
	Segment	2,310	19	7
	Vehicle	846	18	4
	Wine	178	13	3

a

Table 2 :

 2 Classification accuracy (in %) of our proposed method in comparison with other NN-based methods.

	Data set	L2-NN	CDW-NN	MHNN
	Balance	75.15	80.12 a	85.56 b
	Cancer	95.24	95.48	98.06
	Diabetes	70.05	69.96	75.33
	Glass	69.36	71.15	73.72
	Letter	95.15	96.60	96.08
	Liver	64.36	60.88	68.12
	Satimage	89.09	88.45	90.29
	Segment	95.42	95.90	96.92
	Vehicle	69.42	69.55	73.60
	Wine	76.45	89.40	94.38

a The results typeset in boldface are significantly better over the baseline L2-NN method at the 5% level. b The results underlined correspond to the best accuracy.

Table 3 :

 3 Classification CPU time (/s) of our proposed method in comparison with other NN-based methods.

	Data set	L2-NN	CDW-NN	MHNN
	Balance	0.5616	0.9360	1.8308
	Cancer	0.5772	1.0140	1.3472
	Diabetes	0.9984	1.4976	2.1840
	Glass	0.0836	0.1248	0.5192
	Letter	311.20	724.45	8325.4
	Liver	0.1560	0.2496	0.3358
	Satimage	53.414	88.450	340.22
	Segment	6.5520	14.945	48.965
	Vehicle	0.8580	1.8720	3.8360
	Wine	0.0468	0.0780	0.1516

Table 4 :

 4 Classification accuracy (in %) of our proposed method in comparison with other well-known methods.

	Data set	ALLOC80 CART	C4.5	Discrim	NBayes	Quadisc	Cal5	MHNN
	Diabetes 69.9(8) a	74.5(4)	73.0(7)	77.5(1)	73.8(5)	73.8(5)	75.0(3)	75.3(2)
	Letter	93.6(2)	-	86.8(4)	69.8(6)	47.1(7)	88.7(3)	74.7(5)	96.1(1)
	Satimage 86.8(2)	86.2(3)	85.0(4)	82.9(7)	71.3(8)	84.5(6)	84.9(5)	90.3(1)
	Segment 97.0(1)	96.0(3)	96.0(3)	88.4(6)	73.5(8)	84.3(7)	93.8(5)	96.9(2)
	Vehicle	82.7(2)	76.5(4)	73.4(6)	78.4(3)	44.2(8)	85.0(1)	72.1(7)	73.6(5)

In the LOO test, one sample in the training set is selected randomly and is classified based on the remaining training set. This procedure is repeated until all the samples in the training set have been tested.

In this case, the class membership of training data x (i) has the following form ω (i) = {(ω 1 , p 1,i ), • • • , (ω M , p M,i )}, where p q,i is the probability that the training data x (i) belongs to class ω q .

Only those methods that have results in many data sets, and those data sets for which results with many methods are available have been chosen for the comparisons in Table4.

Acknowledgments

The authors would like to thank the anonymous reviewers for their careful reading and in-depth criticisms and suggestions. This work is partially supported by China Natural Science Foundation (No. 61135001, 61374159) and the Doctorate Foundation of Northwestern Polytechnical University (No. CX201319).


Sébastien Penz

Jean-François Girard

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Powerline harmonic noise in MRS data cancellation by

sinusoidal subtraction An efficient solution to cancel powerline interferences

Powerline harmonic noise in MRS data cancellation by sinusoidal subtraction S. Penz, J.F. Girard. BRGM, 3 av. Claude Guillemin, BP 36009, 45060 Orléans Cedex 2

The surface magnetic resonance method (SNMR) is a valuable technique for hydrogeological studies, since it provides information on the porosity, hydraulic conductivity and water content. However the bad signal-to-noise ratio often encountered limits its application range. In particular, in suburban areas, strong powerline harmonics severely degrade the SNMR signals.

The powerline fundamental frequency is subject to small variations in time that make high order harmonics filtering difficult using a classical notch filter without distorting the MRS signal. Harmonics cancellation using sinusoidal subtraction is an alternative, but requires a high accuracy of the instantaneous fundamental frequency value to be efficient. The power grid frequency being regulated we expect that the instantaneous frequency could be monitored with a good S/N ratio using a remote frequencemeter, synchronised with the SNMR device, and later used for processing. Based on this accurate instantaneous frequency measurement we developed a processing method based on the subtraction of a powerline harmonics model of constant amplitudes. We performed numerical experiments to quantify the efficiency of this method, and compare it with classical notch or multi-channel filtering. Studying real noise measurements, we encountered cases where harmonics amplitudes do not remains stable over time. We therefore proposed a processing method that include time-variant amplitudes in the powerline harmonics model. Amplitudes are modeled using a b-spline decomposition and estimated through an inversion procedure. A test on synthetic data is presented to assess the theoretical applicability of the method.

An efficient solution to cancel powerline interferences

S(t) = MRS(t) + H(t) + spikes(t) + N(t) H(t) = A m cos(2πmf f (0).t + φ m + Δφ m (t)) m ∑ Δφ m (t) = 2πm f f (u) f s 0 t ∫ du
The signal recorded in the reception channel can be described by the model:

The powerline interference component of this model takes the abusive form:

, where is the powerline instantaneous frequency.

After spikes removal, using the measured powerline frequency, phase and amplitudes of each harmonic is determined using the cross correlation with a reference sinusoid at the harmonic frequency. The complete harmonic model is later reconstructed as follows:

, with the phase delay due to the fundamental frequency variation.

f f

The harmonic model H(t) is further subtracted to the signal S(t), and the remaining noise can be cancelled by a multichannel filter and/or a stacking procedure.

A m (t) = a n B n κ ,k (t) n ∑

Inversion method to fit time-variant amplitudes

In order to find a better solution for the case of harmonic amplitudes significantly changing over a stack length, we define a new harmonic model:

, where .

Each harmonic amplitude is defined as a linear combination of n b-splines functions. The m×n parameters a can be estimated solving a linear inverse problem. This problem consists in minimizing the following cost function:

, where p are logarithmic parameters, C a smoothing operator and I a damping operator.

>

  Measurements of the fundamental powerline frequency is the key for a good sinusoidal subtraction • Signal parameters are better recovered even with a high noise level • Time variant harmonics amplitude inversion is promising • Performance of filtering combination strategies remains to be evaluated on a large site database > GPS synchronisation of SNMR devices would allow direct application of this metod Girard Jean-Francois BRGM Orléans DGR/REG jf.girard@brgm.fr Contact model sinusoidal subtraction

Fundamental powerline frequency synchroneously measured in three locations (at the regional scale: ~30km distance).

Exemple of four parameters non-linear fitting after synchroneous detection (SNR=0.59).

Aknowledgment: This work was partly funded through the french national research project CRITEX.


Thomas Vissers

Nick Nikiforakis

Nataliia Bielova
email: nataliia.bielova@inria.fr

Wouter Joosen

Crying Wolf ? On the Price Discrimination of Online Airline Tickets

Price discrimination refers to the practice of dynamically varying the prices of goods based on a customer's purchasing power and willingness to pay. In this paper, motivated by several anecdotal accounts, we report on a three-week experiment, conducted in search of price discrimination in airline tickets. Despite presenting the companies with multiple opportunities for discriminating us, and contrary to our expectations, we do not find any evidence for systematic price discrimination. At the same time, we witness the highly volatile prices of certain airlines which make it hard to establish cause and effect. Finally, we provide alternative explanations for the observed price differences.

Introduction

In today's web, users are accustomed to getting a variety of services without explicitly paying for them. Thus, the average user has access to mail services, maps, search, social networks, cloud storage, and online newspapers, without paying a subscription fee to any of them.

These services, in turn, usually make a profit either by directly providing ads to their users, or gathering user details that are used in house, or sold to other companies, in order to provide better targeted ads. These two are not strictly separated because the gathering of information about a user and the showing of ads can (and does) happen through a single action, such as the inclusion of a remote JavaScript library from an advertising syndicator.

An alternative monetization strategy to targeted advertising, is price discrimination. Price discrimination involves varying the price of any specific product or service, depending on the amount that a customer is willing to pay. The vast amounts of user-data gathered on the modern web are a natural fit for such a pricing strategy [START_REF] Odlyzko | Privacy, economics, and price discrimination on the internet[END_REF]. Knowing, for instance, that a user visits webpages which sell high-end goods can be used to infer the income level of that user. This knowledge can, in turn, be used to dynamically increase the price of a product on a, seemingly, unrelated website, simply because that user is likely to have the ability and willingness to pay more for that product. Prior research by Mikians et al. [START_REF] Mikians | Detecting price and search discrimination on the internet[END_REF] showed that price discrimination is used to vary the prices of digital products (such as ebooks) based on the geographical location of the user. The authors later showed that crowdsourcing can be used to unearth harder-to-find cases of price discrimination, such as the ones present in regional e-shops [START_REF] Mikians | Crowd-assisted Search for Price Discrimination in E-Commerce: First results[END_REF].

In this paper, motivated by several anecdotal reports [START_REF] Dawson | Save money on ryanair fares by deleting your cookies?[END_REF][START_REF] Mattioli | On orbitz, mac users steered to pricier hotels[END_REF][START_REF] Sampson | Ryanair exhibit a[END_REF], we investigate whether airlines practice price discrimination on the tickets sold through their websites. Airline tickets are an attractive target for price discrimination due to the highly volatile nature of their prices. An airline could, for instance, recognize the same user over time, e.g., through the use of cookies, and gradually increase the price of a specific ticket. The user is likely to attribute the price increase to flight congestion (many people buying tickets for that specific flight) and buy the ticket at an increased price, out of fear that the price will increase even more.

Through a three-week long experiment, involving 25 different airline companies, we find that, at this time, airlines seem not to be employing any systematic price discrimination. While we did observe some price fluctuations that could be interpreted as due to discrimination, in most cases, these fluctuations could be explained through other means, e.g., increased tax on tickets of a regional airline, when those were purchased outside of that specific region. At the same time, we show how difficult it is to establish cause and effect for airline prices and we make available the set of prices that we collected so that it can be used on future research on the topic of price discrimination [START_REF] Vissers | Online airline price discrimination dataset[END_REF].

Background

User Tracking

Some of the strategies that could be of use in price discrimination require the tracking of users between page loads of the same site, as well as across different websites.

Browser cookies have emerged as the de facto way of tracking users in the modern web. The cookie mechanism allows a web server to store a small amount of data on the computers of visiting users, which is then sent back to the web server upon subsequent requests. Cookies can be separated in first-party and third-party depending on the way on which they are set and read.

First-party cookies are cookies set by the website that the user is consciously visiting, e.g., a user visiting the website of Delta Airlines and receiving cookies for the delta.com domain. First-party cookies are used to, among others, maintain state over the stateless HTTP protocol, and recognize visitors between page loads.

Third-party cookies are cookies given by third-party servers which provide content to a first-party page. If, for instance, Delta airlines uses a Facebook "Like" button, Facebook has the ability to store and read cookies when the visitor visits the delta.com website. Third-party cookies are more intrusive than first-party cookies, since they can be used to track users in a cross-site way [START_REF] Krishnamurthy | Privacy diffusion on the web: A longitudinal perspective[END_REF][START_REF] Roesner | Detecting and defending against third-party tracking on the web[END_REF]. If for instance, the sites travel.com and football.com show ads from the same advertising syndicator, that syndicator has the ability to correlate users between these sites and build a browsing profile for each user that can be then monetized in series of ways, including targeted ads and the selling of a user's information to larger data aggregators and brokers.

Next to cookies and other techniques involving the storing of identifiers at the client-side [START_REF] Mayer | Third-party web tracking: Policy and technology[END_REF], web-based device fingerprinting is another technology that has recently emerged and can also be used to track users. In fingerprinting, several attributes of a user's browsing environment, e.g., a user's browser, platform, screen dimensions, and installed plugins, can be combined to form a fingerprint that is, for all practical purposes, unique [START_REF] Acar | FPDetective: Dusting the Web for fingerprinters[END_REF][START_REF] Eckersley | How Unique Is Your Browser?[END_REF][START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF]. The advantage of fingerprinting is that it is stateless and, because of that, hidden from a user, i.e., no cookies to inspect or delete.

Anecdotal Evidence of Price Discrimination

Over the past years, many articles, blog posts and Internet fora have reported the use of price discrimination in online travel tickets. Generally, these claims are based on anecdotal evidence. In this section, we briefly list several noteworthy cases and discussions.

In 2011, a massively "retweeted" tweet [START_REF] Sampson | Ryanair exhibit a[END_REF] implied that Ryanair was tracking users through cookies and raising their prices based on the user's previous visits. On a blog post that followed [START_REF] Dawson | Save money on ryanair fares by deleting your cookies?[END_REF], similar claims were made by people entering the discussion: TheTrainline.com, Expedia, Easyjet, Virgin, Lastminute and Eurostar were all accused of price discrimination based on previous visits or search queries. The Wall Street Journal reported a year later that Orbitz [3], an online travel agency (OTA), presents Apple-branded computers with more expensive flight and hotel search results first [START_REF] Mattioli | On orbitz, mac users steered to pricier hotels[END_REF], a practice that is referred to as search discrimination [START_REF] Mikians | Detecting price and search discrimination on the internet[END_REF].

In 2013, a column published in USA Today [START_REF] Mcgee | Do travel deals change based on your browsing history[END_REF] specifically discussed the current technical possibilities and legal implications of price discrimination in the travel sector. Furthermore, they claim to have observed a price difference with a cookie-cleared browser in tests they conducted in 2007.

More recently, in January 2014, a blogger explained how he got a less expensive fare from Kayak [START_REF]Kayak -flight[END_REF], a travel metasearch engine, by using a Canadian instead of an American IP address [START_REF] Casanova | How i hacked kayak and booked a cheaper flight[END_REF].

To properly assess these practices, we emulate real users performing search queries for specific flight routes. We do this repeatedly for all the different user profiles on all regarded airlines. For every conducted search query, we keep track of the prices that are presented to that particular user.

In the following paragraphs, we will explain the techniques used to automate the search queries and to construct different user profiles.

Automated search querying

During 21 days, we queried 25 airlines twice a day, with 66 user profiles, from two different geographical locations simultaneously resulting to a total of over 130,000 queries. We automated this large-scale analysis by building a scraper using CasperJS [START_REF]Casperjs -navigation scripting and testing utility for phantomjs[END_REF], which is a navigation scripting and testing utility for Phan-tomJS [START_REF]Phantomjs -a headless webkit scriptable with a javascript api[END_REF], a headless browser. We ensured our scraper followed the exact same steps a normal user would follow when manually searching for airline tickets. The scraper ran from January 15, 2014 until February 5, 2014, querying for flights departing on March 22, 2014 and returning on March 30, 2014. The specific flight routes that were queried were different for every airline, but fixed throughout the entire analysis. The order in which the scraper iterated the 66 user profiles for every airline was randomized at each run.

Constructing user profiles

We constructed a total of 66 unique user profiles, which are the result of combining several different subprofiles, described in the following sections. The majority of these leveraged the ability of PhantomJS to easily configure the browser's internals and cookie settings. Additionally, two geographical subprofiles were created, which were both combined with the 66 user profiles.

Browser and OS profiles

The browser and operating system (OS) profiles are set up to observe potential discrimination based on the user's device. From a web server's perspective, the User-Agent string is the most straightforward feature for identifying the client's Internet browser and OS. When making a web request, the client sends this string as an HTTP header to the web server. Moreover, the User-Agent string also resides in the browser's navigator Javascript-object, together with other indicative strings, such as vendor, platform, appCodeName, appName and appVersion. A web server can use this information to determine which browser and OS a particular client is using. For example, the User-Agent string of Safari Mobile running on an iPad with iOS 4.3.5 is easily recognized: Mozilla/5.0 (iPad; U; CPU OS 4_3_5 like Mac OS X; en-gb) AppleWebKit/533.17.9 (KHTML, like Gecko) Version/5.0.2 Mobile/8L1 Safari/6533.18.5

By spoofing the information in the User-Agent string and the navigator object, we were able to mimic different OSs and browser profiles. Our scraper was programmed to emulate several different profiles: Internet Explorer 9 on Windows 7, Chrome 29 on Windows 7, Firefox 22 on OS X 10.7, Safari 6 on OS X 10.7 and Safari Mobile 5 on iOS (iPad).

Furthermore, we configured additional Chrome, Safari and Internet Explorer profiles with the Do Not Track (DNT) header set to 1. The DNT header is an HTTP header which can be utilized by users to request from a web application to disable their tracking [START_REF]W3C: Tracking preference expression[END_REF].

Consumer profiles Inspired by the study of Mikians et al. [START_REF] Mikians | Detecting price and search discrimination on the internet[END_REF], we designed 3 consumer profiles: affluent, budget and flight comparer. These profiles were composed by gathering cookies of websites that can be associated with them. For example, the cookies for the affluent profile were gathered by visiting sites associated with luxury goods and financial news. For the budget profile, we collected cookies from websites offering discounts and product reviews. And for the travel comparer profile, online travel agencies and travel metasearch engines, such as kayak.com, were included.

For each profile, we kept a separate cookie jar : all cookies gathered by a particular consumer profile were saved in an isolated file. When a consumer profile needs to be instantiated, its cookie jar can simply be loaded in PhantomJS. This way, potential third-party trackers, could access the consumer profile cookies while our crawlers visited the website of each airline.

Cookie setting profiles As discussed in Section 2.1, websites can make use of first-party and third-party cookies to track users between loads of the same page and across different websites. In our experiment, we accounted for four different cookie settings, when gathering ticket prices for each airline:

-Only consumer profile cookies (gathered in advance) -Consumer profile cookies along with first-party cookies -Only first-party cookies (also known as no third-party cookies) -No cookies

In our experiments, the first-party cookies are the cookies set by the airlines themselves which can be used to track a user's previous visits and searches and potentially influence the prices shown to users over time.

Geographical profile Websites often resort to the user's IP address as an indicator of locality [START_REF] Casanova | How i hacked kayak and booked a cheaper flight[END_REF][START_REF] Mikians | Detecting price and search discrimination on the internet[END_REF]. In order to set up different geographical profiles, the scraper ran simultaneously from two different locations, one in New York, United States and one in Leuven, Belgium.

Hypothesis

In order to evaluate the presence of systematic price discrimination, we test for the following hypothesis: if airlines present unequal prices to different users according to their consumer profile, location, or browsing history, we should be able to observe this when comparing the prices presented to a set of emulated users that differ in those characteristics, over several points in time. For instance, if a company is presenting higher prices to users of Apple products, a time-series graph of ticket prices should place our emulated Apple user "above" other users.

Limitations and assumptions

The search queries were not executed in parallel, but consecutively per profile on each location. The rational for this design choice is the following: performing a large number of simultaneous search queries may disrupt the airline's web server. Furthermore, if they engage in some form of rate limiting, our requests could be rejected, prohibiting us from reliably measuring prices. Similarly, we performed all search queries only twice a day for each airline, rather than continuously for our three-week measurement.

All profiles originating from a single geographical location had the same IP address. However, because of the widespread use of NAT technology, it is commonly assumed inadequate for a web server to distinguish between users based on their IP address. Since covering every possible geographical variance is virtually impossible, we only used two geographical profiles during our measurements. In preliminary experiments, an additional location (France) was also evaluated, but no additional differences were observed.

Finally, note that, in this paper, we only considered websites provided by each airline company, rather than travel aggregators and meta search engines. As such, our results should not be generalized to characterize the latter.

Results

Most of conducted the search queries returned multiple flight options, differing in terms of flight routes and departure time. Therefore, after extracting the prices from all search results, the minimum, maximum and average price per query were calculated. Next, this data was plotted as a time-series for each profile. Contrary to our expectations, we were not able to find any clear evidence of price discrimination: the majority of the plots reveal no consistent price difference between the user profiles.

For example, Fig. 1 shows the fluctuations of Ryanair's minimum prices recorded by the scraper located in the United States. We grouped together all profiles that had the same price evolution throughout the entire experiment, resulting in two distinct subsets. Of the 42 measurements, there is only one instance (#33) where a different price is given to a subset of the profiles. When examining the exact timestamp of each profile's measurement, we find that all profiles with a higher price at #33 were recorded consecutively and prior to all measurements with a lower price. This reveals that, most likely, the observed price difference is due to the price actively dropping while conducting the measurements for #33, rather than due to price discrimination. Some airlines showed rapid variations in the availability of tickets. In Fig. 2, the mean price of a KLM route is plotted for each profile. For every measurement, the vast majority of profiles has the same mean price, which results in a clear and steady trend over time. However, numerous steep peaks and valleys occur, affecting different profiles every time. When looking into these outliers, it appears that they are caused by a constantly changing availability of flights. The fluctuations are so dense that no two profiles shared the same price evolution throughout the experiment. To evaluate price discrimination based on location, we examined the calculated statistics of the geographical profiles, e.g., we compared the absolute minima of all American profiles to the absolute minima of Belgian profiles. Again, no clear evidence of price discrimination was found: Nearly all airlines show similar prices for both locations. However, as seen in Fig. 3, there was one exception with United Airlines: for the first 15 days, the Belgian price was consistently higher than the American price. At times, the Belgian price was listed 67.92 USD above the American. Remarkably, though, near the end of the experiment, the Belgian minimum price dropped below the American price several times.

In a preliminary experiment, we looked into price discrimination in multiregional and multilingual websites. We compared the native region or language (with respect to the airline company's origin) with a non-native alternative. A particularly interesting find was the Argentinian website of American Airlines. As shown in Fig. 4, the price was consistently about 19% higher than the price from the American website. After looking into this phenomenon, we discovered that, as of March 18, 2013, the Argentinian government has imposed a tax of 20% on credit card and holiday package purchases [START_REF] Popper | Argentina hikes levy on credit card purchases abroad[END_REF]. These taxes are countermeasures for Argentina's high inflation rate and perfectly explain the systematic price difference.

Alternative explanations for the anecdotal evidence

In this section we discuss several possible phenomena that may appear to a user as evidence of price discrimination, but actually have other causes. These alternative explanations are based on the results of our analysis and additional information concerning regulations and business specifics.

As shown earlier in Fig. 2, flight routes and their prices can be extremely volatile. When we look at consecutive measurements for KLM, it is not uncommon for a flight to suddenly become unavailable, only to reappear in the next measurement. Taking into account that our measurements are roughly 1 minute apart, it is likely that users will encounter different prices when performing two consecutive searches.

When performing a search from several geographical locations, a user may encounter different prices due to regulations and agreements specific to that region. For example, differences may occur simply due to currency conversions [START_REF] Matt | How to be a travel hacker[END_REF]. Also, a country may impose additional taxes, e.g., as seen with Argentina. In contrast, in Peru, some airlines have cheaper fares solely for Peruvian residents [START_REF] Jonjak | Lan surprises tourists with $178.50 fee[END_REF]. Specific agreements and partnerships may differ between regions as well, e.g., Southwest Airlines prohibit third-parties to use their price information. This has, in the past, lead to an injunction against Orbitz [START_REF] Disabatino | Southwest pulls flight data to hinder orbitz[END_REF] and withdrawal of its flight data from the Airline Tariff Publishing Co. (ATPCO). This is a possible explanation for the less expensive flights on Kayak while searching from Canada [START_REF] Casanova | How i hacked kayak and booked a cheaper flight[END_REF], mentioned in Section 2.2. As it turns out, the Canadian results contained the lower priced Southwest Airlines flights, while the American results did not.

Another phenomenon that can be perceived as price discrimination, is the caching of prices: as explained in [START_REF] Elliott | The low airfare that vanishes in a click[END_REF], travel companies do not display real time price information. Instead, for the sake of cost and time efficiency, prices are cached. This can possibly result in discrepancies between prices that were initially displayed and the price at the final step of the booking process. Furthermore, subsequent search queries may display the updated price which can be higher or lower than the previously reported price.

Conclusion

In this paper, motivated by several anecdotal reports, we investigated the presence of price discrimination in airline ticket prices. Contrary to our expectations, our three-week long experiment, spanning 25 different airlines, tens of user profiles, and two geographical locations, did not reveal the use of any systematic price discrimination. Based on our findings, we argue that at least some of the anecdotally reported price differences can be explained through alternate means, such as government policies and variable taxation. We hope that our study can serve as a reference for the current state of practice, and inspire longitudinal studies that may uncover the future adoption of price discrimination by airline companies. We make the data from our research publicly available so that it can be used in future research [START_REF] Vissers | Online airline price discrimination dataset[END_REF].

Fig. 1 .

 1 Fig.1. Minimum price offered by Ryanair for all user profiles (US) over 21 days, for the CRL -LPA route. A small amount of vertical jitter was applied to the data points, in order to prevent the plotted lines from overlapping.

Fig. 2 .

 2 Fig. 2. Mean prices offered by KLM for all user profiles (BE) over 21 days, for the JFK -AMS route. Note, that there are no measurements between #16-19, due to a network problem. The thick black line represents the trend of all other profiles.

Fig. 3 .

 3 Fig. 3. Minimum price offered by United Airlines in Belgium and the United States over 21 days, for the SFO -BRU route. For a meaningful comparison, the listed Belgian prices (in EUR) were converted to USD using the applicable exchange rate for that time.

Fig. 4 .

 4 Fig. 4. Price for a particular SFO -BRU flight offered by American Airlines for the non-native (Argentina, in red) and native (US, in blue) profile over 21 days.

Large-scale analysisAs noted in the previous section, airline companies have been accused of serving different prices according to a client's geographical location, the device they use, their consumer profile or their previous search queries. We evaluate this claim by analyzing 25 airlines continuously for 3 weeks, with dozens of unique user profiles. These profiles are constructed in light of the user-tracking methods explained in Section 2.1, and the potential discriminating factors.

Acknowledgments: We want to thank the anonymous reviewers for the valuable comments. This research was performed with the financial support of the Prevention against Crime Programme of the European Union (B-CCENTRE), the Research Fund KU Leuven, the IWT project SPION, the EU FP7 projects NESSoS, WebSand and the French ANR-10-LABX-07-01 Laboratoire dexcellence CominLabs.

A Airlines

The list of airlines included in our analysis is as follows:

-American Airlines (aa.com) -Aegean Airlines (aegeanair.com) -Alaska Airlines (alaskaair.com) -Alitalia (alitalia.com) -British Airways (britishairways.com) -Brussels Airlines (brusselsairlines.com) -Cathay Pacific (cathaypacific.com) -Delta (delta.com) -EasyJet (easyjet.com) -Emirates (emirates.com) -HOP! (hop.fr) -KLM (klm.com) -LAN (lan.com) -Lufthansa (lufthansa.com) -Qantas (qantas.com.au) -Qatar Airways (qatarairways.com) -Ryanair (ryanair.com) -Saudi Airlines (saudiairlines.com) -Southwest Airlines (southwest.com) -Turkish Airlines (turkishairlines.com) -United Airlines (united.com) -US Airways (usairways.com) -Virgin Atlantic (virgin-atlantic.com) -Widerøe (wideroe.no) -Wizz Air (wizzair.com)