Stéphan Clémençon
email: stephan.clemencon@telecom-paristech.fr

Romaric Gaudel
email: romaric.gaudel@telecom-paristech.fr

Jérémie Jakubowicz
email: jeremie.jakubowicz@telecom-paristech.fr

Jérémie Jakubowicz Ltci

Clustering Rankings in the Fourier Domain

Keywords: clustering, rank data, non-commutative harmonic analysis, feature selection

come

Introduction

In a wide variety of applications, ranging from consumer relationship management (CRM) to economics through the design of recommendation engines for instance, data are often available in the form of rankings, i.e. partially ordered lists of objects expressing preferences (purchasing, investment, movies, etc.). Due to their global nature (modifying the rank of an object may affect that of many other objects), rank data generally deserve a special treatment in regards to statistical analysis. The latter have been indeed the subject of a good deal of attention in the machine-learning literature these last few years. Whereas numerous supervised learning algorithms have been recently proposed in order to predict rankings accurately, see [START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF], [PTA + 07], [START_REF] Clémençon | Tree-based ranking methods[END_REF] for instance, novel techniques have also been developed to handle input data, that are themselves of the form of rankings, for a broad range of purposes: computation of centrality measures such as consensus or median rankings (see [START_REF] Meila | Consensus ranking under the exponential model[END_REF] or [START_REF] Clémençon | Kantorovich distances between rankings with applications to rank aggregation[END_REF] for instance), modelling/estimation/simulation of distribution on sets of rankings (see [START_REF] Mallows | Non-null ranking models[END_REF], [START_REF] Fligner | Distance based ranking models[END_REF], [START_REF] Lebanon | Conditional models on the ranking poset[END_REF], [START_REF] Mandhani | Tractable search for learning exponential models of rankings[END_REF] and [START_REF] Lebanon | Non-parametric modeling of partially ranked data[END_REF] among others), ranking based on preference data (refer to [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF], [START_REF] Crammer | Pranking with ranking[END_REF] or [START_REF] Desjardins | Learning user preferences for sets of objects[END_REF]).

It is the main goal of this paper to consider the issue of clustering rank data from a novel perspective, taking the specific nature of the observations into account. We point out that the method promoted in this paper is by no means the sole possible applicable technique. The most widely used approach to this problem consists in viewing rank data (and, more generally, ordinal data), when renormalized in an appropriate manner, as standard numerical data and apply state-of-the-art clustering techniques, see Chapter 14 in [START_REF] Hastie | The Elements of Statistical Learning[END_REF]. Alternative procedures of probabilistic type, relying on mixture modeling of probability distributions on a set of (partial) rankings, can also be considered, following in the footsteps of [START_REF] Fligner | Multistage ranking models[END_REF]. Rank data are here considered as probability distributions on the symmetric group S n , n ≥ 1 denoting the number of objects to be (tentatively) ranked and our approach crucially relies on the Fourier transform on the set of mappings f : S n → R. Continuing the seminal contribution of [START_REF] Diaconis | A generalization of spectral analysis with application to ranked data[END_REF], spectral analysis of rank data has been recently considered in the machine-learning literature for a variety of purposes with very promising results, see [START_REF] Kondor | Ranking with kernels in Fourier space[END_REF], [START_REF] Huang | Fourier theoretic probabilistic inference over permutations[END_REF] or [START_REF] Huang | Riffled independence for ranked data[END_REF]. This paper pursues this line of research. It aims at showing that, in the manner of spectral analysis in signal processing, Fourier representation is good at describing properties of distributions on S n in a sparse manner, "sparse" meaning here that a small number (compared to n!) of Fourier coefficients carry most of the significant information, from the perspective of clustering especially. As shown in [START_REF] Diaconis | Group representations in probability and statistics[END_REF], the main appeal of spectral analysis in this context lies in the fact that Fourier coefficients encode structural properties of ranking distributions in a very interpretable fashion. Here we propose to use these coefficients as features for defining clusters. More precisely, we shall embrace the approach developed in [START_REF] Witten | A framework for feature selection in clustering[END_REF] (see also [START_REF] Friedman | Clustering objects on subsets of attributes[END_REF]), in order to find clusters on an adaptively-chosen subset of features in the Fourier domain.

The article is organized as follows. Section 2 describes the statistical framework, set out the main notations and recall the key notions of Fourier representation in the context of distributions on the symmetric group that will be used in the subsequent analysis. Preliminary arguments assessing the efficiency of the Fourier representation for discrimination purposes are next sketched in Section 3. In particular, examples illustrating the capacity of parsimonious truncated Fourier expansions to approximate efficiently a wide variety of distributions on S n are exhibited. In Section 4, the rank data clustering algorithm we propose, based on subsets of spectral features, is described at length. Numerical results based on artificial and real data are finally displayed in Section 5. Technical details are deferred to the Appendix.

In this section, we recall key notions on spectral analysis of functions defined on the symmetric group S n and sketch an approximation framework based on this Fourier type representation, that will underly our proposed clustering algorithm.

Setup and First Notations

Here and throughout, n ≥ 1 denotes the number of objects to be ranked, indexed by i = 1, . . . , n. For simplicity's sake, it is assumed that no tie can occur in the present analysis, rankings being thus viewed as permutations of the list of objects {1, . . . , n} and coincide with the elements of the symmetric group S n of order n. Extension of the concepts developed here to more general situations (including partial rankings and/or bucket orders) will be tackled in a forthcoming article. The set of mappings f : S n → C is denoted by C[S n ]. For any σ ∈ S n , the function on S n that assigns 1 to σ and 0 to all τ = σ is denoted by δ σ . The linear space C[S n ] is equipped with the usual inner product: f, g = σ∈Sn f (σ)g(σ), for any (f, g) ∈ C[S n ] 2 . The related hilbertian norm is denoted by ||.||. Incidentally, notice that {δ σ : σ ∈ S n } corresponds to the canonical basis of this Hilbert space. The indicator function of any event E is denoted by I{E}, the trace of any square matrix A with complex entries by tr(A), its conjugate by A * and the cardinality of any finite set S by #S. Finally, for any m ≥ 1, the matrix space M m×m (C) is equipped with the scalar product < A, B > m = tr(A * B) and the Hilbert-Schmidt norm ||A|| HS(m) =< A, A > 1/2 m .

Rank Data as Distributions on S n . The framework we consider stipulates that the observations are of the form of probability distributions on S n , i.e. elements f of C[S n ] taking their values in [0, 1] such that σ∈Sn f (σ) = 1. This models a variety of situations encountered in practice: indeed, list of preferences are rarely exhaustively observed, it is uncommon that rank data of the form of full permutations are available (σ -1 (i) indicating the label of the i-th most preferred object, i = 1, . . . , n). As shown by the following examples, a natural way of accounting for the remaining uncertainty is to model the observations as probability distributions. Precisely, let E 1 , . . . , E K be a partition of S n , with 1 ≤ K ≤ n!. When one observes which of these events is realized, i.e. in which of these subsets the permutation lies, the ensemble of possible observations is in one-to-one correspondence with the set of distributions {f k : 1 ≤ k ≤ K}, where f k denotes the conditional distribution of S given S ∈ E k , S being uniformly distributed on S n , i.e.

f k = (1/#E k ) • σ∈E k δ σ .
In all these situations, the number of events K, through which preferences can be observed, may be very large.

Example 1. (Top-k lists.) In certain situations, only a possibly random number m of objects are ranked, those corresponding to the most preferred objects. In this case, the observations are related to the events of the type E = {σ ∈ S n :

(σ(i 1 ), . . . , σ(i m )) = (1, . . . , m)} where m ∈ {1, . . . , n} and (i 1 , . . . , i m ) is a m-tuple of the set of objects {1, . . . , n}.

Example 2. (Preference data.) One may also consider the case where a collection of objects, drawn at random, are ranked by degree of preference. The events observed are then of the form E = {σ ∈ S n : σ(i 1 ) < . . . < σ(i m )} with m ∈ {1, . . . , n} and (i 1 , . . . , i m ) a m-tuple of the set of objects {1, . . . , n}.

Example 3. (Bucket orders.) The top-k list model can be extended the following way, in order to account for situations where preferences are aggregated. One observes a random partition B 1 , . . . , B J of the set of instances for which: for all 1 ≤ j < l ≤ J and for any (i, i

) ∈ B j × B l , σ(i) < σ(i ).
Hence, our objective is here to partition a set of N probability distributions f 1 , . . . , f N on S n into subgroups C 1 , . . . , C M , so that the distributions in any given subgroup are closer to each other (in a sense that will be specified) than to those of other subgroups. When equipped with a dissimilarity measure D : S n × S n → R + , the clustering task is then classically cast in terms of minimization of the empirical criterion

W(C) = M m=1 1≤i<j≤n D(f i , f j ) • I{(f i , f j ) ∈ C 2 m }, (1)
over the set of all possible partitions C = {C m : 1 ≤ m ≤ M } with M ≥ 1 cells, the choice M requiring next the use of model selection techniques, see [START_REF] Tibshirani | Estimating the number of clusters in a data set via the gap statistic[END_REF] and the references therein. Beyond the fact that this corresponds to a NP-hard optimization problem for which acceptably good solutions can be computed after a reasonable lapse of time through a variety of (meta-)heuristics, the choice of a distance or a dissimilarity measure between pairs of distributions on S n is crucial. We emphasize that depending on the measure D chosen, one may either enhance specific patterns in the rank data or else make them disappear. This strongly advocates for the application of recent adaptive procedures that permit to achieve great flexibility in measuring dissimilarities, see [START_REF] Witten | A framework for feature selection in clustering[END_REF] (refer also to [START_REF] Friedman | Clustering objects on subsets of attributes[END_REF]), selecting automatically a subset of attributes in order to emphasize differences between the cluster candidates. In this article, an attempt is made to implement this approach when attributes/features are those that are output by spectral analysis on C[S n ].

The Fourier Transform on S n

Fourier analysis is an extraordinary powerful tool, whose usefulness and ubiquity is unquestionable and well documented, see [K 89,KLR95]: in signal and image processing it is used for the purpose of building filters and extracting information, in probability theory it permits to characterize probability distributions and serves as a key tool for proving limit theorems, in time-series analysis it allows to analyze second order stationary sequences, in analysis for solving partial differential equations, etc. In fact, it is hard to think about a tool in (applied) mathematics that would be more widespread than the Fourier transform. The most common framework deals with functions f : G → C where G denotes the group R of real numbers, the group Z of integers or the group Z/N Z of integers modulo N . The elements of the abelian group G act on functions f : G → C by translation. Recall that, for any g ∈ G, the translation by g is defined by

T g (f ) : x ∈ G → f (x -g).
A crucial property of the Fourier transform F is that it diagonalizes all translation operators simultaneously: ∀g ∈ G,

F(T g (f ))(ξ) = χ g (ξ) • Ff (ξ),
where χ g (ξ) = exp(2iπgξ) and ξ belongs to the dual group G (being R, R/Z and Z/N Z when G is R, Z and Z/N Z respectively). Consequently, Fourier transform provides a sparse representation of all operators that are spanned by the collection of translations, such as convolution operators.

The diagonalization view on Fourier analysis extends to the case of noncommutative groups such as S n . However, in this case, the related eigenspaces are not necessarily of dimension 1 anymore. In brief, in this context Fourier transform only "block-diagonalizes" translations, as shall be seen below.

The Group Algebra C[S n ]. The set C[S n
] is a linear space on which S n acts linearly as a group of translations

T σ : f ∈ C[S n ] → T σ (f ) = ν∈Sn f (ν • σ -1 )δ ν .
For clarity's sake, we recall the following notion.

Definition 1. (Convolution Product) Let (f, g) ∈ C[S n ] 2 .
The convolution product of g with f (with respect to the counting measure on S n ) is the function defined by f * g :

σ ∈ S n → ν∈Sn f (ν)g(ν -1 • σ) ∈ C.
Remark 1. Notice that one may also write, for any (f, g) ∈ C[S n ] 2 and all σ ∈ S n , (f * g)(σ) ν∈Sn f (σ • ν -1 )g(ν). The convolution product f * δ σ = τ ∈ S n → f (τ • σ -1 ) reduces to the right translation of f by σ, T σ f namely. Observe in addition that, for n > 2, the convolution product is not commutative. For instance:

δ σ * δ τ = δ σ•τ = δ τ •σ = δ τ * δ σ , when σ • τ = τ • σ.
The set C[S n ] equipped with the pointwise addition and the convolution product (see Definition 1 above) is referred to as the group algebra of S n .

Canonical Decomposition. In the group algebra formalism introduced above, a function f is an eigenvector for all the right translations (simultaneously) whenever ∀σ ∈ S n , δ σ * f = χ σ f , where χ σ ∈ C for all σ ∈ S n . For instance, the function f = σ∈Sn δ σ ≡ 1 can be easily seen to be such an eigenvector with χ σ ≡ 1. In addition, denoting by σ the signature of any permutation σ ∈ S n (recall that it is equal to (-1) I(σ) where I(σ) is the number of inversions of σ, i.e. the number of pairs (i, j) in {1, . . . , n} 2 such that i < j and σ(i) > σ(j)), the function f = σ∈Sn σ δ σ is also an eigenvector for all the right translations with χ σ = σ . If one could possibly find n! such linearly independent eigenvectors, one would be able to define a notion of Fourier transform with properties very similar to those of the Fourier transform of functions defined on Z/N Z.

Unfortunately, due to the lack of commutativity of S n , the functions mentioned above are the only eigenvectors common to all right translation operators, up to a multiplicative constant. Switching from the notion of eigenvectors to that of irreducible subspaces permits to define the Fourier transform, see [START_REF] Serre | Algebraic groups and class fields[END_REF].

Definition 2. (Irreducible Subspaces) A non trivial vector subspace V of C[S n ] (i.e. different from {0} and C[S n ]) is said to be irreducible when it is stable under all right translations, i.e. for all (σ, f ) ∈ S n × V , δ σ * f ∈ V and contains no such stable subspace except {0} and itself. Two irreducible subspaces V 1 and V 2 are said to be isomorphic when there exists a bijective linear map

T : V 1 → V 2 that commutes with translations: ∀f ∈ V 1 , ∀σ ∈ S n , T (δ σ * f ) = δ σ * T (f ).
It follows from a well known result in Group Theory (in the compact case, see Peter-Weyl theorem in [START_REF] Serre | Algebraic groups and class fields[END_REF] for instance) that C[S n ] decomposes into a direct sum of orthogonal irreducible subspaces. Spectral/harmonic analysis of an element f ∈ C[S n ] consists then in projecting the latter onto these subspaces and determine in particular which components contribute most to its "energy" ||f || 2 . In the case of the symmetric group S n , the elements of the irreducible representation cannot be indexed by "scalar frequencies", the Fourier components being actually indexed by the set R n of all integer partitions of n, namely:

R n = ξ = (n 1 , . . . , n k ) ∈ N * k : n 1 ≥ • • • ≥ n k , k i=1 n i = n , 1 ≤ k ≤ n .
Remark 2. (Young tableaux) We point out that each element (n 1 , . . . , n k ) of the set R n can be visually represented as a Young tableau, with k rows and n i cells at row i ∈ {1, . . . , k}. For instance, the partition of n = 9 given by ξ = (4, 2, 2, 1) and its conjugate ξ can be respectively encoded by the diagrams:

and .

Hence, the Fourier transform of any function

f ∈ C[S n ] is of the form: ∀ξ ∈ R n , Ff (ξ) = σ∈Sn f (σ)ρ ξ (σ),
where ρ ξ is a function on S n that takes its values in the set of unitary matrices with complex entries of dimension

d ξ × d ξ . Note that ξ d 2 ξ = n!.
For clarity, we recall the following result, that summarizes some crucial properties of the spectral representation on S n , analogous to those of the standard Fourier transform. We refer to [START_REF] Diaconis | Group representations in probability and statistics[END_REF] for an nice account of linear representation theory of the symmetric group S n as well as some of its statistical applications.

Proposition 1. (Main properties of F) The following properties hold true.

(i) (Plancherel formula) ∀(f, g) ∈ C[S n ] 2 , f, g =< Ff, Fg >, where < Ff, Fg >= 1 n! ξ∈Rn d ξ < Ff (ξ), Fg(ξ) >. (ii) (Inversion formula) ∀f ∈ C[S n ], f = 1 n! ξ∈Rn d ξ < ρ ξ (.), Ff (ξ) > d ξ . (iii) (Parseval formula) ∀f ∈ C[S n ], ||f || 2 = 1 n! ξ∈Rn d ξ ||Ff (ξ)|| 2 HS(d ξ ) .
Example 4. For illustration purpose, Fig. 1 below displays the spectral analysis of the Mallows distribution (cf [START_REF] Mallows | Non-null ranking models[END_REF]) when n = 5, given by f σ0,γ (σ

) = { n j=1 (1-exp{-γ})/(1-exp{-jγ})}•exp{-γ •d τ (σ, σ 0 )} for all σ ∈ S n , denot- ing by d τ (σ, ν) = 1≤i<j≤n I{σ • ν -1 (i) > σ • ν -1 (j)} the Kendall τ distance,
for several choices of the location and concentration parameters σ 0 ∈ S n and γ ∈ R * + . Precisely, the cases γ = 0.1 and γ = 1 have been considered. As shown by the plots of the coefficients, the more spread the distribution (i.e. the smaller γ), the more concentrated the Fourier coefficients. Remark 3. (Computational issues) We point out that rank data generally exhibit a built-in high dimensionality. In many applications, the number of objects n to be possibly ranked is indeed very large. Widespread use of methods such as that presented here is conditioned upon advances in the development of practical fast algorithms for computing Fourier transforms. All the displays presented in this paper have been computed thanks to the C++ library S n ob, see [START_REF] Kondor | Snob: a C++ library for fast Fourier transforms on the symmetric group[END_REF], that implements Clausen's fast Fourier transform for S n .

In this section, an attempt is made to exhibit preliminary theoretical and empirical results, which show that spectral analysis of rank data can provide sparse and/or denoised representations of rank data in certain situations, that are useful for discrimination purposes.

Sparse Linear Reconstruction. Let F be a random element of C[S n ] and consider the following approximation scheme that consists in truncating the Fourier representation by retaining the coefficients with highest norm only in the reconstruction. It can be implemented in three steps, as follows. Let K ∈ {1, . . . , n!} be fixed.

1. Perform the Fourier transform, yielding matrix coefficients {FF (ξ)} ξ∈Rn .

2. Sort the frequencies by decreasing order of magnitude of expected weighted norm of the corresponding matrix coefficients: ξ (1) , . . ., ξ (K) , where

E d ξ (1) ||FF (ξ (1) )|| 2 HS(d ξ (1) ) ≥ . . . ≥ E d ξ (M ) ||FF (ξ (M ) )|| 2 HS(d ξ (M ) ) , with M = #R n , d ξ (m)
denoting the dimension of the irreducible space related to the frequency ξ (m) . 3. Keeping the K coefficients with largest second order moment, invert the Fourier transform, producing the approximant

F K (σ) = 1 n! K k=1 d ξ (k) < ρ ξ (k) (σ), FF (ξ (k) ) > d ξ (k) . (2)
The capacity of Fourier analysis to provide a sharp reconstruction of F can be evaluated through the expected distortion rate, namely 2 shows the decay of a Monte-Carlo estimate (based on 50 runs) of the distortion rate K (F ) as the number K of retained coefficient grows, when F is drawn at random in a set of L Mallows distributions. As expected, the more spread the realizations of F (i.e. the smaller γ and/or the larger L), the faster the decrease (i.e. the more efficient the Fourier-based compression).

K (F ) = E[||F - F K || 2 ]/E[||F || 2 ]. Fig.
Remark 4. (On stationarity.) For simplicity, suppose that E[F (σ)] is constant, equal to 0 say. The expected distortion rate can be then easily expressed in terms of the covariance Φ(σ, σ ) = E[F (σ)F (σ )] and in the case when F is "stationary", i.e. when Φ(σ, σ ) = φ(σσ -1 ), it may be shown that Fourier representation has optimal properties in regards to linear approximation/compression, since the covariance operator is then diagonalized by the Fourier basis, exactly as in the well-known L 2 situation. Notice incidentally that such kernels φ(σσ -1 ) have already been considered in [START_REF] Kondor | Snob: a C++ library for fast Fourier transforms on the symmetric group[END_REF] for a different purpose. Developing a full approximation theory based on Fourier representation of C[S n ], and defining in particular specific subspaces of C[S n ] that would be analogous to Sobolev classes and sparsely represented in the Fourier domain is beyond the scope of this paper and will be tackled in a forthcoming article. An Uncertainty Principle. The following proposition states an uncertainty principle in the context of the symmetric group. It extends the result established in [START_REF] Donoho | Uncertainty principles and signal recovery[END_REF] in the abelian setup to a non-commutative situation and can be viewed as a specific case of the inequality proved in [START_REF] Matolcsi | Intersection des mesures spectrales conjuguées[END_REF] through operator-theoretic arguments. A simpler proof, directly inspired from the technique used in [START_REF] Donoho | Uncertainty principles and signal recovery[END_REF] in the commutative case, is given in the Appendix.

Proposition 2. (Uncertainty principle) Let f ∈ C[S n ]. Denote by supp(f ) = {σ ∈ S n : f (σ) = 0}
and by supp(Ff ) = {ξ ∈ R n : Ff (ξ) = 0} the support of f and that of its Fourier transform respectively. Then, we have:

#supp(f ) • ξ∈supp( f ) d 2 ξ ≥ n!. (3)
Roughly speaking, the inequality (3) above says in particular that, if the Fourier representation is sparse, i.e. Ff (ξ) is zero at many frequencies ξ, f (σ) is not.

De-noising in C[S n ].
The following example shows how to achieve noise suppression through Fourier representation in some specific cases. Let A = ∅ be a subset of S n and consider the uniform distribution on it:

f A = (1/#A)• σ∈A δ σ .
We suppose that it is observed with noise and shall study the noise effect in the Fourier domain. The noise is modeled as follows. Let T denote a transposition drawn at random in the set T of all transpositions in S n (P{T = τ } = 2/(n(n -1)) for all τ ∈ T), the noisy observation is:

f = f A * δ T .
Notice that the operator modeling the noise here is considered in [START_REF] Kondor | Multi-object tracking with representations of the symmetric group[END_REF] for a different purpose.

We first recall the following result, proved by means of the Murnaghan-Nakayama rule ( [START_REF] Murnaghan | The Theory of Group Representations[END_REF]), that provides a closed analytic form for the expected Fourier transform of the random distribution f . Proposition 3. For all ξ ∈ R n , we have:

E[Ff (ξ)] = a ξ • Ff A (ξ), (4)
where a ξ = (

r(ξ) i=1 n i (ξ) 2 - r(ξ )
i=1 n i (ξ ) 2 )/(n(n -1)), denoting by r(ξ) the number of rows in the Young diagram representation of any integer partition of n ξ and n i (ξ) the number of cells at row i.

The proposition above deserves some comments. Notice first that the map ξ ∈ R n → a ξ is antisymmetric (i.e. a ξ = -a ξ for any ξ in R n ) and one can show that a ξ is a decreasing function for the natural partial order on Young diagram [START_REF] Diaconis | Group representations in probability and statistics[END_REF]. As it is shown in [START_REF] Rattan | Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula[END_REF],

|a ξ | = O(n -1/2 ) for diagrams ξ satisfying r(ξ), c(ξ) = O( √ n).
For the two lowest frequencies, (n) and (n, n -1) namely, the proposition shows that a (n) = 1 and a (n-1,1) = (n -3)/(n -1). Roughly speaking, this means that the noise leaves almost untouched (up to a change of sign) the highest and lowest frequencies, while attenuating moderate frequencies. Looking at extreme frequencies hopefully allows to recover/identify A.

Remark 5. (A more general noise model) The model above can be extended in several manners, by considering, for instance, noisy observations of the form f = f A * δ Sm , where S m is picked at random among permutations that can be decomposed as a composition of m ≥ 1 transpositions (and no less). One may then show that

E[Ff (ξ)] = a (m) ξ •Ff A (ξ), for all ξ ∈ R n , where the a (m)
ξ 's satisfy the following property: for all frequencies ξ ∈ R n whose row number and column number are both less than c 1 √ n for some constant c 1 < ∞, |a

(m) ξ | ≤ c 2 • n -m/2
, where c 2 denotes some finite constant. See [START_REF] Rattan | Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula[END_REF] for further details.

Spectral Feature Selection and Sparse Clustering

If one chooses to measure dissimilarity in C[S n ] through the square hilbertian norm, the task of clustering a collection of N distributions f 1 , . . . , f N on the symmetric group S n into L << n! groups can be then formulated as the problem of minimizing over all partitions C = {C 1 , . . . , C L } of the dataset the criterion:

M(C) = L l=1 1≤i, j≤N ||f i -f j || 2 • I{(f i , f j ) ∈ C 2 l } = 1 n! ξ∈Rn d ξ L l=1 1≤i, j≤N : (fi,fj )∈C 2 l ||Ff i (ξ) -Ff j (ξ)|| 2 HS(d ξ ) ,
switching to the Fourier domain by using Parseval relation (see Proposition 1). Given the high dimensionality of rank data (cf Remark 3), such a rigid fashion of measuring dissimilarity may prevent the optimization procedure from identifying the clusters, the main features that are possibly responsible for the differences being buried in the criterion. As shown in the previous section, in certain situations only a few well-chosen spectral features may permit to exhibit similarities or dissimilarities between distributions on S n . Following in the footsteps of [START_REF] Witten | A framework for feature selection in clustering[END_REF], we propose to achieve a sparse clustering of the rank data by considering the optimization problem: λ > 0 being a tuning parameter, minimize

M ω (C) = ξ∈Rn ω ξ d ξ n! L l=1 1≤i, j≤N : (fi,fj )∈C 2 l ||Ff i (ξ) -Ff j (ξ)|| 2 HS(d ξ )
(5)

subject to ω = (ω ξ ) ξ∈Rn ∈ R #Rn + , ||ω|| 2 l2 ≤ 1 and ||ω|| l1 ≤ λ, (6)
(Ff i (ξ) m -Ff j (ξ) m ) 2 .
Though it may lead to better results in practice, interpretation of large values of the weights as significant contributions to the clustering by the corresponding features becomes harder since the choice of a basis of V ξ is arbitrary.

As proposed in [START_REF] Witten | A framework for feature selection in clustering[END_REF], the optimization problem (5) under the constraints (6) is solved iteratively, in two stages, as follows. Starting with weights ω = (1/ √ #R n , . . . , 1/ √ #R n ), until convergence, iterate the two steps:

(Step 1.) fixing the weight vector ω, minimize M ω (C) after the partition C, (Step 2.) fixing the partition C, minimize M ω (C) after ω.

A wide variety of clustering procedures have been proposed in the literature to perform

Step 1 approximately (see [START_REF] Wünsch | Clustering[END_REF] for an overview of off-the-shelf algorithms). As regards Step 2, it has been pointed out in [START_REF] Witten | A framework for feature selection in clustering[END_REF] (see Proposition 1 therein), that a closed analytic form is available for the solution ω, the current data partition C being held fixed: ω ξ = S(Z(C, ξ) + , ∆)/ S(Z(C, ξ) + , ∆) 2 , for all ξ ∈ R n , where x + denotes the positive part of any real number x, Z(C, ξ) = l =l (i,j): (fi,fj )∈C l ×C l ||Ff i (ξ) -Ff j (ξ)|| 2 HS(d ξ ) , and S is the soft thresholding function S(x, ∆) = sign(x)(|x| -∆) + , with ∆ = 0 if the l 1 constraint is fulfilled, and chosen positive so as to enforce ω l1 = s otherwise. This section presents experiments on artificial and real data which demonstrate that sparse clustering on Fourier representation recovers clustering information on rank data. For each of the three studied datasets, a hierarchical clustering is learned using [START_REF] Witten | A framework for feature selection in clustering[END_REF] approach, as implemented in the sparcl R library. The clustering phase starts with each example in a separate cluster and then merges clusters two by two. Parameter s, controlling the l 1 norm of ω, is determined after the approach introduced in [WT10], which is related to the gap statistic used by [START_REF] Tibshirani | Estimating the number of clusters in a data set via the gap statistic[END_REF].

Hierarchical Clustering on Mallows Distributions. The first experiment considers an artificial dataset composed of N = 10 examples, where each example is a probability distribution on S n . Formally, each example f i corresponds to the Mallows distribution of center σ i and spreading parameter γ. Centers σ 1 to σ 5 are of the form σ (0) τ i where σ (0) belongs to S n and τ i is a transposition uniformly drawn in the set of all transpositions. Remaining centers follow a similar form σ (1) τ i . Therefore examples should be clustered in two groups: one with the five first examples and a second group with remaining examples. Figure 3 gives the learned dendograms either from the distribution f i , or from its Fourier transform Ff i . The cluster information is fully recovered with the Fourier representation (except for one example), whereas the larger γ, the further from the target clustering is the dendogram learned from the distribution probabilities. Hence, the Fourier representation is more appropriate than the [0, 1] n! representation to cluster these rank data. Table 1. Number of selected coefficients, with N = 10 Mallows models on S7 and spreading parameter γ.

# of coefficients Representation

Total Selected Selected Selected when γ = 0.1 when γ = 1 when γ = 10 Probability distribution 5,040 8 3 1 Fourier transform 5,040 257 54 6

Regarding the number of coefficients selected to construct these dendograms (cf Table 1), sparcl focuses on less coefficients when launched on the distribution probability. Still, with both representations, less than 260 coefficients are selected which remains small compare to the total number of coefficients (5,040). Unsurprisingly, in the Fourier domain, the selected coefficients depend on γ. When γ is small, the approach selects small frequency coefficients, whereas, when γ is large, the used coefficients are those corresponding to high frequencies.

Fig. 1 .

 1 Fig. 1. Coefficients of the Mallows distribution and of its Fourier transform for several choices of the pair of parameters (σ, γ).

Fig. 2 .

 2 Fig. 2. Monte-Carlo estimate of K (F ) as a function of K for a r.v. drawn at random in a set of L Mallows distributions with concentration parameter γ.

=

  ξ∈Rn |ω ξ |. The coefficient ω ξ must be viewed as the weight of the spectral feature indexed by ξ. Observe incidentally that (1/ √ #R n ) • M(C) corresponds to the situation where ω ξ = 1/ √ #R n for all ξ ∈ R n . Following the lasso paradigm, the l 1 -penalty guarantees the sparsity of the solution ω for small values of the threshold λ, while the l 2 penalty prevents the weight vector to concentrate on a single frequency, the one that most exhibits clustering.Remark 6. (Further feature selection) Recall that the Fourier coefficients are matrices of variable sizes. Hence, denoting (abusively) by {Ff (ξ) m : 1 ≤ m ≤ d ξ } the coefficients of the projection of any f ∈ C[S n ] onto the irreducible subspace V ξ chosen in a given orthonormal basis of V ξ , one may consider a refined sparse clustering, namely by considering the objective j≤N : (fi,fj )∈C 2 l

Fig. 3 .

 3 Fig. 3. Dendograms learned on N = 10 Mallows models on S7 with spreading parameter γ. Examples which should be in the same cluster are plotted with same color.

< 1 <

< 6 < ...

Acknowledgements. Authors greatly thank DIGIT ÉO (B ÉMOL project), which partially supported this work.

2 < 1 < 3 < 4 < ... 2 < 1 < 3 < 5 < ... 2 < 1 < 3 < 7 < ... 2 < 1 < 3 < 8 < ... 1 < 3 < 2 < 6 < ... 1 < 3 < 2 < 4 < ... 1 < 3 < 2 < 5 < ... 1 < 3 < 2 < 7 < ... 1 < 3 < 2 < 8 < ... 3 < 2 < 1 < 6 < ... 3 < 2 < 1 < 4 < ... 3 < 2 < 1 < 5 < ... 3 < 2 < 1 < 7 < ... 3 < 2 < 1 < 8 < ... 6 < 8 < 7 < 3 < ... 7 < 8 < 6 < 3 < ... 8 < 6 < 7 < 3 < ... 8 < 7 < 6 < 3 < ... 8 < 7 < 6 < 5 < ... 8 < 7 < 6 < 4 < ... 8 < 6 < 7 < 5 < ... 8 < 6 < 7 < 4 < ... 7 < 8 < 6 < 5 < ... 7 < 8 < 6 < 4 < ... 6 < 8 < 7 < 5 < ... 6 < 8 < 7 < 4 < ... 7 < 6 < 8 < 5 < ... 7 < 6 < 8 < 4 < ... 6 < 7 < 8 < 4 < ... 6 < 7 < 8 < 5 < ... 6 < 7 < 8 < 3 < ... 7 < 6 < 8 < 3 < ... 6 < 8 < 7 < 1 < ... 8 < 6 < 7 < 1 < ... 6 < 8 < 7 < 2 < ... 8 < 6 < 7 < 2 < ... 6 < 7 < 8 < 1 < ... 7 < 6 < 8 < 2 < ... 7 < 8 < 6 < 2 < ... 8 < 7 < 6 < 1 < ... 6 < 7 < 8 < 2 < ... 7 < 6 < 8 < 1 < ... 7 < 8 < 6 < 1 < ... 8 < 7 < 6 < 2 < ... 1 < 2 < 3 < 6 < ... Hierarchical Clustering on Top-k Lists. This second experiment is conducted on artificial data, which consider rankings on eight products. Each example i of the data corresponds to a top-4 list

(1, . . . , 4)}, where (i 1 , i 2 , i 3 ) is either a permutation on products {1, 2, 3} or a permutation on products {6, 7, 8}, and i 4 is one of remaining products. All in all, this dataset contains 60 examples, which should be clustered in two groups or twelve groups. The 60 functions f i have disjoint supports. Therefore, the examples cannot be clustered based on their "temporal" representation. On the contrary, the Fourier representation leads to a dendogram which groups together examples for which the top-3 products are from the same three products (cf Figure 4). Furthermore, this dendogram is obtained from only seven small-frequency coefficients, which is extremely sparse compare to the total 40, 320 coefficients.

Hierarchical Clustering on an E-commerce Dataset. The proposed approach is also used to cluster the real dataset introduced by [START_REF] Richard | Link discovery using graph feature tracking[END_REF]. This data come from an E-commerce website. The only available information is the history of purchases for each user, and the ultimate goal is to predict future purchases. A first step to this goal is to group users with similar behavior, that means to group users based on the top-k rankings associated to their past purchases. We consider the 149 users which have purchased at least 5 products among the 8 most purchased products. The sparse hierarchical clustering approach receives as input the 6,996 smallest frequency coefficients and selects 5 of them. The corresponding dendogram (cf Figure 5) clearly shows 4 clusters among the users. On 7 independent splits of the dataset in two parts of equal sizes, the criterion optimized by sparcl varies from 46.7 to 51.3 with a mean value of 49.1 and a standard deviation of 1.4. The stability of the criterion increases the confidence in this clustering of examples.

Conclusion

In this paper, a novel approach to rank data clustering is introduced. Modeling rank data as probability distributions on S n , our approach relies on the ability of the Fourier transform on S n to provide sparse representations in a broad variety of situations. Several preliminary empirical and theoretical results are presented to support this claim. The approach to sparse clustering proposed in [START_REF] Witten | A framework for feature selection in clustering[END_REF] is adapted to this setup: a lasso-type penalty is used so as to select adaptively a subset of spectral features in order to define the clustering. Numerical examples are provided, illustrating the advantages of this new technique. A better understanding of the class of distributions on S n that can be efficiently described in the Fourier domain and of the set of operators that are almost diagonal in the Fourier basis would permit to delineate the compass of this approach.