Skip to content

Main content

Association-Rule Generator Source Code

Browse the implementation files for Association-Rule Generator.
tool.ts typescript
// Tool: Association-Rule Generator

import { mineFrequentItemsets } from '../apriori/tool';

type Item = number | string;

const MAX_RULES = 100_000;

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

const signature = (items: Item[]): string =>
	JSON.stringify(items.map(itemKey).sort());

const parseProbability = (
	input: unknown,
	allowZero = false
): number | null => {
	if (
		(typeof input !== 'string' && typeof input !== 'number') ||
		(typeof input === 'string' && input.trim() === '')
	) {
		return null;
	}

	const value = Number(input);
	const minimum = allowZero ? 0 : Number.MIN_VALUE;

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

const parseNonNegativeNumber = (
	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 : null;
};

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

export const generateAssociationRules = (
	transactionsInput: unknown,
	minimumSupportInput: unknown,
	minimumConfidenceInput: unknown,
	minimumLiftInput: unknown,
	maximumItemsetSizeInput: unknown
): string => {
	const minimumConfidence = parseProbability(
		minimumConfidenceInput,
		true
	);
	const minimumLift = parseNonNegativeNumber(minimumLiftInput);

	if (minimumConfidence === null || minimumLift === null)
		return '';

	const itemsetResult = mineFrequentItemsets(
		transactionsInput,
		minimumSupportInput,
		maximumItemsetSizeInput
	);

	if (itemsetResult === '') return '';

	const parsed = JSON.parse(itemsetResult) as {
		frequentItemsets: Array<{
			items: Item[];
			support: number;
		}>;
		transactionCount: number;
	};
	const supportByItemset = new Map(
		parsed.frequentItemsets.map((itemset) => [
			signature(itemset.items),
			itemset.support
		])
	);
	const rules: Array<{
		antecedent: Item[];
		confidence: number;
		consequent: Item[];
		leverage: number;
		lift: number;
		support: number;
	}> = [];

	for (const itemset of parsed.frequentItemsets) {
		if (itemset.items.length < 2) continue;

		const subsetCount = 2 ** itemset.items.length;

		for (let mask = 1; mask < subsetCount - 1; mask += 1) {
			const antecedent = itemset.items.filter(
				(_, index) => (mask & (1 << index)) !== 0
			);
			const consequent = itemset.items.filter(
				(_, index) => (mask & (1 << index)) === 0
			);
			const antecedentSupport = supportByItemset.get(
				signature(antecedent)
			);
			const consequentSupport = supportByItemset.get(
				signature(consequent)
			);

			if (
				antecedentSupport === undefined ||
				consequentSupport === undefined ||
				antecedentSupport <= 0 ||
				consequentSupport <= 0
			) {
				continue;
			}

			const confidence = itemset.support / antecedentSupport;
			const lift = confidence / consequentSupport;

			if (
				confidence + Number.EPSILON < minimumConfidence ||
				lift + Number.EPSILON < minimumLift
			) {
				continue;
			}

			rules.push({
				antecedent,
				confidence: round(confidence),
				consequent,
				leverage: round(
					itemset.support -
						antecedentSupport * consequentSupport
				),
				lift: round(lift),
				support: itemset.support
			});

			if (rules.length > MAX_RULES) return '';
		}
	}

	rules.sort(
		(first, second) =>
			second.confidence - first.confidence ||
			second.lift - first.lift ||
			signature(first.antecedent).localeCompare(
				signature(second.antecedent)
			)
	);

	return JSON.stringify(
		{
			ruleCount: rules.length,
			rules,
			transactionCount: parsed.transactionCount
		},
		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: 'Association-Rule Generator',
	slug: 'data-mining/association-rules',
	intro:
		'Generate implication rules from frequent itemsets and filter them by support, confidence, and lift.',
	tool: generateAssociationRules,
	i: [
		{
			example: DEFAULT_TRANSACTIONS,
			label: 'Transactions',
			placeholder: 'JSON array of item arrays',
			render: 'textarea',
			type: 'text',
			value: DEFAULT_TRANSACTIONS
		},
		{
			example: '0.4',
			label: 'Minimum Support',
			placeholder: 'Support above 0 and up to 1',
			type: 'number',
			value: 0.4
		},
		{
			example: '0.7',
			label: 'Minimum Confidence',
			placeholder: 'Confidence from 0 to 1',
			type: 'number',
			value: 0.7
		},
		{
			example: '1',
			label: 'Minimum Lift',
			placeholder: 'Non-negative lift threshold',
			type: 'number',
			value: 1
		},
		{
			example: '3',
			label: 'Maximum Itemset Size',
			placeholder: 'Maximum size from 1 to 10',
			type: 'number',
			value: 3
		}
	],
	o: [
		{
			example: '{ "ruleCount": 2, "rules": [] }',
			label: 'Association Rules',
			placeholder: 'Association rules 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: 'Association rule learning — Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Association_rule_learning'
		}
	]
};

export default Tool;

Description

Browse the implementation files for Association-Rule Generator.

References

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

Similar or alternative tools