class: center, middle, inverse, title-slide .title[ # Clustering ] .subtitle[ ## Part 1a ] .author[ ### Prof. Ryan Weldzius ] .institute[ ### Villanova University ] --- <style type="text/css"> .small .remark-code { /*Change made here*/ font-size: 85% !important; } .tiny .remark-code { /*Change made here*/ font-size: 50% !important; } </style> # Agenda 1. Structure in data 2. "Clustering" 3. Next time: Application --- # Structure -- - Patterns in data -- - Behind everything we've done thus far -- - .blue[Theory Testing:] structure answers research question - .blue[Prediction:] structure improves accuracy -- - A third "camp" in data science: **Learning** --- # Learning -- - No research question, no prediction goal -- - Just want to learn about **structure** of data -- - Existing tools can do it -- - Run 1m regressions - Visualize a thousand variables -- - But these are *slow* -- - This topic: letting **algorithms** learn for you! -- - Today: .red[clustering] --- # Clustering -- - Identify observations that belong to groups -- - Similarities &rarr; group belonging -- - Part of broader set of methods to identify underlying "structure" -- - Today: *k*-means clustering algorithm --- # *k*-means Clustering -- - *k*: number of clusters (i.e., groups) -- - Algorithm assigns each observation to these `\(1\dots k\)` groups -- 1. Choose initial "centroids" at random -- 2. Assign observations to each centroid based on "Euclidean distance" -- 3. Calculate new centroid based on mean of each variable -- 4. Repeat until assignments stabilize -- <center><img src="https://media.tenor.com/eRjjRricmzMAAAAM/krule-john-c-reilly.gif"></center> --- # Euclidean Distance <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-3-1.png" style="display: block; margin: auto;" /> --- # Euclidean Distance <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-4-1.png" style="display: block; margin: auto;" /> --- # Euclidean Distance <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-5-1.png" style="display: block; margin: auto;" /> --- # Euclidean Distance <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-6-1.png" style="display: block; margin: auto;" /> --- # Euclidean Distance <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-7-1.png" style="display: block; margin: auto;" /> --- # Euclidean Distance <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-8-1.png" style="display: block; margin: auto;" /> -- - `\(c^2 = a^2 + b^2\)` &rarr; `\(c = \sqrt{a^2 + b^2}\)` -- - `\(a^2 = (x_2 - x_1)^2 + (y_2 - y_1)^2\)` & `\(b^2 = (x_3 - x_2)^2 + (y_3 - y_2)^2\)` -- - General: `\(\sqrt{\sum_i (q_i - p_i)^2}\)` --- # Centroids - The center of some data <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-9-1.png" style="display: block; margin: auto;" /> --- # Centroids - Initially chosen at random by the algorithm <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-10-1.png" style="display: block; margin: auto;" /> --- # Cluster Assignment - Calculate Euclidean Distance for each observation <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-11-1.png" style="display: block; margin: auto;" /> --- # Cluster Assignment - Calculate Euclidean Distance for each observation <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-12-1.png" style="display: block; margin: auto;" /> --- # Cluster Assignment - Calculate Euclidean Distance for each observation <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-13-1.png" style="display: block; margin: auto;" /> --- # Cluster Assignment - Calculate Euclidean Distance for each observation <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-14-1.png" style="display: block; margin: auto;" /> --- # Cluster Assignment - Calculate Euclidean Distance for each observation <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-15-1.png" style="display: block; margin: auto;" /> --- # Cluster Assignment - Calculate Euclidean Distance for each observation <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-16-1.png" style="display: block; margin: auto;" /> --- # Recalculate Centroids - Set new centroids to mean of `\(x\)` and `\(y\)` among members <img src="14a_ClusteringPart1_files/figure-html/unnamed-chunk-17-1.png" style="display: block; margin: auto;" /> - [A simulation](http://tech.nitoyon.com/en/blog/2013/11/07/k-means/)