Hello! In this video, we'll be measuring the distances between clusters using algorithms
for hierarchical Clustering. Let's look at some algorithms for Hierarchical
Clustering. The first type we'll look at is Agglomerative Clustering. Remember that agglomerative
clustering is a bottom-up approach. Let's say our dataset has n data points. First,
we want to create n clusters, one for each data point. Then each point is assigned as
a cluster. Next, we want to compute the proximity matrix,
which will be an n x n table,. After that, we want to iteratively run the
following steps until the specified cluster number is reached, or until there is only
one cluster left. First, Merge the two nearest clusters (Distances
are computed already in the proximity matrix). Second, Update the proximity matrix with the
new values. We stop after we've reached the specified
number of clusters, or there is only one cluster remaining, with the result stored in a dendrogram.
So the key operation is the computation of the proximity between two clusters.
Different approaches to defining the distance between clusters distinguish the different
algorithms. Remember that the different linkage criteria
we looked at in the previous slide applies here.
Now for the top-down version of Hierarchical Clustering, which is known as divisive clustering.
Note that this method is less popular than the agglomerative version. We will be looking
at two different kinds of divisive clustering. In the first method, we start off with one
cluster, which contains all of the data points in it. Next, we remove the 'outsider' from
the least cohesive cluster. Finally, we stop when each data point is in its own cluster.
If this doesn't happen by this point, then repeat the previous step.
The second divisive clustering algorithm we'll look at, is K-means divisive clustering.
The first step is to run the K-means algorithm on the original dataset. This dataset may
already be partially partitioned, or may just be one large cluster. We choose a value of
K, which is how many subsets we want to break the cluster into, so C 3 for example would
mean we want to break the cluster into 3 smaller clusters. We run this recursively until we
are unable to break the clusters down further. This form of top-down hierarchical clustering
works quickly, because each time we divide the clusters, we are running recursive calls
of K-means on a smaller subset. The runtime for this operation is logarithmic
because every time the k-means algorithm runs a log base k of n, where n is the number of
data points and k is the number of clusters you produce from each cluster in every iteration.
So for example k= 2 would split a cluster into 2 clusters, then each of those clusters
would be split into two more clusters, totaling 4 clusters, and so on.
Note that whenever a cluster is split into different subsets, the clusters are never
merged again. The K-means algorithm only runs in each specific subset of data that it's
working with. Here's a quick example of K-means Hierarchical
Divisive Clustering. Let's say we start with a data set that that looks like this. We'll
also be working with k = 2. So when we run k-means on these two clusters,
we get something that looks like this. Now we have two clusters, one blue and one
red. K-means will now run recursively on each of these clusters.
And let's look at one more split. As previously stated, this would continue until each point
was in a cluster of its own.
Thanks for watching!