dataesr/scientific-paragraphs-categorization huggingface dataset:
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 h closure of column sets for a level at each iteration  [53]. The closure h(C ) of a column set C is computed by intersection of all columns c ∈ C. Closed patterns are extracted from the binary membership matrix using the apriori() function of the arules R package  [54]  with the ''closed frequent itemsets'' parameter. A closed pattern is then a pair consisting of a cluster set and an instance set, such   3  are ordered in decreasing order of the size of their Cluster set L i containing the list of clusters C j i that agree to group together the list of instances x k in the Instance set.
This closed pattern based approach enables the processing of datasets with a very large number of instances N, as in contrast to most other consensus clustering approaches, it does not require the processing of a co-association matrix of size N 2 but only of a membership matrix of size N. M, where M is the number of base clusters, with M ≪ N, and regarding the demonstrated scalability properties of algorithms for extracting Galois closed sets  [52, 53, 55]. 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.
The merging threshold MT 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 MT = 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. The execution of the closed pattern based consensus function for the support example is shown in Fig. 3. Each iterations consider closed patterns in decreasing order of their cluster set size |L i |. The iteration generates a consensus solution according to the clusters generated during the previous iteration and the considered closed patterns.
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 k. 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.
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 us consider the following g() function that defines a value representing existing constraints between two instance a and b of the dataset. g(a, b) = 1 and g(a, b) = -1 denotes respectively that instance a and instance b have a must-link or cannot-link S merge = ∑ a∈X \(X∩Y ) ∑ b∈Y \(X∩Y ) g(a, b) |(X ∪ Y ) \ (X ∩ Y )| (1) It represents how many must-link constraints per instance are satisfied if X and Y are merged.
Experimental results An important difficulty in the application of most clustering and consensus clustering methods is the setting of the k parameter, that defines the number of clusters that will be generated. Indeed, an incorrect value for the k 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 wellknown potential negative effect reported in the literature  [57] [58] [59]. During the experimental evaluation of the Semi-MultiCons approach, we address the following issues: • Comparison between the inferred k 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-Multi-Cons 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 semi-supervised clustering approach is used for both comparison with Semi-Multi-Cons 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  [60]  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  [61] , 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  [60]  also show that MPC-Kmeans outperforms the PC-Kmeans and M-Kmeans semi-supervised clustering algorithms, and recently, in  [59] , 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 is 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. 20 GHz 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  [62] , 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)  [29] , clustering accuracy (ACC)  [63]  and Purity  [64]  indexes. Besides these datasets, the MNIST dataset  [65] , 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 constraint selection and/or random seeds.
The processing of the MNIST dataset by the MPC-Kmeans requires around 10 h 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 6000 to demonstrate the Semi-MultiCons ability to process large and challenging, regarding the number of instance classes, datasets. 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  [66] , soft least squares Euclidean consensus (DWH)  [67] , hard Euclidean consensus (HE)  [68]  and metric pairwise constrained K-means (MPC-Kmeans)  [60].
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 k 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 k parameter can deviate from the number of intrinsic clusters. We therefore choose a range of values for the k parameter according to the approximate the number of intrinsic clusters in the dataset. The MPC-Kmeans algorithm Zoo  [5 -9]  Ecoli  [4 -8]  MNIST  [8 -12]  was chosen as baseline for base clusterings to show the benefits of consensus process based on semi-supervised clustering algorithm.
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 k r by Semi-Multi-Cons over all trials for each dataset are listed in Table  7. k b represents the number of clusters defined by the k 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.
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 k for the dataset, that is to identify the most relevant consensus, i. e. , level in the hierarchy, among the consensuses in output.
Comparison with single semi-supervised clustering approaches In this experiment, the results of the Semi-MultiCons semisupervised 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 Fig. 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.
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 k. 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 k 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 k is given as input, as shown by the black curves, for all three evaluation indexes.
Comparison with semi-supervised consensus clustering approaches This experiment compares the results of the Semi-MultiCons, 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 Fig. 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 k b 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 constraintbased consensus process. Particularly, the original MultiCons approach outperforms Semi-MultiCons with known k 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 k b 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.
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.
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 6000 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 k 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  [72]  of the clustering results for the compared approaches are demonstrated in Fig. 12. The implementation in Scikit-learn Python package  [73]  was used, with initialization method set to PCA  [74]  and parameter perplexity set to 40, that is the same initialization setting as  [72].
The t-SNE visualization is trained on the entire MNIST dataset with 70 000 instances. However, to better visualize the clustering results, only 1000 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.
Computational complexity study This study aims to evaluate the efficiency of the Semi-Multi-Cons approach and compare it with MultiCons and other semisupervised 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 Fig. 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-MultiCons 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 6000, and 10 trials are performed for each execution. Fig. 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.