QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3007|回复: 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
    【数据聚类】第八章第二节:谱聚类算法之切图聚类、算法流程及其实现6 G% Q5 ?# ^- Y7 M3 v/ k

    # O# b7 H" a2 O: p本文部分内容源自刘建平博客,在此基础上进行总结拓展
    ' M* P) O8 l$ _3 h6 I2 o6 q; @$ K9 n: Q9 t; s
    原文链接
    2 |$ x+ f( Q/ d. d/ Y9 B文章目录
      ?* s# t" F* z) P* W6 U一:谱聚类与图划分# c* a, u; G- k3 \5 b
    (1)比例割
    4 H+ x* J* M+ K. G& F  N(2)规范割(常用)* E% F2 v1 W7 w) w5 {% |
    二:谱聚类算法流程/ j! N3 h9 u  B( {! b
    三:Python实现
    + k. V9 q$ S7 p( e2 A4 G/ V四:谱聚类算法优缺点
    9 U0 O2 @" w: q- n4 X: |(1)优点
    $ S4 C4 x0 O$ L7 {% E% Q(2)缺点, M- I" P+ s3 K
    一:谱聚类与图划分. a+ n+ F7 h4 R8 u! H( P9 u$ l
    无向图切图:谱聚类算法根据数据点之间的相似度将数据点划分到不同簇中,因此将数据点映射到无向图之后,可以转化为图划分的问题。对于无向图G GG,切图的目标是将图G ( V , E ) G(V,E)G(V,E)切分成互相无连接k kk个子图,其中: d6 B9 [, k/ |! u* b" |

    1 |0 `' q* }% l, b/ }% y每个子图点的集合为{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
    $ S' C3 F  ^$ [0 d  j1 U2 v: g1
    0 ^! N3 X' i) R% j5 m
    % h8 k6 B2 ]. |% g2 N! P: _2 D ,A
    8 x% r/ h4 S( G2: a* ]/ j) t6 F) e( n; m/ H
    4 B: P* h" }& |) `0 T
    ,...,A 0 J6 Q$ c3 f3 `; X, f
    k
    8 T" G0 K0 j. u. M; T& {
    4 v5 J, s- Z1 ~ },且满足A i ∩ A j = ∅ A_{i}\cap A_{j}=\emptyA
    + ~6 F) y2 L+ F, l8 T- Vi3 \, Z% c1 V% t2 p0 {0 _
    # s; G, a1 e: p3 N
    ∩A + ]! D7 a3 S7 I7 u5 y3 ~2 ~% T
    j
    + \6 K2 X! z5 `) R% H& N; m- H" C! e0 F! ?* E+ t3 R$ f! Y. |
    =∅、A 1 ∪ A 2 ∪ . . . ∪ A k = V A_{1}\cup A_{2}\cup ... \cup A_{k}=VA ( G% z# K3 x4 B) X
    1, k' S* W: F: ?3 [5 l8 h' `! d- J
    : h- Z* Q3 V, _2 W0 c, o5 H; s8 x) C/ e
    ∪A
      {  M( c$ d; t$ ]  ?- R2; t: `+ v% X1 e9 a# |; g) n
    / V# @, f+ S5 C/ w0 Z
    ∪...∪A
    / @" v$ O" P( y$ q) T. t: hk
    $ Z# c% q7 K- p" {3 i! Z7 M! V4 s  }
    =V
    . J3 q& b: m. 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)=
    7 h$ J8 m6 k4 t1 {( bi∈A,j∈B. C) A5 ?8 ^! N( b

    . c. c- G- _6 g# \! W
    ( U& T% `4 t' @, e) {/ I w ; T# |2 i: [+ b- S5 _5 Z( t0 s; i, [
    ij
    % Y2 X5 X' B, s4 j0 c5 A+ n- G9 i$ b+ w: u; |$ ]% r( r& L

    ( T9 `6 r* f# r7 r对于k kk个子图点的集合{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
    ; ~. Y% j& e/ m' h" H10 m( @5 B9 o' w  w9 H

    % \. E& n* V8 B  Y  T ,A
    ' J; o, D2 f: {' b: `2
    % ?6 m3 \& B5 v, }# f& n
    7 z$ v7 [' a: s: o% P ,...,A
    $ ?/ p$ }7 r0 I& Ek
    6 ^6 p4 d, k+ o9 Y, v
    0 X4 w. G: \+ ^" l1 @ },定义切图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 9 ?+ c$ s5 b6 g
    13 \- P! ~7 b4 l+ H  z

    7 A3 j* L3 V# m) s ,A 4 s% a1 t. a4 X$ `, Y* ~
    2
    2 z$ p4 W8 o% G5 @# m- b2 F' x" p. S2 Y6 R! H' _  m
    ,...,A 7 k( G; I% X( @# M
    k
    4 V9 N: U  A1 \, k( j$ C' t( v4 K5 e% E
    )=
      b6 l7 J9 z) y2# b; j7 u/ P; A* Z" }
    1
    ; Q' l) [: H$ v/ g) Z  x# H4 |2 J
    $ E3 f  V0 K3 E) C% G% p# t. [. i' B1 M9 l) e2 m# N
    i=1/ w, c7 m$ s6 x3 s' A

    0 l6 p/ q4 J5 R3 y( c' gk
    ! N  t: o1 p8 v- t1 X8 Q2 U
    8 ~+ C6 _9 E: i3 Y, E' E W(A
    + r' x4 \2 @3 o" ]3 di: M& o9 u, G/ g' D0 Q5 L

    / `5 l5 f8 e1 ^9 @, b, k , & J# ~) x& W" j3 M- J) R
    A: J  q; m1 ]- G1 I; ~
    ˉ
    # |  j7 j. r; [& R4 k) x, c
    : \% s" x7 L; w- V7 Di
    , ^8 v& C' O" d
      j5 o( z# d+ C/ G8 ? ) (其中A ˉ i \bar A_{i} & n/ A+ N' u0 z# z! ~
    A
    & i4 ]- G5 X: |3 R. Kˉ; k0 I6 L2 ^8 m" H, L

    6 k! s" ?+ a0 n- yi- o+ N* a" h3 U9 ^. c1 s0 B8 O9 w1 L
    ) u+ {! }' I3 {8 ^( O" }8 w
    为A i A_{i}A
    & c  u" W; \  e; t0 P& J& fi0 ^% }9 X$ a1 o! B

    ) }' w' F. Z( ]5 a, [/ d 的补集), X3 @; u2 P$ [9 C+ t( }" U3 V
    可以看出,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 7 ~9 j! E  }+ n9 r# [* D
    1+ O+ ?0 n; R% }$ |# W+ V8 X/ m
    3 o8 p, }8 ~/ G  ]" ]7 P5 d
    ,A
    5 k  R& r/ U3 L) @2
    8 s( Z1 ~- E: o
    + ]1 j/ B1 l: K4 N) {" h1 e5 t3 P ,...,A + W3 u# V$ C' ]& y
    k2 b8 p7 R4 a2 ^0 t+ |

    : y" }; P3 T* `; | )=
    ! i6 X6 t# j, D3 [, |- w6 ]2
    $ m4 C, R7 a' E, V, |3 M, K6 X, Z1; k; e( W+ d% F9 r4 |

    * l9 M! J" L/ n0 a% Z* }* ~0 z# E4 \4 ~
    i=1
    9 K, n' t' L2 I- x" K. c5 @2 V7 `0 ~  B' o. ]' V& p8 z1 i: C
    k
    8 V8 a: }5 r6 g( R8 |' Z6 h+ u! h2 ^6 z. F3 J
    W(A 3 X) g; k$ T$ K% R9 _! X
    i
    ) f$ q( z2 e+ f3 S. [
    . o: T- ^2 [1 k , % Y2 p, o/ ~9 g1 R
    A" D! a" }# h" b
    ˉ- L& k1 c9 Y& l/ }
    ( l* L% I- ?0 h- B! D) Y
    i8 M9 p1 x  o$ W( [. J5 t, C
    8 {6 g3 ]. l4 k1 {6 R; c
    )在划分子图时并没有考虑每个子图中节点的个数。所以在某些情况下,最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A # D* J' P2 x0 p7 }# G- c
    1# p% a, q+ u3 u: T; @
    / l8 u$ G4 t' J$ P  s  e
    ,A
    ) |. m# S* v& r& O( {2
    5 W4 Y! ~0 h+ U5 U* V/ q7 J, \( I3 g$ E% U
    ,...,A
    ( b1 G9 f, _/ P8 tk
    4 s+ H  n( F3 q& m# A. j* ^! x: m
    )可能会把一个数据点或是很少数据点看做一个子图,导致子图划分结果不平衡  Y2 p4 A) R1 U7 ^* d

    : I% h; E) l* s+ P6 G* h6 N6 P例如下图,选择一个权重最小的边缘的点,比如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 5 h: Z7 O4 d( h6 O7 w* V
    1) K) w, C2 Q1 j3 S

    ; L" y) o, m: V2 P% [ ,A 8 @7 L7 z: F6 t4 ?& K8 u
    2$ s) m. p6 r% w: n" T- B
    * j) a- V* m6 J0 M$ _, S$ S, X
    ,...,A
    ! K/ h0 }8 |; B8 W! @( @2 Y& ek$ N+ m& A. d+ ~
    # p" w) ?5 ?: D) b5 W1 b
    )但是却不是最优的切图8 ]8 C' _: c" b- I; _
    $ d+ e. d" |( R3 w' W' m. H
    为了解决这个问题,会引入一些正则化方法。最常用的两种方法为比例割和规范割
    8 J& }$ p. m% {' e6 i2 X
    / O) S4 w1 `; W  Q9 U比例割: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
    : |" K7 v+ v! \' S7 q4 {1
    / B2 B, O2 v9 ~$ n: K/ d; [' s+ u, A% p  ], z( O1 ]
    ,A
    . n+ m) T& `3 Z3 S$ S21 _7 q9 M- v+ g6 i+ f; n
    & W2 C. X+ ~% Z! n* q" e6 J3 @9 m# S
    ,...,A
    4 x7 k1 f9 O3 B( R2 T4 @/ gk
    - c/ ^* J, J' D
    9 B. V% X0 h. }4 Q1 h, I- b- J )=
    3 ^( o6 Q4 C8 j1 Y+ g27 J. I/ |) N* q
    1
    8 g: E8 w  H- _' a0 J
    ) d. S* {9 _( R' b8 c* D
    " O" Z( x. A$ S2 [: _; t  f4 ti=1
    8 x$ i3 Y: d* J
    * t$ a% l0 ?3 c2 v) W2 O: hk: N! W/ G9 m* Z

    0 g: V5 ^  j+ I5 L/ T5 Q$ T- F, b5 V6 m- {# E
    ∣A
    3 N' B7 {0 U! t1 gi4 v/ o7 ?6 d& L% l

    0 t; F' e, z% m& s4 Y  Q
    - _: [8 v# n, o6 P+ d$ G. ~- ZW(A
    / n# p$ Q9 v; N+ Ri0 ?' d) X: |+ O! C1 M6 z+ L1 }
    # r3 I" e5 s, O
    , 4 X; l9 _- |: p! W6 K9 Q. r
    A5 A( `- G# B  Z4 O. P
    ˉ
    + O- {8 i' I( y1 ~& X" J- Y0 i( z9 j2 V  W8 x+ S4 G. V
    i
    ! c0 S* d. B# X* f' w: z2 D& u) r2 X# Z: v# p4 }/ f
    )
    9 v' _3 c5 b( V/ [: y' m* I# E. S" b) L* o& l; D3 O( d% D* I
    % Z' }  [- ^3 C  d/ l
    规范割: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
    & c6 x$ e2 k6 }1" ?4 O7 Z; S. a; K- j$ V; [# `
    ) x, j/ {# w' V0 r7 I
    ,A % h# m3 X! c  ?# ?
    2: F; W2 I3 x: B6 X+ f

      E; J% a' s+ J6 @6 ]0 o+ g ,...,A
    3 f: r" v0 Q- yk
    4 y- |* i( z/ h7 y: l. k$ ?- x; ]! [, p' ?. x  q# M9 e1 X9 F: Q0 q5 @
    )= 9 o( c. j: M+ }0 `) J
    2
    6 R+ b$ w' f# s1 P+ a2 M* p! y1
    $ F; k- y4 _6 p' Y! l: v8 D% s5 X  H( H; I- d; S5 a6 h
    / j( i) ]% ?3 W' Y
    i=1
    3 g, x( B- \( B/ J, o; T/ L1 h# A1 s
    k
    ' \% g! V5 V# U# ?3 u
      C: f, B/ M+ f+ ?: e# [
    0 Y* d( W: k9 S: j( P% F0 O2 Hvol(A
    9 S/ m( r- X8 X1 Y' @2 q& Di- {9 S6 ~" l- a1 _- A

    ) l- m; B# T/ s! u, B4 M* y )( a: D1 s0 D4 @. m
    W(A
    8 R, m- E" p6 R$ li
    ) R8 s) {& ?  R# Q9 h8 S6 W* R; R1 B4 U& }& v0 `! T6 b  |$ f
    ,
    3 z3 V# S# I2 l0 V% `A, I' v& i8 O' G$ r" R, T
    ˉ3 L8 P# m% f3 ]. {+ P+ V
    0 w* ^* M( c5 R1 ^6 m
    i
    - `5 P( k& g0 B( Q) O
    . w5 Y+ w1 M! `$ R- G: d! Z! Y% v( h. y4 V )
    ; z$ e& S5 i& i6 @( M
    6 ]0 p% Z  f4 k2 H5 W, H* l1 l" y2 R2 _* R
    (1)比例割% @  K& r" D' ~( E1 b% F5 j0 H
    引入指示向量(点击可查看指示向量定义)h j ∈ { h 1 , h 2 , . . . , h k } h_{j}\in\{h_{1},h_{2},...,h_{k}\}h
    8 I3 R0 w6 r+ ]# Uj7 j" m: x" K- M2 c
    % h  m, r4 _( `4 o' w2 K$ ?
    ∈{h : F+ I" L: y' e
    19 O8 X% k8 C1 B: V
    ) P, ?! j# C3 i% g9 d8 t3 s
    ,h 2 z8 D. Y. N) H, R% F2 P5 [0 h
    2
    1 \" m! ^5 _5 ~1 x- [  a/ x( K9 G0 Z) E
    ,...,h
    ) k& D1 h7 A; w! Fk
    $ c: L$ ^" n1 J  j. W% U2 P+ ~0 ~
    },j = 1 , 2 , . . . , k j=1,2,...,kj=1,2,...,k。对于任意一个向量h j h_{j}h   T9 O1 L; q# q
    j" y7 j2 W7 U" P& U- G! H
    9 n) m# \% h5 k, O- O
    ,它是一个n nn维向量(n nn表示样本数),定义h i j h_{ij}h % g, r: a: q( q3 G. {$ L3 F7 D
    ij2 F& D' Z1 ?6 q8 h$ R! J1 g

    ( h/ T1 B* {) ^6 b 如下
    , R! L( F6 N* f: j9 [- o( h1 g. |- [8 t* v: H4 g4 f( u5 K
    h i j = { 0 , v i ∉ A j ∣ A j ∣ , v i ∈ A j h_{ij}=
    7 D# ~* {  @7 A# ^{0,vi∉Aj|Aj|−−−√,vi∈Aj
    % z, v  B6 D1 I$ S{0,vi∉Aj|Aj|,vi∈Aj
    4 M! V# s  E5 A2 Th
    ! Q0 {& v  z# h6 }0 J* {+ b+ J3 s( zij0 n% K7 C3 k4 n5 [# f7 B
    ! y( o9 o% L; q2 l, s9 D! `/ E
    ={
    # W" [) ?* [! M0 P) w; N* M( H4 F0,v 8 ?! k! o5 [" b. C
    i6 `3 s* a' ~; X9 e7 m8 f
    + Y5 W2 U4 X1 C2 X
    - r+ I) K" o0 I4 e) U
    /  `! P, Z7 m: z$ H% k8 e' Q0 M
    A ; {* S# e: R* g3 h4 b
    j
    2 j- @0 s" [' n0 b& c" J! ^
    ; f/ n* ?! |' C. G. c% X
    " e0 T; z7 l3 F" @∣A - w5 P) R$ \3 @7 e. M& O
    j
    ' S9 q* N; E9 @1 d& Y# E- l( L# j  G3 X6 |% r4 g: ]( h1 H2 {
    / R! `0 A; Z  |& M- _; a
    / H2 [. V, w8 g5 Q& E+ d' s
    ,v
    % P! p- E& I% |i
    # j) y, o+ c; `4 Q% ]# i2 z
    $ |! b8 V% U9 p- ^8 p# W8 R1 P4 q ∈A
    ! u: J* j" f, c- a" jj
    8 q, E. k" L! k9 f
    ) O$ }1 g* a3 ?0 B& s4 `3 j% [) H4 q! K3 s  [: ~( y. l
    5 q. D) I  Z% u, \( ]3 I

    ! V3 q9 h) K0 ^8 W' t
    # D* m( z$ F1 ]( W于是,对于h i T L h i h_{i}^{T}Lh_{i}h $ z, H  D1 k2 I  ~; ]# R
    i
    % Y1 c  j% s+ v9 F. f% eT9 E3 _5 S5 T/ k9 P) _# v
    7 p# Y7 R, M- n, H, ^8 _8 R
    Lh : s4 d6 [+ s( _3 x; @
    i" u5 e( @' {+ x5 l; v2 e$ W
    " U# j1 }- F# U4 f* Q. H
    ,根据拉普拉斯矩阵性质可知
    8 D+ K4 H' C( @* j9 ?0 n9 i" O
    9 P$ n# b# U* Z2 h对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
    : K7 S. u7 ?: m5 D1
    2 p- O/ G7 v) ~" n6 U5 A
    1 p4 H: g$ _, `) W. w ,...,f
    3 G& Y3 P5 r& B! U) R6 u: Yn! z( E5 f9 O6 X- a# x/ I( X; P
    + u5 p- `3 ]2 K* M( K! f! r; Z
    ) . O& |  N0 t$ \0 _% @
    T# l9 S1 ?8 e; U' n
    ∈R ! {) a' A5 Q7 t+ T
    n2 v; Y# ^# {& Z$ I) Y" P0 }  O# ~
    ,有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 6 e  ^6 M6 x0 F" \1 T9 [& u- ^
    T
    $ o/ f  J9 @% l6 E Lf= ) w7 e* Y* }" M+ Y! @6 u7 B
    2
    - O2 I* e9 m( T7 S* Y9 Z# ]1
    - m" Q$ V3 [2 t7 B6 [) X4 J7 h0 y/ q8 j( }
    - L7 S; Z- g3 g& |$ R5 I3 x
    i,j=1
    $ ]  W9 _2 g" V- S
    ' k" h, i5 F; C2 ^% J# @8 l' c  ln/ ~3 T; _  P) M) j& f
    , P1 G. H: X5 k0 u3 t
    w
    4 ^- K" M7 Q. F  e) f# [4 e2 ~% Rij7 u. P7 y  Y# _* _. P
    / X( M: e3 R; _2 R3 N* f
    (f " N4 @$ p. a+ i
    i
    - p2 h' d3 U" i
    ( [% I& t$ i/ l" {+ A% v −f   p/ Y; j+ I( p* l  E) w  @
    j
    9 ]" Z* Q% T$ j) y5 o3 u7 M1 b- l1 P, P. L* _4 `/ W& c
    )
    $ F3 F% r8 k& }6 E( o2 A; Q2% r% T; N+ R* q: h
    : [/ o0 \" K* V1 T. D$ 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}|}
    5 e9 E) e7 x' b, \' Sh 3 x" R0 ]0 [7 s% O
    i
    3 O, Z7 p9 r3 j( y. bT0 Y( h, H1 f, [

    ( J* M# H. D; d2 [# z' _ Lh
    0 m: w1 T1 l& @" o6 j$ T/ V7 N: ui8 \# W" {% j. g' O
    & W# h; y& s# v7 x$ s
    =
    ' f3 A6 S7 z2 F/ `5 ~* S5 R8 q2
    / b7 X. t" e  X5 l) @+ ]1. A1 I1 A+ @* o% Z
    & O" h' l( N( r, k4 y; z

    : o; I! R9 R0 S( Rm=1
    . b9 L% [2 ?' r& a- p1 m9 [( Q0 a( f8 }9 B- e
    3 l" k) Y4 p) M+ b  w
    7 R' K  B- T3 E" Y9 c3 N
    n=19 }$ |' f- i8 m& z+ ^/ D
    8 V2 X% ?- B6 m* z+ w* f
    ' Y0 Z: @  P" B3 w( k
    w 8 A3 z: b; N5 R" }) e
    mn0 @" l8 T& r5 c/ q2 ^/ J6 R

    $ I. }5 ^3 r; |0 \: w. D (h 7 F2 ]. D, c' H* R- P
    im
    8 Q8 D( U- m- X' w$ W( R# {
    , _4 O/ Y0 @9 o& ~: k% I −h
    2 Y" ]& d) P6 v! U2 Pin# W' |, Q. ]% M2 t

    $ ?% f4 S+ Z) }& @ )
    : k- [0 V, d; e0 f% v2  j8 M7 i; i0 A1 F3 Z
    =
    3 F# d0 V4 d* S( |∣A
    + X7 |! U* u( x  D1 W* ni
    , R7 x1 E2 z5 U1 y! V
    - X# j: a/ C5 t4 D! P' |; }0 z5 s5 ^2 U% w3 e2 H1 M
    cut(A
    - |( Q* j7 ?/ A* ]& hi
    ; C/ C' h$ R# i& X  A% ?" {7 j- ]9 s. W0 b7 d! Z  Y( V
    ,
    3 }( z  H! I" l9 }  ~: P7 ?1 TA
    + I+ T5 A! L3 k6 v& u& ~8 Mˉ9 j; `. ~; h4 R8 A2 U

    : \( Q; ~" b* O% Ni
    0 u& H# [0 _9 r" o+ k$ M- c  u) s) |+ B# Q. h) N
    )# R% G: M3 J! E* R. `) e
    0 J3 Q- b/ r5 S8 c. Z4 b" X# Z/ e. J! M

    " S/ ^: e% n+ y) w) O; @+ @# q2 j+ N& ~0 O, ]
    严格证明过程请看刘建平博客:链接+ J! C# Z4 C. v  ]2 R* X  L
    可以看到,对于某一个子图i ii,R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h 1 e0 Z' K9 H/ D. _
    i
      D/ N# k3 \5 G& m: nT
    6 I; n% \( [1 G8 |* ]& y; [3 w% U& N% O' ~( `% l7 B
    Lh / g. z; k* r7 I1 Z# ]
    i
    6 f7 A5 O( y3 m; o1 s! H( ]  o: g6 B
    ,那么对于k kk个子图
    ' y3 _/ d3 g; e) t+ J! i1 ]3 S/ e7 T: i% a6 H
    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)' {; V; L, C$ r" \
    RatioCut(A
    7 Y+ q2 f  d- \: i- U0 z1
    1 `' @& ]# w& j. @7 s& v' x6 u7 u( i' z8 Z% c
    ,A 9 a" I) ~5 h. o+ {- U4 Q/ x
    2
    ; g9 Z, W& J+ S; m) h
      P5 v8 L5 H5 E' V ,...,A
      P# z  t' |" ~  u( v4 P4 nk
    " A2 r% W, s! \; M2 H' c* @+ v2 y. t- w) g% p6 v8 T5 e' Y! q
    )=
    + k0 D0 T8 R/ Y- c) x5 t$ Xi=1* j0 c/ F9 g2 r: ]4 r0 O
    ) N/ x" e5 r  Q/ K( ^
    k6 M$ V; a  h. w1 S4 ~' L' J3 h

    + y7 d( S, g+ y8 ^# c! w h - b' h8 A, C; @
    i) D3 r* Y( S7 j8 T* a6 N
    T9 [8 o: P' g3 ]3 _' v6 ~- P
    * F% B! `% U- F& c
    Lh
    % f2 e+ {5 F! d2 di
    ; _' i% M. ]! S1 U. z% v# @% u+ s7 w8 B  j* y9 p
    =
    1 p: t9 T; ]. j* M& @9 ii=1
    3 _4 m- q2 P0 Y" W% k& l7 B; b+ }$ V2 r6 L  ?
    k; J& ^4 Q# _+ G2 K! T4 ]
    4 y  m7 |7 M1 O- m" L
    (H
    ; _8 c- \( F) ]& aT- S2 v. e' h+ i) ^& S# d% \+ y
    LH)
    # F8 ^" a1 q& r# ~ii
    2 b/ y! p, ^, v/ U. X, v$ H; Y# W( ?4 s
    =tr(H , Y7 h+ W& L8 e! s" C$ q
    T
    , E. T' n" d* k! S( R/ E LH)
    % u+ b3 E0 t3 l7 E; ?/ B- W+ Q- ?' @* U% J) M
    因此,R a t i o n C u t RationCutRationCut切图本质就是最小化t r ( H T L H ) tr(H^{T}LH)tr(H ( m- i) a  Z. R6 k
    T& y& F1 A4 m2 t) Z5 W: q
    LH)。又因为H T H = I H^{T}H=IH # ]( t# v4 v, Y' d4 e  K+ t. O
    T
      Y, J% `% |' b4 }' H5 J' s" }# ` H=I(单位矩阵),则切图优化目标为+ m8 i3 b: @; S' p

    - N# m7 Z' Y" |% {% q% [: g+ Xa 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( V; `  d) V/ J# R4 l
    H
    0 c# i* E9 z  t% largmin
    " |+ N: n; F' m, q( A" m# E' s$ U
    1 }! O; Q1 J/ k! j' {( i* j" Q: y- N! a# F) u% t0 `
    $ n' k* Q* y$ B3 W! Q! B4 a# u' s8 M- l
    tr(H , z8 A7 d& g9 e9 ~% a: |
    T
    5 U" Y0 ~  O$ I+ b  D LH)s.t.H
    ; x) N3 U: e+ }1 uT
    8 f8 D3 t. ]' H/ T4 s. F) f H=I
    + |: Y$ B. C/ d2 l* K
    . K( U  K! Y: U: ^2 y9 a4 n6 o: i对于优化目标t r ( H t L H ) tr(H^{t}LH)tr(H 9 {0 `$ h( R# ~7 s$ W: a* d5 H
    t0 M# D1 P4 B# Z. A" v5 j8 X5 r
    LH)中的每一个优化子目标h i T L h i h_{i}^{T}Lh_{i}h
    8 X* F# c' T3 i& _. Y) o2 Vi
    7 k: ?5 w0 G$ C4 LT  e2 K( ]# q7 D( H
    9 I$ t0 }1 S5 H
    Lh
    . S. Q9 D: O7 @2 N( v0 Li( `2 f( G; ~1 d8 |% `" j3 _9 V4 L7 ^, f
    6 U  p6 r# ?/ `! k$ @, m
    ,其中的h hh是单位正交基,L LL为对称矩阵,所以此时h i T L h i h_{i}^{T}Lh_{i}h % Q! P' W. c9 Q, W* c
    i' ?& d& r8 b* w* a# n7 I* k
    T2 `5 f6 Q/ [; k' E

    4 L4 A% A+ S* X* {+ q% l7 L Lh
    , [3 M. o. H7 y3 bi/ [% c0 P1 C& X3 v  q) I

    4 d+ H( X+ _4 A- U, z4 E5 H1 E8 c 的最大值即为L LL的最大特征值、最小值即为L LL的最小特征值。而在谱聚类中,我们的目标就是要找到目标的最小特征值,得到对应特征值向量,此时切图效果最佳。所以对于h i T L h i h_{i}^{T}Lh_{i}h
    . \; D- D; a' u: m# t- |+ a; S$ mi' a1 S; A5 n' G6 U
    T7 X- B7 M8 J* Q

    3 K+ e8 T4 D" h0 v1 b: X Lh
    9 ^$ ]0 w& j4 f* c6 o2 P. @4 E: ki
    + R- l1 ~- p3 l! s' h' g# f6 B
    + h1 N3 A! _- j8 w  M2 O! I" U ,目标就是找到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 4 k4 ^& A; y) `! v. i
    t$ R: |) K/ o0 I8 Q) M
    LH)= ! A, C. F) c7 t. g1 Z
    i=1
    . B6 Y; X" A$ f* U6 ^  z/ o5 u
    2 u8 _. g4 R$ Dk
    4 S! I% b; |9 x
    0 R* x; N% [, A) k- B h
      _: _1 e* n! ~+ V$ c, X: P$ _i
    # M# v! G  `4 _8 c5 R4 [% BT8 t1 Q7 A5 a* n, v' s* s0 I4 I# p

    % f* g8 u3 j# i; h) W$ b& H) D% U& r Lh , a2 G, a5 ?6 Z: [% Z+ o
    i7 [( V/ c  e5 e' }+ f

    0 P6 J+ h& t  G' s  [# B( i ,则目标就是要找到k kk个最小的特征值: X* J# P9 l6 w1 h3 Y! h; t( Q" F
    / C6 B9 {9 M; s, F# R
    因此,通过找到L LL的最小的k kk个特征值,可以得到对应的k kk个特征向量,这k kk特特征向量组成一个n nn×k kk维矩阵,也即H HH。一般需要对矩阵H HH按行做标准化,如下
    8 R; @# V+ K5 g0 o1 C5 m  |1 ?9 q3 D( p5 Z2 _& S( _2 ^
    一般来说,k kk远小于n nn,也就说进行了降维
    2 M% r* Z/ y. h) ]- {5 q3 s6 x$ k5 E2 th 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}}}
    ! Q2 N4 l2 ~5 \+ b* Eh
    / b+ Q# R5 k) ^& ~; N3 ~( o( H, {* y7 mij1 T; v& m1 m2 {

    ! @8 N+ i& R, E: C% K: s
    5 b  U8 A4 \4 U! b = 0 W8 K# E3 P) t6 \$ e  t5 f( M3 O
    (
    # a7 A. Z$ _" c: V7 {, `! yt=1% p& r7 k6 p' N) R  S& K) ^3 u

    " ]6 s; H# ^  z) X8 dk9 d/ G) {# H3 y( w
    1 a- K) z2 |' f+ K
    h . }; Z6 l! |+ I% ^
    it
    ' n" V3 E# s$ O1 m, h: ^( B$ g2
    0 m. F. F* ]5 h7 @, r# G
    , e$ b5 ]* f. D+ y3 \ ) / y5 k0 ^( a) w9 x
    2
    $ X* ]8 j0 y& {: p; Q6 t1
    2 v0 m4 S% I5 U. l/ e" t1 ?
    6 W' h- C7 K3 C, s8 m5 V  R; d/ o8 s
    ; P3 G, T% x# H" a9 |
    h
    ' }* S# J# L9 {ij+ m# g% a# o$ C3 h0 F$ O' W$ d

    # k! k. F1 H. K6 e
    * f& h, y  D9 x7 ^$ N  U
    . e4 W) g/ y- G5 D$ r  z' Q) b& t( y. o* E3 N* G

    ( L. @) p" d$ r这里需要注意,降维后导致得到的指示向量h hh对应的H HH现在并不能完全指示各样本的归属,因此一般在得到n × k n×kn×k维的矩阵H HH后还需要对每一行进行一次传统的聚类,比如使用K-Means聚类
    6 G/ |. [& U& D3 [# E# R
    9 |  L# t( p5 ~& [: g9 F1 |: b9 `(2)规范割(常用)
    ( z( ^9 ]9 `3 t8 U规范割和比例割类似,只是把比例割的分母∣ A i ∣ |A_{i}|∣A
    0 z" R1 M+ n2 Z) V9 r* \i2 O1 T8 N+ @! v. Z, y0 ?9 d" x
    ) Y; G7 u0 [4 @3 E, M" y6 g1 q
    ∣换成了v o l ( A i ) vol(A_{i})vol(A # ~6 N/ n' N% J; ^
    i; w- Y2 Z2 T6 P0 }& |. Y' U. K
    % d4 F! ?8 z& |: {
    ),定义指示向量h i j h_{ij}h
    ; ^2 _2 v3 r+ Y( m. i$ C$ Uij1 X& k% x$ _5 N. U
    1 R2 q8 q+ z2 w8 E
    如下3 Q0 r& E( ?2 z+ ~+ n, z" ^8 `
    . H$ M& J  G9 S. o
    h i j = { 0 , v i ∉ A j v o l ( A i ) , v i ∈ A j h_{ij}=2 z! E! |. x  x8 Z& d
    {0,vi∉Ajvol(Ai)−−−−−−√,vi∈Aj7 |9 z" q7 K8 L! \* k
    {0,vi∉Ajvol(Ai),vi∈Aj8 a) H7 W' ~0 w" X- v1 l7 k
    h
    : ?) ~! F$ E3 ^- H9 T- Qij3 o/ K3 ^5 L$ q& w

    " g- R& G5 z: F/ w8 X ={
    * s# Z* z! J& [( T' u0,v   O) I/ j5 l: z
    i: [, M. H: m' _' m: m
    0 {2 u; b" T6 i! |* M
    $ H# ?& _, g! Q% n
    /
    8 @' s" D9 r8 J0 q, [A 3 k) A" X" T% i
    j& y# s% x9 r* x0 S7 `
    4 x8 l8 |) }* g, i  ~* l  {

    7 u! v* L! ?9 E7 C1 lvol(A / N+ q" [& R, q, [! ^
    i1 q$ {$ V  W0 o# F
    & u- I' r( t( x7 ^3 }
    )" P' \2 b0 e  }9 _$ C" H8 a
    , T$ |+ T2 ^$ U4 V  I) J
    ,v / b& N$ I3 ^! g' W7 b3 E2 k
    i
    4 v3 W: j/ Y; d# _: X/ t( i7 _1 L% c$ I8 N$ }: ]2 X
    ∈A & R, C6 `7 p% {/ b% H4 M0 Q
    j
    & ]9 d. v; B7 w8 ^3 M# b0 g, `8 f+ g  E. n; O3 O/ e
    - C2 W2 k. V& y9 I$ }

    " c/ o9 V5 S+ a5 l$ c
    ( c' f# @$ g9 \) V' `$ k9 w
    2 R5 G% u0 ?6 S, W8 _5 E! `; d, ]于是,对于h i T L h i h_{i}^{T}Lh_{i}h + @3 x9 {) C% t2 L$ Y6 l
    i
    0 m- A8 g" S) k& k4 Z. w% [0 eT- ?  F7 D7 a* }3 _

      J& h/ V* R) h0 r+ j4 z( H8 K Lh
    ' C( u3 O* B4 r8 n9 L4 a2 e; ^i$ ?/ g; u$ D3 V" b+ H7 \7 t' B
    8 ~! ^+ v0 K) \$ B" K; |' |! K* c
    ,根据拉普拉斯矩阵性质可知
    9 L3 T. H7 T3 A5 N1 Q, w2 p* j% p1 n( n: [9 `
    对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
    8 d( y* D8 {- f$ U* b6 b+ [6 d" H1# a7 r3 j7 e* _
    & g% o# C2 t) Q& \6 q3 I$ w
    ,...,f
    , n: c% R+ s0 ]1 k* nn. x) f. q1 d7 R

    1 g  r) x* T8 J0 J# m- {4 m7 m )
    ) y- L8 m1 c5 D( b5 p3 WT& j1 o+ r( i2 q/ l- V
    ∈R
    9 E7 b% z, Y% b& U% Q9 @4 Fn7 }4 @5 e; i8 o3 O4 x
    ,有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 ( f, w% n' p/ o9 Y) p1 y! K
    T
    , F. y0 i$ T: X Lf= 3 e2 O( r( I% A' J# t! y
    2  t, W, q( s& T/ g( E! @
    1$ G* o4 l' g7 n& L
    + u2 N/ p' q5 L3 w
    , y! [. D# I+ S' S) u, r3 m7 y! V3 s
    i,j=1
    & T! _3 D8 o6 X4 T4 f4 t' `- E3 ^# n: R/ ~. f
    n
    & K/ z. r# z/ F& [' X2 l3 X5 G$ M8 e, }9 c, d: h4 p; L- p6 A7 O1 p
    w ; ~; o) z- g: a* l7 P% M+ k% T
    ij3 A% g: H' p# f: A; A# b" p
    $ T% N. f+ x& L. {7 ~/ G
    (f ! g& O( }$ R+ F$ e, }
    i
    7 j3 l$ @! r% w! k8 o! L% O' R7 U
    ( a' P) ~& v  m9 C −f
    % _( p% X* |/ G; u$ n! kj
    3 B$ p6 Y* y% q4 B/ L7 y; o9 z1 u, k. C
    )
    : Y5 h$ c6 H3 {" |22 `! \/ Q! P1 T" i) u! g: t' N4 R

    & x* m& {5 ]7 Y# g; I( G2 ^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})}
    6 K) L3 t7 f; X  y' {, i, qh
    ' \& X- H, o# W8 Wi
    ! i% x% B9 M* v+ d+ PT
    5 ^  H8 D1 ^( o3 M2 |: T6 P" H) f$ _, J2 k& I1 f7 y% _
    Lh 6 C$ d4 e# @/ {7 b6 p" y* ?
    i: y9 f, w* y7 U" Y/ o
    2 @. f& p* M2 m; Y+ D( X
    =
    6 J8 u$ k% m2 S8 E2
    1 c" _% w% T! `) P+ V1
    9 u8 J, S! _1 B1 G' L6 V1 d' O3 h9 a" o( }5 K5 h2 \
    # E) L6 b3 r: _4 M9 V4 W5 S
    m=1
    1 U1 K  B5 w# L. y( K0 r2 e
    8 S& r8 S2 j6 T6 `) d
    3 ]8 F* \8 d* j  Q/ ^
    6 M# Q" {5 s* D# xn=1
    6 I2 I% d! v& o
    % O: ~$ ]% a7 Z. A  j5 U- k- i0 F; z7 @
    w 2 L- u# R: U1 k8 \
    mn/ s; M& i, C* S$ S
    " n/ }/ d( n8 F, @7 ]1 L' }
    (h
    2 K2 }8 r% T' w6 t- _4 d( xim
    % n( I$ A6 ]/ j/ |4 c8 J8 ^* v1 c1 K8 ^  R% k
    −h
    % K  K- s2 B& T( F* ]# \in
    8 e1 o+ q: J( h( s& s$ W) i! M( F4 H! d" A0 e
    )
    3 M) h, i6 e! f2( G" e, }' ?; U: [* Z' X6 S; I
    =
      b  }. {* Q+ C2 u) V, w1 Lvol(A 7 r% t6 H2 _) y+ Q. w
    i
      B* l6 Z( @6 ~/ j# G* ?9 ~( }: n  v- H( z% S
    )
    ) ^! z/ l# u. \# E6 kcut(A
    ; N! B3 N$ C' ji
    ; _; f( t( t$ I$ G% O0 P9 F1 @7 A9 }
    " U3 }5 ]0 |& U* s- |) I3 o ,
    2 q# W* I! c& mA
    8 z, l$ `/ P* }6 P( L1 A& K8 i  Gˉ
    / B: H! m) j9 Y# t  _/ S# h4 j
    0 l. L; Z5 m" L5 l& v4 ki
    3 Q( w7 n- E, F# x. W. l0 u; ~: B. p  s! X  p
    )' V2 B% n0 ]0 t5 w% ]  S
    $ s2 G' r) D4 y7 M

    2 z4 A6 B3 }: J; K( B( y% {3 M5 L' ?1 P  C( S
    严格证明过程请看刘建平博客:链接
    $ M. i' ]$ g8 w4 U6 j7 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 % Y  I$ Y) C( p6 R: F6 o+ h/ [
    i: ?. @. s7 c6 {0 @
    T6 [. d" {' }* }  D4 C* N! h) n! R* s
    3 `# H- M0 j# m( I
    Lh 4 O3 j5 V& l6 s& N. e
    i8 ?% U5 J7 W$ b: m
    ( I# f: m8 U1 O$ g
    ,那么对于k kk个子图8 k2 Z7 }: Z3 D( m
    0 C* ^6 v5 v/ z% D; K  o
    N 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)) g# H8 p; W8 M/ P
    NCut(A ' ?8 }' E) @4 B9 i7 p* s0 L
    1
    & {- v9 z0 v, `8 f- I. a9 d7 n  l! P
    ,A : R, K5 k, n0 ^3 I2 p5 F0 @
    2
    + h: e9 t+ n* U- S+ i2 `$ G4 r
    ,...,A
    . @2 z5 F2 F8 T- \# e; e! Ok5 G, y6 J4 |# f% }7 [. @) ]
    + s5 r& ~6 T7 S8 N  D$ M
    )=
    ! S+ `' ]( ~6 r/ ^4 @i=1
    , ?; g, I! a0 H, v$ @  x# a: ]( P4 P# @+ `4 G
    k
    : g9 y/ m  i7 z* P+ F  @- ?" V/ H  X5 |0 I
    h 7 P9 C% h( a) W5 b" y* v
    i+ u; q) G$ M" t. b4 k
    T
    * d( ~6 m& i1 \  e; ~! k3 A/ b2 R% ^6 ]: ?( J
    Lh . b, u2 \, W. O, d( x7 P& e$ Q
    i
    2 ]1 P4 T1 U0 S& A1 T  Y1 @; ^
    # c4 i. x4 Q. g1 b) ^ =
    7 C9 L; T" k  g2 G) T) n2 w* S8 e3 qi=1
    5 Z% ^+ W! F6 U; P
    9 t% y; ?- p) mk
    4 [' I+ m( n: Z
    2 _5 N0 N2 n% l2 y4 ?2 q7 Q: r% I (H
    # x1 v% d9 ~) ZT
    4 Z5 g( D6 g+ \, W. J1 l LH)
    * z& F+ `8 v7 u. kii( b0 H: ?! D% }/ o! _$ z6 @

    3 G6 @- I, U. @9 E; t =tr(H 0 D, z  N# R+ U" f. \
    T
    3 r% R: u$ a- _- V6 f LH)
    3 S0 [7 B8 L* q- }$ b) p, S9 {$ l0 ?, J6 z9 g
    但此时H T H ≠ I H^{T}H \not=IH 9 @& w! j5 R* S$ G; Z. t8 |
    T7 M( K* V9 c1 m$ E4 d8 P% {2 T
    H( R/ ]- R4 W) O% J* a5 N& c3 _8 C4 O
    0 K7 f8 S4 ^# V9 S- m; M
    =I,而是H T D H = I H^{T}DH =IH
    6 m1 t4 d' u' [2 kT
    , s3 c' @, _# z: @. r DH=I
    : c: ~% r) N3 I% h3 w2 O& G5 z9 z  K6 }6 g% z/ R# ]+ h! v
    这是因为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 - r. z6 w1 y8 Y+ |# t8 S
    i4 ~: ^7 m% f; R7 N. ]& Z
    T( \( d8 t- Q  P7 g2 w* R' k1 |1 A
    + X- e) R8 d( z( [5 y. z8 s$ o: {
    Dh . u7 Z4 v( L6 u) l5 u) `
    i
    , L5 E8 \# I6 w# E
      l/ c1 n' _# V; n- M = " L" a- `& i& S- B9 C$ q$ i
    j=1
    ) P  s$ A% i3 H( M7 l& C* j" \0 p4 K0 W, ^! @. W+ m: a
    n
    2 T' n, M! G4 N6 O! W9 d
    : L0 Q9 J7 G- K( A- y, ^ h
    9 N6 y8 J& M- V/ a% s* n- p* Pij
    6 n, i2 H7 w/ u, `; u2
    + Q8 p. F* j" o( Y/ L$ b1 M, `; ]5 f
    d : S$ z- M' K9 ^! w0 K
    j9 A. C; n: z6 M* z" p& W7 l$ v% s- M! L
      S6 w! Y: z( F: M
    = ( b+ s6 a; B" \+ S/ c
    vol(A
    6 L. D+ g" O& T" x# U. W" Ji* F. H$ m; |- g0 l1 I& E, y7 F7 t
    4 |3 y- i) _2 Y5 h
    )4 ]6 N. f6 }3 r
    1
    9 W6 D+ s0 C! `9 n- W
    # k6 _% a$ W! D! t
    ( m! t% L7 ^' W9 L+ Q8 Kj∈A
      H. t! ~1 \4 u7 qi1 w! p4 [2 f9 z6 b4 y
    / i2 B) L8 t7 P

    : I2 Q2 Y" ~  f% R0 T/ K% G0 T7 m# `1 y  G! i

    6 ?. j: l9 v4 |# y2 r9 | d ( M) t* k1 C: g  Y0 q( p
    j
    ' Z: |) F: c# R: c" k% |9 Y# o' z. q* F" W% ~, t7 [
    =
    9 v3 n  E+ N2 P, o! ]$ N3 E2 e! Svol(A 3 [* f4 v1 X6 B! Z* R9 E
    i
    % h* ~# P2 X- B* K( l
    ; U. h+ ?0 A7 I7 M )& ?' p$ X7 M) n1 ~5 V
    16 M3 ?) ~4 [0 t) b+ v  w

    " M. c& B) ]4 M9 v4 }6 N) h5 x vol(A
    8 W2 j% x& Z& y4 j* Ni
    & F# U% e* t  i  v
      Z6 y8 P5 A# ]; d. s/ d; t )=1- c9 q/ C3 F/ @" x$ U
    因此,此时切图优化目标为& \: O3 X& z6 E5 m8 f$ v
    6 B( `2 w6 S: U6 Y" C
    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=I5 N* H0 g" ~* f; ~
    H/ l. N7 }% S7 g  i. E
    argmin
    2 M6 j% w8 o5 ]9 X+ y% @$ q; h" Z  e
    % j% R1 A0 J+ G( P

    # L( E7 [; D( x  ^ tr(H . m5 Q4 ~- l; z" V/ K  e. t
    T6 z" e$ h6 G( `: _' w6 ]
    LH)s.t.H + I1 q& F5 F  x& l) V8 Q
    T
    % ]& k4 H1 F0 j8 [6 j DH=I( y# D9 S6 X  W" Q, {
    ) q+ B% @5 A! M1 B2 l: d9 }1 t
    但是现在矩阵H HH中的指示向量h hh并不是标准正交基,所以需要对H HH做一定转换。令H = D − 1 2 F H=D^{-\frac{1}{2}}FH=D 6 `6 e: B$ g/ D' I

    ) K( m+ f, j! k' ^* w7 l2# u4 w2 G  Q- i" l  @) L
    10 B' e, ~' A; H; N' j8 ^

    : ]7 u" K+ p* i. e6 z/ f, |1 c; X4 N% c/ c& D
    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 4 `2 p4 M$ k# N. t6 c
    T
    ) v! T1 J0 x7 f: `3 n- m LH=F ! b2 }. k! o% l# ^6 p" }5 @
    T
    * r6 }2 _4 ^3 _5 @8 \1 | D 2 Q$ n, m. \7 I) T6 l" v0 ]- g/ _3 ?

    4 w( D% Y. S) \) |! y" H2, A  t$ O/ L+ T, d  W
    1
    6 I$ p9 a4 _" \+ x
    $ ^$ c8 L0 A  _; K* [7 j' G
    + o6 q9 y5 W0 S+ F$ W LD
    " [0 U" R# r9 O* q1 S# w# Z7 K
    : N# e/ y8 v0 Y0 c4 a# B3 _2
    ( F6 V7 Y. F& q* M, R+ ?- k1: E$ _: E( C* F5 T

    0 g+ \1 C+ `7 l% k2 j" R% O* B7 N2 m' H% D8 U- Q' ~
    F、H T D H = F T F = I H^{T}DH=F^{T}F=IH ; G' S& k% P. K2 q: v' C- }
    T
    " A" Z2 Q$ B! Z, s0 Y0 r5 ~ DH=F
    ! ?" U" b3 ?) F3 tT
    , S: S9 O2 R- S1 U9 _/ C' T& Y( Y F=I,于是优化目标变更为
    ) ]& w) D& h8 j! u. T* [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
    : Z9 j3 H/ G: f! Q  g2 @F
    $ g8 J5 p8 J0 w' aargmin
    * Q5 m( @" d! D( @
    ! d3 K$ R4 l( E8 ?6 h/ [' O5 L5 r' p. H! `* K
    ( w4 `# q4 m( }( v8 g5 ~
    tr(F
    ' {0 p4 e0 F9 L9 G3 L, c" A: aT
    ! T& j6 j& N" |% G- k D # g( J8 d8 I' L) f
    # Q+ @8 H( _$ `. l# I( ]. y
    2! n* m( c+ R0 L! F* G: I4 S1 l* b5 ]
    1
    - W1 W4 t3 P% c6 Y! T9 D
    ; Z  ^& D9 K& Z
    , c6 n# U; I4 n' B% O8 K4 z9 n+ v LD
    ' F& G. C7 v, r. _: R: [8 a8 _
    ) ^1 n9 p% G; Z( j3 S9 i5 }. i; b2* F- B# s* C- R' [
    1$ c8 ]7 Q; J; x0 s4 z# G4 j& F
    % h1 t. Z4 D4 p! p

      h7 Z" C; j2 a/ f F)s.t.F
    * w8 s/ s; b- KT
    * o6 J9 y( J' m. x& U F=I+ R, ]: e* E  c7 F6 s( {

    2 W$ ^6 k& B1 y/ L( y8 M- p# i现在,和比例割一样,通过找到D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
    7 x8 F7 x' H/ E5 _3 t( N" [" `3 M+ e  Y" @* Q/ {% o0 B
    2
    , X# @0 H" O, e* C( T) t& e" A, z1 a# N1' L6 ]; Q, x6 S! Y7 [; d
    + V8 r  q& Z% ^. A; \

    " ^2 L% h4 ~; P) G0 L LD 1 ~7 \, b9 n$ g7 I$ w8 Y4 e

    9 ?" y5 D. I. Q3 r( {( n, j: [  S2( i+ I2 T' [5 }% C$ d
    1' Y! ~' z1 n7 g8 |' H" u
      X. a  Y2 l0 L5 L% N  g6 C: n% x9 n; r
    . a- T; b! J) B& v
    (就是之前的L LL)的最小的k kk个特征值,可以得到对应的k kk个特征向量,这k kk特征向量组成一个n nn×k kk维矩阵,也即F FF,最后对F FF进行传统聚类3 t7 e" }# `8 v8 O

    0 I# u' S# D4 `0 `, V5 J, E9 ]一般来说,D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D 1 P9 J$ R* `3 O- _3 }- g; n5 y6 @/ @
    1 N6 N: A% q. o( E5 F
    2) O$ Z$ V! b/ J, M! y
    1
      O8 M3 k/ p3 @, J# }. K# o3 J. l- Y
    , Q  H2 M, F9 E
    LD * W: z: R; X. y4 O3 _8 s

    0 ?7 W0 [! _( j6 J. t2' L) g1 S, {( y! ~; Y
    1) n0 C7 p' _% t7 l: `4 y1 K
    0 P+ ]. L' v3 B0 d/ D6 j" d
    / \1 X2 N% ~- r, H; h5 C  |* ]1 D/ ^
    相当于对L LL做了一次标准化,也即L i j d i ∗ d j \frac{L_{ij}}{\sqrt{d_{i}*d_{j}}} 9 j) X+ `5 M" I* A
    d ) S! Q3 d2 T9 Z
    i2 M% s' d0 E+ w: z
    + [. w7 N5 U4 n3 ^* A% ]
    ∗d
    # x# K  E; N7 ^1 Q! yj
    - a. {& F9 A6 c# d$ {
    + H2 O9 l' m7 z2 h$ Q' n% b; z; s
    ( F5 [5 m* {5 `; t: G. J" W9 _, c4 F/ j! W7 h
    : q3 U7 l: E, S4 z5 Q; l6 y+ }
    L
    ; O& I# D2 P( U0 _- v0 i2 eij
    3 f  O, e. ]) v. w, P' ]3 C* a/ I) S

    0 _) [# W2 O7 s" b$ G0 `# g7 l( q8 H1 c1 P

    # p1 e, [8 R! G6 b二:谱聚类算法流程
    - r( C! W$ S6 J" P, l8 {9 E给定数据集D = { x 1 , x 2 , . . . , x n } D=\{x_{1}, x_{2}, ... , x_{n}\}D={x
    & C: v6 m6 n/ [( n; i1# X' B2 ?/ q: v, {/ W; B

    6 ?3 X! R  G) n2 X ,x ! b1 f0 ^4 G# Q1 {5 @
    2
    # v: J) `5 p& f: {2 u, ~* d
    4 G; f4 D! U$ p/ ~ ,...,x 6 ^6 a  S6 U2 d9 M5 p& p' j3 j  e
    n. s2 A1 W$ `  ~3 Q* D
    4 e7 |  V0 l* s, `0 O9 M9 [: z
    }
    4 p( v7 q+ [3 i3 i' c  w6 E, V% i5 \; T
    根据输入的相似矩阵生成方式(一般为高斯核函数)构建相似矩阵S SS(AffinityMatrix)! T9 S5 J/ I; `! j
    根据相似矩阵S SS构建邻接矩阵W WW,再构建度矩阵D DD( g2 ]1 D9 a( q9 c8 i- R
    计算拉普拉斯矩阵L = D − W L=D-WL=D−W
    # ?9 y: {" t* Z8 h4 T得到标准化后的拉普拉斯矩阵D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
    8 s8 G% k4 x. P: Y( ]( v! j# Z) ^. @/ C$ D; t
    2& F" h; t/ s* p
    1
    ; ]# H' j. R9 n0 L& w
    : S+ U) m9 a# W) g4 z: X/ [0 v
    3 V1 `: W: ~8 D7 i7 k2 l LD
      V1 L, R( K6 D, u! l
    ; f% F! C8 x: [) V2
    2 @9 O" F8 H, R& [! a  R+ }5 }# g18 ?/ w6 ?6 i2 Z3 q# W8 s6 S7 [9 G  W7 g& ^
    * I% _% u) J9 L/ v9 q
    " t% i$ [9 C/ d$ x' A. X. g
    . }& W/ f' i" Z* [: T
    计算D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D % R4 o% V: z, v+ T2 W' d' F

    3 W. Y/ ~3 V4 }5 ]2
    & \$ v, k  X& O. H/ D* I1
    7 X5 G# @1 ?/ A( p* u5 X( p4 [; Z9 t- J1 e3 n# \

    " o5 U9 P2 R4 P& v; }( m LD   S" `9 B) s+ H8 Y$ c5 j

    / i' r& D$ \9 [4 C6 P8 v0 u. e2: Q' {% n3 K5 b* k
    1
    ; B" D. ~2 ]; T' Q; _8 T! Y9 l+ [, A2 ]  G2 N! M  H
    0 `* x' q/ ?; s
    最小的k kk个特征值对应的特征向量f ff7 o, M" _1 c' J5 O& X( }0 h* D
    将特征向量f ff组成矩阵并按行标准化,最终组成n nn×k kk维的特征矩阵F FF
    & J; A: c7 x$ j0 G! DF FF中每一行作为一个k kk维的样本,共n nn个样本,采用某种聚类方法进行聚类,假设聚类维数为k 、 k^{、}k & r8 H2 k# ?3 x9 G
    " N6 ?. c4 k) N- j0 P: J8 V! ~' e
    8 C' R; d  |. J8 v+ x5 w
    得到簇划分C( c 1 , c 2 , . . . , c k 、 ) (c_{1}, c_{2}, ... , c_{k^{、}})(c 7 J' N0 i4 s$ `
    15 |, a, T1 e1 c/ h/ O. v

    $ s0 m' Z" B) y- B7 H6 D2 a ,c
    * X# [6 h! [# G6 Z" ^, R4 R28 ]9 ]+ _  a$ X, {) k4 X0 }
    " |" `4 [% k; k# ?- E) g
    ,...,c
    4 L3 R/ ~2 K% Z: R# qk
    0 e" u7 r+ T2 A( D1 @- |. D) [
    ! L$ k0 p4 U& A- H( h4 u
    / B6 D8 g+ {* Z( e+ |
    ( l" g  c% @% w$ |% ~6 `) z )
    : v) `- ~1 d4 F7 I' T三:Python实现3 w. q+ f- r4 s  e; k1 H! w
    import matplotlib.pyplot as plt
    0 A2 C* E- C, x2 b/ O" Pimport numpy as np
    1 q' [5 a# Y0 s$ d* o8 V8 @import pandas as pd
    " Z9 c8 ^7 P$ N4 M4 F7 P6 m' ^from sklearn.cluster import KMeans
    - ^- J3 N6 D2 V7 Z4 }from sklearn.metrics.pairwise import rbf_kernel1 v& x$ B3 P" M1 W, S/ C* q  X% H5 ~
    from sklearn.datasets import make_blobs
    ( e0 u" g" B* [% A, P* v7 `from sklearn.preprocessing import normalize3 @7 V$ I7 |" h0 J
    4 y' {* a4 B7 r
    def get_affinity_matrix(data_set):
      V  D9 i9 Y2 L: |    #  利用高斯核函数计算相似矩阵(全连接)
    $ _' M: \5 |/ a- {0 d    rbf = rbf_kernel(data_set)
    . R6 \0 p8 c" n    for i in range(len(rbf)):
    ' m: }1 \; O/ C7 d( J        rbf[i, i] = 0
    7 w: j$ r0 F$ P+ B: c, w* C7 i    return rbf- f# `! f5 ?, N7 |/ t! M
    # T- p4 O- P) }$ W$ ~% r6 b

    / A- i4 b, a% u$ E$ I$ Q- a. ]" B; ydef distance(x1, x2):
    ; \9 T7 ^5 ^4 W5 o1 c    """
    / t4 ]" i/ @% D# _) s    获得两个样本点之间的距离
    , X' ]$ T& @: {% z+ G    :param x1: 样本点10 U( O* `1 M" D% N; P
        :param x2: 样本点2
    # P% [! W4 Z; e9 X' l+ V1 o. H% U    :return:5 K# S' J! }* c' b2 F
        """
    - f/ T$ z* ]& E. E    dist = np.sqrt(np.power(x1-x2,2).sum())
    ) I, K6 u5 T- P+ H* E( r    return dist
    + V4 m! u9 M) e( G0 L4 A: n+ f$ f" u8 X
    def get_dist_matrix(data):9 E/ E  q9 g- S0 R
        """
    7 J5 R* w. ~; Z: r& W4 b' w. e    获取距离矩阵
    $ h6 M* v2 I% |    :param data: 样本集合. D" l- I" w. Q
        :return: 距离矩阵+ o. f4 O9 h& N+ a" C2 T
        """/ i3 E8 g3 O, e0 ^9 P
        n = len(data)  #样本总数, p7 `  g  Z/ w8 }3 J5 O
        dist_matrix = np.zeros((n, n)) # 初始化邻接矩阵为n×n的全0矩阵8 f% x( w* f6 l" Q0 y
        for i in range(n):
    7 b) H/ m# j# g$ C        for j in range(i+1, n):
    % H1 c) a2 _* }! v) {5 k  N            dist_matrix[j] = dist_matrix[j] = distance(data, data[j])
    & ~* g; w5 I, ?, K) d2 m8 E    return dist_matrix  p1 n: s- T& D0 X$ ?

    4 Q2 ~2 t6 V  T  s! a3 s" cdef get_W(data, k):7 H' A- B  }, k$ u; ^2 \2 @
        # 获取邻接矩阵(K邻近法)3 X/ u8 Q3 p( Y: z% j9 A. _' E' V
        n = len(data)
    6 u5 t/ H& I3 k' Y2 u- _5 w  J    dist_matrix = get_dist_matrix(data)
    / q' j  Z' m/ D! G! g$ z& Q- \4 A    W = np.zeros((n, n))0 o# i4 b$ Y8 G6 X9 v
        for idx, item in enumerate(dist_matrix):5 C' F$ K4 n) |% ^* S0 ^$ _, O3 e
            idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
    1 E9 C* ]# s" Q# Z        W[idx][idx_array[1:k+1]] = 1  e. Z3 [/ O: h' }" m; |  m6 x
        transpW =np.transpose(W)4 ?. ?# [" m! Q) i# R* h
        return (W+transpW)/2
      Y3 K$ E8 ]8 F& o. \1 J# R, q/ i  }, H) P
    def spectral_clustering(data_set, k):
    ( G; Y& T  W' l/ W- R. l' b/ v, X8 I7 r    # 利用相似矩阵S得到邻接矩阵W
    " I& r7 X5 X& B; I$ A# Y, N) v- Y    W = get_affinity_matrix(data_set)  #高斯核函数(全连接法); p/ E* {# ^5 a: U+ M' o
        #  W = get_W(data_set, k)  # K邻近法; @, L8 b+ y6 [
    # T) ~8 k. f) d
        # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵(便于计算拉普拉斯矩阵)( b5 L$ u+ v0 A& m, G( A
        D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
    ; P' s- T' H$ n- @7 g5 W; B+ B  F8 {  M& r( u5 h
        # 计算拉普拉斯矩阵L=D-W
      L1 \1 q0 o$ z1 L' f; W    # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
    ' k. u7 L" f: C7 i' ]    L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
    % a+ r8 g0 n4 K$ H
    0 x8 T" l# h) `5 g    # 得到特征值和特征向量1 y% y, c' w1 Y; I
        eigvals, eigvecs = np.linalg.eig(L)8 B5 ]0 h( n. [2 `/ I! N% _( W

    3 N! X) M. u0 ]    # 找到前k个最小的特征值(索引)! N+ I' l" o& Y6 J/ Z0 j. s( I  H; `& u
        k_smallest_eigvals_index = np.argsort(eigvals)[:k]
    1 [  m% e5 l2 q; j% E( r2 t  S, T
        # 取出这k小特征值对应的特征向量,并正则化/ r7 P' F4 W9 N$ T% j. V( E
        k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])6 t- r( V: G, c$ B  W( Z: e! S4 J

    5 B% _/ G5 p9 V0 |    # 使用K_Means聚类2 U+ h6 Q9 _7 y0 |* w
        return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)2 n2 d( }: k. P. X/ o1 K
    . v* g5 M: A! [1 H$ @6 |

    % H7 `7 j  a+ t7 `2 \2 _$ \; `$ j; ?raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)3 S# F+ l6 ^; L
    raw_data.columns = ['X', 'Y']( @: J. M8 Z' O9 |- j1 \" R5 }
    x_axis = 'X'0 y( L* Z# |" Z8 l! r0 Y0 U  w* _
    y_axis = 'Y'
    2 l  J) y7 d0 L, o% \$ f% t& d" i( b3 p9 L3 v4 O. T' w
    examples_num = raw_data.shape[0]9 B/ X, H7 ~" H9 m
    train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
    7 B* l; f- u, P, [1 a& e) T! o" ^( u: M" Z* [
    , t: @. y' N' X( r$ i6 r6 A- s
    min_vals = train_data.min(0)
    / D1 n/ d# p$ H+ {" T' f( V3 vmax_vals = train_data.max(0)9 @& ^" \4 l- a5 N
    ranges = max_vals - min_vals
    2 i7 k4 R) n- ]$ O0 H6 Wnormal_data = np.zeros(np.shape(train_data))
    0 o% R! G2 W2 R- h5 S/ ^nums = train_data.shape[0]7 h& I5 X9 j+ ~9 b
    normal_data = train_data - np.tile(min_vals, (nums, 1))
    6 f" \  [9 K0 l. b/ b0 Rnormal_data = normal_data / np.tile(ranges, (nums, 1))
    . [# {# R( w$ b$ D  d' _7 R1 S9 N+ l( A. Y9 p
    labels = spectral_clustering(normal_data, 2)
    " s4 R( Y  `/ ^! d
    " a* }% b# y' K+ b# 原数据! z* o" G9 L, t. U
    fig, (ax0, ax1) = plt.subplots(ncols=2)
    7 F7 u1 `" k* p, t* E) tax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')0 {5 r/ F3 B, ]- B( G- s+ i
    ax0.set_title('raw data')# L0 }0 \# T0 D6 v
    # 谱聚类结果
    + v  z4 }+ B0 dax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
    : w3 n0 g1 [& ?, n/ Aax1.set_title('Spectral Clustering')
    4 P5 H$ S8 `  K  |. O" M. z5 J: }! V
    plt.show()
    ; S7 I( w- l, ?3 U  |7 V& v% G3 m8 h4 M! W
    1( v- O0 }' k7 T! x2 x; M
    23 ^! `, r% z* K; y& Q  q
    35 y" D! g( F* K0 c9 e- q/ _, s
    4
    + C' c* ]/ X/ L+ l* ~4 o4 K& L53 Q' b, u/ O6 x2 I, v) a
    6  `. i6 _" o. Z. a
    7
    9 E( O' C8 A% e0 n7 }% W  P8
    0 f! ~- M0 ~1 ?1 V! U1 E90 t3 Z0 d9 [4 h( o. M* b
    10
    # d, z# h  V* {! ~# M+ ^- r3 R$ e111 j% D/ K- ]1 F1 [1 H: ~2 X" a
    122 B3 q1 r& b! F' c
    13  z1 ?) Q! s( p  \
    14* Q5 e- V+ u$ T6 m# v7 x. ~
    15$ D5 E6 [8 o9 E! O
    16
    4 ], }) n2 m  Q+ G8 Q) `3 h4 }3 T8 l17
    . F# l/ k5 @$ h7 e! D! ^0 z: e18
    - E# a; g$ M, Q, w" g9 s6 o8 b19, Q7 k8 Q# R6 g" D
    20
    8 F* e& g( t# r214 H3 K) j9 @6 e$ O7 B
    22
    6 `) ^2 \3 e4 \( S  G8 L  E# O5 G0 V23+ [) A2 s  o: n0 l6 X" N
    24
    * S0 I0 ~1 {1 k$ a254 [* `: q2 ]& T( p: t
    26
    " @" d1 a( Y- t$ Q& N* i/ i272 l6 m8 k2 [2 @* c, B
    28
    ! n- J" l3 c" X) F0 g29
    & r* S$ E4 x7 {9 f$ [5 \30
    ; N* y) K; `( y1 W$ s$ G, @& s0 k31) M& {. ?% Z8 m3 ^9 b
    32
    . [5 z( C: B8 T: X5 T33
    6 e; }; t( |( |# M" h! f34
    2 R1 u$ }6 @5 B) s7 F6 F) \354 G/ Z! [: Z1 K9 \# s
    365 d1 m3 u4 t, B) P8 T
    37
    / r% A8 t% Y9 u4 T" U- x. n38
    ) Z4 O( g9 }* Q+ }- m39/ t2 B. H, x# ?/ n; `# v  H) R
    40# m9 U4 ~8 k$ n: v% P& x! ~# M
    41
    - G6 e. P3 `  T: A1 v' {42
    " l4 Z& x) M8 Y0 M. K43
    / y- l5 n* t6 K- D44
    & C8 Z: g, S/ \1 d% T. \45  B& v& e  R" @, V0 W+ u' v
    460 I+ D' j$ v& e( c
    47
    * u$ @' ?% ^5 A1 a: K- |48
    . v. u4 S  H# h& b0 N49
    + k8 ]; Z4 v3 u) S; {9 R50
    ( Y  J* @2 P; I( ?6 h) [51
    ' V3 S& W* B  \1 ]52- v( T( r; F( W% u9 C# O* h
    53( N+ U9 b5 ]1 Z7 t# Y
    54
    - a9 t! ?% B4 W3 P" D" a& x557 \7 m5 J" {. J0 X  a. R( }
    56: R, F$ c6 g2 x3 n7 V6 [. }
    576 d8 g% S- ?, G3 m: r* u
    58' H: M: l; a5 }, `; t
    59
    0 @; |. i  o- Q( R: I7 |60
    . V6 R4 J/ i7 c0 i$ Q: a4 a61
      J' p. |5 ^& i1 \  E62
    8 z: l! S! c. y& ]& B637 C4 H6 r( \& o. a  ]
    64
    9 ^8 A& g/ i/ `5 S  E65/ j* l- [1 K- d1 U8 K0 N- ]
    660 T4 E; ]' s+ B
    67
    2 o/ h! c$ _6 V68
    ' X. y  _* Q1 }0 `: @& ]4 D+ G69
    # h& f( k5 O1 t6 Q+ J) b7 [: l70
    ; _% e* M& b9 H& X718 k3 a$ ~* n$ p
    723 C; o6 T7 R, i5 v6 u
    73! c3 n, W6 J' M4 _( f) W, L; ?
    74
    & ^& f2 G" M( R750 O4 i4 c0 G% u5 k: L
    76% Z6 K/ ^' i. H+ F' b
    77
    : d6 G; ?7 W+ ]! e# Y' M/ N, f3 J787 o& a/ r# S( q1 N& H6 z* \
    79) q# R9 I5 J) S# v9 W1 F1 M
    80
    ! m( ?: V3 Y4 o81
    3 o) J9 ^+ x4 y9 n. O9 \$ E824 ?  `4 e# C, b/ W4 B
    83
    9 U& b, x+ ^! f7 i, _+ R5 J84
      Q; P& L7 V% \( \85, s* u, D2 |# U) ]9 r! Y
    86" X2 l9 F: @/ m! W$ x0 _3 ?* A2 H0 a
    87
    : J8 N" L( V3 q: i6 Z; T88' t' }' m1 y8 @- E; [0 n& F* s# J  g
    89' ^; A! B4 w+ @% w( j2 f% c6 Y* A
    90
    : c  m9 ]) |% I7 Z91* |4 N+ T! O+ o. h1 S; C2 w9 F
    92( G/ U3 z1 l- O3 W; Q! G$ I
    93
    / }9 d2 G' C* W+ E; r! ^$ ?+ I947 q' G+ r2 P( e: ]2 k# o, N
    95
      W& z( Z# r, \96% K8 D$ O. i+ I7 f
    973 X3 i: r( s( F3 |
    98
    ' o! W- u+ _- ?- O0 p99
    ) d4 n& j1 k1 b) y: l& ]$ _- z100
    , W- ~3 a3 U- o1 a: f6 V101
    1 @$ M, ^0 {0 g7 T$ K: ]* E* m, r102
    9 t5 U, R9 c9 c7 N103
    7 h, H& \. {$ N8 S9 |5 G(高斯核函数). p; |9 w9 C, [7 I+ g" |

    : S: W$ h* j  d9 b( J* h/ d7 K& e* d# H! a+ w0 F+ V
    (K邻近法)' ^, ]# ~( p8 ~. L% P$ I- n
    * v( T& @/ ^' `6 u

    1 i, L$ q& k$ o四:谱聚类算法优缺点+ \  b2 `: ^( v* F. A% x
    (1)优点& F) i% g' v+ g- Z6 ?
    谱聚类只需要数据之间的相似度矩阵,所以对于稀疏数据的聚类很有效
    # r" ]9 s2 ]: {  c! z/ q9 z& `使用了降维,因此处理高纬数据聚类时复杂度要明显低于传统聚类算法$ ]  e5 g. `6 R. Y# A" i. v
    谱聚类算法建立在谱图理论基础上,与传统聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解
      v  I7 \: A& R. C$ V) n( }(2)缺点5 f/ l, q$ G6 Q$ a' [
    如果最终聚类的维度非常高,则由于降维的幅度不够,导致算法的运行速度和最后效果都不是很好
    ' G% E' ~, d4 r9 O聚类效果依赖于相似度矩阵,所以不同的相似度矩阵得到的最终聚类效果大不同相同
    * A! {+ I7 Z; d. @& S————————————————
    2 m. t, d# b& ?版权声明:本文为CSDN博主「快乐江湖」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    $ i* K8 ]3 W/ O" r原文链接:https://blog.csdn.net/qq_39183034/article/details/126747494
    " k6 m5 h! E6 O9 e9 d2 V# S4 j2 b' }, U$ c1 q3 }' R+ O
    6 N' `1 b0 g, X" p, E$ C# `
    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 03:27 , Processed in 0.725498 second(s), 51 queries .

    回顶部