diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial')
21 files changed, 415 insertions, 441 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractDistanceBasedSpatialOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractDistanceBasedSpatialOutlier.java index 1caf7582..f37ee182 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractDistanceBasedSpatialOutlier.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractDistanceBasedSpatialOutlier.java @@ -45,7 +45,7 @@ public abstract class AbstractDistanceBasedSpatialOutlier<N, O, D extends Number /** * Parameter to specify the non spatial distance function to use */ - public static final OptionID NON_SPATIAL_DISTANCE_FUNCTION_ID = OptionID.getOrCreateOptionID("spatialoutlier.nonspatialdistance", "The distance function to use for non spatial attributes"); + public static final OptionID NON_SPATIAL_DISTANCE_FUNCTION_ID = new OptionID("spatialoutlier.nonspatialdistance", "The distance function to use for non spatial attributes"); /** * The distance function to use @@ -84,7 +84,7 @@ public abstract class AbstractDistanceBasedSpatialOutlier<N, O, D extends Number * @param <O> Non-spatial object type * @param <D> Distance value type */ - public static abstract class Parameterizer<N, O, D extends NumberDistance<D, ?>> extends AbstractNeighborhoodOutlier.Parameterizer<N> { + public abstract static class Parameterizer<N, O, D extends NumberDistance<D, ?>> extends AbstractNeighborhoodOutlier.Parameterizer<N> { /** * The distance function to use on the non-spatial attributes. */ diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractNeighborhoodOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractNeighborhoodOutlier.java index f0c05e1e..d3770504 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractNeighborhoodOutlier.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/AbstractNeighborhoodOutlier.java @@ -44,7 +44,7 @@ public abstract class AbstractNeighborhoodOutlier<O> extends AbstractAlgorithm<O /** * Parameter to specify the neighborhood predicate to use. */ - public static final OptionID NEIGHBORHOOD_ID = OptionID.getOrCreateOptionID("neighborhood", "The neighborhood predicate to use in comparison step."); + public static final OptionID NEIGHBORHOOD_ID = new OptionID("neighborhood", "The neighborhood predicate to use in comparison step."); /** * Our predicate to obtain the neighbors @@ -79,7 +79,7 @@ public abstract class AbstractNeighborhoodOutlier<O> extends AbstractAlgorithm<O * * @param <O> Object type */ - public static abstract class Parameterizer<O> extends AbstractParameterizer { + public abstract static class Parameterizer<O> extends AbstractParameterizer { /** * The predicate to obtain the neighbors. */ diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuGLSBackwardSearchAlgorithm.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuGLSBackwardSearchAlgorithm.java index 7f3bac29..cd5670f7 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuGLSBackwardSearchAlgorithm.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuGLSBackwardSearchAlgorithm.java @@ -37,13 +37,13 @@ import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; -import de.lmu.ifi.dbs.elki.database.query.DistanceResultPair; 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.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.ProxyView; import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult; import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.DoubleMinMax; @@ -52,7 +52,6 @@ import de.lmu.ifi.dbs.elki.math.statistics.distribution.NormalDistribution; import de.lmu.ifi.dbs.elki.result.outlier.BasicOutlierScoreMeta; import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult; import de.lmu.ifi.dbs.elki.result.outlier.OutlierScoreMeta; -import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; import de.lmu.ifi.dbs.elki.utilities.documentation.Title; import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; @@ -85,11 +84,11 @@ import de.lmu.ifi.dbs.elki.utilities.pairs.Pair; */ @Title("GLS-Backward Search") @Reference(authors = "F. Chen and C.-T. Lu and A. P. Boedihardjo", title = "GLS-SOD: A Generalized Local Statistical Approach for Spatial Outlier Detection", booktitle = "Proc. 16th ACM SIGKDD international conference on Knowledge discovery and data mining", url = "http://dx.doi.org/10.1145/1835804.1835939") -public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm<V, D, OutlierResult> implements OutlierAlgorithm { +public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?>, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm<V, D, OutlierResult> implements OutlierAlgorithm { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(CTLuGLSBackwardSearchAlgorithm.class); + private static final Logging LOG = Logging.getLogger(CTLuGLSBackwardSearchAlgorithm.class); /** * Parameter Alpha - significance niveau @@ -121,7 +120,7 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte * @param relationy Attribute relation * @return Algorithm result */ - public OutlierResult run(Relation<V> relationx, Relation<? extends NumberVector<?, ?>> relationy) { + public OutlierResult run(Relation<V> relationx, Relation<? extends NumberVector<?>> relationy) { WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relationx.getDBIDs(), DataStoreFactory.HINT_STATIC); DoubleMinMax mm = new DoubleMinMax(0.0, 0.0); @@ -130,7 +129,7 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte ModifiableDBIDs idview = DBIDUtil.newHashSet(relationx.getDBIDs()); ProxyView<V> proxy = new ProxyView<V>(relationx.getDatabase(), idview, relationx); - double phialpha = NormalDistribution.standardNormalQuantile(1.0 - alpha / 2); + double phialpha = NormalDistribution.standardNormalQuantile(1.0 - alpha *.5); // Detect outliers while significant. while(true) { Pair<DBID, Double> candidate = singleIteration(proxy, relationy); @@ -138,15 +137,15 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte break; } scores.putDouble(candidate.first, candidate.second); - if (!Double.isNaN(candidate.second)) { + if(!Double.isNaN(candidate.second)) { mm.put(candidate.second); } idview.remove(candidate.first); } // Remaining objects are inliers - for (DBIDIter iter = idview.iter(); iter.valid(); iter.advance()) { - scores.putDouble(iter.getDBID(), 0.0); + for(DBIDIter iter = idview.iter(); iter.valid(); iter.advance()) { + scores.putDouble(iter, 0.0); } } @@ -162,9 +161,9 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte * @param relationy Attribute relation * @return Top outlier and associated score */ - private Pair<DBID, Double> singleIteration(Relation<V> relationx, Relation<? extends NumberVector<?, ?>> relationy) { - final int dim = DatabaseUtil.dimensionality(relationx); - final int dimy = DatabaseUtil.dimensionality(relationy); + private Pair<DBID, Double> singleIteration(Relation<V> relationx, Relation<? extends NumberVector<?>> relationy) { + final int dim = RelationUtil.dimensionality(relationx); + final int dimy = RelationUtil.dimensionality(relationy); assert (dim == 2); KNNQuery<V, D> knnQuery = QueryUtil.getKNNQuery(relationx, getDistanceFunction(), k + 1); @@ -177,47 +176,51 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte Matrix X = new Matrix(ids.size(), 6); Matrix F = new Matrix(ids.size(), ids.size()); Matrix Y = new Matrix(ids.size(), dimy); - for(int i = 0; i < ids.size(); i++) { - DBID id = ids.get(i); - - // Fill the data matrix - { - V vec = relationx.get(id); - double la = vec.doubleValue(1); - double lo = vec.doubleValue(2); - X.set(i, 0, 1.0); - X.set(i, 1, la); - X.set(i, 2, lo); - X.set(i, 3, la * lo); - X.set(i, 4, la * la); - X.set(i, 5, lo * lo); - } - { - for(int d = 0; d < dimy; d++) { - double idy = relationy.get(id).doubleValue(d + 1); - Y.set(i, d, idy); + { + int i = 0; + for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) { + // Fill the data matrix + { + V vec = relationx.get(id); + double la = vec.doubleValue(0); + double lo = vec.doubleValue(1); + X.set(i, 0, 1.0); + X.set(i, 1, la); + X.set(i, 2, lo); + X.set(i, 3, la * lo); + X.set(i, 4, la * la); + X.set(i, 5, lo * lo); } - } - // Fill the neighborhood matrix F: - { - KNNResult<D> neighbors = knnQuery.getKNNForDBID(id, k + 1); - ModifiableDBIDs neighborhood = DBIDUtil.newArray(neighbors.size()); - for(DistanceResultPair<D> dpair : neighbors) { - if(id.sameDBID(dpair.getDBID())) { - continue; + { + final NumberVector<?> vecy = relationy.get(id); + for(int d = 0; d < dimy; d++) { + double idy = vecy.doubleValue(d); + Y.set(i, d, idy); } - neighborhood.add(dpair.getDBID()); } - // Weight object itself positively. - F.set(i, i, 1.0); - final int nweight = -1 / neighborhood.size(); - // We need to find the index positions of the neighbors, unfortunately. - for (DBIDIter iter = neighborhood.iter(); iter.valid(); iter.advance()) { - int pos = ids.binarySearch(iter.getDBID()); - assert (pos >= 0); - F.set(pos, i, nweight); + + // Fill the neighborhood matrix F: + { + KNNResult<D> neighbors = knnQuery.getKNNForDBID(id, k + 1); + ModifiableDBIDs neighborhood = DBIDUtil.newArray(neighbors.size()); + for(DBIDIter neighbor = neighbors.iter(); neighbor.valid(); neighbor.advance()) { + if(DBIDUtil.equal(id, neighbor)) { + continue; + } + neighborhood.add(neighbor); + } + // Weight object itself positively. + F.set(i, i, 1.0); + final int nweight = -1 / neighborhood.size(); + // We need to find the index positions of the neighbors, + // unfortunately. + for(DBIDIter iter = neighborhood.iter(); iter.valid(); iter.advance()) { + int pos = ids.binarySearch(iter); + assert (pos >= 0); + F.set(pos, i, nweight); + } } } } @@ -236,13 +239,13 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte DBID worstid = null; double worstscore = Double.NEGATIVE_INFINITY; - for(int i = 0; i < ids.size(); i++) { - DBID id = ids.get(i); + int i = 0; + for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) { double err = E.getRow(i).euclideanLength(); // double err = Math.abs(E.get(i, 0)); if(err > worstscore) { worstscore = err; - worstid = id; + worstid = DBIDUtil.deref(id); } } @@ -256,7 +259,7 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte @Override protected Logging getLogger() { - return logger; + return LOG; } /** @@ -269,16 +272,16 @@ public class CTLuGLSBackwardSearchAlgorithm<V extends NumberVector<?, ?>, D exte * @param <V> Input vector type * @param <D> Distance type */ - public static class Parameterizer<V extends NumberVector<?, ?>, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm.Parameterizer<V, D> { + public static class Parameterizer<V extends NumberVector<?>, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm.Parameterizer<V, D> { /** * Holds the alpha value - significance niveau */ - public static final OptionID ALPHA_ID = OptionID.getOrCreateOptionID("glsbs.alpha", "Significance niveau"); + public static final OptionID ALPHA_ID = new OptionID("glsbs.alpha", "Significance niveau"); /** * Parameter to specify the k nearest neighbors */ - public static final OptionID K_ID = OptionID.getOrCreateOptionID("glsbs.k", "k nearest neighbors to use"); + public static final OptionID K_ID = new OptionID("glsbs.k", "k nearest neighbors to use"); /** * Parameter Alpha - significance niveau diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMeanMultipleAttributes.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMeanMultipleAttributes.java index a0c09057..2caee128 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMeanMultipleAttributes.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMeanMultipleAttributes.java @@ -31,11 +31,11 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.DoubleMinMax; import de.lmu.ifi.dbs.elki.math.linearalgebra.Centroid; @@ -45,7 +45,6 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.result.outlier.BasicOutlierScoreMeta; import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult; import de.lmu.ifi.dbs.elki.result.outlier.OutlierScoreMeta; -import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; /** @@ -72,11 +71,11 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @param <O> Attribute Vector */ @Reference(authors = "Chang-Tien Lu and Dechang Chen and Yufeng Kou", title = "Detecting Spatial Outliers with Multiple Attributes", booktitle = "Proc. 15th IEEE International Conference on Tools with Artificial Intelligence, 2003", url = "http://dx.doi.org/10.1109/TAI.2003.1250179") -public class CTLuMeanMultipleAttributes<N, O extends NumberVector<?, ?>> extends AbstractNeighborhoodOutlier<N> { +public class CTLuMeanMultipleAttributes<N, O extends NumberVector<?>> extends AbstractNeighborhoodOutlier<N> { /** * logger */ - public static final Logging logger = Logging.getLogger(CTLuMeanMultipleAttributes.class); + private static final Logging LOG = Logging.getLogger(CTLuMeanMultipleAttributes.class); /** * Constructor @@ -89,28 +88,27 @@ public class CTLuMeanMultipleAttributes<N, O extends NumberVector<?, ?>> extends @Override protected Logging getLogger() { - return logger; + return LOG; } public OutlierResult run(Relation<N> spatial, Relation<O> attributes) { - if(logger.isDebugging()) { - logger.debug("Dimensionality: " + DatabaseUtil.dimensionality(attributes)); + if(LOG.isDebugging()) { + LOG.debug("Dimensionality: " + RelationUtil.dimensionality(attributes)); } final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(spatial); - CovarianceMatrix covmaker = new CovarianceMatrix(DatabaseUtil.dimensionality(attributes)); + CovarianceMatrix covmaker = new CovarianceMatrix(RelationUtil.dimensionality(attributes)); WritableDataStore<Vector> deltas = DataStoreUtil.makeStorage(attributes.getDBIDs(), DataStoreFactory.HINT_TEMP, Vector.class); for(DBIDIter iditer = attributes.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - final O obj = attributes.get(id); - final DBIDs neighbors = npred.getNeighborDBIDs(id); + final O obj = attributes.get(iditer); + final DBIDs neighbors = npred.getNeighborDBIDs(iditer); // TODO: remove object itself from neighbors? // Mean vector "g" Vector mean = Centroid.make(attributes, neighbors); // Delta vector "h" - Vector delta = obj.getColumnVector().minus(mean); - deltas.put(id, delta); + Vector delta = obj.getColumnVector().minusEquals(mean); + deltas.put(iditer, delta); covmaker.put(delta); } // Finalize covariance matrix: @@ -120,11 +118,10 @@ public class CTLuMeanMultipleAttributes<N, O extends NumberVector<?, ?>> extends DoubleMinMax minmax = new DoubleMinMax(); WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(attributes.getDBIDs(), DataStoreFactory.HINT_STATIC); for(DBIDIter iditer = attributes.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - Vector temp = deltas.get(id).minus(mean); + Vector temp = deltas.get(iditer).minus(mean); final double score = temp.transposeTimesTimes(cmati, temp); minmax.put(score); - scores.putDouble(id, score); + scores.putDouble(iditer, score); } Relation<Double> scoreResult = new MaterializedRelation<Double>("mean multiple attributes spatial outlier", "mean-multipleattributes-outlier", TypeUtil.DOUBLE, scores, attributes.getDBIDs()); @@ -149,7 +146,7 @@ public class CTLuMeanMultipleAttributes<N, O extends NumberVector<?, ?>> extends * @param <N> Neighborhood type * @param <O> Attribute object type */ - public static class Parameterizer<N, O extends NumberVector<?, ?>> extends AbstractNeighborhoodOutlier.Parameterizer<N> { + public static class Parameterizer<N, O extends NumberVector<?>> extends AbstractNeighborhoodOutlier.Parameterizer<N> { @Override protected CTLuMeanMultipleAttributes<N, O> makeInstance() { return new CTLuMeanMultipleAttributes<N, O>(npredf); diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianAlgorithm.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianAlgorithm.java index 20ab9a00..7755a459 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianAlgorithm.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianAlgorithm.java @@ -1,26 +1,27 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.spatial;
-/* -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/>. -*/ +
+/*
+ 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.algorithm.outlier.spatial.neighborhood.NeighborSetPredicate;
import de.lmu.ifi.dbs.elki.data.NumberVector;
@@ -30,8 +31,8 @@ import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil;
import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore;
-import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
+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.relation.MaterializedRelation;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
@@ -60,22 +61,22 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Title; * The Difference e = non-spatial-Attribute-Value - Median (Neighborhood) is
* computed.<br>
* The Spatial Objects with the highest standardized e value are Spatial
- * Outliers. </p>
+ * Outliers.
*
* @author Ahmed Hettab
*
* @param <N> Neighborhood type
*/
@Title("Median Algorithm for Spatial Outlier Detection")
-@Reference(authors = "C.-T. Lu and D. Chen and Y. Kou", title = "Algorithms for Spatial Outlier Detection", booktitle = "Proc. 3rd IEEE International Conference on Data Mining", url="http://dx.doi.org/10.1109/ICDM.2003.1250986")
+@Reference(authors = "C.-T. Lu and D. Chen and Y. Kou", title = "Algorithms for Spatial Outlier Detection", booktitle = "Proc. 3rd IEEE International Conference on Data Mining", url = "http://dx.doi.org/10.1109/ICDM.2003.1250986")
public class CTLuMedianAlgorithm<N> extends AbstractNeighborhoodOutlier<N> {
/**
* The logger for this class.
*/
- private static final Logging logger = Logging.getLogger(CTLuMedianAlgorithm.class);
+ private static final Logging LOG = Logging.getLogger(CTLuMedianAlgorithm.class);
/**
- * Constructor
+ * Constructor.
*
* @param npredf Neighborhood predicate
*/
@@ -84,42 +85,40 @@ public class CTLuMedianAlgorithm<N> extends AbstractNeighborhoodOutlier<N> { }
/**
- * Main method
+ * Main method.
*
* @param nrel Neighborhood relation
* @param relation Data relation (1d!)
* @return Outlier detection result
*/
- public OutlierResult run(Relation<N> nrel, Relation<? extends NumberVector<?, ?>> relation) {
+ public OutlierResult run(Relation<N> nrel, Relation<? extends NumberVector<?>> relation) {
final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(nrel);
WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
MeanVariance mv = new MeanVariance();
- for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- DBIDs neighbors = npred.getNeighborDBIDs(id);
+ for (DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
+ DBIDs neighbors = npred.getNeighborDBIDs(iditer);
final double median;
{
double[] fi = new double[neighbors.size()];
// calculate and store Median of neighborhood
int c = 0;
- for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
- if(id.sameDBID(iter)) {
+ for (DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
+ if (DBIDUtil.equal(iditer, iter)) {
continue;
}
- fi[c] = relation.get(iter).doubleValue(1);
+ fi[c] = relation.get(iter).doubleValue(0);
c++;
}
- if(c > 0) {
+ if (c > 0) {
median = QuickSelect.median(fi, 0, c);
- }
- else {
- median = relation.get(id).doubleValue(1);
+ } else {
+ median = relation.get(iditer).doubleValue(0);
}
}
- double h = relation.get(id).doubleValue(1) - median;
- scores.putDouble(id, h);
+ double h = relation.get(iditer).doubleValue(0) - median;
+ scores.putDouble(iditer, h);
mv.put(h);
}
@@ -127,11 +126,10 @@ public class CTLuMedianAlgorithm<N> extends AbstractNeighborhoodOutlier<N> { final double mean = mv.getMean();
final double stddev = mv.getNaiveStddev();
DoubleMinMax minmax = new DoubleMinMax();
- for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- double score = Math.abs((scores.doubleValue(id) - mean) / stddev);
+ for (DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
+ double score = Math.abs((scores.doubleValue(iditer) - mean) / stddev);
minmax.put(score);
- scores.putDouble(id, score);
+ scores.putDouble(iditer, score);
}
Relation<Double> scoreResult = new MaterializedRelation<Double>("MO", "Median-outlier", TypeUtil.DOUBLE, scores, relation.getDBIDs());
@@ -143,16 +141,16 @@ public class CTLuMedianAlgorithm<N> extends AbstractNeighborhoodOutlier<N> { @Override
protected Logging getLogger() {
- return logger;
+ return LOG;
}
@Override
public TypeInformation[] getInputTypeRestriction() {
- return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), VectorFieldTypeInformation.get(NumberVector.class, 1));
+ return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), new VectorFieldTypeInformation<NumberVector<?>>(NumberVector.class, 1));
}
/**
- * Parameterization class
+ * Parameterization class.
*
* @author Ahmed Hettab
*
@@ -166,4 +164,4 @@ public class CTLuMedianAlgorithm<N> extends AbstractNeighborhoodOutlier<N> { return new CTLuMedianAlgorithm<N>(npredf);
}
}
-}
\ No newline at end of file +}
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianMultipleAttributes.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianMultipleAttributes.java index c8bcba74..0d515ac7 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianMultipleAttributes.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMedianMultipleAttributes.java @@ -31,11 +31,11 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; import de.lmu.ifi.dbs.elki.logging.Logging; import de.lmu.ifi.dbs.elki.math.DoubleMinMax; import de.lmu.ifi.dbs.elki.math.linearalgebra.CovarianceMatrix; @@ -44,7 +44,6 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.result.outlier.BasicOutlierScoreMeta; import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult; import de.lmu.ifi.dbs.elki.result.outlier.OutlierScoreMeta; -import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil; import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect; import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; @@ -73,11 +72,11 @@ import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; * @param <O> Non Spatial Vector */ @Reference(authors = "Chang-Tien Lu and Dechang Chen and Yufeng Kou", title = "Detecting Spatial Outliers with Multiple Attributes", booktitle = "Proc. 15th IEEE International Conference on Tools with Artificial Intelligence, 2003", url = "http://dx.doi.org/10.1109/TAI.2003.1250179") -public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> extends AbstractNeighborhoodOutlier<N> { +public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?>> extends AbstractNeighborhoodOutlier<N> { /** * logger */ - public static final Logging logger = Logging.getLogger(CTLuMedianMultipleAttributes.class); + private static final Logging LOG = Logging.getLogger(CTLuMedianMultipleAttributes.class); /** * Constructor @@ -90,7 +89,7 @@ public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> exten @Override protected Logging getLogger() { - return logger; + return LOG; } /** @@ -101,18 +100,17 @@ public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> exten * @return Outlier detection result */ public OutlierResult run(Relation<N> spatial, Relation<O> attributes) { - final int dim = DatabaseUtil.dimensionality(attributes); - if(logger.isDebugging()) { - logger.debug("Dimensionality: " + dim); + final int dim = RelationUtil.dimensionality(attributes); + if(LOG.isDebugging()) { + LOG.debug("Dimensionality: " + dim); } final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(spatial); CovarianceMatrix covmaker = new CovarianceMatrix(dim); WritableDataStore<Vector> deltas = DataStoreUtil.makeStorage(attributes.getDBIDs(), DataStoreFactory.HINT_TEMP, Vector.class); for(DBIDIter iditer = attributes.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - final O obj = attributes.get(id); - final DBIDs neighbors = npred.getNeighborDBIDs(id); + final O obj = attributes.get(iditer); + final DBIDs neighbors = npred.getNeighborDBIDs(iditer); // Compute the median vector final Vector median; { @@ -123,7 +121,7 @@ public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> exten // TODO: skip object itself within neighbors? O nobj = attributes.get(iter); for(int d = 0; d < dim; d++) { - data[d][i] = nobj.doubleValue(d + 1); + data[d][i] = nobj.doubleValue(d); } i++; } @@ -135,8 +133,8 @@ public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> exten } // Delta vector "h" - Vector delta = obj.getColumnVector().minus(median); - deltas.put(id, delta); + Vector delta = obj.getColumnVector().minusEquals(median); + deltas.put(iditer, delta); covmaker.put(delta); } // Finalize covariance matrix: @@ -146,11 +144,10 @@ public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> exten DoubleMinMax minmax = new DoubleMinMax(); WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(attributes.getDBIDs(), DataStoreFactory.HINT_STATIC); for(DBIDIter iditer = attributes.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - Vector temp = deltas.get(id).minus(mean); + Vector temp = deltas.get(iditer).minus(mean); final double score = temp.transposeTimesTimes(cmati, temp); minmax.put(score); - scores.putDouble(id, score); + scores.putDouble(iditer, score); } Relation<Double> scoreResult = new MaterializedRelation<Double>("Median multiple attributes outlier", "median-outlier", TypeUtil.DOUBLE, scores, attributes.getDBIDs()); @@ -175,7 +172,7 @@ public class CTLuMedianMultipleAttributes<N, O extends NumberVector<?, ?>> exten * @param <N> Neighborhood type * @param <O> Attributes vector type */ - public static class Parameterizer<N, O extends NumberVector<?, ?>> extends AbstractNeighborhoodOutlier.Parameterizer<N> { + public static class Parameterizer<N, O extends NumberVector<?>> extends AbstractNeighborhoodOutlier.Parameterizer<N> { @Override protected CTLuMedianMultipleAttributes<N, O> makeInstance() { return new CTLuMedianMultipleAttributes<N, O>(npredf); diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMoranScatterplotOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMoranScatterplotOutlier.java index 7b88ae66..3b876bba 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMoranScatterplotOutlier.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuMoranScatterplotOutlier.java @@ -32,8 +32,8 @@ import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.logging.Logging; @@ -76,10 +76,10 @@ public class CTLuMoranScatterplotOutlier<N> extends AbstractNeighborhoodOutlier< /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(CTLuMoranScatterplotOutlier.class); + private static final Logging LOG = Logging.getLogger(CTLuMoranScatterplotOutlier.class); /** - * Constructor + * Constructor. * * @param npredf Neighborhood */ @@ -88,20 +88,19 @@ public class CTLuMoranScatterplotOutlier<N> extends AbstractNeighborhoodOutlier< } /** - * Main method + * Main method. * * @param nrel Neighborhood relation * @param relation Data relation (1d!) * @return Outlier detection result */ - public OutlierResult run(Relation<N> nrel, Relation<? extends NumberVector<?, ?>> relation) { + public OutlierResult run(Relation<N> nrel, Relation<? extends NumberVector<?>> relation) { final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(nrel); // Compute the global mean and variance MeanVariance globalmv = new MeanVariance(); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - globalmv.put(relation.get(id).doubleValue(1)); + globalmv.put(relation.get(iditer).doubleValue(0)); } DoubleMinMax minmax = new DoubleMinMax(); @@ -110,17 +109,15 @@ public class CTLuMoranScatterplotOutlier<N> extends AbstractNeighborhoodOutlier< // calculate normalized attribute values // calculate neighborhood average of normalized attribute values. for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); // Compute global z score - final double globalZ = (relation.get(id).doubleValue(1) - globalmv.getMean()) / globalmv.getNaiveStddev(); + final double globalZ = (relation.get(iditer).doubleValue(0) - globalmv.getMean()) / globalmv.getNaiveStddev(); // Compute local average z score Mean localm = new Mean(); - for(DBIDIter iter = npred.getNeighborDBIDs(id).iter(); iter.valid(); iter.advance()) { - DBID n = iter.getDBID(); - if(id.equals(n)) { + for(DBIDIter iter = npred.getNeighborDBIDs(iditer).iter(); iter.valid(); iter.advance()) { + if(DBIDUtil.equal(iditer, iter)) { continue; } - localm.put((relation.get(n).doubleValue(1) - globalmv.getMean()) / globalmv.getNaiveStddev()); + localm.put((relation.get(iter).doubleValue(0) - globalmv.getMean()) / globalmv.getNaiveStddev()); } // if neighors.size == 0 final double localZ; @@ -136,7 +133,7 @@ public class CTLuMoranScatterplotOutlier<N> extends AbstractNeighborhoodOutlier< // Note: in the original moran scatterplot, any object with a score < 0 would be an outlier. final double score = Math.max(-globalZ * localZ, 0); minmax.put(score); - scores.putDouble(id, score); + scores.putDouble(iditer, score); } Relation<Double> scoreResult = new MaterializedRelation<Double>("MoranOutlier", "Moran Scatterplot Outlier", TypeUtil.DOUBLE, scores, relation.getDBIDs()); @@ -148,16 +145,16 @@ public class CTLuMoranScatterplotOutlier<N> extends AbstractNeighborhoodOutlier< @Override public TypeInformation[] getInputTypeRestriction() { - return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), VectorFieldTypeInformation.get(NumberVector.class, 1)); + return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), new VectorFieldTypeInformation<NumberVector<?>>(NumberVector.class, 1)); } @Override protected Logging getLogger() { - return logger; + return LOG; } /** - * Parameterization class + * Parameterization class. * * @author Ahmed Hettab * diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuRandomWalkEC.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuRandomWalkEC.java index 852c4be4..ec92afd7 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuRandomWalkEC.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuRandomWalkEC.java @@ -1,26 +1,27 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.spatial;
-/* -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/>. -*/ +
+/*
+ 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.algorithm.AbstractDistanceBasedAlgorithm;
import de.lmu.ifi.dbs.elki.algorithm.outlier.OutlierAlgorithm;
@@ -33,7 +34,6 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore;
import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore;
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.DBIDIter;
import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil;
import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
@@ -42,6 +42,8 @@ import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction;
+import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNHeap;
+import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNUtil;
import de.lmu.ifi.dbs.elki.distance.distancevalue.NumberDistance;
import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.math.DoubleMinMax;
@@ -51,7 +53,6 @@ import de.lmu.ifi.dbs.elki.math.linearalgebra.Vector; import de.lmu.ifi.dbs.elki.result.outlier.BasicOutlierScoreMeta;
import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult;
import de.lmu.ifi.dbs.elki.result.outlier.OutlierScoreMeta;
-import de.lmu.ifi.dbs.elki.utilities.datastructures.heap.KNNHeap;
import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
@@ -82,30 +83,30 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; */
@Title("Random Walk on Exhaustive Combination")
@Description("Spatial Outlier Detection using Random Walk on Exhaustive Combination")
-@Reference(authors = "X. Liu and C.-T. Lu and F. Chen", title = "Spatial outlier detection: random walk based approaches", booktitle = "Proc. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010", url="http://dx.doi.org/10.1145/1869790.1869841")
+@Reference(authors = "X. Liu and C.-T. Lu and F. Chen", title = "Spatial outlier detection: random walk based approaches", booktitle = "Proc. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010", url = "http://dx.doi.org/10.1145/1869790.1869841")
public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm<N, D, OutlierResult> implements OutlierAlgorithm {
/**
- * Logger
+ * Logger.
*/
- private static final Logging logger = Logging.getLogger(CTLuRandomWalkEC.class);
+ private static final Logging LOG = Logging.getLogger(CTLuRandomWalkEC.class);
/**
- * Parameter alpha: Attribute difference exponent
+ * Parameter alpha: Attribute difference exponent.
*/
private double alpha;
/**
- * Parameter c: damping factor
+ * Parameter c: damping factor.
*/
private double c;
/**
- * Parameter k
+ * Parameter k.
*/
private int k;
/**
- * Constructor
+ * Constructor.
*
* @param distanceFunction Distance function
* @param alpha Alpha parameter
@@ -120,13 +121,13 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac }
/**
- * Run the algorithm
+ * Run the algorithm.
*
* @param spatial Spatial neighborhood relation
* @param relation Attribute value relation
* @return Outlier result
*/
- public OutlierResult run(Relation<N> spatial, Relation<? extends NumberVector<?, ?>> relation) {
+ public OutlierResult run(Relation<N> spatial, Relation<? extends NumberVector<?>> relation) {
DistanceQuery<N, D> distFunc = getDistanceFunction().instantiate(spatial);
WritableDataStore<Vector> similarityVectors = DataStoreUtil.makeStorage(spatial.getDBIDs(), DataStoreFactory.HINT_TEMP, Vector.class);
WritableDataStore<DBIDs> neighbors = DataStoreUtil.makeStorage(spatial.getDBIDs(), DataStoreFactory.HINT_TEMP, DBIDs.class);
@@ -136,39 +137,41 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac // construct the relation Matrix of the ec-graph
Matrix E = new Matrix(ids.size(), ids.size());
- KNNHeap<D> heap = new KNNHeap<D>(k);
- for(int i = 0; i < ids.size(); i++) {
- final DBID id = ids.get(i);
- final double val = relation.get(id).doubleValue(1);
- assert (heap.size() == 0);
- for(int j = 0; j < ids.size(); j++) {
- if(i == j) {
- continue;
- }
- final DBID n = ids.get(j);
- final double e;
- final D distance = distFunc.distance(id, n);
- heap.add(distance, n);
- double dist = distance.doubleValue();
- if(dist == 0) {
- logger.warning("Zero distances are not supported - skipping: " + id + " " + n);
- e = 0;
+ KNNHeap<D> heap = KNNUtil.newHeap(distFunc.getDistanceFactory(), k);
+ {
+ int i = 0;
+ for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) {
+ final double val = relation.get(id).doubleValue(0);
+ assert (heap.size() == 0);
+ int j = 0;
+ for(DBIDIter n = ids.iter(); n.valid(); n.advance(), j++) {
+ if(i == j) {
+ continue;
+ }
+ final double e;
+ final D distance = distFunc.distance(id, n);
+ heap.add(distance, n);
+ double dist = distance.doubleValue();
+ if(dist == 0) {
+ LOG.warning("Zero distances are not supported - skipping: " + DBIDUtil.toString(id) + " " + DBIDUtil.toString(n));
+ e = 0;
+ }
+ else {
+ double diff = Math.abs(val - relation.get(n).doubleValue(0));
+ double exp = Math.exp(Math.pow(diff, alpha));
+ // Implementation note: not inverting exp worked a lot better.
+ // Therefore we diverge from the article here.
+ e = exp / dist;
+ }
+ E.set(j, i, e);
}
- else {
- double diff = Math.abs(val - relation.get(n).doubleValue(1));
- double exp = Math.exp(Math.pow(diff, alpha));
- // Implementation note: not inverting exp worked a lot better.
- // Therefore we diverge from the article here.
- e = exp / dist;
+ // Convert kNN Heap into DBID array
+ ModifiableDBIDs nids = DBIDUtil.newArray(heap.size());
+ while(heap.size() > 0) {
+ nids.add(heap.poll());
}
- E.set(j, i, e);
- }
- // Convert kNN Heap into DBID array
- ModifiableDBIDs nids = DBIDUtil.newArray(heap.size());
- while(!heap.isEmpty()) {
- nids.add(heap.poll().getDBID());
+ neighbors.put(id, nids);
}
- neighbors.put(id, nids);
}
// normalize the adjacent Matrix
// Sum based normalization - don't use E.normalizeColumns()
@@ -195,26 +198,26 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac E = E.inverse().timesEquals(1 - c);
// Split the matrix into columns
- for(int i = 0; i < ids.size(); i++) {
- DBID id = ids.get(i);
- // Note: matrix times ith unit vector = ith column
- Vector sim = E.getCol(i);
- similarityVectors.put(id, sim);
+ {
+ int i = 0;
+ for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) {
+ // Note: matrix times ith unit vector = ith column
+ Vector sim = E.getCol(i);
+ similarityVectors.put(id, sim);
+ }
}
E = null;
// compute the relevance scores between specified Object and its neighbors
DoubleMinMax minmax = new DoubleMinMax();
WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(spatial.getDBIDs(), DataStoreFactory.HINT_STATIC);
- for(int i = 0; i < ids.size(); i++) {
- DBID id = ids.get(i);
+ for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
double gmean = 1.0;
int cnt = 0;
for(DBIDIter iter = neighbors.get(id).iter(); iter.valid(); iter.advance()) {
- DBID n = iter.getDBID();
- if(id.equals(n)) {
+ if(DBIDUtil.equal(id, iter)) {
continue;
}
- double sim = MathUtil.angle(similarityVectors.get(id), similarityVectors.get(n));
+ double sim = MathUtil.angle(similarityVectors.get(id), similarityVectors.get(iter));
gmean *= sim;
cnt++;
}
@@ -230,12 +233,12 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac @Override
public TypeInformation[] getInputTypeRestriction() {
- return TypeUtil.array(getDistanceFunction().getInputTypeRestriction(), VectorFieldTypeInformation.get(NumberVector.class, 1));
+ return TypeUtil.array(getDistanceFunction().getInputTypeRestriction(), new VectorFieldTypeInformation<NumberVector<?>>(NumberVector.class, 1));
}
@Override
protected Logging getLogger() {
- return logger;
+ return LOG;
}
/**
@@ -250,32 +253,32 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac */
public static class Parameterizer<N, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm.Parameterizer<N, D> {
/**
- * Parameter to specify the number of neighbors
+ * Parameter to specify the number of neighbors.
*/
- public static final OptionID K_ID = OptionID.getOrCreateOptionID("randomwalkec.k", "Number of nearest neighbors to use.");
+ public static final OptionID K_ID = new OptionID("randomwalkec.k", "Number of nearest neighbors to use.");
/**
- * Parameter to specify alpha
+ * Parameter to specify alpha.
*/
- public static final OptionID ALPHA_ID = OptionID.getOrCreateOptionID("randomwalkec.alpha", "Scaling exponent for value differences.");
+ public static final OptionID ALPHA_ID = new OptionID("randomwalkec.alpha", "Scaling exponent for value differences.");
/**
- * Parameter to specify the c
+ * Parameter to specify the c.
*/
- public static final OptionID C_ID = OptionID.getOrCreateOptionID("randomwalkec.c", "The damping parameter c.");
+ public static final OptionID C_ID = new OptionID("randomwalkec.c", "The damping parameter c.");
/**
- * Parameter alpha: scaling
+ * Parameter alpha: scaling.
*/
double alpha = 0.5;
/**
- * Parameter c: damping coefficient
+ * Parameter c: damping coefficient.
*/
double c = 0.9;
/**
- * Parameter for kNN
+ * Parameter for kNN.
*/
int k;
@@ -288,19 +291,20 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac }
/**
- * Get the kNN parameter
+ * Get the kNN parameter.
*
* @param config Parameterization
*/
protected void configK(Parameterization config) {
- final IntParameter param = new IntParameter(K_ID, new GreaterEqualConstraint(1));
+ final IntParameter param = new IntParameter(K_ID);
+ param.addConstraint(new GreaterEqualConstraint(1));
if(config.grab(param)) {
k = param.getValue();
}
}
/**
- * Get the alpha parameter
+ * Get the alpha parameter.
*
* @param config Parameterization
*/
@@ -312,9 +316,9 @@ public class CTLuRandomWalkEC<N, D extends NumberDistance<D, ?>> extends Abstrac }
/**
- * get the c parameter
+ * get the c parameter.
*
- * @param config
+ * @param config Parameterization
*/
protected void configC(Parameterization config) {
final DoubleParameter param = new DoubleParameter(C_ID);
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuScatterplotOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuScatterplotOutlier.java index 4f11cb38..295c7414 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuScatterplotOutlier.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuScatterplotOutlier.java @@ -31,8 +31,8 @@ import de.lmu.ifi.dbs.elki.data.type.VectorFieldTypeInformation; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +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.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -78,10 +78,10 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(CTLuScatterplotOutlier.class); + private static final Logging LOG = Logging.getLogger(CTLuScatterplotOutlier.class); /** - * Constructor + * Constructor. * * @param npredf Neighborhood predicate */ @@ -90,13 +90,13 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { } /** - * Main method + * Main method. * * @param nrel Neighborhood relation * @param relation Data relation (1d!) * @return Outlier detection result */ - public OutlierResult run(Relation<N> nrel, Relation<? extends NumberVector<?, ?>> relation) { + public OutlierResult run(Relation<N> nrel, Relation<? extends NumberVector<?>> relation) { final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(nrel); WritableDoubleDataStore means = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_TEMP); @@ -104,17 +104,15 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { // regression using the covariance matrix CovarianceMatrix covm = new CovarianceMatrix(2); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - final double local = relation.get(id).doubleValue(1); + final double local = relation.get(iditer).doubleValue(0); // Compute mean of neighbors Mean mean = new Mean(); - DBIDs neighbors = npred.getNeighborDBIDs(id); + DBIDs neighbors = npred.getNeighborDBIDs(iditer); for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) { - DBID n = iter.getDBID(); - if(id.equals(n)) { + if(DBIDUtil.equal(iditer, iter)) { continue; } - mean.put(relation.get(n).doubleValue(1)); + mean.put(relation.get(iter).doubleValue(0)); } final double m; if(mean.getCount() > 0) { @@ -125,7 +123,7 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { m = local; } // Store the mean for the score calculation - means.putDouble(id, m); + means.putDouble(iditer, m); covm.put(new double[] { local, m }); } // Finalize covariance matrix, compute linear regression @@ -143,11 +141,10 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC); MeanVariance mv = new MeanVariance(); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); // Compute the error from the linear regression - double y_i = relation.get(id).doubleValue(1); - double e = means.doubleValue(id) - (slope * y_i + inter); - scores.putDouble(id, e); + double y_i = relation.get(iditer).doubleValue(0); + double e = means.doubleValue(iditer) - (slope * y_i + inter); + scores.putDouble(iditer, e); mv.put(e); } @@ -157,10 +154,9 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { final double mean = mv.getMean(); final double variance = mv.getNaiveStddev(); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - double score = Math.abs((scores.doubleValue(id) - mean) / variance); + double score = Math.abs((scores.doubleValue(iditer) - mean) / variance); minmax.put(score); - scores.putDouble(id, score); + scores.putDouble(iditer, score); } } // build representation @@ -173,16 +169,16 @@ public class CTLuScatterplotOutlier<N> extends AbstractNeighborhoodOutlier<N> { @Override protected Logging getLogger() { - return logger; + return LOG; } @Override public TypeInformation[] getInputTypeRestriction() { - return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), VectorFieldTypeInformation.get(NumberVector.class, 1)); + return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), new VectorFieldTypeInformation<NumberVector<?>>(NumberVector.class, 1)); } /** - * Parameterization class + * Parameterization class. * * @author Ahmed Hettab * diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuZTestOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuZTestOutlier.java index 05729481..02573a06 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuZTestOutlier.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/CTLuZTestOutlier.java @@ -32,8 +32,8 @@ import de.lmu.ifi.dbs.elki.database.Database; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +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.relation.MaterializedRelation; import de.lmu.ifi.dbs.elki.database.relation.Relation; @@ -79,60 +79,57 @@ public class CTLuZTestOutlier<N> extends AbstractNeighborhoodOutlier<N> { /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(CTLuZTestOutlier.class); + private static final Logging LOG = Logging.getLogger(CTLuZTestOutlier.class); /** - * Constructor + * Constructor. * - * @param npredf + * @param npredf Neighbor predicate */ public CTLuZTestOutlier(NeighborSetPredicate.Factory<N> npredf) { super(npredf); } /** - * Main method + * Main method. * * @param database Database * @param nrel Neighborhood relation * @param relation Data relation (1d!) * @return Outlier detection result */ - public OutlierResult run(Database database, Relation<N> nrel, Relation<? extends NumberVector<?, ?>> relation) { + public OutlierResult run(Database database, Relation<N> nrel, Relation<? extends NumberVector<?>> relation) { final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(nrel); WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC); MeanVariance zmv = new MeanVariance(); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - DBIDs neighbors = npred.getNeighborDBIDs(id); + DBIDs neighbors = npred.getNeighborDBIDs(iditer); // Compute Mean of neighborhood Mean localmean = new Mean(); for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) { - DBID n = iter.getDBID(); - if(id.equals(n)) { + if(DBIDUtil.equal(iditer, iter)) { continue; } - localmean.put(relation.get(n).doubleValue(1)); + localmean.put(relation.get(iter).doubleValue(0)); } final double localdiff; if(localmean.getCount() > 0) { - localdiff = relation.get(id).doubleValue(1) - localmean.getMean(); + localdiff = relation.get(iditer).doubleValue(0) - localmean.getMean(); } else { localdiff = 0.0; } - scores.putDouble(id, localdiff); + scores.putDouble(iditer, localdiff); zmv.put(localdiff); } // Normalize scores using mean and variance DoubleMinMax minmax = new DoubleMinMax(); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); - double score = Math.abs(scores.doubleValue(id) - zmv.getMean()) / zmv.getSampleStddev(); + double score = Math.abs(scores.doubleValue(iditer) - zmv.getMean()) / zmv.getSampleStddev(); minmax.put(score); - scores.putDouble(id, score); + scores.putDouble(iditer, score); } // Wrap result @@ -145,16 +142,16 @@ public class CTLuZTestOutlier<N> extends AbstractNeighborhoodOutlier<N> { @Override protected Logging getLogger() { - return logger; + return LOG; } @Override public TypeInformation[] getInputTypeRestriction() { - return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), VectorFieldTypeInformation.get(NumberVector.class, 1)); + return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), new VectorFieldTypeInformation<NumberVector<?>>(NumberVector.class, 1)); } /** - * Parameterization class + * Parameterization class. * * @author Ahmed Hettab * diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SLOM.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SLOM.java index 8ae23229..720fa39f 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SLOM.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SLOM.java @@ -30,8 +30,8 @@ import de.lmu.ifi.dbs.elki.database.Database; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +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.query.distance.DistanceQuery; import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation; @@ -74,7 +74,7 @@ public class SLOM<N, O, D extends NumberDistance<D, ?>> extends AbstractDistance /** * The logger for this class. */ - private static final Logging logger = Logging.getLogger(SLOM.class); + private static final Logging LOG = Logging.getLogger(SLOM.class); /** * Constructor. @@ -100,29 +100,27 @@ public class SLOM<N, O, D extends NumberDistance<D, ?>> extends AbstractDistance WritableDoubleDataStore modifiedDistance = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP); // calculate D-Tilde for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); double sum = 0; double maxDist = 0; int cnt = 0; - final DBIDs neighbors = npred.getNeighborDBIDs(id); + final DBIDs neighbors = npred.getNeighborDBIDs(iditer); for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) { - DBID neighbor = iter.getDBID(); - if(id.equals(neighbor)) { + if(DBIDUtil.equal(iditer, iter)) { continue; } - double dist = distFunc.distance(id, neighbor).doubleValue(); + double dist = distFunc.distance(iditer, iter).doubleValue(); sum += dist; cnt++; maxDist = Math.max(maxDist, dist); } if(cnt > 1) { - modifiedDistance.putDouble(id, ((sum - maxDist) / (cnt - 1))); + modifiedDistance.putDouble(iditer, ((sum - maxDist) / (cnt - 1))); } else { // Use regular distance when the d-tilde trick is undefined. // Note: this can be 0 when there were no neighbors. - modifiedDistance.putDouble(id, maxDist); + modifiedDistance.putDouble(iditer, maxDist); } } @@ -131,29 +129,26 @@ public class SLOM<N, O, D extends NumberDistance<D, ?>> extends AbstractDistance WritableDoubleDataStore sloms = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC); for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); double sum = 0; int cnt = 0; - final DBIDs neighbors = npred.getNeighborDBIDs(id); + final DBIDs neighbors = npred.getNeighborDBIDs(iditer); for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) { - DBID neighbor = iter.getDBID(); - if(neighbor.equals(id)) { + if(DBIDUtil.equal(iditer, iter)) { continue; } - sum += modifiedDistance.doubleValue(neighbor); + sum += modifiedDistance.doubleValue(iter); cnt++; } double slom; if(cnt > 0) { // With and without the object itself: - double avgPlus = (sum + modifiedDistance.doubleValue(id)) / (cnt + 1); + double avgPlus = (sum + modifiedDistance.doubleValue(iditer)) / (cnt + 1); double avg = sum / cnt; double beta = 0; for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) { - DBID neighbor = iter.getDBID(); - final double dist = modifiedDistance.doubleValue(neighbor); + final double dist = modifiedDistance.doubleValue(iter); if(dist > avgPlus) { beta += 1; } @@ -162,8 +157,8 @@ public class SLOM<N, O, D extends NumberDistance<D, ?>> extends AbstractDistance } } // Include object itself - if(!neighbors.contains(id)) { - final double dist = modifiedDistance.doubleValue(id); + if(!neighbors.contains(iditer)) { + final double dist = modifiedDistance.doubleValue(iditer); if(dist > avgPlus) { beta += 1; } @@ -182,13 +177,13 @@ public class SLOM<N, O, D extends NumberDistance<D, ?>> extends AbstractDistance } beta = beta / (1 + avg); - slom = beta * modifiedDistance.doubleValue(id); + slom = beta * modifiedDistance.doubleValue(iditer); } else { // No neighbors to compare to - no score. slom = 0.0; } - sloms.putDouble(id, slom); + sloms.putDouble(iditer, slom); slomminmax.put(slom); } @@ -201,7 +196,7 @@ public class SLOM<N, O, D extends NumberDistance<D, ?>> extends AbstractDistance @Override protected Logging getLogger() { - return logger; + return LOG; } @Override diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SOF.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SOF.java index e9987bf0..a6f39a60 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SOF.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/SOF.java @@ -29,7 +29,6 @@ import de.lmu.ifi.dbs.elki.database.Database; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil;
import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore;
-import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery;
@@ -74,7 +73,7 @@ public class SOF<N, O, D extends NumberDistance<D, ?>> extends AbstractDistanceB /**
* The logger for this class.
*/
- private static final Logging logger = Logging.getLogger(SOF.class);
+ private static final Logging LOG = Logging.getLogger(SOF.class);
/**
* Constructor.
@@ -89,7 +88,7 @@ public class SOF<N, O, D extends NumberDistance<D, ?>> extends AbstractDistanceB @Override
protected Logging getLogger() {
- return logger;
+ return LOG;
}
/**
@@ -110,33 +109,31 @@ public class SOF<N, O, D extends NumberDistance<D, ?>> extends AbstractDistanceB // Compute densities
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- DBIDs neighbors = npred.getNeighborDBIDs(id);
+ DBIDs neighbors = npred.getNeighborDBIDs(iditer);
double avg = 0;
for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
- avg += distFunc.distance(id, iter.getDBID()).doubleValue();
+ avg += distFunc.distance(iditer, iter).doubleValue();
}
double lrd = 1 / (avg / neighbors.size());
if (Double.isNaN(lrd)) {
lrd = 0;
}
- lrds.putDouble(id, lrd);
+ lrds.putDouble(iditer, lrd);
}
// Compute density quotients
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- DBIDs neighbors = npred.getNeighborDBIDs(id);
+ DBIDs neighbors = npred.getNeighborDBIDs(iditer);
double avg = 0;
for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
- avg += lrds.doubleValue(iter.getDBID());
+ avg += lrds.doubleValue(iter);
}
- final double lrd = (avg / neighbors.size()) / lrds.doubleValue(id);
+ final double lrd = (avg / neighbors.size()) / lrds.doubleValue(iditer);
if (!Double.isNaN(lrd)) {
- lofs.putDouble(id, lrd);
+ lofs.putDouble(iditer, lrd);
lofminmax.put(lrd);
} else {
- lofs.putDouble(id, 0.0);
+ lofs.putDouble(iditer, 0.0);
}
}
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/TrimmedMeanApproach.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/TrimmedMeanApproach.java index 41022414..9aa21b66 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/TrimmedMeanApproach.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/TrimmedMeanApproach.java @@ -33,11 +33,11 @@ import de.lmu.ifi.dbs.elki.database.Database; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory;
import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil;
import de.lmu.ifi.dbs.elki.database.datastore.WritableDoubleDataStore;
-import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
import de.lmu.ifi.dbs.elki.database.relation.MaterializedRelation;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
+import de.lmu.ifi.dbs.elki.database.relation.RelationUtil;
import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.logging.progress.FiniteProgress;
import de.lmu.ifi.dbs.elki.math.DoubleMinMax;
@@ -45,14 +45,13 @@ import de.lmu.ifi.dbs.elki.math.Mean; import de.lmu.ifi.dbs.elki.result.outlier.BasicOutlierScoreMeta;
import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult;
import de.lmu.ifi.dbs.elki.result.outlier.OutlierScoreMeta;
-import de.lmu.ifi.dbs.elki.utilities.DatabaseUtil;
import de.lmu.ifi.dbs.elki.utilities.datastructures.QuickSelect;
import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID;
-import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint;
-import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.IntervalConstraint.IntervalBoundary;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterConstraint;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.LessConstraint;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter;
@@ -83,15 +82,15 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { /**
* The logger for this class.
*/
- private static final Logging logger = Logging.getLogger(TrimmedMeanApproach.class);
+ private static final Logging LOG = Logging.getLogger(TrimmedMeanApproach.class);
/**
- * the parameter p
+ * the parameter p.
*/
private double p;
/**
- * Constructor
+ * Constructor.
*
* @param p Parameter p
* @param npredf Neighborhood factory.
@@ -102,29 +101,28 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { }
/**
- * Run the algorithm
+ * Run the algorithm.
*
* @param database Database
* @param nrel Neighborhood relation
* @param relation Data Relation (1 dimensional!)
* @return Outlier detection result
*/
- public OutlierResult run(Database database, Relation<N> nrel, Relation<? extends NumberVector<?, ?>> relation) {
- assert (DatabaseUtil.dimensionality(relation) == 1) : "TrimmedMean can only process one-dimensional data sets.";
+ public OutlierResult run(Database database, Relation<N> nrel, Relation<? extends NumberVector<?>> relation) {
+ assert (RelationUtil.dimensionality(relation) == 1) : "TrimmedMean can only process one-dimensional data sets.";
final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(nrel);
WritableDoubleDataStore errors = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_TEMP);
WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
- FiniteProgress progress = logger.isVerbose() ? new FiniteProgress("Computing trimmed means", relation.size(), logger) : null;
+ FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("Computing trimmed means", relation.size(), LOG) : null;
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- DBIDs neighbors = npred.getNeighborDBIDs(id);
+ DBIDs neighbors = npred.getNeighborDBIDs(iditer);
int num = 0;
double[] values = new double[neighbors.size()];
// calculate trimmedMean
for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
- values[num] = relation.get(iter).doubleValue(1);
+ values[num] = relation.get(iter).doubleValue(0);
num++;
}
@@ -141,21 +139,21 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { tm = mean.getMean();
}
else {
- tm = relation.get(id).doubleValue(1);
+ tm = relation.get(iditer).doubleValue(0);
}
// Error: deviation from trimmed mean
- errors.putDouble(id, relation.get(id).doubleValue(1) - tm);
+ errors.putDouble(iditer, relation.get(iditer).doubleValue(0) - tm);
if(progress != null) {
- progress.incrementProcessed(logger);
+ progress.incrementProcessed(LOG);
}
}
if(progress != null) {
- progress.ensureCompleted(logger);
+ progress.ensureCompleted(LOG);
}
- if(logger.isVerbose()) {
- logger.verbose("Computing median error.");
+ if(LOG.isVerbose()) {
+ LOG.verbose("Computing median error.");
}
double median_dev_from_median;
{
@@ -164,8 +162,7 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { {
int i = 0;
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- ei[i] = errors.doubleValue(id);
+ ei[i] = errors.doubleValue(iditer);
i++;
}
}
@@ -178,15 +175,14 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { median_dev_from_median = QuickSelect.median(ei);
}
- if(logger.isVerbose()) {
- logger.verbose("Normalizing scores.");
+ if(LOG.isVerbose()) {
+ LOG.verbose("Normalizing scores.");
}
// calculate score
DoubleMinMax minmax = new DoubleMinMax();
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- double score = Math.abs(errors.doubleValue(id)) * 0.6745 / median_dev_from_median;
- scores.putDouble(id, score);
+ double score = Math.abs(errors.doubleValue(iditer)) * 0.6745 / median_dev_from_median;
+ scores.putDouble(iditer, score);
minmax.put(score);
}
//
@@ -199,17 +195,17 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { @Override
protected Logging getLogger() {
- return logger;
+ return LOG;
}
@Override
public TypeInformation[] getInputTypeRestriction() {
// Get one dimensional attribute for analysis.
- return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), VectorFieldTypeInformation.get(NumberVector.class, 1));
+ return TypeUtil.array(getNeighborSetPredicateFactory().getInputTypeRestriction(), new VectorFieldTypeInformation<NumberVector<?>>(NumberVector.class, 1));
}
/**
- * Parameterizer
+ * Parameterizer.
*
* @author Ahmed Hettab
*
@@ -219,19 +215,21 @@ public class TrimmedMeanApproach<N> extends AbstractNeighborhoodOutlier<N> { */
public static class Parameterizer<N> extends AbstractNeighborhoodOutlier.Parameterizer<N> {
/**
- * Parameter for the percentile value p
+ * Parameter for the percentile value p.
*/
- public static final OptionID P_ID = OptionID.getOrCreateOptionID("tma.p", "the percentile parameter");
+ public static final OptionID P_ID = new OptionID("tma.p", "the percentile parameter");
/**
- * Percentile parameter p
+ * Percentile parameter p.
*/
protected double p = 0.2;
@Override
protected void makeOptions(Parameterization config) {
super.makeOptions(config);
- DoubleParameter pP = new DoubleParameter(P_ID, new IntervalConstraint(0.0, IntervalBoundary.OPEN, 0.5, IntervalBoundary.OPEN));
+ DoubleParameter pP = new DoubleParameter(P_ID);
+ pP.addConstraint(new GreaterConstraint(0.0)); + pP.addConstraint(new LessConstraint(0.5));
if(config.grab(pP)) {
p = pP.getValue();
}
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/AbstractPrecomputedNeighborhood.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/AbstractPrecomputedNeighborhood.java index 5898b053..2c706ce0 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/AbstractPrecomputedNeighborhood.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/AbstractPrecomputedNeighborhood.java @@ -24,7 +24,8 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood; */ import de.lmu.ifi.dbs.elki.database.datastore.DataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.logging.Logging; @@ -50,7 +51,7 @@ public abstract class AbstractPrecomputedNeighborhood implements NeighborSetPred } @Override - public DBIDs getNeighborDBIDs(DBID reference) { + public DBIDs getNeighborDBIDs(DBIDRef reference) { DBIDs neighbors = store.get(reference); if(neighbors != null) { return neighbors; @@ -60,7 +61,7 @@ public abstract class AbstractPrecomputedNeighborhood implements NeighborSetPred if(getLogger().isDebugging()) { getLogger().warning("No neighbors for object " + reference); } - return reference; + return DBIDUtil.deref(reference); } } @@ -69,7 +70,7 @@ public abstract class AbstractPrecomputedNeighborhood implements NeighborSetPred * * @return Logger */ - abstract protected Logging getLogger(); + protected abstract Logging getLogger(); /** * Factory class. diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExtendedNeighborhood.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExtendedNeighborhood.java index 7a2fda52..4aa96b25 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExtendedNeighborhood.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExtendedNeighborhood.java @@ -28,7 +28,6 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStore; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil; import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; @@ -54,7 +53,7 @@ public class ExtendedNeighborhood extends AbstractPrecomputedNeighborhood { /** * The logger to use. */ - static final Logging logger = Logging.getLogger(ExtendedNeighborhood.class); + private static final Logging LOG = Logging.getLogger(ExtendedNeighborhood.class); /** * Constructor. @@ -67,7 +66,7 @@ public class ExtendedNeighborhood extends AbstractPrecomputedNeighborhood { @Override protected Logging getLogger() { - return logger; + return LOG; } @Override @@ -132,23 +131,22 @@ public class ExtendedNeighborhood extends AbstractPrecomputedNeighborhood { final WritableDataStore<DBIDs> store = DataStoreUtil.makeStorage(database.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC | DataStoreFactory.HINT_TEMP, DBIDs.class); // Expand multiple steps - FiniteProgress progress = logger.isVerbose() ? new FiniteProgress("Expanding neighborhoods", database.size(), logger) : null; + FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("Expanding neighborhoods", database.size(), LOG) : null; for(DBIDIter iter = database.iterDBIDs(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - HashSetModifiableDBIDs res = DBIDUtil.newHashSet(id); - DBIDs todo = id; + HashSetModifiableDBIDs res = DBIDUtil.newHashSet(); + res.add(iter); + DBIDs todo = DBIDUtil.deref(iter); for(int i = 0; i < steps; i++) { ModifiableDBIDs ntodo = DBIDUtil.newHashSet(); for(DBIDIter iter2 = todo.iter(); iter2.valid(); iter2.advance()) { - DBIDs add = innerinst.getNeighborDBIDs(iter2.getDBID()); + DBIDs add = innerinst.getNeighborDBIDs(iter2); if(add != null) { - for(DBIDIter iter3 = add.iter(); iter.valid(); iter.advance()) { - DBID nid = iter3.getDBID(); - if(res.contains(nid)) { + for(DBIDIter iter3 = add.iter(); iter3.valid(); iter3.advance()) { + if(res.contains(iter3)) { continue; } - ntodo.add(nid); - res.add(nid); + ntodo.add(iter3); + res.add(iter3); } } } @@ -157,13 +155,13 @@ public class ExtendedNeighborhood extends AbstractPrecomputedNeighborhood { } todo = ntodo; } - store.put(id, res); + store.put(iter, res); if(progress != null) { - progress.incrementProcessed(logger); + progress.incrementProcessed(LOG); } } if(progress != null) { - progress.ensureCompleted(logger); + progress.ensureCompleted(LOG); } return store; @@ -180,12 +178,12 @@ public class ExtendedNeighborhood extends AbstractPrecomputedNeighborhood { /** * Parameter to specify the neighborhood predicate to use. */ - public static final OptionID NEIGHBORHOOD_ID = OptionID.getOrCreateOptionID("extendedneighbors.neighborhood", "The inner neighborhood predicate to use."); + public static final OptionID NEIGHBORHOOD_ID = new OptionID("extendedneighbors.neighborhood", "The inner neighborhood predicate to use."); /** * Parameter to specify the number of steps allowed */ - public static final OptionID STEPS_ID = OptionID.getOrCreateOptionID("extendedneighbors.steps", "The number of steps allowed in the neighborhood graph."); + public static final OptionID STEPS_ID = new OptionID("extendedneighbors.steps", "The number of steps allowed in the neighborhood graph."); /** * The number of steps to do. @@ -225,7 +223,8 @@ public class ExtendedNeighborhood extends AbstractPrecomputedNeighborhood { * @return number of steps, default 1 */ public static int getParameterSteps(Parameterization config) { - final IntParameter param = new IntParameter(STEPS_ID, new GreaterEqualConstraint(1)); + final IntParameter param = new IntParameter(STEPS_ID); + param.addConstraint(new GreaterEqualConstraint(1)); if(config.grab(param)) { return param.getValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExternalNeighborhood.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExternalNeighborhood.java index 74e5bbcf..01052c1f 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExternalNeighborhood.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/ExternalNeighborhood.java @@ -63,12 +63,12 @@ public class ExternalNeighborhood extends AbstractPrecomputedNeighborhood { /** * Logger */ - static final Logging logger = Logging.getLogger(ExternalNeighborhood.class); + private static final Logging LOG = Logging.getLogger(ExternalNeighborhood.class); /** * Parameter to specify the neighborhood file */ - public static final OptionID NEIGHBORHOOD_FILE_ID = OptionID.getOrCreateOptionID("externalneighbors.file", "The file listing the neighbors."); + public static final OptionID NEIGHBORHOOD_FILE_ID = new OptionID("externalneighbors.file", "The file listing the neighbors."); /** * Constructor. @@ -91,7 +91,7 @@ public class ExternalNeighborhood extends AbstractPrecomputedNeighborhood { @Override protected Logging getLogger() { - return logger; + return LOG; } /** @@ -136,33 +136,32 @@ public class ExternalNeighborhood extends AbstractPrecomputedNeighborhood { private DataStore<DBIDs> loadNeighbors(Relation<?> database) { final WritableDataStore<DBIDs> store = DataStoreUtil.makeStorage(database.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC | DataStoreFactory.HINT_TEMP, DBIDs.class); - if(logger.isVerbose()) { - logger.verbose("Loading external neighborhoods."); + if(LOG.isVerbose()) { + LOG.verbose("Loading external neighborhoods."); } - if(logger.isDebugging()) { - logger.verbose("Building reverse label index..."); + if(LOG.isDebugging()) { + LOG.verbose("Building reverse label index..."); } // Build a map label/ExternalId -> DBID // (i.e. a reverse index!) // TODO: move this into the database layer to share? - Map<String, DBID> lblmap = new HashMap<String, DBID>(database.size() * 2); + Map<String, DBID> lblmap = new HashMap<String, DBID>(database.size() << 1); { Relation<LabelList> olq = database.getDatabase().getRelation(TypeUtil.LABELLIST); Relation<ExternalID> eidq = database.getDatabase().getRelation(TypeUtil.EXTERNALID); for(DBIDIter iditer = database.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID(); if(eidq != null) { - ExternalID eid = eidq.get(id); + ExternalID eid = eidq.get(iditer); if(eid != null) { - lblmap.put(eid.toString(), id); + lblmap.put(eid.toString(), DBIDUtil.deref(iditer)); } } if(olq != null) { - LabelList label = olq.get(id); + LabelList label = olq.get(iditer); if(label != null) { for(String lbl : label) { - lblmap.put(lbl, id); + lblmap.put(lbl, DBIDUtil.deref(iditer)); } } } @@ -170,8 +169,8 @@ public class ExternalNeighborhood extends AbstractPrecomputedNeighborhood { } try { - if(logger.isDebugging()) { - logger.verbose("Loading neighborhood file."); + if(LOG.isDebugging()) { + LOG.verbose("Loading neighborhood file."); } InputStream in = new FileInputStream(file); in = FileUtil.tryGzipInput(in); @@ -187,16 +186,16 @@ public class ExternalNeighborhood extends AbstractPrecomputedNeighborhood { neighbours.add(neigh); } else { - if(logger.isDebugging()) { - logger.debug("No object found for label " + entries[i]); + if(LOG.isDebugging()) { + LOG.debug("No object found for label " + entries[i]); } } } store.put(id, neighbours); } else { - if(logger.isDebugging()) { - logger.warning("No object found for label " + entries[0]); + if(LOG.isDebugging()) { + LOG.warning("No object found for label " + entries[0]); } } } diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/NeighborSetPredicate.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/NeighborSetPredicate.java index 3a6d0e28..b52f8e91 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/NeighborSetPredicate.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/NeighborSetPredicate.java @@ -24,7 +24,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood; */ import de.lmu.ifi.dbs.elki.data.type.TypeInformation; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; import de.lmu.ifi.dbs.elki.database.ids.DBIDs; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.result.Result; @@ -42,7 +42,7 @@ public interface NeighborSetPredicate extends Result { * @param reference Reference object * @return Neighborhood */ - public DBIDs getNeighborDBIDs(DBID reference); + public DBIDs getNeighborDBIDs(DBIDRef reference); /** * Factory interface to produce instances. diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/PrecomputedKNearestNeighborNeighborhood.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/PrecomputedKNearestNeighborNeighborhood.java index 9dd2dee1..f6000ef0 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/PrecomputedKNearestNeighborNeighborhood.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/PrecomputedKNearestNeighborNeighborhood.java @@ -29,15 +29,13 @@ import de.lmu.ifi.dbs.elki.database.datastore.DataStoreFactory; import de.lmu.ifi.dbs.elki.database.datastore.DataStoreUtil;
import de.lmu.ifi.dbs.elki.database.datastore.WritableDataStore;
import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs;
-import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
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.query.DistanceResultPair;
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.distancefunction.DistanceFunction;
+import de.lmu.ifi.dbs.elki.distance.distanceresultlist.KNNResult;
import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
@@ -57,7 +55,7 @@ public class PrecomputedKNearestNeighborNeighborhood<D extends Distance<D>> exte /**
* Logger
*/
- private static final Logging logger = Logging.getLogger(PrecomputedKNearestNeighborNeighborhood.class);
+ private static final Logging LOG = Logging.getLogger(PrecomputedKNearestNeighborNeighborhood.class);
/**
* Constructor.
@@ -80,7 +78,7 @@ public class PrecomputedKNearestNeighborNeighborhood<D extends Distance<D>> exte @Override
protected Logging getLogger() {
- return logger;
+ return LOG;
}
/**
@@ -121,13 +119,12 @@ public class PrecomputedKNearestNeighborNeighborhood<D extends Distance<D>> exte // TODO: use bulk?
WritableDataStore<DBIDs> s = DataStoreUtil.makeStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC, DBIDs.class);
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { - DBID id = iditer.getDBID();
- KNNResult<D> neighbors = knnQuery.getKNNForDBID(id, k);
+ KNNResult<D> neighbors = knnQuery.getKNNForDBID(iditer, k);
ArrayModifiableDBIDs neighbours = DBIDUtil.newArray(neighbors.size());
- for(DistanceResultPair<D> dpair : neighbors) {
- neighbours.add(dpair.getDBID());
+ for (DBIDIter neighbor = neighbors.iter(); neighbor.valid(); neighbor.advance()) {
+ neighbours.add(neighbor);
}
- s.put(id, neighbours);
+ s.put(iditer, neighbours);
}
return new PrecomputedKNearestNeighborNeighborhood<D>(s);
}
@@ -151,12 +148,12 @@ public class PrecomputedKNearestNeighborNeighborhood<D extends Distance<D>> exte /**
* Parameter k
*/
- public static final OptionID K_ID = OptionID.getOrCreateOptionID("neighborhood.k", "the number of neighbors");
+ public static final OptionID K_ID = new OptionID("neighborhood.k", "the number of neighbors");
/**
* Parameter to specify the distance function to use
*/
- public static final OptionID DISTANCEFUNCTION_ID = OptionID.getOrCreateOptionID("neighborhood.distancefunction", "the distance function to use");
+ public static final OptionID DISTANCEFUNCTION_ID = new OptionID("neighborhood.distancefunction", "the distance function to use");
/**
* Parameter k
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/LinearWeightedExtendedNeighborhood.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/LinearWeightedExtendedNeighborhood.java index d170571f..f1c68577 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/LinearWeightedExtendedNeighborhood.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/LinearWeightedExtendedNeighborhood.java @@ -29,10 +29,11 @@ import java.util.List; import de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood.NeighborSetPredicate; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; 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.DoubleDBIDPair; import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer; @@ -41,7 +42,6 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualCons import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; -import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; /** * Neighborhood obtained by computing the k-fold closure of an existing @@ -87,29 +87,27 @@ public class LinearWeightedExtendedNeighborhood implements WeightedNeighborSetPr } @Override - public Collection<DoubleObjPair<DBID>> getWeightedNeighbors(DBID reference) { + public Collection<DoubleDBIDPair> getWeightedNeighbors(DBIDRef reference) { ModifiableDBIDs seen = DBIDUtil.newHashSet(); - List<DoubleObjPair<DBID>> result = new ArrayList<DoubleObjPair<DBID>>(); + List<DoubleDBIDPair> result = new ArrayList<DoubleDBIDPair>(); // Add starting object - result.add(new DoubleObjPair<DBID>(computeWeight(0), reference)); + result.add(DBIDUtil.newPair(computeWeight(0), reference)); seen.add(reference); // Extend. - DBIDs cur = reference; + DBIDs cur = DBIDUtil.deref(reference); for(int i = 1; i <= steps; i++) { final double weight = computeWeight(i); // Collect newly discovered IDs ModifiableDBIDs add = DBIDUtil.newHashSet(); for(DBIDIter iter = cur.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - for(DBIDIter iter2 = inner.getNeighborDBIDs(id).iter(); iter2.valid(); iter2.advance()) { - DBID nid = iter2.getDBID(); + for(DBIDIter iter2 = inner.getNeighborDBIDs(iter).iter(); iter2.valid(); iter2.advance()) { // Seen before? - if(seen.contains(nid)) { + if(seen.contains(iter2)) { continue; } - add.add(nid); - result.add(new DoubleObjPair<DBID>(weight, nid)); + add.add(iter2); + result.add(DBIDUtil.newPair(weight, iter2)); } } if(add.size() == 0) { @@ -172,12 +170,12 @@ public class LinearWeightedExtendedNeighborhood implements WeightedNeighborSetPr /** * Parameter to specify the neighborhood predicate to use. */ - public static final OptionID NEIGHBORHOOD_ID = OptionID.getOrCreateOptionID("extendedneighbors.neighborhood", "The inner neighborhood predicate to use."); + public static final OptionID NEIGHBORHOOD_ID = new OptionID("extendedneighbors.neighborhood", "The inner neighborhood predicate to use."); /** * Parameter to specify the number of steps allowed */ - public static final OptionID STEPS_ID = OptionID.getOrCreateOptionID("extendedneighbors.steps", "The number of steps allowed in the neighborhood graph."); + public static final OptionID STEPS_ID = new OptionID("extendedneighbors.steps", "The number of steps allowed in the neighborhood graph."); /** * The number of steps to do. @@ -217,7 +215,8 @@ public class LinearWeightedExtendedNeighborhood implements WeightedNeighborSetPr * @return number of steps, default 1 */ public static int getParameterSteps(Parameterization config) { - final IntParameter param = new IntParameter(STEPS_ID, new GreaterEqualConstraint(1)); + final IntParameter param = new IntParameter(STEPS_ID); + param.addConstraint(new GreaterEqualConstraint(1)); if(config.grab(param)) { return param.getValue(); } diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/UnweightedNeighborhoodAdapter.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/UnweightedNeighborhoodAdapter.java index ce0666df..c179d81f 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/UnweightedNeighborhoodAdapter.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/UnweightedNeighborhoodAdapter.java @@ -28,15 +28,16 @@ import java.util.Collection; import de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood.NeighborSetPredicate; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; -import de.lmu.ifi.dbs.elki.database.ids.DBID; import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +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.DoubleDBIDPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; 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.Parameterization; import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; -import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; /** * Adapter to use unweighted neighborhoods in an algorithm that requires @@ -61,12 +62,11 @@ public class UnweightedNeighborhoodAdapter implements WeightedNeighborSetPredica } @Override - public Collection<DoubleObjPair<DBID>> getWeightedNeighbors(DBID reference) { + public Collection<DoubleDBIDPair> getWeightedNeighbors(DBIDRef reference) { DBIDs neighbors = inner.getNeighborDBIDs(reference); - ArrayList<DoubleObjPair<DBID>> adapted = new ArrayList<DoubleObjPair<DBID>>(neighbors.size()); + ArrayList<DoubleDBIDPair> adapted = new ArrayList<DoubleDBIDPair>(neighbors.size()); for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) { - DBID id = iter.getDBID(); - adapted.add(new DoubleObjPair<DBID>(1.0, id)); + adapted.add(DBIDUtil.newPair(1.0, iter)); } return adapted; } @@ -120,7 +120,7 @@ public class UnweightedNeighborhoodAdapter implements WeightedNeighborSetPredica /** * The parameter to give the non-weighted neighborhood to use. */ - public static final OptionID INNER_ID = OptionID.getOrCreateOptionID("neighborhood.inner", "Parameter for the non-weighted neighborhood to use."); + public static final OptionID INNER_ID = new OptionID("neighborhood.inner", "Parameter for the non-weighted neighborhood to use."); /** * The actual predicate. diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/WeightedNeighborSetPredicate.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/WeightedNeighborSetPredicate.java index b147935a..16d37587 100644 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/WeightedNeighborSetPredicate.java +++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/spatial/neighborhood/weighted/WeightedNeighborSetPredicate.java @@ -26,10 +26,10 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.spatial.neighborhood.weighted; import java.util.Collection; import de.lmu.ifi.dbs.elki.data.type.TypeInformation; -import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDPair; import de.lmu.ifi.dbs.elki.database.relation.Relation; import de.lmu.ifi.dbs.elki.utilities.optionhandling.Parameterizable; -import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; /** * Neighbor predicate with weight support. @@ -43,7 +43,7 @@ public interface WeightedNeighborSetPredicate { * @param reference Reference object * @return Weighted Neighborhood */ - public Collection<DoubleObjPair<DBID>> getWeightedNeighbors(DBID reference); + public Collection<DoubleDBIDPair> getWeightedNeighbors(DBIDRef reference); /** * Factory interface to produce instances. |