---
title: "Cluster Analysis in R"
author: "Joschka Schwarz"
---

```{r}
#| include: false
source(here::here("R/setup-ggplot2-tie.R"))
options(dplyr.summarise.inform = FALSE)
```

Cluster analysis is a powerful toolkit in the data science workbench. It is used to find groups of observations (clusters) that share similar characteristics. These similarities can inform all kinds of business decisions; for example, in marketing, it is used to identify distinct groups of customers for which advertisements can be tailored. In this course, you will learn about two commonly used clustering methods -  hierarchical clustering and k-means clustering. You won't just learn how to use these methods, you'll build a <strong> strong intuition</strong> for how they work and how to interpret their results. You'll develop this intuition by exploring three different datasets&#58; soccer player positions, wholesale customer spending data, and longitudinal occupational wage data.

# Calculating distance between observations

Cluster analysis seeks to find groups of observations that are similar to one another, but the identified groups are different from each other. This similarity/difference is captured by the metric called distance. In this chapter, you will learn how to calculate the distance between observations for both continuous and categorical features. You will also develop an intuition for how the scales of your features can affect distance.

## What is cluster analysis?

Theory. Coming soon ...


**1. What is cluster analysis?**

Hi, my name is Dima and I am very excited to have you join me in learning all about cluster analysis in R. Cluster analysis is a form of data exploration, and the key to harnessing its power lies in understanding how it works. So, in this course you won't just learn the tools necessary to perform cluster analysis - that's the easy part - I will work with you to build the intuition behind the underlying methods. But, before we get to the how, let's take a moment to discuss, what is clustering?

**2. What is clustering?**

No matter whether you are working with medical data,

**3. What is clustering?**

retail data,

**4. What is clustering?**

or sports data, as a data scientist you are often presented with a bunch of data that you need to make sense of.

**5. What is clustering?**

To understand what clustering is, let's put aside the details of our data and instead focus on the toy example

**6. What is clustering?**

where the data is represented as a matrix containing entries of card suits.

**7. What is clustering?**

To look at it another way, this matrix is composed of rows containing our observations and columns that tell us something that we measured across these observations.We will refer to these columns as the features of our observations. In cluster analysis we are interested in grouping our observations such that all members of a group are similar to one another and at the same time they are distinctly different from all members outside of this group.Imagine in this example we performed cluster analysis to find which observations are similar to one another based on what suit appears in each column.

**8. What is clustering?**

In this case we identified three groups and colored the observations accordingly.To better see these pattens, lets re-organize our observation into their respective colored clusters.

**9. What is clustering?**

Here we can start to see clear patterns that emerge. Fundamentally, this is how cluster analysis works.

**10. What is clustering?**

Or to put it another way, cluster analysis is a form of exploratory data analysis where observations are divided into meaningful groups that share common characteristics amongst each other. So what are the steps involved in performing cluster analysis?

**11. The flow of cluster analysis**

Well, first, you must make sure that your data is ready for clustering, meaning that your data does not have any missing values and that your features are on similar scales.

**12. The flow of cluster analysis**

Next, you must decide on what metric is appropriate to capture the similarity between your observations using the features that you have.

**13. The flow of cluster analysis**

Once you have calculated this you can use a clustering method to group your observations based on how similar they are to each other into clusters.

**14. The flow of cluster analysis**

But, most importantly you will need to analyze the output of these clusters to determine whether they provide any meaningful insight into your data. This often requires a deep understanding of the problem and the data that you are working with.

**15. The flow of cluster analysis**

As you can see in this flow chart, the analysis you perform on these clusters may require you to iterate on the clustering steps until you converge on a meaningful grouping of your data.

**16. Structure of this course**

The first three chapters of this course will help you unpack this process.In this chapter you will gain a deeper understanding of what it means for two observation to be similar - or more specifically ,dissimilar. You will also learn why the features of your data need to be comparable to one another.

**17. Structure of this course**

In chapters two and three you will learn how to use two commonly used clustering methods: hierarchical clustering and k-means clustering.At the end of these chapters and in chapter four you will work through two case studies where clustering analysis provides a unique perspective into the underlying data.

**18. Let's learn!**

So, let's begin!

## When to cluster?

> *Question*
> ---
> **In which of these scenarios would clustering methods likely be appropriate?**  
> <br>
> 1) Using consumer behavior data to identify distinct segments within a market. <br>
> 2) Predicting whether a given user will click on an ad.<br>
> 3) Identifying distinct groups of stocks that follow similar trading patterns.<br>
> 4) Modeling &amp; predicting GDP growth.<br>
> <br>
> ⬜ 1<br>
> ⬜ 2<br>
> ⬜ 4<br>
> ✅ 1 &amp; 3<br>
> ⬜ 2 &amp; 4<br>

That is correct, market segmentation and pattern grouping are both good examples where clustering is appropriate.

Coincidentally, you will get the chance to work on both of these types of problems in this course.

## Distance between two observations

Theory. Coming soon ...


**1. Distance between two observations**

Let's begin by focusing on the question that is fundamental to all clustering analyses: How similar are two observations?

**2. Distance vs Similarity**

Or from another perspective, how dissimilar are they?

**3. Distance vs Similarity**

You see, most clustering methods measure similarity between observations using a dissmilarity metric, often referred to as the distance.These two concepts are just two sides of the same coin.If two observations have a large distance then they are less similar to one another. Likewise, if their distance value is small, then they are more similar.Naturally, we should first develop a keen intuition by what is meant by distance.

**4. Distance between two players**

So, let's work with the scenario of players on a soccer field.

**5. Distance between two players**

In this image you see the positions of two players.How far apart are they? To answer this question we first need their coordinates.

**6. Distance between two players**

Here the blue player is positioned in the center of the field, which we will refer to as 0, 0. While the red player has a position of 12 and 9 - or twelve feet to the right of center and 9 feet up.

**7. Distance between two players**

The players in this case are our observations and their X and Y coordinates are the features of these observations. We can use these features to calculate the distance between these two players.In this case we will use a distance measurement you're likely familiar with.

**8. Distance between two players**

Euclidean distance.

**9. Distance between two players**

Which is simply the hypotenuse of the triangle that is formed by the differences in the x and y coordinates of these players.

**10. Distance between two players**

The familiar formula to calculate this is shown here.

**11. Distance between two players**

Which if we plug in our values of x and y for both players we arrive at the euclidean distance between them.

**12. Distance between two players**

Which in this case is 15.This is the fundamental idea for calculating a measure of dissimilarity between the blue and red players.

**13. dist() function**

To do this in R, we use the dist function to calculate the euclidean distance between our observations. The function simply requires a dataframe or matrix containing your observations and features. In this case, we are working with the dataframe two players. The method by which the distance is calculated is provided by the method parameter. In this case we are using euclidean distance and specify it accordingly.As in our manual calculation we see that the distance between the red and blue players is 15.

**14. More than 2 observations**

This function becomes indespensable if we have more than 2 observations. In this case if we wanted to know the distance between 3 players we would measure the distance between the players two at a time. Running this through the dist function we see that the distance between players red and blue is 15 as before, but we also have measurements between green and blue as well as green and red. In this case, green and red have the smallest distance and hence are closest to one another.The dist function would work just as well if we have more features to use for calculating the distance.

**15. Let's practice!**

Now, Let's put what you've just learned into practice in the upcoming exercises.

## Calculate & plot the distance between two players

You've obtained the coordinates relative to the center of the field for two players in a soccer match and would like to calculate the distance between them.

In this exercise you will plot the positions of the 2 players and manually calculate the distance between them by using the Euclidean distance formula.

**Steps**

1. Plot their positions from the `two_players` data frame using `ggplot`. 
2. Extract the positions of the players into two data frames `player1` and `player2`.
3. Calculate the distance between player1 and player2 by using the Euclidean distance formula 

$$\\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$.

```{r}
# Load package
library(tibble)
library(ggplot2)

# Create two_players
two_players <- tibble(x = c(5,15),
                      y = c(4,10))

# Plot the positions of the players
ggplot(two_players, aes(x = x, y = y)) + 
  geom_point(size = 3) +
  # Assuming a 40x60 field
  lims(x = c(-30,30), y = c(-20, 20)) +
  theme_bw()
  
# Split the players data frame into two observations 
player1 <- two_players[1, ]
player2 <- two_players[2, ]

# Calculate and print their distance using the Euclidean Distance formula
player_distance <- sqrt( (player1$x - player2$x)^2 + (player1$y - player2$y)^2 )
player_distance
```

Excellent work! Using the formula is a great way to learn how distance is measured between two observations.

## Using the dist() function

Using the Euclidean formula manually may be practical for 2 observations but can get more complicated rather quickly when measuring the distance between many observations.

The `dist()` function simplifies this process by calculating distances between our observations (rows) using their features (columns). In this case the observations are the player positions and the dimensions are their x and y coordinates.

*Note: The default distance calculation for the `dist()` function is Euclidean distance*

**Steps**

1. Calculate the distance between two players using the `dist()` function for the data frame `two_players`
2. Calculate the distance between three players for the data frame `three_players`

```{r}
# Calculate the Distance Between two_players
dist_two_players <- dist(two_players)
dist_two_players

# Calculate the Distance Between three_players
three_players <- two_players |> 
                  add_row(x = 0, y = 20)

dist_three_players <- dist(three_players)
dist_three_players
```

The dist() function makes life easier when working with many dimensions and observations.

## Who are the closest players?

You are given the data frame containing the positions of 4 players on a soccer field. 

This data is preloaded as `four_players` in your environment and is displayed below. 

| Player|  x|  y|
|------:|--:|--:|
|      1|  5|  4|
|      2| 15| 10|
|      3|  0| 20|
|      4| -5|  5|

> *Question*
> ---
> **Which two players are closest to one another?**<br>
> <br>
> ⬜ 1 & 2<br>
> ⬜ 1 & 3<br>
> ✅ 1 & 4<br>
> ⬜ 2 & 3<br>
> ⬜ 2 & 4<br>
> ⬜ 3 & 4<br>
> ⬜ Not enough information to decide<br>

That is correct! Players 1 and 4 are the closest to one another.

## The importance of scale

Theory. Coming soon ...


**1. The importance of scale**

When calculating the distance between two players on a soccer field, you used two features, x and y. Both of these features are the coordinates of the players and both are measured in the same manner. Because of this, they are comparable to one another and can be used together to calculate the euclidean distance between the players. But, what happens when the features aren't measured in the same manner or to put it another way, when the values of these features aren't comparable to one another?To answer this question let's walk through an example.

**2. Distance between individuals**

Imagine you are provided with a dataset that contains the heights and weights for a large number of men in the United States. The height feature is measured in feet and the weight feature in pounds. You are interested in calculating the distance between these individuals.Let us start by comparing observations one and two.

**3. Distance between individuals**

Both men are the same height, six feet. But they differ slightly in weight. In this case the difference is two pounds.

**4. Distance between individuals**

If we calculated the euclidean distance between them we would get a value of two. Now let's look at observations one and three.

**5. Distance between individuals**

In this comparison, the weights are the same, but the height is different by two feet. If we calculate the distance once more...

**6. Distance between individuals**

...you guessed it. It's also two.

**7. Distance between individuals**

The distances between both pairs are identical.If we saw these three men standing side by side, would you really believe that observation one is just as similar to three as it is to two. Of course not.Then why are their distances the same? This happens because these features are on different scales. Meaning they have different averages and different expected variability. While in these comparisons these features only vary by a magnitude of two, we intuitively know that a change in two pounds is very different than a change of two feet.So how can we adjust these features to calculate a distance that better aligns with our expectations?

**8. Scaling our features**

To do this we need to convert our features to be on a similar scale with one another.There are various methods for doing this, but for this course we will use the method called standardization.This entails updating each measurement for a feature by subtracting the average value of that feature and then dividing by its standard deviation. Doing this across our features places them on a similar scale where each feature has a mean of zero and a standard deviation of one.

**9. Distance between individuals**

Going back to the previous scenario, we can use the mean and standard deviation of the height and weight features to standardize the values for our three observations. Now, if we calculate the euclidean distances between them...

**10. Distance between individuals**

Voila, the values make sense! They agree with our intuition. One and three are much less similar to one another than one and two.

**11. scale() function**

In R we can use the scale function to standardize height and weight to the same scale.If height_weight is our matrix of observations, similar to what we've just seen. Using the scale function with the default parameters will normalize each feature column to a mean of 0 and a variance of 1.

**12. Let's practice!**

In the next exercise you will have a chance to further explore how scales can affect your ability to interpret the distance value.

## Effects of scale

You have learned that when a variable is on a larger scale than other variables in your data it may disproportionately influence the resulting distance calculated between your observations. Lets see this in action by observing a sample of data from the `trees` data set. 

You will leverage the `scale()` function which by default centers & scales our column features.

Our variables are the following: 

* **Girth** - tree diameter in inches
* **Height**  - tree height in inches

**Steps**

1. Calculate the distance matrix for the data frame `three_trees` and store it as `dist_trees`
2. Create a new variable `scaled_three_trees` where the `three_trees` data is centered & scaled 
3. Calculate and print the distance matrix for `scaled_three_trees` and store this as `dist_scaled_trees`
4. Output both `dist_trees` and `dist_scaled_trees` matrices and observe the change of which observations have the smallest distance between the two matrices *(hint: they have changed)*

```{r}
three_trees <- tibble(Girth  = c(8.3, 8.6, 10.5),
                      Height = c(840, 780, 864))
                  
# Calculate distance for three_trees 
dist_trees <- dist(three_trees)

# Scale three trees & calculate the distance  
scaled_three_trees <- scale(three_trees)
dist_scaled_trees  <- dist(scaled_three_trees)

# Output the results of both Matrices
print('Without Scaling')
dist_trees

print('With Scaling')
dist_scaled_trees
```

Notice that before scaling observations 1 & 3 were the closest but after scaling observations 1 & 2 turn out to have the smallest distance.

## When to scale data?

> *Question*
> ---
> Below are examples of datasets and their corresponding features.<br>
> <br>
> In which of these examples would scaling **not** be necessary?<br>
> <br>
> ⬜ Taxi Trips - `tip earned ($)`, `distance traveled (km)`.<br>
> ⬜ Health Measurements of Individuals - `height (meters)`, `weight (grams)`, `body fat percentage (%)`.<br>
> ⬜ Student Attributes - `average test score (1-100)`, `distance from school (km)`, `annual household income ($)`.<br>
> ⬜ Salespeople Commissions - `total yearly commision ($)`, `number of trips taken`.<br>
> ✅ None of the above, they all should be scaled when measuring distance.<br>

Correct! In all of these cases it would be a good idea to scale your features.

## Measuring distance for categorical data

Theory. Coming soon ...


**1. Measuring distance for categorical data**

So far you have exclusively worked with one type distance metric, the euclidean distance. This is a commonly used metric and is a great starting point when working with data that is continuous. But what happens if the data you have isn't continuous but is categorical?

**2. Binary data**

Let's start with the most basic case of categorical features, those that are binary, meaning that the values can only be one of two possiblities. Here you are presented with survey data, let's call it survey a. The participants of this survey were asked whether they enjoy drinking various types of alcoholic beverages. Since they can only answer yes or no we can code this binary response as TRUE or FALSE.We would be interested to learn which participants are similar to one another based on their responses. To calculate this we will use the similarity score called the Jaccard Index.

**3. Jaccard index**

This measure of similarity captures the ratio between the intersection of A and B to the union of A and B.Or more intuitively the ratio between the number of times the features of both observations are TRUE to the number of times they are ever TRUE.So going back to the previous example.

**4. Calculating Jaccard distance**

Let us calculate the Jaccard similarity for two observations one and two. They only agree in one category, beer, so for the intersection we get the value of one. While the number of categories these observations are ever true, or the union, is four.Dividing the intersection by the union we get the Jaccard similarity value of 0-point-25.But what about the distance. Well remember that distance is 1 - similarity, so in this case the distance is just 0-point-75.

**5. Calculating Jaccard distance in R**

To learn how to do this in R lets start with a subset of our data containing three observations, called survey a.In order to calculate the Jaccard distance between all three observations you just need to specify that the distance method to use in the dist() function is binary.You can see that just like our manual calculation earlier, observations 1 and 2 have a distance of 0-point-75.Now let's expand this idea to a broader case of categorical data where we have features represented by more than two categories.

**6. More than two categories**

For survey b, we have gathered the favorite color and sport for our participants. For color their choices were red blue and green and for sport the decision was between soccer and hockey. To calculate the distance between these observations we need to represent the presence or absence of each category in a process known as dummification. Essentially we consider each feature-value pair and encode its presence or absence as a 1 or 0, which is equivalent to a TRUE or FALSE. Take a look at observation one whose favorite color was red and favorite sport is soccer. After we dummify our data, shown in the table on the right, this observation now has a value of zero for every dummified feature except for the color red and the sport soccer where the value is one.Once our data is dummified, its just a matter or calculating the Jaccard distance between the observations.

**7. Dummification in R**

To perform this preliminary step in R, we would use the dummy-dot-data-dot-frame function from the dummy library. So long as your categorical values are encoded as factors this function will convert them into binary feature value representations.

**8. Generalizing categorical distance in R**

We can leverage this to calculate the distance for our data. In this case we can see that observations 2 and 3, 1 and 4 and 3 and 4 all have a comparable distance, to one another. Which makes sense if you look back at the original data.

**9. Let's practice!**

Now you have the tools to handle both continuous and categorical data types. Let's practice what you've learned.

## Calculating distance between categorical variables

In this exercise you will explore how to calculate binary (Jaccard) distances. 
In order to calculate distances we will first have to dummify our categories using the `dummy.data.frame()` from the library `dummies`

You will use a small collection of survey observations stored in the data frame `job_survey` with the following columns: 

* **job_satisfaction** Possible options: "Hi", "Mid", "Low"
* **is_happy** Possible options: "Yes", "No"

**Steps**

1. Create a dummified data frame `dummy_survey` 
2. Generate a Jaccard distance matrix for the dummified survey data `dist_survey` using  the `dist()` function using the parameter `method = 'binary'`
3. Print the original data and the distance matrix\nNote the observations with a distance of 0 in the original data (1, 2, and 4)
4. Note the observations with a distance of 0 in the original data (1, 2, and 4)

DUMMIES DOES NOT EXIST ON CRAN ANYMORE


```{r}
#| eval: false
# Data
job_survey <- data.frame( # Does not work with tibble
  
  job_satisfaction = c(rep("Hi", 4), "Mid"),
  is_happy         = c(rep("No", 3), "Yes", "No")
  
)

# Load package
library(dummies)

# Dummify the Survey Data
dummy_survey <- dummy.data.frame(job_survey)

# Calculate the Distance
dist_survey <- dist(dummy_survey, method = 'binary')

# Print the Original Data
job_survey

# Print the Distance Matrix
dist_survey
```

Great work! <br> Notice that this distance metric successfully captured that observations 1 and 2 are identical (distance of 0)

## The closest observation to a pair

Below you see a pre-calculated distance matrix between four players on a soccer field. You can clearly see that players **1** &amp; **4** are the closest to one another with a Euclidean distance value of <font color="red">10</font>.

|   |    1|    2|    3|
|--:|----:|----:|----:|
|  2| 11.7|     |     |
|  3| 16.8| 18.0|     |
|  4| 10.0| 20.6| 15.8|

> *Question*
> ---
> **If 1 and 4 are the closest players among the four, which player is closest to players *1* and *4*?**<br>
> <br>
> ⬜ Clearly its player 2!<br>
> ⬜ No! Player 3 makes more sense.<br>
> ✅ Are you kidding me? There isn't enough information to decide.<br>

Great job! We clearly don't have enough information to make this decision without knowing how we compare one observation to a pair of observations. 

The decision required is known as the **linkage method** and which you will learn about in the next chapter!

# 2. Hierarchical clustering

This chapter will help you answer the last question from chapter 1 - how do you find groups of similar observations (clusters) in your data using the distances that you have calculated? You will learn about the fundamental principles of hierarchical clustering - the linkage criteria and the dendrogram plot - and how both are used to build clusters. You will also explore data from a  wholesale distributor in order to perform market segmentation of clients using their spending habits.

## Comparing more than two observations

Theory. Coming soon ...


**1. Comparing more than two observations**

At the end of chapter 1 you were asked to review a question that you may not have known how to answer. Let's start by revisiting this question.

**2. The closest observation to a pair**

You were presented with a distance matrix that contained the euclidean distances between four soccer players. You know that the closest two players are 1 and 4 with a distance value of 10.In order to cluster more than two observations together you need to determine which of these statements are true.Is observation 2 closest to the newly formed group 1, 4?Or is it observation 3?

**3. Linkage criteria: complete**

To answer this question you must decide on how to measure the distance from group 1-4 to these observations. One approach we can take is to measure the maximum distance of each observation to the two members of the group. To calculate this aggregated distance between observation two and group 1-4 we would get take the larger of the two distances from 2 to 1 and 2 to 4. The distance from 2 to 1 is 11-point-7 and the distance from 2 to 4 is 20-point-6. The larger of the two values is of course 20-point-6 and hence is our maximum distance.We can apply the same logic when comparing observation 3. Resulting in a maximum distance of 16-point-8.Using this approach we can say that based on the maximum distance, observation three is closer to group 1-4.

**4. Hierarchical clustering**

Hierarchical clustering is just a continuation of this approach. This clustering method iteratively groups the observations based on their pairwise distances until every observation is linked into one large group.The decision of how to select the closest observation to an existing group is called the linkage criteria. In the previous example we decided that observation three was the closest based on the maximum distance between it and group 1-4. The approach we used is formally called the complete linkage criteria.

**5. Grouping with linkage &amp; distance**

Let's see the hierarchical clustering method in action using a visual representation.

**6. Grouping with linkage &amp; distance**

The distances between the four players have already been calculated and are shown.

**7. Grouping with linkage &amp; distance**

We know that players 1 and 4 have the shortest distance and will be grouped first.

**8. Grouping with linkage &amp; distance**

We are now presented with three options: add player 2 to group 1-4, add player 3 to group 1-4 or start a new group for players 2 and 3. The decision will be made based on which option results in the smallest distance.

**9. Grouping with linkage &amp; distance**

As before, 2 and 3 have a distance of 18.

**10. Grouping with linkage &amp; distance**

To calculate the distance between players 2 and group 1-4 we will use the complete linkage method, which is the maximum of the distances between observation two and each member of group 1-4. The resulting linkage-based distance is 20-point-6.

**11. Grouping with linkage &amp; distance**

Applying the same for player 3 we get a linkage distance of 16-point-8.

**12. Grouping with linkage &amp; distance**

Of these three options, the grouping of player 3 with 1 and 4 is selected because it has the smallest distance value.

**13. Grouping with linkage &amp; distance**

The next round of grouping doesn't require any decision making, we simply aggregate observation two with group 1-3-4.

**14. Grouping with linkage &amp; distance**

Now you have an iterative binary grouping of your four observations. The order in which these observations are grouped generates a hierarchy based on distance, and hence is called hierarchical clustering.

**15. Linkage criteria**

There are many different linkage methods that have been developed but for this course you will focus on the three most commonly used ones.Complete linkage, which we've learned is the maximum distance between two sets. Single linkage, which is the minimum distance. And average linkage, which - you guessed it - is the average distance between two sets. As you progress through this chapter you will have a chance to see the impact this decision can make in the final clustering.

**16. Let's practice!**

Let's proceed with some exercises.

## Calculating linkage

Let us revisit the example with three players on a field. The distance matrix between these three players is shown below and is available as the variable `dist_players`.

From this we can tell that the first group that forms is between players **1** &amp; **2**, since they are the closest to one another with a Euclidean distance value of <font color="red">11</font>.

Now you want to apply the three linkage methods you have learned to determine what the distance of this group is to player **3**.


|   |  1|  2|
|--:|--:|--:|
|  2| 11|   |
|  3| 16| 18|

**Steps**

1. Calculate the distance from player 3 to the group of players 1 & 2 using the following three linkage methods.

    * **Complete:** the resulting distance is based on the maximum.
    * **Single:** the resulting distance is based on the minimum.
    * **Average:** the resulting distance is based on the average.

```{r}
dist_players <- dist_three_players

# Extract the pair distances
distance_1_2 <- dist_players[1]
distance_1_3 <- dist_players[2]
distance_2_3 <- dist_players[3]

# Calculate the complete distance between group 1-2 and 3
complete <- max(c(distance_1_3, distance_2_3))
complete

# Calculate the single distance between group 1-2 and 3
single <- min(c(distance_1_3, distance_2_3))
single

# Calculate the average distance between group 1-2 and 3
average <- mean(c(distance_1_3, distance_2_3))
average
```

Great work! <br> Now you have all the knowledge you need to tackle exercise 12 from chapter 1.

## Revisited: The closest observation to a pair

**You are now ready to answer this question!**

Below you see a pre-calculated distance matrix between four players on a soccer field. You can clearly see that players **1** &amp; **4** are the closest to one another with a Euclidean distance value of <font color="red">10</font>. This distance matrix is available for your exploration as the variable `dist_players`

|   |    1|    2|    3|
|--:|----:|----:|----:|
|  2| 11.7|     |     |
|  3| 16.8| 18.0|     |
|  4| 10.0| 20.6| 15.8|

> *Question*
> ---
> **If 1 and 4 are the closest players among the four, which player is closest to players *1* and *4*?**<br>
> <br>
> ✅ Complete Linkage: Player 3, <br> Single &amp; Average Linkage: Player 2<br>
> ⬜ Complete Linkage: Player 2, <br> Single &amp; Average Linkage: Player 3<br>
> ⬜ Player 2 using Complete, Single &amp; Average Linkage methods<br>
> ⬜ Player 3 using Complete, Single &amp; Average Linkage methods<br>

This is correct, you can see that the choice of the linkage method can drastically change the result of this question.

## Capturing K clusters

Theory. Coming soon ...


**1. Capturing K clusters**

In the last few exercises you explored the ways in which it is possible to group multiple observations together using linkage analysis. Now you are ready to leverage this technique to group your observations into a predefined number of clusters.So let's revisit the soccer example with a few more players.

**2. Grouping soccer players**

In this case you have the positions of six players at the start of a game and you would like to infer which players belong to which team using hierarchical clustering.

**3. Grouping soccer players**

A euclidean distance matrix was calculated for each pair of players and is now used to group players using a complete linkage criteria.This algorithm iteratively proceeds to group the players until they are all under a single group like so...

**4. Grouping soccer players**



**5. Grouping soccer players**



**6. Grouping soccer players**



**7. Grouping soccer players**

Once this is completed we can work backwards to capture a desired number of clusters.At this moment, there is just one cluster.

**8. Extracting 2 clusters**

If we remove the last grouping like so.

**9. Grouping soccer players**

We have two distinct clusters.

**10. Grouping soccer players**

The red cluster contains players five and six while the blue cluster contains players one through four.Just like peeling an onion we can further split this into more parts by  removing the previous linkage grouping.

**11. Grouping soccer players**

In this case it was group 1, 2 and 4 linked to player 3.

**12. Grouping soccer players**

And now we have three distinct clusters (red, blue, and green).So, the process of identifying a pre-defined number of clusters, which we will refer to as k is as simple as undoing the last k-1 steps of the linkage grouping.Now let's learn how to do this in R.

**13. Hierarchical clustering in R**

The positions of the players are available in the data frame called players.As before, to get the euclidean distance between each pair of players we use the dist function.To perform the linkage steps we will use the hclust function which accepts a distance matrix, in our case dist_players and a linkage method. The default linkage method is the complete method. This results in a hclust object containing the linkage steps and can now be used to extract clusters.

**14. Extracting K clusters**

In order to determine which observations belong to which cluster, we use the cutree function. In this case we want to have two clusters because we know that there are two teams. So we provide the function with an hclust object and specify that we want a k of two. The output of cutree is a vector which represents which cluster each observation belongs to.We can append this back to our original data frame to do further analysis with the now clustered observations.

**15. Visualizing K Clusters**

One way we can analyze the clustering result is to plot the positions of these players and color the points based on their cluster assignment. Here we do this using ggplot.Remember that this clustering incorporated several decisions,the distance metric used was euclidean,the linkage metric used was complete and the k was 2. Changing any of these may, and likely will, impact the resulting clusters. This is why it is crucial to analyze the results to see if they actually make sense. For example in this case, the cluster analysis was aimed at identifying the teams to which the players belong to based on their positions at the start of the game. Since soccer games have the same number of players on each team, we know that the results of this clustering are incorrect and would need to consider a different distance or linkage criteria.Incorporating an understanding of your data and your problem into clustering analysis is the key to successfully leveraging this tool.

**16. Let's practice!**

So, let's do just that with some exercises.

## Assign cluster membership

In this exercise you will leverage the `hclust()` function to calculate the iterative linkage steps and you will use the `cutree()` function to extract the cluster assignments for the desired number (`k`) of clusters.

You are given the positions of 12 players at the start of a 6v6 soccer match. This is stored in the `lineup` data frame. 

You know that this match has two teams (k = 2), let's use the clustering methods you learned to assign which team each player belongs in based on their position.

**Notes:** 

* The linkage method can be passed via the **method** parameter: `hclust(distance_matrix, method = "complete")`
* Remember that in soccer opposing teams start on their half of the field.
* Because these positions are measured using the same scale we do not need to re-scale our data.

**Steps**

1. Calculate the Euclidean distance matrix `dist_players` among all twelve players
2. Perform the **complete** linkage calculation for hierarchical clustering using `hclust` and store this as `hc_players`
3. Build the cluster assignment vector `clusters_k2` using `cutree()` with a `k = 2`
4. Append the cluster assignments as a column `cluster` to the `lineup` data frame and save the results to a new data frame called `lineup_k2_complete`

```{r}
# Load package
library(dplyr)

# Load data
lineup <- readRDS("data/lineup.rds")

# Calculate the Distance
dist_players <- dist(lineup)

# Perform the hierarchical clustering using the complete linkage
hc_players <- hclust(dist_players, method = "complete")

# Calculate the assignment vector with a k of 2
clusters_k2 <- cutree(hc_players, k = 2)

# Create a new data frame storing these results
lineup_k2_complete <- mutate(lineup, cluster = clusters_k2)
```

Fantastic job! In the next exercise we will explore this result.

## Exploring the clusters

Because clustering analysis is always in part **qualitative**, it is incredibly important to have the necessary tools to explore the results of the clustering.

In this exercise you will explore that data frame you created in the previous exercise `lineup_k2_complete`. 

**Reminder:** The `lineup_k2_complete` data frame contains the x &amp; y positions of 12 players at the start of a 6v6 soccer game to which you have added clustering assignments based on the following parameters: 

* Distance: *Euclidean*
* Number of Clusters (k): *2*
* Linkage Method: *Complete*

**Steps**

1. Using `count()` from dplyr, count the number of players assigned to each cluster.
2. Using `ggplot()`, plot the positions of the players and color them by cluster assignment.

```{r}
# Count the cluster assignments
count(lineup_k2_complete, cluster)

# Plot the positions of the players and color them using their cluster
ggplot(lineup_k2_complete, aes(x = x, y = y, color = factor(cluster))) +
  geom_point(size = 3) +
  theme_bw()
```

You're doing great! <br> Think carefully about whether these results make sense to you and why.

## Validating the clusters

In the plot below you see the clustering results of the same lineup data you've previously worked with but with some minor modifications in the clustering steps. 

* The **left plot** was generated using a `k=2` and `method = 'average'`
* The **right plot** was generated using a `k=3` and `method = 'complete'`

<img src="http://s3.amazonaws.com/assets.datacamp.com/production/course_5592/datasets/c2_e7_example.png" alt>

> *Question*
> ---
> **If our goal is to correctly assign each player to their correct team then based on what you see in the above plot and what you know about the data set which of the statements below are correct?**<br>
> <br>
> ⬜ The **left plot** successfully clusters the players in their correct team.<br>
> ⬜ The **right plot** successfully clusters the players in their correct team.<br>
> ⬜ The **left plot** fails to correctly cluster the players; <br> because this is a 6v6 game the expection is that both clusters should have 6 members each.<br>
> ⬜ The **right plot** fails to correctly cluster the players; <br> because this is a two team match clustering into three unequal groups does not address the question correctly.<br>
> ✅ Answers 3 & 4 are both correct.<br>

Exactly! Both the results in the left and the right plots can be deemed incorrect based on what we expect from our data.

## Visualizing the dendrogram

Theory. Coming soon ...


**1. Visualizing the dendrogram**

As you recently learned, the process of hierarchical clustering involves iteratively grouping observations via pairwise comparisons until all observations are gathered into a single group. We can represent this grouping visually using a plot called the dendrogram, also knowns as a tree diagram.

**2. Building the dendrogram**

To build a dendrogram, let's start with the same 6 player soccer lineup from our last video.On the left we have the positions of the players and on the right we will assemble a dendgroram as we iteratively group these observations.

**3. Building the dendrogram**

As before we can start the process of hierarchical clustering by taking the two closest observations and grouping them.

**4. Building the dendrogram**

Correspondingly we can represent this grouping in the tree diagram.

**5. Building the dendrogram**

The dendrogram encodes a very important attribute of our grouping, the distance between the observations that were grouped.This is captured by the height axis. In this case the distance between the two observations is 4 point 1 and correspondingly their shared branch is at that height.

**6. Building the dendrogram**

As before we would form the next closest group, by comparing the pairwise distances and linkage criteria-based distances among the observations and existing groups.

**7. Building the dendrogram**

The first group with more than two observations now forms for one two and four and is accordingly represented in the dendrogram.

**8. Building the dendrogram**

The common branch between these three observations again encodes distance, more specifically it is a function of linkage criteria-based distance among all three observations.This is a very important feature of the dendrogram. It allows us to say something very concrete about our grouped observations at any given height. Remember that for distance we chose euclidean distance and the linkage criteria used was the complete method, which is the maximum distance between the group members.So in this case we can look at this dendrogram and say that the members that are a part of this branch, observations one two and four, have a euclidean distance between each other of 12 or less. We will leverage this attribute of the tree in our next video, but in the mean time let's continue to build the dendrogram.

**9. Building the dendrogram**

Iteratively joining the observations and groups.

**10. Building the dendrogram**

Until all are joined into a single group.

**11. Plotting the dendrogram**

Of course, we don't actually do this manually in R. To visualize a dendrogram, all we need to do is plot the corresponding hclust object. In this case we will reuse the hc_players object we created in the previous video to plot our dendrogram.

**12. Let's practice!**

Now that you know how to visualize hierarchical clustering lets explore what kind of impact the decision of linkage criteria can have on the dendrogram.

## Comparing average, single & complete linkage

You are now ready to analyze the clustering results of the `lineup` dataset using the dendrogram plot. This will give you a new perspective on the effect the decision of the linkage method has on your resulting cluster analysis.

**Steps**

1. Perform the linkage calculation for hierarchical clustering using the linkages: complete, single and average
2. Plot the three dendrograms side by side and review the changes

```{r}
# Prepare the Distance Matrix
dist_players <- dist(lineup)

# Generate hclust for complete, single & average linkage methods
hc_complete <- hclust(dist_players, method = "complete")
hc_single   <- hclust(dist_players, method = "single")
hc_average  <- hclust(dist_players, method = "average")

# Plot & Label the 3 Dendrograms Side-by-Side
# Hint: To see these Side-by-Side run the 4 lines together as one command
par(mfrow = c(1,3))
plot(hc_complete, main = 'Complete Linkage')
plot(hc_single,   main = 'Single Linkage')
plot(hc_average,  main = 'Average Linkage')
```

Excellent! Did you notice how the trees all look different? <br> In the coming exercises you will see how visualizing this structure can be helpful for building clusters.

## Height of the tree

An advantage of working with a clustering method like hierarchical clustering is that you can describe the relationships between your observations based on both the **distance metric** and the **linkage metric** selected (the combination of which defines the height of the tree).

**Based on the code below what can you concretely say about the height of a branch in the resulting dendrogram?**

```{r, eval=FALSE}
dist_players <- dist(lineup, method = 'euclidean')
hc_players <- hclust(dist_players, method = 'single')
plot(hc_players)  
```

> *Question*
> ---
> **All of the observations linked by this branch must have:**<br>
> <br>
> ⬜ a **maximum Euclidean** distance amongst each other less than or equal to the height of the branch.<br>
> ⬜ a **minimum Jaccard** distance amongst each other less than or equal to the height of the branch.<br>
> ✅ a **minimum Euclidean** distance amongst each other less than or equal to the height of the branch.<br>

Exactly! Based on this code we can concretely say that for a given branch on a tree all members that are a part of that branch must have a minimum Euclidean distance amongst one another equal to or less than the height of that branch. 

In the next section you will see how this description can be put into action to generate clusters that can be described using the same logic.

## Cutting the tree

Theory. Coming soon ...


**1. Cutting the tree**

In the previous exercises you have learned how to plot and interpret the dendrogram. Now, let's learn how to leverage this visualization to both identify our clusters and highlight some of their key characteristics.

**2. Cutting the tree**

Let's continue our work with the soccer player dendrogram. Remember that the distance between the observations was calculated using euclidean distance and we used the complete linkage criteria. This means that at any given branch, all members that share this branch will have a euclidean distance amongst one another no greater than the height of that branch. We can leverage this idea to both select our clusters and also characterize the relationships of their members.

**3. Cutting the tree**

To do so we can cut our tree at any desired height. Let's choose 15 for now. This means that we remove all links above this cut point and we create our clusters below.

**4. Cutting the tree**

In this case two clusters are formed. Using this height cutoff we can already ascribe a characteristic to them. We can say that all members of the created clusters will have a euclidean distance amongst each other no greater than our cut height of 15. This statement is a function of our choice of height, distance metric and linkage criteria. This information can be very valuable as our data gets more features and becomes harder to plot using only two dimensions.

**5. Coloring the dendrogram - height**

We can visualize the clusters that form at any given height by leveraging the dendextend library to color our dendrogram plot.To do so we first must convert the hclust object into a dendrogram object by using the function as (dot) dendrogram.The next step is to use the color_branches function from the dendextend package to color the branches based on a desired criteria. In this case we want to cut using a height of 15, we represent this using the parameter h.Finally we use the plot function to plot the newly colored dendrogram.

**6. Coloring the dendrogram - height**

We can use this visual to further explore heights at which we may want to create our clusters. Let's say we believed a height of ten would be more appropriate, as shown in this plot with a proposed red line.

**7. Coloring the dendrogram - height**

We perform the steps to color the tree using an h equal to 10. The resulting dendrogram now has four colors for the corresponding four clusters.

**8. Coloring the dendrogram - K**

You can also leverage the color_branches to color the tree using a k criteria by just providing our desired k like so. Resulting in two clusters formed by the cutting of the last grouping.

**9. cutree() using height**

Just like color_branches can interchangeably use height or k, the cutree function we used to first make clusters can be used to assign cluster memberships using a provided height with the parameter h. As before, we can append this vector of cluster assignments to our data frame in order to empower us to do further exploration.

**10. Let's practice!**

Now that you know how to visualize and explore the results of your hierarchical clustering work, let's try it out.

## Clusters based on height

In previous exercises you have grouped your observations into clusters using a pre-defined number of clusters (**k**). In this exercise you will leverage the visual representation of the dendrogram in order to group your observations into clusters using a maximum height (**h**), below which clusters form.

You will work the `color_branches()` function from the `dendextend` library in order to visually inspect the clusters that form at any height along the dendrogram.

The **hc_players** has been carried over from your previous work with the soccer line-up data.

**Steps**

1. Create a dendrogram object `dend_players` from your `hclust` result using the function `as.dendrogram()`
2. Plot the dendrogram
3. Using the `color_branches()` function create & plot a new dendrogram with clusters colored by a cut height of 20
4. Repeat the above step with a height of 40

```{r}
library(dendextend)
dist_players <- dist(lineup, method = 'euclidean')
hc_players   <- hclust(dist_players, method = "complete")

# Create a dendrogram object from the hclust variable
dend_players <- as.dendrogram(hc_players)

# Plot the dendrogram
plot(dend_players)

# Color branches by cluster formed from the cut at a height of 20 & plot
dend_20 <- color_branches(dend_players, h = 20)

# Plot the dendrogram with clusters colored below height 20
plot(dend_20)

# Color branches by cluster formed from the cut at a height of 40 & plot
dend_40 <- color_branches(dend_players, h = 40)

# Plot the dendrogram with clusters colored below height 40
plot(dend_40)
```

Excellent! Can you see that the height that you use to cut the tree greatly influences the number of clusters and their size? Consider taking a moment to play with other values of height before continuing.

## Exploring the branches cut from the tree

The `cutree()` function you used in exercises 5 &amp; 6 can also be used to cut a tree at a given height by using the `h` parameter. Take a moment to explore the clusters you have generated from the previous exercises based on the heights 20 &amp; 40.

**Steps**

1. Build the cluster assignment vector `clusters_h20` using `cutree()` with a `h = 20`
2. Append the cluster assignments as a column `cluster` to the `lineup` data frame and save the results to a new data frame called `lineup_h20_complete`
3. Repeat the above two steps for a height of **40**, generating the variables `clusters_h40` and `lineup_h40_complete`
4. Use ggplot2 to create a scatter plot, colored by the cluster assignment for both heights

```{r}
dist_players <- dist(lineup, method = 'euclidean')
hc_players   <- hclust(dist_players, method = "complete")

# Calculate the assignment vector with a h of 20
clusters_h20 <- cutree(hc_players, h = 20)

# Create a new data frame storing these results
lineup_h20_complete <- mutate(lineup, cluster = clusters_h20)

# Calculate the assignment vector with a h of 40
clusters_h40 <- cutree(hc_players, h = 40)

# Create a new data frame storing these results
lineup_h40_complete <- mutate(lineup, cluster = clusters_h40)

# Plot the positions of the players and color them using their cluster for height = 20
ggplot(lineup_h20_complete, aes(x = x, y = y, color = factor(cluster))) +
  geom_point(size = 3) +
  theme_bw()

# Plot the positions of the players and color them using their cluster for height = 40
ggplot(lineup_h40_complete, aes(x = x, y = y, color = factor(cluster))) +
  geom_point(size = 3) +
  theme_bw()
```

Great job! You can now explore your clusters using both **k** and **h** parameters.

## What do we know about our clusters?

**Based on the code below, what can you concretely say about the relationships of the members within each cluster?**

```{r, eval=FALSE}
dist_players <- dist(lineup, method = 'euclidean')
hc_players   <- hclust(dist_players, method = 'complete')
clusters     <- cutree(hc_players, h = 40)  
```

> *Question*
> ---
> **Every member belonging to a cluster must have:**<br>
> <br>
> ✅ a **maximum Euclidean** distance to all other members of its cluster that is less than 40.<br>
> ⬜ a **maximum Euclidean** distance to all other members of its cluster that is greater than or equal to 40.<br>
> ⬜ a **average Euclidean** distance to all other members of its cluster that is less than 40.<br>

Correct! The height of any branch is determined by the linkage and distance decisions (in this case complete linkage and Euclidean distance). While the members of the clusters that form below a desired height have a maximum linkage+distance amongst themselves that is less than the desired height.

## Making sense of the clusters

Theory. Coming soon ...


**1. Making sense of the clusters**

Over the last series of exercises, you have developed the tools you need to run hierarchical clustering and the intuition to understand the impact of each step. Now you will have a chance to use these skills by clustering a new dataset.

**2. Wholesale dataset**

You will work with a series of 45 records of customer spending from a wholesale distributor. For each customer record you will have 3 features, spending on Milk, Grocery and Frozen Food.

**3. Wholesale dataset**

The dataset will look like this.You will notice that unlike the soccer positions data set, where we only have two features (x and y), this dataset has three features. The consequence of this is that we can't simply explore what the clusters mean from a two dimensional plot.

**4. Exploring more than 2 dimensions**

There are several approaches to overcome this. Once you have assigned the cluster memberships you can make multiple plots with feature pairs and use color to show the difference in clusters. This can be helpful, but only captures one angle of the complex interactions at a time. Also this approach can quickly get out of hand when the number of features expands.Alternatively, you can use dimensionality reduction methods such as principal component analysis in order to plot your multi-dimensional data onto two dimensions and color the points using the cluster assignment. This can be helpful to see if your observations clustered well and the clusters are well separated. However, this type of analysis is difficult to interpret and wouldn't shed light on the characteristics of the clusters.Finally, you can simply explore the distribution characteristics such as the mean and median of each feature within your clusters. By comparing these summary statistics between clusters you can begin to build a narrative of what makes the observations within the cluster similar to each other while different from the observations in the other clusters.

**5. Segment the customers**

In the next series of exercises you will use this data identify the clusters of customers that form based on their spending. This is a common use case of cluster analysis where the desired outcome is to segment customers based on their behaviors. Once the segments are identified we can explore their common characteristics to gain insights into our customer base and design value-driven opportunities using this data.Let's get started.

## Segment wholesale customers

You're now ready to use hierarchical clustering to perform market segmentation (i.e. use consumer characteristics to group them into subgroups).

In this exercise you are provided with the amount spent by 45 different clients of a wholesale distributor for the food categories of **Milk**, **Grocery** &amp; **Frozen**. This is stored in the data frame `customers_spend`. Assign these clients into meaningful clusters.

**Note:** For this exercise you can assume that because the data is all of the same type (amount spent) and you will not need to scale it.

**Steps**

1. Calculate the Euclidean distance between the customers and store this in `dist_customers`
2. Run hierarchical clustering using **complete** linkage and store in `hc_customers`
3. Plot the dendrogram
4. Create a cluster assignment vector using a height of 15,000 and store it as `clust_customers`
5. Generate a new data frame `segment_customers` by appending the cluster assignment as the column `cluster` to the original `customers_spend` data frame

```{r}
# Load data
customers_spend <- readRDS("data/ws_customers.rds")

# Calculate Euclidean distance between customers
dist_customers <- dist(customers_spend)

# Generate a complete linkage analysis 
hc_customers <- hclust(dist_customers, method = "complete")

# Plot the dendrogram
plot(hc_customers)

# Create a cluster assignment vector at h = 15000
clust_customers <- cutree(hc_customers, h = 15000)

# Generate the segmented customers data frame
segment_customers <- mutate(customers_spend, cluster = clust_customers)
```

Excellent! Let's move on to the next exercise and explore these clusters.

## Explore wholesale customer clusters

Continuing your work on the wholesale dataset you are now ready to analyze the characteristics of these clusters. 

Since you are working with more than 2 dimensions it would be challenging to visualize a scatter plot of the clusters, instead you will rely on summary statistics to explore these clusters. In this exercise you will analyze the mean amount spent in each cluster for all three categories.

**Steps**

1. Calculate the size of each cluster using `count()`.
2. Color & plot the dendrogram using the height of 15,000.
3. Calculate the average spending for each category within each cluster using the `summarise_all()` function.

```{r}
dist_customers <- dist(customers_spend)
hc_customers <- hclust(dist_customers)
clust_customers <- cutree(hc_customers, h = 15000)
segment_customers <- mutate(customers_spend, cluster = clust_customers)

# Count the number of customers that fall into each cluster
count(segment_customers, cluster)

# Color the dendrogram based on the height cutoff
dend_customers <- as.dendrogram(hc_customers)
dend_colored <- color_branches(dend_customers, h = 15000)

# Plot the colored dendrogram
plot(dend_colored)

# Calculate the mean for each category
segment_customers %>% 
  group_by(cluster) %>% 
  summarise_all(list(mean))
```

Great work! You've gathered a bunch of information about these clusters, now let's see what can be interpreted from them.

## Interpreting the wholesale customer clusters

| cluster|  Milk| Grocery| Frozen| cluster size|
|-------:|-----:|-------:|------:|------------:|
|       1| 16950|   12891|    991|            5|
|       2|  2512|    5228|   1795|           29|
|       3| 10452|   22550|   1354|            5|
|       4|  1249|    3916|  10888|            6|

> *Question*
> ---
> What observations can we make about our segments based on their average spending in each category?<br>
> <br>
> ⬜ Customers in cluster 1 spent more money on Milk than any other cluster.<br>
> ⬜ Customers in cluster 3 spent more money on Grocery than any other cluster.<br>
> ⬜ Customers in cluster 4 spent more money on Frozen goods than any other cluster.<br>
> ⬜ The majority of customers fell into cluster 2 and did not show any excessive spending in any category.<br>
> ✅ All of the above.<br>

All 4 statements are reasonable, but whether they are meaningful depends heavily on the business context of the clustering.

# 3. K-means clustering

In this chapter, you will build an understanding of the principles behind the k-means algorithm, learn how to select the right k when it isn't previously known, and revisit the wholesale data from a different perspective.  

## Introduction to K-means

Theory. Coming soon ...


**1. Introduction to K-means**

In the last chapter you learned how to use the hierarchical clustering method to group observations. In this chapter you will learn about another popular method of clustering called k-means clustering. To learn how this method works, let's revisit an expanded version of the soccer lineup data you have been working with.

**2. k-means**

This data consists of twelve players on a soccer field at the start of the game. At this point in the game the teams are positioned on opposite sides of the field. We would expect that clustering can be effective in identifying teams and assigning each player to the correct team. The first step of k-means clustering involves making a decision of how many clusters to generate. This is the k in k-means clustering. This can be decided on in advance based on our understanding of the data or it can be estimated from the data empirically. We will discuss the estimation methods later in this chapter. In this example we can leverage what is known about our data. Since we know that soccer is played with two teams we can use a k of 2 for the desired number of clusters. Once k is established the algorithm can proceed.

**3. k-means**

The first step in the k-means algorithm is to initialize k points at random positions in the feature space, we will refer to these points as the cluster centroids. In this data we will illustrate our two centroids using a red and a blue x.

**4. k-means**

For each observation the distance is calculated between the observation and each centroid. In k-means clustering, the distance is limited euclidean only.

**5. k-means**

The observations are initially assigned to the centroid to which they are closest to.

**6. k-means**

We can see this decision boundary represented by the color space.

**7. k-means**

The observations now have an initial assignment to one of the two clusters.

**8. k-means**

The next step involves moving the centroids to the central points of the resulting clusters.

**9. k-means**

Again, the distance of every observation is calculated to each centroid.

**10. k-means**

And they are re-assigned based on which centroid they are closest to.

**11. k-means**

This process continues until the centroids stabilize and the observations are no longer reassigned. This is the fundamental algorithm of kmeans clustering.

**12. kmeans()**

To generate the kmeans model in R you will use the function of the same name. We will continue to work with the lineup data frame that you explored in chapter two. The kmeans function is run with the data as the first argument and the desired number of clusters provided using the centers parameter. Centers in this case is synonymous with k.

**13. Assigning clusters**

Once the model is run you will want to extract the cluster assignments in order to explore their characteristics.You can extract the cluster assignments directly from the model object. The vector of assignments is stored in the model object and is aptly named cluster.As before you can append this vector to your data frame in order to further explore the results of your clustering.

**14. Let's practice!**

Now that you know how kmeans works and how to use it in R let's practice with the soccer lineup data.

## K-means on a soccer field

In the previous chapter you used the `lineup` dataset to learn about **hierarchical** clustering, in this chapter you will use the same data to learn about **k-means** clustering. 
As a reminder, the `lineup` data frame contains the positions of 12 players at the start of a 6v6 soccer match.

Just like before, you know that this match has two teams on the field so you can perform a k-means analysis using *k = 2* in order to determine which player belongs to which team.

Note that in the `kmeans()` function `k` is specified using the `centers` parameter.

**Steps**

1. Build a k-means model called `model_km2` for the `lineup` data using the `kmeans()` function with `centers = 2`
2. Extract the vector of cluster assignments from the model `model_km2$cluster` and store this in the variable `clust_km2`
3. Append the cluster assignments as a column `cluster` to the `lineup` data frame and save the results to a new data frame called `lineup_km2`
4. Use ggplot to plot the positions of each player on the field and color them by their cluster

```{r}
# Build a kmeans model
model_km2 <- kmeans(lineup, centers = 2)

# Extract the cluster assignment vector from the kmeans model
clust_km2 <- model_km2$cluster

# Create a new data frame appending the cluster assignment
lineup_km2 <- mutate(lineup, cluster = clust_km2)

# Plot the positions of the players and color them using their cluster
ggplot(lineup_km2, aes(x = x, y = y, color = factor(cluster))) +
  geom_point(size = 3) +
  theme_bw()
```

Well done! Knowing the desired number of clusters ahead of time can be very helpful when performing a k-means analysis. In the next section we will see what happens when we use an incorrect value of k.

## K-means on a soccer field (part 2)

In the previous exercise you successfully used the  **k-means** algorithm to cluster the two teams from the `lineup` data frame. This time, let's explore what happens when you use a `k` of **3**. 

You will see that the algorithm will still run, but does it actually make sense in this context…

**Steps**

1. Build a k-means model called `model_km3` for the `lineup` data using the `kmeans()` function with `centers = 3`
2. Extract the vector of cluster assignments from the model `model_km3$cluster` and store this in the variable `clust_km3`
3. Append the cluster assignments as a column `cluster` to the `lineup` data frame and save the results to a new data frame called `lineup_km3`
4. Use ggplot to plot the positions of each player on the field and color them by their cluster

```{r}
# Build a kmeans model
model_km3 <- kmeans(lineup, centers = 3)

# Extract the cluster assignment vector from the kmeans model
clust_km3 <- model_km3$cluster

# Create a new data frame appending the cluster assignment
lineup_km3 <- mutate(lineup, cluster = clust_km3)

# Plot the positions of the players and color them using their cluster
ggplot(lineup_km3, aes(x = x, y = y, color = factor(cluster))) +
  geom_point(size = 3) +
  theme_bw()
```

Does this result make sense? Remember we only have 2 teams on the field. It's **very** important to remember that k-means will run with any k that is more than 2 and less than your total observations, but it doesn't always mean the results will be meaningful.

## Evaluating different values of K by eye

Theory. Coming soon ...

**1. Evaluating different values of K by eye**

In the last two exercises you explored the results for two different values of k using the same data. You knew that a k of 3 was clearly incorrect because you applied content expertise to this problem by stating that there are only two teams in a game of soccer and that the teams have the same number of players. But, what happens when you don't know in advance what the right value of k is? In this course you will learn two methods that address this challenge by estimating k empirically from the data. In this video and the accompanying exercises you will build an intuition for one of these methods, the elbow method.

**2. Total within-cluster sum of squares: k = 1**

The elbow method relies on calculating the total within cluster sum of squares across every cluster, that is the sum of euclidean distances between each observation and the centroid corresponding to the cluster to which the observation is assigned. Here this is represented by the dashed lines between the centroid and each observation. While k = 1 isn't really clustering, it can be helpful for the elbow analysis. As such we record the total within cluster sum of squares for the value of k = 1.

**3. Total within-cluster sum of squares: k = 2**

We repeat this step for k = 2. You can already see that the dashed lines are on average shorter and we can expect the total within cluster sum of squares to drop. Which of course it does.

**4. Total within-cluster sum of squares: k = 3**

Same goes for a value of k = 3.

**5. Total within-cluster sum of squares: k = 4**

And for k = 4. We can continue this calculation so long as k is less than our total number of observations.

**6. Elbow plot**

In this case we have calculated this for values of k from one through ten. You may notice a trend that as k increases the total within cluster sum of squares keeps decreasing. This is absolutely natural and expected, just think about it, the more you segment your data the more your points just group together into smaller and more compact clusters until you obtain many clusters with only one or two members. What we are looking for is the point at which the curve beings to flatten out, affectionally referred to as the elbow. In this case we can see that there is a precipitous drop going from a k of one to two and then a leveling off when moving between a k of 2 and 3 and onward.

**7. Elbow plot**

As such we can claim that the elbow in this case occurred where k = 2 and would consider using this estimated value of k.

**8. Generating the elbow plot**

Now that you know how the elbow plot is built, let's learn how to build it in R. The first piece you will need to know is how to calculate the total within cluster sum of squares. Conveniently, the kmeans function already takes care of this for you. All you need to do is to extract it from the model object like so.

**9. Generating the elbow plot**

Because you want to calculate this for multiple values of k you will need to create multiple models and extract their corresponding values. To do this I recommend leveraging the map double function from the purrr library. The code shown here iterates over values of k ranging from one to ten in order to build corresponding models and extract their total within-Cluster sum of squares values. You can append this vector to the corresponding vector of k values to create a data frame.
10. Generating the elbow plot

Which you can then use to plot the elbow plot like so.

**11. Let's practice!**

Let's try it out! 

## Many K's many models

While the `lineup` dataset clearly has a known value of **k**, often times the optimal number of clusters isn't known and must be estimated. 

In this exercise you will leverage `map_dbl()` from the `purrr` library to run k-means using values of k ranging from 1 to 10 and extract the **total within-cluster sum of squares** metric from each one. This will be the first step towards visualizing the elbow plot.

**Steps**

1. Use `map_dbl()` to run `kmeans()` using the `lineup` data for k values ranging from 1 to 10 and extract the **total within-cluster sum of squares** value from each model: `model$tot.withinss`\nStore the resulting vector as `tot_withinss`  
2. Build a new data frame `elbow_df` containing the values of k and the vector of **total within-cluster sum of squares**

```{r}
library(purrr)

# Use map_dbl to run many models with varying value of k (centers)
tot_withinss <- map_dbl(1:10,  function(k){
  model <- kmeans(x = lineup, centers = k)
  model$tot.withinss
})

# Generate a data frame containing both k and tot_withinss
elbow_df <- data.frame(
  k = 1:10,
  tot_withinss = tot_withinss
)
```

Great work! In the next exercise you will plot the elbow plot from this data.

## Elbow (Scree) plot

In the previous exercises you have calculated the **total within-cluster sum of squares** for values of **k** ranging from 1 to 10. You can visualize this relationship using a line plot to create what is known as an elbow plot (or scree plot).  

When looking at an elbow plot you want to see a sharp decline from one k to another followed by a more gradual decrease in slope. The last value of k before the slope of the plot levels off suggests a "good" value of k.

**Steps**

1. Continuing your work from the previous exercise, use the values in `elbow_df` to plot a line plot showing the relationship between **k** and **total within-cluster sum of squares**

```{r}
# Use map_dbl to run many models with varying value of k (centers)
tot_withinss <- map_dbl(1:10,  function(k){
  model <- kmeans(x = lineup, centers = k)
  model$tot.withinss
})

# Generate a data frame containing both k and tot_withinss
elbow_df <- data.frame(
  k = 1:10,
  tot_withinss = tot_withinss
)

# Plot the elbow plot
ggplot(elbow_df, aes(x = k, y = tot_withinss)) +
  geom_line() +
  scale_x_continuous(breaks = 1:10) +
  theme_bw()
```

Fantastic! You have learned how to create and visualize elbow plots as a tool for finding a "good" value of **k**. In the next section you will add another tool to your arsenal for finding **k**.

## Interpreting the elbow plot

Based on the elbow plot you generated in the previous exercise for the `lineup` data:

<img src="http://s3.amazonaws.com/assets.datacamp.com/production/course_5724/datasets/soccer_elbow.png">

> *Question*
> ---
> **Which of these interpretations are valid?**<br>
> <br>
> ✅ Based on this plot, the **k** to choose is **2**; the elbow occurs there.<br>
> ⬜ The **k** to choose is **5**; this is where the trend levels off.<br>
> ⬜ Any value of **k** is valid; this plot does not clearly identify an elbow.<br>
> ⬜ None of the above.<br>

That is correct, you can see that there is a sharp change in the slope of this line that makes an "elbow" shape. Furthermore, this is supported by the prior knowledge that there are **two** teams in this data and a **k** of **2** is desired.

## Silhouette analysis: observation level performance

Theory. Coming soon ...


**1. Silhouette analysis: observation level performance**

In the last series of exercises you utilized the elbow method to estimate a suitable value of k.In this lesson you will learn about the silhouette analysis method. This approach provides a different lens through which you can understand the results of your cluster analysis. It can be used to determine how well each of your observations fit into its corresponding cluster and can be leveraged as an additional method for estimating the value of k.

**2. Soccer lineup with K = 3**

Continuing with our soccer lineup dataset, we will start with the observations already clustered using kmeans with a k of three.

**3. Silhouette width**

Silhouette analysis involves calculating a measurement called the silhouette width for every observation. The silhouette width consists of two parts. The within cluster distance C and the closest neighbor distance N. We'll work with player number 3 to illustrate this calculation.

**4. Silhouette width**

The within cluster distance for an observation is the average euclidean distance from that observation to every other observation within the same cluster. In this case the distances are represented by the arrows to the other 3 members of the green cluster.

**5. Silhouette width**

The closest neighbor distance for an observation is the average distance from that observation to the points of the closest neighboring cluster.

**6. Silhouette width**

It is calculated for the red cluster like so.

**7. Silhouette width**

Then the blue cluster. The smallest average distance to our observation is then used as the closest neighbor distance. In this case the blue cluster is clearly closer.

**8. Silhouette width: S(i)**

Using the values of N and C the silhouette width can be calculated as shown here.

**9. Silhouette width: S(i)**

More importantly is the intuitive interpretation of this value.A value close to one suggests that this observation is well matched to its current cluster.A value of 0 suggests that it is on the border between two clusters and can possibly belong to either one.While a value of -1, or close to -1 suggests that this observation has a better fit with its closest neighboring cluster.What do you think is the silhouette width for player 3? It sits on the border between blue and green so I'm guessing it's probably close to zero.

**10. Calculating S(i)**

We can calculate the silhouette width for each observation by leveraging the pam function from the cluster library. Note, that the pam function is very similar, but is not identical to kmeans. Since we are just using it to characterize our kmeans clusters we can ignore this difference.The pam function requires a data frame and a desired number of clusters provided by the parameter k. The silhouette widths can be accessed from the pam model object as shown here.

**11. Silhouette plot**

Or they can be visualized using the silhouette plot like so.In this plot the bars represent the silhouette widths for each observation. Look at observation three, like we guessed, it's value is close to zero.

**12. Silhouette plot**

Also, note at the bottom of this plot is the average silhouette width across the twelve observations.

**13. Average silhouette width**

This measurement can be retrieved from the model object as shown here. And, it can be interpreted in a manner similar to the silhouette width for an observation.In this case the average is well above zero suggesting that most observations are well matched to their assigned cluster.Now that you have a way of measuring the effectiveness of the clustering, you can perform an analysis similar to the elbow plot and calculate the average silhouette widths for multiple values of k. The greater the average width the better the individual observations match to their clusters.

**14. Highest average silhouette width**

Similar to the elbow plot we can leverage the map double function to run pam across multiple values of k and record the average silhouette width for each, likewise we can append these measurements to a data frame.

**15. Choosing K using average silhouette width**

And use ggplot to see the relationship between k and the average silhouette width.

**16. Choosing K using average silhouette width**

Not surprisingly, the highest average silhouette width is for a k of two, and would be the recommended value based on this method.

**17. Let's practice!**

Now that you know how silhouette analysis works, let's try it out.

## Silhouette analysis

Silhouette analysis allows you to calculate how similar each observations is with the cluster it is assigned relative to other clusters. This metric (silhouette width) ranges from **-1** to **1** for each observation in your data and can be interpreted as follows:

* Values close to **1** suggest that the observation is well matched to the assigned cluster
* Values close to **0** suggest that the observation is borderline matched between two clusters
* Values close to **-1** suggest that the observations may be assigned to the wrong cluster
In this exercise you will leverage the `pam()` and the `silhouette()` functions from the `cluster` library to perform silhouette analysis to compare the results of models with a k of 2 and a k of 3. You'll continue working with the `lineup` dataset.

> Pay close attention to the silhouette plot, does each observation clearly belong to its assigned cluster for k = 3?

**Steps**

1. Generate a k-means model `pam_k2` using `pam()` with `k = 2` on the `lineup` data.
2. Plot the silhouette analysis using `plot(silhouette(model))`.
3. Repeat the first two steps for `k = 3`, saving the model as `pam_k3`.
4. Make sure to review the differences between the plots before proceeding (especially observation **3**) for `pam_k3`.

```{r}
library(cluster)

# Generate a k-means model using the pam() function with a k = 2
pam_k2 <- pam(lineup, k = 2)

# Plot the silhouette visual for the pam_k2 model
plot(silhouette(pam_k2))

# Generate a k-means model using the pam() function with a k = 3
pam_k3 <- pam(lineup, k = 3)

# Plot the silhouette visual for the pam_k3 model
plot(silhouette(pam_k3))

```

Great work! Did you notice that for k = 2, no observation has a silhouette width close to 0? What about the fact that for k = 3, observation 3 is close to 0 and is negative? This suggests that k = 3 is not the right number of clusters.

## Making sense of the K-means clusters

Theory. Coming soon ...


**1. Making sense of the K-means clusters**

Throughout this chapter you have worked to develop an understanding and an intuition of how to use the kmeans algorithm and its associated techniques to perform clustering analysis.Now it's time to put these tools into practice by revisiting the wholesale dataset.

**2. Wholesale dataset**

You have learned a lot since you've last looked at this data so let's have a quick refresher.The wholesale dataset is an exercise in clustering the customers of a wholesale distributor. This use of clustering is also known as market segmentation. The wholesale data consists of 45 observations of client purchases for milk, grocery and frozen food. The data is stored in the data frame customers_spend.

**3. Segmenting with hierarchical clustering**

At the end of chapter two you used hierarchical clustering to segment the customers into four clusters using a height that seemed appropriate based on the structure of the tree.

**4. Segmenting with hierarchical clustering**

You then characterized these customer segments by calculating the average of their spending in each category. From this analysis you learned that segments one, three, and four consist of around five observations each and their members collectively spend more on one category relative to the others. In a real world scenario a finding like this could be used to provide more customized advertising or other targeting for these groups based on their spending habits.Do you think the result will be the be the same if you used a different method for clustering?

**5. Segmenting with K-means**

Let's find out. In the following exercises you will leverage the kmeans tools you have learned in this chapter to:First estimate the best value of k by finding the maximum average silhouette width with respect to k.Then you will use this value of k to create a kmeans model.Finally, you will characterize these k clusters by calculating their average spending in each category like you have in the previous chapter.As you progress through these exercises feel free to look back and compare your results with the corresponding hierarchical clustering exercises. I encourage you to see if the results are different and speculate as to why that may be the case?Most importantly, you must remember that both of these clustering  methods are descriptive and not prescriptive. In other words, they will provide different lenses with which you can understand your underlying data but the choice of which to use and how to correctly use it will be highly dependent on the question at hand as well as an understanding of the underlying subject matter.

**6. Let's cluster!**

So, what are you waiting for, let's see how kmeans segments our customers.

## Revisiting wholesale data: "Best" k

At the end of **Chapter 2** you explored wholesale distributor data `customers_spend` using hierarchical clustering. This time you will analyze this data using the k-means clustering tools covered in this chapter. 

The first step will be to determine the **"best"** value of k using **average silhouette width**.

A refresher about the data: it contains records of the amount spent by 45 different clients of a wholesale distributor for the food categories of **Milk**, **Grocery** &amp; **Frozen**. This is stored in the data frame `customers_spend`. For this exercise you can assume that because the data is all of the same type (amount spent) and you will not need to scale it.

**Steps**

1. Use `map_dbl()` to run `pam()` using the `customers_spend` data for k values ranging from 2 to 10 and extract the **average silhouette width** value from each model: `model$silinfo$avg.width`\nStore the resulting vector as `sil_width`  
2. Build a new data frame `sil_df` containing the values of k and the vector of **average silhouette widths**  
3. Use the values in `sil_df` to plot a line plot showing the relationship between **k** and **average silhouette width**

```{r}
# Use map_dbl to run many models with varying value of k
sil_width <- map_dbl(2:10,  function(k){
  model <- pam(x = customers_spend, k = k)
  model$silinfo$avg.width
})

# Generate a data frame containing both k and sil_width
sil_df <- data.frame(
  k = 2:10,
  sil_width = sil_width
)

# Plot the relationship between k and sil_width
ggplot(sil_df, aes(x = k, y = sil_width)) +
  geom_line() +
  scale_x_continuous(breaks = 2:10) +
  theme_bw()
```

You're doing great! From the plot I hope you noticed that k = 2 has the highest average sillhouette width and is the **\\"best\\"** value of **k** we will move forward with.

## Revisiting wholesale data: Exploration

From the previous analysis you have found that `k = 2` has the highest **average silhouette width**. In this exercise you will continue to analyze the wholesale customer data by building and exploring a kmeans model with **2** clusters.

**Steps**

1. Build a k-means model called `model_customers` for the `customers_spend` data using the `kmeans()` function with `centers = 2`.
2. Extract the vector of cluster assignments from the model `model_customers$cluster` and store this in the variable `clust_customers`.
3. Append the cluster assignments as a column `cluster` to the `customers_spend` data frame and save the results to a new data frame called `segment_customers`.
4. Calculate the size of each cluster using `count()`.

```{r}
set.seed(42)

# Build a k-means model for the customers_spend with a k of 2
model_customers <- kmeans(customers_spend, centers = 2)

# Extract the vector of cluster assignments from the model
clust_customers <- model_customers$cluster

# Build the segment_customers data frame
segment_customers <- mutate(customers_spend, cluster = clust_customers)

# Calculate the size of each cluster
count(segment_customers, cluster)

# Calculate the mean for each category
segment_customers %>% 
  group_by(cluster) %>% 
  summarise_all(list(mean))
```

Well done! It seems that in this case **cluster 1** consists of individuals who proportionally spend more on **Frozen** food while **cluster 2** customers spent more on **Milk** and **Grocery**. Did you notice that when you explored this data using hierarchical clustering, the method resulted in **4** clusters while using k-means got you **2**. Both of these results are valid, but which one is appropriate for this would require more subject matter expertise. Before you proceed with the next chapter, remember that: Generating clusters is a science, but interpreting them is an art.

# 4. Case Study: National Occupational mean wage

In this chapter, you will apply the skills you have learned to explore how the average salary amongst professions have changed over time.  

## Occupational wage data

Theory. Coming soon ...


**1. Occupational wage data**

There are many types of problems that are suitable for cluster analysis. In the last 3 chapters you encountered two common types of such problems. With the soccer lineup data you worked with clustering based on spatial data. With the wholesale spending data you segmented customers into clusters. In this chapter you will encounter a third type of problem. You will leverage the tools you have learned thus far to explore data that changes with time, or time-series data.

**2. Occupational wage data**

You will work with data that consists of the average incomes for twenty two occupations in the United States collected from 2001 to 2016.This corresponds to a matrix where the observations are the 22 occupations and the features of these observations are the measurements of the average income for each year.

**3. Occupational wage data**

This data is stored in the datamatrix called oes.

**4. Occupational wage data**

We can see the trends of each occupation with respect to time in this plot. So the question we must ask ourselves is which occupations cluster together?Or to put it another way are there distinct trends of observations that we can observe?

**5. Next steps: hierarchical clustering**

In the next series of exercises you will go through the necessary steps to analyze this data using hierarchical clustering.As we have discussed in chapters 1 and 2 you will:First determine if any pre-processing steps are needed for this data, such as scaling or imputation.Next you will use the post-processed data to create a distance matrix with an appropriate distance metric.Then you will use the distance matrix to build a dendrogram using a chosen linkage criteria.You will then use what you have learned from this dendrogram to select an appropriate height and extract the cluster assignments.Finally, and most importantly you will explore the resulting clusters to determine whether they make sense and what conclusions can be made from them.

**6. Let's practice!**

Let's give it a shot.

## Initial exploration of the data

You are presented with data from the Occupational Employment Statistics (OES) program which produces employment and wage estimates annually. This data contains the yearly average income from **2001** to **2016** for **22** occupation groups. You would like to use this data to identify clusters of occupations that maintained similar income trends. 

The data is stored in your environment as the data.matrix `oes`.

```{r}
oes <- readRDS("data/oes.rds")
oes
```

Before you begin to cluster this data you should determine whether any pre-processing steps (such as scaling and imputation) are necessary.

> *Question*
> ---
> **Leverage the functions `head()` and `summary()` to explore the `oes` data in order to determine which of the pre-processing steps below are necessary:**<br>
> <br>
> ⬜ *NA* values exist in the data, hence the values must be imputed or the observations with *NAs* excluded.<br>
> ⬜ The variables within this data are not comparable to one another and should be scaled.<br>
> ⬜ Categorical variables exist within this data and should be appropriately dummified.<br>
> ⬜ All three pre-processing steps above are necessary for this data.<br>
> ✅ None of these pre-processing steps are necessary for this data.<br>

Correct, there are no missing values, no categorical and the features are on the same scale. <br> Now you're ready to cluster this data!

## Hierarchical clustering: Occupation trees

In the previous exercise you have learned that the `oes` data is ready for hierarchical clustering without any preprocessing steps necessary. In this exercise you will take the necessary steps to build a dendrogram of occupations based on their yearly average salaries and propose clusters using a height of `100,000`.

**Steps**

1. Calculate the Euclidean distance between the occupations and store this in `dist_oes`
2. Run hierarchical clustering using **average** linkage and store in `hc_oes`
3. Create a denrogram object `dend_oes` from your `hclust` result using the function `as.dendrogram()`
4. Plot the dendrogram
5. Using the `color_branches()` function create & plot a new dendrogram with clusters colored by a cut height of 100,000

```{r}
# Calculate Euclidean distance between the occupations
dist_oes <- dist(oes, method = 'euclidean')

# Generate an average linkage analysis 
hc_oes <- hclust(dist_oes, method = 'average')

# Create a dendrogram object from the hclust variable
dend_oes <- as.dendrogram(hc_oes)

# Plot the dendrogram
plot(dend_oes)

# Color branches by cluster formed from the cut at a height of 100000
dend_colored <- color_branches(dend_oes, h = 100000)

# Plot the colored dendrogram
plot(dend_colored)
```

Well done! Based on the dendrogram it may be reasonable to start with the three clusters formed at a height of 100,000. The members of these clusters appear to be tightly grouped but different from one another. Let's continue this exploration.

## Hierarchical clustering: Preparing for exploration

You have now created a potential clustering for the `oes` data, before you can explore these clusters with ggplot2 you will need to process the `oes` data matrix into a tidy data frame with each occupation assigned its cluster.

**Steps**

1. Create the `df_oes` data frame from the `oes` data.matrix, making sure to store the rowname as a column (use `rownames_to_column()` from the `tibble` library)
2. Build the cluster assignment vector `cut_oes` using `cutree()` with a `h = 100,000`
3. Append the cluster assignments as a column `cluster` to the `df_oes` data frame and save the results to a new data frame called `clust_oes`
4. Use the `gather()` function from the `tidyr()` library to reshape the data into a format amenable for ggplot2 analysis and save the tidied data frame as `gather_oes`

```{r}
# Load package
library(tidyr)

dist_oes <- dist(oes,        method = 'euclidean')
hc_oes   <- hclust(dist_oes, method = 'average')

# Use rownames_to_column to move the rownames into a column of the data frame
df_oes <- rownames_to_column(as.data.frame(oes), var = 'occupation')

# Create a cluster assignment vector at h = 100,000
cut_oes <- cutree(hc_oes, h = 100000)

# Generate the segmented the oes data frame
clust_oes <- mutate(df_oes, cluster = cut_oes)

# Create a tidy data frame by gathering the year and values into two columns
gathered_oes <- gather(data = clust_oes, 
                       key = year, 
                       value = mean_salary, 
                       -occupation, -cluster)
```

Great work! You now have the data frames necessary to explore the results of this clustering

## Hierarchical clustering: Plotting occupational clusters

You have successfully created all the parts necessary to explore the results of this hierarchical clustering work. In this exercise you will leverage the named assignment vector `cut_oes` and the tidy data frame `gathered_oes` to analyze the resulting clusters.

**Steps**

1. View the assignments of each occupation to their clustering by sorting the `cut_oes` vector using `sort()`
2. Use ggplot2 to plot each occupation's average income by year and color the lines by the occupation's assigned cluster.

```{r}
# View the clustering assignments by sorting the cluster assignment vector
sort(cut_oes)

# Plot the relationship between mean_salary and year and color the lines by the assigned cluster
ggplot(gathered_oes, aes(x = year, y = mean_salary, color = factor(cluster))) + 
    geom_line(aes(group = occupation)) +
    theme_bw()
```

Cool huh! From this work it looks like both Management & Legal professions (cluster 1) experienced the most rapid growth in these 15 years.\nLet's see what we can get by exploring this data using k-means.

## Reviewing the HC results

Theory. Coming soon ...


**1. Reviewing the HC results**

Great job, you've successfully analyzed the occupational wage data using hierarchical clustering. Now, let's briefly discuss these results before moving on to kmeans clustering.

**2. The dendrogram**

Remember that this dendrogram was constructed using a euclidean distance and an average linkage criteria. What this means is that at the height of any given branch, all observations belonging to that branch must have an average euclidean distance amongst each other less than or equal to the height of that branch.Rather than using a pre-determined value of k when cutting the tree you used the structure of the tree to make the decision. A height of 100,000 seems reasonable when looking at this structure and generates three clusters. However, it would just be as reasonable to go higher to create two clusters or lower to create four. To better understand the consequence of the cut height, you explored the resulting clusters to see if they make sense.

**3. The trends**

More specifically you plotted the trends of these three clusters and used color to compare and contrast them. Visually this seems to be a reasonable clustering with three distinct trends or slopes that emerge from the three clusters.

**4. Connecting the two**

Based on this analysis one observation we can make is that two occupations concurrently had a higher growth in average wages relative to the others.These are the Management and Legal occupations. Good to know when planning a career trajectory huh?

**5. Next steps: k-means clustering**

Let's revisit this data through the lens of k-means clustering. In k-means analysis you would first need to determine if any pre-processing steps are necessary. However we have already explored this in the hierarchical clustering work and know that the data can be used as is.So the first step will be to empirically estimate the value of k using the two methods you have learned about, the elbow plot and the maximum average silhouette width.Finally, as with any good clustering analysis, you will analyze your resulting clusters to see they make sense and find out what you can learn from them.

**6. Let's cluster!**

Let's cluster.

## K-means: Elbow analysis

In the previous exercises you used the dendrogram to propose a clustering that generated 3 trees. In this exercise you will leverage the k-means elbow plot to propose the "best" number of clusters.

**Steps**

1. Use `map_dbl()` to run `kmeans()` using the `oes` data for k values ranging from 1 to 10 and extract the **total within-cluster sum of squares** value from each model: `model$tot.withinss`\nStore the resulting vector as `tot_withinss`  
2. Build a new data frame `elbow_df` containing the values of k and the vector of **total within-cluster sum of squares**  
3. Use the values in `elbow_df` to plot a line plot showing the relationship between **k** and **total within-cluster sum of squares**

```{r}
# Use map_dbl to run many models with varying value of k (centers)
tot_withinss <- map_dbl(1:10,  function(k){
  model <- kmeans(x = oes, centers = k)
  model$tot.withinss
})

# Generate a data frame containing both k and tot_withinss
elbow_df <- data.frame(
  k = 1:10,
  tot_withinss = tot_withinss
)

# Plot the elbow plot
ggplot(elbow_df, aes(x = k, y = tot_withinss)) +
  geom_line() +
  scale_x_continuous(breaks = 1:10) +
  theme_bw()
```

Fascinating! So the elbow analysis proposes a different value of **k**, in the next section let's see what we can learn from Silhouette Width Analysis.

## K-means: Average Silhouette Widths

So hierarchical clustering resulting in **3** clusters and the elbow method suggests **2**. In this exercise use **average silhouette widths** to explore what the "best" value of **k** should be.

**Steps**

1. Use `map_dbl()` to run `pam()` using the `oes` data for k values ranging from 2 to 10 and extract the **average silhouette width** value from each model: `model$silinfo$avg.width`\nStore the resulting vector as `sil_width`  
2. Build a new data frame `sil_df` containing the values of k and the vector of **average silhouette widths**  
3. Use the values in `sil_df` to plot a line plot showing the relationship between **k** and **average silhouette width**

```{r}
# Use map_dbl to run many models with varying value of k
sil_width <- map_dbl(2:10,  function(k){
  model <- pam(oes, k = k)
  model$silinfo$avg.width
})

# Generate a data frame containing both k and sil_width
sil_df <- data.frame(
  k = 2:10,
  sil_width = sil_width
)

# Plot the relationship between k and sil_width
ggplot(sil_df, aes(x = k, y = sil_width)) +
  geom_line() +
  scale_x_continuous(breaks = 2:10) +
  theme_bw()
```

Great work! It seems that this analysis results in another value of **k**, this time 7 is the top contender (although 2 comes very close).

## The "best" number of clusters

You ran three different methods for finding the optimal number of clusters and their assignments and you arrived with three different answers.

Below you will find a comparison between the 3 clustering results (via coloring of the occupations based on the clusters to which they belong).

<img src="http://assets.datacamp.com/production/course_5776/datasets/c4_e09.png" alt="oes_clusters">

> *Question*
> ---
> **What can you say about the "best" way to cluster this data?**<br>
> <br>
> ⬜ The clusters generated by the hierarchical clustering all have members with a Euclidean distance amongst one another less than 100,000 and hence is the **best** clustering method.<br>
> ⬜ The clusters generated using k-means with a **k = 2** was identified using elbow analysis and hence is the **best** way to cluster this data.<br>
> ⬜ The clusters generated using k-means with a **k = 7** has the largest Average Silhouette Widths among the cluster and hence is the **best** way to cluster this data.<br>
> ✅ All of the above are correct but the **best** way to cluster is highly dependent on how you would use this data after.<br>

All 3 statements are correct but there is no quantitative way to determine which of these clustering approaches is the right one without further exploration.


## Review K-means results

Theory. Coming soon ...


**1. Review K-means results**

I don't know about you, but the results of the last exercise were a little unexpected! You used three approaches for finding clusters and got three completely different answers.Which of them is the right one?

**2. Three clustering results**

If there is one point that I want you to remember from this class, is that the answer is always it depends.It depends on the clustering setup, it depends on the question we are trying to answer and it depends on our understanding of the data that we are working with.To say it another way, clustering methods require a certain amount of subjectivity. They are the looking glass through which we can see a new perspective on our data but it is up to us to judiciously use this perspective.In this case if you would ask for my opinion, I would say that the analysis of the hierarchical based clustering seems to make the most sense here. The three distinct clusters of occupations grouped similar slopes of wage growth effectively while separating the unique trends that appear.

**3. Comparing the two clustering methods**

Is this always the case? What are the differences between k-means and hierarchical clustering?Well there are some fundamental differences between the two.kmeans relies exclusively on euclidean distance whereas hierarchical clustering can handle virtually any distance metric.kmeans requires a random step that may yield different results if the process is re-run, this would not occur in hierarchical clustering.to estimate the value of k, we can use silhouette analysis and the elbow method for k-means, but the same could be said for hierarchical clustering which additionally has the added benefit of leveraging the dendrogramSo why would we ever use k-means clustering instead of hierarchical clustering. The main reason is that the k-means algorithm is less computationally expensive and can be run on much larger data within a reasonable time frame. This is the reason that this algorithm maintains such wide use and popularity.

**4. What have you learned?**

I hope you enjoyed this journey to develop the tools and intuition for working with unsupervised clustering as much as I did.In chapter one you learned the central concept to all clustering, distance. You also learned how important scale can be when calculating distance.In chapter two you learned the fundamentals of hierarchical clustering where you utilized distance to iteratively build a dendrogram and then break it down into clusters.In chapter three you worked with the k-means clustering method and learned about its associated tools.You learned a lot, you should give yourself a pat on the back.

**5. A lot more to learn**

Of course this is only the beginning of your journey. These are just some of the tools you may encounter as you delve further into the world of unsupervised clustering.As a bonus, the pam function you used for silhouette analysis actually used the k-mediods method. Its very similar to k-means except that it can accommodate distance matrices with arbitrary distances just like hierarchical clustering. You should try it out.Two other methods you might be interested in are DBSCAN and Optics clustering, both are very commonly used algorithms that we sadly don't have time for in this course but I strongly encourage you to take what you've learned here to pursue them.

**6. Congratulations!**

If I can leave you with one parting thought that has helped me along my path in data science. Remember that building intuition for your methods is just as, if not more important than learning how to use their associated tools. Like the explorers of old, we data scientists have a lot of uncharted waters ahead of us, best we understand how our ship works.

