解题思路

本题要求用 K-means 在宽高空间对检测框进行聚类，以获得 YOLO 的 Anchor 尺寸。与欧氏距离不同，这里采用 d = 1 − IOU 作为距离度量，能更贴近目标检测中对宽高匹配的要求。

算法选择与要点

1. 初始化（稳定初始化）：直接取前 K 个框作为初始聚类中心（宽、高）。

2. 分配阶段：对每个样本框 $(w, h)$ 计算到所有中心 $(W_k, H_k)$ 的距离

   $$d = 1 - \text{IOU}((w,h),(W_k,H_k))$$

   其中

   $$\text{IOU}=\frac{\min(w,W_k)\cdot \min(h,H_k)}{w\cdot h + W_k\cdot H_k - \min(w,W_k)\cdot \min(h,H_k) + 1e-16} $$

   将样本分配给距离最小的簇。

3. 更新阶段：对每个簇计算所有成员在宽、高上的均值并向下取整（floor），作为新的中心。如果某簇为空，则保留原中心不变。

4. 终止条件：最多迭代 T 次；或当新旧中心配对的 d 值之和

   $$\sum_{k=1}^{K} \left(1-\text{IOU}\big((W_k^{old},H_k^{old}),(W_k^{new},H_k^{new})\big)\right) < 1e-4 $$

   时提前停止。

5. 输出：将最终 K 个中心按面积（宽×高）从大到小排序输出。 注意：迭代中每次更新的中心与最终输出都要向下取整，但 IOU 与 d 的计算始终用浮点数（避免精度问题，分母加 $1e{-16}$）。

该流程等价于在“宽高-IOU”空间上的 K-means 变体，常用于 Anchor 聚类以提升先验框与真实框的匹配度。

代码实现

Python

import sys
import math

# 计算两个宽高框的 IOU（基于宽高，无位置信息）
def iou_wh(w1, h1, w2, h2):
    inter = min(w1, w2) * min(h1, h2)
    union = w1 * h1 + w2 * h2 - inter
    return inter / (union + 1e-16)

# 使用 d = 1 - IOU 的 K-means 聚类，返回最终中心（整数）
def kmeans_anchors(boxes, K, T):
    # 初始化：取前 K 个框为初始中心（转为浮点便于计算）
    centers = [(float(boxes[i][0]), float(boxes[i][1])) for i in range(K)]
    n = len(boxes)

    for _ in range(T):
        # 分配阶段：为每个样本选择最近中心
        assign = [0] * n
        for i, (w, h) in enumerate(boxes):
            best_k = 0
            best_d = 1.0 - iou_wh(w, h, centers[0][0], centers[0][1])
            for k in range(1, K):
                d = 1.0 - iou_wh(w, h, centers[k][0], centers[k][1])
                if d < best_d:
                    best_d = d
                    best_k = k
            assign[i] = best_k

        # 更新阶段：计算新中心（对均值向下取整）
        sums = [[0.0, 0.0] for _ in range(K)]
        cnts = [0] * K
        for (w, h), k in zip(boxes, assign):
            sums[k][0] += w
            sums[k][1] += h
            cnts[k] += 1

        new_centers = []
        for k in range(K):
            if cnts[k] == 0:
                # 空簇：保留原中心
                new_centers.append((centers[k][0], centers[k][1]))
            else:
                W = math.floor(sums[k][0] / cnts[k])
                H = math.floor(sums[k][1] / cnts[k])
                new_centers.append((float(W), float(H)))

        # 终止条件：新旧中心 d 值之和
        change = 0.0
        for k in range(K):
            change += (1.0 - iou_wh(centers[k][0], centers[k][1], new_centers[k][0], new_centers[k][1]))
        centers = new_centers
        if change < 1e-4:
            break

    # 最终结果向下取整并按面积从大到小排序
    final_centers = [(int(math.floor(w)), int(math.floor(h))) for (w, h) in centers]
    final_centers.sort(key=lambda x: x[0] * x[1], reverse=True)
    return final_centers

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it)); K = int(next(it)); T = int(next(it))
    boxes = []
    for _ in range(N):
        w = float(next(it)); h = float(next(it))
        boxes.append((w, h))

    centers = kmeans_anchors(boxes, K, T)
    out = []
    for w, h in centers:
        out.append(f"{w} {h}")
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/* ACM 风格，读取输入，输出结果；核心逻辑放在静态函数里 */
public class Main {

    // 计算宽高框的 IOU
    static double iouWH(double w1, double h1, double w2, double h2) {
        double inter = Math.min(w1, w2) * Math.min(h1, h2);
        double union = w1 * h1 + w2 * h2 - inter;
        return inter / (union + 1e-16);
    }

    // d = 1 - IOU 的 K-means 聚类
    static int[][] kmeansAnchors(double[][] boxes, int K, int T) {
        int N = boxes.length;
        // 初始化：前 K 个样本
        double[][] centers = new double[K][2];
        for (int k = 0; k < K; k++) {
            centers[k][0] = boxes[k][0];
            centers[k][1] = boxes[k][1];
        }

        for (int t = 0; t < T; t++) {
            int[] assign = new int[N];
            // 分配阶段
            for (int i = 0; i < N; i++) {
                double w = boxes[i][0], h = boxes[i][1];
                int bestK = 0;
                double bestD = 1.0 - iouWH(w, h, centers[0][0], centers[0][1]);
                for (int k = 1; k < K; k++) {
                    double d = 1.0 - iouWH(w, h, centers[k][0], centers[k][1]);
                    if (d < bestD) {
                        bestD = d;
                        bestK = k;
                    }
                }
                assign[i] = bestK;
            }

            // 更新阶段
            double[] sumW = new double[K];
            double[] sumH = new double[K];
            int[] cnt = new int[K];
            for (int i = 0; i < N; i++) {
                int k = assign[i];
                sumW[k] += boxes[i][0];
                sumH[k] += boxes[i][1];
                cnt[k]++;
            }

            double[][] newCenters = new double[K][2];
            for (int k = 0; k < K; k++) {
                if (cnt[k] == 0) {
                    // 空簇，保持不变
                    newCenters[k][0] = centers[k][0];
                    newCenters[k][1] = centers[k][1];
                } else {
                    // 向下取整
                    double W = Math.floor(sumW[k] / cnt[k]);
                    double H = Math.floor(sumH[k] / cnt[k]);
                    newCenters[k][0] = W;
                    newCenters[k][1] = H;
                }
            }

            // 终止条件：新旧中心 d 值之和
            double change = 0.0;
            for (int k = 0; k < K; k++) {
                change += (1.0 - iouWH(centers[k][0], centers[k][1], newCenters[k][0], newCenters[k][1]));
            }
            centers = newCenters;
            if (change < 1e-4) break;
        }

        // 最终向下取整并按面积降序
        int[][] ans = new int[K][2];
        for (int k = 0; k < K; k++) {
            ans[k][0] = (int)Math.floor(centers[k][0]);
            ans[k][1] = (int)Math.floor(centers[k][1]);
        }

        Integer[] idx = new Integer[K];
        for (int i = 0; i < K; i++) idx[i] = i;
        Arrays.sort(idx, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                long areaB = 1L * ans[b][0] * ans[b][1];
                long areaA = 1L * ans[a][0] * ans[a][1];
                return Long.compare(areaB, areaA); // 面积降序
            }
        });

        int[][] sorted = new int[K][2];
        for (int i = 0; i < K; i++) {
            sorted[i][0] = ans[idx[i]][0];
            sorted[i][1] = ans[idx[i]][1];
        }
        return sorted;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNext()) return;
        int N = sc.nextInt();
        int K = sc.nextInt();
        int T = sc.nextInt();
        double[][] boxes = new double[N][2];
        for (int i = 0; i < N; i++) {
            boxes[i][0] = sc.nextDouble();
            boxes[i][1] = sc.nextDouble();
        }
        int[][] res = kmeansAnchors(boxes, K, T);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            sb.append(res[i][0]).append(" ").append(res[i][1]);
            if (i + 1 < res.length) sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算两个宽高框的 IOU
double iouWH(double w1, double h1, double w2, double h2) {
    double inter = min(w1, w2) * min(h1, h2);
    double uni = w1 * h1 + w2 * h2 - inter;
    return inter / (uni + 1e-16);
}

// d = 1 - IOU 的 K-means 聚类
vector<pair<int,int>> kmeansAnchors(const vector<pair<double,double>>& boxes, int K, int T) {
    int N = (int)boxes.size();
    // 初始化：前 K 个样本
    vector<pair<double,double>> centers(K);
    for (int k = 0; k < K; ++k) centers[k] = boxes[k];

    for (int t = 0; t < T; ++t) {
        // 分配阶段
        vector<int> assign(N, 0);
        for (int i = 0; i < N; ++i) {
            double w = boxes[i].first, h = boxes[i].second;
            int bestK = 0;
            double bestD = 1.0 - iouWH(w, h, centers[0].first, centers[0].second);
            for (int k = 1; k < K; ++k) {
                double d = 1.0 - iouWH(w, h, centers[k].first, centers[k].second);
                if (d < bestD) {
                    bestD = d;
                    bestK = k;
                }
            }
            assign[i] = bestK;
        }

        // 更新阶段
        vector<double> sumW(K, 0.0), sumH(K, 0.0);
        vector<int> cnt(K, 0);
        for (int i = 0; i < N; ++i) {
            int k = assign[i];
            sumW[k] += boxes[i].first;
            sumH[k] += boxes[i].second;
            cnt[k] += 1;
        }
        vector<pair<double,double>> newCenters(K);
        for (int k = 0; k < K; ++k) {
            if (cnt[k] == 0) {
                // 空簇，保持不变
                newCenters[k] = centers[k];
            } else {
                double W = floor(sumW[k] / cnt[k]);
                double H = floor(sumH[k] / cnt[k]);
                newCenters[k] = {W, H};
            }
        }

        // 终止条件
        double change = 0.0;
        for (int k = 0; k < K; ++k) {
            change += (1.0 - iouWH(centers[k].first, centers[k].second,
                                   newCenters[k].first, newCenters[k].second));
        }
        centers.swap(newCenters);
        if (change < 1e-4) break;
    }

    // 最终向下取整并按面积从大到小排序
    vector<pair<int,int>> ans;
    ans.reserve(K);
    for (int k = 0; k < K; ++k) {
        int W = (int)floor(centers[k].first);
        int H = (int)floor(centers[k].second);
        ans.emplace_back(W, H);
    }
    sort(ans.begin(), ans.end(), [](const pair<int,int>& a, const pair<int,int>& b){
        long long A = 1LL * a.first * a.second;
        long long B = 1LL * b.first * b.second;
        if (A != B) return A > B;               // 面积降序
        if (a.first != b.first) return a.first > b.first; // 次级规则（可选）
        return a.second > b.second;
    });
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, T;
    if (!(cin >> N >> K >> T)) return 0;
    vector<pair<double,double>> boxes(N);
    for (int i = 0; i < N; ++i) {
        cin >> boxes[i].first >> boxes[i].second;
    }
    auto centers = kmeansAnchors(boxes, K, T);
    for (int i = 0; i < (int)centers.size(); ++i) {
        cout << centers[i].first << " " << centers[i].second;
        if (i + 1 < (int)centers.size()) cout << "\n";
    }
    return 0;
}

题目内容

【背景信息】YOLO (You Only Look Once) 系列算法在目标检测领域采用了基于Anchor的机制。Anchor是预定义在图像上的一组固定尺寸和比例的参考框，在特征图的每个位置上预设多个Anchor框作为物体位置和尺寸预测的基准。通过模型预测Anchor与真实框的偏移量$(\Delta x, \Delta y, \Delta w, \Delta 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 = \frac{\text{交集面积}}{\text{并集面积}}$$

对于检测框$B1(w_1,h_1)$ 和 $B2(w_2,h_2)$，交集面积计算为：

$$intersection = \min(w_1, w_2) \times \min(h_1, h_2) $$

并集面积则为两框总面积减去交集：

$$union = w_1 \times h_1 + w_2 \times h_2 - intersection $$

最终：IOU = intersection/(union + 1e-16) (加极小值避免除零)

输入描述

第一行：$N, K, T$，以空格分开。

其中：

• $N$ 为训练集中检测框的个数，$10 \leq N \leq 80$

• $K$ 为聚类中心个数，$3 \leq K \leq 9$

• $T$ 为聚类迭代次数，$2 \leq T \leq 30$

接下来 $N$ 行：每行为检测框的宽与高，用空格分开。

输出描述

按照聚类中心的面积从大到小的顺序，输出聚类后的中心。

（聚类中心的面积 = 聚类中心的宽 $\times$ 聚类中心的高）

样例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

说明

1. 输入第一行为 $12 \; 4 \; 20$，代表12个检测框，要聚成4类，最大迭代次数为20，接下来的12行是检测框的宽与高。

2. 取前4个框 $[12, 23], [34, 21], [43, 23], [199, 23]$ 作为初始聚类中心。

3. 迭代更新计算聚类中心，注意每次迭代时聚类中心都做向下取整。

4. 按照聚类中心的面积（宽 × 高）从大到小排序，输出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

说明

1. 输入第一行为 $12 \; 3 \; 10$，代表12个检测框，要聚成3类，最大迭代次数为10，接下来的12行是检测框的宽与高。

2. 取前3个框 $[12, 23], [34, 21], [43, 23]$ 作为初始聚类中心。

3. 迭代更新计算聚类中心，注意每次迭代时聚类中心都做向下取整。

4. 按照聚类中心的面积（宽 × 高）从大到小排序，输出3个Anchor聚类中心。

提示

注：每次迭代的距离度量 $d$ 和交并比 $IOU$ 都是用浮点数计算，但每次迭代和最终输出的聚类中心都要做向下取整。

▶️