diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/distance/distancefunction')
35 files changed, 1801 insertions, 597 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java index ea178bbb..e29d9237 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java @@ -73,8 +73,7 @@ public abstract class AbstractVectorDoubleDistanceFunction extends AbstractPrimi * @throws IllegalArgumentException when dimensionalities are not the same. */ public static final int dimensionality(SpatialComparable o1, SpatialComparable o2) { - final int dim1 = o1.getDimensionality(); - final int dim2 = o2.getDimensionality(); + final int dim1 = o1.getDimensionality(), dim2 = o2.getDimensionality(); if (dim1 != dim2) { throw new IllegalArgumentException("Objects do not have the same dimensionality."); } @@ -92,8 +91,42 @@ public abstract class AbstractVectorDoubleDistanceFunction extends AbstractPrimi * @throws IllegalArgumentException when dimensionalities are not the same. */ public static final int dimensionality(SpatialComparable o1, SpatialComparable o2, int expect) { - final int dim1 = o1.getDimensionality(); - final int dim2 = o2.getDimensionality(); + final int dim1 = o1.getDimensionality(), dim2 = o2.getDimensionality(); + if (dim1 != dim2 || dim1 != expect) { + throw new IllegalArgumentException("Objects do not have the expected dimensionality of " + expect); + } + return expect; + } + + /** + * Get the common dimensionality of the two objects. Throw an + * {@link IllegalArgumentException} otherwise. + * + * @param o1 First vector / MBR + * @param o2 Second vector / MBR + * @return Common dimensionality + * @throws IllegalArgumentException when dimensionalities are not the same. + */ + public static final int dimensionality(NumberVector<?> o1, NumberVector<?> o2) { + final int dim1 = o1.getDimensionality(), dim2 = o2.getDimensionality(); + if (dim1 != dim2) { + throw new IllegalArgumentException("Objects do not have the same dimensionality."); + } + return dim1; + } + + /** + * Get the common dimensionality of the two objects. Throw an + * {@link IllegalArgumentException} otherwise. + * + * @param o1 First vector / MBR + * @param o2 Second vector / MBR + * @param expect Expected dimensionality + * @return Common dimensionality + * @throws IllegalArgumentException when dimensionalities are not the same. + */ + public static final int dimensionality(NumberVector<?> o1, NumberVector<?> o2, int expect) { + final int dim1 = o1.getDimensionality(), dim2 = o2.getDimensionality(); if (dim1 != dim2 || dim1 != expect) { throw new IllegalArgumentException("Objects do not have the expected dimensionality of " + expect); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java index 5e29ec51..4da3a5dd 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistance import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -132,7 +132,7 @@ public class MinKDistance<O, D extends Distance<D>> extends AbstractDatabaseDist * KNN query instance */ private KNNQuery<T, D> knnQuery; - + /** * Value for k */ @@ -204,16 +204,16 @@ public class MinKDistance<O, D extends Distance<D>> extends AbstractDatabaseDist public TypeInformation getInputTypeRestriction() { return parentDistance.getInputTypeRestriction(); } - + @Override public boolean equals(Object obj) { if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } - MinKDistance<?,?> other = (MinKDistance<?, ?>) obj; + MinKDistance<?, ?> other = (MinKDistance<?, ?>) obj; return this.parentDistance.equals(other.parentDistance) && this.k == other.k; } @@ -239,16 +239,16 @@ public class MinKDistance<O, D extends Distance<D>> extends AbstractDatabaseDist protected void makeOptions(Parameterization config) { super.makeOptions(config); final IntParameter kP = new IntParameter(K_ID); - kP.addConstraint(new GreaterConstraint(1)); + kP.addConstraint(CommonConstraints.GREATER_THAN_ONE_INT); if(config.grab(kP)) { k = kP.getValue(); } - + final ObjectParameter<DistanceFunction<? super O, D>> parentDistanceP = new ObjectParameter<>(DISTANCE_FUNCTION_ID, DistanceFunction.class, EuclideanDistanceFunction.class); - if (config.grab(parentDistanceP)) { + if(config.grab(parentDistanceP)) { parentDistance = parentDistanceP.instantiateClass(config); } - } + } @Override protected MinKDistance<O, D> makeInstance() { diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java index 890a3ece..b2bd9a72 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java @@ -70,14 +70,14 @@ public abstract class AbstractSimilarityAdapter<O> extends AbstractDatabaseDista /** * Holds the similarity function. */ - protected NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>> similarityFunction; + protected NormalizedSimilarityFunction<? super O> similarityFunction; /** * Constructor. * * @param similarityFunction Similarity function to use. */ - public AbstractSimilarityAdapter(NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>> similarityFunction) { + public AbstractSimilarityAdapter(NormalizedSimilarityFunction<? super O> similarityFunction) { super(); this.similarityFunction = similarityFunction; } @@ -102,11 +102,11 @@ public abstract class AbstractSimilarityAdapter<O> extends AbstractDatabaseDista @Override public boolean equals(Object obj) { - if(obj == null) { + if (obj == null) { return false; } // Same subclass - if(!this.getClass().equals(obj.getClass())) { + if (!this.getClass().equals(obj.getClass())) { return false; } // Same similarity function @@ -170,15 +170,15 @@ public abstract class AbstractSimilarityAdapter<O> extends AbstractDatabaseDista /** * Holds the similarity function. */ - protected NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>> similarityFunction = null; + protected NormalizedSimilarityFunction<? super O> similarityFunction = null; @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); - final ObjectParameter<NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>>> param = new ObjectParameter<>(SIMILARITY_FUNCTION_ID, NormalizedSimilarityFunction.class, FractionalSharedNearestNeighborSimilarityFunction.class); - if(config.grab(param)) { + final ObjectParameter<NormalizedSimilarityFunction<? super O>> param = new ObjectParameter<>(SIMILARITY_FUNCTION_ID, NormalizedSimilarityFunction.class, FractionalSharedNearestNeighborSimilarityFunction.class); + if (config.grab(param)) { similarityFunction = param.instantiateClass(config); } } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/ArccosSimilarityAdapter.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/ArccosSimilarityAdapter.java index a808e2a5..4bb2b99d 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/ArccosSimilarityAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/ArccosSimilarityAdapter.java @@ -47,7 +47,7 @@ public class ArccosSimilarityAdapter<O> extends AbstractSimilarityAdapter<O> { * * @param similarityFunction Similarity function */ - public ArccosSimilarityAdapter(NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>> similarityFunction) { + public ArccosSimilarityAdapter(NormalizedSimilarityFunction<? super O> similarityFunction) { super(similarityFunction); } @@ -95,4 +95,4 @@ public class ArccosSimilarityAdapter<O> extends AbstractSimilarityAdapter<O> { return new ArccosSimilarityAdapter<>(similarityFunction); } } -}
\ No newline at end of file +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LinearAdapterLinear.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LinearAdapterLinear.java index c78ff112..428b2c41 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LinearAdapterLinear.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LinearAdapterLinear.java @@ -47,7 +47,7 @@ public class LinearAdapterLinear<O> extends AbstractSimilarityAdapter<O> { * * @param similarityFunction Similarity function */ - public LinearAdapterLinear(NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>> similarityFunction) { + public LinearAdapterLinear(NormalizedSimilarityFunction<? super O> similarityFunction) { super(similarityFunction); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LnSimilarityAdapter.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LnSimilarityAdapter.java index 2a9b49f9..cffd9e2a 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LnSimilarityAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/LnSimilarityAdapter.java @@ -47,7 +47,7 @@ public class LnSimilarityAdapter<O> extends AbstractSimilarityAdapter<O> { * * @param similarityFunction Similarity function */ - public LnSimilarityAdapter(NormalizedSimilarityFunction<? super O, ? extends NumberDistance<?, ?>> similarityFunction) { + public LnSimilarityAdapter(NormalizedSimilarityFunction<? super O> similarityFunction) { super(similarityFunction); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java index 414a4787..3dae70e8 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java @@ -31,8 +31,7 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ListEachConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ListSizeConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntListParameter; @@ -113,12 +112,12 @@ public class HSBHistogramQuadraticDistanceFunction extends WeightedDistanceFunct if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } - return this.weightMatrix.equals(((HSBHistogramQuadraticDistanceFunction)obj).weightMatrix); + return this.weightMatrix.equals(((HSBHistogramQuadraticDistanceFunction) obj).weightMatrix); } - + /** * Parameterization class. * @@ -138,7 +137,7 @@ public class HSBHistogramQuadraticDistanceFunction extends WeightedDistanceFunct super.makeOptions(config); IntListParameter param = new IntListParameter(BPP_ID); param.addConstraint(new ListSizeConstraint(3)); - param.addConstraint(new ListEachConstraint<Integer>(new GreaterEqualConstraint(1))); + param.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT_LIST); if(config.grab(param)) { List<Integer> quant = param.getValue(); assert (quant.size() == 3); diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java index bece8279..b8c18304 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix; import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.math.linearalgebra.pca.PCAFilteredResult; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -129,14 +129,14 @@ public class ERiCDistanceFunction extends AbstractIndexBasedDistanceFunction<Num private boolean approximatelyLinearDependent(PCAFilteredResult pca1, PCAFilteredResult pca2) { Matrix m1_czech = pca1.dissimilarityMatrix(); Matrix v2_strong = pca2.adapatedStrongEigenvectors(); - for (int i = 0; i < v2_strong.getColumnDimensionality(); i++) { + for(int i = 0; i < v2_strong.getColumnDimensionality(); i++) { Vector v2_i = v2_strong.getCol(i); // check, if distance of v2_i to the space of pca_1 > delta // (i.e., if v2_i spans up a new dimension) double dist = Math.sqrt(v2_i.transposeTimes(v2_i) - v2_i.transposeTimesTimes(m1_czech, v2_i)); // if so, return false - if (dist > delta) { + if(dist > delta) { return false; } } @@ -157,34 +157,36 @@ public class ERiCDistanceFunction extends AbstractIndexBasedDistanceFunction<Num * distance function */ public BitDistance distance(NumberVector<?> v1, NumberVector<?> v2, PCAFilteredResult pca1, PCAFilteredResult pca2) { - if (pca1.getCorrelationDimension() < pca2.getCorrelationDimension()) { + if(pca1.getCorrelationDimension() < pca2.getCorrelationDimension()) { throw new IllegalStateException("pca1.getCorrelationDimension() < pca2.getCorrelationDimension(): " + pca1.getCorrelationDimension() + " < " + pca2.getCorrelationDimension()); } boolean approximatelyLinearDependent; - if (pca1.getCorrelationDimension() == pca2.getCorrelationDimension()) { + if(pca1.getCorrelationDimension() == pca2.getCorrelationDimension()) { approximatelyLinearDependent = approximatelyLinearDependent(pca1, pca2) && approximatelyLinearDependent(pca2, pca1); - } else { + } + else { approximatelyLinearDependent = approximatelyLinearDependent(pca1, pca2); } - if (!approximatelyLinearDependent) { + if(!approximatelyLinearDependent) { return new BitDistance(true); } else { double affineDistance; - if (pca1.getCorrelationDimension() == pca2.getCorrelationDimension()) { + if(pca1.getCorrelationDimension() == pca2.getCorrelationDimension()) { WeightedDistanceFunction df1 = new WeightedDistanceFunction(pca1.similarityMatrix()); WeightedDistanceFunction df2 = new WeightedDistanceFunction(pca2.similarityMatrix()); affineDistance = Math.max(df1.distance(v1, v2).doubleValue(), df2.distance(v1, v2).doubleValue()); - } else { + } + else { WeightedDistanceFunction df1 = new WeightedDistanceFunction(pca1.similarityMatrix()); affineDistance = df1.distance(v1, v2).doubleValue(); } - if (affineDistance > tau) { + if(affineDistance > tau) { return new BitDistance(true); } @@ -194,10 +196,10 @@ public class ERiCDistanceFunction extends AbstractIndexBasedDistanceFunction<Num @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } ERiCDistanceFunction other = (ERiCDistanceFunction) obj; @@ -267,14 +269,14 @@ public class ERiCDistanceFunction extends AbstractIndexBasedDistanceFunction<Num configIndexFactory(config, FilteredLocalPCAIndex.Factory.class, KNNQueryFilteredPCAIndex.Factory.class); final DoubleParameter deltaP = new DoubleParameter(DELTA_ID, 0.1); - deltaP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(deltaP)) { + deltaP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(deltaP)) { delta = deltaP.doubleValue(); } final DoubleParameter tauP = new DoubleParameter(TAU_ID, 0.1); - tauP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(tauP)) { + tauP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(tauP)) { tau = tauP.doubleValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java index 4d5553a3..b7a22b32 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix; import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.math.linearalgebra.pca.PCAFilteredResult; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -93,10 +93,10 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } PCABasedCorrelationDistanceFunction other = (PCABasedCorrelationDistanceFunction) obj; @@ -166,7 +166,7 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // for all strong eigenvectors of rv2 Matrix m1_czech = pca1.dissimilarityMatrix(); - for (int i = 0; i < v2_strong.getColumnDimensionality(); i++) { + for(int i = 0; i < v2_strong.getColumnDimensionality(); i++) { Vector v2_i = v2_strong.getCol(i); // check, if distance of v2_i to the space of rv1 > delta // (i.e., if v2_i spans up a new dimension) @@ -174,7 +174,7 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // if so, insert v2_i into v1 and adjust v1 // and compute m1_czech new, increase lambda1 - if (lambda1 < dimensionality && dist > delta) { + if(lambda1 < dimensionality && dist > delta) { adjust(v1, e1_czech, v2_i, lambda1++); m1_czech = v1.times(e1_czech).timesTranspose(v1); } @@ -182,7 +182,7 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // for all strong eigenvectors of rv1 Matrix m2_czech = pca2.dissimilarityMatrix(); - for (int i = 0; i < v1_strong.getColumnDimensionality(); i++) { + for(int i = 0; i < v1_strong.getColumnDimensionality(); i++) { Vector v1_i = v1_strong.getCol(i); // check, if distance of v1_i to the space of rv2 > delta // (i.e., if v1_i spans up a new dimension) @@ -190,7 +190,7 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // if so, insert v1_i into v2 and adjust v2 // and compute m2_czech new , increase lambda2 - if (lambda2 < dimensionality && dist > delta) { + if(lambda2 < dimensionality && dist > delta) { adjust(v2, e2_czech, v1_i, lambda2++); m2_czech = v2.times(e2_czech).timesTranspose(v2); } @@ -231,7 +231,7 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // normalize v Vector v_i = vector.copy(); Vector sum = new Vector(dim); - for (int k = 0; k < corrDim; k++) { + for(int k = 0; k < corrDim; k++) { Vector v_k = v.getCol(k); sum.plusTimesEquals(v_k, v_i.transposeTimes(v_k)); } @@ -248,12 +248,12 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista * @return the Euclidean distance between the given two vectors */ private double euclideanDistance(V dv1, V dv2) { - if (dv1.getDimensionality() != dv2.getDimensionality()) { + if(dv1.getDimensionality() != dv2.getDimensionality()) { throw new IllegalArgumentException("Different dimensionality of FeatureVectors\n first argument: " + dv1.toString() + "\n second argument: " + dv2.toString()); } double sqrDist = 0; - for (int i = 0; i < dv1.getDimensionality(); i++) { + for(int i = 0; i < dv1.getDimensionality(); i++) { double manhattanI = dv1.doubleValue(i) - dv2.doubleValue(i); sqrDist += manhattanI * manhattanI; } @@ -277,8 +277,8 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista configIndexFactory(config, FilteredLocalPCAIndex.Factory.class, KNNQueryFilteredPCAIndex.Factory.class); final DoubleParameter param = new DoubleParameter(DELTA_ID, 0.25); - param.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(param)) { + param.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(param)) { delta = param.doubleValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java index 9a7315b3..b8e720ab 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java @@ -28,7 +28,6 @@ import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.HashMap; -import java.util.List; import java.util.Map; import java.util.regex.Pattern; @@ -40,6 +39,7 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.datasource.parser.AbstractParser; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.logging.progress.IndefiniteProgress; @@ -78,12 +78,12 @@ public class NumberDistanceParser<D extends NumberDistance<D, ?>> extends Abstra * Constructor. * * @param colSep Column separator pattern - * @param quoteChar Quote character + * @param quoteChars Quote characters * @param comment Comment pattern * @param distanceFactory Distance factory to use */ - public NumberDistanceParser(Pattern colSep, char quoteChar, Pattern comment, D distanceFactory) { - super(colSep, quoteChar, comment); + public NumberDistanceParser(Pattern colSep, String quoteChars, Pattern comment, D distanceFactory) { + super(colSep, quoteChars, comment); this.distanceFactory = distanceFactory; } @@ -96,56 +96,80 @@ public class NumberDistanceParser<D extends NumberDistance<D, ?>> extends Abstra ModifiableDBIDs ids = DBIDUtil.newHashSet(); Map<DBIDPair, D> distanceCache = new HashMap<>(); try { - for (String line; (line = reader.readLine()) != null; lineNumber++) { - if (prog != null) { + for(String line; (line = reader.readLine()) != null; lineNumber++) { + if(prog != null) { prog.incrementProcessed(LOG); } // Skip empty lines and comments - if (line.length() <= 0 || (comment != null && comment.matcher(line).matches())) { + if(line.length() <= 0 || (comment != null && comment.matcher(line).matches())) { continue; } - List<String> entries = tokenize(line); - if (entries.size() != 3) { - throw new IllegalArgumentException("Line " + lineNumber + " does not have the " + "required input format: id1 id2 distanceValue! " + line); - } + tokenizer.initialize(line, 0, lengthWithoutLinefeed(line)); + if(!tokenizer.valid()) { + throw new IllegalArgumentException("Less than three values in line " + lineNumber); + } DBID id1, id2; try { - id1 = DBIDUtil.importInteger(Integer.parseInt(entries.get(0))); - } catch (NumberFormatException e) { + id1 = DBIDUtil.importInteger((int) tokenizer.getLongBase10()); + tokenizer.advance(); + } + catch(NumberFormatException e) { throw new IllegalArgumentException("Error in line " + lineNumber + ": id1 is no integer!"); } + if(!tokenizer.valid()) { + throw new IllegalArgumentException("Less than three values in line " + lineNumber); + } try { - id2 = DBIDUtil.importInteger(Integer.parseInt(entries.get(1))); - } catch (NumberFormatException e) { + id2 = DBIDUtil.importInteger((int) tokenizer.getLongBase10()); + tokenizer.advance(); + } + catch(NumberFormatException e) { throw new IllegalArgumentException("Error in line " + lineNumber + ": id2 is no integer!"); } + if(!tokenizer.valid()) { + throw new IllegalArgumentException("Less than three values in line " + lineNumber); + } try { - D distance = distanceFactory.parseString(entries.get(2)); + final D distance; + if(distanceFactory == DoubleDistance.FACTORY) { + @SuppressWarnings("unchecked") + D dist = (D) DoubleDistance.FACTORY.fromDouble(tokenizer.getDouble()); + distance = dist; + } + else { + distance = distanceFactory.parseString(tokenizer.getSubstring()); + } + tokenizer.advance(); put(id1, id2, distance, distanceCache); ids.add(id1); ids.add(id2); - } catch (IllegalArgumentException e) { + } + catch(IllegalArgumentException e) { throw new IllegalArgumentException("Error in line " + lineNumber + ":" + e.getMessage(), e); } + if(tokenizer.valid()) { + throw new IllegalArgumentException("More than three values in line " + lineNumber); + } } - } catch (IOException e) { + } + catch(IOException e) { throw new IllegalArgumentException("Error while parsing line " + lineNumber + "."); } - if (prog != null) { + if(prog != null) { prog.setCompleted(LOG); } // check if all distance values are specified - for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { - for (DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { - if (DBIDUtil.compare(iter2, iter) <= 0) { + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + for(DBIDIter iter2 = ids.iter(); iter2.valid(); iter2.advance()) { + if(DBIDUtil.compare(iter2, iter) <= 0) { continue; } - if (!containsKey(iter, iter2, distanceCache)) { + if(!containsKey(iter, iter2, distanceCache)) { throw new IllegalArgumentException("Distance value for " + DBIDUtil.toString(iter) + " - " + DBIDUtil.toString(iter2) + " is missing!"); } } @@ -163,14 +187,14 @@ public class NumberDistanceParser<D extends NumberDistance<D, ?>> extends Abstra */ private void put(DBID id1, DBID id2, D distance, Map<DBIDPair, D> cache) { // the smaller id is the first key - if (DBIDUtil.compare(id1, id2) > 0) { + if(DBIDUtil.compare(id1, id2) > 0) { put(id2, id1, distance, cache); return; } D oldDistance = cache.put(DBIDUtil.newPair(id1, id2), distance); - if (oldDistance != null) { + if(oldDistance != null) { throw new IllegalArgumentException("Distance value for specified ids is already assigned!"); } } @@ -186,7 +210,7 @@ public class NumberDistanceParser<D extends NumberDistance<D, ?>> extends Abstra * specified ids, false otherwise */ public boolean containsKey(DBIDRef id1, DBIDRef id2, Map<DBIDPair, D> cache) { - if (DBIDUtil.compare(id1, id2) > 0) { + if(DBIDUtil.compare(id1, id2) > 0) { return containsKey(id2, id1, cache); } @@ -215,14 +239,14 @@ public class NumberDistanceParser<D extends NumberDistance<D, ?>> extends Abstra protected void makeOptions(Parameterization config) { super.makeOptions(config); ObjectParameter<D> distFuncP = new ObjectParameter<>(DISTANCE_ID, Distance.class); - if (config.grab(distFuncP)) { + if(config.grab(distFuncP)) { distanceFactory = distFuncP.instantiateClass(config); } } @Override protected NumberDistanceParser<D> makeInstance() { - return new NumberDistanceParser<>(colSep, quoteChar, comment, distanceFactory); + return new NumberDistanceParser<>(colSep, quoteChars, comment, distanceFactory); } } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java index 1974e533..8eea1f15 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java @@ -34,7 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.exceptions.NotImplementedException; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.NoDuplicateValueGlobalConstraint; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; @@ -83,18 +83,21 @@ public class DimensionSelectingLatLngDistanceFunction extends AbstractSpatialDou @Override @Reference(authors = "Erich Schubert, Arthur Zimek and Hans-Peter Kriegel", title = "Geodetic Distance Queries on R-Trees for Indexing Geographic Data", booktitle = "Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Munich, Germany") public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { + if(mbr1 instanceof NumberVector) { + if(mbr2 instanceof NumberVector) { return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); - } else { + } + else { NumberVector<?> o1 = (NumberVector<?>) mbr1; return model.minDistDeg(o1.doubleValue(dimlat), o1.doubleValue(dimlng), mbr2.getMin(dimlat), mbr2.getMin(dimlng), mbr2.getMax(dimlat), mbr2.getMax(dimlng)); } - } else { - if (mbr2 instanceof NumberVector) { + } + else { + if(mbr2 instanceof NumberVector) { NumberVector<?> o2 = (NumberVector<?>) mbr2; return model.minDistDeg(o2.doubleValue(dimlat), o2.doubleValue(dimlng), mbr1.getMin(dimlat), mbr1.getMin(dimlng), mbr1.getMax(dimlat), mbr1.getMax(dimlng)); - } else { + } + else { throw new NotImplementedException("This distance function cannot - yet - be used with this algorithm, as the lower bound rectangle to rectangle distances have not yet been formalized for geodetic data."); } } @@ -117,27 +120,28 @@ public class DimensionSelectingLatLngDistanceFunction extends AbstractSpatialDou @Override public boolean equals(Object obj) { - if (this == obj) { + if(this == obj) { return true; } - if (obj == null) { + if(obj == null) { return false; } - if (getClass() != obj.getClass()) { + if(getClass() != obj.getClass()) { return false; } DimensionSelectingLatLngDistanceFunction other = (DimensionSelectingLatLngDistanceFunction) obj; - if (dimlat != other.dimlat) { + if(dimlat != other.dimlat) { return false; } - if (dimlng != other.dimlng) { + if(dimlng != other.dimlng) { return false; } - if (model == null) { - if (other.model != null) { + if(model == null) { + if(other.model != null) { return false; } - } else if (!model.equals(other.model)) { + } + else if(!model.equals(other.model)) { return false; } return true; @@ -180,18 +184,18 @@ public class DimensionSelectingLatLngDistanceFunction extends AbstractSpatialDou protected void makeOptions(Parameterization config) { super.makeOptions(config); final IntParameter dimlatP = new IntParameter(LATDIM_ID); - dimlatP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(dimlatP)) { + dimlatP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_INT); + if(config.grab(dimlatP)) { dimlat = dimlatP.getValue(); } final IntParameter dimlngP = new IntParameter(LNGDIM_ID); - dimlngP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(dimlngP)) { + dimlngP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_INT); + if(config.grab(dimlngP)) { dimlng = dimlngP.getValue(); } config.checkConstraint(new NoDuplicateValueGlobalConstraint(dimlatP, dimlngP)); ObjectParameter<EarthModel> modelP = new ObjectParameter<>(EarthModel.MODEL_ID, EarthModel.class, SphericalVincentyEarthModel.class); - if (config.grab(modelP)) { + if(config.grab(modelP)) { model = modelP.instantiateClass(config); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/histogram/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/histogram/package-info.java index e6a9a8be..770dcf52 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/histogram/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/histogram/package-info.java @@ -1,4 +1,27 @@ /** * Distance functions for <b>one-dimensional</b> histograms. */ + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ package de.lmu.ifi.dbs.elki.distance.distancefunction.histogram;
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/EuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/EuclideanDistanceFunction.java index 03116430..24dfdc16 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/EuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/EuclideanDistanceFunction.java @@ -34,7 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * @author Arthur Zimek */ @Alias({ "euclidean", "euclid", "l2", "EuclideanDistanceFunction", "de.lmu.ifi.dbs.elki.distance.distancefunction.EuclideanDistanceFunction" }) -public class EuclideanDistanceFunction extends LPNormDistanceFunction { +public class EuclideanDistanceFunction extends LPIntegerNormDistanceFunction { /** * Static instance. Use this! */ @@ -48,81 +48,127 @@ public class EuclideanDistanceFunction extends LPNormDistanceFunction { */ @Deprecated public EuclideanDistanceFunction() { - super(2.); + super(2); } - @Override - public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double delta = v1.doubleValue(d) - v2.doubleValue(d); + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, int start, int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); + final double delta = xd - yd; agg += delta * delta; } - return Math.sqrt(agg); + return agg; } - @Override - public double doubleNorm(NumberVector<?> v) { - final int dim = v.getDimensionality(); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double val = v.doubleValue(d); - agg += val * val; + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, int start, int end, double agg) { + for(int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if(delta < 0.) { + delta = value - mbr.getMax(d); + } + if(delta > 0.) { + agg += delta * delta; + } } - return Math.sqrt(agg); + return agg; } - protected double doubleMinDistObject(NumberVector<?> v, SpatialComparable mbr) { - final int dim = dimensionality(mbr, v); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double value = v.doubleValue(d), min = mbr.getMin(d); - final double diff; - if (value < min) { - diff = min - value; - } else { - final double max = mbr.getMax(d); - if (value > max) { - diff = value - max; - } else { - continue; - } + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, int start, int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if(delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if(delta > 0.) { + agg += delta * delta; } - agg += diff * diff; + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, int start, int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v.doubleValue(d); + agg += xd * xd; + } + return agg; + } + + private final double doublePreNormMBR(SpatialComparable mbr, int start, int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if(delta < 0.) { + delta = -mbr.getMax(d); + } + if(delta > 0.) { + agg += delta * delta; + } + } + return agg; + } + + @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if(dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else if(dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); } return Math.sqrt(agg); } @Override + public double doubleNorm(NumberVector<?> v) { + return Math.sqrt(doublePreNorm(v, 0, v.getDimensionality(), 0.)); + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Some optimizations for simpler cases. - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); - } else { - return doubleMinDistObject((NumberVector<?>) mbr1, mbr2); - } - } else if (mbr2 instanceof NumberVector) { - return doubleMinDistObject((NumberVector<?>) mbr2, mbr1); - } - final int dim = dimensionality(mbr1, mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; double agg = 0.; - for (int d = 0; d < dim; d++) { - final double diff; - final double d1 = mbr2.getMin(d) - mbr1.getMax(d); - if (d1 > 0.) { - diff = d1; - } else { - final double d2 = mbr1.getMin(d) - mbr2.getMax(d); - if (d2 > 0.) { - diff = d2; - } else { - continue; - } + if(v1 != null) { + if(v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } + else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } + else { + if(v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } + else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); + } + } + // first object has more dimensions. + if(dim1 > mindim) { + if(v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); + } + } + // second object has more dimensions. + if(dim2 > mindim) { + if(v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); } - agg += diff * diff; } return Math.sqrt(agg); } @@ -139,13 +185,13 @@ public class EuclideanDistanceFunction extends LPNormDistanceFunction { @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (obj == this) { + if(obj == this) { return true; } - if (this.getClass().equals(obj.getClass())) { + if(this.getClass().equals(obj.getClass())) { return true; } return super.equals(obj); diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPIntegerNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPIntegerNormDistanceFunction.java new file mode 100644 index 00000000..22ae45b3 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPIntegerNormDistanceFunction.java @@ -0,0 +1,215 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.math.MathUtil; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; + +/** + * Provides a LP-Norm for number vectors. Optimized version for integer values + * of p. This will likely not have huge impact, but YMMV. + * + * @author Erich Schubert + * + * @apiviz.landmark + */ +public class LPIntegerNormDistanceFunction extends LPNormDistanceFunction { + /** + * Integer value of p. + */ + int intp; + + /** + * Constructor, internal version. + * + * @param p Parameter p + */ + public LPIntegerNormDistanceFunction(int p) { + super(p); + this.intp = p; + } + + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); + final double delta = (xd >= yd) ? xd - yd : yd - xd; + agg += MathUtil.powi(delta, intp); + } + return agg; + } + + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if(delta < 0.) { + delta = value - mbr.getMax(d); + } + if(delta > 0.) { + agg += MathUtil.powi(delta, intp); + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if(delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if(delta > 0.) { + agg += MathUtil.powi(delta, intp); + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v.doubleValue(d); + final double delta = xd >= 0. ? xd : -xd; + agg += MathUtil.powi(delta, intp); + } + return agg; + } + + private final double doublePreNormMBR(SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if(delta < 0.) { + delta = -mbr.getMax(d); + } + if(delta > 0.) { + agg += MathUtil.powi(delta, intp); + } + } + return agg; + } + + @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if(dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else if(dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + return Math.pow(agg, invp); + } + + @Override + public double doubleNorm(NumberVector<?> v) { + return Math.pow(doublePreNorm(v, 0, v.getDimensionality(), 0.), invp); + } + + @Override + public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if(v1 != null) { + if(v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } + else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } + else { + if(v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } + else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); + } + } + // first object has more dimensions. + if(dim1 > mindim) { + if(v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); + } + } + // second object has more dimensions. + if(dim2 > mindim) { + if(v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); + } + } + return Math.pow(agg, invp); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + /** + * The value of p. + */ + protected int p; + + @Override + protected void makeOptions(Parameterization config) { + super.makeOptions(config); + final IntParameter paramP = new IntParameter(P_ID); + paramP.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT); + if(config.grab(paramP)) { + p = paramP.getValue(); + } + } + + @Override + protected LPIntegerNormDistanceFunction makeInstance() { + if(p == 1) { + return ManhattanDistanceFunction.STATIC; + } + if(p == 2) { + return EuclideanDistanceFunction.STATIC; + } + return new LPIntegerNormDistanceFunction(p); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPNormDistanceFunction.java index c25e04f1..42753ac1 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPNormDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/LPNormDistanceFunction.java @@ -25,11 +25,13 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; +import de.lmu.ifi.dbs.elki.data.type.TypeUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractSpatialDoubleDistanceNorm; import de.lmu.ifi.dbs.elki.utilities.Alias; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -63,62 +65,180 @@ public class LPNormDistanceFunction extends AbstractSpatialDoubleDistanceNorm { this.invp = 1. / p; } - @Override - public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2); - double agg = 0.; - for (int d = 0; d < dim; d++) { + /** + * Compute unscaled distance in a range of dimensions. + * + * @param v1 First object + * @param v2 Second object + * @param start First dimension + * @param end Exclusive last dimension + * @param agg Current aggregate value + * @return Aggregated values. + */ + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); final double delta = (xd >= yd) ? xd - yd : yd - xd; agg += Math.pow(delta, p); } - return Math.pow(agg, invp); + return agg; } - @Override - public double doubleNorm(NumberVector<?> v) { - final int dim = v.getDimensionality(); - double agg = 0.; - for (int d = 0; d < dim; d++) { + /** + * Compute unscaled distance in a range of dimensions. + * + * @param v First vector + * @param mbr Second MBR + * @param start First dimension + * @param end Exclusive last dimension + * @param agg Current aggregate value + * @return Aggregated values. + */ + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if(delta < 0.) { + delta = value - mbr.getMax(d); + } + if(delta > 0.) { + agg += Math.pow(delta, p); + } + } + return agg; + } + + /** + * Compute unscaled distance in a range of dimensions. + * + * @param mbr1 First MBR + * @param mbr2 Second MBR + * @param start First dimension + * @param end Exclusive last dimension + * @param agg Current aggregate value + * @return Aggregated values. + */ + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if(delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if(delta > 0.) { + agg += Math.pow(delta, p); + } + } + return agg; + } + + /** + * Compute unscaled norm in a range of dimensions. + * + * @param v Data object + * @param start First dimension + * @param end Exclusive last dimension + * @param agg Current aggregate value + * @return Aggregated values. + */ + private final double doublePreNorm(NumberVector<?> v, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { final double xd = v.doubleValue(d); - agg += Math.pow(xd >= 0. ? xd : -xd, p); + final double delta = xd >= 0. ? xd : -xd; + agg += Math.pow(delta, p); + } + return agg; + } + + /** + * Compute unscaled norm in a range of dimensions. + * + * @param mbr Data object + * @param start First dimension + * @param end Exclusive last dimension + * @param agg Current aggregate value + * @return Aggregated values. + */ + private final double doublePreNormMBR(SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if(delta < 0.) { + delta = -mbr.getMax(d); + } + if(delta > 0.) { + agg += Math.pow(delta, p); + } + } + return agg; + } + + @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if(dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else if(dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); } return Math.pow(agg, invp); } @Override + public double doubleNorm(NumberVector<?> v) { + return Math.pow(doublePreNorm(v, 0, v.getDimensionality(), 0.), invp); + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Optimization for the simplest case - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); - } - } - // TODO: optimize for more simpler cases: obj vs. rect? - final int dim = dimensionality(mbr1, mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; double agg = 0.; - for (int d = 0; d < dim; d++) { - final double diff; - final double d1 = mbr2.getMin(d) - mbr1.getMax(d); - if (d1 > 0.) { - diff = d1; - } else { - final double d2 = mbr1.getMin(d) - mbr2.getMax(d); - if (d2 > 0.) { - diff = d2; - } else { // The mbrs intersect! - continue; - } - } - agg += Math.pow(diff, p); + if(v1 != null) { + if(v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } + else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } + else { + if(v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } + else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); + } + } + // first object has more dimensions. + if(dim1 > mindim) { + if(v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); + } + } + // second object has more dimensions. + if(dim2 > mindim) { + if(v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); + } } return Math.pow(agg, invp); } @Override public boolean isMetric() { - return (p >= 1); + return (p >= 1.); } @Override @@ -137,15 +257,20 @@ public class LPNormDistanceFunction extends AbstractSpatialDoubleDistanceNorm { @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (obj instanceof LPNormDistanceFunction) { + if(obj instanceof LPNormDistanceFunction) { return this.p == ((LPNormDistanceFunction) obj).p; } return false; } + @Override + public SimpleTypeInformation<? super NumberVector<?>> getInputTypeRestriction() { + return TypeUtil.NUMBER_VECTOR_VARIABLE_LENGTH; + } + /** * Parameterization class. * @@ -163,23 +288,26 @@ public class LPNormDistanceFunction extends AbstractSpatialDoubleDistanceNorm { protected void makeOptions(Parameterization config) { super.makeOptions(config); final DoubleParameter paramP = new DoubleParameter(P_ID); - paramP.addConstraint(new GreaterConstraint(0.)); - if (config.grab(paramP)) { + paramP.addConstraint(CommonConstraints.GREATER_THAN_ZERO_DOUBLE); + if(config.grab(paramP)) { p = paramP.getValue(); } } @Override protected LPNormDistanceFunction makeInstance() { - if (p == 1.0) { + if(p == 1.) { return ManhattanDistanceFunction.STATIC; } - if (p == 2.0) { + if(p == 2.) { return EuclideanDistanceFunction.STATIC; } - if (p == Double.POSITIVE_INFINITY) { + if(p == Double.POSITIVE_INFINITY) { return MaximumDistanceFunction.STATIC; } + if(p == Math.round(p)) { + return new LPIntegerNormDistanceFunction((int) p); + } return new LPNormDistanceFunction(p); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/ManhattanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/ManhattanDistanceFunction.java index 9b8f80a7..3d5d061c 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/ManhattanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/ManhattanDistanceFunction.java @@ -35,7 +35,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * @author Arthur Zimek */ @Alias({ "taxicab", "cityblock", "l1", "ManhattanDistanceFunction", "de.lmu.ifi.dbs.elki.distance.distancefunction.ManhattanDistanceFunction" }) -public class ManhattanDistanceFunction extends LPNormDistanceFunction { +public class ManhattanDistanceFunction extends LPIntegerNormDistanceFunction { /** * The static instance to use. */ @@ -49,73 +49,121 @@ public class ManhattanDistanceFunction extends LPNormDistanceFunction { */ @Deprecated public ManhattanDistanceFunction() { - super(1.); + super(1); } - @Override - public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2); - double agg = 0.; - for (int d = 0; d < dim; d++) { + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, int start, int end, double agg) { + for (int d = start; d < end; d++) { final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); - final double val = (xd >= yd) ? xd - yd : yd - xd; - agg += val; + final double delta = (xd >= yd) ? xd - yd : yd - xd; + agg += delta; } return agg; } - @Override - public double doubleNorm(NumberVector<?> v) { - final int dim = v.getDimensionality(); - double agg = 0.; - for (int d = 0; d < dim; d++) { + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, int start, int end, double agg) { + for (int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if (delta < 0.) { + delta = value - mbr.getMax(d); + } + if (delta > 0.) { + agg += delta; + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, int start, int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if (delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if (delta > 0.) { + agg += delta; + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, int start, int end, double agg) { + for (int d = start; d < end; d++) { final double xd = v.doubleValue(d); - agg += (xd >= 0.) ? xd : -xd; + final double delta = (xd >= 0.) ? xd : -xd; + agg += delta; } return agg; } - protected double doubleMinDistObject(NumberVector<?> v, SpatialComparable mbr) { - final int dim = dimensionality(mbr, v); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double value = v.doubleValue(d), min = mbr.getMin(d); - if (value < min) { - agg += min - value; - } else { - final double max = mbr.getMax(d); - if (value > max) { - agg += value - max; - } + private final double doublePreNormMBR(SpatialComparable mbr, int start, int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if (delta < 0.) { + delta = -mbr.getMax(d); + } + if (delta > 0.) { + agg += delta; } } return agg; } @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if (dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else if (dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + return agg; + } + + @Override + public double doubleNorm(NumberVector<?> v) { + return doublePreNorm(v, 0, v.getDimensionality(), 0.); + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Some optimizations for simpler cases. - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if (v1 != null) { + if (v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } else { + if (v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); } else { - return doubleMinDistObject((NumberVector<?>) mbr1, mbr2); + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); } - } else if (mbr2 instanceof NumberVector) { - return doubleMinDistObject((NumberVector<?>) mbr2, mbr1); } - final int dim = dimensionality(mbr1, mbr2); - - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double d1 = mbr2.getMin(d) - mbr1.getMax(d); - if (d1 > 0.) { - agg += d1; + // first object has more dimensions. + if (dim1 > mindim) { + if (v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); + } + } + // second object has more dimensions. + if (dim2 > mindim) { + if (v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); } else { - final double d2 = mbr1.getMin(d) - mbr2.getMax(d); - if (d2 > 0.) { - agg += d2; - } + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); } } return agg; diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/MaximumDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/MaximumDistanceFunction.java index 1b54e278..2cc1b10c 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/MaximumDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/MaximumDistanceFunction.java @@ -52,61 +52,122 @@ public class MaximumDistanceFunction extends LPNormDistanceFunction { super(Double.POSITIVE_INFINITY); } - @Override - public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2); - double agg = 0.; - for (int d = 0; d < dim; d++) { + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, int start, int end, double agg) { + for (int d = start; d < end; d++) { final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); - final double val = (xd >= yd) ? xd - yd : yd - xd; - if (val > agg) { - agg = val; + final double delta = (xd >= yd) ? xd - yd : yd - xd; + if (delta > agg) { + agg = delta; } } return agg; } - @Override - public double doubleNorm(NumberVector<?> v) { - final int dim = v.getDimensionality(); - double agg = 0.; - for (int d = 0; d < dim; d++) { + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, int start, int end, double agg) { + for (int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if (delta < 0.) { + delta = value - mbr.getMax(d); + } + if (delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, int start, int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if (delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if (delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, int start, int end, double agg) { + for (int d = start; d < end; d++) { final double xd = v.doubleValue(d); - final double val = (xd >= 0.) ? xd : -xd; - if (val > agg) { - agg = val; + final double delta = (xd >= 0.) ? xd : -xd; + if (delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreNormMBR(SpatialComparable mbr, int start, int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if (delta < 0.) { + delta = -mbr.getMax(d); + } + if (delta > agg) { + agg = delta; } } return agg; } @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if (dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else if (dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + return agg; + } + + @Override + public double doubleNorm(NumberVector<?> v) { + return doublePreNorm(v, 0, v.getDimensionality(), 0.); + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Some optimizations for simpler cases. - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if (v1 != null) { + if (v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } else { + if (v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); } } - // TODO: add optimization for point to MBR? - final int dim = dimensionality(mbr1, mbr2); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double diff; - final double d1 = mbr2.getMin(d) - mbr1.getMax(d); - if (d1 > 0.) { - diff = d1; + // first object has more dimensions. + if (dim1 > mindim) { + if (v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); } else { - final double d2 = mbr1.getMin(d) - mbr2.getMax(d); - if (d2 > 0.) { - diff = d2; - } else { - // The objects overlap in this dimension. - continue; - } + agg = doublePreNormMBR(v1, mindim, dim1, agg); } - if (diff > agg) { - agg = diff; + } + // second object has more dimensions. + if (dim2 > mindim) { + if (v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); } } return agg; diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseEuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseEuclideanDistanceFunction.java index bf621103..8fcf0c84 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseEuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseEuclideanDistanceFunction.java @@ -23,8 +23,6 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.BitSet; - import de.lmu.ifi.dbs.elki.data.SparseNumberVector; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @@ -46,50 +44,56 @@ public class SparseEuclideanDistanceFunction extends SparseLPNormDistanceFunctio */ @Deprecated public SparseEuclideanDistanceFunction() { - super(2.0); + super(2.); } @Override public double doubleDistance(SparseNumberVector<?> v1, SparseNumberVector<?> v2) { // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - BitSet b2 = v2.getNotNullMask(); - double accu = 0; - int i1 = b1.nextSetBit(0); - int i2 = b2.nextSetBit(0); - while (true) { - if (i1 == i2) { - if (i1 < 0) { - break; - } - // Both vectors have a value. - double val = v1.doubleValue(i1) - v2.doubleValue(i2); - accu += val * val; - i1 = b1.nextSetBit(i1 + 1); - i2 = b2.nextSetBit(i2 + 1); - } else if (i2 < 0 || (i1 < i2 && i1 >= 0)) { + double accu = 0.; + int i1 = v1.iter(), i2 = v2.iter(); + while(v1.iterValid(i1) && v2.iterValid(i2)) { + final int d1 = v1.iterDim(i1), d2 = v2.iterDim(i2); + if(d1 < d2) { // In first only - double val = v1.doubleValue(i1); + final double val = v1.iterDoubleValue(i1); accu += val * val; - i1 = b1.nextSetBit(i1 + 1); - } else { + i1 = v1.iterAdvance(i1); + } + else if(d2 < d1) { // In second only - double val = v2.doubleValue(i2); + final double val = v2.iterDoubleValue(i2); + accu += val * val; + i2 = v2.iterAdvance(i2); + } + else { + // Both vectors have a value. + final double val = v1.iterDoubleValue(i1) - v2.iterDoubleValue(i2); accu += val * val; - i2 = b2.nextSetBit(i2 + 1); + i1 = v1.iterAdvance(i1); + i2 = v2.iterAdvance(i2); } } + while(v1.iterValid(i1)) { + // In first only + final double val = v1.iterDoubleValue(i1); + accu += val * val; + i1 = v1.iterAdvance(i1); + } + while(v2.iterValid(i2)) { + // In second only + final double val = v2.iterDoubleValue(i2); + accu += val * val; + i2 = v2.iterAdvance(i2); + } return Math.sqrt(accu); } @Override public double doubleNorm(SparseNumberVector<?> v1) { - double accu = 0; - // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - // Set in first only - for (int i = b1.nextSetBit(0); i >= 0; i = b1.nextSetBit(i + 1)) { - double val = v1.doubleValue(i); + double accu = 0.; + for(int it = v1.iter(); v1.iterValid(it); it = v1.iterAdvance(it)) { + final double val = v1.iterDoubleValue(it); accu += val * val; } return Math.sqrt(accu); diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseLPNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseLPNormDistanceFunction.java index 53d63ff8..9fbd9f7f 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseLPNormDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseLPNormDistanceFunction.java @@ -23,8 +23,6 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.BitSet; - import de.lmu.ifi.dbs.elki.data.SparseNumberVector; import de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; import de.lmu.ifi.dbs.elki.data.type.TypeUtil; @@ -32,7 +30,7 @@ import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractPrimitiveDistanceFu import de.lmu.ifi.dbs.elki.distance.distancefunction.DoubleNorm; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -46,59 +44,67 @@ public class SparseLPNormDistanceFunction extends AbstractPrimitiveDistanceFunct /** * Keeps the currently set p. */ - private double p; + private double p, invp; /** * Provides a LP-Norm for FeatureVectors. */ public SparseLPNormDistanceFunction(double p) { super(); + this.p = p; + this.invp = 1. / p; } @Override public double doubleDistance(SparseNumberVector<?> v1, SparseNumberVector<?> v2) { // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - BitSet b2 = v2.getNotNullMask(); - double accu = 0; - int i1 = b1.nextSetBit(0); - int i2 = b2.nextSetBit(0); - while (true) { - if (i1 == i2) { - if (i1 < 0) { - break; - } - // Both vectors have a value. - double val = Math.abs(v1.doubleValue(i1) - v2.doubleValue(i2)); - accu += Math.pow(val, p); - i1 = b1.nextSetBit(i1 + 1); - i2 = b2.nextSetBit(i2 + 1); - } else if (i2 < 0 || (i1 < i2 && i1 >= 0)) { + double accu = 0.; + int i1 = v1.iter(), i2 = v2.iter(); + while(v1.iterValid(i1) && v2.iterValid(i2)) { + final int d1 = v1.iterDim(i1), d2 = v2.iterDim(i2); + if(d1 < d2) { // In first only - double val = Math.abs(v1.doubleValue(i1)); + final double val = Math.abs(v1.iterDoubleValue(i1)); accu += Math.pow(val, p); - i1 = b1.nextSetBit(i1 + 1); - } else { + i1 = v1.iterAdvance(i1); + } + else if(d2 < d1) { // In second only - double val = Math.abs(v2.doubleValue(i2)); + final double val = Math.abs(v2.iterDoubleValue(i2)); + accu += Math.pow(val, p); + i2 = v2.iterAdvance(i2); + } + else { + // Both vectors have a value. + final double val = Math.abs(v1.iterDoubleValue(i1) - v2.iterDoubleValue(i2)); accu += Math.pow(val, p); - i2 = b2.nextSetBit(i2 + 1); + i1 = v1.iterAdvance(i1); + i2 = v2.iterAdvance(i2); } } - return Math.pow(accu, 1.0 / p); + while(v1.iterValid(i1)) { + // In first only + final double val = Math.abs(v1.iterDoubleValue(i1)); + accu += Math.pow(val, p); + i1 = v1.iterAdvance(i1); + } + while(v2.iterValid(i2)) { + // In second only + final double val = Math.abs(v2.iterDoubleValue(i2)); + accu += Math.pow(val, p); + i2 = v2.iterAdvance(i2); + } + return Math.pow(accu, invp); } @Override public double doubleNorm(SparseNumberVector<?> v1) { - double sqrDist = 0; - // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - // Set in first only - for(int i = b1.nextSetBit(0); i >= 0; i = b1.nextSetBit(i + 1)) { - double manhattanI = Math.abs(v1.doubleValue(i)); - sqrDist += Math.pow(manhattanI, p); + double accu = 0.; + for(int it = v1.iter(); v1.iterValid(it); it = v1.iterAdvance(it)) { + final double val = Math.abs(v1.iterDoubleValue(it)); + accu += Math.pow(val, p); } - return Math.pow(sqrDist, 1.0 / p); + return Math.pow(accu, invp); } @Override @@ -123,7 +129,7 @@ public class SparseLPNormDistanceFunction extends AbstractPrimitiveDistanceFunct @Override public boolean isMetric() { - return (p >= 1); + return (p >= 1.); } /** @@ -137,13 +143,13 @@ public class SparseLPNormDistanceFunction extends AbstractPrimitiveDistanceFunct /** * Value for p */ - double p = 2.0; + double p = 2.; @Override protected void makeOptions(Parameterization config) { super.makeOptions(config); DoubleParameter pP = new DoubleParameter(LPNormDistanceFunction.P_ID); - pP.addConstraint(new GreaterConstraint(0)); + pP.addConstraint(CommonConstraints.GREATER_THAN_ZERO_DOUBLE); if(config.grab(pP)) { p = pP.getValue(); } @@ -151,10 +157,10 @@ public class SparseLPNormDistanceFunction extends AbstractPrimitiveDistanceFunct @Override protected SparseLPNormDistanceFunction makeInstance() { - if(p == 2.0) { + if(p == 2.) { return SparseEuclideanDistanceFunction.STATIC; } - if(p == 1.0) { + if(p == 1.) { return SparseManhattanDistanceFunction.STATIC; } if(p == Double.POSITIVE_INFINITY) { diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseManhattanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseManhattanDistanceFunction.java index 4e397e0c..b22aaad7 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseManhattanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseManhattanDistanceFunction.java @@ -1,4 +1,5 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; + /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures @@ -22,8 +23,6 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.BitSet; - import de.lmu.ifi.dbs.elki.data.SparseNumberVector; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @@ -37,7 +36,7 @@ public class SparseManhattanDistanceFunction extends SparseLPNormDistanceFunctio * Static instance */ public static final SparseManhattanDistanceFunction STATIC = new SparseManhattanDistanceFunction(); - + /** * Constructor. * @@ -45,52 +44,59 @@ public class SparseManhattanDistanceFunction extends SparseLPNormDistanceFunctio */ @Deprecated public SparseManhattanDistanceFunction() { - super(1.0); + super(1.); } @Override public double doubleDistance(SparseNumberVector<?> v1, SparseNumberVector<?> v2) { // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - BitSet b2 = v2.getNotNullMask(); - double accu = 0; - int i1 = b1.nextSetBit(0); - int i2 = b2.nextSetBit(0); - while (true) { - if (i1 == i2) { - if (i1 < 0) { - break; - } - // Both vectors have a value. - double val = Math.abs(v1.doubleValue(i1) - v2.doubleValue(i2)); - accu += val; - i1 = b1.nextSetBit(i1 + 1); - i2 = b2.nextSetBit(i2 + 1); - } else if (i2 < 0 || (i1 < i2 && i1 >= 0)) { + double accu = 0.; + int i1 = v1.iter(), i2 = v2.iter(); + while(v1.iterValid(i1) && v2.iterValid(i2)) { + final int d1 = v1.iterDim(i1), d2 = v2.iterDim(i2); + if(d1 < d2) { // In first only - double val = Math.abs(v1.doubleValue(i1)); + final double val = Math.abs(v1.iterDoubleValue(i1)); accu += val; - i1 = b1.nextSetBit(i1 + 1); - } else { + i1 = v1.iterAdvance(i1); + } + else if(d2 < d1) { // In second only - double val = Math.abs(v2.doubleValue(i2)); + final double val = Math.abs(v2.iterDoubleValue(i2)); accu += val; - i2 = b2.nextSetBit(i2 + 1); + i2 = v2.iterAdvance(i2); } + else { + // Both vectors have a value. + final double val = Math.abs(v1.iterDoubleValue(i1) - v2.iterDoubleValue(i2)); + accu += val; + i1 = v1.iterAdvance(i1); + i2 = v2.iterAdvance(i2); + } + } + while(v1.iterValid(i1)) { + // In first only + final double val = Math.abs(v1.iterDoubleValue(i1)); + accu += val; + i1 = v1.iterAdvance(i1); + } + while(v2.iterValid(i2)) { + // In second only + final double val = Math.abs(v2.iterDoubleValue(i2)); + accu += val; + i2 = v2.iterAdvance(i2); } return accu; } @Override public double doubleNorm(SparseNumberVector<?> v1) { - double sqrDist = 0; - // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - // Set in first only - for(int i = b1.nextSetBit(0); i >= 0; i = b1.nextSetBit(i + 1)) { - sqrDist += Math.abs(v1.doubleValue(i)); + double accu = 0.; + for(int it = v1.iter(); v1.iterValid(it); it = v1.iterAdvance(it)) { + final double val = Math.abs(v1.iterDoubleValue(it)); + accu += val; } - return sqrDist; + return accu; } /** diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseMaximumDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseMaximumDistanceFunction.java index f01ae32b..4a516f7a 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseMaximumDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseMaximumDistanceFunction.java @@ -1,9 +1,5 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; -import java.util.BitSet; - -import de.lmu.ifi.dbs.elki.data.SparseNumberVector; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /* This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures @@ -26,6 +22,8 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ +import de.lmu.ifi.dbs.elki.data.SparseNumberVector; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** * Maximum distance function. Optimized for sparse vectors. @@ -37,7 +35,7 @@ public class SparseMaximumDistanceFunction extends SparseLPNormDistanceFunction * Static instance */ public static final SparseMaximumDistanceFunction STATIC = new SparseMaximumDistanceFunction(); - + /** * Constructor. * @@ -51,46 +49,65 @@ public class SparseMaximumDistanceFunction extends SparseLPNormDistanceFunction @Override public double doubleDistance(SparseNumberVector<?> v1, SparseNumberVector<?> v2) { // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - BitSet b2 = v2.getNotNullMask(); - double accu = 0; - int i1 = b1.nextSetBit(0); - int i2 = b2.nextSetBit(0); - while (true) { - if (i1 == i2) { - if (i1 < 0) { - break; - } - // Both vectors have a value. - double val = Math.abs(v1.doubleValue(i1) - v2.doubleValue(i2)); - accu = Math.max(accu, val); - i1 = b1.nextSetBit(i1 + 1); - i2 = b2.nextSetBit(i2 + 1); - } else if (i2 < 0 || (i1 < i2 && i1 >= 0)) { + double accu = 0.; + int i1 = v1.iter(), i2 = v2.iter(); + while(v1.iterValid(i1) && v2.iterValid(i2)) { + final int d1 = v1.iterDim(i1), d2 = v2.iterDim(i2); + if(d1 < d2) { // In first only - double val = Math.abs(v1.doubleValue(i1)); - accu = Math.max(accu, val); - i1 = b1.nextSetBit(i1 + 1); - } else { + final double val = Math.abs(v1.iterDoubleValue(i1)); + if(val > accu) { + accu = val; + } + i1 = v1.iterAdvance(i1); + } + else if(d2 < d1) { // In second only - double val = Math.abs(v2.doubleValue(i2)); - accu = Math.max(accu, val); - i2 = b2.nextSetBit(i2 + 1); + final double val = Math.abs(v2.iterDoubleValue(i2)); + if(val > accu) { + accu = val; + } + i2 = v2.iterAdvance(i2); } + else { + // Both vectors have a value. + final double val = Math.abs(v1.iterDoubleValue(i1) - v2.iterDoubleValue(i2)); + if(val > accu) { + accu = val; + } + i1 = v1.iterAdvance(i1); + i2 = v2.iterAdvance(i2); + } + } + while(v1.iterValid(i1)) { + // In first only + final double val = Math.abs(v1.iterDoubleValue(i1)); + if(val > accu) { + accu = val; + } + i1 = v1.iterAdvance(i1); + } + while(v2.iterValid(i2)) { + // In second only + final double val = Math.abs(v2.iterDoubleValue(i2)); + if(val > accu) { + accu = val; + } + i2 = v2.iterAdvance(i2); } return accu; } @Override public double doubleNorm(SparseNumberVector<?> v1) { - double sqrDist = 0; - // Get the bit masks - BitSet b1 = v1.getNotNullMask(); - // Set in first only - for(int i = b1.nextSetBit(0); i >= 0; i = b1.nextSetBit(i + 1)) { - sqrDist = Math.max(sqrDist, Math.abs(v1.doubleValue(i))); + double accu = 0.; + for(int it = v1.iter(); v1.iterValid(it); it = v1.iterAdvance(it)) { + final double val = Math.abs(v1.iterDoubleValue(it)); + if(val > accu) { + accu = val; + } } - return sqrDist; + return accu; } /** diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedEuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedEuclideanDistanceFunction.java index 2bc85aae..4fb4e6a2 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedEuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedEuclideanDistanceFunction.java @@ -43,74 +43,143 @@ public class WeightedEuclideanDistanceFunction extends WeightedLPNormDistanceFun super(2.0, weights); } - /** - * Provides the Euclidean distance between the given two vectors. - * - * @return the Euclidean distance between the given two vectors as raw double - * value - */ - @Override - public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2, weights.length); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double delta = (v1.doubleValue(d) - v2.doubleValue(d)); + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); + final double delta = xd - yd; agg += delta * delta * weights[d]; } - return Math.sqrt(agg); + return agg; + } + + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if(delta < 0.) { + delta = value - mbr.getMax(d); + } + if(delta > 0.) { + agg += delta * delta * weights[d]; + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if(delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if(delta > 0.) { + agg += delta * delta * weights[d]; + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v.doubleValue(d); + agg += xd * xd * weights[d]; + } + return agg; + } + + private final double doublePreNormMBR(SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if(delta < 0.) { + delta = -mbr.getMax(d); + } + if(delta > 0.) { + agg += delta * delta * weights[d]; + } + } + return agg; } @Override - public double doubleNorm(NumberVector<?> obj) { - final int dim = obj.getDimensionality(); - double agg = 0.; - for (int d = 0; d < dim; d++) { - final double delta = obj.doubleValue(dim); - agg += delta * delta * weights[d]; + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if(dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else if(dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); } return Math.sqrt(agg); } @Override + public double doubleNorm(NumberVector<?> v) { + return Math.sqrt(doublePreNorm(v, 0, v.getDimensionality(), 0.)); + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Optimization for the simplest case - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if(v1 != null) { + if(v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } + else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } + else { + if(v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } + else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); } } - // TODO: optimize for more simpler cases: obj vs. rect? - final int dim = dimensionality(mbr1, mbr2, weights.length); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double diff; - if (mbr1.getMax(d) < mbr2.getMin(d)) { - diff = mbr2.getMin(d) - mbr1.getMax(d); - } else if (mbr1.getMin(d) > mbr2.getMax(d)) { - diff = mbr1.getMin(d) - mbr2.getMax(d); - } else { // The mbrs intersect! - continue; - } - agg += diff * diff * weights[d]; + // first object has more dimensions. + if(dim1 > mindim) { + if(v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); + } + } + // second object has more dimensions. + if(dim2 > mindim) { + if(v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); + } } return Math.sqrt(agg); } @Override public boolean equals(Object obj) { - if (this == obj) { + if(this == obj) { return true; } - if (obj == null) { + if(obj == null) { return false; } - if (!(obj instanceof WeightedEuclideanDistanceFunction)) { - if (obj.getClass().equals(WeightedLPNormDistanceFunction.class)) { + if(!(obj instanceof WeightedEuclideanDistanceFunction)) { + if(obj.getClass().equals(WeightedLPNormDistanceFunction.class)) { return super.equals(obj); } - if (obj.getClass().equals(EuclideanDistanceFunction.class)) { - for (double d : weights) { - if (d != 1.0) { + if(obj.getClass().equals(EuclideanDistanceFunction.class)) { + for(double d : weights) { + if(d != 1.0) { return false; } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedLPNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedLPNormDistanceFunction.java index 3d49c95a..48a9c5a2 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedLPNormDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedLPNormDistanceFunction.java @@ -27,13 +27,14 @@ import java.util.Arrays; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; +import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; /** * Weighted version of the Minkowski L_p metrics distance function. * * @author Erich Schubert */ -// TODO: make parameterizable; add optimized variants public class WeightedLPNormDistanceFunction extends LPNormDistanceFunction { /** * Weight array @@ -51,49 +52,119 @@ public class WeightedLPNormDistanceFunction extends LPNormDistanceFunction { this.weights = weights; } + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); + final double delta = (xd >= yd) ? xd - yd : yd - xd; + agg += Math.pow(delta, p) * weights[d]; + } + return agg; + } + + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if (delta < 0.) { + delta = value - mbr.getMax(d); + } + if (delta > 0.) { + agg += Math.pow(delta, p) * weights[d]; + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if (delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if (delta > 0.) { + agg += Math.pow(delta, p) * weights[d]; + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + final double xd = v.doubleValue(d); + final double delta = xd >= 0. ? xd : -xd; + agg += Math.pow(delta, p) * weights[d]; + } + return agg; + } + + private final double doublePreNormMBR(SpatialComparable mbr, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if (delta < 0.) { + delta = -mbr.getMax(d); + } + if (delta > 0.) { + agg += Math.pow(delta, p) * weights[d]; + } + } + return agg; + } + @Override public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2, weights.length); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double delta = Math.abs(v1.doubleValue(d) - v2.doubleValue(d)); - agg += Math.pow(delta, p) * weights[d]; + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if (dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else if (dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); } return Math.pow(agg, invp); } @Override public double doubleNorm(NumberVector<?> v) { - final int dim = v.getDimensionality(); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double delta = Math.abs(v.doubleValue(d)); - agg += Math.pow(delta, p) * weights[d]; - } - return Math.pow(agg, invp); + return Math.pow(doublePreNorm(v, 0, v.getDimensionality(), 0.), invp); } @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Optimization for the simplest case - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if (v1 != null) { + if (v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } else { + if (v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); + } + } + // first object has more dimensions. + if (dim1 > mindim) { + if (v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); } } - // TODO: optimize for more simpler cases: obj vs. rect? - final int dim = dimensionality(mbr1, mbr2, weights.length); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double diff; - if (mbr1.getMax(d) < mbr2.getMin(d)) { - diff = mbr2.getMin(d) - mbr1.getMax(d); - } else if (mbr1.getMin(d) > mbr2.getMax(d)) { - diff = mbr1.getMin(d) - mbr2.getMax(d); - } else { // The mbrs intersect! - continue; + // second object has more dimensions. + if (dim2 > mindim) { + if (v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); } - agg += Math.pow(diff, p) * weights[d]; } return Math.pow(agg, invp); } @@ -109,7 +180,7 @@ public class WeightedLPNormDistanceFunction extends LPNormDistanceFunction { if (!(obj instanceof WeightedLPNormDistanceFunction)) { if (obj instanceof LPNormDistanceFunction && super.equals(obj)) { for (double d : weights) { - if (d != 1.0) { + if (d != 1.) { return false; } } @@ -120,4 +191,9 @@ public class WeightedLPNormDistanceFunction extends LPNormDistanceFunction { WeightedLPNormDistanceFunction other = (WeightedLPNormDistanceFunction) obj; return Arrays.equals(this.weights, other.weights); } + + @Override + public SimpleTypeInformation<? super NumberVector<?>> getInputTypeRestriction() { + return new VectorFieldTypeInformation<>(NumberVector.class, 0, weights.length); + } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedManhattanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedManhattanDistanceFunction.java index 186f0435..b419f0df 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedManhattanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedManhattanDistanceFunction.java @@ -40,52 +40,122 @@ public class WeightedManhattanDistanceFunction extends WeightedLPNormDistanceFun * @param weights Weight vector */ public WeightedManhattanDistanceFunction(double[] weights) { - super(1.0, weights); + super(1., weights); } - @Override - public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - final int dim = dimensionality(v1, v2, weights.length); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double delta = Math.abs(v1.doubleValue(d) - v2.doubleValue(d)); + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); + final double delta = (xd >= yd) ? xd - yd : yd - xd; agg += delta * weights[d]; } return agg; } - @Override - public double doubleNorm(NumberVector<?> v) { - final int dim = v.getDimensionality(); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double delta = Math.abs(v.doubleValue(d)); + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if (delta < 0.) { + delta = value - mbr.getMax(d); + } + if (delta > 0.) { + agg += delta * weights[d]; + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if (delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + if (delta > 0.) { + agg += delta * weights[d]; + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + final double xd = v.doubleValue(d); + final double delta = xd >= 0. ? xd : -xd; agg += delta * weights[d]; } return agg; } + private final double doublePreNormMBR(SpatialComparable mbr, final int start, final int end, double agg) { + for (int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if (delta < 0.) { + delta = -mbr.getMax(d); + } + if (delta > 0.) { + agg += delta * weights[d]; + } + } + return agg; + } + + @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if (dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else if (dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + return agg; + } + + @Override + public double doubleNorm(NumberVector<?> v) { + return doublePreNorm(v, 0, v.getDimensionality(), 0.); + } + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - // Optimization for the simplest case - if (mbr1 instanceof NumberVector) { - if (mbr2 instanceof NumberVector) { - return doubleDistance((NumberVector<?>) mbr1, (NumberVector<?>) mbr2); + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if (v1 != null) { + if (v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } else { + if (v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); + } + } + // first object has more dimensions. + if (dim1 > mindim) { + if (v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); } } - // TODO: optimize for more simpler cases: obj vs. rect? - final int dim = dimensionality(mbr1, mbr2, weights.length); - double agg = 0; - for (int d = 0; d < dim; d++) { - final double diff; - if (mbr1.getMax(d) < mbr2.getMin(d)) { - diff = mbr2.getMin(d) - mbr1.getMax(d); - } else if (mbr1.getMin(d) > mbr2.getMax(d)) { - diff = mbr1.getMin(d) - mbr2.getMax(d); - } else { // The mbrs intersect! - continue; + // second object has more dimensions. + if (dim2 > mindim) { + if (v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); } - agg += diff * weights[d]; } return agg; } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedMaximumDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedMaximumDistanceFunction.java new file mode 100644 index 00000000..c97848dd --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/WeightedMaximumDistanceFunction.java @@ -0,0 +1,193 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.Arrays; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; + +/** + * Weighted version of the Minkowski L_p metrics distance function. + * + * @author Erich Schubert + */ +public class WeightedMaximumDistanceFunction extends WeightedLPNormDistanceFunction { + /** + * Constructor. + * + * @param weights Weight vector + */ + public WeightedMaximumDistanceFunction(double[] weights) { + super(Double.POSITIVE_INFINITY, weights); + } + + private final double doublePreDistance(NumberVector<?> v1, NumberVector<?> v2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v1.doubleValue(d), yd = v2.doubleValue(d); + final double delta = ((xd >= yd) ? xd - yd : yd - xd) * weights[d]; + if(delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreDistanceVM(NumberVector<?> v, SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double value = v.doubleValue(d), min = mbr.getMin(d); + double delta = min - value; + if(delta < 0.) { + delta = value - mbr.getMax(d); + } + delta *= weights[d]; + if(delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreDistanceMBR(SpatialComparable mbr1, SpatialComparable mbr2, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr2.getMin(d) - mbr1.getMax(d); + if(delta < 0.) { + delta = mbr1.getMin(d) - mbr2.getMax(d); + } + delta *= weights[d]; + if(delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreNorm(NumberVector<?> v, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + final double xd = v.doubleValue(d); + final double delta = (xd >= 0. ? xd : -xd) * weights[d]; + if(delta > agg) { + agg = delta; + } + } + return agg; + } + + private final double doublePreNormMBR(SpatialComparable mbr, final int start, final int end, double agg) { + for(int d = start; d < end; d++) { + double delta = mbr.getMin(d); + if(delta < 0.) { + delta = -mbr.getMax(d); + } + delta *= weights[d]; + if(delta > agg) { + agg = delta; + } + } + return agg; + } + + @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + final int dim1 = v1.getDimensionality(), dim2 = v2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + double agg = doublePreDistance(v1, v2, 0, mindim, 0.); + if(dim1 > mindim) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else if(dim2 > mindim) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + return agg; + } + + @Override + public double doubleNorm(NumberVector<?> v) { + return doublePreNorm(v, 0, v.getDimensionality(), 0.); + } + + @Override + public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { + final int dim1 = mbr1.getDimensionality(), dim2 = mbr2.getDimensionality(); + final int mindim = (dim1 < dim2) ? dim1 : dim2; + + final NumberVector<?> v1 = (mbr1 instanceof NumberVector) ? (NumberVector<?>) mbr1 : null; + final NumberVector<?> v2 = (mbr2 instanceof NumberVector) ? (NumberVector<?>) mbr2 : null; + + double agg = 0.; + if(v1 != null) { + if(v2 != null) { + agg = doublePreDistance(v1, v2, 0, mindim, agg); + } + else { + agg = doublePreDistanceVM(v1, mbr2, 0, mindim, agg); + } + } + else { + if(v2 != null) { + agg = doublePreDistanceVM(v2, mbr1, 0, mindim, agg); + } + else { + agg = doublePreDistanceMBR(mbr1, mbr2, 0, mindim, agg); + } + } + // first object has more dimensions. + if(dim1 > mindim) { + if(v1 != null) { + agg = doublePreNorm(v1, mindim, dim1, agg); + } + else { + agg = doublePreNormMBR(v1, mindim, dim1, agg); + } + } + // second object has more dimensions. + if(dim2 > mindim) { + if(v2 != null) { + agg = doublePreNorm(v2, mindim, dim2, agg); + } + else { + agg = doublePreNormMBR(mbr2, mindim, dim2, agg); + } + } + return agg; + } + + @Override + public boolean equals(Object obj) { + if(this == obj) { + return true; + } + if(obj == null) { + return false; + } + if(!(obj instanceof WeightedMaximumDistanceFunction)) { + if(obj instanceof WeightedLPNormDistanceFunction) { + return super.equals(obj); + } + return false; + } + WeightedMaximumDistanceFunction other = (WeightedMaximumDistanceFunction) obj; + return Arrays.equals(this.weights, other.weights); + } +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/probabilistic/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/probabilistic/package-info.java index 335c6ae0..7a6f705c 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/probabilistic/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/probabilistic/package-info.java @@ -3,4 +3,27 @@ * * @author Erich Schubert */ + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ package de.lmu.ifi.dbs.elki.distance.distancefunction.probabilistic;
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractDimensionsSelectingDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractDimensionsSelectingDoubleDistanceFunction.java index 25cb6407..052e089c 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractDimensionsSelectingDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractDimensionsSelectingDoubleDistanceFunction.java @@ -31,8 +31,7 @@ import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDoubleDistanceFunc import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.ListEachConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntListParameter; @@ -87,10 +86,10 @@ public abstract class AbstractDimensionsSelectingDoubleDistanceFunction<V extend @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } return this.dimensions.equals(((AbstractDimensionsSelectingDoubleDistanceFunction<?>) obj).dimensions); @@ -111,10 +110,10 @@ public abstract class AbstractDimensionsSelectingDoubleDistanceFunction<V extend super.makeOptions(config); dimensions = new BitSet(); final IntListParameter dimsP = new IntListParameter(DIMS_ID); - dimsP.addConstraint(new ListEachConstraint<Integer>(new GreaterEqualConstraint(0))); + dimsP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_INT_LIST); dimsP.setOptional(true); - if (config.grab(dimsP)) { - for (int d : dimsP.getValue()) { + if(config.grab(dimsP)) { + for(int d : dimsP.getValue()) { dimensions.set(d); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractPreferenceVectorBasedCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractPreferenceVectorBasedCorrelationDistanceFunction.java index f3a07639..20ee637e 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractPreferenceVectorBasedCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/AbstractPreferenceVectorBasedCorrelationDistanceFunction.java @@ -34,7 +34,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.PreferenceVectorBasedCorrelati import de.lmu.ifi.dbs.elki.index.IndexFactory; import de.lmu.ifi.dbs.elki.index.preprocessed.preference.PreferenceVectorIndex; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -222,7 +222,7 @@ public abstract class AbstractPreferenceVectorBasedCorrelationDistanceFunction<V protected void configEpsilon(Parameterization config) { final DoubleParameter epsilonP = new DoubleParameter(EPSILON_ID, 0.001); - epsilonP.addConstraint(new GreaterEqualConstraint(0)); + epsilonP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); if (config.grab(epsilonP)) { epsilon = epsilonP.doubleValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingDistanceFunction.java index fe593f0a..5fbe1c73 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingDistanceFunction.java @@ -33,7 +33,7 @@ import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractSpatialDoubleDistan import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; @@ -75,7 +75,7 @@ public class DimensionSelectingDistanceFunction extends AbstractSpatialDoubleDis */ @Override public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { - if (dim >= v1.getDimensionality() || dim >= v2.getDimensionality() || dim < 0) { + if(dim >= v1.getDimensionality() || dim >= v2.getDimensionality() || dim < 0) { throw new IllegalArgumentException("Specified dimension to be considered " + "is larger that dimensionality of FeatureVectors:" + "\n first argument: " + v1.toString() + "\n second argument: " + v2.toString() + "\n dimension: " + dim); } @@ -85,18 +85,20 @@ public class DimensionSelectingDistanceFunction extends AbstractSpatialDoubleDis @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { - if (dim >= mbr1.getDimensionality() || dim >= mbr2.getDimensionality() || dim < 0) { + if(dim >= mbr1.getDimensionality() || dim >= mbr2.getDimensionality() || dim < 0) { throw new IllegalArgumentException("Specified dimension to be considered " + "is larger that dimensionality of FeatureVectors:" + "\n first argument: " + mbr1.toString() + "\n second argument: " + mbr2.toString() + "\n dimension: " + dim); } double m1, m2; - if (mbr1.getMax(dim) < mbr2.getMin(dim)) { + if(mbr1.getMax(dim) < mbr2.getMin(dim)) { m1 = mbr1.getMax(dim); m2 = mbr2.getMin(dim); - } else if (mbr1.getMin(dim) > mbr2.getMax(dim)) { + } + else if(mbr1.getMin(dim) > mbr2.getMax(dim)) { m1 = mbr1.getMin(dim); m2 = mbr2.getMax(dim); - } else { // The mbrs intersect! + } + else { // The mbrs intersect! m1 = 0; m2 = 0; } @@ -130,10 +132,10 @@ public class DimensionSelectingDistanceFunction extends AbstractSpatialDoubleDis @Override public void setSelectedDimensions(BitSet dimensions) { dim = dimensions.nextSetBit(0); - if (dim == -1) { + if(dim == -1) { throw new IllegalStateException("No dimension was set."); } - if (dimensions.nextSetBit(dim + 1) > 0) { + if(dimensions.nextSetBit(dim + 1) > 0) { throw new IllegalStateException("More than one dimension was set."); } } @@ -150,10 +152,10 @@ public class DimensionSelectingDistanceFunction extends AbstractSpatialDoubleDis @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } return this.dim == ((DimensionSelectingDistanceFunction) obj).dim; @@ -173,8 +175,8 @@ public class DimensionSelectingDistanceFunction extends AbstractSpatialDoubleDis protected void makeOptions(Parameterization config) { super.makeOptions(config); final IntParameter dimP = new IntParameter(DIM_ID); - dimP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(dimP)) { + dimP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_INT); + if(config.grab(dimP)) { dim = dimP.getValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceLPNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceLPNormDistanceFunction.java index 2fbdf876..6c9579ad 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceLPNormDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceLPNormDistanceFunction.java @@ -32,10 +32,11 @@ import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; import de.lmu.ifi.dbs.elki.database.query.distance.SpatialPrimitiveDistanceQuery; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancefunction.DoubleNorm; +import de.lmu.ifi.dbs.elki.distance.distancefunction.NumberVectorDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.LPNormDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -45,7 +46,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; * * @author Elke Achtert */ -public class SubspaceLPNormDistanceFunction extends AbstractDimensionsSelectingDoubleDistanceFunction<NumberVector<?>> implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?>>, DoubleNorm<NumberVector<?>> { +public class SubspaceLPNormDistanceFunction extends AbstractDimensionsSelectingDoubleDistanceFunction<NumberVector<?>> implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?>>, DoubleNorm<NumberVector<?>>, NumberVectorDistanceFunction<DoubleDistance> { /** * Value of p */ @@ -200,7 +201,7 @@ public class SubspaceLPNormDistanceFunction extends AbstractDimensionsSelectingD @Override protected void makeOptions(Parameterization config) { final DoubleParameter paramP = new DoubleParameter(LPNormDistanceFunction.P_ID); - paramP.addConstraint(new GreaterConstraint(0)); + paramP.addConstraint(CommonConstraints.GREATER_THAN_ZERO_DOUBLE); if(config.grab(paramP)) { p = paramP.getValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceMaximumDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceMaximumDistanceFunction.java new file mode 100644 index 00000000..60791159 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceMaximumDistanceFunction.java @@ -0,0 +1,149 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction.subspace; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2013 + Ludwig-Maximilians-Universität München + Lehr- und Forschungseinheit für Datenbanksysteme + ELKI Development Team + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU Affero 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 Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +import java.util.BitSet; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; + +/** + * Provides a distance function that computes the Euclidean distance between + * feature vectors only in specified dimensions. + * + * @author Elke Achtert + */ +public class SubspaceMaximumDistanceFunction extends SubspaceLPNormDistanceFunction { + /** + * Constructor. + * + * @param dimensions Selected dimensions + */ + public SubspaceMaximumDistanceFunction(BitSet dimensions) { + super(1.0, dimensions); + } + + /** + * Provides the Euclidean distance between two given feature vectors in the + * selected dimensions. + * + * @param v1 first feature vector + * @param v2 second feature vector + * @return the Euclidean distance between two given feature vectors in the + * selected dimensions + */ + @Override + public double doubleDistance(NumberVector<?> v1, NumberVector<?> v2) { + if (v1.getDimensionality() != v2.getDimensionality()) { + throw new IllegalArgumentException("Different dimensionality of FeatureVectors\n " + "first argument: " + v1 + "\n " + "second argument: " + v2); + } + + double agg = 0.; + for (int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + double v = Math.abs(v1.doubleValue(d) - v2.doubleValue(d)); + if (v > agg) { + agg = v; + } + } + return agg; + } + + @Override + protected double doubleMinDistObject(SpatialComparable mbr, NumberVector<?> v) { + if (mbr.getDimensionality() != v.getDimensionality()) { + throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr.toString() + "\n " + "second argument: " + v.toString()); + } + + double agg = 0.; + for (int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double value = v.doubleValue(d); + final double omin = mbr.getMin(d); + final double diff1 = omin - value; + if (diff1 > 0.) { + if (diff1 > agg) { + agg = diff1; + } + } else { + final double omax = mbr.getMax(d); + final double diff2 = value - omax; + if (diff2 > agg) { + agg = diff2; + } + } + } + return agg; + } + + @Override + public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { + if (mbr1.getDimensionality() != mbr2.getDimensionality()) { + throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr1.toString() + "\n " + "second argument: " + mbr2.toString()); + } + double agg = 0.; + for (int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double max1 = mbr1.getMax(d); + final double min2 = mbr2.getMin(d); + if (max1 < min2) { + double v = min2 - max1; + if (v > agg) { + agg = v; + } + } else { + final double min1 = mbr1.getMin(d); + final double max2 = mbr2.getMax(d); + double v = min1 - max2; + if (v > agg) { + agg = v; + } + } + } + return agg; + } + + @Override + public double doubleNorm(NumberVector<?> obj) { + double agg = 0.; + for (int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + double v = Math.abs(obj.doubleValue(d)); + if (v > agg) { + agg = v; + } + } + return agg; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractDimensionsSelectingDoubleDistanceFunction.Parameterizer { + @Override + protected SubspaceMaximumDistanceFunction makeInstance() { + return new SubspaceMaximumDistanceFunction(dimensions); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java index 76630586..c6a35985 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java @@ -29,8 +29,7 @@ import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractVectorDoubleDistanceFunction; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -68,10 +67,10 @@ public abstract class AbstractEditDistanceFunction extends AbstractVectorDoubleD @Override public boolean equals(Object obj) { - if (obj == null) { + if(obj == null) { return false; } - if (!this.getClass().equals(obj.getClass())) { + if(!this.getClass().equals(obj.getClass())) { return false; } return this.bandSize == ((AbstractEditDistanceFunction) obj).bandSize; @@ -91,9 +90,9 @@ public abstract class AbstractEditDistanceFunction extends AbstractVectorDoubleD protected void makeOptions(Parameterization config) { super.makeOptions(config); final DoubleParameter bandSizeP = new DoubleParameter(BANDSIZE_ID, 0.1); - bandSizeP.addConstraint(new GreaterEqualConstraint(0)); - bandSizeP.addConstraint(new LessEqualConstraint(1)); - if (config.grab(bandSizeP)) { + bandSizeP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + bandSizeP.addConstraint(CommonConstraints.LESS_EQUAL_ONE_DOUBLE); + if(config.grab(bandSizeP)) { bandSize = bandSizeP.doubleValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java index 0e38d8bd..d48a21f0 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java @@ -28,7 +28,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.documentation.Title; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -82,7 +82,7 @@ public class EDRDistanceFunction extends AbstractEditDistanceFunction { // features2.length + ", band: " + band); final double deltaValue = delta; - for (int i = 0; i < v1.getDimensionality(); i++) { + for(int i = 0; i < v1.getDimensionality(); i++) { // Swap current and prev arrays. We'll just overwrite the new curr. { double[] temp = prev; @@ -90,16 +90,16 @@ public class EDRDistanceFunction extends AbstractEditDistanceFunction { curr = temp; } int l = i - (band + 1); - if (l < 0) { + if(l < 0) { l = 0; } int r = i + (band + 1); - if (r > (v2.getDimensionality() - 1)) { + if(r > (v2.getDimensionality() - 1)) { r = (v2.getDimensionality() - 1); } - for (int j = l; j <= r; j++) { - if (Math.abs(i - j) <= band) { + for(int j = l; j <= r; j++) { + if(Math.abs(i - j) <= band) { // compute squared distance double val1 = v1.doubleValue(i); double val2 = v2.doubleValue(j); @@ -110,23 +110,27 @@ public class EDRDistanceFunction extends AbstractEditDistanceFunction { final double subcost = (d <= deltaValue) ? 0 : 1; - if ((i + j) != 0) { - if ((i == 0) || ((j != 0) && (((prev[j - 1] + subcost) > (curr[j - 1] + 1)) && ((curr[j - 1] + 1) < (prev[j] + 1))))) { + if((i + j) != 0) { + if((i == 0) || ((j != 0) && (((prev[j - 1] + subcost) > (curr[j - 1] + 1)) && ((curr[j - 1] + 1) < (prev[j] + 1))))) { // del cost = curr[j - 1] + 1; - } else if ((j == 0) || ((i != 0) && (((prev[j - 1] + subcost) > (prev[j] + 1)) && ((prev[j] + 1) < (curr[j - 1] + 1))))) { + } + else if((j == 0) || ((i != 0) && (((prev[j - 1] + subcost) > (prev[j] + 1)) && ((prev[j] + 1) < (curr[j - 1] + 1))))) { // ins cost = prev[j] + 1; - } else { + } + else { // match cost = prev[j - 1] + subcost; } - } else { + } + else { cost = 0; } curr[j] = cost; - } else { + } + else { curr[j] = Double.POSITIVE_INFINITY; // outside band } } @@ -137,7 +141,7 @@ public class EDRDistanceFunction extends AbstractEditDistanceFunction { @Override public boolean equals(Object obj) { - if (!super.equals(obj)) { + if(!super.equals(obj)) { return false; } return this.delta == ((EDRDistanceFunction) obj).delta; @@ -157,8 +161,8 @@ public class EDRDistanceFunction extends AbstractEditDistanceFunction { protected void makeOptions(Parameterization config) { super.makeOptions(config); final DoubleParameter deltaP = new DoubleParameter(DELTA_ID, 1.0); - deltaP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(deltaP)) { + deltaP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(deltaP)) { delta = deltaP.doubleValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java index fd5bb61c..e7d7dd7e 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java @@ -28,7 +28,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.documentation.Title; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -78,7 +78,7 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { // bandsize is the maximum allowed distance to the diagonal final int band = (int) Math.ceil(v2.getDimensionality() * bandSize); - for (int i = 0; i < v1.getDimensionality(); i++) { + for(int i = 0; i < v1.getDimensionality(); i++) { // Swap current and prev arrays. We'll just overwrite the new curr. { double[] temp = prev; @@ -86,16 +86,16 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { curr = temp; } int l = i - (band + 1); - if (l < 0) { + if(l < 0) { l = 0; } int r = i + (band + 1); - if (r > (v2.getDimensionality() - 1)) { + if(r > (v2.getDimensionality() - 1)) { r = (v2.getDimensionality() - 1); } - for (int j = l; j <= r; j++) { - if (Math.abs(i - j) <= band) { + for(int j = l; j <= r; j++) { + if(Math.abs(i - j) <= band) { // compute squared distance of feature vectors double val1 = v1.doubleValue(i); double val2 = g; @@ -118,24 +118,28 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { final double cost; - if ((i + j) != 0) { - if ((i == 0) || ((j != 0) && (((prev[j - 1] + dist12) > (curr[j - 1] + dist2)) && ((curr[j - 1] + dist2) < (prev[j] + dist1))))) { + if((i + j) != 0) { + if((i == 0) || ((j != 0) && (((prev[j - 1] + dist12) > (curr[j - 1] + dist2)) && ((curr[j - 1] + dist2) < (prev[j] + dist1))))) { // del cost = curr[j - 1] + dist2; - } else if ((j == 0) || ((i != 0) && (((prev[j - 1] + dist12) > (prev[j] + dist1)) && ((prev[j] + dist1) < (curr[j - 1] + dist2))))) { + } + else if((j == 0) || ((i != 0) && (((prev[j - 1] + dist12) > (prev[j] + dist1)) && ((prev[j] + dist1) < (curr[j - 1] + dist2))))) { // ins cost = prev[j] + dist1; - } else { + } + else { // match cost = prev[j - 1] + dist12; } - } else { + } + else { cost = 0; } curr[j] = cost; // steps[i][j] = step; - } else { + } + else { curr[j] = Double.POSITIVE_INFINITY; // outside band } } @@ -146,7 +150,7 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { @Override public boolean equals(Object obj) { - if (!super.equals(obj)) { + if(!super.equals(obj)) { return false; } return this.g == ((ERPDistanceFunction) obj).g; @@ -166,8 +170,8 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { protected void makeOptions(Parameterization config) { super.makeOptions(config); final DoubleParameter gP = new DoubleParameter(G_ID, 0.0); - gP.addConstraint(new GreaterEqualConstraint(0)); - if (config.grab(gP)) { + gP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + if(config.grab(gP)) { g = gP.doubleValue(); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java index 2998248d..4f1c0850 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java @@ -34,8 +34,7 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.documentation.Title; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; -import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessEqualConstraint; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; @@ -219,15 +218,15 @@ public class LCSSDistanceFunction extends AbstractVectorDoubleDistanceFunction { protected void makeOptions(Parameterization config) { super.makeOptions(config); final DoubleParameter pDeltaP = new DoubleParameter(PDELTA_ID, 0.1); - pDeltaP.addConstraint(new GreaterEqualConstraint(0)); - pDeltaP.addConstraint(new LessEqualConstraint(1)); + pDeltaP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + pDeltaP.addConstraint(CommonConstraints.LESS_EQUAL_ONE_DOUBLE); if (config.grab(pDeltaP)) { pDelta = pDeltaP.doubleValue(); } final DoubleParameter pEpsilonP = new DoubleParameter(PEPSILON_ID, 0.05); - pEpsilonP.addConstraint(new GreaterEqualConstraint(0)); - pEpsilonP.addConstraint(new LessEqualConstraint(1)); + pEpsilonP.addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE); + pEpsilonP.addConstraint(CommonConstraints.LESS_EQUAL_ONE_DOUBLE); if (config.grab(pEpsilonP)) { pEpsilon = pEpsilonP.doubleValue(); } |