Julien Ah-Pine
email: julien.ah-pine@xrce.xerox.com

Cluster analysis based on the central tendency deviation principle

Keywords: Cluster analysis, clustering functions, clustering algorithm, categorical and real continuous data, experimental protocol

Our main goal is to introduce three clustering functions based on the central tendency deviation principle. According to this approach, we consider to cluster two objects together providing that their similarity is above a threshold. However, how to set this threshold ? This paper gives some insights regarding this issue by extending some clustering functions designed for categorical data to the more general case of real continuous data. In order to approximately solve the corresponding clustering problems, we also propose a clustering algorithm. The latter has a linear complexity in the number of objects and doesn't require a pre-defined number of clusters. Then, our secondary purpose is to introduce a new experimental protocol for comparing different clustering techniques. Our approach uses four evaluation criteria and an aggregation rule for combining the latter. Finally, using fifteen data-sets and this experimental protocol, we show the benefits of the introduced cluster analysis methods.

Introduction

Clustering is one of the main tasks in data analysis and in data mining fields and has many applications in real-world problems. Given a set of N objects O = {o 1 , . . . , o N }, described by a set of P features D = {D 1 , . . . , D P }, the clustering problem consists in finding homogeneous groups of these objects. However, clustering is a NP-hard problem and one has to use heuristics for processing large data-sets. Reviews of such heuristics can be found in [START_REF] Jain | Data clustering: a review[END_REF][START_REF] Grabmeier | Techniques of cluster algorithms in data mining[END_REF][START_REF] Xu | Survey of clustering algorithms[END_REF]. With respect to the usual taxonomy of clustering methods [START_REF] Jain | Data clustering: a review[END_REF], the present paper aims at contributing to the family of hard partitional techniques. As it was underlined in [START_REF] Xu | Survey of clustering algorithms[END_REF][START_REF] Zhao | Criterion functions for document clustering: Experiments and analysis[END_REF], one important factor in that case, is the partitioning function that a clustering algorithm attempts to optimize. Hence, the contributions of this paper are the following ones. First, we introduce three clustering functions that have the following general formulation:

F (S, µ, X) = N i,i =1 (S ii -µ ii )X ii . (1)
where: S is a similarity matrix; µ is a matrix of central tendency measures of similarities given for each pair of objects; and X is a relational matrix which general term, X ii , equals 1 if o i and o i are in the same cluster; 0 otherwise. X is similar to an adjacency matrix, yet, as it must be a partition, it has to satisfy the following linear constraints [START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF][START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF], ∀i, i , i = 1, . . . , N :

X ii = 1 .
(reflexivity) X ii -X i i = 0 .

(symmetry)

X ii + X i i -X ii ≤ 1 . (transitivity) (2)
Following the relational analysis method (RA in the following) in cluster analysis [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF][START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF], the related clustering problems that we want to solve can be formally stated as: max X F (S, µ, X) with respect to the linear constraints 1 given in [START_REF] Grabmeier | Techniques of cluster algorithms in data mining[END_REF].

Regarding [START_REF] Jain | Data clustering: a review[END_REF], our main point of interest concerns the variable µ. By maximizing F (S, µ, X), we highly consider to group o i and o i together if their similarity S ii is greater than µ ii . However, how to set µ ii ? On which basis should we compute µ ii ? Several existing clustering methods are based on the same kind of objective function [START_REF] Hartigan | Clustering Algorithms[END_REF][START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF]. However, most of them consider µ ii as a constant parameter which can be set by the user. On the contrary, in this paper, we define new clustering functions for which the quantities µ ii are data-dependent and are interpreted as central tendency measures of pairwise similarities.

Then, in order to rapidly find an approximate solution X, we also introduce a clustering algorithm that amounts to a local search based technique. This approach is quite similar to the leader algorithm proposed in [START_REF] Hartigan | Clustering Algorithms[END_REF] and is also studied in the RA context in [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF][START_REF] Grabmeier | Techniques of cluster algorithms in data mining[END_REF]. These techniques interesting as they don't require to fix the number of clusters.

The secondary purpose of this work, is to suggest a new experimental protocol for assessing different cluster analysis methods. Indeed, in most papers covering clustering techniques, only one or two assessment measures are used. In this work, we propose to take into account four different evaluation criteria and a score aggregation method in our experimental protocol. Hence, we propose to use this approach for benchmarking the introduced clustering methods.

The rest of this paper is organized as follows. In section 2, we introduce the central tendency deviation principle and define three new clustering functions. Next, in section 3, we detail the associated clustering algorithm. Then, we present our experimental protocol and the obtained results, in section 4. Finally, we give some conclusions and future work in section 5.

Maximal association criteria and the central tendency deviation principle

In this section, we introduce three clustering functions for partitioning continuous numerical data. Firstly, we recall the maximal association approach in the RA framework [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF]. In this context, association measures are used in their relational representations in order to design objective functions for clustering categorical data. Secondly, we extend these clustering functions to the more general case of continuous data. In that perspective, we underline the central tendency deviation principle.

Contingency and relational representations of association measures

Contingency table analysis aims at measuring the association between categorical variables. Let V k and V l be two categorical variables with category sets {D k s ; s = 1, . . . , p k } and {D l t ; t = 1, . . . , p l } (p k being the number of category of V k ). Their associated contingency table denoted n of size (p k × p l ), is defined as follows: n st = Number of objects in both categories D k s and D l t . Then, it exists many association criteria based on the contingency table [START_REF] Goodman | Measures of association for cross classification[END_REF][START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF]. We are particularly interested in the three following ones:

• The Belson measure (denoted B) introduced in [START_REF] Belson | Matching and prediction on the principle of biological classification[END_REF] which is related to the well-known χ2 measure. The former is actually a non-weighted version of the latter.

• The squared independence deviation measure (denoted E) which was introduced in [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF] and studied in [START_REF] Abdallah | Classification d'un ensemble de variables qualitatives[END_REF] for measuring similarities between categorical variables.

• The Jordan measure (denoted J), which is a coefficient based upon [START_REF] Jordan | Les coefficients d'intensité relative de korosy[END_REF] but which was formally introduced in [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF].

We recall below, the contingency representation of these criteria 2 .

B(V k , V l ) = p k s=1 p l t=1 n st - n s. n .t N 2 . E(V k , V l ) = s,t n 2 st -s n 2 s. t n 2 .t N 2 . J(V k , V l ) = 1 N s,t n st n st - n s. n .t N .
where n s. = p l t=1 n st . In the context of the RA approach in contingency table analysis [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie I[END_REF][START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF][START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF], we can equivalently express the previous criteria using relational matrices. For V k , its relational matrix is denoted C k and its general term C k ii equals 1 if o i and o i are in the same category; 0 otherwise. Then, one can observe the following identities between contingency and relational representations [START_REF] Kendall | Rank correlation methods[END_REF][START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF]:

s,t n 2 st = i,i C k ii C l ii ; s n 2 s. = C k .. ; s,t n st n s. n .t = i,i C k i. + C k .i 2 C l ii . ( 3
)
where i C k ii = C k .i and i,i C k ii = C k ..
. Consequently, we obtain the following relational representations of the studied coefficients [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF]:

B(C k , C l ) = N i=1 N i =1 C k ii - C k i. + C k .i N + C k .. N 2 C l ii . (4)
E(C k , C l ) = i,i C k ii - C k .. N 2 C l ii . (5)
J(C k , C l ) = 1 N i,i C k ii - C k i. N C l ii . (6)
The relational formulation of association measures is of interest for analyzing the differences between such coefficients [START_REF] Ah-Pine | Statistical, geometrical and logical independences between categorical variables[END_REF]. In our context, this formalism allows to define clustering functions for categorical data. We recall and extend this aspect in the following subsection.

Maximal association criteria and their extensions

Let suppose M categorical variables V k ; k = 1, . . . , M and let ∆ represent one of the three studied association measures (4), ( 5) or [START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF]. Then, the maximal association problem introduced in [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF], can be formally stated as follows:

max X 1 M M k=1 ∆(C k , X) .
where X is a relational matrix which satisfies [START_REF] Grabmeier | Techniques of cluster algorithms in data mining[END_REF].

In other words, we want to find the consensus partition X that maximizes the mean average association with all categorical variables C k ; k = 1, . . . , M . This amounts to a clustering model for categorical data or consensus clustering [START_REF] Lebbah | Relational analysis for consensus clustering from multiple partitions[END_REF]. Thanks to the relational representation, we have the following property [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF]:

1 M M k=1 ∆(C k , X) = 1 M ∆ M k=1 C k , X = 1 M ∆ (C, X) . ( 7
)
where C = M k=1 C k and C ii is the number of agreements between o i and o i (the number of variables for which both objects are in the same category).

Therefore, it appears that the mean average of the association between X and the relational matrices C k ; k = 1, . . . , M , is equivalent to the association between the former and an aggregated relational matrix3 , C.

The summation property [START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF] is the basis of the extension of the studied objective functions, that we are going to introduce. Indeed, let represent categorical data as an indicator matrix T of size (N × P ) where P = M k=1 p k . In that representation, we consider all categories of all nominal variables. Accordingly, we denote D = {D 1 , . . . , D P } the set of all categories. Then, the general term of T , T ij , equals 1 if o i is in category D j ; 0 otherwise. In that representation, any object o i is a binary vector of size (P × 1) and the following observation becomes straightforward:

C ii = P j=1 T ij T i j = o i , o i ,
where ., . is the euclidean dot product. Given this geometrical view, we can consider the extension of the clustering functions recalled previously to the more general case of continuous numerical features. Indeed, we simply interpret C ii as a dot product between vectors o i and o i and we symbolically replace any occurrence of C with a generic notation S. Henceforth, we assume that S is a Gram matrix (also called similarity matrix) and the vectors o i ; i = 1, . . . , N , are represented in a continuous feature space T of dimension P .

The central tendency deviation principle

According to the previous subsection, the objective functions that we want to study are the following ones 4 .

B (S, X) = i,i S ii - S i. N + S i . N - S .. N 2 X ii . (8)
E (S, X) = i,i S ii - S .. N 2 X ii . (9)
J (S, X) = i,i S ii - 1 2
S i. N + S i . N X ii . (10)
where S i. = S .i = i S ii (since S is symmetric) and S .. = i,i S ii . Given the previous equations, we can draw out the central tendency deviation principle. Indeed, one can observe that all objective functions are based on a comparison between the similarity of two objects and a central tendency measure.

In the case of B defined in [START_REF] Wakabayashi | The complexity of computing medians of relations[END_REF], the transformation from S ii to

S ii -Si. N -S i . N + S.. N 2
is a geometrical one and is known as the Torgerson transformation [START_REF] Torgerson | Multidimensional scaling : I. theory and method[END_REF]. Let g = 1 N N i=1 o i be the mean vector. Then, we have:

S ii -Si. N -S i . N + S.. N 2 = o i -g, o i -g .
For the Belson function, the objects o i and o i could be clustered together providing that their dot product, centered with respect to the mean vector g, is positive.

Regarding E given in [START_REF] Hartigan | Clustering Algorithms[END_REF], the central tendency is the mean average over all pairwise similarities, S.. N 2 . This approach is also a global one as it considers all (pairs of) objects. In that case, o i and o i are more likely to be in the same cluster if their own similarity is above the mean average of all similarities.

Unlike the previous cases, the function J introduced in [START_REF] Goodman | Measures of association for cross classification[END_REF], is based on a local central tendency approach. For the Jordan function, o i and o i have more chances to be grouped together if their similarity is greater than the arithmetic mean of the mean average of their similarity distributions Si.

N and S i .

N .

However, one special case to consider is when the data are already centered. Indeed, if S ii = o i -g, o i -g , all three clustering functions become equivalent as Si. N = S i . N = S.. N = 0. Despite this point, we propose a version of the clustering functions that combines two kinds of central tendency approaches.

Following the previous observation and the Belson function, we first center the data. This leads to similarities S ii that are either positive or negative. Next, we focus on positive similarities only. Indeed, the latter are related to pairs of vectors whose cosine index is positive which indicates that they are rather similar. Thus, let S + be the set of pairs of objects having positive similarities:

S + = {(o i , o i ) ∈ O 2 : S ii ≥ 0}.
Then, we compute the central tendency measures related to the clustering criteria, on the basis of pairs belonging to S + . More concretely, below are the clustering functions that we propose to define:

B + (S, X) = i,i S ii - S + i. N + i. + S + i . N + i . - S + .. N + .. X ii . (11)
E + (S, X) = i,i S ii - S + .. N + .. X ii . ( 12
) J + (S, X) = i,i S ii - 1 2
S + i. N + i. + S + i . N + i . X ii . (13)
with, ∀i = 1, . . . , N :

S + i. = i :(o i ,o i )∈S + S ii ; S + .. = i,i :(o i ,o i )∈S + S ii ; N + i. = #{o i ∈ O : (o i , o i ) ∈ S + } and N +
.. = #S + (# being the cardinal). Intuitively, this two-step approach allows to obtain more compact clusters since pairs of objects that are finally clustered together must have very high similarities compared to central tendency measures based upon the most relevant similarities which are the positive ones and which actually correspond to the nearest neighbors of objects.

To sum up, we give in Table 1, the parameters µ of the respective clustering functions. This table uses the notations provided in equation [START_REF] Jain | Data clustering: a review[END_REF]. Henceforth, we are interested in the following clustering problems: max X ∆ + (S, X) with respect to the constraints in [START_REF] Grabmeier | Techniques of cluster algorithms in data mining[END_REF], where ∆ + is one of the three functions in Table 1.

Table 1. Clustering functions and their central tendency measures Clus. func.

Central tendency measures

B + (S, X) = F (S, µ B + , X) µ B + ii = S + i. N + i. + S + i . N + i .
-

S + .. N + .. E + (S, X) = F (S, µ E + , X) µ E + ii = S + .. N + .. J + (S, X) = F (S, µ J + , X) µ J + ii = 1 2 " S + i. N + i. + S + i .
N + i .

«

A Clustering algorithm based on transfer operations

The clustering problems that we have formally presented as integer linear programs, can be optimally solved but for very small data-sets. In this paper, we target large data-sets and our purpose is to introduce a clustering algorithm that allows to rapidly find an approximate solution X to these clustering problems.

Regarding the notations, let U = {u 1 , . . . , u q } be the partition solution represented by the relational matrix X (q being the number of clusters of U ). Hence, u l ; l = 1, . . . , q, represents the set of objects that are within this cluster. As we have mentioned in section 1, the core of this heuristic is not new. Actually it can be seen as a prototype-based leader algorithm but employing similarities instead of euclidean distances. The basic ideas of this algorithm were already suggested in [START_REF] Hartigan | Clustering Algorithms[END_REF][START_REF] Marcotorchino | Heuristic approach of the similarity aggregation problem[END_REF][START_REF] Grabmeier | Techniques of cluster algorithms in data mining[END_REF] for example. After introducing the mechanism of such an algorithm, we recall its particular weakness and propose a simple solution to overcome it.

The basic algorithm and its scalable version

Given U , a current partition of the objects, we want to find out if the transfer of an object o i to any other clusters of U distinct from its current cluster, can increase the clustering function value. To this end, we introduce the following contribution measures. In the equations below, u i symbolically represents the current cluster of o i ; u l an existing cluster but different from u i and {o i } the singleton constituted of o i .

cont ui (o i ) = 2 i :o i ∈ui (S ii -µ ii ) -(S ii -µ ii ) . ( 14
)
cont u l (o i ) = 2 i :o i ∈u l (S ii -µ ii ) + (S ii -µ ii ) ∀u l = u i . ( 15
)
cont {o i } (o i ) = (S ii -µ ii ) . ( 16
)
With respect to the objective function [START_REF] Jain | Data clustering: a review[END_REF], and all other things being equal, one can observe that the quantities 5 measures given in ( 14), ( 15) and ( 16), allow to 5 Notice that S and µ are symmetric in our context. In the case of contu i (o i ) for example, the non-symmetric formulation would be:

P i :o i ∈u i (S ii -µ ii ) + P i :o i ∈u i (S i i -µ i i ) -(Sii -µii).
decide whether object o i should: stay in its current cluster; be transferred into another cluster; or generate a new cluster. Regarding [START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF], let cont u l * (o i ) be the maximum contribution of o i to an existing cluster (distinct from its current cluster). Then, in order to maximize the objective function [START_REF] Jain | Data clustering: a review[END_REF], one can observe that the algorithm should:

• create a new cluster if cont {o i } (o i ) is greater than cont ui (o i ) and cont u l * (o i ), • transfer o i to u l * if cont u l * (o i ) is greater than cont ui (o i ) and cont {o i } (o i ),
• do nothing in all remaining cases. Given this basic operation, the algorithm processes all objects and continue until a stopping criterion is full-filled. Typically, we fix a maximal number of iterations over all objects (denoted nbitr in the following).

Since we improve the clustering function value at each operation, this algorithm converges to a local optimum.

In order to have an efficient implementation of the algorithm, we need to compute the contribution quantities ( 14) and ( 15) efficiently. In the following, we start by discussing the computation of the central tendencies µ ii . In a second time, we present an efficient way for computing the contribution quantities ( 14) and ( 15) using prototypes.

According to Table 1, we need to compute the following statistics to determine µ ii : the (N ×1) vectors of general terms S + i. and N + i. and/or the scalars S + .. and N + .. . All these statistics will be referred as the "components of µ". They are computed before applying the clustering heuristic and are considered as inputs of the algorithm. The computation cost of these statistics is O(N 2 × P ). However, we only need one iteration to calculate them. Moreover, we can compute these different vectors incrementally.

Next, if we consider the formulation of the contributions given in ( 14) and ( 15) in terms of S, the computation cost of the algorithm is of order O(N 2 × P × nbitr). When N is high, this implementation is costly. Hopefully, in our context, we can reduce the complexity cost of these quantities. Let us recall that, we are given the feature matrix T of size (N × P ) as input. Furthermore, let us assume that the space dimension is much lower6 than the number of objects, P << N . Then, since S = T • T , we can use the linearity properties of the dot products in order to quickly compute the contributions ( 14) and ( 15) by using prototypes. First, one can observe that:

i :o i ∈u l S ii = i :o i ∈u l o i , o i = o i , h l where h l = i :o i ∈u l o i . ( 17
)
h l is the non-weighted mean vector of size (P × 1) representing the cluster u l . Hence, using h l ; l = 1, . . . , q, as prototypes allows to reduce the computation cost of i :o i ∈u l S ii from O(#u l × P ) to O(P ). Second, the computation of the aggregated central tendencies measures, i :o i ∈u l µ ii , can also be reduced by

P i :o i ∈u l µ B + ii = #u l S + i. N + i + ν l -#u l S + .. N 2 E + (S, X) P i :o i ∈u l µ E + ii = #u l S + .. N 2 J + (S, X) P i :o i ∈u l µ J + ii = 1 2 " #u l S + i. N + i + ν l «
keeping up to date the vector ν of size (q × 1) of general term:

ν l = i :o i ∈u l S + i . N + i .
.

Using ν, we can reduce the computation cost of i :o i ∈u l

S + i . N + i .
, that is involved in the calculation of i :o i ∈u l µ ii , from O(#u l ) to O(1). Accordingly, we give in Table 2, the aggregated central tendency measures of the contribution of o i to a cluster u l , for the different clustering functions.

To sum up, if we pre-compute the components of µ and use the prototypes h l ; l = 1, . . . , q, and ν then we can reduce the computation cost of the clustering algorithm to O(N × q × P × nbitr). In the meantime, the memory cost is kept to O(N × P ). These results are quite satisfying as they make the computation cost and memory cost of such an algorithm comparable to the popular k-means method with respect to the number of objects to be clustered. We finally give in Algorithm 1, the pseudo-code of the proposed clustering algorithm.

Setting the scanning order of objects

One important issue related to Algorithm 1 is its dependency regarding the scanning order of the objects to cluster. To tackle this problem we propose to use one of the component of the central tendency µ that we have introduced beforehand. More precisely, we propose to scan the objects according to the increasing order of (N + 1. , . . . , N + N. ). For object o i , N + i. represents the number of objects with which it has a positive similarity (assuming centered data). Accordingly, we first process the less positively connected objects. This approach can be seen as a strategy for finding small and stable clusters rapidly. To some extent, it also can be viewed as a way for eliminating noise. Indeed, if we choose the decreasing order, the most positively connected objects will be processed first and they will bring in their clusters noisy objects.

Experiments

In this section, we introduce an experimental protocol that aims to compare different clustering techniques. This protocol takes into account four different We take the k-means algorithm as the baseline since this technique is pretty closed in spirit to our proposal (transfer operations) and since it was shown that it provides relevant results compared to other clustering techniques [START_REF] Jain | Landscape of clustering algorithms[END_REF]. In our experiments, we set k as the number of true classes for the k-means algorithm while keeping free this parameter for Algorithm 1. Moreover, for each data-set, we launched 5 different runs with random seeds for the k-means method and took the mean average of the evaluation criteria measures.

Experiments results and discussions

We report in Table 4, the experiments results (in %) we obtained for each triple (evaluation measure × data-set × clustering algorithms). For each pair (evaluation measure × data-sets) we put in bold the score of the best method. We also give in the bottom lines of Table 4, the number of clusters found by the different methods. According to Table 4, one general comment we can make is that the evaluation measures do not necessarily agree about their rankings. Given a data-set, it happens that one clustering method is ranked first for one evaluation measure and last for another one. Besides, some assessment measures are quite dependent on the number of clusters found. This is typically the case for the entropy measure (better for larger number of clusters) and the Jaccard index (better for smaller number of clusters). These observations justify our approach that supports the use of several evaluation criteria in order to have many "opinions". Accordingly, if we apply the experimental protocol we have described in subsection 4.1, we find the following global ranking: J + E + B + ∼ k-means. As we can see, cluster analysis based on the central tendency deviation principle can outperform the k-means technique. Besides, the Jordan criterion J + seems to be the most consensual clustering approach. Interestingly, it is not the one that was most often ranked first. This indicates that the J + objective function is quite robust compared to the other approaches and with respect to the wide variety of data-sets we tested. However, it is worth noticing that regarding higher dimensional data-sets such as synt-cont or mfeat-fou, the B + function seems to perform better. Regarding the number of clusters found, E + gives, on average, the highest number of clusters; next comes B + (except for the iris and abalone data-sets); and then J + . The number of clusters found using our proposals are distinct from the original number of classes. For most of the data-sets, the former is greater than the latter. This suggests that classes can contain several homogeneous subclasses that is interesting to find out in a knowledge discovery context.

Conclusion and future work

We have introduced three clustering functions for numerical data based on the central tendency deviation concept. These partitioning criteria can be seen as extensions of maximal association measures that were defined for clustering categorical data. We have presented an algorithm that approximately solves the clustering problems we have proposed. Moreover, we have defined a robust experimental protocol that involves four different assessment measures and an aggregation rule. We tested our clustering functions using fifteen data-sets and have showed that our proposals can perform better than the k-means algorithm.

In our future work, we intend to further analyze the geometrical properties of the clustering functions we have introduced in order to potentially apply them in more specific contexts such as high dimensional data or clusters with different shapes for example.

Table 2 .

 2 Clustering functions and aggregated central tendency measures of the contribution of object o i to a cluster

	Clus. func. Aggregated central tendency measures
	B + (S, X)

Table 3 .

 3 Data-sets description each object's vector in order to have a unit norm. The resulting feature matrix T is the input of all clustering techniques. Concerning the clustering functions we have introduced in this paper, this amounts to take the Gram matrix S as the cosine similarity matrix between centered vectors. Besides, when applying Algorithm 1, we set nbitr = 10.

	Name	iris sonar glass ecoli liv-ionos wdbc synt-veh-yeast mfeat img-abalo pag-land
						dis			cont silh		-fou seg		blo sat
	Nb. obj. 150 208 214 336 345 351 569 600 846 1484 2000 2310 4177 5473 6435
	Nb. feat. 4	60	10	7	6	34	32	60	18	8	76	18	8	10	36
	Nb. clas. 3	2	6	8	2	2	2	6	4	8	10	7	28	5	6

Table 4 .

 4 Results according to the four evaluation criteria and number of clusters found. 28.1 52.8 13.2 23.9 34.5 43.0 17.1 16.2 26.1 31.2 11.5 24.9 44.1 J + 42.0 10.8 27.8 48.6 11.4 24.7 30.7 44.5 17.0 16.2 30.1 38.4 11.6 23.5 47.3 k-m 57.1 36.4 27.7 37.6 44.0 42.9 73.6 51.8 18.3 19.4 27.6 39.2 5.5 39.9 44.5 AR B + 36.4 4.1 22.3 37.2 1.0 18.0 26.2 67.7 8.0 14.3 42.6 44.9 7.0 3.6 57.3 E + 57.8 3.0 26.2 59.6 0.1 18.5 32.2 51.0 8.8 14.2 35.7 37.5 5.9 7.4 51.8 J + 45.4 3.9 26.7 55.4 0.8 21.1 28.5 52.8 8.9 14.3 40.7 47.8 6.1 5.6 55.5 k-m 58.7 1.9 22.1 43.6 -0.6 17.0 66.8 61.2 7.9 18.0 36.8 47.6 4.9 10.7 53.0 JV B + 33.2 6.3 24.1 41.1 1.8 26.5 37.5 67.5 8.2 18.1 42.3 44.3 15.7 26.2 57.0 E + 55.0 4.5 31.8 64.5 0.6 27.3 42.0 46.3 8.3 20.3 34.9 36.2 18.0 40.0 49.6 J + 46.5 6.3 31.0 60.3 1.5 31.8 39.5 50.4 8.5 19.6 39.9 47.0 17.3 32.2 54.2 k-m 58.7 1.9 27.2 46.6 0.8 17.1 67.0 61.6 7.9 21.5 36.9 48.2 6.2 37.6 53.1 Nb. clus.

	Ent	iris sonar glass ecoli liv-ionos wdbc synt-veh-yeast mfeat img-abalo pag-land
						dis			cont silh		-fou seg		blo sat
	B +	35.7 80.5 50.4 26.7 94.1 45.1 17.4 17.0 80.0 53.1 44.6 44.1 61.8 21.5 38.6
	E +	30.6 75.5 43.4 23.0 94.7 33.6 18.1 25.8 78.8 52.1 42.5 49.8 64.5 16.0 37.4
	J +	34.1 72.3 45.1 23.6 94.6 36.6 18.8 27.3 82.8 52.4 43.8 41.4 66.0 17.9 36.5
	k-m	36.6 97.9 55.4 24.3 98.0 82.1 43.8 26.8 89.4 50.3 51.0 43.2 59.3 20.1 36.8
	Jac
	B +	36.7 12.4 22.7 32.1 11.8 23.8 28.5 57.4 14.4 16.2 31.6 36.0 10.7 23.2 48.7
	E + 54.3 12.2 B + 24 11	7	9	10	13	8	7	9	12	16	11 146	9	10
	E +	7	22	15	15	13	48	21	66	21	19	42	16	69	20	49
	J +	6	17	9	12	11	17	15	14	13	16	27	11	19	12	16
	k-m	3	2	6	8	2	2	2	6	4	8	10	7	28	5	6

Note that we can use integer linear programming to solve this clustering problem[START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF][START_REF] Marcotorchino | Cross association measures and optimal clustering[END_REF] but only for very small data-sets. Indeed, as it was already mentioned, this optimization problem is a NP-hard one[START_REF] Wakabayashi | The complexity of computing medians of relations[END_REF].

Notice that all of them are null when the variables V k and V l are statistically independent.

Also called the collective Condorcet matrix in the RA approach[START_REF] Michaud | Modèles d'optimisation en analyse des données relationnelles[END_REF].

For the Jordan function, we drop the factor 1 N .

For high-dimensional space we can assume a pre-processing step that reduces the dimension of the feature space.

Following the comments given in subsection 2.3.

Algorithm 1 Transfer based heuristic

Require: nbitr = number of iterations; T = the feature matrix; µ = the central tendency components. Take the first object o i as the first element of the first cluster u1: q ← 1 where q is the current number of cluster Update h 1 and ν1 for itr = 1 to nbitr do for i = 1 to N do if o i hasn't been assigned a cluster yet then Set contu i (o i ) ← -∞ and compute cont {o i } (o i ) using ( 16) else Compute contu i (o i ) using ( 14), ( 17), Table 2 and compute cont {o i } (o i ) using ( 16) end if for u l in the set of already constituted clusters do Compute contu l (o i ) using ( 15), ( 17), Table 2 end for Find u l * the cluster which has the highest contribution with object

Create a new cluster u l whose first element is o i : q ← q + 1 Update h l and ν l and update h i and νi

Transfer object o i to cluster u l * : Update h l * and ν l * and update h i and νi if the cluster ui where was taken o i is empty then q ← q -1 end if end if end if end for end for evaluation criteria. The latter can be seen as four different "point of views" when ranking the clustering techniques. Therefore, we use an aggregation rule for combining the different rankings into one global ranking. In our experiments, we take the k-means algorithm as the baseline. We compare the results provided by the latter to the ones given by the clustering heuristic defined in Algorithm 1 and associated to the clustering functions mentioned in Table 1. We used fifteen data-sets of the UCI Machine Learning repository [START_REF] Asuncion | UCI machine learning repository[END_REF]. The results that we obtained show improvements over the k-means procedure.

Experimental protocol

We propose to use four evaluation criteria defined in the literature for assessing the clustering algorithms' results. Usually, only one or two assessment coefficients are used. In this paper, we argue that the more evaluation criteria we use in an experimental protocol, the more robust the conclusions we can draw out from the latter.

We assume that for a given data-set, we have at our disposal, the true label of all objects. Accordingly, we denote by V = {v 1 , . . . , v k } the true partition of the data-set. In that case, v m ; m = 1, . . . , k, is called a class.

Then, the evaluation criteria we propose to use are the following ones: the entropy measure [START_REF] Zhao | Criterion functions for document clustering: Experiments and analysis[END_REF], the Jaccard index [START_REF] Jaccard | The distribution of the flora in the alpine zone[END_REF][START_REF] Youness | Some measures of agreement between close partitions[END_REF], the adjusted Rand Index [START_REF] Hubert | Comparing partitions[END_REF] and the Janson-Vegelius coefficient [START_REF] Janson | The J-index as a measure of association for nominal scale response agreement[END_REF][START_REF] Marcotorchino | Utilisation des comparaisons par paires en statistique des contingences partie II[END_REF][START_REF] Youness | Some measures of agreement between close partitions[END_REF]. They are formally defined below where X and C are the respective relational matrices (see subsection 2.1) of U and V :

Each of these four coefficients allows to rank the different clustering functions. Except for the entropy measure, the higher the score, the better the clustering output U . Since we want to use several data-sets in the experiments, we have as many rankings as pairs in (evaluation criteria × data-sets). Consequently, we need to combine all these rankings. To this end, we propose to use Borda's rank aggregation rule. In that case, let assume that we need to aggregate r rankings of c clustering techniques' result. Then, for each ranking, Borda's rule consists in scoring the best result with c -1, the second one with c -2 and so on until the last one which has a null score. Then, the final ranking of the clustering techniques is obtained by summing the r different scores distributions. The best method is the one which has the highest aggregated score.

As for each clustering method, we have to aggregate rankings with respect to two dimensions (evaluation criteria × data-sets), we apply the previous aggregation method in a two-step framework. Given a data-set, we start by aggregating the ranks provided by the different evaluation criteria. Thus, for each data-set, we obtain a first aggregated ranking of the clustering techniques. Then, we aggregate these consolidated rankings given by each data-set which are now seen as criteria. This second aggregated score distribution provides us with the global ranking that allows to compare the clustering techniques from a global viewpoint.

Experiments settings

We report in Table 3, the description of the fifteen data-sets of the UCI Machine Learning repository [START_REF] Asuncion | UCI machine learning repository[END_REF], that we included in our experiments. These data-sets concern several domains with distinct numbers of objects, features and classes. Our aim is to have a global evaluation of the introduced cluster analysis models rather than a specific evaluation restricted to a certain kind of data-sets. For each data-set we centered 7 and standardized the feature matrix. We also normalized


Julien Ah-Pine

Marco Bressan

Stephane Clinchant

Gabriela Csurka

Yves Hoppenot

Jean-Michel Renders

Crossing textual and visual content in different application scenarios

Keywords: First keyword, Second keyword, More

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

Introduction

Information, especially digital information, is no longer monomodal: web pages can have text, images, animations, sound and video; we have audiobooks, photoblogs and videocasts; the valuable content within a photo sharing site can be found in tags and comments as much as in the actual visual content. Nowadays, it is difficult to visit a page within a popular social network without finding a large variety of content modes surrounded by a rich structure of social information such as profiles, interest groups, consumer behaviour or simple conversations. This major shift in the way we access content and what type of content we access is largely due to the connected, easily accessible, global nature of the internet. The democratization of the tools of production and delivery have also strongly contributed to this situation, e.g. low cost camera-phones combined with accessible publishing tools. This scenario poses a strong need for tools that enable interaction with multimodal information.

Multimodal information processing strongly needs trans-media similarity measures that can effectively bridge the gap between the co-existing modes. Such tools will enable applications whose relevance can already be perceived today: accessing an image repository from a textual query, automatic illustration, content creation and document generation, captioning, multimodal summarization, hybrid categorization and indexing, content personalization, etc. In this article, we explore such measures and propose two new approaches for hybrid text-image information processing, an important particular case of the more general multimodal scenario.

Within multimodal information processing an important family of approaches is constituted by the so-called "trans-media" pseudo-relevance feedback approaches (section 3). The basic idea is to first use one of the media types to gather relevant multimedia information and then, in a second step, use the dual type to perform the final task (retrieve, annotate, etc). These approaches can be seen as an "intermediate level" fusion as the media fusion takes place after a first mono-media retrieval step based on mono-modal similarities (see 2.1 and 2.2).

We describe two methods, both falling in the "trans-media" pseudo-relevance feedback category. In our proposed approaches, similarly to [START_REF] Maillot | Ipal inter-media pseudo-relevance feedback approach to imageclef 2006 photo retrieval[END_REF], we need to define similarities between an aggregate of objects and a new multimodal object. In our first approach (section 3.1), we build a model inspired by the mixture model [START_REF] Zhai | Model-based feedback in the language modeling approach to information retrieval[END_REF] of the aggregate. In our second approach (section 3.2), we define trans-media similarities as an aggregation of mono-modal similarities between the elements of the aggregate and the new multimodal object.

We first provide an overview of the state-of-the-art in hybrid text and image information processing, emphasizing work on trans-media relevance feedback (section 1.1). Then we introduce our monomodal similarity measures for images (section 2.1) and for text (section 2.2). We then focus on our two main contributions (section 3). An important part of our article is dedicated to show how these techniques can be applied to a number of scenarios such as unsupervised text illustration (section 4.3.2); image annotation or captioning (section 4.3.1); ranking and retrieval (section 4.1); cross-media clustering and improved visualisation (section 4.4). Finally, we share some details of a system we developed for assisting in the creation of travel blogs (TBAS) in section 5.1. This system illustrates the way many of these techniques can interact in a real world content creation example. Similarly, we present another tool for browsing multimedia corpora, such as Wikipedia in section 5.2.

Prior Art

The scientific challenge is to understand the nature of the interaction between text and images: how can text be associated with an image (and reciprocally an illustrative image with a text)? how can we organize and access text and image repositories in a better way than naive late fusion techniques? The main difficulty is to overcome the semantic gap and, especially, the fact that visual and textual features are expressed at different semantic levels.

Naive techniques combine the scores from a text retrieval system and from an image retrieval system into a single relevance score: this is the late fusion approach. Departing from the classical late fusion strategy, recent approaches have considered fusion at the feature level (early fusion), estimating correspondences or joint distributions between components across the image and text modes from training data. One of the first approaches in this family is the co-occurrence Model by Mori et al. [START_REF] Mori | Image-to-word transformation based on dividing and vector quantizing images with words[END_REF] where keywords are assigned to patches based on the co-occurence of clustered image features and textual keywords in a labeled training data-set. Instead of looking at the co-occurrences, Vinokourov et al [START_REF] Vinokourov | Learning the semantics of multimedia content with application to web image retrieval and classification[END_REF] propose to find correlations between images and attached texts using the Kernel Canonical Correlation Analysis (KCCA). As far as the "pure" visual mode is concerned, features associated to images have become more and more complex: there were attempts of developing more expressive visual vocabularies, potentially hierarchical, relying on latent semantic extraction techniques such as Probabilistic Semantic Analysis [START_REF] Barnard | Matching words and pictures[END_REF][START_REF] Monay | Plsa-based image auto-annotation: Constraining the latent space[END_REF] or Latent Dirichlet Allocation [START_REF] Blei | Modeling annotated data[END_REF]. Duygulu et al experimented with machine translation models where, a lexicon links a set of discrete objects (words in annotations) onto another set of discrete objects (image regions) [START_REF] Duygulu | Object recognition as machine translation :learning a lexicon for a fixed image vocabulary[END_REF][START_REF] Iyengar | Joint visual-text modeling for automatic retrieval of multimedia documents[END_REF].

Another group of works uses graph models to represent the structure of an image through a graph, e.g. with a Markov network [START_REF] Carbonetto | A statistical model for general contextual object recognition[END_REF] or a concept graph [START_REF] Pan | Gcap: Graph-based automatic image captioning[END_REF]. For example, Carbonetto et al [START_REF] Carbonetto | A statistical model for general contextual object recognition[END_REF], allow interactions between blobs through a Markov random field (MRF). Hence, the probability of an image blob being aligned to a particular word depends on the word assignments of its neighbouring blobs. Similarly, the ALIP system of Li and Wang [START_REF] Li | Alip: The automatic linguistic indexing of pictures system[END_REF] models the interaction between blocks using Markov Models. Simple block-based features are extracted from each training image at several resolutions and a two-dimensional multiresolution hidden Markov model (2D MHMM) is used to describe statistical properties of the feature vectors and their spatial dependences.

The use of pseudo-relevance feedback or any related query expansion mechanisms has been used widely in image retrieval. The basic challenge is how to control that the objects retrieved by the first retrieval step are indeed good representatives of the user needs and do not constitute noise.

The approaches proposed in this paper are mostly aligned with a family of models, inspired by Cross-Lingual Information Retrieval. In cross-lingual systems, a user generates her query in one language (e.g. English) and the system retrieves documents in another language (e.g. French). The analogy here is to consider the visual feature space as a language constitued of blobs or patches, simply called visual words.

Several works were proposed in this direction by Lavrenko et al [START_REF] Jeon | Automatic image annotation and retrieval using cross-media relevance models[END_REF][START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF][START_REF] Feng | Multiple bernoulli relevance models for image and video annotation[END_REF]. They are mainly based on pseudo-feedback methods (known also as query expansions) where the initial query is automatically enriched with new words based on a first retrieval step. In [START_REF] Jeon | Automatic image annotation and retrieval using cross-media relevance models[END_REF] they extended the cross-lingual relevance models to cross-media relevance models. These models were further generalized to continuous features in [START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF] with nonparametric kernels, while in [START_REF] Feng | Multiple bernoulli relevance models for image and video annotation[END_REF] the distribution of words was modelled with Bernoulli distributions.

Cross-media relevance models can also be considered as the ancestors of our methods [START_REF] Clinchant | Xrce's participation to imageclefphoto 2007[END_REF] as well as previous methods used in ImageCLEF challenges [START_REF] Chang | Approaches of using a word-image ontology and an annotated image corpus as intermedia for cross-language image retrieval[END_REF], [START_REF] Maillot | Ipal inter-media pseudo-relevance feedback approach to imageclef 2006 photo retrieval[END_REF]. Indeed, the latter methods do not rely on relevance models but act in the same spirit. For example, from a query image, a visual similarity is first computed and an initial set of (assumed) relevant objects is retrieved. As the objects are multimodal, each image has also a text, and this text can feed any 'text' feedback method (other than relevance models). In other words, the modality of data is switched , from image to text or text to image, dur-ing the (pseudo) feedback process. These last models can be called intermedia feedback, or transmedia feedback techniques. In that sense, transmedia techniques generalize the pseudo-feedback idea present in cross-media relevance models, but are freed from the particular textual and/or visual models proposed by cross-media relevance models. These latter techniques, based on intermedia feedback, go beyond simple late fusion and also simplify the difficulties often met by early fusion techniques, especially the famous "semantic gap" between the visual and textual features. This approach can be seen as an "intermediate level" fusion as the media fusion is after a first mono-media retrieval step based on mono-modal similarities (see 2.1 and 2.2).

Using pseudo-relevance feedback to automatically enrich the representation in one mode with the other one is an approach that has been exploited in several works. Most of the time, the Web itself is used as the multimedia repository and search engines such as Google Image are often usefully exploited to this aim.

For instance, to automatically annotate images -or, in other words, to associate with an image a synthetic textual representation that can be further used for indexing and retrieval -Li [START_REF] Li | Image annotation by large-scale content-based image retrieval[END_REF] and Wang [START_REF] Wang | Annosearch: Image auto-annotation by search[END_REF] combined traditional Web-CBIR (content-based image retrieval) and Text Mining techniques (namely text clustering and term extraction) on the textual data (title, caption, surrounding text) associated with retrieved images. By a careful analysis of these textual data, they were able to find a reliable annotation that captures multiple aspects (regions) of the image. In the same vein, but restricted to purely textual information, Dowman [START_REF] Dowman | Web-assisted annotation, semantic indexing and search of television and radio news[END_REF] proposed a method to automatically annotate audio-video news streams, by a first retrieval step on the BBC Web site based on the textual transcripts of the news. After checking the relevance of the first page retrieved, they extracted a summary from this error-free Web page (title, category tags, named entitites) that was then used to annotate the original (noisy) transcript. Our work differs mainly from these approaches by the final objective (multimedia retrieval instead of image annotation), by the repository that is used and by the way the textual representation of an image is built from a set of pseudo-relevant documents.

Automatic illustration of a textual keyword or concept or, in a nearly equivalent view, automatic gathering of huge amount of images representative of a concept constitutes another familily of methods and applications that can use the same principle of pseudo-relevance feedback in an hybrid (textual+visual) way. The ultimate goal is often to build a categorization model able to recognize a given concept (or keyword) in an image. Starting from a concept as a textual keyword, Yanai [START_REF] Yanai | Probabilistic web image gathering[END_REF] proposed to leverage the vast resource of images on the Internet, by using search engine such as Google Image (that does nothing else than a purely textual retrieval based on the textual metadata that can be associated with images); the retrieved images were then used to build an initial visual model of the concept, following the principle of pseudo-relevance feedback; this model was then used to re-score candidate images and updated iteratively following an EM-like algorithm; by segmenting the candidate images into regions, he was able to offer more accurate visual models of the concept, taking into account only the more relevant regions of the image. Li adopted a very similar approach in [START_REF] Li | Optimol: automatic object picture collection via incremental model learning[END_REF], but in a purely visual way: there was no cross-media step. All these approaches share with our methodology the fact to be based on some pseudo-relevance feedback and, at some stage, switch from one medium to the other one. Once again, our work differs mainly from these approaches by the final objective (multimedia retrieval instead of automatic illustration), by the repository that is used and by the way the visual representation of a textual entity is built from a set of pseudo-relevant documents.

Iyengar and colleagues proposed in [START_REF] Iyengar | Joint visual-text modeling for automatic retrieval of multimedia documents[END_REF] a set of cross-media similarity measures that are not based on pseudo-relevance feedback, but on the "information bottleneck" principle, using an intermediate layer of concepts to make the link between both media. They used an audio-video training dataset (the TRECVID dataset), annotated with about one hundred concepts: these annotations allow them to build a textual model and a visual model for each concept or, equivalently, projection operators from textual and visual features towards a common concept space. As they are able to exploit image regions instead the global image, they used an intermediate step of alignment, in order to assign a unique to each image region. They also proposed to use log-linear models of fusion (instead of linear ones) in order to combine both mono-media and cross-media similarity measures. However, experimental results were not very satisfying.

Very recently, Quattoni [START_REF] Quattoni | Learning visual representations using images with captions[END_REF] proposed a completely different approach to exploit textual meta-data (image caption, surrounding text) in image categorization and dimensionality reduction. Based on the "structural learning approach", they used large quantities of unlabeled data with associated captions in order to improve the learning performance in future image classification problems. They learned a low-dimensional representation that reflects the semantic content of an image, by solving a set of auxiliary problems, namely to predict the presence/absence of a content word from the image features. The low-dimensional representation they obtained turned out to be efficient for generic visual concept detection tasks, even if these visual concepts were not used previously. This very intersting approach could be considered as "cross-media semisupervised learning" but is of course completely different from what we are proposing in this paper.

Monomodal Similarities

First, we will introduce the monomodal similarities, visual and textual, that will serve as basic components for the trans-media similarities.

Image Similarity

As image signature (image representation), we use the Fisher Vector as proposed in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF]. This is an extension to the bag-of-visual-words [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF] and the main idea is to characterize the image with the gradient vector derived from the generative probability model (visual vocabulary). This representation can then be subsequently fed to a discriminative classifier for categorization, or used to compute the similarities between images for retrieval.

The generative probability model in our case is the Gaussian mixture model (GMM) which approximates the distribution of the low-level features in images. It can be seen as a Visual Vocabulary where each Gaussian component N (µ i , Σ i ) models a visual word.

If we denote the set of parameters of the GMM by Φ = {w i , µ i , Σ i , i = 1...N } (w i , being the mixture's weight), we can compute the gradient vector of the likelihood that the image was generated by the model Φ:

∇ Φ log p(I|Φ) . ( 1
)
This gradient of the log-likelihood describes the direction in which parameters should be modified to best fit the data (image features). One of its advantages is that it transforms a variable length sample (number of local patches in the image) into a fixed length representation (which we will call Fisher Vector) whose size is only dependent on the number of parameters in the model (|Φ|).

Before feeding these vectors to a classifier or computing similarities between images, each vector is first normalized using the Fisher Information matrix F Φ , as suggested in [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] (see the paper for the computational details):

f I = F -1/2 Φ ∇ Φ log p(I|Φ) (2)
with

F Φ = E X ∇ Φ log p(I|Φ)∇ Φ log p(I|Φ) T .
and then each vector is re-normalized to have an L1-norm equal to 1.

The similarity measure between two images is then defined as the L1-norm of the difference between the normalized Fisher Vectors:

sim V (I, J) = sim V (f I , f J ) = norm MAX -|| fI -fJ || 1 = norm MAX -i | f i I -f i J | (3)
where f i are the elements of the re-normalized Fisher Vector f . These Fisher Vectors are rich image signatures and have shown state-of-the-art performance both in image categorization [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Ah-Pine | Xrce's participation to imageclefphoto[END_REF] and and content based image retrieval [START_REF] Clinchant | Xrce's participation to imageclefphoto 2007[END_REF][START_REF] Ah-Pine | Xrce's participation to imageclefphoto[END_REF].

Text similarity

First the text is pre-processed including tokenization, lemmatization, word decompounding and standard stop-word removal. Then starting from a traditional bag-ofword representation (assuming independence between words), we adopt the language modeling approach to information retrieval. The core idea is to model a document d by a multinomial distribution over the words denoted by the parameter vector θ d . A simple language model (LM) could be obtained by considering the frequency of words in d (#(d, w)) (corresponding to the Maximum Likelihood estimator:

P ML (w|d) = #(w, d) |d| .
The probabilities could be further smoothed by the corpus language model:

P ML (w|C) = d #(w, d) |C|
using the Jelinek-Mercer interpolation :

θ d,w = λ P ML (w|d) + (1 -λ) P ML (w|C) . (4)
Using this language model, we can define the similarity between two documents using the cross-entropy function: Given monomodal similarities, we will now define transmedia similarities. We assume that we have a repository that contains a set of multimodal documents: R = {d 1 , d 2 , . . . , d M }. We will denote the textual part of d j by T (d j ) and its visual part V (d j ). Note that we are interested here in multi-modal documents containing text and image, but the techniques described below are applicable to other types of multimodal documents too. Let us now consider a new document dq, with its corresponding T (dq) and V (dq) monomodal contents. Note that one of T (dq) and V (dq) can be void. Our concern is now to define how to compute trans-media similarities, i.e. a similarity between T (dq) and V (d j ) or, reciprocally, a similarity between V (dq) and T (d j ).

sim T (d 1 , d 2 ) = w P ML (w|d 1 ) log(θ d2,w )) (5)
To tackle this task, we rely on the principle of trans-media relevance feedback (see figure 1). The main idea of trans-media relevance feedback is to first use one of the modes to gather relevant documents and then to switch to the other mode. To be more concrete, in our case we gather the N most relevant documents from R using some purely visual similarity measure (see section 2.1) with respect to the (visual) query V (dq) or, reciprocally, using a purely textual similarity (see section 2.2) with respect to the (textual) query T (dq). Let us call these top ranked documents n vj and n tj (j = 1, . . . N ) respectively. Obviously, they are not the same in general.

This results in two "dual" representations of the query dq : the textual, dual representation of the visual part V (dq) is an aggregate textual entity denoted by:

N T (V (dq)) = {T (n v1 ), T (n v2 ), . . . , T (n vN )} (6)
Similarly, the visual, dual representation of the textual part T (dq) is an aggregate visual entity denoted by:

N V (T (dq)) = {V (n t1 ), V (n t2 ), . . . , V (n tN )} (7)
We will use these new "dual" representations to compute the trans-media similarity measures. The problem now amounts to define a monomodal similarity measure between some aggregate N T (V (dq)) (resp. N V (T (dq))) and T (d j ) (resp. V (d j )). To this aim, we propose two approaches. The first one remains at the feature or representational level (section 3.1) , while the other directly focuses on aggregating the similarities rather than aggregating the features (section 3.2).

Models for representing aggregated objects

This first approach is more related to textual aggregates, but we can envisage an analog approach for the visual part. The main idea is that we consider the set of aggregated texts in N T (V (dq)) as a set of relevant texts (they are all related to the visual part of the query document dq) and try to model this "relevance concept" F by a language model (LM) θ F . Here, a Language Model must be understood as some probability distribution over the words of the vocabulary. This idea has its inspiration from the language modeling approach to information retrieval originally designed to enrich textual queries (see [START_REF] Zhai | Model-based feedback in the language modeling approach to information retrieval[END_REF] for the basic approach ; more elaborated techniques of feedback for language models can also be envisaged : e.g. [START_REF] Tao | Regularized estimation of mixture models for robust pseudo-relevance feedback[END_REF]).

Let θ F be a multinomial parameter standing for the distribution of relevant terms in N T (V (dq)). In other words, θ F is a probability distribution over words but peaked on relevant terms. It can be easily shown that the likelihood of observing F assuming that it is generated by the process characterized by θ F is:

P (F|θ F ) = nj ∈NT (V (dq)) w∈nj (λP (w|θ F ) + (1 -λ)P (w|θ R )) #(w,nj) (8)
where P (w|θ R ) is word probability built upon the whole repository (what is called usually the corpus language model), λ is a fixed parameter, which can be understood as a noise parameter for the distribution of terms and #(w, n j ) is the number of occurence of term w in document n j . The language model θ F is learned by maximum likelihood optimization with an Expectation Maximization algorithm (as described in [START_REF] Clinchant | Xrce's participation to imageclefphoto 2007[END_REF]). Now θ F is considered as the new representation of dq and we can use standard similarity measures over probability distributions (like the Kullback-Leibler Divergence or the Cross-entropy) in order to derive a similarity between θ F and the textual part T (d j ) on any document (in the repository or not), as soon as the latter is represented by a language model too.

Finally, note that we illustrated the approach using N T (V (dq)) to derive a textual language model of θ F that can be used in conjunction with the original language model of the textual view of the query T (dq), using a simple linear mixture. We can also derive a similar scheme using N V (T (dq)) to derive a new representation (actually some generalized Fisher Vectors) of the "relevance concept", this time relying on Rocchio's method that is more adapted to continuous feature representation ( [START_REF] Rocchio | Relevance feedback in information retrieval[END_REF]):

f F = 1 N v∈NV (T (dq)) fv + 1 |R| d∈R f V (d) (9)

Aggregating Similarity Measures

As an alternative to define a model for the aggregated objects, we can directly aggregate the similarities between the new document and the elements of the aggregated object.

For example, if we use the visual query to gather N T (V (dq)) (see ( 6)), then the new cross-media similarity measure between dq and any multi-modal object is defined by :

sim T V (d, dq) = sim T (T (d), N T (V (dq))) = t∈NT (V (dq)) sim T (T (d), t) (10)
where sim T is typically defined by equation [START_REF] Carbonetto | A statistical model for general contextual object recognition[END_REF]. Note that we do not use the visual part of d nor the textual part of dq which suggests that this similarity measure can also be used directly to compute the similarity between a purely visual object and purely textual object.

In analogy we can switch the two modalities and write:

sim V T (d, dq) = sim V (V (d), N V (T (dq))) = v∈NV (T (dq)) sim V (V (d), v) (11)
where sim V is typically defined by equation [START_REF] Blei | Modeling annotated data[END_REF].

In this case, we do not use the textual part of d nor the visual part of dq.

In the same vein, coming back to the monomodal case, we could define similarity measures in one mode that does not switch mode in the pseudo-relevance feedback phase. This naturally leads to the following equations:

sim T T (d, dq) = sim T (T (d), N T (T (dq))) = t∈NT (T (dq)) sim T (T (d), t) (12)
and

sim V V (d, dq) = sim V (V (d), N V (V (dq))) = v∈NV (V (dq)) sim V (V (d), v) (13)
where

N T (T (dq)) = {T (n t1 ), T (n t2 ), . . . , T (n tN )} ( 14
)
is the aggregated text set obtained by pseudo-relevance feedback on the textual query T (dq) and

N V (V (dq)) = {V (n v1 ), V (n v2 ), . . . , V (n vN )} (15)
is the aggregated image set obtained by pseudo-relevance feedback on the visual query V (dq). Finally, we can combine all the similarities to define a global similarity measure between two multi-modal objects d and dq using, for instance, a linear combination:

sim glob (d, dq) = λ 1 sim T T (d, dq) + λ 2 sim T V (d, dq) + λ 3 sim V T (d, dq) + λ 4 sim V V (d, dq) (16)
Fig. 2 Applications Scenarios of a trans-media system

Application Scenarios

We now describe different scenarios where trans-media similarities are effective. Generally, a user manipulating multimodal data needs clustering and retrieval functionalities.

In order to browse a corpus efficiently, a user also need to express her information need in different modes : visual only, textual only or finally in a mixed representation. Moreover, the user also needs to switch her expression mode from a medium to another one. Figures 2 presents some of these scenarios which rely on trans-media similarities. In the following section, we will explain in details these scenarios: retrieval, image annotation, text illustration and clustering.

Ranking and retrieval

Given a multi-media repository R, our goal is to rank these documents with respect to a new multimedia document (query) dq based on trans-media relevance feedback. This was already tackled in section 3 for mono-media type of queries (dq = T (dq) or dq = V (dq)) and, in this section we go beyond and show how we can integrate and exploit the hybrid nature of the query to improve the retrieval performance. In accordance with the two approaches of section 3, we have again several options:

Language Model of the Aggregated Text

Using the visual part of the query document, we gather the aggregated text:

N T (V (dq)) = {T (n v1 ), T (n v2 ), . . . , T (n vN )}
and estimate a language model θ F for this aggregate. But we can also estimate a language model θq of the textual part of the query T (dq). Combining the two language models through interpolation:

θ q ′ = αθq + (1 -α)θ F (17)
leads to a new query language model θ q ′ that can be used with the Cross-Entropy similarity measure (see section 2.2) to perform a new retrieval on the textual part of objects in R. Setting the value of α is done experimentally and adapted to the particular collection. The robustness of the estimation of θ F has a significant impact on the value of α. Lastly, the value of α can be interpreted as a mixing weight between image and text.

Aggregating Similarity Measures

In section 3.2 we have defined several trans-media similarity measures. These measures can be used directly to re-rank the documents d j of R according to the query dq. Indeed if V (dq) is the visual part of the query document dq and T (d j ) belongs to the initial feedback set N T (V (dq)), then the rank of the neighbors of T (d j ) in the textual sense will be increased even if they are not so similar from a purely visual viewpoint (even when having no image at all). Similarly, when we use T (dq) as query we will increase the ranks of the objects whose image part is similar to V (d k ) ∈ N V (T (dq)) even if they have no textual similarity (or no text at all) with T (dq). Combining them as in ( 16) will take into account both the textual and visual part of the query in the re-ranking process.

The main advantage of this method is that all the measures in ( 16) involves mainly pair-wise similarities between the documents of R. Therefore assuming that the corpus is of reasonable size, those similarities can be pre-computed, so the step after the first search (relevance feedback) can be very fast and efficient.

These retrieval methods have been evaluated at ImageCLEFphoto 2007 [START_REF] Clinchant | Xrce's participation to imageclefphoto 2007[END_REF] and ImageCLEFphoto 2008 Evaluation Forums [START_REF] Ah-Pine | Xrce's participation to imageclefphoto[END_REF]. In these challenges, our image and trans-media similarity based retrieval systems demonstrated very good performance (see [START_REF] Grubinger | Overview of the ImageCLEFphoto 2007 photographic retrieval task[END_REF]). We give in table 1 the best results we obtained for ImageCLEFphoto 2008, using mono-media (text or image) or multimedia (text and image, using late fusion or trans-media similarities) approaches [START_REF] Ah-Pine | Xrce's participation to imageclefphoto[END_REF]. We used MAP (Mean Average Precision) and P@20 (precision at 20) for measuring each run performance. Our runs were ranked among the best ones. As we can see, the results provided by the trans-media approach clearly outperforms both the mono-media approaches and the simple late fusion technique.

Media

Incorporating diversity into the top list

In ImageCLEFphoto 2008, one of the main problems we had to address was to improve the search results by avoiding the redundancy among the first retrieved elements. In other words, the participants were asked to provide results that are both relevant and diverse.

To address this issue, we opted for a two-step approach. The first step consists in ignoring the question of diversity. In other words, we first try to find the most relevant objects using the material introduced in 3.2 and mentioned in the previous paragraph. Then, in a second step, we re-rank the first relevant elements by taking into account their mutual similarities in order to avoid redundancy and thus to promote diversity.

We investigated two main families of methods: implicit and explicit clustering-based approaches. The first method is commonly known as "Maximal Margin Relevance" (MMR) [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF]. It amounts to re-rank the search results so that the element chosen at rank j has to be dissimilar to elements that were already selected at ranks j ′ < j. The second method is based on an explicit clustering of the first k elements, followed by a strategy designed to re-rank the elements so that many different clusters are represented among the first elements of the re-ranked list (see [START_REF] Ah-Pine | Xrce's participation to imageclefphoto[END_REF] for more details).

In both approaches, we are given two components: S1, the similarity vector between a query and the documents of the database and S2, the pairwise similarity matrix between documents of the database.

In the experiments we did for ImageCLEFphoto 2008, we used the results given by the trans-media similarities for measuring the relevance of an object with respect to a query. Therefore, S1 is typically the trans-media run which, as mentioned in the previous paragraph, was the best run we obtained regarding MAP and P@20.

S2 is used for representing the thematic proximity between two documents that will allow us to promote diversity. We tested different similarity matrices. Particularly, in the case of clustering-based approaches, we investigated if either pure textual or multimedia similarities performed better. For the pure textual similarities we used the basic tf idf between the text part of the documents. For the multimedia approach we applied our trans-media similarity measure to the multimedia documents. We report in table 2, the results we obtained. For measuring diversity, the CR@20 (cluster recall at 20) index is used. It is the number of different clusters that is present among the 20 first retrieved elements divided by the total number of clusters that were manually identified by the evaluators. Compared to the pure textual method, the trans-media approach gives better results for both the diversity and the relevance measures. Consequently, for this task, it is also beneficial to combine visual and textual information using our trans-media similarities method in order to improve the results.

Media

Relating text and image through a repository

In section 3 we defined similarity measures between a new document d and the elements of the aggregated object obtained by trans-media relevance feedback using a multimodal query dq. However, neither d nor dq has to be necessarily multi-modal.

Image Annotation

If we consider simply dq = I an image, and d = T a pure text not necessarily in R, [START_REF] Feng | Multiple bernoulli relevance models for image and video annotation[END_REF] becomes:

sim T V (T, I) = sim T (T, N T (I)) = T (dj)∈NT (I) sim T (T, T (d j )) (18)
a similarity defined between an image and text based on a common multimodal repository.

Text Illustration

By duality, we can use the text T as query dq = T and the image as the new document. Then [START_REF] Feng | Multiple bernoulli relevance models for image and video annotation[END_REF] becomes:

sim V T (I, T ) = sim V (I, N V (T )) = V (dj )∈NV (T ) sim V (I, V (d j )) (19)
another similarity defined between the image and the text. Furthermore, we can cluster the top retrieved images and illustrate the different views on the given text.

Trans-media Similarity-based Searching, Clustering and Visualization

Given a set of multimedia documents, our goal is to find the underlying structure of the dataset and also to visualize the proximity relations between the multimedia documents by means of projections in a suitable space 1 . In other words, we want to cluster the datasets, in order to capture the proximity relationships between multimedia documents and then to represent these documents into a space which respects these proximity relationships.

Clustering and visualization processes are of interest for browsing a multimedia corpus such as Wikipedia as we will show in our experiments in section 5.2. Indeed, it allows to seek for information in an exploratory mode by using either the visual or the textual or both the combination of visual and textual aspects of the documents. We can talk about a multi-view access of the multimedia corpus.

When dealing with monomedia documents, many methods exist for clustering and visualizing datasets of images or datasets of texts. In our context we are interested in clustering and visualizing multimedia documents where we have to fuse information from two different monomedia sources. However, as we already mentioned previously, we want to combine the visual and the textual information of a same document at an intermediate level which is different from an early fusion approach or a late fusion approach that were already suggested. In other words, we want to better take into account the semantic correlation between the visual view and the textual view of a same document. For doing so, we propose firstly, to apply our trans-media similarities given in section 3 and then, to use the global similarity matrix given by ( 16) in clustering and projection methods.

Indeed, the global similarity matrix aggregates monomedia similarities with transmedia similarities computed at an intermediate level. As a result, we obtain a global similarity matrix between multimedia documents which aims at overcoming the "semantic gap" between visual and textual representation. Finally, by using this measure, we integrate semantic correlation better than basic early and late fusion methods do.

We will give some examples in section 5 which show that using our global similarity, we are able to retrieve and explore a multimedia corpus in a more efficient way than by using visual similarities or textual similarities only.

Taking in consideration all these different points, we propose a system which allows a user to switch between the different kinds of representation a multimedia document or query can have : monomedia or multimedia representations.

We first compute monomedia similarities based on the methods we have defined in sections 2.1 and 2.2. Given sim V in (3) and sim T in (5), we compute trans-media similarities according to section 3 and we finally retain the aggregated global similarity sim glob in [START_REF] Jeon | Automatic image annotation and retrieval using cross-media relevance models[END_REF] as the similarity matrix that we will use for dealing with multimedia representation of documents or queries.

These three similarity matrices are our basic inputs for similarity-based search, clustering and projection processes :

they are directly used to retrieve similar documents d according to a given document dq corresponding to a query they are the inputs of clustering algorithms which allow to gather in a same cluster documents which are similar they are also the inputs of projection algorithms which allow to represent into a 2D space the graph corresponding to the original proximity relationships between documents

As each representation namely visual, textual and trans-media, can be used, the user has a multi-view acces of the documents of the corpus. In other words, we have three clustering and projection results that the user could use depending on the type of representation of the documents he is interested in.

Multimedia Systems

The next section is devoted to the presentation of two systems, based on the previous scenarios. The first system is a Travel Blog Assistant: its main goal is to help a user generating content for her blog, by linking text and images. The second system is a browsing tool for multimedia corpora, such as Wikipedia. It enables clustering and retrieval in a dataset of composite objects.

Travel Blog Assistant System

To illustrate some of these techniques working on real examples, we build a so called Travel Blog Assistant System (TBAS). Such a system can be of interest for real travelogue websites such as [START_REF] Travelblog | [END_REF][START_REF]Travelpod[END_REF][START_REF]Trippert[END_REF][START_REF]Footstops[END_REF][START_REF]Travbuddy[END_REF][START_REF] Realtravel | [END_REF][START_REF]Travellerspoint[END_REF].

Fig. 3 The prototype interface of our TBAS system.

Figure 3 shows the overall schema of the TBAS system. Its main steps are:

-The user uploads a set of images to be considered. If he edits his blog during his travel he simply plugs his camera and uploads the images captured that day and the previous days (Figure 3(a) and (b)). The images are then pre-processed and image metadata are added to each image. The metadata file can contain different type of information and is typically a structured xml file. First, information such as date, time, location (GPS) can be provided by the camera (exif file). Finally, textual information (tags) are obtained using a trans-media feedback using a repository of multi-media objects (e.g. database of the travelogue site itself) as described in section 4. -When all paragraphs are processed and the illustrative images selected, the system shows a preview of the composed "blog". The page layout can be computed automatically or selected from a set of template layouts. When the user is satisfied with the result, he can simply publish the blog.

A demo version of the TBAS system was developed and tested on a relatively small database (compared to the data we can get on the web). To simulate the traveler's image data, we downloaded under Creative Common licences 185 images from the online photo sharing site Flickr [START_REF] Flickr | [END_REF]. For the travel blog text we collected real blog paragraphs from two travel blog sites, RealT [START_REF] Realtravel | [END_REF] and Tpod [START_REF]Travelpod[END_REF]. In all cases, in order to ensure the semantic correlation between images and blog texts, we focused on two main destinations, Peru and Brasil, and used a few touristic names (cities, etc.) associated with them as keywords or tags for focusing our search in gathering the images and the blog paragraphs.

In figure 4, we show the most similar images for a given blog paragraph, using our transmedia similarities: we ranked the 185 downloaded Flickr images for each travel blog text and selected the top 4 images for each blog.

Trans-media Browsing of Wikipedia Pages

In this section, we present a recent work done in the context of Cap Digital -Infomagic, which is a french project on digital content creation and knowledge management. In a joint work with INA, we have adressed a task of this project about "browsing a multimedia corpus".

The scenario is the following one : a user has at his disposal a multimedia corpus constituted of documents which have both a visual and a textual representation; he is seeking for information within this corpus but he does not know exactly how to express his query; so, he wants to browse the multimedia corpus in an exploratory way in order to progressively refine the expression of his information needs. Given this context, our goal is to provide the user with a system which has the following properties :

when seeking information in such a multimedia corpus, the user can be interested in either the visual feature or the textual feature or the combination of both visual and textual features, of the documents. His interest, moreover, can change at any time : suppose, in a first time, that the user entries a textual query, then a list of multimedia objects is retrieved according to the textual similarities. Looking at this list, the user, in a second time, is more interested in a particular multimedia document because its associated image has attracted his attention. Finally, he would like to look for similar multimedia documents by taking into account both the image and the text associated to this relevant multimedia document. In that context, we want the system to allow the user to search using trans-media similarities. In a general manner, we want the system to allow the user to choose the kind of queries, monomodal or transmodal, which reflects the most what he is searching for. As a result, the system has to integrate as many kind of similarities as types of queries the user can express. -when seeking information in an exploratory mode, an efficient system is the one which assists the user by providing him with a visualization tool which allows to represent proximity relationships between the multimedia documents. In that case, as we have described in section 4.4, clustering and projection methods for information retrieval are relevant processes. Firstly, clustering the set of multimedia documents allows to structure the dataset of multimedia documents into a meaningful partition based on similarities between documents. Using this partition and given a query, the system can suggest the user a list of clusters of relevant documents rather than a simple list of relevant documents. Secondly, projection methods allow to represent the multimedia documents, by means of a graph embedded into a 2D space for example, such that similar documents are close to each other. Using a visualization tool, the user can then explore and browse more intuitively the corpus. In general terms, we want the system to allow similarity-based search where the user can "navigate" in an efficient way within the corpus using the projection and the visualizing tool.

In collaboration with INA, we developed a system which main characteristics are described in section 4.4 and adressed most of the scenarios presented in figure 2. In the context of the previous scenario, this system allows the user to be assisted in his information search needs. We experiment such a system using a subset of the french Wikipedia corpus. We give some details and some screenshots of this systems below.

Extracting multimedia documents from Wikipedia corpus

In this paragraph, we briefly introduce the multimedia corpus on which we applied our system. This corpus concerns around 8,500 pages taken from the french Wikipedia corpus. We extracted these pages from the xml dump done in September 2007 and provided by the Wikipedia Foundation2 .

We selected pages according to their categories. In that perspective, we used the category tree3 of the Wikipedia pages and we selected any pages which has at least one category that has the category "Geography" or "Tourism" as root. For these pages we looked at their images and we extracted the following textual descriptions :

the path of titles, from the page title to the paragraph title where an image is encountered the free-text description of an image which corresponds to the comments we can see below most of images in Wikipedia the whole paragraph where an image is encountered A multimedia document is an image associated to the text given by the concatenation of these three textual desciptions. We obtained more than 23,500 multimedia objects associated to more than 19,000 images and more than 14,000 texts (an image can leads to more than one multimedia objects as it could be associated to several texts and vice versa).

Browsing the Wikipedia corpus

We have explained previously, in which kind of scenarios we place ourselves. In this paragraph, we give some screenshots of the visualization tool developed by INA for illustrating how our monomedia and transmedia similarities methods can be used for browsing efficiently a multimedia corpus.

In figure 5, we show a general view of the browsing tool :

on the left part, we can see the representation in a 2D space of the multimedia documents (in this figure the graph represented is the one based on the textual representation only). We can clearly observe "round packets" of points. These last are clusters of similar documents and the different colors corespond to different clusters. The user can zoom in and zoom out this graph. The point are multimedia documents which can be represented either by their associated images or the most salient words of the associated text. Furthermore, the user can acces directly to the Wikipedia page (or paragraph) corresponding to a selected multimedia object. -on the top right part, there are several tabs which allow the user to customize different parameters such as the layout or the format. But, as we describe it below, the most relevant options that concern this paper are the tabs which allow the user to search into the corpus using different similarities and to change the type of graph depending on the representation of the multimedia documents the user want to use. By choosing one particular tab, there is a particular UI which appears below the tabs region.

The most relevant tabs with respect to the present paper are the following ones :

the "Wikipedia Search" tab which allows the user to search in the corpus by using different kinds of similarity : in figure 5 for example, we selected a multimedia document, then a particular similarity matrix (trans-media in that case) and this gives as output (on the right) the list of the 100 multimedia documents (the associated image and the most relevant textual features) which are the most similar to the query based on the chosen similarity matrix. In the graph, the documents which belong to the list are surrounded with a square the "Wikipedia Maps" tab which allows to change the graph according to a representation and its associated similarity matrix. When switching from one graph to the other, there is an animation which allows the user to visualize how the position of the surrounded documents moves.

Combining visual and textual information can be relevant in information retrieval and seeking

In this paragraph, we illustrate with an example, how trans-media similarity based search, using our global similarities given by ( 16), can improve information retrieval tasks. Suppose in a first time, that we are interested in an image query (a flower which corresponds to the first flower of the list shown in figure 6). Using our tool, we first search for the most similar documents (considering their visual part) by using the visual similarity matrix and by visualizing these documents in the corresponding graph.

In figure 6, we show the region of the graph where most of the retrieved documents are. We can observe that these relevant documents are in one big cluster that is constituted, from the visual point of view, of photos of flowers (the other images of flowers are not surrounded mainly because the retrieved list is limited to the 100 most relevant documents).

In order to refine the results obtained, we can represent the same list of documents in another graph namely the one based on the global similarity matrix. In other words, we want to take into account the combination of the visual and the textual part of the documents. In figure 7, we show the most dense region of relevant documents in this global graph. Unlike the graph based on the visual similarities, we can mainly observe in figure 7, two different clusters. From the visual point of view, it is hard to distinguish these two clusters as there are flowers in both of them. But, by considering the fact that in this representation, we use the global similarities which integrate trans-media similarities, we can deduce that this separation is mainly due to the textual features. This is actually the point. Indeed, by looking at the textual description of those two clusters in more details, we observe that the cluster on the right concerns flowers from the "Vercors" which is a montain region in the south-east of France whereas, the cluster on the left, concerns flowers which are from the "Pyrénées" which is another mountain region but in the south-west of France. In this example, we show that despite high visual similarities, the global similarities, by taking into account in an efficient way the textual information of the multimedia documents, allows to refine information retrieval.

The combination of visual and textual features has allowed to know that the image query is a flower which is encountered in two different regions of France. Furthermore, in an exploratory mode, it also allows, while seeking deeper into the clusters, to discover other flowers that are in those two different regions.

Conclusion

We have presented a framework for accessing multimodal data. First of all, the theoretical contribution is the extension of the principle of trans-media feedback, into a metric view: the definition of trans-media similarities. As it was shown, these new similarity measures of cross-content enables to find illustrative images for a text, to annotate an image, cluster or retrieve multi-modal objects. Moreover, the trans-media similarities are not specific to image and text: they can be applied to any mixture of media ( speech, video, text ) or views of an object. Most importantly, we have shown how these techniques can be used in two use cases: the travel blog assistant system and the multimedia browsing tool. These two applications stress the necessity of cross-media systems, where no monomedia systems can solve the user's problem, nor adress all the different user's need at the same time.

Fig. 1

 1 Fig. 1 Trans-media feedback principle

  3.1. -As represented in Figure (3(c)), the typed (or uploaded) blog text is pre-processed at a paragraph level and related to the images through the repository (see section 4.3). These similarities allow the system to rank the images according to a given paragraph. The top N ranked images (thumbnails) are shown to the user as illustrative examples of the paragraph The user has naturally the possibility to select between them, or to reject and ask for the next N images.

Fig. 4

 4 Fig. 4 Top 4 images to be associated with a blog's paragraph.

Fig. 5

 5 Fig. 5 General screenshot of INA's tool

Fig. 6

 6 Fig. 6 Retrieved documents represented in the graph based on visual similarities

Fig. 7

 7 Fig. 7 Retrieved documents represented in the graph based on global similarities

Table 1

 1 Some results obtained for ImageCLEFphoto 2008

		MAP P@20
	Text only	0.239	0.293
	Image only	0.151	0.328
	Late fusion	0.348	0.437
	Trans-media	0.424	0.554

Table 2

 2 Some results obtained for ImageCLEFphoto 2008 with diversity seeking goal

		MAP P@20	CR@20
	Text only	0.360	0.512	0.408
	Trans-media	0.369	0.527	0.411

such as graph embedded into a

2D representation for example

http://download.wikimedia.org/

http://stats.wikimedia.org/EN/CategoryOverviewIndex.htm

Acknowledgements The authors want to thank particularly INA for their contributions in our work and Florent Perronin for his greatly appreciated help in applying some of the Generic Visual Categorizer (GVC) components.

We would like also to acknowledge the following Flickr users whose photographs we reproduced here under Creative Common licences:

Finally would like also to acknowledge the users who wrote the blog pharagraphs were used and reproduced here. These texts can be found at the folloing adresses: http://realtravel.com/cuzco-journals-j1879736.html http://realtravel.com/machu picchu-journals-j5181463.html http://realtravel.com/rio-journals-j4669810.html http://www.travelpod.com/travel-blog-entries/sarah s america/south america/ 1140114720/tpod.html http://www.travelpod.com/travel-blog-entries/rachel john/roundtheworld/ 1146006300/tpod.html http://www.travelpod.com/travel-blog-entries/eatdessertfirst/world tour 05/ 1160411340/tpod.html http://www.travelpod.com/travel-blog-entries/idarich/rtw 2005/ 1140476400/tpod.html http://www.travelpod.com/travel-blog-entries/twittg/rtw/ 1132765860/tpod.html http://www.travelpod.com/travel-blog-entries/emanddave/worldtrip2006/ 1155492420/tpod.html