summaryrefslogtreecommitdiff
path: root/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java')
-rw-r--r--src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java64
1 files changed, 33 insertions, 31 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java
index 36c70b48..479b0bab 100644
--- a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java
+++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LDOF.java
@@ -4,7 +4,7 @@ package de.lmu.ifi.dbs.elki.algorithm.outlier.lof;
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
- Copyright (C) 2011
+ Copyright (C) 2014
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
@@ -33,14 +33,14 @@ 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.DBIDUtil;
-import de.lmu.ifi.dbs.elki.database.ids.distance.DistanceDBIDListIter;
-import de.lmu.ifi.dbs.elki.database.ids.distance.KNNList;
+import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter;
+import de.lmu.ifi.dbs.elki.database.ids.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.DoubleRelation;
+import de.lmu.ifi.dbs.elki.database.relation.MaterializedDoubleRelation;
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;
@@ -79,9 +79,12 @@ import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter;
*/
@Title("LDOF: Local Distance-Based Outlier Factor")
@Description("Local outlier detection appraoch suitable for scattered data by averaging the kNN distance over all k nearest neighbors")
-@Reference(authors = "K. Zhang, M. Hutter, H. Jin", title = "A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data", booktitle = "Proc. 13th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2009), Bangkok, Thailand, 2009", url = "http://dx.doi.org/10.1007/978-3-642-01307-2_84")
+@Reference(authors = "K. Zhang, M. Hutter, H. Jin", //
+title = "A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data", //
+booktitle = "Proc. 13th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2009), Bangkok, Thailand, 2009", //
+url = "http://dx.doi.org/10.1007/978-3-642-01307-2_84")
@Alias({ "de.lmu.ifi.dbs.elki.algorithm.outlier.LDOF" })
-public class LDOF<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm<O, D, OutlierResult> implements OutlierAlgorithm {
+public class LDOF<O> extends AbstractDistanceBasedAlgorithm<O, OutlierResult> implements OutlierAlgorithm {
/**
* The logger for this class.
*/
@@ -110,7 +113,7 @@ public class LDOF<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBas
* @param distanceFunction distance function
* @param k k Parameter
*/
- public LDOF(DistanceFunction<? super O, D> distanceFunction, int k) {
+ public LDOF(DistanceFunction<? super O> distanceFunction, int k) {
super(distanceFunction);
this.k = k;
}
@@ -123,8 +126,8 @@ public class LDOF<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBas
* @return Outlier result
*/
public OutlierResult run(Database database, Relation<O> relation) {
- DistanceQuery<O, D> distFunc = database.getDistanceQuery(relation, getDistanceFunction());
- KNNQuery<O, D> knnQuery = database.getKNNQuery(distFunc, k);
+ DistanceQuery<O> distFunc = database.getDistanceQuery(relation, getDistanceFunction());
+ KNNQuery<O> knnQuery = database.getKNNQuery(distFunc, k + 1);
// track the maximum value for normalization
DoubleMinMax ldofminmax = new DoubleMinMax();
@@ -135,23 +138,26 @@ public class LDOF<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBas
if(LOG.isVerbose()) {
LOG.verbose("Computing LDOFs");
}
- FiniteProgress progressLDOFs = LOG.isVerbose() ? new FiniteProgress("LDOF_SCORE for objects", relation.size(), LOG) : null;
+ FiniteProgress progressLDOFs = LOG.isVerbose() ? new FiniteProgress("LDOF for objects", relation.size(), LOG) : null;
Mean dxp = new Mean(), Dxp = new Mean();
for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
- KNNList<D> neighbors = knnQuery.getKNNForDBID(iditer, k);
- // skip the point itself
+ KNNList neighbors = knnQuery.getKNNForDBID(iditer, k + 1);
dxp.reset();
Dxp.reset();
- // TODO: optimize for double distances
- for(DistanceDBIDListIter<D> neighbor1 = neighbors.iter(); neighbor1.valid(); neighbor1.advance()) {
- if(!DBIDUtil.equal(neighbor1, iditer)) {
- dxp.put(neighbor1.getDistance().doubleValue());
- for(DistanceDBIDListIter<D> neighbor2 = neighbors.iter(); neighbor2.valid(); neighbor2.advance()) {
- if(!DBIDUtil.equal(neighbor1, neighbor2) && !DBIDUtil.equal(neighbor2, iditer)) {
- Dxp.put(distFunc.distance(neighbor1, neighbor2).doubleValue());
- }
+ DoubleDBIDListIter neighbor1 = neighbors.iter(), neighbor2 = neighbors.iter();
+ for(; neighbor1.valid(); neighbor1.advance()) {
+ // skip the point itself
+ if(DBIDUtil.equal(neighbor1, iditer)) {
+ continue;
+ }
+ dxp.put(neighbor1.doubleValue());
+ for(neighbor2.seek(neighbor1.getOffset() + 1); neighbor2.valid(); neighbor2.advance()) {
+ // skip the point itself
+ if(DBIDUtil.equal(neighbor2, iditer)) {
+ continue;
}
+ Dxp.put(distFunc.distance(neighbor1, neighbor2));
}
}
double ldof = dxp.getMean() / Dxp.getMean();
@@ -162,16 +168,12 @@ public class LDOF<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBas
// update maximum
ldofminmax.put(ldof);
- if(progressLDOFs != null) {
- progressLDOFs.incrementProcessed(LOG);
- }
- }
- if(progressLDOFs != null) {
- progressLDOFs.ensureCompleted(LOG);
+ LOG.incrementProcessed(progressLDOFs);
}
+ LOG.ensureCompleted(progressLDOFs);
// Build result representation.
- Relation<Double> scoreResult = new MaterializedRelation<>("LDOF Outlier Score", "ldof-outlier", TypeUtil.DOUBLE, ldofs, relation.getDBIDs());
+ DoubleRelation scoreResult = new MaterializedDoubleRelation("LDOF Outlier Score", "ldof-outlier", ldofs, relation.getDBIDs());
OutlierScoreMeta scoreMeta = new QuotientOutlierScoreMeta(ldofminmax.getMin(), ldofminmax.getMax(), 0.0, Double.POSITIVE_INFINITY, LDOF_BASELINE);
return new OutlierResult(scoreMeta, scoreResult);
}
@@ -193,21 +195,21 @@ public class LDOF<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBas
*
* @apiviz.exclude
*/
- public static class Parameterizer<O, D extends NumberDistance<D, ?>> extends AbstractDistanceBasedAlgorithm.Parameterizer<O, D> {
+ public static class Parameterizer<O> extends AbstractDistanceBasedAlgorithm.Parameterizer<O> {
protected int k = 0;
@Override
protected void makeOptions(Parameterization config) {
super.makeOptions(config);
final IntParameter kP = new IntParameter(K_ID);
- kP.addConstraint(CommonConstraints.GREATER_THAN_ONE_INT);
+ kP.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT);
if(config.grab(kP)) {
k = kP.getValue();
}
}
@Override
- protected LDOF<O, D> makeInstance() {
+ protected LDOF<O> makeInstance() {
return new LDOF<>(distanceFunction, k);
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-08 00:19:11 +0000