/*
 * Copyright (C) 2018 edraff
 *
 * 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.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.linear.IndexValue;
import jsat.linear.Vec;
import jsat.math.FastMath;
import jsat.math.SpecialMath;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 *
 * @author edraff
 */
public class IsolationForest implements Outlier
{
    private int trees = 100;
    private double subSamplingSize = 256;
    
    List roots = new ArrayList<>();

    public IsolationForest()
    {
    }
    
    public IsolationForest(IsolationForest toCopy)
    {
        this.trees = toCopy.trees;
        this.subSamplingSize = toCopy.subSamplingSize;
        this.roots = new ArrayList<>();
        for(iTreeNode root : toCopy.roots)
            this.roots.add(root.clone());
    }
    
    /**
     * Equation 1 in the Isolation Forest paper
     * @param n
     * @return 
     */
    private static double c(double n)
    {
        return 2*SpecialMath.harmonic(n-1)-(2*(n-1)/n);
    }

    @Override
    public void fit(DataSet d, boolean parallel)
    {
        for(int i =0; i < trees; i++)
            roots.add(new iTreeNode());
        
        int l = (int) Math.ceil(Math.log(subSamplingSize)/Math.log(2));
        int D = d.getNumNumericalVars();
        //Build all the trees
        ParallelUtils.streamP(roots.stream(), parallel).forEach(r->
        {
            r.build(0, l, d.getDataPoints(), new double[D], new double[D]);
        });
    }

    @Override
    public double score(DataPoint x)
    {
        double e_h_x = roots.stream().
                mapToDouble(r->r.pathLength(x.getNumericalValues(), 0))
                .average().getAsDouble();
        //an anomaly score is produced by computing s(x,ψ) in Equation 2
        
        double anomScore = FastMath.pow2(-e_h_x/c(subSamplingSize));
        //anomScore will be in the range [0, 1]
        //values > 0.5 are considered anomolies
        //so just return 0.5-anomScore to fit the interface defintion
        return 0.5-anomScore;
    }

    @Override
    protected IsolationForest clone() throws CloneNotSupportedException
    {
        return new IsolationForest(this);
    }
    
    private class iTreeNode implements Serializable
    {
        
        iTreeNode leftChild;
        iTreeNode rightChild;
        double size = 0;
        double splitVal;
        int splitAtt;
        

        public iTreeNode()
        {
        }

        public iTreeNode(iTreeNode toCopy)
        {
            this.leftChild = new iTreeNode(toCopy.leftChild);
            this.rightChild = new iTreeNode(toCopy.rightChild);
            this.splitVal = toCopy.splitVal;
            this.splitAtt = toCopy.splitAtt;
        }

        @Override
        protected iTreeNode clone() 
        {
            return new iTreeNode(this);
        }
        
        public void build(int e, int l, List X, double[] minVals, double[] maxVals)
        {
            if(e >= l || X.size() <= 1)
            {
                if(X.isEmpty())//super rare, rng guesses the min value itself
                    this.size = 1;
                else//use average
                    this.size = X.stream().mapToDouble(s->s.getWeight()).sum();
                    
                //else, size stays zero
                return;
            }
            //else
            
            
            int D =X.get(0).getNumericalValues().length();
            Arrays.fill(minVals, 0.0);
            Arrays.fill(maxVals, 0.0);
                        
            //find the min-max range for each feature
            X.stream().forEach(d->
            {
                for(IndexValue iv : d.getNumericalValues())
                {
                    int i = iv.getIndex();
                    minVals[i] = Math.min(minVals[i], iv.getValue());
                    maxVals[i] = Math.max(maxVals[i], iv.getValue());
                }
            });
            
            //how many features are valid choices?
            int candiadates = 0;
            for(int i = 0; i < D; i++)
                if(minVals[i] != maxVals[i])
                    candiadates++;
            //select the q'th feature with a non-zero spread
            int q_candidate = RandomUtil.getLocalRandom().nextInt(candiadates);
            int q = 0;
            for(int i = 0; i  X_l = new ArrayList<>();
            List X_r = new ArrayList<>();
            for(DataPoint x : X)
                if(x.getNumericalValues().get(q) < splitVal)
                    X_l.add(x);
                else
                    X_r.add(x);
            splitAtt = q;
            
            this.leftChild = new iTreeNode();
            this.leftChild.build(e+1, l, X_l, minVals, maxVals);
            this.rightChild = new iTreeNode();
            this.rightChild.build(e+1, l, X_r, minVals, maxVals);
        }
        
        
        public double pathLength(Vec x, double e)
        {
            if(leftChild == null)//root node
                return e + c(this.size);
            //else
            if(x.get(splitAtt) < splitVal)
                return leftChild.pathLength(x, e+1);
            else
                return rightChild.pathLength(x, e+1);
        }
    }
}

 

Ads help maintain this website.