Name: 4 11 光譜聚類三步驟 7 17 高級 (4 11 Spectral Clustering Three Steps 7 17 Advanced)
Uploaded: 2021-01-14T07:02:42.000Z
Duration: 7 min 18 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

情態副詞

So basically, let me quickly summarize what we have, learned so far.

Right, so if we want to apply spectral graph partitioning to

find two clusters in a given graph, there are three steps we have to go through.

In the first step, we have to do what is called pre-processing where we

construct a matrix representation of a graph.

In the second step, we go and compute the eigenvalue decomposition of this,

of this graph by identifying eigenvalues and eigenvectors.

In particular, we are interested in the, second smallest eigenvalue lambda 2 and

And then, once we have the cor, the, the,

the vector x, all we have to do is we have to go and

do the grouping where we basically look at the components of ne, of x.

And determine which nodes belong to the set A, and

Kind of, who belongs to the left partition,

Right, so in the pre-processing step, I take our graph G and

In the second step, then, we do the eigenvalue decomposition, where basically

we take, our L when we find a set of eigenvalues and a set of eigenvectors.

we take the second smallest eigenvalue and the corresponding eigenvector.

So here are now all the nodes one to, 1 to 6.

And these are the corresponding entries of the eigenvector.

And what we find, for example, is that now what we have to do is,

We would like to group these nodes into clusters corresponding to the embedding or

the labels of the nodes that, that we have in the corresponding eigenvector.

We basically go and sort the components, of of the vector X, and

identify clusters, by splitting the vector in 2, so [COUGH].

to this case would be to ask, what are the corresponding values that are negative,

what are the corresponding values that are positive, right.

So if this is our vector X, we would split it here between nodes 3 and 4.

These are all the nodes that are on the right-hand side of the 0.

These are all the nodes on the left-hand side of the 0.

Notice that some of the node labels equals to 0, exactly as we said,

Also notice the sum of the squares of the values equals to 1, which is,

So what this basically means is, now, by splitting this vector in half into kind of

the positive part and the negative part, we identified the two clusters.

Here is the cluster A, which is composed of nodes 1 to 3,

and the cluster B that is composed of nodes, 4, 5, and 6.

So, basically, what the components of second smallest eigenvector here basically

embedded the nodes on a line, assigned them the positive and negative values.

We take all the positive nodes, put them into cluster A.

nodes with negative values, put them in the cluster B.

So, now if I give you a bit more interesting example,

here I have graph on the left G that you see it has two clusters.

I computed the lambda 2 and the corresponding eigenvector X.

And all I did here is now I sorted the vector X2, right, the corresponding

eigenvector to the second smallest eigenvalue by, by the entries.

And what you see very nicely is there is a set of components that

has a negative value, and a set of components that has a positive value.

the entries of the eigenvector with a positive value correspond to

one cluster and the remaining ones correspond to the second cluster.

is there anything interesting about the, eigenvectors that corresponds to,

let's say the third smallest eigenvalue, the fourth smallest eigenvalue, and so on.

And just to, for example, show you what happens that, the first case I'll

show you is a graph that I have here that actually contains four small clusters.

If the graph contains four small clusters and I still compute, lambda 2 and

the corresponding eigen vector X2, what, what I show you here is now the,

you see how, how the entries now first are split into two clusters, right?

But then you actually find that here, we have these different steps.

then each of the two clusters has two small clusters embedded in them.

And we see this kind of from the structure of the components of

So the question is, if I have multiple, clusters, how would I go identify them?

So let me just show you some examples how to do this.

For example, if this is my graph G, the same as I had before,

I have my Laplacian matrix L that I do eigendecomposition.

For example, here are the components of vector X1, and

they all have exactly the same value, so exactly as we said and as we have proven.

But for example the components of the third,

And now what you see here is for example that, this is the, the bottom cluster.

here these component's correspond to the fourth cluster.

This gives us now an idea of how do we go if we want to

partition a graph not into clusters but in K of them.

One approach is to do recursive bipartitioning.

It's basically take the full graph, split it in two, and now for

字幕列表影片播放

4 11 光譜聚類三步驟 7 17 高級 (4 11 Spectral Clustering Three Steps 7 17 Advanced)

sort

individual

approach

multiple