三维点云处理 3.5 聚类: Spectral clustering

一、gmm聚类方法失效GMM和K-means聚类方法在欧式空间中基于椭圆或圆形假设面对不规则数据分布时可能失效。二、普聚类普聚类通过图的连接性而非欧式距离进行聚类。同心圆示例中相距较远的点因连接性被归为同类而邻近点因缺乏连接性被划分至不同类别。月牙形数据同理连接性决定聚类结果。1.普聚类定义普聚类基于无向图节点间连线无方向性连线权重定义为节点相似度距离越近相似度越高相似度矩阵W对角线为零避免节点自连接矩阵元素wij表示第i与第j节点相似度2.如何构建图构建无向图及相似矩阵的三种方法全连接法所有节点间均建立连线权重为距离倒数KNN法单向KNN节点与最近k个邻居单向连接双向KNN仅当互为KNN时建立连接连线更稀疏半径邻域法仅连接距离小于阈值的节点权重函数需满足距离越近数值越大3.拉普拉斯矩阵矩阵类型定义物理意义相似矩阵Wwij表示节点i与j的相似度直接反映节点间连接强度度矩阵D对角阵元素为W对应行/列和节点所有连线的权重总和拉普拉斯矩阵LLD-W未归一化普聚类基础归一化拉普拉斯矩阵LsymD(-1/2)LD(-1/2) 或 LrwD^(-1)L用于归一化普聚类1) 未规一化普聚类未归一化普聚类流程构建相似矩阵W - 计算拉普拉斯矩阵LD-W - 选取L最小k个特征向量构成n×k矩阵V - 将V的每一行作为新特征yi∈R^k - 对yi执行K-means聚类 - 原始数据xi类别与yi一一对应关键点特征向量数量k需与目标类别数一致2) 规一化普聚类归一化普聚类流程与未归一化一致区别在于使用Lrw矩阵。核心步骤仍为构建矩阵、特征分解、K-means三部分。4.未规一化与规一化普聚类区别聚类类型优化目标分割倾向未归一化普聚类类别数据量均衡如黑色虚线保证两侧点数相近归一化普聚类类别密度均衡如红色虚线使两侧区域密度相近特征值gap可用于自动确定类别数k若第k与k1特征值差值显著增大则取k为最佳类别数。通常未归一化谱聚类在非标准化的稠密点中表现良好三、普聚类总结普聚类的本质是通过拉普拉斯矩阵处理的k-means算法其数学原理基于图论而非GMM或EM算法。核心要点时间复杂度复杂度为n³n为数据点数量主要源于对n×n拉普拉斯矩阵进行特征值分解的运算。后续k-means步骤的复杂度仅为线性O(n)。优点无类别形状限制可处理任意形状凸形、凹形等的聚类因其基于图论中的连接性而非欧式空间假设。维度无关性通过数据点转化为特征向量矩阵的行可适应任意维度数据而部分算法如Mean Shift、DBSCAN对高维数据效果较差。自动类别发现通过特征值分析可自动确定类别数量无需人工预设。缺点高计算复杂度如n10000时n³运算量极大。四、总结本节涵盖三种聚类方法方法空间假设形状假设需预设类别数其他特性k-means欧式空间圆形或球形是简单高效GMM欧式空间椭圆高斯分布是基于概率模型谱聚类图论连接性无限制否自动发现类别数但计算复杂度高SpectralClustering.py 代码逐段解释这份代码实现的是一种简单的谱聚类Spectral Clustering流程。它先把数据通过谱方法映射到低维特征空间再使用KMeans对映射后的特征进行聚类。1. 文件头与导入部分#!/opt/conda/envs/03-clustering/bin/python# 文件功能 实现 Spectral Clustering 算法importnumpyasnpfromsklearn.clusterimportKMeansimportmatplotlib.pyplotasplt#!/opt/conda/envs/03-clustering/bin/python指定脚本解释器路径。numpy as np用于矩阵、数组运算。KMeans用于对谱特征进行最后的聚类。matplotlib.pyplot as plt用于生成可视化图像。2.SpectralClustering类定义classSpectralClustering(object): SpectralClustering Parameters ---------- n_clusters: int Number of clusters Attributes ---------- 定义了一个谱聚类类。说明这个类支持设置簇数量n_clusters。3. 构造函数__init__def__init__(self,n_clusters2,**kwargs):self.__Kn_clusters self.__labelsNoneself.__K存储期望聚类数 K。self.__labels保存最终聚类结果标签初始化为None。4.fit方法谱聚类核心deffit(self,data):这个方法是谱聚类的主要实现按步骤说明如下。4.1 额外导入fromsklearn.neighborsimportkneighbors_graphfromsklearn.metricsimportpairwise_distancesfromscipy.sparseimportcsgraphfromscipy.sparseimportlinalgpairwise_distances计算数据点之间成对距离。csgraph.laplacian计算图 Laplacian。kneighbors_graph和linalg虽然导入了但在当前代码里只用了csgraph.laplacian。4.2 数据形状N,_data.shape获取数据点个数N和维度_。4.3 构造相似度矩阵AApairwise_distances(data)gammanp.var(A)/4Anp.exp(-A**2/(2*gamma**2))先计算欧氏距离矩阵A。gamma取为距离矩阵方差的四分之一作为 Gaussian 核宽度。用高斯核将距离转换为相似度exp(-d^2/(2*gamma^2))。这样A[i,j]越大表示点i与点j越相似。4.4 计算归一化 LaplacianLcsgraph.laplacian(A,normedTrue)csgraph.laplacian计算图的 Laplacian 矩阵。normedTrue表示使用归一化 Laplacian常用于谱聚类。4.5 谱分解eigval,eigvecnp.linalg.eig(L)对 Laplacian 矩阵做特征分解。eigval特征值数组。eigvec特征向量矩阵。4.6 选择谱特征idx_k_smallestnp.where(eigvalnp.partition(eigval,self.__K)[self.__K])featuresnp.hstack([eigvec[:,i]foriinidx_k_smallest])选择最小的K个特征值对应的特征向量作为新特征。这些特征向量构成了谱聚类的低维表示。np.partition用于快速选择第K小特征值的阈值。features最终是用这些特征向量拼接而成的矩阵。4.7 用 KMeans 聚类k_meansKMeans(initk-means,n_clustersself.__K,tol1e-6)k_means.fit(features)self.__labelsk_means.labels_将谱特征传入 KMeans。使用k-means初始化来提高聚类稳定性。聚类完成后把结果标签保存到self.__labels。5.predict方法defpredict(self,data):returnnp.copy(self.__labels)该方法直接返回fit后保存的标签。注意当前实现并未根据传入的data重新计算标签而是直接返回上一次fit的结果。也就是说predict只适合在同一数据集上调用。6. 数据生成函数generate_datasetdefgenerate_dataset(N300,noise0.07,random_state42,visualizeFalse):fromsklearn.datasetsimportmake_moons X,ymake_moons(N,noisenoise,random_staterandom_state)ifvisualize:...plt.show()returnX使用sklearn.datasets.make_moons生成“月亮形”二维数据集。noise控制噪声程度。visualizeTrue时绘制数据分布图。返回生成的特征X不返回真实标签y。7. 脚本入口if__name____main__:K2Xgenerate_dataset(visualizeFalse)scSpectralClustering(n_clustersK)sc.fit(X)categorysc.predict(X)forkinrange(K):plt.scatter(X[categoryk][:,0],X[categoryk][:,1],ccolor[k],labellabels[k])plt.xlabel(X)plt.ylabel(Y)plt.legend()plt.title(Spectral Clustering Testcase)plt.show()生成一个测试数据集X。创建SpectralClustering实例并调用fit。取回聚类结果category。绘制不同簇的点并显示聚类结果。总结这份代码的谱聚类流程是计算点间距离矩阵用高斯核把距离转为相似度计算归一化 Laplacian对 Laplacian 做特征分解选取最小特征值对应的特征向量作为新特征用KMeans对这些谱特征聚类