Kyriakos A Eslahian

Arghya Majee

Michael Maskos

Alois Würger

Specific salt effects on thermophoresis of charged colloids

Keywords:

I. INTRODUCTION

When applying a temperature gradient to a colloidal suspension, molecules and nanoparticles migrate to the cold or to the hot, depending on the solute and solvent properties [1][2][3][4]. In recent years, this Soret effect, or thermophoresis, has been used for colloidal confinement to a micron-sized hot spot in a channel or thin film [5][6][7], and for self-propulsion of hot Janus particles in active colloids [8][9][10]. The underlying thermal forces are very sensitive to the electrolyte composition. Thus colloids move to the cold side in NaCl solution and to the hot in NaOH, because of the Seebeck effect which takes opposite signs in these electrolytes [11][12][13][14]. The related electric field has been discussed in view of translocating DNA through nanopores [15] and accumulating charge in a micron-size hot spot [16,17]. More generally, thermophoresis shows specific-ion effects [18,19] similar to the Hofmeister series of protein interactions. As another signature for charge effects, the electrostatic repulsion of nearby particles gives rise to a characteristic dependence on volume-fraction and salinity [20,21] The temperature dependence of thermophoresis is poorly understood, in particular the strong increase with T and the change of sign that occur in many instances [22][23][24][25][26]. In a study on lysozyme protein, Iacopini et al. separated the effect of temperature and salinity [22]; their data give clear evidence for an important non-ionic interaction that dominates the temperature dependence. This has been confirmed for non-ionic surfactants [26,27] and PNIPAM microgels [24,25]. A phenomenological law proposed by Piazza describes remarkably well the behavior of non-ionic solutes, proteins, polyelectrolytes, and charged latex beads [26]. Regarding the latter, there is so far no direct proof for a non-ionic driving mechanism. To know whether it exists or not, is important for an efficient surface functionalization of self-propelling colloids.

The present paper addresses two questions on thermophoresis of charged particles: First, is there a nonionic contribution and, second, what is the origin of the temperature dependence? We report on thermal fieldflow fractionation (ThFFF) measurements of the Soret coefficient of polystyrene sulfonate (PS) beads as a function of electrolyte composition and temperature. In view of the theory of phoretic motion of colloids, our data strongly suggest that the answer to the above questions is intimately related to the temperature-induced salt-ion gradients.

The paper is organized in the following way. Sect. 2 gives details of our experimental setup, and Sect. 3 an overview of the theoretical description of thermophoresis due to electric-double layer forces. The effects of the electrolyte composition and temperature are discussed in Sects. 4 and 5. We conclude in Sect. 6 with a discussion of our main results and a comparison to protein thermophoresis.

II. EXPERIMENTAL SECTION

We briefly present the principle of ThFFF as shown in Fig. 1. The colloidal suspension is injected at the channel entrance and, after an equilibration time of one minute [START_REF] Martin | Thermal Nonequilibrium Phenomena in Fluid Mixtures[END_REF], reaches a steady state with vertical concentration profile c = c 0 e -z/ℓ , where the retention length 1/ℓ = S T ∆T/w depends on the Soret coefficient S T , the temperature difference ∆T = T h -T c across the channel, and its width w. In our setup the channel length is 46.4 cm, the breadth 1.8 cm, and the width w =100 µm. Pumping the suspension through the channel results in a parabolic velocity profile. At the exit, the colloidal content is determined by detection of the UVabsorption as a function of time. Typical elution profiles as in Fig. 1c, consist of a strong Gaussian feature at FIG. 1: Schematic view of our ThFFF setup. a) The Soret equilibrium state in the vertical temperature difference is prepared at the entrance of the channel, with a vertical concentration profile c = c 0 e -z/ℓ . b) Pumping the suspension through the channel results in a parabolic velocity profile. At the exit, the colloidal content is determined by detection of the UV-absorption as a function of time. c) Typical elution profiles consist of a strong Gaussian feature at t = tr that describes the arrival of the particles accumulated close to the lower wall. We show elution patterns at different temperatures. At higher T , the position of the Gaussian is shifted to later times, implying a smaller retention length ℓ and thus a higher Soret coefficient. t = t r that describes the arrival of the particles accumulated close to the upper or lower wall; the small precursor peak occurs at the moment where the front of the parabolic flow profile reaches the exit. At higher T , the position of the Gaussian is shifted to later times, implying a smaller retention length ℓ and thus a higher Soret coefficient. In all experiments the flow rate is 0.3 mL/min and the colloidal mass fraction at the moment of injection is in the order of 10 -4 ; the temperature difference is in the range ∆T = 15...25 K for the data shown in Fig. 2 and3, and ∆T = 10...15 K for those in Figs. 4 and5. The effective temperature is calculated by assuming a linear temperature profile through the channel and taking the concentration-weighted mean value. For positive and negative S T this gives T = T c + ∆T (ℓ/w), and

T = T h -∆T (ℓ/w), respectively.
The Soret coefficient is determined following a standard procedure [START_REF] Martin | Thermal Nonequilibrium Phenomena in Fluid Mixtures[END_REF]. The channel void time t 0 , which is given by the centre of gravity of the elugram of one non-retained sample, is divided by the retention time to calculate the retention ratio R = t 0 /t r . The almost parabolic velocity profile results in a characteristic elution pattern that allows us to determine the length ℓ through the relation R = 6λ coth(1/2λ) -12λ 2 , where λ = ℓ/w = 1/S T ∆T [START_REF] Schimpf | Fieldflow fractionation handbook[END_REF]. For most of our data, λ is in the range from 2 to 6%. In the calculated retention parameters, we account for deviations of the flow profile due to the temperature dependent viscosity. Retention parameters have to be corrected in terms of the deviation parameter [START_REF] Belgaied | [END_REF], taking the not ideal flow profile into account, which results from the temperature dependence of the solvent [31]. ThFFF does not distinguish whether the colloid accumulates at the upper or lower plate, and thus provides only the absolute value |S T | of Soret coefficient. Thus the sign has to be inferred from continuity of the data and from previous experiments.

The samples PS 90 and PS 136 are prepared by surfactant-free emulsion polymerization, according to Juang and Krieger [32]. Two-phase polymerization is performed in a glass reactor, thus ensuring optimized stirring and temperature control. After heating the reactor up to 65 • C, 177.7 g of water and 56.8 g of styrene are added. The difference between preparation of PS 90 and PS 136 is the amount of ionic stabilizing comonomer introduced: 0.63 g (PS 90) and 0.41 g (PS 136) of 4styrene sulfonate. After 5 min of homogenization, the radical initiator potassium persulfate, 0.36 g solved in 10 g of water, is added drop-wise. The reaction is kept alive for 24 h, and then latex emulsions are cooled down to room temperature, filtered and dialyzed. The stability of resulting colloidal suspensions is given by electrostatic repulsion, caused exclusively by the introduced sulfonate groups. The sample PS 215 is purchased from Thermo Fisher Scientific (Waltham, MA, USA), and used without further treatment.

All experiments are performed in de-ionized water (18.2 × 10 4 Ωm) without adding surfactant. Except styrene which has to be distilled in prior to the synthesis, all chemicals are introduced as purchased in analytical grade from Merck (Darmstadt, Germany). Hydrodynamic radii of the particles used in this report are determined by dynamic multi-angle light scattering and the spherical shape is verified by transmission electron microscopy. All samples reveal having a very low polydispersity index.

III. CHARGE-DRIVEN THERMOPHORESIS

Charge effects on colloidal motion in a non-uniform electrolyte solution arise from the interaction with the non-uniform electric double-layer [34]. In our systems the Debye screening length κ -1 is small as compared to the particle size, and the surface potential ζ takes moderate values. Thus viscous effects can be treated in boundary layer approximation, and the screened electrostatics can be evaluated to second order in ζ. Then the particle velocity reads [4]

u = - εζ 2 12η ∇T T - ∇n 0 n 0 - ∇ε ε + εζ η E, (1)
with the solvent viscosity η, permittivity ε, and salinity n 0 , and an applied electric field E. The terms in parentheses describe motion in a temperature gradient [35], in a salt gradient [36], and due to an electrostrictive force [37]; the particle moves toward lower temperature but higher salinity and permittivity. The last term in (1) accounts for electrophoresis in an electric field E, with the Helmholtz-Smoluchowksi mobility εζ/η.

Here we deal with an applied thermal gradient and its companion fields induced by the temperature dependent properties of the electrolyte solution according to

τ = - T ε dε dT , α = - T n 0 dn 0 dT , E = S∇T. (2)
Parameter τ accounts for the temperature-dependent permittivity of water. The solvation enthalpies of positive and negative salt ions vary with temperature; they result in a non-uniform salinity with thermal diffusion factor α and a thermoelectric field with Seebeck coefficient S. With the quantities defined in (2) the particle velocity reads u = -D T ∇T , where the companion fields are absorbed in the mobility D T . Its ratio with the Stokes-Einstein coefficient D = k B T/6πηa gives the Soret coefficient S T = D T /D, which varies linearly with the particle radius a. From the above equations we have

S T = 6πa k B T 2 εζ 2 12 (1 + τ + α) -εζST , (3)
where the expressions in parentheses have the dimension of a force, and take typical values of a few pN. A positive sign of S T means that the particle moves to lower temperatures.

It is instructive to compare the magnitude of the different contributions to S T . With a = 215 nm in the overall prefactor and ζ = -50 mV, we find that Ruckenstein's thermo-osmotic term, that is, the "1" in Eq. (3) contributes 0.1 K -1 , and the electrostrictive force ∝ τ about 0.2 K -1 . In NaCl solution, the specific-ion effects with coefficients α and S contribute 0.4 and 0.6 K -1 , respectively; in other words, the four terms are positive and of the same order of magnitude. In NaOH solution, however, the ion-specific effects contribute 0.6 and -3.5 K -1 . These numbers imply that the Soret effect is to a large extent determined by the Seebeck and diffusiophoresis contributions. For negatively charged particles in NaOH solution, one expects the Seebeck term to result in a negative Soret coefficient [12].

Colloidal particles dispersed in an electrolyte solution constitute a quaternary system. An effective binary system as in Eq. ( 3) is obtained by eliminating the salt ion concentrations n ± as variables; thus the ζ-potential accounts for well-known composition of the electric-double layer. The parameters α and S depend on the nonuniform salinity and the surface charges related to the Seebeck thermopotential. This reduction is achieved by solving the diffusion equation for thermally driven ion currents and by replacing ∇n ± with their stationary values [4,38]. This relies in particular on the fact that the salt relaxation times are much shorter than that of the colloidal distribution function. Moreover, at sufficiently small colloidal volume fractions, the back-reaction of the colloidal macro-ions on α and S can be neglected [14].

IV. ELECTROLYTE COMPOSITION

A. Specific-ion effects Fig. 2 shows the Soret coefficient of 215 nm PS beads in a 1 mM solution of NaCl 1-x OH x as a function of the composition parameter x. The data show a linear variation with x; those at 41 • C change of sign at x ≈ 1 2 . These findings are in agreement with previous studies reporting S T > 0 in NaCl and S T < 0 in NaOH [11,13]; a similar linear dependence on composition was reported for SDS micelles in a mixed electrolyte [13]. Moreover, the data at 26 • and 41 • C indicate that the Soret coefficient in NaCl solution increases with temperature.

The only ion-specific quantities in Eq. ( 3) are the Seebeck coefficient S and the thermal diffusion factor α; for a mixed electrolyte we write these quantities as molefraction weighted averages, 3) with ζ = -38 mV, ε = 78ε0, and τ = 1.4; the fit values for the Seebeck coefficient S and thermal diffusion factor α compare favorably with those measured at room temperature by Agar [39]. As discussed below, the temperature dependence of S and α agrees with Eq. ( 5).

S = (1 -x)S NaCl + xS NaOH , α = (1 -x)α NaCl + xα NaOH . (4)
from the numbers given in Table I it is clear that α increases with x, whereas the Seebeck coefficient strongly decreases and changes sign. Moreover, with typical values of the surface potential of less than mV, one finds that the composition dependence of Eq. ( 3) is dominated by the Seebeck term. Since most colloids carry a negative surface charge, one expects quite generally a negative Soret coefficient in NaOH solution.

The fit curves are calculated with constant ζ-potential and the salt parameters given in Table I. We have neglected various additional dependencies, such as the well known variation of the ζ-potential with the pH value. Indeed, our measurements (Stabino) show that, depeding on salinity, ζ varies by about 10 to 30 percent upon replacing NaCl with NaOH. Including this dependence in the fits would merely modify the parameters S and α, but not affect our conclusions.

B. Salinity

In Fig. 3 we plot the Soret coefficient in NaCl solution as a function of the salinity n 0 . First S T increases with n 0 , attains a maximum at about 5 mM, and then drops to small values beyond the resolution of our experiment. The behavior between 10 and 100 mM arises from the variation of the surface potential with salinity in the framework of Debye-Hückel approximation, ζ ∝ n -1/2 0 . This law ceases to be valid at lower salinity, as is wellknown from electrophoresis [42].

As a possible mechanisms for the dependence at low electrolyte strength, and in particular for the occurrence of a maximum, we mention the surface conductivity contribution, similar to well-known reduction of the electrophoretic mobility [42]. On the other hand, there are several effects specific for thermophoresis that have hardly been investigated so far, such as the collective thermoelectric effect [14], or the fact that the coefficients S and α depend significantly on salinity [40].

In moderate or weak electrolytes, there is no satisfactory model for the surface potential and its subtle dependencies on pH, temperature, and salinity. In order

N a A = (Q * N a + Q * A )/2k B T and SN a A = (kB/e)(Q * N a -Q * A )/2kBT
. The fit values are used for the theory curves in Fig. 2. These values agree with the linear temperature dependence for NaCl solutions given in Eq. (5). for the Seebeck term and the remainder, respectively; this agrees at least qualitatively with the data. Yet these laws cease to be valid at lower salinity; our data, and in particular the occurrence of a maximum, are similar to the well-known behavior of the electrophoretic mobility, which is to large extent determined by the salinity dependence of the ζ-potential [42].

α N a C l α N a O H S N a C l (µV/K) S N a O H (µV/K) exp 25
to account for the variation of S T with salinity, we take in all fits ζ = -38 mV at 1 mM, ζ = -53 mV at 5 mM, and ζ = -6.5 mV at 100 mM. The value at 5 mM agrees with the measured ζ-potential over the temperature range studied here; those at 1 and 100 mM are in accord with Fig. 3 and more generally with electrophoretic mobility data.

V. TEMPERATURE DEPENDENCE

Soret data for various colloids show a strong and surprisingly universal temperature dependence [22][23][24][25][26][27].

Here we present data for both NaCl and NaOH solutions that are essential for the main results of this paper.

A. NaCl solution

According to Fig. 3, the Soret coefficient of polystyrene particles vanishes at high salinity. In order to determine whether this is the case at all temperatures, we plot in Fig. 4 Soret data measured at different electrolyte strength as a function of T . The main features are a roughly linear variation with temperature, a strong reduction upon increasing the electrolyte strength, and a 3) with ζ = -53 mV at 5 mM and -6.5 mV at 100 mM; we assume a linear variation of S and α according to Eq. ( 5), with values at 25 • C from Table I. linear increase with the particle size. These findings lead us to two main conclusions of the present work.

First, the Soret effect of 215 nm beads in 5 mM NaCl is almost ten times stronger than in 100 mM solution, and this over the range from 25 • C to 50 • C. This uniform reduction provides strong evidence that thermophoresis of polystryene beads arises from charge effects only. They exclude the existence of a significant non-ionic contribution to S T ; the values in 100 mM solution may be taken as an upper bound. In contrast to our results, the Soret effect of proteins arises essentially from a non-ionic mechanism, as shown by a study on lysozyme at variable eletrolyte strength and temperature [22]. This implies that thermophoresis of PS beads differs fundamentally from that of proteins.

Second, the Soret coefficient at 46 • C is about twice as large as at 26 • C. Since the overall prefactor in (3), and the parameters ζ, ε, and τ, hardly vary with temperature, we conclude that the T -dependence of S T is necessarily related to the Seebeck coefficient S and the thermal diffusion factor α of the salt solution. Moreover, the data confirm the well-known fact that the Soret coefficient is proportional to the particle size [4,33]. The temperature dependence qualtitatively agrees with previous studies on PS beads [23,26].

In order to make the above arguments more quantitative, we have fitted the temperature dependence in terms of a minimal model for the Seebeck coefficient and the thermal diffusion factor,

S NaCl = S 0 NaCl (1 + ξt) , α NaCl = α 0 NaCl (1 + ξt) , (5)
where t = T -298K and the superscript "0" indicates room-temperature values according to Table I. The straight lines in Fig. 4 are calculated from Eq. ( 3) with the slope parameter ξ = 0.14 K -1 . There seem to be no data on the T -dependence of the Seebeck coefficient. The slope measured for the thermal diffusion coefficient α of very strong electrolytes of about 1 M, is about four times smaller [40]; at low salinity a stronger but non-linear increase of α was observed [41]. These experimental findings are compatible with the model ( 5) and the value for ξ.

B. NaOH solution

In Fig. 5 we plot the Soret coefficient of PS beads of different size in NaOH solution between 40 • and 55 • C. In this range S T varies little with temperature. The curves are calculated from Eq. ( 3) with ζ = -38 mV and constant values for S NaOH and α NaOH , as given in Table I. The data for beads of 90, 136, and 215 nm diameter follow roughly the linear size dependence of Eq. (3); the slight discrepancy might be related to the surfactantfree surface, and thus slightly higher ζ-potential, of the homemade 90 and 136 nm sample, in contrast with the commercial 215 nm beads.

As a corollary, we note that our discussion of the data of Figs. 4 and5 implies that solutions of NaCl and NaOH strongly differ in their thermal diffusion behavior. The strong temperature dependence of Fig. 4 is related to the variation of the coefficients in Eq. ( 5), which are qualitatively confirmed by experiment [40,41]. The data of Fig. 5 suggest that S NaOH and α NaOH do not depend on T ; we are not aware of an experimental study on this point.

The coefficients S and α result from the heat of trans-port Q ± , which in turn are given by the ionic solvation enthalpy [39,43]. Besides the electrostatic self-energy, these latter quantities comprise van der Waals and hydration contributions which are not easily evaluated. In the view of the well-known specific ion effects, as expressed for example in the Hofmeister series for protein solutions [44], it would not come as a surprise that NaCl and NaOH strongly differ in their solvation enthalpies.

VI. DISCUSSION

Together with Eq. ( 3) the data presented in the above figures show that the Soret effect of PS beads originates essentially from thermal diffusion of the salt and the electrolyte Seebeck effect, thus confirming previous works [11,13]. As a most important novel finding, our data show moreover that the Seebeck effect and diffusiophoresis in the salt gradient lead to the strong temperature dependence in NaCl solution. Although the variation with T is similar to the behavior observed for various ionic and non-ionic colloidal suspensions [26], our measurements give clear evidence that there are two distinct mechanisms at work: Whereas a study on lysozyme protein shows that the temperature dependence of the Soret data results from a non-ionic interaction [22], the present work indicates that charge effects are dominant for polystyrene beads.

So far all experimental studies reported an increase with temperature, which is generally well fitted by the Piazza's phenomenological law S T = S ∞ T (1 -e (T * -T )/T 0 )

that changes sign at T = T * ; extrapolating our NaCl data gives T * ≈ 15 • C which roughly agrees with the values of [23,26]. On the other hand, the data in NaOH solution presented in Fig. 5 provide the first example for a T -independent Soret coefficient. This finding enforces our above statement that the Soret motion of PS beads is a charge effect and thus has a strikingly different temperature dependence. There remains the question why the non-ionic mechanism at work in protein and micellar solutions and the charge mechanism of latex particles in NaCl solution, show such a similar temperature dependence. Piazza and coworkers pointed out that the non-ionic interaction is strongly correlated with the thermal expansivity β of water [26]. On the other hand, a similar correlation is known to occur between the thermal diffusion factor α NaCl of sodium chloride and β [40]. The data of Fig. 4 suggest that there is a similar relation between the electrolyte Seebeck coefficient S NaCl and the expansivity of water. In this picture, the thermal expansion of water would be at the origin of the temperature dependence of Soret data for non-ionic polymer solutions, proteins, and charged PS particles. By contrast, the data of Fig. 5 indicate a very different behavior of NaOH solution. The physical origin of such ion-specific effects [18,19] could be related to the Hofmeister effect observed for protein solutions.

FIG. 2 :

 2 FIG.2: Soret coefficient of 215 nm PS beads in a mixed electrolyte NaCl 1-x OH x . The data at 41 • C (circles) show a linear dependence on x, and a change of sign at x ≈ 1 2 ; those at 26 • C (squares) indicate that in NaCl solution, ST strongly increases with temperature. The solid lines are calculated from Eq. (3) with ζ = -38 mV, ε = 78ε0, and τ = 1.4; the fit values for the Seebeck coefficient S and thermal diffusion factor α compare favorably with those measured at room temperature by Agar[39]. As discussed below, the temperature dependence of S and α agrees with Eq. (5).

FIG. 3 :

 3 FIG. 3: Soret coefficient of 215 nm PS beads in NaCl solution as a function of the electrolyte strength at TC = 299K with ∆T = 15 K. For high salinity, n 0 > 10 mM, inserting the Debye-Hückel law ζ ∝ n -1/2 0 in (3) gives ST ∝ n -1/2 0 and ∝ n -1 0

FIG. 4 :

 4 FIG.4: Soret coefficient in NaCl solution as a function of temperature. The solid lines are calculated from (3) with ζ = -53 mV at 5 mM and -6.5 mV at 100 mM; we assume a linear variation of S and α according to Eq. (5), with values at 25 • C from TableI.

FIG. 5 :

 5 FIG. 5: Soret coefficient of PS beads in NaOH solution. The electrolyte thermal diffusion Seebeck coefficients α and S are kept constant; the slight temperature dependence arises from the prefactor in (3).

TABLE I :

 I Seebeck coefficient S and thermal diffusion factor α of dilute solutions of NaCl and NaOH. The experimental values are determined from the heats of transport Q *

	N a =3.5 O H =17.2 kJ/mole, measured C l =0.5 kJ/mole, Q * kJ/mole, Q *
	by Agar [39], according to α

Acknowledgment.

A.W. acknowledges support through the Leibniz program of Universität Leipzig during the summer term 2013, and thanks the groups of Frank Cichos and Klaus Kroy for their kind hospitality.


Pascal Cuxac
email: pascal.cuxac@inist.fr

Alain Lelu
email: alain.lelu@univ-fcomte.fr

Martine Cadot
email: martine.cadot@loria.fr

Paving the way for next generation data-stream clustering: towards a unique and statistically valid cluster structure at any time step

Keywords: data-stream clustering, text mining, incremental algorithm, randomisation test, density mode clustering, graph validation, data mining

Introduction

In the field of analysis of scientific and technical information (Suerdem and Karabekir, 2010), tracking how a particular scientific field evolves thematically remains a major subject for study. Let us first consider the interest of taking the time factor into account for a clustering task. Amongst other things, clustering (or unsupervised classification) makes up data groups without requiring prior knowledge. If these data groups are scientific publications as in the case we propose to study and if we consider the corpus of bibliographic records taken as our starting point is representative of a given field, then the clusters can be viewed as research themes in that field of study. The classification that is obtained gives an overview of the scientific field being studied but this overview is static insofar as it is a 'picture' at one given moment. Obviously different classifications can be made at different moments but then the problem is how to efficiently differentiate, when considering the two sets of classification results, between real changes and representational artefacts caused by the method. Indeed, this issue is not the major concern of today's data stream clustering methods, as these are primarily focused on saving storage space when processing huge data flows. Taking the time parameter directly into account when defining the method of clustering means that we can 1 evaluate the evolution and changes in a given scientific field 2 detect novelty in such a data flow.

Of course this permits the clustering of any continuous data flow (news reports, speech recognition, image analysis, web, etc.) or multiple time series analysis.

First however we shall define what we mean by an 'incremental algorithm'. The word 'incremental' is often associated with terms like 'dynamic, adaptive, interactive, online, batch, etc. [START_REF] Memmi | Incremental clustering and category drift[END_REF] uses the expression incremental (or dynamic) algorithm 'when new data can be processed without having to reconsider all of the data. The algorithm will be completely incremental if it updates previous results if necessary'. He also adds an important remark namely that "the data needs to be in the form of a vector within the same vector space. If the dimensions of that space are modified, the problem becomes more complicated". [START_REF] Mfoumoune | Les Aspects Algorithmiques de la Classification Ascendante Pyramidale et Incrémentale[END_REF] defines an incremental algorithm as corresponding to the three following points:

• that it should be possible to apply it without prior knowledge of all the elements to be classified • the classification of a new element should be carried out without intensive usage being made of elements that have already been classified (otherwise all methods become incremental in adding the new element to the original set and re-applying the method to the whole set) • the result should be available after the new element has been inserted.

To complete this definition, we will add a wish list we consider that a fully satisfactory unsupervised and incremental classification should fulfil in the long term:

• stable representations which are independent of the order data are entered and of the initial conditions • grouped vectors: it should 'self-adapt' to the considerable density differences noted in the spaces of descriptors • possibility of overlapping clusters

• open descriptive universe: the appearance of new descriptors at t+1 must not modify the vector structure that existed at t • it should extract very small clusters, even isolated individual elements: 'the core of future clusters?' • it should have the minimum number of parameters.

We will present first a state of the art, showing that no method fulfils, to our knowledge, the ambitious wish list we have set out. In Section 3 we will recall our rigorous incremental clustering method Germen, which relies on the local updating of an inter-document similarity graph at each time step, i.e., when a new document-vector is processed. We will develop two methods for defining such a graph: a classical method that we have used so far, that has proved disappointing on real-world datasets, which consists in linking each text document to its k-nearest neighbours (KNNs); and our novel Monte Carlo method for identifying statistically valid links by a randomisation test. In Sections 4 and 5, we will show the clear superiority of the latter, whether from a qualitative standpoint of intelligibility by an expert, or from the quantitative standpoint of a more balanced distribution of documents in the clusters, as far as our own bibliographic dataset is concerned; and concerning our chosen Reuters' test corpus, it is to be noted that our agreement measure between the Reuters' categories of document pairs and their link structure was good, despite the problematic interpretability of each cluster, a consequence of the poor indexing quality available in this newswire corpus.

We will not present examples of dynamic evolution of these real-world corpora, as visually representing numerous document flows in a complex lattice of clusters -loosing/gaining documents, splitting, merging or emerging -is a difficult representation problem, standing out as a man-machine interface issue and quite distinct from the one addressed here, an issue that will be tackled per se in a future paper. Though time and space efficiency are not the points we intend to challenge against other algorithms at the present time, we will briefly evoke and discuss them: recall that we want a unique and intelligible cluster structure for a given document set, whatever the order of the documents and independent from any initial conditions, a strong condition not even satisfied by most of the static batch clustering methods.

State of the art

When discussing incremental clustering and data flows, it is impossible to ignore the subject of Datastream even if our data and main concerns are different.

A quick overview

Data Stream Mining has been has been an active research field in the USA since the end of the 1990s but remains in its starting phase in France. Its aim is to process data flows whose limits may be infinite (e.g., electricity consumption profiles) in one go. "Obtaining access to entire data sets can become a problem, if not actually impossible. Access to data is strictly sequential and the amount of memory available is very much inferior to the volume of data from the flow" [START_REF] Hébrail | Atelier Gestion et fouille de flux de données[END_REF].

In the USA, the TDT research programme (topic detection and tracking) set up by the Defense Advanced Research Projects Agency (DARPA) in 1996 led to the development of event detection technologies (Wayne, 1998) which focus on computing efficiency in processing flows of tens or hundreds of thousands of news reports or records from data archives or the internet. The methods developed permit the detection of broad trends from large data flows (Wan et al., 2009) but nonetheless are not reliable for detecting more subtle trends or 'weak signals '. Cahlik (2000) compared clustering results obtained at different periods in time. The analysis based on co-words and on co-citations was carried out using the Lexidyn programme; he obtained a method for visualising results which shows the way clusters evolved. However this approach remains relatively rudimentary, difficult to interpret and based on a straightforward document count.

Adapting methods with mobile centres to incrementality

Partitional methods which use aggregation around shifting centres, such as K-means and their many variants, are part of a family based on the optimisation of an overall numerical indicator of the quality of the partition (Yu et al., 2010), in which methods involving mixtures of explicit probabilistic laws are included, which uses the EM (Expectation Maximisation) procedure -for a review see [START_REF] Buntine | Variational extensions to EM and multinomial PCA[END_REF]. The problem of optimisation is NP-hard, they can only be made to converge towards a local optimum which depends on their initialisation (for example the initial positions of centres randomly generated or picked out from the data) or on the order of the data. This disqualified them because we set the proviso that the results should be independent from the initial conditions -our method of axial K-means [START_REF] Lelu | Clusters and factors: neural algorithms for a novel representation of huge and highly multidimensional data sets[END_REF] is part of this family; the local optima for a given number of clusters mostly reveal the same main clusters which are often trivial but can also make the most interesting ones of average or low size appear/disappear/amalgamate or split. Quite a lot of incremental variants of these methods have been proposed [START_REF] Binztock | Un algorithme en ligne pour la détection de nouveauté dans un flux de documents[END_REF][START_REF] Chen | Life cycle modeling of news events using aging theory[END_REF] and a partial review of these can be found in [START_REF] Lin | Data mining and knowledge discovery -Iterative incremental clustering of time series[END_REF]. Many come from the DARPA-TDT research programme such as [START_REF] Gaudin | Apprentissage non-supervise de séries temporelles à l'aide des k-Means et d'une nouvelle méthode d'agrégation de séries[END_REF], [START_REF] Gaber | Mining data streams: a review[END_REF]. The characteristics of these methods which make them incompatible with our criteria are 1 it is necessary to define the number of clusters in advance 2 their level of sensitivity to initialisation seeds 3 they are unable to detect 'emerging trends'.

Neural models

Incremental variants of neural models such as ART, CLASSPHERES, IGNG [START_REF] Aguilar | Incremental ART: a neural network system for recognition by incremental feature extraction[END_REF][START_REF] Puzenat | Priming an Artificial Neural Classifier[END_REF][START_REF] Prudent | Extraction incrémentale de la topologie des Données[END_REF]) have been developed. Problems have occurred however linked to initialisation, to their high number of parameters and calculation time. According to [START_REF] Memmi | Incremental clustering and category drift[END_REF] these are adaptations of neural models rather than real incremental methods. Nonetheless we will discuss those methods based on growing neural gas (GNG) later in this paper.

Hierarchical clustering

A few hierarchical methods such as JERARTOP, COBWEB or CURE [START_REF] Pons-Porrata | JERARTOP: A new topic detection system[END_REF][START_REF] Fisher | Knowledge acquisition via incremental conceptual clustering[END_REF][START_REF] Guha | CURE: an efficient clustering algorithm for large databases[END_REF] are well-adapted to incrementality. These are divisive or agglomerative methods which are often user-friendly and efficient and which results are independent of the order of presentation of the data and of the initial conditions. However they lack robustness when faced with minor disturbances due to similar distances between data-vectors -and, given the quality of the partitions obtained at a given level of the tree, there tends to be a consensus view that prefers to them methods based on mobile centres [START_REF] Lebart | Techniques de la Description Statistique[END_REF].

Most promising methods

Our overview study leads us to conclude that biomimetic methods, density methods and those methods based on GNG are eligible to become incremental.

Biomimetic algorithms

We place in this category evolutionary algorithms (genetic algorithms, evolution strategies etc.), intelligent swarms (Swarm intelligence: clouds of flying insects, artificial ants, etc.) and immune systems [START_REF] Lee | Dynamic partitional clustering using evolution strategies[END_REF][START_REF] Monmarché | Classification et visualisation dynamique de données par nuage d'insectes volants[END_REF].

Azzag points out that "very few incremental biomimetic methods exist even though incrementality is possible in many algorithms. The main advantage of some of these methods (ants, swarm, SI) is that they can provide simultaneously a clustering and a means of visualising of that clustering" [START_REF] Azzag | Un survol des algorithmes biomimétiques pour la classification[END_REF].

Until now, cellular automata have not really been used to a great extent for clustering. [START_REF] Azzag | Classification de données par automate cellulaire[END_REF] and [START_REF] Lavergne | Construction incrémentale et visualisation de graphes de voisinage par des fourmis artificielles', 7èmes journées d'Extraction et Gestion des Connaissances[END_REF] propose an algorithm which uses them to solve a clustering problem, the aim being to obtain a 'visual' result permitting direct exploration of the clusters and possibly to visualise other information (images). This algorithm must be modified to make the clustering overlapping, incremental, and unique whatever the initial conditions.

Neural models

GNG also seems a possible solution for our problem. The main idea behind this method is to successively add new neurons to a network that is initially made up of two connected neurons, thanks to a local analysis of an 'error' parameter generated by the preceding data.

This network is characterised by dynamic management of the neurons, based on a competitive principle which adds or deletes neurons and connections. However initialisation remains random. We are thus faced with a 'plasticity/stability' dilemma -can a GNG network learn new data without using the data it learnt before and without deterioration of the network that has already been generated? An incremental GNG was developed [START_REF] Prudent | Extraction incrémentale de la topologie des Données[END_REF]) and improved by [START_REF] Hamza | An end-to-end administrative document analysis system[END_REF]. It allows data to be learnt in parts if the database is too large to be learnt in one go and thus allows the learning process to be restarted even if the data learnt previously is no longer accessible. But the uniqueness of the representation at any time step has not yet been established.

Density methods

These methods define clusters using the notion of the density of a data-cloud. This notion of density involves the proximity of one point to another, the proximity being defined by a distance threshold or a number of the nearest neighbours. Given 1 a multidimensional cloud of points 2 a definition of the density related to each point in that space 3 the value of the scale parameter of this density function (its 'influence radius'), then the resulting density landscape is unique and perfectly well-defined.

Tremolières (1979) proposed a general 'percolation' algorithm which is independent of the definition of density or the type of data involved. It aims to rigorously define cluster nuclei, ambivalent frontier-points and atypical points, and works by progressively lowering the density level starting from the densest point and spreading around the nuclei which successively appear. Other works in this field use the same principle of finding dense cores, each usually also with a specific definition of density and various types of extensions around dense cores: [START_REF] Moody | Identifying dense clusters in large networks[END_REF][START_REF] Guénoche | Clustering by vertex density in a graph[END_REF][START_REF] Hader | Efficient density clustering using basin spanning trees[END_REF][START_REF] Batagelj | An o(m) Algorithm for Cores Decomposition of Networks[END_REF]. It should be noted that these methods can be translated in terms of graph partitioning, because defining density implies that neighbouring relations be defined, thus a graph. Density Based Spatial Clustering with Noise (DBSCN), described in [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] uses a definition of density using two parameters, one of which specifies the threshold at which cores begin to form and then spread. We also need to bear in mind developments such as of Chameleon [START_REF] Karypis | Chameleon: A Hierarchical Clustering Algorithm using Dynamic Modeling[END_REF], OPTICS [START_REF] Ankerst | OPTICS: ordering points to identify the clustering structure[END_REF]; DENCLUE [START_REF] Hinneburg | An efficient approach to clustering in large multimedia databases with noise[END_REF]. These algorithms were not to our knowledge considered in a dynamic perspective of incrementality.

In the field of self-organising protocols for so-called 'ad-hoc' radio-communication networks, the theme of incrementality for the dynamic partitioning of evolving graphs has been dealt with more directly (e.g., [START_REF] Mitton | Auto-stabilisation dans les réseaux ad hoc[END_REF] though with different application aims from our own. In these protocols, the locational neighbourhoods may fluctuate at each time step, without necessarily including entrances or exits from the network, and the aim is to achieve a relative stability of the composition of the clusters (these are crisp partitions) and stabilise the identity of the nuclei (clusterheads) rather than to attain optimality. Here we are interested by the principle of a completely distributed algorithm for which the knowledge each unit to be classified has of its neighbours and its neighbours' neighbours (2-neighbourhood) at time t is sufficient to permit the definition of the existence and distribution of the resulting clusters at any moment.

Our solution: the GERMEN algorithm

We have worked out the principle of density methods and developed an algorithm named GERMEN [START_REF] Lelu | Classification dynamique d'un flux documentaire: une évaluation statique préalable de l'algorithme GERMEN[END_REF]. The underlying principle of this method is to localise the 'mounds' in the density landscape of the data at each moment t and then to identify any local disturbances in this landscape caused by any document that comes at time t + 1, along with all resulting modifications of the cluster borders.

The documents to be classified are described by their keywords and are organised in the form of a graph where each node represents a document and where the edges represent the links between documents. The way this graph is partitioned can be viewed 1 as spotting the main nuclei nodes, the 'clusterheads', which are locally denser than their surroundings 2 as the extension of their zone of influence by unique or shared linking (simple or multiple 'heritage') with their neighbours further and further away.

The way the algorithm runs permits the progressive construction of a structure of data including the following for each node -its density, its clusterhead number(s) and finally the list of its 2-neighbours. This data is updated constantly; when a new document (node) arrives, the changes to the density that are caused in its neighbourhood are calculated along with any changes to the clusterheads that may occur. The pseudo-code of our algorithm is listed below.

In the first phase of our project, we used a bibliographic test corpus from the PASCAL database (http://www.inist.fr). This corpus consists of 1,541 bibliographic records in the field of geotechnics published in 2003 which index documents such as articles, conference papers or theses. We used the manually-entered indexing keywords in the records to carry out the clustering. We tested two different methods for the weighted graph of links between documents -the 'KNN' oriented graph and the TourneBool [START_REF] Cadot | Extraire et Valider les Relations Complexes en Sciences Humaines: Statistique, Motifs et Règles d'Association[END_REF] method resulting in an unoriented graph.

GERMEN pseudo-code

• Initialisation: the first node in the sequence has no link, has a 0 density and is its own clusterhead.

LCC = Ø // LCC is the list of clusterhead lists for each node //

• FOR each new node :

// induced changes for densities: // • compute its 1-et 2-neighbourhood (income and outcome), and other induced neighbourhood modifications, from which follows the list LL of the nodes concerned by a link creation / suppr. / modif.

• compute its density from its 1-neighbourhood.

• FOR each LL node, and any node in its 1-neighbourhood:

-compute the new density value

KNNs graph

To measure the links, we chose to use the cosine in the distributional space [START_REF] Lelu | Evaluation de trois mesures de similarité utilisées en sciences de l'information[END_REF], a measure linked to the Hellinger distance [START_REF] Domengès | Analyse factorielle sphérique: une exploration[END_REF] where x t is the sum of the components x it of vector X t .

Worthwhile characteristics follow, particularly:

• Distributional equivalence (the representation remains unvaried insofar as the fusion of descriptors with the same relative profiles is concerned).

• Incrementality: the normalisation of the document-vectors avoids the arrival of a new document disturbing the similarities that have already been calculated. Also the generally 'sparse' nature of these vectors permits the incrementality of the descriptors. The number of dimensions of the descriptor space can increase progressively as new descriptors (terms for example) are found in the documents.

• The extension to negative data is straightforward.

The graph of linked documents is constructed using the KNN method where K is set by the user.

TourneBool randomisation test for pruning the less robust links

In our application, we analyse the documents × keywords Boolean matrix. The link computed between two documents is the number of words that occur in both documents, which is also known as 'support'. This can be obtained by calculating the dot product between two document-vectors. First of all, the links that exist through pure chance are eliminated by our TourneBool randomisation test [START_REF] Cadot | Extraire et Valider les Relations Complexes en Sciences Humaines: Statistique, Motifs et Règles d'Association[END_REF][START_REF] Cadot | Random simulations of a datatable for efficiently mining reliable and non-redundant itemsets[END_REF], then those which are too weak are eliminated by our MIDOVA [START_REF] Cadot | A novel decomposition algorithm for binary datatables: encouraging results on discrimination tasks[END_REF] hierarchical stepwise procedure. TourneBool is a statistical validation algorithm which works on a Boolean data matrix. It first randomly generates several hundred Boolean matrices S-equivalent (i.e., with equal marginal sums) to the data Boolean matrix and then it searches for pairs of data which appear to have a link not due to chance.

Table 1

The contingency table of pair (Di, Dj): N, the total number of keywords; Mij, the support; Mi and Mj, the respective numbers of keywords of documents Di and Dj.

Di Non-Di

∑ Dj a = Mij b = Mj -Mij Mj Non-Dj c = Mi -Mij d = N + Mij -Mi -Mj N -Mj ∑ Mi N -Mi N
For each pair of documents (Di, Dj) with a non-null Mij support in the original data, we calculated this support in each of the simulated matrices and thus obtained the support distribution for this pair in the event of there being no link. If the reference Mij is higher than 99% of the Mij's in the distribution then the link is named significative with a risk of less than 1% of being wrong (alpha-risk). The other values are considered as being caused by chance. Once the uninteresting links were eliminated by TourneBool, we filtered the remaining links between documents and kept just the most important ones for classification. For this, we based our work on the calculation of the MIDOVA indicator.

In Table 1, let us consider the following link between two documents, Di and Dj, a gain is determined according to the position of Mij in relation to the 'null hypothesis value' 1 Cij of the [M inf ; M sup ] interval, with M inf = a -min(a, c) and M sup = a + min(b, c). Taking Gij = 2(Mij -Cij) to be the gain value, a zero gain is obtained when Mij is in the median part of the interval and extreme values are obtained when it is at its limits.

In order to only keep the most significant links, we experimented by using a confidence interval of 99.9% with TourneBool to validate the links.

Time complexity

Germen main module

Depending on the data, the processing time for the Nth data-vector varies between a maximum of O(N 2 ) and a O(N) minimum, attained beyond N ~ 1,000-5,000; our experience so far shows that, when a new document-vector is introduced then, the 'disturbed zone' of the data landscape does not exceed 200 to 500 documents, whatever N, which induces a roughly constant updating time in this part of the program (the similarity computation stays O(N)).

TourneBool module

Technically, the experiments described below show that we implemented an adequate scale shift to process text corpora of realistic size. Randomised matrices are generated in time O(n, m, v) and space O(v) where n and m are the numbers of lines and columns of the test matrix, v is its number of non-zero values. This phase is made up of independent processes and can run in parallel in a natural manner. To avoid any problems with memory limits in the following exploitation phase of N matrices (e.g., stocking 100, 200 or 2,000 times v numbers and so forth), we fragmented this phase into independent parallel processes each of which processed a fragment of the (symmetrical) table of the co-occurrences. Processing the Reuters corpus we will describe below (23,000 news reports, 28,000 words) took around two and half days of computing for all these phases which were broken down into three parallel runs on a standard quad-core PC. It should be noted that once the distribution of the words and documents have been stabilised, the TourneBool test can be run without requiring a reiteration of all the simulations, e.g., every 1,000 to 10,000 data-vector inputs.

Of course these performances do not match the requirements for flows of millions data-vectors or more, but they are encouraging for the applications we aim at, like scientometric ones, rarely involving more than tens to hundreds thousands documentvectors.

Results obtained using the Geotechnical corpus

GERMEN runs based on KNN graphs

The results obtained using the K nearest neighbour method to create the graph of links between documents was disappointing. Using a low K value (i.e., 1 to 3), we obtained a very high number of clusters (around 450) in relation to the size of the corpus (1,541 documents). When we increased the K value, a chaining effect led to a reduced number of clusters but with a small number of very large 'catch-all' clusters (Figure 1). Generally we found a lot of small clusters and isolated individual documents. Figure 2 shows the result obtained using K = 3 -there are 448 clusters covering the 1,541 documents and 203 single-unit clusters (those with just one document, 13% of the classified documents). It should be noted that the repartition of data on this oriented graph was obtained by weighting the link between two documents as inversely proportional to the distance calculated between the two documents. 123456789 1 0 1 1 1 2 1 3 1 4 1 9 2 0 2 1 2 2 2 3 3 0 4 6 6 2 6 8

Size of classes

Number of classes

Table 2 shows how the number of links drastically increases when K increases slightly. The total degree for a node (i.e., a document) on the graph may thus be doubled. The expert view is that a number of the very small clusters should be merged and sometimes even merged with bigger clusters. Conversely, the big clusters cover documents with very different subjects.

GERMEN runs based on TourneBool graphs (MIDOVA-weighted)

The results obtained using the TourneBool validation method are promising. Starting with the calculated network of links between documents obtained by this method, we have applied a modified Germen density clustering to process this unoriented graph. The results of the first experiments using this method are encouraging because we found a lot of clusters that were validated by the expert in the field. For this graph, the weight of the links was simply defined by the proportion between the number of descriptors two documents had in common and the maximum total of possible common descriptors. By varying the filtering threshold and keeping only those links whose value is greater than or equal to this threshold, we can thus obtain cluster structures with varying degrees of granularity.

We also carried out a clustering by attributing a value of 1 to all the links and obtained 4 clusters covering not more than 60% of the documents! This clearly shows how important it is to choose correctly the weights attributed to the links.

By using the 'MIDOVA' method for weighting the links, we obtained more relevant and useful clusters but the larger clusters remained poorly defined (Figure 3). Table 3 compares the number of clusters obtained and the documents in those clusters with two confidence intervals. For a threshold of 1 we obtained ten clusters and missed very few documents. In fact the documents that are not taken into account are those that are alone in a cluster of their own. These ten clusters that can be well interpreted are summed up in Table 4. The main keywords for these clusters are relevant and correspond well to the titles that can be found manually in this kind of corpus. However, again it should be noted that the result is not perfect. For example, there are three very large clusters which it would be better to break down more.

Validation test with a public test corpus

The Reuters news agency [START_REF] Lewis | A new benchmark collection for text categorization research[END_REF] made several corpora of news reports available for the data mining community to enable the researchers to compare between work carried out and methods employed analysing a common public database. We used the lyrl2004_tokens_train.dat corpus 2 of 23,149 news reports pre-lemmatised using the Brill tool in order to concentrate our attention on the exploitation of a published vocabulary without a specific indexing or filtering process which might have affected the results, even if that process might have resulted in higher quality indexing (here the lemmas consist of simple truncations of words, which limits the vocabulary to a few tens of thousands of terms but also leads to many cases of semantic ambiguity for the English words in the general vocabulary and to forms that are hard to understand). Finding multiword phrases with more univocal meanings was out of the question as well.

After the hapax legomena (words with occurrence of 1 in the whole corpus) had been eliminated, the vocabulary consisted of 28,450 lemmas (from a0 to zywnociowej) with around 75 unique lemmas per news report. The distribution of word occurrences had the usual Zipfian allure (in log-log coordinates: linear decrease), i.e. a power law with an exponent of around -1.5. The distribution of the number of unique words in the news reports showed a clear maximum of around 26 words and was highly unsymmetrical. To decrease computation time, we extracted 2000 documents from those which had more than two Reuters category codes. This was intended to reduce the coverage of the clusters and thus permit easier interpretation of the results. This sub-corpus was found to be indexed by a total of 13,598 words and included 51 category codes. After extraction of valid links using a 99.9% confidence interval, the clustering obtained by Germen gave disappointing results: the overall f-score (the harmonic mean of precision and recall) was hardly better than the result obtained by picking the clusters by chance. Figure 4 shows the distributions of our cluster sizes. These results were obtained using the TourneBool method and the Germen algorithm with three different thresholds for the links. The distribution of the original Reuters categories is also shown for comparison.

We found the same problems as those explained above -very big clusters and a lot of very small ones. For S2, we obtained 76 clusters and 1,210 clustered documents (around just 60% of the documents). In all our tests, it is difficult to find a comparison between the results and the original partition. We consider the problem stems from the indexation of these records.

This corpus has been used successfully for supervised learning tasks but was thus shown to be unsuited to a clustering task if the standard keywords provided are used. The records would probably require re-indexing but then the problem posed would be to define whether we were evaluating the indexing method or the clustering method, and we preferred to avoid this particular problem. This corpus is most probably suitable for supervised learning tasks because in the vocabulary as a whole there are words of the 'named entity' type which the lemmatisation process does not affect to a great extent and which are strongly linked to Reuters' own categories (companies, products, politicians, sports personalities, places etc.) while the other lemmas happen to be unused without any other damage done.

To conduct a full-scale test for our TourneBool software, we used our TourneBool method to extract the adjacency matrix of the graph of the links between the 28,450 lemmas with a confidence threshold of 99%. This graph was made up of 2.8 million links and its density was 0.0071. In comparison, the density of the matrix of the raw co-occurrences of the words is much higher (0.0406).

For carrying out a comparison with Germen, we tried the WalkTrap 3 graph clustering software tool. This program provides a classification tree in ascending hierarchical order which we cut for the maximum value of the quality indicator of the partition (the modularity). We obtained 21 clusters, 13 of which had more than 55 members and two clusters with more than 7,000 members, which is a typical power law breakdown. The content of these clusters is surprising -one contains first names, another one gathers names of towns in the UK but nonetheless in all cases they include a mixture of names of places, people and companies with content elements, i.e. from aeronautics, chemistry or computing and so forth… This rather unconvincing result confirms the result we obtained with the GERMEN clustering and the fact that the indexing material provided was not adapted to the task of clustering.

However, we refined our inquiry so as to know whether these disappointing results were uniformly distributed among all the Reuters categories, or specific of a number of them, while correct for others. As each newswire is attributed one or several thematic categories by the Reuters indexers, the distribution of these 101 overlapping categories is very uneven; the most important one (CCAT: corporate = industrial) involves nearly half of the newswires, and the whole corpus is covered by the only top-five categories. These categories help us to assess the relevance of our links. We look for a quantitative confirmation: It should be desirable that a statistically valid link could correspond to at least one common Reuters category at both side of the link. This idea may be approximated by computing the density of valid links for the complete sub-graph (i.e., clique) corresponding to each category. Actually, while the overall density of the valid links graph is 0.04, the link densities exceed this value for the near-entirety of the classes. They even exceed 0.5 in 19 of them.

Table 5 shows the title of a few such classes in strong agreement with TourneBool links, and the titles of classes in the opposite case. One can verify that the classes in full agreement involve sharp and factual themes in economics and finance, when classes in low agreement are either large, fuzzy themes, such as Corporate = Industrial, or classes dealing with subjects far from economics and finance, such as arts, health, crime, science, foreign affairs,...We suggest the hypothesis that the words of the general journalistic English language are poorly represented and ambiguous when lemmatised, whereas the specific vocabulary and recurrent named entities of the specialised economic and financial stories are more preserved.

Conclusions and future prospects

The present first generation of datastream clustering methods is focused first on space efficiency, second on time efficiency. The next generation will be focused on content issues: is a small cluster, appearing at time t in a bibliographic record flow, a real one, or an artefact? Is cluster X, representative of an important scientific research front, really growing from year t1 to year t2, and decreasing since then? GERMEN, our incremental clustering method is able to cluster data continually as the data arrives (see [START_REF] Lelu | Clustering dynamique d'un flot de données: un algorithme incrémental et optimal de détection des maxima de densité[END_REF] for a comparison of two cluster structures at two time steps). We have shown here that the TourneBool method provides a more interesting graph than the simple K-NN graph because TourneBool is based on statistical validation of each link in the overall context of the database. Computing improvements are possible if a large corpus needs to be processed relatively quickly: moving to a distributed architecture would seem to be the solution (Recall that once the distributions of the words and documents have been stabilised, the TourneBool test can be run without requiring a frequent reiteration of all the simulations).

We have also seen that the value of the links has a very important influence on the result of the clustering. In-depth study needs to be made of different weighting methods and these will be tested on our corpus with the results submitted for expert validation. Detailed study of the inheritance rules is also required because once the clusterhead is defined, these rules spread the cluster to cover other documents, using the clusterhead as a starting-point.

In our experiences, the content of the Geotechnics corpus test was well mastered and the expert in the field was able to rapidly define whether the data classification was relevant and well-adapted or not. However it is more convincing to carry out tests on public test corpora which are used by the scientific community. As the Reuters corpus did not suit the wholeness of our requirements (being more suited to supervised learning), for our following work we will look for better adapted data sets. Nevertheless, we could check that the texts' link graph was in global agreement with the Reuters' predefined categories, with an excellent agreement for about 20% of them, i.e. the most factual and specific ones. We also plan to make our geotechnical corpus publicly available along with a less specialised corpus covering the whole research activities in the Lorraine region of France which we are beginning to study.

One of our aims is to be able to detect weak signals and observe their behaviour over a period of time. In the results presented above (Table 2), we noted 4 very small clusters which still have a meaning within the overall obtained classification. However we would need to move into 'dynamic' mode to verify whether this result may be an interesting clue for future processing. As the corpus is relatively small, it is currently impossible to make a definite conclusion on this as things stand.

Our future work will be broken down into two phases:

• to continue static iterations of our assessment/correction loop on new corpora while testing other variants of our GERMEN clustering method, in order to reach not only a unique representation at each time step, which is the case today, but also a 100% satisfactory and interpretable one, with balanced reasonable clusters.

• to carry out dynamic tests, above all conditioned by ergonomic and design problems of visual presentation of the 'evolution tracks' (cluster births or mergers, deleted clusters, shifting borders etc.): [START_REF] Humbert | La visualisation dynamique de connaissances scientifiques: intégration des besoins des utilisateurs[END_REF].

Suerdem, A.K. and Karabekir, K. (2010) 'Bridging qualitative and quantitative methods for classifying policy actors into policy discourse communities: thematic analysis and formal concept analysis approaches', International Journal of Data Analysis Techniques and Strategies, Vol. 2, No. 3, pp.199-216. Tremolières, R.C. (1979) 'The percolation method for an efficient grouping of data ', Pattern Recognition, Vol. 11, No. 4, pp.255-262. Wan, R., Chen, J., Wang, L. and Su, X. (2009)

  L of nodes akin to change their state is not empty : list LS = Ø FOR each L node, sorted by decreasing density : ~ apply the rule for clusterhead change according to clusterheads of the inbound denser neighbours (in LCC) and their densities.~ if a change occurs:• update LCC for the current node• compute the possible overhanged nodes (overhanged by the current node);• increment the LS list of overhanged nodes.

Figure 1

 1 Figure1Histogram of the number of clusters and the size of the biggest cluster using K

Figure 2

 2 Figure 2 Histogram of the number of clusters sorted by size using K = 3

Figure 3

 3 Figure 3 Graph of the links validated using TourneBool and filtered thanks to MIDOVA (see online version for colours)

Figure 4

 4 Figure 4 Distribution of the cluster sizes at three different threshold values S0, S1, S2, compared to Reuters categories

Table 2

 2 Properties of the two graphs obtained with K-NN

	Tied docs	Number of links	Density (%)	Max in degree	Min in degree	Max out degree	Min out degree	Max tot. degree	Min tot. degree
	Knn k = 3 1,540	6,407	0.54	48	1	17	3	58	3
	Knn k = 7 1,540 19,848	1.67	77	1	51	3	102	4

Table 3

 3 Number of clusters and classed documents obtained

	Confidence		With gain ≥ 0		With gain ≥ 1
	threshold	# of clusters # of documents classed	# of clusters	# of documents classed
	99%	3	1,540	3	1,471
	99.9%	5	1,526	10	1,453

Table 4

 4 The ten clusters obtained and their three most important keywords

	Number of documents	Number of words	Name of the cluster	Major key-words
	258	990	Hydrogeology	Hydrogeology; hydrology; groundwater
	465	1,323	Seismology	Earthquake; seismology; landslide
	2	21	Rock alteration Penetration resistance; alteration; Arenaceous granite
	5	23	Mathematical	Partial differential equation; applied mathematics;
			modelling	incompressible material
	2	9	Road building	Engineer; road network; linear programming
	2	13	Soil exploration Soil exploration; cavity; fault detection
	15	84	Railway networks Railway vehicle; vibration; structural acoustics
	630	1,589	Soil mechanics Gauge factor; sand; clay
	72	316	Tunnels	Excavation; tunnel; stabilisation
	2	34	Tropical soils	Laterite; tropical area; isotherm

Table 5

 5 The top-15 Reuters categories correctly (left) = poorly (right) accounted for by the valid links between texts

	Correctly related categories	Poorly related categories
	C1511: ANNUAL RESULTS	C13 : REGULATION = POLICY
	E121: MONEY SUPPLY	C32 : ADVERTISING = PROMOTION
	E13 : INFLATION = PRICES	CCAT: CORPORATE = INDUSTRIAL
	E131: CONSUMER PRICES	G159: EC GENERAL
	E132: WHOLESALE PRICES	GCAT: GOVERNMENT = SOCIAL
	E14 : CONSUMER FINANCE	GCRIM: CRIME, LAW ENFORCEMENT
	E141: PERSONAL INCOME	GDIP: INTERNATIONAL RELATIONS
	E142: CONSUMER CREDIT	GDIS: DISASTERS AND ACCIDENTS
	E143: RETAIL SALES	GENT: ARTS, CULTURE, ENTERTMT.
	E31 : OUTPUT=CAPACITY	GENV: ENVIRMT., NATURAL WORLD
	E311: INDUSTRIAL PRODUCTION	GHEA: HEALTH
	E513: RESERVES	GODD: HUMAN INTEREST
	E61: HOUSING STARTS	GPOL: DOMESTIC POLITICS
	E71: LEADING INDICATORS	GSCI: SCIENCE AND TECHNOLOGY
	M11: EQUITY MARKETS	GSPO: SPORTS

  'Grid-based clustering over an evolving data stream', Int. J. Data Mining, Modelling and Management, Vol. 1, No. 4,. Wayne, C.L. (1998) 'Topic detection & tracking (TDT), overview & perspective', Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, Lansdowne, Virginia. Yu, L., Gao, L., Wang, D. and Fu, S. (2010) 'Quantitative function for community structure detection', Int. J. Data Mining, Modelling and Management, Vol. 2, No. 4, pp.351-368. Cij = Mi. Mj / N (for more information please refer to Cadot, 2006). 2 Lewis, D. RCV1-v2/LYRL2004: The LYRL2004 Distribution of the RCV1-v2 Text Categorisation Test Collection (12-Apr-2004 Version) available at 3 WalkTrap <www-rp.lip6.fr/~latapy/PP/walktrap.html>.

Notes

1

at each data input, the resulting cluster structure has to be unique, independent of the order the input vectors are presented

this structure has to be meaningful for an expert, e.g., not composed of a huge 'catch-all' cluster in a cloud of tiny specific ones, as is often the case with large sparse data tables.The first preliminary condition is satisfied by our Germen density-mode seeking algorithm, but the relevance of the clusters vis-à-vis expert judgment relies on the definition of a data density, relying itself on the type of graph chosen for embedding the similarities between text inputs. Having already demonstrated the dynamic behaviour of Germen algorithm, we focus here on appending a Monte-Carlo method for extracting statistically valid inter-text links, which looks promising applied both to an excerpt of the Pascal bibliographic database, and to the Reuters-RCV1 news test collection. Though not being a central issue here, the time complexity of our algorithms is eventually discussed.