/*
 * Copyright (C) 2018 Edward Raff 
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */
package jsat.outlier;

import java.util.ArrayList;
import java.util.List;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.utils.DoubleList;
import jsat.utils.IntList;
import jsat.utils.concurrent.ParallelUtils;

/**
 * This class implements the Local Outlier Factor (LOF) algorithm for outlier detection. 
 * @author Edward Raff 
 */
public class LOF implements Outlier
{
    int minPnts;
    private DistanceMetric distanceMetric;
    VectorCollection vc = new DefaultVectorCollection<>();
    
    
    /**
     * the points in this collection
     */
    private List X;
    /**
     * Stores the distance of an index in X to it's k'th (minPnts) nearest neighbor. 
     */
    private double[] k_distance;
    private double[] lrd_internal;

    public LOF()
    {
        this(15);
    }
    
    public LOF(int minPnts)
    {
        this(minPnts, new EuclideanDistance());
    }
    
    public LOF(int minPnts, DistanceMetric dm)
    {
        setMinPnts(minPnts);
        setDistanceMetric(dm);
    }

    public void setMinPnts(int minPnts)
    {
        this.minPnts = minPnts;
    }

    public int getMinPnts()
    {
        return minPnts;
    }

    public void setDistanceMetric(DistanceMetric distanceMetric)
    {
        this.distanceMetric = distanceMetric;
    }

    public DistanceMetric getDistanceMetric()
    {
        return distanceMetric;
    }
    
    
    

    @Override
    public void fit(DataSet d, boolean parallel)
    {
        X = d.getDataVectors();
        vc.build(parallel, X, distanceMetric);
        
        int N = X.size();
        k_distance = new double[N];
        List> all_knn = new ArrayList<>();
        List> all_knn_dists = new ArrayList<>();
        
        vc.search(X, minPnts+1, all_knn, all_knn_dists, parallel);//+1 to avoid self distance
        
        ParallelUtils.run(parallel, N, (start, end)->
        {
            for(int i = start; i < end; i++)
                k_distance[i] = all_knn_dists.get(i).get(minPnts);
        });
        
        lrd_internal = new double[N];
        ParallelUtils.run(parallel, N, (start, end)->
        {
            for(int i = start; i < end; i++)
            {
                double reachSum = 0;

                for(int j_indx = 1; j_indx < minPnts+1; j_indx++)
                {
                    int neighbor = all_knn.get(i).get(j_indx);
                    double dist = all_knn_dists.get(i).get(j_indx);
                    reachSum += Math.max(k_distance[neighbor], dist);
                }
                
                //lrd_internal[i] = 1.0/(reachSum/minPnts);
                lrd_internal[i] = minPnts/reachSum;
            }
        });
        
        
    }
    
    double lrd(Vec a, List qi)
    {
        return 0;
    }

    @Override
    public double score(DataPoint x)
    {
        IntList knn = new IntList(minPnts);
        DoubleList dists = new DoubleList(minPnts);
        
        vc.search(x.getNumericalValues(), minPnts, knn, dists);
        
        double lof = 0;
        double lrd_x = 0;
        for(int i_indx = 0; i_indx < minPnts; i_indx++)
        {
            int neighbor = knn.get(i_indx);
            double dist = dists.get(i_indx);
            double reach_dist = Math.max(k_distance[neighbor], dist);
            
            lof += lrd_internal[neighbor];
            
            lrd_x += reach_dist;
        }
        
        //lrd_x now has the local reachability distance of the query x
        lrd_x = minPnts/lrd_x;
        //now compuate final LOF score
        lof /= minPnts * lrd_x;
        
        //lof, > 1 indicates outlier, <= 1 indicates inlier. 
        //to map to interface (negative = outlier), -1*(lof-1)
        //use -1.25 b/c the boarder around 1 is kinda noisy
        return -(lof-1.25);
    }
    
}

 

Ads help maintain this website.