解题思路

P3791.第2题-无线网络优化中的基站聚类分析

1000ms

Tried: 3101

Accepted: 597

Difficulty: 7

所属公司 : 华为

算法与标签>机器学习算法

题目内容

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

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

【算法过程】

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

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

输入

输出

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

输入

输出

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的算法步骤为：

选择初始化的前 $k$ 个样本作为初始聚类中心。
针对数据集中每个样本 $x_i$ ，计算它到 $k$ 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中。
针对每个类别 $a_j$ ，重新计算它的聚类中心
$a_j = \frac{1}{c_i} \sum_{x \in c_i} x$
（即属于该类的所有样本的质心）。
重复上面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，则该点的轮廓系数为 $1$ 。

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是偶数）

输入

预期输出（选填）

解题思路

相关算法与实现要点

P3791.第2题-无线网络优化中的基站聚类分析

题目内容

输入描述

输出描述

样例1

样例2

提示

K-means的算法步骤为：

轮廓系数 (Silhouette Coefficient Index)：

RoundingMode.HALF_EVEN：

Status

Development

Support

About