mis.m

一个matlab的工具包,里面包括一些分类器 例如 KNN KMEAN SVM NETLAB 等等有很多.

% Modified Improved Iterative Scaling Algorithm
%
% function run = mis(input_file, max_iter, scale_flag, sparse_flag, newtonmethod, smooth_flag, alpha)
%
% input_file:		input filename, string
% max_iter:		maximum number of iteration
% sparse_flag:		sparse data (text data) ?
% newtonmethod(string):	MIS, MIS_ONCE, MIS_ONCE_DEBUG
% smooth_flag:		which kind of smoothing, 
%			0 means upper/lower bound, otherwise means IIS	back-off
% alpha:		back-off weight for IIS
%

function run = mis(input_file, max_iter, sparse_flag, newtonmethod, smooth_flag, alpha)

if (nargin < 2), max_iter = 100; end;
if (nargin < 3), sparse_flag = 0; end;
if (nargin < 4), newtonmethod = 'MIS'; end;
if (nargin < 5), smooth_flag = 0; end;
if (nargin < 6), alpha = 0; end;

min_value = 0.001;
% Load UCI data (or Text Data if sparse flag == 1)
Data = dlmread(input_file, ',');
if sparse_flag
  Data = spconvert(Data);
end

% Set some parameters
FeatureNum = size(Data, 2) - 1;
DataNum = size(Data, 1);
X = abs(Data(:, 1:FeatureNum)); % X must have non-negative values
Y = full(Data(:, FeatureNum + 1)); % make Y a full matrix

% Perform feature selection for Text Data
if sparse_flag
  X_sum = sum(X > 0);
  [C, I] = sort(X_sum);
  X = full(X(:, I(length(I)-499:length(I))));
  num_feature = 500;
end
X = (X == 0) .* min_value + X;

% Adjust the class labels, so that it begins from 1!
class_set = unique(Y);
New_Y = zeros(DataNum, 1);
for i = 1:length(class_set)
  New_Y = New_Y + (Y == class_set(i)) .* i;
end
Y = New_Y;
ClassNum = max(Y); % number of classes of the data

% initialize the parameters
Lamdas = zeros(FeatureNum, ClassNum);
Deltas = zeros(FeatureNum, ClassNum);
OldDeltas = zeros(FeatureNum, ClassNum);

% compute the empirical expectation for each class
EmpiricalExp = zeros(FeatureNum, ClassNum);
for classindex = 1 : ClassNum
  EmpiricalExp(:, classindex) = sum(X(Y == classindex, :))' / DataNum;
end

% compute the f^#
FeatureSharp = sum(X');
pow = FeatureSharp;

% the main loop of MIS
for iter = 1 : max_iter
  % compute the class probabilities
  ClassMat = X * Lamdas;
  ClassMax = max(ClassMat')';
  for classindex = 1:ClassNum
    ClassMat(:, classindex) = ClassMat(:, classindex) - ClassMax;
  end;
  ClassProbs = exp(ClassMat);

  % normalizer
  Z = sum(ClassProbs')';

  % normalize the class probabilities
  for classindex = 1 : ClassNum
    ClassProbs(:, classindex) = ClassProbs(:, classindex) ./ Z;
  end
  % compute the log-likelihood
  LL = 0.0;
  for classindex = 1 : ClassNum
    LL = LL + sum(log(ClassProbs(Y == classindex, classindex)));
  end
  
  % print out the current log-likelihood
  if (mod(iter, 50) == 0)
    fprintf('Iteration %d:\t%f, AVG LL = %f\n', iter, LL, LL/DataNum);
  end
  
  % preprocessing the old deltas
  if (smooth_flag == 0)
    for classindex = 1 : ClassNum
      for lamdaindex = 1 : FeatureNum
        if OldDeltas(lamdaindex, classindex) < 1.0e-20
            OldDeltas(lamdaindex, classindex) = 1.0e-20;
        elseif OldDeltas(lamdaindex, classindex) > 10
            OldDeltas(lamdaindex, classindex) = 10;
        end
      end
    end
  else
	OldDeltas = alpha + ( 1 - alpha ) * OldDeltas;    
  end

  % update the lamdas using Newton's method
  % estimate each parameters' augmentation (delta)
  totalbound = 0.0;
  for classindex = 1 : ClassNum
    W = (X * OldDeltas(:, classindex))';
    for lamdaindex = 1 : FeatureNum
      coef = (ClassProbs(:, classindex) .* X(:, lamdaindex))' / DataNum;
      % recompute the pows
      if (iter == 1)
            [root, fval,bound] = integrated_newton(newtonmethod, coef, ...
					       FeatureSharp, -EmpiricalExp(lamdaindex, classindex), 100);
      else
            pow = W / OldDeltas(lamdaindex, classindex);
            [root, fval, bound] = integrated_newton(newtonmethod, coef, pow, -EmpiricalExp(lamdaindex, classindex), 100);
      end
      Deltas(lamdaindex, classindex) = root;
      totalbound = totalbound + bound;
    end
  end
  if (strcmp(newtonmethod, 'MIS_ONCE_DEBUG') == 1) & (totalbound < 0.0)
    fprintf('Newton Approximation may have trouble:( %f < 0.0 )!\n', ...
	    totalbound);
  end
  
  Lamdas = Lamdas + Deltas;
  OldDeltas = abs(Deltas);
  run.e(iter) = LL / DataNum;  
end