PaperlayerView exact revision on arXiv

Source-linked AI summary

A Novel Community Detection Based Genetic Algorithm for Feature Selection

Mehrdad Rostami, Kamal Berahmand, Saman Forouzandeh

arXiv:2008.03543v1cs.LGcs.NEstat.ML

TL;DR

Feature selection must remove irrelevant and redundant variables from high-dimensional data, but existing meta-heuristics may neglect correlations among selected features. The paper proposes a community-detection-based genetic algorithm that clusters similar features and repairs genetic solutions accordingly. Across benchmark classification experiments, the authors report continuously improved classification accuracy compared with available feature-selection algorithms.

  • Problem

    Existing feature-selection methods may remove irrelevant features while neglecting redundancy and correlations among selected features in high-dimensional datasets.

  • Method

    CGAFS calculates feature similarities, clusters features with community detection, and uses a genetic algorithm with community-based repair operations and a multi-objective fitness function.

  • Results

    The authors report continuously improved classification accuracy across benchmark classification problems compared with available feature-selection algorithms.

  • Takeaways & Limitations

    The approach integrates relevance, redundancy, feature clustering, and feature-subset-size selection within a genetic feature-selection framework.

  • Takeaways & Limitations

    The method uses user-specified parameters that were selected after preliminary implementation and were not intended to be optimum.

Abstract

from arXiv · show

The selection of features is an essential data preprocessing stage in data mining. The core principle of feature selection seems to be to pick a subset of possible features by excluding features with almost no predictive information as well as highly associated redundant features. In the past several years, a variety of meta-heuristic methods were introduced to eliminate redundant and irrelevant features as much as possible from high-dimensional datasets. Among the main disadvantages of present meta-heuristic based approaches is that they are often neglecting the correlation between a set of selected features. In this article, for the purpose of feature selection, the authors propose a genetic algorithm based on community detection, which functions in three steps. The feature similarities are calculated in the first step. The features are classified by community detection algorithms into clusters throughout the second step. In the third step, features are picked by a genetic algorithm with a new community-based repair operation. Nine benchmark classification problems were analyzed in terms of the performance of the presented approach. Also, the authors have compared the efficiency of the proposed approach with the findings from four available algorithms for feature selection. The findings indicate that the new approach continuously yields improved classification accuracy.

1. Introduction

High-dimensional data make feature selection necessary because computational costs and overfitting risks increase, while existing genetic approaches may ignore feature connections. The proposed CGAFS integrates community detection with genetic search to reduce redundancy and determine feature-subset size automatically.

  • Motivation: High-dimensional datasets increase computational costs and overfitting risk, making dimensionality reduction essential when training examples are limited.The introduction states that classification problems may require at least 10×D×C training examples, and feature reduction decreases the needed sample size.
  • Proposed approach: CGAFS uses community detection to divide features into clusters before genetic selection, addressing feature connections that conventional genetic selection may overlook.The approach integrates community detection structurally into a GA-based wrapper model rather than applying filters and wrappers sequentially.
  • Proposed approach: Community-based repair operations modify offspring chromosomes to eliminate related features selected from the same feature structure.The repair operator uses predetermined feature clusters when repairing newly produced offspring.
  • Novelty: The method identifies feature clusters automatically instead of requiring the number of clusters in advance, unlike k-means and fuzzy c-means.Grouping similar features is intended to prevent redundant feature selection.
  • Novelty: CGAFS determines the optimal number of selected features from the original feature structure and inner similarities rather than requiring that number beforehand.The introduction frames the selected-feature count as unknown in advance.
  • Novelty: Its multi-objective fitness function jointly considers feature relevance and redundancy while seeking a near-optimal solution in reasonable time.The method assigns importance to feature subsets and differs from iterative approaches that produce non-dominated solution sets.

2. Related Work

Related work presents feature selection as an optimization problem involving relevance, redundancy, computational cost, and classification performance. Existing filters and meta-heuristics provide approximate solutions, but selecting an optimal subset remains difficult.

  • Feature-selection methods: Feature selection methods support classification by reducing computational demands, but selecting an optimal feature subset is an NP-hard problem.The related-work discussion contrasts efficient ranking methods with the difficulty of subset optimization.
  • Feature-selection methods: Ranking-based filters score and sort features using relevance criteria, but they neglect redundancy among selected features.Subset-selection methods instead use heuristic or meta-heuristic searches to find near-optimal feature sets.
  • Optimization challenge: Exhaustive analysis of all feature subsets is computationally costly, time-consuming, and inefficient even for relatively small feature spaces.The dimensionality is represented by n original features, while s denotes the current subset size.
  • Optimization challenge: Meta-heuristic algorithms seek satisfactory feature subsets within acceptable time rather than guaranteeing optimal solutions.They are used to manage computational complexity in high-dimensional datasets and to escape local optima.

3. Proposed Method

The proposed method combines feature filtering, graph-based community detection, and a genetic algorithm to select relevant, non-redundant feature subsets. Its design automatically forms feature communities, evaluates relevance and redundancy jointly, and repairs offspring using community structure.

  • Feature preprocessing: The method first removes irrelevant features using Fisher scores, reducing the dataset to 100 features before clustering.This preprocessing step targets features that are ineffective for classification.
  • Feature graph: Features are represented as a completely connected undirected graph whose edge weights encode pairwise feature similarity.Similarity values range from 0 for entirely dissimilar features to 1 for completely similar features and are softmax-normalized.
  • Feature clustering: The method applies community detection to group similar features without requiring the number of clusters to be specified in advance.The clustering approach addresses limitations involving cluster count, feature distribution, and unequal feature influence.
  • Genetic algorithm: Each chromosome selects k×ω features, where k is the number of communities and ω controls the final subset size.Genes are binary: 1 indicates a selected feature and 0 an unselected feature.
  • Fitness evaluation: Fitness combines KNN classification accuracy with the summed similarities among selected features to evaluate feature relevance and redundancy together.The fitness function is applied to each selected feature subset during each iteration.
  • Evolution and repair: The algorithm performs crossover, mutation, and community-based repair before selecting the strongest chromosome as the final feature set.The repair operation directs the search toward non-redundant feature subsets using community structure.

4. Experiments and discussion

The experiments evaluate wrapper-based feature-selection methods across multiple classifiers using classification accuracy, selected-feature count, and execution time. CDGAFS generally achieves the strongest classification results, reduces dimensionality substantially, and has the lowest average feature-selection execution time.

  • Evaluation setup: The experiments compare wrapper-based feature-selection methods using classification accuracy and selected-feature count across multiple classifiers.The evaluation uses KNN, SVM, and AdaBoost, with results averaged over ten independent runs.
  • Classification accuracy: On the SpamBase dataset with KNN, CDGAFS reaches 93.99% classification accuracy, compared with 92.54% for PSO, 91.81% for ACO, and 90.35% for ABC.These values are reported as mean classification accuracies from the comparative experiments.
  • Classification accuracy: CDGAFS achieves the highest average classification accuracy across the KNN, SVM, and AdaBoost classifiers.The reported averages are 89.89% for KNN and 89.15% for AdaBoost; on SVM, it exceeds PSO by 0.77 percentage points and ACO by 1.39 percentage points.
  • Selected features: The feature-selection methods substantially reduce dimensionality by selecting a small fraction of the original features.CDGAFS selects 14.33%, 10.52%, 7.06%, and 21.92% in SpamBase, Sonar, Arrhythmia, and Isolet, respectively.
  • Execution time: CDGAFS has the lowest average feature-selection execution time across the datasets, followed by PSO-based and ACO-based methods.The reported execution-time comparison concerns feature selection only, excluding the independent final classification process.

PSO ACO ABC CDGAFS

CDGAFS uses a community-based repair operation to improve genetic-algorithm feature selection, with experiments showing effective and rapid identification of salient features. Its computational cost combines feature scoring, graph construction, community detection, iterative genetic search, and classification.

  • PSO ACO ABC CDGAFS: CDGAFS uses a community-based repair operation, whereas GAFS omits the repair operation.The comparison evaluates both approaches on Sonar and SpamBase datasets.
  • PSO ACO ABC CDGAFS: Figures 6 and 7 compare classification accuracy and convergence for CDGAFS and GAFS on Sonar and SpamBase.The figures are used to examine the repair operation’s influence on feature selection.
  • PSO ACO ABC CDGAFS: CDGAFS rapidly identifies salient features in feature space, and the figures show the successful function of its repair operation.The reported comparison attributes the observed convergence behavior to the repair-enabled method.
  • PSO ACO ABC CDGAFS: The method’s feature-scoring stage has complexity O(ncp), while graph construction requires O(n^2p) time.Here, n is the number of original features, p the number of patterns, and c the number of classes.
  • PSO ACO ABC CDGAFS: Community detection requires O(nlog n), and iterative genetic search requires O(IPkfk) time.P is the population size, k the number of clusters, fk the fitness-function cost, and I the number of iterations.
  • PSO ACO ABC CDGAFS: The KNN classifier contributes O(Pn) time complexity to the proposed method.The supplied passage reports this as the classifier’s time complexity.

5. Conclusions

The paper concludes that its feature-selection framework combines similarity and relevance assessment, community detection, and multi-objective genetic optimization. Reported comparisons indicate higher efficiency, faster convergence, and better search efficiency than other feature-selection methods.

  • 5. Conclusions: The framework first calculates feature similarities and relevance, then uses community detection to eliminate redundant features.It selects a certain number of features from each detected cluster.
  • 5. Conclusions: The proposed method embeds a filter-wrapper framework into a genetic algorithm for feature selection.This combines the stated advantages of filter and wrapper methods.
  • 5. Conclusions: The method proposes a multi-objective evolutionary algorithm for feature selection.The conclusion presents this as a central component of the proposed technique.
  • 5. Conclusions: The proposed method reports higher efficiency, faster convergence, and greater search efficiency than other feature-selection methods.These outcomes are based on the reported performance comparison.
Loading 2008.03543v1…