查看: 2954|回复: 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])- e+ E) ]& w( e) f7 \- {: f# y% e
return dist_matrix
) O' S$ E  o+ O) f- `# _; T& Z4 z! ^* g* c0 M* G& P2 U8 \5 t
def get_W(data, k):
( V& q  o. m6 S8 }4 ]3 N3 j # 获取邻接矩阵（K邻近法）4 e& D1 T; j$ o! a( [
n = len(data)" o$ B% V7 q- h
dist_matrix = get_dist_matrix(data)& s8 l- s/ A) E3 f) j8 h! @* k
W = np.zeros((n, n))
8 u! m, C0 l1 h1 E5 z for idx, item in enumerate(dist_matrix):
. Q1 Z$ ~) f3 k       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表8 B* J( P& E% V( [" `
      W[idx][idx_array[1:k+1]] = 1. y0 |- j' H& Z+ g% u$ s
transpW =np.transpose(W)
  X! _1 h9 w0 ?  o return (W+transpW)/2
! z( W. Q4 t# Y9 c6 F, j+ W& k7 C, m
def spectral_clustering(data_set, k):6 B* v  X+ o- N* e! j
# 利用相似矩阵S得到邻接矩阵W
! O: P0 O. C; g! f W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
9 n0 u3 p2 c: i( ^ #  W = get_W(data_set, k)  # K邻近法
1 p; D& ^: Q) L  w" o) z5 e
) P! R6 w) ?9 o: p# W # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）: h9 m0 I, b/ Z
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
" f4 y6 @) d  U& V- V; x
# 计算拉普拉斯矩阵L=D-W
1 D; M, H- i  ~6 y/ T # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv3 a* {4 Y5 x- ^; D" t/ d# C$ w$ P" a
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)1 d* t8 w6 Q6 [, A# z7 E9 N
( q! h+ `) |3 P% x7 B0 f, g' V
# 得到特征值和特征向量6 M: Y% y* c/ e3 k% e
eigvals, eigvecs = np.linalg.eig(L)
9 |3 O# x/ n4 x5 S; `8 W: q! s* F  G- p7 `  n6 p" G. X
# 找到前k个最小的特征值（索引）1 Z4 T" q5 g% e/ \: N$ n1 R
k_smallest_eigvals_index = np.argsort(eigvals)[:k]5 ^5 y8 D) F. s4 K) }. p

) k% }+ k: ]& V! r, l # 取出这k小特征值对应的特征向量，并正则化
3 P. ~; T0 D: {7 g k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
, t' ?1 {5 R  e0 x1 T* q( S$ d( X4 M' O% ^6 }3 Q% {6 q& n- V: z
# 使用K_Means聚类
$ l0 z; l3 Q6 k' v" y9 z return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)9 k+ H1 V9 X  z' e) e2 J3 R0 A9 f

5 G% b* e& S$ R& h- z5 Q5 z- n  s( E' W* K$ l3 k# f
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
1 s" A$ _/ [. ~5 p* k) |raw_data.columns = ['X', 'Y']
/ P5 J3 }" n2 }# s1 k5 q& Tx_axis = 'X'
, r# f/ S' {# }. }* Ay_axis = 'Y'
1 X$ J0 ]' X: Z! `0 O
3 c0 }" e! ?0 e' k2 `examples_num = raw_data.shape[0]1 J" v3 H  H1 x! w" `6 `4 i1 @) @
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2): M2 O7 ?! f7 ]/ D, _3 t

7 e1 g: G! o! b8 t/ R8 C2 E$ B% Q" _3 N, K
min_vals = train_data.min(0)) ^3 ]+ w& m  |7 `) _1 A$ P- c
max_vals = train_data.max(0)
) g4 U0 k! d' `( a* D' K" X$ Franges = max_vals - min_vals3 f5 f- I; T5 z7 L$ n: E' y
normal_data = np.zeros(np.shape(train_data))
% c2 i  e9 F& w: \nums = train_data.shape[0]
2 Z3 H% ]- d4 U, F% {" T+ |  Mnormal_data = train_data - np.tile(min_vals, (nums, 1))! F4 J" J, u; G6 w' L3 Q# k# }
normal_data = normal_data / np.tile(ranges, (nums, 1))
" G: T9 y3 Z$ ~4 Y/ V0 O/ i  P5 I! ^. E- b! N7 ^* W5 }
labels = spectral_clustering(normal_data, 2)& O& D# i. M0 c$ l

8 Q* B' }5 _6 B! Y; n% A# 原数据& j3 s3 O6 K2 D4 n3 s1 N( U
fig, (ax0, ax1) = plt.subplots(ncols=2)
4 x' g6 t$ n. l6 t5 Vax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
+ Y' Y" L$ l2 m3 B6 ]ax0.set_title('raw data')$ ]# s4 P: f- U3 G! D" r. @
# 谱聚类结果6 E1 N! ]# A( U$ r1 S, P* A/ Y5 n1 f
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
3 u& J* V: p8 R: Vax1.set_title('Spectral Clustering')
0 _' ]  P; q" b7 A0 S
" X* ]" A8 x9 i3 w% @1 F* wplt.show()
3 p& D: J8 W/ \  S$ C/ W5 C) z9 r) y; p, E  e
1
5 Q: E! }) ]7 `0 Q$ U& k2
( P1 v& `9 Q2 Q8 A31 t! X: K( E- _: b
4
8 n; ]( k+ _1 a) W1 L56 X) l$ y" d! A- q  }/ E
60 I7 B" Z( a' a
7' j. y) C8 i4 F: `/ i
8
$ X) O% o! \; B4 y$ _9, D6 @- ]: j" H6 z& v/ Z5 o
10
. \, K8 O0 \0 B$ w$ h" T11
5 a! P# t% R/ \( ~124 r* [5 i0 V6 F! o9 f1 z/ }
13
- C) Z# \6 H6 s, r14
4 e  P6 s) p7 y& A! h% @154 a; \; ^2 b& |( I: n5 t
16
( V' X6 g6 |, Z4 r- k17& R- g. l: u5 a( W5 \
18( Z' G* g6 B! R; F
19; Y2 h$ t! T7 G' ]' H3 U) r! e
20" S: I5 U. ~$ _1 l* a: z* L
21' {- S$ K2 K# w, {" U
22" {1 Z( o5 F5 o( ^
238 V7 s5 z2 A4 T" b( d4 H- c
246 t0 p! H! S1 M$ h
25
! v% ]0 ^$ J6 U1 \1 d; g260 v4 r$ G# J1 g2 r/ P1 ~( g
27  c0 f  e# r6 t+ q4 M
28
0 ~0 v! f; u. {! M$ X29
; z2 Y, a  z% {0 O- {; o. \30! X0 x; R$ m  s9 l% x5 Q
31+ J5 ?! a8 S3 t2 G) F- e" |4 d* {
32
: f) o3 q$ M7 m- g% ~9 L33  O  Q- a  u- h1 R0 O) O
34  Y( t7 j* r2 \2 w  ?9 _: A2 ^
351 {/ |2 u: s; s" Y
36
3 A8 u4 u1 P) F37
7 c6 r1 Q: H7 |0 U384 @5 ^; {1 H: l/ G9 m& d
39
  h4 Z1 ~6 G7 M/ A2 H9 c% l405 P( d& q  `& P- h1 y5 E' ]
410 S+ Y* f; i' b- e
42, }6 p' E# y% |2 Y+ N
43
! q- I: F; T: q5 X44, Q* q+ s8 @& A' H3 i
45
8 P* m8 p/ M9 w! I, f466 _4 A* d2 U7 P% X" l8 ~
473 K1 {) d4 Y" G2 e( K9 |
48. W8 q, @! P$ |# N% C$ R
49
: L' Q. d2 d2 Z3 x% w+ ~( x50
/ P2 k4 U# @4 P( }" F51
5 F- ]% N/ G' C: U# \8 Q& }( D528 v. X& j& \7 @' `
53
$ F' {4 h5 c2 m; r' I8 F54  E  }) F, w$ Z0 m
55; u% P; y4 {! H  H. W# D! ^2 W- g
56
0 `* ^6 g' p. h4 s0 B6 y4 w4 b57
# I: H' ^* [- x6 v2 J" W/ {58
+ X. E- L+ q5 j4 h59
& e1 ~5 S% m, G, A8 S60
- O* a! U: k' b/ Y61/ q# _0 |( k: b# L, y( a0 @6 W& ~
62
5 V/ B3 m) [6 Z8 C630 L9 w, D+ u7 z2 r' v/ e
64
/ o- `" u  S2 K65/ N9 y' b/ T  `) ?6 P  h" S
66
; P) v# x) s; F% i8 \* V67( C3 Z8 h! r" _! N! w
68
9 u# p, A6 Y' C& I3 O& m693 I: D  I6 ~' L2 }1 |+ `2 \- P4 h" F: l
70/ P  M: d! R* h8 U- c/ L
71
0 A/ J/ }8 ]; }/ b6 d72
  l& C8 }1 `2 O8 t4 q5 g' W732 M+ I5 A3 v& n/ ^+ O& E
74
5 n: ]. l- p) }75" O0 V% W% ?# b8 A4 O
76# k. V) X2 U/ g. G0 f0 Z
773 Q: Y0 O; S* _  I
780 O$ _9 L% b9 t8 O
79$ |" H% j. W; v1 K, C2 k
80
  `: _  ]+ A. E- A/ U" G81
, f8 E6 m# x2 N. w& {% e% o82" G, G! D$ U' N. j" ?5 z, N
83
5 q% R% U5 [  e4 N" ^" `( h/ _84% u& ?* A8 u! e. X. H7 F% H
854 I! h  r2 l3 j$ \4 C# U
86  i) g4 p+ ?8 e3 c; h' z
879 V3 X$ ?* g8 r; y- p& m( h
88
# l9 F6 u! w2 W9 I1 G89
* n, B; a" `. o$ Z6 e8 r90
  c# D+ w( {6 d6 f( g% y- g91
, k& S0 h  [* H; Z928 s4 U' [1 Z- x% Y3 T+ l/ w
93
: j$ w4 L7 S  P9 s8 x94: l3 Z4 k$ f- T1 L& F' _2 |% [
951 o+ D" [0 Y$ `4 `% H
961 V5 A, X3 e; [" M
977 y( R, E/ E1 U3 H6 b
98
+ }4 _9 H9 z& X6 |99$ O+ Y6 v+ G- d/ _6 n9 e0 S% v( W
100  q2 I2 j! Y5 p
101
. {" [4 I8 Y+ c9 q102
9 Y" @0 e/ F, V" G1033 _$ `/ D5 I; J! E) o
（高斯核函数）5 D6 c& E( ?) j0 k' S
, S# W: _4 j# F$ X. s8 @

9 K9 e4 G) K3 S（K邻近法）5 i' ?: d7 v4 q; m

% m+ o4 E5 E: Y$ r' c, w! j. O% P, a# z2 }" X. L9 u
四：谱聚类算法优缺点
: g' G, L- U8 D" c; w（1）优点
5 {: t9 v) R/ E谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效1 ~( d% z  r5 k& z- I3 _2 t( T
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
  O% d/ J; e% O1 J1 e谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
2 x2 i7 V  t: H2 {（2）缺点& X1 X8 u8 z8 Z
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好! }8 U* s8 t' u" F7 p' c/ ]5 J
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同4 r: ?) |9 e8 |
————————————————
  U) Q2 T3 D' W0 `* v! I, P5 @版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。" [0 S( _) a' x- g0 x( |: V2 e
原文链接：https://blog.csdn.net/qq_39183034/article/details/1267474942 R) P& F# i4 \+ b

( q: b0 s; Q7 Q0 _1 n9 o+ v6 ^  y3 P2 A4 X( C3 q$ b8 ~