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

Question

这是在这里发布的问题的继续: 在2D位图上寻找质心,其中讨论了在布尔矩阵中找到质心,如给出的示例.

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

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

注意：我在这里使用曼哈顿距离（又名 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)

这是一个非常直观的结果，只需查看您的矩阵即可（请注意，与您的示例相比，坐标是从零开始的）。