4

5 つの要素 (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)です。これは、ほとんどあなたが望むことを行います: 与えられた行列に対して、対角に近い非ゼロ要素を持つ傾向がある順列を見つけます。symrcmMATLAB には、まさにそれを行う組み込み関数があります。

したがって、それがマトリックスであると仮定する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 に答える