Performance evaluation of seven multi-label classification methods on real-world patent and publication datasets

The problem transformation methods aim to tackle problems by converting multilabel classification problem to one or more single-label problems. Binary Relevance (BR) (Li & Ogihara, 2003) and ClassifierChain (CC) (Read et al., 2011) are two popular methods that transform multi-label classification problems into single-label binary classification problems. However, the BR strategy and CC strategy fail to utilize the correlations between labels. The Label Powerset methodology (Tsoumakas & Vlahavas, 2007) treats each distinct label combination as a separate class, leading to a multi-class classification task. This approach generates an extensive range of possible label combinations.

The algorithm adaptation methods aim to transform single-label classification algorithms to accommodate multi-label data. Typically, Clare & King (2001) proposed using the concept of information gain, which was inspired by decision trees, to select features and generate classifiers. The Multi-Label k-Nearest Neighbor Algorithm (MLkNN) (Zhang & Zhou, 2007) begins by searching for the k-Nearest examples and subsequently calculating distances to make the final decision on labels. Adaboost.MH and Adaboost.MR (Schapire, 1999) uses an iterative approach to update the estimated sample weights using a weak classifier and determine the final predicted labels through weighted voting. Rank-SVM (Elisseeff & Weston, 2001) and Multi-Label Least-Squares Support Vector Machine (ML²S-SVM) (Xu & An, 2019) are based on the principles of support vector machines and incorporate kernel tricks to effectively handle multi-label classification problems. It is worth noting that the advancement of deep learning techniques in recent years has led to the emergence of several promising deep learning-based methods for multi-learning, including ML-Net (Du et al., 2019), PatentNet (Haghighian Roudsari et al., 2022) and so on.

Ensemble methods strive to enhance the performance of classifiers by employing a combination of strategies, examples of such methods include ensemble classifier chains (ECC), ensemble random K-label sets (RAkEL), and ensemble of neural network-based algorithms. The resulting representations derived from the ensemble methodology have demonstrated a marked propensity to enhance the accuracy and resilience of multi-label classification models.

ECC represents a technique that involves a series of classifiers (CC) (Freitas Rocha et al., 2022) in selecting the optimal label through an aggregation of votes for each label. Meanwhile, the integration of neural network-based algorithms aims to amalgamate various deep learning techniques to resolve the problem of multi-label topic classification. On the other hand, RakEL (Tsoumakas et al., 2010) uses a set of LabelPowerset classifiers, where each set of k-labels is trained as a multi-label classifier. During the prediction phase, the algorithm integrates a voting mechanism to combine the prediction results from multiple classifiers.

To the best of our knowledge, several open-source toolkits, implementing the above multi-label classification learning methods, can be accessed freely (see Table 1 for details). Though it is still unknown the performance on real-world datasets until now. Therefore, three of these toolkits are chosen to conduct comprehensive comparative analysis: Dependency-LDA (Rubin et al., 2012), Scikit-Multilearn (Szymanski & Kajdanowicz, 2017) and Neural Classifier (Liu et al., 2019). Apart from Dependency-LDA, both Scikit-Multilearn and Neural Classifier implement a suit of multi-label classification approaches.

The Scikit-Multilearn is a Python library, which encapsulates eleven multi-label classification learning methods. For the sake of comprehensiveness, this article chooses a representative from each type described above as follows: LabelPowerset, MLkNN, and RakEL. The Neural Classifier is a text classification toolbox on the basis of the deep learning framework PyTorch. This toolbox implements a variety of deep learning methods, which can not only consider the dependency between the labels, but also the hierarchical structure of the labels in the format of tree or Directed Acyclic Graph (DAG). It has been shown that the TextCNN, TexRNN and TextRCNN perform better than other algorithms (Liu et al., 2019).

The Dependency-LDA model (Rubin et al., 2012) is a kind of probabilistic topic models, which derives from Latent Dirichlet Allocation (LDA) model (Blei et al., 2003). This model is able to capture the dependencies between the labels as well as the prior label frequencies. It significantly improves performance over the Flat-LDA and Prior-LDA models (Rubin et al., 2012), and is highly competitive with popular discriminative approaches on large-scale datasets. It is worth mentioning that the Dependency-LDA model has a strong performance advantage when the distribution of label frequencies is highly skewed.

In a multi-label classification task, the labels are available at the training phrase. But it is more complex to infer the best label set for a document without any label since each label assignment is evaluated in the first place and then the ones with top highest posterior probability are returned. This model allows us to explore the entire topic space of each document with all possible label assignments. By setting an appropriate threshold for the posterior probability of the topic, one can infer the most likely label set for an interested document.

The MLkNN method (Zhang & Zhou, 2007), as a representative of algorithm adaptation methods, is developed from the traditional k-Nearest Neighbor (kNN) approach. The main idea of MLkNN method is that, for each test sample, its k-nearest neighbors (the k instances with the smallest distance from it in the feature space) are found from the training set in the first place. Then, the statistical information of these neighbors, such as the number of neighbors belonging to the same category and the maximum posteriori probability principle (MAP), is used to determine the label set of a focal test sample.

the Label Powerset (LP) (Tsoumakas & Vlahavas, 2007) transforms a multi-label classification problem into a multi-class classification problem. This method maps each unique label combination to a new category, and then a multi-class classification method can be readily utilized. In this way, the relationship between the labels can be fully taken into account, while simplifying the problem.

For ease of understanding, let’s take Figure 1 as an example. In this case, the instance E₁ is attached to the labels y₂ and y₃. One can create a new label y_2,3 to denote the combination of y₂ and y₃. Thus, the problem of assigning the combinations of {y₁, y₂, y₃, y₄} to the resulting instances is transformed into the problem of dividing the instances into four categories: {y₁, y_2,3, y_3,4, y_1,3}. It avoids, to some extent, the problem of an exponential increase in the label space when dealing with all label combinations.

Figure 1.

The RAkEL method (Tsoumakas et al., 2011) is actually an ensemble of Label Powerset (LP) classifiers (Tsoumakas & Vlahavas, 2007), in which each LP classifier is trained on a different small random subset of labels. Compared to the LP method, the RAkEL method can consider the label correlations, and avoid the problem of high complexity to some extent.

In more detail, the RAkEL method iteratively constructs an ensemble of m LP classifiers. At each iteration, it randomly selects a k-labelset (viz. the label combination with k elements) from the space of possible label combinations without replacement. Then, an LP classifier is trained on the chosen k-labelset. Note that the number of iterations and the size of the labelsets k are two core parameters preset by users. Finally, the predicted results of LP classifiers are counted and the label set of a target instance can be obtained according to a threshold (0.5 in general).

It’s worth mentioning that two variants are proposed by Szymanski et al. (2016): (1) the RAkELd method divides the label set into k disjoint subsets, and (2) the RAkELo allows overlapping of label subspaces. In this study, the RAkELd method is utilized in the following experiments. Since the labels of the three datasets in this study (cf. Section Dataset) have a certain hierarchical relationship, we should follow the principle of “mutual exclusion” in the division of the label sets, so the former is chosen here.

The TextCNN model (Kim, 2014), shown in Figure 2, consists of four parts: input layer, convolution layer, pooling layer and full connection layer. It processes fixed-length text sequences, using word embeddings for representation. Texts are adjusted to a specified length by either filling in short sequences or truncating longer ones. The sentences from the first layer can be expressed as cohesive operator expressions of word tokens. These sentences then slide in one dimension within a certain height (window value) of the convolution kernel to generate the new feature c_i by setting a filter w, c_i is calculated by the formula c_i=f(w⋅x_i:i+h–1+b), where x_i:j represents the connection of words x_i, x_i+1, …, x_i+j, b is a bias term and f is a nonlinear function.

Figure 2.

The convolution layer outputs a feature graph, which is then processed by maxpooling in the pooling layer to produce a fixed-length output. This output feeds into a full connection layer, culminating in a Logistic Regression classifier that outputs label probabilities.

As the name states, the TextRNN model (Liu et al., 2016) has a capacity for shortterm memory. The inputs to the model are related not only to the input at the present moment, but also to its output over a period of time. As a matter of fact, the TextRNN model is an extension of the traditional feed-forward neural network for text classification because its recursive structure is well suited for processing variable-length sentence inputs.

It dynamically updates the hidden layer based on both the immediate input and feedback from previous states, utilizing a nonlinear function to process sequences. This model learns the correlation between sequential inputs and outputs, with past outputs significantly influencing future ones. It emphasizes the importance of label frequency in training, arranging labels in descending order of occurrence for effective label correlation learning. The final output represents the sequence, feeding into layers that predict label probabilities. Parameters are minimized against cross entropy to accurately classify instances. Similar to the TextCNN, the TextRNN employs word embedding in its input layer, transitioning from sparse one-hot vectors to dense word vectors.

The recursive convolutional neural network (RCNN) (Lai et al., 2015) can introduce less noise and capture the context information to the maximum extent when learning the word representation. In addition, the model can retain a larger range of word ordering when learning textual representation. The RCNN model combines the advantages of RNN and CNN, and introduces the idea of RNN based on the four-part structure of CNN (Lai et al., 2015). It processes documents as sequences of words, aiming to classify them into resulting labels based on the probability p(k|D,θ), where θ represents the network parameters. The RCNN uniquely constructs word representations by combining context from both sides of a word with the word itself, utilizing bidirectional RNNs for context extraction. Context vectors c_l(w_i) and c_r(w_i) for each word are generated through specific equations, incorporating word embeddings and shared parameters for sentence boundaries to create a comprehensive representation of each word.

To demonstrate the difficulty of multi-label classification on the real-world datasets, Table 2 reports the characteristics of our datasets and several benchmark ones: emotions (Trohidis et al., 2011), scene (Boutell et al., 2004), bibtex (Katakis et al., 2008), and medical (Pestian et al., 2007). From Table 2, several phenomena can be observed as follows. (a) The number of instances and labels in the benchmark datasets is much less than that in our datasets. (b) The labels in our datasets show a clear hierarchical structure, but no hierarchical structure is observed from the benchmark datasets. Among our three datasets, the Biological-Sciences dataset ranks first in terms of the number of hierarchies, followed by the Health-Sciences dataset. (c) The label output space of our datasets, especially USPTO dataset, is generally larger than that of the benchmark datasets in terms of label cardinality. The label cardinality represents the average number of labels allocated to an instance. (d) Our datasets are more unbalanced than the benchmark datasets in terms of the number of documents per label (cf. the last three columns in Table 2). Among our three datasets, the number of documents allocated to each label varies the most in the USPTO dataset, followed by the Health-Science dataset. Notably, due to the limited instances within the sub-group levels of IPC and CPC, this study has limited the hierarchy to the group level.

To understand intuitively the highly skewed distribution of label frequencies, Figure 3 illustrates the power-law distribution characteristics of our three datasets. From Figure 3, it is not difficult to see that the vast majority of the labels are associated with a small number of documents, and relatively few labels are assigned to a large number of documents. This is a very popular characteristic in the real-world multi-label classification problems (Dekel & Shamir, 2010; Liu et al., 2005; Yang et al., 2003).

Figure 3.

In addition, this part uses NLTK tools in Python to process text, including sentence and word segmentation, part-of-speech tagging, word-type reduction, deactivation and removal of stop words, punctuation marks and numbers. After these preprocessing steps, our datasets mainly consist of semantic word stems. In the end, the statistics of each dataset are shown in Table 3.

Since an instance is attached with multiple labels, it is not trivial to group a multilabel dataset into two disjoint subsets. Before splitting our dataset into training and test sets, we identify the following rules. (1) An instance does not belong to two sets at the same time. To say it in another way, the training set has no intersection with the test set. (2) The label set in the test set is a subset of the label set in the training set. That is to say, each label must appear in the training set, and several labels are allowed not to appear in the test set. (3) In our experiment, the ratio between the number of instances in the training and test set is approximately 4:1.

To enable our splitting procedure to follow the above rules, the stratification method in Sechidis et al. (2011) is utilized in the first place. Then, we manually adjust several instances that do not meet the above requirements. In the end, the number of instances in the training set and test set is shown in Table 4.

In the literature, two groups of measures are usually utilized: the label-based evaluation measures and the instance-based evaluation measures. As for the former, the performance of a single label in all instances is calculated in terms of accuracy, precision, recall and F1 score, and then one averages the performance of all labels to obtain an overall performance (Tsoumakas & Vlahavas, 2007). The latter is further divided into classification-based measures and ranking-based measures (Ghamrawi & Mccallum, 2005; Godbole & Sarawagi, 2004).

Generally speaking, there are no universal multi-label classification evaluation measures for all problems. In this study, the following three classification-based measures are adopted: Macro-F1, Micro-F1 and Hamming Loss.

Each method has several core parameters. It is well-documented that these parameters will influence the performance of the resulting method. Therefore, it is necessary to tune the core parameters of each approach before performance comparison.

The majority of the experiments conducted within this study are executed on Colab servers, which are equipped with a GPU of 16GB and a CPU of 12GB, resulting in approximate program execution times of around 2 hours. For deep learning models, such as RCNN, and for processing larger datasets, such as USPTO, the most substantial server configurations utilized comprise a GPU of 48GB and a CPU of 64GB, with program run times approximating 10 hours.

For the convenience of readers, the experimental results of the above seven methods are summarized in Table 8. It is noteworthy that Table 8 just depicts the best performance in terms of three evaluation measures, but the resulting parameters may not be consistent. From Table 8, the following conclusions can be drawn:

(1) For the datasets with small data size and balanced document-label distribution, the TextCNN and TextRCNN models should be preferred. In more detail, both the Biological-Sciences and the Health-Sciences datasets have smaller number of documents and labels, more balanced document-label distribution than the USPTO dataset. The TextCNN model shows obvious superiority on these two datasets, especially the Biological-Sciences dataset.

(2) For extremely large datasets with unbalanced document-label distribution, the MLkNN algorithm is more effective. For the USPTO dataset, the maximum number of labels assigned to an instance is 65. This means that we need to make a judgment on the top 65 labels for each instance. The top number of labels of the other datasets is 4 and 7 respectively, which is much simpler than the USPTO dataset. The MLkNN algorithm can effectively avoid this kind of individual judgment. To say it in another way, this algorithm is more suitable for large datasets with skewed document-label distribution by simply calculating the distance between the k instances of known categories closest to the instance, and then assigning labels according to the principle of minimum distance.

Additionally, we have calculated the Spearman’s rank correlation coefficients among the Macro F1, Micro F1, and Hamming loss metrics, as presented in Table 8. The analysis reveals a robust positive correlation between Macro F1 and Micro F1 (0.76), indicating a strong relationship. However, no significant correlation is detected between Macro/Micro F1 and Hamming loss. This indicates that different dimensions of multi-label classification tasks are measured by macro/micro F1 and Hamming loss. In the context of multi-label classification research and applications, it is imperative to choose evaluation metrics with flexibility, taking into consideration their respective strengths and weaknesses, as well as the specific context in which they are applied.