查看: 3104|回复: 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])
7 r; H! K$ B4 Y1 _! B: A- F8 B+ c: u return dist_matrix. [  C5 V3 k/ {( K5 j* u# D4 H& v
  f* U+ ?( L& f1 W: \3 L2 d
def get_W(data, k):
+ h/ C5 U4 ?1 L0 p# y( E5 v2 n # 获取邻接矩阵（K邻近法）
0 z) q* o/ t6 U4 B; u# n: d, _6 \ n = len(data)
$ d+ {) n, j# G% B2 i" K dist_matrix = get_dist_matrix(data)+ P, E' r% b. F. |7 u# V
W = np.zeros((n, n))
% w$ b9 M! x/ S8 v( ] for idx, item in enumerate(dist_matrix):; r* ?  \& a" Z; X3 H
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表9 V8 s2 q4 n# s
      W[idx][idx_array[1:k+1]] = 1# `1 S* h' ?! n  U0 k* ~, _
transpW =np.transpose(W)
# t# M- y0 l4 M  \/ C return (W+transpW)/2
- z- `) ^/ O: h* |) h; p) Q; f# ]6 y% f  Q+ z9 G1 E
def spectral_clustering(data_set, k):3 _& W8 ?5 o: W
# 利用相似矩阵S得到邻接矩阵W0 o+ b3 [) j: |+ K: ]
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）( o  O2 h" q* E9 s: ]# R
#  W = get_W(data_set, k)  # K邻近法# B* Z( o2 F. V) j: m2 u4 S

; A- x: I2 F' y. v7 ?, d1 x0 } # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
5 b4 x5 Y! \, N  c7 K D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))( N# o9 g5 Z( _# S

2 x& R6 U( B6 Y% c: f # 计算拉普拉斯矩阵L=D-W
# i1 {0 T, o* P2 x. D% E # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
% R  u  Q) n1 Y) k9 R$ D6 h+ M L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
6 L7 H# N1 Q- P% c& |% T& h' h) z
# 得到特征值和特征向量
8 {0 N/ @% B& C4 K6 A- k8 H eigvals, eigvecs = np.linalg.eig(L)* o! N; s) G( u2 d2 [- F
& B( O% d/ F) t9 _& j% z4 V# s
# 找到前k个最小的特征值（索引）
2 |( N* B. ~! I0 W; c! W) K& r k_smallest_eigvals_index = np.argsort(eigvals)[:k]8 R2 w, U0 W4 f" M( \
9 {6 P! f( S" d6 W
# 取出这k小特征值对应的特征向量，并正则化
) \. w/ N2 H+ ]6 g' b4 s4 T k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
! u; c9 Q3 t% x5 s# V! W& M9 N' ?2 i% c4 Y- y
# 使用K_Means聚类
) s" v7 Q" f' B: @& Y5 `. y7 f return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)7 G, Y5 k6 E8 f0 r/ \9 ^

3 }/ O7 e7 \" L3 f  M, D: a
3 w0 p# \* p9 E% draw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)5 v8 e$ a5 {" K5 @" U$ y. i
raw_data.columns = ['X', 'Y']
0 g' n6 N9 a: n6 z3 Ex_axis = 'X'
$ M! S' ~1 K/ P8 i2 H% qy_axis = 'Y'! C( A* [( j" U9 n* [
; W: s% a6 G  Q1 M" ?2 t
examples_num = raw_data.shape[0]
3 \  L2 P" h' n2 a8 f% J1 g9 jtrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
4 F, J3 Q; d; p: p7 `3 n- j5 z5 n/ E* P, i' s  ?/ Z
' {; A$ G4 N  a  l) G
min_vals = train_data.min(0)6 @# G- t% s0 I
max_vals = train_data.max(0)
( z0 @6 D4 M! h4 Eranges = max_vals - min_vals3 W1 B% \( k) _8 i0 f
normal_data = np.zeros(np.shape(train_data))( ]( F) \2 X# X6 f# h
nums = train_data.shape[0]
( n* S( Q6 S$ a: h5 M4 Onormal_data = train_data - np.tile(min_vals, (nums, 1))$ M- r: {, {" H0 i( N1 W
normal_data = normal_data / np.tile(ranges, (nums, 1))
0 F9 {! ]$ ]1 O
labels = spectral_clustering(normal_data, 2)
; S' x1 }, Y0 j* I! D3 G8 T2 C
/ Q' Z8 _1 r  F4 L, ^% G. ]$ v; ]# 原数据
7 b9 R2 N0 M, v3 i* }. i& Ffig, (ax0, ax1) = plt.subplots(ncols=2)  N( R2 R/ [7 `0 P/ p
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')4 ^. {! f  {: {% Q; w; N( Q" E
ax0.set_title('raw data')5 Y, U- H& ]0 O6 m0 F
# 谱聚类结果
* R* V7 {1 g  N; \6 Pax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)! G- G+ Y3 g! z% Q" ~6 G1 v* n
ax1.set_title('Spectral Clustering')
( W- t4 s7 M# j: M' V7 I" X# R+ z6 @0 @( w8 ~
plt.show()
# `9 h8 a# X& \9 J3 Q" g4 ?6 L4 i* A% t4 R. S5 {  P
1
* V, ~: p- g! ^3 m9 U, t24 X7 y) R& x# M7 W1 {" V
3
3 K7 l4 P/ K+ Z" w* `: ~- C4 j4
# @! z3 [  B4 L5 d+ B5
+ O# Q9 H+ v# u% V& i6' E' H( Y' q& d; X
7: w: u; L) o1 N8 B, W
8/ W1 r8 M) Q! [8 x+ ]! V
9
7 ^' q+ p" D, k7 e) h$ b10  X/ y, R# o7 I. l
11# K. C7 e9 \* G  T( A* ?- h  C# {  T
12
9 y( F- [! p5 o; l13* x0 W7 U1 q  s! B+ u
14* o1 j' V0 x$ m
15# Y5 n# d. u% K5 x6 [8 v  C. [
16
4 k( P/ J8 J4 I  T0 H0 M17+ Y: m0 \; H/ A/ M$ r
18. {" d  n" J" v5 ?
193 j4 N( b( }; J9 s% ?5 i* }) y: C
205 q  A) S$ S; Y
214 Y) v7 {2 \& i
22( t/ z" U5 Q% r4 p6 c$ R' w
23
2 N& y! Y: N( c24
' B! S8 B& s0 [' C, C1 M/ |2 U25% H2 R4 D0 L1 F
26
+ ?. g/ c8 e- Q4 g7 M0 L+ ^27
: W5 P% P! L* X  F5 n28
6 n2 d! K3 m5 [4 i/ W% g29
5 o0 ^  }: @  T' o* J0 ], o30
( O, S, S" y8 V; `' I31
) Y: v; v7 B! w3 g7 M32
+ ^2 Y9 v1 {0 B7 _& S: C33& d# p% j! F! w, H3 t
34
* S/ y( T! W6 \' O35
+ I! J+ Z& S' V, X, s" O36) |: G3 B" ]) q4 ^; w( ^% w* z. n
370 A4 L6 }5 U% C  I
38
, }! i! z. B$ V" L. P  @& I2 h39
' F1 z; Y( W' ]' V40
9 [' X, Z. R. E  K9 e0 I- f41& h& t; W  L' F7 @" Q
42/ R% b9 a/ D9 q7 T$ {3 K. J. L. q
43% n; u7 K, H0 z! S$ O: c, B7 o
440 }' h, U& i$ I
45
& K: R/ t% o, Y8 B# ?46+ j+ @' \9 d- v; Q2 z/ n2 F
473 N+ G( q- o9 F+ a! C/ m
48
; c0 |2 X3 r& c; Y49, R* y' O" h. a: v) ~# x; U
50
# X! f6 Q% a2 `51
+ H7 u: S$ k3 x- b52! N; _9 }. R: b- W& ^: X
53) O. {) G9 ~* W1 g7 |8 P
54
, D4 ~0 q7 [/ I( [+ l" C/ ?" \/ y553 A: l) r7 L  Y* s4 e! n0 U
568 C2 M1 z( H; O2 w. Q
57
( o) Q& D) U5 ]1 e58
" Q$ N2 x: U3 a  _59
% g6 {( x  x5 U, A60
5 Q6 p" f1 c! `8 v- S6 p+ y614 J  x, F, n: L2 W
62
1 B7 ?  g0 y& y) q" X63; }2 |* B1 I, T( I/ r' w
64) @8 a5 h- M# s
65" q0 c$ E! E1 w  a
66/ ~- D$ _5 D& f& w0 U
67
2 i4 y8 l; Q. x* J684 H* J9 }) M5 ]% s( [
690 L( u  _3 s) t8 |0 f3 l& p
708 u0 }9 d, q6 N+ [8 n
71. d, Z5 d- K) h* L, f5 @: {
72
* k, Y) r+ t. G* e9 x73
7 H. q0 a2 h* T! u0 X3 b74( P" c% ~( W7 O* W1 L! X; L
75
( B0 e0 V, \/ n76! {" @2 r8 c  e. D
772 M6 [1 Z  t/ e" C
78( @6 d/ m6 N, H$ ?. U
79% u2 M. R. m, L- n+ e
80
2 B/ p1 p' N6 y. L. H5 @9 k81
: d9 V! E' K4 @1 v82
, i; G; Y# w1 Y9 r7 i' f) S83" H" \1 p4 b& B9 Q
84
! K0 z2 K6 _( _0 K  K' B- y* L" }85, \7 [; Q; `) i& d
86# M' z8 x) h2 c7 M2 r
87
, r9 O, O* H7 Z88
- ^- J5 J4 ^0 N5 A0 v8 H0 E89  c& }3 X4 U" q. W0 d
90
2 T: B, Z& o8 M' e- f5 Q9 I/ r91: y9 ]& A" u5 f" O5 S4 x/ d$ B$ y( m
92
6 B1 w9 t# y( r! b+ n93
, q  [% s: ]+ p) y! e. _94) v9 ?+ b2 @, r) y5 Y6 n
95. q; t' e3 Q* w- m7 K
96
5 d# s, L, n( y" [# e97
, f, N: \% T% Q5 n: S98  b# W! @/ Q. ]* A- O) G/ W6 H: L# m1 B
99
6 i, p5 H4 n1 K/ i+ d  t( M2 r100
# B/ ^$ z7 v% Z7 C& P101
' ?5 A4 v4 [1 e$ |0 t9 u1020 }; a8 P& Z7 i
103
# q* x3 l) @5 a（高斯核函数）
! o# p. {/ P6 w& ~1 k/ m3 E0 ~: w) d7 B7 D1 B

9 F7 H$ [7 y. \3 G7 |（K邻近法）8 F- _) X& ]! j3 p: O+ L

  O" m1 `- W( Y4 ?0 O$ i) p& `
. f* t4 v5 l; g. h/ V( B9 V四：谱聚类算法优缺点
% _- d; M% b/ h0 K（1）优点$ l: H- ~/ G  [8 W5 B* Q6 L
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效& A+ f% k% v  H
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法: p7 E  b( m+ G3 W0 W' s
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
  q# n  T1 s) a5 w6 v' T: m（2）缺点: g. {# p$ |( S$ K& C" \& T4 n% v
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
3 {6 Y! @0 p: `0 N7 A+ b聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同! I. B- x) p+ e2 G
————————————————( P, q( T, v! K5 S3 u, M2 I  j
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 ]" `& v0 Q' @% M原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494  r# p9 x0 g. M( A* \6 _

4 d5 D2 b5 \+ A) t2 \; |5 H: K
9 \5 y9 k* a" X3 X+ M3 G& U% }