NNF

Non Negative Matrix Factorization

Non negative Matrix factorization is another linear subspace method used in clustering algorithms. Due to it's optimization aim it has inherent clustering properties and has e.g. been used for face recognition tasks, spectral data analysis astronomy and others.

Check out the great wikipedia articel here

Implementation details

This class provides 3 different approaches for NNF matrices from the MIT's journaclub (id = 21). The approach is a interative one and use (described here:

• divergence update approach
• eukledian update approach
• alternating least squares.

Interface description

   TNNMFProps = record
     MaxIter : integer;            // maximum number of iterations used to find a solution 
     tolUpdate : double;           // algorithm converges if reconstruction error
                                  // does not change by this tolerance. If set to 0 the Maximum iterations are used
     method : TNNMFPropsMethod;     // if false use euclidian update
     RankOfBasis : integer;
     UseLastResIfFail : boolean;   // in case we have problems with the floating point precission use the last valid result
     DoUpdateWithEPSMtx : boolean; // before division the matrix a matrix close to floating point precission is added
   end;

   procedure SetProperties(const props : TNNMFProps);

Overwrites the default properties used in the constructor.

Default values set in the constructor are:

   constructor TNNMF.Create;
   begin
        fProps.MaxIter := 100;
        fProps.method := nnmfDivergence;
        fProps.RankOfBasis := -1; // use all
        fProps.tolUpdate := 1e-4; // use a tolerance
        fProps.UseLastResIfFail := True;
        fProps.DoUpdateWithEPSMtx := True;

        inherited Create;
   end;

   TNMFRes = (nmOk, nmFloatingPointPrecReached, nmFailed);
   
   function TNNMF.CalcNMF(V : TDoubleMatrix) : TNMFRes;

Calculates the NNF according to the properties defined previously. V is in the form:

• width = number of examples
• height = example dimension

Note that one can steere the number of resulting vectors by settings "RankOfBasis". (-1 if the resulting matrix is the same size as the input matrix)

   function ProjectToFeatureSpace(Example: TDoubleMatrix): TDoubleMatrix;
   function Reconstruct(Features: TDoubleMatrix): TDoubleMatrix;

Standard projection functions -> project the new input matrix to the subspace and back

Examples

From the matrix testing suit:

   procedure TTestNMF.TestSimplePatternEukl;
   var V : IMatrix;
       nmf : TNNMF;
       params : TNNMFProps;
       res : TNMFRes;
   {$IFNDEF FPC}
   const cExpectedW : Array[0..79] of double = 
      ( 0.2285, 0, 0, 0, 0, 0.0005, 0, 0,
        0, 0.2378, 0, 0.0001, 0, 0, 0, 0, 
        0, 0, 0.2486, 0, 0, 0, 0, 0.0002,
        0, 0, 0.0001, 0, 0, 0.2476, 0, 0,
        0.0005, 0, 0, 0, 0, 0, 0, 0.2019,
        0.0030, 0, 0, 0, 0.1650, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0.1880, 0.0001,
        0, 0, 0.0406, 0.0556, 0, 0, 0.0010, 0,
        0, 0, 0, 0, 0.1503, 0.0034, 0, 0.0009, 
        0.0002, 0, 0, 0.2514, 0, 0, 0, 0 );
   {$ENDIF}
   begin
        V := TDoubleMatrix.CreateEye(10);
        nmf := TNNMF.Create;
        params.MaxIter := 100;
        params.tolUpdate := 1e-4;
        params.method := nnmfEukledian;
        params.RankOfBasis := 8;
        params.UseLastResIfFail := True;
        params.DoUpdateWithEPSMtx := True;
        nmf.SetProperties(params);

        RandSeed := 331;

        res := nmf.CalcNMF(V.GetObjRef);
        if res <> nmFailed then
        begin
             Status(WriteMtx(nmf.W.SubMatrix, nmf.W.Width));
             Status(WriteMtx(nmf.H.SubMatrix, nmf.H.Width));
        end;

        Check(res <> nmFailed, 'Error calculating NMF from an eye matrix');
        {$IFNDEF FPC}
        // note the FPC uses a different random generator -> results may differ
        Check(CheckMtx(nmf.W.SubMatrix, cExpectedW), 'Error calculating the nmf transformation matrix');
        {$ENDIF}

        nmf.Free;
   end;