Announcements¶

• HW1 is due today at 8pm

• HW 2 is out

• Upcoming office hours:

  • Today: Peer tutor Daniel Cho from 12:30-3:30pm in CCDS 16th floor
  • Today: Abhishek Tiwari from 4-5pm on CCDS 13th floor

• Read Boyd-Vandenberghe Chapter 3.1-3.2 and Chapter 4

7. The K-Means Problem¶

The inner product is the sum of the componentwise product of $u$ and $v$.

If $u=\left[\begin{array}{c}{u}_1\\ u_2\\ ⋮\\ u_n\end{array}\right]$ and $v=\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right],$ then the inner product of $u$ and $v$ is:

Definition. The norm of $v$ is the nonnegative scalar $\parallel v\parallel$ defined by

We can use inner product to find the distance between two vectors.

And because the Pythagorean Theorem says that $u$ and $v$ are perpendicular if and only if:

We can say that two vectors $u$ and $v$ in $R^n$ are orthogonal to each other if $u^{T}v=0.$

7.1 The Angle Between Two Vectors¶

There is an important connection between the inner product of two vectors and the angle between them. This connection is very useful (e.g., in visualizing data mining operations).

We start from the law of cosines:

Now let's interpret this law in terms of vectors $u$ and $v$.

Once again, it is the angle that these vectors make at the origin that we are concerned with.

Applying the law of cosines we get:

Now, previously we calculated that:

Which means that $$2u^{\top }v=2\parallel u\parallel \parallel v\parallel \cos \theta$$

So

This is a very important connection between the notion of inner product and trigonometry.

As a quick check, note that if $u$ and $v$ are nonzero, and $u^{\top }v=0$, then $\cos \theta =0.$

In other words, the angle between $u$ and $v$ is 90 degrees (or 270 degrees). So this agrees with our definition of orthogonality.

One implication in particular concerns unit vectors.

So

Note that $\frac{u}{\parallel u\parallel }$ and $\frac{v}{\parallel v\parallel }$ are unit vectors.

So we have the very simple rule, that for two unit vectors, their inner product is the cosine of the angle between them!

Example. Consider $u=\left[\begin{array}{c}0.95\\ 0.31\end{array}\right],$ and $v=\left[\begin{array}{c}0.20\\ 0.98\end{array}\right].$

So $u^{\top }v=(0.95\cdot 0.20)+(0.31\cdot 0.98)=0.5$

So $\cos \theta =\mathrm{0.5.}$

So $\theta =60$ degrees.

Example. Find the angle formed by the vectors:

Solution. First normalize the vectors:

So

Then calculate the cosine of the angle between them:

Then:

We can also compute this angle using Python.

Example Application: Cosine Similarity¶

Let's consider a data science application of this technique. Suppose we are given two documents $d_1$ and $d_2$.

For a goal such as information retrieval, we'd like to know whether the two documents are "similar".

One common way to formalize similarity is to say that documents are similar if they contain similar words. Here, we will view each document as a "bag of words," and ignore where each word occurs in the document.

We can measure this as follows: Construct a vector $x_1$ that counts the frequency of occurrence of certain words in $d_1$:

Do the same thing for $d_2$, yielding $x_2$.

What we have done is taken individual documents and represented them as vectors $x_1$ and $x_2$ in a very high dimensional space, $R^n$.

Here $n$ could be 10,000 or more.

Now, to ask whether the two documents are similar, we simply ask "do their vectors point in the same general direction?"

And, despite the fact that we are in a very high dimensional space which we cannot visualize, we can nonetheless answer the question easily.

The angle between the two document-vectors is simply:

7.2 The Clustering Problem¶

But what if rather than having two documents, we have a million documents? Then it's less clear what to make about the similarity or dissimilarity of any pair of documents. We want a more systematic way to understand the patterns in the overall dataset.

When we do clustering, what problem are we trying to solve? We will answer this question informally at first. (But soon we will look at formal criteria!)

Informally, a clustering is:

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.

So we want our clustering algorithm to:

• minimize intra-cluster distances
• maximize inter-cluster distances

Here are the basic questions we need to ask about clustering:

• What is the right kind of "similarity" to use?
• What is a "good" partition of objects?
  • ie, how is the quality of a solution measured?
• How to find a good partition?
  • are there efficient algorithms?
  • are there algorithms that are guaranteed to find good clusters?

Now note that even with our more-formal discussion, the criteria for deciding on a "best" clustering can still be ambiguous.

To accommodate the ambiguity here, one approach is to seek a hierarchical clustering. That is, as set of nested clusters organized in a tree.

We'll discuss hierarchical cluster next time.

For today, we'll focus on partitional clustering:

in a partitional clustering, the points are divided into a set of non-overlapping groups.

In a partitional clustering:

• Each object belongs to one, and only one, cluster
• The set of clusters covers all the objects

We are going to assume for now that the number of clusters is given in advance.

We will denote the number of clusters as $k$.

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 $x_1,\dots ,x_n$ 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 $\{x_1,\dots ,x_n\}$ as:

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

7.3 The $k$-means Problem¶

Now, we are ready to state our first formalization of the clustering problem.

We will assume that

• data items are represented by points in $R^d$ (i.e., each data item has $d$ features)
• $n$ points are given
• the number of clusters $k$ is given

$k$-means Problem:

Find $k$ points $c_1,\dots ,c_k$ (called centers, centroids, or means), so that the cost

is minimized.

Equivalently: we can think in terms of the partition itself.

Consider the set $X=\{x_1,\dots ,x_n\}$ where $x_i\in R^d$.

Find $k$ points $c_1,\dots ,c_k$

and partition the set $X$ into $k$ different subsets $\{X_1,\dots ,X_k\}$ by assigning each point $x_i$ to its nearst cluster center,

so that the cost

is minimized.

We now have a formal definition of a clustering.

This is not the only definition possible, but it is an intuitive and simple one.

How hard is it to solve this problem?

• $k=1$ and $k=n$ are easy special cases (why?)
• But, this problem is NP-hard if the dimension of the data is at least 2
  • We don't expect that there is any exact, efficient algorithm in general

Nonetheless, there is a simple algorithm that works quite well in practice!

7.4 The $k$-means Algorithm¶

$k$-means Problem: Find $k$ points $c_1,\dots ,c_k$ (called centers, centroids, or means), so that the sum of squares of distances from every point to the closest center

is minimized.

[Source: Wikipedia]

There is a "classic" algorithm for this problem, called the "$k$-means algorithm."

It was voted among the top-10 algorithms in data mining!

It is such a good idea that it has been independently discovered multiple times.

It was first discovered by Lloyd in 1957, so it is often called Lloyd's algorithm.

The (approximate) $k$-means algorithm:

1. Pick $k$ cluster centers $\{c_1,\dots ,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 $c_k$.

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

Let's walk through a picture showing how this algorithm works:

7.5 An example of $k$-means with synthetic data¶

Let's do an extended example showing $k$-means clustering in practice and in the context of the python libraries scikit-learn.

scikit-learn is a useful Python library for machine learning functions.

Our goals are to learn:

• How clustering is used in practice
• Tools for evaluating the quality of a clustering
• Tools for assigning meaning or labels to a cluster
• Important visualizations
• A little bit about feature extraction for text

Working with synthetic data¶

Generally, when learning about or developing a new unsupervised method, it's a good idea to try it out on a dataset in which you already know the "right" answer.

One way to do that is to generate synthetic data that has some known properties.

Among other things, scikit-learn contains tools for generating synthetic data for testing.

To get a sense of the raw data we can inspect it.

For statistical visualization, a good library is seaborn, imported as sns.

That plot shows all the data.

As usual, each row is a data item and the columns correspond to features (which are simply coordinates here).

Geometrically, these points live in a 30 dimensional space, so we cannot directly visualize their geometry.

So let's compute the pairwise distances for visualization purposes.

We can compute all pairwise distances in a single step using a scikit-learn function:

And we can then visualize the data is using a heatmap on the set of pairwise distances.

Visualizing with Multidimensional Scaling¶

The idea behind Multidimensional Scaling (MDS) is:

• given a distance (or dissimilarity) matrix,
• find a set of coordinates for the points that approximates those distances as well as possible.

Usually we are looking for points in 2D or maybe 3D for visualization purposes.

The algorithm works by starting with random positions, and then moving points in a way that reduces the disparity between true distance and euclidean distance.

Note that there are many ways that this can fail!

• Perhaps the dissimilarities are not well modeled as euclidean distances
• It may be necessary to use more than 2 dimensions to capture any clustering via euclidean distances

So we can see that, although the data lives in 30 dimensions, we can get a sense of how the points are clustered by approximately placing the points into two dimensions.

Applying $k$-Means¶

The Python package scikit-learn has a huge set of tools for unsupervised learning generally, and clustering specifically.

These are in sklearn.cluster.

There are 3 functions in all the clustering classes,

• fit(),
• predict(), and
• fit_predict().

fit() builds the model from the training data (e.g. for $k$-means, it finds the centroids),

predict() assigns labels to the data after building the model, and

fit_predict() does both in a single step.

All the tools in scikit-learn are implemented as python objects.

Thus, the general sequence for using a tool from scikit-learn is:

• Create the object, probably with some hyperparameter settings or intialization,
• Run the method, generally by using the fit() function, and
• Examine the results, which are generally property variables of the object.

Visualizing the Results of Clustering¶

Let's visualize the results. We'll do that by reordering the data items according to their cluster.