查看: 3033|回复: 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])* H4 x* {" `8 e& S, |
return dist_matrix
' E7 Y0 Z- Q5 J1 }  i% j) O. v9 t% w/ L9 \7 y& V( E
def get_W(data, k):
5 f! L+ K) h& z9 y/ O # 获取邻接矩阵（K邻近法）, ?+ \; u; I8 f7 M
n = len(data)
( K* M* U7 j! @3 K, r, k dist_matrix = get_dist_matrix(data)
8 O) J9 q" u& ^" F" R# x7 |5 V W = np.zeros((n, n))) l( c6 i) D- d0 ~2 }6 n7 d
for idx, item in enumerate(dist_matrix):
+ y& D2 ~0 @. R: `2 u2 E1 u* f       idx_array = np.argsort(item)  # 每一行距离列表进行排序,得到对应的索引列表$ `5 I3 X% F, B. r# T% q; x: I& j! t+ v$ n
      W[idx][idx_array[1:k+1]] = 1" E: x' n+ ^' T3 o$ e: F. z
transpW =np.transpose(W)! O, h% N/ O/ o9 K8 \6 _# C( ~
return (W+transpW)/27 v: T% \+ o0 Y% q1 Q8 b
* j4 t6 p& Q) ?9 u) z) X6 O; \0 \9 z
def spectral_clustering(data_set, k):
5 D, |9 _. p& l0 q6 E7 R) J  b # 利用相似矩阵S得到邻接矩阵W- a. |% Q  U: v; Z# D
W = get_affinity_matrix(data_set)  #高斯核函数（全连接法）
2 s; j# U6 K, z% l3 Q: | #  W = get_W(data_set, k)  # K邻近法
8 n4 S+ G1 [, H1 g* g9 D5 C6 r7 d1 j7 Y7 g8 O1 l# n) e. P4 k
# 计算度矩阵D,并得到矩阵D的1/2次方的逆矩阵（便于计算拉普拉斯矩阵）/ U6 a- {7 F. e: F4 x. t, h
D_inv = np.diag(np.power(np.sum(W, axis=1), -0.5))8 O0 M6 E7 J# \( j/ T) P

# D' i# V* M8 j5 \' u # 计算拉普拉斯矩阵L=D-W
  ~/ V9 a2 p+ F" M # 标准化拉普拉斯矩阵l = D_inv*L*D_inv=I-D_inv*W*D_inv
9 |2 ^* O. P, f9 y2 O5 _ L = np.eye(len(data_set)) - np.dot(np.dot(D_inv, W), D_inv)5 V* |( z: k; z4 F. Q) k: ^! p  r; e
2 |$ ^2 F$ v1 @* p/ I
# 得到特征值和特征向量+ S/ E9 \6 b' d5 F9 H# `- g
eigvals, eigvecs = np.linalg.eig(L)
; M! Q, L. E. w  |
1 S, e* H  O! H7 u% e # 找到前k个最小的特征值（索引）
1 Z2 C3 Z& Y% O: A' Z k_smallest_eigvals_index = np.argsort(eigvals)[:k]
; u" H* o% E9 u) n& Z$ M. r0 d) b1 D6 F& J: f; P% N7 }
# 取出这k小特征值对应的特征向量，并正则化
( c: G, F5 f2 Z4 C) J% A k_smallest_eigvecs = normalize(eigvecs[:, k_smallest_eigvals_index]); {' o4 H  P" O4 ?8 M
: R* H8 i2 H! O: {! ^
# 使用K_Means聚类# a3 D3 g6 ~  p
return KMeans(n_clusters=k).fit_predict(k_smallest_eigvecs)
$ p% Q. {& U$ Y
. n3 F# P/ a* V! _
% N% g- R3 k5 w& X3 ]6 rraw_data = pd.read_csv(r'E:\Postgraduate\Dataset\jain.csv', header=None)
9 \2 Y2 u3 |' E5 V/ [raw_data.columns = ['X', 'Y']/ f% w$ X0 W/ {9 X; S' m5 F
x_axis = 'X'% m: A  P" d  V2 f3 S& {
y_axis = 'Y'
' h3 L+ ]9 y; |: G5 ]2 ^2 k' G! p( V$ b' I# ]$ i4 J
examples_num = raw_data.shape[0]% J. o; L/ [- v
train_data = raw_data[[x_axis, y_axis]].values.reshape(examples_num, 2)* C! a3 ?/ U  O. F# v$ Z4 }" T
0 a# q: U6 r4 M: x; G/ Q% B3 t4 j9 c

" ]& I$ U" S/ p/ J( Umin_vals = train_data.min(0)( k* n' i# e/ T' a+ b
max_vals = train_data.max(0)5 D- N2 y1 N0 Q+ {( n! m6 w2 [% [
ranges = max_vals - min_vals
/ c$ `. F/ p! `0 Z% j# Nnormal_data = np.zeros(np.shape(train_data))6 ]9 P2 w) _, z6 d/ L, J0 Z
nums = train_data.shape[0]& L0 v3 Z+ h& T. I: M5 `5 g
normal_data = train_data - np.tile(min_vals, (nums, 1))
1 V( ^$ C& x7 |4 cnormal_data = normal_data / np.tile(ranges, (nums, 1))
* i7 P  U8 j' [5 y9 b' p* `7 j" _9 m2 p% [$ y9 Z. S( a! O
labels = spectral_clustering(normal_data, 2)( `" _$ j3 q5 y/ d# G" D+ v( N
. `" G2 I" z) u6 D
# 原数据
; q: l& Q3 ]. `& |; Ffig, (ax0, ax1) = plt.subplots(ncols=2)
5 @' B  g1 E5 m! F3 `2 Hax0.scatter(normal_data[:, 0], normal_data[:, 1], c='black')
4 u% L2 J4 b1 b) a9 }: u7 Max0.set_title('raw data')  X. P; {8 w, J. J
# 谱聚类结果7 o0 ]* `, I3 j" U
ax1.scatter(normal_data[:, 0], normal_data[:, 1], c=labels)2 x" J9 |! `- R( J( h( W8 a
ax1.set_title('Spectral Clustering')$ T$ F' L  K/ @2 D: T

- P- ~& q5 U8 U$ O7 T" eplt.show()* B/ c( H" X4 f0 t
: Y! M& D" t4 w: b. H
1
) q0 z: w& ]' {& l" }3 C2
* d/ o# s; T5 K! U$ s6 g3( q0 N: Q. x" |( k* ?
47 F* U5 d: u1 E6 D& d
5! N4 t/ e- p+ I
6# p  n0 A8 g9 r- I" E' {
7
. x. A' x6 R' X86 s1 D) Z0 r* q+ n
9# [6 T' Z) R  k1 k
10
# L" g2 b3 q  K2 Q11
1 H, n5 [; G4 d' u; Q! @9 l7 L0 g12
1 {; |$ G5 L: T! y13
* @/ C: p# V1 {" a  V7 W146 C4 x% K9 \' `" x
15
! R" k$ k" [# `) D167 Z& u3 [( G2 O( A: r
178 t6 l, h. m+ s
18: D: ~  O& B$ p  ~
19! d7 G6 m4 r; Y, `( `
206 J6 m1 i7 n9 S! e8 ^' f, @9 ?& y; ^
21# ~% l6 @$ P4 s; b' U6 Y/ w! D3 P
22
% d9 J; O; i3 p8 v6 j23
( O" H9 o# A2 d! o5 z24
3 L: h) L0 ?2 M% X' Y25
) d- Q& o3 \" |* f+ H26
* W% Y3 ]. S  v8 s+ C( U$ L; L27
) `" Z" C0 Q3 M& a# Q28
* ]/ y4 W3 Y9 u$ R294 v7 y$ n5 a3 Z" b6 [+ R7 }" ~0 n' k
302 j  p) f* B6 b0 M4 i
31; b- J7 e. B7 q6 a9 j) N
32
3 Q, b5 S/ O/ ^  B33
/ d7 k9 u  E. o) E& ~0 r347 L) A" j7 D% U
35
6 x+ h9 Z7 W  }6 R$ r36& h' h$ t8 c; r4 |7 q! q
37+ ^- z6 D* o) @2 V+ j- r1 D$ W
382 E7 F5 `% o+ d6 J7 N3 r/ B$ y
391 r% U! j1 {- p; _7 L/ i0 Y- I& }
40
' T% w: D* Z$ Q0 n+ B/ Q: O+ i  K( f41+ m# ]- @& P7 G( ^2 V; u6 T: l
42
" c# n( u( I, C6 \! }7 F0 U: A433 |5 r' m  `/ O
44
* k8 h1 I0 Y/ x' u& |45
: j+ b1 d5 E9 B3 y) h2 g46* w+ A  F3 X3 M; g2 }
47
, Y8 ~- w' f- B1 b; [5 g48
& [$ ]4 p1 a( Y' D, H49% O" W5 F- W* ?
50  Q1 L1 ?& h. R, x2 h2 O3 X- G
516 B+ {) m  u" s& A& H
52
* z5 r% F7 P  {  G' E5 @537 X* O* r4 K) Y* F& v; F" q. ~
54' J# V  Z4 l$ y# c6 }5 v, C
55
1 h% V$ g0 B  ^6 g- {2 [+ `566 b( u0 b2 V; b+ y/ w/ E$ [
571 i: [: _$ U5 T3 h9 t+ H, D. n) u
58( }- n; q$ V. ?3 ^7 @3 B
59) L  v2 M  f  g/ b! u( n) M
60
9 Z8 K/ W: R! g7 S& U61! {, r% Q) m$ y
62. \0 t5 f" b, m3 {( M" v
63, g9 T2 R: T( G, t7 V0 }, i3 J
64
* U- s2 N0 w; G$ `0 b- N65) U( ]. ^( E( m! F. C; W
661 y2 f0 t/ A! ]: ?
673 F: c' l( y1 j, G7 v
68
$ K, p" V  f: V# }+ f6 c69
: y9 W6 G  _" H: n% n! ~0 m70
3 s* I+ k8 j/ [  ^# a* r71- t: @) F3 j: j
72& y) l9 b! O' R3 k) a. R
73
* t+ s# ^6 [. t7 F1 x  U74' D4 ?3 f4 u0 I+ A! N
75
3 a) {* ^5 @8 ~: y76
+ G# T- B% o- y3 r6 C0 G77
3 g9 F. J5 x6 h" m( J% M78
" ]+ K- _! n5 R- q/ @, W79
: k* W3 z1 g+ |  _# c" \802 x+ u* s& ^2 Z4 f' c
81
+ K; n1 s& P9 ~+ [" e82
8 s2 F) N$ B5 e; @% p  O83
. l5 [7 ?/ {8 N/ \# J846 d: q1 k. p& c
85( Q/ J$ R5 p* o3 H3 G
86
5 f" e* I+ L# p4 d. F87
$ |9 u$ d6 [) g88
' l' k" L' g9 V! f; M2 {891 y# k1 k" c" H2 H+ D) F- E2 w* G' U
90
) C8 N! L1 m2 }$ F; J91% \5 ?" d% |) ]9 Z/ D- @; }) e9 Y
923 _2 q. C/ ~, c3 T3 o' ~7 F" ]( a
93% s8 H, C! r" f+ @4 W( t3 E5 R
94! b- J" Q" p* ~! c# X
95
5 d) y- O& ]: v" S! g7 G6 K96
3 _0 G: `7 e% X0 Y/ d0 s8 j97
! W+ `+ O, M3 k7 ~8 o& o, T' `98
+ m9 w- l/ a8 q, C6 ^1 O99
9 X6 m; u  c- Y! T100
4 c5 Y* M& q1 \1011 l+ d5 y, m3 W4 u# y" `1 a
102
- A$ I# E& g, U) L. r1037 d+ w  n& A6 n
（高斯核函数）
; A9 i7 }- G' `# S+ ^5 ~
" G% Z) m4 R& o
  S9 I% B; `' Z7 h( S（K邻近法）: k$ j: ], r5 K5 G
/ k. F7 r2 r- _& V" V2 `0 X4 R4 {( r
) T7 x. W1 S1 i8 I
四：谱聚类算法优缺点& {; t. Z3 d: |' y) q+ A
（1）优点4 g% g# G. F: I* y: r5 _
谱聚类只需要数据之间的相似度矩阵，所以对于稀疏数据的聚类很有效# w, k: f* D. j8 `$ h
使用了降维，因此处理高纬数据聚类时复杂度要明显低于传统聚类算法& k& @, L6 z4 V6 w. a
谱聚类算法建立在谱图理论基础上，与传统聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解5 Z5 D/ r/ ?! @( H- a5 R
（2）缺点
2 t( t6 h1 U1 q# H如果最终聚类的维度非常高，则由于降维的幅度不够，导致算法的运行速度和最后效果都不是很好
) |3 n1 H8 C# W( H, C聚类效果依赖于相似度矩阵，所以不同的相似度矩阵得到的最终聚类效果大不同相同" h+ F5 m) H1 L
————————————————
' w, x2 s( i$ a# t+ V: m, I: ^, l& G版权声明：本文为CSDN博主「快乐江湖」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 w, s- K( O) }* z3 m' z原文链接：https://blog.csdn.net/qq_39183034/article/details/126747494: q9 L' L; X1 W# s/ q+ L  s( r

+ L6 m4 Z( ~# a2 _3 L
( x2 a$ Y# }* ^) V" f/ z