数学建模社区-数学中国

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

作者: 杨利霞 时间: 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])
# _3 J* L* Z8 b6 g8 ?. O) e return dist_matrix* O% B6 v0 z2 @7 w. F: y/ j
5 p# x  N# e% C4 ], x7 M" Z+ L* O! c
def get_W(data, k):8 t1 D! U" d8 e0 I- e; }
# 获取邻接矩阵（K邻近法）: {1 d; A+ y5 i9 I& W* h8 O. I
n = len(data)
/ M! l9 ?: p5 R, |3 Z dist_matrix = get_dist_matrix(data)6 L1 x& V5 ^: P  V/ Q, r2 A; L9 z
W = np.zeros((n, n))
9 l+ J" C9 u/ _' g2 Y for idx, item in enumerate(dist_matrix):
% X, C( \$ W: ?3 J       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表! Y4 q' `3 e: ?: I1 `5 a, [* i
      W[idx][idx_array[1:k+1]] = 1
6 `2 A. b. T, }; a% |8 N& } transpW =np.transpose(W)
8 V7 J' U4 ^6 i1 S4 g5 g$ o( B: L return (W+transpW)/2
: b) m  D& c. T4 M  j* W; O' I
. M! [* ^* M  [: Mdef spectral_clustering(data_set, k):, K0 e  }" F/ r1 q- @2 w
# 利用相似矩阵S得到邻接矩阵W
1 B) s  U. L; U' A6 x* s3 M W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
: o  w# K- i3 @+ @. _ #  W = get_W(data_set, k)  # K邻近法9 q7 `% B9 k' ?) B) d8 {/ @/ B
! Z# I* s6 d7 K$ F; d. p
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）6 z/ {" W# L+ t9 M
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))! O" m& i' k8 {+ g
: f( z% j" s5 D; D' F
# 计算拉普拉斯矩阵L=D-W
% R; \/ e2 d+ g7 Y' _ # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
% a/ b5 d& s7 a& R L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)3 k8 ^2 L) q/ Z& j
' W5 S0 ?5 A- q# b- S
# 得到特征值和特征向量
+ y. Q  l( S/ e6 ?. {: s eigvals, eigvecs = np.linalg.eig(L)
  C  x% b' l/ \8 _6 k1 I/ J7 {. x) S( g  x7 T7 i0 _
# 找到前k个最小的特征值（索引）
% w" @% d$ X, t1 W* v k_smallest_eigvals_index = np.argsort(eigvals)[:k]1 P% w" |1 R$ g# I# \
0 V% E9 Y6 n, ]3 S0 w: [1 f
# 取出这k小特征值对应的特征向量，并正则化: `) b5 R% x. d/ O: ~
k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
3 C" L  P; _  B% ^3 ~% o! p2 J6 t7 C9 n
# 使用K_Means聚类3 L9 }2 e" a- K5 e  K! e
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)+ [3 m) y, r# E1 m) q) \

! G2 Y+ ^7 F- k, r
" s  |$ W9 l& Y' u/ Fraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
3 ^& {9 l6 _8 F" R5 [+ M  yraw_data.columns = ['X', 'Y']1 L2 i; T4 q; q
x_axis = 'X'8 g; x  h! U7 z- L6 B# n4 W8 c
y_axis = 'Y'
/ O5 F2 w% ?. E+ T8 z; `
$ ?2 V- b$ d- J- R% Yexamples_num = raw_data.shape[0]1 u% w# g1 y2 h) u! w$ B  V
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
% b. W6 b& @  P  B4 [: Q, q6 b2 q" A: c

  N3 F6 \. e0 S) c, K% N$ lmin_vals = train_data.min(0)
# t! P( x4 V0 r) n' g( y# {* k9 Zmax_vals = train_data.max(0)
3 D$ @% H: \% ~0 y0 W0 V* g, Mranges = max_vals - min_vals' L6 x& u) ^3 f2 O9 v
normal_data = np.zeros(np.shape(train_data))
$ n8 `6 n+ d4 Y/ v  |2 onums = train_data.shape[0]( O! E; K2 ^& H+ B; m* W1 |& H
normal_data = train_data - np.tile(min_vals, (nums, 1))6 e6 g0 `. @( S! v
normal_data = normal_data / np.tile(ranges, (nums, 1))
" q+ I: j$ h+ x. v2 x7 d4 C; z/ R9 a. b7 I
labels = spectral_clustering(normal_data, 2)4 T: O# {$ c0 t) ^7 z$ k
0 P2 Y. A. K. f" d' v2 X
# 原数据9 }/ p8 N6 s& Y) {) S( y5 @
fig, (ax0, ax1) = plt.subplots(ncols=2)8 G6 h5 T# @' ~- A' ^, k2 |
ax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')7 m$ b+ A) a8 G' c/ M+ ~9 B
ax0.set_title('raw data'). F) C4 R) k8 |, ^5 a9 m- f
# 谱聚类结果
, w& b, l8 B& T8 W: Jax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)6 Y, a7 G7 g; r: N0 y
ax1.set_title('Spectral Clustering')! f( T& v! y9 {3 M$ L8 @* N7 a
" B: E5 a& _2 a8 y
plt.show()- c" U  Y, N7 ^

! f  l9 L( e! e1
$ i2 Q" e# U' {5 G9 @  j, ^  W  b2
" d; ?( ]4 {: D2 x% e3 m" B0 ^# J3
' e5 U' x( d1 p3 M9 s+ C4& I; D+ l) l- R- m4 C6 i! \
5
0 B2 M9 A1 Q% ~+ k6
. r/ K$ F; L2 h+ F1 i& i) z7
7 @; x$ }- a3 @8
7 h4 h; @/ u1 L& e* j/ B9
! t6 C$ [+ [0 }  i101 P7 x/ $ o) }
112 c/ _# F* o' g1 t1 L1 N
12
7 U# e$ q3 f& y; x/ u13- [8 |4 t  j! S) ~) I& l) j3 @
14
: x& K3 ~; a- b  q1 k157 h% p' `7 E) z9 I; V1 j! X
16
5 V4 A* s3 U1 d/ U* T( ?17
% y. b. G; A( }  s; B! g: x183 x1 g4 V3 z& @$ A( p) {/ ~
19
: w. x6 h$ v+ t) {20
! F6 Y" d# S0 p' v! q21* x: r5 K; a8 [! p/ \! X4 ?
22
9 W$ n7 X( ~% t' E$ d' a( Y7 `( n235 k* h* m/ C% J+ d0 n: _
240 `! V0 `  C  m* ]
25( |. b- j/ p6 P% |
26
' |, w0 Q, H) Y, D27
( p$ $ H* B3 R8 w* `. ~8 {28
% ?0 c6 ^5 [( Z( `/ `+ d29; F+ F$ j' a) |. [
30
* I# p3 m! h& B1 t3 ]# u314 j5 c; K2 z. A+ A# l4 ?: v9 f
32! `4 ?! E- Z4 V9 R
33' A; ^( q$ y8 A1 g9 L6 {6 |2 @
34
: x! K5 F3 b; d, y% S357 f' O$ H  ]3 n, t9 S6 J
36+ A7 l9 q  n) I& g
37
+ q) Y4 M6 R5 p38( T  T3 S. y4 [0 n
39
, L! u, B1 B7 h! ?% _! x40
5 A( t/ Z: y8 X6 {" ^41
6 \( n3 V8 ^/ Z. d; T. p' D/ d  I420 e! p" O; {5 g1 V% I, b4 M, d
43# l  t' \, y  z; H& g+ e
44, z1 s" j3 ]: k* j8 K
45
# M0 A# L* `3 c0 W7 l" O: c" |467 l! d: s7 {, h2 s
47
! L% i% E0 ?, g3 i5 j& i48
) L% \. r) m1 t7 M0 K- q49
5 W4 b2 o7 s8 ]9 h50
  q# L0 W5 v* x- [0 S51
) u" E9 U+ x8 {7 @/ o52; o0 j, o; f- [. Z! H  u% [
53
8 V+ T0 i6 d6 W  P) [6 j9 N& B54
# Z# P- i9 M- H6 {0 w# {558 g: B) t8 H0 E
56% `4 W# O4 D+ `. F( m/ b
578 x- r; C* B$ [% U" T) M
58
3 w' w, {6 Z# i6 m$ C0 k: U59
, k( S+ j" D5 d8 |' H60
: ]# f' |3 u7 O0 s# g8 `' u( t: ?61
4 {5 ]9 m& D, k/ Y- {. W7 `$ c62
: Y5 J* E1 v) m; F9 n; e3 L63
2 c9 h# g9 O- S9 u3 R; q64/ [5 m. _9 g" ^
65; d2 Z( e. K- ]) O
66& a+ k) {4 Z; z  m
67! l0 J: \" }( y
68, [9 w$ v) p. k$ S+ v
690 {* q) B. o; @) C1 H2 y
70" P7 E' x' n0 s+ A& m# F: a4 N
71
# l9 A9 O/ @4 X* B72
0 b7 b2 ]6 u& y% n$ A73
0 U7 G6 u% ~: \746 a, N/ ~/ O' G( l. g8 f1 S
754 b: ?* ]% p/ c* V
76
  O( |# i% {  V5 g* d6 d8 R77
$ Q* }3 g& n. h/ }78, [# D  D% N# ?3 G% U7 K' r
79
7 W+ m8 {, G3 d5 s807 d/ K- k6 g% g
81
- N  S0 B( \9 \5 I" a82. |  u) U  k' k' I7 B7 I3 ^& y8 I+ S& D1 L
83+ Y! I  p0 D$ ]! W2 c& r% r
84
, y# K' q* h5 q- p85, x  k# `- [7 Z- ]
86" X. V* j' m, A4 U- m; H& V
870 H) K6 p6 n) y- a" M: k- i
883 {5 g5 Z) @. [& I) {& t
89% H4 B1 E# x( D* S: j" E3 j# |
90
3 [" w1 S1 s3 Q$ O  ~% {, L9 K( C910 J; L' O1 Z1 K8 S
92& R- }) B( r! d( |+ Y7 Y+ x% U! z
93
* n8 a% U$ w: t94
* o& I2 I; [8 g8 T2 S958 a9 M9 l/ V! h( N- V9 {6 W# [- Z) Z
967 `' U3 ^, A( r7 L9 Z" |
97
+ x; |- f& x$ e( z. p; ]982 H2 n2 E6 F: m3 H8 B1 @
99: Q$ Q+ G9 [8 n! h
100
+ R$ \% r+ l! z- r4 Q101+ X. A% t! d/ X' a
102: y8 s, ?) `' V  l; U
103/ K. M1 E4 \' N) n6 V
（高斯核函数）( Z$ @. H8 N! x1 m7 r! F

9 f" a* @$ L' p& i! |. s
% ^- g& T5 A7 Q; M9 I（K邻近法）/ s& n' d" w; K% {2 P
' a, R# a( t! M( c

! `, j* \+ Y+ S, Q+ Q0 H5 S% @四：谱聚类算法优缺点. ~& z2 _* P; t' `8 F8 E* c
（1）优点
6 z" R* j. ^- k! {9 @谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效' X" e1 l8 n8 m% x6 Z  |
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法6 v3 P- v% T/ Z, s5 M/ b/ t" p2 f( O
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解7 L; @* K" l. f3 g! e6 v. y0 T# h
（2）缺点- v3 r# |7 k8 D
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
! n4 q7 [% g+ i聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同! c6 B/ C2 \2 d5 H" @8 H
————————————————
* B0 R  ^) H0 d' w, v2 Z% S; A版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 R6 l/ h8 z" q/ p0 U: \" Q5 K. Q: ~原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
! c) x1 d9 S( o
/ ]* Y/ |& h; c5 X5 \9 Q7 S# `* I5 \- w& t( Q  z

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