algorithm - 在矩阵/位图中查找质量簇

Question

这是这里发布的问题的延续: Finding the center of mass on a 2D bitmap正如给出的示例，其中讨论了如何在 bool 矩阵中找到质心。

假设现在我们将矩阵展开为这种形式:

0 1 2 3 4 5 6 7 8 9
1 . X X . . . . . .
2 . X X X . . X . .
3 . . . . . X X X .
4 . . . . . . X . .
5 . X X . . . . . .
6 . X . . . . . . .
7 . X . . . . . . .
8 . . . . X X . . .
9 . . . . X X . . .

如您所见，我们现在有 4 个质心，对应 4 个不同的集群。

我们已经知道如何在只有一个质心存在的情况下找到质心，如果我们在此矩阵上运行该算法，我们将在矩阵中间得到一些点，这对我们没有帮助。

什么是找到这些质量簇的好、正确和快速的算法？

Answer 1

我想我会检查矩阵中的每个点并根据它的邻居计算出它的质量。点的质量会随着距离的平方下降。然后，您可以选择彼此之间距离最短的前四个点。

下面是我编写的一些 Python 代码，试图说明找出每个点的质量的方法。使用您的示例矩阵的一些设置:

matrix = [[1.0 if x == "X" else 0.0 for x in y] for y in """.XX......
.XXX..X..
.....XXX.
......X..
.XX......
.X.......
.X.......
....XX...
....XX...""".split("\n")]

HEIGHT = len(matrix)
WIDTH = len(matrix[0])
Y_RADIUS = HEIGHT / 2
X_RADIUS = WIDTH / 2

计算给定点的质量:

def distance(x1, y1, x2, y2):
  'Manhattan distance http://en.wikipedia.org/wiki/Manhattan_distance'
  return abs(y1 - y2) + abs(x1 - x2)

def mass(m, x, y):
  _mass = m[y][x]
  for _y in range(max(0, y - Y_RADIUS), min(HEIGHT, y + Y_RADIUS)):
    for _x in range(max(0, x - X_RADIUS), min(WIDTH, x + X_RADIUS)):
      d = max(1, distance(x, y, _x, _y))
      _mass += m[_y][_x] / (d * d)
  return _mass

注意:我使用的是 Manhattan距离(也称为 Cityblock，也称为 Taxicab Geometry)，因为我认为使用欧几里得距离增加的准确性不值得调用 sqrt() 的成本。

遍历我们的矩阵并构建元组列表，例如 (x, y, mass(x,y)):

point_mass = []
for y in range(0, HEIGHT):
  for x in range(0, WIDTH):
    point_mass.append((x, y, mass(matrix, x, y)))

根据每个点的质量对列表进行排序:

from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)

查看排序列表中的前 9 个点:

(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 1, 4.6736111111111107)
(1, 4, 4.5938888888888885)
(2, 0, 4.54)
(4, 7, 4.4480555555555554)
(1, 5, 4.4480555555555554)
(5, 7, 4.4059637188208614)
(4, 8, 4.3659637188208613)

如果我们从最高到最低工作并过滤掉与已经看到的点太接近的点，我们将得到(我正在手动完成，因为我现在没有时间用代码来完成...... .):

(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)

这是一个非常直观的结果，只需查看您的矩阵(请注意，与您的示例进行比较时，坐标是从零开始的)。