PythonRobotics机器人算法-映射算法之K均值聚类(K-means object clustering)


1.概述

K-均值算法(K-means clustering)源于信号处理中的一种向量量化方法,现在则更多地作为一种聚类分析方法流行于数据挖掘领域。K-均值聚类的目的是:把n个点(可以是样本的一次观察或一个实例)划分到k个聚类中,使得每个点都属于离他最近的均值(此即聚类中心)对应的聚类,以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。

这个问题在计算上是NP困难的,不过存在高效的启发式算法。一般情况下,都使用效率比较高的启发式算法,它们能够快速收敛于一个局部最优解。这些算法通常类似于通过迭代优化方法处理高斯混合分布的最大期望算法(EM算法)。而且,它们都使用聚类中心来为数据建模;然而k-平均聚类倾向于在可比较的空间范围内寻找聚类,期望-最大化技术却允许聚类有不同的形状。

K-均值聚类与K-近邻之间没有任何关系(后者是另一流行的机器学习技术)。

2.K均值聚类实例

下面展示一下基于python实现的K均值聚类。

(1)定义初始参数

1
2
3
4
5
6
import numpy as np
import math
import matplotlib.pyplot as plt
import random

show_animation = True

(2)算法过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Clusters:
    def _ _init__(self, x, y, nlabel):
        self.x = x
        self.y = y
        self.ndata = len(self.x)
        self.nlabel = nlabel
        self.labels = [random.randint(0, nlabel - 1)
                       for _ in range(self.ndata)]
        self.cx = [0.0 for _ in range(nlabel)]
        self.cy = [0.0 for _ in range(nlabel)]

def kmeans_clustering(rx, ry, nc):
    clusters = Clusters(rx, ry, nc)
    clusters = calc_centroid(clusters)
    MAX_LOOP = 10
    DCOST_TH = 0.1
    pcost = 100.0
    for loop in range(MAX_LOOP):
        #print("Loop:", loop)
        clusters, cost = update_clusters(clusters)
        clusters = calc_centroid(clusters)
        dcost = abs(cost - pcost)
        if dcost < DCOST_TH:
            break
        pcost = cost
    return clusters

def calc_centroid(clusters):
    for ic in range(clusters.nlabel):
        x, y = calc_labeled_points(ic, clusters)
        ndata = len(x)
        clusters.cx[ic] = sum(x) / ndata
        clusters.cy[ic] = sum(y) / ndata
    return clusters

def update_clusters(clusters):
    cost = 0.0
    for ip in range(clusters.ndata):
        px = clusters.x[ip]
        py = clusters.y[ip]
        dx = [icx - px for icx in clusters.cx]
        dy = [icy - py for icy in clusters.cy]
        dlist = [math.sqrt(idx* * 2 + idy* * 2) for (idx, idy) in zip(dx, dy)]
        mind = min(dlist)
        min_id = dlist.index(mind)
        clusters.labels[ip] = min_id
        cost += min_id
    return clusters, cost

def calc_labeled_points(ic, clusters):
    inds = np.array([i for i in range(clusters.ndata)
                     if clusters.labels[i] == ic])
    tx = np.array(clusters.x)
    ty = np.array(clusters.y)
    x = tx[inds]
    y = ty[inds]
    return x, y

def calc_raw_data(cx, cy, npoints, rand_d):
    rx, ry = [], []
    for (icx, icy) in zip(cx, cy):
        for _ in range(npoints):
            rx.append(icx + rand_d * (random.random() - 0.5))
            ry.append(icy + rand_d * (random.random() - 0.5))
    return rx, ry

def update_positions(cx, cy):
    DX1 = 0.4
    DY1 = 0.5
    cx[0] += DX1
    cy[0] += DY1
    DX2 = -0.3
    DY2 = -0.5
    cx[1] += DX2
    cy[1] += DY2
    return cx, cy

def calc_association(cx, cy, clusters):
    inds = []
    for ic in range(len(cx)):
        tcx = cx[ic]
        tcy = cy[ic]
        dx = [icx - tcx for icx in clusters.cx]
        dy = [icy - tcy for icy in clusters.cy]
        dlist = [math.sqrt(idx* * 2 + idy* * 2) for (idx, idy) in zip(dx, dy)]
        min_id = dlist.index(min(dlist))
        inds.append(min_id)
    return inds

(3)结果可视化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def main():
    print(_ _file__ + " start!!")
    cx = [0.0, 8.0]
    cy = [0.0, 8.0]
    npoints = 10
    rand_d = 3.0
    ncluster = 2
    sim_time = 15.0
    dt = 1.0
    time = 0.0
    while time &lt;= sim_time:
        print("Time:", time)
        time += dt
        # simulate objects
        cx, cy = update_positions(cx, cy)
        rx, ry = calc_raw_data(cx, cy, npoints, rand_d)
        clusters = kmeans_clustering(rx, ry, ncluster)
        # for animation
        if show_animation:
            plt.cla()
            inds = calc_association(cx, cy, clusters)
            for ic in inds:
                x, y = calc_labeled_points(ic, clusters)
                plt.plot(x, y, "x")
            plt.plot(cx, cy, "o")
            plt.xlim(-2.0, 10.0)
            plt.ylim(-2.0, 10.0)
            plt.pause(dt)
    print("Done")

if _ _ name__ == '_ _main__':
    main()

执行结果如下。下面为利用k均值算法进行二维目标聚类的实例

参考文献

  1. https://zh.wikipedia.org/wiki/K-平均算法
  2. https://baike.baidu.com/item/K-means/4934806
  3. MacQueen J. Some methods for classification and analysis of multivariate observations[C] //Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. 1967, 1(14): 281-297.
  4. https://pythonrobotics.readthedocs.io/en/latest/
  5. https://github.com/AtsushiSakai/PythonRobotics/
  6. PythonRobotics: a Python code collection of robotics algorithms

进化学习团队将会根据大家意见和建议持续修改、维护与更新。转载请注明出处(进化学习: https://www.evolutionarylearn.com/paper/ra-pythonrobotics-mapping-kmoc/)。

赞赏

微信赞赏支付宝赞赏

Have any Question or Comment?

One comment on “PythonRobotics机器人算法-映射算法之K均值聚类(K-means object clustering)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

热门主题 & 页面

分类目录

博客统计

无点击次数。