package jsat.datatransform.kernel;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.datatransform.DataTransformBase;
import jsat.datatransform.PCA;
import jsat.datatransform.kernel.Nystrom.SamplingMethod;
import jsat.distributions.Distribution;
import jsat.distributions.discrete.UniformDiscrete;
import jsat.distributions.kernels.KernelTrick;
import jsat.distributions.kernels.RBFKernel;
import jsat.linear.DenseMatrix;
import jsat.linear.DenseVector;
import jsat.linear.EigenValueDecomposition;
import jsat.linear.Matrix;
import jsat.linear.RowColumnOps;
import jsat.linear.Vec;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.utils.random.RandomUtil;

/**
 * A kernelized implementation of {@link PCA}. Because this works in a different
 * feature space, it will do its own centering in the kernel space. 
 * 

* KernelPCA is expensive to compute at O(n3) work, where n is * the number of data points. For this reason, sampling from {@link Nystrom} is * used to reduce the data set to a reasonable approximation. *

* See: Schölkopf, B., Smola, A.,&Müller, K.-R. (1998). Nonlinear Component * Analysis as a Kernel Eigenvalue Problem. Neural Computation, 10(5), * 1299–1319. doi:10.1162/089976698300017467 * * @author Edward Raff * @see Nystrom.SamplingMethod */ public class KernelPCA extends DataTransformBase { private static final long serialVersionUID = 5676602024560381023L; /** * The dimension to project down to */ private int dimensions; @ParameterHolder private KernelTrick k; private int basisSize; private Nystrom.SamplingMethod samplingMethod; private double[] eigenVals; /** * The matrix of transformed eigen vectors */ private Matrix eigenVecs; /** * The vecs used for the transform */ private Vec[] vecs; //row / colum info for centering in the feature space private double[] rowAvg; private double allAvg; /** * Creates a new Kernel PCA transform object using the * {@link RBFKernel RBF Kernel} and 100 dimensions * */ public KernelPCA() { this(100); } /** * Creates a new Kernel PCA transform object using the * {@link RBFKernel RBF Kernel} * * @param dimensions the number of dimensions to project down to. Must be * less than than the basis size */ public KernelPCA(int dimensions) { this(new RBFKernel(), dimensions); } /** * Creates a new Kernel PCA transform object * * @param k the kernel trick to use * @param dimensions the number of dimensions to project down to. Must be * less than than the basis size */ public KernelPCA(KernelTrick k, int dimensions) { this(k, dimensions, 1000, SamplingMethod.UNIFORM); } /** * Creates a new Kernel PCA transform object * @param k the kernel trick to use * @param dimensions the number of dimensions to project down to. Must be * less than than the basis size * @param basisSize the number of points from the data set to select. If * larger than the number of data points in the data set, the whole data set * will be used. * @param samplingMethod the sampling method to select the basis vectors */ public KernelPCA(KernelTrick k, int dimensions, int basisSize, Nystrom.SamplingMethod samplingMethod) { setDimensions(dimensions); setKernel(k); setBasisSize(basisSize); setBasisSamplingMethod(samplingMethod); } /** * Creates a new Kernel PCA transform object * @param k the kernel trick to use * @param ds the data set to form the data transform from * @param dimensions the number of dimensions to project down to. Must be * less than than the basis size * @param basisSize the number of points from the data set to select. If * larger than the number of data points in the data set, the whole data set * will be used. * @param samplingMethod the sampling method to select the basis vectors */ public KernelPCA(KernelTrick k, DataSet ds, int dimensions, int basisSize, Nystrom.SamplingMethod samplingMethod) { this(k, dimensions, basisSize, samplingMethod); fit(ds); } @Override public void fit(DataSet ds) { if(ds.getSampleSize() <= basisSize) { vecs = new Vec[ds.getSampleSize()]; for(int i = 0; i < vecs.length; i++) vecs[i] = ds.getDataPoint(i).getNumericalValues(); } else { int i = 0; List sample = Nystrom.sampleBasisVectors(k, ds, ds.getDataVectors(), samplingMethod, basisSize, false, RandomUtil.getRandom()); vecs = new Vec[sample.size()]; for(Vec v : sample) vecs[i++] = v; } Matrix K = new DenseMatrix(vecs.length, vecs.length); //Info used to compute centered Kernel matrix rowAvg = new double[K.rows()]; allAvg = 0; for(int i = 0; i < K.rows(); i++) { Vec x_i = vecs[i]; for(int j = i; j < K.cols(); j++) { double K_ij = k.eval(x_i, vecs[j]); K.set(i, j, K_ij); K.set(j, i, K_ij);//K = K' } } //Get row / col info to perform centering. Since K is symetric, the row //and col info are the same for(int i = 0; i < K.rows(); i++) for(int j = 0; j < K.cols(); j++) rowAvg[i] += K.get(i, j); for (int i = 0; i < K.rows(); i++) { allAvg += rowAvg[i]; rowAvg[i] /= K.rows(); } allAvg /= (K.rows()*K.cols()); //Centered version of the marix //K_c(i, j) = K_ij - sum_z K_zj / m - sum_z K_iz / m + sum_{z,y} K_zy / m^2 for(int i = 0; i < K.rows(); i++) for(int j = 0; j < K.cols(); j++) K.set(i, j, K.get(i, j) - rowAvg[i] - rowAvg[j] + allAvg); EigenValueDecomposition evd = new EigenValueDecomposition(K); evd.sortByEigenValue(new Comparator() { @Override public int compare(Double o1, Double o2) { return -Double.compare(o1, o2); } }); eigenVals = evd.getRealEigenvalues(); eigenVecs = evd.getV(); for(int j = 0; j < eigenVals.length; j++)//TODO row order would be more cache friendly RowColumnOps.divCol(eigenVecs, j, Math.sqrt(eigenVals[j])); } /** * Copy constructor * @param toCopy the object to copy */ protected KernelPCA(KernelPCA toCopy) { this.dimensions = toCopy.dimensions; this.k = toCopy.k.clone(); this.basisSize = toCopy.basisSize; this.samplingMethod = toCopy.samplingMethod; if(toCopy.eigenVals != null) this.eigenVals = Arrays.copyOf(toCopy.eigenVals, toCopy.eigenVals.length); if(toCopy.eigenVecs != null) this.eigenVecs = toCopy.eigenVecs.clone(); if(toCopy.vecs != null) { this.vecs = new Vec[toCopy.vecs.length]; for(int i = 0; i < vecs.length; i++) this.vecs[i] = toCopy.vecs[i].clone(); this.rowAvg = Arrays.copyOf(toCopy.rowAvg, toCopy.rowAvg.length); } this.allAvg = toCopy.allAvg; } @Override public DataPoint transform(DataPoint dp) { Vec oldVec = dp.getNumericalValues(); Vec newVec = new DenseVector(dimensions); //TODO put this in a thread local object? Or hope JVM puts a large array on the stack? final double[] kEvals = new double[vecs.length]; double tAvg = 0; for (int j = 0; j < vecs.length; j++) tAvg += (kEvals[j] = k.eval(vecs[j], oldVec)); tAvg /= vecs.length; for (int i = 0; i < dimensions; i++) { double val = 0; for (int j = 0; j < vecs.length; j++) val += eigenVecs.get(j, i) * (kEvals[j] - tAvg - rowAvg[i] + allAvg); newVec.set(i, val); } return new DataPoint(newVec, dp.getCategoricalValues(), dp.getCategoricalData(), dp.getWeight()); } @Override public KernelPCA clone() { return new KernelPCA(this); } /** * * @param k the kernel trick to use */ public void setKernel(KernelTrick k) { this.k = k; } /** * * @return the kernel trick to use */ public KernelTrick getKernel() { return k; } /** * Sets the basis size for the Kernel PCA to be learned from. Increasing the * basis increase the accuracy of the transform, but increased the training * time at a cubic rate. * * @param basisSize the number of basis vectors to build Kernel PCA from */ public void setBasisSize(int basisSize) { if (basisSize < 1) throw new IllegalArgumentException("The basis size must be positive, not " + basisSize); this.basisSize = basisSize; } /** * Returns the number of basis vectors to use * * @return the number of basis vectors to use */ public int getBasisSize() { return basisSize; } /** * Sets the dimension of the new feature space, which is the number of * principal components to select from the kernelized feature space. * * @param dimensions the number of dimensions to project down too */ public void setDimensions(int dimensions) { if (dimensions < 1) throw new IllegalArgumentException("The number of dimensions must be positive, not " + dimensions); this.dimensions = dimensions; } /** * Returns the number of dimensions to project down too * * @return the number of dimensions to project down too */ public int getDimensions() { return dimensions; } /** * Sets the method of selecting the basis vectors * * @param method the method of selecting the basis vectors */ public void setBasisSamplingMethod(SamplingMethod method) { this.samplingMethod = method; } /** * Returns the method of selecting the basis vectors * * @return the method of selecting the basis vectors */ public SamplingMethod getBasisSamplingMethod() { return samplingMethod; } public static Distribution guessDimensions(DataSet d) { return new UniformDiscrete(20, 200); } }

Ads help maintain this website.