In the previous few sections, we have explored one category of unsupervised machine learning models: dimensionality reduction. Here we will move on to another class of unsupervised machine learning models: clustering algorithms. Clustering algorithms seek to learn, from the properties of the data, an optimal division or discrete labeling of groups of points.
Many clustering algorithms are available in Scikit-Learn and elsewhere, but perhaps the simplest to understand is an algorithm known as k-means clustering, which is implemented in sklearn.cluster.KMeans. We begin with the standard imports:
- %matplotlib inline
- import matplotlib.pyplot as plt
- import seaborn as sns; sns.set() # for plot styling
- import numpy as np
The k-means algorithm searches for a predetermined number of clusters within an unlabeled multidimensional dataset. It accomplishes this using a simple conception of what the optimal clustering looks like:
Those two assumptions are the basis of the k-means model. We will soon dive into exactly how the algorithm reaches this solution, but for now let’s take a look at a simple dataset and see the k-means result. First, let’s generate a two-dimensional dataset containing four distinct blobs. To emphasize that this is an unsupervised algorithm, we will leave the labels out of the visualization (Figure 5-110):
- from sklearn.datasets.samples_generator import make_blobs
- X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
- plt.scatter(X[:, 0], X[:, 1], s=50);
Figure 5-110. Data for demonstration of clustering
By eye, it is relatively easy to pick out the four clusters. The k-means algorithm does this automatically, and in Scikit-Learn uses the typical estimator API:
- from sklearn.cluster import KMeans
- kmeans = KMeans(n_clusters=4)
- kmeans.fit(X)
- y_kmeans = kmeans.predict(X)
- plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
- centers = kmeans.cluster_centers_
- plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.5);
Figure 5-111. k-means cluster centers with clusters indicated by color
The good news is that the k-means algorithm (at least in this simple case) assigns the points to clusters very similarly to how we might assign them by eye. But you might wonder how this algorithm finds these clusters so quickly! After all, the number of possible combinations of cluster assignments is exponential in the number of data points—an exhaustive search would be very, very costly. Fortunately for us, such an exhaustive search is not necessary; instead, the typical approach to k-means involves an intuitive iterative approach known as expectation–maximization.
k-Means Algorithm: Expectation–Maximization
Expectation–maximization (E–M) is a powerful algorithm that comes up in a variety of contexts within data science. k-means is a particularly simple and easy-to understand application of the algorithm, and we will walk through it briefly here. In short, the expectation–maximization approach consists of the following procedure:
Here the “E-step” or “Expectation step” is so named because it involves updating our expectation of which cluster each point belongs to. The “M-step” or “Maximization step” is so named because it involves maximizing some fitness function that defines the location of the cluster centers—in this case, that maximization is accomplished by taking a simple mean of the data in each cluster.
The literature about this algorithm is vast, but can be summarized as follows: under typical circumstances, each repetition of the E-step and M-step will always result in a better estimate of the cluster characteristics. We can visualize the algorithm as shown in Figure 5-112.
For the particular initialization shown here, the clusters converge in just three iterations. For an interactive version of this figure, refer to the code in the online appendix.
The k-means algorithm is simple enough that we can write it in a few lines of code. The following is a very basic implementation (Figure 5-113):
- from sklearn.metrics import pairwise_distances_argmin
- def find_clusters(X, n_clusters, rseed=2):
- # 1. Randomly choose clusters
- rng = np.random.RandomState(rseed)
- i = rng.permutation(X.shape[0])[:n_clusters]
- centers = X[i]
- while True:
- # 2a. Assign labels based on closest centersr
- labels = pairwise_distances_argmin(X, centers)
- # 2b. Find new centers from means of points
- new_centers = np.array([X[labels == i].mean(0) for i in range(n_clusters)])
- # 2c. Check for convergence
- if np.all(centers == new_centers):
- break
- centers = new_centers
- return centers, labels
- centers, labels = find_clusters(X, 4)
- plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis');
Most well-tested implementations will do a bit more than this under the hood, but the preceding function gives the gist of the expectation–maximization approach.
Caveats of expectation–maximization
There are a few issues to be aware of when using the expectation–maximization algorithm. The globally optimal result may not be achieved!
First, although the E–M procedure is guaranteed to improve the result in each step, there is no assurance that it will lead to the global best solution. For example, if we use a different random seed in our simple procedure, the particular starting guesses lead to poor results (Figure 5-114):
Figure 5-114. An example of poor convergence in k-means
Here the E–M approach has converged, but has not converged to a globally optimal configuration. For this reason, it is common for the algorithm to be run for multiple starting guesses, as indeed Scikit-Learn does by default (set by the n_init parameter, which defaults to 10).
The number of clusters must be selected beforehand
Another common challenge with k-means is that you must tell it how many clusters you expect: it cannot learn the number of clusters from the data. For example, if we ask the algorithm to identify six clusters, it will happily proceed and find the best six clusters (Figure 5-115):
- labels = KMeans(6, random_state=0).fit_predict(X)
- plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis');
Figure 5-115. An example where the number of clusters is chosen poorly
Whether the result is meaningful is a question that is difficult to answer definitively; one approach that is rather intuitive, but that we won’t discuss further here, is called silhouette analysis.
Alternatively, you might use a more complicated clustering algorithm which has a better quantitative measure of the fitness per number of clusters (e.g., Gaussian mixture models; see “In Depth: Gaussian Mixture Models”) or which can choose a suitable number of clusters (e.g., DBSCAN, mean-shift, or affinity propagation, all available in the sklearn.cluster submodule).
k-means is limited to linear cluster boundaries
The fundamental model assumptions of k-means (points will be closer to their own cluster center than to others) means that the algorithm will often be ineffective if the clusters have complicated geometries. In particular, the boundaries between k-means clusters will always be linear, which means that it will fail for more complicated boundaries. Consider the following data, along with the cluster labels found by the typical k-means approach (Figure 5-116):
- from sklearn.datasets import make_moons
- X, y = make_moons(200, noise=.05, random_state=0)
- labels = KMeans(2, random_state=0).fit_predict(X)
- plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis');
Figure 5-116. Failure of k-means with nonlinear boundaries
This situation is reminiscent of the discussion in “In-Depth: Support Vector Machines” , where we used a kernel transformation to project the data into a higher dimension where a linear separation is possible. We might imagine using the same trick to allow k-means to discover nonlinear boundaries.
One version of this kernelized k-means is implemented in Scikit-Learn within the SpectralClustering estimator. It uses the graph of nearest neighbors to compute a higher-dimensional representation of the data, and then assigns labels using a k-means algorithm (Figure 5-117):
- from sklearn.cluster import SpectralClustering
- model = SpectralClustering(n_clusters=2, affinity='nearest_neighbors', assign_labels='kmeans')
- labels = model.fit_predict(X)
- plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis');
Figure 5-117. Nonlinear boundaries learned by SpectralClustering
We see that with this kernel transform approach, the kernelized k-means is able to find the more complicated nonlinear boundaries between clusters.
k-means can be slow for large numbers of samples
Because each iteration of k-means must access every point in the dataset, the algorithm can be relatively slow as the number of samples grows. You might wonder if this requirement to use all data at each iteration can be relaxed; for example, you might just use a subset of the data to update the cluster centers at each step. This is the idea behind batch-based k-means algorithms, one form of which is implemented in sklearn.cluster.MiniBatchKMeans. The interface for this is the same as for standard KMeans; we will see an example of its use as we continue our discussion.
Examples
Being careful about these limitations of the algorithm, we can use k-means to our advantage in a wide variety of situations. We’ll now take a look at a couple examples.
Example 1: k-Means on digits
To start, let’s take a look at applying k-means on the same simple digits data that we saw in “In-Depth: Decision Trees and Random Forests” and “In Depth: Principal Component Analysis”. Here we will attempt to use k-means to try to identify similar digits without using the original label information; this might be similar to a first step in extracting meaning from a new dataset about which you don’t have any a priori label information.
We will start by loading the digits and then finding the KMeans clusters. Recall that the digits consist of 1,797 samples with 64 features, where each of the 64 features is the brightness of one pixel in an 8×8 image:
- from sklearn.datasets import load_digits
- digits = load_digits()
- digits.data.shape
The clustering can be performed as we did before:
- kmeans = KMeans(n_clusters=10, random_state=0)
- clusters = kmeans.fit_predict(digits.data)
- kmeans.cluster_centers_.shape
The result is 10 clusters in 64 dimensions. Notice that the cluster centers themselves are 64-dimensional points, and can themselves be interpreted as the “typical” digit within the cluster. Let’s see what these cluster centers look like (Figure 5-118):
- fig, ax = plt.subplots(2, 5, figsize=(8, 3))
- centers = kmeans.cluster_centers_.reshape(10, 8, 8)
- for axi, center in zip(ax.flat, centers):
- axi.set(xticks=[], yticks=[])
- axi.imshow(center, interpolation='nearest', cmap=plt.cm.binary)
Figure 5-118. Cluster centers learned by k-means
We see that even without the labels, KMeans is able to find clusters whose centers are recognizable digits, with perhaps the exception of 1 and 8.
Because k-means knows nothing about the identity of the cluster, the 0–9 labels may be permuted. We can fix this by matching each learned cluster label with the true labels found in them:
- from scipy.stats import mode
- labels = np.zeros_like(clusters)
- for i in range(10):
- mask = (clusters == i)
- labels[mask] = mode(digits.target[mask])[0]
- ''' Use the majority of labels from cluster to give the label to the cluster '''
- from sklearn.metrics import accuracy_score
- accuracy_score(digits.target, labels)
With just a simple k-means algorithm, we discovered the correct grouping for 80% of the input digits! Let’s check the confusion matrix for this (Figure 5-119):
- from sklearn.metrics import confusion_matrix
- mat = confusion_matrix(digits.target, labels)
- sns.heatmap(mat.T, square=True, annot=True, fmt='d', cbar=False,
- xticklabels=digits.target_names,
- yticklabels=digits.target_names)
- plt.xlabel('true label')
- plt.ylabel('predicted label');
Figure 5-119. Confusion matrix for the k-means classifier
As we might expect from the cluster centers we visualized before, the main point of confusion is between the eights and ones. But this still shows that using k-means, we can essentially build a digit classifier without reference to any known labels!
Just for fun, let’s try to push this even further. We can use the t-distributed stochastic neighbor embedding (t-SNE) algorithm (mentioned in “In-Depth: Manifold Learning” ) to preprocess the data before performing k-means. t-SNE is a nonlinear embedding algorithm that is particularly adept at preserving points within clusters. Let’s see how it does:
- from sklearn.manifold import TSNE
- # Project the data: this step will take several seconds
- tsne = TSNE(n_components=2, init='pca', random_state=0)
- digits_proj = tsne.fit_transform(digits.data)
- # Compute the clusters
- kmeans = KMeans(n_clusters=10, random_state=0)
- clusters = kmeans.fit_predict(digits_proj)
- # Permute the labels
- labels = np.zeros_like(clusters)
- for i in range(10):
- mask = (clusters == i)
- labels[mask] = mode(digits.target[mask])[0]
- # Compute the accuracy
- accuracy_score(digits.target, labels)
That’s nearly 94% classification accuracy without using the labels. This is the power of unsupervised learning when used carefully: it can extract information from the dataset that it might be difficult to do by hand or by eye.
Example 2: k-means for color compression
One interesting application of clustering is in color compression within images. For example, imagine you have an image with millions of colors. In most images, a large number of the colors will be unused, and many of the pixels in the image will have similar or even identical colors. For example, consider the image shown in Figure 5-120, which is from Scikit-Learn’s datasets module (for this to work, you’ll have to have the pillow Python package installed):
- # Note: this requires the pillow package to be installed
- from sklearn.datasets import load_sample_image
- china = load_sample_image("china.jpg")
- ax = plt.axes(xticks=[], yticks=[])
- ax.imshow(china);
Figure 5-120. The input image
The image itself is stored in a three-dimensional array of size (height, width, RGB), containing red/blue/green contributions as integers from 0 to 255:
- china.shape
One way we can view this set of pixels is as a cloud of points in a three-dimensional color space. We will reshape the data to [n_samples x n_features], and rescale the colors so that they lie between 0 and 1:
- data = china / 255.0 # use 0...1 scale
- data = data.reshape(427 * 640, 3)
- data.shape
We can visualize these pixels in this color space, using a subset of 10,000 pixels for efficiency (Figure 5-121):
- def plot_pixels(data, title, colors=None, N=10000):
- if colors is None:
- colors = data
- # choose a random subset
- rng = np.random.RandomState(0)
- i = rng.permutation(data.shape[0])[:N]
- colors = colors[i]
- R, G, B = data[i].T
- fig, ax = plt.subplots(1, 2, figsize=(12, 6))
- ax[0].scatter(R, G, color=colors, marker='.')
- ax[0].set(xlabel='Red', ylabel='Green', xlim=(0, 1), ylim=(0, 1))
- ax[1].scatter(R, B, color=colors, marker='.')
- ax[1].set(xlabel='Red', ylabel='Blue', xlim=(0, 1), ylim=(0, 1))
- fig.suptitle(title, size=20);
- plot_pixels(data, title='Input color space: 16 million possible colors')
Figure 5-121. The distribution of the pixels in RGB color space
Now let’s reduce these 16 million colors to just 16 colors, using a k-means clustering across the pixel space. Because we are dealing with a very large dataset, we will use the mini batch k-means, which operates on subsets of the data to compute the result much more quickly than the standard k-means algorithm (Figure 5-122):
- from sklearn.cluster import MiniBatchKMeans
- kmeans = MiniBatchKMeans(16)
- kmeans.fit(data)
- new_colors = kmeans.cluster_centers_[kmeans.predict(data)]
- plot_pixels(data, colors=new_colors, title="Reduced color space: 16 colors")
Figure 5-122. 16 clusters in RGB color space
The result is a recoloring of the original pixels, where each pixel is assigned the color of its closest cluster center. Plotting these new colors in the image space rather than the pixel space shows us the effect of this (Figure 5-123):
- china_recolored = new_colors.reshape(china.shape)
- fig, ax = plt.subplots(1, 2, figsize=(16, 6),
- subplot_kw=dict(xticks=[], yticks=[]))
- fig.subplots_adjust(wspace=0.05)
- ax[0].imshow(china)
- ax[0].set_title('Original Image', size=16)
- ax[1].imshow(china_recolored)
- ax[1].set_title('16-color Image', size=16);
Figure 5-123. A comparison of the full-color image (left) and the 16-color image (right)
Some detail is certainly lost in the rightmost panel, but the overall image is still easily recognizable. This image on the right achieves a compression factor of around 1 million! While this is an interesting application of k-means, there are certainly better way to compress information in images. But the example shows the power of thinking outside of the box with unsupervised methods like k-means
沒有留言:
張貼留言