查看: 3008|回复: 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）比例割
（2）规范割（常用）
二：谱聚类算法流程
三：Python实现
四：谱聚类算法优缺点
（1）优点
（2）缺点
一：谱聚类与图划分
无向图切图：谱聚类算法根据数据点之间的相似度将数据点划分到不同簇中，因此将数据点映射到无向图之后，可以转化为图划分的问题。对于无向图G GG，切图的目标是将图G ( V , E ) G(V,E)G(V,E)切分成互相无连接k kk个子图，其中

每个子图点的集合为{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
1

,A
2

,...,A
k

}，且满足A i ∩ A j = ∅ A_{i}\cap A_{j}=\emptyA
i

∩A
j

=∅、A 1 ∪ A 2 ∪ . . . ∪ A k = V A_{1}\cup A_{2}\cup ... \cup A_{k}=VA
1

∪A
2

∪...∪A
k

=V
对于任意两个子图点的集合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)=
i∈A,j∈B
∑

w
ij

对于k kk个子图点的集合{ A 1 , A 2 , . . . , A k } \{A_{1},A_{2},...,A_{k}\}{A
1

,A
2

,...,A
k

}，定义切图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
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

W(A
i

,
A
ˉ

i

) （其中A ˉ i \bar A_{i}
A
ˉ

i

为A i A_{i}A
i

的补集）
可以看出，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
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

W(A
i

,
A
ˉ

i

)在划分子图时并没有考虑每个子图中节点的个数。所以在某些情况下，最小化c u t ( A 1 , A 2 , . . . , A k ) cut(A_{1},A_{2},...,A_{k})cut(A
1

,A
2

,...,A
k

)可能会把一个数据点或是很少数据点看做一个子图，导致子图划分结果不平衡

例如下图，选择一个权重最小的边缘的点，比如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
1

,A
2

,...,A
k

)但是却不是最优的切图

为了解决这个问题，会引入一些正则化方法。最常用的两种方法为比例割和规范割

比例割：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
1

,A
2

,...,A
k

)=
2
1

i=1
∑
k

∣A
i

∣
W(A
i

,
A
ˉ

i

)

规范割：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

,A
2

,...,A
k

)=
2
1

i=1
∑
k

vol(A
i

)
W(A
i

,
A
ˉ

i

)

（1）比例割
引入指示向量（点击可查看指示向量定义）h j ∈ { h 1 , h 2 , . . . , h k } h_{j}\in\{h_{1},h_{2},...,h_{k}\}h
j

∈{h
1

,h
2

,...,h
k

}，j = 1 , 2 , . . . , k j=1,2,...,kj=1,2,...,k。对于任意一个向量h j h_{j}h
j

，它是一个n nn维向量（n nn表示样本数），定义h i j h_{ij}h
ij

如下

h i j = { 0 ， v i ∉ A j ∣ A j ∣ ， v i ∈ A j h_{ij}=
{0，vi∉Aj|Aj|−−−√，vi∈Aj
{0，vi∉Aj|Aj|，vi∈Aj
h
ij

={
0，v
i

∈
/
A
j

∣A
j

∣

，v
i

∈A
j

于是，对于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，根据拉普拉斯矩阵性质可知

对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
1

,...,f
n

)
T
∈R
n
，有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
T
Lf=
2
1

i,j=1
∑
n

w
ij

(f
i

−f
j

)
2

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}|}
h
i
T

Lh
i

=
2
1

m=1
∑

n=1
∑

w
mn

(h
im

−h
in

)
2
=
∣A
i

∣
cut(A
i

,
A
ˉ

i

)

严格证明过程请看刘建平博客：链接
可以看到，对于某一个子图i ii，R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，那么对于k kk个子图

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)
RatioCut(A
1

,A
2

,...,A
k

)=
i=1
∑
k

h
i
T

Lh
i

=
i=1
∑
k

(H
T
LH)
ii

=tr(H
T
LH)

因此，R a t i o n C u t RationCutRationCut切图本质就是最小化t r ( H T L H ) tr(H^{T}LH)tr(H
T
LH)。又因为H T H = I H^{T}H=IH
T
H=I（单位矩阵），则切图优化目标为

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
H
argmin

tr(H
T
LH)s.t.H
T
H=I

对于优化目标t r ( H t L H ) tr(H^{t}LH)tr(H
t
LH)中的每一个优化子目标h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，其中的h hh是单位正交基，L LL为对称矩阵，所以此时h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

的最大值即为L LL的最大特征值、最小值即为L LL的最小特征值。而在谱聚类中，我们的目标就是要找到目标的最小特征值，得到对应特征值向量，此时切图效果最佳。所以对于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，目标就是找到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
t
LH)=
i=1
∑
k

h
i
T

Lh
i

，则目标就是要找到k kk个最小的特征值

因此，通过找到L LL的最小的k kk个特征值，可以得到对应的k kk个特征向量，这k kk特特征向量组成一个n nn×k kk维矩阵，也即H HH。一般需要对矩阵H HH按行做标准化，如下

一般来说，k kk远小于n nn，也就说进行了降维
h 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}}}
h
ij
∗

=
(
t=1
∑
k

h
it
2

)
2
1

h
ij

这里需要注意，降维后导致得到的指示向量h hh对应的H HH现在并不能完全指示各样本的归属，因此一般在得到n × k n×kn×k维的矩阵H HH后还需要对每一行进行一次传统的聚类，比如使用K-Means聚类

（2）规范割（常用）
规范割和比例割类似，只是把比例割的分母∣ A i ∣ |A_{i}|∣A
i

∣换成了v o l ( A i ) vol(A_{i})vol(A
i

)，定义指示向量h i j h_{ij}h
ij

如下

h i j = { 0 ， v i ∉ A j v o l ( A i ) ， v i ∈ A j h_{ij}=
{0，vi∉Ajvol(Ai)−−−−−−√，vi∈Aj
{0，vi∉Ajvol(Ai)，vi∈Aj
h
ij

={
0，v
i

∈
/
A
j

vol(A
i

)

，v
i

∈A
j

于是，对于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，根据拉普拉斯矩阵性质可知

对于任意向量f = ( f 1 , . . . , f n ) T ∈ R n f=(f_{1},...,f_{n})^{T} \in R^{n}f=(f
1

,...,f
n

)
T
∈R
n
，有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
T
Lf=
2
1

i,j=1
∑
n

w
ij

(f
i

−f
j

)
2

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})}
h
i
T

Lh
i

=
2
1

m=1
∑

n=1
∑

w
mn

(h
im

−h
in

)
2
=
vol(A
i

)
cut(A
i

,
A
ˉ

i

)

严格证明过程请看刘建平博客：链接
可以看到，对于某一个子图i ii，R a t i o n C u t RationCutRationCut就对应于h i T L h i h_{i}^{T}Lh_{i}h
i
T

Lh
i

，那么对于k kk个子图

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)
NCut(A
1

,A
2

,...,A
k

)=
i=1
∑
k

h
i
T

Lh
i

=
i=1
∑
k

(H
T
LH)
ii

=tr(H
T
LH)

但此时H T H ≠ I H^{T}H \not=IH
T
H

=I，而是H T D H = I H^{T}DH =IH
T
DH=I

这是因为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
i
T

Dh
i

=
j=1
∑
n

h
ij
2

d
j

=
vol(A
i

)
1

j∈A
i

∑

d
j

=
vol(A
i

)
1

vol(A
i

)=1
因此，此时切图优化目标为

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
H
argmin

tr(H
T
LH)s.t.H
T
DH=I

但是现在矩阵H HH中的指示向量h hh并不是标准正交基，所以需要对H HH做一定转换。令H = D − 1 2 F H=D^{-\frac{1}{2}}FH=D
−
2
1

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
T
LH=F
T
D
−
2
1

LD
−
2
1

F、H T D H = F T F = I H^{T}DH=F^{T}F=IH
T
DH=F
T
F=I，于是优化目标变更为
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
F
argmin

tr(F
T
D
−
2
1

LD
−
2
1

F)s.t.F
T
F=I

现在，和比例割一样，通过找到D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

（就是之前的L LL）的最小的k kk个特征值，可以得到对应的k kk个特征向量，这k kk特征向量组成一个n nn×k kk维矩阵，也即F FF，最后对F FF进行传统聚类

一般来说，D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

相当于对L LL做了一次标准化，也即L i j d i ∗ d j \frac{L_{ij}}{\sqrt{d_{i}*d_{j}}}
d
i

∗d
j

L
ij

二：谱聚类算法流程
给定数据集D = { x 1 , x 2 , . . . , x n } D=\{x_{1}, x_{2}, ... , x_{n}\}D={x
1

,x
2

,...,x
n

}

根据输入的相似矩阵生成方式（一般为高斯核函数）构建相似矩阵S SS（AffinityMatrix）
根据相似矩阵S SS构建邻接矩阵W WW，再构建度矩阵D DD
计算拉普拉斯矩阵L = D − W L=D-WL=D−W
得到标准化后的拉普拉斯矩阵D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

计算D − 1 2 L D − 1 2 D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D
−
2
1

LD
−
2
1

最小的k kk个特征值对应的特征向量f ff
将特征向量f ff组成矩阵并按行标准化，最终组成n nn×k kk维的特征矩阵F FF
F FF中每一行作为一个k kk维的样本，共n nn个样本，采用某种聚类方法进行聚类，假设聚类维数为k 、 k^{、}k
、

得到簇划分C( c 1 , c 2 , . . . , c k 、 ) (c_{1}, c_{2}, ... , c_{k^{、}})(c
1

,c
2

,...,c
k
、

)
三：Python实现
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import rbf_kernel
from sklearn.datasets import make_blobs
from sklearn.preprocessing import normalize

def get_affinity_matrix(data_set):
#  利用高斯核函数计算相似矩阵(全连接)
rbf = rbf_kernel(data_set)
for i in range(len(rbf)):
      rbf[i, i] = 0
return rbf

def distance(x1, x2):
"""
获得两个样本点之间的距离
:param x1: 样本点1
:param x2: 样本点2
:return:
"""
dist = np.sqrt(np.power(x1-x2,2).sum())
return dist

def get_dist_matrix(data):
"""
获取距离矩阵
:param data: 样本集合
:return: 距离矩阵
"""
n = len(data)  #样本总数
dist_matrix = np.zeros((n, n)) # 初始化邻接矩阵为n×n的全0矩阵
for i in range(n):
      for j in range(i+1, n):
         dist_matrix[j] = dist_matrix[j] = distance(data, data[j])5 b3 h& |* H; }1 G& F& {0 T
return dist_matrix3 A3 F4 R5 L# v% e6 X

4 `! n+ y& C+ A9 i! sdef get_W(data, k):
' n- D6 |; a" g1 l$ t( _1 k # 获取邻接矩阵（K邻近法）, @+ b0 P- u  G6 L
n = len(data)3 o; F' q4 f3 a% l4 j) x
dist_matrix = get_dist_matrix(data)
1 V' I& o* n) C+ {$ w W = np.zeros((n, n))- j- ~' K" F3 }6 Y' I$ p
for idx, item in enumerate(dist_matrix):( V8 H% V% l# M+ i5 Y
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表( ]6 ^5 _# O5 `8 v+ a  {' B
      W[idx][idx_array[1:k+1]] = 1" f2 F+ T9 h7 v8 f: S
transpW =np.transpose(W)
$ R6 ?! f! [+ S return (W+transpW)/2
6 M2 ]% ^2 I5 l7 g; @  d0 v/ Q: K. b) S' P2 A/ g
def spectral_clustering(data_set, k):
/ e! u5 n. H+ O7 j6 V # 利用相似矩阵S得到邻接矩阵W
) c$ a# Z2 K! Q  J W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）% I0 Q! w) K) ~
#  W = get_W(data_set, k)  # K邻近法% a# L8 ^0 v6 E
, Z* q5 b  m' s
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）% m2 R. E: ]& B7 z
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))- d0 h4 `2 W9 l% R& p

/ ~6 A7 ~# Y; n, a. ^1 S # 计算拉普拉斯矩阵L=D-W; \" L" V; m: r8 W" I, t+ ]4 A
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
; z0 r9 J/ B0 k" k' [0 k$ e( p L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)1 d/ |6 d! B- ?: i& _1 [3 S; F9 Y
3 k- x/ V- d% N. {- e
# 得到特征值和特征向量
- `4 H4 U1 D! E0 ^ eigvals, eigvecs = np.linalg.eig(L)
% \! D8 z/ J* O# w4 H6 H7 D+ l# b! j# c: y7 z; l9 [0 I
# 找到前k个最小的特征值（索引）4 h9 h1 v, Z$ Q! e3 h1 ?
k_smallest_eigvals_index = np.argsort(eigvals)[:k]3 @9 r- R7 |* Z# v9 ?" W0 Y4 C
, N( o& C( l  m9 ?% n
# 取出这k小特征值对应的特征向量，并正则化
4 P1 u' g; V  ~$ ~+ T( p k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
; r& X7 f3 Q  s- }4 X. ^9 T# k+ q
; L9 w! m7 H4 r5 I4 j # 使用K_Means聚类
" X( Q' [* }0 n& {; k! F1 g return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)7 N% S' Z  \6 F, r) P, b

0 h: d" K1 I! t. T* y
1 ^! t9 E  _! D: B$ F, {- h) x# Draw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
, e/ b/ e% B# l& ^' Z# D, D5 Draw_data.columns = ['X', 'Y']0 u" \+ ^6 h( O) K9 `4 P( g1 I
x_axis = 'X'0 b- @8 `, S: R8 v& J+ ]  K
y_axis = 'Y'
: p0 i1 k! Q# r1 W/ K; v5 j- W  w6 i' W  \3 |* n# @
examples_num = raw_data.shape[0]
0 }8 S; m! }0 l) I; ytrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
3 O" V5 {# u9 m# [  v$ o3 o# n  B1 n# G' [
  c5 I8 G; j% Z0 X% I  R
min_vals = train_data.min(0)
+ Q+ r6 m, }- @! i) Zmax_vals = train_data.max(0)
+ F# d/ f8 s& ?5 c) W1 xranges = max_vals - min_vals
2 N/ w% _3 X* s( w2 Jnormal_data = np.zeros(np.shape(train_data))$ W) ?$ ]3 D7 C
nums = train_data.shape[0]
% R' C4 o1 T# {; P' c5 Mnormal_data = train_data - np.tile(min_vals, (nums, 1))
6 s* z- w2 h6 k8 ?4 [6 m, v- L3 snormal_data = normal_data / np.tile(ranges, (nums, 1))
2 ?+ r. `: L/ o8 m0 Q* t3 [) {9 {
) d* P4 A/ h' t* l& [4 g( Nlabels = spectral_clustering(normal_data, 2)- A; o0 k3 E6 v, N$ ]) G
, m2 {6 q+ {' C3 R4 D, U) ~
# 原数据1 I9 z; W% v$ o/ `# v' A6 l  O
fig, (ax0, ax1) = plt.subplots(ncols=2)4 [; k, I3 V6 R3 Z& l8 J, q. ?
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
: u7 D2 Q6 g* f# S5 a- H: F* s" ~* a5 aax0.set_title('raw data')
4 f+ Y( t: {4 t& \; V# 谱聚类结果
7 V, u' M% q! _/ `* R$ ]. z) T6 Jax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)* j0 o  o6 [6 l6 X/ d6 p
ax1.set_title('Spectral Clustering')
. U+ l1 U! H: N
" A. S& M9 q3 m( xplt.show()* `3 l, J8 c' W

8 K/ B8 i! I2 h& I8 u5 p) a6 z1
% |: |) k+ j- y8 U5 b3 x# E26 o# j" g# d; n7 e
3; w, P) w5 }) K* m
4
9 }- T# d9 I7 S: E: V5) ?  \9 Z' P+ K4 n! u
6
2 n- j, H6 \& P' n, i; n7
7 k/ N* L2 j; J/ E& n: \7 g" e85 y* J$ `, j! Y6 k( j) R
9
- s1 \$ T9 }0 b7 N. \10
: I" m5 e* }5 b/ W, H9 r11: m; f+ V4 I" Q
12
6 B6 M% [2 l7 A  V" T) M$ Y13: H" K4 x3 n/ ?+ W: z9 i
145 G- ]/ O! ~' \
15! r. w! I: C. ]% Z1 ]( `
16
- w2 }$ n3 I  O) v179 @5 c& ?8 j' l. q
18; D. M6 l0 Q% n1 w- }$ D. T) {) p
19
# R# K6 U. Z5 p0 a20
4 }0 s9 Q! a% T% Z- u21) P7 N; u$ b" H
225 x, |$ _6 X+ p1 C; g
23  L# Q- J4 u* G5 O+ |) w
24; {  u. P' h% ]$ \* c& z
25& H: s1 @6 x& K5 w% _2 R
263 ^: s( z6 `$ v7 p
27
! f4 t2 w" I$ W28
8 T+ `7 J: z+ U6 c, b$ X29
/ B5 |* E6 m$ X% O! v30
3 p  ?( e. R. V  F" a31) u: K# {& p( I- q4 S% z7 D
32
' c6 K/ F* M9 S* h33
5 ^1 T- z" M8 t2 g) o34
  I1 t6 d: o) \/ X5 A35
/ V* j" ]9 ]6 T36
- e+ h. ?0 o/ V1 C* c  I2 r37
9 F" p( r$ `0 T8 [: o38( i0 R. i6 ^! o( ?
39; Q8 L5 O3 s) }
40
: _: s9 {, F+ z5 r6 J41
; d8 c( V; Z8 s" E" s/ B8 p# a422 W8 P9 x, e3 X  V' b
43
# n& w! q/ a" R1 c5 K. l44% @6 M  S) V9 b% O/ ^$ R+ U' H3 T
45
+ o! J1 b( B4 V/ Q" q9 {  Y# c46
( E6 M7 k8 u) S% T9 Y: U47- i# o% q1 K+ E4 x
48! [8 J3 |& {+ r% P) T& D) e$ l0 O6 Y; n
49, `' f" r: J$ k
50
* [% `" W$ s& x$ I6 A$ n  g( E) Q51
% l# |: a, q2 p" f1 S  s52( u7 ^7 w8 T  O" \+ ?% F% @0 Z
53* i, G3 j# C( k7 e
540 i: E, `+ F3 F' u
55
4 q/ I; E4 p2 p( Z) w* _56/ z% N# I, P4 E( x
57
% _% Q- A+ `) o. z7 o( m0 j58
! j1 ^' `0 r, G" C59
, s1 E+ r  j5 g/ p( Z60
) A) e% X; {; @1 e1 [: [61! s6 g7 Q9 o" ^" p! }" _
62
) `" J7 J2 z- r8 K$ N+ B/ }637 X1 i* r2 ~- i2 f0 f* @' s, U+ o
64
3 v, C6 C+ t, X5 i6 t4 c- s65/ I% J4 K* w7 x/ L0 P9 ~
66
" ?$ `+ O' i2 J67
& G/ z, w, w! H9 y/ d3 {# {# u68
7 M. ?" A) o: e. y( u: ]! E69; G0 |  \- n$ f6 i, q2 m
70+ ]- `" p3 [- i' N: [) _% \
71
# N, f. {, l/ {# D8 H; [8 V72
/ k1 y- E: p/ x3 L$ l730 V- G% ]( [9 {* h" d, Y& I
74
; I  {: G3 O' Z; W  X& E0 _4 n75
# f9 V. K+ Z' i& J2 L8 @) K9 E76
7 j. X6 N, v% r& x3 |- g77
8 B3 T# }% c% Y+ A0 o7 s3 M8 E8 C78! T5 J6 N4 F3 o  K8 K! }+ V( x: p
79' b9 s9 j. d1 {/ O9 T. H/ x  G3 E
80- k5 D# H0 p1 R! h) V0 i$ B) ?
815 ^/ D9 N( M  R
82
: V0 M0 H" l  s6 n+ Z83
* x9 H% G, e& J* s# @847 }) H5 D6 Z" h+ b- s+ _5 Z
85+ }9 E  r4 V4 Q2 h* {, E* l! y& W
86/ a! a2 I0 \, B1 p0 H" m+ H
871 l6 I  K! k+ p* _$ K
88
5 T3 s# I5 @7 q6 R  J894 c2 T6 m; e2 I/ F$ s) e1 q
90
, |5 l' e( ~$ s91, D! H1 V: u4 x& R
92
6 _% f6 @% @0 y$ r; y  V, k932 b( R1 P) b/ N
94
4 A, L/ c1 H4 k95; S  j" `  A! q
963 L5 Q* y7 r4 O/ Z
97& Y8 k  g. `* ^1 O) n
98  Y* D4 u1 @  r0 ^8 o1 Q/ H
99
8 D! l5 N. h  [: V7 f8 c0 K5 l100
) ^( U4 k) U, T101
9 z8 g7 |) @" b3 b- P- Q, D102
" q1 j( n$ y- U& w. g103) P& T" t8 W. J
（高斯核函数）, D  d0 Y5 X- `. ?( e1 w9 j

4 I9 m7 t( x0 G+ f8 w8 }. C
; x+ V! [8 Z8 ?+ r2 A3 ~（K邻近法）3 F' Z/ i! r0 t8 ~7 F1 V. l1 N8 S

  y2 t: X9 U+ g! k- F: v% q. U: D+ ~0 W8 @0 f- ^
四：谱聚类算法优缺点
# \* C: M( U/ G; s（1）优点, o% s' v; g8 Z) m2 U
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
6 q+ K( ?2 s* J1 j使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法% M/ H/ H, S. ~! e7 ^+ C
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
: f0 P% l: u$ K（2）缺点
4 x2 H6 n9 Q6 c6 q3 A如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好  L% k; ]3 _$ g7 x9 T4 X0 C! U2 d8 q
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
8 w7 Z; i7 q1 [& f* `+ }————————————————" w4 X0 W* n3 s. F2 @( N9 _" f
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。! H! \+ f, {! Q3 ]2 }) S% n
原文链接：https://blog.csdn.net/qq_39183034/article/details/1267474947 Q* F& R5 y* L6 ^* f* j7 ]6 g
* U0 ^* r6 q# K* f
9 Q5 G, Q! r' }