diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski')
13 files changed, 1362 insertions, 423 deletions
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); + } +} |