Notes

class Node:
def __init__(self, item, count, parent):
self.i = item
self.c = count
self.p = parent
self.children = {}
self.next = None

def create_fp_tree(ds, min_sup):
ht = {}
for t in ds:
for i in t:
ht[i] = ht.get(i, 0) + ds[t]

for i in list(ht):
if ht[i] < min_sup:
del(ht[i])

freq_items = set(ht.keys())

if len(freq_items) == 0:
return None, None

for i in ht:
ht[i] = [ht[i], None]

tree = Node("Null", 1, None)

for t, c in ds.items():
local_d = {}
for i in t:
if i in freq_items:
local_d[i] = ht[i][0]
if len(local_d) > 0:
ordered_items = [v[0] for v in sorted(local_d.items(), key=lambda x: (-x[1], x[0]))]
insert_tree(ordered_items, tree, ht, c)

return tree, ht

def insert_tree(items, node, ht, count):
if items[0] in node.children:
node.children[items[0]].c += count
else:
node.children[items[0]] = Node(items[0], count, node)

if ht[items[0]][1] is None:
ht[items[0]][1] = node.children[items[0]]
else:
update_header(ht[items[0]][1], node.children[items[0]])

if len(items) > 1:
insert_tree(items[1:], node.children[items[0]], ht, count)

def update_header(n, t):
while n.next is not None:
n = n.next
n.next = t

def ascend_tree(n, p):
if n.p is not None:
p.append(n.i)
ascend_tree(n.p, p)

def find_prefix_path(b, t):
cp = {}
while t is not None:
p = []
ascend_tree(t, p)
if len(p) > 1:
cp[frozenset(p[1:])] = t.c
t = t.next
return cp

def print_tree(n, i):
print(' ' * i, n.i, ' ', n.c)
for c in n.children.values():
print_tree(c, i + 3)

def mine_tree(tree, ht, min_sup, prefix, freq_sets):
bigL = [v[0] for v in sorted(ht.items(), key=lambda x: (-x[1][0], x[0]))]

for b in bigL:
new_set = prefix.copy()
new_set.add(b)
freq_sets.append(new_set)
cpb = find_prefix_path(b, ht[b][1])
my_tree, my_head = create_fp_tree(cpb, min_sup)

if my_head is not None:
print("Cond FP-tree for", new_set)
print_tree(my_tree, 1)
print()
mine_tree(my_tree, my_head, min_sup, new_set, freq_sets)

def fp_growth(ds, min_sup):
tree, ht = create_fp_tree(ds, min_sup)
print("FP-Tree:")
print_tree(tree, 1)
print()
freq_sets = []
mine_tree(tree, ht, min_sup, set(), freq_sets)
return freq_sets

# Example input dataset
ds = {
frozenset({'bread', 'milk'}): 2,
frozenset({'bread', 'diaper', 'beer', 'eggs'}): 1,
frozenset({'bread', 'diaper', 'beer', 'cola'}): 1,
frozenset({'bread', 'milk', 'diaper', 'beer'}): 1,
frozenset({'milk', 'diaper', 'beer', 'cola'}): 1
}

# Minimum support threshold
min_sup = 2

# Run FP-Growth algorithm
freq_sets = fp_growth(ds, min_sup)

# Display frequent itemsets
print("Frequent Itemsets:")
for s in freq_sets:
print(s)