An Efficient Feature Selection Algorithm for Computer-aided Polyp Detection

Jianhua Yao, Jiang Li, Jianhua Yao 0001, Ronald M. Summers, Nicholas Petrick, Michael T. Manry, Amy K. HaraInt. J. Artif. Intell. Tools 2006 · DOI

TL;DR

This paper introduces a novel, efficient feature selection algorithm called Piecewise Linear Orthonormal Floating Search (PLOFS) for computer-aided polyp detection in CT colonography. By combining a piecewise linear orthonormal model with a floating search strategy, PLOFS significantly reduces computational complexity while achieving comparable performance to other methods, making it a practical advancement for medical imaging analysis.

What Problem Does This Paper Address?

Colorectal cancer is a significant health concern, and computer-aided detection (CAD) systems for colon polyp detection using CT colonography offer a promising alternative to traditional colonoscopy. However, CAD systems often rely on a large number of quantitative features extracted from medical images. This high dimensionality presents several challenges: increased computational resources and memory requirements for training, the "curse of dimensionality" problem with limited data, and potential convergence difficulties and poor generalization in large neural networks. Feature selection aims to address these issues by identifying a compact, informative subset of features that maximizes classification accuracy. Existing feature selection methods have drawbacks, including the "nesting effect" (where features cannot be re-selected or discarded once processed) and high computational costs, particularly for wrapper methods that involve training a classifier for each feature subset evaluation.

Methods

The proposed algorithm, PLOFS, is a wrapper-type feature selection method that aims for computational efficiency while avoiding the "nesting effect." It integrates a Piecewise Linear Orthonormal (PLO) model with a floating search engine.

Here's a breakdown of the key components:

  • Piecewise Linear Orthonormal (PLO) Model: Instead of a single linear model, PLO models partition the feature space into regions (clusters) and fit simple hyperplanes within each region. This allows for better approximation of nonlinear relationships often found in medical imaging data. The paper uses a Self-Organizing Map (SOM) for initial clustering and then prunes clusters to find an optimal number. The orthonormal aspect refers to transforming the features within each cluster into an orthonormal basis, which simplifies calculations.
  • Floating Search Engine: This is the core innovation for efficient feature selection. Unlike traditional forward or backward search, the floating search allows features to be added and removed dynamically. It prevents the "nesting effect" by enabling features to be re-evaluated.
  • Orthonormal Least Squares (OLS) Procedure: The paper leverages an OLS procedure, specifically a Modified Schmidt procedure, to efficiently calculate the orthonormal bases and model weights. This procedure requires only one pass through the data to compute autocorrelation and cross-correlation matrices, making it computationally efficient.
  • Fitness Evaluation: The fitness of a feature or a set of features is defined by the total variance explained for all outputs (i.e., the contribution to classification accuracy).

The PLOFS algorithm proceeds by first determining the optimal number of clusters for the PLN model. Then, it uses a forward least square method to initialize feature subsets. It iteratively adds the most significant feature and then conditionally deletes the least significant feature, updating the fitness values at each step. This process continues until the desired number of features is selected.

Datasets

The study evaluated their algorithm on four datasets derived from CT colonography (CTC) data:

  • Supine_2D
  • Supine_3D
  • Prone_2D
  • Prone_3D

These datasets represent different acquisition views (supine/prone) and dimensions (2D/3D). The paper notes that these datasets contain a large number of features (102) extracted using 2-D or 3-D segmentation algorithms. No new benchmark datasets were introduced; existing CTC data was utilized.

Key Insights and Ideas

  • Bridging Filter and Wrapper Methods: PLOFS acts as a wrapper method in its evaluation of feature subsets but achieves computational efficiency closer to filter methods due to the efficient PLO model and OLS procedure.
  • Avoiding the "Nesting Effect" is Crucial: The paper strongly emphasizes the limitations of traditional forward and backward search methods due to the "nesting effect." The floating search is presented as a superior alternative for feature selection.
  • Piecewise Linear Models for Complex Data: The adoption of piecewise linear models is justified by their ability to approximate nonlinear systems, which are common in medical imaging, offering a more robust approach than purely linear models.
  • Computational Efficiency is Paramount: The primary motivation for PLOFS is to drastically reduce the time required for feature selection, especially when dealing with a high number of initial features. This is critical for practical deployment of CAD systems.

Key Results

  • Time Efficiency: The PLOFS algorithm, when combined with Exhaustive Search (ES) for the final selection of 3 features from the reduced set, demonstrated superior time efficiency. It required approximately 1-2 minutes to complete the feature selection process, significantly outperforming other methods like ES (90-134 minutes), Forward Stepwise Search (FSS) (23-54 minutes), Genetic Algorithm (GA) (6-7 minutes), and Progressive Search (PS) (28-75 minutes).
  • Performance Comparability: Despite its efficiency, PLOFS achieved statistically similar fitness values (average of sensitivity and specificity) to the other evaluated algorithms across the four CTC datasets. This indicates that the efficiency gains did not come at the cost of classification performance.
  • Reduced Feature Set: The PLOFS algorithm effectively reduced the dimensionality of the data, selecting a compact subset of features (e.g., 25 features were initially selected by PLOFS before a final 3-feature selection by ES).

Limitations and Future Work

  • Number of Clusters: Determining the optimal number of clusters for the PLN model is identified as a model validation problem, which is inherently difficult. The paper mentions using a pruning procedure based on training and testing error to find this number.
  • Comparison to PCA: The authors acknowledge that Principal Component Analysis (PCA) is a popular method for dimensionality reduction and express interest in comparing PLOFS to PCA-based filter methods in future work.
  • Hybrid Algorithms: The paper suggests that combining GA with PLOFS could potentially yield even more efficient hybrid algorithms.
  • Generalizability: While tested on CTC data, the generalizability of PLOFS to other medical imaging modalities or different types of classification problems is not extensively explored.

Summary updated

BibTeX
@article{yao2006efficient,
  author = {Jianhua Yao and Jiang Li and Jianhua Yao and Ronald M. Summers and Nicholas Petrick and Michael T. Manry and Amy K. Hara},
  title = {{An Efficient Feature Selection Algorithm for Computer-aided Polyp Detection}},
  journal = {Int. J. Artif. Intell. Tools},
  year = {2006},
  doi = {10.1142/s021821300600303x},
}
Figure