package jsat.classifiers.knn;

import java.util.*;
import jsat.DataSet;
import jsat.classifiers.*;
import jsat.distributions.Distribution;
import jsat.distributions.discrete.UniformDiscrete;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.UntrainedModelException;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.*;
import jsat.linear.vectorcollection.*;
import jsat.math.MathTricks;
import jsat.parameters.*;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;

/**
 * An implementation of the Nearest Neighbor algorithm, but with a 
 * British spelling! How fancy. 
 * @author Edward Raff
 */
public class NearestNeighbour implements  Classifier, Regressor, Parameterized
{

    private static final long serialVersionUID = 4239569189624285932L;
    private int k;
    private boolean weighted;
    private DistanceMetric distanceMetric;
    private CategoricalData predicting;
    
    private VectorCollection> vecCollection;

    /**
     * Returns the number of neighbors currently consulted to make decisions
     * @return the number of neighbors
     */
    public int getNeighbors()
    {
        return k;
    }

    /**
     * Sets the number of neighbors to consult when making decisions
     * @param k the number of neighbors to use
     */
    public void setNeighbors(int k)
    {
        if(k < 1)
            throw new ArithmeticException("Must be a positive number of neighbors");
        this.k = k;
    }
    
    public int getNeighbors(int k)
    {
        return k;
    }

    public DistanceMetric getDistanceMetric()
    {
        return distanceMetric;
    }

    public void setDistanceMetric(DistanceMetric distanceMetric)
    {
        if(distanceMetric == null)
            throw new NullPointerException("given metric was null");
        this.distanceMetric = distanceMetric;
    }

    private enum Mode {REGRESSION, CLASSIFICATION};
    /**
     * If we are in classification mode, the double is an integer that indicates class.
     */
    Mode mode;
    
    /**
     * Constructs a new Nearest Neighbor Classifier
     * @param k the number of neighbors to use
     */
    public NearestNeighbour(int k)
    {
        this(k, false);
    }
    
    /**
     * Constructs a new Nearest Neighbor Classifier
     * @param k the number of neighbors to use
     * @param vcf the vector collection factory to use for storing and querying 
     */
    public NearestNeighbour(int k, VectorCollection> vcf)
    {
        this(k, false, new EuclideanDistance(), vcf);
    }

    /**
     * Constructs a new Nearest Neighbor Classifier
     * @param k the number of neighbors to use
     * @param weighted whether or not to weight the influence of neighbors by their distance
     */
    public NearestNeighbour(int k, boolean weighted)
    {
        this(k, weighted, new EuclideanDistance());
    }
    
    /**
     * Constructs a new Nearest Neighbor Classifier
     * @param k the number of neighbors to use
     * @param weighted whether or not to weight the influence of neighbors by their distance
     * @param distanceMetric the method of computing distance between two vectors. 
     */
    public NearestNeighbour(int k, boolean weighted, DistanceMetric distanceMetric )
    {
        this(k, weighted, distanceMetric, new DefaultVectorCollection>());
    }
    
    /**
     * Constructs a new Nearest Neighbor Classifier
     * @param k the number of neighbors to use
     * @param weighted whether or not to weight the influence of neighbors by their distance
     * @param distanceMetric the method of computing distance between two vectors. 
     * @param vcf the vector collection factory to use for storing and querying 
     */
    public NearestNeighbour(int k, boolean weighted, DistanceMetric distanceMetric, VectorCollection> vcf )
    {
        this.mode = null;
        this.vecCollection = vcf;
        this.k = k;
        this.weighted = weighted;
        this.distanceMetric = distanceMetric;
    }

    @Override
    public CategoricalResults classify(DataPoint data)
    {
        if(vecCollection == null || mode != Mode.CLASSIFICATION)
            throw new UntrainedModelException("Classifier has not been trained for classification");
        Vec query  = data.getNumericalValues();
        
        List, Double>> knns = vecCollection.search(query, k);
        
        if(weighted)
        {
            double[] dists = new double[knns.size()];
            for(int i = 0; i < knns.size(); i++)
                dists[i] = knns.get(i).getPair();
            //we want something like 1/dist to make closer values weighted higher
            double offset = MathTricks.min(dists)*0.1+1e-15;
            for(int i = 0; i < knns.size(); i++)
                dists[i] = 1/(offset+dists[i]);
            
            MathTricks.softmax(dists, false);
            
            CategoricalResults results = new CategoricalResults(predicting.getNumOfCategories());
            for(int i = 0; i < knns.size(); i++)
            {
                VecPaired pm = knns.get(i).getVector();
                int index =  (int) Math.round(pm.getPair());

                results.setProb(index, results.getProb(index) + dists[i]);//all weights are 1
            }
            
            return results;
        }
        else
        {
            CategoricalResults results = new CategoricalResults(predicting.getNumOfCategories());
        
            for(int i = 0; i < knns.size(); i++)
            {
                VecPaired pm = knns.get(i).getVector();
                int index =  (int) Math.round(pm.getPair());

                results.setProb(index, results.getProb(index) + 1.0);//all weights are 1
            }

            results.normalize();

            return results;
        }
    }

    @Override
    public void train(ClassificationDataSet dataSet, boolean parallel)
    {
        if(dataSet.getNumCategoricalVars() != 0)
            throw new FailedToFitException("KNN requires vector data only");
        
        mode = Mode.CLASSIFICATION;
        this.predicting = dataSet.getPredicting();
        List> dataPoints = new ArrayList>(dataSet.getSampleSize());
                
        //Add all the data points
        for(int i = 0; i < dataSet.getClassSize(); i++)
        {
            for(DataPoint dp : dataSet.getSamples(i))
            {
                //We want to include the category in this case, so we will add it to the vector
                dataPoints.add(new VecPaired(dp.getNumericalValues(), (double)i));//bug? why isnt this auto boxed to double w/o a cast?
            }
        }
        
        TrainableDistanceMetric.trainIfNeeded(distanceMetric, dataSet, parallel);
        
        vecCollection.build(parallel, dataPoints, distanceMetric);
    }
    
    @Override
    public double regress(DataPoint data)
    {
        if(vecCollection == null || mode != Mode.REGRESSION)
            throw new UntrainedModelException("Classifier has not been trained for regression");
        Vec query  = data.getNumericalValues();
        
        List, Double>> knns = vecCollection.search(query, k);
        
        double result = 0, weightSum = 0;
        
        for(int i = 0; i < knns.size(); i++)
        {
            double distance = knns.get(i).getPair();
            VecPaired pm = knns.get(i).getVector();
            
            double value = pm.getPair();
            
            
            if(weighted)
            {
                distance = Math.max(1e-8, distance);//Avoiding zero distances which will result in Infinty getting propigated around
                double weight = 1.0/Math.pow(distance, 2);
                weightSum += weight;
                result += value*weight;
            }
            else
            {
                result += value;
                weightSum += 1;
            }
        }
        
        return result/weightSum;
    }

    @Override
    public void train(RegressionDataSet dataSet, boolean parallel)
    {
        if(dataSet.getNumCategoricalVars() != 0)
            throw new FailedToFitException("KNN requires vector data only");
        
        mode = Mode.REGRESSION;

        List> dataPoints = new ArrayList>(dataSet.getSampleSize());
                
        //Add all the data points
        for (int i = 0; i < dataSet.getSampleSize(); i++)
        {
            DataPointPair dpp = dataSet.getDataPointPair(i);

            dataPoints.add(new VecPaired(dpp.getVector(), dpp.getPair()));
        }
        
        TrainableDistanceMetric.trainIfNeeded(distanceMetric, dataSet, parallel);

        vecCollection.build(parallel, dataPoints, distanceMetric);
    }
    
    @Override
    public NearestNeighbour clone()
    {
        NearestNeighbour clone = new NearestNeighbour(k, weighted, distanceMetric.clone(), vecCollection.clone());
        
        if(this.predicting != null)
            clone.predicting = this.predicting.clone();
        clone.mode = this.mode;
        
        if(this.vecCollection != null)
            clone.vecCollection = this.vecCollection.clone();
        
        return clone;
    }
    
    /**
     * Guesses the distribution to use for the number of neighbors to consider
     * @param d the dataset to get the guess for
     * @return the guess for the Neighbors parameter
     */
    public static Distribution guessNeighbors(DataSet d)
    {
        return new UniformDiscrete(1, 25);
    }
    
    @Override
    public boolean supportsWeightedData()
    {
        return false;
    }
}

 

Ads help maintain this website.