解题思路
本题要求用 K-means 在宽高空间对检测框进行聚类，以获得 YOLO 的 Anchor 尺寸。与欧氏距离不同，这里采用 d = 1 − IOU 作为距离度量，能更贴近目标检测中对宽高匹配的要求。
算法选择与要点
- 初始化（稳定初始化）：直接取前 K 个框作为初始聚类中心（宽、高）。
- 分配阶段：对每个样本框 (w,h) 计算到所有中心 (Wk,Hk) 的距离
P3842.第2题-Yolo检测器中的anchor聚类
题目内容
【背景信息】YOLO (You Only Look Once) 系列算法在目标检测领域采用了基于Anchor的机制。Anchor是预定义在图像上的一组固定尺寸和比例的参考框，在特征图的每个位置上预设多个Anchor框作为物体位置和尺寸预测的基准。通过模型预测Anchor与真实框的偏移量(Δx,Δy,Δw,Δh)，而非直接输出坐标，避免了直接回归绝对坐标的困难。
【任务目标】
基于k-means聚类算法生成YOLO目标检测中的Anchor框：给定N个检测框的宽和高，聚类得到K个Anchor尺寸，并按照面积从大到小的顺序输出Anchor尺寸。
【任务目标】
基于k-means聚类算法生成YOLO目标检测中的Anchor框：给定N个检测框的宽和高，聚类得到K个Anchor尺寸，并按照面积从大到小的顺序输出Anchor尺寸。
聚类的流程如下：
初始化：为保证聚类结果的稳定性，采用稳定初始化策略，直接取前K个框作为初始中心。
分配阶段：计算每个框到所有聚类中心的距离，分配到最近的中心。
更新阶段：计算每个簇中所有框的宽高均值作为新的聚类中心（在每次迭代计算聚类中心时，均进行向下取整）。
迭代终止条件：当达到设定迭代次数T或新旧聚类中心之间的d值之和小于1e-4时停止迭代。
注：聚类使用 d=1−IOU 作为距离度量，d和IOU的计算均使用浮点数。
其中IOU的核心公式为交并面积比，即
IOU=并集面积交集面积
对于检测框B1(w1,h1) 和 B2(w2,h2)，交集面积计算为：
intersection=min(w1,w2)×min(h1,h2)
并集面积则为两框总面积减去交集：
union=w1×h1+w2×h2−intersection
最终：IOU = intersection/(union + 1e-16) (加极小值避免除零)
输入描述
第一行：N,K,T，以空格分开。
其中：
-
N 为训练集中检测框的个数，10≤N≤80
-
K 为聚类中心个数，3≤K≤9
-
T 为聚类迭代次数，2≤T≤30
接下来 N 行：每行为检测框的宽与高，用空格分开。
输出描述
按照聚类中心的面积从大到小的顺序，输出聚类后的中心。
（聚类中心的面积 = 聚类中心的宽 × 聚类中心的高）
样例1
输入
12 4 20
12 23
34 21
43 23
199 23
34 23
108 12
200 107
12 78
123 110
34 23
56 48
78 66
输出
133 94
121 27
36 22
12 50
说明
-
输入第一行为 12420，代表12个检测框，要聚成4类，最大迭代次数为20，接下来的12行是检测框的宽与高。
-
取前4个框 [12,23],[34,21],[43,23],[199,23] 作为初始聚类中心。
-
迭代更新计算聚类中心，注意每次迭代时聚类中心都做向下取整。
-
按照聚类中心的面积（宽 × 高）从大到小排序，输出4个Anchor聚类中心。
样例2
输入
12 3 10
12 23
34 21
43 23
199 23
34 23
108 12
200 107
12 78
123 110
34 23
56 48
78 66
输出
150 76
51 25
12 50
说明
-
输入第一行为 12310，代表12个检测框，要聚成3类，最大迭代次数为10，接下来的12行是检测框的宽与高。
-
取前3个框 [12,23],[34,21],[43,23] 作为初始聚类中心。
-
迭代更新计算聚类中心，注意每次迭代时聚类中心都做向下取整。
-
按照聚类中心的面积（宽 × 高）从大到小排序，输出3个Anchor聚类中心。
提示
注：每次迭代的距离度量 d 和交并比 IOU 都是用浮点数计算，但每次迭代和最终输出的聚类中心都要做向下取整。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
