package jsat.classifiers.neuralnetwork;

import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.*;

import jsat.classifiers.*;
import jsat.clustering.SeedSelectionMethods;
import jsat.clustering.SeedSelectionMethods.SeedSelection;
import jsat.linear.Vec;
import jsat.linear.VecPaired;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.TrainableDistanceMetric;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.math.decayrates.*;
import jsat.parameters.*;
import jsat.utils.random.RandomUtil;

/**
 * Learning Vector Quantization (LVQ) is an algorithm that extends {@link SOM} 
 * to take advantage of label information to perform classification. It creates 
 * a number of representatives, or learning vectors, for each class. The LVs are
 * then updated iteratively to push away from the wrong class and pull closer to
 * the correct class. LVQ is equivalent to a type of 2 layer neural network. 
 * 
 * @author Edward Raff
 */
public class LVQ implements Classifier, Parameterized
{

	private static final long serialVersionUID = -3911765006048793222L;
	/**
     * The default number of iterations is {@value #DEFAULT_ITERATIONS}
     */
    public static final int DEFAULT_ITERATIONS = 200;
    /**
     * The default learning rate {@value #DEFAULT_LEARNING_RATE}
     */
    public static final double DEFAULT_LEARNING_RATE = 0.1;
    /**
     * The default eps distance factor between the two wining vectors 
     * {@value #DEFAULT_EPS}
     */
    public static final double DEFAULT_EPS = 0.3;
    /**
     * The default scaling factor for the {@link LVQVersion#LVQ3} case is 
     * {@value #DEFAULT_MSCALE}
     */
    public static final double DEFAULT_MSCALE = (0.5-0.1)/2+0.1;
    /**
     * The default method of LVQ to use LVQ3
     */
    public static final LVQVersion DEFAULT_LVQ_METHOD = LVQVersion.LVQ3; 
    /**
     * The default number of representatives per class is 
     * {@value #DEFAULT_REPS_PER_CLASS}
     */
    public static final int DEFAULT_REPS_PER_CLASS = 3;
    /**
     * The default stopping distance for convergence is 
     * {@value #DEFAULT_STOPPING_DIST}
     */
    public static final double DEFAULT_STOPPING_DIST = 1e-3;

    /**
     * The default seed selection method is SeedSelection.KPP
     */
    public static final SeedSelection DEFAULT_SEED_SELECTION= SeedSelection.KPP;
    
    private DecayRate learningDecay;
    private int iterations;
    private double learningRate;
    /**
     * The distance metric to use
     */
    protected DistanceMetric dm;
    private LVQVersion lvqVersion;
    private double eps;
    private double mScale;
    private double stoppingDist;
    private int representativesPerClass;
    /**
     * Array containing the learning vectors
     */
    protected Vec[] weights;
    /**
     * Array of the class that each learning vector represents
     */
    protected int[] weightClass;
    /**
     * Records the number of times each neuron won and was off the correct class
     * during training. Neurons that end with a count of zero wins will be ignored
     */
    protected int[] wins;
    private SeedSelectionMethods.SeedSelection seedSelection;
    /**
     * Contains the Learning vectors paired with their index in the weights array
     */
    protected VectorCollection> vc;

    /**
     * Creates a new LVQ instance 
     * @param dm the distance metric to use
     * @param iterations the number of iterations to perform
     */
    public LVQ(DistanceMetric dm, int iterations)
    {
        this(dm, iterations, DEFAULT_LEARNING_RATE, DEFAULT_REPS_PER_CLASS);
    }

    /**
     * Creates a new LVQ instance
     * @param dm the distance metric to use
     * @param iterations the number of iterations to perform
     * @param learningRate the learning rate to use when updating
     * @param representativesPerClass the number of representatives to create 
     * for each class
     */
    public LVQ(DistanceMetric dm, int iterations, double learningRate, 
            int representativesPerClass)
    {
        this(dm, iterations, learningRate, representativesPerClass, DEFAULT_LVQ_METHOD, new ExponetialDecay());
    }
    
    /**
     * Creates a new LVQ instance
     * @param dm the distance metric to use
     * @param iterations the number of iterations to perform
     * @param learningRate the learning rate to use when updating
     * @param representativesPerClass the number of representatives to create 
     * for each class
     * @param lvqVersion the version of LVQ to use
     * @param learningDecay the amount of decay to apply to the learning rate
     */
    public LVQ(DistanceMetric dm, int iterations, double learningRate, 
            int representativesPerClass, LVQVersion lvqVersion, 
            DecayRate learningDecay)
    {
        setLearningDecay(learningDecay);
        setIterations(iterations);
        setLearningRate(learningRate);
        setDistanceMetric(dm);
        setLVQMethod(lvqVersion);
        setEpsilonDistance(DEFAULT_EPS);
        setMScale(DEFAULT_MSCALE);
        setSeedSelection(DEFAULT_SEED_SELECTION);
        setVecCollection(new DefaultVectorCollection<>());
        setRepresentativesPerClass(representativesPerClass);
    }
    
    /**
     * Copy Constructor
     * @param toCopy version to copy
     */
    protected LVQ(LVQ toCopy)
    {
        this(toCopy.dm.clone(), toCopy.iterations, toCopy.learningRate, 
                toCopy.representativesPerClass, toCopy.lvqVersion, 
                toCopy.learningDecay);
        if(toCopy.weights != null)
        {
            wins = Arrays.copyOf(toCopy.wins, toCopy.wins.length);
            weights = new Vec[toCopy.weights.length];
            weightClass = Arrays.copyOf(toCopy.weightClass, toCopy.weightClass.length);

            for(int i = 0; i < toCopy.weights.length; i++)
                this.weights[i] = toCopy.weights[i].clone();
        }
        setEpsilonDistance(toCopy.eps);
        setMScale(toCopy.getMScale());
        setSeedSelection(toCopy.getSeedSelection());
        if(toCopy.vc != null)
            this.vc = toCopy.vc.clone();
        setVecCollection(toCopy.vc.clone());
        
    }

    /**
     * When using {@link LVQVersion#LVQ3}, a 3rd case exists where up to two 
     * learning vectors can be updated at the same time if they have the same 
     * class. To avoid over fitting, an additional regularizing weight is placed
     * upon the learning rate for their update. THis sets the additional 
     * multiplied. It is suggested to use a value in the range of [0.1, 0.5]
     * 
     * @param mScale the multiplication factor to apply to the learning vectors
     */
    public void setMScale(double mScale)
    {
        if(mScale <= 0 || Double.isInfinite(mScale) || Double.isNaN(mScale))
            throw new ArithmeticException("Scale factor must be a positive constant, not " + mScale);
        this.mScale = mScale;
    }

    /**
     * Returns the scale used for the LVQ 3 learning algorithm update set.
     * @return a scale used during LVQ3
     */
    public double getMScale()
    {
        return mScale;
    }

    /**
     * Sets the epsilon multiplier that controls the maximum distance two 
     * learning vectors can be from each other in order to be updated at the 
     * same time. If they are too far apart, only one can be updated. It is 
     * recommended to use a value in the range [0.1, 0.3]
     * 
     * @param eps the scale factor of the maximum distance for two learning 
     * vectors to be updated at the same time
     */
    public void setEpsilonDistance(double eps)
    {
        if(eps <= 0 || Double.isInfinite(eps) || Double.isNaN(eps))
            throw new ArithmeticException("eps factor must be a positive constant, not " + eps);
        this.eps = eps;
    }

    /**
     * Sets the epsilon scale distance between learning vectors that may be 
     * allowed to two at a time. 
     * 
     * @return the scale of the allowable distance between learning vectors when
     * updating
     */
    public double getEpsilonDistance()
    {
        return eps;
    }

    /**
     * Sets the learning rate of the algorithm. It should be set in accordance 
     * with {@link #setLearningDecay(jsat.math.decayrates.DecayRate) }. 
     * 
     * @param learningRate the learning rate to use
     */
    public void setLearningRate(double learningRate)
    {
        if(learningRate <= 0 || Double.isInfinite(learningRate) || Double.isNaN(learningRate))
            throw new ArithmeticException("learning rate must be a positive constant, not " + learningRate);
        this.learningRate = learningRate;
    }

    /**
     * Returns the learning rate at which to apply updates during the algorithm.
     * 
     * @return the learning rate to use
     */
    public double getLearningRate()
    {
        return learningRate;
    }

    /**
     * Sets the decay rate to apply to the learning rate. 
     * 
     * @param learningDecay the rate to decay the learning rate 
     */
    public void setLearningDecay(DecayRate learningDecay)
    {
        this.learningDecay = learningDecay;
    }

    /**
     * Returns the method used to decay the learning rate over each iteration
     * @return the decay rate used at each iteration
     */
    public DecayRate getLearningDecay()
    {
        return learningDecay;
    }

    /**
     * Sets the number of learning iterations that will occur. 
     * 
     * @param iterations the number of iterations for the algorithm to use
     */
    public void setIterations(int iterations)
    {
        if(iterations < 0)
            throw new ArithmeticException("Can not perform a negative number of iterations");
        this.iterations = iterations;
    }

    /**
     * Returns the number of iterations of the algorithm to apply
     * @return the number of iterations to perform
     */
    public int getIterations()
    {
        return iterations;
    }
    
    /**
     * Sets the number of representatives to create for each class. It is 
     * possible to have an unbalanced number of representatives per class, but 
     * that is not currently supported. Increasing the number of representatives
     * per class increases the complexity of the decision boundary that can be 
     * learned. 
     * 
     * @param representativesPerClass the number of representatives to create 
     * for each class
     */
    public void setRepresentativesPerClass(int representativesPerClass)
    {
        this.representativesPerClass = representativesPerClass;
    }

    /**
     * Returns the number of representatives to create for each class. 
     * @return the number of representatives to create for each class. 
     */
    public int getRepresentativesPerClass()
    {
        return representativesPerClass;
    }

    /**
     * Sets the version of LVQ used. 
     * 
     * @param lvqMethod the version of LVQ to use
     */
    public void setLVQMethod(LVQVersion lvqMethod)
    {
        this.lvqVersion = lvqMethod;
    }

    /**
     * Returns the version of the LVQ algorithm to use.
     * @return the version of the LVQ algorithm to use.
     */
    public LVQVersion getLVQMethod()
    {
        return lvqVersion;
    }

    /**
     * Sets the distance used for learning
     * @param dm the distance metric to use
     */
    public void setDistanceMetric(DistanceMetric dm)
    {
        this.dm = dm;
    }

    /**
     * Returns the distance metric to use 
     * @return the distance metric to use
     */
    public DistanceMetric getDistanceMetric()
    {
        return dm;
    }

    /**
     * The algorithm terminates early if the learning vectors are only moving 
     * small distances. The stopping distance is the minimum distance that one 
     * of the learning vectors must move for the algorithm to continue.
     * 
     * @param stoppingDist the minimum distance for each learning vector to move
     */
    public void setStoppingDist(double stoppingDist)
    {
        if(stoppingDist < 0 || Double.isInfinite(stoppingDist) || Double.isNaN(stoppingDist))
            throw new ArithmeticException("stopping dist must be a zero or positive constant, not " + stoppingDist);
        this.stoppingDist = stoppingDist;
    }

    /**
     * Returns the stopping distance used to terminate the algorithm early
     * @return the stopping distance used toe nd the algorithm early
     */
    public double getStoppingDist()
    {
        return stoppingDist;
    }

    /**
     * Sets the seed selection method used to select the initial learning vectors 
     * @param seedSelection the method of initialing LVQ
     */
    public void setSeedSelection(SeedSelection seedSelection)
    {
        this.seedSelection = seedSelection;
    }

    /**
     * Returns the method of seed selection used 
     * @return the method of seed selection used 
     */
    public SeedSelection getSeedSelection()
    {
        return seedSelection;
    }
    
    /**
     * There are several LVQ versions, each one adding an additional case in 
     * which two LVs instead of one can be updated. 
     */
    public enum LVQVersion 
    {
        /**
         * LVQ1 will only update one LV
         */
        LVQ1, 
        /**
         * Two vectors will be updated if they are close enough together. The 
         * closest was the wrong class but the 2nd closet was the correct class. 
         */
        LVQ2, 
        /**
         * Two vectors will be updated if they are close enough together and do 
         * not belong to the same class if one of them was the correct class to 
         * a training vector. 
         */
        LVQ21, 
        /**
         * Two vectors will be updated if they are close enough together and are
         * of the same class as the training vector.
         */
        LVQ3
    }

    /**
     * Sets the vector collection factory to use when storing the final learning vectors
     * @param vcf the vector collection factory to use
     */
    public void setVecCollection(VectorCollection> vcf)
    {
        this.vc = vcf;
    }
    
    @Override
    public CategoricalResults classify(DataPoint data)
    {
        CategoricalResults cr = new CategoricalResults(weightClass.length/representativesPerClass);
        
        
        int index = vc.search(data.getNumericalValues(), 1).get(0).getVector().getPair();
        cr.setProb(weightClass[index], 1.0);
        
        return cr;
    }

    /**
     * Returns true if the two distance values are within an acceptable epsilon 
     * ratio of each other. 
     * @param minDist the first distance
     * @param minDist2 the second distance
     * @return true if the are acceptable close
     */
    protected boolean epsClose(double minDist, double minDist2)
    {
        return min(minDist/minDist2, minDist2/minDist) > (1 - eps)
                        && max(minDist/minDist2, minDist2/minDist) < (1 + eps);
    }
    
    @Override
    public void train(ClassificationDataSet dataSet, boolean parallel)
    {
        TrainableDistanceMetric.trainIfNeeded(dm, dataSet, parallel);
        Random rand = RandomUtil.getRandom();
        int classCount = dataSet.getPredicting().getNumOfCategories();
        weights = new Vec[classCount*representativesPerClass];
        Vec[] weightsPrev = new Vec[weights.length];
        weightClass = new int[weights.length];
        wins = new int[weights.length];

        //Generate weights that are hopefully close to their final positions
        
        int curClass = 0;
        int curPos = 0;
        while(curClass < classCount)
        {
            List origSubList = dataSet.getSamples(curClass);
            List> subList =
                    new ArrayList<>(origSubList.size());
            for(DataPoint dp : origSubList)
                subList.add(new DataPointPair<>(dp, curClass));
            ClassificationDataSet subSet = 
                    new ClassificationDataSet(subList, dataSet.getPredicting());
            List classSeeds = 
                    SeedSelectionMethods.selectIntialPoints(subSet, 
                    representativesPerClass, dm, rand, seedSelection);
            for(Vec v : classSeeds)
            {
                weights[curPos] = v.clone();
                weightsPrev[curPos] = weights[curPos].clone();
                weightClass[curPos++] = curClass;
            }
            curClass++;
        }
        Vec tmp = weights[0].clone();

        for(int iteration = 0; iteration < iterations; iteration++)
        {
            for(int j = 0; j < weights.length; j++)
                weights[j].copyTo(weightsPrev[j]);
            Arrays.fill(wins, 0);
            double alpha = learningDecay.rate(iteration, iterations, learningRate);
            for(int i = 0; i < dataSet.getSampleSize(); i++)
            {
                Vec x = dataSet.getDataPoint(i).getNumericalValues();
                int closestClass = -1;
                int minDistIndx = 0, minDistIndx2 = 0;
                double minDist = Double.POSITIVE_INFINITY, minDist2 = Double.POSITIVE_INFINITY;
                
                for(int j = 0; j < weights.length; j++)
                {
                    double dist = dm.dist(x, weights[j]);
                    if(dist < minDist)
                    {
                        if(lvqVersion == LVQVersion.LVQ2)
                        {
                            minDist2 = minDist;
                            minDistIndx2 = minDistIndx;
                        }
                        minDist = dist;
                        minDistIndx = j;
                        closestClass = dataSet.getDataPointCategory(i);
                        
                    }
                }

                if (lvqVersion.ordinal() >= LVQVersion.LVQ2.ordinal()
                        && weightClass[minDistIndx] != weightClass[minDistIndx2]
                        && closestClass == weightClass[minDistIndx2]
                        && epsClose(minDist, minDist2))
                {//Update both vectors 
                    //Move the closest farther away
                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx]);
                    weights[minDistIndx].mutableSubtract(alpha, tmp);
                    //And the 2nd closest closer
                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx2]);
                    weights[minDistIndx2].mutableAdd(alpha, tmp);
                    wins[minDistIndx2]++;
                }
                else if (lvqVersion.ordinal() >= LVQVersion.LVQ21.ordinal()
                        && weightClass[minDistIndx] != weightClass[minDistIndx2]
                        && closestClass == weightClass[minDistIndx]
                        && epsClose(minDist, minDist2))
                {//Update both vectors 
                    //Move the closest closer
                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx]);
                    weights[minDistIndx].mutableAdd(alpha, tmp);
                    wins[minDistIndx]++;
                    //And the 2nd closest farther away
                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx2]);
                    weights[minDistIndx2].mutableSubtract(alpha, tmp);
                }
                else if (lvqVersion.ordinal() >= LVQVersion.LVQ3.ordinal()
                        && weightClass[minDistIndx] == weightClass[minDistIndx2]
                        && min(minDist/minDist2, minDist2/minDist) > (1-eps)*(1+eps))
                {//Update both vectors in the same direction
                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx]);
                    weights[minDistIndx].mutableAdd(mScale*alpha, tmp);

                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx2]);
                    weights[minDistIndx2].mutableAdd(mScale*alpha, tmp);
                    wins[minDistIndx]++;
                    wins[minDistIndx2]++;
                }
                else //Base case, can only update one vector
                {
                    x.copyTo(tmp);
                    tmp.mutableSubtract(weights[minDistIndx]);
                    if(closestClass == weightClass[minDistIndx])//Move closer to the right class
                    {
                        wins[minDistIndx]++;
                        weights[minDistIndx].mutableAdd(alpha, tmp);
                    }
                    else//Move farther away
                    {
                        weights[minDistIndx].mutableSubtract(alpha, tmp);
                    }
                }
                
            }
            //Check for early convergence
            boolean stopEarly = true;
            for(int j = 0; j < weights.length; j++)
                if(stopEarly && dm.dist(weights[j], weightsPrev[j]) > stoppingDist)
                    stopEarly = false;
            if(stopEarly)
                break;
        }
        
        List> finalLVs = new ArrayList>(weights.length);
        for(int i = 0; i < weights.length; i++)
            if(wins[i] == 0)
                continue;
            else
                finalLVs.add(new VecPaired(weights[i], i));
        vc.build(parallel, finalLVs, dm);
    }
    
    @Override
    public boolean supportsWeightedData()
    {
        return false;
    }

    @Override
    public LVQ clone()
    {   
    	return new LVQ(this);
    }
    
}

 

Ads help maintain this website.