Najeh Hajlaoui
email: najeh.hajlaoui@imag.fr

corpus de messages pour la multilinguïsation de sites de ecommerce en SMS, initialement en arabe

Keywords: SMS (Short Messages Services), corpus naturel et réel, multilinguïsation, traduction brute, traduction fonctionnelle, CRLcats(Content Representation Language-Classified Ads through SMS) SMS (Short Messages Services), natural and real corpus, multilinguisation, brut translation, functional translation, CRLcats

. CATS is a system of management of small Arabic advertisements posted in SMS of buying and selling ( cars, real estate...), currently deployed in Jordan by the FastLink operator. In order to adapt this system to other languages (French, English) and in length by applying it to other sectors (employment, marriage, domestic machines, trade of mobile phone, pages yellow...), we are in the difficulty in finding or building SMS corpora functionally equivalent to a real, Arab and natural corpus. A simple translation of this starting corpus gives it the same type of corpus (real, natural)? We present, in this paper, an answer to this question and a solution for a case of multilinguisation of sites of e-commerce in SMS, initially in Arabic. Résumé Dans ce papier, nous présentons notre recherche qui se déroule dans le cadre du projet CATS (Classified Ads through SMS) [3]. CATS est un système de gestion de petites annonces en arabe postées en SMS pour l'achat et la vente (occasion automobile, immobilier…), actuellement déployé en Jordanie par l'opérateur FastLink. Pour faire évoluer ce système en largeur en l'adaptant à d'autres langues (français, anglais) et en longueur en l'appliquant à d'autres secteurs (emploi, mariage, fourniture, appareils ménagers, commerce de téléphone portable, pages jaunes…), nous sommes confrontés à la difficulté de trouver ou de construire des corpus de SMS fonctionnellement équivalents à un corpus arabe, réel et naturel. Une simple traduction de ce corpus de départ donne-elle un corpus de même critère (réel, naturel) ? Nous présentons, dans ce papier, une réponse à cette question ainsi qu'une solution pour un cas de multilinguïsation de sites de ecommerce en SMS, initialement en arabe.

 [START_REF] Nespole | NEgotiating through SPOken Language in E-commerce[END_REF].

Transformation d'un analyseur en un CE : utilisation de nouvelles voies, il s'agit d'écrire un CE en Ariane G5 (par spécialisation/adaptation d'un analyseur classique du français).

Construction d'un système de TA : construire un système de TA des SMS en français vers les SMS en arabe. Pour cela, il faudrait construire un grand corpus parallèle, par traduction manuelle d'arabe en français, ou par génération à partir des représentations"pivot" CRLcats, puis par construction automatique d'un système de TA français-arabe spécialisé aux SMS, soit par une méthode statistique (de nombreux "kits" existent), soit par une méthode analogique [7]. Le point intéressant ici est de déterminer le domaine de validité de la méthode (caractéristiques du souslangage, taille minimale du corpus nécessaire pour obtenir le niveau de qualité souhaité).

Nous présentons ici un besoin commun pour toutes ces méthodes : un corpus réel français.

Approche 2 : approche classique

Il s'agit d'utiliser des systèmes de traduction pour obtenir des « prétraductions » en L (en anglais par exemple AREN) et passer à « des traductions de référence » en les révisant et les traduisant dans L pour obtenir une bonne qualité. Une fois que les traductions de référence sont obtenues, nous les utiliserons comme « accroche » pour trouver les correspondances naturelles produites directement par des utilisateurs spontanés parlant la langue L comme langue maternelle.

Conclusion

Dans les deux cas, les deux approches sont utiles et donnent comme résultat un corpus de SMS naturels en L fonctionnellement équivalent au corpus arabe de départ. L'approche 1 suppose qu'on dispose des représentations CRLcats ainsi qu'une transformation de CRLcats vers UNL. Dans notre cas et pour des raisons de manque de ressources logicielles, nous utiliserons dans ce que suit l'approche 2.

4

Recherche et production de corpus équivalents Dans cette partie, nous cherchons à trouver et construire des corpus en L fonctionnellement équivalents à des corpus en arabe sous une certaine contrainte de production (dans notre cas c'est un SMS).

Traduction du corpus arabe

Nous avons traduit la totalité du corpus SMS_ar_extr_content en anglais avec Systran professionnel version 5. Puisqu'il n'existe pas de système de TA français arabe, nous avons décidé, dans première étape, de traduire manuellement une partie de ce corpus afin d'évaluer l'hypothèse H. s(i,j)=1/1+α × (edit(i,j)/min(length(i),length(j)))

Remarque : α est un nombre positif qui sert de paramètre. La valeur usuelle employée est 1.

Figure 7:mesures de similarité

Pour un seuil de similarité fixé à 0,90, nous avons obtenu une similarité moyenne de 0,75 et 20% de traductions correctes.

Conclusion

La valeur de similarité est très faible, cela signifie que notre hypothèse H posée au départ est vraie : H les traductions directes d'un corpus réel constitué de phrases naturelles ne donnent pas de résultats naturels en français.

Production du corpus équivalent

Nous avons utilisé l'approche classique pour produire un petit corpus français fonctionnellement équivalent au corpus arabe initial. Afin de développer ce corpus, nous avons adopté la technique suivante : à partir du modèle d'annonces composé de 50 types de SMS révisées et jugées fonctionnelles, nous avons multiplié le nombre de ces annonces en formant des combinaisons différentes des arguments utilisés (type, modèle, année, couleur, prix…). Il s'agit de remplacer par exemple une année par une autre « je cherche une voiture modèle 98 » par « je cherche une voiture modèle 99 »…) Une marque par une autre « A vendre BMW rouge » par « A vendre PEUGEOT noire »… Il reste à améliorer encore le corpus obtenu pour pouvoir tester et démarrer le système CATS porté vers le français en supprimant des tas de mots inutiles (articles, prépositions longues, etc), en introduisant des abréviations usuelles dans les petites annonces et en ajoutant des abréviations de type phonétique ("ke" pour "que", "g" pour "j'ai", etc.) Cette méthode nous a permis d'obtenir un corpus fonctionnellement équivalent en français constitué de quelques centaines d'annonces, il est possible de le faire évoluer à des milliers d'annonces.

Conclusion et perspectives

Un nouvel axe de recherche a été décrit dans cet article sur la définition, la recherche, la production d'un type très particulier de corpus : c'est les corpus naturels, réels, spontanés rédigés par des êtres humains dans leurs langages maternels. Leur point fort est la réalité du contenu vu qu'ils sont construits d'une façon très naturelle, ce qui garantit l'évidence de l'hypothèse H (testée pour le français) que nous avons prouvé dans ce travail: les traductions directes d'un corpus réel constitué de phrases naturelles ne donnent pas de résultats naturels en français.

Nous avons proposé quelques méthodes de production de corpus réels. Nous avons obtenu un corpus réel en français avec lequel nous avons démarré et testé le système CATS. Une perspective importante de ce travail serait de produire de tel corpus en utilisant le passage pivot CRLcats comme c'est décrit dans la section Réflexions sur les méthodes possibles de multilinguisation du système CATS. Ce pivot nous permettra d'obtenir des corpus réels multilingues, par la suite nous avons l'idée de construire un système de traduction pour les SMS basé sur l'ensemble des corpus réels multilingues obtenus.

1 Problématique 1 . 1

 111 Contexte : description du système CATS Notre recherche se déroule autour du projet CATS (Classified Ads through SMS) [3]. C'est un système d'achat et de vente basé sur l'utilisation des SMS. Bien qu'il n'y ait pas de transaction directe, il aide les utilisateurs à vendre et acheter sans avoir à se déplacer. N'importe quelle personne se trouvant en Jordanie qui veut vendre une voiture peut envoyer un SMS en arabe au système indiquant sa proposition de vente avec la précision de quelques attributs comme le modèle, l'année, etc. Une autre personne intéressée par l'achat d'une voiture, peut simplement envoyer un message au système, expliquant sa requête. Dans ce cas de correspondance et grâce au système CATS, les deux personnes sont mets en contact. Par exemple un utilisateur a envoyé à partir de son téléphone mobile le SMS suivant décrivant sa requête d'achat. Une traduction brute de ce message donne : 6/1/2005 11:32:20 AM Message reçu : 962795028727 : recherche d'une voiture Honda, modèle 97, et le prix entre 3500 et 3750 Si c'était un Français, il écrirait plutôt (traduction fonctionnelle) : 6/1/2005 11:32:20 AM Message reçu : 962795028727 : recherche voiture Honda, modèle 97, prix entre 3500 et 3750 Dinars Un autre utilisateur a envoyé la proposition de vente suivante. Une traduction brute de cette proposition en français donne : 9/4/2005 12:48:12 PM Message In : +962795463274, En raison de départ à vendre vetement de soirée en très bon état avec un prix excellent Si c'était un Français, il écrirait plutôt (traduction fonctionnelle) : 9/4/2005 12:48:12 PM Message In : +962795463274, Cse départ vend vêtement de soirée en très bon état, TB prix Ces SMS sont envoyés à un numéro spécial et sont enregistrés automatiquement dans un corpus de données précédés de la date, de l'heure et du numéro de téléphone. Leurs textes sont analysés et une réponse est envoyée automatiquement à l'expéditeur du SMS en cas de correspondance de la demande avec l'une des propositions. Ce corpus est enrichi automatiquement par les annonces envoyées. Il est formé de phrases en arabe mélangées de dialecte jordanien, d'arabe littéraire et d'autres mots anglais importés. C'est un corpus naturel, évolutif et assez intéressant. Son point fort est la réalité du contenu, mais le rendre multilingue est une tâche assez délicate et utile en même temps pour démarrer l'adaptation du système CATS à d'autres langues. 1.2 Architecture La figure suivante montre l'architecture du système CATS : un vendeur ou un acheteur envoie un SMS, le texte de ce SMS est analysé avec un extracteur d'information et est représenté dans un format intermédiaire CRLcats (Content Representation Language). Cette représentation est traduite en requête SQL et envoyée vers une base de données. En cas de correspondance de requêtes, une réponse sera transmise à la personne intéressée.

Figure 1 :

 1 Figure 1 : architecture du système CATS 1.3 Motivation Nous voulons porter CATS vers d'autres langues, en commençant par le français pour les deux simples raisons suivantes : la première c'est que Daoud veut porter son système au français mais il ne le parle pas et la deuxième c'est qu'on a un extracteur d'information pour le français.

Figure 4 :

 4 Figure 4:exemple de traduction brute, littérale et fonctionnelle du corpus SMS_ar_extr_content 4.2 Evaluation de l'hypothèse H Afin d'évaluer l'hypothèse H, nous utilisons les notions classiques de rappel et de précision pour un nombre limité de phrases. Rappel = Nombre de traductions correctes / Nombre de traductions de référence Précision = Nombre de traductions correctes / Nombre de traductions proposées Afin de trouver les valeurs des mesures de rappel et précision, nous utilisons une méthode connue basée sur le calcul de distance d'édition entre deux chaînes de caractères (algorithme de Wagner & Fischer, 1974) [6]. La distance d'édition entre deux chaînes (caractères ou mots) est le nombre minimal de suppressions, insertions ou de remplacements nécessaires pour transformer une chaîne à un autre. La distance d'édition entre deux chaînes x = a 1 …a m et y = b 1 …b n est D(m, n), définie par :

Figure 5 :

 5 Figure 5 : exemple de calcul de distance 4.2.1 Résultats : Avec un coût de suppression, d'insertion ou de changement fixé à 1, on obtient 2 traductions correctes sur 50 (une distance d'édition égale à 0), ce qui donne les valeurs suivantes : Distance minimale = 0. Distance moyenne = 21,88. Distance maximale = 88. Rappel =0,04 La valeur du rappel trouvée signifie qu'il y a très peu de traductions brutes qui correspondent à des traductions fonctionnelles de référence c'est à dire que la sortie d'un système de traduction pour tels SMS (dans notre cas un non Français qui a traduit les SMS) est très différente de ce que peut dire un Français.

Figure 6 :

 6 Figure 6: mesures de distance d'édition Nous mesurons la similarité des traductions brutes et naturelles (fonctionnelles) définie comme suit :

1.4 Problèmes et difficultés

					Internet sont rares et leurs contenus sont différents de
					ce que nous cherchons. Les principales différences
					sont culturelles, ou proviennent de l'utilisation d'un
					langage codé, ou du mode de saisie.
					1.4.1	Différences culturelles
					Les différences culturelles se concrétisent dans
					l'utilisation d'un dialecte pour chaque langue. Dans
					le cas de notre corpus arabe, quelques mots sont
					écrits en arabe comme ils sont prononcés en anglais,
					c'est une transcription en écriture arabe de la
					prononciation anglaise du mot. D'autre part, l'anglais
					est la deuxième langue en Jordanie, contrairement à
					d'autres pays arabes et francophones. Mais un
					phénomène similaire est observé dans d'autres pays,
					par exemple, en Tunisie, pays francophone, où on
					arabise des mots français et où on les emploie dans
					les discussions quotidiennes au lieu d'utiliser les
					équivalents arabes.
					Exemple : dans les SMS présentés dans le
					paragraphe 2.1, le mot «	» qui veut dire
					« modèle » est une prononciation du mot anglais
					« model » mais en signifie pas "modèle" en arabe.
	Nous	disposons	du	corpus	original
	SMS_ar_orig.txt, constitué de 12372 d'annonces en
	arabe, et de taille 448 Ko. Nous sommes confrontés
	à la difficulté de trouver des corpus
	fonctionnellement équivalents en français et en
	anglais : les corpus d'annonces et de tchat sur

1.4.2 Utilisation d'un langage codé Il

							en
	expressions familières ou abrégées du genre MDR
	(mort de rire), BI1 (bien) ou A2M1 (à demain).
	Parmi les personnes interrogées, 41 % disent utiliser
	toujours ou très souvent de tels termes codés
	lorsqu'elles envoient des messages SMS à leurs amis
	ou aux membres de leur famille. Cette proportion fait
	un bond spectaculaire chez les jeunes de 18 à 24 ans :
	elle	passe	à	plus	de	73	%
	(

existe des logiciels de rédaction des SMS "complets" pour le français et d'autres langues. Un communiqué de presse montre que les Français veulent pourtant défendre le bon langage, mais un vrai phénomène de société s'empare de la France : les SMS forment un langage codé riche http://www.languefrancaise.net/news/index.php).

1.4.3 Absence de T9 pour certaines langues ou principe de saisie très différent T9

Text Input, célèbre logiciel de saisie de texte utilisant l'alphabet ou les caractères est fréquemment utilisé pour certaines langues. Théoriquement l'utilisation du T9 pour certaines langues, réduit l'utilisation des abréviations dans la rédaction des SMS, mais tout dépend de la culture, des habitudes et du savoir des utilisateurs :certains ne savent utiliser le T9, d'autres n'aiment pas l'utilisation d'un dictionnaire…

1.4.4 Conclusion et hypothèse

Dans ce travail, notre problématique est de trouver des méthodes qui permettent de produire des corpus réels, spontanés, naturels et fonctionnels en tenant compte des différences cités ci-dessus Pour cela, nous posons l'hypothèse H suivante :

H :

les traductions directes d'un corpus réel constitué de phrases naturelles ne donnent pas de résultats naturels en français, anglais etc.

  Nous montrons dans ce qui suit la validité de l'hypothèse H et nous proposons une solution au problème suivant :

comment construire des corpus parallèles de SMS fonctionnellement équivalents dans des situations de e-commerce ? 2 Etude : traitement et mise en forme du corpus existant 2.1 Etude précise du corpus source

	2.2	Structure du corpus original
	Comme le montre la figure 2, le corpus original
	(SMS_ar_orig.txt) contient accidentellement des
	lignes vides, des morceaux d'annonces incomplètes
	(présence de la date et/ou de l'heure de l'annonce,
	mais absence du coeur de l'annonce, ou annonces
	faites en anglais). Certes, ce de corpus est
	moins propre qu'un corpus normal. Les raisons
	sont nombreuses : erreurs humaines naturelles
	(envoi d'un message incomplet en appuyant sur la
	touche « OK » involontairement, SMS rédigés par
	des personnes résidant en Jordanie mais parlant
	l'anglais et pas l'arabe, et n'hésitant pas à envoyer
	des annonces en anglais pour leurs besoins
	commerciaux). D'autres erreurs techniques peuvent
	arriver, comme la faiblesse du réseau pour tel ou tel
	opérateur téléphonique. Malheureusement, la
	dernière version du système CATS accepte encore
	de tels SMS "sales". Les messages en anglais
	doivent être traduits manuellement en arabe avant
	d'être passés au système.

Le corpus CATS contient environ 23 % d'arabe jordanien, 5% de mots anglais importés, 70% d'arabe littéraire et 2% d'autres mots inconnus. Cela rend le traitement de ce type de corpus difficile, ajoutant d'autres difficultés liées à la structure du corpus.

Il est clair que ce type de corpus nécessite une étape de prétraitement (nettoyage et filtrage) pour pouvoir en extraire le contenu. Figure 2: exemple du corpus SMS_ar_orig 2.

3 Étape de prétraitement et extraction du contenu

Les annonces du corpus SMS_ar_orig sont constituées des champs suivants : Tableau 1: champs du corpus original SMS_ar_orig

Les coeurs de ces annonces sont précédés par une virgule, ce qui facilite le nettoyage. Par des programmes Perl, nous anons filtré ce corpus en supprimant tous les messages vides, les lignes vides et d'autres saletés parfois incompréhensibles. Cela réduit le nombre d'annonces de 12372 à 3017. Nous obtenons ainsi un nouveau corpus que nous appelons SMS_ar_extr_content.

2.4 Étape de normalisation

Notre corpus de départ est un fichier texte en codage arabe (Windows). Afin de faciliter sa manipulation et son traitement sur d'autres platesformes (UNIX, LINUX, MAC OS X), et en utilisant de simples outils tels que TexEdit ou Excel, et des programmes de conversion, nous avons transféré ce corpus dans une première étape vers un format texte avec un codage utf-8, puis dans des formats XML (codage utf-8). Le premier format, CXM (Common eXample Markup), sert à représenter des corpus monolingues et est très simple, et le deuxième format, CPXM (Common Parallel eXample Markup), est destiné à coder des fichiers multilingues.

2.5 Mise dans une base de données Afin

  de faciliter la manipulation des données et pour une meilleure gestion de l'historique des versions ainsi que les différences entre les différentes versions de ce même corpus et avec d'autres types de corpus (tchat, annonces sur le Web), nous avons mis ces données dans une base de données conçue de façon à gérer la notion de versionnage.

		Ads_type{saloon, wanted}
		Country{saloon, French}
		Figure 3 : exemple de représentation CRLcats
		Plusieurs méthodes sont possibles pour la
		multilinguisation. Nous donnons dans ce qui suit
		une brève description de chacune des méthodes.
		Dans d'autres articles en cours de rédaction, nous
		donnons une description complètes ainsi qu'une
		comparaison de ces méthodes.
		Localisation interne : localisation d'un CE-
		CATS (Content Extractor CATS) existant pour une
		autre langue. Concrètement, il s'agit d'adapter
		l'implémentation existante du CE pour l'arabe
		(arabe-contentcats, notée ar-cc) au français
		(français-contentcats, notée fr-cc).
		Adaptation externe : adaptation et greffe du
		CE externe (CE-ext) d'un autre système pour la
		même langue. Concrètement, il s'agit d'adapter à
		CATS un CE du français existant, celui du du
		projet Nespole fr-IF
	3	Réflexions sur les méthodes possibles de
		multilinguisation du système CATS
	3.1	Méthodes possibles

Il s'avère que CATS utilise des représentations du contenu en "CRLcats", syntaxiquement semblables à UNL, mais qui ne correspondent pas du tout à la représentation UNL standard, liée à une expression linguistique en anglais (même si elle en est une représentation profonde). CRLcats est une représentation de type Propriété{objet, valeur}.

Exemple : "Je cherche une voiture française"


Aichetou Bouchareb

Marc Boullé

Fabrice Clérot

Fabrice Rossi

Model based co-clustering of mixed numerical and binary data

Co-clustering is a data mining technique used to extract the underlying block structure between the rows and columns of a data matrix. Many approaches have been studied and have shown their capacity to extract such structures in continuous, binary or contingency tables. However, very little work has been done to perform co-clustering on mixed type data. In this article, we extend the latent block models based co-clustering to the case of mixed data (continuous and binary variables). We then evaluate the effectiveness of the proposed approach on simulated data and we discuss its advantages and potential limits.

Introduction

The goal of co-clustering is to jointly perform a clustering of rows and a clustering of columns of a data table. Proposed by [Good, 1965] then by [Hartigan, 1975], co-clustering is an extension of the standard clustering that extracts the underlying structure in the data in the form of clusters of row and clusters of columns. The advantage of this technique, over the standard clustering, lies in the joint (simultaneous) analysis of the rows and columns which enables extracting the maximum of information about the interdependence between the two entities. The utility of co-clustering lies in its capacity to create easily interpretable clusters and its capability to reduce a large data table into a significantly smaller matrix having the same structure as the orig-inal data. Performing an analysis on the smaller summary matrix enables the data analyst to indirectly study the original data while significantly reducing the cost in space and computing time.

Since its introduction, many co-clustering methods have been proposed (for example, [Bock, 1979, Cheng and Church, 2000, Dhillon et al., 2003]). These methods differ mainly in the type of data (continuous, binary or contingency data), in the considered hypotheses, the method of extraction and the expected results (hard clustering, fuzzy clustering, hierarchical clustering, etc.). One of the renowned approaches is the co-clustering using latent block models which is a mixture model based technique where each cluster of rows or columns is defined by latent variables to estimate ( [START_REF] Govaert | Co-Clustering[END_REF]). These models extend the use of Gaussian mixture models and Bernoulli mixture models to the context of co-clustering.

Latent block based co-clustering models have therefore been proposed and validated for numerical, binary, categorical, and contingency data. Nevertheless, to our knowledge, these models have never been applied to mixed data. Actually, real life data is not always either numerical or categorical and an outright information extraction method is required to handle mixed type data as well as uni-typed data. Since the majority of data analysis methods are designed for a particular type of input data, the analyst finds himself/herself forced to go through a phase of data pre-processing to transform the data into a uni-type data (often binary) in order to use an appropriate method.

Another option is to separately analyze each part of the data (by type) using an appropriate method, then perform a joint interpretation of the results. However, data pre-processing is very likely to result in a loss of information while independently analyzing different parts of the data, using methods that are based on different models, makes the joint interpretation of the results even harder and sometimes the results are simply incoherent.

Mixture models have been used to analyze mixed data in the context of clustering, by [START_REF] Mcparland | Model based clustering for mixed data: clustmd[END_REF] who propose using a latent variable model according to the Gaussian distribution regardless of the data type (numerical, binary, ordinal, or nominal data). However, the use of these models in co-clustering remains uncommon. In this paper, we propose to extend the co-clustering mixture models, proposed by [Govaert andNadif, 2003, Govaert andNadif, 2008], to the case of mixed data (with numerical and binary variables) by adopting the same approach of maximum likelihood estimation as the authors.

The remainder of this paper is organized as follows. In Section 2, we start by defining the latent block models and their use in co-clustering. In Section 3, we extend these models to mixed data co-clustering. Section 4 presents our experimental results on simulated data. Section 5 provides a discussion of the results. Finally, conclusions and future work are presented in Section 6.

Latent block model based co-clustering

Consider the data table x = (x ij , i ∈ I, j ∈ J) where I is the set of n objects and J the set of d variables characterizing the objects, defined by the rows and columns of the matrix x, respectively. The goal of co-clustering is to find a partition Z of the rows into g groups and a partition W of the columns into m groups, describing the permutation of rows and columns that defines groups of rows and groups of columns and forms homogeneous blocks at the intersections of the groups. Supposing the number of row clusters and the number of column clusters to be known, an entry x ij belongs to the block B kl = (I k , J l ) if and only if the row x i. belongs to the group I k of rows, and the column x .j belongs to the group J l of columns. The partitions of the rows and columns can be represented by the binary matrix z of row affiliations to the row clusters and the binary matrix of column affiliations w, where z ik = 1 if and only if x i. ∈ I k and w jl = 1 if and only if x .j ∈ J l .

The likelihood of the latent block model LMB is given by:

f (x; θ) = (z,w)∈(Z×W) p((z, w); θ)p(x|z, w; θ), (1)
where θ is the set of unknown model parameters, and (Z × W) is the set of all possible partitions z of I and w of J that fulfill the following LBM hypotheses:

1. the existence of a partition of rows into g clusters {I 1 , . . . , I g } and a partition of columns into m clusters {J 1 , . . . , J m } such that each entry x ij , of the data matrix, is the result of a probability distribution that depends only on its row cluster and its column cluster. These partitions can be represented by latent variables that can be estimated, 2. the memberships of the row clusters and of the column clusters are independent, 3. knowing the cluster memberships, the observed data units are independent (conditional independence to the couple (z, w)).

Under these hypotheses, the log-likelihood of the data is given by:

L(θ) = log f (x; θ) = log   (z,w)∈Z×W ik π z ik k jl ρ w jl l ijkl ϕ kl (x ij ; α kl ) z ik w jl   ,
where the sums and products over i, j, k, and l have their limits from 1 to n, d, g, and m, respectively, π k and ρ l are the proportions of the k th cluster of rows and the l th cluster of columns, and α kl is the set of parameters specific to the block B kl . The likelihood ϕ kl is that of a Gaussian distribution in the case of numerical data and that of a Bernoulli distribution in the case of binary data.

For an (n × d) data matrix and a partition into g × m co-clusters, the sum over Z×W would take at least g n ×m d operations ( [START_REF] Brault | Revue des méthodes pour la classification jointe des lignes et des colonnes d'un tableau[END_REF]).

Directly computing the log-likelihood is infeasible in a reasonable time, preventing therefore a direct application of EM algorithm, classically used in mixture models. Thus, [START_REF] Govaert | Block clustering with Bernoulli mixture models : Comparison of different approaches[END_REF]] use a variational approximation and a Variational Expectation Maximization algorithm for optimization.

LBM based co-clustering of mixed data

The latent block model as defined in Section 2 can only be applied to unitype data. To extend their use to the case of mixed data, we now consider a mixed type data table Additionally to the previously mentioned LBM hypotheses, we suppose that the partition of rows, the partition of continuous columns and the partition of the binary columns are independent. These partitions are represented by the binary clustering matrices z, w c , w d and by the fuzzy clustering matrices s, tc and td, respectively. Furthermore, conditionally on w c , w d and z, the data matrix entries (x ij ) {i∈I,j∈J} are supposed independent and there is a mean, independent from the model, to distinguish the continuous columns from the binary ones. Under these hypotheses, the likelihood of the generative model for mixed data can be written as:

x = (x ij , i ∈ I, j ∈ J = J c ∪ J d )
f (x; θ) = (z,wc,w d )∈(Z×(Wc,W d ))   ik π z ik k jclc ρ wc jc lc lc j d l d ρ wd j d l d l d ijcklc ϕ c klc (x ijc ; α klc ) z ik wc jc lc ij d kl d ϕ d kl d (x ij d ; α kl d ) z ik wd j d l d   .
Note that the aforementioned hypotheses lead to a simple combination of the previously existing situations (binary and continuous). Therefore, this combination adds no further mathematical difficulty, but rather potential practical consequences, resulting from coupling two different distributions (in the clustering of rows) and by the incommensurable natures of the densities (continuous variables) and probabilities (binary variables).

For likelihood optimization, we use an iterative Variational Expectation Maximization algorithm, inspired by [START_REF] Govaert | Block clustering with Bernoulli mixture models : Comparison of different approaches[END_REF], as described below.

Variational approximation

In the latent block model, the goal is to optimize the full-information, which requires knowing the latent variables z, w c and w d . The full-information log-likelihood is given by:

Lc(x, z, wc, w d ; θ) = ik z ik log π k + jclc wc jclc log ρ lc + j d l d wd j d l d log ρ l d + ijcklc z ik wc jclc log ϕ c klc (x ijc ; α klc ) + ij d kl d z ik wd j d l d log ϕ d kl d (x ij d ; α kl d ),
where the sums over i, j c , j d , k, l c , l d have their limits from 1 to n, d c , d d , g, m c and m d respectively. However, a direct application of the EM algorithm is impractical due to the dependency between the memberships to the clusters of rows z and the memberships to the clusters of continuous columns w c on one hand, and between the memberships to the clusters of rows z and the memberships to the clusters of binary columns w d , on the other hand. This makes the computation of the joint distribution p(z, w c , w d |x, θ) rather an impossible task. It is thus impractical to integrate the log-likelihood of the full-information data, given this distribution.

As in [START_REF] Govaert | Block clustering with Bernoulli mixture models : Comparison of different approaches[END_REF], we use a variational approximation that consists of approximating the conditional distributions of the latent variables to a factorisable form. More precisely, we approximate p(z, w c , w d |x, θ) by the adjustable distribution product q(z|x, θ), q(w c |x, θ) and q(w d |x, θ), of parameters s ik = q(z ik = 1|x, θ), tc jl = q(wc jl = 1|x, θ) and td jl = q(wd jl = 1|x, θ) respectively.

The full-information likelihood is thus lower bounded by the following F c criterion Fc(s, tc, td, θ)

= ik s ik log π k + jclc tc jclc log ρ lc + j d l d td j d l d log ρ l d + ijcklc s ik tc jclc log ϕ c klc (x ijc ; α klc ) + ij d kl d s ik td j d l d log ϕ d kl d (x ij d ; α kl d ) - ik s ik log s ik - jclc tc jclc log tc jclc - j d l d td j d l d log td j d l d ,
which provides an approximation for the likelihood. The maximization of F c is simpler to conduct and yields a maximization of the expected fullinformation log-likelihood. Therefore, the goal will onward be to maximize the criterion F c .

The Variational Expectation Maximization algorithm

Maximizing the lower bound F c in the mixed-data latent block model (MLBM) is performed, until convergence, in three steps:

• with regard to s, with fixed θ, tc and td, which amounts to computing

ŝik ∝ π k exp ( jclc tc jclc log ϕ c klc (x ijc , α klc )) exp ( j d l d td j d l d log ϕ d kl d (x ij d , α kl d )), (2)
• with regard to tc and td with fixed s and θ, which amounts to computing

tc jclc ∝ ρ lc exp ( ik s ik log ϕ c klc (x ijc , α klc ))
and td

j d l d ∝ ρ l d exp ( ik s ik log ϕ d kl d (x ij d , α kl d )), (3) with:
k

s ik = lc tc jlc = l d td jl d = 1,
• with regard to θ, which amounts to computing the cluster proportions and parameters

πk = i ŝik n ; ρlc = jc tc jlc dc ; ρl d = j d td jl d d d ; μklc = ijc ŝik tc jclc x ijc i ŝik jc tc jclc ; σ2 klc = ijc ŝik tc jclc (x ijc -μklc ) 2 i ŝik jc tc jclc et αkl d = ij d ŝik td j d l d x ij d i ŝik j d td j d l d . (4)
In our implementation (Algorithm 1), we used = 10 -5 as convergence constant for the inner loops, = 10 -10 for the outer loop, and we normalized ŝ, tc and td, after calculation, by taking the relative values: ŝik ← ŝik h ŝih and similarly for tc and td.

Experiments

In this section, we evaluate the proposed approach on simulated data with controlled setups. This evaluation step is necessary to measure how well the approach can uncover the true distributions from data with known parameters. To do this, we start by presenting the setups used to produce artificial data followed by an analysis of the experimental results of the proposed LBM extension. The first experiment is set to validate our implementation on uni-type data and confirm the contribution of the approach. The second experiment is set to investigate the influence of various parameters such as the number of co-clusters, the size of the data matrix and the level of overlap in the data.

Algorithm 1: The Mixed-data Latent Block Model VEM algorithm Require: Data x, the number of clusters g, mc, m d , maximum number of iterations maxIT ER and InnerM axIter iteration c←0 Initialization: choose s = c c , td = tc c , td = td c randomly and compute θ = θ c (equation ( 4)) while c ≤ maxIT ER and Unstable(Criterion) do t←0, s t ← s c , tc ← tc c , td ← td c , θ t ← θ c while t ≤ InnerM axIter and Unstable(Criterion) do For every i = 1 : n and k = 1 : g, compute s t+1 ik : equation (2) For every k = 1 : g, lc = 1 : mc and : equation ( 4)

l d = 1 : m d , compute π t+1 k , µ t+1 klc , σ t+1 klc et α t+1 kl d : equation (4) Criterion ← Fc(s t+1 , tc, td, θ t+1 ) t ← t + 1 end while s ← s c+1 ← s t-1 , θ ← θ c+1 ← θ t-1 t ← 0 while t ≤ InnerM
Criterion ← Fc(s, tc t+1 , td t+1 , θ t+1 ) t ← t + 1 end while tc ← tc c+1 ← tc t-1 , td ← td c+1 ← td t-1 , θ ← θ c+1 ← θ t-1 Criterion ← Fc(s, tc, td, θ) c ← c + 1 end while Ensure: (s, tc, td, θ)

First experiment

The purpose of this experiment is two-fold: validate our implementation and evaluate the interest of considering continuous and binary data jointly.

The data set

Our first data sets consist of simulated data matrices containing g = 4 clusters of rows, m c = 2 clusters of continuous columns and m d = 2 clusters of binary columns.

The particularity of this experiment lies in the fact that independently co-clustering the continuous and the binary parts of the data would only distinguish two clusters of rows but jointly, the co-clustering of the data sets should extract four clusters of rows. In this experiment, we study the effect of the size of the data matrix and the level of overlap.

• The size of the data matrix: the data size is defined by the number of rows which is equal to the number of continuous columns and to the number of binary columns. We consider the sizes 25, 50, 100, 200 and 400 rows (and columns of each type) for which the resulting matrices will have 25 × 50, 50 × 100, 100 × 200, 200 × 400 and 400 × 800 entries respectively. • The level of confusion where we study the effect of the overlap between the distributions. Here, we consider three levels of overlap (called confusion) between the co-clusters:

-Low: every continuous co-cluster follows a Gaussian distribution of mean µ ∈ {µ 1 = 1, µ 2 = 2} and a standard deviation σ = 0.25 while a binary co-cluster follows a Bernoulli distribution of parameter α ∈ {α 1 = 0.2, α 2 = 0.8}). This setup provides easily separable co-clusters since the regions of overlap between the observed values is small. -Medium: every continuous co-cluster follows a Gaussian distribution of mean µ ∈ {µ 1 = 1, µ 2 = 2} and a standard deviation σ = 0.5 while a binary co-cluster follows a Bernoulli distribution of parameter α ∈ {α 1 = 0.3, α 2 = 0.7}. This setup provides a relatively large overlap region which should make the cluster separability harder than in the case of low confusion. -High: every continuous co-cluster follows a Gaussian distribution of mean µ ∈ {µ 1 = 1, µ 2 = 2} and a standard deviation σ = 1 while a binary co-cluster follows a Bernoulli distribution of parameter α ∈ {α 1 = 0.4, α 2 = 0.6}. This provides a large overlap region which should make the cluster separability even more difficult.

The exact configuration of the parameters is shown in Table 1. One should note that a Gaussian mixture based co-clustering on the columns Jc 1 and Jc 2 from Table 1, would distinguish two clusters of rows by coupling {I 1 and I 3 }, on one hand, then {I 2 and I 4 }, on the other hand, as single row clusters. Similarly, a Bernoulli based co-clustering on the columns Jd 1 and Jd 2 should distinguish two clusters of rows by associating {I 1 with I 2 } and {I 3 with I 4 }. By performing a co-clustering on the mixed data, we expect to distinguish four clusters of rows.

µ and α Jc1 Jc2 Jd1 Jd2 I1 µ2 µ1 α2 α1 I2 µ2 µ2 α2 α1 I3 µ2 µ1 α2 α2 I4 µ2 µ2 α2 α2
Table 1: The specification of the true parameters.

Our experiments are performed in two steps: apply the co-clustering algorithm to the continuous data and to the binary data separately, then apply the algorithm on the mixed data.

Evaluation of the results

Knowing the true clusters of each row and column of the data, we choose to measure the performance of a co-clustering using the Adjusted Rand's Index ( [START_REF] Hubert | Comparing partitions[END_REF]) for the rows and columns. The Adjusted Rand index (ARI) is a commonly used measure of similarity between two data clusterings that can be used to measure the distance (as a probability of agreements) between the true row and column partitions and the partitions found by the co-clustering. The ARI has a maximum value of 1 for identical partitions and a minimal value of zero for independent partitions. We will thus recover and compare the ARI of rows and columns in the three cases: when co-clustering the continuous data alone, when co-clustering the binary data alone, and when co-clustering the mixed data.

For each configuration, we generate 3 data samples according to the previously illustrated parameters and we present the results in the form of violin plots. A violin plot ( [START_REF] Hintze | Violin plots: A box plot-density trace synergism[END_REF]) is a numeric data visualization method that combines the advantages of a box plots with an estimation of the probability density over the different values, which gives a better visualization of the variability of the results as well as important statistics such as the mean, the median and the extent of the measured values.

Validating our implementation

To validate our implementation, we applied our implementation of the coclustering algorithm to the continuous part alone and to the binary part alone while comparing the results with those of the blockcluster package ( [START_REF] Bhatia | blockcluster: An r package for model based co-clustering[END_REF]). Blockcluster is an R package for co-clustering binary, contingency, continuous and categorical data that implements the standard latent block models for co-clustering uni-type data.

Figure 1 shows a comparison between the adjusted Rand index (of rows and columns) of the co-clustering obtained using blockcluster compared to our proposed approach. The comparison confirms that our implementation provides very comparable results, in terms of ARI and of parameter estimation, with respect to the blockcluster package in most of the cases. In particular, BC provides better ARI when co-clustering the binary data while our approach provides similar or remarkably better results when co-clustering the continuous data. However, in terms of computation time, our implementation takes at least ten times longer than the blockcluster package. This is mainly because we needed high quality in our comparison experiments, and therefore we focused on quality rather than computation time in our implementation (see Section 5).

The advantage of mixed data co-clustering

One approach to co-clustering mixed data consists of performing a coclustering on each data type then jointly analyzing the results to conclude a co-clustering like structure for the complete data. This experiment provides an example of configurations where such joint analysis remains incapable of finding the true clusters of rows. Figure 2 compares the partition of rows found by the co-clustering of the continuous data with the partition found by the co-clustering of the binary part. Had the two co-clusterings correctly discovered the true clusters of rows, the partitions would be coherent and the ARI would approach 1, which is not the case. In fact, regardless of the data size and of the level of overlap between the distributions, the two partitions are completely independent as shown by the ARI values, which are at maximum zero. This shows that although the same row clusters are present in both data types, the joint analysis of the two independent co-clusterings does not extract the common and global structure and does not provide any additional information on the true distribution compared to a uni-type data analysis. Given such mixed data, the correspondence between the continuous and binary partitions is virtually null. This leaves the choice open for interpreting either the continuous co-clusters or the binary ones. Our approach proposes to use the full data and provides co-clusters for which the accuracy of the row clusters is at least as good as the best of the two choices. Furthermore, mixed data co-clustering significantly improves the accuracy of the retrieved partition in the majority of the studied cases (Figure 3).

From Figure 3, it is clear that, regardless of the level of overlap between the distributions and regardless of the size of the matrix, co-clustering the mixed data, instead of separately co-clustering the continuous and the binary parts, improves significantly the quality of the obtained row partition (see Figures 3a, 3b, and3c). In fact, in the worst case scenarios, mixed data co-clustering provides ARI of rows that are at least as good as the best ARI results when performing uni-type data analysis. On the other hand, the adjusted Rand indexes of columns do not necessarily improve significantly (in some cases, it does), which is expected because the configuration is set so that the clusters of columns are separable using uni-type data and the mixed analysis would not improve the performance of the clustering of columns (independence between the two data types in terms of column clusters). With respect to the data size and the level of overlap between the distributions, we notice the following.

• Influence of the data size: as the data size increases, the quantity of the data units used by the optimization algorithm increases, which facilitates the convergence of the algorithms to the true underlying distributions. This effect can be observed from the ARI values, shown in Figure 3, and mainly in the case of binary and mixed data. • Influence of the level of confusion: as expected, when the level of confusion between the distributions increases, it becomes harder to recover the exact true partition of rows. This effect is particularly visible in Figures 3f and3c, where the high level of confusion makes the separation of the clusters difficult in the case of binary (and consequently mixed) data and particularly in small matrices.

To summarize, the joint co-clustering of the continuous and binary variables of the simulated data sets enables us to use the full data and obtain considerably better accuracy, compared to an independent analysis by data type. The results of the co-clustering (both uni-type and mixed) are at their best when the level of confusion is low or the data matrix is big. With respect to the level of confusion, this behavior is expected since the true structure of the data is well separable. In fact, the level of confusion simulates the overlap between the distributions. Therefore, the higher the overlap, the data will contain more observations with relatively equal probabilities to belong to either of the distributions. Hence, a decrease in the accuracy of the clustering as it is measured over all the observations. The effect of bigger matrices can be explained by the fact that the more data is present, the more iterations are required by the algorithm which improves the quality of the estimated parameters.

• The number of co-clusters: we choose three different partitions g × (m c +m d ) of the original data matrix: 2×(2+2), 3×(3+3), and 4×(4+4). • The size of the data: the size of the data is defined by the number of rows and the total number of columns. For this experiment, we choose the sizes 25, 50, 100, 200 and 400 for rows. For the number of columns, we distinguish two different configurations:

-square matrices: the number of columns of each type is equal to the number of rows. -rectangular matrices: we set the number of columns (of each type) to 5, 10, and 20.

• The level of confusion: similarly to the first experiment, we consider three levels of overlap between the distributions: Low (with Gaussian means µ ∈ {p 1 = 1, p 2 = 2}, Gaussian standard deviations σ = 0.25 and Bernoulli parameters α ∈ {p

1 = 0.2, p 2 = 0.8}), Medium (µ ∈ {p 1 = 1, p 2 = 2}, σ = 0.5 and α ∈ {p 1 = 0.3, p 2 = 0.7}) and High (µ ∈ {p 1 = 1, p 2 = 2}, σ = 1 and α ∈ {p 1 = 0.4, p 2 = 0.6}). µ or α J1 J2 I1 p1 p1 I2 p1 p2 µ or α J1 J2 J3 I1 p1 p2 p1 I2 p1 p2 p2 I3 p1 p1 p1 µ or α J1 J2 J3 J4 I1 p2 p1 p2 p1 I2 p2 p1 p2 p2 I3 p2 p2 p2 p2 I4 p2 p1 p1 p1
Table 3: The true parameter specification with 2 × (2 + 2), 3 × (3 + 3) and 4 × (4 + 4) co-clusters.

The specification of the co-clusters and their configuration are shown in Table 3. Similarly to the first experiment, we generate 3 samples of each data configuration according to its parameters and we present the resulting ARI in the form of violin plots. To present the co-clustering results, we distinguish between square matrices and rectangular ones.

The co-clustering results: square matrices

Although each of the continuous and binary parts of the data can be sufficient to extract the underlying structure of the data, we notice that, as in the first experiment, jointly co-clustering the continuous and binary data clearly improves the performance of the co-clustering.

Figures 4, 5 and6 show the adjusted Rand indexes of rows and columns by level of confusion and with respect to the various parameters, in the case of continuous, binary and mixed data co-clustering.

From the ARI plots (Figure 4 and Figure 5 in particular), the first noticeable result is that the binary part of the data is sensitive to the size of the data, to the number of co-clusters and to the level of confusion while the continuous part is generally more stable and is mostly influenced only by the number of co-clusters and the size of the data.

• Influence of the number of co-clusters: given the same data size and the same level of overlap between the clusters, we notice (Figure 4) that as the number of co-clusters increases, the extraction of the true partition (both in terms of rows and column clusters) becomes harder. This effect is observed in particular in the case of binary variables as the variability of the results is greater when the number of co-clusters becomes high. However, this variability is less drastic in the case of continuous and mixed data (see Figures 5a , 5b, and 5c for example). The greater the number of clusters, the more data is required for the true partition to be found. • Influence of the data size: the global performances of the co-clustering of uni-type data (which we have established is equivalent to the standard LBM co-clustering) confirms (as established in Section 4.1.4) that the co-clustering performs better as the data size increases. Additionally, we notice that the continuous part of the data is always easier to co-cluster than the binary part. This is almost regardless of the data size (except in the case of large number of co-clusters: 4 × (4 + 4)). The binary part on the other hand performs particularly worse for small matrices. In summary, the best partitioning of the mixed co-clusters is obtained, regardless of the number of co-clusters and the level of confusion, with medium to large matrices.

• Influence of the level of confusion: the co-clustering of the mixed data performs as expected with respect to the level of confusion. The higher the confusion, the more difficult is the extraction of the true partition of the rows, particularly in the case of small matrices (compare for example the Figures 4a, 5a, and 6a). On the contrary, even when the level of confusion is high, the quality of the recovered co-clusters improves with the size of the data (see the evolution of the ARI values in Figure 6).

The co-clustering results: rectangular matrices

Figure 7 shows the adjusted Rand indexes of rows by level of confusion and with respect to the various parameters, in the case of rectangular matrices and 2 × (2 + 2) co-clusters.

From this experiment, we notice that even for rectangular matrices, the same conclusions are valid. In particular, the proposed approach extracts the true structure of the data in the case of low confusion. As the level of overlap between the co-clusters increases, the co-clustering of the binary part becomes less accurate both in the case of a standard LBM on uni-type data and the case of mixed data. Finally, the bigger the data size, the more accurate is the co-clustering both using uni-type and mixed data. As with the square matrices, an improvement in the ARI of columns is also noticed when using mixed data. The same conclusions are valid for the configurations containing 3 × (3 + 3) and 4 × (4 + 4) co-clusters.

Discussion

When applying the co-clustering algorithm on uni-type data, we noticed some optimization problems. Firstly, the algorithm converges to a local optimum which corresponds, very often, to a unique cluster of rows and a unique cluster of columns. We have thus addressed the problem by forcing a minimal number of iterations (the c parameter in Algorithm 1) which considerably enhanced the quality of the optimization results. However, the algorithms (both our approach and the blockcluster package) do not perform the same way when the marginal parameters are equal per cluster or when they are different. To study this effect, we have considered a second configuration (call it the symmetric case) where the marginal parameters are equal. Table 4 shows an example of the parameter specification of such configurations. In the symmetric configuration, where the marginal parameters are equal, the problem of cluster separability becomes intrinsically difficult (especially for square matrices) and the optimization algorithm tends to have trouble getting out of the zone of the local optimum corresponding to one single cluster of rows and one single cluster of columns, in which it falls since the very first iterations. To solve this problem, we required the algorithm to start with small steps when computing the assignments to the clusters (s, tc and td) without letting the criterion fully stabilize, then after few first steps in this initial phase, we iterate until criterion stabilization. This strategy provides better solutions in the case of binary data but results in no notable improvement in some continuous cases. As mentioned earlier, because of this focus on obtaining high quality results, our implementation takes at least ten times longer than the blockcluster package but provides more accurate row and column partitions and more accurate parameter estimation. Table 5 shows a comparative example of the means computation time for the rectangular matrix containing 100 rows and 2 × (2 + 2) co-clusters.

µ or α J1 J2 I1 p1 p2 I2 p2 p1 µ or α J1 J2 J3 I1 p1 p1 p2 I2 p1 p2 p1 I3 p2 p1 p1 µ or α J1 J2 J3 J4 I1 p1 p1 p1 p2 I2 p1 p1 p2 p1 I3 p1 p2 p1 p1 I4 p2 p1 p1 p1

Conclusion and future work

In this article, we have proposed an extension of the latent block models to the co-clustering of mixed type data. The experiments show the capability of the approach to estimate the true model parameters, extract the true distributions from simulated data, and provide better quality results when the complete data set is used rather than separately co-clustering the continuous or binary parts. The proposed approach comes as a natural extension of the LBM based co-clustering and performs a co-clustering of mixed data in the same way that a standard LBM based co-clustering applies to uni-type data.

On the course of our experiments, we have noticed that for the data sets with equal marginal parameters, both our algorithm and the state of the art algorithm implemented in the package blockcluster tend to fall in a local optimum. This is a limitation to the latent block based methods for coclustering, mainly in the context of an exploratory analysis where the true underlying distributions are unknown.

In our future works, we aim to extend the approach to the case of categorical data and beyond binary data and to study the option of BIC based regularization to automatically infer the number of clusters of rows and the number of clusters of columns.

  where I is the set of n objects characterized by continuous and binary variable, J c is the set of d c continuous variables and J d the set of d d binary variables. Our goal is to find a partition of rows into g clusters, a partition of the continuous columns into m c clusters, and a partition of the binary columns into m d clusters, denoted Z, W c and W d respectively.

  axIter and Unstable(Criterion) do For every jc = 1 : dc, j d = 1 : d d , lc = 1 : mc and l d = 1 : m d , compute tc t+1 jclc and td t+1 j d l d : equation (3) For every k = 1 : g, lc = 1 : mc and l d = 1 : m d , compute ρ t+1 c , ρ t+1 d , µ t+1 klc , σ t+1 klc and α t+1 kl d

Fig. 1 :

 1 Fig.1: First experiment: comparing the ARI of rows and the ARI of columns (the yaxis) using our implementation (MLBM) with the blockcluster (BC) package, applied to the continuous and binary data. Compare the red plots with the green ones and the blue with the magenta. The higher the ARI values, the better.

Fig. 2 :

 2 Fig. 2: First experiment: comparing the partition of rows obtained using the continuous part alone with the partition obtained using the binary part of the data. The y axis shows the measured ARI values.

Fig. 3 :

 3 Fig. 3: First experiment: ARI of rows and ARI of columns (in the y-axis) in the continuous, binary and mixed data.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Second experiment (Low confusion): ARI of rows and ARI of columns (in the y-axis) in the case of continuous, binary and mixed data.

Fig. 6 :

 6 Fig. 6: Second experiment (High confusion): ARI of rows and ARI of columns (the yaxis) in the case of continuous, binary and mixed data.

Fig. 7 :

 7 Fig. 7: Second experiment (2 × (2 + 2) co-clusters): ARI of rows (the y-axis) in the case of continuous, binary and mixed data.

Table 4 :

 4 The true specification of the co-clusters in a symmetric configuration with 2 ×

	(2 + 2), 3 × (3 + 3) and 4 × (4 + 4) co-clusters.

Table 5 :

 5 Example of the computation time (in seconds).

	Number of columns	→	5 columns	10 columns	20 columns
	Level of overlap	measure\method	MLBM BC	MLBM BC	MLBM BC
	Low confusion	mean	2.97 0.01	4.3 0.016	8.31 0.03
		sd	0.11 0.005	0.4 0.005	0.6 0.005
	Medium confusion	mean	8.01 0.01	5.5	0.01	8.4	0.01
		sd	1.2	0.01	0.2	0	0.3	0
	High confusion	mean	15	0.04	16.4 0.01	25.9 0.01
		sd	12	0.01	6.4	0.01	5.2	0.01

However, this is a well known phenomenon in the standard the standard LBM context. For example, in [START_REF] Govaert | Co-Clustering[END_REF], the authors note that given the same number of co-clusters in the data, the classification error rate depends not only on the parameters but also on the size of the data matrix (the Bayes classification risk decreases with the size of the data). Also, [START_REF] Mariadassou | Convergence of the groups posterior distribution in latent or stochastic block models[END_REF] show that, when the estimated parameters converge to the true parameters, the recovered partitions will converge to the true partitions when the size of the data becomes sufficiently large. Using the mixed data latent block model, the accuracy of the estimated parameters is remarkable which reinforces the hypothesis that, as in the standard latent block models, given enough data, our approach would converge to the true partitions. Table 2 shows examples of the estimated parameters using the mixed data latent block model MLBM on the data containing 100 rows.

Low confusion

Jc2

Jc1 (0.50, 0.520) (0.50, 0.497) (0.50, 0.502) (0.50, 0.493) (0.50, 0.505) (0.50, 0.505) (0.50, 0.501) (0.50, 0.504)

Jd1

Jd2 (0.7, 0.718) (0.3, 0.297) (0.7, 0.695) (0.3, 0.315) (0.7, 0.704) (0.7, 0.685) (0.7, 0.700) (0.7, 0.674) High confusion

Jc1 (1.00, 1.016) (1.00, 0.989) (1.00, 1.018) (1.00, 0.979) (1.00, 0.999) (1.00, 1.001) (1.00, 0.992) (1.00, 1.008)

Jd2

Jd1 (0.4, 0.351) (0.6, 0.597) (0.4, 0.399) (0.6, 0.594) (0.6, 0.591) (0.6, 0.590) (0.6, 0.631) (0.6, 0.616)

Second experiment

The objective of this experiment is to study the impact of the number of co-clusters, the size of the data and the level of confusion between the distributions.

The data set

To study the influence of the number of co-clusters, the data sets are generated using the following parameters.


Aichetou Bouchareb

Marc Boullé

Fabrice Clérot

Fabrice Rossi

Co-clustering based exploratory analysis of mixed-type data tables

Introduction

Data analysis techniques can be divided into two main categories: supervised analysis, where the goal is to predict a mapping between a set of input variables and a target output variable, and unsupervised analysis where the objective is to describe the set of all variables by uncovering the underlying structure of the data. This is often achieved by identifying dense and homogeneous clusters of instances, using a family of techniques called clustering. Co-clustering ([Good, 1965, Hartigan, 1975]), also called cross-classification, is an extension of the standard clustering approach. It is a class of unsupervised data analysis techniques that aim at simultaneously clustering the set of instances and the set of variables of a data table.

Over the past years, numerous co-clustering methods have been proposed (for example, [Bock, 1979], [Govaert, 1983], [START_REF] Dhillon | Informationtheoretic co-clustering[END_REF], and [START_REF] Govaert | Co-Clustering[END_REF]). These methods differ on several axes including: data types, clustering assumptions, clustering techniques, expected results, etc. In particular, two main families of methods have been extensively studied: matrix reconstruction based methods where the co-clustering is viewed as a matrix approximation problem, and mixture model based methods where the co-clusters are defined by latent variables that need to be estimated (for a full review of co-clustering techniques, readers are referred to [START_REF] Brault | Revue des méthodes pour la classification jointe des lignes et des colonnes d'un tableau[END_REF]). The typical models used in mixture based approaches are Gaussian for numerical data, multinomial for categorical data and Bernoulli for binary data.

Fig. 1: An illustration of a co-clustering where the original binary data table is on the left and the co-clustered binary table is on the right. Figure 1 shows an example of a binary data table representing n = 10 instances and m = 7 variables ( [START_REF] Govaert | Block clustering with Bernoulli mixture models : Comparison of different approaches[END_REF]) and the binary table of co-clusters resulting from a co-clustering into 3 × 3 = 9 co-clusters. The table of co-clusters provides a summary of the original data and allows to view the main associations between the set of instances and the set of variables.

Co-clustering methods are naturally limited to homogeneous data where all variables are of the same nature: binary, numerical or categorical. In the present paper, we propose to extend these exploratory analysis methods to the case of mixed-type data using a two-step methodology. The first step consists in binarizing the data using a number of parts, given by the analyst, using equal frequency discretization in the case of numerical variables and keeping the most frequent values in the case of categorical variables. The second step consists of using a co-clustering method between the instances and variable parts, leading to a partition of the instances on one hand and a partition of the variable parts on the other hand.

Given a number of parts, our objective is to require no further parameters such as the number of instance clusters and the number of variable part clusters. Therefore, in the co-clustering step, we use the MODL approach ( [Boullé, 2011]) for its non parametric nature, its efficiency for extracting correlation structures from the data, its scalability and its robustness to overfitting induced by the embedded regularization.

Since we are in the context of exploratory analysis of a mixed-type data table, we compared our methodology to the most widely used factor analysis method in case of the presence of categorical variables: Multiple Correspondence Analysis (MCA). Indeed, MCA is factor analysis technique that enables one to extract and analyze the correlations between categorical variables while performing a typology of instances. It enables the instances and the variables to be handled in a complementary manner by duality where groups of instances can be interpreted using variables and vice-versa. These aims of MCA are thus consistent with the goals of co-clustering, hence the usefulness of such comparison.

The remainder of this paper is organized as follows. In section 2 we give an outline of the MODL approach for co-clustering, then in section 3 we illustrate our proposed methodology for co-clustering mixed-type data tables.

In section 4, we present a summary of the MCA basics. Section 5 presents the experimental results along with a comparative analysis. Finally, conclusions and future work are presented in section 6.

MODL based co-clustering of two categorical variables

This section presents a summary of the MODL approach ( [Boullé, 2011]) that clusters simultaneously the values of two categorical variables X and Y . In definition 1, we introduce a family of models for estimating the joint density of two categorical variables, based on partitioning the values of each variable into groups of values (hence MODL performs value oriented co-clustering). We then present the evaluation criterion for these models in theorem 1. Definition 1. A co-clustering model of two categorical variables is defined by:

• a number of groups for each variable,

• the partition of the values of each variable into groups of values,

• the distribution of the instances of the data over the cells of the resulting data grid, • for each variable and each group, the distribution of the instances of the group on the values of the group.

Notations:

• N : number of instances • V, W : number of values for each variable (assumed known)

• I, J: number of groups for each variable (unknown)

• G = IJ: number of cells in the resulting data grid • m i. , m .j : number of values in group i (resp. j)

• n v. , n .w : number of instances for value v (resp. w)

• n vw : number of instances for the pair of values (v, w)

• N i. , N .j : number of instances in the group i (resp. j)

• N ij : number of instances in the cell (i, j) of the data grid Every model from the set of models in definition 1 is completely defined by the choice of I, J, N ij , n v. , n .w , and the partition of the values of each variable to groups (clusters). In the co-clustering context, these parameters correspond to the number of clusters per variable, the multinomial distribution of the instances on the co-clusters, and the parameters of the multinomial distributions of the instances of each variable cluster on the values of the cluster. Notice that these parameters are optimized by the algorithm and not fixed the analyst: by using MODL we will not add any additional user chosen parameter to the data pre-processing parameter.

The number of values in each cluster m i. and m .j result from the partition of the values of each variable into the defined number of clusters. Similarly, the number of instances per cluster N i. and N .j are derived by summation from the number of instances per co-cluster (N i. = j N ij and N .j = i N ij ).

In order to select the best model, a MAP based criterion is chosen: we maximize the probability of the model given the data P (M |D) = P (M )P (D|M )

P (D)
. We use a prior distribution on the model parameters that exploits the natural hierarchical nature of the parameters. The distribution is uniform at each level of the hierarchy. In practice, it serves as a regularization term which prevents the optimization from selecting systematically a high number of groups, for instance.

Using the formal definition of the joint density estimation models and its prior hierarchical distribution, the Bayes formula enables us to compute the exact probability of a model given the data, which leads to theorem 1.

Theorem 1. Among the set of models, a co-clustering model distributed according to a uniform hierarchical prior is Bayes optimal if its evaluation according to the following criteria is minimal ( [Boullé, 2011]):

c(M ) = log V + log W + log B(V, I) + log B(W, J) + log N + G -1 G -1 + I i=1 log Ni. + mi. -1 Ni. -1 + J j=1 log N.j + m.j -1 N.j -1 + log N ! - I i=1 J j=1 log Nij ! + I i=1 log Ni.! + J j=1 log N.j ! - V v=1 log nv.! - W w=1 log n.w! (1)
where B(V, I) is the number of ways of partitioning a set of V elements into I nonempty groups which can be written as a sum of the Stirling number of the second kind: B(V, I)

= I i=1 S(V, i).
The first line of this criterion corresponds to the prior distribution of choosing the numbers of groups and to the partition of the values of each variable to the chosen number of groups. The second line represents the specification of the parameters of the multinomial distribution of the N instances on the G cells of the data grid and the specification of the multinomial distribution of the instances of each group on the values of the group. The third line corresponds to the likelihood of the distribution of the instances on the data grid cells and the likelihood of the distribution of the instances per group over the values in the group, by the mean of a multinomial term.

The estimation of the joint density of two categorical variables distributed according to hierarchical parameter priors is implemented in the software Khiops1 . We use this software for our experiments presented in section 5. The detailed formulation of the approach as well as optimization algorithms and asymptotic properties can be found in [Boullé, 2011].

Mixed-type data co-clustering

In this section we present our two-step approach. The first step is described in Sections 3.1 and 3.2 and consists in binarizing the numerical and categorical variables. The second step leverages the MODL approach to perform a coclustering of the instances × binarized variables data, see Section 3.3.

Data pre-processing

The first step of our methodology consists of binarizing all variables using a user parameter k, which represents the maximal number of parts per variable. In the case of a numerical variable, these parts are the result of an unsupervised discretization of the range of the variable into k intervals with equal frequencies. In the case of a categorical variable, the k -1 most frequent values define the first k -1 parts while the k th part receives all the other values. An alternative discretization is with equal bins. However, frequency based discretization reinforces the robustness of the approach and minimizes the effect of outliers if present in the data (both outlier instances and variable values).

The parameter k defines the maximal granularity at which the analysis can be performed. A good choice of k is related to a trade off between the fineness of the analysis, the time required to compute the co-clustering of the second step, and the interpretability of the co-clustering results. The computational cost of the MODL co-clustering in the worst case is in O(N √ N log N ) where N is the total number of instances (in our case, N = n × m, see Section 3.2), but the observed computation time tends to decrease with smaller k, when data is far from the worse case. Also the size of the data set and its complexity can be taken as an indicator, small values are probably sufficient for small and simple data sets while for larger ones, it would be wise to choose a larger parameter k. Nevertheless, we recommend to start with high values of k since it gives a detailed description of the data. Starting from a detailed description, the MODL approach will group the variable parts that needed not to be separated in the same cluster which can only enhance the level of correspondence of the resulting co-clustering to the original data, without much loss of information.

One should note, however, that the granularity parameter k is far less restrictive than other common parameters such as the number of instance clusters and the number of variable clusters, commonly used in the vast majority of co-clustering methods. In our experiments, we used k = 5 for a small data set and k = 10 for a relatively large one.

If we take the Iris database for example, the output of the binarization step, for k = 5, is illustrated in table 1.

SepalLength SepalWidth PetalLength PetalWidth Class ] -∞; 5.05] ] -∞; 2.75] ] -∞; 1.55] ] -∞; 0.

Data transformation

The MODL approach ( [Boullé, 2011]), summarized in Section 2, has been chosen because it is non parametric, effective, efficient, and scalable. Although designed for joint density estimation, MODL has also been applied to the case of instances×binary-variables. An example of such application is that of a large corpus of documents, where each document is characterized by tens of thousands of binary variables representing the usage of words. In this case, the corpus of documents is transformed beforehand into a representation in the form of two variables IdText and IdWord.

IdInstance IdVarPart

I1 SepalLength]5.05; 5.65]

I1 SepalWidth]3.45; +∞[ I1 PetalLength] -∞; 1.55] I1 PetalWidth] -∞; 0.25] I1 Class{Iris-setosa} I2 SepalLength ] -∞; 5.05] I2 SepalWidth]2.75; 3.05] I2 PetalLength] -∞; 1.55] I2 PetalWidth] -∞; 0.25] I2 Class{Iris-setosa}
Table 2: The first 10 instances of the binarized Iris database

In the same manner, we transform the binarized database into two variables IdInstance and IdVarPart by creating, for each instance, a record per variable that logs the link between the instance and its variable part. The set of n initial instances characterized by m variables is thus transformed into a new data set of N = n × m instances and two categorical variables, the first of which contains V = n values and the second containing, at most, W = m × k values. For instance, in the Iris database, this transformation results in two columns of 750 instances. Table 2 shows the first ten instances. Notice that after the transformation, the algorithm cannot leverage two aspects of the data: the actual value taken by a variable inside a variable part and the original links between variable parts. In other words, the fact that SepalLength]5.05; 5.65] and SepalLength ] -∞; 5.05] both refer to the same original variable is not leveraged by MODL.

Co-clustering and co-cluster interpretation

Now that our data is represented in the form of two categorical variables, we can apply MODL to find a model estimating the joint density between these two variables. This results in two partitions of the values of the newly introduced categorical variables. Clusters of values of IdInstance are in fact clusters of instances while clusters of values of IdVarPart are clusters of variable parts. Thus the results is a form of co-clustering in which variables are clustered at the level of parts rather than globally. In the resulting co-clustering, the instances of the original database (values of the variable IdInstance) are grouped if they are distributed similarly over the groups of variables parts (values of the variable IdVarPart), and vice-versa.

When the optimal co-clustering is too detailed, coarsening of the partitions can be implemented by merging clusters (of objects or variable parts) in order to obtain a simplified structure. While this model coarsening approach can degrade the co-clustering quality, the induced simplification enables the analyst to gain insight on complex data at a coarser level, in a way similar to exploration strategies based on hierarchical clustering. The dimension on which the merging is performed and the best merging are chosen optimally at each coarsening step with regards to the minimum divergence from the optimal co-clustering, measured by the difference between the optimal value of the criterion and the valued obtained after merging to clusters.

Multiple Correspondence Analysis

Factor analysis is a set of statistical methods, the purpose of which is to analyze the relationships or associations that exist in a data table, where rows represent instances and columns represent variables (of any type).

The main purpose of factor analysis is to determine the level of similarity (or dissimilarity) between groups of instances (problem classically treated by clustering) and the level of associations (correlations) between the observed variables. Multiple correspondence analysis is a factor analysis technique that enables one to analyze the correlations between multiple categorical variables while performing a typology (grouping) of instances and variables in a complementary manner.

MCA in practice

Let x = (x ij , i ∈ I, j ∈ J) be the instance×variables data table, where I is the set of n studied objects and J is the set of p categorical variables (with m j categories each) characterizing the objects. Since mathematical operations would not make sense in categorical variables, MCA uses an indicator matrix called complete disjunctive table (CDT) which is a juxtaposition of p indicator matrices of all variables where rows represent the instances and columns represent the categories of the variable. This CDT can be considered as a contingency table between instances and the set of all categories in the data table.

For a given CDT, T , the sum of all elements of each row is equal to the number p of variables, the sum of all elements of a column s is equal to the marginal frequency n s of the corresponding category, the sum of all columns in each indicator matrix is equal to 1, the sum of all elements in T is equal to np, the matrix of row weights is given by r = 1 n I, and the column weights are given by the diagonal matrix D = diag(D 1 , D 2 , . . . , D p ) where each D j is the diagonal matrix containing the marginal frequencies of all categories of the j th variable.

Main mathematical results for MCA

The principal coordinates of categories are given by the eigenvectors of 1 p D -1 T t T, which are the solutions of the equation:

1 p D -1 T t Ta = µa
The principal coordinates of instances are given by the eigenvectors of 1 p TD -1 T t , which are the solutions of the equation:

1 p TD -1 T t z = µz
We deduce ( [Saporta, 2006]) the transition formulas given by z = 1 √ µ 1

p Ta and a = 1 √ µ D -1 T t z, which describes how to pass between the coordinates.

Note that:

• the total inertia is equal to ( m p -1), where m is the total number of categories.

• the inertia of all the m j categories in the j th variable is equal to 1 p (m j -1). Since the contribution of a variable to the total inertia is proportional to the number of categories in the variable, it is preferable to require all variables to have the same number of categories, hence the utility of the pre-processing step (section 3.1).

• the contributions of an instance i and of a category s to a principal axis are given by:

Ctr h (i) = 1 n z 2 ih µ h et Ctr h (s) = n s np a 2 ih µ h
• the contribution of a variable to the inertia of a factor is equal to the sum of contributions of all categories in the variable to that same axis. This contribution measures the level of correlation between the variable and the principal axis.

MCA can be used to simultaneously analyze categorical and numerical variable. To do so, we follow the classic approach of decomposing the range of each numerical variable into intervals.

Experiments

We start the experiments by comparing our methodology (Section 3) with MCA (Section 4) using the Iris database for didactic reasons, then we evaluate our approach using the Adult database ( [Lichman, 2013]) to evaluate its scalability.

The case study: Iris database

The Iris database consists of n = 150 instances and m = 5 variables, four numerical and one categorical.

Co-clustering

Fig. 2: Coclustering pour la base Iris

After binarizing the Iris data using a granularity of k = 5 parts and applying the MODL co-clustering method, we found that the optimal grid consists of 3 clusters of instances and 8 clusters of variable parts. Figure 2 illustrates this grid where rows represent the instance clusters and columns represent the variable part clusters. The mutual information between the two dimensions can be visualized in each cell, where the red color represents an overrepresentation of the instances compared to the case where the two dimensions are independent and the blue color represents an under representation.

The three instance clusters, shown in figure 2, can be characterized by the types of flowers of which they are composed and by the most represented variable parts per cluster (the red cell of each row of the grid):

• in the first row: a cluster of 50 flowers, all of the class Iris-setosa and characterized by the variable parts: Class{Iris-setosa} Notice first that, as expected, the methodology enables us to group variable (parts) of different nature in the same cluster.

The three instance clusters are easily understandable as they represent the small, large and medium flowers respectively. These clusters are mainly explained by three clusters of variable parts containing the variables Class, PetalLength and PetalWidth. In fact it is well known that in the Iris data set, the three classes are well separated by the Petal variables. This is reflected here by the grouping of the variables as well as by the instance clusters.

Conversely, looking at the clusters of variable parts, one can distinguish two non informative clusters (the fourth and eighth columns which are the two columns with the least contrast), which are based essentially on the variable SepalWidth:

• the fourth column contains the parts: SepalWidth] -∞; 2.75], SepalWidth]2.75; 3.05], and SepalLength]5.65; 6.15],

• the eighth column contains the parts: SepalWidth]3.05; 3.15] and SepalWidth]3.15; 3.45].

The small values of SepalWidth (fourth column) are slightly over-represented by the cluster of instances associated to the classes Iris-versicolor and Irisvirginica while the intermediate values (eighth column) are slightly overrepresented for the cluster of instances associated to Iris-versicolor.

MCA analysis

MCA analysis is performed based on the same data binarization as previously.

The distribution of eigenvalues (Figure 3) indicates that the first two principal axes do capture enough information with a cumulative variance of 38.30%. Therefore, we will limit our analysis to the first factorial plan.

The comparison between the projection of variables (figure 4 The projection of instances (on the left of figure 4) shows a mixture between Iris-virginica and Iris-versicolor. These results are identical to those found using the co-clustering analysis.

The variable parts issued from SepalWidth are weakly correlated with the others and contribute less the first factorial plan: the small values (less than 3.05) are associated with the mixture zone between Iris-virginica and Iris-versicolor, the intermediate values (between 3.05 and 3.45) have their projections in between Iris-virginica and Iris-setosa (they are therefore present in both flowers).

These results are also in agreement with the results deduced from the co-clustering (see the above interpretation of the fourth and eighth columns in the co-clustering).

Finally, on this didactic example where the results of MCA are easily interpretable, a good agreement emerges between the MCA and the proposed co-clustering approach.

The case study: Adult database

The Adult database is composed of n = 48842 instances represented by m = 15 variables, 6 numerical and 9 categorical. When the Adult data is binarized, using k = 10, and the transformation into two variables is performed as presented in Section 3, we obtain a data set of N ≈ 750, 000 rows and two columns: the IdInstance variable containing around n ≈ 50, 000 values (corresponding to the initial instances) and the IdVarPart variable containing m × k ≈ 150 values (corresponding to the variable parts). The co-clustering algorithm is an anytime, regularly issuing its quality index (the achieved level of compression). For the Adult database, the co-clustering takes about 4 mn for a first quality result (a time beyond which the level of compression does not improve significantly). However, we proceed with the optimization for about an hour which results in around 5% of improvement in the log-likelihood of the model. The obtained result is very detailed, with 34 clusters of instances and 62 clusters of variable parts. In an exploratory analysis context, this level of detail hinders the interpretability.

Co-clustering

In our case, the results can be simplified by iteratively merging the rows and columns of the finest clusters until reaching a reasonable percentage of the initial amount of information. Figure 5 presents the co-clustering results with 34 × 62 clusters (on the left), which represents 100% of the initial information, and a simplified version with 10 × 14 clusters preserving 70% of the initial information in the data.

The first level of retrieved patterns appears clearly when we consider dividing the clusters of instances into two parts, visible on the top half and the bottom half of the co-clustering cells presented in figure 5. The instance clusters in the top half are mainly men with a good salary, with an over-representation of the variable part clusters containing sex{Male}, relationship{Husband}, relationship{Married...}, class{More}, age]45.5; 51.5], age]51.5; 58.5], hoursPerWeek]48.5; 55.5], hoursPerWeek]55.5; +∞[. The instance clusters in the bottom half are mainly for women or rather poor unmarried men, with an over-representation of the variable part clusters containing class{Less}, sex{Female}, maritalStatus{Never-married}, maritalStatus-{Divorced}, relationship{Own-child}, relationship{Not-in-family}, relationship-{Unmarried}.

In the left side figure, the instance cluster with the most contrast (hence the most informative) is on the first row and it can easily be interpreted by the over-represented variable part clusters in the same row:

• relationship{Husband}, relationship{Married...}, • educationNum]13.5; +∞[, education{Masters}, • education{Prof-school}, • sex{Male}, • class{more}, • occupation{Prof-specialty},
• age]45.5; 51.5], age]51.5; 58.5],

• hoursPerWeek]48.5; 55.5], hoursPerWeek]55.5; +∞[. It is therefore a cluster of around 2000 instances, with mainly married men with rather long studies, working in the field of education, at the end of their careers, working extra-time with good salary.

In the right side figure, the most contrasted clusters of variable parts, hence the most informative, are those presented by the columns 4 to 9. These contain only variable parts issued from the variables education and educationNum which are the most structuring variables for this data set.

• educationNum]11.5; 13.5], education{Assoc-acdm}, education{Bachelors} (the 4 th column),

• educationNum]-∞; 7.5], education{10th}, education{11th}, education{7th-8th}(the 5 th column),

• educationNum]13.5; +∞[, education{Masters}(the 6 th column),

• educationNum]10.5; 11.5], education{Assoc-voc}, education{Prof-school} (the 7 th column),

• educationNum]7.5; 9.5], education{HS-grad}(the 8 th column),

• educationNum]9.5; 10.5], education{Some-college}(the 9 th column).

The variables education and educationNum are, respectively, categorical and numerical, very correlated as their variable part clusters seem particularly consistent.

MCA analysis

Figure 6 shows the distribution of the variability captured by the axes along with the cumulative level on information. On the contrary to the smaller Iris database, the distribution of the variance (Figure 6) indicates that the first two principal axes only capture a cumulative variance of 7.5%. Figure 7 shows the projections of the instances and variable parts on the first factorial plan where in the left side figure, the black circles are the instances that gain less than 50K and the red triangles are the instances that gain more than 50K. Without the prior knowledge about the class of each instance, which is the case in exploratory analysis, the projection of instances appears as a single dense cluster.

The projection on the first factorial plan does not allow to distinguish any clusters, which is not surprising given the low level of variability captured by this plan. However, in order to capture 20%, 25% or 30% of the variance, one needs to choose 7, 10 or 13 axes, respectively. Choosing a high number of axes, say 13, means that some post analysis of the projections is required. In order to extract potentially meaningful cluster from the MCA results, we performed a k-means on the projections of the instances and the variable parts on the factor space formed by the first 13 axes. Figure 8 shows the projection of the k-means centers with k = 10 (on the left) and k = 100 (on the right to illustrates how complex the data is). The k-means clustering of the projections with k = 2 gives two clusters containing 26178 instances associated to 50 variable parts, and 22664 instances associated with 46 variable parts, respectively. The first cluster of instances associates the variable part class{more} with being married, white, a men, having more than 10.5 years of education, being more than 30.5 years old, working more than 40.5 hours per week, or originating from Canada, Cuba, India or Philippines. The second cluster of instances associates the variable part class{less} with being young (age] -∞; 30.5]), having less than 10.5 years of education, being never married, divorced or widowed, being Amer-Indian-Eskimo, black or an other non white race (race{Other}), working for less than 40.5 hours per week, being a women or originated from countries like El-Salvador, England, Germany, Mexico, Puerto-Rico, and United-States. These clusters are consistent with the two main clusters found by the coclustering, particularly in combining being a men, married, middle aged and working extra hours with earning more than 50K and associating being a women, never married, divorced, or having a child with earning less than 50k.

Table 3 shows a summary of the k-means clustering with k = 10 indicating the contribution of each cluster to the intra-cluster variance. To avoid confusion with the clusters resulting from co-clustering, we name the k-means clusters using letters: {a, b, c, d, e, f, g, h, i, j}. Table 4 shows the confusion matrix between the clusters issued from the co-clustering method and the clusters issued from the k-means of projections.

The problem of comparing the two clusterings can be seen as a maximum weight matching problem in a weighted bipartite graph, also known as the assignment problem. It consists of finding the one-to-one matching between the nodes that provides a maximum total weight. This assignment problem can be solved using the Hungarian method [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF]. Applied on the matrix of mutual information, the Hungarian algorithm results in the following cluster associations: (1, d), (2, g), (3, j), (4, i), (5, b), (6, h), (7, f ), (8, c), (9, a), (10, e) as highlighted in table 4. These same associations are also obtained when applying the algorithm to the chi2 table. This one-to-one matching carries 76.3% of the total mutual information. The highest contributions to the conserved mutual information associate the k-means cluster a with the co-clustering cluster 9, the k-means cluster c with the co-clustering cluster 8, the k-means cluster f with the co-clustering cluster 7, the k-means cluster h with the co-clustering cluster 6, the k-means cluster i with the co-clustering cluster 4, the k-means cluster j with the co-clustering cluster 3. In terms of variable parts, these clusters are as follows:

• the cluster a contains individuals who never-worked or work as handlerscleaners, have less than 7.5 years of education, or have a level of education from the 7th to the 11th grade. • the cluster c contains instances characterized by: workclass{Self-emp-inc}, education{Assoc-acdm, Bachelors}, education num]11.5; 13.5], occupation {Exec-managerial, Sales}, race{Asian-Pac-Islander}, capital loss ]77.5; +∞[, hours per week]40.5; 48.5], hours per week]48.5; 55.5], native-country{Germany, Philippines}. • the cluster f contains instances characterized by: earning less than 50K (class{less}), being relatively young (age]26.5; 33.5]), having relatively low level of education (education{HS-grad} and education num]7.5; 9.5]), being unmarried, divorced or separated, being an Amer-Indian-Eskimo, Black or Female. • the cluster h contains instances that work less than 35.5 hours per week, are under 26.5 years old, never married and have a child. • the cluster i contains middle-aged individuals (between 41.5 and 45.5 years old), with moderate education (9.5 to 10.5 years of education) and working in farming or fishing. To summarize, the clusters obtained using a k-means on the projections of the MCA, are somewhat consistent with those obtained using the co-clustering. However, the process of extracting these clusters, through MCA analysis, is rather tedious while with co-clustering, the clusters could be extracted and explained simply by looking at the matrix of co-clusters.

Discussion

An important contribution of our methodology, compared to MCA, is its ease of application and the direct interpretability of its results. When MCA is applied to a database of a significant size, such as Adult, the projections of instances and variables on the first factorial plan (and even on the second plan) do not enable us to distinguish any particularly dense clusters. Therefore, it is necessary to choose a high number of axes in order to capture enough information. On the database Adult, we found that 13 axes explain only 30% of the information. Choosing this high number of axes meant that some post analysis of the projections (such as k-means) is necessary to extract any possible clusters. Applying this long process for cluster extraction, the results obtained using k-means, although only explaining 30% of the information, are somewhat consistent with those obtained using the co-clustering and our two-step methodology. However, with our methodology, the hierarchy of clusters enables us to choose the desired level of detail and the percentage of information, then one can distinguish, and eventually explain, the most informative clusters, recognized by their contribution to the total information.

Conclusion

In this article, we have proposed a methodology for using co-clustering in exploratory analysis of mixed-type data. Given a number of parts, chosen by the analyst, the numerical variables are discretized into intervals with equal frequencies and the most frequent values in the categorical variables are kept. A co-clustering between the instances and the binarized variables is then performed while letting the algorithm infer, automatically, the size of the summarizing matrix.

We have shown that on a small database, exploratory analysis reveals a good agreement between MCA and co-clustering, despite the differences between the models and the methodologies. We have also shown that exploratory analysis is feasible even on large and complex databases. The proposed methods is a steps toward understanding a data set via a joint analysis of the clusters of instances and the clusters of variable parts. The results of these experiments are particularly promising and show the usefulness of the proposed methodology for real situations of exploratory analysis.

However, this methodology is limited by the need for the analyst to chose a parameter, the number of parts per variable, used for data binarization. Furthermore, the co-clustering method does not follow the origins of the parts which would be useful to consider the intrinsic correlation structure that exist between the parts originated from the same variable, which form a partition. In future work, we will handle these limitations by defining co-clustering models that integrate the granularity parameter and track the clusters of variable parts that form a partition of the same variable. By defining an evaluation criterion for such co-clustering as well as dedicated algorithms, we hope to automate the choice of the granularity and improve the quality of the co-clustering results.

  25] Iris-setosa ]5.05; 5.65] ]2.75; 3.05] ]1.55; 3.95] ]0.25; 1.15] Iris-versicolor ]5.65; 6.15] ]3.05; 3.15] ]3.95; 4.65] ]1.15; 1.55] Iris-virginica ]6.15; 6.55] ]3.15; 3.45] ]4.65; 5.35] ]1.55; 1.95] ]6.55; +∞[ ]3.45; +∞[ ]5.35; +∞[ ]1.95; +∞[

  Fig. 3: Histogram of eigenvalues (on the left) and the percentage of variance captured by the axes in the MCA analysis of Iris

Fig. 5 :

 5 Fig. 5: Co-clustering of the Adult database, with 100% of information (on the left) and 70% of information (on the right).

Fig. 6 :

 6 Fig. 6: Barplots of the variability (on the left) and the cumulative information captured by the axes (on the right) in the MCA analysis of Adult.

Fig. 7 :

 7 Fig. 7: Projection of the set of instances and variable parts, of the Adult database, on the first factorial plan

Fig. 8 :

 8 Fig. 8: Projection of the k-means centers with k=10 and k=100 clusters, on the first factorial plan.

Table 1 :

 1 The output of the discretization step for k = 5

  , PetalLength]inf ; 1.55] and PetalWidth] -inf ; 0.25],• in the second row: a cluster of 54 flowers, 50 of which are of the class Iris-virginica, and characterized by the following variable parts:

	Class{Iris-virginica}, PetalLength]5.35; +inf [, PetalWidth]1.95; +inf [ and
	PetalWidth]1.55; 1.95],
	• the third row: a cluster of 46 flowers, all of the class Iris-versicolor, and
	caracterized by the variable parts:
	Class{Iris-versicolor}, PetalLength]3.95; 4.65] and PetalWidth]1.15; 1.55].

Table 3 :

 3 Summary of the clusters of instances using k-means

	cluster a	b	c	d	e	f	g	h	i	j
	1	1679 444 141 2289 886 12	7	0	48 111
	2	0	20 4096 0	0	0	0	0	0	0
	3	0	96	0	0	0	18	5	0	0 6377
	4	0	31	0	0	0	0	0	13 3588 0
	5	114 88 576 247 129 331 54 28 455 434
	6	0	59	0	0	0	0 252 3314 3072 0
	7	1 183 0	1	0 7318 776 609	0	127
	8	0	27 4512 0	0	3 150 93	0	0
	9	2503 617 0	0	0	2 299 16	0	0
	10	0	7	0 1496 1046 2	38	2	0	0

Table 4 :

 4 The confusion matrix between the co-clustering and k-means partitions.

  • the cluster j contains instances characterized by the variable parts:

age]33.5; 37.5], age]37.5; 41.5], age]45.5; 51.5], age]51.5; 58.5], workclass {Self-emp-not-inc}, fnlwgt]65739; 178144.5], hours per week]55.5; +∞[, re-lationship{Husband}, marital status {Married-AF-spouse}, marital status {Married-civ-spouse}, occupation{Craft-repair, Transport-moving}, race-{White}, sex{Male}.

The Khiops tool is available as a shareware at www.khiops.com/.