Performs the APRIORI algorithm on the given database.

@param relation the Relation to process
@return the AprioriResult learned by this APRIORI
433105
public FrequentItemsetsResult run(Relation<BitVector> relation) {
    DBIDs ids = relation.getDBIDs();
    List<Itemset> solution = new ArrayList<>();
    final int size = ids.size();
    final int needed = getMinimumSupport(size);

    // TODO: we don't strictly require a vector field.
    // We could work with knowing just the maximum dimensionality beforehand.
    VectorFieldTypeInformation<BitVector> meta = RelationUtil.assumeVectorField(relation);
    if(size > 0) {
      final int dim = meta.getDimensionality();
      Duration timeone = LOG.newDuration(STAT + "1-items.time").begin();
      List<OneItemset> oneitems = buildFrequentOneItemsets(relation, dim, needed);
      LOG.statistics(timeone.end());
      if(LOG.isStatistics()) {
        LOG.statistics(new LongStatistic(STAT + "1-items.frequent", oneitems.size()));
        LOG.statistics(new LongStatistic(STAT + "1-items.transactions", ids.size()));
      }
      if(LOG.isDebuggingFine()) {
        LOG.debugFine(debugDumpCandidates(new StringBuilder(), oneitems, meta));
      }
      if(minlength <= 1) {
        solution.addAll(oneitems);
      }
      if(oneitems.size() >= 2 && maxlength >= 2) {
        Duration timetwo = LOG.newDuration(STAT + "2-items.time").begin();
        ArrayModifiableDBIDs survivors = DBIDUtil.newArray(ids.size());
        List<? extends Itemset> candidates = buildFrequentTwoItemsets(oneitems, relation, dim, needed, ids, survivors);
        ids = survivors; // Continue with reduced set of transactions.
        LOG.statistics(timetwo.end());
        if(LOG.isStatistics()) {
          LOG.statistics(new LongStatistic(STAT + "2-items.frequent", candidates.size()));
          LOG.statistics(new LongStatistic(STAT + "2-items.transactions", ids.size()));
        }
        if(LOG.isDebuggingFine()) {
          LOG.debugFine(debugDumpCandidates(new StringBuilder(), candidates, meta));
        }
        if(minlength <= 2) {
          solution.addAll(candidates);
        }
        for(int length = 3; length <= maxlength && candidates.size() >= length; length++) {
          Duration timel = LOG.newDuration(STAT + length + "-items.time").begin();
          // Join to get the new candidates
          candidates = aprioriGenerate(candidates, length, dim);
          if(LOG.isDebuggingFinest()) {
            LOG.debugFinest(debugDumpCandidates(new StringBuilder().append("Before pruning: "), candidates, meta));
          }
          survivors = DBIDUtil.newArray(ids.size());
          candidates = frequentItemsets(candidates, relation, needed, ids, survivors, length);
          ids = survivors; // Continue with reduced set of transactions.
          LOG.statistics(timel.end());
          if(LOG.isStatistics()) {
            LOG.statistics(new LongStatistic(STAT + length + "-items.frequent", candidates.size()));
            LOG.statistics(new LongStatistic(STAT + length + "-items.transactions", ids.size()));
          }
          if(LOG.isDebuggingFine()) {
            LOG.debugFine(debugDumpCandidates(new StringBuilder(), candidates, meta));
          }
          solution.addAll(candidates);
        }
      }
    }
    return new FrequentItemsetsResult("APRIORI", "apriori", solution, meta, size);
  }
141292
public OutlierResult run(Database database, Relation<O> relation) {
    StepProgress stepprog = LOG.isVerbose() ? new StepProgress("IDOS", 3) : null;
    if(stepprog != null) {
      stepprog.beginStep(1, "Precomputing neighborhoods", LOG);
    }
    KNNQuery<O> knnQ = DatabaseUtil.precomputedKNNQuery(database, relation, getDistanceFunction(), Math.max(k_c, k_r) + 1);
    DBIDs ids = relation.getDBIDs();

    if(stepprog != null) {
      stepprog.beginStep(2, "Computing intrinsic dimensionalities", LOG);
    }
    DoubleDataStore intDims = computeIDs(ids, knnQ);
    if(stepprog != null) {
      stepprog.beginStep(3, "Computing IDOS scores", LOG);
    }
    DoubleMinMax idosminmax = new DoubleMinMax();
    DoubleDataStore ldms = computeIDOS(ids, knnQ, intDims, idosminmax);
    if(stepprog != null) {
      stepprog.setCompleted(LOG);
    }
    DoubleRelation scoreResult = new MaterializedDoubleRelation("Intrinsic Dimensionality Outlier Score", "idos", ldms, ids);
    OutlierScoreMeta scoreMeta = new QuotientOutlierScoreMeta(idosminmax.getMin(), idosminmax.getMax(), 0.0, Double.POSITIVE_INFINITY, 1.0);
    return new OutlierResult(scoreMeta, scoreResult);
  }
1273339
public PointerHierarchyRepresentationResult run(Database db, Relation<O> relation) {
    DistanceQuery<O> dq = db.getDistanceQuery(relation, getDistanceFunction());
    ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());
    final int size = ids.size();

    if(size > 0x10000) {
      throw new AbortException("This implementation does not scale to data sets larger than " + 0x10000 + " instances (~17 GB RAM), which results in an integer overflow.");
    }
    if(Linkage.SINGLE.equals(linkage)) {
      LOG.verbose("Notice: SLINK is a much faster algorithm for single-linkage clustering!");
    }

    // Compute the initial (lower triangular) distance matrix.
    double[] scratch = new double[triangleSize(size)];
    DBIDArrayIter ix = ids.iter(), iy = ids.iter(), ij = ids.iter();
    // Position counter - must agree with computeOffset!
    int pos = 0;
    boolean square = Linkage.WARD.equals(linkage) && !getDistanceFunction().isSquared();
    for(int x = 0; ix.valid(); x++, ix.advance()) {
      iy.seek(0);
      for(int y = 0; y < x; y++, iy.advance()) {
        scratch[pos] = dq.distance(ix, iy);
        // Ward uses variances -- i.e. squared values
        if(square) {
          scratch[pos] *= scratch[pos];
        }
        pos++;
      }
    }

    // Initialize space for result:
    WritableDBIDDataStore parent = DataStoreUtil.makeDBIDStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    WritableDoubleDataStore height = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    WritableIntegerDataStore csize = DataStoreUtil.makeIntegerStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);
    for(DBIDIter it = ids.iter(); it.valid(); it.advance()) {
      parent.put(it, it);
      height.put(it, Double.POSITIVE_INFINITY);
      csize.put(it, 1);
    }

    // Repeat until everything merged, except the desired number of clusters:
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Agglomerative clustering", size - 1, LOG) : null;
    for(int i = 1; i < size; i++) {
      double min = Double.POSITIVE_INFINITY;
      int minx = -1, miny = -1;
      for(ix.seek(0); ix.valid(); ix.advance()) {
        if(height.doubleValue(ix) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int xbase = triangleSize(ix.getOffset());
        for(iy.seek(0); iy.getOffset() < ix.getOffset(); iy.advance()) {
          if(height.doubleValue(iy) < Double.POSITIVE_INFINITY) {
            continue;
          }
          final int idx = xbase + iy.getOffset();
          if(scratch[idx] <= min) {
            min = scratch[idx];
            minx = ix.getOffset();
            miny = iy.getOffset();
          }
        }
      }
      assert (minx >= 0 && miny >= 0);
      // Avoid allocating memory, by reusing existing iterators:
      ix.seek(minx);
      iy.seek(miny);
      // Perform merge in data structure: x -> y
      // Since y < x, prefer keeping y, dropping x.
      int sizex = csize.intValue(ix), sizey = csize.intValue(iy);
      height.put(ix, min);
      parent.put(ix, iy);
      csize.put(iy, sizex + sizey);

      // Update distance matrix. Note: miny < minx
      final int xbase = triangleSize(minx), ybase = triangleSize(miny);
      // Write to (y, j), with j < y
      for(ij.seek(0); ij.getOffset() < miny; ij.advance()) {
        if(height.doubleValue(ij) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int sizej = csize.intValue(ij);
        scratch[ybase + ij.getOffset()] = linkage.combine(sizex, scratch[xbase + ij.getOffset()], sizey, scratch[ybase + ij.getOffset()], sizej, min);
      }
      // Write to (j, y), with y < j < x
      for(ij.seek(miny + 1); ij.getOffset() < minx; ij.advance()) {
        if(height.doubleValue(ij) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int jbase = triangleSize(ij.getOffset());
        final int sizej = csize.intValue(ij);
        scratch[jbase + miny] = linkage.combine(sizex, scratch[xbase + ij.getOffset()], sizey, scratch[jbase + miny], sizej, min);
      }
      // Write to (j, y), with y < x < j
      for(ij.seek(minx + 1); ij.valid(); ij.advance()) {
        if(height.doubleValue(ij) < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int jbase = triangleSize(ij.getOffset());
        final int sizej = csize.intValue(ij);
        scratch[jbase + miny] = linkage.combine(sizex, scratch[jbase + minx], sizey, scratch[jbase + miny], sizej, min);
      }
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);

    return new PointerHierarchyRepresentationResult(ids, parent, height, dq.getDistanceFunction().isSquared());
  }
1279514
public OutlierResult run(Relation<? extends NumberVector> relation) {
    final DBIDs ids = relation.getDBIDs();
    WritableDoubleDataStore ranks = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_STATIC);
    DoubleMinMax minmax = new DoubleMinMax();

    KernelDensityEstimator kernel = new KernelDensityEstimator(relation, eps);
    long[] subspace = BitsUtil.zero(kernel.dim);

    FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("OUTRES scores", ids.size(), LOG) : null;

    for(DBIDIter iditer = ids.iter(); iditer.valid(); iditer.advance()) {
      BitsUtil.zeroI(subspace);
      double score = outresScore(0, subspace, iditer, kernel, ids);
      ranks.putDouble(iditer, score);
      minmax.put(score);
      LOG.incrementProcessed(progress);
    }
    LOG.ensureCompleted(progress);

    OutlierScoreMeta meta = new InvertedOutlierScoreMeta(minmax.getMin(), minmax.getMax(), 0., 1., 1.);
    return new OutlierResult(meta, new MaterializedDoubleRelation("OUTRES", "outres-score", ranks, ids));
  }
40890
public CollectionResult<double[]> run(Database database, Relation<O> relation, Relation<?> lrelation) {
    final DistanceQuery<O> distQuery = database.getDistanceQuery(relation, getDistanceFunction());
    final int qk = k + (includeSelf ? 0 : 1);
    final KNNQuery<O> knnQuery = database.getKNNQuery(distQuery, qk);

    MeanVarianceMinMax[] mvs = MeanVarianceMinMax.newArray(k);

    final DBIDs ids = DBIDUtil.randomSample(relation.getDBIDs(), sampling, random);

    FiniteProgress objloop = LOG.isVerbose() ? new FiniteProgress("Computing nearest neighbors", ids.size(), LOG) : null;
    // sort neighbors
    for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
      KNNList knn = knnQuery.getKNNForDBID(iter, qk);
      Object label = lrelation.get(iter);

      int positive = 0, i = 0;
      for(DBIDIter ri = knn.iter(); i < k && ri.valid(); ri.advance()) {
        if(!includeSelf && DBIDUtil.equal(iter, ri)) {
          // Do not increment i.
          continue;
        }
        positive += match(label, lrelation.get(ri)) ? 1 : 0;
        final double precision = positive / (double) (i + 1);
        mvs[i].put(precision);
        i++;
      }
      LOG.incrementProcessed(objloop);
    }
    LOG.ensureCompleted(objloop);

    // Transform Histogram into a Double Vector array.
    Collection<double[]> res = new ArrayList<>(k);
    for(int i = 0; i < k; i++) {
      final MeanVarianceMinMax mv = mvs[i];
      final double std = mv.getCount() > 1. ? mv.getSampleStddev() : 0.;
      res.add(new double[] { i + 1, mv.getMean(), std, mv.getMin(), mv.getMax(), mv.getCount() });
    }
    return new CollectionResult<>("Average Precision", "average-precision", res);
  }
63452
public PointerDensityHierarchyRepresentationResult run(Database db, Relation<O> relation) {
    final DistanceQuery<O> distQ = db.getDistanceQuery(relation, getDistanceFunction());
    final KNNQuery<O> knnQ = db.getKNNQuery(distQ, minPts);
    // We need array addressing later.
    final ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());

    // Compute the core distances
    // minPts + 1: ignore query point.
    final WritableDoubleDataStore coredists = computeCoreDists(ids, knnQ, minPts);

    WritableDBIDDataStore pi = DataStoreUtil.makeDBIDStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    WritableDoubleDataStore lambda = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC, Double.POSITIVE_INFINITY);
    // Temporary storage for m.
    WritableDoubleDataStore m = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);

    FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("Running HDBSCAN*-SLINK", ids.size(), LOG) : null;
    // has to be an array for monotonicity reasons!
    ModifiableDBIDs processedIDs = DBIDUtil.newArray(ids.size());

    for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
      // Steps 1,3,4 are exactly as in SLINK
      step1(id, pi, lambda);
      // Step 2 is modified to use a different distance
      step2(id, processedIDs, distQ, coredists, m);
      step3(id, pi, lambda, processedIDs, m);
      step4(id, pi, lambda, processedIDs);

      processedIDs.add(id);

      LOG.incrementProcessed(progress);
    }
    LOG.ensureCompleted(progress);

    return new PointerDensityHierarchyRepresentationResult(ids, pi, lambda, distQ.getDistanceFunction().isSquared(), coredists);
  }
761339
public PointerPrototypeHierarchyRepresentationResult run(Database db, Relation<O> relation) {
    DistanceQuery<O> dq = DatabaseUtil.precomputedDistanceQuery(db, relation, getDistanceFunction(), LOG);
    final DBIDs ids = relation.getDBIDs();
    final int size = ids.size();

    // Initialize space for result:
    PointerHierarchyRepresentationBuilder builder = new PointerHierarchyRepresentationBuilder(ids, dq.getDistanceFunction().isSquared());
    Int2ObjectOpenHashMap<ModifiableDBIDs> clusters = new Int2ObjectOpenHashMap<>(size);

    // Allocate working space:
    MatrixParadigm mat = new MatrixParadigm(ids);
    ArrayModifiableDBIDs prots = DBIDUtil.newArray(MatrixParadigm.triangleSize(size));
    initializeMatrices(mat, prots, dq);

    DBIDArrayMIter protiter = prots.iter();
    FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("MiniMax clustering", size - 1, LOG) : null;
    DBIDArrayIter ix = mat.ix;
    for(int i = 1, end = size; i < size; i++) {
      end = AGNES.shrinkActiveSet(ix, builder, end, //
          findMerge(end, mat, protiter, builder, clusters, dq));
      LOG.incrementProcessed(progress);
    }
    LOG.ensureCompleted(progress);
    return (PointerPrototypeHierarchyRepresentationResult) builder.complete();
  }
13577
public Instance instantiate(Database database, Relation<V> relation) {
    DistanceQuery<V> dq = database.getDistanceQuery(relation, EuclideanDistanceFunction.STATIC);
    KNNQuery<V> knnq = database.getKNNQuery(dq, settings.k);

    WritableDataStore<PCAFilteredResult> storage = DataStoreUtil.makeStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP, PCAFilteredResult.class);

    PCARunner pca = settings.pca;
    EigenPairFilter filter = settings.filter;
    Duration time = LOG.newDuration(this.getClass().getName() + ".preprocessing-time").begin();
    FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress(this.getClass().getName(), relation.size(), LOG) : null;
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      DoubleDBIDList ref = knnq.getKNNForDBID(iditer, settings.k);
      PCAResult pcares = pca.processQueryResult(ref, relation);
      storage.put(iditer, new PCAFilteredResult(pcares.getEigenPairs(), filter.filter(pcares.getEigenvalues()), 1., 0.));
      LOG.incrementProcessed(progress);
    }
    LOG.ensureCompleted(progress);
    LOG.statistics(time.end());
    return new Instance(relation.getDBIDs(), storage, relation);
  }
558706
public OutlierResult run(Relation<V> relation) {
    final int dim = RelationUtil.dimensionality(relation);
    final int size = relation.size();
    ArrayList<ArrayList<DBIDs>> ranges = buildRanges(relation);

    ArrayList<int[]> Rk;
    // Build a list of all subspaces
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Subspace size", k, LOG) : null;
    // R1 initial one-dimensional subspaces.
    Rk = new ArrayList<>();
    // Set of all dim*phi ranges
    ArrayList<IntIntPair> q = new ArrayList<>();
    for(int i = 0; i < dim; i++) {
      for(int j = 0; j < phi; j++) {
        q.add(new IntIntPair(i, j));
        Rk.add(new int[] { i, j });
      }
    }
    LOG.incrementProcessed(prog);

    // build Ri
    for(int i = 2; i <= k; i++) {
      ArrayList<int[]> Rnew = new ArrayList<>();

      for(int j = 0; j < Rk.size(); j++) {
        int[] c = Rk.get(j);
        for(IntIntPair pair : q) {
          boolean invalid = false;
          for(int t = 0; t < c.length; t += 2) {
            if(c[t] == pair.first) {
              invalid = true;
              break;
            }
          }
          if(!invalid) {
            int[] neu = Arrays.copyOf(c, c.length + 2);
            neu[c.length] = pair.first;
            neu[c.length + 1] = pair.second;
            Rnew.add(neu);
          }
        }
      }
      Rk = Rnew;
      LOG.incrementProcessed(prog);
    }
    if(prog != null) {
      prog.setProcessed(k, LOG);
    }
    LOG.ensureCompleted(prog);

    WritableDoubleDataStore sparsity = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    // calculate the sparsity coefficient
    for(int[] sub : Rk) {
      DBIDs ids = computeSubspace(sub, ranges);
      final double sparsityC = sparsity(ids.size(), size, k, phi);

      if(sparsityC < 0) {
        for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
          double prev = sparsity.doubleValue(iter);
          if(Double.isNaN(prev) || sparsityC < prev) {
            sparsity.putDouble(iter, sparsityC);
          }
        }
      }
    }
    DoubleMinMax minmax = new DoubleMinMax();
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      double val = sparsity.doubleValue(iditer);
      if(Double.isNaN(val)) {
        sparsity.putDouble(iditer, 0.0);
        val = 0.0;
      }
      minmax.put(val);
    }
    DoubleRelation scoreResult = new MaterializedDoubleRelation("AggarwalYuNaive", "aggarwal-yu-outlier", sparsity, relation.getDBIDs());
    OutlierScoreMeta meta = new InvertedOutlierScoreMeta(minmax.getMin(), minmax.getMax(), Double.NEGATIVE_INFINITY, 0.0);
    return new OutlierResult(meta, scoreResult);
  }
204793
public PointerHierarchyRepresentationResult run(Database db, Relation<O> relation) {
    if(SingleLinkage.class.isInstance(linkage)) {
      LOG.verbose("Notice: SLINK is a much faster algorithm for single-linkage clustering!");
    }
    DistanceQuery<O> dq = db.getDistanceQuery(relation, getDistanceFunction());
    final DBIDs ids = relation.getDBIDs();
    MatrixParadigm mat = new MatrixParadigm(ids);

    // Compute the initial (lower triangular) distance matrix.
    initializeDistanceMatrix(mat, dq, linkage);

    // Initialize space for result:
    PointerHierarchyRepresentationBuilder builder = new PointerHierarchyRepresentationBuilder(ids, dq.getDistanceFunction().isSquared());

    nnChainCore(mat, builder);
    return builder.complete();
  }
786485
public Clustering<MedoidModel> run(Database database, Relation<V> relation) {
    DistanceQuery<V> distQ = DatabaseUtil.precomputedDistanceQuery(database, relation, getDistanceFunction(), LOG);
    // Choose initial medoids
    if(LOG.isStatistics()) {
      LOG.statistics(new StringStatistic(KEY + ".initialization", initializer.toString()));
    }
    ArrayModifiableDBIDs medoids = DBIDUtil.newArray(initializer.chooseInitialMedoids(k, relation.getDBIDs(), distQ));
    DBIDArrayMIter miter = medoids.iter();
    double[] mdists = new double[k];
    // Setup cluster assignment store
    List<ModifiableDBIDs> clusters = new ArrayList<>();
    for(int i = 0; i < k; i++) {
      HashSetModifiableDBIDs set = DBIDUtil.newHashSet(relation.size() / k);
      set.add(miter.seek(i)); // Add medoids.
      clusters.add(set);
    }

    // Initial assignment to nearest medoids
    // TODO: reuse this information, from the build phase, when possible?
    double tc = assignToNearestCluster(miter, mdists, clusters, distQ);
    if(LOG.isStatistics()) {
      LOG.statistics(new DoubleStatistic(KEY + ".iteration-" + 0 + ".cost", tc));
    }

    IndefiniteProgress prog = LOG.isVerbose() ? new IndefiniteProgress("K-Medoids EM iteration", LOG) : null;
    // Swap phase
    int iteration = 0;
    DBIDVar best = DBIDUtil.newVar();
    while(true) {
      boolean changed = false;
      // Try to swap the medoid with a better cluster member:
      int i = 0;
      for(miter.seek(0); miter.valid(); miter.advance(), i++) {
        best.unset();
        double bestm = mdists[i];
        for(DBIDIter iter = clusters.get(i).iter(); iter.valid(); iter.advance()) {
          if(DBIDUtil.equal(miter, iter)) {
            continue;
          }
          double sum = 0;
          for(DBIDIter iter2 = clusters.get(i).iter(); iter2.valid(); iter2.advance()) {
            if(DBIDUtil.equal(iter, iter2)) {
              continue;
            }
            sum += distQ.distance(iter, iter2);
          }
          if(sum < bestm) {
            best.set(iter);
            bestm = sum;
          }
        }
        if(best.isSet() && !DBIDUtil.equal(miter, best)) {
          changed = true;
          assert (clusters.get(i).contains(best));
          medoids.set(i, best);
          mdists[i] = bestm;
        }
      }
      if(!changed) {
        break; // Converged
      }
      // Reassign
      double nc = assignToNearestCluster(miter, mdists, clusters, distQ);
      ++iteration;
      if(LOG.isStatistics()) {
        LOG.statistics(new DoubleStatistic(KEY + ".iteration-" + iteration + ".cost", nc));
      }
      LOG.incrementProcessed(prog);
    }
    LOG.setCompleted(prog);
    if(LOG.isStatistics()) {
      LOG.statistics(new LongStatistic(KEY + ".iterations", iteration));
    }

    // Wrap result
    Clustering<MedoidModel> result = new Clustering<>("k-Medoids Clustering", "kmedoids-clustering");
    for(DBIDArrayIter it = medoids.iter(); it.valid(); it.advance()) {
      result.addToplevelCluster(new Cluster<>(clusters.get(it.getOffset()), new MedoidModel(DBIDUtil.deref(it))));
    }
    return result;
  }
1124213
public static LinkRelation parse(String relation) {

		return LINK_RELATIONS.stream() //
				.filter(it -> it.value().equalsIgnoreCase(relation)) //
				.findFirst() //
				.orElseThrow(() -> new IllegalArgumentException(relation + " is not a valid IANA link relation!"));
	}
132378
public HistogramResult run(Database database, Relation<O> relation) {
    final DistanceQuery<O> distanceQuery = database.getDistanceQuery(relation, getDistanceFunction());
    final KNNQuery<O> knnQuery = database.getKNNQuery(distanceQuery, relation.size());

    if(LOG.isVerbose()) {
      LOG.verbose("Preprocessing clusters...");
    }
    // Cluster by labels
    Collection<Cluster<Model>> split = (new ByLabelOrAllInOneClustering()).run(database).getAllClusters();

    DoubleHistogram hist = new DoubleHistogram(numbins, 0.0, 1.0);

    if(LOG.isVerbose()) {
      LOG.verbose("Processing points...");
    }
    FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("Computing ROC AUC values", relation.size(), LOG) : null;

    ROCEvaluation roc = new ROCEvaluation();
    MeanVariance mv = new MeanVariance();
    // sort neighbors
    for(Cluster<?> clus : split) {
      for(DBIDIter iter = clus.getIDs().iter(); iter.valid(); iter.advance()) {
        KNNList knn = knnQuery.getKNNForDBID(iter, relation.size());
        double result = EvaluateClustering.evaluateRanking(roc, clus, knn);

        mv.put(result);
        hist.increment(result, 1. / relation.size());

        LOG.incrementProcessed(progress);
      }
    }
    LOG.ensureCompleted(progress);

    // Transform Histogram into a Double Vector array.
    Collection<double[]> res = new ArrayList<>(relation.size());
    for(DoubleHistogram.Iter iter = hist.iter(); iter.valid(); iter.advance()) {
      res.add(new double[] { iter.getCenter(), iter.getValue() });
    }
    HistogramResult result = new HistogramResult("Ranking Quality Histogram", "ranking-histogram", res);
    result.addHeader("Mean: " + mv.getMean() + " Variance: " + mv.getSampleVariance());
    return result;
  }
1142701
public OutlierResult run(Relation<V> relation) {
    final DBIDs ids = relation.getDBIDs();
    KNNQuery<V> knnQuery = QueryUtil.getKNNQuery(relation, getDistanceFunction(), k + 1);

    final int dim = RelationUtil.dimensionality(relation);
    if(k <= dim + 1) {
      LOG.warning("PCA is underspecified with a too low k! k should be at much larger than " + dim);
    }

    WritableDoubleDataStore cop_score = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    WritableDataStore<double[]> cop_err_v = models ? DataStoreUtil.makeStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC, double[].class) : null;
    WritableIntegerDataStore cop_dim = models ? DataStoreUtil.makeIntegerStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC, -1) : null;
    // compute neighbors of each db object
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Correlation Outlier Probabilities", relation.size(), LOG) : null;

    double[] centroid = new double[dim];
    double[] scores = new double[dim];
    ModifiableDBIDs nids = DBIDUtil.newHashSet(k + 10);
    for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
      nids.clear();
      nids.addDBIDs(knnQuery.getKNNForDBID(id, k + 1));
      nids.remove(id); // Do not use query object

      computeCentroid(centroid, relation, nids);
      PCAResult pcares = pca.processIds(nids, relation);
      double[][] tevecs = pcares.getEigenvectors();
      double[] evs = pcares.getEigenvalues();
      double[] projected = times(tevecs, minusEquals(relation.get(id).toArray(), centroid));

      if(dist == DistanceDist.CHISQUARED) {
        double sqdevs = 0;
        for(int d = 0; d < dim; d++) {
          double dev = projected[d];
          // Scale with variance and accumulate
          sqdevs += dev * dev / evs[d];
          scores[d] = 1 - ChiSquaredDistribution.cdf(sqdevs, d + 1);
        }
      }
      else {
        assert (dist == DistanceDist.GAMMA);
        double[][] dists = new double[dim][nids.size()];
        int j = 0;
        double[] srel = new double[dim];
        for(DBIDIter s = nids.iter(); s.valid() && j < nids.size(); s.advance(), j++) {
          V vec = relation.get(s);
          for(int d = 0; d < dim; d++) {
            srel[d] = vec.doubleValue(d) - centroid[d];
          }
          double sqdist = 0.0;
          for(int d = 0; d < dim; d++) {
            double serrd = transposeTimes(tevecs[d], srel);
            dists[d][j] = (sqdist += serrd * serrd / evs[d]);
          }
        }
        double sqdevs = 0;
        for(int d = 0; d < dim; d++) {
          // Scale with Stddev
          final double dev = projected[d];
          // Accumulate
          sqdevs += dev * dev / evs[d];
          // Sort, so we can trim the top 15% below.
          Arrays.sort(dists[d]);
          // Evaluate
          scores[d] = 1 - GammaChoiWetteEstimator.STATIC.estimate(dists[d], SHORTENED_ARRAY).cdf(sqdevs);
        }
      }
      // Find best score
      double min = Double.POSITIVE_INFINITY;
      int vdim = dim - 1;
      for(int d = 0; d < dim; d++) {
        double v = scores[d];
        if(v < min) {
          min = v;
          vdim = d;
        }
      }
      // Normalize the value
      final double prob = expect * (1 - min) / (expect + min);
      cop_score.putDouble(id, prob);
      if(models) {
        // Construct the error vector:
        Arrays.fill(projected, vdim + 1, dim, 0.);
        cop_err_v.put(id, timesEquals(transposeTimes(tevecs, projected), -prob));
        cop_dim.putInt(id, dim - vdim);
      }
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);

    // combine results.
    DoubleRelation scoreResult = new MaterializedDoubleRelation("Correlation Outlier Probabilities", COP_SCORES, cop_score, ids);
    OutlierScoreMeta scoreMeta = new ProbabilisticOutlierScore();
    OutlierResult result = new OutlierResult(scoreMeta, scoreResult);
    if(models) {
      result.addChildResult(new MaterializedRelation<>("Local Dimensionality", COP_DIM, TypeUtil.INTEGER, cop_dim, ids));
      result.addChildResult(new MaterializedRelation<>("Error vectors", COP_ERRORVEC, TypeUtil.DOUBLE_ARRAY, cop_err_v, ids));
    }
    return result;
  }
223286
public OutlierResult run(Relation<O> relation) {
    final int k1 = k + 1; // Query size
    final double perplexity = k / 3.;
    KNNQuery<O> knnq = relation.getKNNQuery(getDistanceFunction(), k1);
    final double logPerp = perplexity > 1. ? FastMath.log(perplexity) : .1;

    double[] p = new double[k + 10];
    ModifiableDoubleDBIDList dists = DBIDUtil.newDistanceDBIDList(k + 10);
    DoubleDBIDListIter di = dists.iter();
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("ISOS scores", relation.size(), LOG) : null;
    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_DB, 1.);
    for(DBIDIter it = relation.iterDBIDs(); it.valid(); it.advance()) {
      KNNList knns = knnq.getKNNForDBID(it, k1);
      if(p.length < knns.size() + 1) {
        p = new double[knns.size() + 10];
      }
      final DoubleDBIDListIter ki = knns.iter();
      try {
        double id = estimateID(it, ki, p);
        adjustDistances(it, ki, knns.getKNNDistance(), id, dists);
        // We now continue with the modified distances below.
        // Compute affinities
        SOS.computePi(it, di, p, perplexity, logPerp);
        // Normalization factor:
        double s = SOS.sumOfProbabilities(it, di, p);
        if(s > 0.) {
          nominateNeighbors(it, di, p, 1. / s, scores);
        }
      }
      catch(ArithmeticException e) {
        // ID estimation failed, supposedly constant values because of too many
        // duplicate points, or too small k. Fall back to KNNSOS.
        // Note: this looks almost identical to the above, but uses ki instead
        // of the adjusted distances di!
        // Compute affinities
        SOS.computePi(it, ki, p, perplexity, logPerp);
        // Normalization factor:
        double s = SOS.sumOfProbabilities(it, ki, p);
        if(s > 0.) {
          nominateNeighbors(it, ki, p, 1. / s, scores);
        }
      }
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);
    DoubleMinMax minmax = transformScores(scores, relation.getDBIDs(), logPerp, phi);
    DoubleRelation scoreres = new MaterializedDoubleRelation("Intrinsic Stoachastic Outlier Selection", "isos-outlier", scores, relation.getDBIDs());
    OutlierScoreMeta meta = new ProbabilisticOutlierScore(minmax.getMin(), minmax.getMax(), 0.);
    return new OutlierResult(meta, scoreres);
  }
774989
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);
  }
1145796
public OutlierResult run(Database database, Relation<NumberVector> relation) {
    final int dbdim = RelationUtil.dimensionality(relation);
    final int mindim = dbdim >> 1;
    final int maxdim = dbdim - 1;
    final Random rand = rnd.getSingleThreadedRandom();

    ArrayList<OutlierResult> results = new ArrayList<>(num);
    {
      FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("LOF iterations", num, LOG) : null;
      for(int i = 0; i < num; i++) {
        long[] dimset = randomSubspace(dbdim, mindim, maxdim, rand);
        SubspaceEuclideanDistanceFunction df = new SubspaceEuclideanDistanceFunction(dimset);
        LOF<NumberVector> lof = new LOF<>(k, df);

        // run LOF and collect the result
        OutlierResult result = lof.run(database, relation);
        results.add(result);
        LOG.incrementProcessed(prog);
      }
      LOG.ensureCompleted(prog);
    }

    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
    DoubleMinMax minmax = new DoubleMinMax();
    if(breadth) {
      FiniteProgress cprog = LOG.isVerbose() ? new FiniteProgress("Combining results", relation.size(), LOG) : null;
      @SuppressWarnings("unchecked")
      Pair<DBIDIter, DoubleRelation>[] IDVectorOntoScoreVector = (Pair<DBIDIter, DoubleRelation>[]) new Pair[results.size()];

      // Mapping score-sorted DBID-Iterators onto their corresponding scores.
      // We need to initialize them now be able to iterate them "in parallel".
      {
        int i = 0;
        for(OutlierResult r : results) {
          IDVectorOntoScoreVector[i] = new Pair<DBIDIter, DoubleRelation>(r.getOrdering().order(relation.getDBIDs()).iter(), r.getScores());
          i++;
        }
      }

      // Iterating over the *lines* of the AS_t(i)-matrix.
      for(int i = 0; i < relation.size(); i++) {
        // Iterating over the elements of a line (breadth-first).
        for(Pair<DBIDIter, DoubleRelation> pair : IDVectorOntoScoreVector) {
          DBIDIter iter = pair.first;
          // Always true if every algorithm returns a complete result (one score
          // for every DBID).
          if(iter.valid()) {
            double score = pair.second.doubleValue(iter);
            if(Double.isNaN(scores.doubleValue(iter))) {
              scores.putDouble(iter, score);
              minmax.put(score);
            }
            iter.advance();
          }
          else {
            LOG.warning("Incomplete result: Iterator does not contain |DB| DBIDs");
          }
        }
        // Progress does not take the initial mapping into account.
        LOG.incrementProcessed(cprog);
      }
      LOG.ensureCompleted(cprog);
    }
    else {
      FiniteProgress cprog = LOG.isVerbose() ? new FiniteProgress("Combining results", relation.size(), LOG) : null;
      for(DBIDIter iter = relation.iterDBIDs(); iter.valid(); iter.advance()) {
        double sum = 0.0;
        for(OutlierResult r : results) {
          final double s = r.getScores().doubleValue(iter);
          if(!Double.isNaN(s)) {
            sum += s;
          }
        }
        scores.putDouble(iter, sum);
        minmax.put(sum);
        LOG.incrementProcessed(cprog);
      }
      LOG.ensureCompleted(cprog);
    }
    OutlierScoreMeta meta = new BasicOutlierScoreMeta(minmax.getMin(), minmax.getMax());
    DoubleRelation scoreres = new MaterializedDoubleRelation("Feature bagging", "fb-outlier", scores, relation.getDBIDs());
    return new OutlierResult(meta, scoreres);
  }