diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace')
11 files changed, 458 insertions, 119 deletions
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 a7204562..b58979ef 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 @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -42,7 +42,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntListParameter; * @author Elke Achtert * @param <V> the type of FeatureVector to compute the distances in between */ -public abstract class AbstractDimensionsSelectingDoubleDistanceFunction<V extends FeatureVector<?, ?>> extends AbstractPrimitiveDistanceFunction<V, DoubleDistance> implements PrimitiveDoubleDistanceFunction<V> { +public abstract class AbstractDimensionsSelectingDoubleDistanceFunction<V extends FeatureVector<?, ?>> extends AbstractPrimitiveDistanceFunction<V, DoubleDistance> implements PrimitiveDoubleDistanceFunction<V>, DimensionSelectingSubspaceDistanceFunction<V, DoubleDistance> { /** * Dimensions parameter. */ @@ -51,7 +51,7 @@ public abstract class AbstractDimensionsSelectingDoubleDistanceFunction<V extend /** * The dimensions to be considered for distance computation. */ - private BitSet dimensions; + protected BitSet dimensions; /** * Constructor. @@ -68,22 +68,12 @@ public abstract class AbstractDimensionsSelectingDoubleDistanceFunction<V extend return new DoubleDistance(doubleDistance(o1, o2)); } - /** - * Returns a bit set representing the selected dimensions. - * - * @return a bit set representing the selected dimensions - */ + @Override public BitSet getSelectedDimensions() { - BitSet dimensions = new BitSet(this.dimensions.size()); - dimensions.or(this.dimensions); return dimensions; } - /** - * Sets the selected dimensions according to the set bits in the given BitSet. - * - * @param dimensions a BitSet designating the new selected dimensions - */ + @Override public void setSelectedDimensions(BitSet dimensions) { this.dimensions.clear(); this.dimensions.or(dimensions); 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 3d6aab90..8b5f526e 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 @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DiSHDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DiSHDistanceFunction.java index 8a58261d..f0eb8289 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DiSHDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DiSHDistanceFunction.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team 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 83df84f1..382167e9 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 @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -108,20 +108,6 @@ public class DimensionSelectingDistanceFunction extends AbstractPrimitiveDistanc } @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - if(dim > mbr1.getDimensionality() || dim > mbr2.getDimensionality()) { - 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 c1 = (mbr1.getMin(dim) + mbr1.getMax(dim)) / 2; - double c2 = (mbr2.getMin(dim) + mbr2.getMax(dim)) / 2; - - double manhattan = c1 - c2; - - return Math.abs(manhattan); - } - - @Override public DoubleDistance distance(NumberVector<?, ?> o1, NumberVector<?, ?> o2) { return new DoubleDistance(doubleDistance(o1, o2)); } @@ -131,11 +117,6 @@ public class DimensionSelectingDistanceFunction extends AbstractPrimitiveDistanc return new DoubleDistance(doubleMinDist(mbr1, mbr2)); } - @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - /** * Returns the selected dimension. * diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingSubspaceDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingSubspaceDistanceFunction.java new file mode 100644 index 00000000..acc24bf7 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionSelectingSubspaceDistanceFunction.java @@ -0,0 +1,52 @@ +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) 2012 + 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.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; + +/** + * Interface for dimension selecting subspace distance functions. + * + * @author Erich Schubert + * + * @param <O> Object type + * @param <D> Distance value + */ +public interface DimensionSelectingSubspaceDistanceFunction<O, D extends Distance<D>> extends DistanceFunction<O, D> { + /** + * Returns a bit set representing the selected dimensions. + * + * @return a bit set representing the selected dimensions + */ + public BitSet getSelectedDimensions(); + + /** + * Sets the selected dimensions according to the set bits in the given BitSet. + * + * @param dimensions a BitSet designating the new selected dimensions + */ + public void setSelectedDimensions(BitSet dimensions); +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/HiSCDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/HiSCDistanceFunction.java index dc8c01b2..4835a6c6 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/HiSCDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/HiSCDistanceFunction.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/LocalSubspaceDistanceFunction.java index 1afced55..b7d36264 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/LocalSubspaceDistanceFunction.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -48,13 +48,13 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameteriz * * @apiviz.has Instance */ -public class SubspaceDistanceFunction extends AbstractIndexBasedDistanceFunction<NumberVector<?, ?>, FilteredLocalPCAIndex<NumberVector<?, ?>>, SubspaceDistance> implements FilteredLocalPCABasedDistanceFunction<NumberVector<?, ?>, FilteredLocalPCAIndex<NumberVector<?, ?>>, SubspaceDistance> { +public class LocalSubspaceDistanceFunction extends AbstractIndexBasedDistanceFunction<NumberVector<?, ?>, FilteredLocalPCAIndex<NumberVector<?, ?>>, SubspaceDistance> implements FilteredLocalPCABasedDistanceFunction<NumberVector<?, ?>, FilteredLocalPCAIndex<NumberVector<?, ?>>, SubspaceDistance> { /** * Constructor * * @param indexFactory Index factory */ - public SubspaceDistanceFunction(IndexFactory<NumberVector<?, ?>, FilteredLocalPCAIndex<NumberVector<?, ?>>> indexFactory) { + public LocalSubspaceDistanceFunction(IndexFactory<NumberVector<?, ?>, FilteredLocalPCAIndex<NumberVector<?, ?>>> indexFactory) { super(indexFactory); } @@ -76,12 +76,12 @@ public class SubspaceDistanceFunction extends AbstractIndexBasedDistanceFunction * * @author Erich Schubert */ - public static class Instance<V extends NumberVector<?, ?>> extends AbstractIndexBasedDistanceFunction.Instance<V, FilteredLocalPCAIndex<V>, SubspaceDistance, SubspaceDistanceFunction> implements FilteredLocalPCABasedDistanceFunction.Instance<V, FilteredLocalPCAIndex<V>, SubspaceDistance> { + public static class Instance<V extends NumberVector<?, ?>> extends AbstractIndexBasedDistanceFunction.Instance<V, FilteredLocalPCAIndex<V>, SubspaceDistance, LocalSubspaceDistanceFunction> implements FilteredLocalPCABasedDistanceFunction.Instance<V, FilteredLocalPCAIndex<V>, SubspaceDistance> { /** * @param database Database * @param index Index */ - public Instance(Relation<V> database, FilteredLocalPCAIndex<V> index, SubspaceDistanceFunction distanceFunction) { + public Instance(Relation<V> database, FilteredLocalPCAIndex<V> index, LocalSubspaceDistanceFunction distanceFunction) { super(database, index, distanceFunction); } @@ -145,8 +145,8 @@ public class SubspaceDistanceFunction extends AbstractIndexBasedDistanceFunction } @Override - protected SubspaceDistanceFunction makeInstance() { - return new SubspaceDistanceFunction(factory); + protected LocalSubspaceDistanceFunction makeInstance() { + return new LocalSubspaceDistanceFunction(factory); } } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceEuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceEuclideanDistanceFunction.java new file mode 100644 index 00000000..6330ed34 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceEuclideanDistanceFunction.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) 2012 + 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 SubspaceEuclideanDistanceFunction extends SubspaceLPNormDistanceFunction { + /** + * Constructor. + * + * @param dimensions Selected dimensions + */ + public SubspaceEuclideanDistanceFunction(BitSet dimensions) { + super(2.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 sqrDist = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double delta = v1.doubleValue(d + 1) - v2.doubleValue(d + 1); + sqrDist += delta * delta; + } + return Math.sqrt(sqrDist); + } + + @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 sqrDist = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double delta; + final double value = v.doubleValue(d + 1); + final double omin = mbr.getMin(d + 1); + if(value < omin) { + delta = omin - value; + } + else { + final double omax = mbr.getMax(d + 1); + if(value > omax) { + delta = value - omax; + } + else { + continue; + } + } + sqrDist += delta * delta; + } + return Math.sqrt(sqrDist); + } + + @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 sqrDist = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double delta; + final double max1 = mbr1.getMax(d + 1); + final double min2 = mbr2.getMin(d + 1); + if(max1 < min2) { + delta = min2 - max1; + } + else { + final double min1 = mbr1.getMin(d + 1); + final double max2 = mbr2.getMax(d + 1); + if(min1 > max2) { + delta = min1 - max2; + } + else { // The mbrs intersect! + continue; + } + } + sqrDist += delta * delta; + } + return Math.sqrt(sqrDist); + } + + @Override + public double doubleNorm(NumberVector<?, ?> obj) { + double sqrDist = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double delta = obj.doubleValue(d + 1); + sqrDist += delta * delta; + } + return Math.sqrt(sqrDist); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractDimensionsSelectingDoubleDistanceFunction.Parameterizer { + @Override + protected SubspaceEuclideanDistanceFunction makeInstance() { + return new SubspaceEuclideanDistanceFunction(dimensions); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionsSelectingEuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceLPNormDistanceFunction.java index b9f52de9..7904c333 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/DimensionsSelectingEuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceLPNormDistanceFunction.java @@ -4,7 +4,7 @@ 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) 2011 + Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team @@ -31,8 +31,13 @@ import de.lmu.ifi.dbs.elki.data.type.TypeUtil; 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.LPNormDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDoubleDistanceFunction; 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.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; /** * Provides a distance function that computes the Euclidean distance between @@ -40,14 +45,30 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; * * @author Elke Achtert */ -public class DimensionsSelectingEuclideanDistanceFunction extends AbstractDimensionsSelectingDoubleDistanceFunction<NumberVector<?, ?>> implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { +public class SubspaceLPNormDistanceFunction extends AbstractDimensionsSelectingDoubleDistanceFunction<NumberVector<?, ?>> implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>>, DoubleNorm<NumberVector<?, ?>> { + /** + * Value of p + */ + private double p; + /** * Constructor. * * @param dimensions Selected dimensions + * @param p p value */ - public DimensionsSelectingEuclideanDistanceFunction(BitSet dimensions) { + public SubspaceLPNormDistanceFunction(double p, BitSet dimensions) { super(dimensions); + this.p = p; + } + + /** + * Get the value of p. + * + * @return p + */ + public double getP() { + return p; } /** @@ -65,44 +86,39 @@ public class DimensionsSelectingEuclideanDistanceFunction extends AbstractDimens throw new IllegalArgumentException("Different dimensionality of FeatureVectors\n " + "first argument: " + v1 + "\n " + "second argument: " + v2); } - if(v1.getDimensionality() < getSelectedDimensions().cardinality()) { - throw new IllegalArgumentException("The dimensionality of the feature space " + "is not consistent with the specified dimensions " + "to be considered for distance computation.\n " + "dimensionality of the feature space: " + v1.getDimensionality() + "\n " + "specified dimensions: " + getSelectedDimensions()); - } - double sqrDist = 0; - for(int d = getSelectedDimensions().nextSetBit(0); d >= 0; d = getSelectedDimensions().nextSetBit(d + 1)) { - double manhattanI = v1.doubleValue(d + 1) - v2.doubleValue(d + 1); - sqrDist += manhattanI * manhattanI; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + double delta = Math.abs(v1.doubleValue(d + 1) - v2.doubleValue(d + 1)); + sqrDist += Math.pow(delta, p); } - return Math.sqrt(sqrDist); + return Math.pow(sqrDist, 1. / p); } 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()); } - if(v.getDimensionality() < getSelectedDimensions().size()) { - throw new IllegalArgumentException("The dimensionality of the feature space " + "is not consistent with the specified dimensions " + "to be considered for distance computation.\n " + "dimensionality of the feature space: " + v.getDimensionality() + "\n " + "specified dimensions: " + getSelectedDimensions()); - } double sqrDist = 0; - for(int d = getSelectedDimensions().nextSetBit(0); d >= 0; d = getSelectedDimensions().nextSetBit(d + 1)) { - double value = v.doubleValue(d); - double r; - if(value < mbr.getMin(d)) { - r = mbr.getMin(d); - } - else if(value > mbr.getMax(d)) { - r = mbr.getMax(d); + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double delta; + final double value = v.doubleValue(d + 1); + final double omin = mbr.getMin(d + 1); + if(value < omin) { + delta = omin - value; } else { - r = value; + final double omax = mbr.getMax(d + 1); + if(value > omax) { + delta = value - omax; + } + else { + continue; + } } - - double manhattanI = value - r; - sqrDist += manhattanI * manhattanI; + sqrDist += Math.pow(delta, p); } - return Math.sqrt(sqrDist); + return Math.pow(sqrDist, 1. / p); } @Override @@ -110,60 +126,54 @@ public class DimensionsSelectingEuclideanDistanceFunction extends AbstractDimens if(mbr1.getDimensionality() != mbr2.getDimensionality()) { throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr1.toString() + "\n " + "second argument: " + mbr2.toString()); } - if(mbr1.getDimensionality() < getSelectedDimensions().size()) { - throw new IllegalArgumentException("The dimensionality of the feature space " + "is not consistent with the specified dimensions " + "to be considered for distance computation.\n " + "dimensionality of the feature space: " + mbr1.getDimensionality() + "\n " + "specified dimensions: " + getSelectedDimensions()); - } - double sqrDist = 0; - for(int d = getSelectedDimensions().nextSetBit(0); d >= 0; d = getSelectedDimensions().nextSetBit(d + 1)) { - final double m1, m2; - if(mbr1.getMax(d) < mbr2.getMin(d)) { - m1 = mbr1.getMax(d); - m2 = mbr2.getMin(d); + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double delta; + final double max1 = mbr1.getMax(d + 1); + final double min2 = mbr2.getMin(d + 1); + if(max1 < min2) { + delta = min2 - max1; } - else if(mbr1.getMin(d) > mbr2.getMax(d)) { - m1 = mbr1.getMin(d); - m2 = mbr2.getMax(d); - } - else { // The mbrs intersect! - continue; + else { + final double min1 = mbr1.getMin(d + 1); + final double max2 = mbr2.getMax(d + 1); + if(min1 > max2) { + delta = min1 - max2; + } + else { // The mbrs intersect! + continue; + } } - double manhattanI = m1 - m2; - sqrDist += manhattanI * manhattanI; + sqrDist += Math.pow(delta, p); } - return Math.sqrt(sqrDist); + return Math.pow(sqrDist, 1. / p); } @Override - public double doubleCenterDistance(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()); - } - if(mbr1.getDimensionality() < getSelectedDimensions().size()) { - throw new IllegalArgumentException("The dimensionality of the feature space " + "is not consistent with the specified dimensions " + "to be considered for distance computation.\n " + "dimensionality of the feature space: " + mbr1.getDimensionality() + "\n " + "specified dimensions: " + getSelectedDimensions()); - } - - double sqrDist = 0; - for(int d = getSelectedDimensions().nextSetBit(0); d >= 0; d = getSelectedDimensions().nextSetBit(d + 1)) { - double c1 = (mbr1.getMin(d) + mbr1.getMax(d)) / 2; - double c2 = (mbr2.getMin(d) + mbr2.getMax(d)) / 2; + public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { + return new DoubleDistance(doubleMinDist(mbr1, mbr2)); + } - double manhattanI = c1 - c2; - sqrDist += manhattanI * manhattanI; - } - return Math.sqrt(sqrDist); + @Override + public DoubleDistance norm(NumberVector<?, ?> obj) { + return new DoubleDistance(doubleNorm(obj)); } @Override - public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleMinDist(mbr1, mbr2)); + public double doubleNorm(NumberVector<?, ?> obj) { + double sqrDist = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + double delta = Math.abs(obj.doubleValue(d + 1)); + sqrDist += Math.pow(delta, p); + } + return Math.pow(sqrDist, 1. / p); } @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); + public <T extends NumberVector<?, ?>> SpatialPrimitiveDistanceQuery<T, DoubleDistance> instantiate(Relation<T> database) { + return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(database, this); } - + @Override public VectorFieldTypeInformation<? super NumberVector<?, ?>> getInputTypeRestriction() { return TypeUtil.NUMBER_VECTOR_FIELD; @@ -174,11 +184,6 @@ public class DimensionsSelectingEuclideanDistanceFunction extends AbstractDimens return true; } - @Override - public <T extends NumberVector<?, ?>> SpatialPrimitiveDistanceQuery<T, DoubleDistance> instantiate(Relation<T> database) { - return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(database, this); - } - /** * Parameterization class. * @@ -187,9 +192,29 @@ public class DimensionsSelectingEuclideanDistanceFunction extends AbstractDimens * @apiviz.exclude */ public static class Parameterizer extends AbstractDimensionsSelectingDoubleDistanceFunction.Parameterizer { + /** + * Value of p + */ + private double p; + @Override - protected DimensionsSelectingEuclideanDistanceFunction makeInstance() { - return new DimensionsSelectingEuclideanDistanceFunction(dimensions); + protected void makeOptions(Parameterization config) { + final DoubleParameter paramP = new DoubleParameter(LPNormDistanceFunction.P_ID, new GreaterConstraint(0)); + if(config.grab(paramP)) { + p = paramP.getValue(); + } + super.makeOptions(config); + } + + @Override + protected SubspaceLPNormDistanceFunction makeInstance() { + if(p == 2.0) { + return new SubspaceEuclideanDistanceFunction(dimensions); + } + if(p == 1.0) { + return new SubspaceManhattanDistanceFunction(dimensions); + } + return new SubspaceLPNormDistanceFunction(p, dimensions); } } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceManhattanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceManhattanDistanceFunction.java new file mode 100644 index 00000000..905ee037 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/SubspaceManhattanDistanceFunction.java @@ -0,0 +1,142 @@ +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) 2012 + 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 SubspaceManhattanDistanceFunction extends SubspaceLPNormDistanceFunction { + /** + * Constructor. + * + * @param dimensions Selected dimensions + */ + public SubspaceManhattanDistanceFunction(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 sum = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + sum += Math.abs(v1.doubleValue(d + 1) - v2.doubleValue(d + 1)); + } + return sum; + } + + 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 sum = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double value = v.doubleValue(d + 1); + final double omin = mbr.getMin(d + 1); + if(value < omin) { + sum += omin - value; + } + else { + final double omax = mbr.getMax(d + 1); + if(value > omax) { + sum += value - omax; + } + else { + continue; + } + } + } + return sum; + } + + @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 sum = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + final double max1 = mbr1.getMax(d + 1); + final double min2 = mbr2.getMin(d + 1); + if(max1 < min2) { + sum += min2 - max1; + } + else { + final double min1 = mbr1.getMin(d + 1); + final double max2 = mbr2.getMax(d + 1); + if(min1 > max2) { + sum += min1 - max2; + } + else { // The mbrs intersect! + continue; + } + } + } + return sum; + } + + @Override + public double doubleNorm(NumberVector<?, ?> obj) { + double sum = 0; + for(int d = dimensions.nextSetBit(0); d >= 0; d = dimensions.nextSetBit(d + 1)) { + sum += Math.abs(obj.doubleValue(d + 1)); + } + return sum; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractDimensionsSelectingDoubleDistanceFunction.Parameterizer { + @Override + protected SubspaceManhattanDistanceFunction makeInstance() { + return new SubspaceManhattanDistanceFunction(dimensions); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/package-info.java index f24e112f..85035eec 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/subspace/package-info.java @@ -5,7 +5,7 @@ This file is part of ELKI: Environment for Developing KDD-Applications Supported by Index-Structures -Copyright (C) 2011 +Copyright (C) 2012 Ludwig-Maximilians-Universität München Lehr- und Forschungseinheit für Datenbanksysteme ELKI Development Team |