查看: 3005|回复: 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])
% I  e( K$ S" \$ j return dist_matrix* E$ D6 a8 {0 A, S1 W& R

+ r# C, R2 o! v3 k, ]) R6 ]* Odef get_W(data, k):6 u, o4 X3 X' L$ m
# 获取邻接矩阵（K邻近法）" Q9 |( t% F/ D& [
n = len(data). {2 g" ^# j! K. n5 \
dist_matrix = get_dist_matrix(data)( Z: l  k! b$ _8 J' S4 Z
W = np.zeros((n, n))
# J1 x9 N( W9 X8 E, h for idx, item in enumerate(dist_matrix):( q) E, j- r  q% G$ O! [+ R! o
      idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表. S- c$ J0 z' v) `- A1 E. B
      W[idx][idx_array[1:k+1]] = 1# J4 V- N/ P3 u6 [+ u9 ?" t
transpW =np.transpose(W)2 B, s0 ?- }' h5 I; z7 V# A
return (W+transpW)/25 E% a0 J$ K  u/ y4 S
# H+ p5 j6 M. C9 O1 i1 s4 |! Z
def spectral_clustering(data_set, k):" L  P' f/ @* Q6 `
# 利用相似矩阵S得到邻接矩阵W/ {  w. T+ t& u; T
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）; L+ h( O/ b/ V
#  W = get_W(data_set, k)  # K邻近法. x/ k: c% x) h" d' j  R% y/ U

- e1 ^7 ?' K4 ?9 v0 p' p6 V" e # 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）
9 M/ z. Y9 x5 |* \% V7 R D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))' M. T. r9 A: r% G3 Q( v+ G* m

& H3 [# i5 v. c$ C5 h) z/ w # 计算拉普拉斯矩阵L=D-W
" g6 t9 u2 m+ p: e  T! C # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
/ ~4 c& L5 K' W3 w$ u# Y L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)
  }+ b6 ]/ _3 h, C! H# w4 {+ @% I: }% [9 e$ I* A( G
# 得到特征值和特征向量& g* q$ L* \6 \( j* @3 `
eigvals, eigvecs = np.linalg.eig(L)3 ~5 T! A1 T0 x( e$ y

" m6 N6 r: p" C* g& i3 s # 找到前k个最小的特征值（索引）& [& V/ N/ r8 N! W" J( t  b  A
k_smallest_eigvals_index = np.argsort(eigvals)[:k]9 T) ?; `( B5 J$ P2 w2 K
; r) r8 I& _# v: j; w5 {. m
# 取出这k小特征值对应的特征向量，并正则化
: h6 V! C6 b* M1 V" e+ g) T k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index])# B8 }1 Y6 L- i. t2 v  ~: X2 m$ Z+ [
0 X$ g& t7 b6 K
# 使用K_Means聚类
, w. v" [5 p% f return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)1 K5 v6 g/ u# @) J5 S+ c" g

) ]: k" G# W  Y# o7 [# Y
- ?4 Q4 f, D/ ^$ ]  P! Hraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)+ ?% M% X7 i+ b+ X1 F9 K: m
raw_data.columns = ['X', 'Y']3 I! ]; X+ V/ M" c  K
x_axis = 'X'
# ^! z5 {" I1 }y_axis = 'Y'
) P, k/ D! J  X1 \" o! a( }
0 ~. z3 V9 m5 a5 Nexamples_num = raw_data.shape[0]
/ B3 ~9 p, q: P+ Jtrain_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)  \% J' F0 y. _& n# S1 B1 Q
! H! j2 e- Y' V( F5 x

$ W& R+ w# i) ~* Y5 [1 jmin_vals = train_data.min(0)( z% w6 n6 X: Y3 h8 B
max_vals = train_data.max(0)1 u" d5 l" k: a- ?) u* N- ?5 W5 K
ranges = max_vals - min_vals
/ T1 M8 I9 n% Z8 c  ^; Jnormal_data = np.zeros(np.shape(train_data)), h( e4 J5 v/ g% O( {, }& F
nums = train_data.shape[0]# |; F8 Y+ i) Z  b3 ?7 w9 N8 p' n/ |
normal_data = train_data - np.tile(min_vals, (nums, 1))
& z2 j8 [, H, }4 Y. B/ p( lnormal_data = normal_data / np.tile(ranges, (nums, 1))0 R0 {3 |3 B7 h) o' t, g9 R  R9 m
3 P4 R% n, k# P3 \0 x. p
labels = spectral_clustering(normal_data, 2)
9 b; U% f) V* N2 T+ T  _+ W& P  V; K1 B6 m) V# J) s8 D
# 原数据
! k/ ]5 k1 Y- ^* i7 _" Cfig, (ax0, ax1) = plt.subplots(ncols=2)
) H8 ~- c, E" U3 q3 a! Z8 Kax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
3 M2 \2 Z6 `, T- q% Z2 b  Tax0.set_title('raw data')
4 p0 G, P$ }' M# 谱聚类结果6 B+ g# d# \/ `" d$ m8 }
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)
4 m% e, K1 F+ t4 V1 Gax1.set_title('Spectral Clustering')
( `& m+ {- p! [5 Z% D. f# M
& `( h# |' A$ q2 W( b' Y9 |plt.show()
( k" v% T3 d% b! k2 g( ?5 U3 [/ q9 W1 Q. f( e' z9 w
19 ~* I7 K' ~/ \, o
24 }5 W3 J- I. z6 Z8 c! z& h; \
3+ ^5 F" O% p* T/ {* @; X! Y, m
4. D4 i+ w0 P6 P8 V8 P
52 G7 @$ d1 W% E7 L4 j
6
( K+ c3 ]0 E1 \7
% d& D' C# N$ d( e1 t, f$ h8
3 ~  F$ ~+ Z+ y# z, G3 h0 i9/ I% _7 M! L6 x, E  E. c9 B( L
10% u% R. ]- ]; f5 n' y, L: }- k
11
! t3 o  ?3 Y3 m6 p/ j12* b  N8 i& c; z7 M) _! M( H5 b8 P
138 I2 y3 j( G% R9 R9 D# E
14
% O6 k0 U/ C% s; D! t8 v& M15( Q; Z8 I" j2 u4 J: \1 K5 A7 U
16' U& w; w2 f! e1 A1 ?+ w; V- f1 N) t
178 X' s4 {7 A: G$ U; A& E6 d: ~* P/ j
18
% b- G2 r; k2 ]- V0 r19
* y5 H1 U0 P# c7 M5 T  x/ B20/ f$ n- j8 D! ^
21
( }; v7 I: P4 K22
3 J. G6 H. E: q2 ^23# u; ~$ l* O( a* L5 x
248 {5 M/ J0 ]7 [) F) E+ K# C
254 Q: i  c7 P6 a5 V
26
2 O% v3 R/ Q+ T( ?; X+ e0 S1 M4 l27. j/ s/ ^8 ^) ^: k1 f% M
286 T% D, T/ ]! ^# K. o
296 y9 V& X9 N: p0 X  W4 ?% I
30
: m0 Z4 K3 b! f31
4 L) k2 q" W. e# p; h32& p* q4 q* q7 k( y1 k: L& N
33
, S4 V/ q1 ^: r7 ]% \+ x% F* x7 j34; s: }* A4 s4 S$ {) q8 x0 P
35
4 S9 [- E5 k/ R& v36# ~) [4 M, z1 Q5 l* u" m
37
0 H0 C7 x1 P; T/ J387 D1 u' @- N$ s1 V5 T0 q* S
39$ W/ b* }' f8 o9 B5 K4 i2 F
40
8 [8 `. v" S! |! ~5 i% p418 g7 @; X3 M) f  @8 G: n# R3 r
424 G) \' I3 M/ }' z; r
43
: z. n2 c6 `) W) U  M4 T& I44
! d& W7 b6 _  p9 m% k* y! Z' g' Y45
2 M0 x* ^% f1 W7 J  R! O46
" U3 Q- g7 @. v; e6 v( Z) N47) Z) M  W" u) W; U
48; x9 C9 i8 l" }4 w9 W- I
49+ \: `9 ?- F1 f, a2 L! t# a' B2 n  G9 ~4 m
50
- c5 A8 p5 K' L5 q6 [9 K* w% q518 {  `/ O; ], i9 S4 r# N, b( R
52* F& h2 g7 ?; E* A) b) S7 ^
53" g4 O4 J, J" d3 P7 q. _
54) m- W1 `9 _( G& H  |$ e) [0 P
55
! R, x$ O# ~$ N56) h' @( ]- |2 A( D9 `$ @+ O! v' ^
57; b* u- g; x, }
58
$ c0 H$ P$ J, y59
7 B( }: j& {! i60' z9 }/ W$ b% Z7 c
61# d' o2 T* @9 X3 _' i+ y
628 f5 N+ T  V% v) _
637 q7 C" Z7 |; ?- M" d
64) n( D; D( t6 K2 y
65
7 n# i4 s0 M% q+ ~66
! o2 {- T$ ?' N; Q67/ I7 x; t" o1 C) t3 z
68
2 o( m+ z8 Y. i# Q& w# ^, l) w  d69; Y4 U2 B- p% l/ d: {* u6 U) z
70
9 Y0 j4 P9 I% G& Z71
# k; U4 w9 S- i" V. ]$ O72) V7 R6 ?8 G/ Y4 D9 ~8 r( ~
739 \, K$ L1 f, t6 b4 h4 y/ T2 ~
74
3 J# \" y6 o1 \- d) ?4 ^$ B75- J4 V# q- x! C+ d2 Z% r% B
766 w- z! _+ @5 s  Z3 _: ?
773 s( b, D0 Q' i2 F' a0 B& K0 [
78
! T6 s9 k4 O. D7 m0 K79
# E7 m! p0 b5 u& p2 }80
/ E# m3 d2 R. V  S& M$ U" l. z& E& i81
8 r7 E: D1 [$ Q3 u0 K82
3 F- o5 p; @% R$ \% n) a& q83
4 J# P. J5 D: }84
! X: Z$ p7 @2 h: |4 A85
% [3 |8 F( E4 `9 j86
& l+ v- c: x/ y87
8 ~6 t( [& l. ]) \6 p  h) a88
$ C: O3 x) H) `4 y89* n" ]" n5 Q! @! A6 X
90
. L, ]; j( E( z9 H+ f6 s$ Y91
3 S7 n4 ^0 _; c& ]3 c& V! S92
! C& V: {9 R) e6 C9 k% C0 s, j5 g9 @93, B% y; L5 Q  [: ~+ ^# O
947 N3 j, V# [* L! r2 A( R
95
7 N5 u8 u3 u% ^% Y# g" j) \1 ]- Q96
. B, l1 ~- l- G. c97
9 ~5 B1 A7 E1 n6 c2 w9 }& T7 T98. J8 w! \0 x+ c( |3 N7 B9 H
99
2 a/ F) B4 _* I100
$ A0 f# k2 C; c; S) V0 t101
& \' U6 X- @& J  c6 C102
9 Q. S9 b1 {- n- D1038 |* ~& z4 |, C: v" p3 e0 Q/ U
（高斯核函数）
, B1 Q. b1 x9 @; K# U7 a3 o+ a3 C' I
6 j' f$ a( P' c' D1 u
8 X; {4 G# c3 h9 h9 p, j5 }# F（K邻近法）
- e6 |7 o& f- I
/ K7 A/ x1 y) T9 K# J& n
9 q. H$ Y: C5 b* ~$ p7 r: H四：谱聚类算法优缺点4 B, L/ b1 G% f7 S
（1）优点
. X" A; C# k' P9 c" H9 ?谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效
9 \2 A$ ~. N+ _1 Q+ `. \使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法. }0 {$ P$ D) S# W
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解# P1 a. R5 _% c2 a4 [
（2）缺点
; Y# y/ c- F* ]" ?* X0 L如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
: K) ~( }- G& q" o& G聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同
( Z. m% A, ]( E4 d9 d/ t+ V————————————————( r0 |+ b2 D( _4 ^- W
版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) D+ W* g/ h8 A$ k5 S) [原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494" F5 D9 e% |: o0 J1 O' _* {

. n, W$ z. \: t5 h" r" `8 E8 F% k0 r8 j5 k, ?% b