查看: 3044|回复: 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])
; m6 j" H+ K+ t2 K return dist_matrix
8 O$ X5 r9 i* z( J9 @$ D1 ~% u, [% a) y
def get_W(data, k):
# O; Y$ X" a% N% v4 V  z # 获取邻接矩阵（K邻近法）0 e+ f, M3 E0 i, T/ b0 r9 B
n = len(data)) R9 ?0 [5 o6 l/ {" H/ w3 Z( o
dist_matrix = get_dist_matrix(data)# s$ R8 U3 z' M8 b
W = np.zeros((n, n))
1 A- d# p$ Q# X2 H; [ for idx, item in enumerate(dist_matrix):3 h& _4 b; }' X. @, c8 `( _
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表
5 ]% O, a5 E+ W8 O! x8 j: W       W[idx][idx_array[1:k+1]] = 1
9 i: q0 D" I, t- f, {9 w9 ` transpW =np.transpose(W)
* v+ a# C6 u" a1 U3 b4 u" u return (W+transpW)/2" _' g7 T' a0 D7 c9 Y. J( A( N4 d, P6 H
6 E9 Z5 L, Y. i% L
def spectral_clustering(data_set, k):3 G$ m$ n$ {- z' @" H- h' C
# 利用相似矩阵S得到邻接矩阵W
( u. T' D2 [7 l0 ], @9 D W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
  C6 E# U) R5 b! q #  W = get_W(data_set, k)  # K邻近法
1 P$ u9 i$ H* H* z# @- d( Y7 p/ c  K; v1 S$ K2 m" L+ ?
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
+ f% d! F& \9 L: B D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))/ R3 R4 b% N5 l2 e
" Q0 B" @; \0 F. q6 @
# 计算拉普拉斯矩阵L=D-W' Y; O# M( {1 Z0 L; ~8 D: l2 ~
# 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv/ {/ `( W" X: y
L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)& l- T0 Q! e* b, m7 T! p

  N! s! G/ X/ Q8 N  P6 b # 得到特征值和特征向量
  T0 h  t0 D  [: b4 ^) c eigvals, eigvecs = np.linalg.eig(L)
: ]$ j6 j% F2 `6 u. s* U7 u; g
8 a  m# i8 R! D9 S% D7 A$ d # 找到前k个最小的特征值（索引）
# @4 H! P9 B% `& A k_smallest_eigvals_index = np.argsort(eigvals)[:k]
- l; w) v& e; J. K- i. ]) h/ U4 Z) c. t% Y1 V6 `% K4 q
# 取出这k小特征值对应的特征向量，并正则化
7 T4 P: O) }4 ~; G* T, N0 \ k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])
- ?4 r& }% G+ [
9 M' ?1 @. U0 P& a' m5 i # 使用K_Means聚类
: k) ^) R3 W1 s5 ?) t) a& ~ return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)0 \6 ?; X# Q) m! t

" G5 N. X9 j7 a8 A% B- K' D
$ Z1 o% D. U( b$ N. j* x8 draw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)/ i$ Q3 M" ]8 f9 L8 f+ _9 N
raw_data.columns = ['X', 'Y']
+ |- b( m& R( g1 v1 s, E7 Yx_axis = 'X'7 h8 C/ n' a. g: O* ]9 S
y_axis = 'Y'% A9 i) R8 {7 o+ s5 q% v/ d$ p. f

( Q$ m% n/ |  Q$ I. `2 hexamples_num = raw_data.shape[0]
( L' p- y' e9 [% I7 r5 J% Ktrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2); k0 G- j3 T5 X7 W0 O; ^

* v2 N  [0 V8 y
" q& h* ]% s( U: [! @min_vals = train_data.min(0)
6 P6 L* Y# @; x$ Tmax_vals = train_data.max(0)$ p' P7 |  w8 g4 D# G- p% Y4 B' @
ranges = max_vals - min_vals
( }# p. a) j- hnormal_data = np.zeros(np.shape(train_data))
- `$ M) x, z7 d3 w; @! h+ h5 Z9 p7 ]nums = train_data.shape[0]
2 b6 ?( M- A6 O+ L/ L0 ?normal_data = train_data - np.tile(min_vals, (nums, 1))
: A& Z/ s2 C  v# V2 ~* R1 Znormal_data = normal_data / np.tile(ranges, (nums, 1))/ u1 }' B0 a* x* B

% J8 f0 x/ Y' X$ h0 Glabels = spectral_clustering(normal_data, 2)0 m/ z5 d3 D+ j% z& `; M' L
/ G2 p8 \5 x8 r# E. L
# 原数据
( d& f- Z& V- v( V9 x4 tfig, (ax0, ax1) = plt.subplots(ncols=2)
2 k" H* \' p  jax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
; K0 W& ^7 O* `2 R( [& B0 qax0.set_title('raw data')4 H: n' y# S1 I( s
# 谱聚类结果
/ C  m( R5 h2 \5 y5 z0 I( H0 qax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)/ g8 q5 A- V! T; e% o0 k
ax1.set_title('Spectral Clustering'), M' e5 t1 y* B5 Q0 A1 K5 T
1 \1 l& ]6 m, Y' o
plt.show()% T+ W5 k' g1 {* a% f' r8 K
; ^8 e& q% V8 Z: |5 ^
1
) C, l7 a( q) A+ v1 I  H! U27 ?1 y- H! t1 A! s1 F% b" a% R
3
7 v1 K& u" ]  e( k( j) ]7 \! f4) k7 j- i# g# C" P/ o3 J& ^8 Y$ N
5
6 H0 I% n+ T1 k% I6  r2 [0 {* G" a. B: U- K! B
7) Z* Y4 n( M, N8 D( M. ?
8
) j% u- J' G/ {9 ], [91 u4 J5 d6 q% I& W7 v8 X
10, a4 N" N1 W" _% i
11
7 f( Q5 o; Q) W3 l121 y9 H( {. G$ R, x
13' `7 K& g4 D' y+ S7 i2 s' I
14
+ P: x5 j( Z) H/ u7 z15
* t/ ?3 [7 Q9 j' ]165 I3 @; B$ Y6 e' B
17
" m# Z6 S, Q- }- X8 r5 f  j! A18
  ]5 ?, i/ `. [1 |19
* r6 v+ Q& L( O  O! J20, g9 T; ]% w4 }- }
21
" @3 v6 A3 E8 |0 W7 E4 y2 B22  K# L3 l6 O" }' Q: Y
23
  ?3 U* t! P& n' v$ F248 S1 V9 p; `7 H+ [( v" B
25/ H% G0 s( y9 T1 e9 {0 P& [  k
26
% A- m" |% [" O279 v0 D4 d- F5 R8 s& S2 F6 F
28
$ h# \; e' d7 d+ i0 s296 Z8 o8 W6 c* f, W' I
30
; i- a  X  E3 v* r. E$ K31
. Z$ F* G. P; g( }  `2 _& E32
! t6 P( P* ^0 i# g& H" B338 u1 O( v; ]. B5 `3 I' y& F* w
34
* P% G; B6 E7 C) r0 h6 s358 j" h6 \, Y9 T3 m8 R0 y
365 `9 p' i9 y. m3 q( Q0 \
37
9 r1 h7 G; @6 p38( e7 ^7 `; o. \1 ]! ?
396 Q, J% `" u& s5 B9 C: j
400 l, a' {! R5 j0 M6 K% f: Z8 U
41! b! x0 R# K* w, N" T! g& m; s8 C
427 E: ~. s- `! n2 E8 q& H1 y. \
43, \8 W* i) K& M7 W( [4 b
44
' W8 o5 K, q& _457 s; _+ ~8 Z  p: z3 K; s; I
46
, ]# l5 L1 G# V475 }% N( D4 q$ H) ]3 u% K
48
( I. n5 y& z8 T49, w7 l- v; B+ z0 v3 V
50
- _' f, g' @. u3 r% M0 x51* ?1 ]* Q+ T- T) y
52' s0 i6 r- `; t$ ^5 l8 u
53
7 E9 M2 A5 H8 O7 N9 @! Y& y54$ H# D' c7 f5 d' ]+ v- v7 H
55
% D' A! Y! t7 T4 J7 Y% H56
0 u) o0 w/ C7 C8 |; c" a57) F, |' V; Y1 U4 A, C( x( ^, B+ H
58
! I  a3 T7 z* O  w$ `59
0 w9 u" s; W: Q; E60
' s7 }. S* n/ B3 u8 E. |/ Q61
( k6 i9 g8 ^- S) u# L62
9 b. g/ r2 T; K8 B. H$ [* P' y63
  B  M$ Z$ N% B" R  N64& d# a7 C/ b3 ]' @  i) q. I
65
5 j9 k' p: P$ U, I& U5 o( a. a66" s. M3 \" \9 p0 w
67/ ~, Q9 P3 B* m* i) ~
68' h0 \/ @. X, @/ j
69
6 r0 I# u- _+ o; O6 |8 A1 H) b2 _70
3 J9 o5 B% S6 ]/ O. x712 a* a( Q5 x. L# u0 I9 v& I
72  g/ ^! U. ^" e' [4 I! ]. n4 W
73( L& j1 j" \+ D5 u
74; v" u# y# y* \# h8 A: N+ v
75
  |" u' p$ n5 O7 f) N761 `3 G( i) d7 v" v& u* f5 o, K: ?
77
% D% S" B# \( t/ u% a$ O78; V- M7 b3 U) m: M3 R! ]
79
! w$ Y" V) g( r9 `* y3 g80
/ ?* Q* j: h8 u4 Z2 o3 k81
+ {0 A: U+ }0 m7 _' ?; Z- u+ i822 N* d' M/ q( o) R
83' J" x2 j2 \0 `
84% U9 J) Y9 H' H$ A( n
85
2 n5 l  b! c9 Y/ N& U860 F1 [7 d5 ]* E! [0 U" `. a
87
1 K) B% H8 y. u% z' a88' o# q$ E1 o( i
89
3 b2 X2 V7 b6 F90$ t# x2 ]: @' ]& i' b" O3 F% _* ?
91
, {  u5 K+ _5 G5 X( Z92
% o7 ]6 G) g1 e' o938 z8 `1 k; `- g& r
947 Q6 o8 l0 c/ w8 U+ F7 h5 V
952 u4 ?3 I& d, R5 O; j3 |) d
96
- P# h& v2 f" M& b0 _97
$ L7 f( B& z( L% @8 {$ `98
' S- b) q0 I, v2 o$ J: e99( m1 ]; u  p$ h- C& u2 i. z
100  ?( e' G" R" A2 E
101; e1 N! \9 N7 N# D" z# w( f
102* i- ?  r# M. U( R+ k
103' E  K  t' v8 E, r
（高斯核函数）* q' D% ?! h5 {- m

1 g5 V6 t9 ~( k( H& n5 |$ I$ e! p, z
（K邻近法）
. {3 e* S% Y1 g# B+ ~- b1 ?
' d- T; j; l/ v6 `& \9 v& w) k& V2 c0 g) k8 b4 x+ B$ C( j* @
四：谱聚类算法优缺点
: U, y& H( B! O) t4 t. |- ?* M. C% j（1）优点1 t: q- z0 q+ D+ ^! B
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效8 S' m/ f- s6 s' E- Q3 h! D
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法
& j$ e+ e: e; A! f" W1 c" j谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解& n! ^' t/ o0 V4 U( j
（2）缺点& p8 s$ @( Z$ y" h% J/ s! `
如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
# z0 f/ Z) A# D( Y9 H( N聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同: k: E+ @; I+ j1 V' v/ y7 f0 a+ l
————————————————
% l" T  @8 P: D8 d, L% k& q  i版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。$ g6 u. s0 S0 C  R
原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494+ ^! `4 a2 X* H
6 C) w1 n  c" s% `/ p! X; e( a; P
/ o: `7 V7 b/ o+ e; c- i% Q