diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/distance')
114 files changed, 1732 insertions, 607 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/distance/DistanceUtil.java b/src/de/lmu/ifi/dbs/elki/distance/DistanceUtil.java index 0b6ccd10..7a394b8b 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/DistanceUtil.java +++ b/src/de/lmu/ifi/dbs/elki/distance/DistanceUtil.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance; 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/AbstractCosineDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractCosineDistanceFunction.java deleted file mode 100644 index 61e4a22f..00000000 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractCosineDistanceFunction.java +++ /dev/null @@ -1,107 +0,0 @@ -package de.lmu.ifi.dbs.elki.distance.distancefunction; - -/* - This file is part of ELKI: - Environment for Developing KDD-Applications Supported by Index-Structures - - Copyright (C) 2011 - 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.SparseNumberVector; -import de.lmu.ifi.dbs.elki.database.query.distance.PrimitiveDistanceQuery; -import de.lmu.ifi.dbs.elki.database.relation.Relation; -import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; -import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; - -/** - * Abstract base class for Cosine and ArcCosine distances. - * - * @author Erich Schubert - */ -public abstract class AbstractCosineDistanceFunction extends AbstractVectorDoubleDistanceFunction { - /** - * Constructor. - */ - public AbstractCosineDistanceFunction() { - super(); - } - - /** - * Compute the angle between two vectors. - * - * @param v1 first vector - * @param v2 second vector - * @return Angle - */ - protected double angle(NumberVector<?, ?> v1, NumberVector<?, ?> v2) { - if(v1 instanceof SparseNumberVector<?, ?> && v2 instanceof SparseNumberVector<?, ?>) { - return angleSparse((SparseNumberVector<?, ?>) v1, (SparseNumberVector<?, ?>) v2); - } - Vector m1 = v1.getColumnVector(); - m1.normalize(); - Vector m2 = v2.getColumnVector(); - m2.normalize(); - return m1.transposeTimes(m2); - } - - /** - * Compute the angle for sparse vectors. - * - * @param v1 First vector - * @param v2 Second vector - * @return angle - */ - protected double angleSparse(SparseNumberVector<?, ?> v1, SparseNumberVector<?, ?> v2) { - BitSet b1 = v1.getNotNullMask(); - BitSet b2 = v2.getNotNullMask(); - BitSet both = (BitSet) b1.clone(); - both.and(b2); - - // Length of first vector - double l1 = 0.0; - for(int i = b1.nextSetBit(0); i >= 0; i = b1.nextSetBit(i + 1)) { - final double val = v1.doubleValue(i); - l1 += val * val; - } - l1 = Math.sqrt(l1); - - // Length of second vector - double l2 = 0.0; - for(int i = b2.nextSetBit(0); i >= 0; i = b2.nextSetBit(i + 1)) { - final double val = v2.doubleValue(i); - l2 += val * val; - } - l2 = Math.sqrt(l2); - - // Cross product - double cross = 0.0; - for(int i = both.nextSetBit(0); i >= 0; i = both.nextSetBit(i + 1)) { - cross += v1.doubleValue(i) * v2.doubleValue(i); - } - return cross / (l1 * l2); - } - - @Override - public <T extends NumberVector<?, ?>> PrimitiveDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { - return new PrimitiveDistanceQuery<T, DoubleDistance>(relation, this); - } -}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDBIDDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDBIDDistanceFunction.java index 71d8d0bb..f1a53803 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDBIDDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDBIDDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/AbstractDatabaseDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDatabaseDistanceFunction.java index 22e0cbc3..845ea0ea 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDatabaseDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractDatabaseDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/AbstractIndexBasedDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractIndexBasedDistanceFunction.java index dfefb355..9280b783 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractIndexBasedDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractIndexBasedDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/AbstractPrimitiveDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractPrimitiveDistanceFunction.java index d4ec52b1..1c94bc28 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractPrimitiveDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractPrimitiveDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/AbstractVectorDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java index 4bc2a381..dbda2e96 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -38,7 +38,7 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; * @apiviz.uses NumberVector * @apiviz.has DoubleDistance */ -public abstract class AbstractVectorDoubleDistanceFunction extends AbstractPrimitiveDistanceFunction<NumberVector<?, ?>, DoubleDistance> implements PrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { +public abstract class AbstractVectorDoubleDistanceFunction extends AbstractPrimitiveDistanceFunction<NumberVector<?, ?>, DoubleDistance> implements PrimitiveDoubleDistanceFunction<NumberVector<?, ?>>, NumberVectorDistanceFunction<DoubleDistance> { /** * Constructor. */ diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceNorm.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceNorm.java new file mode 100644 index 00000000..7a7785e1 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/AbstractVectorDoubleDistanceNorm.java @@ -0,0 +1,40 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + 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 de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Abstract base class for double-valued number-vector-based distances based on + * norms. + * + * @author Erich Schubert + */ +public abstract class AbstractVectorDoubleDistanceNorm extends AbstractVectorDoubleDistanceFunction implements DoubleNorm<NumberVector<?, ?>> { + @Override + public DoubleDistance norm(NumberVector<?, ?> obj) { + return new DoubleDistance(doubleNorm(obj)); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ArcCosineDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ArcCosineDistanceFunction.java index fd19bfef..03563c6f 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ArcCosineDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ArcCosineDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -24,6 +24,14 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; */ import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.VectorUtil; +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.database.query.distance.SpatialDistanceQuery; +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.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** @@ -34,12 +42,12 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * * @author Arthur Zimek */ -public class ArcCosineDistanceFunction extends AbstractCosineDistanceFunction { +public class ArcCosineDistanceFunction extends AbstractVectorDoubleDistanceFunction implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { /** * Static instance */ public static final ArcCosineDistanceFunction STATIC = new ArcCosineDistanceFunction(); - + /** * Provides a CosineDistanceFunction. * @@ -61,8 +69,8 @@ public class ArcCosineDistanceFunction extends AbstractCosineDistanceFunction { * @return the cosine distance for two given feature vectors v1 and v2 */ @Override - public double doubleDistance(NumberVector<?,?> v1, NumberVector<?,?> v2) { - double d = Math.acos(angle(v1, v2)); + public double doubleDistance(NumberVector<?, ?> v1, NumberVector<?, ?> v2) { + double d = Math.acos(VectorUtil.cosAngle(v1, v2)); if(d < 0) { d = 0; } @@ -70,6 +78,20 @@ public class ArcCosineDistanceFunction extends AbstractCosineDistanceFunction { } @Override + public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { + double d = Math.acos(VectorUtil.minCosAngle(mbr1, mbr2)); + if(d < 0) { + d = 0; + } + return d; + } + + @Override + public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { + return new DoubleDistance(doubleMinDist(mbr1, mbr2)); + } + + @Override public String toString() { return "ArcCosineDistance"; } @@ -85,6 +107,16 @@ public class ArcCosineDistanceFunction extends AbstractCosineDistanceFunction { return this.getClass().equals(obj.getClass()); } + @Override + public <T extends NumberVector<?, ?>> SpatialDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { + return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); + } + + @Override + public SimpleTypeInformation<? super NumberVector<?, ?>> getInputTypeRestriction() { + return TypeUtil.NUMBER_VECTOR_VARIABLE_LENGTH; + } + /** * Parameterization class. * diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CanberraDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CanberraDistanceFunction.java new file mode 100644 index 00000000..6c8647ab --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CanberraDistanceFunction.java @@ -0,0 +1,127 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2011 + 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.database.query.distance.SpatialDistanceQuery; +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.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * Canberra distance function, a variation of Manhattan distance. + * + * <p> + * Reference:<br /> + * G. N. Lance, W. T. Williams<br /> + * Computer programs for hierarchical polythetic classification ("similarity + * analysis")<br /> + * In: Computer Journal, Volume 9, Issue 1 + * </p> + * + * @author Erich Schubert + */ +@Reference(authors = "G. N. Lance, W. T. Williams", title = "Computer programs for hierarchical polythetic classification (similarity analysis).", booktitle = "Computer Journal, Volume 9, Issue 1", url = "http://comjnl.oxfordjournals.org/content/9/1/60.short") +public class CanberraDistanceFunction extends AbstractVectorDoubleDistanceFunction implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { + /** + * Static instance. Use this! + */ + public static final CanberraDistanceFunction STATIC = new CanberraDistanceFunction(); + + /** + * Constructor. + */ + protected CanberraDistanceFunction() { + super(); + } + + @Override + public double doubleDistance(NumberVector<?, ?> o1, NumberVector<?, ?> o2) { + final int dim = o1.getDimensionality(); + double sum = 0.0; + for(int i = 1; i <= dim; i++) { + double v1 = o1.doubleValue(i); + double v2 = o2.doubleValue(i); + final double div = Math.abs(v1) + Math.abs(v2); + if (div > 0) { + sum += Math.abs(v1 - v2) / div; + } + } + return sum; + } + + @Override + public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { + final int dim = mbr1.getDimensionality(); + double sum = 0.0; + for(int d = 1; d <= dim; d++) { + final double m1, m2; + if(mbr1.getMax(d) < mbr2.getMin(d)) { + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); + } + else if(mbr1.getMin(d) > mbr2.getMax(d)) { + m1 = mbr1.getMin(d); + m2 = mbr2.getMax(d); + } + else { // The mbrs intersect! + continue; + } + final double manhattanI = m1 - m2; + final double a1 = Math.max(-mbr1.getMin(d), mbr1.getMax(d)); + final double a2 = Math.max(-mbr2.getMin(d), mbr2.getMax(d)); + final double div = a1 + a2; + if (div > 0) { + sum += manhattanI / div; + } + } + return sum; + } + + @Override + public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { + return new DoubleDistance(doubleMinDist(mbr1, mbr2)); + } + + @Override + public <T extends NumberVector<?, ?>> SpatialDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { + return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected CanberraDistanceFunction makeInstance() { + return CanberraDistanceFunction.STATIC; + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CosineDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CosineDistanceFunction.java index 25abe7ef..2d681dad 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CosineDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/CosineDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -24,6 +24,14 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; */ import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.VectorUtil; +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.database.query.distance.SpatialDistanceQuery; +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.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** @@ -34,7 +42,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * * @author Arthur Zimek */ -public class CosineDistanceFunction extends AbstractCosineDistanceFunction { +public class CosineDistanceFunction extends AbstractVectorDoubleDistanceFunction implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { /** * Static instance */ @@ -62,7 +70,7 @@ public class CosineDistanceFunction extends AbstractCosineDistanceFunction { */ @Override public double doubleDistance(NumberVector<?, ?> v1, NumberVector<?, ?> v2) { - double d = 1 - angle(v1, v2); + double d = 1 - VectorUtil.cosAngle(v1, v2); if(d < 0) { d = 0; } @@ -70,6 +78,20 @@ public class CosineDistanceFunction extends AbstractCosineDistanceFunction { } @Override + public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { + double d = 1 - VectorUtil.minCosAngle(mbr1, mbr2); + if(d < 0) { + d = 0; + } + return d; + } + + @Override + public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { + return new DoubleDistance(doubleMinDist(mbr1, mbr2)); + } + + @Override public String toString() { return "CosineDistance"; } @@ -85,6 +107,16 @@ public class CosineDistanceFunction extends AbstractCosineDistanceFunction { return this.getClass().equals(obj.getClass()); } + @Override + public <T extends NumberVector<?, ?>> SpatialDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { + return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); + } + + @Override + public SimpleTypeInformation<? super NumberVector<?, ?>> getInputTypeRestriction() { + return TypeUtil.NUMBER_VECTOR_VARIABLE_LENGTH; + } + /** * Parameterization class. * diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DBIDDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DBIDDistanceFunction.java index 25a74c19..c4e6a891 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DBIDDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DBIDDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/DistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DistanceFunction.java index cc8a3699..0d38b418 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/DoubleNorm.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DoubleNorm.java new file mode 100644 index 00000000..3d7ed70f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/DoubleNorm.java @@ -0,0 +1,43 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + 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 de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; + +/** + * Interface for norms in the double domain. + * + * @author Erich Schubert + * + * @param <O> Object type + */ +public interface DoubleNorm<O> extends Norm<O, DoubleDistance>, PrimitiveDoubleDistanceFunction<O> { + /** + * Compute the norm of object obj as double value. + * + * @param obj Object + * @return Double + */ + public double doubleNorm(O obj); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/EuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/EuclideanDistanceFunction.java index 235bedb3..c0bc5696 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/EuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/EuclideanDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -25,9 +25,6 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -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.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** @@ -72,6 +69,17 @@ public class EuclideanDistanceFunction extends LPNormDistanceFunction implements return Math.sqrt(sqrDist); } + @Override + public double doubleNorm(NumberVector<?, ?> v) { + final int dim = v.getDimensionality(); + double sqrDist = 0; + for(int i = 1; i <= dim; i++) { + final double delta = v.doubleValue(i); + sqrDist += delta * delta; + } + return Math.sqrt(sqrDist); + } + protected double doubleMinDistObject(SpatialComparable mbr, NumberVector<?, ?> v) { final int dim = mbr.getDimensionality(); if(dim != v.getDimensionality()) { @@ -121,8 +129,8 @@ public class EuclideanDistanceFunction extends LPNormDistanceFunction implements for(int d = 1; d <= dim1; d++) { final double m1, m2; if(mbr1.getMax(d) < mbr2.getMin(d)) { - m1 = mbr1.getMax(d); - m2 = mbr2.getMin(d); + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); } else if(mbr1.getMin(d) > mbr2.getMax(d)) { m1 = mbr1.getMin(d); @@ -138,44 +146,11 @@ public class EuclideanDistanceFunction extends LPNormDistanceFunction implements } @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - - @Override - public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleMinDist(mbr1, mbr2)); - } - - @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - final int dim1 = mbr1.getDimensionality(); - if(dim1 != 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 = 1; d <= dim1; d++) { - final double c1 = (mbr1.getMin(d) + mbr1.getMax(d)) / 2; - final double c2 = (mbr2.getMin(d) + mbr2.getMax(d)) / 2; - - final double manhattanI = c1 - c2; - sqrDist += manhattanI * manhattanI; - } - return Math.sqrt(sqrDist); - } - - @Override public boolean isMetric() { return true; } @Override - public <T extends NumberVector<?, ?>> SpatialPrimitiveDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { - return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); - } - - @Override public String toString() { return "EuclideanDistance"; } @@ -188,7 +163,7 @@ public class EuclideanDistanceFunction extends LPNormDistanceFunction implements 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/FilteredLocalPCABasedDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/FilteredLocalPCABasedDistanceFunction.java index 0bd93ede..03074815 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/FilteredLocalPCABasedDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/FilteredLocalPCABasedDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/IndexBasedDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/IndexBasedDistanceFunction.java index aac19541..8663c8c3 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/IndexBasedDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/IndexBasedDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/JeffreyDivergenceDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/JeffreyDivergenceDistanceFunction.java new file mode 100644 index 00000000..3aa6908f --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/JeffreyDivergenceDistanceFunction.java @@ -0,0 +1,100 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2011 + 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.utilities.documentation.Reference; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; + +/** + * Provides the Jeffrey Divergence Distance for FeatureVectors. + * + * @author Erich Schubert + */ +@Reference(authors="J. Puzicha,J.M. Buhmann, Y. Rubner, C. Tomasi", title="Empirical evaluation of dissimilarity measures for color and texture", booktitle="Proc. 7th IEEE International Conference on Computer Vision", url="http://dx.doi.org/10.1109/ICCV.1999.790412") +public class JeffreyDivergenceDistanceFunction extends AbstractVectorDoubleDistanceFunction { + /** + * Static instance. Use this! + */ + public static final JeffreyDivergenceDistanceFunction STATIC = new JeffreyDivergenceDistanceFunction(); + + /** + * Constructor for the Jeffrey divergence. + * + * @deprecated Use static instance! + */ + @Deprecated + public JeffreyDivergenceDistanceFunction() { + } + + @Override + public double doubleDistance(NumberVector<?, ?> v1, NumberVector<?, ?> v2) { + final int dim1 = v1.getDimensionality(); + if(dim1 != v2.getDimensionality()) { + throw new IllegalArgumentException("Different dimensionality of FeatureVectors" + "\n first argument: " + v1.toString() + "\n second argument: " + v2.toString() + "\n" + v1.getDimensionality() + "!=" + v2.getDimensionality()); + } + double dist = 0; + for(int i = 1; i <= dim1; i++) { + final double xi = v1.doubleValue(i); + final double yi = v2.doubleValue(i); + final double mi = (xi + yi) / 2; + dist += xi * Math.log(xi / mi); + dist += yi * Math.log(yi / mi); + } + return dist; + } + + @Override + public String toString() { + return "JeffreyDivergenceDistance"; + } + + @Override + public boolean equals(Object obj) { + if(obj == null) { + return false; + } + if(obj == this) { + return true; + } + if(this.getClass().equals(obj.getClass())) { + return true; + } + return super.equals(obj); + } + + /** + * Parameterization class, using the static instance. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer extends AbstractParameterizer { + @Override + protected JeffreyDivergenceDistanceFunction makeInstance() { + return JeffreyDivergenceDistanceFunction.STATIC; + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LPNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LPNormDistanceFunction.java index d17825e9..134b587f 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LPNormDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LPNormDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -24,6 +24,10 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; */ import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +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.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint; @@ -37,9 +41,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter; * * @apiviz.landmark */ -public class LPNormDistanceFunction extends AbstractVectorDoubleDistanceFunction { - // TODO: implement SpatialPrimitiveDoubleDistanceFunction? - +public class LPNormDistanceFunction extends AbstractVectorDoubleDistanceNorm implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { /** * OptionID for the "p" parameter */ @@ -84,6 +86,17 @@ public class LPNormDistanceFunction extends AbstractVectorDoubleDistanceFunction return Math.pow(sqrDist, 1.0 / p); } + @Override + public double doubleNorm(NumberVector<?, ?> v) { + final int dim = v.getDimensionality(); + double sqrDist = 0; + for(int i = 1; i <= dim; i++) { + final double delta = v.doubleValue(i); + sqrDist += Math.pow(delta, p); + } + return Math.pow(sqrDist, 1.0 / p); + } + /** * Get the functions p parameter. * @@ -94,6 +107,45 @@ public class LPNormDistanceFunction extends AbstractVectorDoubleDistanceFunction } @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 dim1 = mbr1.getDimensionality(); + if(dim1 != mbr2.getDimensionality()) { + throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr1.toString() + "\n " + "second argument: " + mbr2.toString()); + } + + double sumDist = 0; + for(int d = 1; d <= dim1; d++) { + final double m1, m2; + if(mbr1.getMax(d) < mbr2.getMin(d)) { + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); + } + else if(mbr1.getMin(d) > mbr2.getMax(d)) { + m1 = mbr1.getMin(d); + m2 = mbr2.getMax(d); + } + else { // The mbrs intersect! + continue; + } + final double manhattanI = m1 - m2; + sumDist += Math.pow(manhattanI, p); + } + return Math.pow(sumDist, 1.0 / p); + } + + @Override + public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { + return new DoubleDistance(doubleMinDist(mbr1, mbr2)); + } + + @Override public boolean isMetric() { return (p >= 1); } @@ -114,6 +166,11 @@ public class LPNormDistanceFunction extends AbstractVectorDoubleDistanceFunction return false; } + @Override + public <T extends NumberVector<?, ?>> SpatialPrimitiveDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { + return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); + } + /** * Parameterization class. * diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LocallyWeightedDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LocallyWeightedDistanceFunction.java index 1345013b..ee3cc438 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LocallyWeightedDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/LocallyWeightedDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -132,11 +132,11 @@ public class LocallyWeightedDistanceFunction<V extends NumberVector<?, ?>> exten V v1 = relation.get(id1); V v2 = relation.get(id2); - Vector v1Mv2 = v1.getColumnVector().minus(v2.getColumnVector()); - Vector v2Mv1 = v2.getColumnVector().minus(v1.getColumnVector()); + Vector v1Mv2 = v1.getColumnVector().minusEquals(v2.getColumnVector()); + Vector v2Mv1 = v2.getColumnVector().minusEquals(v1.getColumnVector()); - double dist1 = v1Mv2.transposeTimes(m1).times(v1Mv2).get(0, 0); - double dist2 = v2Mv1.transposeTimes(m2).times(v2Mv1).get(0, 0); + double dist1 = v1Mv2.transposeTimesTimes(m1, v1Mv2); + double dist2 = v2Mv1.transposeTimesTimes(m2, v2Mv1); if(dist1 < 0) { if(-dist1 < 0.000000000001) { @@ -180,8 +180,8 @@ public class LocallyWeightedDistanceFunction<V extends NumberVector<?, ?>> exten } Matrix m = null; // index.getLocalProjection(v.getID()).similarityMatrix(); - Vector rv1Mrv2 = v.getColumnVector().minus(new Vector(r)); - double dist = rv1Mrv2.transposeTimes(m).times(rv1Mrv2).get(0, 0); + Vector rv1Mrv2 = v.getColumnVector().minusEquals(new Vector(r)); + double dist = rv1Mrv2.transposeTimesTimes(m, rv1Mrv2); return new DoubleDistance(Math.sqrt(dist)); } @@ -203,8 +203,8 @@ public class LocallyWeightedDistanceFunction<V extends NumberVector<?, ?>> exten for(int d = 1; d <= mbr1.getDimensionality(); d++) { double m1, m2; if(mbr1.getMax(d) < mbr2.getMin(d)) { - m1 = mbr1.getMax(d); - m2 = mbr2.getMin(d); + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); } else if(mbr1.getMin(d) > mbr2.getMax(d)) { m1 = mbr1.getMin(d); diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ManhattanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ManhattanDistanceFunction.java index 8cbe0fdb..c638ce13 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ManhattanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ManhattanDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -25,9 +25,6 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -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.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** @@ -73,8 +70,24 @@ public class ManhattanDistanceFunction extends LPNormDistanceFunction implements } return sum; } + + /** + * Returns the Manhattan norm of the given vector. + * + * @param v the vector to compute the norm of + * @return the Manhattan norm of the given vector + */ + @Override + public double doubleNorm(NumberVector<?,?> v){ + final int dim = v.getDimensionality(); + double sum = 0; + for(int i = 1; i <= dim; i++) { + sum += Math.abs(v.doubleValue(i)); + } + return sum; + } - protected double doubleMinDistObject(SpatialComparable mbr, NumberVector<?, ?> v) { + private double doubleMinDistObject(SpatialComparable mbr, NumberVector<?, ?> v) { final int dim = mbr.getDimensionality(); if(dim != v.getDimensionality()) { throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr.toString() + "\n " + "second argument: " + v.toString() + "\n" + dim + "!=" + v.getDimensionality()); @@ -94,8 +107,8 @@ public class ManhattanDistanceFunction extends LPNormDistanceFunction implements r = value; } - final double manhattanI = value - r; - sumDist += Math.abs(manhattanI); + final double manhattanI = Math.abs(value - r); + sumDist += manhattanI; } return sumDist; } @@ -123,8 +136,8 @@ public class ManhattanDistanceFunction extends LPNormDistanceFunction implements for(int d = 1; d <= dim1; d++) { final double m1, m2; if(mbr1.getMax(d) < mbr2.getMin(d)) { - m1 = mbr1.getMax(d); - m2 = mbr2.getMin(d); + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); } else if(mbr1.getMin(d) > mbr2.getMax(d)) { m1 = mbr1.getMin(d); @@ -134,50 +147,17 @@ public class ManhattanDistanceFunction extends LPNormDistanceFunction implements continue; } final double manhattanI = m1 - m2; - sumDist += Math.abs(manhattanI); - } - return sumDist; - } - - @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - final int dim1 = mbr1.getDimensionality(); - if(dim1 != mbr2.getDimensionality()) { - throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr1.toString() + "\n " + "second argument: " + mbr2.toString()); - } - - double sumDist = 0; - for(int d = 1; d <= dim1; d++) { - final double c1 = (mbr1.getMin(d) + mbr1.getMax(d)) / 2; - final double c2 = (mbr2.getMin(d) + mbr2.getMax(d)) / 2; - - final double manhattanI = c1 - c2; - sumDist += Math.abs(manhattanI); + sumDist += manhattanI; } return sumDist; } @Override - public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleMinDist(mbr1, mbr2)); - } - - @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - - @Override public boolean isMetric() { return true; } @Override - public <T extends NumberVector<?, ?>> SpatialPrimitiveDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { - return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); - } - - @Override public String toString() { return "ManhattanDistance"; } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MaximumDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MaximumDistanceFunction.java index ece11645..e718d087 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MaximumDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MaximumDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -25,10 +25,6 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; import de.lmu.ifi.dbs.elki.data.NumberVector; import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; -import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery; -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.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; /** @@ -69,6 +65,16 @@ public class MaximumDistanceFunction extends LPNormDistanceFunction implements S } @Override + public double doubleNorm(NumberVector<?, ?> v) { + final int dim = v.getDimensionality(); + double max = 0; + for(int i = 1; i <= dim; i++) { + max = Math.max(v.doubleValue(i), max); + } + return max; + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { final int dim1 = mbr1.getDimensionality(); if(dim1 != mbr2.getDimensionality()) { @@ -93,42 +99,11 @@ public class MaximumDistanceFunction extends LPNormDistanceFunction implements S } @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - final int dim1 = mbr1.getDimensionality(); - if(dim1 != mbr2.getDimensionality()) { - throw new IllegalArgumentException("Different dimensionality of objects."); - } - double max = 0; - for(int i = 1; i <= dim1; i++) { - final double c1 = (mbr1.getMax(i) - mbr1.getMin(i)) / 2; - final double c2 = (mbr2.getMax(i) - mbr2.getMin(i)) / 2; - final double d = Math.abs(c2 - c1); - max = Math.max(d, max); - } - return max; - } - - @Override - public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleMinDist(mbr1, mbr2)); - } - - @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - - @Override public boolean isMetric() { return true; } @Override - public <T extends NumberVector<?, ?>> SpatialDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { - return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); - } - - @Override public String toString() { return "MaximumDistance"; } @@ -141,7 +116,7 @@ public class MaximumDistanceFunction extends LPNormDistanceFunction implements S 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/MinKDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java index 9c03134c..ef805c6d 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinKDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -23,16 +23,14 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; along with this program. If not, see <http://www.gnu.org/licenses/>. */ -import java.util.List; - import de.lmu.ifi.dbs.elki.data.type.TypeInformation; import de.lmu.ifi.dbs.elki.database.QueryUtil; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.query.DatabaseQuery; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; import de.lmu.ifi.dbs.elki.database.query.distance.AbstractDatabaseDistanceQuery; import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery; +import de.lmu.ifi.dbs.elki.database.query.knn.KNNResult; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.DistanceUtil; import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; @@ -139,6 +137,11 @@ public class MinKDistance<O, D extends Distance<D>> extends AbstractDatabaseDist private int k; /** + * Distance query for parent distance. + */ + private DistanceQuery<T, D> parentDistanceQuery; + + /** * Constructor. * * @param relation Database @@ -147,13 +150,14 @@ public class MinKDistance<O, D extends Distance<D>> extends AbstractDatabaseDist public Instance(Relation<T> relation, int k, DistanceFunction<? super O, D> parentDistance) { super(relation); this.k = k; + this.parentDistanceQuery = parentDistance.instantiate(relation); this.knnQuery = QueryUtil.getKNNQuery(relation, parentDistance, k, DatabaseQuery.HINT_HEAVY_USE); } @Override public D distance(DBID id1, DBID id2) { - List<DistanceResultPair<D>> neighborhood = knnQuery.getKNNForDBID(id1, k); - D truedist = knnQuery.getDistanceQuery().distance(id1, id2); + KNNResult<D> neighborhood = knnQuery.getKNNForDBID(id1, k); + D truedist = parentDistanceQuery.distance(id1, id2); return computeReachdist(neighborhood, truedist); } @@ -171,7 +175,7 @@ public class MinKDistance<O, D extends Distance<D>> extends AbstractDatabaseDist * @param truedist True distance * @return Reachability distance */ - protected D computeReachdist(List<DistanceResultPair<D>> neighborhood, D truedist) { + protected D computeReachdist(KNNResult<D> neighborhood, D truedist) { // TODO: need to check neighborhood size? // TODO: Do we need to check we actually got the object itself in the // neighborhood? diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinimumDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinimumDistanceFunction.java index c9c00cc4..2a31a829 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinimumDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/MinimumDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -37,7 +37,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * @author Erich Schubert */ // TODO: add spatial? -public class MinimumDistanceFunction extends AbstractVectorDoubleDistanceFunction implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { +public class MinimumDistanceFunction extends AbstractVectorDoubleDistanceNorm implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { /** * Static instance. Use this. */ @@ -69,6 +69,16 @@ public class MinimumDistanceFunction extends AbstractVectorDoubleDistanceFunctio } @Override + public double doubleNorm(NumberVector<?, ?> v) { + final int dim = v.getDimensionality(); + double min = Double.POSITIVE_INFINITY; + for(int i = 1; i <= dim; i++) { + min = Math.min(v.doubleValue(i), min); + } + return min; + } + + @Override public double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2) { final int dim = mbr1.getDimensionality(); if(dim != mbr2.getDimensionality()) { @@ -98,30 +108,11 @@ public class MinimumDistanceFunction extends AbstractVectorDoubleDistanceFunctio } @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - final int dim = mbr1.getDimensionality(); - if(dim != mbr2.getDimensionality()) { - throw new IllegalArgumentException("Different dimensionality of FeatureVectors" + "\n first argument: " + mbr1.toString() + "\n second argument: " + mbr2.toString()); - } - double min = Double.MAX_VALUE; - for(int i = 1; i <= dim; i++) { - final double d = Math.abs((mbr1.getMin(i) + mbr1.getMax(i)) / 2 - (mbr2.getMin(i) + mbr1.getMax(i)) / 2); - min = Math.min(d, min); - } - return min; - } - - @Override public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { return new DoubleDistance(doubleMinDist(mbr1, mbr2)); } @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - - @Override public String toString() { return "MinimumDistance"; } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/Norm.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/Norm.java new file mode 100644 index 00000000..98ef1f1d --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/Norm.java @@ -0,0 +1,44 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + 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 de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Abstract interface for a mathematical norm. + * + * @author Erich Schubert + * + * @param <O> Object type + * @param <D> Distance type + */ +public interface Norm<O, D extends Distance<D>> extends DistanceFunction<O, D> { + /** + * Compute the norm of object obj. + * + * @param obj Object + * @return Norm + */ + public D norm(O obj); +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/NumberVectorDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/NumberVectorDistanceFunction.java new file mode 100644 index 00000000..68034672 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/NumberVectorDistanceFunction.java @@ -0,0 +1,40 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2011 + 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.distance.distancevalue.Distance; + +/** + * Base interface for the common case of distance functions defined on numerical vectors. + * + * @author Erich Schubert + * + * @apiviz.landmark + * + * @param <D> Distance type + */ +public interface NumberVectorDistanceFunction<D extends Distance<D>> extends PrimitiveDistanceFunction<NumberVector<?, ?>, D> { + // Empty - marker interface +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDistanceFunction.java index d27d9a38..f8b62225 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/PrimitiveDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDoubleDistanceFunction.java index 03306ef0..e4d19702 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/PrimitiveDoubleDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/ProxyDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ProxyDistanceFunction.java index 909b1120..9afdbecd 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ProxyDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/ProxyDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/RandomStableDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/RandomStableDistanceFunction.java index 3d5715ec..0632d475 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/RandomStableDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/RandomStableDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/SharedNearestNeighborJaccardDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SharedNearestNeighborJaccardDistanceFunction.java index 0b80f512..cfc4217e 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SharedNearestNeighborJaccardDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SharedNearestNeighborJaccardDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -26,7 +26,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.preprocessed.snn.SharedNearestNeighborIndex; @@ -39,7 +39,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameteriz * * @author Erich Schubert * - * @apiviz.composedOf de.lmu.ifi.dbs.elki.index.preprocessed.snn.SharedNearestNeighborIndex.Factory + * @apiviz.composedOf SharedNearestNeighborIndex.Factory * @apiviz.has SharedNearestNeighborJaccardDistanceFunction.Instance oneway - - «create» * * @param <O> object type @@ -82,7 +82,14 @@ public class SharedNearestNeighborJaccardDistanceFunction<O> extends AbstractInd super(database, preprocessor, parent); } - static protected double jaccardCoefficient(TreeSetDBIDs neighbors1, TreeSetDBIDs neighbors2) { + /** + * Compute the Jaccard coefficient + * + * @param neighbors1 SORTED neighbor ids of first + * @param neighbors2 SORTED neighbor ids of second + * @return Jaccard coefficient + */ + static protected double jaccardCoefficient(DBIDs neighbors1, DBIDs neighbors2) { int intersection = 0; int union = 0; Iterator<DBID> iter1 = neighbors1.iterator(); @@ -118,8 +125,8 @@ public class SharedNearestNeighborJaccardDistanceFunction<O> extends AbstractInd @Override public DoubleDistance distance(DBID id1, DBID id2) { - TreeSetDBIDs neighbors1 = index.getNearestNeighborSet(id1); - TreeSetDBIDs neighbors2 = index.getNearestNeighborSet(id2); + DBIDs neighbors1 = index.getNearestNeighborSet(id1); + DBIDs neighbors2 = index.getNearestNeighborSet(id2); return new DoubleDistance(1.0 - jaccardCoefficient(neighbors1, neighbors2)); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunction.java index 2dd6bd06..27dd1219 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -32,33 +32,22 @@ import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; * API for a spatial primitive distance function. * * @author Erich Schubert - * + * * @param <V> Vector type * @param <D> Distance type */ public interface SpatialPrimitiveDistanceFunction<V extends SpatialComparable, D extends Distance<D>> extends PrimitiveDistanceFunction<V, D> { /** - * Computes the distance between the two given MBRs according to this - * distance function. + * Computes the distance between the two given MBRs according to this distance + * function. * * @param mbr1 the first MBR object * @param mbr2 the second MBR object - * @return the distance between the two given MBRs according to this - * distance function + * @return the distance between the two given MBRs according to this distance + * function */ D minDist(SpatialComparable mbr1, SpatialComparable mbr2); - /** - * Computes the distance between the centroids of the two given MBRs - * according to this distance function. - * - * @param mbr1 the first MBR object - * @param mbr2 the second MBR object - * @return the distance between the centroids of the two given MBRs - * according to this distance function - */ - D centerDistance(SpatialComparable mbr1, SpatialComparable mbr2); - @Override public <T extends V> SpatialDistanceQuery<T, D> instantiate(Relation<T> relation); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDoubleDistanceFunction.java index 07527baa..9ae39089 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SpatialPrimitiveDoubleDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -49,15 +49,4 @@ public interface SpatialPrimitiveDoubleDistanceFunction<V extends SpatialCompara * distance function */ double doubleMinDist(SpatialComparable mbr1, SpatialComparable mbr2); - - /** - * Computes the distance between the centroids of the two given MBRs - * according to this distance function. - * - * @param mbr1 the first MBR object - * @param mbr2 the second MBR object - * @return the distance between the centroids of the two given MBRs - * according to this distance function - */ - double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2); }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SquaredEuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SquaredEuclideanDistanceFunction.java index e899b1e2..80edcc09 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SquaredEuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/SquaredEuclideanDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -36,7 +36,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; * * @author Arthur Zimek */ -public class SquaredEuclideanDistanceFunction extends AbstractVectorDoubleDistanceFunction implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { +public class SquaredEuclideanDistanceFunction extends AbstractVectorDoubleDistanceNorm implements SpatialPrimitiveDoubleDistanceFunction<NumberVector<?, ?>> { /** * Static instance. Use this! */ @@ -53,6 +53,17 @@ public class SquaredEuclideanDistanceFunction extends AbstractVectorDoubleDistan super(); } + @Override + public double doubleNorm(NumberVector<?, ?> v) { + final int dim = v.getDimensionality(); + double sum = 0; + for(int i = 1; i <= dim; i++) { + final double val = v.doubleValue(i); + sum += val * val; + } + return sum; + } + /** * Provides the squared Euclidean distance between the given two vectors. * @@ -122,8 +133,8 @@ public class SquaredEuclideanDistanceFunction extends AbstractVectorDoubleDistan for(int d = 1; d <= dim1; d++) { final double m1, m2; if(mbr1.getMax(d) < mbr2.getMin(d)) { - m1 = mbr1.getMax(d); - m2 = mbr2.getMin(d); + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); } else if(mbr1.getMin(d) > mbr2.getMax(d)) { m1 = mbr1.getMin(d); @@ -139,29 +150,6 @@ public class SquaredEuclideanDistanceFunction extends AbstractVectorDoubleDistan } @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - final int dim1 = mbr1.getDimensionality(); - if(dim1 != 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 = 1; d <= dim1; d++) { - final double c1 = (mbr1.getMin(d) + mbr1.getMax(d)) / 2; - final double c2 = (mbr2.getMin(d) + mbr2.getMax(d)) / 2; - - final double manhattanI = c1 - c2; - sqrDist += manhattanI * manhattanI; - } - return sqrDist; - } - - @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - - @Override public DoubleDistance minDist(SpatialComparable mbr1, SpatialComparable mbr2) { return new DoubleDistance(doubleMinDist(mbr1, mbr2)); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedDistanceFunction.java index 201a999d..046cc3e9 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -59,14 +59,10 @@ public class WeightedDistanceFunction extends AbstractVectorDoubleDistanceFuncti */ @Override public double doubleDistance(NumberVector<?, ?> o1, NumberVector<?, ?> o2) { - if(o1.getDimensionality() != o2.getDimensionality()) { - throw new IllegalArgumentException("Different dimensionality of FeatureVectors" + "\n first argument: " + o1.toString() + "\n second argument: " + o2.toString()); - } + assert (o1.getDimensionality() == o2.getDimensionality()) : "Different dimensionality of FeatureVectors" + "\n first argument: " + o1.toString() + "\n second argument: " + o2.toString(); - Vector o1_minus_o2 = o1.getColumnVector().minus(o2.getColumnVector()); - double dist = MathUtil.mahalanobisDistance(weightMatrix, o1_minus_o2); - - return dist; + Vector o1_minus_o2 = o1.getColumnVector().minusEquals(o2.getColumnVector()); + return MathUtil.mahalanobisDistance(weightMatrix, o1_minus_o2); } @Override diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedLPNormDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedLPNormDistanceFunction.java index a31ed6e7..38302573 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedLPNormDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedLPNormDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 @@ -26,6 +26,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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 Euclidean distance function. @@ -68,6 +69,41 @@ public class WeightedLPNormDistanceFunction extends LPNormDistanceFunction { } return Math.pow(sqrDist, 1.0 / p); } + + @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 dim1 = mbr1.getDimensionality(); + if(dim1 != mbr2.getDimensionality()) { + throw new IllegalArgumentException("Different dimensionality of objects\n " + "first argument: " + mbr1.toString() + "\n " + "second argument: " + mbr2.toString()); + } + + final double p = getP(); + double sumDist = 0; + for(int d = 1; d <= dim1; d++) { + final double m1, m2; + if(mbr1.getMax(d) < mbr2.getMin(d)) { + m1 = mbr2.getMin(d); + m2 = mbr1.getMax(d); + } + else if(mbr1.getMin(d) > mbr2.getMax(d)) { + m1 = mbr1.getMin(d); + m2 = mbr2.getMax(d); + } + else { // The mbrs intersect! + continue; + } + final double manhattanI = m1 - m2; + sumDist += Math.pow(manhattanI, p) * weights[d - 1]; + } + return Math.pow(sumDist, 1.0 / p); + } @Override public boolean equals(Object obj) { diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedSquaredEuclideanDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedSquaredEuclideanDistanceFunction.java index d1bcbf26..a2944385 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedSquaredEuclideanDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/WeightedSquaredEuclideanDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction; 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/adapter/AbstractSimilarityAdapter.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java index 7f610d8b..206a32e7 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/AbstractSimilarityAdapter.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.adapter; 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/adapter/SimilarityAdapterArccos.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterArccos.java index 4f1814ec..d1a5aa4a 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterArccos.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterArccos.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.adapter; 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/adapter/SimilarityAdapterLinear.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterLinear.java index 664b6421..e2c0f981 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterLinear.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterLinear.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.adapter; 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/adapter/SimilarityAdapterLn.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterLn.java index 8d7ec170..a45b6108 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterLn.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/SimilarityAdapterLn.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.adapter; 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/adapter/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/package-info.java index 1f92d5fc..303d3500 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/adapter/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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java index 05c766ca..4eff8822 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HSBHistogramQuadraticDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram; 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/colorhistogram/HistogramIntersectionDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HistogramIntersectionDistanceFunction.java index 362f3589..6ed8e744 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HistogramIntersectionDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/HistogramIntersectionDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram; 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 @@ -70,11 +70,6 @@ public class HistogramIntersectionDistanceFunction extends AbstractVectorDoubleD } @Override - public DoubleDistance centerDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - return new DoubleDistance(doubleCenterDistance(mbr1, mbr2)); - } - - @Override public double doubleDistance(NumberVector<?, ?> v1, NumberVector<?, ?> v2) { final int dim1 = v1.getDimensionality(); if(dim1 != v2.getDimensionality()) { @@ -117,26 +112,6 @@ public class HistogramIntersectionDistanceFunction extends AbstractVectorDoubleD } @Override - public double doubleCenterDistance(SpatialComparable mbr1, SpatialComparable mbr2) { - final int dim1 = mbr1.getDimensionality(); - if(dim1 != mbr2.getDimensionality()) { - throw new IllegalArgumentException("Different dimensionality of FeatureVectors" + "\n first argument: " + mbr1.toString() + "\n second argument: " + mbr2.toString() + "\n" + mbr1.getDimensionality() + "!=" + mbr2.getDimensionality()); - } - double dist = 0; - double norm1 = 0; - double norm2 = 0; - for(int i = 1; i <= dim1; i++) { - final double val1 = (mbr1.getMin(i) + mbr1.getMax(i)) / 2; - final double val2 = (mbr2.getMin(i) + mbr2.getMax(i)) / 2; - dist += Math.min(val1, val2); - norm1 += val1; - norm2 += val2; - } - dist = 1 - dist / Math.min(norm1, norm2); - return dist; - } - - @Override public <T extends NumberVector<?, ?>> SpatialDistanceQuery<T, DoubleDistance> instantiate(Relation<T> relation) { return new SpatialPrimitiveDistanceQuery<T, DoubleDistance>(relation, this); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/RGBHistogramQuadraticDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/RGBHistogramQuadraticDistanceFunction.java index b902d43e..5ba02e17 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/RGBHistogramQuadraticDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/RGBHistogramQuadraticDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.colorhistogram; 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/colorhistogram/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/package-info.java index 2d1c85bb..43e90206 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/colorhistogram/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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java index 08c4ce3b..d59851b9 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/ERiCDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.correlation; 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 @@ -35,6 +35,7 @@ import de.lmu.ifi.dbs.elki.index.preprocessed.localpca.FilteredLocalPCAIndex; import de.lmu.ifi.dbs.elki.index.preprocessed.localpca.KNNQueryFilteredPCAIndex; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix; +import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.math.linearalgebra.pca.PCAFilteredResult; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; @@ -135,10 +136,10 @@ public class ERiCDistanceFunction extends AbstractIndexBasedDistanceFunction<Num Matrix m1_czech = pca1.dissimilarityMatrix(); Matrix v2_strong = pca2.adapatedStrongEigenvectors(); for(int i = 0; i < v2_strong.getColumnDimensionality(); i++) { - Matrix v2_i = v2_strong.getColumn(i); + Vector v2_i = v2_strong.getCol(i); // check, if distance of v2_i to the space of pca_1 > delta // (i.e., if v2_i spans up a new dimension) - double dist = Math.sqrt(v2_i.transposeTimes(v2_i).get(0, 0) - v2_i.transposeTimes(m1_czech).times(v2_i).get(0, 0)); + double dist = Math.sqrt(v2_i.transposeTimes(v2_i) - v2_i.transposeTimesTimes(m1_czech, v2_i)); // if so, return false if(dist > delta) { diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java index fdfac072..05ae0e13 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PCABasedCorrelationDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.correlation; 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 @@ -34,6 +34,7 @@ import de.lmu.ifi.dbs.elki.index.preprocessed.localpca.FilteredLocalPCAIndex; import de.lmu.ifi.dbs.elki.index.preprocessed.localpca.KNNQueryFilteredPCAIndex; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.linearalgebra.Matrix; +import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.math.linearalgebra.pca.PCAFilteredResult; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint; @@ -172,10 +173,10 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // for all strong eigenvectors of rv2 Matrix m1_czech = pca1.dissimilarityMatrix(); for(int i = 0; i < v2_strong.getColumnDimensionality(); i++) { - Matrix v2_i = v2_strong.getColumn(i); + Vector v2_i = v2_strong.getCol(i); // check, if distance of v2_i to the space of rv1 > delta // (i.e., if v2_i spans up a new dimension) - double dist = Math.sqrt(v2_i.transposeTimes(v2_i).get(0, 0) - v2_i.transposeTimes(m1_czech).times(v2_i).get(0, 0)); + double dist = Math.sqrt(v2_i.transposeTimes(v2_i) - v2_i.transposeTimesTimes(m1_czech, v2_i)); // if so, insert v2_i into v1 and adjust v1 // and compute m1_czech new, increase lambda1 @@ -188,10 +189,10 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista // for all strong eigenvectors of rv1 Matrix m2_czech = pca2.dissimilarityMatrix(); for(int i = 0; i < v1_strong.getColumnDimensionality(); i++) { - Matrix v1_i = v1_strong.getColumn(i); + Vector v1_i = v1_strong.getCol(i); // check, if distance of v1_i to the space of rv2 > delta // (i.e., if v1_i spans up a new dimension) - double dist = Math.sqrt(v1_i.transposeTimes(v1_i).get(0, 0) - v1_i.transposeTimes(m2_czech).times(v1_i).get(0, 0)); + double dist = Math.sqrt(v1_i.transposeTimes(v1_i) - v1_i.transposeTimes(m2_czech).times(v1_i).get(0)); // if so, insert v1_i into v2 and adjust v2 // and compute m2_czech new , increase lambda2 @@ -227,22 +228,22 @@ public class PCABasedCorrelationDistanceFunction extends AbstractIndexBasedDista * @param vector the vector to be inserted * @param corrDim the column at which the vector should be inserted */ - private void adjust(Matrix v, Matrix e_czech, Matrix vector, int corrDim) { + private void adjust(Matrix v, Matrix e_czech, Vector vector, int corrDim) { int dim = v.getRowDimensionality(); // set e_czech[corrDim][corrDim] := 1 e_czech.set(corrDim, corrDim, 1); // normalize v - Matrix v_i = vector.copy(); - Matrix sum = new Matrix(dim, 1); + Vector v_i = vector.copy(); + Vector sum = new Vector(dim); for(int k = 0; k < corrDim; k++) { - Matrix v_k = v.getColumn(k); - sum.plusEquals(v_k.timesEquals(v_i.scalarProduct(0, v_k, 0))); + Vector v_k = v.getCol(k); + sum.plusTimesEquals(v_k, v_i.transposeTimes(v_k)); } v_i.minusEquals(sum); - v_i.timesEquals(1.0 / Math.sqrt(v_i.scalarProduct(0, v_i, 0))); - v.setColumn(corrDim, v_i); + v_i.normalize(); + v.setCol(corrDim, v_i); } /** diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PearsonCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PearsonCorrelationDistanceFunction.java index 96e5262e..a618ae36 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PearsonCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/PearsonCorrelationDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.correlation; 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/correlation/SquaredPearsonCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/SquaredPearsonCorrelationDistanceFunction.java index 786fcd82..86d822d3 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/SquaredPearsonCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/SquaredPearsonCorrelationDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.correlation; 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/correlation/WeightedPearsonCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/WeightedPearsonCorrelationDistanceFunction.java index adabd90f..01e41f1b 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/WeightedPearsonCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/WeightedPearsonCorrelationDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.correlation; 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/correlation/WeightedSquaredPearsonCorrelationDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/WeightedSquaredPearsonCorrelationDistanceFunction.java index e7abca9b..8b5ecd98 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/WeightedSquaredPearsonCorrelationDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/WeightedSquaredPearsonCorrelationDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.correlation; 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/correlation/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/package-info.java index f82c7b92..2033dab1 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/correlation/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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedDoubleDistanceFunction.java index e541452e..9d92d727 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedDoubleDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.external; 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/external/DiskCacheBasedFloatDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedFloatDistanceFunction.java index b9ebbf9e..ff6b5e3d 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedFloatDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DiskCacheBasedFloatDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.external; 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/external/DistanceParser.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DistanceParser.java new file mode 100644 index 00000000..93874eaf --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DistanceParser.java @@ -0,0 +1,55 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction.external; + +/* + 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.io.InputStream; + +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; + +/** + * A DistanceParser shall provide a DistanceParsingResult by parsing an InputStream. + * + * @author Arthur Zimek + * + * @apiviz.uses DistanceParsingResult oneway - - «create» + * + * @param <D> distance type + */ +public interface DistanceParser<D extends Distance<D>> { + /** + * Parameter for distance function. + */ + public static final OptionID DISTANCE_ID = OptionID.getOrCreateOptionID("parser.distance", "Distance type used for parsing values."); + + /** + * Returns a list of the objects parsed from the specified input stream + * and a list of the labels associated with the objects. + * + * @param in the stream to parse objects from + * @return a list containing those objects parsed + * from the input stream and their associated labels. + */ + DistanceParsingResult<D> parse(InputStream in); +} diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DistanceParsingResult.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DistanceParsingResult.java new file mode 100644 index 00000000..1fc15b52 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/DistanceParsingResult.java @@ -0,0 +1,82 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction.external; + +/* + 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.Map; + +import de.lmu.ifi.dbs.elki.datasource.bundle.MultipleObjectsBundle; +import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; + +/** + * Provides a list of database objects and labels associated with these objects + * and a cache of precomputed distances between the database objects. + * + * @author Elke Achtert + * + * @param <D> distance type + */ +public class DistanceParsingResult<D extends Distance<D>> { + /** + * The cache of precomputed distances between the database objects. + */ + private final Map<DBIDPair, D> distanceCache; + + /** + * Objects representation (DBIDs and/or external IDs) + */ + private MultipleObjectsBundle objects; + + /** + * Provides a list of database objects, a list of label objects associated + * with these objects and cached distances between these objects. + * + * @param objectAndLabelList the list of database objects and labels + * associated with these objects + * @param distanceCache the cache of precomputed distances between the + * database objects + */ + public DistanceParsingResult(MultipleObjectsBundle objectAndLabelList, Map<DBIDPair, D> distanceCache) { + this.objects = objectAndLabelList; + this.distanceCache = distanceCache; + } + + /** + * Returns the cache of precomputed distances between the database objects. + * + * @return the cache of precomputed distances between the database objects + */ + public Map<DBIDPair, D> getDistanceCache() { + return distanceCache; + } + + /** + * Get the objects + * + * @return the objects bundle + */ + public MultipleObjectsBundle getObjects() { + return objects; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedDoubleDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedDoubleDistanceFunction.java index 46ee475d..50344460 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedDoubleDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedDoubleDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.external; 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 @@ -34,9 +34,6 @@ import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.datasource.parser.DistanceParser; -import de.lmu.ifi.dbs.elki.datasource.parser.DistanceParsingResult; -import de.lmu.ifi.dbs.elki.datasource.parser.NumberDistanceParser; import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractDBIDDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.utilities.FileUtil; @@ -45,6 +42,8 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; 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.parameterization.ChainedParameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.ListParameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.FileParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -135,7 +134,7 @@ public class FileBasedDoubleDistanceFunction extends AbstractDBIDDistanceFunctio * @return Collection of all IDs in the cache. */ public DBIDs getIDs() { - ModifiableDBIDs ids = DBIDUtil.newTreeSet(); + ModifiableDBIDs ids = DBIDUtil.newHashSet(); for(DBIDPair pair : cache.keySet()) { ids.add(pair.getFirst()); ids.add(pair.getSecond()); @@ -179,9 +178,14 @@ public class FileBasedDoubleDistanceFunction extends AbstractDBIDDistanceFunctio if(config.grab(MATRIX_PARAM)) { matrixfile = MATRIX_PARAM.getValue(); } + final ObjectParameter<DistanceParser<DoubleDistance>> PARSER_PARAM = new ObjectParameter<DistanceParser<DoubleDistance>>(PARSER_ID, DistanceParser.class, NumberDistanceParser.class); if(config.grab(PARSER_PARAM)) { - parser = PARSER_PARAM.instantiateClass(config); + ListParameterization parserConfig = new ListParameterization(); + parserConfig.addParameter(DistanceParser.DISTANCE_ID, DoubleDistance.class); + ChainedParameterization combinedConfig = new ChainedParameterization(parserConfig, config); + combinedConfig.errorsTo(config); + parser = PARSER_PARAM.instantiateClass(combinedConfig); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedFloatDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedFloatDistanceFunction.java index d01983af..10a4f206 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedFloatDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/FileBasedFloatDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.external; 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,9 +31,6 @@ import java.util.Map; import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; -import de.lmu.ifi.dbs.elki.datasource.parser.DistanceParser; -import de.lmu.ifi.dbs.elki.datasource.parser.DistanceParsingResult; -import de.lmu.ifi.dbs.elki.datasource.parser.NumberDistanceParser; import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractDBIDDistanceFunction; import de.lmu.ifi.dbs.elki.distance.distancevalue.FloatDistance; import de.lmu.ifi.dbs.elki.utilities.FileUtil; @@ -42,6 +39,8 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title; import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; 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.parameterization.ChainedParameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.ListParameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.FileParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; @@ -165,6 +164,10 @@ public class FileBasedFloatDistanceFunction extends AbstractDBIDDistanceFunction } final ObjectParameter<DistanceParser<FloatDistance>> PARSER_PARAM = new ObjectParameter<DistanceParser<FloatDistance>>(PARSER_ID, DistanceParser.class, NumberDistanceParser.class); if(config.grab(PARSER_PARAM)) { + ListParameterization parserConfig = new ListParameterization(); + parserConfig.addParameter(DistanceParser.DISTANCE_ID, FloatDistance.class); + ChainedParameterization combinedConfig = new ChainedParameterization(parserConfig, config); + combinedConfig.errorsTo(config); parser = PARSER_PARAM.instantiateClass(config); } } diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java new file mode 100644 index 00000000..c7a09e1a --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/NumberDistanceParser.java @@ -0,0 +1,240 @@ +package de.lmu.ifi.dbs.elki.distance.distancefunction.external; + +/* + 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.io.BufferedReader; +import java.io.IOException; +import java.io.InputStream; +import java.io.InputStreamReader; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.regex.Pattern; + +import de.lmu.ifi.dbs.elki.data.type.TypeUtil; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDPair; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; +import de.lmu.ifi.dbs.elki.datasource.bundle.MultipleObjectsBundle; +import de.lmu.ifi.dbs.elki.datasource.parser.AbstractParser; +import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.utilities.documentation.Description; +import de.lmu.ifi.dbs.elki.utilities.documentation.Title; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; + +/** + * Provides a parser for parsing one distance value per line. + * <p/> + * A line must have the following format: id1 id2 distanceValue, where id1 and + * id2 are integers representing the two ids belonging to the distance value. + * Lines starting with "#" will be ignored. + * + * @author Elke Achtert + * + * @apiviz.has NumberDistance + * + * @param <D> distance type + */ +@Title("Number Distance Parser") +@Description("Parser for the following line format:\n" + "id1 id2 distanceValue, where id1 and is2 are integers representing the two ids belonging to the distance value.\n" + " The ids and the distance value are separated by whitespace. Empty lines and lines beginning with \"#\" will be ignored.") +public class NumberDistanceParser<D extends NumberDistance<D, ?>> extends AbstractParser implements DistanceParser<D> { + /** + * The logger for this class. + */ + private static final Logging logger = Logging.getLogger(NumberDistanceParser.class); + + /** + * The distance function. + */ + private final D distanceFactory; + + /** + * Constructor. + * + * @param colSep + * @param quoteChar + * @param distanceFactory Distance factory to use + */ + public NumberDistanceParser(Pattern colSep, char quoteChar, D distanceFactory) { + super(colSep, quoteChar); + this.distanceFactory = distanceFactory; + } + + @Override + public DistanceParsingResult<D> parse(InputStream in) { + BufferedReader reader = new BufferedReader(new InputStreamReader(in)); + int lineNumber = 0; + + ModifiableDBIDs ids = DBIDUtil.newHashSet(); + Map<DBIDPair, D> distanceCache = new HashMap<DBIDPair, D>(); + try { + for(String line; (line = reader.readLine()) != null; lineNumber++) { + if(lineNumber % 10000 == 0 && logger.isDebugging()) { + logger.debugFine("parse " + lineNumber / 10000); + // logger.fine("parse " + lineNumber / 10000); + } + if(!line.startsWith(COMMENT) && line.length() > 0) { + List<String> entries = tokenize(line); + if(entries.size() != 3) { + throw new IllegalArgumentException("Line " + lineNumber + " does not have the " + "required input format: id1 id2 distanceValue! " + line); + } + + DBID id1, id2; + try { + id1 = DBIDUtil.importInteger(Integer.parseInt(entries.get(0))); + } + catch(NumberFormatException e) { + throw new IllegalArgumentException("Error in line " + lineNumber + ": id1 is no integer!"); + } + + try { + id2 = DBIDUtil.importInteger(Integer.parseInt(entries.get(1))); + } + catch(NumberFormatException e) { + throw new IllegalArgumentException("Error in line " + lineNumber + ": id2 is no integer!"); + } + + try { + D distance = distanceFactory.parseString(entries.get(2)); + put(id1, id2, distance, distanceCache); + ids.add(id1); + ids.add(id2); + } + catch(IllegalArgumentException e) { + throw new IllegalArgumentException("Error in line " + lineNumber + ":" + e.getMessage(), e); + } + } + } + } + catch(IOException e) { + throw new IllegalArgumentException("Error while parsing line " + lineNumber + "."); + } + + if(logger.isDebugging()) { + logger.debugFine("check"); + } + + // check if all distance values are specified + for(DBID id1 : ids) { + for(DBID id2 : ids) { + if(id2.getIntegerID() < id1.getIntegerID()) { + continue; + } + if(!containsKey(id1, id2, distanceCache)) { + throw new IllegalArgumentException("Distance value for " + id1 + " - " + id2 + " is missing!"); + } + } + } + + if(logger.isDebugging()) { + logger.debugFine("add to objectAndLabelsList"); + } + + // This is unusual for ELKI, but here we really need an ArrayList, not a + // DBIDs object. So convert. + List<DBID> objects = new ArrayList<DBID>(ids.size()); + for(DBID id : ids) { + objects.add(id); + } + return new DistanceParsingResult<D>(MultipleObjectsBundle.makeSimple(TypeUtil.DBID, objects), distanceCache); + } + + /** + * Puts the specified distance value for the given ids to the distance cache. + * + * @param id1 the first id + * @param id2 the second id + * @param distance the distance value + * @param cache the distance cache + */ + private void put(DBID id1, DBID id2, D distance, Map<DBIDPair, D> cache) { + // the smaller id is the first key + if(id1.getIntegerID() > id2.getIntegerID()) { + put(id2, id1, distance, cache); + return; + } + + D oldDistance = cache.put(DBIDUtil.newPair(id1, id2), distance); + + if(oldDistance != null) { + throw new IllegalArgumentException("Distance value for specified ids is already assigned!"); + } + } + + /** + * Returns <tt>true</tt> if the specified distance cache contains a distance + * value for the specified ids. + * + * @param id1 the first id + * @param id2 the second id + * @param cache the distance cache + * @return <tt>true</tt> if this cache contains a distance value for the + * specified ids, false otherwise + */ + public boolean containsKey(DBID id1, DBID id2, Map<DBIDPair, D> cache) { + if(id1.getIntegerID() > id2.getIntegerID()) { + return containsKey(id2, id1, cache); + } + + return cache.containsKey(DBIDUtil.newPair(id1, id2)); + } + + @Override + protected Logging getLogger() { + return logger; + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer<D extends NumberDistance<D, ?>> extends AbstractParser.Parameterizer { + /** + * The distance function. + */ + protected D distanceFactory; + + @Override + protected void makeOptions(Parameterization config) { + super.makeOptions(config); + ObjectParameter<D> distFuncP = new ObjectParameter<D>(DISTANCE_ID, Distance.class); + if(config.grab(distFuncP)) { + distanceFactory = distFuncP.instantiateClass(config); + } + } + + @Override + protected NumberDistanceParser<D> makeInstance() { + return new NumberDistanceParser<D>(colSep, quoteChar, distanceFactory); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/package-info.java index 3db358d3..3099122a 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/external/package-info.java @@ -6,7 +6,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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java index f1c8b1b3..d4d7d9f5 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/DimensionSelectingLatLngDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.geo; 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/geo/LatLngDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/LatLngDistanceFunction.java index 2b3d3805..c50b3326 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/LatLngDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/LatLngDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.geo; 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/geo/LngLatDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/LngLatDistanceFunction.java index 053e2f18..b48e7cae 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/LngLatDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/LngLatDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.geo; 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/geo/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/package-info.java index e71080fb..913447fd 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/geo/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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/package-info.java index 85bb15f8..c47db2f8 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/package-info.java @@ -37,7 +37,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 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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java index 3360e7ba..a504f680 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/AbstractEditDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries; 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/timeseries/DTWDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/DTWDistanceFunction.java index 2f0e9045..4461a680 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/DTWDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/DTWDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries; 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/timeseries/EDRDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java index a0c20f6e..c918ab03 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/EDRDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries; 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/timeseries/ERPDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java index 3d41e0c7..40ed00ba 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/ERPDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries; 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,7 +48,7 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { /** * Keeps the currently set g. */ - private double g; + private final double g; /** * Constructor. @@ -76,10 +76,7 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { // size of edit distance band // bandsize is the maximum allowed distance to the diagonal - int band = (int) Math.ceil(v2.getDimensionality() * bandSize); - - // g parameter for local usage - double gValue = g; + final int band = (int) Math.ceil(v2.getDimensionality() * bandSize); for(int i = 0; i < v1.getDimensionality(); i++) { // Swap current and prev arrays. We'll just overwrite the new curr. @@ -101,11 +98,11 @@ public class ERPDistanceFunction extends AbstractEditDistanceFunction { if(Math.abs(i - j) <= band) { // compute squared distance of feature vectors double val1 = v1.doubleValue(i + 1); - double val2 = gValue; + double val2 = g; double diff = (val1 - val2); final double d1 = Math.sqrt(diff * diff); - val1 = gValue; + val1 = g; val2 = v2.doubleValue(j + 1); diff = (val1 - val2); final double d2 = Math.sqrt(diff * diff); diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java index 3264db7e..b9a26c8b 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/LCSSDistanceFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancefunction.timeseries; 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/timeseries/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/package-info.java index bb252054..cad7fba9 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancefunction/timeseries/package-info.java @@ -8,7 +8,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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/AbstractDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/AbstractDistance.java index b239cea2..3e5e86af 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/AbstractDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/AbstractDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/BitDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/BitDistance.java index 9b579452..24e33d35 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/BitDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/BitDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/CorrelationDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/CorrelationDistance.java index 4a15ab80..f1203887 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/CorrelationDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/CorrelationDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/Distance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/Distance.java index 838dcfd6..73e11fa6 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/Distance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/Distance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/DoubleDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/DoubleDistance.java index 102fcc94..ce63b4e1 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/DoubleDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/DoubleDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/FloatDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/FloatDistance.java index 87fca22f..5aaaab91 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/FloatDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/FloatDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/IntegerDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/IntegerDistance.java index 0eb77593..b99b88c3 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/IntegerDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/IntegerDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/NumberDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/NumberDistance.java index b5b534ee..a3aff609 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/NumberDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/NumberDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/PCACorrelationDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PCACorrelationDistance.java index ff7b6bf4..c2e2da6d 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PCACorrelationDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PCACorrelationDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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 @@ -147,6 +147,6 @@ public class PCACorrelationDistance extends CorrelationDistance<PCACorrelationDi @Override public boolean isUndefinedDistance() { - return correlationValue == -1 && euclideanValue == Double.NaN; + return correlationValue == -1 && Double.isNaN(euclideanValue); } }
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PreferenceVectorBasedCorrelationDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PreferenceVectorBasedCorrelationDistance.java index 694650cf..c62cacc4 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PreferenceVectorBasedCorrelationDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/PreferenceVectorBasedCorrelationDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/SubspaceDistance.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/SubspaceDistance.java index cb929c44..3d4b7f4c 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/SubspaceDistance.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/SubspaceDistance.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.distancevalue; 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/distancevalue/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/package-info.java index 430c1456..30fcdf35 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/distancevalue/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/distancevalue/package-info.java @@ -10,7 +10,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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/package-info.java index 50fc45a2..801d4314 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/package-info.java @@ -7,7 +7,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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractDBIDSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractDBIDSimilarityFunction.java index 12a39916..163438ce 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractDBIDSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractDBIDSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/AbstractIndexBasedSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractIndexBasedSimilarityFunction.java index ad065c68..72f44e4d 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractIndexBasedSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractIndexBasedSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/AbstractPrimitiveSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractPrimitiveSimilarityFunction.java index a37efe9d..c408d1bb 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractPrimitiveSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/AbstractPrimitiveSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/DBIDSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/DBIDSimilarityFunction.java index d93c93f9..e7316115 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/DBIDSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/DBIDSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/FractionalSharedNearestNeighborSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/FractionalSharedNearestNeighborSimilarityFunction.java index c909cd6c..ec4460d8 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/FractionalSharedNearestNeighborSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/FractionalSharedNearestNeighborSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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 @@ -25,8 +25,9 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; import java.util.Iterator; +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; import de.lmu.ifi.dbs.elki.database.ids.DBID; -import de.lmu.ifi.dbs.elki.database.ids.TreeSetDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; import de.lmu.ifi.dbs.elki.index.preprocessed.snn.SharedNearestNeighborIndex; @@ -47,7 +48,7 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameteriz * @param <O> object type */ // todo arthur comment class -public class FractionalSharedNearestNeighborSimilarityFunction<O> extends AbstractIndexBasedSimilarityFunction<O, SharedNearestNeighborIndex<O>, TreeSetDBIDs, DoubleDistance> implements NormalizedSimilarityFunction<O, DoubleDistance> { +public class FractionalSharedNearestNeighborSimilarityFunction<O> extends AbstractIndexBasedSimilarityFunction<O, SharedNearestNeighborIndex<O>, ArrayDBIDs, DoubleDistance> implements NormalizedSimilarityFunction<O, DoubleDistance> { /** * Constructor. * @@ -73,7 +74,7 @@ public class FractionalSharedNearestNeighborSimilarityFunction<O> extends Abstra * * @param <T> Object type */ - public static class Instance<T> extends AbstractIndexBasedSimilarityFunction.Instance<T, SharedNearestNeighborIndex<T>, TreeSetDBIDs, DoubleDistance> { + public static class Instance<T> extends AbstractIndexBasedSimilarityFunction.Instance<T, SharedNearestNeighborIndex<T>, ArrayDBIDs, DoubleDistance> { /** * Constructor. * @@ -84,7 +85,14 @@ public class FractionalSharedNearestNeighborSimilarityFunction<O> extends Abstra super(database, preprocessor); } - static protected int countSharedNeighbors(TreeSetDBIDs neighbors1, TreeSetDBIDs neighbors2) { + /** + * Compute the intersection size. + * + * @param neighbors1 SORTED neighbor ids of first + * @param neighbors2 SORTED neighbor ids of second + * @return Intersection size + */ + static protected int countSharedNeighbors(DBIDs neighbors1, DBIDs neighbors2) { int intersection = 0; Iterator<DBID> iter1 = neighbors1.iterator(); Iterator<DBID> iter2 = neighbors2.iterator(); @@ -109,8 +117,8 @@ public class FractionalSharedNearestNeighborSimilarityFunction<O> extends Abstra @Override public DoubleDistance similarity(DBID id1, DBID id2) { - TreeSetDBIDs neighbors1 = index.getNearestNeighborSet(id1); - TreeSetDBIDs neighbors2 = index.getNearestNeighborSet(id2); + DBIDs neighbors1 = index.getNearestNeighborSet(id1); + DBIDs neighbors2 = index.getNearestNeighborSet(id2); int intersection = countSharedNeighbors(neighbors1, neighbors2); return new DoubleDistance((double) intersection / index.getNumberOfNeighbors()); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/IndexBasedSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/IndexBasedSimilarityFunction.java index 95d854c0..29ae9ce3 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/IndexBasedSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/IndexBasedSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/InvertedDistanceSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/InvertedDistanceSimilarityFunction.java new file mode 100644 index 00000000..ad193d9e --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/InvertedDistanceSimilarityFunction.java @@ -0,0 +1,74 @@ +package de.lmu.ifi.dbs.elki.distance.similarityfunction; + +/* + 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 de.lmu.ifi.dbs.elki.data.type.SimpleTypeInformation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancevalue.DoubleDistance; +import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; + +/** + * Adapter to use a primitive number-distance as similarity measure, by computing + * 1/distance. + * + * @author Erich Schubert + * + * @param <O> Object type + */ +public class InvertedDistanceSimilarityFunction<O> extends AbstractPrimitiveSimilarityFunction<O, DoubleDistance> { + /** + * Parameter to specify the similarity function to derive the distance between + * database objects from. Must extend + * {@link de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction} . + * <p> + * Key: {@code -adapter.distancefunction} + * </p> + * <p> + * Default value: + * {@link de.lmu.ifi.dbs.elki.distance.distancefunction.EuclideanDistanceFunction} + * </p> + */ + public static final OptionID DISTANCE_FUNCTION_ID = OptionID.getOrCreateOptionID("adapter.distancefunction", "Distance function to derive the similarity between database objects from."); + + /** + * Holds the similarity function. + */ + protected PrimitiveDistanceFunction<? super O, ? extends NumberDistance<?, ?>> distanceFunction; + + @Override + public DoubleDistance getDistanceFactory() { + return DoubleDistance.FACTORY; + } + + @Override + public SimpleTypeInformation<? super O> getInputTypeRestriction() { + return distanceFunction.getInputTypeRestriction(); + } + + @Override + public DoubleDistance similarity(O o1, O o2) { + double dist = distanceFunction.distance(o1, o2).doubleValue(); + return new DoubleDistance(1. / dist); + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedPrimitiveSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedPrimitiveSimilarityFunction.java index f5347e71..fc86a3bc 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedPrimitiveSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedPrimitiveSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/NormalizedSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedSimilarityFunction.java index 5979ad3f..b2be1a56 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/NormalizedSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/PrimitiveSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/PrimitiveSimilarityFunction.java index edb57ca0..b5642d0c 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/PrimitiveSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/PrimitiveSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/SharedNearestNeighborSimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SharedNearestNeighborSimilarityFunction.java index 74c2534c..0025ee75 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SharedNearestNeighborSimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SharedNearestNeighborSimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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 @@ -26,6 +26,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; import java.util.Iterator; import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.ids.SetDBIDs; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.distance.distancevalue.IntegerDistance; @@ -60,7 +61,14 @@ public class SharedNearestNeighborSimilarityFunction<O> extends AbstractIndexBas return IntegerDistance.FACTORY; } - static protected int countSharedNeighbors(SetDBIDs neighbors1, SetDBIDs neighbors2) { + /** + * Compute the intersection size + * + * @param neighbors1 SORTED neighbors of first + * @param neighbors2 SORTED neighbors of second + * @return Intersection size + */ + static protected int countSharedNeighbors(DBIDs neighbors1, DBIDs neighbors2) { int intersection = 0; Iterator<DBID> iter1 = neighbors1.iterator(); Iterator<DBID> iter2 = neighbors2.iterator(); @@ -112,8 +120,8 @@ public class SharedNearestNeighborSimilarityFunction<O> extends AbstractIndexBas @Override public IntegerDistance similarity(DBID id1, DBID id2) { - SetDBIDs neighbors1 = index.getNearestNeighborSet(id1); - SetDBIDs neighbors2 = index.getNearestNeighborSet(id2); + DBIDs neighbors1 = index.getNearestNeighborSet(id1); + DBIDs neighbors2 = index.getNearestNeighborSet(id2); return new IntegerDistance(countSharedNeighbors(neighbors1, neighbors2)); } diff --git a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SimilarityFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SimilarityFunction.java index 687d17d7..d8324a80 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SimilarityFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/SimilarityFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction; 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/similarityfunction/kernel/FooKernelFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/FooKernelFunction.java index 24a9efda..093cf652 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/FooKernelFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/FooKernelFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel; 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/similarityfunction/kernel/KernelMatrix.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/KernelMatrix.java index c41a2e91..a8b6d8fc 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/KernelMatrix.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/KernelMatrix.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel; 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/similarityfunction/kernel/LinearKernelFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/LinearKernelFunction.java index 7d3f85d3..6cde55a6 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/LinearKernelFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/LinearKernelFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel; 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/similarityfunction/kernel/PolynomialKernelFunction.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/PolynomialKernelFunction.java index c3ad7e3e..e32f5b45 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/PolynomialKernelFunction.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/PolynomialKernelFunction.java @@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.distance.similarityfunction.kernel; 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/similarityfunction/kernel/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/package-info.java index a059de3a..6d2e46fc 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/kernel/package-info.java @@ -7,7 +7,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 diff --git a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/package-info.java b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/package-info.java index 033daf1c..ba53fba3 100644 --- a/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/package-info.java +++ b/src/de/lmu/ifi/dbs/elki/distance/similarityfunction/package-info.java @@ -7,7 +7,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 |