Bookmark this: tool.io/clustering/optics/source-code
OPTICS Clustering Tool Source Code
Browse the implementation files for OPTICS Clustering Tool.tool.ts typescript
import { parseFiniteNumberList } from '../../parse/numeric-dataset/tool';
import { parseFiniteNumber } from '../../parse/number/tool';
import { parseInteger } from '../../parse/integer/tool';
type OrderedPoint = {
coreDistance: number | null;
index: number;
point: number[];
reachabilityDistance: number | null;
};
const distance = (a: number[], b: number[]) =>
Math.hypot(...a.map((value, index) => value - b[index]));
export const runOptics = (
pointsInput: unknown,
epsilonInput: unknown,
minimumPointsInput: unknown
): string => {
if (typeof pointsInput !== 'string') return '';
const epsilon = parseFiniteNumber(epsilonInput);
const minimumPoints = parseInteger(minimumPointsInput);
const points = pointsInput
.trim()
.split(/\n+/)
.map(parseFiniteNumberList);
if (
epsilon === null ||
epsilon <= 0 ||
minimumPoints === null ||
minimumPoints < 2 ||
points.length < minimumPoints ||
points.length > 5_000 ||
points.some((point) => !point) ||
new Set(points.map((point) => point!.length)).size !== 1 ||
points.length * (points[0]?.length ?? 0) > 1_000_000
)
return '';
const values = points as number[][];
const processed = new Set<number>();
const reachability = Array<number>(values.length).fill(
Infinity
);
const ordering: OrderedPoint[] = [];
const neighbors = (index: number) =>
values
.map((point, other) => ({
distance: distance(values[index], point),
index: other
}))
.filter((candidate) => candidate.distance <= epsilon)
.sort(
(a, b) => a.distance - b.distance || a.index - b.index
);
const coreDistance = (nearby: { distance: number }[]) =>
nearby.length >= minimumPoints
? nearby[minimumPoints - 1].distance
: Infinity;
const expand = (start: number) => {
const seeds = [start];
while (seeds.length) {
seeds.sort(
(a, b) => reachability[a] - reachability[b] || a - b
);
const current = seeds.shift()!;
if (processed.has(current)) continue;
processed.add(current);
const nearby = neighbors(current);
const core = coreDistance(nearby);
ordering.push({
coreDistance: Number.isFinite(core)
? Number(core.toPrecision(10))
: null,
index: current,
point: values[current],
reachabilityDistance: Number.isFinite(
reachability[current]
)
? Number(reachability[current].toPrecision(10))
: null
});
if (!Number.isFinite(core)) continue;
for (const candidate of nearby)
if (!processed.has(candidate.index)) {
const updated = Math.max(core, candidate.distance);
if (updated < reachability[candidate.index]) {
reachability[candidate.index] = updated;
if (!seeds.includes(candidate.index))
seeds.push(candidate.index);
}
}
}
};
for (let index = 0; index < values.length; index += 1)
if (!processed.has(index)) expand(index);
return JSON.stringify(
{ epsilon, minimumPoints, ordering },
null,
2
);
};
export const Tool: TypeTool = {
name: 'OPTICS Clustering Tool',
slug: 'clustering/optics',
intro:
'Order multidimensional points by density reachability with the OPTICS clustering algorithm.',
tool: runOptics,
i: [
{
example: '0,0\n0.1,0\n0,0.1\n5,5\n5.1,5\n5,5.1',
label: 'Points',
placeholder: 'One numeric point per line',
render: 'textarea',
type: 'text'
},
{
example: '0.5',
label: 'Maximum Radius',
placeholder: 'Positive epsilon',
type: 'number'
},
{
example: '3',
label: 'Minimum Points',
placeholder: 'Core-neighborhood size',
type: 'number'
}
],
o: [
{
example: '{ "ordering": [] }',
label: 'OPTICS Ordering',
placeholder: 'Reachability ordering will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title: 'OPTICS algorithm - Wikipedia',
url: 'https://en.wikipedia.org/wiki/OPTICS_algorithm'
}
]
};
export default Tool;
Description
Browse the implementation files for OPTICS Clustering Tool.