Nombreuses sont les personnes qui ont contribué de près ou de loin à la réussite de cette thèse. Tout d'abord, un grand merci à mon directeur de thèse Pr. Mohamed Nadif pour son soutien, ses orientations et son implication active. J'ai beaucoup appris de lui et profité de sa grande compétence en modélisation et apprentissage statistique. Le Pr. Nadif a toujours montré une grande confiance en mes capacités et m'a permis de travailler de manière autonome, tout en fournissant des conseils précieux et en me poussant à explorer plus en profondeur certaines questions de recherche. Enfin, ses qualités humaines, sa rigueur scientifique, sa disponibilité et ses encouragements constants sont les facteurs clés qui m'ont aidé à mûrir en tant que chercheur et mener à terme ce projet de thèse.

Je remercie aussi le Dr. Nicoleta Rogovschi pour sa participation en tant que co-encadrant. Elle a montré une grande foie en moi et m'a encouragé tout au long de cette thèse. Ses conseils sur des questions de rédaction et de présentation m'ont poussé à apprendre d'autres aspects d'être un bon chercheur.

Je souhaite aussi exprimer mon respect et ma gratitude au Dr. François Role avec qui j'ai eu l'occasion de collaborer et d'avoir beaucoup d'échanges fructueux sur des aspects techniques, de fouille de données et bien d'autres. J'ai grandement apprécié ses qualités humaines et scientifiques.

J'ai la chance de bénéficier d'un jury de thèse de grande qualité, en particulier je remercie les rapporteurs Pr. Christophe Ambroise et Pr. Fabrice Rossi pour leurs lectures approfondies de mon manuscrit ainsi que leurs remarques et recommandations à la fois pertinentes et constructives. Je voudrais aussi remercier les autres membres de mon jury, Pr. Josiane Mothe et Pr. Talel Abdessalem, de m'avoir fait l'honneur d'accepter d'examiner mon travail.

Mon expérience en tant que doctorant ne serait sans doute pas aussi gratifiante sans mes amis et collègues de bureau, Melissa Ailem, Charlotte Laclau, Kais Allab et Adel Benaissa, que je tiens à remercier pour leurs sympathie, gentillesse et générosité. D'un côté un peu plus personnel j'aimerais remercier un certain nombre de personnes qui m'ont toujours encouragé et contribué de manière indirecte au bon déroulement de cette thèse, à savoir mes cousins Lounes et Lyes, ma tante Djamila, mes deux frères Yacine et vi Tarik, mes oncles Rachid et Madjid, mes amis Younès et Karim et mes cousins Faredj et Mourad.

Enfin, il n'y a pas de mots pour exprimer ma reconnaissance à ma mère Fatiha, mon père Hacène, mon oncle Lakhdar et ma grand-mère Khadija pour leurs soutiens et encouragements indéfectibles ainsi que tous les sacrifices qu'ils ont fait pour mon épanouissement sur tous les plans de la vie.

Résumé

La classification automatique, qui consiste à regrouper des objets similaires au sein de groupes, également appelés classes ou clusters, est sans aucun doute l'une des méthodes d'apprentissage non-supervisé les plus utiles dans le contexte du Big Data. En effet, avec l'expansion des volumes de données disponibles, notamment sur le web, la classification ne cesse de gagner en importance dans le domaine de la science des données pour la réalisation de différentes tâches, telles que le résumé automatique, la réduction de dimension, la visualisation, la détection d'anomalies, l'accélération des moteurs de recherche, l'organisation d'énormes ensembles de données, etc. De nombreuses méthodes de classification ont été développées à ce jour, ces dernières sont cependant fortement mises en difficulté par les caractéristiques complexes des ensembles de données que l'on rencontre dans certains domaines d'actualité tel que le Filtrage Collaboratif (FC) et de la fouille de textes. Ces données, souvent représentées sous forme de matrices, sont de très grande dimension (des milliers de variables) et extrêmement creuses (ou sparses, avec plus de 95% de zéros).

En plus d'être de grande dimension et sparse, les données rencontrées dans les domaines mentionnés ci-dessus sont également de nature directionnelles. En effet, plusieurs études antérieures ont démontré empiriquement que les mesures directionnelles, telle que la similarité cosinus, sont supérieurs à d'autres mesures, telle que la distance Euclidiennes, pour la classification des documents textuels ou pour mesurer les similitudes entre les utilisateurs/items dans le FC. Cela suggère que, dans un tel contexte, c'est la direction d'un vecteur de données (e.g., représentant un document texte) qui est pertinente, et non pas sa longueur. Il est intéressant de noter que la similarité cosinus est exactement le produit scalaire entre des vecteurs unitaires (de norme 1). Ainsi, d'un point de vue probabiliste l'utilisation de la similarité cosinus revient à supposer que les données sont directionnelles et réparties sur la surface d'une hypersphère unité.

En dépit des nombreuses preuves empiriques suggérant que certains ensembles de données sparses et de grande dimension sont mieux modélisés sur une hypersphère unité, la plupart des modèles existants dans le contexte de la fouille de textes et du FC s'appuient sur des hypothèses populaires : distributions Gaussiennes ou Multinomiales, qui sont malheureusement inadéquates pour des données directionnelles.

x Dans cette thèse, nous nous focalisons sur deux challenges d'actualité, à savoir la classification des documents textuels et la recommandation d'items, qui ne cesse d'attirer l'attention dans les domaines de la fouille de textes et celui du filtrage collaborative, respectivement. Afin de répondre aux limitations ci-dessus, nous proposons une série de nouveaux modèles et algorithmes qui s'appuient sur la distribution de von Mises-Fisher (vMF) qui est plus appropriée aux données directionnelles distribuées sur une hypersphère unité. Les contributions majeures de cette thèse s'articulent autour de quatre axes principaux.

Dans un premier temps nous proposons une nouvelle variante incrémentale de l'algorithme k-means sphérique, qui s'appuyant sur la similarité cosinus permet de gérer efficacement les changements fréquents dans les données du filtrage collaboratif, à savoir l'apparition de nouveaux utilisateurs, items, notes et mise à jour de notes existantes. Les résultats expérimentaux confirment l'efficacité et la rapidité de notre approche dans les deux situations suivantes: statique où les données restent inchangées, et dynamique où de nouvelles données sont intégrées au fur et à mesure de leurs disponibilités.

Dans un second temps nous nous intéressons à l'exploitation des réseaux sociaux dans les systèmes de filtrage collaboratif. Avec l'avènement des réseaux sociaux les approches de FC sociale se sont avérées très efficaces pour atténuer les problèmes liés à la sparsité des données, ce qui permet d'améliorer la qualité des recommandations de manière notable dans la plus part des cas. D'une part, nous avons les avantages de la modélisation des données sur une hypersphère unité, et d'autre part, nous avons les avantages de l'intégration des informations des réseaux sociaux dans le FC. L'exploitation simultanée des caractéristiques directionnelles des données du FC et les informations provenant des réseaux sociaux permettra d'améliorer les recommandations de façon significative. Pour ce faire, nous développons une nouvelle approche basée sur un mélange de distributions de vMF tout en tenant compte des interactions sociales entre les utilisateurs. Les résultats empiriques sur divers ensembles de données réels suggèrent que, pour formuler des recommandations de bonne qualité, il est non seulement nécessaire de prendre en compte la nature directionnelle des données du FC mais aussi les interactions sociales entre les utilisateurs.

Dans un troisièmes temps, nous nous intéressons à la classification croisée qui consiste, cette fois-ci, à partitionner simultanément les deux dimensions d'une matrice de données afin de faire ressortir une structure en blocs latents dans les données initiales. Cette dernière s'avère être plus bénéfique que la classification simple pour le traitement de matrices creuses à grande dimension, et cela même si l'utilisateur est intéressé uniquement par le partitionnement sur une seule dimension. Les approches de classification croisées existantes s'appuient, cependant, sur des hypothèses qui sont inappropriées pour des données projetées sur une hypersphère unité. Afin de surmonter cette limite, nous proposons un nouveau modèle de mélange pour la classification croisée qui s'appuie sur un mélange de distributions vMF. Ce modèle qui est parcimonieux a l'avantage d'exploiter simultanément les bénéfices de la classification croisée et de la modélisation des données sur une hypersphère unité. Nous étudions les connexions théoriques du modèle proposé avec d'autres modèles, et nous dérivons une série de nouveaux algorithmes qui s'avèrent évolutifs et efficaces pour la classification croisée des matrices documents-termes qui ont la particularité d'être très creuses et de grande dimension.

La dernière contribution de cette thèse consiste à contrer les problèmes liés à l'obtention de classes vides ou très déséquilibrées. En effet, du fait de la grande dimensionnalité et de la sparsité caractérisant les données, les méthodes de classification croisée, comme les méthodes de classification simple, ont tendance à générer des classes vides ou très déséquilibrées, en particulier lorsque le nombre de classes souhaité est grand. Afin de surmonter cette difficulté, nous développons une nouvelle approche de classification croisée directionnelle qui intègre avec succès un mécanisme de conscience. Ce dernier permet de pénaliser les clusters en fonction de leurs tailles. L'algorithme proposé est évolutif et garantit de faire croître, à chaque itération, de façon monotone un critère de type k-means sphérique en alternant la classification des lignes et des colonnes. En outre, sur des données réelles, les résultats empiriques obtenus appuient fortement l'efficacité de l'approche proposée. to the well known Zachary's karate club network; friendships between 34 members of a karate club at a US university in the 1970s [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF]. .

Introduction

Clustering aims to organize a set of objects into homogeneous groups, such that objects in the same cluster (or group) are more "similar" to each other than to objects in different clusters [START_REF] Xu | Survey of clustering algorithms[END_REF][START_REF] Everitt | Cluster Analysis[END_REF][START_REF] Aggarwal | Data clustering: algorithms and applications[END_REF]. In machine learning, where data is often represented by a matrix where the rows denote objects (instances, individuals), and the columns denote features (attributes, variables), clustering is a powerful unsupervised learning technique that aims to "summarize" data-seeks to find a reduced representation of data by grouping together either similar objects or variables-to ease their exploration and interpretation. More precisely, clustering seeks to discover a hidden structure of the data that can be exploited to represent the data in a compressed fashion, that reflects faithfully the original data. Due to its practical importance, clustering has received a lot of attention in various communities such as machine learning, data mining and information retrieval. This led to the development of a wide variety of clustering methods, regarding the context and types of data, i.e., binary, categorical, continuous or count data [START_REF] Aggarwal | Data clustering: algorithms and applications[END_REF]. Despite the extensive efforts of many research communities, clustering approaches are still seriously challenged by the characteristics-high dimensionality and sparsity-of certain data sets arising in some current areas of interest such as text mining and collaborative filtering. In fact, when dealing with such data, most of traditional clustering algorithms suffer from poor performances in terms of both scalability and quality of clustering. In this thesis, we propose a suite of novel algorithms that are based on rigorous probabilistic assumptions, and which are able to handle effectively and efficiently high dimensional sparse data sets. In particular, we focus on the two areas of text mining and collaborative filtering, with the aim to solve the challenging tasks of document clustering and item recommendation, using high dimensional sparse document-term and user-item matrices, respectively.

I.1. Motivation and Contribution

I.1.1. Why von Mises-Fisher based models?

Several data sets arising in some current areas of interest, such as text mining, collaborative filtering and bioinformatics, are high dimensional and extremely sparse; usually theses data sets consist of more than 1000 features and 95% of zero entries. Analysing such data is a major challenge. Indeed, most of existing clustering methods suffer from poor performances in this context. Apart from being high dimensional and sparse, the data sets arising in the above domains are also directional in nature [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF]Banerjee et al., 2005b).

In text mining, where data arises in the form of high dimensional sparse document-term matrices, clustering text documents is of great interest for several practical reasons: automatic summarization and organization of documents, efficient browsing and navigation of huge text corpora, dimensionality reduction, visualization, speed up search engines, etc. In this domain, it is well known that normalizing the data vectors so that they lie on a unit-hypersphere-L 2 normalization-allows us to remove the biases induced by the lengths of documents and reach better clustering performances. Furthermore, it has been found that von Mises-Fisher (vMF) based clustering algorithms, including the spherical k-means algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], are superior to several other clustering methods which are based on popular assumptions such as Gaussian, Multinomial or Bernoulli, see for instance [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF][START_REF] Gopal | Von mises-fisher clustering models[END_REF]. Recall that the vMF distribution is a continuous probability distribution, from directional statistics [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF], that arises naturally for directional data lying on the surface of a unit-hypersphere. In particular, the vMF distribution focuses on the directions of objects-data vectors-and measures the distance between them using the cosine similarity, which turns out to be a more effective measure for clustering text documents [START_REF] Strehl | Impact of similarity measures on web-page clustering[END_REF]. From a probabilistic perspective, the success of the L 2 normalization and vMF-based models, for clustering text documents, constitutes a strong empirical evidence that text data has intrinsic directional characteristics that match well with the modeling assumption of the vMF distribution.

Collaborative filtering (CF) is a widely used recommendation approach, it consists in making recommendations for users according to the preferences of other similar users. Over the last decade, CF systems have become central in modern web applications such as Amazon, Netflix, Youtube, Flixster, etc. In fact, CF makes it possible to filter the huge amount of information generated in the above applications so as to guide the users towards items that might interest them. Collaborative Filtering is another domain where it is better to model data as directional. In fact, let us consider the cosine similarity and Pearson Correlation Coefficient (PCC), two widely used measures in this domain. The above two, or their variants, have been found to be more effective and efficient than Euclidean distortions to assess similarities between users or items [START_REF] Sarwar | Item-based collaborative filtering recommendation algorithms[END_REF][START_REF] Liu | A new user similarity model to improve the accuracy of collaborative filtering[END_REF]. Observe that both measures focus on the directions of data vectors, i.e., the similarity between two objects-users or items-is measured relative to the angle between them. The success of such measures in CF suggests that the direction of a user (resp., item) preference-vector is relevant, not its magnitude.

It is worth noting that both the above measures are exactly the scalar product between objects lying on the surface of a unit-hypersphere, i.e., objects of unit length (L 2 norm). This is straightforward for the cosine similarity, now let us look at the PCC between two users, represented by vectors x and y in R d , given by: PCC(x, y) = (x -x) ⊤ (y -ȳ) ∥x -x∥∥y -ȳ∥ , where x and ȳ are two vectors of the appropriate dimensions, such that x1 = • • • = xd = ∑ j x j /d and ȳ1 = • • • = ȳd = ∑ j y j /d. Let x ′ = x-x ∥x-x∥ and y ′ = y-ȳ ∥y-ȳ∥ , then the PCC between x and y is exactly the scalar product (cosine similarity) between the two unit-length vectors x ′ and y ′ . Hence, using the cosine and PCC measures is equivalent to assume that CF data is directional and distributed on the surface of a unit-hypersphere. The success of such measures constitutes empirical evidence that CF data sets possess intrinsic directional properties [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF] that should be taken into account when modeling such data.

Despite the substantial empirical evidence that some high dimensional sparse data sets are better modeled as directional 1 data, most existing models in the context of text document clustering and CF are based on popular assumptions such as Gaussian or Multinomial, which are inadequate for directional data destributed on the surface of a unit-hypersphere.

I.1.2. Contributions

This thesis deals with a suite of new models and algorithms tailored for directional data distributed on the surface of a unit-hypersphere. The proposed models are scalable and able to handle effectively certain high dimensional sparse data sets such as text and CF data. The major contributions of this thesis are structured around four main topics: may offer a good recommendation accuracy, they are computationally prohibitive. Scalable approaches are, therefore, needed if CF techniques are to be usable in realistic scenarios where data evolves rapidly. This thesis presents a scalable incremental variant of the spherical k-means algorithm, that is able to handle effectively the frequent changes in CF data such as submission of new ratings, update of existing ratings, appearance of new users and items.

Directional Clustering with Social-Network information

Recently, several works have demonstrated that incorporating information from social networks, such as friendships and trust relationships, into tradition traditional CF enables to alleviate significantly the sparsity related issues such as the problem of cold start users, i.e., who expressed very few ratings. Social-based CF builds on the assumption that, for making good recommendations, not only the user's expressed preferences are important but also the user's social interactions. This is natural as people often turn to their friends for advice before choosing a movie, a book, a restaurant, etc. By capturing this real-life behaviour, social CF approaches make more realistic recommendations and, thereby, improve the performances of traditional methods noticeably in most cases. This thesis propose a novel social CF model in order to address the sparsity issue. By contrast to existing social CF models, which are based on popular assumptions such as Gaussian, the proposed one builds on the von Mises-Fisher assumption that turns out to be more adequate to model CF data. Extensive experiments, on several real-wold data sets, illustrate the advantages of our modeling assumption and suggest that not only the users' social interactions, but also the intrinsic directional characteristics of CF data should be taken into account so as to improve recommendations.

Co-clustering via a mixture of von Mises-Fisher distributions

In the context of high dimensionality and sparsity, co-clustering, or simultaneous clustering of rows and columns of data matrices, turns out to be more beneficial than traditional one-sided clustering even if we are interested in clustering along one dimension, only. Popular co-clustering assumptions such as Gaussian, Multinomial or Bernoulli are, however, inadequate for L 2 normalized data. In this thesis, we propose novel rigorous probabilistic model for co-clustering, which is suitable for directional data lying on the surface of a unit hypersphere. The proposed model successfully integrates a directional measure, namely the cosine similarity, into a co-clustering framework. Based on the proposed model we derived several new co-clustering algorithms that are very scalable and effective. Empirical results, on numerous simulated and real-world data sets, demonstrate the effectiveness of our model and algorithms for handling high dimensional sparse document-term matrices.

-Chapters 5 and 6 are devoted to new co-clustering approaches tailored for directional data distributed on the surface of a unit-hypersphere. More precisely, Chapter 5 presents a novel co-clustering model that builds on the von Mises-Fisher distribution and a suite of algorithms arising from this model, including soft, hard, stochastic and simulated annealing variants. While Chapter 6 presents a novel vMF-based co-clustering approach with some balancing constraints on the row and column cluster sizes. A property that could be of great interest in some situations as illustrated in Chapter 6.

I.3. Notations

Through this thesis, we will use the following notations (unless stated otherwise):

-Matrices are denoted with boldface uppercase letters, vectors with boldface lowercase letters and sets by script style uppercase letters. The L 2 norm is denoted by ∥.∥. The (d -1) dimensional unit sphere embedded in R d is denoted by S d-1 .

-Data is represented by a matrix X = (x i j ) of size n × d, x i j ∈ R, the i th row of this matrix is represented by a vector x i = (x i1 , . . . , x id ) ⊤ , where ⊤ denotes the transpose.

-The partition of the set of rows I into g clusters can be represented by a classification matrix Z of elements z ih in {0, 1} satisfying ∑ g h=1 z ih = 1. The notation z = (z 1 , . . . , z n ) ⊤ , where z i ∈ {1, . . . , g} represents the cluster label of i, will be also used. These notations are illustrated in Table 1.

-Similarly the notations W = (w jh ), w jh ∈ {0, 1} satisfying ∑ g h=1 w jh = 1, and w = (w 1 , . . . , w d ) ⊤ , where w j ∈ {1, . . . , g} represents the cluster label of j, will be used to represent the partition of the set of columns J , see Table 1.

-In the same way, the fuzzy classification matrix of I will be denoted by Z = (z ih )

where zih ∈ [0, 1], satisfying ∑ g h=1 zih = 1, for all i in I.

-The sums and the products relating to rows, columns, row clusters and column clusters will be subscripted respectively by the letters i, j and h, without indicating the limits of variation which will be implicit. So, the sums ∑ i , ∑ j and ∑ h stands respectively for

∑ n i=1 , ∑ d j=1 and ∑ g h=1 .
Table 1 Data matrix X and associated row and column partitions indicated respectively by the representations z and Z, w and W, with g = 3.

columns (J ) z (n×1) Z = (z ih ) (n×g) 1 • • • j • • • d rows (I) x 1 x 11 • • • x 1 j • • • x 1d 1 1 0 0 . . . . . . . . . . . . x i x i1 • • • x i j • • • x id 3 0 0 1 . . . . . . . . . . . . x n x n1 • • • x n j • • • x nd 2 0 1 0 w (1×d) 3 • • • 1 • • • 2 W T = (w h j ) 0 • • • 1 • • • 0 0 • • • 0 • • • 1 (g × d) 1 • • • 0 • • • 0 Chapter 1

Clustering approaches

This chapter provides a brief survey of existing approaches to clustering. The objective here is not to provide a detailed description of all existing clustering methods, but rather to give an outline of the major approaches to clustering.

Hierarchical clustering

Given a set of objects to be clustered, hierarchical methods consist in constructing a sequence of partitions of the set varying from singletons to the whole set. A hierarchical clustering algorithm aims to transform a measure of dissimilarity between objects into a sequence of nested partitions, or an indexed hierarchy, such as the closest objects are grouped in the clusters with the smallest indexes. The obtained clustering hierarchy can be represented by a dendrogram as illustrated in Figure 1.1. The way in which the clustering hierarchy is built gives rise to two major hierarchical clustering categories.

Agglomerative hierarchical clustering. These approaches , also known as bottom up, first put each object in its own cluster, then start merging closest clusters until there is only a single cluster left. These methods require to choose a metric (e.g. euclidean distance), to compute dissimilarities between objects, and a linkage function (or criteria) to compute the dissimilarity between clusters based on the pairwise distances between objects. Several linkage criteria exist; the most popular are: single-linkage [START_REF] Sibson | Slink: an optimally efficient algorithm for the single-link cluster method[END_REF], complete-linkage [START_REF] Sorensen | A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on danish commons[END_REF], average-linkage [START_REF] Sokal | A statistical method for evaluating systematic relationships[END_REF]) and Ward's criterion [START_REF] Ward | Hierarchical grouping to optimize an objective function[END_REF]. For instance, the single-linkage defines the distance between two clusters as the pairwise distance between the two closest objects-one in each cluster. In addition to the above traditional methods several agglomerative clustering approaches have been proposed, they differ in their dissimilarity metric and linkage strategy, for more details the reader can refer to survey papers [START_REF] Xu | Survey of clustering algorithms[END_REF][START_REF] Murtagh | Algorithms for hierarchical clustering: an overview[END_REF] or the book of [START_REF] Everitt | Cluster Analysis[END_REF]. Divisive hierarchical clustering. As opposed to agglomerative methods, divisive, also denoted as top down, approaches assume that all objects belong to a big single cluster at the beginning, then split it repeatedly into smaller clusters, according to some chosen criterion, until each object form its own cluster or some stopping condition is reached. Example of divisive clustering approaches are MONA and DIANA described in [START_REF] Kaufman | Finding groups in data: an introduction to cluster analysis[END_REF], some other methods can be found in [START_REF] Everitt | Cluster Analysis[END_REF]. Divisive approaches are less common in practice, as opposed to agglomerative ones, due to their high computational cost.

The main advantages of hierarchical-based clustering approaches is that they do not require the number of clusters as an input, some methods, such as single-linkage, are able to discover clusters with non-convex shapes, and they can offer different clustering levels according to the position where the dendrogram is cut. These approaches exhibit, however, two major weaknesses: the first one is that they do not scale well to large datasets, the computational time complexity of most existing hierarchical methods is usually given respectively in O(n 3 ) and O(2 n ) for agglomerative and divisive approaches, where n is the number of objects. The complexity of some efficient agglomerative approaches is O(n 2 ). Hierarchical methods are therefore not suitable for large high dimensional datasets, such those encountered in text mining and collaborative filtering domains. The second, is that most existing methods perform the splitting or merging operations irreversibly and never undo what was done.

Density-based clustering

Density-based clustering methods assume that clusters are dense regions-of objects-in the feature space, and that clusters are separated by low dense regions. Objects in the latter regions are considered as noise. One of the most known density-based clustering approach is DBSCAN proposed in [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. In this approach, the density around a given object o i is defined as the number of objects within a distance ε around object o i . If the number of such objects if greater than a certain threshold minPts, called the density threshold, then o i is considered a core point, and o i is considered a border point otherwise. Based on the above notions, DBSCAN starts by randomly selecting an object o i , if it is a core point then a cluster is formed by connecting all density-reachable objects from o i , otherwise-o i is a border point-another object is selected. This process is repeated until all objects are processed, for more details the reader can refer to [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]. The DBSCAN method has the advantage of being able to discover clusters of arbitrary shapes. It is, however, highly sensitive to the settings of the density threshold minPts and radius ε parameters. In order to overcome the latter drawback, the same authors proposed OPTICS [START_REF] Ankerst | Optics: ordering points to identify the clustering structure[END_REF] a generalization of DBSCAN that do not require the parameters minPts and ε. In general density-based clustering methods are not very efficient for high dimensional data. Some approaches, such as grid-based methods [START_REF] Wang | Sting: A statistical information grid approach to spatial data mining[END_REF][START_REF] Hinneburg | An efficient approach to clustering in large multimedia databases with noise[END_REF], that can handle more efficiently high dimensional data have been proposed. Nevertheless, the latter may be less effective in some situations. For further details and more recent developments in density based-clustering, please refer to [START_REF] Kriegel | Density-based clustering[END_REF].

Graph-based clustering

This category of clustering methods works on data represented as a graph-from a graph theory point of view-that consists of a set of vertices (or nodes) and a set of edges between them-usually undirected; each edge connects a pair of nodes. Given such a graph structure, the aim of graph-based clustering is to find clusters of nodes, in such way that nodes within a cluster are more connected to each other than to those in other clusters, an illustration is given in figure 1.2. In other words, graph clustering seeks a partition of a graph into k clusters in such way that there will be many edges within each cluster and only few edges between clusters. A large class of graph clustering methods consists in solving graph cut problems; may be the simplest and one of the most popular is the minimum cut problem. It seeks to find a partition of the nodes in a graph by minimizing the sum of weights of the edges between clusters. Several variants of minimum cut have been proposed, among which

Partitional clustering

The aim of partitional clustering is to discover a hidden partition of a set of objects into g disjoint clusters, i.e., with non-hierarchical structure, in such a way that objects within a cluster are more "similar" to each other than to those in other clusters. Partitional approaches are widely used in practice due to their simplicity and scalability.

Centroid-based approaches

Centroid-based clustering represents a large class of partitional clustering methods. In this approach each cluster is represented by a centroid (or prototype) vector-which is not necessarily in the set of objects-and the aim is to find a partition of the objects, into g clusters, that optimizes some criterion, usually the deviation of each object from its cluster centroid. A trivial way to find such an optimal partition is to enumerate all possible partitions. As the latter is infeasible in practice, centroid-based approaches rely on optimization procedures which guarantee only a locally optimal solution. The choice of the cluster representativescentroids-and the criterion to optimize gives rise to a large number of centroid-based clustering methods. Among which we can mention the well known k-means algorithm.

The k-means algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF][START_REF] Bock | Clustering methods: A history of k-means algorithms[END_REF] is the most popular partitional clustering method, it seeks to find a partition of the objects into g clusters in such a way that the sum of squared euclidean distances, between each object and its cluster centroid, is minimized. Formally, k-means aims to minimize the following objective function

C(µ, z) = n ∑ i=1 g ∑ h=1 z ih ∥x i -µ h ∥ 2 .
(1.1)

where x i ∈ R d denote the ith object, µ h ∈ R d is the centroid of cluster h, z ih = 1 if the ith object belongs to cluster h and z ih = 0, otherwise. In order to minimize (1.1) the k-means algorithm involves the following steps:

1. Initialization: sample at random g initial centroids from the set of objects.

2. Optimization: alternate the following two steps until convergence.

(a) Assignement: assign each object to the closest centroid cluster, according to the euclidean distance.

(b) Update: compute the new centroids minimizing (1.1).

Several variants of the k-means algorithm have been developed, we can cite the k-medoids algorithm [START_REF] Kaufman | Clustering by means of medoids[END_REF] that constraints the centroids to be members of the set of objects. Both k-means and k-medoids are special cases of a more general centroid-based clustering approach known as méthode des nuées dynamiques [START_REF] Diday | Une nouvelle méthode en classification automatique et reconnaissance des formes la méthode des nuées dynamiques[END_REF]. The latter makes it possible to have centroids of various forms, not necessarily vectors in R d as in k-means. A more recent generalization of the k-means principle to any Bregman divergence-from which the euclidean distance arises as a special case-has been proposed in (Banerjee et al., 2005b).

Model-based approaches

Mixture model is undoubtedly a very powerful approach to clustering. It offers considerable flexibility, it is able to model different types of data-continuous, contingency, binary, etc.and uncover various specific cluster structures. Furthermore, it allows us to make precise assumptions and understand the theoretical foundation behind some clustering methods. In fact, several partitioning clustering approaches arise as special cases from mixture modelbased approaches. For instance, the k-means algorithm presented in the previous section can be derived from a mixture of Gaussian distributions, under some restrictive constraints. Intuitively, model-based clustering assumes that data is generated according to an underlying mixture of g probability distributions, usually from the same family. Objects within a cluster are assumed to be generated from the same distribution, that is each cluster is characterised by a probability distribution-called a component-with some specific parameters. The probability density function of such a mixture takes the following form:

f (X|Θ) = n ∏ i=1 g ∑ h=1 α h ϕ(x i |θ h ). (1.2)
where X is a n × d data matrix, its ith row (object) is denoted by x i . The parameters of the mixture are Θ = {α 1 , . . . , α g , θ }, parameter α h denotes the proportion of objects generated from component h such that ∑ g h=1 α h = 1, and ϕ(x i |θ h ) denotes a density/mass function of component h with some specific parameters θ h . For instance, in the case of a mixture of Gaussian distributions the set of parameters for each component is θ h = {µ h , Σ h }, where µ h ∈ R d , and Σ ∈ R d×d denote respectively the mean and covariance matrix parameters. Figure 1.3 uses the density obtained from a mixture of three Gaussian components in R 2 to illustrate this concept of a probability mixture.

The generative process assumed by the above mixture model is as follows

1. Choose a component h ∼ Multinomial(α 1 , . . . , α g ).
2. Choose a data point x i ∼ ϕ(x i |θ h ). The clustering in this context consists in reversing the above generative process and estimating the model parameters Θ, given the observed data X. To perform the latter task two main approaches are widely used in practice, namely the Maximum Likelihood (ML) and the Classification ML (CML) [START_REF] Scott | Clustering methods based on likelihood ratio criteria[END_REF][START_REF] Symons | Clustering criteria and multivariate normal mixtures[END_REF] approaches. The principle of the above two is to find the parameters Θ maximizing the likelihood of the observed data X. To this end, both techniques rely on the complete data log-likelihood, because it is difficult to work directly with the likelihood function, given as follows

L c (Θ; X, Z) = ∑ i ∑ h z ih log α h + ∑ i ∑ h z ih log ϕ(x i |θ h ).
(1.3)

As the latent variable Z is unknown in practice, the Expectation-Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] is usually used to find the ML estimates of the model parameters, while the Classification variant of EM (CEM) [START_REF] Celeux | A classification em algorithm for clustering and two stochastic versions[END_REF] is used under the CML approach. Regarding the clustering context, the main difference between the above two, is that the EM algorithm yields a soft clustering, i.e., each object has a probability of being generated from all clusters, and the clustering partition is obtained at the end-when the convergence is reached-by allocating each object to the most likely cluster that might have generated it, while the CEM algorithm simultaneously estimates the model parameters and the clustering partition, in an iterative scheme. Several modelbased clustering approaches exist we can mention, for instance, the Gaussian [START_REF] Banfield | Model-based gaussian and non-gaussian clustering[END_REF][START_REF] Celeux | Gaussian parsimonious clustering models[END_REF], Multinomial [START_REF] Jollois | Clustering large categorical data[END_REF][START_REF] Govaert | Clustering of contingency table and mixture model[END_REF], Bernoulli [START_REF] Govaert | Classification binaire et modeles[END_REF][START_REF] Govaert | Comparison of the mixture and the classification maximum likelihood in cluster analysis with binary data[END_REF][START_REF] Nadif | Clustering for binary data and mixture models-choice of the model[END_REF][START_REF] Mccallum | A comparison of event models for naive bayes text classification[END_REF] and von Mises-Fisher (Banerjee et al., 2005a;[START_REF] Gopal | Von mises-fisher clustering models[END_REF] mixture models for clustering respectively continuous, categorical, binary and directional data. For more details about model-based approaches to clustering the reader can refer to the books [START_REF] Mclachlan | Mixture models. inference and applications to clustering[END_REF][START_REF] Mclachlan | Finite mixture models[END_REF][START_REF] Govaert | Data Analysis[END_REF].

Conclusion

In this chapter, we outlined the major approaches to clustering and discussed their main strengths and weaknesses. The above list is not exhaustive and other clustering approaches exist. For instance, some methods consist in combining two or more of aforementioned approaches so as to reap the benefits of each of them. We can also mention non-negative matrix factorization based-approaches that have emerged recently [START_REF] Xu | Document clustering based on non-negative matrix factorization[END_REF]. In the rest of this thesis we focus on partitional clustering under the centroid-and model-based approaches that are closely related to each other. Our choice for these methods it largely motivated by their scalability, their strong theoretical foundations and their flexibility.

In the next chapter, we propose to tackle the problem of item recommendation by means of partitional clustering. While clustering has received very few attention in this context, as opposed to some other approaches such as matrix factorization and k nearest neighbors, we illustrate how clustering can benefit collaborative filtering systems, in terms of both scalability and effectiveness, when making proper modeling assumptions.

Chapter 2

Incremental directional clustering for a dynamic collaborative filtering system

This chapter describes a novel efficient incremental CF system based on a clustering approach. More precisely, we propose to model the user-item preferences as directional data distributed on the surface of a unit-hypersphere and develop a generalized sequential variant of the spherical k-means algorithm, which arises from a mixture of von Mises-Fihser distributions, so as to handle the frequent changes in CF filtering, i.e., submission of new ratings, update of existing ratings, appearance of new users and items. This gives rise to a very effective and scalable CF system, as illustrated through extensive experiments on several popular benchmark data sets.

Motivation

A collaborative filtering system (CF) aims at filtering huge amount of information, in order to guide users of web applications towards items that might interest them. Such a system, consists in recommending a set of personalized items for an active user, according to the preferences of other similar users. Existing methods, such as memory and Matrix Factorization (MF) approaches can achieve very good recommendation accuracy, unfortunately they are computationally very expensive. Applying such approaches to real-world applications in which users, items and ratings are frequently updated remains therefore a challenge.

In this work we aim to overcome the above limitation and develop a novel efficient incremental CF system. The proposed approach builds on the spherical k-means algorithm (Skmeans) [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], thereby in addition to handling frequent changes in CF data, our approach leverages the benefits of the cosine similarity which has been found to be superior to several other measures, such as Euclidean distortions, in collaborative filtering [START_REF] Liu | A new user similarity model to improve the accuracy of collaborative filtering[END_REF]. The Skmeans algorithm has strong theoretical basis and can be derived from a mixture of von Mises-Fisher distribution (Banerjee et al., 2005b). Furthermore, Skmeans has been successfully applied to text and gene-expression data whose characteristics are similar to those of CF.

Introduction

Nowadays the Web provides a very large amount of information, unfortunately users are unable to manage all this information correctly to reach the relevant information in a short time. The common solution to this problem is the use of recommender systems (RSs) [START_REF] Bobadilla | Recommender systems survey. Knowledge-Based Systems[END_REF][START_REF] Tang | Social recommendation: a review[END_REF] which automatically predict the preferences of users for some given items, in order to provide them with the useful recommendations. Many RSs have been proposed and adopted by real applications such as Amazon (books recommendation) [START_REF] Linden | com recommendations: Item-to-item collaborative filtering[END_REF], YouTube (videos recommendation) [START_REF] Davidson | The youtube video recommendation system[END_REF], Netflix (movies recommendation) [START_REF] Koren | The bellkor solution to the netflix grand prize[END_REF], Facebook (recommendation of: users, advertising, etc.). These RSs can be divided into three overall groups:

Content-based approaches. They attempt to predict how users will rate a set of items based on their personal information (country, interests, gender, occupation, etc.) and/or the features of the items (author, type, description, field, title, tag, etc.) that they liked in the past [START_REF] Pazzani | Content-based recommendation systems[END_REF]. For instance, if some users enjoyed science-fiction movies in the past, the system will suggest them other movies of the same genre. The major shortcoming of content-based approaches is that they suggest only the same kinds of items, and the sort of information mentioned above (user information and item features) is hard to collect.

Collaborative filtering (CF). It is the most often used approach in RSs. It consists in predicting items that an active user will enjoy, based on items that the people who are most similar to this user have enjoyed. Among CF systems two distinct types of approach are to be found: -Memory-based CF: these approaches are based on computing similarities. User-based collaborative filtering [START_REF] Bobadilla | Recommender systems survey. Knowledge-Based Systems[END_REF] looks for similarities between the active user u a and all other users and tries to predict the preference of u a for a set of new items, according to the preferences of the K most similar users to u a . Item-based collaborative filtering [START_REF] Sarwar | Item-based collaborative filtering recommendation algorithms[END_REF] [START_REF] Ungar | Clustering methods for collaborative filtering[END_REF], co-clustering [START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF][START_REF] Khoshneshin | Incremental collaborative filtering via evolutionary coclustering[END_REF], matrix factorization (MF) [START_REF] Sarwar | Application of dimensionality reduction in recommender system -a case study[END_REF][START_REF] Koren | The bellkor solution to the netflix grand prize[END_REF][START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF][START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF][START_REF] Hastie | Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares[END_REF], non-negative matrix factorization [START_REF] Zhang | Learning from incomplete ratings using non-negative matrix factorization[END_REF][START_REF] Sindhwani | A family of non-negative matrix factorizations for one-class collaborative filtering problems[END_REF][START_REF] Gu | Collaborative filtering: Weighted nonnegative matrix factorization incorporating user and item graphs[END_REF], mixtures models [START_REF] Marlin | Collaborative filtering and the missing at random assumption[END_REF][START_REF] Kim | Bayesian binomial mixture model for collaborative prediction with non-random missing data[END_REF] and transfer learning approach [START_REF] Li | Can movies and books collaborate?: Cross-domain collaborative filtering for sparsity reduction[END_REF][START_REF] Wang | Feature subspace transfer for collaborative filtering[END_REF].

There is also an important category of CF models, often referred as social model-based CF [START_REF] Ma | Recommender systems with social regularization[END_REF][START_REF] Tang | Social recommendation: a review[END_REF][START_REF] Bobadilla | Recommender systems survey. Knowledge-Based Systems[END_REF][START_REF] Delporte | Socially enabled preference learning from implicit feedback data[END_REF][START_REF] Gao | Content-aware point of interest recommendation on location-based social networks[END_REF], which exploit additional information from social networks (i.e, trusted users, friendship graph, followers, followed, etc) to improve the quality of recommendations. All these methods can provide reasonable prediction time, since the model is learned offline.

Hybrid approaches This category of recommender systems [START_REF] Burke | Hybrid recommender systems: Survey and experiments[END_REF] consists in combining several RS methods , in order to reap the benefits of several approaches simultaneously. Most of hybrid RSs combine collaborative filtering with content-based approaches [START_REF] Barragáns-Martínez | A hybrid content-based and item-based collaborative filtering approach to recommend tv programs enhanced with singular value decomposition[END_REF].

Related work and contribution

Collaborative filtering is the most often used approach in real-world recommender systems. Nevertheless, CF systems do have some drawbacks of their own. Traditional CF approaches, such as matrix factorization (MF) and memory-based methods, can achieve good prediction accuracy, but their computation time rises steeply as the number of users and items increases. Furthermore, these methods need to be performed periodically (offline) in order to take into account new ratings, users and items. However, with this strategy, new information which appear between two offline computations are not considered.

As a result, applying traditional CF techniques to real-world applications such as Netflix in which the sets of users, items and ratings are frequently updated, is a non-trivial task.

To overcome the problem of computation time, incremental CF systems have been proposed. The most popular are incremental CF based on MF approaches [START_REF] Sarwar | Incremental singular value decomposition algorithms for highly scalable recommender systems[END_REF][START_REF] Han | Incremental learning for dynamic collaborative filtering[END_REF], incremental CF based on co-clustering [START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF][START_REF] Khoshneshin | Incremental collaborative filtering via evolutionary coclustering[END_REF], and incremental memory-based CF, including user [START_REF] Papagelis | Incremental collaborative filtering for highly-scalable recommendation algorithms[END_REF] and item [START_REF] Yang | Scalable collaborative filtering using incremental update and local link prediction[END_REF] based approaches. All these efforts have demonstrated the effectiveness of developing incremental models to provide scalable collaborative filtering systems. But often, these approaches will significantly reduce the quality of recommendations. Further, most of these approaches (except memory-based CF) do not handle all possible dynamic scenarios (i.e, submission of new ratings, update of existing ratings, appearance of new users and new items). For instance incremental CF based on singular value decomposition [START_REF] Sarwar | Incremental singular value decomposition algorithms for highly scalable recommender systems[END_REF], do not treat the two first scenarios (mentioned above).

In this chapter we focus on the problem of computation time in CF systems. In order to overcome this drawback we propose a novel incremental CF approach, which is based on a weighted version of the online spherical k-means algorithm OSkmeans [START_REF] Zhong | Efficient online spherical k-means clustering[END_REF]. Our method is able to handle in a very short time the frequent changes in CF data, including the submission of new ratings, the update of existing ratings, the occurrence of new users and items. Below, we summarize the key contributions we make in this chapter.

-We derive a novel effective CF system, based on a weighted version of OSkmeans which is more suitable for CF data. -In order to handle frequent changes in CF data, we design incremental updates, which allow to efficiently treat submissions of new ratings, updates of existing ratings, and appearance of new users and items. -We provide extensive experiments on real-world datasets, under two scenarios: 1) static situation, where available data are kept unchanged, and 2) dynamic situation, where new information are incorporated incrementally. Numerical experiments validate our approach. The results on several real datasets show that our method outperforms significantly state-of-the-art incremental methods in terms of both scalability and recommendation quality.

Online spherical k-means

Throughout this chapter matrices are denoted with boldface uppercase letters and vectors with boldface lowercase letters. The user-item preference matrix is denoted by U = (u i j ) of size n × d, the i th row (user) of this matrix is represented by a vector u i = (u i1 , . . . , u ip ) ⊤ , where ⊤ denotes the transpose. The column j corresponds to the j th item. The partition of the set of rows into g clusters can be represented by a classification matrix Z of elements z ik in {0, 1} g satisfying ∑ g h=1 z ih = 1. The notation z = (z 1 , . . . , z n ) ⊤ , where z i ∈ {1, . . . , g} represents the cluster of i, will be also used.

Many clustering algorithms have been proposed depending on the type of data and patterns to be found. In this chapter we focus on the spherical k-means (Skmeans) algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], and in particular on its online spherical version (OSkmeans). Our focus on this algorithm is motivated by the effectiveness of the cosine similarity in the context of high dimensional sparse data, such as CF data [START_REF] Liu | A new user similarity model to improve the accuracy of collaborative filtering[END_REF], document-term matrices and gene-expression data (Banerjee et al., 2005b). Before describing OSkmeans, we will first introduce the Skmeans algorithm.

The Skmeans algorithm proposed by [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], and available in R software [START_REF] Hornik | Spherical k-means clustering[END_REF] is a k-means algorithm in which the objects (users) u 1 , . . . , u n are assumed to lie on a unit-hypersphere. The Skmeans algorithm originally maximizes the sum of the dot product between the elements of the data points and the g means directions characterizing the clusters. This is equivalent to maximizing the sum of the cosine similarity of the normalized data, and the aim at each iteration is to measure the similarity between u i and center µ h by ⟨u i ,

µ h ⟩ = u ⊤ i µ h = ∥u i ∥ ∥µ h ∥ cos(u i , µ h ) = cos(u i , µ h ).
Maximizing the sum of the dot products is equivalent to maximizing the sum of the cosine similarity on the unit hypersphere. The algorithm then maximizes the following objective function:

L = n ∑ i=1 g ∑ h=1 z ih cos(u i , µ h ) = n ∑ i=1 g ∑ h=1 z ih u ⊤ i µ h , (2.1)
where z ih ∈ {0, 1}; z ih = 1 if u i ∈ hth cluster, z ih = 0 otherwise. Skmeans repeats the following two steps until convergence:

-For i = 1, . . . , n, assign u i to the hth cluster, where

z i = arg max h u ⊤ i µ h , h = 1, . . . , g. -Calculate µ h = ∑ i,h z ih u i || ∑ i,h z ih u i || .
Note that, the objective function 2.1 is associated to a restricted von Mises-Fisher mixture model (Banerjee et al., 2005b). The latter will be studied in details in the next chapters. Furthermore, the online Skmeans developed by [START_REF] Zhong | Efficient online spherical k-means clustering[END_REF] uses competitive learning (Winner-Takes-All strategy) to minimize the objective function (2.1), which leads to where η is the learning rate, µ h is the closest centroid to the object u i , and

µ new h = µ h + η ∂ L i ∂ µ h ||µ h + η ∂ L i ∂ µ h || = µ h + ηu i ||µ h + ηu i || , Algorithm 1: OSkmeans. Input: n normalized objects u i (∥u i ∥ = 1) in R p ,
L i = ∑ g h=1 z ih u ⊤ i µ h .
From the OSkmeans method (described in Algorithm 1), we can see that each centroid is updated incrementally with a learning rate η. [START_REF] Zhong | Efficient online spherical k-means clustering[END_REF] proposed an exponentially decreasing learning rate η ⊤ = η 0 (

η f η 0 ) t n×B
, where η 0 = 1.0, η f = 0.01, B is the number of batch iterations and t, (0 ≤ t ≤ n × B) is the current iteration. The author showed that this decreasing learning rate is better than a flat rate (η = 0.05).

Efficient Incremental Collaborative Filtering system

In this section, we describe our collaborative filtering system EICF, designed to provide a high quality of recommendations with a very low computation cost. This system can be divided into three main steps: training, prediction, and incremental training. The different steps are as follows:

Training step

This step, consists in clustering the users into g groups. Unfortunately the traditional OSkmeans algorithm which has been proposed in the context of text document clustering, is not adapted for CF data. Unlike text data, the sparsity in CF is caused by unknown ratings, which requires a different handling than if the sparsity is caused by entries of "zero". To address this problem, we propose a novel variant of OSkmeans which is more suitable for CF. It consists in introducing user weights, in order to tackle the sparsity problem; by giving more importance to users who provided many ratings. The resulting clusters will be highly influenced by the most useful users (i.e. users with high weights). Below we give more details about this weighted version of OSkmeans. Let w i denotes the weight of the ith user, the weighted objective function of the Skmeans is given by:

L w = n ∑ i=1 L w i , where L w i = ∑ g h=1 w i z ih u ⊤ i µ h , (2.2)
Thus, the corresponding update centroid for the weighted OSkmeans is given by:

µ new h = µ h + η ∂ L w i ∂ µ h ||µ h + η ∂ L w i ∂ µ h || = µ h + ηw i u i ||µ h + ηw i u i || , (2.3)
We now give an intuitive formulation of user weights. Let M = (m i j ) be an (n × p) binary matrix, such that m i j = 1 if the rating u i j is available, and m i j = 0 otherwise. Its ith row corresponds to a vector m i = (m i1 , . . . , m ip ) ⊤ indicating which items have been rated by the ith user. Thus, we define the weight of the ith user to be proportional to the number of his available ratings as follows:

w i = (m T i ✶) × σ (u i ) (2.4)
where ✶ is the vector of the appropriate dimension which all its values are 1, and σ (u i ) denotes the standard deviation of ratings provided by u i . We consider the standard deviation in order to give less importance to users who provide only low ratings or similarly, only high ratings (i.e. users who expressed the same preference for all items they have rated).

In the following, we focus on the initialization of the clustering process which is a crucial step. In fact, initializing the weighted OSkmeans by sampling g random centroids is not effective. Most of users will have rated only a few items, so there is a high probability of selecting as an initial centroid a user with only few observed ratings. Furthermore, selecting the initial centroids only from the set of users who have rated a lot of items is not a good solution, because not all structures would be detected. In order to avoid this problem we suggest the following initialization routine:

1. Generate a random partition of the users into g clusters, which can be represented by z = (z 1 , . . . , z n ), where z i ∈ {1, . . . , g} represents the cluster to which the ith user belongs. 2. Estimate initial centroids as follows: let µ h j denotes the jth component of the kth centroid, then we have

µ h j = ∑ i m i j w i z ih u i j ∥ ∑ i w i z ih u i ∥ (2.5)
Algorithm 2: EICF training. Input: n normalized users u i (∥u i ∥ = 1) in R p , K is the number of clusters and B is the number of batch iterations; Output: K centers µ k in R p , and z = (z 1 , . . . , z n );

Steps:

1. Compute user weights: w i = (m T i 1) × σ (u i ); 2. Initialization: random initialization of the partition z, t = 1; 3. Estimation of the initial centroids:

µ k j = ∑ i m i j w i z ik u i j ∥ ∑ i w i z ik u i ∥ for b = 1 to B do
for each u i in U do 4. User assignment: compute z i = arg max k (w i u ⊤ i µ k ); 5. Centroid update: compute the winner centroid by μz i =

µ z i +ηw i u i ∥µ z i +ηw i u i ∥ ; t = t + 1 end for end for
According to formula (2.5), a component µ h j of an initial centroid is estimated by taking the sum over all observed ratings for the jth item, within the corresponding cluster h. Thereby, items which are rarely evaluated will be automatically penalized. Algorithm 2 describes in more details our training step.

Prediction step

In this step, unknown ratings are predicted according to the clustering results. However, it is difficult to make consistent predictions, even when the best clustering results are achieved, because there are so many unknown ratings in U. To overcome this difficulty we propose to estimate unknown ratings by a weighted average of observed ratings, as follows:

u a j = ∑ n i=1 w i z ih u ⊤ i µ h × u i j ∑ n i=1 w i z ih u ⊤ i µ h , (2.6)
Let u a denotes the active user, h = z a . The key idea behind this strategy is to weight the available ratings u i j according to the similarity between each user u i and its corresponding centroid µ h , and to weight by w i , in order to give greater importance for users closest to their centroid, and respectively to give more importance for ratings provided by most important users.

The prediction equation (2.6) is attractive because it only depends on the clustering results, which means that it can be performed offline and stored in a (g × d) matrix P, which leads to very short prediction times.

Incremental training step

In the sequel, we design incremental updates, in order to handle the frequent changes in CF data. We can distinguish four main situations: 1) submission of new ratings, 2) update of existing ratings, 3) appearance of new users, 4) appearance of new items. In the following, we give the update formulas for each situation.

Submission of a new rating Let u a denotes an active user who submits a new rating for an item j. The equations below, give the different incremental updates to perform in this case.

-Update the norm of u a : ∥u

+ a ∥ = ∥u a ∥ 2 + u 2 a j
-For each h, update the similarity between u a and µ h :

cos(u + a , µ h ) = 1 ∥u + a ∥ [∥u a ∥ × u ⊤ a µ h + u a j µ h j ],
-Update the weight of the active user:

ŵa = ( w a σ (u a ) + 1) × σ (u + a )
-Update the assignment of u a : ẑa = arg max h cos(u + a , µ h ).

-Update the corresponding centroid µ ẑa , by using formula (2.3) where

σ (u + a ) 2 = N a ×(σ (u a ) 2 + ū2 a )+u 2 a j N a +1
-(

N a ūa +u a j N a +1 ) 2 , thanks to König-Huygens formula, i.e., σ (u a ) = 1 N a ∑ j u 2 a j -ū2 a . The notation u + a denotes the active user u a after submitting the new rating u i j , N a and ūa denote respectively, the number of ratings and the average rating of u a before evaluating item j. Note that, as the centroids are stable at the end of training, the two latter incremental updates concerning the assignment of u a , do not need to be performed after each new rating.

Update an existing rating In this case, the active user updates an existing rating for an item j. As for the submission of a new rating, the main updates are summarized below.

-Update the norm of u a : ∥u

+ a ∥ = ∥u a ∥ 2 -u 2 a j + û2 a j
-For each h, update the similarity between u a and µ h :

cos(u + a , µ h ) = 1 ∥u + a ∥ [∥u a ∥ × u ⊤ a µ h -u a j µ h j + ûa j µ h j ]
-Update the weight of the active user: ŵa = w a σ (u a ) × σ (u + a )

-Update the assignment of u a : ẑa = arg max h cos(u + a , µ h ).

-Update the corresponding centroid ẑa , by using equation (2.3) where

σ (u + a ) 2 = (σ (u a ) 2 + ū2 a + û2 a j -u 2 a j
N a ) -( ūa + ûa j -u a j N a ) 2 , ûa j denotes the new value substituted for the existing rating u a j , and the notation u + a represents the active user after updating the known rating u a j .

Appearance of new user In this situation, a new user is incorporated into the model in real time. Let ûa denotes a new user. The model is incremented as follows:

-Compute the weight of ûa , by using equation (2.4).

-Assign ûa to cluster h where h = arg max 1≤h ′ ≤g (

û⊤ a µ h ′ ∥ ûa ∥ ).
-Update the corresponding centroid: μh =

µ h +ηw a ûa ∥ ûa ∥ ∥µ h +ηw a ûa ∥ ûa ∥ ∥
.

Appearance of new item When a new item appears, it has no ratings, so there is nothing to change in the model. When a new item starts receiving ratings, handling new item, reduces to handling the submission of new ratings.

Experimental results

Hereafter, we compare our collaborative filtering system with other popular incremental CF systems, over different real-world datasets.

Datasets

We use three popular datasets in the field of recommender systems. The first is MovieLens1

(ML-1M), consisting of 1,000,209 ratings provided by 6040 users for 3952 movies (only 4.2% of ratings are observed). The second is MovieLens (ML-100k), containing 100,000 ratings given by 943 users for 1664 movies. The proportion of observed ratings in this dataset is 6.4%. The last dataset is Epinions, with 664,824 ratings from 49,290 users on 139,738 items (movies, musics, electronic products, books, . . . ), it is collected from the epinions web site 2 . The Epinions dataset is more than 99% sparse. In all the above datasets the user ratings (u i j ) belong to the following set: {1, 2, 3, 4, 5, NA}, such that u i j = NA, for the non observed ratings.

Methods and environment

We compare our Efficient Incremental CF (EICF) with several popular methods, namely: incremental user-based CF IUCF [START_REF] Papagelis | Incremental collaborative filtering for highly-scalable recommendation algorithms[END_REF], incremental item-based CF IICF [START_REF] Yang | Scalable collaborative filtering using incremental update and local link prediction[END_REF], and incremental CF based on co-clustering COCLUST [START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF]. The comparisons are made with the R package recommenderlab [START_REF] Hahsler | recommenderlab: A framework for developing and testing recommendation algorithms[END_REF]. All the evaluations are made under the same machine (OS: ubuntu 14.04 LTS 64-bit, Memory: 8 GiB, Processor: Intel® Core™ i7-3770 CPU @ 3.40GHz × 8). Except for comparisons on Epinions data (OS: ubuntu 14.04 LTS 64-bit, Memory: 32 GiB, Processor: Intel(R) Xeon(R) CPU E5-2620 0 @ 2.00GHz).

Evaluation metrics

Prediction metrics such as Mean Absolute Error (MAE) or Root of Mean Square Error (RMSE) are widely used in order to evaluate recommender systems. As mentioned by the authors in [START_REF] Liu | A new user similarity model to improve the accuracy of collaborative filtering[END_REF], these metrics are not the most relevant in the context of RS, because they do not measure the quality of the set of recommendations. In many cases, low MAE and RMSE do not necessarily equate to best user satisfaction. As illustrated in Table 2.1, whether the ratings are in the set {1, 2, 3, 4, 5} let u a be an active user who rated two items as follows: u a1 = 2 and u a2 = 4 and the three recommender systems RS1, RS2 and RS3. As reported in this table, -RS1 predicts 1 instead of 2 for u a1 and 5 instead of 4 for u a2 , -RS2 predicts 2 for u a1 and 3 for u a2 , -and RS3 predicts 3, for both u a1 and u a2 .

In terms of MAE and RMSE, RS2 appears to be the best. However RS1 will make better recommendations; indeed, it does not recommend the first item since it predicts 1 and unlike RS2, it clearly recommend the second item; it is a good recommendation since the real rating Precisions, Recall and F-measure. These metrics measure the quality of the set of recommendations [START_REF] Bobadilla | Recommender systems survey. Knowledge-Based Systems[END_REF], which makes them more appropriate for evaluating RS. Below we give a brief description of the aforementioned metrics:

Precision: is the proportion of good recommendations R g from the total number of recommendations

R T : precision = R g R T .
Recall: is the proportion of good recommendations from the number of relevant items in the testing set RI t : recall = R g RI t . F-measure(F1): combines precision and recall as follows:

F1 = 2 × precision × recall precision + recall .
The ROC curve is the plot of recall (true positive rate TPR) by the proportion of bad recommendations out of the total number of recommendations (false positive rate FPR). To evaluate our CF system we focus on the quality of the recommendations and the computation time (prediction and training time).

Performance comparison

To measure the quality of recommendations we adopt the following split strategy: 1) We generate ten random training-test (80-20%) sets from each database. 2) In each test set only

x ratings per user are given to the recommender systems and the others are retained for the evaluation. This method is known as the Given x protocol (Given x) [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative filtering[END_REF][START_REF] Hahsler | recommenderlab: A framework for developing and testing recommendation algorithms[END_REF]. In the following evaluations we set x = 10 in the static situation and x = 5 in the dynamic situation. 3) Averaged results (ROC-curves, F-measure F1, MAE, RMSE) are presented for each RS over all the splits. Before starting the comparisons we experimentally define the best parameters for each algorithm on each dataset using the following strategy: each RS is performed several times with different parameters on the corresponding dataset, and the parameters that correspond to the best performance are retained. Figure 2.1 illustrates the above process for assessing the number of clusters for EICF on different datasets. At the end we obtain the following parameters.

-For the ML-100k: the number of clusters g = 7 for our approach EICF; the number of k-nearest neighbours is set to 25 and 40 for IUCF and IICF, respectively. For COCLUST we select the same parameters as those used by George and Merugu [START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF], the number of row and column clusters are both set to 3. -For the ML-1M: the number of clusters g = 20 for EICF; the number of k-nearest neighbours is set to 50 for both IUCF and IICF; and for COCLUST the number of row and column clusters are both set to 3. -For the Epinions dataset: we retain 10 clusters for EICF, the number of k-nearest neighbours is set to 120 and 135 for IUCF and IICF, respectively. The number of row clusters and column clusters for COCLUST are set to 6 and 7 respectively. Below, we report the performances of each method on each dataset, under two situations: 1) static situation, where available data are kept unchanged, and 2) dynamic situation, where new information are incorporated incrementally. From figures 2.2a and 2.2b we note that on the ML-100k dataset our method EICF provides a high quality of recommendations, thanks to our approach for alleviating the sparsity problem; by introducing user weights. Moreover, both figures show that, EICF outperforms all other incremental approaches. We also note a low recommendation quality from COCLUST, which can be explained by the fact that COCLUST ignores the sparsity problem, and operates only on data that have actually been observed. In other words, COCLUST combines different summary statistics in order to compute the predictions (user, item averages, row-cluster, column-cluster and co-cluster averages) which are highly biased since they are often estimated from rare observed values. All of this lead to a low quality of recommendations.

Static situation

Figure 2.3 shows that with the ML-1M dataset our method achieves a high quality of recommendations, and still outperforms all other methods, just like with the ML-100k dataset, which confirms the stability of our approach. the two latter approaches is due to the high rate of unknown ratings (the Epinions dataset is more than 99% sparse). For COCLUST we provided an explanation above, for IICF, the reason is that, most items have received only few ratings, thereby the estimation of item-to-item similarities is not reliable.

Computation time comparison

To compare computation time we generate four subsets from the MovieLens (ML-1M) database: Movie40, Movie60, Movie80 and Movie100. Each MovieX is obtained by randomly sampling X% of users and X% of items from ML-1M. For each subset and each approach, to estimate the average computation time (training + prediction time), we use the split strategy described above. To make coherent comparisons, we retain for each method the same parameters that were used for the ROC and F1 comparisons. Figure 2.5 shows that EICF is the best in terms of computation time. As reported in Table 2.2, the complexity of EICF is just O(gBW * ) for the training step and O(1) for the prediction step, where B is the number of batch iterations, W * is the total number of observed Table 2.2 Comparison of computational times (in the worst case) in various situations. W * denotes the number of observed ratings in U. g and m are the number of row and column clusters, k denotes the number of neighbours for memory CF (IUCF, IICF). d * is the number of observed ratings for a new user, n * denotes the number of available ratings for a new item. Finally, B denotes the number of iterations

Algorithm

Static training Prediction Inc. train

IUCF O(nW * ) O(k) O(nd * ) EICF O(gBW * ) O(1) O(gd * ) COCLUST O(BW * + ngmB + dgmB) O(1) O(d * ) IICF O(dW * ) O(d * ) O(dn * )
ratings in U, and g is the number of clusters (i.e, g ≪ n and g ≪ d). Moreover, Figure 2.5 shows that the computation time required by memory-based methods (IUCF and IICF) is high and increases more rapidly. This is due to the intensive training step of these approaches, which consists in computing user-to-user and item-to-item similarities for IUCF and IICF, respectively. From Figure 2.5, we also note that the computation time of COCLUST is high, even if its complexity (training: O(W * + ngm + dgm); prediction: O( 1)) might appear attractive. The reason is that COCLUST fails to converge rapidly, because the estimates used in this method's optimization step are biased. Furthermore, the strategy proposed by the authors in [START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF], which consists in replacing the average of empty blocks (i.e, which do not contain observed ratings) by the global rating average, disturbs the convergence of the co-clustering.

Dynamic situation

In this case new information (i.e, ratings, users and items) are incorporated incrementally, after the training step of each method. From Figures 2.6 and 2.7, we observe that on both MovieLens datasets, EICF continues to exhibit a high quality of recommendation; thanks to its efficient incremental updates for handling new data. As in the static case, EICF outperforms all other incremental methods. We also observe that COCLUST continues to provide poor performances in the dynamic situation, because it uses only partial updates for handling new changes in CF data, thereby new information are not really incorporated into the model in a dynamic way. In fact, for new users the predictions are based on item averages computed from available ratings. Thus, the recommendations for new users, are made without involving the co-clustering model. We can also note a significant decrease in the performances of IICF and COCLUST; a poor recommendation for both methods in all the recommendation lists (TPR ≃ 0, for all the lists). This is due to sparsity problem as mentioned above; more than 99% of ratings are unknown in the Epinions dataset.

Computation time in the dynamic situation

In Table 2.2 we reported the complexity of the incremental updates (i.e, incremental training) in the worst case, for each method. Incorporating a new user, represents the most expensive computation for EICF and IUCF, similarly incorporating a new item denotes the worst case for IICF. From Table 2.2, we observed that EICF have the best complexity in the dynamic scenario. In fact, in order for EICF to incorporate a new user ûa with d * observed ratings, it performs an assignment and update steps. The cost of the assignment is O(gd * ), as g similarities need to be computed and at most d * dimensions (items) will be involved. The cost of updating the winner centroid is O(d * ), at most d * items will be considered. Thus, the total cost of EICF for handling a new user is O(gd * ) (i.e, based on O(gd * ) + O(d * )).

In order to measure the computation time in the dynamic situation, 20% of users (i.e, randomly selected) in each dataset are considered as new ones. We then report in Table 2.3, the computation time required by each method, for incorporating and generating recommendations for these users. Note that IICF is favoured in this comparison, unlike the other methods; incorporating new users is not the most expensive computation for this approach.

From Table 2.3 we observe that EICF requires much less time for handling new information, than the other incremental methods, including IICF although it is advantaged. This performance rises significantly as the volume of data increases. In fact, contrary to the other methods, the complexity of EICF does not depend on the number of users and items. Therefore, EICF is more suitable than the other incremental methods, for real world applications involving large databases in which users, items and ratings are frequently updated. Note that, the computation time of COCLUST reported in Table2.3 is high, even if its complexity in the dynamic situation (i.e, inc. train: O(d * )) might appear attractive. The reason is that, this approach provides only partial updates, and the co-clustering is performed periodically to completely incorporate new information.

Conclusion and perspectives

In this chapter we presented a novel efficient and effective incremental CF system, which is based on a weighted clustering approach. To achieve high quality of recommendations, we introduced user weights into the clustering process, to lessen the effect of users who provided only few ratings. In order to address the computational time problem, we designed incremental updates, which allows our system to handle in a very short time, the frequent changes in CF data; such as submissions of new ratings, appearance of new users and items. Numerical experiments on real-world datasets demonstrate the efficiency and the effectiveness of our method which provides a better quality of recommendations than existing incremental CF systems, while requiring less computation time. In fact, unlike the other methods, the complexity of our approach does not depend on the number of users and items. Thus, EICF is more suitable than existing incremental approaches, for real-world applications involving huge databases, in which available information (i.e, users, items and ratings) frequently changes.

The good results of EICF suggest practical possible studies. A possible future work can be to improve the efficiency of EICF, by developing a parallel version, that can support distributed computations. On the other hand, more advanced strategies for handling the sparsity problem in CF can be considered. To this goal, two main tracks deserve to be investigated. The first consists in developing a social version of EICF, that can exploit information from social networks [START_REF] Tang | Social recommendation: a review[END_REF]. The second consists in using statistical approaches for handling missing data because the sparsity in CF is due to missing ratings [START_REF] Little | Statistical analysis with missing data[END_REF][START_REF] Marlin | Collaborative filtering and the missing at random assumption[END_REF]. As earlier works shown that the Skmeans algorithm can be derived from mixture of von Mises-Fisher distributions (Banerjee et al., 2005b), it will be possible to handle the missing ratings statistically [START_REF] Little | Statistical analysis with missing data[END_REF]. Furthermore, in order to treat both users and items simultaneously, we can embed the EICF in a probabilistic co-clustering framework. In this way, we can use the latent block models (Govaert andNadif, 2003, 2013) and derive a variant of the Block EM algorithm [START_REF] Govaert | An EM algorithm for the block mixture model[END_REF].

Finally, our approach could imply the extension of NMF approaches (widely used in CF) to the context of dynamic CF. Indeed, it has been shown that under some restrictions NMF can be interpreted as a clustering approach [START_REF] Xu | Document clustering based on non-negative matrix factorization[END_REF]. Hence, in the case of two factors NMF, the first factor indicates the degree in which a user belongs to a cluster and the second one contains cluster centroids. Thus, based on the incremental updates of EICF (mainly related to users assignments and centroids updates), one can similarly design incremental updates for the latent factors in the NMF context.

Chapter 3 Directional Clustering with Social-Network information for Recommendation

Collaborative Filtering models are severely challenged by the high dimensionality and sparsity of user-item preference matrices. Recently, several works have shown that incorporating information from social networks, such as friendship and trust relationships, into traditional CF alleviates the sparsity related issues and yields a better recommendation quality in most cases. More interestingly, even with comparable performances, social-based CF is more beneficial than traditional CF; the former makes it possible to provide recommendations for cold start users. This chapter presents a novel CF model that leverages information from social networks in order to improve recommendations. While existing social CF approaches are based on popular modelling assumptions such as Gaussian or Multinomial, our model is based on the von Mises-Fisher assumption that turns out to be more adequate than the aforementioned assumptions, for high dimensional sparse data. Setting the model parameters under the maximum likelihood approach, we derive an effective social-based CF system. Empirical results on several real-world datasets provide strong support for the advantages of the proposed model.

Introduction

Although memory-and model-based CF approaches introduced in the previous chapter, often denoted as traditional CF methods, constitute an important contribution to CF and can offer a good recommendation accuracy, these techniques are still seriously challenged by the characteristics of collaborative filtering data, i.e. high dimensionality and sparsity. Over the last few years, with the advent of social networks, social-based collaborative filtering has emerged as a new promising technique to alleviate the sparsity related issues. Such an approach consists in using information from online social networks-usually friendship and/or trust information-to improve recommendations. More intuitively, social-based CF approaches are based on the assumption that, for making a good recommendation, not only the user's expressed preferences are important but also the user's social interactions. This is natural, since in real life people often turn to their friends, to ask for a nice movie to watch, an interesting book to read, a good restaurant, etc. By taking into account this real-life behaviour, social-based CF approaches make more realistic recommendations and are therefore expected to offer better performances than traditional CF methods. More interestingly, even with comparable recommendation accuracy, social-based methods are more beneficial than traditional approaches, in that they can make recommendations for cold start users-with very few expressed preferences or none at all. In fact, Social CF models exploit the social interactions of cold-start users to provide them with useful recommendations.

As mentioned in the beginning of this thesis and the previous chapter, apart from being high dimensional and sparse , CF data are also directional in nature. In fact, it seems better to model CF data as directional data distributed on the surface of a unit-hypersphere [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF]Banerjee et al., 2005b), and to use directional measures, such as the cosine similarity, instead of euclidean distortions to assess the similarities between users/items.

Existing social CF models, however, are based on popular modelling assumptions, such as Gaussian or Multinomial, which are inadequate for directional data lying on the surface of a unit-hypersphere. Hence, it seems natural to question whether it is possible to leverage both the users' social interactions and the directional properties of CF data, simultaneously. In this chapter, we provide an answer to this question: we develop a novel social CF model which is based on the von Mises-Fisher (vMF) assumption, that arises naturally for directional data lying on the surface of a unit-hypersphere. The proposed model successfully integrates a directional measure, namely the cosine similarity, into a social CF model. This makes it possible to achieve a high recommendation accuracy, as illustrated in our experiments. To the best of our knowledge the work we present is the first social-based CF approach that accounts for the directional characteristics of collaborative filtering data.

The remainder of the chapter is organized as follows. Section 2 is devoted to present related work. In Section 3, we review the vMF mixture model, then we propose to generalize the above model to account for social interactions among users and derive a scalable Generalized Expectation-Maximization (GEM) algorithm for inference and parameter estimation (Section 4). Finally, we evaluate our contribution on real data sets.

Related work

The work we present here is related to two main topics, namely CF approaches accounting for social-network information, and vMF mixture models from directional statistics [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF]Banerjee et al., 2005b).

Over the last few years, several social-based collaborative filtering approaches have been proposed, most of which are based on Probabilistic Matrix Factorization (PMF) [START_REF] Ma | Sorec: social recommendation using probabilistic matrix factorization[END_REF][START_REF] Ma | Learning to recommend with social trust ensemble[END_REF][START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF][START_REF] Ma | Recommender systems with social regularization[END_REF]. The key idea behind these approaches is to make the latent preference factor of each user close to that of his/her direct neighbors in the user-user social graph, so as to capture the influence between friends. In [START_REF] Ma | Sorec: social recommendation using probabilistic matrix factorization[END_REF] the authors built a MF model that connects the user-item preference matrix with the user-user social graph through a shared user latent factor. The same authors in [START_REF] Ma | Learning to recommend with social trust ensemble[END_REF] proposed an approach that fuses a MF model on the user-item matrix with a MF on the user-user graph, then predicts unknown preferences by combining the ratings resulting from both models. Based on the above works, in [START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF] the authors proposed SocialMF another matrix factorization-based method that accounts for trust propagation. Ref. [START_REF] Ma | Recommender systems with social regularization[END_REF] proposed to add a regularization, into the traditional PMF [START_REF] Salakhutdinov | Probabilistic matrix factorization[END_REF], so as to bring the latent factors of socially connected users closer to each other. In [START_REF] Yang | Social collaborative filtering by trust[END_REF] the authors proposed three trust MF-based models that consider different aspects of trust information. The first variant reflects that the preference of a user for an item is influenced by the preferences of his/her trustees on that item, the second reflects that the behaviour of a user will influence that of his/her trusters and the third is a combination of the above two during the prediction phase. More recently, in [START_REF] Guo | Trustsvd: Collaborative filtering with both the explicit and implicit influence of user trust and of item ratings[END_REF] the authors proposed TrustSVD an extension of the well known SVD++ [START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative filtering model[END_REF] method that accounts for social trust information. Ref. [START_REF] Chaney | A probabilistic model for using social networks in personalized item recommendation[END_REF] proposed Social Poisson Factorization. In addition to learn the user and item latent factors, as in traditional MF, this method introduces a third latent factor that reflects how much each user is influenced by his/her direct neighbors in the social network. Then, the preference of a user for an item is explained by combining the three factors above.

All these efforts demonstrated that, considering information from social networks in CF makes it possible to alleviate the sparsity related issues and generate more realistic and accurate recommendations. Nevertheless, existing approaches to social CF are based on popular assumptions such as Gaussian, Multinomial or Poisson, and therefore do not account for the aforementioned directional characteristics of CF data. In this chapter, we aim to address this limitation by building a novel model-based social CF approach, that leverages the social interactions among users as well as the directional properties of CF data. More precisely, the proposed model is based on a mixture of von Mises-Fisher distributions, and successfully integrates a directional measure, the cosine similarity, into a social CF framework.

The vMF distribution is a continuous probability distribution, on a unit-hypersphere, from directional statistics [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF]. It focuses on the directions of objects and measures the distance between them using the cosine similarity. Most of the earlier works using vMF distributions focused on low dimensional data, i.e., 2-or 3-dimensional data [START_REF] Mclachlan | Finite mixture models[END_REF], due to the difficulties related to the estimation of the concentration parameter kappa, which involves the inversion of a ratio of Bessel functions. A notable contribution is the mixture of vMF distributions movMFs (Banerjee et al., 2005b) for clustering high dimensional sparse data. Banerjee et al. (2005b) derived an EM-based solution for inference and parameter estimation, and they proposed an accurate approximation to estimate the concentration parameter κ for a high dimensional vMF distribution. Since this contribution, different vMF-based models for high dimensional sparse data have been proposed. For instance [START_REF] Reisinger | Spherical topic models[END_REF] proposed a topic model based on a mixture of vMF distributions. More recently, for text data clustering, [START_REF] Gopal | Von mises-fisher clustering models[END_REF] proposed a full Bayesian formulation of movMFs and developed two novel variants of movMFs, namely hierarchical and temporal. [START_REF] Le | Semantic visualization for spherical representation[END_REF] proposed a vMF-based model for the semantic visualization of high dimensional sparse text data.

Preliminaries

In this section, we shall describe the mixture of von Mises-Fisher distributions proposed by Banerjee et al. (2005b), but first we review the von Mises-Fisher (vMF) distribution, which is well known in directional statistics [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF].

The Multivariate von Mises-Fisher (vMF) Distribution

A d dimensional vMF (d-vMF) distribution, i.e, d ≥ 2 is a continuous probability distribution on a unit hypersphere S d-1 . Thus, if a d dimensional data point x i on S d-1 , i.e, x i ∈ R d and ∥x i ∥ = 1 follows a d-vMF distribution, its probability density function is given by: where µ is the mean direction (centroid) parameter and κ denotes the concentration parameter, such that ∥µ∥ = 1 and κ ≥ 0. The normalization term c d (κ) is equal to:

f (x i |µ, κ) = c d (κ) exp κ µ T x i , ( 3
c d (κ) = κ d 2 -1 (2π) d 2 Id 2 -1 (κ) (3.2)
where I r (κ) represents the modified Bessel function of the first kind and order r. In the vMF distribution the parameter κ controls the concentration of data points x i ∈ S d-1 following (3.1), around the mean direction µ. Thus, f (x i |µ, κ) reduces to the uniform density on S d-1 for κ = 0, and it is uni-modal if κ > 0. In particular, when κ → ∞, f (x i |µ, κ) tends to a point density. Figure 3.1 illustrates the impact of κ, by presenting three sample of 100 points on the unit circle (i.e d = 2) according to three 2-vMF distributions with the same centroid µ, but with different values of κ. For more details on the vMF distribution, the reader can refer to [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF][START_REF] Dhillon | Modeling data using directional distributions[END_REF].

The mixture of von Mises-Fisher Distributions (movMFs)

Now, we review the mixture model of von Mises-Fisher distributions for clustering directional data distributed on a unit hypersphere (Banerjee et al., 2005b). In this model, the data points x 1 , . . . , x n are assumed to be generated from a mixture of g vMF distributions with a set of unknown parameters Θ. The density function of this mixture takes the following form:

f (x i |Θ) = ∑ h α h f h (x i |µ h , κ h ), (3.3)
α z i κ z i x i µ z i n Fig. 3.
2 movMFs as a graphical model.

where Θ = {µ 1 , . . . , µ g , α 1 , . . . , α g , κ 1 , . . . , κ g }, µ h and κ h represent the centroid and the concentration parameters of the h th component, respectively. Each parameter α h denotes the proportion of points x i generated from the h th component, such that ∑ h α h = 1 and α h > 0, ∀h ∈ {1, . . . , g}. The generative process of this model is summarized below:

1. Choose a component h ∼ Multinomial(α 1 , . . . , α g ).

Choose a data point

x i on S d-1 ∼ f h (x i |µ h , κ h ).
The graphical model of the vMF mixture model (movMFs) is depicted in figure 3.2, and the corresponding log-likelihood function takes the following form

L(Θ; X) = ∑ i log ∑ h α h f h (x i |µ h , κ h ) , (3.4)
As the optimization of the above function is intractable, we rely on the "complete" data likelihood given by

L(µ, α, κ; X, z) = ∏ i α z i (c d (κ z i ) exp κ z i µ ⊤ z i x i ), (3.5)
where z is the latent variable which is assumed to be known, i.e, z i = h if x i is generated from the h th component. Using the classification matrix Z, the corresponding complete data log-likelihood takes the following form:

L c (Θ; X, Z) = ∑ h z .h log α h + ∑ h z .h log c d (κ h ) + ∑ i,h z ih κ h µ ⊤ h x i (3.6)
where z .h denotes the cardinality of cluster h.

As the latent variable z is unknown in practice, the authors in (Banerjee et al., 2005b) proposed to use the EM algorithm to obtain the maximum likelihood estimates for the parameters Θ. The E-step finds the conditional expectation of the missing variable z given the current estimated parameters Θ (t) and the observed data, i.e. zih = E(z ih = 1|x i , Θ (t) ).

The M-step finds the new parameters Θ (t+1) maximizing the expectation of the complete data log-likelihood (3.6) subject to the constraints ∑ h α h = 1, ∥µ h ∥ = 1 and κ h > 0. This procedure leads to the soft vMF clustering algorithm (Banerjee et al., 2005b), denoted in this chapter as movMF.

Note that if we impose the following constraints on the parameters: equality of proportions α 1 = . . . = α h and concentration κ 1 = . . . = κ h parameters, the maximization of L c (Θ; X, Z) reduces to the maximization of the spherical k-means criterion [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF]Banerjee et al., 2005b)

∑ i,h z ih κ h µ ⊤ h x i = ∑ i,h z ih < µ h , x i >= ∑ i,h z ih cos(δ ih )
where <, > denotes the scalar product and δ ih is the angle between both vectors x i and µ h . So when relying on a vMF mixture model, the cosine similarity is underlying. In fact, the well known spherical k-means algorithm, using cosine similarity instead of euclidean distortions, arises as special case from the movMF algorithm considered in this chapter, when we enforce some restrictive constraints (Banerjee et al., 2005b).

Social von Mises-Fisher Mixture Model

We now propose Social-movMFs a novel model that leverages simultaneously the benefits of the vMF-based modeling and social information. Specifically, we propose to generalize the mixture of vMF distribution movMFs, presented above, to account for the social interactions among users. The intuition behind our model is to bring the distributions over clusters of socially connected users closer to each other. To this end, inspired from previous works on learning using manifold regularization [START_REF] Zhu | Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning[END_REF][START_REF] Belkin | Manifold regularization: A geometric framework for learning from labeled and unlabeled examples[END_REF][START_REF] Cai | Modeling hidden topics on document manifold[END_REF][START_REF] Mei | Topic modeling with network regularization[END_REF][START_REF] He | Laplacian regularized gaussian mixture model for data clustering[END_REF], we propose to smooth the posterior probabilities zih based on the user-user graph. Posterior smoothness can be achieved by using any adequate function, here we adopt the quadratic energy function-also denoted as the graph harmonic function- [START_REF] Zhu | Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning[END_REF] defined as follows in our case

R(T ) = 1 2 ∑ h ∑ i ∑ j τ i j (z ih -z jh ) 2 (3.7)
where τ i j = 1 if users i and j are socially connected and τ i j = 0, otherwise, T = (τ i j ) is the adjacency matrix of the user-user social graph. The above function is minimized if all socially connected users exhibit similar posterior distributions over clusters. Recall that our purpose is to force socially connected users to exhibit similar distributions over clusters. This objective can be achieved by regularizing the log-likelihood (3.4) by function (3.7). By doing so in an adequate manner, we obtain the following regularized log-likelihood:

L r (Θ; X, T ) = L(Θ; X) -λ R(T ) (3.8)
where R(T ) plays the role of the regularization term that enforces smoothness of the posterior probabilities on the social network, and λ is the regularization parameter that controls the degree of smoothness. Observe that the complete data log-likelihood (3.6) of movMFs arises from (3.8) as a special case when λ = 0. The corresponding regularized complete data log-likelihood can be obtained by substituting L c (Θ, X, Z) for L(Θ, X) in (3.8).

It is worth noting that the regularized log-likelihood (3.8) is penalized by users who are socially connected and who exhibit substantially different distributions over clusters. Thus, as opposed to the movMFs model, Social-movMFs accounts for interactions among users.

Maximum Likelihood estimates

In order to obtain the maximum likelihood estimates of the model parameters we rely on the Generalized EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF][START_REF] Mclachlan | The EM algorithm and extensions[END_REF]. The E-step is to estimate the posterior probabilities zih , given the current estimated parameters Θ (t) and the observed data X, as follows [START_REF] Neal | A view of the em algorithm that justifies incremental, sparse, and other variants[END_REF]:

zih = E(z ih = 1|x i , Θ (t) ) ∝ α (t) h f h (x i |µ (t) h , κ (t) h ).
(3.9)

The M-step finds the new parameters Θ (t+1) maximizing or increasing the expectation of the complete data log-likelihood which is given by

Q(Θ, Θ (t) ) = E L c (Θ; X, Z)|X, Θ (t) = ∑ i,h z.h log α h + ∑ h z.h log c d (κ h ) + ∑ i,h zih κ h µ ⊤ h x i (3.10)
where z.h = ∑ i zih . The above optimization scheme yields the movMF algorithm providing parameter estimation for the classical movMFs model (Banerjee et al., 2005b). In our case, the purpose is to take into account social interactions among users. Thus, instead of maximizing expression (3.10), we maximize the following regularized expected complete data log-likelihood (or equivalently the expectation of the regularized complete data log-likelihood):

Q r (Θ, Θ (t) ) = Q(Θ, Θ (t) ) -λ R(T ) = ∑ i,h z.h log α h + ∑ h z.h log c d (κ h ) + ∑ i,h zih κ h µ ⊤ h x i - λ 2 ∑ h ∑ i ∑ j τ i j (z ih -z jh ) 2 (3.11)
Note that the direct maximization of expression (3.11) is intractable due to the introduction of the regularization term-the M-step of EM does not have a closed-form solution. Fortunately, in the GEM algorithm it is sufficient to find a better Θ at each iteration, i.e. we choose t) ). Hence, following the strategy described in [START_REF] Cai | Modeling hidden topics on document manifold[END_REF][START_REF] He | Laplacian regularized gaussian mixture model for data clustering[END_REF], which is closely related to the optimization scheme proposed in [START_REF] Zhu | Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning[END_REF] in the context of semi-supervised learning, we derive an efficient M-step that is guaranteed to increase (3.11) at each iteration. The key idea is to optimize the different parts of (3.11) separately so as to increase Q r (Θ (t) , Θ (t) ). More precisely, we first minimize the regularization term, as it depends only on the posterior probabilities zih . This step yields the smoothed posteriors on the user-user graph. It is obvious that the smoothed posterior zih minimizing R(T ) is given by zih = ∑ j τ i j z jh ∑ j τ i j . This minimization scheme, however, can lead to a strong smoothing, where the new posteriors are substantially far from the original ones. Hence, for a better control of the smoothing process one should decrease R(T ) gradually, instead of its direct minimization. This can be done by the Newton-Raphson method as follows:

Θ (t+1) so that Q r (Θ (t+1) , Θ (t) ) ≥ Q r (Θ (t) , Θ (
zih := zih -γ R ′ (T ) R ′′ (T ) = (1 -γ)z ih + γ ∑ j τ i j z jh ∑ j τ i j (3.12)
where R ′ , R ′′ denote the first and second derivative of the regularization term relative to zih , and γ ∈ [0, 1] is the Newton-Raphson's step parameter. In our context, we can think of γ being the level of smoothing. If γ = 0 then no smoothing is performed, and if γ = 1 then the smoothed posterior distribution of each user is completely specified by the posterior distributions of his neighbors in the social graph.

Once the smoothing step is done, the next step consists in maximizing the expectation of the complete data log-likelihood Q relative to the parameters Θ, which yields the following update formulas (Banerjee et al., 2005b):

αh = ∑ i zih n , (3.13a) μh = r h ∥r h ∥ where r h = ∑ i zih x i , (3.13b) κh ≈ rh d -r3 h 1 -r2 h where rh = I d/2 ( κh ) I d/2-1 ( κh ) = ∥r h ∥ ∑ i zih . (3.13c)
Notice that, an exact estimation of the concentration parameter κh implies to inverse a ratio of Bessel functions, which has not a close form expression. To overcome this difficulty Banerjee et al. (2005b) proposed the efficient approximation (3.13c), which is suitable for high dimensional datasets. Furthermore, [START_REF] Tanabe | Parameter estimation for von mises-fisher distributions[END_REF] showed theoretically that the above approximation lies in the interval in which the exact ML estimates of κ h exists. More accurate approximation of κ h can be reached by using iterative methods [START_REF] Tanabe | Parameter estimation for von mises-fisher distributions[END_REF][START_REF] Sra | A short note on parameter approximation for von mises-fisher distributions: and a fast implementation of i s (x)[END_REF], the latter, however, are less suitable in high dimensions, since they involve an extensive computation of a ratio of Bessel functions.

It is worth nothing that the M-step just described does not necessarily increase the regularized log-likelihood function (3.8), due to the smoothing step. In order to address this issue, we adopt the same strategy as in [START_REF] Cai | Modeling hidden topics on document manifold[END_REF][START_REF] He | Laplacian regularized gaussian mixture model for data clustering[END_REF]. After each M-step we check if the regularized log-likelihood function has been decreased, then we decrease the smoothing parameter γ and perform again the M-step. Alternating the above E-step and optimization scheme (M-step) constitutes our soft social movMF algorithm-denoted as Soc-movMF in the rest of the chapter-, which is described in more details by Algorithm 3.

It can be shown that the computational complexity of Soc-movMF is

O(g • nr + g • ns)
per iteration, which scales linearly with the number of observed relations ns in the social network and observed ratings nr in the user-item matrix. In practice, we have nr ≪ n × d and ns ≪ n × n, thereby Soc-movMF is very efficient and suitable for large datasets.

Fitting the parameters of the proposed model Social-movMFs, to the user-item matrix, using Soc-movMF constitutes the training component of our CF system. Once this step is done, the missing ratings of the ith user can be easily predicted as follows

xi = ∑ h zih µ h ∥ ∑ h zih µ h ∥ . (3.14) Algorithm 3: Soc-movMF. Input: X (x i ∈ S d-1
) the rating matrix of size (n × d), T the adjacency matrix of the social network, g the number of clusters, λ the regularization parameter.

Output: Z, Θ; 1. Random initialization: Θ ← Θ (0) ; t ← 0; repeat 2. Expectation step of GEM:

for i = 1 to n do for h = 1 to g do z(t) ih ← α h f h (x i |µ h ,κ h ) ∑ ℓ α ℓ f ℓ (x i |µ ℓ ,κ ℓ )
end for end for 3. Maximization step of GEM: smooth ← TRUE; γ ← 0.9; while smooth do 3.1 Smooth the posterior probabilities z(t+1

) ih ← z(t) ih ; ∀i, h z(t+1) ih ← (1 -γ)z (t+1) ih + γ ∑ j τ i j z(t+1) jh ∑ j τ i j ; ∀i, h 3.2. Compute the new parameters Θ (t+1) for h = 1 to g do αh ← ∑ i z(t+1) ih n μh ← r h ∥r h ∥ with r h = ∑ i z(t+1) ih x i κh ← rh d-r 3 h 1-r 2 h with rh = I d/2 ( κh ) I d/2-1 ( κh ) = ∥r h ∥ ∑ i z(t+1) ih . end for 3.3. Compute the regularized log-likelihood L r (Θ (t+1) ; X) ← L(Θ (t+1) ; X) -λ R(T ) if L r (Θ (t+1) ; X) < L r (Θ (t) ; X) then 3.4 Decrease the smoothing parameter γ γ ← γ × γ else smooth ← FALSE; t ← t + 1; end if end while until convergence
Observation It is worth noting that the proposed model Social-movMFs allows the propagation of social information, between users, through the smoothing process (see step 3.1 in Algorithm 3). A property which is desirable since it may help to alleviate the sparsity related issues in both the rating matrix and social network, as it has already been emphasized in previous works [START_REF] Ma | Sorec: social recommendation using probabilistic matrix factorization[END_REF][START_REF] Ma | Learning to recommend with social trust ensemble[END_REF][START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF].

Experimental study

To show the benefits of our approach, we conduct extensive experiments on several realworld datasets, in which we benchmark Soc-movMF against several strong competing social-CF methods, namely SoRec [START_REF] Ma | Sorec: social recommendation using probabilistic matrix factorization[END_REF], RSTE [START_REF] Ma | Learning to recommend with social trust ensemble[END_REF], SocialMF [START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF], SoReg [START_REF] Ma | Recommender systems with social regularization[END_REF]), TrustMF (Yang et al., 2013) and TrustSVD [START_REF] Guo | Trustsvd: Collaborative filtering with both the explicit and implicit influence of user trust and of item ratings[END_REF]. In order to illustrate the advantage of leveraging information from social networks, we also compare Soc-movMF with the traditional movMFs-based clustering algorithm movMF (Banerjee et al., 2005b). Notice that movMF arises as a special case from Soc-movMF when λ = 0. For all competing methods we used LibRec1 , except for movMF we used our implementation.

Note that previous works, in the context of social CF, established empirically that the aforementioned competing methods perform better than several traditional CF approaches, such as SVD++ [START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative filtering model[END_REF], Matrix Factorization-and probabilistic MF-based methods, therefore we do not consider these approaches in our experiments.

Datasets

We selected five popular benchmark real-world datasets, including both the user-item preferences and social relationships between users, namely FilmTrust, CiaoDVD, Ciao-280k, Flixster and Epinions.

• Flixster2 : is a social rating dataset crawled by Jamali and Ester [START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF] from the flixster.com website. The latter is a social movie website, where users can watch, buy, share, rate and review movies. Each user can create his/her own social network by adding users into his/her friend list.

• FilmTrust3 : is a dataset crawled by Guo et al [START_REF] Guo | A novel bayesian similarity measure for recommender systems[END_REF] from the FilmTrust website. FilmTrust, as Flixster, is a movie rating and sharing community. Unlike the Flixster datasets, the social interactions between users are directed in FilmTrust.

• Ciao-280k4 : this dataset is crawled by Tang et al [START_REF] Tang | mtrust: discerning multi-faceted trust in a connected world[END_REF] from the product review website Ciao (ciao.co.uk). In the above site users can rate and review products as well as add users to their trust network.

• CiaoDVD 3 : is crawled by Guo et al [START_REF] Guo | Etaf: An extended trust antecedents framework for trust prediction[END_REF] from the Ciao site from the category of DVDs.

• Epinions 4 : is crawled from the Epinions website (epinions.com). As Ciao, Epinions is a consumer review site where users can rate and review products, and add members to their trust list.

The characteristics of the above datasets are reported in Table 3.1. The trust links, in the social network, are directed, while friendship are undirected.

Evaluation Metrics

Evaluating CF approaches still remains a challenging task. In our experiments we adopt a commonly used approach to evaluate such systems, that consists in assessing the recommendation accuracy on a set of held-out items-the test set. To this end, we retain four widely used measures, from information retrieval, namely the Normalized Discount Cumulative Gain (nDCG), Mean Reciprocal Rank (MRR), Precision@k (Prec@k) and Recall@k (Rec@k),

where k is the number of items in the recommendation list.

• MRR: The Reciprocal Rank (RR) for a recommendation list is the multiplicative inverse of the rank of the first "good" item. The mean reciprocal rank is the average of the RR's of all the recommendation lists.

MRR = 1 n ∑ i 1 rank i
where n is the number of users who receive recommendations, i.e. the number of recommendation lists, and rank i is the rank of the first correct item in the recommendation list of user i. Intuitively, the RR measures how far a user should go in the recommendation list to find a good item.

• nDCG5 : the DCG is used to measure the gain of each item relative to its position in a ranked list of items. Formally the DCG for a user i is given by

DCG i = ∑ j∈D i 1 log (rank j + 1)
where D i denotes the set of held-out items for user i, and rank j is the rank of item j. The normalized DCG i is given by

nDCG i = DCG i idealDCG i
where the idealDCG i is the best achievable DCG i , i.e. the value of the measure if the ranking was perfect. The nDCG is high if the most relevant items appear early in the ranked list. To evaluate an entire model we compute the average nDCG over all users: nDCG = 1 n ∑ i nDCG i . • Precision@k: for each user the Precision@k denotes the proportion of good items in his/her top-k recommendation list. To evaluate an entire CF system we compute the average Precision@k over all users.

• Recall@k the Recall@k for a user is the proportion of good items, in the user's top-k recommendation list, from the number of relevant held-out items for that user. As for the above measures, we can compute the average Recall@k over all users, to evaluate an entire model.

The nDCG measures the raking quality of a model, while Precision@k and Recall@k assess the quality of a user's top-k recommendation list. All the above measures vary from 0.0 to 1.0, the higher these measures, the better is the recommendation quality.

Notice that we do not consider prediction metrics, such as MAE and RMSE, in our experiments. As it has been already established by previous works [START_REF] Cremonesi | Performance of recommender algorithms on top-n recommendation tasks[END_REF][START_REF] Amatriain | Workshop on recommendation utility evaluation: beyond rmse-rue 2012[END_REF][START_REF] Loiacono | An analysis of the 2014 recsys challenge[END_REF][START_REF] Chaney | A probabilistic model for using social networks in personalized item recommendation[END_REF], low MAE and RMSE do not necessarily equate to best user satisfaction. As emphasized in [START_REF] Cremonesi | Performance of recommender algorithms on top-n recommendation tasks[END_REF][START_REF] Amatriain | Workshop on recommendation utility evaluation: beyond rmse-rue 2012[END_REF], the purpose of a CF system is to provide users with a set of relevant items, as a ranked list. In most commercial systems, users do not receive the predicted rating values, but rather lists of few selected items and ordered according to these values. Thus, the task of item recommendation is by nature a ranking problem. It is therefore more adequate to evaluate CF systems according to the quality of lists of items they recommend. Furthermore, in our case each approach makes predictions in its own range. For instance our method normalizes data so that it lies on a unit hypersphere, some retained competing methods map the original ratings to the interval [0,1]. So, it is not consistent to compare theses approaches in terms of prediction accuracy, by using measures such as MAE and RMSE which are strongly sensitive to the range in which the predicted ratings lie.

Experimental Settings

In our experiments we adopt the 5-fold cross validation strategy. Each dataset was randomly split into five folds. At each run four folds-80% of data-are used for training and the remaining fold is used for testing. On each dataset we perform five runs in order to test all folds. The average performance over the five runs is reported as the final result.

In order for comparisons to be fair and assess the impact of the social network information, we use the same random parameters Θ 0 to initialize both Soc-movMF and movMF, in all our experiments.

Our approach Soc-movMF and the traditional movMF, require as an input the number of clusters g which is analogous the number of latent factors k in matrix factorization-based approaches. The number of latent factors k, in the retained baselines, is usually set to 5 or 10 in previous works. In our experiments we found that the different baselines achieve better performances with k = 5 in all most all situations, we choose therefore k = 5 for all MF-based approaches. Concerning the number of clusters, we empirically found that both our approach and movMF provide high performances with a small number of clusters-usually g ≤ 10. Thus, for fairness purpose, and due to the analogy between g and k, we set g = 5 in all our experiments. Nevertheless, we illustrates the impact of g in our experiments.

Another input required by all approaches including the proposed one and competing methods, is the regularization parameter λ . In our case we set this parameter to 1 so as to give equal importance to both the preference and social information. The impact of λ is, however, illustrated in our experiments. The MF-based methods considered here often require several regularization parameters that are usually set to λ = 0.001. The other settings for the regularization parameters, determined either by our experiments or by previous works [START_REF] Guo | Trustsvd: Collaborative filtering with both the explicit and implicit influence of user trust and of item ratings[END_REF], are as follows: TrustMF and socialMF λ T = 1.0, SoRec λ c = 0.001 for Flixster and 1.0 for the others, SoReg β = 1.0 for Flixster and 0.1 for the others, RSTE α = 0.4, TrustSVD λ t = 0.9, 1.0, 1.0, 0.5, 0.5 and λ = 1.2, 0.5, 0.5, 0.9, 0.8 for FilmTrust, CiaoDVD, Ciao-280k, Epinions and Flixster, respectively.

Empirical results and discussion

The average performances of each approach over the different datasets are reported in Table 3.2. In order to ease interpretation, Figures 3.3 to 3.6 provide another representation of the results reported in Table 3.2. As these results show clearly, the proposed Soc-movMF performs substantially better than all competing methods, over all datasets. Note that even a small improvement in nDCG may result in an important improvement in terms of the other recommendation quality measures, this is due to the log factor in nDCG.

Beyond the fact that the proposed approach outperforms competing methods, several questions still deserve to be asked.

Is it beneficial to model CF data as directional data distributed on the surface of a unit-hypersphere?

We observe that even if the traditional vMF-based model movMF does not exploit the social interactions among users, it is superior to the other competing methods in almost all situations, except on Flixster where SoReg offer the best performance among the competing methods. This provides strong empirical support for the advantage of leveraging the intrinsic directional properties of CF data. What is the impact of the social component of Soc-movMF? Recall that movMF arises as a special case from Soc-movMF when λ = 0, i.e. movMF is exactly the Soc-movMF without the social component. Column "Improve", in Table 3.2, shows that the proposed Soc-movMF noticeably improves the performances of movMF. This constitutes empirical evidence that accounting for social interactions among users helps to improve the recommendation quality. Why does the improvement rate, in the recommendation quality, differ substantially from one dataset to another?

The improvement rate on Flixster is significantly more important than on the other datasets, while the improvement on FilmTrust is quite low. We believe that this behaviour is due to the characteristics of the different datasets in terms of the number of observed ratings and social relations per user. In Figure 3.7 we report the proportion of cold start users 6 , who have very few ratings (resp., social-relations), five or fewer, in the user-item matrix (resp., social network). From Figure 3.7 we note that Flixster exhibits different characteristics in comparison to the other datasets. In fact, in Flixster, while most users-more than 50%-are cold start users in the user-item matrix, only few are cold start in the social network as opposed to the other datasets. This suggests that the social interactions in Flixster play a key role in handling the cold start users in the preference matrix, which allowed the Soc-movMF to improve the performances of movMF by a noticeable amount. In FilmTrust, we note only few cold start users in the preference matrix, against a lot of cold start users-more than 90%in the social network. Hence, most information in FilmTrust is contained in the user-item matrix, which may explain the low improvement in the performances of Soc-movMF relative to movMF. In the Epinions and CiaoDVD datasets we observe a high rate of cold start users in both the user-item matrix and the social network. Although most users expressed only few social interactions in the above two, the social information seems to play an important role, in that it allowed Soc-movMF to reach better performances than movMF. We believe that this behaviour may be due to the propagation of social interactions in Soc-movMF. Finally, the high performances of Soc-movMF, relative to its traditional variant movMF, on Ciao-280k suggest that even when only few users are cold start users, in the preference matrix, the social information is still of great interest to improve the recommendations.

To sum up, the results from Table 3.2,Figures 3.3 to 3.6 and Figure 3.7 suggest that not only the social information but also the directional properties of CF data should be taken into account to improve the recommendations. It seems better to model collaborative filtering data as directional data. Moreover, accounting for social interactions among users seems to be of particular interest when most users expressed very few ratings, i.e. the cold start users. To investigate the latter result further, in the next section we conduct experiments in which we benchmark the social Soc-movMF against the traditional movMF on cold start users.

movMFs vs Social-movMFs on cold start users

Cold start is a major challenge in CF, because in many real-world applications most users express very few ratings. In order to complete the results from the previous section, we shall investigate in greater depth the impact of the social information on cold start users, who expressed very few ratings. We conduct, therefore, another series of experiments in which we benchmark our social model Soc-movMF against the traditional movMF model, on cold start users. From Table 3.3 we can clearly observe that Soc-movMF still provides a high recommendation accuracy and substantially improves the performances of movMF. More interestingly, on the FilmTrust, Ciao-280k and Flixster data sets we observe a greater improvement, in the performance of Soc-movMF relative to movMF, compared with Table 3.2 (see column "Improve"). In order to understand why the improvement rate may differ substantially from one dataset to another, we report in Figure 3.8 the distribution of out degree 3.3 and Figure 3.8, we observe that the improvement rate in the performances of Soc-movMF, relative to movMF, goes from high to low as the distribution of the number of social interactions, per cold start user, decreases. For instance on Flixster, we observe that most cold start users expressed more than five social relationships, which may explain the strong superiority of social Soc-movMF in comparison to movMF. These results, constitute empirical evidence, that accounting for social interactions among users is of great interest and helps to alleviate the cold start issue.

Impact of the number of clusters and the regularization

In the sequel we investigate the impact of the two parameters g and λ on the performances of Soc-movMF. We illustrate their behavior on the FilmTrust, CiaoDVD, Ciao-280k and Epinions datasets in terms of nDCG. In Figure 3.9 the values of nDCG are depicted as a function of the number of clusters g, over the different datasets. We observe that a small number of clusters (< 10) seems to be enough, in order for Soc-movMF to reach high recommendation performances. Figure 3.10 illustrates the impact of the regularization parameter λ . As it is clear from this figure, Soc-movMF is highly stable relative to the variations of the regularization parameter λ , and seems to provide slightly better performances with a small value of λ , which facilitates the setting of this parameter.

Conclusion and perspectives

We proposed Social-movMFs, a novel model that accounts for social network information to improve item recommendations. Social-movMFs simultaneously seeks groups of users who tend to express similar preferences and brings the distributions, over clusters, of socially connected users closer to each other so as to capture the influences between friends. While existing approaches to social CF are based on popular modelling assumptions, such as Gaussian, our approach builds on the vMF distribution which arises naturally for directional data distributed on the surface of a unit-hypersphere. From our experiments, it seems that CF datasets possess intrinsic directional characteristics that are consistent with the vMF modeling assumption. Moreover, incorporating social information into a vMF mixture model turns out to be very beneficial and makes it possible to alleviate the sparsity related issues, such as the cold start problem.

In terms of performance the proposed model improves noticeably the recommendation accuracy of several strong competing methods, including the traditional movMF and several social CF models, as illustrated in our experiments. Our empirical results suggest that, for making good recommendations, not only the social interactions among users should be taken into account, but also the intrinsic "directional" properties of CF data.

The good performances of Social-movMFs motivates future investigations, that may include incorporating time into Social-movMFs, and building online variants so as to handle the frequent changes in social CF: new ratings, social relations, items and users.

Another possible future work is to extend Social-movMFs to the context of co-clustering, by relying on the block vMF mixture model, described in Chapter 5, so as to partition the sets of users and items simultaneously. Such an extension would allow us to alleviate the

Introduction

In general terms co-clustering [START_REF] Govaert | Co-Clustering[END_REF]-also denoted as block clustering [START_REF] Govaert | Clustering with block mixture models[END_REF], bi-clustering [START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF], direct clustering [START_REF] Hartigan | Direct clustering of a data matrix[END_REF], two-way clustering [START_REF] Bock | Two-way clustering for contingency tables: Maximizing a dependence measure[END_REF], two-mode clustering [START_REF] Van Dijk | Two-mode clustering methods: a structured overview[END_REF] or simultaneous clustering [START_REF] Govaert | Simultaneous clustering of rows and columns[END_REF]-is an important extension of traditional one-sided clustering, that addresses the problem of simultaneous clustering of both dimensions of a data matrix. More precisely, co-clustering seeks "homogeneous" submatrices, namely co-clusters (or blocks)-see Definition 1-where rows and columns follow some consistent patterns.

Definition 1 Let X be a data matrix of size n × d where I is the set of n rows, and J the set of d columns. A co-cluster (or a block) hℓ is a couple (I h , J ℓ ) (I h ⊆ I, J ℓ ⊆ J ), i.e., each co-cluster corresponds to a sub-matrix I h × J ℓ .

Co-clustering exhibits several practical advantages making it possible to meet the growing needs in several current areas of interest, in terms of effectiveness, scalability and visualization. Below, we summarize some key properties of co-clustering:

-By intertwining row clustering and column clustering at each stage, co-clustering performs an implicitly adaptive dimensionality reduction, which is imperative to deal with high dimensional sparse data. This makes it possible (i) to develop efficient algorithms with a dramatically smaller number of parameters (ii) to reduce the original data matrix into a much simpler and condensed data matrix with the same structure.

-Co-clustering exploits the inherent duality between rows and columns of data matrices making it possible to enhance the clustering along both dimensions, by exploiting the latent column structure during row assignments and vice versa.

-Far from adding complexity, co-clustering is more informative than one-sided clustering, and produces meaningful clusters. In the case of document-term matrices, for example, co-clustering annotates sets of documents automatically by clusters of words.

Binary table reorganized according to the row and column partitions

One of the earliest explicit formulation of co-clustering dates back to [START_REF] Hartigan | Direct clustering of a data matrix[END_REF][START_REF] Hartigan | Clustering Algorithms[END_REF] under the name of "direct clustering". In the former work, various cluster models and structures were introduced, and a stepwise divisive strategy was proposed that simultaneously seeks hierarchical row and column clustering. The proposed algorithm, initially treats the whole matrix as a block, then at each step a selected block is splited into two sub-blocks, i.e, either by rows or columns, so that the reduction of the within co-cluster variance is maximized. This divisive process is repeated until no significant reduction of the within co-cluster variance is observed. Since this seminal work, co-clustering has received extensive attention in various application domains, such as text mining (Hofmann et al., 1999;[START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF]Dhillon et al., 2003;[START_REF] Long | Co-clustering by block value decomposition[END_REF][START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF][START_REF] Ailem | Co-clustering document-term matrices by direct maximization of graph modularity[END_REF] to group words and documents simultaneously, bioinformatics [START_REF] Cheng | Biclustering of expression data[END_REF][START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF][START_REF] Cho | Minimum sum-squared residue co-clustering of gene expression data[END_REF][START_REF] Gupta | Mib: Using mutual information for biclustering gene expression data[END_REF][START_REF] Hanczar | Ensemble methods for biclustering tasks[END_REF] to cluster genes and experimental conditions simultaneously, web mining [START_REF] Xu | Co-clustering analysis of weblogs using bipartite spectral projection approach[END_REF][START_REF] Charrad | Block clustering for web pages categorization[END_REF], collaborative filtering (Hofmann and Puzicha, 1999;[START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF][START_REF] Deodhar | Scoal: a framework for simultaneous co-clustering and learning from complex data[END_REF][START_REF] Khoshneshin | Incremental collaborative filtering via evolutionary coclustering[END_REF] to group users and items simultaneously, affiliation networks [START_REF] Zanghi | Fast online graph clustering via erdős-rényi mixture[END_REF][START_REF] Zanghi | Clustering based on random graph model embedding vertex features[END_REF] or evolving graphs [START_REF] Guigourès | Discovering patterns in time-varying graphs: a triclustering approach[END_REF], giving rise to a large variety of co-clustering methods.

Metric-based co-clustering

Metric approaches to co-clustering are based on the intuition that there is an underlying block structure in the original data, that can be exploited to summarize it by a smaller data matrix with the same structure. To this end, metric co-clustering methods consist in optimizing a criterion that measures the difference between the original data matrix and its compressed representation-summary-due to co-clustering. One of the most popular co-clustering criterion is the least-squares, that is suitable for continuous data [START_REF] Govaert | Simultaneous clustering of rows and columns[END_REF], given as follows:

W (C, z, w) = ∑ i, j,h,ℓ z ih w jℓ (x i j -c hℓ ) 2 (4.1)
where z and w denote respectively the row and column partitions, C = (c hℓ ) is the compressed representation of the original data matrix X due to co-clustering, i.e, C is a matrix of size g × m and c hℓ ∈ R is the representative of each block or co-cluster. The co-clustering in this context is to find z, w and C minimizing criterion (4.1). The above optimization problem is intractable, however, a locally optimal solution can be obtained, for instance, by using the double k-means procedure-so called because of its relation to the k-means algorithmdescribed below. Starting from a random initial position, the double k-means algorithm alternates the following optimization steps until convergence:

1. Row assignment. Compute z given w and C: z i = arg min h ′ ∑ jℓ w jℓ (x i jx hℓ ) 2 , ∀i.

2. Column assignment. Compute w given z and C: w j = arg min ℓ ′ ∑ ih z ih (x i jx hℓ ) 2 , ∀ j.

3.

Update co-clusters. Compute C given z and w: c hℓ = ∑ i j z ih w jℓ x i j z .h w .ℓ , ∀h, ℓ.

where z .h and w .ℓ denote respectively the cardinality of row cluster h and column cluster ℓ.

A large class of co-clustering algorithms are based on the above least-squares criterion, or its variants, and use the principle of double k-means to solve the corresponding optimization problem. Among such algorithms we can cite, for instance, the CROEUC algorithm (Govaert, 1995), the minimum sum-squared residue co-clustering algorithms, tailored for gene expression data, proposed in [START_REF] Cho | Minimum sum-squared residue co-clustering of gene expression data[END_REF] and the co-clustering algorithms, based on non-negative matrix tri-factorization, proposed by Labiod and Nadif (2011a).

Another important class of co-clustering methods are those based on information measures such the chi-squared statistic and mutual information. This category of co-clustering algorithms is, in particular, appropriate for dyadic data-contingency tables-such as document-term matrices. In this context we can mention two notable approaches, namely the CROKI2 [START_REF] Govaert | Simultaneous clustering of rows and columns[END_REF] and the information theoretic co-clustering (ITCC) (Dhillon et al., 2003) algorithms, based respectively on the chi-squared statistic and mutual information. Both the above approaches aim to minimize the loss in information, relative to the corresponding information measure, due to co-clustering. For more details and theoretical connections between the above two, please refer to the book of [START_REF] Govaert | Co-Clustering[END_REF].

Motivated by metric approaches to co-clustering, [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximations[END_REF] posed the coclustering as a matrix approximation problem, and they developed a general framework that allows the use of any Bregman divergence to measure the approximation error and, thereby, the quality of co-clustering. For instance, under some constraints and when the the Bregman divergence is the Kullback-Leibler divergence this corresponds to the information theoretic co-clustering (Dhillon et al., 2003), similarly, when the Bregman divergence is the squared euclidean distance this corresponds to the double k-means co-clustering algorithm presented above.

Graph-based co-clustering

In the graph-based approach data are modeled by a bipartite graph, from graph theory, with two sets of vertices I and J denoting respectively rows and columns. Each row/column is represented by a vertex, the two sets of vertices are connected by a set of undirected edges, as illustrated in Figure 4.2.

Let X denote the original data matrix, the adjacency matrix of the corresponding bipartite graph takes the following form:

A = 0 X X T 0 (4.2)
Based on such a graph modelling, the co-clustering is to seek g clusters of densely connected nodes, by minimizing the sum of the weights of the edges between clusters and maximizing the sum of the weights of the edges within clusters.

B1 B2 B3 B4 B5 B6 B7 A1 1 1 1 0 0 1 1 A2 1 1 0 0 0 1 1 A3 0 0 0 1 1 1 1 A4 0 0 0 1 0 1 1 A1 A2 A3 A4 B1 B2 B3 B4 B5 B6 B7 Fig. 4.

Binary data and its associated bipartite graph

In this context [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF] proposed the spectral co-clustering algorithm, he presented a bipartite graph modelling for a document-word collection, then he proposed to find an optimal partitioning of the document-word bipartite graph, into g row and column clusters, by using a spectral relaxation for the minimum cut graph partitioning problem. Labiod and Nadif (2011b) proposed a normalized generalized version of the modularity measure [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] which is popular in network analysis. Then, they developed a spectral co-clustering algorithm maximizing the proposed criterion, for simultaneous clustering of binary and categorical data. The authors, shown that the proposed algorithm performs well in the context of text document clustering, and they studied the problem of assessing the number of co-clusters by using the proposed criterion. More recently, [START_REF] Ailem | Co-clustering document-term matrices by direct maximization of graph modularity[END_REF] proposed a novel co-clustering algorithm maximizing the graph modularity. More precisely, they proposed an efficient k-means like alternating optimization scheme as a direct way to maximize the graph modularity, without eigenvector computation-a step which is computationally prohibitive. As in (Labiod and Nadif, 2011b), [START_REF] Ailem | Co-clustering document-term matrices by direct maximization of graph modularity[END_REF] illustrated how the modularity measure can be exploited to assess the number of clusters.

Model-based co-clustering

The generative mixture model approach [START_REF] Govaert | Co-Clustering[END_REF]) is a very powerful technique to design co-clustering algorithms. It offers more flexibility, can incorporate different domain knowledge, allow us to model different types of data and uncover various specific cluster structures. Furthermore, the generative model-based approach provides theoretical justifications behind a large class of metric-based co-clustering algorithms.

In this context, most of co-clustering methods are based on the Latent Block Model (LBM) [START_REF] Govaert | Clustering with block mixture models[END_REF]. Intuitively, the LBM assumes that a data matrix is composed of co-clusters, each of which is characterized by an underlying probability distribution called a component. Each co-cluster is a set of real values x i j ∈ R drawn from some Putting the co-clustering problem under the LBM framework involves the choice of (i) the number of row and column clusters, (ii) an adequate probability distribution according to the type of data, (iii) a method to fit the model parameters. Formally, the probability density function of the LBM takes the following form:

f (X|Θ) = ∑ z,w n ∏ i=1 α z i d ∏ j=1 ρ w j ∏ i, j ϕ(x i j |θ z i w j ) . (4.3)
where the notation ∑ z,w stands for the sum over all possible row and column partitions, X = (x i j ) denotes a data matrix of size n × d, z i ∈ {1, . . . , g} and w j ∈ {1, . . . , m} denote the row and column cluster labels, Θ = {α, ρ, θ 11 , . . . , θ gm } is the set of parameters, such that α = {α 1 , . . . , α g } and ρ = {ρ 1 , . . . , ρ m } represent respectively the row and column mixing proportions, θ hℓ is the parameter of the probability distribution ϕ characterizing co-cluster hℓ. The LBM assumes that (i) the univariate random variable x i j are independent given z and w, (ii) the row and column partitions-treated as latent variables-are independent, i.e.

p(z, w) = p(z)p(w). Its graphical model is depicted in Figure 4.3, and the corresponding generative process is as follows:

1. For each row i: choose a cluster label z i = h ∼ Multinomial(α 1 , . . . , α g ).

2. For each column j: choose a cluster label w j = ℓ ∼ Multinomial(ρ 1 , . . . , ρ m ).

3. For each entry (i, j) Choose a value x i j ∼ ϕ(x i j |θ z i w j ).

Co-clustering under the LBM is to reverse the above generative process and fit the model parameters Θ to the observed data X. To this end, two main approaches can be considered, namely the Maximum Likelihood (ML) approach-involving the Expectation-Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF]-and the Classification ML (CML) approach [START_REF] Scott | Clustering methods based on likelihood ratio criteria[END_REF][START_REF] Symons | Clustering criteria and multivariate normal mixtures[END_REF]-using the Classification EM (CEM) algorithm [START_REF] Celeux | A classification em algorithm for clustering and two stochastic versions[END_REF])-, yielding respectively to soft and hard co-clustering. Regarding the type of data several LBM-based co-clustering algorithms have been proposed. We can cite the co-clustering of binary data based on the Bernoulli LBM (Govaert andNadif, 2003, 2008), the Poisson LBM-based co-clustering [START_REF] Govaert | Latent block model for contingency table[END_REF] dealing with contingency tables. In the above works, the authors considered both the ML and CML approaches to estimate the model parameters. Under the ML approach, the authors emphasized the difficulty due to the coupling of the missing variables z and w, and derived an efficient variational EM algorithm for inference and parameter estimation.

Under a Bayesian formulation, the latent block model, or its variants, have been also investigated to address specific problems in graph clustering [START_REF] Latouche | Bayesian methods for graph clustering[END_REF][START_REF] Daudin | A mixture model for random graphs[END_REF][START_REF] Corneli | Exact icl maximization in a non-stationary time extension of the latent block model for dynamic networks[END_REF] or to raised challenges such as the model selection or empty classes [START_REF] Van Dijk | Two-mode clustering methods: a structured overview[END_REF][START_REF] Lomet | Model selection for gaussian latent block clustering with the integrated classification likelihood[END_REF][START_REF] Keribin | Estimation and selection for the latent block model on categorical data[END_REF]. Recently, Wyse and Friel (2012) considered a collapsed Bayesian extension of the Bernoulli LBM [START_REF] Govaert | Block clustering with bernoulli mixture models: Comparison of different approaches[END_REF], which is able to learn the number of row and column clusters. We can also mention the Bayesian co-clustering model [START_REF] Shan | Bayesian co-clustering[END_REF], which can be viewed as an extension of the latent block model where each row/column may belong to multiple cluster. For more details on the LBM and generative model-based co-clustering approaches the reader can refer to the book of [START_REF] Govaert | Co-Clustering[END_REF].

One notable advantage of model-based co-clustering approaches is that they provide the theoretical justifications behind a large class of metric-based co-clustering algorithms. For instance, [START_REF] Govaert | Co-Clustering[END_REF] demonstrated that under some restrictive constraints and when the contingency table is converted to a joint probability distribution, the hard Poisson LBM co-clustering algorithm is equivalent to the well known information theoretic coclustering (ITCC) (Dhillon et al., 2003). In the same spirit, the double k-means co-clustering can be derived as a special case from the Gaussian block model [START_REF] Nadif | Model-based co-clustering for continuous data[END_REF][START_REF] Govaert | Co-Clustering[END_REF].

Non-Negative Matrix Factorization-based approaches

An other variety of co-clustering algorithms are those based on non-negative matrix factorization (NMF). Even if co-clustering is not the purpose of NMF, this approach has recently received a lot of interest for co-clustering positive matrices, such as document-term data arising in text mining. Given a positive data matrix X, NMF-based co-clustering algorithms seek a three factor decomposition ZSW T of X, by optimizing the following criterion min Z>0, S>0, W>0 ∥X -ZSW T ∥ 2 (4.4) where ∥.∥ is the Frobenius norm, Z and W are two positive matrices containing row and column cluster memberships, respectively, and S is a positive reduced form-a summary-of X due to co-clustering. Among NMF based co-clustering methods we can cite the nonnegative block value decomposition NBVD by [START_REF] Long | Co-clustering by block value decomposition[END_REF], who derived an alternating algorithm based on a set of multiplicative update rules to optimize criterion (4.4). In the same spirit [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF]; [START_REF] Yoo | Orthogonal nonnegative matrix tri-factorization for co-clustering: Multiplicative updates on stiefel manifolds[END_REF] addressed the problem of simultaneous clustering, by developing two variant of orthogonal three factors NMF, namely ONM3F [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF] and ONMTF [START_REF] Yoo | Orthogonal nonnegative matrix tri-factorization for co-clustering: Multiplicative updates on stiefel manifolds[END_REF]. The difference with [START_REF] Long | Co-clustering by block value decomposition[END_REF] is that in [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF][START_REF] Yoo | Orthogonal nonnegative matrix tri-factorization for co-clustering: Multiplicative updates on stiefel manifolds[END_REF] the authors imposed orthogonality constraints on row and column cluster indicator factors, i.e. Z and W, and they emphasized the importance of such constraints in the clustering context. We can also cite the work of Labiod and Nadif (2011a) in which two NMF-based co-clustering algorithms have been proposed. Contrary to the previous works, Labiod and Nadif (2011a) placed the co-clustering aim under the NMF formulation at the beginning.

Conclusion

In this chapter, we introduced the concept of co-clustering, outlined the main approaches to co-clustering and presented some advantages of co-clustering over traditional one-sided clustering when dealing with high dimensional sparse data. Although co-clustering approaches have been proven to be very effective in the context of high dimensionality and sparsity, they still exhibit some limitations. For instance, existing co-clustering methods are based on popular assumptions such as Gaussian, Multinomial, Poisson or Bernoulli, which are inadequate for directional data distributed on the surface of a unit hypersphere (or equivalently L 2 normalized data). However, as it has been emphasized in this thesis and some previous works, some high dimensional sparse data sets, such as text, posses intrinsic directional properties and are, therefore, better modeled as directional data. So far, we highlighted the benefits of both the co-clustering and L 2 normalization in the context of high dimensional sparse data, so it seems natural to question whether it is possible to reap the advantages of both co-clustering and L 2 normalization, simultaneously. In the next chapters, we provide an answer for the above question; we design a general co-clustering model that is well suited for directional data lying on a unit-hypersphere. Our choice for the model-based approach is motivated by its flexibility and strong theoretical foundations. The proposed model is parsimonious and gives rise to several scalable and effective co-clustering algorithms.

Chapter 5 Von Mises-Fisher based Co-clustering

In the context of high dimensional sparse data, co-clustering turns out to be more beneficial than one-sided clustering even if one is interested in clustering along one dimension, only.

As highlighted in the previous chapters and the beginning of this thesis, some datasets, such as document-term matrices, exhibit directional characteristics and the L 2 normalization of such data so that it lies on the surface of a unit hypersphere is necessary. Popular co-clustering assumptions such as Gaussian or Multinomial are not adequate for directional data. This chapter presents a novel co-clustering model based on a mixture of von Mises-Fisher distributions, which is well-suited for modelling directional data lying on a unit hypersphere. The proposed model successfully integrates a directional measurecosine similarity-into a co-clustering framework. It is parsimonious and able to reveal a block diagonal structure as well as a good partitioning of rows and columns. By setting the estimate of the model parameters under the maximum likelihood (ML) and the classification ML (CML) approaches, we derive six novel co-clustering algorithms, namely soft, hard, stochastic and simulated annealing variants. Extensive experiments on several simulated and real-world datasets confirm the advantage of our approach and demonstrate the effectiveness of our algorithms.

Introduction

The mixture of von Mises-Fisher (vMF) distributions (Banerjee et al., 2005b), introduced in chapter 3, turn out to be a wise choice when dealing with high dimensional sparse data. In fact, this model, noted movMFs, is one of the most appropriate model for clustering high dimensional sparse data, such as document-term matrices arising in text mining. In this domain, it has been empirically demonstrated that vMF-based clustering methods perform better than several existing approaches, see for instance [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF][START_REF] Gopal | Von mises-fisher clustering models[END_REF]. From a statistical point of view this means that document-term matrices possess directional characteristics [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF]. Existing vMF-based clustering models, however, focus only on clustering along one dimension, i.e, either row or column clustering. Hence, they do not exploit the inherent duality between rows and columns of data matrices. In the clustering context, it turns out that the exploitation of this duality during the clustering process, presents a real advantage to improve the quality of clustering and alleviate the aforementioned difficulties related to high dimensionality and sparsity. This, can be achieved by using a new form of clustering that simultaneously partitions rows and columns of a data matrix, namely the co-clustering introduced in the previous chapter.

In this chapter, we concentrate on the practical problem of co-clustering document-term matrices arising in text mining. Despite the importance of modelling text data as directional data, existing co-clustering approaches are based on popular modelling assumptions such as Gaussian or Multinomial, which are inadequate to model L 2 normalized data distributed on the surface of a unit hypersphere. Thus, it seems natural to question whether it is possible to get the best of both directional modelling and co-clustering, within the same model. In this chapter, we provide an answer for the above question. We present a general co-clustering framework based on a mixture of von Mises-Fisher distributions. Our model inherits the advantages of both the co-clustering and the modelling assumption of the vMF distribution. Contrary to existing co-clustering methods, it exploits the directional characteristics exhibited by some datasets, such as document-term matrices.

To our knowledge, the work that we present, is the first that addresses the problem of co-clustering with a mixture of vMF distributions. The key contributions of this chapter are the following:

-We present a novel model for co-clustering high dimensional sparse matrices. This model is based the vMF distribution and successfully integrates a directional measurecosine similarity-into a co-clustering framework. It is therefore more suitable, than existing co-clustering models, for data exhibiting directional characteristics such as document-term matrices.

-We provide theoretical connections between our model and existing ones, namely the mixture of von Mises-Fisher distributions (Banerjee et al., 2005b), the Gaussian [START_REF] Banfield | Model-based gaussian and non-gaussian clustering[END_REF] and the block Gaussian mixture models [START_REF] Nadif | Model-based co-clustering for continuous data[END_REF].

-Setting the estimate of the model parameters under the maximum likelihood (ML) approach, we formulate various co-clustering algorithms a soft, hard, stochastic and two simulated annealing variants. Furthermore, by enforcing some constraints on the concentration parameters and cluster proportions we derive a novel efficient nonparametric co-clustering algorithm. The latter can be viewed as an extension of the well known spherical k-means algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF] to the context of co-clustering.

-In order to show the benefits of our approach for the analysis of high dimensional sparse data, we conducted extensive experiments on numerous synthetic and real-world datasets, on which we benchmark our algorithms against several strong baselines.

-The dimensionality reduction property of the proposed model alleviates the problem of high concentration parameters κ involved in Bessel functions, which induces over and under flows, a well known difficulty in classical vMF based models (Banerjee et al., 2005b). We validate this important result (i) theoretically by a theorem guaranteeing that our model leads to a concentration parameter that is less or equal to that of movMFs, for each cluster, (ii) empirically by demonstrating that our algorithms yield substantially lower concentration parameters than movMFs-based algorithms, on realworld datasets.

Related work

Most of the earlier works using the vMF distribution focused on low dimensional data, i.e, using 2-or 3-dimensional vMF distributions [START_REF] Mclachlan | Finite mixture models[END_REF], due to difficulties related to the estimation of the concentration parameter κ, that involves the inversion of ratios of Bessel functions. In the context of clustering and high dimensionality, Banerjee et al. (2005b) proposed algorithms derived from a mixture of vMF distributions movMFs.

They used an EM-based solution to estimate the parameters of their model and proposed an accurate approximation to estimate the concentration parameter κ for a high dimensional vMF distribution. Since this contribution, different vMF based models for clustering high dimensional sparse data have been proposed. For instance [START_REF] Reisinger | Spherical topic models[END_REF] proposed a spherical topic model based on a mixture of vMF distributions, which is highly inspired from the Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF]. More recently, for text data clustering, [START_REF] Gopal | Von mises-fisher clustering models[END_REF] proposed a full Bayesian formulation of movMFs and developed two novel variants of movMFs, namely hierarchical and temporal. [START_REF] Le | Semantic visualization for spherical representation[END_REF] proposed a vMF-based model for the semantic visualization of spherical data. In the previous chapter we proposed a vMF model that accounts for the social interactions between users to alleviate the sparsity related issues in CF and improve recommendations. All these works, however, focused only on one-sided clustering. Hence, unlike existing vMF-based models, the model proposed in this chapter acts simultaneously on both dimensions of data matrices, and thereby exhibits the advantages of co-clustering, such as the exploitation of the inherent duality between the rows and columns of data matrices, that makes it possible to improve clustering performances. Specifically, our model seeks a diagonal structure by co-clustering, meaning that rows and columns have the same number of clusters, and after a proper reorganisation of rows and columns we obtain a block diagonal structure, as illustrated in Figure 5.1.

In text mining, the domain on which we concentrate our experiments, a diagonal structure arises naturally in document-term matrices, as it has been demonstrated by several earlier works. For example, [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF] proposed the efficient spherical k-means algorithm which can be derived as a special case from a mixture of vMF distributions (Banerjee et al., 2005b), and they empirically demonstrated that documents are grouped together because they use similar words yielding a block diagonal structure. In (Dhillon et al., 2003) the well known information theoretic co-clustering algorithm was proposed, that seeks a more general block structure, i.e, not necessarily diagonal. However during the experiments on real world document-term matrices, the authors observed that some word clusters are highly indicative of individual document clusters inducing a block diagonal sub-structure, that captures the most useful information.

Among popular diagonal co-clustering, we can mention spectral approaches [START_REF] Dhillon | Co-clustering documents and words using bipartite spectral graph partitioning[END_REF]Labiod and Nadif, 2011b) and the block diagonal model for co-clustering binary data [START_REF] Li | A general model for clustering binary data[END_REF] or count data [START_REF] Ailem | Co-clustering document-term matrices by direct maximization of graph modularity[END_REF].

The diagonal assumption may seem restrictive, however, when dealing with high dimensional sparse data, such as document-term matrices, this assumption exhibits several advantages as opposed to a non-binding model:

-It makes it possible to develop more parsimonious models thereby more efficient algorithms, since we only focus on the most important co-clusters (diagonal ones).

-Unlike a general partionning by co-clustering, that treats similarly useful (relevant) and noisy (irrelevant) co-clusters, a diagonal co-clustering algorithm concentrates on the most relevant co-clusters therefore it is expected to achieve better results, since it implicitly ignores noisy co-clusters.

-Due to sparsity, a general co-clustering algorithm may result in a poor locally optimal solution. More precisely, a general co-clustering algorithm seeks "homogeneous" co-clusters and as all co-clusters are treated equally, the quality of co-clustering may be biased by co-clusters containing a majority of zero entries, that are homogeneous but not useful (or irrelevant). This difficulty increases with the number of co-clusters.

-In the context of document-term matrices, diagonal co-clustering has the advantage of producing directly interpretable document clusters. Let us assume a co-clustering of a document-term matrix into 20 document-and 20 word-clusters. A naive partitioning by co-clustering will produce 400 co-clusters, and it is left to the user to identify the most useful co-clusters so as to determine which document clusters should go with which term clusters, while a diagonal co-clustering will produce only 20 co-clusters that capture the most useful information.

A Mixture of von Mises-Fisher Distributions for Coclustering

Recall that the mixture of vMF distributions (movMFs) (Banerjee et al., 2005b), presented in chapter 3 (section 3.3.2), focuses solely on clustering along one dimension of a data matrix. Now, we propose a novel mixture of vMF distribution for co-clustering or simultaneous clustering of both dimensions of a data matrix. Following the results of [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], which state that the unit centroids produced by the spherical k-means algorithm-a restricted version of the soft-and hard-movMF clustering algorithms (Banerjee et al., 2005b)are localized in the feature space and tend towards orthonormality, we propose to capture and exploit this structure during the clustering process. More precisely, we assume some natural assumptions on the structure of centroids, i.e, orthonormality and homogeneity, at the beginning. To this end, we introduce a new parameter w (see Figure 5.2) that simultaneously guarantees the above assumptions and plays the role of a column partition. From a coclustering point of view, this is equivalent to assume that rows and columns have the same number of clusters and that each column cluster is associated or describes a single row cluster. Thus, inducing a block diagonal structure, see Figure 5.1. The generative process of this model is as follows:

1. Choose a component h ∼ Multinomial(α 1 , . . . , α g ).

2. Given µ h , κ h and w, generate data point

x i on S d-1 ∼ f h (x i |µ h , κ h , w). α z i κ z i x i µ z i n α z i κ z i x i µ z i w n Fig. 5.
2 Graphical models: left movMFs (Banerjee et al., 2005b), right dbmovMFs (proposed model).

Our model called dbmovMFs (diagonal block mixture of vMF distributions) seeks to partition simultaneously the set of rows I and columns J . Thereby it has the advantage of exploiting the duality between rows and columns of data matrices. The density function of dbmovMFs is given by:

f (x i |Θ) = ∑ h α h f h (x i |µ w h , κ w h , w), (5.1)
where the set of parameters Θ is now formed by µ w 1 ,. . ., µ w g , α 1 , . . . , α g , κ w 1 , . . . , κ w g and the column partition w, i.e, w j = h if the j th column belongs to the h th column cluster, that is associated with the h th row cluster. Notice that, the centroid and the concentration parameters µ w h , κ w h , respectively, depend on the column partition w. It follows from the orthonormality and homogeneity assumptions, respectively, that for each centroid µ w h : µ h j = 0 if w jh = 0, and µ h j = µ hh for all j such as w jh = 1. For instance, assuming a mixture of 3 vMF distributions, i.e, g = 3 and h, k = 1, 2, 3, each centroid µ w h ∈ S d-1 takes this form:

µ w h = (µ h1 , . . . , µ h1 , µ h2 , . . . , µ h2 , µ h3 , . . . , µ h3 ) ⊤ (5.2)
where µ hk is repeated w .h times; w .h denotes the cardinality of the h th column cluster. In addition, we have µ hk = 0 ∀k ̸ = h, leading implicitly to the orthonormality of centroids. Let X denotes a set of n randomly sampled data points x i on S d-1 according to (5.1). Using the row and column classification matrices Z and W, respectively, the complete data likelihood of X takes the following form:

L(W, µ, α, κ|X , Z) = ∏ i ∏ h α h c d (κ h ) × ∏ j (exp κ h µ hh x i j ) w jh z ih .
The corresponding complete data log-likelihood of X is given by:

L c (Θ|X , Z) = ∑ i,h z ih log α h + ∑ i,h z ih log(c d (κ h )) + ∑ i,h, j z ih w jh κ h µ hh x i j = ∑ h z .h log α h + ∑ h z .h log(c d (κ h )) + ∑ i,h z ih κ h µ hh ∑ j w jh x i j = ∑ h z .h log α h + ∑ h z .h log(c d (κ h )) + ∑ i,h
z ih κ h µ hh u ih (5.3) where u ih = ∑ j w jh x i j . This leads to

L c (Θ|X , Z) = ∑ h z .h log α h + ∑ h z .h log(c d (κ h )) + ∑ i,h
z ih y ih (5.4) where y ih = κ h µ hh u ih , and in the same manner, we can give another expression of L c (Θ|X , Z) in terms of column assignments as follows

∑ h z .h log α h + ∑ h z .h log(c d (κ h )) + ∑ j,h
w jh t jh (5.5) where t jh = κ h µ hh v h j , with v h j = ∑ i z ih x i j .

Connection to existing models

Assuming that the column partition w is fixed, the dbmovMFs model can be viewed as a classical movMFs (Banerjee et al., 2005b) where the mean directions vectors µ h , h = 1, . . . , g, take the form (5.2) described above. Moreover, we can establish connections with the Gaussian mixture model [START_REF] Banfield | Model-based gaussian and non-gaussian clustering[END_REF] and the block Gaussian mixture model [START_REF] Govaert | Co-Clustering[END_REF]. More precisely, using the equivalence between the vMF and the Gaussian distribution [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF] and assuming that w is fixed, it can be shown that dbmovMFs is equivalent to a mixture of Gaussian distributions of spherical form, i.e, the variance of the h th cluster is given by σ 2 h = ∥m w h ∥/κ h , m w h is the centroid of the corresponding Gaussian component and µ w h = m w h /∥m w h ∥. The latter model, is also equivalent to a diagonal version of the block Gaussian mixture model [START_REF] Govaert | Co-Clustering[END_REF], i.e, each Gaussian component is parameterized by the variance σ 2 h and mean vector m w h , described above.

Maximum Likelihood estimates and the EM b algorithm

To obtain the maximum likelihood estimates for the parameters Θ, we use the Generalized EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF][START_REF] Mclachlan | The EM algorithm and extensions[END_REF]. The E-step is reduced to compute the posterior probabilities defined by zih ∝ α

(t) h f h (x i |µ (t) h , κ (t)
h ). The M-step consists in estimating all parameters maximizing or increasing the expectation of the complete data log-likelihood (5.3), subject to the constraints ∑ h α h = 1, ∥µ w h ∥ 2 = ∑ j w jh µ 2 hh = 1 and κ h > 0. We obtain the following update formulas (see Appendix A.1).

ŵ jh ←      1, if h = arg max h ′ t jh ′ 0, otherwise. (5.6a) αh = ∑ i zih n , (5.6b) μhh = r w h ∥r w h ∥ = ± 1 √ ŵ.h where r w h = ∑ i, j zih ŵ jh x i j and ŵ.h = ∑ j ŵ jh (5.6c) κh ≈ rw h d -rw h 3 1 -rw h 2 where rw h = I d/2 ( κh ) I d/2-1 ( κh ) = ∥r w h ∥ z.h ŵ.h (5.6d)
where t jh = κ h µ hh ṽh j , with ṽh j = ∑ i zih x i j , r w h is a d dimensional vector such that r w h j = r w h if w jh = 1 and r w h j = 0, otherwise. Alternating the above E and M steps leads to our soft-dbmovMF algorithm described in Algorithm 4.

Observe that, unlike the classical movMFs where it is easy to verify that rh ≤ 1 (see equation 3.13c) given the definition of r, it is not straightforward to verify that rw h ≤ 1, without careful analysis. Such a result is imperative, to guarantee that the concentration parameters are positive, i.e, κ h > 0 , ∀h, especially when using the approximation of equation (5.6d). Proposition 1 provides theoretical guarantee about the fact that 0 ≤ rw h ≤ 1, thereby it ensures that concentration parameter κ h estimated from equation (5.6d) is always positive.

Proposition 1 Let r be a non-zero vector in R d (i.e., r = (r 1 , . . . , r d ) T , such as d ≥ 1) which results from a weighted sum of n d-dimensional unit vector, i.e, r = ∑ i p i x i , x i ∈ R d and ∥x i ∥ = 1 , ∀i ∈ {1, . . . , n} , n ≥ 2, the weights p i ≥ 0, ∀i. Let r d be a vector in R d , such as all its components are equal to the sum of elements of r (i.e, r d

1 = • • • = r d d = ∑ d j=1 r j ). Then 0 ≤ ∥r d ∥ ≤ d × ∑ i p i with equality only if all unit vectors x i are equal/collinear.
The proof is available in Appendix (A.2). By replacing r d , d and p i in Proposition 1 with r w h , ŵ.h and zih respectively, it is easy to verify 0 ≤ rw h ≤ 1.

Algorithm 4: soft-dbmovMF (EM b ).

Input: X (x i ∈ S d-1 ), g the number of co-clusters.

Output: Z and W, Steps: Initialization: Θ ← Θ (0) ; repeat 1. Expectation step of EM:

for i = 1 to n do for h = 1 to g do zih ← α h f h (x i |µ h ,κ h ) ∑ l α l f l (x i |µ l ,κ l )
end for end for 2. Maximization step of EM:

for j = 1 to d do for h = 1 to g do ṽh j ← ∑ i zih x i j ; t jh ← κ h µ hh ṽh j end for for h = 1 to g do ŵ jh ← 1, if h = arg max h ′ t jh ′ 0, otherwise. end for end for for h = 1 to g do αh ← ∑ i zih n μhh ← ± 1 √ ŵ.h ; r w h ← ∑ i, j zih ŵ jh x i j κh ← rw h d-(r w h ) 3 1-(r w h ) 2 ; rw h ← ∥r w h ∥ z.h ŵ.h
end for until convergence More interestingly, notice that the concentration parameters depend on the column partition w, hence, the dimensionality reduction of dbmovMFs alleviates the problem of high concentration parameters. The following theorem guarantee that dbmovMFs leads to a concentration parameter that is less or equal to that of movMFs, for each cluster. The proof is provided in Appendix (A.2). In practice and when dealing with high dimensional datasets, we empirically observe that dbmovMFs-based co-clustering algorithms yield substantially lower concentration parameters than movMFs-based algorithms, see section (5.7.2).

Theorem 1 Let X be a n × d matrix, its i th row (object) x i is a d-dimensional unit vector in S d-1 (i.e, x i ∈ R d and ∥x i ∥ = 1 , ∀i ∈ {1, . . . , n} , n ≥ 2, d ≥ 3). Let z = (z 1 , . . . , z n ) denote a partition of the set of objects of X into g disjoint clusters. Then, whatever the partition w of attributes of X into g disjoints clusters, the concentration parameter of each dbvMF component estimated via approximation (5.6d) is always less or equal to the concentration parameter of the corresponding vMF component estimated via approximation (3.13c). That is,

κw h ≈ rw h d -rw h 3 1 -rw h 2 ≤ κh ≈ rh d -(r h ) 3 1 -(r h ) 2
with equality only if rw h = rh .

Classification Maximum Likelihood estimates and the CEM b algorithm

Setting our model dbmovMFs under the CML approach, that consists in maximizing the classification likelihood instead of its expectation [START_REF] Scott | Clustering methods based on likelihood ratio criteria[END_REF][START_REF] Symons | Clustering criteria and multivariate normal mixtures[END_REF][START_REF] Celeux | A classification em algorithm for clustering and two stochastic versions[END_REF], we derive a hard version of dbmovMFs called CEM b . This is done by incorporating a classification step (C-step) between the E and M steps as follows,

z ih ←      1, if h = arg max h ′ zih ′ 0, otherwise.
The C-step of CEM b , generates a completed sample (x i ,z i ) by allocating each object x i to cluster z i with the highest posterior probability zih , ∀h. Then, unlike the EM b algorithm where the M-step is based on the expectation of the complete data likelihood, the M-step of CEM b consists in maximizing the complete data likelihood instead of its expectation, thereby the update of the parameters Θ t are based on the completed sample (x i ,z i ). The corresponding M-step can be deduced from the M-Step of EM b by replacing zih by z ih and thereby t jh by t jh . Algorithm 5 gives a full description of CEM b .

Regarding the clustering context, the main difference between ML and CML approaches is that, under the ML approach, the partition z of the set of objects into g clusters is deduced at convergence of EM b , by assigning each object x i to the cluster that maximizes the a posteriori probability zih , while under the CML approach the clustering process is taken into account during parameters estimation. In this way, CEM b simultaneously estimates the parameters and the partition z. It is well known that the ML approach yields more consistent estimate of the parameters thus often provides better clustering than the classification approach, Algorithm 5: hard-dbmovMF (CEM b ). Input: X (x i ∈ S d-1 ), g the number of co-clusters. Output: Z and W, Steps: Initialization: Θ ← Θ (0) ; repeat 2. Expectation step of CEM:

for i = 1 to n do for h = 1 to g do f h (x i |Θ (t) ) ← c d (κ h ) ∏ j (e κ h µ hh x i j ) w jh end for 3. Classification step of CEM: for h = 1 to g do z ih ← 1, if h = arg max h ′ α h ′ f h ′ (x i |Θ (t)
) 0, otherwise. end for end for 4. Maximization step of CEM:

for j = 1 to d do for h = 1 to g do v h j ← ∑ i z ih x i j ; t jh ← κ h µ hh v h j end for for h = 1 to g do ŵ jh ← 1, if h = arg max h ′ t jh ′ 0, otherwise. end for end for for h = 1 to g do α h ← z .h n μhh ← ± 1 √ ŵ.h ; r w h ← ∑ i, j z ih ŵ jh x i j κh ← rw h d-(r w h ) 3 1-(r w h ) 2 ; rw h ← ∥r w h ∥ z .h ŵ.h
end for until convergence especially when the clusters are not well separated. However, the CML approach exhibits some nice properties generated by CEM b , -CEM b is considerably more faster and scalable than EM b , for instance, consider the update of the parameter ŵ jh , under the ML approach (see, equation 5.6a) we iterate through all objects x i to compute t jh , while with CEM b we only iterate through objects within the h th cluster to compute t jh .

-CEM b allows us to avoid numerical difficulties, i.e, over and under flows, related to the computation of the conditional probabilities zih , especially in the case of vMF distribution where the normalization terms c d (κ h ) involve Bessel functions and the concentration parameters act as multipliers in the exponent. More precisely, with CEM b there is no need for computing the conditional probabilities zih , the C-step can be done equivalently by assigning each object x i to the cluster maximising log α h + log f h (x i |Θ (t) ). Furthermore, this contributes to the efficiency, scalability and memoryspace saving of CEM b .

-It eases the derivation of a large number of standard clustering algorithms as special cases from a mixture framework, which allows to give them a probabilistic interpretation. For example, in our case, starting from CEM b we derive a novel co-clustering algorithm, which can be viewed as an extension of the well known spherical kmeans algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF] to the context of co-clustering.

Diagonal Block Spherical Kmeans (dbSkmeans)

In this section, we derive a novel diagonal co-clustering algorithm from hard-dbmovMF, by enforcing some restrictive constrains on the concentration parameters κ h and the mixing proportions α h . We name this novel algorithm diagonal block spherical kmeans (dbSKmeans), due to its theoretical connection to the spherical k-means algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF].

Definition

Let's assume that all the mixing proportions are equal and all the concentration parameters are equal to a finite constant, i.e, α h = 1 g , κ h = κ, for all h ∈ {1, . . . , g}. Under these restrictions, the complete data log-likelihood (A.2) becomes:

L c (Θ|X , Z) = ∑ h z h log (1/g) + ∑ h z h log(c d (κ)) + κ ∑ i,h, j z ih w jh µ hh x i j = n[log (1/g) + log(c d (κ))] constant +κ ∑ i,h z ih (µ w h ) T x i .
(5.7)

Hence, maximizing the complete data log-likelihood (5.7) is equivalent to maximizing the following criterion:

∑ i,h z ih (µ w h ) T x i . (5.8)
Observe that, criterion (5.8) is given in terms of row clustering, we can similarly express it in terms of column clustering as follows ∑ j,h w jh t jh where t jh = κ µ hh v h j with v h j = ∑ i z ih x i j .

(5.9)

Intertwining the maximization of criterion (5.8) and ( 5.9) for fixed row and column clustering, respectively, constitutes our block spherical kmeans (dbSkmeans) algorithm, for co-clustering directional data. The centroid µ h is estimated in the same way as in the M-step of hard-dbmovMF (i.e, μhh = ± 1

√ ŵ.h
, for all h ∈ {1, . . . , g}). The dbSkmeans algorithm is a restricted version of hard-dbmovMF, hence at each iteration it never decreases criterion (5.8) and it is guaranteed to terminate in a finite number of iterations at a local maximum of the restricted likelihood function (5.8). Algorithm 6 describes dbSkmeans in detail.

Algorithm 6: dbSkmeans.

Input: X (x i ∈ S d-1
), g the number of co-clusters. Output: Z and W, Steps:

Initialization: Θ ← Θ (0) ; repeat 1.
Rows assignment:

for i = 1 to n do z i ← h where h = arg max h ′ cos(µ w h ′ , x i ) end for 2. Columns assignment:

for j = 1 to d do w j ← h where h = arg max h ′ √ z .h ′ √ w .h ′ cos(µ z h ′ , x j ) end for 3. Centroids update: for h = 1 to g do µ hh ← ± 1 √ w .h
end for until convergence

Connection to other algorithms

Note that, maximizing criterion (5.8) is equivalent to maximizing the sum of cosine similarity between each object x i and its corresponding centroid, thereby if we further assume that the column partition w is fixed, criterion (5.8) is exactly the criterion maximized by the spherical k-means algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], where the centroids take the form (5.2) introduced in the previous section.

Moreover, connections with the two-sided (or double) k-means algorithm, i.e, using euclidean distance, can be established. It is well known that the double kmeans algorithm minimizes the following objective function

W (z, w) = ∑ i, j,h,ℓ z ih w jℓ (x i j -c hℓ ) 2 = ∑ i, j,h,ℓ z ih w jℓ x 2 i j + ∑ i, j,h,ℓ z ih w jℓ c 2 hℓ -2 ∑ i, j,h,ℓ z ih w jℓ c hℓ x i j = ∑ i,h z ih ∥x i ∥ 2 + ∑ i,h z ih ∥c w h ∥ 2 -2 ∑ i,h z ih (c w h ) ⊤ x i (5.10)
where c w h denotes the h th row centroid, i.e, c w h = (c h1 , . . . , c h1 , c h2 , . . . , c h2 , . . . , c hm , . . . , c hm ) ⊤ assuming that the data points x i and the row centroids c w h are normalized in order to lie on the surface of a unit hypersphere, i.e, x i , c w h ∈ R d and ∥x i ∥ = ∥c w h ∥ = 1, then optimizing criterion W (z, w) (5.10) is equivalent to maximizing the following criterion

W (z, w) = ∑ i,h z ih (c w h ) ⊤ x i .
(5.11)

Furthermore, if we constrain the number of row clusters to be equal to that of column clusters and the centroids c w h to take the form (5.2) introduced earlier, then criterion (5.11) becomes exactly the same as criterion (5.8) optimized by our dbSkmeans algorithm. Hence, under the aforementioned constrains dbSkmeans is equivalent to a large number of co-clustering algorithms using the principle of double k-means, among which we can cite the well known Minimum Sum-Squared Residue Co-Clustering of Gene Expression Data by [START_REF] Cho | Minimum sum-squared residue co-clustering of gene expression data[END_REF], the CROEUC algorithm due to [START_REF] Govaert | Simultaneous clustering of rows and columns[END_REF] and the co-clustering based on non-negative matrix tri-factorization proposed by Labiod and Nadif (2011a).

Analysis of column assignment

Hereafter, we shall give some intuitions and interpretations about the column affectation step of dbSkmeans.

w j = arg max h t jh = arg max h κ µ hh v h j = arg max h κ µ hh ∑ i z ih x i j = arg max h κ(µ z h ) T x j = arg max h κ∥µ z h ∥∥x j ∥cos(µ z h , x j ) ≡ arg max h ∥µ z h ∥cos(µ z h , x j ) = arg max h √ z .h √ w .h cos(µ z h , x j ) (5.12)
where x j denotes the j th column, µ z h denotes the h th "column centroid", i.e, µ hi = 1/ √ w .h if z ih = 1 and µ hi = 0, otherwise. The superscript z is used to denote the fact that the column centroid µ z h depends on the row clustering. Hence, the column affectation step of dbSkmeans is equivalent to maximizing a "weighted" cosine similarity between each column x j and the corresponding column centroid µ z h . The weight √ z .h √ w .h has a nice semantic interpretation, for instance let x j be a column such that cos(µ z 1 , x j ) = cos(µ z 2 , x j ), w .1 = w .2 and z .1 > z .2 , then the column x j will be assigned to the first column cluster. The role of the weight in this situation is to assign more elements to column clusters describing row clusters containing more objects than the others. This is natural, since row clusters with a lot of objects are expected to be described by more features than those with few objects. Furthermore, as the above weight is inversely proportional to the root square of the size of the corresponding column cluster, it has an interesting regularizing effect that makes it possible to avoid the formation of empty and/or very large column clusters. Thereby, this implicitly prevents dbSkmeans from generating empty (very large) row clusters induced by empty (very large) column clusters.

In summary, the weight involved in the column affectation step of dbSkmeans, has a nice regularizing effect, that prevents dbSkmeans from generating highly skewed solution with empty and/or very large co-clusters. Moreover, it makes it possible to find a trade-off between row and column clusters sizes, by trying to deal with the natural intuition that row clusters with more objects are expected to be described by column clusters with more features, than the other row clusters.

Stochastic Variants

It is well known that the EM algorithm is strongly dependent on its starting position. The stochastic variant of EM (SEM) [START_REF] Celeux | The SEM algorithm: a probabilistic teacher algorithm derived from the EM algorithm for the mixture problem[END_REF] however makes it possible to overcome this limitation. It consists in incorporating a stochastic step (S-step) between the E and M steps, which generates a completed sample (x i ,z i ) by drawing a cluster z i ∈ {1, . . . , g} for each data point x i according to the multinomial distribution M(z i1 , . . . , zig ).

Hence, as with the CEM algorithm [START_REF] Celeux | A classification em algorithm for clustering and two stochastic versions[END_REF] the update of the parameters Θ t are based on the completed sample (x i , z i ) i.e, complete data likelihood instead of its expectation. It follows from the above description that SEM does not share the convergence properties of EM and CEM. In fact, SEM can allow an update estimate Θ t+1 even if L(Θ t+1 ) < L(Θ t ). Thereby, SEM does not necessarily converge to the first encountered stationary point of the log-likelihood, which allows SEM to ignore saddle points and insignificant local optima. This is the main reason why SEM can be expected to achieve better solutions than EM. It has been shown that the sequence of parameters {Θ t } generated by SEM is an ergodic Markov chain, thereby, it converges to the unique stationary distribution of this Markov chain. For further details about SEM, the reader can refer to [START_REF] Celeux | The SEM algorithm: a probabilistic teacher algorithm derived from the EM algorithm for the mixture problem[END_REF].

Stochastic dbmovMFs and the SEM b algorithm

Based on SEM we formulate a stochastic version of soft-dbmovMF called SEM b . In our case, we further propose a stochastic column assignment, by converting t jh to probabilities w jh , i.e, w jh ∝ t jh and drawing a cluster w j for each column j according to multinomial distribution M( w j1 , . . . , w jg ). This makes it possible to avoid a quick convergence to a bad local optimum of the likelihood function, due to hard column assignments. More intuitively, in the case of document-term matrices, during the first iterations document clusters are mixed, hence each word is involved to describe several document clusters thereby imposing hard word assignments at the beginning, by using equation (5.6a), can lead to a poor local optimum of the likelihood function, especially when the clusters are poorly separated. Algorithm 7 describes in more details SEM b .

Simulated annealing dbmovMFs-based algorithms

One of the main drawback of the SEM algorithm is that it does not share the convergence properties of EM; SEM converges in distribution and does not converge point-wise. Furthermore, when the sample size of the observed data is small, SEM may converge to a stationary Algorithm 7: Stochastic-dbmovMF (SEM b ). Input: X (x i ∈ S d-1 ), g the number of co-clusters. Output: Z, W and Θ.

Steps: Initialization: Θ ← Θ (0) ; repeat 1. Expectation step:

for i = 1 to n do for h = 1 to g do zih ← α h f h (x i |µ h ,κ h ) ∑ l α l f l (x i |µ l ,κ l )
end for 2. Stochastic step:

Select z i ∈ {1, . . . , g} ∼ M(z i1 , . . . , zig ) end for 3. Maximization step:

for h = 1 to g do α h ← ∑ i z ih n for j = 1 to d do v h j ← ∑ i z ih x i j ; t jh ← κ h µ hh v h j
end for end for for j = 1 to d do Select w j ∈ {1, . . . , g} ∼ M( w j1 , . . . , w jg )

end for for h = 1 to g do μhh ← 1 √ w .h ; r w h ← ∑ i, j z ih w jh x i j κh ← rw h d-(r w h ) 3 1-(r w h ) 2 ; rw h ← ∥r w h ∥ z .h w .h
end for until convergence distribution with a high variance, which leads to poor estimation of the parameters. In order to overcome the aforementioned limitations, the Simulated Annealing version of EM (SAEM) has been proposed [START_REF] Celeux | A stochastic approximation type em algorithm for the mixture problem[END_REF], that reaps the benefit of both EM and SEM simultaneously. To do so, let γ t be a sequence of positive real numbers starting from 1 and decreasing to zero, at each iteration the parameters are updated as follows

Θ t+1 SAEM = (1 -γ t+1 )Θ t+1 EM + γ t+1 Θ t+1 SEM
where Θ t+1 EM and Θ t+1 SEM denote the parameters estimated using EM and SEM, respectively. Thus, SAEM goes from pure SEM at the beginning towards pure EM at the end. If we further impose the following constraint lim t→∞ γ t γ t+1 = 1, we can ensure the asymptotic convergence of SAEM to a local maximum of the log-likelihood function.

Based on SAEM, we derive the SAEM b algorithm, which is a simulated annealing version of EM b . In our case, however, it is difficult to use the above update formula of SAEM due to parameter w. In order to overcome this difficulty, we propose to use the following simplified form to update the parameters, which turns out to be effective and less costly.

Θ t+1 SAEM b ←      Θ t+1 SEM b , if γ t+1 ≥ (1 -γ t+1 ) Θ t+1 EM b , otherwise.
We propose to use the following exponentially decreasing form for

γ t = 1 -exp it t -it max β
where it t , it max denote respectively, the current iteration and the maximum number of iterations, β is a positive real parameter that controls the number of SEM b and EM b iterations to be performed. More precisely when β → ∞, SAEM b tends to pure EM b , similarly when β → 0, SAEM b tend to pure SEM b . In our experiments, we set β = 20 and it max = 100, in such a way that most iterations at the beginning are done using SEM b , in order to reach a steady state and avoid poor local optima, and the last few iterations are performed using EM b , to ensure the convergence of SAEM b to a local optimum of the log-likelihood function. This simplified version consists in initializing EM b with SEM b . Note that, seeing the initialization of EM b via SEM b as a kind of a Simulated Annealing variant, justifies why EM b is expected to provide better performances with such an initialization.

In the same manner, we derived a hard simulated annealing variant, denoted in this chapter as CAEM b . The difference with the SAEM b algorithm is that the iterations at the end are performed using CEM b instead of EM b . In Figure 5.3 we report the different algorithms discussed in this chapter. Skmeans dbSkmeans

ĸ h = ĸ, ⩝ h α h = α, ⩝ h ĸ h = ĸ, ⩝ h α h = α, ⩝ h

Computational Complexity in the Worst Case

In this section, we shall analyse the computational complexity of dbSkmeans, hard-dbmovMF and soft-dbmovMF.

Proposition 2 Let X be a n × d matrix, let nz denote the number of non-zeros entries in X, "it" is the number of iterations and g is the number of co-clusters to be found. Then (i) the computational complexity of dbSkmeans described in Algorithm 6 is given in O(it • nz), (ii) the computational complexity of hard-dbmovMF described in Algorithm 5 is given in O(it • nz) (iii) the computational complexity of soft-dbmovMF described in Algorithm 4 is given in O(it • g • nz).

Proof (i). The computational bottleneck for dbSkmeans is with the row and column assignments. We prove that the complexity of both row and column assignments is O(nz). Let

x i denote the i th row of X (i.e, x i is a d dimensional vector in S d-1
). Assume that we look for a co-clustering of X into g co-clusters, and let µ w h be the h th centroid, characterising the h th co-cluster. The computational cost of the scalar product

(µ w h ) T x i is O(x h i )
, where x h i is number of non-zeros entries of x i within the h th column cluster, this complexity holds thanks to the form of µ w h , see equation (5.2). Thereby, the complexity of the assignment of

x i is given in O(x * i ) (based on O(x 1 i + • • • + x g i ))
, where x * i denotes the number of non-zeros entries of x i . Therefore, the total cost of one row assignments step is O(nz). Similarly, we can show that the cost of one column assignments step is O(nz). Thus the computational complexity of dbSkmeans is given in O(it • nz), based on O(it • (nz + nz)).

Table 5.1 Computational complexity of different algorithms (in the worst case). nz denotes the number of non-zero entries in the matrix X, g is the number of clusters (co-cluster) and it denotes the number of iterations.

movMFs (Banerjee et al., 2005b) dbmovMFs (this chapter) soft-movMF hard-movMF Skmeans soft-dbmovMF hard-dbmovMF dbSkmeans

O(it • g • nz) O(it • g • nz) O(it • g • nz) O(it • g • nz) O(it • nz) O(it • nz)
In the same manner we can prove (ii) and (iii), see Appendix (A.3) for further details. Proposition 2, states that theoretically, the computational time of our algorithms is linear with respect to the number of non-zero entries in X. Hence, the proposed algorithms are very efficient (in particular the hard variants) and therefore suitable for large sparse datasets. Table 5.1 summarizes the computational complexity of the different algorithms.

Experimental results

In this section, we shall provide extensive empirical results to validate and illustrate the benefits of our model dbmovMFs and the corresponding co-clustering algorithms. We first propose to validate the correctness of our model on simulated datasets. Then, in order to show the benefits of our approach, we conduct extensive experiments on numerous real world text datasets, in which we benchmark our algorithms, i.e, EM b , CEM b , SEM b , SAEM b , CAEM b and dbSkmeans against several strong baselines denoted in this chapter as follows -EM denotes the soft-movMF algorithm proposed in (Banerjee et al., 2005b).

-CEM denotes the hard-movMF algorithm proposed in (Banerjee et al., 2005b).

-DAEM is the deterministic annealing version of soft-movMF proposed in [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF].

-Skmeans denotes the spherical k-means algorithm [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF], which is also a simplified version of soft-movMF, where

κ h = κ → ∞, α h = α, for all h.
It is also a restricted version of hard-movMF where κ h = κ, α h = α, for all h.

Notice that, in the context of text document clustering, it has been empirically shown on numerous real-world datasets, that the aforementioned baselines perform better than several existing clustering and co-clustering algorithms, namely: k-means using the euclidean distance, generative mixture models using Bernoulli, Gaussian, and Multinomial distributions, spectral co-clustering, and Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF]. Therefore, we do not include these approaches in our comparisons. For further details see [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF][START_REF] Gopal | Von mises-fisher clustering models[END_REF].

Simulated data sets

In the following, we validate the correctness of our model and implementations, on several simulated datasets corresponding to various particular situations, illustrated in Figure 5.4, namely balanced co-clusters, unbalanced co-clusters, clusters with equal concentration and with different concentrations and last overlapping clusters. We consider five different simulated datasets, each of them consists of a sample of 5000 unit vectors from a Diagonal Block Mixture of three 1000-dimensional vMF distributions. The different simulated datasets, i.e, sdata1, . . . , sdata5 are described in Table 5.2. In this table, α, κ and µ denote the true parameters, while α, κ and μ denote the estimated ones. As this table shows clearly, when co-clusters are reasonably separated, both EM b and CEM b provide excellent performances, even in situations where data exhibit unbalanced cluster sizes and concentration parameters. However, in the case of poorly separated coclusters, i.e, sdata5, EM b and CEM b suffer from a convergence to a poor local maximum of the likelihood function, due to hard column assignments at the beginning, i.e, during the first iterations the row clusters are mixed, hence each column is involved to describe several row clusters. The simulated annealing variant SAEM b , however, overcomes this difficulty thanks to stochastic assignments in the beginning and thereby, yields excellent performance on sdata5 although the co-clusters are poorly separated.

Real-world datasets

As a practical example we select the domain of text mining and we concentrate on the challenging task of document clustering using high dimensional sparse document-term matrices. We retain six popular benchmark text datasets: CSTR used in [START_REF] Li | A general model for clustering binary data[END_REF], CLASSIC4 1 , WEBACE, the 20-newsgroups data NG20, SPORTS used in [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF], and TDT2 2 . All these datasets are carefully selected to represent various particular challenging situations in clustering: balanced clusters, unbalanced clusters, different number of clusters, different sizes, different degrees of cluster overlap (i.e, well separated clusters and poorly separated clusters). The characteristics of these different datasets are summarized in Table 5.3. Note that, in contrast to document clusters, the true word cluster labels are not known in the above datasets, this is the reason why we mainly concentrate our experiments on document clustering. However, under our formulation row clusters induce column clusters and vice versa, hence the quality of row clustering is informative about the quality of column clustering. It is reasonable to expect that a good row partitioning induces a good column partitioning and vice versa.

Evaluation measures

Evaluating clustering results is not a trivial task, however, when the true category labels are known, a commonly used approach to validate clustering results consists to compare the estimated partition with the true one. To this end, several measures have been proposed, in our experiments we retain two widely used measures to assess the quality of clustering, namely the Normalized Mutual Information NMI [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] and the Adjusted Rand Index ARI [START_REF] Milligan | A study of the comparability of external criteria for hierarchical cluster analysis[END_REF][START_REF] Hubert | Comparing partitions[END_REF]. Intuitively, NMI quantifies how much the estimated clustering is informative about the true clustering, while the ARI measures the degree of agreement between an estimated clustering and a reference clustering. Both NMI and ARI are equal to 1 if the resulting clustering is identical to the true one, and close to zero for a random clustering.

Experimental setting

In all our experiments we use the TF-IDF normalized data representation, more precisely we use the TF-IDF weighting scheme proposed in Scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF]. For each dataset we set g to the real number of clusters, and in order to make fair comparisons, all non-stochastic algorithms are initialized using the same row partition resulting from Skmeans4 started using a random initial point, unless stated otherwise. For our algorithms, we further initialize the concentration parameters to 10 and the centroids to random initial vectors, in order to be able to estimate the initial column partition. Concerning our stochastic variants, i.e, SEM b , CAEM b and SAEM b they are initialized using the same random row and column partitions.

Evaluation of row clustering

Tables 5.4 and 5.5, summarize the results of the different methods in terms of NMI and ARI, over all datasets. All results are averaged over thirty different starting points, obtained using the initialization strategy described above. Between brackets, we report the results corresponding to the trial with the highest criterion. As it is evident from these tables, our dbmovMFs-based algorithms, i.e, EM b , CEM b and dbSkmeans exhibit high performances as opposed to movMFs-based method. In fact, EM b , CEM b and dbSkmeans achieve better performances than EM, CEM and Skmeans, in almost all situations, except in terms of ARI on CLASSIC4 and NMI on SPORTS, however, the difference is not significant. We note that both EM b and CEM b perform somewhat better than dbSkmeans, in fact the former generalize dbSkmeans. Once again we observe only a slight difference between EM b and CEM b , which is statistically not significant.

Advantages of SAEM b and CAEM b

We observe that our simulated annealing variants, SAEM b and CAEM b , provide the best performances in almost all situations (although they are initialized randomly), except on SPORTS, where SEM b achieves substantially better results than the other methods. As opposed to EM b , CEM b and dbSkmeans which depend strongly on their starting positions, the stochastic variants, i.e, SAEM b and CAEM b are not sensitive to their initial positions. For instance, in the case of high overlapping clusters as in CLASSIC4, NG20 and SPORTS, we observe that EM b , CEM b and dbSKmeans suffer from a convergence to a poor local maximum of the likelihood function, when they are initialized randomly. The SAEM b and CAEM b algorithms, however, avoid this difficulty and converge to a better local optimum of the likelihood function, see Table 5.6; this is due to the advantage of SEM b in the begining. ,533.3 122,329,895 4,866,978 3,411,592,328 432,277,941 1,299,234,559 CEM b 976,520.4 122,329,033 4,866,769 3,411,588,346 432,276,368 1,299,232,734 CAEM b 976,540 122,341,547 4,867,537 3,411,836,825 432,282,583 1,299,303,290 SAEM b 976,547 122,341,562 4,868,739 3,411,838,557 432,286,341 1,299,304,500

NMI vs ARI

Tables 5.4 and 5.5 show that our algorithms provide high performances in terms of both NMI and ARI, while the other movMFs-based methods sometimes provide good NMI but low ARI as this is the case with almost all datasets, except CSTR. Figure 5.6 confirms this remark; we observe that the behavior of NMI and that of ARI are more often in keeping with our algorithms rather than with movMFs-based algorithms5 , i.e, DAEM, EM, CEM and Skmeans.

The explanation is that movMFs-based clustering methods tend to merge small clusters and try to split larger ones into comparably sized clusters, as it has been already emphasized in (Banerjee et al., 2005b). In fact, unlike ARI, the NMI measure is less sensitive to clusters merging and/or splitting. Our dbmovMFs-based algorithms, however, thanks to the centroids orthonormality assumption, avoid the above difficulty, and are able to discover large as well as small clusters (see Figure 5.7 and confusion matrices of Table 5.7). Furthermore, as we can see from Figure 5.7, EM b reveals a more interesting structure (i.e, block diagonal) than Skmeans.

Impact of concentration parameters

We observe that the Skmeans algorithm which is a restricted version of movMFs where all clusters share the same proportion and the same concentration parameter, yields better results than the other movMFs-based algorithms, as it has been already emphasized by [START_REF] Gopal | Von mises-fisher clustering models[END_REF]. The low performance of EM and CEM as opposed to Skmeans, is due to high concentration parameters κ h in the normalization terms c d (κ h ) that involve Bessel functions. As it has been highlighted by Banerjee et al. (2005b), in the case of large positive matrices, all the data lie on the first orthant of a d-dimentional hypersphere, thereby the concentration of such data is implicitly high. As a result, the concentration parameters κ h of the vMF distributions are high and increase exponentially with the dimensionality of the data. Our model dbmovMFs, however, alleviates this problem of high concentration parameters, thanks to its implicitly adaptive dimensionality reduction property. In Figure 5.8 are reported the distribution of the concentration parameters estimated by our dbmovMFsbased algorithms and movMFs-based algorithms. We clearly observe that our algorithms, CEM b , EM b , CAEM b and SAEM b , yield substantially lower concentration parameters than EM and CEM.

Interpretation of column clusters

Although we focused on document clustering, notice that our algorithms offer word clusters. Each of them describes a single document cluster and thereby, allows to understand the semantic meaning of document clusters. Tables 5.8, 5.9 and 5.10 provide typical examples, where the four, seven and top six word clusters resulting from SAEM b on CLASSIC4 and TDT2 respectively, are represented by their top 15 terms. The top terms of each co-cluster were obtained by keeping only the terms that appear in most documents in the considered cluster. The obtained word clusters are meaningful and help to make sense of the corresponding document clusters; they are semantically coherent. More interestingly, and as illustrated in Table 5.9 on the CLASSIC4 datatset, when the requested number of clusters ( 7) is greater than the natural number of clusters ( 4), our algorithm try to split the natural clusters into semantically coherent sub-clusters. Hence, when the true number of clusters is not known, one can request a relatively high number of clusters and then merge them adequately, based on the obtained word clusters.

Assessing the number of clusters

Often in practice the number of clusters is not known in advance and should be determined by the user. Assessing the number of clusters is, however, not straightforward and still remains one of the biggest challenges in machine learning. Fortunately, in our case we can rely to therefore k = g × (d + 2) -1 due to g concentration parameters κ h 's, g -1 mixing proportions α h 's and d × g column cluster parameters w jh 's.

In figures 5.9 to 5.14 are depicted the values of the log-likelihood, AIC, AIC3 and BIC as a function of the number of clusters, over different data sets (we found that the ICL criterion, not reported here for presentation purpose, behaves like BIC). First of all, we observe that the log-likelihood can clearly not be used to assess the right number of clusters as it varies, as expected, monotonically when the number of clusters increases. The penalty term of the BIC criterion seems to be too strong due to the high number of parameters to be estimated, as a result BIC, increases monotonically and, thereby, does not allows us to identify the number of clusters, except on CLASSIC4 and WEBACE where BIC and ICL identify 3 and 6 clusters, respectively, instead of 4 and 20. From figures 5.9 to 5.14 we observe that AIC and AIC3 are able to identify a number of clusters that is close or even equal to the right number of clusters on almost all data sets, except on TDT2 where both criteria under estimate the number of clusters. This suggests that, in our case, a convenient penalty term γ lies between 1 and 3/2.

Furthermore, the AIC criterion seems to be slightly better than AIC3 since the latter tends to underestimate the right number of clusters on some data sets such as NG20 and CSTR. Another notable result is that, on the CLASSIC4 data set, that contains 4 classes, AIC3 suggests 6 clusters while AIC suggests a number of clusters between 6 and 8, this is, however, not an issue. In fact, as illustrated in table 5.9 some classes in CLASSIC4 are composed of several semantically coherent sub-clusters. Thereby, an interesting approach would be to consider the number of clusters determined by AIC/AIC3 as a starting point, which can then be tuned by exploring the top terms of the obtained word clusters so as to decide whether the number of clusters should be increased, decreased or kept unchanged.

Conclusion and perspectives

In this chapter we proposed a novel generative model based on a mixture of vMF distributions, called dbmovMFs, that successfully integrates a directional measure, namely the cosine similarity, into a co-clustering framework. The high performances of dbmovMFs-based algorithms confirm again the benefits of the vMF modelling assumption when we are dealing with some high dimensional sparse datasets, as it has been already emphasized in (Banerjee et al., 2005b;[START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF][START_REF] Gopal | Von mises-fisher clustering models[END_REF]. The introduction of column clustering into a mixture of vMF distribution seems to be beneficial from several perspectives: (i) in terms of inference this allows us to reduce substantially the complexity of the model regarding the number of free parameters to be estimated and thereby yielding a parsimonious model, (ii) it makes it possible to exploit the inherent duality between rows and columns which improves the performance, in terms of document clustering, of vMF-based mixture models by a noticeable amount, as demonstrated in our experiments, (iii) it alleviates the high concentration parameter κ issue, by performing an implicitly adaptive dimensionality reduction at each stage, and finally, (iiii) it has the advantage of producing directly interpretable clusters and co-clusters, which may also help to assess the number of clusters when the latter is not known, as emphasized in section 5.7.2.

By setting the estimate of the model parameters under the ML and CML approaches, we proposed six novel co-clustering algorithms corresponding to different variants of the EM algorithm. We derived soft, hard, stochastic and simulated annealing variants. Extensive experiments, conducted on numerous simulated and real-world datasets, provide empirical evidence about the advantages and effectiveness of the proposed algorithms for simultaneous clustering of documents and words, using high dimensional sparse document-term matrices. In particular, we recommend the simulated annealing variants that seem to reach the best performances in almost all situations, especially when clusters are poorly separated. However, if scalability is a requirement, the hard variants CEM b and dbSkmeans may turn out to be a wise choice.

The good performances of our algorithms motivate further investigations. For instance, it would be interesting to propose a way to simultaneously use estimates obtained by SEM b and EM b /CEM b in an iterative process to overcome therefore the difficulty of managing parameter w. We could also improve dbmovMFs by considering a Bayesian formulation that would enable sharing of information between co-clusters [START_REF] Gopal | Von mises-fisher clustering models[END_REF]. Future improvements could also involve the development of temporal, incremental and on-line variants of our algorithms. Such variants would be of great interest for applications such as collaborative filtering where available information evolves frequently. Finally, it would be opportune to tackle the problem of the number of co-clusters which remains one of the most important challenge in co-clustering. For instance, an interesting strategy would be to treat the problem of parameter estimation and assessing the number of co-clusters simultaneously [START_REF] Wyse | Block clustering with collapsed latent block models[END_REF].

Chapter 6 Frequency Sensitive Co-clustering

It is well known that, because of the high dimensionality and sparsity of the data, co-clustering approaches, like one-sided clustering methods, tend to generate highly unbalanced clusters, i.e., clusters of widely varying sizes, in particular when the number of required clusters is large [START_REF] Dhillon | Iterative clustering of high dimensional text data augmented by local search[END_REF][START_REF] Cho | Minimum sum-squared residue co-clustering of gene expression data[END_REF][START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF][START_REF] Zhang | A local search approach to k-clustering[END_REF]. However, in some situations it may be more beneficial to avoid such very skewed solutions. This chapter describes a novel directional co-clustering approach that addresses the above issue, that is a co-clustering method that makes it possible to take into account the directional properties of some data sets as well as avoid bad solutions with very unbalanced clusters. More precisely, the approach presented here builds on the block mixture of von Mises-Fisher distributions, which is described in the previous chapter, and uses a conscience mechanism that helps to avoid extremely skewed solutions with very small/large or empty clusters. Experimental results on numerous real-world datasets provide empirical evidence about the benefits of the proposed approach.

Introduction

Although vMF-based clustering approaches alleviate the problem of high dimensionality and sparsity, they tend to produce very unbalanced clusters, i.e., clusters of widely varying sizes, due to high dimensionality and sparsity, especially when the number of required clusters is large [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF].

Obviously, when dealing with real-world datasets, it seems more reasonable to expect unbalanced clusters. However, in many situations it is more beneficial to have balanced clusters, i.e., clusters of comparable sizes. For instance, in text document clustering, balancing, as pointed in [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF], is of great interest when generating topic hierarchies as it prevents the generation of heavily skewed hierarchies, which eases navigation. In collaborative filtering (CF), partitioning users into comparably sized groups makes it possible to make fair recommendations for all users. In fact, a clustering-based CF system (Salah et al., 2015) makes recommendations to users according to the shared preferences within their groups. Thus, no relevant recommendation can be made for users from small clusters, similarly it is difficult to make personalized recommendations for users from large clusters.

For more examples of real-life applications where balanced clustering is useful, the reader can refer to [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF].

Motivated by balanced clustering and directional based clustering, the authors in [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF] proposed a variant of Skmeans called Frequency Sensitive Skmeans (FS-Skmeans) for balanced clustering on high dimensional hyperspheres. The FS-Skmeans algorithm is inspired from the Frequency Sensitive Competitive Learning (FSCL) approach [START_REF] Ahalt | Competitive learning algorithms for vector quantization[END_REF]) that uses the "conscience" mechanism [START_REF] Desieno | Adding a conscience to competitive learning[END_REF]. The latter was first used in competitive learning in order to address the problem of highly unbalanced clusters. It consists in penalizing frequently winning "centroids" by making them less likely to win in the future. Based on the conscience mechanism, FSCL was proposed in the context of Vector Quantization to address the problem of under utilisation of parts of codebook. More precisely, FSCL penalizes the representative units by introducing multiplicative terms proportional to some function of the number of their winning. Notice that it only focuses on clustering along one dimension of data matrices, i.e., either rows or columns clustering. However, as pointed in the previous chapter, in the case of high dimensional sparse data, it turns out to be more useful to treat simultaneously both dimensions of data matrices even if one is primarily interested in clustering along one dimension.

However, co-clustering methods, like traditional one-sided clustering, tend to produce highly unbalanced/empty row and column clusters when dealing high dimensional sparse data [START_REF] Cho | Minimum sum-squared residue co-clustering of gene expression data[END_REF], particularly if the number of desired clusters is large. In this chapter, we relay on the block mixture of vMF distributions dbmovMFs, presented in the previous chapter, that constitutes a general framework for co-clustering directional data. Then, in order to avoid obtaining clusters of widely varying sizes, we modify dbmovMFs in a principled way by introducing a "conscience" mechanism that penalizes the clusters relative to the number of object that have been assigned to them. This yields a very scalable co-clustering algorithm that is guaranteed to increase a spherical k-means like criterion by alternating row and column clusterings at each stage.

To the best of our knowledge, the work that we present, is the first that introduces a conscience mechanism into a co-clustering model in order to avoid highly skewed solution with very small or empty clusters. Experimental results on various real-world datasets provide empirical evidence about the advantages of our approach.

Frequency Sensitive Co-clustering

Inspired by Frequency Sensitive Competitive Learning and FS-Skmeans, we propose hereafter to modify dbmovMFs, described in the previous chapter, in an adequate manner by introducing a conscience mechanism, in order to address the problem of obtaining strongly unbalanced clusters and thereby avoiding poor solutions. More precisely, we aim to penalize each row and column cluster by a function of its cardinality, i.e, the number of its elements. To this end, we assume that the concentration parameters are inversely proportional to a function of the number of objects (rows) that has been assigned to their corresponding cluster, i.e, κ h = ℓ/ f (z .h ), ∀h, where z .h represents the cardinality of row cluster h, ℓ is a constant and f denotes any increasing function. The choice of ℓ and f are discussed in more details below. The complete data log-likelihood of X is given by:

L c (Θ|X, Z) = ∑ h z .h log α h + ∑ h z .h log(c d (κ h )) + ∑ i,h z ih κ h µ hh ∑ j w jh x i j = ∑ h z .h log α h + ∑ h z .h log(c d (κ h )) + ∑ i,h z ih κ h (µ w h ) ⊤ x i . (6.1)
The logarithm of the normalization constant is equal to 2m+r where Γ(x) is the Gamma function. Now, let us suppose that each concentration parameter κ h is sufficiently small (i.e, we assume that clusters are not well separated), it is sufficient to choose ℓ = 1 and f (x) ≥ 1 leading to κ h ∈ [0, 1], so that we can ignore terms of the above series with higher power of κ h . Thus, we can approximate I r (κ h ) with the first two terms of this series as follows

log c d (κ h ) = d 2 -1 log κ h - d 2 log 2π -log Id 2 -1 (κ h ). (6.2) We have, I r (κ h ) = ∑ ∞ m=0 1 m!Γ(m+r+1) κ h 2
I r (κ h ) ≈ κ r h 2 r r! + κ r+2 h 2 r+2 (r + 1)! = κ r h 1 2 r r! + κ 2 h 2 r+2 (r + 1)! = κ r h 4(r + 1) + κ 2 h 2 r+2 (r + 1)! (6.3)
for high dimensionality, i.e, large order r = d/2-1, and for small κ h , we have 4(r +1)+κ 2 h ≈ 4(r + 1) and I r (κ

h ) ≈ κ r h 4(r+1) 2 r+2 (r+1)! thereby, log Id 2 -1 (κ h ) ≈ d 2 -1 log κ h + log c where c = 4(r+1) 2 r+2 (r+1)! . Substituting this approximation in (6.2) gives us, log c d (κ h ) = d 2 -1 log κ h - d 2 log 2π - d 2 -1 log κ h -log c = - d 2 log 2π -log c (6.4)
Substituting (6.4) in (6.1) and assuming that all the mixing proportions are equal, i.e, α h = 1 g ∀h leads to .5) Making concentration parameter κ h inversely proportional to a function of the size of cluster h, i.e, κ h ∝ 1/ f (z .h ), where f is an increasing function greater than 1, we choose the root square function f (x) = √ x and obtain

L c (Θ|X, Z) = ∑ h z .h log (1/g) + ∑ h z .h - d 2 log 2π -log c + ∑ i,h z ih κ h (µ w h ) ⊤ x i = n log (1/g) - d 2 log 2π -log c constant + ∑ i,h z ih κ h (µ w h ) ⊤ x i . ( 6
L c (Θ|X, Z) ≡ ∑ i,h 1 √ z .h z ih (µ w h ) ⊤ x i (6.6)
From (6.6) it is obvious that object assignments are done by maximizing a weighted Skmeans like criterion, and we observe that the weights penalize larger clusters. Similarly, we can express (6.6) in terms of column assignment as

L c (Θ|X, Z) ≡ ∑ j,h 1 √ w .h w jh (µ z h ) ⊤ x j (6.7)
where w .h , µ z h , i.e, ∥µ z h ∥ = 1 denote the cardinality and the centroid of hth column cluster, respectively, and x j denotes the jth column. Hence, as for objects clustering, feature clustering consists in maximizing a weighted Skmeans like criterion that penalizes larger column clusters by a multiplicative term. It can easily be deduced as follows

L c (Θ|X, Z) ≡ ∑ i,h 1 √ z .h z ih (µ w h ) ⊤ x i = ∑ j,h 1 √ z .h w jh µ hh ∑ i z ih x i j = ∑ j,h 1 √ z .h w jh 1 √ w .h ∑ i z ih x i j = ∑ j,h 1 √ w .h w jh (µ z h ) T x j ≡ ∑ j,h
Initialization: Θ ← Θ (0) ; repeat 1. Assignment of objects: for i = 1 to n do z i ← h where h = arg max h ′ (z .h ′ ) -0.5 cos(µ w h ′ , x i ) end for 2.
Assignement of Features: for j = 1 to d do w j ← h where h = arg max h ′ (w .h ′ ) -0.5 cos(µ z h ′ , x j ) end for 3. Computation of µ hh 's maximizing (6.6):

for h = 1 to g do µ hh ← 1 √ w .h
end for until convergence Herein, we prove that FSdbSkm monotonically increases criterion (6.6), and terminates in a finite number of iterations at a local optimal solution.

At iteration (t), L c (Θ|X, Z) noted L c , we have

L (t) c = ∑ i,h (z (t) .h ) -0.5 z (t) ih ((µ w h ) (t) ) ⊤ x i = ∑ i,h (z (t)
.h ) -0.5 z

(t) ih (µ hh ) (t) ∑ j w (t) jh x i j = ∑ i,h (z (t)
.h ) -0.5 z

(t) ih (w (t) .h ) -0.5 ∑ j w (t) jh x i j = ∑ i,h (w (t)
.h ) -0.5 z

(t) ih (z (t) .h ) -0.5 ∑ j w (t) jh x i j = ∑ i,h (w (t)
.h ) -0.5 z

(t) ih (µ z hh ) (t) ∑ j w (t) jh x i j ≤ ∑ i,h (w (t)
.h ) -0.5 z

(t+1) ih (µ z hh ) (t) ∑ j w (t+1)
jh x i j (6.9) the latter inequality follows from Steps ( 1) and ( 2) of FSdbSkm. Further, as we have

(µ z hh ) (t+1) = arg max µ z hh L (t) c , subject to the constraint ∥µ z h ∥ = 1 therefore (µ z hh ) (t+1) = (z (t+1) .h
) -0.5 , thereby we obtain,

L (t) c ≤ ∑ i,h (z (t) .h ) -0.5 z (t+1) ih (µ z hh ) (t+1) ∑ j w (t) jh x i j ≤ ∑ i,h (w (t) .h ) -0.5 z (t+1) ih (z (t+1) .h ) -0.5 ∑ j w (t) jh x i j ≤ ∑ i,h (z (t+1) .h ) -0.5 z (t+1) ih (µ hh ) (t+1) ∑ j w (t+1) jh x i j ≤ ∑ i,h (z (t+1) .h ) -0.5 z (t+1) ih ((µ w h ) (t+1) ) ⊤ x i = L (t+1) c
the latter inequality follows from step (3) of FSdbSkm. The convergence of FSdbSkm to a local optimum of criterion (6.6) follows, since the number of distinct row and column partitions is finite.

Experimental results

To show the benefits of our approach, we conduct extensive experiments on numerous real-world text datasets, in which we benchmark our algorithm FSdbSkm against several strong baselines: the soft-movMF proposed in (Banerjee et al., 2005b), da-movMF is the deterministic annealing version of movMF proposed in [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF] and

Skmeans [START_REF] Dhillon | Concept decompositions for large sparse text data using clustering[END_REF] which is also a simplified version of soft-movMF, where κ h = κ → ∞, α h = α, for all h. For text documents clustering, it has been empirically shown on numerous real-world datasets, that the aforementioned baselines perform better than several existing clustering and co-clustering algorithms including: K-means with the euclidean distance, generative model using Gaussian, Bernoulli and Multinomial distributions, spectral co-clustering, and Latent Dirichlet Allocation (LDA) (see [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF][START_REF] Gopal | Von mises-fisher clustering models[END_REF]). Therefore, we do not include these approaches in our comparisons.

Datasets

As a practical example we select the domain of text mining and we concentrate on the challenging task of text document clustering using high dimensional sparse document-term matrices. Hence, we retain six popular benchmark text datasets, CLASSIC41 , LA12, the 20-newsgroups data NG20, SPORTS used in [START_REF] Zhong | Generative model-based document clustering: a comparative study[END_REF], NG2 and NG17-19 consisting respectively of two and three overlapping classes2 of NG20. All these datasets are carefully selected to represent various particular challenging situations in clustering: different degrees of cluster balance, different numbers of clusters, different sizes, different degrees of cluster overlap. The characteristics of these datasets are summarized in Table 6.1. Note that, in the above datasets, the true document cluster labels are available. The

Evaluation measures

Evaluating clustering results is not a trivial task, however, when the true category labels are known, a commonly used approach to validate clustering results consists in comparing the estimated partition with the true one. To this end, several measures have been proposed to assess the "similarity" between the estimated clustering and the true clustering. In our experiments we retain two widely used measures to assess the quality of clustering, namely the Normalized Mutual Information NMI [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] and the Adjusted Rand Index ARI [START_REF] Hubert | Comparing partitions[END_REF].

To assess cluster balancing we use three measures: the Standard Deviation in Cluster Sizes (SDCS) [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF], the ratio of minimum cluster size to the expected cluster size RME [START_REF] Banerjee | A generalized maximum entropy approach to bregman co-clustering and matrix approximation[END_REF]) and the Balance coefficient, i.e, the ratio of the minimum cluster size to the maximum cluster size. The latter makes it possible to know whether very small/large clusters are obtained.

Empirical results and discussion

In all our experiments we use the TF-IDF normalized data representation, in particular we use the TF-IDF weighting scheme proposed in Scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF]. For each dataset we set g to the real number of clusters, and in order to make consistent comparisons, all algorithms are initialized using the same random row partition. For our algorithm we further randomly initialize the column partition. Each algorithm is run until there is no significant increase of the optimized criterion.

Notice that, in the case of document-term matrices, during the first iterations, document clusters are mixed. Hence each word is involved to describe several document clusters, thus imposing hard word assignments at the beginning, as in Algorithm 8, could lead to a poor local solution. To avoid this difficulty, we perform a stochastic column assignment during the first 70% iterations of FSdbSkm as follows: for each column j select a cluster w j according to a Multinomial distribution M( w j1 , . . . , w jg ) where w jh ∝ 1 √ w .h cos(µ z h , x j ). Figure 6.1 illustrates the structure revealed by Skmeans and our algorithm FSdbSkeamns on the NG2 dataset. As we can see from this Figure, FSdbSkeamns not only reaches better performances in terms of NMI, ARI and Balance but also reveals a more interesting structure, i.e, block diagonal. Tables 6.2 and 6.3, summarize the results of the different methods in terms of NMI and ARI, over all datasets. All results are averaged over thirty different starting points, obtained using the initialization strategy described above. Between brackets, we report the result corresponding to the trial with the highest criterion. As these tables show clearly, our algorithm FSdbSkm provides substantially better results than the other vMF-based clustering algorithms. In particular when the data exhibits overlapping clusters as this is the case for NG2, CLASSIC4, NG20 and NG17-19. In fact, FSdbSkm is derived from a vMF-based model by assuming that clusters are not well separated, i.e., by assuming small concentration parameters. More interestingly, even when clusters are extremely unbalanced in nature, as in the SPORTS dataset, FSdbSkm provides high performances in terms of NMI and ARI. In fact, FSdbSkm tries to discover balanced clusters (see Table 6.4) without destroying the overall structure of data. Hence in such situation, the conscience mechanism of FSdbSkm has a regularizing effect that makes it possible to avoid poor solutions with empty or very large clusters. Moreover, as Tables 6.2, 6.3, 6.4 and 6.5 show, when clusters are naturally balanced as in NG2, NG17-19 and NG20 FSdbSkm yields substantially better performances in terms of all measures. Finally, Figure 6.2 shows that FSdbSkm offers a good trade off between cluster-balancing and quality of clustering. So far, we focused on document clustering but FSdbSkm offers word clusters as well. Each word cluster describes a single document cluster thereby easing semantic interpretations. Table 6.6 provides a typical example, where the four word clusters, discovered by FSdbSkm on CLASSIC4, are represented by their top 15 terms. The obtained word clusters are meaningful and help to make sense of the corresponding document clusters.

Conclusion and perspectives

In this chapter we proposed FSdbSkm, a novel co-clustering algorithm tailored for high dimensional sparse data. Unlike existing co-clustering algorithms, FSdbSkm is derived from a mixture of vMF distributions. It is more suitable than existing co-clustering methods for directional data distributed on a unit hypersphere, a typical situation in text mining where data are often normalized in order to remove the bias induced by the length of documents. Moreover, FSdbSkm, like Frequency Sensitive Competitive Learning, uses a conscience mechanism that penalizes larger clusters in order to avoid highly skewed solutions with very large/small clusters. Empirical results obtained on numerous real-world datasets show that FSdbSkm performs better than other strong baselines, which confirms the advantages of our approach. Moreover, even if balancing is not a requirement, the conscience mechanism of FSdbSkm has an interesting regularizing effect that makes it possible to avoid poor solutions.

Although the FSdbSkm algorithm is inspired by FSCL, it does not have the incremental behaviour of FSCL. Hence, possible future work could include further research to develop incremental and on-line variants of FSdbSkm that would be of great interest for applications, such as Collaborative Filtering (see chapter 2), where available data change frequently.

Conclusion and Perspectives

Through this thesis, we proposed and studied a novel class of clustering algorithms tailored for directional data distributed on the surface of a unit-hypersphere-L 2 normalized data. The algorithms studied in this thesis are derived from rigorous probabilistic models that build on the von Mises-Fisher (vMF) distribution from directional statistics [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF]. Our focus on the above modeling assumption is largely motivated by the substantial empirical evidence that some high dimensional sparse data sets, such as text and collaborative filtering (CF) data, posses intrinsic directional properties that match well with the modeling assumption of the vMF distribution. In fact, several previous studies in information retrieval have empirically demonstrated that directional measures such as the cosine similarity are superior to several other measures, such Euclidean distortions, for clustering text documents or assessing similarities between users (resp. items) in CF.

The main contributions and key results of this thesis can be summarized as follows:

-Chapter 2 exposes a scalable incremental variant of the spherical k-means algorithm suitable for CF, and which is able to handle effectively the frequent changes in the data such as submission of new ratings, update of existing ratings, appearance of new users and items. Extensive experiments conducted on popular benchmark data sets demonstrate the effectiveness and scalability of our method denoted as EICF. It offers a better quality of recommendations than other incremental CF systems while requiring less computation time, in both the static situation, where available data are kept unchanged, and dynamic situation, where new information are incorporated incrementally. In addition, to evaluate the performances of our approach under different circumstances, we also emphasized and illustrated why prediction metrics such as mean average error (MAE) and root mean square error (RMSE), widely used in the context of recommender systems, are inadequate to evaluate CF models. In fact, in many situation low MAE and RMSE do not necessarily equate to best user satisfaction.

-Chapter 3 presents a novel social collaborative filtering model which is based on the vMF assumption. The proposed model (Social-movMFs) is motivated by the benefits of both modeling CF data as directional data distributed on a unit-hypersphere and incorporating information from online social-networks so as to alleviate the sparsity related issues in CF. The Social-movMFs model is based on the natural assumption that socially connected users tend to share similar tastes. Indeed, in the physical world people usually turn to their friends, as they are familiar with their tastes, to ask for suggestions before choosing a movie, restaurant, book, etc. In this spirit, Social-movMFs simultaneously seeks for groups of users who tend to express similar preferences and brings the distributions over clusters (groups of users) of socially connected users closer to each other so as to capture the relations between users. An experimental study on various real-wold data sets, that include both the user-item preference matrix and the user-user social network, demonstrates the advantages of both the vMF modeling assumption and using social network information in order to alleviate the sparsity problem and improve CF performances, especially when there are many cold start users, i.e., who expressed very few ratings or even none at all.

-Chapter 5 describes a novel co-clustering model that is well suited for co-clustering L 2 normalized data. While existing co-clustering approaches are based on popular assumption such Gaussian, Multinomial or Bernoulli that are inadequate for L 2 normalized data, the proposed model dbmovMFs builds on the vMF assumption, that arises naturally for data lying on the surface of a unit-hypersphere, and successfully integrates a directional measure, namely the cosine similarity into a co-clustering framework. Hence, dbmovMFs leverages the advantages of both the co-clustering and the modeling assumption of the vMF distribution when dealing with high dimensional sparse data sets. Co-clustering by using the vMF distribution is not straightforward. Most existing co-clustering approaches are based on the principle of the latent block model (LBM) (Govaert andNadif, 2003, 2013) which uses univariate probability distributions; the vMF distribution, however, is a probability distributions of L 2 normalized vectors. In order to overcome the aforementioned difficulty, we moved the co-clustering into the centroid parameter of the vMF distribution by making some appropriate assumptions on its structure. In other words, by contrast to LBM-based co-clustering where an entire model is designed for co-clustering, in our case we are using a one-sided clustering model and put the co-clustering aim in the model parameters. The dbmovMFs can give rise to several new co-clustering algorithms, in this thesis we derived and studied six algorithms, including hard, soft and stochastic variants. Empirical results on numerous simulated and real-world data sets provide strong support for the effectiveness of our approach and the benefits of the vMF modelling assumption in the case of high dimensional sparse text data. The introduction of column clustering into a mixture of vMF distribution turns out to be very useful from several perspectives:

-In terms of inference it reduces substantially the complexity of the model regarding the number of free parameters to be estimated, which yields a parsimonious model and very scalable algorithms.

-It makes it possible to exploit the inherent duality between rows and columns which improves the performance, in terms of document clustering, of vMF-based mixture models noticeably, as illustrated in our experiments.

-It performs an implicitly adaptive dimensionality reduction at each stage, which makes possible to alleviate the high concentration parameter κ issue because of high dimensionality.

-It provides us with semantically coherent and directly interpretable results where each document cluster is described by a term cluster, which may also help to assess the number of clusters when the latter is not known, as emphasized in section 5.7.2.

-More interestingly, when assessing the number of clusters, the word cluster may be exploited so as to tune the number of cluster returned by well-established information criteria, AIC and AIC3, for model selection.

-Chapter 6 presents a novel co-clustering approach that uses a conscience mechanism in order to escape extremely skewed solutions, with very unbalanced or empty clusters, because of high dimensionality and sparsity, in particular when the number of desired clusters is large. The proposed algorithm FSdbSkm is derived from the dbmovMFs model, it is therefore well suited for L 2 normalized data. Empirical results obtained on several real-world data sets show that FSdbSkm succeeds in avoiding bad local solutions with very unbalanced clusters sizes and performs substantially better than other strong baselines. More interestingly, even when the balancing is not a requirement, and the clusters are by nature very unbalanced, the conscience mechanism of FSdbSkm is still of great interest. In such situation, instead of destroying the natural cluster structure of the data so as to provide balanced clusters, the conscience mechanism acts as a regularizer that prevents from poor locally optimal solutions. This behaviours suggests that FSdbSkm seeks for balanced clusters but not to the detriment of the inherent structure of data.

Overall, the results from our thesis highlight the importance of accounting for the intrinsic directional properties of some high dimensional sparse data sets such as those encountered in text mining and collaborative filtering. Relying on the directional assumption allows us to develop not only very effective but also very scalable algorithms, which are well suited for handling high dimensionality and sparsity.

The studies presented in this thesis motivate further investigations that may include -Incorporating context-aware information [START_REF] Tang | Social recommendation: a review[END_REF][START_REF] Bobadilla | Recommender systems survey. Knowledge-Based Systems[END_REF] such as time into EICF and Social-movMF so as to handle the sparsity problem even more effectively and thereby improve recommendations. Because the sparsity in CF is caused by missing (or unobserved) ratings, and both EICF and Social-movMF are based on mixture models, another possibility to better address the sparsity problem is to rely to well-established statistical theory of missing data analysis [START_REF] Little | Statistical analysis with missing data[END_REF].

-Extend dbmovMFs to collaborative filtering in order to treat the sets of users and items simultaneously. This would be useful for several reasons: the dimensionality reduction property of dbmovMFs will help to alleviate the sparsity and develop very scalable CF systems, it will provide us with more interpretable results by grouping users and items into meaningful clusters, i.e., each group of users may be described by a cluster of items they prefer, and vice versa. Moreover the social component of Social-movMFs can be easily incorporated into dbmovMFs in order to account for social interactions among users in the latter.

-It is interesting to consider a Bayesian formulation of dbmovMFs [START_REF] Gopal | Von mises-fisher clustering models[END_REF] that would enable sharing of information between co-clusters, consider a soft column partition w and, more interestingly, allow the number of co-clusters to be determined automatically as part of the learning process.

-The von Mises-Fisher distribution is one of the simplest distributions for directional data lying on the surface of a unit-hypersphere, and other distributions from directional statistics deserve to be considered. For instance the Kent distribution [START_REF] Mardia | Directional statistics. Wiley series in probability and statistics[END_REF], which is the analogous on a unit-hypersphere of the multivariate Gaussian distribution with an unconstrained covariance matrix, is more sophisticated than the vMF distribution and can model clusters of more flexible shapes. Nevertheless, it is substantially more difficult to work with a high dimensional Kent distribution regarding parameter estimation.

In the same manner, to maximize expectation (A.1) with respect to µ w h , subject to the constraint (µ w h ) T µ w h = 1, we form the corresponding Lagrangian by isolating the terms which depends on µ w h , this leads to L(µ, λ ) = ∑ h,i, j zih w jh κ h µ hh x i j + λ h (1 -∑ j w jh µ 2 hh )

Taking the derivative with respect to µ hh , we obtain:

∂ L(µ, λ ) ∂ µ h = ∑ i, j
zih w jh κ h x i j -2λ w .h µ hh where w .h = ∑ j w jh . Setting this derivative to zero, we obtain λ µ hh = ∑ i, j zih w jh κ h x i j 2w .h

. Thus, λ 2 µ 2 hh = (∑ i, j zih w jh κ h x i j ) 2 4w 2

.h

.

Multiplying both sides by w .h , yields:

λ 2 w .h µ 2 hh =
(∑ i, j zih w jh κ h x i j ) 2 4w .h . (A.4)

Hence, we obtain λ = κ h √ w .h (∑ i, j zih w jh x i j ) 2 2w .h = κ h ∥r w h ∥ 2w .h where r w h is a d dimensional vector, i.e, let j ′ = 1, . . . , d, r w h j ′ = r w h = ∑ i, j zih w jh x i j if w jh = 1 and r w h j ′ = 0, otherwise. Hence, the maximizing value of the parameter µ hh is given by: μhh = ∑ i, j zih w jh x i j ∥r w h ∥ = ∑ i, j zih w jh x i j w .h (∑ i, j zih w jh x i j ) 2

= ± 1 √ w .h (A.5) according to whether r w h = ∑ i, j zih w jh x i j is positive or negative. It follows from equation (A.5) that given the column partition w and the sign of r w h , the centroid parameter µ w h can be deduced directly.

Next we concentrate on maximizing equation (A.1), with respect to the concentration parameters κ h , subject to the constraint κ h > 0, ∀h. The Lagrangian up to terms which do not contains κ h is given by L(κ) = ∑ h z.h log(c d (κ h )) + ∑ h,i, j zih w jh κ h μhh x i j note that, by KKT conditions, the Lagrangian multiplier for the constraint κ h > 0 has to be equal to zero. Taking the partial derivative of equation (A.6) with respect to κ h , we obtain

∂ L(κ) ∂ κ h = z.h c ′ d (κ h ) c d (κ h ) + ∑ i, j
zih w jh μhh x i j

Setting this derivative equal to zero, leads to: The latter equation (A.7), arises from the use of the following recurrence formula [START_REF] Abramowitz | Handbook of mathematical functions: with formulas, graphs, and mathematical tables[END_REF], page 376):

c ′ d (κ h ) c d (κ h ) = - μhh × ∑ i,
κ h I s+1 (κ h ) = κ h I ′ s (κ h ) -sI s (κ h ). (A.8)
Note that computing the maximizing value κh from equation (A.6) implies to inverse a ratio of Bessel function, a problem for which no a closed-form solution can be obtained. Thus, following (Banerjee et al., 2005b), we propose to derive an accurate approximation of the concentration parameter, by using the following continued fraction formula: (A.10)

I d/2 (κ h ) I d/2-1 (κ h ) = 1 d κ h + 1

A.2 Concentration parameters: dbmovMFs vs movMFs

Hereafter, we provide the proofs for Proposition 1 and Theorem 1. Recall that as opposed to the classical movMFs where it is easy to verify that rh ≤ 1 (see equation 6c) given the definition of r, it is not straightforward to verify that rw h ≤ 1, without careful analysis. Proposition 1 provides theoretical guarantee about the fact that 0 ≤ rw h ≤ 1, which is imperative, to guarantee that the concentration parameters are positive, i.e, κ h > 0 , ∀h, specially when using the approximation of equation (A.10). The following Proposition is useful and necessary to prove both Proposition 1 and Theorem 1. r ′ h is a w .h dimensional sub vector of r h , it follows from the above definition that r′ h ≤ rh . On the other hand, rw h = ∥r w h ∥ ∑ i zih ∑ j ŵ jh where r w h denotes a w .h dimensional vector, each its elements are equal to sum of elements of the h th co-cluster (i.e, r w h1 = • • • = r w hw .h = r w h = ∑ i, j zih ŵ jh x i j ), similarly we can show that each elements of r w h are equal to sum of elements of r ′ h (i.e, r w h = ∑ j r ′ h j ). Hence using Proposition 3, where the dimensionality d = w .h , we have

∥r w h ∥ ∑ j ŵ jh ≤ ∥r ′ h ∥ thus, rw h = ∥r w h ∥ ∑ i zih ∑ j ŵ jh ≤ r′ h = ∥r ′ h ∥ ∑ i zih ≤ rh Thereby, rw h d 1 -rw h 2 ≤ rh d 1 -(r h ) 2 .
We now show that, rw

h d -(r w h ) 3 1 -rw h 2 ≤ rh d -r3 h 1 -(r h ) 2 .
As rw h ≤ rh we have 1-(r h ) 2 , then it is sufficient to demonstrate that,

rw h d -(r w h ) 3 1 -(r h ) 2 ≤ rh d -r3 h 1 -(r h ) 2 .
We have

rw h d -(r w h ) 3 1 -(r h ) 2 - rh d -r3 h 1 -(r h ) 2 = d(r w h -rh ) + (r 3 h -(r w h ) 3 ) 1 -(r h ) 2 .
Based on Lemma 1, for all d ≥ 3 we have r3 h -(r w h ) 3 ≤ d rw h -rh . As rw h ≤ rh it is easy to verify that d(r w h -rh ) + (r 3 h -(r w h ) 3 ) ≤ 0.

Based on the fact that 1 -(r h ) 2 > 0 we have rw h d-(r w h ) 3

1-(r h ) 2 ≤ rh d-r 3 h 1-(r h ) 2 . Hence, using the above inequalities we get (for all d ≥ 3)

rw h d -(r w h ) 3 1 -rw h 2 ≤ rh d -r3 h 1 -(r h ) 2 .

A.3 Computational Complexity in the Worst Case

Hereafter, we provide the proofs for the computational complexity of (ii) soft-dbmovMF (EM b ) and (iii) hard-dbmovMF (CEM b ) given in Proposition 2 (section 5.6).

Proof (ii). The computational bottleneck for hard-dbmovMF is with row, column assignments and concentration parameters updates. From Proposition 2 (i), the total cost of row and column assignments is O(it • nz). We show that the computational cost for updating concentration parameters is O(it • nz). The main computation for updating the h th concentration parameter is with the computation of r w h . The computational cost of the latter term is given in O(x * h ), where x * h the number of non-zeros entries in the h th co-cluster. Thus, the complexity for updating all concentrations parameters is O(nz), based on O(x * 1 + • • • + x * g ) and the fact that at most all non-zeros entries in the matrix X are contained in the g diagonal co-clusters. Hence, the cost for updating the concentration parameters in hard-dbmovMF is O(it • nz), thereby the total cost of hard-dbmovMF is O(it • nz).

Proof (iii). As for hard-dbmovMF it is easy to verify that the total cost of row assignments and concentration parameters updates is given in O(it • nz) for soft-dbmovMF. Now we prove that in contrast to hard-dbmovMF the computational cost of column assignments for soft-dbmovMF is O(it • g • nz). The computational bottleneck for column assignment step of soft-dbmovMF is with the terms v h j ← ∑ i zih x i j , h ∈ {1, . . . , g}, j ∈ {1, . . . , d}. The cost of v h j is given in O(x * j ), where x * j is the number of non-zeros entries in the j th column. During the column assignment step for each cluster h and column j we compute v h j , hence the computational cost of this step is given in O(g • nz). Therefore, the total computational cost of soft-dbmovMF is O(it • g • nz), based on O(it • nz • (g + 1)).

Introduction 1 . 1

 11 An indexed hierarchy represented as a dendrogram . . . . . . . . . . . . . 1.2 Illustration of graph clustering in social networks. The graph corresponds

1 . 3

 13 Gaussian Mixture in R 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Assessing the number of clusters for EICF on different datasets, using F1 metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Evaluation of several recommender systems on ML-100k dataset (static situation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Evaluation of several recommender systems on the ML-1M dataset (static situation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Evaluation of several recommender systems on Epinions dataset (static situation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Comparison of training + prediction time on ML-1M subsets. . . . . . . . . 2.6 Evaluation of several RS on ML-100k dataset (Dynamic situation). . . . . . 2.7 Evaluation of several recommender systems on ML-1M dataset (Dynamic situation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Evaluation of several CF systems on the Epinions dataset (Dynamic situation ). 3.1 Three sample of 100 points according to three 2-vMF distributions, with different concentration parameters, and the same mean direction µ = (1/ √ 2, 1/ √ 2). The segment starting from the circle centre denotes the mean direction of each vMF distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 movMFs as a graphical model. . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Comparison of average nDCG over different datasets. . . . . . . . . . . . 3.4 Comparison of average MRR over different datasets. . . . . . . . . . . . . 3.5 Comparison of average Precision@10 over different datasets. . . . . . . .xviii List of figures 3.6 Comparison of average Recall@10 over different datasets. . . . . . . . . . 3.7 % of cold start users in the user-item matrix (Preference) and social-network (Social). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Cold start users : distribution of out degree, i.e., the number of social interactions per cold start user, over the different datasets . . . . . . . . . . 3.9 Impact of the number of clusters g. . . . . . . . . . . . . . . . . . . . . . 3.10 Impact of the regularization parameter λ . . . . . . . . . . . . . . . . . . . 4.1 Binary table reorganized according to the row and column partitions . . . . 4.2 Binary data and its associated bipartite graph . . . . . . . . . . . . . . . . 4.3 LBM's graphical model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 A co-clustering obtained by using EM b (soft-dbmovMF): (left) original data, (middle) data reorganized according to z, (right) data reorganized data according (z, w) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Graphical models: left movMFs (Banerjee et al., 2005b), right dbmovMFs (proposed model). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Von Mises-Fisher mixture models-based clustering (left) and co-clustering (right) algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Simulated datasets reorganized according to row and column partitions: (a) sdata1, (b) sdata2, (c) sdata3, (d) sdata4 (e) sdata5. . . . . . . . . . . . . . 5.5 Behaviour of log-likelihood over iterations, on the different datasets. . . . . 5.6 Best NMI and ARI over all datasets for each method. Our algorithms provide good performances in terms both NMI and ARI while movMFsbased approach sometimes provide good NMI but low ARI. For instance, on SPORTS EM b provides NMI = 0.62 and ARI = 0.61 while SKmeans provides NMI = 0.63 and ARI = 0.44. (see confusion matrices of Table 5.7) 5.7 Visualization of SPORTS dataset: (a) original, (b) reorganized according to Skmeans's row partition, (c) reorganized according to EM b 's row and column partitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Distribution of concentration parameters . . . . . . . . . . . . . . . . . . . 5.9 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the CSTR dataset (True number of classes: 4). . . . . 5.10 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the CLASSIC4 dataset (True number of classes: 4). . 5.11 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the WEBACE dataset (True number of classes: 20). . 5.12 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the NG20 dataset (True number of classes: 20). . . . 5.13 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the SPORTS dataset (True number of classes: 7). . . 5.14 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the TDT2 dataset (True number of classes: 30). . . . 6.1 NG2 dataset (Balance = 1). Left: original, middle: reorganized according to Skmeans result(NMI = 0.57, ARI = 0.67, Balance = 0.73), right: Reorganized according to FSdbSkm results(NMI = 0.74, ARI = 0.83, Balance = 0.98). . . 6.2 Left Balance vs NMI, Righ Balance vs ARI. The circles denote the scores recorded by FSdbSkm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Data matrix X and associated row and column partitions indicated respectively by the representations z and Z, w and W, with g = 3. . . . . . . . . 2.1 Comparison of MAE and RMSE achieved by three recommender systems, on a small example (numbers in bold correspond to best performances). . . 2.2 Comparison of computational times (in the worst case) in various situations. W * denotes the number of observed ratings in U. g and m are the number of row and column clusters, k denotes the number of neighbours for memory CF (IUCF, IICF). d * is the number of observed ratings for a new user, n * denotes the number of available ratings for a new item. Finally, B denotes the number of iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Computation time comparison in the dynamic scenario (in sec). . . . . . . . 3.1 Description of Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Comparison of Average recommendation accuracy over different datasets. "Improve" indicates the improvement reached by the proposed social model Soc-movMF relative to performance of the traditional movMF model. . . . . . 3.3 Comparison of Average recommendation accuracy on cold start userswith 5 or fewer ratings-over different datasets. "Improve" indicates the improvement reached by the proposed social model Soc-movMF relative to the performance of movMF. . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Computational complexity of different algorithms (in the worst case). nz denotes the number of non-zero entries in the matrix X, g is the number of clusters (co-cluster) and it denotes the number of iterations. . . . . . . . . . 5.2 Comparison of true and estimated parameters by our algorithms on different simulated dataset, (α,κ,µ) denote the true parameters while ( α, κ, μ) denote the estimated parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Description of Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 1 . 1

 11 Fig. 1.1 An indexed hierarchy represented as a dendrogram

Fig. 1 . 3

 13 Fig. 1.3 Gaussian Mixture in R 2

Fig. 2 . 1

 21 Fig. 2.1 Assessing the number of clusters for EICF on different datasets, using F1 metric.

Figure 2 .

 2 Figure 2.2 shows the ROC-curves and F1 comparisons of the different CF methods on the ML-100k dataset. The ROC-curves in Figure 2.2a are built by varying the size of the top-N recommendation list and representing the TPR and FPR of each CF for the different lists. The longest list contains 40 elements. In Figure 2.2b the F-measure of each method is represented over the different lists. All other ROC-curves and F1 comparisons are built in the same way.From figures 2.2a and 2.2b we note that on the ML-100k dataset our method EICF provides a high quality of recommendations, thanks to our approach for alleviating the sparsity

Fig. 2 . 2 Fig. 2 . 3

 2223 Fig. 2.2 Evaluation of several recommender systems on ML-100k dataset (static situation).

Figure 2 .

 2 Figure 2.3 shows that with the ML-1M dataset our method achieves a high quality of recommendations, and still outperforms all other methods, just like with the ML-100k dataset, which confirms the stability of our approach.Figure2.4 shows the evaluation of the different collaborative filtering systems, on the Epinon dataset in the static situation. In Figures 2.4a and 2.4b EICF provides the best performances. Also, both figures show an important decline in the performances of the other incremental CF systems, especially COCLUST and IICF. The low recommendation quality of

Fig. 2 . 4 Fig. 2 . 5

 2425 Figure 2.3 shows that with the ML-1M dataset our method achieves a high quality of recommendations, and still outperforms all other methods, just like with the ML-100k dataset, which confirms the stability of our approach.Figure2.4 shows the evaluation of the different collaborative filtering systems, on the Epinon dataset in the static situation. In Figures 2.4a and 2.4b EICF provides the best performances. Also, both figures show an important decline in the performances of the other incremental CF systems, especially COCLUST and IICF. The low recommendation quality of

Fig. 2 . 6 Fig. 2 .

 262 Fig. 2.6 Evaluation of several RS on ML-100k dataset (Dynamic situation).

Fig. 2 .

 2 Fig. 2.8 Evaluation of several CF systems on the Epinions dataset (Dynamic situation ).

Figure 2 .

 2 Figure 2.8 gives the ROC-curves and F1 comparison on Epinions dataset, in the dynamic situation. From Figures 2.8aand 2.8b we can note that EICF outperforms the other methods.We can also note a significant decrease in the performances of IICF and COCLUST; a poor recommendation for both methods in all the recommendation lists (TPR ≃ 0, for all the lists).

  Figure 2.8 gives the ROC-curves and F1 comparison on Epinions dataset, in the dynamic situation. From Figures 2.8aand 2.8b we can note that EICF outperforms the other methods.We can also note a significant decrease in the performances of IICF and COCLUST; a poor recommendation for both methods in all the recommendation lists (TPR ≃ 0, for all the lists).

Fig. 3 . 1

 31 Fig. 3.1 Three sample of 100 points according to three 2-vMF distributions, with different concentration parameters, and the same mean direction µ = (1/ √ 2, 1/ √ 2). The segment starting from the circle centre denotes the mean direction of each vMF distribution.

Fig. 3 . 4 FilmTrustFig. 3 . 5 FilmTrustFig. 3 . 6

 343536 Fig. 3.4 Comparison of average MRR over different datasets.

Fig. 3 .

 3 Fig. 3.7 % of cold start users in the user-item matrix (Preference) and social-network (Social).

Fig. 3 .

 3 Fig. 3.8 Cold start users : distribution of out degree, i.e., the number of social interactions per cold start user, over the different datasets

FilmTrustFig. 3 .

 3 Fig. 3.9 Impact of the number of clusters g.

FilmTrustFig. 3 .

 3 Fig. 3.10 Impact of the regularization parameter λ .

Fig. 4 .

 4 Fig. 4.1 Binary table reorganized according to the row and column partitions

Fig. 4 .

 4 Fig. 4.3 LBM's graphical model

Fig. 5 .

 5 Fig. 5.1 A co-clustering obtained by using EM b (soft-dbmovMF): (left) original data, (middle) data reorganized according to z, (right) data reorganized data according (z, w)

Fig. 5 . 3

 53 Fig. 5.3 Von Mises-Fisher mixture models-based clustering (left) and co-clustering (right) algorithms.

Fig. 5 . 4

 54 Fig. 5.4 Simulated datasets reorganized according to row and column partitions: (a) sdata1, (b) sdata2, (c) sdata3, (d) sdata4 (e) sdata5.

Figure 5 .

 5 5 illustrates the behaviour of SAEM b and its advantage compared to SEM b , the same behaviour is observed for CAEM b .

Fig. 5 . 5

 55 Fig. 5.5 Behaviour of log-likelihood over iterations, on the different datasets.

Fig. 5 . 6 Fig. 5 .

 565 Fig. 5.6 Best NMI and ARI over all datasets for each method. Our algorithms provide good performances in terms both NMI and ARI while movMFs-based approach sometimes provide good NMI but low ARI. For instance, on SPORTS EM b provides NMI = 0.62 and ARI = 0.61 while SKmeans provides NMI = 0.63 and ARI = 0.44. (see confusion matrices of Table5.7)

Fig. 5 .

 5 Fig. 5.8 Distribution of concentration parameters

Fig. 5 .

 5 Fig. 5.9 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the CSTR dataset (True number of classes: 4).

Fig. 5 .

 5 Fig. 5.10 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the CLASSIC4 dataset (True number of classes: 4).

Fig. 5 .

 5 Fig. 5.12 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the NG20 dataset (True number of classes: 20).

Fig. 5 .

 5 Fig. 5.13 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the SPORTS dataset (True number of classes: 7).

Fig. 5 .

 5 Fig. 5.14 Behaviour of the log-likelihood, AIC, AIC3 and BIC when varying the number of clusters on the TDT2 dataset (True number of classes: 30).

Fig. 6 .

 6 Fig. 6.1 NG2 dataset (Balance = 1). Left: original, middle: reorganized according to Skmeans result(NMI = 0.57, ARI = 0.67, Balance = 0.73), right: Reorganized according to FSdbSkm results(NMI = 0.74, ARI = 0.83, Balance = 0.98).

Fig. 6 . 2

 62 Fig. 6.2 Left Balance vs NMI, Righ Balance vs ARI. The circles denote the scores recorded by FSdbSkm.

Proposition 3

 3 Let r be a non-zero vector in R d (i.e., r = (r 1 , . . . , r d ) T , such as d ≥ 1). Let r d be a vector in R d , such as all its component are equal to the sum of elements of r (i.e, r d = ∑ d j=1 r j ✶ where ✶ denotes the constant one vector). Then ∥r d ∥ d ≤ ∥r∥ with equality only if all components of r are equal (i.e, r 1 = • • • = r d ). Proof. Let d and r + be two vectors in R d defined as follows: d = 1 √ d ✶ and r + with r + j = |r j |, ∀ j ∈ {1, . . . , d}. We have d T .r + = ∥d∥∥r + ∥ cos(d, r + ). By definition of r + and d, we have ∥r + ∥ = ∥r∥ and ∥d∥ = 1, hence ∥r d ∥ d ≤ ∥r∥ cos(d, r + ). Since both d and r + are non-zero vectors and lie on the first orthant of a d-dimensional unit hypersphere, by dividing both sides of the above inequality by ∥r∥, we get 0 ≤ ∥r d ∥ d∥r∥ ≤ cos(d, r + ) ≤ 1 Parameters Estimation as both a and b are in[0, 1-k b k ≤ n |a -b| Theorem 1 Let X be a n × d matrix, its i th row (object) x i is a d-dimensional unit vector in S d-1 (i.e, x i ∈ R d and ∥x i ∥ = 1 , ∀i ∈ {1, . . . , n} , n ≥ 2, d ≥ 3). Let z = (z 1 , . . . , z n )denote a partition of the set of objects of X into g disjoint clusters. Then, whatever the partition w of attributes of X into g disjoints clusters, the concentration parameter of each dbvMF component estimated via approximation(5.6d) is always less or equal to the concentration parameter of the corresponding vMF component estimated via approximation(3.13c

  consists in finding the K nearest neighbors of each item and making recommendations according to the neighborhood of items enjoyed by the user u a . The most commonly used similarity measures in these approaches are Cosine

	Similarity (COS), Pearson Correlation Coefficient (PCC) and Jaccard. In addition to these
	traditional measures, a number of other similarity measures have been proposed in this
	context: Adjusted COS, Adjusted PCC, Constrained COS, Constrained PCC, Jaccard
	Mean Square Difference, PIP similarity (Ahn, 2008), NHSM similarity (Liu et al., 2014),
	etc.
	-Model based CF: these approaches begin by suggesting a model that will learn from the
	user/item rating matrix U in order to capture the hidden features of the users and items.
	Then, they predict the missing ratings according to this model. Many model-based CF
	techniques have been proposed, the most popular being those based on clustering (Ungar

  g is the number of clusters, B is the number of batch iterations. Output: g centroids µ h in R p , the partition of the objects represented by z = (z 1 , . . . , z n ) ⊤ where z i ∈ {1, . . . , g}.

	Steps:
	1. Initialization: t = 0, random normalized cluster centroids {µ 1 , . . . , µ g }; for b = 1 to B do
	for i = 1 to n do
	2. Assignment step: for each object u i , compute z i = arg max h (u ⊤ i µ h ); 3. Update of Centroids step: compute the winner centroid µ new z i = µ z i +ηu i ∥µ z i +ηu i ∥ ; t = t + 1
	end for
	end for

Table 2 .

 2 [START_REF] Salah | Stochastic Co-clustering for Document-Term Data[END_REF] Comparison of MAE and RMSE achieved by three recommender systems, on a small example (numbers in bold correspond to best performances). Furthermore, in terms of MAE and RMSE, RS1 and RS3 are equivalent, nevertheless RS1 is clearly better than RS3, in terms of recommendation quality.Another category of evaluation metrics used in RS are those known in the field of CF as recommendation metrics, and they include: Receiver Operating Characteristic (ROC),

			item1	item2
	True ratings	active user (u a )	u a1 = 2	u a2 = 4	MAE	RMSE
		RS1	1	5	1.0	1.0
	Predicted ratings	RS2	2	3	0.5	0.71
		RS3	3	3	1.0	1.0
	is 4.

Table 2 .

 2 3 Computation time comparison in the dynamic scenario (in sec).

	datasets	CF methods.	Computation time (sec)
		EICF	0.51
	ML-100k	IUCF IICF	1.78 0.88
		COCLUST	0.97
		EICF	2.86
	ML-1M	IUCF IICF	138.1 7.96
		COCLUST	11.85
		EICF	149.20
	Epinions	IUCF IICF	4041.01 927.22
		COCLUST	212.71

Table 3 .

 3 1 Description of Datasets

	Characteristics	Datasets FilmTrust CiaoDVD Ciao-280k Flixster Epinions
	#Users	1,508	17,615	7,375	147,612	40,163
	#Items	2,071	16,121	106,797	48,794	139,738
	#Ratings	35,497	72,665	284,052	8,196,077 664,824
	Density	1.14%	0.026%	0.04	0.114%	0.01%
	ratings-scale	[0.5,4]	[1,5]	[1,5]	[0.5,5]	[1,5]
	#links	1,853	22,484	111,781	2,538,746 442,979
	links-type	trust	trust	trust	friendship trust
	Network-density 0.08%	0.01%	0.2%	0.011%	0.029%

Table 3 .

 3 2 Comparison of Average recommendation accuracy over different datasets. "Improve" indicates the improvement reached by the proposed social model Soc-movMF relative to performance of the traditional movMF model.Fig. 3.3 Comparison of average nDCG over different datasets.

	Dataset	Measure TrustSVD TrustMF SocialMF RSTE SoRec SoReg movMF Soc-movMF Improve
		nDCG	0.1764	0.1679	0.2040	0.4612 0.1833 0.4658 0.6291	0.6626	5.05%
	FilmTrust	MRR Prec@10	0.0142 0.0029	0.0142 0.0090	0.0799 0.0117	0.3926 0.0829 0.3664 0.5843 0.1807 0.0087 0.2069 0.3218	0.6311 0.3385	7.41% 4.93%
		Rec@10	0.0048	0.0219	0.0242	0.3215 0.0194 0.3391 0.5785	0.6215	6.92%
		nDCG	0.1085	0.1023	0.1149	0.1236 0.1149 0.1283 0.1451	0.1527	4.98%
	CiaoDVD	MRR Prec@10	0.0062 0.0012	0.0062 0.0014	0.0124 0.0024	0.0214 0.0122 0.0139 0.0252 0.0059 0.0025 0.0024 0.0059	0.0335 0.0077	24.8% 23.4%
		Rec@10	0.0059	0.0090	0.0141	0.0384 0.0143 0.0172 0.0351	0.0455	22.9%
		nDCG	0.1206	0.1117	0.1158	0.1094 0.1172 0.1157 0.1690	0.1820	7.14%
	Ciao-280k	MRR Prec@10	0.0079 0.0012	0.0009 0.0001	0.0053 0.0009	0.0005 0.0068 0.0065 0.0653 0.0001 0.0012 0.0006 0.0199	0.0907 0.0256	28.0% 22.3%
		Rec@10	0.0016	0.0002	0.0013	0.0002 0.0019 0.0016 0.0243	0.0380	36.1%
		nDCG	0.1071	0.1004	0.1021	0.0953 0.0944 0.1113 0.1438	0.1508	4.64%
	Epinions	MRR Prec@10	0.0037 0.0006	0.0094 0.0021	0.0045 0.0009	0.0016 0.0021 0.0047 0.0263 0.0002 0.0004 0.0005 0.0069	0.0409 0.0097	35.7% 28.9%
		Rec@10	0.0013	0.0053	0.0022	0.0006 0.0010 0.0017 0.0169	0.0229	26.2%
		nDCG	0.1800	0.1277	0.1399	0.1289 0.1397 0.2768 0.2072	0.3547	41.6%
	Flixster	MRR Prec@10	0.0376 0.0137	0.0005 0.0002	0.0157 0.0016	0.0004 0.0157 0.1237 0.0497 0.0001 0.0016 0.0313 0.0113	0.2382 0.0948	79.1% 88.1%
		Rec@10	0.0116	0.0000	0.0104	0.0000 0.0105 0.0924 0.0045	0.1635	97.2%

Table 3 .

 3 [START_REF] Salah | Classification Croisée via un Modèle de Mélange de von Mises-Fisher[END_REF] Comparison of Average recommendation accuracy on cold start users-with 5 or fewer ratings-over different datasets. "Improve" indicates the improvement reached by the proposed social model Soc-movMF relative to the performance of movMF.

	Datasets	Measures	movMF	Soc-movMF	Improve
		nDCG	0.4534	0.4663	2.75%
	FilmTrust	MRR Prec@10	0.3457 0.0731	0.3572 0.0843	3.21% 13.3%
		Rec@10	0.4760	0.5471	13.0%
		nDCG	0.1409	0.1459	3.40%
	CiaoDVD	MRR Prec@10	0.0271 0.0058	0.0317 0.0062	14.5% 6.62%
		Rec@10	0.0487	0.0519	6.09%
		nDCG	0.1203	0.1344	10.5%
	Ciao-280k	MRR Prec@10	0.0201 0.0041	0.0431 0.0073	53.3% 42.9%
		Rec@10	0.0185	0.0375	50.6%
		nDCG	0.1102	0.1127	2.17%
	Epinions	MRR Prec@10	0.0125 0.0022	0.0161 0.0032	22.0% 31.1%
		Rec@10	0.0152	0.0218	30.1%
		nDCG	0.1142	0.3106	63.2%
	Flixster	MRR Prec@10	0.0047 0.0003	0.1848 0.0394	97.5% 99.2%
		Rec@10	0.0023	0.3209	99.3%

Table 5 .

 5 2 Comparison of true and estimated parameters by our algorithms on different simulated dataset, (α,κ,µ) denote the true parameters while ( α, κ, μ) denote the estimated parameters.

	Data sdata1	Components cluster1 cluster2 cluster3	α 0.34 0.33 0.33	True Parameters κ 500.00 1/ µ hh √ 340 500.00 1/ √ 330 500.00 1/ √ 330	Algorithms CEM b EM b CEM b EM b CEM b EM b	α 0.339 0.339 0.328 0.329 0.333 0.332	Parameter Estimation |α -α| κ |κ -κ| 0.001 501.38 1.38 0.001 499.87 0.13 0.002 500.90 0.90 0.001 499.33 0.67 0.003 500.56 0.56 0.002 500.42 0.42	µ T μ 1.00 1.00 1.00 1.00 1.00 1.00
	sdata2	cluster1 cluster2 cluster3	0.70 0.25 0.05	320.00 400.00 500.00	1/ √ 1/ √ 1/ √	340 330 330	CEM b EM b CEM b EM b CEM b EM b	0.691 0.700 0.261 0.250 0.048 0.050	0.009 0.00 0.011 0.00 0.002 0.00	320.72 319.62 398.23 401.51 497.75 499.28	0.72 0.38 1.77 1.51 2.25 0.72	1.00 1.00 1.00 1.00 1.00 1.00
	sdata3	cluster1 cluster2 cluster3	0.34 0.33 0.33	320.00 400.00 500.00	1/ √ 1/ √ 1/ √ 700 250 50	CEM b EM b CEM b EM b CEM b EM b	0.345 0.345 0.330 0.330 0.325 0.325	0.005 0.005 0.00 0.00 0.005 0.005	319.82 319.83 399.11 399.30 487.82 500.40	0.18 0.17 0.89 0.70 12.18 0.40	0.998 1.00 1.00 1.00 0.980 1.00
	sdata4	cluster1 cluster2 cluster3	0.70 0.250 0.05	320.00 400.00 500.00	1/ √ 1/ √ 1/ √ 700 250 50	CEM b EM b CEM b EM b CEM b EM b	0.697 0.702 0.254 0.248 0.049 0.05	0.003 0.002 0.004 0.002 0.001 0.00	320.20 320.10 400.37 399.77 498.10 501.12	0.20 0.10 0.37 0.23 1.90 1.12	1.00 1.00 1.00 1.00 1.00 1.00
	sdata5	cluster1 cluster2 cluster3	0.34 0.33 0.33	70.00 70.00 70.00	1/ √ 1/ √ 1/ √	340 330 330	CEM b EM b SEM b SAEM b CEM b EM b SEM b SAEM b CEM b EM b SEM b SAEM b	0.34 0.34 0.33 0.33 0.330 0.340 0.33 0.33 0.330 0.320 0.34 0.34	0.00 0.00 0.01 0.01 0.00 0.01 0.00 0.00 0.00 0.01 0.01 0.01	59.22 45.43 53.68 69.96 55.66 43.41 58.69 70.38 53.39 43.00 55.12 70.13	10.78 24.57 16.32 0.04 14.34 26.59 11.31 0.38 16.61 27.00 14.88 0.13	0.334 0.387 0.793 0.991 0.430 0.339 0.850 0.995 0.487 0.388 0.805 0.989

Table 5 .

 5 3 Description of Datasets

	Datasets	Characteristics #Documents #Words #Clusters Sparsity (%) Balance 3
	CSTR	475	1000	4	96.60	0.399
	WEBACE	2340	1000	20	91.83	0.169
	CLASSIC4	7094	5896	4	99.41	0.323
	NG20	19949	43586	20	99.82	0.991
	SPORTS	8580	14870	7	99.14	0.036
	TDT2	9394	36771	30	99.64	0.028

Table 5 .

 5 4 Comparison of average NMI and ARI, on CSTR, CLASSIC4 and WEBACE datatsets.

		CSTR	CLASSIC4	WEBACE
		NMI	ARI	NMI	ARI	NMI	ARI
	Skmeans	0.732±0.026 (0.759)	0.772±0.025 (0.807)	0.591±0.020 (0.595)	0.468±0.011 (0.476)	0.613±0.008 (0.620)	0.423±0.026 (0.394)
	CEM	0.734±0.025 (0.759)	0.774±0.024 (0.807)	0.413±0.011 (0.410)	0.199±0.018 (0.194)	0.619±0.011 (0.623)	0.398±0.021 (0.412)
	EM	0.741±0.026 (0.768)	0.777±0.026 (0.808)	0.406±0.013 (0.403)	0.190±0.015 (0.184)	0.614±0.014 (0.623)	0.385±0.034 (0.397)
	DAEM	0.779±0.013 (0.783)	0.813±0.014 (0.817)	0.591±0.002 (0.592)	0.471±0.002 (0.472)	0.620±0.008 (0.628)	0.427±0.022 (0.468)
	dbSkmeans	0.753±0.016 (0.771)	0.803±0.014 (0.816)	0.647±0.002 (0.653)	0.460±0.002 (0.464)	0.616±0.008 (0.620)	0.469±0.033 (0.507)
	CEM b	0.754±0.024 (0.789)	0.804±0.022 (0.830)	0.660±0.003 (0.665)	0.467±0.003 (0.473)	0.623±0.011 (0.637)	0.479±0.038 (0.519)
	EM b	0.754±0.022 (0.792)	0.803±0.022 (0.837)	0.660±0.002 (0.668)	0.466±0.002 (0.473)	0.624±0.008 (0.639)	0.481±0.025 (0.523)
	SEM b	0.776±0.022 (0.807)	0.820±0.024 (0.846)	0.691±0.031 (0.721)	0.705±0.053 (0.735)	0.567±0.044 (0.597)	0.582±0.035 (0.588)
	CAEM b	0.794±0.014 (0.817)	0.833±0.013 (0.851)	0.735±0.033 (0.746)	0.751±0.048 (0.772)	0.640±0.007 (0.658)	0.666±0.019 (0.688)
	SAEM b	0.795±0.011 (0.821)	0.830±0.010 (0.851)	0.746±0.023 (0.773)	0.756±0.039 (0.798)	0.644±0.015 (0.661)	0.656±0.021 (0.689)

Table 5 .

 5 5 Comparison of average NMI and ARI, on NG20, SPORTS and TDT2 datasets.

		NG20	SPORTS	TDT2
		NMI	ARI	NMI	ARI	NMI	ARI
	Skmeans	0.542±0.013 (0.555)	0.375±0.016 (0.379)	0.614±0.044 (0.627)	0.405±0.053 (0.442)	0.790±0.012 (0.801)	0.492±0.031 (0.514)
	CEM	0.467±0.013 (0.484)	0.149±0.021 (0.150)	0.446±0.048 (0.455)	0.151±0.067 (0.177)	0.750±0.021 (0.769)	0.436±0.048 (0.466)
	EM	0.465±0.013 (0.481)	0.143±0.020 (0.141)	0.444±0.049 (0.453)	0.149±0.067 (0.174)	0.751±0.019 (0.771)	0.438±0.041 (0.489)
	DAEM	0.556±0.018 (0.576)	0.369±0.022 (0.393)	0.618±0.005 (0.620)	0.398±0.016 (0.416)	0.795±0.007 (0.806)	0.462±0.011 (0.456)
	dbSkmeans	0.579±0.013 (0.591)	0.417±0.020 (0.440)	0.572±0.032 (0.615)	0.451±0.084 (0.601)	0.794±0.012 (0.808)	0.636±0.028 (0.682)
	CEM b	0.582±0.011 (0.594)	0.388±0.024 (0.403)	0.558±0.039 (0.608)	0.508±0.080 (0.602)	0.799 ±0.014 (0.817)	0.657±0.032 (0.719)
	EM b	0.585±0.010 (0.601)	0.390±0.025 (0.425)	0.564±0.037 (0.617)	0.517±0.072 (0.605)	0.799±0.015 (0.821)	0.658±0.034 (0.699)
	SEM b	0.534±0.013 (0.553)	0.347±0.022 (0.367)	0.670±0.018 (0.700)	0.713±0.033 (0.767)	0.718±0.020 (0.748)	0.619±0.022 (0.656)
	CAEM b	0.605±0.010 (0.608)	0.381±0.019 (0.385)	0.601±0.013 (0.612)	0.602±0.021 (0.613)	0.794±0.011 (0.806)	0.723±0.020 (0.749)
	SAEM b	0.610±0.011 (0.615)	0.393±0.012 (0.390)	0.613±0.015 (0.621)	0.620±0.016 (0.625)	0.791±0.010 (0.821)	0.709±0.021 (0.752)

Table 5 .

 5 6 Comparison of classification log-likelihood.

		CSTR	CLASSIC4	WEBACE	NG20	SPORTS	TDT2
	EM b	976

Table 5 .

 5 7 SPORTS dataset: confusion matrices crossing the row clusters obtained by both algorithms (rows) and the true row clusters (columns). The column z .h indicates the sizes of clusters.

			EM b (NMI = 0.617, ARI = 0.605)				Skmeans (NMI = 0.627 , ARI = 0.442)
	1	1 3338		2 219	3 41	4 27	5 487	6 48	7 82		z .h 4242	1 1705	2 1	3 0	4 1	5 1	6 0	7 0		z .h 1708
	2	8		1008	0	0	16	0	0		1032	0		904	0	0	1	0	1		906
	3	24		22	5	0	39	5	7		102	1		1	0	0	798	1	0		801
	4	36		138	0	0	449	2	2		627	1326	0	0	0	6	0	0		1332
	5	3		14	0	1	1345	1	10		1374	81		30	24	6	1171	5	4		1321
	6	3		8	99	94	10	280	0		494	298		473 121 115	369	330	23	1729
	7	0		1	0	0	0	0	708		709	1		1	0	0	0	0	781	783
	200 300 400 500 600							500 1000 2000							500 1000 1500 2000
		CEMb	EMb	CAEMb	SAEMb	CEM	EM		CEMb	EMb	CAEMb	SAEMb	CEM	EM		CEMb	EMb	CAEMb	SAEMb	CEM	EM
				(a) CSTR					(b) WEBACE					(c) CLASSIC4
	3000 5000 7000							10000 20000 30000							5000 15000
	1000	CEMb	EMb	CAEMb	SAEMb	CEM	EM	0	CEMb	EMb	CAEMb	SAEMb	CEM	EM		CEMb	EMb	CAEMb	SAEMb	CEM	EM
			(d) SPORTS						(e) TDT2						(f) NG20

Table 5 .

 5 8 Word clusters resulting from SAEM b on the CLASSIC4 dataset. Each cluster is represented by its top 15 terms, sorted according to their popularity. Clusters C1, C2, C3 and C4 correspond respectively to CACM, CISI, CRANFIELD and MEDLINE.

	C1	C2	C3	C4
	algorithm	librari	flow	cell
	program	inform boundari	patient
	system	scienc	layer	rat
	comput	research pressur	growth
	languag	book	heat	blood
	method	servic	wing	acid
	function	scientif	number	hormon
	gener	index	bodi	tissu
	problem	journal	solut	diseas
	data	retriev	shock	cancer
	time	studi	theori	treatment
	structur	develop	equat	tumor
	integr	literatur	mach	renal
	process	public	effect	kidnei
	matrix	univers	plate	dai

Table 5 .

 5 9 Clustering of CLASSIC4 into 7 co-clusters by SAEM b : the obtained word clusters represented by their top 15 terms, sorted according to their popularity.

	CACM	CISI	CRANFIELD		MEDLINE
	C1	C2	C3	C4	C5	C6	C7
	algorithm program	librari	flow	cell	children	patient
	function	system	inform	boundari	rat	child	cancer
	integr	comput	scienc	layer	growth	speech	ventricular
	matrix	languag research	pressur	acid	autist	diseas
	polynomi	data	book	heat	hormon	anxieti	arteri
	permut	problem	servic	wing	tissu	disord	therapi
	squar	structur	index	number	activ	joint	treatment
	invers	process	scientif	bodi	dna	visual	pulmonari
	fit	time	retriev	solut	protein syndrome	defect
	random	gener	journal	shock	kidnei	autism	breast
	complex techniqu	studi	equat	antigen	mother	aortic
	root	code	develop	theori	dai	earli	cardiac
	exponenti	algol	literatur	mach	human childhood	renal
	error	oper	docum	effect	len	symptom hydrocephalu
	gamma	set	public	plate	cultur	infantil	hypothermia

Table 5 .

 5 10 The top 6 word clusters resulting from SAEM b on dataset TDT2. Each cluster is represented by its top 15 terms, sorted according to their popularity.

	C10	C24	C28	C12	C25	C3
	iraq	percent	lewinsky	suharto	nuclear	tobacco
	un	asian	starr	indonesia	pakistan	smoking
	weapons	economic	clinton	jakarta	india	industry
	iraqi	financial	president	indonesian	test	bill
	inspectors economy	white	habibie	treaty	senate
	baghdad	market	house	imf	kashmir	legislation
	united	stock	monica	suhartos	sharif	companies
	saddam	crisis	grand	political	islamabad	settlement
	annan	yen	jury	student	conducted	congress
	council	dollar	counsel	reform	five	cigarette
	military	currency independent	protests	ban	republicans
	secretary	billion	investigation	rupiah	device	documents
	sites	banks	intern	riots	intelligence	tax
	security	stocks	sexual	step	explosions	lawsuits
	inspections	growth	lawyers	demonstration	powers	democrats

  Thanks to our co-clustering formulation, penalizing larger row clusters using an adequate choice of concentration parameters, i.e, κ h = 1/ f (z .h ), ∀h, with f (x) = √ x, naturally yields a penalization of larger column clusters with an appropriate multiplicative term, equal to 1/ √ w .h . Another choice of function f will give a different criterion. Our Frequency Sensitive co-clustering algorithm, called Frequency Sensitive Diagonal Block Spherical k-means (FSdbSkm) is described in more details by Algorithm 8. It can be shown that the computational complexity of FSdbSkm is given in O(it • nz), where it and nz denote respectively the number of iterations and non-zero entries. Thereby FSdbSkm is very efficient, therefore suitable for high dimensional sparse data. Input: X (x i ∈ S d-1 ), g the number of co-clusters.

	Algorithm 8: FSdbSkm.
	Output: Z and W,
	Steps:
	1 √ w .h	w jh cos(µ z h , x j )	(6.8)

Table 6 .

 6 1 Description of Datasets.

	Datasets	n	d	Characteristics g Sparsity (%) Balance RME	SDCS
	NG2	500	2000	2	96.85	1.00	1.00	0.00
	CLASSIC4 7094	5896	4	99.41	0.323	0.582 972.18
	NG20	19949 43586 20	99.82	0.991	0.993 2.28
	SPORTS	8580 14870 7	99.14	0.036	0.099 1253.01
	LA12	6279 31472 6	99.52	0.281	0.498 526.49
	NG17-19	2998 23233 3	99.51	0.998	0.999 1.15
	word cluster labels, however, are not known, this is the reason why we mainly concentrate
	our experiments on document clustering. Nevertheless, under our formulation row clusters
	induce column clusters and vice versa thereby the quality of row clustering is informative
	about the quality of column clustering.

Table 6 .

 6 2 Comparison of Average NMI, ARI on the NG20, SPORTS, LA12 datasets.

		NG20	SPORTS	LA12
		NMI	ARI	NMI	ARI	NMI	ARI
	soft-movMF	0.44±0.01 (0.46)	0.12±0.01 (0.13)	0.43±0.03 (0.43)	0.12±0.05 (0.10)	0.40±0.04 (0.46)	0.21 ±0.07 (0.29)
	da-movMF	0.57±0.01 (0.58)	0.40±0.02 (0.40)	0.62±0.02 (0.63)	0.40±0.03 (0.41)	0.53±0.01 (0.55)	0.49±0.01 (0.52)
	Skmeans	0.54±0.01 (0.55)	0.37±0.02 (0.38)	0.61±0.04 (0.63)	0.40±0.05 (0.44)	0.53±0.05 (0.56)	0.48±0.05 (0.50)
	FSdbSkm	0.61±0.01 (0.62)	0.50±0.01 (0.51)	0.62±0.03 (0.67)	0.52±0.05 (0.62)	0.56±0.02 (0.58)	0.53±0.02 (0.55)

Table 6 .

 6 3 Comparison of Average NMI, ARI on the NG17-19, CLASSIC4 and NG2 datasets.

		NG17-19	CLASSIC4	NG2
		NMI	ARI	NMI	ARI	NMI	ARI
	soft-movMF	0.27±0.02 (0.29)	0.14 ±0.01 (0.14)	0.48±0.01 (0.49)	0.29±0.02 (0.30)	0.14±0.06 (0.26)	0.06±0.06 (0.16)
	da-movMF	0.37±0.01 (0.37)	0.31±0.01 (0.30)	0.59±0.003 0.47±0.002 (0.59) (0.47)	0.55±0.06 (0.57)	0.64±0.08 (0.66)
	Skmeans	0.42±0.04 (0.41)	0.36±0.06 (0.35)	0.59±0.02 (0.59)	0.47±0.01 (0.48)	0.51 ±0.06 (0.57)	0.58 ±0.08 (0.67)
	FSdbSkm	0.53±0.04 (0.57)	0.56±0.04 (0.59)	0.70±0.01 (0.72)	0.67±0.01 (0.70)	0.71±0.02 (0.74)	0.81±0.01 (0.83)

Table 6 .

 6 [START_REF] Salah | A dynamic collaborative filtering system via a weighted clustering approach[END_REF] Comparison BALANCE, RME and SDCS on the NG20, SPORTS, LA12 datasets.

			NG20		SPORTS		LA12
		BALANCE RME SDCS BALANCE RME SDCS BALANCE RME SDCS
	soft-movMF	0.018	0.125 1534.42	0.074	0.293 1618.73	0.069	0.159 751.63
	da-movMF	0.120	0.256 465.26	0.252	0.517 644.86	0.603	0.782 232.82
	Skmeans	0.175	0.332 401.42	0.271	0.476 545.37	0.372	0.594 361.74
	FSdbSkm	0.482	0.627 147.79	0.446	0.715 383.80	0.534	0.679 223.07
	Table 6.5 Comparison BALANCE, RME and SDCS on NG17-19, CLASSIC4, NG2.
			NG17-19		CLASSIC4		NG2
		BALANCE RME SDCS BALANCE RME SDCS BALANCE RME SDCS
	soft-movMF	0.079	0.188 1204.23	0.251	0.547 1398.46	0.275	0.432 200.82
	da-movMF	0.272	0.508 752.79	0.457	0.635 591.90	0.825	0.904 33.94
	Skmeans	0.171	0.347 902.26	0.467	0.635 582.49	0.735	0.834 48.08
	FSdbSkm	0.710	0.838 172.40	0.407	0.581 615.34	0.976	0.988 4.24

Table 6 .

 6 6 CLASSIC4 dataset: the term clusters discovered by FSdbSkm represented by their top 15 terms sorted according to cosine similarity. The clusters C1, C2, C3 and C4 corresponds respectively to CACM, CRANFIELD, CISI and MEDLINE.

	C1	C2	C3	C4
	algorithm	flow	librari	patient
	program boundari inform	cell
	system	layer	scienc	case
	comput pressur	index	rat
	languag	equat	retriev	growth
	method	solut	research treatment
	function	heat	book	blood
	gener	wing	servic	acid
	matrix	number scientif hormon
	data	bodi	docum	diseas
	time	theori	search children
	problem	shock develop increas
	structur	mach	journal	tissu
	integr	effect	studi	normal
	set	plate	user	group

  j zih w jh x i j z.h .

	Replacing μhh by then:	∑ i, j zih w jh x i j ∥r w h ∥	(see, equation A.5), we obtain	c ′ d (κ h ) c d (κ h ) = -	∥r w h ∥ z.h ŵ.h . Let s = d/2 -1,
	c ′ d (κ h ) =	sκ s-1 h (2π) s+1 I s (κ h ) -κ s h (2π) s+1 I ′ s (κ h ) (2π) 2s+2 I 2 s (κ h )
	=	sκ s-1 h (2π) s+1 I s (κ h )	-	κ s h I ′ s (κ h ) (2π) s+1 I 2 s (κ h )
	= c d (κ h )	s κ h	-	I ′ s (κ h ) I s (κ h )	.	(A.6)
	Hence, we obtain		-c ′ d (κ h ) c d (κ h )	=	I s+1 (κ h ) I s (κ h )	=	I d/2 (κ h ) I d/2-1 (κ h )	.	(A.7)

  -(r h ) 2which corresponds to the approximation of the concentration parameters under dbmovMFs and movMFs without the correction term. Since both rw h and rh are in ]0, 1[, it is straightforward to verify that if rw h ≤ rh then the above inequality is always verified. Thus, in what follows we aim to demonsrate that rw

	is, Proof. We first prove that h as follows κw h ≈ rw h d -rw h 1 -rw rw h d 1 -rw h 1 Now, let's define r′ 3 2 ≤ r′ h = ∥r ′ h ∥ ∑ i zih where r ′ h j =	rh d     	r h j , if w jh = 1 0, otherwise.	). That

h 2 ≤ κh ≈ rh d -(r h ) 3 1 -(r h )

2 with equality only if rw h = rh . h ≤ rh . By definition, we have rh = ∥r h ∥ ∑ i zih where r h = ∑ i zih x i

In the rest of this thesis we treat "direction data" and "L

normalized data" as synonyms

http://grouplens.org/datasets/movielens/

http://www.epinions.com

http://www.librec.net/

http://www.cs.ubc.ca/ jamalim/datasets/

http://www.librec.net/datasets.html

http://www.jiliang.xyz/trust.html

Several variants of nDCG exist, here we adopt the same as in LibRec for fairness purpose.

Cold start users are those with only few observed rating/social-interactions. Following previous works[START_REF] Jamali | A matrix factorization technique with trust propagation for recommendation in social networks[END_REF][START_REF] Guo | Trustsvd: Collaborative filtering with both the explicit and implicit influence of user trust and of item ratings[END_REF] we assume that a user is cold start in the user-item matrix if he/she expressed five or fewer ratings. Similarly a user is cold start in the social network if he/she has five or fewer social interactions.

http://www.dataminingresearch.com/

http://www.cad.zju.edu.cn/home/dengcai/

The balance coefficient is the ratio of the minimum cluster size to the maximum cluster size.

We found that all algorithms, except stochastic variants, provide substantially better results when they are initialized using Skmeans (in almost all situations)

For presentation purpose we omit CEM in Figure5.6, but from tables 5.4 and 5.5 it is straightforward to verify that the behaviour of CEM is too close to that of EM

http://www.dataminingresearch.com/

talk.politics.misc, talk.politics.guns and talk.politics.mideast

Remerciements

Submitted articles

1. Aghiles Salah, Nicoleta Rogovschi, and Mohamed Nadif. Co-clustering via a mixture of von Mises-Fisher Distributions. under review in Journal of Machine Learning Research. 2016. 2. Aghiles Salah, and Mohamed Nadif. Directional Model-based Social Collaborative Filtering to Alleviate the Sparsity related Issues. Under review.

well-established statistical theory of model selection since our algorithms are based on the maximization of the likelihood. More precisely, we can use information criteria, such the Akaike information criterion (AIC) [START_REF] Akaike | A new look at the statistical model identification[END_REF][START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF], AIC3 [START_REF] Bozdogan | Mixture-model cluster analysis using model selection criteria and a new informational measure of complexity[END_REF], Bayesian information criterion (BIC) [START_REF] Schwarz | Estimating the dimension of a model[END_REF] or integrated classification likelihood (ICL) [START_REF] Biernacki | Assessing a mixture model for clustering with the integrated completed likelihood[END_REF]. The aforementioned information criteria (IC) measure the quality of a model given some observed data, and they are formally given by

where k denotes the number of parameters to be estimated, γ a penalty coefficient and L is the maximized value of the log-likelihood function. With γ = 1 we have the AIC criterion, γ = 3/2 we obtain AIC3 and γ = (log n)/2 leads to the BIC criterion where n is the simple size-the number of rows/documents in our case. And last, ICL can be obtained from (5.13) by replacing L with the complete data log-likelihood Lc and setting γ to (log n)/2.

Intuitively the above information criteria penalize the log-likelihood according to the complexity of the model in terms of the number of parameters to be estimated; the lower the information criterion, the better is the model quality. Hence, information criteria can be used to select the best model, which yields the lowest value in terms of the selected information criterion, among a set of models. In our case we are interested in selecting the number of clusters, we therefore study the behaviour of AIC, AIC3 and BIC when varying the number of clusters, on each dataset.

Note that this problem has been investigated by many authors for different mixture models including the vMF mixture model [START_REF] Bouberima | Assessing the number of clusters from a mixture of von mises-fisher[END_REF] where the authors have performed Monte Carlo simulations taking into account the overlap degree of clusters and the size of data. Although their experiments were performed on moderate size and non sparse data, the authors emphasized the good behavior of AIC and AIC3 compared to BIC and ICL.

For our experiments, we use the value of L resulting from the simulated annealing dbmovMFs (SAEM b ) algorithm as it seems to provide the best performances in almost all cases. Determining the number of free parameters in dbmovMFs is not straightforward due to the mixing of continuous and discrete parameters. The parameters α and κ contain g -1 and g parameters, respectively. The column partition w-that is treated as a parameter in our case-contains the same number of parameters whatever the number of column clusters. Nevertheless, as pointed by [START_REF] Van Dijk | Two-mode clustering methods: a structured overview[END_REF], the number of possible values for each parameter increases with the number of clusters, it is therefore more convenient to consider w under its matrix form W of size (d × g), where each row indicates to which cluster the corresponding column belongs. The effective number of free parameters in dbmovMFs is

List of Publications Published articles

Appendix A

Parameters Estimation

In this appendix, we provide the derivation details of maximum likelihood estimates for parameters of the diagonal block mixture of von Mises-Fisher distributions (dbmovMFs).

A.1 Maximum Likelihood Estimate

The expectation of the complete data log-likelihood of dbmovMFs is given by

where z.h = ∑ i zih . We first maximize the expectation of the complete log-likelihood (A.1) with respect to α h , subject to the constraint ∑ h α h = 1. The corresponding Lagrangian, up to terms which are not function of α h , is given by

Taking derivatives with respect to α h , we obtain ∂ L(α,λ )

Setting this derivative to zero leads to z.h = λ α h . Summing both sides over all h yields λ = n, thereby the maximizing value of the parameter α h is given by:

The right hand side equality holds only if d and r + are collinear, thereby all components of r are equal (i.e,r 1 = • • • = r d ). Hereafter we provide the proof of Proposition 1.

Proposition 1 Let r be a non-zero vector in R d (i.e., r = (r 1 , . . . , r d ) T , such as d ≥ 1) which results from a weighted sum of n d-dimensional unit vector, i.e, r = ∑ i p i x i , x i ∈ R d and ∥x i ∥ = 1 , ∀i ∈ {1, . . . , n} , n ≥ 2, the weights p i ≥ 0, ∀i. Let r d be a vector in R d , such as all its components are equal to the sum of elements of r (i.e, r d = ∑ d j=1 r j ✶). Then ∥r d ∥ ≤ d × ∑ i p i with equality only if all unit vectors x i are equal/collinear.

Proof. Based on Proposition 3 and the following inequality: ∥r∥

In the following, we prove Theorem 1, which states that for a given row clustering z, dbmovMFs-based algorithms lead to a concentration parameter that is less or equal to that of movMFs-based algorithms, for each cluster, and whatever the column partition w. The following Lemma will be useful in the proof of Theorem 1.