查看: 2939|回复: 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])+ Y7 B+ U: X7 p) C
return dist_matrix
8 h2 _* S4 A6 C
! Z/ z3 p: s4 G8 t6 Qdef get_W(data, k):% ~6 h, }( r" c6 t- v; k
# 获取邻接矩阵（K邻近法）# m  _& ~# h! J/ M2 P7 |
n = len(data)$ D% e5 _# f/ ]0 M; \; Y
dist_matrix = get_dist_matrix(data)
! B3 ?' w/ b$ |8 H* R+ ?" o W = np.zeros((n, n))& t. P1 @9 }' z& T/ Q
for idx, item in enumerate(dist_matrix):; |3 E& j7 i$ ~) A
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
& q& N* x, ]- u' q$ l& r       W[idx][idx_array[1:k+1]] = 17 p+ u2 @: S6 w; ?0 ^( g3 d
transpW =np.transpose(W), ~- [/ B: v# {4 b0 U
return (W+transpW)/2
  ~8 g7 L9 M$ m* L) k0 v( K8 F# I
def spectral_clustering(data_set, k):# d7 l! L) m( k1 z
# 利用相似矩阵S得到邻接矩阵W
9 P# {0 |5 }6 W7 L1 ^# a9 E W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
- n8 c' }9 x9 U1 Z #  W = get_W(data_set, k)  # K邻近法
2 e+ B! N7 M" M' p6 H7 }, U9 b$ W8 O2 V" ?* x
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
: J! L4 _% ^" K+ w" w D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))1 z& S+ ?" @* z3 N" D2 L( H! p

, \/ n; t) H+ k3 T; I, P # 计算拉普拉斯矩阵L=D-W
, i& c( n& _/ h # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
; B' a3 s: A  ]+ M' P L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
- U# R% [, |1 a) {( j; |, j8 ^5 y, Y' w
# 得到特征值和特征向量1 Q  y- o$ ^- F) a3 j
eigvals, eigvecs = np.linalg.eig(L)4 \: A4 ?0 `- ~. r. v
% v8 w  X3 x- Y* y
# 找到前k个最小的特征值（索引）: R- l6 k7 W' ]* k! U
k_smallest_eigvals_index = np.argsort(eigvals)[:k]

* A8 Q+ R3 {7 @, m0 U # 取出这k小特征值对应的特征向量，并正则化% l9 p% L* k! O2 P4 e+ M9 V  s
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])4 m. N+ D: f! W" i. e' F
" b" i; |/ c) o9 ~; S4 ]/ P
# 使用K_Means聚类
& _2 Q) y& V: K& m  F return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
# _# Q3 `0 c5 w! u: P6 j) s# C8 d2 b& W+ Y9 R! [
. a0 F  V, `5 _& _3 K/ ^& Q6 J1 E
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
- w/ r  B. S4 W* Qraw_data.columns = ['X', 'Y']
" N' E& X* b& M8 Fx_axis = 'X'! x# T/ I( y  d' O" p9 Q& y
y_axis = 'Y'! Z2 c) D1 [4 m" x9 ^8 C

0 m0 G" G* W  X6 f( g' q0 Rexamples_num = raw_data.shape[0]" ]# h5 I; n! B. L
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
" U* N- C* ?$ n4 a9 a( ~$ M; d0 o! c6 E. C
  G0 L) r8 f' d
min_vals = train_data.min(0)
' a4 \0 W9 ]8 j: J- @max_vals = train_data.max(0)  v" I( B' u/ b8 j0 o+ ?+ V
ranges = max_vals - min_vals
; U0 k9 T, [4 p2 O/ ^normal_data = np.zeros(np.shape(train_data))3 {! |+ b8 n: q
nums = train_data.shape[0]& u1 O- e& a! G* O* _( N
normal_data = train_data - np.tile(min_vals, (nums, 1))9 x5 Z; @9 o  N5 g- u. a
normal_data = normal_data / np.tile(ranges, (nums, 1))/ }% i2 v9 h0 u2 b# V( }
0 |2 _2 {( y: ]# N/ W+ i- M
labels = spectral_clustering(normal_data, 2)6 z" n6 `8 O4 S* f& K

$ O# a# y! Y7 E# ]. z# 原数据$ U# h) C; Z8 Q- ~
fig, (ax0, ax1) = plt.subplots(ncols=2), J' q! F: a+ w
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
" ?3 m0 X# ?/ p' V! V$ Dax0.set_title('raw data')+ E- h" K' u5 M& }5 l" m# b3 D  h
# 谱聚类结果% J9 U6 T0 s+ D! R
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
& F. ^9 p$ I  v/ y2 nax1.set_title('Spectral Clustering'); ~8 R  _6 O' @) ~& X
( a6 d. _# p( l! `
plt.show()! k  J6 }; S7 L; d% {* ^; r  r% z
% d! @# V% c: p
1
! }7 T6 U( g9 B+ P) J: n4 ?2
7 n5 W: k0 r* E, S7 c. @2 i3
" M  ]* ^* @0 G% H" a4
# z; {6 L6 }" i% |0 ], i8 `- Z% P50 u8 M& A" \5 m# b, W1 |- j9 o. V/ h
6  Z5 y1 f! j( `! w' v) w
7
; z2 I5 m& u! Z  A+ \( ~) n3 _8; b/ \( \( N* y& P4 d3 X! o
9: }% s8 N7 V* I: p+ c1 {* O
10
. K, O- a" d8 Y4 K11
2 c6 A4 Z, y& h: t/ ~5 q, B6 @  f12# ~' V  g3 a# X( f3 n6 K
13
, w6 j: E- A0 y5 L14
0 N, m( P( }/ V7 C+ ^+ B15
7 f3 O# V# O0 w161 k2 e5 G( k0 ?' s
17
' o  Y+ R7 ~7 ?( W5 R6 \! {18
. R' Q% n8 f1 E- T  j19% ^) a; u$ n3 b" G4 W. e; ]& [
20
; W' _4 ]' S# j2 _2 ?( p" u21
5 R6 e" _. T) {3 Q! w22; l, x, H9 @8 m" u5 C
23
( @& W7 h9 ~: M0 A247 k* W4 a# ?) w: h! [+ }
25
: s/ A; Z+ |$ h" e% x26* W3 F( _9 J  z# P8 ^1 j
27
! g4 t9 W. e5 u28
7 v- n4 t3 z) Y& r0 ^% `29
5 F5 i7 ^- `& ]) N9 l2 h" B# `" T30
; c5 a- h' i! ]31
3 k5 }1 m8 J  O* |. g327 _$ r3 g+ A& o" `8 O
336 R& @5 T+ J. x
34
, H% P$ \9 t: C% x  `: u( z4 g357 V7 i$ V# n, O" ~
369 ^" w1 M( f: q: L# W2 h% N
37
! \( e2 f6 y2 U) `- g388 p( e4 W2 Y. x' ~  |5 Z2 E7 i
39
+ j; Q2 b9 F: ~/ j0 U3 A40
- l! k9 U: D' r) A41
6 Q4 V, S- H  w- H& j420 i& q* ?; V2 T/ H
43
( G9 b) `- R, ]1 G, A44
- G9 S2 r' P7 v450 y( Z. _0 x, g/ @- ]
46
' R9 t# p4 V* o* d8 ~/ G1 _- I; z47
+ t/ ^/ A: ^2 R% ?) \- z* q48
0 E& g4 s1 v3 L: p49) }' }" S  b! d
507 r! K; [0 |" |. ^9 ~# h
51! w( {- \3 k/ a7 V# w9 {
52
9 j* m/ t+ z$ P+ i! R+ e8 r& n9 ~2 q53) h7 R6 z0 d" J! U. J# [+ Q
544 h3 s0 s* V) B" u
55
0 D! w; U$ }! o5 i! z% W56
8 e4 p3 f; U2 T% Z57$ I: E2 C& N  @5 U" M* q
58; X, r1 ^& `, s% s+ c; C1 e9 \, T
59( D  g& u7 O" _; t+ ^; p
60* j' A6 F0 f1 f
61# D3 U3 @* X. Y' w% C9 ]9 Y
62
9 s# G% b+ ]* Y! _! Y+ n& X63
8 i9 u) P9 ~; m+ n64
* t3 F0 }7 Z& J( G65
6 |0 Z5 L9 n, I! @1 ~66
' n; P: h. Z2 a0 L9 t9 t% g( N5 M67
% R* M2 V' D/ z. _. h4 {68
5 H% x* D. @- Q% V69% ^. ~1 {8 k8 `: ~$ O3 i
70; i8 \! u) M8 c
71$ J0 W0 u( X8 f6 a# D4 ?; P
72
/ {) N1 N) [8 y% b5 L73
1 Z9 Z$ z+ E, @( n- U+ q* m3 c74; f  M8 m& n% M0 \; H/ W0 J" P
75
5 B( b, x& x, p8 ], R! u; a76
' O% R6 v( G2 B3 V3 z7 J77: }: O: p: X6 g( H/ A# ]" ^; w
782 R9 y" J9 |  C- C; c4 Z3 s
79
( T4 ^5 ]3 D3 b4 L! y) w7 f80
& z4 }" ^# Q$ ~. k; f% y+ z, O, G' _81
/ I+ z3 H! o0 m7 m( l2 n! z. C$ @82
) ]4 U+ ?9 ~$ _- X& c& Z83! T0 A! q, ?/ i( T* O0 H+ y* n8 \- g
84
! Z& y2 i1 D5 _9 r& d85
0 \+ C) O9 p2 \4 b& B86' [- h6 f# v: H2 ^0 U- P$ v
87
9 F$ A2 _7 X' a  {0 o. V: x$ ?885 d( R1 c5 ~! B! r/ }
89& N3 ^0 o  c8 |8 l; L
90% _% F) O& k) r6 F2 D7 N: b, W
91/ m5 ^5 F7 M: r7 a  L
92
/ y$ @6 B! _; a- M6 \938 S3 j6 ?$ W6 ^4 s( n
94- F: ~8 g; K7 ~: n" N7 _1 w
95. f. ^+ t1 Z* ?+ d- M  Q* C9 `
96
8 e* h3 o* L0 I+ [* S/ v5 d3 H97, O/ H* y, J# j% t
983 `+ k  a/ x. @0 y
99; z% F0 K. G$ j- c) O* H
100% E/ F2 X2 N3 K/ R! o: `+ N, N
101& w  |9 _! V" ]7 Q- e8 u
102
9 l0 o' ^9 i# O: P103# l$ M! j; V; _. w. s5 y
（高斯核函数）
$ `1 E' r7 i  t6 u; T; P4 V6 |& w: ~

- P# @9 {& Z9 j* k（K邻近法）
) e  _, L  A& Q8 C: }/ F4 t- W" z
8 F2 ]$ F% Y1 z8 ]- Y# W6 \& n% s8 W6 b
四：谱聚类算法优缺点8 Y" [; K, p# s
（1）优点
# J, t- }9 U9 O1 P7 E9 l7 x谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
1 J/ @) o; R4 G* ]" g6 @8 E使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法# X7 @. i) i$ w) x" U3 v. D. x
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
* x, v& z. Z$ i（2）缺点1 n4 U2 H7 A9 g. t  i3 }
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好5 R! j6 \& A+ q( _- _
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同8 [# z1 E5 E" Z$ [1 y/ y' [
————————————————
* B* j7 m6 U  H7 f版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) Z% P" B8 x4 m8 p* _原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494% R8 H) R( Q) h' H4 E) r9 H4 M

1 Y$ S/ c% T( K5 z7 e1 Q" I( k4 H
$ M4 l4 \6 Z# r( J9 s- g: \: h- M  \