数学建模社区-数学中国

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

作者: 杨利霞 时间: 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])6 d0 n( O" Z3 |- ]: N+ F
return dist_matrix
0 X& h! j* O+ Z8 a+ l( ~5 Q4 ~7 X! ^% i9 d; ?* H% T
def get_W(data, k):
0 ]0 k$ P7 B. I1 G. [/ Y" G( h # 获取邻接矩阵（K邻近法）
+ Z+ |* i% m! U3 ^+ W; u) H n = len(data)
9 Q+ N) t6 @, n( e0 i dist_matrix = get_dist_matrix(data)
7 W8 z8 _8 @5 S, [* K8 B  O W = np.zeros((n, n))
! A: }: m" B. O3 t for idx, item in enumerate(dist_matrix):8 c+ q/ x# Q* M5 r1 I5 d; b( x+ Z. g
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
6 P9 j5 d, [, p4 ]8 D  a$ T* k       W[idx][idx_array[1:k+1]] = 12 U5 u; y3 z" }' |, m* v# H
transpW =np.transpose(W)
return (W+transpW)/2
: [/ t0 F; |# p# b* W0 U9 z# a: l) p+ `0 T# }
def spectral_clustering(data_set, k):" W  n. t- U5 \8 y! O! u* T( l/ m1 ]% q* g
# 利用相似矩阵S得到邻接矩阵W# V5 t0 m  P3 W! Z
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
  J7 ~4 w' S" E) V. q% @ #  W = get_W(data_set, k)  # K邻近法7 k$ p; m/ o' F7 ~% r" r
; N' R% |! A6 V; H, c
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）  a2 \  [" w4 y+ b' {$ T: @
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))) l& W2 w9 t; o( W  |
" B0 W  Q9 }9 @
# 计算拉普拉斯矩阵L=D-W
9 b" S- |  h6 d. F # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv3 w( T* W: M0 u
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)- b& J% N$ t: k

# `9 o6 F0 J6 m7 d # 得到特征值和特征向量2 G+ B% T4 Z5 w9 W$ y
eigvals, eigvecs = np.linalg.eig(L)
8 J" O* B5 T5 E7 t1 V3 u/ d" V: n/ [2 B% }9 i" }
# 找到前k个最小的特征值（索引）6 C. J6 I% r+ _" g0 u
k_smallest_eigvals_index = np.argsort(eigvals)[:k]
# M& u6 F, n4 `
, n6 G$ c, A" \: \1 a # 取出这k小特征值对应的特征向量，并正则化4 e2 D* E. n) u: S( F0 W+ s
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])9 d1 g0 l# s$ ]
/ V2 p$ i+ M3 l
# 使用K_Means聚类2 c/ O; q" C  F! w- w# L- P! I) B* Y
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)' b6 z1 P1 a; _* b% B6 s

4 i" x# n. s2 V- N+ S
% x0 Z5 Y: y7 d6 lraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)2 M3 u! S. b/ h
raw_data.columns = ['X', 'Y']. p9 G* K, R8 ~
x_axis = 'X'
1 U& I. m8 Q5 `" a1 \y_axis = 'Y'
2 S8 Q; |  T& f- [; {. [: p/ u, v$ b8 J* e5 T
examples_num = raw_data.shape[0]0 \/ q  e/ B8 F/ a7 q
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
, R: m) H, \  t5 M" C" Y  E  U* [$ h! \' D; L/ f3 i5 ~
4 p1 x6 n5 ]/ T1 y: U
min_vals = train_data.min(0)
/ E' j+ U+ I0 w/ O/ }max_vals = train_data.max(0)2 J! D& r/ p* e( u# n
ranges = max_vals - min_vals
* N; N2 F4 X; h: O4 dnormal_data = np.zeros(np.shape(train_data))$ j; t; n6 I1 L# x
nums = train_data.shape[0]3 ^! R; i" \  L5 _% a
normal_data = train_data - np.tile(min_vals, (nums, 1))! |/ f/ J3 E5 x% o
normal_data = normal_data / np.tile(ranges, (nums, 1))
0 p& h0 e5 G$ \" R- H' ]7 }, B! i. H2 |' \% H+ H. }
labels = spectral_clustering(normal_data, 2)& Q3 A% v) ^6 a$ T3 f

( C* Y' C5 E# l! [5 D# 原数据
) Q5 W, E7 R) A+ E' \2 |- Vfig, (ax0, ax1) = plt.subplots(ncols=2)
4 H7 Q) ]: I5 p, ~6 G  ^ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')) p* _2 h+ r5 e* ]3 o
ax0.set_title('raw data')
' L' b& h' U9 e% f7 M# 谱聚类结果
" c: V, m9 l+ G* {# Sax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)" C. P5 l* W' i- x9 A
ax1.set_title('Spectral Clustering')
; W" E: C: M; O( {$ |, L
3 q! L5 i( o5 H0 Aplt.show()0 R4 D3 }0 T6 o8 J
0 `4 j- }  d! R* {/ ~2 H
1
" i% N$ K2 ^# x/ o( G0 w2' a+ R( s& q& @/ k5 V9 X
34 }/ M6 x, G  M& u7 u% y
4" u) |; z* k0 t( W2 D
5
6 F. \0 j3 U7 L3 y% Y) x( j6
+ f7 V/ I- o. ]8 L5 _7
3 }) A  q" v3 m8  d& N" T2 @' C
9
& G1 @! s$ n$ Z: X0 v( {+ z10
1 a8 a: a7 ]- _" s) D+ P110 [- a7 Z3 r$ D0 Z; c: g9 r3 I/ t
12$ E2 \( p( i5 v( v0 X  ^* y* A
13. Q8 P8 r* \+ M! ^( i( w2 }
142 B7 s  @4 C0 R( [! E
15
' y6 x; K% C: }: }* L" W16
$ K2 ]0 ]3 ^9 E1 r% |% v0 h& r7 W172 B2 n  [: N, g) U- @
18* w; D4 L3 o" n% Y
19+ R2 V8 |# s' H5 Z6 b9 b7 Q
20
& v7 @5 I  C1 b& I21
6 N$ m; ?' n* F22
, ^: l  N: ~. O) s% U# Q) a" N23; L; v0 u7 b! ]7 u
24
7 M4 X6 ~9 F: J6 i8 R25
" \% ^! u: ?0 B' G$ `, y26. C9 e0 g, z5 s- ^3 \  I, t* X
27$ _) X& y+ l. j! C
28
5 l( ]+ v; O6 x8 ^29# [6 Q. k8 F7 C' P6 f/ j8 t* L" Y6 B" i
30
3 F% v1 P) c! a2 p( I: f0 x5 c311 r! O2 h( {7 g
32- P( S  ?% X0 L! k; E3 h
33* U  {- ^  d/ M* K. O! D- U3 r% D
34
: t2 O7 i6 v% j  n+ v& S" f  S35
- v1 T, i8 Q; s1 _; T; P36
- h  s0 p* T3 @( |37
7 }4 c% ~/ {& V: Y4 \% t385 O  x: `- e- w+ B
39/ \8 e6 m. x$ W
40
) |# o) T% D2 U3 j7 s41
9 z; X8 a# G0 f42+ e+ J& S7 q9 ?2 W, w$ Z9 \9 F
437 {, I( h. K8 m$ K( _
44$ ]5 i( E: z! b
45
8 O& T' r3 {* v8 d8 D, v46
2 S" a+ i0 U7 C9 q# @* o: S47$ g) ~5 I0 G: |3 B( q. {
48
3 J+ G* K4 R+ x5 D, O  q7 x# ^. A49
: E4 e) v- O2 U  u9 r50$ \' X8 N' V  @- _5 T
51
7 \3 D; n; O" P) H5 t52
  a/ F$ |2 g' `3 t- H53
4 G( T3 c" x  `( I/ L1 J8 b# {54$ s/ q& {$ B; k5 N/ V2 E& G# W4 ]/ z
557 M7 D6 C! ]( w) J% r. S
56) o$ m: I% t4 ^
57
& _, t9 Q3 z$ t2 L: a  h& W: o0 h587 S9 w. _& e: y# p
59
& X5 T. i$ B$ t) S, r. U60* _$ J+ G! j8 d7 C6 Z* h" s
61; ^: E7 K/ |5 Q
624 s+ g  B- P4 h7 S5 }
63
* P# J5 ]" s6 ~+ c4 a+ }64
! ~' b- P4 z. F* e3 A% i65* U4 i* J, f5 O/ [  Z# {, W6 |
66+ [! ~9 R7 @: L% H9 H* B& K
67
  `' `0 T  t! }* r" T1 \68
/ [' v' T3 R2 k; B69
! @+ M. u5 t% H( O/ p' S" R, i70
4 S; C" W! e/ |6 C; A71
1 ?' j& D, A2 T! T2 U1 w72
- y/ V7 O* e  O( W; g, |& M4 E73. l6 u. Q  Y; d
74
6 Y' Z( ?8 U3 q2 e! w7 L75% p; \2 o% v% `* z4 e+ G
76
' o/ h  N8 T/ T1 K. ]. w- ]8 B5 A77
+ l! v) U1 K2 S4 H7 ]" m787 L5 Y; O* ~3 X
798 j- @; _1 R5 G$ \3 I
80
" e7 w$ s3 ]! N. ~" G+ Q81
$ u! ~% p2 \$ p823 u9 x' Q* ^0 o8 g4 k
83; z8 O4 M8 n( Q5 B; X9 e' X- m& n
840 i' s+ N0 Z* ^5 S
85
# S) r8 R  r/ w& m. C86' I3 u! _! X5 I- q7 y! O" P$ F! k, e
87. B# H2 S: n. o- d: F
884 K  w" J# Y3 b) F+ R7 ^, Q
89
  A* n  |1 |  h3 y90
. p- T1 F6 I( o6 y  j% _2 ^# I91: h$ t, }- S$ q5 w& Y; W
92& R* ~  W3 U  A  a/ Z0 Q: W
93) @7 P9 ~* N( w/ F: g
947 A. t5 m( V% E
95. K* }. m* _1 D5 Y3 h; c) E
96# r$ \5 {" R, U, I9 \, P4 ]! y
971 H- [# ~; |* ~% w5 f
98# J$ u- s7 f- x, u1 E: ~( ]
99
2 |$ R, \3 ~/ }3 B100
0 w7 M6 r& k; y8 u) `" J% U+ G1012 }" @8 @6 ?. f% Y; f6 d8 }4 o
102
' y2 ]# A$ w9 S* a103
' k. P* `# N' [' l# g8 Z（高斯核函数）
/ @& u% j* w7 `5 N) E& L8 x6 B
% b$ q  X# y# `) E1 u# t* W
5 u+ D3 g# s) P+ E9 C' R) E（K邻近法）
! l' N& x" m: V* ?) R5 x% e
8 w9 v  R, l0 g
: a- N  _) U, w. r四：谱聚类算法优缺点
1 `, L' T9 [$ W（1）优点
# Q& U$ v: O. `4 L谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
$ ~0 V4 V: f9 D- _; L使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
. u% o2 U5 h( ~$ G2 d$ \# Y( b谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
* H3 @' y: [6 B2 D5 J（2）缺点
! |0 s) t) `: k. t( O6 o如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好3 A( ]; X. k5 G7 Y5 i
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同: Z( m- N3 f6 C( f: S; x; S8 U
————————————————& |8 k$ r; |& ]
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- E* Q! h7 H+ ~原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494, s4 y, U9 A4 B
4 Z" p/ I1 W2 s8 S& F, E, K
5 t& {) G  v2 y% F# c  z. ?/ x

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