Clustering is the most well-known unsupervised learning technique. It finds structure in unlabeled data by identifying similar groups, or clusters.

K-Means Clustering

The K-Means algorithm:

1. Place `k` random centroids for the initial clusters.
2. **Assign data samples to the nearest centroid.**
3. Update centroids based on the above-assigned data samples.

Repeat Steps 2 and 3 until convergence.

---

In this exercise, we will implement Step 2.

Now we have the three random centroids. Let's assign data points to their nearest centroids. 

To do this we're going to use a <a href="https://en.wikipedia.org/wiki/Distance" target="_blank">Distance Formula</a> to write a `distance()` function. Then, we are going to iterate through our data samples and compute the distance from each data point to each of the 3 centroids.

Suppose we have a point and a list of three distances in `distances` and it looks like `[15, 20, 5]`, then we would want to assign the data point to the 3rd centroid. The `argmin(distances)` would return the index of the lowest corresponding distance, `2`, because the index `2` contains the minimum value.

Implementing K-Means: Step 2

To get a better sense of the data in the `iris.data` matrix, let's visualize it!

With Matplotlib, we can create a 2D scatter plot of the Iris dataset using two of its features (sepal length vs. petal length). The sepal length measurements are stored in column `0` of the matrix, and the petal length measurements are stored in column `2` of the matrix.

But how do we get these values?

Suppose we only want to retrieve the values that are in column `0` of a matrix, we can use the NumPy/pandas notation `[:,0]` like so:

```py
matrix[:,0]
```

`[:,0]` can be translated to `[all_rows , column_0]`

Once you have the measurements we need, we can make a scatter plot like this:

```py
plt.scatter(x, y)
```

To show the plot:

```py
plt.show()
```

Let's try this! But this time, plot the sepal length (column `0`) vs. sepal width (column `1`) instead.


Visualize Before K-Means

You used K-Means and found three clusters of the `samples` data. But it gets cooler!

Since you have created a model that computed K-Means clustering, you can now feed *new* data samples into it and obtain the cluster labels using the `.predict()` method.

So, suppose we went to the florist and bought 3 more Irises with the measurements:

```py
[[ 5.1  3.5  1.4  0.2 ]
 [ 3.4  3.1  1.6  0.3 ]
 [ 4.9  3.   1.4  0.2 ]]
```

We can feed this new data into the model and obtain the labels for them.


New Data?

Now it is your turn! 

In this review section, find another dataset from one of the following:

- The <a href="http://scikit-learn.org/stable/datasets/index.html" target="_blank">scikit-learn</a> library
-  <a href="https://archive.ics.uci.edu/ml/index.php" target="_blank">UCI Machine Learning Repo</a>
- Codecademy GitHub Repo (coming soon!)

Import the `pandas` library as `pd`:

```py
import pandas as pd
```

Load in the data with `read_csv()`:

```py
digits = pd.read_csv("http://archive.ics.uci.edu/ml/machine-learning-databases/optdigits/optdigits.tra", header=None)
```

Note that if you download the data like this, the data is already split up into a training and a test set, indicated by the extensions **.tra** and **.tes**. You’ll need to load in both files. 

With the command above, you only load in the training set.

Happy Coding!



Try It On Your Own

At this point, we have grouped the Iris plants into 3 clusters. But suppose we didn't know there are three species of Iris in the dataset, what is the best number of clusters? And how do we determine that?

Before we answer that, we need to define what is a *good* cluster?

Good clustering results in tight clusters, meaning that the samples in each cluster are bunched together. How spread out the clusters are is measured by *inertia*. Inertia is the distance from each sample to the centroid of its cluster. The lower the inertia is, the better our model has done.

You can check the inertia of a model by:

```py
print(model.inertia_)
```

For the Iris dataset, if we graph all the `k`s (number of clusters) with their inertias:

<img src="https://content.codecademy.com/programs/machine-learning/k-means/number-of-clusters.svg" title="Where is the elbow?" alt="Optimal Number of Clusters"/>

Notice how the graph keeps decreasing. 

Ultimately, this will always be a trade-off. The goal is to have low inertia *and* the least number of clusters.

One of the ways to interpret this graph is to use the *elbow method*: choose an "elbow" in the inertia plot - when inertia begins to decrease more slowly.

In the graph above, 3 is the optimal number of clusters.



The Number of Clusters

At this point, we have clustered the Iris data into 3 different groups (implemented using Python and using scikit-learn). But do the clusters correspond to the actual species? Let's find out!

First, remember that the Iris dataset comes with target values:

```py
target = iris.target
```

It looks like:

```py
[ 0 0 0 0 0 ... 2 2 2]
```

According to the metadata:
- All the `0`'s are *Iris-setosa*
- All the `1`'s are *Iris-versicolor*
- All the `2`'s are *Iris-virginica*

Let's change these values into the corresponding species using the following code:

```py
species = np.chararray(target.shape, itemsize=150)

for i in range(len(samples)):
  if target[i] == 0:
    species[i] = 'setosa'
  elif target[i] == 1:
    species[i] = 'versicolor'
  elif target[i] == 2: 
    species[i] = 'virginica'
```

Then we are going to use the Pandas library to perform a *cross-tabulation*. 

Cross-tabulations enable you to examine relationships within the data that might not be readily apparent when analyzing total survey responses.

The result should look something like:

```bash
labels    setosa    versicolor    virginica
0             50             0            0
1              0             2           36
2              0            48           14
```

(You might need to expand this narrative panel in order to the read the table better.)

The first column has the cluster labels. The second to fourth columns have the Iris species that are clustered into each of the labels.

By looking at this, you can conclude that: 
- *Iris-setosa* was clustered with 100% accuracy.
- *Iris-versicolor* was clustered with 96% accuracy.
- *Iris-virginica* didn't do so well.
 
Follow the instructions below to learn how to do a cross-tabulation.


Evaluation

The K-Means algorithm:

1. **Place `k` random centroids for the initial clusters.**
2. Assign data samples to the nearest centroid.
3. Update centroids based on the above-assigned data samples.

Repeat Steps 2 and 3 until convergence.

---

After looking at the scatter plot and having a better understanding of the Iris data, let's start implementing the K-Means algorithm.

In this exercise, we will implement Step 1.

Because we expect there to be three clusters (for the three species of flowers), let's implement K-Means where the `k` is 3. 

Using the NumPy library, we will create three *random* initial centroids and plot them along with our samples.


Implementing K-Means: Step 1

Before we implement the K-means algorithm, let's find a dataset. The `sklearn` package embeds some datasets and sample images. One of them is the <a href="https://en.wikipedia.org/wiki/Iris_flower_data_set" target="_blank">Iris dataset</a>.

The Iris dataset consists of measurements of sepals and petals of 3 different plant species:

- *Iris setosa*
- *Iris versicolor*
- *Iris virginica*

<img src="https://content.codecademy.com/programs/machine-learning/k-means/iris.svg" title="Iris" />

The sepal is the part that encases and protects the flower when it is in the bud stage. A petal is a leaflike part that is often colorful.

From `sklearn` library, import the `datasets` module:

```py
from sklearn import datasets
```

To load the Iris dataset:

```py
iris = datasets.load_iris()
```

The Iris dataset looks like:

```py
[[ 5.1  3.5  1.4  0.2 ]
 [ 4.9  3.   1.4  0.2 ]
 [ 4.7  3.2  1.3  0.2 ]
 [ 4.6  3.1  1.5  0.2 ]
   . . .
 [ 5.9  3.   5.1  1.8 ]]
```

We call each piece of data a _sample_. For example, each flower is one sample.

Each characteristic we are interested in is a _feature_. For example, petal length is a feature of this dataset.

The features of the dataset are:

- **Column 0:** Sepal length
- **Column 1:** Sepal width
- **Column 2:** Petal length
- **Column 3:** Petal width

The 3 species of Iris plants are what we are going to cluster later in this lesson.



Iris Dataset

The K-Means algorithm:

1. Place `k` random centroids for the initial clusters.
2. Assign data samples to the nearest centroid.
3. Update centroids based on the above-assigned data samples.

**Repeat Steps 2 and 3 until convergence.**

---

In this exercise, we will implement Step 4.

This is the part of the algorithm where we repeatedly execute Step 2 and 3 until the centroids stabilize (convergence). 

We can do this using a `while` loop. And everything from Step 2 and 3 goes inside the loop.

For the condition of the `while` loop, we need to create an array named `errors`. In each `error` index, we calculate the difference between the updated centroid (`centroids`) and the old centroid (`centroids_old`).

The loop ends when all three values in `errors` are `0`.

Implementing K-Means: Step 4

1. Place k random centroids for the initial clusters. 2. Assign data samples to the nearest centroid. 3. Update centroids based on the newly assigned samples.

The goal of clustering is to separate data so that data similar to one another are in the same group, while data different from one another are in different groups. So two questions arise:

- How many groups do we choose?
- How do we define similarity?

_K-Means_ is the most popular and well-known clustering algorithm, and it tries to address these two questions.

- The "K" refers to the number of clusters (groups) we expect to find in a dataset.
- The "Means" refers to the average distance of data to each cluster center, also known as the *centroid*, which we are trying to minimize. 

It is an iterative approach:

1. Place `k` random centroids for the initial clusters.
2. Assign data samples to the nearest centroid.
3. Update centroids based on the above-assigned data samples.

Repeat Steps 2 and 3 until *convergence* (when points don't move between clusters and centroids stabilize).

Once we are happy with our clusters, we can take a new unlabeled datapoint and quickly assign it to the appropriate cluster.


We have done the following using `sklearn` library:

- Load the embedded dataset
- Compute K-Means on the dataset (where `k` is 3)
- Predict the labels of the data samples

And the labels resulted in either `0`, `1`, or `2`.

Let's finish it by making a scatter plot of the data again! 

This time, however, use the `labels` numbers as the colors.

To edit colors of the scatter plot, we can set `c = labels`:

```py
plt.scatter(x, y, c=labels, alpha=0.5)

plt.xlabel('sepal length (cm)')
plt.ylabel('sepal width (cm)')
```

Visualize After K-Means

Often, the data you encounter in the real world won't have flags attached and won't provide labeled answers to your question. Finding patterns in this type of data, unlabeled data, is a common theme in many machine learning applications. *Unsupervised Learning* is how we find patterns and structure in these data.

**Clustering** is the most well-known unsupervised learning technique. It finds structure in unlabeled data by identifying similar groups, or *clusters*.
Examples of clustering applications are:  

- **Recommendation engines:** group products to personalize the user experience
- **Search engines:** group news topics and search results
- **Market segmentation:** group customers based on geography, demography, and behaviors
- **Image segmentation:** medical imaging or road scene segmentation on self-driving cars

Let's get started!

Introduction to Clustering

The K-Means algorithm:

1. Place `k` random centroids for the initial clusters.
2. Assign data samples to the nearest centroid.
3. **Update centroids based on the above-assigned data samples.**

Repeat Steps 2 and 3 until convergence.

---

In this exercise, we will implement Step 3.

Find *new* cluster centers by taking the average of the assigned points. To find the average of the assigned points, we can use the `.mean()` function.

Implementing K-Means: Step 3

Awesome, you have implemented K-Means clustering from scratch! 

Writing an algorithm whenever you need it can be very time-consuming and you might make mistakes and typos along the way. We will now show you how to implement K-Means more efficiently – using the <a href="https://scikit-learn.org/stable/" target="_blank">scikit-learn</a> library.

Instead of implementing K-Means from scratch, the `sklearn.cluster` module has many methods that can do this for you.

To import `KMeans` from `sklearn.cluster`:

```py
from sklearn.cluster import KMeans
```

For Step 1, use the `KMeans()` method to build a model that finds `k` clusters. To specify the number of clusters (`k`), use the `n_clusters` keyword argument:

```py
model = KMeans(n_clusters = k)
```

For Steps 2 and 3, use the `.fit()` method to compute K-Means clustering:

```py
model.fit(X)
```

After K-Means, we can now predict the closest cluster each sample in X belongs to. Use the `.predict()` method to compute cluster centers and predict cluster index for each sample:

```py
model.predict(X)
```


