顺德网站建设效果,国外比较有名的设计工作室网站,春暖花开 wordpress主题,网站界面设计图片【聚类】谱聚类详解、代码示例 文章目录【聚类】谱聚类详解、代码示例1. 介绍2. 方法解读2.1 先验知识2.1.1 无向权重图2.1.2 拉普拉斯矩阵2.2 构建图#xff08;第一步#xff09;2.2.1 ϵ\epsilonϵ 邻近法2.2.2 k 近邻法2.2.3 全连接法2.3 切图#xff08;第二步#xf…【聚类】谱聚类详解、代码示例 文章目录【聚类】谱聚类详解、代码示例1. 介绍2. 方法解读2.1 先验知识2.1.1 无向权重图2.1.2 拉普拉斯矩阵2.2 构建图第一步2.2.1 ϵ\epsilonϵ 邻近法2.2.2 k 近邻法2.2.3 全连接法2.3 切图第二步2.3.1 最小化 cut (A1, A2, . . . Ak)\text{cut (A1, A2, . . . Ak)}cut (A1, A2, . . . Ak)2.3.2 RatioCut 切图2.3.3 Ncut切图3. 谱聚类流程3.1 输入与输出3.2 一般流程4. 代码演示5. 总结6. 参考1. 介绍
谱聚类的基本原理
把所有数据看成空间中的点这些点之间可以用变连接起距离较远的两个点之间的边权重较低而距离较近的两个点之间的边权重较高通过对所有数据点组成的图进行切图让切图后的不同的子图间边权重和尽可能小即距离远而子图内的边权重和尽可能高即距离近。
难点
如何构建图如何切分图
2. 方法解读
2.1 先验知识
2.1.1 无向权重图 2.1.2 拉普拉斯矩阵 2.2 构建图第一步
2.2.1 ϵ\epsilonϵ 邻近法 2.2.2 k 近邻法 2.2.3 全连接法
比前两种方法第三种方法所有的点之间的权重值都大于0因此称之为全连接法。
可以选择不同的核函数来定义边权重常用的有多项式核函数高斯核函数和Sigmoid核函数。最常用的是高斯核函数 RBF。
2.3 切图第二步 其中Aiˉ\bar {\text{A}_i}Aiˉ 为 A\text{A}A 的补集。
进而如何切图使子图内的点权重高子图之间的点权重低
2.3.1 最小化 cut (A1, A2, . . . Ak)\text{cut (A1, A2, . . . Ak)}cut (A1, A2, . . . Ak)
一个自然的想法就是最小化 cut (A1, A2, . . . Ak)\text{cut (A1, A2, . . . Ak)}cut (A1, A2, . . . Ak)但是可以发现这种极小化的切图存在问题如下图
为了避免最小切图导致的切图效果不佳我们需要对每个子图的规模做出限定一般来说有两种切图方式第一种是 RatioCut第二种是 Ncut。
2.3.2 RatioCut 切图
对于每个切图不仅要考虑最小化 cut (A1, A2, . . . Ak)\text{cut (A1, A2, . . . Ak)}cut (A1, A2, . . . Ak)还要考虑最大化每个子图样本的个数即最小化 RatioCut函数
这里需要提一下hih_ihi是正交基但并不是单位正交基因为hiThi1∣Aj∣{h_i}^Th_i \frac{1}{|A_j|}hiThi∣Aj∣1而不是1。但是不影响后面结论。
2.3.3 Ncut切图 3. 谱聚类流程
3.1 输入与输出
输入样本集 D(x1,x2,...,xn)D(x_1, x_2,...,x_n)D(x1,x2,...,xn)邻接矩阵的生成方式降维后的维度k1聚类方法聚类后的簇个数k2输出 簇划分C(c1,c2,...,ck2)C ( c_1, c_2,. . .,c_{k2})C(c1,c2,...,ck2)
3.2 一般流程
根据邻接矩阵生成方式构建邻接矩阵W构建度矩阵D计算出拉普拉斯矩阵L构建标准化后的拉普拉斯矩阵D−12LD−12D^{-\frac {1}{2}}LD^{-\frac {1}{2}}D−21LD−21计算D−12LD−12D^{-\frac {1}{2}}LD^{-\frac {1}{2}}D−21LD−21最小的k1个特征值所各自对应的特征向量f将各自对应的特征向量f组成的矩阵按行标准化最终组成n × k1 维矩阵F对F 中的每一行作为一个k1维样本共n个样本用输入的聚类方法进行聚类聚类个数为k2得到簇划分C(c1,c2,...,ck2)C ( c_1, c_2,. . .,c_{k2})C(c1,c2,...,ck2)。
4. 代码演示
import numpy as np
import matplotlib.pyplot as plt
from sklearn import cluster, datasets
from sklearn.preprocessing import StandardScalernp.random.seed(0)# 数据构造
n_samples 1500
noisy_circles datasets.make_circles(n_samplesn_samples, factor0.2, noise0.05)
noisy_moons datasets.make_moons(n_samplesn_samples, noise0.05)
blobs datasets.make_blobs(n_samplesn_samples, random_state8)data_sets [(noisy_circles, {n_clusters: 3}),(noisy_moons, {n_clusters: 2}), (blobs, {n_clusters: 3})
]
colors [#377eb8, #ff7f00, #4daf4a]
affinity_list [rbf, nearest_neighbors]plt.figure(figsize(20, 15))for i_dataset, (dataset, algo_params) in enumerate(data_sets):params algo_paramsX, y datasetX StandardScaler().fit_transform(X)for i_affinity, affinity_strategy in enumerate(affinity_list):spectral cluster.SpectralClustering(n_clustersparams[n_clusters],eigen_solverarpack, affinityaffinity_strategy)spectral.fit(X)y_pred spectral.labels_.astype(int)y_pred_colors []for i in y_pred:y_pred_colors.append(colors[i])plt.subplot(3, 4, 4*i_dataseti_affinity1)plt.title(affinity_strategy)plt.scatter(X[:, 0], X[:, 1], colory_pred_colors)# plt.show()
plt.savefig(a.jpg)5. 总结
优点 谱聚类只需要数据之间的邻接矩阵因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到由于使用了降维因此在处理高维数据聚类时的复杂度比传统聚类算法好。 缺点 如果最终聚类的维度非常高则由于降维的幅度不够谱聚类的运行速度和最后的聚类效果均不好聚类效果依赖于邻接矩阵不同的邻接矩阵得到的最终聚类效果可能很不同。
6. 参考
【1】https://blog.csdn.net/qq_42735631/article/details/121010760
