Unit 6 7b Spectral Clustering Algorithm knowitvideos English Japanese

Unit 6 7b Spectral Clustering AlgorithmYouTube↗ IA↗(long shot)
Howto & Style 42.3K views 553 likes 9 dislikes 22 Oct 2011

knowitvideos 11.8K subscribers N/A YouTube↗

Click to Play Video

So let's look at this example again--let me redraw the data.

再び例を見ます　データを書き直しましょう

What makes these clusters so different is not the absolute location of each data point,

このクラスタに違いが出る要因はそれぞれのデータの絶対位置ではなく

but the connectedness of these data points.

これらのデータのデータ点の連結性です

The fact that these 2 points belong together is likely because there's lots of points in-between.

この2つの点が同類なのは中間にたくさんの点があるからです

In other words, it's the affinity that defines those clusters, not the absolute location.

言い換えれば類似度とは絶対位置ではなくこのクラスタを意味します

So spectral clustering gets annotation of affinity to make clustering happen.

スペクトラルクラスタリングは類似度の情報をもとにクラスタリングを行います

So let me look at the simple example for spectral clustering

簡単な例を見てみましょう

that would also work for K-means or EM,

k－means法やEM法にも応用できますが

but they'll be useful to illustrate spectral clustering.

スペクトラルクラスタリングの説明にも役立ちます

Let's assume there's 9 data points as shown over here,

ここに9つのデータ点があるとします

and I've colored them differently in blue, red, and black.

それぞれを青、赤、黒と別の色にしましたが

But to clustering algorithms, they all come with the same color.

クラスタリングアルゴリズムではすべて同じ色です

Now the key element of spectral clustering is called the affinity martrix,

スペクトラルクラスタリングの重要な要素は “類似度行列”と言います

which is a 9 by 9 matrix in this case,

この場合は9×9の行列です

where each data point gets graphed realtive to each other data point.

それぞれのデータ点は関係する部分でグラフにします

So let me write down all the 9 data points into the different rows of this matrix--

それでは9つのデータ点をすべてこの行列の横列に書き込みましょう

the red ones, the black ones, and the blue ones.

赤、黒、青です

And in the columns, I graphed the exact same 9 data points.

縦列に同じく9つのデータ点を書きます

I then calculate for each pair of data points their affinity,

次にそれぞれのデータ点のペアを計算します

where I use for now affinity as the quadratic distance in this diagram over here.

類似度はこのグラフにある二次距離を利用します

Clearly, the red dots to each other have a high affinity,

明らかに赤い点は互いに類似度が高いです

which means a small quadratic distance.

つまり二次距離が小さいのです

Let me indicate this as follows--

説明すると次の通りです

But realtive to all the other points, the affinity is weak.

しかし他の点に関係していると類似度は弱まります

So there's a very small value in these elements over here.

ですのでそれぞれの要素には小さな値があります

Similarly, the affinity of the black data points to each other is very high,

同じように黒のデータ点の類似度は高いです

which means that the following block diagonal in this matrix will have a very large value.

つまり下の行列で斜めのブロック部分は大きな値があります

Yet the affinity to all the other data points will be low.

他のデータ点に関する類似度も低くなります

And of course, the same is true for the blue data points.

もちろん青のデータ点も同じです

The interesting thing to notice now is that this is an approximately rank-deficient matrix.

青のデータ点の面白い点はランクが不足している行列だということです

And further, the data points that belong to the same class-- like the 3 red dots or the 3 black dots,

さらに同じクラスに属している 3つの赤い点や黒い点のデータ点のように

have a singular affinitive vector to all the other data points.

他のデータ点すべてに別々の類似的なベクトルを持っています

So this vector over here is similar to this vector over here.

ここにあるベクトルはこのベクトルと似ています

It's similar to this vector over here, but it's very different to this vector over here,

ここにあるベクトルは似ていますがこちらのベクトルは違います

which then itself is similar to the vector over here,

つまりここにあるベクトルは似ており

yet different to the previous ones.

前のベクトルとは異なります

Such a situation is easily addressed by what's called principal component analysis, or PCA.

そのような状況はいわゆる “主成分分析（PCA）”と呼ばれます

PCA is a method to identify vectors that are similar

PCAはランク不足行列で

in an approximate rank-deficient matrix.

似ているベクトルを特定する方法です

Consider once again our affinity matrix

もう一度類似度行列を

with prinicple component analysis, which is a standard linear trick,

基本的な線形代数の技法である PCAを使って考えてみましょう

we can re-represent this matrix by the most dominant tivectors you'll find there.

この行列をここにある支配的なベクトルで書き直しましょう

And the first one, might look like this.

このようにします

The second one, which would be orthogonal, may look like this.

次にこのように直交するベクトルにします

The third one, like this.

3つ目はこうです

These are called eigenvectors, and the principle component now is each eigenvector has an item of value

これらを固有ベクトルと言いそれぞれの固有ベクトルが主成分になります

that states how prevalent this vector is in the original data.

元のデータの中でどのくらい優勢かということです

And for these 3 vectors, you're going to find a large eigenvalue

3つのベクトルで大きな固有値を探しましょう

because there's a number data points that represent

なぜなら最初の3つのベクトルが

these vectors quite prevalently like the first 3 does for this guy over here.

この固有ベクトルを上手く表現できるような上手いデータ点がいくつか存在するからです

There might be additional eigenvectors like something like this,

このように他の固有ベクトルがあるかもしれません

but such eigenvectors will have a small eigenvalue

しかしそれは小さな固有値になるでしょう

simply because this vector isn't really required to explain the data over here.

このベクトルはこのデータの説明に不可欠ではありません

It might just be explaining some of the noise in the affinity matrix

類似度行列にあるノイズを説明しているかもしれません

that I didn't even dare draw in here.

ここではあえて書きませんでした

Now if you take the eigenvectors with the largest eigenvalues--3 in this case,

この場合3つの大きな固有値を使って固有ベクトルを示すなら

you first discover that the dimensionality of the underlying data space.

まず初めに基礎のデータ部分の距離を発見するでしょう

The dimensionality equals the number of large eigenvalues.

距離は大きい固有値の数と等しいです

Further, if you re-represent each data vector using those eigenvectors,

さらにこの固有ベクトルを使って各データのベクトルを書き直せば

you'll find a 3 dimensional space where original data falls into a varity of different places.

その次元空間は元のデータが違う場所に落とし込まれた三次元空間と分かるでしょう

And these places are easily told apart by conventional clustering.

この場所はクラスタリングで簡単に分けられます

So in summary, spectral clustering builds an affinity matrix of the data points.

つまりスペクトラルクラスタリングはデータ点の類似度行列を作成し

It strikes the eigenvectors with the largest eigenvalues,

固有ベクトルを大きい固有値に求めて

and then re-map those vecotrs into a new space with the data points easily clustering the conventional way.

従来の方法でクラスタリングできるデータ点を作り新しい空間にベクトルを作り直します

This is called affinity-based clustering or spectral clustering.

これは類似度に基づくクラスタリングまたはスペクトラルクラスタリングと言われます

Let me illustrate this once again with the data set that has a different spectral clustering than a conventional clustering.

従来とは異なるスペクトラルクラスタリングのデータセットを使いもう一度説明しましょう

In this data set, the different clusters belong

異なるクラスタがまとまっています

together because they're affinity is similar.

各クラスタの類似度が同じだからです

These 2 points belong together because there is a point in-between.

中間の点が1つなのでこの2点をひとまとめにできます

If we now draw the affinity matrix for those data points,

このデータ点の類似度マトリックスを描くと

you find that the first and second data points are close together

1つ目と2つ目のデータ点が近いことが分かります

and the second and the third, but not the first and the third.

2つ目と3つ目も同様ですが 1つ目と3つ目は違います

Hence these 2 off diagonal elements here have remained small.

従ってこの2つの非対角要素は小さいままです

Similarly for the red points as shown here with these 2 elements over here relatively small.

同じように比較的小さいこの2つの要素を使うと赤い点もこの通りです

And also for the black points

そして黒い点も同じです

where these 2 elements over here are small.

ここにある2つの要素は小さいです

And interestingly enough, even though these aren't blocked diagonal,

面白いことにこれらが対角ブロックでなければ

your first 3 largest eigenvectors will still look the same as before.

最初の3つの最大固有ベクトルは以前と同じに見えるでしょう

I find this quite remarkable

これは注目すべき点です

that even though these aren't exactly blocks,

これらが正確にブロックでないとしても

those vecotrs still represent the 3 most important vectors for which to recover the data using principle component analysis.

このベクトルはPCAを使ったデータを戻すための 3つの重要なベクトルを意味します

So in this case, spectral clustering would easily

この場合スペクトラルクラスタリングは

assign those guys and those guys and those guys to the respective same cluster,

これとこれとこれを容易に同じクラスタにします

which wouldn't be quite as easily the case for expectation-maximization or k-means.

EM法やk－means法の場合ほど簡単ではありません

So let me ask you the following quiz.

ではこれから問題を出します

Suppose we have 8 data points.

ここに8つのデータ点があるとします

How many elements will the affinity matrix have?

類似度マトリックスにどのくらいの要素があるでしょう？

Similar videos:

0 views 0 likes 0 dislikes 05 Jun 2026100% match

Gundarr (Ep 11): Skygoth (subtitulado al castellano)
daniborr
12.3K views 52 likes 5 dislikes 02 Jul 2012100% match

Gundarr (Ep 12): Sausage Party Poopers (subtitulado al castellano)
daniborr
35.1K views 110 likes 10 dislikes 03 Jul 2012100% match

Gundarr (Ep 18): Pistol Passing (subtitulado al castellano)
daniborr
14.7K views 63 likes 2 dislikes 10 Aug 2012100% match

Gundarr (Ep 2): Duck a la Rage (subtitulado al castellano)
daniborr
18.8K views 60 likes 3 dislikes 21 Jun 2012100% match

0 views 0 likes 0 dislikes 05 Jun 2026100% match

CEOS Chatter
Fernando Garcia
1.3K views 2 likes 1 dislikes 14 Mar 2012100% match

Unit 2, Topic 25, A-Star Third Question ANSWER

20K views 15 likes 33 dislikes 05 Oct 2011100% match

Unit 3 6d Question

16.4K views 1 likes 0 dislikes 08 Oct 2011100% match

Henry VIII - documentary BBC
Iris Houbaer
46.6K views 78 likes 7 dislikes 23 Apr 2014100% match

[ENG SUB] 110811 Mnet Wide Super Junior Interview Part 3/3
yingxuan0806
38.7K views 332 likes 1 dislikes 16 Oct 2011100% match

Mr. Peabody & Sherman
TheCaptionedInternet
43.6K views 74 likes 9 dislikes 03 Mar 2014100% match

Unit 1w, 7 Poker Answer

16.4K views 12 likes 1 dislikes 05 Oct 2011100% match

Instrucciones para llorar, de Julio Cortázar
Inés Andrés
5.9K views 10 likes 0 dislikes 10 Jan 2012100% match

Έλεν Κέλερ 2 ελληνικοί υπότιτλοι
Nasia Ntai
10K views 42 likes 1 dislikes 12 May 2013100% match

Unit 2, Topic 22, More on Uniform Cost Search

14.8K views 29 likes 4 dislikes 05 Oct 2011100% match

Unit 5 47 Gradient Descent Implementation

14K views 16 likes 17 dislikes 17 Oct 2011100% match

Unit 8 4 Vacuum Cleaner Example

15.1K views 46 likes 4 dislikes 31 Oct 2011100% match

PROBLEMAS DE APRENDIZAJE
Kuenta Libros
36.9K views 103 likes 4 dislikes 15 Sep 2011100% match

Recomendación kuentalibros - pizarra digital y niños con discapacidad auditiva
anitamc20
933 views 1 likes 0 dislikes 21 Dec 2012100% match

(ENG/CHI SUB) 140216 SM True Thailand Facebook EXO
Baby Xiumin
783 views 10 likes 0 dislikes 16 Feb 2014100% match

0 views 0 likes 0 dislikes 05 Jun 2026100% match

0 views 0 likes 0 dislikes 05 Jun 2026100% match

Unit 2, Topic 27, A-Star Fifth Question

22.4K views 32 likes 7 dislikes 05 Oct 2011100% match

Unit 4, 9 Gibbs Sampling

41K views 107 likes 26 dislikes 06 Oct 2011100% match

Gundarr (Ep 21): Tele Vision Quest (subtitulado al castellano)
daniborr
16.8K views 54 likes 4 dislikes 30 Aug 2012100% match

Unit 2, Topic 19, Search Optimality Answer

14.5K views 14 likes 4 dislikes 05 Oct 2011100% match

Unit 6 5j EM Algorithm

13.8K views 28 likes 5 dislikes 22 Oct 2011100% match

Unit 2, Topic 25, A-Star Third Question

26.6K views 9 likes 17 dislikes 05 Oct 2011100% match

TED & TEDx explained
Kyo young Chu
1.1K views 7 likes 0 dislikes 02 Apr 2012100% match

Settings Privacy About Contact Donate