KMeans等其他聚类算法

KMeans算法是一种经典的聚类方法，最早由Stuart Lloyd在1957年提出，并在1982年由J. MacQueen推广和普及。虽然KMeans已经有几十年的历史，但它依然是数据挖掘和机器学习领域中最常用的聚类算法之一。

数学原理

KMeans算法的目标是将数据集分成(k)个簇，每个簇的中心（质心）是该簇中所有点的平均值。算法的步骤如下：

初始化：随机选择(k)个初始质心。
分配数据点：将每个数据点分配到距离最近的质心。
更新质心：重新计算每个簇的质心，即该簇中所有点的平均值。
重复步骤2和3，直到质心不再变化或达到最大迭代次数。

用数学公式表示为：

初始质心：
分配数据点：
更新质心：

其中，表示第个簇的质心，表示第个簇，表示欧几里德距离。

其他聚类算法简要介绍

OPTICS（Ordering Points To Identify the Clustering Structure）

OPTICS算法通过分析数据点的可达性图来识别不同密度的簇，非常适合处理具有不同密度的复杂数据集。

import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import OPTICSif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)  # 每10个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])  # 指定显示为灰色print(pcd)pcd1 = deepcopy(pcd)points = np.array(pcd1.points)result = OPTICS(min_samples=2, max_eps=5).fit(points)labels = result.labels_max_label = np.max(labels) + 1colors = np.random.randint(255, size=(max_label+1, 3)) / 255.colors = colors[labels]colors[labels < 0] = 0  # 没有分类成功的点设置为黑色pcd1.colors = o3d.utility.Vector3dVector(colors[:, :3])o3d.visualization.draw_geometries([pcd1], window_name="OPTICS 点云聚类", width=800, height=600)

Spectral Clustering

Spectral Clustering利用数据的特征值和特征向量，将数据映射到一个低维空间中进行聚类，适合处理非凸形状的簇。

import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import SpectralClusteringif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)  # 每10个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])  # 指定显示为灰色print(pcd)pcd2 = deepcopy(pcd)points = np.array(pcd2.points)result = SpectralClustering(n_clusters=8).fit(points)labels = result.labels_max_label = np.max(labels) + 1colors = np.random.randint(255, size=(max_label+1, 3)) / 255.colors = colors[labels]colors[labels < 0] = 0  # 没有分类成功的点设置为黑色pcd2.colors = o3d.utility.Vector3dVector(colors[:, :3])o3d.visualization.draw_geometries([pcd2], window_name="Spectral Clustering 点云聚类", width=800, height=600)

Hierarchical Clustering

Hierarchical Clustering分为凝聚层次聚类和分裂层次聚类，创建一棵树状结构（树状图）来表示数据点之间的层次关系。

import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import AgglomerativeClusteringif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)  # 每10个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])  # 指定显示为灰色print(pcd)pcd3 = deepcopy(pcd)points = np.array(pcd3.points)result = AgglomerativeClustering(n_clusters=8).fit(points)labels = result.labels_max_label = np.max(labels) + 1colors = np.random.randint(255, size=(max_label+1, 3)) / 255.colors = colors[labels]colors[labels < 0] = 0  # 没有分类成功的点设置为黑色pcd3.colors = o3d.utility.Vector3dVector(colors[:, :3])o3d.visualization.draw_geometries([pcd3], window_name="Hierarchical Clustering 点云聚类", width=800, height=600)

Mean-shift

Mean-shift是一种基于密度的聚类方法，通过滑动窗口找到数据点密度的峰值，非常适合处理形状不规则的簇。

import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import estimate_bandwidth, MeanShiftif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)  # 每10个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])  # 指定显示为灰色print(pcd)pcd4 = deepcopy(pcd)points = np.array(pcd4.points)bandwidth = estimate_bandwidth(points, quantile=0.2, n_samples=500)result = MeanShift(bandwidth=bandwidth).fit(points)labels = result.labels_max_label = np.max(labels) + 1colors = np.random.randint(255, size=(max_label+1, 3)) / 255.colors = colors[labels]colors[labels < 0] = 0  # 没有分类成功的点设置为黑色pcd4.colors = o3d.utility.Vector3dVector(colors[:, :3])o3d.visualization.draw_geometries([pcd4], window_name="Mean-shift 点云聚类", width=800, height=600)

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）

BIRCH算法通过构建一个高度平衡的树结构，进行逐步聚类，适用于大规模数据集。

import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import Birchif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)  # 每10个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])  # 指定显示为灰色print(pcd)pcd5 = deepcopy(pcd)points = np.array(pcd5.points)result = Birch(n_clusters=8).fit(points)labels = result.labels_max_label = np.max(labels) + 1colors = np.random.randint(255, size=(max_label+1, 3)) / 255.colors = colors[labels]colors[labels < 0] = 0  # 没有分类成功的点设置为黑色pcd5.colors = o3d.utility.Vector3dVector(colors[:, :3])o3d.visualization.draw_geometries([pcd5], window_name="BIRCH 点云聚类", width=800, height=600)

Affinity Propagation

Affinity Propagation通过传递“信息”在数据点之间找到一组最能代表其他数据点的“示例”，不需要预先指定簇的数量。

import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import AffinityPropagationif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)  # 每10个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])  # 指定显示为灰色print(pcd)pcd6 = deepcopy(pcd)points = np.array(pcd6.points)result = AffinityPropagation(preference=-20).fit(points)labels = result.labels_max_label = np.max(labels) + 1colors = np.random.randint(255, size=(max_label+1, 3)) / 255.colors = colors[labels]colors[labels < 0] = 0  # 没有分类成功的点设置为黑色pcd6.colors = o3d.utility.Vector3dVector(colors[:, :3])o3d.visualization.draw_geometries([pcd6], window_name="Affinity Propagation 点云聚类", width=800, height=600)

以上所有的聚类算法同时对目标点云数据进行聚类的结果如下：

# -*- coding: utf-8 -*-
"""
乐乐感知学堂公众号
@author: https://blog.csdn.net/suiyingy
"""import open3d as o3d
import numpy as np
from copy import deepcopy
from sklearn.cluster import OPTICS, SpectralClustering, AgglomerativeClustering, estimate_bandwidth, MeanShift, Birch, AffinityPropagationif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd = pcd.uniform_down_sample(10)#每50个点采样一次pcd.paint_uniform_color([0.5, 0.5, 0.5])#指定显示为灰色print(pcd)pcd1 = deepcopy(pcd)pcd1.translate((20, 0, 0)) #整体进行x轴方向平移20points = np.array(pcd1.points)result = OPTICS(min_samples=2, max_eps=5).fit(points)#各个类别中心# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label+1, 3))/255.colors = colors[labels]#没有分类成功的点设置为黑色colors[labels < 0] = 0 pcd1.colors = o3d.utility.Vector3dVector(colors[:, :3])pcd2 = deepcopy(pcd)pcd2.translate((-20, 0, 0)) #整体进行x轴方向平移-20points = np.array(pcd2.points)result = SpectralClustering(n_clusters=8).fit(points)#各个类别中心# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label+1, 3))/255.colors = colors[labels]#没有分类成功的点设置为黑色colors[labels < 0] = 0 pcd2.colors = o3d.utility.Vector3dVector(colors[:, :3])pcd3 = deepcopy(pcd)pcd3.translate((0, 20, 0)) #整体进行y轴方向平移20points = np.array(pcd3.points)result = AgglomerativeClustering(n_clusters=8).fit(points)#各个类别中心# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label+1, 3))/255.colors = colors[labels]#没有分类成功的点设置为黑色colors[labels < 0] = 0 pcd3.colors = o3d.utility.Vector3dVector(colors[:, :3])pcd4 = deepcopy(pcd)pcd4.translate((0, -20, 0)) #整体进行y轴方向平移-20points = np.array(pcd4.points)#定义搜索半径，也可以直接初始化一个数值bandwidth = estimate_bandwidth(points, quantile=0.2, n_samples=500)result = MeanShift(bandwidth=bandwidth).fit(points)#各个类别中心# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label+1, 3))/255.colors = colors[labels]#没有分类成功的点设置为黑色colors[labels < 0] = 0 pcd4.colors = o3d.utility.Vector3dVector(colors[:, :3])pcd5 = deepcopy(pcd)pcd5.translate((40, 0, 0)) #整体进行x轴方向平移40points = np.array(pcd5.points)result = Birch(n_clusters=8).fit(points)#各个类别中心# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label+1, 3))/255.colors = colors[labels]#没有分类成功的点设置为黑色colors[labels < 0] = 0 pcd5.colors = o3d.utility.Vector3dVector(colors[:, :3])pcd6 = deepcopy(pcd)pcd6.translate((-40, 0, 0)) #整体进行x轴方向平移-40points = np.array(pcd6.points)result = AffinityPropagation(preference=-20).fit(points)#各个类别中心# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label+1, 3))/255.colors = colors[labels]#没有分类成功的点设置为黑色colors[labels < 0] = 0 pcd6.colors = o3d.utility.Vector3dVector(colors[:, :3])# 点云显示o3d.visualization.draw_geometries([pcd, pcd1, pcd2, pcd3, pcd4, pcd5, pcd6], #点云列表window_name="点云聚类",point_show_normal=False,width=800,  # 窗口宽度height=600)  # 窗口高度

KMeans可视化算法实例

以下是一个使用Open3D进行KMeans聚类的示例：

import open3d as o3d
import numpy as np
from sklearn.cluster import KMeansif __name__ == '__main__':file_path = 'rabbit.pcd'pcd = o3d.io.read_point_cloud(file_path)pcd.paint_uniform_color([0.5, 0.5, 0.5])#指定显示为灰色print(pcd)points = np.array(pcd.points)result = KMeans(n_clusters=8).fit(points)#各个类别中心center = result.cluster_centers_# labels返回聚类成功的类别，从0开始，每个数据表示一个类别labels = result.labels_#最大值相当于共有多少个类别max_label = np.max(labels) + 1 #从0开始计算标签print(max(labels))#生成k个类别的颜色，k表示聚类成功的类别colors = np.random.randint(255, size=(max_label, 3))/255.colors = colors[labels]pcd.colors = o3d.utility.Vector3dVector(colors[:, :3])# 点云显示o3d.visualization.draw_geometries([pcd], #点云列表window_name="Kmeans点云聚类",point_show_normal=False,width=800,  # 窗口宽度height=600)  # 窗口高度