Run the algorithm

@param database Database to process
@param relation Relation to process
@return Outlier result
18144
public OutlierResult run(Database database, Relation<O> relation) {
    DistanceQuery<O> distFunc = database.getDistanceQuery(relation, getDistanceFunction());
    KNNQuery<O> knnQuery = database.getKNNQuery(distFunc, k);

    // track the maximum value for normalization
    DoubleMinMax ldofminmax = new DoubleMinMax();
    // compute the ldof values
    WritableDoubleDataStore ldofs = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);

    // compute LOF_SCORE of each db object
    if(LOG.isVerbose()) {
      LOG.verbose("Computing LDOFs");
    }
    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 neighbors = knnQuery.getKNNForDBID(iditer, k);
      dxp.reset();
      Dxp.reset();
      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();
      if(Double.isNaN(ldof) || Double.isInfinite(ldof)) {
        ldof = 1.0;
      }
      ldofs.putDouble(iditer, ldof);
      // update maximum
      ldofminmax.put(ldof);

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

    // Build result representation.
    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);
  }
1162651
public Clustering<Model> run(Database database, Relation<O> relation) {
    StepProgress stepprog = LOG.isVerbose() ? new StepProgress("LSDBC", 3) : null;
    final int dim = RelationUtil.dimensionality(relation);
    final double factor = FastMath.pow(2., alpha / dim);

    final DBIDs ids = relation.getDBIDs();
    LOG.beginStep(stepprog, 1, "Materializing kNN neighborhoods");
    KNNQuery<O> knnq = DatabaseUtil.precomputedKNNQuery(database, relation, getDistanceFunction(), k);

    LOG.beginStep(stepprog, 2, "Sorting by density");
    WritableDoubleDataStore dens = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP);
    fillDensities(knnq, ids, dens);
    ArrayModifiableDBIDs sids = DBIDUtil.newArray(ids);
    sids.sort(new DataStoreUtil.AscendingByDoubleDataStore(dens));

    LOG.beginStep(stepprog, 3, "Computing clusters");
    // Setup progress logging
    final FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("LSDBC Clustering", ids.size(), LOG) : null;
    final IndefiniteProgress clusprogress = LOG.isVerbose() ? new IndefiniteProgress("Number of clusters found", LOG) : null;
    // (Temporary) store the cluster ID assigned.
    final WritableIntegerDataStore clusterids = DataStoreUtil.makeIntegerStorage(ids, DataStoreFactory.HINT_TEMP, UNPROCESSED);
    // Note: these are not exact, as objects may be stolen from noise.
    final IntArrayList clustersizes = new IntArrayList();
    clustersizes.add(0); // Unprocessed dummy value.
    clustersizes.add(0); // Noise counter.

    // Implementation Note: using Integer objects should result in
    // reduced memory use in the HashMap!
    int clusterid = NOISE + 1;
    // Iterate over all objects in the database.
    for(DBIDIter id = sids.iter(); id.valid(); id.advance()) {
      // Skip already processed ids.
      if(clusterids.intValue(id) != UNPROCESSED) {
        continue;
      }
      // Evaluate Neighborhood predicate
      final KNNList neighbors = knnq.getKNNForDBID(id, k);
      // Evaluate Core-Point predicate:
      if(isLocalMaximum(neighbors.getKNNDistance(), neighbors, dens)) {
        double mindens = factor * neighbors.getKNNDistance();
        clusterids.putInt(id, clusterid);
        clustersizes.add(expandCluster(clusterid, clusterids, knnq, neighbors, mindens, progress));
        // start next cluster on next iteration.
        ++clusterid;
        if(clusprogress != null) {
          clusprogress.setProcessed(clusterid, LOG);
        }
      }
      else {
        // otherwise, it's a noise point
        clusterids.putInt(id, NOISE);
        clustersizes.set(NOISE, clustersizes.getInt(NOISE) + 1);
      }
      // We've completed this element
      LOG.incrementProcessed(progress);
    }
    // Finish progress logging.
    LOG.ensureCompleted(progress);
    LOG.setCompleted(clusprogress);

    LOG.setCompleted(stepprog);

    // Transform cluster ID mapping into a clustering result:
    ArrayList<ArrayModifiableDBIDs> clusterlists = new ArrayList<>(clusterid);
    // add storage containers for clusters
    for(int i = 0; i < clustersizes.size(); i++) {
      clusterlists.add(DBIDUtil.newArray(clustersizes.getInt(i)));
    }
    // do the actual inversion
    for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
      // Negative values are non-core points:
      int cid = clusterids.intValue(id);
      int cluster = Math.abs(cid);
      clusterlists.get(cluster).add(id);
    }
    clusterids.destroy();

    Clustering<Model> result = new Clustering<>("LSDBC", "lsdbc-clustering");
    for(int cid = NOISE; cid < clusterlists.size(); cid++) {
      boolean isNoise = (cid == NOISE);
      Cluster<Model> c;
      c = new Cluster<Model>(clusterlists.get(cid), isNoise, ClusterModel.CLUSTER);
      result.addToplevelCluster(c);
    }
    return result;
  }
821778
public OutlierResult run(Database database, Relation<N> nrel, Relation<? extends NumberVector> relation) {
    final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(database, nrel);
    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);

    MeanVariance mv = new MeanVariance();
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      DBIDs neighbors = npred.getNeighborDBIDs(iditer);
      final double median;
      {
        double[] fi = new double[neighbors.size()];
        // calculate and store Median of neighborhood
        int c = 0;
        for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
          if(DBIDUtil.equal(iditer, iter)) {
            continue;
          }
          fi[c] = relation.get(iter).doubleValue(0);
          c++;
        }

        if(c > 0) {
          median = QuickSelect.median(fi, 0, c);
        }
        else {
          median = relation.get(iditer).doubleValue(0);
        }
      }
      double h = relation.get(iditer).doubleValue(0) - median;
      scores.putDouble(iditer, h);
      mv.put(h);
    }

    // Normalize scores
    final double mean = mv.getMean();
    final double stddev = mv.getNaiveStddev();
    DoubleMinMax minmax = new DoubleMinMax();
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      double score = Math.abs((scores.doubleValue(iditer) - mean) / stddev);
      minmax.put(score);
      scores.putDouble(iditer, score);
    }

    DoubleRelation scoreResult = new MaterializedDoubleRelation("MO", "Median-outlier", scores, relation.getDBIDs());
    OutlierScoreMeta scoreMeta = new BasicOutlierScoreMeta(minmax.getMin(), minmax.getMax(), 0.0, Double.POSITIVE_INFINITY, 0);
    OutlierResult or = new OutlierResult(scoreMeta, scoreResult);
    or.addChildResult(npred);
    return or;
  }
1194853
public Result 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();
    // 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:
    double[] height = new double[size];
    Arrays.fill(height, Double.POSITIVE_INFINITY);
    // Parent node, to track merges
    // have every object point to itself initially
    ArrayModifiableDBIDs parent = DBIDUtil.newArray(ids);
    // Active clusters, when not trivial.
    Int2ReferenceMap<ModifiableDBIDs> clusters = new Int2ReferenceOpenHashMap<>();

    // Repeat until everything merged, except the desired number of clusters:
    final int stop = size - numclusters;
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Agglomerative clustering", stop, LOG) : null;
    for(int i = 0; i < stop; i++) {
      double min = Double.POSITIVE_INFINITY;
      int minx = -1, miny = -1;
      for(int x = 0; x < size; x++) {
        if(height[x] < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int xbase = triangleSize(x);
        for(int y = 0; y < x; y++) {
          if(height[y] < Double.POSITIVE_INFINITY) {
            continue;
          }
          final int idx = xbase + y;
          if(scratch[idx] < min) {
            min = scratch[idx];
            minx = x;
            miny = y;
          }
        }
      }
      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.
      height[minx] = min;
      parent.set(minx, iy);
      // Merge into cluster
      ModifiableDBIDs cx = clusters.get(minx);
      ModifiableDBIDs cy = clusters.get(miny);
      int sizex = 1, sizey = 1; // cluster sizes, for averaging
      if(cy == null) {
        cy = DBIDUtil.newHashSet();
        cy.add(iy);
      }
      else {
        sizey = cy.size();
      }
      if(cx == null) {
        cy.add(ix);
      }
      else {
        sizex = cx.size();
        cy.addDBIDs(cx);
        clusters.remove(minx);
      }
      clusters.put(miny, cy);

      // Update distance matrix. Note: miny < minx

      // Implementation note: most will not need sizej, and could save the
      // hashmap lookup.
      final int xbase = triangleSize(minx), ybase = triangleSize(miny);
      // Write to (y, j), with j < y
      for(int j = 0; j < miny; j++) {
        if(height[j] < Double.POSITIVE_INFINITY) {
          continue;
        }
        final DBIDs idsj = clusters.get(j);
        final int sizej = (idsj == null) ? 1 : idsj.size();
        scratch[ybase + j] = linkage.combine(sizex, scratch[xbase + j], sizey, scratch[ybase + j], sizej, min);
      }
      // Write to (j, y), with y < j < x
      for(int j = miny + 1; j < minx; j++) {
        if(height[j] < Double.POSITIVE_INFINITY) {
          continue;
        }
        final int jbase = triangleSize(j);
        final DBIDs idsj = clusters.get(j);
        final int sizej = (idsj == null) ? 1 : idsj.size();
        scratch[jbase + miny] = linkage.combine(sizex, scratch[xbase + j], sizey, scratch[jbase + miny], sizej, min);
      }
      // Write to (j, y), with y < x < j
      for(int j = minx + 1; j < size; j++) {
        if(height[j] < Double.POSITIVE_INFINITY) {
          continue;
        }
        final DBIDs idsj = clusters.get(j);
        final int sizej = (idsj == null) ? 1 : idsj.size();
        final int jbase = triangleSize(j);
        scratch[jbase + miny] = linkage.combine(sizex, scratch[jbase + minx], sizey, scratch[jbase + miny], sizej, min);
      }
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);

    // Build the clustering result
    final Clustering<Model> dendrogram = new Clustering<>("Hierarchical-Clustering", "hierarchical-clustering");
    for(int x = 0; x < size; x++) {
      if(height[x] < Double.POSITIVE_INFINITY) {
        DBIDs cids = clusters.get(x);
        if(cids == null) {
          ix.seek(x);
          cids = DBIDUtil.deref(ix);
        }
        Cluster<Model> cluster = new Cluster<>("Cluster", cids);
        dendrogram.addToplevelCluster(cluster);
      }
    }

    return dendrogram;
  }
391754
public OutlierResult run(Database database, Relation<N> spatial, Relation<O> relation) {
    final NeighborSetPredicate npred = getNeighborSetPredicateFactory().instantiate(database, spatial);
    DistanceQuery<O> distFunc = getNonSpatialDistanceFunction().instantiate(relation);

    WritableDoubleDataStore lrds = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_TEMP | DataStoreFactory.HINT_HOT);
    WritableDoubleDataStore lofs = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
    DoubleMinMax lofminmax = new DoubleMinMax();

    // Compute densities
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      DBIDs neighbors = npred.getNeighborDBIDs(iditer);
      double avg = 0;
      for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
        avg += distFunc.distance(iditer, iter);
      }
      double lrd = 1 / (avg / neighbors.size());
      if(Double.isNaN(lrd)) {
        lrd = 0;
      }
      lrds.putDouble(iditer, lrd);
    }

    // Compute density quotients
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      DBIDs neighbors = npred.getNeighborDBIDs(iditer);
      double avg = 0;
      for(DBIDIter iter = neighbors.iter(); iter.valid(); iter.advance()) {
        avg += lrds.doubleValue(iter);
      }
      final double lrd = (avg / neighbors.size()) / lrds.doubleValue(iditer);
      if(!Double.isNaN(lrd)) {
        lofs.putDouble(iditer, lrd);
        lofminmax.put(lrd);
      }
      else {
        lofs.putDouble(iditer, 0.0);
      }
    }

    // Build result representation.
    DoubleRelation scoreResult = new MaterializedDoubleRelation("Spatial Outlier Factor", "sof-outlier", lofs, relation.getDBIDs());
    OutlierScoreMeta scoreMeta = new QuotientOutlierScoreMeta(lofminmax.getMin(), lofminmax.getMax(), 0.0, Double.POSITIVE_INFINITY, 1.0);
    OutlierResult or = new OutlierResult(scoreMeta, scoreResult);
    or.addChildResult(npred);
    return or;
  }
1005605
public ChangePoints run(Relation<DoubleVector> relation) {
    if(!(relation.getDBIDs() instanceof ArrayDBIDs)) {
      throw new AbortException("This implementation may only be used on static databases, with ArrayDBIDs to provide a clear order.");
    }
    return new Instance(rnd.getSingleThreadedRandom()).run(relation);
  }
417026
public OutlierResult run(Relation<P> spatial, Relation<? extends NumberVector> relation) {
    DistanceQuery<P> distFunc = getDistanceFunction().instantiate(spatial);
    WritableDataStore<double[]> similarityVectors = DataStoreUtil.makeStorage(spatial.getDBIDs(), DataStoreFactory.HINT_TEMP, double[].class);
    WritableDataStore<DBIDs> neighbors = DataStoreUtil.makeStorage(spatial.getDBIDs(), DataStoreFactory.HINT_TEMP, DBIDs.class);

    // Make a static IDs array for matrix column indexing
    ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());

    // construct the relation Matrix of the ec-graph
    double[][] E = new double[ids.size()][ids.size()];
    KNNHeap heap = DBIDUtil.newHeap(k);
    {
      int i = 0;
      for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) {
        final double val = relation.get(id).doubleValue(0);
        assert (heap.size() == 0);
        int j = 0;
        for(DBIDIter n = ids.iter(); n.valid(); n.advance(), j++) {
          if(i == j) {
            continue;
          }
          final double e;
          final double distance = distFunc.distance(id, n);
          heap.insert(distance, n);
          if(distance == 0) {
            LOG.warning("Zero distances are not supported - skipping: " + DBIDUtil.toString(id) + " " + DBIDUtil.toString(n));
            e = 0;
          }
          else {
            double diff = Math.abs(val - relation.get(n).doubleValue(0));
            double exp = FastMath.exp(FastMath.pow(diff, alpha));
            // Implementation note: not inverting exp worked a lot better.
            // Therefore we diverge from the article here.
            e = exp / distance;
          }
          E[j][i] = e;
        }
        // Convert kNN Heap into DBID array (unordered)
        ModifiableDBIDs nids = DBIDUtil.newArray(heap.size());
        for(DBIDIter it = heap.unorderedIterator(); it.valid(); it.advance()) {
          nids.add(it);
        }
        neighbors.put(id, nids);
      }
    }
    // normalize the adjacent Matrix
    // Sum based normalization - don't use E.normalizeColumns()
    // Which normalized to Euclidean length 1.0!
    // Also do the -c multiplication in this process.
    for(int i = 0; i < E[0].length; i++) {
      double sum = 0.0;
      for(int j = 0; j < E.length; j++) {
        sum += E[j][i];
      }
      if(sum == 0) {
        sum = 1.0;
      }
      for(int j = 0; j < E.length; j++) {
        E[j][i] = -c * E[j][i] / sum;
      }
    }
    // Add identity matrix. The diagonal should still be 0s, so this is trivial.
    assert (E.length == E[0].length);
    for(int col = 0; col < E[0].length; col++) {
      assert (E[col][col] == 0.0);
      E[col][col] = 1.0;
    }
    E = timesEquals(inverse(E), 1 - c);

    // Split the matrix into columns
    {
      int i = 0;
      for(DBIDIter id = ids.iter(); id.valid(); id.advance(), i++) {
        // Note: matrix times ith unit vector = ith column
        double[] sim = getCol(E, i);
        similarityVectors.put(id, sim);
      }
    }
    E = null;
    // compute the relevance scores between specified Object and its neighbors
    DoubleMinMax minmax = new DoubleMinMax();
    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(spatial.getDBIDs(), DataStoreFactory.HINT_STATIC);
    for(DBIDIter id = ids.iter(); id.valid(); id.advance()) {
      double gmean = 1.0;
      int cnt = 0;
      for(DBIDIter iter = neighbors.get(id).iter(); iter.valid(); iter.advance()) {
        if(DBIDUtil.equal(id, iter)) {
          continue;
        }
        double sim = angle(similarityVectors.get(id), similarityVectors.get(iter));
        gmean *= sim;
        cnt++;
      }
      final double score = FastMath.pow(gmean, 1.0 / cnt);
      minmax.put(score);
      scores.putDouble(id, score);
    }

    DoubleRelation scoreResult = new MaterializedDoubleRelation("randomwalkec", "RandomWalkEC", scores, relation.getDBIDs());
    OutlierScoreMeta scoreMeta = new BasicOutlierScoreMeta(minmax.getMin(), minmax.getMax(), 0.0, Double.POSITIVE_INFINITY, 0.0);
    return new OutlierResult(scoreMeta, scoreResult);
  }
802885
public Clustering<Model> run(Relation<V> relation) {
    final DBIDs ids = relation.getDBIDs();

    // Degenerate result:
    if(ids.size() < minpts) {
      Clustering<Model> result = new Clustering<>("DBSCAN Clustering", "dbscan-clustering");
      result.addToplevelCluster(new Cluster<Model>(ids, true, ClusterModel.CLUSTER));
      return result;
    }

    double gridwidth = this.gridwidth; // local copy.
    if(gridwidth < 2. * epsilon) {
      LOG.warning("Invalid grid width (less than 2*epsilon, recommended 10*epsilon). Increasing grid width automatically.");
      gridwidth = 2. * epsilon;
    }
    return new Instance<V>(getDistanceFunction(), epsilon, minpts, gridwidth).run(relation);
  }
351558
public RetrievalPerformanceResult run(Database database, Relation<O> relation, Relation<?> lrelation) {
    final DistanceQuery<O> distQuery = database.getDistanceQuery(relation, getDistanceFunction());
    final DBIDs ids = DBIDUtil.randomSample(relation.getDBIDs(), sampling, random);

    // For storing the positive neighbors.
    ModifiableDBIDs posn = DBIDUtil.newHashSet();
    // Distance storage.
    ModifiableDoubleDBIDList nlist = DBIDUtil.newDistanceDBIDList(relation.size());

    // For counting labels seen in kNN
    Object2IntOpenHashMap<Object> counters = new Object2IntOpenHashMap<>();

    // Statistics tracking
    double map = 0., mroc = 0.;
    double[] knnperf = new double[maxk];
    int samples = 0;

    FiniteProgress objloop = LOG.isVerbose() ? new FiniteProgress("Processing query objects", ids.size(), LOG) : null;
    for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
      Object label = lrelation.get(iter);
      findMatches(posn, lrelation, label);
      if(posn.size() > 0) {
        computeDistances(nlist, iter, distQuery, relation);
        if(nlist.size() != relation.size() - (includeSelf ? 0 : 1)) {
          LOG.warning("Neighbor list does not have the desired size: " + nlist.size());
        }
        map += AveragePrecisionEvaluation.STATIC.evaluate(posn, nlist);
        mroc += ROCEvaluation.STATIC.evaluate(posn, nlist);
        KNNEvaluator.STATIC.evaluateKNN(knnperf, nlist, lrelation, counters, label);
        samples += 1;
      }
      LOG.incrementProcessed(objloop);
    }
    LOG.ensureCompleted(objloop);
    if(samples < 1) {
      throw new AbortException("No object matched - are labels parsed correctly?");
    }
    if(!(map >= 0) || !(mroc >= 0)) {
      throw new AbortException("NaN in MAP/ROC.");
    }

    map /= samples;
    mroc /= samples;
    LOG.statistics(new DoubleStatistic(PREFIX + ".map", map));
    LOG.statistics(new DoubleStatistic(PREFIX + ".rocauc", mroc));
    LOG.statistics(new DoubleStatistic(PREFIX + ".samples", samples));
    for(int k = 0; k < maxk; k++) {
      knnperf[k] = knnperf[k] / samples;
      LOG.statistics(new DoubleStatistic(PREFIX + ".knn-" + (k + 1), knnperf[k]));
    }

    return new RetrievalPerformanceResult(samples, map, mroc, knnperf);
  }
380944
public OutlierResult run(Relation<V> relation) {
    final int dim = RelationUtil.dimensionality(relation);
    final ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());

    svm.svm_set_print_string_function(LOG_HELPER);

    svm_parameter param = new svm_parameter();
    param.svm_type = svm_parameter.ONE_CLASS;
    param.kernel_type = svm_parameter.LINEAR;
    param.degree = 3;
    switch(kernel){
    case LINEAR:
      param.kernel_type = svm_parameter.LINEAR;
      break;
    case QUADRATIC:
      param.kernel_type = svm_parameter.POLY;
      param.degree = 2;
      break;
    case CUBIC:
      param.kernel_type = svm_parameter.POLY;
      param.degree = 3;
      break;
    case RBF:
      param.kernel_type = svm_parameter.RBF;
      break;
    case SIGMOID:
      param.kernel_type = svm_parameter.SIGMOID;
      break;
    default:
      throw new AbortException("Invalid kernel parameter: " + kernel);
    }
    // TODO: expose additional parameters to the end user!
    param.nu = nu;
    param.coef0 = 0.;
    param.cache_size = 10000;
    param.C = 1;
    param.eps = 1e-4; // not used by one-class?
    param.p = 0.1; // not used by one-class?
    param.shrinking = 0;
    param.probability = 0;
    param.nr_weight = 0;
    param.weight_label = new int[0];
    param.weight = new double[0];
    param.gamma = 1. / dim;

    // Transform data:
    svm_problem prob = new svm_problem();
    prob.l = relation.size();
    prob.x = new svm_node[prob.l][];
    prob.y = new double[prob.l];
    {
      DBIDIter iter = ids.iter();
      for(int i = 0; i < prob.l && iter.valid(); iter.advance(), i++) {
        V vec = relation.get(iter);
        // TODO: support compact sparse vectors, too!
        svm_node[] x = new svm_node[dim];
        for(int d = 0; d < dim; d++) {
          x[d] = new svm_node();
          x[d].index = d + 1;
          x[d].value = vec.doubleValue(d);
        }
        prob.x[i] = x;
        prob.y[i] = +1;
      }
    }

    if(LOG.isVerbose()) {
      LOG.verbose("Training one-class SVM...");
    }
    String err = svm.svm_check_parameter(prob, param);
    if(err != null) {
      LOG.warning("svm_check_parameter: " + err);
    }
    svm_model model = svm.svm_train(prob, param);

    if(LOG.isVerbose()) {
      LOG.verbose("Predicting...");
    }
    WritableDoubleDataStore scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_DB);
    DoubleMinMax mm = new DoubleMinMax();
    {
      DBIDIter iter = ids.iter();
      double[] buf = new double[svm.svm_get_nr_class(model)];
      for(int i = 0; i < prob.l && iter.valid(); iter.advance(), i++) {
        V vec = relation.get(iter);
        svm_node[] x = new svm_node[dim];
        for(int d = 0; d < dim; d++) {
          x[d] = new svm_node();
          x[d].index = d + 1;
          x[d].value = vec.doubleValue(d);
        }
        svm.svm_predict_values(model, x, buf);
        double score = -buf[0]; // / param.gamma; // Heuristic rescaling, sorry.
        // Unfortunately, libsvm one-class currently yields a binary decision.
        scores.putDouble(iter, score);
        mm.put(score);
      }
    }
    DoubleRelation scoreResult = new MaterializedDoubleRelation("One-Class SVM Decision", "svm-outlier", scores, ids);
    OutlierScoreMeta scoreMeta = new BasicOutlierScoreMeta(mm.getMin(), mm.getMax(), Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, 0.);
    return new OutlierResult(scoreMeta, scoreResult);
  }
1133577
public PointerHierarchyRepresentationResult run(Database database, Relation<O> relation) {
    DBIDs ids = relation.getDBIDs();
    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);

    final Logging log = getLogger(); // To allow CLINK logger override

    FiniteProgress progress = log.isVerbose() ? new FiniteProgress("Running SLINK", ids.size(), log) : null;
    ArrayDBIDs aids = DBIDUtil.ensureArray(ids);

    // First element is trivial/special:
    DBIDArrayIter id = aids.iter(), it = aids.iter();
    // Step 1: initialize
    for(; id.valid(); id.advance()) {
      // P(n+1) = n+1:
      pi.put(id, id);
      // L(n+1) = infinity already.
    }
    // First element is finished already (start at seek(1) below!)
    log.incrementProcessed(progress);

    // Optimized branch
    if(getDistanceFunction() instanceof PrimitiveDistanceFunction) {
      PrimitiveDistanceFunction<? super O> distf = (PrimitiveDistanceFunction<? super O>) getDistanceFunction();
      for(id.seek(1); id.valid(); id.advance()) {
        step2primitive(id, it, id.getOffset(), relation, distf, m);
        process(id, aids, it, id.getOffset(), pi, lambda, m); // SLINK or CLINK
        log.incrementProcessed(progress);
      }
    }
    else {
      // Fallback branch
      DistanceQuery<O> distQ = database.getDistanceQuery(relation, getDistanceFunction());
      for(id.seek(1); id.valid(); id.advance()) {
        step2(id, it, id.getOffset(), distQ, m);
        process(id, aids, it, id.getOffset(), pi, lambda, m); // SLINK or CLINK
        log.incrementProcessed(progress);
      }
    }

    log.ensureCompleted(progress);
    // We don't need m anymore.
    m.destroy();
    m = null;

    return new PointerHierarchyRepresentationResult(ids, pi, lambda, getDistanceFunction().isSquared());
  }
174538
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());

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

    final int numedges = ids.size() - 1;
    DoubleLongHeap heap = new DoubleLongMinHeap(numedges);
    // 2. Build spanning tree.
    FiniteProgress mprog = LOG.isVerbose() ? new FiniteProgress("Computing minimum spanning tree (n-1 edges)", numedges, LOG) : null;
    PrimsMinimumSpanningTree.processDense(ids, //
        new HDBSCANAdapter(ids, coredists, distQ), //
        new HeapMSTCollector(heap, mprog, LOG));
    LOG.ensureCompleted(mprog);
    // Storage for pointer representation:
    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);
    convertToPointerRepresentation(ids, heap, pi, lambda);

    return new PointerDensityHierarchyRepresentationResult(ids, pi, lambda, distQ.getDistanceFunction().isSquared(), coredists);
  }
341053
public Clustering<MedoidModel> run(Database db, Relation<O> relation) {
    ArrayDBIDs ids = DBIDUtil.ensureArray(relation.getDBIDs());
    final int size = ids.size();

    int[] assignment = new int[size];
    double[][] s = initialization.getSimilarityMatrix(db, relation, ids);
    double[][] r = new double[size][size];
    double[][] a = new double[size][size];

    IndefiniteProgress prog = LOG.isVerbose() ? new IndefiniteProgress("Affinity Propagation Iteration", LOG) : null;
    MutableProgress aprog = LOG.isVerbose() ? new MutableProgress("Stable assignments", size + 1, LOG) : null;

    int inactive = 0;
    for(int iteration = 0; iteration < maxiter && inactive < convergence; iteration++) {
      // Update responsibility matrix:
      for(int i = 0; i < size; i++) {
        double[] ai = a[i], ri = r[i], si = s[i];
        // Find the two largest values (as initially maxk == i)
        double max1 = Double.NEGATIVE_INFINITY, max2 = Double.NEGATIVE_INFINITY;
        int maxk = -1;
        for(int k = 0; k < size; k++) {
          double val = ai[k] + si[k];
          if(val > max1) {
            max2 = max1;
            max1 = val;
            maxk = k;
          }
          else if(val > max2) {
            max2 = val;
          }
        }
        // With the maximum value known, update r:
        for(int k = 0; k < size; k++) {
          double val = si[k] - ((k != maxk) ? max1 : max2);
          ri[k] = ri[k] * lambda + val * (1. - lambda);
        }
      }
      // Update availability matrix
      for(int k = 0; k < size; k++) {
        // Compute sum of max(0, r_ik) for all i.
        // For r_kk, don't apply the max.
        double colposum = 0.;
        for(int i = 0; i < size; i++) {
          if(i == k || r[i][k] > 0.) {
            colposum += r[i][k];
          }
        }
        for(int i = 0; i < size; i++) {
          double val = colposum;
          // Adjust column sum by the one extra term.
          if(i == k || r[i][k] > 0.) {
            val -= r[i][k];
          }
          if(i != k && val > 0.) { // min
            val = 0.;
          }
          a[i][k] = a[i][k] * lambda + val * (1 - lambda);
        }
      }
      int changed = 0;
      for(int i = 0; i < size; i++) {
        double[] ai = a[i], ri = r[i];
        double max = Double.NEGATIVE_INFINITY;
        int maxj = -1;
        for(int j = 0; j < size; j++) {
          double v = ai[j] + ri[j];
          if(v > max || (i == j && v >= max)) {
            max = v;
            maxj = j;
          }
        }
        if(assignment[i] != maxj) {
          changed += 1;
          assignment[i] = maxj;
        }
      }
      inactive = (changed > 0) ? 0 : (inactive + 1);
      LOG.incrementProcessed(prog);
      if(aprog != null) {
        aprog.setProcessed(size - changed, LOG);
      }
    }
    if(aprog != null) {
      aprog.setProcessed(aprog.getTotal(), LOG);
    }
    LOG.setCompleted(prog);
    // Cluster map, by lead object
    Int2ObjectOpenHashMap<ModifiableDBIDs> map = new Int2ObjectOpenHashMap<>();
    DBIDArrayIter i1 = ids.iter();
    for(int i = 0; i1.valid(); i1.advance(), i++) {
      int c = assignment[i];
      // Add to cluster members:
      ModifiableDBIDs cids = map.get(c);
      if(cids == null) {
        cids = DBIDUtil.newArray();
        map.put(c, cids);
      }
      cids.add(i1);
    }
    // If we stopped early, the cluster lead might be in a different cluster.
    for(ObjectIterator<Int2ObjectOpenHashMap.Entry<ModifiableDBIDs>> iter = map.int2ObjectEntrySet().fastIterator(); iter.hasNext();) {
      Int2ObjectOpenHashMap.Entry<ModifiableDBIDs> entry = iter.next();
      final int key = entry.getIntKey();
      int targetkey = key;
      ModifiableDBIDs tids = null;
      // Chase arrows:
      while(tids == null && assignment[targetkey] != targetkey) {
        targetkey = assignment[targetkey];
        tids = map.get(targetkey);
      }
      if(tids != null && targetkey != key) {
        tids.addDBIDs(entry.getValue());
        iter.remove();
      }
    }

    Clustering<MedoidModel> clustering = new Clustering<>("Affinity Propagation Clustering", "ap-clustering");
    ModifiableDBIDs noise = DBIDUtil.newArray();
    for(ObjectIterator<Int2ObjectOpenHashMap.Entry<ModifiableDBIDs>> iter = map.int2ObjectEntrySet().fastIterator(); iter.hasNext();) {
      Int2ObjectOpenHashMap.Entry<ModifiableDBIDs> entry = iter.next();
      i1.seek(entry.getIntKey());
      if(entry.getValue().size() > 1) {
        MedoidModel mod = new MedoidModel(DBIDUtil.deref(i1));
        clustering.addToplevelCluster(new Cluster<>(entry.getValue(), mod));
      }
      else {
        noise.add(i1);
      }
    }
    if(noise.size() > 0) {
      MedoidModel mod = new MedoidModel(DBIDUtil.deref(noise.iter()));
      clustering.addToplevelCluster(new Cluster<>(noise, true, mod));
    }
    return clustering;
  }
337466
public Clustering<Model> run(Database database, Relation<V> relation) {
    // current dimensionality associated with each seed
    int dim_c = RelationUtil.dimensionality(relation);

    if(dim_c < l) {
      throw new IllegalStateException("Dimensionality of data < parameter l! " + "(" + dim_c + " < " + l + ")");
    }

    // current number of seeds
    int k_c = Math.min(relation.size(), k_i * k);

    // pick k0 > k points from the database
    List<ORCLUSCluster> clusters = initialSeeds(relation, k_c);

    double beta = FastMath.exp(-FastMath.log(dim_c / (double) l) * FastMath.log(1 / alpha) / FastMath.log(k_c / (double) k));

    IndefiniteProgress cprogress = LOG.isVerbose() ? new IndefiniteProgress("Current number of clusters:", LOG) : null;

    while(k_c > k) {
      // find partitioning induced by the seeds of the clusters
      assign(relation, clusters);

      // determine current subspace associated with each cluster
      for(ORCLUSCluster cluster : clusters) {
        if(cluster.objectIDs.size() > 0) {
          cluster.basis = findBasis(relation, cluster, dim_c);
        }
      }

      // reduce number of seeds and dimensionality associated with
      // each seed
      k_c = (int) Math.max(k, k_c * alpha);
      dim_c = (int) Math.max(l, dim_c * beta);
      merge(relation, clusters, k_c, dim_c, cprogress);
      if(cprogress != null) {
        cprogress.setProcessed(clusters.size(), LOG);
      }
    }
    assign(relation, clusters);

    LOG.setCompleted(cprogress);

    // get the result
    Clustering<Model> r = new Clustering<>("ORCLUS clustering", "orclus-clustering");
    for(ORCLUSCluster c : clusters) {
      r.addToplevelCluster(new Cluster<Model>(c.objectIDs, ClusterModel.CLUSTER));
    }
    return r;
  }
1314986
public Clustering<ClusterModel> run(Relation<V> relation) {
    ArrayModifiableDBIDs ids = DBIDUtil.newArray(relation.getDBIDs());
    final int size = ids.size();

    // Sort by the sole dimension
    ids.sort(new VectorUtil.SortDBIDsBySingleDimension(relation, dim));

    // Density storage.
    WritableDoubleDataStore density = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP, 0.);

    DBIDArrayIter iter = ids.iter(), iter2 = ids.iter();

    StepProgress sprog = LOG.isVerbose() ? new StepProgress("Clustering steps", 2) : null;

    LOG.beginStep(sprog, 1, "Kernel density estimation.");
    {
      double[] scratch = new double[2 * k];
      iter.seek(0);
      for(int i = 0; i < size; i++, iter.advance()) {
        // Current value.
        final double curv = relation.get(iter).doubleValue(dim);

        final int pre = Math.max(i - k, 0), prek = i - pre;
        final int pos = Math.min(i + k, size - 1), posk = pos - i;
        iter2.seek(pre);
        for(int j = 0; j < prek; j++, iter2.advance()) {
          scratch[j] = curv - relation.get(iter2).doubleValue(dim);
        }
        assert (iter2.getOffset() == i);
        iter2.advance();
        for(int j = 0; j < posk; j++, iter2.advance()) {
          scratch[prek + j] = relation.get(iter2).doubleValue(dim) - curv;
        }

        assert (prek + posk >= k);
        double kdist = QuickSelect.quickSelect(scratch, 0, prek + posk, k);
        switch(mode){
        case BALLOON: {
          double dens = 0.;
          if(kdist > 0.) {
            for(int j = 0; j < prek + posk; j++) {
              dens += kernel.density(scratch[j] / kdist);
            }
          }
          else {
            dens = Double.POSITIVE_INFINITY;
          }
          assert (iter.getOffset() == i);
          density.putDouble(iter, dens);
          break;
        }
        case SAMPLE: {
          if(kdist > 0.) {
            iter2.seek(pre);
            for(int j = 0; j < prek; j++, iter2.advance()) {
              double delta = curv - relation.get(iter2).doubleValue(dim);
              density.putDouble(iter2, density.doubleValue(iter2) + kernel.density(delta / kdist));
            }
            assert (iter2.getOffset() == i);
            iter2.advance();
            for(int j = 0; j < posk; j++, iter2.advance()) {
              double delta = relation.get(iter2).doubleValue(dim) - curv;
              density.putDouble(iter2, density.doubleValue(iter2) + kernel.density(delta / kdist));
            }
          }
          else {
            iter2.seek(pre);
            for(int j = 0; j < prek; j++, iter2.advance()) {
              double delta = curv - relation.get(iter2).doubleValue(dim);
              if(!(delta > 0.)) {
                density.putDouble(iter2, Double.POSITIVE_INFINITY);
              }
            }
            assert (iter2.getOffset() == i);
            iter2.advance();
            for(int j = 0; j < posk; j++, iter2.advance()) {
              double delta = relation.get(iter2).doubleValue(dim) - curv;
              if(!(delta > 0.)) {
                density.putDouble(iter2, Double.POSITIVE_INFINITY);
              }
            }
          }
          break;
        }
        default:
          throw new UnsupportedOperationException("Unknown mode specified.");
        }
      }
    }

    LOG.beginStep(sprog, 2, "Local minima detection.");
    Clustering<ClusterModel> clustering = new Clustering<>("onedimensional-kde-clustering", "One-Dimensional clustering using kernel density estimation.");
    {
      double[] scratch = new double[2 * minwindow + 1];
      int begin = 0;
      int halfw = (minwindow + 1) >> 1;
      iter.seek(0);
      // Fill initial buffer.
      for(int i = 0; i < size; i++, iter.advance()) {
        final int m = i % scratch.length, t = (i - minwindow - 1) % scratch.length;
        scratch[m] = density.doubleValue(iter);
        if(i > scratch.length) {
          double min = Double.POSITIVE_INFINITY;
          for(int j = 0; j < scratch.length; j++) {
            if(j != t && scratch[j] < min) {
              min = scratch[j];
            }
          }
          // Local minimum:
          if(scratch[t] < min) {
            int end = i - minwindow + 1;
            { // Test on which side the kNN is
              iter2.seek(end);
              double curv = relation.get(iter2).doubleValue(dim);
              iter2.seek(end - halfw);
              double left = relation.get(iter2).doubleValue(dim) - curv;
              iter2.seek(end + halfw);
              double right = curv - relation.get(iter2).doubleValue(dim);
              if(left < right) {
                end++;
              }
            }
            iter2.seek(begin);
            ArrayModifiableDBIDs cids = DBIDUtil.newArray(end - begin);
            for(int j = 0; j < end - begin; j++, iter2.advance()) {
              cids.add(iter2);
            }
            clustering.addToplevelCluster(new Cluster<>(cids, ClusterModel.CLUSTER));
            begin = end;
          }
        }
      }
      // Extract last cluster
      int end = size;
      iter2.seek(begin);
      ArrayModifiableDBIDs cids = DBIDUtil.newArray(end - begin);
      for(int j = 0; j < end - begin; j++, iter2.advance()) {
        cids.add(iter2);
      }
      clustering.addToplevelCluster(new Cluster<>(cids, ClusterModel.CLUSTER));
    }

    LOG.ensureCompleted(sprog);
    return clustering;
  }
1078333
public Result run(Database database, Relation<NumberVector> relation) {
    final int dim = RelationUtil.dimensionality(relation);
    final DistanceQuery<NumberVector> distanceQuery = database.getDistanceQuery(relation, getDistanceFunction());
    final KNNQuery<NumberVector> knnQuery = database.getKNNQuery(distanceQuery, k + 1);

    final double[] min = new double[dim], extend = new double[dim];
    initializeDataExtends(relation, dim, min, extend);

    if(!LOG.isStatistics()) {
      LOG.warning("This algorithm must be used with at least logging level " + Level.STATISTICS);
    }

    MeanVariance hmean = new MeanVariance(), umean = new MeanVariance(),
        wmean = new MeanVariance();
    // compute the hopkins value several times and use the average value for a
    // more stable result
    for(int j = 0; j < this.rep; j++) {
      // Compute NN distances for random objects from within the database
      double w = computeNNForRealData(knnQuery, relation, dim);
      // Compute NN distances for randomly created new uniform objects
      double u = computeNNForUniformData(knnQuery, min, extend);
      // compute hopkins statistik
      double h = u / (u + w); // = a / (1+a)
      hmean.put(h);
      umean.put(u);
      wmean.put(w);
    }
    final String prefix = this.getClass().getName();
    LOG.statistics(new LongStatistic(prefix + ".samplesize", sampleSize));
    LOG.statistics(new LongStatistic(prefix + ".dim", dim));
    LOG.statistics(new LongStatistic(prefix + ".hopkins.nearest-neighbor", k));
    LOG.statistics(new DoubleStatistic(prefix + ".hopkins.h.mean", hmean.getMean()));
    LOG.statistics(new DoubleStatistic(prefix + ".hopkins.u.mean", umean.getMean()));
    LOG.statistics(new DoubleStatistic(prefix + ".hopkins.w.mean", wmean.getMean()));
    if(rep > 1) {
      LOG.statistics(new DoubleStatistic(prefix + ".hopkins.h.std", hmean.getSampleStddev()));
      LOG.statistics(new DoubleStatistic(prefix + ".hopkins.u.std", umean.getSampleStddev()));
      LOG.statistics(new DoubleStatistic(prefix + ".hopkins.w.std", wmean.getSampleStddev()));
    }
    // Evaluate:
    double x = hmean.getMean();
    // See Hopkins for a proof that x is supposedly Beta distributed.
    double ix = BetaDistribution.regularizedIncBeta(x, sampleSize, sampleSize);
    double p = (x > .5) ? (1. - ix) : ix;
    LOG.statistics(new DoubleStatistic(prefix + ".hopkins.p", p));
    return null;
  }
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;
  }