解题思路

相关算法与实现要点

• K-Means

  • 初始中心：取前 $k$ 个点作为初始中心（简单且可重复）。

  • 迭代过程：

    • 分配：每个点归到欧氏距离最近的中心；

题目内容

【问题背景】在无线网络优化中，基站的位置分布直接影响信号覆盖质量。密集区域的基站可能造成资源浪费，而稀疏区域则会出现信号覆盖不足。

【任务要求】给定$n$个基站的二维坐标，使用K-Means算法将其划分为$k$个簇，再通过计算每个簇的轮廓系数（Silhouette Coefficient），识别信号覆盖最差的簇（轮廓系数最低），并在该簇中心新增基站以优化信号覆盖。

【算法过程】

1. 使用前$k$个基站作为初始聚类中心，执行K-Means算法。K-means的结束条件为：最大迭代次数100或者所有簇中心点移动距离都不大于$1e-6$。
2. 计算每个簇的轮廓系数（簇内所有点的轮廓系数平均值）。
3. 找出轮廓系数最低的簇。
4. 输出该簇的中心坐标（保留两位小数），作为新增基站的位置。

K-Means和轮廓系数的详细介绍见“提示”。

输入描述

第一行：基站数量 $n$ 和聚类簇数 $k$，之间以空格分开，其中 $n$ 取值范围为 $[1,500]$，$k$ 取值范围为 $[1,120]$。

接下来 $n$ 行：每行两个整数，表示基站的坐标 $x$ 和 $y$，其中 $x$ 取值范围为 $[0,5000]$，$y$ 取值范围为 $[0,3000]$。

输出描述

新增基站的坐标：$x,y$ （输出结果四舍五入保留两位小数，采用 RoundingMode.HALF_EVEN）

样例1

输入

6 2
0 0
1 1
2 2
10 10
11 11
5 5

输出

8.67,8.67

说明

簇划分结果：簇 $0:[(0,0),(1,1),(2,2)]$，中心 $(1,1);$ 簇 $1:[(5,5),(10,10)(11,11)]$，中心 $(8.67,8.67)$ 轮廓系数:簇 $0$ 的轮廓系数: $0.82$ ;簇 $1$ 轮廓系数: $0.35$ 答案:输簇 $1$ 的中心点: $(8.67,8.67)$

样例2

输入

4 2
0 0
0 1
1 0
10 10

输出

0.33,0.33

说明

簇划分结果：簇 $0$ : $[(0,0),(0,1)(1,0)]$ ，中心点: $(0.33,0.33)$ ; 簇 $[(10.10)]$ ，中心点: $(10,10)$

轮廓系数:线 $0$ 的轮廓系数: $0.92$ ;簇 $1$ 的轮廓系数: $1.0$ 答案:输出簇 $0$ 的中心点: $0.33,0.33$

簇 $0:[A(0,0),B(0,1),C(1, 0)]$ ;

簇 $1$ : $[(10. 10)]$

簇 $0$ 的轮廓系数计算:

计算点 $A(0,0)$ :

1、$A$ 同簇平均距离为 $1$ : $A$ 到 $B(0,1)$ 距离 $1$ ，$A$ 到 $C(1,0)$ 距离 $1$

2、$A$ 到簇 $1$ 平均距离为 $14.142$ : $A$ 到 $D(10,10)$ 距离 $14.142$

3、$A$ 的轮廓系数 $s(A):0.929$

计算点 $B(0,1)$ :

1、$B$ 同簇平均距离为 $1.207:B$ 到 $A (0,0)$ 距离 $1$ ，$B$ 到 $C(1,0)$ 距离 $1.414$

2、$B$ 到簇 $1$ 平均距离为 $13.454:B$ 到 $D(10,10)$ 距离 $13.454$

3、$B$ 的轮廓系数 $s(B):0.910$

计算点 $C(1,0):$ 1、$C$ 同簇平均距离为 $1.207:C$ 到 $A(0,0)$ 距离 $1，C$ 到 $B(0,1)$ 距离 $1.414$

2、$C$ 到簇 $1$ 平均距离为 $13.454:C$ 到 $D(10,10)$ 距离 $13.454$

3、$C$ 的轮廓数 $s(C):0.910$

簇 $0$ 轮廓系数: $(s(A)+s(b)+s(b))/3=2.749/3=0.92$

提示

K-means的算法步骤为：

1. 选择初始化的前 $k$ 个样本作为初始聚类中心。

2. 针对数据集中每个样本 $x_i$，计算它到 $k$ 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中。

3. 针对每个类别 $a_j$，重新计算它的聚类中心

   $$a_j = \frac{1}{c_i} \sum_{x \in c_i} x$$

   （即属于该类的所有样本的质心）。

4. 重复上面2、3两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

轮廓系数 (Silhouette Coefficient Index)：

1、对于一个数据点 $i$，先计算它和簇内其他数据点的平均距离 $a_i$。

2、然后计算该点与不包含该点所在簇的其他簇内数据点的平均距离 $b_i$（簇间相似度），选取其中距离最小的那个作为 $i$ 的簇间平均距离。

3、最后，计算数据点 $i$ 的轮廓系数：

$s_i = \frac{b_i - a_i}{\max(a_i, b_i)}$

将所有数据点的轮廓系数取平均值，即得到聚类算法的整体轮廓系数。

若某个数据点所在簇的数据点数量小于等于1，则该点的轮廓系数为 $0$。

RoundingMode.HALF_EVEN：

1、Python默认的HALF_EVEN模式，其他语言按照如下规则处理： HALF_EVEN也称为“银行家舍入”或“向偶数舍入”。这种模式下，当小数部分恰好为$0.5$时，round()会将结果舍入到最近的偶数。

• round(2.55, 1) 会返回 $2.6$ （因为6是偶数）
• round(2.65, 1) 会返回 $2.6$ （因为6是偶数）
• round(2.75, 1) 会返回 $2.8$ （因为8是偶数）
• round(1.15, 1) 会返回 $1.2$ （因为2是偶数）