proof_1_pca_kmeans.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Visualizing and Understanding the Relationship between PCA, Auto encoder and K-Means Clustering."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Principal Component Analysis (PCA) is a widely used technique in the area\n",
    "of Unsupervised Dimensionality Reduction. In Unsupervised data Cluster-\n",
    "ing, one of the popular technique is K-means clustering. C Ding et al.\n",
    "proved that K-means Clustering can be approximated as a super-sparse PCA.\n",
    "Authors also proved that that the relaxed solution of K-means Clustering,\n",
    "specified by the Cluster Indicators, is given by Principal Component Anal-\n",
    "ysis (PCA). Although PCA is not a Clustering method, it is generally used\n",
    "to reveal Clusters. In General, both methods, PCA and K-means Clustering\n",
    "are used together. This is because in case of higher Dimension data, PCA\n",
    "helps in reducing the Dimension of data on which we can apply K-means\n",
    "Clustering to reduce Computation cost. In a nutshell, we aim to establish\n",
    "the Relationship between PCA and K-means Clustering along with needed\n",
    "proofs. Later we Visualise graphs, for this established Relationship on IMDB\n",
    "Movie dataset. Later we extend this to Understand relationship between PCA and \n",
    "auto-encoder. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "# Paper 1 : K-means Clustering via Principal Component Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "# Here we prove that principal components are the continuous solutions to the discrete cluster membership indicators for K-means clustering."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## 1.Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "\n",
    "This paper new insights to the observed effectiveness of PCA-based data reductions, beyond the conventional noise-reduction explanation. The need for Data reductions are characterized by Continously evolving data in high dimension space. In Unsupervised learning, most popular technique (Hartigan\n",
    "& Wang, 1979; Lloyd, 1957; MacQueen, 1967) is K means Method, which use Centroids to characterise clusters and optimise the Total cluster Distance (within Cluster distance and Between cluster distance.)\n",
    "\n",
    "In Unsupervised dimensonality reduction, PCA is one of most often used technique. In this technique, High dimension input is reduced to low Dimension input data. In ((Zha et al., 2002), It is shown that applying  PCA first is applied on data and K-means is applied on it to Cluster the data.\n",
    "\n",
    "In Principal Componenent Analysis(PCA), we pick the Attributes which give maximum variance. It is proven to be Equivalent to the best low rank approximation to Singular value decomposition(Eckart & Young, 1936). Although the importance of PCA can be explained with noise reduction, however there is still reasoning required to explain this out.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "This paper proves that principal components computed in the PCA technique are equivalent to Cluster membership indicators in K-Means clustering algorithm. In other words, PCA is performing Clustering according to Objective function defined in K-means clustering. This provides formal argument to performing K-means Clustering via PCA.\n",
    "\n",
    "K means clustering is characterised by Centroids for individual Clusters. The objective function defined in K-means clustering is :\n",
    "\n",
    "\n",
    "$J_{\\mathrm{K}}=\\sum_{k=1}^{K} \\sum_{i \\in C_{k}}\\left(\\mathbf{x}_{i}-\\mathbf{m}_{k}\\right)^{2}$\n",
    "\n",
    "Here (x1,x2,...,xn) denote Data matrix,\n",
    "\n",
    "$m_k$ denote centroid of Cluster k where $m_k$ = $\\sum_{i \\in C_{k}} \\mathbf{x}_{i} / n_{k}$\n",
    "\n",
    "$n_k$ denote number of points in a cluster k.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Formulation for PCA :\n",
    "\n",
    "Let the data matrix be X = (x1,x2,...,xn)\n",
    "\n",
    "Y = (y1,y2....yn) and $\\mathbf{y}_{i}=\\mathbf{x}_{i}-\\overline{\\mathbf{x}}$\n",
    "\n",
    "$\\overline{\\mathbf{x}}=\\sum_{i} \\mathbf{x}_{i} / n$\n",
    "\n",
    "Covariance matrix is designed as $\\sum_{i}\\left(\\mathbf{x}_{i}-\\overline{\\mathbf{x}}\\right)\\left(\\mathbf{x}_{i}-\\overline{\\mathbf{x}}\\right)^{T}/n=Y Y^{T}$\n",
    "\n",
    "principal directions be $A_k$\n",
    "\n",
    "Eigen values as $B_k$\n",
    "\n",
    "Condition for PCA can be specified as :\n",
    "\n",
    "\n",
    "$Y Y^{T} \\mathbf{A}_{k}=\\lambda_{k} \\mathbf{A}_{k}, Y^{T} Y \\mathbf{B}_{k}=\\lambda_{k} \\mathbf{B}_{k}, \\mathbf{B}_{k}=Y^{T} \\mathbf{A}_{k} / \\lambda_{k}^{1 / 2}$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "# Proof to show principal Components in PCA is equivalent to clusters membership indicators in K-means clustering.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "2 way Clustering :\n",
    "\n",
    "Let us assume K = 2, that implies \n",
    "\n",
    "$d\\left(\\mathrm{C}_{k}, \\mathrm{c}_{\\ell}\\right) \\equiv \\sum_{i \\in C_{k}} \\sum_{j \\in C_{\\ell}}\\left(\\mathrm{x}_{i}-\\mathrm{x}_{j}\\right)^{2}$\n",
    "\n",
    "Then we Simplify we get i.e..,\n",
    "\n",
    "$J_{\\mathrm{K}}=\\sum_{k=1}^{K} \\sum_{i \\in C_{k}} \\frac{\\left(\\mathbf{x}_{i}-\\mathbf{x}_{j}\\right)^{2}}{2 n_{k}}=n \\overline{\\mathbf{y}^{2}}-\\frac{1}{2} J_{\\mathrm{D}}$\n",
    "\n",
    "\n",
    "\n",
    "and also,\n",
    "\n",
    "\n",
    "$J_{\\mathrm{D}}=\\frac{n_{1} n_{2}}{n}\\left[2 \\frac{d\\left(\\mathrm{c}_{1}, \\mathrm{C}_{2}\\right)}{n_{1} n_{2}}-\\frac{d\\left(\\mathrm{c}_{1}, \\mathrm{C}_{1}\\right)}{n_{1}^{2}}-\\frac{d\\left(\\mathrm{c}_{2}, \\mathrm{C}_{2}\\right)}{n_{2}^{2}}\\right]$\n",
    "\n",
    "\n",
    "\n",
    "and $\\frac{d\\left(\\mathrm{C}_{1}, \\mathrm{C}_{2}\\right)}{n_{1} n_{2}}=\\frac{d\\left(\\mathrm{C}_{1}, \\mathrm{C}_{1}\\right)}{n_{1}^{2}}+\\frac{d\\left(\\mathrm{C}_{2}, \\mathrm{C}_{2}\\right)}{n_{2}^{2}}+\\left(\\mathrm{m}_{1}-\\mathrm{m}_{2}\\right)^{2}$\n",
    "\n",
    "where $\\overline{\\mathbf{y}^{2}}=\\sum_{i} \\mathbf{y}_{i}^{T} \\mathbf{y}_{i} / n$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "So minimising $J_{\\mathrm{K}}$ is equivalent to maximising $J_{\\mathrm{D}}$\n",
    "\n",
    "Theorm 1 :\n",
    "\n",
    "We have proved for K=2, minimising the within cluster distance  $J_{\\mathrm{K}}$ is eqivalent to maximising the the distance objective function  $J_{\\mathrm{D}}$ which is always positive.\n",
    "\n",
    "Note :\n",
    "\n",
    "1) Later we prove that maximising  $J_{\\mathrm{D}}$ \n",
    "\n",
    "\n",
    "\n",
    "Theorm 2 :\n",
    "\n",
    "For K = 2, Clustering membership solution is equivalent to principal component v1.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}