de.lmu.ifi.dbs.elki.application.greedyensemble

Class GreedyEnsembleExperiment

java.lang.Object

de.lmu.ifi.dbs.elki.application.AbstractApplication

de.lmu.ifi.dbs.elki.application.greedyensemble.GreedyEnsembleExperiment

@Reference(authors="E. Schubert, R. Wojdanowski, A. Zimek, H.-P. Kriegel",
           title="On Evaluation of Outlier Rankings and Outlier Scores",
           booktitle="Proc. 12th SIAM International Conference on Data Mining (SDM), Anaheim, CA, 2012.",
           url="http://dx.doi.org/10.1137/1.9781611972825.90")
public class GreedyEnsembleExperiment
extends AbstractApplication

Class to load an outlier detection summary file, as produced by ComputeKNNOutlierScores, and compute a naive ensemble for it. Based on this initial estimation, and optimized ensemble is built using a greedy strategy. Starting with the best candidate only as initial ensemble, the most diverse candidate is investigated at each step. If it improves towards the (estimated) target vector, it is added, otherwise it is discarded. This approach is naive, and it may be surprising that it can improve results. The reason is probably that diversity will result in a comparable ensemble, while the reduced ensemble size is actually responsible for the improvements, by being more decisive and less noisy due to dropping "unhelpful" members. This still leaves quite a bit of room for improvement. If you build upon this basic approach, please acknowledge our proof of concept work. Reference:

E. Schubert, R. Wojdanowski, A. Zimek, H.-P. Kriegel
On Evaluation of Outlier Rankings and Outlier Scores
In Proceedings of the 12th SIAM International Conference on Data Mining (SDM), Anaheim, CA, 2012.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	GreedyEnsembleExperiment.Distance Distance modes.
static class	GreedyEnsembleExperiment.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) GreedyEnsembleExperiment.Distance	distance Distance in use.
private InputStep	inputstep The data input part.
private static Logging	LOG Get static logger.
(package private) int	minvote Minimum votes.
(package private) ScalingFunction	prescaling Outlier scaling to apply during preprocessing.
(package private) double	rate Expected rate of outliers.
(package private) boolean	refine_truth Variant, where the truth vector is also updated.
(package private) ScalingFunction	scaling Outlier scaling to apply to constructed ensembles.
(package private) EnsembleVoting	voting Ensemble voting method.

Fields inherited from class de.lmu.ifi.dbs.elki.application.AbstractApplication

REFERENCE, VERSION

Constructor Summary

Constructors

Constructor and Description
GreedyEnsembleExperiment(InputStep inputstep, EnsembleVoting voting, GreedyEnsembleExperiment.Distance distance, ScalingFunction prescaling, ScalingFunction scaling, double rate) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
static Relation<NumberVector>	applyPrescaling(ScalingFunction scaling, Relation<NumberVector> relation, DBIDs skip) Prescale each vector (except when in skip) with the given scaling function.
private static void	applyScaling(double[] raw, ScalingFunction scaling)
(package private) double	gain(double score, double ref, double optimal) Compute the gain coefficient.
private PrimitiveDistanceFunction<NumberVector>	getDistanceFunction(double[] estimated_weights)
static void	main(String[] args) Main method.
void	run() Runs the application.
protected void	singleEnsemble(double[] ensemble, NumberVector vec) Build a single-element "ensemble".
protected void	updateEstimations(int[] outliers, int numoutliers, double[] weights, double[] truth)

Methods inherited from class de.lmu.ifi.dbs.elki.application.AbstractApplication

printErrorMessage, runCLIApplication, usage

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG

private static final Logging LOG

Get static logger.

inputstep

private InputStep inputstep

The data input part.

refine_truth

boolean refine_truth

Variant, where the truth vector is also updated.

voting

EnsembleVoting voting

Ensemble voting method.

prescaling

ScalingFunction prescaling

Outlier scaling to apply during preprocessing.

scaling

ScalingFunction scaling

Outlier scaling to apply to constructed ensembles.

rate

double rate

Expected rate of outliers.

minvote

int minvote

Minimum votes.

distance

GreedyEnsembleExperiment.Distance distance

Distance in use.

Constructor Detail

GreedyEnsembleExperiment

public GreedyEnsembleExperiment(InputStep inputstep,
                        EnsembleVoting voting,
                        GreedyEnsembleExperiment.Distance distance,
                        ScalingFunction prescaling,
                        ScalingFunction scaling,
                        double rate)

Constructor.

Parameters:

inputstep - Input step

voting - Ensemble voting

distance - Distance function

prescaling - Scaling to apply to input data

scaling - Scaling to apply to ensemble members

rate - Expected rate of outliers

Method Detail

run

public void run()

Description copied from class: AbstractApplication

Runs the application.

Specified by:

run in class AbstractApplication

singleEnsemble

protected void singleEnsemble(double[] ensemble,
                  NumberVector vec)

Build a single-element "ensemble".

Parameters:

ensemble -

vec -

applyPrescaling

public static Relation<NumberVector> applyPrescaling(ScalingFunction scaling,
                                     Relation<NumberVector> relation,
                                     DBIDs skip)

Prescale each vector (except when in skip) with the given scaling function.

Parameters:

scaling - Scaling function

relation - Relation to read

skip - DBIDs to pass unmodified

Returns:

New relation

applyScaling

private static void applyScaling(double[] raw,
                ScalingFunction scaling)

updateEstimations

protected void updateEstimations(int[] outliers,
                     int numoutliers,
                     double[] weights,
                     double[] truth)

getDistanceFunction

private PrimitiveDistanceFunction<NumberVector> getDistanceFunction(double[] estimated_weights)

gain

double gain(double score,
          double ref,
          double optimal)

Compute the gain coefficient.

Parameters:

score - New score

ref - Reference score

optimal - Maximum score possible

Returns:

Gain

main

public static void main(String[] args)

Main method.

Parameters:

args - Command line parameters.