查看: 3071|回复: 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])$ [# j8 s* Q9 M* E
return dist_matrix- v6 A6 B- i- L. r; t5 A) X

" n2 Z- D# t3 X. E5 e1 @& @) q) K: xdef get_W(data, k):
; r% _+ e/ m7 Y& E/ J # 获取邻接矩阵（K邻近法）
2 y# e6 i8 q2 b: T* J n = len(data)
) l; B+ v1 {9 v" {, Y dist_matrix = get_dist_matrix(data)
" d1 l8 b5 O! q7 f0 E; z+ k W = np.zeros((n, n))& A; C# O8 Z" F2 U; |- m, k
for idx, item in enumerate(dist_matrix):
1 r' t1 d5 ]% a, h2 t       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表% S. {% |( v! |# \
      W[idx][idx_array[1:k+1]] = 1
7 j/ k; {9 U/ t! p# d transpW =np.transpose(W)
' j; a" Y( A3 R  I5 h/ ]1 H, F5 ` return (W+transpW)/2
  e% J" d& d, O3 H' V# \! t0 e& l% F6 V& S: b( W
def spectral_clustering(data_set, k):( ]+ [3 x' y2 g/ I" ?
# 利用相似矩阵S得到邻接矩阵W
9 K5 u0 v. W5 Q7 g& H W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）6 x& R8 `( d  z, J) y- {) T
#  W = get_W(data_set, k)  # K邻近法
* N5 `! Z$ @" X9 {+ ^
1 S! x7 ^8 F: P3 A # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）! M! {' K% v0 J2 e+ n$ ^
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))5 e3 \! u" `0 K) m8 ]

$ {; i5 i: I/ X$ c6 d* ? # 计算拉普拉斯矩阵L=D-W4 r: t8 Q7 Q  f* @6 {
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv. F: w/ P$ B1 M* e' Z6 d% F
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv), c! v$ c, o6 a7 o7 F1 P
% ^$ f8 X; Q3 x1 ^2 x3 m( [
# 得到特征值和特征向量
' l+ `) e9 k* l$ D eigvals, eigvecs = np.linalg.eig(L)
, E- w. O' P5 Q, F# t% L3 D0 M* `2 y0 X* e0 ?; a+ ^- T
# 找到前k个最小的特征值（索引）
2 e$ v6 X( c* G: P) s% P k_smallest_eigvals_index = np.argsort(eigvals)[:k]  r; [" ~# g# Y: V3 [4 Q, M8 e

' t  t. j" l4 G- [% |, ^. e- C # 取出这k小特征值对应的特征向量，并正则化
5 S0 m1 b& d4 O' _6 ]; p; _3 ^ k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])/ g$ j# C, Y9 p! m, S, ~

( [. S, i9 D" R. N8 K7 t' G # 使用K_Means聚类: Y1 H. R+ v6 J# w" X. c2 Y1 c
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
7 W4 q, D2 W7 V# Z# S7 X/ Z! X$ b' n' M
$ e% o( [0 u4 n& D& c: m& u% N
raw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
- ?% T" w8 @) ]9 r$ M3 g  I0 @) Draw_data.columns = ['X', 'Y']% k- }+ L0 `) E& A, i
x_axis = 'X'2 H' T; M) R6 L
y_axis = 'Y'6 }1 N  I6 W, w( y1 w/ B( `
9 O" J& z% E& ~
examples_num = raw_data.shape[0]
2 _5 P7 o5 s7 D* {train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)
' H3 G+ ]' G5 ]" Y3 J4 N, O2 ]" a) k# ^

) a1 Q: X8 C8 O5 |; tmin_vals = train_data.min(0)" y* k7 W, a, ^# i$ D
max_vals = train_data.max(0)
8 q( X) p  Q: granges = max_vals - min_vals) I6 s" A, E! X0 y' T: W* j. k" x
normal_data = np.zeros(np.shape(train_data))
/ G" G& c- V  O" ^. tnums = train_data.shape[0]
3 u1 F! P' u4 p3 n& fnormal_data = train_data - np.tile(min_vals, (nums, 1))
+ x  _2 T, G& F0 ]  y7 Qnormal_data = normal_data / np.tile(ranges, (nums, 1))
. C" j" n" e  m$ @3 C; ]
9 M0 |3 j: S% `7 ulabels = spectral_clustering(normal_data, 2)* H# k% B& F  ~$ q5 Q7 i
3 I) H7 R% P! }3 a" M
# 原数据* p% @, v2 n( }& A6 T4 z0 g
fig, (ax0, ax1) = plt.subplots(ncols=2)
. A, J2 Y6 J4 i: d) |; w( X# iax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')0 L/ Y$ N" |7 s$ c; S6 x
ax0.set_title('raw data')
% m0 b" T6 }% K+ [# 谱聚类结果. y& C6 }! h# f: F/ a) v
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)* l: }! N& Y8 c: ?- N
ax1.set_title('Spectral Clustering')) f5 _' F/ E( }0 Z: y

& @# O; N  N7 a; }, vplt.show(): t+ @+ o! ]$ r* s) L

( L! x3 p! J; W. k7 {18 W4 l  J$ \5 z3 ?. L
2
- [( m6 E" O* q( s& B) b3! |0 J2 ^1 C( v0 x+ i% {
48 ]4 G* q: j$ ?: W/ X. ~( W4 R
5
' Q  p5 x8 q, u1 k) l64 y" L8 [1 }# r$ j) u
7
* h, X+ [" R6 T$ d- p) n5 O" m8
) U; U( t. j# z9 b$ O9& s* i! |. d3 K: a* P
10
: m3 F, P7 M' h. |# i11
* J( J: B7 Y9 Q+ M, N12
- P# D# m+ I1 Y135 v+ `6 l: z; T$ @3 d7 u
14
) m0 Q  H1 S( u2 w: {& [" z! i9 S15
1 y  f7 ?+ Q+ v# h* n2 ]3 j164 j1 T, p  A5 w
17
  Y% I% n  [  @3 P% ]+ {$ T4 E8 C188 E) U- a  o8 ^" c/ P* ?
19
- |) S+ R# I+ r( J20
$ E1 y8 G: H$ g8 f) h21
0 H2 l+ z( b$ @( U/ b220 v( v0 \( r0 w2 o0 C4 ]
23
) S4 d  z  B! O1 _/ `2 n245 y" s4 G/ ]2 m( L0 g' y
25, T. p2 L* x4 G" e8 W" u
26) Q" k: f0 l3 q9 e' g
27
. ?& T! _5 P1 T28
' u4 t- c+ H4 l! o  m3 r6 x299 e# K+ H: S0 N! y" g5 F2 {( B
30
+ e2 ]3 k0 q0 y& G$ Y! \% D' x* v31
" c; z* n" c) j+ Z" {. J" G32& z  z5 V( v% Z- O* u% @' h5 \, Z
33
; i  L- \4 p# c: a  I( l7 x& c348 W$ p* m( o8 k7 F: `$ j: C
356 h& ?# x# L+ L+ {$ b$ X. A
366 V( X0 ^: z( u
37- M! E5 e" ^4 G) n# G3 ]
38
: H1 l& P* c$ N* Z393 j% X( Y6 w) J
404 o& J& z2 a% e" b9 M5 m
41
6 o7 y3 z& ?% i- K! }423 e; i5 v4 v) `2 s( C* s$ D/ z
43! D# y4 u+ t) q# d% U0 Z7 x
44
# Q$ a4 b# E5 @+ i& f45
/ r1 O. E7 P) Y( Z- }46
: {1 K( E2 f: C1 x% ~  E7 B47
) D8 z9 B& ^9 x48
# T4 {" ~* d: n1 O49
2 ?2 a! d/ g- [; n6 }509 Z5 d# L/ A% u7 L
51
" r' w9 x) Y5 I) C% E1 y% R52
1 y2 c. B' r2 G$ x53
7 p- {- Y2 Z9 M) |* w+ \, b54
& {) j5 _7 p2 S) P; a55, D$ m( W9 f4 H1 a
56
# b8 Q! n7 f: l57
% I: u; K/ v& U$ k! E7 o# ]589 `1 ~2 W( W# @+ ^! v) ~4 A( l. F
594 z9 b8 d1 }( Z" a3 y
60
9 I0 P) h" u- S- k61
2 b% L/ o: D' t. a5 F9 d9 d62
0 s6 a# ]  O8 T63/ p$ t3 w7 J' X
64" N) b* z2 ?7 T5 a+ V2 n3 a1 u
65  E1 K! c0 k7 P
668 l2 U/ J1 Q. A. i, c9 f1 H# o
67: e4 q. [2 M! Q) o# s8 Q3 x
68( A4 J" K# Q, x$ o: k; M: p
69
& [* E7 n8 n, ~$ s9 A, ^# q702 Q5 Y' y3 Q8 p& G8 s
71' p2 H8 O% ]" @- j' w& ]
72
  h. p. j) {- i& L# X# c6 x, d* v73% k5 [, B" D  q1 x4 Q: f
74
: x3 w, ?8 E1 d& Q) p$ ^75# d$ L! g- u' v5 z0 t* o- T8 v
76' }# e; m  G3 P+ W# D3 v; n& {
77- c& A( N* I8 R- u2 u4 P+ c- \
78/ [$ B0 i% t+ _2 d" ~
79
2 j# j3 m8 f2 N80
8 s) {* e9 k! |$ S% l81
2 @0 Q, O) {6 I- W* Q82
1 {3 b8 J0 Z/ c6 Z83, P- w% j- [/ D' {) d
84: E" h! A8 c2 U2 \1 h
85
# Q7 b6 e9 c4 D8 Y: `4 {86
# m8 D9 D' m: |7 v& j87
7 G# O: d* j9 Z% o  I. ]! x! \88: ?# t' @) P2 v( X0 S/ X% @
89
& ]. H2 Q+ a+ l5 V- P900 f4 [. s" B3 ]& R6 A6 y- g
91. e8 ?6 s7 R/ y4 x+ K: {0 U
92( J, r4 i* Y4 }
93
* m5 t4 l' B- D2 v0 w$ A. d$ P. P94/ [2 }, F: i0 h. o; j' i& P
95
# H* G5 @5 T- ?0 Y0 `9 o' I96; ^7 {' Y8 M6 P$ `1 V" g
97
' M+ s4 N  F5 ]+ P98
# m) v; p) B# L" j- F) r99/ f+ k6 |' N; E- Y/ j
100
7 q% P" ^) {0 T1 h. t0 Q101; G# y! [  H+ |. {# b
102$ g+ s. x8 s1 j* E
103
0 s/ J' b' u' [4 ?" P（高斯核函数）
+ r: T9 S, r% _' Z. i% \' K5 J! u! s: z! U2 w

% D5 l* O$ u2 u. a5 e  \' O# H（K邻近法）8 m0 o5 s5 o4 \! [9 `7 x! q4 H
% C( F% ^! K! \& a
9 @% W9 \% U' O
四：谱聚类算法优缺点6 U' c* ]* }: B" k* H9 ?5 X6 o
（1）优点
( I7 ^, C" Z6 s. f, R" f谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
9 A- e% y: y& @使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
/ m& F! D1 H5 z- `$ X  }' Q# K谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解
3 b) ?) q' B' F7 J& |（2）缺点3 {8 \& }) b6 k
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
3 |" a( o0 w& k# l聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
" {  u, e" M% @  @2 F5 u' H) k————————————————: y3 }  g& f+ S1 m" E
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 a% ^! `. s) k4 Y2 T原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494
1 f2 k: R% H! g. D* {/ L! p% q
: [/ i' E& m# j& O1 H5 x- h* }5 B; O  ~1 S