Francisco De A T De Carvalho

Patrice Bertrand

Filipe M De Melo

Batch self-organizing maps based on city-block distances for interval variables

Keywords: Self-organizing maps, Interval-valued data, City-block distances, Adaptive distances, Symbolic data analysis

The Kohonen Self Organizing Map (SOM) is an unsupervised neural network method with a competitive learning strategy which has both clustering and visualization properties. Interval-valued data arise in practical situations such as recording monthly interval temperatures at meteorological stations, daily interval stock prices, etc. Batch SOM algorithms based on adaptive and non-adaptive city-block distances, suitable for objects described by interval-valued variables, that, for a fixed epoch, optimizes a cost function, are presented. The performance, robustness and usefulness of these SOM algorithms are illustrated with real interval-valued data sets.

Introduction

Clustering is a popular task in knowledge discovery, and it is applied in various fields including data mining, pattern recognition, computer vision, etc. Clustering methods aim at organizing a set of items into clusters such that items within a given cluster have a high degree of similarity, while items belonging to different clusters have a high degree of dissimilarity. The most popular clustering techniques are hierarchical and partitional methods [START_REF] Jain | Data clustering: a review[END_REF][START_REF] Xu | Survey of clustering algorithms[END_REF]. K-means algorithm and fuzzy c-means are the most famous partitional approaches.

The Kohonen Self Organizing Map (SOM) [START_REF] Kohonen | Self-Organisation Maps[END_REF] is an unsupervised neural network method with a competitive learning strategy which has both clustering and visualization properties. Different from K-means, SOM uses the neighborhood interaction set to approximate lateral neural interaction and discover the topological structure hidden in the data, and in addition to the best matching referent vector (winner), its neighbors on the map are updated, resulting in regions where neurons in the same neighborhood are very similar. It can be considered as an algorithm that maps a high dimensional data space to lattice space which usually has a lower 1 dimension (typically, dimension two) and is called a map. This projection enables a partition of the inputs into "similar" clusters while preserving their topology. The map training can be incremental or batch.

This paper gives batch SOM algorithms to manage individuals described by interval-valued variables. Interval-valued variables are needed, for example, when an object represents a group of individuals and the variables used to describe it need to assume a value which express the variability inherent to the description of a group.

Interval-valued data arise in practical situations such as recording monthly interval temperatures at meteorological stations, daily interval stock prices, etc. Another source of interval-valued data is the aggregation of huge databases into a reduced number of groups, the properties of which are described by interval-valued variables. Therefore, tools for interval-valued data analysis [START_REF] Bock | Analysis of Symbolic Data, Exploratory methods for extracting statistical information from complex data[END_REF][START_REF] Diday | Symbolic Data Analysis and the Sodas Software[END_REF] are very much required.

In [START_REF] Bock | Clustering algorithms and Kohonen maps for symbolic data[END_REF][START_REF] D'urso | Midpoint radius self-organizing maps for intervalvalued data with telecommunications application[END_REF] it is presented incremental SOM algorithms that are able to manage interval-valued data. More recently, batch SOM based on non-adaptive [START_REF] De Carvalho | Une version batch de l'algorithme SOM pour des données de type intervalle[END_REF][START_REF] Hajjar | Self-organizing map based on L2 distance for intervalvalued data[END_REF] and adaptive Euclidean distances [START_REF] De Carvalho | Une version batch de l'algorithme SOM pour des données de type intervalle[END_REF] as well as non-adaptive city-block distances [START_REF] Hajjar | Self-organizing map based on city-block distance for interval-valued data[END_REF], have been presented.

This paper aims at proposing batch SOM algorithms based on adaptive and non-adaptive city-block distances, suitable for objects described by interval-valued variables, that, for a fixed epoch, optimizes a cost function. The performance, robustness and usefulness of these SOM algorithms are illustrated with real interval-valued data sets, in comparison with batch SOM algorithms based on adaptive and non-adaptive Euclidean distances.

Batch self-organizing maps based on city-block distances

This section presents batch SOM algorithms based on adaptive (ABSOM-L1) and non-adaptive (BSOM-L1) city-block distances for interval-valued data. They are based on the batch SOM algorithm based on the Euclidean distances for real-valued data [START_REF] Badran | Self-organizing maps and unsupervised classification[END_REF].

Let E = {e 1 , . . . , e n } be a set of n objects indexed by i and described by p interval-valued variables indexed by j. An interval-valued variable X [START_REF] Bock | Analysis of Symbolic Data, Exploratory methods for extracting statistical information from complex data[END_REF] is a correspondence defined from E in ℑ such that for each e i ∈ Ω, X(e i ) = [a, b] ∈ ℑ, where ℑ is the set of closed intervals defined from ℜ. Each object e i is represented as a vector of intervals x i = (x i1 , . . . , x ip ), where

x ij = [a ij , b ij ] ∈ ℑ = {[a, b] : a, b ∈ ℜ, a ≤ b}.
A basic assumption of the presented batch SOM algorithms is that a prototype w r of cluster P r (r = 1. . . . , m) is also represented as a vector of intervals w r = (w r1 , . . . , w rp ), where

w rj = [α rj , β rj ] ∈ ℑ (j = 1, . . . , p).
The IBSOM-L1 algorithm is an iterative two-step algorithm (representation and affectation steps) in which the whole data set E is presented to the map before any adjustments are made. The IBSOM-L1 algorithm minimizes the following cost function:

J = n i=1 m r=1 K T (δ(f T (x i ), r)) d(x i , w r ) ( 1
)
where f is the allocation function and f T (x i ) stands for the neuron of the map that is associated to the object x i , and δ(f T (x i ), r)) is the distance on the map between a neuron r and the neuron that is allocated to the object x i . Moreover, K T , that is parameterized by T (where T stands for temperature), is the neighborhood kernel function that defines influence region around each neuron r.

The generalized dissimilarity function between an input data x i and a prototype w f T (x i ) is given by:

d T (x i , w f T (x i ) ) = m r=1 K T (δ(f T (x i ), r)) d(x i , w r ) (2)
where

d(x i , w r ) = p j=1 [|a ij -α rj | + |b ij -β rj |] (3)
is a suitable city-block distance between vectors of intervals. This generalized distance is a weighted sum of the city-block distances between x i and all the reference vectors of the neighborhood of the neuron f T (x i ). It takes into account all the neurons of the map. The IABSOM-L1 algorithm is an iterative three-step algorithm (representation, weighting and affectation steps) in which the whole data set E is also presented to the map before any adjustments are made. The cost function of the IABSOM-L1 algorithm is given by:

J = n i=1 m r=1 K T (δ(f T (x i ), r)) d λ r (x i , w r ) (4)
The generalized dissimilarity function between an input data x i and a prototype w f T (x i ) is given by:

d T Λ (x i , w f T (x i ) ) = m r=1 K T (δ(f T (x i ), r)) d λ r (x i , w r ) (5)
where

d λ r (x i , w r ) = p j=1 λ rj [|a ij -α rj | + |b ij -β rj |] (6)
is an adaptive city-block distance parameterized by the vector of weights on the variables λ r = (λ r1 , . . . , λ rp ) and Λ= (λ 1 , . . . , λ m ). Note that the weight vectors λ r (r = 1, . . . , m) change at each iteration, i.e., they are not determined absolutely, and are different from one neuron to another.

When T is kept fixed, for IBSOM-L1 algorithm, the minimization of J is performed iteratively in two steps (representation and allocation), whereas for IABSOM-L1, the minimization of J is performed iteratively in three steps (representation, weighting and affectation).

During the representation step of IBSOM-L1, the allocation function is kept fixed. The cost function J is minimized with respect to the prototypes. During the representation step of IABSOM-L1, the allocation function and the vectors of weights are kept fixed. The cost function J is also minimized with respect to the prototypes. For both algorithms, the components w rj (j = 1, . . . , p) of the prototype w r (r = 1, . . . , m) are such that they minimize

n i=1 K T (δ(f T (x i ), r))[|a ij -α rj | + |b ij -β rj |]
This problem brings to the minimization of n i=1 |y i -az i |, where

y i = K T (δ(f T (x i ), r)) a ij (or, equivalently, y i = K T (δ(f T (x i ), r)) b ij ), z i = K T (δ(f T (x i ), r)
) and a = α rj (or, equivalently, a = β rj ). The solution of this problem is known and to solve it the following algorithm can be used [START_REF] Jajuga | L1-norm based fuzzy clustering[END_REF][START_REF] Karst | Linear curve fitting using least deviations[END_REF]:

1. Determining u i = y i /z i (i = 1, . . . , n); 2.
Rearrange the z i 's according to ascending order of u i 's and get z1 , . . . , zn ;

3. Minimize r l=1 |z l | -n l=r+1 |z l | regarding r;
4. If the minimum is negative, take a = u r . If the minimum is positive, take a = u r+1 . Finally, if the minimum is equal to zero, take a = (u r + u r+1 )/2.

Theorem 2.1. The boundaries of the intervals

w rj = [α rj , β rj ] (r = 1, . . . , K; j = 1, . . . , p) are such that α rj ≤ β rj .
Proof. The proof is given in appendix.

During the weighting step of IABSOM-L1, the reference vectors (prototypes) and the allocation function are kept fixed. The cost function J is minimized with respect to the vectors of weights. The computation of these vectors of weights in this algorithm is also inspired from the approach used to compute a weight for each variable in each cluster in the dynamic clustering algorithm based on adaptive distances [START_REF] Diday | Classification Automatique avec Distances Adaptatives[END_REF].

The vectors of weights λ r = (λ r1 , . . . , λ rp ) (r = 1, . . . , m), under λ rj > 0 and p j=1 λ rj = 1, have their weights λ rj (j = 1, . . . , p) calculated according to the following expression:

λ rj = { p h=1 n i=1 K T (δ(f T (x i ), h))[|a ij -α rh | + |b ij -β rh |]} 1 p n i=1 K T (δ(f T (x i ), r))[|a ij -α rj | + |b ij -β rj |] (7)
During the affectation step of IBSOM-L1, the reference vectors (prototypes) are kept fixed. The cost function J is minimized with respect to the allocation function and each individual x i is assigned to its nearest neuron:

c = f T (x i ) = arg min 1≤r≤m d T (x i , w r ) (8)
During the affectation step of IABSOM-L1, the reference vectors (prototypes) and the vectors of weights are kept fixed. The cost function J is minimized with respect to the allocation function and each individual x i is assigned to its nearest neuron:

c = f T (x i ) = arg min 1≤r≤m d T Λ (x i , w r ) (9)
The batch SOM algorithm based on adative and non-adaptive city-block distances for intervalvalued can be summarized as follows.

. , p)

For IBSOM-L1 algorithm, assign each object x i to the closest neuron (cluster) according to equation ( 8); For IABSOM-L1 algorithm, assign each object x i to the closest neuron (cluster) according to equation (9);

Step 2 Representation Set T = T max ( T min Tmax )

t N iter -1 ; Compute w rj (j = 1, . . . , p), components of the prototypes w r = (w r1 , . . . , w rp ) (r = 1, . . . , m), according to the algorithm given by [START_REF] Jajuga | L1-norm based fuzzy clustering[END_REF][START_REF] Karst | Linear curve fitting using least deviations[END_REF].

Step 3 Weighting Skip this step for IBSOM-L1 algorithm; For IABSOM-L1 algorithm, compute the components λ rj of the vectors of weights λ r (r = 1, . . . , m; j = 1, . . . , p) according to equation ( 7);

Step 4 Affectation For IBSOM-L1 algorithm, assign each object x i to the closest neuron (cluster) according to equation ( 8); For IABSOM-L1, algorithm, assign each object x i to the closest neuron (cluster) according to equation (9);

Step 5 Stopping criterion If T = T min then STOP; otherwise set t = t + 1 and go to Step 2 (Representation).

Experimental results

To evaluate the performance of these SOM algorithms, two applications with a car models and a freshwater fish species interval-valued data set are considered. Our aim is to achieve a comparison of the batch SOM algorithms based on adaptive and non-adaptive city-block distances with the batch SOM algorithms based on adaptive (hereafter named IABSOM-L2) and non-adaptive (hereafter named IBSOM-L2) Euclidean distances [START_REF] De Carvalho | Une version batch de l'algorithme SOM pour des données de type intervalle[END_REF][START_REF] Hajjar | Self-organizing map based on L2 distance for intervalvalued data[END_REF] between vectors of intervals. Then, the usefulness of these batch SOM algorithms will be illustrated with an application concerning a city temperatures interval-valued data set.

As pointed out by [START_REF] Badran | Self-organizing maps and unsupervised classification[END_REF] the performance of these algorithms strongly depend on the parameters of the minimization algorithms. The most important important are T max , T min , N iter and the cooled schedule.

K T (δ(c, r) = exp - (δ(c, r)) 2 2T 2
Intitially, each interval-valued variable on these data sets were normalized by means of a suitable dispersion measure [START_REF] Chavent | On central tendency and dispersion measures for intervals and hypercubes[END_REF]. Let D j = {x 1j , . . . , x nj } be the set of observed intervals x ij = [a ij , b ij ] on variable j (j = 1, . . . , p). The dispersion of the jth variable is defined as

s 2 j = n i=1 d j (x ij , g j ), where g j = [α j , β j ] is the "central" interval computed from D j and d j (x ij , g j ) = |a ij -α j | + |b ij -β j | (if the comparison between intervals uses the city-block distance), or d j (x ij , g j ) = (a ij -α j ) 2 + (b ij -β j ) 2 (

if the comparison between intervals uses the Euclidean distance).

The central interval g j = (α j , β j ) T has its bounds computed from n i=1 d j (x ij , g j ) → M in. They are α j = 1 n a ij and

β j = 1 n b ij . Each observed interval x ij = [a ij , b ij ] (i = 1, . . . , n) is normalized as xij = [ã ij , bij ], where ãij = a ij √ (s 2 j )
and bij = (if the comparison between intervals uses the city-block distance). One can easily show that s2 j = 1, where αj = 1 n ãij and βj = 1 n bij . Now, all the normalized interval-valued variables have the same dispersion s2 j = 1. In order to compare the results given by the batch SOM algorithms applied on the intervalvalued data sets considered in this paper, an external index the corrected Rand index (CR) [START_REF] Hubert | Comparing partitions[END_REF] and the overall error rate of classification (OERC) [START_REF] Breiman | Classification and Regression Trees[END_REF].

Performance of the batch SOM algorithms

The car model data set concerns 33 car models described by 8 interval-valued variables. These car models are grouped in four a priori classes of unequal sizes: Utilitarian (size 10), Berlina (size 8), Sporting (size 7) and Luxury (size 8). The interval-valued variables are: Price, Engine Capacity, Top Speed, Acceleration, Step, Length, Width and Height.

The freshwater fish species concerns 12 species of freshwater fish, each specie being described by 13 symbolic interval variables. These species are grouped into four a priori classes of unequal sizes acoording to diet: two classes (Carnivorous and Detritivorous) of size 4 and two clusters of size 2 (Omnivorous and Herbivorous). The symbolic interval variables are: Length, Weight, Muscle, Intestine, Stomach, Gills, Liver, Kidneys, Liver/Muscle, Kidneys/Muscle, Gills/Muscle, Intestine/Muscle and Stomach/Muscle. Each batch SOM algorithm was run 50 times on these datasets and the best result, according to the adequacy criterion, was selected. The cluster partitions obtained with these clustering methods were compared with the 4-class partition known a priori. Table 2 For the car models data set, the batch SOM algorithms with adaptive distances outperformed the batch SOM with non-adaptive distances. Moreover, the batch SOM algorithms with Euclidean distances outperformed the batch SOM algorithms with city-block distances. Finally, the batch SOM algorithms with adaptive Euclidean distances had the best performance whereas the worst performance was presented by the batch SOM algorithm based on non-adaptive city-block distances.

For the freshwater fish species data set, the batch SOM algorithms with city-block distances outperformed the batch SOM with Euclidean distances. Moreover, the batch SOM algorithms with non-adaptive city-block distances had the best performance and the batch SOM algorithms with non-adaptive Euclidean distances had the worst performance.

Robustness of the batch SOM algorithms

Theoretical studies indicate that city-block based models are more robust than those based on Euclidean distances. In order to evaluate the robustness of these batch SOM algorithms, we introduces 4 outliers on the car models and 1 outlier on the freshwater fish species data sets in the following way: the boundaries of the interval-valued variables describing, repectively, 1 individual of the the freshwater fish species and 4 individuals of the car models (one individual by each a priori class) were multiplied by 10 (configuration 1), by 100 (configuration 2) and by 1000 (configuration 3).

The batch SOM algorithms have been applied on these modified data sets. The cluster partitions obtained with these clustering methods were compared with the 3-class partition known a priori. Again, the comparison indexes used were the CR and ERC. These indexes were also calculated for the best result. Table 3 shows the results.

It can be observed that all the batch SOM algorithms were affected by the introduction of outiliers. However, those based on Euclidean distance were more affected than those based on city-block distances.

Application: city temperatures interval-valued data set

City temperature interval-valued data set [START_REF] Guru | Multivalued type proximity measure and concept of mutual similarity value useful for clustering symbolic patterns[END_REF] gives the minimum and the maximum monthly temperatures of cities in degrees centigrade. This data set consists of a set of 37 cities described by 12 interval-valued variables. The ABSOM-L1 batch SOM algorithm was run 50 times on the city temperature intervalvalued data set and the best result, according to the adequacy criterion, was selected. Figure 1 gives the self-organizing map of this interval-valued data set.

Table 5 gives the description of the cluster prototypes according to the minimum and the maximum monthly temperatures.

In Figure 1, the cities in bold are the most similar to the prototype of the cluster that they belong. It can be observed that the grid is coherent with the latitude location and temperature ranges of the cities. Latitude location grows from left to right and from bottom to top on the grid. Temperature ranges grows from right to left and from top to bottom on the grid.

Conclusion

The main contributions of this paper are the introduction of batch SOM algorithms based on adaptive and non-adaptive city-block distances, suitable for objects described by interval-valued variables, that, for a fixed epoch, optimizes a cost function. These SOM algorithms combine The performance of these batch SOM algorithms based on adaptive and non-adaptive cityblock distances were evaluated in comparison with batch SOM algorithms based on adaptive and non-adaptive Euclidean distances on car models and freshwater fish species interval-valued data sets. The accuracy of the results furnished by these algorithms was assessed by the corrected Rand index (CR) and the overall error rate of classification (OECR).

Overall, the batch SOM algorithms with adaptive (city-block and Euclidean) distances outperformed the batch SOM algorithms with non-adaptive distances on the original car models and freshwater fish species data sets. Moreover, all the batch SOM algorithms were affected by the introduction of outiliers. However, those based on Euclidean distance were more affected than those based on city-block distances.

Finally, the application of the batch SOM algorithm based on city-block distances on the city temperatures interval-valued data sets illustrated the usefulness of the presented SOM algorithms.

In the rest of this section, we aim to compare the sets opt (u) and opt (v) when u and v satisfy u i ≤ v i for all i ∈ {1, . . . , n}. We begin with the next lemma.

Lemma A.3 Consider a sequence u of n reals together with z 1 , z 2 , . . . , z n ∈ ]0, 1[. Given any real h > 0 and any integer k ∈ {1, . . . , n},

denote v = u + h e k . If (a, b) ∈ [opt (u) × opt (v)] \ [opt (v) × opt (u)], then a ≤ b. Proof. Let (a, b) ∈ [opt (u) × opt (v)] \ [opt (v) × opt (u)],
where we have denoted v = u + h e k . Then it results:

φ(b, v) -φ(a, v) ≤ 0 and φ(b, u) -φ(a, u) ≥ 0, one at least of these two inequalities being strict.

Since u k < v k = u k + h, all the possible cases, w.r.t. to a, are as follows:

a ≤ u k , u k < a ≤ v k and v k < a. Suppose that b < a. Case 1: a ≤ u k . Therefore b < a ≤ u k < v k . For each x ∈ R, we have: φ(x, v) = φ(x, u) -z k (u k -x) + z k (v k -x) φ(x, v) = z k (v k -u k ) + φ(x, u) Thus: φ(a, v) = z k (v k -u k ) + φ(a, u), φ(b, v) = z k (v k -u k ) + φ(b, u).
This leads to:

φ(b, v) -φ(a, v) = φ(b, u) -φ(a, u)

Observe that [START_REF] Hajjar | Self-organizing map based on L2 distance for intervalvalued data[END_REF] contradicts the fact that, by [START_REF] Guru | Multivalued type proximity measure and concept of mutual similarity value useful for clustering symbolic patterns[END_REF], either φ(b, v) -φ(a, v) ≤ 0 or φ(b, u)φ(a, u) ≥ 0 is a strict inequality.

For each l ∈ {0, 1, . . . , L}, define the sequence w (l) as follows:

w (l) =      u, if l = 0, u + l j=1
h σ(j) e σ(j) , otherwise.

Notice that w (L) = v according to [START_REF] Hajjar | Self-organizing map based on city-block distance for interval-valued data[END_REF]. Moreover, for each l ∈ {0, 1, . . . , L -1}, we have: w (l+1) = w (l) + h σ(l+1) e σ(l+1) .

Since for each k ∈ K, we have h k > 0, it results from Proposition A.4 that:

∀l ∈ {0, 1, . . . , L -1}, opt ⋆ (w (l) ) ≤ opt ⋆ (w (l+1) ).

As a consequence, we obtain:

opt ⋆ (w (0) ) ≤ opt ⋆ (w (1) ) ≤ . . . ≤ opt ⋆ (w (L) ), and thus opt ⋆ (u) = opt ⋆ (w (0) ) ≤ opt ⋆ (w (L) ) = opt ⋆ (v), as required.

Algorithm 2. 1 .

 1 Batch self-organizing algorithm for interval-valued data based on city-block distances.Step 1 InitializationFix the number m of neurons (clusters); Fix δ; Fix the kernel fuction K T ; Fix the number of iterations N iter ; Fix T min , T max ; Set T ← T max ; Set t ← 0; Randomly select m distinct prototypes w (0) c ∈ E (c = 1, . . . , m); Set the map L(m, W 0 ), where W 0 = (w (0) 1 , . . . , w (0) m ); For IABSOM-L1 algorithm, set λ rj = 1 (r = 1, . . . , m; j = 1, . .

Case 2 :+ b 1 2 ≤ a 2 + b 2 2 =

 222 u k < a ≤ v k . Subcase 2-1: b ≤ u k . Then b ≤ u k < a ≤ v k .The following equalities are straightforward. The first of them is proved as in Case 1:φ(b, v) = z k (v k -u k ) + φ(b, u), φ(a, v) = z k (v k -a) -z k (a -u k ) + φ(a, u), φ(a, v) = z k (v k + u k -2a) + φ(a, u). Then φ(b, v) -φ(a, v) = 2z k (a -u k ) + φ(b, u) -φ(a, u) > φ(b, u) -φ(a, u) ≥ 0. Thus φ(b, v)φ(a, v) > 0, which contradicts the definition of b. Proof. Let v = u + h e k .Since opt (u) and opt (v) are intervals that may be reduced to singletons, we denote opt(u) = [a 1 , a 2 ] and opt (v) = [b 1 , b 2 ] with a 1 ≤ a 2 and b 1 ≤ b 2 . If b 1 < a 1 , then (a 1 , b 1 ) ∈ opt (u) × opt (v) with b 1 ∈ opt (v) \ opt (u), which is contradictory by Lemma 1. Therefore a 1 ≤ b 1 . Similarly, if b 2 < a 2 , then (a 2 , b 2 ) ∈ opt (u) × opt (v) and a 2 ∈ opt (u) \ opt (v), which is again contradictory by Lemma 1. Therefore a 2 ≤ b 2 . It results that opt ⋆ (u) = a 1 opt ⋆ (v),which proves that the result of the proposition holds true.Then, Theorem 2.1 is an immediate consequence of the next Proposition A.5.Proposition A.5 Let u and v be two sequence of n real numbers such that u ≤ v, i.e. u i ≤ v i for each i ∈ {1, . . . , n}. Then opt ⋆ (u) ≤ opt ⋆ (v).Proof. Let K = {k ∈ {1, . . . , n} : u k < v k } and L = | K |. Denote h k = v k -u k for each k ∈ K,and denote by σ an arbitary bijection from {1, . . . , L} onto set K. It results:v = u + L l=1h σ(l) e σ(l) .

Table 1 :

 1 Table 1 gives the parameters for the batch SOM algorithms. They were fixed after several tests with these algorithms. Parameters Interval-valued data sets N Iter Number of neurons m T min T max Parameters List Moreover, in this paper δ is the Euclidean distance and the neighborhood kernel function is

	Car models Freshwater fish species City temperatures	30 30 30	9 (3 × 3 grid) 6 (2 × 3 grid) 9 (3 × 3 grid)	0.3 0.3 0.3	6.5 6.5 6.5

Table 2 :

 2 shows the results. Comparison between the batch SOM algorithms on the car models and freshwater fish species interval-valued data sets

	Car models data set		Freshwater fish species data set
		Comparison indexes		Comparison indexes
	Clustering algorithms CR	OERC	Clustering algorithms	CR	OERC
	IBSOM-L1	0.329	0.242	IBSOM-L1	0.496	0.083
	IABSOM-L1	0.477	0.152	IABSOM-L1	0.423	0.167
	IBSOM-L2	0.444	0.212	IBSOM-L2	-0.013	0.417
	IABSOM-L2	0.570	0.152	IABSOM-L2	0.209	0.333

Table 3 :

 3 Comparison between the batch SOM algorithms

	Car models interval-valued data set	Freshwater fish species interval-valued data set
			Clustering algorithms			Clustering algorithms
	Conf.	IBSOM-L1	IABSOM-L1	Conf.	IBSOM-L1	IABSOM-L1
		CR	OERC	CR	OERC		CR OERC	CR	OERC
	1	0.297	0.394	0.423	0.364	1	0.304	0.167	0.163	0.333
	2	0.320	0.424	-0.007	0.667	2	0.160	0.250	0.119	0.500
	3	0.320	0.424	-0.007	0.667	3	0.186	0.333	0.390	0.167
			Clustering algorithms			Clustering algorithms
	Conf.	IBSOM-L2	IABSOM-L2	Conf.	IBSOM-L2	IABSOM-L2
		CR	OERC	CR	OERC		CR OERC	CR	OERC
	1	-0.013	0.667	-0.009	0.667	1	0.166	0.333	0.233	0.333
	2	-0.013	0.697	-0.009	0.667	2	0.007	0.583	0.007	0.583
	3	-0.013	0.697	-0.009	0.667	3	0.007	0.583	0.007	0.583

Table 4 :

 4 Table 4 shows part of this interval-valued data set. In this application, the 12 interval-valued variables have been considered for clustering purposes. City temperature interval-valued data set with 12 interval variables

		January February . . . November December
	Amsterdam	[-4, 4]	[-5, 3]	. . .	[1, 10]	[-1, 4]
	. . .	. . .	. . .	. . .	. . .	. . .
	Mauritius	[22, 28]	[22, 29]	. . .	[19, 27]	[21, 28]
	. . .	. . .	. . .	. . .	. . .	. . .
	Zurich	[-11, 9]	[-8, 15] . . .	[0, 19]	[-11, 8]

Table 6

 6 Final grid of the city temperature interval-valued data set

		Athens, Lisbon	Frankfurt, Zurich	Amsterdam, Copenhagen
		Rome, San Francisco	(47 : 22 o N-50 : 06 o N)	Geneva, Moscow
		Tehran, Tokyo			Munich, Stockholm
		(35 : 41 o N-41 : 54 o N)				Toronto, Vienna
							(43 : 42 o N-59 : 19 o N)
		Bahrain, Cairo	Madrid, Seoul		London, New York
		Dubai, Hong Kong	(37 : 33 o N-40 : 23 o N)	Paris
			NewDelhi				(40 : 39 o N-51 : 30 o N)
		(22 : 16 o N-30 : 29 o N)
		Bombay, Calcutta,	Mauritius	Mexico City, Nairobi
		Colombo, Kuala Lumpur	(20 : 10 o S)		Sydney
		Madras, Manila			(33 : 51 o S-19 : 26 o N)
			Singapore
		(01 : 17 o N-22 : 56 o N)
	Figure 1: Var.		Cluster prototypes
		1	2	3	4	5	6	7	8	9
	JAN	6.2:11.6	-9.8:8.9	-3.5:0.8	12.5:19.7	0.8:8.9	0.8:6.2	20.6:29.6 21.5:27.8 11.6:25.1
	FEB	5.7:12.5	-7.7:15.4	-4.8:2.8	11.5:22.1	0.9:11.5	0.9:6.7	22.1:29.8 22.1:28.9 15.4:26.0
	MAR	7.5:16.1	-4.3:17.2	-1.0:7.5	15.0:24.7	3.2:16.1	2.1:9.6	22.5:31.1 21.5:29.0 17.2:24.7
	APR 11.2:17.5	0:21.3	2.5:12.5	18.8:28.8	6.2:18.8	5.0:15.0	23.8:32.6 21.3:27.5 16.3:23.8
	MAY 13.3:23.6	2.9:26.6	7.3:17.7	22.1:32.5 11.8:23.6	7.3:19.2	25.1:32.5 19.2:25.1 13.3:22.1
	JUN	17.9:27.7 6.54:29.4 11.4:21.2 24.5:34.3 16.3:29.4 11.4:21.2 24.5:32.7 17.9:24.5 11.4:21.2
	JUL	22.6:31.3 10.4:31.3 13.9:24.4 26.1:36.6 17.4:31.3 13.9:24.4 24.4:29.6 17.4:22.6 10.4:20.9
	AUG 22.3:30.9	8.5:25.7	13.7:22.3 25.7:34.3 15.4:29.1 13.7:20.6 25.7:29.1 17.1:22.3 10.3:20.6
	SEP	18.8:26.6	4.7:23.5	10.9:18.8 25.0:34.4 12.5:28.2 10.9:20.3 25.0:29.7 17.2:23.5 10.9:23.5
	OCT 14.5:21.2	2.6:22.5	6.6:13.2	21.2:30.4	7.9:23.8	7.9:15.9	23.8:30.4 18.5:25.1 13.2:23.8
	NOV	8.7:17.5	0:14.2	1.0:6.5	17.5:26.2	6.5:18.5	5.4:9.8	22.9:29.5 18.5:27.3 14.2:25.1
	DEC	6.4:13.7	-8.2:8.2	-1.8:2.7	13.7:21.0	0.9:9.1	0.9:6.4	22.0:30.2 21.0:28.4 12.8:22.9

gives the relevance weights of the interval-valued variabels into the clusters. It can be observed, for example, that in cluster 2 (Frankfurt and Zurich), the variable

Table 5 :

 5 Cluster prototypes: minimum and the maximum monthly temperatures "temperature of June" has the greatest relevance weight because in these cities the temperature in this month ranges very similarly, respectively, [3 : 27] and[6 : 30]. On contrary, the variable "temperature of November" has the smallest relevance weight in this cluster because in these cities the temperature in this month ranges more diferently, respectively, [-3 : 14] and [0 : 19].

Table 6 :

 6 City temperature data set: relevance weights of the interval-valued variabels into the clusters the best visualization and clustering characteristics provided by SOM neural networks with the flexibility offered by adaptive distances in the recognition of classes with different shapes and sizes and the robustness of the city-block distances.

	Var.				Clusters
	1	2	3	4	5	6	7	8	9
	JAN 0.62 1.38 0.48 0.76 1.01 0.75 0.50 0.66 0.40
	FEB 0.92 1.39 0.54 0.75 0.60 0.70 0.59 0.79 0.67
	MAR 1.53 0.65 0.51 0.77 0.42 1.23 0.91 0.92 2.01
	APR 2.06 0.77 0.87 0.86 1.43 1.83 1.21 1.05 1.52
	MAY 1.24 2.25 1.22 0.95 1.11 1.03 0.81 1.10 1.13
	JUN 0.87 2.58 1.75 1.23 0.91 0.80 1.24 1.16 0.71
	JUL 0.64 1.35 1.86 1.51 1.33 0.74 1.39 1.19 0.83
	AUG 0.62 0.73 2.00 1.36 2.02 0.84 1.37 1.21 0.95
	SEP 0.96 0.96 1.61 1.51 1.44 0.99 1.42 1.23 1.20
	OCT 1.76 1.05 1.42 1.14 0.58 0.91 2.00 1.13 2.16
	NOV 1.45 0.37 0.74 0.86 0.53 1.97 0.99 1.05 1.50
	DEC 0.49 0.46 0.62 0.71 2.19 0.89 0.54 0.71 0.47

Acknowledgement

The authors would like to thanks CNPq and FACEPE (Brazilian agencies) for their finacial support.

Appendix

A Proof of Theorem 2.1

Recall that the important issue is here the minimisation of n i=1 |y i -az i |, and that we denoted u i = y i z i for each i = 1, . . . , n. Then it is equivalent to minimise n i=1 z i | u i -a | with respect to the value of a. Recall also that by definition we have z i ∈ ]0, 1[. Thus, given an arbitrary sequence of n reals, denoted z = (z 1 , z 2 , . . . , z n ), we may associate with any sequence u = (u 1 , u 2 , . . . , u n ) of n reals a function φ by:

where we will suppose that z i ∈ ]0, 1[ for each i ∈ {1, . . . , n}. With these notation and hypothesis, and assuming that the terms of u are increasingly ordered, i.e.:

it was proved (see [START_REF] Jajuga | L1-norm based fuzzy clustering[END_REF][START_REF] Karst | Linear curve fitting using least deviations[END_REF]) that the set argmin x∈R φ(x ; u) is an interval of the form [u i , u j ] where j ∈ {i, i + 1}, for some i ∈ {1, . . . , n -1}. In other words, there exist i ∈ {1, . . . , n -1} such that argmin x∈R φ(x ; u) is an interval that is either reduced to {u i } or equal to [u i , u i+1 ].

Notation A.1 In order to simplify our notations, we will write opt (u) in place of argmin x∈R φ(x ; u). Moreover, given an increasing sequence u of n reals, opt (u) is then of the form [u i , u j ] where j ∈ {i, i + 1}, for some i ∈ {1, . . . , n -1}. Based on these notations, opt ⋆ (u) will designate the real defined as opt ⋆ (u) = u i + u j 2 (see the the algorithm presented hereabove before Theorem

2.1).

Notation A.2 Let u and v be any two finite sequences of n reals, and α and β be any two reals. The notation α u + β v will denote the sequence defined by:

In addition, given an integer n > 0, we define the sequence e k of n reals as follows:

The following equalities are easily checked: the third of them is proved as in Subcase 2-1:

We deduce that φ(b, v) -φ(a, v) > 0, which contradicts again the definition of b.

The following equalities hold clearly, the first of them being proved as in Case 1:

The following equalities hold, the third of them being proved as in Subcase 3-1:

we deduce that φ(b, v)φ(a, v) > 0, which contradicts again the definition of b.

The following equalities hold, the third of them being established as in Subcase 3-2:

Thus φ(b, v) -φ(a, v) = φ(b, u) -φ(a, u). This contradicts the fact that, by [START_REF] Guru | Multivalued type proximity measure and concept of mutual similarity value useful for clustering symbolic patterns[END_REF], at least one of the inequalities φ(b, v) -φ(a, v) ≤ 0 and φ(b, u) -φ(a, u) ≥ 0 is strict.

We conclude that b < a leads to a contradiction in any case, so that a ≤ b holds, as required.

Proposition A.4 Let u be any sequence of n real numbers, h > 0, k ∈ {1, . . . , n} and {z 1 , z 2 , . . . , z n } ⊆ ]0, 1[. Then opt ⋆ (u) ≤ opt ⋆ (u + h e k ).


Theunis Piersma

Flyway evolution is too fast to be explained by the Modern Synthesis: proposals for an 'extended' evolutionary research agenda

Keywords: Calidris canutus, Common garden experiment, Epigenetics, Evolution, Extended synthesis, Last Glacial Maximum, Migration, Red Knot, Shorebirds

In this paper I argue that to fully grasp the generation and maintenance of variation in the migratory phenotypes of (shore-)birds we need to expand our scientific search-image and include developmental processes and non-genetic pathways of inheritance in the explanatory frameworks. Traditionally, studies of micro-evolution of migratory phenotypes were restricted to comparative studies on migratory versus nonmigratory taxa, and artificial selection and heritability experiments on quantitative behavioural traits related to migration. Such studies had a focus on the genetic axis of inheritance and were restricted to songbirds. In avian groups such as the shorebird families Scolopacidae and Charadriidae all but a few island species are migrants, which precludes comparative studies at the species level. Just as other taxa, shorebirds have geographically separate breeding populations (either or not recognized as subspecies on the basis of morphological differences) which differentiate with respect to the length, general direction and timing of migration, including the use of fuelling at staging sites and the timing of moult. However, their breeding systems preclude artificial selection and heritability experiments on quantitative traits. This would seem to limit the prospects of evolutionary analysis until one realizes that the speed of evolutionary innovation in shorebird migratory life-histories may be so fast as to necessitate other avenues of explanation and investigation. According to our best current estimates based on mitochondrial gene sequence variation, in red knots Calidris canutus considerable phenotypic variation has evolved since the Last Glacial Maximum ca. 20,000 years ago, to the extent that six subspecies are currently recognized. This would be too short a time for the origin of the qualitatively and quantitatively distinct and non-overlapping traits to be explained by random point mutations followed by natural selection, although we cannot dismiss the possibility of previously unexpressed (standing) genetic variation followed by selection. I argue that to understand the flyway evolution of such shorebirds in the 'extended' evolutionary framework, we need to give due attention to developmental versatility and broad-sense epigenetic evolutionary mechanisms. This means that experimental studies at the phenotypic level are now necessary. This could involve a combination of observational studies in our rapidly changing world, common garden experiments, and even experiments involving global scale displacements of particular migratory phenotypes at different phases of development. I provide suggestions on how such experiments could be carried out.

Introduction

Most of what has been written about the evolution of bird migration [START_REF] Alerstam | Long-distance migration: evolution and determinants[END_REF] had a strong focus on the (micro-)evolution of migration traits in songbirds (e.g. [START_REF] Berthold | Genetic basis of migratory behaviour in European warblers[END_REF][START_REF] Berthold | Microevolution of migratory behaviour illustrated by the Blackcap Sylvia atricapilla: 1993 Witherby lecture[END_REF][START_REF] Able | Rapid 'evolution' of migratory behaviour in the introduced house finch of eastern North America[END_REF] and comparative studies between migrant and non-migrant taxa (e.g. [START_REF] Zink | Towards a framework for understanding the evolution of avian migration[END_REF][START_REF] Helbig | Evolution of migration: a phylogenetic and biogeographic perspective[END_REF][START_REF] Outlaw | Evolution of long-distance migration in and historical biogeography of Catharus thrushes: a molecular phylogenetic approach[END_REF][START_REF] Rappole | An integrative framework for understanding the origin and evolution of avian migration[END_REF][START_REF] Salewski | The evolution of bird migration-a synthesis[END_REF]. The portfolio included studies of artificial selection and heritability experiments on quantitative behavioural traits related to migration such as the duration and timing of migratory restlessness (e.g. [START_REF] Van Noordwijk | A framework for the stury of genetic variation in migratory behaviour[END_REF][START_REF] Pulido | The genetics and evolution of avian migration[END_REF][START_REF] Pulido | Current selection for lower migratory activity will drive the evolution residency in a migratory bird population[END_REF]. As impressive and as valuable all these studies are, I have found myself frustrated to apply the supposedly unifying but passerinebiased frameworks to the thinking about flyway evolution in the group of birds that I am most familiar with, the shorebirds, and especially the family of sandpipers Scolopacidae (Piersma et al. 1996) and the plover family Charadriidae (Piersma & Wiersma 1996).

Here is why. All but a few (island) species of shorebirds are migrants which precludes comparative studies on closely-related migratory and non-migratory species. As other taxa, shorebirds do have geographically separate breeding populations (either or not recognized as subspecies on the basis of morphological differences; [START_REF] Engelmoer | Geographical variation in waders[END_REF] which differentiate with respect to the length, general direction and timing of migration, including the use of fuelling at staging sites and the timing of moult.

However, the peculiarities of their breeding systems preclude studies of inheritance of quantitative traits such as migratory restlessness. Importantly, the traits on the basis of which subspecies are distinguished are distinct and do not overlap, i.e. they seem to show evolutionary novelty rather than the gradual variation that natural selection can work on [START_REF] Van Noordwijk | A framework for the stury of genetic variation in migratory behaviour[END_REF].

All of these impossibilities may actually turn out to be a blessing in disguise as it forces us to think about evolutionary mechanisms of flyway evolution other than those involving genes and the genetic inheritance pathway only. This is especially relevant as in shorebirds extant trait variation seem to have evolved over very short time spells relative to the evolutionary timescales necessary for new point mutations and subsequent natural selection to live out their creativity [START_REF] Barrett | Adaptation from standing genetic variation[END_REF]. For example, studies of neutral markers in the mitochondrial genome of Red Knots Calidris canutus have indicated that the outspoken global flyway pattern that we observe today (Fig. 1) may be of recent, post-Pleistocene, origin [START_REF] Buehler | Population divergence times and historical demography in Red Knots and Dunlins[END_REF][START_REF] Buehler | Reconstructing palaeoflyways of the late Pleistocene and early Holocene Red Knot (Calidris canutus)[END_REF]. The discontinuous circumpolar breeding range of red knots incorporates breeding areas of at least six populations that are morphologically sufficiently distinct to count as subspecies [START_REF] Tomkovich | An analysis of the geographic variability in Knots Calidris canutus based on museum skins[END_REF][START_REF] Tomkovich | A new subspecies of Red Knot Calidris canutus from the New Siberian Islands[END_REF], but which appear to have diversified recently from a small founder population that survived the Last Glacial Maximum at approximately 20,000 years ago. The subspecies are certainly distinct when it comes to their migratory trajectories and the seasonal timing of their movements [START_REF] Piersma | Fuel storage rates in Red Knots worldwide: facing the severest ecological constraint in tropical intertidal conditions?[END_REF]Buehler & Piersma 2008;[START_REF] Piersma | Using the power of comparison to explain habitat use and migration strategies of shorebirds worldwide[END_REF]. For the classic evolutionary mechanisms of random point mutations and gene selection mechanisms to explain the divergence of qualitatively and quantitatively distinct and non-overlapping traits, populations and time since divergence simply have been too small [START_REF] Haldane | The cost of natural selection[END_REF][START_REF] Nunney | The cost of natural selection revisited[END_REF].

In this brief contribution I aim to propose that to understand the flyway evolution of such shorebirds we need an 'extended' evolutionary framework with a mindset that is prepared to consider the many creative possibilities of individual development [START_REF] Turner | The tinkerer´s accomplice. How design emerges from life itself[END_REF]Badyaev 2011a,b) and broad-sense epigenetic evolutionary mechanisms (Jablonka and Lamb 2006). In addition to further genomic work to establish timelines of divergence in different clades of long-distance migrants, I will argue that we need intensive observational studies in our rapidly changing world and experimental studies at the phenotypic level.

Microevolution of contrasting seasonally changing phenotypes

Red Knots and other long-distance migrating shorebirds show amazing seasonal variation in phenotype. For example, body mass is doubled before take-off on flights of 5,000 km or more, and halved during the continuous flight which may take up to 10 days [START_REF] Battley | Empirical evidence for differential organ reductions during trans-oceanic bird flight[END_REF][START_REF] Gill Re | Extreme endurance flights by landbirds crossing the Pacific Ocean: ecological corridor rather than barrier?[END_REF]). These changes involve great modifications in fat stores, but also include modifications to most organs (other than the kidneys, the lungs and the brain; [START_REF] Piersma | Rapid changes in the size of different functional organ and muscle groups during refueling in a long-distance migrating shorebird[END_REF]Battley and Piersma 2004;[START_REF] Piersma | The flexible phenotype: A body-centred integration of ecology, physiology, and behaviour[END_REF]. On top of all these seasonal variations, shorebirds also adjust phenotypes to unpredictable environmental changes in food type, climatic conditions and disease pressure (Vézina et al. 2007[START_REF] Vézina | Phenotypic compromise in the face of conflicting ecological demands: an example in Red Knots Calidris canutus[END_REF]Buehler et al. 2008a,b).

If some of today's flyways indeed were established within the past 1000 years (as in the split between the Red Knot subspecies rufa and islandica; [START_REF] Buehler | Reconstructing palaeoflyways of the late Pleistocene and early Holocene Red Knot (Calidris canutus)[END_REF], then it follows that it is possible for very drastic changes in phenotype (body size, plumage characters, annual cycle characteristics) to occur within 100 generations (Fig. 2). The subspecies rufa and islandica are both relatively large-bodied [START_REF] Tomkovich | An analysis of the geographic variability in Knots Calidris canutus based on museum skins[END_REF]), but despite its name, rufa is the palest subspecies, whereas islandica is among the darkest (Buehler and Piersma 2008). Rufa has the longest seasonal migration, commuting between the sub-Antarctic during the nonbreeding season and the Canadian High Arctic during the breeding season (see Fig. 1), whereas the islandica which breeds nearby has the shortest migration of all the subspecies. The two subspecies differ with respect to departure directions, the timing of fuelling, flight and moult episodes, seasonal disease pressures (Buehler et al. 2009b) and dietespecially during northward migration [START_REF] Piersma | Fuel storage rates in Red Knots worldwide: facing the severest ecological constraint in tropical intertidal conditions?[END_REF].

Interestingly, and arguing for a hard-wired programming of annual cycles, the seasonal phenotypic changes shown outdoors are maintained by Red Knots and Great Knots Calidris tenuirostris kept in photoperiodic-and temperature-constant indoor environments [START_REF] Piersma | When a year takes 18 months: evidence for a strong circannual clock in a shorebird[END_REF][START_REF] Reneerkens | Expression of annual cycles in preen wax composition in red knots: constraints on the changing phenotype[END_REF][START_REF] Piersma | Endogenous circannual rhythmicity in body mass, molt, and plumage of Great Knots Calidris tenuirostris[END_REF]. When adult birds of the contrasting subspecies islandica and rufa are brought into similar conditions in captivity, they show very distinct annual cycles (Fig. 3). Birds of the islandica subspecies typically show a single mass peak in spring and carry their alternate plumage relatively briefly (see also [START_REF] Piersma | When a year takes 18 months: evidence for a strong circannual clock in a shorebird[END_REF][START_REF] Reneerkens | Expression of annual cycles in preen wax composition in red knots: constraints on the changing phenotype[END_REF]), whereas rufa knots in captivity show two mass peaks and carry the alternate plumage much longer.

If the divergence of the flyways of rufa and islandica knots really represent historic rather than prehistoric phenomena, this raises the compelling question as to how shorebirds could adjust migration-related traits so quickly.

Beyond hard-coding: soft coding and the extended synthesis

Over the last 100 years biology has strongly focused on the two-stage evolutionary process of mutational changes to the genome with downstream consequences for the phenotype on which natural selection operates. This is a relatively slow process, and the finding that rapid phenotypic change commonly occurs in a wide variety of organisms, has lead to explanations invoking selection for previously unexpressed (hidden or 'standing') genetic variation [START_REF] Barrett | Adaptation from standing genetic variation[END_REF][START_REF] Rouzic | Evolutionary potential of hidden genetic variation[END_REF]. Whilst I cannot dismiss this possibility, I also like to be open to explanations that go beyond the hardcoding of phenotypic traits.

Increasingly, evolutionary biologists appreciate that inheritance pathways other than the transmission of genes play a role in evolution (Jablonka and Lamb 2006;Pigliucci and Müller 2010). Interestingly, these 'soft-coded' inheritance pathways (Fig. 4) would imply considerable interaction and even trans-generational feedbacks between the environment and the phenotype, and this could speed up the ways in which organisms adapt to rapid environmental change [START_REF] Mj | Developmental plasticity and evolution[END_REF]Jablonka and Lamb 2006;[START_REF] Turner | The tinkerer´s accomplice. How design emerges from life itself[END_REF][START_REF] Laland | EvoDevo and niche construction: building bridges[END_REF][START_REF] Piersma | The flexible phenotype: A body-centred integration of ecology, physiology, and behaviour[END_REF].

The revolution in molecular biology has spawned an enormous research effort to refine the molecular basis of evolutionary change [START_REF] Bromham | Reading the story in DNA. A beginner's guide to molecular evolution[END_REF]). Yet, despite the availability of a wealth of advanced quantitative and molecular genetic techniques and innovative statistical tools [START_REF] Ellegren | Genetic basis of fitness differences in natural populations[END_REF][START_REF] Rice | A guide to the genomics of ecological speciation in natural animal populations[END_REF], an understanding of the ways in which genetic change underpin phenotypic change (i.e. the translation from genotype to phenotype) is a long way off [START_REF] Sheldon | Genetic perspectives on the evolutionary consequences of climate change in birds[END_REF]. The gene-up approach to the microevolution of bird migration is now yielding the first successes (e.g. [START_REF] Karell | Climate change drives microevolution in a wild bird[END_REF][START_REF] Mueller | Identification of a gene associated with avian migratory behaviour[END_REF]), but is still far removed from understanding the evolution and maintenance of trait variation. Apart from notable exceptions to do with rare diseases, the detection of DNA variations that explain the phenotype has been frustratingly complex [START_REF] Dowell | Genotype to phenotype: a complex problem[END_REF]. One of the reasons is that non-genetic factors play such an important role in the expression of genotypes (Jablonka and Lamb 2006;[START_REF] Turner | The tinkerer´s accomplice. How design emerges from life itself[END_REF]). Biology could be enriched by the acknowledgement that non-genetic factors such as developmental processes (expressed as phenotypic plasticity) and learning can affect the generation and maintenance of variation and rapid change of phenotypes (Fig. 5). The explanatory Darwinian ingredients of the Modern Synthesis [START_REF] Mayr | Animal species and evolution[END_REF][START_REF] Mayr | The growth of biological thought. Diversity, evolution, and inheritance[END_REF] no longer suffice [START_REF] Both | Flexibility of timing of avian migration to climate change masked by environmental constraints en route[END_REF]; Pigliucci and Müller 2010).

There are various 'soft-coded' ways in which the actual translation into phenotypes of the genetic code in DNA may be blocked or facilitated (Fig. 4). In the cellular epigenetic scenario, the presence or absence of methyl, acetyl or phosphate groups to the DNA or histones can transiently or permanently modify gene expression by altering the local chromatin structure [START_REF] Johannes | Epigenome dynamics: a quantitative genetics perspective[END_REF][START_REF] Law | Dynamic DNA methylation[END_REF]. These cellular epigenetic changes can be induced by environmental and/or genetic factors, and can remain relatively stable over several generations [START_REF] Teixeira | A role for RNAi in the selective correction of DNA methylation defects[END_REF][START_REF] Reinders | Compromised stability of DNA methylation and transposon immobilization in mosaic Arabidopsis epigenomes[END_REF]. Phenotype can also be changed by mechanisms other than (epi)genome variation (Fig. 4). For example, the physiology of a bird embryo can also be affected by variable levels of maternal hormones, immune factors, etc.; developmental inheritance). Also, young birds can learn the migration route from more experienced birds (behavioural inheritance).

Research opportunities in the anthropocene

We live in the Anthropocene [START_REF] Steffen | The Anthropocene: are humans now overwhelming the great forces of nature?[END_REF][START_REF] Kolbert | Enter the anthropocene: age of man[END_REF], an era of loss and of opportunity. Our time is one of strong declines in biodiversity [START_REF] Pereira | Scenarios for global biodiversity in the 21 st century[END_REF]), yet it is also a time when we can learn from the rapid ongoing changes if we care to look. 'Looking these individuals (e.g. [START_REF] Baker | Rapid population decline in Red Knots: fitness consequences of decreased refuelling rates and late arrival in Delaware Bay[END_REF][START_REF] Leyrer | Seasonal survival rates of a migratory shorebird suggest tropical wintering is riskier than migration[END_REF]. Recent advances in multistate modeling [START_REF] Lebreton | Modeling individual animal histories with multistate capture-recapture models[END_REF]) should enable the estimation of variation in survival rates over several generations within and between flyways and also obtain estimates of dispersal rates. In the case of the best studied Red Knot subspecies rufa, islandica and canutus, this would yield estimates of vital rates and dispersal during periods of habitat decline and restoration [START_REF] Baker | Rapid population decline in Red Knots: fitness consequences of decreased refuelling rates and late arrival in Delaware Bay[END_REF][START_REF] Kraan | Landscape-scale experiment demonstrates that Wadden Sea intertidal flats are used to capacity by molluscivore migrant shorebirds[END_REF]) and thus enable us to examine the demographic drivers of micro-evolution.

Phenotypic experimentation

Recent observations suggests that individual Red Knots (rufa as well as islandica) may sometimes switch flyways. This indicates that individual flexibility of flyway use is higher than what we have assumed so far. An adult Red Knot marked in northern Norway (presumably islandica) was resighted a year later in the Mingan Archipelago, in the Gulf of St. Lawrence, Canada. Another bird marked at Mingan (presumably rufa) had moved to Iceland two years after marking [START_REF] Wilson | Three records of Red Knots Calidris canutus possibly changing flyways[END_REF]. Given the highly sociable behaviour of this species, individuals may be tuned by the behaviour of group members [START_REF] Helm | Sociable schedules: interplay between avian seasonal and social behaviour[END_REF], enabling them to successfully switch between flyways.

I suggest that we could find out about the degrees of flexibility, and the epigenetic mechanisms involved (Fig. 4), by carrying out two types of phenotypic experiments: (1) bring birds together in common environments (common garden experiments) and ( 2) (Perdeck 1958[START_REF] Perdeck | Orientation of Starlings after displacement to Spain[END_REF][START_REF] Perdeck | An experiment on the orientation of juvenile Starlings during spring migration[END_REF]. We could fit birds with small solar-energized satellite tags and reciprocally translocate them between flyways. To show the scope for testing explicit evolutionary/developmental hypotheses of such phenotypic experimentation, I have worked out a case where young and old rufa and islandica knots are reciprocally displaced between the staging areas on southward migration (Table 1). We can use the contrast between juveniles and adults to see whether having experienced one or more full migration cycles affects the capacity to adjust flexibly to a new situation and fly with the 'receiving' flocks at the new location, or whether the routines have become fixed with respect to phenotypic change and migration.

displacing
Thus, by including young and older birds in the experiment, we can address the role of age-dependent behavioural inheritance, i.e. learning, on the expectation that in their first year, learning phenotypes would still be able to adjust phenotypically to new regimes, whereas older birds might not [START_REF] Sutherland | Evidence for flexibility and constraint in migration systems[END_REF]. Fully flexible individuals will move with their new flocks, and even adjust the timing of fuelling and moult. If this would occur we have to explain an interesting contrast with the results from the preliminary aviary experiments (Fig. 3). Such flexibility would be at variance with the idea that the divergent traits have a rigid genetic background and would emphasize the creative force of two-way interactions between organisms and their environment [START_REF] Laland | EvoDevo and niche construction: building bridges[END_REF]).

[Figures:]

Fig. 1 The worldwide flyways of six morphologically distinct subspecies of Red Knot.

Polygons in the Arctic depict breeding ranges; circles depict principal wintering areas with the diameters of circles indicating relative numbers of birds. Arrows depict north-and southward migration routes and use of en route sites. Projected above the contemporary distribution of red knots is a 'tree' summarizing the phylo-geographic structure as presently understood [START_REF] Buehler | Population divergence times and historical demography in Red Knots and Dunlins[END_REF]. Note that the subspecies rufa and islandica are impossible to tell apart on the basis of neutral genetic markers yet show very different migratory pathways. Also note that whereas most subspecies have distinct wintering areas, the closely related piersmai (mainly tropical northwest Australia) and rogersi (mainly New Zealand) show some degree of overlap that may hint at ongoing microevolutionary change. The remaining three are all 'somatic' and include 'developmental inheritance' (e.g. through maternal effects), 'behavioural inheritance' (through niche construction), and 'symbolic inheritance'. One of the reasons that it took biologists so long to distinguish these layers is that they are thoroughly intertwined. There is also 'reciprocal causation', especially between niche and body. Note that 'symbolic inheritance' is specific to organisms that read books, watch TV and write grant applications. Of the five possible inheritance pathways of information transfer between generations, two (developmental inheritance and behavioural inheritance) would be especially relevant for the fast evolutionary change of flyways and annual schedules. Developed from [START_REF] Jablonka | Evolution in four dimensions: Genetic, epigenetic, behavioral and symbolic variation in the history of life[END_REF]Lamb (2005, 2007) and adapted after [START_REF] Piersma | The flexible phenotype: A body-centred integration of ecology, physiology, and behaviour[END_REF]. [Tables :]

Table 1 Predictions to what will happen to birds translocated across the Atlantic from either the islandica or rufa subspecies of Red Knot, depending on how migration and annual routines are flexibly orchestrated, and whether learning from older birds takes place during early life. For the predictions for 'fixed circannual programmes' we listed the scenario where red knots after displacement know latitude, but not longitude (possibility-1), or know precisely where they are with respect to where they come from (possibility-2).

  carefully' at global scales is now made possible by the close connections (through internet and cheap airfares) of focussed observers worldwide (e.g. Rahkimberdiev et al. 2011), the availability of capture-recapture datasets spanning several generations of birds (van der Jeugd et al. , and by the possibility to examine survival and dispersal using an amazing array of remote sensing and tracking tools (Robinson et al. 2010). Even for small organisms that travel the world such as Red Knots, the tools are now available to track their survival and movements across the globe with considerable spatial and temporal precision. Building on the ongoing demographic studies assembled within a worldwide collaborative research network with a particular emphasis on individually colour-ringing Red Knots and other shorebirds and resighting them (Global Flyway Network, see Piersma 2007), comparative analyses can be done of dispersal and survival based on sample sizes of several thousands individually marked Red Knots and multiple resightings of many of

Fig. 2 Fig. 3 .

 23 Fig.2Contrasts in the migration and annual cycle characteristics of the two most closely related subspecies of Red Knots (rufa and islandica), with a suggestion of seven traits that would have to evolve considerable quantitative and qualitative novelty in the presumed descendent subpecies islandica within a short spell of time[START_REF] Buehler | Reconstructing palaeoflyways of the late Pleistocene and early Holocene Red Knot (Calidris canutus)[END_REF]). The bars show the typical (average) timing of birds carrying a basic plumage (grey) or the alternate plumage (rusty) and the timing of moult from one plumage type into the other (light rusty). Also indicated are the timings of northward (upward pointing triangles) and southward (downward pointing triangles) flights, generally three each in rufa and two each in islandica.

Fig. 4

 4 Fig.4In addition to the genetic variation transmitted from generation to generation through the germline, there are four additional 'epigenetic' inheritance pathways. The first of those, 'cellular epigenetic inheritance', transmits acquired information via the gametes.

Fig. 5

 5 Fig. 5 Schematic representation of the key concepts of Darwinism (centre), the Modern Synthesis (intermediate field) and a more extended synthesis of evolutionary explanations (outer ring) of life forms on earth. This scheme, modified after Pigliucci & Müller (2010), aims to show the near-continuous expansion of evolutionary theory with new and increasingly non-genetic concepts for mechanisms of change. I propose that an understanding of the evolutionary mechanisms of rapid flyway evolution would require research efforts on phenotypic plasticity and learning.

  birds to new conditions (translocation experiments). Building on preliminary results reported in Fig. 3, bringing birds from different flyways under identical environmental conditions would allow us to examine the degree that the seasonally changing phenotypes are (in-)flexible for genetic and non-genetic reasons, or whether the birds can adjust to alternative photoperiodic regimes. If the degree of adjustment is agedependent, this would additionaly tell us if social learning is involved. The common garden experiments should be complemented by experiments 'in the wild'. In the 1950s and 1960s Perdeck and collaborators translocated 15,000 Starlings Sturnus vulgaris and 1250 Chaffinches Fringilla coelebs from The Netherlands to Switzerland and 3500 Starlings to Spain in what is now one of the most classic series of experiments in the study of bird migration

  Fixed circannual programme-2 Return to Europe Return to Europe Return to the Americas

		islandica moved to Canada	rufa moved to Wadden Sea
		as juvenile	as adult	as juvenile	as adult
	Fixed circannual programme-1 Stay in the north	Stay in the north	Fly south with	Fly south with
		(as in Europe)	(as in Europe)	canutus	canutus
					Returns to the
					Americas
	Flexible during early ontogeny Migrate to S.	Stay north or	Stay in Europe or fly	Fly south with
		America	return to Europe	south with canutus	canutus or return to
					America
	Fully flexible	Migrate to S.	Migrate to S.	Stay in Europe or fly	Stay in Europe or fly
		America	America	south with canutus	south with canutus

Acknowledgements

The ideas presented here developed slowly over many years during discussions with Allan J. Baker, Ritsert Jansen, Deborah M. Buehler, Yvonne I. Verkuil, Franjo Weissing, David W. Winkler, Christiaan Both, Robert E. Gill, T. Lee Tibbitts, Bob Ricklefs, Hugh Boyd, Eva Jablonka, Barbara Helm, Andreas Helbig, Robert Zink, and many others. I am grateful to Franz Bairlein for providing the opportunity to present these ideas at the Centennial Symposium of the Vogelwarte Helgoland, and for his patient prompting to actually get a manuscript. Maarten Brugge was responsible for the husbandry of, and data collection on, the captive red knots, Dick Visser drew the figures, and Yvonne Verkuil and Eldar Rakhimberdiev provided constructive comments on the manuscript.