3e:null 3f:["$","title",null,{"children":"Unsupervised Learning | Jhelum Chakravorty | Observable"}] 45:T4a6,slide` ### Limitations of ${mtex`K`}-means ${mtex`K`}-means often does not do a good job in clustering when there are variations in density, nonspherical shapes of clusetrs and outliers.

**How to evaluate ${mtex`K`}-means results?** * Supervised evaluation: use a pre-classified dataset as a benchmark - Given the knowledge of the ground truth class assignments of the samples, use some metric, e.g., *homogeneity*, *completeness*, *v-score*, to evaluate the goodness of the the clustering (higher score is better) - Python: from **sklearn** import **metrics**; *metrics.homogeneity_score(labels_true, labels_pred)* * Unsupervised evaluation: minimize intra-cluser distance (maximize *cohesiveness*) and maximize inter-clusetr distance (*separation*)

Details: [Cluster Analysis Using K-means Explained](https://codeahoy.com/2017/02/19/cluster-analysis-using-k-means-explained/) `46: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

`47:T658,keypresscontrol= { document.cells = document.getElementsByClassName("observablehq"); document.current=2; document.stopnumber = document.cells.length- 5 //keymap document.onkeyup = function(e) { console.log(e) ; if (e.which === 83){console.log('re -s- tart'); document.current=2 var elmnt = document.cells[document.current] elmnt.scrollIntoView(); } if (e.which === 32| e.which === 39| e.which === 40){console.log('space'); document.current+=1 if (document.current < (document.stopnumber)){ var elmnt=document.cells[document.current]; if (elmnt.innerHTML != '

'){ elmnt.scrollIntoView(); } else { document.stopnumber = document.current; } }else{document.current = document.stopnumber } } if (e.which === 38 | e.which === 37){console.log('back'); document.current-=1 if (document.current <2){document.current = 2} var elmnt = document.cells[document.current] elmnt.scrollIntoView(); } } }48:T8a4,slide = { function slide() { const container = document.createElement("div"); container.className = "slide"; container.appendChild(md.apply(this, arguments)); return container; } function end() { const container = document.createElement("div"); container.className = "end"; return container; } slide.end = end; function iframe(strings) { const container = document.createElement("div"); container.innerHTML="" container.className = "slide"; return container; } slide.iframe=iframe; function html(strings) { const container = document.createElement("div"); container.innerHTML = strings; container.className = "slide slide--html"; return container; } slide.html = html; function htmldark(strings) { const container = document.createElement("div"); container.innerHTML = strings; container.className = "slide slide--html dark"; return container; } slide.htmldark = htmldark; function code(strings) { const container = document.createElement("div"); const pre = container.appendChild(document.createElement("pre")); const code = pre.appendChild(document.createElement("code")); let string = strings[0] + "", i = 0, n = arguments.length; while (++i < n) string += arguments[i] + "" + strings[i]; code.textContent = string.trim(); container.className = "slide slide--code"; return container; } slide.code = code; slide.js = function() { const container = code.apply(this, arguments); const content = container.firstChild.firstChild; content.className = "js hljs javascript"; hl.highlightBlock(content); return container; }; slide.img = function(strings) { const img = new Image; let string = strings[0] + "", i = 0, n = arguments.length; while (++i < n) string += arguments[i] + "" + strings[i]; img.src = string.trim(); img.className = "slide slide--img"; return img; }; return slide; }49:[] 43:{"id":"78d3ac3ed2c28834","slug":"unsupervised-learning","title":"Unsupervised Learning","thumbnail":"f92e04558a887db2fb5d48d932290e8e416cb3b3930b3dfa8513ca34ea2e14c7","access_level":"public","create_time":"$D2020-08-10T17:20:28.511Z","update_time":"$D2020-09-24T13:54:27.750Z","view_time":null,"first_public_time":"$D2020-08-10T17:21:00.694Z","has_unpublished_edits":null,"fork":{"id":"4b4ee5df8d58dd83","slug":"unsupervised-learning","title":"Unsupervised Learning","owner":{"id":"58c635fe0c6a930c","login":"krisrs1128","name":"Kris Sankaran"}},"stars":1,"starred":false,"owner":{"type":"team","id":"f2fc5ebdd7876938","login":"jhelum-ch","name":"Jhelum Chakravorty","avatar_url":"https://avatars-next.observableusercontent.com/e83434a00e17e1552b4c063369c1a25828f14baddcc06570dd0b3dcd14b13b9d","tier":"starter_2024","bio":""},"version":525,"publish_version":525,"role":null,"authored":false,"authors":[{"type":"individual","id":"d5380db8be1a36e9","login":"jhelum-ch","name":"Jhelum Chakravorty","avatar_url":"https://avatars-next.observableusercontent.com/e83434a00e17e1552b4c063369c1a25828f14baddcc06570dd0b3dcd14b13b9d","tier":null,"bio":""}],"members":[{"type":"individual","id":"d5380db8be1a36e9","login":"jhelum-ch","name":"Jhelum Chakravorty","avatar_url":"https://avatars-next.observableusercontent.com/e83434a00e17e1552b4c063369c1a25828f14baddcc06570dd0b3dcd14b13b9d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Unsupervised Learning","cells":[{"id":0,"value":"md`# Unsupervised Learning\n\nIFT6758, Fall 2020\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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"slide`### PCA\n\nWhat is this?\n\n

\n\nCredit for the idea: Prof. Julie Josse\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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_{kj}\\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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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 (although might not be crucial)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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\nHere 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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":510,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"slide`### Hierarchical Clustering\n\nBehold, the cluster dendrogram.\n${chart}\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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\nRef: [Ten quick tips for effective dimensionality reduction](https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1006907)\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":291,"value":"slide`### What to watch out for\n\n* The choice of distance is crucial.\n - Numeric data: e.g., Euclidean, Squared Euclidean, Manhattan, Mahalanobis, Minkowski\n - Text or other non-numeric data: Hamming, Levenshtein \n\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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"slide`### Some final remarks\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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":256,"value":"import {chart} from \"@mbostock/tree-of-life\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":450,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":452,"value":"hl = require(\"@observablehq/highlight.js@1.0.0/highlight.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"slide_style = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"import {mtex_block} from \"@krisrs1128/function-fitting\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":415,"value":"import {mtex} from \"@krisrs1128/function-fitting\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W49","stdlib":"1"}} 44:"$43:body"