diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/algorithm/outlier/KNNWeightOutlier.java')
| -rw-r--r-- | src/de/lmu/ifi/dbs/elki/algorithm/outlier/KNNWeightOutlier.java | 189 |
1 files changed, 0 insertions, 189 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/KNNWeightOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/KNNWeightOutlier.java deleted file mode 100644 index 88603f09..00000000 --- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/KNNWeightOutlier.java +++ /dev/null @@ -1,189 +0,0 @@ -package de.lmu.ifi.dbs.elki.algorithm.outlier;
-
-/*
- This file is part of ELKI:
- Environment for Developing KDD-Applications Supported by Index-Structures -
- Copyright (C) 2011
- Ludwig-Maximilians-Universität München
- Lehr- und Forschungseinheit für Datenbanksysteme
- ELKI Development Team -
- This program is free software: you can redistribute it and/or modify
- it under the terms of the GNU Affero General Public License as published by
- the Free Software Foundation, either version 3 of the License, or
- (at your option) any later version. -
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU Affero General Public License for more details. -
- You should have received a copy of the GNU Affero General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
- */
-
-import de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm;
-import de.lmu.ifi.dbs.elki.data.type.TypeInformation;
-import de.lmu.ifi.dbs.elki.data.type.TypeUtil;
-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.DBIDIter;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceDBIDListIter;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DoubleDistanceKNNList;
-import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList;
-import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery;
-import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
-import de.lmu.ifi.dbs.elki.database.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.distancevalue.NumberDistance;
-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;
-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.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.parameterization.Parameterization;
-import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter;
-
-/**
- * Outlier Detection based on the accumulated distances of a point to its k
- * nearest neighbors.
- *
- * Based on: F. Angiulli, C. Pizzuti: Fast Outlier Detection in High Dimensional
- * Spaces. In: Proc. European Conference on Principles of Knowledge Discovery
- * and Data Mining (PKDD'02), Helsinki, Finland, 2002.
- *
- * @author Lisa Reichert
- *
- * @apiviz.has KNNQuery
- *
- * @param <O> the type of DatabaseObjects handled by this Algorithm
- * @param <D> the type of Distance used by this Algorithm
- */
-@Title("KNNWeight outlier detection")
-@Description("Outlier Detection based on the distances of an object to its k nearest neighbors.")
-@Reference(authors = "F. Angiulli, C. Pizzuti", title = "Fast Outlier Detection in High Dimensional Spaces", booktitle = "Proc. European Conference on Principles of Knowledge Discovery and Data Mining (PKDD'02), Helsinki, Finland, 2002", url = "http://dx.doi.org/10.1007/3-540-45681-3_2")
-public class KNNWeightOutlier<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm<O, D, OutlierResult> implements OutlierAlgorithm {
- /**
- * The logger for this class.
- */
- private static final Logging LOG = Logging.getLogger(KNNWeightOutlier.class);
-
- /**
- * Parameter to specify the k nearest neighbor
- */
- public static final OptionID K_ID = new OptionID("knnwod.k", "k nearest neighbor");
-
- /**
- * The kNN query used.
- */
- public static final OptionID KNNQUERY_ID = new OptionID("knnwod.knnquery", "kNN query to use");
-
- /**
- * Holds the value of {@link #K_ID}.
- */
- private int k;
-
- /**
- * Constructor with parameters.
- *
- * @param distanceFunction Distance function
- * @param k k Parameter
- */
- public KNNWeightOutlier(DistanceFunction<? super O, D> distanceFunction, int k) {
- super(distanceFunction);
- this.k = k;
- }
-
- /**
- * Runs the algorithm in the timed evaluation part.
- */
- public OutlierResult run(Database database, Relation<O> relation) {
- final DistanceQuery<O, D> distanceQuery = database.getDistanceQuery(relation, getDistanceFunction());
- KNNQuery<O, D> knnQuery = database.getKNNQuery(distanceQuery, k);
-
- if(LOG.isVerbose()) {
- LOG.verbose("computing outlier degree(sum of the distances to the k nearest neighbors");
- }
- FiniteProgress progressKNNWeight = LOG.isVerbose() ? new FiniteProgress("KNNWOD_KNNWEIGHT for objects", relation.size(), LOG) : null;
-
- DoubleMinMax minmax = new DoubleMinMax();
-
- // compute distance to the k nearest neighbor. n objects with the highest
- // distance are flagged as outliers
- WritableDoubleDataStore knnw_score = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
- for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
- // compute sum of the distances to the k nearest neighbors
-
- final KNNList<D> knn = knnQuery.getKNNForDBID(iditer, k);
- double skn = 0;
- if(knn instanceof DoubleDistanceKNNList) {
- for(DoubleDistanceDBIDListIter neighbor = ((DoubleDistanceKNNList) knn).iter(); neighbor.valid(); neighbor.advance()) {
- skn += neighbor.doubleDistance();
- }
- }
- else {
- for(DistanceDBIDListIter<D> neighbor = knn.iter(); neighbor.valid(); neighbor.advance()) {
- skn += neighbor.getDistance().doubleValue();
- }
- }
- knnw_score.putDouble(iditer, skn);
- minmax.put(skn);
-
- if(progressKNNWeight != null) {
- progressKNNWeight.incrementProcessed(LOG);
- }
- }
- if(progressKNNWeight != null) {
- progressKNNWeight.ensureCompleted(LOG);
- }
-
- Relation<Double> res = new MaterializedRelation<>("Weighted kNN Outlier Score", "knnw-outlier", TypeUtil.DOUBLE, knnw_score, relation.getDBIDs());
- OutlierScoreMeta meta = new BasicOutlierScoreMeta(minmax.getMin(), minmax.getMax(), 0.0, Double.POSITIVE_INFINITY, 0.0);
- return new OutlierResult(meta, res);
- }
-
- @Override
- public TypeInformation[] getInputTypeRestriction() {
- return TypeUtil.array(getDistanceFunction().getInputTypeRestriction());
- }
-
- @Override
- protected Logging getLogger() {
- return LOG;
- }
-
- /**
- * Parameterization class.
- *
- * @author Erich Schubert
- *
- * @apiviz.exclude
- */
- public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm.Parameterizer<O, D> {
- protected int k = 0;
-
- @Override
- protected void makeOptions(Parameterization config) {
- super.makeOptions(config);
- final IntParameter kP = new IntParameter(K_ID);
- if(config.grab(kP)) {
- k = kP.getValue();
- }
- }
-
- @Override
- protected KNNWeightOutlier<O, D> makeInstance() {
- return new KNNWeightOutlier<>(distanceFunction, k);
- }
- }
-}
\ No newline at end of file |