假设有 8 个点聚类成 3 个簇，A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9),距离为城市街 区距离（|u1-v1|+|u2-v2|）。假设初始聚类中心为 A1,B1,C1,用 K-Means 算法计算，要求如下： （1）给出第一次循环执行后的三个聚类中心； （2）最后聚类得到的三个簇。

首先，我们可以将 8 个点的坐标绘制在二维坐标系上，如下图所示：


接下来，我们按照 K-Means 算法的流程进行计算：

1. 随机选择三个点作为初始聚类中心，这里我们选择 A1(2,10), B1(5,8), C1(1,2)。

2. 计算每个点到三个聚类中心的距离，并将其归到距离最近的簇中。

| 点 | 到 A1 的距离 | 到 B1 的距离 | 到 C1 的距离 | 最近的簇 |
|----|-------------|-------------|-------------|----------|
| A1 | 0 | 3 | 8 | A1 |
| A2 | 5 | 4 | 9 | B1 |
| A3 | 9 | 6 | 12 | B1 |
| B1 | 3 | 0 | 7 | B1 |
| B2 | 5 | 2 | 9 | B1 |
| B3 | 7 | 2 | 11 | B1 |
| C1 | 8 | 6 | 0 | C1 |
| C2 | 7 | 5 | 5 | C1 |

3. 计算每个簇的平均值，并将其作为新的聚类中心。

新的 A1: (2, 10)
新的 B1: (6.6, 5.8)
新的 C1: (2.5, 5.5)

4. 重复步骤 2 和 3，直到聚类中心不再发生变化或达到最大迭代次数。

第二次迭代：

| 点 | 到 A1 的距离 | 到 B1 的距离 | 到 C1 的距离 | 最近的簇 |
|----|-------------|-------------|-------------|----------|
| A1 | 0 | 5.3 | 7.1 | A1 |
| A2 | 5 | 2.2 | 6.1 | B2 |
| A3 | 9 | 4.2 | 6.7 | B2 |
| B1 | 3.6 | 0 | 7.8 | B1 |
| B2 | 5.1 | 2.2 | 4.5 | B2 |
| B3 | 7.2 | 2.2 | 4.9 | B2 |
| C1 | 8.5 | 5.9 | 0 | C1 |
| C2 | 7.2 | 3.6 | 3.2 | C2 |

新的 A1: (2, 10)
新的 B1: (6.3, 4.3)
新的 C1: (2.5, 5.5)

第三次迭代：

| 点 | 到 A1 的距离 | 到 B1 的距离 | 到 C1 的距离 | 最近的簇 |
|----|-------------|-------------|-------------|----------|
| A1 | 0 | 6.2 | 6.5 | A1 |
| A2 | 5 | 2.5 | 5.5 | B2 |
| A3 | 9 | 4.9 | 4.5 | C1 |
| B1 | 3.6 | 0 | 7.8 | B1 |
| B2 | 5.1 | 2.5 | 2.8 | C1 |
| B3 | 7.2 | 2.5 | 3.2 | C1 |
| C1 | 8.5 | 5.4 | 0 | C1 |
| C2 | 7.2 | 3.1 | 2.5 | C2 |

新的 A1: (2, 10)
新的 B1: (6.3, 4.3)
新的 C1: (5.7, 4.3)

第四次迭代：

| 点 | 到 A1 的距离 | 到 B1 的距离 | 到 C1 的距离 | 最近的簇 |
|----|-------------|-------------|-------------|----------|
| A1 | 0 | 6.2 | 6.5 | A1 |
| A2 | 5 | 2.5 | 5.5 | B2 |
| A3 | 9 | 4.9 | 4.5 | C1 |
| B1 | 3.6 | 0 | 7.8 | B1 |
| B2 | 5.1 | 2.5 | 2.8 | C1 |
| B3 | 7.2 | 2.5 | 3.2 | C1 |
| C1 | 8.5 | 5.4 | 0 | C1 |
| C2 | 7.2 | 3.1 | 2.5 | C2 |

新的 A1: (2, 10)
新的 B1: (6.3, 4.3)
新的 C1: (5.7, 4.3)

可以看出，第四次迭代后聚类中心不再发生变化，算法收敛。最终聚类得到的三个簇为：

簇 1：A1(2,10)
簇 2：B2(7,5), B3(6,4), C2(4,9)
簇 3：A2(2,5), A3(8,4), B1(5,8), C1(1,2)