featselp.m

The pattern recognition matlab toolbox

%FEATSELP Pudil's floating feature selection (forward)
% 
% [W,R] = FEATSELP(A,CRIT,K,T,FID)
%
% INPUT	
% 	A    Training dataset
%   CRIT Name of the criterion or untrained mapping 
%        	(default: 'NN', 1-Nearest Neighbor error)
%   K    Number of features to select (default: K = 0, select optimal set)
%   T    Tuning dataset (optional)
%   N    Number of cross-validations (optional)
%   FID  File ID to write progress to (default [], see PRPROGRESS)
%
% OUTPUT
%   W    Feature selection mapping
%   R    Matrix with step-by-step results
% 
% DESCRIPTION
% Forward floating selection of K features using the dataset A. CRIT sets
% the criterion used by the feature evaluation routine FEATEVAL. If the
% dataset T is given, it is used as test set for FEATEVAL. Alternatively
% a number of cross-validations N may be supplied. For K = 0, the optimal
% feature set (maximum value of FEATEVAL) is returned. The result W can
% be used for selecting features in a dataset B using B*W.
% The selected features are stored in W.DATA and can be found by +W.
%
% Note: this routine is highly time consuming.
%
% In R the search is reported step by step:
% 
% 	R(:,1) : number of features
% 	R(:,2) : criterion value
% 	R(:,3) : added / deleted feature
% 
% SEE ALSO
% MAPPINGS, DATASETS, FEATEVAL, FEATSELO, FEATSELB, FEATSELI,
% FEATSEL,  FEATSELF, FEATSELM, PRPROGRESS

% Copyright: R.P.W. Duin, [e-mail]
% Faculty of Applied Sciences, Delft University of Technology
% P.O. Box 5046, 2600 GA Delft, The Netherlands

% $Id: featselp.m,v 1.3 2007/04/21 23:06:46 duin Exp $

function [w,r] = featselp(a,crit,ksel,t,fid)

	prtrace(mfilename);
	
	if (nargin < 2) | isempty(crit)
    prwarning(2,'no criterion specified, assuming NN');
		crit = 'NN'; 
	end
	if (nargin < 3) | isempty(ksel)
		ksel = 0; 
	end
	if (nargin < 4) | isempty(t)
    prwarning(3,'no tuning set supplied (risk of overfit)');
		t = [];
	end
	if (nargin < 5)
		fid = [];
	end

  % If no arguments are supplied, return an untrained mapping.

	if (nargin == 0) | (isempty(a))
		w = mapping('featselp',{crit,ksel,t});
		w = setname(w,'Floating FeatSel');
		return
	end

	isvaldfile(a,1,2); % at least 1 object per class, 2 classes
	a = testdatasize(a);
	iscomdset(a,t);
	
	[m,k,c] = getsize(a); featlist = getfeatlab(a);

	% If KSEL is not given, return all features.

	if (ksel == 0)
		peak = 1; ksel = k; 
	else 
		peak = 0; 
	end

	if (~isempty(t))
		if (k ~= size(t,2))
      error('The sizes of the training and tuning dataset do not match.')
		end
	end

	critval_opt = zeros(1,k);	% Maximum criterion value for sets of all sizes.
  critval_max = 0;    			% Maximum criterion value found so far.
  I = [1:k];      			    % Pool of remaining feature indices.
  J = [];      			      	% Pool of selected feature indices.
  r = [];           			  % Result matrix with selection history.
	Iopt = J; 

	n = 0;
	prprogress(fid,'\nfeatselp: Pudils Floating Search\n')
	while (n < k)

		critval = zeros(1,length(I));

		% Add the best feature.

		for j = 1:length(I)
			L = [J,I(j)];					% Add one feature to the already selected ones.

			if (isempty(t))				% Evaluate the criterion function.
				critval(j) = feateval(a(:,L),crit);
			else
				critval(j) = feateval(a(:,L),crit,t(:,L));
			end

      % If this feature is the best so far and we have not yet selected
			% KSEL features, store it.

			if (critval(j) > critval_max) & (n < ksel)
				n_max = length(L);
				critval_max = critval(j);
				Iopt = L;
			end
		end

    [mx,j] = max(critval);  % Find best feature of the remaining ones,
    J = [J, I(j)];          %   add it to the set of selected features
    I(j) = [];              %   and remove it from the pool.

		% Store the best criterion value found for any set of n features.
		n = n + 1; critval_opt(n) = mx;

		r = [r; [n, mx, J(end)]];
		prprogress(fid,'  %d %f',r(end,1:2));
		prprogress(fid,' %i',J);
		prprogress(fid,'\n')
		
		% Now keep removing features until the criterion gets worse.

		while (n > 2)
			critval = zeros(1,n);
			for j = 1:n
				L = J; L(j) = [];		% Remove one feature from the selected ones.		

				if (isempty(t))			% Evaluate the criterion function.
					critval(j) = feateval(a(:,L),crit);
				else
					critval(j) = feateval(a(:,L),crit,t(:,L));
				end		

				% If removing this feature gives the best result so far (or
				% the same result using less features), and we have not yet
				% removed all KSEL features, store it.

				if ((critval(j) > critval_max) | ((critval(j) == critval_max) & ...
																					(length(L) < n_max))) & ...
					 (n <= ksel + 1)
					n_max = length(L);
					critval_max = critval(j);
					Iopt = L;
				end
			end

			% If this subset is better than any found before, store and report it.
			% Otherwise, stop removing features.

			[mx,j] = max(critval);

			if (mx > critval_opt(n-1))
				n = n - 1; critval_opt(n) = mx;
				I = [I,J(j)]; J(j) = [];
				r = [r; [n, mx, -I(end)]];
		    prprogress(fid,'  %d %f',r(end,1:2));
				prprogress(fid,' %i',J);
				prprogress(fid,'\n')
			else
				break;
			end

		end

		% If we have found more than KSEL features, return the mapping using
		% the best KSEL features.

		if (n > ksel)
			if (ksel < length(Iopt))
				J = Iopt(1:ksel);
			else
				J = Iopt;
			end
			prprogress(fid,'featselp finished\n')
			w = featsel(k,J);
			w = setlabels(w,featlist(J,:));
			w = setname(w,'Floating FeatSel');
			return
		end

	end
	prprogress(fid,'featselp finished\n')
	
	% Return all features, sorted by their criterion value.

	w = featsel(k,Iopt);
	w = setlabels(w,featlist(Iopt,:));
	w = setname(w,'Floating FeatSel');

return