PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-objective Feature Selection with Missing Data in Classification

Yu Xue, Yihang Tang, Xin Xu, Jiayu Liang, Ferrante Neri

arXiv:2104.08747v1cs.AI

TL;DR

Feature selection commonly balances classification accuracy and feature count, while missing data is a concern in incomplete datasets. This paper adds missing rate as a reliability objective and applies NSGA-III; on six incomplete UCI datasets, it reports overall superiority over the compared methods in IGD and HV.

  • Problem

    Feature selection often balances classification accuracy and solution size, while missing data is common and can make selected features unreliable.

    Source: §I · pp. 1–2, §VI · p. 9

  • Method

    The paper uses mean imputation, adds missing rate as a third objective alongside classification error and solution size, and applies NSGA-III.

    Source: §I · p. 2, §III · p. 3, §VI · p. 9

  • Results

    On six incomplete UCI datasets, NSGA-III showed overall superiority to the compared methods in IGD and HV.

    Source: §VI · p. 9

  • Takeaways & Limitations

    The study concludes that NSGA-III performs better for three-objective feature selection on the incomplete datasets tested.

    Source: §V · p. 6, §VI · p. 9

    The authors state that their NSGA-III implementation has room for improvement.

    Source: §VI · p. 9

Abstract

from arXiv · show

Feature selection (FS) is an important research topic in machine learning. Usually, FS is modelled as a+ bi-objective optimization problem whose objectives are: 1) classification accuracy; 2) number of features. One of the main issues in real-world applications is missing data. Databases with missing data are likely to be unreliable. Thus, FS performed on a data set missing some data is also unreliable. In order to directly control this issue plaguing the field, we propose in this study a novel modelling of FS: we include reliability as the third objective of the problem. In order to address the modified problem, we propose the application of the non-dominated sorting genetic algorithm-III (NSGA-III). We selected six incomplete data sets from the University of California Irvine (UCI) machine learning repository. We used the mean imputation method to deal with the missing data. In the experiments, k-nearest neighbors (K-NN) is used as the classifier to evaluate the feature subsets. Experimental results show that the proposed three-objective model coupled with NSGA-III efficiently addresses the FS problem for the six data sets included in this study.

I. INTRODUCTION

Feature selection removes irrelevant or redundant features, but much prior work considered complete data and commonly balanced classification accuracy against solution size. For incomplete data, this paper uses mean imputation and adds missing rate as a third optimization objective, addressed with NSGA-III.

I. INTRODUCTION

  • Feature selection identifies and eliminates irrelevant or redundant features that can lower classification performance and increase computational cost.Without prior information about the data, such features can be difficult to identify.Source: §I · p. 1
  • Earlier multi-objective feature-selection studies considered accuracy and solution size, while many studies assumed complete data.The paper notes that missing data can make selected features unreliable.Source: §I · p. 2

II. MEAN IMPUTATION METHOD

  • Mean imputation replaces each missing value with the average of available values for that feature.The authors select it as a low-complexity approach suited to large data sets.Source: §I · p. 2, §II · p. 2

I. INTRODUCTION

  • The proposed model adds missing rate to classification accuracy and solution size, making reliability a third feature-selection objective.The paper proposes NSGA-III to address the increased problem complexity.Source: §I · p. 2

III. THREE-OBJECTIVE FEATURE SELECTION PROBLEMS AND NSGA-III ALGORITHM

The paper formulates feature selection as a three-objective optimization problem, evaluating classification error, solution size, and missing rate. Candidate solutions encode feature choices, and the missing-rate objective assesses the reliability of selected features.

III. THREE-OBJECTIVE FEATURE SELECTION PROBLEMS AND NSGA-III ALGORITHM

  • A candidate solution is a real-valued vector aligned with the data-set features, and a threshold converts its values into binary selection decisions.Values above the threshold select a feature; values below it discard the feature.Source: §III · pp. 2–3
  • The classification-error objective is evaluated with 5-nearest neighbors and 10-fold cross-validation.The paper uses classification error rate for comparison through the non-dominance relation.Source: §III · p. 3
  • The three objectives assess classification accuracy, solution size, and missing rate to account for the reliability of selected features.The paper formulates classification error rate as its first objective and defines missing rate relative to missing data in the original set.Source: §III · p. 3
  • The missing-rate objective uses the missing-value count in selected features relative to the missing data in the original set.The selected feature indices are stored in vector y before the selected-set count is calculated.Source: §III · p. 3

A. NSGA-III algorithm

NSGA-III combines non-dominated sorting with reference-point-based selection. Its procedure generates and combines parent and offspring populations, then uses reference points when rank-based selection cannot fill the next population.

A. NSGA-III algorithm

  • The algorithm’s stated input is reference points and a parent population, and its output is the next population.Source: A. NSGA-III algorithm · p. 3
  • NSGA-III generates offspring through binary crossover and polynomial mutation, combines them with the parents, and applies fast non-dominated sorting.It selects N individuals for the next population.Source: A. NSGA-III algorithm · p. 3
  • Reference-point-based selection resolves cases where non-dominated rank alone cannot select the required individuals.The algorithm begins by constructing reference points and an initialization population.Source: A. NSGA-III algorithm · p. 3

B. Fast non-donminated sorting

Fast non-dominated sorting ranks individuals by dominance, using domination counts and dominated-individual lists to construct successive fronts.

B. Fast non-donminated sorting

  • The algorithm compares each individual with the others, recording whom it dominates in Sp and how many dominate it in np.It initializes Sp as empty and np as zero for each individual.Source: B. Fast non-donminated sorting · p. 3
  • Individuals with np = 0 enter the first front, F1.The procedure then reduces the domination counts of individuals dominated by members of each front, adding those reaching zero to the next front.Source: B. Fast non-donminated sorting · p. 4
  • The process repeats front by front until no further fronts remain.The described stopping condition is Fi = φ.Source: B. Fast non-donminated sorting · p. 4

C. Selection method based on reference points

When rank alone cannot fill the next population, NSGA-III uses reference points to select individuals and maintain diversity across objectives.

C. Selection method based on reference points

  • Reference-point selection supplements non-dominated ranking when rank alone cannot select enough individuals for the next generation.The method constructs reference points following Das and Denniss.Source: C. Selection method based on reference… · p. 4
  • For three objectives, the reference points lie on an equilateral triangle, with each objective divided into P parts.The described set contains (P + M − 1) reference points; Fig. 1 illustrates four divisions per objective.Source: C. Selection method based on reference… · p. 4, Figure 1 · p. 5
  • Each individual is associated with the reference point whose reference line is closest, using the vertical distance V.The reference line runs between the reference point and the ideal point.Source: C. Selection method based on reference… · p. 4
  • Selection from the last front favors underrepresented reference points, choosing the shortest-distance individual when no earlier front is associated with that point.If earlier fronts already associate with the point, an associated individual is selected randomly.Source: C. Selection method based on reference… · p. 5

IV. EXPERIMENTAL SETUP

The experimental setup uses six incomplete UCI datasets, whose reported missing rates extend up to 24.9%.

IV. EXPERIMENTAL SETUP

  • The experiments use six incomplete datasets from the UCI Machine Learning Repository.Table I is identified as presenting the dataset information.Source: §IV · p. 5
  • 24.9% is the highest missing rate among the six datasets.The dataset descriptions include sample counts, dimensions, class counts, and missing rates.Source: §IV · p. 5

A. Preparation work

Preparation uses mean imputation before splitting each dataset into training and test sets, with K-NN evaluating feature subsets.

A. Preparation work

  • The preparation applies mean imputation to fill missing dataset values before dividing each dataset into training and test sets.A random 70% of examples form the training set, and the remainder form the test set.Source: A. Preparation work · p. 5
  • K-NN evaluates feature-subset fitness, while 10-fold cross-validation measures classification accuracy.Source: A. Preparation work · p. 5

B. Benchmark algorithms and parameter settings

The study compares NSGA-III with four algorithms on six data sets, using repeated runs with a fixed fitness-evaluation budget and specified settings.

B. Benchmark algorithms and parameter settings

C. Performance metrics

The study uses IGD and hyper-volume to evaluate multi-objective algorithm performance, with IGD reflecting solution distribution and convergence and HV assessing several aspects of solution-set quality.

C. Performance metrics

  • Inverted generational distance (IGD) is introduced as one indicator for evaluating NSGA-III on multi-objective feature-selection problems.Source: C. Performance metrics · p. 5
  • IGD measures the minimum Euclidean distance from each objective-set individual to the non-dominated solution set; smaller values indicate better distribution and convergence.Source: C. Performance metrics · p. 5
  • Hyper-volume (HV) evaluates convergence, extensiveness, and distribution of a multi-objective algorithm’s solution set.Source: C. Performance metrics · p. 5

V. EXPERIMENTAL RESULTS

Across six data sets, NSGA-III outperforms NSGA-II, SPEA-II and IBEA on IGD, and is similar to KnEA; HV results favor NSGA-III in most cases. Its non-dominated solutions are more uniform, with better performance across classification accuracy, solution size and missing rate on training and test sets.

V. EXPERIMENTAL RESULTS

  • The tables report mean and standard deviation; bold marks the best mean, while T-sig reports 95%-confidence T-test comparisons using +, − or =.Source: §V · p. 5
  • On training and test sets, NSGA-III outperforms NSGA-II, SPEA-II and IBEA on IGD, while performing similarly to KnEA.The training-set comparison finds significant advantages over NSGA-II on five data sets and similar performance on one.Source: Table II · p. 6, Table III · p. 6, §V · p. 6
  • The authors attribute the more uniform solutions to NSGA-III’s reference-point system, which spreads offspring through the objective space and increases diversity.Source: §V · pp. 6, 9
  • NSGA-III’s non-dominated solutions are more uniform and perform better on classification accuracy, solution size and missing rate across training and test sets.Fig. 2 covers training sets and Fig. 3 covers test sets; their axes represent classification error, solution size and missing rate.Source: §V · p. 6, Figure 2 · p. 7, Figure 3 · p. 8
  • On test sets, NSGA-III has higher HV than other algorithms in most cases; on training sets it beats SPEA-II on four and IBEA and KnEA on five.For training sets, it is significantly better than NSGA-II on three data sets and similar on two.Source: §V · p. 6, Table V · p. 9, Table IV · p. 9

VI. CONCLUSION

The paper models feature selection on incomplete data as a three-objective problem, adding missing rate to accuracy and solution size, and addresses it with an adapted NSGA-III. On six incomplete UCI data sets, NSGA-III showed overall superiority to the compared methods in IGD and HV; the authors identify further improvement as future work.

VI. CONCLUSION

  • The model adds missing rate as a third feature-selection objective alongside accuracy and solution size, and addresses the resulting problem with an adapted NSGA-III.Source: §VI · p. 9
  • On six incomplete UCI data sets, NSGA-III showed overall superiority to the four compared algorithms in IGD and HV.Source: §VI · p. 9
  • The authors see room to improve their NSGA-III implementation and identify integration of knowledge-based feature information into its selection mechanism as future work.Source: §VI · p. 9

Related papers

Loading 2104.08747v1…