查看: 3029|回复: 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])# F0 v1 m4 {% g( w
return dist_matrix- s6 h4 H5 U. ?3 B

  R+ w2 m0 Y+ i: M0 [def get_W(data, k):& R* |  X1 z% W3 B
# 获取邻接矩阵（K邻近法）5 L0 q- A7 D0 s
n = len(data)
/ [; ]3 t' C9 J4 [: ?' {6 j6 \- P; ^ dist_matrix = get_dist_matrix(data)
1 K; ]% ]9 Q( j, Q5 \ W = np.zeros((n, n))9 E" ]! p) P: T0 w  `! H5 |1 k0 f
for idx, item in enumerate(dist_matrix):0 U# h9 z& l8 \; e0 d+ @- D7 K
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
4 Y. G& N: F$ E       W[idx][idx_array[1:k+1]] = 1
7 x% p0 _" T4 D transpW =np.transpose(W)
5 U, T4 e+ t5 \9 g* U% \ return (W+transpW)/2
; S7 t! `: q; |  _6 ]# F/ G( c$ v# ?% \2 n( ^- n+ o- J' T
def spectral_clustering(data_set, k):
3 i0 W8 a5 n5 \ # 利用相似矩阵S得到邻接矩阵W
9 ]; F( Y3 }1 |2 R W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
  \8 R. M5 K. g5 c/ V, P #  W = get_W(data_set, k)  # K邻近法" l  q: h3 _+ E! b+ E5 P- Z
& b3 j1 I! U! \' h2 A* W1 y
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）1 C- k3 _% B- `$ o1 g6 j! d
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))0 Q; L) _( V" R

0 r/ s# ^9 F& h5 A! K# E& P3 W+ h0 {% a # 计算拉普拉斯矩阵L=D-W
" {' |) F9 _  H5 @ # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv6 I( F% ?7 R5 c" v: m
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)' `+ o& ^  b& ^) p$ i# H! U
0 o  G, _2 V0 O+ o9 {. b8 l
# 得到特征值和特征向量1 d* t' _4 y9 j: M
eigvals, eigvecs = np.linalg.eig(L)
2 N& J3 w2 W& T" G" b4 g
7 L+ N: C. |! S2 I( R: _3 E# F0 ?% q # 找到前k个最小的特征值（索引）
* k$ R0 ~' A) G# H& J k_smallest_eigvals_index = np.argsort(eigvals)[:k]& y+ Y& b, Q0 [

9 s* \1 Y( g$ j3 v1 Y: W/ Q0 a # 取出这k小特征值对应的特征向量，并正则化( s; e% J* j/ v" z
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])# y6 r2 k5 f; @0 Z% P6 n6 J' u+ V
7 k1 A; Q9 P- F
# 使用K_Means聚类, \" w! ?) m: h
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)/ u7 y2 V% Q2 k- G/ N3 T2 _$ y

' d, Y4 P* t' l+ L2 ]4 ^! C
4 W; v8 Z: [% _: Braw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
' M+ s' w: E6 B! I& C, braw_data.columns = ['X', 'Y']
9 t9 F; O! {) `/ ^% E( qx_axis = 'X'2 K6 q: ~" b5 Q8 F+ E7 w
y_axis = 'Y'% e" J1 n1 v  a
, V" \8 g0 d: H) I6 Y  r0 }& f" ?
examples_num = raw_data.shape[0]
4 }+ `" a: O# J3 D% Jtrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
3 ^4 C! N: o2 A$ `7 Q& F/ z) ]9 s( I* J

( n3 b; L! I' E* Q0 bmin_vals = train_data.min(0)' `+ Q" u% _2 y8 P! `
max_vals = train_data.max(0)
3 B9 C' R- w8 Z* F3 T& }ranges = max_vals - min_vals
2 f8 y/ w: Q+ l; t( Dnormal_data = np.zeros(np.shape(train_data))
9 i0 h) m1 y( Q/ N3 Mnums = train_data.shape[0]
4 q* f' h& ^( D9 I$ c, fnormal_data = train_data - np.tile(min_vals, (nums, 1)), Y  A" D4 P; E( d% S) ^* H5 N
normal_data = normal_data / np.tile(ranges, (nums, 1))7 j% s2 _, B' O

3 g6 U/ s% v, Glabels = spectral_clustering(normal_data, 2)* \9 }# O- c+ m: l. c4 f9 t2 P

6 H8 U1 t! Q  Q# 原数据
7 s9 c1 D2 F. ]3 pfig, (ax0, ax1) = plt.subplots(ncols=2)  O) [8 p: a" J9 B0 T( j: [: F
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
7 N& H2 R" O' B$ k$ Xax0.set_title('raw data')
; `* R) x/ F6 N# 谱聚类结果  d* q/ }3 r. H2 G$ b) s
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
: w# G$ W. @) W. M0 D- ~ax1.set_title('Spectral Clustering')
5 j; H: s5 F- [8 {% i4 t! `! ^3 @5 w
plt.show()
/ B. o- h9 y+ W1 K
( W9 f5 K$ n% _1" b2 j: |! E  d7 P: C! B, ~3 r# V
2
. l8 }4 O' L) }: c( `- M8 q- U3: i! f* P  h4 q' G- z, d7 a
4
' G, `) H5 I* J5
3 Q9 t" b" u7 n7 t5 i! [6
# V) t) D1 a$ R9 o7
3 ^  k, J4 r* s+ j) n" W2 C8
, v: t/ d9 c: g9% C) p: E/ H2 v
105 O7 g+ v8 O# M6 Q2 y# F
11; K4 R4 u5 P( a, |
12
+ P: j3 M( a# @) `4 S137 u% S/ q5 b  t
14- C$ n' f" U2 g7 ^3 X
15' X8 W! o3 c1 }9 u
16- |. y) ]0 [& E9 \9 C4 e
174 o$ m6 O( K( M) i0 v7 }  q
18
' A* W3 G* P) |1 a* T& P193 t9 W$ d5 t9 h8 c
20
1 R) z) i* {( R" |& y3 A' J211 c! c8 {8 w# U
22% O- c+ z1 w, r6 {
23) B+ D" }+ H  ^0 d! m& ~
24+ v5 _- K1 t* ?) G
25. w9 K( Y& n* d( D6 C6 ~
268 @/ y5 U: R, o4 K
27
' Q. q+ e. O' S280 w, ?' Y; O; L4 H4 w' s3 ^
29# h: m9 g) X5 A5 U% c% g0 |' h9 b
301 H) o: i2 D* t. g3 G! k6 _5 X
31
! T5 Y$ I( M* k2 g/ }; E7 F32
$ r& h# J) W" {, z3 D1 T33
5 e; ?5 \* y% e8 x) C7 |/ k; V34
) T& h4 b8 E9 F4 ~$ ]% |, C35
% f4 y2 w: Z. Q! n* ^% s36, m' B7 L2 y3 U1 x9 f
37
3 ~( P7 b. O- T1 \( L& I38
8 \1 t" @4 a, C/ ?/ T8 n39
4 [1 C" X, y3 o5 S40& J( U8 l5 X$ U8 d2 r- r
41
( t" N, L4 ?0 }! n1 K" l. l42
7 q- [# D& p: ?43
9 S' M1 B2 ?1 ~" k0 g6 c44/ W1 k8 e4 F) ~5 q7 I# X4 n4 h+ z
454 g' g( F, W+ ]2 J6 m
463 w' E: W% `0 B/ \3 X
47
- I" o* e: s# ^7 ~7 t48
+ V( J" z3 v1 U7 U3 q7 n, y49
4 X% o' V: ~: i8 n2 D4 H" Z6 E50& x5 N. E) R" L, s3 B" H3 m
51
' M0 q  K9 _* q' b524 n1 M; h0 m  X7 i, |# Z
53
5 k' ?, B$ J' Y54. Y! m& q! f- C
55( t! U% {/ \! }- k3 N, Y
560 j2 |7 H+ g& g. U6 S+ l2 @3 S
57; H' y, L0 Z& b- M3 G) t
58; Z0 K' @( y2 Z- ?! }9 w: I
59" K* v3 ^% X3 ~2 N
60- ^/ \8 U: A: E6 y0 a" K
61$ p& T# {' y) n% q. g6 x5 x
62* L: r4 K5 h5 l: T
63
4 }: A3 T- J* v0 z. K5 C+ |64
( d3 N& ^0 r8 @65, @0 Q* k" h( ?8 v5 O/ y
66
- D, @" {( ^1 j67
$ i8 \8 f6 l( {1 V* r68- H; i. Q7 \2 q% H7 t
69% Z5 M* q3 z3 X! E3 P4 B# j1 a
70! Q  \5 \- J9 l3 Y
71
8 P# X4 k4 P3 u72$ t1 {3 y, y# H! z
73
/ V' M4 ?$ [  H/ a& }5 Q7 H74: x% T8 N# w# t9 E$ ^
750 i0 D) _% }+ T  ~0 |+ A1 _3 D6 D
76
- B7 V7 i) N$ ^0 ~779 S9 C) S; y0 ]1 n# f1 r
78% f" v& C, e3 j( B. T0 B
79: p2 B% x8 H) v7 O
80+ d& g: Q# w& g2 m/ j, ^5 h
81
, t: a! Y% ]- [) \82
# |5 @( B) K& C8 g' \9 Y5 \83
- r& D- q# h- {- n4 d: I# H$ l+ \6 d84
: a( H4 j8 C/ k7 l; W85
0 E  C/ m# @3 B( H- h" @86
% f+ N& @7 t5 [! S9 t: g7 o! e87
3 g! v0 g* s% X( T88
) `/ r! U" \9 E4 i( f4 W89+ M( L8 r- S8 E% P3 y( d
902 ?5 S. Z$ b  T: p$ |3 F+ d- E2 q
91
: D$ \6 _$ H; ^# c, N5 @1 ]9 a) v% X924 h3 X/ z- F0 ]
938 v) T* `2 Q# W
942 @3 q  x& }- e2 j% X9 F: q
95
0 k. _0 }# Z( }& |7 K1 }96+ ~! T; T/ S5 Z* v
97
2 _/ ~7 H. g3 ]98
6 G( H# F# }3 K' d990 a" h7 X0 P/ ~! X  ^; c. |
100$ ]# n, I) _& Z- w- ]8 `/ X
1015 ^2 S1 i/ a1 ]4 g' S
102
: f$ E5 _6 q% w2 _4 e/ E103
/ l1 i4 X: I1 X' f& ~（高斯核函数）' A8 d' ?* [7 {  ?$ E5 B" n4 i
0 X) [. u, ^& T8 C
9 J/ o1 G5 V( E
（K邻近法）, P  m; m) |  o; Q
0 ^+ J1 W8 t" f2 [
+ q# |) h5 r3 H( ^1 T
四：谱聚类算法优缺点
7 J6 s- l% ~4 J  @9 @（1）优点- Z- u# i0 r8 j& M7 [+ W
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
& N# L" U/ R  S! r4 ]使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法( }4 S' I; a6 l2 Q9 f, J) u
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
/ R) M/ O3 w% o* p3 `2 a. D（2）缺点
) R, ?( m% i- G7 h/ \+ `如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
( T6 N- j5 K% h  D聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同, p2 h- @: d% E4 ^
————————————————& b( [  T4 t" B3 j: F* }
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ b  a, v3 f5 Y  F# o/ S. s原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494: s1 E6 p$ C9 o

  Z5 P7 i+ n8 d( f' T) x3 u, B4 M, e% V