package jsat.linear.vectorcollection;

import java.util.List;
import java.util.Random;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.math.OnLineStatistics;
import jsat.utils.Pair;

/**
 * The VPTreeMV is an extension of the VPTree, the MV meaning "of Minimum Variance". This extension 
 * alters the splitting method of nodes, giving up the O(log n) bound on query time. This is done 
 * to reduce the variance in the distance to the parent node of each split, which can result in 
 * lopsided distributions of values for each split. At the same time, this lopsidedness may better 
 * reflect the locality of points in the data set. This can result in a decrease in query time 
 * for some data sets, with minimal impact on construction time. 
 * 
 * @author Edward Raff
 */
public class VPTreeMV extends VPTree
{

    private static final long serialVersionUID = 6668184445206226077L;

    public VPTreeMV(List list, DistanceMetric dm, VPSelection vpSelection, Random rand, int sampleSize, int searchIterations, boolean parallel)
    {
        super(list, dm, vpSelection, rand, sampleSize, searchIterations, parallel);
    }

    public VPTreeMV(List list, DistanceMetric dm, VPSelection vpSelection, Random rand, int sampleSize, int searchIterations)
    {
        super(list, dm, vpSelection, rand, sampleSize, searchIterations);
    }

    public VPTreeMV(List list, DistanceMetric dm, VPSelection vpSelection)
    {
        super(list, dm, vpSelection);
    }

    public VPTreeMV(List list, DistanceMetric dm)
    {
        super(list, dm);
    }

    public VPTreeMV(List list, DistanceMetric dm, boolean parallel)
    {
        super(list, dm, parallel);
    }

    public VPTreeMV(DistanceMetric dm)
    {
        super(dm);
    }
    
    public VPTreeMV(DistanceMetric dm, VPSelection sampling)
    {
        super(dm, sampling);
    }

    public VPTreeMV()
    {
        super();
    }
    
    public VPTreeMV(VPTreeMV toClone)
    {
        super(toClone);
    }

    @Override
    protected int splitListIndex(List> S)
    {
        int splitIndex = S.size()/2;
        int maxLeafSize = getMaxLeafSize();
        
        if(S.size() >= maxLeafSize*4)
        {
            //Adjust to avoid degenerate cases that create a long string of tiny splits. Most imbalacned slpit can be 1:20
            int minSplitSize = Math.max(maxLeafSize, S.size()/20);
            
            OnLineStatistics rightV = new OnLineStatistics();
            OnLineStatistics leftV = new OnLineStatistics();
            for(int i = 0; i < minSplitSize; i++)
                leftV.add(S.get(i).getFirstItem());
            for(int i = minSplitSize; i < S.size(); i++)
                rightV.add(S.get(i).getFirstItem());
            splitIndex = minSplitSize;
            double bestVar = leftV.getVarance()*minSplitSize+rightV.getVarance()*(S.size()-minSplitSize);
            for(int i = minSplitSize+1; i < S.size()-minSplitSize; i++)
            {
                double tmp = S.get(i).getFirstItem();
                leftV.add(tmp);
                rightV.remove(tmp, 1.0);
                double testVar = leftV.getVarance()*i + rightV.getVarance()*(S.size()-i);
                if(testVar < bestVar)
                {
                    splitIndex = i;
                    bestVar = testVar;
                }
            }
        }
        
        return splitIndex;
    }

    @Override
    public VPTreeMV clone()
    {
        return new VPTreeMV<>(this);
    }
}

 

Ads help maintain this website.