Rado, Jairo Adrien Pavel

Mr Ciprian

Julien C Chauchat

Keywords: hierarchical clustering, co-clustering, Information Retrieval, the cluster hypothesis, distributed computing RDDs . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Commonly-used distance measures for numeric and binary data [4] . . . . 2.4 methods and parameter values . . . . . . . . . experimented datasets . . . . . . . . . .

Contrat de diffusion

Ce document est diffusé sous le contrat

Résume

Comme une méthode d'apprentissage automatique non supervisé, la classification automatique est largement appliquée dans des tâches diverses. Différentes méthodes de la classification ont leurs caractéristiques uniques. La classification hiérarchique, par exemple, est capable de produire une structure binaire en forme d'arbre, appelée dendrogramme, qui illustre explicitement les interconnexions entre les instances de données. Le Mots-clés: classification ascendante hiérarchique, co-clustering, recherche d'informations, l'hypothèse de cluster, calcul distribué.

Chapter 1

Introduction

Context

We are now living in an era of data. We use Twitter to share our opinions, we have Facebook to connect with our families and friends, we view job offers and profiles on LinkedIn, and we search for answers on Google. The Internet, devices and applications are part of our modern life, they make our life more convenient and comfortable. On the other hand, we contribute to provide data through them. Everyday, huge amounts of data are being generated, processed and analyzed. A new concept appeared in news and research articles, "Big Data". It refers to the challenges and technologies that address the four V's of Big Data, veracity, variety, velocity and volume, which are impossible to be processed with a common method. Among all types of data (images, logs, texts and videos) that are produced over the Web, textual data is surely one of the types that draws much attention of researchers.

Compared to other types of data, textual data is easier to generate, easier to collect and ubiquitous in every domain. Analysis on textual data allows researchers to extract public opinions on Twitter, to identify user groups on Facebook or to recommend jobs for users on LinkedIn. Text clustering is one of the analyses that applies clustering methods on textual data. It provides useful descriptive information on a collection of textual files, and is commonly used in organizing files, e.g., grouping similar documents such as news and tweets.

Information retrieval (IR) is a wide domain that extensively applies textual analysis. The general objective is to retrieve texts, which are supposed to be relevant to a given query, with efficiency and effectiveness. Commonly-used Web search engines such as Google, Bing and Yahoo! are successful IR applications. Such engines are document-based IR systems, which return a list of ranked documents in response to a user query. Some less famous engines such as Yippy1 and Carrot22 are cluster-based IR systems, which return a list of documents from a number of clusters that are presumably relevant to a user query. To address Big Data, there are challenges exposed to both IR systems in terms of computing efficiency and retrieval effectiveness.

The REQUEST Project

The REQUEST 3 project, short for REcursive QUEry and Scalable Technologies, is a French national project that finances this thesis. Its general objectives are to explore and develop technologies in the aspects of Big Data analysis, visualization and cloud computing. Seven industrial entities, Thales, SNCF, Talend, Syllabs, Altic, Aldecis Isthma, and six academic laboratories, ERIC (Lyon), LIP6 (Paris), LIMSI (Orsay), LABRI (Bordeaux), L2TI (Paris), UTT (Troyes), initially take part in this project. To address the analytics of massive volume data, REQUEST focuses on the development of scalable approaches based on NoSQL (not only SQL) storage and distributed computing. Three topics are covered in this project:

1. intelligent recursive and iterative IR, 2. scalable algorithms and distributed implementations,

new approaches of visualization.

Engaged in the work that covers topic 1 and topic 2, my team emphasizes our research with clustering methods, applications to IR, as well as scalable and distributed algorithms. Our tasks are to find scalable clustering methods, apply them in IR tasks, and implement them in a distributed manner.

Challenges

There are two types of clustering, flat clustering and hierarchical clustering. The result of a flat clustering method presents clusters without interconnections. There is no information on how clusters and how objects inside a cluster are connected. For example, given an input of six data instances, A, B, C, D, E and F, applying a flat clustering method may return two clusters, ABC and DEF. But there is no way to know whether A firstly merges with B or with C. And there is no way to know whether D is closer to E or to F. This information, however, is available in hierarchical clustering, which we consider more informative than flat clustering. In IR tasks, this character of hierarchical clustering is advantageous as it organizes a collection of documents with extra details on their connections, and thus it allows an IR system to better guide users in information seek. However, hierarchical clustering is computationally expensive. Its time complexity is O(N 3 ) for conventional agglomerative methods, and for divisive hierarchical clustering, complexity can be NP-hard. In many cases, hierarchical clustering is not preferred due to its high complexity, despite its advantageous character. It is thus essential to design an innovative method that makes the hierarchical clustering to perform correctly, using limited computing resources. The capability of an algorithm to achieve expected results using limited computing resources (such as memory and computing time) on relatively large dataset is referred to as "scalability". Nevertheless, limited by the computing procedure of the hierarchical clustering, making it scalable is not trivial.

There are many research works that try to improve the efficiency of hierarchical clustering. A common drawback of these works is that they are not generic, i.e., they work on one or a few methods, but are not applicable to other methods of the same type. We are interested in finding a generic framework that is applicable for all conventional hierarchical clustering methods. Another issue found in past works is that they either require some extra structure (for example, a clustering feature tree in the BIRCH method [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF]) or deploy a sampling procedure in order to reduce processing time. An obvious disadvantage of sampling is that it is likely to hurt the accuracy of the results. Is it possible to find a generic framework that is scalable and capable to produce deterministic results? This is one of the problems that this thesis devotes to solve for conventional hierarchical clustering.

Another clustering method, co-clustering, is also being widely studied and applied. Unlike usual clustering methods, which only group objects, a co-clustering method groups objects and their features at the same time. It outputs a number of co-clusters, each containing a subset of objects and a subset of features. For example, an individual cocluster obtained from a collection of documents is composed of a set of similar documents and a set of words that are associated to the set of documents. Co-clusters are like flat clusters. There is no information on how co-clusters and elements inside a co-cluster are connected. As there is not sufficient study on this subject in the past research works, it inspires us to look for a new approach that is capable to simultaneously group objects and features, as well as to retain the connections among elements inside a co-cluster and among co-clusters. The challenge of this task is to find such an approach.

As a branch in the domain of IR, applying clustering methods in IR tasks has been studied for many decades. Cluster-based IR applications have a fundamental assumption, the cluster hypothesis. It states that similar documents in a cluster tends to respond to the same query. There exist many works that test this hypothesis using several conventional hierarchical clustering methods. However, in terms of retrieval effectiveness, these works draw different conclusions. The difference in their conclusions are likely caused by the differences in experimental settings, experimented datasets and evaluation measures.

Performing a cluster hypothesis test using a specific clustering method allows us to know how well a query is answered to (retrieval effectiveness) and how fast a query is responded (retrieval efficiency). This knowledge is essential in understanding the performance of a clustering method in an IR task. However, the challenge is: how to perform a test on the cluster hypothesis, given the fact that there are different experimental settings, datasets and evaluation measures.

Distributed computing is becoming more and more popular in processing large datasets.

As hardware is commonly available at low cost, it is feasible to group commodity machines and use their collective computing power to handle data processing. With the aid of open source applications that are capable of handling concurrency, job scheduling and data replication, applying distributed computing becomes practical and convenient.

Still, there are many technical details to consider in practice in order to achieve efficiency and ensure computing accuracy. And the most challenging part is how to program a user-defined algorithm so that it can be correctly performed on a distributed computing platform.

Contributions

To serve the REQUEST project's objectives and to tackle the challenges, we introduce the contributions in this thesis.

• We study previous works on hierarchical clustering and co-clustering, analyze their advantages and drawbacks, propose new approaches, verify, experiment and evaluate them. The proposed algorithms are:

1. Sim_AHC [START_REF] Ah | Similarity based hierarchical clustering with an application to text collections[END_REF], the similarity-based hierarchical clustering framework.

As mentioned previously, applying AHC is prohibitively expensive due to its high complexity. To address this issue, different AHC algorithms have been proposed in past works (Section 2.2). However, these algorithms are either not generic, or their results are not deterministic due to the use of sampling.

A great interest for us is to find a framework that is generic to all conventional clustering methods and produces deterministic results. Inspired by the connection between similarities and distances, we propose Sim_AHC. It uses similarities instead of distances, and outputs a binary tree-like structure that can thoroughly illustrate the connections of sub-clusters, which are composed of data instances. This is a generic framework for seven conventional hierarchical clustering methods and it outputs deterministic results. More importantly, as its similarities are all between zero and one, a thresholding strategy can be applied to sparsify the similarity matrix in order to achieve computing efficiency.

Through our experiments, we find that the computing efficiency of Sim_AHC can be largely improved in terms of memory use and running time, with clustering quality being guaranteed. In fact, Sim_AHC clusters as well as, or better than conventional AHC methods that use distances. This holds true, even when the similarity matrix is substantially sparsified in Sim_AHC.

Besides, thanks to the usage of inner product, any kernel function can be applied in Sim_AHC. These properties make Sim_AHC superior to distancebased hierarchical clustering methods. [START_REF] Wang | Shcoclust, a scalable similarity-based hierarchical co-clustering method and its application to textual collections[END_REF], the similarity-based hierarchical co-clustering method.

SHCoClust

Interested in a hybrid approach that is capable of performing co-clustering while maintaining the connections of elements inside a co-cluster and among co-clusters, we propose SHCoClust. The output is also a binary tree-like structure. However, sub-clusters are composed of both data instances and features. This allows us to explore co-clusters that are organized by a hierarchy. When clustering texts, SHCoClust models a collection of documents as a bipartite graph, whose vertices are documents and terms. The objective is to form several sub-graphs, inside each of which vertices are closely associated. However, the associations among sub-graphs are weak. SHCoClust can be regarded as an extension of Sim_AHC applied in a space that is composed of eigenvectors of the Laplacian matrix of the bipartite graph.

In terms of clustering quality, our experiments demonstrate that SHCoClust significantly outperforms the conventional hierarchical clustering methods. In comparison to the Spectral Bipartite Co-clustering method [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], improvement in clustering quality is obtained in SHCoClust when the input similarity matrix is sparsified. Besides, SHCoClust inherits the advantageous property of Sim_AHC in attenuating high complexity. As inner product based similarities are used, its input similarity matrix can be sparsified in order to achieve better efficiency, and this strategy does not harm the clustering quality.

• Application to testing the cluster hypothesis.

We propose two tests on the cluster hypothesis, using Sim_AHC and SHCoClust, respectively. There are several interests for us to perform these tests: firstly, they allow us to understand how well and how fast a query is responded using a clustering method. Secondly, some of past works that test the cluster hypothesis conclude differently on which clustering method has better retrieval effectiveness. We are interested to provide a benchmark on this issue. Besides, we discover that only four conventional clustering methods are tested previously, leaving the conclusions on the other methods unknown. Thus the third interest of our tests is to provide a complete conclusion for all methods. Lastly, retrieval efficiency is barely discussed in these tests. As an important factor that measures performance, it is essential to provide experimental evidence on this issue. In our experiments, we examine the efficiency by addressing the impact of sparsifying the similarity matrix. Besides, comparisons between the two tests are provided in terms of retrieval effectiveness and efficiency.

In our experiments, optimal cluster Search is applied to search for the optimal cluster for a given query. We use the E-measure to evaluate retrieval effectiveness.

Similarities that are generated by linear kernel and Gaussian kernel are used in all experiments. In the test that applies Sim_AHC, we find that the average link and the Ward method are the most effective clustering methods. In contrast, in the test that applies SHCoClust, a wider rage of methods such as centroid, single link and McQuitty demonstrate better effectiveness than the others in some cases.

In terms of efficiency, we show that the retrieval effectiveness is barely affected by sparsification in both tests. Concretely, when the similarity matrix is getting more and more sparsified, retrieval effectiveness tends to be invariant.

• Implementation using a recent distributed computing platform. After comparing different distributed computing architectures, we select the Apache Spark Engine 4since it best suits our needs for computation speed and for compatibility. Utilizing its Resilient Distributed Databases (RDDs), we implement two algorithms, the distributed Sim_AHC and the distributed spectral embedding. Implementing a user-defined program in Spark is not a trivial task. Unlike in conventional programming, the performance of a Spark program is also dependent on the number partitions of RDDs, the length of RDD's lineage, the assigned number of cores, the assigned distributed memory, as well as the choice of caching or uncaching an RDD. There is no rule of thumb on how to choose these parameters, because they are really task-dependent. The only way is to explore along programming and to learn a suitable setting by experimenting. In this thesis, apart from implementation details, we also provide the learned experience in each implementation.

Thesis Outline

This thesis is composed of seven chapters, they are structure as follows:

In Chapter 2, we present state of the art, in which we detail background knowledge, related concepts, previously proposed approaches, existing techniques and software that concern (1) agglomerative hierarchical clustering, (2) co-clustering, (3) the cluster hypothesis tests and (4) distributed computing and architectures.

Chapter 3 and Chapter 4 respectively illustrate the proposed algorithms, Sim_AHC and SHCoClust. In detail, we exhibit, elaborate on and discuss mathematical deduction, computing procedures, properties, experimental verification, results and visualization.

In the experiments, we carry out text clustering tasks on several datasets. Chapter 5 presents the applications of testing the cluster hypothesis using the proposed methods. Unlike in text clustering, we use the E-measure to evaluate retrieval effectiveness in the context of optimal cluster search, and we adopt different experimental settings. This chapter is subdivided into three parts. In the first two parts, we elaborate on the proposed tests on the cluster hypothesis. In each individual part, we address two subjects: (1) a comparison of retrieval effectiveness among seven conventional hierarchical clustering methods, and (2) the impact of sparsification on retrieval effectiveness and efficiency. The third part of this chapter contributes to a comparison between the two tests on overall retrieval effectiveness and on general computing efficiency.

Chapter 6 shows the details of the distributed implementations. We present data structure, computing settings, technical problems as well as solutions.

Finally, chapter 7 concludes this thesis and exhibits research perspectives.

Notations

D a dataset D pairwise dissimilarity matrix n the number of data instances/samples m the number of data attributes/features i a row index, i = 1, . . . , n j a column index, j = 1, . . . , m A a data matrix of n-by-m K the number of desired clusters A a data matrix of n-by-m a ij a value in the i th row and the j th column of A z a partition of data instances w a partition on data attributes g the number of partitions of data instances h the number of partitions of data attributes k an index of z, k = 1, . . . , g l an index of w, l = 1, . . . , h G a bipartite graph V the set of vertices of G, v i ∈ V V i a subset of V E the set of edges d a document t a term e an edge W the adjacency matrix of G w ij an element of W D the degree matrix deg i degree of vertex v i L the graph Laplacian matrix v an eigenvector V a matrix with eigenvectors v i as columns C i a cluster y i the i-th row of V A n the scaled weighted matrix of A M the number of nonzero values in A n S a similarity matrix, S = (s ij ) i,j=1,...,n F a factorized matrix from A G a factorized matrix from A Chapter 2

State of the Art

Introduction

In the State of the Art, we present concepts, existing approaches, techniques that concern the content of this thesis in detail. As the principle tasks of this thesis are about clustering texts, so this chapter starts with fundamental knowledge on this subject. This includes the basic assumption, the base model, and commonly-used proximity measures for text clustering. After we present these concepts, an overview of popular and recent text clustering algorithms is presented. Since this thesis also concerns implementations of the proposed methods using distributed computing, we also introduce some fundamental knowledge on distributed and parallel computing. In this part, readers can have a better idea of the techniques chosen in this thesis. After presenting necessary concepts in Section 2.1, we develop three more sections in this chapter. Each is on a specific topic. These topics are the agglomerative hierarchical clustering, the co-clustering, and the tests of the cluster hypothesis.

For the agglomerative hierarchical clustering, we first introduce the conventional methods and the Lance-Williams formula. After this, several approaches of the nearest neighbor chain are illustrated. In the end of this Section, some on-line AHC algorithms, as well as the distributed and parallel approaches of AHC are presented.

The section of co-clustering starts with the approaches of the latent block model, a group of statistical models. Then the graph partitioning approach is presented. As this approach is used in SHCoClust, which is proposed in the thesis, more details of mathematical insight and properties are provided. Furthermore, several existing methods of this approach are elaborated on and compared among. This section also contains some algorithms that apply non-negative matrix factorization in co-clustering. As it is in fact related to the core method of the graph partitioning method, an explanation on this relation is given in the end of the section.

The last section of this chapter contributes to the tests of the cluster hypothesis. As this thesis proposes two new tests on this hypothesis, it is necessary to present concepts and tests on this subject. Concretely, the classic tests, the refined tests and the languagemodel-based tests are presented. In the end of this section, applications of the cluster hypothesis in IR is shortly discussed.

The objective of this chapter is to present, in details, the concepts, approaches, comparisons and discussions that are indispensable for readers to understand the content of this thesis.

Clustering Texts

2.1.1.1 The "Bag-of-Words" Assumption

Clustering textual data groups similar documents and reveals hidden connections. As textual data is more complex than numeric data, it requires to be treated differently.

There are a few assumptions for processing textual data, different assumptions lead to different approaches. The "bag-of-words" assumption is one of the most popular ones.

It considers a piece of text (or a document) as a set of words. In this assumption, the ordering of words is ignored, only their existence matters. There are other assumptions that believe the ordering of words conveys necessary information, which is taken as features in corresponding models.

Depending on the choice of assumption, clustering methods on textual data vary. In general, these methods can be categorized into distance-based algorithms, phrase-based algorithms, probabilistic generative models, textual streams methods and graph approaches.

In the scope of this thesis, we focus on the distance-based algorithms and develop our approaches on top of the bag-of-words assumption, so that we can compare our methods with past research works, most of which apply the same setting.

The Vector Space Model

Based on the bag-of-words assumption, textual data can be represented in the vector space model, in which any document in a given collection is considered as a vector with its contained unique terms (or words) as features (or attributes). In such a way, a collection of documents can be treated as a matrix, in which each row is a document vector and each column is indexed by a term. Depending on specific needs, this document-term matrix can either be binary, or filled with term weights. Commonly-used term weighting schemes are term frequency (TF), term frequency-inverse document frequency (TF-IDF) and BM25. In each scheme, a term in the vocabulary is assigned with a weight, reflecting its importance in the collection. As documents often contain different number of terms, the document-term matrix is usually normalized, standardized or scaled. If documents contain too many terms, feature reduction is necessary. It helps reduce the number of features and to transform the features into a different space, where clustering or other learning tasks can be performed with better effectiveness.

Commonly-used Proximity Measures

For distance-based algorithms and when the TF-IDF scheme is applied, cosine similarity is often used to measure the proximity between two documents d i and d j :

cosine(d i , d j ) = < d i • d j > ∥d i ∥ • ∥d j ∥ .
where < • > indicates an inner product, and ||d|| indicates the Euclidean norm of a document vector d. Under the vector space model, where documents are featured by their terms, the cosine similarity measures the angle of two document vectors in the projected space. Being 0 means that the document vectors are orthogonal, thus entirely dissimilar; and being 1 indicates that the document vectors are pointing to the same direction, they are entirely identical.

Depending on the choice of models, different proximity measures should be used. For example, when documents are represented as probability distributions over terms, Kullback-Leibler divergence [START_REF] Charu | A survey of text clustering algorithms[END_REF] is often used as a proximity measure. It measures how one probability distribution diverges from a second expected probability distribution. tering. The main idea of this approach considers low dimensional frequent term sets as cluster candidates, i.e., a frequent term set is regarded as a descriptor of a cluster. Looking for a set of carefully chosen frequent term sets is thus a clustering process, which is based on the mutual overlap of frequent sets with respect to the sets of supporting documents. Clustering with frequent phrases differs from other text clustering methods by treating a document as a string instead a bag of words. So that the ordering information of words in a document is retained. This clustering approach uses an indexing method to organize the phrases in the collection of documents, and then uses this organization to create clusters. In [START_REF] Zamir | Web document clustering: A feasibility demonstration[END_REF], the authors introduce Suffix Tree Clustering, which identifies sets of documents that share common phrases and uses this information to create clusters and to summarize their content for users.

There are other text clustering approaches, such as probabilistic document clustering and semi-supervised methods. Topic modeling is an example of probabilistic document clustering. The idea is to create a probabilistic generative model that represents a collection of documents as a function of hidden random variables, whose parameters are estimated from the document collection [START_REF] Charu | A survey of text clustering algorithms[END_REF]. PLSI (Probabilistic Latent Semantic Indexing) [START_REF] Hofmann | Probabilistic latent semantic indexing[END_REF] and LDA (Latent Dirichlet Allocation) [START_REF] David M Blei | Latent dirichlet allocation[END_REF] are two representative methods for topic modeling. Semi-supervised learning is a technique situated between supervised and non-supervised learning. With some prior but incomplete knowledge of document labels, semi-supervised learning processes such knowledge to perform a clustering or a classification task. There exist different semi-supervised approaches in text clustering.

For instance, [START_REF] Charu | On using partial supervision for text categorization[END_REF], a method that incorporates supervision in a non-supervised partitional clustering method; [START_REF] Blum | Learning to classify text from labeled and unlabeled documents[END_REF] represents a number of semi-supervised learning using probabilistic frameworks; and [START_REF] Ji | Document clustering with prior knowledge[END_REF] is a graph-based method that incorporates prior knowledge in the clustering process.

In this thesis, we focus on one of the distance-based text clustering methods, agglomerative hierarchical clustering, and one of the word-phrase-based clustering approaches, co-clustering with words and documents.

Distributed and Parallel Computing

A conventional computer program processes a given input sequentially using available resources of a single machine. If the given input is too large to fit in the memory of the machine, techniques that take advantage of concurrent computing are practically required. Bekkerman et al. [START_REF] Bekkerman | Scaling up machine learning: Parallel and distributed approaches[END_REF] point out that there are two major directions in which concurrent execution of tasks can be realized: data parallelism and task parallelism.

The former refers to executing the same computation on multiple inputs concurrently, and the latter refers to segmenting the overall algorithm into parts, some of which can be executed concurrently. With the development of hardware technologies, computing devices become cheaper and more powerful. This trend offers remarkable increase in computing capabilities to handle both data and task parallelism.

Parallel computing platform and distributed computing platform are the two types of platforms that support data parallelism and task parallelism, respectively. The parallel computing platform is characterized by organizing processing units in some structure, and by the access to shared memory via direct communication among the units. Modern parallel platforms are usually based on hybrid typologies, in which processing units are organized hierarchically, with multiple layers of shared memory [START_REF] Bekkerman | Scaling up machine learning: Parallel and distributed approaches[END_REF]. The Graphics Processing Units (GPUs) are a good example of such an architecture. GPUs are usually composed of dozens of multiprocessors, each is comprised of multiple stream processors.

These stream processors are organized in "blocks", and any individual block has access to relatively small locally shared memory and a much larger globally shared memory [START_REF] Mohammed | Large-scale parallel data mining[END_REF].

Other parallel platforms include multi-core processing and Message Passing Interface (MPI).

Compared to parallel platforms, distributed computing platforms typically have larger physical distances among processing units, for which less direct communication is usually supported by local (or remote) network. Therefore, they have higher latency and lower bandwidth. However, distributed computing platforms have advantages. For example, individual processing units can be heterogeneous. Moreover, these platforms automatically schedule jobs, synchronize, transfer and recover data (data recovery only happens when a computing unit fails to respond). MapReduce, Apache Spark, Dryad, Pregel and CIEL are a few popular distributed platforms. They actually use a distributed storage system to store data, but to a user, all the computation is like running on a single machine. Dean and Ghemawat [1], Zaharia et al. [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF], Ingersoll [START_REF] Ingersoll | Introducing apache mahout. Scalable, commercial-friendly machine learning for building intelligent applications[END_REF], Gropp [START_REF] Gropp | Tutorial on mpi: The message-passing interface[END_REF], Barney [START_REF] Barney | Openmp tutorial[END_REF] provide detailed insights on these distributed platforms.

The distributed implementations illustrated in this thesis are built on the Apache Spark Moreover, it provides user-friendly APIs (Application Programming Interfaces) and rich Machine Learning libraries for Python, R, Java and Scala. Despite many advantages, Spark is developed from the MapReduce computing scheme.

MapReduce

First introduced by J. allelized and executed on a cluster of machines. This advantage exempts programmers from the details of partitioning the input data, scheduling the executing tasks across a set of machines, handling machine failures, and managing inter-machine communication.

The machines that MapReduce functions operate on are called nodes. One node executes the master program, while the other nodes run copies of a worker program. The master is responsible for assigning tasks to workers and storing the status of assigned task on each worker. During the execution of a job, master and workers interact in both the map and the reduce phases. Dean and Ghemawat [1] summarize seven steps that are involved in executing a MapReduce job (Figure 2.2). 1. The input is firstly split into M pieces by the MapReduce library in the user program. Then many copies of the program are copied on nodes.

2. The master program is responsible to assign tasks to workers. There are M map tasks and R reduce tasks to assign. Once an idle worker is detected, a task is then assigned to it.

3. If the worker is assigned a map task, it reads from the corresponding input split, and parses the content into key-value pairs. These pairs are later passed to the user-defined map function, which outputs intermediate key-value pairs and buffers them in memory.

key-value pairs and sums up the list of occurrences for each word. The final output is a set of word-occurrences pairs.

MapReduce is an innovative programming model that is capable to process large datasets on a cluster of commodity computers. However, it suffers from considerable I/O overhead, as the intermediate key-values pairs are unavoidably written to and read from the local disk. When it performs an iterative algorithm, the processing can be greatly slowed down, as the output of the preceding iteration is stored on local disk and then read in the following iteration. Due to this reason, MapReduce is not an ideal platform for iterative algorithms.

Apache Spark

Apache Spark is an in-memory distributed computing architecture for iterative and interactive applications. The core concept of Spark are RDDs [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF], each of which is an immutable collection partitioned across a cluster of nodes. An RDD can be cached in memory. This mechanism allows each node to cache its respective slices for local com- The properties of RDDs make Spark an ideal programming model for bulk iterative algorithms [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF]. These properties are:

Type Description HadoopRDD result of reading from HDFS via function textFile() MapPartitionRDD result of calling map(), flatMap(), filter(), etc CoalescedRDD result of repartition() or coalesce() transformations PairRDD result of groupByKey(), join(), zip(), etc It is composed of a driver program and several worker nodes, which are linked by a cluster manager (this can be the Spark built-in cluster manager or Mesos or YARN).

In a cluster mode, an application runs as an independent set of processes on a cluster, and Apache Spark when they perform an iterative algorithm 9 . In the former platform, output that is generated in a preceding iteration is stored on HDFS, and the following iteration reads from HDFS to continue the computation. It is obvious that much I/O overhead is produced, which can largely slow down the computation. Differently, on the Spark platform, the intermediate output is stored in the distributed memory, allowing immediate data access for the following iterations. In this way, the computing time can be substantially shortened. This is one principle reason that makes Spark more advantageous than MapReduce in running an iterative algorithm. To a user, access to files stored on HDFS is like accessing files stored on a single machine.

Commands11 that operate on HDFS files are similar to Linux commands.

Agglomerative Hierarchical Clustering

Overview

Clustering is a major unsupervised machine learning method. As shown in Figure 2.8 Many AHC methods were proposed in the past decades. In principle, these methods can be categorized into:

• conventional AHC methods,

• nearest neighbor chain algorithms, and

• other approaches.

Apart from those methods that try to reduce the time complexity of AHC by algorithmic optimization, other methods try to improve computing efficiency by utilizing the technologies of distributed and parallel computing. According to the specific techniques, these methods can be classified into parallel methods and distributed methods.

Conventional Methods and the Lance-Williams Formula

Conventional Methods

Given a dataset of n instances, the general procedure of conventional AHC is shown in Algorithm 1. The output of this procedure is a dendrogram that grows upwards.

Data type Distance Formula

Binary

Jaccard distance In the vector space model, when documents are vectorized using the TF-IDF weighting system, values are all numeric and non-negative. Under this model, documents are actually projected into the feature space, where the projection is sphere-like. Therefore, the Euclidean distance is usually chosen to determine the dissimilarity of two document vectors. And it is our choice to compute D(C i , C j ) in the general procedure of AHC.

D jac (X, Y ) = |X △ Y |/|X ∪ Y | Dice distance D dice = |X △ Y |/(|X| + |Y |) Numeric Minkowski distance D min (X, Y ) = ( ∑ m j=1 |x j -y j | p ) 1/p Mahalanobis distance D mah (X, Y ) = ∥X -Y ∥ A = √ (X -Y )A(X -Y ) T Average distance D ave (X, Y ) = ( 1 m ∑ m j=1 (x j -y j ) 2 ) 1/2
In AHC, an essential step is to compute D(C ij , C k ) after C i and C j are merged. Shown in Figure 2.10, there are two types of methods, the graphic and the geometric. The former type uses cluster graphic representations to compute D(C ij , C k ), the single link method, the complete link method, the group average method and the weighted group average method belong to this type. The group average method is also named as average link or UPGMA (unweighted pair group method with arithmetic mean), and its weighted variation is the weighted group average method, which is also referred as the McQuitty method or WPGMA (weighted pair group method with arithmetic mean). While for the geometric methods, they use cluster centroids to determine the distance between C ij and C k . The centroid method, the median method and the Ward method are of this type. Table 2.4 lists the distance updating formulas of these methods, where

-→ c ij denotes the centroid of cluster C ij , i.e. -→ c ij = |i| -→ c i +|j| -→ c j |i|+|j|
, with |i| representing the number of members in cluster C i , and -→ ω ij denotes the median of cluster Type Method Distance updating formula

C ij with -→ ω ij = 1 2 ( -→ ω i + - → ω j ).
D(C ij , C k ) Graphic single min(d(i, k), d(j, k)) min x∈C ij ,y∈C k D(x, y) complete max(d(i, k), d(j, k)) max x∈C ij ,y∈C k D(x, y) average (n i d(i, k) + n j d(j, k))/(n i + n j ) 1 |C i ||C j | ∑ x∈C ij ,y∈C k D(x, y) weighted (d(i, k) + d(j, k))/2
Geometric centroid

√ n i d(i, k) + n j d(j, k) n i + n j - n i n j d(i, j) (n i + n j ) 2 || -→ c ij -- → c k || 2 median √ d(i, k) 2 + d(j, k) 2 - d(i, j) 4 || -→ ω ij -- → ω k || 2 Ward √ (n i + n k )d(i, k) + (n j + n k )d(j, k) -n k d(i, j) n i + n j + n k √ 2|C ij ||C k | |C ij | + |C k | • || -→ c ij --→ c k || 2

The Lance-Williams Formula

Lance and Williams [START_REF] Godfrey | A general theory of classificatory sorting strategies: Ii. clustering systems[END_REF] formulate the above-mentioned methods in a unified way and name this formulation as the Lance-Williams formula. Equation 2.1 and Table 2.5 present this formula and list the methods and their parameter values.

D(C ij , C k ) =α i D(C i , C k ) + α j D(C j , C k ) + βD(C i , C j ) + γ|D(C i , C k ) -D(C j , C k )| (2.1) Methods α i α j β γ single 1/2 1/2 0 -1/2 complete 1/2 1/2 0 1/2 average |C i | |C i |+|C j | |C j | |C i |+|C j | 0 0 McQuitty 1/2 1/2 0 0 centroid |C i | |C i |+|C j | |C j | |C i |+|C j | - |C i ||C j | (|C i |+|C j |) 2 0 median 1/2 1/2 -1/4 0 Ward |C i |+|C k | |C i |+|C j |+|C k | |C j |+|C k | |C i |+|C j |+|C k | - |C k | |C i |+|C j |+|C k | 0 Table 2.

5: Lance-Williams formula: methods and parameter values

This formula provides much convenience in computing D(C ij , C k ) using the seven conventional AHC methods, which can be applied by simply fitting corresponding parameter values into the formula. However, it does not change the complexity of storage and computation. For these methods, the computation requires O(n 2 ) storage for n initial objects, and O(n 3 ) time complexity [START_REF] Murtagh | Algorithms for hierarchical clustering: an overview[END_REF].

Nearest Neighbor Chain Approaches

Over decades, many AHC algorithms have been proposed for better efficiency. These include Sibson's SLINK algorithm [START_REF] Sibson | Slink: an optimally efficient algorithm for the single-link cluster method[END_REF], Rohlf's MST (Minimum Spanning Tree) algorithm [START_REF] James | Hierarchical clustering using minimum spanning tree[END_REF] for single link, Defays' method for complete link method [START_REF] Defays | An efficient algorithm for a complete link method[END_REF], and the reciprocal nearest neighbor methods of de Rham [START_REF] De | La classification hiérarchique ascendante selon la méthode des voisins réciproques[END_REF] and Juan [START_REF] Juan | Programme de classification hiérarchique par l'algorithme de la recherche en chaîne des voisins réciproques[END_REF]. Murtagh surveys these algorithms in [START_REF] Murtagh | Algorithms for hierarchical clustering: an overview[END_REF][START_REF] Murtagh | A survey of recent advances in hierarchical clustering algorithms[END_REF] and discusses their time and storage complexity. According to his survey, methods that use nearest neighbor chain to find reciprocal nearest neighbors have O(n 2 ) time and storage complexity. An exception is the storage complexity of the Ward method, which is O(n). Though with lower time complexity, the nearest neighbor chain approaches are not applicable for the centroid and the median methods.

Applying nearest neighbor chain (NN-chain) to perform AHC consists of two steps: (1) construct the NN-chain for each data instance and (2) look for the pairs of points that are reciprocal or mutual nearest neighbors (RNNs). Once the RNNs are found, they are These clustering methods do not generate height inversions in their dendrograms, i.e., the height of a child node is always lower than the height of its parent nodes. This can be formulated as:

D(C i , C j ) < D(C i , C k ) or D(C i , C j ) < D(C j , C k ) =⇒ D(C i , C j ) < D(C ij , C k ) (2.2)
It is a form of Bruynooghe's reducibility property [START_REF] Bruynooghe | Méthodes nouvelles en classification automatique de données taxinomiques nombreuses[END_REF]. A clustering method, whose dissimilarity matrix satisfies this property, produces a dendrogram shown as the left sub-figure in Figure 2.12. The single link, complete link, average link, the McQuitty and the Ward methods all output dendrograms of this type. The centroid and median methods, on the other hand, output dendrograms with height inversions, shown as the right sub-figure. Therefore, results of NN-chain output by these two methods cannot be guaranteed to have the same hierarchy as the conventional approaches. Müllner [START_REF] Müllner | Modern hierarchical, agglomerative clustering algorithms[END_REF] proves the correctness of the NN-chain approach. Furthermore, he proposes a generic algorithm that overcomes the inversion problem for the median and centroid methods, based on Anderberg's idea of maintaining a list of nearest neighbors for each data point [START_REF] Michael | Cluster analysis for applications[END_REF]. The major improvement of this algorithm is the transformation of the list of nearest neighbors into a cached priority queue. With such a structure, the time used for repeated minimum searches is reduced. But this modification does not really improve the complexity for the median and centroid methods. It is claimed to have a time complexity of O(n 3 ) for the median and centroid methods, and O(n 2 ) for the other methods unified by the Lance-Williams formula. As to the storage complexity, it is O(n 2 ) for all. A shortcoming of this generic approach is that, for the geometric clustering methods, they are limited to the Euclidean distance. Plus, in this approach does not explain how the inversion problem is solved for the centroid and median methods.

Fast-RNN is another work that improves the efficiency of the NN-chain approach [START_REF] Roberto | Fast reciprocal nearest neighbors clustering[END_REF]. This work adopts the RNN clustering algorithm [START_REF] Leibe | Efficient clustering and matching for object class recognition[END_REF], which has O(n 2 m) time and O(n) storage complexity. n and m denote the number of data instances and the number of features, respectively. The main innovation of fast-RNN algorithm is that, its NN-chain is constructed by a dynamic space partitioning strategy using slices. Given a predefined distance parameter ϵ, an iterative slicing procedure is applied to search for a list of nearest neighbor candidates for each data point. The candidates are interesting points that are located within a slice of width 2ϵ centered at a data point in a multi-dimensional space.

Attaching a candidate list of nearest neighbors to data point is a similar data structure used in [START_REF] Müllner | Modern hierarchical, agglomerative clustering algorithms[END_REF]. However, the way of updating proximity between a newly merged cluster and a remaining cluster differs in fast-RNN. It employs a similarity measure that uses cluster centroids. This requires tracking the mean values and variances of clusters along the clustering procedure. Though fast-RNN returns identical results as the conventional RNN algorithm with better efficiency, it has some obvious constraints. One constraint is that it needs an extra step to find a proper value for ϵ, which does not seem to be a trivial task. Besides, this method is only shown to be applicable for the average link clustering method. Limited by its proximity measure, this method is not suitable for graph methods.

Approaches for Large Datasets

Aside from algorithms that focus to decrease the complexity of AHC, there are other approaches that try to make AHC applicable for large datasets. A well-known algorithm is BIRCH [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF], which is capable to handle large datasets and is robust against outliers.

The key feature of BIRCH is its use of a clustering feature (CF) tree, which is designed to capture important clustering information in the original data while requiring less storage. After the CF tree is constructed, an AHC algorithm is applied to the set of summaries to perform global clustering. BIRCH achieves a computational complexity of O(n). Nevertheless, as BIRCH is independent from the Lance-Williams formula, it does not provide any method that is included in the formula.

Another famous algorithm is CURE [START_REF] Guha | Cure: an efficient clustering algorithm for large databases[END_REF], which applies a set of well-scattered points to represent a cluster. In this way, rich cluster shapes (other than hyperspheres) can be discovered. In addition, the chaining effect of minimum spanning tree, as well as the tendency to favor clusters with similar centroids can be avoided. CURE reduces computational complexity with a random sampling and partitioning strategy. Thus, its complexity is dependent on the size of the sampled dataset. Concretely, its time complexity is O(n 2 sample log n sample ) and its space complexity is O(n sample ). The main drawback of CURE is that its results are indeterministic due to its sampling procedures.

On-line AHC Algorithms

Apart from clustering on static datasets, some algorithms are capable to perform AHC on on-line datasets. These algorithms include MCUPGMA [START_REF] Loewenstein | Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space[END_REF] for average link, ESPRIT hcluster [START_REF] Sun | Esprit: estimating species richness using large collections of 16s rrna pyrosequences[END_REF] for single link and complete link, and SparseHC [START_REF] Nguyen | Sparsehc: a memoryefficient online hierarchical clustering algorithm[END_REF] for single link, complete link and average link.

Claimed to be a memory-efficient on-line algorithm, SparseHC scans a stored distance matrix chunk-by-chunk, compresses the information in the currently loaded chunk, then applies adjacency map (an efficient graph representation) to store unmerged cluster connections. It permits constant access to these connections for clustering with reduced computation time. This strategy empirically allows SparseHC to achieve a linear storage complexity. According to experimental results, SparseHC does decrease the memory growth. However, in terms of time complexity, only the efficiency of single link is shown improved.

Distributed and Parallel Approaches for AHC

There are various approaches that adopt distributed or parallel computing to speed up AHC. In literature, we can find parallel approaches that employ GPUs [START_REF] Shalom | An approach for fast hierarchical agglomerative clustering using graphics processors with cuda[END_REF], MPI [START_REF] Du | A novel parallelization approach for hierarchical clustering[END_REF], multi-threading [3] and multi-processing [START_REF] Hendrix | Parallel hierarchical clustering on shared memory platforms[END_REF]. For distributed approaches, there are [START_REF] Wang | Parable: A parallel random-partition based hierarchical clustering algorithm for the mapreduce framework[END_REF][START_REF] Jin | Incremental, distributed single-linkage hierarchical clustering algorithm using mapreduce[END_REF] and [START_REF] Jin | A scalable hierarchical clustering algorithm using spark[END_REF] that use MapReduce and Spark, respectively.

Parallel Approaches

Shalom et al. [START_REF] Shalom | An approach for fast hierarchical agglomerative clustering using graphics processors with cuda[END_REF] implement parallel single link and complete link clustering methods on GPU using CUDA (compute unified device architecture). Invited by NVIDIA 12 , CUDA is a parallel computing platform and application programming interface (API) that allow software developers to use GPU for general purpose processing. Du and Lin [START_REF] Du | A novel parallelization approach for hierarchical clustering[END_REF] parallelize the single link method based on MPI for multiple-instruction and multiple-data environments. Jeon and Yoon [3] propose a parallelizing scheme for multithreaded shared-memory machines to alleviate the cost of performing AHC, based on the concept of nearest neighbor chains. The proposed method allocates available threads into two groups, one for managing nearest neighbor chains, and the other for updating distance information. Hendrix et al. [START_REF] Hendrix | Parallel hierarchical clustering on shared memory platforms[END_REF] present SHRINK, a scalable algorithm that implements the single link method in OpenMP (open multi-processing). OpenMP is an API that supports multi-platform shared memory multiprocessing programming. It uses a portable, scalable model that provides programmers a flexible interface to develop parallel applications on different platforms, which vary from standard desktop computers to supercomputers. The main parallelizing strategy of SHRINK is to divide the input dataset into overlapping subsets. Dendrogram is generated for each subset using the SLINK algorithm [START_REF] Sibson | Slink: an optimally efficient algorithm for the single-link cluster method[END_REF]. A full dendrogram is eventually constructed by combining small individual dendrograms.

Distributed Approaches

Wang and Dutta [START_REF] Wang | Parable: A parallel random-partition based hierarchical clustering algorithm for the mapreduce framework[END_REF] present PARABLE, a hierarchical clustering algorithm for the MapReduce framework. It proceeds in two main steps: local hierarchical clustering on nodes using mappers and reducers, and integration of results by a dendrogram alignment technique. As this approach randomly splits data into smaller partitions in the first step, it only outputs approximate results. Jin et al. [START_REF] Jin | Incremental, distributed single-linkage hierarchical clustering algorithm using mapreduce[END_REF] formulate the single link method as an MST (minimum spanning tree) construction problem on a complete graph. This method firstly decomposes the complete graph into a set of non-overlapped subgraphs, then computes the intermediate sub-MSTs for each subgraph, and merges all sub-MSTs to output final result. Additionally, this approach can treat incremental data insertion for a separate data subset and integrate it with the existing result. The MapReduce implementation of this method achieves a significant speed up. However, evaluation of clustering quality is not given in this work. Later, Jin et al. [START_REF] Jin | A scalable hierarchical clustering algorithm using spark[END_REF] provide an extended work of [START_REF] Jin | Incremental, distributed single-linkage hierarchical clustering algorithm using mapreduce[END_REF] by offering another distributed implementation using the Spark platform.

Compared with their former work, the authors argue that, the new implementation performs significantly better in terms of performance and scalability. Still, evaluation on clustering quality is not discussed.

Co-clustering

Overview

Co-clustering is a subspace clustering method, it performs clustering in both data and feature spaces by simultaneously partitioning data instances and their attributes into subgroups, which are called co-clusters. Each co-cluster contains a subset of data instances and a subset of attributes. For example, for a gene expression dataset, a co-cluster is composed of a subset of closely grouped genes and a subset of conditions that are highly associated to the subset of genes. For a collection of documents, co-clustering returns a subset of documents mixed with a subset of "describing" terms. In research works on co-clustering, it is also named as block clustering, direct clustering, cross-clustering, simultaneous clustering, bi-clustering, two-way clustering, two-mode clustering or two-side clustering [START_REF] Govaert | Co-clustering[END_REF]. In this thesis, we use the name of co-clustering.

For over four decades, co-clustering has been applied in many different domains such as text mining, bio-informatics, Web mining, etc. In text mining, a collection of documents is usually represented as a document-term matrix. As this matrix is often sparse and of high dimensions, co-clustering offers a good solution to reduce dimensions and to summarize the data. Two widely cited works are [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] and [START_REF] Inderjit S Dhillon | Informationtheoretic co-clustering[END_REF] that respectively apply spectral Figure 2.13 presents a graph model that illustrates the process of randomized data generation in LBMs. Determined by parameter α, a is an observed variable presented in the data matrix A. z and w are latent variables that are controlled by parameters π and ρ. This process consists of:

• generating labelings z = (z 1 , . . . , z n ) into g clusters according to the categorical distribution π = (π 1 , . . . , π g ),

• generating labelings w = (w 1 , . . . , w m ) into h clusters according to the categorical distribution ρ = (ρ 1 , . . . , ρ h ), and

• generating a real value a ij for i = 1, . . . , n and j = 1, . . . , m according to the distribution f (.; α z i w j ).

Let Z and W respectively denote the possible labels z for the set of data instances and w for the set of data attributes, the probability density function of a is defined as:

f (A; θ) = ∑ (z,w∈Z×W) p(z, w)f (A|z, w; θ) (2.3)
with θ = (π, ρ, α). Three methods are proposed to estimate parameters in Equation 2.3 using its log-likelihood, they are LBVEM (the variational EM approach), LBCEM (the classification EM approach) and LBSEM (the stochastic EM-Gibbs approach) 13 .

LBVEM and LBCEM are two approximations to estimate θ based on a distribution on Z × W, denoted by R = P (z, w|A, θ). LBVEM imposes that the distribution of labels is assumed to be independent, i.e., R(z, w) = R(z)R(w) with R(z) = ∏ i q(z i ) and R(w) = ∏ j q(w j ). By maximizing an approximation of the derived likelihood through a number of iterations, LBVEM obtains cluster labels for rows and for columns in A.

LBCEM consists of inserting a classification step between E and M steps in estimating θ.

Both LBVEM and LBCEM guarantee the convergence, and they are simple to implement and scalable [START_REF] Govaert | Co-clustering[END_REF].

LBSEM is a simple adaptation to LBVEM of the standard stochastic EM algorithm [START_REF] Celeux | Stochastic versions of the em algorithm: an experimental study in the mixture case[END_REF]. However, unlike the standard method that incorporates a stochastic step between the E and the M steps to simulate missing data based on their conditional distribution, LBSEM applies a Gibbs sampling scheme to simulate the couple (z, w). This is the characteristic that makes LBSEM and LBVEM different. Unlike LBVEM, LBSEM uses no approximation, and it is less sensitive to starting values.

Depending on the data type of matrix A, several variations of LBVEM and LBCEM are derived, with incorporating suitable data distributions. For example, when A is binary, there are Bernoulli LBVEM and Bernoulli LBCEM; when A is continuous, there are Gaussian LBVEM and Gaussian LBCEM algorithms; and when A is being considered as a contingency table, there are Poinsson LBVEM and Poisson LBCEM.

When A is being considered as a contingency table, Charrad et al. [START_REF] Charrad | On the number of clusters in block clustering algorithms[END_REF] proposes a method to determine the number of co-clusters, by alternatively applying K-means algorithm on rows and on columns to form a number of co-clusters that optimize their χ 2 values.

Graph Partitioning Approaches

Unlike LBMs, graph partitioning approaches model a data matrix as an undirected bipartite graph, in which two sets of vertices are connected by a number of edges. No edge occurs between two vertices of the same set, and every edge carries a sort of association between two connected vertices. This association is measure by a value of weight. The objective of a clustering method is to divide input data instances into several groups such that instances in the same group are similar and those in different groups are dissimilar [START_REF] Von | A tutorial on spectral clustering[END_REF]. Likewise, when partitioning a bipartite graph, we aim to obtain sub-graphs such that vertices and edges in the same sub-graph are tightly associated, meanwhile vertices and edges in different sub-graphs are loosely connected. To achieve this, we need to partition the graph by removing the weak edges, that carry the least association between two sub-graphs. In graph theory, the concept that partitions a graph into two disjoint sub-graphs is cut. For two disjoint sub-graphs, V 1 and V 2 , their cut is defined as

cut(V 1 , V 2 ) = ∑ i∈V 1 ,j∈V 2 e ij (2.4)
and for K disjoint sub-graphs, V 1 , . . . , V K , their cut is defined as

cut(V 1 , . . . , V K ) = K ∑ i=1 cut(V i , V i ) with V i denoting the complement of V i , that is V i ∪ V i = V .
Von Luxburg [START_REF] Von | A tutorial on spectral clustering[END_REF] argues that when K > 2, the solution of mincut often results in separating one individual from the rest of the graph. It outputs sub-graphs of very unbalanced sizes. In practice, sub-graphs are expected to be "reasonably large". There exist two common objective functions to encode the desired scenarios: the RatioCut [START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF] and the normalized cut Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF], defined in Equation 2.5 and in Equation 2.6, respectively:

RatioCut(V 1 , . . . , V K ) = K ∑ i=1 cut(V i , V i ) |V i | (2.5) N cut(V 1 , . . . , V k ) = K ∑ i=1 cut(V i , V i ) vol(V i ) (2.6)
where |V i | denotes the number of vertices in V i , and vol(V i ) denotes the sum of degrees of all vertices in V i . The degree of a vertex is the sum of values of all its edges. The sets of sub-graph vertices satisfy

V i ∩ V j = ∅ and V 1 ∪ • • • ∪ V K = V . Equations 2.5
and 2.6 have small values if the sub-graphs V i are not too small. When cut(V i , V i ) = 1, Equations 2.5 and 2.6 respectively reach the minimum if all |V i | or all vol(V i ) coincide.

Both scenarios result in balanced sub-graphs, measured by the number of vertices or edge weights. However, minimizing either function with balancing conditions is a NP-hard task [START_REF] Wagner | Between min cut and graph bisection[END_REF]. Spectral clustering [START_REF] Von | A tutorial on spectral clustering[END_REF] provides a solution to solve relaxed versions of these problems. The co-clustering methods proposed in [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF][START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF] detail two approaches that use normalized spectral clustering by relaxing Ncut. A derived approach that applies an isoperimetric embedding is explained in [START_REF] Rege | Bipartite isoperimetric graph partitioning for data co-clustering[END_REF]. As these approaches output the same number of row-wise and column-wise clusters, resulting co-clusters are along the diagonal of the input data matrix.

In order to have a better understanding on how spectral clustering can be used as a solution in graph partitioning to perform co-clustering, we present basic concepts of spectral clustering, its mathematical insight and some state-of-the-art approaches.

Graph Laplacians, Properties and Spectral Clustering

Let G = (V, E) denote a bipartite graph constructed by a set of vertices V = (v i ) i=1,...,n and a set of edges E, and let W = (w ij ) i,j=1,...,n denote the weighted adjacency matrix of G. w ij = 0 means that vertices v i and v j are not connected, and

w ij = w ji as G is undirected. The degree of a vertex v i ∈ V is defined as deg i = ∑ n j=1
w ij , it is the sum that runs over all vertices adjacent to v i . The degree matrix D is a diagonal matrix with degrees deg 1 , . . . , deg n on the diagonal. As we start with

K = 2, thus V = V 1 ∪ V 2 . Let f = [f 1 , . . . , f n ] T denote
the partition vector defined as

f i =    +1, i ∈ V 1 , -1, i ∈ V 2 .
(2.7) Spectral clustering is favored in many applications over traditional clustering methods, as it can be solved efficiently by standard linear algebra software and has better clustering quality. The main tools for spectral clustering are graph Laplacian matrices.

Von Luxburg [START_REF] Von | A tutorial on spectral clustering[END_REF] presents two types of graph Laplacian: unnormalized and normalized. The unnormalized graph Laplacian matrix is defined as L = D -W . Details on its properties can be found in [START_REF] Mohar | The laplacian spectrum of graphs[END_REF][START_REF] Mohar | Some applications of laplace eigenvalues of graphs[END_REF]. For normalized graph Laplacian, there are two forms of matrices. One is defined as L sym = D -1/2 LD -1/2 and the other is defined as L rw = D -1 L. The former is a symmetric matrix, while the latter is closely related to random walk. Their properties are detailed in [START_REF] Rk | Spectral graph theory[END_REF]. In [START_REF] Von | A tutorial on spectral clustering[END_REF], the author summarizes some general properties of unnormalized and normalized Laplacian matrices, and several properties of L sym and L rw . As these properties are essential in understanding spectral clustering methods and graph partitioning co-clustering approaches, we present them below:

• General properties of graph Laplacian matrix.

1. For every f ∈ R n , there is

f T Lf = 1 2 n ∑ i,j=1 w ij (f i -f j ) 2 . (2.8) 2.
L is symmetric and positive semi-definite.

3. The smallest eigenvalue of L is zero, and the corresponding eigenvector is the constant one vector, e = [1, . . . , 1] T .

L has n non-negative, real-valued eigenvalues

0 = λ 1 ≤ λ 2 ≤ • • • ≤ λ n .
• Main properties of the normalized graph Laplacian matrix.

1. For every f ∈ R n , there is

f T Lf = 1 2 n ∑ i,j=1 w ij ( f i √ deg i - f j √ deg j ) 2 .
(2.9)

2. λ is an eigenvalue of L rw with eigenvector v if and only if λ is an eigenvalue of L sym with eigenvector D 1/2 v.

3. λ is an eigenvalue of L rw with eigenvector v if and only if λ and v solve the generalized eigenproblem Lv = λDv.

4. 0 is an eigenvalue of L rw with the constant one vector e as eigenvector. 0 is an eigenvalue of L sym with eigenvector D 1/2 e.

5.

L sym and L rw are positive semi-definite and have n non-negative real-valued

eigenvalues 0 = λ 1 ≤ • • • ≤ λ n .
• From eigenvalue 0 of L to the connected components.

The multiplicity14 of the eigenvalue 0 of a graph Laplacian matrix is related to the number of connected components in the bipartite graph. Given G as an undirected graph with non-negative weights on all edges, the multiplicity K of the eigenvalue 0 of L equals the number of connected components V 1 , . . . , V K in the graph. For unnormalized L and for normalized L rw , the eigenspace of eigenvalue 0 is spanned by the indicator vectors e V 1 , . . . , e V K of those components; for L sym , the eigenspace of eigenvalue 0 is spanned by the vectors

D 1/2 e V 1 , . . . , D 1/2 e V K .
Von Luxburg [START_REF] Von | A tutorial on spectral clustering[END_REF] presents an intuitive explanation on the relation stated above.

Assuming that all vertices in G are ordered according to the K connected components they belong to, the adjacency matrix W and the Laplacian matrix L thus have a block diagonal form such as

L =        L 1 L 2 . . . L K        .
Each block L i is a proper graph Laplacian on its own, and it corresponds to the i th connected component. The spectrum of L is given by the union of the spectra of L i , and the corresponding eigenvectors of L are the eigenvectors of L i . Every L i has eigenvalue 0 with multiplicity 1, and the corresponding eigenvector is the constant one vector e on the i-th connected component. Therefore, L has as many eigenvalues 0 as there are connected components, and the corresponding eigenvectors are the indicator vectors of the connected components.

• Unnormalized and normalized spectral clustering methods.

There exist many approaches that apply the properties of unnormalized and normalized Laplacian matrices to solve clustering problems. Assuming that the input dataset contains x 1 , . . . , x n instances, these approaches require a pairwise similarity matrix S = (s ij ) i,j=1,...,n with s ij = s(x i , x j ) to construct a similarity graph.

Three representative approaches are respectively represented by Algorithm 3, Algorithm 4 and Algorithm 5. The common point in these approaches is that they apply the K-means method on a transformed matrix constructed from the first K eigenvectors of a Laplacian matrix.

Algorithm 3 Spectral clustering using unnormalized L [63]

Require: Similarity matrix S ∈ R n×n , K clusters to construct 1: Construct a similarity graph G from S, let W be the weighted adjacency matrix, and let D be the diagonal matrix.

2: Compute the unnormalized Laplacian L = D -W .

3: Compute the first K eigenvectors v 1 , . . . , v K of L. 4: Let V ∈ R n×K be the matrix containing the vectors v 1 , . . . , v K as columns.

5: For i = 1, . . . , n, let y i ∈ R K be the vector corresponding to the i th row of V . 6: Cluster the points

(y i ) i=1,...,n in R K with the K-means algorithm into clusters C 1 , . . . , C K . Ensure: Clusters V 1 , . . . , V K with V i = {j|y j ∈ C i }.
Algorithm 4 Spectral clustering using L rw [START_REF] Shi | Normalized cuts and image segmentation[END_REF] Require: Similarity matrix S ∈ R n×n , K clusters to construct 1: Construct a similarity graph G from S, let W be the weighted adjacency matrix, and let D be the diagonal matrix.

2: Compute the first K eigenvectors v 1 , . . . , v K of the generalized eigenproblem (D - W )v = λDv. 3: Let V ∈ R n×K
be the matrix containing the vectors v 1 , . . . , v K as columns. 4: For i = 1, . . . , n, let y i ∈ R K be the vector corresponding to the i-th row of V . 5: Cluster the points

(y i ) i=1,...,n in R K with the K-means algorithm into clusters C 1 , . . . , C K . Ensure: Clusters V 1 , . . . , V K with V i = {j|y j ∈ C i }.
Algorithm 5 Spectral clustering using L sym [START_REF] Andrew | On spectral clustering: Analysis and an algorithm[END_REF] Require: Similarity matrix S ∈ R n×n , K clusters to construct 1: Construct a similarity graph G from S, let W be the weighted adjacency matrix, and let D be the diagonal matrix.

2: Compute the normalized Laplacian L sym = D -1/2 (D -W )D -1/2 .
3: Let V ∈ R n×K be the matrix containing the vectors v 1 , . . . , v K as columns.

4: Form the matrix U ∈ R n×K from V by normalizing the row sums to have norm 1, i.e.,

u ij = v ij √ ∑ K v 2 iK
5: For i = 1, . . . , n, let y i ∈ R K be the vector corresponding to the i-th row of U .

6: Cluster the points

(y i ) i=1,...,n in R K with the K-means algorithm into clusters C 1 , . . . , C K . Ensure: Clusters V 1 , . . . , V K with V i = {j|y j ∈ C i }.

Mathematical Insight: Spectral Graph Partitioning by Optimizing

Ncut

In order to understand how spectral clustering can solve graph partitioning by relaxing an optimization problem, we detail mathematical deduction and reasoning in this section.

We explain several graph partitioning co-clustering approaches that apply Ncut and our reasoning focuses on Ncut. This reasoning explains the mathematical formulation in Section 2.3.3.3, which SHCoClust is established on. To make it simple, we consider the simplest case, when K = 2, i.e., it is only required to cut G into two parts,

V = V 1 ∪ V 2 .
Accordingly, the objective function of minimizing Ncut becomes

min N cut(V 1 , V 2 ) = cut(V 1 , V 2 ) vol(V 1 ) + cut(V 2 , V 1 ) vol(V 2 ) . (2.10)
In Ncut, an element in the partition vector f takes a form of

f i =    √ vol(V 2 ) vol(V 1 ) , if i ∈ V 1 , - √ vol(V 1 ) vol(V 2 ) , if i ∈ V 2 .
(2.11)

The optimization problem shown in Equation 2.10 is non convex. However, with the aid of Equation 2.8, it can be converted to a convex problem.

2f T Lf = n ∑ i,j=1 x ij (f i -f j ) 2 (2.12) = ∑ i∈V 1 j∈V 2 x ij ( √ vol(V 2 ) vol(V 1 ) + √ vol(V 1 ) vol(V 2 ) ) 2 + ∑ i∈V 1 j∈V 2 x ij ( - √ vol(V 1 ) vol(V 2 ) - √ vol(V 2 ) vol(V 1 ) ) 2 (2.13) = ∑ i∈V 1 j∈V 2 x ij ( vol(V 2 ) vol(V 1 ) + vol(V 1 ) vol(V 2 ) + 2 ) + ∑ i∈V 1 j∈V 2 x ij ( vol(V 1 ) vol(V 2 ) + vol(V 2 ) vol(V 1 ) + 2 ) = ( ∑ i∈V 1 j∈V 2 x ij + ∑ i∈V 1 j∈V 2 x ij )( vol(V 1 ) vol(V 2 ) + vol(V 2 ) vol(V 1 ) + 2
) (2.14) = 2cut(V 1 , V 2 ) ( vol(V 1 ) vol(V 2 ) + vol(V 2 ) vol(V 2 ) + vol(V 2 ) vol(V 1 ) + vol(V 1 ) vol(V 1 ) ) (2.15) = 2cut(V 1 , V 2 ) ( vol(V ) vol(V 2 ) + vol(V ) vol(V 1 ) ) = 2vol(V ) ( cut(V 1 , V 2 ) vol(V 2 ) + cut(V 1 , V 2 ) vol(V 1 ) ) = 2vol(V )N cut(V 1 , V 2 ) (2.16)
Note that in Equation 2.12, x ij replaces w ij because of the relation presented in Equation 2.22. With Equation 2.11, Equation 2.12 is extended to be Equation 2.13. In Equation 2.14, applying the definition of cut explained in Equation 2.4 and expanding the scalar 2 to be two more items results in Equation 2.15. Finally, given

K = 2, vol(V ) = vol(V 1 ) + vol(V 2 )
s.t. Df ⊥ e, f T Df = vol(V ).
Note that Equation 2.11 is another constraint for the new optimization problem presented in Equation 2.17. However, with this constraint, the entries of the solution vector f are only allowed to take two particular values, making the optimization problem NP-hard.

A solution is to relax this constrain by allowing the entries in f to be reals, i.e., f i ∈ R.

With this relaxation, the optimization problem can be solved with the aid of Laplacian properties (Section 2.3.3.1). Let f = D -1/2 g, this substitution in Equation 2.17 results in

min g T D -1/2 LD -1/2 g (2.18) s.t. g ⊥ D 1/2 e, ∥g∥ 2 = vol(V ).
where

D -1/2 LD -1/2 = L sym , D 1/2 e is the first eigenvector of L sym and vol(V ) is a constant. Problem 2.
18 is in the form of the standard Rayleigh-Ritz theorem (also named Rayleigh quotient). Solution g is given by the second eigenvector of L sym , and f is in fact the second eigenvector of the generalized eigenproblem Lv = λDv.

Co-clustering Documents and Terms Using Spectral Graph Partitioning

Dhillon [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] proposes a co-clustering approach, in which a document collection is modeled as a bipartite graph and graph partitioning is applied to discover co-clusters. Let A = (a ij ) i=1,...,n.j=1,...,m denote a document-term matrix that is extracted from a collection of documents. Each element of A is a TF-IDF score, i.e.,

a ij = t ij × log ( |n| |n i |
) , where t ij denotes the frequency of term t j in document d i , |n| denotes the total number of documents in the collection, and |n i | denotes the number of documents that contain term t j . In this work, A is modeled as a bipartite graph G, whose vertices are documents and terms, and a TF-IDF score is considered as an association between a document and a

term. An interesting point presented in this work is that the author presents the concept of duality of term clustering and document clustering, and he shows how this duality is related to graph partitioning. As this method outputs the same number of clusters on documents and on terms, let us assume that both document set I and term set J

contain K clusters, with indexes l = 1, . . . , K. A document cluster is denoted by z l , with z 1 ∪ • • • ∪ z K = I and z l ∩ z l ′ = ∅, l ̸ = l ′ . A term cluster is denoted by w l , with w 1 ∪ • • • ∪ w K = J and w l ∩ w l ′ = ∅, l ̸ = l ′ .
By definition, "a given term t j belongs to a term cluster w l if its association with the document cluster z l is greater than its association with any other document cluster" [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF]. Therefore, there exists:

w l = ( t j : ∑ d i ∈z l a ij ≥ ∑ d i ∈z l ′ a ij , l ′ = 1, . . . , K ) . (2.19)
Likewise, a document cluster can be defined as:

z l = ( d i : ∑ t j ∈w l a ij ≥ ∑ t j ∈w l ′ a ij , l ′ = 1, . . . , K ) . (2.20)
Equations 2.19 and 2.20 illustrate that a given document clustering determines a term clustering, which in turn determines a better document clustering. This connection is a duality of term and document clustering. The "best" term and document clustering would correspond to a sub-graph such that the crossing edges between partitions have minimum weights. This is achieved when

cut(z 1 ∪ w 1 , . . . , z K ∪ w K ) = min V 1 ,...,V K cut(V 1 , . . . , V K ). (2.21)
As stated in Section 2.3.3, optimizing Equation 2.21 results in unbalanced clusters.

Dhillon [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] avoids this problem by minimizing Ncut (Section 2.3.3.2). He starts with a bi-partitioning problem when K = 2, then extends the approach to multi-partitioning.

However, different from the assumptions of spectral clustering (Section 2.3.3.1), this approach defines the adjacency matrix and the degree matrix respectively to be

W = [ 0 A A T 0 ] , D = [ D 1 0 0 D 2 ] (2.22) with D 1 (i, i) = ∑ j a ij and D 2 (j, j) = ∑ i a ij ,
indicating the sum of edge-weights incident on document i and on term j, respectively. This results in a Laplacian matrix

L = [ D 1 -A -A T D 2 ] . (2.23)
In Section 2.3.3.2, with K = 2, we show that the second eigenvector of the generalized eigenproblem Lv = λDv provides a real relaxation to the discrete optimization of fining the minimum normalized cut. In [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], the author uses Expressions 2.22 and 2.23 in the generalized eigenproblem to find the solution. Let vector v be a vertical combination of vector v 1 and of vector v 2 . The following equation can be derived:

[ D 1 -A -A T D 2 ] [ v 1 v 2 ] = λ [ D 1 0 0 D 2 ] [ v 1 v 2 ] . (2.24)
From Equation 2.24, it is easy to obtain:

D 1 v 1 -Av 2 = λD 1 v 1 , -A T v 1 + D 2 v 2 = λD 2 v 2 .
(2.25)

Assuming that each document contains at least one term and each term is contained at least in one document, D 1 and D 2 are then non-singular. Equation 2.25 can then be expressed as:

D 1/2 1 v 1 -D -1/2 1 Av 2 = λD 1/2 1 v 1 , -D -1/2 2 A T v 1 + D 1/2 2 v 2 = λD 1/2 2 v 2 .
(2.26) Equation 2.26 can be further simplified into:

(1 -λ)D 1/2 1 v 1 = D -1/2 1 Av 2 , (1 -λ)D 1/2 2 v 2 = D -1/2 2 A T v 1 .
(2.27)

Let µ = D 1/2 1 v 1 and ν = D 1/2 2 v 2 hold, this produces v 1 = D -1/2 1 µ and v 2 = D -1/2 2
ν. With these, Equation 2.27 can be rewritten as:

(1 -λ)µ = D -1/2 1 AD -1/2 2 ν, (1 -λ)ν = D -1/2 2 A T D -1/2 1 µ.
(2.28)

Let A n = D -1/2 1 AD -1/2 2 . Accordingly, A T n = D -1/2 2 A T D -1/2 1 holds. Let σ = (1 -λ)
Equation 2.28 becomes: to Problem 2.17 is the eigenvector that associates to the second eigenvalue, λ 2 . As

σµ = A n ν, σν = A T n µ. ( 2
σ 2 = 1 -λ 2
, the solution to Equation 2.24 is then the left and right singular vectors µ 2 and ν 2 that associate to σ 2 . µ 2 indicates the bi-partitioning of documents, while ν 2 gives the indicator of bi-partitioning for terms. The full computing procedure of this bi-partitioning approach is presented in Algorithm 6.

Though the mathematical reasoning of this approach starts from Expressions 2.22 and 2.23, in fact the final solution only depends on A n , which is much smaller than the other matrices. This is an obvious advantage.

Based on Algorithm 6, when K > 2, a multi-partitioning solution can be obtained in a recursive manner. However, in [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], a more direct approach is provided by applying Algorithm 6 Spectral Bi-partitioning on documents and terms [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] Require: An input document-term matrix A of shape n × m 1: Compute diagonal matrices D 1 and D 2 from A.

2: Compute matrix A n by A n = D -1/2 1 A n D -1/2 2
.

3: Apply SVD on A n to obtain the left and the right singular vectors µ 2 and ν 2 that associate to the second singular value σ 2 .

4: Obtain the optimal eigenvector v in the generalized eigenproblem Lv = λDv by computing

v 1 = D -1/2 1 µ 2 and v 2 = D -1/2 2
ν 2 . 5: For i = 1, . . . , n + m, let y i ∈ R be the vector corresponding to the i-th row of v. 6: Cluster the points (y i ) i=1,...,n+m with the K-means algorithm into clusters

C 1 , C 2 . Ensure: Clusters V 1 and V 2 with {V i = j|y i ∈ C i }.
K-means on a matrix that is constructed from singular vectors µ 2 , . . . , µ ⌈log K 2 ⌉+1 and ν 2 , . . . , ν ⌈log K 2 ⌉+1 . In fact, this matrix can be interpreted as projections of documents and terms in a space of R K . This is referred as "spectral embedding" [START_REF] Von | A tutorial on spectral clustering[END_REF]. Though there is nothing proved to use K-means clustering in this space to construct discrete partitions from the real valued representation y i , the Euclidean distance turns out to be a meaningful quantity. This provides favorable evidence for applying K-means to achieve multi-partitioning in [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], where the author experimentally demonstrates good clustering quality. Since the Euclidean distance is considered as a meaningful metric in spectral embedding, and clustering using K-means in this space is experimentally proven to be good, analogously, it is reasonable to apply other clustering methods, such as hierarchical clustering methods, to obtain co-clusters organized in a hierarchy.

A drawback of [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] is that there is no discussion on the computing complexity of Algorithm 6. A similar co-clustering method is proposed in [START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF]. Likewise, it also uses the left and the right singular vectors to solve the graph partitioning problem, with the purpose to obtain balanced clusters by minimizing Ncut. The major difference this approach introduces is that it constructs multi-partitioning by recursively performing bi-partitioning. Besides, a discussion on computation complexity to obtain the left and the right singular vectors is elaborated. Zha et al. [START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF] state that the computation complexity of their approach is O(CK svd M ), where C denotes the number of recursions, K svd denotes the number of singular values and M denotes the number of nonzero values in matrix A n . Usually, the computation complexity of a complete SVD process can reach O(min(nm 2 , mn 2 )) in decomposing a matrix of size n-by-m [START_REF] Holmes | Fast svd for large-scale matrices[END_REF]. However, in this work, the authors apply the Lanczos bi-diagonalization procedure [START_REF] Bai | Templates for the solution of algebraic eigenvalue problems: a practical guide[END_REF] to reduce the complexity of obtaining the left and the right singular vectors. In principle, this procedure goes through a number of iterations to compute partial SVDs. In each iteration, two matrix-vector multiplications A n µ and A T n ν are calculated. Consequently, the computation complexity of obtaining the left and the right singular vectors becomes proportional to the number of nonzero values in the input matrix A n .

The approaches proposed in [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF][START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF] are sometimes referred to "Spectral-SVD" co-clustering methods. As these approaches are based on a relaxation imposed on the optimization problem (Section 2.3.3.2), there is no guarantee on the quality of such a solution with respect to the exact solution. An good example can be found in [START_REF] Guattery | On the quality of spectral separators[END_REF], where the authors prove that Spectral-SVD methods fail to produce the best partition in a cockroach graph, which looks like a ladder with several rimes removed. To overcome this problem, Rege et al. [START_REF] Rege | Bipartite isoperimetric graph partitioning for data co-clustering[END_REF] propose the Isoperimetric Co-clustering Algorithm (ICA), which is another approach that performs co-clustering by partitioning a weighted bipartite graph. However, different from the Spectral-SVD methods that try to minimize Ncut or RatioCut, ICA heuristically minimizes the ratio of the perimeter of the bipartite graph partition and the area of the partition under an appropriate definition of graph-theoretic area. In the experiments, ICA is proven to partition the cockroach graph more effectively than the Spectral-SVD methods. However, it is also more difficult to implement.

Co-clustering Using Non-negative Matrix Factorization

Non-negative Matrix Factorization

Apart from discovering co-clusters using graph-partitioning approaches, another important branch of methods is based on matrix factorization. As in text clustering, the input TF-IDF matrices are usually non-negative, therefore non-negative matrix factorization (NMF) is much studied for clustering as well as for co-clustering.

Given a non-negative matrix A = (a ij ) i=1,...,n;j=1,...,m , NMF tries to decompose A into two non-negative matrices, such that A ≈ F G, where F ∈ R n×k and G ∈ R m×k . F and G can be obtained by solving:

min ∥A -F G T ∥ 2 s.t F, G ≥ 0. (2.30)
As the function ∥A -F G T ∥ 2 is not convex with variables F and G, it is only possible to find local minima to the optimization problem. Lee and Seung [START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF] propose "multiplicative update rules" as a method to solve the optimization problem. They claim that it is a good compromise between speed and ease of implementation, in comparison with gradient descent and conjugate gradient methods. NMF can be applied in a wide range of domains, such as image processing, recommender systems and document clustering [START_REF] Daniel | Learning the parts of objects by non-negative matrix factorization[END_REF]. If A presents a document-term matrix, NMF provides F and G as the clustering indicator matrices of documents and of terms, respectively. In this case, there are k clusters of documents and k clusters of terms. In [START_REF] Li | Nonnegative matrix factorizations for clustering: A survey[END_REF], it is shown that when the orthogonal constraint G T G = I is added, NMF becomes equivalent to K-means clustering.

Approaches for Co-clustering

Li and Ding [START_REF] Li | Nonnegative matrix factorizations for clustering: A survey[END_REF] survey a range of NMF variations, among which Tri-Factorization (TF) based methods are often used to solve co-clustering problems. Briefly, TF aims to decompose matrix A into three non-negative matrices. A formulation of TF proposed in [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF] is described as:

min ∥A -F SG T ∥ 2 s.t F T F = G T G = I and F, S, G ≥ 0 where F ∈ R n×k , S ∈ R k×c and G ∈ R m×c .
Matrix S is introduced to absorb the different scales between A, F and G. Besides, it offers increased degrees of freedom, so that lowrank matrix representation remains accurate when F returns row clusters and G returns column clusters. An obvious drawback of TF is that it is computationally expensive, due to intensive matrix multiplications. Wang et al. [START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF] propose a Fast Nonnegative Matrix

Tri-factorization (FNMTF) that reduces the computational cost by using fewer matrix multiplications. The objective function is defined as:

min ∥A -F SG T ∥ 2 s.t. F ∈ Ψ n×k , G ∈ Ψ m×c .
The main difference between TF and FNMTF is that the orthonormal constraints on F and G change. The outputs of FNMTF are matrix F for row clustering and matrix G for column clustering.

Connection Between NMF and Spectral Graph Partitioning

Ding et al. [START_REF] Ding | On the equivalence of nonnegative matrix factorization and spectral clustering[END_REF] show an interesting link between NMF and graph partitioning via spectral clustering. They prove that using graph Laplacian matrix in minimizing the objective function such as Ncut and RatioCut can be equivalently carried out via non-negative matrix factorization. Concretely, this association is introduced by inserting a division of vol(V ) to the objective function in Expression 2.17. With L = D -W and f T Df = vol(V ), a new objective function can be written as:

min f T (D -W )f f T Df s.t. Df ⊥ e. (2.31)
Recall that f = D -1/2 g is used to establish Expression 2.18. With g = D 1/2 f , the authors use a normalized vector h, such that h = g ∥g∥ , to rewrite Expression 2.31 as

min h T (I -W )h s.t. h ⊥ D 1/2 e (2.32) with W = D -1/2 W D -1/2
min ∥h - D 1/2 f ∥D 1/2 f ∥ ∥ 2 . (2.35)
This gives an equivalent solution to using spectral graph partitioning.

Distributed and Parallel Approaches

Along with approaches that try to improve computational efficiency from algorithmic aspects, there exist many methods that take advantage of hardware parallelism. Papadimitriou and Sun [START_REF] Papadimitriou | Disco: Distributed co-clustering with mapreduce: A case study towards petabyte-scale end-to-end mining[END_REF] propose DisCo, a scalable framework under which co-clustering algorithms that employ a checkerboard structure can be implemented with MapReduce.

Given a matrix A of n rows and m columns, and r and c denoting row group assignments and column group assignments, the goal of DisCo is to find r and c such that, after permutation based on r and c, the correlated sub-matrices are grouped together. As searching for the optimal group assignments is NP-hard, DisCo introduces a local search by alternating between row and column assignments while holding the other assignments fixed.

BiTM (Bi-clustering using Topological Maps) performs co-clustering based on self-organizing maps [START_REF] Sarazin | Biclustering using sparkmapreduce[END_REF]. Its implementation is built on Apache Spark. BiTM consists of a topological map and a set of observations. It iteratively looks for the column and row assignments that associate observations to the topological map. The output is a block structure.

Su et al. [START_REF] Su | Co-clusterd: a distributed framework for data co-clustering with sequential updates[END_REF] introduce sequential updates for alternate minimization co-clustering (AMCC) [START_REF] Banerjee | A generalized maximum entropy approach to bregman coclustering and matrix approximation[END_REF] and propose Co-ClusterD, a distributed framework that consists of two approaches to parallelize AMCC by (1) dividing clusters and (2) batching points. Co-ClusterD is implemented based on iMapReduce [START_REF] Zhang | imapreduce: A distributed computing framework for iterative computation[END_REF], a distributed framework on Hadoop that supports iterative algorithms.

Tests of the Cluster Hypothesis

Overview

Information retrieval (IR) is a wide domain, there are many research works that contribute in different directions. For example, collaborative IR analyses user-to-user collaboration in order to perform shared IR tasks [START_REF] Tamine | Collaborative information retrieval: Concepts, models and evaluation[END_REF][START_REF] Tamine | Collaborative information retrieval: Frameworks, theoretical models, and emerging topics[END_REF]; selective search provides perspectives on how to organize a very large document collection so that it can be searched accurately and efficiently [START_REF] Kulkarni | Selective search: Efficient and effective search of large textual collections[END_REF][START_REF] Kim | Efficient distributed selective search[END_REF]; query performance prediction is studied to estimate retrieval effectiveness in the absence of relevance judgments [START_REF] Katz | Wikipedia-based query performance prediction[END_REF][START_REF] Raviv | Query performance prediction for entity retrieval[END_REF]; and cluster-based IR systems apply clustering methods in performing IR tasks [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF][START_REF] Voorhees | The cluster hypothesis revisited[END_REF][START_REF] Croft | A model of cluster searching based on classification[END_REF].

The cluster hypothesis is the fundamental assumption of applying clustering methods in IR. This hypothesis states that "the associations between documents convey information about the relevance of documents to requests" [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF]. It implies that, for a query, relevant documents tend to be more similar to each other than the non-relevant documents.

Therefore, relevant documents are likely to appear in the same clusters. For more than four decades, different tests on the cluster hypothesis have been experimented from various aspects. They provide theoretical yet valuable knowledge in studying the retrieval effectiveness and efficiency of a target clustering method in an IR application.

Based on objectives and approaches, these tests can be categorized into classic tests, refined tests and language-model based tests.

Classic Tests

Generally speaking, classic tests can be classified into two kinds. The first kind focuses on comparing retrieval effectiveness between a specifically designed cluster based search and conventional inverted file system (IFS) search. The overlap test [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF], the nearest neighbor test [START_REF] Voorhees | The cluster hypothesis revisited[END_REF] and the density test [START_REF] El | Techniques for the measurement of clustering tendency in document retrieval systems[END_REF] are representatives of this kind. They first examine whether the cluster hypothesis characterizes the experimented collections, then compare the effectiveness of retrieving documents using a designed search strategy, against document-based search. The other kind of tests emphasizes a specific clustering family, hierarchical clustering, which is capable to explicitly reveal the connections of all documents, and is thus more informative and beneficial in retrieving documents.

While many works compare retrieval effectiveness among a set of hierarchical clustering methods, some other tests examine the different strategies of searching documents in the dendrogram output by a hierarchical clustering method.

Comparison Tests of Cluster-based and Document-based Search

Overlap Test. Jardine and van Rijsbergen [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF] test the cluster hypothesis based on the assumption that "given a query, the similarity between two relevant documents should be higher than the similarity between a relevant and a non-relevant document". They measure the overlap (or say the separation) between two similarity distributions of relevant pairs and non-relevant pairs. A collection with a low overlap value is believed to cluster strongly together for a set of queries, and relevant documents are thus better separated from non-relevant documents. Within this experimental setting, their overlap test using the Cranfield-200 collection concludes that cluster-based searches have the potential to greatly outperform IFS. The same result is obtained in a later test, in which the full Cranfield15 collection is experimented [START_REF] Joost | Document clustering: An evaluation of some experiments with the cranfield 1400 collection[END_REF].

Nearest Neighbor Test. Voorhees [START_REF] Voorhees | The cluster hypothesis revisited[END_REF] not for the CISI collection. The extent to which the cluster hypothesis characterizes a collection seems to have little effect on how well cluster searching performs as compared to a sequential search of the collection [START_REF] Voorhees | The cluster hypothesis revisited[END_REF].

Density Test. El-Hamdouchi and Willett [START_REF] El | Techniques for the measurement of clustering tendency in document retrieval systems[END_REF] propose the density test. The concept of density is defined as "the total number of postings in the collection divided by the product of the number of documents in the collection and the number of terms which have been used for the indexing the collection". For example, given a collection of n documents indexed by an average of m terms, which are selected from a vocabulary of M terms, the density is m/M . Given a collection, documents that only have a few terms from the vocabulary are unlikely have common terms with other documents. Thus they tend to have low inter-document similarities. However, when a document-term matrix is densely populated, documents tend to share a large number of terms, therefore higher similarities are expected. Based on this assumption, the density test expects that collections with high density values would give better results in clustered search than those with low values. This test is empirically demonstrated to be more correlated than the overlap and the nearest-neighbor tests, with the relative improvement posted by cluster-based retrieval [START_REF] Kurland | The cluster hypothesis in information retrieval[END_REF]. Besides, this test does not require query or relevance data, so it can be applied to test collections whose query set is unavailable.

Tests Using Hierarchical Clustering

Comparing retrieval effectiveness among different hierarchical clustering methods.

Inspired by the initial work on the cluster hypothesis [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF], many subsequent works devote their tests to examining the retrieval effectiveness of different hierarchical clustering methods. Differing from flat clustering, hierarchical clustering is more informative in revealing the internal connections among a set of input documents. It outputs a binary tree structure, named dendrogram, which is able to explicitly illustrate how individual documents are grouped. In cluster-based retrieval applications, dendrograms can illustrate how relevant documents are located, and thus can be very beneficial in guiding information seeking. In Section 2.2.1, we state that the agglomerative hierarchical clustering (AHC) is practically preferred to divisive hierarchical clustering, as the latter can be NP-hard. In testing the cluster hypothesis, many research works have extensively applied four AHC methods to compare their retrieval effectiveness. These methods are single link, complete link, average link and Ward method. However, in terms of retrieval effectiveness, results of these tests are not consistent. Griffiths et al. [START_REF] Griffiths | Hierarchic agglomerative clustering methods for automatic document classification[END_REF] claim that "average link gave the best results" in his test, while Willett [START_REF] Willett | Recent trends in hierarchic document clustering: a critical review[END_REF] concludes that single link displays the poorest performance, and that "complete link is probably the most effective method". Yet, Griffiths et al. [START_REF] Griffiths | Using interdocument similarity information in document retrieval systems[END_REF] state that "Ward's method was found to give the best overall results". In addition, discussion on computing efficiency is usually out of the scope of these works. As complexity of conventional AHC is up to O(n 3 ), efficiency is an important factor to consider in practice. Moreover, a common incompleteness of these works is that they do not cover all members in the conventional AHC family. As illustrated in Figure 2.10, there are seven conventional AHC methods, but only four of them have been tested and compared.

Comparing cluster-based searching strategies.

Based on hierarchical clustering, another branch of tests concentrates on comparisons of two different cluster-based searching strategies: top-down search and bottom-up search [START_REF] Joost | Document clustering: An evaluation of some experiments with the cranfield 1400 collection[END_REF][START_REF] Willett | Recent trends in hierarchic document clustering: a critical review[END_REF]. The result of these strategies is a cluster of documents instead of a set of ranked documents. In the top-down search, the query enters via the root of the dendrogram. It is then matched against two child clusters. The child cluster with higher query-cluster similarity is chosen to continue the search. The search moves down until it finds one cluster that satisfies a pre-defined retrieval criterion. This pre-defined retrieval criterion can be a minimal number of relevant documents contained in the cluster. Alternatively, it can be a critical similarity value, at which the similarities of query and clusters start to decrease. This searching strategy has a time complexity of O(log n). However, a general problem of this strategy is that it often produces a large cluster that contains most of relevant documents and many non-relevant documents, resulting in high recall and low precision. This problem can be avoided using the bottom-up search, which starts with leaf clusters of the dendrogram and moves up toward the root until some retrieval criterion is met. Nevertheless, this search is not efficient if there are too many documents at the leaf nodes. A recommended way is to determine a starting cluster for the search by manually selecting a single relevant document at the leaf level. However, this search strategy is likely to output a relevant cluster that has high precision but low recall. In [START_REF] Willett | Recent trends in hierarchic document clustering: a critical review[END_REF], it is stated that "bottom-up searching will generally give better results than top-down searching, especially when the very small bottom-level clusters are used".

A similar conclusion is stated in [START_REF] Croft | A model of cluster searching based on classification[END_REF], where the author proves that bottom-up search is superior to top-down search via a probabilistic model.

Optimal cluster search.

In both searching strategies, it is required to compute the similarity between a query and a cluster representative. Usually, a centroid is used as the representative of a cluster.

When the size of a cluster is small, such a representative can be considered to be a reasonable description. However, for a large cluster, it becomes less suitable to represent a cluster using a representative. Differing from the two search strategies, the optimal cluster search [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF] does not involve actual matching between a query and a cluster representative. In scanning the hierarchy of the dendrogram, a cluster is considered as the optimal cluster if it has the minimal E-measure, which is defined as

E = 1 - (β 2 + 1)P R β 2 P + R (2.36)
with P and R denoting the precision and recall, respectively. β is a parameter that balances the importance of precision and recall. It usually takes values 0.5, 1 and 2.

When β = 1, the E-measure is equivalent to the F -measure.

Compared to top-down search and bottom-up search, optimal cluster search is superior, as it adopts the (harmonic) mean of precision and recall. It avoids to retrieve either large clusters that result in high precision and low recall, or small clusters that have high recall and low precision. In addition, it is still possible to adjust between precision and recall by choosing different values for β. Another advantage of optimal cluster search is that it does not require to compute any cluster representative. In fact, it directly concerns the internal connections of documents in the dendrogram when it computes the retrieval effectiveness for a query. Thus, it eliminates the bias brought from external sources to the document hierarchy.

Refined Tests

Several recent works refine some of the classic tests by adopting a different distance measure or new experimental settings.

Smucker and Allan [START_REF] Mark | A new measure of the cluster hypothesis[END_REF] claim that the nearest neighbor test applies an insufficient measure in testing the cluster hypothesis, as it only requires documents to be locally clustered. Thus, it cannot distinguish whether a set of relevant documents are locally or globally clustered. For some similarity measures and some document collections, the nearest neighbor test may fail to detect when relevant documents do cluster well.

By modeling documents into a weighted and directed graph, this work proposes a new measure, the normalized mean reciprocal distance (nMRD), which is able to capture global document-to-document similarities. It proves to be an effective measure for testing the cluster hypothesis.

Tombros [START_REF] Tombros | The effectiveness of query-based hierarchic clustering of documents for information retrieval[END_REF] refines the overlap test and re-examines the retrieval effectiveness of hierarchical clustering in a dynamic fashion. Differing from the previous tests designed in [START_REF] Voorhees | The cluster hypothesis revisited[END_REF][START_REF] Croft | A model of cluster searching based on classification[END_REF], in which clustering is applied statically over the whole document collection prior to querying. This test applies clustering only on the top-n ranked documents, which are retrieved in response to a query. The retrieval effectiveness is then measured by optimal cluster search, and compared against an IFS. The conclusions of such dynamic cluster-based retrieval confirm that the effectiveness of optimal query-specific cluster significantly outperforms optimal IFS. Moreover, under this dynamic setting, average link outperforms single link, complete link and Ward method.

Language Model-based Tests

All the tests mentioned above are based on the "bag-of-words" assumption and the vector space model. Another set of tests on the cluster hypothesis adopt the language model [START_REF] Raiber | The correlation between cluster hypothesis tests and the effectiveness of cluster-based retrieval[END_REF][START_REF] Raiber | Exploring the cluster hypothesis, and clusterbased retrieval, over the web[END_REF]. In such a model, a document is not considered as a set of terms, but as a distribution of terms. A detailed survey on the language model can be found in [START_REF] Zhai | Statistical language models for information retrieval[END_REF].

Differing from vector space model-based tests, in which similarity/dissimilarity measures are often the Euclidean distance, the cosine similarity, the Dice coefficient, or the Jaccard coefficient. In language model-based tests, this metric is measured by the expected negative cross entropy between the documents' Dirichlet-smoothed unigram language models, i.e.,

S(d i , d j ) = exp ( -CE ( p Dir[0] d i (.)||p Dir[µ] d j (.)
))

where d i and d j are two documents, CE is the cross entropy (or Kullback-Leibler divergence), Dir is the Dirichlet smoothing, and µ is its parameter. µ is set to 1000 in [START_REF] Raiber | Exploring the cluster hypothesis, and clusterbased retrieval, over the web[END_REF].

Raiber and Kurland [START_REF] Raiber | Exploring the cluster hypothesis, and clusterbased retrieval, over the web[END_REF] model several web-scaled datasets using the language model and retest the nearest neighbor test. They conclude that "the cluster hypothesis can hold, as determined by a specific test, for large scale Web corpora to the same extend it does for newswire corpora". In comparing the retrieval effectiveness of the nearest neighbor clusters, the single link hierarchical clusters and the document-based ranking system, they state that the nearest neighbor clusters outperform the others.

Raiber and Kurland [START_REF] Raiber | Exploring the cluster hypothesis, and clusterbased retrieval, over the web[END_REF] also retest the overlap test, the density test and the nMRD test on top-n retrieved documents (n = 50, 100, 250, 500) from nine various datasets [START_REF] Raiber | The correlation between cluster hypothesis tests and the effectiveness of cluster-based retrieval[END_REF]. The objective is to find the impact of correlation between a cluster hypothesis test and the effectiveness of cluster-based retrieval. Their work reveals that the correlation between the two is influenced by the type, the size of collections, the tested methods, and the number of documents in the retrieved list.

Applications of the Cluster Hypothesis in IR

The Cluster Hypothesis provides the core assumption and theoretical base for selective search, a parsimonious retrieval strategy in IR. Selective search partitions a collection based on document similarity in order to obtain topic-based subsets, and it searches only a few subsets that are estimated to contain relevant documents for a given query [START_REF] Kulkarni | Selective search: Efficient and effective search of large textual collections[END_REF]. Compared to traditional search, which divides the collection into subsets and then processes the query against all shards in parallel, selective search outperforms its counterpart using limited computing resources. A well-studied question in selective search is how to smartly partition a collection so that documents in the same partitions are semantically similar.

Apart from academic research, commercial cluster-based retrieval systems provide alternatives to commonly-used document-based search engines. Yippy.com 17 and Car-rot2.org18 are two search engines of this genre. In responding to a query, a list of ranked documents and a list of concept clusters are returned. By clicking a cluster label, a set of child concept clusters displays. The ranked documents change accordingly, as users click the clusters that they are interested in. Compared to document-based search, this searching procedure is more navigating and helpful when user's information need is unclear.

Conclusion

In this chapter, we aim to present the state of the art that is related to the content of this thesis.

Firstly we introduce the basic knowledge on text clustering, distributed and parallel computing. Then, we emphasize on three topics: agglomerative hierarchical clustering, co-clustering and tests on the cluster hypothesis. Detailed concepts and existing approaches are presented for each topic. Concretely, in agglomerative hierarchical clustering, we introduce approaches that are most related to the methods concerned in this thesis. They are the conventional AHC methods and the Lance-Williams formula. Besides, the nearest neighbor chain approach is also presented and discussed.

With respect to co-clustering, we first present a statistical model, the latent block model.

Then, we detail the graph partitioning approach by elaborating on its properties and mathematical insight, which offer good explanations to one of the proposed methods in this thesis, the SHCoClust. Moreover, we introduce another co-clustering approach, which is based on non-negative matrix factorization. As this method is related to the Spectral-SVD methods, we believe it offers a good insight for the proposed method.

Comes lastly is the tests on the cluster hypothesis. We detail three main kinds of tests,

Chapter 3

The Similarity-based Agglomerative Hierarchical Clustering Framework

Motivation

As stated in Chapter 1, we are interested in agglomerative hierarchical clustering (AHC), as it is capable to explicitly reveal the internal connections of data instances. In this sense, it is superior to flat clustering. In addition, AHC is more efficient than its counterpart, the divisive hierarchical clustering, which can reach NP-hard. However, as mentioned in section 2.2, chapter 2, AHC methods are still computationally costly. The time complexity of computing a conventional AHC method can reach O(N 3 ). Nearest neighbor chain (NN-chain) methods are more efficient [START_REF] Murtagh | A survey of recent advances in hierarchical clustering algorithms[END_REF][START_REF] Bruynooghe | Classification ascendante hiérarchique des grands ensembles de données : un algorithme rapide fondé sur la construction des voisinages réductibles[END_REF], as their time complexity is up to

O(N 2
). Yet, as they are constrained by the reducibility property, these methods cannot work with median and centroid methods. Others methods, such ad CURE [START_REF] Guha | Cure: an efficient clustering algorithm for large databases[END_REF] and BIRCH [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF], claim to address large datasets. But they also have disadvantages. For example, CURE reduces data by random sampling and partitioning. Though it decreases time complexity to O(N 2 sample logN sample ), the results are indeterministic due to the random procedures. As to BIRCH, its time complexity is O(N ), but an extra structure, the clustering features (CF) tree, has to be employed in order to store compact summaries of the original data. A more recent approach, SparseHC [START_REF] Nguyen | Sparsehc: a memoryefficient online hierarchical clustering algorithm[END_REF], is capable to perform online AHC by principally structuring clusters with an adjacency hash map. According to experimental results, this method does decrease memory growth, but time complexity is improved only for single link. Besides, this approach is not generic, it is only applicable for single link, complete link and average link.

We are interested in a method that is generic for all conventional AHC methods, independent from any external structure, deterministic in its results and scalable. Scalability is an important property for an algorithm. In parallel and distributed computing, a scalable algorithm means that computing can be performed concurrently, so that the total running time decreases as the number of computing units increases on the same input. In a traditional computing mode, where computing is performed sequentially, a scalable algorithm can be interpreted as being capable to perform the same computing task while occupying much less resources, such as memory and running time, compared to a non-scalable algorithm on the same input. Therefore, such an algorithm can process larger datasets with limited computing resources available.

To satisfy our requirements, we propose a similarity-based agglomerative hierarchical clustering framework, Sim_AHC. It is called "a framework" as it can address all of conventional AHC methods. It is thus generic. In addition, it does not require any other external structure, nor a random sampling procedure. Therefore, its results are deterministic and it is independent from any external structure. Sim_AHC can be considered as a new expression of the Lance-Williams (LW) formula, but uses inner product-based similarities instead of distances. This change provides two important advantages.

• On one hand, as the similarities lie between 0 and 1, it is feasible to employ a filtering strategy to sparsify the input similarity. This results in less memory to store non-zero similarity values, as well as less computing time to perform clustering.

Sim_AHC is thus scalable.

• On the other hand, as similarities are based on inner products, it is possible to use different kernel functions to compute similarities. This property allows Sim_AHC to perform AHC methods on non-linearly separable datasets more effectively. This chapter is organized as follows: in Section 3.2, we detail Sim_AHC from several aspects: the mathematical deduction, its extension to kernel functions, and some advice on sparsifying the input similarity matrix. Through the mathematical deduction, the readers can have a good understanding on how we replace distances in the Lance-Williams formula with inner product similarities to produce Sim_AHC. Besides, detailed reasoning on the equivalence of the two frameworks is illustrated as well. We then show how the basic form of inner product similarity can be extended to any kernel function. Next, we point out how to correctly sparsify a general similarity matrix, which can be obtained from negative vectors. After the theoretical properties of Sim_AHC are explained, we present our experiments and results in Section 3.3. Our experiments using linear kernel and Gaussian kernel aim at testing (1) the equivalence between Sim_AHC and its counterpart, the Lance-Williams formula, and (2) the impact of sparsifying the input similarity matrix on scalability and on clustering quality. Our empirical results tested on three datasets demonstrate that Sim_AHC is equivalent to the AHC algorithm using the Lance-Williams formula. In addition, the impact of sparsifying the input similarity matrix is positive, for the gain of efficiency does not compromise clustering quality.

Concretely, clustering quality tends to be preserved as the input similarity matrix is getting more and more sparsified. It collapses when the matrix is largely sparsified at some level. Before this collapsing point, up to 90% memory usage can be freed, and up to 85% running time is saved with our tested datasets. Meanwhile, clustering quality is preserved as high as or better than using full-sized similarity matrix as input.

The Similarity-based Hierarchical Clustering Framework, Sim_AHC

In this section, we introduce Sim_AHC from several aspects. Firstly, we start with the mathematical reasoning to show how this framework is deduced and how it is equivalent to the Lance-Williams formula. Secondly, we extend the framework to kernel functions.

Lastly, we present a strategy to sparsify the input similarity matrix.

Mathematical Deduction

Assuming we are dealing with a dataset of n instances and m features, let a matrix A of shape n-by-m represent this dataset. With x and y being two row vectors from A, the Euclidean distance of x and y can be expressed as:

D Euclidean (x, y) = m ∑ i=1 (x i -y i ) 2 . (3.1)
The inner product of x and y is defined as:

⟨x, y⟩ = m ∑ i=1 x i y i . (3.2)
It is clear that the Euclidean distance of x and y can be expressed in the form of an inner product, so as the squared Euclidean distance. Using inner products, the squared Euclidean distance of x and y can be expressed as:

D 2 Euclidean = ⟨x, x⟩ + ⟨y, y⟩ -2⟨x, y⟩. (3.3)
Let us assume that the similarity between x and y, S(x, y), is defined by the inner product of their normalized form, i.

(C i , C j ) = arg min (Cx,Cy) D(C x , C y ) = arg max (Cx,Cy) ( - 1 2 D(C x , C y ) ) = arg max (Cx,Cy) [ S(C x , C y ) - 1 2 ( S(C x , C x ) + S(C y , C y ) ) ] . (3.6)
When the pair (C i , C j ) that has the largest similarity is found, C i and C j are merged into one cluster C (ij) . With C k denoting any remaining cluster, for the subsequent iterations, we show that the Lance-Williams formula can be recast as follows:

-

1 2 D(C (ij) , C k ) = S(C (ij) , C k ) - 1 2 ( S(C (ij) , C (ij) ) + (α i + α j )S(C k , C k ) ) (3.7)
where:

S(C (ij) , C k ) = α i S(C i , C k ) + α j S(C j , C k ) + βS(C i , C j ) (3.8) -γ|S(C i , C i )/2 -S(C i , C k ) -S(C j , C j )/2 + S(C j , C k )| S(C (ij) , C (ij) ) = (α i + β)S(C i , C i ) + (α j + β)S(C j , C j ). (3.9)
Formulas 3.6 and 3.7 are equivalent to (C i , C j ) = arg min (Cx,Cy) D(C x , C y ) in the conventional AHC procedure, while the recurrence formulas 3.8 and 3.9 are the counterparts of the Lance-Williams formula (Equation 2.1) that establishes our method. With S(C x , C x ) = 1 holding for all n singletons {C x }, we show below that our formulation is equivalent to the Lance-Williams formula for each clustering scheme listed in Table 2.5:

• Single link and complete link methods.

It is easy to show that Equation 3.8 reduces to S( Since α i + α j = 1 holds in Equation 3.7, then Equation 3.6 with the reduced updating rules of Equations 3.8 and 3.9 are globally equivalent to the conventional procedure. Note that, for the other methods, γ = 0, so Equation 3.8 boils down to

C (ij) , C k ) = α i S(C i , C k ) + α j S(C j , C k ) + βS(C i , C j ) -γ|S(C i , C k ) -S(C j , C k )|,
S(C (ij) , C k ) = α i S(C i , C k ) + α j S(C j , C k ) + βS(C i , C j ).
• Average link, McQuitty, centroid, median and Ward methods.

Recall that S(C x , C x ) = 1 holds for all n singletons {C x }. In Equation 3.7, when the term S(C ij , C ij ) is replaced by Equation 3.9, with some simple linear algebra manipulations, Equation 3.7 becomes:

- 1 2 D(C (ij) , C k ) = S(C (ij) , C k ) -(α i + α j + β).
With the value of the term -(α i + α j + β) being equal or greater than -1, we can divide the five clustering methods into two groups: (1) the average link, McQuitty and Ward methods that have -(α i +α j +β) = -1, and (2) the centroid and median methods who satisfy -(α i + α j + β) > -1:

1. Regarding the average link, McQuitty and Ward methods, with the aid of Table 2.5, it is not difficult to prove that -(α i + α j + β) = -1 always holds. Consequently, for these methods, Equation 3.6 with the updating rules

S(C (ij) , C k ) = α i S(C i , C k ) + α j S(C j , C k ) + βS(C i , C j ) and S(C (ij) , C (ij) ) = 1
is globally equivalent to the general AHC procedure.

2. Concerning the centroid and median methods, since α i + α j = 1 in Equation 3.7, the coefficient assigned to S(C k , C k ) vanishes. However,

α i + α j + 2β ̸ = 1
in Equation 3.9. Hence, S(C (ij) , C (ij) ) ̸ = 1. Therefore, it is important to apply the weighting system determined in Equation 3.9 for the global equivalence of the centroid and median methods to hold.

Wrapping up all particular cases discussed above, the computing procedure of Sim_AHC goes through the following steps.

• At each iteration, we solve:

(C i , C j ) = arg max (Cx,Cy) S(C x , C y ) - 1 2 ( S(C x , C x ) + S(C y , C y ) ) . (3.10)
• After having merged (C i , C j ) into C (ij) , the similarity matrix S is updated by applying the two following equations:

S(C (ij) , C k ) = α i S(C i , C k ) + α j S(C j , C k ) + βS(C i , C j ) (3.11) -γ|S(C i , C k ) -S(C j , C k )| S(C (ij) , C (ij) ) = δ i S(C i , C i ) + δ j S(C j , C j ). (3.12)
The new expression leaves the values of parameters α i , α j , β and γ unchanged as in the original Lance-Williams formula. To guarantee the equivalence for each clustering method, the values of the newly added parameters δ i and δ j can be determined freely, as long as their sum satisfies the following conditions:

δ i + δ j =          1 2
for median

|C i | 2 +|C j | 2 (|C i |+|C j |) 2
for centroid 1 for other methods.

At beginning of this Section, we use A to denote a data matrix. In a text mining task, A = {a (ij) } i=1,...,n;j=1,...,m can be considered as a document-term matrix of shape n-by-m, with n denoting the number of documents in the corpus. After some preprocessing, each document is represented by a vector of m terms. When the TF-IDF weighting strategy is applied, a ij is the TF-IDF value of the j th term in the i th document. Before input

A to Sim_AHC, it is important to perform row-wise normalization on A, so that each

S(C i , C j )- 1 2 (S(C i , C i ) + S(C j , C j ))]. This is equal to -1 2 D(C i , C j ), a negative value.

Extension to Kernel Functions

Recall that the basic assumption of Sim_AHC is Equation 3.4. The usage of inner products in Sim_AHC allows us to naturally extend its clustering methods to kernel functions [START_REF] Cristianini | An introduction to support vector machines and other kernel-based learning methods[END_REF]. Consequently, in our method, broader similarity measures can be easily employed and non-linearly separable datasets can be addressed more effectively.

Let ϕ : I → F represents a mapping from a low dimensional space to a possibly infinite dimensional space. A kernel function K on two data vectors x and y in space I is defined as K(x, y) = ⟨θ(x), θ(y)⟩. It is in fact the inner product of two mapped vectors in space F. If K is a linear kernel, the S matrix in our approach is filled with cosine similarities, and more importantly, its diagonal entries should be constant. Gaussian and Laplacian kernels satisfy this condition naturally, but other kernels must be normalized.

To generalize all cases, we obtain a normalized kernel similarity matrix by: S(x, y) = K(x, y) √ K(x, x)K(y, y) .

(3.14)

Sparsification of the Cosine Similarity Matrix

For a document-term matrix A that is filled with TF-IDF values, as TF-IDF values are non-negative, the similarity values in the resulting similarity matrix S lie between 0 and 1. However, in the general case, S can contain negative values. In that case, let m < 0 be the minimal value in S and |m| its absolute value. It is always possible to transform S in order to have non negative values using the following re-scaling operator, ∀x, y ∈ Â:

S(x, y) ← S(x, y) + |m| 1 + |m| . (3.15)
Since this mapping is monotonically increasing, S remains an inner product matrix and, in addition, its diagonal is filled with value 1.

Assuming that S is non negative, we propose to apply a simple thresholding operator that depends on a parameter τ ∈ [0, 1]. Any pair of clusters that has a similarity value below τ is considered being far enough from each other, thus their similarity is replaced by 0. Similarities that are over τ are unchanged in S. Formally, this process can be expressed as:

S(x, y) ← S(x, y)I (S(x,y)≥τ ) (3.16)
where I (S(x,y)≥τ ) = 1 if S(x, y) ≥ τ and I (S(x,y)≥τ ) = 0 otherwise.

When S exists in memory as a sparse matrix, i.e., only non-zero values are actually stored, the thresholding strategy with τ results in an S matrix sparser than the original one. Therefore, less memory is required to store S and less computing time is demanded to compute on it. However, this strategy is unsuitable for distances, even normalized distances that have value between 0 and 1. Because for distances, zero and close-to-zero values are the most important as they signify high similarity, these values have to be stored instead of being ignored.

Next, we propose to restrict the search for pairs of clusters to merge in Equation 3.10 into the following subset:

S = {(C k , C l ) : S(C k , C l ) > 0}.
This permits to reduce running time, since the bottleneck of the general AHC algorithm is actually the time used in searching for the optimal proximity value, which has O(N 2 ) time complexity.

Accordingly, we propose to replace Equation 3.10 with:

(C i , C j ) = arg max (C k ,C l )∈S S(C k , C l ) - 1 2 (S(C k , C k ) + S(C l , C l )). (3.17)
As we shall see in the next section, this approach not only dramatically reduces processing time, but also achieves better clustering results.

Experimental Verification

The goals of our experiments are to demonstrate that:

1. under the assumptions exposed previously, the framework based on Equations 3.10, 3.11 and 3.12 is equivalent to the conventional AHC procedure (Algorithm 1), and the Lance-Williams formula (Equation 2.1);

2. sparsifying the cosine similarity matrix obtained by Formula 3.16, and applying Sim_AHC (Equations 3.17, 3.11 and 3.12) considerably decreases memory use and running time, while better clustering results can be obtained.

To this end, we experiment on text clustering tasks. Indeed, hierarchical clustering is particularly interesting in this case, since it allows expressing the relationships between different topics in a collection and at different granularity levels. Moreover, cosine similarities are classic proximity functions used for documents. In addition, hierarchical document organization based on the conventional AHC procedure faces the problem of scalability, since text collections are usually large. Our experiments seek to overcome these limits.

It is important to note that our purpose is not to compare different AHC methods among each other, but rather to exemplify the properties of Sim_AHC in comparison to the conventional AHC procedure that use the Lance-Williams formula. As a consequence, the results obtained by the conventional approach serve as our baseline.

Datasets, Preprocessing and Evaluation Measures

In our experiments, we use three well-known corpora that are employed in text clustering benchmarks: Reuters-21578 Based on the "bag-of-words" assumption and the vector space model, a simple preprocessing is performed on each dataset: (1) terms that appear in less than 0.2% and in more than 95% documents in a collection are removed, (2) no stemming or lemmatization is applied on the remaining terms, no stop word is removed, (3) the TF-IDF weighting scheme is applied, and (4) l 2 normalization on each document vector is applied3 . "No.Docs" and "No.Terms" in Table 3.1 indicate the number of documents and the number of terms after preprocessing. Consequently, preprocessing generates a document-term matrix, where each row is a document vector represented by a set of terms in the columns.

We use the adjusted Rand index (ARI) and (the absolute value of) the cophenetic correlation (CC) between dendrograms to compare the clustering outputs. CC is employed to evaluate how far our dendrogram is from the one produced by the conventional AHC procedure. In this case, higher is better and the maximum value 1 means that the dendrograms are equivalent and thus represent the same hierarchy. ARI is an external assessment criterion that evaluates the quality of the clustering output in regard to a given ground-truth. It requires to flatten the dendrogram with the correct number of clusters, then the obtained partition and the ground-truth are compared to each other.

Greater ARI values imply better clustering outputs. The maximum value 1 is observed when the ground-truth is perfectly recovered.

Experiment Settings and Results

Given a document-term matrix A, two types of matrices are generated: the cosine similarity matrix S and the corresponding distance matrix D as defined by Equation 3.5.

Note that since the document-term matrix consists of non negative values, similarity values in S are all between 0 and 1 (s ∈ [0, 1]), therefore no rescaling operator is needed.

Given a clustering method, the S matrix is taken as input to Sim_AHC, while the related dense matrix D is taken as input to the conventional AHC algorithm. Consequently, two dendrograms are returned and we compute the CC in order to assess the similarity between the two outputs. Two cases are of interest: (1) when τ = 0, which means no sparsification and the dense S is used; and (2) when τ > 0 and increases, which leads to sparser and sparser S matrices.

In addition to 0, we choose other threshold values τ at the 10 th , 25 th , 50 th , 75 th and 90 th percentiles of distribution of values in S. Let k denote the rank of a percentile so that k ∈ {0, 10, 25, 50, 75, 90} with the convention that the 0 th percentile is 0. Accordingly, when k grows the k th percentile τ is greater and greater and the S matrix becomes sparser and sparser.

We experiment with two types of kernel: linear and Gaussian. The linear kernel is simply the inner product in I between normalized vectors as defined in Equation 3.4.

The Gaussian kernel between two points x, y ∈ Â is given by K(x, y) = exp(-γ∥x-y∥ 2 ).

It corresponds to a cosine measure in F. In our experiment we set γ to 1/p by default 4 .

In Figure 3.1, we show the results obtained for all seven methods on the Reuters, SMART and 20NG datasets, respectively. Results for linear and Gaussian kernels are arranged in the left and right blocks. Rows correspond to AHC methods (using their abbreviations) and columns to collections. In each graph, each point corresponds to one of the measurements listed afterwards with respect to an S matrix; the x-axis corresponds to percentile ranks (divided by 100) which define the threshold values τ (not shown); solid lines with plus signs represent the relative memory use; dashed lines with cross signs show the relative running time; and dotted lines with circle symbols indicates the absolute value of cophenetic coefficient (CC), dotted lines with triangle symbols give the ARI values. We report the curves of several measurements (y-axis) when S is progressively sparsified as the percentile rank (x-axis) increases. In addition to CC and ARI graphs (dotted lines with circle and triangle symbols, respectively), the percentage of memory use of a sparse S with respect to the dense S, i.e., memory use at τ i ̸ =0 memory use at τ =0 , and the proportion of running time when using a sparse S as compared to the dense S, i.e., running time at τ i ̸ =0 running time at τ =0 , are plotted as well (solid lines with plus symbols and dashed lines with cross symbols, respectively). Therefore, memory and processing time costs related to the full S (corresponding to the 0 th percentile where τ = 0) serve as baselines (with y-axis value of 100%). In these cases, the lower the percentages the bigger the gains.

Equivalence between Sim_AHC and the Lance-Williams Formula

In Figure 3.1, for all datasets and both kernels, CC values are all equal to one when τ = 0 (0 th percentile shown at the origin). This empirically demonstrates that our approach is equivalent to AHC using the Lance-Williams formula.

Next, as percentile rank increases, CC values generally decrease, illustrating the fact that dendrograms move away from Lance-Williams formula based results. However, when using the linear kernel, CC values generally remain high even when the majority of similarity values are removed. Concerning the Gaussian kernel, CC values drop rapidly after having thresholded 10% of the lowest similarities, but they start increasing again after this fall.

However, the single link method presents a peculiar behavior: for all collections and both kernels, it always recovers the result given by the usual AHC procedure despite the fact that 90% of the S matrix is sparsified. In other words, our framework is able to obtain the same dendrogram as the original Lance-Williams formula, but with 90% of memory usage and running time saved.

Impact of Sparsifying Similarities on Scalability

Let M ≤ N 2 be the number of non-zero cells in S. The storage cost of our approach is O(M ). The time complexity 5 is O(N M ), which indicates a linearly relationship with respect to storage complexity.

In Figure 3.1, solid lines with plus symbols give the percentage of size of the sparse S with respect to the dense S. As expected, this quantity linearly decreases as the percentile rank k grows.

Next, dashed lines with cross signs show the proportion of processing time observed with a sparse S with respect to the running time achieved with the dense S. We observe linear curves as well, which depicts the linear relationship between memory and time complexities.

The sparsification of the S matrix enables decreasing storage complexity and running time. Besides, it also has an impact on clustering quality.

Previously, we have noticed that CC values were decreasing as S was sparser and sparser.

In the following, we examine some cases in which our framework wins on both sides: scalability and quality.

Impact of Sparsifying Similarities on Clustering Quality

We focus on the quality of clustering output by analyzing ARI values. We observe that average link, McQuitty and Ward techniques work out better in general. Surprisingly, many of the best results are obtained with a very sparse S matrix and not with the full one. In Table 3 For Reuters, the best ARI value is provided by average link with a full S given by the Gaussian kernel. However, comparable performance is obtained with the same method and kernel, but with a sparse S that saves 75% memory and 62% processing time.

Concerning SMART, average link gives the best ARI value as well, but with a linear kernel. Compared to the Lance-Williams formula-based AHC algorithm, Sim_AHC obtains a higher ARI while saving 90% memory and 85% running time.

Regarding 20NG, the Ward technique with Gaussian kernel works out the best. Our method allows increasing the baseline ARI value up to 54% while consuming around half of memory and running time.

Discussion

We have introduced Sim_AHC, an equivalent formulation of the Lance-Williams formula based on cosine similarities instead of Euclidean distances. Our AHC procedure, which relies on this formulation and a sparsified cosine similarity matrix, not only has better scalability properties, but is also able to output better clustering results.

We believe that two reasons account for this phenomenon. Firstly, sparsifying the S matrix reduces the noise by removing the lowest similarity values, therefore leading to better clustering performances. Secondly, when two clusters (C i , C j ) are merged together, their respective neighborhoods (clusters having a non null similarity value with C i and C j respectively) are fused as well, so that C (ij) has a larger neighborhood than both C i and C j . Furthermore, the updating rule (Equation 3.11) allows reinforcing the similarity value of C (ij) with C k if the latter cluster belongs to both initial neighborhoods. In fact, our approach can be viewed as a sort of "transitive closure" starting with reliable seeds (the pairs with highest similarity values) and propagating similarities through "trusted" neighborhoods.

However, the main drawback of our method is that, either sparsifying S does not improve the ARI value at all (see complete link applied to Reuters with Gaussian kernel in Figure 3.1, for instance), or improvements are not regular and setting the threshold value τ becomes difficult. Further theoretical investigations should be undertaken in these respects to have a better understanding of the properties of our framework.

Conclusion

In this chapter, we introduce Sim_AHC, a similarity-based agglomerative hierarchical clustering framework. Unlike other similar methods proposed in the past, Sim_AHC is a generic framework as it covers all conventional AHC methods unified in the Lance-Williams formula. Its results are deterministic, because it does not involve any sampling process. It is also independent from any extra structure. Through mathematical reasoning and experimental verification on several text clustering tasks, we demonstrate that Sim_AHC is theoretically and empirically equivalent to the Lance-Williams formula.

However, Sim_AHC can be easily extended to kernel functions, as it uses inner product at base. This features makes it capable to address non-linearly separable datasets more effectively, unlike the Lance-Williams formula. More importantly, having all similarities between 0 and 1 in this framework helps set up a threshold value to sparsify the input similarity matrix, in order to reduce memory use and running time. Our experiments show that up to 85% running time and 90% memory use can be spared using Sim_AHC.

Surprisingly, the efficiency gain does not compromise clustering quality, which tends to remain constant or even improve compared to using a full-sized input. This discovery proves that Sim_AHC is scalable, as it is capable to obtain the same or better results while using limited computing resources.

In the next chapter, we introduce a variation of Sim_AHC that is capable to group both documents and terms.

Chapter 4

The Similarity-based Hierarchical Co-clustering Method

Motivation

Introduced in Section 2.3 of Chapter 2, co-clustering is a subspace clustering method that simultaneously groups data instances and their features. It results in a number of co-clusters, each of which contains a partition of closely situated data instances and a partition of highly associated features. Depending on the content of an input dataset, data instances and their features coexist in the same co-cluster interpret each other accordingly. For example, performing co-clustering on a gene expression dataset, where genes are featured by a set of conditions, produces co-clusters, each containing a subgroup of genes that exhibit highly correlated activities for a subgroup of conditions [START_REF] Sara | Biclustering algorithms for biological data analysis: a survey[END_REF]; for a textual dataset, where documents are featured by a set of terms, co-clustering can find "describing" terms for similar documents in a co-cluster.

We believe that this advantageous property of co-clustering provides interesting insights.

For instance, when applying in cluster-based IR tasks, co-clustering can retrieves not only documents but also terms, providing useful extra knowledge in seeking information.

However, knowledge on how co-clusters and how elements in a co-cluster are connected is absent. We are interested in a method that is able to organize co-clusters and elements in a co-cluster, illustrating their interconnections. This is our initial motivation to work on a hierarchical co-clustering method.

Previously, in 2.3 of Chapter 2, we review a number of co-clustering techniques. In principle, three groups of methods are presented: LBMs, graph partitioning approaches and NMF-based approaches. Comparing these methods, we choose to build a hierarchical co-clustering method using Spectral-SVD, which is applied in some of the graph partitioning approaches. Our reasons are: first of all, Spectral-SVD-based graph partitioning approaches are more likely to be combined with a hard clustering method. However, to LBMs and NMF-based approaches, embedding an external clustering method in them is not trivial. Secondly, our basic assumption is the "bag-of-words" assumption and the vector space model, we consider a document as a set of terms instead of a distribution.

Thus it is not very suitable to choose LBMs, which are dependent on the distribution of the input. LBMs are more suitable for the assumption of language model, where document is considered as a distribution of terms. In fact, based on the relation, σ 2 = 1λ 2 , where λ 2 indicates the second eigenvalue of L sym , and σ 2 denotes the second singular value of A n , the second eigenvector of L sym and the second left and right singular vectors of A n provide the equivalent solution to the relaxed optimization problem of Ncut. However, compared to looking for the second left and right singular vectors of A n , solving the problem using the second eigenvector of L sym requires to perform computation on a much larger matrix, see Equation 2.23. In order to achieve better performance, we prefer to look for the singular vectors of A n .

For multi-partitioning, where several sub-graphs (or clusters) are generated, there are two options: either recursively performing bi-partitioning, or applying a flat clustering method, such as K-means, on the resulted matrix composed by singular vectors. Comparing the two options, the second one is preferred, as recursively performing bi-partitioning is more computationally expensive than applying a flat clustering method. Moreover, the second option provides possibility to apply any other clustering method rather than K-means.

In the multi-partitioning case of Algorithm 6, applying K-means method returns flat co-clusters, which are of the same level. It is thus not possible to know how co-clusters are connected. In addition, inside such a co-cluster, the documents and terms are also of the same level, there is no information on how they are linked. Differently, AHC or Sim_AHC outputs a dendrogram. This is a binary tree structure that can display how documents are merged step by step. However, the connection among terms is ignored. It would be very interesting to have a hybrid structure that is capable to return co-clusters, and to display the connections of clustered documents and terms in a co-cluster, as well as to preserve the information on how co-clusters are linked at different levels. We believe that this hybrid structure that combines the properties of co-clustering and hierarchical clustering is more beneficial than any the contributing method. It surely provides us a better understanding of our data.

For such purpose, we propose SHCoClust, a similarity-based hierarchical co-clustering method. It is inspired by the Spectral Bi-partitioning Co-clustering algorithm [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], in the sense that it applies "spectral embedding" to project the input data into a space constructed by the singular vectors, then it performs clustering on the projected data in order to obtain real cluster labels for the input. Differently, we perform Sim_AHC on the projected data with the purpose to organize co-clusters and elements in an individual co-cluster in a form of dendrogram. The principle reason of choosing Sim_AHC over the conventional AHC method is that we are interested to make advantage of its scalability property. In addition, its compatibility with kernel functions makes it more favored over the conventional method.

The input to SHCoClust is a square data matrix. In the scope of this thesis, we address text clustering tasks, thus our input is a document-term matrix, denoted by A. Let n and m denote the number of rows and the number of columns of A, they also signify the number of documents and the number of terms. The computing procedure of SHCoClust is presented in Algorithm 8.

Algorithm 8 Computing procedure of SHCoClust

Require: An input document-term matrix A of shape n × m 1: Compute diagonal matrices D 1 and D 2 from A.

2: Compute matrix A n by A n = D -1/2 1 × A × D -1/2 2
.

3: Apply SVD on A n to obtain l left singular vectors, µ 1 , µ 2 , . . . , µ l , and l right singular vectors ν 1 , ν 2 , . . . , ν l .

4: Construct matrix U by µ 2 , . . . , µ l , and matrix V by ν 2 , . . . , ν l . 5: Apply matrix multiplication

D -1/2 1 × U and D -1/2 2
× V to output Z 1 and Z 2 . 6: Vertically combine Z 1 and Z 2 to output matrix Z. 7: For i = 1, . . . , n + m, let y i ∈ R be the vector corresponding to the i-th row of Z. 8: Apply l 2 normalization on Z, and compute pairwise similarity matrix S from it. 9: Re-scale S by Formula 3.15. 10: while num_iterations< n do 11:

Search for the pair of rows (Z i , Z j ) that has the maximal similarity in S, by Equation 3.10,

12:

Merge Z i and Z j into Z (ij) and add a corresponding parent node in the dendrogram with height value [S(Z i , Z j ) -1 2 (S(Z i , Z i ) + S(Z j , Z j ))],

13:

Compute the similarity of Z (ij) and any other row Z k and update S accordingly, by Equations 3.11 and 3.12.

14: end while Ensure:

A dendrogram of 2(n + m) -1 nodes
The computing procedure of SHCoClust shown in Algorithm 8 is basically composed of two parts: spectral embedding that projects the input data into a space of eigenvectors, and application of Sim_AHC on the projected data to perform clustering.

1. Lines 1-6 correspond to the spectral embedding. This part is consisted of three steps: generation of the diagonally normalized matrix A n , application of SVD and production of the projected data matrix Z.

• The generation of the diagonally normalized matrix A n . Given the document-term matrix A, we compute the diagonal matrices D 1 and D 2 by The mathematics behind this is explained by Equations 2.25 to 2.29.

D 1 (i, i) = ∑ m j=1 A ij and D 2 (j, j) = ∑ n i A ij .
• The application of SVD. Applying SVD on A n with a given parameter l, the number of desired singular values, outputs l left singular vectors, µ 1 , µ 2 , . . . , µ l , and l right singular vectors ν 1 , ν 2 , . . . , ν l . A left singular vector µ contains n elements, and a right singular vector ν contains m elements.

It is important to note that their corresponding singular values should be in such an order:

1 = σ 1 ≥ σ 2 ≥ • • • ≥ σ l .
Recall the relation between a singular value of A n and an eigenvalue of the graph Laplacian L, σ = 1λ, and the eigenvalues are ordered as 0 = λ 1 ≤ λ 2 ≤ . . . . According to the Rayleigh-Ritz theorem, in a bi-partitioning task when there are two eigenvalues, the eigenvector that corresponds to the non-zero eigenvalue is the solution to the optimization Problem 2.18. When it comes to a multi-partitioning task, we are interested in the eigenvectors that correspond to the non-zero eigenvalues.

In terms of singular vectors, those who correspond to singular values that are smaller than 1 provide the solution. This is why we exclude the first left singular vector and the first right singular vector in matrices U and V . U is of shape n × (l -1), and V is of shape m × (l -1). In [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF], the author determines l by l = ⌈log 2 k⌉, where k is the number of desired clusters. However, it is lack of empirical training or theoretical proof. In our experiment, we learn this parameter by grid search for each tested dataset, and the l value that leads to the smallest difference between the original data and the projected data is selected.

• The production of the projected matrix Z. After U and V are generated, they are used to multiply D 1 and D 2 , the degree matrices of document vertices and of term vertices. The process of multiplication can be considered as projecting documents to a space constructed by left singular vectors in U , and projecting terms to a space constructed by right singular vectors in V .

Two matrices are output, Z 1 and Z 2 , they contain projected documents and terms in the space of singular vectors. They are of shape n × (l -1) and m × (l -1), respectively. The following step is to vertically concatenate Z 1 and Z 2 , that is, to fuse projected documents and terms in a space of l -1 dimensions. Performing clustering in this space outputs co-clusters consisted of documents and terms.

2. Lines 7-14, performing Sim_AHC on matrix Z to generate hierarchical co-clusters.

As Z is a matrix of projected data mixed with documents and terms, it is important to index Z so that we are able to know which rows correspond to the set of documents and which rows correspond to the set of terms. Before preforming Sim_AHC, Z should be normalized so that each row has norm 1, this is based on the basic assumption of Sim_AHC, see Equation 3.4. Then we can compute the pairwise similarity matrix S from the normalized Z. If inner product is chose to compute the pairwise similarities, S is filled with cosine similarity values. And its diagonal is constantly 1. Like in a common Sim_AHC process, kernel functions can be used to compute pairwise similarities, as shown in Equation 3.14. In our experiments, we use linear kernel (inner product) and Gaussian kernel to test SHCoClust in several text clustering tasks. In order to take advantage of the scalability property of Sim_AHC, we are interested to sparsify S to improve clustering efficiency.

However, different from a document-term matrix filled with non-negative TF-IDF values, Z possibly contain many negative values, it is thus important to re-scale its pairwise similarity matrix S by Formula 3.15 in order to have all similarity values between 0 and 1. After the re-scaling, we are able to set up a threshold value τ ∈ [0, 1] to sparsify S in a proper manner.

Sim_AHC goes through a number of iterations. More S is sparsified, less iterations Sim_AHC needs to go through. In each iteration, a pair of documentdocument, term-term or document-term is merged and an internal node is created in the dendrogram. Due to the relation shown in Equation 3.7, the dendrogram grows downwards, the height of a newly merged node is negative, and its value is

[S(Z i , Z j ) -1 2 (S(Z i , Z i ) + S(Z j , Z j ))].

Experiments: Clustering Effectiveness and Efficiency

Our experiments on SHCoClust emphasize two aspects, the clustering effectiveness and the clustering efficiency. For the first aspect, we compare clustering quality among SHCo-Clust, the Spectral Bipartite Co-clustering method (SBC) [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] and the conventional AHC methods. In order to examine whether sparsification influences the clustering quality, we sparsify the similarity matrix S in SHCoClust and compare the clustering quality against the use case of using a full-sized S. As to clustering effectiveness, we are interested to examine how clustering quality is affected when S is getting more and more sparsified, using both linear kernel and Gaussian kernel.

Datasets, Preprocessing and Evaluation Measures

Six experimented datasets are sampled from the corpora mentioned in Section 3.3.1, their details can be found in Table 4.1. In the rest of the paper, theses datasets are referred by their indexes shown in column "Ind.". Based on the bag-of-words assumption and the vector space model, each dataset is preprocessed into a document-term matrix, whose rows are document vectors and columns are terms. A few steps are involved in preprocessing, in detail, stop words are removed, terms that have document frequency higher than 20% and lower than 1% are removed, and TF-IDF weighting strategy is applied. "nb.docs" and "nb.terms" indicate the numbers of documents and of terms after the preprocessing. "K" is the ground-truth number of clusters, "l" is the learned parameter for SVD. "Z shape" indicates the shape of matrix Z obtained by the step of spectral embedding in Algorithm 8. "ARPACK" 1 is used as solver in SVD.

Dataset

Ind To evaluate clustering quality, we use the adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF] and the normalized Mutual Information (NMI) [START_REF] Aaron F Mcdaid | Normalized mutual information to evaluate overlapping community finding algorithms[END_REF]. They both measure the similarity between a list of ground-truth cluster labels and a list of predicted labels. The Rand Index measures the similarity between two list of labels by considering all pairs of samples and counting pairs that are assigned in the same or different clusters in the two lists. The ARI is the "corrected" version of the Rand Index, because it is adjusted for chance using the scheme of: ARI = RI-E[RI] max(RI)-E[RI] , with RI stands for the Rand Index, and E[.] denotes an expected value. The value of ARI ranges from 0 to 1, with 1 indicating that the two lists of cluster labels are identical, and 0 for being entirely different. NMI is normalization of the Mutual Information score. Its value is also between 0 and 1, with 1 indicating a perfect correlation between two compared lists, and 0 for non mutual information between the two. In order to use these two measures, we flatten the dendrogram obtained by SHCoClust to K clusters, then compute ARI and NMI using the predicted and the ground-truth cluster labels.

Comparisons of Clustering Effectiveness

We are interested in how well SHCoClust performs. Is it better or worse than the benchmark methods, such as SBC and the conventional AHC? And does sparsification affect clustering quality, positively or negatively? To answer these questions, we design our first experiments that are consisted of four tests as follows:

1 https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/arpack.py 1. SHCoClust without sparsification v.s. conventional AHC.

2. SHCoClust with sparsification v.s. without.

3. SHCoClust without sparsification v.s. BSC. [START_REF] Michel | Encyclopedia of distances[END_REF]. SHCoClust with sparsification v.s. BSC.

In tests that concern sparsification, threshold values τ at percentiles ranks {10, 25, 50, 75, 90}% of similarities in S are used to sparsify S. In this experiment, we apply linear kernel to obtain S, which is in fact filled with cosine similarities. The results of this experiment are illustrated in Figure 4.1. From top to down, each row maps to one test that is distinguished by its index. Each column lists the corresponding results for a tested dataset. Graph in each cell is a bar chart that is highlighted by a vertical line at x=0. The y-axis in each graph is labeled by the abbreviations of seven clustering methods. Bars in these graphs indicate the "difference" of values for ARI (the red, or the dark bars in a gray-scale printed paper) and for NMI (the blue, or the light ones) using a clustering method, obtained by subtraction of two tested approaches (A v.s. B, A -B). In the case of sparsification, we chose the highest value of ARI or NMI obtained in each clustering methods through the sequence of τ , then subtract it with the ARI or NMI value obtained by the approach in comparison.

In Figure 4.1, we can discovery a few interesting findings:

• Compared to conventional AHC, clustering quality is largely improved using SHCo-Clust for all clustering methods, except for single link and the Ward method. In datasets of S0 and S1, the increase is tremendous, ARI and NMI are raised up to 0.8 and 0.7 at maximum.

• When sparsification is applied in SHCoClust, the clustering quality is further enhanced. However, this enhancement does not compromise SHCoClust's efficiency.

Instead, as most highest ARI and NMI values are obtained when τ ∼ 1, the efficiency of SHCoClust is considerably improved, thanks to a largely sparsified input.

• SHCoClust (without sparsification) obtains close results to SBC for all clustering methods, except for single link. Though improvements can be found in R5, NG8 and R7, other datasets do not display any. However, when sparsification is applied in SHCoClust, some noticeable amelioration can be observed. Comparing graphs of test 3) and of test 4), bars generally exhibit a left-to-right drift, diminishing their heights in the left side of the vertical line at x=0, and growing their heights in the right side. This drift is very apparent in R7 and NG20, where ARI and NMI

Examination of Clustering Efficiency with Sparsification

In our second experiment, we examine the improvement of clustering efficiency when the similarity matrix S is getting more and more sparsified, and we record the changes of clustering effectiveness in order to observe if clustering quality compromises when computing efficiency is improved via sparsification. In addition, we extend the similarity function in SHCoClust to Gaussian kernel, given by K(x, y) = exp(-γ∥x -y∥ 2 ) for

x, y ∈ D, γ = 1/dim(I) by default2 . Three representative datasets R5, S0 and NG8 are experimented and are compared to their results obtained by linear kernel. The input kernel matrix is sparsified in the same fashion as in the previous experiment. For each threshold value, ARI, NMI, relative memory usage and relative running time are recorded. Figure 4.2 illustrates the results of this experiment. Indexed by the abbreviations of clustering methods in row and the names of datasets in column, each graph in Figure 4.2 contains four lines: the solid line with "+" sign denotes the NMI values, the dashed line with triangle sign is for ARI, while the solid line with "o" sign and the solid line with "x" sign represent the relative memory usage and the relative running time, respectively. The x-axis corresponds to the percentile ranks that define the threshold values τ (not shown). At each τ ∈ (0, 1), exact memory usage and running time are recorded, and are divided by those at τ = 0, i.e., when no thresholding is applied, to obtain the relative memory usage and the relative running time.

In Figure 4.2 we can see that, as the percentile rank increases, memory usage and running time decrease correspondingly, however, ARI and NMI tend to preserve their values at some level until the percentile rank approaches closely to 1. More precisely, before the percentile rank crosses 75%, in most cases, we can obtain ARI and NMI values as high as (or higher than) using the full-sized input. In some other cases, ARI and NMI even boost after percentile rank is over 75%, like in S0 (of linear kernel at average link).

Among seven clustering methods, single link is the most peculiar, its ARI and NMI are invariant to the effect of sparsification, however, in R5 (of linear and Gaussian kernel) and NG8 (of Gaussian kernel), ARI of single link boosts at percentile rank = 90%, at which point memory usage and running time are largely reduced. Comparing the two kernel functions, overall similar behavior can be observed regarding the four curves. In some cases, Gaussian kernel returns higher metric values than linear kernel, and vice versa. Among the three experimented datasets, results of S0 are globally better, while R5 and NG8 display limited difference in their results.

Principle conclusions we can draw from this experiment are that:

• SHCoClust is capable to guarantee the clustering quality even when its input is largely sparsified, requiring considerably reduced memory usage and running time.

τ at percentile rank of 75% is a heuristically good threshold in our experiment (90% for single link).

• The clustering quality does not compromise when computing efficiency is improved by sparsifying the similarity matrix S. On the contrary, clustering effectiveness is even increased when using a sparsified S. This is likely due to the fact that • SHCoClust can be easily employed with a kernel function, though only linear and Gaussian kernels are experimented here, we believe that its compatibility with kernel functions enables it to handle non-linearly separable datasets more effectively in other tasks.

Discussion of Complexity and Scalability

Mentioned in Section 2.3.3.3, the computation complexity of a complete SVD process can reach O(min(nm 2 , mn 2 )) in decomposing a matrix of size n-by-m [START_REF] Holmes | Fast svd for large-scale matrices[END_REF]. This is the complexity of performing spectral embedding in Algorithm 8. As matrix Z is of shape (n+m)×(l-1), the storage complexity for its pairwise similarity matrix S is O((n+m)

Conclusion

In this chapter, a new algorithm, the similarity-based hierarchical co-clustering method, SHCoClust, is presented. We are interested in the advantageous property of co-clustering, which is capable to perform clustering in both data space and in feature space. Beginning with explaining the choice among several co-clustering techniques, we select the graph partitioning approach, as it allows to embed an arbitrary hard clustering method.

The drawback of this kind of approaches is that they output flat co-clusters, and elements inside one co-cluster are not structured. Therefore, it is not possible to know how co-clusters are connected with each other, and how elements inside a co-cluster are organized. Inspired by the spectral embedding introduced in Section 2.3.3.3, we propose a hybrid learning method that is capable to perform hierarchical co-clustering. In such a way, co-clusters and elements inside an individual co-cluster are organized in a tree structure. It allows us to have a better understanding on an input dataset by examining how co-clusters and their elements are structured.

After presenting the motivation of this work, we present the proposed method by illustrating its computing procedure and the related mathematical details. We hope to give enough information to present a clear idea and method for readers. In the experiment part, we examine the proposed method from two aspects, the clustering effectiveness and computing efficiency. For the first aspect, we compare clustering quality of the proposed method with two benchmark methods in two scenarios, with a full-sized similarity matrix or with a sparsified one. By four different tests, it is concluded that the proposed method significantly improves clustering quality compared to the conventional AHC for most clustering methods, and it achieves improvements over SBC when sparsification is applied on the similarity matrix. As to computing efficiency, we examine the improvement of clustering efficiency when the similarity matrix is getting more and more sparsified, and how this influences clustering quality. Using linear and Gaussian kernels on three datasets, we discover that sparsifying similarity matrix can largely improve computing efficiency by reducing memory use and running time, more importantly, clustering quality does not compromise while computing efficiency is improved via sparsification.

On the contrary, clustering effectiveness is improved when similarity matrix is sparsified.

Furthermore, we present a discussion on the complexity of the proposed method and a visualization on a sampled dataset. We show that the proposed method is capable to perform co-clustering, meanwhile, organizing co-clusters and elements inside individual co-cluster in a tree-like structure. It provides richer knowledge on the input data than either a pure co-clustering method or a pure hierarchical clustering method.

Mentioned in Section 4.3.4, for most cases in our experiments, the threshold value at percentile rank of 75% is the heuristically optimal threshold value, at which the ARI is preserved as high as possible while the similarity matrix is sparsified to have as less nonzero values as possible. A future work would be to determine a well-designed method to determine such a optimal threshold value for general cases when input datasets vary in size and in type.

Chapter 5

Testing the Cluster Hypothesis

Motivation

Previously, we present Sim_AHC and SHCoClust in Chapter 3 and in Chapter 4. As sated in Section 1.2 of Chapter 1, the task that our team undertakes is the "intelligent recursive and iterative information retrieval", for which we are required to apply clustering and co-clustering algorithms on IR tasks. However, IR is a wide field, it contains too many interesting research subjects that we do not have enough time for. Since our previous works are all clustering-based, we narrow down our research topic to the cluster hypothesis, which is the fundamental hypothesis of employing clustering methods in IR.

By testing this hypothesis using Sim_AHC and SHCoClust, we are able to obtain important knowledge on how effectively a given query is responded, and with what efficiency.

These knowledge, though theoretical, allow us to have basic but fundamental ideas on the retrieval behaviors of applying Sim_AHC and SHCoClust. Recall that the basic assumption adopted in our research for text clustering is the "bagof-words" assumption and the vector space model. Therefore, the language-model-based tests are out of the scope of this thesis. As we devote much of our time to studying conventional AHC methods and the Lance-Williams formula, we are most interested in the cluster hypothesis tests that employ AHC methods. Interestingly, after carefully reviewing these tests, we find out that their conclusions are not consistent regarding which clustering method is the most effective. This inconsistency is likely caused by the differences in tested datasets, experimental settings and evaluation measures. In addition, these tests merely examine four AHC methods1 in the Lance-Williams formula, leaving the retrieval performance of the other three methods unknown. Moreover, only retrieval effectiveness is addressed in these works, knowledge on retrieval efficiency is left blank. As AHC methods are computationally costly, it is practically important to examine their retrieval efficiency. These findings motivate us to design new tests that cover all AHC methods in the Lance-Williams formula within a universal experimental framework, and to examine the retrieval effectiveness and efficiency.

In the rest of this chapter, we elaborate on two proposed tests on the cluster hypothesis using Sim_AHC and SHCoClust, respectively. In each test, we employ optimal cluster search and the E-measure to evaluate retrieval effectiveness and compare it among seven AHC methods. Recall that a cluster-based retrieval process applies a search strategy and outputs a cluster that is believed to be the most relevant to a query. There are three search strategies, the top-down, the bottom-up and the optimal cluster search (Section 2.4.2.2). Among these strategies, we choose optimal cluster search in our experiments.

It is superior to its counterparts, as it does not depend on cluster representatives. Besides, it allows to compute a measure that balances between precision and recall, in order to avoid retrieving large clusters (that results in low precision but high recall) and small clusters (that have low recall but high precision). This measure used in optimal cluster search is called E-measure, it is defined as Equation 2.36. The characteristics of optimal cluster search and the E-measure allow us to evaluate retrieval effectiveness without bias, as they directly concern the structure of a dendrogram without depending on external object, such as a cluster representative.

In addition to examining and comparing retrieval effectiveness of different clustering methods, we also address efficiency issue. As Sim_AHC and SHCoClust are more efficient when their similarity matrices are sparsified, we test whether improving efficiency via sparsification influences the retrieval effectiveness measured by the E-measure. After presenting the two proposed tests, we illustrate an empirical comparison between them in order to have a better understanding on their retrieval performance.

The outline of this chapter is structured as follows: in Section 5.2, details on tested datasets, preprocessing and experiment setting are presented. In Section 5.3, a new test on the cluster hypothesis using Sim_AHC is introduced. Another test that uses SHCo-Clust is illustrated in Section 5.4. In each test, we compare the retrieval effectiveness of seven hierarchical clustering methods, and we examine the impact of improving efficiency via sparsification on the effectiveness. In Section 5.5, we compare between the two proposed tests by performing statistical tests, and discuss their computing complexity.

Datasets, Preprocessing and Experiment Setting

Five datasets from two collections are used in our experiments. Three of the Classic-4 datasets2 , MED, CISI and CACM, have been tested in previous works [START_REF] Voorhees | The cluster hypothesis revisited[END_REF][START_REF] Tombros | The effectiveness of query-based hierarchic clustering of documents for information retrieval[END_REF][START_REF] El | Comparison of hierarchic agglomerative clustering methods for document retrieval[END_REF].

Introduction on MED (or MEDLINE) and CISI datasets can be found in Section 3. For each dataset, a simple preprocessing is employed: stop words are removed; terms that have document frequency higher than 20% and lower than 2% are removed; the remaining terms are stemmed by Porter Stemmer [START_REF] Martin | An algorithm for suffix stripping[END_REF]; TF-IDF weighting scheme is applied and l 2 normalization is performed on each document vector. The output of preprocessing for each dataset is a document-term matrix, whose number of documents and number of terms are indicated by nb.docs and nb.terms in Table 5.1.

Each dataset contains a complete query set and a relevance judgment file, which specifies a list of relevant documents to a query. In evaluation, we use the query set and the relevance judgment file to compute E-measure. The number of queries for each dataset is given by nb.queries, and the number of relevant documents per query is given by nb.docs/query.

For the TREC datasets (AP and WSJ), the relevance judgments files of TREC-2 are used 4 . They concern 100 queries indexed from 51 to 150 by the TREC convention. For AP collection, there are 97 queries extracted in total. On average, each query has 110 relevant documents. For WSJ collection, 50 queries are extracted, each query has 91 relevant documents on average. As our tested datasets are sampled, they contain less documents than the full collections, so we remove the documents that are not contained in these tested datasets from the list of relevant documents for each query. This results in 61 and 27 queries for the sampled AP and WSJ datasets, respectively. And each query has 2 relevant documents on average.

Our experiment is consisted of a number of tests. In each test, a full-sized or a sparsified pairwise similarity matrix S, generated by either linear kernel or Gaussian kernel, is used as input. We then apply one of the seven AHC methods (either in Sim_AHC or in SHCoClust) to produce a dendrogram, which is later cut at each height to output a set of flattened clusters. For each query in the query set, we search for its optimal cluster by scanning all the flattened clusters, for each of which we compute an E value. The cluster that has the minimal E value is the optimal cluster. The final output of such a test is a key-value pair, with a query ID being the key and the optimal E value (i.e., the E value of the optimal cluster that corresponds to the query) being the value.

Recall that E-measure [START_REF] Jardine | The use of hierarchic clustering in information retrieval[END_REF] is used to evaluate retrieval effectiveness. Expressed as E = 1 -(β 2 +1)P R β 2 P +R , smaller E value indicates better retrieval effectiveness. P and R represent precision and recall, respectively, which can be expressed by P = tp d and R = tp q . d is the number of documents in an optimal cluster, q is the number of relevant documents for a query, tp = d ∩ q is the number of true positive documents. β is the parameter that balances the importance between precision and recall, it takes values of 0.5, 1 and 2.

A New Cluster Hypothesis Test Using Sim_AHC

In this section, a new test on the cluster hypothesis is introduced. Differing from those tests that apply conventional AHC methods, this test applies the similarity-based hierarchical clustering framework, Sim_AHC. In Chapter 3, we mathematically and empirically demonstrate that Sim_AHC is equivalent to the conventional AHC procedure with the Lance-Williams formula. Using inner product-based similarities, Sim_AHC allows to employ a threshold value to sparsify the similarity matrix in order to improve computing efficiency. Its experiments demonstrate that the sparsifying strategy not only improve efficiency, but also guarantee or improve clustering quality.

In this test, we apply Sim_AHC to testing the cluster hypothesis. The objective of this test is three-folded: first of all, we are interested in complementing previous research works, where only four AHC methods are tested. In this test, all conventional AHC methods that are unified in the Lance-Williams formula and in Sim_AHC are tested.

Secondly, by applying optimal cluster search and computing the E-measure, we compare retrieval effectiveness among these methods and provide a benchmark using a universal experimental setting. Thirdly, we address efficiency issue in this test. Concretely, we examine the influence of sparsifying similarity matrix on retrieval efficiency, and on retrieval effectiveness.

Comparison of Retrieval Effectiveness Among Seven Clustering

Methods

Table 5.3 and Table 5.4 display results of our first experiment. Each cell in Table 5.3 is an averaged optimal E value, which is the mean value of all optimal E values for a set of queries in a tested dataset. Suppose that a dendrogram is produced after applying the single link clustering method on MED dataset, whose query set contains 30 queries, Q = {q 1 , . . . , q 30 }. By optimal cluster search, we find an optimal cluster for a query and obtain the corresponding optimal E value. For this set of queries, the averaged optimal E value is computed as 1 30 ∑ 30 i=1 E i , it is equal to 0.452 (at β = 0.5). Correspondingly, the standard deviation of optimal E values for the queries of MED dataset is 0.157, shown in Table 5.4.

In this experiment, the input similarity matrix S is generated by linear kernel and by Gaussian kernel. No thresholding strategy is applied, thus the full-sized S is used in computation. Values in Table 5.3 that are highlighted in bold are column-wise minimums. They signify the best retrieval effectiveness among seven clustering methods at a β value.

As the averaged optimal E values are very close, we use three decimals to distinguish them. When these values are too close, we select the column-wise lowest using four decimals, but only three are shown. Likewise, in Table 5 In Table 5.4, we can see that standard deviation values are generally small, indicating that the overall difference between an optimal E value and the averaged optimal E value is small. Compared to MED, CISI and CACM datasets, AP and WSJ datasets have more larger standard deviation values. This is likely caused by the reduced number of relevant documents in their relevance judgment files. Small optimal clusters that contain relevant files tend to generate very low optimal E values, but larger optimal clusters that do not contain any relevant file tend to output very high optimal E values. This causes standard deviation values to increase in AP and WSJ datasets.

With Table 5.2, we can confirm that our results obtained from MED (using linear kernel), CISI, CACM and AP datasets conform to the conclusion in [START_REF] Griffiths | Using interdocument similarity information in document retrieval systems[END_REF], which states that "Ward method was found to give the best overall results", though this work retrieves several clusters instead of one. As to the conclusions of [START_REF] Griffiths | Hierarchic agglomerative clustering methods for automatic document classification[END_REF][START_REF] Tombros | The effectiveness of query-based hierarchic clustering of documents for information retrieval[END_REF], which claim that "average link gave the best results", we only have the result obtained by MED dataset using Gaussian kernel to support them. In fact, compared to average link, we find that McQuitty achieves the same or better efficiency. Furthermore, our results disagree with the finding in [START_REF] Willett | Recent trends in hierarchic document clustering: a critical review[END_REF],

which concludes that "complete link is probably the most effective method". In our experiments, complete link performs poorly. Single link, centroid and median methods usually obtain larger averaged optimal E values than the other methods, showing poor retrieval effectiveness.

For two kernels, they obtain close results in many cases. Among all tested datasets, MED obtains generally lower E values than the other datasets, it is also the smallest collection. For MED, CISI and CACM datasets, their averaged optimal E values tend to increase as the values of β increase. On the contrary, for AP and WSJ datasets, as the values of β increase, averaged optimal E values tend to decrease. This is actually related to the sizes of optimal clusters and the number of relevant documents per query.

In MED, CISI and CACM datasets, the sizes of optimal clusters increase as the values of β increase. The size of an optimal cluster influences precision and recall. Larger optimal cluster tends to have lower precision but higher recall. When β = 2, E-measure assigns more importance to precision, making larger optimal clusters to have higher E values.

As to AP and WSJ datasets used in our experiments, the number of relevant documents per query is very small. In this case, larger clusters are likely to contain all relevant files, resulting in higher precision. Small clusters, on the other hand, probably have low precision as they do not contain any relevant document. This eventually makes E values to decrease when β moves from 0.5 to 2.

To compare among the averaged optimal E values obtained at β = 0.5, 1 and 2, we provide Figure 5.1 that illustrates the results of each dataset in Table 5.3. Numbers 1-7 along x-axis index seven clustering methods, from single link to Ward method. Dotted line with circle sign, solid line with triangle sign and dashed line with plus sign present the averaged optimal E values at β = 0.5, 1 and 2, respectively. Note that in order to clearly display the difference of the three lines, each plot has its own scale for y-axis.

Kernel MED CISI CACM AP WSJ Linear • • • • • • • 1 2 3 4 5 6 7
0.4 0.5 0.6 0.7 0.8

• • • • • • • 1 2 3 4 5 6 7
0.55 0.65 0.75 0.85

• • • • • • • 1 2 3 4 5 6 7
0.55 0.65 0.75 0.85

• • • • • • • 1 2 3 4 5 6 7
0.4 0.5 0.6 0.7 0.8

• • • • • • • 1 2 3 4 5 6 7
0.5 0.6 0.7 0.8 0.9 0.55 0.65 0.75 0.85

Gaussian • • • • • • • 1 2 3 4 5
• • • • • • • 1 2 3 4 5 6 7
0.4 0.5 0.6 0.7 0.8

• • • • • • • 1 2 3 4 5 6 7
0.5 0.6 0.7 0.8 0.9

Influence of Improving Efficiency via Sparsification on Retrieval Effectiveness

In Section 3.3.2 of Chapter 3, we observe that improving efficiency by sparsifying the similarity matrix S in Sim_AHC does not harm clustering quality, which on the contrary gets improved in many cases. We give two reasons to explain this phenomenon in Section 3.4: first of all, sparsifying S "purifies" similarities by removing non-significant values.

Secondly, fusing a pair of similar clusters allows their respective neighborhoods to be combined, making it is more likely to absorb another cluster that is initially close to either of the neighborhoods.

Though measuring clustering quality is different from measuring retrieval effectiveness, these two associate with each other. Intuitively, better retrieval effectiveness is more likely obtained when documents are well clustered, in which documents in one cluster are highly similar and documents from different clusters are largely dissimilar. This motivates us to examine whether improving computing efficiency by sparsifying similarity matrix S influences retrieval effectiveness.

Like our previous experiments that involve sparsification, in this experiment, our baseline is still the absolute running time (in seconds) and memory usage when a full-sized similarity matrix S is used as input. We record the relative running time and relative memory usage when S is sparsified by a threshold value τ . Likewise, the set of τ values is When S is sparsified by a τ value, only its non-zero values are kept in memory. Performing a clustering method from Sim_AHC on a sparsified S outputs a reduced dendrogram, which is smaller than the dendrogram output by a full-sized S. This reduced dendrogram is cut at each height to generate a set of flat clusters, whose sizes vary from small to large. Flat clusters that are obtained near dendrogram's leaf nodes are usually smaller than those obtained near the dendrogram's root. For each query in the query set that is attached to the dataset in test, optimal cluster search is performed to find the optimal cluster for this query. Once the optimal cluster is found, an optimal E value is obtained, accordingly. In order to reflect how a specific dendrogram responds to all queries that come from the same set, we average over their optimal E values to get the averaged optimal E value for the set of queries. This value is recorded and plot. of using complete link in MED and CISI datasets becomes worse when the similarity matrix S is getting more and more sparsified. However, the opposite discovery can be found in the plots of centroid method applying on MED, CISI, AP and WSJ datasets in Figure 5.3, where E curves drop down when percentile rank is approaching to 1. It implies that even similarity matrix S is sparsified, with less memory use and less running time, retrieval effectiveness is actually improved.

MED

In most plots, E curves tend to preserve at their levels and fluctuate very subtly as S is being more and more sparsified. This is likely caused by the fact that most optimal clusters are small and they situate near the leaf nodes of a dendrogram. Sparsifying S mostly influences clusters that have small similarities, and these clusters are usually located near the root of the dendrogram. That is why sparsifying S does not really affect optimal clusters. And retrieval effectiveness is preserved. This is an interesting discovery.

It implies that with sparsifying S, we can achieve the same retrieval effectiveness using much less computing resources.

Comparing two kernels, they obtain similar results. Though it is difficult to see much differences between Figure 5.2 and Figure 5.3, based on recorded values, we observe that Gaussian kernel always achieves better retrieval effectiveness than linear kernel for centroid and median methods. This holds for all datasets except for CACM dataset. In addition, both kernels obtain exactly the same results using single link for any full-sized or sparsified S.

Summary

In this section, we introduce a new test on the cluster hypothesis using the similaritybased hierarchical clustering framework, Sim_AHC. From the aspects of retrieval effectiveness and efficiency, we examine this test by comparing retrieval effectiveness among seven clustering methods, and by investigating the impact of improving efficiency via sparsification on retrieval effectiveness. In comparing seven clustering methods, we conclude that Ward outperforms the other methods. This conclusion agrees with some of past research works. In examining the influence of sparsifying similarity matrix on retrieval effectiveness, our experiments using linear kernel and Gaussian kernel demonstrate that improving computing efficiency by sparsifying similarity matrix does not harm retrieval effectiveness. In fact, retrieval effectiveness is almost invariant to the effect of sparsification. This result implies that using a largely sparsified similarity matrix, with substantially reduced memory and running time, retrieval effectiveness can be guaranteed. Comparing between linear kernel and Gaussian kernel, we find out that Gaussian kernel improves retrieval effectiveness of centroid and median methods.

A New Cluster Hypothesis Test Using SHCoClust

Unlike Sim_AHC, which performs clustering only on documents, SHCoClust groups both documents and terms at the same time. This characteristic makes it unique in the sense that it organizes co-clusters in a hierarchy and structures elements in a cocluster. As stated previously, a cluster-based IR system built on such a method can be advantageous, as it is capable to return relevant documents and "describing" terms of these documents. In this sense, richer knowledge is provided for seeking information.

In previous section, by examining how well document clusters respond to a query in Sim_AHC, we obtain a few interesting findings. This makes us curious about the retrieval performance of SHCoClust. How well its document clusters respond to a query using a co-clustering method? Similarly, as the computing efficiency of SHCoClust can also be improved by sparsifying its similarity matrix, we are interested to see whether its retrieval effectiveness can be likewise guaranteed when sparsification is applied, as shown in the test of Sim_AHC. For such purposes, in this section, we perform a new test that applies SHCoClust to compare retrieval effectiveness among seven clustering methods, and to examine the impact of sparsifying similarity matrix on retrieval effectiveness.

Recall that in SHCoClust, a document-term matrix is firstly projected into a space that is constructed by eigenvectors of a graph Laplacian matrix, then clustering is performed on the projected data. Though the same set of datasets are used in this test, different processes are required by SHCoClust. First of all, spectral embedding is applied on a preprocessed document-term matrix to obtain matrix Z. Secondly, Z is normalized.

Note that it is important to correctly map documents and terms to their corresponding vectors in Z. Thirdly, similarity matrix S co is computed from Z and it is re-scaled to have similarity values between 0 and 1. The set of threshold values τ is selected from percentile ranks at {10, 25, 50, 75, 90}% of similarities in S co . When a τ is used to sparsify S co , a reduced dendrogram is produced. In order to correctly measure retrieval effectiveness based on relevance judgment information, it is necessary to remove all terms from an output dendrogram. Otherwise, the number of terms would increase the size of a cluster, lowering precision and affecting E value.

Comparison of Retrieval Effectiveness Among Seven Clustering Methods

In comparing retrieval effectiveness among seven clustering methods of SHCoClust, a full-sized similarity matrix S co is used as input. With such an input, a clustering method produces a complete dendrogram, which is then cut at each height to generate a set of flat clusters. After removing terms from each flat cluster, optimal cluster search is performed on these flat clusters for each query to look for its optimal cluster and the optimal E value. The information provided by a relevance judgment file is used at this step to compute E values. The optimal E value is recorded for each query. However, in order to reflect how well a dendrogram responds to all queries of an input dataset, we average the optimal E values over the number of queries. This averaged optimal E value is used to evaluate the overall retrieval effectiveness of a clustering method on a dataset. is an averaged optimal E value, i.e., the mean value of optimal E values of all queries in a tested dataset. And a value in Table 5.7 is a corresponding standard deviation.

Column-wise minimums in both tables are highlighted in bold. In Table 5.6, a bold value signifies the best retrieval effectiveness achieved by a clustering method at a β value. And in Table 5.7, a bold value marks the method that produces the most stable optimal E values at a β value.

To compare retrieval effectiveness among seven clustering methods from Table 5.6, a summary is provided in Table 5.5, in which the clustering method that achieves at least two minimums across three β values is listed for each dataset. When no such a method exists, a "-" sign is used. From this

Impact of Sparsification on Retrieval Effectiveness

In the test of Sim_AHC, shown in Section 5.3.2, we find out that retrieval effectiveness is guaranteed when similarity matrix is getting more and more sparsified. Unlike sparsifying a similarity matrix in Sim_AHC, in SHCoClust sparsification is applied on a similarity matrix that is obtained from projected data. This difference might lead to different conclusions from the experiment of Sim_AHC. Interested in finding this out, in this section we examine the influence of sparsification on retrieval effectiveness in SHCoClust.

Likewise, the baseline of our experiment is the absolute running time T τ =0 and memory use M τ =0 when a full-sized S co is taken as input. Given a threshold value τ , τ > 0, S co is sparsified by only keeping its non-zero values that are greater or equal to τ in memory.

A clustering method is applied on a sparsified S co and an incomplete dendrogram is output. The memory use that is occupied by the sparsified S co , M τ , and the running time of performing clustering, T τ , are recorded. The relative memory use, Mτ M τ =0 , and the relative running time, Tτ T τ =0 , are computed and plotted. The output dendrogram is flattened at each height, resulting a set of flat clusters. In order to compute E-measure, only documents are kept in each flat cluster (terms are removed). Using the relevance judgment information in a dataset, the optimal cluster is searched for each query and corresponding optimal E value is computed. In the end, the averaged optimal E value is calculated for all queries. It is interesting to see that a similar conclusion can be drawn from this experiment as in the test of Sim_AHC, that is, retrieval effectiveness tends to be invariant to the effect of sparsifying similarity matrix. It is clear that, in the results of both linear and Gaussian kernels, the lines of the averaged optimal E values are almost straight in all plots, in which relative running time and relative memory use decrease as percentile rank increases. In fact, these lines are even more constant than the results obtained in the same experiment of Sim_AHC. In addition, results obtained from two kernels are also

Summary

In this section, we propose a new test on the cluster hypothesis using SHCoClust. In our experiments, we firstly illustrate results of comparing retrieval effectiveness among seven clustering methods, then we examine the impact of sparsifying similarity matrix on retrieval effectiveness and on computing efficiency. In the first experiment, we find out that Ward method is no more the dominating one as concluded in the test of Sim_AHC.

value increases. Unlike Sim_AHC, SHCoClust goes through more iterations and outputs larger dendrograms. This results in more flat clusters for optimal cluster search, and provides more candidates to be selected as the optimal cluster for a query. It is why SHCoClust has lower variance of the optimal E values than Sim_AHC.

Comparison between Two Proposed Tests

In Section 5.3 and Section 5.4, we design and carry out two new tests on the cluster hypothesis using Sim_AHC and SHCoClust, respectively. In each test, we compare retrieval effectiveness among seven clustering methods and examine the impact of improving computing efficiency by sparsification on retrieval effectiveness. In this section, we compare the two tests to find out which clustering framework has better retrieval effectiveness. Besides, we provide a discussion on the complexity of the two clustering frameworks.

On Retrieval Effectiveness

One way to compare retrieval effectiveness between Sim_AHC and SHCoClust is to compare results in Table 5.3 and in Table 5. [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF]. In order to perform a fair comparison, we carry out a set of paired two-tailed Student T-tests between the results obtained in the Sim_AHC test and the results obtained in the SHCoClust test. Our objective is to examine whether the retrieval effectiveness of Sim_AHC is the same or significantly different from that of SHCoClust. If they are significantly different, we compare their averaged optimal E values to conclude which one is more effective.

Previously, it is explained that the averaged optimal E value is the mean value of a list of optimal E values for a set of queries. To perform one T-test, we take two lists of optimal E values. One list is from Sim_AHC and the other list is from SHCoClust using the same clustering method on the same dataset with the same kernel function at the same β value. The null hypothesis is H 0 : µ 0 = µ 1 , with µ 0 and µ 1 denoting the averaged optimal E value of Sim_AHC and of SHCoClust, respectively. And the alternative hypothesis is H 1 : µ 0 ̸ = µ 1 . It is a paired T-test, because the two lists of optimal E values in comparison are generated from the same dataset for the same query set using the same clustering method, but from two different frameworks.

In each T-test, we compute a statistical T value and compare it against the corresponding critical value at confidence level α = 95%. If the absolute T value is greater than its critical value, the null hypothesis H 0 is rejected and the alternative hypothesis H 1 is accepted; otherwise, the alternative hypothesis H 1 is rejected and the null hypothesis H 0 is accepted.

Summary

In this section, we compare retrieval effectiveness between Sim_AHC and SHCoClust by performing a set of paired two-tailed T-tests. We conclude that Sim_AHC is more effective than SHCoClust using complete link, average link, McQuitty and Ward methods in MED, CISI and CACM datasets. On the contrary, SHCoClust is more effective than Sim_AHC using single link, centroid and median methods in AP and WSJ datasets. In terms of computing efficiency, determined by the computing procedures, SHCoClust is more costly than Sim_AHC.

Conclusion

In this chapter, two new tests on the cluster hypothesis are performed using Sim_AHC and SHCoClust. The motivation of performing these tests is to obtain important knowledge on how effectively a query is responded using different clustering methods, and with what computing efficiency. We believe that this knowledge is fundamental for us to understand the retrieval behaviors of the proposed clustering frameworks. Another interest of this work is to provide a benchmark on this topic. In reviewing past works, we find out that conclusions drawn from the cluster hypothesis tests are not consistent, in comparing retrieval effectiveness among several hierarchical clustering methods.

The inconsistency is likely caused by the difference in datasets, experiment setting and evaluation. Additionally, in the past works, only four out of seven conventional clustering methods are tested. This motivates us to propose new tests, in which we use universal datasets, experiment settings and evaluation measure to test seven clustering methods in the framework of Sim_AHC and of SHCoClust. As Sim_AHC is equivalent to conventional AHC and the Lance-Williams formula, retrieval effectiveness obtained by Sim_AHC is the same to the conventional AHC framework. Another contribution of this work is that we provide insight of retrieval efficiency for the cluster hypothesis tests that apply hierarchical clustering methods. Concretely, we examine the impact of improving efficiency by sparsifying similarity matrix on retrieval effectiveness.

In the test that uses Sim_AHC, we discover that Ward method is the dominating method, who achieves the best retrieval effectiveness in most cases. This conclusion agrees with some of the past works. However, in the test that uses SHCoClust, a wider range of performing methods is returned. As to the impact of improving efficiency by sparsifying similarity matrix on retrieval effectiveness, both tests present similar result, i.e., retrieval effectiveness is almost invariant to the impact of sparsification. We observe that when threshold value approaches to 1, with reduced memory use and running time, retrieval effectiveness is guaranteed. This is an interesting discovery, which implies that it is likely to achieve the same retrieval effectiveness with largely reduced memory use and running time. We explain that sparsification disconnects clusters that are near the root of a dendrogram, but it gives little impact on most optimal clusters, who are close to the leaf nodes of the dendrogram. In comparing the retrieval effectiveness between the proposed tests, we perform a sets of paired two-tailed T-tests. We conclude that Sim_AHC is significantly more effective than SHCoClust using complete link, average link, McQuitty and Ward methods. However, SHCoClust is more effective than Sim_AHC using single link, centroid and median methods.

Chapter 6

The Distributed Implementations In this chapter, we illustrate the distributed implementations of Sim_AHC and of SHCo-Clust, by presenting details of computing procedure, data structure, problems and solutions. To us, implementing Sim_AHC and SHCoClust is a process of "learning by doing". Though the performance of distributed Sim_AHC is not as good as expected, we gain some valuable practical programming knowledge using Spark. We share this learned knowledge in this chapter as well. For SHCoClust, like many other Spectral-SVD methods, it uses spectral embedding as core. We provide an implementation of distributed spectral embedding and make it applicable not only in SHCoClust but also in other Spectral-SVD methods. In Section 6.2 and Section 6.3, we present implementation details of distributed Sim_AHC and distributed spectral embedding, respectively.

6.2

The Distributed Implementation of Sim_AHC The key is an ID number and the value is a document vector. Next, a cartesian function is applied on the MapPartitionRDD to compute pairwise similarities and self similarities. For example, given a pair of indexed document vectors such as

(C 1 , [val 1 , val 2 , . . . , val m ]) and (C 2 , [val 1 , val 2 , . . . , val m ]
), the output of the cartesian function on these two vectors is still in a form of key-value pair, such as

((C 1 , C 2 ), (S 12 , S ′ 12
)), where S 12 is the inner product-based similarity of the two document vectors, and S ′ 12 = S 12 -0.5 × [S 11 + S 22 ] is their self similarity of. As document vectors are normalized during preprocessing, if an inner product is applied in the function that generates S 12 , it is cosine similarity. This can be extended to other kernel functions. If the number of documents is n, the output of

Step 1 contains n 2 pairs. By applying a filtering function (a transformation function), we reduce the number of pairs to n(n -1)/2. The filtered output is a set of MapPartitionRDDs, it is illustrated as a pairwise similarity table in Figure 6.1.

2. In the second step, our program searches for the pair of documents that has the largest pairwise similarity in the pairwise similarity table. This operation is an action function. Once it is called, all the transformation functions that are previously called on RDDs are materialized, and it outputs the key-value pair that has the maximal similarity. Let (C i , C j ) denote the pair of documents that have the largest similarity, S ij , and the corresponding self similarity is S ′ ij . Once (C i , C j ) is found, it is appended into a list, which is used to build a dendrogram.

3. In the third step, we firstly remove the entry ((C i , C j ), (S ij , S ′ ij )) from the original pairwise similarity table. The remaining entries are categorized into: (1) entries that contain index C i in their keys, (2) entries that contain index C j in their keys, and (3) the other entries that contain neither i nor j in their keys. Accordingly, the pairwise similarity table is split into three different tables: The i-k When launching a Spark application, it is essential to specify configuration properties for the cluster, such as the number of executors, the number of executor cores, the size of executor memory, etc. There are many properties that can be configure 2 , Table 6

a summary of RDDs' sizes and memory usage and (4) environment information.

A Spark application is composed of a set of jobs, each job is further composed of a list of stages, each stage has several tasks. Figure 6.2 is a screenshot of Spark web UI homepage, which contains three parts of information: (1) cluster general information and status,

(2) workers' information and status, and (3) applications' information and status. If there is an running application, we can access the list of jobs, shown in Figure 6.3. Each job is indexed by an ID number, information such as applied functions, submitted time, We can also access the DAG (Directed Acyclic Graph) visualization of a job, shown in Additionally, we can access to the information of executors, shown in Figure 6.6. This information allows us to know the status, number of RDDs' blocks, size of storage memory, number of cores, number of active, failed, complete tasks, etc for each executor.

With this information, we can observe whether work load is balanced among executors.

Spark web UI provides essential information when running a Spark application, it is the most important tool to debug and improve a Spark user program.

if it is set too small for a large dataset, the computation is inefficient as well. This is a dataset-dependent parameter.

In our early experiments using Iris dataset, we artificially set the number of partitions to 2 when the data is read from HDFS. Through iterations, we observe that the number of partitions is tripled in each iteration, and processing is getting slower and slower. By tracking the number of partitions of the tables shown in Figure 6. Due to the difference between the repartition() function and the coalesce() function, we choose to use coalesce() function to control the number of partitions after the union() function in Step 5. Specifically, we set coalesce(numPartitions=2), so that the number of tasks observed in Spark UI goes through a loop of "2-4-6-2" in each iteration. For Iris dataset, this modification makes each iteration to finish in less than 0.5s, and entire processing time is around 70s (averaged over seven clustering methods).

• Applying checkpoint to cut the lineage of RDDs.

Since we find a way to control the number of partitions, and distributed Sim_AHC performs correctly on Iris dataset. We feed a larger dataset, 2cir_10xe3.txt to test the performance of our implementation. We observe that though the number of partitions is under control, occupied memory on each worker increases as the number of iterations increases. After the 200th iteration, all workers' memory is filled up and the program is forced to stop. In DAG visualization, we find We observe that as the number of iterations increases (there are 1999 iterations for 2cir_10xe3 dataset, with number of partitions being 5), the processing time per iteration gradually reduces from 5s to 0.7s, and checkpoint reconstruction time reduces from 3.3min to 30s. It is reasonable to have this decrease in time as the size of pairwise similarity table is reduced along iterations. The whole processing time of 2cir_10xe3 dataset takes around two hours to generate a complete dendrogram.

• Approaches that try to find the maximal similarity.

to observe running time. On several small samples (each has a few hundred rows) from 2cir_10xe5 dataset, we observe that as threshold value increases, the processing time of the count() function on resulting child RDDs decreases, and the number of counted values decreases as well. Similar to the count() function, RDD's max() function is also an action function, our tests imply that applying max() function on filtered RDDs would reduce the time of looking for the maximal similarity. However, if we use a threshold value to sparsify pairwise similarities, then search for the maximal in the filtered values, a question is: as pairwise similarities are updated after each iteration, how can we dynamically determine a threshold value that returns a non-empty (yet not too large) list of similarities in each iteration? Recall that it is impossible to return all similarities to the driver program when the input data is large, thus prior knowledge on the basic statistics of the similarities is unknown. In fact, in order to determine a proper threshold value, it is unavoidable to have an idea on the distribution of similarities, and this requires an action function on the whole RDDs' lineage, which is as expensive as looking for the maximal.

3. After many tests involved in the two solutions stated above, it seems that as long as the maximal similarity is searched in the full set of similarities, it is hard to avoid materializing the entire RDDs' lineage. For a dataset that has n objects, we are only interested to find the closest pair. If we are able to group the dataset into a few groups, each of which is composed of similar objects, then our objective is merely to find the closest pair in one of these groups, instead of computing all pairwise similarities and searching the maximal among them. So we formulate our problem to a problem of "looking for the nearest neighbor". A solution that we find to solve this problem is Locality Sensitive Hashing (LSH) [START_REF] Rajaraman | Finding similar items[END_REF]. The objective of LSH is to find the most similar pairs that are above some lower bound in similarity. The general procedure of LSH is composed of two steps: (1) it converts input data into a set of signatures, which are short but good representatives of data instances; and (2) it assigns similar data instances into different groups via their signatures. Depending on choice of similarities (such as Jaccard similarity, cosine similarity, etc), the method that computes signatures varies [START_REF] Wang | Hashing for similarity search: A survey[END_REF]. For example, Jaccard similarity is commonly used in searching similar web-pages, the corresponding hashing function that is used to compute the signatures of web-pages is MinHashing. Given a family of l hashing functions, In the resulting matrix, if two rows are identical, then they are similar objects that are assigned into one group. Parameter t ≈ (1/b) 1/r is the threshold in LSH that defines how similar data instances have to be in order for them to be considered as a desired "similar pair". If avoidance of false negatives is important, it is better to select b and r that produce a value lower than t;

if speed is important and it is desired to limit false positives, it is better to select b and r that produce a higher threshold [START_REF] Rajaraman | Finding similar items[END_REF].

• Python v.s. Scala.

Spark is implemented in Scala

Summary

In this section, we present the implementation of distributed Sim_AHC, by providing details on its computing procedure, debugging tool and practical knowledge learned from experimentation.

In looking for an answer to explain why this implementation cannot really work well on large datasets, we doubt that Spark may not be the suitable platform to an iterative algorithm like Sim_AHC, in which RDDs' lineage accumulates and only partial RDDs are required to be materialized for later iterations. Recall that "Spark is for bulk iterative algorithms" [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF].

The concepts of "bulk iterations" and of "incremental iterations" are distinguished in [START_REF] Ewen | Spinning fast iterative data flows[END_REF]: the former compute a complete new results from input data; while in the latter one, each iteration result only modifies or adds to some small subset of the input data.

In the case of Sim_AHC, it is more like an incremental iterative algorithm rather than a bulk iterative algorithm, because its result obtained in each iteration is dependent on previous iteration. This process requires mutable state to be updated and carried to the next iteration. Spark is not well-optimized to address this kind of iterative algorithms.

Recall that Spark RDDs are immutable, and manipulation on this property impacts computational efficiency of iterative algorithms.

The Distributed Implementation of Spectral-embedding

As seen in Algorithm 8, the core of SHCoClust is spectral embedding, which projects input data into a space that is constructed by the eigenvectors of graph Laplacian matrix. Given a document-term matrix A, performing spectral embedding on A projects it into a new space, where A becomes Z. SHCoClust applies Sim_AHC on Z, while the bipartite spectral graph partitioning method [START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] applies K-means on Z. Another distributed implementation that we provide here is the distributed spectral-embedding.

As spectral embedding is the basic step in Spectral-SVD methods, we believe that our implementation provides an option for other searchers to perform spectral embedding in their works. is firstly converted from a BlockMatrix into an IndexedRowMatrix. Then the built-in multiply() function of an IndexedRowMatrix is applied. This multiplication directly outputs an IndexedRowMatrix.

Computing Procedure

In order to remove the first columns in the resulting IndexedRowMatrices, we have to convert these two matrices into two sets of Spark indexed vectors, from which it is possible to remove elements in a specific column. After Z is output, there are different ways to perform clustering on Z. For example, we can use the distributed Sim_AHC on Z to apply (distributed) SHCoClust, we can also apply a Spark built-in clustering method, such as K-means to apply the (distributed) bipartite spectral graph partitioning method. In order to achieve efficiency, it is better to cache Z in the distributed memory during calculation.

It is worth to mention that when parallelizing a data object via SparkContext, the number of partitions is equal to the number of executor cores by default. However, in this distributed implementation, we observe that the number of partitions of Z is usually larger than the default value. This is caused by the fact that the combination of D × V is performed by a union() function, which automatically sums up the number of partitions of the two sets of RDDs. If Z is loaded from HDFS to perform clustering, it is advised to adjust the number of partitions of Z in order to achieve better performance.

Experiments and Analysis

In our experiments, we test the performance of distributed spectral embedding. Table 6.3 lists the experimented datasets, among which the SMART, AP and WSJ datasets are mentioned in Section 5.2. AP-1 and AP-2 are two sampled datasets from the full AP collection. The ZSDF dataset contains all files from four collections provided in our purchased TREC corpus 10 . These collections are "Ziff", "San Jose Mercury News", "Dept. of Energy" and "Federal Register". "Size (Mb)", "Num.Docs" and "Num.Terms" respectively list the size, the number of documents and the number of extracted terms of each dataset. When the assigned executor memory is fixed, for small datasets, it is hard to see the influence of the number of total cores on running time. As we can see in the experiments that use SMART and AP-1 datasets, the processing time for SVD and the total running time first decrease then increase as more cores are assigned. As to larger datasets, some trend can be observed. It is clear that in the experiments of AP-2, AP, WSJ and ZSDF datasets, as the number of total cores increase, the processing time of SVD and the total running time both decrease.

One explanation is that when too many cores are used to process a relatively small dataset, the benefit of distributed computing is lessened by the overhead of network communication and the cost of data shuffling among executors. However, when a dataset is large enough for a number of assigned cores and the amount of assigned memory, the overhead of network communication and the cost data shuffling become less dominant compared to the amount of processing time. As result, the time gain of distributed computing becomes more evident.

The results of this experiment imply that our implementation is capable to scale, when the number of cores increases, the processing time decreases. However, there is a condition for this scalability, i.e., the number of cores assigned in processing should be suitable to the size of input dataset. Otherwise, the computation cannot benefit from being distributed.

One of the bottlenecks of this implementation is the Spark built-in SVD() function. This function is implemented in Java and wrapped with py4j package so that it can be used as a Python function. However, it is not possible to adjust the level of parallelism inside this function through Python. By observing the running process, we think that the number of tasks is fixed in this function, and it cannot automatically adapt to the number of assigned cores. For a relatively large dataset, this can be problematic as the available computing power cannot be utilized, and cached data has to wait for being processed.

Another bottleneck is the BlockMatrix, which cannot yet accept a really large dataset.

And it does not support operations on sparse matrix either.

Conclusion

In this section, we present two distributed implementations, the distributed Sim_AHC and the distributed spectral embedding. For both implementations, we illustrate details on their computing procedures, debugging tool, data types and configuration parameters.

Implementing a Spark program is different from implementing a conventional program.

Configuration parameters, such as the number of cores, the size of executor memory, etc., have important impact on the performance of a Spark application. And there is no rule of thumb to set optimal values to these parameters. The only solution is to learn them from experiments. In implementing the distributed Sim_AHC, we obtain valuable experience from many failures. Though this program is being made better through many troubleshooting trials, it is still not performing as expected for a real large dataset. So far it is capable to return accurate results on small and medium-sized datasets. What is more important is our experience learned from this progress, such as the control over the number of partitions, the necessity of cutting an endlessly growing lineage by checkpoint, application of LSH to find similar objects, etc. Some of these learned knowledge provide us valuable practice in implementing the distributed spectral embedding and other programs using Spark. For SHCoClust, we implement its core, the spectral embedding, in a distributed manner. The key point of this implementation is to correctly convert data types between local types and distributed types, and to choose suitable distributed types when data is presented in a distributed matrix. Though there exist some bottlenecks due to some Spark built-in functions, this distributed implementation works properly. In our experiments, we demonstrate its scalability on several datasets that vary in size. We believe that this implementation provides an option in performing spectral embedding for methods that apply spectral embedding.

Chapter 7

Conclusions and Perspectives

Conclusions

In this thesis, with addressing text clustering tasks as our focus, we elaborate on our contributions on toward scalable hierarchical clustering methods, tests on the cluster hypothesis and distributed implementations.

First of all, interested in organizing documents in a collection and in preserving their interconnections, we study hierarchical clustering methods. Our focus is the conventional AHC methods that are unified by the Lance-Williams formula. The problem of conventional AHC methods is that they are computationally costly, due to their high complexity. To overcome this drawback, we propose Sim_AHC, a similarity-based hierarchical framework. It is equivalent to the Lance-Williams formula, but it uses inner product-based similarities instead of distances. This characteristic makes Sim_AHC advantageous: (1) as its similarities are between 0 and 1, we can apply a thresholding strategy to sparsify its similarity matrix. This results in improved computing efficiency.

In our experiments, we find out that sparsification indeed leads to reduced running time and memory use. And surprisingly, clustering quality is preserved and even improved.

Our analysis is that by sparsifying similarity matrix, noise is removed. Furthermore, it connects neighborhoods and absorbs data points that are close to these neighborhoods.

(2) using inner product-based similarities can easily extend similarities in Sim_AHC to kernel functions. In our experiments, we perform tests using similarity matrix that is generated by both linear and Gaussian kernels. In the work of Sim_AHC, our initial objective is to provide an equivalent framework to the Lance-Williams formula, with better computing efficiency.

Secondly, co-clustering methods draw our attention with its capability of simultaneously clustering data instances and data features. This property is beneficial in text clustering, as it can return co-clusters of documents and terms. However, in common coclustering methods, there is no information on how resulting co-clusters are connected and how elements in a co-cluster is structured. This motivates us to propose SHCo-Clust, a similarity-based hierarchical co-clustering method. It is a hybrid algorithm that processes the characteristic of co-clustering and hierarchical clustering. But it is more advantageous than the two. One one hand, the output of SHCoClust has richer information. It outputs a dendrogram, but unlike a dendrogram that is output by a hierarchical clustering, its dendrogram aggregates both documents and terms. By cutting this dendrogram, we can obtain a number of sub-dendrograms, each of which is a co-cluster that organizes its elements in a hierarchy. On the other hand, SHCoClust also uses inner product-based similarities. Like Sim_AHC, it can be extended to different kernel functions. And more importantly, a thresholding strategy can be applied in SHCoClust to achieve better computing efficiency. In our experiments, we discover that clustering quality of SHCoClust is guaranteed or improved when sparsification is applied. Comparing with conventional AHC methods, clustering quality in SHCoClust is much improved.

More importantly, we find that when sparsification is applied, on average 75% running time and memory use can be spared, while preserving clustering quality.

Thirdly, after applying Sim_AHC and SHCoClust in text clustering tasks, we further apply them in testing the cluster hypothesis. We believe that by testing this hypothesis, we are able to have better understanding on retrieval effectiveness and efficiency of these two frameworks. Another interest of doing this work is to provide a benchmark on this topic. In reviewing past research works, we find that in terms of which clustering method achieves the best retrieval effectiveness, there are different conclusions. Besides, efficiency issue is not sufficiently discussed in these works. In our tests that applies Sim_AHC and SHCoClust, we use optimal cluster search and the E-measure to evaluate retrieval effectiveness. In comparing retrieval effectiveness among seven clustering methods, we conclude that Ward method is the most effective method in most cases in the test of Sim_AHC. However, in the test of SHCoClust, a wider range of performing methods is obtained. In terms of efficiency, we examine the influence of improving efficiency by sparsifying similarity matrix on retrieval effectiveness. We discover that in both tests retrieval effectiveness tends to be invariant to the effect of sparsification, with substantial memory use and running time being reduced. Our analysis is that sparsifying similarity matrix like disconnects clusters that are near the root of a dendrogram, but leaves little impact on optimal clusters that are usually near the leaf nodes of the dendrogram. And in our experiments, we find that most optimal clusters are small clusters that are near the leaf nodes. In comparing Sim_AHC and SHCoClust, we discover that in MED, CISI and CACM datasets, Sim_AHC is more effective than SHCoClust using complete link, average link, McQuitty and Ward methods. On the contrary, SHCoClust is more effective than Sim_AHC using single link, centroid and median methods in AP and WSJ datasets. Besides, as SHCoClust generates more flat clusters than Sim_AHC, it has smaller variance of optimal E values than Sim_AHC.

Lastly, we provide distributed implementations of Sim_AHC and SHCoClust using Apache Spark engine. Along our study of Spark and implementing Sim_AHC and the core of SHCoClust, spectral embedding, we learn that the performance of a Spark program depends not only on the implementation, but also on the configuration of computing resources. After many trials and tests, we manage to implement the distributed Sim_AHC and the distributed spectral embedding. Along this process, we gain useful practical experience of using Spark and we share this experience in this thesis. We hope this can be a helpful reference for other people that are interest in implementing similar algorithms.

Perspectives

There are some points that we like to improve in our works: first of all, sparsification used in Sim_AHC and SHCoClust depends on a threshold value. Usually we pass a list of threshold values to see which one gives the best clustering quality with the least computing resources. But in practice, we probably want a function that can determines such a threshold value automatically. On this subject, we have not examined sufficiently.

And this is one of the further works that we would like to contribute. Secondly, in testing the cluster hypothesis using Sim_AHC and CoClust, we feel that there is more to do in examining optimal clusters. During our experiments, we observe that the size of optimal cluster usually links to its location in a dendrogram and affects the value of precision and recall. But we do not have systematic knowledge on this matter. It would be worth examining the link between the size of optimal cluster to retrieval effectiveness in the future. Lastly, as stated previously, we doubt that Spark may not be the suitable platform for Sim_AHC. An alternative might be using a parallel distributed computing platform. And we would like to look into this direction. We also notice that Spark is

  co-clustering, d'autre part, génère des co-clusters, contenant chacun un sous-ensemble d'instances de données et un sous-ensemble d'attributs de données. L'application de la classification sur les données textuelles permet d'organiser les documents et de révéler les connexions parmi eux. Cette caractéristique est utile dans de nombreux cas, par exemple, dans les tâches de recherche d'informations basées sur la classification. À mesure que la taille des données disponibles augmente, la demande de puissance du calcul augmente. En réponse à cette demande, de nombreuses plates-formes du calcul distribué sont développées. Ces plates-formes utilisent les puissances du calcul collectives des machines, pour couper les données en morceaux, assigner des tâches du calcul et effectuer des calculs simultanément. Dans cette thèse, nous travaillons sur des données textuelles. Compte tenu d'un corpus de documents, nous adoptons l'hypothèse de «bag-of-words» et applique le modèle vectoriel. Tout d'abord, nous abordons les tâches de la classification en proposant deux méthodes, Sim_AHC et SHCoClust. Ils représentent respectivement un cadre des méthodes de la classification hiérarchique et une méthode du co-clustering hiérarchique, basé sur la proximité. Nous examinons leurs caractéristiques et performances du calcul, grâce de déductions mathématiques, de vérifications expérimentales et d'évaluations. Ensuite, nous appliquons ces méthodes pour tester l'hypothèse du cluster, qui est l'hypothèse fondamentale dans la recherche d'informations basée sur la classification. Dans de tels tests, nous utilisons la recherche du cluster optimale pour évaluer l'efficacité de recherche pour tout les méthodes hiérarchiques unifiées par Sim_AHC et par SHCoClust . Nous aussi examinons l'efficacité du calcul et comparons les résultats. Afin d'effectuer les méthodes proposées sur des ensembles de données plus vastes, nous sélectionnons la plate-forme v vi d'Apache Spark et fournissons implémentations distribuées de Sim_AHC et de SHCo-Clust. Pour le Sim_AHC distribué, nous présentons la procédure du calcul, illustrons les difficultés rencontrées et fournissons des solutions possibles. Et pour SHCoClust, nous fournissons une implémentation distribuée de son noyau, l'intégration spectrale. Dans cette implémentation, nous utilisons plusieurs ensembles de données qui varient en taille pour examiner l'échelle du calcul sur un groupe de noeuds.

2. 1 . 1 . 4

 114 Text Clustering Algorithms: An Overview Aggarwal and Zhai[START_REF] Charu | A survey of text clustering algorithms[END_REF] present two major types of clustering algorithms: distancebased methods and word-phrase-based methods. Distance-based clustering algorithms contain two members, agglomeartive hierarchical clustering (AHC) and distance-based partitioning algorithms (Figure2.1). The AHC approach processes the pairwise distances of input documents, and outputs a binary tree structure that explicitly presents the interconnections among input documents. More details on this approach are provided in Section 2.2. In contrast, the K-medoid and the K-means algorithms are partitioning algorithms. They return flat clusters of documents. The distances of documents to their cluster representatives are supposed to be minimized in convergence. A hybrid

Figure 2 . 1 :

 21 Figure 2.1: Overview of text clustering algorithms

platform 1 ,

 1 which is an advanced directed acyclic graph (DAG) execution engine that supports cyclic data flow and in-memory computing. The core concept of Spark are the resilient distributed datasets (RDDs), which makes Spark low I/O cost and fast computing engine. Spark has been shown to be 100 timess faster than Hadoop MapReduce.

Figure 2 . 2 :

 22 Figure 2.2: MapReduce execution overview [1]

  putation and reuses them in other operations. The advantage of caching RDDs is that it avoids much I/O overhead. There are two operations supported by RDD abstraction: transformations and actions. An input dataset is firstly converted into a set of RDDs. By applying transformation functions, the input RDDs are transformed and this process generates a lineage of RDDs. Transformations are lazy functions, they do not execute until an action function is called. An action function executes all the transformation functions that construct the RDDs' lineage and returns final results, which are displayed or stored on local disk.

  is the easiest way to run a Spark application on a top of a cluster. Apache Mesos and Hadoop Yarn are two different resource managing softwares. Mesos is built to be a global resource manager for an entire data center. It determines what resources are available when a job request comes into the Mesos master. Once the job request is accepted, it places the job on the workers. Hadoop YARN (short for Yet Another Resource Negotiator) is the second-generation MapReduce. It is a central resource manager for a Hadoop cluster. It monolithic schedules jobs after evaluating all available resources.

Figure 2 . 5 :

 25 Figure 2.5: Spark cluster architecture

Figure 2 .

 2 Figure 2.5 illustrates the structure of a cluster of nodes when a cluster mode is deployed 3 .

Figure 2 . 6 and

 26 Figure 2.6 and Figure 2.7 illustrate the major difference between Hadoop MapReduce

Figure 2 . 6 :Figure 2 . 7 :

 2627 Figure 2.6: When MapReduce runs an iterative job

[ 2 ]

 2 , clustering can be categorized into hard and fuzzy clustering. In hard clustering, each data instance belongs to one cluster; in fuzzy clustering, on the other hand, a data instance can be possessed by several clusters. Hard clustering further contains partitional and hierarchical clustering. Partitional clustering is also called flat clustering, it outputs individual clusters that do not connect to each other. K-means is an example of flat clustering. Hierarchical clustering outputs a binary tree-like structure, called dendrogram (Figure 2.9). A dendrogram explicitly exhibits the connections among clusters, i.e., how data instances are grouped iteratively. This presentation is advantageous in revealing interconnections of data instances and sub-clusters. A classic example of dendrogram is the revolutionary tree that exhibits the evolutionary relationship among various biological species, based on similarities and differences in their physical or generic characteristics.

Figure 2 . 8 :

 28 Figure 2.8: Overview of clustering methods

Figure 2 . 9 :

 29 Figure 2.9: Example of dendrogram

Algorithm 1

 1 General procedure of AHC Data: Pairwise dissimilarity matrix D of input data Initialize a dendrogram of n leaves with null height values while number of iterations < n do 1. (C i , C j ) = arg min (Cx,Cy) D(C x , C y ), i.e. search for the minimal distance in D and the pair of clusters (C i , C j ), 2. merge C i and C j into C ij and add a corresponding parent node in the dendrogram with height value D(C i , C j ), 3. compute distance between C ij and another cluster C k , and update D accordingly. end Result: A dendrogram of 2n -1 nodes There are different distance measures to compute D(C i , C j ), some of the commonlyused measures for numeric and for binary data are listed in Table 2.3, where X = (x 1 , . . . , x m ) and Y = (y 1 , . . . , y m ) denote two vectors of m features. Note that the Minkowski distance becomes Manhattan distance, Euclidean distance and maximum distance, when its parameter p takes values of 1, 2 and ∞, respectively.

Figure 2 . 10 :

 210 Figure 2.10: Commonly used conventional AHC methods[2]

Figure 2 . 11 :Algorithm 2

 2112 Figure 2.11: Comparison of conventional AHC methods (left) and the NN-chain algorithm (right) [3]

Figure 2 . 12 :

 212 Figure 2.12: Dendrograms without and with height inversion

Figure

2. 14

 14 (a) illustrates an example, in which a bipartite graph models a small document-term matrix. Its vertices are composed of documents and terms, and each of its edges carries a TF-IDF value. With this model, finding co-clusters in a data matrix is equivalent to partitioning its bipartite graph into several sub-graphs.

Figure 2 .

 2 14(b) displays a solution that partitions the bipartite in Figure 2.14(a) into two sub-graphs, V 1 and V 2 . Each sub-graph contains a subset of documents and a subset of terms.

Figure 2 . 14 :

 214 Figure 2.14: An illustration of (a) a bipartite graph and (b) its partitions. d i denotes a document, t j denotes a term, e ij denotes an edge that links d i and t j . V 1 and V 2 denote two sub-graphs.

. 29 )

 29 Equation 2.29 in fact represents the canonical forms of the Singular Value Decomposition (SVD) of matrix A n . σ is a singular value, while µ and ν are the corresponding left and right singular vectors for σ. As shown in Section 2.3.3.2, when K = 2, the solution

Figure 2 .

 2 15 (a) illustrates the optimal cut on a cockroach graph obtained by either RatioCut or Ncut, which results in two horizontal sub-graphs. However, by Spectral-SVD, it obtains two vertical sub-graphs shown as Figure2.15 (b), where the cut is not optimized.

Figure 2 . 15 :

 215 Figure 2.15: A cockroach graph partitioned by (a) an ideal cut and by (b) a Spectral-SVD method

  the classic tests, the refined tests, and the language model-based tests. By reading this section, reads can have a good understanding on the concept of the cluster hypothesis, as well on different tests proposed in the past. In this thesis, we contribute to the classic tests. Concretely, we propose new tests that apply Sim_AHC and SHCoClust, with focus on comparing retrieval effectiveness among different hierarchical clustering methods and addressing efficiency issue.

  , x) = S(y, y) = 1 always holds. Given Equation 3.3, the corresponding dissimilarity D(x, y) can be defined as:D(x, y) = || x ||x|| -y ||y|| || 2 = S(x, x) + S(y, y) -2S(x, y) = 2(1 -S(x, y)). (3.5) Now let x and y be two vectors C x and C y , each representing a cluster. Under the above assumptions, we can provide an equivalent expression of the Lance-Williams formula using S instead of D. Recall that in the first iteration of the AHC algorithm (Algorithm 1), there are n clusters, each being one data point C x . With Equation 3.5, we can deduce a relationship shown as follows:

  and Equation 3.9 reduces to S(C (ij) , C (ij) ) = 1, as α i + α j + 2β = 1 with parameter values in Table2.5.

j=1 a 2 ij( 3 Algorithm 7

 237 individual document vector is scaled to unit norm. Let a i. denote a document vector represented by m TF-IDF values. It is suitable to adopt the l 2 -norm to normalized a i. into: âi. = a i. ∥a i. ∥ with ∥a i. ∥ = m ∑ .13) with ∥a i. ∥ denoting the norm of a i. and âi. denoting the normalized form. Normalization on A outputs Â. The input to Sim_AHC is the pairwise similarity matrix S of Â, S = Â ÂT . Algorithm 7 details the computing procedure of Sim_AHC. Sim_AHC computing procedure Data: The pairwise similarity matrix S Initialize a dendrogram of n leaves with null height values while number of iterations < n do 1. Search for the pair of clusters (C i , C j ) that has the maximal similarity in S, by Equation 3.10, 2. Merge C i and C j into C (ij) and add a corresponding parent node in the dendrogram with height value [S(C i , C j ) -1 2 (S(C i , C i ) + S(C j , C j ))], 3. Compute the similarity of C (ij) and any other cluster C k and update S accordingly, by Equations 3.11 and 3.12. end Result: A dendrogram of 2n -1 nodes Unlike the dendrogram output by a conventional AHC method, the dendrogram output by Sim_AHC is growing downwards. The height of a newly merged cluster is [

D 1 and D 2

 2 store the row sums and column sums of A. If A is represented as a graph, its documents and terms are vertices, its edges carry the TF-IDF weights, D 1 and D 2 are in fact the degree matrices for the document vertices and for the term vertices, respectively. Having D 1 and D 2 , they generate A n by matrix multiplication.

  A full dendrogram output by SHCoClust contains n + m leaves and n + m -1 internal nodes. Cutting the dendrogram at some height results in a number of flat co-clusters, each contains a sub-dendrogram of documents and terms, in Section 4.4, visualization of a sampled dataset is presented.

Figure 4 . 1 :

 41 Figure 4.1: Comparisons of clustering quality among conventional AHC, BSC, SHCo-Clust with and without sparsification

Figure 4 . 2 :

 42 Figure 4.2: Results of linear kernel and Gaussian kernel with sparsification

2 )

 2 and the time complexity of applying Sim_AHC on Z can reach O((n + m) 3 ). Sparsifying S with τ results in M non-zero values stored for computation, M < (n + m) 2 , eventually reduces storage complexity to O(M ) and time complexity to O((n + m)M ). The linear relationship between the storage and time complexity is demonstrated by the lines of relative memory and relative running time in Figure 4.2. Let τ * define a threshold value,at which clustering quality is preserved as high as possible, meanwhile S is sparsified to have M as small as possible. As stated previously, τ at percentile rank of 75% is the τ * for most cases in our experiment.

  Since 1970s, many researchers have devoted their efforts to testing the cluster hypothesis from different aspects. Depending on the content of these works, we categorize these tests into classic tests, refined tests and language-model-based tests. For the classic tests, a group of research works emphasize comparisons of retrieval effectiveness between cluster-based and document-based retrieval systems; while some other works focus on testing the cluster hypothesis using hierarchical clustering methods; or on comparing cluster-based searching strategies in a hierarchy of clusters. The refined tests propose improved modification on some of the classic tests. Both classic tests and refined tests are based on the "bag-of-words" assumption, and they apply the vector space model to process their inputs. Differently, the language-model-based tests assume that documents are distributions of terms, thus the basic function that is used to measure similarities among documents varies from the other tests. More details on these works can be found in Section 2.4 in Chapter 2.

3 . 1 in

 31 Chapter 3. CACM dataset is a collection of abstracts from computer science journals. The other two datasets are sampled from Associated Press (AP) and Wall Street Journal (WSJ) collections, which are part of the TREC collection 3 . The full AP and WSJ collections in TREC contain 242,275 newswire articles and 161,512 journal articles, respectively.

Figure 5 . 1 :

 51 Figure 5.1: Illustration of results in Table 5.3 for each tested dataset

  selected from the {10, 25, 50, 75, 90}% percentile ranks of values in S. Results of this experiment are displayed in Figure 5.2 (when S is generated by linear kernel) and in Figure 5.3 (when S is generated by Gaussian kernel), where x-axis corresponds to the percentile ranks. Dotted line with circle sign and solid line with triangle sign represent the relative memory usage and the relative running time, respectively. Dashed lines with plus sign, cross sign and square sign indicate the averaged optimal E values at β = 0.5, 1.0 and 2.0, respectively.

Figure 5 . 2 :Figure 5 . 3 :

 5253 Figure 5.2: Results of sparsifying S obtained by linear kernel

Figure 5 .

 5 Figure 5.4 plots the results in Table5.6. Like in Figure5.1, integers 1-7 along x-axis map to seven clustering methods. Dotted line with circle sign, solid line with triangle sign and dashed line with plus sign represent the averaged optimal E values at β = 0.5, 1 and 2, respectively. Note that each plot has its own scale for y-axis. From Figure5.4, we can observe that, all E curves are less fluctuate than in Figure5.1 and tend to keep flat. This indicates that unlike in Sim_AHC, clustering methods in SHCoClust are close to each other in terms of retrieval effectiveness. One thing in common to Figure5.1 is that, E values at β = 0.5 are lower than those at β = 1 and 2 in MED, CISI and CACM datasets. In AP and WSJ datasets, however, E values at β = 2 is lower than those at β = 0.5 and 1. In particular, in MED dataset, E curves are better separated in SHCoClust than in Sim_AHC.

Figure 5 . 5 andFigure 5 . 3 ,

 5553 Figure 5.5 and Figure 5.6 illustrate experiment results of sparsifying S co , which is obtained using linear kernel and Gaussian kernel, respectively. Like in Figure 5.2 and in Figure 5.3, percentile ranks are along x-axis; (green) dotted line with circle sign represents relative memory use, Mτ M τ =0 , and (orange) solid line with triangle sign denotes relative running time, Tτ T τ =0 . Dashed lines with plus sign, cross sign and square sign indicate the averaged optimal E values at β = 0.5, 1 and 2, respectively.

Figure 5 . 5 :

 55 Figure 5.5: Results of sparsifying S co obtained by linear kernel

Figure 6 . 1 :

 61 Figure 6.1: Computing procedure of distributed Sim_AHC using Spark RDDs. C x and C y denotes two clusters, S xy denotes their pairwise similarity and S ′ xy denotes their self similarity.

Figure 6 . 2 :

 62 Figure 6.2: Screenshot of Spark web UI homepage

Figure 6 . 5 .

 65 Figure 6.5. It shows the growth of lineage of RDDs through consecutive stages inside a job. It helps us to track the growth of RDDs' lineage. If the lineage is too long, it is then necessary to cut the lineage in order to save memory and to accelerate calculation.

H = {h 1

 1 , . . . , h l }, each hash function operates on each data instance in the input dataset (assuming it has n instances and m features), generating a signature matrix of shape n × l. This process is like projecting the input dataset into a new space of l dimensions. Each signature represents an input data instance. Next step is to assign signatures into a number of groups, each group containing a set of similar data instances. Two more parameters are required here, the number of bands b and the number of signatures in each band r, b × r = l holds. We can consider that the signature matrix is vertically cut into b parts, each part having r columns. Hashing signatures in the signature matrix band by band and row by row outputs a matrix of n × b.

Figure 6 . 2 . 2 - 1 /2 1 ×A×D- 1 /2 2 .- 1 /2 1 × 2 2 .- 1 /2 1 × U and D - 1 /2 2 ×- 1 /2 1 ×- 1 /2 2 ×

 6221112112211121112 Figure 6.8 illustrates the computing procedure of distributed spectral-embedding. The input is a collection of raw documents that are stored on HDFS. After preprocessing, this collection is converted into a distributed document-term matrix A, which is also store on HDFS. There are two other inputs, which are saved as two lists in the master node (where runs the driver program). They are the inverse squared root of the row sums and of the column sums of A, denoted by D -1/2 1 and D -1/2 2 . Differing from a conventional program, where data is cached in the RAM of a single machine. In a Spark program, an object may be cached in the RAM of the master node or in the distributed RAM of the workers. Thus a Spark program operates on both local data types and distributed data types. The Spark local vector (dense or sparse), labeled

4 .- 1 /2 1 ×- 1 /2 2 ×

 41112 Generating final output. The last step is to combine the two sets of distributed indexed vectors resulted from D U and from D V . The combination outputs Z, a set of distributed indexed vectors, which is stored as a set of Spark pickle files on HDFS.

-1/2 1 ×

 1 U and D -1/2 2

  gradually moving to DataFrame from RDDs. Maybe we can use DataFrame to improve the implementation of distributed spectral embedding. Avec la formule de Lance et Williams et les méthodes classiques de classification ascendante hiérarchique comme notre base de référence, nos expériences utilisant des proximités générées par le noyau gaussien et le noyau linéaire démontrent que, les résultats obtenus par Sim_AHC sont identiques à ceux produits par les méthodes initiales.Plus important encore, lorsque la matrice de proximités est rendue plus en plus éparse, l'utilisation de la mémoire et du temps de fonctionnement diminuent. Par contre, la qualité de la classification est garantie, grâce au fait que les bruits sont supprimés par le seuillage.Contrairement à la classification hiérarchique, le co-clustering effectue la classification dans l'espace de données et l'espace des attributs. Cependant, le co-clustering ne peut pas préserver l'interconnexion des éléments qu'il regroupe. Pour surmonter cet inconvénient, nous proposons SHCoClust[START_REF] Wang | Shcoclust, a scalable similarity-based hierarchical co-clustering method and its application to textual collections[END_REF], la méthode de co-clustering hiérarchique basée sur la similarité. Il est considéré comme une méthode hybride de Sim_AHC et de coclustering spectral. Concrètement, dans SHCoClust, nous modelons un corpus de documents comme une graphe bipartite, dont les sommets sont des documents et des termes.Ensuite, nous appliquons la méthode de spectral-SVD[START_REF] Von | A tutorial on spectral clustering[END_REF] pour couper la graphe en plusieurs sous-graphes, chaque étant un co-cluster. La méthode de spectral-SVD, en fait, construit une espace avec les vecteurs propres de la matrice laplacienne de la graphe bipartite. Puis, elle projette la matrice originale dans cette espace. Nous appliquons la classification hiérarchique Sim_AHC sur la matrice transformée.SHCoClust hérite des caractéristiques de la classification hiérarchique Sim_AHC et du co-clustering spectral. Il produit un dendrogramme composé à la fois de documents et de termes. En coupant le dendrogramme, nous pouvons obtenir un certain nombre de coclusters, dont chacun est un co-cluster hiérarchique, c'est-à-dire que les interconnexions de documents et de termes dans un co-cluster sont préservées. Plus important encore, comme SHCoClust utilise également des proximités du produit scalaire, nous pouvons également l'étendre aux fonctions du noyau et nous pouvons appliquer une stratégie du seuillage pour rendre la matrice éparse. Nos expériences démontrent que la qualité de la classification de SHCoClust est en grande partie améliorée par rapport aux méthodes de la classification hiérarchique conventionnelle. Par rapport à la méthode de co-clustering spectral, SHCoClust réalise une amélioration lorsque sa matrice de proximités est rendu éparse. En outre, nous constatons que, en épargnant la matrice de proximités, bien que moins de mémoire et moins de temps soient nécessaires pour effectuer le calcul, la qualité de la classification peut être garantie. Dans nos ensembles de données testés, en moyenne, un gain du mémoire et un gain du temps jusqu'à 75 % sont obtenus sans nuire à la qualité de la classification.

Table 2

 2

	Transformations Actions
	map(func) reduce(func)
	flatMap(func) collect()
	filter(func) count()
	groupByKey() first()
	reduceByKey() take(n)
	sortByKey() saveAsTextFile(path)
	mapValues(func) counteByKey()
	union() foreach(func)
	distinct() collectAsMap()
	... ...

.1 lists a few transformations and actions functions.

Table 2 .

 2

1: A few RDDs' transformations and actions functions

Table 2 . 2 :

 22 Types of commonly-used RDDsIn Spark, a user program is an application. Each application is composed of a number of jobs, and each job has a number of tasks. In terms of executing an application, Spark provides two modes: the local mode and the cluster mode. When Spark launches an application in local mode, all the tasks are actually run on one machine but in a multithreading way. This mode is useful in developing, testing and debugging programs using

small datasets. Cluster mode is deployed when a cluster of nodes is configured. Depending on the types of resource manager, there three cluster modes: standalone mode, Spark on Apache Mesos, and Spark on Hadoop YARN. The standalone mode is Spark's built-in cluster environment. It is available in the default distribution of Spark and it

  these processes are coordinated by the SparkContext, which is initialized in the driver program. Executors run the processes and store data on worker nodes. With the cluster manager allocating resources, Spark acquires executors from cluster nodes and sends user program to the executors, on which the user program is split into tasks, each task is a unit process4 .Spark provides two sets of Machine Learning libraries (MLlib), the RDD-based 5 and the DataFrame-based6 . A Spark DataFrame 7 is a distributed collection of data that is organized into named columns. It is conceptually equivalent to a table in a relational database or a data frame in R/Python, but with richer optimizations under the hood.DataFrames can be constructed from a wide array of sources such as existing RDDs, structured data files and tables in Hive 8 . Starting from Spark 2.0, the RDD-based MLlib entered maintenance mode and new features are only added to DataFrame-based MLlib.

From the production point of view, it is more efficient to use DataFrame-based MLlib in a business project, as the built-in ML functions allow users to quickly implement standard pipelined-programs without digging into implementation details like using the RDDbased libraries. However, these functions leave users little control over the data, and

Table 2 . 3

 23

: Commonly-used distance measures for numeric and binary data

[START_REF] Michel | Encyclopedia of distances[END_REF]

Table 2 . 4 :

 24 Graphic and geometric methods for computing D(C ij , C k )[START_REF] Müllner | Modern hierarchical, agglomerative clustering algorithms[END_REF]

  provides an alternative method, the nearest neighbor test. She assumes that the k nearest neighbors of a document d are the k documents that are the most similar to d. Therefore, if the cluster hypothesis holds for a collection, then many of the nearest neighbors of a relevant document would also be relevant. For each relevant document of each query, this test examines whether the assumption holds by computing the k nearest neighbors of a relevant document and recording the number of relevant documents in the set of neighbors. Four datasets

(MED, CACM, CISI

16

and INSPEC) are experimented, with k ∈ [0, 5]. The nearest neighbor test concludes that the cluster hypothesis holds for the MED collection, but

Table 3 . 1 :

 31 1 [108], SMART[START_REF] Inderjit S Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] and 20Newsgroups 2[START_REF] Lang | NewsWeeder : learning to filter netnews[END_REF]. The Reuters corpus is a collection of newswire articles, assembled and indexed with categories by personnel from Reuters Ltd. Its ApteMode is a collection of 10,788 financial articles from 90 categories (classes). This collections is skewed (yet less than the original corpus) with 36.7% of the documents in the most common classes, and only 2 documents in each of the five least common classes. In our experiment, we generate a sample of the ApteMode collection, named Reuters, by firstly ignoring the classes that have less than 50 documents, and then randomly sampling (without replacement) a number of articles from each remaining class. The SMART corpus contains three classes, MENDLINE, CISI and CARNFILED, containing 1033, 1460, and 1400 journal abstracts on medicine, informatics and aerodynamics, respectively. The 20Newsgroups corpus contains 18,821 news articles from 20 classes. The number of documents in each class varies between 628 to 999. In our experiments, we use a sample of the 20Newsgroup corpus, named 20NG, by randomly selecting (without replacement) 300 documents from 15 classes. Details of datasets used in our experiments can be found inTable 3.1. , sci.electronics, comp.sys.ibm.pc.hardware, rec.sport.hockey, talk.politics.guns, comp.os.ms-windows.misc, soc.religion.christian, 15 4483 4455 rec.autos, rec.motorcycles, sci.crypt, sci.med, sci.space rec.sport.baseball, talk.politics.mideast, comp.graphics Descriptions of experimented datasets

	No. No.	No.

Table 3 . 2

 32 .2, we report the best outcomes of this phenomenon. Mem% and Time% indicate the percentage of saved memory and processing time, respectively, when the sparse S is compared to the dense S.

		Method	kernel	τ	Mem% Time% CC	ARI
	Reuters	Average Gaussian Average Gaussian 0.99 0	0 -75	0 -62	1 0.81 0.539 0.543
	SMART	Average Average	Linear Linear	0 0.078	0 -90	0 -85	1 0.96 0.944 0.939
	20NG	Ward Ward	Gaussian Gaussian 0.99 0	0 -50	0 -47	1 0.26 0.154 0.100

: Best ARI results for each collection when τ = 0 (baseline) and when τ > 0 (sparsified S)

Table 4 .

 4

1: Experimented Datasets

Table 4 .

 4 2 exhibits the consummation of resources measured by memory gain and time gain at τ * , at which highest ARIs are obtained (marked by *). The clustering methods that output ARIs* and the ARI values of SBC are listed. -x in Mem% and Time% indicates the relatively reduced memory and time compared to using a full-sized input.

	Dataset Method τ * value Mem% Time% ARI* BSC
	R5	Median	0.242	-25	-8	0.395 0.263
	R7	Ward	0.998	-75	-61	0.158 0.069
	S0	Average	0.996	-90	-86	0.803 0.753
	S1	Centroid	0.778	-50	-11	0.770 0.752
	NG8	Centroid	0.880	-75	-43	0.287 0.222
	NG20	Ward	0.998	-75	-37	0.158 0.094

Table 4 . 2

 42

	reduced memory usage and running time. Except for R5 dataset, in which median
	method only gains 8% in time and 25% in memory, other datasets obtain up to 86%
	time gain and 75% memory gain on average. This proves that SHCoClust is good at
	economizing computing resources, meanwhile preserving the clustering effectiveness. In
	other words, if given limited computing resources, SHCoClust is able to process relatively
	large datasets. This reflects the scalability of SHCoClust.

: Highest ARI, relative gain in memory and in time with sparsiciation From this table we can see that all ARIs* are higher than those of SBC, implying a better clustering quality in SHCoClust. Moreover, ARIs* are obtained with significantly

Table 5 .

 5 1 lists the details of the five experimented datasets.

	Collection		Classic-3		TREC
	Dataset	MED CISI CACM AP WSJ
	nb.docs	1033 1460	2936	3147 1937
	nb.terms	651	578	263	1562 1345
	nb.queries	30	76	52	61	27
	nb.docs/query	23	41	15	2	2

Table 5 . 1 :

 51 Experimented datasets

Table 5 . 2 :

 52 .4 column-wise minimal standard deviation is highlighted. By observing Table 5.3, we can see that in both kernels Ward dominates the other methods with better retrieval effectiveness; McQuitty and average link achieve the best effectiveness in some cases. A brief summary of Table 5.3 is provided in Table 5.2, which lists the clustering methods that obtain at least two lowest averaged E values at β = 0.5, 1 and 2. Clustering methods that obtain at least two lowest averaged E values at β = 0.5, 1 and 2

	Kernel/Dataset	MED	CISI CACM	AP	WSJ
	Linear kernel	Ward	Ward Ward Ward McQuitty
	Gaussian kernel average Ward Ward Ward McQuitty

Table 5 . 3 :

 53 Retrieval effectiveness measured by averaged optimal E values for seven clustering methods in Sim_AHC using linear and Gaussian kernels

	Linear kernel	Dataset β = single 0.452 0.549 0.582 0.678 0.774 0.761 0.686 0.779 0.813 0.713 0.694 0.622 0.757 0.736 0.666 MED CISI CACM AP WSJ 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 complete 0.498 0.625 0.658 0.641 0.747 0.750 0.607 0.713 0.730 0.612 0.573 0.467 0.645 0.611 0.523 average 0.453 0.519 0.489 0.611 0.700 0.686 0.626 0.708 0.706 0.611 0.578 0.474 0.632 0.597 0.504
		McQuitty 0.469 0.554 0.538 0.611 0.709 0.700 0.620 0.709 0.709 0.610 0.572 0.461 0.628 0.593 0.498
		centroid 0.591 0.716 0.752 0.757 0.844 0.814 0.682 0.765 0.787 0.829 0.828 0.805 0.899 0.905 0.902
		median 0.526 0.639 0.682 0.683 0.789 0.790 0.668 0.748 0.753 0.766 0.744 0.682 0.819 0.801 0.756
		Ward 0.438 0.518 0.513 0.598 0.696 0.696 0.574 0.670 0.675 0.609 0.571 0.463 0.645 0.608 0.517
	Gaussian kernel	Dataset β = single 0.452 0.549 0.582 0.678 0.774 0.761 0.686 0.779 0.813 0.713 0.694 0.622 0.757 0.736 0.666 MED CISI CACM AP WSJ 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 complete 0.492 0.616 0.645 0.640 0.746 0.749 0.605 0.708 0.725 0.612 0.574 0.466 0.645 0.610 0.520 average 0.454 0.520 0.498 0.612 0.703 0.691 0.627 0.714 0.714 0.616 0.584 0.483 0.637 0.601 0.503 McQuitty 0.467 0.552 0.549 0.612 0.711 0.703 0.618 0.705 0.706 0.615 0.577 0.466 0.631 0.598 0.507
		centroid 0.479 0.527 0.512 0.688 0.755 0.734 0.715 0.769 0.762 0.807 0.788 0.717 0.855 0.833 0.775
		median 0.490 0.562 0.561 0.671 0.755 0.742 0.685 0.754 0.747 0.760 0.732 0.642 0.804 0.776 0.705
		Ward 0.455 0.540 0.530 0.600 0.695 0.691 0.575 0.675 0.682 0.611 0.573 0.465 0.644 0.608 0.519

Table 5 . 4 :

 54 Standard deviation of optimal E values for seven clustering methods, corresponding to Table5.3

Table 5 .

 5 6 and Table 5.7 illustrate the results of this experiment. A value in Table 5.6

Table 5 .

 5 table, we can see that for linear kernel, average link outperforms the others in CISI and CACM datasets, with complete link for AP and WSJ datasets. For Gaussian kernel, the best performing method is Ward for CISI dataset, centroid for AP dataset, single link for CACM and WSJ datasets. It is interesting to see that the clustering methods that return the minimal averaged optimal E values in this test are very different from those in the test of Sim_AHC, where only Ward, McQuitty and average link are the winners. Results in this test provide awider range of outperforming methods, especially for Gaussian kernel. However, one thing in common with the Sim_AHC test is that, as β increases from 0.5 to 2, the averaged optimal E values increase for MED, CISI and CACM datasets, and decrease for AP and WSJ datasets (Table5.6). Likewise, this is influenced by the sizes of optimal clusters and the number of relevant documents per query.By observing Table5.3 and Table5.6, we find that, in comparison with Sim_AHC, SHCo-Clust returns higher (averaged optimal) E values for MED, CISI and CACM datasets, and lower E values for AP and WSJ datasets. This implies that SHCoClust has better retrieval effectiveness than Sim_AHC for AP and WSJ datasets, but for the other datasets Sim_AHC has better retrieval effectiveness. And from Table5.4 and Table5.4, we can observe that, compared to Sim_AHC, SHCoClust usually obtains lower standard deviation for MED, CISI, CACM datasets and higher standard deviation for AP and WSJ datasets. There are two reasons to explain these:(1) in SHCoClust, the dendrogram of a clustering method grows by aggregating both documents and terms.Compared to Sim_AHC, SHCoClust requires a larger number of iterations to complete clustering, and it eventually outputs a larger dendrogram, with documents and terms being its leaf nodes. When flattening this dendrogram to perform optimal cluster search, a larger number of flat clusters (with terms being removed) are generated, providing more candidates for the optimal cluster; (2) AP and WSJ datasets have only a few relevant documents per query. Therefore, it is more probable for a generated flat cluster to contain all relevant documents for a query. As SHCoClust generates more flat clusters than Sim_AHC, it is more likely to find small clusters that have precision equal to 1.Besides, as the number of relevant documents is small, recall tends to be high as well.MED, CISI and CACM datasets, on the other hand, have more relevant document per query. Therefore, it is like to have lower recall than AP and WSJ datasets.

	Kernel/Dataset MED	CISI	CACM	AP	WSJ
	Linear kernel	-	average average complete complete
	Gaussian kernel	-	Ward	single	centroid	single

5: Clustering methods that obtain at least two lowest averaged optimal E values at β = 0.5, 1 and 2

  [START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF]

  [START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF]

  [START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF]

  [START_REF] Wang | Fast nonnegative matrix tri-factorization for large-scale data co-clustering[END_REF]

  Illustration of results in Table5.6 for each tested dataset

	0.40 0.45 0.50	•	•	•	•	•	•	•
		1	2	3	4	5	6	7
	Figure 5.4:

Table 5 . 6 :

 56 Retrieval effectiveness measured by averaged optimal E values for seven clustering methods in SHCoClust using linear and Gaussian kernels

	Linear kernel	Dataset β = single 0.686 0.772 0.726 0.728 0.790 0.742 0.690 0.789 0.811 0.484 0.503 0.467 0.473 0.488 MED CISI CACM AP WSJ 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 complete 0.676 0.770 0.718 0.733 0.792 0.740 0.684 0.787 0.808 0.484 0.503 0.458 0.439 0.451 0.413 2 0.458 average 0.678 0.758 0.706 0.725 0.789 0.734 0.683 0.784 0.806 0.505 0.521 0.470 0.456 0.467 0.426
		McQuitty 0.680 0.760 0.714 0.729 0.788 0.735 0.684 0.785 0.810 0.504 0.523 0.474 0.457 0.463	0.418
		centroid 0.677 0.753 0.699 0.726 0.788 0.740 0.683 0.787 0.810 0.505 0.521 0.470 0.456 0.466	0.425
		median 0.679 0.757 0.720 0.729 0.789 0.737 0.687 0.789 0.808 0.505 0.523 0.473 0.457 0.463	0.418
		ward 0.679 0.754 0.698 0.725 0.787 0.741 0.681 0.787 0.814 0.499 0.517 0.469 0.445 0.456	0.419
	Gaussian kernel	Dataset β = single 0.673 0.759 0.749 0.733 0.818 0.800 0.675 0.774 0.797 0.525 0.562 0.529 0.493 0.502 0.453 MED CISI CACM AP WSJ 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 0.5 1 2 complete 0.645 0.744 0.707 0.722 0.798 0.767 0.677 0.778 0.796 0.514 0.539 0.490 0.566 0.559 0.498 average 0.645 0.735 0.679 0.722 0.788 0.745 0.683 0.782 0.796 0.525 0.546 0.491 0.566 0.559 0.498 McQuitty 0.651 0.730 0.687 0.721 0.788 0.747 0.680 0.778 0.793 0.525 0.548 0.499 0.556 0.546 0.469
		centroid 0.643 0.734 0.687 0.723 0.790 0.752 0.687 0.781 0.796 0.506 0.529 0.483 0.568 0.560	0.496
		median 0.643 0.737 0.703 0.722 0.790 0.750 0.682 0.778 0.789 0.512 0.532 0.480 0.552 0.545	0.477
		Ward 0.650 0.740 0.691 0.728 0.787 0.744 0.678 0.780 0.795 0.514 0.536 0.485 0.539 0.537	0.480

Table 5 . 7 :

 57 Standard deviation of optimal E values for seven clustering methods, corresponding to Table5.6

Table 5

 5 .8 displays T values of all T-tests, with those whose absolute value are smaller than critical value being highlighted in red.For T-tests that accept H 1 in MED, CISI and CACM datasets, we further compare the averaged optimal E values of Sim_AHC (Table5.3) and SHCoClust (Table5.6), we conclude that for these datasets Sim_AHC is significantly more effective than SHCoClust using complete link, average link, McQuitty and Ward methods. On the other hand, for T-tests that accept H 1 in AP and WSJ datasets, we find that SHCoClust is significantly more effective than Sim_AHC using single link, centroid and median methods.

	From Table 5.8, we can observe that most (absolute) T values are greater than critical
	values, implying that in most cases the retrieval effectiveness of Sim_AHC is significantly
	different from that of SHCoClust. In some cases, (absolute) T values are smaller than
	critical values. As we can see, for MED, CISI and CACM datasets, red T values often
	appear at single link, median and centroid methods. However, for AP and WSJ (using
	Gaussian) datasets, red T values occur in complete link, average link, McQuitty and
	Ward methods.

Table 5 .

 5 8: T values of T-tests with H 0 : µ 0 = µ 1 and H 1 : µ 0 ̸ = µ 1 at α = 95%. µ 0 indicates the mean of optimal E values obtained in Sim_AHC, µ 1 for SHCoClust. Values highlighted in red are smaller than critical value.5.5.2 On Computing EfficiencyIn Section 3.3.2.2 and Section 4.3.4, we provide some discussion on the time complexity of Sim_AHC and of SHCoClust. Given a document-matrix A of shape n × m, without sparsification, the time complexity of Sim_AHC is O(n 3 ), and O(min(nm 2 , mn 2 ) + (n + m) 3 ) for SHCoClust. As shown previously, better computing efficiency can be achieved by sparsifying similarity matrix S, resulting in M non-zero values being stored in memory, M ≪ n 2 . This strategy reduces time complexity of Sim_AHC to O(nM ), and of SHCoClust to O(min(nm 2 , mn 2 ) + (n + m)M ). Comparing the two clustering frameworks, SHCoClust is more costly than Sim_AHC no matter sparsifying S or not, because it requires to apply spectral embedding and to perform clustering on a similarity matrix of shape (n + m) × (n + m). However, it allows to retrieve both documents and terms, which Sim_AHC cannot do.

  The core of Spark is the RDDs (Resilient Distributed Datasets). Any input read from a distributed file system can be cached as a set of RDDs across a cluster of nodes. It is important to note that RDDs are immutable and are not materialized immediately. There are two types of operations for RDDs, transformation and action. A transformation function transforms RDDs from one type to another, constructing a lineage of RDDs.An action function, on the other hand, executes all the transformation functions of the lineage and returns an output, which can stored in hard disk or displayed. Both types of functions operate on many data items (contained in RDDs) concurrently.

	6.1 Introduction
	Previously, we demonstrate that the computing efficiency of Sim_AHC and SHCoClust
	can be improved by sparsifying their similarity matrix. This strategy allows Sim_AHC
	and SHCoClust to address relatively larger datasets with limited computing resources on
	a single machine, where calculation is processed sequentially. Introduced in Section 2.1.2,
	distributed and parallel computing are capable to take advantage of hardware to improve
	efficiency by assigning computing tasks among a set of processors. These processors can
	be either located in one machine (parallel), or connected via a local or remote network
	(distributed). For each type of computing, there exists a number of softwares.
	We improve the efficiency of Sim_AHC and SHCoClust from an algorithmic point of
	view. Interested in further enhancing their efficiency, we choose distributed computing
	to accelerate the speed of calculation in case of processing larger input. Compared parallel
	computing, distributed computing is capable to handle issues such as data replication,
	machine failure, job scheduling and recovery. These functions save us time from many
	extra problems in implementing our programs. This is the main reason that we choose
	distributed computing.
	Among many distributed computing softwares, we choose Apache Spark. Mentioned in
	Section 2.1.2.2, Apache Spark is an in-memory architecture, which allows intermediate
	datasets to be cached in distributed memory of a cluster of nodes. This characteristic
	prevents the intermediate datasets from being stored on hard disk. Unlike MapReduce

platform, where a lot of I/O overhead is produced due to reading and writing from and to hard disk, Spark is more efficient because it avoids this overhead. For some iterative algorithm, it is advantageous.

  Unlike this procedure, where computation is processed sequentially and a similarity in S can be assigned with a new value, distributed Sim_AHC needs to cache S as a set of RDDs in the distributed memory, and applies functions to update S while respecting that RDDs are immutable. The characteristic of RDDs determines that we

	6.2.1 Computing Procedure
	cannot update S by assigning a new value to a similarity in it as in a conventional
	program. But what we can do is to create a set of new RDDs and delete a set of
	old RDDs. Based on this rule, we design a computing procedure in Figure 6.1. Given
	a collection of documents, we firstly preprocess it into a document-term matrix, then

Illustrated in Algorithm 7, having pairwise similarity matrix S, the computing procedure of Sim_AHC is composed of three steps in each iteration: firstly, searching for the pair of closest clusters; secondly, merge this pair into one cluster; and lastly, update similarity matrix S.

we store this matrix as a set of document vectors on HDFS. The program of distributed Sim_AHC reads from HDFS, loads these vectors and cache them as a set of RDDs in the distributed memory. After a number of iterations, the program outputs a dendrogram.

  table, the j-k table and the ¬i-¬j table. C k denotes any other remaining (document) cluster. This splitting process is achieved by three filtering functions. Recall that filter() is an RDD transformation function. The three tables are of MapPartitionRDD, whose items are cached across the cluster of nodes. 4. It is worth mentioning that entries in i-k table and in j-k table share the same set of indexes C k in their keys. In this step, our program firstly aligns index C k between the two tables, then applies Equation 3.11 and Equation 3.12 on the aligned pairs to update both pairwise similarities and self similarities. Depending a clustering method, the similarities are computed accordingly. The output of this step is the ij-k table. It is a UnionRDD because a union function is applied upon i-k table and j-k table.5. In the last step, our program combines ij-k table and ¬i-¬j table to form a "new pairwise similarity table", which is used in the next iteration. This combination is also achieved by an union function.In order to obtain a complete dendrogram, our program theoretically requires n -1 iterations. In each iteration, it runs through Step 2-5. The program is available at https://github.com/xywang/spark_ahc. Note that all tables mentioned above are encapsulated as RDDs.Our experiments are run on a cluster of five Linux machines, which are connected via a local network. We name this cluster as "minicluster". Each machine in minicluster has 8G RAM and 4 cores. Hadoop 2.6 and Spark 2.0.0 are installed and configured on every machine. SSH communication is established. Spark standalone cluster mode is deployed, with one machine executing the driver program while the others performing executor processes. Our program is implemented in Python 2.7. In Spark, the Python API (Application Programming Interface) is often referred as PySpark 1 . PyCharm IDE

	(Integrated Development Environment) 4.5.1 is installed and configured on minicluster
	to facilitate programming.
	6.2.2 Experiments
	6.2.2.1 Settings and Configurations

  .1 lists several commonly used properties in our Spark applications. These properties can be set in Spark configuration file, or in user program, or through spark-submit command.

	Property Default Meaning
	spark.app.name (none) The application name.
	spark.driver.cores	1	Number of cores to use for the driver process.
	spark.driver.memory	1G	Amount of memory to use for the driver process.
	spark.executor.memory	1G	Amount of memory to use per executor process.
	spark.executor.cores	all	Number of cores to use on each executor.

Table 6 .

 6

1: Commonly used Spark application properties 6.2.2.2 Spark Web UI Once launching a Spark application, SparkContext is initialized in driver program, the lineage of RDDs starts to grow by transformation functions. As these functions are not materialized immediately, it is difficult to debug a Spark program. One practical way is to observe running process from Spark web UI (User Interface). Every SparkContext launches a web UI, which is accessible by the address http://<driver-node-ip>:4040 in a web browser. Spark web UI displays useful information of a Spark application. This includes (1) a list of scheduler jobs, stages and tasks, (2) information of running executors,

  1, we find out that the problem is caused by the union() function, which is applied in Step 4 and in Step 5. In PySpark, when applying the union() function, such asRDD 3 ← RDD 1 .union(RDD 2), the number of partitions of the produced RDDs is the sum of the number of partitions of the input RDDs. For example, if RDD 1 and RDD 2 each has m partitions, RDD 3 eventually has 2m partitions. Back to our experiment, the usage of union() inStep 4 and Step 5 results in tripled number of partitions in iteration, slowing down the process.

There are two ways to control the number of partitions, one is by repartition() function, the other one is by coalesce() function. Once passing a desired number of partitions "numPartitions", both functions are able to change the number of partitions of an input RDDs to numPartitions. The difference is that repartition() function requires to reshuffle the data in the RDDs so that it can create more or fewer partitions and balance data across the new set of partitions. This process always shuffles all data over the network

5

. As to coalesce() function, it only decreases the number of partitions to numPartitions. It avoids shuffling data, and thus is more efficient when we only want to have fewer partitions.

  RDDs' lineage grows larger and larger as the number of iterations increases.Concretely, in one iteration, the RDDs of the pairwise similarity table (Figure6.1) are the parent of the RDDs of i-k table, j-k table and ¬i-¬j table. And the child RDDs of i-k table and j-k table, the ij-k table unions with the ¬i-¬j table to produce a new pairwise similarity table, which is used in the next iteration. As we can see, in this process, the lineage of RDDs grows with child RDDs being usedas parent RDDs between two consecutive iterations. This cycle makes the entire RDDs' lineage to grow till the end of the program. It is possible to execute on such a long lineage if the input dataset is relatively small, for example, the program works on Iris dataset. However, when the dataset gets larger, like 2cir_10xe3.txt, the lineage becomes too large to fit in the memory before the program reaches its end. In every 31 st iteration, checkpointed RDDs are reconstructed from checkpoint directory and used in the next 29 iterations. Though reconstructing RDDs from checkpoint directory consumes some time, overall processing proceeds correctly in our experiment.

5

http://spark.apache.org/docs/latest/rdd-programming-guide.html that Spark is a in-memory distributed platform, it allows RDDs to be cached in the distributed memory of a cluster of nodes. The function persist() is done to do so. Besides, unwanted RDDs can be uncached to free distributed memory by unpersist() function. In our program, the input file is cached after it is read from HDFS. In order to cope the problem of lineage, the first solution that we come up with is to unpersist the RDDs of the pairwise similarity table after a number of iterations, then persist them again in a number of following iterations. This solution can be considered as a trade-off between efficiency and memory use. However, in practice, it does not improve the performance. After some trials, we find out that caching and unchaching RDDs only move them into and out of distributed memory, the growth of lineage is not affected.

Therefore we set up a checkpoint on the RDDs' lineage to cut it after a number of iterations. The checkpoint() function stores cached RDDs in the checkpoint directory on HDFS and all references of parent RDDs are removed. In our experiment that uses 2cir_10xe3 dataset, we checkpoint RDDs after every 30 iterations.

Table 6 . 3 :

 63 Experimented datasets10 https://catalog.ldc.upenn.edu/LDC93T3AFor each dataset, singular values obtained by the distributed implementation are firstly verified against those output by a conventional Python program. It is shown that the singular values obtained by the distributed and by the conventional programs are always identical. After this verification, we move to examine the performance in several scenarios, where the size of assigned executor memory and the number of total cores vary. Results of this experiment are listed in Table6.4. "ExeMem(Gb)" indicates the size of assigned memory (measured by gigabytes) in each executor, and "Num.TotCores" is the number of total cores assigned to the cluster. We configure minicluster to have five worker nodes, i.e., one machine hosts the driver program as well as a worker program, and the other four machines only host worker programs. "Time.SVD(s)" records the running time (measured in seconds) of performing SVD, and "Time.UI(s) records the total processing time (measured in seconds) from Spark UI.

	Dataset Size (Mb) Num.Docs Num.Terms
	START	5.8	3,893	6,812
	AP-1	26.3	10,458	1,564
	AP-2	53.1	20,845	1,551
	WSJ	534.2	173,252	1364
	AP	766.2	242,918	1540
	ZSDF	1759.9	638,884	1500

Table 6 . 4 :

 64 Performance of distributed spectral embedding using SMART, AP, WSJ and ZSDF datasets

  même efficacité de recherche en utilisant beaucoup moins de mémoire et de temps pour effectuer le calcul. En comparant les résultats de la test du Sim_AHC et de la test du SHCoClust à l'aide d'un test de Student, nous découvrons que Sim_AHC est plus efficace que SHCoClust lorsqu'il utilise des méthodes de lien simple, lien complet, lien moyen, McQuitty et Ward dans de petits ensembles de données. Cependant, SHCoClust est plus efficace que Sim_AHC en utilisant des méthodes de lien simple, lien moyen et centroïde dans des ensembles de données relativement plus grandes. Intéressés par effectuer le calcul pour des ensembles de données vastes, nous choisissons l'Apache Spark 1 pour implémenter Sim_AHC et SHCoClust. Le Spark est une plateforme du calcul distribué. Il utilise la capacité du calcul collective d'un groupe de noeuds pour traiter des ensembles de données vastes. En général, le Spark fonctionne sur un système de fichier distribué, qui est établi sur un groupe de machines. Après une initialisation, le Spark coupe des tâches du calcule et les assigne aux noeuds, qui ensuite effectuent leurs tâches simultanément. Le concept de base du Spark est les données distribuées résilientes (RDDs) [21]. Comme une abstraction grossier, une RDD est en fait un morceau de données qui est mit en mémoire-cache distribué. Le RDD est immuable et il y a deux groupes de fonctions qui peuvent traiter RDDs. Ces sont les fonctions de transformation et d'actions. Les fonctions de transformation permet aux RDDs de croître en une forme de lignée, et les fonctions d'actions coupe la lignée de RDDs, effectue le calcul et renvoie les résultats. La caractéristique de RDD demande une façon différente que les programme conventionnels en terme d'implémentation. Bien que le Spark gère automatiquement la planification des travaux, la réplication des données et la communication réseau parmi les noeuds, il existe encore de nombreux paramètres à régler afin d'optimiser l'efficacité et l'évolutivité du calcul, par exemple, le nombre de morceaux des RDDs, le nombre de tâches à assigner et la taille de mémoirecache à utiliser dans chaque noeud. Il est aussi important de contrôler la longueur de la lingée des RDDs. Nous fournissons deux implémentations distribuées, le Sim_AHC distribué et la méthode de spectral-SVD distribuée. Pour chaque implémentation, nous illustrons la procédure et la performance du calcul. Nous trouvons que l'implémentation du Sim_AHC distribué ne fonctionne pas aussi bien que prévu. Après avoir essayé des solutions différentes, nous concluons que le Spark est peut-être pas une plate-forme du calcul appropriée pour un algorithme comme Sim_AHC, dans lequel une itération dépend l'itération précédente. Le Spark est plutôt un bon choix pour les algorithmes qui fonctionnent aux itérations indépendantes par lot. Dans cette thèse, nous partageons nos connaissances savantes de nos expériences, en croyant qu'elles seraient utiles pour d'autres chercheurs, qui s'intéressent à la mise en oeuvre de la méthode hiérarchique à l'aide de Spark. Pour l'implémentation distribuée de SHCoClust, nous proposons une façon distribuée de réaliser la méthode de spectral-SVD. Dans nos expériences, nous utilisons des données de tailles différentes pour examiner la caractéristiques de l'échelle.Mots-clés : classification ascendante hiérarchique, co-clustering, recherche d'informations, l'hypothèse de cluster, calcul distribué.

https://yippy.com/

http://search.carrot2.org/stable/search

https://www.thalesgroup.com/fr/worldwide/big-data/news/request-programme-launched

spark.apache.org/

https://spark.apache.org/

https://spark.apache.org/docs/latest/cluster-overview.html

https://spark.apache.org/docs/latest/cluster-overview.html

https://spark.apache.org/docs/latest/mllib-guide.html

https://spark.apache.org/docs/latest/ml-guide.html

https://spark.apache.org/docs/latest/sql-programming-guide.html

https://hive.apache.org/

https://www.tutorialspoint.com/spark_sql/spark_sql_quick_guide.htm

https://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-common/ FileSystemShell.html

The geometric multiplicity of an eigenvalue is the number of linearly independent eigenvectors associated with it.

A textual collection of 1,400 short abstracts of aeronautical system articles.

http://ir.dcs.gla.ac.uk/resources/test_collections/

https://yippy.com/

http://search.carrot2.org/stable/search

Distribution 1.0, ApteMod version.

We use the same dataset as in http://qwone.com/~jason/20Newsgroups/.

A Python script for preprocessing is available at https://github.com/xywang/text_ preprocessing/blob/master/preprocessing.py

Note that this default setting is used in popular SVM packages. In this case γ is very low, the Gaussian kernel provides values close to 1 and data points in a pair is close to each other.

Similarly to the general AHC algorithm based on a dissimilarity matrix where M = N (N -1).

This default setting is used in popular SVM packages. Besides, when γ is low, Gaussian kernel provides close-to-one values and higher similarities between pairs of points.

These methods are: the single link, the complete link, the average link and the Ward method

It contains the SMART datasets (MED, CISI and CRAN). We do not use CRAN (or CRANFIELD) dataset in the cluster hypothesis tests, because query indexes in its query file do not match those in its relevance judgment file. http://ir.dcs.gla.ac.uk/resources/test_collections/

https://catalog.ldc.upenn.edu/LDC93T3A

https://www.scala-lang.org/

https://www.py4j.org/

Acknowledgments

REQUEST project, which financed my PhD study.

A wider range of methods are shown to be performing. However, the difference of the averaged optimal E values obtained by seven methods is in fact quite small. In the second experiment, we obtain a similar conclusion, i.e., sparsifying similarity matrix results in better computing efficiency without harming retrieval effectiveness. This is probably caused by the fact that most optimal clusters are located near the leaf nodes of an output dendrogram. Sparsification disconnects clusters that have small similarities, and these clusters are likely near the root. Therefore, optimal clusters are not affected by sparsifying the similarity matrix, and retrieval effectiveness keeps invariant as threshold Appendix A

Publication List

International Conferences sur des matrices de produits scalaires est davantage propice à la définition de méthodes de seuillage de mesures de proximités. Nous proposons alors de pré-traiter la matrice de proximités de façon à la rendre éparse afin de permettre un meilleur passage à l'échelle de ces techniques de classification.