|
|
{% extends "layout.html" %}
|
|
|
|
|
|
{% block content %}
|
|
|
<!DOCTYPE html>
|
|
|
<html lang="en">
|
|
|
<head>
|
|
|
<meta charset="UTF-8">
|
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
|
|
<title>Study Guide: Eclat Algorithm</title>
|
|
|
|
|
|
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
|
|
|
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
|
|
|
<style>
|
|
|
|
|
|
body {
|
|
|
background-color: #ffffff;
|
|
|
color: #000000;
|
|
|
font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, Helvetica, Arial, sans-serif;
|
|
|
font-weight: normal;
|
|
|
line-height: 1.8;
|
|
|
margin: 0;
|
|
|
padding: 20px;
|
|
|
}
|
|
|
|
|
|
|
|
|
.container {
|
|
|
max-width: 800px;
|
|
|
margin: 0 auto;
|
|
|
padding: 20px;
|
|
|
}
|
|
|
|
|
|
|
|
|
h1, h2, h3 {
|
|
|
color: #000000;
|
|
|
border: none;
|
|
|
font-weight: bold;
|
|
|
}
|
|
|
|
|
|
h1 {
|
|
|
text-align: center;
|
|
|
border-bottom: 3px solid #000;
|
|
|
padding-bottom: 10px;
|
|
|
margin-bottom: 30px;
|
|
|
font-size: 2.5em;
|
|
|
}
|
|
|
|
|
|
h2 {
|
|
|
font-size: 1.8em;
|
|
|
margin-top: 40px;
|
|
|
border-bottom: 1px solid #ddd;
|
|
|
padding-bottom: 8px;
|
|
|
}
|
|
|
|
|
|
h3 {
|
|
|
font-size: 1.3em;
|
|
|
margin-top: 25px;
|
|
|
}
|
|
|
|
|
|
|
|
|
strong {
|
|
|
font-weight: 900;
|
|
|
}
|
|
|
|
|
|
|
|
|
p, li {
|
|
|
font-size: 1.1em;
|
|
|
border-bottom: 1px solid #e0e0e0;
|
|
|
padding-bottom: 10px;
|
|
|
margin-bottom: 10px;
|
|
|
}
|
|
|
|
|
|
|
|
|
li:last-child {
|
|
|
border-bottom: none;
|
|
|
}
|
|
|
|
|
|
|
|
|
ol {
|
|
|
list-style-type: decimal;
|
|
|
padding-left: 20px;
|
|
|
}
|
|
|
|
|
|
ol li {
|
|
|
padding-left: 10px;
|
|
|
}
|
|
|
|
|
|
|
|
|
ul {
|
|
|
list-style-type: none;
|
|
|
padding-left: 0;
|
|
|
}
|
|
|
|
|
|
ul li::before {
|
|
|
content: "•";
|
|
|
color: #000;
|
|
|
font-weight: bold;
|
|
|
display: inline-block;
|
|
|
width: 1em;
|
|
|
margin-left: 0;
|
|
|
}
|
|
|
|
|
|
|
|
|
pre {
|
|
|
background-color: #f4f4f4;
|
|
|
border: 1px solid #ddd;
|
|
|
border-radius: 5px;
|
|
|
padding: 15px;
|
|
|
white-space: pre-wrap;
|
|
|
word-wrap: break-word;
|
|
|
font-family: "Courier New", Courier, monospace;
|
|
|
font-size: 0.95em;
|
|
|
font-weight: normal;
|
|
|
color: #333;
|
|
|
border-bottom: none;
|
|
|
}
|
|
|
|
|
|
|
|
|
.story-eclat {
|
|
|
background-color: #fff5f6;
|
|
|
border-left: 4px solid #d63384;
|
|
|
margin: 15px 0;
|
|
|
padding: 10px 15px;
|
|
|
font-style: italic;
|
|
|
color: #555;
|
|
|
font-weight: normal;
|
|
|
border-bottom: none;
|
|
|
}
|
|
|
|
|
|
.story-eclat p, .story-eclat li {
|
|
|
border-bottom: none;
|
|
|
}
|
|
|
|
|
|
.example-eclat {
|
|
|
background-color: #ffeff4;
|
|
|
padding: 15px;
|
|
|
margin: 15px 0;
|
|
|
border-radius: 5px;
|
|
|
border-left: 4px solid #e67ab0;
|
|
|
}
|
|
|
|
|
|
.example-eclat p, .example-eclat li {
|
|
|
border-bottom: none !important;
|
|
|
}
|
|
|
|
|
|
|
|
|
.quiz-section {
|
|
|
background-color: #fafafa;
|
|
|
border: 1px solid #ddd;
|
|
|
border-radius: 5px;
|
|
|
padding: 20px;
|
|
|
margin-top: 30px;
|
|
|
}
|
|
|
.quiz-answers {
|
|
|
background-color: #ffeff4;
|
|
|
padding: 15px;
|
|
|
margin-top: 15px;
|
|
|
border-radius: 5px;
|
|
|
}
|
|
|
|
|
|
|
|
|
table {
|
|
|
width: 100%;
|
|
|
border-collapse: collapse;
|
|
|
margin: 25px 0;
|
|
|
}
|
|
|
th, td {
|
|
|
border: 1px solid #ddd;
|
|
|
padding: 12px;
|
|
|
text-align: left;
|
|
|
}
|
|
|
th {
|
|
|
background-color: #f2f2f2;
|
|
|
font-weight: bold;
|
|
|
}
|
|
|
|
|
|
|
|
|
@media (max-width: 768px) {
|
|
|
body, .container {
|
|
|
padding: 10px;
|
|
|
}
|
|
|
h1 { font-size: 2em; }
|
|
|
h2 { font-size: 1.5em; }
|
|
|
h3 { font-size: 1.2em; }
|
|
|
p, li { font-size: 1em; }
|
|
|
pre { font-size: 0.85em; }
|
|
|
table, th, td { font-size: 0.9em; }
|
|
|
}
|
|
|
</style>
|
|
|
</head>
|
|
|
<body>
|
|
|
|
|
|
<div class="container">
|
|
|
<h1>⚡ Study Guide: The Eclat Algorithm</h1>
|
|
|
|
|
|
|
|
|
|
|
|
<div>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<a
|
|
|
href="/eclat-three"
|
|
|
target="_blank"
|
|
|
onclick="playSound()"
|
|
|
class="
|
|
|
cursor-pointer
|
|
|
inline-block
|
|
|
relative
|
|
|
bg-blue-500
|
|
|
text-white
|
|
|
font-bold
|
|
|
py-4 px-8
|
|
|
rounded-xl
|
|
|
text-2xl
|
|
|
transition-all
|
|
|
duration-150
|
|
|
|
|
|
/* 3D Effect (Hard Shadow) */
|
|
|
shadow-[0_8px_0_rgb(29,78,216)]
|
|
|
|
|
|
/* Pressed State (Move down & remove shadow) */
|
|
|
active:shadow-none
|
|
|
active:translate-y-[8px]
|
|
|
">
|
|
|
Tap Me!
|
|
|
</a>
|
|
|
</div>
|
|
|
|
|
|
<script>
|
|
|
function playSound() {
|
|
|
const audio = document.getElementById("clickSound");
|
|
|
if (audio) {
|
|
|
audio.currentTime = 0;
|
|
|
audio.play().catch(e => console.log("Audio play failed:", e));
|
|
|
}
|
|
|
}
|
|
|
</script>
|
|
|
|
|
|
|
|
|
<h2>🔹 Core Concepts</h2>
|
|
|
<div class="story-eclat">
|
|
|
<p><strong>Story-style intuition: The Efficient Librarian</strong></p>
|
|
|
<p>Imagine our Supermarket Detective (from the Apriori guide) has a new colleague, an efficient librarian. The detective uses a "horizontal" approach: they go through each shopping receipt one by one to see what's inside. The librarian uses a "vertical" approach. Instead of looking at receipts, they create an index card for every single item in the store. On the card for "Milk," they simply list the ID number of every receipt that contains milk. To find out how many people bought {Milk, Bread} together, they just take the two cards and find the common receipt IDs. This is the core idea of <strong>Eclat</strong>. It's often much faster because finding common IDs between two lists is a very quick operation.</p>
|
|
|
</div>
|
|
|
<p>The <strong>Eclat Algorithm</strong> (Equivalence Class Clustering and bottom-up Lattice Traversal) is an efficient algorithm for frequent itemset mining. Unlike Apriori, which scans the database horizontally (transaction by transaction), Eclat uses a <strong>vertical data format</strong> and finds frequent itemsets by intersecting transaction ID lists. This approach can be significantly faster, especially for dense datasets.</p>
|
|
|
|
|
|
<h2>🔹 Key Definitions</h2>
|
|
|
<ul>
|
|
|
<li>
|
|
|
<strong>Itemset:</strong> A collection of one or more items (e.g., {Milk, Diapers}).
|
|
|
</li>
|
|
|
<li>
|
|
|
<strong>Support:</strong> The number of transactions an itemset appears in. Note: Eclat often uses the raw count, not the percentage.
|
|
|
</li>
|
|
|
<li>
|
|
|
<strong>Tidset (Transaction ID set):</strong> The set of all transaction IDs (TIDs) that contain a specific itemset. This is the heart of the vertical data format.
|
|
|
<div class="example-eclat">
|
|
|
<p><strong>Example:</strong>
|
|
|
<br>TID(Milk) = {T1, T3, T4}
|
|
|
<br>TID(Bread) = {T1, T2, T4, T5}
|
|
|
</p>
|
|
|
</div>
|
|
|
</li>
|
|
|
<li>
|
|
|
<strong>Vertical Data Format:</strong> The data is structured as a map from each item to its tidset, instead of the traditional list of transactions.
|
|
|
</li>
|
|
|
</ul>
|
|
|
|
|
|
<h2>🔹 The Eclat Principle</h2>
|
|
|
<div class="story-eclat">
|
|
|
<p><strong>The Librarian's Smart Trick:</strong> The librarian's method for finding the support of a combined itemset is incredibly fast. To find the support of {Milk, Bread}, they don't need to look at any receipts. They just take the two index cards and find the common numbers (the intersection).</p>
|
|
|
</div>
|
|
|
<p>The core principle of Eclat is that the support of a larger itemset can be computed directly by intersecting the tidsets of its smaller subsets. The size of the resulting intersection is the support count.</p>
|
|
|
<p>$$ \text{Support}(X \cup Y) = |TID(X) \cap TID(Y)| $$</p>
|
|
|
<div class="example-eclat">
|
|
|
<p><strong>Example:</strong>
|
|
|
<br>TID(Milk) = {T1, T3, T4}
|
|
|
<br>TID(Bread) = {T1, T2, T4, T5}
|
|
|
<br>TID({Milk, Bread}) = TID(Milk) ∩ TID(Bread) = {T1, T4}
|
|
|
<br>Support({Milk, Bread}) = |{T1, T4}| = 2.</p>
|
|
|
</div>
|
|
|
|
|
|
<h2>🔹 Algorithm Steps</h2>
|
|
|
<p>Eclat uses a depth-first search (DFS) approach to explore the search space of itemsets.</p>
|
|
|
|
|
|
<ol>
|
|
|
<li><strong>Convert to Vertical Format:</strong> Scan the database once to transform the horizontal list of transactions into a vertical map of item → tidset.</li>
|
|
|
<li><strong>Find Frequent 1-Itemsets:</strong> Find all items whose tidset size is greater than or equal to `min_support`.</li>
|
|
|
<li><strong>Recursive Search (DFS):</strong>
|
|
|
<ul>
|
|
|
<li>Start with a frequent 1-itemset (e.g., {Milk}).</li>
|
|
|
<li>Find all other frequent items that can be combined with it.</li>
|
|
|
<li>For each combination (e.g., {Milk, Bread}), calculate the new tidset by intersection.</li>
|
|
|
<li>If the new tidset is frequent (its size ≥ `min_support`), add it to the list of frequent itemsets and then use this new itemset as the base for the next level of recursion (e.g., find combinations like {Milk, Bread, Butter}).</li>
|
|
|
</ul>
|
|
|
</li>
|
|
|
<li><strong>Continue</strong> this recursive process until no more frequent itemsets can be generated from a branch.</li>
|
|
|
</ol>
|
|
|
|
|
|
<h2>🔹 Comparison with Apriori</h2>
|
|
|
<table>
|
|
|
<thead>
|
|
|
<tr>
|
|
|
<th>Feature</th>
|
|
|
<th>Eclat</th>
|
|
|
<th>Apriori</th>
|
|
|
</tr>
|
|
|
</thead>
|
|
|
<tbody>
|
|
|
<tr>
|
|
|
<td><strong>Data Format</strong></td>
|
|
|
<td><strong>Vertical</strong> (Item → {TID1, TID2, ...})</td>
|
|
|
<td><strong>Horizontal</strong> (TID → {Item1, Item2, ...})</td>
|
|
|
</tr>
|
|
|
<tr>
|
|
|
<td><strong>Search Method</strong></td>
|
|
|
<td><strong>Depth-First Search (DFS)</strong></td>
|
|
|
<td><strong>Breadth-First Search (BFS)</strong></td>
|
|
|
</tr>
|
|
|
<tr>
|
|
|
<td><strong>Main Operation</strong></td>
|
|
|
<td>Tidset <strong>intersection</strong>.</td>
|
|
|
<td>Candidate <strong>generation</strong> and database scanning.</td>
|
|
|
</tr>
|
|
|
<tr>
|
|
|
<td><strong>Performance</strong></td>
|
|
|
<td>Generally faster, especially on dense datasets.</td>
|
|
|
<td>Can be slow due to repeated database scans and large candidate sets.</td>
|
|
|
</tr>
|
|
|
</tbody>
|
|
|
</table>
|
|
|
|
|
|
<h2>🔹 Strengths & Weaknesses</h2>
|
|
|
<h3>Advantages:</h3>
|
|
|
<ul>
|
|
|
<li>✅ <strong>Faster than Apriori:</strong> Avoids the expensive process of candidate generation and repeated database scans. Support counting via intersections is very fast.</li>
|
|
|
<li>✅ <strong>Efficient for Dense Data:</strong> Works particularly well when transactions are long and contain many items.</li>
|
|
|
</ul>
|
|
|
<h3>Disadvantages:</h3>
|
|
|
<ul>
|
|
|
<li>❌ <strong>Memory Intensive:</strong> The tidsets, especially for frequent items in a large dataset, can become very long and consume a lot of memory.</li>
|
|
|
<li>❌ <strong>Less Common:</strong> Not as widely implemented in standard machine learning libraries as Apriori.</li>
|
|
|
</ul>
|
|
|
|
|
|
<h2>🔹 Python Implementation (Conceptual Example)</h2>
|
|
|
<div class="story-eclat">
|
|
|
<p>Since Eclat is less common in libraries like `scikit-learn`, here's a conceptual Python example using a library called `pyECLAT`. The logic mirrors the algorithm steps: we prepare the data, create an Eclat object, and call `fit()` to get the frequent itemsets.</p>
|
|
|
</div>
|
|
|
<pre><code>
|
|
|
# NOTE: You would need to install pyECLAT first: pip install pyECLAT
|
|
|
import pandas as pd
|
|
|
from pyECLAT import ECLAT
|
|
|
|
|
|
# --- 1. Create a Sample Dataset in the right format ---
|
|
|
# The data is a DataFrame where each row is a transaction.
|
|
|
# NaN values are used for padding.
|
|
|
data = {'Transaction': [1, 2, 3, 4, 5],
|
|
|
'Items': [['Milk', 'Beer', 'Diapers'],
|
|
|
['Bread', 'Butter', 'Milk'],
|
|
|
['Beer', 'Diapers', 'Milk', 'Cola'],
|
|
|
['Bread', 'Butter', 'Beer', 'Diapers'],
|
|
|
['Bread', 'Butter']]}
|
|
|
df = pd.DataFrame(data)
|
|
|
|
|
|
# --- 2. Initialize and Run the Eclat Algorithm ---
|
|
|
# We create an ECLAT object from our transactions data.
|
|
|
eclat_instance = ECLAT(data=df['Items'])
|
|
|
|
|
|
# You can see the binary (one-hot encoded) format it uses internally
|
|
|
# print(eclat_instance.df_bin)
|
|
|
|
|
|
# --- 3. Find Frequent Itemsets ---
|
|
|
# We set min_support to 0.4, meaning itemsets in at least 2 of the 5 transactions.
|
|
|
# The 'fit' method does all the work of intersecting tidsets.
|
|
|
min_support = 0.4
|
|
|
rule_indices, rule_supports = eclat_instance.fit(min_support=min_support,
|
|
|
min_combination=1, # Min number of items in an itemset
|
|
|
max_combination=3) # Max number of items
|
|
|
|
|
|
print("--- Frequent Itemsets (Support >= 40%) ---")
|
|
|
print(rule_supports)
|
|
|
</code></pre>
|
|
|
|
|
|
<h2>🔹 Best Practices</h2>
|
|
|
<ul>
|
|
|
<li><strong>Choose the Right Algorithm:</strong> Use Eclat for dense datasets where the number of transactions is not excessively large. For sparse data with many transactions, FP-Growth is often the best choice.</li>
|
|
|
<li><strong>Manage Memory:</strong> Be mindful that tidsets for very common items can be huge. If you run into memory issues, you may need to increase your `min_support` threshold.</li>
|
|
|
</ul>
|
|
|
|
|
|
<div class="quiz-section">
|
|
|
<h2>📝 Quick Quiz: Test Your Knowledge</h2>
|
|
|
<ol>
|
|
|
<li><strong>What is the fundamental difference in how Apriori and Eclat scan data?</strong></li>
|
|
|
<li><strong>If TID({A}) = {1, 2, 5} and TID({B}) = {2, 4, 5, 6}, what is the support count of the itemset {A, B}?</strong></li>
|
|
|
<li><strong>What is the main disadvantage of using Eclat on a dataset with millions of transactions?</strong></li>
|
|
|
<li><strong>What search strategy does Eclat use to find frequent itemsets?</strong></li>
|
|
|
</ol>
|
|
|
<div class="quiz-answers">
|
|
|
<h3>Answers</h3>
|
|
|
<p><strong>1.</strong> Apriori scans data <strong>horizontally</strong> (it reads each transaction to see what items it contains). Eclat uses a <strong>vertical</strong> format (it looks at each item to see which transactions it appeared in).</p>
|
|
|
<p><strong>2.</strong> The support is the size of the intersection of the tidsets: |{1, 2, 5} ∩ {2, 4, 5, 6}| = |{2, 5}| = <strong>2</strong>.</p>
|
|
|
<p><strong>3.</strong> The main disadvantage is high <strong>memory consumption</strong>, as the tidsets for very frequent items can become extremely large lists containing millions of transaction IDs.</p>
|
|
|
<p><strong>4.</strong> Eclat uses a <strong>Depth-First Search (DFS)</strong> strategy to traverse the lattice of potential itemsets.</p>
|
|
|
</div>
|
|
|
</div>
|
|
|
|
|
|
<h2>🔹 Key Terminology Explained (Eclat)</h2>
|
|
|
<div class="story-eclat">
|
|
|
<p><strong>The Story: Decoding the Efficient Librarian's Index</strong></p>
|
|
|
</div>
|
|
|
<ul>
|
|
|
<li>
|
|
|
<strong>Vertical Data Format:</strong>
|
|
|
<br>
|
|
|
<strong>What it is:</strong> A way of storing transactional data where each item is a key, and its value is a list of all transaction IDs it appears in.
|
|
|
<br>
|
|
|
<strong>Story Example:</strong> Instead of a pile of receipts, the librarian has a card catalog. Each drawer is an item ("Milk," "Bread," etc.), and each card in that drawer is a receipt ID. This is a <strong>vertical format</strong>.
|
|
|
</li>
|
|
|
<li>
|
|
|
<strong>Tidset Intersection:</strong>
|
|
|
<br>
|
|
|
<strong>What it is:</strong> The core operation of Eclat. It's the process of finding the common elements between two or more transaction ID lists.
|
|
|
<br>
|
|
|
<strong>Story Example:</strong> When the librarian takes the list of receipt IDs for "Milk" and the list for "Bread" and finds all the numbers that appear on both lists, they are performing a <strong>tidset intersection</strong>.
|
|
|
</li>
|
|
|
<li>
|
|
|
<strong>Depth-First Search (DFS):</strong>
|
|
|
<br>
|
|
|
<strong>What it is:</strong> A strategy for exploring a tree or graph structure. It goes as deep as possible down one path before backtracking.
|
|
|
<br>
|
|
|
<strong>Story Example:</strong> To find all combinations, the librarian starts with {Milk}, then immediately finds all frequent pairs starting with Milk, like {Milk, Bread}. Then, they try to extend that to {Milk, Bread, Butter} before backtracking to try other pairs like {Milk, Diapers}. This is a <strong>DFS</strong> approach.
|
|
|
</li>
|
|
|
</ul>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
</body>
|
|
|
</html>
|
|
|
{% endblock %}
|
|
|
|
