algorithm - 聚类一组矩形

Question

我有一组矩形，我需要根据它们之间的欧几里德距离将它们聚集在一起。附图中解释了这种情况。.

一种可能的方法是取每个矩形的中心并使用 K 均值对中心点进行聚类（距离函数将是 XY 平面中的欧几里德距离）。但是，我想知道是否有任何其他方法可以解决这个问题，它不是通过中心点来近似矩形，而是考虑到矩形的实际形状。

Answer 1

只要您可以定义它们之间的距离（例如最小矩形到矩形的距离），就可以查看可以与任意数据类型一起使用的算法，例如DBSCAN和OPTICS 。

K-means 可能不太好，因为它是为具有平方欧几里得距离（= 平方和，簇内方差）的点数据设计的。

Answer 2

制定这个问题的一种方法是查看每个矩形i，以及每对(i,j)具有距离的矩形d(i,j)，然后从中形成一个距离矩阵。这个距离度量d可以是矩形中心之间的距离，也可以是更花哨的东西，比如矩形上最近点之间的距离。

然后，应用一个将距离矩阵作为输入的聚类算法，将距离矩阵定义D为元素为 的(i,j)矩阵d(i,j)。

相关：使用距离矩阵进行聚类

Anony-Mousse 的回答对给定距离矩阵的可用于聚类的算法提供了一些不错的建议。

Answer 3

我们使用带有 left_x、right_x、top_y、bottom_y 坐标的光谱聚类作为特征，结果非常好。