Transcription
Data MiningDimensionality reductionHamid BeigySharif University of TechnologyFall 1394Hamid Beigy (Sharif University of Technology)Data MiningFall 13941 / 40
Outline1Introduction2Feature selection methods3Feature extraction methodsPrincipal component analysisKernel principal component analysisFactor analysisLinear discriminant analysisHamid Beigy (Sharif University of Technology)Data MiningFall 13942 / 40
Table of contents1Introduction2Feature selection methods3Feature extraction methodsPrincipal component analysisKernel principal component analysisFactor analysisLinear discriminant analysisHamid Beigy (Sharif University of Technology)Data MiningFall 13943 / 40
IntroductionThe complexity of any classifier or regressors depends on the number of input variables orfeatures. These complexities includeTime complexity: In most learning algorithms, the time complexity depends on thenumber of input dimensions(D) as well as on the size of training set (N). Decreasing Ddecreases the time complexity of algorithm for both training and testing phases.Space complexity: Decreasing D also decreases the memory amount needed for trainingand testing phases.Samples complexity: Usually the number of training examples (N) is a function of lengthof feature vectors (D). Hence, decreasing the number of features also decreases thenumber of training examples.Usually the number of training pattern must be 10 to 20 times of the number of features.Hamid Beigy (Sharif University of Technology)Data MiningFall 13943 / 40
IntroductionThere are several reasons why we are interested in reducing dimensionality as a separatepreprocessing step.Decreasing the time complexity of classifiers or regressors.Decreasing the cost of extracting/producing unnecessary features.Simpler models are more robust on small data sets. Simpler models have less varianceand thus are less depending on noise and outliers.Description of classifier or regressors is simpler / shorter.Visualization of data is simpler.Hamid Beigy (Sharif University of Technology)Data MiningFall 13944 / 40
Peaking phenomenonIn practice, for a finite N, by increasing the number of features we obtain an initialimprovement in performance, but after a critical value further increase of the number offeatures results in an increase of the probability of error. This phenomenon is also knownas the peaking phenomenon.If the number of samples increases (N2 N1 ), the peaking phenomenon occures forlarger number of features (l2 l1 ).Hamid Beigy (Sharif University of Technology)Data MiningFall 13945 / 40
Dimensionality reduction methodsThere are two main methods for reducing the dimensionality of inputsFeature selection: These methods select d (d D) dimensions out of D dimensions andD d other dimensions are discarded.Feature extraction: Find a new set of d (d D) dimensions that are combinations of theoriginal dimensions.Hamid Beigy (Sharif University of Technology)Data MiningFall 13946 / 40
Table of contents1Introduction2Feature selection methods3Feature extraction methodsPrincipal component analysisKernel principal component analysisFactor analysisLinear discriminant analysisHamid Beigy (Sharif University of Technology)Data MiningFall 13947 / 40
Feature selection methodsFeature selection methods select d (d D) dimensions out of D dimensions and D dother dimensions are discarded.Reasons for performing feature selectionIncreasing the predictive accuracy of classifiers or regressors.Removing irrelevant features.Enhancing learning efficiency (reducing computational and storage requirements).Reducing the cost of future data collection (making measurements on only those variablesrelevant for discrimination/prediction).Reducing complexity of the resulting classifiers/regressors description (providing an improvedunderstanding of the data and the model).Feature selection is not necessarily required as a pre-processing step forclassification/regression algorithms to perform well.Several algorithms employ regularization techniques to handle over-fitting or averagingsuch as ensemble methods.Hamid Beigy (Sharif University of Technology)Data MiningFall 13947 / 40
Feature selection methodsFeature selection methods can be categorized into three categories.Filter methods: These methods use the statistical properties of features to filter out poorlyinformative features.Wrapper methods: These methods evaluate the feature subset within classifier/regressoralgorithms. These methods are classifier/regressors dependent and have better performancethan filter methods.Embedded methods:These methods use the search for the optimal subset intoclassifier/regression design. These methods are classifier/regressors dependent.Two key steps in feature selection process.Evaluation: An evaluation measure is a means of assessing a candidate feature subset.Subset generation: A subset generation method is a means of generating a subset forevaluation.Hamid Beigy (Sharif University of Technology)Data MiningFall 13948 / 40
Feature selection methods (Evaluation measures)Large number of features are not informative- either irrelevant or redundant.Irrelevant features are those features that don’t contribute to a classification or regressionrule.Redundant features are those features that are strongly correlated.In order to choose a good feature set, we require a means of a measure to contribute tothe separation of classes, either individually or in the context of already selected features.We need to measure relevancy and redundancy.There are two types of measuresMeasures that relay on the general properties of the data. These assess the relevancy ofindividual features and are used to eliminate feature redundancy. All these measures areindependent of the final classifier. These measures are inexpensive to implement but may notwell detect the redundancy.Measures that use a classification rule as a part of their evaluation. In this approach, aclassifier is designed using the reduced feature set and a measure of classifier performance isemployed to assess the selected features. A widely used measure is the error rate.Hamid Beigy (Sharif University of Technology)Data MiningFall 13949 / 40
Feature selection methods (Evaluation measures)The following measures relay on the general properties of the data.Feature ranking: Features are ranked by a metric and those that fail to achieve a prescribedscore are eliminated.Examples of these metrics are: Pearson correlation, mutual information, and information gain.Interclass distance: A measure of distance between classes is defined based on distancesbetween members of each class.Example of these metrics is: Euclidean distance.Probabilistic distance: This is the computation of a probabilistic distance betweenclass-conditional probability density functions, i.e. the distance between p(x C1 ) and p(x C2 )(two-classes).Example of these metrics is: Chhernoff dissimilarity measure.Probabilistic dependency: These measures are multi-class criteria that measure the distancebetween class-conditional probability density functions and the mixture probability densityfunction for the data irrespective of the class, i.e. the distance between p(x Ci ) and p(x).Example of these metrics is: Joshi dissimilarity measure.Hamid Beigy (Sharif University of Technology)Data MiningFall 139410 / 40
Feature selection methods (Search algorithms)Complete search: These methods guarantee to find the optimal subset of featuresaccording to some specified evaluation criteria.For example exhaustive search and branch and bound methods are complete.Sequential search: In these methods, features are added or removed sequentially. Thesemethods are not optimal, but are simple to implement and fast to produce results.Best individual N: The simplest method is to assign a score to each feature and thenselect N top ranks features.Sequential forward selection: It is a bottom-up search procedure that adds new featuresto a feature set one at a time until the final feature set is reached.Generalized sequential forward selection: In this approach, at each time r 1, featuresare added instead of a single feature.Sequential backward elimination: It is a top-down procedure that deletes a single featureat a time until the final feature set is reached.Generalized sequential backward elimination : In this approach, at each time r 1features are deleted instead of a single feature.Hamid Beigy (Sharif University of Technology)Data MiningFall 139411 / 40
Table of contents1Introduction2Feature selection methods3Feature extraction methodsPrincipal component analysisKernel principal component analysisFactor analysisLinear discriminant analysisHamid Beigy (Sharif University of Technology)Data MiningFall 139412 / 40
Feature extractionIn feature extraction, we are interested to find a new set of k (k D) dimensions thatare combinations of the original D dimensions.Feature extraction methods may be supervised or unsupervised.Examples of feature extraction methodsPrincipal component analysis (PCA)Factor analysis (FA)sMulti-dimensional scaling (MDS)ISOMapLocally linear embeddingLinear discriminant analysis (LDA)Hamid Beigy (Sharif University of Technology)Data MiningFall 139412 / 40
Principal component analysisPCA project D dimensional input vectors to k dimensional input vectors via a linearmapping with minimum loss of information. Dimensions are combinations of the originalD dimensions.The problem is to find a matrix W such that the following mapping results in theminimum loss of information.Z WTXPCA is unsupervised and tries to maximize the variance.The principle component is w1 such that the sample after projection onto w1 is mostspread out so that the difference between the sample points becomes most apparent.For uniqueness of the solution, we require kw1 k 1,Let Σ Cov (X ) and consider the principle component w1 , we havez1 w1T xVar (z1 ) E [(w1T x w1T µ)2 ] E [(w1T x w1T µ)(w1T x w1T µ)] E [w1T (x µ)(x µ)T w1 ] w1T E [(x µ)(x µ)T ]w1 w1T Σw1Hamid Beigy (Sharif University of Technology)Data MiningFall 139413 / 40
Principal component analysis (cont.)The mapping problem becomesw1 argmax w T Σwwsubject to w1T w1 1.Writing this as Lagrange problem, we havemaximize w1T Σw1 α(w1T w1 1)w1Taking derivative with respect to w1 and setting it equal to 0, we obtain2Σw1 2αw1 Σw1 αw1Hence w1 is eigenvector of Σ and α is the corresponding eigenvalue.Since we want to maximize Var (z1 ), we haveVar (z1 ) w1T Σw1 αw1T w1 αHence, we choose the eigenvector with the largest eigenvalue, i.e. λ1 α.Hamid Beigy (Sharif University of Technology)Data MiningFall 139414 / 40
Principal component analysis (cont.)The second principal component, w2 , should alsomaximize variancebe unit lengthorthogonal to w1 (z1 and z2 must be uncorrelated)The mapping problem for the second principal component becomesw2 argmax w T Σwwsubject to w2T w2 1 and w2T w1 0.Writing this as Lagrange problem, we havemaximize w2T Σw2 α(w2T w2 1) β(w2T w1 0)w2Taking derivative with respect to w2 and setting it equal to 0, we obtain2Σw2 2αw2 βw1 0Pre-multiply by w1T , we obtain2w1T Σw2 2αw1T w2 βw1T w1 0Note that w1T w2 0 and w1T Σw2 (w2T Σw1 )T w2T Σw1 is a scaler.Hamid Beigy (Sharif University of Technology)Data MiningFall 139415 / 40
Principal component analysis (cont.)Since Σw1 λ1 w1 , therefore we havew1T Σw2 w2T Σw1 λ1 w2T w1 0Then β 0 and the problem reduces toΣw2 αw2This implies that w2 should be the eigenvector of Σ with the second largest eigenvalueλ2 α.Similarly, you can show that the other dimensions are given by the eigenvectors withdecreasing eigenvalues.Since Σ is symmetric, for two different eigenvalues, their corresponding eigenvectors areorthogonal. (Show it)If Σ is positive definite (x T Σx 0 for all non-null vector x), then all its eigenvalues arepositive.If Σ is singular, its rank is k (k D) and λi 0 for i k 1, . . . , D.Hamid Beigy (Sharif University of Technology)Data MiningFall 139416 / 40
Principal component analysis (cont.)DefineZ W T (X m)Then k columns of W are the k leading eigenvectors of S (the estimator of Σ).m is the sample mean of X .Subtracting m from X before projection centers the data on the origin.How to normalize variances?Hamid Beigy (Sharif University of Technology)Data MiningFall 139417 / 40
Principal component analysis (cont.)How to select k?QIf all eigenvalues are positive and S Di 1 λi is small, then some eigenvalues have littlecontribution to the variance and may be discarded.Scree graph is the plot of variance as a function of the number of eigenvectors.Hamid Beigy (Sharif University of Technology)Data MiningFall 139418 / 40
Principal component analysis (cont.)How to select k?We select the leading k components that explain more than for example 95% of thevariance.The proportion of variance (POV) isPkλiPOV Pi 1Di 1 λiBy visually analyzing it, we can choose k.Hamid Beigy (Sharif University of Technology)Data MiningFall 139419 / 40
Principal component analysis (cont.)How to select k?Another possibility is to ignore the eigenvectors whose corresponding eigenvalues are lessthan the average input variance (why?).In the pre-processing phase, it is better to pre-process data such that each dimension hasmean 0 and unit variance(why and when?).Question: Can we use the correlation matrix instead of covariance matrix? Drive solutionfor PCA.Hamid Beigy (Sharif University of Technology)Data MiningFall 139420 / 40
Principal component analysis (cont.)PCA is sensitive to outliers. A few points distant from the center have large effect on thevariances and thus eigenvectors.Question: How can use the robust estimation methods for calculating parameters in thepresence of outliers?A simple method is discarding the isolated data points that are far away.Question: When D is large, calculating, sorting, and processing of S may be tedious. Is itpossible to calculate eigenvectors and eigenvalues directly from data without explicitlycalculating the covariance matrix?Hamid Beigy (Sharif University of Technology)Data MiningFall 139421 / 40
Principal component analysis (reconstruction error)In PCA, input vector x is projected to the z space asz W T (x µ)When W is an orthogonal matrix (W T W I ), it can be back-projected to the originalspace asx̂ Wz µx̂ is the reconstruction of x from its representation in the z space.Question: Show that PCA minimizes the following reconstruction error.Xkx̂i xi k2iThe reconstruction error depends on how many of the leading components are taken intoaccount.Hamid Beigy (Sharif University of Technology)Data MiningFall 139422 / 40
Principal component analysis (cont.)PCA is unsupervised and does not use label/output information.Karhunen-loeve expansion allows using label/output information.Common principle components assumes that the principal components are the same foreach class whereas the variance of these components differ for different classes.Flexible discriminant analysis, which does a linear projection to a lower-dimensional spacein which all features are uncorrelated. This method use minimum distance classifier.Hamid Beigy (Sharif University of Technology)Data MiningFall 139423 / 40
Kernel principal component analysisPCA can be extended to find nonlinear directions in the data using kernel methods.Kernel PCA finds the directions of most variance in the feature space instead of the inputspace.Linear principal components in the feature space correspond to nonlinear directions in theinput space.Using kernel trick, all operations can be carried out in terms of the kernel function ininput space without having to transform the data into feature space.Let φ correspond to a mapping from the input space to the feature space.Each point in feature space is given as the image of φ(x) of the point x in the input space.In feature space, we can find the first kernek principal component W1 (W1T W1 1) bysolvingΣφ W1 λ 1 W1Covariance matrix Σφ in feature space is equal toΣφ 1 XNφ(xi )φ(xi )TNi 1We assume that the points are centered.Hamid Beigy (Sharif University of Technology)Data MiningFall 139424 / 40
Kernel principal component analysis (cont.)Plugging Σφ into Σφ W1 λ1 W1 , we obtainN1 Xφ(xi )φ(xi )TN1N!W1 λ 1 W1i 1NX φ(xi ) φ(xi )T W1 λ 1 W1i 1 N Xφ(xi )T W1i 1Nλ1NXφ(xi ) W1ci φ(xi ) W1i 1ci φ(xi )T W1Nλ1is a scalar valueHamid Beigy (Sharif University of Technology)Data MiningFall 139425 / 40
Kernel principal component analysis (cont.)Now substitutePNi 1 ci φ(xi ) W1 in Σφ W1 λ1 W1 , we obtainN1 Xφ(xi )φ(xi )TN!i 1NX!ci φ(xi ) λ1i 1NXci φ(xi )i 1NXN N1 XXcj φ(xi )φ(xi )T φ(xj ) λ1ci φ(xi )Ni 1 j 1i 1 NNNXXX φ(xi )cj φ(xi )T φ(xj ) Nλ1ci φ(xi )i 1j 1i 1Replacing φ(xi )T φ(xj ) by K (xi , xj )NXi 1Hamid Beigy (Sharif University of Technology) φ(xi )NX cj K (xi , xj ) Nλ1NXci φ(xi )i 1j 1Data MiningFall 139426 / 40
Kernel principal component analysis (cont.)Multiplying with φ(xk )T , we obtainNX φ(xk )T φ(xi )i 1NX cj K (xi , xj ) Nλ1j 1NX K (xk , xi )i 1NXNXci φ(xk )T φ(xi )i 1 cj K (xi , xj ) Nλ1j 1NXci K (xk , xj )i 1By some algebraic simplificatin, we obtain (do it)K 2 C Nλ1 KCMultiplying by K 1 , we obtainKC Nλ1 CKC η1 CWeight vector C is the eigenvector corresponding to the largest eigenvalue η1 of thekernel matrix K .Hamid Beigy (Sharif University of Technology)Data MiningFall 139427 / 40
Kernel principal component analysis (cont.)ReplacingPNi 1 ci φ(xi ) W1 in constraint W1T W1 1, we obtainN XNXcj cj φ(xi )T φ(xj ) 1i 1 j 1C T KC 1Using KC η1 C , we obtainC T (η1 C ) 1η1 C T C 11 C 2 η1Since C is an eigenvector of K , it will have unit norm.qTo ensure that W1 is a unit vector, multiply C by η11Hamid Beigy (Sharif University of Technology)Data MiningFall 139428 / 40
Kernel principal component analysis (cont.)In general, we do not ma input space to the feature space via φ, hence we cannotcompute W1 usingNXci φ(xi ) W1i 1We can project any point φ(x) on to principal direction W1W1T φ(x) NXTci φ(xi ) φ(x) i 1NXci K (xi , x)i 1When x xi is one of the input points, we haveai W1T φ(xi ) KiT Cwhere Ki is the column vector corresponding to the I th row of K and ai is the vector inthe reduced dimension.This shows that all computation are carried out using only kernel operations.Hamid Beigy (Sharif University of Technology)Data MiningFall 139429 / 40
Factor analysisIn PCA, from the original dimensions xi (for i 1, . . . , D), we form a new set of variablesz that are linear combinations of xiZ W T (X µ)In factor analysis (FA), we assume that there is a set of unobservable, latent factors zj(for j 1, . . . , k), which when acting in combination generate x.Thus the direction is opposite that of PCA.The goal is to characterize the dependency among the observed variables by means of asmaller number of factors.Suppose there is a group of variables that have high correlation among themselves andlow correlation with all the other variables. Then there may be a single underlying factorthat gave rise to these variables.FA, like PCA, is a one-group procedure and is unsupervised. The aim is to model the datain a smaller dimensional space without loss of information.In FA, this is measured as the correlation between variables.Hamid Beigy (Sharif University of Technology)Data MiningFall 139430 / 40
Factor analysis (cont.)Hamid Beigy (Sharif University of Technology)Data MiningFall 139431 / 40
Factor analysis (cont.)As in PCA, we have a sample x drawn from some unknown probability density withE [x] µ and Cov (x) Σ.We assume that the factors are unit normals, E [zj ] 0, Var (zj ) 1, and areuncorrelated,Cov (zi , zj ) 0, i 6 j.To explain what is not explained by the factors, there is an added source for each inputwhich we denote by i .It is assumed to be zero-mean, E [ i ] 0, and have some unknown variance, Var ( i ) ψi.These specific sources are uncorrelated among themselves, Cov ( i , i ) 0, i 6 j, and arealso uncorrelated with the factors, Cov ( i , zj ) 0, i, j.FA assumes that each input dimension, xi can be written as a weighted sum of the k Dfactors, zj plus the residual term.xi µi vi1 z1 vi2 z2 . . . vik zk iThis can be written in vector-matrix form asx µ VZ iV is the D k matrix of weights, called factor loadings.Hamid Beigy (Sharif University of Technology)Data MiningFall 139432 / 40
Factor analysis (cont.)We assume that µ 0 and we can always add µ after projection.Given that Var (zj ) 1 and Var ( i ) ψi and22Var (xi ) vi1 vi2 . . . vik2 iIn vector-matrix form, we haveΣ Var (X ) VV T ΨThere are two uses of factor analysis:It can be used for knowledge extraction when we find the loadings and try to express thevariables using fewer factors.It can also be used for dimensionality reduction when k D.Hamid Beigy (Sharif University of Technology)Data MiningFall 139433 / 40
Factor analysis (cont.)For dimensionality reduction, we need to find the factor, zj , from xi .We want to find the loadings wji such thatzj DXwji xi ii 1In vector form, for input x, this can be written asz WTx For N input, the problem is reduced to linear regression and its solution isW (X T X ) 1 X T ZWe do not know Z ; We multiply and divide both sides by N 1 and obtain (drive it!)T 1W (N 1)(X X )XTZ N 1 XTXN 1 1XTZ S 1 VN 1Z XW XS 1 VHamid Beigy (Sharif University of Technology)Data MiningFall 139434 / 40
Linear discriminant analysisLinear discriminant analysis (LDA) is a supervised method for dimensionality reduction forclassification problems.Consider first the case of two classes, and suppose we take the D dimensional inputvector x and project it down to one dimension usingz WTxIf we place a threshold on z and classify z w0 as class C1 , and otherwise class C2 , thenwe obtain our standard linear classifier.In general, the projection onto one dimension leads to a considerable loss of information,and classes that are well separated in the original D dimensional space may becomestrongly overlapping in one dimension.However, by adjusting the components of the weight vector W , we can select a projectionthat maximizes the class separation.Consider a two-class problem in which there are N1 points of class C1 and N2 points ofclass C2 , so that the mean vectors of the two classes are given bymj 1 XxiNji CjHamid Beigy (Sharif University of Technology)Data MiningFall 139435 / 40
Linear discriminant analysis (cont.)The simplest measure of the separation of the classes, when projected onto W , is theseparation of the projected class means.This suggests that we might choose W so as to maximizem2 m1 W T (m2 m1 )wherem j W T mjThis expression can be made arbitrarily large simply by increasing the magnitude of W .PTo solve this problem, we could constrain W to have unit length, so that i wi2 1.Using a Lagrange multiplier to perform the constrained maximization, we then find thatW (m2 m1 )Hamid Beigy (Sharif University of Technology)Data MiningFall 139436 / 40
Linear discriminant analysis (cont.)This approach has a problem: The following figure shows two classes that are wellseparated in the original two dimensional space but that have considerable overlap whenprojected onto the line joining their means.This difficulty arises from the strongly non-diagonal covariances of the class distributions.The idea proposed by Fisher is to maximize a function that will give a large separationbetween the projected class means while also giving a small variance within each class,thereby minimizing the class overlap.Hamid Beigy (Sharif University of Technology)Data MiningFall 139437 / 40
Linear discriminant analysis (cont.)The idea proposed by Fisher is to maximize a function that will give a large separationbetween the projected class means while also giving a small variance within each class,thereby minimizing the class overlap.The projection z W T x transforms the set of labeled data points in x into a labeled setin the one-dimensional space z.The within-class variance of the transformed data from class Cj equalsXsj2 (zi mj )2i Cjwherezi w T xi .We can define the total within-class variance for the whole data set to be s12 s22 . .The Fisher criterion is defined to be the ratio of the between-class variance to thewithin-class variance and is given byJ(W ) Hamid Beigy (Sharif University of Technology)(m2 m1 )2s12 s22Data MiningFall 139438 / 40
Linear discriminant analysis (cont.)Between-class covariance matrix equals toSB (m2 m1 )(m2 m1 )TTotal within-class covariance matrix equals toXXSW (xi m1 ) (xi m1 )T (xi m2 ) (xi m2 )Ti C1i C2J(W ) can be written asJ(w ) W T SB WW T SW WTo maximize J(W ), we differentiate with respect to W and we obtain W T SB W SW W W T SW W SB WSB W is always in the direction of (m2 m1 ) (Show it!).We can drop the scalar factors W T SB W and W T SW W (why?).Multiplying both sides of S 1W we then obtain (Show it!)W S 1W (m2 m1 )Hamid Beigy (Sharif University of Technology)Data MiningFall 139439 / 40
Linear discriminant analysis (cont.)The result W S 1W (m2 m1 ) is known as Fisher’s linear discriminant, although strictlyit is not a discriminant but rather a specific choice of direction for projection of the datadown to one dimension.The projected data can subsequently be used to construct a discriminant function.The above idea can be extended to multiple classes (Read section 4.1.6 of Bishop).How the Fisher’s linear discriminant can be used for dimensionality reduction? (Show it!)Hamid Beigy (Sharif University of Technology)Data MiningFall 139440 / 40
Wrapper methods:These methods evaluate the feature subset within classi er/regressor algorithms. These methods are classi er/regressors dependent and have better performance than lter methods. Embedded methods:These methods use the search for the optimal subset into classi er/regression design. These methods are classi er/regressors dependent.
