Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
About Spectral Clustering
Search
Shunya Ueta
October 16, 2014
Research
3k
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
About Spectral Clustering
Spectral Clusteringというクラスタリング手法についての基本的な説明のスライドです。
@MMA_LAB
Shunya Ueta
October 16, 2014
Transcript
12 slides
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
More Decks by Shunya Ueta
See All by Shunya Ueta
20分で分かる Human-in-the-Loop 機械学習におけるアノテーションとヒューマンコンピューターインタラクションの真髄
hurutoriya
6
4.1k
Query Understanding for Search Engines. Chap2 Query Classification
hurutoriya
0
630
Introducing "Challenges and research opportunities in eCommerce search and recommendations"
hurutoriya
0
410
Auto Content Moderation in C2C e-Commerce at OpML20
hurutoriya
0
830
TFX: A tensor flow-based production-scale machine learning platform
hurutoriya
0
740
Applied machine learning at facebook a datacenter infrastructure perspective HPCA18
hurutoriya
0
400
machine learning tips in the python world PRMLer Night
hurutoriya
1
730
パターン認識と機械学習 第1章 #PRML学ぼう PRML輪講 #2 / PRML Seminar 2 go to introduction in machine learning
hurutoriya
1
3.3k
複数人でコードを書く際のFist Step
hurutoriya
0
430
Other Decks in Research
See All in Research
フィジカルAIの社会実装に向けて -AIエージェントからAgentic Roboticsへ-
hf149
1
2.8k
SAM3を用いたコマ・吹き出しの 領域検出と分割構造からの読み順推定
kzmssk
0
230
ICAITD 2026 Oral Presentation
rikkabotan7
0
150
La génomique au service de la fromageabilité du lait grâce aux spectres MIR
institutdelelevage
PRO
0
230
A Preliminary Performance Evaluation of Cassandra Accord
sira
0
110
Méthane 2030 : Développer des solutions de réduction des émissions de méthane entérique : 1ers résultats
institutdelelevage
PRO
0
130
PHTalks Bengaluru - SSRF When All Else Fails
dk999
0
1.2k
MIRU2026 チュートリアル講演2:三次元データ処理の動向
nnchiba
8
5.6k
[IEICE-Soceity-Conf2026] セマンティック通信を見据えたマルチスケールセンシングと 学習の融合によるデジタルツイン基盤 / Digital Twin Infrastructure via the Fusion of Multi-Scale Sensing and Learning toward Semantic Communications
pman0214
0
150
20261101GISA-FOSS4G
tosseto
1
160
Adapter les bergeries aux fortes chaleurs
institutdelelevage
PRO
0
190
GeoAgent勉強会 論文紹介と強い推論モデルが与えるインパクト
satai
5
500
Featured
See All Featured
RailsConf 2023
tenderlove
30
1.6k
Darren the Foodie - Storyboard
khoart
PRO
5
4.1k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
4.6k
Have SEOs Ruined the Internet? - User Awareness of SEO in 2025
akashhashmi
0
550
How to Get Subject Matter Experts Bought In and Actively Contributing to SEO & PR Initiatives.
livdayseo
1
250
Navigating Weather and Climate Data
rabernat
0
600
How to Ace a Technical Interview
jacobian
280
24k
Measuring Dark Social's Impact On Conversion and Attribution
stephenakadiri
2
330
DevOps and Value Stream Thinking: Enabling flow, efficiency and business value
helenjbeal
2
450
Heart Work Chapter 1 - Part 1
lfama
PRO
11
37k
The Art of Programming - Codeland 2020
erikaheidi
57
15k
GitHub's CSS Performance
jonrohan
1033
470k