appcoars_m.m

Coarsening approximations of belief functions

function [mm,FFc,FFa,C,N,N0]=appcoars_m(mm,FF,K,version);

% Copyright Thierry Denoeux 
% April 4, 2002
%

% Joint inner and outer coarsening approximation of several 
% basic belief assignments (bba)
%
% [mm,FFc,FFa,C,N,N0]=appcoars_m(mm,FF,K,version);
%
% Input:
% mm = cell array containing the belief masses of the bba's
%      mm{k} is the vector (n,1) of belief masses for the n focal elements of the k-th bba
% FF = cell array containing the focal elements of the bba's
%      FF{k} is a (n,c) matrix of focal elements for the k-th bba
% Let F=FF{k}. Then:
% F(i,j)=1 if focal element Fi contains element j
%       =0 otherwise
% K = desired size of frame
% version = 'in' for inner approximation, 'out' for outer approximation
%
% Output
% mm = cell array containg the new vectors of belief masses. 
%      mm{k} is a vector of size (n1,1), with n1 <= n (the number of focal elements can only decrease) 
% FFc = cell array containg the new matrices of focal elements.
%       FFc{k} is of size (n1,K)
% FFa = cell array containg the corresponding matrices of focal elements
%       FFa{k} is of size (n1,c) 
% C = vector (c,1). C(i) is the class of singleton i in the partition
% N = sum of the cardinalities of the bba's after approximation
% N0 = initial sum of cardinalities (before approximation)
%
% Reference:
% A. Ben Yaghlane, T. Denoeux and K. Melloui. Coarsening approximations of belief functions. 
% In S. Benferhat and P. Besnard, Eds, Proceedings of ECQSARU'2001, pages 362-373, Toulouse, 
% September 2001, Springer-Verlag.
ns=length(FF);
F=[];m=[];
nn=zeros(ns,1);
for i=1:ns,
   F=[F;FF{i}];
   nn(i)=size(FF{i},1);
   m=[m;mm{i}];   
end;
[n,c]=size(F);
C=zeros(c,1);
c0=c;

Fc=F;

if strcmp(version,'out'),
   iv=1;
elseif strcmp(version,'in')
   iv=2;
else,
   disp('Error: unknown version !');
   return
end;

N0=zeros(ns,1);
for i=1:ns,
  F1=FF{i};
  m1=mm{i};
  N0(i)=sum(F1')*m1;
end;

if K>= c,
  C=1:c;
  FFc=FF;
  FFa=FF;
  N=N0;
  return
else

% calculation of distance matrix
D=ones(c,c)*inf;
for i=2:c,
  for j=1:i-1,
    D(i,j)=m'*abs(Fc(:,i)-Fc(:,j));
  end;
end;
for i=1:c, I{i}=i; end;

while (c > K),
  [dm,im,jm]=min2(D);
  I{c+1}=[I{im};I{jm}];
  if iv==1,
     Fc(:,c+1)=max([Fc(:,im) Fc(:,jm)],[],2);
  else,
     Fc(:,c+1)=min([Fc(:,im) Fc(:,jm)],[],2);
  end;
  for j=1:c,
    D(c+1,j)=m'*abs(Fc(:,c+1)-Fc(:,j));
  end;
  D(:,c+1)=inf*ones(c+1,1);
  Fc(:,[im jm])=[];
  D([im jm],:)=[];D(:,[im jm])=[];
  I([im jm])=[];
  c=c-1;
end;
for k=1:c,
  C(I{k})=k*ones(length(I{k}),1);
end;
end;

% cleaning

imax=0;
for i=1:ns,
   FFc{i}=Fc(imax+1:imax+nn(i),:);
   imax=imax+nn(i);   
end;
N=N0;
for k=1:ns,
   Fc1=FFc{k};
   mc1=mm{k};
   [Fc1,I,J]=unique(Fc1,'rows');
   n1=size(Fc1,1);
   m1=zeros(n1,1);
   for i=1:n1,
     ii=find(J==i);
     m1(i)=sum(mc1(ii));
   end;
  [temp ii]=sort(-m1);
  m1=-temp;
  Fc1=Fc1(ii,:);
% Vacuous extension
  Fa=zeros(n1,c0);
  for i=1:c0,
    Fa(:,i)=Fc1(:,C(i));
  end;
  mm{k}=m1;
  FFc{k}=Fc1;
  FFa{k}=Fa;
  N(k)=sum(Fa')*m1;
end;


%---------------------------------
function [x,i,j]=min2(X)

[y,ii]=min(X);
[x,j]=min(y);
i=ii(j);