Skip to content

Instantly share code, notes, and snippets.

@n1try n1try/apriori.py
Last active Feb 14, 2018

Embed
What would you like to do?
Naive implementation of the Apriori algorithm in Python
# Naive implementation of the Apriori algorithm in Python
# Example 2 from https://en.wikipedia.org/wiki/Apriori_algorithm
data = [
{1,2,3,4},
{1,2,4},
{1,2},
{2,3,4},
{2,3},
{3,4},
{2,4}
]
def support(tx, txs, absolute=False):
if absolute: return len([t for t in txs if t.issuperset(tx)])
return len([t for t in txs if t.issuperset(tx)]) / len(txs)
def apriori(txs, min_sup):
l = [[{i} for i in set().union(*txs) if support({i}, txs, min_sup > 1) > min_sup]]
k = 1
while len(l[k-1]) > 0:
c = list(set([frozenset(s.union(i)) for i in l[0] for s in l[k-1] if s != i and len(i) == 1 and len(s.union(i)) == k+1])) # frozensets are hashable
l.insert(k, [ct for ct in c if support(ct, txs, min_sup > 1) >= min_sup])
k += 1
return l
if __name__ == '__main__':
min_sup = 3
fis = apriori(data, min_sup)
if len(fis[0]) < 1: print('Did not find any frequent item sets with support of {}'.format(min_sup))
else: print('Maximum length ({}) frequent item sets are: {}'.format(len(fis[-2][0]), [tuple(s) for s in fis[-2]]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.