Recently several methods were proposed for the improvement of multi-label classi cation performance by using constraints on labels. Such constraints are based on dependencies between classes often present in multi-label data and can be mined as association rules from training data. The rules are then applied in a post-processing step to correct the classi er predictions. Due to properties of association rule mining these improvement methods often achieve low improvement expressed mostly in the better prediction of large classes. In the presence of class ontologies this is undesirable because larger classes correspond to higher levels in hierarchies presenting general concepts and can thus be trivial. In this paper we overcome the problem by focusing on improving multi-label classi cation performance on small classes. We present a new method of improvement based on mining cross-ontology association rules which is best suited for classi cation with multiple class ontologies, but can also be applied to multi-label classi cation with one class taxonomy.
The increasing popularity of ontologies in di erent areas has led to the
availability of data that can be annotated with multiple classes coming from di erent
class taxonomies. This is a special case of multi-label classi cation. Generally,
combining information from the ontologies providing di erent insights into a
domain can be helpful in discovering new cross-ontology associations not evident
from only one ontology. For example, if a lm is classi ed by its genre in a genre
ontology and by the producing company in an ontology of producers, one can nd
a possible interesting relation between a certain genre and a producing company,
specialized in this genre. Recently, data mining techniques such as association
analysis were applied to nding valuable cross-ontology Association Rules (ARs)
between multiple ontologies corresponding to distinct categorizations of genes in
bioinformatics [
On the other hand, useful information from such cross-ontology rules can be successfully employed to improve performance in multi-label classi cation: ARs found among classes of multiple ontologies can be used to correct predicted labels because the presence of a certain class or classes can be helpful for predicting another one. For example, a proper application of the association between a certain genre and a producing company specializing in this genre, as discussed above, can increase the probability of correctly predicting a genre, providing the corresponding company has been already correctly predicted. Thus it should lead to an improvement in classi cation performance. This is especially important with respect to very large ontologies with many thousands of classes, which are usually di cult to deal with.
Another problem with class ontologies that has not yet been dealt with
sufciently in recent research is that classi er performance in such a case is largely
dominated by more general classes higher in the hierarchy because they are more
present in the data and hence simpler to predict for a classi er. On the other
hand, such general classes do not often provide interesting information and are
sometimes trivial. For this reason, in mining cross-ontology rules rare
association rules [
An important di erence between our approach and several state-of-the-art methods discussed in the next section is that they use constraints for labels of one labelset and not two di erent class ontologies. Further, our approach focuses on rare labels, i.e. the ones with low support, since they are normally the greater part of the labelset.
The rest of the paper is organized as follows. A brief overview of the approaches to multi-label improvement with ARs is given in Section 2. Afterwards, our approach is explained in Section 3, followed by the experiments of Section 4. In Section 5 we conclude the paper. 2
Recently several approaches to improving multi-label classi cation performance
were proposed that dealt with dependencies between classes present in
multilabel data. Some of them belong to the eld of multi-label classi cation with
constraints and apply constraints on labels to performance improvement usually
in a post-processing step. The constraints are often mined in form of ARs from
training data [
The initial work was devoted to prediction corrections within the ranking by
pairwise comparison framework [
A more recent approach of [
In contrast to the discussed post-processing methods evaluated in a certain
multi-label classi cation setting (either pairwise or BR), a more general
approach, Label Reduction with Association Rules (LRwAR), was proposed in [
Besides relatively low improvement demonstrated by the existing methods, they
have the problem of using the standard support-con dence framework for AR
mining, which normally extracts high support rules that often exist between
large classes. So they ignore small classes as a potential source for improvement
because minimum support ltering can remove not only noise but also rare
classes. The greatest problem of Con dence in such a setup is that associations
of small classes to large ones are normally ranked very high. In the case of a
class ontology these ARs simply show hierarchical parent-child relations, i.e.
that one label a is more speci c than another b. The rule extracted would be
a!b, which means that if label a appears, then label b should appear too. Such
obvious relations can be derived from an extracted hierarchy, on the one hand,
as in [
Another problem with the standard AR framework is choosing the thresholds for Support and Con dence which is done manually and can therefore be suboptimal. So, the rst issue to be dealt with improving multi-label classi cation performance by constraints is the acquisition of high-quality rules. In the proposed approach we solve this problem by omitting the minimum support threshold and using a special interestingness measure which is well-suited for rare rules. Additionally we tune its threshold automatically depending on the range of values for extracted rules. The idea is to use rare ARs between classes that is from a small class to another small one and that classes belong to two or more ontologies describing di erent aspects of a dataset. In this case hierarchical relations between the classes of one ontology will not be taken into account. In such a setting, training data are annotated with categories of both ontologies. Then mined rules are used to improve class predictions for one of both ontologies. So, rare cross-ontology rules can be helpful in order to solve the described problems.
The second important issue is deciding when to apply a rule. Is the predicted
label trusty enough to insert an additional label based on its presence? The worst
case scenario would be that the rule is applied on the basis of a false positive
inserting an additional false positive. Another undesirable outcome would be
that the antecedent label is a true positive but applying a rule would create a
false positive, i.e. the prediction of the classi er should not be overruled. The
desirable decision is only to use a true positive to add another true positive, i.e.
that a rule corrects the missclassi cation of a label. In [
To extract pairwise ARs, we performed experiments with the interestingness
measures well-suited for mining rare rules [
Kulc(A; B) = PAB 2 ( 1 PA + 1 PB ):
In order to select only the best rules, adaptive thresholding without a predened value was applied as follows: After calculating Kulc of all rules, the values are sorted in descending order as a curve C. We assume that there will be a slope between a few high scored rules and the rest. In order to select these rules the curve C is smoothed into S and only the part with a relatively low variance is analyzed. Thus we need rst to determine whether the variance of the curve S is high:
CV =
> m (1) where MEAN (S) is the average value of the curve S and VAR(S) its variance. If the condition of Eq. (1) is true, we use only the values in the slope of the curve and calculate the median that de nes a Threshold Value TV for the most interesting rules:
TV = CMEDIAN (fijDIFF (Si)>MEAN (DIFF (S))g) where DIFF (S) is the di erence between two neighbor values in the curve S. Since the step size between two values is 1, DIFF (S) can also be seen as the derivative of S. Otherwise, i.e. if the variance is high, the average of the values not much lower than the mean of the entire curve is taken:
TV =
j2fijSi>MEAN (S) tg :
De ning the threshold in this manner, we select only those rules that have Kulc values above TV as good enough to be applied to prediction improvement.
m and t should be set so that the changes are signi cant and the only high valued rules are selected, respectively. 3.2
As discussed above, applying a rule for insertion of a label without taking the
corresponding classi er's judgment into account can lead to no improvement
or even poorer prediction performance. A better way would be to use rankings
produced by the classi er. An attempt was proposed in [
A drawback of this method is that it relies on individual parameter
optimization for each rule through a cost-intensive calculation of the Ranking Loss.
This is not viable for large datasets as the later work [
We propose a similar approach. The antecedent A of a rule A!B should be already positively predicted, i.e. should have a score greater than the threshold t, but an additional criterion should hold: VVBA > 0:5, i.e. the score of the consequent should be at least 50% of the value of the antecedent in order to set the consequent.
As emphasized before, our approach was designed to work on classi cation problems with two di erent multi-label sets coming from two ontologies, but it can still be applied to the problems with only one class taxonomy in order to compare to other methods, as is shown in the next section. 4 4.1
We used two multi-label real-world datasets: Reuters and Yeast. The rst one was used with two class ontologies \Topics" and \Industries" for mining crossontology ARs as well as in a simpli ed version with only \Topics" labels in order to compare our method to the results of other improvement methods published elsewhere.
The two-ontology Reuters dataset was formed by preprocessing with stopword removal and stemming the original data provided by http://trec.nist. gov/data/reuters/reuters.html. We used the 5000 most frequent terms in the training set and applied tf-idf weighting as well as column-wise normalization performed separately on training and test data. In the original 800k samples only 300k contained at least one \Industries" label. From these we selected random 30k samples and split them into a training and a test set with the ratio of 2:1, i.e. 20k training samples and 10k test samples. In total there were 103 \Topics" labels and 364 \Industries" labels. We will denote this dataset as Reuters 10k below.
The simpli ed version (Reuters 5k with only \Topics" classes) consisted of 5000 training and 5000 test samples chosen randomly from the original 23k training set. The data preprocessing was performed as described above.
For the sake of comparison, the Yeast dataset was also taken from the MEKA
package [
As a baseline classi er we used LIBLINEAR [
For LRwAR we also implemented a variation using rankings for all classes and only inserting new labels. We use the acronym OF (only ll) for this variation. The original method foresees deleting rankings of classes in the consequent of a rule as well.
Parameters of LRwAR and LCS were set as in their original works [
Parameters for adaptive thresholding were set to m = 0:2 and t = 0:75. These values were obtained by the manual experimentation on the Reuters dataset and are, in our opinion, general enough to be used for all datasets. 4.3
We used the F-1 measure, which is the harmonic mean of Recall and
Precision. It can be calculated in several ways depending on averaging [
pared our approach to LRwAR,LCS, and LCA on the datasets used in other studies. In Table 1 the results for Yeast and Reuters 5k are depicted.
On the Yeast data, IRAR, LCS, and LRwAR OF could improve the results of BR and ML-kNN classi ers in terms of mF1, IF1, and LF1. The improvement achieved by IRAR was the highest. H-loss for this dataset could not be increased by any of the compared methods. Among them LRwAR was the worst because its results were even worse as those of the baseline classi ers in terms of all performance measures. In contrast to the other methods, IRAR was also better than LCA for BR and comparable to it for ML-kNN. This shows that a powerful thresholding strategy can outperform many improvement methods based on label constraints. IRAR was the only improvement methods that could increase the CC results. This was the highest LF1 value by far on this dataset.
This is consistent with the important fact that IRAR could increase the LF1 value signi cantly more than the other methods in almost all con gurations. The only exception was for Reuters 5k and BR where it improved second best. This can be explained by the better improvement of the classi cation performance on small classes. Indeeed, as Figure 1a shows, the number of true positives on small and middle-size classes obtained by IRAR was higher than that of LCA (Figure 1b). This di erence is even more pronounced if we compare F-1 values for each class obtained by all improvement methods and presented in Figure 2a. One can see, for example, that IRAR achieves a signi cant improvement in F-1 for the last class where the other methods show no improvement at all or that it has much more improvement on the classes 5-10.
Analyzing the curves of mF1 and LF1 in dependence on the threshold t one can see a trade-o between them (Figure 2b). IRAR is able to achieve both high LF1 and mF1 values near their crossing point.
On the Reuters 5k dataset, IRAR had again the highest improvement against the baseline classi er as compared to the other improvement methods in terms of all performance measures, except for h-loss. The largest performance di erence was again in LF1. IRAR performance was comparable to that of LCA. LCS and LRwAR achieved a very small improvement against the baseline classi er and were worse than LCA in terms of all performance measures, except for h-loss. Here we can see that CC had was the second best classi er, but no improvement could beat LCA method. Again, the exception remains IRAR with LF1, having a 18% value increase over the baseline performance and 3% over LCA.
CC did not outperform BR in the experiments, although CC does consider
the connections between the labels in a certain way. A solution would be to
use Ensembles of CC (ECC) [
Number of True Positives per Class Number of True Positives per Class (a) Yeast, IRAR, number of true positives (b) Yeast, LCA, number of true positives
BR
ML-kNN mF1 IF1
CC Dataset with two class ontologies: Reuters 10k Table 2 depicts the results of classi cation improvement for the Reuters 10k dataset, rst classi ed separately in \Topics" and \Industries" and then with improved \Industries" predictions, by using cross-ontological ARs. In general, the classi cation performance for \Topics" was higher than for \Industries" classes. The results of the improvement methods LCS and IRAR for this class ontology were better than those of the baseline classi er, except that h-loss of IRAR was lower. At the same time, LRwAR showed negative improvement and LRwAR OF only improvement at the fourth place after the decimal point. In contrast, IRAR was able to achieve the overall best LF1. Its results were also somewhat similar to the results of LCA. It is interesting to note that LCS outperformed LCA in terms of mF1 and IRAR in terms of LF1. So, we can conclude that LCS is more e ective for classes with large support and IRAR for those with small support. This will be due to the use of con dence to extract the rules.
The results for Reuters 10k \Industries" are similar to those obtained for \Topics". Here LRwAR had even more negative improvement in terms of all performance measures and LRwAR OF showed again only marginal improvement. LCS was equal or better than the baseline and achieved again the highest mF1 value. This time both LCA and IRAR were worse than the baseline in terms of h-loss and mF1, but improved IF1 and LF1. However IRAR was better than LCA in three out of four performance measures and had again the best LF1.
Using cross-ontology ARs for the improvement of \Industries" predictions revealed an interesting fact: the results of LCS and both LRwAR variants worsened in comparison with those shown in the previous experiment while IRAR could improve its h-loss and mF1 values. Here, LCS uses the thresholds of di erent classi ers trained with di erent labelsets that may obstruct its performance. Also the low occurrence of labels in the labelsets may lead to poor results of the Con dence-based methods. In this paper we proposed a novel method of classi cation improvement in multilabel classi cation IRAR. It uses cross-ontology association rules and focuses on the improvement of predictions for small classes. Additionally, we compared it with state-of-the-art methods developed to correct predicted rankings by using constraints on labels in a post-processing step. One of the methods, LRwAR, showed negative improvement in most of the experiments and its variation only marginal improvement. LCS scored better in terms of improvement, but a better thresholding strategy such as LCA often achieved even more improvement. IRAR could outperform LCA in three out of four performance measures on the Yeast and Reuters 10k datasets. More importantly, it boosted the LF1 value signi cantly and showed the best LF1 result in three of ve experiments. This means that IRAR is well suited for improving performance on small classes. This method is also able to achieve the trade-o between LF1 and mF1, i.e. it was able to achieve a high LF1 at a relatively low number of false positives. This points to the fact that the method can be used e ectively with datasets exhibiting highly skewed label distributions as, for example, in the case of class ontologies.