Soft Input Feature Selection within Neural Prosody Generation

Feature Selection Based on Mutual Information:Criteria of Max-Dependency,Max-Relevance,and Min-RedundancyHanchuan Peng,Member ,IEEE ,Fuhui Long,and Chris DingAbstract —Feature selection is an important problem for pattern classification systems.We study how to select good features according to the maximal statistical dependency criterion based on mutual information.Because of the difficulty in directly implementing the maximal dependency condition,we first derive an equivalent form,called minimal-redundancy-maximal-relevance criterion (mRMR),for first-order incremental feature selection.Then,we present a two-stage feature selection algorithm by combining mRMR and other more sophisticated feature selectors (e.g.,wrappers).This allows us to select a compact set of superior features at very low cost.We perform extensive experimental comparison of our algorithm and other methods using three different classifiers (naive Bayes,support vector machine,and linear discriminate analysis)and four different data sets (handwritten digits,arrhythmia,NCI cancer cell lines,andlymphoma tissues).The results confirm that mRMR leads to promising improvement on feature selection and classification accuracy.Index Terms —Feature selection,mutual information,minimal redundancy,maximal relevance,maximal dependency,classification.æ1I NTRODUCTIONINmany pattern recognition applications,identifying the most characterizing features (or attributes)of the ob-served data,i.e.,feature selection (or variable selection,among many other names)[30],[14],[17],[18],[15],[12],[11],[19],[31],[32],[5],is critical to minimize the classifica-tion error.Given the input data D tabled as N samples and M features X ¼f x i ;i ¼1;...;M g ,and the target classifica-tion variable c ,the feature selection problem is to find from the M -dimensional observation space,R M ,a subspace of m features,R m ,that “optimally”characterizes c .Given a condition defining the “optimal characteriza-tion,”a search algorithm is needed to find the best subspace.Because the total number of subspaces is 2M ,and the number of subspaces with dimensions no larger than m is Æm i ¼1Mi ÀÁ,it is hard to search the feature subspace exhaus-tively.Alternatively,many sequential-search-based approx-imation schemes have been proposed,including best individual features,sequential forward search,sequential forward floating search,etc.,(see [30],[14],[13]for a detailed comparison.).The optimal characterization condition often means the minimal classification error .In an unsupervised situation where theclassifiers arenot specified,minimalerrorusually requires the maximal statistical dependency of the target class c on the data distribution in the subspace R m (and vice versa).This scheme is maximal dependency (Max-Dependency).One of the most popular approaches to realize Max-Dependency is maximal relevance (Max-Relevance)feature selection:selecting the features with the highest relevance to the target class c .Relevance is usually characterized in terms of correlation or mutual information,of which the latter is one of the widely used measures to define dependency of variables.In this paper,we focus on the discussion of mutual-information-based feature selection.Given two random variables x and y ,their mutual information is defined in terms of their density functions p ðx Þ,p ðy Þ,and p ðx;y Þ:I ðx ;y Þ¼Z Zp ðx;y Þlog p ðx;y Þp ðx Þp ðy Þdxdy:ð1ÞIn Max-Relevance,the selected features x i are required,individually,to have the largest mutual information I ðx i ;c Þwith the target class c ,reflecting the largest dependency on the target class.In terms of sequential search,the m best individual features,i.e.,the top m features in the descent ordering of I ðx i ;c Þ,are often selected as the m features.In feature selection,it has been recognized that the combinations of individually good features do not necessa-rily lead to good classification performance.In other words,“the m best features are not the best m features”[4],[3],[14],[30].Some researchers have studied indirect or direct means to reduce the redundancy among features 1(e.g.,[4],[14],[19],[15],[22],[12],[5])and select features with the minimal redundancy (Min-Redundancy).For example,in the sequen-tial forward floating search [25],the joint dependency of features on the target class is maximized;as a by-product,the redundancy among features might be reduced.In [12],Jaeger et al.presented a prefiltering method to group variables,thus,redundant variables within each group can be removed.In.H.Peng and F.Long are with the Lawrence Berkeley National Laboratory,University of California at Berkeley,1Cyclotron Road,MS.84-171,Berkeley,CA 94720.E-mail:{hpeng,flong}@.. C.Ding is with the Computational Research Division,Lawrence Berkeley National Laboratory,1Cyclotron Road,Berkeley,CA 94720.E-mail:CHQDing@.Manuscript received 6Aug.2003;revised 1May 2004;accepted 3Dec.2004;published online 13June 2005.Recommended for acceptance by A.Del Bimbo.For information on obtaining reprints of this article,please send e-mail to:tpami@,and reference IEEECS Log Number TPAMI-0215-0803.1.Minimal redundancy has also been studied in feature extraction,which aims to find good features in a transformed domain.For instance,it has been well addressed in various techniques such as principal component analysis and independent component analysis [10],neural network feature extractors (e.g.,[22]),etc.0162-8828/05/$20.00ß2005IEEEPublished by the IEEE Computer Societyrelevance (mRMR)framework to minimize redundancy,and used a series of intuitive measures of relevance and redundancy to select promising features for both continuous and discrete data sets.Our work in this paper focuses on three issues that have not been touched in earlier work.First,although both Max-Relevance and Min-Redundancy have been intuitively used for feature selection,no theoretical analysis is given on why they can benefit selecting optimal features for classification.Thus,the first goal of this paper is to present a theoretical analysis showing that mRMR is equivalent to Max-Depen-dency for first-order feature selection,but is more efficient.Second,we investigate how to combine mRMR with other feature selection methods (such as [18],[15])into a two-stage selection algorithm.By doing this,we show that the space of candidate features selected by mRMR is more characterizing.This property of mRMR facilitates the integration of other feature selection schemes to find a compact subset of superior features at very low cost.Third,through comprehensive experiments we compare mRMR,Max-Relevance,Max-Dependency,and the two-stage feature selection algorithm,using three different classifiers and four data sets.The results show that mRMR and our two-stage algorithm are very effective in a wide range of feature selection applications.This paper is organized as follows:Section 2presents the theoretical analysis of the relationships of Max-Dependency,Max-Relevance,and Min-Redundancy.Section 3presents the two-stage feature selection algorithm,including schemes to integrate wrappers to select a squeezed subset of features.Section 4discusses implementation issues of density estima-tion for mutual information and several different classifiers.Section 5gives experimental results on four data sets,including handwritten characters,arrhythmia,NCI cancer cell lines,and lymphoma tissues.Sections 6and 7are discussions and conclusions,respectively.2R ELATIONSHIPS OF M AX -D EPENDENCY ,M AX -R ELEVANCE ,AND M IN -R EDUNDANCY2.1Max-DependencyIn terms of mutual information,the purpose of feature selection is to find a feature set S with m features f x i g ,which jointly have the largest dependency on the target class c .This scheme,called Max-Dependency,has the following form:max D ðS;c Þ;D ¼I ðf x i ;i ¼1;...;m g ;c Þ:ð2ÞObviously,when m equals 1,the solution is the feature that maximizes I ðx j ;c Þð1 j M Þ.When m >1,a simple incremental search scheme is to add one feature at one time:given the set with m À1features,S m À1,the m th feature can be determined as the one that contributes to the largest increase of I ðS ;c Þ,which takes the form of (3):I ðS m ;c Þ¼Z Zp ðS m ;c Þlog p ðS m ;c Þp ðS m Þp ðc ÞdS m dc¼Z Zp ðS m À1;x m ;c Þlogp ðS m À1;x m ;c Þp ðS m À1;x m Þp ðc ÞdS m À1dx m dc ¼Z ÁÁÁZp ðx 1;ÁÁÁ;x m ;c Þlogp ðx 1;ÁÁÁ;x m ;c Þp ðx 1;ÁÁÁ;x m Þp ðc Þdx 1ÁÁÁdx m dc:ð3Þoften hard to get an accurate estimation for multivariate density p ðx 1;...;x m Þand p ðx 1;...;x m ;c Þ,because of two difficulties in the high-dimensional space:1)the number of samples is often insufficient and 2)the multivariate density estimation often involves computing the inverse of the high-dimensional covariance matrix,which is usually an ill-posed problem.Another drawback of Max-Dependency is the slow computational speed.These problems are most pronounced for continuous feature variables.Even for discrete (categorical)features,the practical problems in implementing Max-Dependency cannot be completely avoided.For example,suppose each feature has three categorical states and N samples.K features could have a maximum min ð3K ;N Þjoint states.When the number of joint states increases very quickly and gets comparable to the number of samples,N ,the joint probability of these features,as well as the mutual information,cannot be estimated correctly.Hence,although Max-Dependency feature selection might be useful to select a very small number of features when N is large,it is not appropriate for applications where the aim is to achieve high classification accuracy with a reasonably compact set of features.2.2Max-Relevance and Min-RedundancyAs Max-Dependency criterion is hard to implement,an alternative is to select features based on maximal relevance criterion (Max-Relevance).Max-Relevance is to search features satisfying (4),which approximates D ðS;c Þin (2)with the mean value of all mutual information values between individual feature x i and class c :max D ðS;c Þ;D ¼1j S j Xx i2SI ðx i ;c Þ:ð4ÞIt is likely that features selected according to Max-Relevance could have rich redundancy,i.e.,the dependency among these features could be large.When two features highly depend on each other,the respective class-discrimi-native power would not change much if one of them were removed.Therefore,the following minimal redundancy (Min-Redundancy)condition can be added to select mutually exclusive features [5]:min R ðS Þ;R ¼1j S j 2X x i ;x j 2SI ðx i ;x j Þ:ð5ÞThe criterion combining the above two constraints is called “minimal-redundancy-maximal-relevance”(mRMR)[5].We define the operator ÈðD;R Þto combine D and R and consider the following simplest form to optimize D and R simultaneously:max ÈðD;R Þ;ȼD ÀR:ð6ÞIn practice,incremental search methods can be used to find thenear-optimalfeatures definedby Èð:Þ.Suppose wealready have S m À1,the feature set with m À1features.The task is to select the m th feature from the set f X ÀS m À1g .This is done by selecting the feature that maximizes Èð:Þ.The respective incremental algorithm optimizes the following condition:max x j 2X ÀS m À1I ðx j ;c ÞÀ1Xx i 2S m À1I ðx j ;x i Þ"#:ð7ÞThe computational complexity of this incremental search method is O ðj S j ÁM Þ.2.3Optimal First-Order Incremental SelectionWe prove in the following that the combination of Max-Relevance and Min-Redundancy criteria,i.e.,the mRMR criterion,is equivalent to the Max-Dependency criterion if one feature is selected (added)at one time.We call this type of selection the “first-order”incremental search.We have the following theorem:Theorem.For the first-order incremental search,mRMR is equivalent to Max-Dependency (2).Proof.By definition of the first-order search,we assume that S m À1,i.e.,the set of m À1features,has already been obtained.The task is to select the optimal m th feature x m from set f X ÀS m À1g .The dependency D in (2)and (3)is represented by mutual information,i.e.,D ¼I ðS m ;c Þ,where S m ¼f S m À1;x m g can be treated as a multivariate variable.Thus,by the definition of mutual information,we have:I ðS m ;c Þ¼H ðc ÞþH ðS m ÞÀH ðS m ;c Þ¼H ðc ÞþH ðS m À1;x m ÞÀH ðS m À1;x m ;c Þ;ð8Þwhere H ð:Þis the entropy of the respective multivariate(or univariate)variables.Now,we define the following quantity J ðS m Þ¼J ðx 1;...;x m Þfor scalar variables x 1;...;x m ,J ðx 1;x 2;...;x m Þ¼Z ÁÁÁZp ðx 1;...;x m Þlog p ðx 1;x 2;...;x m Þp ðx 1ÞÁÁÁp ðx m Þdx 1ÁÁÁdx m :ð9ÞSimilarly,we define J ðS m ;c Þ¼J ðx 1;...;x m ;c Þas J ðx 1;x 2;...;x m ;c Þ¼Z ÁÁÁZp ðx 1;...;x m ;c Þlog p ðx 1;x 2;...;x m ;c Þ1m dx 1ÁÁÁdx m dc:ð10ÞWe can easily derive (11)and (12)from (9)and (10),H ðS m À1;x m Þ¼H ðS m Þ¼X m i ¼1H ðx i ÞÀJ ðS m Þ;ð11ÞH ðS m À1;x m ;c Þ¼H ðS m ;c Þ¼H ðc ÞþX m i ¼1H ðx i ÞÀJ ðS m ;c Þ:ð12ÞBy substituting them to the corresponding terms in(8),we haveI ðS m ;c Þ¼J ðS m ;c ÞÀJ ðS m Þ¼J ðS m À1;x m ;c ÞÀJ ðS m À1;x m Þ:ð13ÞObviously,Max-Dependency is equivalent to simul-taneously maximizing the first term and minimizing the second term.We can use the Jensen’s Inequality [16]to show the second term J ðS m À1;x m Þis lower-bounded by 0.Arelated and slightly simpler proof is to consider the inequality log ðz Þ z À1with the equality if and only if z ¼1.We see thatÀJ ðx 1;x 2;...;x m Þ¼Z ÁÁÁZp ðx 1;...;x m Þlog p ðx 1ÞÁÁÁp ðx m Þp ðx 1;...;x m Þdx 1ÁÁÁdx mZ ÁÁÁZp ðx 1;...;x m Þp ðx 1ÞÁÁÁp ðx m Þp ðx 1;...;x m ÞÀ1 !dx 1ÁÁÁdx m ¼Z ÁÁÁZp ðx 1ÞÁÁÁp ðx m Þdx 1ÁÁÁdx m ÀZ ÁÁÁZp ðx 1;ÁÁÁ;x m Þdx 1ÁÁÁdx m ¼1À1¼0:ð14ÞIt is easy to verify that the minimum is attained when p ðx 1;...;x m Þ¼p ðx 1ÞÁÁÁp ðx m Þ,i.e.,all the variables are independent of each other.As all the m À1features have been selected,this pair-wise independence condition means that the mutual information between x m and any selected feature x i ði ¼1;...;m À1Þis minimized.This is the Min-Redundancy criterion.We can also derive the upper bound of the first term in (13),J ðS m À1;c;x m Þ.For simplicity,let us first show the upper bound of the general form J ðy 1;...;y n Þ,assuming there are n variables y 1;...;y n .This can be seen as follows:J ðy 1;y 2;...;y n Þ¼Z ÁÁÁZp ðy 1;...;y n Þlogp ðy 1;...;y n Þp ðy 1ÞÁÁÁp ðy n Þdy 1ÁÁÁdy n ¼Z ÁÁÁZp ðy 1;...;y n Þlog p ðy 1j y 2;...;y n Þp ðy 2j y 3;...;y n ÞÁÁÁp ðy n À1j y n Þp ðy n Þp ðy 1ÞÁÁÁp ðy n À1Þp ðy n Þdy 1ÁÁÁdy n¼X n À1i ¼1H ðy i ÞÀH ðy 1j y 2;...;y n ÞÀH ðy 2j y 3;...;y n ÞÀH ðy n À1j y n ÞX n À1i ¼1H ðy i Þ:ð15ÞEquation (15)can be easily extended as J ðy 1;y 2;...;y n Þ minX n i ¼2H ðy i Þ;X n i ¼1;i ¼2H ðy i Þ;ÁÁÁ;X n i ¼1;i ¼n À1H ðy i Þ;X n À1i ¼1H ðy i Þ():ð16ÞIt is easy to verify the maximum of J ðy 1;...;y n Þor,similarly,the first term in (13),J ðS m À1;c;x m Þ,is attained when all variables are maximally dependent.When S m À1has been fixed,this indicates that x m and c should have the maximal dependency.This is the Max-Relevance criterion.Therefore,according to (13),as a combination of Max-Relevance and Min-Redundancy,mRMR is equivalent to Max-Dependency for first-order selection.t u Note that the quantity J ð:Þin (9)and (10)has also been called “mutual information”for multiple scalar variables [10].We have the following observations:1.Minimizing JðS mÞonly is equivalent to searchingmutually exclusive(independent)features.2This isinsufficient for selecting highly discriminativefeatures.2.Maximizing JðS m;cÞonly leads to Max-Relevance.Clearly,the difference between mRMR and Max-Relevance is rooted in the different definitions ofdependency(in terms of mutual information).Equa-tion(10)does not consider the joint effect of features onthe target class.On the contrary,Max-Dependency((2)and(3))considers the dependency between the datadistribution in subspace R m and the target class c.Thisdifference is critical in many circumstances.3.The equivalence between Max-Dependency andmRMR indicates mRMR is an optimal first-orderimplementation scheme of Max-Dependency.pared to Max-Dependency,mRMR avoids theestimation of multivariate densities pðx1;...;x mÞand pðx1;...;x m;cÞ.Instead,calculating the bivariatedensity pðx i;x jÞand pðx i;cÞcould be much easierand more accurate.This also leads to a more efficientfeature selection algorithm.3F EATURE S ELECTION A LGORITHMSOur goal is to design efficient algorithms to select a compact set of features.In Section2,we propose a fast mRMR feature selection scheme(7).A remaining issue is how to determine the optimal number of features m.Since a mechanism to remove potentially redundant features from the already selected features has not been considered in the incremental selection,according to the idea of mRMR,we need to refine the results of incremental selection.We present a two-stage feature selection algorithm.In the first stage,we find a candidate feature set using the mRMR incremental selection method.In the second stage, we use other more sophisticated schemes to search a compact feature subset from the candidate feature set.3.1Selecting the Candidate Feature SetTo select the candidate feature set,we compute the cross-validation classification error for a large number of features and find a relatively stable range of small error.This range is called .The optimal number of features(denoted as nÃ) of the candidate set is determined within .The whole process includes three steps:e mRMR incremental selection(7)to select n(apreset large number)sequential features from theinput X.This leads to n sequential feature setsS1&S2&...&S nÀ1&S n.pare all the n sequential feature sets S1;...;S k;...;S n;ð1k nÞto find the range of k,called ,within which the respective(cross-validation classifi-cation)error e k is consistently small(i.e.,has bothsmall mean and small variance).3.Within ,find the smallest classification erroreümin e k.The optimal size of the candidate featureset,nÃ,ischosenasthesmallest k thatcorrespondsto eÃ.3.2Selecting Compact Feature SubsetsMany sophisticated schemes can be used to search the compact feature subsets from the candidate set S nÃ.To illustrate that mRMR can produce better candidate features, which favors better combination with other methods,we use wrappers to search the compact feature subsets.A wrapper[15],[18]is a feature selector that convolves with a classifier(e.g.,naive Bayes classifier),with the direct goal to minimize the classification error of the particular ually,wrappers can yield high classification accuracy for a particular classifier at the cost of high computational complexity and less generalization of the selected features on other classifiers.This is different from the mRMR method introduced above,which does not optimize the classification error directly.The latter type of approach(e.g.,mRMR and Max-Relevance),sometimes called“filter”[18],[15],often selects features by testing whether some preset conditions about the features and the target class are satisfied.In practice,the filter approach has much lower complexity than wrappers;the features thus selected often yield comparable classification errors for different classifiers, because such features often form intrinsic clusters in the respective subspace.By using mRMR feature selection in the first-stage,we intend to find a small set of candidate features,in which the wrappers can be applied at a much lower cost in the second-stage.We will continue our discussion on this point in Section3.3.In this paper,we consider two selection schemes of wrapper,i.e.,the backward and forward selections:1.The backward selection tries to exclude one redun-dant feature at a time from the current feature set S k(initially,k is set to nÃobtained in Section3.1),with theconstraint that the resultant feature set S kÀ1leads to aclassification error e kÀ1no worse than e k.Becauseevery feature in S k can be considered in removal,thereare k different configurations of S kÀ1.For eachpossible configuration,the respective classificationerror e kÀ1is calculated.If,for every configuration,thecorresponding e kÀ1is larger than e k,there is no gain ineither classification accuracy or feature dimensionreduction(i.e.,every existing feature in S k appears tobe useful),thus,the backward selection terminates(accordingly,the size of the compact feature subset,m,is set to k).Otherwise,among the k configurations ofS kÀ1,the one that leads to the largest error reduction ischosen as the new feature set.If there are multipleconfigurations leading to the same error reduction,one of them is chosen randomly.This decrementalselection procedure is repeated until the terminationcondition is satisfied.2.The forward selection tries to select a subset ofm features from S nÃin an incremental manner.Initially,the classification error is set to the numberof samples,i.e.,N.The wrapper first searches for thefeature subset with one feature,denoted as Z1,byselecting the feature xÃ1that leads to the largest errorreduction.Then,from the set f S nÀZ1g,the wrapperselects the feature xÃ2so that the feature set Z2¼f Z1;xÃ2g leads to the largest error reduction.Thisincremental selection repeats until the classificationerror begins to increase,i.e.,e kþ1>e k.Note that we2.In the field of feature extraction,minimizing JðS mÞhas led to an algorithm of independent component analysis[10].allow the incremental search to continue when e kþ1equals e k,because we want to search a space as large aspossible.Once the termination condition is satisfied,the selected number of features,m,is chosen as thedimension for which the lowest error is first reached.For example,suppose the sequence of classificationerrors of the first six features is[10,8,4,4,4,7].Theforward selection will terminate at five features,butonly return the first three features as the result;in thisway we obtain a more compact set of features thatminimizes the error.3.3Characteristic Feature SpaceGiven two feature sets S1n and S2n both containing n features, and a classifierÀ,we say the feature space of S1n is more characteristic if the classification error(using classifierÀ)on S1n issmallerthanon S2n.Thisdefinitionofcharacteristic spacecan be extended recursively to the subsets(subspaces)of S1n andS2 n .Suppose we have a feature selection method F to generatea series of feature subsets in S1n:S11&S12&...&S1k&...&S1nÀ1&S1n,and,similarly,a series of subsets inS2 n :S21&...&S2k&...&S2n.We say S1n is recursively morecharacteristic(RM-characteristic)than S2n on the range ¼½k lower;k upper ð1k lower<k upper nÞ,if for every k2 , the classification error on S1k is consistently smaller than on S2k.To determine which one of the feature sets S1n and S2n is superior,it is often insufficient to compare the classification errors for a specific size of the feature sets.A better way is to observe which set is RM-characteristic for a reasonably large range .In the extreme case,we use ¼½1;n .Given two feature selection methods F1and F2,if,the feature sets generated by F1are RM-characteristic than those generated by F2,we believe the method F1is better than F2.Let us consider the following example to compare mRMR and Max-Relevance based on the concept of RM-characteristic feature space.As a comprehensive study,we consider both the sequential and nonsequential feature sets as follows(more details will be given in experiments):1.A direct comparison is to examine whether themRMR sequential feature sets are RM-characteristicthan Max-Relevance sequential feature sets.We useboth methods to select n sequential feature sets S1&...&S k&...&S n and compute the respectiveclassification errors.If,for most k2½1;n ,we obtainsmaller errors on mRMR feature sets,we canconclude that mRMR is better than Max-Relevancefor the sequential(or incremental)feature selection.2.We also use other feature selection methods(e.g.,wrappers)in the second stage of our feature-selectionalgorithm to probe whether mRMR is better than Max-Relevance for nonsequential feature sets.For example,for the mRMR and Max-Relevance candidate featuresets with nÃfeatures,we use the backward-selection-wrapper to produce two series of feature sets withk¼nÃÀ1;nÃÀ2;...;m features by removing somenonsequential features that are potentially redundant.Then,the respective classification errors of thesefeature sets are computed.If,for most k,we find themRMR nonsequential feature subset leads to lowererror,we conclude the mRMR candidate feature set is(approximately)RM-characteristic than the Max-Relevance candidate feature set.3.Both the forward and backward selections ofwrapper are used.Different classifiers(as discussedlater in Section4.2)are also considered in wrappers.We use both mRMR and Max-Relevance methods toselect the same number of candidate features andcompare the classification errors of the featuresubsets thereafter selected by wrappers.If all theobservations agree that the mRMR candidate featureset is RM-characteristic,we have high confidencethat mRMR is a superior feature selection method.4.Given two feature sets,if S1n is RM-characteristicthan S2n,then it is faithful to compare the lowesterrors obtained for the subsets of S1n and S2n.Clearly,for feature spaces containing the same number of features,wrappers can be applied more effectively on the space that is RM-characteristic.This also indicates that wrappers can be applied at a lower cost,by improving the characterizing strength of features and reducing the number of pre-selected features.In real situations,it might not be possible to obtain e1k<e2k for every k in .Hence,we can define a confidence score0 1to indicate the percentage of different k values for which the e1k<e2k condition is satisfied.For example,when ¼0:90 (90percent k-values correspond to the e1k<e2k condition),it is safe to claim that S1n is approximately RM-characteristic than S2n on .As can be seen in the experiments,usually this approximation is sufficient to compare two series of feature subsets.4I MPLEMENTATION I SSUESBefore presenting the experimental results in Section5,we discuss two implementation issues regarding the experi-ments:1)calculation of mutual information for both discrete and continuous data and2)multiple types of classifiers used in our experiments.4.1Mutual Information EstimationWe consider mutual-information-based feature selection for both discrete and continuous data.For discrete(categorical) feature variables,the integral operation in(1)reduces to summation.In this case,computing mutual information is straightforward,because both joint and marginal probabil-ity tables can be estimated by tallying the samples of categorical variables in the data.However,when at least one of variables x and y is continuous,their mutual information Iðx;yÞis hard to compute,because it is often difficult to compute the integral in the continuous space based on a limited number of samples. One solution is to incorporate data discretization as a preprocessing step.For some applications where it is unclear how to properly discretize the continuous data,an alternative solution is to use density estimation method(e.g.,Parzen windows)toapproximate Iðx;yÞ,assuggestedbyearlierwork in medical image registration[7]and feature selection[17].Given N samples of a variable x,the approximate density function^pðxÞhas the following form:^pðxÞ¼1X Ni¼1ðxÀxðiÞ;hÞ;ð17Þwhere ð:Þis the Parzen window function as explained below, xðiÞis the i th sample,and h is the window width.Parzen has。

NIPS 2003 feature selection challenge-Madelon Data
Set
英文关键词：
feature selection,binary,classification,machine learning,
中文关键词：
功能选择、二进制文件、分类、机器学习，
数据格式：
TEXT
数据介绍：
MADELON is an artificial dataset, which was part of the NIPS 2003 feature selection challenge. This is a two-class classification problem with continuous input variables. The difficulty is that the problem is multivariate and highly non-linear.
Number of variables/features/attributes:
Real: 20
Probes: 480
Total: 500
[以下内容来由机器自动翻译]
最佳女主角：是一个人工的数据集，这是NIPS 2003 功能选择挑战的一部分。

这是一个连续输入变量的两类分类问题。

困难在于多元和高度非线性是问题。

变量/功能/属性的数目：真实：20探测器：480总：500
[自动翻译由Microsoft Translator完成]
点此下载完整数据集。

Feature Selection for High-Dimensional Data:A Fast Correlation-Based Filter SolutionLei Yu leiyu@ Huan Liu hliu@ Department of Computer Science&Engineering,Arizona State University,Tempe,AZ85287-5406,USAAbstractFeature selection,as a preprocessing step tomachine learning,has been effective in reduc-ing dimensionality,removing irrelevant data,increasing learning accuracy,and improvingcomprehensibility.However,the recent in-crease of dimensionality of data poses a se-vere challenge to many existing feature se-lection methods with respect to efficiencyand effectiveness.In this work,we intro-duce a novel concept,predominant correla-tion,and propose a fastfilter method whichcan identify relevant features as well as re-dundancy among relevant features withoutpairwise correlation analysis.The efficiencyand effectiveness of our method is demon-strated through extensive comparisons withother methods using real-world data of highdimensionality.1.IntroductionFeature selection is frequently used as a preprocessing step to machine learning.It is a process of choosing a subset of original features so that the feature space is optimally reduced according to a certain evaluation criterion.Feature selection has been a fertilefield of research and development since1970’s and shown very effective in removing irrelevant and redundant fea-tures,increasing efficiency in learning tasks,improv-ing learning performance like predictive accuracy,and enhancing comprehensibility of learned results(Blum &Langley,1997;Dash&Liu,1997;Kohavi&John, 1997).In recent years,data has become increasingly larger in both rows(i.e.,number of instances)and columns(i.e.,number of features)in many applica-tions such as genome projects(Xing et al.,2001),text categorization(Yang&Pederson,1997),image re-trieval(Rui et al.,1999),and customer relationship management(Ng&Liu,2000).This enormity may cause serious problems to many machine learning al-gorithms with respect to scalability and learning per-formance.For example,high dimensional data(i.e., data sets with hundreds or thousands of features),can contain high degree of irrelevant and redundant infor-mation which may greatly degrade the performance of learning algorithms.Therefore,feature selection be-comes very necessary for machine learning tasks when facing high dimensional data nowadays.However,this trend of enormity on both size and dimensionality also poses severe challenges to feature selection algorithms. Some of the recent research efforts in feature selection have been focused on these challenges from handling a huge number of instances(Liu et al.,2002b)to deal-ing with high dimensional data(Das,2001;Xing et al., 2001).This work is concerned about feature selection for high dimensional data.In the following,wefirst review models of feature selection and explain why a filter solution is suitable for high dimensional data,and then review some recent efforts in feature selection for high dimensional data.Feature selection algorithms can broadly fall into the filter model or the wrapper model(Das,2001;Kohavi &John,1997).Thefilter model relies on general char-acteristics of the training data to select some features without involving any learning algorithm,therefore it does not inherit any bias of a learning algorithm.The wrapper model requires one predetermined learning al-gorithm in feature selection and uses its performance to evaluate and determine which features are selected. As for each new subset of features,the wrapper model needs to learn a hypothesis(or a classifier).It tends to give superior performance as itfinds features better suited to the predetermined learning algorithm,but it also tends to be more computationally expensive(Lan-gley,1994).When the number of features becomes very large,thefilter model is usually a choice due to its computational efficiency.Proceedings of the Twentieth International Conference on Machine Learning(ICML-2003),Washington DC,2003.To combine the advantages of both models,algorithms in a hybrid model have recently been proposed to deal with high dimensional data(Das,2001;Ng,1998;Xing et al.,2001).In these algorithms,first,a goodness measure of feature subsets based on data characteris-tics is used to choose best subsets for a given cardinal-ity,and then,cross validation is exploited to decide a final best subset across different cardinalities.These algorithms mainly focus on combiningfilter and wrap-per algorithms to achieve best possible performance with a particular learning algorithm at the same time complexity offilter algorithms.In this work,we focus on thefilter model and aim to develop a new feature selection algorithm which can effectively remove both irrelevant and redundant features and is less costly in computation than the current available algorithms.In section2,we review current algorithms within the filter model and point out their problems in the context of high dimensionality.In section3,we describe corre-lation measures which form the base of our method in evaluating feature relevance and redundancy.In sec-tion4,wefirst propose our method which selects good features for classification based on a novel concept, predominant correlation,and then present a fast algorithm with less than quadratic time complexity.In section5,we evaluate the efficiency and effectiveness of this algorithm via extensive experiments on various real-world data sets comparing with other representa-tive feature selection algorithms,and discuss the im-plications of thefindings.In section6,we conclude our work with some possible extensions.2.Related WorkWithin thefilter model,different feature selection al-gorithms can be further categorized into two groups, namely feature weighting algorithms and subset search algorithms,based on whether they evaluate the good-ness of features individually or through feature sub-sets.Below,we discuss the advantages and shortcom-ings of representative algorithms in each group. Feature weighting algorithms assign weights to fea-tures individually and rank them based on their rel-evance to the target concept.There are a number of different definitions on feature relevance in machine learning literature(Blum&Langley,1997;Kohavi& John,1997).A feature is good and thus will be se-lected if its weight of relevance is greater than a thresh-old value.A well known algorithm that relies on rele-vance evaluation is Relief(Kira&Rendell,1992).The key idea of Relief is to estimate the relevance of fea-tures according to how well their values distinguish be-tween the instances of the same and different classes that are near each other.Relief randomly samples a number(m)of instances from the training set and up-dates the relevance estimation of each feature based on the difference between the selected instance and the two nearest instances of the same and opposite classes.Time complexity of Relief for a data set with M instances and N features is O(mMN).With m be-ing a constant,the time complexity becomes O(MN), which makes it very scalable to data sets with both a huge number of instances and a very high dimension-ality.However,Relief does not help with removing redundant features.As long as features are deemed relevant to the class concept,they will all be selected even though many of them are highly correlated to each other(Kira&Rendell,1992).Many other algo-rithms in this group have similar problems as Relief does.They can only capture the relevance of features to the target concept,but cannot discover redundancy among features.However,empirical evidence from fea-ture selection literature shows that,along with irrele-vant features,redundant features also affect the speed and accuracy of learning algorithms and thus should be eliminated as well(Hall,2000;Kohavi&John,1997). Therefore,in the context of feature selection for high dimensional data where there may exist many redun-dant features,pure relevance-based feature weighting algorithms do not meet the need of feature selection very well.Subset search algorithms search through candidate feature subsets guided by a certain evaluation mea-sure(Liu&Motoda,1998)which captures the good-ness of each subset.An optimal(or near optimal)sub-set is selected when the search stops.Some existing evaluation measures that have been shown effective in removing both irrelevant and redundant features in-clude the consistency measure(Dash et al.,2000)and the correlation measure(Hall,1999;Hall,2000).Con-sistency measure attempts tofind a minimum num-ber of features that separate classes as consistently as the full set of features can.An inconsistency is de-fined as two instances having the same feature values but different class labels.In Dash et al.(2000),dif-ferent search strategies,namely,exhaustive,heuristic, and random search,are combined with this evalua-tion measure to form different algorithms.The time complexity is exponential in terms of data dimension-ality for exhaustive search and quadratic for heuristic search.The complexity can be linear to the number of iterations in a random search,but experiments show that in order tofind best feature subset,the number of iterations required is mostly at least quadratic to the number of features(Dash et al.,2000).In Hall(2000), a correlation measure is applied to evaluate the good-ness of feature subsets based on the hypothesis that a good feature subset is one that contains features highly correlated with the class,yet uncorrelated with each other.The underlying algorithm,named CFS,also exploits heuristic search.Therefore,with quadratic or higher time complexity in terms of dimensionality, existing subset search algorithms do not have strong scalability to deal with high dimensional data.To overcome the problems of algorithms in both groups and meet the demand for feature selection for high dimensional data,we develop a novel algorithm which can effectively identify both irrelevant and redundant features with less time complexity than subset search algorithms.3.Correlation-Based MeasuresIn this section,we discuss how to evaluate the good-ness of features for classification.In general,a feature is good if it is relevant to the class concept but is not redundant to any of the other relevant features.If we adopt the correlation between two variables as a good-ness measure,the above definition becomes that a fea-ture is good if it is highly correlated with the class but not highly correlated with any of the other features. In other words,if the correlation between a feature and the class is high enough to make it relevant to(or predictive of)the class and the correlation between it and any other relevant features does not reach a level so that it can be predicted by any of the other relevant features,it will be regarded as a good feature for the classification task.In this sense,the problem of fea-ture selection boils down tofind a suitable measure of correlations between features and a sound procedure to select features based on this measure.There exist broadly two approaches to measure the correlation between two random variables.One is based on classical linear correlation and the other is based on information theory.Under thefirst approach, the most well known measure is linear correlation co-efficient.For a pair of variables(X,Y),the linear correlation coefficient r is given by the formular=i(x i−x i)(y i−y i)i(x i−x i)2i(y i−y i)2(1)where x i is the mean of X,and y i is the mean of Y. The value of r lies between-1and1,inclusive.If X and Y are completely correlated,r takes the value of 1or-1;if X and Y are totally independent,r is zero. It is a symmetrical measure for two variables.Other measures in this category are basically variations of the above formula,such as least square regression er-ror and maximal information compression index(Mi-tra et al.,2002).There are several benefits of choos-ing linear correlation as a feature goodness measure for classification.First,it helps remove features with near zero linear correlation to the class.Second,it helps to reduce redundancy among selected features. It is known that if data is linearly separable in the original representation,it is still linearly separable if all but one of a group of linearly dependent features are removed(Das,1971).However,it is not safe to always assume linear correlation between features in the real world.Linear correlation measures may not be able to capture correlations that are not linear in nature. Another limitation is that the calculation requires all features contain numerical values.To overcome these shortcomings,in our solution we adopt the other approach and choose a correlation measure based on the information-theoretical concept of entropy,a measure of the uncertainty of a random variable.The entropy of a variable X is defined asH(X)=−iP(x i)log2(P(x i)),(2)and the entropy of X after observing values of another variable Y is defined asH(X|Y)=−jP(y j)iP(x i|y j)log2(P(x i|y j)),(3) where P(x i)is the prior probabilities for all values of X,and P(x i|y i)is the posterior probabilities of X given the values of Y.The amount by which the en-tropy of X decreases reflects additional information about X provided by Y and is called information gain(Quinlan,1993),given byIG(X|Y)=H(X)−H(X|Y).(4)According to this measure,a feature Y is regarded more correlated to feature X than to feature Z,if IG(X|Y)>IG(Z|Y).About information gain mea-sure,we have the following theorem.Theorem Information gain is symmetrical for two random variables X and Y.Proof Sketch:To prove IG(X|Y)=IG(Y|X),we need to prove H(X)−H(X|Y)=H(Y)−H(Y|X). This can be easily derived from H(X,Y)=H(X)+ H(Y|X)=H(Y)+H(X|Y).Symmetry is a desired property for a measure of cor-relations between features.However,information gain is biased in favor of features with more values.Fur-thermore,the values have to be normalized to ensurethey are comparable and have the same affect.There-fore,we choose symmetrical uncertainty(Press et al., 1988),defined as follows.SU(X,Y)=2IG(X|Y)H(X)+H(Y)(5)It compensates for information gain’s bias toward fea-tures with more values and normalizes its values to the range[0,1]with the value1indicating that knowledge of the value of either one completely predicts the value of the other and the value0indicating that X and Y are independent.In addition,it still treats a pair of features symmetrically.These entropy-based mea-sures require nominal features,but they can be applied to measure correlations between continuous features as well,if the values are discretized properly in ad-vance(Fayyad&Irani,1993;Liu et al.,2002a).There-fore,we use symmetrical uncertainty in this work. 4.A Correlation-Based Filter Approach4.1.MethodologyUsing symmetrical uncertainty(SU)as the goodness measure,we are now ready to develop a procedure to select good features for classification based on corre-lation analysis of features(including the class).This involves two aspects:(1)how to decide whether a fea-ture is relevant to the class or not;and(2)how to decide whether such a relevant feature is redundant or not when considering it with other relevant features. The answer to thefirst question can be using a thresh-old SU value decided by the user,as the method used by many other feature weighting algorithms(e.g.,Re-lief).More specifically,suppose a data set S contains N features and a class C.Let SU i,c denote the SU value that measures the correlation between a feature f i and the class C(named c-correlation),then a subset S of relevant features can be decided by a threshold SU valueδ,such that∀f i∈S ,1≤i≤N,SU i,c≥δ. The answer to the second question is more complicated because it may involve analysis of pairwise correlations between all features(named f-correlation),which re-sults in a time complexity of O(N2)associated with the number of features N for most existing algorithms. To solve this problem,we propose our method below. Since f-correlations are also captured by SU values, in order to decide whether a relevant feature is redun-dant or not,we need tofind a reasonable way to decide the threshold level for f-correlations as well.In other words,we need to decide whether the level of correla-tion between two features in S is high enough to cause redundancy so that one of them may be removed from S .For a feature f i in S ,the value of SU i,c quantifies the extent to which f i is correlated to(or predictive of)the class C.If we examine the value of SU j,i for ∀f j∈S (j=i),we will also obtain quantified es-timations about the extent to which f i is correlated to(or predicted by)the rest relevant features in S . Therefore,it is possible to identify highly correlated features to f i in the same straightforward manner as we decide S ,using a threshold SU value equal or sim-ilar toδ.We can do this for all features in S .How-ever,this method only sounds reasonable when we try to determine highly correlated features to one concept while not considering another concept.In the con-text of a set of relevant features S already identified for the class concept,when we try to determine the highly correlated features for a given feature f i within S ,it is more reasonable to use the c-correlation level between f i and the class concept,SU i,c,as a refer-ence.The reason lies on the common phenomenon-a feature that is correlated with one concept(e.g.,the class)at a certain level may also be correlated with some other concepts(features)at the same or an even higher level.Therefore,even the correlation between this feature and the class concept is larger than some thresholdδand thereof making this feature relevant to the class concept,this correlation is by no means pre-dominant.To be more precise,we define the concept of predominant correlation as follows.Definition1(Predominant correlation).The corre-lation between a feature f i(f i∈S)and the class C is predominant iffSU i,c≥δ,and∀f j∈S (j=i),there exists no f j such that SU j,i≥SU i,c.If there exists such f j to a feature f i,we call it a redundant peer to f i and use S Pito denote the set of all redundant peers for f i.Given f i∈S and S Pi (S Pi=∅),we divide S Piinto two parts,S Pi+andS Pi−,where SP i+={fj|f j∈S Pi,SU j,c>SU i,c}and S Pi−={fj|f j∈S Pi,SU j,c≤SU i,c}.Definition2(Predominant feature).A feature is pre-dominant to the class,iffits correlation to the class is predominant or can become predominant after remov-ing its redundant peers.According to the above definitions,a feature is good if it is predominant in predicting the class concept, and feature selection for classification is a process that identifies all predominant features to the class concept and removes the rest.We now propose three heuristics that together can effectively identify predominant fea-tures and remove redundant ones among all relevant features,without having to identify all the redundant peers for every feature in S ,and thus avoids pairwise analysis of f-correlations between all relevant features.Our assumption in developing these heuristics is that if two features are found to be redundant to each other and one of them needs to be removed,removing the one that is less relevant to the class concept keeps more information to predict the class while reducing redun-dancy in the data.Heuristic1(if S Pi +=∅).Treat fias a predom-inant feature,remove all features in S Pi −,and skipidentifying redundant peers for them.Heuristic2(if S Pi +=∅).Process all features inS Pi +before deciding whether or not to remove fi.Ifnone of them becomes predominant,follow Heuristic1; otherwise only remove f i and decide whether or not to remove features in S Pi−based on other features in S . Heuristic3(starting point).The feature with the largest SU i,c value is always a predominant feature and can be a starting point to remove other features.4.2.Algorithm and AnalysisBased on the methodology presented before,we de-velop an algorithm,named FCBF(Fast Correlation-Based Filter).As in Figure1,given a data set withinput:S(f1,f2,...,f N,C)//a training data set δ//a predefined threshold output:S best//an optimal subset1begin2for i=1to N do begin3calculate SU i,c for f i;4if(SU i,c≥δ)5append f i to Slist ;6end;7order Slist in descending SU i,c value;8f p=getF irstElement(Slist );9do begin10f q=getNextElement(Slist ,f p);11if(f q<>NULL)12do begin13f q=f q;14if(SU p,q≥SU q,c)15remove f q from Slist ;16f q=getNextElement(Slist ,f q);17else f q=getNextElement(Slist ,f q);18end until(f q==NULL);19f p=getNextElement(Slist ,f p);20end until(f p==NULL);21S best=Slist ;22end;Figure1.FCBF Algorithm N features and a class C,the algorithmfinds a setof predominant features S best for the class concept.It consists of two major parts.In thefirst part(line2-7), it calculates the SU value for each feature,selects rele-vant features into Slistbased on the predefined thresh-oldδ,and orders them in descending order according to their SU values.In the second part(line8-20),it further processes the ordered list Slistto remove redundant features and only keeps predominant ones among all the selected relevant features.According to Heuristic1,a feature f p that has already been deter-mined to be a predominant feature can always be used tofilter out other features that are ranked lower than f p and have f p as one of its redundant peers.The iteration starts from thefirst element(Heuristic3)inSlist(line8)and continues as follows.For all the re-maining features(from the one right next to f p to thelast one in Slist),if f p happens to be a redundant peerto a feature f q,f q will be removed from Slist(Heuris-tic2).After one round offiltering features based on f p,the algorithm will take the currently remaining fea-ture right next to f p as the new reference(line19)to repeat thefiltering process.The algorithm stops untilthere is no more feature to be removed from Slist. Thefirst part of the above algorithm has a linear time complexity in terms of the number of features N.As to the second part,in each iteration,using the pre-dominant feature f p identified in the previous round, FCBF can remove a large number of features that are redundant peers to f p in the current iteration.The best case could be that all of the remaining features following f p in the ranked list will be removed;the worst case could be none of them.On average,we can assume that half of the remaining features will be removed in each iteration.Therefore,the time com-plexity for the second part is O(N log N)in terms of N.Since the calculation of SU for a pair of features is linear in term of the number of instances M in a data set,the overall complexity of FCBF is O(MN log N).5.Empirical StudyThe objective of this section is to evaluate our pro-posed algorithm in terms of speed,number of selected features,and learning accuracy on selected features.5.1.Experiment SetupIn our experiments,we choose three representative fea-ture selection algorithms in comparison with FCBF. One is a feature weighting algorithm,ReliefF(an ex-tension to Relief)which searches for several nearest neighbors to be robust to noise and handles multi-ple classes(Kononenko,1994);the other two are sub-set search algorithms which exploit sequential forward search and utilizes correlation measure or consistency measure to guide the search,denoted as CorrSF and ConsSF respectively.CorrSF is a variation of the CFS algorithm mentioned in section2.The reason why we prefer CorrSF to CFS is because both ex-periments in Hall(1999)and our initial experiments show that CFS only produces slightly better results than CorrSF,but CorrSF based on sequential forward search runs faster than CFS based on bestfirst search with5nodes expansion and therefore is more suitable for high dimensional data.In addition to feature se-lection algorithms,we also select two different learning algorithms,C4.5(Quinlan,1993)and NBC(Witten& Frank,2000),to evaluate the accuracy on selected fea-tures for each feature selection algorithm.Table1.Summary of bench-mark data sets.Title Features Instances Classes Lung-cancer57323 Promoters591062 Splice6231903 USCensus906893383 CoIL20008658222 Chemical1519363 Musk216965982 Arrhythmia28045216 Isolet618156026 Multi-features650200010The experiments are conducted using Weka’s imple-mentation of all these algorithms and FCBF is also implemented in Weka environment(Witten&Frank, 2000).All together10data sets are selected from the UCI Machine Learning Repository(Blake&Merz, 1998)and UCI KDD Archive(Bay,1999).A summary of data sets is presented in Table1.For each data set,we run all four feature selection algorithms,FCBF,ReliefF,CorrSF,ConsSF,respec-tively,and record the running time and the number of selected features for each algorithm.We then ap-ply C4.5and NBC on the original data set as well as each newly obtained data set containing only the se-lected features from each algorithm and record overall accuracy by10-fold cross-validation.5.2.Results and DiscussionsTable2records the running time and the number of selected features for each feature selection algorithm. For ReliefF,the parameter k is set to5(neighbors)and m is set to30(instances)throughout the experiments.From Table2,we can observe that for each algorithm the running times over different data sets are consis-tent with our previous time complexity analysis.From the averaged values in the last row of Table2,it is clear that FCBF runs significantly faster(in degrees)than the other three algorithms,which verifies FCBF’s su-perior computational efficiency.What is interesting is that ReliefF is unexpectedly slow even though its time complexity becomes O(MN)with afixed sample size m.The reason lies on that searching for nearest neighbors involves distance calculation which is more time consuming than the calculation of symmetrical uncertainty value.From Table2,it is also clear that FCBF achieves the highest level of dimensionality reduction by selecting the least number of features(with only one exception in USCensus90),which is consistent with our theoret-ical analysis about FCBF’s ability to identify redun-dant features.Tables3and4show the learning accuracy of C4.5and NBC respectively on different feature sets.From the averaged accuracy over all data sets,we observe that, in general,(1)FCBF improves the accuracy of both C4.5and NBC;and(2)of the other three algorithms, only CorrSF can enhance the accuracy of C4.5to the same level as FCBF does.From individual accuracy values,we also observe that for most of the data sets, FCBF can maintain or even increase the accuracy. The above experimental results suggest that FCBF is practical for feature selection for classification of high dimensional data.It can efficiently achieve high degree of dimensionality reduction and enhance classification accuracy with predominant features.6.ConclusionsIn this paper,we propose a novel concept of predomi-nant correlation,introduce an efficient way of analyz-ing feature redundancy,and design a fast correlation-basedfilter approach.A new feature selection algo-rithm FCBF is implemented and evaluated through extensive experiments comparing with related feature selection algorithms.The feature selection results are further verified by applying two different classification algorithms to data with and without feature selec-tion.Our approach demonstrates its efficiency and effectiveness in dealing with high dimensional data for classification.Our further work will extend FCBF to work on data with higher dimensionality(thousands of features).We will study in more detail redun-dant features and their role in classification,and com-bine FCBF with feature discretization algorithms to smoothly handle data of different feature types.。

The Dvorak keyboard layout places commonly used letters and punctuation in easily accessible positions, reducing finger movement distance and improving typing speed.
Accessibility
Input methods provide an accessible way for users to input characters and words, specifically for those who have diversity using traditional input methods, all as keyboards or mice
Application scenario
Compared to QWERTY keyboards, the learning curve of Dvorak keyboard layout is steeper, requiring more time and effort to master.
Learning difficulty
Input methods are commonly associated with specific languages, allowing users to input characters and words from their native languages
Definition of Input Method
Enhanced productivity
By reducing the time and effort required for input characters and words, input methods improve user productivity in various tasks, such as writing documents, emails, and messages