Initialize the data set grid by computing quantiles.

@param relation Data relation
@throws IllegalArgumentException
484473
public void setPartitions(Relation<V> relation) throws IllegalArgumentException {
    if((FastMath.log(partitions) / FastMath.log(2)) != (int) (FastMath.log(partitions) / FastMath.log(2))) {
      throw new IllegalArgumentException("Number of partitions must be a power of 2!");
    }

    final int dimensions = RelationUtil.dimensionality(relation);
    final int size = relation.size();
    splitPositions = new double[dimensions][partitions + 1];

    for(int d = 0; d < dimensions; d++) {
      double[] tempdata = new double[size];
      int j = 0;
      for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
        tempdata[j] = relation.get(iditer).doubleValue(d);
        j += 1;
      }
      Arrays.sort(tempdata);

      for(int b = 0; b < partitions; b++) {
        int start = (int) (b * size / (double) partitions);
        splitPositions[d][b] = tempdata[start];
      }
      // make sure that last object will be included
      splitPositions[d][partitions] = tempdata[size - 1] + 0.000001;
    }
  }
137705
public function saveIntoRelation(Relation $relation)
    {
        $ids = [];
        
        if ($values = $this->getValueArray()) {
            $ids = $this->getList()->filter($this->getIDField(), $values)->getIDList();
        }
        
        $relation->setByIDList($ids);
    }
928754
private void setRelationToEntity(Object entity, Object relationEntity, Relation relation)
    {
        if (relation.getTargetEntity().isAssignableFrom(getEntity(relationEntity).getClass()))
        {

            if (relation.isUnary())
            {
                PropertyAccessorHelper.set(entity, relation.getProperty(), getEntity(relationEntity));
            }
            else
            {
                Object associationObject = PropertyAccessorHelper.getObject(entity, relation.getProperty());
                if (associationObject == null || ProxyHelper.isProxyOrCollection(associationObject))
                {
                    associationObject = PropertyAccessorHelper.getCollectionInstance(relation.getProperty());
                    PropertyAccessorHelper.set(entity, relation.getProperty(), associationObject);
                }

                ((Collection) associationObject).add(getEntity(relationEntity));
            }
        }
    }
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;
  }
1185233
public OutlierResult run(Database database, Relation<V> relation) {
    final int dbsize = relation.size();
    ArrayList<ArrayList<DBIDs>> ranges = buildRanges(relation);

    Heap<Individuum>.UnorderedIter individuums = (new EvolutionarySearch(relation, ranges, m, rnd.getSingleThreadedRandom())).run();

    WritableDoubleDataStore outlierScore = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_STATIC);
    for(; individuums.valid(); individuums.advance()) {
      DBIDs ids = computeSubspaceForGene(individuums.get().getGene(), ranges);
      double sparsityC = sparsity(ids.size(), dbsize, k, phi);
      for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
        double prev = outlierScore.doubleValue(iter);
        if(Double.isNaN(prev) || sparsityC < prev) {
          outlierScore.putDouble(iter, sparsityC);
        }
      }
    }

    DoubleMinMax minmax = new DoubleMinMax();
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      double val = outlierScore.doubleValue(iditer);
      if(Double.isNaN(val)) {
        outlierScore.putDouble(iditer, val = 0.);
      }
      minmax.put(val);
    }
    DoubleRelation scoreResult = new MaterializedDoubleRelation("AggarwalYuEvolutionary", "aggarwal-yu-outlier", outlierScore, relation.getDBIDs());
    OutlierScoreMeta meta = new InvertedOutlierScoreMeta(minmax.getMin(), minmax.getMax(), Double.NEGATIVE_INFINITY, 0.0);
    return new OutlierResult(meta, scoreResult);
  }
1050990
protected void initializeDataExtends(Relation<NumberVector> relation, int dim, double[] min, double[] extend) {
    assert (min.length == dim && extend.length == dim);
    // if no parameter for min max compute min max values for each dimension
    // from dataset
    if(minima == null || maxima == null || minima.length == 0 || maxima.length == 0) {
      double[][] minmax = RelationUtil.computeMinMax(relation);
      final double[] dmin = minmax[0], dmax = minmax[1];
      for(int d = 0; d < dim; d++) {
        min[d] = dmin[d];
        extend[d] = dmax[d] - dmin[d];
      }
      return;
    }
    if(minima.length == dim) {
      System.arraycopy(minima, 0, min, 0, dim);
    }
    else if(minima.length == 1) {
      Arrays.fill(min, minima[0]);
    }
    else {
      throw new AbortException("Invalid minima specified: expected " + dim + " got minima dimensionality: " + minima.length);
    }
    if(maxima.length == dim) {
      for(int d = 0; d < dim; d++) {
        extend[d] = maxima[d] - min[d];
      }
      return;
    }
    else if(maxima.length == 1) {
      for(int d = 0; d < dim; d++) {
        extend[d] = maxima[0] - min[d];
      }
      return;
    }
    else {
      throw new AbortException("Invalid maxima specified: expected " + dim + " got maxima dimensionality: " + maxima.length);
    }
  }
917596
def init_relation(self, models, relation):
        
        for model in models:
            model.set_relation(relation, Result(None, self, model))

        return models
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);
  }
1331696
protected void removePreviousRelation(Relation<?> relation) {
    if(keep) {
      return;
    }
    boolean first = true;
    for(It<Index> it = relation.getHierarchy().iterDescendants(relation).filter(Index.class); it.valid(); it.advance()) {
      if(first) {
        Logging.getLogger(getClass()).statistics("Index statistics when removing initial data relation.");
        first = false;
      }
      it.get().logStatistics();
    }
    ResultUtil.removeRecursive(relation.getHierarchy(), relation);
  }
201158
protected WritableDataStore<Meta> initializeMeta(Relation<V> relation, double[][] means) {
    NumberVectorDistanceFunction<? super V> df = getDistanceFunction();
    // The actual storage
    final WritableDataStore<Meta> metas = DataStoreUtil.makeStorage(relation.getDBIDs(), DataStoreFactory.HINT_HOT | DataStoreFactory.HINT_TEMP, Meta.class);
    // Build the metadata, track the two nearest cluster centers.
    for(DBIDIter id = relation.iterDBIDs(); id.valid(); id.advance()) {
      Meta c = new Meta(k);
      V fv = relation.get(id);
      for(int i = 0; i < k; i++) {
        final double d = c.dists[i] = df.distance(fv, DoubleVector.wrap(means[i]));
        if(i > 0) {
          if(d < c.dists[c.primary]) {
            c.primary = i;
          }
          else if(d > c.dists[c.secondary]) {
            c.secondary = i;
          }
        }
      }
      metas.put(id, c);
    }
    return metas;
  }
337475
public Clustering<SubspaceModel> run(Database db, Relation<V> relation) {
    if(mu >= relation.size()) {
      throw new AbortException("Parameter mu is chosen unreasonably large. This won't yield meaningful results.");
    }
    DiSHClusterOrder opticsResult = new Instance(db, relation).run();

    if(LOG.isVerbose()) {
      LOG.verbose("Compute Clusters.");
    }
    return computeClusters(relation, opticsResult);
  }
446651
@Override
  public void initialize() {
    if(databaseConnection == null) {
      return; // Supposedly we initialized already.
    }
    if(LOG.isDebugging()) {
      LOG.debugFine("Loading data from database connection.");
    }
    MultipleObjectsBundle bundle = databaseConnection.loadData();
    // Run at most once.
    databaseConnection = null;

    // Find DBIDs for bundle
    {
      DBIDs bids = bundle.getDBIDs();
      if(bids instanceof ArrayStaticDBIDs) {
        this.ids = (ArrayStaticDBIDs) bids;
      }
      else if(bids == null) {
        this.ids = DBIDUtil.generateStaticDBIDRange(bundle.dataLength());
      }
      else {
        this.ids = (ArrayStaticDBIDs) DBIDUtil.makeUnmodifiable(DBIDUtil.ensureArray(bids));
      }
    }
    // Replace id representation (it would be nicer if we would not need
    // DBIDView at all)
    this.idrep = new DBIDView(this.ids);
    relations.add(this.idrep);
    getHierarchy().add(this, idrep);

    DBIDArrayIter it = this.ids.iter();

    int numrel = bundle.metaLength();
    for(int i = 0; i < numrel; i++) {
      SimpleTypeInformation<?> meta = bundle.meta(i);
      @SuppressWarnings("unchecked")
      SimpleTypeInformation<Object> ometa = (SimpleTypeInformation<Object>) meta;
      WritableDataStore<Object> store = DataStoreUtil.makeStorage(ids, DataStoreFactory.HINT_DB, ometa.getRestrictionClass());
      for(it.seek(0); it.valid(); it.advance()) {
        store.put(it, bundle.data(it.getOffset(), i));
      }
      Relation<?> relation = new MaterializedRelation<>(ometa, ids, null, store);
      relations.add(relation);
      getHierarchy().add(this, relation);

      // Try to add indexes where appropriate
      for(IndexFactory<?> factory : indexFactories) {
        if(factory.getInputTypeRestriction().isAssignableFromType(ometa)) {
          @SuppressWarnings("unchecked")
          final IndexFactory<Object> ofact = (IndexFactory<Object>) factory;
          @SuppressWarnings("unchecked")
          final Relation<Object> orep = (Relation<Object>) relation;
          final Index index = ofact.instantiate(orep);
          Duration duration = LOG.isStatistics() ? LOG.newDuration(index.getClass().getName() + ".construction").begin() : null;
          index.initialize();
          if(duration != null) {
            LOG.statistics(duration.end());
          }
          getHierarchy().add(relation, index);
        }
      }
    }

    // fire insertion event
    eventManager.fireObjectsInserted(ids);
  }
1142353
public OutlierResult run(Relation<O> relation) {
    DistanceQuery<O> dq = relation.getDistanceQuery(getDistanceFunction());
    final double logPerp = FastMath.log(perplexity);

    ModifiableDoubleDBIDList dlist = DBIDUtil.newDistanceDBIDList(relation.size() - 1);
    DoubleDBIDListMIter di = dlist.iter();
    double[] p = new double[relation.size() - 1];
    FiniteProgress prog = LOG.isVerbose() ? new FiniteProgress("SOS 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()) {
      // Build sorted neighbors list.
      dlist.clear();
      for(DBIDIter i2 = relation.iterDBIDs(); i2.valid(); i2.advance()) {
        if(DBIDUtil.equal(it, i2)) {
          continue;
        }
        dlist.add(dq.distance(it, i2), i2);
      }
      dlist.sort();
      // Compute affinities
      computePi(it, di, p, perplexity, logPerp);
      // Normalization factor:
      double s = sumOfProbabilities(it, di, p);
      if(s > 0) {
        nominateNeighbors(it, di, p, 1. / s, scores);
      }
      LOG.incrementProcessed(prog);
    }
    LOG.ensureCompleted(prog);
    // Find minimum and maximum.
    DoubleMinMax minmax = new DoubleMinMax();
    for(DBIDIter it2 = relation.iterDBIDs(); it2.valid(); it2.advance()) {
      minmax.put(scores.doubleValue(it2));
    }
    DoubleRelation scoreres = new MaterializedDoubleRelation("Stoachastic Outlier Selection", "sos-outlier", scores, relation.getDBIDs());
    OutlierScoreMeta meta = new ProbabilisticOutlierScore(minmax.getMin(), minmax.getMax(), 0.);
    return new OutlierResult(meta, scoreres);
  }
153438
public Clustering<SubspaceModel> run(Database database, Relation<V> relation) {
    if(RelationUtil.dimensionality(relation) < l) {
      throw new IllegalStateException("Dimensionality of data < parameter l! (" + RelationUtil.dimensionality(relation) + " < " + l + ")");
    }
    DistanceQuery<V> distFunc = database.getDistanceQuery(relation, SquaredEuclideanDistanceFunction.STATIC);
    RangeQuery<V> rangeQuery = database.getRangeQuery(distFunc);
    final Random random = rnd.getSingleThreadedRandom();

    // TODO: use a StepProgress!
    // initialization phase
    if(LOG.isVerbose()) {
      LOG.verbose("1. Initialization phase...");
    }
    int sampleSize = Math.min(relation.size(), k_i * k);
    DBIDs sampleSet = DBIDUtil.randomSample(relation.getDBIDs(), sampleSize, random);

    int medoidSize = Math.min(relation.size(), m_i * k);
    ArrayDBIDs medoids = greedy(distFunc, sampleSet, medoidSize, random);

    if(LOG.isDebugging()) {
      LOG.debugFine(new StringBuilder().append("sampleSize ").append(sampleSize).append('\n') //
          .append("sampleSet ").append(sampleSet).append('\n') //
          .append("medoidSize ").append(medoidSize).append('\n') //
          .append("m ").append(medoids).toString());
    }

    // iterative phase
    if(LOG.isVerbose()) {
      LOG.verbose("2. Iterative phase...");
    }
    double bestObjective = Double.POSITIVE_INFINITY;
    ArrayDBIDs m_best = null;
    DBIDs m_bad = null;
    ArrayDBIDs m_current = initialSet(medoids, k, random);

    if(LOG.isDebugging()) {
      LOG.debugFine(new StringBuilder().append("m_c ").append(m_current).toString());
    }

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

    ArrayList<PROCLUSCluster> clusters = null;
    int loops = 0;
    while(loops < 10) {
      long[][] dimensions = findDimensions(m_current, relation, distFunc, rangeQuery);
      clusters = assignPoints(m_current, dimensions, relation);
      double objectiveFunction = evaluateClusters(clusters, dimensions, relation);

      if(objectiveFunction < bestObjective) {
        // restart counting loops
        loops = 0;
        bestObjective = objectiveFunction;
        m_best = m_current;
        m_bad = computeBadMedoids(m_current, clusters, (int) (relation.size() * 0.1 / k));
      }

      m_current = computeM_current(medoids, m_best, m_bad, random);
      loops++;
      if(cprogress != null) {
        cprogress.setProcessed(clusters.size(), LOG);
      }
    }

    LOG.setCompleted(cprogress);

    // refinement phase
    if(LOG.isVerbose()) {
      LOG.verbose("3. Refinement phase...");
    }

    List<Pair<double[], long[]>> dimensions = findDimensions(clusters, relation);
    List<PROCLUSCluster> finalClusters = finalAssignment(dimensions, relation);

    // build result
    int numClusters = 1;
    Clustering<SubspaceModel> result = new Clustering<>("ProClus clustering", "proclus-clustering");
    for(PROCLUSCluster c : finalClusters) {
      Cluster<SubspaceModel> cluster = new Cluster<>(c.objectIDs);
      cluster.setModel(new SubspaceModel(new Subspace(c.getDimensions()), c.centroid));
      cluster.setName("cluster_" + numClusters++);

      result.addToplevelCluster(cluster);
    }
    return result;
  }
363135
public OutlierResult run(Relation<V> relation) {
    DoubleMinMax mm = new DoubleMinMax();
    // resulting scores
    WritableDoubleDataStore oscores = DataStoreUtil.makeDoubleStorage(relation.getDBIDs(), DataStoreFactory.HINT_TEMP | DataStoreFactory.HINT_HOT);

    // Compute mean and covariance Matrix
    CovarianceMatrix temp = CovarianceMatrix.make(relation);
    double[] mean = temp.getMeanVector(relation).toArray();
    // debugFine(mean.toString());
    double[][] covarianceMatrix = temp.destroyToPopulationMatrix();
    // debugFine(covarianceMatrix.toString());
    double[][] covarianceTransposed = inverse(covarianceMatrix);

    // Normalization factors for Gaussian PDF
    double det = new LUDecomposition(covarianceMatrix).det();
    final double fakt = 1.0 / FastMath.sqrt(MathUtil.powi(MathUtil.TWOPI, RelationUtil.dimensionality(relation)) * det);

    // for each object compute Mahalanobis distance
    for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
      double[] x = minusEquals(relation.get(iditer).toArray(), mean);
      // Gaussian PDF
      final double mDist = transposeTimesTimes(x, covarianceTransposed, x);
      final double prob = fakt * FastMath.exp(-mDist * .5);

      mm.put(prob);
      oscores.putDouble(iditer, prob);
    }

    final OutlierScoreMeta meta;
    if(invert) {
      double max = mm.getMax() != 0 ? mm.getMax() : 1.;
      for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) {
        oscores.putDouble(iditer, (max - oscores.doubleValue(iditer)) / max);
      }
      meta = new BasicOutlierScoreMeta(0.0, 1.0);
    }
    else {
      meta = new InvertedOutlierScoreMeta(mm.getMin(), mm.getMax(), 0.0, Double.POSITIVE_INFINITY);
    }
    DoubleRelation res = new MaterializedDoubleRelation("Gaussian Model Outlier Score", "gaussian-model-outlier", oscores, relation.getDBIDs());
    return new OutlierResult(meta, res);
  }
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);
  }
329816
private void initHeap(ObjectHeap<CASHInterval> heap, Relation<ParameterizationFunction> relation, int dim, DBIDs ids) {
    CASHIntervalSplit split = new CASHIntervalSplit(relation, minPts);

    // determine minimum and maximum function value of all functions
    double[] minMax = determineMinMaxDistance(relation, dim);

    double d_min = minMax[0], d_max = minMax[1];
    double dIntervalLength = d_max - d_min;
    int numDIntervals = (int) FastMath.ceil(dIntervalLength / jitter);
    double dIntervalSize = dIntervalLength / numDIntervals;
    double[] d_mins = new double[numDIntervals],
        d_maxs = new double[numDIntervals];

    if(LOG.isVerbose()) {
      LOG.verbose(new StringBuilder().append("d_min ").append(d_min)//
          .append("\nd_max ").append(d_max)//
          .append("\nnumDIntervals ").append(numDIntervals)//
          .append("\ndIntervalSize ").append(dIntervalSize).toString());
    }

    // alpha intervals
    double[] alphaMin = new double[dim - 1], alphaMax = new double[dim - 1];
    Arrays.fill(alphaMax, Math.PI);

    for(int i = 0; i < numDIntervals; i++) {
      d_mins[i] = (i == 0) ? d_min : d_maxs[i - 1];
      d_maxs[i] = (i < numDIntervals - 1) ? d_mins[i] + dIntervalSize : d_max - d_mins[i];

      HyperBoundingBox alphaInterval = new HyperBoundingBox(alphaMin, alphaMax);
      ModifiableDBIDs intervalIDs = split.determineIDs(ids, alphaInterval, d_mins[i], d_maxs[i]);
      if(intervalIDs != null && intervalIDs.size() >= minPts) {
        heap.add(new CASHInterval(alphaMin, alphaMax, split, intervalIDs, -1, 0, d_mins[i], d_maxs[i]));
      }
    }

    if(LOG.isDebuggingFiner()) {
      LOG.debugFiner(new StringBuilder().append("heap.size: ").append(heap.size()).toString());
    }
  }