Re: Clustering Pairs

us — Thu, 02 Aug 2007 06:16:03 -0400

Marie:
<SNIP down to problem with example...

> [1 10;1 11;1 12;2 11;5 10;5 15;6 18]
> I want to cluster together all pairs of numbers that contain common values. For example, in this case this would be [1 2 5 10 11 12 15] and [6 18]...

there are many solutions to this.
however, your example does not make sense...
can you be more clear?
us

Clustering Pairs

Marie — Thu, 02 Aug 2007 02:16:44 -0400

Greetings,
I have a series of pairs of numbers, e.g.:
[1 10;1 11;1 12;2 11;5 10;5 15;6 18]
I want to cluster together all pairs of numbers that contain common values. For example, in this case this would be [1 2 5 10 11 12 15] and [6 18].
Any help is appreciated!
S

Re: Clustering Pairs

ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford) — Thu, 02 Aug 2007 01:51:12 -0400

In article <f8reqc$o08$1@fred.mathworks.com>, "Marie "
<sarrowsmith@gmail.com> wrote:

> Greetings,
> I have a series of pairs of numbers, e.g.:
> [1 10;1 11;1 12;2 11;5 10;5 15;6 18]
> I want to cluster together all pairs of numbers that contain common
values. For example, in this case this would be [1 2 5 10 11 12 15] and [6
18].
> Any help is appreciated!
> S
----------------------
I believe you are seeking what in mathematics is known as an equivalence
relation, Marie. For example, the 2 and the 15 are in the same
equivalence class (cluster) because of a chain of pairings connecting
them: (2,11), (11,1), (1,10), (10,5), and (5,15). (Note that order within
the pairs is not significant.) If I am interpreting you correctly, the
following is designed to carry out the desired clustering. However, since
my version of matlab does not have the cell array feature, I leave the
last step to you.

% Choose a two-columned array A of pairs regarded as equivalent
A = [1 10;1 11;1 12;2 11;5 10;5 15;6 18];

% Then develop a transitive, commutative (symmetric) matrix M.
[B,ig,N] = unique(A(:)); % Find all the unique elements of A
n = size(B,1);
N = reshape(N,[],2); % N is same size as A with indices into B
M = accumarray(N,1,[n,n]); % Place 1's in M corres. to pairs in N
M = M+M.'; % Make M symmetric
M(M~=0) = 1; % Set nonzeros equal to 1
fg = true;
while fg % Loop until M is entirely transitive and symmetric
Mc = M; % Save copy of M
M = M*M+M; % Extend M transitively
M(M~=0) = 1; % Replace nonzeros with ones
fg = any(any(M~=Mc)); % Quit loop when M remains unchanged
end

% The unique rows of M indicate the desired equivalence sets (clusters)
C = unique(M,'rows'); % Find unique rows of M

% For each row of C, convert the 1's to the corresponding elements of A
c{i} = B(C(i,:)~=0);
% Presumably you will place each of these c{i}'s in a cell array, since
they are of differing lengths.

The truth is that I don't have the 'unique' and 'accumarray' functions
either, so you should test this out carefully, since it is difficult for
me to do so thoroughly. I have only had the patience to carry out a
simple test where the 'unique' and 'accumarrays' have been manually
determined.

Roger Stafford

MATLAB Central Newsreader - Clustering Pairs

Re: Clustering Pairs

Clustering Pairs

Re: Clustering Pairs