Editing Association rule learning (section)

=== Eclat algorithm ===

Eclat<ref name="eclat" /> (alt. ECLAT, stands for Equivalence Class Transformation) is a [[backtracking]] algorithm, which traverses the frequent itemset lattice graph in a [[depth-first search]] (DFS) fashion. Whereas the [[breadth-first search]] (BFS) traversal used in the Apriori algorithm will end up checking every subset of an itemset before checking it, DFS traversal checks larger itemsets and can save on checking the support of some of its subsets by virtue of the downward-closer property. Furthermore it will almost certainly use less memory as DFS has a lower space complexity than BFS.

To illustrate this, let there be a frequent itemset {a, b, c}. a DFS may check the nodes in the frequent itemset lattice in the following order: {a} → {a, b} → {a, b, c}, at which point it is known that {b}, {c}, {a, c}, {b, c} all satisfy the support constraint by the downward-closure property. BFS would explore each subset of {a, b, c} before finally checking it. As the size of an itemset increases, the number of its subsets undergoes [[combinatorial explosion]].

It is suitable for both sequential as well as parallel execution with locality-enhancing properties.<ref>{{cite report |citeseerx=10.1.1.42.3283 |hdl=1802/501 |title=New Algorithms for Fast Discovery of Association Rules |pages=283–286 |year=1997 |first1=Mohammed Javeed |last1=Zaki |first2=Srinivasan |last2=Parthasarathy |first3=Mitsunori |last3=Ogihara |first4=Wei |last4=Li }}</ref><ref>{{cite journal|title=Parallel Algorithms for Discovery of Association Rules|doi=10.1023/A:1009773317876 |year=1997 |last1=Zaki |first1=Mohammed J. |journal=Data Mining and Knowledge Discovery |volume=1 |issue=4 |pages=343–373 |last2=Parthasarathy |first2=Srinivasan |last3=Ogihara |first3=Mitsunori |last4=Li |first4=Wei |s2cid=10038675 }}</ref>