Estimate minimum and maximum via sampling.

@param relation Relation to process
@param distFunc Distance function to use
@return Minimum and maximum
332510
private DoubleMinMax sampleMinMax(Relation<O> relation, DistanceQuery<O> distFunc) {
    int size = relation.size();
    Random rnd = new Random();
    // estimate minimum and maximum.
    int k = (int) Math.max(25, FastMath.pow(relation.size(), 0.2));
    TreeSet<DoubleDBIDPair> minhotset = new TreeSet<>();
    TreeSet<DoubleDBIDPair> maxhotset = new TreeSet<>(Collections.reverseOrder());

    int randomsize = (int) Math.max(25, FastMath.pow(relation.size(), 0.2));
    double rprob = ((double) randomsize) / size;
    ArrayModifiableDBIDs randomset = DBIDUtil.newArray(randomsize);

    DBIDIter iter = relation.iterDBIDs();
    if(!iter.valid()) {
      throw new EmptyDataException();
    }
    DBID firstid = DBIDUtil.deref(iter);
    iter.advance();
    minhotset.add(DBIDUtil.newPair(Double.MAX_VALUE, firstid));
    maxhotset.add(DBIDUtil.newPair(Double.MIN_VALUE, firstid));
    for(; iter.valid(); iter.advance()) {
      // generate candidates for min distance.
      ArrayList<DoubleDBIDPair> np = new ArrayList<>(k * 2 + randomsize * 2);
      for(DoubleDBIDPair pair : minhotset) {
        // skip the object itself
        if(DBIDUtil.equal(iter, pair)) {
          continue;
        }
        double d = distFunc.distance(iter, pair);
        np.add(DBIDUtil.newPair(d, iter));
        np.add(DBIDUtil.newPair(d, pair));
      }
      for(DBIDIter iter2 = randomset.iter(); iter2.valid(); iter2.advance()) {
        double d = distFunc.distance(iter, iter2);
        np.add(DBIDUtil.newPair(d, iter));
        np.add(DBIDUtil.newPair(d, iter2));
      }
      minhotset.addAll(np);
      shrinkHeap(minhotset, k);

      // generate candidates for max distance.
      ArrayList<DoubleDBIDPair> np2 = new ArrayList<>(k * 2 + randomsize * 2);
      for(DoubleDBIDPair pair : minhotset) {
        // skip the object itself
        if(DBIDUtil.equal(iter, pair)) {
          continue;
        }
        double d = distFunc.distance(iter, pair);
        np2.add(DBIDUtil.newPair(d, iter));
        np2.add(DBIDUtil.newPair(d, pair));
      }
      for(DBIDIter iter2 = randomset.iter(); iter2.valid(); iter2.advance()) {
        double d = distFunc.distance(iter, iter2);
        np.add(DBIDUtil.newPair(d, iter));
        np.add(DBIDUtil.newPair(d, iter2));
      }
      maxhotset.addAll(np2);
      shrinkHeap(maxhotset, k);

      // update random set
      if(randomset.size() < randomsize) {
        randomset.add(iter);
      }
      else if(rnd.nextDouble() < rprob) {
        randomset.set((int) Math.floor(rnd.nextDouble() * randomsize), iter);
      }
    }
    return new DoubleMinMax(minhotset.first().doubleValue(), maxhotset.first().doubleValue());
  }
431402
def dist(self):
        
        if self.func is None:
            return random.uniform(self.min, self.max)
        if self._dist is None:
            x = numpy.arange(self.min, self.max, (self.max-self.min)/1000.0)
            p = self.func(x).cumsum()
            p -= p.min()
            p /= p.max()
            self._dist = interpolate.interp1d(p, x)
        return self._dist(random.random())
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;
  }
1196084
private int getClusterBoundary(Relation<O> relation, List<? extends Cluster<MeanModel>> clusters) {
    int totalSize = relation.size();
    int clusterBoundary = clusters.size() - 1;
    int cumulativeSize = 0;
    for(int i = 0; i < clusters.size() - 1; i++) {
      cumulativeSize += clusters.get(i).size();

      // Given majority covered by large cluster
      if(cumulativeSize >= totalSize * alpha) {
        clusterBoundary = i;
        break;
      }

      // Relative difference in cluster size between two consecutive clusters
      if(clusters.get(i).size() / (double) clusters.get(i + 1).size() >= beta) {
        clusterBoundary = i;
        break;
      }
    }
    return clusterBoundary;
  }
22412
public static double[][] computeMinMax(Relation<? extends NumberVector> relation) {
    int dim = RelationUtil.dimensionality(relation);
    double[] mins = new double[dim], maxs = new double[dim];
    for(int i = 0; i < dim; i++) {
      mins[i] = Double.MAX_VALUE;
      maxs[i] = -Double.MAX_VALUE;
    }
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      final NumberVector o = relation.get(iditer);
      for(int d = 0; d < dim; d++) {
        final double v = o.doubleValue(d);
        mins[d] = (v < mins[d]) ? v : mins[d];
        maxs[d] = (v > maxs[d]) ? v : maxs[d];
      }
    }
    return new double[][] { mins, maxs };
  }
343128
private void linearScan(Relation<? extends O> relation, DBIDIter iter, O obj, double range, ModifiableDoubleDBIDList result) {
    final PrimitiveDistanceFunction<? super O> rawdist = this.rawdist;
    while(iter.valid()) {
      final double distance = rawdist.distance(obj, relation.get(iter));
      if(distance <= range) {
        result.add(distance, iter);
      }
      iter.advance();
    }
  }
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);
  }
14725
private Pair<KNNQuery<O>, KNNQuery<O>> getKNNQueries(Database database, Relation<O> relation, StepProgress stepprog) {
    DistanceQuery<O> distQ = database.getDistanceQuery(relation, reachabilityDistanceFunction, DatabaseQuery.HINT_HEAVY_USE);
    // "HEAVY" flag for knnReach since it is used more than once
    KNNQuery<O> knnReach = database.getKNNQuery(distQ, kreach, DatabaseQuery.HINT_HEAVY_USE, DatabaseQuery.HINT_OPTIMIZED_ONLY, DatabaseQuery.HINT_NO_CACHE);
    // No optimized kNN query - use a preprocessor!
    if(!(knnReach instanceof PreprocessorKNNQuery)) {
      if(stepprog != null) {
        if(referenceDistanceFunction.equals(reachabilityDistanceFunction)) {
          stepprog.beginStep(1, "Materializing neighborhoods w.r.t. reference neighborhood distance function.", LOG);
        }
        else {
          stepprog.beginStep(1, "Not materializing neighborhoods w.r.t. reference neighborhood distance function, but materializing neighborhoods w.r.t. reachability distance function.", LOG);
        }
      }
      int kpreproc = (referenceDistanceFunction.equals(reachabilityDistanceFunction)) ? Math.max(kreach, krefer) : kreach;
      knnReach = DatabaseUtil.precomputedKNNQuery(database, relation, reachabilityDistanceFunction, kpreproc);
    }

    // knnReach is only used once
    KNNQuery<O> knnRefer;
    if(referenceDistanceFunction == reachabilityDistanceFunction || referenceDistanceFunction.equals(reachabilityDistanceFunction)) {
      knnRefer = knnReach;
    }
    else {
      // do not materialize the first neighborhood, since it is used only once
      knnRefer = QueryUtil.getKNNQuery(relation, referenceDistanceFunction, krefer);
    }

    return new Pair<>(knnRefer, knnReach);
  }
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);
  }
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;
  }
72663
public OutlierResult run(Database database, Relation<O> relation) {
    final DistanceQuery<O> distanceQuery = database.getDistanceQuery(relation, getDistanceFunction());
    KNNQuery<O> knnQuery = database.getKNNQuery(distanceQuery, k + 1); // +
                                                                       // query
                                                                       // point

    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Compute Local Isolation Coefficients", relation.size(), LOG) : null;

    DoubleMinMax minmax = new DoubleMinMax();
    WritableDoubleDataStore lic_score = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      final KNNList knn = knnQuery.getKNNForDBID(iditer, k + 1); // + query
                                                                 // point
      double skn = 0; // sum of the distances to the k nearest neighbors
      int i = 0; // number of neighbors so far
      for(DoubleDBIDListIter neighbor = knn.iter(); i < k && neighbor.valid(); neighbor.advance()) {
        if(DBIDUtil.equal(iditer, neighbor)) {
          continue;
        }
        skn += neighbor.doubleValue();
        ++i;
      }
      double lic = knn.getKNNDistance() + (i > 0 ? skn / i : 0);
      lic_score.putDouble(iditer, lic);
      minmax.put(skn);

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

    DoubleRelation res = new MaterializedDoubleRelation("Local Isolation Coefficient", "lic-outlier", lic_score, relation.getDBIDs());
    OutlierScoreMeta meta = new BasicOutlierScoreMeta(minmax.getMin(), minmax.getMax(), 0., Double.POSITIVE_INFINITY, 0.);
    return new OutlierResult(meta, res);
  }
159196
@Override
  public OutlierResult run(Database db, Relation<V> relation) {
    DBIDs ids = relation.getDBIDs();
    WritableDoubleDataStore abodvalues = DataStoreUtil.makeDoubleStorage(ids, DataStoreFactory.HINT_STATIC);
    DoubleMinMax minmaxabod = new DoubleMinMax();
    if(kernelFunction.getClass() == LinearKernelFunction.class) {
      if(!kNNABOD(db, relation, ids, abodvalues, minmaxabod)) {
        // Fallback, if we do not have an index.
        fastABOD(db, relation, ids, abodvalues, minmaxabod);
      }
    }
    else {
      fastABOD(db, relation, ids, abodvalues, minmaxabod);
    }

    // Build result representation.
    DoubleRelation scoreResult = new MaterializedDoubleRelation("Angle-Based Outlier Degree", "abod-outlier", abodvalues, relation.getDBIDs());
    OutlierScoreMeta scoreMeta = new InvertedOutlierScoreMeta(minmaxabod.getMin(), minmaxabod.getMax(), 0.0, Double.POSITIVE_INFINITY);
    return new OutlierResult(scoreMeta, scoreResult);
  }
957243
public OutlierResult run(Relation<V> relation) {
    SimilarityQuery<V> snnInstance = similarityFunction.instantiate(relation);
    FiniteProgress progress = LOG.isVerbose() ? new FiniteProgress("Assigning Subspace Outlier Degree", relation.size(), LOG) : null;
    WritableDoubleDataStore sod_scores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC);
    WritableDataStore<SODModel> sod_models = models ? DataStoreUtil.makeStorage(relation.getDBIDs(), DataStoreFactory.HINT_STATIC, SODModel.class) : null;
    DoubleMinMax minmax = new DoubleMinMax();
    for(DBIDIter iter = relation.iterDBIDs(); iter.valid(); iter.advance()) {
      DBIDs neighborhood = getNearestNeighbors(relation, snnInstance, iter);

      double[] center;
      long[] weightVector = null;
      double sod = 0.;
      if(neighborhood.size() > 0) {
        center = Centroid.make(relation, neighborhood).getArrayRef();
        // Note: per-dimension variances; no covariances.
        double[] variances = computePerDimensionVariances(relation, center, neighborhood);
        double expectationOfVariance = Mean.of(variances);
        weightVector = BitsUtil.zero(variances.length);
        for(int d = 0; d < variances.length; d++) {
          if(variances[d] < alpha * expectationOfVariance) {
            BitsUtil.setI(weightVector, d);
          }
        }
        sod = subspaceOutlierDegree(relation.get(iter), center, weightVector);
      }
      else {
        center = relation.get(iter).toArray();
      }

      if(sod_models != null) {
        sod_models.put(iter, new SODModel(center, weightVector));
      }
      sod_scores.putDouble(iter, sod);
      minmax.put(sod);
      LOG.incrementProcessed(progress);
    }
    LOG.ensureCompleted(progress);
    // combine results.
    OutlierScoreMeta meta = new BasicOutlierScoreMeta(minmax.getMin(), minmax.getMax());
    OutlierResult sodResult = new OutlierResult(meta, new MaterializedDoubleRelation("Subspace Outlier Degree", "sod-outlier", sod_scores, relation.getDBIDs()));
    if(sod_models != null) {
      sodResult.addChildResult(new MaterializedRelation<>("Subspace Outlier Model", "sod-outlier", new SimpleTypeInformation<>(SODModel.class), sod_models, relation.getDBIDs()));
    }
    return sodResult;
  }
1005980
protected void computeINFLO(Relation<O> relation, ModifiableDBIDs pruned, KNNQuery<O> knnq, WritableDataStore<ModifiableDBIDs> rNNminuskNNs, WritableDoubleDataStore inflos, DoubleMinMax inflominmax) {
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("Computing INFLOs", relation.size(), LOG) : null;
    HashSetModifiableDBIDs set = DBIDUtil.newHashSet();
    for(DBIDIter iter = relation.iterDBIDs(); iter.valid(); iter.advance()) {
      if(pruned.contains(iter)) {
        inflos.putDouble(iter, 1.);
        inflominmax.put(1.);
        LOG.incrementProcessed(prog);
        continue;
      }
      final KNNList knn = knnq.getKNNForDBID(iter, kplus1);
      if(knn.getKNNDistance() == 0.) {
        inflos.putDouble(iter, 1.);
        inflominmax.put(1.);
        LOG.incrementProcessed(prog);
        continue;
      }
      set.clear();
      set.addDBIDs(knn);
      set.addDBIDs(rNNminuskNNs.get(iter));
      // Compute mean density of NN \cup RNN
      double sum = 0.;
      int c = 0;
      for(DBIDIter niter = set.iter(); niter.valid(); niter.advance()) {
        if(DBIDUtil.equal(iter, niter)) {
          continue;
        }
        final double kdist = knnq.getKNNForDBID(niter, kplus1).getKNNDistance();
        if(kdist <= 0) {
          sum = Double.POSITIVE_INFINITY;
          c++;
          break;
        }
        sum += 1. / kdist;
        c++;
      }
      sum *= knn.getKNNDistance();
      final double inflo = sum == 0 ? 1. : sum / c;
      inflos.putDouble(iter, inflo);
      inflominmax.put(inflo);
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);
  }
620023
protected double computePLOFs(Relation<O> relation, KNNQuery<O> knn, WritableDoubleDataStore pdists, WritableDoubleDataStore plofs) {
    FiniteProgress progressPLOFs = LOG.isVerbose() ? new FiniteProgress("PLOFs for objects", relation.size(), LOG) : null;
    double nplof = 0.;
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      final KNNList neighbors = knn.getKNNForDBID(iditer, kcomp + 1); // + query
                                                                      // point
      // use first kref neighbors as comparison set.
      int ks = 0;
      double sum = 0.;
      for(DBIDIter neighbor = neighbors.iter(); neighbor.valid() && ks < kcomp; neighbor.advance()) {
        if(DBIDUtil.equal(neighbor, iditer)) {
          continue;
        }
        sum += pdists.doubleValue(neighbor);
        ks++;
      }
      double plof = MathUtil.max(pdists.doubleValue(iditer) * ks / sum, 1.0);
      if(Double.isNaN(plof) || Double.isInfinite(plof)) {
        plof = 1.0;
      }
      plofs.putDouble(iditer, plof);
      nplof += (plof - 1.0) * (plof - 1.0);

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

    nplof = lambda * FastMath.sqrt(nplof / relation.size());
    if(LOG.isDebuggingFine()) {
      LOG.debugFine("nplof normalization factor is " + nplof);
    }
    return nplof > 0. ? nplof : 1.;
  }
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;
  }
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());
  }