【数据聚类】第八章第二节:谱聚类算法之切图聚类、算法流程及其实现 ( U: y& z1 o3 n' \9 T" T/ f- V+ m/ E. q( N( _* h. t! Z
本文部分内容源自刘建平博客,在此基础上进行总结拓展3 w7 F: N, ]6 N8 l5 E+ ]
; a. V; V! g* ^4 Y# [" A! U$ Y原文链接& ?: z& R/ P6 H+ e
文章目录 & G" z4 ^- C( g8 d一:谱聚类与图划分 ' R' d+ R. a; i* I& J. a7 m(1)比例割 0 M& c' H$ n1 y4 _' X! @: ~(2)规范割(常用)5 k- Z0 Z2 B5 U# C4 N
二:谱聚类算法流程 8 _; m( Z- t, Q) V+ m$ E三:Python实现 - G" T; r& h6 D0 M$ S0 |四:谱聚类算法优缺点" D7 \& y' f: a Q
(1)优点 # j4 J {$ D# v0 f& T' ]7 U7 c! f# n$ P(2)缺点 $ `7 K( G* K6 B7 X一:谱聚类与图划分# l6 t/ n' F# |- |7 P |" Q& C
无向图切图:谱聚类算法根据数据点之间的相似度将数据点划分到不同簇中,因此将数据点映射到无向图之后,可以转化为图划分的问题。对于无向图G GG,切图的目标是将图G ( V , E ) G(V,E)G(V,E)切分成互相无连接k kk个子图,其中# F% P! w: G$ v3 C! T
# R% a" G1 } N* a
每个子图点的集合为{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A + t& ~$ d' r2 `* S
1 . w; c, G2 ~# i, q' f/ ~8 [9 D' p' }3 W* T8 Y
,A 7 ?3 Q& P H9 o$ |: v5 N# M
26 Q: s0 q X' Z1 Y, X
4 g" Y" e7 V r3 C
,...,A - I7 q* P6 i$ Fk # k5 {% z) X( {! a: u7 D! P9 E3 P
},且满足A i ∩ A j = ∅ A_{i}\cap A_{j}=\emptyA @8 B Z- S( o9 Z: C2 ri ! v4 {# A! X) W, R1 `7 P; p: n, ]* e }
∩A # t4 v+ y$ H& R) p1 W
j ]! N" A9 f9 f6 o# v) v- d / @, a8 l# @. i+ A5 i =∅、A 1 ∪ A 2 ∪ . . . ∪ A k = V A_{1}\cup A_{2}\cup ... \cup A_{k}=VA / H0 X: I$ c9 N* _1 w8 I6 M9 p# n" ~1 G1 1 `9 A/ \+ a5 [0 i* ]/ |$ b # o+ `9 u; ]; s; e ∪A % X( e, j& c: y" b
2 , O% w$ A' d1 m$ ]6 ^( B% E 2 h" [4 M! @+ \5 ^+ d0 q% m ∪...∪A / X; a: E& l M7 n0 \% |6 V! yk 8 n. c" X4 y, o& r, w, P, d5 ~( L& H& q" n3 A
=V * s- G7 N+ S5 V; V3 F6 M7 n2 G对于任意两个子图点的集合A AA、B BB,我们定义A AA和B BB之间的切图权重为W ( A , B ) = ∑ i ∈ A , j ∈ B w i j W(A,B)=\sum\limits_{i\in A,j \in B} w_{ij}W(A,B)= 1 m. b5 A) A0 j, y/ B1 K8 c r
i∈A,j∈B 1 K: _( h8 i" b; u) t∑ ) C; s/ r7 ]$ p6 V) C# y4 ` 5 Y* C$ [- `* W* \ w . R7 w- e$ c6 H4 o# s' l6 yij # U1 o3 {, o2 g: t7 T \3 X3 D+ `0 k, ]% c2 B4 q
& X7 E2 C; r7 _4 W' e对于k kk个子图点的集合{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A 7 V2 P0 S9 v3 f1 S" @3 ]% i* c1, h5 O# }+ `' U
) W( ]" Y% v/ k0 A
,A @3 Q( } y( [ x7 \, ]6 U
24 }+ o) ^' t1 E1 R4 H
1 F2 H- P4 p; v3 m; T
,...,A : @9 U0 G; e" l3 E6 {9 `
k / K8 |, H# E8 X( U4 Y- h% T# y2 h# Y$ s, K t8 L8 c; {4 B/ N* g
},定义切图c u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) cut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}W(A_{i},\bar A_{i})cut(A 2 K: M8 V7 T" Y! v0 {% V$ }4 E4 b
14 D" X6 ~4 a* k) T' c$ R+ I
. A# Q! ?5 B1 e! S% x ,A % n3 y1 S1 T' h P2 _* n' q4 Q2$ V5 x" E; W0 z! z c/ u" v
- J* d7 o* N$ g9 [% U ,...,A 3 x2 d" K. n% y
k9 a/ ]0 b$ N7 M9 y4 v! `% x" ~
9 E( C8 b2 z! ]' k
)= . y* M8 o1 b$ A2 P, n" o% }
26 k" y3 C' ?, N7 K4 Y5 l% R
1 7 m# b% Y6 T6 B0 Y+ @5 x5 H( Z ' N6 F2 R3 `9 ` % E- o$ B: W0 A/ [' u1 y8 Ti=1 : X4 m" Z( a% p( S+ n! U0 |∑ X9 a C! d# C0 w) F# h. }6 G. J
k2 @+ X5 Q: ~3 X2 Z$ B1 y# u
$ G- n4 B9 U1 ?( E# T; z
W(A 9 G! I4 i; |' h1 J7 e0 `i; [1 U$ }$ N7 t- z) w, G
8 x+ |, U+ H. ~, P s , - x2 f8 e% F& B1 U3 n, [
A , c7 p: g- [! E+ v+ cˉ 8 k( L8 w5 v g$ m: r# s/ f - ?6 E5 W* V5 ~7 f5 ^$ n# G, Ii # n' H: Y; j; L4 U' J% h+ N" z! e5 L s' T% d' z1 E' z
) (其中A ˉ i \bar A_{i} : L$ v" x' @$ I& I1 S
A9 D/ I9 D5 b0 s0 g/ M5 `
ˉ % Q5 k- x% Z% q- M; [# M2 ? x4 l- g, o7 U: m& T
i- {. C0 C4 X! k }( {8 q
4 H2 I; P( E! u) C
为A i A_{i}A 3 n, T) C1 C5 Ni6 i Z0 s! c% J$ ~0 `
2 x. ^% r' e% `, X0 [5 F- T( ]
的补集) ) v/ g5 T2 \0 j9 ?9 r" p+ S可以看出,c u t cutcut描述了子图之间的相似性,c u t cutcut越小那么子图的差异性就越大。但是c u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) cut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}W(A_{i},\bar A_{i})cut(A ! ~6 Y' J0 _' z, ]% a2 e4 o1 F( A! k+ F) R# g
1 4 Q4 N; X% R0 {% X) I% c; I1 V x) L( e
,A c! j B, j6 j7 g7 v6 p2. D- h0 d7 Y* ?; Q- @) j
9 i7 `% h) b7 ?
,...,A ' s* M7 v8 A* I# H$ Q* @k . v( R" ` j& m4 f& T8 f' Q+ H' v }
)= 2 K7 e& ?0 v8 {( h0 b0 _
2 ( O. {: @) R( m5 e5 O0 Z11 w) W6 J! d' z% M. M- ]- `
/ i6 j# t, U; l! D& C8 b: \% h6 K
$ h4 C: Q' ^4 ~i=17 r7 w# m' x! @* ~! [9 ^: u
∑' R) j0 X; P: \; e$ c" N
k ' y6 m, H- s- o# ?0 o* z2 E; r $ G: m/ a, Q( B9 D3 J W(A 9 G) D# g- ^" l. l9 ki : X8 u3 \4 T; t7 i/ O5 d* j+ C% E& {( ~2 H( z2 s- S
, ' ^0 [; a, F2 h4 fA $ X7 u ~8 M- [9 y/ k9 D4 ^ˉ" c& U. w4 D$ i- J3 `3 r o
% u' H; z$ J! ri2 C: x# b% l9 c6 p$ @& q9 C
- z' f/ H- V* o+ Q; L. r2 x5 l
)在划分子图时并没有考虑每个子图中节点的个数。所以在某些情况下,最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A 1 }& j _/ ]+ L7 e' Z
1, w: }/ Q7 N; M# |% t
# | \! D# D0 b7 D
,A . `# @) h+ t1 U+ d: U4 \" \
2 ! c6 w0 m _, ~+ d l1 J9 m/ Z7 {( `7 h( ? ,...,A ; M4 O8 Y$ {; K) @2 fk6 M8 |0 h" X1 q l7 m1 N3 P
7 g! `; j' Y5 v j. D0 \ )可能会把一个数据点或是很少数据点看做一个子图,导致子图划分结果不平衡 9 `+ V3 r s) k i | ! M, _ f! z+ ]6 x例如下图,选择一个权重最小的边缘的点,比如C CC和H HH之间进行c u t cutcut,这样可以最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A 9 }( Q# O7 d4 p, F1 & A+ G& L0 I8 j3 O* y" K0 E7 ?7 k; T: N1 D7 o( u3 o0 \
,A ! K3 k7 i% q% R8 h2) b: {3 J# S: \5 _
3 X A4 A" ]* I9 w) V7 e- b7 V4 `
,...,A ' b9 y$ w# _) S9 Ak 3 H7 h% S, `3 ^! |" ^' }9 G$ F1 h7 V1 K
)但是却不是最优的切图# h8 n& d& O' V( c( [2 p
- g% I. d9 B: [/ W: C为了解决这个问题,会引入一些正则化方法。最常用的两种方法为比例割和规范割 }9 S5 G9 S7 p) ~9 y, X- f
J4 K3 E; t) \2 p2 p比例割:R a t i o c u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) ∣ A i ∣ Ratiocut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_{i},\bar A_{i})}{|A_{i}|}Ratiocut(A 5 u j$ C/ h. h# I! w2 ^
1 ! W- o8 e! I# q/ D0 Y5 n, S) t; c b4 u' g4 w. F
,A " ^( m8 ]" O( K9 A5 x27 \' W7 a3 V7 o
6 f: g7 s( \9 x; Z$ z" M- F0 W
,...,A ' _& z3 w) |. B& Z: e# a8 d7 fk 3 b; s! J; y5 H8 @3 G, {. o, d- _6 J+ r4 X/ ~4 M4 W. Y- }
)= / i: `3 \1 O9 L- w: r& y
2. Q& p. p B5 m6 | f4 o! \7 Z
1 ( K8 _3 B9 r9 M$ n8 G 0 P' ?2 w# P! z x * s% b" D: J0 @: ~; {( B, `i=1; @! h# t" O Q( {5 [( k
∑ / {& C. s# R0 R6 F3 {- L5 j! gk2 E0 o5 c7 y* ~( D. K1 I8 A
- F5 F6 O5 ? Y" @; _: O$ Q/ I5 `+ `( [/ E1 ]& N1 W7 d! B
∣A ~1 P7 t9 b/ J% n# v/ Y
i) G7 \2 K( B% V" |, b8 ]
Q3 X. o; ?: E, H" h ∣$ U# R5 S6 |- e1 Q
W(A 7 } m2 w. Z1 [# M1 U, s. i: U* Ki1 }' `6 O3 U8 a$ f) }4 K
' x+ O) K3 M3 C , . O2 W, |- a) e) q4 C$ Y& _/ yA 2 T9 s% ]; Q. n6 _ˉ ! g& Y/ i4 s5 d) z8 F5 x3 U0 W: q9 Q+ P9 j0 U
i9 L- x2 u$ K2 }" e& }- c. y
0 S# [ B. v5 b0 U3 V, A; F2 j ) O4 J6 u5 G# q5 e0 K& @& D ) Q4 k5 |+ C0 L ! z9 M3 b: z& L* O规范割:N C u t ( A 1 , A 2 , . . . , A k ) = 1 2 ∑ i = 1 k W ( A i , A ˉ i ) v o l ( A i ) NCut(A_{1},A_{2},...,A_{k})=\frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_{i},\bar A_{i})}{vol(A _{i})}NCut(A 1 _& x" @9 @5 G) I% O
17 O; z/ ^" F, U2 E
* N) X w% @. q7 _% C ,A , Z- v6 p: f4 ~" p: j' X, O2 ' j/ |' S: I+ G, M# `# H% f+ p0 k) ?' \$ M9 t- Y5 K
,...,A & Q7 {# q" _, k/ Ak 8 V" m3 F2 t% a9 B/ e/ u- M 2 g7 v" ^3 Q" c; V/ B- c. b )= ; ?' M$ u, l, i; i2 # G$ a1 X$ j* q L* Y; s: M1 F1 2 J n! s& @$ A4 O' {' b, T5 s4 F2 o
9 z, R+ m$ s! i Y R7 ^1 T2 v. K
i=1 . @3 n9 ]# t% ^/ s7 \ v6 T∑ - o, p" o) e$ n3 w$ h3 ok9 U- p1 {9 `; V' |& b) O
$ o- [6 h4 z% R5 M1 W) r H( D, g! Z2 Gvol(A 3 C8 h$ }( q4 t- D( W. H3 n( h
i/ h6 d1 ?+ z2 i6 ]* x
" c" W: S# ?" H9 _9 @- H, ?; @
) # g3 y. F2 a# ?( Y8 @W(A 5 o! j9 @; W- ri; a- R9 i% c, @' u c+ o( F. L) l
5 C2 {2 B! a9 f& e' n/ a4 R
, & Q, P% Q s \- e, ], H' J3 n4 M. g6 O
A ; k( J& w& _9 ~. C3 e: B0 Bˉ 2 H9 w; H; ]5 q8 x! H( K; A4 ]) M4 i z' e0 p1 Q. y
i$ m- E8 P1 l& I6 I& \
$ @# ^; y* W; l( f, \# l
) $ Z V7 C& N/ d' w& j- [) i+ ^4 U$ V# w- r+ p5 [( x& w
( @8 u6 C+ x) h; B" ^(1)比例割0 h6 B, K" ~ b1 F/ u8 X) _
引入指示向量(点击可查看指示向量定义)h j ∈ { h 1 , h 2 , . . . , h k } h_{j}\in\{h_{1},h_{2},...,h_{k}\}h 3 J. o0 @4 h8 e' F% [0 w, z
j c: ?) Q- }& r" J' u0 s, F" |* P/ b- e
∈{h 0 p l! j) n6 P7 P$ ^4 D7 z+ p1) ]0 i% {+ V! T
. o* ]* n6 w R' r3 h/ [. w
,h 2 |4 q7 W( s0 Z6 _. W2 & N$ d" ]$ n' `" u 6 W% }5 P' ` K, Z' V3 ` ,...,h 6 _0 f- N* Y* x0 Y6 p g
k* ~4 R. W5 W4 J: I% \# t/ Y
& I R3 r( W3 L% |& D2 R0 E2 U },j = 1 , 2 , . . . , k j=1,2,...,kj=1,2,...,k。对于任意一个向量h j h_{j}h + V# z3 [0 r% z; n9 {" q& }j ! X2 v+ F! H3 ~! t- i4 n5 G$ { , e% ]! T# }9 d/ m. w2 O( q ,它是一个n nn维向量(n nn表示样本数),定义h i j h_{ij}h ; o6 J3 a+ N' v. q+ K$ _) wij0 O Z: I2 G4 y/ |0 i8 F
) W) _1 a+ v2 G/ m 如下 + _0 z m4 v3 G3 @! N+ p% {0 ^" R7 n( C" N
h i j = { 0 , v i ∉ A j ∣ A j ∣ , v i ∈ A j h_{ij}= / I$ n! N! [* u. M{0,vi∉Aj|Aj|−−−√,vi∈Aj + `7 A3 n" z7 A$ _ a- h( Q) M9 `{0,vi∉Aj|Aj|,vi∈Aj ! ?; |+ S+ q$ v- I1 Kh 8 i$ |7 g0 V3 ]* l1 }
ij/ J, R: `4 U; g! m: Q2 Z. N8 w1 H
3 m" p2 W0 E* ~1 f8 W$ B/ L8 ]& L ={ 1 T% n+ m5 E& [ D. B
0,v 2 d/ e5 t% E8 b. ~
i & ?; ?4 ]1 j& M% S 9 m) z8 a5 @. m& t' p3 ]5 C/ W ∈' J: K, v1 i8 x, q0 {: b% f- P
/ + n( a5 p3 C0 }3 _1 m4 eA " B1 @3 K$ B" Jj 9 j7 H S! Z5 S+ g9 d ; Z3 q& O0 f, ]7 e! i P1 u+ ~: G: q9 a5 i9 d9 D2 T5 d
∣A / d2 M) l6 N4 B: u2 gj / k- {( f8 J' |4 q - B) h9 W. I3 V% F ∣* s# k2 f& S( J
- G. e; d' x3 I2 `% g) M ,v 4 A8 s% q% h/ m" b1 d) T: j$ H0 Bi2 m. @+ m0 ^) a+ _6 N$ D4 ~
/ u6 a/ R8 ~% w g& n [! _ ∈A 8 g1 E! I* E) R; p6 w2 J8 Ej , e, D1 m7 x: \* F5 f6 f( H: ]9 [# I6 t4 q
. k! I9 s( y' Z; m: ~( B( \ ) S8 _, `$ }: v$ P # _9 }8 p1 \6 h) m4 j* ]3 y$ |- K* a) q- [! H
于是,对于h i T L h i h_{i}^{T}Lh_{i}h & w6 M6 V y. J% [* T, V9 pi. B: b" h l% u
T% [1 |. t7 ~3 |
* H# o k3 Y, |1 e6 e# T Lh \8 A9 n% o/ ji0 }2 E/ J; N3 X% ^# a3 {/ O8 A
8 P2 W" j/ M. e ,根据拉普拉斯矩阵性质可知' G; _' Z$ d4 S$ r( t: a" T; h3 D, p
8 n" v/ L6 [5 ?4 T- H/ q9 W' c. X4 M0 E
对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f : E! K% z* w1 E' k; A5 U. ~" _4 h
1 & c1 A6 C! |6 O6 j0 t% J! k6 l$ n. n/ H, P/ W
,...,f . W9 W5 U T6 I- M' o. G4 Mn " j4 n. r& f1 d+ n % d3 i$ h) Y& d ) : H% X0 A3 E# A4 F/ M. o" Y
T ; q5 d* V- w- O. e! R0 H ∈R 8 l. i# @: \& F! y9 in% H# g7 a4 b2 x7 W- Q% [
,有f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^{T}Lf=\frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_{i}-f_{j})^{2}f ( g$ j, K; C& b9 e! ]3 ?* D5 `
T' v. G; i8 q! b7 R- Z0 X+ k
Lf= j) }% q, P3 N4 b& m7 J) X
2' D( s$ |! ^& @% @ Y7 _# F
16 h7 ~4 T5 i% v. n; D
; Y, v8 c {, f3 @+ q. o% C
/ f& Q+ w: L7 x- ei,j=1 & s7 G: y3 }# }- M4 o; w* x∑ 3 Y4 R. j1 i$ ]$ y8 Qn 7 M5 ]. q& Y; z% o4 D5 e6 H7 z% i0 q3 M F/ Y
w 7 U) T) x0 q6 f
ij ; p( m2 n) {1 w8 `& b# ` ; g9 i0 } n$ J4 ] (f o$ d- M7 l; G/ J U, @/ p0 |9 \8 M
i! R( n. Z# X3 Q, _
- v# g0 K% |' u# J% c4 J
−f 8 o$ T$ q7 n3 @+ T$ g6 g
j - M/ J* z2 o9 w# T% |( M - I$ G% |. I* A$ |+ G ) / I. D1 s! I5 @
2 * S: `: o* P6 d" f5 @! ]% t) z; p! t! e% e
h i T L h i = 1 2 ∑ m = 1 ∑ n = 1 w m n ( h i m − h i n ) 2 = c u t ( A i , A ˉ i ) ∣ A i ∣ h_{i}^{T}Lh_{i}=\frac{1}{2}\sum\limits_{m=1}\sum\limits_{n=1}w_{mn}(h_{im}-h_{in})^{2}=\frac{cut(A_{i},\bar A_{i})}{|A_{i}|} 4 V; m! A! C7 c0 ]7 ^h 9 B% C$ G( U5 M9 H. a" T8 F
i* g6 z6 O' [, A" r& ~# N
T8 H& j6 u$ \- m' f0 c
+ v8 N# F+ N7 B
Lh 9 }2 i1 g+ C A+ W/ _i4 G p$ }9 g# w
/ q, t1 p9 V: ]. T = " v3 q# Q4 U) ]7 H$ ]2 3 N4 q9 N9 q( F! Y# L- x14 k% ^. \/ w7 f" b1 z
8 W H% `0 ?8 U* E+ {. o& b3 R . q# z) ]; O2 n- |( A. z3 x3 F4 Nm=1 # _& f+ ~) x/ `: @4 H8 q∑ + s; c& M* @6 g& m/ H9 ]2 ^( n% Y& [ g
8 N) n6 ^* E% d4 [1 o3 Z Vn=1) b# J5 ^; o0 x- i \3 P
∑ ; E, N2 Z) g- k% v- U; p4 q4 X% l& J. Q* L) |
w % S+ U) E, _" g V' u
mn 9 J6 o4 n9 j( c# w3 F3 {6 Q , V- n8 n5 b O# ~8 A8 p% b$ X' y (h ! ]& J% O; T% S% E$ i0 kim 1 {; F& ~4 l9 h b) y4 F) [; u* }7 T2 e
−h 8 x1 _7 o( @) J! U7 c
in - W- x1 n+ _! m9 X, U* K, r& e1 ^) g& `
) . D3 y, t( e0 w1 o: m; V2 ; o1 ]# w1 R* w3 `0 n = $ G# [% e8 a _1 w1 S N( _∣A 5 {* i/ B* _' u5 O- _i! e) Q( C2 L0 Z$ Z3 d! |4 e
3 a0 a% u. q% R! o. k6 ~$ u
∣) @# N. U6 N7 \ X9 `
cut(A 6 h2 z4 ~3 \# k' ] ~! n1 c$ Si ?: z. i5 @7 \( ^$ d" M9 D1 n$ h# f! A7 R
, % K0 U9 l# I& E7 _A 4 |" ^5 F, U4 S: @ˉ N/ p: G* E8 _$ z1 w, }
9 a3 j6 @6 r8 _ Z) s0 h, Y! {; {' ]
i0 x' W% d' J+ B% F7 Z
- s% [, ^; _2 p# } ), k2 w& t5 j( z+ G# F# {
( h3 z$ j# A. P8 w0 x- Y ' ~) L, N4 }' }2 O; g8 t6 P9 l0 `" l" Z0 {6 p) s x' x) v d# z
严格证明过程请看刘建平博客:链接 & k J. P; B9 r2 H8 h/ s( F可以看到,对于某一个子图i ii,R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h / ]/ f' {1 i; O, Z4 D/ u
i / J# _5 N X1 d5 ]0 ^8 NT) w. t( x) ]3 J
+ j. f) L! J- [ Lh ! l; D7 ], V- m oi' R/ w6 [& _; F( |. r
8 k: }4 D. ^+ [. h) h2 j
,那么对于k kk个子图" ]0 `9 E% Z* @ Z: U; R
6 g( B* ?8 c9 F4 j
R a t i o C u t ( A 1 , A 2 , . . . , A k ) = ∑ i = 1 k h i T L h i = ∑ i = 1 k ( H T L H ) i i = t r ( H T L H ) RatioCut(A_{1},A_{2},...,A_{k})=\sum\limits_{i=1}^{k}h_{i}^{T}Lh_{i}=\sum\limits_{i=1}^{k}(H^{T}LH)_{ii}=tr(H^{T}LH): G9 ~; c/ L' e( H% g
RatioCut(A , P- Y- F) K6 Q9 `6 u; y3 \
10 ~$ M' W5 P& T
, \1 p& U. i% A0 s- b ,A 6 B9 ? x! |4 p0 M$ x
2 9 `! F! ~ ^5 u 8 u0 a0 z4 {+ P# w6 g8 X ,...,A & i4 D$ o" M( d- d; r* y5 o. r% c7 T
k 8 A8 u8 O6 P% j" z2 h7 ~) |+ G6 ]; S$ V
)= " O( j* J, U* I3 ci=11 x- }- |5 ]! C) D1 s
∑7 t1 w+ l2 ~/ c
k . q3 |9 M2 S6 \2 C/ D k% X3 i: k+ b2 J. T/ h
h " o- R# y6 j9 T; M/ y3 H* A$ t, F% T Ui1 k# s7 \# A6 g" k: N- R
T 4 g1 o2 ?9 d: v! z3 R, C0 R# @ ) B" Z, d' ]/ Y* y Lh / H+ m- W) W8 D3 W6 ~
i# I1 o. H8 {3 U6 @! i, {5 x& n* E+ B
% ^5 I' c; W' a. ?3 d" v( O = " G( [: ]2 N @) }4 xi=1# x g4 x9 s$ ?5 @
∑% v/ w$ K' F% X: k
k% b9 K. ^7 x$ x* q! q1 p
& H, i( O! u5 G (H $ V/ X* S% U" j- U8 k; e
T( T5 f2 [* A6 W; V0 ]* x1 o2 s
LH) % k: z B& i) z- _
ii 2 g& V4 } Q$ f% @9 A3 n; c& ^% D4 @6 m
=tr(H 3 A* u8 m' }2 X
T $ \) z! I! F0 h* I LH)9 t+ Y \$ F9 \
3 W; i. }* `# s% E) y. s+ z: I因此,R a t i o n C u t RationCutRationCut切图本质就是最小化t r ( H T L H ) tr(H^{T}LH)tr(H 8 g& D# e/ @' [T + I; x1 |# H2 i$ l5 x) t F$ A9 S LH)。又因为H T H = I H^{T}H=IH 0 D% g; ^! a$ Q& s+ B8 d( q3 m
T * L2 L4 e9 e" e. B1 l H=I(单位矩阵),则切图优化目标为 7 t8 a% K! H, L. c. U4 d2 e7 Q 3 m1 Q6 `; {% c- B7 `# Na r g m i n ⏟ H t r ( H T L H ) s . t . H T H = I \underbrace{argmin}_{H} tr(H^{T}LH) s.t.H^{T}H=I% N" [- C, P% j; [3 C
H2 ]1 @% u% R* [4 h8 r
argmin+ B: W: d1 w7 s+ t7 i, S, ?
/ p9 A! |. l7 `6 `/ j$ v" _( m 8 t& w) ]4 _, J1 A. t j: g' y- X: ?+ q+ x0 k+ P# o6 B
tr(H " E+ ?, v" L L5 L2 U5 hT* G+ {7 ~) G9 @& j% M5 c5 m- \
LH)s.t.H % F& ?4 s6 @4 g2 {2 p9 c: k
T) C# k7 q6 J& n+ \) c* J- t: Z
H=I 8 R7 U0 Z4 F$ P9 d8 N) X 1 A$ P( F( m- F8 O对于优化目标t r ( H t L H ) tr(H^{t}LH)tr(H : ]; U1 j: d* St1 a# A8 M- ]. O
LH)中的每一个优化子目标h i T L h i h_{i}^{T}Lh_{i}h 9 R6 T8 \/ w" h7 i8 ri 2 s: D0 O5 C9 a* h1 [2 L1 y2 p0 }! fT, C5 s! @# y% L8 W* Q2 H4 c9 F) ^
: v7 d2 m% o. w; R7 W) T* _6 U Lh # c |( b. N- Y$ Y. }7 q9 A
i+ B1 J5 ]; T( o% ]( ^7 _ B
0 M$ T: q* q( j# J* z: E ,其中的h hh是单位正交基,L LL为对称矩阵,所以此时h i T L h i h_{i}^{T}Lh_{i}h ' e5 k! n) @( C* G r# q: }5 N8 S1 N
i0 d1 Q. d Q1 K
T & C7 K5 f) k( g0 k y 2 O" \& |. X: T4 @" {0 G8 A2 [: e Lh , ?/ O$ \* R! Y( qi7 e5 |) U2 |, V8 D
' C! S0 q( h5 x: J* u, @& `1 N( [
的最大值即为L LL的最大特征值、最小值即为L LL的最小特征值。而在谱聚类中,我们的目标就是要找到目标的最小特征值,得到对应特征值向量,此时切图效果最佳。所以对于h i T L h i h_{i}^{T}Lh_{i}h ' ^9 r4 c4 c G- A" _) A% X. @i) {" ?% T# W- W" o1 f3 E
T, I8 i8 t& k& g0 B8 F
* ^, b5 H1 k8 v1 G. r+ s8 Q
Lh & c; W* P+ K2 O$ _( F
i! [4 E$ O( g p3 }
# \6 b+ h5 v7 `; I) L7 ^1 @ ,目标就是找到L LL的最小特征值,而对于t r ( H t L H ) = ∑ i = 1 k h i T L h i tr(H^{t}LH)=\sum\limits_{i=1}^{k}h_{i}^{T}Lh_{i}tr(H # i) @6 `; d( P( z4 b0 A
t y" `2 ?& L0 C+ Q) p
LH)= / A2 `6 g9 B) W, s1 T- S. J
i=1 & R; J" f( O8 J9 x* E) _∑4 |; z) @- o. W# {9 m
k + S! P9 G. S% r; M8 Q 6 E5 h W/ L7 ~6 @- l8 { h 5 ]' K" f" r* q; A7 N1 o G
i 4 w. H! D8 t- }; @! f1 f* OT 8 X/ {: R( C6 Z W# l # v# Z0 ^ [ _2 Q7 X; n Lh & P7 g9 X4 w: {
i 4 ~4 L) k! H K. S8 D& B, W) @9 }/ F$ p
,则目标就是要找到k kk个最小的特征值$ B0 [/ L3 B; U2 b$ l
% W4 o9 e5 h& D, n) j
因此,通过找到L LL的最小的k kk个特征值,可以得到对应的k kk个特征向量,这k kk特特征向量组成一个n nn×k kk维矩阵,也即H HH。一般需要对矩阵H HH按行做标准化,如下 - P$ p$ i/ i, [1 J9 m: s+ R! X1 z" Z3 b4 g( _9 x: y
一般来说,k kk远小于n nn,也就说进行了降维 ) q0 D; Q& `; V! Ah i j ∗ = h i j ( ∑ t = 1 k h i t 2 ) 1 2 h_{ij}^{*}=\frac{h_{ij}}{(\sum\limits_{t=1}^{k}h_{it}^2)^{\frac{1}{2}}} % ]+ R4 G7 I5 I; x7 J6 Dh : B" L* b d6 c; ?# W3 tij" W: E6 R3 e, S( [! o9 r* h
∗4 S; @+ V+ y# s W" U
2 y" Z7 d1 a3 N. F
= * M; O/ l, q+ G% r9 S5 n" q( " c' c( {* I! K0 et=1 + T+ n# Y$ g* u: v- v% O∑. Q% B0 S, i" Q8 j
k1 e s! X/ Q" s" S V1 V
' a" G, z9 \7 {6 i+ T" J/ w h 6 Z3 w- J% ?9 |8 H5 [
it, G" _# u/ L4 s6 t( V
2 0 l; v$ B1 H6 t6 q3 O / A/ `" O" X2 A4 N/ v1 S5 }1 h ) ' f$ D# j0 w: [! N8 s9 l+ P5 v: e b2 ! d4 R) i3 i: n* l( e C1 6 C. w3 J( Y/ r4 P7 d2 ~9 d( M; c, [7 i' r* X+ V, v
, D- F0 J5 V9 E ]& y @6 f6 z$ p7 z1 lh . T& k' \ G) w7 Z' l1 W! r6 W
ij* \, p% A5 J0 u: }4 `7 {
4 l5 I3 o- P! d, b" v- r/ o- I1 N6 o
8 L0 o& I; Q5 S; t. Q/ V9 f4 L5 t b6 y5 ]# v
! w! \$ M* ]; }* P* j这里需要注意,降维后导致得到的指示向量h hh对应的H HH现在并不能完全指示各样本的归属,因此一般在得到n × k n×kn×k维的矩阵H HH后还需要对每一行进行一次传统的聚类,比如使用K-Means聚类! @& ~, _: { g) v9 T! U
, L% s' u/ { F
(2)规范割(常用)+ U7 l& G+ V8 @
规范割和比例割类似,只是把比例割的分母∣ A i ∣ |A_{i}|∣A $ h& B) v. O9 Y1 a% ai 2 t V& ]. V! ]$ e0 Q4 l6 j$ Z$ ` ~' F+ d2 ^1 z1 M9 `
∣换成了v o l ( A i ) vol(A_{i})vol(A * R0 U' Z% q* F- w5 I) T. O3 s
i) }" }1 ^/ Q7 E" x4 A* s
5 t' F/ S& d" b. @5 e7 j ),定义指示向量h i j h_{ij}h ' `( n' @/ Y. u" d$ @5 Bij " ?$ Z& ~' `8 t5 w( c% |$ o) v) Z + i, k7 T' p" }3 } 如下 0 u7 N* r: e- |* Z8 E+ n ! q: g3 s' ~; l, rh i j = { 0 , v i ∉ A j v o l ( A i ) , v i ∈ A j h_{ij}=" j* S. g b$ J9 b$ u% o
{0,vi∉Ajvol(Ai)−−−−−−√,vi∈Aj& G! d/ J' p! z& e2 Q' A
{0,vi∉Ajvol(Ai),vi∈Aj + }/ t8 B0 f4 u: [h # M% i9 m3 ]; s6 u9 i" X7 v& m3 k- [ Q5 gij# D. i; F/ S( H1 o3 J
8 `; y/ `9 m( @' o) g0 w; z ={ U8 j' j I0 L/ K1 K0 |
0,v 2 y, p2 q, i; e& j1 n- ai. E1 |; a, I4 ^' ~
- o+ t3 x8 W8 S) A' A) f/ _, P ∈ & C d- p0 t! q& Y/ 7 r `3 M9 Z, X; [6 |5 v, N& ~! lA # N- z; C Y6 j8 K! N5 ?j5 g- S& R; Q& d3 S% X
- p4 ^9 p$ M% j0 H: P
' L( W$ C, h/ p; `
vol(A : v- y0 G. k* k Ri7 M& V+ f. x, C- u f0 ^
, U( S& r4 c! y0 K$ c9 f
) * n( R+ J; m1 [$ }+ e9 W+ r* e! H8 r F2 b' r7 j
,v ( v/ `8 M {& c6 ti ( d& q2 I0 ]8 p" m4 B" S% `6 X, L- c8 Q6 {& z, X
∈A - ?; t7 r7 A& E' f2 Cj " L; T" C& S* _& t0 {4 H' S6 s' }. E& a/ Q; b- [7 Q& y/ K5 j( [7 I
6 ~0 o$ B/ G- W8 ], W6 V ! ^8 {6 X- r3 A* E. x0 l, d0 ?9 x0 g1 D: u6 w8 D
! r+ c: ` j1 P' u) g$ S+ u
于是,对于h i T L h i h_{i}^{T}Lh_{i}h # i& o( }9 K0 k' o( w. ]4 O ^1 mi, Q4 Y! ]4 O5 Z3 ~( q; L, i& d0 i
T3 r5 W1 b# C$ J' B: Q
. F3 i/ C. t' ?$ r5 D& m ] W
Lh 8 d, i- Z" @1 ~0 z4 R3 O) F
i 3 O2 [3 ?1 a b- {1 s, \- o/ j( i) k( \7 A
,根据拉普拉斯矩阵性质可知$ `# g2 t/ }2 ^
) G4 W1 m; q$ _9 n, Z- m对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f 6 D1 ]" Y1 }4 _3 ?3 o1 G0 @1 % Q( |3 J8 R1 ^- ?# C0 {- B3 s8 Q$ O- H
,...,f 5 P4 }) R I7 [% P% N
n - G' z) V1 y' U3 |- `/ A( Y4 m7 K6 V6 F% q/ g2 |1 c
) 4 K+ w5 Q/ E; @8 F* I7 H! x
T + @3 D! M$ ~/ `5 I$ g ∈R $ c0 q6 N2 ]! Z% r( G' c
n* K' s4 y; h8 H' P0 ^
,有f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^{T}Lf=\frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_{i}-f_{j})^{2}f ' k- }5 B$ W& p, O
T 6 _4 ~! u) u+ Q; Q5 B+ J9 k7 G7 Q* v Lf= 9 c" d% i6 f6 ?# I# d2 ) @$ @& A- k5 ?* b0 G1 @' O14 y3 x* o2 `' @# N* d
; {, R' r2 k8 ~/ ]1 t y4 v7 w, X, i: s8 [) Q1 D
i,j=19 S) g# P) L" U+ D* J6 o0 k
∑8 {( L5 {/ H* p1 a; f3 T
n& b! p% V! C+ A, g; m
+ V/ r; Y* o$ `* C5 S' ?
w - a$ L2 Y' q% W2 d. E( d1 ^; M7 Kij / q, W( C$ @7 {& |$ m o. r% z A; x; Q: o
(f 2 S+ g& \. k0 f6 Hi- z& j0 J. a# X8 @& I3 g; \
2 y2 D5 b9 D. c8 c+ V% g4 R( } −f 2 f" c7 D O) ?8 K, w/ o$ x
j. K1 ~- e, n _! a# I$ m
7 O o* m1 X6 e6 K
) 0 {; ~+ T9 Q# o/ X0 k, E
2! l3 J+ t5 S+ E3 h4 P1 v
% X S T7 ~! Y2 ^9 zh i T L h i = 1 2 ∑ m = 1 ∑ n = 1 w m n ( h i m − h i n ) 2 = c u t ( A i , A ˉ i ) v o l ( A i ) h_{i}^{T}Lh_{i}=\frac{1}{2}\sum\limits_{m=1}\sum\limits_{n=1}w_{mn}(h_{im}-h_{in})^{2}=\frac{cut(A_{i},\bar A_{i})}{vol(A_{i})}, D/ z" K) N: T# a7 B! V
h 7 t" ^2 c$ @1 @+ }i& k2 X8 K" f% `
T3 @4 F/ r9 \4 k( m2 ?
9 i' N6 t! B$ O: q6 d; h6 D& q4 T Lh . }5 s5 f: I Q: U) w2 h% ni n/ h. E8 q2 c; J4 ~ * t5 D- {1 O5 Y; N = , {: o2 O. t H# [7 _! d2 * m9 o* k& L* ]: I. p% P3 J1 , `; I- r2 W. R" {. t. f9 _7 w' u; q( c; x9 _
e* Z" M( c& F/ p
m=1 $ D" X+ i; k! ?9 x, S+ T∑) ~ j1 \. m9 I' u; h% e0 x3 I4 |
. u/ S* O( {1 `- `7 W8 R2 j+ o! T, g9 a, c
n=17 x+ `. `8 ~" r; ]
∑ % f3 q2 a' I$ K7 R : g8 y7 K+ t+ R: M8 ]8 u( }+ u w % [" @; y3 e! ^ s( X' H
mn 0 G4 F ?$ ~( W# p1 {! H9 V/ Q# Q V$ T s1 {( \# u2 e
(h % g# R* `4 p% O q* D
im 3 }/ @, \- K/ v3 Z# G8 `- _" K/ F0 P3 [; r9 Z
−h 5 t2 O1 Z. v7 Z: t3 b5 T( a1 Q- O
in# @9 j* A$ l- s0 z+ N
( o/ t, V+ `" t; U U' d/ C
) " ?: W! q5 ^ m, e
2 4 {* \; f* M" G3 m# H; a: j: r = * L4 T7 i8 C A1 ?
vol(A 7 t2 ^8 p" ^4 S& J3 qi - B9 w2 H1 ]8 f A x" m $ @+ z+ _$ h' D, f R& P# P% \ )8 f1 N# ^; F8 j# b
cut(A 7 Z; ?- K1 a+ s6 C+ q; e& Vi/ y& W' W% n0 v+ ~ V
# q" `+ H7 @* }8 a# \( v( O1 _
, ! u6 F: ]6 D) \/ p8 GA ) }2 U" Z7 s% I/ n5 N4 tˉ2 B# X7 @0 M3 D7 [+ ^1 y5 ^
7 j* d3 p4 }- b. {; k3 S. b ni7 N& y* g. L( }/ c' o0 Z
r6 j/ x4 W) Q ) * F9 {: K! ~; [- Y3 E/ q5 O& N4 @2 Y$ K1 y2 B
8 e, y7 x9 p, J; J 9 D5 Q6 R" ~, E" b- D严格证明过程请看刘建平博客:链接 % v8 E" }5 d3 b/ S# T/ c可以看到,对于某一个子图i ii,R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h 2 W$ Z9 g3 N8 S, ]4 g! _i ! I- G9 e# @$ L3 [, vT ) |5 a- h$ @" c. [' |* W G) J J6 U7 L$ Y& y0 E. \8 W2 C0 S Lh / ?! u& T* X' Vi/ o/ y4 N6 F+ r1 [
6 { T3 R5 c7 \! f) H6 z
,那么对于k kk个子图 ( Z( c1 A9 a/ \' C! ?- e ) X& K# Y4 I/ c" z6 BN C u t ( A 1 , A 2 , . . . , A k ) = ∑ i = 1 k h i T L h i = ∑ i = 1 k ( H T L H ) i i = t r ( H T L H ) NCut(A_{1},A_{2},...,A_{k})=\sum\limits_{i=1}^{k}h_{i}^{T}Lh_{i}=\sum\limits_{i=1}^{k}(H^{T}LH)_{ii}=tr(H^{T}LH)0 w5 @ j# Q* N' X
NCut(A 6 r4 L" d; S; [5 j1 $ `+ c3 F) l1 b3 n: v6 [4 m3 @- w* B. N9 d h" W
,A * \) t5 \3 O" w' Z; E% I
2. f- C. I. g$ @# C
; X3 m) S8 I) V+ c3 h
,...,A ' n8 j, f8 z' {$ e( p5 i1 _
k : K) A* ` t! T" j. t8 w* ^6 V ) U* T3 u- h5 h& R7 C. Q; T2 g- o )= , R7 B3 p6 Q3 C/ N; S" s# _; m- S
i=1 + E( d* x g; k2 p∑ ; y* g% p0 B6 Y7 g) |% _; Lk2 F" r; n8 e" ^$ [! q7 g' x+ ` f* L
, F% w; Q4 b \( T3 g- _6 u- X
h ) B8 V( x/ r1 t0 A8 E* w% Ci . i9 P; Y; i: n% g8 i' b. b9 ?T- q* b' @' T; K* w
3 P0 B5 N4 V! e& s5 K1 b Lh 4 ?! S. J& {8 v1 i3 D$ j& `
i # W8 j" w% z' S4 I8 R# s8 W 8 W4 d ~2 U- d! k4 `5 t3 h' g- P, U = / d# f7 b2 c, V' }
i=1 6 B. I/ ^. d; _; H5 ~# E2 I/ v∑9 T, d0 N" V6 ?7 T
k + }; |' X1 g, G" ] P( `) O! x# w5 g& H$ w
(H / ?3 v- N9 e) R, K
T% a4 W5 o% o- c8 p0 n' @+ u" ~5 q: S
LH) 9 y; `/ K; G* W& Kii 7 F2 ]( ~' Z1 p 6 @" H) R; y2 h =tr(H / ~+ Q/ e4 r' p% Y
T) T" f9 Y/ Z! ~: g0 }8 t
LH)2 _! J) B: S/ l" }/ K
9 i) O+ F+ c8 F8 g2 n0 t
但此时H T H ≠ I H^{T}H \not=IH 1 e& _( B$ m- P, y
T& m0 m e' q+ n0 c& \1 `
H" x( \) e4 E& V; g; B |
. X% V% ~) N7 X( K* N( w=I,而是H T D H = I H^{T}DH =IH ; t) k# y) D% ?$ @/ F- Y3 D% o. {T; T, H+ a. T# N% d' G
DH=I$ p" P& F. S% r4 J- i
& k; E8 n0 t- d' Z这是因为h i T D h i = ∑ j = 1 n h i j 2 d j = 1 v o l ( A i ) ∑ j ∈ A i d j = 1 v o l ( A i ) v o l ( A i ) = 1 h_{i}^{T}Dh_{i}=\sum\limits_{j=1}^{n}h_{ij}^{2}d_{j}=\frac{1}{vol(A_{i})}\sum\limits_{j\in A_{i}}d_{j}=\frac{1}{vol(A_{i})}vol(A_{i})=1h : `2 c& e3 X" k! B/ I+ ti) `& r* c0 K( \" x3 y* r4 G4 A& B
T $ g( ~& O, \. h2 n. C) v* m+ Z% O0 v9 O( ^ {1 u/ P( }
Dh , q* X+ E k F# H& Mi2 P5 I4 ^2 N. K3 E' W* y
0 e" { V3 y3 [0 _! b = 2 y: U/ W; M* v ~4 X
j=11 Y; ^' _7 l# w# u6 p# j
∑ " W) }; D0 |- Jn6 m7 ~8 j2 Y2 Z. Z! C( Z" _
' @4 t( ]: w$ Y1 Q" ^3 D h $ B) g+ L! C; S) [" Y2 q
ij1 z9 J0 l8 A) ^' \
2 ' }/ n# q# |" f* ^/ b6 \ + H, N4 m2 F; I: a d 0 l9 ?' [, ?+ m" `5 v
j 7 @1 W0 C, e! h/ p9 r - v( N3 i5 a- p) q7 s = $ W. F5 o; p# h! [; T/ x3 ^: Qvol(A ' U* k# j3 o) [3 k% U* E9 P
i, B) z [' x+ }8 \' z8 @6 z
9 M( q/ h S) z- H! W
)+ W/ K( p9 q: Q6 \/ k- Q
1 " N3 o, Q+ B5 P6 W9 \7 r" z 2 |+ e: n% {, q# I ! [0 A; D0 V p0 u) `j∈A / A. x) G! d" t# \, T9 s$ q6 Pi ; v$ X" }3 m; A2 a2 }: J# @/ i8 Z( \1 g3 K2 s
8 X. x d1 z! i
∑5 v( |+ L; D0 ^7 \0 G0 m# f8 d. n! s
6 _+ i9 X) z4 A9 t% R d / f. N( T, c- P0 Q/ Kj) Z! G9 M# H/ W$ q( H* [
, P, a$ J ^) `; e) `* P = 0 z; r8 \- b3 f1 zvol(A ) U6 g$ R( }+ y; @0 Oi) y9 l; x0 E( `# |7 x
( ^7 j) D2 h9 T- F' k7 P) A
)9 J5 O; C8 U {1 ?& s- F4 {( [' M$ I' ^5 C
1' [/ _1 v% |' D
0 F6 U: j5 I0 v1 p' H
vol(A 8 D& G: ?. L' `6 A$ v
i. f. o7 I- E5 S3 ?- T2 f" q3 m
& X7 m0 ~. T- t4 t0 V- d9 g )=1) f% h& K3 Z/ B" @, P
因此,此时切图优化目标为, k2 d7 ~0 @/ Z9 `5 \0 g+ a
" o, \7 k8 d( l6 Ua r g m i n ⏟ H t r ( H T L H ) s . t . H T D H = I \underbrace{argmin}_{H} tr(H^{T}LH) s.t.H^{T}DH=I + K; D: B) c- o9 U; i. J3 `5 ?H 7 O _1 D# H& i" g4 u" Qargmin 5 `! I4 ~! F& V2 }! E % J8 R$ ]4 }+ p: I6 l' q7 B; R& {" W) @+ q/ _4 \
7 K; c) Y" g7 e tr(H ( e( D" W8 s. X; z7 _. g) ^T0 R2 I$ U( A* P* y6 t
LH)s.t.H - { B6 M5 b. ]" q0 p+ T" B3 j
T ^1 Z. Y& P1 H( c/ z. ? } DH=I $ P* h2 m/ w# k# l! i: V$ k4 F$ C. c8 T2 B9 R; d, @
但是现在矩阵H HH中的指示向量h hh并不是标准正交基,所以需要对H HH做一定转换。令H = D − 1 2 F H=D^{-\frac{1}{2}}FH=D - @* N& u- @3 r
− $ g) I: m9 P# Y2 H4 M: I0 E2( d$ ?! U0 [9 q: a6 }: g- i6 A% D
1 * n% V A$ p* t8 x; s* r5 k7 p3 }. Y3 A
+ K" p" X* U1 y. q F,则H T L H = F T D − 1 2 L D − 1 2 F H^{T}LH=F^{T}D^{-\frac{1}{2}}LD^{-\frac{1}{2}}FH 8 F. e* g3 F; L" J0 k* H0 x' TT " p7 p1 z; A1 |8 I LH=F 4 n+ P! ^; ^! R5 bT% h- E5 O6 Y* i# U( H3 z
D , t; V3 K5 p$ g
− : m7 y3 R8 j9 e% F6 I" `! y+ _2 ( f/ c) K, r) Y. c1! t, Q$ \; P0 q! b6 G6 t+ x" j/ m
6 S$ v5 [" u3 g * c7 M. b- }# J! u" m& J* E- o LD 3 z2 v, d* \1 U: z* D8 [− % ]- S0 ~) W0 d. U
2 , p/ Z- r. P8 Z# |& D1 l3 c1 m1) g. @/ s/ M: c" P% M, Z; o. p! Z
+ q4 y) A4 K* E2 ~/ O" t3 ^
+ i2 a! a* H/ k$ x% M
F、H T D H = F T F = I H^{T}DH=F^{T}F=IH ; W& m/ o6 a- V- U
T I2 C, y9 K. x, \0 _) S DH=F # N* M, u; W, ?$ tT # |" T7 j7 ?, k# i6 J' o3 p F=I,于是优化目标变更为 & G1 t1 X z6 \* R/ m' t8 ra r g m i n ⏟ F t r ( F T D − 1 2 L D − 1 2 F ) s . t . F T F = I \underbrace{argmin}_{F} tr(F^{T}D^{-\frac{1}{2}}LD^{-\frac{1}{2}}F) s.t.F^{T}F=I$ m- o- n3 M- `
F % j' B) V- `- x( f! \, Zargmin ; [/ v% I4 y! _5 \/ J9 P/ Y& g( Z; U; m9 @4 ?
. e+ b1 Y8 W' g4 C; m# T
+ ?% b ^7 `( r, V! } tr(F 3 }3 q# j. s, FT 9 G% N2 ]1 ?9 o% e( g D - {2 C# W* O' N( Q" r! O* Q− - V1 F' Z9 t: l: P2 v: N! v, A& n0 R8 @& Q
1' [* G# p8 Q6 l: i2 T$ y
3 M2 P' y; g9 [" E/ z7 A6 G8 o& L3 ]( X: \
LD * d' E+ r& B$ L0 P
− 7 f. F7 m: E, g/ D( C5 ~) \22 q7 J s5 i1 [" {# n- g
1 2 ?1 z G5 j% z9 @! ?) d6 l3 C% A' k5 d; O$ e% X0 O: s
- ?' @2 z: ?& K6 `7 C
F)s.t.F 1 Q" K/ }; R7 y9 p a3 xT & i8 L5 l, c) S; g; O F=I + K$ z( L, S, ?# A1 f * C2 M. N7 |% s现在,和比例割一样,通过找到D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D # H. e% T+ P3 n4 p& M# f; I# {− + `" T( r' o0 ~; ?24 A* p3 ~" j$ V% H
16 |# g2 M" @* v+ J5 p0 W
3 p0 l N9 P; K + W5 g. u4 b4 D+ v' g9 e2 l LD 4 R/ D2 R5 M8 Q B6 z1 T
− 9 U- }7 I7 H2 X3 G* v: s! n, V2* x( {/ e" h+ `$ B& [; y: Y& F
1 % {( U* z- h+ [; @% u% A8 V4 c% G& p- ?, h- t- v2 E$ z+ U( X& ]9 O8 }" o+ f: {
) a" M2 z/ f+ i8 q' c (就是之前的L LL)的最小的k kk个特征值,可以得到对应的k kk个特征向量,这k kk特征向量组成一个n nn×k kk维矩阵,也即F FF,最后对F FF进行传统聚类 4 n/ l& m1 F; ^' E 1 {1 L# u; k( u9 ^: J e一般来说,D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D 7 Y) O6 Y5 u& N
− $ y( @! G5 |2 z5 H2 * u$ ] M6 t* q! C1 c3 {) V17 V& C P! J4 s& g
) H3 y; R/ ?, {$ B# W) j0 l
1 a% H- Q& z% t4 ~# T2 o a
LD * G) y5 U# [1 q( q7 e. V6 n7 H
− 2 n T/ a( q) y8 O$ B5 u( T% m
2 # O/ l* ~2 i) I1 2 Q# ~3 J0 A$ e( z : K6 V3 B/ E, \) p; d+ ?8 f' [) A3 p" J3 y1 s& i! d
相当于对L LL做了一次标准化,也即L i j d i ∗ d j \frac{L_{ij}}{\sqrt{d_{i}*d_{j}}} 9 F% K/ Q3 o( p4 _6 y: Yd S' e7 \, H3 B2 [/ F l ~
i' V& K% d3 x/ i/ X; w7 ^$ a9 c
& q' g) M+ y6 }9 k* J1 F
∗d 6 |- u" M3 G* |/ R4 e9 X' k! jj 2 a- d1 x& l* x! y- H . {( T: D) H( h, X7 ^% K8 ^, q( v% s& S- E
- r: e; V, g5 j 1 T& u" ]/ H7 j% a7 K* mL 2 s6 D( D: Q) x! ]5 Iij8 w% F% m5 }: V
" \8 e. I- n3 X/ A2 C% P1 {! h2 g