聚类的分割

1.K-均值聚类

（1）K-均值聚类介绍

k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。

聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

在具有不同k值的同一数据集上运行k均值聚类的示例（注意：在k = 50的图中，颜色会重复出现，但表示单独的聚类）。

（2）k - means算法

先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：

1)没有（或最小数目）对象被重新分配给不同的聚类。

2)没有（或最小数目）聚类中心再发生变化。

3)误差平方和局部最小。

伪代码：

假设我们有$n$个数据点，要将其分成$k$类。

1. 先随机选取$k$个点$c_1,c_2,...,c_k$作为初始的聚类中心。
2. 定义收敛/终止标准(解决方案的稳定性和最大迭代次数)
3. while 不符合收敛/终止准则 do:
   1. for $i=1$ to $n$:
      
      计算$p_i$到每个簇中心的距离
      
      分配$p_i$到最接近它的质心，并相应地标记它
      
      endfor
   2. for $j=1$ to $k$:
      
      根据所有数据点的平均值重新计算$j$的质心
      
      endfor
      
      endwhile

（3）k -means 代码

首先给出完整的代码：

import numpy as np
import matplotlib.pyplot as plt
import cv2# 定义一个函数来生成集群
def cluster_gen(n_clusters, pts_minmax=(10, 100), x_mult=(1, 4), y_mult=(1, 3),x_off=(0, 50), y_off=(0, 50)):# n_clusters = 要生成的集群数量# pts_minmax = 每个集群的点数范围# x_mult = 乘法器的范围，在x方向修改集群的大小# y_mult = 乘法器的范围，在y方向修改集群的大小# x_off = 簇在x方向上的位置偏移范围# y_off = 簇在y方向上的位置偏移范围# 初始化一些空列表以接收集群成员位置clusters_x = []clusters_y = []# 在给定的参数范围内生成随机值n_points = np.random.randint(pts_minmax[0], pts_minmax[1], n_clusters)x_multipliers = np.random.randint(x_mult[0], x_mult[1], n_clusters)y_multipliers = np.random.randint(y_mult[0], y_mult[1], n_clusters)x_offsets = np.random.randint(x_off[0], x_off[1], n_clusters)y_offsets = np.random.randint(y_off[0], y_off[1], n_clusters)# 生成随机集群给定参数值for idx, npts in enumerate(n_points):xpts = np.random.randn(npts) * x_multipliers[idx] + x_offsets[idx]ypts = np.random.randn(npts) * y_multipliers[idx] + y_offsets[idx]clusters_x.append(xpts)clusters_y.append(ypts)# 返回集群的位置return clusters_x, clusters_y# 生成一些集群
n_clusters = 7
clusters_x, clusters_y = cluster_gen(n_clusters)
# 转换为OpenCV格式的单个数据集
data = np.float32((np.concatenate(clusters_x), np.concatenate(clusters_y))).transpose()# k - means参数定义
# 要定义的集群数量
k_clusters = 7
# 要执行的最大迭代数
max_iter = 10
# 停止迭代的精度准则
epsilon = 1.0
# 以OpenCV格式定义标准
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
# 调用数据集上的k-means算法
compactness, label, center = cv2.kmeans(data, k_clusters, None, criteria, 10, cv2.KMEANS_RANDOM_CENTERS)# 定义一些空列表来接收k-means集群点
kmeans_clusters_x = []
kmeans_clusters_y = []# 从输出中提取k-means集群
for idx in range(k_clusters):kmeans_clusters_x.append(data[label.ravel() == idx][:, 0])kmeans_clusters_y.append(data[label.ravel() == idx][:, 1])# 绘制原始集群与k-means集群的比较
fig = plt.figure(figsize=(12, 6))
plt.subplot(121)
min_x = np.min(data[:, 0])
max_x = np.max(data[:, 0])
min_y = np.min(data[:, 1])
max_y = np.max(data[:, 1])
for idx, xpts in enumerate(clusters_x):plt.plot(xpts, clusters_y[idx], 'o')plt.xlim(min_x, max_x)plt.ylim(min_y, max_y)plt.title('Original Clusters', fontsize=20)
plt.subplot(122)
for idx, xpts in enumerate(kmeans_clusters_x):plt.plot(xpts, kmeans_clusters_y[idx], 'o')plt.xlim(min_x, max_x)plt.ylim(min_y, max_y)plt.title('k-means Clusters', fontsize=20)
fig.tight_layout()
plt.subplots_adjust(left=0.03, right=0.98, top=0.9, bottom=0.05)
plt.show()

代码解释

K-means集群是一种强大的工具，但也有其局限性。Udacity提供了了一个沙箱环境，我们可以在其中测试k-means算法的局限。

# 定义一个函数来生成集群
def cluster_gen(n_clusters, pts_minmax=(10, 100), x_mult=(1, 4), y_mult=(1, 3),x_off=(0, 50), y_off=(0, 50)):# n_clusters = 要生成的集群数量# pts_minmax = 每个集群的点数范围# x_mult = 乘法器的范围，在x方向修改集群的大小# y_mult = 乘法器的范围，在y方向修改集群的大小# x_off = 簇在x方向上的位置偏移范围# y_off = 簇在y方向上的位置偏移范围# 初始化一些空列表以接收集群成员位置clusters_x = []clusters_y = []# 在给定的参数范围内生成随机值n_points = np.random.randint(pts_minmax[0], pts_minmax[1], n_clusters)x_multipliers = np.random.randint(x_mult[0], x_mult[1], n_clusters)y_multipliers = np.random.randint(y_mult[0], y_mult[1], n_clusters)x_offsets = np.random.randint(x_off[0], x_off[1], n_clusters)y_offsets = np.random.randint(y_off[0], y_off[1], n_clusters)# 生成随机集群给定参数值for idx, npts in enumerate(n_points):xpts = np.random.randn(npts) * x_multipliers[idx] + x_offsets[idx]ypts = np.random.randn(npts) * y_multipliers[idx] + y_offsets[idx]clusters_x.append(xpts)clusters_y.append(ypts)# 返回集群的位置return clusters_x, clusters_y

首先要做的是生成一些集群。现在提供了一个名为cluster_gen()的函数，它将从随机高斯分布生成简单的集群总体。

numpy.random.randint(low, high=None, size=None, dtype='l')

函数的作用是，返回一个随机整型数，范围从低（包括）到高（不包括），即[low, high)。

如果没有写参数high的值，则返回[0,low)的值。

np.random.randn(d0,d1,d2……dn)

1. 当函数括号内没有参数时，则返回一个浮点数；
2. 当函数括号内有一个参数时，则返回秩为1的数组，不能表示向量和矩阵；
3. 当函数括号内有两个及以上参数时，则返回对应维度的数组，能表示向量或矩阵；

生成集群后，需要将数据转换为OpenCV所需要的格式，然后定义k-means算法的约束，最后调用该cv2.kmeans()函数。

# 生成一些集群
n_clusters = 7
clusters_x, clusters_y = cluster_gen(n_clusters)
# 转换为OpenCV格式的单个数据集
data = np.float32((np.concatenate(clusters_x), np.concatenate(clusters_y))).transpose()# k - means参数定义
# 要定义的集群数量
k_clusters = 7
# 要执行的最大迭代数
max_iter = 10
# 停止迭代的精度准则
epsilon = 1.0
# 以OpenCV格式定义标准
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, max_iter, epsilon)
# 调用数据集上的k-means算法
compactness, label, center = cv2.kmeans(data, k_clusters, None, criteria, 10, cv2.KMEANS_RANDOM_CENTERS)

关于opencv下的kmean算法，函数为cv2.kmeans():

函数的格式为：kmeans(data, K, bestLabels, criteria, attempts, flags)

1. data: 分类数据。
2. K: 分类数，opencv2的kmeans分类是需要已知分类数的。
3. bestLabels：预设的分类标签：没有的话None
4. criteria：迭代停止的模式选择，这是一个含有三个元素的元组型数。格式为（type,max_iter,epsilon）
   
   其中，type又有两种选择：
   
   cv2.TERM_CRITERIA_EPS:精确度（误差）满足epsilon停止。
   
   cv2.TERM_CRITERIA_MAX_ITER：迭代次数超过max_iter停止。
   
   cv2.TERM_CRITERIA_EPS+cv2.TERM_CRITERIA_MAX_ITER，两者合体，任意一个满足结束。
5. attempts：重复试验kmeans算法次数，将会返回最好的一次结果
6. flags：初始类中心选择，两种方法：cv2.KMEANS_PP_CENTERS; cv2.KMEANS_RANDOM_CENTERS

程序输出如下:

2. DBSCAN算法

（1）DBSCAN算法介绍