Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
About Spectral Clustering
Search
Shunya Ueta
October 16, 2014
Research
0
2.8k
About Spectral Clustering
Spectral Clusteringというクラスタリング手法についての基本的な説明のスライドです。
@MMA_LAB
Shunya Ueta
October 16, 2014
Tweet
Share
More Decks by Shunya Ueta
See All by Shunya Ueta
20分で分かる Human-in-the-Loop 機械学習におけるアノテーションとヒューマンコンピューターインタラクションの真髄
hurutoriya
5
2.6k
Query Understanding for Search Engines. Chap2 Query Classification
hurutoriya
0
350
Introducing "Challenges and research opportunities in eCommerce search and recommendations"
hurutoriya
0
200
Auto Content Moderation in C2C e-Commerce at OpML20
hurutoriya
0
500
TFX: A tensor flow-based production-scale machine learning platform
hurutoriya
0
210
Applied machine learning at facebook a datacenter infrastructure perspective HPCA18
hurutoriya
0
190
machine learning tips in the python world PRMLer Night
hurutoriya
1
650
パターン認識と機械学習 第1章 #PRML学ぼう PRML輪講 #2 / PRML Seminar 2 go to introduction in machine learning
hurutoriya
1
2.8k
複数人でコードを書く際のFist Step
hurutoriya
0
360
Other Decks in Research
See All in Research
論文読み会 KDD2024 | Relevance meets Diversity: A User-Centric Framework for Knowledge Exploration through Recommendations
cocomoff
0
130
[ECCV2024読み会] 衛星画像からの地上画像生成
elith
1
960
LLM時代にLabは何をすべきか聞いて回った1年間
hargon24
1
570
大規模言語モデルのバイアス
yukinobaba
PRO
4
800
marukotenant01/tenant-20240916
marketing2024
0
640
渋谷Well-beingアンケート調査結果
shibuyasmartcityassociation
0
340
第79回 産総研人工知能セミナー 発表資料
agiats
2
180
Human-Informed Machine Learning Models and Interactions
hiromu1996
2
550
VisFocus: Prompt-Guided Vision Encoders for OCR-Free Dense Document Understanding
sansan_randd
1
400
FOSS4G 山陰 Meetup 2024@砂丘 はじめの挨拶
wata909
1
130
Weekly AI Agents News! 11月号 プロダクト/ニュースのアーカイブ
masatoto
0
240
第 2 部 11 章「大規模言語モデルの研究開発から実運用に向けて」に向けて / MLOps Book Chapter 11
upura
0
450
Featured
See All Featured
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
Making Projects Easy
brettharned
116
6k
Building Better People: How to give real-time feedback that sticks.
wjessup
366
19k
A Philosophy of Restraint
colly
203
16k
Automating Front-end Workflow
addyosmani
1366
200k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
27
1.5k
4 Signs Your Business is Dying
shpigford
182
21k
Building Your Own Lightsaber
phodgson
104
6.2k
Designing on Purpose - Digital PM Summit 2013
jponch
116
7k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
160
15k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
226
22k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
28
2.2k
Transcript
About Spectral Clustering Univ. of Tsukuba MMA Lab Shunya
Ueta
目次 1. Spectral Graph 1. About 2. Graph
Laplacian Matrix 3. 応用例 2. Spectral Clustering 3. 実装 2
About Spectral Graph 歴史: 1950年代~ 目的:
グラフの特徴とグラフの固有値・固有ベクトル を結びつける 応用例: Spectral Clustering 画像領域分割 3
Graph Laplacian matrix 4 定義: 4 2 3
5 1 [ 0 1 0 1 0 ] [ 1 0 1 1 0 ] [ 0 1 0 0 1 ] [ 1 1 0 0 1 ] [ 0 0 1 1 0 ] [ 2 0 0 0 0 ] [ 0 3 0 0 0 ] [ 0 0 2 0 0 ] [ 0 0 0 3 0 ] [ 0 0 0 0 2 ] AG DG G n頂点無向グラフ G = (V, E) : AG : DG : Gの近接行列 Gの次数行列 LG = DG AG ラプラシアン行列 [ 2 -‐1 0 -‐1 0 ] [ -‐1 3 -‐1 -‐1 0 ] [ 0 -‐1 2 0 -‐1 ] [ -‐1 -‐1 0 3 -‐1 ] [ 0 0 -‐1 -‐1 2 ] LG = =
Spectral Graphの応用例 画像領域分割 : 画素毎の類似画像 5
Spectral Graphの応用例 画像領域分割 6
Spectral Grapth の応用例 Spectral Clustering 7
Spectral Clustering 8 P次元 n 個 .
. . 目的 p次元のデータn個を kクラスタに分類したい グラフ表現 データをグラフで表す Laplacian matrix グラフの行列表現 n n 対称行列 固有値集合(スペクトラム)を求める 固有ベクトルを小さいものから k番目までを選定 k n
Graph Laplacian matrix 9 定義: 4 2 3
5 1 [ 0 1 0 1 0 ] [ 1 0 1 1 0 ] [ 0 1 0 0 1 ] [ 1 1 0 0 1 ] [ 0 0 1 1 0 ] [ 2 0 0 0 0 ] [ 0 3 0 0 0 ] [ 0 0 2 0 0 ] [ 0 0 0 3 0 ] [ 0 0 0 0 2 ] AG DG G n頂点無向グラフ G = (V, E) : AG : DG : Gの近接行列 Gの次数行列 LG = DG AG ラプラシアン行列 [ 2 -‐1 0 -‐1 0 ] [ -‐1 3 -‐1 -‐1 0 ] [ 0 -‐1 2 0 -‐1 ] [ -‐1 -‐1 0 3 -‐1 ] [ 0 0 -‐1 -‐1 2 ] LG = =
ProperLes of Laplacian matrix 10 1. Lは部分対角優位行列なので全ての固有値は 0 以上
2. L の最小固有値は 0 であり、対応する固有ベクトルは全要素1の n 次元ベクトル 3. 固有値0の個数はグラフの連結部の数 連結部A 連結部B Laplacian matrix グラフの行列表現 対称行列 A B 1 1 1 0 0 0 I 0 = x x 固有値 対角行列
ProperLes of Laplacian matrix 11 1. Lは部分対角優位行列なので全ての固有値は 0 以上
2. L の最小固有値は 0 であり、対応する固有ベクトルは全要素1の n 次元ベクトル 3. 固有値0の個数はグラフの連結部の数 連結部A 連結部B Laplacian matrix グラフの行列表現 対称行列 A B 0 0 0 1 1 1 I 0 = x x 固有値 対角行列
Spectral Clustering 12 理想的なグラフ状態 各行に対して各列の要素が クラスタを示している
k n 1 1 0 0 0 0 0 1 0 0 i番目の行はあるデータX_i が所属するクラスタを 示している 0 0 0 1 1