Information Gain Nrga Algorithm Biology Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Gene expressions by microarray data technique has been effectively utilized for classification and diagnostic of cancer nodules. Numerous data mining techniques like clustering are presently applied for identifying cancer using gene expression data. A unsupervised learning technique is a clustering technique used to find out grouping structure in a set of data. The problem of feature selection in clustering algorithm is, what type of data attributes used is not known and also for data there is no class labels so there is no clear criteria to direct the search. An additional problem in clustering is the determination of the number of clusters, which clearly impacts and is subjective by the feature selection issue. Gene expression database have a great potential as a medical diagnostic tool since they represent the state of a cell at the molecular level. Training data sets is available for the classification of cancer types generally have a fairly small sample size compared to the number of genes involved. Feature selection is considered to be a problem of optimization in machine learning, reduces the number of features, noisy and redundant data, and results in acceptable classification accuracy. Hence, selecting significant genes from the microarray data poses a dreadful challenge to researchers due to their high-dimensionality features in clustering technique and the usually small sample size. In this paper, proposes a clustering algorithm which is a hybrid model of information gain turbo-genetic algorithm for feature selection in microarray data sets. Information Gain (IG) was used to select important feature subsets (genes) from all features in the gene expression data, and a Non-Dominated Ranked Genetic Algorithm (NRGA) was employed for actual feature selection. The K-NN method is used to evaluate the NRGA algorithm. Experimental results show that the proposed clustering based method simplifies the number of gene expression levels effectively and gives accurate feature selection while compared with other methods.

Keywords---Feature Selection, Gene Expression, Genetic Algorithm, Non-Dominated Ranked Genetic Algorithm, Information Gain, K-nearest neighbor (K-NN)


The goal of clustering is to determine a natural combination in a group of patterns, points, or objects, without knowledge of any class labels. Clustering is widespread in any discipline that involves analysis of multivariate data. It is, of course, impractical to exhaustively list the numerous uses of clustering techniques. In the background of the human genome development, new technologies were emerged, it facilitate the parallel execution of experiments on a large number of genes at the same time. Hence it is called as DNA microarrays, or DNA chips, constitute a prominent example. This technology aims at the measurement of mRNA levels in particular cells or tissues for many genes at once. To this end, single strands of balancing DNA for the genes of interest which can be immobilized on spots arranged in a grid on a support which will typically be a glass slide, a quartz wafer, or a nylon membrane. Measuring the quantity of label on each spot then yields an intensity value that should be correlated to the abundance of the corresponding RNA transcript in the sample [1].

The parallelism in this kind of experiment lies in the hybridization of mRNA extracted from a single sample to many genes at once using clustering technique. The measured values are not obtained on an absolute scale. Because it depends on many factors such as the efficiencies of the various chemical reactions involved in the sample preparation, as well as on the amount of immobilized DNA available for hybridization. The class of transcripts that is probed by a spot may differ in different applications. Most commonly, each spot is meant to probe a particular gene. The representative sequence of DNA on the spot may be either a carefully selected fragment of cDNA, a more arbitrary PCR product amplified from a clone matching the gene [3]. Another level of sophistication is reached when a spot represents, e.g., a particular transcript of a gene. In this case or for the distinction of mRNA abundances of genes from closely related gene families, careful design and selection is made of the immobilized DNA are required. Similarly, the selection of samples to study and to compare to each other using DNA microarrays requires careful planning as will become clear upon consideration of the statistical questions arising from this technology [2] [4].

Microarray data samples classification involves feature selection and classifier design. Generally, only a small number of gene expression data show a strong correlation with a certain phenotype compared to the total number of genes investigated. This means that of the thousands of genes investigated, only a small number show significant correlation with a certain phenotype. Consequently, in order to analyze gene expression profiles correctly, feature (gene) selection is crucial for the classification process. The goal of feature selection is to identify the subset of differentially expressed genes that are potentially relevant for distinguishing the sample classes. A good selection method for genes relevant for sample classification is based on the number of genes investigatedâ€"is needed to increase the predictive accuracy and to avoid incomprehensibility.

Several methods have been used to perform feature selection, e.g., genetic algorithms [5], branch and bound algorithms [6] [7], sequential search algorithms [8], mutual information [9], tabu search [10], entropy-based methods, regularized least squares, random forests, instance-based methods, and least squares support vector machines. In this study, a two-stage method to implement feature selection. In the first stage, an information gain (IG) value was calculated each gene (feature). In the second stage, all the selected features must conform to a threshold. Consequently, feature selection was once again performed, this time capitalizing on the NRGA’s unique attributes to select the features. The K-nearest neighbor method (K-NN) with leave-one-out cross-validation (LOOCV) based on Euclidean distance calculations served as an evaluator of the NRGA for more classification problems taken from the literature. This procedure improved the performance of populations by having a chromosome approximate a local optimum, reducing the number of features based on clustering method, and preventing the NRGA from getting trapped in a local optimum.

Related Work

Different clustering algorithms and methods have been developed to improve the preceding ones, unravelling the problems and fit for specific fields [11]. There is no absolute clustering method that can be universally used to solve all problems. So in order to select or generate a suitable clustering strategy, it is vital to investigate the features of the problem.

As Xu and Wunsch [12] revealed the step is usually combined with the selection of a corresponding proximity measure and the construction of a criterion function. Patterns are grouped according to whether they resemble each other. Once a proximity measure is selected, the construction of a clustering condition function makes the partition of clusters an optimizing problem.

K-means is a form of partition-based clustering technique mainly utilized in clustering gene expression data [13]. K-means is well known for its simplicity and speed. It performs quite well on large datasets. However, it may not provide the identical result with each run of the algorithm. It is observed that, K-means is very good at handling outliers but its performance is not satisfactory in detecting clusters of random shapes.

A Self Organizing Map (SOM) [14] is more robust than K-means for clustering noisy data. Due to the noisy data there would be some miscalculation in the accuracy. The input required is the number of clusters and the grid layout of the neuron map. Prior identification of the number of clusters is tough for the gene expression data. Furthermore, partitioning approaches are restricted to data of lower dimensionality, with intrinsic well-separated clusters of high density. Thus partitioning approaches do not perform well on high dimensional gene expression data sets with intersecting and embedded clusters. A hierarchical structure can also be built based on SOM such as Self-Organizing Tree Algorithm (SOTA) [15]. Fuzzy Adaptive Resonance Theory (Fuzzy ART) [16] is another form of SOM which measures the coherence of a neuron (e.g., vigilance criterion). The output map is accustomed by splitting the existing neurons or adding new neurons into the map, until the coherence of each neuron in the map satisfies a user specified threshold.

information gain with nrga for feature selection

Information Gain

Information gain (IG) is a feature ranking method based on decision trees that exhibits good performance [17]. Information gain used in feature selection constitutes a filter approach. The idea behind IG is to select features that reveal the most information about the classes. Ideally, such features are highly discriminative and occur in a single class [18]. Information gain is a measure based on entropy; it indicates to what extent the whole entropy is reduced if knows the value of a specific attribute. Therefore, IG value indicates how much information this attribute contributes to the data set [17]. Each feature has its own IG value which determines whether this feature is to be selected or not. A threshold value is used for checking the features; if a feature has a greater IG value than the threshold, the feature is chosen; or else, it is not selected. Clustering is then done by learning the parameters of these models and the associated probabilities.

Let S be the set of n instances and C be the set of k classes. represents the fraction of the example in S that has class Ci. Then, the expected information from this class membership is given by:

If a particular attribute A has v distinct values, the expected information is obtained by the decision tree in which A is the root, and the weighted sum of expected information of the subsets of A is based on the distinct values. Let Si be the set of instances and Ai the value of attribute A:

Then, the difference between and provides the information gained by partitioning S according to the test A

A higher information gain will result in a higher likelihood of obtaining pure classes in a target class.

After calculating the information gain values for all features, a threshold for the results was established. Since the results show that most IG values are zero after the computation process, not many features have an influence on the category in a data set, signifying that these features are irrelevant for classification. Threshold was 0 for most of the data sets. If the information gain value of the feature was higher than the threshold, the feature was selected; if not, the feature was not selected according to the clustering technique.

Genetic Algorithms

Genetic algorithms (GAs) are stochastic search algorithms modeled on the process of natural selection underlying biological evolution. They can be applied to many search, optimization, and machine learning problems [19,20,21]. The algorithm is proceeded in iterative manner. Each string is the encoded binary, real etc., account of a candidate result. An evaluation function acquaintances a fitness measure with every string and indicates its fitness for the problem.

GAs have been successfully applied on a variety of problems, including scheduling problems [22], machine learning problems [23,24], multiple objective problems [25,26], feature selection problems, data mining problems [27], and traveling salesman problems [28]. The proposed approach uses the Non-Dominated Ranked Genetic Algorithm for the optimization purpose. The main advantages of using Non-Dominated Ranked Genetic Algorithm are that it converges very significantly than GA. Moreover, it provides rank based fitness function and it is quicker than GA.

K-Nearest Neighbor

The K-nearest neighbor (K-NN) is one of the most popular nonparametric methods [29, 30]. Attributes and training models are the main parameters with which K-NN classifies a new object. The K-NN method consists of a supervised learning algorithm where the result of a new query instance is classified based on the majority of the K-nearest neighbor category. The advantage of the K-NN method is its simplicity and easy implementation. K-NN is not negatively affected when the training data is large, and is indifferent to noisy training data [29]. In this study, the feature subset was measured by the Leave-One-Out Cross-Validation of one nearest neighbor (1-NN).

Neighbors are calculated using their Euclidean distance. The 1-NN classifier does not require any user-specified parameters, and the classification results are implementation independent.

NRGA Algorithm

In this study, the above two different feature selection models for microarray data classification were combined to select relevant genes. In the first-stage, IG, a filter method, was used to select informative genes. Initially, calculate the information gain values (IG values) for eleven gene expression data sets by Weka [31]. Information gain values were calculated for each gene in the microarray data sets by IG, and then the features were sorted in accordance with their information gain values. A feature with a higher information gain value indicates higher discrimination of this feature compared to other categories and means that the feature contains gene information useful for classification.

In the following example, gene expression data sets contain nine genes (features) which can be represented by F1, F2, F3, F4, F5, F6, F7, F8, and F9. After the application of IG, the nine information gain scores were: F1 = 0, F2 = 0.4, F3 = 0, F4 = 0.9, F5 = 0, F6 = 1.2, F7 = 0.6, F8 = 0.5, F9 = 0. Since most of the scores were 0, so use 0 as the threshold value.

The five values that were above this threshold value (F2, F4, F6, F7, and F8) were then used to continue implementing the feature selection process in the second-stage. In the second stage the NRGA algorithm is introduced to increase the classification accuracy and searching abilities.

The ith string in the population is selected with a probability proportional to. Since the population size is usually kept fixed in a simple GA, the sum of the probability of each string being selected for the mating pools must be one. Therefore, the probability for selecting the ith string is

Where n is the population size,

The NRGA algorithm is shown below. At first, a random parent population P is formed. The random values for is chosen in the way that the selected random value must be within the limit specified in above equation.

The sorting of the population is in accordance with the non-domination. Every solution is allocated a fitness (or rank) equivalent to its non-domination level. Non-domination level of 1 represents the best level, 2 represents the next-best level, etc.

Pseudo code for NRGA Algorithm:

Initialize Population


Generate random populations of â€" size n

Evaluate population objective values J based on 1-NN for

Assign rank (level) for random Populations of based on pareto dominance sort



Ranked based roulette wheel selection

Recombination and mutation


for i=1 to g do

for each member of the combined population (P∪Q) do

Assign rank (level) based on Pareto-sort

Generate sets of non-dominated fronts

Calculate the crowding distance between members of each front

end for

(elitist) Select the members of the combined population based on least dominated n solution make the population of the next generation. Ties are resolved by taking the less crowding distance

Create next generation


Ranked based Roulette wheel selection

Recombination Mutation


end for

The features selected during the first-stage were used for feature selection by the NRGA algorithm. The chromosome length represents the number of the features. The bit value {1} represents a selected feature, whereas the bit value {0} represents a non-selected feature. The predictive accuracy of a 1-NN determined by the LOOCV method was used to measure the fitness of an individual. For example, when a 9-dimensional data set (n = 9) is analyzed, any number of features smaller than n can be selected. When the adaptive value is calculated, these five features in each data set represent the data dimension and are evaluated by the 1-NN method. The fitness value for 1-NN evolves according to the LOOCV method for all data sets.

In the LOOCV method, a single observation from the original sample is selected as the validation data, and the remaining observations as the training data. This is repeated so that each observation in the sample is used once as the validation data. Essentially, this is the same as K-fold cross-validation where K is equal to the number of observations in the original sample.

NRGA algorithm was implemented. Initially, a Population of is created. Random Populations of is then generated which is of size N. Then the objective function values of J is evaluated. Rank is assigned to the Population with the best objective values based on the Pareto Dominance sort. Then the selection process is carried out based on the ranked based roulette wheel selection. Then in the reproduction phase, recombination and mutation is carried out. Reproduction phase produces new set of population , & which are the points in the s-plane. A combined Population (RPUQ) is generated. Rank is assigned to the Population with the best objective values based on the Pareto Dominance sort. The members are selected from the combined population based on least dominated N solution (elitist).

The new population of size N is used for selection. Now, two tiers ranked based roulette wheel selection is applied, one tier to select the front and the other to select solution from the front, here the solutions belonging to the best non-dominated set have the largest probabilities to be selected. Then, in the reproduction phase, crossover and mutation are applied to create a new population RP of size N.


Feature selection improves calculation efficiency and classification accuracy in classification problems with multiple features, since not all features necessarily influence classification accuracy. Selecting appropriate features attributes according to the clustering technique which improves the accuracy; on the other hand, selecting inappropriate features attributes compromises the accuracy. Hence, employing appropriate feature selection to select optimal features for a category results in higher accuracy.

The data sets in this study consisted of many gene expression profiles, which were downloaded from They include tumor, brain tumor, leukemia, lung cancer, and prostate tumor samples. The microarray data was obtained by the oligonucleotide technique, except in the case of SRBCT, which was obtained by continuous image analysis.

Table 1: Format of Gene Expression Classification Data

Data Set Name




Genes Selected

Percentage of Gene Selected

Diagnostic Task




Brain Tumor








5 human brain tumor types

Lung cancer








4 lung cancer types and normal


Prostate Tumour








Prostate tumor and normal tissues

Table 2. Accuracy of classification for gene expression data

Data Sets







Brain Tumor






Lung cancer






Prostate Tumour






The KNN method is served as an evaluator of the NRGA algorithm. The experimental results show that the proposed NRGA gives more accuracy when compared with the other existing methods like SVM and genetic algorithm.


The goal of this study was to identify the genes that provide relevant information and thus benefit the classification process. After the feature selection process, irrelevant genes are excluded, thus decreasing computing time and increasing the classification accuracy. The search abilities of NRGA depend on the population diversity of the chromosomes. A larger population diversity suits the broader search ability of the NRGA method. This extended search in the solution space is equivalent to different subset combinations of genes that can result in superior classification

In this method a NRGA algorithm is used to perform feature selection based on clustering technique. The K-NN method with LOOCV served as an evaluator of the NRGA fitness functions. Experimental results showed that NRGA simplified feature selection by clustering effectively reducing the total number of features needed, and obtained a higher accuracy compared to other feature selection methods in most cases. The accuracy obtained by the proposed method had the highest accuracy, and was comparable with other techniques. IG can serve as a pre-processing tool to help optimize the feature selection process, since it either increases the accuracy, reduces the number of necessary features for classification, or both. The proposed NRGA method could conceivably be applied to problems in other areas in the future.