Bookmark this: tool.io/data-mining/apriori/source-code
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.