The pattern recognition problem for real-life applications of gas identification is challenging due to the limited amount of data existing and the sequential variability of the mechanism mostly caused by drift and the real-time detection. These problems are commonly caused by the slow response of most of the gas sensors. In this paper, a novel gas identification approach based on the cluster-k-nearest neighbor (C-k-NN) is introduced. The effectiveness of this approach has been successfully demonstrated on the experimental data set obtained from array of gas sensors. Our classification takes advantages of both the k-NN, which is highly accurate, and the k-means cluster, which is able to reduce the classification time. In order to increase the accuracy rate, a new feature selection method is proposed. The selection of features is based on their ability to separate and distinguish between different classes. Advanced statistical metrics are introduced to quantify the classification contribution of each feature. Mostly, classifiers are suffering from misclassification detection; new statistical metrics are introduced to estimate the exactness of the classifier response, i.e., to detect the misclassification. To enhance the classification performances for gas identification, a new tree classification design is introduced, named tree C-k-NN. In order to assess the technique, experiments were conducted on six different gases. Accuracy rate of 98.7 has been obtained with the C-k-NN and 100 with the tree C-k-NN. The performance of this approach is also validated using three publicly available data sets. © 2001-2012 IEEE.