The Label Ranking (LR) problem is a well-known nonstandard supervised classification problem, the goal of which is to learn preference classifiers from data, mapping instances to rankings of the labels of the class variable. In the literature, the particular setting where the output of the LR problem is a complete ranking without ties (a.k.a. permutation) has been profusely studied, and many algorithms have been designed to solve these particular instances based on the use of specific probability distributions and aggregation methods for permutations. However, also partial orders (a.k.a. bucket orders) can be considered as output in LR problems (i.e., some labels of the class variable may be tied), but the algorithms available do not tackle this kind of ranking. We refer to this particular case of LR as the Partial Label Ranking (PLR) problem. Thus, motivated by the lack of current methods to deal with the PLR problem, we design machine learning algorithms based on instance-based and decision tree approaches to tackle the PLR problem. We evaluate our proposals on a benchmark of 15 data sets obtained by transforming multiclass instances, and analyze their performance by carrying out a standard machine learning statistical analysis procedure.

The Optimal Bucket Order Problem (OBOP) is a rank aggregation problem which consists in finding a consensus ranking (with ties) that generalizes a set of input rankings. In this paper, with the aim of solving the OBOP in an efficient and scalable way, we propose several greedy algorithms based on different sort-first and cluster-second strategies. More specifically, the sorting step is based on the Borda method, whereas in the cluster step, pairs of adjacent buckets are suitably joined. The proposed methods are experimentally compared with the state-of-the-art greedy algorithms for solving the OBOP by using a large benchmark of real-world databases. Furthermore, we provide a complete statistical analysis of the experimental study, which shows that several of the proposed algorithms outperform the current state-of-the-art greedy algorithms. We also analyze the trade-off between accuracy and execution time of the algorithms to guide the users regarding the selection of the best option for each particular case. The study carried out shows that our proposal is not only competitive in terms of accuracy with the state-of-the-art evolutionary strategy for dealing with the OBOP, but is also fast and scalable.

Annual journal rankings are usually considered a tool for the evaluation of research and researchers. Although they are an objective resource for such evaluation, they also present drawbacks: (a) the uncertainty about the definite position of a target journal in the corresponding annual ranking when selecting a journal, and (b) in spite of the nonsignificant difference in score (for instance, impact factor) between consecutive journals in the ranking, the journals are strictly ranked and eventually placed in different terciles/quartiles, which may have a significant influence in the subsequent evaluation. In this article we present several proposals to obtain an aggregated consensus ranking as an alternative/complementary tool to standardize annual rankings. To illustrate the proposed methodology we use as a case study the Journal Citation Reports, and in particular the category of Computer Science: Artificial Intelligence (CS:AI). In the context of the consensus rankings obtained by the different methods, we discuss the convenience of using one or the other procedure according to the corresponding framework. In particular, our proposals allow us to obtain consensus rankings that avoid crisp frontiers between similarly ranked journals and consider the longitudinal/temporal evolution of the journals.

High Efficiency Video Coding was developed by the JCT-VC to replace the current H.264/AVC standard, which has dominated digital video services in all segments of the domestic and professional markets for over ten years. Therefore, there is a lot of legacy content encoded with H.264/AVC, and an efficient video transcoding from H.264 to HEVC will be needed to enable gradual migration to HEVC. HEVC adopts a quad tree-based Coding Unit block partitioning structure that is flexible in adapting various texture characteristics at the expense of a high computational cost. This paper presents a data-driven probabilistic CTU splitting algorithm that is designed to exploit the information gathered at the H.264/AVC decoder in order to make faster decisions on CU splitting in HEVC. Experimental results show that the proposed algorithm can achieve a good tradeoff between coding efficiency and complexity compared with the anchor transcoder, and, moreover, it outperforms other related works available in the literature.

Learning Bayesian networks is known to be an NP-hard problem, and this, combined with the growing interest in learning models from high-dimensional domains, leads to the necessity of finding more efficient learning algorithms. Recent papers have proposed constrained approaches of successfully and widely used local search algorithms, such as Hill Climbing. One of these algorithms families, called constrained Hill Climbing (CHC), greatly improves upon the efficiency of the original approach, obtaining models with slightly lower quality but maintaining their theoretical properties. In this paper, we propose three different modifications to the most scalable version of these algorithms, fast constrained Hill Climbing, to improve the quality of its output by relaxing the constraints imposed to include some diversification in the search process. The aim of these new approaches is to adjust the trade-off between efficiency and accuracy of the algorithm, as they do not modify its complexity and only imply a few more search iterations. We perform an intensive experimental evaluation of the modifications proposed with an extensive comparison between the original algorithms and the new modifications covering several scenarios with quite large data sets. Available code and data for further use of the algorithms presented in this paper and experiment replication can be available at http://simd.albacete.org/supplements/FastCHC.html.

This paper deals with the problem of wrapper-based feature subset selection in classification oriented datasets with a (very) large number of attributes. In such datasets sophisticated search algorithms like beam search, branch and bound, best first, genetic algorithms, etc., become intractable in the wrapper approach due to the high number of wrapper evaluations to be carried out. One way to alleviate this problem is to use the so-called filter-wrapper approach or Incremental Wrapper-based Subset Selection (IWSS), which consists in the construction of a ranking among the predictive attributes by using a filter measure, and then a wrapper approach is used guided by the rank. In this way the number of wrapper evaluations is linear with the number of predictive attributes. In this paper we present a contribution to the IWSS approach which helps it to obtain more compact subsets, and consists into allow not only the addition of new attributes but also the interchange with some of the already included in the selected subset. The disadvantage of this novelty is that it grows up the worst-case complexity of IWSS up to O(n2), however, as in the case of the well known sequential forward selection (SFS) the actual number of wrapper evaluations is considerably smaller. Empirical tests over 7 (biological) datasets with a large number of attributes demonstrate the success of the proposed approach when comparing with both IWSS and SFS.

Triangulation of Bayesian networks (BNs) is an NP-hard problem and of great importance for the efficiency of propagation algorithms. Several approaches, most of them basically heuristic, have been proposed to search optimal solutions for this problem. Recently, Olesen and Madsen1 launched the possibility of applying the maximal prime subgraph decomposition (MPSD) to the problem of triangulation. The idea is to retriangulate separately each MPS, so that we can work on smaller graphs. In this article, we exploit this idea by using both greedy heuristic algorithms and stochastic ones [genetic algorithms (GAs)]. From an experimentation performed over 10 real complex networks, we study empirically the usefulness of applying this MPSD-based retriangulation. © 2003 Wiley Periodicals, Inc.