置换矩阵的行和列以进行聚类

Question

我有一个尺寸为1000x1000的距离矩阵,沿对角线对称为0.我想通过同时重新排序矩阵的行和列来形成距离(簇)的分组.这就像在使用热图可视化其聚类之前重新排序矩阵一样.我觉得这应该是一个简单的问题,但我没有太多运气找到在线进行排列的代码.有人可以帮忙吗？

Answer 1

这是一种想到的方法:

1. "稀疏化"矩阵,以便只有"足够接近"的邻居在矩阵中具有非零值.
2. 使用Cuthill-McKee算法压缩稀疏矩阵的带宽.
3. 使用步骤2的结果对原始矩阵进行对称重新排序.

例

我将使用Octave(我正在做的一切也应该在Matlab中工作),因为它内置了Reverse Cuthill-McKee(RCM)实现.

首先,我们需要生成距离矩阵.此函数创建一组随机点及其距离矩阵:

function [x, y, A] = make_rand_dist_matrix(n)
  x = rand(n, 1);
  y = rand(n, 1);
  A = sqrt((repmat(x, 1, n) - repmat(x', n, 1)).^2 +
       (repmat(y, 1, n) - repmat(y', n, 1)).^2);
end

让我们使用它来生成和可视化100点示例.

[x, y, A] = make_rand_dist_matrix(100);
surf(A);

从上面查看表面图得到下面的图像(当然,你的图像会有所不同).

暖色代表比冷色更大的距离.i矩阵中的行(或列,如果您愿意)包含点i和所有点之间的距离.点i和点之间的距离j在入口处A(i, j).我们的目标是重新排序矩阵,使得对应于点的行i靠近对应于距离较近的点的行i.

稀疏化的一种简单方法A是使所有条目都大于某个阈值零,这就是下面所做的,尽管更复杂的方法可能更有效.

B = A < 0.2;   % sparsify A -- only values less than 0.2 are nonzeros in B
p = symrcm(B); % compute reordering by Reverse Cuthill-McKee
surf(A(p, p)); % visualize reordered distance matrix

现在,矩阵的排序方式使矩阵中的附近点更加靠近.当然,这个结果并不是最佳的.使用启发式算法计算稀疏矩阵带宽压缩,并且RCM是一种非常简单的方法.正如我上面提到的,用于产生稀疏矩阵的更复杂的方法可以给出更好的结果,并且不同的算法也可以产生针对该问题的更好结果.

纯娱乐

查看发生的事情的另一种方法是绘制点并连接一对点,如果它们在矩阵中的相应行是相邻的.你的目标是让线条连接彼此靠近的点对.为了获得更具戏剧性的效果,我们使用比上述更多的点数.

[x, y, A] = make_rand_dist_matrix(2000);
plot(x, y);   % plot the points in their initial, random order

显然,连接遍布各处,并且发生在各种各样的距离上.

B = A < 0.2;     % sparsify A
p = symrcm(B);
plot(x(p), y(p)) % plot the reordered points

重新排序后,连接往往距离更小,更有序.