Bookmark this: tool.io/clustering/affinity-propagation/source-code
Affinity Propagation Clustering Tool Source Code
Browse the implementation files for Affinity Propagation Clustering Tool.tool.ts typescript
// Tool: Affinity Propagation Clustering
type Preference = 'median' | 'minimum';
const MAX_DIMENSIONS = 20;
const MAX_ITERATIONS = 1_000;
const MAX_POINTS = 100;
const PREFERENCES: Preference[] = ['median', 'minimum'];
const parseFiniteNumber = (input: unknown): number | null => {
if (
(typeof input !== 'string' && typeof input !== 'number') ||
(typeof input === 'string' && input.trim() === '')
) {
return null;
}
const value = Number(input);
return Number.isFinite(value) ? value : null;
};
const parsePositiveInteger = (
input: unknown,
maximum: number
): number | null => {
const value = parseFiniteNumber(input);
return value !== null &&
Number.isSafeInteger(value) &&
value >= 1 &&
value <= maximum
? value
: null;
};
const parsePoints = (input: unknown): number[][] | null => {
if (typeof input !== 'string' || input.trim() === '')
return null;
try {
const points: unknown = JSON.parse(input);
if (
!Array.isArray(points) ||
points.length < 2 ||
points.length > MAX_POINTS ||
!Array.isArray(points[0]) ||
points[0].length < 1 ||
points[0].length > MAX_DIMENSIONS
) {
return null;
}
const dimensions = points[0].length;
return points.every(
(point) =>
Array.isArray(point) &&
point.length === dimensions &&
point.every(
(value) =>
typeof value === 'number' && Number.isFinite(value)
)
)
? (points as number[][])
: null;
} catch {
return null;
}
};
const median = (values: number[]): number => {
const sorted = [...values].sort(
(first, second) => first - second
);
const middle = Math.floor(sorted.length / 2);
return sorted.length % 2 === 0
? (sorted[middle - 1] + sorted[middle]) / 2
: sorted[middle];
};
const round = (value: number): number =>
Number(value.toPrecision(12));
export const clusterByAffinityPropagation = (
pointsInput: unknown,
preferenceInput: unknown,
dampingInput: unknown,
maxIterationsInput: unknown,
convergenceIterationsInput: unknown
): string => {
const points = parsePoints(pointsInput);
const damping = parseFiniteNumber(dampingInput);
const maxIterations = parsePositiveInteger(
maxIterationsInput,
MAX_ITERATIONS
);
const convergenceIterations = parsePositiveInteger(
convergenceIterationsInput,
MAX_ITERATIONS
);
if (
points === null ||
!PREFERENCES.includes(preferenceInput as Preference) ||
damping === null ||
damping < 0.5 ||
damping >= 1 ||
maxIterations === null ||
convergenceIterations === null ||
convergenceIterations > maxIterations
) {
return '';
}
const size = points.length;
const similarities = Array.from({ length: size }, () =>
new Array<number>(size).fill(0)
);
const offDiagonal: number[] = [];
for (let pointIndex = 0; pointIndex < size; pointIndex += 1) {
for (
let candidateIndex = 0;
candidateIndex < size;
candidateIndex += 1
) {
if (pointIndex === candidateIndex) continue;
const similarity = -points[pointIndex].reduce(
(total, coordinate, dimension) =>
total +
(coordinate - points[candidateIndex][dimension]) ** 2,
0
);
if (!Number.isFinite(similarity)) return '';
similarities[pointIndex][candidateIndex] = similarity;
offDiagonal.push(similarity);
}
}
const preference =
preferenceInput === 'minimum'
? Math.min(...offDiagonal)
: median(offDiagonal);
for (let index = 0; index < size; index += 1) {
similarities[index][index] = preference;
}
let availabilities = Array.from({ length: size }, () =>
new Array<number>(size).fill(0)
);
let responsibilities = Array.from({ length: size }, () =>
new Array<number>(size).fill(0)
);
let previousExemplars = '';
let stableIterations = 0;
let iterations = 0;
let converged = false;
for (
let iteration = 1;
iteration <= maxIterations;
iteration += 1
) {
const nextResponsibilities = responsibilities.map((row) => [
...row
]);
for (
let pointIndex = 0;
pointIndex < size;
pointIndex += 1
) {
for (
let candidateIndex = 0;
candidateIndex < size;
candidateIndex += 1
) {
let competingMaximum = -Infinity;
for (
let otherIndex = 0;
otherIndex < size;
otherIndex += 1
) {
if (otherIndex === candidateIndex) continue;
competingMaximum = Math.max(
competingMaximum,
availabilities[pointIndex][otherIndex] +
similarities[pointIndex][otherIndex]
);
}
const responsibility =
similarities[pointIndex][candidateIndex] -
competingMaximum;
nextResponsibilities[pointIndex][candidateIndex] =
damping *
responsibilities[pointIndex][candidateIndex] +
(1 - damping) * responsibility;
}
}
const nextAvailabilities = availabilities.map((row) => [
...row
]);
for (
let candidateIndex = 0;
candidateIndex < size;
candidateIndex += 1
) {
let positiveTotal = 0;
for (
let pointIndex = 0;
pointIndex < size;
pointIndex += 1
) {
if (pointIndex !== candidateIndex) {
positiveTotal += Math.max(
0,
nextResponsibilities[pointIndex][candidateIndex]
);
}
}
for (
let pointIndex = 0;
pointIndex < size;
pointIndex += 1
) {
const availability =
pointIndex === candidateIndex
? positiveTotal
: Math.min(
0,
nextResponsibilities[candidateIndex][
candidateIndex
] +
positiveTotal -
Math.max(
0,
nextResponsibilities[pointIndex][
candidateIndex
]
)
);
nextAvailabilities[pointIndex][candidateIndex] =
damping * availabilities[pointIndex][candidateIndex] +
(1 - damping) * availability;
}
}
responsibilities = nextResponsibilities;
availabilities = nextAvailabilities;
iterations = iteration;
const exemplarState = Array.from(
{ length: size },
(_, index) =>
availabilities[index][index] +
responsibilities[index][index] >
0
? '1'
: '0'
).join('');
stableIterations =
exemplarState === previousExemplars
? stableIterations + 1
: 1;
previousExemplars = exemplarState;
if (
exemplarState.includes('1') &&
stableIterations >= convergenceIterations
) {
converged = true;
break;
}
}
const evidence = Array.from(
{ length: size },
(_, index) =>
availabilities[index][index] +
responsibilities[index][index]
);
let exemplars = evidence
.map((value, index) => ({ index, value }))
.filter(({ value }) => value > 0)
.map(({ index }) => index);
if (exemplars.length === 0) {
exemplars = [
evidence.reduce(
(best, value, index) =>
value > evidence[best] ? index : best,
0
)
];
}
const assignments = points.map((_, pointIndex) =>
exemplars.reduce((best, exemplar) =>
similarities[pointIndex][exemplar] >
similarities[pointIndex][best]
? exemplar
: best
)
);
for (const exemplar of exemplars) {
assignments[exemplar] = exemplar;
}
return JSON.stringify(
{
assignments,
clusters: exemplars.map((exemplar) => ({
exemplar,
members: assignments
.map((assignedExemplar, index) => ({
assignedExemplar,
index
}))
.filter(
({ assignedExemplar }) =>
assignedExemplar === exemplar
)
.map(({ index }) => index)
})),
converged,
exemplars,
iterations,
preference: round(preference)
},
null,
2
);
};
export const Tool: TypeTool = {
name: 'Affinity Propagation Clustering Tool',
slug: 'clustering/affinity-propagation',
intro:
'Cluster numeric points by exchanging responsibility and availability messages between candidate exemplars.',
tool: clusterByAffinityPropagation,
i: [
{
example: '[[1,1],[1.2,0.9],[8,8],[8.2,7.9]]',
label: 'Points',
placeholder: 'JSON array of equally sized numeric points',
render: 'textarea',
type: 'text',
value: '[[1,1],[1.2,0.9],[8,8],[8.2,7.9]]'
},
{
example: 'median',
label: 'Preference',
options: [
{
selected: true,
text: 'Median similarity',
value: 'median'
},
{ text: 'Minimum similarity', value: 'minimum' }
],
placeholder: 'Select the shared exemplar preference',
type: 'select',
value: 'median'
},
{
example: '0.7',
help: 'Damping must be at least 0.5 and less than 1.',
label: 'Damping',
placeholder: 'Message damping factor',
type: 'number',
value: 0.7
},
{
example: '200',
label: 'Maximum Iterations',
placeholder: 'Maximum message-passing iterations',
type: 'number',
value: 200
},
{
example: '15',
label: 'Convergence Iterations',
placeholder: 'Stable iterations required to stop',
type: 'number',
value: 15
}
],
o: [
{
example:
'{ "exemplars": [1, 3], "assignments": [1, 1, 3, 3] }',
label: 'Clusters',
placeholder:
'Affinity propagation result will appear here...',
render: 'textarea',
type: 'text'
}
],
cite: [
{
title:
'Clustering by Passing Messages Between Data Points',
url: 'https://doi.org/10.1126/science.1136800'
},
{
title: 'Affinity propagation — Wikipedia',
url: 'https://en.wikipedia.org/wiki/Affinity_propagation'
}
]
};
export default Tool;
Description
Browse the implementation files for Affinity Propagation Clustering Tool.