特征选择

A Novel Unsupervised Feature Selection Method for Bioinformatics Data Setsthrough Feature ClusteringGuangrong Li1, 2, Xiaohua Hu3, 4, Xiajiong Shen4, Xin Chen3, Zhoujun Li51School of Computer, Wuhan University, Wuhan, China2College of Accounting, Hunan University, Changsha, China3College of Information Science and TechnologyDrexel University, Philadelphia, PA 191044College of Computer and Information Engineering,Henan University, Henan, China5Dept. of Computer Science, Beihang University, Beijing, ChinaAbstractMany feature selection methods have been proposed and most of them are in the supervised learning paradigm. Recently unsupervised feature selection has attracted a lot of attention especially in bioinformatics and text mining. So far, supervised feature selection and unsupervised feature selection method are studied and developed separately. A subset selected by a supervised feature selection method may not be a good one for unsupervised learning and vice verse. In bioinformatics research, however it is very common to perform clustering and classification iteratively for the same data sets, especially in gene expression analysis, thus it is very desirable to have a feature selection method which works well for both unsupervised learning and supervised learning. In this paper we propose a novel feature selection algorithm through feature clustering. Our algorithm does not need the class label information in the data set and is suitable for both supervised learning and unsupervised learning. Our algorithm groups the features into different clusters based on feature similarity, so that the features in the same clusters are similar to each other. A representative feature is selected from each cluster, thus reduces the feature redundancy. Our feature selection algorithm uses feature similarity for feature redundancy reduction but requires no feature search, works very well for high dimensional data set. We test our algorithm on some biological data sets for both clustering and classification analysis and the results indicates that our FSFC algorithm can significantly reduce the original data sets without scarifying the quality of clustering and classification . 1. IntroductionFeature selection (also known as variable selection, subspace selection, or dimensionality reduction) is a procedure to select a subset from the original feature set by eliminating redundant and less informative features so that the subset has only the best discriminative features [15]. There are three major benefits of feature selection (FS): (1) improves the prediction performance of the predictors; (2) helps predictors do faster and more cost-effective prediction; and (3) provides a better understanding of the underlying process that generated data [9]. Therefore FS has been an essential tool for many applications, especially bioinformatics, text mining, and combinatorial chemistry [9] where high dimensional data is very common.Feature selection research has been studied extensively in the supervised learning paradigm in various disciplines such as machine learning, data mining, pattern recognition, etc for very long time. Recently unsupervised feature selection (UFS) received some attentions in data mining and machine learning as clustering high dimensional data sets becomes an essential and routine task in bioinformatics and text mining. UFS is becoming an essential preprocessing step because UFS can not only reduce computational time greatly due to reduced feature subset but also improve clustering quality because no redundant features that could act as noises are involvedin unsupervised learning.Feature selection as heuristic search consists of four modules; the selection of starting point in feature search, the organization of the search (search strategy), the evaluation of feature subsets, and search halting criterion [2]. With this guideline it seems that UFS could be designed in the same way with some modifications as supervised feature selection. However, the traditional feature selection approach cannot be directly applied to UFS. This is because, dueto the absence of class label in data set, two of the fourrequired modules are recondite to fulfill in UFS; the evaluation of feature subsets, generated through feature search, and search halting criterion, because it mostly depends on feature subset evaluation, are abstruse. Also it is impossible to measure the correlations between the class and each feature by using distance, information or dependence measures, which is an essential processing in FS. In addition to that, due to the unknown number of clusters, it is very hard to evaluate feature subsets in UFS. That is why supervised feature selection and unsupervised feature selection and studied and developed separately.The subsets selected based on supervised feature selection may not a good one for clustering task and vice verse [3]. In some real applications, various data mining analysis may need to apply to the same data, which is very popular in bioinformatics study, especially in gene expression analysis. It is very common to perform clustering to group genes and then perform classification to identify important genes to distinguish different genes type in different groups. Thus, it is necessary to design a feature selection method that works for both supervised and unsupervised learning. In this paper we present a novel feature selection approach based on feature clustering. Since our method does not rely on the classification label information in the data set, it works for both supervised and unsupervised learning. In our method, we use maximal information compression index (MICI) [14] to evaluate the similarity of the feature and then use a novel distance measure to cluster the feature into different clusters. In each cluster, a representative feature is selected, thus the number of feature is reduced significantly.The rest of this paper is organized as follows. In Section 2 we first discuss filter and wrapper method in feature selection since most UFS works are based on these methods, then discuss several feature selection methods based on feature clustering in text mining and a UFS approach based on feature clustering. We explain our method (FSFC) in details in Section 3. In Section 4, extensive experiment results of various biological data sets for both clustering and classification based on our FSFC approach are presented. In Section 5 we conclude the paper.2. Related WorkTraditionally, filter and wrapper feature selection approaches have been widely used in supervised feature selection [12]. Wrapper approach uses learning (or induction) algorithm for both the FS and the evaluation of each feature set while filter approach uses intrinsic properties of data (e.g. the correlation with the class) for FS. Both wrapper and filter approaches need to search the feature space to get a feature subset. For feature search greedy algorithms, instead of exhaustive search, like forward or backward sequential selection is widely used. For exhaustive search, the whole search space is O(2D), where D is the number of features and for forward or backward sequential search, the search space is O(D2).In wrapper approach, every feature set must be evaluated by learning algorithm instead of intrinsic properties of data. However, it requires huge amount of computational time. Even if scalable and efficient learning algorithms and greedy algorithm for feature search are used in wrapper approach, it is very expensive in terms of computational cost. A huge number (at least D2) of iterative running of the algorithms make it infeasible to be applied in high-dimensional data set.On the other hand, in bioinformatics, the number of features in the data sets tends to be very large, feature clustering method has been used frequently for the initial exploration analysis. It was found that this method outperforms traditional feature selection methods [1] [16] and it also reduces more redundant features with high classification accuracy than feature selection methods [1]. Distributional clustering method and information bottleneck method are used for feature clustering [1] [16]. However, these two methods require high computational time, compared with [6] that uses information theoretic framework. The framework is similar to information bottleneck but it uses a new divisive algorithm (similar to k-means algorithm) that uses Kullback Leibler divergences as distance, which makes it faster. Recently an unsupervised feature selection method based on clustering method was introduced in [14]. However, the method requires user input parameter k, where k is used to control the neighborhood size of the feature clusters. It is very difficult to pick up the proper k value and it normally needs to try different k value many times before a desirable k value is determined. For different k value, the whole procedure to calculate the distance and clustering the data need to start over. 3. Our Algorithm (FSFC)One of the reasons why UFS is very challenging is because it is very hard to distinguish informative features from less informative features due to the absence of class label. Unlike traditional UFS methods [13] [4] [18] [5] [17] [7], we propose a clustering based feature selection algorithm which uses feature similarity for redundancy reduction but requiring no feature search.Our feature selection method consists of two major steps: first the entire feature set is partitioned into different homogeneous subsets (clusters) based on the feature similarity, and then a representative feature is selected from each cluster. Partitioning the features is done using hierarchical clustering based on MICI. A representative feature of each cluster is selected based on our cost distance function. Such representatives (features) constitute the optimal feature subset. The algorithm is summarized as below:Algorithm: Feature Selection through Feature Clustering (FSFC)Input: Data set D = {F n, n = 1, …, D} (D is the number of features), the number of feature kOutput: the reduced feature subset FS kMethodStep1: FS k = ∅Calculate MICI for each feature pairStep2: RepeatSelect S i, S j if C(S i, S j) is the minimumMerge S i & S jUntil all the objects are merged into one clusterStep3: Select the top k clusters from the hierarchical cluster treeFor each cluster S kThe center CF k(the feature with the smallest sum of MICI all other features inthe cluster) is selected as a representativefeature of the cluster.FS k = FS k∪ CF kEndForThe complexity of the FSFC algorithm is O(D2), where is the dimension. Even though the sequential forward selection and backward elimination also have complexity O(D2), but the each evaluation of the searched based approach is more item consuming than ours.var()var()x y+, where “var” means a sample variance and “cov” means a sample covariance. MICI as a similarity measure between features in our method has many benefits over correlation coefficient and least square regression error; first, MICI is symmetric regardless of the feature order on distance calculation (i.e. Distance(F1,F2) = Distance(F2,F1), where F n is the n th feature); secondly it is strong for data translation since the formula includes mean, variance, and covariance; finally it is insensitive to rotation of the variable.The distance function used in our clustering adapted from [20], it was successfully used for in cluster ensemble approach [10]. It is defined as(,)min((),())i j i j j ic S S D S S D S S=→→, where1,1()(,)m inij ji imi j i jx Si x SiD S S M IC I x xm∈=∈→=∑S i and S j are the i th and j th clusters in the clustering hierarchy. In hierarchical clustering S i or S j contains only one object (a feature in our case) in the beginning. S i and S j are merged based on the distance. As the clustering step progresses, the number of unclustered objects decreases one by one. The process stops until all the clusters are merged into one cluster. For each cluster a representative feature is selected from the features in the cluster. Our definition of the representative feature of a cluster is the center of the features which has the shortest sum of distance to all other features in the cluster. For example in the “1D” and “2D” example as shown below, The star should be the representative of both clusters because it is in the middle; the distance of the star for every other object in the cluster is the shortest.▲▼★◀▶A cluster in 1D space A cluster in 2D spaceA hierarchical clustering tree is formed after running the algorithm once in the data set. Different feature subsets can be easily formed from this tree. To generate a feature subset with size k, k representative features are selected from the top K clusters in the cluster tree. Since our feature selection approach is based on hierarchical clustering, it is very easy to generate various feature subsets without much computational overhead. We only need to do clustering once. This is a significant advantages compared with other approaches. For example, in [14] for different k, the whole clustering procedure needs to be done over again.Our clustering based FSFC method does not require any feature search, it is expected that our algorithm is considerably fast, compared with traditional UFS. The biggest differences of our approach from [14] is that in our method we only need to do feature clustering once and then can choose different numbers of features for the exploration analysis with very little computation overhead for clustering, which is considered crucial inreal applications. Another difference is that our k is exactly the number of cluster; the exact number of features reduced is expected in the result.4. Experiment ResultsWe conduct extensive experiments to demonstrate that our approach works well for both clustering and classification tasks. We want to demonstrate that our FSFC can significantly reduce the original data sets without scarifying the quality of clustering and classification. We first apply our FSFC method on the original data set to reduce the number of feature and then apply either clustering or classification algorithm. We want to demonstrate that our method can significantly reduce the number of redundant featuresin high dimensional data set and retain highly informative features, which is essential for clustering and/or classification. In our experiments we use various biological data sets (protein sequence, microarray gene expression data sets) for clustering and classification.Before applying our FSFC method to data sets for clustering analysis, we remove the class label from the original data sets and use the class label only on generating the true clusters for MS measurement purpose (MS definition is explained in the experimental subsection). For clustering analysis, K-means, SOM, and Fuzzy C-means are used and MS is used as an evaluation measurement for the clustering result. For classification analysis, SVM light is used [11]. This software is available at /. For each data set, the features are decreased by 20 percents each time so each data set generate 4 additional data sets with 20% features removed each time. For example, if a data set has 100 features, data sets with 20, 40, 60, and 80 features are generated using FSFC algorithm. Graphs based on MS or the accuracy of SVM are provided; y axis indicates MS or SVM accuracy while x axis indicates the number of features used. Please note the small is better in MS while the bigger is better in the accuracy of SVM.4.1 Clustering analysis with FSFC a pre-processing step for data reductionIn these tests, we demonstrate that FSFC can significantly reduce the original data sets without scarifying the clustering quality.To evaluate the clustering results, we adopt the Minkowski score. A clustering solution for a set of n elements can be represented by an nxn matrix C whereC ij=1 iff x i and x j are in the same cluster according to the solution and C ij=0 otherwise. A measure of Minkowski Score (MS) between the clustering results C(h) from a particular clustering algorithm CA h with a reference clustering T (or alternatively, the true clusters if the cluster information in the data set is known in advance) is defined as MS (T, C(h)) = ||T-C(h)||/||T||, where ||T|| = sqrt(∑i∑j T ij)The Minkowski score is the normalized distance between the two matrices. Hence a perfect solution will obtain a score zero, and the smaller the score, the better solution.We use 5 public gene datasets for our clustering analysis.(1) Yeast gene data set contains 7129 tuples and 80 attributes. But 2465 genes are classified. Such genes are classified into 108 function family. All Yeast data sets used here have 80 attributes. In our experiment, each family is treated as a cluster. Yeast1, Yeast2, and Yeast3 data sets are extracted from those genes. Yeast1 data set with 3 clusters contains 101 tuples and Yeast2 data set with 2 clusters contains 80 tuples. Yeast3 data set with 4 classes contains 669 tuples. The original data set is available here (/EisenData.htm).Yeast1(MS index)K-means SOMFuzzy C-mean16 features 1.086 1.066 1.10232 features 1.027 0.945 1.06448 features 1.014 0.912 1.043 64 features 1.028 0.929 1.05480 features 1.040.956 1.054Yeast2(MS index)K-means SOMFuzzy C-mean16features 0.926 0.879 0.879 32features 0.759 0.817 0.799 48features 0.780 0.713 0.737 64 features 0.737 0.688 0.713 80 features 0.759 0.737 0.713Yeast3 (MS index) K-means SOMFuzzy C-mean16 features 1.198 1.185 1.37332 features 1.136 1.167 1.54048 features 1.123 1.114 1.265 64 features 1.110 1.119 1.303 80 features 1.124 1.1181.305(2) Leukemia data set has 7129 genes but 52 genes are classified into 2 clusters. Our experiment data set has 52 genes and 38 features. The data set is available from /colondata.Leukemia (MS index) K-means SOMFuzzy C-mean8 features 0.917 0.768 0.93315 features 0.933 0.768 0.93323 features 0.933 0.768 0.89830 features 0.933 0.768 0.877 38 features0.877 0.768 0.877(3) B-cell Lymphoma dataset has 4026 genes and 96 features. 43 genes are classified into 4 clusters. The/lymphoma.B-cellLymphoma (MS index) K-means SOMFuzzy C-mean19 features 0.831 0.965 1.08738 features 0.512 0.841 1.106 58 features 0.569 0.816 0.56977 features 0.577 0.768 0.82196 features 0.779 0.882 0.569(4) RTK (Receptor Tyrosine Kinase) data set has 6312 genes and 16 attributes but 137 genes are classified into 7 classes. We used this classified gene so our experiment data set with 7 classes has 137 genes and 16 features. The data set is available from /RTK/.RTK(MS index)K-means SOMFuzzy C-mean 3features 1.354 1.350 1.354 6features 1.347 1.285 1.375 10 features 1.354 1.256 1.35413 features 1.435 1.275 1.35116 features 1.291 1.277 1.359(5) BRCA1 (related with breast cancer) data set has 373 genes and 12 attributes. 337 genes are classified into 51 classes (each class has 1~43genes). Our experimental data set with 6 clusters has 164 tuples and 12 features. For more information about this gene data set, refer to [21].BRCA1(MS index)K-means SOMFuzzy C-mean2 features 1.308 1.277 1.3635 features 1.354 1.317 1.3487 features 1.353 1.292 1.35810 features 1.351 1.304 1.36012 features 1.355 1.302 1.3474.2 Classification analysis with FSFC as pre-processing step for data reduction.4.2.1UCI data sets are used for classification testingData Set Name# ofClass# ofTuples# ofFeaturesSpambase 2 4601 57 Ionosphere 2 351 34 MultipleFeatures10 2000 649Spambase SVM11 features 71.67%23 features 81.30%34 features 86.01%46 features 91.30%57 features73.12%Ionosphere SVM7 features 61.90%14 features 62.86%20 features 61.90%27 features 63.81%34 features61.90%Multiple Features SVM130 features 85.33%260 features 85.17%389 features 85.83%519 features 87.00%649 features81.83% 4.2.2 Protein Data:The first data set has 315 features and 38009 tuples [3]. We use 10 fold cross validation for the accuracy result.Protein interaction SVM63 features 65.86%126 features 66.92%189 features 67.52%252 features 67.88%315 features70.53%The second data set with 2 classes has 300 features and 94466 tuples [3]. We use 10 fold cross validation for the accuracy result.Solvent SVM60 features 68.72%120 features 75.64%180 features 77.47%240 features 77.61%300 features78.05%5. Discussions and ConclusionThe difference of our algorithm from traditional unsupervised feature selection is two fold; it is clustering base so it does not require feature search. Inour algorithm k is the number of the features in the selection output. We only need to do the feature clustering once and get different feature subsets with various dimension numbers without extra computational cost. This characteristic is useful in data mining where multiscale representation of the data is often necessary. In our algorithm, k acts as a scale parameter which controls the degree of details in a more direct manner. These make it suitable for a wide variety of data mining tasks involving large dimensional data set.The novelty of our method is the absence of search process which contributes to the high-computational time requirement of those features selection algorithms. Our algorithm is based on pairwise feature similarity measures, which are fast to compute. Unlike other approaches, which are based on optimizing either classification accuracy or clustering performance explicitly. In our method, we determine a set of maximally independent features by discarding the redundant ones; this improves the applicability of the resulting features to other data mining task such as data reduction, summarization, and association mining in addition to clustering/classification.The experimental results on various biological data sets indicate our algorithm work well both for supervised learning and unsupervised learning. As our future plan, we would like to test our feature selection approach on biomedical literature mining and hope to report our findings in the near future.Acknowledgement: This work is supported partially by NSF CCF 0514679, and the NSF Career grant (IIS-0448023) and PA Dept of Health Grants (#239667).6. References[1] L. D. Baker and A. McCallum, “Distributional clusteringof words for text classification”, in SIGIR’98: Proceedings of the 21st Annual International ACM SIGIR, Melbourne, Australia, 1998, pp. 96–103.[2] A. Blum, and P. Langley, “Selection of relevant features and examples in machine learning”, Artificial Intelligence, vol. 97, pp. 245-271, 1997.[3] H. Chen, H. Zhou H., X. Hu, and I. Yoo, “Classification Comparison of Prediction of Solvent Accessibility from Protein Sequences”, in the 2nd Asia-Pacific Bioinformatics Conference, New Zealand, Jan 18-22, 2004.[4] M. Dash, H. Liu, and J. Yao, “Dimensionality Reductionof Unsupervised Data”, in 9th IEEE Int'l Conf. Tools with Artificial Intelligence, 1997, pp. 532-539. [5] M. Devaney and A. Ram, “Efficient Feature Selection in Conceptual Clustering”, in 14th Int'l Conf. Machine Learning, 1997.[6] I. S. Dhillon, S. Mallela, and R. Kumar, “A Divisive Information-Theoretic Feature Clustering Algorithm for Text Classification”, JMLR, vol. 3, pp.1265-1287, 2003.[7] J. G. Dy and C. E. Brodley, “Feature Subset Selection and Order Identification for Unsupervised Learning”, ICML, 2000, pp. 247-254.[8] D. H. Fisher, “Knowledge acquisition via incremental conceptual clustering, Machine Learning”, Machine Learning, vol. 2, pp.139-172, 1987.[9] I. Guyon and A. Elisseeff, “An Introduction to Variable and Feature Selection JMLR Special Issue on Variable and Feature Selection”, Kernel Machines Section, Mar, pp. 1157-1182, 2003.[10] X. Hu and Y. Yoo, “Cluster Ensemble and Its Applications in Gene Expression Analysis”, in BIBE, 2006. [11] T. Joachims, “Making large-Scale SVM Learning Practical”, Advances in Kernel Methods - Support Vector Learning, MIT-Press, 1999.[12] G. H. John, R. Kohavi, and K. Pfleger, “Irrelevant features and the subset selection problem”, in 11th International conference on Machine Learning, New Brunswick, NJ, 1994, pp. 121-129.[13] Y.S. Kim, N. Street, and F. Menczer, “Evolutionary model selection in unsupervised learning”, Intelligent Data Analysis, vol. 6, pp. 531-556, 2002.[14] P. Mitra, C. A. Murthy, and Sankar K. Pal, “Unsupervised Feature Selection Using Feature Similarity”, IEEE Transactions on Pattern Analysis and Machine Intelligenc, vol. 24, pp. 301-312, 2002.[15] M.E Morita, R. Sabourin, F. Bortolozzi, and C.Y. Suen, “Unsupervised Feature Selection Using Multi-Objective Genetic Algorithm for Handwritten Word Recognition”, in the 7th International Conference on Document Analysis and Recognition, Edinburgh, Scotland, 2003, pp.666-670.[16] N. Slonim and N. Tishby. “The power of word clusters for text classification.” In 23rd European Colloquium on Information Retrieval Research (ECIR), 2001.[17] L. Talavera, “Feature Selection as a Preprocessing Step for Hierarchical Clustering”, in 16th Int'l Conf. on Machine Learning, 1999, pp. 389-397.[18] L. Talavera, “Dependency-Based Feature Selection for Clustering Symbolic Data”, Intelligent Data Analysis, vol. 4, pp. 19-28, 2000.[19] P.L. Welcsh, M.K. Lee, R.M. Gonzalez-Hernandez, D.J. Black, M. Mahadevappa, E.M. Swisher, J.A. Warrington, and M.C. King, “BRCA1 transcriptionally regulates genes involved in breast tumorigenesis”, in Natl Acad Sci U S A 99, 2002, pp. 7560-7565.[20] Y. Zeng, J. Tang, J. Garcia-Frias, and G.R. Gao, “An Adaptive Meta-Clustering Approach: Combining The Information From Different Clustering Results”, in IEEE Computer Society Bioinformatics Conference, Stanford University, pp. 276-287.[21] “Machine Learning Repository”/~mlearn/MLRepository.html。