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.2k
Query Understanding for Search Engines. Chap2 Query Classification
hurutoriya
0
430
Introducing "Challenges and research opportunities in eCommerce search and recommendations"
hurutoriya
0
260
Auto Content Moderation in C2C e-Commerce at OpML20
hurutoriya
0
630
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
230
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
[輪講] SigLIP 2: Multilingual Vision-Language Encoders with Improved Semantic Understanding, Localization, and Dense Features
nk35jk
2
530
データサイエンティストの就労意識~2015→2024 一般(個人)会員アンケートより
datascientistsociety
PRO
0
690
AIによる画像認識技術の進化 -25年の技術変遷を振り返る-
hf149
6
3.5k
「エージェントって何?」から「実際の開発現場で役立つ考え方やベストプラクティス」まで
mickey_kubo
0
120
最適化と機械学習による問題解決
mickey_kubo
0
140
SSII2025 [TS2] リモートセンシング画像処理の最前線
ssii
PRO
7
2.8k
Type Theory as a Formal Basis of Natural Language Semantics
daikimatsuoka
1
220
GeoCLIP: Clip-Inspired Alignment between Locations and Images for Effective Worldwide Geo-localization
satai
3
240
数理最適化と機械学習の融合
mickey_kubo
15
8.8k
Towards a More Efficient Reasoning LLM: AIMO2 Solution Summary and Introduction to Fast-Math Models
analokmaus
2
230
言語モデルによるAI創薬の進展 / Advancements in AI-Driven Drug Discovery Using Language Models
tsurubee
2
380
20250624_熊本経済同友会6月例会講演
trafficbrain
1
120
Featured
See All Featured
We Have a Design System, Now What?
morganepeng
53
7.7k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.8k
Optimizing for Happiness
mojombo
379
70k
Producing Creativity
orderedlist
PRO
346
40k
Music & Morning Musume
bryan
46
6.6k
Typedesign – Prime Four
hannesfritz
42
2.7k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
22k
A designer walks into a library…
pauljervisheath
207
24k
Making the Leap to Tech Lead
cromwellryan
134
9.4k
The Invisible Side of Design
smashingmag
300
51k
Balancing Empowerment & Direction
lara
1
390
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