Announcements¶

• HW 2 is due Friday (2/10) at 8pm

• Upcoming office hours:

  • Tomorrow: Peer tutor Rohan Anand from 1:30-3pm in CCDS 16th floor
  • Tomorrow: Abhishek Tiwari from 3:30-4:30pm on CCDS 13th floor

• Read Tan, Steinbach, Karpatne, Kumar Chapter 7.3

Homework logistics¶

• Abhishek will take questions about converting to pdf during discussion today

• Please select the pages each question is on. Starting from hw2, I will deduct 10% from submissions that don't do this.

k-Means recap¶

Centroid and Variance¶

To measure how close or different many vectors are in space, let's define the idea of a dataset centroid.

Given a n different vectors x1,…,xn each with the same dimension d, the centroid is the average of the vectors taken componentwise.

In other words: the centroid is the "center of mass" of the dataset.

Next, we define the sample variance of a dataset {x1,…,xn} as:

In other words, the sample variance of the set of points is the average squared distance from each point to the centroid.

k-means Problem:

Find k points c1,…,ck (called centers, centroids, or means), so that the cost

is minimized.

The (approximate) k-means algorithm:

1. Pick k cluster centers \{{\bf c_1}, \dots, {\bf c_k}\}. These can be chosen randomly, or by some other method.
2. For each j, define the cluster X_j as the set of points in X that are closest to center {\bf c_k}.

(Nearer to {\bf c_k} than to any other center.) 3. For each j, redefine {\bf c_j} to be the center of mass of cluster X_j.
(In other words, {\bf c_j} is the mean of the vectors in X_j.) 4. Repeat (i.e., go to Step 2) until convergence.

7.6 Limitations of k-means¶

As you can see, k-means can work very well.

However, we don't have any guarantees on the performance of k-means.

In particular, there are various settings in which k-means can fail to do a good job.

1. k-means tries to find spherical clusters.

   Because each point is assigned to its closest center, the points in a cluster are implicitly assumed to be arranged in a sphere around the center.

2. k-means tries to find equal-sized clusters.

   For the same reason, the sizes of clusters are implicitly assumed to be approximately equal.

3. k-means is sensitive to the starting cluster centers.

   If the initial guess (Step 1) is a bad one, k-means may get "stuck" in a bad solution.

How can we avoid the kind of bad initialization we just saw?

A good strategy is to pick points that are distant to each other. This strategy is called "k-means++".

It works very well in practice, and the scikit-learn implementation uses it by default.

Feature Scaling¶

Given the tendency of k-means to look for spherical clusters, we should consider the scales of the various features.

In fact, in general when constructing or selecting a distance metric, one needs to think carefully about the scale of the features being used.

Example. Consider the case where we are clustering people based on their age, income, and whether they have children.

We might use age in years, income in dollars, and build an enumerated data type for existence of children.

Thus, the following records:

• Joe Smith, age 27, income USD 75,000, two children
• Eve Jones, age 45, income USD 42,000, no children

Would be encoded in feature space as:

What would happen if we used Euclidean distance as our dissimilarity metric in this feature space? (This is what k-means uses.)

Clearly, the influence of income would dominate the other two features. For example, a difference of parenthood is about as significant as a difference of one dollar of yearly income.

We are unlikely to expose parenting-based differences if we cluster using this representation.

The most common way to handle this is feature scaling.

The basic idea is to rescale each feature separately, so that its range of values is about the same as all other features.

For example, one may choose to:

• shift each feature independently by subtracting the mean over all observed values
  • This means that each feature is now centered on zero
• then rescale each feature so that the standard deviation overall observed values is 1.
  • This means that the feature will have about the same range of values as all the others.

Choosing the right k¶

Generally, we would say that, given some k, the k-means algorithm "learns" the cluster centers -- that is, the parameters of the model.

But we have not yet considered how to choose the right number of clusters.

That's typically not something one knows in advance.

As an aside:

• This parameter (k) is an example of a hyperparameter.
• A hyperparameter is a parameter that must be set before the model parameters can be learned.

Our basic strategy will be to

• Iterate through different k.
• Use some criterion to decide which k is most appropriate (we will discuss this next).

8. Cluster Evaluation¶

8.1 How useful are the clusters?¶

How do we know whether the clusters we get represent "real" structure in our data?

Consider this dataset, which we have clustered using k-means:

In fact, this dataset was generated using uniform random numbers for the coordinates.

So ... it truly has no clusters.

The point is: any clustering algorithm will always output some "clustering" of the data.

The question is, does the clustering reflect real structure?

Generally we encounter two problems:

• Are there "real" clusters in the data?
• if so, how many clusters are there?

There is often no definitive answer to either of these questions. You will need to use your judgment in answering them.

That said, we can define some metrics that will help to evaluate the extent to which clustering appears useful.

Rand Index¶

One tool we may be able to use in some settings is external information about the data.

In particular, we may have knowledge from some other source about the nature of the clusters in the data.

In that case, what we need is a way to compare a proposed clustering with some externally-known, "ground truth" clustering.

The Rand Index is a similarity measure for clusterings. We can use it to compare two clusterings.

Or, if we are testing an algorithm on data for which we know ground truth, we can use it to assess the algorithm's accuracy.

Defining the Rand Index.

Each item in our dataset is assumed to have two labelings, one for each clustering.

For example, we could have a ground truth label assignment T and a comparison clustering C.

Intuitively, the idea behind Rand Index is to consider pairs of points, and ask whether pairs that fall into the same cluster in T also fall into the same cluster in C.

Specifically:

Let a be the number of pairs that have the same label in T and the same label in C.

Let b be: the number of pairs that have different labels in T and different labels in C.

Then the Rand Index is: \mbox{RI}(T,C) = \frac{a+b}{n \choose 2}

How do we know whether a particular Rand Index (RI) score is significant?

We might compare it to the RI for a random assignment of points to labels.

This leads to the Adjusted Rand Index.

Definition of Adjusted Rand Index.

To "calibrate" the Rand Index this way, we use the expected Rand Index of random labelings, denoted E[\text{RI}].

The Expected Rand Index considers C to be a clustering that has the same cluster sizes as T, but labels are assigned at random.

Using that, we define the adjusted Rand index as a simple rescaling of RI:

The computation of the E[\text{RI}] and the \max(\text{RI}) are simple combinatorics (we'll omit the derivation).

Example.

Let's consider again our 3-cluster dataset with known labels y.

Here is the adjusted Rand Index, when using k-means to cluster this dataset for 1 to 10 clusters:

8.2 Deciding on the Number of Clusters¶

An important we face in evaluating a clustering is how many clusters are present.

In practice, to use k-means or most other clustering methods, one must choose k, the number of clusters, via some process.

Inspecting Clustering Error¶

The first thing you might do is to look at the k-means objective function and see if it levels off after a certain point.

Recall that the k-means objective can be considered the clustering "error".

If the error stops going down, that would suggest that the clustering is not improving as the number of clusters is increased.

Recall our synthetic data from earlier.

For this synthetic dataset, here is the k-means objective, as a function of k:

Warning: This synthetic data is not at all typical. You will almost never see such a sharp change in the error function as we see here.

Silhouette Coefficient¶

Of course, normally, the ground truth labels are not known.

In that case, evaluation must be performed using the model itself.

Recall our definition of clustering:

a grouping of data objects, such that the objects within a group are similar (or near) to one another and dissimilar (or far) from the objects in other groups.

This suggests a metric that could evaluate a clustering: comparing the distances between points within a cluster, to the distances between points in different clusters.

The Silhouette Coefficient is an example of such an evaluation, where a higher Silhouette Coefficient score relates to a model with "better defined" clusters.

(sklearn.metrics.silhouette_score)

Let a be the mean distance between a data point and all other points in the same cluster.

Let b be the mean distance between a data point and all other points in the next nearest cluster.

Then the Silhouette Coefficient for a clustering is: s = \frac{b-a}{\max(a, b)}

Let's apply the Silhouette Coefficient to our synthetic dataset.

Again, these results are more perfect than typical.

But the general idea is to look for a local maximum in the Silhouette Coefficient as the potential number of clusters.