数学建模社区-数学中国

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

作者: 杨利霞 时间: 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])+ y$ O5 E& j+ S  f* z5 k- N
return dist_matrix' {4 m- k7 ~; x+ y3 J- v5 Z
4 y( K3 \3 }/ s8 m' M
def get_W(data, k):
( z: K: V: X) q5 B) O+ M1 C # 获取邻接矩阵（K邻近法）
. t, l6 ]+ _+ G$ d0 J n = len(data)
2 }  b  g" u! G dist_matrix = get_dist_matrix(data)/ Y* p* {5 O" J' a6 s, L5 i
W = np.zeros((n, n)), a, M8 Z& |8 r6 _  C
for idx, item in enumerate(dist_matrix):
3 `8 ]2 d# N; O+ F/ V       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表8 c5 Q" j% _" o: j
      W[idx][idx_array[1:k+1]] = 1- }& k" [" \' i7 h
transpW =np.transpose(W); ]9 {3 I* y/ A. c
return (W+transpW)/2
0 Q" L! N* p: ?
4 q; |7 H- p7 A+ b( @def spectral_clustering(data_set, k):
% p8 j, E) H+ W6 x- n5 G% U& | # 利用相似矩阵S得到邻接矩阵W
2 V% ]9 X! J3 Q5 h$ I W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
) h; K$ C( I. p3 Q7 r  P0 e #  W = get_W(data_set, k)  # K邻近法
6 M  Q1 a+ @9 t+ l" ]/ Z- X  [
* ?+ p+ F% L6 K9 M # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）. t" D+ Q7 V4 W; o& l) d8 {3 d
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))3 u$ C* {0 n5 p* A/ r6 d: M. S

! }" _$ L( d6 z # 计算拉普拉斯矩阵L=D-W
8 c8 b) X6 \+ Q+ I. {" ^ # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
: D2 }7 m7 e; [ L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)/ w2 ?& d7 `; S8 X7 P
) [1 E0 ^( u1 z$ b
# 得到特征值和特征向量
/ \0 |- T! H+ W- o9 z. e$ l2 \ eigvals, eigvecs = np.linalg.eig(L)8 _' ]% v5 `$ L  Y, p! M
' S7 Z, |; r" z* c5 L
# 找到前k个最小的特征值（索引）* ^0 i7 L* O: N2 g  X4 U2 A
k_smallest_eigvals_index = np.argsort(eigvals)[:k]

9 [: H1 L8 ^2 D; H# Y7 u7 q # 取出这k小特征值对应的特征向量，并正则化
, ]% _) u2 K- J3 x k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])/ ]* v: F# Y" B" B9 K: q
& I& `- o4 @( z/ c9 J5 d' Y0 _* S
# 使用K_Means聚类! A; j* S- Z2 _7 k7 t+ ^& ~  j$ n# T. U
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
  d4 k+ T; a8 F
1 d6 D* h, G/ o; O2 ]' I
" f( y; F+ {4 c" G, l& B$ traw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
# U+ O7 K( W* H( `$ W9 {" nraw_data.columns = ['X', 'Y']
8 h/ t& L$ W8 N/ dx_axis = 'X'
# N" o) w- I% Fy_axis = 'Y'0 Y! s# `1 a  B' e! S0 a
8 R# d: M# c1 d4 O% X  h: s) {
examples_num = raw_data.shape[0]
% F& u8 C& p4 u7 o3 U1 i7 Ctrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)2 t/ H* e: e" I/ I! n, e' V0 _

) V5 |- g: E3 {+ g1 [2 l' {& x  k, G5 p' U# N# [. Z- e- I
min_vals = train_data.min(0)# Y0 ?" S3 G: z; @  O: x
max_vals = train_data.max(0)& q, K2 D1 ?! D4 B; j$ k* D+ }
ranges = max_vals - min_vals$ G7 _! b7 J0 \) B
normal_data = np.zeros(np.shape(train_data))1 z. {& O) ~$ R! r
nums = train_data.shape[0]
( U5 c3 V" y& C* N. I& Nnormal_data = train_data - np.tile(min_vals, (nums, 1))# \# N, e- W- A, D. k
normal_data = normal_data / np.tile(ranges, (nums, 1))& k2 N1 F' {! t' I; A. m% a: }
* D* c3 A# K4 w% D
labels = spectral_clustering(normal_data, 2)# U, i7 H$ ]# T) C3 E
! h% }- \% n) K$ B! A$ z
# 原数据
* {' u" g: H; H( Dfig, (ax0, ax1) = plt.subplots(ncols=2)
! c8 @) n4 Y! Tax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')/ e7 |# Q( y0 a/ x
ax0.set_title('raw data')$ u3 D, @  V4 _8 H: |, A
# 谱聚类结果' I- H$ X( T( [( E2 a& d( }
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
) R" ^$ ~% h/ T& wax1.set_title('Spectral Clustering')  u, s+ w5 J/ E9 E: X

# B: j, {% z# I" L& zplt.show()
9 t* e  y; K$ v- ~/ m5 f% z5 z% {+ z  @
1
- p# x* |* P  M25 [! T; F8 p. n! \
3
7 H. p/ {) N& [4
8 x$ @2 h* |8 D' y: O4 g5 z5) ^4 R1 r2 R9 V$ m
6) }% S. h" ?# R; p
7
+ Z/ N& Q4 J1 g1 `81 L+ r/ j& r( v1 B" z/ K" f! `& O+ v
9
( o) N) m- [$ }102 c9 I8 C6 U+ C: w
11! {3 G5 S' z9 O  D
12: Q, ]- Y! X/ f2 i9 C+ n
13, e" Y% g& j3 k! |: @5 K: a
14
- d3 }! _6 u  m( W" c& H15. M$ X6 ^& p' ~3 C' v- f
167 @' y" H7 ^, G7 b- J, l; u* O
170 C$ O3 a( t7 Q8 v; |
18
# x# z# ~, |  m, m" @# C19
" D8 {. A/ V- R3 X- o. X/ u205 A0 w1 i0 r* F
21
; h: l) Q, F- a6 F% D22' R5 _7 j2 Z% I; E1 _3 x9 W4 g
23
$ ?! T" v: p7 D249 m; {3 ]% P7 \' B4 {
25
6 p1 ]( x0 U+ U$ g268 E' o9 e1 C  L, n; [
27
) `. e. B7 f8 t( q7 c! |7 k28
& w; l& Q% e% ~3 z29
1 Q. `: _# N. g30- K  ?; a% b4 L) f$ d" o
31
/ ~# t( e9 R7 Q, @' ~: x* M32
. C" f2 _; s0 r$ C7 T7 |33- w1 O% J+ H% ~
34
& ?) `& P' B% y$ T# m- T35+ Q2 B" f; E3 \
367 O. w: {4 U- U6 B, d/ [' x
37. o6 F3 T; {, X6 o1 d
38
39+ i9 j' j& y! ]1 p
40
+ N) m- `' z, @8 K* D3 f$ \' f41! k7 s- w! ^2 b: _* ]! k( N+ t# H
42/ f  p) t/ \) z' k1 Z. R7 Y
433 T4 @6 q, {7 ]7 V' ?; R
44
# n) x4 S9 y4 A45) C' l6 ^) W1 ^, i8 w
46
* V3 z% l* R" L3 U+ y& U47# f" q) j% ^+ A2 t
48
( H  \. d2 s8 i1 O49
9 R2 u8 e' \) r3 m50
/ s/ w: [" x' `% U# R51! W, Z2 s6 p% C- w0 k
52: q7 p( M. B: _. N$ D
53
2 Y! M% I  y: b3 r5 o- X542 Q3 ^. J7 Q/ G: m; v; V# E3 \1 a% K
55
6 [9 D  x4 x( M5 S56
+ J  {, P/ N( |57
1 S% E; V- q; M) g2 T" {" l. S; k58
* \+ y7 d7 X: v( O/ j59
; h1 D1 {* Z! B! R60
5 v% |- D' W8 y* E; K2 ]61
* j( H" o8 R3 u" ^6 r" {$ ]62. y& g  m/ z. U* p4 Q8 t0 Z% S; X
63
' A2 {8 @) f+ X8 m# N64
; Z. E* b! O2 E65! c, @* ^4 n& c' l; U% l
665 A. S3 b% D, W: ?% P; {
67
8 F) S0 {  L1 _: x, W3 B) C4 g68
" N7 n4 s5 g& N: W6 ?69
1 I( H- O, m% I+ C70
% @0 j" p! y/ A71
1 T5 b1 x: z4 }; n2 L' Z8 _; b5 L726 Y0 O2 u, S% x# M0 F0 L6 B9 l/ t
731 [8 B  }3 H. }  f8 t( y  }6 t
740 C: p' @  f  \5 z, d' ~
75
) k2 K( _$ |+ Y# T+ Y$ V76! o# J+ q; E+ X) K  A+ D
77
  R4 C* y! n! R: B) c5 z788 k2 |8 [0 Y" g- ~* F$ d
79' ]8 o5 y  l" T5 C
80
/ Y0 z3 f& y. i1 Q+ o5 H. J$ W) y81
; h- T1 v+ X" ~5 J82
8 b3 `$ @/ `8 P, h: B) |, Y832 p" s3 R, R! q/ v; D  n- C
84
) d! r7 ]+ E) U) P- W) @85
2 ~0 B0 h! l( Y. w86: E& B6 C3 L: Z, i$ j2 q$ ?# [
87
6 k1 Y  x$ e* O3 @88- D# I/ ~* y4 V2 ?
89
6 {( J# S) z# A. e) N90
/ T: r  E& i0 c! K% }6 d91; F! O8 A" h6 W! B  [7 ?
92
  I3 G, s8 [8 ^/ V: N' k& V! ~  S93+ r  |0 x1 s8 K/ Y
94
" k  @  r, z0 A+ S, i& a& t950 _% [9 s" G( h  z! A
96* x" b( c7 b( ?3 v; h
97( S5 z' b3 Q5 V* |; G
98
' ]9 y+ K( S! k. N+ q3 D5 H99
* s0 h8 i5 W$ g* y. v7 z% [- O5 L100
2 d+ M9 I3 b# v8 u7 M) P! K101
/ {% z+ P5 k) X! B& E1025 o7 }9 ~" q, g; W$ J
103; o0 M6 |4 Z: U. p
（高斯核函数）
) f- X' M$ Q+ ?; l
: n* n9 v3 U0 E+ R5 _7 Q4 z2 j
4 s% U( x) I- M+ o# X9 X( _（K邻近法）
, T" `7 e0 x7 M4 ^7 T$ z( y/ X
- Z/ x  @# @8 {  g8 [+ }& j- }, s" d& j2 `$ |+ x4 j
四：谱聚类算法优缺点& ]0 b2 o& I: k* z1 r7 f$ [( M4 V  m) V
（1）优点9 j8 `, ?1 A' m) K+ y
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效: p6 y- ~: L2 `+ A; y5 t* m; Q
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
+ \* }* }7 L; M" I% D谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解6 s: H' I5 O. ]+ y1 s. {
（2）缺点( X: j+ A& N$ F4 U7 n, K9 W
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好  j9 }, \: p. w' Z3 K6 \3 n
聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
/ J! |  A; P3 l% h————————————————5 S: y& N  `( y. k% h; v5 K
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。- h/ E: h7 a3 s% x* {
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494+ S0 L6 |) j1 K

/ |  s& C2 g) S+ v* K7 z9 o- [  s2 P0 j9 v+ ]- z. |, R

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