Voronoi图与k-means聚类的几何舞蹈从劳埃德松弛到数据分群的实战解析在数据科学领域聚类算法如同一位隐形的雕塑家将无序的数据点塑造成具有意义的形态。而在这其中k-means算法以其简洁高效著称成为数据分析师工具箱中的常客。但鲜为人知的是这个看似简单的算法背后隐藏着一幅精妙的几何图景——Voronoi图与Delaunay三角剖分的数学之美。本文将带您深入探索这一几何与算法的奇妙联结揭示劳埃德松弛算法如何通过分配-更新的优雅舞步为数据点带来均匀分布的按摩效果。1. Voronoi图空间划分的自然语言想象一片草原上分布着几处水井每只动物都会选择距离自己最近的水源饮水。这种自然的归属关系正是Voronoi图所描述的数学现实——将平面划分为若干个区域每个区域包含距离特定生成点最近的所有位置。1.1 数学定义与几何特性给定平面上一组离散点集P{p₁,p₂,...,pₙ}Voronoi图将空间划分为n个单元Vᵢ满足Vᵢ {x | d(x,pᵢ) ≤ d(x,pⱼ), ∀j≠i}其中d(x,y)表示距离度量通常采用欧几里得距离d(x,y) √[(x₁-y₁)² (x₂-y₂)²]Voronoi单元具有以下关键性质凸性单元内任意两点的连线仍完全包含在该单元内局部性每个单元仅由其邻近生成点决定边界特性单元边界是相邻生成点连线的垂直平分线1.2 距离度量的视觉影响距离函数的选择会显著改变Voronoi图的形态特征。下表对比了常见距离度量下的Voronoi图差异距离度量公式单元形状特征典型应用场景欧几里得L₂范数凸多边形平滑边界空间分析、图像处理曼哈顿L₁范数直角多边形锯齿状边界城市路径规划、棋盘游戏切比雪夫L∞范数矩形边界45°对角线机器人导航、像素分析马氏距离√[(x-y)ᵀΣ⁻¹(x-y)]各向异性椭圆统计分类、异常检测import numpy as np from scipy.spatial import Voronoi, voronoi_plot_2d import matplotlib.pyplot as plt # 生成随机点集 points np.random.rand(30, 2) # 计算Voronoi图 vor Voronoi(points) # 可视化 fig voronoi_plot_2d(vor) plt.plot(points[:,0], points[:,1], ko) plt.title(欧几里得距离下的Voronoi图) plt.show()注意在实际应用中Voronoi图的边数可能远多于生成点数因为一个生成点可能被多个Voronoi边包围。2. Delaunay三角剖分Voronoi的对偶图景如果将Voronoi图中相邻单元的生成点连接起来就会得到一幅令人惊叹的网状结构——Delaunay三角剖分。这种对偶关系不仅是数学上的优雅存在更为计算几何提供了实用工具。2.1 定义与空圆特性Delaunay三角剖分满足独特的空圆准则对于任意三角形其外接圆内不包含其他数据点。这一性质带来了两个重要优势最大化最小角避免了瘦长三角形提高了网格质量局部最优性三角剖分在整体上达到角度最优配置2.2 计算与应用实践从Voronoi图到Delaunay三角剖分的转换可通过以下步骤实现对每个Voronoi顶点找到其对应的三个生成点连接这些生成点形成Delaunay三角形确保每个三角形满足空圆特性from scipy.spatial import Delaunay # 计算Delaunay三角剖分 tri Delaunay(points) # 可视化 plt.triplot(points[:,0], points[:,1], tri.simplices) plt.plot(points[:,0], points[:,1], o) plt.title(Delaunay三角剖分) plt.show()在三维建模中Delaunay三角剖分常用于生成表面网格。以下是一个典型的工作流程采集物体表面的点云数据执行Delaunay三角剖分移除不符合物体几何特征的三角形对网格进行平滑和优化处理提示在处理大规模点云时可采用分治算法将复杂度从O(n²)降低到O(n log n)3. 劳埃德松弛算法数据点的均衡之术劳埃德松弛算法如同一位耐心的按摩师通过反复调整将杂乱的点集变得均匀有序。这一过程与k-means聚类有着惊人的相似性揭示了数学在不同领域的统一美。3.1 算法步骤解析劳埃德算法的每次迭代包含两个关键阶段Voronoi划分阶段根据当前生成点计算Voronoi图将空间划分为多个Voronoi单元质心迁移阶段计算每个Voronoi单元的质量中心将生成点移动到对应单元的质心位置def lloyd_relaxation(points, iterations5): for _ in range(iterations): vor Voronoi(points) new_points np.zeros_like(points) for i in range(len(points)): # 获取当前点的Voronoi区域 region vor.regions[vor.point_region[i]] if not region or -1 in region: # 检查无效区域 new_points[i] points[i] continue # 计算区域顶点坐标 vertices vor.vertices[region] # 计算质心 new_points[i] vertices.mean(axis0) points new_points return points # 执行劳埃德松弛 relaxed_points lloyd_relaxation(points.copy(), iterations10) # 可视化结果 vor Voronoi(relaxed_points) fig voronoi_plot_2d(vor) plt.plot(relaxed_points[:,0], relaxed_points[:,1], ro) plt.title(经过劳埃德松弛后的Voronoi图) plt.show()3.2 收敛性与终止条件随着迭代进行劳埃德算法会逐渐达到稳定状态。我们可以通过以下指标判断收敛质心位移量当最大位移小于阈值ε时停止能量函数最小化∑(x - cᵢ)²其中cᵢ是最近质心迭代次数设置最大迭代次数作为安全保障下表展示了不同终止条件的效果比较终止条件优点缺点适用场景位移阈值精度可控可能陷入局部最优高精度需求能量变化反映整体优化计算成本较高理论研究固定迭代确定性高可能过早或过晚停止实时系统4. k-means聚类的几何视角将劳埃德算法中的概念迁移到k-means聚类我们会发现两者本质相同——都是在交替执行分配和更新两个步骤只是换上了数据科学的外衣。4.1 算法对应关系Voronoi概念k-means对应数据意义生成点聚类中心数据模式代表Voronoi单元聚类划分数据归属关系质心计算均值更新中心点优化4.2 Python实现与优化以下是利用Voronoi图思想实现的k-means算法from sklearn.cluster import KMeans from sklearn.datasets import make_blobs # 生成模拟数据 X, y make_blobs(n_samples300, centers4, cluster_std0.6, random_state0) # 执行k-means聚类 kmeans KMeans(n_clusters4, initrandom, n_init10) kmeans.fit(X) centers kmeans.cluster_centers_ labels kmeans.labels_ # 可视化聚类结果与Voronoi图 vor Voronoi(centers) fig voronoi_plot_2d(vor, show_verticesFalse, line_colorsorange) plt.scatter(X[:,0], X[:,1], clabels, s50, cmapviridis, alpha0.6) plt.scatter(centers[:,0], centers[:,1], cred, s200, alpha0.8) plt.title(k-means聚类与Voronoi图) plt.show()算法优化技巧初始化改进采用k-means策略选择初始中心提前停止当中心点移动小于阈值时终止迭代并行计算利用多核处理加速距离计算近似算法使用MiniBatch k-means处理大数据4.3 多维扩展与实用考量在高于二维的空间中Voronoi单元变为多维凸多面体但核心概念保持不变。实践中需要考虑维度灾难高维空间中距离差异减小影响聚类效果距离选择针对数据特性选择合适距离度量聚类验证使用轮廓系数、Davies-Bouldin指数等评估质量以下是一个三维Voronoi图的示例代码from mpl_toolkits.mplot3d import Axes3D from scipy.spatial import Voronoi # 生成三维点集 points_3d np.random.rand(20, 3) # 计算3D Voronoi图 vor_3d Voronoi(points_3d) # 可视化 fig plt.figure(figsize(10, 7)) ax fig.add_subplot(111, projection3d) # 绘制生成点 ax.scatter(points_3d[:,0], points_3d[:,1], points_3d[:,2], cb, s20) # 绘制Voronoi边 for simplex in vor_3d.ridge_vertices: simplex np.asarray(simplex) if np.all(simplex 0): ax.plot(vor_3d.vertices[simplex, 0], vor_3d.vertices[simplex, 1], vor_3d.vertices[simplex, 2], k-) ax.set_title(三维Voronoi图) plt.tight_layout() plt.show()提示在实际数据分析中通常需要先进行PCA等降维处理再可视化高维聚类结果
Voronoi图与k-means聚类：用劳埃德松弛算法给你的数据点做个‘均匀按摩’
Voronoi图与k-means聚类的几何舞蹈从劳埃德松弛到数据分群的实战解析在数据科学领域聚类算法如同一位隐形的雕塑家将无序的数据点塑造成具有意义的形态。而在这其中k-means算法以其简洁高效著称成为数据分析师工具箱中的常客。但鲜为人知的是这个看似简单的算法背后隐藏着一幅精妙的几何图景——Voronoi图与Delaunay三角剖分的数学之美。本文将带您深入探索这一几何与算法的奇妙联结揭示劳埃德松弛算法如何通过分配-更新的优雅舞步为数据点带来均匀分布的按摩效果。1. Voronoi图空间划分的自然语言想象一片草原上分布着几处水井每只动物都会选择距离自己最近的水源饮水。这种自然的归属关系正是Voronoi图所描述的数学现实——将平面划分为若干个区域每个区域包含距离特定生成点最近的所有位置。1.1 数学定义与几何特性给定平面上一组离散点集P{p₁,p₂,...,pₙ}Voronoi图将空间划分为n个单元Vᵢ满足Vᵢ {x | d(x,pᵢ) ≤ d(x,pⱼ), ∀j≠i}其中d(x,y)表示距离度量通常采用欧几里得距离d(x,y) √[(x₁-y₁)² (x₂-y₂)²]Voronoi单元具有以下关键性质凸性单元内任意两点的连线仍完全包含在该单元内局部性每个单元仅由其邻近生成点决定边界特性单元边界是相邻生成点连线的垂直平分线1.2 距离度量的视觉影响距离函数的选择会显著改变Voronoi图的形态特征。下表对比了常见距离度量下的Voronoi图差异距离度量公式单元形状特征典型应用场景欧几里得L₂范数凸多边形平滑边界空间分析、图像处理曼哈顿L₁范数直角多边形锯齿状边界城市路径规划、棋盘游戏切比雪夫L∞范数矩形边界45°对角线机器人导航、像素分析马氏距离√[(x-y)ᵀΣ⁻¹(x-y)]各向异性椭圆统计分类、异常检测import numpy as np from scipy.spatial import Voronoi, voronoi_plot_2d import matplotlib.pyplot as plt # 生成随机点集 points np.random.rand(30, 2) # 计算Voronoi图 vor Voronoi(points) # 可视化 fig voronoi_plot_2d(vor) plt.plot(points[:,0], points[:,1], ko) plt.title(欧几里得距离下的Voronoi图) plt.show()注意在实际应用中Voronoi图的边数可能远多于生成点数因为一个生成点可能被多个Voronoi边包围。2. Delaunay三角剖分Voronoi的对偶图景如果将Voronoi图中相邻单元的生成点连接起来就会得到一幅令人惊叹的网状结构——Delaunay三角剖分。这种对偶关系不仅是数学上的优雅存在更为计算几何提供了实用工具。2.1 定义与空圆特性Delaunay三角剖分满足独特的空圆准则对于任意三角形其外接圆内不包含其他数据点。这一性质带来了两个重要优势最大化最小角避免了瘦长三角形提高了网格质量局部最优性三角剖分在整体上达到角度最优配置2.2 计算与应用实践从Voronoi图到Delaunay三角剖分的转换可通过以下步骤实现对每个Voronoi顶点找到其对应的三个生成点连接这些生成点形成Delaunay三角形确保每个三角形满足空圆特性from scipy.spatial import Delaunay # 计算Delaunay三角剖分 tri Delaunay(points) # 可视化 plt.triplot(points[:,0], points[:,1], tri.simplices) plt.plot(points[:,0], points[:,1], o) plt.title(Delaunay三角剖分) plt.show()在三维建模中Delaunay三角剖分常用于生成表面网格。以下是一个典型的工作流程采集物体表面的点云数据执行Delaunay三角剖分移除不符合物体几何特征的三角形对网格进行平滑和优化处理提示在处理大规模点云时可采用分治算法将复杂度从O(n²)降低到O(n log n)3. 劳埃德松弛算法数据点的均衡之术劳埃德松弛算法如同一位耐心的按摩师通过反复调整将杂乱的点集变得均匀有序。这一过程与k-means聚类有着惊人的相似性揭示了数学在不同领域的统一美。3.1 算法步骤解析劳埃德算法的每次迭代包含两个关键阶段Voronoi划分阶段根据当前生成点计算Voronoi图将空间划分为多个Voronoi单元质心迁移阶段计算每个Voronoi单元的质量中心将生成点移动到对应单元的质心位置def lloyd_relaxation(points, iterations5): for _ in range(iterations): vor Voronoi(points) new_points np.zeros_like(points) for i in range(len(points)): # 获取当前点的Voronoi区域 region vor.regions[vor.point_region[i]] if not region or -1 in region: # 检查无效区域 new_points[i] points[i] continue # 计算区域顶点坐标 vertices vor.vertices[region] # 计算质心 new_points[i] vertices.mean(axis0) points new_points return points # 执行劳埃德松弛 relaxed_points lloyd_relaxation(points.copy(), iterations10) # 可视化结果 vor Voronoi(relaxed_points) fig voronoi_plot_2d(vor) plt.plot(relaxed_points[:,0], relaxed_points[:,1], ro) plt.title(经过劳埃德松弛后的Voronoi图) plt.show()3.2 收敛性与终止条件随着迭代进行劳埃德算法会逐渐达到稳定状态。我们可以通过以下指标判断收敛质心位移量当最大位移小于阈值ε时停止能量函数最小化∑(x - cᵢ)²其中cᵢ是最近质心迭代次数设置最大迭代次数作为安全保障下表展示了不同终止条件的效果比较终止条件优点缺点适用场景位移阈值精度可控可能陷入局部最优高精度需求能量变化反映整体优化计算成本较高理论研究固定迭代确定性高可能过早或过晚停止实时系统4. k-means聚类的几何视角将劳埃德算法中的概念迁移到k-means聚类我们会发现两者本质相同——都是在交替执行分配和更新两个步骤只是换上了数据科学的外衣。4.1 算法对应关系Voronoi概念k-means对应数据意义生成点聚类中心数据模式代表Voronoi单元聚类划分数据归属关系质心计算均值更新中心点优化4.2 Python实现与优化以下是利用Voronoi图思想实现的k-means算法from sklearn.cluster import KMeans from sklearn.datasets import make_blobs # 生成模拟数据 X, y make_blobs(n_samples300, centers4, cluster_std0.6, random_state0) # 执行k-means聚类 kmeans KMeans(n_clusters4, initrandom, n_init10) kmeans.fit(X) centers kmeans.cluster_centers_ labels kmeans.labels_ # 可视化聚类结果与Voronoi图 vor Voronoi(centers) fig voronoi_plot_2d(vor, show_verticesFalse, line_colorsorange) plt.scatter(X[:,0], X[:,1], clabels, s50, cmapviridis, alpha0.6) plt.scatter(centers[:,0], centers[:,1], cred, s200, alpha0.8) plt.title(k-means聚类与Voronoi图) plt.show()算法优化技巧初始化改进采用k-means策略选择初始中心提前停止当中心点移动小于阈值时终止迭代并行计算利用多核处理加速距离计算近似算法使用MiniBatch k-means处理大数据4.3 多维扩展与实用考量在高于二维的空间中Voronoi单元变为多维凸多面体但核心概念保持不变。实践中需要考虑维度灾难高维空间中距离差异减小影响聚类效果距离选择针对数据特性选择合适距离度量聚类验证使用轮廓系数、Davies-Bouldin指数等评估质量以下是一个三维Voronoi图的示例代码from mpl_toolkits.mplot3d import Axes3D from scipy.spatial import Voronoi # 生成三维点集 points_3d np.random.rand(20, 3) # 计算3D Voronoi图 vor_3d Voronoi(points_3d) # 可视化 fig plt.figure(figsize(10, 7)) ax fig.add_subplot(111, projection3d) # 绘制生成点 ax.scatter(points_3d[:,0], points_3d[:,1], points_3d[:,2], cb, s20) # 绘制Voronoi边 for simplex in vor_3d.ridge_vertices: simplex np.asarray(simplex) if np.all(simplex 0): ax.plot(vor_3d.vertices[simplex, 0], vor_3d.vertices[simplex, 1], vor_3d.vertices[simplex, 2], k-) ax.set_title(三维Voronoi图) plt.tight_layout() plt.show()提示在实际数据分析中通常需要先进行PCA等降维处理再可视化高维聚类结果
