Skip to content

Main content

Apriori Frequent-Itemset Miner Source Code

Browse the implementation files for Apriori Frequent-Itemset Miner.
tool.ts typescript
// Tool: Apriori Frequent-Itemset Miner

type Item = number | string;

const MAX_CANDIDATES = 100_000;
const MAX_ITEMSET_SIZE = 10;
const MAX_TRANSACTIONS = 5_000;
const MAX_UNIQUE_ITEMS = 100;
const MAX_WORK = 20_000_000;

const itemKey = (item: Item): string =>
	`${typeof item}:${String(item)}`;

const parseProbability = (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 > 0 && value <= 1
		? value
		: null;
};

const parsePositiveInteger = (
	input: unknown,
	maximum: number
): number | null => {
	const value =
		typeof input === 'string' || typeof input === 'number'
			? Number(input)
			: NaN;

	return Number.isSafeInteger(value) &&
		value >= 1 &&
		value <= maximum
		? value
		: null;
};

const parseTransactions = (
	input: unknown
): {
	items: Map<string, Item>;
	transactions: Set<string>[];
} | null => {
	if (typeof input !== 'string' || input.trim() === '')
		return null;

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

		if (
			!Array.isArray(transactions) ||
			transactions.length === 0 ||
			transactions.length > MAX_TRANSACTIONS
		) {
			return null;
		}

		const items = new Map<string, Item>();
		const parsed: Set<string>[] = [];

		for (const transaction of transactions) {
			if (
				!Array.isArray(transaction) ||
				transaction.length === 0
			) {
				return null;
			}

			const keys = new Set<string>();

			for (const item of transaction) {
				if (
					!(
						(typeof item === 'string' && item.trim() !== '') ||
						(typeof item === 'number' && Number.isFinite(item))
					)
				) {
					return null;
				}

				const key = itemKey(item);
				keys.add(key);
				items.set(key, item);
			}

			parsed.push(keys);
		}

		return items.size <= MAX_UNIQUE_ITEMS
			? { items, transactions: parsed }
			: null;
	} catch {
		return null;
	}
};

const signature = (keys: string[]): string =>
	JSON.stringify(keys);
const round = (value: number): number =>
	Number(value.toPrecision(12));

export const mineFrequentItemsets = (
	transactionsInput: unknown,
	minimumSupportInput: unknown,
	maximumSizeInput: unknown
): string => {
	const parsed = parseTransactions(transactionsInput);
	const minimumSupport = parseProbability(minimumSupportInput);
	const maximumSize = parsePositiveInteger(
		maximumSizeInput,
		MAX_ITEMSET_SIZE
	);

	if (
		parsed === null ||
		minimumSupport === null ||
		maximumSize === null
	) {
		return '';
	}

	const { items, transactions } = parsed;
	const minimumCount = Math.ceil(
		minimumSupport * transactions.length
	);
	const counts = new Map<string, number>();

	for (const transaction of transactions) {
		for (const key of transaction) {
			counts.set(key, (counts.get(key) ?? 0) + 1);
		}
	}

	let previous = [...counts]
		.filter(([, count]) => count >= minimumCount)
		.map(([key]) => [key])
		.sort((first, second) => first[0].localeCompare(second[0]));
	const frequent: Array<{ count: number; keys: string[] }> =
		previous.map((keys) => ({
			count: counts.get(keys[0])!,
			keys
		}));

	for (
		let size = 2;
		size <= maximumSize && previous.length > 0;
		size += 1
	) {
		const previousSet = new Set(previous.map(signature));
		const candidateMap = new Map<string, string[]>();

		for (let first = 0; first < previous.length; first += 1) {
			for (
				let second = first + 1;
				second < previous.length;
				second += 1
			) {
				const candidate = [
					...new Set([...previous[first], ...previous[second]])
				].sort();

				if (
					candidate.length !== size ||
					!candidate.every((_, removedIndex) =>
						previousSet.has(
							signature(
								candidate.filter(
									(_, index) => index !== removedIndex
								)
							)
						)
					)
				) {
					continue;
				}

				candidateMap.set(signature(candidate), candidate);

				if (candidateMap.size > MAX_CANDIDATES) return '';
			}
		}

		const candidates = [...candidateMap.values()];

		if (candidates.length * transactions.length > MAX_WORK) {
			return '';
		}

		const next: string[][] = [];

		for (const candidate of candidates) {
			const count = transactions.filter((transaction) =>
				candidate.every((key) => transaction.has(key))
			).length;

			if (count >= minimumCount) {
				next.push(candidate);
				frequent.push({ count, keys: candidate });
			}
		}

		previous = next;
	}

	return JSON.stringify(
		{
			frequentItemsets: frequent.map(({ count, keys }) => ({
				count,
				items: keys.map((key) => items.get(key)!),
				size: keys.length,
				support: round(count / transactions.length)
			})),
			minimumCount,
			transactionCount: transactions.length
		},
		null,
		2
	);
};

const DEFAULT_TRANSACTIONS =
	'[["bread","milk"],["bread","diapers","beer","eggs"],["milk","diapers","beer","cola"],["bread","milk","diapers","beer"],["bread","milk","diapers","cola"]]';

export const Tool: TypeTool = {
	name: 'Apriori Frequent-Itemset Miner',
	slug: 'data-mining/apriori',
	intro:
		'Find frequent itemsets with Apriori candidate generation and downward-closure pruning.',
	tool: mineFrequentItemsets,
	i: [
		{
			example: DEFAULT_TRANSACTIONS,
			label: 'Transactions',
			placeholder: 'JSON array of item arrays',
			render: 'textarea',
			type: 'text',
			value: DEFAULT_TRANSACTIONS
		},
		{
			example: '0.6',
			label: 'Minimum Support',
			placeholder: 'Support above 0 and up to 1',
			type: 'number',
			value: 0.6
		},
		{
			example: '3',
			label: 'Maximum Itemset Size',
			placeholder: 'Maximum size from 1 to 10',
			type: 'number',
			value: 3
		}
	],
	o: [
		{
			example:
				'{ "frequentItemsets": [], "transactionCount": 5 }',
			label: 'Frequent Itemsets',
			placeholder: 'Apriori result will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title:
				'Fast Algorithms for Mining Association Rules in Large Databases',
			url: 'https://www.vldb.org/conf/1994/P487.PDF'
		},
		{
			title: 'Apriori algorithm — Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Apriori_algorithm'
		}
	]
};

export default Tool;

Description

Browse the implementation files for Apriori Frequent-Itemset Miner.

References

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

Similar or alternative tools