Elsevier

Signal Processing

Volume 93, Issue 6, June 2013, Pages 1566-1576
Signal Processing

Efficient ant colony optimization for image feature selection

https://doi.org/10.1016/j.sigpro.2012.10.022Get rights and content

Abstract

Feature selection (FS) is an important task which can significantly affect the performance of image classification and recognition. In this paper, we present a feature selection algorithm based on ant colony optimization (ACO). For n features, existing ACO-based feature selection methods need to traverse a complete graph with O(n2) edges. However, we propose a novel algorithm in which the artificial ants traverse on a directed graph with only O(2n) arcs. The algorithm incorporates the classification performance and feature set size into the heuristic guidance, and selects a feature set with small size and high classification accuracy. We perform extensive experiments on two large image databases and 15 non-image datasets to show that our proposed algorithm can obtain higher processing speed as well as better classification accuracy using a smaller feature set than other existing methods.

Highlights

► A feature selection algorithm based on ant colony optimization is presented. ► The algorithm can obtain higher processing speed than other existing methods. ► The algorithm can select a smaller feature set than other existing methods. ► Higher quality classification results are obtained using such smaller feature set. ► The advantages of the algorithm are proved empirically.

Introduction

Reduction of pattern dimensionality via feature extraction is one of the most important tasks for pattern recognition and classification. Feature selection has considerable importance in areas such as bioinformatics [1], [2], [3], signal processing [4], [5], [6], [7], [8], image processing [9], [10], [11], text categorization [12], data mining [13], pattern recognition [14], [15], [16], [17], [18], medical diagnosis [19] and remote sensor image recognition [20]. The goal of feature selection is to choose a subset of available features by eliminating unnecessary features. To extract as much information as possible from a given image set while using the smallest number of features, we should eliminate the features with little or no predictive information, and ignore the redundant features that are strongly correlated [21], [22]. As a result, a large amount of computation time can be saved. The selected subset of features used to represent such classification function influences several aspects of image classification, including the time required to learn a classification function, the accuracy of the learned classification algorithm, the time-space cost associated with the features, and the number of samples required for training.

Ant colony optimization (ACO) is an evolution simulation algorithm proposed by Dorigo et al. [43], [44], [45]. Inspired by the behaviors of the real ant colony, they recognized the similarities between the ants' food-hunting activities and traveling salesman problem (TSP), and successfully solved the TSPs using the same principle that the ants have used to find the shortest route to food source via communication and cooperation. ACO has been successfully used for system fault detecting, job-shop scheduling, frequency assignment, network load balancing, graph coloring, robotics and other combinational optimization problems [45].

ACO is a multi-agent system where communications among artificial ants result in a positive feedback behavior to guide the ant colony to converge to the optimal solution. Pheromone information, which simulates the chemical substance the real ants lay on the route they passed, is assigned to the edges of the graph. Artificial ants are used in ACO to travel in the graph to search for optimal paths according to the pheromone and problem-specific local heuristics information. The pheromone on each edge is evaporated at a certain rate at each iteration. It is also updated according to the quality of the paths containing this edge. Artificial ants are usually associated with a list that records their previous actions, and they may apply some additional operations such as local search, crossover and mutation, to improve the quality of the results obtained. Compared with GA, ACO has some advantages such as allowing positive feedback, distributed computing, and constructive greedy heuristic search.

In recent years, some ACO based methods for feature selecting are reported. Basiri et al. [1] used ACO to select features for predicting post-synaptic activity in proteins. Nemati et al. [6] proposed an ACO based algorithm to reduce features size in automatic speaker verification. Aghdam et al. [12] proposed an ACO based feature selecting algorithm for text categorization. Kanan et al. [15] also presented an improved ACO algorithm for feature selection in face recognition. Their algorithm can select the optimal feature subset in terms of shortest feature length and the best performance of classifier. Vieira et al. [37] proposed an algorithm for feature selection based on two cooperative ant colonies, which minimizes two objectives: the number of features and the classification error. Two pheromone matrices and two different heuristics are used for these objectives. Subbotin [39] presented a modified ACO algorithm for feature selection. Akarsu et al. [46] proposed a hybrid modeling approach based on ACO for clustering and feature selection.

In some methods for feature selection, ACO is also combined with other methods to improve the quality of feature selection and classification. Huang [38] presented a hybrid ACO-based classifier model that combines ACO and support vector machines (SVM) to improve classification accuracy with a small and appropriate feature subset. To simultaneously optimize the feature subset and the SVM kernel parameters, the feature importance and the pheromones are used to determine the transition probability; the classification accuracy and the weight vector of the feature provided by the SVM classifier are both considered to update the pheromone. Based on ACO and rough sets, Chen et al. [47] proposed an approach to feature selection which adopts mutual information based feature significance as heuristic information. In their algorithm the artificial ants start their tour from the feature core, which changes the complete graph to a smaller one. Sivagaminathan et al. [48] presented a hybrid method based on ACO and artificial neural networks to address feature selection.

In most ACO-based feature selection methods, the nodes in the graph are used to represent the features. Ants traverse on the graph to look for a path containing part of the nodes which indicate the features selected. For n features, most ACO-based feature selection methods use a complete graph with O(n2) edges. This means that O(n2) pheromone and heuristic information will be computed and stored.

In this paper, we present an ACO-based feature selection algorithm, ACOFS, to reduce the memory requirement and computation time. In this algorithm, the artificial ants traverse on a directed graph with only 2n arcs. The algorithm uses classifier performance and feature set size to guide search, and optimizes the feature set in terms of its size and classifier performance. Experimental results on large image and non-image datasets show that the proposed algorithm has superior performance. Compared with other existing algorithms, our algorithm can obtain higher processing speed and classification accuracy with a smaller feature set.

The rest of the paper is organized as follows. Section 2 reviews related work on feature selection. Section 3 presents the proposed ACO based algorithm, ACOFS, for feature selection. Section 4 describes the implementation details of ACOFS. Section 5 shows and analyzes the experimental results obtained by ACOFS and compares the performance with other similar methods. Section 6 draws conclusions.

Section snippets

Related work on feature selection

Methods for feature selection can generally be classified into two main categories: model-free methods and model-based methods [22]. Model-free methods do assume a particular model and only use statistical tests on the data to select features. In the model-based methods, models with different sets of features are compared, and the model that minimizes the output error is selected. In this case, the feature selection is actually a problem of global combinatorial optimization in machine learning,

The ACO algorithm for image feature selection

We designed an ACO algorithm to optimize the feature subset. In the algorithm, an ant's solution represents a subset of features. Based on the pheromone and heuristic information, the transition probability is calculated for an ant to select a solution path. In designing the ACO-based system, we use a graph where the ants travel to construct a solution path.

Given a feature set of size n, the feature selection problem is to find a minimal feature subset of size s (s<n) while maintaining a fairly

Implementation of the algorithm

In an ACO based optimization method, the design of the pheromone update strategy, and the measurement of the quality of the solutions are critical.

Experimental results

To evaluate the proposed feature selection algorithm ACOFS, we test it by a series of experiments on standard image databases. The ACOFS algorithm is applied to select the relevant features and is compared with GA-based approach GAs [34], the modified ACO algorithm for feature selection presented in [39], which is denoted as mACO, the feature selection approach based on AdaBoost [49], Forward Greedy Algorithm (Forward GA) and Backward Greedy algorithm (Backward GA) [26]. All the experiments are

Conclusions

Image feature selection is an important task which can significantly affect the performance of image classification and recognition. In this paper, we have presented a feature selection algorithm, ACOFS, based on ant colony optimization. For n features, most existing ACO-based feature selection methods use a complete graph with O(n2) edges. The proposed ACOFS algorithm, in contrast, uses artificial ants to traverse on a directed graph with only O(2n) arcs. The ACOFS algorithm guides its search

Acknowledgments

This research was supported in part by the Chinese National Natural Science Foundation under grant Nos. 61070047, 61070133 and 61003180, State Key Fundamentals Research (973) Project under contract 2012CB316003, Natural Science Foundation of Jiangsu Province under contracts BK2010318, BK21010134, and Natural Science Foundation of Education Department of Jiangsu Province under contract 09KJB20013.

References (55)

  • S.M. Awaidah et al.

    A multiple feature/resolution scheme to Arabic (Indian) numerals recognition using hidden Markov models

    Signal Processing

    (2009)
  • K. Polat et al.

    Medical decision support system based on artificial immune recognition immune system (AIRS), fuzzy weighted pre-processing and feature selection

    Expert Systems with Applications

    (2007)
  • L.F. Mendonça et al.

    Decision tree search methods in fuzzy modeling and classification

    International Journal of Approximate Reasoning

    (2007)
  • Y.M. Li et al.

    Research of multi-population agent genetic algorithm for feature selection

    Expert Systems with Applications

    (2009)
  • P. Pulkkinen et al.

    Fuzzy classifier identification using decision tree and multi objective evolutionary algorithms

    International Journal of Approximate Reasoning

    (2008)
  • S.M. Vieira et al.

    Two cooperative ant colonies for feature selection using fuzzy models

    Expert Systems with Applications

    (2010)
  • C.L. Huang

    ACO-based hybrid classification system with feature subset selection and model parameters optimization

    Neurocomputing

    (2009)
  • X. Wang et al.

    Feature selection based on rough sets and particle swarm optimization

    Pattern Recognition Letters

    (2007)
  • C. Blum

    Ant colony optimization: introduction and recent trends

    Physics of Life Reviews

    (2005)
  • E. Akarsu et al.

    Simultaneous feature selection and ant colony clustering

    Procedia Computer Science

    (2011)
  • Y.M. Chen et al.

    A rough set approach to feature selection based on ant colony optimization

    Pattern Recognition Letters

    (2010)
  • R.K. Sivagaminathan et al.

    A hybrid approach for feature subset selection using neural networks and ant colony optimization

    Expert Systems with Applications

    (2007)
  • M.E. Basiri, N. Ghasem-Aghaee, M.H. Aghdam, Using ant colony optimization-based selected features for predicting...
  • Y. Saeys et al.

    A review of feature selection techniques in bioinformatics

    Bioinformatics

    (2007)
  • T.W. Liao

    Feature extraction and selection from acoustic emission signals with an application in grinding wheel condition monitoring

    Engineering Applications of Artificial Intelligence

    (2010)
  • S. Nemati, R. Boostani, M.D. Jazi, A novel text-independent speaker verification system using ant colony optimization...
  • M.H. Aghdam, N. Ghasem-Aghaee, M.E. Basiri, Application of ant colony optimization for feature selection in text...
  • Cited by (128)

    View all citing articles on Scopus
    View full text