31:Tad36,slide` ### Similarity between clusters * The height on the dendrogram gives the similarity between descendants * But what's a good distance between pairs of sets? - Single: Minimum distance between any pair of points - Complete: Maximum distance between any pair of points - Average: Average distance over all pairs of points

`32:[] 2f:{"title":"Unsupervised Learning","cells":[{"id":0,"value":"md`# Unsupervised Learning\n\nIFT6758, Fall 2019\n\nReading: [ISLR](http://faculty.marshall.usc.edu/gareth-james/ISL/ISLR%20Seventh%20Printing.pdf) sections 10.1, 10.2 and [PDS](https://tanthiamhuat.files.wordpress.com/2018/04/pythondatasciencehandbook.pdf) pg. 462 - 476\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"slide`### What is unsupervised learning?\n\n* Supervised learning: Learn some mapping ${mtex`x_i \\to y_i`} \n* Unsupervised learning\n - Usual definition: \"Exploring the data ${mtex`x_i`}\"\n* Less orthodox interpretations\n - Learning with hidden labels (clusters: missing classes)\n - Data compression for human consumption\n - Generation of derived data for human consumption\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":34,"value":"slide`### Common Themes\n\n* Much harder to evaluate\n* Most methods can be categorized as either,\n - Dimensionality reduction: Few features that summarize many\n - Clustering: Few \"prototypes\" that are representative of whole dataset\n* We'll review canonical examples,\n - PCA (dimensionality reduction)\n - K-means and Hierarchical Clustering (clustering)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"slide`### PCA\n\nWhat is this?\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":56,"value":"slide`### PCA\n\nWhat is this?\n\n

\n\nCredit for the idea: Prof. Julie Josse\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"slide`### PCA\n\nIdea: Certain views of high-dimensional data are more informative than others.\n\nCan you find a low-dimensional representation with as much variation as possible?`","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"slide`### PCA\n\nCan you find a low-dimensional representation with as much variation as possible?\n\nTo implement the idea,\n* What will be the candidate family of low-dimensional representations?\n* How will we choose one of the many candidates?\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":66,"value":"slide`### Candidates: Linear Mixings\n\nCan you find a **low-dimensional representation** with as much variation as possible?\n\n* For a representation, consider linear combinations of high-dimensional vectors,\n\n${mtex_block`\n\\begin{aligned}\nz_i &= \\sum_{j = 1}^{p} \\varphi_{1j} x_{ij} \\\\\n&= \\varphi_1^{T}x_i\n\\end{aligned}\n`}\n* ${mtex`\\varphi_1`} is a free parameter. E.g., if ${mtex`\\varphi_{1} = \\left(\\frac{1}{p}, \\dots, \\frac{1}{p}\\right)`}, then we summarize ${mtex`x_i`} by averaging over its coordinates\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":84,"value":"slide`### Selection Criteria: Maximal Variance\n\nCan you find a low-dimensional representation with **as much variation** as possible?\n\n* The ${mtex`z_i`}'s should be as spread out as possible: ${mtex_block`\\text{maximize}_{\\varphi_1} \\frac{1}{n}\\sum_{i = 1}^{n}z_{i}^{2}`}\n - Subject to constraint ${mtex`\\|\\varphi_{1}\\|^2 = 1`}.\n\nSee the example [here](http://setosa.io/ev/principal-component-analysis/). The red arrow is ${mtex`\\varphi_1`} and the points along the 1D axes are the associated ${mtex`z_i`}'s.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":403,"value":"slide`### Selection Criteria: Maximal Variance\n\nCan you find a low-dimensional representation with **as much variation** as possible?\n\n* The ${mtex`z_i`}'s should be as spread out as possible: ${mtex_block`\\text{maximize}_{\\varphi_1} \\frac{1}{n}\\sum_{i = 1}^{n}z_{i}^{2}`}\n - Subject to constraint ${mtex`\\|\\varphi_{1}\\|^2 = 1`}.\n\nSee the example [here](http://setosa.io/ev/principal-component-analysis/). The red arrow is ${mtex`\\varphi_1`} and the points along the 1D axes are the associated ${mtex`z_i`}'s.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"slide`### Second, third, ... PCA directions\n\n* Once you find ${mtex`\\varphi_1`}, you can find a \"second\" direction ${mtex`\\varphi_2`}\n* Found by solving the exact same optimization, but with a new constraint that it's at 90 degrees to the previous directions\n* Interpretation: PCA is finding a new, better coordinate system for your data\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":149,"value":"slide`### Semantics\n\n* The ${mtex`\\varphi_k`} are the PCA \"directions\" or \"components.\"\n* The ${mtex`z_i`} are called \"scores.\"\n - Interpreted as coordinates with respect to the directions ${mtex`\\varphi_k`}.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"slide`### Alternative Interpretation: Linear Approximation\n\n* The first ${mtex`K`} directions in PCA find the best ${mtex`K`}-dimensional linear approximation (using sum of squared error to measure approximation quality).\n* This means it's fair to say ${mtex_block`\\begin{aligned} x_{ij} \\approx \\sum_{k = 1}^{K} z_{ik} \\varphi_{jk}\\end{aligned}`}\n* Or, in matrix notation, ${mtex`x_i \\approx \\Phi z_i`}, where ${mtex`\\Phi`} concatenates the ${mtex`\\varphi_{k}`}'s vertically\n - ${mtex`x_i`} is a mixture of the components ${mtex`\\varphi_k`} with weights ${mtex`z_{ik}`}.\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"slide`### Biplots\n\nSince apparently ISLR is apparently all about breaking bad themed data, we'll practice reading PCA plots using \\`USArrests\\`.\n\n\n* ${mtex`z_{i}`} give the states's coordinates\n* Can interpret components by looking at how variables contribute. Variable ${mtex`j`} is plotted at ${mtex`\\left(\\varphi_{1j}, \\varphi_{2j}\\right)`}.\n - E.g., the second PC mostly captures variation related to urban population\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":421,"value":"slide`### Biplots\n\nArrows come from the ${mtex`\\varphi_{1}`} and ${mtex`\\varphi_{2}`}. The ${mtex`\\left(x, y\\right)`}-coordinate of the arrows comes from viewing these PCs in 2D.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":426,"value":"slide`### Biplots\n\n* The coordinate of ${mtex`x_i`} on the biplot is ${mtex`\\left(z_{i1}, z_{i2}\\right)`}\n* Since ${mtex`x_i \\approx z_{i1}\\varphi_{1} + z_{i2}\\varphi_2`}, they have large values for variables with large loadings in the coordinate directions where ${mtex`x_i`} is farther along\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":435,"value":"slide`### Biplots\n\n* For example, California ${mtex`\\approx -2.5 \\varphi_1 - 1.52 \\varphi_2`} \n* Since ${mtex`\\varphi_1`} puts negative weight on the crimes, California has more than the average # of crimes (${mtex`- \\times - = +`})\n* Since ${mtex`\\varphi_2`} puts negative weight on urban population, California has larger than the average population\n\n

\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":387,"value":"slide`### Explained Variation\n* Amount explained by ${mtex`k^{th}`} component,\n${mtex_block`\n\\frac{\\sum_{i = 1}^{n} \\|z_{ki}\\|^{2}}{\\sum_{i = 1}^{n} \\|x_i\\|^{2}}\n`}\n\n* If no directions are preferred, get ${mtex`\\approx \\frac{1}{p}\\%`} everywhere\n* Exercise: What would the plot below look like if the data were shaped like...\n - a pancake (two long directions, one short one)\n - a cigar (one long direction, two short ones).\n\n

\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"slide`### Things to watch out for\n\n* Even though the method is easy to run, there are lots of potential issues,\n - Variables might be at different scales, and there might be ambiguity about whether to rescale them\n - The directions are only unique up to sign\n* Choosing ${mtex`K`} is tricky (but maybe also not crucial)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":180,"value":"slide` ### Clustering\n\nIdea: Partition the observations, so that those that are similar to each other appear together\n\nLook for homogeneous subgroups in your heterogeneous data.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":183,"value":"slide`### Formalization\n\nA partition ${mtex`C_1, \\dots, C_k`} is a collection of subsets satisfying,\n\n* Each sample is in a subset: ${mtex_block`\\cup_{k = 1}^{K} C_{k} = \\{1, \\dots, n\\}`} \n* Subsets are disjoint: For any pair, ${mtex_block`C_{k} \\cap C_{k^{\\prime}} = \\empty`}\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":367,"value":"slide`### Formalization\n\nA partition ${mtex`C_1, \\dots, C_k`} is a collection of subsets satisfying,\n\n* Each sample is in a subset: ${mtex_block`\\cup_{k = 1}^{K} C_{k} = \\{1, \\dots, n\\}`} \n* Subsets are disjoint: For any pair, ${mtex_block`C_{k} \\cap C_{k^{\\prime}} = \\empty`}\n\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":373,"value":"slide`### Formalization\n\nA partition ${mtex`C_1, \\dots, C_k`} is a collection of subsets satisfying,\n\n* Each sample is in a subset: ${mtex_block`\\cup_{k = 1}^{K} C_{k} = \\{1, \\dots, n\\}`} \n* Subsets are disjoint: For any pair, ${mtex_block`C_{k} \\cap C_{k^{\\prime}} = \\empty`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":376,"value":"slide`### Formalization\n\nA partition ${mtex`C_1, \\dots, C_k`} is a collection of subsets satisfying,\n\n* Each sample is in a subset: ${mtex_block`\\cup_{k = 1}^{K} C_{k} = \\{1, \\dots, n\\}`} \n* Subsets are disjoint: For any pair, ${mtex_block`C_{k} \\cap C_{k^{\\prime}} = \\empty`}\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":193,"value":"slide`### Formalization\n\nWe don't want just any partition, but the one that minimizes within group variation, which we'll call ${mtex`W`}.\n\n${mtex_block`\n\\begin{aligned}\n\\underset{C_{k}}{\\text{minimize}} \\sum_{k = 1}^{K} W\\left(C_k\\right)\n\\end{aligned}\n`}\n\nUsually, we use ${mtex`W\\left(C_k\\right) = \\frac{1}{\\left|C_k\\right|} \\sum_{i, i^\\prime \\in C_k} \\|x_i - x_{i}^{\\prime}\\|^{2}`}.\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":207,"value":"slide`### Algorithm\n\nThis is a combinatorial optimization problem, and finding the global optimum is computationally challenging.\n\n*However* the following algorithm usually finds good local optima,\n\n1. Arbitrarily assign each ${mtex`x_i`} to one of the clusters, ${mtex`C_1, \\dots, C_K`}.\n2. Iterate until convergence,\n\n a. Compute the mean ${mtex`\\bar{x}_k`} of the points in ${mtex`C_k`}.\n\n b. Reassign the points ${mtex`x_i`}, so they are put in the cluster whose \n centroid they are closest to.\n\nThis is a nice [demo](http://tech.nitoyon.com/en/blog/2013/11/07/k-means/). The procedure reduces the criterion under study at each step, which means we will converge to a local optimum.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":229,"value":"slide` ### Hierarchical Clustering\n\n* ${mtex`K`} controls the \"magnification\" at which we do the clustering.\n* What if we could do the clustering at many different scales, all at once?`","pinned":false,"hidden":false,"mode":"ojs"},{"id":232,"value":"slide`### Hierarchical Clustering\n\nBehold, the cluster dendrogram.\n${chart}\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"slide`### Interpretation\n\n* Samples which are similar to each other are put on the same subtree.\n* Pairs of samples that are very similar to one another share very recent common ancestors\n - Beware: Samples can be close by at the leaves without being close in the subtree sense\n* You can get a standard clustering by \"cutting\" tree at some horizontal level\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":354,"value":"slide`### That's cool, how do I make it?\n\n* These trees are informative. We'd like an automated procedure for creating them.\n\na. Initialize: Associate each point with a cluster ${mtex`C_i := \\{x_i\\}`}\nb. Iterate until only one cluster: Look at all pairs of clusters. Merge the pair ${mtex`C_k, C_{k^{\\prime}}`} which are the most similar. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":357,"value":"slide`### That's cool, how do I make it?\n\n* These trees are informative. We'd like an automated procedure for creating them.\n\na. Initialize: Associate each point with a cluster ${mtex`C_i := \\{x_i\\}`}\nb. Iterate until only one cluster: Look at all pairs of clusters. Merge the pair ${mtex`C_k, C_{k^{\\prime}}`} which are the most similar. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":358,"value":"slide`### That's cool, how do I make it?\n\n* These trees are informative. We'd like an automated procedure for creating them.\n\na. Initialize: Associate each point with a cluster ${mtex`C_i := \\{x_i\\}`}\nb. Iterate until only one cluster: Look at all pairs of clusters. Merge the pair ${mtex`C_k, C_{k^{\\prime}}`} which are the most similar. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":363,"value":"slide`### That's cool, how do I make it?\n\n* These trees are informative. We'd like an automated procedure for creating them.\n\na. Initialize: Associate each point with a cluster ${mtex`C_i := \\{x_i\\}`}\nb. Iterate until only one cluster: Look at all pairs of clusters. Merge the pair ${mtex`C_k, C_{k^{\\prime}}`} which are the most similar. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":351,"value":"slide`### That's cool, how do I make it?\n\n* These trees are informative. We'd like an automated procedure for creating them.\n\na. Initialize: Associate each point with a cluster ${mtex`C_i := \\{x_i\\}`}\nb. Iterate until only one cluster: Look at all pairs of clusters. Merge the pair ${mtex`C_k, C_{k^{\\prime}}`} which are the most similar. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":226,"value":"slide`### That's cool, how do I make it?\n\n* These trees are informative. We'd like an automated procedure for creating them.\n\na. Initialize: Associate each point with a cluster ${mtex`C_i := \\{x_i\\}`}\nb. Iterate until only one cluster: Look at all pairs of clusters. Merge the pair ${mtex`C_k, C_{k^{\\prime}}`} which are the most similar. \n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":331,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":337,"value":"slide` ### Similarity between clusters\n\n* The distance between the clusters at any iteration can be visualized on the tree\n* Merges lower on the tree --> Smaller intercluster distance\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":342,"value":"slide` ### Similarity between clusters\n\n* The distance between the clusters at any iteration can be visualized on the tree\n* Merges lower on the tree --> Smaller intercluster distance\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":287,"value":"slide`### What to watch out for\n\n* Do you even have clusters?\n\n

\n\nFrom [Ten quick tips for effective dimensionality reduction](https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1006907)\n\nFor interesting middle ground, consider mixed membership models.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"slide`### What to watch out for\n\n* The choice of distance is crucial. \n* Don't try to find a \"perfect\" distance. Try many, and assess the sensitivity of your findings.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":304,"value":"slide` ### What to watch out for\n\nOutliers, nonspherical shapes, and variations in density will mess you up, if you just use ${mtex`K`}-means.\n\n

\n\nFrom [Cluster Analysis Using K-means Explained](https://codeahoy.com/2017/02/19/cluster-analysis-using-k-means-explained/)\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"slide`### Rant\n\nUnsupervised learning is useful for more than \"exploring your data\"\n\nWe are both \"summarizing\" data and [_creating more of it_](https://simplystatistics.org/2019/04/17/tukey-design-thinking-and-better-questions/)\n * The centroids in a clustering are new data, which help us understand the original data\n\n\nThese methods are critical submodules in [removal of batch effects](https://www.ncbi.nlm.nih.gov/pubmed/22257669), [interpretation of deep networks](https://arxiv.org/abs/1706.05806), [anomaly detection](https://docs.microsoft.com/en-us/azure/machine-learning/studio-module-reference/pca-based-anomaly-detection), [regularized regression](https://en.wikipedia.org/wiki/Principal_component_regression) and much much more.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"import {chart} from \"@mbostock/tree-of-life\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"import {slide} from \"@mbostock/slide\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"slide_style = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"import {mtex_block} from \"@krisrs1128/function-fitting\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":415,"value":"import {mtex} from \"@krisrs1128/function-fitting\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":319,"value":"slide` ### Extra Material\n\n\n* The relationship between PCA and the covariance matrix\n${mtex_block`\n\\begin{aligned}\n\\frac{1}{n} \\sum_{i = 1}^{n} \\left(\\varphi_{1}^{T}x_{i}\\right)^{2} &= \\frac{1}{n} \\sum_{i = 1}^{n} \\left(\\varphi_{1}^{T}x_i\\right) \\left(x_{i}^{T}\\varphi_{1}\\right) \\\\\n&= \\varphi_{1}^{T} \\left(\\frac{1}{n} \\sum_{i = 1}^{n} x_{i}x_{i}^{T} \\right)\\varphi_{1} \\\\\n&= \\varphi_{1}^{T} \\hat{\\Sigma} \\varphi_{1}\n\\end{aligned}\n`}\n`","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}