unit12_cluster/demo1_doc_cluster.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Demo:  Document Clustering and Latent Semantic Analysis\n",
    "\n",
    "An important application of clustering is for sorting documents into groups.  In this demo, we will illustrate how to use the k-means algorithms for this task.  This example is taken mostly from one of the [sklearn examples](http://scikit-learn.org/stable/auto_examples/text/document_clustering.html).\n",
    "\n",
    "Through the demo, you will learn how to:\n",
    "* Represent a corpus as a set of strings\n",
    "* Build a vocabulary from a corpus\n",
    "* Compute the TF-IDF scores for the documents in the corpus based on the vocabulary\n",
    "* Run k-means to automatically discover document clusters\n",
    "* Display key terms in each document cluster\n",
    "* Perform an LSA on a corpus with a sparse SVD."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Loading the Data\n",
    "\n",
    "First, we load the standard packages along with a number of `sklearn` sub-packages for text processing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import fetch_20newsgroups\n",
    "from sklearn.decomposition import TruncatedSVD\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "from sklearn.feature_extraction.text import HashingVectorizer\n",
    "from sklearn.feature_extraction.text import TfidfTransformer\n",
    "from sklearn.pipeline import make_pipeline\n",
    "from sklearn.preprocessing import Normalizer\n",
    "from sklearn import metrics\n",
    "\n",
    "from sklearn.cluster import KMeans, MiniBatchKMeans\n",
    "\n",
    "import sys\n",
    "from time import time\n",
    "\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [UseNet newsgroups](https://en.wikipedia.org/wiki/Usenet_newsgroup) were popular 20 years ago as online forums for discussing various issues.  Although they are not used much today for topic discussions, the posts from that era are still widely-used in machine learning classes for demonstrating various text processing methods.  Due to their wide use, the `sklearn` package has a built-in routine `fetch_20newsgroups` for extracting the newsgroup examples.  We will extract just four of the 20 categories in this demo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading 20 newsgroups dataset for categories:\n",
      "['alt.atheism', 'talk.religion.misc', 'comp.graphics', 'sci.space']\n"
     ]
    }
   ],
   "source": [
    "categories = [\n",
    "    'alt.atheism',\n",
    "    'talk.religion.misc',\n",
    "    'comp.graphics',\n",
    "    'sci.space',\n",
    "]\n",
    "# Uncomment the following to do the analysis on all the categories\n",
    "#categories = None\n",
    "\n",
    "print(\"Loading 20 newsgroups dataset for categories:\")\n",
    "print(categories)\n",
    "\n",
    "dataset = fetch_20newsgroups(subset='all', categories=categories,\n",
    "                             shuffle=True, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the `np.unique` command to compute the number of unique labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "labels = dataset.target\n",
    "true_k = len(np.unique(labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The data is in the `data` field of `dataset`.  Each entry `dataset.data[i]` is a string corresponding to the post to the newsgroup.  We can print an example as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Post from comp.graphics\n",
      "\n",
      "From: richter@fossi.hab-weimar.de (Axel Richter)\n",
      "Subject: True Color Display in POV\n",
      "Keywords: POV, Raytracing\n",
      "Nntp-Posting-Host: fossi.hab-weimar.de\n",
      "Organization: Hochschule fuer Architektur und Bauwesen Weimar, Germany\n",
      "Lines: 6\n",
      "\n",
      "\n",
      "Hallo POV-Renderers !\n",
      "I've got a BocaX3 Card. Now I try to get POV displaying True Colors\n",
      "while rendering. I've tried most of the options and UNIVESA-Driver\n",
      "but what happens isn't correct.\n",
      "Can anybody help me ?\n",
      "\n"
     ]
    }
   ],
   "source": [
    "doc_ind = 10  # Index of an example document\n",
    "data_ex = dataset.data[doc_ind]\n",
    "cat_ex  = dataset.target_names[labels[doc_ind]]\n",
    "print('Post from {0:s}'.format(cat_ex))\n",
    "print()\n",
    "print(data_ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computing TF-IDF features\n",
    "\n",
    "Documents are natively text.  To apply most machine learning algorithms, we need to convert the documents to vectors.  One popular method is the so-called TF-IDF score.  First, we select a set of words in the corpus.  Each word is sometimes called a *token*.  For each token `n` and document `i`, we then compute the data matrix:\n",
    "      \n",
    "    X[n,i] = TF-IDF score of word i in document n\n",
    "           = term freq[n,i] * inverse doc frequency[i]\n",
    "           \n",
    "where\n",
    "\n",
    "    term freq[n,i]  = (#occurances of word i in doc n)/(#words in doc n)  \n",
    "    inverse doc freq[i] = log(#docs in corpus/#docs with word i)\n",
    "        \n",
    "In the data matrix `X`, each document `n` is represented by a vector `X[n,:]`.\n",
    "\n",
    "The data matrix `X` can be computed by a *vectorizer*.  Writing an efficient vectorizer is somewhat time-consuming.  Luckily, `sklearn` has very good routines to compute the TF-IDF representations of a corpus.  We first create a `TfidfVectorizer` object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "vectorizer = TfidfVectorizer( \n",
    "                max_df=0.5, # max doc freq (as a fraction) of any word to include in the vocabulary\n",
    "                min_df=2,   # min doc freq (as doc counts) of any word to include in the vocabulary\n",
    "                max_features=10000,           # max number of words in the vocabulary\n",
    "                stop_words='english',         # remove English stopwords\n",
    "                use_idf=True )        # use IDF scores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we create the data matrix from the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extracting features from the training dataset using a sparse vectorizer\n",
      "done in 1.329500s\n",
      "n_samples: 3387, n_features: 10000\n"
     ]
    }
   ],
   "source": [
    "print(\"Extracting features from the training dataset using a sparse vectorizer\")\n",
    "t0 = time()\n",
    "X = vectorizer.fit_transform(dataset.data)\n",
    "print(\"done in %fs\" % (time() - t0))\n",
    "print(\"n_samples: %d, n_features: %d\" % X.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can display the terms with the highest TF-IDF scores in a post as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "weimar               0.565396 \n",
      "pov                  0.518174 \n",
      "renderers            0.183033 \n",
      "univesa              0.178595 \n",
      "und                  0.174842 \n",
      "fuer                 0.171591 \n",
      "true                 0.159214 \n",
      "raytracing           0.150534 \n",
      "displaying           0.140240 \n",
      "ve                   0.139752 \n",
      "options              0.134309 \n",
      "rendering            0.133027 \n",
      "driver               0.129544 \n",
      "happens              0.122540 \n",
      "colors               0.119138 \n",
      "card                 0.113776 \n",
      "display              0.108457 \n",
      "germany              0.108231 \n",
      "tried                0.106282 \n",
      "color                0.103717 \n",
      "anybody              0.100397 \n",
      "correct              0.100234 \n",
      "isn                  0.084694 \n",
      "got                  0.081865 \n",
      "keywords             0.081865 \n",
      "try                  0.080601 \n",
      "help                 0.078058 \n",
      "nntp                 0.044277 \n",
      "host                 0.043985 \n",
      "posting              0.042608 \n"
     ]
    }
   ],
   "source": [
    "doc_ind = 10  # Index of an example document\n",
    "xi = X[doc_ind,:].todense()\n",
    "term_ind = xi.argsort()[:, ::-1]\n",
    "xi_sort = xi[0,term_ind]\n",
    "terms = vectorizer.get_feature_names()\n",
    "\n",
    "for i in range(30):\n",
    "    term = terms[term_ind[0,i]]\n",
    "    tfidf = xi[0,term_ind[0,i]]\n",
    "    print('{0:20s} {1:f} '.format(term, tfidf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Run k-Means\n",
    "\n",
    "We now run k-means on the TF-IDF vectors to try  to automatically detect clusters.  First, we construct a `kMeans` object to perform the clustering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "km = KMeans(n_clusters=true_k, init='k-means++', max_iter=100, n_init=1,\n",
    "                verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Then, we run the k-means clustering.  This will run through several iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Clustering sparse data with KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=100,\n",
      "    n_clusters=4, n_init=1, n_jobs=1, precompute_distances='auto',\n",
      "    random_state=None, tol=0.0001, verbose=True)\n",
      "Initialization complete\n",
      "Iteration  0, inertia 6471.584\n",
      "Iteration  1, inertia 3298.955\n",
      "Iteration  2, inertia 3286.116\n",
      "Iteration  3, inertia 3282.101\n",
      "Iteration  4, inertia 3280.273\n",
      "Iteration  5, inertia 3279.445\n",
      "Iteration  6, inertia 3278.835\n",
      "Iteration  7, inertia 3278.143\n",
      "Iteration  8, inertia 3277.275\n",
      "Iteration  9, inertia 3276.412\n",
      "Iteration 10, inertia 3275.771\n",
      "Iteration 11, inertia 3275.325\n",
      "Iteration 12, inertia 3274.769\n",
      "Iteration 13, inertia 3274.301\n",
      "Iteration 14, inertia 3274.040\n",
      "Iteration 15, inertia 3273.789\n",
      "Iteration 16, inertia 3273.598\n",
      "Iteration 17, inertia 3273.358\n",
      "Iteration 18, inertia 3273.018\n",
      "Iteration 19, inertia 3272.584\n",
      "Iteration 20, inertia 3272.387\n",
      "Iteration 21, inertia 3272.262\n",
      "Iteration 22, inertia 3272.163\n",
      "Iteration 23, inertia 3272.137\n",
      "Iteration 24, inertia 3272.116\n",
      "Iteration 25, inertia 3272.098\n",
      "Iteration 26, inertia 3272.086\n",
      "Iteration 27, inertia 3272.073\n",
      "Iteration 28, inertia 3272.052\n",
      "Iteration 29, inertia 3272.050\n",
      "Converged at iteration 29: center shift 0.000000e+00 within tolerance 9.816505e-09\n",
      "done in 8.145s\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"Clustering sparse data with %s\" % km)\n",
    "t0 = time()\n",
    "km.fit(X)\n",
    "print(\"done in %0.3fs\" % (time() - t0))\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get an idea of the clusters, we print out the terms corresponding to the 10 largest components of the centroid in each cluster.  You can clearly see the clustering of topics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cluster 0: graphics image thanks university files file 3d help gif ac\n",
      "Cluster 1: space com nasa article gov university posting like just host\n",
      "Cluster 2: god com sandvik people keith jesus say don morality sgi\n",
      "Cluster 3: henry access toronto digex pat alaska zoo spencer net space\n"
     ]
    }
   ],
   "source": [
    "order_centroids = km.cluster_centers_.argsort()[:, ::-1]\n",
    "for i in range(true_k):\n",
    "    print(\"Cluster %d:\" % i, end='')\n",
    "    for ind in order_centroids[i, :10]:\n",
    "        print(' %s' % terms[ind], end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparison of clusters to newsgroup categories\n",
    "\n",
    "The clusters found by k-means were not based on the newsgroup category in which the post came from.  To compare the two, we create a sort of confusion matrix where:\n",
    "\n",
    "`C[i,j] = ` fraction of cluster `j` came from newsgroup `i`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.00469484  0.11244378  0.66358025  0.        ]\n",
      " [ 0.94131455  0.12668666  0.00102881  0.00436681]\n",
      " [ 0.03521127  0.54947526  0.          0.97816594]\n",
      " [ 0.01877934  0.2113943   0.33539095  0.01746725]]\n"
     ]
    }
   ],
   "source": [
    "labelkm = km.labels_\n",
    "from sklearn.metrics import confusion_matrix\n",
    "C = confusion_matrix(labels,labelkm)\n",
    "\n",
    "Csum = np.sum(C,axis=0)\n",
    "Cnorm = C / Csum[None,:]\n",
    "print(Cnorm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To interpret this confusion matrix, let's print out the newsgroup names:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['alt.atheism', 'comp.graphics', 'sci.space', 'talk.religion.misc']"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset.target_names"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, returning to the confusion matrix, we see that some discovered clusters lie almost entirely within one of the newsgroup subjects.  This is especially true for `comp.graphics` and `sci.space`.  However, some discovered clusters tend to have entries of both `alt.atheism` and `talk.religon.misc`, whose topics are likely to have a lot of overlap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We print an example of a post that came from a newsgroup that is different from the most common newsgroup in that cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual newsgroup: talk.religion.misc\n",
      "Most common newsgroup in cluster:  sci.space\n",
      "\n",
      "From: dickeney@access.digex.com (Dick Eney)\n",
      "Subject: Re: Swastika (was: Hitler - pagan or Christian?)\n",
      "Organization: Express Access Online Communications, Greenbelt, MD USA\n",
      "Lines: 15\n",
      "NNTP-Posting-Host: access.digex.net\n",
      "\n",
      "The observation that the Tree of Life would rotate clockwise in the\n",
      "northern hemisphere and counterclockwise in the southern probably doesn't\n",
      "give enough consideration to the feebleness of the Coriolis force compared\n",
      "to, say, the phototropism of vegetation.  A much more likely explanation\n",
      "is the classic one: that the clockwise swastika is the Sun-wheel, because\n",
      "the sun progresses across the sky that way.  (Although that's not the\n",
      "historical way it happened; clocks were first made as little imitation\n",
      "images of the sun moving thru the heavens.  So it's more valid to talk of\n",
      "the clock going sunwise, but do the engineers listen to me?  Of course\n",
      "not.)  Anyway, there is still much uncertainty about whether the\n",
      "anti-swastika goes counter-sunwise because that represents Evil, or\n",
      "because it is the Sun's twin-opposite, the Moonwheel.  The use of anti-Sun\n",
      "to represent Evil may be because humans are so strongly visually-oriented,\n",
      "but I'm not going to try to settle THAT one just now.\n",
      "-- Diccon Frankborn (dickeney@access.digex.com)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "I = np.where((labels==3) & (labelkm == 3))[0]\n",
    "doc_ind = I[3]\n",
    "ind_cluster = labelkm[doc_ind]\n",
    "km_cat = dataset.target_names[np.argmax(Cnorm[:,ind_cluster])]\n",
    "\n",
    "data_ex = dataset.data[doc_ind]\n",
    "true_cat  = dataset.target_names[labels[doc_ind]]\n",
    "print('Actual newsgroup: {0:s}'.format(true_cat))\n",
    "print('Most common newsgroup in cluster:  {0:s}'.format(km_cat))\n",
    "print()\n",
    "print(data_ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Latent Semantic Analysis\n",
    "\n",
    "Another important tool in document analysis is [latent semantic analysis (LSA)](https://en.wikipedia.org/wiki/Latent_semantic_analysis).  In LSA, we simply compute an SVD of the TF-IDF matrix,\n",
    "\n",
    "    X = U diag(S) V\n",
    "    \n",
    "This is equivalent to performing a PCA on `X`.  If we let `A = U diag(S)` then `X = AV`.  First, we compute the PCs of `X`.  Since `X` is a sparse matrix, it is preferable to use the sparse `svds` method in the `scipy` package."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "import scipy.sparse.linalg\n",
    "U1,S1,V1 = scipy.sparse.linalg.svds(X,k=300)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can next plot the singular values. We see that the first few singular values are significantly larger than the remaining singular values suggesting that the term-document matrix `X` has a low rank structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x18b0992fc18>]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXEAAAEACAYAAABF+UbAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFfJJREFUeJzt3X2QXXV9x/H3Nw9ENgkkgUAICQmIEAkiYMCqoLeDUoby\nYO1YtcNYrTJ22gpFpqJ1OtmZtk47nVqtU9v6hKU1daytPIwMitbLgyCgJIRAIlgaQgiEhDyRRDbZ\n8Osfv3vZzbKbvZc99949d9+vmTP37Lkn5/5+czaf+9vveYqUEpKkcprU6QZIkl49Q1ySSswQl6QS\nM8QlqcQMcUkqMUNckkqsoRCPiKsj4uHadFWrGyVJasyoIR4RS4GPAMuAM4FLIuKkVjdMkjS6Rkbi\nrwfuSyn1pZQOAHcC72ltsyRJjWgkxNcA50fE7IjoAS4GFra2WZKkRkwZbYWU0rqI+BvgdmA3sBI4\n0OqGSZJGF83eOyUi/gp4KqX0z0OWexMWSWpSSinG8u8bPTtlbu31BOC3gBUjNKYrp+XLl3e8DfbP\n/tm/7puKMGo5pea/ImIOsB/4w5TSrkI+XZI0Jg2FeErp7a1uiCSpeV6x2YBKpdLpJrSU/Ss3+zex\nNX1gc8QNRaSitiVJE0FEkNpxYFOSND4Z4pJUYoa4JJWYIS5JJWaIS1KJGeKSVGKGuCSVmCEuSSVm\niEtSiRniklRihrgklZghLkklZohLUokZ4pJUYoa4JJWYIS5JJWaIS1KJNfq0+2siYk1ErI6Ib0bE\nYa1umCRpdKOGeETMBz4OnJ1SOoP8cOX3t7phkqTRNfS0e2AyMD0iXgJ6gE2ta5IkqVGjjsRTSpuA\nvwM2AE8DO1JKP2x1wyRJo2uknDILuBxYBMwHZkTE77a6YZKk0TVSTnkn8ERKaRtARPw38FZgxdAV\ne3t7X56vVCpUKpVCGilJ3aBarVKtVgvdZqSUDr1CxLnA14BzgD7geuCBlNI/DlkvjbYtSdKAiCCl\nFGPZRiM18fuB7wArgYeAAL48lg+VJBVj1JF4wxtyJC5JTWnLSFySNH4Z4pJUYoa4JJWYIS5JJWaI\nS1KJGeKSVGKGuCSVmCEuSSVmiEtSiRniklRihrgklZghLkklZohLUokZ4pJUYoa4JJWYIS5JJWaI\nS1KJGeKSVGKGuCSV2KghHhGnRMTKiHiw9rozIq5qR+MkSYfW1IOSI2ISsBF4c0rpqSHv+aBkSWpC\nJx6U/E7gf4cGuCSpM5oN8fcB/9GKhkiSmjel0RUjYipwGfCpkdbp7e19eb5SqVCpVMbQNEnqLtVq\nlWq1Wug2G66JR8RlwB+mlC4a4X1r4pLUhHbXxD+ApRRJGlcaGolHRA/wJHBSSumFEdZxJC5JTShi\nJN7UKYajNMYQl6QmdOIUQ0nSOGKIS1KJGeKSVGKGuCSVmCEuSSVmiEtSiRniklRihrgklZghLkkl\nZohLUokZ4pJUYoa4JJWYIS5JJWaIS1KJGeKSVGKGuCSVmCEuSSVmiEtSiRniklRiDYV4RBwZEf8Z\nEWsj4pGIeHOrGyZJGt2UBtf7AnBrSum9ETEF6GlhmyRJDRr1afcRcQSwMqX02lHW82n3ktSEdj3t\n/kRga0RcHxEPRsSXI+Lw4VY0wyWpvRopp0wBzgb+KKX0s4j4PPApYPnQFZcv72VS7WuhUqlQqVSK\na6kklVy1WqVarRa6zUbKKccC96aUTqr9fB5wXUrp0iHrpb6+xGGHFdo+SepabSmnpJQ2A09FxCm1\nRRcAjw63bn//WJoiSWpWo2enXAV8MyKmAk8AHx5uJUNcktpr1HJKwxuKSNu2JWbPLmRzktT12nV2\nSsMciUtSexniklRihYb4gQNFbk2SNBpH4pJUYoa4JJWY5RRJKjFH4pJUYo7EJanECg3xPXuK3Jok\naTSFhvj27UVuTZI0mkJDfNu2IrcmSRqNIS5JJWaIS1KJGeKSVGKGuCSVmCEuSSVmiEtSiRniklRi\nhrgklVhDz9iMiPXATuAlYH9K6dxh1kmTJyf27YNJhX41SFJ3KuIZm40+7f4loJJSOuSF9dOnw65d\nMGvWWJokSWpUo2PmaGTdOXMsqUhSOzUa4gm4PSIeiIgrR1rJEJek9mq0nPK2lNIzETGXHOZrU0p3\nD11p+/ZePv95OPlkqFQqVCqVQhsrSWVWrVapVquFbrOhA5sH/YOI5cALKaXPDVmePvaxxKmnwjXX\nFNlESepORRzYHLWcEhE9ETGjNj8duBBYM9y6558Pd901luZIkpox6kg8Ik4Evkuui08BvplS+uth\n1ksbNiTe9CbYvBliTN8tktT9ihiJN11OOURjUkqJxYvhtttgyZJCNitJXast5ZRmnX8+3P2KQ56S\npFYoPMTPOgtWry56q5Kk4RQe4qefDmuGPewpSSqaIS5JJVZ4iB93HPT3w3PPFb1lSdJQhYd4hKNx\nSWqXltw01hCXpPZoSYifcQasWtWKLUuSBmtJiC9bBj/7WSu2LEkarPArNgH6+mD2bNi6FXp6Ctm8\nJHWdcXnFJsC0abB0qSUVSWq1lj0Nc9kyeOCBVm1dkgQtDvGf/7xVW5ckQQtD/LTTYN26Vm1dkgQt\nDPHXvQ4efxwKOm4qSRpGy0L8qKPy1Ztbt7bqEyRJLQvxiDwaf+yxVn2CJKllIQ5wyim5pCJJao2W\nh7gjcUlqnYZDPCImRcSDEXFzo/+mfnBTktQazYzErwYebWbjS5fCQw811yBJUuMaCvGIWABcDHy1\nmY2fdhps3uwZKpLUKo2OxP8e+FOgqbO+J0+GN78Z7r236XZJkhowZbQVIuI3gc0ppVURUQFGvONW\nb2/vy/OVSoVKpcJb3wr33AOXXlpAayWpxKrVKtVqtdBtjnor2oj4LHAF0A8cDswE/jul9MEh66Xh\ntvWDH8Bf/iXceWdhbZakrlDErWibup94RLwDuDaldNkw7w0b4i+8AAsX5vuozJs3lqZKUncZt/cT\nH2zmTPjt34ZvfKPVnyRJE09Lnuwz1P33wwc+kM8Zn9Tyrw1JKodSjMQBzjkHjjgCfvSjdnyaJE0c\nbQnxCPjYx+Bf/qUdnyZJE0dbyikAu3bB4sXw9a/Du99dyEdKUqmVppwCuZxyyy1w7bWOyCWpKG0b\nidf94hdw3nlwxx35snxJmqhKNRKvO/VUuPJKWLGi3Z8sSd2nIyf8XXgh3H57Jz5ZkrpL28spAH19\nMHcuPPkkzJ5dyMdLUumUspwCMG1arovfemsnPl2SuseodzFslT/5E7jiCnjxRfjIRzrVCkkqt46U\nU+pWrYJLLoH162FKx75OJKkzSltOqTvzTDjhBPje9zrZCkkqr47fjurqq+FDH8o3yNqypdOtkaRy\n6XiIv+99+WHKixblR7nt3NnpFklSeXS0Jj7UlVfCa14DX/xiIU2SpHGt7U/2GaUxYw7xbdvgjW/M\nZ6584hP57oeS1K2KCPFxdU7InDnwk5/ARRfB5Mk5zCVJIxtXIQ75bJVbb4W3vCX//PGP50CXJL3S\nuCqnDPbYY/kioPnz882yDHJJ3aYt54lHxLSIuC8iVkbEwxGxfCwf2KhTTsk3ydq6FSoV+Pa3Yd++\ndnyyJJVHQyPxiOhJKe2NiMnAT4CrUkr3D1mn0JF43b59cOON8E//BM8+m5/TOX9+4R8jSW3Xtis2\nU0p7a7PTyHX04tN6BIcdBr/zO/DjH8MHPwi/9mtw/fXQgu8LSSqdRkfik4CfA68F/jGl9Olh1mnJ\nSHyoO++Ea66BJUvgq1+Fww9v+UdKUku07RTDlNJLwFkRcQRwY0ScllJ6dOh6vb29L89XKhUqlcpY\n2jast78d7r4bfv/3c638u9+1vCKpHKrVKtVqtdBtNn12SkT8ObAnpfS5IcvbMhKvSwk++1n40pfg\nK1+Biy9u20dLUiHadXbK0RFxZG3+cOBdwLqxfGgRIuAzn4EbbsgXBV12Gfzf/3W6VZLUXo0c2DwO\n+HFErALuA76fUho3z+S54AJ4+OF8cdA55+SLg1asgOef73TLJKn1xu3FPq/G+vXwrW/BT38Kd9yR\nb3H70Y/C0qUdbZYkDavrboBVpGeegc99Dv7933OQf/KTMHNmp1slSQNK/2SfVjruOPjbv833Kr/3\nXpg3L59j/u1vQ39/p1snScXo2pH4UAcOwM0359H5pk1w7bX5YOiCBZ1umaSJynLKq3THHfDlL8P3\nvw9XXAGXXgrnnmu5RVJ7GeJj9Oyz8IUvwF13wapV8N735vr5W94Ck7q20CRpvDDEC7RjR34s3IoV\neVT+jW/4ZCFJrWWIt8DevXDeeXDMMXDWWfnhzZdd5shcUvEM8RbZti3fy/yxx+Cmm+BXv4Jf/3W4\n7jpYuLDTrZPULQzxNnjppXzx0Pe+l+/TcvzxuWZ+8cXwznd6MFTSq2eIt9nOnfn+LHfckZ8Des89\ncOqpuYb+B3+QR+mzZ3e6lZLKwhDvsN274ZFH4JZb8uX+W7bAe94Db3gDvO51cPrpsGiR9XRJwzPE\nx5nnn89PHXrqqVxPX7MGtm+Hd7wjh/vSpfCmN8HUqZ1uqaTxwBAvgR078pWiP/whrF4Njz6aSy4X\nXACXXAJnnw0nnZQfQydpYjHES2j//nxzrttuy3X1NWtg48Z8wHTZMrjwQjjzTDjtNB89J3U7Q7xL\n7NuXD5jedVc+aLp6dS7HnHginHFGnpYuzc8VPekkyzFStzDEu9i+fbBuXQ70hx6CtWvzzxs35nBf\nsgRe//oc7vWAf81rOt1qSc0wxCegF1+Exx/Pgb52bT47Zs0aeOKJHOpLluSrTM87L5/yePTRnh0j\njVeGuF7W1wcPPpgDvlrN8xs3wq5dMHcuHHtsvsf6smVw/vn5/PZjjoFp0zrdcmniakuIR8QC4Abg\nWOAl4CsppX8YZj1DfBx68cV8/vrmzfD00/nq07vvzjX4557L4f7GN8JRR+Vp4UI44YR8fvsJJ+Qv\nAG8EJrVGu0J8HjAvpbQqImYAPwcuTymtG7KeIV4yKcEvf5lPe9y+HbZuzee4P/kkbNiQpz17cpjX\np3q41+cXLHA0L71aHSmnRMSNwBdTSj8astwQ70K7d+dg37Dh4HCvz2/aBHPmHBzu8+ZBTw/Mn59P\nnTz++Dzinzy5072Rxpe2h3hELAaqwOkppd1D3jPEJ6ADB/LDNQYH/LPP5hH8M8/kEs7TT+c7Qx5z\nTK7Fn3xyDv4TT8w3EDvyyFzSmT/f0o0mlraGeK2UUgX+IqV00zDvG+Ia0f79edT+yCM58J9/Htav\nzyP9bdvyk5V27cpBXh/Bv/a1+f4zs2bBEUcMTEcdBTNmGPgqvyJCfEqDHzQF+A7wb8MFeF1vb+/L\n85VKhUqlMpa2qYtMnZpLLosWjbzO3r056OvTunX5fu67dsELL+TXnTvzF0B/fz7bZtGiHPhz5+bp\n6KNfOT9njqdZanyoVqtUq9VCt9nQSDwibgC2ppQ+cYh1HImrbfbuzeWaDRtyuWbLljxt3TowX592\n7cr3q5k7N9frFy/OPx95ZJ5mzcrTnDl5mj07v3rxlFqtXWenvA24E3gYSLXpz1JKtw1ZzxDXuNTf\nn0fvW7bk4F+/Pt+YbOfOPO3Ykaft23Nppz5NmTIQ6IPDfbhlg+ePPNKRvxrjxT5Si6SUR/vbtg2E\n++CQH26+/rp7d67dNxv+jv4nHkNcGof6+/MIv5ngr0+TJjUW/rNmHVwKmjUrfwF4sLdcDHGpi6SU\nH8rdyOi/XgbauTMv37kzPw92cKgPNw0N/sHT4Yf7JdBuhrikl7344sE1/qHTod7bsSP/BTFrVj53\nf/r0/HrEEQMHgOvzM2fmUzzrU09P/gLo6Rn4opg50+MCjTDEJRWmry+H+e7dedq1a2CqHwTeuXPg\n/T17Bl5/9at8DKH+RbFnTw79adPyRV4LF+agHzz19Ax8EcycOTAN/rk+362lIkNc0rjU35/Dv68v\nnxG0aVMO+qHT7t35GoAXXjh4fuiy/v5Xhnv958Gvh1o2+IKxnp7x8aVgiEuaEPbvPzjU638NNLqs\nfsFY/aKxvr5cMhpcFqqXkQZPM2a8cn7w69BlzR5XaNsVm5LUSVOnDpyhU4T+/oFy0NAvgL1783uD\np23bBuaHKyfVl+3bd3CZaKTwnz49P8ClCIa4pAlnypSBA7ZFOnBg5LAfGvxF3dXTcookdUgR5RRP\nApKkEjPEJanEDHFJKjFDXJJKzBCXpBIzxCWpxAxxSSoxQ1ySSswQl6QSM8QlqcRGDfGI+FpEbI6I\n1e1okCSpcY2MxK8HfqPVDRnPqtVqp5vQUvav3OzfxDZqiKeU7ga2t6Et41a3/xLZv3KzfxObNXFJ\nKjFDXJJKrKH7iUfEIuCWlNIZh1jHm4lLUpPa9Xi2qE0ta4gkqXmNnGK4ArgHOCUiNkTEh1vfLElS\nIwp7PJskqf3GfGAzIi6KiHUR8VhEXFdEozotItZHxEMRsTIi7q8tmx0RP4iIX0TE9yOi4Eests5w\nF2wdqj8R8emIeDwi1kbEhZ1pdeNG6N/yiNgYEQ/WposGvVea/kXEgoj4n4h4JCIejoirasu7Yv8N\n07+P15Z3y/6bFhH31bLk4YhYXlte3P5LKb3qifwl8EtgETAVWAUsGcs2x8MEPAHMHrLsb4BP1uav\nA/660+1soj/nAWcCq0frD3AasJJ8vGRxbf9Gp/vwKvq3HPjEMOu+vkz9A+YBZ9bmZwC/AJZ0y/47\nRP+6Yv/V2txTe50M/BQ4t8j9N9aR+LnA4ymlJ1NK+4FvAZePcZvjQfDKv1IuB/61Nv+vwLvb2qIx\nSMNfsDVSfy4DvpVS6k8prQceJ+/ncWuE/sHwB+Mvp0T9Syk9m1JaVZvfDawFFtAl+2+E/h1fe7v0\n+w8gpbS3NjuNHM6JAvffWEP8eOCpQT9vZGAHlFkCbo+IByLio7Vlx6aUNkP+xQOO6VjrinHMCP0Z\nuk+fprz79I8jYlVEfHXQn6ul7V9ELCb/xfFTRv597Ib+3Vdb1BX7LyImRcRK4Fng9pTSAxS4/7zY\nZ3hvSymdDVwM/FFEnE8O9sG67Yhwt/XnS8BJKaUzyf95/q7D7RmTiJgBfAe4ujZi7arfx2H61zX7\nL6X0UkrpLPJfUOdGxFIK3H9jDfGngRMG/bygtqzUUkrP1F63ADeS/5zZHBHHAkTEPOC5zrWwECP1\n52lg4aD1SrlPU0pbUq3ICHyFgT9JS9e/iJhCDrh/SyndVFvcNftvuP510/6rSyntAqrARRS4/8Ya\n4g8AJ0fEoog4DHg/cPMYt9lREdFTGxUQEdOBC4GHyf36UG213wNuGnYD49fQC7ZG6s/NwPsj4rCI\nOBE4Gbi/XY0cg4P6V/uPUfceYE1tvoz9+zrwaErpC4OWddP+e0X/umX/RcTR9VJQRBwOvItc9y9u\n/xVw5PUi8hHlx4FPdfpIcAH9OZF8ls1Kcnh/qrZ8DvDDWl9/AMzqdFub6NMKYBPQB2wAPgzMHqk/\nwKfJR8XXAhd2uv2vsn83AKtr+/JGcg2ydP0D3gYcGPQ7+WDt/9yIv49d0r9u2X9vqPVpVa0/n6kt\nL2z/ebGPJJWYBzYlqcQMcUkqMUNckkrMEJekEjPEJanEDHFJKjFDXJJKzBCXpBL7fw5Hz7lpq1Ix\nAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x18b09895748>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(S1[::-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given the low rank structure of `X`, we can write \n",
    "\n",
    "     X[n,i] = \\sum_k A[n,k] V[k,i]\n",
    "     \n",
    "where the sum is over some relatively small number of components.  There are two uses for this representation:\n",
    "* Word and document embeddings:  A[n,:] provides a low-dimensional vector representation of each document.  This is useful pre-processing step in many natural processing (NLP) methods.  This type of representation is closely related to an important topic of *word embeddings* and *document embeddings*.\n",
    "* Topic modeling:  One interpretation of the PCA is that each PC `k` represents some common *topic* in the corpus.  Then, `A[n,k] =` the component of topic `k` in document `n` and `V[k,i]` represents the occurance of word `i` in topic `k`.\n",
    "\n",
    "To get an idea of the words within each PC, we print the words for the largest components in the first 5 PCs.  On a small corpus like 20 newsgroups, the PCs in this case are not very useful.  But, the technique can yield more useful results in larger corpi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PC 0: muenchen does dan bockamp targa colour shall ch uk man\n",
      "PC 1: phigs government uci 3d khomeini colorado uni rh rayshade screen\n",
      "PC 2: clarke asimov wesleyan values vga physics fl ed pluto tyre\n",
      "PC 3: ericsson color wesleyan point program convenient boeing scott targa jpeg\n",
      "PC 4: thanks muenchen format mac earth pluto color uci true ether\n"
     ]
    }
   ],
   "source": [
    "V1sort = np.abs(V1).argsort()[:, ::-1]\n",
    "for i in range(5):\n",
    "    print(\"PC %d:\" % i, end='')\n",
    "    for ind in V1sort[i, :10]:\n",
    "        print(' %s' % terms[ind], end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}