Skip to content

Main content

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.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools