4 files changed, 624 insertions, 0 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/EMOutlier.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/EMOutlier.java
new file mode 100644
index 00000000..5a02fb56
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/EMOutlier.java
@@ -0,0 +1,166 @@
+package de.lmu.ifi.dbs.elki.algorithm.outlier.clustering;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2014
+ 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.AbstractAlgorithm;
+import de.lmu.ifi.dbs.elki.algorithm.clustering.em.EM;
+import de.lmu.ifi.dbs.elki.algorithm.outlier.OutlierAlgorithm;
+import de.lmu.ifi.dbs.elki.data.Clustering;
+import de.lmu.ifi.dbs.elki.data.NumberVector;
+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.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.logging.Logging;
+import de.lmu.ifi.dbs.elki.result.Result;
+import de.lmu.ifi.dbs.elki.result.outlier.OutlierResult;
+import de.lmu.ifi.dbs.elki.result.outlier.OutlierScoreMeta;
+import de.lmu.ifi.dbs.elki.result.outlier.ProbabilisticOutlierScore;
+import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil;
+import de.lmu.ifi.dbs.elki.utilities.datastructures.hierarchy.Hierarchy.Iter;
+import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
+import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
+
+/**
+ * outlier detection algorithm using EM Clustering. If an object does not belong
+ * to any cluster it is supposed to be an outlier. If the probability for an
+ * object to belong to the most probable cluster is still relatively low this
+ * object is an outlier.
+ * 
+ * @author Lisa Reichert
+ * 
+ * @apiviz.has EM
+ * 
+ * @param <V> Vector type
+ */
+// TODO: re-use an existing EM when present?
+@Title("EM Outlier: Outlier Detection based on the generic EM clustering")
+@Description("The outlier score assigned is based on the highest cluster probability obtained from EM clustering.")
+public class EMOutlier<V extends NumberVector> extends AbstractAlgorithm<OutlierResult> implements OutlierAlgorithm {
+  /**
+   * The logger for this class.
+   */
+  private static final Logging LOG = Logging.getLogger(EMOutlier.class);
+
+  /**
+   * Inner algorithm.
+   */
+  private EM<V, ?> emClustering;
+
+  /**
+   * Constructor with an existing em clustering algorithm.
+   * 
+   * @param emClustering EM clustering algorithm to use.
+   */
+  public EMOutlier(EM<V, ?> emClustering) {
+    super();
+    this.emClustering = emClustering;
+  }
+
+  /**
+   * Runs the algorithm in the timed evaluation part.
+   * 
+   * @param database Database to process
+   * @param relation Relation to process
+   * @return Outlier result
+   */
+  public OutlierResult run(Database database, Relation<V> relation) {
+    emClustering.setSoft(true);
+    Clustering<?> emresult = emClustering.run(database, relation);
+    Relation<double[]> soft = null;
+    for(Iter<Result> iter = emresult.getHierarchy().iterChildren(emresult); iter.valid(); iter.advance()) {
+      if(!(iter.get() instanceof Relation)) {
+        continue;
+      }
+      if(((Relation<?>) iter.get()).getDataTypeInformation() == EM.SOFT_TYPE) {
+        @SuppressWarnings("unchecked")
+        Relation<double[]> rel = (Relation<double[]>) iter.get();
+        soft = rel;
+      }
+    }
+
+    double globmax = 0.0;
+    WritableDoubleDataStore emo_score = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_TEMP | DataStoreFactory.HINT_HOT);
+    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
+      double maxProb = Double.POSITIVE_INFINITY;
+      double[] probs = soft.get(iditer);
+      for(double prob : probs) {
+        maxProb = Math.min(1. - prob, maxProb);
+      }
+      emo_score.putDouble(iditer, maxProb);
+      globmax = Math.max(maxProb, globmax);
+    }
+    DoubleRelation scoreres = new MaterializedDoubleRelation("EM outlier scores", "em-outlier", emo_score, relation.getDBIDs());
+    OutlierScoreMeta meta = new ProbabilisticOutlierScore(0.0, globmax);
+    // combine results.
+    OutlierResult result = new OutlierResult(meta, scoreres);
+    // TODO: add a keep-EM flag?
+    result.addChildResult(emresult);
+    return result;
+  }
+
+  @Override
+  public TypeInformation[] getInputTypeRestriction() {
+    return TypeUtil.array(TypeUtil.NUMBER_VECTOR_FIELD);
+  }
+
+  @Override
+  protected Logging getLogger() {
+    return LOG;
+  }
+
+  /**
+   * Parameterization class.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   */
+  public static class Parameterizer<V extends NumberVector> extends AbstractParameterizer {
+    /**
+     * EM clustering algorithm to run.
+     */
+    protected EM<V, ?> em;
+
+    @Override
+    protected void makeOptions(Parameterization config) {
+      super.makeOptions(config);
+      Class<EM<V, ?>> cls = ClassGenericsUtil.uglyCastIntoSubclass(EM.class);
+      em = config.tryInstantiate(cls);
+    }
+
+    @Override
+    protected EMOutlier<V> makeInstance() {
+      return new EMOutlier<>(em);
+    }
+  }
+}
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/KMeansOutlierDetection.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/KMeansOutlierDetection.java
new file mode 100644
index 00000000..c6155527
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/KMeansOutlierDetection.java
@@ -0,0 +1,178 @@
+package de.lmu.ifi.dbs.elki.algorithm.outlier.clustering;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2014
+ Ludwig-Maximilians-Universität München
+ Lehr- und Forschungseinheit für Datenbanksysteme
+ ELKI Development Team
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Affero General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU Affero General Public License for more details.
+
+ You should have received a copy of the GNU Affero General Public License
+ along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+import java.util.List;
+
+import de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm;
+import de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeans;
+import de.lmu.ifi.dbs.elki.algorithm.clustering.kmeans.KMeansLloyd;
+import de.lmu.ifi.dbs.elki.algorithm.outlier.OutlierAlgorithm;
+import de.lmu.ifi.dbs.elki.data.Cluster;
+import de.lmu.ifi.dbs.elki.data.Clustering;
+import de.lmu.ifi.dbs.elki.data.NumberVector;
+import de.lmu.ifi.dbs.elki.data.model.ModelUtil;
+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.query.distance.DistanceQuery;
+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.database.relation.RelationUtil;
+import de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction;
+import de.lmu.ifi.dbs.elki.logging.Logging;
+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.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;
+
+/**
+ * Outlier detection by using k-means clustering.
+ * 
+ * The scores are assigned by the objects distance to the nearest center.
+ * 
+ * We don't have a clear reference for this approach, but it seems to be a best
+ * practise in some areas to remove objects that have the largest distance from
+ * their center. If you need to cite this approach, please cite the ELKI version
+ * you used (use the <a href="http://elki.dbs.ifi.lmu.de/wiki/Publications">ELKI
+ * publication list</a> for citation information and BibTeX templates).
+ * 
+ * @author Erich Schubert
+ * 
+ * @apiviz.has KMeans
+ * 
+ * @param <O> Object type
+ */
+public class KMeansOutlierDetection<O extends NumberVector> extends AbstractAlgorithm<OutlierResult> implements OutlierAlgorithm {
+  /**
+   * Class logger.
+   */
+  private static final Logging LOG = Logging.getLogger(KMeansOutlierDetection.class);
+
+  /**
+   * Clustering algorithm to use
+   */
+  KMeans<O, ?> clusterer;
+
+  /**
+   * Constructor.
+   * 
+   * @param clusterer Clustering algorithm
+   */
+  public KMeansOutlierDetection(KMeans<O, ?> clusterer) {
+    super();
+    this.clusterer = clusterer;
+  }
+
+  /**
+   * Run the outlier detection algorithm.
+   * 
+   * @param database Database
+   * @param relation Relation
+   * @return Outlier detection result
+   */
+  public OutlierResult run(Database database, Relation<O> relation) {
+    DistanceFunction<? super O> df = clusterer.getDistanceFunction();
+    DistanceQuery<O> dq = database.getDistanceQuery(relation, df);
+
+    // TODO: improve ELKI api to ensure we're using the same DBIDs!
+    Clustering<?> c = clusterer.run(database, relation);
+
+    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_DB);
+    DoubleMinMax mm = new DoubleMinMax();
+
+    @SuppressWarnings("unchecked")
+    NumberVector.Factory<O> factory = (NumberVector.Factory<O>) RelationUtil.assumeVectorField(relation).getFactory();
+    List<? extends Cluster<?>> clusters = c.getAllClusters();
+    for(Cluster<?> cluster : clusters) {
+      // FIXME: use a primitive distance function on number vectors instead.
+      O mean = factory.newNumberVector(ModelUtil.getPrototype(cluster.getModel(), relation));
+      for(DBIDIter iter = cluster.getIDs().iter(); iter.valid(); iter.advance()) {
+        double dist = dq.distance(mean, iter);
+        scores.put(iter, dist);
+        mm.put(dist);
+      }
+    }
+
+    // Build result representation.
+    DoubleRelation scoreResult = new MaterializedDoubleRelation("KMeans outlier scores", "kmeans-outlier", scores, relation.getDBIDs());
+    OutlierScoreMeta scoreMeta = new BasicOutlierScoreMeta(mm.getMin(), mm.getMax(), 0., Double.POSITIVE_INFINITY, 0.);
+    return new OutlierResult(scoreMeta, scoreResult);
+  }
+
+  @Override
+  public TypeInformation[] getInputTypeRestriction() {
+    return TypeUtil.array(clusterer.getDistanceFunction().getInputTypeRestriction());
+  }
+
+  @Override
+  protected Logging getLogger() {
+    return LOG;
+  }
+
+  /**
+   * Parameterizer.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   * 
+   * @param <O> Object type
+   */
+  public static class Parameterizer<O extends NumberVector> extends AbstractParameterizer {
+    /**
+     * Parameter for choosing the clustering algorithm.
+     */
+    public static final OptionID CLUSTERING_ID = new OptionID("kmeans.algorithm", //
+    "Clustering algorithm to use for detecting outliers.");
+
+    /**
+     * Clustering algorithm to use
+     */
+    KMeans<O, ?> clusterer;
+
+    @Override
+    protected void makeOptions(Parameterization config) {
+      super.makeOptions(config);
+
+      ObjectParameter<KMeans<O, ?>> clusterP = new ObjectParameter<>(CLUSTERING_ID, KMeans.class, KMeansLloyd.class);
+      if(config.grab(clusterP)) {
+        clusterer = clusterP.instantiateClass(config);
+      }
+    }
+
+    @Override
+    protected KMeansOutlierDetection<O> makeInstance() {
+      return new KMeansOutlierDetection<>(clusterer);
+    }
+  }
+}
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/SilhouetteOutlierDetection.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/SilhouetteOutlierDetection.java
new file mode 100644
index 00000000..3bd9cf8b
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/SilhouetteOutlierDetection.java
@@ -0,0 +1,253 @@
+package de.lmu.ifi.dbs.elki.algorithm.outlier.clustering;
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2014
+ Ludwig-Maximilians-Universität München
+ Lehr- und Forschungseinheit für Datenbanksysteme
+ ELKI Development Team
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Affero General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU Affero General Public License for more details.
+
+ You should have received a copy of the GNU Affero General Public License
+ along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+import java.util.List;
+
+import de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm;
+import de.lmu.ifi.dbs.elki.algorithm.clustering.ClusteringAlgorithm;
+import de.lmu.ifi.dbs.elki.algorithm.outlier.OutlierAlgorithm;
+import de.lmu.ifi.dbs.elki.data.Cluster;
+import de.lmu.ifi.dbs.elki.data.Clustering;
+import de.lmu.ifi.dbs.elki.data.type.TypeInformation;
+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.ArrayDBIDs;
+import de.lmu.ifi.dbs.elki.database.ids.DBIDArrayIter;
+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.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.evaluation.clustering.internal.EvaluateSilhouette;
+import de.lmu.ifi.dbs.elki.logging.Logging;
+import de.lmu.ifi.dbs.elki.math.DoubleMinMax;
+import de.lmu.ifi.dbs.elki.result.outlier.InvertedOutlierScoreMeta;
+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.Reference;
+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.Flag;
+import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter;
+
+/**
+ * Outlier detection by using the Silhouette Coefficients.
+ * 
+ * Silhouette values are computed as in:
+ * <p>
+ * P. J. Rousseeuw<br />
+ * Silhouettes: A graphical aid to the interpretation and validation of cluster
+ * analysis<br />
+ * In: Journal of Computational and Applied Mathematics Volume 20, November 1987
+ * </p>
+ * 
+ * but then used as outlier scores. To cite this outlier detection approach,
+ * please cite the ELKI version you used (use the <a
+ * href="http://elki.dbs.ifi.lmu.de/wiki/Publications">ELKI publication list</a>
+ * for citation information and BibTeX templates).
+ * 
+ * @author Erich Schubert
+ * 
+ * @apiviz.has ClusteringAlgorithm
+ * 
+ * @param <O> Object type
+ */
+@Reference(authors = "P. J. Rousseeuw", //
+title = "Silhouettes: A graphical aid to the interpretation and validation of cluster analysis", //
+booktitle = "Journal of Computational and Applied Mathematics, Volume 20", //
+url = "http://dx.doi.org/10.1016%2F0377-0427%2887%2990125-7")
+public class SilhouetteOutlierDetection<O> extends AbstractDistanceBasedAlgorithm<O, OutlierResult> implements OutlierAlgorithm {
+  /**
+   * Class logger.
+   */
+  private static final Logging LOG = Logging.getLogger(SilhouetteOutlierDetection.class);
+
+  /**
+   * Clustering algorithm to use
+   */
+  ClusteringAlgorithm<?> clusterer;
+
+  /**
+   * Keep noise "clusters" merged, instead of breaking them into singletons.
+   */
+  private boolean mergenoise = false;
+
+  /**
+   * Constructor.
+   * 
+   * @param distanceFunction Distance function
+   * @param clusterer Clustering algorithm
+   * @param mergenoise Flag to keep "noise" clusters merged, instead of breaking
+   *        them into singletons.
+   */
+  public SilhouetteOutlierDetection(DistanceFunction<? super O> distanceFunction, ClusteringAlgorithm<?> clusterer, boolean mergenoise) {
+    super(distanceFunction);
+    this.clusterer = clusterer;
+    this.mergenoise = mergenoise;
+  }
+
+  @Override
+  public OutlierResult run(Database database) {
+    Relation<O> relation = database.getRelation(getDistanceFunction().getInputTypeRestriction());
+    DistanceQuery<O> dq = database.getDistanceQuery(relation, getDistanceFunction());
+
+    // TODO: improve ELKI api to ensure we're using the same DBIDs!
+    Clustering<?> c = clusterer.run(database);
+
+    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_DB);
+    DoubleMinMax mm = new DoubleMinMax();
+
+    List<? extends Cluster<?>> clusters = c.getAllClusters();
+    for(Cluster<?> cluster : clusters) {
+      if(cluster.size() <= 1 || (!mergenoise && cluster.isNoise())) {
+        // As suggested in Rousseeuw, we use 0 for singletons.
+        for(DBIDIter iter = cluster.getIDs().iter(); iter.valid(); iter.advance()) {
+          scores.put(iter, 0.);
+        }
+        mm.put(0.);
+        continue;
+      }
+      ArrayDBIDs ids = DBIDUtil.ensureArray(cluster.getIDs());
+      double[] as = new double[ids.size()]; // temporary storage.
+      DBIDArrayIter it1 = ids.iter(), it2 = ids.iter();
+      for(it1.seek(0); it1.valid(); it1.advance()) {
+        // a: In-cluster distances
+        double a = as[it1.getOffset()]; // Already computed distances
+        for(it2.seek(it1.getOffset() + 1); it2.valid(); it2.advance()) {
+          final double dist = dq.distance(it1, it2);
+          a += dist;
+          as[it2.getOffset()] += dist;
+        }
+        a /= (ids.size() - 1);
+        // b: other clusters:
+        double min = Double.POSITIVE_INFINITY;
+        for(Cluster<?> ocluster : clusters) {
+          if(ocluster == /* yes, reference identity */cluster) {
+            continue;
+          }
+          if(!mergenoise && ocluster.isNoise()) {
+            // Treat noise cluster as singletons:
+            for(DBIDIter it3 = ocluster.getIDs().iter(); it3.valid(); it3.advance()) {
+              double dist = dq.distance(it1, it3);
+              if(dist < min) {
+                min = dist;
+              }
+            }
+            continue;
+          }
+          final DBIDs oids = ocluster.getIDs();
+          double b = 0.;
+          for(DBIDIter it3 = oids.iter(); it3.valid(); it3.advance()) {
+            b += dq.distance(it1, it3);
+          }
+          b /= oids.size();
+          if(b < min) {
+            min = b;
+          }
+        }
+        final double score = (min - a) / Math.max(min, a);
+        scores.put(it1, score);
+        mm.put(score);
+      }
+    }
+
+    // Build result representation.
+    DoubleRelation scoreResult = new MaterializedDoubleRelation("Silhouette Coefficients", "silhouette-outlier", scores, relation.getDBIDs());
+    OutlierScoreMeta scoreMeta = new InvertedOutlierScoreMeta(mm.getMin(), mm.getMax(), -1., 1., .5);
+    return new OutlierResult(scoreMeta, scoreResult);
+  }
+
+  @Override
+  public TypeInformation[] getInputTypeRestriction() {
+    final TypeInformation dt = getDistanceFunction().getInputTypeRestriction();
+    TypeInformation[] t = clusterer.getInputTypeRestriction();
+    for(TypeInformation i : t) {
+      if(dt.isAssignableFromType(i)) {
+        return t;
+      }
+    }
+    // Prepend distance type:
+    TypeInformation[] t2 = new TypeInformation[t.length + 1];
+    t2[0] = dt;
+    System.arraycopy(t, 0, t2, 1, t.length);
+    return t2;
+  }
+
+  @Override
+  protected Logging getLogger() {
+    return LOG;
+  }
+
+  /**
+   * Parameterizer.
+   * 
+   * @author Erich Schubert
+   * 
+   * @apiviz.exclude
+   * 
+   * @param <O> Object type
+   */
+  public static class Parameterizer<O> extends AbstractDistanceBasedAlgorithm.Parameterizer<O> {
+    /**
+     * Parameter for choosing the clustering algorithm
+     */
+    public static final OptionID CLUSTERING_ID = new OptionID("silhouette.clustering", //
+    "Clustering algorithm to use for the silhouette coefficients.");
+
+    /**
+     * Clustering algorithm to use
+     */
+    ClusteringAlgorithm<?> clusterer;
+
+    /**
+     * Keep noise "clusters" merged, instead of breaking them into singletons.
+     */
+    private boolean mergenoise = false;
+
+    @Override
+    protected void makeOptions(Parameterization config) {
+      super.makeOptions(config);
+
+      ObjectParameter<ClusteringAlgorithm<?>> clusterP = new ObjectParameter<>(CLUSTERING_ID, ClusteringAlgorithm.class);
+      if(config.grab(clusterP)) {
+        clusterer = clusterP.instantiateClass(config);
+      }
+
+      Flag noiseP = new Flag(EvaluateSilhouette.Parameterizer.MERGENOISE_ID);
+      if(config.grab(noiseP)) {
+        mergenoise = noiseP.isTrue();
+      }
+    }
+
+    @Override
+    protected SilhouetteOutlierDetection<O> makeInstance() {
+      return new SilhouetteOutlierDetection<>(distanceFunction, clusterer, mergenoise);
+    }
+  }
+}
diff --git a/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/package-info.java b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/package-info.java
new file mode 100644
index 00000000..15ee771e
--- /dev/null
+++ b/src/de/lmu/ifi/dbs/elki/algorithm/outlier/clustering/package-info.java
@@ -0,0 +1,27 @@
+/**
+ * Clustering based outlier detection.
+ */
+
+/*
+ This file is part of ELKI:
+ Environment for Developing KDD-Applications Supported by Index-Structures
+
+ Copyright (C) 2014
+ 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/>.
+ */
+package de.lmu.ifi.dbs.elki.algorithm.outlier.clustering;
+\ No newline at end of file