Classification Algorithms on Gene Expression Data
Term Project Report for CH39lL (Bioinformatics)
HYUK CHO
Table of Contents
- Introduction
- Classification Algorithms
- Challenges
- Data Description
- Parameter Settings
- Experimental Results
- Analysis of Results
- Conclusions
- References
- Source Codes
Introduction
- In this project, we compare the performance of supervised machine learning algorithms for the classification based on gene expression data. The following algorithms can be included: k-nearest neighbor(KNN) algorithm and Concept Vector-based(CB) algorithms.
- If we are interested in finding genes, which exhibit a particular expression pattern, we can find close neighbors of that pattern using a metric such as the Pearson Correlation as we learned in the class. To discover which genes have similar expression patterns in a dataset, or which experiments have similar expression profiles, we can cluster the data using some techniques such as k-means clustering algorithm and self-organizing maps. However in this project, we focus on evaluating the feasibility and performance of traditional classification algorithms and, if possible, want to propose new approaches for classification that improve the overall performance in the point of precision and recall performance.
- For the problem of classifying genes based on their expression profiles, the independent variables are the gene expression levels obtained during the different experiments, and the dependent variables are the function of the gene. A data set consists of a set of gene expression measurements from m genes in each n samples (generally one from each experiment). So each gene in the data set can be represented by a gene expression vector, showing the gene's expression in each of n samples.
- Concept vector-based(CB) classification and clustering are of latest and best performing techniques in data mining and machine learning area. Moreover, as long as I know, there have been no researches that use CB classification on gene expression data. So, if we can transform and normalize the gene expression matrix into a similarity matrix whose values are limited in some specific range, for example, from 0 to 1 (i.e., normalized) as that of vector space model(VSM) in data mining society, we can directly apply CB classification algorithm to classify functionality of genes in gene expression data.
- k-nearest neighbor(KNN) classification algorithm
- Naive Bayesian(NB) classification algorithm
- Concept Vector-based(CB) classification algorithm
Brief overview of this project
|
|
Need more information about some classification algorithms?
|
|
Classification Algorithms
- The goal of classification is to build a set of models that can correctly predict the class of the different objects. The input to these methods is a set of objects (i.e., training data), the classes which these objects belong to (i.e., dependent variables), and a set of variables describing different characteristics of the objects (i.e., independent variables). Once such a predictive model is built, it can be used to predict the class of the objects for which class information is not known a priori. The key advantage of supervised learning methods over unsupervised methods (for example, clustering) is that by having an explicit knowledge of the classes the different objects belong to, these algorithms can perform an effective feature selection if that leads to better prediction accuracy.
- The followings are brief overview on some classification algorithms that has been used in data mining and machine learning area and used for this project.
- KNN classifier is an instance-based learning algorithm that is based on a distance function for pairs of observations, such as the Euclidean distance. In this classification paradigm, k nearest neighbors of a training data is computed first. Then the similarities of one sample from testing data to the k nearest neighbors are aggregated according to the class of the neighbors, and the testing sample is assigned to the most similar class. One of advantages of KNN is that it is well suited for multi-modal classes as its classification decision is based on a small neighborhood of similar objects. So, even if the target class is multi-modal (i.e., consists of objects whose independent variables have different characteristics for different subsets), it can still lead to good accuracy. A major drawback of the similarity measure used in KNN is that it uses all features equally in computing similarities. This can lead to poor similarity measures and classification errors, when only a small subset of the features is useful for classification.
- NB algorithm has been widely used for document classification, and has been shown to produce very good performance. NB algorithm computes the posterior probability that the document belongs to different classes and assigns it to the class with the highest posterior probability. The posterior probability of class is computed using Bayes rule and the testing sample is assigned to the class with the highest posterior probability. Despite the fact that the independence assumption of naive Bayesian does not hold in real data sets, it performs surprisingly well, in practice. If we know the exact class distribution functions, the metric selection and class prediction would be straightforward from a Bayesian perspective.
- In CB classification algorithm, the length of each vector is normalized so that it is of unit length. The idea behind the concept-based classification is extremely simple. For each set of experiments belonging to the same class, we compute their concept vector by summing up all vectors in the class and normalize it by its 2-norm. If there are k classes in the training data set, this leads to k concept vectors, where each concept vectors for each class. The class of a new sample is determined as follow. First we use the frequencies of the various genes computed from the training set to compute the weighted representation of the given experiment and scale it so that it has unit length. Then, we compute the similarity between this vector to all k concept vectors using the cosine measure. Finally, based on these similarities, we assign it to the class corresponding to the most similar concept. One of the advantages of the CB classification algorithm is that it summarizes the characteristics of each class, in the form of concept vector. SO, the advantage of th summarization performed by the concept vectors is that it combines multiple prevalent features together, even if these features are not simultaneously present in a single experiment. That is, if we look at the prominent dimensions of the concept vector (i.e., highest weight terms), these will correspond to genes that appear frequently in the class, but no necessarily all in the same set of experiment. This is particularly important for high dimensional data sets for which the coverage of any individual feature is often quite low.
Brief overview of some classification algorithms
|
|
|
|
|
|
|
|
Challenges
- What do we need/do in the preprocessing step?
- How to make the matrix to represent similarity between genes and experiments?
- What is the good distance measure?
- Do we need to do feature selection for better performance in the accuracy and computational efficiency?
- How many training/testing data are needed for reasonable performance?
- For semi-supervised learning (i.e., we know only partial true label information), how much can we guarantee the accuracy of classified result?
- Can we improve accuracy by combining two or three classification algorithms?
|
|
Data Description
- We use the yeast gene expression profile that is publicly available from Brown's group at Stanford University.
- This experiments are consisting of 79 experiments on 2467 yeast genes.
- However some of 2467 genes don't have all 79 experimental values because each experiment was performed on different subset of genes. So we add value 0.0 to these missing experimental values.
- Among these 2467 genes, we removed 136 genes because these had no functional information or some of them have small number of genes in that class. The main reason we did is that, with these biased data, we have low chance to get good classification performance and it makes difficulty in comparing classification performance of each algorithm. So we used 2331 genes that have 79 experimental values.
- We refer to the functional gene catalog the functional annotations on yeast genes in the Munich Information Centre for Protein Sequence (MIPS) database.
- This experiments are consisting of 79 experiments on 2467 yeast genes.
- The MIPS database defines a total of 249 gene function classes in a hierarchical structure. So, some genes can be assigned to multiple categories.
-
Among 249 gene function classes, we select the following nine classes that are nine largest functions.
The first integer means the number of yeast genes that we use and are assigned to the corresponding
function and the second integer is total number of genes classified into this function.
- METABOLISM (253/1066)
- CELL CYCLE AND DNA PROCESSING (162/837)
- TRANSCRIPTION (98/794)
- PROTEIN SYNTHESIS (158/359)
- CELLULAR TRANSPORT AND TRANSPORT MECHANISMS (230/497)
- CELL RESCUE, DEFENSE AND VIRULENCE (92/368)
- CONTROL OF CELLULAR ORGANIZATION - cytoplasm (414/547)
- CONTROL OF CELLULAR ORGANIZATION - nucleus (632/755)
- CONTROL OF CELLULAR ORGANIZATION - mitochondrion (292/360)
- Yeast gene expression profile (2467 genes, 79 experiments) which has missing values and headers.
- Cleaned Yeast gene expression profile (2467 genes, 79 experiments) which has all missing values (i.e., N/A) substituted by 0.0 and no headers.
- Cleaned and Modified Yeast gene expression profile (2331 genes, 79 experiments) which has only genes having functional category in MIPS and belongs to top 9 categories. Remember that the values are not normalized yet.
- Converted Yeast gene expression profile to CCS format Remember that the values are not normalized yet.
- True label (i.e., category information) for each gene used
To classify genes according to their functions, we need to have both the actual gene expression profile and the different functional classes of genes.
1. Gene Expression Profile
|
|
2. Function Gene Class
|
|
3. Data
|
|
Parameter Settings
- We select 80 % of training data for each category and the remaining genes (i.e. 20 % of each category) are used as testing data. So if it is not specified explicitly, we follow this selection. Remember that we randomly select training data according to the given percentage of training data, so every time we run programs with different training and testing data set.
- We normalize each gene vector using 2-norm. So each gene expression vector has unit length.
- We measure distance using inner product between a testing gene and a training gene for KNN and between a concept vector of training genes and a training gene for CB classification.
- To get learning curves, we set the range of training size from 0.1 to 0.9.
- We set the number of nearest neighbors(i.e., k) to be 1, 2, 5, 10, 15, 20, and 25. It turns out by experiments that k (> 25) doesn't affect much to the classification performance, so we just select k=10 for the whole experiments which shows the performance good enough to compare.
- We compute one concept vector for each category by using true category information on training data. So we don't need to specify any parameters for CB classification algorithm.
Common parameter setting for every algorithm:
|
|
1. k-Nearest Neighbor(KNN) Algorithm
|
|
2. Concept Vector-based(CB) Algorithm
|
|
Experimental Results
- Accuracy = (TP + TN) / (TP + FP + FN + TN)
- Precision = TP / (TP + FP)
- Recall = TP / (TP + FN)
- Learning curves(LCs) shows the change of performance (accuracy, precision, or recall) according to the change of training data size.
- TABLE 1 shows the classification accuracy for both KNN and CB classification algorithms. Here, k means the number of nearest neighbors for KNN and t means the total # of runs of the algorithms. The last row shows the averaged values after t=5 (i.e., 5 runs).
-
LCs for KNN classification algorithm for accuracy/precision/recall (FIGURE 1/2/3) on each training, testing and both data
(Click any one to view larger figure.) -
LCs for CB classification algorithm for accuracy/precision/recall (FIGURE 4/5/6) on training, testing, and both data
(Click any one to view larger figure.) -
Comparison of LCs for accuracy/precision/recall (FIGURE 7/8/9) on training data
(Click any one to view larger figure.) -
Comparison of LCs for accuracy/precision/recall (FIGURE 10/11/12) on testing data
(Click any one to view larger figure.) -
Comparison of LCs for accuracy/precision/recall (FIGURE 13/14/15) on both (i.e., training + testing) data
(Click any one to view larger figure.)
How to evaluate classification performance?
|
|
1. Accuracy for training/testing/both data (TABLE 1)
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2. Macro-precision for training/testing/both data (TABLE 2)
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3. Macro-recall for training/testing/both data (TABLE 3)
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4. Learning Curves(LCs) for training/testing/both data
|
|
|
|
|
|
|
|
|
|
Analysis of Results
- Tables summarize the classification performance (accuracy(TABLE 1), precision(TABLE 2), and recall(TABLE 3)) of the two classification algorithms. Remember that in fact, there is no difference between training and testing data in KNN classification algorithm. However for the comparison purpose, I divided data set into three categories, training, testing, and both (= training + testing) data.
- From the TABLE 1, we can say that KNN classification algorithm outperforms CB classification algorithm in classification accuracy. Also, the accuracy is improved as the number of nearest neighbors (i.e., k) increases. However, at some k, accuracy is not improved. Actually, finding optimal k is one of issues in KNN classification algorithm. Also, the difference of accuracy between the two algorithms is largest among the three classification performance measures (i.e., accuracy, precision, and recall).
- For the case of precision (TABLE 2), KNN classification algorithm has still better performance over all data types (i.e., training, testing, and both data). However, the difference of precision between the two algorithms becomes smaller than that of accuracy. Moreover, for some k (i.e., k=1, 2, and 5), CB classification algorithm shows slightly better precision values and shows consistent values overall experiments. So we can say that CB classification algorithm gives robust precision values.
- On the other hand, CB classification algorithm results in better recall than KNN classification algorithm does. Like its result on Preston (see TABLE 2), CB classification algorithm shows robust recall values.
- KNN classification outperforms CB classification algorithm only for accuracy. Reversely, CB classification algorithm shows similar precision and better recall performance. Therefore, from TABLE 1, 2 and 3, it is not clear which algorithm is better for gene classification because there is no particular difference between the two algorithms.
- In order to closely look at the classification performance, we check how the three performance measures are changed according to the change of number (i.e., percentage) of training data set. Here from 10 to 90 percentage of whole data were selected as training data and the remaining data are used as testing data.
- FIGURE 1/2/3 show how accuracy/recall/precision are changed with KNN and size of training data. Interestingly, shapes and magnitude (i.e., value) of lines for training/testing/both data are similar. As I mentioned before, this is due to the fact that there is no difference between training and testing data. One important thing we can learn from FIGURE 1/2/3 is the fluctuation of lines. Being fluctuated or crossing other lines tells us that the performance of KNN classification algorithm can be affected by the size of training data. However the amount of fluctuation is not big. They also show increasing shapes along with the number of training data.
- FIGURE 4/5/6 show CB classification algorithm's characteristics. With 10 percentage of data as a training data, it has highest accuracy, precision, and recall value for training data and the training curves gradually decrease as the size of training data increases. However both testing and both data are not changed much (rather almost constant). Moreover there is no severe fluctuation and no crossing lines. The two lines for testing and both data are almost parallel. It means that it is not sensitive to the number of training data. Rather we can say that it is also robust to the number of training data.
- Through FIGURE 1-6, we check each algorithm's general performance and characteristics. Additionally we compare both algorithms in the same categories: FIGURE 7/8/9 compare the three performance on training data, FIGURE 10/11/12 check them on testing data, and 13/14/15 do on both data. As we see the accuracy performance through TABLE 1/2/3, we can see that KNN has better accuracy performance. Interestingly, Interestingly, the shape of learning curves(LCs) of the two algorithms on testing and training data are really similar except some minor difference. The lines on testing and training data are close and rather in parallel each other. It means that both algorithms has similar precision and recall performance and both are robust to the size of training data even though KNN is not more robust than CB is.
- In fact, it is not an unexpected result that KNN classification algorithm is robust to the size of training data. In our experiments (not shown in this webpage) using KNN and CB classification algorithm for vector space model (VSM) of text document data, CB classification algorithms clearly outperformed KNN classification algorithm in the three classification measures as well as learning curves. So we guess that this result is owing to the hidden (i.e., implicit) characteristics of gene expression data and different normalization. For example, in VSM, we just use the frequency of each word in each document and based on this frequency, we give weight for each word both locally and globally and normalize each document vector using 2-norm. So possible values in matrix ranges from 0 to 1. However in gene expression data, we treat missing values as 0.0 and normalize them using 2-norm, so they can have positive/ negative values.
- In summary, the classification performance is so similar that it is not easy to say which is better. However, this result gives us more interesting consideration as follows: In computational time and scalability point of view, CB classification clearly outperforms KNN classification algorithm because it just computes the angles (i.e., cosines) of the two gene vectors between small number of concept vectors and a testing gene. Remember that in KNN classification algorithm, we compute all cosines between training genes and a testing gene every iteration and need additional computation to get k nearest neighbors. So, we can expect similar (or sometimes better) classification performance within even shorter time. Additionally, concept vector is a normalized centroid vector, so it is a representative vector for the class (or category). Therefore it is not sensitive to erroneous or missing values because it is resulted from being summed and being normalized. In other words, small erroneous or missing values doesn't make big changes of values in a centroid vector. This also can answer to the results shown in above TABLEs. As mentioned before, even though we use different samples of training data at each run, CB classification algorithm results in constant performance because concept vector is not changed much at each run. Further more, in KNN classification algorithm, the performance is directly related with the distance between neighbors and a testing gene. So with bad selection of training, we can get bad classification result.
|
|
Conclusions
- In this project, we focused on two classification algorithms, KNN classification algorithm and CB classification algorithm, for classifying yeast genes according to functionality. First we selected nine largest yeast gene functional categories out of 249 categories in the MIPS database. We used a partial gene expression data (2331 genes, 79 experiments) of the original yeast gene expression profile (2467 genes, 79 experiments) by removing 136 genes based on the nine categories and inserting 0.0 for missing data. After then, we compared the two algorithms by using three classification performance measures, accuracy, precision, and recall, for each training, testing, and both data. Additionally we showed several LCs to investigate each algorithm's classification behavior on different size of training data.
-
From TABLEs and FIGUREs, we conclude that the overall classification performance is not good as mentioned
in [7], which shows similar classification performance on the same data we have used. However we found
that both KNN classification algorithm and CB classification algorithm have common classification
behaviors:
- First, they give similar classification performance. Specifically, KNN classification algorithm gives better accuracy, CB classification algorithm has slightly better recall, and both show similar precision.
- Secondly, except LCs for training data, LCs for both algorithms show close quantities and similar patterns for testing and both data. However LCs for CB classification algorithm are robust to the size of training data.
- For high-dimensional data, computational feasibility can be an important issue. So CB classification algorithm is more desirable than KNN classification algorithm, since the former results in similar or better classification performance in linear-time computation as mentioned in [10].
-
Our experimental results suggest the usefulness and feasibility of CB classification algorithm on
a gene expression profile. However the general classification performance is not explicitly better than
KNN classification algorithm. So it is worth mentioning the future research directions with which we
can refine CB classification of gene functionality on gene expression data.
- We just used nine largest categories and used them as flat categories even though the MIPS database provides us hierarchical categories. So, one research direction is to use this hierarchical category information when we do classify gene functions.
- Additionally, we don't know how many categories are appropriate for classification. For example, [10] used 50 highest categories on the same data set.
- We used all 79 experiments and inserted 0.0 for missing data. So one other possible future work is to use feature selection in order to get computational and interpretational advantages.
- As shown in [10], class size can affect classification performance. So we can investigate relationship between classification performance and the distribution of class sizes to get reasonable number and size of category classes without worsening performance.
- We saw KNN classification algorithm is better on accuracy and CB classification algorithm is better on recall. So we can think of combination of the two classification algorithms or other algorithms so that we can take advantages of other algorithms' better behavior.
1. Summary
|
|
2. Conclusions
|
|
3. Future Works
|
|
References
- Inderjit S. Dhillon and Dharmendra S. Modha, "Concept Decompositions for Large Sparse Text Data using Clustering,", Machine Learning, vol. 42:1, pp. 143-175, January, 2001.
- R. Sandberg, G. Winberg, C. Branden, A. Kaske, I. Ernberg, and J. Coster, "Capturing Whole-Genome Characteristics in Short Sequences Using a Naive Bayesian Classifier," Genome Research, vol. 11, pp. 1404-1409, 2001.
- E. M. Marcotte, I. Xenarios, A. M. van der Bliek, and D. Eisenberg, "Localizing proteins in the cell from their phylogenetic profiles," PNAS, vol. 97, pp. 12115-12120, 2000.
- D. K. Slonim, P. Tamayo, J. P. Mesirov, T. R. Golub, and E. S. Lander, "Class Prediction and Discovery Using Gene Expression Data," Proceedings of the fourth annual international conference on Computational molecular biology, pp. 263-272, 2000.
- S. Dudoit, J. Fridlyand, and T. P. Speed, "Comparison of Discrimination Methods for the Classification of Tumors Using Gene Expression Data,", Technical report #576, Department of Statistics, University of Califonia at Berkeley, June 2000.
- M. B. Eisen, P. T. Spellman, P. O. Brown, and D. Botstein, "Cluster analysis and display of genome-wide expression patterns," Genetics, vol. 95, pp. 14863-14868, December 1998.
- M. Kuramochi and G. Karypis, "Gene Classification using Expression Profiles: A Feasibility Study," To appear in The 2nd IEEE International Symposium on Bioinformatics & Bioengineering (BIBE 2001), 2001.
- E. P. Xing, M. I. Jordat, and R. M. Karp, "Feature Selection for High-Dimensional Genomic Microarray Data"
- P. Pavlidis, C. Tang, and W. S. Noble, "Classification of genes using probabilistic models of microarray expression profiles," BIOKDD01: Workshop on Data Mining in Bioinformatics (with SIGKDD01 Conference)
- E. Han and G. Karypis, "Centroid-Based Document Classification: Analysis & Experimental Results," Technical Report: #00-017, University of Minnesota, Dept. of Computer Science, March 2000.
|
|
Source Codes
- C++ Program for getting truelabel information from the MIPS data.
- Mail to hyukcho@cs.utexas.edu to get KNN-classification algorithm and CB classification algorithm in MATLAB.