Jérémie Sublime
email: jeremie.sublime@isep.fr

Basarab Matei
email: matei@lipn.univ-paris13.fr

Guénaël Cabanes
email: guenael.cabanes@lipn.univ-paris13.fr

Nistor Grozavu
email: nistor.grozavu@lipn.univ-paris13.fr

Younès Bennani
email: younes.bennani@lipn.univ-paris13.fr

Antoine Cornuéjols
email: antoine.cornuejols@agroparistech.fr

Entropy based probabilistic collaborative clustering

Keywords:

Unsupervised machine learning approa ches involving several clustering algorithms working together to tackle difficult data sets are a recent area of research with a large number of applications such as clustering of distributed data, multi-expert clustering, multi-scale clustering analysis or multi-view clustering. Most of these frameworks can be regrouped under the umbrella of collaborative clustering, the aim of which is to reveal the common underlying structures found by the different algorithms while analyzing the data.

Within this context, the purpose of this article is to propose a collaborative framework lifting the limitations of many of the previously proposed methods: Our proposed collaborative learning method makes possible for a wide range of clustering algorithms from different families to work together based solely on their clustering solutions, thus lifting previous limitation requiring identical prototypes between the different collaborators. Our proposed framework uses a variational EM as its theoretical basis for the collaboration process and can be applied to any of the previously mentioned collaborative contexts.

In this article, we give the main ideas and theoretical foundations of our method, and we demonstrate its effectiveness in a series of experiments on real data sets as well as data sets from the literature.

like in the real world, such problems can be tackled more easily by having several algorithms working together in order to increase both the quality of the results and their reliability.

Approaches based on this idea of several algorithms working together have been widely studied in the case of supervised learning [START_REF] Schapire | The strength of weak learnability[END_REF][START_REF] Wolpert | Stacked generalization[END_REF][START_REF] Kittler | On combining classifiers[END_REF][START_REF] Bachman | Learning with Pseudo-ensembles[END_REF] where they gave birth to the field of Ensemble Learning.

Ensemble methods are easy to implement in supervised learning for two reasons: First, it is straightforward to define a combination of predictive functions to get an aggregated prediction function (for instance, a linear combination is used in boosting). Second, it is simple to measure both the performance of individual prediction functions and the diversity of the set of the functions that are candidate for being part of the combined global decision function. Things are not so straightforward in unsupervised learning. Here, each individual solution is a soft or hard partition of the data set. How to combine these partitions has no obvious answer.

In cooperative clustering, each clustering algorithm produces its result independently. The final clustering is computed in a post-processing step, and the only exchange of information is about when the individual processes are completed, so that postprocessing can start. In this case, a set of clustering algorithms are used in parallel on a given data set. Once all local computations

ARTICLE IN PRESS

JID: PR [m5G; July 10, 2017;19:28 ] are completed, a master algorithm takes control and combines the local results to get a hopefully better overall clustering. The resolution of the possible conflicts between the local solutions requires an algorithm that is able to compare results that may differ in their format (e.g. different numbers of clusters, different degrees of belief associated with the results, ...) and to find a consensus solution that minimizes the overall violation to the local results. The cooperative framework is closely related to the ensemble methods developed for supervised learning. In these approaches, a set of (diverse) classifiers is learned and the classification of new data points is obtained by taking a (weighted) vote of their predictions.

Bayesian averaging can be considered as a precursor method. Numerous new ones have been developed, from error-correcting output coding to Bagging, and Boosting and their application in various domains have become routine with often good results.

In collaborative clustering (The sequel of this paper), the group solves together problems defined and imposed by the central controller, affecting an individual task to each learner. Interactions are recurrent between team members, responsibility is collective, the action of each teammate is geared to the performance of the group and vice versa. By contrast to the cooperative clustering model, the collaborative model does not seek an overall hopefully better clustering of a given data set through the combination of individual solutions. In the collaborative framework, the goal is that each local computation, quite possibly applied to distinct data sets, benefits from the work done by the other collaborators. This can be done through the exchange of information about the local data, or the current hypothesized local clustering, or the value of one algorithm's parameters. The validity of the approach rests on the assumption that useful information can be shared among the local tasks. This scheme leads naturally to distributed implementations of the computations, but unlike in the cooperative framework, it generally entails several iterations at each local node because convergence of the consensus solution requires several passes of the algorithm. Indeed, in addition to the problem of what information to exchange between collaborators, one question is how to measure the evolution at each node and on a global level.

There are many applications in unsupervised learning for which collaborative clustering can prove useful:

• Multi-scale analysis : In this case several algorithms would be analyzing the same objects, all looking at the same features, but searching for a different number of clusters. That kind of analysis can be beneficial for data sets that have intrinsic multiscale structures such as satellite images for which a lower level analysis of global landscape areas (urban areas, water bodies, forests) often helps to improve a higher level analysis of smaller details (trees, cars, houses, gardens, streets, etc.).

• Multi-expert analysis : In this case, all algorithms would be working on the same objects and features of a difficult data set. Given the very high number of existing clustering algorithms, all more or less specialized and that may or may not give good results depending on the problem, trying several of them on a data set and having them exchanging their information could be justified: merging the informations on clusters found only by some clustering algorithms, refining the results based on clusters that are more or less well identified depending on the method, etc.

• Multi-view clustering [START_REF] Zimek | The blind men and the Elephant: on meeting the problem of multiple truths in data from clustering and pattern mining perspectives[END_REF][START_REF] Kumar | A co-training approach for multi-view spectral clustering[END_REF] : Different algorithms process different types of attributes for the same objects. For example one algorithm for geometric attributes, one for text attributes, one for colors, one for numerical attributes, etc. The goal of the collaboration in this case would be to have each attribute type processed by a specialized algorithm while giving these algorithms a more global picture of the data set by enabling some exchanges between them.

• Clustering of distributed data [START_REF] Depaire | PSO driven collaborative clustering: a clustering algorithm for ubiquitous environments[END_REF] : The same objects have their 102 attributes split on several databases that can't exchange their 103 data because of privacy issues. While the name is different, this 104 is in fact very much equivalent to multi-view clustering.

105

• Big Data Clustering [START_REF] Cai | Multi-view k-means clustering on big data[END_REF] : Data sets that are too large or have too 106 many attributes to be processed efficiently by a single algo-107 rithm may be easier to tackle once their attributes are split and 108 processed by several algorithms. This type of clustering is use-109 ful in the area of Big Data analysis and would require a high 110 degree of cooperation between the algorithms to get the global 111 picture.

112

As one can see, all these applications have a lot of similarities: 113 we have several algorithms working on the same data or subsets of 114 the same data, and that will or could at some point try to aggre-115 gate or to mutually exploit their respective results. While some of 116 these applications could be considered a field of their own such as 117 multi-view clustering or distributed clustering [START_REF] Zimek | The blind men and the Elephant: on meeting the problem of multiple truths in data from clustering and pattern mining perspectives[END_REF] , all of them can 118 be classified as horizontal collaborative clustering frameworks [9-119 12] : several algorithms working on the same data eventually look-120 ing for a different number of clusters, and not necessarily having 121 access to the same features.

122

We generally distinguish between two types of collaborative 123 methods [START_REF] Pedrycz | Interpretation of clusters in the framework of shadowed sets[END_REF][START_REF] Grozavu | Topological collaborative clustering[END_REF] : Vertical collaboration encompasses all cases where 124 several algorithms are working on different data that have similar 125 clusters or distributions. And Horizontal collaboration deals with 126 cases where several algorithms are collaborating on the same ob-127 jects, eventually described from different views. In this article, we 128 are mostly interested in horizontal collaboration. These two steps are sometimes followed by an aggregation step 136 which aims at reaching a consensus with the final results after col-137 laboration. In this work we will not address the aggregation step 138 because it is a field of its own, and that depending on the appli-139 cation it may not always be advisable to aggregate, for instance 140 when the different views, sites or scales have conflicting partitions 141 [START_REF] Zhang | Knowledge discovery in multiple databases, Advanced Information and Knowledge Processing[END_REF] . We will instead focus on the collaborative step where the al-142 gorithms exchange bits of information with a goal of mutual im-143 provement.

144

From there, the main difference between what is traditionally 145 referred as "clustering ensemble learning " [START_REF] Vega-Pons | A survey of clustering ensemble algorithms[END_REF] and collaborative 146 clustering is that clustering ensemble learning methods aim at 147 finding a single consensus partition, while collaborative cluster-148 ing does not have this final goal. In short, the field of collabora-149 tive clustering is concerned with finding algorithms and functions 150 that allow algorithms to share information and to improve their re-151 sults based on each other similarities, while the field of ensemble 152 learning is more concerned with finding algorithms and methods 153 to merge the solutions or find a consensus between them. Collabo-154 rative clustering can therefore be a task of its own (e.g. multi-view 155 clustering where consensus is not always possible nor advisable), 156 or a preliminary step to an ensemble learning task. The methods 157 and techniques used by both fields are therefore naturally overlap-158 ping, and a good collaborative algorithm must respect properties 159 that are very similar to these of a good ensemble learning method: 160 • Novelty: Collaborative clustering must make it possible to find solutions that would have been otherwise unattainable locally. The remainder of this article is organized as follows:

In Section 2 , we propose a state of the art in which we introduce some of the pioneer and earlier proposed methods and frameworks for collaborative learning with their strengths and weaknesses.

In Section 3 , we introduce our proposed method for horizontal collaborative clustering. As stated previously, the method that we propose aims at being more generic than the previously proposed frameworks. We begin by explaining the principle of our method and its theoretical basis. Then we study the stopping criterion and parameters tuning of our algorithm. And finally, we demonstrate that our proposed method has good convergence properties similar to these of a EM algorithm.

In Section 4 , we show some experimental results. We are mostly interested in showing some potential applications of our proposed method applied to multi-scale clustering and multi-view clustering.

Finally, this work ends with a conclusion and perspectives on future works.

State of the art in collaborative clustering

One of the first collaborative clustering algorithm was introduced in 2002 by Pedrycz [START_REF] Pedrycz | Collaborative fuzzy clustering[END_REF][START_REF] Pedrycz | Fuzzy clustering with a knowledge-based guidance[END_REF] under the name "Collaborative Fuzzy Clustering " (CoFC). This method was designed for the specific case of distributed data where the information cannot be shared between the different sites. This method was based on a modified version of the Fuzzy C-Means algorithm [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF] .

The main limitation of this approach is that it only enables Fuzzy C-Means algorithms to collaborate together, and furthermore some methods even require that all of them be looking for the same number of clusters.

Similar approaches were used to develop several other collaborative-like methods CoEM [START_REF] Bickel | Estimation of mixture models using co-em[END_REF] , CoFKM , [START_REF] Cleuziou | Cofkm: a centralized method for multiple-view clustering[END_REF] , and another collaborative EM-like algorithm [START_REF] Hu | Maximum likelihood combination of multiple clusterings[END_REF] based on Markov Random Fields.

All these algorithms display similar limitations: the objective functions and sometimes the number of clusters must be identical for all exchanged information. This is due to the fact that they all try to optimize an objective function the form of which is:

227

( S opt , opt ) = Argmax ( S , ) L g ( S , ) = Argmax ( S , ) J i =1 L (X i | S i , i ) - j = i τ j,i • ( i , j ) (1)
where J is the number of collaborators, S contains all algorithm's 228 partitions, their distributions parameters, L g ( S , ) is the global 229 likelihood of the system, each L ( X i | S i , i ) is the local log-likelihood 230 of a collaborating algorithm, each ( i , j ) the "collaborative 231 term " is a custom pairwise penalty that compares the difference 232 between the parameters or prototypes of two algorithms, and the 233 τ j , i which do not exist in all methods are weights given to the 234 collaborative penalties. The definition of the local term L ( X i | S i , 235 i ) based on which algorithms collaborate together makes the 236 main difference between all these methods, while definition of the 237 penalty ( i , j ) only slightly differs depending on the collabora-238 tive method. This later parameter is the limiting one since compar-239 ing prototypes and parameters requires that the algorithms have 240 the same types of prototypes and some kind of mapping between 241 the clusters of the different algorithms.

242

The work of Pedrycz on the CoFC algorithm was also extended 243 to be adapted to the Self-Organizing Maps (SOM) [START_REF] Grozavu | Topological collaborative clustering[END_REF][START_REF] Grozavu | Collaborative Unsupervised Learning and Cluster Characterization[END_REF][START_REF] Grozavu | Topological collaborative clustering[END_REF] and to 244 the Generative Topographic Maps (GTM) [START_REF] Ghassany | Collaborative clustering using prototype-1156 based techniques[END_REF] .

245

In [START_REF] Grozavu | Topological collaborative clustering[END_REF] , the classical SOM objective function is modified by 246 adding a specific extra term for horizontal collaboration and a dif-247 ferent one for vertical collaboration. For the collaborative version 248 of the GTM algorithm [START_REF] Ghassany | Collaborative clustering using prototype-1156 based techniques[END_REF] , the principle is the same with the M-249

Step of the EM algorithm mapping the neurons to the final clusters 250 being modified.

251

One problem with these two methods is that they do not re-252 ally solve the main issue of collaboration between different types 253 of algorithms since their model in once again analog to the one in 254 Eq. [START_REF] Schapire | The strength of weak learnability[END_REF] . Furthermore, while the number of clusters does not mat-255 ter in the case of the collaborative SOM and collaborative GTM, in 256 both cases the maps must have the same number of neurons and 257 be topologically similar to each other. This is actually even more 258 restraining than a requirement on the number of clusters.

259

The SAMARAH method [START_REF] Wemmert | Classification Hybride Distribuée Par Collaboration De Methodes 1158 Non Supervisées[END_REF][START_REF] Forestier | Collaborative multi-strategical classi-1160 fication for object-oriented image analysis[END_REF] is another type of collaborative 260 framework the strength of which is that it can deal with any kind 261 of hard clustering algorithm and is not concerned with issues such 262 as fitness functions, number of clusters, or prototypes. Unlike the 263 previously introduced method, SAMARAH only handles horizon-264 tal collaboration due to the lack of prototypes, and was designed 265 mostly for clustering applied to image data. Its goal is very simple: 266 given J clustering results for the same data, the idea is to modify 267 these results in an iterative and collaborative way with the aim of 268 reducing their diversity in order to make the finding of a consen-269 sus solution easier. 270 Once the results have been generated during the local step, the 271 SAMARAH method maps the clusters of the different algorithms 272 using probabilistic confusion matrices (PCM). Let S i and S j be two 273 clustering results from two algorithms A i and A j looking for K i and 274 K j clusters respectively. 275 Then, the probabilistic confusion matrix (PCM) i , j that maps 276 the clusters from A i to A j is defined as shown bel ow:

277 i, j = ⎛ ⎜ ⎝ ω i, j 1 , 1 • • • ω i, j 1 ,K j . . . . . . . . . ω i, j K i , 1 • • • ω i, j K i ,K j ⎞ ⎟ ⎠ where ω i, j a,b = | S i a ∩ S j b | | S i a | (2)
In Eq. ( 2) , S i a denotes the a th cluster of algorithm vantages of both prototype-based collaborative methods and the SAMARAH method, without their issues.

A i i.e., S i a = 278 { x ; x ∈ X i , x ∈ a by A i } and | S i a | is
Our goal in this section is to find a way to modify Eq. ( 1) so that the collaborative term will not depend on the prototypes. Therefore, we propose a likelihood function based on Eq. ( 3) which uses a global consensus term C ( S ) based on the partitions. The main differences with Eq. ( 1) are that we used a model based on partitions rather than prototypes, our proposed model is consensus based instead of divergence based, and we use a global term instead of a pairwise one. We chose this global model because unlike the pairwise version, it does not require to assume that the algorithms are independent from each other (which is of course not true).

In this model, λ ∈ [0, 1] is a weight parameter to balance between the local and collaborative term. The left term

J i =1 L (X i | S i , i ) is called the local term , and the right term λ • C ( S )
is the collaborative term. Note that the C ( • ) here stands for "consensus": we have a collaborative term based on a consensus function.

( S opt , opt ) = Argmax ( S , ) L g ( S , ) = Argmax ( S , ) J i =1 L (X i | S i , i ) + λ • C( S ) (3)
With this model, and using a collaborative term based on different a posteriori distributions instead of a collaborative term based on distributions parameters, our proposed model lifts off the limitation that only identical algorithms looking for the same number of clusters can work together. Furthermore, using our model even non-parametric algorithms -for which the distributions parameter i can not be explicitly formulated-can be used in a collaborative setting since our model is based on the partitions (solution matrices or vectors) which are explicit for any clustering algorithm.

The penalty factor λ > 0 regularizes the collaboration part. Please note that in [START_REF] Dasgupta | Pac generalization bounds for co-1166 training[END_REF] , the authors have demonstrated that there is a direct relation between reducing the divergences and maximizing the consensus under mild assumptions. Therefore, both strategies are equivalent.

Analogously to Eq. ( 3) , our idea is to optimize a modified fitness of the log-likelihood function that considers both the local partitions and the information coming from the other algorithms' solutions. By considering only the partitions S i and not the parameters, very much like in the SAMARAH method [START_REF] Wemmert | Classification Hybride Distribuée Par Collaboration De Methodes 1158 Non Supervisées[END_REF][START_REF] Forestier | Collaborative multi-strategical classi-1160 fication for object-oriented image analysis[END_REF] , we ensure that our model is both generic.

As we will demonstrate in the next subsection, this change from i to S i is made possible because we use an alternate maximization procedure in which the partitions are computed from the prototypes and then the prototypes are updated based on the partitions and the data. In short, the partitions can be seen as a discretization of the distributions described by the prototypes.

While this improvement will result in a more generic paradigm when it comes to horizontal collaboration, it is worth mentioning that removing the prototypes also makes vertical collaboration (algorithms collaborating on different data sets with similar clusters) impossible whereas some of the earlier methods covered this case of knowledge transfer between similar data sets [START_REF] Grozavu | Topological collaborative clustering[END_REF][START_REF] Pedrycz | Collaborative fuzzy clustering[END_REF][START_REF] Ghassany | Collaborative clustering using prototype-1156 based techniques[END_REF] , albeit only between identical algorithms.

To optimize (3) we use the Expectation Maximization ( EM ) strategy. The workflow in Algorithm (1) highlights how our algorithm can indeed be considered as an EM algorithm. During the E-Step, the partitions S are updated using fixed values for the distributions parameters . Then, during the M-Step, these parameters are updated based on the new partitions.

The exact form of the functional L g is explained in the next section, while the sopping criterion is detailed in Section 3.5 .

Please cite this article as: J.

i X i = { x i 1 , . . . , x i N } , x i n ∈ R d
The subset of the data observed by algorithm

A i X X = { X 1 , . . . , X J }
The full data with all views i The parameters describing the distributions observed by algorithm

A i = { 1 , . . . , J }

The set of distributions parameters for all algorithms

A i A i = { X i , S i , i , K i }
An algorithm looking for K i clusters of distribution parameters i in the subset X i and finding a partition S i

τ j , i τ j , i ∈ [0, 1]
The weight of the collaboration from

A j to A i s i n,c s i n,c ∈ (0 , 1) , K i c=1 s i n,c = 1
The responsibility given by algorithm

A i to the cluster c ∈ [1.. K i ] for the data x i n S i S i = (s i n,c ) K i ×K i
The partition found by algorithm A i . For fuzzy clusters, S i is a matrix.

Z i Z i : → [1.. K i ]
The latent random vector linked to the solutions of algorithm

A i P ( Z i | X i , i )
the a posteriori distribution of Z i conditionnally to X i and i H See Eq. ( 16)

The global entropy of the collaborative system for all algorithms

ω i, j a,b ω i, j a,b = P(Z j n = b| Z i n = a, S , X , )
The percentage of data associated to cluster a by A i that belong in the cluster b of

A j q q = { q 1 , • • • , q J } , ∀ i q i ∈ [1 ..K i ]
A combination of clusters (see Section 3.4 )

g i ( q , c ) g i ( q , c ) ∈ (0, 1), c ∈ [1.. K i ]
A consensus function assessing the likelihood of having q i = c knowing the rest of q Algorithm 1: Collaborative "EM ".

Initialize, t = 0 and (0) with the local step while the global entropy H decreases do

E-Step: S (t) = Argmax S L g ( S , (t)) , M-Step: ( t + 1 ) = Argmax L g ( S (t) , ) , t = t + 1 end
Return S (t)

Objective function

The fundamental question in horizontal collaborative setting is to find the right functional to optimize so that we can properly answer the problem of having several algorithms working together by exchanging their information with a goal of mutual improvement.

To do so, we have the following constraints: We want a functional similar to Eq. ( 3) based on the partitions instead of distributions prototypes, where we attempt to bias each local solution S i t so that S i t+1 takes into account the information from the other partitions without using any prototypes. The problem therefore consists in finding the right local and collaborative terms.

Defining the local term is relatively easy and can be done using any kind of likelihood function for probabilistic algorithms, and ad-hoc normalized quality criterion for other types of algorithms.

The literature is also full of potential divergence and consensus functions between partitions for the collaborative term that measure the divergence or consensus between two partitions (NMI, entropies, Rand Index, etc.). However, if we add the extra-constraint that the partitions are mostly non-binary and that Eq. ( 3) should be optimized in a reasonable amount of time, we face the following problem: For vector partitions of size N , most of these operators have a complexity in O ( N 2 ). Therefore, the final cost of updating all partitions for the J algorithms looking on average for K clusters would be equivalent to call these operators J × N × K times, hence a final complexity of O ( N 3 ) just to optimize the collaborative term.

Since such complexity obviously does not scale well, in the remainder of this section we explain how we re-designed a likelihood function from scratch using a solid probabilistic model. Then, in Section 3. More precisely the global likelihood function writes:

L g ( S , ) = L ( S , ) + λ • C( S ) , ( 4
)
where X is the observed variable, the set of parameters and S = 434 (S 1 , . . . , S J ) is the set of all partitions.

435

In the first term L in Eq. ( 4) , just as in Eq. ( 3) , we express the 436 log-likelihood of S based only on the local information and model 437 of each algorithm taken individually and the data x n . We evaluate 438 then the log-likelihood of the completed sample against the a pos-439

teriori distribution of (Z i | X i n , i ) . 440 L ( S , ) = J i =1 N n =1 P (Z i n | X i n , i ) • log P (X i n , Z i n | i ) .
(

) 5
The second term of Eq. ( 4) is detailed in Eq. ( 6) . It is computed 441 from the likelihood that each element x n be linked to the right 442 cluster based on the other algorithms' partitions and the choice 443 of cluster for the same data in the local view. The difference be-4 4 4 tween the local likelihood and the likelihood based on the other 445 algorithms gives us the collaborative term. This term C ( S ) therefore 446 is the likelihood of S based on all the solutions. 447

C( S ) = J i =1 N n =1 P (Z i n | X n \ X i n , S ) -P (Z i n | X i n , i ) • log P (X i n , Z i n | i ) (6)
Then using Eqs. ( 5) and ( 6) we obtain following a posteriori 448 probability for the completed sample X i n , Z i n corresponding to al-449 gorithm A i : 450

P (Z i n = c| X i n , i , S ) = (1 -λ) • P (Z i n = c| X i n , i ) + λ • P (Z i n = c| X n \ X i n , S ) (7)
Note that due to the lack of independence

P (Z i | X n \ X i n , S ) is not 451
tractable. Nevertheless, in the next section we show tractable up-452 date rules for the responsibilities. In this section, we will proceed with the practical description 455 of the update rules for the responsibilities s i n,c so that we can ac-456 tually compute the partitions that are solutions of the functional 457 from Eq. [START_REF] Depaire | PSO driven collaborative clustering: a clustering algorithm for ubiquitous environments[END_REF] . For fuzzy clustering we then infer that the update 458 rule for the responsibility for all data x n and all cluster c from iter-459 ation t to iteration t + 1 during the E -step of Algorithm (1 ) is the 460 following:

461 s i n,c (t + 1) = (1 -λ) • s i n,c (t) + λ • q ∈ Q| q i = c P ( q | X n \ X i n , t \ i (t)) • P (Z i n = q i | q ) (8)
Please cite this article as: J. The first term s i n,c | t comes from the local partition, and is actually given by the a posteriori probability P (Z i n = c| x i n , i (t)) for the data

x n by using the Bayes rule.

The second term is a key element in this paper: we have J algorithm running parallel, and each of these algorithm can assign the data x n to any cluster in [1..

K i ]. Let q = { q 1 , • • • , q J } , ∀ i q i ∈ [1 ..K i ]
, q ∈ Q be one combination of cluster chosen by the J algorithms among all possible sets of combinations Q . Based on these notations, the collaborative term assess the likelihood of such combination q for the data x n based on all algorithms except the local algorithm A i , hence the notations X n \ X i n and t ࢨ i ( t ). Then the collaborative term asses the probability of having q i = c knowing the rest of the combination q . Since we are considering the case of fuzzy clustering, all possibles combinations in Q must be evaluated, hence the sum.

To sum up, the second term sums all possibles combinations of clusters q ∈ Q where q i = c, then assess the probability of such combination for the data x n for the other algorithms. This probability is then multiplied by the probability of q i = c knowing the other elements of the combination q . We will approach this second probability using a consensus function g i ( q , c) ≈ P (q i = c| q ) .

Since Q the set of all possible combination grows exponentially large with the number of algorithms, and because most of the combination probabilities are very close to 0, we make the simplification of only considering the most likely combination q * n =

Argmax q P ( q | X n \ X i n , t \ i t ) .
Therefore the update rule (8) becomes:

s i n,c (t + 1) = (1 -λ) • s i n,c (t) + λ • g i ( q * n , c) (9)
where we remind that λ is a weight parameter between local and external information.

As one can see from Eq. ( 9) , the discretization of our model

Combination functions

In this Section we give some example of a particular class of "combination functions " that are tractable and can be used in our collaborative framework.

First, we want to begin by explaining the intuitive meaning of g i as a consensus function: Given a partitioning problem processed in parallel by several algorithms (or a vote process in which several algorithms take part), g i ( q , c ) assesses the consensus or degree of compatibility of a cluster c from the algorithm A i with the group

of clusters q = { c 1 , • • • , c j , • • • , c J } , j = i from the other algorithms. Definition 1. A function g i : Q × [1 ..K i ] → [0 , 1] is a combination
function for the algorithm i if it satisfies:

1. g i ( q , c ) needs to increase strictly between 0 and 1 when the consensus between the different algorithms grows on the likelihood of having q i = c for a given combination q .

2. g i ( q , c ) needs to be normalized so that for any cluster combination q that occurs at least once, we have:

c∈ [1 ..K i ] g i ( q , c) = 1 .
3. When the algorithms have the exact same partitions and c = argmax q i s i n,q i , then:

g i ( q * n , c) = 1 .
Note that the properties of the combination function are nat-524 urally satisfied by any marginal of a probability density function 525 defined on latent space.

526

To be more precise on the computation and increasing property 527 of g , let i be a fixed algorithm, be c a fixed cluster and q be a fixed 528 cluster combination such that q i = c. The value g i ( q , c ) is computed 529 by considering S the set of all partitions, in the following way: we 530 compute the likelihood of q i = c with respect to all others choices 531 q j , j = i for the cluster c and a given partition S ∈ S . This likelihood 532 is computed directly from the cardinality of the intersections of 533 all involved clusters. We propose thereafter 3 possible combination 534 functions abiding by the axioms exposed before. All have different 535 strengths and weaknesses. They are shown in Eqs. ( 10) - [START_REF] Sublime | Collaborative clustering with heterogeneous algorithms[END_REF] .

536 g i ∩ ( q , c) = | j = i q i ∩ q j | | j = i q j | , q i = c ( 10
)
The formula from Eq. ( 10) assesses consensus between the local 537 algorithm and the other algorithms divided by the consensus be-538 tween the other algorithms. This combination function is the one 539 that should be picked in absence of the independence hypothe-540 sis between the different algorithms. This combination function is 541 normalized, However it is costly to compute due to the K J possible 542 intersections. It is also worthy to mention that this combination 543 function does not allow to weight the influence of the different al-544 gorithms.

545

g i + ( q , c) = 1 B j = i τ j,i | q i ∩ q j | | q j | = 1 B j = i τ j,i • ω j,i q j ,q i , q i = c (11)
In Eq. ( 11) , making the hypothesis that all algorithms are in-546 dependent, we compute the mean pairwise consensus between 547 the partitions, and in [START_REF] Sublime | Collaborative clustering with heterogeneous algorithms[END_REF] the geometric mean consensus. In both 548 Equations, the τ j , i are weights that can be set to different val-549 ues in order to change the influence of the algorithms on each 550 other, and B is a normalization constant that is needed to respect 551 axiom 2. Both equations are based on the same PCM Matrices 552 j,i = (ω j,i q j ,q i ) (K j ×K i ) from the SAMARAH method described in Eq. 553 [START_REF] Wolpert | Stacked generalization[END_REF] and which are relatively cheap to compute. Beyond the fact 554 that both combination functions require a normalization, g * also 555 has the issue that it always returns 0 whenever one of the inter-556 section is null.

557

g i * ( q , c) = 1 B j = i | q i ∩ q j | | q j | τ j,i = 1 B j = i ω j,i q j ,q i τ j,i , q i = c ( 12
)
Given that all 3 combinations functions have their pros and 558 cons, picking one is context dependent. For instance, g i ∩ certainly 559 is the most interesting one to have a global consensus combination 560 function, but should be avoided with a large number of collabora-561 tors due to its complexity and is unpractical when weighting the 562 collaborators is a requirement. Then g i * has a behavior that is very 563 close from g i ∩ with less computational complexity. Another advan-564 tage of g i * is that it has a Bayesian interpretation if we assume the 565 hypothesis that all partitions are independent. On the other hand 566 g i + behaves a bit differently but it will not tend as fast towards zero 567 when one or more intersections are null. Furthermore, both g i + and 568 g i * scale better with a large number of collaborators. Further dis-569 cussions on the complexity of these functions are available in sec-570 tion 3.5, and some experimental results are shown in Section 4.1 .

571 Finally, as one can see, the 3 combination functions are in prac-572 tice based solely on the local clustering partitions and can be used 573 regardless of the type of algorithm and the number of clusters it 574 is searching for. This property is fundamental in the sense that it 575 lifts off the previous limitations of collaborative frameworks allow-576 ing only algorithms of the same kind to work together and forcing 577 them to search for the same number of clusters. Using these parti-578 Please cite this article as: J.

cpx = J × cpx (A (N, K )) + N × cpx (g) ( 13
)
where cpx (A (N, K )) is the average complexity of the collaborators 586 and cpx ( g ) is the complexity of the chosen combination function. 597

cpx min = J × cpx (A (N, K )) + O (J × N) (14)
Otherwise, we have:

598 cpx max = J × cpx (A (N, K )) + O (J 2 N 2 ) ( 15
)
To conclude on the complexity of our proposed method: In the 599 less favorable scenario using g ∩ without the independence hypoth-600 esis, or using a suboptimal version of g + or g * , the collaboration 601 adds complexity term in O ( J 2 N 2 ). This term is therefore only neg-602 ligible when using algorithms the complexity of which is superior The stopping criterion used by our algorithm is the probabilistic 613 confusion entropy [START_REF] Wang | Probabilistic confusion en-1168 tropy for evaluating classifiers[END_REF][START_REF] Wei | A novel measure for evaluating 1170 classifiers[END_REF] as shown in Eq. ( 16) bellow:

614

H = J i =1 J j = i -1 K i × log (K j ) K i l=1 K j m =1 ω i, j l,m log (ω i, j l,m ) (16)
This entropy assess the pairwise divergences between the algo-615 rithms, and is equal to 0 when all algorithms have identical parti-616 tions, and 1 when there is a full disagreement. In short, H is the 617 system global entropy under the conditions that all algorithms are 618 independent. We chose to use this entropy because it uses the ω i, j l,m 619 from the probabilistic confusion matrix in Eq. ( 2) that we already 620 compute for two of our combination functions g . As such, the en-621 tropy H is much less costly to compute than any other divergence 622 or consensus measure in the literature.

623

The justification that this entropy is a good stopping criterion 624 is the following: from Eq. ( 6) , we know that the collaboration of 625 algorithm A i with all the others collaborators can be measured by 626 the difference between the cross entropy of the two distributions 627 P ( Z i | X ࢨX i , S ) and P ( Z i | X i , i ), and the entropy of the distribution 628 P ( Z i | X i , i ). Therefore, the collaborative term is oppositely propor-629 tional to the system global entropy H. From there, since we use 630 an EM-like optimization process the form of which is a local term 631 minus a difference of two entropies , we know from the proof of the variational EM [START_REF] Neal | A view of the EM algorithm that justifies incremental, 1172 sparse, and other variants[END_REF] that both involved entropies increase strictly, and therefore that their difference decreases. As such, the global entropy H is a is a valid stopping criterion. Furthermore, this type of entropic criterion is consistent with earlier studies that have shown the importance of diversity and entropy in collaborative clustering [START_REF] Azimi | Adaptive cluster ensemble selection[END_REF][START_REF] Grozavu | Diversity analysis in collaborative cluster-1177 ing[END_REF][START_REF] Zarinbal | Relative entropy collaborative fuzzy clus-1180 tering method[END_REF] .

Setting the weights parameters

We now want to discuss the role of the weighting parameter τ j , i . These parameters weight the strength of the collaborative link from an algorithm A j to an algorithm A i , and ultimately they determine the value of the parameter λ i used as a weig ht between the local and the collaborative term.

There are several techniques to set up these weights:

• Arbitrarily setting the same value for all weights. While this is not the best method to avoid negative collaboration, it is certainly the lest computationally expensive one and it is widely used in the literature [START_REF] Pedrycz | Collaborative fuzzy clustering[END_REF][START_REF] Bickel | Estimation of mixture models using co-em[END_REF][START_REF] Cleuziou | Cofkm: a centralized method for multiple-view clustering[END_REF] . It is this method that we used in this paper.

• Using expert knowledge to set them up, for instance using quality and diversity criterion between the solutions [START_REF] Rastin | Collaborative clustering: how to 1183 select the optimal collaborators?[END_REF] . This method can prove useful when expert knowledge is available or specific shapes are expected for the clusters, but it is biased towards certain types of algorithms.

• Searching the weights that optimize the collaborative term when the partitions and parameters are fixed [START_REF] Ghassany | Collaborative clustering using prototype-1156 based techniques[END_REF] . This method is very effective at reducing the risks of negative collaborations because it tends to favor the most stable solutions. However, it is also known to favor collaborations between already similar partitions, which also tend to reduce the overall performances.

Experimental results

Our experimentation will be separated in 4 distinct parts: in the first part we will demonstrate a practical calculation of the 3 combinations functions g using an artificial data set with the goal of showing how the calculus is done in practice and also to demonstrate that all functions have a similar behavior. In the second part, a second experiment is proposed, in which we show the performances of our proposed method in term of collaborative power. In the third part, we show two comparative experiments: First, comparison of our method with other state of this art collaborative and multi-view frameworks. And second, we propose an application of our method for the multi-scale analysis of image data in which we compare it with non-collaborative algorithms. Finally in part 4, we show the average computation times of our methods under various parameters.

Offer settings that the other methods do not.

Example of empirical calculi with the combination functions

Let us consider an artificial data set X containing 81 observations. We suppose that 3 algorithms are working on a multi-view analysis of this data set, each of them searching for 2 clusters. In Fig. 1 , we show the partitions found by each algorithm in a 2dimension projection that is very convenient to visualize the problem.

The first algorithm (in red on the figure) is searching for two clusters { a , a }, the second algorithm (in blue) is searching for the clusters { b , b } and the third (in green) for { c , c }. Due to the multi-view nature of this experiment, we can see that they find very dissimilar partitions.

Please cite this article as: J.

Table 2

Example of results for different combination functions.

g red ∩ ( q , a ) = | a ∩ b ∩ c | | b ∩ c | = 2 10 = 0 . 2 g red ∩ ( q , a ) = | a ∩ b ∩ c | | b ∩ c | = 8 10 = 0 . 8 g red + ( q , a ) = 1 B | a ∩ b | | b | + | a ∩ c | | c | = 1 Z 20 36 + 7 35 ≈ 0 . 38 g red + ( q , a ) = 1 B | a ∩ b | | b | + | a ∩ c | | c | = 1 Z 16 36 + 28 35 ≈ 0 . 62 g red * ( q , a ) = 1 B | a ∩ b | | b | × | a ∩ c | | c | = 1 Z 20 36 × 7 35 ≈ 0 . 24 g red * ( q , a ) = 1 B | a ∩ b | | b | × | a ∩ c | | c | = 1 Z 16 36 × 28 35 ≈ 0 . 76

Table 3

Example of results for different combination functions. Example of results for different combination functions.

g blue ∩ ( q , b ) = | a ∩ b ∩ c | | a ∩ c | = 5 7 = 0 . 71 g blue ∩ ( q , b ) = | a ∩ b ∩ c | | a ∩ c | = 2 7 = 0 . 29 g blue + ( q , b ) = 1 B | a ∩ b | | a | + | b ∩ c | | c | = 1 B 25 45 + 25 35 ≈ 0 . 63 g blue + ( q , b ) = 1 B | a ∩ b | | a | + | b ∩ c | | c | = 1 B 20 45 + 10 35 ≈ 0 . 37 g blue * ( q , b ) = 1 B | a ∩ b | | a | × | b ∩ c | | c | = 1 B 25 45 × 25 35 ≈ 0 . 76 g blue * ( q , b ) = 1 B | a ∩ b | | a | × | b ∩ c | | c | = 1
g green ∩ ( q , c ) = | a ∩ b ∩ c | | a ∩ b | = 2 20 = 0 . 1 g green ∩ ( q , c ) = | a ∩ b ∩ c | | a ∩ b | = 18 20 = 0 . 9 g green + ( q , c ) = 1 Z | a ∩ c | | a | + | b ∩ c | | b | = 1 Z 7 45 + 10 36 ≈ 0 . 22 g green + ( q , c ) = 1 Z | a ∩ c | | a | + | b ∩ c | | b | = 1 Z 38 45 + 26 36 ≈ 0 . 78 g green * ( q , c ) = 1 Z | a ∩ c | | a | × | b ∩ c | | b | = 1 Z 7 45 × 10 36 ≈ 0 . 07 g green * ( q , c ) = 1 Z | a ∩ c | | a | × | b ∩ c | | b | = 1 Z 38 45 × 26 36 ≈ 0 . 93
• We have an empirical confirmation that g i * is a very good approximation of g i ∩ , while g i + leads to more flexible results.

What we can observe from this experiment is that the combinations functions that we have proposed serve their intended purpose and encourage changing the partitions in a way that will lower the diversity between the algorithms' solutions. According to Tables 234, the data x n should be moved to cluster a , b and c in order to increase the consensus.

However, one should keep in mind that these changes may only happen if the collaborative term is strong enough compared with the local term which we do not mention in this experiment.

In the light of this first experiment that complete the study on the complexity of our algorithm performed in Section 3.5 , we think that the function g i ∩ should be favored when the data set is small enough to do the computations in a reasonable amount of time, and that otherwise g i * should be favored over g i + because it is the best approximation.

Multi-view collaborative clustering experiments 4.2.1. Experimental setting

In this experiment, we propose to evaluate our framework for collaborative multi-view clustering task. To this end, our experimental setting is the following: We considered the VHR Strasbourg (9 clusters), the Images (7 clusters), the WDBC (2 clusters) and the Spam Base (2 clusters) data sets in a multi-view setting where their attributes were split between different algorithms.

In the list bellow we explain how we created our views by splitting the data sets depending on their attributes.

• For WDBC: one view with only cell 1 (attributes 1 -10), one view with only cell 2 (attributes 11 -20), one view with only cell 3 (attributes 21 -30), three views combining theses (cells 1 and 2, 1 and 3, 2 and 3). All 6 mentioned combinations using only appearance attributes only (texture, smoothness, compactness, fractal dimension), or only geometric attributes only (radius, perimeter, area, concavity, concave points, symmetry).

• For Image Segmentation: Region based attributes (attributes 1 -9), local attributes (attributes 10 -19), region-based + red attributes (attributes 1 -9, 11 and 14), region-based + green attributes (attributes 1 -9, 13 and 16), region-based + blue attributes (attributes 1 -9, 12 and 15), raw attributes only (attributes 1 -5, 11, 12 and 13), post-processed attributes only (6 -10 and 14 -19).

• For Spam Base: Any random combination of 19 attributes among the 57 total attributes was considered a view.

• For VHR Strasbourg: Geometric attributes only, radiometric attributes only, comparison with neighboring segments only, color attributes only (redundant with radiometric and comparison attributes), saturation and texture attributes only (also redundant with radiometric and comparison attributes).

We invite you to see appendix A for details on the data sets.

Given this setting, each view was first processed individually by a clustering algorithm (local step), and then they were all pro-Please cite this article as: J. cessed using our proposed collaborative method. To assess the efficiency of our method, we measured the results of 2 internal index and 1 external index before and after the collaborative step so that we could see whether or not the collaboration was beneficial. The indexes used are the Davies -Bouldin index [START_REF] Davies | A cluster separation measure[END_REF] and the Silhouette index [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF] for the internal indexes and the Adjusted Rand Index [START_REF] Hubert | Comparing partitions[END_REF][START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF] for the external index.

We justify the use of two internal indexes because they do not assess the same things: The Silhouette Index assesses whether or not each data is on average closer to the data from its own cluster than from the data of the other clusters, while the Davies-Bouldin index is a more direct measure of the compactness of the clusters around their centroids and whether or not they are well separated.

This experiment was conducted with all collaborators having the same collaboration weights (

λ = 1 -1 J ).
The algorithms used in the collaboration process were a mix of Fuzzy C-Means algorithms, EM algorithms for the Gaussian Mixture Model, plus the GTM algorithm [START_REF] Bishop | GTM: the generative topographic 1194 mapping[END_REF] for Spam Base, and the SR-ICM algorithm [START_REF] Sublime | Semantic 1196 rich ICM algorithm for VHR satellite image segmentation[END_REF] for the VHR Strasbourg data set. These algorithms were chosen for several reasons:

• They have a random initialization which makes them nondeterministic and therefore interesting both from a collaboration point of view, and also to run a larger number of simulations without using always the same solutions.

• They all have a solid convergence proof and will not hinder the convergence of the collaborative process.

• Even if they don't use the same prototypes and cannot exchange directly on a prototype level, the fact that they are all prototype based makes it possible to use them directly in our collaborative framework without having to adapt them first.

• In the case of the SR-ICM algorithm, it is one of the few available algorithm specialized in pre-segmented high resolution satellite images.

Results

In Table 5 , we show the change in the internal indexes before and after collaborations. For readability purposes, the sign of all variations for the Davies-Bouldin index have been inversed so that all positive values mean improvement for both indexes. The results for the change in the Adjusted Rand Index are shown in Table 6 . In both tables, we indicate how many simulations were done, and the number collaborators is displayed in the "Simulations " columns.

For all indexes, we indicate the average improvement and its standard deviation, as well as the range of change in the considered indexes in the "Min/Max " column where we show the best improvement and worst deterioration achieved over all simulations.

The first striking result from Table 5 is that the gain for the internal quality indexes (Silhouette and Davies -Bouldin) has a lot of

μ = 2% σ ≈ 0 +3% -2% Imgseg 100 × 7 μ = -2% σ ≈ 0 +5% -2% Spam Base 100 × 5 μ = 10% σ = 6% +22% -4% Battalia3 100 × 3 μ = 6% σ = 1% +9% -2% MV2 100 × 4 μ = -3% σ ≈ 0 +2% -6% VHR Strasbourg 35 × 5 μ = -8% σ = 5% +6% -20%
variations. The explanation lies in the fact that while our proposed 806 framework aims at improving all the results, in practice the best 807 collaborators' results are often negatively impacted by weaker al-808 gorithms. Nevertheless, we can see that the collaboration results 809 for the Silhouette and Davies -Bouldin indexes remain positive on 810 average, which tends to prove the robustness of our proposed col-811 laborative Framework.

812

The second point highlighted by this experiment and that is 813 very obvious in Table 6 is that our proposed collaborative frame-814 work does not solve the issue of achieving good results on external 815 indexes (the Adjusted Rand Index here) with purely unsupervised 816 clustering algorithms. The weaker performances achieved on the 817 Adjusted rand index can be explained by two factors: 818 First, without external knowledge, there is no reason for the 819 collaborative process to converge toward the ground truth. The 820 idea of adding external knowledge into our collaborative process 821 may be considered in our future works. Second, in the case of the 822 VHR Strasbourg data set, the ground expert truth contains 15 clus-823 ters covering only 90% of the data set, several of them very un-824 likely to be found by a clustering algorithm. As a consequence, the 825 collaborative process only worsened the situations where the clus-826 tering algorithms found only a reduced number of clusters, there-827 fore boosting indexes such as the Davies -Bouldin index -which is 828 very high for this data set-while severely worsening the results on 829 the Adjusted Rand Index. laborative SOM algorithm [START_REF] Nistor Grozavu | From variable weighting to cluster characterization in 1199 topographic unsupervised learning[END_REF] and the collaborative GTM algorithm [START_REF] Ghassany | Collaborative clustering using prototype-1156 based techniques[END_REF] .

All methods are used in a setting similar to the previous paragraph: the data sets are split in several views and each collaborative model is applied to all the views. Then, in Table 7 , we show the averable results achieved after collaboration for the Rand Index (Rand) and the Davies -Bouldin Index (DB). We remind that the Rand index is better when it is close to 1, and that the Davies -Bouldin index is not normalized and better when smaller.

As one can see, when comparing our proposed method with the Multi-view EM we can see that our method achieves better results. This is interesting because the only difference between our method and theirs is that the MV-EM is based on prototypes and our method is based on partitions. This proves the efficiency of our method. Regarding the other two methods, we can see that we achieve comparative results: prototype based algorithms do better on the WDBC and SpamBase dataset, and we do better with the other datasets.

However, please note that comparing collaborative algorithms is very difficult and that these experiments may not be very significant to determine which method is more effective: for instance both the collaborative SOM and GTM algorithms only allow pairwise communication during the collaboration process, while in our method and in the multi-view EM all algorithms communicate at the same time. Another difference is that unlike our method, the 3 others have objective functions using prototypes instead of partitions which makes communication easier between algorithms but also restricts the collaboration between similar algorithms looking for the same number of clusters, hence why we decided to use only EM algorithms for our methods in order to have settings as similar as possible. Furthermore, the collaborative SOM and GTM algorithms computes topographic maps and not directly clusters.

The partition can only be found by using the K-Means or EM algorithm on the final map, thus affecting the performances of both methods. Finally, when comparing a collaborative EM algorithm to a collaborative GTM algorithm, one can wonder if it is really the collaboration process that is evaluated, or the efficiency of the EM algorithm versus the GTM algorithm. For these reasons, the results of this section have to be taken with caution. As one can see, there is an obvious hierarchical relationship between the different objects of interests that can be detected when searching for different numbers of clusters. However, the In our experiment, we compare our results with these of two 898 other algorithms: the EM algorithm for the Gaussian Mixture 899 Model [START_REF] Dempster | Maximum likelihood from incomplete 1202 data via the em algorithm[END_REF] , and the regular SR-ICM algorithm [START_REF] Sublime | Semantic 1196 rich ICM algorithm for VHR satellite image segmentation[END_REF] both looking 900 for 3, 6 and 9 clusters. In Fig. 2 , we show the hierarchical clusters 901 that we expected to find. The goal of the experiment is to demon-902 strate that our proposed collaborative method performs as best or 903 better than local clustering methods working individually at dif-904 ferent scales, but also that is these hierarchical structures will be 905 reflected in the PCM matrices, and that the collaborative process 906 will strengthen them.

907

The results were assessed using the Davies -Bouldin index as a 908 an internal criterion. This index assesses the compactness of the 909 clusters and how well they are separated. It is worth mentioning 910 that the Davies -Bouldin index usually gives better results with less 911 clusters. As for the external index, we used the Rand Index to com-912 pare our results with the expert ground truth. 8 , where the best 915 result for each number of cluster is highlighted in bold.

916

As one can see, once again the results are non conclusive with 917 the Rand Index where our method is not significantly better than 918 the other. This was to be expected for the reason that like in the 919 previous experiment, our collaborative framework does not have 920 access to the expert ground truth and therefore cannot be expected 921 to improve external indexes. However, we can see that we perform 922 better than the other methods on the 6 and 9 clusters scale, with 923 a much higher level of significance. The slightly lower performance 924 on the 3 clusters scale can be explained by the fact that our col-925 laborative approach mimics hierarchical clustering both ascending 926 and descending since the collaboration goes both ways. However 927 the descending approach is far more beneficial to get a goo d hi-928 erarchy leading to spherical clusters centered around the mean of 929 Please cite this article as: J. the parent cluster at the upper scale, and therefore our methods works much better at scales with more clusters.

Finally, if when comparing the results with these of Table 7 , an interesting remark is that the multi-scale approach with all the data as we did it in this experiments leads to better results that the multi-view approach of the previous experiment. This was to be expected since having access to all the data plus different scales of clusters leads to more information than just collaborating on partial views of the data.

In Fig. 3 , we show the hierarchical structures extracted from the PCM matrices of our method. As one can see, there are some differences with the expected clusters from Fig. 2 , that we have highlighted in red. In particular, we note that the hierarchical structure is not perfect with some classes covering each other. More interestingly there seem to be a confusion several blue elements of the image (namely individual houses with blue roofs and water) which may hint that the color attributes remain the dominant ones in the formation of the clusters when not using a multi-view approach.

Computation times

In Table 9 , we show the average computation times achieved by our algorithm with different data sets given different numbers of collaborators and the two types of combination function. We used a C++ implementation of our method, running on a i5-3210M at the end of the local step, but remains mostly stable when the 961 number of collaborators or the diversity between the initial solu-962 tions increases.

963

As one can see in Table 9 , the g * combination function is much 964 faster than the exact combination function g ∩ , and the computa-965 tion times then increase with the number of clusters and the com-966 plexity of the data sets. Please note, that the computations times 967 for g ∩ with the VHR Strasbourg data set are not complete due to 968 overly long computation times.

Conclusion 970

In this article, we have proposed a new collaborative framework 971 that enables various algorithms to mutually improve their results. 972 Our main contribution is that our proposed method allows algo-973 rithms of different types to work together regardless of the num-974 ber of clusters they are searching for. The strength of our approach 975 is that it needs neither the subsets, nor the prototypes, or the 976 models used by the different algorithms to be shared during the 977 collaboration step: only the solution vectors produced by all algo-978 rithms need to be shared. Our framework is therefore more generic than previously proposed methods for horizontal collaboration in a sense that it has much less restrictions in terms of which algorithms can collaborate together. The cost of this more generic context is that our method cannot deal with vertical collaboration whereas some early methods could.

The optimization process behind our method is based on the variational EM, and optimizes a collaborative term which is equivalent to an entropy, thus ensuring good convergence properties.

Our framework has been tested on several data sets in a multiview, a multi-experts and a multi-scale collaborative clustering contexts. Our results have validated the efficiency of our approach in bringing improvements to clustering solutions via collaboration.

Furthermore, these experiments have highlighted that our method can find a large number of applications such as multi-view clustering, clustering of distributed data and hierarchical multi-scale clustering.

In our future works, we will focus on improving the overall collaboration process by weighting differently the influence of the different collaborators towards one another depending on quality and diversity measures. By doing so our goal will be to reduce cases of • It was corrected for distortion effects and issues due to the satellite angle.

• Then, a first segmentation was done using the software eCognition.

• The first segmentation was corrected to merge small neighboring segments that were too similar. This operation led to the 187.058 final segments. 1 Available from Dr. J. Sublime ResearchGate account.

Finally, we would like to mention that the VHR Strasbourg data 1038 set was provided with a partial hybrid ground truth containing 15 1039 classes [START_REF] Sublime | Semantic 1196 rich ICM algorithm for VHR satellite image segmentation[END_REF] . The process to build the ground truth was the follow-1040 ing: 1041

• Expert geographers determined 15 classes of interest.

1042

• Using on-field observations, Google Maps and city plans, they 1043 labeled a high resolution map of the city.

1044

• The expert map was projected on the VHR Strasbourg segmen-1045 tation so that each segment was given a label using a majority 1046 vote based on percentage of covering.

1047

• The 10% of the segments being on the German side of the bor-1048 der are not covered by this ground-truth.

1049

While we are ware that this hybrid ground-truth is not with-1050 out flaws, the visual results seemed good enough to use it as a 1051 reference for our external indexes when conducting experiments 1052 using the VHR Strasbourg data set. Furthermore, from the 15 orig-1053 inal classes we merged a few that could not possibly be detected 1054 by a unsupervised algorithm (e.g. winter crops and summer crops, 1055 more than 50 ha vegetation and more than 10 ha vegetation, etc.) 1056 and ended up with 9 classes.

  4 , we show how to optimize this new function with a low complexity of O ( N ). Very much like in Eq. (3) , we consider that the functional in the collaborative setting is decoupled into two different terms, the local term L ( S , ) computed from all local log-likelihood or quality indexes, and the collaborative term C ( S ) in the form of a global consensus function between the partitions.

453 3 . 4 .

 34 Update rules454

  leads to very simple update rules which require only the local likelihood proposed by each algorithm for the possibles clusters of each data, the partitions produced by all the algorithms, and a good combination function g i . This combination function, through which the algorithms will collaborate, has the key role of assessing the likelihood of a local decision based on the other algorithms' partitions. Since the M-Step of our proposed algorithm only used information from the local term of the functional, the update rules are identical to these of the local algorithm in their non-collaborative version. For instance, in the case of a Gaussian mixture model, the mean , variance-covariance and mixing probabilities of each clusters are computed using the usual rules.

587

  All three combinations functions have a complexity in O ( J × N ). 588 However, using g + and g * , the combinations functions' values can 589 be computed only once at the beginning of each iteration and 590 stored in an array of size J 2 × K 2 instead of being computed on the 591 flight for each of the N data. Using this technique, the right com-592 plexity term involving the combination function disappears. How-593 ever, this is not an option with the function g ∩ where at best 594 J × K J-1 values would have to be computed and stored. 595 Therefore, using g + or g * while storing the values in memory, 596 the best possible complexity is:

  the best case scenario using the optimized version 605 of g + or g * with the memory trade off, the collaboration adds a lin-606 ear complexity term in O ( N ). Considering that the best clustering 607 algorithms also have a linear complexity, the loss of performance 608 is negligible when compared with using the original clustering al-609 gorithms in parallel. Therefore, using fast algorithm, we can get a 610 complexity in O ( N ) to optimize the functional in Eq. (7) .611 3.5. Stopping criterion 612

Fig. 1 .

 1 Fig. 1. 2-dimension projection of 3 partitions of 2 clusters each, on a 81 observations data set. The small numbers in the figure highlight the number of data in each intersection of clusters.

24 In Fig. 1 ,• 704 •

 241704 we are interested in the data x n which has been as-690 signed to a , b and c by the 3 algorithms respectively. Let us sup-691 pose now, that we use our combination function g to see whether 692 or not the decision of the first algorithm to put x n in the cluster 693 a makes consensus with the partition of the two other algorithms 694 which put it in b and c . In Table2, we show how to practically 695 use the intersections of the clusters to compute g i ( q , a ) and g i ( q , 696 a ) with all 3 combination functions that we have introduced ear-697 lier (using τ = 1 ). The same experiment is done in Tables3 and 6984 , to check the consensus on b / b and c / c respectively for the 699 same data x n . 700 The results are interesting in several ways: 701 First we have the confirmation that all 3 functions roughly be-702 have the same way and agree on the same most consensual 703 clusters. We can observe the complementary relationships between

830 4 . 3 .

 43 Comparison with other methods831 4.3.1. Comparison with other collaborative algorithms 832 In this section, we propose a comparison with other algorithms 833 from the literature: we compare our method using several EM al-834 gorithms for the Gaussian mixture model collaborating together 835 (with g + and λ = 0 . 5 ) with the multi-view EM algorithm, the col-836 Please cite this article as: J. Sublime et al., Entropy based probabilistic collaborative clustering, Pattern Recognition (2017), http://dx.

913 4 . 3 . 2 . 2 .

 4322 Results. The results of this experiments over a dozen sim-914 ulations for each algorithm are shown in Table

Fig. 2 .

 2 Fig. 2. Expected hierarchical clusters.

Fig. 3 .

 3 Fig. 3. Found hierarchical clusters.

  969

Acknowledgement

  This work has been supported by the ANR project COCLICO, ANR-12-MONU-0 0 01 .Appendix A. Data setsA1. VHR Strasbourg data setThe VHR Strasbourg 1 data set[START_REF] Rougier | Improvements of urban vegetation segmentation and 1204 classification using multi-temporal pleiades images[END_REF] contains the description of 187.058 segments extracted from a very high resolution satellite image of the French city of Strasbourg. The original image covers an area of approximately 4 × 5 km with one pixel being equivalent to a (10 cm ) 2 area. The original image then went through the following process:

Each segment is described by numerical 27

 27 attributes, as well as a 28th column containing the IDs of neighbor segments. The first 27 attributes contain different types of features describing the segments: Radiometric features from the original image (brightness, colors, hue, saturation, min/max pixel values, etc.), geometric features (shape, size, coordinates, skewness, orientation, border length, circular mean, etc), comparison features with neighboring segments (contrast, number of brighter objects, number of darker objects, min difference to neighbors, etc.). As one can see, this data set is good for multi-view clustering by construction due to the different types of available features. But because of the very high resolution of the image, it can also be used for multi-scale clustering. Indeed different scales of interest are available: From only 3 clusters (vegetation, water areas and urban area), to a large number of clusters on urban elements (trees, cars, individual pools, roads, individual houses, etc.). All scales in between can be studied depending on the considered number of clusters.

1057A2.•

  Other data sets1058Several data sets used in this article are from the UCI repository 1059[START_REF] Frank | UCI machine learning repository[END_REF] :1060 Wisconsin Diagnostic Breast Cancer (WDBC): This data set con-1061 tains 569 instances having 30 parameters and 2 classes. These 1062 30 parameters contain 10 descriptors for 3 different cells of 1063 the same patient. And these descriptors can themselves be split 1064 into geometric and other appearance based attributes, therefore 1065 making this data set also good for multi-view.

  the number of data in this clus-279 i and the b th cluster of A j at the same time. The PCM i , j

		JID: PR	ARTICLE IN PRESS	[m5G; July 10, 2017;19:28 ]
	280	ter, and | S i a ∩ S	j b | is the number of data linked to the a th cluster
	317 318	of A solution S i made of K i clusters, based on the features of the data set X i ⊆X it has access to. In the case of hard clustering, S i can be
	319	translated into a solution vector of size N , and for fuzzy clustering
	320	into a matrix of size N × K i . We denote this later matrix S i = (s i n,c ) ,
	321	where 1 ≤ n ≤ N and 1 ≤ c ≤ K i . The solutions S i output by the algo-
	322 323	rithms are therefore two-dimensional matrices of size N × K i where each element s i n,c expresses the responsibility (probability) given
	324	by algorithm A i to a cluster c for the data element x n .
	325	Each algorithm A i computes the solutions S i , as usual by intro-
	326	ducing a latent discrete random vector Z i defined on some latent
	327 328	space with the range [1 , . . . , K i ] , hence computing the a posteriori distribution of the variable Z i conditionally on X i and S i .
	329	Finally, in order to quantify the degree of information coming
	330	from the collaboration, for a given algorithm A i , we will assume
	331	the existence of some weight τ j , i ∈ (0, 1), which measure the rel-
	332	ative external information from the algorithm j = i accepted by A i .
	333	All weights τ j , i are stored in a square matrix of size J × J which
	334	therefore contains the strength of all collaboration links. Most no-
	335	tations used in this article are summed up in Table 1 bel ow.
		3.2. Problem formulation

336

Within the context of horizontal collaboration that we have 337 presented before, the method that we propose takes many ad-338

  Sublime et al., Entropy based probabilistic collaborative clustering, Pattern Recognition (2017), http://dx.doi.org/10.1016/j.patcog.2017.07.014

	JID: PR	ARTICLE IN PRESS	[m5G; July 10, 2017;19:28 ]

Table 5

 5 Multi-view collaboration improvement results on internal indexes.

	Data Set	Simulations	Silhouette Index		DB-Index
			Average Improvement	Min/Max	Average Improvement	Min/Max
	WDBC	100 × 10	μ = 0 . 122 σ = 0 . 057	+0 . 241 -0 . 09	μ = -0 . 013 σ = 0 . 011	+0 . 042 -0 . 036
	Imgseg	100 × 7	μ = 0 . 091 σ = 0 . 020	+0 . 133 -0 . 017	μ = 0 . 102 σ = 0 . 071	+0 . 251 -0 . 101
	Spam Base	100 × 5	μ = 0 . 037 σ = 0 . 026	+0 . 081 -0 . 122	μ = 0 . 165 σ = 0 . 129	+0 . 440 -0 . 106
	Battalia3	100 × 3	μ = 0 . 025 σ = 0 . 004	+0 . 092 -0 . 147	μ = 1 . 375 σ = 0 . 327	+1 . 793 -1 . 184
	MV2	100 × 4	μ = 0 . 04 σ = 0 . 008	+0 . 083 +0 . 01	μ = 0 . 45 σ = 0 . 08	+1 . 320 +0 . 02
	VHR Strasbourg	35 × 5	μ = 0 . 027 σ = 0 . 005	+0 . 037 -0 . 049	μ = 0 . 377 σ = 0 . 047	+0 . 475 -0 . 094

Table 6

 6 Multi-view collaboration improvement results on the adjusted Rand Index.

	Data Set	Simulations	Adjusted Rand Index
			Average Improvement	Min/Max
	WDBC	100 × 10

Table 7

 7 doi.org/10.1016/j.patcog.2017.07.014 Experimental results.

	JID: PR	ARTICLE IN PRESS		[m5G; July 10, 2017;19:28 ]
	Dataset		Our Model	MV-EM		GTM collab		SOM collab
			Rand	DB	Rand	DB	Rand	DB	Rand	DB
	Wdbc (2 clusters)		95.50	0.85	92.30	0.97	96.57	0.9	97.08	0.84
	SpamBase (2 clusters)	86.77	0.94	74.69	1.27	83.79	0.92	84.27	0.87
	Battalia3 (6 clusters)		80.00	2.43	77.37	2.83	78.04	2.68	78.75	2.51
	MV2 (4 clusters)		94.32	1.34	93.72	1.34	89.61	1.61	90.21	1.44
	VHR Strasbourg (9 clusters)	74.56	2.89	73.37	3.21	68.97	4.15	70.14	3.78

Table 8

 8 size of these data sets usually makes them ineligible for hier-891 archical clustering algorithms because of their high computational 892 complexity. We therefore propose an experiment in which we use 893 our collaborative Framework on several instances of the previously 894 mentioned SR-ICM algorithm searching for 3, 6 and 9 clusters with 895 access to all attributes. In this experiment, we use the g * combina-896

	Experimental results: Hierarchical collaborative cluster-
	ing.
	Algorithm	Davies -Bouldin Index	Rand Index
	EM 3	2.36928	0.67454
	SR-ICM 3	2.32855	0.67606
	Co SR-ICM 3	2.32674	0.67435
	EM 6	2.88014	0.75867
	SR-ICM 6	2.67816	0.76935
	Co SR-ICM 6	2.49726	0.77068
	EM 9	2.62786	0.78225
	SR-ICM 9	2.94065	0.79063
	Co SR-ICM 9	2.58836	0.792187
	tion function and λ = 1 2 .		897

huge

Table 9

 9 Computation times.

	Data Set	Computation time / number of collaborators
		2	3	5	7	10
	WDBC g ∩	7s	15s	45 s	77s	3 min
	ImgSeg g ∩	2 min	5 min	13 min	27 min	52 min
	Spam base g ∩	6 min	17 min	42 min	1 h 38	4h
	WDBC g * /g +	2 s	3 s	6 s	8 s	13 s
	ImgSeg g * /g +	9 s	16 s	27 s	34 s	46 s
	Spam base g * /g +	56 s	1 min 25	2 min 23	3 min 18	4 min 27
	VHR Strasbourg g * /g +	24 min	37 min	1 h 04	1 h 28	2 h

1066 •

 1066 Image Segmentation data set (ImgSeg): The 2310 instances of 1067 this data set were drawn randomly from a database of 7 out-1068 door images. The images were hand segmented to create a clas-1069 sification for every pixel. Each instance is a 3 × 3 region repre-1070 sented by 19 attributes and there are 7 classes to be found. The 1071 19 attributes are either color-based (sub-divised into red, green 1072 and blue attributes), position based (row, column, pixel count), 1073 or other color attributes (contrast, hue, etc.) 1074 • Spam Base : The Spam Base data set contains 4601 observa-1075 tions described by 57 attributes and a label column: Spam or 1076 not Spam (1 or 0). The different attributes can be split into 1077 word frequencies, letter frequencies and capital run sequences 1078 attributes. The Battalia3 data set 2 (artificial): Battalia3 is an artificial 1081 dataset created using the exoplanet random generator from the 1082 online game Battalia.fr; This data set describes 20 0 0 randomly 1083 generated exoplanets with 27 numerical attributes and their as-1084 sociated class (6 classes). The attributes can be split between 1085 system and orbital parameters (7 attributes), planet charac-1086 teristics (10 attributes) and atmospheric characteristics (10 at-1087 tributes). 1088 • The "MV2 " data set (artificial): A data set created specifically 1089 to test this kind of algorithm. It features 20 0 0 randomly gener-1090 ated data, split into 4 views of 6 attributes each, and a total of 4 1091 classes. All attributes were generated either from Gaussian dis-1092 tributions with parameters linked to the matching class, or are 1093 random noise, or are linear combinations of other attributes.

1079

We also used two artificial data sets: 1080 •

Collaborative methods usually follow a two-step procedure[START_REF] Pedrycz | Collaborative fuzzy clustering[END_REF] :

1. Local step : Each algorithm will individually process the data it

has access to and produce a local clustering partition.

2. Collaborative step : The algorithms share their results and try to

confirm or improve their models with the goal of achieving bet-134 ter clustering results. 135

Please cite this article as: J. Sublime et al., Entropy based probabilistic collaborative clustering, Pattern Recognition (2017), http://dx.doi.org/10.1016/j.patcog.2017.07.014

Available from Dr. J. Sublime ResearchGate account. Please cite this article as: J. Sublime et al., Entropy based probabilistic collaborative clustering, Pattern Recognition (2017), http://dx.doi.org/10.1016/j.patcog.2017.07.014

ARTICLE IN PRESS

JID: PR [m5G; July 10, 2017;19:28 ]

ARTICLE IN PRESS