4

我有五个元素（C1、C2、C3、C4、C5）的相关矩阵 X

      C1    C2    C3     C4   C5  

 C1    *     1     0     1     0
 C2    1     *     0     0     1
 C3    0     0     *     1     1
 C4    1     0     1     *     0
 C5    0     1     1     0     *

我想使用 MatLab 将尽可能多的非零单元格靠近对角线，同时保持对角线单元格为“*”。

例如，您可能会注意到以下矩阵中的列和行正在移动，而对角线单元格是“*”。

      C1    C4    C2     C5   C3  

 C1    *     1     1     0     0
 C4    1     *     0     0     1
 C2    1     0     *     1     0
 C5    0     0     1     *     1
 C3    0     1     0     1     *

因为我想做聚类，所以我希望尽可能多的非零单元格在移位后接近对角线。这是一个 NP 难题。

任何人都知道 MatLab 中的哪些功能可以实现这一点？

4

2 回答 2

4

您正在寻找的可能是反向 Cuthill-McKee 算法 (RCM)，它几乎可以满足您的需求：对于给定的矩阵，它会找到一个排列，其非零元素往往更接近对角线。MATLAB 中有一个内置函数symrcm可以做到这一点。

因此，假设这X是您的矩阵，您可以执行以下操作：

p = symrcm(X);
Xnew = X(p, p);

Xnew是新的重新排序矩阵，并且p是新的行/列顺序。

例子

我们先创建一个矩阵：

X = [10 0 0 7 0; 3 20 0 0 11; 0 0 30 0 29; 12 7 0 40 0; 0 33 0 0 50]

现在让我们重新排序：

p = symrcm(X);
Xnew = X(p, p)

结果是：

Xnew =    
    40    12     7     0     0
     7    10     0     0     0
     0     3    20    11     0
     0     0    33    50     0
     0     0     0    29    30

似乎是对的。

于 2013-03-12T12:15:44.893 回答
1 
A = [1 0  0 1 0;
     0 1  0 0 1;
     0 0  1 0 1;
     1 1  0 1 0;
     0 1  0 0 1]; 
N = length(A);
switched = false;

%%
% Calculate initial Global Energy
disp(A);
global_energy = 0;
for l = 1:N
    for m = 1:N
        if(A(l,m))
            global_energy = global_energy + (l-m)^2/2;
        end
    end
end
disp(global_energy); 

counter = 0;
counter_cutoff = 10000000000;
while(true)
    switched = false;
    counter = counter + 1;
    for i = 1:N
        for j = i+1:N        
            current_metric = 0; % Calculate metric of row i and j with columns i and j
            permuted_metric = 0; % Calculate metric if they were permuted        
            % Row i
            for k = 1:N
                if(k ~= i && k ~= j && A(i,k))
                    current_metric = current_metric + (i-k)^2/2;
                    permuted_metric = permuted_metric + (j-k)^2/2;
                end
            end
            % Row j
            for k = 1:N
                if(k ~= i && k ~= j && A(j,k))
                    current_metric = current_metric + (j-k)^2/2;
                    permuted_metric = permuted_metric + (i-k)^2/2;
                end
            end
            % Col i
            for k = 1:N
                if(k ~= i && k ~= j && A(k,i))
                    current_metric = current_metric + (i-k)^2/2;
                    permuted_metric = permuted_metric + (j-k)^2/2;
                end
            end
            % Col j 
            for k = 1:N
                if(k ~= i && k ~= j && A(k,j))
                    current_metric = current_metric + (j-k)^2/2;
                    permuted_metric = permuted_metric + (i-k)^2/2;
                end
            end

            % If permuted metric is less, swap columns and rows - set switched to true 
            if(permuted_metric < current_metric)
                switched = true; % there was at least one switch
                % Now switch rows and columns
                % Switch columns first
                A(:,[i j]) = A(:,[j i]);
                % Now switch rows
                A([i j],:) = A([j i],:);
            end
        end
    end
    if(~switched || counter > counter_cutoff)
        % All permutations did not lead to a switching of rows and columns
        break;
    end
end

% Calculate final Global Energy
disp(A);
global_energy = 0;
for l = 1:N
    for m = 1:N
        if(A(l,m))
            global_energy = global_energy + (l-m)^2/2;
        end
    end
end
disp(global_energy);

终端：

 1     0     0     1     0
 0     1     0     0     1
 0     0     1     0     1
 1     1     0     1     0
 0     1     0     0     1

22

 1     1     0     0     0
 1     1     1     0     0
 0     0     1     1     0
 0     0     1     1     0
 0     0     0     1     1

 3
于 2013-03-12T07:11:13.253 回答