Feature Selection for Multi-label Learning: A Systematic Literature Review and Some Experimental Evaluations
---
paper_title: Computational Methods of Feature Selection

paper_content:

PREFACE Introduction and Background Less Is More Huan Liu and Hiroshi Motoda Background and Basics Supervised, Unsupervised, and Semi-Supervised Feature Selection Key Contributions and Organization of the Book Looking Ahead Unsupervised Feature Selection Jennifer G. Dy Introduction Clustering Feature Selection Feature Selection for Unlabeled Data Local Approaches Summary Randomized Feature Selection David J. Stracuzzi Introduction Types of Randomizations Randomized Complexity Classes Applying Randomization to Feature Selection The Role of Heuristics Examples of Randomized Selection Algorithms Issues in Randomization Summary Causal Feature Selection Isabelle Guyon, Constantin Aliferis, and Andre Elisseeff Introduction Classical "Non-Causal" Feature Selection The Concept of Causality Feature Relevance in Bayesian Networks Causal Discovery Algorithms Examples of Applications Summary, Conclusions, and Open Problems Extending Feature Selection Active Learning of Feature Relevance Emanuele Olivetti, Sriharsha Veeramachaneni, and Paolo Avesani Introduction Active Sampling for Feature Relevance Estimation Derivation of the Sampling Benefit Function Implementation of the Active Sampling Algorithm Experiments Conclusions and Future Work A Study of Feature Extraction Techniques Based on Decision Border Estimate Claudia Diamantini and Domenico Potena Introduction Feature Extraction Based on Decision Boundary Generalities about Labeled Vector Quantizers Feature Extraction Based on Vector Quantizers Experiments Conclusions Ensemble-Based Variable Selection Using Independent Probes Eugene Tuv, Alexander Borisov, and Kari Torkkola Introduction Tree Ensemble Methods in Feature Ranking The Algorithm: Ensemble-Based Ranking against Independent Probes Experiments Discussion Efficient Incremental-Ranked Feature Selection in Massive Data Roberto Ruiz, Jesus S. Aguilar-Ruiz, and Jose C. Riquelme Introduction Related Work Preliminary Concepts Incremental Performance over Ranking Experimental Results Conclusions Weighting and Local Methods Non-Myopic Feature Quality Evaluation with (R)ReliefF Igor Kononenko and Marko Robnik Sikonja Introduction From Impurity to Relief ReliefF for Classification and RReliefF for Regression Extensions Interpretation Implementation Issues Applications Conclusion Weighting Method for Feature Selection in k-Means Joshua Zhexue Huang, Jun Xu, Michael Ng, and Yunming Ye Introduction Feature Weighting in k-Means W-k-Means Clustering Algorithm Feature Selection Subspace Clustering with k-Means Text Clustering Related Work Discussions Local Feature Selection for Classification Carlotta Domeniconi and Dimitrios Gunopulos Introduction The Curse of Dimensionality Adaptive Metric Techniques Large Margin nearest Neighbor Classifiers Experimental Comparisons Conclusions Feature Weighting through Local Learning Yijun Sun Introduction Mathematical Interpretation of Relief Iterative Relief Algorithm Extension to Multiclass Problems Online Learning Computational Complexity Experiments Conclusion Text Classification and Clustering Feature Selection for Text Classification George Forman Introduction Text Feature Generators Feature Filtering for Classification Practical and Scalable Computation A Case Study Conclusion and Future Work A Bayesian Feature Selection Score Based on Naive Bayes Models Susana Eyheramendy and David Madigan Introduction Feature Selection Scores Classification Algorithms Experimental Settings and Results Conclusion Pairwise Constraints-Guided Dimensionality Reduction Wei Tang and Shi Zhong Introduction Pairwise Constraints-Guided Feature Projection Pairwise Constraints-Guided Co-Clustering Experimental Studies Conclusion and Future Work Aggressive Feature Selection by Feature Ranking Masoud Makrehchi and Mohamed S. Kamel Introduction Feature Selection by Feature Ranking Proposed Approach to Reducing Term Redundancy Experimental Results Summary Feature Selection in Bioinformatics Feature Selection for Genomic Data Analysis Lei Yu Introduction Redundancy-Based Feature Selection Empirical Study Summary A Feature Generation Algorithm with Applications to Biological Sequence Classification Rezarta Islamaj Dogan, Lise Getoor, and W. John Wilbur Introduction Splice-Site Prediction Feature Generation Algorithm Experiments and Discussion Conclusions An Ensemble Method for Identifying Robust Features for Biomarker Discovery Diana Chan, Susan M. Bridges, and Shane C. Burgess Introduction Biomarker Discovery from Proteome Profiles Challenges of Biomarker Identification Ensemble Method for Feature Selection Feature Selection Ensemble Results and Discussion Conclusion Model Building and Feature Selection with Genomic Data Hui Zou and Trevor Hastie Introduction Ridge Regression, Lasso, and Bridge Drawbacks of the Lasso The Elastic Net The Elastic-Net Penalized SVM Sparse Eigen-Genes Summary INDEX
---
paper_title: A Review on Multi-Label Learning Algorithms

paper_content:

Multi-label learning studies the problem where each example is represented by a single instance while associated with a set of labels simultaneously. During the past decade, significant amount of progresses have been made toward this emerging machine learning paradigm. This paper aims to provide a timely review on this area with emphasis on state-of-the-art multi-label learning algorithms. Firstly, fundamentals on multi-label learning including formal definition and evaluation metrics are given. Secondly and primarily, eight representative multi-label learning algorithms are scrutinized under common notations with relevant analyses and discussions. Thirdly, several related learning settings are briefly summarized. As a conclusion, online resources and open research problems on multi-label learning are outlined for reference purposes.
---
paper_title: Data Mining Concepts and Techniques

paper_content:

Understand the need for analyses of large, complex, information-rich data sets. Identify the goals and primary tasks of the data-mining process. Describe the roots of data-mining technology. Recognize the iterative character of a data-mining process and specify its basic steps. Explain the influence of data quality on a data-mining process. Establish the relation between data warehousing and data mining. Data mining is an iterative process within which progress is defined by discovery, through either automatic or manual methods. Data mining is most useful in an exploratory analysis scenario in which there are no predetermined notions about what will constitute an "interesting" outcome. Data mining is the search for new, valuable, and nontrivial information in large volumes of data. It is a cooperative effort of humans and computers. Best results are achieved by balancing the knowledge of human experts in describing problems and goals with the search capabilities of computers. In practice, the two primary goals of data mining tend to be prediction and description. Prediction involves using some variables or fields in the data set to predict unknown or future values of other variables of interest. Description, on the other hand, focuses on finding patterns describing the data that can be interpreted by humans. Therefore, it is possible to put data-mining activities into one of two categories: Predictive data mining, which produces the model of the system described by the given data set, or Descriptive data mining, which produces new, nontrivial information based on the available data set.
---
paper_title: A Review on Multi-Label Learning Algorithms

paper_content:

Multi-label learning studies the problem where each example is represented by a single instance while associated with a set of labels simultaneously. During the past decade, significant amount of progresses have been made toward this emerging machine learning paradigm. This paper aims to provide a timely review on this area with emphasis on state-of-the-art multi-label learning algorithms. Firstly, fundamentals on multi-label learning including formal definition and evaluation metrics are given. Secondly and primarily, eight representative multi-label learning algorithms are scrutinized under common notations with relevant analyses and discussions. Thirdly, several related learning settings are briefly summarized. As a conclusion, online resources and open research problems on multi-label learning are outlined for reference purposes.
---
paper_title: An Empirical Study of Lazy Multilabel Classification Algorithms

paper_content:

Multilabel classification is a rapidly developing field of machine learning. Despite its short life, various methods for solving the task of multilabel classification have been proposed. In this paper we focus on a subset of these methods that adopt a lazy learning approach and are based on the traditional k-nearest neighbor (k NN) algorithm. Two are our main contributions. Firstly, we implement BRk NN, an adaptation of the k NN algorithm for multilabel classification that is conceptually equivalent to using the popular Binary Relevance problem transformation method in conjunction with the k NN algorithm, but much faster. We also identify two useful extensions of BRk NN that improve its overall predictive performance. Secondly, we compare this method against two other lazy multilabel classification methods, in order to determine the overall best performer. Experiments on different real-world multilabel datasets, using a variety of evaluation metrics, expose the advantages and limitations of each method with respect to specific dataset characteristics.
---
paper_title: Lazy Multi-label Learning Algorithms Based on Mutuality Strategies

paper_content:

Lazy multi-label learning algorithms have become an important research topic within the multi-label community. These algorithms usually consider the set of standard k-Nearest Neighbors of a new instance to predict its labels (multi-label). The prediction is made by following a voting criteria within the multi-labels of the set of k-Nearest Neighbors of the new instance. This work proposes the use of two alternative strategies to identify the set of these examples: the Mutual and Not Mutual Nearest Neighbors rules, which have already been used by lazy single-learning algorithms. In this work, we use these strategies to extend the lazy multi-label algorithm BRkNN. An experimental evaluation carried out to compare both mutuality strategies with the original BRkNN algorithm and the well-known MLkNN lazy algorithm on 15 benchmark datasets showed that MLkNN presented the best predictive performance for the Hamming-Loss evaluation measure, although it was significantly outperformed by the mutuality strategies when F-Measure is considered. The best results of the lazy algorithms were also compared with the results obtained by the Binary Relevance approach using three different base learning algorithms.
---
paper_title: A Review on Multi-Label Learning Algorithms

paper_content:

Multi-label learning studies the problem where each example is represented by a single instance while associated with a set of labels simultaneously. During the past decade, significant amount of progresses have been made toward this emerging machine learning paradigm. This paper aims to provide a timely review on this area with emphasis on state-of-the-art multi-label learning algorithms. Firstly, fundamentals on multi-label learning including formal definition and evaluation metrics are given. Secondly and primarily, eight representative multi-label learning algorithms are scrutinized under common notations with relevant analyses and discussions. Thirdly, several related learning settings are briefly summarized. As a conclusion, online resources and open research problems on multi-label learning are outlined for reference purposes.
---
paper_title: Evaluating ReliefF-Based Multi-Label Feature Selection Algorithm

paper_content:

In multi-label learning, each instance is associated with multiple labels, which are often correlated. As other machine learning tasks, multi-label learning also suffers from the curse of dimensionality, which can be mitigated by feature selection. This work experimentally evaluates four multi-label feature selection algorithms that use the filter approach. Three of them are based on the ReliefF algorithm, which takes into account interacting features. The quality of the selected features is assessed by three different learning algorithms. Evaluating multi-label learning algorithms is a complicated task, as multiple evaluation measures, which might optimize different loss functions, should be considered. To this end, \(General_B\), a baseline algorithm which learns by only looking at the multi-labels of the dataset, is used as a reference. Results show that feature selection contributed to improve the performance of classifiers initially worse than \(General_B\) and highlight ReliefF-based algorithms in some experimental settings.
---
paper_title: A Framework to Generate Synthetic Multi-label Datasets

paper_content:

A controlled environment based on known properties of the dataset used by a learning algorithm is useful to empirically evaluate machine learning algorithms. Synthetic (artificial) datasets are used for this purpose. Although there are publicly available frameworks to generate synthetic single-label datasets, this is not the case for multi-label datasets, in which each instance is associated with a set of labels usually correlated. This work presents Mldatagen, a multi-label dataset generator framework we have implemented, which is publicly available to the community. Currently, two strategies have been implemented in Mldatagen: hypersphere and hypercube. For each label in the multi-label dataset, these strategies randomly generate a geometric shape (hypersphere or hypercube), which is populated with points (instances) randomly generated. Afterwards, each instance is labeled according to the shapes it belongs to, which defines its multi-label. Experiments with a multi-label classification algorithm in six synthetic datasets illustrate the use of Mldatagen.
---
paper_title: Label Construction for Multi-label Feature Selection

paper_content:

Multi-label learning handles datasets where each instance is associated with multiple labels, which are often correlated. As other machine learning tasks, multi-label learning also suffers from the curse of dimensionality, which can be mitigated by dimensionality reduction tasks, such as feature selection. The standard approach for multi-label feature selection transforms the multi-label dataset into single-label datasets before using traditional feature selection algorithms. However, this approach often ignores label dependence. This work proposes an alternative method, LCFS, which constructs new labels based on relations between the original labels to augment the label set of the original dataset. Afterwards, the augmented dataset is submitted to the standard multi-label feature selection approach. Experiments using Information Gain as a measure to evaluate features were carried out in 10 multi-label benchmark datasets. For each dataset, the quality of the features selected was assessed by the quality of the classifiers built using the features selected by the standard approach in the original dataset, as well as in the dataset constructed by four LCFS settings. The results show that setting LCFS with simple strategies using pairs of labels gives rise to better classifiers than the ones built using the standard approach in the original dataset. Moreover, these good results are accomplished when a small number of features are selected.
---
paper_title: Data Mining: Practical Machine Learning Tools and Techniques

paper_content:

Data Mining: Practical Machine Learning Tools and Techniques offers a thorough grounding in machine learning concepts as well as practical advice on applying machine learning tools and techniques in real-world data mining situations. This highly anticipated third edition of the most acclaimed work on data mining and machine learning will teach you everything you need to know about preparing inputs, interpreting outputs, evaluating results, and the algorithmic methods at the heart of successful data mining. Thorough updates reflect the technical changes and modernizations that have taken place in the field since the last edition, including new material on Data Transformations, Ensemble Learning, Massive Data Sets, Multi-instance Learning, plus a new version of the popular Weka machine learning software developed by the authors. Witten, Frank, and Hall include both tried-and-true techniques of today as well as methods at the leading edge of contemporary research. *Provides a thorough grounding in machine learning concepts as well as practical advice on applying the tools and techniques to your data mining projects *Offers concrete tips and techniques for performance improvement that work by transforming the input or output in machine learning methods *Includes downloadable Weka software toolkit, a collection of machine learning algorithms for data mining tasks-in an updated, interactive interface. Algorithms in toolkit cover: data pre-processing, classification, regression, clustering, association rules, visualization
---
paper_title: Label Construction for Multi-label Feature Selection

paper_content:

Multi-label learning handles datasets where each instance is associated with multiple labels, which are often correlated. As other machine learning tasks, multi-label learning also suffers from the curse of dimensionality, which can be mitigated by dimensionality reduction tasks, such as feature selection. The standard approach for multi-label feature selection transforms the multi-label dataset into single-label datasets before using traditional feature selection algorithms. However, this approach often ignores label dependence. This work proposes an alternative method, LCFS, which constructs new labels based on relations between the original labels to augment the label set of the original dataset. Afterwards, the augmented dataset is submitted to the standard multi-label feature selection approach. Experiments using Information Gain as a measure to evaluate features were carried out in 10 multi-label benchmark datasets. For each dataset, the quality of the features selected was assessed by the quality of the classifiers built using the features selected by the standard approach in the original dataset, as well as in the dataset constructed by four LCFS settings. The results show that setting LCFS with simple strategies using pairs of labels gives rise to better classifiers than the ones built using the standard approach in the original dataset. Moreover, these good results are accomplished when a small number of features are selected.
---
paper_title: ReliefF-ML: An Extension of ReliefF Algorithm to Multi-label Learning

paper_content:

In the last years, the learning from multi-label data has attracted significant attention from a lot of researchers, motivated from an increasing number of modern applications that contain this type of data. Several methods have been proposed for solving this problem, however how to make feature weighting on multi-label data is still lacking in the literature. In multi-label data, each data point can be attributed to multiple labels simultaneously, thus a major difficulty lies in the determinations of the features useful for all multi-label concepts. In this paper, a new method for feature weighting in multi-label learning area is presented, based on the principles of the well-known ReliefF algorithm. The experimental stage shows the effectiveness of the proposal.
---
paper_title: Theoretical and Empirical Analysis of ReliefF and RReliefF

paper_content:

Relief algorithms are general and successful attribute estimators. They are able to detect conditional dependencies between attributes and provide a unified view on the attribute estimation in regression and classification. In addition, their quality estimates have a natural interpretation. While they have commonly been viewed as feature subset selection methods that are applied in prepossessing step before a model is learned, they have actually been used successfully in a variety of settings, e.g., to select splits or to guide constructive induction in the building phase of decision or regression tree learning, as the attribute weighting method and also in the inductive logic programming. ::: ::: A broad spectrum of successful uses calls for especially careful investigation of various features Relief algorithms have. In this paper we theoretically and empirically investigate and discuss how and why they work, their theoretical and practical properties, their parameters, what kind of dependencies they detect, how do they scale up to large number of examples and features, how to sample data for them, how robust are they regarding the noise, how irrelevant and redundant attributes influence their output and how different metrics influences them.
---
paper_title: Evaluating ReliefF-Based Multi-Label Feature Selection Algorithm

paper_content:

In multi-label learning, each instance is associated with multiple labels, which are often correlated. As other machine learning tasks, multi-label learning also suffers from the curse of dimensionality, which can be mitigated by feature selection. This work experimentally evaluates four multi-label feature selection algorithms that use the filter approach. Three of them are based on the ReliefF algorithm, which takes into account interacting features. The quality of the selected features is assessed by three different learning algorithms. Evaluating multi-label learning algorithms is a complicated task, as multiple evaluation measures, which might optimize different loss functions, should be considered. To this end, \(General_B\), a baseline algorithm which learns by only looking at the multi-labels of the dataset, is used as a reference. Results show that feature selection contributed to improve the performance of classifiers initially worse than \(General_B\) and highlight ReliefF-based algorithms in some experimental settings.
---
paper_title: A STABILITY INDEX FOR FEATURE SELECTION

paper_content:

Sequential forward selection (SFS) is one of the most widely used feature selection procedures. It starts with an empty set and adds one feature at each step. The estimate of the quality of the candidate subsets usually depends on the training/testing split of the data. Therefore different sequences of features may be returned from repeated runs of SFS. A substantial discrepancy between such sequences will signal a problem with the selection. A stability index is proposed here based on cardinality of the intersection and a correction for chance. The experimental results with 10 real data sets indicate that the index can be useful for selecting the final feature subset. If stability is high, then we should return a subset of features based on their total rank across the SFS runs. If stability is low, then it is better to return the feature subset which gave the minimum error across all SFS runs.
---

Title: Feature Selection for Multi-label Learning: A Systematic Literature Review and Some Experimental Evaluations
Section 1: Introduction
Description 1: This section introduces the importance of feature selection in data mining, the challenges of multi-label data, and the aim of the paper.

Section 2: Multi-label learning
Description 2: This section defines multi-label learning, describes learning methods, and discusses multi-label evaluation measures considered in the work.

Section 3: Multi-label feature selection
Description 3: This section discusses the systematic review of the literature on multi-label feature selection, categorizes the publications, and highlights prevalent approaches.

Section 4: Problem transformation-based feature selection
Description 4: This section describes problem transformation approaches for multi-label feature selection, focusing on methods like Binary Relevance (BR) and Label Powerset (LP).

Section 5: ReliefF algorithm adaptation for multi-label feature selection
Description 5: This section explores the proposed ReliefF-based extensions (RF-ML and RFM-ML) for multi-label feature selection and evaluates them experimentally.

Section 6: Conclusion
Description 6: This section summarizes the key contributions, findings, and limitations of the research, and suggests directions for future work.