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.9k
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
3.1k
Query Understanding for Search Engines. Chap2 Query Classification
hurutoriya
0
420
Introducing "Challenges and research opportunities in eCommerce search and recommendations"
hurutoriya
0
250
Auto Content Moderation in C2C e-Commerce at OpML20
hurutoriya
0
620
TFX: A tensor flow-based production-scale machine learning platform
hurutoriya
0
260
Applied machine learning at facebook a datacenter infrastructure perspective HPCA18
hurutoriya
0
220
machine learning tips in the python world PRMLer Night
hurutoriya
1
680
パターン認識と機械学習 第1章 #PRML学ぼう PRML輪講 #2 / PRML Seminar 2 go to introduction in machine learning
hurutoriya
1
3k
複数人でコードを書く際のFist Step
hurutoriya
0
380
Other Decks in Research
See All in Research
SkySense : A Multi-Modal Remote Sensing Foundation Model Towards Universal Interpretation for Earth Observation Imagery
satai
3
200
RapidPen: AIエージェントによるペネトレーションテスト 初期侵入全自動化の研究
laysakura
0
1.3k
Principled AI ~深層学習時代における課題解決の方法論~
taniai
3
1.2k
rtrec@dbem6
myui
6
800
研究テーマのデザインと研究遂行の方法論
hisashiishihara
5
1.3k
Adaptive fusion of multi-modal remote sensing data for optimal sub-field crop yield prediction
satai
3
190
Transparency to sustain open science infrastructure - Printemps Couperin
mlarrieu
1
160
実行環境に中立なWebAssemblyライブマイグレーション機構/techtalk-2025spring
chikuwait
0
210
大規模な2値整数計画問題に対する 効率的な重み付き局所探索法
mickey_kubo
1
180
Sosiaalisen median katsaus 03/2025 + tekoäly
hponka
0
1.2k
電力システム最適化入門
mickey_kubo
1
560
ASSADS:ASMR動画に合わせて撫でられる感覚を提示するシステムの開発と評価 / ec75-shimizu
yumulab
1
300
Featured
See All Featured
Product Roadmaps are Hard
iamctodd
PRO
53
11k
Facilitating Awesome Meetings
lara
54
6.4k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
26k
YesSQL, Process and Tooling at Scale
rocio
172
14k
4 Signs Your Business is Dying
shpigford
183
22k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Statistics for Hackers
jakevdp
799
220k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
2
110
GraphQLとの向き合い方2022年版
quramy
46
14k
Become a Pro
speakerdeck
PRO
28
5.4k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
47
2.8k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
7
640
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