Abstract The hybrid genetic search (HGS) metaheuristic has produced outstanding results for several variants of the vehicle routing problem. A recent implementation of HGS specialized to the capacitated vehicle routing problem (CVRP) is a state‐of‐the‐art method for this variant. This paper proposes an improved HGS for the CVRP obtained by incorporating a new solution generation method into its (re‐)initialization process to guide the search more efficiently and effectively. The solution generation method introduced in this work combines an approach based on frequent patterns extracted from good solutions by a data mining process and a randomized version of the Clarke and Wright savings heuristic. As observed in our experimental comparison, the proposed method significantly outperforms the original algorithm regarding the final gap to the best known solutions and the primal integral.

In collaborative software development, multiple contributors frequently change the source code in parallel to implement new features, fix bugs, refactor existing code, and make other changes. These simultaneous changes need to be merged into the same version of the source code. However, the merge operation can fail, and developer intervention is required to resolve the conflicts. Studies in the literature show that 10 to 20 percent of all merge attempts result in conflicts, which require the manual developer's intervention to complete the process. In this paper, we concern about a specific type of change that affects the structure of the source code and has the potential to increase the merge effort: code refactorings. We analyze the relationship between the occurrence of refactorings and the merge effort. To do so, we applied a data mining technique called association rule extraction to find patterns of behavior that allow us to analyze the influence of refactorings on the merge effort. Our experiments extracted association rules from 40,248 merge commits that occurred in 28 popular open-source projects. The results indicate that: (i) the occurrence of refactorings increases the chances of having merge effort; (ii) the more refactorings, the greater the chances of effort; (iii) the more refactorings, the greater the effort; and (iv) parallel refactorings increase even more the chances of having effort, as well as the intensity of it. The results obtained may suggest behavioral changes in the way refactorings are implemented by developer teams. In addition, they can indicate possible ways to improve tools that support code merging and those that recommend refactorings, considering the number of refactorings and merge effort attributes.

Data uncertainty remains a challenging issue in many applications, but few classification algorithms can effectively cope with it. An ensemble approach for uncertain categorical features has recently been proposed, achieving promising results. It consists in biasing the sampling of features for each model in an ensemble so that less uncertain features are more likely to be sampled. Here we extend this idea of biased sampling and propose two new approaches: one for selecting training instances for each model in an ensemble and another for sampling features to be considered when splitting a node in a Random Forest training. We applied these approaches to classify ageing-related genes and predict drugs' side effects based on uncertain features representing protein-protein and protein-chemical interactions. We show that ensembles based on our proposed approaches achieve better predictive performance. In particular, our proposed approaches improved the performance of a Random Forest based on the most sophisticated approach for handling uncertain data in ensembles of this kind. Furthermore, we propose two new approaches for interpreting an ensemble of Naive Bayes classifiers and analyse their results on our datasets of ageing-related genes and drug's side effects.

The hybridization of metaheuristics with data mining techniques has been successfully applied to combinatorial optimization problems. Examples of this type of strategy are DM-GRASP and MDM-GRASP, hybrid versions of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, which incorporate data mining techniques. This type of hybrid method is called Data-Driven Metaheuristics and aims at extracting useful knowledge from the data generated by metaheuristics in their search process. Despite success in combinatorial problems like the set packing problem and maximum diversity problem, proposals of this type to solve continuous optimization problems are still scarce in the literature. This work presents a data mining hybrid version of C-GRASP, an adaptation of GRASP for problems with continuous variables. We call this new version DMC-GRASP, which identifies patterns in high-quality solutions and generates new solutions guided by these patterns. We performed computational experiments with DMC-GRASP on a set of well-known mathematical benchmark functions, and the results showed that metaheuristics for continuous optimization could also benefit from using patterns to guide the search for better solutions.

Coping with uncertainty is a very challenging issue in many real-world applications. However, conventional classification models usually assume there is no uncertainty in data at all. In order to fill this gap, there has been a growing number of studies addressing the problem of classification based on uncertain data. Although some methods resort to ignoring uncertainty or artificially removing it from data, it has been shown that predictive performance can be improved by actually incorporating information on uncertainty into classification models. This paper proposes an approach for building an ensemble of classifiers for uncertain categorical data based on biased random subspaces. Using Naive Bayes classifiers as base models, we have applied this approach to classify ageing-related genes based on real data, with uncertain features representing protein-protein interactions. Our experimental results show that models based on the proposed approach achieve better predictive performance than single Naive Bayes classifiers and conventional ensembles.

In many important application domains, such as text categorization, biomolecular analysis, scene or video classification and medical diagnosis, instances are naturally associated with more than one class label, giving rise to multi-label classification problems. This has led, in recent years, to a substantial amount of research in multi-label classification. More specifically, feature selection methods have been developed to allow the identification of relevant and informative features for multi-label classification. This work presents a new feature selection method based on the lazy feature selection paradigm and specific for the multi-label context. Experimental results show that the proposed technique is competitive when compared to multi-label feature selection techniques currently used in the literature, and is clearly more scalable, in a scenario where there is an increasing amount of data.

Abstract A recent survey using industrial projects has shown that providing an estimate of the lifetime of pull requests to developers helps to speed up their conclusion. Previous work has explored pull request lifetime prediction in open‐source projects using regression techniques but with a broad margin of error. The first objective of our work was to reduce the average error rate of the prediction obtained by the regression techniques so far. We performed experiments with different regression techniques and achieved a significant decrease in the mean error rate. The second objective of our work was to obtain a more effective and useful predictive model that can classify pull requests according to five discrete time intervals. We proposed new predictive attributes for the estimation of the time intervals and employed attribute selection strategies to identify subsets of attributes that could improve the predictive behavior of the classifiers. Our classification approach achieved the best accuracy in all the 20 projects evaluated in comparison with the literature. The average accuracy was of 45.28% to predict pull request lifetime, with an average normalized improvement of 14.68% in relation to the majority class and 6.49% in relation to the state‐of‐the‐art.

Summary When external contributors want to collaborate with an open‐source project, they fork the repository, make changes, and send a pull request to the core team. However, the lifetime of a pull request, defined by the time interval between its opening and its closing, has a high variation, potentially affecting the contributor engagement. In this context, understanding the root causes of pull request lifetime is important to both the external contributors and the core team. The former can adopt strategies that increase the chances of fast review, while the latter can establish priorities in the reviewing process, alleviating the pending tasks and improving the software quality. In this work, we mined association rules from 97,463 pull requests from 30 projects in order to find characteristics that have affected the pull requests lifetime. In addition, we present a qualitative analysis, helping to understand the patterns discovered from the association rules. The results indicate that: (i) contributions with shorter lifetimes tend to be accepted; (ii) structural characteristics, such as number of commits, changed files, and lines of code, have influence, in an isolated or combined way, on the pull request lifetime; (iii) the files changed and the directories to which they belong can be robust predictors for pull request lifetime; (iv) the profile of external contributors and their social relationships have influence on lifetime; and (v) the number of comments in a pull request, as well as the developer responsible for the review, are important predictors for its lifetime.

Understanding the ageing process is a very challenging problem for biologists. To help in this task, there has been a growing use of classification methods (from machine learning) to learn models that predict whether a gene influences the process of ageing or promotes longevity. One type of predictive feature often used for learning such classification models is Protein-Protein Interaction (PPI) features. One important property of PPI features is their uncertainty, i.e., a given feature (PPI annotation) is often associated with a confidence score, which is usually ignored by conventional classification methods. Hence, we propose the Lazy Feature Selection for Uncertain Features (LFSUF) method, which is tailored for coping with the uncertainty in PPI confidence scores. In addition, following the lazy learning paradigm, LFSUF selects features for each instance to be classified, making the feature selection process more flexible. We show that our LFSUF method achieves better predictive accuracy when compared to other feature selection methods that either do not explicitly take PPI confidence scores into account or deal with uncertainty globally rather than using a per-instance approach. Also, we interpret the results of the classification process using the features selected by LFSUF, showing that the number of selected features is significantly reduced, assisting the interpretability of the results. The datasets used in the experiments and the program code of the LFSUF method are freely available on the web at http://github.com/pablonsilva/FSforUncertainFeatureSpaces.

The number of people diagnosed with anxiety disorders has been increasing in recent years. The correct diagnosis of such disorders is not always a trivial task, sometimes forcing an individual to consult with many clinicians and performing several medical exams. Post-traumatic Stress Disorder (PTSD) is a disorder related to experienced events, which presented a certain degree of threat to an individual. When experiencing situations that refer to past events, an individual may present reactions that trigger physiological changes in the organism such as tachycardia or bradycardia. Many disorders have common symptoms, and identifying these subtleties results in greater diagnosis efficiency and effectiveness. Artificial Intelligence (AI) and Data Mining (DM) techniques have helped specialists in the diagnosis and prevention of diseases and disorders. In our research, we aim at finding new biomarkers to diagnose PTSD analyzing physiological signals with DM techniques. In this paper, we used a dataset from an experiment with civilians that were recently exposed to traumatic events related to violence. Those individuals completed a questionnaire that evaluates the impact of such events through PCL (PTSD Disorder Checklist for DSM-IV) scale. Heart rate and skin conductance signals were collected while viewing emotional and neutral stimuli images. We applied DM techniques and classification algorithms to evaluate and maximize PCL score prediction performance considering those physiological signal data. The best result was obtained with SMO algorithm with its hyperparameters values suggested by an auto-learning procedure, presenting an accuracy of 85.45% (p-value = 0.001), precision of 0.8 (p-value = 0.001), recall of 0.5714 and F-Measure of 0.6667 (p-value = 0.001).

In recent years, multi-label classification (MLC) has become an emerging research topic in big data analytics and machine learning. In this problem, each object of a dataset may belong to multiple class labels and the goal is to learn a classification model that can infer the correct labels of new, previously unseen, objects. This paper presents a survey of genetic algorithms (GAs) designed for MLC tasks. The study is organized in three parts. First, we propose a new taxonomy focused on GAs for MLC. In the second part, we provide an up-to-date overview of the work in this area, categorizing the approaches identified in the literature with respect to the taxonomy. In the third and last part, we discuss some new ideas for combining GAs with MLC.

Feature selection methods have been widely adopted to prepare high-dimensional feature spaces for the classification task of data mining. However, in many real-world datasets, the feature space is formed by binary features related via generalization-specialization relationships, also known as hierarchical feature spaces. Although there are many methods for the traditional feature selection problem, methods which properly consider hierarchical features are still very underexplored. In this work, we propose a novel genetic algorithm (GA) for hierarchical feature selection. The proposed GA has two novel hierarchical mutation operators tailored to deal with redundant features in hierarchical feature spaces. The computational experiments show that our proposed approach exhibited better predictive performance than two state-of-the-art hierarchical feature selection methods (SHSEL and HIP) and also than two traditional feature selection methods (ReliefF and CFS).

Sentiment analysis is the task of determining the opinion expressed on subjective data, which may include microblog messages, such as tweets. This type of message has been considered the target of sentiment analysis in many recent studies, since they represent a rich source of opinionated texts. Thus, in order to determine the opinion expressed in tweets, different studies have employed distinct strategies, which mainly include supervised machine learning methods. For this purpose, different kinds of features have been evaluated. Despite that, none of the state-of-the-art studies has evaluated distinct categories of features, regarding their similar characteristics. In this context, this work presents a literature review of the most common feature representation in Twitter sentiment analysis. We propose to group features sharing similar aspects into specific categories. We also evaluate the relevance of these categories of features, including meta-level features, using a significant number of Twitter datasets. Furthermore, we apply important and well-known feature selection strategies in order to identify relevant subsets of features for each dataset. We show in the experimental evaluation that the results achieved in this study, using feature selection strategies, outperform the results reported in previous works for the most of the assessed datasets.

The scope of this work is the application of data mining techniques to improve the performance of metaheuristics in the combinatorial optimization scenario. Data mining techniques have been coupled with metaheuristics in order to obtain patterns of suboptimal solutions that are used to guide the he uristic search for better-cost solutions in less computational time. This kind of hybridization has been successfully explored to solve several optimization problems, for which the solutions and their patterns are limitedly characterized by sets of elements. The challenge of this work is to extend this hybrid approach to a broader domain. We therefore propose a hybrid data mining heuristic to solve the one-commodity pickup-and-delivery traveling salesman problem, for which solutions are defined by sequences of elements. Computational experiments, conducted on a set of instances from the literature, showed that the hybrid heuristic reached better-costs solutions faster than the original strategy. This way, it was evidenced that not only problems whose solutions are represented by sets of elements can benefit from the hybridization of metaheuristics with data mining, but also problems whose solutions are represented by a sequence of elements.

Multi-label classification (MLC) is the task of assigning multiple class labels to an object based on the features that describe the object. One of the most effective MLC methods is known as Classifier Chains (CC). This approach consists in training q binary classifiers linked in a chain, y1 → y2 → ... → yq, with each responsible for classifying a specific label in {l1, l2, ..., lq}. The chaining mechanism allows each individual classifier to incorporate the predictions of the previous ones as additional information at classification time. Thus, possible correlations among labels can be automatically exploited. Nevertheless, CC suffers from two important drawbacks: (i) the label ordering is decided at random, although it usually has a strong effect on predictive accuracy; (ii) all labels are inserted into the chain, although some of them might carry irrelevant information to discriminate the others. In this paper we tackle both problems at once, by proposing a novel genetic algorithm capable of searching for a single optimized label ordering, while at the same time taking into consideration the utilization of partial chains. Experiments on benchmark datasets demonstrate that our approach is able to produce models that are both simpler and more accurate.

When developers want to contribute to an opensource project, they fork the repository, make changes, and send a pull request to the core team to incorporate these changes back into the repository. However, some projects enforce this collaboration model even for changes made by core team developers. This potentially enhances the quality of the repository by adding an inspection step before accepting a contribution into the repository. In this context, though less frequently, the contributions may be rejected. The understanding of the factors that lead to the rejection of these internal contributions is crucial for the improvement of the ways core developers collaborate, having a direct impact on the team productivity. In this work we extract association rules from pull request data stored in software repositories in order to find factors that have influence over the decision of rejecting contributions made by core developers. In addition, we present a qualitative analysis of some cases, helping to understand the patterns that arose from the association rules. The results indicate that some key factors increase the changes of having internal contributions rejected: (i) the inexperience with pull requests, (ii) the complexity of contributions, as well as the locality of the artifacts that have been modified, and (iii) the contribution policy of the projects.

First proposed in 2009, the classifier chains model (CC) has become one of the most influential algorithms for multi-label classification. It is distinguished by its simple and effective approach to exploit label dependencies. The CC method involves the training of q single-label binary classifiers, where each one is solely responsible for classifying a specific label in ll, ..., lq. These q classifiers are linked in a chain, such that each binary classifier is able to consider the labels predicted by the previous ones as additional information at classification time. The label ordering has a strong effect on predictive accuracy, however it is decided at random and/or combining random orders via an ensemble. A disadvantage of the ensemble approach consists of the fact that it is not suitable when the goal is to generate interpretable classifiers. To tackle this problem, in this work we propose a genetic algorithm for optimizing the label ordering in classifier chains. Experiments on diverse benchmark datasets, followed by the Wilcoxon test for assessing statistical significance, indicate that the proposed strategy produces more accurate classifiers.

Attribute selection is a data preprocessing step which aims at identifying relevant attributes for the target machine learning task – namely classification in this paper. In this paper, we propose a new attribute selection strategy – based on a lazy

Metaheuristics represent an important class of techniques to solve, approximately, hard combinatorial optimization problems for which the use of exact methods is impractical. In this work, we propose a hybrid version of the GRASP metaheuristic, which incorporates a data mining process, to solve the p-median problem. We believe that patterns obtained by a data mining technique, from a set of sub-optimal solutions of a combinatorial optimization problem, can be used to guide metaheuristic procedures in the search for better solutions. Traditional GRASP is an iterative metaheuristic which returns the best solution reached over all iterations. In the hybrid GRASP proposal, after executing a significant number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the p-median problem. These patterns present characteristics of near optimal solutions and can be used to guide the following GRASP iterations in the search through the combinatorial solution space. Computational experiments, comparing traditional GRASP and different data mining hybrid proposals for the p-median problem, showed that employing patterns mined from an elite set of sub-optimal solutions made the hybrid GRASP find better results. Besides, the conducted experiments also evidenced that incorporating a data mining technique into a metaheuristic accelerated the process of finding near optimal and optimal solutions.

Multicast communication is a topic of intense study by the network research community. The IP Multicast service of the network layer doesn't provide the desired reliability to some multicast applications, and the interest towards approaches to reliable multicast communication has increased. In this work, we focus on the Server Replication method, wherein the data are replicated over a subset of the multicast-capable relaying hosts and retransmission requests from receivers are handled by the nearest Replicated Server. The problem of selecting the best subset of the multicast-capable relaying hosts to replicate the data is NP-Hard. We propose a hybrid metaheuristic to find near optimal solutions for this problem. This proposal is based on a hybrid version of the GRASP metaheuristic that incorporates data mining techniques. Experimental results show that our technique outperforms existing approaches.