The dendrogram

Loading...

En provenance du cours de University of Washington

Machine Learning: Clustering & Retrieval

1388 notes

University of Washington

Machine Learning: Clustering & Retrieval

1388 notes

Cours 4 sur 4 dans Specialization Machine Learning

Case Studies: Finding Similar Documents A reader is interested in a specific news article and you want to find similar articles to recommend. What is the right notion of similarity? Moreover, what if there are millions of other documents? Each time you want to a retrieve a new document, do you need to search through all other documents? How do you group similar documents together? How do you discover new, emerging topics that the documents cover? In this third case study, finding similar documents, you will examine similarity-based algorithms for retrieval. In this course, you will also examine structured representations for describing the documents in the corpus, including clustering and mixed membership models, such as latent Dirichlet allocation (LDA). You will implement expectation maximization (EM) to learn the document clusterings, and see how to scale the methods using MapReduce. Learning Outcomes: By the end of this course, you will be able to: -Create a document retrieval system using k-nearest neighbors. -Identify various similarity metrics for text data. -Reduce computations in k-nearest neighbor search by using KD-trees. -Produce approximate nearest neighbors using locality sensitive hashing. -Compare and contrast supervised and unsupervised learning tasks. -Cluster documents by topic using k-means. -Describe how to parallelize k-means using MapReduce. -Examine probabilistic clustering approaches using mixtures models. -Fit a mixture of Gaussian model using expectation maximization (EM). -Perform mixed membership modeling using latent Dirichlet allocation (LDA). -Describe the steps of a Gibbs sampler and how to use its output to draw inferences. -Compare and contrast initialization techniques for non-convex optimization objectives. -Implement these techniques in Python.

À partir de la leçon

Hierarchical Clustering & Closing Remarks

In the conclusion of the course, we will recap what we have covered. This represents both techniques specific to clustering and retrieval, as well as foundational machine learning concepts that are more broadly useful.<p>We provide a quick tour into an alternative clustering approach called hierarchical clustering, which you will experiment with on the Wikipedia dataset. Following this exploration, we discuss how clustering-type ideas can be applied in other areas like segmenting time series. We then briefly outline some important clustering and retrieval ideas that we did not cover in this course.<p> We conclude with an overview of what's in store for you in the rest of the specialization.

Why hierarchical clustering?2:22

Divisive clustering4:09

Agglomerative clustering2:45

The dendrogram4:56

Agglomerative clustering details7:03

Hidden Markov models9:24

Rencontrer les enseignants

Emily Fox
Amazon Professor of Machine Learning
Statistics
Carlos Guestrin
Amazon Professor of Machine Learning
Computer Science and Engineering

[MUSIC]

So one way to compactly represent the results of hierarchical equestrian

are through something called a dendrogram.

And we're going to explain the dendrogram in the context of agglomerative

clustering, even though this type of representation can be used for

other hierarchical equestrian approaches as well.

So the dendrogram representation is as follows.

Along the x axis, we're going to place each one of our data points, but

carefully ordered so that we get a very nice visual coming out of this and then

along the y-axis, what we're indicating is the distance between different clusters.

So more specifically, when we're thinking about single linkage,

where we're looking at the minimum distance between the set of points

in any pair of clusters, then what the height of a specific

merge point is going to represent is the distance between those two clusters.

So let's describe this a little bit more where if we look at a given merge point,

and below that we have two separate trees,

each one of those trees is going to represent a different cluster.

So in this example, we have this blue cluster, so all these points

that are colored in blue are data points that are assigned to this blue cluster

at some iteration of this algorithm and likewise, we have this green cluster.

And then the height of the merge between this blue branch and

this green branch indicates what was the minimum distance between

any point in that blue cluster and any point in that green cluster.

And so that minimum distance is where we're going to put that merge of the blue

branch with the green branch, so that specifies the height along the y-axis.

And so, throughout this tree, we're seeing the different clusters that are present

and the distances between these clusters as different merges were made

throughout the algorithm, going from every data point being in its own cluster,

all the way to all the data points being in one cluster.

And likewise, if we look at any path down this dendrogram,

what that indicates is the cluster membership of a given data point

throughout all the different merge steps.

So what cluster that data point belonged to and

the sequence of merges made for those clusters.

So in summary, we see that the dendrogram is able to capture all the critical

elements of the hierarchical clustering result.

So what are the different cluster memberships?

Which cluster is merged with which?

And what were the distances between those clusters

at the point at which they merged?

Well, one important thing we can think of doing from the dendrogram

is extracting a partition.

Because remember, if we run agglomerative clustering from beginning all the way to

the end, we're starting with all data points in separate individual clusters and

then ending with all data points in one cluster.

And what we really want is we want to produce some clustering of our data

points, that's somewhere in between.

Not at the granularity of every point being its own cluster and

not at this very coarse granularity of everything being one cluster.

So this leads to a question of how do we extract some partition?

How do we define a set of clusters to produce from this hierarchical

clustering procedure?

And one really simple approach is to perform a cut

along the y-axis of the dendrogram.

Then every branch that crosses this line that we chose

is going to define a separate cluster.

So in this example, we see we have this fuchsia cluster, blue, green, orange, and

gray clusters.

But remember in this visualization, each of these data points,

this just represented different data indices in our data set.

But what we can do is we can go back to our original feature space and

visualize what the resulting clusters look like.

So if our data were just in 2D, like all the examples we've been given,

because of our nice 2D slide representation, this might be

the clustering associated with the cut that we showed on the previous slide here.

And as we think about varying where this cut point is, we're looking at different

possible clusterings of our dataset through different granularities, going

from really, really fine granularity all the way up to very coarse granularities.

So let's spend a little time thinking about what it means to cut the dendrogram

at some level D*.

Well what we're saying then is that, for

the resulting clusters produced by this cut, there are no pair of

clusters at a distance less than D* that have not already been merged.

So that means that D* is the minimum distance between our clusters at

this level of the clustering.

[MUSIC]

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play