Geek Answers Handbook

How to move large values ​​close to the matrix diagonal in the correlation matrix

I have a correlation matrix X of five elements (C1, C2, C3, C4, C5)

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 *

I want to use MatLab to move whole non-zero cells close to the diagonal, and the diagonal cells are "*".

For example, you may notice that the columns and rows are shifted in the next matrix, and the diagonal cells are “*”.

  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 *

Because I want to do clustering, so I want all non-zero cells to move closer to the diagonal after the shift. This is an NP-hard problem.

Does anyone know what functions in MatLab can implement this?

+4
source share
2 answers

What you're looking for is perhaps the Cuthill-McKee (RCM) inverse algorithm , which pretty much does what you want: for this matrix finds a permutation that tends to make its non-zero elements closer to the diagonal. There is a built-in symrcm function in MATLAB that does just that.

So, assuming X is your matrix, you can do the following:

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

Xnew is the new reordered matrix, and p is the new row / column order.

Example

First, create a matrix:

 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]

Now reorder it:

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

Result:

 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

Seems right.

+3
source 
 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 + (lm)^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 + (ik)^2/2; permuted_metric = permuted_metric + (jk)^2/2; end end % Row j for k = 1:N if(k ~= i && k ~= j && A(j,k)) current_metric = current_metric + (jk)^2/2; permuted_metric = permuted_metric + (ik)^2/2; end end % Col i for k = 1:N if(k ~= i && k ~= j && A(k,i)) current_metric = current_metric + (ik)^2/2; permuted_metric = permuted_metric + (jk)^2/2; end end % Col j for k = 1:N if(k ~= i && k ~= j && A(k,j)) current_metric = current_metric + (jk)^2/2; permuted_metric = permuted_metric + (ik)^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(:,[ij]) = A(:,[ji]); % Now switch rows A([ij],:) = A([ji],:); 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 + (lm)^2/2; end end end disp(global_energy);

Terminal:

  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
0
source

More articles:


All Articles