SFIM / SARE -- streaming frequent itemsets and association rules (Spark)

Requires the spark extra (pip install -e ".[spark]", see Installation).

FIMoTS (Frequent Itemset Mining over Time-sensitive Streams) mines frequent itemsets over a Spark Streaming sliding window, implementing the distributed algorithm of Fernandez-Basso, Francisco-Agra, Martin-Bautista & Ruiz (2019) -- see Citing ARMxtend. Rather than rescanning the whole window on every new batch of transactions, it maintains a Frequent Itemset Tree (FIT) together with per-itemset transforming bounds that bracket how many transactions can be added/removed before an itemset's frequent/infrequent status could possibly change, so only itemsets close to that boundary need their support recomputed.

SFIM and SARE share the exact same FIMoTS implementation (FIMoTS_Structure, FIMoTS_Tree, FIMoTS_Node, FIMoTS_List, FIMoTS_Bounds, WindowData, DecimalFraction, FIMoTS_Algorithm). SARE additionally extracts association rules from the current tree of frequent itemsets -- the extension to association rule mining that the 2019 paper lists as future work.

Running the algorithm

from ARMxtend.SFIM import main  # or ARMxtend.SARE

main(minSuppNum=1, minSuppDen=3, mode="STREAMING", intervals=5,
    hostname="localhost", port=9999, threads=2, seconds=5)
  • minSuppNum/minSuppDen: minimum relative support, as a fraction of integers (e.g. 1/3).
  • mode: "TEXTFILE" for a static dataset (one transaction per line, items separated by spaces, read from filesDir) or "STREAMING" to receive transactions in real time via Spark Streaming.
  • intervals: number of time intervals (batches of transactions) that make up the sliding window.
  • SARE.main additionally accepts minConf: if given, association rules with confidence >= minConf are extracted and printed after every window update, alongside the frequent itemsets.

SARE.extractAssociationRules

extractAssociationRules(actual_fimots_structure, metric="confidence", min_threshold=0.7)

Extracts crisp association rules from the frequent itemsets currently held in a FIMoTS_Structure (built and kept up to date by SARE.main/FIMoTS_Algorithm). Because the FIT already stores, by construction, the support of every non-empty subset of each frequent itemset (candidates are generated by combining shorter frequent itemsets), extracting rules reduces exactly to the crisp, non-distributed case: this function builds the pandas.DataFrame expected by ARM.association_rules from the tree, and delegates to it.

from ARMxtend.SARE import extractAssociationRules

rules = extractAssociationRules(actual_fimots_structure, min_threshold=0.7)

See tests/test_sare_association_rules.py for a runnable example that builds a FIMoTS_Structure by hand (without running the full streaming algorithm) and verifies the extracted rules against FIM.BD_ARE.generate_rules.