{"id":597,"date":"2019-01-08T10:19:12","date_gmt":"2019-01-08T10:19:12","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=597"},"modified":"2019-01-08T10:51:46","modified_gmt":"2019-01-08T10:51:46","slug":"dimensionality-reduction-ii","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/dimensionality-reduction-ii\/","title":{"rendered":"Dimensionality Reduction – II"},"content":{"raw":"
\r\n\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To explain the Fisher Linear Discriminant approach\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Singular Value Decomposition\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To outline the computation of Singular Value Decomposition\r\n\r\n \r\n\r\n28.1 Introduction<\/strong>\r\n\r\n \r\n

The main idea of Fisher linear discriminant approach is finding the projection to a line such that samples from different classes projected on the line are well separated (Figure 28.1).<\/p>\r\n \r\n\r\n\"\"\r\n

Figure 28.1 Bad and Good Projections<\/strong><\/p>\r\n \r\n

28.2 The Basis of Fisher Discriminant<\/strong><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Suppose we have 2 classes and d-dimensional samples X1<\/sub>\u00a0,X2<\/sub>\u00a0,...., Xn\u00a0<\/sub>where n1 samples come from the first class and n2 samples come from the second class. Consider projection on a line, and let the line direction be given by unit vector V. Scalar Vt<\/sup>\u00a0Xi\u00a0<\/sub>is the distance of projection of xi from the origin. Thus is the projection of into a one dimensional subspace (Figure 28.2).<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 28.2<\/strong><\/p>\r\n\r\n<\/div>\r\n

<\/div>\r\n
\r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n<\/div>\r\n \r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n

Thus scatter is just sample variance multiplied by n. In other words, scatter measures the same concept as variance, the spread of data around the mean, only that scatter is just on a different scale than variance.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\n28.3 Fisher Linear Discriminant<\/strong>\r\n

\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n

We need to normalize by both scatter of class 1 and scatter of class 2. Thus Fisher linear discriminant needs to project on line in the direction v which maximizes J(v) (Figure 28.5). Here J(v) is defined such that we want the projected means to be far from each other and the scatter of each class to be as small as possible that is we want the samples of the respective classes to cluster around the projected means. If we find v which makes J(v) large, we are guaranteed that the classes are well separated (Figure 28.6).<\/p>\r\n\"\"\r\n

Figure 28.5 Definition of J(V)<\/strong><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 28.6 Well Separated Projected Samples<\/strong><\/p>\r\n \r\n

All we need to do now is to express J explicitly as a function of v and maximize it. This is fairly straightforward but needs application of linear algebra and calculus. We define the separate class scatter matrices S1 and S2 for classes 1 and 2. These measure the scatter of original samples xi (before projection) as follows:<\/p>\r\n\"\"\r\n\r\n \r\n\r\nNow let us consider the samples belonging to two classes as given below:\r\n\r\n \r\n\r\n\u2013\u00a0 Class 1 has 5 samples c1=[(1,2),(2,3),(3,3),(4,5),(5,5)]\r\n\r\n \r\n\r\n\u2013 Class 2 has 6 samples c2=[(1,0),(2,1),(3,1),(5,3),(6,5)] Now let us arrange data in 2 separate matrices as follows:\r\n\r\n\"\"\r\n

It is to be noted that PCA performs very poorly on this data because the direction of largest variance is not helpful for classification (Figure 28.7).<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 28.7 PCA based Dimensionality Reduction<\/strong><\/p>\r\n \r\n\r\nNow let us first compute the mean for each class. M1= mean(c1)=[3 3.6] M2= mean (c2) = [3.3 2]\r\n\r\n \r\n\r\nNow based on these means let us compute the scatter matrices S1 and S2 for each class as follows:\r\n\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Notice, that as long as the line has the right direction, its exact position does not matter.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n28.4 Singular Value Decomposition<\/strong>\r\n\r\n \r\n

Now let us discuss the final method of dimensionality reduction namely Singular Value Decomposition (SVD). SVD can be viewed as a method for transforming correlated variables into a set of uncorrelated ones that better expose the various relationships among the original data items. It is a method for identifying and ordering the dimensions along which data points exhibit the most variation. With SVD, it\u2019s possible to find the best approximation of the original data points using fewer dimensions. Hence, SVD is used for data reduction.<\/p>\r\n \r\n

Singular Value Decomposition factorizes a real or complex matrix. For an M<\/em> \u00b4 N<\/em> matrix A<\/strong> of rank r<\/em> there exists a factorization (Singular Value Decomposition = SVD<\/strong>) as follows:<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n\r\n \r\n

Here the columns of U<\/em><\/strong> are orthogonal eigen vectors of AA<\/em><\/strong>T<\/em><\/strong><\/sup>, the columns of V<\/em><\/strong> are orthogonal eigen vectors of A<\/em><\/strong>T<\/em><\/strong><\/sup>A<\/em><\/strong> and Eigen values l1 \u2026 lr of AA<\/em><\/strong>T<\/em><\/strong><\/sup> are the eigen values of A<\/em><\/strong>T<\/em><\/strong>A<\/em><\/strong>. An illustration of SVD dimensions and sparseness is as given in Figure 28.9.<\/p>\r\n\"\"\r\n

Figure 28.9 SVD Illustration <\/strong><\/p>\r\n \r\n

The corresponding singular values are given below.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n

(c)<\/p>\r\n\"\"\"\"\r\n\r\n \r\n\r\n<\/div>\r\n

<\/div>\r\n\"\"\"\"\r\n\r\n\"\"\r\n\r\nSummary<\/strong>\r\n
    \r\n \t
  • Explained the Fisher Linear Discriminant approach<\/li>\r\n \t
  • Outlined the concept of Singular Value Decomposition<\/li>\r\n \t
  • Discussed the computation of Singular Value Decomposition.<\/li>\r\n<\/ul>","rendered":"
    \n

     <\/p>\n

    Learning Objectives:<\/strong><\/p>\n

     <\/p>\n

    The learning objectives of this module are as follows:<\/p>\n

     <\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To explain the Fisher Linear Discriminant approach<\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the concept of Singular Value Decomposition<\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To outline the computation of Singular Value Decomposition<\/p>\n

     <\/p>\n

    28.1 Introduction<\/strong><\/p>\n

     <\/p>\n

    The main idea of Fisher linear discriminant approach is finding the projection to a line such that samples from different classes projected on the line are well separated (Figure 28.1).<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    Figure 28.1 Bad and Good Projections<\/strong><\/p>\n

     <\/p>\n

    28.2 The Basis of Fisher Discriminant<\/strong><\/p>\n<\/div>\n

    \n

     <\/p>\n

    Suppose we have 2 classes and d-dimensional samples X1<\/sub>\u00a0,X2<\/sub>\u00a0,…., Xn\u00a0<\/sub>where n1 samples come from the first class and n2 samples come from the second class. Consider projection on a line, and let the line direction be given by unit vector V. Scalar Vt<\/sup>\u00a0Xi\u00a0<\/sub>is the distance of projection of xi from the origin. Thus is the projection of into a one dimensional subspace (Figure 28.2).<\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    Figure 28.2<\/strong><\/p>\n<\/div>\n

    <\/div>\n
    \n

    \"\"<\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n<\/div>\n

     <\/p>\n

    \n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    Thus scatter is just sample variance multiplied by n. In other words, scatter measures the same concept as variance, the spread of data around the mean, only that scatter is just on a different scale than variance.<\/p>\n<\/div>\n

     <\/p>\n

    28.3 Fisher Linear Discriminant<\/strong><\/p>\n

    \n

     <\/p>\n

    \"\"<\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

     <\/p>\n

    We need to normalize by both scatter of class 1 and scatter of class 2. Thus Fisher linear discriminant needs to project on line in the direction v which maximizes J(v) (Figure 28.5). Here J(v) is defined such that we want the projected means to be far from each other and the scatter of each class to be as small as possible that is we want the samples of the respective classes to cluster around the projected means. If we find v which makes J(v) large, we are guaranteed that the classes are well separated (Figure 28.6).<\/p>\n

    \"\"<\/p>\n

    Figure 28.5 Definition of J(V)<\/strong><\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    Figure 28.6 Well Separated Projected Samples<\/strong><\/p>\n

     <\/p>\n

    All we need to do now is to express J explicitly as a function of v and maximize it. This is fairly straightforward but needs application of linear algebra and calculus. We define the separate class scatter matrices S1 and S2 for classes 1 and 2. These measure the scatter of original samples xi (before projection) as follows:<\/p>\n

    \"\"<\/p>\n

     <\/p>\n

    Now let us consider the samples belonging to two classes as given below:<\/p>\n

     <\/p>\n

    \u2013\u00a0 Class 1 has 5 samples c1=[(1,2),(2,3),(3,3),(4,5),(5,5)]<\/p>\n

     <\/p>\n

    \u2013 Class 2 has 6 samples c2=[(1,0),(2,1),(3,1),(5,3),(6,5)] Now let us arrange data in 2 separate matrices as follows:<\/p>\n

    \"\"<\/p>\n

    It is to be noted that PCA performs very poorly on this data because the direction of largest variance is not helpful for classification (Figure 28.7).<\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

    Figure 28.7 PCA based Dimensionality Reduction<\/strong><\/p>\n

     <\/p>\n

    Now let us first compute the mean for each class. M1= mean(c1)=[3 3.6] M2= mean (c2) = [3.3 2]<\/p>\n

     <\/p>\n

    Now based on these means let us compute the scatter matrices S1 and S2 for each class as follows:<\/p>\n

     <\/p>\n

    \"\"<\/p>\n<\/div>\n

    \n

     <\/p>\n

    Notice, that as long as the line has the right direction, its exact position does not matter.<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

     <\/p>\n

    28.4 Singular Value Decomposition<\/strong><\/p>\n

     <\/p>\n

    Now let us discuss the final method of dimensionality reduction namely Singular Value Decomposition (SVD). SVD can be viewed as a method for transforming correlated variables into a set of uncorrelated ones that better expose the various relationships among the original data items. It is a method for identifying and ordering the dimensions along which data points exhibit the most variation. With SVD, it\u2019s possible to find the best approximation of the original data points using fewer dimensions. Hence, SVD is used for data reduction.<\/p>\n

     <\/p>\n

    Singular Value Decomposition factorizes a real or complex matrix. For an M<\/em> \u00b4 N<\/em> matrix A<\/strong> of rank r<\/em> there exists a factorization (Singular Value Decomposition = SVD<\/strong>) as follows:<\/p>\n<\/div>\n

    \"\"<\/p>\n

    \n

     <\/p>\n

    Here the columns of U<\/em><\/strong> are orthogonal eigen vectors of AA<\/em><\/strong>T<\/em><\/strong><\/sup>, the columns of V<\/em><\/strong> are orthogonal eigen vectors of A<\/em><\/strong>T<\/em><\/strong><\/sup>A<\/em><\/strong> and Eigen values l1 \u2026 lr of AA<\/em><\/strong>T<\/em><\/strong><\/sup> are the eigen values of A<\/em><\/strong>T<\/em><\/strong>A<\/em><\/strong>. An illustration of SVD dimensions and sparseness is as given in Figure 28.9.<\/p>\n

    \"\"<\/p>\n

    Figure 28.9 SVD Illustration <\/strong><\/p>\n

     <\/p>\n

    The corresponding singular values are given below.<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    (c)<\/p>\n

    \"\"\"\"<\/p>\n

     <\/p>\n<\/div>\n

    <\/div>\n

    \"\"\"\"<\/p>\n

    \"\"<\/p>\n

    Summary<\/strong><\/p>\n

      \n
    • Explained the Fisher Linear Discriminant approach<\/li>\n
    • Outlined the concept of Singular Value Decomposition<\/li>\n
    • Discussed the computation of Singular Value Decomposition.<\/li>\n<\/ul>\n","protected":false},"author":3,"menu_order":27,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-597","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/597","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/597\/revisions"}],"predecessor-version":[{"id":624,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/597\/revisions\/624"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/597\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/media?parent=597"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapter-type?post=597"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/contributor?post=597"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/license?post=597"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}