/*
* 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.math.SpecialMath;
import jsat.utils.DoubleList;
import jsat.utils.IntList;
import jsat.utils.concurrent.ParallelUtils;
/**
* This class implements the Local Outlier Probabilities (LoOP) algorithm for outlier detection.
* @author Edward Raff
*/
public class LoOP implements Outlier
{
int minPnts;
private double lambda = 3;
private DistanceMetric distanceMetric;
VectorCollection vc = new DefaultVectorCollection<>();
/**
* Stores the "standard distance" of an index in X to its nearest neighbors
*/
private double[] standard_distance;
private double nPLOF;
public LoOP()
{
this(20);
}
public LoOP(int minPnts)
{
this(minPnts, new EuclideanDistance());
}
public LoOP(int minPnts, DistanceMetric dm)
{
setMinPnts(minPnts);
setDistanceMetric(dm);
}
public void setMinPnts(int minPnts)
{
this.minPnts = minPnts;
}
public int getMinPnts()
{
return minPnts;
}
public void setLambda(double lambda)
{
this.lambda = lambda;
}
public double getLambda()
{
return lambda;
}
public void setDistanceMetric(DistanceMetric distanceMetric)
{
this.distanceMetric = distanceMetric;
}
public DistanceMetric getDistanceMetric()
{
return distanceMetric;
}
@Override
public void fit(DataSet d, boolean parallel)
{
List X = d.getDataVectors();
vc.build(parallel, X, distanceMetric);
int N = X.size();
standard_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++)
standard_distance[i] = Math.sqrt(all_knn_dists.get(i).stream()
.mapToDouble(z->z*z).sum()/minPnts+1e-6);
});
double[] plof_internal = new double[N];
nPLOF = ParallelUtils.run(parallel, N, (start, end)->
{
double sqrdPLOF = 0;
for(int i = start; i < end; i++)
{
double neighborSD = 0;
for(int j_indx = 1; j_indx < minPnts+1; j_indx++)
{
int neighbor = all_knn.get(i).get(j_indx);
neighborSD += standard_distance[neighbor];
}
plof_internal[i] = standard_distance[i]/(neighborSD/minPnts) - 1;
sqrdPLOF += plof_internal[i]*plof_internal[i];
}
return sqrdPLOF;
}, (a,b)->a+b);
nPLOF = Math.sqrt(nPLOF/N);
}
@Override
public double score(DataPoint x)
{
IntList knn = new IntList(minPnts);
DoubleList dists = new DoubleList(minPnts);
vc.search(x.getNumericalValues(), minPnts, knn, dists);
double e_pdist = 0;
double stndDist_q = 0;
for(int i_indx = 0; i_indx < minPnts; i_indx++)
{
int neighbor = knn.get(i_indx);
double dist = dists.get(i_indx);
e_pdist += standard_distance[neighbor];
stndDist_q += dist*dist;
}
//lrd_x now has the local reachability distance of the query x
stndDist_q = Math.sqrt(stndDist_q/minPnts+1e-6);
//normalize pdist of neighbors
e_pdist /= minPnts;
double plof_os = stndDist_q/e_pdist - 1;
double loop = Math.max(0, SpecialMath.erf(plof_os/(lambda * nPLOF * Math.sqrt(2))));
//loop, > 1/2 indicates outlier, <= 1/2 indicates inlier.
//to map to interface (negative = outlier), -1*(loop-1/2)
return -(loop-0.5);
}
}
Ads help maintain this website.