appcoars.m

Coarsening approximations of belief functions

function [m,Fc,Fa,C,N,N0]=appcoars(m,F,K,version);

% Copyright Thierry Denoeux 
% April 4, 2002
%

% Inner and outer coarsening approximation of a single basic belief assignment
%
% [m,Fc,Fa,C,N]=appcoars(m,F,K,version);
%
% Input:
% m = vector (n,1) of belief masses for the n focal elements
% F = (n,c) matrix of focal elements
% 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
% m = new vector of belief masses, of size n1<=n (the number of focal 
%     elements have decreased)
% Fc = new (n1,K) matrix of focal elements
% Fa = corresponding (n1,c) matrix of focal elements
% C = vector (c,1). C(i) is the class of singleton i in the partition
% N = cardinality of the approximation 
% N0 = initial cardinality (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.



[n,c]=size(F);
C=zeros(c,1);
c0=c;

Fc=F;

[p,q]=size(m);
if q>p, m=m'; end;

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

N0=sum(F')*m;

if K>= c,
   C=1:c;
   Fc=F;
   Fa=F;
   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

[Fc1,I,J]=unique(Fc,'rows');
n=size(Fc1,1);
m1=zeros(n,1);
for i=1:n,
  ii=find(J==i);
  m1(i)=sum(m(ii));
end;
m=m1;Fc=Fc1;


% Vacuous extension
Fa=zeros(n,c0);
for i=1:c0,
   Fa(:,i)=Fc(:,C(i));
end;

[temp ii]=sort(-m);
m=-temp;
Fc=Fc(ii,:);
Fa=Fa(ii,:);

N=sum(Fa')*m;

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

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