Skip to content

Main content

Archetypal Analysis Demonstrator Source Code

Browse the implementation files for Archetypal Analysis Demonstrator.
tool.ts typescript
// Tool: Archetypal Analysis Demonstrator

const MAX_ARCHETYPES = 20;
const MAX_DIMENSIONS = 20;
const MAX_ITERATIONS = 2_000;
const MAX_POINTS = 200;
const MAX_WORK = 20_000_000;

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 parseData = (input: unknown): number[][] | null => {
	if (typeof input !== 'string' || input.trim() === '')
		return null;

	try {
		const data: unknown = JSON.parse(input);

		if (
			!Array.isArray(data) ||
			data.length < 2 ||
			data.length > MAX_POINTS ||
			!Array.isArray(data[0]) ||
			data[0].length < 1 ||
			data[0].length > MAX_DIMENSIONS
		) {
			return null;
		}

		const dimensions = data[0].length;

		return data.every(
			(point) =>
				Array.isArray(point) &&
				point.length === dimensions &&
				point.every(
					(value) =>
						typeof value === 'number' && Number.isFinite(value)
				)
		)
			? (data as number[][])
			: null;
	} catch {
		return null;
	}
};

const squaredDistance = (
	first: number[],
	second: number[]
): number =>
	first.reduce(
		(total, value, index) =>
			total + (value - second[index]) ** 2,
		0
	);

const projectSimplex = (values: number[]): number[] => {
	const sorted = [...values].sort(
		(first, second) => second - first
	);
	let cumulative = 0;
	let rho = 0;

	for (let index = 0; index < sorted.length; index += 1) {
		cumulative += sorted[index];

		if (sorted[index] + (1 - cumulative) / (index + 1) > 0) {
			rho = index;
		}
	}

	const theta =
		(sorted
			.slice(0, rho + 1)
			.reduce((sum, value) => sum + value, 0) -
			1) /
		(rho + 1);

	return values.map((value) => Math.max(0, value - theta));
};

const multiply = (
	coefficients: number[][],
	values: number[][]
): number[][] =>
	coefficients.map((row) =>
		values[0].map((_, dimension) =>
			row.reduce(
				(total, coefficient, index) =>
					total + coefficient * values[index][dimension],
				0
			)
		)
	);

const round = (value: number): number =>
	Number(value.toPrecision(10));

export const demonstrateArchetypalAnalysis = (
	dataInput: unknown,
	archetypeCountInput: unknown,
	iterationCountInput: unknown,
	learningRateInput: unknown
): string => {
	const data = parseData(dataInput);
	const archetypeCount = parsePositiveInteger(
		archetypeCountInput,
		MAX_ARCHETYPES
	);
	const iterationCount = parsePositiveInteger(
		iterationCountInput,
		MAX_ITERATIONS
	);
	const learningRate = parseFiniteNumber(learningRateInput);

	if (
		data === null ||
		archetypeCount === null ||
		archetypeCount > data.length ||
		iterationCount === null ||
		learningRate === null ||
		learningRate <= 0 ||
		learningRate > 1 ||
		data.length *
			data[0].length *
			archetypeCount *
			iterationCount >
			MAX_WORK
	) {
		return '';
	}

	const dimensions = data[0].length;
	const centroid = data[0].map(
		(_, dimension) =>
			data.reduce(
				(total, point) => total + point[dimension],
				0
			) / data.length
	);
	const selected: number[] = [];

	while (selected.length < archetypeCount) {
		let bestIndex = -1;
		let bestDistance = -Infinity;

		for (let index = 0; index < data.length; index += 1) {
			if (selected.includes(index)) continue;

			const distance =
				selected.length === 0
					? squaredDistance(data[index], centroid)
					: Math.min(
							...selected.map((selectedIndex) =>
								squaredDistance(
									data[index],
									data[selectedIndex]
								)
							)
						);

			if (distance > bestDistance) {
				bestDistance = distance;
				bestIndex = index;
			}
		}

		selected.push(bestIndex);
	}

	let beta: number[][] = selected.map((selectedIndex) =>
		Array.from({ length: data.length }, (_, index) =>
			index === selectedIndex ? 1 : 0
		)
	);
	let alpha = Array.from({ length: data.length }, () =>
		new Array<number>(archetypeCount).fill(1 / archetypeCount)
	);

	for (
		let iteration = 0;
		iteration < iterationCount;
		iteration += 1
	) {
		let archetypes = multiply(beta, data);
		let reconstructions = multiply(alpha, archetypes);

		alpha = alpha.map((coefficients, pointIndex) => {
			const gradient = archetypes.map(
				(archetype) =>
					2 *
					archetype.reduce(
						(total, value, dimension) =>
							total +
							(reconstructions[pointIndex][dimension] -
								data[pointIndex][dimension]) *
								value,
						0
					)
			);

			return projectSimplex(
				coefficients.map(
					(value, index) =>
						value - learningRate * gradient[index]
				)
			);
		});

		reconstructions = multiply(alpha, archetypes);
		const archetypeGradients = Array.from(
			{ length: archetypeCount },
			() => new Array<number>(dimensions).fill(0)
		);

		for (
			let pointIndex = 0;
			pointIndex < data.length;
			pointIndex += 1
		) {
			for (
				let archetypeIndex = 0;
				archetypeIndex < archetypeCount;
				archetypeIndex += 1
			) {
				for (
					let dimension = 0;
					dimension < dimensions;
					dimension += 1
				) {
					archetypeGradients[archetypeIndex][dimension] +=
						2 *
						alpha[pointIndex][archetypeIndex] *
						(reconstructions[pointIndex][dimension] -
							data[pointIndex][dimension]);
				}
			}
		}

		beta = beta.map((coefficients, archetypeIndex) => {
			const gradient = data.map((point) =>
				point.reduce(
					(total, value, dimension) =>
						total +
						archetypeGradients[archetypeIndex][dimension] *
							value,
					0
				)
			);

			return projectSimplex(
				coefficients.map(
					(value, index) =>
						value - learningRate * gradient[index]
				)
			);
		});

		archetypes = multiply(beta, data);

		if (
			![
				...alpha.flat(),
				...beta.flat(),
				...archetypes.flat()
			].every(Number.isFinite)
		) {
			return '';
		}
	}

	const archetypes = multiply(beta, data);
	const reconstructions = multiply(alpha, archetypes);
	const sumSquaredError = data.reduce(
		(total, point, index) =>
			total + squaredDistance(point, reconstructions[index]),
		0
	);

	if (!Number.isFinite(sumSquaredError)) return '';

	return JSON.stringify(
		{
			archetypeCoefficients: beta.map((row) => row.map(round)),
			archetypes: archetypes.map((row) => row.map(round)),
			mixtureCoefficients: alpha.map((row) => row.map(round)),
			sumSquaredError: round(sumSquaredError)
		},
		null,
		2
	);
};

export const Tool: TypeTool = {
	name: 'Archetypal Analysis Demonstrator',
	slug: 'data-analysis/archetypal-analysis',
	intro:
		'Approximate multivariate observations as convex mixtures of archetypes that are themselves mixtures of the observations.',
	tool: demonstrateArchetypalAnalysis,
	i: [
		{
			example: '[[0,0],[0,1],[1,0],[1,1],[0.5,0.5]]',
			label: 'Data',
			placeholder:
				'JSON array of equally sized numeric observations',
			render: 'textarea',
			type: 'text',
			value: '[[0,0],[0,1],[1,0],[1,1],[0.5,0.5]]'
		},
		{
			example: '3',
			label: 'Archetypes',
			placeholder: 'Number of archetypes',
			type: 'number',
			value: 3
		},
		{
			example: '300',
			label: 'Iterations',
			placeholder: 'Projected-gradient iterations',
			type: 'number',
			value: 300
		},
		{
			example: '0.01',
			label: 'Learning Rate',
			placeholder: 'Positive projected-gradient step up to 1',
			type: 'number',
			value: 0.01
		}
	],
	o: [
		{
			example: '{ "archetypes": [], "sumSquaredError": 0 }',
			label: 'Archetypal Analysis',
			placeholder:
				'Archetypes and mixture coefficients will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'Archetypal Analysis',
			url: 'https://doi.org/10.1080/00401706.1994.10485840'
		},
		{
			title: 'Archetypal analysis — Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Archetypal_analysis'
		}
	]
};

export default Tool;

Description

Browse the implementation files for Archetypal Analysis Demonstrator.

References

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

Similar or alternative tools