Dorien Herremans

Elaine Chew

The digital marketplace is rapidly changing the global music industry. Image © Pavel Ignatov | 123rf

of O.R. modeling in the context of the MorpheuS project [30,[START_REF] Herremans | MorpheuS: generating structured music with constrained patterns and tension[END_REF]. For a more complete overview of music generation systems, the reader is referred to [START_REF] Herremans | A Functional Taxonomy of Music Generation Systems[END_REF] [START_REF] Herremans | A Functional Taxonomy of Music Generation Systems[END_REF].

The Digital Music Economy

The digital marketplace is rapidly changing the global music industry. In 2014, the industry's digital revenue increased by 6.9 percent, reaching a total of $6.85 billion [START_REF]Digital Music Report 2015 -Charting the path to sustainable growth[END_REF]. Vast amounts of music-related apps have surfaced for smartphones. These easy-to-use and seemingly simple apps are powered by clever algorithms, often inspired by techniques common to O.R.; cases in point include Shazam and Spotify. In this article, we aim to highlight an up-and-coming area that has only recently gained popularity: automatic music generation.

Automatic music generation serves many purposes. The objective is not to replace composers -the algorithms still rely heavily on human-conceived designs and are nowhere near producing high art music -but serve the purpose of creating changeable music in scalable ways for more mundane recurring scenarios. Imagine a world where small independent video makers can access large amounts of copyright-free and bespoke music for use as background music to their videos, or where a user can generate a novel soundtrack to accompany their vacation photo slideshow for online sharing. What if a computer game could have different and new music that follows the suspense each time the player enters the game? It is scenarios like these that have provided researchers with the motivation for developing methods for automatic music generation.

The idea of automatically composing music existed long before the rst computers were built. In the words of Ada Lovelace, widely regarded to be the world's rst programmer, as she wrote about the general-purpose computing machine: "[The Engine's] operating mechanism might act upon other things besides numbers [...] Supposing, for instance, that the fundamental relations of pitched sounds in the signs of harmony and of musical composition were susceptible of such expressions and adaptations, the engine might compose elaborate and scienti c pieces of music of any degree of complexity or extent." -Lovelace, 1843 [START_REF] Lovelace | Notes by AAL" [Augusta Ada Lovelace[END_REF] Today, several techniques exist for generating music that sounds reasonable at the local scale. The big challenge that the eld faces is that of creating music that possesses long-term structure and large-scale coherence. We believe that looking at music generation as an optimization problem offers a viable framework for solving this problem.

Optimization-Based Approaches to Music Generation

Composing music can be construed as a constraint satisfaction or combinatorial optimization problem. Composers such as Stravinsky have likened the composition process to one of following self-imposed constraints: "My freedom consists in my moving about within the narrow frame that I have assigned myself for each one of my undertakings. ... The more constraints one imposes, the more one frees one's self of The task is then to nd the right combination of notes that best satis es these constraints. But how does one judge if a piece of music is good, or if one solution is better than another? The late music theorist Edward Cone has written that "a good composition manifests its structural principles" and that most music criticism "sets about discovering the standards implied by a given work and testing how well it lives up to them" [START_REF] Cone | Analysis Today[END_REF]. This theory thus offers a way to assess the quality of a composition, but evaluation -how we construct an objective function that effectively measures the quality of music -remains a central challenge in music generation.

Quantifying Music Quality

[4]).

There are three main ways to evaluate a musical piece. The rst is via human evaluation. Arguably the best way to nd out if a piece sounds good is to test it in front of a live audience. Unfortunately, this technique does not scale well and would be impossible to embed in a quantitative algorithm as it would cause huge delay. This problem is often referred to as the human tness bottleneck [START_REF] Biles | Autonomous GenJam: eliminating the tness bottleneck by eliminating tness[END_REF].

Next, we could turn to music theory to obtain a set of rules that de nes what is permissible in a given style. Music generation algorithms that rely on rules focus primarily on counterpoint, a style of music popular in the Renaissance period that has multiple harmonically interdependent voices [START_REF] Herremans | Composing fth species counterpoint music with a variable neighborhood search algorithm[END_REF][START_REF] Phon-Amnuaisuk | The four-part harmonisation problem: a comparison between genetic algorithms and a rule-based system[END_REF]. Counterpoint is one of the most formally de ned musical styles; for most other genres of music, no such well-behaved set of rules exist. A third, more robust technique is to use machine learning to construct the objective function. Since the 1950s, Markov models have been used to capture statistical properties of musical pieces and genres [START_REF] Pinkerton | Information theory and melody[END_REF][START_REF] Brooks | An experiment in musical composition[END_REF]. While these models can capture many aspects and features of music, their traditional sampling methods (e.g., random walk, Gibbs sampling) do not provide a method for generating structure and thus the resulting pieces often lack long-term coherence. More recently there has been interest in using deep neural networks for composition [START_REF] Herremans | Modelling Musical Context with Word2Vec[END_REF][START_REF] Herremans | A Functional Taxonomy of Music Generation Systems[END_REF], yet the problem of constraining longterm structure remains.

Herremans et al. [START_REF] Herremans | Generating structured music for bagana using quality metrics based on Markov models[END_REF] developed a method to integrate Markov models in the objective function of a metaheuristic. The approach allows for the resulting music to be evaluated based on a machinelearned model, yet supports the use of hard constraints to x a larger structure. In our MorpheuS system [START_REF] Herremans | Tension ribbons: Quantifying and visualising tonal tension[END_REF][START_REF] Herremans | MorpheuS: automatic music generation with recurrent pattern constraints and tension pro les[END_REF], this approach is further expanded to tackle complex polyphonic music and automatically detected recurring patterns. We also developed a way to combine machine learning and music theory to construct a new type of objective function based on musical tension. In order to work with music in a quantitative way, we need a mathematical representation. Typically, music consists of a number of notes, each with properties such as pitch (often expressed as a MIDI pitch), duration, start time and beat number. In the MorpheuS project, the music generation problem is re-cast as one of nding new pitches that satisfy certain structural constraints given a rhythm template extracted from an existing piece. Our goal is thus to morph a pre-existing piece into a new composition.

Almost all the music that we hear is tonal, i.e., adhering to a system of hierarchical pitch relations.

The tonal properties of a piece of music and how they evolve over time shape the listener's perception of musical stability and tension. The tension pro le of a piece is one of the main de ning characteristics that imbues upon the piece long-term structural, which we use as a structural constraint in the MorpheuS project. This tension pro le is calculated based on the spiral array model for tonality [START_REF] Chew | Mathematical and Computational Modeling of Tonality: Theory and Applications[END_REF].

The spiral array consists of multiple embedded helices (see Figure 1), representing tonal entities at three hierarchical levels: pitch classes, chords and keys. The pitch class helix is effectively the line of fths (most simply explained as pitches having a simple 2:3 frequency ratio) wrapped around a cylinder so that pitch classes align vertically every four quarter turns. Chords and keys are each generated as convex combinations of their de ning elements as shown in Figure 2.

A real-time implementation of the spiral array and its tonal analysis algorithms has been used in live performances [START_REF] Chew | MuSA. RT: music on the spiral array. real-time[END_REF] to visualize tonal relationships in a music piece (see Figure 3). Leonard Meyer [START_REF] Meyer | Emotion and Meaning in Music[END_REF] ascribes the emotional content of music to the composer's choreography of expectation. Expectation suspended elicits tension, and expectation ful lled leads to resolution of that tension. The MorpheuS system aims to recreate the palpable tension that music generates; to this end, we have developed a model that captures tonal tension based on the spiral array [START_REF] Herremans | Tension ribbons: Quantifying and visualising tonal tension[END_REF].

The spiral array tension model rst segments a piece into equal length subdivisions and maps the notes to clouds of points in the array. Three aspects of tonal tension are captured using these clouds: the cloud diameter measures the dispersion (an indicator of dissonance) of note clusters in tonal space; the cloud momentum measures the movement of pitch sets (change in tonal context) in the spiral array; and, tensile strain measures the distance between the local and global tonal context. Each attribute can be visualized as tension ribbons on the score (see Figure 5).

Figure 4, shows a well-known tense chord in the spiral array: the German Sixth. It is noticeably spread out in the tonal space. The German Sixth chord occurs on the last beat of the second bar of Scott Joplin's "Binks' Waltz" (Figure 5). When this chord occurs, there is a noticeable increase in the tension ribbons representing cloud diameter and cloud momentum in the spiral array model. The tensile strain starts to increase slightly earlier, adding to the buildup of tonal suspense leading up to the German Sixth chord.

Patterns in Music

Repetition forms another important aspect of music structure. Recurrent themes and motives are reinforced with each repetition and stay in the listener's mind through the listening experience. A study by Margulis [START_REF] Margulis | Aesthetic responses to repetition in unfamiliar music[END_REF] revealed that listeners rated unfamiliar music that had repetitions as more enjoyable, interesting and artistic than the original non-repeated version. With repetition, patterns begin to form; Plato alludes to the importance of patterns in music:

"I would teach children music, physics and philosophy; but most importantly music, for the patterns in music and all the arts are the keys to learning." -Plato as cited by Plato & Bloom [START_REF] Plato | The republic of Plato[END_REF] Thus, in MorpheuS, we aim to generate music with patterns having the same length and that recur at the same places as the original template piece. In order to generate music with recurring patterns, we need to rst nd them. Compression algorithms such as SIATECCompress [20] and COSIATEC [START_REF] Meredith | Music analysis and point-set compression[END_REF] can be used to nd maximal translatable patterns, i.e., the largest subset of consecutive notes that recur either verbatim or transposed by a constant interval.

Using the elements discussed above, we can de ne music generation as an optimization problem. MorpheuS takes as an input a template piano piece. From the exemplar piece, the rhythmic structure is extracted and retained as a template. The algorithm aims to nd new pitches for each note in the original piece, and thus morph the piece into a new one. Recurring patterns in the template piece are detected using COSIATEC. These patterns form hard constraints during the optimization so as to enforce perceptible musical motifs and to ensure long-term coherence. The objective of the algorithm is to generate music with a speci c tension pro le; the user can choose to have the algorithm match the tension pro le of the template piece, or follow a user-given tension pro le.

To solve the multi-objective tension pro le matching problem, we have implemented an e cient variable neighborhood search (VNS) metaheuristic based on the algorithm developed by Herremans [START_REF] Herremans | Compose≡Compute -Computer Generation and Classi cation of Music Through Operations Research Methods[END_REF] for generating counterpoint music. This original VNS has been extended -with a move that changes multiple notes in a time slice -in order to handle more complex polyphonic music.

Conclusions

Systems like MorpheuS can now compose music with limited global structure, which may well be a starting point for scalable systems for automatic music generation. The output is promising, but still falls short of human creations. Take, for example, the issue of playability. The MopheuS-Haydn piece contains many awkward leaps and hand crossings; although these are not impossible, they do not often appear in human compositions. In the literature, apart from some algorithms for rudimentary ngering [START_REF] Balliauw | A variable neighborhood search algorithm to generate piano ngerings for polyphonic sheet music[END_REF]29], quantifying playability (which is far more than ngering) remains an important challenge.

Secondly, little is known about how the interactions of local and global patterns generate coherence. Could there be a way to generate viable patterns without relying on a template? Third, the shaping of music is closely tied to body movement, and feelings such as stress and lilt are part and parcel of musical communication. There are currently no known methods for, say, generating a lilting feeling or incorporating a danceability factor, which is not automatic even when the time signature is three-quarters (as in a waltz).

Finally, aspects such as having the time to breathe and to respire are essential components of human and thus musical communication. How does a composer modulate, beyond tonal tension, other factors for moments of release? As we consider and tackle these challenges, we nd ourselves faced with the deeper question of what it means to be human.



  https://pubsonline.informs.org/do/10.1287/orms.2018.01.03/full/ 3/14 the chains that shackle the spirit." -Stravinsky (as quoted in Strauss [27])

Figure 1 :

 1 Figure 1: Multiple embedded helices in the spiral array representing pitch classes, major and minor chords (triads), and major and minor keys (Figure reproduced from Chew 2014, p.59[START_REF] Chew | Mathematical and Computational Modeling of Tonality: Theory and Applications[END_REF]).



  https://pubsonline.informs.org/do/10.1287/orms.2018.01.03/full/ 4/14

Figure 2 :

 2 Figure 2: Spiral array pitch class, chord, and key representations: chords are weighted combination of their component pitches, and keys of their de ning tonic (rooted on the rst scale degree), subdominant (rooted on the fourth scale degree), and dominant (rooted on the fth scale degree). (Figures reproduced from Chew 2014, p.54-55 [4]).

Figure 3 .

 3 Figure 3. Elaine Chew performing with the MuSA_RT app [31] at the New Resonances Concert of the 2012 International Computer Music Modeling and Retrieval Conference.

Figure 4 :

 4 Figure 4: Joplin's German Sixth chord mapped to the spiral array; the chord in the key of Eb major consists of the notes Cb, Eb, F# and A.

 14 (Figure 5 :

 145 Figure 5: Tension ribbons of the German Sixth chord in Scott Joplin's Binks' Waltz (1905).



  https://pubsonline.informs.org/do/10.1287/orms.2018.01.03/full/ 8/14

Segmental Pattern Discovery in Music

Darrell Conklin, Christina Anagnostopoulou


Micaël Lassalle

Mustapha Moulana

Didier Ramon

Jérôme Colin

Olivier Hagolle

Micaël Lassalle¹

Mustapha Moulana²

Didier Ramon²

Jérôme Colin¹

Improving the modeling of adjacency effects for MAJA high resolution atmospheric corrections

teaching and research institutions in France or abroad, or from public or private research centers.

• adjacency effects : blur on satellite images due to atmospheric scattering • not negligible for high spatial resolution • MAJA [START_REF] Hagolle | MAJA Algorithm Theoretical Basis Document[END_REF][START_REF] Hagolle | [END_REF] :

○ CNES atmospheric correction processor for high resolution optical images ○ 2A-level for Sentinel-2 images ○ accounts for adjacency effects ○ ⍴ coupling so that we can retrieve corresponding G :

•
Computations with Smart-G (4)

Results

Perspectives

Contributions :

-atmospheric reflectance :

-direct transmission :

-diffuse transmission :

-multi-reflections : (coupling effect)

• to demonstrate the benefits of the new algorithm against the existing one, combining : ○ Sentinel-2 products ○ in-situ measurements :

-strongly contrasted site : crop field close to a forest (150m) -ROSAS station, Lamasquère (France) (5) • to implement the new algorithm within MAJA

  current model of adjacency effects within MAJA : ○ atmospheric Point Spread Function ○ constant gaussian function ○ range : 1km ➡ objectives : -to model adjacency effects along wavelengths, type of aerosols, optical thickness, Sun and satellite angles -to implement this model within MAJA in accordance with MAJA specifications : error < 1% Context • Miesch et al. (3) description of infinity of photon paths interacting or not with ground surface whose reflectance is ⍴(x,y) : • sum of each contribution for Top Of Atmosphere reflectances ⍴ TOA (x,y) : with ⍴ coupling = ⍴ ⊛ G (model of multi-reflections) • for this poster : ○ focus on 443nm wavelength and aerosol optical thickness is set to 0.2 ○ over an artificially contrasted surface (ground reflectance varying from 0 to 1) : ⇒ adjacency effects are higher than in realistic conditions • computation of TOA reflectances combining each term of Miesch equation : ⍴ TOA,Miesch • comparison of ⍴ TOA,Miesch and TOA reflectances directly computed with Smart-G : ⍴ TOA,ref • retrieving ground reflectances ⍴ by inverting Miesch equation (iterative process) : note : orange plot (iteration 1) corresponds to atmospheric corrections without accounting for adjacency effects ⇒ 5 th iteration : RMSE < 0.01 (specifications) even with this over contrasted landscape Model • radiative transfer code based on Monte Carlo method, developed by Hygéos • choice of Smart-G : very fast (GPU parallelisation), accurate computation of atmospheric phenomena including polarisation • physical quantities computed : ○ transmissions, atmosphere reflectance and albedo, TOA reflectances ○ :

  Results of ⍴ TOA,Miesch and ⍴ TOA,ref for landscapes with gaussian reflectance distributions of varying 𝜎 : Results of ⍴ TOA,Miesch and ⍴ TOA,ref for landscapes with a 1.0 reflectance disk of varying radius within a 0.0 reflectance surface : RMSE : 0.00019 -0.00017 -0.00016 -0.00019 -0.00032 RMSE : 0.00069 -0.00063 -0.00123 Results of ground reflectances for landscape with checkerboard reflectance distribution : RMSE after each iteration : 0.1316 -0.0315 -0.0197 -0.0104 -0.0104 -


Séverine Affeldt
email: severine.affeldt@u-paris.fr

Lazhar Labiod
email: lazhar.labiod@u-paris.fr

Mohamed Nadif
email: mohamed.nadif@u-paris.fr

Ensemble Block Co-clustering: A Unified Framework for Text Data

Keywords: Computing methodologies → Unsupervised learning, Ensemble methods, Cluster analysis, • Information systems → Clustering and classification, • Mathematics of computing → Probability co-clustering, ensemble method, information retrieval, text mining

In this paper, we propose a unified framework for Ensemble Block Co-clustering (EBCO), which aims to fuse multiple basic co-clusterings into a consensus structured affinity matrix. Each co-clustering to be fused is obtained by applying a co-clustering method on the same document-term dataset. This fusion process reinforces the individual quality of the multiple basic data co-clusterings within a single consensus matrix. Besides, the proposed framework enables a completely unsupervised co-clustering where the number of co-clusters is automatically inferred based on the non trivial generalized modularity. We first define an explicit objective function which allows the joint learning of the basic co-clusterings aggregation and the consensus block co-clustering. Then, we show that EBCO generalizes the one side ensemble clustering to an ensemble block co-clustering context. We also establish theoretical equivalence to spectral co-clustering and weighted double spherical 𝑘-means clustering for textual data. Experimental results on various real-world document-term datasets demonstrate that EBCO is an efficient competitor to some state-of-the-art ensemble and co-clustering methods.

INTRODUCTION

Clustering is the process of organizing similar objects into meaningful clusters. This approach is essential in many fields, including data science, machine learning, information retrieval, bio-informatics and computer vision, to deal with massive data. The clustering problem has been extensively addressed by different communities and many different approaches have been developed from various perspectives with various focuses. Although the purpose of clustering may seem simple, it is however an inherently difficult problem; different clustering algorithms and even multiple trials of the same algorithm may produce different results due to the fact that the initialization is not deterministic. To overcome the resulting instability and improve clustering performance, the ensemble clustering approach became an interesting alternative and therefore emerged as an important extension of the classical clustering problem. It refers to the following problem: given a number of different (input) clusterings that have been generated from a dataset, find a single final (consensus) clustering that is a better fit in some sense than the existing clusterings [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF].

Ensemble clustering has been extensively studied and many different approaches have been developed from various perspectives with various focuses [START_REF] Al-Razgan | Weighted clustering ensembles[END_REF][START_REF] Zhang | Solving cluster ensemble problems by bipartite graph partitioning[END_REF][START_REF] Li | Solving consensus and semisupervised clustering problems using nonnegative matrix factorization[END_REF][START_REF] Topchy | Combining multiple weak clusterings[END_REF][START_REF] Vega-Pons | Weighted partition consensus via kernels[END_REF][START_REF] Vega-Pons | A survey of clustering ensemble algorithms[END_REF][START_REF] Wang | Generalized cluster aggregation[END_REF][START_REF] Yoon | Heterogeneous clustering ensemble method for combining different cluster results[END_REF]. The main contribution of the co-association method is the redefinition of the consensus clustering problem as a classical graph partition problem. Thereby, Strehl and Ghosh [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] developed three graph-based algorithms for consensus clustering. Fred and Jain [START_REF] Ln | Combining multiple clusterings using evidence accumulation[END_REF] applied the agglomerative hierarchical clustering. In addition, there are some other interesting approaches for the ensemble clustering, such as the ones based on Information theoretic method [START_REF] Topchy | Combining multiple weak clusterings[END_REF], EM algorithm with a finite mixture of multinomial distributions [START_REF] Topchy | A mixture model for clustering ensembles[END_REF], Matrix factorization based method [START_REF] Li | Weighted consensus clustering[END_REF][START_REF] Li | Solving consensus and semisupervised clustering problems using nonnegative matrix factorization[END_REF][START_REF] Wang | Generalized cluster aggregation[END_REF], and kernel-based methods [START_REF] Vega-Pons | Weighted partition consensus via kernels[END_REF], respectively. Recently, Liu et al. [START_REF] Liu | Spectral ensemble clustering[END_REF] proposed a spectral ensemble clustering method, which ran spectral clustering on the co-association matrix and transformed it as a weighted 𝑘-means problem to achieve high efficiency. Tao et al. [START_REF] Tao | Robust spectral ensemble clustering[END_REF] proposed a unified framework to simultaneously learn a robust representation for the co-association matrix and find the final consensus partition. However, existing ensemble techniques are primarily designed for one side clustering methods, and few research efforts have been reported for ensemble co-clustering methods. For datasets arising in text mining and bioinformatics where the data is represented in a very high dimensional space, clustering both dimensions of data matrix simultaneously is often more desirable than traditional one side clustering. Co-clustering [START_REF] Ailem | Co-clustering documentterm matrices by direct maximization of graph modularity[END_REF][START_REF] Govaert | Co-clustering: models, algorithms and applications[END_REF][START_REF] Labiod | Co-clustering for binary and categorical data with maximum modularity[END_REF][START_REF] Salah | Model-based von Mises-Fisher Coclustering with a Conscience[END_REF] which is a simultaneous clustering of objects and features of data matrix consists generally in interlacing object clusterings with feature clusterings at each iteration; co-clustering exploits the duality between objects and features which allows to effectively deal with high dimensional data. In this way, co-clustering algorithms aim to reorganize the initial data matrix into homogeneous co-clusters 1 or biclusters, that can therefore be seen as subsets characterized by a set of observations and a set of features. Furthermore, co-clustering implicitly performs an adaptive dimensionality reduction at each iteration, leading to better object clustering accuracy compared to one side clustering methods.

The success on one hand of ensemble methods in classification and clustering, and on the other hand of co-clustering techniques to deal with high dimensional and sparse data, provides the main motivations for applying ensemble methods in document-term matrix co-clustering. In this work, we propose a novel Ensemble Block Co-clustering (EBCO) framework in which the input is a collection of document-term matrix co-clusterings. The output of the framework is a consensus block co-clustering. The Figure 1 illustrates the detailed conceptual framework of the EBCO method. This paper provides a unified view on combining multiple coclusterings by studying connections among various consensus and co-clustering criteria. The contribution of this paper is four-fold:

• We first tackle the problem of combining multiple co-clusterings as a bipartite graph co-clustering problem from a new perspective.

• Then, we propose an explicit objective function to generate and supervise the basic co-clusterings, and to determine the final co-clustering. • We show the connections between various consensus and co-clustering criteria. In particular, we demonstrate that the proposed method employs a generalized co-association matrix to find the consensus co-partition and equivalently results in a weighted 𝑘-means co-clustering, which decreases the time and space complexity.

1 Each co-cluster determines a submatrix of the original data matrix with some desired properties.

• Finally we propose a method to assess the number of coclusters. To the best of our knowledge, this is first time an ensemble co-clustering is considered while estimating the number of co-clusters.

The rest of the article is organized as follows: Section 2 discusses the related work; Section 3 details the EBCO framework for ensemble co-clustering; Section 4 investigates gateways and connections to some state-of-the-art consensus and co-clustering techniques for textual data. Section 5 shows experimental evaluations and results analysis; and, finally, Section 6 concludes the paper and discusses future work.

RELATED WORK

Co-clustering, under various names, has been successfully used in a wide range of application domains where the co-clusters can take different forms [START_REF] Van Mechelen | Two-mode clustering methods: a structured overview[END_REF]. If it has become popular, it is mainly through its numerous applications in different domains. For instance, in bioinformatics co-clustering, referred to as biclustering [START_REF] Sara | Biclustering algorithms for biological data analysis: a survey[END_REF], is used to cluster genes and experimental conditions simultaneously. In collaborative filtering [START_REF] Deodhar | SCOAL: a framework for simultaneous co-clustering and learning from complex data[END_REF], it is used to group users and items simultaneously, and in text mining [START_REF] Ailem | Graph modularity maximization as an effective method for co-clustering text data[END_REF][START_REF] Govaert | Mutual information, phi-squared and model-based co-clustering for contingency tables[END_REF] to group terms and documents simultaneously. If there are many works on ensemble clustering, few of them are devoted to co-clustering. To improve the performance of popular biclustering methods devoted to microarrays data, in [START_REF] Hanczar | Using the bagging approach for biclustering of gene expression data[END_REF] the authors proposed to adapt the approach of bagging to biclustering problems and in [START_REF] Hanczar | Ensemble methods for biclustering tasks[END_REF] they formalized the ensemble biclustering through a problem of binary triclustering. However, by contrast with our proposal, these approaches are unfortunately not appropriate for textual data due the nature of the data and the objective of the biclustering algorithms considered.

On the other hand, several approaches, inspired by the spectral clustering principle leading to a subspace on which 𝑘-means is applied, have been proposed. For instance, Huang et al. [START_REF] Huang | Spectral co-clustering ensemble[END_REF] designed a spectral co-clustering ensemble algorithm (SCCE) formulated as a bipartite graph partition problem. More specifically, let X be a data matrix (𝑛 objects described by 𝑑 features). A SVD is performed on the (𝑛 + 𝑑) × (𝑛 + 𝑑) adjacency matrix, then 𝑘-means is applied on the obtained subspace. More recently, Xianxue et al. [START_REF] Yu | Co-clustering Ensembles based on Multiple Relevance Measures[END_REF] proposed a co-clustering ensemble algorithm (CoCE) which, unlike SCCE, first evaluates the quality of the base co-clusters by measuring featureto-object relevance, and then the consensus process relies on the resulting hybrid graph. To obtain the object and feature clusters, 𝑘-means is performed separately on the obtained subspace by performing a SVD on a small graph Laplacian matrix. In fact, CoCE is formulated as a trace minimization problem and introduces a blockwise matrix multiplication technique to perform the optimization. The adjacency matrix is reduced from an (𝑛 + 𝑑) square matrix to an 𝑛 by 𝑑 matrix. As a result, CoCE is distinct from SCCE and has a lower time complexity. Yet, the CoCE time complexity still remains considerably high, in particular when dealing with text data, that are generally sparse and high dimensional.

As we will see in detail, EBCO differs from the above-mentioned approaches at three stages; 1) Our consensus approach is based on multiple co-clusterings while remaining in the spirit of a double 𝑘-means-like algorithm. It has therefore a considerably lower computational complexity. 2) Our approach focuses on text data and takes into account the nature of the data which exhibits directional characteristics.

3) The evaluation of the number of co-clusters is addressed in our proposal unlike in all the approaches cited above.

ENSEMBLE BLOCK CO-CLUSTERING (EBCO)

As we focus on document-term matrices, let X = (𝑥 𝑖 𝑗 ) be a data matrix of size 𝑛 × 𝑑, where 𝑥 𝑖 𝑗 ∈ N denotes the frequency of term 𝑗 in document 𝑖. The 𝑖 𝑡ℎ row (document) of this matrix is represented by a vector x 𝑖 = (𝑥 𝑖1 , . . . , 𝑥 𝑖𝑑 ) ⊤ , where ⊤ denotes the transpose. The partition of the set of documents 𝐼 into 𝑔 clusters can be represented by a classification matrix Z = (𝑧 𝑖𝑘 ) ∈ {0, 1} 𝑛×𝑔 satisfying ∀𝑖, 𝑔 𝑘=1 𝑧 𝑖𝑘 = 1. In the same way, we adopt the same notation for the partition of the set of terms 𝐽 by considering a classification matrix W = (𝑤 𝑗𝑘 ) ∈ {0, 1} 𝑑×𝑔 satisfying ∀𝑗, 𝑔 𝑘=1 𝑤 𝑗𝑘 = 1.

Problem definition

The techniques related to seriation aim to reorganize 𝐼 and 𝐽 according to a diagonal block correspondence [START_REF] Marcotorchino | Block seriation problems: A unified approach. Reply to the problem of H. Garcia and JM Proth[END_REF]. This objective, called the block seriation problem, can be addressed by finding optimal partitions described by Z and W of 𝐼 and 𝐽 respectively. This task can be carried out by a co-clustering method or relying on a block seriation relation Q = (q 𝑖 𝑗 ) defined on 𝐼 × 𝐽 by Q = ZW ⊤ where q 𝑖 𝑗 = 1 if document 𝑖 is in the same block as attribute 𝑗 and q 𝑖 𝑗 = 0 otherwise. Then,

q 𝑖 𝑗 = 𝑔 𝑘=1 z 𝑖𝑘 w 𝑗𝑘 = (ZW ⊤ ) 𝑖 𝑗 . (1)
The matrix Q represents a block seriation relation (see [START_REF] Marcotorchino | Block seriation problems: A unified approach. Reply to the problem of H. Garcia and JM Proth[END_REF] for further details), then it must respect the following properties, -Binarity. q 𝑖 𝑗 ∈ {0, 1}, ∀(𝑖, 𝑗) ∈ 𝐼 × 𝐽 .

-Assignment constraints. These constraints ensure the bijective correspondence between classes of two partitions, meaning that each class of the partition of 𝐼 has one and one corresponding class of the partition 𝐽 , and conversely, these constraints are expressed linearly as follows,

𝑗 ∈𝐽 q 𝑖 𝑗 ≥ 1 ∀𝑖 ∈ 𝐼 𝑖 ∈𝐼 q 𝑖 𝑗 ≥ 1 ∀𝑗 ∈ 𝐽 .
-Triad impossible. The role of these constraints is to ensure the blocks disjoint structure which is expressed by the following system inequality,

           q 𝑖 𝑗 + q 𝑖 𝑗 ′ + q 𝑖 ′ 𝑗 ′ -q 𝑖 ′ 𝑗 -1 ≤ 1 q 𝑖 ′ 𝑗 ′ + q 𝑖 ′ 𝑗 + q 𝑖 𝑗 -q 𝑖 𝑗 ′ -1 ≤ 1 q 𝑖 ′ 𝑗 + q 𝑖 𝑗 + q 𝑖 𝑗 ′ -q 𝑖 ′ 𝑗 ′ -1 ≤ 1 q 𝑖 𝑗 ′ + q 𝑖 ′ 𝑗 ′ + q 𝑖 ′ 𝑗 -q 𝑖 𝑗 -1 ≤ 1.
Furthermore, note that these constraints generalize the transitivity for non symmetric data. In the case where 𝐼 = 𝐽 , it is easy to show that the block seriation relation Q becomes an equivalence relation, i.e. Q = ZZ ⊤ or Q = WW ⊤ . Notice that the block seriation defined in Eq. ( 1) is not balanced by the row and column cluster size, meaning that a cluster might become small when affected by outliers. Thus we propose a new scaled block seriation relation that considers both row and column cluster sizes as follows,

q 𝑖 𝑗 = 𝑔 𝑘=1 z 𝑖𝑘 w 𝑗𝑘 √ z .𝑘 w .𝑘 = 𝑔 𝑘=1 z𝑖𝑘 w𝑗𝑘 = ( Z W 𝑇 ) 𝑖 𝑗 (2)
where the cluster sizes of Z and W are on the diagonal of D z = Z ⊤ Z and D w = W ⊤ W, respectively. Thereby we have Z = ZD -0.5 z and W = WD -0.5 w .

Objective function

The problem of combining multiple co-clusterings can be described as follows. Let M = {(Z 𝑙 , W 𝑙 ); 𝑙 = 1, ..., 𝑚} be a set of 𝑚 copartitions2 obtained by a given co-clustering algorithm. Each cocluster can be modeled as a scaled block seriation relation in this way

M 𝑙 = Z 𝑙 W ⊤ 𝑙 , 𝑙 = 1, . . . , 𝑚.
As the purpose is to obtain a final co-clustering having the properties of Q = ( q 𝑖 𝑗 ), we propose to rely on a consensus structured affinity matrix Q such that each M 𝑙 can be modeled as M 𝑙 = Q + 𝐸 𝑙 , 𝑙 = 1, . . . , 𝑚. This leads us to the following optimization problem. min

Q 𝑚 𝑙=1 𝐷 ( M 𝑙 , Q) (3)
where 𝐷 is a cost function that allows us to quantify the quality of the approximation of M 𝑙 by Q; 𝐷 can be, for instance, the Frobenius norm. This measure minimizes the disagreements between each basic co-clustering M 𝑙 and the consensus co-clustering Q; it can be solved by min

Q 𝑚 𝑙=1 || M 𝑙 -Q|| 2 𝐹 .
On the other hand, it is easy to show that optimal solution Q * is the consensus (average) affinity matrix M = 1 𝑚 𝑚 𝑙=1 M 𝑙 . Hence, given M, the objective function to optimize becomes min

Q J 𝐸𝐵𝐶𝑂 (M, Q) ≡ min Q ||M -Q|| 2 𝐹 . (4)
Proposition 3.1. Let M and Q be 𝑛 × 𝑑 matrices, we have,

min Q ||M -Q|| 2 𝐹 ≡ max Q 𝑇𝑟 (M Q ⊤ ) ≡ max Z, W 𝑇𝑟 ( Z ⊤ M W) (5)
Proof. Let us expand the left term in [START_REF] Deodhar | SCOAL: a framework for simultaneous co-clustering and learning from complex data[END_REF],

||M -Q|| 2 𝐹 = ||M|| 2 𝐹 + || Q|| 2 𝐹 -2𝑇𝑟 (M Q ⊤ ) (6)
First of all, ||M|| 2 𝐹 is known, and does not depend on Q. On the other hand, as regards

|| Q|| 2 𝐹 , it is easy to show that || Q|| 2 𝐹 = 𝑇𝑟 ( Q Q ⊤ ) = 𝑇𝑟 ( Z ⊤ Z W ⊤ W) = 𝑇𝑟 (I) = 𝑔
where 𝑔 is the number of co-clusters that is assumed to be known (its assessment will be discussed later). Hence, due to (6) and the property 𝑇𝑟 (𝐴𝐵) = 𝑇𝑟 (𝐵𝐴) provided that the product is possible, we have, min

Q ||M -Q|| 2 𝐹 ≡ max Q 𝑇𝑟 (M Q ⊤ ) ≡ max Z, W 𝑇𝑟 (M W Z ⊤ ) ≡ max Z, W 𝑇𝑟 ( Z ⊤ M W).

□

In the following, we will see the interest of this formulation of the objective function both in terms of optimization and connections with other algorithms.

Optimization and algorithm

Before solving (5), note that using both properties𝑇𝑟 (𝐴𝐵) = 𝑇𝑟 (𝐵𝐴) and 𝑇 𝑟 (𝐴 ⊤ ) = 𝑇 𝑟 (𝐴), if 𝐴 is a square matrix, it easy to show that,

(𝑎) 𝑇 𝑟 ( Z ⊤ M W) = 𝑇𝑟 (Z ⊤ M WD -0.5 z ) = ⟨M W, Z⟩ D -0.5 z (7) (𝑏) 𝑇 𝑟 ( Z ⊤ M W) = 𝑇𝑟 (W ⊤ M ⊤ ZD -0.5 w ) = ⟨M ⊤ Z, W⟩ D -0.5 w . (8)
The two terms ⟨M W, Z⟩ D -0.5 z and ⟨M ⊤ Z, W⟩ D -0.5 w in ( 7) and ( 8 Given an initial guess of W and Z, we iteratively update the model parameters,

Update of Z: when W is fixed, Z can be obtained by maximizing ⟨M W, Z⟩ D -0.5 z = 𝑖,𝑘 𝑧 𝑖𝑘 1 √ 𝑧 .𝑘 w ⊤ 𝑘 m 𝑖 . Then the update of Z is given by ∀𝑖, 𝑧 𝑖𝑘 = argmax 𝑘 ′ 1 √ 𝑧 .𝑘 ′ w ⊤ 𝑘 ′ m 𝑖 ∈ {0, 1}, this leads to Z = 𝐵𝑖𝑛𝑚𝑎𝑥 3 (M WD -0.5 z ). (9)
Update of W: when Z is fixed, W can be obtained by maximizing

⟨M ⊤ Z, W⟩ D -0.5 w = 𝑗,𝑘 𝑤 𝑗𝑘 1 √ 𝑤 .𝑘 z ⊤ 𝑘 m 𝑗 . Then the update of W is given by ∀𝑗, 𝑤 𝑗𝑘 = argmax 𝑘 ′ 1 √ 𝑤 .𝑘 ′ z ⊤ 𝑘 ′ m 𝑗 ∈ {0, 1}. This leads to W = 𝐵𝑖𝑛𝑚𝑎𝑥 (M ⊤ ZD -0.5 w ). (10)
Note that the update rules show the mutual interaction between the set of documents and the set of terms. In the sequel, we give the details of the alternating procedure of EBCO in Algorithm 1.

Algorithm 1 Ensemble Block Co-Clustering (EBCO).

Input: M = {(Z 𝑙 , W 𝑙 ); 𝑙 = 1, . . . , 𝑚} a collection of co-partitions, 𝑔 number of co-clusters, Output: co-partition (Z, W) Initialization: a) Compute M b) Random initialization of W and Z 4 . repeat 1. Assignment of documents (9)
• Z ← 𝐵𝑖𝑛𝑚𝑎𝑥 (M WD -0.5 z ) 2. Assignment of terms [START_REF] Ln | Combining multiple clusterings using evidence accumulation[END_REF] •

W ← 𝐵𝑖𝑛𝑚𝑎𝑥 (M ⊤ ZD -0.5 w ) until convergence of 𝐽 𝐸𝐵𝐶𝑂 (M, Q) = ||M -Q|| 2 𝐹 (4)
Note that M WD -0.5 z and M ⊤ ZD -0.5 w are the projections of documents and words in the low-dimensional space. Furthermore, we 3 Let A = (𝑎 𝑖𝑘 ) ∈ {0, 1} 𝑛×𝑔 with ∀𝑖, 𝑘 𝑎 𝑖𝑘 = 1 and B = (𝑏 𝑖𝑘 ) ∈ R 𝑛×𝑔 , then A ← 𝐵𝑖𝑛𝑚𝑎𝑥 (B) means ∀𝑖, 𝑎 𝑖𝑘 = argmax 𝑘 ′ 𝑏 𝑖𝑘 ′ , 𝑘 ′ = 1, . . . , 𝑔. 4 Initial W and Z can be obtained, for instance, by using spherical 𝑘-means.

observe the conscience mechanism principle [START_REF] Desieno | Adding a conscience to competitive learning[END_REF] 5 thanks to the role played by the diagonal matrices D -0.5 z and D -0.5 w . Besides, EBCO is computationally efficient and its complexity can be shown to be 𝑂 (𝑛 • 𝑖𝑡 • (2𝑔)) where 𝑖𝑡 is the number of iterations, which is small (about few dozens).

RELATIONS AMONG DIFFERENT CONSENSUS AND CO-CLUSTERING FUNCTIONS

We detail in this section the connections with various criteria. In particular, we highlight the equivalence relation between our proposal and other state-of-the-art consensus and co-clustering methods devoted to text data -namely one side ensemble clustering, spectral co-clustering, NMTF and double spherical 𝑘-means -. The mathematical details of derivation on the connections are presented in the rest of this section.

Connection to ensemble clustering

First of all, we show that the proposed framework for ensemble co-clustering is a natural generalization of the well studied one side ensemble clustering. In fact, the proposed optimization problem in Eq. ( 4) generalizes the ensemble clustering objective based on the co-association matrix. Indeed, the consensus co-clustering modeled by a scaled Block seriation relation

Q = Z W ⊤ which is defined on 𝐼 × 𝐽 , generalizes the scaled equivalence relation Y = Z Z ⊤ , which is defined on 𝐼 × 𝐼 . Let us consider the objective function of EBCO, min Q 𝑚 𝑙=1 || M 𝑙 -Q|| 2 𝐹 ≡ min Q ||M -Q|| 2 𝐹 .
When 𝐼 ≡ 𝐽 , Q becomes Y and M takes the following form S =

1 𝑚 𝑚 𝑙=1 Z 𝑙 Z ⊤ 𝑙 .
Thereby, the objective function optimized by EBCO is reduced to the objective of one side ensemble clustering as follows, min

Y 𝑚 𝑙=1 || S 𝑙 -Y|| 2 𝐹 ≡ min Y ||S -Y|| 2 𝐹 ≡ max Z ⊤ Z=I 𝑇𝑟 ( Z ⊤ S Z).
Note that the combined co-affinity matrix M can be viewed as an extension of S which is central in the ensemble clustering context. Furthermore, all the connections which will be discussed below remain valid in the context of ensemble clustering.

Connection to spectral co-clustering

In the optimization problem of Eq. ( 4), we relax the non-negativity constraint on both Z and W. Therefore, we have, min

Q J 𝐸𝐵𝐶𝑂 ( Q) ≡ max Z ⊤ Z=I, W ⊤ W=I 𝑇𝑟 ( Z ⊤ M W)
where Z = ZD -0.5 z and W = WD -0.5 w . It is easy to verify that Z and W satisfy the orthogonality constraint, i.e. Z ⊤ Z = I and W ⊤ W = I. This optimization problem can be performed by Lagrange multipliers into eigenvalue problem. Then, given 𝑠𝑣𝑑 (M) = ZΣ W ⊤ , the discrete co-clustering is obtained by performing 𝑘-means on the concatenated data Z W ⊤ . This is equivalent to the spectral co-clustering method proposed in [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF].

Connection to NMTF

In a similar way, we can establish a connection with Non-negative Matrix Tri-Factorization (NMTF) [START_REF] Pei | Nonnegative matrix tri-factorization with graph regularization for community detection in social networks[END_REF][START_REF] Wang | Nonnegative matrix tri-factorization based high-order co-clustering and its fast implementation[END_REF][START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF] that consists in approximating X by ZDW ⊤ . Let us consider the weighting diagonal matrix

D (𝑔×𝑔) = (d 𝑘𝑘 ) defined by D = D -0.5 z D -0.5 w ; d 𝑘𝑘 = 1 √ 𝑧 .𝑘 𝑤 .𝑘
depends on a geometric mean of documents and words cluster sizes in co-cluster 𝑘𝑘, then we have min

Z,W ||X -ZD -0.5 z D -0.5 w W ⊤ || 2 𝐹 ≡ min Z,W,D=D -0.5 z D -0.5 w ||X -ZDW ⊤ || 2 𝐹 ≡ max Z,W,D 𝑇𝑟 (Z ⊤ XWD) ≡ max Q J 𝐸𝐵𝐶𝑂 (X, Q).
Thereby, the criterion optimized by Fast NMTF proposed in [START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF] applied on X with an additional constraint on the centroid matrix D is equivalent to EBCO applied on X.

Connection to double weighted spherical k-means

Note that as M can be written in vector form in two ways:

M = [m 1 , . . . , m 𝑛 ] ⊤ or M = [m 1 , . . . , m 𝑑 ],
we can derive two expres-

sions of 𝑇 𝑟 ( Z ⊤ M W) = ⟨M W, Z⟩ D -0.5 z = ⟨M ⊤ Z, W⟩ D -0.5
w . Indeed from Eq. ( 7) and Eq. ( 8) respectively we have,

⟨M W, Z⟩ D -0.5 z = 𝑖,𝑘 𝑧 𝑖𝑘 1 √ 𝑧 .𝑘 w ⊤ 𝑘 m 𝑖 = 𝑖,𝑘 1 √ 𝑧 .𝑘 𝑧 𝑖𝑘 𝑐𝑜𝑠 ( w 𝑘 , m 𝑖 ), ⟨M ⊤ Z, W⟩ D -0.5 w = 𝑗,𝑘 𝑤 𝑗𝑘 1 √ 𝑤 .𝑘 z ⊤ 𝑘 m 𝑗 = 𝑗,𝑘 1 √ 𝑤 .𝑘 𝑤 𝑗𝑘 𝑐𝑜𝑠 ( z 𝑘 , m 𝑗 ).
From both formulations, we can observe that EBCO looks like a double weighted spherical 𝑘-means with a conscience mechanism devoted to document clustering and referred to as DCC [START_REF] Salah | Model-based von Mises-Fisher Coclustering with a Conscience[END_REF]. Both criteria are weighted by 1/ √ 𝑧 .𝑘 and 1/ √ 𝑤 .𝑘 whose role here is to discourage larger clusters to absorb new rows or columns and therefore, to avoid empty clusters. However, unlike DCC, with EBCO the norms of z 𝑘 , w 𝑘 , m 𝑗 and m 𝑖 are not necessarily equal to 1.

UNSUPERVISED BASIC CO-CLUSTERINGS SELECTION AND ASSESSMENT OF THE NUMBER OF CO-CLUSTERS

A challenging problem in co-clustering is the inference of the number of co-clusters which is often assumed to be known by the user.

In this section, we present a method to determine this parameter based on the work of [START_REF] Labiod | Co-clustering for binary and categorical data with maximum modularity[END_REF], where the authors rely on modularity criterion to deal with co-clustering of categorical data.

EBCO objective versus Modularity criterion

Given the affinity matrix M defined on 𝐼 × 𝐽 , to tackle the coclustering we consider the following generalized modularity measure J 𝑀𝑜𝑑 defined in [START_REF] Labiod | Co-clustering for binary and categorical data with maximum modularity[END_REF],

J 𝑀𝑜𝑑 (Q) = 1 2|𝐸| 𝑛 𝑖=1 𝑛 𝑗=1 (𝑚 𝑖 𝑗 - 𝑚 𝑖. 𝑚 .𝑗 2|𝐸|
)q 𝑖 𝑗 .

where 2|𝐸| = 𝑖,𝑗 𝑚 𝑖 𝑗 = 𝑚 .. is the total weight of edges and 𝑚 𝑖. =

𝑗 𝑚 𝑖 𝑗 -the degree of 𝑖 and 𝑚 .𝑗 = 𝑖 𝑚 𝑖 𝑗 -the degree of 𝑗. This Modularity measure takes the following matrix trace form,

J 𝑀𝑜𝑑 (Q) = 1 2|𝐸| 𝑇𝑟 [(M -𝛿) ⊤ Q] where 𝛿 𝑖 𝑗 = 𝑚 𝑖. 𝑚 .𝑗 𝑚 .. . ( 12
)
As the objective function in Eq. ( 12) is linear with respect to Q and as the constraints that 𝑍 must respect linear equations, we can theoretically solve the problem using an integer linear programming solver. However, this problem is 𝑁 𝑃 hard; as result we use heuristics in practice for dealing with large datasets. In Eq. ( 12), if we set 𝛿 = 0 and consider the scaled Block seriation Q instead of the binary Block seriation Q, J 𝑀𝑜𝑑 is equivalent to J 𝐸𝐵𝐶𝑂 . Then, when 𝛿 = 0, EBCO can be viewed as a relaxation of the modularity criterion which considers the size of row clusters and column clusters, and leads to a tractable optimization problem.

Assessing of the number of co-clusters

Since modularity objective is not a trivial criterion, we co-cluster each data set into different number of co-clusters varying from 2 to K. For each fixed number of co-clusters, the co-clustering modularity is computed and the optimal number of co-clusters is considered to correlate well with the maximum modularity value. Unlike to known spectral clustering methods, in [START_REF] Ailem | Graph modularity maximization as an effective method for co-clustering text data[END_REF] authors show that the modularity measure allows natural co-clusters identification, i.e. the maximum value of modularity correlates well with the optimal number of co-clusters. EBCO enables a modularity-based evaluation of the number of co-clusters at the step denoted as Option 2 in Figure 1.

Unsupervised selection of relevant basic co-clusterings

Given a collection of basic co-clusterings generated on the same dataset, the co-clustering modularity is computed for each basic co-clustering and the selection of relevant co-clusterings in the final collection is considered based on the modularity value. We consider only basic co-clusterings with high modularity value (modularity value greater than a fixed threshold), i.e the relevance of a coclustering correlate well with the maximum modularity value. EBCO enables a modularity-based selection of the basic co-clusterings at the step denoted as Option 1 in Figure 1.

EXPERIMENTS

We performed extensive experiments on a wide range of real-world text datasets. Our results demonstrate the high performance of EBCO . In particular, we compare our approach with four effective diagonal and non-diagonal co-clustering algorithms that are very competitive in the field of text co-clustering, namely DCC [START_REF] Salah | Model-based von Mises-Fisher Coclustering with a Conscience[END_REF],

CoClustMod [START_REF] Ailem | Co-clustering documentterm matrices by direct maximization of graph modularity[END_REF][START_REF] Ailem | Graph modularity maximization as an effective method for co-clustering text data[END_REF], CoClustSpecMod [START_REF] Labiod | Co-clustering for binary and categorical data with maximum modularity[END_REF] and CROINFO [START_REF] Govaert | Co-clustering: models, algorithms and applications[END_REF][START_REF] Govaert | Mutual information, phi-squared and model-based co-clustering for contingency tables[END_REF].

We also compare EBCO to CoCE [START_REF] Yu | Co-clustering Ensembles based on Multiple Relevance Measures[END_REF], a recent and competitive co-clustering ensemble algorithm. For CROINFO6 , CoClustMod and CoClustSpecMod, we used the implementation and default parameters of the CoClust Python package [START_REF] Role | CoClust: A Python Package for Co-Clustering[END_REF]. For CoCE, we used the Matlab source code proposed by the authors 7 . EBCO and DCC were implemented in Python. Note that in [START_REF] Ailem | Co-clustering documentterm matrices by direct maximization of graph modularity[END_REF][START_REF] Ailem | Graph modularity maximization as an effective method for co-clustering text data[END_REF], through extensive experiments on text datasets, the authors showed that CoclusMod outperforms several other notable co-clustering methods that we do not retain in our comparisons. Similarly, as the competitiveness of CoCE was extensively demonstrated in [START_REF] Yu | Co-clustering Ensembles based on Multiple Relevance Measures[END_REF], we do not include the approaches outperformed by CoCE in our experiments.

Benchmark datasets

For our evaluations, we consider 7 benchmark document-term datasets that are popular for the document clustering task, namely SPORTS, TR45, PUBMED10, LA12, CLASSIC4, CSTR and CLASSIC3 (Table 1). Each document-term data matrix X can be viewed as a contingency table (or a two-way frequency table) where 𝑥 𝑖 𝑗 indicates the number of occurrences of word 𝑗 in document 𝑖. Together, these datasets embed several challenging situations such as different degrees of cluster balance, diverse cluster sizes and various degrees of cluster overlap. These datasets cover a wide range of imbalance strength as can be seen from their Balance coefficient (Table 1), which is the ratio of the minimum cluster size to the maximum cluster size. As is frequently the case in document-term co-clustering, the labels of benchmark datasets are only known for documents and not the words. Yet, as the words partition is inherently associated with the document partition, we expect that the quality of the document clustering is informative about the quality of the word clustering.

Experimental settings

We normalized each document-term matrix using the TF-IDF weighting scheme (term-frequency times inverse document frequency) as implemented in the scikit-learn Python package. The EBCO results are averaged over 10 different runs. Each run involves the generation of an ensemble matrix M based on several basic coclusterings with a growing number of co-clusters (Fig. 1, steps (𝑎) & (𝑏)) and a final co-clustering on the ensemble matrix M with 10 different initializations and 100 iterations (Fig. 1, step (𝑐)). For each run, the final co-clustering that corresponds to the best algorithm criterion is automatically retained. Furthermore, to avoid poor local solution that could be induced by early hard word assignments in the iteration, we perform stochastic column assignments during the first 70 iterations, as described in [START_REF] Salah | Directional co-clustering[END_REF].

Evaluation metrics

To evaluate the performance of EBCO and the competitive text co-clustering methods (DCC, CoClustMod, CoClustSpecMod and CROINFO), we compare the document clustering of their bi-partitions with the original document labels. The comparisons are made by computing the Adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF] and the Normalized Mutual Information (NMI) [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF], which are two widely used measures that assess the similarity between the estimated clusters and the true clustering. In particular, NMI evaluates how the estimated clustering is informative about the known clustering, and ARI quantifies the agreement between the estimated clustering and the true labels. NMI, unlike ARI, is less sensitive to cluster splitting or merging. For both metrics, we used the implementation provided by the scikit-learn Python package.

In Section 6.4, we first evaluate the EBCO performance on a complete collection of 𝑠 = 24 basic co-clusterings with a growing number of co-clusters from 2 to 25 and using the original document cluster number 𝑔 as final number of co-clusters. We compare these evaluations to the results obtained with several recent and competitive text co-clustering methods, namely DCC, CoClustMod, CoClustSpecMod and CROINFO. Then, in Section 6.5, we evaluate the EBCO performance on a partial collection where the basic co-clusterings are automatically selected based on modularity (𝑠 < 24; Fig. 1, Option (1)). Finally, we evaluate in Section 6.6 the fully unsupervised version of EBCO, when the final number of co-clusters is also automatically learned based on modularity (Fig. 1, Option (2)).

Complete co-clusterings collection ensemble

As detailed in Section 6.1, only the document labels are known and are used to evaluate the different approaches in this section. We first obtained a collection of basic co-clusterings, {(Z 𝑙 , W 𝑙 )} 𝑙 ∈ [2...25] . Then, these co-clusterings are merged into M, before repeating the final co-clustering alternating steps until the convergence of the objective function J 𝐸𝐵𝐶𝑂 (Algorithm 1). While the number of co-clusters for each basic co-clustering varies from 2 to 25, the final number of co-clusters is set to the known number 𝑔 for each benchmark document-text dataset. The NMI and ARI results are average over 10 trials. Table 2 summarizes the comparative results of EBCO for the 7 datasets.

As can be seen from Table 2, our co-clustering ensemble approach outperforms the other methods on all datasets with a significant margin. Interestingly, EBCO outperforms both the ARI and NMI of the other approaches, with an average ARI and NMI increase of 0.128 and 0.098 respectively. These improvements, in particular for ARI, shows the good capacity for EBCO to handle imbalanced clusters.

In figure 2 we note the high performance of EBCO as compared to CoCE in terms of clustering. Furthermore, it should also be remembered that unlike EBCO having a linear complexity, the computational complexity of CoCE is dominated by the execution of SVD; which is 𝑂 (𝑒𝑁𝑛𝑑), where 𝑒 = ⌈log 2 𝑔⌉ and 𝑁 is the number of 50 Lanczos iteration steps as mentioned in [START_REF] Yu | Co-clustering Ensembles based on Multiple Relevance Measures[END_REF]. Such complexity makes the use of CoCE quite prohibitive for high dimensional text data.

Partial co-clusterings collection ensemble

Using the complete basic co-clusterings collection already provides a significant improvement of EBCO as compare to alternative text co-clustering approaches or ensemble co-clustering methods (Section 6.4). However, not all the basic co-clusterings are necessary to build the joint matrix M. In fact, based on a modularity criteria, one can identify the best basic co-clustering from the whole collection and its closest co-clusterings that could bring valuable information. Specifically, taking the highest modularity of the collection, we can select a partial collection of models that reach a modularity equal or greater than 95%, 90%, 85%, 80%, 75%, 50% or 25% the maximum modularity. The Figure 3a exemplifies this selection for CLASSIC4 (horizontal dashed lines). Figure 3b to Figure 3f illustrate the evolution of NMI and ARI when increasing the partial collection up to the complete collection for several benchmark datasets. Our experiments indicate that a partial collection of models with a modularity value of at least 80% of the maximum modularity would be sufficient to reach the maximum NMI and ARI. Therefore, we would generally advice this percentage for other studies.

Interestingly, one can see from Figure 3a that even if the basic co-clusterings infer a number of co-clusters of 5 instead of 4 for the CLASSIC4 dataset, the fully unsupervised version of EBCO ultimately infer the expected number of co-clusters (see Section 6.6, Table 3). This reinforce the idea that beyond the model that maximizes the modularity, closest models should also be considered in an ensemble approach as they can bring relevant information.

Fully unsupervised ensemble co-clustering

We evaluate in this section the ability of EBCO to run as a fully unsupervised approach (Fig. 1, EBCO with Option 1 and Option 2). Specifically, EBCO can automatically infer the best number of co-clusters based on modularity (Fig. 1, Option (2)). Table 3 gives the NMI and ARI results for EBCO and the inferred number of coclusters 𝑔 ★ for the 7 benchmark datasets. As empirically suggested by our experiments, we have set the partial collection with models having at least 80% of the maximum modularity value.

As can be seen in Table 3, EBCO infers a number of co-clusters 𝑔 ★ that is equal or closed to the expected number 𝑔 for almost all benchmark datasets. For one dataset, PUBMED10, the number of co-clusters is more strongly underestimated. We hypothesis that for this dataset the inferred number of co-clusters 𝑔 ★ better reflects the actual co-cluster number as several document topics are inherently intertwined. We specifically discuss this point in details in Section 6.7. In Figures 4a &4c, we give for CSTR and PUBMED10 the inferred number of co-clusters (gray datapoint annotation) while increasing the size of the partial collection. We also provide the evolution of the NMI and ARI. For both datasets, the EBCO co-clustering provides a clear partitioning of the input document-term matrices, as can be seen from Figures 4b &4d

Evaluating topic and word clusterings

In the following, we first analyse the co-clusters top terms for PUBMED10 [START_REF] Chen | Exemplar-based visualization of large document corpus (infovis2009-1115)[END_REF]. We then study the distribution of document topics in the co-clusters and make the link with their top terms. In particular, we study the evolution of the topics distribution when the number of co-clusters varies from 10 (the known document labels) to 7 (the EBCO estimation). PUBMED10 is based on approximately 15, 000 biomedical abstracts downloaded from Medline database that cover 10 diseases and that were published between 2000 and 2008. Each document is originally labeled with the corresponding disease (Table in Figure 5). Our results suggest that EBCO infers a number of co-clusters (𝑔 ★ = 7) that reflects actual biomedical relationships between diseases (Figure 5, bottom line). We propose an improvement over the frequency ordering method that is based on the Normalized Pointwise Mutual Information (NPMI) to reorder the most frequent co-cluster words. The NPMI ranges between -1 and +1, and is formally defined as NPMI(𝑤 𝑖 , 𝑤 𝑗 ) = PMI(w i , w j )/log(𝑝 (𝑤 𝑖 , 𝑤 𝑗 )), where the PMI between words 𝑤 𝑖 and 𝑤 𝑗 is defined as log 𝑝 (𝑤 𝑖 , 𝑤 𝑗 )/𝑝 (𝑤 𝑖 )𝑝 (𝑤 𝑗 ) . We use the NPMI through a k-nn-like (𝑘 nearest neighbors) approach to compute for each word a NPMI 𝑖 score defined a,

NPMI 𝑖 = 1 |Ω 𝑖 | 𝑤 𝑗 ∈Ω 𝑖 NPMI(𝑤 𝑖 , 𝑤 𝑗 ) (13)
where Ω 𝑖 is the set of 𝑘 words 𝑤 𝑗 having the highest NPMI score with 𝑤 𝑖 . Therefore, the NPMI 𝑖 quantifies the membership of a word in a cluster based on its relationships with its 𝑘 most closest NPMI neighbors. The Table 4 gives the top NPMI 𝑖 words for PUBMED10 word clusters (𝑘 = 5 neighbors among the 30 most frequent terms) for the fully unsupervised EBCO co-clustering (𝑔 ★ =7). Probabilities are derived from the whole English Wikipedia, using a NPMI implementation proposed by Röder et al. [START_REF] Röder | Exploring the space of topic coherence measures[END_REF]. Therefore, the NPMI 𝑖 scores are independent of the input document-term data.

As can be seen from Table 4, the top NPMI 𝑖 terms contain words that are coherent with the main topics. For instance, the Hay Fever 10 top terms now include immunotherapy -a seasonal allergy treatment -and oesinophil -a marker in seasonal allergic rhinitis -, while the frequency-based approach rank these terms at the 24 𝑡ℎ and 25 𝑡ℎ position respectively. The word pneumonia can be found in the Otitis top terms at the 2 𝑛𝑑 position -instead of 19 𝑡ℎ based only on frequency -which is coherent with the fact that Streptococcus pneumoniae is the most common microbial agent found in otitis. Finally, the AMD 10 top terms are enriched with diabetic -an AMD risk factor -, and edema -a symptom of macular degeneration. Pie charts gives the percentage of disease-documents associated to EBCO co-clusters. As can be seen, several co-clusters are stable and keep a clear predominant topic when changing the number of co-clusters, such as AMD (gray pie charts), Otitis (blue pie charts), Migraine (light green pie charts without Raynaud Disease) and Hay Fever (brown pie charts).

We can observe a stable co-cluster with two main topics, namely Hepatitis A and Chickenpox (Fig. 5, purple and orange pie charts). The biomedical literature gives an explanation for this balanced association, as hepatitis has been found in several studies to be a severe complication of chickenpox in adult, with possibly lethal outcome. The association of these two topics corresponds to an actual biomedical fact, that is clearly reflected by the word partition. In Table 4 (last column), top terms contain varicella, hepatitis, infection and outbreak.

The Figure 5 also shows the gathering of several topics when 𝑔 ′ is reduced. As an example, Kidney Calculi and Gout are associated when 𝑔 ′ = 10, and are then associated with Jaundice when 𝑔 ′ ∈ [START_REF] Zhang | Solving cluster ensemble problems by bipartite graph partitioning[END_REF][START_REF] Inderjit S Dhillon | Information-theoretic co-clustering[END_REF][START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF]. This topics gathering expresses a medical reality as Kidney stone disease is commonly seen in patients with underlying metabolic disorders such a Gout. Furthermore, Gout disease results in elevated levels of uric acid that can lead to crystals precipitating in the kidneys, inducing stone formation. In Table 4 (first column), the corresponding top terms are uric, acid, oxalate, calcium, kidney and gout. Several studies have demonstrated clinical associations between renal failure and obstructive jaundice -jaundice that results from abnormal retention of bile in the liver-. Specifically, the retention of bile constituents (eg. bilirubin) has deleterious effect on cardiovascular function, which in turn can induce kidney failure and tubular necrosis. As can be seen in Table 4, the top terms also contain obstruction and jaundice.

The Figure 5 also highlights the association between Migraine and Raynaud's disease for 𝑔 ′ ∈ [10..7], and with AMD when 𝑔 ′ = 7. This again corresponds to biomedical facts. Specifically, Raynaud's disease patients hyper-react to phenomenom that constrict blood vessels (eg. cold, vibration, stress) leading to a lack of blood and oxygenation in digits and body parts. It has been established that Raynaud's is a frequent comorbid condition with Migraine. Some Migraine treatments are efficient on Raynaud's, such as calcium channel blockers. Yet, the most effective Raynaud's treatments, that are based on blood vessels dilatation are not recommended for migraineurs. Furthermore, studies have revealed genetic predisposition for Raynaud's disease, in particular an association with a polymorphism in the NOS1 gene which is known for its role in cold induced vascular responses. Among the top terms from Table 4 (fifth column), mutation, gene or polymorphism clearly support this specificity of Raynaud's disease. These terms also strongly contrast with the top terms of the other co-cluster that has Migraine as main topic (Table 4, Migraine column). Finally, the constriction of blood vessels -frequently found in Raynaud's disease -that nourish the retina, is one of the AMD risk factors. This could explain the association of AMD to this co-cluster when 𝑔 ′ = 7.

All in all, it appears that the co-clustering proposed by the fully unsupervised EBCO (with 𝑔 ★ = 7) brings interesting biomedical indications on several actual disease relationships.

In unsupervised learning, ensemble clustering is a beneficial alternative to improve the quality of clustering. In our proposal, we have shown that this approach is undoubtedly useful to be extended in the context of text data co-clustering. Thereby, we have not only achieved this objective in terms of co-clustering quality and ease of co-clusters interpretation but we have also been able to address the crucial problem of choosing the number of co-clusters. This has been demonstrated on several datasets and compared to competitive co-clustering algorithms devoted to the same task. The EBCO is therefore tailored for document-term matrices and offers even a unified framework which can be exploited for other types of data. It is worth noting that the high time and space complexity of CoCE prevents handling large-scale data co-clustering; its computational cost is dominated by the execution of SVD on the 𝑛 by 𝑑 adjacency matrix. By contrast, EBCO uncovers an equivalence relationship with weighted double spherical 𝑘-means that dramatically decreases the time and space complexity to roughly linear complexity.

On the other hand, we have shown how our approach can be converted to an ensemble clustering approach. Furthermore, in terms of algorithmic or criterion, we established interesting connections with NMTF, spectral clustering and double weighted spherical 𝑘-means with conscience mechanism. These connections open up new prospects for investigation for other types of datasets.

Figure 1 :

 1 Figure 1: EBCO Framework: 𝑎) From a document-term matrix, let be a collection of 𝑚 co-clusterings or co-partitions (Z 𝑙 , W 𝑙 ); 𝑙 = 1, . . . , 𝑚 obtained by a given co-clustering algorithm. 𝑏) Construct a combined affinity matrix which integrates information from all basic co-clusterings by M = 1 𝑚 𝑚 𝑙=1 M 𝑙 where M 𝑙 = Z 𝑙 W ⊤ 𝑙 . 𝑐) Factorize the matrix M into a common consensus block co-clustering Q = ZW ⊤ .

  ) suggest to replace the maximization of 𝑇𝑟 ( Z ⊤ M W) by the alternated maximization of max Z ⟨M W, Z⟩ D -0.5 z and max W ⟨M ⊤ Z, W⟩ D -0.5 w .

TR45 NMI 0

 0 .69 ± 0.02 0.49 ± 0.03 0.71 ± 0.02 0.54 ± 0.03 0.75 ± 0.01 ARI 0.56 ± 0.04 0.42 ± 0.02 0.66 ± 0.05 0.44 ± 0.06 0.69 ± 0.02 PUBMED10 NMI 0.56 ± 0.01 0.49 ± 0.02 0.36 ± 0.00 0.56 ± 0.03 0.63 ± 0.01 ARI 0.44 ± 0.01 0.44 ± 0.04 0.18 ± 0.00 0.46 ± 0.04 0.52 ± 0.02 LA12 NMI 0.52 ± 0.02 0.42 ± 0.02 0.35 ± 0.00 0.45 ± 0.04 0.59 ± 0.01 ARI 0.45 ± 0.03 0.41 ± 0.03 0.17 ± 0.00 0.38 ± 0.05 0.57 ± 0.02 CLASSIC4 NMI 0.72 ± 0.00 0.67 ± 0.03 0.41 ± 0.00 0.66 ± 0.06 0.77 ± 0.01 ARI 0.71 ± 0.01 0.61 ± 0.05 0.22 ± 0.00 0.58 ± 0.11 0.78 ± 0.01 CSTR NMI 0.68 ± 0.01 0.66 ± 0.05 0.76 ± 0.00 0.69 ± 0.02 0.79 ± 0.00 ARI 0.61 ± 0.05 0.70 ± 0.05 0.80 ± 0.00 0.70 ± 0.07 0.83 ± 0.01 CLASSIC3 NMI 0.94 ± 0.00 0.94 ± 0.00 0.91 ± 0.00 0.94 ± 0.00 0.96 ± 0.00 ARI 0.97 ± 0.00 0.97 ± 0.00 0.94 ± 0.00 0.96 ± 0.00 0.98 ± 0.00 (a) NMI (b) ARI

Figure 2 :

 2 Figure 2: Comparative evaluations for CoCE and EBCO on text datasets.

Figure 3 :

 3 Figure 3: (𝑎), Partial collection selection for CLASSIC4 using modularity. Dashed lines indicate the maximum modularity percentage required. (𝑏) to (𝑒), Mean±sd clustering NMI and ARI by percentage of maximum modularity. Gray annotations give the range of co-cluster number.

Figure 4 :

 4 Figure 4: (𝑎) & (𝑐). Mean±sd clustering NMI and ARI for several partial basic co-clustering collections. Gray datapoint annotations give the inferred co-clusters number. (𝑏) & (𝑑). EBCO reorganized documents × terms matrices.

  .

6. 7 . 1

 71 EBCO co-clusters top terms. Identifying the most representative terms of each co-clustering that indicate the main topics is a challenging task. It is usual to provide a simple ordering of the co-cluster words in decreasing order of their frequency and select the most frequent words to characterize the co-cluster topics. Yet, this option can favor the appearance of none informative terms among the top terms, such as adverbs or pronouns.

6. 7 . 2

 72 Distribution of document topics in EBCO co-clusters. The Figure 5 summarizes the topics distribution for EBCO co-partitions with a number of co-clusters between 𝑔 ′ = 10 (top) and 𝑔 ′ = 7 (bottom).

Figure 5 :

 5 Figure 5: PUBMED10 topic distribution in the original dataset (left) and with EBCO co-clusterings (right; 𝑔 ′ ∈ [10..7]).

Table 1 :

 1 Description of Datasets

			Characteristics
	Datasets
		#documents #words g Sparsity (%) Balance
	SPORTS	8580	14870 7	99.14	0.036
	TR45	690	8261 10	96.60	0.088
	PUBMED10	15565	22437 10	99.72	0.093
	LA12	6279	31472 6	99.52	0.281
	CLASSIC4	7094	5896	4	99.41	0.323
	CSTR	475	1000	4	96.60	0.399
	CLASSIC3	3891	4303	3	98.95	0.710

Table 2 :

 2 Mean±sd clustering NMI and ARI. Bold values indicate the best result over all methods. SPORTS NMI 0.57 ± 0.01 0.53 ± 0.04 0.45 ± 0.00 0.57 ± 0.03 0.59 ± 0.01 ARI 0.39 ± 0.01 0.45 ± 0.06 0.30 ± 0.00 0.45 ± 0.04 0.47 ± 0.06

	Datasets	DCC	CoClustMod CoClustSpecMod CROINFO	EBCO

Table 3 :

 3 Mean±sd clustering NMI and ARI. Basic coclusterings modularity is at least 80% of the maximum collection modularity.

	Datasets		EBCO 80%	𝑔 ★ Expected 𝑔
	CLASSIC3	NMI ARI	0.95 ± 0.00 0.97 ± 0.00	3.0	3
	CSTR	NMI ARI	0.79 ± 0.00 0.83 ± 0.01	4.0	4
	CLASSIC4	NMI ARI	0.76 ± 0.02 0.76 ± 0.06	4.1	4
	LA12	NMI ARI	0.61 ± 0.02 0.59 ± 0.03	5.7	6
	SPORTS	NMI ARI	0.59 ± 0.02 0.51 ± 0.06	6.0	7

Table 4 :

 4 NPMI 𝑖 scores within top frequent word clusters for the fully unsupervised EBCO (𝑔 ★ = 7)

	Kidney Calculi								Migraine
	Jaundice		AMD		Otitis		Migraine		AMD		Hay Fever		Hepatitis A
	Gout	NPMI 𝑖		NPMI 𝑖		NPMI 𝑖		NPMI 𝑖 Raynaud Disease NPMI 𝑖		NPMI 𝑖 Chickenpox NPMI 𝑖
	uric	0.52	macular	0.61	otitis	0.48	placebo	0.34	mutation	0.42	allergic	0.55	varicella	0.57
	kidney	0.46 degeneration 0.47	pneumonia 0.44	efficacy	0.33	gene	0.39	rhinitis	0.55	zoster	0.56
	urinary	0.46	retinal	0.46	antibiotics 0.39	adverse	0.33	allele	0.39	allergy	0.54	virus	0.48
	urine	0.45	edema	0.37	bacterial	0.38 treatment 0.33	genetic	0.39	asthma	0.51	vzv	0.48
	oxalate	0.44	acuity	0.37	acute	0.38	dose	0.32	polymorphism	0.37	allergen	0.51	hepatitis	0.46
	renal	0.44	diabetic	0.37	chronic	0.37	drug	0.31	disease	0.27 immunotherapy 0.40	infection	0.43
	calcium	0.39	optic	0.33	influenza	0.32 headache 0.30	migraine	0.24	nasal	0.38	viral	0.42
	serum	0.38	visual	0.30	recurrent	0.32	effect	0.30	affect	0.23	pollen	0.38	antibodies	0.36
	acid	0.37	vision	0.27	effusion	0.32	pain	0.29	factor	0.23	symptom	0.34	immune	0.35
	gout	0.36	eye	0.26 complication 0.31	triptan	0.25	identify	0.19	skin	0.28	prevalence 0.32
	obstruction	0.32	injection	0.26	ear	0.29	treat	0.24	associate	0.19	exposure	0.25	incidence	0.28
	jaundice	0.30	laser	0.23	pathogenic 0.28	severe	0.23	analysis	0.18	cell	0.25	estimate	0.27
	lithotripsy	0.30	amd	0.22	resistant	0.25	medical	0.23	evidence	0.18	eosinophil	0.25	detect	0.22
	patient	0.29	therapy	0.21	isolate	0.20 prevention 0.23	suggest	0.18	airway	0.23	outbreak	0.21
	calculi	0.28	risk	0.21	membrane 0.20	trial	0.22	blood	0.15	seasonal	0.23	sample	0.17
	Disease	#doc.
	Gout	543
	Chickenpox	732
	Raynaud's disease 343
	Jaundice	503
	Hepatitis A	796
	Hay Fever	1517
	Kidney Calculi	1549
	AMD	3283
	Migraine	3703
	Otitis	2596

By co-partition, we mean a set of mutually exclusive and collectively exhaustive co-clusters such that each document and term are in one and only one co-cluster. Note that a co-partition is a block seriation relation.

When the clusters are by nature very unbalanced, the conscience mechanism has a regularizing effect that makes it possible to escape poor locally optimal solutions where some clusters are very big/small or even empty.

CROINFO and ITCC[START_REF] Inderjit S Dhillon | Information-theoretic co-clustering[END_REF] are equivalent, they optimise the same objective function. Further, CROINFO is a new formulation of ITCC in the spirit of clustering algorithms, both are linked to a restricted Poisson Latent Block Model[START_REF] Govaert | Mutual information, phi-squared and model-based co-clustering for contingency tables[END_REF]

http://mlda.swu.edu.cn/codes.php?name=CoCE.

ACKNOWLEDGMENTS

This work was supported by a grant overseen by the French National Research Agency (ANR-19-CE23-0002). It also received the labelling of Cap Digital and EuroBiomed competitiveness clusters.


G Bidaut

C J Stoeckert
email: stoeckrt@pcbi.upenn.edu

stem-cell-paper-bidaut-stoeckert CHARACTERIZATION OF UNKNOWN ADULT STEM CELL SAMPLES BY LARGE SCALE DATA INTEGRATION AND ARTIFICIAL NEURAL NETWORKS

Stem cells represent not only a potential source of treatment for degenerative diseases but can also shed light on developmental biology and cancer. It is believed that stem cells differentiation and fate is triggered by a common genetic program that endows those cells with the ability to differentiate into specialized progenitors and fully differentiated cells. To extract the stemness signature of several cells types at the transcription level, we integrated heterogeneous datasets (microarray experiments) performed in different adult and embryonic tissues (liver, blood, bone, prostate and stomach in Homo sapiens and Mus musculus). Data were integrated by generalization of the hematopoietic stem cell hierarchy and by homology between mouse and human. The variation-filtered and integrated gene expression dataset was fed to a single-layered neural network to create a classifier to (i) extract the stemness signature and (ii) characterize unknown stem cell tissue samples by attribution of a stem cell differentiation stage. We were able to characterize mouse stomach progenitor and human prostate progenitor samples and isolate gene signatures playing a fundamental role for every level of the generalized stem cell hierarchy.

Introduction

A wide variety of stem cell types have been recently reported to exist in several adult organs and are suspected to be present in most tissues. Well known stem cells types include hematopoietic stem cells (HSCs), neural stem cells (NSCs), myogenic progenitors (muscle), and others having a more restricted potential (such as gut and skin 1 ) The consensus among stem cell researchers is that stem cell fate decision and renewal are triggered by sev-eral mechanisms that do not completely overlap among different stem cells type in the same organism 2 , and in different species 3 . Two key questions are still unresolved: (i) Despite the knowledge of their existence, the location and differentiation capabilities of stem or progenitor cells are unknown for the vast majority adult organs ; methods to confirm the presence of stem/progenitor cells in adult tissues are needed. For instance, there is a large uncertainty on whether pancreatic beta-cell progenitor cells reside within the pancreatic ductal epithelium, the pancreatic small cells, or acinar tissue, or all of the previous 4 . (ii) The list of early markers that drive differentiation and self-renewal properties is still not agreed upon.

In this paper, we present a computational method to decipher common mechanisms of stem cells differentiation at the transcriptomic level using microarray data. We therefore integrated several datasets obtained from heterogeneous stem cells studies and trained an artificial neural network to extract a list of common gene markers triggering stem cell differentiation and fate decisions. Our hypothesis is that pathways triggering differentiation are at least partially conserved among adult stem cells/progenitors, forming a molecular signature reflecting embryonic and adult stem cells plasticity -the stemness. This hypothesis has been formulated several times 5 , and is supported by measured transcriptome data 6 , following a controversy about whether the stemnesss property could really be verified at the transcriptional level 7 . Discovering a shared signature should help characterize unknown stem cells populations, i.e. to determine whether a cell population contains stem cell/progenitors, and what is their differentiation potential/stage. In addition, the publication of a catalog of genes involved in differentiation of several cell types would be a valuable resource for stem cell researchers and developmentalists.

To extract molecular signatures for stem/progenitor cells developmental stages by gene expression profiling, we trained a multiclass single-layer linear ANN that subsequently allowed us to characterize unknown samples and position them in a hierarchy ranging from totipotent stem cells to fully differentiated cells. We tested the predictions made by our neural network using two tissues that were only partially characterized: Mouse stomach epithelium and human prostate (Figure 1). The ability of our system to generalize its classification to unknown stem cell types was assessed with a one-leave out cross-validation procedure on the training data.

ANNs represent a class of machine learning algorithm that were successfully applied to a large range of open ended problems. Their basic structure has been inspired from neurobiology and takes the form of a feed forward network of neurons modeled by a transition function. In a typical setup, an initial network topology is chosen depending on the nature of the problem; neurons are then trained for several epochs, leading to an ANN model, which is in turn applied to the classification of unknown samples. In biology, they were applied early for multiclass tumor classification in cancer discovery of cancer molecular subtypes and identification of biomarkers 8 .

To properly use a classification system on the selected dataset we consistently labeled the stem and differentiated cells in tissues according to their differentiation stage/properties using a controlled vocabulary. The hematopoietic stem cell hierarchy 5 was used as a model: in this differentiation system, the different cells identified and isolated thanks to functional assays, are hierarchically positioned according to their differentiation potentials. At top of the hierarchy is the HSC, which can give rise to all blood cells and has self-renewal capacity, and finally the various types of mature blood cells. We defined a more general model (see section Data integration) applicable to all stem cell types, including adult stem cells and embryonic stem cells. Five stages are recognized, as shown in Table 1 The whole scheme operates in three steps. First we generated a training dataset by integration of several gene expression datasets generated by the SCGAP (Stem Cell Genome Anatomy Projects) consortium in different tissues, and projected it in a predefined space of basis vectors using the technique of vector projection 9 , to group genes having similar dynamics of differentiation. We then used this integrated dataset to train a single-layer artificial multi-class neural network to classify unknown tissues potentially containing stem/progenitors cells in one of the predefined categories. Cross validation over training dataset led to 31 independent ANN models, trained independently by iteratively pulling out a tissue from the training data. The optimal number of genes to be employed in the classification was found by performing the training while reducing the number of genes used for classification. At each iteration, the top genes were retained by sorting the ANN weights and were kept before next training iteration. Classification error rate was minimized for 63 genes, and this set of genes was retained as a minimal core representing the stemness property shared by the set of stem/progenitor cells in the data. Finally, we tested the predicting power of the 31 models on two tissues not used for training that are potentially a mixture of adult and progenitor cells, namely mouse stomach progenitors 10 and human prostate progenitors 11 .

The datasets analyzed measure gene expression in mouse and human, stem or progenitor cell in various tissues at different development stages. Gene coverage varies with the type of chip (from 6K-to 18K genes, see Table 2). Data were integrated at the gene level using the NCBI Homologene database 12 and at the experimental level using a controlled vocabulary of Table 1. The resulting data matrix contains 18720 genes profiled across 82 samples in total.

The 82 arrays are grouped by tissues. A unique tissue sample is characterized by a group of at least two arrays, up to five arrays covering previously stem/progenitor cells categories A-E -this is a necessary condition to be able to perform vector projection. This lead us to a final table of 40 tissues. The inherent architecture of the neural network-based single layer system allows for detailed exploration of two important parameters: (i) ranking weights for each of the five stages allow extraction of genes reported by the classifier to be a marker for this particular stem cell stage. (ii) ranking genes on a vector y resulting from the expression projection multiplied by the corresponding weight for a given cell population (y n = w n .p n , w being the highest level neuron weight and p the expression projection) allows to delineate gene profiles critical for proper classification of this tissue. We additionally performed an analysis of highly ranked genes and statistically enriched gene ontologies (GO) for each of the stem/progenitor stage (unpublished data). A hidden layer to the architecture was not added even though it might decrease classification error because of the concern of overtraining and losing the ability to interpret the gene weights associated with each stem/progenitor cell stage. Other classifier types have also been considered but ANNs have been retained to keep the ability to rank genes according to their weights.

Material and Methods

Dataset

The dataset is an integration of stem cell transcriptional data generated by the 7 members of the SCGAP (Stem Cell Genome Anatomy Projects) consortium to train and test the system. Every SCGAP members performed large scale gene expression analysis on AffyMetrix arrays in given cell types and in two organisms, M. musculus and H. sapiens after specific purification steps (see Table 2). Data are available for interactive search on the Consortium's web portal (http://www.scgap.org), for download from every SCGAP member's web site, and in an integrated form the supportive web site (http://scann.sourceforge.net).

Data integration

Data were integrated at two level to take into account the heterogeneous nature of the consortium platforms. Data were first normalized within single datasets using iterative lowess normalization to compensate for differences in hybridization among the different platforms. The mas summarization method implemented in the bioconductor (R) software package (library affy) provided us with the expression values. We labeled the training dataset with a controlled vocabulary describing the five stem cell/progenitor differentiation stages (See Figure 1(b) and Table 1).

Vector Projection

Vector projection is a technique previously used for feature extraction in time course pancreas development gene expression data 9 . This technique allows for quick gene identification from pre-defined expression profiles that model the expected behavior of the genes we wish to isolate as most representative. In our case, vector projection captures genes with expression profiles peaking in different stem/progenitor differentiation stages for a given tissue (See Figure 1). The mathematical definition of vector projection is the inner product of a gene profile within a tissue to each model vector. We designed all model vector for the extraction of gene profile that were primarily expressed at one of the five progenitor/stem cell stage. These projection values were used to filter out genes without enough expression variation across tissues, and after filtering, projection values were presented to the ANN for training. Vector projection could be extended to extract gene profiles peaking in two or mode population -for instance to extract genes expressed during totipotency, turned off during self-renewal, and expressed again lated during lineage committed differentiation.

Missing values and Data Organization

A critical issue of the data we are analyzing are the missing values. This is particularly concerning here since projecting gene expression profiles characterized by missing value points can lead to results dramatically different from those expected. To cope with this issue, we performed vector projection using only the determined values, and re-normalize the model vector to a value of 1.0 using only the non-missing populations. After projection, the obtained dataset is organized both by tissue and projection values and reports the projection value for every stem/progenitor stem cell stage within every tissue. The projection values are then submitted to the ANN.

System Architecture and Parameters

The classifier used here is an extension of the well known single layer associative memory (Figure 1). It is characterized by a single neuronal layer holding the input weights to be learned from the data. Five neurons in total have been associated to the five levels of stem/differentiated cell hierarchy previously defined. The output for each neuron is the scalar product of the projection input by the weights: y i = N n=1 w i,n .p n , with y being the neuron output, i the neuron number, n the gene index, N the total number of genes, w i,n the nth value of the ith neuron weight, and p n the nth value of the gene expression projection to be classified. At every cross-validation step, one tissue is selected for testing and the others as a training set. A new neural network model is created (the weights are reinitialized) and the training set is presented to the network for 200 epochs. At each epoch, tissues from the training set are presented in a random order to the network, and weights are updated with a classic gradient descent-type training rule: ∆w n = a(k)[y nyd n ], w n being the current weight value, a(k) the learning rate (typically decreasing over time, we used a(k) = 1/(k + 1), k being the epoch number), y n the output and yd n the desired neuron output. Each ANN model trained during cross validation is kept and used at a later stage for final classification of unknown samples. The number of weights to be conserved is updated until a minimal classification error rate is reached during cross-validation.

We then performed the cross-validation and estimated the optimal number of features for tissue classification by iteratively reducing the number of weights (or input genes) used by the ANN during training. The sum of misclassified test samples on the 31 ANN models versus the number of genes is represented figure 2(a) and is minimized for 63 genes (16 genes on individual neurons).

Classification algorithm

For a given tissue that we wish to classify and attribute to one of the five cell types defined in Table 1, classification was performed as follows: The tissue tested must meet several conditions: At least two samples must be available to perform vector projection, a fully differentiated sample known a priori, and the second sample containing stem/progenitor cells to be characterized. The system then characterizes every sample by first assigning it to a category as described in Table 1 for each of the 31 ANN models generated during leave one out training. A consensus is given by majority voting on the 31 ANN models. To understand the biological functions involved in the various differentiation stages, we examined the genes used in the classification and the enriched ontologies with ClutrFree 14 (data not shown). curves decreased rapidly and did not revealed overtraining in the neural network, even though we went up to 200 epochs, except for one neural stem cell tissues (Mouse NSC sample 2, not pictured). We used the network to characterize two tissues potentially containing progenitors, namely human prostate and mouse stomach. Those two tissues were classified as expected by the system and are thus likely a mixture of fully differentiated cells and stem cells (Table 3). The ANN models allowed us not only to characterize unknown tissues but also to extract genes that back the classification in those categories, by ranking the genes according to their weights -a higher weight meaning the gene plays an essential role in the classification. The training of 5 neurons allowed us to extract a total of 5 gene sets, each of them related to a stem cell developmental stage (totipotent, multipotent, progenitor, lineage-committed progenitors (LCP) and differentiated cell). The analysis of markers was done on the first model given by the leave-one out run for a training on 63 genes. The top 10 genes lists ranked by weights for each population are presented Table 4. For the totipotent population, the top genes include Rbbp9, a gene that may play a role in cell proliferation and differentiation.

Results and Discussion

classification results

In the multipotent population, we found MGI:1916782 (Hopx ) -expressed in embryonic myocardium and other mesoderm, but not in endocardium or great vessels. HOP is also highly expressed in the developing heart, dependent on the cardiac-restricted homeodomain protein Nkx2.5. Inactivation of Hop in mice by homologous recombination results in a partially penetrant embryonic lethal phenotype with severe developmental cardiac defects involving the myocardium.

In tissues containing progenitor cells, we found several interesting markers: Letmd1 is an oncoprotein that has a role in the development of human breast cancer. The protein encoded by ptprm is a member of the protein tyrosine phosphatase (PTP) family which is known to be signaling molecules regulating a variety of cellular processes including cell growth, differentiation, mitotic cycle, and oncogenic transformation. We also found the cell surface antigen CD109. This is a glycosylphosphatidylinositol (GPI)-linked glycoprotein found on a subset of hematopoietic stem and progenitor cells 15 .

Other markers of interest were also found in the two other categories: In lineage-committed progenitors, 4932441K18 (FIAT ) is a transcriptional regulator of osteoblastic functions. Anxa3 encodes a protein member of the annexin family. Members of this family are involved in cellular growth, and this particular protein may play a role in anti-coagulation. Sfrp4 is a Wnt pathway inhibitor and plays a central role in cell fate decisions. We also found CD34, known to be expressed in hematopoietic stem cells, and a marker for stem cell purification (ranked 13th in the LCP category).

Interestingly, exploration of the gene list for 87 genes shows Socs2 in the top 10 genes for the Multipotent category. Socs2 is ubitiquously expressed in most tissues in M. musculus and was shown to play an important regulatory role in neural development, neural stem cell differentiation and neuronal growth 16 . It is also a growth-hormone inducible and novel inhibitor of intestinal epithelial cell proliferation and intestinal growth. It was also shown to play a role in mammary gland development and regulate the fate of mesenchymal precursor cells 17 , which is the nature of the cells we are studying here. Phenotype of Socs2-/-mice are describe therein and includes enlargement of bone and skeletal muscles.

The full list of markers obtained with the training for 63 genes is available from the supporting web site (scann.sourceforge.net).

Discussion

We present a novel approach that involved large scale integration of heterogeneous microarray datasets and pattern recognition analysis based on a vector projection technique to create a neural network-based classifier for characterization the differentiation properties of unknown stem cell tissues and extraction a molecular signature of stemness. Analysis of genes obtained by weight ranking highlighted gene product involved in several steps of cell differentiation. Thus, differentiation recruits a large panel of different genes and pathways and results from subtle expression level changes in a large number of genes. However, there is obviously more work to precisely validate the markers found. We were able to perform correct classification of unknown tissues (mouse stomach progenitors and human prostate progenitors) with a signature of 63 genes representing a core of genes involved in the differentiation process. As a natural extension of this work, we plan to include other stem cell studies publicly available on repositories such as Gene Expression Omnibus and ArrayExpress. On the technical side, we plan to improve the generalization capabilities of the classifier by boosting techniques, and make it accessible through a publicly available web server to perform the classification of unknown stem cell type. Other classifiers types will also be considered and their performance on this dataset studied.

Acknowledgments

We thank the SCGAP Consortium members for sharing data and providing insights for the analysis, and Dr Françoise Birg, Dr Patrice Dubreuil and Wahiba Gherraby for their valuable comments on the manuscript. Dr Ghislain Bidaut is funded by the Fondation pour la Recherche Médicale (FRM) and the Institut National du Cancer (INCa). This work was initially funded by grant U01 DK63481.

Figure 2 ( 5 .Figure 1 .

 251 Figure 2(a) shows the global misclassification rate versus the number of genes. The quadratic error rate for the training set and tests sets are respectively represented Figures 2(b) and 2(c). The error rate of every individual ANN trained with 63 genes is shown Figures 2(d) for the training set and the corresponding held out tissue. Misclassified tissues are pointed with an arrow. The minimal misclassification rate was obtained for 63 genes (See arrow on Figure 2(a), yielding a set of genes representing the core of stemness genes necessary for cell differentiation from ESCs to fully differentiated cells in both H. sapiens and M. musculus data. Error progression

Figure 2 .

 2 Figure 2. Classification results obtained for the ANN system.

Table 1 .

 1 Properties of the generalized stem cell hierarchy and the controlled vocabulary used for classification.

	Code	Stem Cell Type	Properties
	A	Totipotent Stem Cell	Capable of self-renewal and able to generate all cell types
	B	Multipotent Stem Cell	Capable of self-renewal and able to generate most cell types
	C	Progenitor Cell	Capable of generating several cell types
	D	Lineage-Committed Progenitor (LCP) Cell	Capable of generating a single or a restricted number of cell types
	E	Differentiated Cell	Cell displaying final phenotype

Table 2 .

 2 Summary of tissues, platforms and cover. The two last tissues marked in bold are used for testing. Stem cell categories are marked with code (From A to E), corresponding to the previously defined stem cell stages in Table1.

	Author/Lab	Tissue	Platform	N genes	Categories
	Darlington et al. (2007) 13	Mouse Embryonic Liver	Affy. 430A	12798	C,E
	Rowe et al. (unpublished)	Mouse Bone	Affy. U74 Av2, Bv2, Cv2	15127	C,D,E
	Ivanova et al. (2002) 5 Ivanova et al. (2002) 5	Human Fetal Liver (HSCs) Mouse Fetal Liver (HSC)	Affy. U95 Av2,B,C,D,E Affy. U74 Av2, Bv2, Cv2	17024 15127	B,D,E B,D,E
	Ivanova et al. (2002) 5	Mouse Adult Bone Marrow	Affy. U74 Av2, Bv2, Cv2	15127	B,C,D,E
	Ivanova et al. (2002) 5	Mouse Embryonic Stem Cells (ESCs)	Affy. U74 Av2, Bv2, Cv2	15127	A
	Ivanova et al. (2002) 5	Mouse Neural Stem Cells (NSCs)	Affy. U74 Av2, Bv2, Cv2	15127	B
	Ivanova et al. (unpublished)	Human Coord Blood (HSCs)	Affy. U133 A,B	17275	B,D
	Ivanova et al. (unpublished)	Human Adult Bone Marrow (HSCs)	Affy. U133 A,B	17275	B,D
	Ivanova et al. (unpublished) Oudes et al. (2006) 11	Mouse Adult Bone Marrow (HSCs) Human Prostate Progenitors	Affy. 430 A,B Affy. U133plus2.0	18626 18806	B,C X,E
	Mills et al. (2002) 10	Mouse Stomach progenitors	Affy. Mu11K A,B	6975	X,E
	Total: 5 distinct	12 distinct	6 distinct	18720	5 distinct

Table 3 .

 3 Classification by majority vote on the 31 Neural Network models generated for 63 genes

			Tissue to be tested	Majority Vote
			Mouse Stomach Progenitor	Progenitor
			Human Prostate Progenitor	Multipotent Stem Cells
					(b)
	Number of	100
	misclassified
	samples
		10
		10 4	10 3	10 2	10 1

Quadratic error rate for training set

	Minimum
	for 63 genes

Table 4 .

 4 Top 10 genes sets for the 5 stem cell stages ranked by weights.

	Totipotent	Multipotent	Progenitor	LCP	Diff. Cells
	Gene List	Gene List	Gene List	Gene List	Gene List

Dbn1 Procr Letmd1 Coq3 Aqp1 1110001A23Rik Gprasp2 Lrp8 Mgst1 Rhced BC053917 AI661017 Kpna3 PDZK8 Rhbdl4 5830405N20Rik Ctso Ptprm Cybb MGI:1933403 Iqwd1 Gkap1 Rbp4 Rbbp9 Wnt11 5730420B22Rik Lrrc16 Ass1 Cst7 Eif2ak3 Rbp4 Nrbp2 Itgb2 4932441K18 Nfe2 Rpp40 Adam8 Med6 Fli1 Fech Nfe2 Irak1bp1 Cd109 Anxa1 AI661017 Rbbp9 MGI:1916782 5830405N20Rik Gpr124 Gzma