{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Tut5 - PCA_dim_Reduction.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SgaFaHY8aSju"
      },
      "source": [
        "#PCA Introduction"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nja4csa73IP5"
      },
      "source": [
        "Principal Component Analysis, or PCA for short, is a method used for dimensionality reduction and the visualization of high dimensional data.\n",
        "\n",
        "It can be thought of as a projection method where data with m-columns (features) is projected into a subspace with m or fewer columns, whilst retaining the essence of the original data.\n",
        "\n",
        "The PCA method can be described and implemented using the tools of linear algebra. It projects the data in a lower dimensional space along the directions of maximum variance that are orthogonal to each other, while trying to preserve as much of the data's variation as possible.\n",
        "\n",
        "![alt text](https://miro.medium.com/max/1204/0*PnqMbZEdnuL9yHuo.png)\n",
        "\n",
        "Calculating PCA involves:\n",
        "* Calculating the covariance matrix.\n",
        "* Calculating the eigenvalues and eigenvector\n",
        "* Forming Proncipal Components\n",
        "* Projection into a new feature space\n",
        "\n",
        "![alt text](https://miro.medium.com/max/1124/0*cgmVlr-0eTeJrudC.png)\n",
        "\n",
        "Calculating the eigen values and eigen vectors\n",
        "\n",
        "* For every eigenvalue, there is a corresponding eigenvector. \n",
        "* We will sort eigenvalue in decreasing order. \n",
        "* The vector V1 corresponds to maximum eigenvalue have maximum variance implying maximum information of the dataset. \n",
        "* Similarly, variance decreases as eigenvalue decreases.\n",
        "\n",
        "λ is an eigen value for a matrix A if it is a solution of the characteristic \n",
        "equation: det(λ*I - A) = 0\n",
        "\n",
        "* Where, I is the identity matrix of the same dimension as A.\n",
        "* Having determined the eigenvalue λ, a corresponding eigen-vector v, can be found by solving: (λ*I-A)v = 0\n",
        "\n",
        "* The eigenvalues λ1,λ2,...,λm are the variances of the corrdinates on each principal component axis. \n",
        "\n",
        "![alt text](https://miro.medium.com/max/960/0*X5QQmLTzK8aTB-40.jpg)\n",
        "\n",
        "Overview:\n",
        "1. First, we need to center our data\n",
        "\n",
        "![alt text](https://miro.medium.com/max/148/1*a8Z8fvL9utK3FgYKWucZqw.png)\n",
        "\n",
        "2. Then we compute covariance matrix *S* for centered data and find its eigenvectors *b* and eigenvalues *λ*.\n",
        "\n",
        "![alt text](https://miro.medium.com/max/227/1*m34jfHslnEaOYXWTZuXmEQ.png)\n",
        "\n",
        "3. Sort eigenvectors by corresponding eigenvalues in descending order.\n",
        "\n",
        "4. Then we form matrix B from first M eigenvectors and perform dimensionality reduction\n",
        "\n",
        "![alt text](https://miro.medium.com/max/385/1*OL25pSQvFoije8pHcaR5EA.png)\n",
        "\n",
        "5. For inverse transformation we need to get back to original space (find projections) and shift data back from the center adding mean values\n",
        "\n",
        "![alt text](https://miro.medium.com/max/235/1*NR8X87duwZsMcSEwIYC5Tg.png)\n",
        "\n",
        "Transforming the data using PCA — removes the collinearity within the data. However, since PCA only removes linear dependence among variables; even after transforming the variables using PCA, they may still be dependent — in a non linear way.\n",
        "\n",
        "PCA Applications:\n",
        "* Data Visualization\n",
        "* Speed-up Machine Learning Algorithms"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zFL3Gb7Q_azt"
      },
      "source": [
        "#Manually Calculate Principal Component Analysis"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VpM4qFYGnS7j"
      },
      "source": [
        "PCA is an operation applied to a dataset, represented by an n x m matrix A that results in a projection of A which we will call B. Let’s walk through the steps of this operation.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CrEW0vt51i8K"
      },
      "source": [
        "from numpy import array\n",
        "from numpy import mean\n",
        "#Function that computes covariance matrix\n",
        "from numpy import cov\n",
        "#Function that computes the Eigen decomposition\n",
        "from numpy.linalg import eig\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "# define a matrix\n",
        "#\n",
        "#     a11, a12\n",
        "#A = (a21, a22)\n",
        "#     a31, a32\n",
        "# 2x3 matrix\n",
        "# 3 vectors with two components\n",
        "A = array([[1, 3, 5], [2, 4, 6]])\n",
        "print('A:')\n",
        "print(A)\n",
        "\n",
        "plt.scatter(A[0,:], A[1,:], s=150)\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ru7zWNUEp4p3"
      },
      "source": [
        "The first step is to calculate the mean values of each column."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jO-ihY-ypsJP"
      },
      "source": [
        "#A mean value for each component\n",
        "M = mean(A, axis=1,keepdims=True)\n",
        "print('Mean of each vector component',M.shape)\n",
        "print(M)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "opAQbADGp7LX"
      },
      "source": [
        "PCA is largely affected by scales and different features might have different scales. So it is better to standardize data before finding PCA components.\n",
        "Next, we need to center the values in each column by subtracting the mean column value."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Bt5JuiIkpuuP"
      },
      "source": [
        "C = A - M\n",
        "print('Normalized matrix',C.shape)\n",
        "print(C)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "froGnrDqp_dO"
      },
      "source": [
        "The next step is to calculate the covariance matrix of the centered matrix C.Correlation is a normalized measure of the amount and direction (positive or negative) that two columns change together. \n",
        "Covariance is a generalized and unnormalized version of correlation across multiple columns. \n",
        "A covariance matrix is a calculation of covariance of a given matrix with covariance scores for every column with every other column, including itself."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1XSFN_h5pxAf"
      },
      "source": [
        "V = cov(C)\n",
        "print('Covariance matrix V:')\n",
        "print('C',C.shape,'x C^T ',C.T.shape,'->',V.shape)\n",
        "print(V)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DysLHUt_qDUu"
      },
      "source": [
        "Finally, we calculate the eigendecomposition of the covariance matrix V. \n",
        "This results in a list of eigenvalues and a list of eigenvectors.\n",
        "\n",
        "The eigendecomposition is calculated on a square matrix using an efficient iterative algorithm, of which we will not go into the details."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kmlM0W-Upyhw"
      },
      "source": [
        "# eigendecomposition of covariance matrix\n",
        "values, vectors = eig(V)\n",
        "print('\\nEigenvectors:')\n",
        "print(vectors)\n",
        "print('\\nEigenvalues:')\n",
        "print(values)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RnYpwfPMkoQz"
      },
      "source": [
        "# project data\n",
        "P = vectors.T.dot(C)\n",
        "print('\\nProjected data:')\n",
        "print(P)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sEkigIBiq0wq"
      },
      "source": [
        "Interestingly, we can see that only the first eigenvector is required, suggesting that we could project our 2×3 matrix onto a 1×3 matrix with little loss, i.e., we lose no information when projecting to a line. Essentially project along the X axis."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R9I1Rz-1qXO3"
      },
      "source": [
        "This is called the covariance method for calculating the PCA, although there are alternative ways to to calculate it. \n",
        "\n",
        "Other matrix decomposition methods can be used such as Singular-Value Decomposition, or SVD. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eD1nF8_p_h8s"
      },
      "source": [
        "#PCA on MNIST dataset with code"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vxdb2OXqr1ss"
      },
      "source": [
        "Loading the MNIST dataset images and their labels. Load only the training set  normalizing the data.\n",
        "\n",
        "![alt text](https://machinelearningmastery.com/wp-content/uploads/2019/02/Plot-of-a-Subset-of-Images-from-the-MNIST-Dataset-1024x768.png)\n",
        "\n",
        "Each number is a 28x28 image which corresponds to a 784 dimensional vector.\n",
        "This is difficult to visualize so we need to reduce the dimensionality. Lets try and reduce the dimensionality to 3!\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gvZL5DxW1uw_"
      },
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from keras.datasets import mnist\n",
        "\n",
        "from sklearn.preprocessing import StandardScaler\n",
        "\n",
        "(X_train, label), (_, _) = mnist.load_data()\n",
        "X_train = X_train.reshape(len(X_train), np.prod(X_train.shape[1:]))\n",
        "data = X_train\n",
        "standardized_data = StandardScaler().fit_transform(data)\n",
        "print(standardized_data.shape)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEqPCbvS4Dqa"
      },
      "source": [
        "#find the co-variance matrix which is : A^T * A\n",
        "sample_data = standardized_data\n",
        "# matrix multiplication using numpy\n",
        "covar_matrix = np.matmul(sample_data.T , sample_data)\n",
        "print (\"The shape of variance matrix =\", covar_matrix.shape)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LSGHdLUm4Pnp"
      },
      "source": [
        "# finding the top two eigen-values and corresponding eigen-vectors \n",
        "# for projecting onto a 3-Dim space.\n",
        "#https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.linalg.eigh.html\n",
        "from scipy.linalg import eigh\n",
        "# the parameter ‘eigvals’ is defined (low value to heigh value) \n",
        "# eigh function will return the eigen values in asending order\n",
        "# this code generates only the top 3 eigenvalues.\n",
        "values, vectors = eigh(covar_matrix)\n",
        "vectors = vectors[:,-3:]\n",
        "print(\"Shape of eigen vectors = \",vectors.shape)\n",
        "# converting the eigen vectors into (3,d) shape for easyness of further computations\n",
        "vectors = vectors.T\n",
        "print(\"Updated shape of eigen vectors = \",vectors.shape)\n",
        "# here the vectors[1] represent the eigen vector corresponding 1st principal eigen vector\n",
        "# here the vectors[0] represent the eigen vector corresponding 2nd principal eigen vector"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5_PJuv-g4gYF"
      },
      "source": [
        "Projecting the original data sample on the plane formed by three principal eigenvectors by vector-vector multiplication."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z7ZolHL74ZeX"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "new_coordinates = np.matmul(vectors, sample_data.T)\n",
        "# also add the label as a third dimension to use it for color visualization\n",
        "new_coordinates = np.vstack((new_coordinates, label)).T\n",
        "print(new_coordinates.shape)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vPrcCJ2x-kAr"
      },
      "source": [
        "fig = plt.figure(figsize=(8, 6))\n",
        "ax = fig.add_subplot(111, projection='3d')\n",
        "\n",
        "ax.scatter(new_coordinates[:,0], new_coordinates[:,1], new_coordinates[:,2], c=new_coordinates[:,3]*20, s=50, alpha=0.6, edgecolors='w')\n",
        "\n",
        "ax.set_xlabel('1st_principal')\n",
        "ax.set_ylabel('2nd_principal')\n",
        "ax.set_zlabel('3d_principal')\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "--y0Xg-d4msO"
      },
      "source": [
        "Appending label to the 3d projected data(vertical stack) and plotting the labeled points."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dOL4SE6g6TUR"
      },
      "source": [
        "#PCA for dimensionality Reduction using Scikit-Learn"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MHuj7_j5tCPb"
      },
      "source": [
        "Lets see how to use the principle components to reconstruct the original data. We will use the sci-kit learn library and its built-in PCA method."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oJksLYDk6Ti2"
      },
      "source": [
        "# initializing the pca\n",
        "from sklearn import decomposition\n",
        "from sklearn.preprocessing import StandardScaler\n",
        "\n",
        "pca = decomposition.PCA()\n",
        "scaler = StandardScaler()\n",
        "\n",
        "#Fit on training set only.\n",
        "mnist = scaler.fit_transform(sample_data)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jaljX2YC6h0o"
      },
      "source": [
        "# PCA for dimensionality redcution\n",
        "#We set the maximum number of components\n",
        "pca.n_components = 784\n",
        "\n",
        "pca_data = pca.fit_transform(mnist)\n",
        "\n",
        "#The PCA function internally computes how much of the variance is captures by \n",
        "#each component. \n",
        "percentage_var_explained = pca.explained_variance_ / np.sum(pca.explained_variance_);\n",
        "\n",
        "cum_var_explained = np.cumsum(percentage_var_explained)\n",
        "\n",
        "# Plot the PCA spectrum\n",
        "plt.figure(1, figsize=(6, 4))\n",
        "\n",
        "plt.clf()\n",
        "plt.plot(cum_var_explained, linewidth=2)\n",
        "plt.axis('tight')\n",
        "plt.grid()\n",
        "plt.xlabel('n_components')\n",
        "plt.ylabel('Cumulative_explained_variance')\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WErcT8YxuMSP"
      },
      "source": [
        "If we take 200-dimensions, approx. 90% of variance is expalined.\n",
        "\n",
        "\n",
        "The idea with going from 784 components to 154 is to reduce the running time of a supervised learning algorithm. One of the cool things about PCA is that we can go from a compressed representation (154 components) back to an approximation of the original high dimensional data (784 components)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QG4feVsYvBMl"
      },
      "source": [
        "#Select the number of components used to construct the lower dimensional space\n",
        "#15,200\n",
        "pca.n_components = 15\n",
        "# fit the transform and project data to the lower-dimensional space\n",
        "pca_data = pca.fit_transform(mnist)\n",
        "#poject back to the original space\n",
        "approximation = pca.inverse_transform(pca_data)\n",
        "\n",
        "#Plot the original image and its reconstruction\n",
        "plt.figure(figsize=(8,4));\n",
        "\n",
        "# Original Image\n",
        "plt.subplot(1, 2, 1);\n",
        "#30000,40000\n",
        "ind=40000\n",
        "plt.imshow(sample_data[ind].reshape(28,28)*255,\n",
        "              cmap = plt.cm.gray, interpolation='nearest',\n",
        "              clim=(0, 255));\n",
        "plt.xlabel('784 components', fontsize = 14)\n",
        "plt.title('Original Image', fontsize = 20);\n",
        "\n",
        "plt.subplot(1, 2, 2);\n",
        "plt.imshow(approximation[ind].reshape(28, 28)*255,\n",
        "              cmap = plt.cm.gray, interpolation='nearest',\n",
        "              clim=(0, 255));\n",
        "plt.xlabel(str(pca.n_components)+' components', fontsize = 14)\n",
        "plt.title('Reconstructed Output', fontsize = 20);"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}