Tianshu Yang

Nicolas Pasquier

Frederic Precioso

{𝐶

{𝑥

𝑆

= {{𝑥

}} {{𝑥

}} 𝑆

{{𝑥

{𝑥 {∅

Semi-supervised Consensus Clustering Based on Closed Patterns

Keywords:

Semi-supervised consensus clustering, also called semi-supervised ensemble clustering, is a recently emerged technique that integrates prior knowledge into consensus clustering in order to improve the quality of the clustering result. In this article, we propose a novel semi-supervised consensus clustering algorithm extending the previous work on the MultiCons multiple consensus clustering approach. By using closed pattern mining technique, the proposed Semi-MultiCons algorithm manages to generate a recommended consensus solution with a relevant inferred number of clusters 𝑘 based on ensemble members with different 𝑘 and pairwise constraints. Compared with other semi-supervised and/or consensus clustering approaches, Semi-MultiCons does not require the number of generated clusters 𝑘 as an input parameter, and is able to alleviate the widely reported negative effect related to the integration of constraints into clustering. The experimental results demonstrate that the proposed method outperforms state of the art semi-supervised consensus clustering algorithms.

Semi-supervised clustering

. Semi-supervised clustering approaches can be classified into three types [6]: Constraint-based methods, distancebased methods and hybrid methods.

Constraint-based methods refer to algorithms that utilize supervision information to restrict the feasible solutions

Introduction

Clustering is the process of grouping data into partitions so that similar instances are most likely to be placed in the same partition [START_REF] Grira | A review of machine learning techniques for processing multimedia content[END_REF]. Many clustering algorithms were proposed regards to different applications and data properties [START_REF] Ahmad | Survey of state-of-the-art mixed data clustering algorithms[END_REF][START_REF] Rodriguez | Clustering algorithms: A comparative approach[END_REF][START_REF] Xu | A comprehensive survey of clustering algorithms[END_REF]. Each one of them has its own strengths as well as its own limitations [START_REF] Ghosh | A survey of consensus clustering[END_REF][START_REF] Karypis | Chameleon: Hierarchical clustering using dynamic modeling[END_REF]. Therefore, more and more researchers focus on consensus clustering, also called clustering ensemble, since it provides a more stable, robust and accurate performance than any single clustering algorithm [START_REF] Boongoen | Cluster ensembles: A survey of approaches with recent extensions and applications[END_REF][START_REF] Wu | A comparative study of clustering ensemble algorithms[END_REF]. Consensus clustering, also referred to as clustering ensemble, aims to enhance the clustering process by combining multiple clustering results generated from different clustering algorithms with different parameterizations [START_REF] Nguyen | Consensus clusterings[END_REF][START_REF] Topchy | Clustering ensembles: Models of consensus and weak partitions[END_REF][START_REF] Vega-Pons | A survey of clustering ensemble algorithms[END_REF]. However, as an unsupervised learning method, consensus clustering approaches cannot make use of supervision information, even if sometimes such information is available for some instances. This leads to the emergence of semi-supervised consensus clustering, also referred to as semi-supervised clustering ensemble, which aims at using such a prior knowledge in the consensus clustering to improve the quality of the final clustering.

In this paper, we propose a novel semi-supervised consensus clustering algorithm, named Semi-MultiCons, extending the previous work on the MultiCons consensus clustering approach [START_REF] Al-Najdi | Multiple consensuses clustering by iterative merging/splitting of clustering patterns[END_REF]. Like described in [START_REF] Al-Najdi | Multiple consensuses clustering by iterative merging/splitting of clustering patterns[END_REF], Semi-MultiCons uses closed pattern mining technique, based on frequent closed itemset mining technique, to generate multiple consensus clustering solutions with inferred 𝑘. Meanwhile, we developed a novel consensus function based on pairwise constraints and a strategy to select the most appropriate inferred 𝑘. We also optimized the implementation of [START_REF] Al-Najdi | Multiple consensuses clustering by iterative merging/splitting of clustering patterns[END_REF] to reduce the time and space complexities of the closed pattern processing by the approach. yang@i3s.unice.fr (T. YANG); pasquier@i3s.unice.fr (N. PASQUIER); precioso@i3s.unice.fr (F. PRECIOSO) ORCID(s):

The remaining of the paper is organized as follows. In Section 2, we report on related work on semi-supervised clustering, consensus clustering and semi-supervised consensus clustering. In Section 3, we present preliminary notions about prior knowledge representation and the Multi-Cons approach. Section 4 introduces and explains the novel Semi-MultiCons method. Section 5 presents and analyzes the experimental results. The conclusions and future work are stated in Section 6.

Related work

Many algorithms, based on different principles and formalisms for grouping instances of a dataset into clusters according to their similarity, have been proposed in the literature. The most recent approaches developed in this domain presented in this section intent to optimizing this process. Semi-supervised clustering methods aim at integrating available initial prior knowledge about the relevance of grouping or separating certain pairs of instances. Consensus clustering methods aim to combine the results of different clustering algorithms, based on different approaches, to generate a final clustering based on the most frequent aggregations between the initial clusterings. The semi-supervised consensus clustering approach combines these two methods in order to optimize the clustering result in terms of robustness and relevance of the result, depending on the initial information available in the application domain. when assigning data to clusters, either directly by changing assignment strategy to prevent assignments that violate supervision information [START_REF] Wagstaff | Constrained k-means clustering with background knowledge[END_REF], or indirectly by penalizing and/or rewarding objective function if supervision information is violated and/or satisfied [START_REF] Davidson | Clustering with constraints: Feasibility issues and the k-means algorithm[END_REF][START_REF] Pelleg | K-means with large and noisy constraint sets[END_REF]. With distancebased methods, supervision information is applied in distance learning. This distance can be a distance in the original data space [START_REF] Xing | Distance metric learning, with application to clustering with side-information[END_REF], distance in low dimension feature space [START_REF] Tang | Enhancing semisupervised clustering: a feature projection perspective[END_REF] or even kernel distance matrix [START_REF] Hoi | Learning nonparametric kernel matrices from pairwise constraints[END_REF]. Hybrid methods combine constraint-based methods and distance-based methods [START_REF] Basu | A probabilistic framework for semi-supervised clustering[END_REF].

Semi-supervised clustering takes advantage of supervised information to improve the performance and guide the search to meet user preferences and domain knowledge. However, since most semi-supervised algorithms are iterative and sensitive to input order of data, they are less stable and robust.

Consensus clustering

Consensus clustering aims to address the limitations of single clustering approaches and to improve the robustness and quality of result by combining multiple clustering solutions generated from different clustering algorithmic configurations, that is different algorithms with different parameterizations, [START_REF] Topchy | Clustering ensembles: Models of consensus and weak partitions[END_REF]. The problem can be described as follows. Let 𝑚 denotes the number of clustering solutions. Φ represents the result sets of clustering solutions Φ = {𝛾 1 , 𝛾 2 , ..., 𝛾 𝑚 }, where 𝛾 𝑖 = {𝐶 𝑖 1 , 𝐶 𝑖 2 , ..., 𝐶 𝑖 𝑘 } is the 𝑖 𝑡ℎ clustering result with 𝑘 clusters. 𝐶 𝑖 𝑗 denotes the 𝑗 𝑡ℎ cluster of the 𝑖 𝑡ℎ solution. The goal is to find a consensus partition 𝑃 which better reflects the relevant properties of each solution in Φ.

In general, consensus clustering methods consist of two stages. At the first stage, different clustering solutions Φ are generated from the same dataset. Then, in the second stage, a consensus function is applied on Φ to find the final consensus clustering [START_REF] Boongoen | Cluster ensembles: A survey of approaches with recent extensions and applications[END_REF]. Figure 1 shows an overview of the consensus clustering process.

There are various ensemble generation strategies and consensus function approaches. A clustering ensemble can be achieved by using different clustering algorithms, by random sub-spacing/sampling initial data [START_REF] Minaei-Bidgoli | Effects of resampling method and adaptation on clustering ensemble efficacy[END_REF], by using different number of clusters 𝑘 parameter values, by repeated executions of a single clustering algorithm with several parameter sets [START_REF] Iam-On | Refining pairwise similarity matrix for cluster ensemble problem with cluster relations[END_REF], or by using any combination of the aforementioned methods. Different consensus functions have been developed to combine the base clustering results, such as mixture models [START_REF] Topchy | A mixture model for clustering ensembles[END_REF], voting-based approach [START_REF] Ayad | On voting-based consensus of cluster ensembles[END_REF], mutual information [START_REF] Topchy | Combining multiple weak clusterings[END_REF], co-association based approach [START_REF] Fred | Finding consistent clusters in data partitions[END_REF], graph and hyper-graph based approaches [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] and genetic algorithms [START_REF] Luo | Combining multiple clusterings using information theory based genetic algorithm[END_REF] among others.

Consensus clustering is proved to outperform single clustering method on stability and accuracy [START_REF] Topchy | Analysis of consensus partition in cluster ensemble[END_REF][START_REF] Wang | Semi-supervised consensus clustering for gene expression data analysis[END_REF]. However, as an unsupervised learning method, it is not designed to use any supervision information, even though sometimes a such information is available.

Semi-supervised consensus clustering

Considering the limitations of semi-supervised clustering and consensus clustering, it is natural to combine them, and thus semi-supervised consensus clustering emerged. Semi-supervised consensus clustering not only considers supervision information, but also integrates multiple clustering results into a unified consensus solution to improve the quality, stability and robustness of the final result [START_REF] Yu | Semi-supervised ensemble clustering based on selected constraint projection[END_REF].

Supervision information can be used in both steps of consensus clustering, as shown in Figure 2. It can be used in base clustering generation, which means, replace unsupervised clustering method with semi-supervised clustering method. In the consensus step, prior knowledge can be integrated in the consensus function to lead the consensus process. For example, instead of using all generated clusters and treating each of them without difference, the existence of supervision information makes it possible to assign different weight to clusters. Usually, clusters that violate supervision information are eliminated or assigned a lower weight.

Several semi-supervised consensus clustering approaches have been proposed during the last few years. In [START_REF] Yu | Knowledge based cluster ensemble for cancer discovery from biomolecular data[END_REF], prior knowledge is used to evaluate the quality of each base spectral clustering result. A confidence matrix of each cluster is then constructed based on it and is used with spectral clustering as consensus function. In [START_REF] Iqbal | Semi-supervised clustering ensemble by voting[END_REF], voting based consensus clustering is extended to semi-supervised context by replacing unsupervised base clusterings with semi-supervised base clusterings. Users are required to provide weights for each semi-supervised clustering algorithm and for each cluster. These weights are engaged in a voting based consensus function to produce the final clustering. In [START_REF] Yang | Consensus clustering based on constrained self-organizing map and improved Cop-Kmeans ensemble in intelligent decision support systems[END_REF], an improved COP-Kmeans (Constraint Partitioning K-means) algorithm [START_REF] Wagstaff | Constrained k-means clustering with background knowledge[END_REF] is proposed as base semi-supervised clustering method, and a new constrained self-organizing map approach is implemented as consensus function. In [START_REF] Wang | Semi-supervised consensus clustering for gene expression data analysis[END_REF], a semi-supervised spectral clustering approach is used for base clusterings, while the authors' graph based consensus function, named Hybrid Bipartite Graph Function [START_REF] Fern | Solving cluster ensemble problems by bipartite graph partitioning[END_REF], remains unsupervised. In [START_REF] Mahmood | Semisupervised evolutionary ensembles for web video categorization[END_REF], a genetic algorithm based consensus function is extended by taking supervision information into consideration in the fitness function. In [START_REF] Yu | Incremental semi-supervised clustering ensemble for high dimensional data clustering[END_REF], cluster ensemble members are generated by a constraint propagation algorithm [START_REF] Lu | Exhaustive and efficient constraint propagation: A graph-based learning approach and its applications[END_REF], which is a semi-supervised method. Prior knowledge is also used to evaluate and eliminate ensemble members, and only a subset of these ensemble members are taken into account in a graph based consensus function. In [START_REF] Xiao | Semi-supervised hierarchical clustering ensemble and its application[END_REF], prior knowledge is integrated in both the CHAMELEON unsupervised hierarchical clustering algorithm [START_REF] Karypis | Chameleon: Hierarchical clustering using dynamic modeling[END_REF] to improve its result and in the co-association matrix used by the consensus function. In [START_REF] Yu | Semi-supervised ensemble clustering based on selected constraint projection[END_REF], instead of using all prior knowledge, different subsets of prior knowledge are assigned each to different ensemble members. Then, an adaptive weighting process associates each ensemble member with its weight, and the weighted normalized cut algorithm, that is a graph based consensus function, is adopted to generate the final result. A summary about this related work is shown in Table 1. Besides these approaches, recent reported methods seek to apply semi-supervised consensus learning to deep learning domain on various types of data and in many tasks. This is, for example, the approach taken in self-ensembling teacher-student method on graph-structured data [START_REF] Luo | Every node counts: Self-ensembling graph convolutional networks for semisupervised learning[END_REF] and co-training method in semantic segmentation task [START_REF] Luo | Categorylevel adversarial adaptation for semantic segmentation using purified features[END_REF][START_REF] Luo | Taking a closer look at domain shift: Category-level adversaries for semantics consistent domain adaptation[END_REF].

In this paper, we propose a novel semi-supervised consensus clustering approach that integrates supervised information as pairwise constraints, similarly to the ideas in [START_REF] Yang | Consensus clustering based on constrained self-organizing map and improved Cop-Kmeans ensemble in intelligent decision support systems[END_REF][START_REF] Yu | Incremental semi-supervised clustering ensemble for high dimensional data clustering[END_REF], in both base clustering generation step and consensus function execution, like [START_REF] Iqbal | Semi-supervised clustering ensemble by voting[END_REF][START_REF] Xiao | Semi-supervised hierarchical clustering ensemble and its application[END_REF][START_REF] Yang | Consensus clustering based on constrained self-organizing map and improved Cop-Kmeans ensemble in intelligent decision support systems[END_REF][START_REF] Yu | Semi-supervised ensemble clustering based on selected constraint projection[END_REF][START_REF] Yu | Incremental semi-supervised clustering ensemble for high dimensional data clustering[END_REF]. Unlike the other approaches which use base clusterings to estimate the relationships among instances, such as co-association matrix [START_REF] Xiao | Semi-supervised hierarchical clustering ensemble and its application[END_REF] or normalized cut graph [START_REF] Yu | Semi-supervised ensemble clustering based on selected constraint projection[END_REF][START_REF] Yu | Incremental semi-supervised clustering ensemble for high dimensional data clustering[END_REF] based approaches, the Semi-MultiCons approach constructs a binary membership matrix, which eventually corresponds to a bipartite graph, as described in [START_REF] Wang | Semi-supervised consensus clustering for gene expression data analysis[END_REF], representing the relationships between instances and ensemble clusters. The output of the Semi-MultiCons approach is a hierarchical structure similar to [START_REF] Xiao | Semi-supervised hierarchical clustering ensemble and its application[END_REF].

Preliminaries

The Semi-MultiCons approach relies on the use of partial background knowledge, represented as constraints of coassignment to a cluster or of assignment to different clusters concerning a certain number of instances of the dataset, and the extension of the MultiCons approach for multiple consensus clusterings based on the Galois closed set theory. These two central concepts are presented in this section.

Pairwise constraints

The prior knowledge integrated in semi-supervised clustering is also called constraints since this knowledge can be seen as constraints on how data should be grouped during the clustering process. Many types of constraints exist, including partial label constraints, pairwise constraints, capacity constraints [START_REF] Wagstaff | Intelligent clustering with instancelevel constraints[END_REF], while the most popular one is pairwise constraints which describe true similarity between pairs of instances. Common pairwise constraints include must-link constraints and cannot-link constraints [START_REF] Wagstaff | Clustering with instance-level constraints[END_REF]:

• Must-link constraints imply that two instances must be assigned to the same cluster, or more generally, they are more likely to be similar with each other.

• Cannot-link constraints imply that two instances can not be assigned to the same cluster, or more generally, they are more likely to be dissimilar with each other.

Must-link constraints and cannot-link constraints are widely used in semi-supervised clustering algorithms [START_REF] Ruiz | Density-based semi-supervised clustering[END_REF][START_REF] Wagstaff | Clustering with instance-level constraints[END_REF], in metric learning [START_REF] Wang | Semisupervised metric learning by maximizing constraint margin[END_REF], in dimensionality reduction [START_REF] Chen | Semisupervised dimensionality reduction with pairwise constraints for hyperspectral image classification[END_REF] and many other domains. In this paper, prior knowledge is provided in the form of must-link and cannot-link constraints.

MultiCons Approach

The MultiCons approach for multiple consensus clustering is presented in [START_REF] Al-Najdi | A closed patterns-based approach to the consensus clustering problem[END_REF]. This approach is based on the frequent closed itemset framework [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF] to efficiently discover closed patterns among the different base clustering solutions. Each closed pattern defines an agreement between the base clusterings in grouping a set of dataset instances. By dividing/merging these patterns into groups, MultiCons generates multiple consensuses in a tree-like structure that helps understanding the clustering process and the data space subjacent natural structures.

In the following subsections, the MultiCons approach is described step by step and illustrated using a dataset 𝑋 = {𝑥 1 , 𝑥 2 , ..., 𝑥 9 } of nine instances as a support example.

Ensemble members

The clustering ensemble, consisting of several base clusterings, defines the search space in input of the approach. Different clustering algorithms with different parameter settings, defining each an algorithmic configuration, are used in this step to ensure diversity in the initial clustering solutions that will be combined by the consensus function. This diversity allows to discover intrinsic clusters in the data space, defined by the analyzed dataset, corresponding to different subspace structures. These data subspace structures can be discovered by different algorithmic approaches, such as centroid based, density based or hierarchical based clustering approaches for instance, with different parameter settings.

As a support example of the MultiCons process, we consider the five base clusterings in the clustering ensemble shown in Table 2 generated by applying five unsupervised clustering algorithms to dataset 𝑋. A summary on semi-supervised consensus clustering methods. For each referred method, the approach used for generating base clusterings and in the consensus function, as well as the steps involving the use of the supervision information are described.

Method

Base clustering Consensus function

Steps involving supervision information [START_REF] Yu | Knowledge based cluster ensemble for cancer discovery from biomolecular data[END_REF] Spectral clustering Spectral clustering Consensus step [START_REF] Iqbal | Semi-supervised clustering ensemble by voting[END_REF] Semi-supervised clustering Voting based approach Generation step and consensus step [START_REF] Yang | Consensus clustering based on constrained self-organizing map and improved Cop-Kmeans ensemble in intelligent decision support systems[END_REF] Improved COP-Means COP-SOM Generation step and consensus step [START_REF] Wang | Semi-supervised consensus clustering for gene expression data analysis[END_REF] Semi-supervised spectral clustering Hybrid Bipartite Graph Function Generation step [START_REF] Mahmood | Semisupervised evolutionary ensembles for web video categorization[END_REF] Unsupervised clustering Genetic algorithm Consensus step [START_REF] Yu | Incremental semi-supervised clustering ensemble for high dimensional data clustering[END_REF] Constraint propagation Normalized cut Generation step and consensus step [START_REF] Xiao | Semi-supervised hierarchical clustering ensemble and its application[END_REF] Improved CHAMELEON Co-association based approach Generation step and consensus step [START_REF] Yu | Semi-supervised ensemble clustering based on selected constraint projection[END_REF] Constraint propagation Weighted normalized cut Generation step and consensus step

Binary membership matrix transformation

The representation of the clustering ensemble as a binary membership matrix aims at optimizing the efficiency of closed pattern mining from the ensemble. Each cluster of the base clusterings in the ensemble is then represented as a binary vector depicting the set of instances assigned to the cluster.

The binary membership matrix M for the support example in Table 2 is shown in Table 3. It represents relationships between instances and clusters in the clustering ensemble: Rows represent the finite set of instances and columns represent the finite set of clusters. A cell value 𝑀[𝑖, 𝑐] = 1 in the 𝑖 𝑡ℎ row and 𝑐 𝑡ℎ column denotes that instance 𝑖 belongs to cluster 𝑐, 𝑀[𝑖, 𝑐] = 0 otherwise.

Closed pattern extraction

Closed patterns in a binary matrix, also called Galois closed concepts, each consist of two components: Its extension that is a closed set of rows, i.e., instances, and its intension that is a closed set of columns, i.e., attributes, of the binary matrix. These closed sets are defined according to two functions:

• The 𝑓 (𝑅) function associates with a set of rows 𝑅 all the columns related to every row 𝑟 ∈ 𝑅 in the matrix.

• The 𝑔(𝐶) function associates with a set of columns 𝐶 all the rows related to every column 𝑐 ∈ 𝐶 in the matrix.

The couple of applications (𝑓 , 𝑔) is a Galois connection, and their compositions ℎ(𝐶) = 𝑓 (𝑔(𝐶)) and ℎ ′ (𝑅) = 𝑔(𝑓 (𝑅))

are Galois closure operators. A set of columns 𝐶 is closed if ℎ(𝐶) = 𝐶 and a set of rows 𝑅 is closed if ℎ ′ (𝑅) = 𝑅.
The ℎ(𝐶) and ℎ ′ (𝑅) operators generate extensions and intensions, respectively, of closed patterns when applied to the binary matrix. A closed pattern thus represents a maximal, according to inclusion relation, set of columns related to a maximal set of rows in the matrix, that is all the columns in the closed pattern intension and all the rows in its extension are related in the binary matrix.

For efficiently extracting all closed patterns from large data matrices, since the number of columns is usually much lower than the number of rows in the dataset, closed pattern extensions are identified in the matrix using the ℎ(𝐶) closure function. The corresponding intensions are implicitly generated during the calculation of the ℎ(𝐶) closure from the matrix [START_REF] Mondal | A new approach for association rule mining and bi-clustering using formal concept analysis[END_REF]. The search space of the algorithm is then the subset lattice of columns, where nodes represent column sets and edges between them represent inclusion relationships. In the subset lattice, each level contains all column sets of a given size, and the algorithm performs an iterative level-wise bottom-up traversal of the lattice, calculating the ℎ closure of column sets for a level at each iteration [START_REF] Yahia | Frequent closed itemset based algorithms: A thorough structural and analytical survey[END_REF]. The closure ℎ(𝐶) of a column set 𝐶 is computed by intersection of all columns 𝑐 ∈ 𝐶.

Closed patterns are extracted from the binary membership matrix using the apriori() function of the arules R package [START_REF] Hahsler | The arules R-package ecosystem: Analyzing interesting patterns from large transaction data sets[END_REF] with the "closed frequent itemsets" parameter. A closed pattern is then a pair consisting of a cluster set and an instance set, such that all instances in the instance set belong to all clusters in the cluster set. Each denotes a Table 3 Example binary membership matrix M. Each clusters 𝐶 𝑗 𝑖 of clustering result 𝛾 𝑖 in Table 2 is represented as a vertical binary vector indicating for each instance 𝑥 𝑘 , with 𝑘 between 1 and 9, if it was assigned to the cluster by a value of 1, or not assigned to the cluster by a value of 0.

Instance 𝐶 1 1 𝐶 2 1 𝐶 1 2 𝐶 2 2 𝐶 1 3 𝐶 2 3 𝐶 3 3 𝐶 1 4 𝐶 2 4 𝐶 3 4 𝐶 1 5 𝐶 2 5 𝐶 3 5 𝑥 1 1 0 1 0 1 0 0 1 0 0 1 0 0 𝑥 2 1 0 1 0 1 0 0 1 0 0 1 0 0 𝑥 3 1 0 1 0 1 0 0 1 0 0 1 0 0 𝑥 4 0 1 0 1 1 0 0 0 1 0 0 1 0 𝑥 5 0 1 0 1 1 0 0 0 1 0 0 1 0 𝑥 6 0 1 0 1 0 1 0 0 1 0 0 1 0 𝑥 7 0 1 0 1 0 1 0 0 1 0 0 1 0 𝑥 8 0 1 0 1 0 0 1 0 0 1 0 0 1 𝑥 9 0 1 0 1 0 0 1 0 0 1 0 0 1
{𝐶 1 3 } {𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 }
clustering pattern, that is an agreement between the base clusterings to group together the instances in the instance set.

A closed pattern can be observed as a maximal rectangle of '1' in the binary membership matrix, which denotes a pair consisting of a row set and a column set, such that for every row 𝑖 in the instance set and every column 𝑐 in the cluster set, we have 𝑀[𝑖, 𝑐] = 1. This closed pattern based approach enables the processing of datasets with a very large number of instances 𝑁, as in contrast to most other consensus clustering approaches, it does not require the processing of a co-association matrix of size 𝑁 2 but only of a membership matrix of size 𝑁.𝑀, where 𝑀 is the number of base clusters, with 𝑀 ≪ 𝑁, and regarding the demonstrated scalability properties of algorithms for extracting Galois closed sets [START_REF] Bertet | Lattices, closures systems and implication bases: A survey of structural aspects and algorithms[END_REF][START_REF] Mondal | A new approach for association rule mining and bi-clustering using formal concept analysis[END_REF][START_REF] Yahia | Frequent closed itemset based algorithms: A thorough structural and analytical survey[END_REF].

For further processings, the length of a closed pattern is defined as the length of its cluster set, that is the number of base clusterings that agreed to group its instance set. Its instance set can also be seen as a cluster. The extracted closed patterns for the support example are shown in Table 4.

Consensus function

The consensus function in [START_REF] Al-Najdi | A closed patterns-based approach to the consensus clustering problem[END_REF] generates a number 𝐿 𝑢𝑛𝑖𝑞𝑢𝑒 of consensus clustering solutions, where 𝐿 𝑢𝑛𝑖𝑞𝑢𝑒 is the number of unique values among the sizes |𝐿 𝑖 ] of closed pattern cluster sets. Concretely, we iterate a loop index 𝑙 𝑡 from the maximum value of |𝐿 𝑖 | to the minimum value of |𝐿 𝑖 | and generate one consensus solution 𝑆 𝑙 𝑡 per iteration. Each consensus solution 𝑆 𝑙 𝑡 is generated based on instance sets with |𝐿 𝑖 | = 𝑙 𝑡 and the consensus solution 𝑆 𝑙 𝑡-1 of the previous iteration. The first consensus solution is generated from instance sets of closed patterns with maximal length |𝐿 𝑚𝑎𝑥(𝑖) |. Since for each consensus solution the clusters must be disjoint, the consensus function determines to either merge or split two intersecting cluster sets 𝑋 and 𝑌 using Jaccard similarity [START_REF] Jaccard | The distribution of the flora in the alpine zone[END_REF]:

𝑠(𝑋, 𝑌 ) = 𝑚𝑎𝑥 ( |𝑋 ∩ 𝑌 | |𝑋| , |𝑋 ∩ 𝑌 | |𝑌 | )
If 𝑠(𝑋, 𝑌 ) is greater than the input merging threshold 𝑀𝑇 , usually set to 0.5 by default, then 𝑋 and 𝑌 are merged. Otherwise the larger cluster among 𝑋 and 𝑌 is split. The merging threshold 𝑀𝑇 is a parameter of the function that can be defined by the user to adapt the merging/splitting consensus creation process to the properties of the data in input. Experiments have shown that a value 𝑀𝑇 = 0.5 is the most adequate for most benchmark datasets, originating from different application contexts and with different data space structure properties, that have been tested. The iterative consensus process repeats until there is no intersection among clusters. The pseudo-code of the consensus function of the MultiCons approach is detailed in Algorithm 1.

ALGORITHM 1

Consensus process of the MultiCons approach. The execution of the closed pattern based consensus function for the support example is shown in Figure 3. Each iterations consider closed patterns in decreasing order of their cluster set size |𝐿 𝑖 |. The iteration generates a consensus solution according to the clusters generated during the previous iteration and the considered closed patterns. The first consensus clustering solution consists of clusters corresponding to the maximal number of agreements between the base clusterings, that is the closed patterns with the largest cluster set size. For each iteration of the loop, the cluster sets 𝑋 and 𝑌 considered, i.e., among the previously generated clusters and considered closed patterns, that are intersecting are underlined in the execution trace.

Hierarchical graphical representation

The generated consensus solutions are presented to the user in a hierarchical graphical representation, as shown in Figure 4 for the support example. Each level represents a generated consensus solution corresponding to a given minimal number of agreements between the base clusterings, that is the cluster set size of closed patterns considered during the iteration that generated the solution. A consensus solution that is generated by several successive iterations of the process is depicted only once in the graphical representation, with the associated number of times it was generated (not shown in Figure 4) as it denotes a higher stability of this solution, and thus a higher robustness of its constituting clusters.

A recommended consensus clustering solution is suggested to the user. This solution is selected based on both its highest similarity with the clustering ensemble and its stability in the consensus creation process. However, different clustering solutions can be chosen as the final result depending on requirements and constraints of the application performed. The hierarchical graphical representation can also provide important information for choosing a clustering solution regarding its stability and clusters that are present in several successive clustering solutions.

Properties of the approach

The major advantages of MultiCons over other consensus clustering methods are about its easily readable hierarchical graphical representation, allowing the user to analyze the consensus building process and identify clusters of particular importance, and its ability to discover the number of intrinsic clusters in the dataset data space without explicitly specifying the number of generated clusters 𝑘. However, due to the fact that the consensus process needs to be repeated until all clusters are disjoint, evaluating the computational complexity of MultiCons is difficult, since it significantly relies on how many times the process is repeated. Nevertheless, considerations about the computational complexity of the Semi-MultiCons approach are provided in section 4.1, considering the algorithmic optimization introduced in the clustering pattern processing with the novel Semi-MultiCons semi-supervised consensus function.

Semi-MultiCons Approach

In the Semi-MultiCons approach, the implementation of the consensus function is optimized compared with the MultiCons approach. This optimization reduces the number of loops of the consensus cluster creation process from closed patterns. Novel constraints-based consensus function and selection method of the recommended final clustering solution are also introduced. These new algorithmic processes add the use of supervision information, represented as must-link and cannot-link constraints, for optimizing the relevance of the recommended consensus solution regarding available prior knowledge.

The workflow of the Semi-MultiCons approach is shown in Figure 5. The initial steps of Semi-MultiCons, that is the creation of the clustering ensemble, its transformation into a binary membership matrix and the extraction of closed patterns, are identical to MultiCons initial steps. These steps define the search space for the consensus function and thus, the generation of the consensus clustering hierarchical graphical representation.

Implementation optimization

For each iteration 𝑙 𝑡 of the consensus process of Mul-tiCons, the instance sets of closed patterns with |𝐿 𝑖 | = 𝑙 𝑡 are first combined with clusters of the previous consensus solution 𝑆 𝑙 𝑡-1 . These two types of clustering patterns are compared during the 𝑙 𝑡 iteration to create the 𝑆 𝑡 consensus clustering solution. For this, each pair of instance sets and consensus clusters are enumerated until no intersection is detected. This results in inaccessible computational complexity evaluation due to the unknown number of loops required. However, since all clusters in 𝑆 𝑙 𝑡-1 are already disjoint, this overlapping check is not required for the Semi-MultiCons approach.

Size 𝑙 𝑡

Set Assume that on average a closed pattern 𝐶 𝑖 contains 𝑛 𝑐 instances and a cluster in 𝑆 𝑙 𝑡 contains 𝑛 𝑠 instances. The average number of loops performed is then 𝑁∕𝑛 𝑐 × 𝑁∕𝑛 𝑠 . Intersection check and constraint check needs 𝑂(𝑘×𝑛 𝑐 ×𝑛 𝑠 ), resulting in an estimated complexity of 𝑂(𝑘𝑁 2 ) on average for the Semi-MultiCons consensus process.

Constraint-based consensus generation

The novel Semi-MultiCons constraints-based consensus function makes use of supervision information represented in the form of must-link constraints and cannot-link constraints. The objective is to define a normalized score that evaluates how many constraints are satisfied or violated if the merge or split operation between clusters is performed.

Let's consider the following 𝑔() function that defines a value representing existing constraints between two instance 𝑎 and 𝑏 of the dataset. 𝑔(𝑎, 𝑏) = 1 and 𝑔(𝑎, 𝑏) = -1 denotes respectively that instance 𝑎 and instance 𝑏 have a must-link or cannot-link constraint. Otherwise, if no constraint exists between 𝑎 and 𝑏, we have 𝑔(𝑎, 𝑏) = 0. Then, the score of

𝑆 𝑚𝑒𝑟𝑔𝑒 = ∑ 𝑎∈𝑋⧵(𝑋∩𝑌 ) ∑ 𝑏∈𝑌 ⧵(𝑋∩𝑌 ) 𝑔(𝑎, 𝑏) |(𝑋 ∪ 𝑌 ) ⧵ (𝑋 ∩ 𝑌 )| (1)
It represents how many must-link constraints per instance are satisfied if 𝑋 and 𝑌 are merged. Similarly, the score of split 𝑋 ∩ 𝑌 from 𝑋 and of split 𝑋 ∩ 𝑌 from 𝑌 are defined as follows:

𝑆 𝑠𝑝𝑙𝑖𝑡𝑋 = - ∑ 𝑎∈𝑋⧵(𝑋∩𝑌 ) ∑ 𝑏∈𝑋∩𝑌 𝑔(𝑎, 𝑏) |𝑋| ( 2
)
𝑆 𝑠𝑝𝑙𝑖𝑡𝑌 = - ∑ 𝑎∈𝑌 ⧵(𝑋∩𝑌 ) ∑ 𝑏∈𝑋∩𝑌 𝑔(𝑎, 𝑏) |𝑌 | (3)
If the three scores all equal to 0, it means that no supervision information on 𝑋 and 𝑌 is available and the 𝑠(𝑋, 𝑌 ) measure, as defined in Section 3.2.4, will be used. Otherwise, we will select the highest score to merge or split the clusters to comply with the objective to meet as many constraints as possible.

To illustrate the effect of the use of supervision information in the consensus generation process, let's consider the support example consisting of closed patterns in Table 4 with an additional cannot-link constraint between 𝑥 4 and 𝑥 8 . The resulting constraint-based consensus process of Semi-MultiCons is shown in Figure 6. For simplification of the presentation, the iterations before 𝑙 𝑡 = 2, i.e., for 𝑙 𝑡 = 5 and 𝑙 𝑡 = 4, that are not impacted by the additional cannot-link constraint are omitted since their results are the same as for the Multi-Cons approach.

Selection strategy

The Semi-MultiCons result for the support example, which execution is depicted in Table 6, is presented in the hierarchical graphical representation shown in Figure 7.

Duplicated consensus clustering solution are generated for iterations 𝑙 𝑡 = 4 and 𝑙 𝑡 = 2. This common solution is then represented only once in the final hierarchical graphical representation with its associated count of how many times this consensus clustering occurs. This count represents the frequency of the consensus solution among all possible solutions, denoting its stability in the consensus generation

No intersection, generate 𝑆 1

End process, and thus the robustness of its constituting clusters regarding the search space in input. In the final hierarchical graphical representation for the support example shown in Figure 7, the frequencies of each level, from the bottom to the top of the hierarchy, are respectively 1, 2 and 1. The selection of the final recommended consensus solution to the user is based on both the number of satisfied must-link constraints and violated cannot-link constraints, and on the stability of the solution in the result and its similarity with the clustering ensemble. In the support example in Figure 7, the consensus clustering solution {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }} that satisfies the cannot-link constraint between 𝑥 4 and 𝑥 8 and has a frequency equals to 2 is selected. This solution is the one that satisfies the largest number of constraints and has the highest frequency, as well as the highest similarity with the clustering ensemble, among the generated consensus clustering solutions.

𝑆 1 = {{𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }}

Experimental results

An important difficulty in the application of most clustering and consensus clustering methods is the setting of the 𝑘 parameter, that defines the number of clusters that will be generated. Indeed, an incorrect value for the 𝑘 parameter may lead to a significant decrease in the relevance of the clustering result. Another difficulty, related to semi-supervised clustering usage of supervision information, is that integrating constraints sometimes lead to worse performance than using no constraints, which is a well-known potential negative effect reported in the literature [START_REF] Davidson | Measuring constraintset utility for partitional clustering algorithms[END_REF][START_REF] Wagstaff | When is constrained clustering beneficial, and why?[END_REF][START_REF] Zhang | A framework for deep constrained clustering -Algorithms and advances[END_REF]. During the experimental evaluation of the Semi-MultiCons approach, we address the following issues:

• Comparison between the inferred 𝑘 value provided by Semi-MultiCons with the ground truth number of classes for classical benchmark datasets used to compare semi-supervised approaches.

• Comparison of performance between MultiCons, Semi-MultiCons and other semi-supervised clustering and/or consensus clustering approaches.

• Evaluation of the potential negative effect of constraints integration in the Semi-MultiCons process and comparison with other approaches.

• Study about scalability and complexity of the Semi-MultiCons approach for processing very large datasets.

The experimental settings, presented hereafter, were defined to address more specifically these central questions.

As detailed hereafter, the MPC-Kmeans single semisupervised clustering approach is used for both comparison with Semi-MultiCons semi-supervised consensus clustering approach, and to generate base clusterings in the clustering ensemble when comparing Semi-MultiCons with other semi-supervised consensus clustering approaches. The MPC-Kmeans approach [START_REF] Bilenko | Integrating constraints and metric learning in semi-supervised clustering[END_REF] was selected since, to the best of our knowledge, it was reported in the literature as one of the most efficient single semi-supervised clustering approaches regarding result relevance. MPC-Kmeans is an hybrid method that combines constraint-based and distancebased methods. In [START_REF] Covões | A study of K-Meansbased algorithms for constrained clustering[END_REF], experiments reported in Table 3, representing NMI index score for UCI Machine Learning Repository datasets, show that MPC-Kmeans is actually the best performer among the CVQE, LCVQE, Kmeans and MPC-Kmeans algorithms, regardless execution times. Experimental results in [START_REF] Bilenko | Integrating constraints and metric learning in semi-supervised clustering[END_REF] also show that MPC-Kmeans outperforms the PC-Kmeans and M-Kmeans semi-supervised clustering algorithms, and recently, in [START_REF] Zhang | A framework for deep constrained clustering -Algorithms and advances[END_REF], MPC-Kmeans is used as baseline algorithm, and it is shown that it outperforms the Flexible CSP and COP-Kmeans algorithms.

As stated before for the MultiCons approach, ensemble diversity, that is the diversity among the base clusterings which constitute the search space for consensus clusters in ensemble methods, is a very important factor for the relevance of the consensus result. This is also the case for the clustering ensemble in the context of operational applications performed with the Semi-MultiCons semi-supervised approach. However, in the context of this article, only the MPC-Kmeans algorithm was used to create ensemble members since the objective to assess and compare the results of the tested approaches with regards to the impact of pairwise constraints, and to ensure that no other factors related to the properties of the data space defined by the dataset and the single clustering algorithms used for creating base clusterings impact the results.

Experiments were conducted on a Dell server with 32 Intel Xeon 8 cores CPU E5-4620 2.20GHz processors and 529 GB main memory, running under CentOS operating system, and RAID 0 hard disk data storage virtualization technology for input/output performance optimization. An open source implementation in R of the Semi-MultiCons approach is available at https://github.com/lazzyCloud/semi-multicons to facilitate the replication of the experiments.

Experimental datasets

Four classical benchmark datasets from the UCI Machine Learning Repository [START_REF] Dua | UCI Machine Learning Repository, University of California[END_REF], namely the Iris, Wine, Zoo and Ecoli datasets, are used to evaluate the Semi-MultiCons semi-supervised ensemble clustering performance using the standard Normalized Mutual Information (NMI) [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF], clustering accuracy (ACC) [START_REF] Xu | Document clustering based on non-negative matrix factorization[END_REF] and Purity [START_REF] Schütze | Introduction to Information Retrieval[END_REF] indexes. Besides these datasets, the MNIST dataset [START_REF] Lecun | MNIST Handwritten Digit Database[END_REF], that is very large regarding both its number of attributes and its number of instances, is used to evaluate the scalability and complexity of the Semi-MultiCons approach.

The potential negative effect of constraints was not studied for the MNIST dataset due to the limitations of the MPC-Kmeans approach for such a large dataset. For the negative effect experiment, repeated trials are necessary in order to get rid of potential randomness introduced by Some basic facts about these datasets are stated in Table 5. Note that the Zoo and Ecoli datasets present an imbalanced class issue, with classes represented by very few instances. This can result in a number of intrinsic clusters in their data space corresponding to the number of major classes in the dataset, and thus, fewer than the total number of classes in the dataset. Both these five well-known benchmark datasets and the Normalized Mutual Information index measure were selected as they are the most popular in the domain, thus enabling to compare results with most unsupervised and semi-supervised clustering algorithms proposed in the literature.

Constraint generation

For all experiments, the must-link and cannot-link constraints are generated randomly from the classes of instances in the dataset. A pair of instances is added to the set of must-link constraints if these randomly chosen instances belong to the same. Otherwise, this pair of instances is added to the set of cannot-link constraints. This process is repeated until the number of must-link and cannot-link pairwise constraints required for the experiment is satisfied. For each experiment, all compared algorithms use exactly the same set of constraints.

Algorithmic approaches

Diverse criteria were considered for determining the best approaches to compare with Semi-MultiCons. These criteria consider in first place the quality of the clustering results, the efficiency and scalability of the approach regarding data size, the applicability of the approach to dataset containing heterogeneous and missing data, and the approach robustness to noise and outliers in the data. Considering theoretical and experimental results reported in the literature, and the availability and the results of implementation tests, the following semi-supervised clustering algorithmic approaches were selected: Third model (GV3) from [START_REF] Gordon | Fuzzy partition models for fitting a set of partitions[END_REF], soft least Input parameters. For each of the ve datasets, the range of values for the 𝑘 parameter dening the number of clusters extracted in the base clusterings are shown.

Dataset Range of values for 𝑘 parameter

Iris [2 -6] Wine [2 -6] Zoo [5 -9] Ecoli [4 -8] MNIST [8 -12] squares Euclidean consensus (DWH) [START_REF] Dimitriadou | A combination scheme for fuzzy clustering[END_REF], hard Euclidean consensus (HE) [START_REF] Hornik | Hard and soft Euclidean consensus partitions[END_REF] and metric pairwise constrained Kmeans (MPC-Kmeans) [START_REF] Bilenko | Integrating constraints and metric learning in semi-supervised clustering[END_REF]. Implementations of these approaches can be found in R packages clue [START_REF] Hornik | A CLUE for CLUster Ensembles[END_REF] and conclust [START_REF] Tran | conclust: Pairwise constraints clustering[END_REF]. The original MultiCons method [START_REF] Al-Najdi | Multiple consensuses clustering by iterative merging/splitting of clustering patterns[END_REF] was also used in the experiments to demonstrate the improvement offered by the Semi-MultiCons approach in the context of semi-supervised clustering.

Input parameters

For consensus clustering, algorithmic configurations defining the base clusterings are necessary to generate ensemble members. The range of values for the number of clusters 𝑘 parameter used for the ensemble member generation are shown in Table 6. In operational applications of clustering, the number of clusters that are inherent to the data space properties is unknown, and a general idea is to estimate it based on a small sample set of data. However, this estimation for the 𝑘 parameter can deviate from the number of intrinsic clusters. We therefore choose a range of values for the 𝑘 parameter according to the approximate the number of intrinsic clusters in the dataset. The MPC-Kmeans algorithm was chosen as baseline for base clusterings to show the benefits of consensus process based on semi-supervised clustering algorithm.

Evaluation indexes

Normalized Mutual Information (NMI) [START_REF] Kvålseth | On normalized mutual information: Measure derivations and properties[END_REF], clustering accuracy (ACC) [START_REF] Xu | Document clustering based on non-negative matrix factorization[END_REF] and Purity [START_REF] Schütze | Introduction to Information Retrieval[END_REF] indexes are used to evaluate the quality of the resulting clusterings. For the Semi-MultiCons approach, while multiple consensus clustering solutions are generated, only the recommended solution is considered as the output. In the following experimental results, the evaluation index score and the inferred number of clusters 𝑘 of the recommended solution are represented as 𝑆 𝑟 , that is the average evaluation index value obtained for Semi-MultiCons, and 𝑘 𝑟 , that is the average number of clusters generated for Semi-MultiCons for the repeated executions of each experiment. For other consensus clustering approaches that require 𝑘 as an input parameter, the number of cluster 𝑘 𝑏 that reaches their best performance is used. To avoid bias in comparison, we also demonstrate the level of Semi-MultiCons which number of clusters is equal to 𝑘 𝑏 as reference. Essentially, a better performance means a greater evaluation index value and an inferred 𝑘 𝑟 that is closer to the number of classes in the dataset.

Experiment settings

The number of constraints ranges from 0 to 150 for UCI Machine Learning Repository datasets. For each number of constraints, 30 different constraint sets were generated with 10 times repeated trials for each execution. For the MNIST dataset, due to the size of the dataset and the computational complexity of the MPC-Kmeans algorithm, the number of constraints was fixed to 6 000 and each consensus approach was run 10 times. Semi-MultiCons and other methods are guaranteed to access exactly the same constraints for each execution.

Comparison between inferred and real number of classes

The average inferred numbers of clusters 𝑘 𝑟 by Semi-MultiCons over all trials for each dataset are listed in Table 7. 𝑘 𝑏 represents the number of clusters defined by the 𝑘 parameter in input for which the MPC-Kmeans algorithm achieves its best performance. Detailed results about MPC-Kmeans and Semi-MultiCons performances are given in Section 5.2. The real, i.e., ground truth, number of classes and the number of major classes in the dataset are also given as reference. The major classes refers to the class which contains at least 5% number of instances. As stated before, the Zoo and Ecoli datasets contain classes with only few instances and have therefore a number of intrinsic clusters that is lower than their total number of classes. We can thus observe that MPC-Kmeans does not always achieve its best performance when its 𝑘 parameter value is equal to ground truth number of classes. The MPC-Kmeans approach trends to find large, balanced clusters in data, while the inferred 𝑘 𝑟 provided by Semi-MultiCons is much closer to the ground truth number of classes.

For the MNIST dataset, the largest 𝑘 in input gives the best MPC-Kmeans performance. Semi-MultiCons also infers a large 𝑘 𝑟 , implying that the number of clusters in the data space may be larger than the number of classes in the dataset. Actually, several subspaces in the data space defined by the input dataset, that is intrinsic clusters in this data space, can correspond to the same class. This is the case if the class corresponds to different subgroups of instances, which means the class can be characterized by several distinct groups of instances in the data space. On the contrary, if some classes cannot be fully distinguished using the information provided by the dataset, several classes may belong to the same subspace of the data space, i.e., correspond to a unique intrinsic group of instances in the data space, and then the number of underlying clusters in the data space may be lower than the number of classes in the dataset. The multi-level structure of clusters in output of Semi-MultiCons can provide information about this property, by showing the successive merging and splitting operations performed, and help to automatically discover the appropriate number of clusters 𝑘 for the dataset, that is to identify the most relevant Comparison between the inferred and ground truth numbers of classes. For each of the ve datasets, the range of values for the 𝑘 parameter, the average number of clusters 𝑘 𝑟 inferred by Semi-MultiCons, the number of clusters 𝑘 𝑏 for MPC-Kmeans to generate the best base clustering solution, the total number of classes and the number of major classes in the dataset are shown.

Dataset Input 𝑘 Average 𝑘 𝑟 𝑘 𝑏 Number of classes Number of major classes Iris

Comparison with single semi-supervised clustering approaches

In this experiment, the results of the Semi-MultiCons semi-supervised consensus clustering approach and the MPC-Kmeans single clustering approach are compared in terms of the relevance of the consensus solution generated. As stated before, the NMI, ACC and Purity indexes are used to evaluate and compare the relevance of the generated clustering solutions. The number of pairwise constraints used was varied between 0 and 160 to evaluate their impact on the clustering result. The results of Semi-MultiCons and MPC-Kmeans for the Iris, Wine, Zoo and Ecoli datasets are presented in Figure 8. The best performance obtained for all trials of each execution is shown. We could note that for some experiments, the number of clusters obtained may be different from the number of classes in the dataset, due to the potential existence of several clusters defining a class in the data space as discussed in Section 5.1.

The three curves depicting the evaluation of MPC-Kmeans results correspond each to a different value for the input parameter 𝑘. The blue curve corresponds to the 𝑘 𝑏 value number of clusters, that generates the best result among all tested values in 6. The red curve corresponds to the 𝑘 𝑏 -1 value, and the green curve corresponds to the 𝑘 𝑏 + 1 value. The yellow curve represents the 𝑆 𝑟 evaluation in the situation where the number of classes is unknown for Semi-MultiCons, that is the consensus clustering evaluated is the one automatically selected by the approach in the output hierarchy. The black curve represents the 𝑆 𝑟 evaluation when the number of classes 𝑘 𝑏 is given as input, that is the consensus clustering evaluated is the one with a number of clusters equal to 𝑘 𝑏 in the output hierarchy. We can clearly see from the curves that the performance increases with the number of constraints, proving that constraints are useful for improving the quality of the clustering.

Considering the MPC-Kmeans approach, we observe that its performance strongly depends on the value of its input parameter 𝑘. If this value does not fit well with the number of clusters in the dataset, MPC-Kmeans fails to give good performance. Also, for imbalanced Zoo and Ecoli dataset, MPC-Kmeans achieves its best performance when 𝑘 does not correspond to the number of classes, showing the difficulties MPC-Kmeans faces when the number of clusters is large. In contrast, the Semi-MultiCons approach is able to give a comparable or better performance when the number of clusters 𝑘 is given as input, as shown by the black curves, for all three evaluation indexes. Moreover, without knowing 𝑘, Semi-MultiCons is still able to give good performance, close to those obtained with known 𝑘, as shown by the yellow curves, especially when 𝑘 is large.

Comparison with semi-supervised consensus clustering approaches

This experiment compares the results of the Semi-Multi-Cons, the MultiCons and other baseline semi-supervised consensus clustering approaches in terms of relevance of the consensus solution generated. Experimental results for the Semi-MultiCons, MultiCons, DWH, GV3 and HE approaches for the Iris, Wine, Zoo and Ecoli datasets are presented in Figure 9. The height of the curves represents the value of the three evaluation indexes for the clustering generated when varying the number of pairwise constraints between 0 and 160 as shown on the horizontal axis. As in all the subsequent experiments, all the tested semi-supervised approaches use exactly the same information in input, that is the set of base clusterings in the clustering ensemble and the set of pairwise constraints between instances.

Clearly, Semi-MultiCons reaches comparable or better performance when the number of clusters 𝑘 𝑏 is used to choose the final clustering result in the output hierarchy, for all three evaluation indexes. It also outperforms the original MultiCons approach, demonstrating the positive effect of the proposed constraint-based consensus process.

Particularly, the original MultiCons approach outperforms Semi-MultiCons with known 𝑘 on Purity evaluation index for Zoo dataset. However, high Purity index can be easily achieved when the number of clusters is large. Combining the results for the NMI and ACC evaluation indexes, the Semi-MultiCons approach still performs better than the original MultiCons approach. We can note that even without explicitly knowing the 𝑘 𝑏 value, Semi-MultiCons is able to generate a solution reaching a good performance, overall close to the best solution. For the three other approaches, results are similar for the four datasets: The best solutions are generated by the GV3 algorithm, the lower performer solutions are generated by the DWH algorithm, and the HE algorithm generates solutions with an evaluation that is intermediate between those of GV3 and DWH algorithms. During this experiment, the GV3 algorithm is the only approach with performances that are comparable with Semi-MultiCons. However, Semi-MultiCons has better properties than GV3 regarding efficiency in time and space, i.e., number of operations performed and memory usage, as shown by the scalability and complexity analysis presented in the following sections.

Analysis about negative effect

A potential negative effect issue of semi-supervised clustering methods was largely reported in the literature [START_REF] Davidson | Measuring constraintset utility for partitional clustering algorithms[END_REF][START_REF] Wagstaff | When is constrained clustering beneficial, and why?[END_REF][START_REF] Zhang | A framework for deep constrained clustering -Algorithms and advances[END_REF]. This issue relates to the use of pairwise constraints as supervision information in the clustering process that sometimes leads to performance, in terms of quality of the clustering result, that are worse than using no constraint. However, most semi-supervised consensus clustering algorithms were only evaluated by average performance, thus not highlighting this potential issue.

The importance of the negative effect of using constraints is evaluated by the fraction of times that unconstrained clustering produces better results than constrained clustering. For comparison of results, the unconstrained version is defined by the performance of the K-means approach, i.e., equivalent to using no constraints for performing unsupervised MPC-Kmeans, with an input parameter 𝑘 equals to the optimal number of clusters 𝑘 𝑏 . The percentage values shown represent the proportion of experiments where the clustering solution generated by the constrained algorithm underperforms the result of K-means approach with parameter 𝑘 equals to 𝑘 𝑏 .

The results of the experiment are shown in Figure 10. The horizontal axis shows the number of pairwise constraints used during the execution and the vertical axis shows the fraction of times that the algorithm produced worse performance than the baseline K-means clustering with 𝑘 𝑏 as input parameter. The black curve represents the evaluation of the Semi-MultiCons consensus solution which number of clusters is equal to the optimal number of clusters 𝑘 𝑏 . The yellow curve represents the negative effect ratio of 𝑆 𝑟 evaluation in the situation where the number of classes is unknown for Semi-MultiCons. The brown curve represents the negative effect ratio of the MultiCons approach. The four remaining curves represent the evaluation of the semisupervised results of the MPC-Kmeans, GV3, HE and DWH algorithms with a 𝑘 input parameter equals to 𝑘 𝑏 .

We can see from the results in the figure that for all algorithms, the negative effect decreases when the number of constraints increases, implying that extending the size of the constraint set can be a possible solution to fight against the negative effect. Under the same condition, where the optimal number of clusters is provided, Semi-MultiCons highly reduces the occurrence of negative effect, compared to other approaches, for most datasets as illustrated by the black curve. When the optimal number of clusters is not provided, Semi-MultiCons alleviates negative effect as well, especially for datasets where the number of clusters is large.

For the Iris dataset, GV3 and Semi-MultiCons even reach 0% negative effect ratio when size of constraint set is large.

A specific feature of the Iris dataset, compared to other benchmark datasets used, is that this dataset is perfectly balanced regarding the number of instances in each class.

Analysis about convergence

Since the proposed constraint-based consensus process is a dynamic process with splitting/merging operations, we evaluate the convergence of Semi-MultiCons in this experiment, to illustrate the trend of the cost regards to the number of iterations. The objective of the novel constraints-based consensus function, as explained in 4.2, is to meet as many constraints as possible. The cost is hereby defined as the percentage of unsatisfied pairwise constraints. It is calculated for each of the successive levels of the hierarchy generated by Semi-MultiCons, from bottom to top. These successive levels from bottom to top eventually correspond the number of iterations, as each level represents a consensus solution generated based on the previous level and the considered closed patterns, as stated in Figure 3 and Figure 6.

Results presented in Figure 11 show that for all the four datasets, the cost moves continuously towards a minima, with a decreasing trend as the number of iteration increases, proving the convergence of the Semi-MultiCons approach.

Performance on the MNIST dataset

This experiment aims to compare the performances of the different semi-supervised clustering approaches in terms of execution times and applicability regarding memory usage. The MNIST benchmark dataset, containing 70 000 instances, is used for these performance tests. The number of pairwise constraints is fixed to 6 000 and each algorithm is run 10 times.

Results for the compared approaches are given in Table 8. These results present both the average quality of the clustering in output and execution times for each algorithm. Since the GV3 algorithm runs out of memory for such a large dataset, that exceeds its capacity regarding memory usage, its performances are not presented. Note that for this experiment, the optimal number of clusters is not provided as parameter 𝑘 to Semi-MultiCons. We can see that among the five compared approaches, the DWH and HE approaches have the lowest execution times. However, as observed before, their performance in terms of relevance of the clustering result is clearly lower compared to Semi-MultiCons and GV3 for datasets from the UCI Machine Learning Repository. The MPC-Kmeans approach requires very important execution times compared to all other approaches. Overall, we can find that the Semi-MultiCons approach is able to both handle large and challenging datasets, and provide a relevant clustering result even when the optimal number of clusters or classes is unknown. The t-Distributed Stochastic Neighbor Embedding (t-SNE) visualization [START_REF] Van Der Maaten | Visualizing data using t-sne[END_REF] of the clustering results for the compared approaches are demonstrated in Figure 12. The implementation in Scikit-learn Python package [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] was used, with initialization method set to PCA [START_REF] Smith | A Tutorial on Principal Components Analysis[END_REF] and parameter perplexity set to 40, that is the same initialization setting as [START_REF] Van Der Maaten | Visualizing data using t-sne[END_REF]. The t-SNE visualization is trained on the entire MNIST dataset with 70 000 instances. However, to better visualize the clustering results, only 1 000 randomly sampled instances are displayed. For reasons of clarity and readability, the minority clusters which contain less than 1.5% percentage of the total number of instances in the MNIST dataset, are represented as one cluster in black. We can observe that in the latent space, the digits 4 and 9 are difficult to be recognized and all the five approaches fail to separate them. Compared to other approaches, the Semi-MultiCons has better performance on digits 5 and 8 as it is the only approach that can partition them into two clusters. The HE and DWH approaches have the worst performance, since they under-perform the other approaches in terms of the digits 2 and 3. The t-SNE visualization gives a straightforward and complementary illustration to better understand and evaluate the clustering results presented in Table 8.

Computational complexity study

This study aims to evaluate the efficiency of the Semi-MultiCons approach and compare it with MultiCons and other semi-supervised clustering approaches. During the first experiment of this study, the execution times of Semi-MultiCons, MultiCons and the four other semi-supervised clustering approaches used in the experiments are compared. Experimental results are presented in Figure 13. Note that for the consensus-based approaches, the execution time of the ensemble member generation is not considered. The curves depict the execution times of the six approaches while varying the number of pairwise constraints used during the execution. We can see that DWH and HE are the most efficient approaches for the four datasets of the UCI Machine Learning Repository. They have close execution times and their curves often overlap each other in the figure. We can also observe that MultiCons and Semi-MultiCons execution times are systematically lower than those of MPC-Kmeans and GV3 for all the four datasets. The Semi-MultiCons execution times are slightly higher than those of MultiCons due to the fact that it integrates constraints during consensus process.

During the second experiment of this study, Semi-Multi-Cons was applied to different samples of the MNIST dataset. Seven samples, containing from 10 000 instances for the smallest to 70 000 instances for the largest, were generated from the MNIST dataset. The number of pairwise constraints is fixed to 6 000, and 10 trials are performed for each execution. Figure 14 presents the average execution times for each of the seven executions. The curve shows that the scalability property of Semi-MultiCons is linear in the number of instances for generating the output consensus clustering hierarchy. In Section 4.1, the complexity of Semi-MultiCons was estimated as proportional to the squared number of instances 𝑁 in the dataset. The results show that the time complexity is close to this estimate of the computational complexity of Semi-MultiCons.

Conclusion

In this article, we present a new semi-supervised consensus clustering approach named Semi-MultiCons. During the development of this approach, we optimized the implementation of the initial MultiCons approach for multiple consensus clustering [START_REF] Al-Najdi | Multiple consensuses clustering by iterative merging/splitting of clustering patterns[END_REF], and we designed a new iterative constraint-based consensus function to integrate supervision information into the consensus clustering process. The experiments conducted on four reference benchmark datasets from the UCI Machine Learning Repository and on the MNIST large dataset have led to the following conclusions:

• The prior knowledge, i.e., supervision information, represented as pairwise constraints between instances is useful for improving the quality of clustering.

• Semi-MultiCons manages to infer the correct number of clusters in output, while processing base clustering ensemble members with different numbers of clusters.

• Semi-MultiCons is able to generate a clustering solution with comparable or better relevance compared to single semi-supervised clustering and consensus clustering approaches without explicitly knowing the optimal number of clusters 𝑘.

• Semi-MultiCons is able to process datasets with large number of instances contrarily to several other approaches, and has a linear scalability in the number of dataset instances.

• Semi-MultiCons has the ability to solve operational clustering problems encountered when data is imbalanced, the number of clusters is large and/or the number of clusters is ambiguous or unknown.

In the general case of operational applications, where the intrinsic number of clusters in the data space is unknown, the Semi-MultiCons approach can be used as a pre-processing step to contribute to the discovery of the appropriate number of clusters, as well as a consensus clustering method to achieve better clustering quality.

Although Semi-MultiCons is more time consuming than the most efficient baseline semi-supervised consensus clustering approaches like HE and DWH, its execution times remain acceptable even for large and complex datasets such as the MNIST benchmark dataset. Also, the hierarchical output of Semi-MultiCons can offer significant improvements, compared to such approaches which generate a single clustering solution, regarding the application performed. For example, it can provide information to better understand the properties of the data space through the visualisation of successive mergers of sets of instances represented in the ConsTree. Future plans to improve the efficiency of the approach in terms of time complexity encompass the design of new algorithmic solutions to:

• Extract clustering patterns, such as generated by the MultiCons approach, directly from the binary membership matrix, by merging the iterative processes of closed pattern extraction and consensus cluster generation by the consensus function.

• Integrate supervised information represented as pairwise constraints between instances in the closed pattern mining phase from the binary membership matrix, by the definition of a new constraints-based closure function.

• Extract constraints-based clustering patterns, such as generated by the Semi-MultiCons approach, directly from the binary membership matrix with the new constraints-based closure function.

Among perspectives of further work, the first is the investigation of the effect of noise on performances of the approach. The second is the utilization of the Semi-Multi-Cons consensus function as a loss function, as the proposed constraints-based consensus function demonstrates an appropriate convergence, to apply it in a deep learning pipeline architecture [START_REF] El-Amir | A tour through the deep learning pipeline[END_REF]. As a matter of fact, several deep learning approaches recently reported in the literature, such as for example [START_REF] Zhang | A framework for deep constrained clustering -Algorithms and advances[END_REF], integrate pairwise constraints in the objective function of deep neural networks.

Figure 1 :

 1 Figure 1: Overview of consensus clustering procedure. Dierent clustering algorithmic congurations are applied to the input dataset for creating the clustering ensemble to which is applied the consensus function for generating the nal clustering result.

Figure 2 :

 2 Figure 2: Overview of semi-supervised consensus clustering procedure. supervision information is used as prior knowledge either or both during the clustering ensemble creation and the generation of the nal clustering result by the consensus function.

Figure 3 :

 3 Figure 3: Example MultiCons consensus process from closed patterns in Table 4. Closed patterns are processed in decreasing order of their cluster set size |𝑙 𝑖 |, and the rst line of each row shows the patterns considered during the 𝑙 𝑡 cluster set size iteration. The merging and splitting operations performed during each iteration, depending on underlined intersecting subsets of instances between created clusters and closed patterns, are then depicted. The resulting consensus clustering 𝑆 𝑙 𝑡 of iteration 𝑙 𝑡 is shown on the last line of the row. The last row shows the 𝑆 1 consensus clustering at the top of the hierarchical graphical representation in Figure 4.

Figure 4 :

 4 Figure 4: Hierarchical consensus clustering of the MultiCons approach. Each level in the hierarchical representation depicts a clustering of the dataset. Nodes represent instance sets of clusters and edges represent inclusion relationships between clusters, showing the successive groupings of instances corresponding each to a dierent number of agreements between clusterings of the base clustering ensemble.

Figure 5 : 2

 52 Figure 5: Workow of the Semi-MultiCons approach. The dataset in input is processed by dierent clustering algorithmic congurations to create the clustering ensemble. The ensemble is transformed into a binary membership matrix from which closed patterns are extracted. These closed patterns are then processed by the Semi-MultiCons consensus function according to supervision information to generate the hierarchical consensus clustering result in which the nal recommended clustering is identied.

Figure 6 :

 6 Figure 6: Example Semi-MultiCons constraint-based consensus process. Closed patterns are processed in decreasing order of their Cluster set size |𝑙 𝑖 |. Iterations for cluster set size 𝑙 𝑡 = 5 and 4 are identical to the corresponding iterations in Figure 3. For 𝑙 𝑡 = 2 and 1, the rst line of the corresponding row shows the cluster sets of closed patterns considered during the iteration. The merging and splitting operations performed during the iteration, depending on underlined intersecting subsets of instances between created clusters and closed patterns, and the supervision information constraints, are then depicted. The resulting consensus clustering 𝑆 2 and 𝑆 1 are shown on the last line of the rows. The last row shows the 𝑆 1 consensus clustering at the top of the hierarchical graphical representation in Figure 7.

Figure 7 :

 7 Figure 7: Hierarchical consensus clustering of the Semi-Multi-Cons approach. The three consensus clusterings generated from closed patterns and constraints are represented as a level in the hierarchical representation. The levels show the successive groupings of instances, each corresponding to a dierent number of agreements between clusterings of the ensemble, between instance sets of clusters represented as nodes. Edges represent inclusion relationships between clusters of dierent levels.

  .e., level in the hierarchy, among the consensuses in output.

Figure 8 :

 8 Figure 8: Comparison between Semi-MultiCons and MPC-Kmeans approaches. The curves illustrate the best clustering result obtained by the MCP-Kmeans single clustering approach and the Semi-MultiCons consensus clustering approach for each of the Iris (a), Wine (b), Zoo (c) and Ecoli (d) benchmark datasets. The horizontal axis shows the number of pairwise constraints used during the execution and the vertical axis shows the evaluation index value (NMI, ACC or Purity) of the clustering solution.

Figure 9 :

 9 Figure 9: Comparison between the Semi-MultiCons, MultiCons and other baseline semi-supervised consensus clustering approaches. The curves illustrate the best clustering result obtained by the DWH, GV3, HE, MultiCons and Semi-MultiCons approaches for each of the Iris (a), Wine (b), Zoo (c) and Ecoli (d) benchmark datasets. The horizontal axis shows the number of pairwise constraints used during the execution and the vertical axis shows the evaluation index value, for the NMI, ACC or Purity evaluation indexes, of the clustering solution generated.

Figure 10 :

 10 Figure 10: Ratio of negative eect. Evaluation of the negative eect of pairwise constraints for semi-supervised clustering in terms of the fraction of times that the algorithm produced worse performance than the baseline K-means clustering with optimal number of clusters as input parameter. The horizontal axis shows the number of pairwise constraints used during the execution and the vertical axis shows the ratio of negative eect in percentage, regards to the NMI, ACC and Purity evaluation indexes.

Figure 11 :

 11 Figure 11: Convergence of Semi-MultiCons. Evaluation of the convergence of Semi-MultiCons in terms of the percentage of unsatised pairwise constraints that is represented as the cost. The horizontal axis shows the successive levels of the generated hierarchy from bottom to top, which eventually corresponds to the number of iterations, and the vertical axis shows the cost as the percentage of unsatised pairwise constraints.

Figure 12 :

 12 Figure 12: Representations of the clustering results of the semi-supervised single and consensus clustering approaches on the MNIST dataset of 70 000 instances using the t-SNE visualization. Figures show the clustering results for 1 000 sample instances in the latent space. The horizontal and vertical axis represent the latent space and the colors represent the clustering results.

Figure 13 :

 13 Figure 13: Execution times. The curves show the execution times of the MPC-Kmeans, DWH, GV3, HE, MultiCons and Semi-MultiCons clustering approaches for each of the Iris (a), Wine (b), Zoo (c) and Ecoli (d) benchmark datasets. The horizontal axis shows the number of pairwise constraints used during the execution and the vertical axis shows the number of seconds required by the approach to generate the output clustering solution.

Figure 14 :

 14 Figure 14: Execution times of Semi-MultiCons for the MNIST dataset. Each bar in the diagram represents the execution time in seconds for the MNIST sample which number of instances is represented on the horizontal axis.

Table 1

 1

Table 2

 2 Example of clustering ensemble members. Each of the ve base clustering results 𝛾 𝑖 , for 𝑖 between 1 and 5, is represented by the instance sets of its clusters 𝐶 𝑗 𝑖 . Base clustering List of instance sets of base clusters

	𝛾 1	𝐶 1 1 = {𝑥 1 , 𝑥 2 , 𝑥 3 }	𝐶 2 1 = {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }
	𝛾 2	𝐶 1 2 = {𝑥 1 , 𝑥 2 , 𝑥 3 }	𝐶 2 2 = {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }
	𝛾 3	𝐶 1 3 = {𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 } 𝐶 2 3 = {𝑥 6 , 𝑥 7 }	𝐶 3 3 = {𝑥 8 , 𝑥 9 }
	𝛾 4	𝐶 1 4 = {𝑥 1 , 𝑥 2 , 𝑥 3 }	𝐶 2 4 = {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }	𝐶 3 4 = {𝑥 8 , 𝑥 9 }
	𝛾 5	𝐶 1 5 = {𝑥 1 , 𝑥 2 , 𝑥 3 }	𝐶 2 5 = {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }	𝐶 3 5 = {𝑥 8 , 𝑥 9 }

Table 4

 4 Closed patterns extracted from example binary membership matrix M. The seven closed patterns extracted from the binary membership matrix in Table3are ordered in decreasing order of the size of their Cluster set 𝐿 𝑖 containing the list of clusters 𝐶𝑗

𝑖

that agree to group together the list of instances 𝑥 𝑘 in the Instance set.

Length ({𝐿 𝑖 }) Cluster set 𝐿 𝑖

Instance set 1

  Instance sets of closed patterns 𝐶 𝑖 with their length |𝐿 𝑖 |, merging threshold 𝑀𝑇 = 0.5 Output: Multiple consensus solutions 𝑆 𝑙 1: 𝐿 𝑢𝑛𝑖𝑞𝑢𝑒 ← unique values in the list of pattern lengths |𝐿 𝑖 | 2: 𝑆 𝑙 0 ← ∅ 3: for 𝑙 𝑡 in 𝐿 𝑢𝑛𝑖𝑞𝑢𝑒 do 4: 𝑆 𝑙 𝑡 ← 𝑆 𝑙 𝑡-1 ∪ 𝐶 𝑖 which length |𝐿 𝑖 | = 𝑙

	5:	endFlag ← True
	6:	repeat
	7: 8:	for each pair of clusters (𝑋, 𝑌 ) in 𝑆 𝑙 𝑡 do if 𝑋 intersects with 𝑌 then
	9:	endFlag ← False
	10:	Calculate 𝑠(𝑋, 𝑌 )
	11:	if 𝑠(𝑋, 𝑌 ) >= 𝑀𝑇 then
	12:	Merge 𝑋 and 𝑌
	13:	else
	14:	Split larger cluster
	15:	end if
	16:	end if
	17:	end for
	18:	until endFlag = True
	19: end for

Input:

  𝑆 𝑙 𝑡-1 ∪ 𝐶 𝑖 patterns with |𝐿 𝑖 | = 𝑙 𝑡 Processing explanation 5 𝑆 𝑙 0 = ∅, patterns 𝐶 𝑖 with |𝐿 𝑖 | = 5: {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 }, {𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }} {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 }, {𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }} No intersection, generate 𝑆 5 4 𝑆 5 = {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 }, {𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }}, patterns 𝐶 𝑖 with |𝐿 𝑖 | = 4: {{𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }} {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 }, {𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }} s(X, Y) = 1, merge {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }, {𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }} s(X, Y) = 1, merge {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }} No intersection, generate 𝑆 4 2 𝑆 4 = {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }}, patterns 𝐶 𝑖 with |𝐿 𝑖 | = 2: {{𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }} {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 }, {𝑥 8 , 𝑥 9 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }} s(X, Y) = 1, merge {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }, {𝑥 8 , 𝑥 9 }} s(X, Y) = 1, merge {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }} No intersection, generate 𝑆 2 1 𝑆 2 = {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }}, 𝐶 𝑖 patterns with |𝐿 𝑖 | = 1: {{𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 }} {{𝑥 1 , 𝑥 2 , 𝑥 3 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }, {𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 }} s(X, Y) = 1, merge {{𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 }, {𝑥 4 , 𝑥 5 , 𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }} s(X, Y) = 0.4, split the larger cluster {{𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 }, {𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }} No intersection, generate 𝑆 1

End

𝑆 1 = {{𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 }, {𝑥 6 , 𝑥 7 , 𝑥 8 , 𝑥 9 }}

  Instance sets of closed patterns 𝐶 𝑖 with their length |𝐿 𝑖 | Output: Multiple consensus solution 𝑆 𝑙 1: 𝐿 𝑢𝑛𝑖𝑞𝑢𝑒 ← unique values in the list of pattern lengths |𝐿 𝑖 | 2: 𝑆 𝑙 0 ← ∅ 3: for 𝑙 𝑡 in 𝐿 𝑢𝑛𝑖𝑞𝑢𝑒 do

	4: 5:	𝑆 𝑙 𝑡 ← 𝑆 𝑙 𝑡-1 𝐶 𝑛𝑜𝑤 ← 𝐶 𝑖 with length 𝐿 𝑖 = 𝑙 𝑡
	6:	for 𝑋 in 𝐶 𝑛𝑜𝑤 do
	7: 8:	for 𝑌 in 𝑆 𝑙 𝑡 do if Should merge according to constraint-based consensus
		function then
	9:	𝑋 ← 𝑋 ∪ 𝑌
	10:	𝑌 ← ∅
	11:	else
	12:	Larger cluster ← larger cluster -𝑋 ∩ 𝑌
	13:	end if
	14:	end for
	15: 16:	Add 𝑋 to 𝑆 𝑙 𝑡 end for
	17: end for
	merging two clusters 𝑋 and 𝑌 is defined as:

Input:

Table 5

 5 Benchmark dataset properties. For each of the ve experimental datasets, its number of instance classes, number of attributes and number of instances are shown.

	Dataset Classes Attribute Number of instances
	Iris	3	4	150
	Wine	3	13	178
	Zoo	7	17	101
	Ecoli	8	8	336
	MNIST	10	784	70000
	constraint selection and/or random seeds. The processing of
	the MNIST dataset by the MPC-Kmeans requires around
	10 hours to complete, which results in unacceptable time
	cost regarding the number of repeated trials required by the
	experiment. Therefore, the number of constraints for MNIST
	is fixed to 6 000 to demonstrate the Semi-MultiCons ability
	to process large and challenging, regarding the number of
	instance classes, datasets.

Table 6

 6

Table 7

 7

Table 8

 8 Performance on the MNIST dataset. Comparison of the semisupervised single and consensus clustering approaches on the MNIST dataset of 70 000 instances. Results show the relevance of the clustering solution evaluated with the NMI, ACC and Purity indexes and execution times in seconds.

	Algorithm	NMI	ACC	Purity Time (s)
	Semi-MultiCons 0.8024 0.7735 0.7839	268.39
	MultiCons	0.7721 0.7092 0.7445	30.81
	MPC-Kmeans	0.7706 0.7025 0.7428 15677.64
	HE	0.7603 0.6861 0.7197	0.99
	DWH	0.7529 0.6873 0.7193	0.24

Acknowledgment

This project was carried out as part of the IDEX UCA JEDI MC 2 joint project between Amadeus and the Université Côte d'Azur. This work has been supported by the French government, through the UCA JEDI Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01.