import { euclidean } from "../metrics/index.js";
import { Heap } from "../datastructure/index.js";
/**
* @class
* @alias OPTICS
*/
export class OPTICS {
/**
* **O**rdering **P**oints **T**o **I**dentify the **C**lustering **S**tructure.
* @constructor
* @memberof module:clustering
* @alias OPTICS
* @todo needs restructuring.
* @param {Matrix} matrix - the data.
* @param {Number} epsilon - the minimum distance which defines whether a point is a neighbor or not.
* @param {Number} min_points - the minimum number of points which a point needs to create a cluster. (Should be higher than 1, else each point creates a cluster.)
* @param {Function} [metric = euclidean] - the distance metric which defines the distance between two points of the {@link matrix}.
* @returns {OPTICS}
* @see {@link https://www.dbs.ifi.lmu.de/Publikationen/Papers/OPTICS.pdf}
* @see {@link https://en.wikipedia.org/wiki/OPTICS_algorithm}
*/
constructor(matrix, epsilon, min_points, metric = euclidean) {
this._matrix = matrix;
this._epsilon = epsilon;
this._min_points = min_points;
this._metric = metric;
this._ordered_list = [];
this._clusters = [];
this._DB = new Array(matrix.shape[0]).fill();
this.init();
return this;
}
/**
* Computes the clustering.
*/
init() {
const ordered_list = this._ordered_list;
const matrix = this._matrix;
const N = matrix.shape[0];
const DB = this._DB;
const clusters = this._clusters;
let cluster_index = this._cluster_index = 0;
for (let i = 0; i < N; ++i) {
DB[i] = {
"element": matrix.row(i),
"index": i,
"reachability_distance": undefined,
"processed": false,
}
}
for (const p of DB) {
if (p.processed) continue;
p.neighbors = this._get_neighbors(p);
p.processed = true;
clusters.push([p.index])
cluster_index = clusters.length - 1;
ordered_list.push(p);
if (this._core_distance(p) != undefined) {
const seeds = new Heap(null, d => d.reachability_distance, "min")
this._update(p, seeds);
this._expand_cluster(seeds, clusters[cluster_index]);
}
}
return this;
}
/**
*
* @private
* @param {Object} p - a point of {@link matrix}.
* @returns {Array} An array consisting of the {@link epsilon}-neighborhood of {@link p}.
*/
_get_neighbors(p) {
if ("neighbors" in p) return p.neighbors;
const DB = this._DB;
const metric = this._metric;
const epsilon = this._epsilon;
const neighbors = [];
for (const q of DB) {
if (q.index == p.index) continue;
if (metric(p.element, q.element) < epsilon) {
neighbors.push(q);
}
}
return neighbors;
}
/**
*
* @private
* @param {Object} p - a point of {@link matrix}.
* @returns {Number} The distance to the {@link min_points}-th nearest point of {@link p}, or undefined if the {@link epsilon}-neighborhood has fewer elements than {@link min_points}.
*/
_core_distance(p) {
const min_points = this._min_points;
const metric = this._metric;
if (p.neighbors && p.neighbors.length <= min_points) {
return undefined;
}
return metric(p.element, p.neighbors[min_points].element);
}
/**
* Updates the reachability distance of the points.
* @private
* @param {Object} p
* @param {Heap} seeds
*/
_update(p, seeds) {
const metric = this._metric;
const core_distance = this._core_distance(p);
const neighbors = this._get_neighbors(p);//p.neighbors;
for (const q of neighbors) {
if (q.processed) continue;
const new_reachability_distance = Math.max(core_distance, metric(p.element, q.element));
//if (q.reachability_distance == undefined) { // q is not in seeds
if (seeds.raw_data().findIndex(d => d.element == q) < 0) {
q.reachability_distance = new_reachability_distance;
seeds.push(q);
} else { // q is in seeds
if (new_reachability_distance < q.reachability_distance) {
q.reachability_distance = new_reachability_distance;
seeds = Heap.heapify(seeds.data(), d => d.reachability_distance, "min"); // seeds change key =/
}
}
}
}
/**
* Expands the {@link cluster} with points in {@link seeds}.
* @private
* @param {Heap} seeds
* @param {Array} cluster
*/
_expand_cluster(seeds, cluster) {
const ordered_list = this._ordered_list;
while (!seeds.empty) {
const q = seeds.pop().element;
q.neighbors = this._get_neighbors(q);
q.processed = true;
cluster.push(q.index);
ordered_list.push(q);
if (this._core_distance(q) != undefined) {
this._update(q, seeds);
this._expand_cluster(seeds, cluster);
}
}
}
/**
* Returns an array of clusters.
* @returns {Array<Array>} Array of clusters with the indices of the rows in given {@link matrix}.
*/
get_clusters() {
const clusters = [];
const outliers = [];
const min_points = this._min_points;
for (const cluster of this._clusters) {
if (cluster.length < min_points) {
outliers.push(...cluster);
} else {
clusters.push(cluster);
}
}
clusters.push(outliers);
return clusters;
}
/**
* @returns {Array} Returns an array, where the ith entry defines the cluster affirmation of the ith point of {@link matrix}. (-1 stands for outlier)
*/
get_cluster_affirmation() {
const N = this._matrix.shape[0];
const result = new Array(N).fill();
const clusters = this.get_clusters();
for (let i = 0, n = clusters.length; i < n; ++i) {
const cluster = clusters[i]
for (const index of cluster) {
result[index] = (i < n - 1) ? i : -1;
}
}
return result;
}
}