Chapter 14 - Unsupervised Learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 14 - Unsupervised Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.1 - Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* If one supposes that $(X, Y)$ are random variables represented by some joint probability density $Pr(X, Y)$, then supervised learning can be formally characterized as a density estimation problem where one is concerned with determining properties of the conditional density $Pr(Y|X)$. \n",
    "* Usually the properties of interest are the \"location\" parameters $\\mu$ that minimize the expected error at each x.\n",
    "* In unsupervised learning, one has a set of N observations $(x_1, x_2,..., x_N)$ of a random p-vector $X$ having joint density $Pr(X)$. The goal is to directly infer the properties of this probability density without the help of a supervisor or teacher providing correct answers or degree-of-error for each observation.\n",
    "* Principal components, multidimensional scaling, self-organizing maps, and principal curves, for example, attempt to identify low-dimensional manifolds within the X-space that represent high data density. \n",
    "* Cluster analysis attempts to find multiple convex regions of the X-space that contain modes of $Pr(X)$. This can tell whether or not $Pr(X)$ can be represented by a mixture of simpler densities representing distinct types or classes of observations.\n",
    "* In the context of unsupervised learning, there is no such direct measure of success as there is in supervised learning. It is difficult to ascertain the validity of inferences drawn from the output of most unsupervised learning algorithms. This uncomfortable situation has led to heavy proliferation of proposed methods, since effectiveness is a matter of opinion and cannot be verified directly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.2 - Association Rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The goal is to find joint values of the variables $X = (X_1, X_2, . . . , X_p)$ that appear most frequently in the data base.\n",
    "* For example, Assume $X_{ij}$ means a customer with transaction $i$ bought item $j$ (binary 0/1).  What combinations of j columns often are seen together? This can be useful for stocking shelves, cross marketing, etc.\n",
    "* The basic goal of association rule analysis is to find a collection of prototype X-values $v_1,...,v_L$ for the feature vector $X$, such that the probability density $Pr(v_l)$ evaluated at each of those values is relatively large -- the problem can be viewed as \"mode finding\" or \"bump hunting.\" \n",
    "* With many variables, the number of observations where $X = v_l$ will almost always be too small for estimation of $Pr(v_l)$ if you are taking the approach of estimating it with the fraction of observations that are $X = v_l$.\n",
    "* Instead, we seek regions of the X-space with high probability content relative to their size or support.\n",
    "* The ultimate goal is to find all item sets/combinations that have a prevalance greater than some lower bound $L$.\n",
    "* There are reasonable algorithms to compute this -- it exploits the idea that any item set $A$ consisting of a subset of items in $B$ must have support greater than or equal to that of $B$.  So we can start with item sets that are of rank 1 & discard those that are less than or equal to the threshold. Then we go to item sets of 2, ...repeat the process.\n",
    "\n",
    "**A-priori algorithm**\n",
    "* The high support item set $K$ returned by a-priori algorithm is cast into a set of association rules -- we partition it into 2 disjoint subsets $A$ and $B$ (not the same as the previous note).  A is called the antecedent and B the consequent. \n",
    "*  The \"support\" of the rule T(A ⇒ B) is the fraction of observations in the union of the antecedent and consequent, which is just the support of the item set K from which they were derived. It can be viewed as an estimate (14.5) of the probability of simultaneously observing both item sets Pr(A and B) in a randomly selected market basket. \n",
    "* The \"confidence\" or \"predictability\" C(A ⇒ B) of the rule is its support divided by the support of the antecedent which can be viewed as an estimate of Pr(B|A).\n",
    "* An example query might be \"Display all transactions in which ice skates are the consequent that have confidence over 80% and support of more than 2%.\" This could provide information on those items (antecedent) that predicate sales of ice skates. Focusing on a particular consequent casts the problem into the framework of supervised learning.\n",
    "\n",
    "**Unsupervised as Supervised**\n",
    "* The density estimation problem can be transformed into one of supervised function approximation. \n",
    "* The main idea here is to find an unknown density $g(x)$ by using a known density $g_0(x)$. Using monte carlo simulation we draw samples from $g_0(x)$ and assign them a value of y = 0. The resulting density is a mixture density. We also use $g(x)$ and assign those values y = 1.  Using the combined data set we can estimate $\\mu(x) = E(y|x)$.\n",
    "* After doing some algebra on $E(y|x)$ based on a mixture mean formula, we can recover a possible value for g(x).\n",
    "* These estimates may not always be accurate, but they can thus be viewed as \"contrast\" statistics that provide information concerning departures of the data density $g(x)$ from the chosen reference density $g_0(x)$.\n",
    "* Choice of reference density might depend on the question you are trying to ask -- for example, is there a departure from the uniform density?\n",
    "\n",
    "**Generalized Association Rules**\n",
    "* One might be able to use the \"supervised\" approach as above to find areas of high density for use in creating association rules.\n",
    "* Both market basket analysis and the generalized formulation implicitly reference the uniform probability distribution. One seeks item sets that are more frequent than would be expected if all joint data values $(x_1, x_2, \\dots, x_N)$ were uniformly distributed.\n",
    "* The market basket analysis seems to favor items that have high support.  For example, even if vodka => caviar generates a lot of lift, each individual item has low support so their joint support is also low.\n",
    "* Using the product of the variable marginal data densities as a reference distribution removes the preference for highly frequent values of the individual variables in the discovered item sets.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.3 - Cluster Analysis\n",
    "* Cluster analysis, also called data segmentation, has a variety of goals. All relate to grouping or segmenting a collection of objects into subsets or \"clusters,\" such that those within each cluster are more closely related to one another than objects assigned to different clusters. \n",
    "* In addition, the goal is sometimes to arrange the clusters into a natural hierarchy -- finding clusters of clusters.\n",
    "* Central to all of the goals of cluster analysis is the notion of the degree of similarity (or dissimilarity) between the individual objects being clustered - this is similar to specifying a cost function in supervised learning.\n",
    "* Dissimilarity matrix - given N objects, an NxN matrics where $X_{ij}$ represents the dissimilarity between objects $i$ and $j$. Has a 0 diagonal. Converting to similarity would simply require passing each value through an inversion function.\n",
    "\n",
    "**Distance Functions**\n",
    "* Most common distance function is squared distance in Euclidean space.\n",
    "* Other alternative distance functions for quantitative variables are absolute distance and correlation (note this is a similarity measurement, not dissimilarity).\n",
    "* Ordinal/ranked variables are often transformed via $\\frac{i−1/2}{M}, i=1,...,M$ in their original ordering. On this scale they are then treated as quantitative variables.\n",
    "* Categorical variables with M levels can be delineated in an MxM binary indicator matrix that is sort of the silohuette of the identity matrix (0 on diagonal, 1 otherwise).\n",
    "\n",
    "**Object Dissimilarity**\n",
    "* Typically, total object similiarity is computed as a weighted average over the individual variable dissimilarities. Note that setting all weights equal doesn't mean each variable contributes equally. The formula is more complex than that and there is a formula for finding equal weights.\n",
    "* It is often more productive to use domain expertise & other judgements to set the weights.\n",
    "* The most common method of incorporating missing values in dissimilarity calculations is to omit these from the calculation.\n",
    "\n",
    "**Clustering Algorithms**\n",
    "* Clustering algorithms fall into three distinct types: combinatorial algorithms, mixture modeling, and mode seeking.\n",
    "* Combinatorial algorithms work directly on the observed data with no direct reference to an underlying probability model. \n",
    "* Mixture modeling supposes that the data is an i.i.d sample from some population described by a probability density function. This density function is characterized by a parameterized model taken to be a mixture of component density functions; each component density describes one of the clusters. This model is then fit to the data by maximum likelihood or corresponding Bayesian approaches. \n",
    "* Mode seekers (\"bump hunters\") take a nonparametric perspective, attempting to directly estimate distinct modes of the probability density function. Observations \"closest\" to each respective mode then define the individual clusters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Combinatorial Clustering**\n",
    "* Assigns K clusters for N data points (K <= N) by optimizing some loss function. For example, minimizing the distance between all points in a cluster.\n",
    "* Unfortunately, such optimization by complete enumeration is feasible only for very small data sets. For example, assigning 19 obervations to 4 optimal clusters can take $10^{10}$ assignments.\n",
    "* To make it feasible, we have to take some shortcuts like assigning an initial partitioning strategy.  Then, within those partitions find the optimal subpartitions.\n",
    "\n",
    "**K-means**\n",
    "* The K-means algorithm is one of the most popular iterative descent clustering methods. It is intended for situations in which all variables are of the quantitative type.\n",
    "* We select K initial means to server as clusters centroids.\n",
    "* Points are added to the nearest cluster and shift the centroids.\n",
    "* The goal is minimize the average dissimilarity from the cluster mean.\n",
    "* One should start the algorithm with many different random choices for the starting means, and choose the solution having smallest value of the objective function.\n",
    "\n",
    "**Vector Quantization**\n",
    "* The K-means clustering algorithm represents a key tool in the apparently unrelated area of image and signal compression, particularly in vector quantization or VQ.\n",
    "* Many portions of an image look the same (blocks of all white pixels for example).  We can perform K means in this context to make a 200x200 pixel image become a 50x50 block image where each block is a k-means mean. This is an example of lossy compression. A lossless algorithm could still take advantage of similarities in pixel colors but would not do any type of averaging or approximation.\n",
    "\n",
    "**K-Medoids Clustering**\n",
    "* Using squared Euclidean distance places the highest influence on the largest distances. This causes the procedure to lack robustness against outliers that produce very large distances.\n",
    "* The only part of the K-means algorithm that assumes squared Euclidean distance is the minimization step.\n",
    "* The algorithm can be generalized for use with arbitrarily defined dissimilarities  by replacing this step by an explicit optimization. In the most common form, centers for each cluster are restricted to be one of the observations assigned to the cluster. This algorithm assumes attribute data, but the approach can also be applied to data described only by proximity matrices\n",
    "\n",
    "**Practical Issues**\n",
    "* Choice of K (number of clusters to use) is usually driven and defined by the problem at hand. (e.g. we have K salespeople to assign N customers).\n",
    "* However, sometimes we don't know K and are trying to figure out how many distinct groupings a data set might have.\n",
    "* Data-based methods for estimating K typically examine the within-cluster dissimilarity as a function of the number of clusters K.\n",
    "* Within-cluster dissimilarity typically decreases with increasing K.\n",
    "\n",
    "**Hierarchical Clustering**\n",
    "* The results of applying K-means or K-medoids clustering algorithms depend on the choice for the number of clusters to be searched and a starting configuration assignment. In contrast, hierarchical clustering methods do not require such specifications.\n",
    "* Instead, they require the user to specify a measure of dissimilarity between (disjoint) groups of observations, based on the pairwise dissimilarities among the observations in the two groups.\n",
    "* As the name suggests, they produce hierarchical representations in which the clusters at each level of the hierarchy are created by merging clusters at the next lower level. \n",
    "* At the lowest level, each cluster contains a single observation. \n",
    "* At the highest level there is only one cluster containing all of the data.\n",
    "* Agglomerative strategies start at the bottom and at each level recursively merge a selected pair of clusters into a single cluster. This produces a grouping at the next higher level with one less cluster. The pair chosen for merging consist of the two groups with the smallest intergroup dissimilarity.\n",
    "* Divisive methods start at the top and at each level recursively split one of the existing clusters at that level into two new clusters. The split is chosen to produce two new groups with the largest between-group dissimilarity. \n",
    "* It is up to the user to decide which level of the hierarchy is most \"natural\".\n",
    "* The dissimilarity $d(G,H)$ between G and H is computed from the set of pairwise observation dissimilarities $d_{ii′}$ where one member of the pair i is in G and the other $i′$ is in H. \n",
    "* Single-linkage dissimilarity just finds the cluster with the minimum pair dissimilarity. Also called nearest neighbor technique. \n",
    "* Complete-linkage / furthest neighbor takes the cluster with the maximum pair dissimilarity.\n",
    "* Group average will take the mean pair dissimilarity between clusters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data:\n",
      "[[ 2.79843356  2.27470477]\n",
      " [ 2.53005911  2.87830499]\n",
      " [ 3.2780683   2.58894425]\n",
      " [ 2.08976026  1.61464356]\n",
      " [ 2.20474396  2.03762395]\n",
      " [ 3.08063244  2.69396499]\n",
      " [ 2.23756629  3.51414617]\n",
      " [ 2.44175516  2.35076855]\n",
      " [ 1.10636767  3.40336943]\n",
      " [ 1.7394638   2.90412719]\n",
      " [ 2.32859942  2.62974661]\n",
      " [ 1.9595157   3.84247679]\n",
      " [ 2.94611902  1.84767565]\n",
      " [ 3.06593047  3.50758204]\n",
      " [ 2.22157249  3.07766279]\n",
      " [ 2.75327041  2.3389151 ]\n",
      " [ 2.5740756   3.03728379]\n",
      " [ 2.74744775  2.04560625]\n",
      " [ 2.29230798  1.65603364]\n",
      " [ 1.94720779  0.92637273]\n",
      " [-1.5499242  -0.54221727]\n",
      " [-2.14698768 -3.65491894]\n",
      " [-1.49629521 -4.32407829]\n",
      " [-2.06423891 -2.55449872]\n",
      " [-3.13062195 -1.62472235]\n",
      " [-3.19846565 -1.01571087]\n",
      " [-1.43537764 -2.53659318]\n",
      " [-4.10437112 -2.92939413]\n",
      " [-1.9032882  -3.30232434]\n",
      " [-2.25802833 -2.47315255]\n",
      " [-2.54420779 -3.16128005]\n",
      " [-4.02327264 -3.49496728]\n",
      " [-2.80627652 -3.19328171]\n",
      " [-2.02584108 -1.97214685]\n",
      " [-3.16590382 -3.21791144]\n",
      " [-2.52018147 -2.84263465]\n",
      " [-3.00658407 -1.69818026]\n",
      " [-2.32021905 -2.68686574]\n",
      " [-3.09470074 -3.24597976]\n",
      " [-5.00754386 -3.23275154]]\n",
      "\n",
      "Labels:\n",
      "[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0 0]\n",
      "\n",
      "Prediction:\n",
      "[1 1]\n",
      "\n",
      "Cluster centers:\n",
      "[[-2.6901165  -2.6851805 ]\n",
      " [ 2.41714486  2.55849766]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Text(0.5, 1.0, 'K-Means Clustering Example')"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAEICAYAAABCnX+uAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nO3de3xU9bnv8c9jiCRVNBaDlUQMXjaVOxp77GFbPWDBW5XqOVa3rdu690GsqHRbfEE5x6LbFhQ9qLU9ltPtC1tsK2Urtlo3YNFdtVoNcjEISLUoCV4iFdQSNcBz/lgTmEzmlsyazKzM9/165cXMWmvW+q1JeOY3z++3nmXujoiIRNcBhW6AiIjkRoFcRCTiFMhFRCJOgVxEJOIUyEVEIk6BXEQk4hTIJZLMbKGZ3VIE7RhkZh+ZWVmh21IIZlZnZm5mfQrdllKmQB5xZrbFzM6Ie36xmb1vZqcl2dbN7N34/3RmVh5bVlQXFFjgWjNrNLO/mVmTmf3azEaEeIzTzawpl324+5vufrC77wmrXe1iH1afxj4o2n/Whn0ciT4F8l7EzP4R+BFwjrv/Z4rN3gfOint+VmxZsbkLuA64Fvgs8HfAUuCcQjYqXg/1Qm+LfVC0/4zqgWNKxCiQ9xJmdiVwBzDR3f+YZtOfA5fFPb8M+FnCvg41s38zs7fMrNnMbmlPHZjZsWa20sy2m9l7ZvaAmVXFvXaLmX3HzNaZ2U4ze9DMKmLrDjezR81sh5n91cyeNrNOf4NmdjxwNXCJu69090/cfZe7P+Duc5Nsf7mZPZOwzM3suNjjs83sFTP7MHY+3zGzg4DHgYFxvd2BZnaAmc0ws9di57jYzD4b2097GuGfzOxNYGViasHMnjKzfzWzZ2PHW25mh8e16zIzeyO27/+d+I0qW2b2NTP7i5kdEnt+lpm9bWbVsed3mdlWM/vAzFaZ2alxr50d+3azKNbGl83s78xsZuzb2VYzmxC3/VNmNsfMXojt75H29yRJu1L+7Uj+KJD3DlcBNwPj3b0hw7ZLgS+ZWZWZHQacCjySsM1CYDdwHDAGmAD8c2ydAXOAgcAJwFHA7ITXXwScCQwGRgKXx5ZfDzQB1cARwHeBZCmd8UCTu7+Q4Vyy9W/Ale7eDxgOrHT3vxF8G9kW19vdBlwDTAJOi53j+wTfcuKdRnDuE1Mc7x+AbwIDgAOB7wCY2VDgx8ClwJHAoUBNd07I3R8E/gjcbWb9Y+f4z+7eEtvkRWA0wbeZXwC/bv9AjfkKwYf6YcBqYBlBPKgh+Fv6ScIhLwOuiLV7N3B3iqYtJPXfjuSLu+snwj/AFuADgmB8QIZtneA/2E+BK4EpwP+LLfPYNkcAnwCVca+7BHgyxT4nAasT2vP1uOe3AffGHt8ca+dxGdo5C3g+wzYLgVtijy8Hnkl2rrHHb8bO95CEbU4n+MCIX7aB4AOx/fmRQBvQB6iL7feYuPXty/rEnj8F/K+49d8C/iP2+Ebgl3HrPgN8CpyR5hw/BnbE/dwft74qdm4vAz/J8H69D4yKPZ4NrIhb9xXgI6As9rxf7Jyq4s5pbtz2Q2PtLos//67+7egnvB/1yHuHqwhyyD81MwMws/VxKYNTE7b/GUEPq1NaBTgaKAfeiqVAdhD0zgbE9nuEmf0q9rX5A2ARcHjCPt6Oe7wLODj2eB7wZ2C5mb1uZjNSnM92ggAalguBs4E3zOw/zeyLabY9Gng47tw3AHsIglS7rRmOl+r8B8a/1t13EZxrOre7e1Xczz/GvX4H8GuCbxl3xL8olj7aEEtv7SDo/cf/nt6Je9wKvOf7B2xbY/8eHLdN/Dm/QfA3kvh7T/u3I/mjQN47vEOQjjiV4Ks77j7M96cMnk7Y/mmCQHkE8EzCuq0EvarD44LHIe4+LLb+BwQ9sBHufgjwdYJ0S0bu/qG7X+/uxwDnAf9iZuOTbPp7oNbM6rPZL/A3gt4tAGb2uYTjvuju5xMElKXA4vZVSfa1FTgrIXhWuHtz/C6zbFeit4DauHZWAv27uS/MbDRBuuOXxKU6Yh/cNxCkuA5z9ypgJ1n+nlI4Ku7xIIJvKe8lbJPpb0fyRIG8l/AgvzseONPM5mfY1gm+Tp8Xexy/7i1gOXCHmR0SG/w71vZPZ+xH8DV8p5nVANOzbaOZnWtmx8W+Newk6OnuTdK+zQQfSL+0YIrggWZWYcHUymS9+LXAMDMbHcsDz4475oFmdqmZHerubQRpqPZjvgP0N7ND4/Z1L/B9Mzs69vpqMzs/23PMYAnwFTP7r2Z2YKyd3QqusfNcRDDO8E2gxsy+FVvdjyBP3QL0MbMbgUNybPvXzWyomX2GIEW2xBOmXGbxtyN5okDei7j7m8A44L+b2ZwM26539/UpVl9GMEj3CkFudQn7Ux03AScSBOLHgIe60MTjgScIPgieA37s7k+m2PZa4B6CgcYdwGvAV4HfJjmXVwmCyxPAZjp/y/gGsCWWCppCMNiIu28k6M2+HksFDCSY9vgbgvTPh8DzwH/pwjmmFHu/rwF+RdA7/wh4l6AXm8oN1nEeeXsveA6w1d3/r7t/QvDN6BYLZvwsA/4DeJUgDfIxmdNBmfycIGf/NlBB8PtJJt3fjuSJJXTIRKSHmNnBBB9Sx7v7XwrdnlTM7Clgkbv/tNBtkeTUIxfpQWb2FTP7jAXz2G8nmHGypbCtkqhTIBfpWecD22I/xwMXJ45TiHSVUisiIhGnHrmISMQVpPTk4Ycf7nV1dYU4tIhIZK1ateo9d69OXF6QQF5XV0dDQ6aSICIiEs/M3ki2XKkVEZGICy2Qm1mZma02s0fD2qeIiGQWZo/8OoICQyIi0oNCyZGbWS3BnVu+D/xLd/bR1tZGU1MTH3/8cRhNkh5WUVFBbW0t5eXlhW6KSMkJa7DzToJqa/1SbWBmk4HJAIMGDeq0vqmpiX79+lFXV0esEqtEhLuzfft2mpqaGDx4cKGbI1Jyck6tmNm5wLvuvirddu6+wN3r3b2+urrT7Bk+/vhj+vfvryAeQWZG//799W1K8mbp6mbGzl3J4BmPMXbuSpaubs78ohISRo98LHCemZ1NUBXtEDNb5O5f7+qOFMSjS787yZelq5uZ+dDLtLYFVXObd7Qy86GXAZg0plt3yut1cu6Ru/tMd6919zrgYoL7IXY5iIuIJDNv2aZ9Qbxda9se5i3bVKAWFR/NI49TVlbG6NGjGTZsGKNGjeKOO+5g795O9z3oYMuWLfziF7/ooRaKlJ5tO1q7tLwUhRrI3f0pdz83zH32pMrKStasWcP69etZsWIFjz/+ODfddFPa1yiQi+TXwKrKLi0vRZHtked78GPAgAEsWLCAe+65B3dny5YtnHrqqZx44omceOKJ/PGPfwRgxowZPP3004wePZr58+en3E5Eumf6xCFUlpd1WFZZXsb0iUMK1KLiU5BaK7nqqcGPY445hj179vDuu+8yYMAAVqxYQUVFBZs3b+aSSy6hoaGBuXPncvvtt/Poo8EFrbt27Uq6nYh0T/v/6XnLNrFtRysDqyqZPnGIBjrjRDKQpxv8yNcvt62tjalTp7JmzRrKysp49dVXc9pORLI3aUyNAncakQzkPTX48frrr1NWVsaAAQO46aabOOKII1i7di179+6loqIi6Wvmz5+f1XYiEr6lq5sL1nMv5LEjmSPvicGPlpYWpkyZwtSpUzEzdu7cyZFHHskBBxzAz3/+c/bsCb4R9OvXjw8//HDf61JtJyL51Z5ybd7RirM/5doTFw8V8tgQ0UCer8GP1tbWfdMPzzjjDCZMmMD3vvc9AL71rW9x//33M2rUKDZu3MhBBx0EwMiRIykrK2PUqFHMnz8/5XYikl+FnG9e6LnukUyt5GvwI13v+fjjj2fdunX7nt96660AlJeXs3Llyg7bJttOJOoKmTrIRiHnmxd6rnskAzlo8EOkJ0XhMvmBVZU0JwmcPTHfvJDHhoimVkSkZxU6dZCNQs43L/Rc98j2yEWk5xQ6dZCNQs43L/RcdwVyEcmo0KmDbBUy5VrIYyu1IiIZFTp1IOmpRy4iGRU6dSDpqUce5+233+biiy/m2GOP5aSTTuLss8/m1VdfZcuWLQwfPrxb+1y4cCHbtm3LuW2PP/449fX1DB06lDFjxnD99dd3az87duzgxz/+cc7tkdIzaUwNz84Yx1/mnsOzM8YpiBcRBfIYd+erX/0qp59+Oq+99hqrVq1izpw5vPPOOznttzuBfPfu3R2eNzY2MnXqVBYtWsQrr7xCQ0MDxx13XLfa051A7u4Z67KLFINSvSVcGPfsrDCzF8xsrZmtN7P0BbzDsm4xzB8Os6uCf9ctzml3Tz75JOXl5UyZMmXfslGjRnHqqad22G7hwoVMnTp13/Nzzz2Xp556ij179nD55ZczfPhwRowYwfz581myZAkNDQ1ceumljB49mtbWVlatWsVpp53GSSedxMSJE3nrrbcAOP3005k2bRr19fXcddddHY552223MWvWLD7/+c8DwQ0wrrrqKiAoJXDhhRdy8sknc/LJJ/Pss88CMHv2bK644gpOP/10jjnmGO6++24gKLv72muvMXr0aKZPnw7AvHnzOPnkkxk5cuS+K1m3bNnCkCFDuOyyyxg+fDhbt27tdH4ixaS7l8n3huAfRo78E2Ccu39kZuXAM2b2uLs/H8K+k1u3GH57LbTFRtF3bg2eA4y8qFu7bGxs5KSTTup2k9asWUNzczONjY1A0POtqqrinnvu4fbbb6e+vp62tjauueYaHnnkEaqrq3nwwQeZNWsW9913HwCffvpp0pK3jY2NKVMp1113Hd/+9rf5+7//e958800mTpzIhg0bANi4cSNPPvkkH374IUOGDOGqq65i7ty5NDY2smbNGgCWL1/O5s2beeGFF3B3zjvvPP7whz8waNAgNm/ezP33388pp5zCqlWrOp2fSDHpTlXUKFzolI2cA7m7O/BR7Gl57Mdz3W9av795fxBv19YaLO9mIM/VMcccw+uvv84111zDOeecw4QJEzpts2nTJhobG/nyl78MBCUBjjzyyH3rv/a1r3X5uE888QSvvPLKvucffPABH30U/DrOOecc+vbtS9++fRkwYEDSNNHy5ctZvnw5Y8aMAeCjjz5i8+bNDBo0iKOPPppTTjkl6/MTKaTuzHUvREnsfAhl1oqZlQGrgOOAH7n7n8LYb0o7m7q2PAvDhg1jyZIlGbfr06dPh3zxxx9/DMBhhx3G2rVrWbZsGffeey+LFy/e19Nu5+4MGzaM5557Lum+UxXYGjZsGKtWrWLUqFGd1u3du5fnn38+abncvn377ntcVlbWKffe3qaZM2dy5ZVXdli+ZcuWDu3J5vxEuiuMOi7dmesehQudshHKYKe773H30UAt8AUz6zTFw8wmm1mDmTW0tLTkdsBDa7u2PAvjxo3jk08+YcGCBfuWrVu3jqeffrrDdnV1daxZs4a9e/eydetWXnjhBQDee+899u7dy4UXXsgtt9zCSy+9BHQscztkyBBaWlr2BfK2tjbWr1+fsW3Tp0/nBz/4wb6bVOzdu5d7770XgAkTJvDDH/5w37btKZNUEsvuTpw4kfvuu29fL765uZl333230+tSnZ9IrsIqAdvVue5LVzdzgFnSdcV2oVMmoc4jd/cdZvYkcCbQmLBuAbAAoL6+PrfUy/gbO+bIAcorg+XdZGY8/PDDTJs2jVtvvZWKigrq6uq48847O2w3duxYBg8ezNChQznhhBM48cQTgSAAfvOb39zXW58zZw4Al19+OVOmTKGyspLnnnuOJUuWcO2117Jz5052797NtGnTGDZsWNq2jRw5kjvvvJNLLrmEXbt2YWace25wj+u7776bq6++mpEjR7J7926+9KUv7QvyyfTv35+xY8cyfPhwzjrrLObNm8eGDRv44he/CMDBBx/MokWLKCvr+B8i1fmJ5Cqs9EZX5rq3f3js8c6hKIoXOpknOZEu7cCsGmiLBfFKYDlwq7s/muo19fX1njiot2HDBk444YTsD7xucZAT39kU9MTH31iw/LgEuvw7FAEGz3gs6aCaAX+Ze05ejjl27sqkaZgyM+64aFTR5sfNbJW71ycuD6NHfiRwfyxPfgCwOF0QD83IixS4RXqBQtRxSZUD3+tetEE8nTBmrawDxoTQFhEpQdMnDukwBRDyn97Ix4eH7tkZk2uaRwpHvzvprkljaphzwQhqqioxoKaqkjkXjMhrEAy7CFih79lZNEWzKioq2L59O/3798dSjCRLcXJ3tm/fnnQKpEg28lUCNlUvOewiYIWej140gby2tpampiZynpooBVFRUUFtbfenf4qELfGqzZM+WMHJS/8n/sh27NBaJo2/kUkzwhlny2Y+ej5TL0UTyMvLyxk8eHChmyEivUR8L/m8A55hbvlP+Yx9GqwMoaxHvEw593yXAiiqHLmISFjie8M39Fm8P4i3ay/rEYJMOfd83/NUgVxEeqX4GSgD7b3kG+VQ1iNepgHbfJcCKJrUiohImOKnNW7zw6lNFsxzKOuRKN2Abb7nyqtHLiK9Unwved7ui2ilb4f1rfTlxWOv6ZG25Puep+qRi0ivtb+XPI4Xf1PHwFW3cSTb2eb9uW33Rax48WjmHNWcsh5LWLNM8n3P05xrrXRHslorIiL5lKq+Sk1VJc/OGNdhWeIsk3ZVleXMPm9YwS7jT1VrRakVESkJXRlwTDbLBGBHa1uPXrGZLQVyESkJqQYWky1PN5skzGmDYVEgF5GS0JUBx0yzSYrtDkIK5CJSErpSnCtZ0I9XbHcQ0qwVESkZ2Rbnat/mpt+u5/1dbR3WFeMdhBTIRaRXyEdRqs8c2If3d7VRZsYed2p6uM54tnIO5GZ2FPAz4AjAgQXufleu+xURyVbYRakS97fHfV9PvNiCOISTI98NXO/uQ4FTgKvNbGgI+xURyUrYRanyXeQqbDkHcnd/y91fij3+ENgAFN9Hloj0WmEXpcp3kauwhTprxczqCO7f+ack6yabWYOZNejmESISpq7MES/E/vIttEBuZgcD/w5Mc/cPEte7+wJ3r3f3+urq6rAOKyISelGqTPtburqZsXNXMnjGY4ydu7LgV3qGMmvFzMoJgvgD7v5QGPsUEclW2EWp0u0v33f76Y6ci2ZZcKfk+4G/uvu0bF6jolkiElVdKb4VtnwWzRoLfAMYZ2ZrYj9nh7BfEZGiU4wDoTmnVtz9GcBCaIuISCjyecf6fN/tpztUa0VEIinVgGN7Drt5RyvO/hx2WAOS+b7bT3foEn0RiZx0A47pLuYJo1ee77v9dIcCuYhETrpg3RM57GyLb/UUpVZEJHLSBeuoXcwTBgVyEYmcdMG6GHPY+aZALiKRky5Yd+UGEr2FcuQiEjmZBhyLLYedbwrkIhJJpRas01FqRUQk4hTIRUQiToFcRCTiFMhFRCJOgVxEJOIUyEVEIk6BXEQk4kIJ5GZ2n5m9a2aNYexPRESyF1aPfCFwZkj7EhGRLgjlyk53/4OZ1YWxLxGRRPm8409v0GOX6JvZZGAywKBBg3rqsCISccV41/pi02ODne6+wN3r3b2+urq6pw4rIhGX7iYSEtCsFREpasV41/pio0AuIkWtFO/401VhTT/8JfAcMMTMmszsn8LYr4hIKd7xp6vCmrVySRj7ERFJVIx3rS82urGEiBQ93UQiPeXIRUQiToFcRCTiFMhFRCJOgVxEJOIUyEVEIk6BXEQk4hTIRUQiToFcRCTiFMhFRCJOgVxEJOIUyEVEIk6BXEQk4hTIRUQiToFcRCTiwrqxxJlmtsnM/mxmM8LYp4iIZCfnQG5mZcCPgLOAocAlZjY01/2KiEh2wuiRfwH4s7u/7u6fAr8Czg9hvyIikoUwAnkNsDXueVNsWQdmNtnMGsysoaWlJYTDiogI9OBgp7svcPd6d6+vrq7uqcOKiPR6YQTyZuCouOe1sWUiItIDwgjkLwLHm9lgMzsQuBj4TQj7FRGRLPTJdQfuvtvMpgLLgDLgPndfn3PLREQkKzkHcgB3/x3wuzD2JSIiXaMrO0VEIk6BXEQk4hTIRUQiToFcRCTiQhnsFMmnpaubmbdsE9t2tDKwqpLpE4cwaUyni4dFSpYCuRS1paubmfnQy7S27QGgeUcrMx96GUDBXCRGqRUpavOWbdoXxNu1tu1h3rJNBWqRSPFRIJeitm1Ha5eWi5QiBXIpagOrKru0XKQUKZBLUZs+cQiV5WUdllWWlzF94pACtUik+GiwU4pa+4CmZq2IpKZALkVv0pgaBW6RNJRaERGJOAVyEZGIUyAXEYm4nAK5mf0PM1tvZnvNrD6sRomISPZyHexsBC4AfhJCWyRLqj0iIvFyCuTuvgHAzMJpjWSk2iMikqjHcuRmNtnMGsysoaWlpacO2+uo9oiIJMrYIzezJ4DPJVk1y90fyfZA7r4AWABQX1/vWbdQOlDtERFJlDGQu/sZPdEQyc7AqkqakwRt1R4RKV2afhgxqj0iIolynX74VTNrAr4IPGZmy8JplqQyaUwNcy4YQU1VJQbUVFUy54IRGugUKWHm3vPp6vr6em9oaOjx44qIRJmZrXL3TtfsKLUiIhJxCuQiIhGnQC4iEnEK5CIiEadALiIScQrkIiIRp0AuIhJxumdnhKmcrYiAAnlkpSpn2/DGX3lyY4uCu0gJUSCPqFTlbB94/k3ar9VVrXKR0qAceUSlKlubWHBBtcpFej8F8ojqStla1SoX6d0UyCMqWTnbVDfcU61ykd5NgTyikpWzvfSUQapVLlKCNNgZYZPG1HQaxKw/+rOakihSYhTIe5lkwb2QNNddJP9yvUPQPDPbaGbrzOxhM6sKq2ESfe1z3Zt3tOLsnw65dHVzoZsm0qvkmiNfAQx395HAq8DM3JskvUWque6aDikSrpwCubsvd/fdsafPA7W5N0l6i1TTHjUdUiRcYc5auQJ4PNVKM5tsZg1m1tDS0hLiYaVYpZr2qOmQIuHKGMjN7Akza0zyc37cNrOA3cADqfbj7gvcvd7d66urq8NpvRS1ZHPdNR1SJHwZZ624+xnp1pvZ5cC5wHh3T7xCXEpY++wUzVoRya+cph+a2ZnADcBp7r4rnCZJb1Js0yFFeqNcc+T3AP2AFWa2xszuDaFNIiLSBTn1yN39uLAaIiIi3aNaKyIiEadALiIScaq1It2mOioixUGBXLol1T1DQbeVE+lpCuTSLenqqEwaU5PX3rq+CYh0pEAu3ZKujko+e+v6JiDSmQY7pVvS1VHJZ9VDVVQU6UyBvJStWwzzh8PsquDfdYuzetnS1c3s+nR3p+XtdVTyWfVQFRVFOlMgL1XrFsNvr4WdWwEP/v3ttRmDeXtq4/1dbR2WV1WWM+eCEUwaU5PXqoeqqCjSmQJ5qfr9zdCW0Ittaw2Wp5EstQFwUN8++3LU+ax6qIqKIp1psLNU7Wzq2vKYbFIb+ax6qIqKIp0pkJeqQ2tjaZUky0k9xW9gVSXNSYJ5Ymojn1UPVVFRpCOlVkrV+BuhPCGvXF4J429Me9NkpTZEio965F3Qqy5EGXlR8O/vbw7SKYfWBsF95EXMm7sy5RS/Z2eMA5TaECkmCuRZ6pUXooy8aH9Aj5MpD67UhkhxySm1Ymb/ambrYjeVWG5mA8NqWLEppQtRNMVPJFpyzZHPc/eR7j4aeBS4MYQ2FaVSuhBFeXCRaMkpkLv7B3FPDwJ67c2XS6mXOmlMDXMuGEFNVSUG1FRV7rvYR0SKT845cjP7PnAZsBP4b2m2mwxMBhg0aFCuh+1x0ycO6ZAjh97dS1UeXCQ6zD19J9rMngA+l2TVLHd/JG67mUCFu38v00Hr6+u9oaGhq20tuF41ayWNUjlPkagxs1XuXt9peaZA3oUDDAJ+5+7DM20b1UBeTLoTbLN5TeLsHAi+eSi1IlJ4qQJ5rrNWjo97ej6wMZf9pbN0dTNj565k8IzHGDt3JUtXN+frUEUv2QU70x5cw5ibl6d8X9Jd5BOvlGbniPQWuebI55rZEGAv8AYwJfcmddYr53DnIFXhqvd3taV8XzLd0addvmfnKG0jEr5cZ61c6O7DY1MQv+Lueekmq5fYUbqgmup9yTZA53N2TrbfCkSkayJRa6WU5nBnI1NQTfa+ZBug8zmHXB/IIvkRiUBeSnO4s5Es2MZL9r5kG6DzOYdcH8gi+RGJWiulNoc7k/agOvs369nR2vFOPanel67U8c7XHPJsS+CKSNeENv2wK7oz/bDYBsmKpT3F0o5saGqjSG7yPo+8K6I+j1wBqfui9MEjUmxSBfJIpFaKTbZT+aQzXfovEr5IDHYWGw3aiUgxUY+8GzRol5zSJiKFoR55N6hed2e62EekcBTIu0H1ujvTxT4ihaPUSjdp0K4jjRuIFI565BIKXX0rUjgK5BIKjRuIFI5SKxKKrpQAEJFwKZBLaDRuIFIYoaRWzOx6M3MzOzyM/YmISPZyDuRmdhQwAXgz9+aIiEhXhdEjnw/cAPR89S0REcn55svnA83uvjaLbSebWYOZNbS0tORyWBERiZNxsNPMngA+l2TVLOC7BGmVjNx9AbAAgjK2XWijiIikkTGQu/sZyZab2QhgMLDWzABqgZfM7Avu/naorRQRkZS6Pf3Q3V8GBrQ/N7MtQL27vxdCu0REJEu6slNEJOJCuyDI3evC2pdIMqp3LpKcruyUSEi8T2p7vXNAwVxKnlIrEgmqdy6SmgK5RILqnYukpkAukaB65yKpKZBLJKjeuUhqGuyUSFC9c5HUFMglMlTvXCQ5pVZERCJOgVxEJOIUyEVEIk6BXEQk4hTIRUQiztx7/h4PZtYCvNHjB86fwwGV781M71Nmeo+yU6rv09HuXp24sCCBvLcxswZ3ry90O4qd3qfM9B5lR+9TR0qtiIhEnAK5iEjEKZCHY0GhGxARep8y03uUHb1PcZQjFxGJOPXIRUQiToFcRCTiFMhDZmbXm5mb2eGFbkuxMbN5ZrbRzNaZ2cNmVlXoNhUTMzvTzDaZ2Z/NbEah21NszOwoM3vSzF4xs/Vmdl2h21QsFMhDZGZHAROANwvdliK1Ahju7iOBV4GZBW5P0TCzMuBHwDZr44UAAAGWSURBVFnAUOASMxta2FYVnd3A9e4+FDgFuFrvUUCBPFzzgRsAjSAn4e7L3X137OnzQG0h21NkvgD82d1fd/dPgV8B5xe4TUXF3d9y95dijz8ENgAqUI8CeWjM7Hyg2d3XFrotEXEF8HihG1FEaoCtcc+bUJBKyczqgDHAnwrbkuKgOwR1gZk9AXwuyapZwHcJ0iolLd175O6PxLaZRfA1+YGebJv0DmZ2MPDvwDR3/6DQ7SkGCuRd4O5nJFtuZiOAwcBaM4MgZfCSmX3B3d/uwSYWXKr3qJ2ZXQ6cC4x3XcQQrxk4Ku55bWyZxDGzcoIg/oC7P1To9hQLXRCUB2a2Bah391KszpaSmZ0J/B/gNHdvKXR7iomZ9SEYAB5PEMBfBP7B3dcXtGFFxIJe0v3AX919WqHbU0yUI5eedA/QD1hhZmvM7N5CN6hYxAaBpwLLCAbxFiuIdzIW+AYwLvb3s8bMzi50o4qBeuQiIhGnHrmISMQpkIuIRJwCuYhIxCmQi4hEnAK5iEjEKZCLiEScArmISMT9f1gm4HPKbksWAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# Generate gaussian noise with 2 distinct means\n",
    "X = np.vstack([np.random.normal([2.5, 2.5], 0.5, [20, 2]), np.random.normal([-2.5, -2.5], 1, [20, 2])])\n",
    "\n",
    "kmeans = KMeans(n_clusters=2, random_state=0).fit(X)\n",
    "\n",
    "print('Data:')\n",
    "print(X)\n",
    "print('')\n",
    "print('Labels:')\n",
    "print(kmeans.labels_)\n",
    "print('')\n",
    "print('Prediction:')\n",
    "print(kmeans.predict([[0, 0], [4, 4]]))\n",
    "print('')\n",
    "print('Cluster centers:')\n",
    "print(kmeans.cluster_centers_)\n",
    "\n",
    "plt.scatter(X[:, 0], X[:, 1])\n",
    "plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1])\n",
    "plt.legend(['Data', 'Cluster Centers'])\n",
    "plt.title('K-Means Clustering Example')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.4 - Self Organizing Maps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* This method can be viewed as a constrained version of K-means clustering, in which the prototypes are encouraged to lie in a one-or-two-dimensional manifold in the feature space.\n",
    "* The prototypes are initially organized to lie in the two-dimensional principal component plane of the data.\n",
    "* The SOM procedure tries to bend the plane so that the prototypes approximate the data points as well as possible. Once the model is fit, the observations can be mapped down onto the two-dimensional grid.\n",
    "* The observations $x_i$ are processed one at a time. We find the closest prototype $m_j$ to $x_i$ in Euclidean distance in $\\mathbb{R}^p$, and then for all neighbors $m_k$ of $m_j$, move $m_k$ toward $x_i$.\n",
    "* The neighbors $m_k$ are defined by a hyper-parameter Euclidean distance neighborhood.\n",
    "* Distance is defined in the space Q1 × Q2 of integer topological coordinates of the prototypes, rather than in the feature space $\\mathbb{R}^p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.5 - Principal Components, Curves and Surfaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Principal Components**\n",
    "* Principal components are a sequence of projections of the data, mutually uncorrelated and ordered in variance.\n",
    "* The principal components of a feature space are the orthogonal vectors describing the space, ordered by variance. We can choose the top $k$ principal components and project the original data into this lower dimensional hyperplane. \n",
    "* Finding the principal components can be done via an SVD decomposition of the centered feature matrix.\n",
    "* Principal components are a useful tool for dimension reduction and compression. \n",
    "* Principal curves generalize the principal component line, providing a smooth one-dimensional curved approximation to  a set of data points in $\\mathbb{R}^p$. A principal surface is more general, providing a curved manifold approximation of dimension 2 or more.\n",
    "\n",
    "**Principal Curves**\n",
    "\n",
    "*Consider an abstract distribution and not real data for the following:*\n",
    "* A curve $f(\\lambda)$ is considered a principal curve if it is the average of all data points that project to it.\n",
    "* Continuous multi-variate distributions have infinitely many prinicpal curves, but we are mainly interested in the smooth ones.\n",
    "* The set of k points that minimize the expected distance from X to its prototypes (defined by the k points) are called the principal points of the distribution. \n",
    "* Principal points are the distributional analogs of centroids found by K-means clustering. \n",
    "* Principal curves can be viewed as $k = \\infty$ principal points, but constrained to lie on a smooth curve.\n",
    "*  Principal surfaces have exactly the same form as principal curves, but are of higher dimension. The mostly commonly used is the two-dimensional principal surface, with coordinate functions $f(\\lambda_1, \\lambda_2)$.\n",
    "\n",
    "**Spectral Clustering**\n",
    "* Traditional clustering methods like K-means use a spherical or elliptical metric to group data points. Hence they will not work well when the clusters are non-convex. \n",
    "* Spectral clustering is a generalization of standard clustering methods, and is designed for these situations.\n",
    "* The starting point is a $N × N$ matrix of pairwise similarities $s_{ii}′ \\geq 0$ between all observation pairs. \n",
    "* We represent the observations in an undirected similarity graph G = ⟨V, E⟩. The N vertices $v_i$ represent the observations, and pairs of vertices are connected by an edge if their similarity is positive (or exceeds some threshold). The edges are weighted by the $s_{ii′}$. \n",
    "* Clustering is now rephrased as a graph-partition problem, where we identify connected components with clusters. We wish to partition the graph, such that edges between different groups have low weight, and within a group have high weight.\n",
    "* Spectral clustering finds the $m$ eigenvectors corresponding to the m smallest eigenvalues of $L$, where $L$ is the graph Laplacian which is defined as $L = G-W$. $G$ is the diagonal matrix representing the degree of each vertex (the sum of weights on edges connected to it) and $W$ is the adjaceny matrix, which is a matrix of edge weights.\n",
    "\n",
    "**Kernel Principal Components**\n",
    "* Spectral clustering is related to kernel principal components, a non-linear version of linear principal components. \n",
    "* Standard linear principal components (PCA) are obtained from the eigenvectors of the covariance matrix, and give directions in which the data have maximal variance.\n",
    "* Kernel PCA expands the scope of PCA, mimicking what we would obtain if we were to expand the features by non-linear transformations, and then apply PCA in this transformed feature space.\n",
    "* Kernel PCA is quite sensitive to the scale and nature of the kernel. \n",
    "\n",
    "**Sparse Principal Components**\n",
    "* We often interpret principal components by examining the direction vectors $v_j$, also known as loadings, to see which variables play a role. Often this interpretation is made easier if the loadings are sparse.\n",
    "* Methods for deriving principal components with sparse loadings are often based on the Lasso technique.\n",
    "* One method solves for principal components subject to the constraint $\\sum_{j=1}^{p} |vj| \\leq t$.\n",
    "* The absolute-value constraint encourages some of the loadings to be zero and hence v to be sparse. \n",
    "* Further sparse principal components are found in the same way, by forcing the kth component to be orthogonal to the first k − 1 components. Unfortunately this problem is not convex and the computations are difficult.\n",
    "* Other methods follow a similar approach of putting a constraint on the eigenvectors/loadings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.6 - Non-negative Matrix Factorization\n",
    "* Non-negative matrix factorization is a recent alternative approach to principal components analysis, in which the data and components are assumed to be non-negative. It is useful for modeling non-negative data such as images.\n",
    "* It is found by maximizing the log-likelihood from a model in which $x_{ij}$ has a Poisson distribution — quite reasonable for positive data.\n",
    "* The $N × p$ data matrix $X$ is approximated by $X ≈ WH$ where $W$ is $N × r$ and $H$ is $r×p$.\n",
    "\n",
    "**Archetypal Analysis**\n",
    "* Approximates data points by prototypes that are themselves linear combinations of data points. In this sense it has a similar flavor to K-means clustering. \n",
    "* Rather than approximating each data point by a single nearby prototype, archetypal analysis approximates each data point by a convex combination of a collection of prototypes. \n",
    "* Again we assume $X ≈ WH$. The N data points are represented by convex combinations of the r archetypes (rows of H).\n",
    "* The use of a convex combination forces the prototypes to lie on the convex hull of the data cloud (on the edge of the boundaries). In this sense, the prototypes are \"pure\", or \"archetypal\".\n",
    "* Convex combinations are linear combinations whose coefficients are > 0 and whose weights sum to 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.7 - Independent Component Analysis and Exploratory Projection Pursuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Factor analysis is a classical technique developed in the statistical literature that aims to identify latent variables -- those that are not directly observed but whose effects can be covered by other variables in a multivariate model (driving forces that may be hard to identify or measure).\n",
    "* In terms of random variables, we can interpret the SVD, or the corresponding principal component analysis (PCA), as an estimate of a latent variable model X = AS.  The correlated $X_j$ are each represented as a linear expansion in the uncorrelated, unit variance variables $S_l$. This is saying that each variable is represented as a linear combination of variables $S_l$ where $S = \\sqrt{N}U$ in the SVD decomposition $X=UDV^T$.\n",
    "* There are many such decompositions, and it is therefore impossible to identify any particular latent variables as unique underlying sources. The classical factor analysis model, developed primarily by researchers in psychometrics, alleviates these problems to some extent.\n",
    "* In classifical factor analysis, let $X = AS + ε$. Here S is a vector of q < p underlying latent variables or factors, A is a p × q matrix of factor loadings, and the $ε_j$ are uncorrelated zero-mean disturbances. The idea is that the latent variables $S_l$ are common sources of variation amongst the $X_j$ , and account for their correlation structure, while the uncorrelated $ε_j$ are unique to each $X_j$ and pick up the remaining unaccounted variation. \n",
    "* Typically the $S_j$ and the $ε_j$ are modeled as Gaussian random variables, and the model is fit by maximum likelihood.\n",
    "\n",
    "**Independent Component Analysis**\n",
    "* The independent component analysis (ICA) model has exactly the same form, except the $S_i$ are assumed to be statistically independent rather than uncorrelated. \n",
    "* Cocktail party problem, where different microphones $X_j$ pick up mixtures of different independent sources $S_l$ (music, speech from different speakers, etc.). ICA is able to perform blind source separation, by exploiting the independence and non-Gaussianity of the original sources.\n",
    "* Many of the popular approaches to ICA are based on entropy. \n",
    "* A well-known result in information theory says that among all random variables with equal variance, Gaussian variables have the maximum entropy.\n",
    "* ICA applied to multivariate data looks for a sequence of orthogonal projections such that the projected data look as far from Gaussian as possible. With pre-whitened data, this amounts to looking for components that are as independent as possible.\n",
    "* ICA starts from essentially a factor analysis solution, and looks for rotations that lead to independent components. From this point of view, ICA is just another factor rotation method.\n",
    "\n",
    "**Exploratory Projection Pursuit**\n",
    "* Exploratory projection pursuit is a graphical exploration technique for visualizing high-dimensional data.\n",
    "* Their view was that most low (one or two-dimensional) projections of high-dimensional data look Gaussian. \n",
    "* Interesting structure, such as clusters or long tails, would be revealed by non-Gaussian projections.\n",
    "\n",
    "**A Direct Approach to ICA**\n",
    "* Independent distributions by definition have a joint density function that is the product of their individual densities.\n",
    "* The authors present an approach that estimates this density directly using generalized additive models."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.8 - Multidimensional Scaling\n",
    "* Both self-organizing maps and principal curves and surfaces map data points in $R^p$ to a lower-dimensional manifold. Multidimensional scaling (MDS) has a similar goal, but approaches the problem in a somewhat different way.\n",
    "* The idea is to find a lower-dimensional representation of the data that preserves the pairwise distances between points as well as possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.9 - Nonlinear Dimension Reduction and Local Multidimensional Scaling\n",
    "* Several methods have been recently proposed for nonlinear dimension reduction, similar in spirit to principal surfaces. \n",
    "* The idea is that the data lie close to an intrinsically low-dimensional nonlinear manifold embedded in a high-dimensional space. \n",
    "* These methods can be thought of as \"flattening\" the manifold, and hence reducing the data to a set of low-dimensional coordinates that represent their relative positions in the manifold. \n",
    "* They are useful for problems where signal-to-noise ratio is very high (e.g., physical systems), and are probably not as useful for observational data with lower signal-to-noise ratios.\n",
    "* Isometric feature mapping (ISOMAP) constructs a graph to approximate the geodesic distance between points along the manifold. \n",
    "* Local linear embedding takes a very different approach, trying to preserve the local affine structure of the high-dimensional data. Each data point is approximated by a linear combination of neighboring points. Then a lower dimensional representation is constructed that best preserves these local approximations.\n",
    "* Local MDS defines a neighborhood using K-nearest neighbors.  It then minimizes the same stress function as in MDS but points that are not neighbors are weighted to be very far apart; such pairs are given a small weight w so that they don’t dominate the overall stress function. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14.10 - The Google PageRank Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Suppose that we have N web pages and wish to rank them in terms of importance.\n",
    "* The PageRank algorithm considers a webpage to be important if many other webpages point to it.\n",
    "* However, the linking webpages that point to a given page are not treated equally: the algorithm also takes into account both the importance (PageRank) of the linking pages and the number of outgoing links that they have. \n",
    "* Linking pages with higher PageRank are given more weight, while pages with more outgoing links are given less weight.\n",
    "* This algorithm is therefore defined recursively."
   ]
  }
 ],
 "metadata": {
  "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}