QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3010|回复: 0
打印 上一主题 下一主题

[其他资源] 【数据聚类】第八章第二节:谱聚类算法之切图聚类、算法流程及其实现

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2022-9-12 18:41 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    【数据聚类】第八章第二节:谱聚类算法之切图聚类、算法流程及其实现1 j" l6 z* z+ z; y& I1 X* }

    0 s: Y6 w; R$ {% q0 q) g4 u1 U本文部分内容源自刘建平博客,在此基础上进行总结拓展
    8 c5 X. U" Y; _+ I& b
    ' i+ B& @3 X4 x2 j% Y& b* ^原文链接9 P3 X$ U/ i6 _# S
    文章目录' D8 j0 D: G3 N' [+ P7 Y0 X/ _
    一:谱聚类与图划分
    * v/ w) r( J5 |# n1 o7 w5 Z(1)比例割$ }; e6 m0 N1 c- d, {( S; j
    (2)规范割(常用)
    . L* ?9 _, c* S8 d" S4 b二:谱聚类算法流程
    2 Z, I% M1 H. u% O/ [# f8 R' x三:Python实现
    & B7 s. x" p! D$ S8 N0 V+ R% ?四:谱聚类算法优缺点
    ) S9 ?& }9 b0 ]5 ]3 o. H(1)优点
    6 J' v* q0 N1 `$ P8 ?) B' S! d(2)缺点
    . P' I2 J8 x) H; Y  _一:谱聚类与图划分, F! ^/ W: z2 N" j+ x
    无向图切图:谱聚类算法根据数据点之间的相似度将数据点划分到不同簇中,因此将数据点映射到无向图之后,可以转化为图划分的问题。对于无向图G GG,切图的目标是将图G ( V , E ) G(V,E)G(V,E)切分成互相无连接k kk个子图,其中9 [$ G3 s3 E3 B# E: L

    2 O% r/ S6 X, W7 B: x* A3 {每个子图点的集合为{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
    ( `) F" ~( E4 [- d+ o1
    - b! J, k1 R8 j5 ~8 N' U8 G
    2 Q# H! q: M5 m" }4 t ,A % d7 c6 C. y8 L+ a" L4 X+ Z
    2( `: M" v6 P3 ?4 L

    $ @7 W% w2 v/ N ,...,A
    8 W# |# {* V! f1 I1 ~7 K" Jk
    ' E. w3 j* D( @& G0 m- N. Z
    % X1 Q1 U- P& A+ S },且满足A i ∩ A j = ∅ A_{i}\cap A_{j}=\emptyA
    ) [6 F1 ~0 A1 ?1 Y) v. l3 Ji! V1 B! t% p) u; C2 w" T

    9 r9 ]+ @8 `# H5 V ∩A   B, f' s6 A9 _  I# U% j+ s- R- X
    j
    7 W4 R; ~" G1 K  G* N9 v1 m) n& P$ F4 {# {
    =∅、A 1 ∪ A 2 ∪ . . . ∪ A k = V A_{1}\cup A_{2}\cup ... \cup A_{k}=VA
    5 q( i$ K3 T5 r9 S. |  N3 d1& w2 O. ?( n! o. {& e, j

    - V! H3 T9 x  G ∪A
    9 R. g, R1 o, X( B: D$ {2' O8 E4 S! X1 t' M) g

    7 P+ F: {2 u9 R! E' x! t& e8 m ∪...∪A / k$ S, z: o( w/ z  H
    k' f1 v! l* _6 U2 D& T. l. i7 ~

    , Q+ z4 [3 O; x+ h7 O/ n/ [0 J& U =V) V  W# U. |+ w- N- ?! U7 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)=   L/ |1 z- i7 V9 a" Y! H0 V
    i∈A,j∈B3 Y4 t1 C3 g: G; m; p' U( u
    2 q  o+ p; ?0 E6 D. k8 J

    4 h* V7 y( p5 Z5 P; l9 ` w
    / r( V$ i+ d$ n! z; Xij* H& n& W8 H! {; D' Z2 f" H
    ( W$ n4 V, K* y# W  n/ k
    : Q+ i  l5 j- u5 D* L
    对于k kk个子图点的集合{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
    / g& M( m4 p+ k. [1# |/ a8 A  r5 O4 c4 u0 j
    3 T; v4 D# q- b8 ?
    ,A
    / y* I' {$ j7 o; M% Y4 I- P& W7 P8 C& q2
    * s2 C0 e" b" `4 u" W6 `! Z$ E
    : I2 ~" L' m1 v* P" r# n$ [+ G) u2 j9 v& M ,...,A
    4 H2 |, W: V( o( |) j. bk
    ) R4 j/ U! w( G& `/ z3 M4 P/ i# Z+ K( F0 n
    },定义切图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
    : Z. b7 a. H9 S7 i1 X1- l4 q9 C3 y* _2 p% w

    ! d% K9 ~& F' W$ d, L* R. \9 z ,A ) u! F9 K: ]/ R: \  p! n
    28 W( q  p& L( @/ W

    7 t% r; c0 v" h0 Q" L3 h, U! h. [! k ,...,A 9 l. p" H8 @# x, x, s
    k
    . ^$ S! E5 J. o3 x. l
    7 f: G# N$ ?; w( s! Y- d )=
    : ^# t/ f" o0 u2
    % G0 t& L7 [6 T1 B8 B7 a3 A1
    ! E7 G1 W6 D4 O8 l
    4 _/ ^1 M8 |: n  b6 Y0 c; }) r! b% I) I& [9 H+ ~# E
    i=1
    ( u4 [7 g. k' p- z7 @0 o
    ! Q7 J# b8 k; [% `0 d8 T" Yk5 j4 A4 }( C' J0 Q
    5 g; ?( I/ ?% \
    W(A
    : C# \% [$ {- a8 Mi
    ! U) Y; H0 S7 ]
    7 y5 {3 v6 a# t" I5 y ,
    ' A! ^: [' a! ^# XA( c9 z/ @4 s; k2 a' `! R- T6 a6 v
    ˉ
    0 @7 c! M. }! j; b0 m! N- D9 _4 d4 S7 q, J7 w+ U& M5 z
    i
    2 k; s9 b* Z; Y* x( v. ^
    : {8 S# f; a3 k- S ) (其中A ˉ i \bar A_{i} : V1 x  C/ T+ |3 K
    A) q3 i" m2 q5 p2 n
    ˉ. P6 b) i! V. s

    - m0 S1 q+ B. c$ ji
    0 m1 C* J( s5 s
    ! T4 y( s3 O, w 为A i A_{i}A : k7 s3 x( m, W' ^: B: ?! c
    i
    : `6 v9 Q3 B5 w! }6 i* r) a+ C; s( `7 }. T3 o6 O
    的补集), L- Y9 B' a) _4 c# U9 N% s" n- q
    可以看出,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
    ) N3 T% a+ ?3 p& h& u6 X$ |0 R1
    ' G& k& S) t! O. f8 f
    , H) O% O; i' n0 G! z) k ,A
    ( i) x6 N/ ?, m2
    ! n5 d+ f* W6 }# B- w; C' }) ~7 N2 L* ?8 I% g& k
    ,...,A 8 a9 N1 A$ m6 w& h
    k
    / D9 f) B$ ^/ D7 p, U) I7 E# n; K" |
    )=
    8 m/ o3 K0 m3 M  S5 A: x20 F9 S- ~/ R- r1 e; N
    1' h% L4 Z6 D# p+ o, k
    # F5 ?: G+ W* B- d% H
    ( ~+ B6 ?: R. r) P# D
    i=19 Y; s5 H9 P3 F! A) Y" j) E" Q

    , M7 O/ i' X- Nk
    ( n/ u- e3 [& r2 ^- J" u: ]" L$ E! F/ D: v$ E
    W(A
    : i3 E; A" E7 Y, w! qi4 K& P7 z. h8 c$ q" F/ C5 I# I9 y
    ' L( ]+ M3 Q- L. J# Z0 g
    , 6 ?2 a" O  D, k2 `' J
    A
    3 [& v# m3 W) Zˉ0 z- o" ?! Y  P) u

    ; {1 q0 l. T/ m% T7 k) t4 ^4 Y/ k- u6 Ki
    4 C1 `+ b! O9 r  U5 S1 Y9 V- M
    " T( }" X1 U( M8 s4 w  n' f )在划分子图时并没有考虑每个子图中节点的个数。所以在某些情况下,最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A
    9 t6 w; F% g  p$ g3 i# Y! z1
    " G4 w4 o, t1 z  |
    + ]) X9 E4 Y# q( Q& C2 v ,A
    $ }/ l8 N' X' U8 O4 F; G2
    & }7 ]8 h' Z* ~$ D" n8 }( w5 H9 K8 I* J2 `. W
    ,...,A * G9 f+ E& L7 O$ |" D
    k
    " ?" K) s+ X: E% H' E5 ?9 ?- _4 t2 h6 D0 ?9 Q: f
    )可能会把一个数据点或是很少数据点看做一个子图,导致子图划分结果不平衡
    + {0 |/ ?" f4 p' |2 C0 M& K( z+ O( M3 x& p1 y2 G
    例如下图,选择一个权重最小的边缘的点,比如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
    : B# o- ^* J  Z4 t1
    4 Q# c! j' _% ^9 W  v# ~5 L, b* P* x9 b2 M' f& K6 U
    ,A
    1 h' M8 e6 k, X2 b% @; n26 R4 M. |+ m" S! \3 B
    3 g8 z9 x9 o7 f3 e2 V( b3 _
    ,...,A ( J! B4 u9 D# i8 b- D9 `
    k( }) V" f" G# g8 L
    & K6 C1 y# [) n
    )但是却不是最优的切图# o% ]* ]1 U; h) d& U  V3 K
    1 j# X4 ?3 D! u7 A( E
    为了解决这个问题,会引入一些正则化方法。最常用的两种方法为比例割和规范割
    : |7 Z/ ?- G& c# ~5 C2 Z* M% \9 Z3 L; Y( |0 V% i
    比例割: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
    7 f+ a+ F" E" ^. H% R+ z" n- ]0 U1# i! y$ z) ?0 B0 @5 v

    ( I. T8 `& n' e: W7 U ,A
    4 Y' p. s3 h3 P* x) c2
    1 u+ R! @3 ?- ~0 R6 T4 d
    ' _: j3 p3 `0 E/ F/ e8 `5 @ ,...,A
    & B8 q* ~3 g6 G5 K7 n* {1 Dk
    & \% j$ R5 d- Y" M+ `
    ! P! R# p3 d* \9 [) ? )= 5 W& I) e# ~0 S; a% z7 [% b6 |
    2- [% H% a# ?; ^# u6 }
    1
    # j) i$ S8 k+ |, i0 A3 a7 a+ a
    * }1 C, R  F- u' B+ n& V6 w
    " u4 v* L( Z9 f; Z6 ti=15 _8 v$ X4 H8 t8 E

    ) e  {) D, O9 x6 [# c3 a, @) B4 fk
    # \5 W: T# f4 Q5 M# v% a; O
    . E) `% B( V0 q; J3 ~# ^4 l' X) J7 B( f
    ( W4 a2 t. K5 J  n* p3 w3 U  b- {: d) A∣A
    ' _" O' Y7 h- s. c$ d! ~i$ r' U, q* r: y* d+ A# N  f
    4 u3 n) Y  X8 S# t$ C1 d8 N

    5 n/ F- v7 W( U$ h! YW(A ) S! I* @" |7 J  V5 N$ C
    i
    5 h8 Z# a1 V' }5 O2 M6 t7 G
    1 b* P2 D- U  L+ g" @9 m , 4 c4 j  b% u# d" a- i: @: [
    A
    : `' _' |. A- p& Z& x+ d, T1 Iˉ0 H. F4 l) d5 S; o" s* F
    0 v( u+ |. i8 i
    i; Q& `: \  a  B9 z0 m+ |" O- H
    0 _/ B$ p; M& [; w& D
    )" f* y# C' Y5 I. @% i
    ! r& `1 K. V$ I

    ! |2 t& y5 ?3 w6 u3 X+ E规范割: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
    0 P5 a# K+ h1 b$ _" Y16 ?  t. W- x% h) c* F* |7 K  ^

    3 k7 d5 w0 P5 q" A0 k0 t. ]; s ,A " Y4 D! t; }( S: e- e" k; e4 E7 `
    28 C9 t! t2 ]" l# A7 j
    ) r: k5 U6 O' D( p) M6 T
    ,...,A
    ) V# r8 ]# d0 ~1 sk4 I9 u8 r- L$ y, F
    + G9 \1 L1 r2 k
    )=
    + G1 F' P. w2 l. K2
    6 }: i" s3 X7 y" J! a13 N4 g$ [! C; w( T% S: R3 N9 ^) p) Y
      n  g; g8 }: a0 v& f
    9 i( g3 m9 s/ l) V& ?4 O/ \
    i=1
    - M( v7 `- w% Y3 y: B. t3 j5 c* D/ Q* K( I9 i
    k
    0 v$ z4 q. ], q% _6 u2 K2 A% i! g# R* M$ H9 y8 v0 G
    8 Q$ Q5 W6 n; H) s1 u- _
    vol(A $ l# K4 I, r; O4 G
    i6 t9 }) z# J8 l  q
    1 u5 t  P, ?' h2 b5 d1 j' p: d
    ): E6 T6 B5 p; @& G3 V+ R
    W(A
    : ~5 C0 Z) {7 y& C* N. e- I8 Ei2 q6 `- X: w5 J/ A8 H
    6 D$ B( u. L, _. w- D! f4 u; @
    ,
    ' ]; B1 Y) K7 T  iA' Z. G# e1 B9 L# S3 X" m' p
    ˉ( a9 V4 M3 w1 b' A( Z7 l

      z* y. x* U# j4 C! zi* t# ~  N2 I2 q$ F5 e

      l7 O! N* ~! |8 I; F6 B )
    0 j! O! C8 N+ I1 Z# x. l0 a8 @. ]: s- h8 ?: i* F

    8 w. i: g1 p( y(1)比例割
    # ?/ ]/ z# f2 W, r* E0 L- s引入指示向量(点击可查看指示向量定义)h j ∈ { h 1 , h 2 , . . . , h k } h_{j}\in\{h_{1},h_{2},...,h_{k}\}h % g6 b& f. C; f
    j
    2 I2 h. x* o' f, |9 ]2 Y, k/ E3 Z, m- F+ ]4 {+ M
    ∈{h
    ! x6 ]: D: p. ]' p4 O7 \1' a* S* U* L3 p
    5 T# E) {8 I! _9 C) l) C3 h
    ,h # N7 U1 D4 C- M9 |' e1 T) m- M
    2
    ( S. x* ~3 I: f0 B/ `$ S7 R1 ?
    4 X- z1 o& L" A' k: K5 S5 ~ ,...,h
    / W  ]. w# ^5 ?! ik+ y) L" y- v, p9 \5 |' p

    ( w. S/ M% N% |" e },j = 1 , 2 , . . . , k j=1,2,...,kj=1,2,...,k。对于任意一个向量h j h_{j}h 4 Q  _. i$ g2 _- k# x
    j
    9 p% F/ e% T, W( }5 C" I5 h& s7 s! ]( E0 E4 c
    ,它是一个n nn维向量(n nn表示样本数),定义h i j h_{ij}h
    " |: I( A& c8 t2 D6 ~& f! y4 Kij! P! q+ g" S  _
    " c' g9 _9 K3 G1 L7 U
    如下7 Z' V0 t: m( T
    7 b7 |6 l- U3 k4 r! H  J( h
    h i j = { 0 , v i ∉ A j ∣ A j ∣ , v i ∈ A j h_{ij}=7 s) |( ^3 v" D$ W  Z0 J
    {0,vi∉Aj|Aj|−−−√,vi∈Aj7 A8 a+ k# @3 K) v  L8 I3 v) s
    {0,vi∉Aj|Aj|,vi∈Aj8 O* N" f. ~" _! x8 [# R
    h ) Z3 u( W  p$ N% ]
    ij
    * ^4 Y/ I) K9 x$ v2 x( f% _! [7 z7 o7 b9 Y% q+ J1 ~: o" A8 e
    ={ 1 K8 `2 r% {! ~" l8 f7 P
    0,v ( w+ E  I6 H8 G, ]' e) U0 A: R4 f4 Q) ~
    i* y* c2 o. _/ S* r3 e
    0 l( Z- Y2 {' u& }1 O+ M; [

    ! j$ h0 K/ B* [+ H$ D# E6 z/
    , C7 O1 Z- v. o" A/ n3 H' R7 i5 K! zA
    4 a3 d# {  B# Q' M. Zj6 S( T' T& ^# D, U
    0 y8 L9 \) R/ `( N1 ^* K

    1 k* s& s) z# n  Z- h∣A - O9 @- E  V0 D$ R0 o0 ?; e, S+ \
    j
    9 Z0 b; v$ E! Q
    7 G8 k5 D+ k9 k$ q
    & R( ~9 v+ o. L6 @; k8 ?( O* ~4 `# L
    ) D* g" ]) S- `# p+ O- M ,v
    ! e% ~) X* i1 [! X# q5 D3 yi
    , ?) m5 o& [# i% V5 |2 Z+ R" D4 }7 _# z* t' b0 C! j7 v
    ∈A
    ' u, u8 x, E4 Gj
    . y  x3 i: n# p% P" D% J: \* A# ~" z. r4 o" `& r$ W
    6 Z: \7 x! L. J7 [$ T. `) W

    % z7 B! i! Y% u8 `, w1 q( _& j  V; o" D0 H
    3 ^+ B8 W  C: ?. P2 b: Y
    于是,对于h i T L h i h_{i}^{T}Lh_{i}h % C2 {% X) @7 W% k
    i
    * s6 ~3 J( y4 O% sT
    6 x9 \+ e! k; P+ x+ f7 w) }
    ( v, a/ m1 B2 \2 i5 Q9 J! T0 B0 I7 @+ y Lh + d9 o; }6 }4 _* A
    i
    5 r, a/ s  N# T- c% x8 z) q2 r8 o- S/ S# ]9 ?
    ,根据拉普拉斯矩阵性质可知
    . m& w8 I& M- R+ e, r0 H+ z8 ]8 H
    对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
    5 N% t* T0 U9 D+ h/ ?" t& n1
    ( Q" f' b: n. N. O3 E) P: k. `4 u- o9 l4 G- [+ U7 q+ H) a8 z
    ,...,f   O* Y' s, K- M+ B2 u
    n- x1 D9 X5 I6 f7 ?  U: c  }. B

    5 C1 ~8 y& F  K )   @) C3 m- }$ T9 b: y8 ~
    T, Z9 `, ~/ T0 w
    ∈R ; ?% n2 \4 [6 R3 C' x
    n/ G5 H0 j9 ?% x4 g% a* c. v
    ,有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 / V0 b3 V8 e$ Y! M: o, ^
    T. k7 P' L: X. Z2 }3 a* ~2 k
    Lf= - \! A. B2 p& z2 @
    2% Q$ Y$ k- f& O) P: N  C7 `! G& d. q
    1
    : u, ]* s/ i" J- @( E
    % L, w. M# _# ^- G" |
    ; ?. f) w4 f# k% W9 ~i,j=1
    / i# A% W' U, ?0 T# {3 e7 h! `
    7 L, I+ t; X, ]5 n$ t2 I# {n
      r) h! N. _6 q7 b; {2 [& x, K. t$ j! b5 n3 J; k
    w
    5 O4 }. [1 i1 m9 G. u# I7 Eij" ?4 C7 N9 \( q' O9 B: p& z8 A; ?/ ]9 B
    ) W  x- w: i6 t% p1 d
    (f 1 s* B' n/ @* W4 K
    i3 v; r* C3 X6 E1 P
    / U+ J- ]  x  h
    −f
    7 m/ Y, x$ M' ?: F8 }# P  Rj
    ' {% n! H- G. ~# }: |# q; ~* a$ V5 \
    ) 1 d% \- W" ?, d! v
    2
    % i( n* g% Q7 I# b) F7 m' ^6 S- G- C0 L
    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}|}
    2 m$ x# s# a! |6 l" |& Ch
    0 n# B$ r$ J; o  {i
    8 Y* a/ {+ P5 \T1 o+ M7 m$ T8 ^6 f

    4 V5 M% V! h4 l- t9 S Lh ! s/ S4 D8 p7 V
    i2 L9 `+ g4 p( a4 M' I
    4 C& c0 m$ ~1 N, l; z
    = & p* j1 L# \( h5 X: e& L
    2
    8 j& y3 @0 Z8 b. O+ U1
    ' E8 C4 x5 D6 B+ Z: R+ D3 K8 H3 m8 q6 s, ^

    6 l4 d6 e- w7 Jm=1( u) m) r5 J' N

    0 K3 m2 t. K( a& \* @: O2 H0 P2 a6 q. |
    * U+ Z( l! Y; v# U( {, C- q
    n=1
    * ]6 j- P/ s: i. E4 F7 D5 Z+ f' Q1 W" f1 q" R1 G+ P; L! ~2 u1 M

    3 t! S# S$ s# I; e2 R w
    * {' T+ f2 u, [1 [7 ]/ }, d" B  R) P6 \, Tmn) M' e# x6 J: s' w1 u, j) K" h% R
    . c3 _5 D4 l! R: @  i% N3 I% g
    (h + X; v8 W, f  n8 t: O- g
    im
    1 V1 |& s! b! w3 F" ^+ ]* p1 @$ T/ N# O/ ?: z5 o0 X+ h1 d3 R
    −h
    ! [8 D, X/ v2 Nin
    / r1 v# P* u; r( n( V% C0 z" H) F1 n
    )   O. G7 a& F, q+ d1 Z
    2
    3 t1 m' T! T& t7 x) N. c& t7 ` =
    7 D. m1 C( H* H∣A , @& y5 [3 c! a( Z1 h. y' O
    i
    5 [2 \0 D/ Q9 a; ?8 r: Q" ^& l
    $ g: u! A  Z3 c  ]  R% L0 l( V# a6 d8 t. w+ s4 B3 x# A
    cut(A 8 w$ N# ^) L/ n: z( c  ]
    i' n0 g. _+ t3 V# I# T  s( V6 t
    / i! [" Y5 J6 J: t4 t
    , ' ?. L9 {7 k$ Z# f: N2 u4 ?
    A% A) p# {+ c2 a( Q" {
    ˉ
    + ~' T& S+ d3 g8 m; I% |* f5 g9 D- w1 v/ ~+ j9 o
    i
    2 I+ W4 U# @; R0 B6 A% @8 D- L6 c" t# t) m  n: ~# A
    )7 Y2 r1 y, T; C' Y4 l$ Q* I9 W
    & a' @) M9 f# i7 H" G
    9 H* _  P0 A7 r9 ]8 V: i, g4 ~

    7 U# Q7 s! b% a" v3 h2 N! Y6 ^严格证明过程请看刘建平博客:链接
    + L7 P3 O: J8 G1 b$ w0 G; x+ C( r可以看到,对于某一个子图i ii,R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h / U8 m" U1 }) C; ?1 {. C2 `& N: w, F
    i
    % f. Z( U& t: R- Y( x# Q& N- z: JT* I+ r# M8 C  \3 M

    / G2 a( t0 w# `; ~# n Lh 2 V: {  z# p+ C+ @8 h
    i
    ; ^8 v2 S& ?5 T; |- d% c7 \$ b  r$ o4 d
    ,那么对于k kk个子图
      h7 N! W* T' @/ K% M+ b' N+ G2 N& g# t& s2 ?
    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)) m" O6 V0 q5 [9 P
    RatioCut(A
    0 G' B' ~# _' Y8 {( @9 ]1
    # A4 T9 W) E8 I( ?+ o  o/ n/ y9 c/ H2 N* y( U7 w6 ?, U4 K6 }1 ^. z
    ,A
    " G5 \6 P3 W# s% w0 d2* S$ M. w% u9 o2 u  S8 |
    " H! g8 p/ U* W1 Z) t# I
    ,...,A
      K& z9 d' q' ~& q; Qk
    / L) H$ h+ r$ g* `- w% {6 F/ U0 n  A
    0 H/ t3 G% R1 K3 D5 o; F )=
    2 Z5 |/ ?4 d3 I7 b! d: F7 hi=1
    9 n, H- K& `+ @  U2 a2 Q4 Z) L0 k+ E8 Y1 j4 W1 g$ O
    k
    8 P" \( ^4 B1 a4 t) w6 S1 }9 Q2 Z6 n
    h # ]" l, t9 q, C6 `4 |
    i+ ]% C/ m; @3 n
    T0 Q/ L! \9 U( o+ E9 G- J$ W% K1 g
    $ B# a3 R2 p! E& A
    Lh ) u; N, C9 ^* z: E: T& [6 G
    i$ c! ?) \+ O$ P2 z0 c
    0 r  `4 v  p" Q, I* m" d/ W
    = * |/ R6 Y. a( P+ F
    i=1- K6 B/ l+ t* ]% X

    . R4 K. J* y4 Zk
    6 K7 m; q4 N% i5 U0 q6 E  x" X5 N
    3 c8 G/ ?% g8 ^) a. t7 a" J (H
    & x6 \) O, i6 z7 P  KT
    + ?+ C7 F1 H5 g7 m1 @ LH)
    ! n5 p2 J, J$ {ii( g7 I, X  X5 p
    9 H& ]- p% {! t+ Y* ]6 U  \
    =tr(H   i1 ~, _; I$ u* X
    T
    1 r  g, f( L2 d% i/ q$ H! F% M LH): P$ M, q2 U' t$ E8 _7 [

    1 A4 {' x1 h1 C( w因此,R a t i o n C u t RationCutRationCut切图本质就是最小化t r ( H T L H ) tr(H^{T}LH)tr(H 6 v- l! [! W* [: E' t* {9 g: R
    T9 @( U6 _  F) ]. g7 R
    LH)。又因为H T H = I H^{T}H=IH
    0 {4 U# g# r; H' D- [2 m1 NT" o; S5 v1 [( _0 D1 [- U& m
    H=I(单位矩阵),则切图优化目标为
    - _; |9 A- m2 f$ t6 D3 K" w% r5 u  l7 I4 X
    a 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
    ( o9 l+ B0 l/ p6 @2 HH
    + w: S) ?" V, margmin
    4 Y3 g$ X+ Y" J+ t7 K$ t, o' \# \: ~
    - m# K  T6 F* Z, P( f' a1 a8 N( g3 W1 H; ]2 l- [
    1 N; g; e  x7 v* ~
    tr(H
    0 B8 G  \3 D# D* f9 V* }3 b8 eT
    * A% I, Y5 i1 x# m( E LH)s.t.H 9 l' z! k8 x) `( u) [
    T
    0 w+ e' ^8 u, q. s# u H=I
    $ h" ^7 n6 w0 w! ^1 e* {' M
    % P- w! m$ m& [* q: n& e对于优化目标t r ( H t L H ) tr(H^{t}LH)tr(H
    9 A# b2 Z% H8 ~, l% J. U2 ut- Q- S5 U! U: U0 y7 O+ z/ p# G
    LH)中的每一个优化子目标h i T L h i h_{i}^{T}Lh_{i}h
      z; g+ \, Q. l: q/ R% l% k/ Wi
    3 U+ l" N# T8 L, @T, n& x3 ~1 C6 Y' ?
    5 }* E9 ?* Z9 O
    Lh 1 U+ W$ g, G  e6 ]
    i! f, s$ O8 t  q! J5 T0 f

    - y# t/ y- i! h0 ?% ~- t ,其中的h hh是单位正交基,L LL为对称矩阵,所以此时h i T L h i h_{i}^{T}Lh_{i}h ( j; t% f3 t! @! J: m
    i, K9 f9 c- m0 x8 I& [! `: O
    T
    + O* w4 j  u2 F: ?9 y
    - O" _) U: d1 C$ t& v Lh " x! H/ F% Q9 s% k* t
    i
    2 w) r) `: ]8 `5 j4 M! v/ ^; d4 M% t: S* |# b! A
    的最大值即为L LL的最大特征值、最小值即为L LL的最小特征值。而在谱聚类中,我们的目标就是要找到目标的最小特征值,得到对应特征值向量,此时切图效果最佳。所以对于h i T L h i h_{i}^{T}Lh_{i}h & p& j# {2 ?# _% I. M1 b$ v2 Y2 K
    i
    9 G% |- H, s  D) y+ LT
    % }# m% u9 M+ P! K4 e( b+ h! Y2 t7 B' f! n" ~
    Lh
    ; {5 I8 `$ A4 H& Ei1 H3 s; |' W- a! ^# N: u
    8 Y! G$ D( \0 K2 Y
    ,目标就是找到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
    6 |! I% _6 _, m3 w( Ut7 d2 d, q& Q2 X" d: A; ]6 _% s
    LH)= ( J3 j) Q3 v0 b+ B6 ]) n2 `
    i=1* o& {) a2 v+ l/ V" E

    ' ^9 e3 |3 M& j% wk: s' j) v4 u3 `( }7 q# Y  |. J
    # P' e! B* N0 @! d  I- v7 T
    h 4 I8 r# _! \0 }
    i5 J1 S$ Z5 b, [& i
    T
    , |7 x" q1 x$ D/ T! H0 d/ E5 ?9 r9 q6 }5 S! c! N( ]
    Lh
    ! D, w" h- r/ N( _i1 Z3 f9 t; Y( g2 @# c( r
    , S; N9 z' B2 M+ B" Y
    ,则目标就是要找到k kk个最小的特征值% U/ W% ]7 K8 ?
    ; g* H- ^5 T1 t7 `! s+ q0 C
    因此,通过找到L LL的最小的k kk个特征值,可以得到对应的k kk个特征向量,这k kk特特征向量组成一个n nn×k kk维矩阵,也即H HH。一般需要对矩阵H HH按行做标准化,如下. T5 ?# e+ q/ D; ~& `

    " s4 f2 Q! i" j- E! {4 t一般来说,k kk远小于n nn,也就说进行了降维
    5 r! O7 h1 p" Q5 R- l4 Q$ 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}}}
    1 E( E+ \0 o! u$ G9 Ph ( q4 X+ u5 N9 [
    ij
    . h7 }  |' i4 R1 }. x
    4 }: h7 d, P6 x5 e  h0 H
    ( ?( I6 d8 t. @' I = $ t' h& U6 e: t, R: O
    (
    : _* D' _, E. j1 _t=1
    . ]% |2 e9 E/ z5 Q" F' i# t) E8 I
    $ R$ U" M- A6 n5 _9 Mk
    8 V8 B7 U9 ~/ h6 w
    7 K( ~- b: M; f* Y0 [0 j h
    5 w' p5 W# h0 g% {, bit$ ]! o+ {  P& k, S; W, v  ?$ L
    2* i2 i3 p/ d; T/ f/ V2 a" _
    * R# o! t3 U  k. W
    ) 9 z0 R2 V1 h  _( C, I
    2
    8 U8 J1 Q; `  R. r" _- D  e7 y& j15 D; I* ?% b  M. ?

    , z: O9 P- E1 _' |" l9 r
    ; B1 d, O# I( R( a/ K& Z
    / U  z5 P% H* f$ M8 \5 W  p2 `# ^) Yh
    2 g5 s0 [8 S, v4 Zij
    0 h0 t- ^) l/ V8 I3 `# Y
    0 N) o: W3 ~# }! E
    9 B' `" Q' V3 Z# b
    , m) q8 }* K6 N! `
    & ?- z" P( Y9 E% z4 A+ s) z$ g3 C* [$ ?, C1 s% _
    这里需要注意,降维后导致得到的指示向量h hh对应的H HH现在并不能完全指示各样本的归属,因此一般在得到n × k n×kn×k维的矩阵H HH后还需要对每一行进行一次传统的聚类,比如使用K-Means聚类
    9 ~% @/ y, s/ v+ \7 J7 W" a8 a: |1 s8 J8 o$ O1 Z
    (2)规范割(常用)
    " _! o/ _/ D; R% J规范割和比例割类似,只是把比例割的分母∣ A i ∣ |A_{i}|∣A
    $ c) z2 V+ R+ ^i! V5 |; B( w* Y4 F: X5 B

    ; Q) w8 B- A! N ∣换成了v o l ( A i ) vol(A_{i})vol(A
      `$ }) h' I- U" o* Ni
    : H# `: J( I' z9 h7 w* H- B7 r8 ^, n+ D9 F+ v
    ),定义指示向量h i j h_{ij}h
    * L+ ]  ^- @7 l9 tij
    . E4 d) A& `, x% g, C" c/ E8 e2 m' x  w% g
    如下
    1 |0 o3 b' [5 r$ C/ \) G7 ~9 `
    : w1 L3 K8 m3 \7 Yh i j = { 0 , v i ∉ A j v o l ( A i ) , v i ∈ A j h_{ij}=; P% {8 c6 |6 ~7 @
    {0,vi∉Ajvol(Ai)−−−−−−√,vi∈Aj+ J" \; }& m, k' h% W/ ]! v
    {0,vi∉Ajvol(Ai),vi∈Aj
    5 l3 i* e# w; F/ Z2 W% `h ( n' I! ]/ v5 f3 m$ s
    ij
    3 V! y0 _; ^6 d  e: @
    + Y( J0 p; H6 S% y ={ * K0 K$ ?7 e0 d/ T# [- s% [# M0 f9 q/ W/ l
    0,v
    9 Y9 i4 J" e/ m: g. }$ yi
    " X4 ], Y$ B9 [# y' ?9 d7 k* ]5 J& B$ A

    9 z" y- I2 b' L+ A. }/
    * e4 H& I$ `  VA
    2 H0 `5 l! f( Z6 G7 r5 |. z$ Mj4 F7 q/ {2 k! }: n9 V! g$ r
    - x/ C9 y0 f3 v8 r( q

    & ]! v) M' A. v+ Rvol(A
    % ?. q: y  g1 r1 O- wi
    % p. q5 b! x: `  y4 n' P
    , n  L/ W2 A$ _: r# y: x6 S )  M# {* w5 n' _3 g

    % Y9 Q7 O  B  f. e4 z" P ,v
    4 V9 ?$ O; _% {, Z9 S! Yi' ~* b7 D/ O" u3 f6 v1 f) k

    9 m4 E) N/ A5 J) y/ @$ O4 [ ∈A
    2 {" i2 Y2 _, b* o% L/ T* Yj& K, C' B8 p+ x6 n
    & W, A7 W( U5 |) g7 P
    4 p; z$ k& ^/ ?
    ; m" ^, U4 Q- Y
    " N$ B! J  s+ B! w

    . g" r; c/ P. P# R) p2 U于是,对于h i T L h i h_{i}^{T}Lh_{i}h
    1 A6 \) T& [  |9 Fi
    ) l/ w9 ~) Y, r" c/ w( ?- R( uT7 k& U( r8 r8 q- ~3 n& S# W

    5 v7 r2 `' p: l2 \" d' Y/ S Lh # X/ D+ h) Y0 R0 V6 |" H
    i
    2 _5 G1 c# t% ~" W/ w# v5 m$ M
    ; l# k8 x: A+ T2 S, k- }1 K ,根据拉普拉斯矩阵性质可知7 l2 [4 I' S! L7 l/ |: L
    ; A' H( w( w# Q& Y
    对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f ' G) g/ u7 |2 [
    14 D/ [' U3 W9 J& m
    % o  v. [- k# k3 C
    ,...,f ) C$ ?4 I* V) y: r# ?/ e* j
    n
    ) I' K/ R, s% @) K5 |& N* z5 M2 y( D5 `+ {/ P) a
    )
    ! C' C* g1 J+ BT" ?* K& i; S8 L( F6 o- O
    ∈R
    5 G* t/ o& E1 m# Wn
    4 b  Q8 c' E. P! `# D ,有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
      b, h0 R: x# k" Z' U- oT8 s  q, v9 y- d8 ?; f) C
    Lf=
    9 _6 v3 E( I; [' M2" f7 F- x7 N( a1 B* |1 i/ q
    1
    ) i: z% |* v1 ^$ `+ G8 L" F( r3 H
    3 q  @+ |. E$ U+ u+ y2 S$ R; g4 [' r5 F0 Y; A. T: a
    i,j=17 j: ]5 W/ c% }$ N- N
    4 a/ Y6 Q0 A5 O, C
    n- t( c0 R/ R; |9 H: r; F3 |

    6 t# B0 q' H7 H# c. A8 y" N, {$ V w & z% I$ D% z& r: Y' [
    ij. S. {% a' b2 G. b

      `/ b# s* c8 Y7 K (f % I* V# z7 g; z( Y9 n9 Q0 w
    i
    * G8 L) j# O- v( O/ Q. w' b8 z, _7 ]: Y- i" n
    −f
    ! v9 q0 j( O& A3 Lj& a2 I4 K; K$ j+ Z# Z6 _) Y- a
    2 [% |, |9 J; w8 _; ^4 L
    )
    & d1 K0 ?0 m9 n5 D& w: u( |' s2
    ' e  j, A/ [5 z! U0 }: |% \: L/ R. A% M( U/ o' f' ~
    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 ) 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})}
    , B/ `0 m" ]: W; _: V* dh 2 j0 P+ e; c1 _, ?9 v
    i( @) j$ L# }1 T% _( [5 G) ?
    T5 l  m+ H* X! Y

      Y) e/ g8 N( E" G Lh # j( X9 J0 e- m; `8 S
    i
    9 w, l% b1 ]" Z3 y- A2 ?' e+ }$ _0 W' ^6 m  A! y( m, ]+ v' L+ b
    = - {3 E/ Y% R1 p9 q/ O* \
    2
    " q# W. a. m" u( d0 V, e+ Y5 f4 {8 M9 }16 X6 |3 z. j7 o
    . C' ]; o+ D5 H/ a& u3 D
    # p+ E. W  ~+ N7 N8 |  L
    m=1
    " B- Y- ]" r' P# o9 D; c% j( e* n! j
    / M' A2 m- a. B' r/ H

    2 T' W1 q- W6 wn=12 i6 Y  m9 C( F- E, ^3 B

    6 g0 ]4 o5 _; {0 e
    3 k" ~) r- L5 ?5 g: i w
    - h& |0 s5 A$ }; tmn8 F2 {1 V( o- ^

    5 N2 S1 `  c# r; @ (h " q) O  C7 C3 Q
    im! A0 C& ]+ C  ?# q) ]# L" U5 G+ j' H
    7 [* q! ]( I8 c7 Z9 s6 E# X% W  ?
    −h % z- v/ ]/ }0 d3 l8 }
    in
    ; \  v! X. n" d7 k  @3 @
    + c$ ^- C5 p; W  r6 ` ) $ |' h5 E1 q5 Q$ d' R
    2
      K) |% a+ E% r = 4 j: ~1 ^1 f. V) Q, |
    vol(A
    + L3 L9 X+ P6 i' T% O0 \: si
    ' E+ M4 x" h; D5 b3 i" @3 E+ K0 Y& K: D; G" p7 I
    ): ?# F+ {3 B% Q, H6 _8 r2 L# L! O, d
    cut(A
    ' p1 i2 \5 q" ?) {i
    ) n% R) n; E. n1 E9 v
    , T5 T# Y% e7 G1 x ,
    ( q+ M; o, w' d; Q( YA
    3 r# [2 O" p7 Y( z( Q& l9 t; p  dˉ8 v% U! I. f3 g. S; F, {) d! L& ^
    $ Q5 ~: z* V6 ^
    i
    4 [3 V& U. x, S2 p0 v7 ]' W, \% K! |- C
    )
    0 ^, K0 V' Z& F1 \! D* ]+ g" \; y

    ) ^& X  R5 E" S0 {
    % H0 W" N9 r% X8 _* G: w& y; m严格证明过程请看刘建平博客:链接- r6 _+ [8 v/ n
    可以看到,对于某一个子图i ii,R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h 4 S2 W( c8 x0 Z+ e. B" ]( I
    i5 y1 w3 M- Q, A: {3 M8 w
    T
    ( `8 J7 i. M1 B: T
    . D) s1 B# M. r$ i Lh , j$ @# B" C8 D1 s! a; n: ^
    i7 Z$ E5 o0 V' ^/ `; T5 h
    / v5 G0 v0 A* N3 b2 M' Q5 v
    ,那么对于k kk个子图* R* \' V7 k# K: Y! s

    ) a$ ^6 f' y) r" kN 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)
    * m( X; m$ ?  P  z1 XNCut(A 4 f  I  p/ g2 g
    1' Z: D0 y, Y) `2 z- h
    9 C$ e, f9 D# w* L$ V/ w5 d1 \
    ,A
    : D+ t% f9 h- t; V( e. n6 j6 z& D2$ l2 ]( P! H6 S" [" R. a
    . c3 I% l7 ^; U" t  D& t, {1 q
    ,...,A
    , T0 ?' C9 V9 _3 o: H' O* {* Jk
    3 i4 e" N3 c4 c4 R6 Q' q" b) b9 y- d. u
    )=
    ! F, Y* s9 w: |. a) g: w4 Wi=1
    1 o, g$ ~+ t( T# g5 t
    ( [- F; Q6 }7 T  Y7 k( k" y8 Sk
    3 K! e8 Y! O' F; ?% T8 {' {
    . W# G8 \" ~: z) Q+ { h 1 Z3 W  s- M) j) Z' p: C/ c& H
    i
    . g4 F7 n$ e! j2 @T
    # U1 ~# F" g5 K5 X3 i
    2 e2 @4 C+ u8 S3 e- T" I. |6 Q Lh
    0 \9 K- a) @# m. Fi6 ?6 c% z* y; v" |2 p5 ]' U
      t% C; b) O- l6 \5 R& C
    =
    - ~5 w% e: d' Z0 \: q+ ?/ fi=1$ w9 c0 q0 U: j# F6 X' |+ k7 U
    1 v+ f. m+ b- z4 n) ~
    k
    7 |3 ]) k! k/ f, \' H2 G2 B' G5 r3 i3 J
    (H 4 l* K% c$ |6 W) d' O* {
    T
      i$ a+ G. @( c6 ?- S LH) & Y* O, e/ x9 N
    ii% y: I* W6 f/ ^: I; o
    5 M* ?+ D, o) e  a, |
    =tr(H
    : u0 Z: E0 o0 I" e. `( {T
    6 J8 q; j5 K6 t4 v7 J6 Q! a% t& C$ G7 H LH)+ I* @; S5 j+ M6 n* T- n
    # g2 s! q6 F- T' @. Z3 K, w+ A
    但此时H T H ≠ I H^{T}H \not=IH
    - H+ u  s, d. v1 @T
    ' f. d! Z. `7 I, r/ K. b) _ H
    9 }7 e. C8 @$ ^6 g
    1 u1 O* C! `& l" |# U" z, I4 Z=I,而是H T D H = I H^{T}DH =IH " Z- u6 H8 f4 T9 ~6 E
    T8 s7 J( ~# e: H! J6 l4 T$ i
    DH=I1 l, i0 M- T5 s# Q# [, G
    : m& L; Y: x) a( H6 r
    这是因为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
    1 c6 [! J2 b4 L- u, r6 D! Gi
    ; |- n7 \! n  M) j/ iT
    ( Y. X+ m1 }! `# k7 J/ q+ M! {# g- ~5 S
    Dh
    / x3 i) W0 m: l- xi
    # ~2 Q% q8 W! Z; ?$ ^+ s3 P: N
    6 ^& n1 h- x# h" E =
    , |1 d- i) n) b2 ?% }$ s! l" k. Qj=10 W  f3 ]2 K& A; l) ~

    7 ?' [8 {2 F4 R1 e- H$ @! G$ Hn+ K2 O1 _5 I3 T9 M+ E  z, z

    * ?$ P& I# Q) v8 O; [' W; w h
    ! D8 O  H3 G. A/ Uij3 x; Z8 Z, d" T
    25 [; |/ F9 l+ H/ ~* f* P' B, {

    ( \* m, g. g3 e( Q1 T; ] d % j+ r6 N. [4 Z5 I2 z$ X0 }5 q2 q  H
    j
    4 i8 D5 D  ?8 s1 [" d0 p$ \# ]% [+ }( F, n+ F4 w# z
    =
    + ~( g, n9 Z1 `# ^2 Pvol(A
    & [% R1 V5 r! @0 Y. d1 A( Ti8 K- s$ M. u; k! r6 `; w3 x
    : G6 p+ w: y* W& F- ]
    )
    , x7 u* s- }5 W( l0 [) p  T4 `% }, ?1
    ! T/ f7 @" _# R) X7 B; }
    9 o/ X( U8 N0 u8 n* o, @$ ^# ~$ _: k7 _+ {2 @
    j∈A 6 a. l2 r8 H; s& h* S$ P
    i& b- ]; O6 F! a
    9 ?! ~$ _  k# ^- l& f6 e- `

    # [  y% |* d: Q8 @; z+ X" w' N# Y4 ]/ B8 c6 Q

    5 n2 I# n# K( l9 v, ?% X" o6 l7 F d ) g( Y/ E: Q+ ?9 x, x) _
    j" M  t: M6 P$ D0 s5 l

    1 O& q2 g( B, U! q, h5 L) u = & x1 q- [9 f, A* Q5 c9 @' Q
    vol(A
    2 B- X* G* d" wi
    + Y. I6 G- \) r7 m) Q0 b9 p0 ^" U2 z+ ~, M! I7 R
    )2 S: g1 e* X. ^% x4 M
    1" E5 D# N3 f+ I+ R( K
    + |/ A7 }+ Q4 L  f5 i
    vol(A 9 S, k& T. t* d  N9 N
    i8 s7 m* M9 u" ^: P
      P/ Q  [3 |; ~" {* ]" j0 f2 k
    )=1: s' x4 @1 B) o; d
    因此,此时切图优化目标为
    : i$ R* U& Z) k1 P  }! E/ z, {: i2 a+ F
    a 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
    0 j! n8 P1 S( I% b" b- {0 [1 KH
    0 F7 ?, X) ^, [8 @7 Hargmin
    1 F" l5 q, i: p/ L( w/ O) c. y
    ! F  s3 k- C% k1 g% p8 }
    9 o- Z" \. l& J4 [0 c9 z9 S/ U5 k  y& Y+ f
    tr(H
    , v, G& t8 F5 l4 v7 U0 j2 B0 kT
    9 l, I7 c' V. c4 l8 i- a LH)s.t.H 8 S4 `& Q% e( J/ a/ v$ U- p
    T
    5 H8 M/ J; N! ^$ Z* \- E1 o3 G. |1 w5 r DH=I$ G( m& a7 @0 j, A4 u
    9 G6 n) z7 y1 r6 J! `
    但是现在矩阵H HH中的指示向量h hh并不是标准正交基,所以需要对H HH做一定转换。令H = D − 1 2 F H=D^{-\frac{1}{2}}FH=D 9 o# T0 a" i* h. |  @# G0 L# p7 \
    3 F8 v3 r$ j/ }
    2
    6 ^- [0 y+ t4 v1 V0 w% ^1
    % W+ L7 Q9 G* u) s
    5 e* v& c& s: \# o) S
    $ v  p7 F: B0 T0 n; E 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
    * b( d! J2 I/ i4 k7 cT* Z1 Z4 ]) c: `6 G( A
    LH=F ; T' a+ s2 ]0 i, {
    T
    % E  A% Q+ J8 z7 Q  q D
    7 p" `4 p3 j' ?- w8 G, Y7 I$ B# q$ l, b( e
    25 a' {1 k4 T; _( j( G4 M5 o) v9 g
    1/ z( ~: x$ A6 W7 K# z

    9 y5 }- u8 q. i5 B0 E) c9 {8 q& Z
    . H. Z8 |. v% _ LD
    / G9 O) v/ V/ |5 H3 s
    3 S, Z! N% r! L8 p+ [2
    2 _) h, S# W; F: i( N4 `$ ~1" Y% |7 I! G$ `0 x* @

    ! n# u$ |5 B- Y/ n' }/ z  R$ ]" z. n/ J
    F、H T D H = F T F = I H^{T}DH=F^{T}F=IH
    2 |, `" E2 i9 B0 ~0 l' l4 nT
    $ @: @6 v# L0 t2 B DH=F
    . F$ y. \2 x& ~5 K7 G. e8 _$ x9 qT
    2 s1 C0 D' o0 L  I- F F=I,于是优化目标变更为# i+ E2 q+ I$ R. q) d
    a 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
    6 m0 N# e; g' ^' b2 gF% P  L2 |$ Y) ?, h8 h
    argmin
    : E: U8 J# G1 B, Z; b4 c
    # M) i- l; Z; \6 |5 S$ F* x5 `0 C

    9 q) T  c3 ?8 u% _, {- z$ j tr(F
    - I' L, V" R: JT
    & V- q' k' n3 D/ \7 T: A D - ^; ]8 L5 v" X( K; J
    5 Y- ~# h6 ?2 k+ |, V% o! ^2 J
    2
    . \1 e; d7 r! g6 x' G; O7 d1 g, T1 \6 ^1- D: R, c9 W  r; G4 F5 O. D( v
    ) w* b7 [3 n$ n# p# }; ~$ {* J* N7 S

    + d+ \: X5 W1 d0 S2 K2 X, h$ H% G LD
    5 K- k* o! c6 ^" ?1 X/ F* H
    6 e% A0 G! P1 @  n9 c+ r6 J2
    7 p6 {; y! {% K8 b+ i1* i* K) K. u( c7 U& k4 h) U* N

    6 u3 _& a1 P  K3 |/ D
    # X2 l! Y% e  R) i F)s.t.F
    ( N) J+ {; z0 MT$ Z0 y0 j5 l% K. B  t( Q
    F=I- c- w. W+ e* O* s0 g: s% }$ h
    ' }' w2 ~! H  e; e; `* i: v
    现在,和比例割一样,通过找到D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D 0 k) K: `6 D. f% c  p6 L8 S
    % s6 L# e, ^% \5 b9 m
    2
    . {* u) u* m$ j. ]2 ?6 o1  j' R6 m; }4 H) [& z. p0 \1 B8 B
    4 y; d  S  e- `* o2 X

    * s5 @- U; \6 d/ J1 t4 u- o LD
      Q9 f/ l7 D: d- X7 ^2 Q; R' c% Y  {  d8 x8 K
    22 o4 x( A' h8 e
    1
    1 Q% @  m( Z3 V# C4 o8 X9 O, _0 O6 C( v% U
    ; g/ y2 S4 a- R4 Y7 B4 P% \; i
    (就是之前的L LL)的最小的k kk个特征值,可以得到对应的k kk个特征向量,这k kk特征向量组成一个n nn×k kk维矩阵,也即F FF,最后对F FF进行传统聚类
    # j4 d# a6 @' r9 V( _, M
    ( N0 F$ L% m" a. L) E一般来说,D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
    $ [% m2 F3 P# @4 f; v: C
      j: `2 N1 [4 T" j2
    7 I' f0 V9 g+ n2 b0 j" u1
    % E# O1 V: I2 N2 U4 d' K. n( H8 D; o5 t
    8 K' Y* m* C! V8 \2 x, ^7 e
    LD
    + N! B0 K2 f8 N- V, l% \4 @" p. C+ T1 H$ Z2 u& w1 w0 g, C8 d$ U
    2
    " }6 A+ _* ]& P& v' @1
      Z* m! h. e  y9 }  a- E5 r3 {3 H7 w' d* |$ y

    2 W1 ~/ ~4 `8 U$ h+ j% K; u! H 相当于对L LL做了一次标准化,也即L i j d i ∗ d j \frac{L_{ij}}{\sqrt{d_{i}*d_{j}}}
    ! g- Z& a/ q3 U! m4 Gd & @0 z/ I* a! ^7 }2 Q
    i
    : e: m7 |1 M+ s- K0 s7 O' n4 v& g6 U! i( r# h( \) n$ J
    ∗d 8 G( W5 N  M6 A( k; S% C$ k
    j: v0 _- c& J3 c3 r9 E- n: k

    + s4 z  g4 v5 n) O9 \/ N$ ?3 c
    1 v! {8 n8 i* A  M
    2 v$ s  ?" Z8 A3 ^$ G" K4 j5 l( T) ~; w. B, C$ E6 ~7 D5 R  k+ d
    L 0 x+ m8 F* D4 Z$ R
    ij
    $ x& ~& S% G4 q  H( l
    4 z" O7 \0 m" F, G) j! V- _7 d: l# }, V5 x7 f+ E

    $ H$ O  {/ u7 |! D: E1 w3 N3 `5 l$ ?% m* @' J, o
    二:谱聚类算法流程
    ; S/ G8 I9 o+ {1 P+ m5 |给定数据集D = { x 1 , x 2 , . . . , x n } D=\{x_{1}, x_{2}, ... , x_{n}\}D={x
    ) Z" J. G! m* L1 t. }) V( G1& e, f( b. q. Z* a0 j4 l1 Q

    3 u" u( r- v$ T8 ~7 Q ,x
    ' X, C- l6 o  i7 v  u2% d7 g" W. V2 i, O- c, [1 L* H0 r

    9 U2 W# O5 A: } ,...,x 0 j; H+ r2 ~2 b, N% z& B/ }" x4 T
    n2 q2 U& j& y/ Z8 D+ g
    5 E3 }" V- Z+ f9 ^
    }% l  S: g7 f3 t' J+ D; ?$ l3 B
    2 l: w2 y8 A$ v5 D" }7 G
    根据输入的相似矩阵生成方式(一般为高斯核函数)构建相似矩阵S SS(AffinityMatrix)( ^3 I# h+ V5 a/ V/ E
    根据相似矩阵S SS构建邻接矩阵W WW,再构建度矩阵D DD
    7 y' ?3 v. {0 V0 l# d  t计算拉普拉斯矩阵L = D − W L=D-WL=D−W: f5 D, _7 c' E$ M
    得到标准化后的拉普拉斯矩阵D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D / ?0 Q4 v9 I) t5 S8 h% p* u2 Y
    - R& K1 I5 c. o7 J: c0 H' J% \) w
    23 J' M' a2 j/ o, d! q, s: g
    18 f1 [0 o3 H" g9 E& i* s

    ) Y, G; r" E# i) e! f
    0 p3 k& ~) Y  D6 y) N$ \ LD 0 A; c$ d9 a4 a8 o9 O. m. Y$ [& @5 T
    ) Z* N# q# q( v0 G! @" h: ~! z
    2$ o' p* m+ n/ J8 r$ r- Y% W
    1
    ' `  W5 p9 ]  R( u0 K4 E' u- B. [! `" j! X) m! T7 T
    + J% }% N0 I- ^4 K

    " Y* O6 I) x+ F5 ?  c计算D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
    ( d9 H& L/ l# t; o& k. [
      G- R, z7 L8 E2! g& ]* b; P7 v  b9 ~: T
    1
    . v. ^8 ?( _8 _, F" ?7 `8 S& [" f1 E2 f+ `) f% [' {: {2 ]/ }

    ! u' o$ U5 `+ _( E& t LD $ t% D# E0 |2 |0 k/ O6 Y; \
    % M  b; w$ W' v2 [- f( ?
    2# b& D" r! M+ s
    1
    1 |+ P+ F! t$ ~7 L3 Y5 D5 h5 _6 ~: j4 l; m  [: N. _6 |# u

    5 r1 {* x( K- ^4 q 最小的k kk个特征值对应的特征向量f ff
    , Y; D& R; A1 J9 R! F将特征向量f ff组成矩阵并按行标准化,最终组成n nn×k kk维的特征矩阵F FF/ Z8 ?; F2 m- s; x1 U/ h% c' h
    F FF中每一行作为一个k kk维的样本,共n nn个样本,采用某种聚类方法进行聚类,假设聚类维数为k 、 k^{、}k
    5 G, @$ U, T- k( d1 o6 X( f/ n( s: D7 c
    6 y- _2 O* ^- B$ n4 m
    得到簇划分C( c 1 , c 2 , . . . , c k 、 ) (c_{1}, c_{2}, ... , c_{k^{、}})(c
    - C) u+ a# C- C% m0 S- _1
    ! E# L6 h/ C( i, l, `! ]3 a3 N: V9 y! e% y0 q
    ,c
    ! C% f+ l8 W4 n' X2
    - g  ?: Q  F6 u: t4 ^2 c
    5 V5 U5 S7 m& q" l* \7 p$ l( [8 ] ,...,c
    ; q3 o( j4 ?! p; Tk
    6 J1 m; p1 U+ Q) B
    # |3 m7 o6 X: y2 [$ o2 `. ~" o6 E8 O# c

    / a, M( c3 _) H) v! x  [0 W )$ X$ y- k2 q; `2 F) z8 G0 Y
    三:Python实现. ]' A6 H$ q  [' O& A
    import matplotlib.pyplot as plt
    6 k2 E) J7 A, Z5 R& kimport numpy as np" {8 e6 K8 f# T, r6 V+ d2 U
    import pandas as pd* M  X# c  h) H" |; R$ F% l3 }
    from sklearn.cluster import KMeans; h8 e- U: {7 S% @) w
    from sklearn.metrics.pairwise import rbf_kernel
    ; h' w; I* p( ~6 w: mfrom sklearn.datasets import make_blobs. ^: r% U& z9 g2 L: f& ]" `+ W
    from sklearn.preprocessing import normalize
    , L# {6 a5 O3 j- c' |  [
    ! [* Q0 [/ o8 d$ a- J& E1 p. Qdef get_affinity_matrix(data_set):
    3 ~" ~' Y0 [) S% v/ I- _    #  利用高斯核函数计算相似矩阵(全连接)% q5 D5 {! l& p! _$ R2 }
        rbf = rbf_kernel(data_set)6 A  h& f, X( q
        for i in range(len(rbf)):
    . g- [6 W3 \* y/ p. |        rbf[i, i] = 0
    / m: M1 f8 `0 K+ O& ^5 W$ {6 u8 `    return rbf
      i- k8 `* F' p: b( O/ s) J4 h, G' T9 B; t$ G

    ! w$ J3 R+ d# c8 Q( R4 ^def distance(x1, x2):5 O& k: I# j9 p+ G  Y
        """
    9 ?; q( a6 B0 @4 Y5 ^4 V5 N( @    获得两个样本点之间的距离: J" F/ |1 ~! h9 m  k1 ~- F. K
        :param x1: 样本点1
    4 e/ T& S1 l/ I" ?. Z    :param x2: 样本点2. ~. ~3 K/ \1 ]; U* E
        :return:& _; s$ S( T) S5 m
        """' X. ], e- i- `; F) C' z/ i
        dist = np.sqrt(np.power(x1-x2,2).sum())
    % Z$ k$ T0 k$ n- s# H& T    return dist/ x$ W; O* S% O$ `, s; S6 g

    ! n, A2 A+ t) E; `  u2 G$ s6 Zdef get_dist_matrix(data):2 V; F9 L  ~! k: i) v1 q  q8 S
        """
    ! S+ s* ]9 B9 l6 K( F6 t    获取距离矩阵8 T* @# E0 g2 z) n& y! d2 y( f  A
        :param data: 样本集合
    5 L, I& W- I! c    :return: 距离矩阵
    1 V' W3 y& \$ V' @/ ]    """0 C% Q% r& L* Q  d" ~% U5 }( _# u$ O
        n = len(data)  #样本总数. w  m7 L* R3 T% [4 {8 C. [" H
        dist_matrix = np.zeros((n, n)) # 初始化邻接矩阵为n×n的全0矩阵. g1 u( H1 u5 x. z( z% w
        for i in range(n):
    ' Z4 e, O2 b; X4 a+ ]        for j in range(i+1, n):8 d& \2 \' B" M7 u  _
                dist_matrix[j] = dist_matrix[j] = distance(data, data[j])0 \) Y+ P$ }1 y. u
        return dist_matrix
    0 N0 s8 x* J+ G2 |2 {8 c8 g) d6 I' l! t- |7 e6 H1 k* B
    def get_W(data, k):! K( ^$ S/ d2 D! S( G! M
        # 获取邻接矩阵(K邻近法)
    6 o% T5 B6 o) t& z    n = len(data)
    . n4 F7 g+ w+ E$ S8 N/ Q    dist_matrix = get_dist_matrix(data)
    4 F9 K8 x% n& E( h, U. U. m8 `; n: I    W = np.zeros((n, n))
    3 }& g# v& ?* w' ~4 j* x) X& M    for idx, item in enumerate(dist_matrix):
    ! u, q: A. c9 B* n        idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表3 j: t$ n4 D; n
            W[idx][idx_array[1:k+1]] = 13 G( S) y; _* y& _, F. \, y* L
        transpW =np.transpose(W)
    * ~& W( e" l; Z6 |, ^    return (W+transpW)/2$ U2 R% J  H' u4 |- c4 `' j# Q
    . t/ {* C. A: L9 f$ W
    def spectral_clustering(data_set, k):
    : s$ n9 N" G4 J: ^5 S, N9 ^    # 利用相似矩阵S得到邻接矩阵W
    8 S' ^0 M2 a0 v+ d2 }( r    W = get_affinity_matrix(data_set)  #高斯核函数(全连接法)4 L4 h- {5 W& [4 z' _" L
        #  W = get_W(data_set, k)  # K邻近法
    * |# A0 [: E' K! }
    ) J$ F1 `5 P1 v, i8 ], z    # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵(便于计算拉普拉斯矩阵)' y; \: S5 Z3 X2 V% @( T
        D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
      t+ L/ l* Z( w9 ]3 M# }: Y. L
    1 X3 U  K4 q5 @    # 计算拉普拉斯矩阵L=D-W
    ) l5 k3 q$ o, o; O, \( l: r8 w    # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
    + h4 I; W( {0 }3 t2 f, \3 E9 n# g    L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
    ' r4 `2 i6 r: T& p% m% U4 [5 Z% M/ Q& C. {8 @
        # 得到特征值和特征向量* K1 J: V5 ^$ K1 W5 r6 B3 L
        eigvals, eigvecs = np.linalg.eig(L)
    % v' b; Z  V6 W
    ' P" O$ C" H& {: ]* O9 m4 M    # 找到前k个最小的特征值(索引)
    ! R- d! o. |3 a; `3 p    k_smallest_eigvals_index = np.argsort(eigvals)[:k]: e7 m2 `# o3 C) S

    8 A6 z$ E( V% i4 b) }    # 取出这k小特征值对应的特征向量,并正则化/ Q" P/ s$ }" o$ g  T- S
        k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
    ! S2 A+ M$ G% `" I' h# O) Z, U$ ^8 v) J/ f* v
        # 使用K_Means聚类
    ! t4 R  T* ?' B* X6 z; h    return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
    - e- C% B3 \6 ~! @: c1 l8 H2 z& h) v4 a( s+ @- z6 q

    ! K; K, Y1 S" traw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)! A+ R' `( _3 s9 y
    raw_data.columns = ['X', 'Y']* Q- Z  i6 F: V
    x_axis = 'X'
    5 r9 j6 {; b- Gy_axis = 'Y'8 B$ a# ^7 k2 J' n8 I5 q2 w8 D, g

    : c8 W  G% o& F* f! O2 F# fexamples_num = raw_data.shape[0]) p$ E6 x- Z' i+ k
    train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)5 `( U. r% V& F6 {0 }
    7 S8 y4 `/ M; _0 `% j

    # Z; T. r$ B% L1 Dmin_vals = train_data.min(0)' x& g& C6 ~1 Z2 Q
    max_vals = train_data.max(0)$ D6 |3 o- F( j# D
    ranges = max_vals - min_vals
    ' H0 s1 m! h. ^4 Snormal_data = np.zeros(np.shape(train_data))
    8 _9 W' a4 a5 i+ J3 ~nums = train_data.shape[0]# l5 D7 s! v* `) d$ C% C+ m% u' {
    normal_data = train_data - np.tile(min_vals, (nums, 1))2 Y. k' J2 Z4 D" t; Z- l
    normal_data = normal_data / np.tile(ranges, (nums, 1))
    1 Z; Z$ t: d+ z, b) |9 }
    5 I- s1 R3 m7 B2 t: L$ qlabels = spectral_clustering(normal_data, 2)6 g& k, m$ v% {! S
    $ q5 I- ^( \: Z* a
    # 原数据) c3 p8 g4 [* N6 V" g
    fig, (ax0, ax1) = plt.subplots(ncols=2)
    ' J( e4 b( y) }ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')2 o/ S, i! C7 Y0 \! p- Q( N
    ax0.set_title('raw data')
    7 b& M- w4 C/ X* W7 R% d# 谱聚类结果# W) L6 s# U$ ^+ H
    ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels): @0 D# D! t2 m! K1 q1 T; ]" c
    ax1.set_title('Spectral Clustering')
    , }; m7 b& R. ^7 ^9 M
    ) h  [8 [* d+ P6 D7 L7 zplt.show()
    " c* u2 y$ S9 n6 B% j" Z
    3 E( w( f& A6 m4 J: N% t1
    / q; U- F. j5 _, k2% c% }3 S  ]$ A$ b4 z5 g
    3
    % \# z$ q- o* ?& e4" Q/ ^* A, d% [& Y5 I* T
    5
    , Z  }8 W- C0 c+ ?6
    % {, l% L, Y0 N. C( a/ l7
    ' S$ p! a* t2 W4 l8
    2 s* M- p1 K. T9 G) _. A8 a9
    / Z0 a- C: R% W% ]5 V: ]2 L4 N- o10$ \9 X0 q7 ~' D9 _& Q/ f. D
    112 Q4 P! v7 U5 |5 t+ I& O
    12
    % |% K+ F0 V  i& K& W13
    1 `6 F  z- O' ^* M7 Q8 a- N" V14
    , M+ u5 P$ |" u15' I& `- m1 T3 ^( n
    16
    8 Z- R; I# J) I1 c2 u( h175 w. _. T$ B* \
    185 O  d% q, n" y
    19- u0 R+ X( P  g6 [/ F8 c
    20
    ; J. K7 V7 ?1 D% x% x1 Z21
    ( e6 _3 O  W1 X/ F  C; k, [# F22. l6 V4 G1 e* e  x0 x1 Z
    231 `" _9 V& Y5 x3 }& s
    24
    6 Y- ?# A- c! b- C25
    ! [5 ^& `3 _, s- z0 }( V( ~26
    0 c0 N# A9 L5 h0 S0 [3 q& e7 J8 d27
    . b! \2 _$ k2 {9 S288 o9 [. B. T/ V
    297 g2 @/ Q+ C# j. ^
    309 M; P- X7 a/ J4 @
    31
    6 q# Z' |/ O, _4 M" |4 Y4 f32
    % U7 w; d' l% [1 a$ i$ S0 [33
      m7 A- B; d" c5 S34
    & O3 O: D1 N3 s359 C, E$ D  T( ]+ B% y
    360 a2 \  k# [7 ?& q4 R( ]  l
    372 q. {! F0 ]; G! a" B% k! E0 W
    38% @; m& t+ s$ j. x
    39/ N0 H0 f+ {5 m4 V
    40! ?5 D. g) S' i+ y8 `/ d
    41
    ! X& v/ A/ A( H" W3 D- l429 W' w6 P% A, x8 D; a5 q
    43. u6 P' A' {* l: D: N, I
    44/ u1 ]. O: G3 @
    451 L3 i3 R) J+ I) B
    46% M2 W% q$ z' H5 S4 g  B1 z; c
    470 q/ i, v% u) E. I. J! {/ l/ R
    48
    3 V- S- ?/ [6 t$ A6 b49
    " D+ N- M9 Z7 `* |9 g( p50$ p3 R$ m/ t% I
    51
    2 C  M% y5 G+ |" H52
    2 D  r9 _! a  Q- H  \53, p( s" I% U9 I3 T0 P" v
    54- Z- |4 g* f9 y- v% n. n3 C
    55
    - g7 f# \+ Y7 g# n6 x6 m' [8 ^" I565 K2 b. G6 E& }" {6 A
    57
    2 y8 }( V" A* M9 y4 S58
    : _1 b: ~, j! O: W$ u/ S597 n0 A1 e) d! |9 }& D' w8 C4 Y6 U
    602 ~5 h1 |; [5 T3 C1 F0 Z
    61/ t6 J# d: U' E5 O, |5 V
    62
    % k* ?; b, h4 K, Z9 ~63
    # M0 B6 \( ^# K+ N4 d" ~. u64
    % u. P4 }1 U# k1 `/ A( R2 ^65; {2 c/ M" y- }: h
    66
    " y+ d, z" X! {. ?" M67
    1 j) v, b: W! v& o4 ?4 F. S+ k68: n$ h3 B/ o* C; k3 }& H
    69
    : k( n# w- l0 P6 }/ o! |' n  ~3 ?0 }70. {3 K" n; R, C+ y4 O
    71+ ?( i* @5 |9 O
    72
    . P. T. g$ E) W# i73
    # n' Q& n/ e  m( Q3 V. N74
    6 Y, Q) R" k6 R" z: L" C+ h. u75
    8 ~7 _: c6 F# J1 C$ d76
    : O% k% t' a3 t2 K! P. ^: s7 c* ]: W77
    ! H7 t  a8 h+ U78
    8 J# V9 g+ n' r& m. k  l7 z79
    0 A6 d3 Q3 {3 r( d1 ~4 D) e. ^80
    8 A  b; @. Z; T( [3 {. x: y81
    : H8 `+ S0 y+ a; Z- C; M82
    . l) f# O! e; @& g1 x83
    * _3 m6 Z' M; y$ u84' \; \0 U5 A3 l0 k' K
    85
    + \  P. P6 q1 H1 X, a) v! X2 C86# ^' Y) i& L6 |( `% N6 `6 P& Y
    87
    * B, j+ P7 w; I: _88
    ) }. x2 _, k- u7 Q. R3 N" X; b. q89# c  u# x  H2 b" f* h9 l  q
    90& D# S$ V: F! i$ [
    91% E7 Y' D# a9 a6 ?2 k
    92
    # }& Z& N. U4 M) a& L, h8 E8 x. x93) d/ H3 `- v5 w! P/ Z
    947 D1 e& |; P7 x1 J$ u, h
    95
    6 T' q0 l- \( u  b% j! @% ?9 B& s96
    - u& a& @: o& A4 p$ a979 ^2 [1 c& o: }8 a" m7 I
    98
    " `+ o. l6 a5 N* ^8 D% g3 D99
    7 h* Q! J( D2 G3 s1009 l+ x4 a8 f  {0 j% Q0 b+ [2 D
    101# C$ S$ ?9 r- X) Y, h/ J. R
    102/ O8 C9 G  h. f$ J4 C: S5 A9 w* B4 }
    103
    ; o$ v) l- D6 o: X1 ]* @(高斯核函数)% b3 q; H5 h7 a9 G- g" T5 N: ^- p( V

    4 ?9 i9 ]; N0 J0 i/ J9 V
    3 b0 }5 q2 `) z(K邻近法)
    " y8 s# w% K  |) m
      Y$ h$ G4 B- v; M! S( `- T+ D/ d4 N, N2 T
    四:谱聚类算法优缺点
      c. P) u. M( D1 t, c7 B(1)优点4 M# A! b5 z4 H: ^4 i% ~
    谱聚类只需要数据之间的相似度矩阵,所以对于稀疏数据的聚类很有效
    ) `4 a- n" \% i: d" D( o' d使用了降维,因此处理高纬数据聚类时复杂度要明显低于传统聚类算法  j( y0 l( ^# G! _0 T3 A
    谱聚类算法建立在谱图理论基础上,与传统聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解& c; b6 Y, B1 J% i
    (2)缺点
    " [6 g4 l# ^. ^/ \* J# j" o如果最终聚类的维度非常高,则由于降维的幅度不够,导致算法的运行速度和最后效果都不是很好8 o4 y  |* h. K
    聚类效果依赖于相似度矩阵,所以不同的相似度矩阵得到的最终聚类效果大不同相同( H: ^' s) O  d. W; N" ], o
    ————————————————9 j' `+ X9 g% z' m/ b
    版权声明:本文为CSDN博主「快乐江湖」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    & h' S" |9 n" E原文链接:https://blog.csdn.net/qq_39183034/article/details/126747494. L# ], q4 V4 E

    9 Q' a7 _4 _) }- E; O: A# H( h& R' D& W+ Y% {0 L/ f' d% c/ Z% }. [4 z
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-14 18:19 , Processed in 0.461444 second(s), 51 queries .

    回顶部