Learn how to do K-Means Clustering with better centroid selection.

K-Means++ Clustering

Congratulations, now your K-Means model is improved and ready to go!

K-Means++ improves K-Means by placing initial centroids more strategically. As a result, it can result in more optimal clusterings than K-Means.

It can also outperform K-Means in speed. If you get very unlucky initial centroids using K-Means, the algorithm can take a long time to converge. K-Means++ will often converge quicker!

You can implement K-Means++ with the <a href="https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html" target="_blank">scikit-learn</a> library similar to how you implement K-Means.

The `KMeans()` function has an `init` parameter, which specifies the method for initialization:

- `'random'`
- `'k-means++'`

**Note:** scikit-learn's `KMeans()` uses `'k-means++'` by default, but it is a good idea to be explicit!

Review

Suppose we have four data samples that form a rectangle whose width is greater than its height:

<img src="https://content.codecademy.com/programs/machine-learning/k-means-plus-plus/no_clusers.png" title="Data Points in Rectangle Shape" />

If you wanted to find two clusters (`k` = 2) in the data, which points would you cluster together? You might guess the points that align vertically cluster together, since the height of the rectangle is smaller than its width. We end up with a left cluster (purple points) and a right cluster (yellow points).

<img src="https://content.codecademy.com/programs/machine-learning/k-means-plus-plus/correct.png" title="Optimal Cluster" />

Let's say we use the regular K-Means algorithm to cluster the points, where the cluster centroids are initialized randomly. We get unlucky and those randomly initialized cluster centroids happen to be the midpoints of the top and bottom line segments of the rectangle formed by the four data points. 

<img src="https://content.codecademy.com/programs/machine-learning/k-means-plus-plus/poor_cluster.png" title="Random Centroid Placement" />

The algorithm would converge immediately, without moving the cluster centroids. Consequently, the two top data points are clustered together (yellow points) and the two bottom data points are clustered together (purple points).

<img src="https://content.codecademy.com/programs/machine-learning/k-means-plus-plus/final_cluster.png" title="Suboptimal Clusters" />

This is a *suboptimal clustering* because the width of the rectangle is greater than its height. The optimal clusters would be the two left points as one cluster and the two right points as one cluster, as we thought earlier.

Poor Clustering

Using the <a href="http://scikit-learn.org/stable/" target="_blank">scikit-learn</a> library and its `cluster` module , you can use the `KMeans()` method to build an original K-Means model that finds 6 clusters like so:

```py
model = KMeans(n_clusters=6, init='random')
```

The `init` parameter is used to specify the initialization and `init='random'` specifies that initial centroids are chosen as random (the original K-Means).

But how do you implement K-Means++?

There are two ways and they both require little change to the syntax:

**Option 1:** You can adjust the parameter to `init='k-means++'`.

```py
test = KMeans(n_clusters=6, init='k-means++')
```

**Option 2:** Simply drop the parameter.

```py
test = KMeans(n_clusters=6)
```

This is because that `init=k-means++` is actually *default* in scikit-learn.



K-Means++ using Scikit-Learn

To recap, the Step 1 of the K-Means algorithm is "Place `k` random centroids for the initial clusters".

The K-Means++ algorithm replaces Step 1 of the K-Means algorithm and adds the following:

- **1.1** The first cluster centroid is randomly picked from the data points.
- **1.2** For each remaining data point, the distance from the point to its nearest cluster centroid is calculated.
- **1.3** The next cluster centroid is picked according to a probability proportional to the distance of each point to its nearest cluster centroid. This makes it likely for the next cluster centroid to be far away from the already initialized centroids.

**Repeat 1.2 - 1.3** until `k` centroids are chosen.


What is K-Means++?

The K-Means clustering algorithm is more than half a century old, but it is not falling out of fashion; it is still the most popular clustering algorithm for Machine Learning.

However, there can be some problems with its first step. In the traditional K-Means algorithms, the starting postitions of the centroids are intialized completely randomly. This can result in suboptimal clusters.

In this lesson, we will go over another version of K-Means, known as the **K-Means++ algorithm**. K-Means++ changes the way centroids are initalized to try to fix this problem.