I have created a new interactive webpage to demonstrate how the Eclat algorithm is applied for frequent itemset mining. This webpage allows to enter a transaction database, select the minimum support and to see step by step what the Eclat algorithm does to produce the final result. This tool is designed for students or people who want to learn how Eclat work.
The webpage is here: Eclat Algorithm Demo
Let me show you how it works. First you have to enter a transaction database such as this:
Then, you can select a minimum support threshold value such as 2 transactions and click the Run Eclat button:
Then, all the steps of the algorithm will be displayed as well as the final result like this:
## Step 1: Convert the Transaction Data to the Vertical Format
| Item | transaction ids |
--------------------------
bread: {0, 1, 4}
milk: {0, 3, 4}
cheese: {1, 2, 3, 4}
butter: {1, 3}
eggs: {2, 3}
## Step 2: Calculate the support of each item
| Item | transaction ids | Support |
|------|---------------------------|
bread: {0, 1, 4} support: 3
milk: {0, 3, 4} support: 3
cheese: {1, 2, 3, 4} support: 4
butter: {1, 3} support: 2
eggs: {2, 3} support: 2
## Step 3: Keep only the frequent items
| Item | transaction ids | Support |
|------|---------------------------|
bread: {0, 1, 4} support: 3
milk: {0, 3, 4} support: 3
cheese: {1, 2, 3, 4} support: 4
butter: {1, 3} support: 2
eggs: {2, 3} support: 2
## Step 4: Sort The Frequent Items by Ascending Order of Support
| Item | Support |
|------|---------|
| butter | 2
| eggs | 2
| bread | 3
| milk | 3
| cheese | 4
## Step 5: Start the Depth-First Search to Generate Candidates and Find the Frequent Itemsets
##### The algorithm now checks the equivalence class containing these itemsets:
equivalence class: {butter} {eggs} {bread} {milk} {cheese}
Joining candidates {butter} and {eggs} to create {butter eggs}:
Transactions of {butter}: {1, 3}
Transactions of {eggs}: {2, 3}
Transactions of {butter eggs}: {1, 3} n {2, 3} = {3}
Support of {butter eggs}: 1
Frequent: No
Joining candidates {butter} and {bread} to create {butter bread}:
Transactions of {butter}: {1, 3}
Transactions of {bread}: {0, 1, 4}
Transactions of {butter bread}: {1, 3} n {0, 1, 4} = {1}
Support of {butter bread}: 1
Frequent: No
Joining candidates {butter} and {milk} to create {butter milk}:
Transactions of {butter}: {1, 3}
Transactions of {milk}: {0, 3, 4}
Transactions of {butter milk}: {1, 3} n {0, 3, 4} = {3}
Support of {butter milk}: 1
Frequent: No
Joining candidates {butter} and {cheese} to create {butter cheese}:
Transactions of {butter}: {1, 3}
Transactions of {cheese}: {1, 2, 3, 4}
Transactions of {butter cheese}: {1, 3} n {1, 2, 3, 4} = {1, 3}
Support of {butter cheese}: 2
Frequent: Yes
Joining candidates {eggs} and {bread} to create {eggs bread}:
Transactions of {eggs}: {2, 3}
Transactions of {bread}: {0, 1, 4}
Transactions of {eggs bread}: {2, 3} n {0, 1, 4} = {}
Support of {eggs bread}: 0
Frequent: No
Joining candidates {eggs} and {milk} to create {eggs milk}:
Transactions of {eggs}: {2, 3}
Transactions of {milk}: {0, 3, 4}
Transactions of {eggs milk}: {2, 3} n {0, 3, 4} = {3}
Support of {eggs milk}: 1
Frequent: No
Joining candidates {eggs} and {cheese} to create {eggs cheese}:
Transactions of {eggs}: {2, 3}
Transactions of {cheese}: {1, 2, 3, 4}
Transactions of {eggs cheese}: {2, 3} n {1, 2, 3, 4} = {2, 3}
Support of {eggs cheese}: 2
Frequent: Yes
Joining candidates {bread} and {milk} to create {bread milk}:
Transactions of {bread}: {0, 1, 4}
Transactions of {milk}: {0, 3, 4}
Transactions of {bread milk}: {0, 1, 4} n {0, 3, 4} = {0, 4}
Support of {bread milk}: 2
Frequent: Yes
Joining candidates {bread} and {cheese} to create {bread cheese}:
Transactions of {bread}: {0, 1, 4}
Transactions of {cheese}: {1, 2, 3, 4}
Transactions of {bread cheese}: {0, 1, 4} n {1, 2, 3, 4} = {1, 4}
Support of {bread cheese}: 2
Frequent: Yes
##### The algorithm now checks the equivalence class containing these itemsets:
equivalence class: {bread,milk} {bread,cheese}
Joining candidates {bread milk} and {bread cheese} to create {bread milk cheese}:
Transactions of {bread milk}: {0, 4}
Transactions of {bread cheese}: {1, 4}
Transactions of {bread milk cheese}: {0, 4} n {1, 4} = {4}
Support of {bread milk cheese}: 1
Frequent: No
Joining candidates {milk} and {cheese} to create {milk cheese}:
Transactions of {milk}: {0, 3, 4}
Transactions of {cheese}: {1, 2, 3, 4}
Transactions of {milk cheese}: {0, 3, 4} n {1, 2, 3, 4} = {3, 4}
Support of {milk cheese}: 2
Frequent: Yes
The final result is:
butter
eggs
bread
milk
cheese
butter cheese
eggs cheese
bread milk
bread cheese
milk cheese
This is perfect for learning as you can easily experiment with different input and see the results in your browser. However, this implementation of Eclat in Javascript is not designed to be efficient. For efficient implementations of frequent itemset mining algorithms, please see the SPMF software. It offers highly efficient implementations that can run on large databases.
By the way, I also created another webpage that gives an interactive demo of the Apriori algorithm, another popular algorithm for frequent itemset mining. And if you want to learn more about pattern mining, you may also be interested to check my free online course on pattern mining.
—
Philippe Fournier-Viger is a full professor working in China and founder of the SPMF open source data mining software.
