Python实现二维点矩形形状聚类：最小化集群总面积并控制数量

你需要的聚类效果参考如下：

核心逻辑说明 #

你提的需求属于带数量约束的最小矩形覆盖聚类问题，优化目标是指定集群数量上限的前提下，最小化所有集群的外包矩形面积之和，目前有两种成熟的实现思路：

• 自底向上聚合：初始每个点为独立集群，每次选择合并后面积增量最小的两个集群合并，直到集群数量达到你设定的阈值，该方法得到的总面积是近似最优的
• 预聚类后生成外包矩形：先用常规聚类方法（如KMeans、DBSCAN）把点分成指定数量的集群，再给每个集群生成最小外包矩形，该方法计算速度更快，适合大数量级的点集

可直接运行的Python代码 #

自底向上聚合实现（适合中小规模点集） #

import numpy as np
from itertools import combinations

class RectCluster:
    def __init__(self, points):
        self.points = np.asarray(points)
        self.x_min, self.x_max = self.points[:, 0].min(), self.points[:, 0].max()
        self.y_min, self.y_max = self.points[:, 1].min(), self.points[:, 1].max()
        self.area = (self.x_max - self.x_min) * (self.y_max - self.y_min)
    
    def merge(self, other_cluster):
        """合并两个集群，返回新的矩形集群"""
        merged_points = np.vstack([self.points, other_cluster.points])
        return RectCluster(merged_points)

def rect_cluster_agg(points: np.ndarray, target_cluster_num: int) -> list[RectCluster]:
    """
    矩形聚类主函数
    :param points: 二维点数组，shape为(n, 2)
    :param target_cluster_num: 目标集群数量
    :return: 聚类后的矩形集群列表
    """
    clusters = [RectCluster([p]) for p in points]
    while len(clusters) > target_cluster_num:
        min_add_area = float('inf')
        best_merge_pair = None
        # 遍历所有组合找合并代价最小的对
        for (i, c1), (j, c2) in combinations(enumerate(clusters), 2):
            merged_c = c1.merge(c2)
            add_area = merged_c.area - c1.area - c2.area
            if add_area < min_add_area:
                min_add_area = add_area
                best_merge_pair = (i, j)
        # 执行合并
        i, j = best_merge_pair
        new_c = clusters[i].merge(clusters[j])
        clusters = [c for idx, c in enumerate(clusters) if idx not in (i, j)] + [new_c]
    return clusters

使用示例 #

# 生成测试点集
points = np.random.rand(100, 2) * 100
# 聚类为5个矩形集群
clusters = rect_cluster_agg(points, target_cluster_num=5)
# 输出结果
for idx, cluster in enumerate(clusters, 1):
    print(f"集群{idx}：x范围[{cluster.x_min:.1f}, {cluster.x_max:.1f}]，y范围[{cluster.y_min:.1f}, {cluster.y_max:.1f}]，面积{cluster.area:.1f}")

性能优化建议 #

• 点数量超过1000时，不要直接用上述全组合遍历的方法，可以引入KD树筛选空间相邻的集群合并候选，大幅降低计算量
• 如果对面积最优性要求不高，可以先用sklearn.cluster.KMeans把点聚为指定K个簇，再对每个簇求最小外包矩形，代码更简单，速度也更快
• 如果需要约束矩形的长宽比、最大面积等参数，可以在合并代价中加入对应的惩罚项即可

内容的提问来源于stack exchange，提问作者baptou