查看: 2940|回复: 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: J7 e# A) f return dist_matrix
1 W! M3 C$ b# W# z/ D& s( M5 b. S; b. {9 X( v5 J- `
def get_W(data, k):
' L3 x7 O( Z, s # 获取邻接矩阵（K邻近法）3 |0 J3 ^' f' w* n
n = len(data)& U; h) H! _/ w" c/ j  K( n
dist_matrix = get_dist_matrix(data)
; b! x2 ^* h4 K% N4 j; E W = np.zeros((n, n))
8 c+ e9 H0 F3 P$ b for idx, item in enumerate(dist_matrix):- u  P  p* P' {& ]  S! f* X/ M' d
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
( f8 n: V0 |$ F       W[idx][idx_array[1:k+1]] = 1
; L! k8 B' l* o7 j& m& Y transpW =np.transpose(W)
# Y* o+ b  H7 P% Q+ j+ A7 j* b return (W+transpW)/21 F/ W) B' _5 Z0 X5 n  F9 c

, N7 o% h8 n+ ~def spectral_clustering(data_set, k):6 t& ?7 l$ L4 q& k( V7 t
# 利用相似矩阵S得到邻接矩阵W
: ^4 ~* [' {5 k& \9 E4 V W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
4 t/ A4 _' m2 }) q #  W = get_W(data_set, k)  # K邻近法0 d' ^1 {, D" h
0 A$ U6 _; b4 {
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
. {& i* K0 j5 a0 {/ m+ t3 ? D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))7 S7 f) j' a2 D

7 V3 K' s8 X- G9 Q7 d. e # 计算拉普拉斯矩阵L=D-W
, N& o  w7 Z; H # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
5 _. \, q+ _! ~1 a( {0 W/ \ L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)5 G- E  J) @! J5 z- ^
3 _' C4 m4 A5 E1 ]6 }2 z' Y3 J- ]
# 得到特征值和特征向量
- {/ P* q4 m- @4 u eigvals, eigvecs = np.linalg.eig(L)
7 n+ Z: s4 L6 a- C& u. `( ?  s3 p
# 找到前k个最小的特征值（索引）
8 o( P; E/ X! p; |/ C k_smallest_eigvals_index = np.argsort(eigvals)[:k]
1 a0 v, d- T. E$ E7 p9 E$ l* k  m7 m) Q1 z0 @* m  f
# 取出这k小特征值对应的特征向量，并正则化  V1 O0 ^! i) T0 p
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index]); z2 A. p6 U- x- h

' g8 C  @  S  q: B; H  u+ Y" e # 使用K_Means聚类
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)1 ?) A4 |$ C7 j7 z
! x) o5 o' [8 `, V* B
" I5 E0 P% K6 m- W& N
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)- R) p: h4 z4 P* S- W) r
raw_data.columns = ['X', 'Y']/ P( c7 N' B6 O9 h
x_axis = 'X'
2 @$ }) e! `* `y_axis = 'Y'. d9 K7 n- }* a8 ~* j& a5 g
0 \/ d6 a& s9 j& N$ {/ {/ {' P
examples_num = raw_data.shape[0]; ]- H8 o8 f9 N7 |6 O+ M3 k
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
3 d( R# J% |! W- l1 S) b6 v. b/ ?
# w' A9 b9 A; I: Z2 H
/ M: f) e: ]; \! {. imin_vals = train_data.min(0)
$ [. d( e; a: |( Y& Pmax_vals = train_data.max(0)5 M. ?) }6 c, Y6 `' ?, X
ranges = max_vals - min_vals
+ ~& Y7 i4 b3 G4 P; y8 A* _normal_data = np.zeros(np.shape(train_data))
6 M9 I: N5 Q" A4 ?nums = train_data.shape[0]3 `" y+ I3 k/ ]4 v* o% V
normal_data = train_data - np.tile(min_vals, (nums, 1))
) B& h; `9 N  q. n0 tnormal_data = normal_data / np.tile(ranges, (nums, 1))( m3 M. ]! e% W/ ]

; c2 h+ I+ z7 g  Flabels = spectral_clustering(normal_data, 2)
$ _, g' N3 W6 Z3 y: Z" @9 f2 L2 |( f* `: u8 G! F9 O
# 原数据& [5 l5 S* ^) J7 R, n  y
fig, (ax0, ax1) = plt.subplots(ncols=2)% K' W1 j1 {$ y4 `) }" n/ r5 `& E/ }
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
0 |; ]. P: {) q8 W8 s  z5 \  a0 Fax0.set_title('raw data')6 E, n* R9 L6 p1 L7 L; f
# 谱聚类结果
/ X# }0 l- \' @$ ]' {0 cax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)" O! {: o1 E7 g7 v8 Z
ax1.set_title('Spectral Clustering')
: m$ C$ L7 c. X7 j: b/ Z$ n* D% d# O7 ~& s6 a  M  s8 F# y
plt.show()
" A& h" r3 _1 W% P( |+ l
! s: l" E& a# ], V, }5 b1; y- L2 q. \& y2 A- R
2: X( ]6 y. _" f( ]* N
3
/ B7 V$ c4 X( v4
. U$ m. N& f# T5+ E, L, O" h+ t7 z# L' d
6
! U% q% [& s+ F; C3 k. ^- t7
: |7 ]$ g- O! Q. R8: g- l3 I6 v/ V
9
7 Z2 [: S" \' I! D10/ e, P( F1 q" f4 z- Q/ l$ _
11
. `, e. q( r" c: m12+ G8 ?. e! I: P1 |, z
13% k( x% z$ k0 D7 ~
14) T! Z  D! K( q7 B  W
15
9 d" g. Z# F5 T$ C" i165 L* p: N1 x2 K5 Z% q. Z" s$ B& @- [
172 [7 g5 a5 U  R7 j
18
: H3 V* O; E/ a) X192 G$ _7 K: A; c' p$ X
20; n6 t( |1 a8 U/ U
21
9 Q" O' Z4 }- H$ i) G: v" Y3 \22/ Q4 c/ t+ s/ I/ K& \2 H; v
23
$ r& {8 v3 z# x  m+ ]  }4 C/ w24( j; v* m7 i6 v# h4 X4 ?2 t3 \* }
25
: R& q- v4 Z2 M7 x- `262 \" p4 Z. d9 m, L
27
  j4 O, \- i% t( y28
5 L+ V1 N& q$ v2 s" `29
$ n' T3 ^5 S$ o& @30
* e) h- H$ f( O  I31
8 p% d/ H6 ]$ _8 t; p7 [# W# z; c: h32" h* Q4 A. o) q  ?8 I2 w5 s! Q
338 v* p4 ^- U3 }7 s/ w% ^9 ]9 ~  S
34; ~; v$ Z( R: C  B4 y- f0 J3 _$ u+ Y
356 P/ t7 m: e1 A& Y$ h, |
36- ?1 z4 e6 z) s" s- k
37
$ t( V5 c! V$ A- m38
3 }/ r) x, u8 I& F0 @" }$ m# S39; b6 P1 v$ l) C# h9 \. [
400 o9 ?  f6 I9 \0 Y$ D
41$ E( H. W% I) E
42& Q" H' Y1 j8 z2 ]( Y& ~. E
43
% b9 k% m$ C3 O# D4 @" b1 N/ j44. z3 u: z- u/ J' Y" f7 R8 [/ q
45
1 Q  T) i" T, l; a6 `9 \9 y46- i  U( r3 e4 q. c4 c. T
477 j, Y( X4 |( W
48: a! F8 [1 |# I% m( v" L
49
. i% E4 C: _) b4 T504 B4 h6 h$ v2 t! ]! U4 G8 D
51% q; o" ~$ ?$ X. ^/ W* Q9 @
52+ K$ F) I3 l2 l* L& ?8 c% Q
53
  g  x% b+ m+ [7 ^: S9 p. C; I544 o* g8 U, J' `* i
55% b: S2 s; j* L: i6 n) B. v9 V! q
56
5 l' Y3 g, C5 T, \) y578 ?3 }  v5 j% S3 C5 q5 }
58
9 _0 K3 B& C$ z/ q! L' J59# |8 p5 x+ d' W0 c
60
# E  F4 ~. E$ l+ ~* o- ^' S61% R! k% w. h5 \& ]
627 v' r7 V) ?5 i) J# Y9 e- E- c3 M, ?% ~$ |
63' B! l/ f4 m6 V1 Q; W& x
64
/ c" R- u  ?. ]1 L9 {65
5 o2 b- n+ T: A, p# S5 I/ p66, {* S0 G7 M2 _  S' _! L' u
67
, S% ?+ T0 n) F" @: ~' {68
/ i! l: z$ D/ S6 h691 Z2 X" X; [" n
70
: ?# @7 x' |4 F0 s. [0 n( T% L719 _5 s8 x% l3 Q* |& [* U1 W
727 [; U2 z, ^: h% L# T, }
73" ?% C. F# I. w+ M" s6 [8 [7 c
74
2 N( }/ B2 h" u  e4 d9 t3 w750 }, \1 J% a+ G# Q
76
7 D7 r0 O6 t; B0 f77
# v  {# d/ ]6 M) j+ ?5 p, U78* W6 r2 T( \0 v/ P
79+ a, t( g" Z( h0 |
80& ~* e$ Y% l( \/ o
81
: B3 A8 ~9 _+ T  p82
. @- X7 f6 t- l* q" H83$ h3 B6 [5 k& L# a0 O# \
84, A2 R! i8 Q8 l) }6 g3 e* O
85
  z3 R  G  J7 u  @& T0 d3 ^86! q0 D0 V# J5 O% f9 M$ x) P
87
. A1 K5 h4 ?+ G4 `% o1 c$ V88
% G6 p9 d- o3 u4 v) f89& t' z$ p/ L  n+ F0 _
90
: B( B1 A4 I/ v8 o3 C91
3 Q! w3 c) X* C929 {4 W. `% s; r
93
/ e. S2 Q+ w8 ~: Z, R: t94
' Q& C2 L1 t( h6 g, V8 B95- X& e- q. t+ u/ {4 L
96
/ }4 `4 M! y% T' a2 |+ I  {97
: h8 |- W  [- z# z# ~8 L98
% y$ Q; e- t7 M6 }  V99
1 X5 z) @3 D3 M* O+ q8 u: S* E3 ~100
4 p  N& c. Z+ w4 p& W1018 G" @( b- _: a3 I" j' `* @9 C5 Y
102% ~# k% \6 }0 q" M8 g' i
1035 \: ?) z/ N$ s) `- Y
（高斯核函数）
5 J" u8 t" Z+ j0 `  \; H; u( R0 e4 L! o  G0 ]! h0 b2 L

* z  h  q4 n! b6 N1 e（K邻近法）& Y( G* v, h+ {+ u9 P6 Z; Y$ _

' @% Y1 k, u6 o: u" [! b  O8 O
( W  W1 V; L0 H* g- w四：谱聚类算法优缺点2 q% f3 a+ H$ C2 t( Y- g2 m; Q
（1）优点2 C6 i/ d' i* t9 A9 O, [
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效8 A7 z7 j7 w4 R* w9 t7 F" j" o
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
6 V2 S* E* Q7 G% F8 @谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解' H* v4 \; ]1 t
（2）缺点
: k# p* y4 _# F2 H& {  y如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
! R  k- u2 d* X2 W5 h% K聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同5 b+ [; @/ }, @6 _: f( a
————————————————' F. O- g* _5 r# [1 l9 c" M$ h* p
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。: g2 d; e; j% Z$ w
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
3 n  q  n8 I0 T$ m5 Y: ]" H1 V- r
" R9 t: u$ F7 Z5 p6 x$ R- q/ v+ N* b! u, ^" U# R8 J- p