数学建模社区-数学中国

标题: 【数据聚类】第八章第二节：谱聚类算法之切图聚类、算法流程及其实现 [打印本页]

作者: 杨利霞 时间: 2022-9-12 18:41
标题: 【数据聚类】第八章第二节：谱聚类算法之切图聚类、算法流程及其实现
【数据聚类】第八章第二节：谱聚类算法之切图聚类、算法流程及其实现

本文部分内容源自刘建平博客，在此基础上进行总结拓展

原文链接
文章目录
一：谱聚类与图划分
（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])
8 P6 |4 N0 H  y  N6 d! t+ \ return dist_matrix3 N8 J% |/ \2 H6 ^/ k! Q8 L

- z) k/ q' u5 w5 M9 a, n- z4 bdef get_W(data, k):
3 @4 I. Z# F! x; u8 L/ S # 获取邻接矩阵（K邻近法）+ O  M& p" ~& y$ L/ [" |
n = len(data)" S% \2 n0 u4 n
dist_matrix = get_dist_matrix(data)
) c2 F9 |3 T4 S! V) i W = np.zeros((n, n))+ K: s8 u3 Y' m
for idx, item in enumerate(dist_matrix):
# k; x& A/ O( D& r       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
2 o* F1 G! d4 V5 v       W[idx][idx_array[1:k+1]] = 1* q! @. o! |9 T
transpW =np.transpose(W)
" W$ y0 K, s5 K1 \' ? return (W+transpW)/2
+ V! U$ j, m, k& P% i) n& ~2 m7 Y
5 z' R5 A3 R1 c* ]+ M) qdef spectral_clustering(data_set, k):
: e& I8 S4 h3 C+ ] # 利用相似矩阵S得到邻接矩阵W
9 v. @( U$ D$ W# N" p! R W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
- E( D3 ~4 ^; [4 b# ] #  W = get_W(data_set, k)  # K邻近法) P) n4 L1 z; c: b4 l. x2 {; E
0 {0 k7 X: w4 r  c
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
8 m( y9 |* Y5 Z: A' N- h( J3 A' L/ e D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))
/ X5 D: R" Q2 [, m7 S6 J' l! i
* A& [* x0 O* {3 x" ^, Q6 K( ~  Q # 计算拉普拉斯矩阵L=D-W
2 @- V4 K! j$ H) F # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
( B/ y# p6 [. x4 O' f4 e7 X L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)2 Z5 ]2 Z" {! B2 v7 q% c( v. O+ [
& s: B2 r1 o6 b+ ?6 k1 [8 ^! v* ]
# 得到特征值和特征向量
$ N: W( z+ n  ] eigvals, eigvecs = np.linalg.eig(L)# c) o. ~/ F5 i# |1 f

4 N8 ?; ^. J, [" w5 W& N # 找到前k个最小的特征值（索引）1 Y* ?1 i2 t4 [- |$ g
k_smallest_eigvals_index = np.argsort(eigvals)[:k]$ W& i7 w# l1 j, r- {6 h

8 V. G5 o- c% Y1 B' n # 取出这k小特征值对应的特征向量，并正则化
* v; P2 L: e' y$ v k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
2 Q# M7 Y3 }2 L
9 y$ `: `, j5 f" j9 o& g- ` # 使用K_Means聚类7 ~! I; u9 c) Q- r! W1 x
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)" k2 x: o$ S5 t! }6 G& }5 ~. N

8 v* g+ }' q" X3 x/ D6 J; q- C3 g1 `% X7 i4 E3 m4 X5 S
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
6 Y( h( ^9 C5 \+ c" j9 g+ i3 K1 rraw_data.columns = ['X', 'Y']
& A1 k, c& ^8 o( \x_axis = 'X'
/ K1 u# U9 u% @( F& `y_axis = 'Y'
; ^& w- ?5 k# r0 x" [0 O& h0 J7 c* G2 T8 D+ Z3 F2 T% S1 z4 w9 x9 G
examples_num = raw_data.shape[0]
  L! _3 |- r4 N( }! k9 ktrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)" w2 ]" W9 \# n9 u. x) i
' ^- u/ H/ o# n
; A; l6 m) J) W# q$ n7 o/ v
min_vals = train_data.min(0)8 x& O, Z" \* O; A5 `! R
max_vals = train_data.max(0)
4 V6 }% z$ N2 A1 uranges = max_vals - min_vals) X' D1 n+ _7 i* `' q+ A% n' t
normal_data = np.zeros(np.shape(train_data))
1 Z) X$ |  H; n# X, ?% L! r+ Cnums = train_data.shape[0]+ Z2 t$ h8 v/ Q4 u$ x9 q
normal_data = train_data - np.tile(min_vals, (nums, 1))( Z4 I% n5 K3 Z0 V; e7 w3 U
normal_data = normal_data / np.tile(ranges, (nums, 1))8 {7 h  |/ p) t" H
8 |5 r; _! ]7 R( R
labels = spectral_clustering(normal_data, 2): `+ Z, ~' N  L; W+ S0 A2 S+ r, i
$ ~, o3 a! ^6 D: |8 T# `* `
# 原数据
, r3 b! X% k# r5 x& Ofig, (ax0, ax1) = plt.subplots(ncols=2)
; {( Q1 C& g6 {6 V3 b- `7 ]9 m( Hax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')' @0 e$ j! k, ?0 {8 f/ v
ax0.set_title('raw data')! j8 f" K$ W. k4 E# J
# 谱聚类结果
, \7 A0 F( Q9 T7 Q2 c6 M' i% aax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
5 @4 l" Z# F+ v- J' L& xax1.set_title('Spectral Clustering')
/ h0 u# d0 b: M$ Z' B
$ f: k; q. A5 t. ^/ a; Z+ r$ s# vplt.show()) V3 r* o5 D2 A: g7 i) c5 U' O4 T  i

3 w* e6 E/ C1 z: C: k1. V* O! Q3 k) U: Y- E$ l1 F
24 W1 y7 b2 K7 a. H9 Q+ p& u$ o7 S
34 B; [% _2 J* g6 e- l% t
40 {2 P" v5 s7 G% z" O. ]/ X
51 l# H( |7 S+ q' B" ~- E
65 r5 W' z: d$ M2 S' P5 Y
7
& |! l# a$ B3 `0 m84 T3 b5 j, v5 g! s5 _$ \; V
91 Y" E* B, d. i) m/ i, v
10
2 p+ d5 G, g6 J7 X, o  C4 J0 @113 M- k% g5 L3 O% O# F2 g% `
12
' }8 ^& i7 H# D! @# q13
) t% K' [( [% V14" M8 {, t/ X, ]& S% R3 _( m
15) k4 w1 p) x2 L
164 y. ~2 x0 L* R
17
. v2 w- i/ w6 V: J4 v+ i18# p& G, G; d* a/ l% @3 d7 [$ b; ~
19. e/ j2 l8 |. ?
20  g& t: p5 @2 M0 h% v7 N. l
21; p; {, [) N9 X* C! {' J) |* e
22
- ?0 y" w$ ?' T23
* ]) s) D0 M4 w  e1 w; F4 r24. @  ?  B, |, r2 p  B' R% L
25
8 C$ A7 Y8 i$ e0 V- \# v; Z26' m5 W1 b6 Z  ?* i  N
27
4 q& |$ r+ ?9 L. Z4 h28/ X( M9 ]6 h9 X4 r! R& a
29- V7 w. `2 ^, Y* t$ Y1 B  W2 A
30
0 A5 X, X7 o9 x/ s' T31# {  V% M7 x; E, ]+ ?
325 M4 x+ Q/ }2 I( |9 Y. J
33
! ~; S2 e) m, m" y2 g  o34
' y+ ?( s9 f* a2 O+ _5 g. n35
" y& G: a( A+ ]" X- q( L( i36
5 f- K9 I8 L. k2 i37
2 k# @: a: a" ]1 {5 h6 P38
, W  s4 e! j) f! r9 C, d39
9 F; _& h+ E6 C. b40( r. |, f% K: U0 J* H8 s7 w
41
2 f; B: \* C% y42( Q, T$ t' ]0 K& r* Y- T$ g# p
43
6 h, I4 O9 z/ J* K2 g3 ]442 l- f+ a5 M; [
457 |+ \( }' X; ?% e! W$ I( C0 z
46) K, T7 p8 E+ S
47, r5 l5 _5 U  B2 i
48
. J+ J9 k9 C" B8 P49
8 m; G3 C/ C. ]50
. o, y8 i. J. B) c5 v: Q' p51
& c5 X) d' n* p523 i7 Y" W' ~9 L! \8 m9 N4 z
53
( W* N1 y: `/ k7 g54
' ]- Q! k. K! v% F% \% e55+ S  U/ v' }9 f' J
56! f$ ?9 E# t% g+ W+ Y
57/ @, C6 [7 _1 \& \1 I7 U, T  |
58/ N# a# ~4 h1 x( D) F3 W  y9 s9 `$ h
59
3 Y# m) t5 a$ R7 @* J6 e60
0 p: k+ w' I5 b. E, A61
6 G  J/ ~5 s  W62
; S: }5 a" ^( E63' T" `/ F& R9 Z
64' d6 ~0 a5 |+ f" L: z
65
+ S8 [; D" U$ n( ^, T0 d66
( A5 B, E$ x* @$ E/ t: a67
5 i( ?4 v& Y8 r. l, B' M9 }689 d& C$ H; J: m6 A3 Y1 c
69
8 O+ T" u1 F* t6 u) k4 ]% u70
- h# k8 F( I. `! X1 `1 h5 d71' a2 }& O# F# r5 z2 k+ T* l* i
72
8 A$ @: a) K/ b% Y- W& q( W73: w" D5 B8 W, |. f4 x* n5 M
74& ], P, Y% a: H! L) }+ B
75
  C1 Y+ |  B9 L4 j& L% v2 W; c8 [767 j: P! P! S8 _
77
( t" n* A" j" W0 Y$ }  ^- I- I  [78
/ Q: ]/ U2 V8 `# ]! u79
2 n( `5 N) `- ]4 ?! J6 h! @80+ @( V# D- l9 C) m5 c3 Y
81! D9 v, u: ^; s, {' ], |0 @; J2 ?
82
( p% h/ F9 X: @( b# J# m% r5 {832 [" Y' m+ i- w2 H4 B+ M$ ?, g4 C
84$ ]+ F$ u: O: r5 g, e( z+ d6 x
85
& f5 F8 c) Q/ o) V* C1 O86
. V" I; w0 w, y6 K& d87( S% g4 \1 `9 Q$ t8 l. P% n
88: h0 Q$ N  o3 d" R) A
89
$ ]% i+ j3 U  D) T' ?+ y90: Q* d- L- M' G4 q
91& m0 v8 N, W* f  I
92
9 ^, D: a" S5 L2 e% \0 Z93# [* C+ J: @. }1 Q: H
941 R3 F4 z/ X" r+ h# h/ T
955 l- c! H0 l& c
96
, k3 g' q' G1 Q5 l) z- R, Y97' t& A) e* E' p4 P
98- b' h" v  u* v$ ]) {# ~
990 ^' W0 _- Y+ I; V" y" l# m. A
100
/ N; b( q1 T2 t3 D101
1 b* Y! ^+ P1 m+ F$ L( B* Y9 t2 j; m102
& M2 ?# f1 T7 p4 X$ K$ j& \103  F3 {  E* b) }% ?* p
（高斯核函数）
/ \/ o/ y2 e% ]# O! A
3 H& H/ a3 n6 e% o& W3 O) f8 G
1 c2 [( S/ y, J, ^8 n  s; N1 f2 {（K邻近法）
$ ~" w& C* L4 I( H( J- W' I7 X; U: ?" A
( v/ N/ W% o5 k6 @
四：谱聚类算法优缺点1 \& t6 N/ V( v. q
（1）优点, L9 c( }9 e& M- x  q
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
4 F2 B; o7 U( E& F7 `8 M使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
3 s4 \; n' s. h5 B& H% j: W' F谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
) D2 ~4 ?5 P. R/ V0 M& f（2）缺点+ r% X9 y4 X8 L1 \3 ~$ V- e  Z$ g8 t4 P. T
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好- D2 I1 K# j" ?" ]- V
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同% b2 v; B" Q7 G2 ^- s" B2 ~
————————————————
7 u# y7 }( X( S版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。. |% v7 [3 T, d
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494- w4 `- X! [, y0 v9 G2 Y
, n+ V6 Q! _+ e7 Q

7 V  ~; E3 h, G  X; c! R# z4 H

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5